A Scalable t-Wise Coverage Estimator: Algorithms and Applications
- 27 June 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. 50 (8) , 2021-2039
Abstract
Owing to the pervasiveness of software in our modern lives, software systems have evolved to be highly configurable. Combinatorial testing has emerged as a dominant paradigm for testing highly configurable systems. Often constraints are employed to define the environments where a given system is expected to work. Therefore, there has been a sustained interest in designing constraint-based test suite generation techniques. A significant goal of test suite generation techniques is to achieve t -wise coverage for higher values of t . Therefore, designing scalable techniques that can estimate t -wise coverage for a given set of tests and/or the estimation of maximum achievable t -wise coverage under a given set of constraints is of crucial importance. The existing estimation techniques face significant scalability hurdles. We designed scalable algorithms with mathematical guarantees to estimate (i) t-wise coverage for a given set of tests, and (ii) maximum t-wise coverage for a given set of constraints. In particular, ApproxCov takes in a test set $\mathcal{U}$ and returns an estimate of the t-wise coverage of $\mathcal{U}$ that is guaranteed to be within (1 ± ε)-factor of the ground truth with probability at least $1 - \delta$ for a given tolerance parameter ε and a confidence parameter $\delta$ . A scalable framework ApproxMaxCov for a given formula F outputs an approximation which is guaranteed to be within (1 ± ε) factor of the maximum achievable t-wise coverage under F, with probability $\ge 1 - \delta$ for a given tolerance parameter ε and a confidence parameter $\delta$ . Our comprehensive evaluation demonstrates that ApproxCov and ApproxMaxCov can handle benchmarks that are beyond the reach of current state-of-the-art approaches. In this paper we present proofs of correctness of ApproxCov, ApproxMaxCov, and of their generalizations.We show how the algorithms can improve the scalability of a test suite generator while maintaining its effectiveness. In addition, we compare several test suite generators on different feature combination sizes t.
Keywords
This publication has 67 references indexed in Scilit:
- Test scenario generation for feature-based context-oriented software systemsJournal of Systems and Software, 2022
- Tinted, Detached, and Lazy CNF-XOR Solving and Its Applications to Counting and Sampling2020
- $\mathsf {WAPS}$ : Weighted and Projected Sampling2019
- Assessing fine-grained feature dependenciesInformation and Software Technology, 2016
- Learning Combinatorial Interaction Test Generation Strategies Using Hyperheuristic Search2015
- A Formal Logic Approach to Constrained Combinatorial TestingJournal of Automated Reasoning, 2010
- A density‐based greedy algorithm for higher strength covering arraysSoftware Testing, Verification and Reliability, 2008
- IPOG/IPOG‐D: efficient test generation for multi‐way combinatorial testingSoftware Testing, Verification and Reliability, 2007
- Subtractive reductions and complete problems for counting complexity classesTheoretical Computer Science, 2005
- Upper bounds for covering arrays by tabu searchDiscrete Applied Mathematics, 2004