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

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

(2) 存在一条路径以 e 2 开始并以结束节点结束,而中间节点不包含 n 1 .
定义 3. 数据依赖:在控制流图 G 中,节点 n 1 数据依赖于节点 n 2 ,当且仅当满足以下条件.
(1) 节点 n 2 定义了变量 v;
(2) G 中存在一条从 n 2 到 n 1 但未重新定义 v 的路径;
(3) 节点 n 1 使用了变量 v.
Zeller [15] 提出的 Defect-Infection-Failure 模型指出:开发人员在用给定的测试用例执行缺陷程序时,软件缺
陷可能会导致其余源代码部分的感染,感染状态的传播最终会导致程序失效.程序实体间的依赖分析不仅有助
于定位引起程序失效的根源,而且还充分考虑了感染状态在程序内部的传播机制,为理解程序失效提供了有效
的上下文信息,一定程度上可以帮助开发人员理解错误产生的原因.因此在错误定位过程中引入程序依赖性分
析可以有效地提高方法的精度和准确性.
下面给出数据依赖路径分析过程中的相关定义.
0
n
n
1
1
0
定义 4. 变量轨迹:变量 v x 的轨迹为 Trace(v x )={ v , v ,…, v },其中, v 、 v 、 v 表示程序中变量 v x 在程序
x x x x x x
执行过程中的定义与使用.
变量的定义是指其值或内部状态发生改变,通常出现在赋值指令、输入数据指令或过程调用中,而变量的
使用是指其值或内部属性被读取,但未发生任何改变的过程.这样一个程序的行为就可以通过一组变量跟踪来
表示.
i
i
i
i
i
定义 5. 变量依赖关系:变量 v x 和 v y 的依赖关系为 VDR(v x ,v y )={( v , v ) | v Trace(v x ), v  Trace(v y ), v 
x y x y x
i
v },其中,“→”表示数据依赖关系.
y
2 本文方法
2.1 总体框架
FLPI 方法以待测程序 PG 和测试用例集 T c 作为输入,最终得到错误定位报告.整体框架主要包括 3 个部分:
预处理阶段、错误定位方法和定位结果显示,如图 2 所示.
① 预处理阶段:通过静态分析对待测源程序 PG 构建控制流图,同时进行程序插桩工作,编译执行插桩后的
程序并运行测试用例集,获取程序的执行轨迹和覆盖信息.
② 利用控制流图分析得到程序所有执行路径中的不同数据依赖关系,即以语句节点 l i 作为数据依赖前驱
和依赖后继时的不同 P l ,结合程序的执行轨迹和数据依赖路径分析结果得到 P l 的覆盖信息,根据覆盖信息矩阵
计算得到 P l 在执行过程中 4 类随机事件的信息熵.
③ 计算所有路径中不同 P l 的怀疑度值,对于涉及到语句 l i 的所有 P l 的怀疑度值进行加权平均,最终得到程
序所有语句节点的怀疑度,生成错误定位报告定位到错误语句.

Fig.2 Overall framework of our approach
图 2 本文方法的总体框架
2.2 数据依赖路径分析
程序变量的状态在程序运行过程中沿着不同的执行路径发生改变,变量的不正确定义和使用会造成程序