软件产品线测试的新技术突破-k8凯发旗舰

软件产品线（software product line, spl）是一种有效的软件开发方法，既可以满足终端用户多样化的需求，实现产品的个性化定制，又有助于节约开发成本，减少维护工作量。由于测试产品数量随特征（软件产品线的模块）数量呈指数增长，测试所有软件产品在实际中几乎不可行。为平衡测试可靠性和测试集数量，t-组合测试应运而生，它要求找到一个可覆盖任意t个特征所有可能组合的最小测试集。然而，现有的t-组合测试算法难以有效处理实际应用中存在的大规模和高交互强度的情形。

不少研究引入了基于相似性的测试方法以解决t-组合测试可扩展性差的问题。这类方法在生成测试集时需增强当前测试集的多样性以实现特定目标，如最大化缺陷检测率或覆盖率等。基于相似性的测试无法确保100%的t-组合覆盖率，但可以灵活地设置待生成的测试用例个数及运行时间。在测试资源有限的情形下，基于相似性的测试具有更强的灵活性。

近期，智能算法研究中心的研究人员提出了一种基于多样性可满足性（satisfiability, sat）求解器和新颖性搜索（novelty search, ns）的软件产品线测试算法dsatns [1]。该算法采用多样性sat求解器产生测试用例，运用新颖性搜索（novelty search, ns）算法的归档策略维护测试集的多样性，并以迭代改进的方式不断提升当前测试集的多样性，进而覆盖更多特征组合或发现更多缺陷，如图1所示。

图1 dsatns算法示意图

（1）多样性sat求解器

dsatns算法结合了两类多样性求解器，依概率调用rsat4j [2]和probsat。其中，rsat4j是随机化版本的sat4j [3]，旨在产生不相似的sat解；而dprobsat则是研究人员提出的probsat [4]的改进算法。如图2所示，dprobsat借助概率向量产生一个多样化的初始解c，若c不可行，则调用原始的probsat予以修复。作为一个通用框架, 该算法适用于任何sls类型的sat求解器。

图2 dprobsat算法示意图

（2）测试集的归档策略

dsatns根据ns算法采用了两种归档策略globalarch（见图3）和localarch（见图4），分别考虑了测试集的全局多样性和局部多样性。新颖得分是ns算法中的核心概念，度量个体所在区域的拥挤程度。新颖得分越高，说明个体所在区域越稀疏，反之则越密集。globalarch通过不断搜索新颖得分更高的个体并替换，提高了测试集的整体多样性，但忽略了新个体所在区域的局部信息。新个体的加入可能会导致出现局部聚集的现象，而在localarch的策略中，新测试用例及与其最近的测试用例不能同时存在，提高了测试集的局部多样性。

图3 全局归档策略globalarch的示意图

图4 局部归档策略localarch的示意图

研究人员在50个公开的软件产品线上进行仿真实验，验证了dsatns算法各组件的有效性。实验结果表明，采用多样性求解器有助于改善覆盖率和缺陷检测率，全局和局部归档策略则相辅相成，适用于测试集规模较大和较小的情形。

图5给出了dsatns与各主流算法关于缺陷检测率的u检验结果。由图5可知，无论 n（测试集规模）多大，dsatns 始终优于tsega [5]和tsens [5]。当n较小时，dsatns的优势尤其明显；当n较大时，dsatns在80%以上的特征模型上与其对比算法无显著的统计差异。与sat4j [3]相比，dsatns始终具有压倒性优势。

图5 dsatns与主流算法缺陷检测率的u检验结果。黑、白、灰三种实验结果标注分别表示第一个算法显著优于、差于和等同于第二个算法[1]。

图6展示了通过friedman检验得到的dsatns与各对比算法在缺陷检测率指标上的平均排名。对所有n值而言，dsatns不仅获得了最佳排名，而且与其他算法的性能差异在多数情形下具有统计显著性。当n较小时，dsatns展现出卓越的性能表现，这对于该算法的实际应用是非常有利的。因此可以得出结论：dsatns的整体性能优于其他主流算法。

图6 friedman 检验得到的各算法的平均排名（越小越好）[1]

综上所述，智能算法研究中心究基于相似性的软件产品线测试方法，提出了一种基于多样性 sat 求解器和新颖性搜索的算法dsatns，在软件产品线测试中展现出了卓越的性能表现。

本文算法中提出的多样性sat求解框架是通用的，现在所采用的sat求解器完全可以直接替换成任何其它求解器。因此，在后续工作中比较这些求解器的性能表现并给出关于如何选择求解器的合理建议是有意义的。此外，智能算法研究中心也将探索把双归档策略应用于与软件产品线相关的其他任务，如多样性采样等，以期为软件测试方法的发展作出积极贡献。

参考文献

[1] 向毅, 黄翰, 罗川, 等. 基于多样性 sat 求解器和新颖性搜索的软件产品线测试[j]. 软件学报, 2023, 33: 1-23.

[2] henard c, papadakis m, perrouin g, et al. bypassing the combinatorial explosion: using similarity to generate and prioritize t-wise test configurations for software product lines[j]. ieee transactions on software engineering, 2014, 40(7): 650-670.

[3] anne p. the sat4j library release 2.2 system description[j]. journal on satisfiability, boolean modeling and computation (jsat), 2010, 7: 59-64.

[4] balint a, schöning u. choosing probability distributions for stochastic local search and the role of make versus break[c]//international conference on theory and applications of satisfiability testing. berlin, heidelberg: springer berlin heidelberg, 2012: 16-29.

[5] xiang y, huang h, li m, et al. looking for novelty in search-based software product line testing[j]. ieee transactions on software engineering, 2022, 48(7): 2317-2338.