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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2024,35(6):2821−2843 [doi: 10.13328/j.cnki.jos.006906] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
基于多样性 SAT 求解器和新颖性搜索的软件产品线测试

向 毅 1 , 黄 翰 1 , 罗 川 2 , 杨晓伟 1

1
(华南理工大学 软件学院, 广东 广州 510006)
2
(北京航空航天大学 软件学院, 北京 100191)
通信作者: 黄翰, E-mail: hhan@scut.edu.cn

摘 要: 软件产品线测试是一项非常具有挑战性的工作. 基于相似性的测试方法通过提升测试集的多样性以达到
提高测试覆盖率和缺陷检测率的目的. 因其具有良好的可拓展性和较好的测试效果, 目前已成为软件产品线测试
的重要手段之一. 在该测试方法中, 如何产生多样化的测试用例和如何维护测试集的多样性是两个关键问题. 针对
以上问题, 提出一种基于多样性可满足性 (SAT) 求解器和新颖性搜索 (novelty search, NS) 的软件产品线测试算法.
Key words: software product line testing; satisfiability solver; novelty search
具体地, 所提算法同时采用两类多样性 SAT 求解器产生多样化的测试用例. 特别地, 为了改善随机局部搜索 SAT
求解器的多样性, 提出一种基于概率向量的通用策略产生候选解. 此外, 为同时维护测试集的全局和局部多样性,
设计并运用两种基于 NS 算法思想的归档策略. 在 50 个真实软件产品线上的消融和对比实验验证多样性 SAT 求
解器和两种归档策略的有效性, 以及所提算法较其他主流算法的优越性.
关键词: 软件产品线测试; 可满足性求解器; 新颖性搜索
中图法分类号: TP311

中文引用格式: 向毅, 黄翰, 罗川, 杨晓伟. 基于多样性SAT求解器和新颖性搜索的软件产品线测试. 软件学报, 2024, 35(6):
2821–2843. http://www.jos.org.cn/1000-9825/6906.htm
英文引用格式: Xiang Y, Huang H, Luo C, Yang XW. Software Product Line Testing Based on Diverse SAT Solvers and Novelty
Search. Ruan Jian Xue Bao/Journal of Software, 2024, 35(6): 2821–2843 (in Chinese). http://www.jos.org.cn/1000-9825/6906.htm

Software Product Line Testing Based on Diverse SAT Solvers and Novelty Search
1
2
1
XIANG Yi , HUANG Han , LUO Chuan , YANG Xiao-Wei 1
1
(School of Software Engineering, South China University of Technology, Guangzhou 510006, China)
2
(School of Software, Beihang University, Beijing 100191, China)
Abstract: Software product line testing is challenging. The similarity-based testing method can improve testing coverage and fault
detection rate by increasing the diversity of test suites. Due to its excellent scalability and satisfactory testing effects, the method has
become one of the most important test methods for software product lines. How to generate diverse test cases and how to maintain the
diversity of test suites are two key issues in this test method. To handle the above issues, this study proposes a software product line test
algorithm based on diverse SAT solvers and novelty search (NS). Specifically, the algorithm simultaneously uses two types of diverse SAT
solvers to generate diverse test cases. In particular, in order to improve the diversity of stochastic local search SAT solvers, the study
proposes a general strategy that is based on a probability vector to generate candidate solutions. Furthermore, two archiving strategies
inspired by the idea of the NS algorithm are designed and applied to maintain both the global and local diversity of the test suites.
Ablation and comparison experiments on 50 real software product lines verify the effectiveness of both the diverse SAT solvers and the
two archiving strategies, as well as the superiority of the proposed algorithm over other state-of-the-art algorithms.

* 基金项目: 广东省科技攻关重点项目 (2020B0303300001); 2018–2019 年度广东省“新一代人工智能”重大项目 (2020AAA0108404); 国
家自然科学基金 (61906069, 62276103, 62202025, 61876207); 广东省基础与应用基础研究基金 (2019A1515011700, 2020A1515010696,
2022A1515011491); 中央高校基本科研业务费专项资金 (2020ZYGXZR014); 广东省财税大数据重点实验室开放基金 (2022kyc021)
收稿时间: 2022-07-12; 修改时间: 2022-09-19; 采用时间: 2023-01-19; jos 在线出版时间: 2023-07-05
CNKI 网络首发时间: 2023-07-07