一句话：提出基于采样的 SamplingCA，用少量测试用例覆盖有效成对元组，显著缩小成对覆盖数组并加速生成。
组合交互测试是测试高度可配置系统的有效范式，其中成对测试（t=2）应用最广。其核心问题是成对覆盖数组生成（PCAG）：在硬约束下构造最小的 2-wise 覆盖数组。PCAG 是困难的组合优化问题，现有算法在大型实例上可扩展性差，生成覆盖数组耗时长，影响测试效率与效果。本文提出 SamplingCA，一种基于采样的方法：先利用采样技术获得一个小测试集，尽可能多地覆盖有效成对元组，再补充少量测试用例覆盖剩余有效元组。在 125 个公开 PCAG 实例上的实验表明，SamplingCA 生成的成对覆盖数组显著小于当前最优方法，且运行速度快一到两个数量级，能够缓解可扩展性问题并推进 PCAG 求解的先进水平。
Combinatorial interaction testing (CIT) is an effective paradigm for testing highly configurable systems, and its goal is to generate a t-wise covering array (CA) as a test suite, where t is the strength of testing. It is recognized that pairwise testing (i.e., CIT with t=2) is the most common CIT technique, and has high fault detection capability in practice. The problem of pairwise CA generation (PCAG), which is a core problem in pairwise testing, aims at generating a pairwise CA (i.e., 2-wise CA) of minimum size, subject to hard constraints. The PCAG problem is a hard combinatorial optimization problem, which urgently requires practical methods for generating pairwise CAs (PCAs) of small sizes. However, existing PCAG algorithms suffer from the severe scalability issue; that is, when solving large-scale PCAG instances, existing state-of-the-art PCAG algorithms usually cost a fairly long time to generate large PCAs, which would make the testing of highly configurable systems both ineffective and inefficient. In this paper, we propose a novel and effective sampling-based approach dubbed SamplingCA for solving the PCAG problem. SamplingCA first utilizes sampling techniques to obtain a small test suite that covers valid pairwise tuples as many as possible, and then adds a few more test cases into the test suite to ensure that all valid pairwise tuples are covered. Extensive experiments on 125 public PCAG instances show that our approach can generate much smaller PCAs than its state-of-the-art competitors, indicating the effectiveness of SamplingCA. Also, our experiments show that SamplingCA runs one to two orders of magnitude faster than its competitors, demonstrating the efficiency of SamplingCA. Our results confirm that SamplingCA is able to address the scalability issue and considerably pushes forward the state of the art in PCAG solving.
DOI 原文 ·
@inproceedings{paperbot7142,
title = {SamplingCA: effective and efficient sampling-based pairwise testing for highly configurable software systems},
author = {Chuan Luo and Qiyuan Zhao and Shaowei Cai and Hongyu Zhang and Chunming Hu},
booktitle = {FSE},
year = {2022},
doi = {10.1145/3540250.3549155}
}