基于程序谱的方法级别错误定位技术

徐 迟，苏小红，王甜甜

（哈尔滨工业大学计算机科学与技术学院，哈尔滨150001）

0 引 言

目前基于程序谱的错误定位方法［1］有很多，例如 Tarantula 方 法［2］、Ochiai方 法［3］等 等， 其 中Tarantula方法也经常用来作为实验的对比方法。然而，这类方法的可疑度计算公式中的参数，其实并不适合用来进行方法级别的定位。本文接下来首先探讨了基于程序谱的错误定位相关问题，然后分析了Tarantula方法在方法级别定位上的不足之处，并且给出了Optimal Ranking错误定位方法。最后，通过实验分析，验证了本文的方法能够提高方法级别定位的效率。

1 错误定位相关问题

软件错误定位的目的就是为了找到待测程序中存在的bug，待测程序通常表示为P，P中的程序实体可以表示为：

其中，m表示为P中的程序实体数量，本文中，程序实体都是指待测程序中的方法。pi（1≤i≤m）表示P中的第i个方法。

待测程序P的测试用例集表示为：

其中，待测程序P的测试用例集T中的测试用例数量为n，ti（1≤i≤n）表示T中的第i个测试用例。同时，用TF表示执行失败的测试用例集合，TP表示执行成功的测试用例集合。

使用测试用例去执行待测程序得到的结果表示为：

其中，n表示测试用例的个数，ri（1≤i≤n）表示第i个测试用例的执行结果，ri的取值有2种可能，1或者0。如果ri＝0，就表示第i个测试用例的执行结果为成功；如果ri＝1，就表示第i个测试用例的执行结果为失败。

用矩阵M来表示每个测试用例的覆盖信息，其数学表述如下：

其中，M为一个m行n列的矩阵，Mij表示测试用例tj执行程序实体pi的情况。如果Mij＝1，就表示测试用例tj执行了程序实体pi；如果Mij＝0，就表示测试用例tj没有执行到程序实体pi。

覆盖信息矩阵M和结果向量R共同组成了记录程序谱信息的0-1矩阵，0-1矩阵将作为本文研究的错误定位方法的输入。本文研究中选取的示例程序如图1所示。

图1 示例程序Fig.1 Sample program

研究中针对图1的示例程序，给出了6组测试用例进行测试得到的0-1矩阵，其最终直观展示可见表1。

表1 示例程序的0-1矩阵Tab.1 0-1 matrix of sample program

0-1矩阵中的每一列表示测试用例ti是否调用了程序中的方法，最后一行表示测试用例ti的执行结果。

2 Optimal Ranking错误定位方法

2.1 方法设计流程

Optimal Ranking方法的整体设计流程如图2所示。首先基于待测程序的抽象语法树，进行方法级别的程序插桩。然后使用测试用例去执行插桩后的程序得到方法的调用序列。接下来根据方法的调用序列，统计方法的调用信息，使用Optimal Ranking的可疑度数学公式来计算每个方法的可疑度。最后对每个方法根据可疑度的大小进行降序排列，得到方法可疑度的排序列表，用于对此后定位结果的研究与分析。

图2 方法的整体流程图Fig.2 The overall flow chart of the method

2.2 方法级别定位和语句级别定位的区别

方法级别定位和语句级别定位主要的不同之处，就在于程序的执行路径和其相对应的执行结果上。下面将以图1中的示例程序来进行阐释说明。

图1（a）所示的是一段含有bug语句的代码，bug语句所在的方法为f3。 图1（b）中，给出了含有bug语句的方法f3的具体功能。可以看到，f3方法的第5行代码出现了错误，程序的本意是想输出c的值，但是却误写成了输出-c的值。

如果采用的是语句级别的错误定位方法，那么给定测试用例t的前提下，该研发代码片段只有执行到了f3的第5行语句的时候，测试用例t的执行结果才可能是失败（不考虑偶然正确性测试用例的前提下）。

而对于方法级别的错误定位来说，研究中插桩的粒度是方法级别，因此程序的执行路径不会考虑到方法中具体的某一条语句是否执行。那么，当使用测试用例t执行这段代码时，如果没有执行到f3中的第5行错误语句，那么测试用例t的执行结果就是成功的。这样，根据基于覆盖的错误定位方法的理论，被成功的测试用例执行到的程序体应该更少的怀疑，同时想定位到的包含bug语句的f3方法的怀疑度就会降低。而研究中设定的理想情况是，只要执行到了包含bug语句的方法（f3），那么测试用例的执行结果应该就是失败的。

例如，图1（a）中的程序输入测试用例t＝｛2，1，-1｝。显然这个测试用例的执行结果是成功的。对于语句级别的定位来说，测试用例t并没有执行f3中第5行的错误语句；而对于方法级别的定位来说，测试用例t却调用了f3。这样，因为程序执行了f3，且得到了正确的输出结果，那么f3的怀疑度明显就会降低。

2.3 可疑度计算公式

根据2.2节所述，在方法级别的错误定位上，测试用例虽然调用了包含错误语句的方法，但实际上却没有执行到具体的错误语句，所以就会导致研究拟设的执行结果是失败的测试用例，而实际的执行结果却是成功的。这样必定会影响错误定位的精度。

