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

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

安全的选择策略将所有覆盖程序中受影响部分的测试用例作为回归测试用例,例如基于代码修改的回归
测试用例选择策略.
(4) 最小化策略.
在原始程序的测试集合中选择可以保证程序中被修改代码至少被覆盖 1 次的最小子集作为回归测试集合.
全部重新测试用例所消耗的执行成本大,而随机选择策略依赖于测试人员的经验,稳定度低,精确度不高.
最小化策略所选择出的测试用例集合最小,执行成本低,但是错误检测能力较差.安全的测试选择策略所选出的
测试集检测错误的能力较强,用例数目相对不是很多,因此通常使用安全的选择策略进行回归测试的选择.但随
着程序规模的扩大,安全选择策略中进行程序分析的成本也随之增加.
随着软件开发规模的扩大,研究人员对回归测试的关注越来越多,提出了很多有效的回归测试选择策略,其
中包括整数规划、数据流分析、符号执行、动态切片、graph-walking、源代码文本差异、SDG 系统依赖图切
片、路径分析、变更检测、防火墙、控制流图聚类识别、基于设计的测试等方法.很多研究工作对回归测试用
[6]
例技术进行了总结和系统性综述 [1620] .Rothermel 等人 提出一种基于程序依赖图的安全的回归测试选择技术,
这是一种非常经典的回归测试选择技术.这种技术通过构造原始程序 P 和修改后的程序 P'的依赖图,深度优先
遍历两个依赖图并识别出依赖图中被修改的节点,然后挑选出所有覆盖修改节点的测试用例.对于被修改的程
序,一个能够检测出故障的测试用例必然是覆盖修改节点的测试用例,因此,Rothermel 等人提出的回归测试选
择技术是安全的,其回归测试集合包含了所有能够检测故障的测试用例.然而,这种测试用例选择技术选择出的
测试用例集合包含了许多无法发现故障的测试用例.这种方法虽然能够保证安全性,但是并不能有效地降低测
试成本,因此很多测试用例选择方法在测试集合大小与错误发现能力之间进行了权衡,在保障一定安全性的前
提下减小了测试集合大小.Graves 等人 [21] 指出,回归测试的核心问题是选择和执行测试用例所需要的时间和测
试集合的故障检测能力之间的权衡问题.
常用的回归测试选择策略基于代码修改分析等方法找出代码修改相关的测试用例,并将其作为回归测试
选择用例.这里将覆盖了被修改代码的测试用例称为“覆盖修改的用例”,将可检测出被修改程序中的错误的测
试用例称为“故障检测用例”.覆盖修改用例不一定是故障检测用例,覆盖修改的用例集合还包含了虽然覆盖修
改但发生了偶然正确性现象的用例,图 1 所示为这 3 类测试用例之间的关系.偶然正确性现象在实际场景中非
常频繁地发生,这导致覆盖修改用例中包含大量的偶然正确性用例,因此,目前的回归测试选择策略受到了偶然
正确性现象的不良影响.

Fig.1 The set of modification-traversing test
图 1 覆盖修改测试用例集合
2.3 偶然正确性概率的估算

为了消除偶然正确性现象对回归测试选择的影响,首先需要判断测试用例执行时是否发生偶然正确性现
象.在以往的工作中 [2,5] ,我们提出了估计程序执行中发生偶然正确性现象概率的方法,该方法从代码执行过程
中内存空间中值变化的角度出发,通过动态的数据流和控制流两个方面对发生偶然正确性的概率进行估算.根
据 PIE 模型,错误被发现需要满足执行、感染和传播 3 个条件,而这 3 个事件的发生有一定的包含关系.假设程
序中语句 s 包含错误,在执行测试 t 时该错误被发现的概率 T(s,t)可用条件概率进行计算:
T(s,t)=PR(E)PR(I|E)PR(P|EI) (1)
其中,PR(E)表示 s 被执行的概率,这个概率可以通过错误语句 s 在此次执行中是否被覆盖直接得到.如果错误语