基于关联规则的软件多故障定位技术

张泽林，赵洋

（南京理工大学，江苏南京210094）

摘要：为了提高软件故障的定位效率，提出一种基于关联规则的软件多故障定位技术。通过使用聚类方法把失败的测试用例分成针对特定错误的聚类，使用基于交叉表的软件故障定位方法发现软件中的故障，在定位过程中使用关联规则挖掘高可疑代码与软件故障的关系，提高故障定位的效率，最后对Siemens用例集和Tarantula方法进行对比。实验表明基于关联规则的软件多故障定位技术在软件多故障定位方面效率优于Tarantula方法。

教育期刊网 http://www.jyqkw.com
关键词 ：关联规则；多故障定位；提高定位效率；聚类方法

中图分类号：TN911-34 文献标识码：A 文章编号：1004-373X（2015）12-0039-05

收稿日期：2014-12-06

基金项目：国家自然科学基金（61103002）

0 引言

随着软件产品的发展，软件规模以及软件复杂度的不断增大使得软件调试过程越发困难。软件故障定位是调试过程中成本最高同时耗时最长的一项[1]。在软件自动化调试领域，出现了许多相应的方法，Jones和Har-rold 提出了Tarantula[2]方法，该方法通过对比程序实体在失败测试用例和成功测试用例之间的差别，计算程序实体的怀疑度实现故障定位。C.Liu提出了SOBER[3]方法，该方法使用谓词在测试用例中取值为真对程序故障出现的影响实现故障定位。其他还有一些定位方法[4-6]比如CBI、NNQ、SBI等。这些方法大多使用程序实体的覆盖信息来计算每一个程序实体的可疑度，然后通过可疑度排名列表去发现软件故障。这些方法虽然在单故障的情况下取得了很好的效果，但是在多故障的情况下，效果都不是很理想。他们大多都采用one-bug-at-a-time 的方式实现多故障的定位，但是这种方式弊端明显：时间效率低，同时需要重复测试。

Jones和Harrold提出了一种并行调试技术[7]，通过对可能导致同一个故障的测试用例进行分类，然后结合成功执行的测试用例构造用以测试每个故障的测试用例子集，来同时定位不同的软件故障。但现有的基于覆盖率的错误定位（Coverage Based Fault Localization，CBFL）方法只是统计代码语句或代码基本块的覆盖率，并没有考虑程序执行的数据依赖和控制依赖，因此会出现定位不准确的情况。结合以上两点，本文将在并行的基础上使用关联规则挖掘软件故障。

1 相关工作

许多该领域的学者提出了不同的软件故障定位技术。这些技术大多通过收集语句或者谓词等程序实体的覆盖信息，然后对收集到的信息利用相应的怀疑度公式计算每条语句的怀疑度，据此找出软件中的故障。本文也使用这种方式，同时，结合关联规则的思想来提高软件的多故障定位效率。

1.1 基于交叉表的故障定位技术

W.Eric提出了一种基于交叉表的技术进行软件故障定位的方法[4，8]。该方法的主要思路是：针对每个测试用例的每一条语句构造一个交叉表，通过该交叉表收集语句的覆盖信息和执行结果。然后，利用每条语句的统计信息计算该语句的怀疑度（Suspiciousness）。通过这种方式，所有的语句都可以根据计算出的怀疑度来降序排名。语句的怀疑度越高，该语句越会被优先检查，可以通过排名依次检查语句，直至发现软件的故障。

该技术通过引用一个名为Chi-square test的假设测试来检查测试用例执行结果和语句覆盖信息之间的依赖关系。Chi-square 的数据通过交叉表中的数据计算而来，同时与Chi-square 中的关键值进行对比，决定这个假设（即执行结果独立于与语句的覆盖信息）被接受还是被抛弃，然后，通过计算语句的怀疑度数值ζ 进行故障定位。ζ 的数值越大表示语句的怀疑度越高，怀疑度越高则会被优先检查。基于交叉表的软件故障定位技术通过计算语句的怀疑度来预测语句包含故障的可能性。其实验结果表明基于交叉表的软件故障定位技术相比于绝大多数的软件故障定位技术，如Tarantula、Liblit05、SOBER等方法，效果更好。

1.2 并行调试

