2021, Vol. 32
2. 中国矿业大学 计算机科学与技术学院, 江苏 徐州 221116;
3. 高安全系统的软件开发与验证技术工业和信息化部重点实验室(南京航空航天大学), 江苏 南京 211106
2. School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116, China;
3. Key Laboratory of Safety-Critical Software of Ministry of Industry and Information Technology(Nanjing University of Aeronautics and Astronautics), Nanjing 211106, China
导致软件运行失效或发生故障的原因称为软件错误[1], 研究软件错误产生的机制是定位软件错误的前提, 而错误产生的原因主要与其内部因素与外部因素有关.软件测试一直以来都被视为检测和分析软件错误的重要途径[2], 软件测试分为静态测试和动态测试.动态分析方法能够准确地捕获程序的执行轨迹、数据流覆盖、逻辑控制依赖等重要信息, 动态测试方法只能证明程序中存在错误而不能预测和修复错误, 因此软件调试就显得格外重要[3].在软件开发和维护过程中, 程序调试是一项十分容易出错的任务, 其关键步骤就是错误定位和缺陷修复[4-6].
传统的错误定位技术包括程序日志记录、断言、断点和性能分析.而自动化错误定位技术主要分为基于静态分析的方法和基于动态测试的方法.后者通过测试用例驱动待测程序, 将程序执行结果与预期结果进行分析对比完成错误定位过程[7].
基于程序频谱的错误定位技术能够直观地提供程序实体的测试覆盖信息, 且计算复杂度低、操作简单、适用范围广, 因此一直以来都是研究的热点.Harrold等人[8]首先提出频谱在错误定位上的应用; 在此基础上, 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方法利用程序实体的覆盖信息计算其可疑度值, 具有计算复杂度低、操作简单且适用范围广的特点, 因此一直是错误定位问题的研究热点, 这也是本文研究的重点.
SBFL方法一般遵循以下步骤: 执行测试用例, 通过插桩技术获取源程序在给定测试用例集下的覆盖信息以及执行结果, 并根据覆盖信息和执行结果构建测试覆盖矩阵和执行结果向量; 统计分析覆盖信息, 借助不同的错误定位公式计算程序实体的可疑度, 并根据可疑度计算结果由高到低的顺序排列程序实体.程序实体的可疑度越高, 其包含错误的可能性就越大, 开发人员依次检查程序实体开展错误定位工作.基于频谱的软件错误定位框架如图 1所示.
|
Fig. 1 Spectrum-based fault localization framework 图 1 基于频谱的软件错误定位框架 |
对于任意一个程序实体Si, 其在测试用例下的执行信息和覆盖特征可以用一个四元组表示, 即Ns=(NCF, NUF, NCS, NUS).4个元素分别代表执行失败且覆盖程序实体Si的测试用例次数、执行失败且未覆盖程序实体Si的测试用例次数、执行成功且覆盖程序实体Si的测试用例次数和执行成功且未覆盖程序实体Si的测试用例次数.一般情况下, 用NF表示所有执行失败的测试用例次数, 用NC表示所有执行成功的测试用例次数.表 1给出了几种典型的错误定位技术可疑度度量公式.
|
Table 1 The calculation formula of suspicious degree for fault localization 表 1 典型的错误定位怀疑度计算公式 |
1.2 程序依赖性分析
程序依赖分析主要分析程序实体的执行顺序、函数之间的相互调用以及依赖关系, 是一种理解和分析软件行为特征的重要手段, 在程序分析与调试、软件测试与维护等软件工程领域有着广泛的应用.目前常用的方法主要包括过程内的依赖分析(控制依赖分析和数据依赖分析等)、过程间的依赖分析(程序依赖图分析等)和程序切片等.下面给出程序依赖性分析的相关定义.
定义1. 控制流图CFG(control flow graph).程序PG的控制流图是一对(N, E)组合, 其中, N代表PG中所有语句的节点集合, E代表有向边集合, 而边(ni, nj)则表示从节点ni到节点nj的控制流, 其中, 条件分支和循环边上的标识表示取这些边时的条件.
定义2. 控制依赖: 在控制流图G中, 如果节点n2具有输出边e1和e2, 则节点n1控制依赖于n2, 当且仅当满足以下条件.
(1) G中以e1开始并以结束节点结束的每条路径都包含n1;
(2) 存在一条路径以e2开始并以结束节点结束, 而中间节点不包含n1.
定义3. 数据依赖: 在控制流图G中, 节点n1数据依赖于节点n2, 当且仅当满足以下条件.
(1) 节点n2定义了变量v;
(2) G中存在一条从n2到n1但未重新定义v的路径;
(3) 节点n1使用了变量v.
Zeller[15]提出的Defect-Infection-Failure模型指出: 开发人员在用给定的测试用例执行缺陷程序时, 软件缺陷可能会导致其余源代码部分的感染, 感染状态的传播最终会导致程序失效.程序实体间的依赖分析不仅有助于定位引起程序失效的根源, 而且还充分考虑了感染状态在程序内部的传播机制, 为理解程序失效提供了有效的上下文信息, 一定程度上可以帮助开发人员理解错误产生的原因.因此在错误定位过程中引入程序依赖性分析可以有效地提高方法的精度和准确性.
下面给出数据依赖路径分析过程中的相关定义.
定义4. 变量轨迹: 变量vx的轨迹为Trace(vx)={
执行过程中的定义与使用.
变量的定义是指其值或内部状态发生改变, 通常出现在赋值指令、输入数据指令或过程调用中, 而变量的使用是指其值或内部属性被读取, 但未发生任何改变的过程.这样一个程序的行为就可以通过一组变量跟踪来表示.
定义5. 变量依赖关系: 变量vx和vy的依赖关系为VDR(vx, vy)={(
FLPI方法以待测程序PG和测试用例集Tc作为输入, 最终得到错误定位报告.整体框架主要包括3个部分: 预处理阶段、错误定位方法和定位结果显示, 如图 2所示.
|
Fig. 2 Overall framework of our approach 图 2 本文方法的总体框架 |
① 预处理阶段: 通过静态分析对待测源程序PG构建控制流图, 同时进行程序插桩工作, 编译执行插桩后的程序并运行测试用例集, 获取程序的执行轨迹和覆盖信息.
② 利用控制流图分析得到程序所有执行路径中的不同数据依赖关系, 即以语句节点li作为数据依赖前驱和依赖后继时的不同Pl, 结合程序的执行轨迹和数据依赖路径分析结果得到Pl的覆盖信息, 根据覆盖信息矩阵计算得到Pl在执行过程中4类随机事件的信息熵.
③ 计算所有路径中不同Pl的怀疑度值, 对于涉及到语句li的所有Pl的怀疑度值进行加权平均, 最终得到程序所有语句节点的怀疑度, 生成错误定位报告定位到错误语句.
2.2 数据依赖路径分析程序变量的状态在程序运行过程中沿着不同的执行路径发生改变, 变量的不正确定义和使用会造成程序发生故障.数据依赖路径分析不仅可以得到变量状态变化信息及其传递轨迹, 而且可以获取语句之间的相互作用和依赖关系, 为错误定位分析提供更加有效的上下文信息.变量依赖关系说明了其值和内部状态发生改变的机理, 主要包括变量之间的语义联系和变量的自身依赖.
Aho等人[16]提出了利用控制依赖图和控制依赖子图进行数据依赖分析的方法.收集控制依赖图的DEF[n]、REF[n]、KILL[n]、IN[n]和OUT[n]集合, 其分别代表语句节点N中产生变量的集合、使用变量的集合、杀死变量的集合、流入语句节点的变量集合和流出语句节点的变量集合.除DEF[n]和REF[n]外, 其余集合均为一个语句节点和变量构成的二元组, 表示为⟨li, vx⟩.本文参考了文献[16]中的方法, 使用控制流图CFG获取上述集合并进行数据依赖分析.
算法1描述了对程序所有执行路径进行数据依赖分析的过程.输入控制流图以及各节点的IN、OUT、REF、DEF集, 对CFG进行遍历, 针对图中的每个节点N, 首先判断其变量的使用情况, 在使用集不为空时将使用变量x与IN集中的变量vx对比, 并建立从节点N到节点li的数据依赖边(第4行~第8行), 最后遍历控制流图, 输出节点N到其父节点的数据依赖边, 完成数据依赖分析过程(第12行~第14行).
算法1. 数据依赖分析.
输入: 控制流图CFG, 各节点的IN、OUT、REF、DEF集;
输出: 数据依赖关系.
1. for each node N in CFG do
2. if REF[n] is not null then
3. for each variable x in REF[n] do
4. for each pair ⟨li, vx⟩ in IN[n] do
5. if vx==x then
6. establish data-dependent edges from node N to li
7. end if
8. end for
9. end for
10. end if
11. end for
12. for each node N in CDS do
13. output the data dependent edges from node N to its parent
14. end for
end
在一条执行路径上, 若在语句节点li处定义了变量vx, 而在语句节点lj处引用了变量vx, 那么我们使用Pl (li, lj, vx)来表示这种数据依赖关系, 其中, li为依赖前驱, lj为依赖后继, vx为依赖变量.Pl(li, *, vx)和Pl (*, li, vx)分别代表以li为依赖前驱和后继的不同数据依赖关系.通过对语句节点li所有不同执行路径的分析可以得到其有效上下文信息, 利用数据流对变量定义使用的跟踪和变量依赖关系的描述分析程序复杂的行为, 更好地定位程序错误的位置.
2.3 测试事件信息熵与怀疑度计算SBFL方法就是针对程序的执行覆盖信息进行一系列操作, 进而确定程序语句出错的可能性[17], 从本质上讲就是利用怀疑度公式进行概率统计.程序语句在测试用例下的执行信息和覆盖特征可以用一个四元组表示, 即(NCF, NUF, NCS, NUS), 其分别代表不同的随机事件.以往的怀疑度计算仅仅考虑了不同事件发生的次数而忽略了组合事件附带的信息.信息熵是表示随机事件不确定性的数学化度量, 因此利用信息熵可以将程序语句存在错误可能性的信息量加权平均, 将两者有机结合即可将测试事件信息引入到可疑度计算中.
在错误定位研究过程中, 若存在大量执行失败的测试用例, 那么对执行成功的测试用例进行研究可以获得更多与错误相关的信息; 反之, 若仅有少数测试用例失败, 那么其更有利于错误定位.基于此, 文献[18]提出了一种基于事件信息量的方法SIQ.本文在其基础上, 利用信息熵加以改进, 进一步提高错误定位的精度.
信息熵是表示随机事件不确定性的数学化度量, 是所有随机事件信息量的期望.对于一组随机事件
| $H(x) = E[I({x_i})] = - \mathop \sum \limits_{i = 1}^n (P({x_i}) \times \log P({x_i}))H(x) = E[I({x_i})] = - \mathop \sum \limits_{i = 1}^n (P({x_i}) \times \log P({x_i}))$ | (1) |
错误定位中的测试事件主要分为4类, 即执行成功的事件P和执行失败的事件F、覆盖程序实体的测试事件C(s)和未覆盖程序实体的测试事件U(s), 它们的信息熵表示如下:
| $H(P) = E[I(P)] = - \mathop \sum \nolimits \left( {\frac{{{N_S}}}{{{N_S} + {N_F}}} \times \log \frac{{{N_S}}}{{{N_S} + {N_F}}}} \right)$ | (2) |
| $H(F) = E[I(F)] = - \mathop \sum \nolimits \left( {\frac{{{N_F}}}{{{N_S} + {N_F}}} \times \log \frac{{{N_F}}}{{{N_S} + {N_F}}}} \right)$ | (3) |
| $H(C(s)) = E[I(C(s))] = - \mathop \sum \nolimits \left( {\frac{{{N_C}(s)}}{{{N_C}(s) + {N_U}(s)}} \times \log \frac{{{N_C}(s)}}{{{N_C}(s) + {N_U}(s)}}} \right)$ | (4) |
| $H(U(s)) = E[I(U(s))] = - \mathop \sum \nolimits \left( {\frac{{{N_U}(s)}}{{{N_C}(s) + {N_U}(s)}} \times \log \frac{{{N_U}(s)}}{{{N_C}(s) + {N_U}(s)}}} \right)$ | (5) |
为避免程序实体全部被覆盖执行或全部不执行两类随机事件的发生, 我们取未执行一次代替全部执行的事件, 同理, 用覆盖一次代替全部不执行的事件.
对测试事件进一步分析可知: NCF和NUS的数值越高, 说明覆盖程序实体的测试事件更容易导致执行失败而未覆盖程序实体的测试事件更容易使得执行成功, 这两个参数与怀疑度计算成正比.同理可得, NCS和NUF的数值与怀疑度计算成反比.
利用信息熵H(P)、H(F)、H(C(s))和H(U(s))将程序语句存在错误可能性的信息量加权平均, 对计算公式中参数设置权重进行动态调整, 辅助语句可疑度的计算.由于测试事件执行成功与否和其覆盖信息并不是相互独立的, 两者的信息熵无法相加, 故以乘积的方式引入.综上所述, 我们得到的怀疑度计算公式如下:
| $susp(s) = \frac{{(H(C(s)) \times H(F) \times {N_{CF}}(s)) + (H(U(s)) \times H(P) \times {N_{US}}(s))}}{{(H(C(s)) \times H(P) \times {N_{CS}}(s)) + (H(U(s)) \times H(F) \times {N_{UF}}(s))}}$ | (6) |
本节引入了一个简单的例子程序, 该例子程序包含12条语句, 错误语句位于s5处, 例子程序及其控制流图如图 3所示.
|
Fig. 3 An example program and its CFG 图 3 示例程序及其控制流图 |
同时设计了如下8个测试用例: t1(6, 3, 6)、t2(-4, 1, -4)、t3(4, 2, 2)、t4(1, 5, 1, )、t5(1, 0, -1)、t6(2, -4, 1)、t7(0, 4, -1)和t8(0, 0, 1).程序语句的覆盖信息及使用Tarantula和FLPI方法对示例程序的定位结果见表 2.其中, “语句”表示程序相关的语句; “覆盖信息”表示在各个测试用例执行过程中对各个语句的覆盖情况; “排名”表示用Tarantula方法和我们的方法分别计算得到的各个语句出错怀疑度值的排名.
|
|
Table 2 The result of the example program 表 2 示例程序结果 |
针对上述的示例程序, 我们来介绍FLPI方法的定位过程.首先根据控制流图及各节点的IN、OUT、REF、DEF集获取程序所有执行路径中的不同数据依赖关系, 例如语句节点5的IN集为(1, x)、(2, y)、(3, z)和(4, m), OUT集为(5, x)、(2, y)、(3, z)和(4, m), REF集为x和z, 而DEF集则为x.针对语句节点5, 将其REF集中的使用变量与IN集中的流入变量进行对比, 由此可以建立Pl关系(1, 5, x)和(3, 5, z), 同理可以得到所有执行路径中的其他数据依赖关系, 分别为(2, 4, y)、(3, 8, z)、(3, 10, z)、(3, 11, z)、(4, 9, m)、(5, 6, x)、(5, 7, x)、(5, 8, x)、(5, 10, x)、(6, 11, y)、(8, 10, x)、(10, 12, r)和(11, 12, r).
接下来结合程序语句覆盖信息和所有执行路径中的数据依赖关系对示例程序进行路径分析, 得到Pl的覆盖信息并计算其相应的信息熵等值, 所得结果见表 3.
|
|
Table 3 The result of path analysis 表 3 路径分析结果 |
与s5语句相关的Pl为(1, 5, x)、(3, 5, z)、(5, 6, x)、(5, 7, x)、(5, 8, x)和(5, 10, x), 以(1, 5, x)为例, 其信息熵等值计算如下:
| $ H(P)=-\sum\left(\frac{N_{S}}{N_{S}+N_{F}} \times \log \frac{N_{S}}{N_{S}+N_{F}}\right)=-\frac{5}{5+3} \times \log \frac{5}{5+3}=0.42, H(F)=0.53, $ |
| $ H(C(s))=-\sum\left(\frac{N_{C}(s)}{N_{C}(s)+N_{U}(s)} \times \log \frac{N_{C}(s)}{N_{C}(s)+N_{U}(s)}\right)=-\frac{7}{7+1} \times \log \frac{7}{7+1}=0.17, H(U(s))=0.38, \\ {susp}(s)=\frac{\left(H(C(s)) \times H(F) \times N_{C F}(s)\right)+\left(H(U(s)) \times H(P) \times N_{U S}(s)\right)}{\left(H(C(s)) \times H(P) \times N_{C S}(s)\right)+\left(H(U(s)) \times H(F) \times N_{U F}(s)\right)}=\frac{0.17 \times 0.53 \times 3+0.38 \times 0.42 \times 0}{0.17 \times 0.42 \times 5+0.38 \times 0.53 \times 0}=0.757 . $ |
同理可以得到其他与s5语句相关的Pl的怀疑度值分别为0.757、0.757、0.757、1.459和3.786, 加权平均得到susp(s5)=1.379.同理可以得到其余语句的怀疑度值, 详见表 1最后一列.表 1最后一行显示了两种方法在最好和最坏情况下需要检查的语句数, 分别为3-11和5-5.由此示例可知, FLPI方法是可行的.综上, FLPI方法可以减少语句检查数量, 提高错误定位的精度.
3 实验针对本文提出的基于路径分析和信息熵的错误定位方法进行实验验证评估其有效性.实验运行环境为Windows 10和Linux系统, 2.60GHz Intel(R) i5四核处理器, 4GB物理内存.
3.1 实验对象本文选取了17个程序作为实验对象, 程序特征见表 4.前14个程序来自SIR库[19], 后3个开源项目JFreeChar、Joda-Time和Mockito来自Defect4J库[20].
|
|
Table 4 Experimental subject 表 4 实验对象 |
本文的实验最终选取了基准程序中的249个错误版本.剩余程序被排除的主要原因如下: 部分错误版本程序不存在失败的测试用例, 如replace的版本32和schedule2的版本9;部分错误版本程序无法收集到覆盖信息, 如print_tokens的版本4、schedule的版本5和print_tokens2的版本10等; 部分错误版本程序没有输出错误, 如Time的版本2和版本19、Mockito的版本6和版本10等.
3.2 评价标准为了评估所提错误定位方法的有效性, 本文采用以下4个指标与现有方法进行实验比较.
● 累积检查语句数.即对于不同错误版本的基准程序定位到错误时累积检查的总语句数, 其值越低, 说明方法越有效.
● Expense(错误定位代价)[21].Expense从相对指标的角度描述了错误定位方法的精度, 该指标表示在检测到错误时需要检查的程序语句的百分比, 其值越低, 则定位精度越高, 公式具体如下:
| $ { Expense }=\frac{ { Number~~ of ~~~~statements~~ examined }}{ { Total ~~number ~~of ~~statements ~~in ~~the ~~program }} \times 100 \% $ | (6) |
● EXAM(检查得分)[22].EXAM得分可以直观地反映不同错误定位方法的效率, 该指标表示在相同程序语句检查范围内定位到程序错误的数量, 其值越高, 则定位效果越好, 公式具体如下:
| $ EXAM=\frac{{Number~~of~~fault~~examined}}{{Number~~of~~statements~~examined}}×100\% $ | (7) |
● 时间开销.定位错误需要的时间代价, 它反映了不同错误定位方法的性能及时间效率.
3.3 实验设计为了验证本文提出的基于路径分析和信息熵的上下文错误定位方法, 设计对比实验评估其有效性.用于对比实验的错误定位方法主要有3组共7种类型, 其中第1组为经典的错误定位技术, 即Tarantula、Ochiai和Naish1;第2组为较优的Dstar(Tarantula、Ochiai、Nsish1、Dstar公式参见表 1)、Naish2(公式(8))和Russel & Rao(公式(9)), 其中, Dstar公式中的*通常取2[5], 后两个是经理论证明的最优公式[23]; 第3组为基于信息量的错误定位方法SIQ[18].
| $Naish2 = {N_{CF}} - \frac{{{N_{CS}}}}{{{N_{CS}} + {N_{US}} + 1}}$ | (8) |
| $Russel~~\& ~~Rao = \frac{{{N_{CF}}}}{{{N_{CF}} + {N_{UF}} + {N_{CS}} + {N_{US}}}}$ | (9) |
同时实验设计了如下两个问题.
(1) 本文提出的FLPI方法能否提高错误定位的准确度?若能, 具体提高了多少?
(2) 本文提出的FLPI方法能否提高错误定位的效率?若能, 提高了多少?
3.4 实验结果与分析在17个开源程序上开展对比实验, 错误定位方法在每个程序不同版本上定位到错误时累积检查语句数的对比结果见表 5, 而不同方法定位代价的对比结果见表 6.
|
|
Table 5 Comparison of cumulative check statements between FLPI and other methods 表 5 FLPI与其他方法累积检查语句数的比较 |
|
|
Table 6 Expense comparison between FLPI and other methods (%) 表 6 FLPI与其他方法错误定位代价的比较(%) |
使用累积检查语句数指标分析可知: 在17个程序上, FLPI方法累积检查语句总数均少于其他对比方法, 其占Tarantula、Ochiai、Naish1、Naish2、Dstar、Russel & Rao和SIQ方法累积检查语句总数的比例分别为82.44%、84.63%、86.31%、86.61%、85.67%、83.01%和92.72%.针对3组对比对象, 累积检查语句数平均减少了14.09%.
使用错误定位代价Expense指标分析可知: 针对第1组对比方法Tarantula、Ochiai和Naish1, FLPI方法在17个基准程序上错误定位代价分别平均降低了1.87%、1.43%和1.73%, 其中, 在schedule2和tcas两个程序上最为明显, 平均降低了6.21%和4.75%;与Dstar、Naish2和Russel & Rao相比, FLPI方法错误定位代价分别降低了1.29%、1.47%和1.61%, 其中, 在schedule和print_tokens两个子程序上最为明显, 平均降低了6.31%和4.36%;与方法SIQ相比, FLPI错误定位代价最多降低了2.57%.
为了更加直观地对比FLPI和其他方法的定位效果, 使用EXAM指标评估不同方法的效率, 首先分析FLPI和其他方法在Siemens Suite程序集上的对比结果, 所得结果如图 4所示.其中, 横坐标表示代码检查百分比, 纵坐标表示在代码检查范围内定位到程序错误的百分比.
|
Fig. 4 EXAM comparison between FLPI and other methods on Siemens programs 图 4 在Siemens的程序集上FLPI与其他方法检查得分EXAM比较 |
观察图 4可知, 在Siemens Suite程序集上, 本文提出的FLPI方法在检查相同比例代码时可以定位到更多的错误, 而且至多只需要检查70%多的代码语句就可以定位到全部的错误.针对第1组和第2组对比对象Tarantula、Ochiai和Naish2等, EXAM分数有了很大的提高, 在代码检查率为10%时平均提高了15%, 而当检查量超过40%时, 提高比例尤为明显; 对比SIQ方法, FLPI也有一定的提高.
各取3组对比对象中的一种方法, 使用EXAM指标在Siemens Suite中单个程序上开展实验研究, 所得结果如图 5所示.
|
Fig. 5 EXAM comparison between FLPI and other methods on each Siemens program 图 5 在Siemens的单个程序上FLPI与其他方法检查得分EXAM比较 |
观察图 5可知, 在单个程序上不同错误定位方法也有一定的差异, 对于print_tokens2和replace, 所有方法的定位效果都比较好, FLPI在检查相同规模的代码量时可以定位到更多的错误, 在print_tokens、schedule和schedule2程序上, FLPI方法定位效果提高较多, 而所有方法在tcas程序上定位效果相比其他程序略差一些, 主要是因为tacs程序错误版本较多而可执行语句较少.
同样使用EXAM指标评估FLPI和对比方法在NanoXML程序集和XML-sec程序集以及Defect4J上的定位效果, 所得结果如图 6所示.
|
Fig. 6 EXAM comparison between FLPI and other methods on NanoXML, XML-sec, and Defect4J 图 6 NanoXML、XML-sec和Defect4J上FLPI与其他方法检查得分EXAM比较 |
观察图 6可知, 在NanoXML程序集上, 本文提出的FLPI方法在检查相同比例代码时可以定位到更多的错误, 而且最多只需要检查80%的代码语句就可以定位到全部的错误.各取3组对比对象中的一种方法即Tarantula、Naish2和SIQ进行分析, 而在代码检查比例为10%、20%、30%、40%和50%时, FLCP方法定位到的错误比Tarantula多了14%、19%、9%、10%和17%, 相比较Naish2, 多了2%、8%、5%、5%和13%, 而相比较SIQ, 分别多了2%、3%、1%、-1%和4%.同理可得, 在XML-sec程序集上, FLPI方法至多只需要检查70%的代码语句就可以定位到全部的错误, 同样与Tarantula、Naish2和SIQ对比分析可得: 在代码检查比例为10%、20%、30%、40%和50%时, FLPI方法定位到的错误比Tarantula多了23%、25%、25%、14%和18%, 相比较Naish2, 多了10%、14%、14%、17%和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%.
为了进一步验证FLPI方法的有效性, 使用EXAM指标将其与Context-F[24]方法进行对比, 所得结果如图 7所示.在代码检查比例为10%、20%、30%、40%和50%时, FLPI方法比Russel & Rao(Context)提高了29%、14%、6%、1%和3%, 且优于4种方法中最优的Dstar(Context).
|
Fig. 7 EXAM comparison between FLPI and Context-FL 图 7 FLPI与Context-FL检查得分EXAM比较 |
表 7给出了FLPI方法与对比方法在17个基准程序上定位到每个错误版本的平均时间开销情况, 可以看出, 随着程序规模的扩大, 由于对程序执行路径进行数据依赖分析的原因, FLPI的时间成本会有所增加.
|
|
Table 7 Comparison of time cost among FLPI and other techniques 表 7 FLPI与其他方法时间开销对比 |
基于上述对实验结果的分析, 我们来回答第3.3节提出的两个研究问题.
(1) 使用Expense指标对FLPI方法和其他方法的对比实验结果表明: 在不同的实验程序上, FLPI对比Tarantula、Ochiai、Naish1、Dstar、Naish2、Russel & Rao和SIQ的错误定位代价最多降低了8.80%、7.03%、9.12%、7.03%、6.79%、7.28%和2.57%, 而平均错误定位代价分别降低了1.90%、1.45%、1.75%、1.31%、1.49%、1.63%和0.55%.因此, FLPI方法在一定程度上提高了错误定位的精度.
(2) 使用EXAM指标对FLPI方法和其他方法的对比实验结果表明: 在Siemens Suite程序集上, FLPI对比Tarantula、Ochiai、Naish1、Naish2、Russel & Rao和SIQ定位效率都有提高, 其中在print_tokens、schedule和schedule2程序上提高得较多.总体来看, FLPI方法在检查相同比例代码时可以定位到更多的错误, 而且至多只需检查70%多的代码语句就可以定位到程序的全部错误.因此, FLPI方法在一定程度上提高了错误定位的效率.而在NanoXML程序集上, FLPI方法最多只需检查80%的代码语句就可以定位到全部的错误.而在代码检查比例为10%、20%、30%、40%和50%时, FLCP方法定位到的错误比Tarantula多了14%、19%、9%、10%和17%, 相比较Naish2, 多了2%、8%、5%、5%和13%, 而相比较SIQ, 分别多了2%、3%、1%、-1%和4%.同理可得, 在XML-sec上, FLPI方法至多只需检查70%的代码语句就可以定位到全部的错误, 对比上述3种方法, FLPI方法定位到的错误比Tarantula多了23%、25%、25%、14%和18%, 相比较Naish2, 多了10%、14%、14%、17%和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]提出基于信息量的错误定位方法, 该方法根据测试信息中不同事件的类型及其发生的概率, 结合语句的执行信息, 动态地计算和调整错误定位的结果.与他们的方法不同, 我们除了增加信息熵来调整可疑语句的怀疑度计算公式外, 还增加了数据流的分析, 以提高错误定位的精度.
Tarantula[9]是一种经典的基于程序频谱的错误定位技术, 该方法使用覆盖率和执行结果(成功或失败)来度量每个语句的可疑度.在此基础上, 其他研究学者也相继提出了一些方法, 例如Abreu等人[10, 11]受聚类分析和分子生物学领域中相似度系数的启发, 分别提出了Jaccard方法和Ochiai方法, 这些方法极大地提高了错误定位的有效性.不仅如此, 目前基于相似系数的技术已经用于不同的研究, 研究人员还开发了很多实用的程序插件和工具, 使得程序实体的可疑度计算变得更加便捷.Naish等人[30]提出了两种技术O和OP, 其中, 技术O是为寻找单一bug的程序设计的, 而OP更适合于多个错误的程序.Wong等人还提出了H3b和H3c[31]、交叉表[32]和DStar技术[33].Souza等人[34]将两种基于路线图的技术与新的过滤策略相结合实现了语句块级别和方法级别的可疑度度量, 极大地优化了错误定位技术.王赞等人[35, 36]将遗传算法和基于搜索的软件工程思想有机地结合, 寻找最高适应度值的错误实体, 在此基础上, 他们还利用模拟退火算法和遗传算法, 构建了一个称为FSMFL的框架来解决多错误定位问题.宗芳芳等人[37]提出了二次定位策略, 粗分细找, 准确地确定故障的具体位置.在先前的研究中, 我们提出了利用失败执行的上下文信息的缺陷定位方法, 进一步提高基于频谱的错误定位的精度[38].与以上方法不同, 在基于频谱信息的基础上, 本文所提方法增加了路径分析的相关信息, 并在可疑语句怀疑度计算公式中增加了信息熵的相关信息.在之前工作[39]的基础上, 本文开展了更为充分的实验验证, 增加了对比方法实验及实验程序.
6 结束语针对现有的错误定位方法在定位错误时单独考虑程序实体怀疑度, 忽视程序语句之间上下文信息的问题, 本文提出了一种基于路径分析和信息熵的上下文错误定位方法.该方法首先进行程序插桩工作, 执行插桩后的程序并运行测试用例得到程序的执行覆盖信息, 同时通过静态分析对待测源程序构建图形结构, 并利用其进行数据依赖分析; 接下来根据程序的执行轨迹和数据依赖分析结果对程序的执行路径进行分析, 同时利用信息熵理论重新设计怀疑度计算公式, 并结合所有执行路径中不同数据依赖关系的覆盖信息分析得到可疑语句的错误定位报告; 最后按照可疑度值大小顺序检查语句, 定位并修复错误.在实验部分, 本文使用17个基准程序对FLPI方法进行了验证, 对比实验结果表明, FLPI方法能够有效地提高错误定位的准确度和效率.
虽然我们在不同规模的基准程序集上验证了本文方法的有效性, 但未来需要在更大规模、更多语言和真实程序上开展研究.同时, 软件错误定位领域还有许多亟需解决的问题, 例如偶然正确性问题、方法级别的错误定位与多错误定位研究等, 因此, 如何将本文方法及程序上下文信息有效地结合并解决这些问题还有待进一步的探索.此外, 本文所提方法在提高定位精度的同时也增加了一定的时间开销, 因此, 如何在提高错误定位精度的同时优化时间效率也是一个非常值得深入研究的问题.
| [1] |
Collofello JS, Woodfield SN. Evaluating the effectiveness of reliability-assurance techniques. Journal of Systems and Software, 1989, 9(3): 191-195.
[doi:10.1016/0164-1212(89)90039-3] |
| [2] |
Pai GJ, Dugan JB. Empirical analysis of software fault content and fault proneness using Bayesian methods. IEEE Trans. on Software Engineering, 2007, 33(10): 675-686.
[doi:10.1109/TSE.2007.70722] |
| [3] |
Zeller A, Hildebrandt R. Simplifying and isolating failure inducing input. IEEE Trans. on Software Engineering, 2002, 28(2): 183-200.
[doi:10.1109/32.988498] |
| [4] |
Vessy I. Expertise in debugging computer programs: A process analysis. Int'l Journal of Man-machine Studies, 1985, 23(5): 459-494.
[doi:10.1016/S0020-7373(85)80054-7] |
| [5] |
Pearson S, Campos J, Just R, Fraser G, Abreu R, Ernst MD, Pang D, Keller B. Evaluating and improving fault localization. In: Proc. of the 39th IEEE/ACM Int'l Conf. on Software Engineering. 2017. 609-620.
|
| [6] |
Wang KC, Wang TT, Su XH, Ma PJ. Key scientific issues and state-art of automatic software fault localization. Chinese Journal of Computers, 2015, 38(11): 2262-2278(in Chinese with English abstract).
https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201511010.htm |
| [7] |
Wong WE, Gao R, Li Y, Abreu R, Wotawa F. A survey on software fault localization. IEEE Trans. on Software Engineering, 2016, 42(8): 707-740.
[doi:10.1109/TSE.2016.2521368] |
| [8] |
Jones JA, Harrold MJ, Stasko J. Visualization of test information to assist fault localization. In: Proc. of the 24th Int'l Conf. on Software Engineering. 2002. 467-477.
|
| [9] |
Jones JA, Harrold MJ, Stasko J. Visualization for fault localization. In: Proc. of the 23rd Int'l Conf. on Software Engineering. 2001. 71-75.
|
| [10] |
Abreu R, Zoeteweij P, Golsteijn R, Gemund A. A practical evaluation of spectrum-based fault localization. Journal of Systems and Software, 2009, 82(11): 1780-1792.
[doi:10.1016/j.jss.2009.06.035] |
| [11] |
Chen MY, Kiciman E, Fratkin E, Fox A, Brewer E. Pinpoint: Problem determination in large, dynamic internet services. In: Proc. of the 32th Int'l Conf. on Dependable Systems and Networks. 2002. 595-604.
|
| [12] |
Baah GK, Podgurski A, Harrold MJ. The probabilistic program dependence graph and its application to fault diagnosis. IEEE Trans. on Software Engineering, 2010, 36(4): 528-545.
[doi:10.1109/TSE.2009.87] |
| [13] |
Feyzi F, Parsa S. FPA-FL: Incorporating static fault-proneness analysis into statistical fault localization. Journal of Systems and Software, 2018, 136: 39-58.
[doi:10.1016/j.jss.2017.11.002] |
| [14] |
Chen X, Ju XL, Wen WZ, Gu Q. Review of dynamic fault localization approaches based on program spectrum. Ruan Jian Xue Bao/Journal of Software, 2015, 26(2): 390-412(in Chinese with English abstract).
http://www.jos.org.cn/1000-9825/4708.htm [doi:10.13328/j.cnki.jos.004708] |
| [15] |
Zeller A. Why Programs Fail: A Guide to Systematic Debugging. Elsevier, 2009.
|
| [16] |
Aho AV, Lam MS, Sethi R, Ullman JD. Compilers: Principles, Techniques, & Tools. Pearson, 2007.
|
| [17] |
Troya J, Segura S, Parejo JA, Ruiz-Cortes A. Spectrum-based fault localization in model transformations. ACM Trans. on Software Engineering and Methodology, 2018, 27: 3-13.
http://www.zhangqiaokeyan.com/academic-journal-foreign_other_thesis/0204113014339.html |
| [18] |
Ding H, Chen L, Qian J, Xu L, Xu BW. Fault localization method using information quantity. Ruan Jian Xue Bao/Journal of Software, 2013, 24(7): 1484-1494(in Chinese with English abstract).
http://www.jos.org.cn/1000-9825/4294.htm [doi:10.3724/SP.J.1001.2013.04294] |
| [19] |
Do H, Elbaum S, Rothermel G. Supporting controlled experimentation with testing techniques: An infrastructure and its potential impact. Empirical Software Engineering, 2005, 10(4): 405-435.
[doi:10.1007/s10664-005-3861-2] |
| [20] |
Just R, Jalali D, Ernst MD. Defect4J: A database of existing faults to enable controlled testing studies for Java programs. In: Proc. of the 23rd Int'l Symp. on Software Testing and Analysis. 2013. 437-440.
|
| [21] |
Jones JA, Harrold MJ. Empirical evaluation of the Tarantula automatic fault-localization techniques. In: Proc. of the Int'l Conf. on Automation Software Engineering. 2005. 273-282.
|
| [22] |
Wong WE, Qi Y. BP neural network-based effective fault localization. Int'l Journal of Software Engineering and Knowledge Engineering, 2009, 19(4): 573-597.
[doi:10.1142/S021819400900426X] |
| [23] |
Xie X, Chen TY, Kuo FC, Xu B. A theoretical analysis of the risk evaluation formulas for spectrum-based fault localization. ACM Trans. on Software Engineering and Methodology, 2013, 22(4): 1-40.
http://dl.acm.org/doi/pdf/10.1145/2522920.2522924 |
| [24] |
Zhang Z, Tan QP, Mao XG, Lei Y, Chang X, Xue JX. Effective fault localization approach based on enhanced contexts. Ruan Jian Xue Bao/Journal of Software, 2019, 30(2): 266-281(in Chinese with English abstract).
http://www.jos.org.cn/1000-9825/5677.htm [doi:10.13328/j.cnki.jos.005677] |
| [25] |
Li ZJ, Yan LF, Liu YZ, Zhang ZY, Jiang B, MURE: Making use of mutations to refine spectrum-based fault localization. In: Proc. of the IEEE Int'l Conf. on Software Quality, Reliability and Security Companion. 2018. 56-63.
|
| [26] |
Kochhar PS, Xia X, Lo D, Li S. Practitioners' expectations on automated fault localization. In: Proc. of the 25th Int'l Symp. on Software Testing and Analysis. 2016. 165-176.
|
| [27] |
Collofello JS, Cousins L. Towards automatic software fault localization through decision-to-decision path analysis. In: Proc. of the National Computer Conf. 1987. 539-544.
|
| [28] |
Korel B. PELAS-Program error-locating assistant system. IEEE Trans. on Software Engineering, 1988, 14(9): 1253-1260.
[doi:10.1109/32.6169] |
| [29] |
Renieris M, Reiss SP. Fault localization with nearest neighbor queries. In: Proc. of the 18th IEEE Int'l Conf. on Automated Software Engineering. 2003. 30-39.
|
| [30] |
Naish L, Lee HJ, Ramamohanarao. A model for spectra-based software diagnosis. ACM Trans. on Software Engineering and Methodology, 2011, 20(3): 1-32.
|
| [31] |
Wong WE, Debroy V, Choi B. A family of code coverage based heuristics for effective fault localization. Journal of Systems and Software, 2010, 83(2): 188-208.
[doi:10.1016/j.jss.2009.09.037] |
| [32] |
Wong WE, Debroy V, Xu D. Towards better fault localization: A crosstab-based statistical approach. IEEE Trans. on Systems Man and Cybernetics Part C-Applications and Reviews, 2012, 42(3): 378-396.
[doi:10.1109/TSMCC.2011.2118751] |
| [33] |
Wong WE, Debroy V, Gao R, Li Y. The DStar method for effective software fault localization. IEEE Trans. on Reliability, 2014, 63(1): 290-308.
[doi:10.1109/TR.2013.2285319] |
| [34] |
Souza HA, Mutti D, Chaim ML, Kon F. Contextualizing spectrum-based fault localization. Information and Software Technology, 2018(94): 245-261.
http://www.zhangqiaokeyan.com/academic-journal-foreign_other_thesis/0204111300878.html |
| [35] |
Wang Z, Fan XY, Zou YG, Chen X. Genetic algorithm based multiple faults localization technique. Ruan Jian Xue Bao/Journal of Software, 2016, 27(4): 879-900(in Chinese with English abstract).
http://www.jos.org.cn/1000-9825/4970.htm [doi:10.13328/j.cnki.jos.004970] |
| [36] |
Zheng Y, Wang Z, Fan X, Chen X, Yang Z. Localizing multiple software faults based on evolution algorithm. Journal of Systems and Software, 2018, 139: 107-123.
[doi:10.1016/j.jss.2018.02.001] |
| [37] |
Zong FF, Huang HY, Ding ZH. Software fault location based on double-times-locating strategy. Ruan Jian Xue Bao/Journal of Software, 2016, 27(8): 1993-2007(in Chinese with English abstract).
http://www.jos.org.cn/1000-9825/4858.htm [doi:10.13328/j.cnki.jos.004858] |
| [38] |
Wang RC, Jiang SJ, Zhang K, Yu Q. Improving the accuracy of spectrum-based fault localization using multiple rules. IEICE Trans. on Information and System, 2020, E103-D(6): 1328-1338.
[doi:10.1587/transinf.2019EDP7207] |
| [39] |
Zhang X. Research on fault localization based on context[MS. Thesis]. Xuzhou: China University of Mining and Technology, 2020(in Chinese with English abstract).
|
| [6] |
王克朝, 王甜甜, 苏小红, 马培军. 软件错误自动定位关键科学问题及研究进展. 计算机学报, 2015, 38(11): 2262-2278.
https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201511010.htm |
| [14] |
陈翔, 鞠小林, 文万志, 顾庆. 基于程序频谱的动态缺陷定位方法研究. 软件学报, 2015, 26(2): 390-412.
http://www.jos.org.cn/1000-9825/4708.htm [doi:10.13328/j.cnki.jos.004708] |
| [18] |
丁晖, 陈林, 钱巨, 许蕾, 徐宝文. 一种基于信息量的缺陷定位方法. 软件学报, 2013, 24(7): 1484-1494.
http://www.jos.org.cn/1000-9825/4294.htm [doi:10.3724/SP.J.1001.2013.04294] |
| [24] |
张卓, 谭庆平, 毛晓光, 雷晏, 常曦, 薛建新. 增强上下文的错误定位技术. 软件学报, 2019, 30(2): 266-281.
http://www.jos.org.cn/1000-9825/5677.htm [doi:10.13328/j.cnki.jos.005677] |
| [35] |
王赞, 樊向宇, 邹雨果, 陈翔. 一种基于遗传算法的多缺陷定位方法. 软件学报, 2016, 27(4): 879-900.
http://www.jos.org.cn/1000-9825/4970.htm [doi:10.13328/j.cnki.jos.004970] |
| [37] |
宗芳芳, 黄鸿云, 丁佐华. 基于二次定位策略的软件故障定位. 软件学报, 2016, 27(8): 1993-2007.
http://www.jos.org.cn/1000-9825/4858.htm [doi:10.13328/j.cnki.jos.004858] |
| [39] |
张旭. 基于上下文的错误定位方法研究[硕士学位论文]. 徐州: 中国矿业大学, 2020.
|