一句话：提出局部搜索算法 CAmpactor，将已有的两两覆盖数组压缩到更小规模，平均缩小约45%。
软件定制化需求催生了大量高度可配置系统，组合交互测试（CIT）是测试这类系统的有效手段，其中两两测试（t=2）应用最广且故障检测能力强。两两测试的核心问题是两两覆盖数组生成（PCAG），即在最小规模下生成两两覆盖数组（PCA），但现有最优 PCAG 算法面临严重的可扩展性挑战：难以有效处理大规模实例，导致生成的 PCA 规模偏大。为此，本文提出 CAmpactor——一种新颖高效的局部搜索算法，其目标不是从零生成 PCA，而是对给定 PCA 进行压缩，使其规模更小。作者在大量真实、公开的 PCAG 实例上开展实验，结果表明 CAmpactor 生成的 PCA 规模比现有最优 PCAG 算法构造的 PCA 小约 45%；同时，CAmpactor 能压缩多种不同 PCAG 算法产生的 PCA，验证了其通用性。
The increasing demand for software customization has led to the development of highly configurable systems. Combinatorial interaction testing (CIT) is an effective method for testing these types of systems. The ultimate goal of CIT is to generate a test suite of acceptable size, called a t-wise covering array (CA), where t is the testing strength. Pairwise testing (i.e., CIT with t=2) is recognized to be the most widely-used CIT technique and has strong fault detection capability. In pairwise testing, the most important problem is pairwise CA generation (PCAG), which is to generate a pairwise CA (PCA) of minimum size. However, existing state-of-the-art PCAG algorithms suffer from the severe scalability challenge; that is, they cannot tackle large-scale PCAG instances effectively, resulting in PCAs of large sizes. To alleviate this challenge, in this paper we propose CAmpactor, a novel and effective local search algorithm for compacting given PCAs into smaller sizes. Extensive experiments on a large number of real-world, public PCAG instances show that the sizes of CAmpactor's generated PCAs are around 45% smaller than the sizes of PCAs constructed by existing state-of-the-art PCAG algorithms, indicating its superiority. Also, our evaluation confirms the generality of CAmpactor, since CAmpactor can reduce the sizes of PCAs generated by a variety of PCAG algorithms.
@inproceedings{ZhaoL00LZH23,
title = {CAmpactor: A Novel and Effective Local Search Algorithm for Optimizing Pairwise Covering Arrays},
author = {Qiyuan Zhao and Chuan Luo and Shaowei Cai and Wei Wu and Jinkun Lin and Hongyu Zhang and Chunming Hu},
booktitle = {FSE},
year = {2023},
doi = {10.1145/3611643.3616284}
}