A Tuple-Oriented Sampling Method for Generating Small Pairwise Covering Arrays in Configurable Software Systems

Pairwise testing is the most commonly used combinatorial interaction testing (CIT) technique to verify highly configurable systems, aiming to select the minimum number of testing configurations to cover all valid pairwise combinations of option values. The core problem of pairwise testing is the pairwise covering array generation (PCAG) problem. Existing PCAG methods typically struggle to generate small-scale pairwise covering arrays (PCA) for instances with complex constraints, or they require excessive computational time. To address these limitations, we propose DivSampCA, which employs a tuple-oriented adaptive sampling technique to enhance the diversity of the sampled configurations. Moreover, DivSampCA employs a novel full coverage strategy to ensure that the remaining uncovered pairwise tuples are covered with as few configurations as possible. We validate our method on 121 publicly available configurable system instances, and the experimental results show that DivSampCA achieves the smallest covering array in 71% of the instances, which is on average 15.54% smaller than that of other algorithms. Moreover, it is the fastest in 65% of the instances, reducing the average time by 42.36%. These results indicate that DivSampCA can generate smaller covering arrays in a shorter time and represents a significant advancement in solving the PCAG problem.