软件故障定位技术进展*
鞠小林1，2，3+，姜淑娟1，张艳梅1，董国伟2
1.中国矿业大学计算机科学与技术学院，江苏徐州221116
2.中国信息安全测评中心，北京100085
3.南通大学计算机科学与技术学院，江苏南通226019
Advances in Fault Localization Techniques ∗
JU Xiaolin 1，2，3+,JIANG Shujuan 1,ZHANG Yanmei 1,DONG Guowei 2
1.School of Computer Science and Technology,China University of Mining and Technology,Xuzhou,Jiangsu 221116,China
2.China Information Technology Security Evaluation Center,Beijing 100085,China
3.School of Computer Science and Technology,Nantong University,Nantong,Jiangsu 226019,China
+Corresponding author:
JU Xiaolin,JIANG Shujuan,ZHANG Yanmei,et al.Advances in fault localization techniques.Journal of Frontiers of Computer Science and Technology,2012,6(6)：481-494.
Abstract:Fault localization is a kind of time consuming and labor intensive work during debugging.To reduce the cost of debugging and assist the developers to locate and repair program faults,fault localization techniques navigate the fault program fragments by examining the source code and analyzing software behavior and test results.This paper reviews the recent achievements in the field of fault localization.And then,for many reprentative methods of fault localization,it gives a detail analysis by categories of their basic principles and the modeling methods.It also discuss the contribution of each work and the major difference between them,and prents some commonly-ud evaluation benchmarks and metrics.Finally,it concludes the future rearch consideration of fault localization techniques.Key words:program analysis;software debugging;fault diagnosis;fault localization;localization metrics
*The National Natural Science Foundation of China under Grant Nos.90818021,60970032,61100047(国家自然科学基金);the Natural Science Foundation of Jiangsu Province of China under Grant No.BK2008124(江苏省自然科学基金);the Graduate Training Innovative Projects Foundation of Jiangsu Province under Grant No.CX10B_157Z (江苏省研究生培
养创新工程项目).
Received 2012-02,Accepted 2012-04.
ISSN 1673-9418CODEN JKYTA8
Journal of Frontiers of Computer Science and Technology 1673-9418/2012/06(06)-0481-14DOI:10.3778/j.issn.1673-9418.2012.06.001E-mail:fcst@ http ：// Tel:
+86-10-51616056
Journal of Frontiers of Computer Science and Technology 计算机科学与探索2012,6(6)1引言软件调试需要程序员进行大量的人机交互[1]。故障定位是调试过程中最为耗时和费力的活动之一[2]，它通过审查源程序语义和结构，结合分析程序的执行过程及结果，辅助开发人员找到软件故障位置。研究人员提出了一系列自动化的故障定位方法，这些方法可分为静态方法和动态方法。静态方法利用程序的依赖关系、类型约束等信息来分析程序中的可能故障点；动态方法则通过测试程序，跟踪程序的执行轨迹和覆盖信息来进行故障定位。高效地定位软件故障可减轻程序员手工排查程序语句的工作量，提升调试速度和效率。本文调研了近30年来出现的具有代表性的软件故障定位方法，分类并说明了其原理及模型，讨论了这些方法的主要成果并对它们进行了比较，给出了常用的评测集和故障定位评价方法，最后展望了软件故障定位的进一步研究方向。2故障定位技术概述2.1问题的提出根据IEEE 标准定义，故障是隐藏在程序中不正确的指令、过程或数据定义[3]。故障是由程序员的失误引入的，一次失误可能导致一个或多个软件故障，这些故障隐藏于程序中的一条语句或分散的若干语句之中。故障定位的粒度，可以是程序语句，也可以是程序的分支、函数、方法或类等基本块。语句和基本块统称为程序实体。定义程序P 由m 个程序实体组成，记为P ={s 1，s 2，...，s m }[4]。定义S '={s '1，s '2，...，s 'k }为程序P 存在的故障，其中S 'ÍP ，s 'j (1 j k )为存在故障的程序实体。故障定位是找出P 中所有的存在故障程序实体
集合S '的过程。
不妨假设P 中的程序实体都有可能出错，从而将精确定位故障转化为计算所有程序实体出错的可能性，可得到一个程序实体的故障怀疑度降序列表Rank =[s '1，s '2，...，s 'm ]，s 'j ÎP (1 j m )。简言之，故障定位的关键任务就是求得程序实体怀疑度排名列表，程序员调试时依次检查排名列表中的程序实体，直至找到真正软件故障。
2.2相关研究
人们提出了一系列用于调试的自动故障定位方法[5-21]。Weir [5]最早提出了可将程序切片用于软件左右互搏术
调试中。Al-Khanjari 等人[6-10]进一步研究了在故障定位中应用切片技术。Renieris 和Reiss [11]比较了程序成功和失败执行的相似执行序列的差异，提出了基于相似程序频谱的最近邻查询（nearest neighbor que-ries ，NNQ ）方法。Jones 等人[12]认为语句的故障怀疑度与其执行失败的次数正相关，提出了用不同颜色
表示语句故障可疑程度的方法。Han 等人[13]对谓词
在成功和失败执行时的取值模式进行建模，量化每
个谓词取值模式与故障之间统计相关性，提出了基于假设检验的SOBER 方法。Cellier [14]将形式概念分析用于故障定位。Ali 等人[15]应用数据挖掘中分类技术进行故障定位。国内学者在故障定位领域
也进行了相关研究，取得了一些研究成果。虞凯等人[16]对软件错误的动态定位技术进行了比较全面的总结，并提出了一种基于多频谱的定位技术[17]；王新平等人提
出了基于程序执行轨迹的故障定位方法[18]；徐宝文等人[19]提出了基于组合测试的调试方法；严俊等人[20]也对基于组合测试的故障定位技术进行了总结；郝丹
摘要：故障定位是调试过程中一项耗时费力的工作。为了降低调试成本，并辅助开发人员定位和修复软件故障，软件故障定位技术通过审查源代码、分析测试过程的软件行为和测试结果来定位包含故障的代码片段。综述了近期故障定位领域相关成就，分类介绍了各种代表性的故障定位方法的基本原理和建模技术，讨论了这些故障定位技术的贡献以及它们之间的主要区别，给出了常用的故障定位效果基准测试集和度量方法，展望了故障定位技术的研究方向。
关键词：程序分析；软件调试；故障诊断；故障定位；定位度量
文献标识码：A 中图分类号：TP311
482
等人[21]考虑了测试用例之间的相似性对故障定位的影响，提出了基于相知相似度故障定位（similarity-aware fault localization ，SAFL ）方法。3软件故障定位技术的分类依据定位过程“是否需要运行软件”准则，将故障定位技术分为两大类：（1）基于静态分析的故障定位（static analysis-bad
fault localization ，SABFL ）。依据程序语言的语法和语义，静态分析软件结构和程序实体之间依赖关系以发现违反系统约束的程序实体，从而定位故障。（2）基于测试的故障定位（test-bad fault local-ization ，TBFL ）。设计测试用例并运行软件，依据程序执行轨迹及输出结果进行故障定位。3.1基于静态分析的故障定位静态分析指不运行程序而分析程序源码或目标码。目前主要有四种基于静态分析的故障定位方法：面向语句的方法、符号执行方法、形式化方法和指针分析方法。3.1.1面向语句的方法面向语句的方法依据程序设计语言的基本约束，检测程序的语法、控制结构以及数据类型等问题，定位故障并提出警告或给出修复建议。有两种实现方式：一种是将语法分析、类型分析等分析
技术集成到编译器或集成开发环境[22]，随程序编辑过程进行静态分析以识别故障；另一种方式通过独立分析工具或开发环境的外部插件，静态分析程序语句以定位故障。FindBugs [23]是一个开源的用于静态分析Java 源程序及字节码的框架，采用不同技术设计故障或缺陷检测器，并定义相应的故障或缺陷模式，在程序编辑和调试时检测并定位Java 源程序的故障，同时给出修复建议。FindBugs 预定义了300多种故障和缺陷模式，例如文件未关闭、缺少必要的或多余的null check 等。赵建军等人[24]在FindBugs 基础上，定义了用于检测面向方面（aspect-oriented ）系统的17种故障模式，并设计了用于检测AspectJ 故障的XFindBugs 系统。面向语句的方法一般用于编辑或调试程序时定
位与程序语法结构、变量类型以及系统约束有关的
故障，但不能发现与程序逻辑有关的故障，如不可达
路径、程序死锁等。脸上长小痘痘
3.1.2符号执行方法
勠力
符号执行[25]指不执行程序，用符号（如x ）作为变
量的值，对程序各条路径模拟执行，跟踪被模拟的各
条执行路径上变量的值（实际上是符号x 的表达式），从而得到一组关于变量初始值的约束，称为路径条件。只有当路径条件满足时，对应路径才是可执行的。需用约束求解方法来判定路径条件是否满足，
并需要考虑两种情形：（1）如果得到的路径条件是布尔表达式，则该约束求解问题是NP 问题；（2）如果得到的路径条件是一组数值表达式，则可用线性规划
求解。把分析工作限定在实际可达路径上，能为程
序员提供更为准确的故障相关的上下文信息。King [25]最早在调试中使用符号执行方法，实验表明符号执行可以较好地适用于顺序程序的调试。Young 等人[26]提出了结合符号执行的并发分析技术，
用于检测并发程序中的故障。他们首先基于Taylor
算法[26]生成一组程序流图，并为每个流图分配一个Token （代表控制线程），然后用路径表达式表示符号执行的值，路径条件表示符号执行条件，自上而下符号执行程序流图，检查访问冲突、死锁等故障。符号执行避免了构造测试用例和运行程序，但是也面临两个主要难题：
（1）复杂的结构语义和操作语义建模问题。符号执行要对被分析代码的结构语义和操作语义进行
建模，构建一个虚拟机模型。符号执行是路径敏感的分析方法，因此一般为每条路径创建一个专属虚拟机模型，以保证路径之间相互独立。编程语言中使用的数据结构和操作语句具有复杂性和灵活性，使得建模变得十分困难，而模型准确程度将直接影响静态分析结果精度。
（2）路径爆炸问题。程序可执行路径随程序规模的增大呈指数增长，分析工作量随之急剧增加[27]。3.1.3形式化方法
燃气灶哪个好形式化方法采用数学及逻辑方法描述和验证软
鞠小林等：软件故障定位技术进展
483
早发Journal of Frontiers of Computer Science and Technology计算机科学与探索2012,6(6)
件系统。描述内容包括系统性质和行为。系统性质指系统必须满足的约束，系统行为指为实现系统功能所执行的动作。描述系统性质称为规约，描述系统行为称为建模。形式化验证主要包括两类方法：一类是以逻辑推理为基础的定理证明，将软件验证问题转化为数学定理证明问题，判断程序是否满足指定属性[28]；另一类是以穷尽搜索为基础的模型检验[29]，通过显式状态搜索或隐式不动点计算来验证有穷状态并发/实时系统的模态/命题性质。
Flanagan等人[30]利用条件验证和自动定理证明技术设计了静态检查Java代码的检查器（ESC/Java），可在编译Java代码时检测常见的源代码故障。在程序中添加简单的标注语言，形式化表示程序决策，ESC/Java检查这些带标注语言的源代码，对标注语言表示的决策与实际程序代码不一致部分给出警告信息，或者给出潜在运行时故障警告。
定理证明和模型检验可用于检测软件死锁等故障，但由于需要先建立软件的形式化模型，增加了额外的工作量。此外它们与符号执行一样，面临着状态空间爆炸问题，因此在实际软件故障定位中应用较少。
3.1.4指针分析方法
指针分析[31]用于确定指针值以及所指对象的存储位置。程序运行遇到空指针解引用（null pointer dereference，NPR）时会引发异常。NPR问题是指针分析研究的重点内容。研究者针对NPR问题开展了多方面研究，提出的NPR分析方法可以分为两类：第一类方法是自动推导出空指针标注。Cousot 等人最先提出指针分析[32]，定义了一个抽象域概念来描述程序空值变量，通过抽象解释形式证明了抽象域描述的正确性[33]。Hubert等人[34]提出了一种空指针分析方法，通过扩展抽象域推导出非空字段，基于约束分析以识别NPR。抽象域只能描述一般指针变量空值情形，不能处理对象指针空值情形。
第二类方法需要预先给程序代码段添加空指针标注。Male等人[35]对类的检查算法进行了扩展，通过检查类和过程内传递的标注进行指针分析。这种方法将指针分析的范围局限在类或过程内部，借助指针分析工具进行全局分析，可以获得较高的局部分析精度，但得到的结果可能不正确或不完整。Spoto[36]提出了一种用抽象解释构造和证明上下文敏感的静态空指针分析方法，该方法构造二叉决策图，对Java字节码和Java代码进行基于布尔表达式的非空标注推断。
指针分析往往借助符号执行或实际执行程序，而且指针问题常与内存泄露、访问越界等相关。受可判定性问题的制约，加上分析时间和存储空间等限制，多数的指针分析采用“近似”或者“简化”策略，导致分析结果不够精确[27]。
静态分析可以提早发现和定位程序故障，减少后期维护成本。此外，静态分析理论知识完备，已开发了一些商用或开源静态分析工具（如FindBugs、JLINT、PMD、ESC/Java等）。静态分析能发现动态分析难以发现的故障，但静态分析技术也具有局限性，需要改进和完善。
3.2基于测试的故障定位
基于测试的故障定位通过选择测试用例，运行待测程序，跟踪并分析程序执行过程及结果，从而定位软件故障。根据定位故障利用的信息及定位方式，基于测试的故障定位技术可以分为以下三类：基于执行覆盖的故障定位（coverage-bad fault localization，CBFL）、基于依赖关系的故障定位（dependency-bad fault localization，DBFL）、基于模型的故障定位（model-bad fault localization，MBFL）。
3.2.1基于执行覆盖的故障定位
韩国和朝鲜的关系CBFL跟踪程序执行轨迹及执行结果，计算程序实体的故障怀疑度。程序执行轨迹可以通过程序的输出、插装代码或者平台接口获取[27]。根据计算怀疑度的方法和策略，将故障定位方法分为以下三类：集合运算法、概率统计法和怀疑度计算优化。
（1）集合运算法
集合运算法认为出现在失败执行轨迹中的程序实体可能存在故障，采用集合的并和交运算缩小怀疑范围[11，39]。一次失败运行轨迹为Tr f，一组成功运行轨迹为Tr1
p
Tr2
p
... Tr k
p
，并和交运算的结果分别为
Tr
f
- i=1k Tr i p和 i=1k Tr i p-Tr f。通常并集比交集得
484
到的可疑故障集规模大，程序员需要检查更多的程序实体，但故障查全率比后者高。Renieris 和Reiss [11]提出了最近邻执行轨迹NNQ 故障定位方法。对于一个失败的执行轨迹Tr f 和许多成功的执行轨迹Tr 1p Tr 2p ... Tr k
p ，根据距离准则从Tr 1p Tr 2p ... Tr k p 中选择一条与Tr f 距离最近的一条
Tr m p ，可疑故障集用Tr f -Tr m p 表示。计算轨迹距离可用海明距离、夹角余弦或者排列距离。其中，海明距
离只关注程序实体是否被执行，不能反映两个执行轨迹间真正的相似性。夹角余弦距离直接用各程序
实体被执行的次数参与计算，受循环执行的影响较大。排列距离只考虑执行次数的相对关系，能较好地体现执行轨迹间的相似性[25]。NNQ 法分离出一部分程序实体作为可疑故障集合。（2）概率统计法概率统计法认为程序中每一个可执行实体都可能存在故障，但可疑程度不同，可以根据概率统计原理，计算每个程序实体存在故障的概率。Jones 等人[12]认为程序语句存在故障的可能性与它被失败用例执行的次数正相关，提出了用红-黄-绿等颜色可视化表示语句存在故障的可疑程度，红色表示高度可疑，绿色表示不怀疑。并且给出了颜色计算公式，实现了可视化故障定位工具Tarantula 。Jones 等人[37]进一步给出了语句s 的怀疑度计算公式如下：Tarantula (s )=T f (s )|
|T f T p (s )||T p +T f (s )||T f （1）其中，T f (s )和T p (s )分别表示语句s 失败执行和成功执行的次数；||T p 和||T f 分别表示测试通过和未通过的测试用例数。Tarantula 方法需要一个较大规模的测试集，并且至少需要一次通过测试和一次未通过测试。怀疑度的取值范围从0到1，数值越大，表示语句出错的概率越大。计算每个可执行语句的怀疑度，调试人员依怀疑度降序检查语句，直至找到真正故障。Tarantula 方法容易推广到基本块、函数、方法等程序实体。此外，Tarantula 能一定程度地容忍故障语句偶尔出现在成功的执行覆盖中，而且这种容忍
有时能提升Tarantula 的故障定位有效性[37]。
Tarantula 方法提出之后，研究者陆续提出了一些类似的怀疑度计算方法[17-18]，但故障定位精度并没有
得到明显提高。Abreu 等人[38]引入分子生物学领域的相似系数（similarity coefficients ）Ochiai ，定义语句s
的怀疑度计算公式如下：
Ochiai (s )=T
(s )
（2）
Abreu 等人[38]也通过实验证明了Ochiai 的定位精度稍优于Tarantula 方法，并且在定位多故障时与Tarantula 方法相比，定位性能得到了提升[39]。Tarantula 方法与Ochiai 方法只考虑语句在成功执行的轨迹和失败执行的轨迹中的频率，没有考虑
语句与执行结果之间的关系。Wong 等人[40-41]提出了一个定义良好的统计方法Crosstab 。该方法分别统计成功执行与失败执行情况下，可执行语句s 分别被覆盖的次数，并构建该语句的交叉表，进而对s 计算χ2
统计量χ2(s )。χ2(s )表示语句s 与测试结果关联程度，在给定显著性水平χ2
σ下进行假设检验，可以判断
语句s 是否独立于测试结果。χ2(s )随着样本数量增多而上升，为方便度量怀疑度，转而求语句s 的相依系数M (s )=
，语句s 的怀疑度定
义如式（3）所示：
Crosstab (s )=ì
í
学跆拳道的好处
îïïM (s ),if φ(s )>10,if φ(s )=1-M (s ),if φ(s )<1
（3）
其中，φ(s )=(T f (s )/|T f |)/(T p (s )/|T p |)。当φ(s )=1时，则签证加急
χ2(s )=0，语句s 对软件成功执行和失败执行的贡献相同；当φ(s )>1时，则语句s 对失败执行的贡献较大，语句s 可能存在故障，怀疑度为M (s )；反之，当φ(s )<1时，则s 语句对成功执行的贡献较大，怀疑度为-M (s )。与上述基于语句的执行轨迹定位方法不同，文献[13，42]提出了基于谓词覆盖的故障定位技术。该技术考虑到程序中谓词取值（真/假）与其后某个故障的出现有着必然联系。例如，一段程序的谓词P 的真鞠小林等：软件故障定位技术进展
485
