基于聚类分析的软件多故障定位技术*

李 雷,陈朝晖,董晓刚,李 轶

0 引 言

随着计算机技术不断提高和发展，软件的高可靠性、高安全性的要求越来越高，尤其是在航空航天嵌入式软件中，保证软件能够正常稳定地按照预期目标运行尤为重要，当软件中出现故障时，需要短时间内找到故障的位置，因此对软件故障定位技术的研究具有重要的意义.本文在近几年提出的一些软件故障定位技术调研基础上，提出了一种结合聚类分析算法的故障定位技术来解决软件多故障定位的问题，并在Siemens测试集的数据基础上，和现有的一些方法进行对比测试，验证该算法的有效性.

1 研究背景及相关工作

1.1 故障定位技术概述

关于软件中的故障通常有以下这几种常见的定义.首先是根据IEEE标准，故障可以定义为隐藏在程序中不正确的指令、过程或数据定义[1]；也可以把故障看作是软件运行中出现的内部状态，是一种动态行为[2].软件故障定位就是在软件运行结果与预期结果不符时，如何找到导致这一结果的故障位置或原因的过程.在进行故障定位时，将程序语句或者程序的分支、函数、方法等构成程序最基本组成的元素称为程序实体.

由于在定位过程中，无法提前获知真正存在故障的语句，因此理论上每一个程序实体都可能包含故障，因此可以把故障定位转化为计算每一个程序实体出错的概率，这样就可以得到一个程序实体的故障可疑度列表.只需根据列表中的可疑度值大小对程序实体进行检查即可.

1.2 单故障定位技术

根据定位时是否运行待测程序，可以将软件故障定位技术分成两类：

(1) 基于静态分析的故障定位技术：不运行待测程序，利用程序语句之间的依赖关系以及类型约束等信息来分析程序中的故障位置.比较有代表性的有以下几种方法：Weiser[3]提出利用切片程序调试技术进行软件故障定位的方法.主要的思路如下：将待测程序进行切片操作，对含有故障部分的切片不断缩小范围，直到找到真正的故障位置；Podgurskil[4]等人提出一种使用静态分析程序依赖关系进行故障定位的方法.通过分析源代码来构造程序依赖图，并利用依赖图来进行软件的测试、调试以及维护；King[5]在程序调试过程中提出符号执行方法，并且证明了该方法能够适用于顺序程序的调试.随着软件规模的不断增大，代码量以及程序复杂度越发庞大，因此单纯依靠分析程序代码和依赖关系来实现故障定位的方法变得愈发困难，因此现阶段的定位基本不使用静态分析的方法来完成故障定位.

(2) 基于测试的故障定位技术：结合测试用例运行待定位的程序，对程序执行过程中的信息进行分析，利用程序动态执行信息进行定位.同时，根据对比方法的不同，又可以将故障定位方法划分为基于距离向量度量的方法和基于特征统计的方法.见表1.

表1 基于测试的故障定位技术Tab.1 Test-based fault location technology

1.3 多故障定位技术

在实际应用中，软件中存在的故障往往不止一处，传统的用于单故障定位技术的方法在解决多故障问题时的效率明显降低，因此研究人员提出了一些改进方法来研究多故障定位技术.

1) 李博[10]在虞凯提出的多程序谱的基础上进行改进，使之可以处理多故障程序定位问题，主要的改进思路在于得到数据依赖和控制依赖谱后，进行计算时对得到的可疑度不是简单的线性操作，而是先进行预处理后在求出总的可疑度值进行排序定位.2) 于全江在多故障环境下对程序谱故障定位技术的各个风险评估函数的定位效果进行研究[11]，并提出对部分参数进行修改权重的方法来探究最优参数权重，从而实现多故障定位中良好的定位效果.3) 相比于一般的基于程序谱的方法，文万志在其论文中提出一种基于条件切片谱的方法来进行多故障程序定位的研究[12]，和传统方法相比，其定位精度有所提高，定位效果也很显著.4) 除了利用程序谱的方法之外，一些研究人员提出可以结合数据挖掘的思想来解决多故障定位问题，并且取得了一定的进展.张泽林在其论文[13]中提出利用聚类分析的思想来处理测试用例，将不同故障进行隔离，然后分别进行定位.

2 基于聚类分析的方法

本文提出了一种在程序谱的基础上结合聚类分析技术来完成软件多故障定位操作，并通过实验验证了该算法的有效性.

2.1 算法的提出及思路

在目前故障定位研究领域中，基于程序谱的故障定位技术在单故障定位方面表现出很好的效果，但是在多故障的环境下，故障的定位能力正确率不足.例如，在Tarantula方法中，假设程序中存在两处故障时，根据测试用例得到的语句可疑度排名中，第一个故障的可疑度最高，排在第一位，但是第二个故障的可疑度可能不是排在第二位，在定位到该故障之前可能还需要检查程序中其他正确语句，这就增加了定位时间开销，导致定位效率和预期结果存在差异.造成这种情况的原因主要有2个方面，首先基于程序谱的方法在对程序语句执行信息进行统计时，会存在语句“叠加”的现象，以图1中的示例程序流程进行阐述说明.

图1 示例程序流程图Fig.1 Sample program flow

假定在程序中存在一个分支语句流程，在两个分支中分别存在两处故障，并且两条路径最终都会经过语句4，则在统计语句覆盖执行信息时，语句4被失败测试用例执行次数会比这两条故障语句的执行次数多，由于基于程序谱的定位方法的思想是被失败执行用例覆盖次数越多，那么该条语句出错的可能性越大，因此在计算语句可疑度时，语句4的可疑度值会比真正故障语句可疑度大，在根据可疑度值进行排序的定位报告中，语句4的位置会在两条故障语句之前，导致定位效率降低.

另外在一般基于程序谱的定位方法中，测试用例的分布不均也会导致其在多故障环境下定位效率不高.例如，在某程序中存在2处故障，其中由一个故障激发的失败测试用例数目为m，由另一个错误激发的失败测试用例数目为n，其中m>n，则对程序语句执行信息统计时，某些只被第一个故障对应的失败用例覆盖的语句可疑度值会比第二处真正故障语句的结果大，会使这些语句在定位报告中排序的位置在真正故障语句的前面，也导致定位效率降低.

由于上述问题的存在，本文提出利用聚类分析的思想，将对应不同故障的这些失败测试用例进行区分，保证每条故障语句都只对应被其经过的失败测试用例，这样在统计计算时，可以排除不同故障引起的测试用例间的干扰与影响，从而提高定位效率.算法的框架思路如下图2所示.

图2 算法框架流程图Fig.2 Algorithm framework process

和已有的基于程序谱的定位技术相比，本文提出的方法在得到包含程序语句执行信息的程序谱后，没有直接进行统计参数，计算每条语句的可疑度值的工作，而是按照测试用例的执行结果将程序谱分为只含有失败用例和只含有成功用例的子程序谱，并对失败用例程序谱中的覆盖执行向量进行聚类，最后通过得到的针对不同故障的子程序谱，计算语句的可疑度值，排序并进行定位操作.

2.2 数据预处理

基于程序谱的故障定位技术需要利用程序语句的覆盖执行信息，因此在运行源程序后，需要对程序语句在所有测试用例中的执行情况进行收集.通过使用GCOV工具在进行编译、收集信息以及生成报告这三个步骤后，会得到一个以gcov为后缀的文件，如下图3所示，其中包含了程序中所有语句的执行信息.

图3 gcov文件示意图Fig.3 The gcov file

为了能够对程序执行信息做进一步处理，引入程序谱的概念，程序谱的概念最早是由Reps[14]为了解决千年虫的问题而提出的，随后，Harrold对程序谱做了详细的定义和分类[15]，程序谱通常是用来刻画程序运行时行为信息，表征了一个程序执行轨迹.程序谱的本质是一个二维数组，包含了程序语句在所有测试用例下的执行情况.用1代表该语句在测试用例中被覆盖执行，0代表该条语句在测试用例中未被覆盖执行.同时为了满足后续聚类算法的实现，需要对得到的初始程序谱进行改造，分别得到只包含失败执行用例和只包含成功执行用例的程序谱，其中前者是研究重点，也是聚类算法的数据基础，通过对失败测试用例对应的覆盖执行向量进行聚类操作，得到针对不同故障的失败用例子集，然后结合成功执行用例进行语句可疑度值的统计.

2.3 聚类算法的实现

聚类分析作为数据挖掘中经常提到的一种思想，其应用十分广泛，尤其是在处理软件多故障定位这一领域，本文利用聚类分析来解决故障定位问题.通过利用聚类分析思想将失败执行测试用例进行区分，从而可以构成由不同故障引起的测试用例子集，并根据这些子集进行多故障定位操作.

常用的聚类算法包括划分法、层次法、基于密度的方法以及基于模型的方法.本文采用的是层次法中的凝聚法来实现聚类操作，主要原因是首先在进行定位之前并不知道程序中包含故障的数目，因此也就无法提前预知可以将测试用例分为几类，另外基于层次法的方法形式简单，易于实现，而且得到的聚类结果也比较清晰.

本文提出的聚类算法的实现过程如下图4所示.

图4 聚类算法实现流程Fig.4 Clustering algorithm implementation process

1) 判断当前选取的覆盖向量是否已完成聚类操作，若还未执行聚类则进入下一步骤，否则跳过该向量，选择下一条执行向量进行判断.

2) 判断待合并的执行向量是否在之前聚类操作中被其他类簇合并，若存在则执行下一步，否则寻找其他向量，判断是否可以进行聚类过程.

3) 计算当前选取的执行向量和待合并的向量之间的相似系数，并和给定的阈值进行比较，若满足当前阈值条件，则将两条向量进行聚类，并更新合并后的类簇中质心，反之则寻找下一条执行向量进行上述操作.

2.4 多故障定位技术的实现

在得到针对不同故障的测试用例子集后，就可以对每条语句的执行信息进行统计计算，最终找到程序中故障的位置.首先将聚类后的失败用例程序谱子集和在数据预处理阶段拆分得到的成功用例程序谱结合，构造针对不同故障的程序谱.然后利用Naish统计公式计算每条语句的可疑度值，最后根据得到的结果进行排序，并按照排序表查找源程序中对应语句，完成故障定位操作.该部分功能实现的伪代码如下所示：

输入：s_spectra[i,j],spectra[i,j]

输出：suspicion[n]

for row:0→final_spectra.GetLength(0)

final_spectra[row, 0]← spectra[row, 0];

for j:0→s_spectra.GetLength(1)

for row:0→final_spectra.GetLength(0)

final_spectra[row, j]←s_spectra[row, j];

k←s_spectra.GetLength(1);

foreacheach file_line∈file_lines

for row:0→final_spectra.GetLength(0)

final_spectra[row, k]←spectra[row, int.Parse(file_line)];

k++;

for row:1→final_spectra.GetLength(0)

for j:1→ s_spectra.GetLength(1)

if (final_spectra[row, j] == 1)then

aep++;

else

anp++;

for j:s_spectra.GetLength(1)→ final_spectra.GetLength(1); j++)

if (final_spectra[row, j]==1) then

aef++;

suspicion[row]=aef-aep/(aep+anp+1);

其中s_spectra数组存储的是成功执行用例程序谱，另一个输入spectra数组存储的是初始化程序谱.该部分算法首先是构造针对不同故障的测试用例子集，其中包括聚类后的失败用例子集和成功用例程序谱.然后对得到的这些子谱中的语句执行信息进行统计，采用的是Naish统计公式，其中aef代表的是某条语句被失败测试用例覆盖执行的统计数目，aep则是对应着被成功测试用例覆盖执行的统计数目，anp的含义是没有被成功测试用例覆盖执行的统计数目.通过对每条语句的这三个统计量进行统计，就可以计算得到该语句的可疑度值.最后根据得到的结果按大小进行排序并回到源程序中查找对应语句，实现软件多故障定位的目的.

3 程序用例测试集

在当前故障定位技术研究领域中，应用广泛的程序集是Siemens程序集，该程序集由7个程序组成，程序结构多样性，通用性强，每个程序的代码行数不超过600行，主要是基于C语言程序定位，后续加入针对Java、c++等常用语言的程序定位.该程序集是由西门子公司开发的，全部程序集可以从相应的网站中下载[16].本文通过选择其中部分程序集进行定位研究，表1是选取的部分程序集的概要信息，其中包含程序名称及版本号、故障数目、代码行数、以及测试用例数[17].

表1 Siemens测试套件概要Tab.1 Siemens test suite profile

4 实验结果以及测试评价

