Constructing Interaction Test Suites for Highly-Configurable Systems in the Presence of Constraints: A Greedy Approach

By Myra B. Cohen, Matthew B. Dwyer, Jiangfan Shi. IEEE Transactions on Software Engineering, 2008

332 citations recorded by the source corpus.

Researchers have explored the application of combinatorial interaction testing (CIT) methods to construct samples to drive systematic testing of software system configurations. Applying CIT to highly-configurable software systems is complicated by the fact that, in many such systems, there are constraints between specific configuration parameters that render certain combinations invalid. Many CIT algorithms lack a mechanism to avoid these. In recent work, automated constraint solving methods have been combined with search-based CIT construction methods to address the constraint problem with promising results. However, these techniques can incur a non-trivial overhead. In this paper, we build upon our previous work to develop a family of greedy CIT sample generation algorithms that exploit calculations made by modern Boolean satisfiability (SAT) solvers to prune the search space of the CIT problem. We perform a comparative evaluation of the cost-effectiveness of these algorithms on four real-world highly-configurable software systems and on a population of synthetic examples that share the characteristics of those systems. In combination our techniques reduce the cost of CIT in the presence of constraints to 30 percent of the cost of widely-used unconstrained CIT methods without sacrificing the quality of the solutions.

Subfields: Information Systems, Software

View Paper: https://www.semanticscholar.org/paper/ee7ab201ca6bf8719b36bc93eb37e32e625fb749

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Systems

In Software

Citations in the corpus

Regression testing minimization, selection and prioritization: a survey (2012, methodology): “For example, the greedy approach aims to find, one by one, the ‘next’ test case that will most increase the k-way interaction coverage [129, 130], which resembles the greedy approach to test case prioritization.”
A survey of combinatorial testing (2011, methodology): “2007], presented a general constraint representation and a technique based on the existing constraint handling techniques [Cohen et al. 2007b; Fouché et al. 2007; Cohen et al. 2008].”
An orchestrated survey of methodologies for automated software test case generation (2013, methodology): “…configurations, and if we model the entire preference space this becomes intractable; the literature has reported the optimization configuration space of GCC (the GNU Compiler Collection) (FreeSWF, 2012), an open source widely used compiler framework, is in the order of 10 61 (Cohen et al., 2008).”
Search Based Software Engineering: A Comprehensive Analysis and Review of Trends Techniques and Applications (2009, methodology): “[124] 2008 Combinatorial interaction testing generate the smallest subset of configuration for t-way coverage Array Greedy Real”