ALLPAIRS

By James Bach, james@satisfice.com <mailto:james@satisfice.com>, www.satisfice.com

Installation Instructions
Unzip everything into a directory. That’s all.

How to Use 
Allpairs.pl is a Perl script that constructs a reasonably small set of test cases that include all pairings of each value of each of a set of parameters. Actually, I don’t know if I’m saying that right. Let me show you. If you have two parameters you want to cover in a set of tests, say, printer and operating system, they might look something like this:

Operating System
Win98
Win2K
WinXP

Printer
HP 4050
HP 4100

To test all the pairings, the test cases would look like this:

CASE	OS	Printer	
1	Win98	HP 4050	
2	Win98	HP 4100	
3	Win2K	HP 4050	
4	Win2K	HP 4100	
5	WinXP	HP 4050	
6	WinXP	HP 4100	

In the case of two parameters, all pairs is also all combinations. But look what happens when we add a third parameter:

Duplex Print
Y
N

CASE	OS	Printer	Duplex	
1	Win98	HP 4050	Y	
2	Win98	HP 4100	Y	
3	Win2K	HP 4050	Y	
4	Win2K	HP 4100	Y	
5	WinXP	HP 4050	Y	
6	WinXP	HP 4100	Y	
7	Win98	HP 4050	N	
8	Win98	HP 4100	N	
9	Win2K	HP 4050	N	
10	Win2K	HP 4100	N	
11	WinXP	HP 4050	N	
12	WinXP	HP 4100	N	

All combinations of each of these parameters creates twelve test cases. But what if all we really need is a set of test cases that guarantee that each value of each parameter is paired in at least one case? Then we can get away with fewer cases. We’re back down to six, in fact:

CASE	OS	Printer	Duplex	
1	Win98	HP 4050	Y	
2	Win98	HP 4100	N	
3	Win2K	HP 4050	N	
4	Win2K	HP 4100	Y	
5	WinXP	HP 4050	Y	
6	WinXP	HP 4100	N	

If a bug will be triggered when the value of any one of the three parameters is paired with a value of either of the other two, then we’ll catch it with this set of test cases. If a bug occurs only when three specific values are tried together, this set of cases will not necessarily catch it, but at least we’ve achieved all pairs.

All pairs coverage is a lot easier to achieve than all combinations. For instance, if you want to test with ten parameters of 26 values each, all combinations leads to 141,167,095,653,376 test cases. Allpairs does it in 1094 cases.

To use Allpairs, prepare a tab-delimited table of parameters that you'd like to permute. The easiest way to do this is with Excel:

Operating System	Printer	Duplex	
Win98	HP 4050	Y	
Win2K	HP 4100	N	
WinXP			

Then copy the excel table and paste into a text file (let’s say you name it vars.txt). Run the Allpairs program from a DOS command-line like this:

ALLPAIRS VARS.TXT > TESTCASES.TXT

If you have Perl installed, you can run the script instead like so:

PERL ALLPAIRS.PL VARS.TXT > TESTCASES.TXT

The content of testcases.txt is suitable for pasting into Excel. It will look like this:

The first part of the output is the test cases. The “pairings”column reports the number of unique pairings that Allpairs managed to find.

The second part of the output helps you see how the pairings were done. It lists each pair, shows how many times that pair appears in the test case table, and lists the specific test case or cases in which those pairings occur.

Don’t Care Values: “~”

Sometimes, the value of a particular cell in a test case table doesn’t matter, because all of its pairings have already been achieved. In that case the value chosen is the one that has been paired the fewest times relatively to the other cells in the test case. Also, the cell is marked with a “~” symbol to alert you that you can substitute any other value for the one ALLPAIRS chose and still achieve your all-pairs coverage goal.

Example

Included in the ZIP file is a real-life example of testing printing in Microsoft Word. PRINTING.TXT is the data file. The PRINTING.XLS shows the results (I formatted it by hand to make it more readable).

Notes

Test Design
When permuting parameters, the more parameters you choose, the more work you’ll have to do for each test case. So, just choose those parameters that might reasonably interact with each other. Furthermore, think about the importance of the resulting bug. If a problem only happens when two values of two obscure parameters are used together, the result may be a bug that no one will care to fix.

When a value is “don’t care” (marked by a tilde) choose a value which either maximizes the probability of a failure, or maximizes the impact of the failure, should one occur. 

Other Tools
My version does not produce an optimal solution, but it’s good enough that I’ve lost interest in trying to discover the optimal solution myself. Consider the case of 10 parameters with 10 values each. Allpairs will do it in 177 cases. The smallest number of test cases possible is somewhere between 100 and 177. I suspect it’s something down around 130. But compared to the alternative of 10 billion test cases to achieve all permutations, 177 is not too bad.

Telcordia Technologies (<http://www.argreenhouse.com>) has a web-based tool that does a somewhat better job than Allpairs. For instance, with 40 parameters of three values each, their tool can cover all pairs with 21 test cases. Allpairs requires 29. However, their tool costs $6000 a seat. Compare that to FREE…