一种故障传播感知的程序故障定位方法

何加浪 孟 锦 张 琨 张 宏

(南京理工大学计算机科学与技术学院 南京 210094)

1 引言

随着信息化的不断深入，人们对计算机软件的依赖不断增强，对软件质量的要求也越来越高；在某些关键领域要求软件必须具有很高的可信性，否则很可能造成重大损失。由于软件复杂性不断增大，程序员花费在故障定位上的时间越来越多，这严重阻碍了故障的修复和软件可信性的提升，因而软件的快速故障定位问题就成了国内外研究的热点。

目前的研究主要集中在基于覆盖的故障定位(Coverage-Based Fault-Localization, CBFL)技术方面。CBFL的主要思路是利用软件多次执行获取成功执行的覆盖路径和失败执行的覆盖路径，通过分析比较这两种覆盖路径，计算出覆盖路径中各节点包含故障的可疑度，然后根据可疑度将节点进行排序输出，程序员根据该有序序列依次检查各节点，最终确定故障位置。Jones等人[1]提出的 Tarantula技术使用程序语句作为覆盖节点，统计各语句在失败测试用例中被覆盖的相对次数与在成功测试用例中被覆盖的相对次数，然后使用上述两个相对次数的比值作为节点可疑度的计算值；之后，Wong等人[2]按成功和失败的测试用例对故障的支持度不同对各测试用例进行区分，改进了文献[1]的工作；但是基于语句的覆盖对所有语句都要进行统计分析，计算量较大，因而文献[3,4]使用软件中不同位置的断言作为节点，通过插桩技术构建覆盖路径，利用统计分析方法确定各断言处的可疑度；Zhang等人[5]在此基础上通过关键断言状态转换技术确定故障位置，其主要思想是在失败执行中强制改变某断言状态后若执行恢复正常，则认为该断言属于关键断言，进而根据关键断言确定节点可疑度。通过断言覆盖代替语句覆盖，有效降低了计算量，但是由于断言位置的确定并不能保证覆盖到真正的故障位置，因而定全率[6]会受到很大影响。Santelices等人[7]综合了前人的研究成果，分析比较了各种覆盖类型的特点，指出对于不同的故障，各种覆盖类型的故障定位技术各有优劣，因而提出了一种多类型覆盖方法并通过实验验证了方法的有效性和优越性。

上述研究都是在覆盖路径节点相互独立的基础上进行的，没有考虑故障在路径中的传播对可疑度的影响，因而文献[8]考虑采用边覆盖代替节点覆盖，根据边可疑度计算节点可疑度，使节点可疑度具有捕捉故障在节点间传播的能力；Zhao等人[9]在计算节点可疑度时考虑了节点的入边和出边，改进了文献[8]方法；但此类方法存在的主要问题是所有处在故障传播路径当中的节点可疑度值都会偏高，因为计算是沿着故障传播路径进行的，有些中间节点只是参与了故障传播，并不是故障的真正位置，因此不应参与相应计算。本文为了消除故障传播对中间节点可疑度计算的影响，不再使用覆盖路径中的边，而是直接生成具有表达故障传播能力的虚边(Virtual Edge, VE)来对节点可疑度进行修正，一方面解决了中间节点参与可疑度计算的问题；另一方面也降低了可疑度的计算复杂性。本文在第2节介绍了基本概念；第3节详细描述了本文所提出的可疑度计算模型 VE-CBFL；第 4节是相关实验和分析；最后在第5节给出结论。

2 基本概念

在程序故障定位中，目的是根据程序发生故障信息寻找程序故障位置，而故障一般是程序缺陷(bug)被触发产生的，故障定位实际上是寻找与故障对应的缺陷所在位置，因而本文约定：在不引起混淆的情况下故障和缺陷不加区分地使用。

定义 1 基础块：不含有跳转指令的顺序执行的语句片段；程序中所有基础块组成的集合记为B={b1,b2,… ,bm}。

性质 1 在CBFL类方法中，基础块内的各语句的可疑度相同。这较容易理解：基础块内不含跳转指令，在程序一次执行中基础块内的语句要么全被覆盖，要么都不被覆盖，因而像CBFL这类基于覆盖信息的方法无法分辨出基础块内语句可疑度的差别。

图1 示例程序的控制流图

3 VE-CBFL描述

3.1 初始s(vi)计算

表1 s(vi)计算的算法

3.2 s(vi)的修正

