A Scalable t-wise Coverage Estimator: Algorithms and Applications
(2024) IEEE Transactions on Software Engineering — Vol. 50, n° 8, p. 2021-2039 (2024)
Files
main.pdf
accepted
Open Access - Adobe PDF
- 641.9 KB
Details
- Authors
- 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 U and returns an estimate of the t-wise coverage of U that is guaranteed to be within (1 ± ε)-factor of the ground truth with probability at least 1 − δ for a given tolerance parameter ε and a confidence parameter δ . 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 ≥ 1 − δ for a given tolerance parameter ε and a confidence parameter δ . 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.
- Affiliations
Citations
Baranov, E., Sourav Chakraborty, Legay, A., Kuldeep S. Meel, & N. Variyam Vinodchandran. (2024). A Scalable t-wise Coverage Estimator: Algorithms and Applications. IEEE Transactions on Software Engineering, 50(8), 2021-2039. https://doi.org/10.1109/TSE.2024.3419919 (Original work published 2024)