摘要 : 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 constrain... 展开 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, $\mathsf{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\pm\varepsilon)$-factor of the ground truth with probability at least $1-\delta$ for a given tolerance parameter $\varepsilon$ and a confidence parameter $\delta$. A scalable framework ${\mathsf{ApproxMaxCov}}$ for a given formula ${\mathsf{F}}$ outputs an approximation which is guaranteed to be within $(1\pm\varepsilon)$ factor of the maximum achievable $t$-wise coverage under ${\mathsf{F}}$, with probability $\geq 1-\delta$ for a given tolerance parameter $\varepsilon$ and a confidence parameter $\delta$. Our comprehensive evaluation demonstrates that $\mathsf{ApproxCov}$ and ${\mathsf{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 $\mathsf{ApproxCov}$, ${\mathsf{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$. 收起