High-level Constraint Support For Combinatorial Testing

Abstract

Combinatorial testing constructs test cases by combining different input parameter values based on some effective combinatorial strategy. This software testing approach has displayed very promising attributes and is rapidly gaining popularity in recent years. However, existing work does not provide adequate support for constraint handling. Constraints are often specified as part of an input parameter model and they may be due to several reasons such as incompatibility between certain hardware and software components. A test generation algorithm needs to take these constraints into account during the test generation process to exclude combinations that are invalid from the domain semantics. In this thesis, we describe a general approach to handling constraints for combinatorial testing. Our approach includes a formal notation that allows the user to specify constraints at a higher level of abstraction. We discuss how to deal with the problem of "future conflicts", which arises when a selected value satisfies all the constraints at one point in the test generation process but fails to satisfy some constraints in the future. Our approach can be combined with different combinatorial test generation algorithms, and we demonstrate this by showing how to extend an existing combinatorial test generation algorithm, called In-Parameter-Order-General (IPOG), to handle constraints. We describe a Java based combinatorial testing tool developed in the course of this research work called FireEye, which implements an extended version of IPOG that supports constraint handling, and report some experimental results that demonstrate the effectiveness of our approach.