# Reference Request: Application of Block Designs to Software Testing

I've started looking at incidence structures and combinatorial designs (possible motivation: to upper-bound some structures in generalized self-assembly), and the Wikipedia article makes the following interesting-yet-unexplained statement: block designs have application to software testing. (The Wikipedia page with the claim is here).

My google-fu doesn't pick up a good reference for this application. Can anyone give me a lead?

## 3 Answers

Suppose you have some software which includes a list of n variables s1,s2,...,sn and suppose each of these variables are able to take on a range of values. Now suppose you want to test the program for 2-way interactions, that is, you want to test the program runs correctly for every pair of variables si and sj and every possible value that these variables can take.

To do this by a brute-force -- by processing each pair i and j one-by-one, then testing each allowable value of si and sj (while picking the others arbitrarily) -- would require testing a enormous number of cases.

But, we can test for several 2-way interactions in a single test. For example, if we have three variables s1, s2 and s3, and we test when s1=1, s2=2 and s3=0, then we have tested three possible 2-way interactions simultaneously.

We can design a test-suite for the program based on a covering array -- the columns represent the variables and the rows represent the specific test to be performed (so fewer rows is better). In a strength 2 covering array, within any two columns i and j, there exists every possible pair of the variables si and sj. There are higher strength covering arrays which can test for t-way interactions (but usually interactions are a result of only a few components).

Sets of mutually orthogonal Latin squares (and various other block designs) form particularly efficient covering arrays.

• Thanks, same comment as above - wish I could accept more than one answer. – Aaron Sterling Sep 3 '10 at 11:41