本文选取tcas测试集和print_tokens2测试集作为实验对象，一共50个故障程序，其中tcas程序包括41个版本的程序，print_tokens2程序中包括9个故障程序，这些程序中基本都是单故障程序，因此选择向每个程序中分别手动注入2-3个故障，构造多故障程序.为了衡量实验的效果，一种可行的评价标准是有必要的.本文采用Jones[18]提出的一种衡量标准.公式如下所示：

(1)

(2)

在该公式中，Expense代表了找到某处故障需要消耗的代价，其中rank of fault指的是当前找到的故障语句在故障报告中的排名，可疑度值越大该语句的排名越靠前，size of program是程序中全部语句的数目，两者的比值表示找到该处故障时，已检查的语句占程序语句的比值，Expense的结果越大，说明在找到该故障前需要检查的语句越多，表明定位效率越低.D表示的找到程序中所有故障时，需要消耗的代价总和.举例说明，假设程序一共有10条语句，其中某一条故障语句根据可疑度值排在第4位，即rank of fault的值为4，则找到该条语句需要消耗的代价为40%.公式1和2主要通过计算定位到所有故障时，在源程序中已经检查的程序语句数目占源程序中所有语句数目的比例之和来说明故障定位方法的效率.得到的结果越小，说明定位到所有故障之前需要检查的语句数目越少，那么表明该故障定位技术的效率越高.表2是利用基于聚类的定位算法和一般的基于程序谱的定位方法在多故障环境下的定位效率研究的实验结果，其中一般程序谱方法中，我们利用的统计公式是Tarantula方法、Jaccard方法以及Ochiai方法，而基于聚类的方法中利用的统计公式则是Naish方法.

表2 实验结果数据表Tab.2 Data sheet of experimental results

从上表中可以得出如下结论：

1) 在大部分的测试程序中，基于聚类的方法在定位出所有故障时需要消耗的代价要低于其他方法，说明在定位出所有故障时，本文提出的方法需要检查的非故障语句数目最少，定位效率较高，验证了该方法的有效性.

2) 在部分测试结果中，基于聚类的方法的定位效率相对较差，通过对这些测试程序执行得到的聚类结果以及包含的故障类型进行分析发现，在V5和V12版本中，由于失败执行测试用例的数目相对偏少，导致得到的聚类分簇结果准确率降低，进而影响根据可疑度值对语句进行排序时得到的定位报告，使基于聚类的方法的定位效率要低于其他几种方法.

3) 而在V14和V15的故障版本程序中，本文提出的方法的定位效率偏低的原因可能是这两个版本中包含的故障类型对定位效率产生影响，由于这两个版本中存在的是具有“传递”性的故障，利用聚类方法直接定位到的是受故障“传染”的程序语句，而非真正的故障语句，在故障定位报告中，真正故障语句的排名可能会靠后，从而导致定位效率降低.

通过上述实验的分析验证，可以看出本文提出的结合聚类分析的基于程序谱的故障定位方法可以在一定范围内提高定位效率；另外和一般基于程序谱的定位方法每次只能定位到一处故障相比，在引入聚类分析的思想后，每次测试都可以根据聚类算法得到的针对不同故障的测试用例子集，定位到多个程序错误，缩短查找程序故障的时间，提高定位效率，降低测试人员的工作量.而且通过对其中定位效率偏低的故障版本进行分析后，对未来研究方向具有了一定的指导借鉴意义.

5 结束语

为了研究软件多故障定位问题，本文在调研近几年提出的一些软件故障定位技术的基础上，提出了基于聚类分析的软件多故障定位方法，并利用Siemens测试套件中的一些程序集进行验证评测，对实验结果进行了分析.该方法首先利用聚类算法将代表程序语句在测试用例下的执行情况的覆盖向量进行分簇，得到针对不同故障的失败用例子集，然后构造针对不同故障的程序谱，最后按照Naish统计公式计算程序语句的可疑度并降序排列得到故障定位报告.经过实验验证，本文提出的故障定位技术可以定位出部分类型的故障，并且定位效率要优于已有的一些基于程序谱的定位技术，降低了定位需要的开销，减少测试人员的工作量.当程序中包含的故障数目逐渐增多或者包含诸如语句丢失等某些特定类型故障时，本文提出的定位技术的效率会出现降低的情况，需要进一步的分析研究，这也是后续工作中重点关注的一个方向.