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

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

关键词： 关联规则； 多故障定位； 提高定位效率； 聚类方法

0 引 言

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等方法，效果更好。

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

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

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

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

（2） 该语句基本块本身不是故障语句，但是该基本块的执行会导致故障语句的执行，进而发生故障。这表明高可疑语句块或者是故障或者会导致故障，因此考虑通过关联规则挖掘高可疑代码与软件故障的关系，提高故障定位的效率。 测试用例的执行路径能够反映出故障代码与高可疑代码之间的关联，即高可疑代码的执行导致故障语句的执行，进而出现故障。故障语句与高可疑语句表现出了在执行路径上覆盖信息的一致性，然而执行轨迹的路径表示十分复杂和耗时[10]，因此采用相对轻量级的覆盖向量来近似表示路径的覆盖信息。

2.1 路径覆盖向量的表示

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

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

2.2 求解频繁集

求解频繁集的算法如下：

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

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

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

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

图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所示。

式中：[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 结 语

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

参考文献

[2] JONES J A. HARROLD M J. Empirical evaluation of the Tarantula 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 hypothesis testing?based approach [J]. IEEE Transactions on Software Engineering， 2006， 32（10）： 831?848.

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

[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， Verification， and Validation. Lillehammer， Norway， 2008： 42?51.

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