Page 248 - 《软件学报》2024年第6期

2824 软件学报 2024 年第 35 卷第 6 期

Al-Hajjaji 等人 [2,7] 系统地研究了基于相似性的测试用例排序, 即确定测试用例的顺序从而尽可能快地发现缺陷.
他们将相似性定义为待选测试用例与所有已选测试用例的最小距离, 而非 Henard 等人 [20] 所定义的距离之和 (某些
情形下具有一定误导性 [2] ). 随后, Al-Hajjaji 等人 [31] 又探讨了如何利用不同类型的信息度量软件产品之间的相似性.
特别地, 他们将计算相似性的输入信息分为问题空间信息 (如特征选择相似性、属性相似性和实例相似性) 和解空间
信息 (如家族模型相似性). 此外, 他们还探讨了结合不同类型的信息以构造产品综合相似性指标的可能性.
针对行为 SPLs, Devroey 等人 [32] 研究了基于相似性的测试用例生成问题. 结果表明, 基于相似性的测试用例
生成与行为 SPL 模型是有关联的. 此外, 作者还比较了多个度量测试用例相似性的距离, 发现 Hamming 和 Jaccard
距离最为有效. 从既往工作的实验结果看, 相似性指标的改进的确能获得不错的 t-组合覆盖率或缺陷检测率. 相似
性指标与 t-组合覆盖密切相关也符合人们的直觉. 但是, 基于相似性的软件产品线测试方法为什么有效并未得到
强有力的解释.
最近, Xiang 等人 [33] 借助相关性分析发现, 相似性指标与 t-组合覆盖率之间是呈显著正相关的. 该发现有利于
从统计学角度阐明基于相似性的软件产品线测试的基本原理: 相似性指标的改善可潜在地提升 t-组合覆盖率. 此
外, 为维护并提升测试集的多样性, 他们采用 NS 作为搜索算法. 作为进化算法的一种新范式, 该算法不断奖励“新

颖”个体, 即与已发现的个体不同的个体. 上述算法机理高度契合基于相似性的软件产品线测试的目标, 故采用
NS 算法是非常恰当的. 文献 [33] 的实验结果也证实了上述断言. 最后, 他们还从实验上论证, 针对软件产品线测
试用例的生成问题, 将 CDCL 求解器与 SLS 求解器相结合是一种非常有前景的方法.
与文献 [33] 一样, 本文也采用了两类 SAT 求解器和 NS 算法中的归档策略. 不同的是, 本文采用的是两类多
样化的 SAT 求解器, 其中多样化的 SLS 求解器是由本文提出的一种通用策略实现的. 此外, 本文同时运用了文
献 [33] 中的全局归档策略和我们提出的一种局部归档策略, 兼顾了测试集的全局和局部多样性, 形成了互补效应,
而文献 [33] 仅考虑了测试集的全局多样性. 从第 5 节的实验结果将看到, 多样化 SAT 求解器和两种归档策略的综
合运用显著改进了文献 [33] 中的算法.
3 基础知识

本文研究软件产品线的测试问题, 下面就相关概念和基本知识予以介绍.
3.1 特征模型

如第 1 节所述, 软件产品线采用可复用的软件模块系统式地组装软件产品, 这些产品具有共性, 也有特性. 特
征模型 (FM) 是一种表示软件产品线共性与特性的直观、简洁方法. 视觉上, 特征模型是一种树状结构, 其中每个
节点代表一个特征, 代表系统的某个功能模块, 边则明确了特征之间的约束关系. 例如, 图 1 所示的特征模型表示
的是一个简化后的移动手机软件产品线, 共包含 10 个特征 (模块). 一般地, 特征模型中存在 6 大类约束关系, 分别
为强制的 (mandatory), 可选的 (optional), 或 (or), 排斥或 (xor), 需要 (require) 和排斥 (exclude). 研究表明 [5] , 上述所
有约束关系均可由命题公式表示, 进一步可转换为等价的合取范式 CNF. 图 1 中的特征模型所描述的约束关系可
转换为以下 CNF.
FM = x 1 ∧(¬x 1 ∨ x 2 )∧(x 1 ∨¬x 2 )∧(¬x 1 ∨ x 4 )∧(x 1 ∨¬x 4 )∧(x 1 ∨¬x 3 )∧(x 1 ∨¬x 5 )∧(x 4 ∨¬x 6 )
= ∧(x 4 ∨¬x 7 )∧(x 4 ∨¬x 8 )∧(¬x 4 ∨ x 6 ∨ x 7 ∨ x 8 )∧(¬x 6 ∨¬x 7 )∧(¬x 6 ∨¬x 8 )∧(¬x 7 ∨¬x 8 )
= ∧(x 5 ∨¬x 9 )∧(x 5 ∨¬x 10 )∧(¬x 5 ∨ x 9 ∨ x 10 )∧(x 8 ∨ x 9 )∧(¬x 3 ∨¬x 6 ) (1)
其中, 每个析取式 (如 ¬x 1 ∨ x 2 等) 称为子句. 所有子句的集合称为特征模型的功能性约束集. 值得说明的是, CNF
是 SAT 问题的标准形式. 因此, 为变量赋值使得它们满足所有功能性约束本质上是求解一个 SAT 问题.
x 1 , x 2 ,..., x n 表示特征模型的 n l 1 ,l 2 ,...,l m 表示特征模型对应 CNF 约束中的 m 个
更正式地, 若采用 个特征, 用
子句. 我们有以下定义:
定义 1. 特征模型可看作一个二元组 (X,L) , 其中 X = {x 1 , x 2 ,..., x n } 表示 n 个布尔型特征 (即变量), L =
{l 1 ,l 2 ,...,l m } 表示特征之间的 m 个约束关系. 称 L 是满足的当且仅当所有 l i (i = 1,2,...,m) 均是满足的.