Guest Post – All-Pairs Testing

by Greg M Lucas on 1 March 2012

I am very pleased to be able to present this article written by Dennis Lloyd Jr (blog | twitter), creator of the Test Driven Databases Initiative and one of the authors of the tSQLt Unit Testing framework for SQL Server.  One of a series on applying test case heuristics to database testing, this article explores an approach to minimising the number of tests that need to be written for procedures and methods with many input parameters.

All-Pairs Testing

by Dennis Lloyd Jr

About the Series

Test case heuristics are patterns used to help decide the next test to write and ensure test coverage of requirements. This is the third post on a series of test case heuristics pertaining to database testing.

I’m trying out a new way of delivering series to a wider audience – post sharing! The series home is at: http://testdrivendatabases.com/testheuristics where you can find links to all articles in the series. The posts will be scattered over a variety of websites and blogs.

Definition:

Clean coding techniques should drive us to write methods with as few parameters as possible. We know that the more parameters a method has, the more difficult it is to understand, test and maintain. Consider a method that has five parameters, each of which have three possible values. There are 125 different combinations possible among the parameters! Growing the number of possible values for each parameter, even modestly, results in a much larger number of combinations. Testing every combination quickly becomes time consuming and questionably helpful.

First, we should do our best to have smaller code with fewer parameters. Next, if we’re using a technique such as test driven design, we shouldn’t have untested execution paths. However, if we’re still stuck with a method that needs to be tested that has many parameters, we can utilize all-pairs testing to reduce the number of tests that we need to write.

All-pairs testing (or pairwise testing) is a technique for generating test case inputs that reduces the overall number of tests we need to write. Instead of writing a test for every combination of the parameters, we instead make sure that we have at least one test for each pairing of input parameter values. This takes advantage of a convenient discovery in software defects: most defects are caused by a single parameter, many defects are caused by the interaction of two parameters, far fewer defects occur by the interaction of three or more parameters [D.R. Kuhn, D.R. Wallace, A.J. Gallo, Jr. (June 2004). “Software Fault Interactions and Implications for Software Testing”. IEEE Trans. on Software Engineering 30 (6).]

Purpose:

All-Pairs Testing:

  • Allows you to reduce the number of test cases needed to test methods with many parameter value combinations
  • Utilizes information we know about where defects occur to focus on getting reasonable test coverage
  • Uses a tool to generate test case inputs

Example:

Suppose we want to deliver meaningful video game advertising to a web page viewer. We’ve collected information about their operation system, browser, some basic demographics and their video game preferences. The algorithm is complex and requires all parameters to be considered. We want to generate a set of test cases that will most likely find defects if they exist.

We can use an all-pairs program, such as PICT from Microsoft (http://msdn.microsoft.com/en-us/testing/bb980925) to generate our test cases. First we store the “model” in a text file, model.txt in this example. The model is simply the parameter names and their allowed values.

Browser: Chrome, Internet Explorer, Firefox, Safari, Opera
Operating System: Windows, Linux, MacOS
Region: North America, South America, Africa, Europe, Asia
Age Group: Under 13, Teenager, Young Adult, Middle Aged, Elderly
Primary Genre Preference: Adventure, Role Playing, Racing, Social, Arcade
Secondary Genre Preference: Adventure, Role Playing, Racing, Social, Arcade

Next we execute the PICT program:

PICT.exe model.txt

This produces the following output:

Browser Operating System Region Age Group Primary Genre Preference Secondary Genre Preference
Firefox Windows Africa Middle Aged Arcade Adventure
Internet Explorer Linux Africa Under 13 Racing Social
Opera MacOS North America Elderly Adventure Arcade
Internet Explorer Windows Europe Young Adult Role Playing Arcade
Chrome MacOS Africa Young Adult Social Role Playing
Safari Windows South America Teenager Racing Racing
Opera Linux Asia Teenager Social Adventure
Chrome Linux South America Elderly Arcade Social
Firefox Windows North America Under 13 Role Playing Role Playing
Safari MacOS North America Young Adult Racing Adventure
Opera MacOS Europe Middle Aged Role Playing Racing
Safari Windows Asia Middle Aged Social Social
Internet Explorer MacOS North America Teenager Arcade Racing
Safari Linux Africa Under 13 Adventure Racing
Firefox Linux Asia Elderly Role Playing Arcade
Opera Linux Europe Under 13 Arcade Role Playing
Chrome MacOS South America Middle Aged Racing Arcade
Internet Explorer Windows South America Elderly Social Role Playing
Firefox MacOS Asia Young Adult Arcade Racing
Safari MacOS Africa Under 13 Arcade Arcade
Firefox Linux North America Teenager Social Social
Firefox Windows South America Young Adult Adventure Adventure
Firefox MacOS Europe Teenager Adventure Social
Chrome Windows Africa Teenager Role Playing Arcade
Chrome Windows Europe Under 13 Adventure Adventure
Opera Linux South America Young Adult Role Playing Social
Opera Windows Asia Under 13 Racing Role Playing
Chrome Linux North America Middle Aged Social Racing
Safari Linux Europe Elderly Racing Adventure
Firefox Windows Africa Teenager Racing Role Playing
Internet Explorer Linux Asia Middle Aged Adventure Adventure
Internet Explorer Linux South America Under 13 Social Arcade
Safari MacOS Asia Middle Aged Adventure Role Playing
Opera MacOS Africa Elderly Adventure Racing
Chrome Linux Asia Young Adult Role Playing Adventure
Safari Windows Europe Teenager Social Racing
Safari MacOS Africa Under 13 Role Playing Arcade

 

We can use each row of this table as a separate test case. Note that this is still a relatively large number of tests – but it sure beats trying to test all combinations!

Notes:

All-pairs testing can be exceptionally useful when dealing with getting tangled, monolithic legacy code under test. Getting such code under test is a prerequisite of doing any refactoring to break up the code into more manageable and testable components.

There are many tools that can be used for generating all-pairs combinations. A list can be found at: http://www.pairwise.org/tools.asp

Previous post:

Next post: