All-pairs testing

In computer science, all-pairs testing or pairwise testing is a combinatorial method of software testing that, for each pair of input parameters to a system (typically, a software algorithm), tests all possible discrete combinations of those parameters. Using carefully chosen test vectors, this can be done much faster than an exhaustive search of all combinations of all parameters, by "parallelizing" the tests of parameter pairs.

Rationale

Assume that the test function has $N$ parameters given in a set $\{ P_i\} = \{ P_1 , P_2 , ... , P_N \}$. The range of the parameters are given by $R(P_i)= R_i$. Let's assume that $|R_i|= n_i$. We notice that the set of choices of ranges $X = \{ n_i \}$ can be a multiset, because there can be multiple parameters having same number of choices.

Let's define $max(S)$ as one of the maximum of the multiset $S$. Then, the number of pair-wise test cases on this test function would be:-

$T = max(X) \times max ( X \setminus max(X) )$

Plainly that would mean, if the $n = max(X)$ and $m = max ( X \setminus max(X) )$ then the number of tests is typically O(nm). Where n and m are the number of possibilities for each of the two parameters with the most choices.

Parameter Name	Value 1	Value 2	Value 3	Value 4
Enabled	True	False	*	*
Choice Type	1	2	3	*
Category	a	b	c	d

In this case the parameters are Enabled with choices range of 2, Choice Type with 3, and Category with 4. That would mean: $X = \{ 2, 3 , 4 \}$ Hence, n = 4, m = 3 and number of tests would be 12. The pict tool generated pairwise test cases on the input looks like:-

Enabled	Choice Type	Category
True	3	a
True	1	d
False	1	c
False	2	d
True	2	c
False	2	a
False	1	a
False	3	b
True	2	b
True	3	d
False	3	c
True	1	b

The below table would generate a multiset :

Parameter Name	Value 1	Value 2	Value 3	Value 4
Enabled	True	False	*	*
Choice Type	1	2	3	4
Category	a	b	c	d

In this case the parameters are Enabled with choices range of 2, Choice Type with 4, and Category with 4. That would mean:- $X = \{ 2, 4 , 4 \}$ and it is a multiset. Hence, n = 4, m = 4 and number of tests would be 16, which are shown in the below table:-

Enabled	Choice Type	Category
True	3	b
False	3	d
True	2	a
True	1	c
False	4	b
False	1	a
False	2	b
True	4	d
True	4	a
True	2	d
False	4	c
False	1	b
True	2	c
False	1	d
False	3	a
True	3	c

The reasoning behind all-pairs testing is this: the simplest bugs in a program are generally triggered by a single input parameter. The next simplest category of bugs consists of those dependent on interactions between pairs of parameters, which can be caught with all-pairs testing. Bugs involving interactions between three or more parameters are progressively less common, while at the same time being progressively more expensive to find by exhaustive testing, which has as its limit the exhaustive testing of all possible inputs.

This can be further generalized.^{[citation needed]} The idea is to apply sorting to the set $X = \{ n_i \}$ so that $P = \{ P_i \}$ gets ordered too. Let the sorted set be a $N$ tuple :-

$P_s = < P_i > \;  ; \; i < j \implies |R(P_i)| < |R(P_j)|$

Now we can take the set $X(2) = \{ P_{N-1} , P_{N-2} \}$ and call it the pairwise testing. Generalizing further we can take the set $X(3) = \{ P_{N-1} , P_{N-2} , P_{N-3} \}$ and call it the 3-wise testing. Eventually, we can say $X(T) = \{ P_{N-1} , P_{N-2} , ... , P_{N-T} \}$ T-wise testing.

The N-wise testing then would just be, all possible combinations from the above formula.

One of the main strengths of combinatorial technique is that it enables a significant reduction of the number of test cases without compromising functional coverage. Many testing methods regard all-pairs testing of a system or subsystem as a reasonable cost-benefit compromise between often computationally infeasible higher-order combinatorial testing methods, and less exhaustive methods which fail to exercise all possible pairs of parameters. Because no testing technique can find all bugs, all-pairs testing is typically used together with other quality assurance techniques such as unit testing, symbolic execution, fuzz testing, and code review.

See also

• Software testing
• Orthogonal array testing

External links

• Combinatorialtesting.com; Includes clearly written introductions to pairwise and other, more thorough, methods of combinatorial testing
• Hexawise.com - Pairwise test case generating tool with both free and commercial versions (also provides more thorough 3-way, 4-way, 5-way, and 6-way coverage solutions)
• Pairwise Testing Comes of Age - Review including history, examples, issues, research
• Pairwise Testing: Combinatorial Test Case Generation
• Pairwise testing
• All-pairs testing
• Pairwise and generalized t-way combinatorial testing
• TestApi - .NET API library for testing, providing a variation generation API
• NTestCaseBuilder - another .NET API library; focussed purely on combinatoric testing and scalability of test case generation
• JCombinatorial - an open-source library that facilitates all-pairs testing with JUnit
• "rdExpert Software for Orthogonal Array Testing". Phadke Associates, Inc. "Commercial toolset for Orthogonal Array and PairWise Testing." 
• Pairwise Testing in the Real World: Practical Extensions to Test-Case Scenarios