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

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

information technology, this approach introduces the execution context information by analyzing the data dependencies in all execution
paths, and introduces the test event information into the suspiciousness formula by using the information entropy theory, so as to
maximize the accuracy and efficiency of fault localization. To evaluate the effectiveness of the proposed approach, the experiments are
conducted on a set of benchmark programs and open source programs. Experimental results show that the proposed FLPI approach can
effectively improve the accuracy and efficiency of fault localization.
Key words: fault localization; context information; information entropy; path analysis

[1]
导致软件运行失效或发生故障的原因称为软件错误 ,研究软件错误产生的机制是定位软件错误的前提,
而错误产生的原因主要与其内部因素与外部因素有关.软件测试一直以来都被视为检测和分析软件错误的重
[2]
要途径 ,软件测试分为静态测试和动态测试.动态分析方法能够准确地捕获程序的执行轨迹、数据流覆盖、逻
辑控制依赖等重要信息,动态测试方法只能证明程序中存在错误而不能预测和修复错误,因此软件调试就显得
[3]
格外重要 .在软件开发和维护过程中,程序调试是一项十分容易出错的任务,其关键步骤就是错误定位和缺陷
修复 [46] .
传统的错误定位技术包括程序日志记录、断言、断点和性能分析.而自动化错误定位技术主要分为基于静
态分析的方法和基于动态测试的方法.后者通过测试用例驱动待测程序,将程序执行结果与预期结果进行分析
[7]
对比完成错误定位过程 .
基于程序频谱的错误定位技术能够直观地提供程序实体的测试覆盖信息,且计算复杂度低、操作简单、适
[8]
用范围广,因此一直以来都是研究的热点.Harrold 等人 首先提出频谱在错误定位上的应用;在此基础上,Jones
[9]
等人 提出了 Tarantula 技术,并利用不同深度的颜色可视化地将语句出错的可能性呈现出来;Abreu 等人 [10,11]
受聚类分析和分子生物学领域中相似度系数的启发,分别提出了 Jaccard 方法和 Ochiai 方法.在此之后,越来越多
的基于频谱信息的错误定位技术被相继提出.多数方法仅仅利用二元覆盖信息计算语句的可疑度值,并根据可
疑度值大小顺序检查语句.这些方法在错误定位过程中对程序执行过程和轨迹进行了高度简化,忽略了变量之
间固有的语义联系和依赖关系等程序执行上下文信息,从而大大影响了定位的精度,使得程序员很难在短时间
内根据单个程序实体的可疑度来找出程序中故障的位置.
程序依赖分析表明了程序实体的执行顺序、相互调用和依赖关系,是一种理解和分析软件行为特征的重要
手段,因此基于程序依赖信息的错误定位技术更加注重程序实体的内部信息及其之间的相互关系.Baah 等人 [12]
以概率图形模型为基础,通过对具有统计依赖性信息的程序依赖图进行扩充,提出了基于概率程序依赖图即
PPDG(probabilistic program dependence graph)的错误定位模型.该模型很好地反映了程序内部行为,很大程度上
提高了定位的精度.
针对上述关于两类技术存在问题的分析,本文提出了一种基于路径分析和信息熵的错误定位方法 FLPI
(fault localization based on path analysis and information entropy).该方法在基于频谱信息技术的基础上,通过对
所有执行路径中的数据依赖关系进行分析以获取执行上下文信息,同时利用信息熵理论将测试事件信息引入
到可疑度计算公式中,最大程度地提高错误定位的精度和效率.
本文第 1 节给出本文方法的技术背景.第 2 节首先描述 FLPI 方法的框架和整体流程,然后具体介绍该方法,
最后给出一个实例分析.第 3 节使用基准程序集 Siemens Suite、Nano XML、XML-sec 及 Defect4J 对本文所提
方法开展实验验证及结果分析.第 4 节介绍相关工作.最后总结全文并讨论进一步的研究方向.

1 研究背景

1.1 基于频谱的错误定位技术
基于频谱的错误定位(SBFL)是一种典型的动态分析技术,它主要利用软件测试过程中收集到的两种信
息 [13,14] ,即测试执行结果和程序频谱进行分析来识别错误程序实体(如语句、分支、基本块、方法或谓词).SBFL
方法利用程序实体的覆盖信息计算其可疑度值,具有计算复杂度低、操作简单且适用范围广的特点,因此一直
是错误定位问题的研究热点,这也是本文研究的重点.