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

向毅 等: 基于多样性 SAT 求解器和新颖性搜索的软件产品线测试 2823

器所处理对象的标准输入形式. 为了提高所生成测试用例的多样性, 研究人员针对 SAT 求解器本身的改进或者其
灵活运用开展了持续性研究. 例如, Henard 等人 [20,35] 提出了 SAT4J [36] 求解器内部参数的随机化策略 (本文称这种
改造后的求解器为 rSAT4J); Luo 等人 [34] 提出了一种面向软件产品线测试的随机局部搜索 SAT 求解器, 即 LS-
Sampling; Xiang 等人 [33] 建议同时运用两类求解器, 即冲突驱动的子句学习 (conflict-driven clause learning, CDCL)
求解器和随机局部搜索 (stochastic local search, SLS) 求解器. 文献 [33] 所采用的求解器为 rSAT4J (属于 CDCL 求
解器) 和 ProbSAT [37] (属于 SLS 求解器), 但仅前者是一种多样化的 SAT 求解器. 若将后者也进行多样化处理, 是
否有助于进一步改善测试效果? 这是一个有待探索的问题. 针对后者, 既往工作 [20,34] 并未予以足够重视. 事实上, 若
采用多样化 SAT 求解器生成的测试用例无法在最终测试集得以保留, 那么多样性 SAT 求解器的作用也将大打折
扣. 文献 [33] 首次采用新颖性搜索 (novelty search, NS) 算法 [38] 中的归档策略维护测试集的多样性, 取得了较好的
效果. 但是, 该归档策略仅从全局的角度出发考虑测试集的多样性, 而忽略了新测试用例所在区域的局部信息 (如
新测试用例与其最近邻的距离等). 同时提升测试集的全局和局部多样性对测试效果带来怎样的影响? 这也是一个
有待回答的问题.
在既往工作 [33] 的基础上, 本文提出了一种基于多样性 SAT 求解器和新颖性搜索的软件产品线测试算法 (命名
通过最大化测试用例的多样性来模拟
为 dSATNS), 它同时采用了两种不同类型的多样化 SAT 求解器产生测试用例, 并且运用 NS 算法的两种 (全局和
局部) 归档策略维护测试集的多样性. 为了提高 SLS 求解器的多样性, 本文提出了一种基于概率向量的通用策略
为该类求解器产生多样的候选解/种子 (详细介绍见第 4.2 节). 在 50 个真实软件产品线上的实验结果表明, 采用两
类多样性 SAT 求解器的确有助于提高软件产品线测试的覆盖率和缺陷检测率. 实验结果还发现, 仅采用全局和局
部归档策略分别适合测试集规模较大和较小的情形, 而同时采用两种策略则能获得折衷效果. 最后, 对比实验结果
揭示, 本文所提出的算法较主流算法具有显著优势: 无论测试集规模的大小, dSATNS 总是排名第一. 特别地, 当测
试集规模较小时, dSATNS 的优势愈明显. 在测试资源 (时间、成本等) 有限的情况下, 测试人员往往希望通过运行
尽可能少的测试用例以发现尽可能多的缺陷, 而本文所提出的算法为生成这样的测试用例的集合提供了一种行之
有效的解决方案.
本文的主要贡献包括: 1) 提出了一种基于概率向量的通用策略为 SLS 求解器生成多样化的种子. 该策略简单
易实现, 可在不改变现有 SLS 求解器内部搜索机理的情形下, 辅助求解器生成多样化的测试用例. 2) 根据 NS 算法
的思想, 设计了一种局部归档策略维护测试集的多样性. 该策略与现有的全局归档策略 [33] 形成互补效应. 3) 综合
运用两类多样性求解器和两种归档策略, 提出了一种面向软件产品线测试的 dSATNS 算法, 其性能显著优于当前
主流算法.
本文第 2 节回顾基于相似性的软件产品线测试方法. 第 3 节介绍本文所需的基础知识, 包括特征模型和软件
产品线测试相关概念. 第 4 节详细介绍本文提出的软件产品线测试算法 dSATNS. 第 5 节通过消融和对比实验验
证各算法构件的有效性以及本文算法较其他主流算法的优越性, 并探讨关键参数对算法性能的影响. 第 6 节总结
全文.

2 基于相似性的软件产品线测试相关工作

Henard 等人 [20] t-组合测试. 具体地, 他们提出了一种基于相似性的适应
度函数并采用遗传算法 (genetic algorithm, GA) 进行优化. 这样做的目的是生成一组尽可能不相似 (多样) 的测试
用例, 从而潜在地覆盖更多的特征组合 (或软件缺陷). 此外, 为提高 SAT4J 求解器 [36] 所生成测试用例的多样性, 作
者建议随机化该求解器的内部参数, 即为变量赋值的策略 (包括正文字优先、反文字优先和随机文字). 实验结果

表明, Henard 等人的方法可处理大规模和高交互强度的情形, 是 t-组合测试的一种可拓展的、灵活的替代方案. 测
试用例生成工具 PLEDGE [30] 实现了上述方法. 随后, Fischer 等人 [29] 的实验结果表明, Henard 等人 [20] 的方法能有效
地检测出软件产品线 Drupal [39] 的真实缺陷. 上述方法可取得与 CASA [14] 相当的 t-组合覆盖率. 这些研究结果充分
说明, 相似性指标是 t-组合覆盖率的一种恰当的替代.