View source for 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 vector]]s, this can be done much faster than an exhaustive search of [[Software testing#Input combinations and preconditions|all combinations]] of all parameters by "parallelizing" the tests of parameter pairs.<ref>{{Cite web |last=Berger |first=Bernie |date=2003 |title=Efficient Testing with All-Pairs |url=https://techwell.com/sites/default/files/articles/XDD6488filelistfilename1_0.pdf |access-date=21 November 2023 |website=TechWell Corporation}}</ref>

== Rationale ==

In most cases, a single input parameter or an interaction between two parameters is what causes a program's bugs.<ref>{{cite book |last=Black |first=Rex |year=2007 |title=Pragmatic Software Testing: Becoming an Effective and Efficient Test Professional |publisher=[[John Wiley & Sons|Wiley]] |location=New York |isbn=978-0-470-12790-2 |page=240}}</ref>  Bugs involving interactions between three or more parameters are both progressively less common <ref>{{cite journal |last1=Kuhn |first1=D. Richard |last2=Wallace |first2=Dolores R. |last3=Gallo |first3=Albert M. Jr. |date=June 2004 |title=Software Fault Interactions and Implications for Software Testing |journal=IEEE Transactions on Software Engineering |volume=30 |issue=6 |pages=418–421 |url=http://csrc.nist.gov/staff/Kuhn/kuhn-wallace-gallo-04.pdf |doi=10.1109/TSE.2004.24 |s2cid=206778290 }}</ref> and also progressively more expensive to find, such testing has as its limit the testing of all possible inputs.<ref>{{cite report |last1=Kuhn |first1=D. Richard |last2=Kacker |first2=Raghu N. |author3=Yu Lei |date=October 2010 |title=Practical Combinatorial Testing. SP 800-142. |publisher=[[National Institute of Standards and Technology]] |doi=10.6028/NIST.SP.800-142|doi-access=free }}</ref> Thus, a combinatorial technique for picking test cases like all-pairs testing is a useful cost-benefit compromise that enables a significant reduction in the number of test cases without drastically compromising functional coverage.<ref>{{cite book |date=July 18, 2008 |title=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. |journal=IEEE STD 829-2008 |doi=10.1109/IEEESTD.2008.4578383 |pages=1–150 |isbn=978-0-7381-5746-7 }}</ref>

More rigorously, if we assume that a test case has <math>N</math> parameters given in a set <math>\{ P_i\} = \{ P_1 , P_2 , ... , P_N \}</math>.
The range of the parameters are given by <math>R(P_i)= R_i</math>.
Let's assume that <math>|R_i|= n_i</math>.
We note that the number of all possible test cases is a <math>\prod n_i</math>. Imagining that the code deals with the conditions taking only two parameters at a time, might reduce the number of needed test cases.{{clarify|date=March 2016|reason=This clause is not well-formed, and the extraneous comma and the ambiguous placement of "taking only two pair at a time" obscure its meaning.}}

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

<math>max(S)</math> is one of the maximum of the multiset <math>S</math>
The number of pair-wise test cases on this test function would be:-
<math>
T =  max(X) \times max ( X \setminus max(X) )
</math>

Therefore, if the <math> n = max(X) </math> and <math> m =  max ( X \setminus max(X) ) </math> 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 <math>\prod n_i</math>·

== N-wise testing ==

N-wise testing can be considered the generalized form of pair-wise testing.{{citation needed|date=July 2012}}

The idea is to apply [[sorting]] to the set  <math>X = \{ n_i \}</math> so that <math>P = \{ P_i \}</math> gets ordered too.
Let the sorted set be a  <math>N</math> tuple :-

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

Now we can take the set <math>X(2) = \{ P_{N-1} , P_{N-2}  \}</math> and call it the pairwise testing.
Generalizing further we can take the set <math>X(3) = \{ P_{N-1} , P_{N-2} , P_{N-3}  \}</math> and call it the 3-wise testing.
Eventually, we can say <math>X(T) = \{ P_{N-1} , P_{N-2} , ... , P_{N-T}  \}</math>  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.

{| class="wikitable"
|-
! 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 pairwise test cases, generated by Microsoft's "pict" tool, are shown below.

{| class="wikitable sortable"
|-
! 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
|}

== See also ==

* [[Software testing]]
* [[Orthogonal array testing]]

== Notes ==
{{reflist}}

== External links ==
* [http://www.developsense.com/testing/PairwiseTesting.html Pairwise testing]
* [http://csrc.nist.gov/acts/ Pairwise and generalized t-way combinatorial testing]
* [http://msdn.microsoft.com/en-us/library/cc150619.aspx Pairwise Testing in the Real World: Practical Extensions to Test-Case Scenarios]
* [https://www.pairwise.org Pairwise Testing - Combinatorial Test Case Generation]

{{Prone to spam|date=April 2015}}
<!--     {{No more links}}

       Please be cautious adding more external links.

Wikipedia is not a collection of links and should not be used for advertising.

     Excessive or inappropriate links will be removed.

 See [[Wikipedia:External links]] and [[Wikipedia:Spam]] for details.

If there are already suitable links, propose additions or replacements on
the article's talk page, or submit your link to the relevant category at
DMOZ (dmoz.org) and link there using {{Dmoz}}.

-->

{{Software testing}}

{{DEFAULTSORT:All-Pairs Testing}}
[[Category:Software testing]]
[[Category:Combinatorics]]
[[Category:Design of experiments]]