通常状况下，一个软件出现失效状况下，软件中会包含多个故障，同时软件调试的人员也会不止一个，因此可以通过并行的方式实现软件故障的定位工作，相比于one-bug-at-a-time的方式，并行故障定位会更加高效，通过构造并行工作流，不同的工作人员可以专注于不同的软件故障。要实现并行的软件故障定位，最重要的问题是如何对任务进行划分和分派，这就需要一种可以把错误的测试用例集从新分配成多个小的与特定故障相关的错误测试用例子集的技术。Jones 和Harrold 提出了一种并行调试的技术[7]用以实现解决这个问题。这种技术会自动把失败的测试用例集分割为针对不同软件故障的测试用例子集。通过使用测试用例动态运行获取执行结果的行为模型和信息，该技术可以生成一个针对不同错误的失败测试用例子集。通过把失败测试用例子集和成功的测试用例结合，就得到了一个专注于特定单错误的测试用例集。这些单错误测试用例集的个数就是对程序中故障个数的预测。

2 关联规则在软件故障定位中的应用

在基于覆盖的软件故障定位技术中，现有技术通过收集测试用例执行的覆盖信息计算语句可疑度，进而定位软件故障。在现有的技术中，往往没有考虑语句间的数据依赖和控制依赖关系，不同语句的覆盖统计是相互独立的，这导致定位的不准确，CBFL方法经常能定位到程序失效时的执行代码，而这些失效时的执行代码多数情况下并不是错误代码[9]，文献[9]表明，基于覆盖的软件故障定位计算可疑度得出的高可疑度语句主要分一下几种情况：

（1）该语句基本块本身就是故障语句，并且该基本块出现在错误测试用例的概率高于出现在成功测试用例的概率。

（2）该语句基本块本身不是故障语句，但是该基本块的执行会导致故障语句的执行，进而发生故障。这表明高可疑语句块或者是故障或者会导致故障，因此考虑通过关联规则挖掘高可疑代码与软件故障的关系，提高故障定位的效率。

测试用例的执行路径能够反映出故障代码与高可疑代码之间的关联，即高可疑代码的执行导致故障语句的执行，进而出现故障。故障语句与高可疑语句表现出了在执行路径上覆盖信息的一致性，然而执行轨迹的路径表示十分复杂和耗时[10]，因此采用相对轻量级的覆盖向量来近似表示路径的覆盖信息。

2.1 路径覆盖向量的表示

定义1：中间不存在控制跳转的连续代码语句构成一个代码基本块，简称为基本块。

定义2：覆盖向量值指代码基本快在每次执行中的覆盖信息构成的向量pathi = (b1,b2 ,-,b n ) 。其中：pathi表示覆盖向量；bi 表示程序中代码基本块，bi =0表示该代码基本块没有被覆盖，bi =1 表示该代码基本块被覆盖。

定义3：一个函数在测试用例集下的执行轨迹符号化表示为EXEM( fi) ={B,T,PATH} 。其中：B 表示函数fi的基本块集合；T 表示测试用例集的所有测试用例集合，PATH ={path0 ,path1,-,pathm} 表示针对每个测试用例的覆盖向量集合。根据程序执行的结果可以将执行轨迹分为成功执行和失败执行，即EXEMp 和EXEMf 。

2.2 求解频繁集

根据故障语句与高可疑代码之间表现出的覆盖一致性，可以求解故障语句的“频繁集”来表现这种关联[11-12]，软件故障或者存在于高可疑代码中，或者存在于高可疑代码的频繁集中，因此通过频繁集来提高软件故障定位的效率。只需求出与高可疑代码保持覆盖一致的分量对应的基本块，即可通过频繁集提高故障定位的效率。

求解频繁集的算法如下：

输入：OBS,EXEMf

输出：FG(频繁集集合)

符号表示：

fg(bk):以bk为目标代码的频繁集，k表示bk在OBS中的索引

u ∧ v:向量与操作

I:单位向量，维度为基本块个数

初始化：FG ← NULL

1. for each bk∈ OBS

2. fg(bk) ← I

3. for each pathi∈ PATH

4. if pathi (bk) > 0 then

5. fg(bk) ← fg(bk)∧ pathi

6. end if

7. end for

8. FG ← FG - fg(bk)

9. end for

算法中：bk 代表目标代码；fg(bk ) 表示与bk 保持频繁一致性的分量集，即求解出的以bk 为目标的频繁集。算法过程为：遍历bk 不等于0的分量进行与操作，即得到所有的bk 的频繁集。通过计算每一条语句块的可疑度，按照可疑度降序检查发现错误，若语句块中不存在错误则检查语句块的频繁集（依据可疑度排序）查找错误，这种方式可提高定位效率。

