8
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

See Orthogonal Latin squares: an application of experiment design to compiler testing.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.