Open Testware Reviews

ALLPAIRS Test Case Generation Tool

Copyright 2003 by Tejas Software Consulting - All rights reserved.

Contents

Overview -- Maturity -- Project activity -- Platforms -- Support -- Documentation -- Installation -- Implementation -- Performance -- Similar tools -- Limitations -- Observations

Overview

Reviewed: 2003-Jan-23
Version reviewed: 1.2, 2003-Jan-29
Maintainer: James Bach, Satisfice, Inc., james@satisfice.com
URL: http://satisfice.com/testmethod.shtml
Testingfaqs.org category: Test Design Tools
License: GNU GPL v2
User interface: command line

ALLPAIRS is a test design tool tailored for Windows but portable to a wide variety of platforms with a some minor tweaks to the script file. It automates the "all pairs" test design technique, which is a method of intelligently choosing a small number of combinations of values from a potentially astronomically large number of test cases. Common uses of this tool is testing combinations of software features to see if they interact, and trying to generate reasonable combinations of configuration options for configuration testing. Maybe "common" isn't the proper word - few testers seem to be aware of this technique. More people need to be aware of it.

ALLPAIRS is a bit on the frontier. It's a beta quality tool. You'll need to do some background reading beyond the documentation provided with the tool to understand how the technique works and to make sure you're applying it properly, but you don't need to understand the tool implementation to be able to construct the input for the tool and to use the output.

ALLPAIRS does have some notable limitations that are described in this report, though most can be easily worked around by users who are familiar with using scripting languages. ALLPAIRS is also not suitable for users who aren't comfortable with a command-line interface.

Full disclosure: I have known the author, James Bach, on a professional basis for several years.

Maturity

4 - Beta (on a scale of 1-5)

The tool is reported as working well according to a handful of people. Broader testing would be required for Production status.

Project activity

3 - Stable (on a scale of 1-5)

Before I shared my initial findings with the author, there had been no changes to the tool since December 2001. There are few visible users and no established community of support. There is still some work that could be done on the tool that would be more likely to get done if there were an active user community.

Platforms

Out of the box, ALLPAIRS works best on Microsoft Windows. But the code itself appears to be portable to most platforms that support Perl. These platforms include a very wide variety of operating systems including most Unix variants, MacOS, and Windows 3.1 and above. Users on non-Windows systems will likely need to remove the CTRL-M line endings from the allpairs.pl script and the sample data file, and may wish to make minor changes to allow executing the script directly. None of these changes require modifying the code. These changes are described in the Limitations section (item 3, 4, 8, and 9).

It does not need to be run on the same platform as the software under test. The Perl script interpreter must be installed as a prerequisite, unless you use the canned allpairs.exe binary on Windows. In any case, you will need a Perl interpreter if you want to modify the source code. You will need an application that can extract zip files to install the tool. No extra Perl libraries are required by ALLPAIRS.

Using a spreadsheet application to manage the data input and output is highly recommended. With some difficulty, you can use a text editor instead. Integration with spreadsheet programs is easy using copy/paste on Windows. On Windows NT I was able to copy from OpenOffice and Excel spreadsheets to text files with the proper tab-separated value format. I could not copy the output from a DOS shell window back into a spreadsheet without messing up the columns, but I could paste from a Cygwin shell or the Notepad application back into a spreadsheet. I could also import the tab-separated value files into either spreadsheet with several extra mouse clicks. On Linux  I could paste from OpenOffice into a shell, and I could paste from the Kate editor (but not several other methods I tried) back into OpenOffice. I could import and export the files on Linux. On MacOS X, I couldn't find a way to get tab-separated data into or out of AppleWorks.

There is no information on which configurations or Perl versions the program has been tested on. I ran it successfully (with exceptions noted above) on these configurations:

Support

There is no online bug tracking database for this tool. There is no official mailing list to discuss usage of the tool. There's a chance you could find interested parties on the agile-testing list or the software-testing list. Otherwise, contact the maintainer directly with queries about this tool.

Source code is included in the main distribution package. There is no public version control mechanism for the source code. There is a change log in the headers of allpairs.pl that lists version numbers but not dates. Previous versions of the tool are not available on the web site, only the most recent version.

ALLPAIRS produces diagnostic output every time you run it. These diagnostics provide statistics about all possible pairings, showing how many times each pairing appears in the tests and a cross-reference to the test cases.

There is no established commercial support for the tool, though Satisfice, Inc. or other consulting firms could likely be engaged to support and enhance the tool.

Documentation

The tool comes with a 4-page tutorial in richtext format. Note that the tables and images do not display properly in AbiWord 1.0.3, though the document looks fine in OpenOffice 1.0.1. The tutorial is somewhat Windows-focused, but it only takes minor finessing to apply it to other operating systems. The tutorial does a decent job of getting you started with ALLPAIRS. There's no formal definition of the user interface, however. The tutorial does not give any background information or references about the all-pairs technique.

Beyond what is provided with the tool, you can find some background information at http://aetgweb.argreenhouse.com/papers.html, which has papers, including several academic references, on the subject of the "Combinatorial Design Approach", which I assume is similar to or the same as the all-pairs technique. Dr. Madhav S. Phadke has a paper "Planning Efficient Software Tests" in a 1997 issue of Crosstalk that discusses the use of orthogonal arrays to design tests. Several references are included.

