Page 261 - 《软件学报》2021年第7期

姜淑娟 等:基于路径分析和信息熵的错误定位方法 2179

和 26%,而相比较 SIQ,分别多了 6%、8%、5%、3%和 6%.而在 Defect4J 的 3 个开源项目上,FLPI 方法错误定位
的效果有了很大的提升,在检查可执行语句为 10%和 20%时最为明显,与所有对比方法比较分别提高了 28%和
37%、26%和 31%、23%和 29%、18%和 26%、20%和 29%、32%和 41%、12%和 13%.

4 有效性分析

本节从内部有效性、外部有效性、结构有效性等方面来分析威胁本文所提方法有效性的因素.
对 FLPI 方法内部有效性的影响主要在于两个方面.(1) 3 组对比实验在全部基准程序集上数据的准确性,
本文按照相关文献复现实验过程,保证了对比实验数据的真实性;(2) 数据依赖路径分析及信息熵计算结果对
定位精度的影响,本文借鉴了 Aho 等人 [16] 提出的数据依赖分析方法,同时严格按照信息论中信息熵的定义优化
了怀疑度计算公式.
对 FLPI 方法外部有效性的影响主要在于实验基准程序的代表性.本文选取了在错误定位研究中广泛使用
的 Siemens Suite,NanoXML 程序集,XML-sec 程序集,Defect4J 中的 3 个开源项目 JFreeChar、Joda-Time 和
Mockito 作为研究对象.实验对象既有小、中规模的程序,又有大规模的程序.实验程序中的错误既有人工植入的
错误,又有真实的错误.
对 FLPI 方法构造有效性的影响主要在于本文用来评估错误定位方法有效性的评价标准,本文采用 3 个软
件错误定位研究中常用的评价指标,即累积检查语句数、错误定位代价 Expense、检查得分 EXAM 和时间开销
分别评价 FLPI 方法和对比对象所有基准程序集上的定位效果,因此可以有效评价不同方法的错误定位效果.分
别评价某个错误定位方法在某个缺陷和所有缺陷上的错误定位效果,因此可以有效评价不同方法的错误定位
效果.

5 相关工作

目前国内外研究人员针对软件错误定位这一课题已经进行了大量的研究,提出了很多基于测试的自动化
软件错误定位技术 [6,7] ,主要包括以下几种类别:基于程序切片的技术、基于程序频谱的技术、基于机器学习与
数据挖掘的技术、基于谓词统计的技术以及基于程序状态变更的技术.本文主要重点研究基于程序频谱的错误
[7]
定位技术 .
程序频谱描述了程序动态执行的行为信息,例如程序内部条件分支的执行信息或循环路径的覆盖信息,开
发人员可以使用这些信息追踪记录程序的行为 [25,26] .Collofello 和 Coussis [27] 的早期研究表明,这种频谱可以用
于软件错误定位.当执行失败时,这些信息可以用来识别导致失败的可疑代码.代码覆盖率或可执行语句命中谱
(executable statement hit spectrum)表示在成功执行和失败执行过程中测试程序的哪些部分被覆盖.通过对比就
可以识别出哪些程序组件与错误相关,从而缩小对导致执行失败的故障组件的搜索范围.早期的研究 [28] 仅使用
失败的测试用例进行基于频谱的错误定位,后来一些学者同时研究成功和失败的测试用例并度量统计两者之
间的差异,最终获得了更好的结果.Renieris 和 Reiss [29] 提出了一种基于 ESHS 的技术,即最近邻查询技术,它将失
败的测试用例与成功测试用例中与其最相似的那个进行比较,也就是语句的执行模式越接近所有测试用例的
失败模式,那么该语句出错的可能性就越大.
丁晖等人 [18] 提出基于信息量的错误定位方法,该方法根据测试信息中不同事件的类型及其发生的概率,结
合语句的执行信息,动态地计算和调整错误定位的结果.与他们的方法不同,我们除了增加信息熵来调整可疑语
句的怀疑度计算公式外,还增加了数据流的分析,以提高错误定位的精度.
[9]
Tarantula 是一种经典的基于程序频谱的错误定位技术,该方法使用覆盖率和执行结果(成功或失败)来度
量每个语句的可疑度.在此基础上,其他研究学者也相继提出了一些方法,例如 Abreu 等人 [10,11] 受聚类分析和分
子生物学领域中相似度系数的启发,分别提出了 Jaccard 方法和 Ochiai 方法,这些方法极大地提高了错误定位的
有效性.不仅如此,目前基于相似系数的技术已经用于不同的研究,研究人员还开发了很多实用的程序插件和工
P
具,使得程序实体的可疑度计算变得更加便捷.Naish 等人 [30] 提出了两种技术 O 和 O ,其中,技术 O 是为寻找单