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

2170 Journal of Software 软件学报 Vol.32, No.7, July 2021

发生故障.数据依赖路径分析不仅可以得到变量状态变化信息及其传递轨迹,而且可以获取语句之间的相互作
用和依赖关系,为错误定位分析提供更加有效的上下文信息.变量依赖关系说明了其值和内部状态发生改变的
机理,主要包括变量之间的语义联系和变量的自身依赖.
Aho 等人 [16] 提出了利用控制依赖图和控制依赖子图进行数据依赖分析的方法.收集控制依赖图的 DEF[n]、
REF[n]、KILL[n]、IN[n]和 OUT[n]集合,其分别代表语句节点 N 中产生变量的集合、使用变量的集合、杀死变
量的集合、流入语句节点的变量集合和流出语句节点的变量集合.除 DEF[n]和 REF[n]外,其余集合均为一个语
句节点和变量构成的二元组,表示为l i ,v x .本文参考了文献[16]中的方法,使用控制流图 CFG 获取上述集合并进
行数据依赖分析.
算法 1 描述了对程序所有执行路径进行数据依赖分析的过程.输入控制流图以及各节点的 IN、OUT、REF、
DEF 集,对 CFG 进行遍历,针对图中的每个节点 N,首先判断其变量的使用情况,在使用集不为空时将使用变量 x
与 IN 集中的变量 v x 对比,并建立从节点 N 到节点 l i 的数据依赖边(第 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 l i ,v x  in IN[n] do
5. if v x ==x then
6. establish data-dependent edges from node N to l i
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
在一条执行路径上,若在语句节点 l i 处定义了变量 v x ,而在语句节点 l j 处引用了变量 v x ,那么我们使用 P l
(l i ,l j ,v x )来表示这种数据依赖关系,其中,l i 为依赖前驱,l j 为依赖后继,v x 为依赖变量.P l (l i ,*,v x )和 P l (*,l i ,v x )分别代表
以 l i 为依赖前驱和后继的不同数据依赖关系.通过对语句节点 l i 所有不同执行路径的分析可以得到其有效上下
文信息,利用数据流对变量定义使用的跟踪和变量依赖关系的描述分析程序复杂的行为,更好地定位程序错误
的位置.
2.3 测试事件信息熵与怀疑度计算
SBFL 方法就是针对程序的执行覆盖信息进行一系列操作,进而确定程序语句出错的可能性 [17] ,从本质上
讲就是利用怀疑度公式进行概率统计.程序语句在测试用例下的执行信息和覆盖特征可以用一个四元组表示,
即(N CF ,N UF ,N CS ,N US ),其分别代表不同的随机事件.以往的怀疑度计算仅仅考虑了不同事件发生的次数而忽略了
组合事件附带的信息.信息熵是表示随机事件不确定性的数学化度量,因此利用信息熵可以将程序语句存在错
误可能性的信息量加权平均,将两者有机结合即可将测试事件信息引入到可疑度计算中.
在错误定位研究过程中,若存在大量执行失败的测试用例,那么对执行成功的测试用例进行研究可以获得