I hear that the book Lessons Learned in Software Testing discusses the all-pairs technique on pages 52-60. And
http://fit.c2.com/wiki.cgi?AllPairsExample discusses all-pairs, though it seems to assume that you're already familiar with some of the other context of the web site.

Installation

The tool is distributed in a zip file. The only installation required (aside from prerequisites mentioned in the Platforms section) is extracting the zip file. There is no directory structure in the zip file, so you should create a new directory/folder to contain the files. You may wish to modify your executable path or copy one or both of the ALLPAIRS programs to a directory in your path so that you don't have to type the full pathname to invoke the program.

Implementation

ALLPAIRS is implemented in a single script file, allpairs.pl, written in Perl. The script is a mere 304 non-comment source lines. Windows users may run the supplied "allpairs.exe" program to run ALLPAIRS without having Perl installed. The "use strict" feature is used in the script to enforce good programming constructs, but it does not have a "use warnings" call to help identify run-time problems.

There are no automated test cases included to test ALLPAIRS itself. However, there are three sample data sets with expected output in the tutorial that can serve as rudimentary regression tests.

Performance

Test design tools can require enormous amount of processing time, especially for large tasks. I found that ALLPAIRS completed in reasonable time for small and medium sized problems. I tested using data sets with the same number of values for each attribute, and an equal number of attributes and values (rows and columns in the input). Here's what I found on a 266 MHz machine running Cygwin / Windows 2000.

problem size
time (h:mm:ss)
3 x 3
 0:00:00.1
6 x 6
 0:00:02
9 x 9
 0:00:16
12 x 12
 0:01:27
15 x 15
 0:04:53
18 x 18
 0:14:31
21 x 21
 0:35:47
24 x 24
 1:25:18

I wasn't terribly scientific in my data gathering. I redirected the output to a file, because printing the output to a terminal window slowed down the script by as much as a factor of two. I used the perl script rather than the allpairs.exe executable. Oddly enough, ALLPAIRS was significantly slower on a 450 MHz Linux machine with more memory, sometimes by more than a factor of four. Tests on that same 450 MHz machine running Window NT were similar to the results in the chart above.

In case you're curious, the 24 x 24 problem yielded 1296 test cases. I think most ALLPAIRS runs will be smaller than 15 x 15, and given that you probably don't need to run the ALLPAIRS tool every time you execute your tests, performance shouldn't be an issue.

Similar tools

There is a Java implementation of an all-pairs tool by Cunningham & Cunningham that is based largely on the ALLPAIRS implementation. The code is licensed under the GNU GPL.

The AETG Web Service is a commercial web service from Telcordia Technologies that's available on a subscription basis. It seems to use an all-pairs approach. The ALLPAIRS tutorial cites an example where ALLPAIRS generated 29 tests and AETG generated only 21.

rdExpert is a commercial tool from Phadke Associates, Inc. that uses orthogonal arrays to design tests. Comparing rdExpert to ALLPAIRS shows an interesting interplay between the better optimization of the commercial tools and the fact that orthogonal arrays by their nature may require more tests than all-pairs. I used an evaluation copy of rdExpert 5.11.00. Using the example in the Performance section of this report, ALLPAIRS generated four tests for the 4 x 4 problem, as did rdExpert. For the 8 x 8 problem, ALLPAIRS generated 96 tests and rdExpert generated only 64. For a 9 x 9 problem, ALLPAIRS gave me 139 tests and rdExpert gave me 81. However, in the scenario given in the Observations section, ALLPAIRS generated 32 tests but rdExpert generated 64. The fact that this example didn't use equally balanced values for the attributes (which is almost always the case in the real world) may have a bearing on the different results here.

While the difference between ALLPAIRS and rdExpert varied by as much as a factor of two, keep in mind that any of these tools are drastically reducing the number of tests compared to an all-combinations approach. That's about 387 million possible combinations for the 9 x 9 case, reduced to only two or three digits.

Limitations

