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 note that the all possible conditions that can be used is an exponentiation, while imagining that the code deals with the conditions taking only two pair at a time, might reduce the number of conditionals.

To demonstrate, suppose there are X,Y,Z parameters. We can use a predicate of the form P(X,Y,Z) of order 3, which takes all 3 as input, or rather three different order 2 predicates of the form p(u,v) . P(X,Y,Z) can be written in an equivalent form of p_{xy}(X,Y) , p_{yz}(Y,Z) , p_{zx}(Z,X) where comma denotes any combination. If the code is written as conditions taking "pairs" of parameters: then,the set of choices of ranges X = \{ n_i \} can be a multiset, because there can be multiple parameters having same number of choices.

max(S) is one of the maximum of the multiset S. 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, and it can be quite a lot less than the exhaustive \prod n_i

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.[1] Bugs involving interactions between three or more parameters are progressively less common,[2] 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.[3]

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.[4] 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. For example, consider the case of N=10 binary parameters. An exhaustive set of tests involves 2^{10} tests, whereas the all-pair setting would involve just 6.

N-wise testing

N-wise testing can be considered the generalized form of pair-wise testing.

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.

Example

Consider the parameters shown in the table below.

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

'Enabled', 'Choice Type' and 'Category' have a choice range of 2, 3 and 4, respectively. An exhaustive test would involve 24 tests (2 x 3 x 4). Multiplying the two largest values (3 and 4) indicates that a pair-wise tests would involve 12 tests. The pict tool generated pairwise test cases is shown below.

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

Notes

  1. ↑ Black, Rex (2007). Pragmatic Software Testing: Becoming an Effective and Efficient Test Professional. New York: Wiley. p. 240. ISBN 978-0-470-12790-2.
  2. ↑ D.R. Kuhn, D.R. Wallace, A.J. Gallo, Jr. (June 2004). "Software Fault Interactions and Implications for Software Testing" (PDF). IEEE Trans. on Software Engineering 30 (6).
  3. ↑ Practical Combinatorial Testing. SP 800-142. (PDF) (Report). Natl. Inst. of Standards and Technology. 2010.
  4. ↑ "IEEE 12. Proceedings from the 5th International Conference on Software Testing and Validation (ICST). Software Competence Center Hagenberg. "Test Design: Lessons Learned and Practical Implications.".

See also

External links