3 基于交叉表的软件多故障定位技术

下面对基于交叉表的软件多故障定位技术进行具体介绍。

图1为程序实例展示，该程序用于求取输入的是三参数中间值。

图1的程序中包含两个错误，分别是语句行6和语句行9，使用在测试用例集中10 组参数组合分别为T1~T10。图中“√”代表了每条测试用例的语句覆盖信息；在最后一行给出了每个测试用例的执行结果：P 代表成功，F代表失败。

由图1可知，导致失败的测试用例往往具有相同或者相似的语句覆盖信息。因此可以通过聚类方法将测试用例进行分类，将错误测试用例中语句覆盖路径相同或者相似的路径分为一类，这些被分为不同类的失败测试用例子集就是专注于不同错误的测试用例集。在mid函数中，测试用例7~10失败了。而且，测试用例7，8有相同的覆盖信息，这意味着测试用例7，8可能会导致同样的软件故障。同时，测试用例9，10也具有相同的覆盖信息，同理，它们也可能导致同样的软件故障。通过上述分类原理和观察到的现象，下面把失败的测试用例分为两组针对不同错误的失败测试用例子集。然后通过使用Jones和Harrold的并行调试的方法，将失败的测试用例子集分别与成功测试用例结合，形成两组不同的测试用例子集。两组测试用例子集如图2和图3所示。

叉表，语句交叉表模板如图4所示。

图4 所示交叉表是一个表示测试用例执行情况和测试用例是否被覆盖的二维表。表中各个变量的含义分别是：w 代表程序中的一条语句；NCS (w) 代表覆盖w的成功的测试用例数；NUS (w) 代表没有覆盖w 的成功测试用例数；NS 代表成功的测试用例数；NCF (w) 代表覆盖了语句w 的失败测试用例数；NUF (w) 代表没有覆盖语句w 的失败测试用例数；NF 代表失败的测试用例数；NC(w) 代表覆盖了的测试w 用例总数；NU (w) 代表没有覆盖w 的测试用例数；N 代表总的测试用例数。

使用图4 提供的模板和文献[4]中提供的公式计算每条语句的怀疑度。针对图2和图3两个测试用例集分别计算怀疑度，给出怀疑度列表降序排名如表1所示。

表1 中，语句9 的怀疑度最高，会最先被检测。在表2中语句6的怀疑度最高，会最先被检测。这表明通过构造针对不同错误的测试用例子集并行的进行故障定位是可以实现的，这将有利于提高软件故障定位的效率。在此计算验证了通过并行的方式进行软件故障定位的有效性。进行并行的故障定位有一个前提就是构造针对不同错误的测试用例。通过使用二分法构造针对不同的测试用例，针对不同的待测函数，可以根据函数的输入集合和函数的功能创造出不同的二分法条件。在上面例子中，mid函数是用作求取输入的3个数的中间值的函数，因此中间的参数最有可能导致软件故障。所以中间的参数作为分类条件，在mid函数中使用“中间的参数是不是在第一个出现”作为分类的条件，如果一个失败测试用例满足这个条件则把它放在一个类别中，不满足则放在另一个类别，同样以图1的测试用例为例，发现T9和T10满足这个条件，所以把他们分为一类，T7和T8分为另一类，这样即可进行并行软件故障定位。

同时，给出一个终止条件，用于判断分类是否完成，即针对不同错误的测试用例是否已经被分配到了各自相应的类别下。聚类的相似性系数可以提供判断不同对象之间相似程度的度量，因此可以使用相似系数来判断每个类别中的对象是否足够相似，不同类别间的对象是否足够相异来判断分类是否完成。相关系数公式如下：

式中：Xi 为第i 条语句在失败测试用例X 中的覆盖情况，Xi 为1代表覆盖，0代表未覆盖；Xˉ 表示失败测试用例Xi 的覆盖比例；相应的Y 的含义和X 相同。利用图1 中的例子可以将失败的测试用例集分类。给定一个相关性系数的值，比如0.8，当两个失败测试用例的关联系数小于0.8时说明它们关联性不大，即它们针对不同的错误。计算r78 =1，这表明T7和T8关联性非常大，针对相同的错误，对T9 和T10 计算结果也是1，说明它们应该分为一组。通过循环计算每两个测试用例之间的相关系数，直到类别内任意两个测试用例的相关系数大于0.8时，就说明分类完成。本文给出的上述方法虽然能够对针对不同错误的测试用例进行分类，但需要对每两个错误测试用例进行计算，所以这个过程相当耗时，开销也是很大。

