Allpairs, pairwise, combinatorial analysis

Last week I went to StarWest as a presenter and as a track chair to introduce speakers. Being a track chair is wonderful because you get to interface more closely with other speakers. Anyway...one of the speakers I introduced was Jon Bach. Jon is a good public speaker, and I was pleasantly surprised that he was doing a talk on the allpairs testing technique (also known as pairwise or combinatorial analysis). I wish Jon dedicated a little more time to the specifics of the technique during his talk and was generally more aware of available tools and information for folks to investigate further, but I think he successfully raised the general awareness and interest in pariwise testing as an effective testing technique among the audience.

Pairwise testing is one approach to solving the potential explosion in the number of tests when dealing with multiple parameters whose variables are semi-coupled or have some dependency on variable states of other parameters. For example, in the font dialog of MS Word there are 11 checkboxes for various effects such as superscript, strikethrough, emboss, etc. Obviously these effects have impact on how the characters in a particular font are displayed and can be used in multiple combinations such as Strikethrough + Subscript + Emboss. The total number of combinations of effects is the Cartesian product of the variables for each parameter, or 2¹¹ or 2048 in this example. This doesn't include different font types, styles, etc. which also interdependent. So, you can see how the number of combinations increases rapidly especially as additional dependent parameters are included in the matrix.

The good news is the industry has a lot of evidence to suggest that most software defects occur from simple interactions between the variables of 2 parameters. So, from a risk based perspective where it may not be feasible to test all possible combinations how do we choose the combinations out of all the possibilities? Two common approaches include orthogonal arrays and combinatorial analysis.

But, true orthogonal arrays require that the number of variables is the same for all parameters. (Rarely true in software.) It is possible to create "mixed orthogonal arrays" where some combinations of variables will be tested more than once. For example, if we have 5 parameters and one parameter has 5 variables and the remains 4 parameters only have 3 variables each, we can see from the orthogonal array selector (available on FreeQuality website) the size of the orthogonal array is L₂₅ (which basically means the test case will require 25 tests which is still significantly less than the total number of combinations of 405).

The other approach is combinatorial analysis (often referred to as pairwise or allpairs testing) because the approach most commonly used is to use a mathematical formula to reduce the total number of combinations in such a way that each variable for each parameter is tested with each variable from the other parameters at least once. In the above example, the number of tests would be reduced to 16. (Note: some tools will give slightly different results.) However, some tools (such as Microsoft's PICT) also allow for more complex analysis of variable combinations such as triplets and n-wise coverage.

One problem that is hopefully not overlooked by testers using these tools is that some combinations of variables are simply not possible. For example, in the Effects group of the Font dialog it is impossible to check the Superscript checkbox and the Subscript checkbox simultaneously. Therefore, the tester either has to manually modify the output, or use a tool that allows constraints. Again, this is another situation where Microsoft's free tool PICT excels. PICT uses a simply basic-like language for conditional and unconditional constraining of combinations of variables. PICT also allows weighting variables, seeding, output randomization, and negative testing.

I didn't want this to be a PICT sales job, but alas my bias has influenced this post. So, I will conclude by pointing the readers to the Pairwise Testing website. My colleague Jacek Czerwonka has pulled together great resources on the technique of combinatorial analysis including a list of free and commercially available tools, and white papers supporting the value and practicality of this testing technique.

Comments

• Anonymous
  October 31, 2006
  The comment has been removed

• Anonymous
  October 31, 2008
  Hi, Recently I was searching for pairwise material and landed in your blog. Thanks a lot for pointing out PICT. it is Clear Introduction. Currently I am doing a study on the effectiveness of such a tool over manual test data generation. After producing the data manually and using the tool, I want to compare both of them to see how the data is distributed. Is there a methodical way to do this comparison? Any pointers will be greatly appriciated. Thanks in advance.

• Anonymous
  October 31, 2008
  Hi Krishtheindian, There are already numerous studies on the web and at http://www.pairwise.org. I don't understand what you mean by "compare both of them to see how the data is distributed." Combinatorial analysis is a technique for reducing the number of tests from all possible combinations when analyzing the interactions of varaible state combinations for n-way direct or semi-coupled unordered parameters. This has nothing to do with distribution of data. Exactly how are you going to produce manual tests to compare against the output of a tool? Producing all possible combinations of variable states is only reasonable for small feature sets because the total number of possible combinations is the Cartesian product of the number of variable states for all semi-coupled or dependent paramter. So, for trivial feature sets of say up to a hundred or so possible combinations comparisons between manaul tests and n-way analysis is relatively easy and has been done several times. But such trivial feature sets do not expose the full potentional of the toolset. Manual selection of tests from a feature set that produces say 10,000 or >1,000,000 possible combinations is unreasonably improbable.