程序具有很强的逻辑性，在一个基础块发生的故障其真正位置也许位于另外的基础块，例如在程序某个位置释放了一块空间却在另一个位置再次使用、没有初始化的NULL指针等。在图1示例中，故障的真正位置在b2，然而却发生在b5处，这样按照前一节计算的结果s(b5) = 0 .800是最可疑的基础块就不能准确反映事实情况。本文思路是从可疑度最大的节点max{s(vi)}出发，判断与其直接前驱节点是否存在故障传播趋势，如果存在则递归处理该前驱节点直到到达某个节点vo不再存在这种传播趋势，然后以该节点为起点，以节点max{s(vi)}为终点建立一条虚边来修正vo的可疑度。

图2是对示例1进行处理的结果，最终生成虚边ve2,5对s(b2)进行修正，具体算法如表2所示，该算法首先找出初始可疑度最大的节点vmax，对于此节点存在两种可能：

图2 虚边的生成

4 实验和分析

4.1 评价指标和实验目的

序列不包含真正的故障位置，则该输出序列就不是完备的。

表2 s(vi)修正算法

本文实验的目的就是要在上述评价指标的基础上验证本文方法能有效而快速地定位故障位置，并且与其它方法进行比较，具体从以下3个方面考虑：

(1)分析本文方法在考虑故障传播因素时对故障定位的影响；

(2)在定准率、定全率、有效值和时间开销方面与同类方法相比，验证本文方法的有效性和优越性；

(3)验证本文在表1算法中提出的压缩空间对定全率指标的影响较小的结论。

针对第(1)，(3)两个方面本文选取 3个程序实例：图1示例，CDBug和DDBug[10]作为第1组实验；第2组实验按照程序规模选择8个实用程序作为程序对象，具体如表3所示。

4.2 实验结果及分析

表4是第1组程序的实验结果。表中给出了每种方法计算出来的s(vi)值，表中黑色粗体表示故障所在基础块，列中的黑色圆点代表执行测试用例覆盖的相应基础块。

以示例1为例，从表4中可以看出，文献[1]和文献[7]方法计算出可疑度最高的节点均是b5，没有考虑到故障的传播，获得的可疑度不够准确；而文献[9]方法计算出b2可疑度高于b5，但由于b4处在故障传播路径中，其可疑度受到了很大影响，甚至高出了b2；本文方法(VE-CBFL)在计算初始s(vi)值时s(b5)最大，根据表2描述的算法2修正后的s(b2)'值超过s(b5)'，与预期相符。在可疑空间压缩方面，示例1栏中的b1,b5被压缩掉，压缩率为33.3%；特别注意到在CDBug和DDBug栏中，尽管计算初始s(vi)值时均压缩掉b1，但在修正时由于检测到了b1处在故障传播路径中的起始位置，因而对其进行了修正，从而降低可疑空间的压缩对定全率μ的影响。

表3 故障软件版本相关信息

上述实例分析较好地验证了实验目的的(1), (3)两个方面；更进一步地，为了验证本文方法的有效性和优越性，按程序规模选取8个实用程序作为实验对象，分别从定准率、定全率、有效值和时间开销方面与同类方法相比。

从ξ的定义可知，ξ值与nC,nL两个参数有关，故障定位方法期望nC越小越好；而对于不同的方法，nL可能不同，为了对不同方法进行准确的比较，本文分别选取nL=max_nL及作为参数，实验结果如图3所示，图中软件id 是对上述8个程序按规模进行的编号。从图 3(a)可以看出这 4种方法随着软件规模的扩大，定准率都有所下降，这符合一般的软件越复杂越难找出隐藏故障的观点；另一方面通过曲线的比较可以看出本文方法(VE-CBFL)在定准率指标上具有一定优势；图3(b)是按nL= m in_nL对不同方法输出序列进行截断，从该图可以看出截断后各方法ξ值具有整体降低的趋势，这是由ξ的定义决定的，另外在6, 8处文献[1]和文献[7]方法由于这种截断都导致输出序列不再包含故障位置，从而使相应的ξ值等于零，造成定全率的下降。

图3 ξ比较结果

表5 定全率μ值比较

定全率反映了不同方法输出序列的完备性，一方面期望故障定位方法输出序列尽可能短，另一方面要求该序列尽量完备，在实际应用中可以根据不同类型程序的特点进行折中处理，具体可参考文献[11]设置保留度阈值的思想方法，本文不再赘述。

有效值是评价故障定位方法对程序员调试程序是否有帮助的指标，本文以传统的Ad hoc调试方法平均需要检查的基础块数目的期望为基准进行比较，实验结果如图4所示。从图中可以看出有效值η均大于零，这说明4种方法对程序员调试均有帮助，本文方法相对较好；但是考虑到程序员自身的调试经验，当η比较小时对调试帮助效果已不是很明显，从图中曲线下降趋势来看，本文方法对应曲线下降相对平稳，具有一定的优势。

图5是不同方法的时间开销对比，从图中可以看出随着程序规模的扩大，各方法时间开销都呈上升趋势；在程序规模相对小的情况下，本文方法时间开销相对较大；但随着程序规模的变大，其他方法时间开销迅速增加，而本文方法则相对缓慢；这主要是由于本文方法在计算节点可疑度时对空间进行了压缩的原因；尽管对空间的压缩需要消耗一定的时间，但是当程序规模很大时这种压缩所带来的优势十分明显。

5 结束语

软件的快速故障定位是提高软件可信性的前提条件，本文在分析了现有研究的基础上，提出了基于故障传播感知的故障定位方法，有效降低了由于故障的传播性对故障定位准确性造成的影响，并给出了相关的评价指标；在此基础上通过实验将本文方法与前人的研究工作进行了比较，得出如下两点结论：(1)通过对边故障传播趋势的分析来修正节点可疑度是可行的，能有效提高故障定位的定准率等相关指标；(2)在计算节点可疑度前预先对可疑空间进行压缩，可以有效减少时间开销，并随着软件规模的不断扩大效果尤为明显，这为故障定位的快速性要求提供了保证。

本文的研究是对传统的基于覆盖的故障定位技术的延伸，在这方面除了需要考虑故障的传播对故障定位准确性造成的影响之外，还有其他很多因素如代码的缺失、多故障之间的交叉影响等需要考虑和进一步研究；另一方面如何根据具体需求和故障特点建立层次化多粒度的自适应故障定位模型也值得进一步深入研究。

图4 有效值比较

图5 时间开销比较

[1] Jones J A and Harrold M J. Empirical evaluation of the tarantula automatic fault-localization technique[C]. Proc. of the 20th IEEE/ACM Conference on Automated Software Engineering, Long Beach, California, USA, December 2005:273-282.

[2] Wong W E, Debroy V, and Choi B. A family of code coverage-based heuristics for effective fault localization [J].Journal of Systems and Software, 2010, 83(2): 188-208.

[3] Liblit B, Naik M, Zheng A X,et al.. Scalable statistical bug isolation[C]. Proc. of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation,Chicago, Illinois, USA, June 2005: 15-26.

[4] Liu Chao, Fei Long, Yan Xi-feng,et al.. Statistical debugging:a hypothesis testing-based approach [J].IEEE Transactions on Software Engineering, 2006, 32(10): 831-848.

[5] Zhang Xiang-yu, Gupta N, and Gupta R. Locating faults through automated predicate switching[C]. Proc. of the 28th International Conference on Software Engineering, Shanghai,China, May 2006: 272-281.

[6] Renieris E. A research framework for software-fault localization tools[D]. [Ph.D. dissertation], Brown University,2005.

[7] Santelices R, Jones J A, Yu Y,et al.. Lightweight faultlocalization using multiple coverage types[C]. Proceedings of the 31st International Conference on Software Engineering,Vancouver, Canada, May 2009: 56-66.

[8] Zhang Zhen-yu, Chan W K, Tse T H,et al.. Capturing propagation of infected program states[C]. Proceedings of the the 7th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on The Foundations of Software Engineering (ESEC/FSE'09),Amsterdam, The Netherlands, August 2009: 43-52.

[9] Zhao Lei, Wang Li-na, Xiong Zuo-ting,et al.. Executionaware fault localization based on the control flow analysis[C].Proceedings of the First International Conference on Information Computing and Applications, Tangshan, China,October 2011: 158-165.

[10] Yu Kai, Ling Meng-xiang, Gao Qin,et al.. Locating faults using multiple spectra-specific models[C]. The 26th Symposium on Applied Computing, Taichung, March 2011:1404-1410.

[11] 柳永坡, 吴际, 金茂忠, 等. 基于贝叶斯统计推理的故障定位实验研究[J]. 计算机研究与发展, 2010, 47(4): 707-715.Liu Yong-po, Wu Ji, Jin Mao-zhong,et al.. Experimentation study of BBN-based fault localization [J].Journal of Computer Research and Development, 2010, 47(4): 707-715.