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

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

99.4
70 90
99.2
69 89
覆盖率 (%) 68 覆盖率 (%) 88 覆盖率 (%) 99.0

98.8
67
87 98.6
66
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0

P r P r P r
(g) 2.6.28.6-icse11 (N=4) (h) 2.6.28.6-icse11 (N=10) (i) 2.6.28.6-icse11 (N=100)

图 10 参数 P r 对算法性能的影响 (续)

综上, RQ4 的答案如下: 参数 P r 对 dSATNS 算法性能的影响因 N 值及待求解特征模型的不同而有所不同. 一

P r 取较小值 (如 0.1) 时效果较好. 这与既往工作 [33] 的结论是一致的.
般地,
6 结 论

本文研究基于相似性的软件产品线测试方法, 提出了一种基于多样性 SAT 求解器和新颖搜索的算法. 该算法
的目的在于产生并维护一组多样化的测试用例, 进而覆盖更多的特征组合、发现更多的软件缺陷. 为了生成多样
化的测试用例, 同时采用了两类 (CDCL 和 SLS) 多样性 SAT 求解器. 实验结果表明, 多样性求解器的运用确实有
助于提升多样性, 进而提高覆盖率和缺陷检测率. 为维护测试集的多样性, 同时采用了全局和局部归档策略, 它们
均以 NS 算法的思想为基础. 其中, 局部归档策略是本文提出的一种新方法. 实验结果揭示, 全局和局部档案策略
分别适用于测试集规模较大和较小的情形, 而两个档案策略的同时运用则能获得折衷效果. 最后, 对比实验表明本
文所提算法的整体性能优于其他主流算法. 特别是当测试集规模较小时, 本文算法具有明显优势.
本文所建议的多样性 SAT 求解框架 (即算法 2) 是通用的. 现在所采用的 SAT 求解器完全可以直接替换成任
何其他求解器, 如 Glucose [48] , NLocalSAT [49] , LS-Sampling [34] , SamplingCA [50] 等. 在将来, 比较这些求解器的性能表
现并给出关于如何选择求解器的合理建议是一项有意义的工作. 在多样性 SLS 求解器的设计方面, 将概率向量与
ProbSAT 所采用的随机机制深度结合是一个值得尝试的方向. 最后, 我们也将探索把本文所采用的双归档策略应
用于与软件产品线相关的其他任务, 如多样性采样 [51] 等.

References:
[1] Clements PC, Northrop LM. Software Product Lines: Practices and Patterns. Boston: Addison-Wesley Professional, 2001. 1–10.
[2] Al-Hajjaji M, Thüm T, Lochau M, Meinicke J, Saake G. Effective product-line testing using similarity-based product prioritization.
Software & Systems Modeling, 2019, 18(1): 499–521. [doi: 10.1007/s10270-016-0569-2]
[3] Hierons RM, Li MQ, Liu XH, Parejo JA, Segura S, Yao X. Many-objective test suite generation for software product lines. ACM Trans.
on Software Engineering and Methodology, 2020, 29(1): 2. [doi: 10.1145/3361146]
[4] Lian XL, Zhang L. Multi-objective optimization algorithm for feature selection in software product lines. Ruan Jian Xue Bao/Journal of
Software, 2017, 28(10): 2548–2563 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5130.htm [doi: 10.13328/j.cnki.
jos.005130]
[5] Batory D. Feature models, grammars, and propositional formulas. In: Proc. of the 9th Int’l Conf. on Software Product Lines (SPLC 2005).
Rennes: Springer, 2005. 7–20. [doi: 10.1007/11554844_3]
[6] Benavides D, Segura S, Ruiz-Cortés A. Automated analysis of feature models 20 years later: A literature review. Information Systems,
2010, 35(6): 615–636. [doi: 10.1016/j.is.2010.01.001]
[7] Al-Hajjaji M, Thüm T, Meinicke J, Lochau M, Saake G. Similarity-based prioritization in software product-line testing. In: Proc. of the
18th Int’l Software Product Line Conf. (Vol. 1). Florence: Association for Computing Machinery, 2014. 197–206. [doi: 10.1145/2648511.