Combinatorial Designs for Software Interaction Testing
by
Charles J. Colbourn
Department of Computer Science and Engineering, Arizona State University

Testing software that is produced by combining numerous commercial off-the-shelf components poses challenging combinatorial problems. While individual components have typically been well tested in isolation, their interaction with other components typically has not. Yet complex systems with numerous components, each having many available implementations, cannot be tested exhaustively as a result of the combinatorial explosion of the number of systems that could in principle be composed from the available components. In the absence of information about erroneous interactions that might occur, software interaction testing proposes that tests be designed to ensure that, for every subset of t components, and for every available implementation of each component in this subset, there is at least one test in which these t components are instantiated by the chosen implementations. The combinatorial design that underlies such software interaction tests is the covering array, a natural generalization of orthogonal arrays. Numerous open problems on covering arrays are of interest; we focus on combinatorial and algorithmic questions concerning their construction.

PDF

Date received: October 14, 2005