<p>See <a href="http://scholar.google.com/scholar?cluster=16591915454227907953">Orthogonal Latin squares: an application of experiment design to compiler testing</a>.</p>

CC BY-SA 2.5
2010-09-03T11:41:16.667Z
Thanks, same comment as above - wish I could accept more than one answer.
Aaron Sterling
CC BY-SA 2.5
2010-09-03T08:56:23.953Z
2010-09-03T08:56:23.953Z
Radu GRIGore
<p>Check these references:</p>

<p><a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=536462">Cohen, D.M.;   Dalal, S.R.;   Parelius, J.;   Patton, G.C., The combinatorial design approach to automatic test generation</a>
<a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=536462"></a></p>

<p><a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=605761">Cohen, D.M.;   Dalal, S.R.;   Fredman, M.L.;   Patton, G.C.;, The AETG system: an approach to testing based on combinatorial design</a>
<a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=605761"></a></p>

CC BY-SA 2.5
2010-09-03T11:09:40.527Z
2010-09-03T11:09:40.527Z
Mohammad Al-Turkistany
<p>Suppose you have some software which includes a list of n variables s<sub>1</sub>,s<sub>2</sub>,...,s<sub>n</sub> 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 s<sub>i</sub> and s<sub>j</sub> and every possible value that these variables can take.</p>

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

<p>But, we can test for several 2-way interactions in a single test.  For example, if we have three variables s<sub>1</sub>, s<sub>2</sub> and s<sub>3</sub>, and we test when s<sub>1</sub>=1, s<sub>2</sub>=2 and s<sub>3</sub>=0, then we have tested three possible 2-way interactions simultaneously.</p>

<p>We can design a test-suite for the program based on a <a href="http://math.nist.gov/coveringarrays/coveringarray.html">covering array</a> -- 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 s<sub>i</sub> and s<sub>j</sub>.  There are higher strength covering arrays which can test for t-way interactions (but usually interactions are a result of only a few components).</p>

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

CC BY-SA 2.5
2010-09-03T11:04:11.733Z
2010-09-03T11:04:11.733Z
Douglas S. Stones
<p>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 <a href="http://en.wikipedia.org/wiki/Block_design">here</a>).</p>

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

<reference-request>
Reference Request: Application of Block Designs to Software Testing
Aaron Sterling
# Reference Request: Application of Block Designs to Software Testing

(Asked by: username_0 on 2010-09-03)

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](http://en.wikipedia.org/wiki/Block_design)).

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

**Tags:** reference-request

---

## 3 answers

### Answer by username_3 on 2010-09-03. Score: 8 | Accepted answer

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](http://math.nist.gov/coveringarrays/coveringarray.html) -- 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.


---

### Answer by username_1 on 2010-09-03. Score: 6

See [Orthogonal Latin squares: an application of experiment design to compiler testing](http://scholar.google.com/scholar?cluster=16591915454227907953).

> **Comments:**
> **username_0**: Thanks, same comment as above - wish I could accept more than one answer.  

---

### Answer by username_2 on 2010-09-03. Score: 5

Check these references:

[Cohen, D.M.; Dalal, S.R.; Parelius, J.; Patton, G.C., The combinatorial design approach to automatic test generation](http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=536462)

[Cohen, D.M.; Dalal, S.R.; Fredman, M.L.; Patton, G.C.;, The AETG system: an approach to testing based on combinatorial design](http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=605761)


---