此时，研究是否可以换个角度，考虑那些没有被失败测试用例Tf执行到的方法。因为这些方法没有被失败测试用例Tf执行到，就意味着，导致测试用例执行失败的错误语句，一定不会在这些方法中。因此，可以给这些方法赋一个比较低的可疑度值。

基于上文分析，研究给出了针对方法级别错误定位的Optimal Ranking方法（简称O方法）。O方法的可疑度的计算公式为：

其中，a表示待测程序中的某个方法。方法a的第一个下角标表示a是否被测试用例执行，n表示没被执行，e表示被执行。方法a的第二个下角标表示测试用例的执行是否成功，p表示成功，f表示失败。因此anf就表示没有调用到方法a的失败测试用例个数，anp表示没有执行到方法a的成功测试用例个数。

从公式（5）中可以看到，O方法的可疑度计算公式相比于其它的可疑度计算方法，使用了anf和anp这2个在其它方法中并未居于重要位置的变量。如果所有没执行到方法a的测试用例中有失败的测试用例，即anf＞0，就可给这些方法的可疑度赋值为-1。此外，如果2个方法的anf＝0，则这两者一定有相同的aef，因为anf+aef是所有失败测试用例的总数。同理，anp+aep是所有成功测试用例的总数。分析至此可以推知，对于包含错误语句的方法，只有小部分执行到此方法的测试用例是成功的，即aep的值很小，因此anp的值就会相对较大。所以对于那些anf值不为0的方法，用anp来表示其对应的可疑度是非常合理的。

2.4 实例分析

研究中设计选取的示例程序使用Tarantula方法和O方法的方法级别错误定位结果可见表2。可以看到，使用Tarantula方法计算方法的可疑度，包含错误语句的方法f3的可疑值并没有排在第一位；而是用O方法计算方法的可疑度，f3方法的可疑度值则是最大的。 显然，对于示例程序，O方法的定位效果要优于Tarantula方法的定位效果。接下来将详尽分析为何会得到这样的结果。

首先，研究中将给出Tarantula方法的可疑度计算公式的数学表述如下：

其中，各符号表示的含义和公式（5）中各符号的含义相同。

表2 示例程序的方法级别定位结果对比Tab.2 Comparison of function-level location results for sample program

仔细观察表2中的数据可以发现，t3、t4、t6这3组测试用例虽然调用了方法f3，但是因为没有执行f3中的错误语句，因此，这3组测试用例得到的执行结果都是正确的，这样就会导致aep的值变大，Tarantula方法计算的可疑度值就会变小。而理想情况下，研究希望t3、t4、t6这3组测试用例的执行结果都是失败的，这样aef的值就会变大，Tarantula方法计算的可疑度值也会变大。此消彼长，就会导致Tarantula方法计算的f3方法的可疑值变小。

如果使用O方法计算可疑度，分析得知f2、f4、f5这3个方法的anf值都是大于零的，因此根据公式（5），就将被赋予最小的可疑度值。而f3方法的anf值是等于零的，因此随即会被赋予更大的可疑度值。

3 实验分析

为了进一步验证在方法级别的错误定位上O方法的定位效果，本文使用了Siemens测试集［4］进行实验，并且将Tarantula方法作为本文实验的对比方法。实验的评价指标选择的是成功定位百分比（PSD）［5］，表示通过检查待测程序中特定百分比的方法，成功检查到包含错误语句方法的程序占总程序的百分比。研究推得其计算公式为：

其中，a%表示检测待测程序中a%的方法；program_total_num表示待测程序的总数；successful_findbug_num表示所有待测程序中，可疑度排名前a%的方法中可以找到包含错误语句的方法的程序数。

基于如上分析，仿真运行得到在Siemens测试集上，本文的方法和Tarantula方法在方法级别错误定位上的定位精度折线图的展示效果如图3所示。横轴表示的是检查的方法百分比，纵轴表示的是检查相应百分比的方法时，成功定位到包含错误语句方法的程序数占总程序数的百分比。研究中，测试集的方法数都小于20，因此横轴从10%开始。从图3中可以看到，检查相同百分比的方法时，O方法相比于Tarantula方法，能够定位到更多的错误。此外，O方法想要定位到全部的错误需要检查90%左右的方法，而Tarantula方法则需要检查全部的方法。

综合如上实验分析结果，可以得出如下研究结论：在方法级别的错误定位上，O方法的定位效果相比于Tarantula方法的定位效果要更好一些。

图3 方法级别错误定位结果Fig.3 Results of function-level fault location

4 结束语

针对语句级别定位效率不高的问题，本文提出了方法级别的错误定位方法。并且通过分析基于程序谱的方法级别错误定位和语句级别错误定位的不同，进一步重点说明了有些错误定位方法的可疑度计算公式不适合应用在方法级别的错误定位上。最后通过实验验证了O方法在方法级别定位上有相对更好的定位效果。

此外，除了基于程序谱的方法级别错误定位方法，某些非程序谱的错误定位方法也可以应用于方法级别的错误定位上，这些均有待未来的深入探讨与研究。