软件产品线（Software Product Line, SPL）是一种有效的软件开发方法，它在满足软件产品之间共性的基础上，可以灵活地根据用户需求实现软件定制。

图1 软件产品线示意图[4]

自动化测试和自动化配置是软件产品线研究的两个重要课题。针对以上两个课题，华南理工大学智能算法研究中心联合英国伯明翰大学、中山大学等单位的专家学者，进行了一系列研究[1-4]，相关成果先后发表/录用在软件工程领域以及进化计算领域的旗舰期刊上。下面重点介绍我们在软件产品线自动化测试方面的最新研究成果[1]，该工作已被IEEE Transactions on Software Engineering正式录用。

众所周知，测试是确保软件可靠性的有效手段。软件产品线测试是一项极具挑战的工作。由于软件产品线所包含的软件产品数量巨大，逐一测试所有软件产品几乎不可能。因此，研究人员不断寻求既能减少测试用例个数，又能保证一定错误发现率的软件产品线测试方法。其中，t组合测试是一类重要的测试方法，它基于以下事实：软件产品线的错误通常由t（大于等于2）个组件之间的交互触发。然而，t组合测试仅适用于小规模的软件产品线以及较小t值（小于等于3）的情况。对于现实中的大规模软件产品线或较大t值的情况，t组合测试难以扩展。

为规避t组合测试扩展性差的问题，基于相似性的软件产品线测试应运而生。该测试方法一般采用搜索算法，生成一组相似性尽可能小（或差异性尽可能大）的测试用例，从而尽可能地覆盖更多的t组合。Henard等人[5]的研究结果表明，基于相似性的软件产品线测试是t组合测试的一种有效替代。它既可取得较高的t组合覆盖率，又可避免t组合测试扩展性差的问题。近年来，基于相似性的软件产品线测试逐步发展成为一个独立的研究分支[6]。

然而，基于相似性的软件产品线测试的基本原理尚缺乏强有力的解释。研究中心近期的工作[1]，从统计学角度出发，深入地阐明了基于相似性的软件产品线测试的基本原理；与此同时，首次引入Novelty Search (NS)算法生成一组多样化的测试用例。具体地研究工作包括：

（1）运用相关性分析揭示相似性指标与t组合覆盖率之间的内在关联。相关性分析结果表明：相似性指标，如Henard等人[5]提出的基于相似性的适应值和NS算法所采用的新颖得分(Novelty Score)等，与t组合覆盖率之间是呈显著正相关的。图2清晰地表明，t组合覆盖率随着新颖得分的增大而呈上升趋势。

图2 新颖得分与覆盖率之间的正相关关系[1]

该发现可以很好地解释基于相似性的软件产品线测试为何有效：运用搜索算法优化相似性指标，提升测试用例差异性的同时，可间接地提高t组合覆盖率。

（2）证明了新颖得分是Henard等人提出的适应值[5]的推广。新颖得分和Henard等人提出的适应值均为相似性指标，但二者提出的年代、背景和目的均不相同。经公式推导，我们惊奇地发现，两个看似不相关的指标之间是存在内在联系的： Henard等人的适应值是新颖得分的一个特例。换言之，新颖得分有效地推广了Henard等人的适应值。上述发现很有意义，因为它表明这两个相似性指标是内在统一的。鉴于新颖得分的普适性，在实际应用中，我们推荐使用新颖得分作为相似性指标。

（3）从概念和实验上，充分论证了NS（见图3）是基于相似性的软件产品线测试的有效工具。

图3 NS算法示意图[1]

首先，NS算法采用外部档案维护在搜索过程中找到的一组多样化解集，该解集正好可作为软件产品线的测试集；其次，NS算法的目的是生成一组多样化的解集，这正好符合基于相似性的软件产品线测试的目标；最后，NS算法具有很好的理论性质[7-8]，这些性质便于对算法的性能进行分析。实验上，我们将NS算法与三个主流算法(Unpredictable[5], GA[5]和SamplingDown[6])进行了比较。Friedman 检验结果见图4。

图4 Friedman检验得到的各算法平均排名

如图4所示，NS算法的整体性能排名第一，其次是Henard等人[5]的GA算法。进一步地，我们还计算了NS与各算法比较时的效应值（effect size, ES），结果见表1。可以发现，与其它三个算法相比，NS算法性能具有大幅度提升！

表1 NS与各算法效应值的比较

上述实验结果表明，就算法的整体性能而言，NS最优，其次为GA，再次为SamplingDown，最后为Unpredictable。事实上，NS优于GA并非偶然，而是可以根据相关性分析结果进行合理解释。NS和GA采用的相似性指标分别为新颖得分和基于相似性的适应值[5]。相关性分析表明，前者与t组合覆盖率之间的正相关强度比后者更强。这不难理解为何NS的性能要优于GA。本实验所采用的程序已完全公开，见https://github.com/gzhuxiangyi/TSE_NS。

最后，华南理工大学智能算法研究中心，长期致力于将人工智能算法应用在解决软件工程领域的典型问题上，并已取得一些初步成效。未来，我们将继续在这个领域进行探索，以期为软件工程的学科建设和发展作出积极贡献。

参考文献

1. Yi Xiang, Han Huang, Miqing Li, Sizhe Li, and Xiaowei Yang. Looking For Novelty in Search-based Software Product Line Testing, IEEE Transactions on Software Engineering, 2021, DOI: 10.1109/TSE.2021.3057853

2. Yi Xiang, Yuren Zhou, Zibin Zheng, Miqing Li, Configuring Software Product Lines by Combining Many-objective Optimization and SAT Solvers, ACM Transactions on Software Engineering and Methodology, 2018, 26(4): 14.1-14.46.

3. Yi Xiang, Xiaowei Yang, Yuren Zhou, Han Huang. Enhancing Decomposition-based Algorithms by Estimation of Distribution for Constrained Optimal Software Product Selection, IEEE Transactions on Evolutionary Computation, 2020, 24(2): 245-259.

4. Yi Xiang, Xiaowei Yang, Yuren Zhou, Zibin Zheng, Miqing Li, Han Huang. Going deeper with optimal software products selection using many-objective optimization and satisfiability solvers. Empirical Software Engineering, 2020, 25(1): 591-626.

5. C. Henard, M. Papadakis, G. Perrouin, J. Klein, P. Heymans, Y. Le Traon, Bypassing the Combinatorial Explosion: Using Similarity to Generate and Prioritize T-Wise Test Configurations for Software Product Lines, IEEE Transactions on Software Engineering, 2014, 40(7): 650–670.

6. M. Al-Hajjaji, T. Thüm, M. Lochau, J. Meinicke, G. Saake, Effective Product-Line Testing Using Similarity-Based Product Prioritization, Software and Systems Modeling, 2019, 18(10): 1–23.

7. S. Doncieux, A. Laflaqui`ere, and A. Coninx, Novelty Search: a Theoretical Perspective, Genetic and Evolutionary Computation Conference (GECCO’19), 2019, 99–106.

8. S. Doncieux, G. Paolo, A. Laflaqui`ere, and A. Coninx, Novelty Search Makes Evolvability Inevitable, Genetic and Evolutionary Computation Conference (GECCO’20), 2020, 85–93.

总编：黄翰

文字：向毅

图片：向毅、袁中锦

校稿：黄翰、袁中锦、奚宇霖

时间：2021年3月4日