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

《基于关联规则的软件多故障定位技术》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于关联规则的软件多故障定位技术张泽林，赵洋（南京理工大学，江苏南京210094）摘要：为了提高软件故障的定位效率，提出一种基于关联规则的软件多故障定位技术。通过使用聚类方法把失败的测试用例分成针对特定错误的聚类，使用基于交叉表的软件故障定位方法发现软件中的故障，在定位过程中使用关联规则挖掘高可疑代码与软件故障的关系，提高故障定位的效率，最后对Siemens用例集和Tarantula方法进行对比。实验表明基于关联规则的软件多故障定位技术在软件多故障定位方面效率优于Tarantula方法。.jyqke的方式实现多故障的定位，但是这种方式弊端明显：时间效率低，同时需要重复测试。Jones和

2、Harrold提出了一种并行调试技术[7]，通过对可能导致同一个故障的测试用例进行分类，然后结合成功执行的测试用例构造用以测试每个故障的测试用例子集，来同时定位不同的软件故障。但现有的基于覆盖率的错误定位（CoverageBasedFaultLocalization，CBFL）方法只是统计代码语句或代码基本块的覆盖率，并没有考虑程序执行的数据依赖和控制依赖，因此会出现定位不准确的情况。结合以上两点，本文将在并行的基础上使用关联规则挖掘软件故障。1相关工作许多该领域的学者提出了不同的软件故障定位技术。这些技术大多通过收集语句或者谓词等程序实体的覆盖信息，然后对收集到的信息利用相应的怀疑度

3、公式计算每条语句的怀疑度，据此找出软件中的故障。本文也使用这种方式，同时，结合关联规则的思想来提高软件的多故障定位效率。1.1基于交叉表的故障定位技术(fi)={B,T,PATH}。其中：B表示函数fi的基本块集合；T表示测试用例集的所有测试用例集合，PATH={path0,path1,-,pathm}表示针对每个测试用例的覆盖向量集合。根据程序执行的结果可以将执行轨迹分为成功执行和失败执行，即EXEMp和EXEMf。2.2求解频繁集根据故障语句与高可疑代码之间表现出的覆盖一致性，可以求解故障语句的“频繁集”来表现这种关联[11-12]，软件故障或者存在于高可疑代码中，或者存在于高可疑

4、代码的频繁集中，因此通过频繁集来提高软件故障定位的效率。只需求出与高可疑代码保持覆盖一致的分量对应的基本块，即可通过频繁集提高故障定位的效率。求解频繁集的算法如下：输入：OBS,EXEMf输出：FG(频繁集集合)符号表示：fg(bk):以bk为目标代码的频繁集，k表示bk在OBS中的索引u∧v:向量与操作I:单位向量，维度为基本块个数初始化：FG←NULL1.foreachbk∈OBS2.fg(bk)←I3.foreachpathi∈PATH4.ifpathi(bk)>0then5.fg(bk)←fg(bk)∧pathi6.endif7.endfor8.FG←FG-fg(bk)9

5、.endfor算法中：bk代表目标代码；fg(bk)表示与bk保持频繁一致性的分量集，即求解出的以bk为目标的频繁集。算法过程为：遍历bk不等于0的分量进行与操作，即得到所有的bk的频繁集。通过计算每一条语句块的可疑度，按照可疑度降序检查发现错误，若语句块中不存在错误则检查语句块的频繁集（依据可疑度排序）查找错误，这种方式可提高定位效率。3基于交叉表的软件多故障定位技术下面对基于交叉表的软件多故障定位技术进行具体介绍。图1为程序实例展示，该程序用于求取输入的是三参数中间值。图1的程序中包含两个错误，分别是语句行6和语句行9，使用在测试用例集中10组参数组合分别为T1~T10。图中“√”

6、代表了每条测试用例的语句覆盖信息；在最后一行给出了每个测试用例的执行结果：P代表成功，F代表失败。由图1可知，导致失败的测试用例往往具有相同或者相似的语句覆盖信息。因此可以通过聚类方法将测试用例进行分类，将错误测试用例中语句覆盖路径相同或者相似的路径分为一类，这些被分为不同类的失败测试用例子集就是专注于不同错误的测试用例集。在mid函数中，测试用例7~10失败了。而且，测试用例7，8有相同的覆盖信息，这意味着测试用例7，8可能会导致同样的软件故障。同时，测试用例9，10也具有相同的覆盖信息，同理，它们也可能导致同样的软件故障。通过上述分类原理和观察到的现象，下面把失败的测试用例分为两组

7、针对不同错误的失败测试用例子集。然后通过使用Jones和Harrold的并行调试的方法，将失败的测试用例子集分别与成功测试用例结合，形成两组不同的测试用例子集。两组测试用例子集如图2和图3所示。叉表，语句交叉表模板如图4所示。图4所示交叉表是一个表示测试用例执行情况和测试用例是否被覆盖的二维表。表中各个变量的含义分别是：id函数是用作求取输入的3个数的中间值的函数，因此中间的参数最有可能导致软件故障。所以中间的参数作为分类条件，在mid函数中使