一句话：提出高效评分计算方法并集成梯度下降，构造 FastCA，在覆盖数组大小与运行时间上显著提升组合测试生成效率。
组合交互测试（CIT）是检测高可配置软件系统故障的常用手段，其核心是生成小的 t-way 覆盖数组。针对约束覆盖数组生成（CCAG）问题，已有元启发式算法通常需要很长时间才能得到高质量解，主要瓶颈在于评分计算过程。本文提出一种更高效的评分计算方法，并将其应用于当前先进算法 TCA，显著提升效率；该方法还使原先因评分代价过高而不可行的算法思想变得可用。作者进一步集成梯度下降搜索步骤，形成新算法 FastCA。在大量真实世界与合成基准上的实验表明，FastCA 在覆盖数组大小和运行时间两方面均显著优于 CCAG 的最先进算法。
Combinatorial interaction testing (CIT) is a popular approach to detecting faults in highly configurable software systems. The core task of CIT is to generate a small test suite called a t-way covering array (CA), where t is the covering strength. Many meta-heuristic algorithms have been proposed to solve the constrained covering array generating (CCAG) problem. A major drawback of existing algorithms is that they usually need considerable time to obtain a good-quality solution, which hinders the wider applications of such algorithms. We observe that the high time consumption of existing meta-heuristic algorithms for CCAG is mainly due to the procedure of score computation. In this work, we propose a much more efficient method for score computation. The score computation method is applied to a state-of-the-art algorithm TCA, showing significant improvements. The new score computation method opens a way to utilize algorithmic ideas relying on scores which were not affordable previously. We integrate a gradient descent search step to further improve the algorithm, leading to a new algorithm called FastCA. Experiments on a broad range of real-world benchmarks and synthetic benchmarks show that, FastCA significantly outperforms state-of-the-art algorithms for CCAG algorithms, in terms of both the size of obtained covering array and the run time.
DOI 原文 ·
@inproceedings{paperbot5155,
title = {Towards more efficient meta-heuristic algorithms for combinatorial test generation},
author = {Jinkun Lin and Shaowei Cai and Chuan Luo and Qingwei Lin and Hongyu Zhang},
booktitle = {FSE},
year = {2019},
doi = {10.1145/3338906.3338914}
}