I ran across the issues below while evaluating ALLPAIRS. I did not attempt to thoroughly test the tool.
  1. There is no way to tell ALLPAIRS that some test combinations are impossible. It will assume that all test parameters can and must be paired with all others. This is discussed more thoroughly in the Observations section. The author has researched the possibility of fixing this but hasn't implemented the changes yet.
  2. ALLPAIRS is not heavily optimized to squeeze the number of tests as small as possible, as illustrated in the Similar tools section. There is probably no feasible algorithm to produce a perfectly optimized solution, but commercial tools tend to be better optimized.
  3. Allpairs.pl uses DOS-style line endings. This causes mysterious parse errors that prevent the script from running on Linux and Cygwin. The workaround is to use a filter to remove the CTRL-M characters from the file.
  4. The printing.txt file uses DOS-style line endings, which causes spurious CTRL-M characters to be embedded in the output on MacOS X and Linux. This can garble the output in some situations, such as when the output goes directly to a terminal window. Remove the CTRL-M characters to work around this problem.
  5. ALLPAIRS complains if there are extra tabs on the end of a line in the input file. The error message is confusing because you can't see that there's an extra tab there.
  6. If the header and all values in a column in the input are blank (an invalid input), ALLPAIRS aborts with an internal error, "Can't use an undefined value as an ARRAY reference at ./allpairs.pl line 444." 
  7. The usage message is far more than 24 lines long, which could make it unreadable on a standard-size terminal window that doesn't buffer the output. The bottom of the usage message looks like real ALLPAIRS output, but with the wrong data relative to the input data specified on the command line.
  8. The execute bits aren't set on allpairs.pl after you extract it from the zip file, which prevents you from directly invoking the script on Linux and MacOS X. You can either call the perl interpreter directly or set the execute bits yourself.
  9. There is no "#!/usr/bin/perl" line at the beginning of allpairs.pl. This prevents you from invoking the script directly on Linux, MacOS X, and Cygwin. You can call the perl interpreter directly or add this line to the script yourself.  If there were a "#!" line, you still might have to modify it to match the location where Perl is installed on your system.
  10. Using an input file containing one tab and a newline character on Cygwin / Windows 2000 (an invalid input), I got this error intermittently: "Can't use an undefined value as an ARRAY reference at ./allpairs.pl line 400." This is hard to reproduce.
  11. If I run the tool like this from a DOS window on Windows NT 4.0: "allpairs.pl printing.txt > printing.out", the output file is empty. This is a limitation of Windows NT (but not newer versions of Windows). You can call the Perl interpreter directly to work around this: "perl allpairs.pl printing.txt > printing.out".
  12. When I run ALLPAIRS  in a KDE konsole window on Linux and ALLPAIRS prints an error message that includes a row from the data file, the row is truncated at the end of the first screen line. This appears to be a limitation of konsole's ability to wrap long lines. To work around, pipe the output to less or use an xterm.
I found the following issues while reviewing ALLPAIRS version 1.01. The author addressed these issues during the course of the review and they are fixed in version 1.2.

Observations

ALLPAIRS uses the all-pairs technique to design test cases. Like most test design tools, it won't implement your tests for you. What you get is a list of attribute combinations that you can use for either manual testing or as a specification for developing automated tests. The tool is applicable for any level of testing from unit to acceptance testing, and any kind of application domain except for some aspects of safety-critical products.

The all-pairs technique is very similar to the orthogonal array technique, and in fact the two are often confused with each other. All-pairs is likely to produce fewer test cases than the orthogonal array technique. Using orthogonal arrays allows for some sophisticated failure analysis that you can't do with all-pairs, but few testers are likely to need this analysis for their first use of either of these techniques.

Suppose you need to do configuration testing for a web application. You first need to do equivalence partitioning to determine the input to feed to ALLPAIRS. Let's say you need to make sure that people using Linux, MacOS, Windows ME, and Windows XP can use the application (you'll only test one configuration of each, or else you'd need to make the list longer). You want to test using five different web browser versions, three display sizes, three color depths, and six localized languages. Your configuration smoke test takes an hour to run. Multiplying all these parameters together gives 1080 unique combinations - that's 1080 test hours.

But all you really wanted was to make sure that you test each browser with each operating system, test each language with each display size, etc. Perhaps it's not important what the screen size is when you run Mozilla on Linux. Perhaps it's not important whether you try each language specifically with IE on Windows XP, as long as you try each language with IE somewhere, and you test each language with Windows XP using some browser. If all you care about is that your tests make sure each parameter is paired with each other parameter at least once, then the ALLPAIRS tool can reduce the 1080 combinations to only 32 - less than a week of testing.

If you really do need to have more than pair-wise coverage, reducing your test suite using an all-pairs tool will introduce too much risk that you will miss bugs that are only found with certain combinations of three or more test parameters. But if business requirements in our example dictate that you don't have more than a week to test anyway, then the all-pairs technique can maximize the chance that you'll find bugs with the limited resources that you have.

Consider that your test parameters might have some impossible combinations, such as Internet Explorer and Linux. There's no way to tell ALLPAIRS that certain combinations are impossible, and after ALLPAIRS has done its work, you can't simply remove or arbitrarily modify a test case that has an impossible pairing, because the test probably has other pairings that are unique to that test. Perhaps a workaround would be to duplicate the impossible test case and then change one of the troublesome test parameters on one version of the test so the test is feasible, and change the other troublesome parameter on the second version. That should preserve the other pairings in the test. For example, if you have a test case with the values "Linux, IE, 800x600, 256 colors, Spanish" and it turns out that neither Linux nor IE are "don't care" values, you could transform it to these two feasible test combinations: "Linux,  Mozilla, 256 colors, Spanish" and "Windows XP, IE, 800x600, 256 colors, Spanish". 

ALLPAIRS has not yet attracted an active user community. However, it implements a technique that should be used more widely in the testing field, so I think it's worth a look if you have a testing challenge that is amenable to the all-pairs technique and you don't want to immediately make an investment in one of the commercial offerings. You may have to dig around to find sufficient documentation on how this technique works, especially if you're not mathematically inclined. I think that would be time well-spent.