Covering arrays for interaction software testing
by Charles Colbourn
Arizona State University
ABSTRACT
The US economy loses 59.5 billion dollars a year because of software
errors undetected by adequate software testing. The reasons for failure to test
software sufficiently are complex, and many are not amenable to mathematical
treatment. But some are. Suppose, for example, that you have a collection
of n software components, each having some finite number of states or
configurations that it can be in. Errors can arise from the improper
interaction among a subset of the components when they are in
certain configurations. When the number of components is large,
the possible assignments of configurations to components are simply too numerous
for us to test them all. We can argue that when errors arise, relatively few components are
"responsible" for the error. Then our objective is
simplified: We must test all t-way interactions for some small t.
When we abstract this requirement, our objective is to produce
a covering array. In this talk, we define covering arrays and relate them
to other combinatorial designs. We then describe some new computational and
combinatorial constructions for these arrays. The focus is on using elegant
mathematics in a real application.
Back to the
Discrete Mathematics and its Applications home page.