The test suite generation problem: Optimal instances and their implications

AbstractIn the test suite generation (TSG) problem for software systems, I is a set of n input parameters where each I∈I has κ(I) data values, and O is a collection of subsets of I where the interactions of the parameters in each O∈O are thought to affect the outcome of the system. A test case for (I,O,κ) is an n-tuple (t1,t2,…,tn) that specifies the value of each input parameter in I. The goal is to generate a smallest-sized test suite (i.e., a set of test cases) that covers all combinations of each O∈O. The decision version of TSG is known to be NP-complete.In this paper, we present new families of (I,O,κ) for which optimal test suites can be constructed efficiently. They differ from the ones already known by the way we characterize (I,O) and κ. We then use these instances to generate test suites for arbitrary software systems. When each O∈O has |O|=2, the sizes of the test suite are guaranteed to be at most ⌈log2n⌉×OPT, matching the current best bound for this problem. Our constructions utilize the structure of (I,O) and κ; consequently, the less “complex” (I,O) and κ are, the better are the bounds on the sizes of the test suites