一句话：提出局部搜索算法 HSCA，通过多轮生成、动态优先级与变量分组，显著提升高强度覆盖数组生成效果。
高度可配置软件系统需要组合交互测试（CIT）来检验配置交互引发的故障，其中约束覆盖数组生成（CCAG）是核心问题。现有算法在低强度（2-wise、3-wise）CCAG 上有效，但求解 4-wise、5-wise 等高强度问题面临严峻挑战。本文提出局部搜索算法 HSCA，融合多轮覆盖数组生成机制、动态优先级分配技术和变量分组策略。在 35 个真实与合成实例上的实验表明，HSCA 生成的 4-wise 和 5-wise 覆盖数组显著小于现有最优算法，并分别成功求解 35 和 29 个实例，其中 11 和 15 个为现有算法无法求解的实例。结果显示 HSCA 能有效缓解高强度 CCAG 挑战。
Highly configurable software systems are crucial in practice to satisfy the rising demand for software customization, and combinatorial interaction testing (CIT) is an important methodology for testing such systems. Constrained covering array generation (CCAG), as the core problem in CIT, is to construct a$t$-wise covering array (CA) of minimum size, where$t$represents the testing strength. Extensive studies have demonstrated that high-strength CIT (e.g., 4-wise and 5-wise CIT) has stronger fault detection capability than low-strength CIT (i.e., 2-wise and 3-wise CIT), and there exist certain critical faults that can be disclosed through high-strength CIT. Although existing CCAG algorithm has exhibited effectiveness in solving the low-strength CCAG problem, they suffer the severe highstrength challenge when solving 4-wise and 5-wise CCAG, which urgently calls for effective solutions to solving 4-wise and 5 wise CCAG problems. To alleviate the high-strength challenge, we propose a novel and effective local search algorithm dubbed HSCA. Particularly, HSCA incorporates three new and powerful techniques, i.e., multi-round CA generation mechanism, dynamic priority assigning technique, and variable grouping strategy, to improve its performance. Extensive experiments on 35 real-world and synthetic instances demonstrate that HSCA can generate significantly smaller 4-wise and 5-wise CAs than existing state-of-the-art CCAG algorithms. More encouragingly, among all 35 instances, HSCA successfully builds 4-wise and 5-wise CAs for 35 and 29 instances, respectively, including 11 and 15 instances where existing CCAG algorithms fail. Our results indicate that HSCA can effectively mitigate the high-strength challenge.
DOI 原文 ·
@inproceedings{paperbot8721,
title = {Towards High-Strength Combinatorial Interaction Testing for Highly Configurable Software Systems},
author = {Chuan Luo and Shuangyu Lyu and Wei Wu and Hongyu Zhang and Dianhui Chu and Chunming Hu},
booktitle = {ICSE},
year = {2025},
doi = {10.1109/icse55347.2025.00113}
}