4 实验及结果分析

下面使用本文给出的基于关联规则的软件多故障定位技术和Tarantula方法进行对比来验证本文方法的定位效果。在此使用Siemens程序集来进行试验的对比工作。程序集中tacas程序包含的故障版本数最多，同时可执行的语句数最少，这意味着tacas程序有可能包含多故障，因此选用该程序验证本文的方法。对文献[4]中的EXAM 度量进行扩展，将针对每个故障的EXAM相加，形成EXAMtotal 作为度量的标准。

基于关联规则的软件多故障定位方法与Tarantula方法的对比如图5所示。

图5 分别给出了在不同的故障版本比例下两种方法的EXAMtotal 得分。其中“1”代表20%的故障，“2”代表40%的故障，“3”代表60%的故障，“4”代表80%的故障。可以看到在故障比例较低的环境下，本文的方法效率明显优于Tarantula方法。

5 结语

本文提出了基于关联规则的软件多故障定位方法，并且与Tarantula方法进行了对比，结果表明本文的方法效率较高。不过本文提出的方法也存在一些不足，并没有考虑把测试用例划分为针对不同故障的测试用例的效率，同时也没有考虑失败测试用例分类的效果进行验证。在Siemens测试集上通过实验验证了基于关联规则的软件多故障定位的效率，结果证明本文的方法能有效地发现软件的故障。

作者简介：张泽林（1990—），男，山东临沂人，硕士研究生。研究方向为软件测试技术。

赵洋（1978—），男。研究方向为计算机软件与理论、可信软件。

教育期刊网 http://www.jyqkw.com
参考文献

[1] JONES J A. Semi-automatic fault localization [D]. USA：Geor-gia Institute of Technology，2008.

[2] JONES J A. HARROLD M J. Empirical evaluation of the Ta-rantula automatic fault-localization technique [C]// Proceedings of the 20th IEEE/ACM international Conference on Automated Software Engineering. Long Beach，CA，USA：IEEE，2005：273-282.

[3] LIU C，FEI L，YAN X，et al. Statistical debugging：A hypothe-sis testing-based approach [J]. IEEE Transactions on Software Engineering，2006，32（10）：831-848.

[4] RENIERES M， REISS S P. Fault localization with nearest neighbor queries [C]// Proceedings of the 18th IEEE/ACM Inter-national Conference on Automated Software Engineering. Mon-treal，Canada：IEEE，2003：30-39.

[5] LIBLIT B，NAIK M，ZHENG A X. Scalable statistical bug iso-lation [C]// Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation. 2005：15-16.

[6] HAO D，ZHANG L，PAN Y，et al. On similarity - awareness in testing-based fault localization [J]. Automated Software Engineering，2008，15（2）：207-249.

[7] JONES J A，BOWRING J F，HARROLD M J. Debugging in Parallel [D]. London， UK： Georgia Institute of Technology，2007.

[8] WONG E，WEI T，QI Y，et al. Crosstab-based statistical method for effective fault localization [C]// Proceedings of the 2008 International Conference on Software Testing，Verifica-tion，and Validation. Lillehammer，Norway，2008：42-51.

[9] ZHANG Z，CHAN W K，TSE T H. Capturing propagation of infected program states [C]// Proceedings of the 17th Interna-tional Conference on Foundation of Software Engineering. Am-sterdam，Netherl：[s.n.]，2009：43-52.

[10] BALL T，LARUS J R. Efficient path profiling [C]// Proceedings of the International Symposium on Microarchitecture. Paris，France： [s.n.]，1996：46-57.

[11] WONG E，QI Y. Effiective program debugging based on execution slices and inter-block data dependency [J]. Jour-nal of Systems and Software，2006，79（2）：891-903.

[12] JIANG L，SU Z. Context-aware statistical debugging：From bug prediceors to faulty control flow paths [C]// Proceedings of the 22th IEEE International Conference on Automated Soft-ware Engineering. Atlanta，USA：IEEE，2007：184-193.