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

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

SBFL 方法一般遵循以下步骤:执行测试用例,通过插桩技术获取源程序在给定测试用例集下的覆盖信息
以及执行结果,并根据覆盖信息和执行结果构建测试覆盖矩阵和执行结果向量;统计分析覆盖信息,借助不同的
错误定位公式计算程序实体的可疑度,并根据可疑度计算结果由高到低的顺序排列程序实体.程序实体的可疑
度越高,其包含错误的可能性就越大,开发人员依次检查程序实体开展错误定位工作.基于频谱的软件错误定位
框架如图 1 所示.

Fig.1 Spectrum-based fault localization framework
图 1 基于频谱的软件错误定位框架

对于任意一个程序实体 S i ,其在测试用例下的执行信息和覆盖特征可以用一个四元组表示,即 N s =(N CF ,N UF ,
N CS ,N US ).4 个元素分别代表执行失败且覆盖程序实体 S i 的测试用例次数、执行失败且未覆盖程序实体 S i 的测
试用例次数、执行成功且覆盖程序实体 S i 的测试用例次数和执行成功且未覆盖程序实体 S i 的测试用例次数.
一般情况下,用 N F 表示所有执行失败的测试用例次数,用 N C 表示所有执行成功的测试用例次数.表 1 给出了几
种典型的错误定位技术可疑度度量公式.
Table 1 The calculation formula of suspicious degree for fault localization
表 1 典型的错误定位怀疑度计算公式
公式名称 公式表达式
CF N
N ∕
Tarantula F
N CF N ∕ F N CS N∕ S
N
Ochiai CF
N F  (N CF  N CS )
  1N ＜ N F
CS
Naish1 
 N S  NN CS  N F
CS
N *
Dstar CF
N CS  N UF
N
Jaccard CF
N CS  N CF  N UF
Wong2 N CF－N CS

1.2 程序依赖性分析
程序依赖分析主要分析程序实体的执行顺序、函数之间的相互调用以及依赖关系,是一种理解和分析软件
行为特征的重要手段,在程序分析与调试、软件测试与维护等软件工程领域有着广泛的应用.目前常用的方法
主要包括过程内的依赖分析(控制依赖分析和数据依赖分析等)、过程间的依赖分析(程序依赖图分析等)和程序
切片等.下面给出程序依赖性分析的相关定义.
定义 1. 控制流图 CFG(control flow graph).程序 PG 的控制流图是一对(N,E)组合,其中,N 代表 PG 中所有语
句的节点集合,E 代表有向边集合,而边(n i ,n j )则表示从节点 n i 到节点 n j 的控制流,其中,条件分支和循环边上的标
识表示取这些边时的条件.
定义 2. 控制依赖:在控制流图 G 中,如果节点 n 2 具有输出边 e 1 和 e 2 ,则节点 n 1 控制依赖于 n 2 ,当且仅当满
足以下条件.
(1) G 中以 e 1 开始并以结束节点结束的每条路径都包含 n 1 ;