'Orthogonal arrays' is a fairly recent mathematical theory that is attracting increasing interest. It concerns the mathematical properties in the combining of factors, so-called " Combinatorics". It has countless interesting applications in science, industry and… testing.
Combinations are also employed in testing. Consider that system behaviour in general is determined by several parameters, each of which can assume various values. In order to create a test case, the tester chooses one of the possible values for each parameter. In fact, he is creating a combination of parameter values that is going to be tested. The testing of all the possible combinations soon becomes unfeasible in practice. If, for example, there are 8 parameters, each of which have 3 possible values (or equivalence classes), then there are already 38 = 6,561 possibilities! Of necessity, only a subset can be tested. But what is a sensible subset to use? This is where orthogonal arrays and pairwise testing can offer a solution.
Here it is first explained what the principle of pairwise testing are, to familiarise the reader with the meaning and result of such techniques that are based on combinatorics. Subsequently, the more complex material of orthogonal arrays is explained along general lines. The latter is not necessary in order to be able to apply the basic technique of pairwise testing, but is intended for those interested in deeper theory.
Pairwise testing
Pairwise testing is based on the phenomenon that most faults in software are the consequence of one particular factor or the combination of 2 factors. The number of faults that are caused by a specific combination of more than 2 factors becomes exponentially smaller. Instead of testing all the possible combinations of all the factors, it is very effective if every combination of 2 factors is tested.
DefinitionThe aim of pairwise testing is to test all the possibilities of any combination of 2 factors. |
This delivers an enormous reduction in the number of required test cases, yet still gives a good fault-detection result. Scientific research has shown that pairwise testing would find over 97% of the faults.
The following example illustrates the meaning of pairwise testing.
In more detailIn the system under test (for ordering books via the Internet), the following 3 parameters play a role. For each parameter, there are 2 equivalence classes to be tested:
In order to test all the combinations relating to these 3 parameters, 2x2x2=8 test cases are required, namely:
For pairwise testing, as few as 4 test cases will suffice, as shown below:
Of the 2 parameters [Number of books, Sum], all 4 existing combinations are tested (Few/Low; Few/High; Many/Low; Many/High). The same applies to the other combinations of 2 parameters, so for [Number of books, Membership card] and [Sum, Membership card]. Check it for yourself. |
What is the point of this? If a fault exists in the system that occurs when one of the possible values of one of the parameters is combined with a particular value of one of the other parameters, then this fault is always found with these 4 test cases. That is the strength of pairwise testing.
Deriving test cases for pairwise testing
If there is a pair of parameters with only 2 equivalence classes, the test cases necessary for pairwise testing can be derived manually. In most situations in practice, however, there are more parameters and equivalence classes and it is not possible to do this manually. In that case, there are 2 ways of solving this:
- Application of orthogonal arrays (see following subsection)
- Use of tools (discussed further in this section).
The number of necessary test cases, and how exactly they are combined, depends on the tool that is used. Various tools are available, both commercially and free via the Internet (freeware, see http://pairwise.org).
Take, for example, the following more extended version of the "book-ordering system". The previously mentioned parameters now have more equivalence classes, and another parameter: "Ordering period", has been added:
| Number of books | 1 ; 2-8 ; >8 |
| Sum | <100 ; 100-250 ; >250 |
| Membership card | None; Silver; Gold; Platinum |
| Ordering period | Weekday; Weekend; Public holiday |
For the testing of all possible combinations in this case, 3x3x4x3=108 test cases are necessary. For pairwise testing, a fraction of these will suffice.
We used two of the tools available and this resulted in 13 respective 14 testcases!
Stronger variants, such as triplewise testing
The principle of pairwise testing can be extended to the combination of more than two factors. For example, the testing of all the possibilities of any three random factors is known as 'triplewise testing'. A general definition is as follows:
DefinitionN-wise testing has the aim of testing all the possibilities of any random combination of N factors. |
The maximum value for N is equal to the number of parameters. In that case, the result is equal to the testing of the complete decision table: all the combinations of all the values of all the parameters. In practice, a value of 4 or higher is seldom applied.
One of the used tools can tackle a randomly given strength. For triplewise testing of the previously given example, this tool calculates 43 test situations. Application of N=4 would deliver the maximum number of 108 test situations.
Orthogonal arrays
The first example of pairwise testing deals with 3 parameters, each with 2 equivalence classes. If, for each parameter, the equivalence classes are numbered, i.e. "1" and "2", then the 4 test cases for pairwise testing are described by the following 2-dimensional array:
| param-1 | param-2 | param-3 | |
|---|---|---|---|
| TC-1 | 1 | 1 | 1 |
| TC-2 | 1 | 2 | 2 |
| TC-3 | 2 | 1 | 2 |
| TC-4 | 2 | 2 | 1 |
This is an example of an orthogonal array and is noted as L4(23). The meaning of the different symbols here is:
| 4 | The number of rows (therefore the number of test cases that appear to be required) |
| 2 | The maximum value in each column (therefore the number of equivalence classes of each parameter) |
| 3 | The number of columns (therefore the parameters that together form a test case) |
The interesting property of this array is that every combination of 2 columns contains all the possible combinations of the values "1" and "2". The term for this is that it is an orthogonal array of "strength 2". This exactly fits the purpose of pairwise testing, in which "all the combinations of equivalence classes of TWO random parameters" are tested.
Another special property of orthogonal arrays is that they are balanced. That means that each combination of parameter values occurs with equal frequency to any other combination of parameter values. This property distinguishes orthogonal arrays from pairwise testing. With the test cases that are created through the application of pairwise testing, certain equivalence classes usually occur more frequently than others do. With orthogonal arrays, all the equivalence classes (even each combination of equivalence classes) occur with equal frequency.
For deeper testing than pairwise testing, an orthogonal array with a higher strength is necessary. For the testing of all the combinations of equivalence classes of three random parameters, an orthogonal array of "strength 3" will be required. Below is an orthogonal array of strength 3 for 4 parameters, each of which can have 2 values:
| 1 | 1 | 1 | 1 |
| 1 | 1 | 2 | 2 |
| 1 | 2 | 1 | 2 |
| 1 | 2 | 2 | 1 |
| 2 | 1 | 1 | 2 |
| 2 | 1 | 2 | 1 |
| 2 | 2 | 1 | 1 |
| 2 | 2 | 2 | 2 |
This array has the property that every combination of 3 columns contains all the possible combinations of the values 1 and 2, namely (1 1 1), (1 1 2), (1 2 1), (1 2 2), (2 1 1), (2 1 2), (2 2 1) and (2 2 2).
The notation for this orthogonal array is L8(24, 3), in which the number 3 indicates the strength of the array. In the literature, there are various ways of noting orthogonal arrays. The most usual ways of notation are:
- L8(24, 3),
- OA(8, 24, 3),
- OA(8, 4, 2, 3)
If the value for strength is omitted, the default value of strength 2 is assumed.
All of the foregoing can be summarised in the following complicated definition:
DefinitionAn orthogonal array LN(sk, t) is a 2-dimensional array of N rows and k columns consisting of elements that can assume s values, whereby every combination of t columns contains all the combinations of the s values in equal proportion. |
An orthogonal array does not exist for every value of "s" and "k". In practice, such a situation uses a 'too big' array, with the superfluous columns being ignored in its application.
So far, orthogonal arrays have been described in which the possible values for the elements of all the columns are equal. There are also orthogonal arrays in which columns can have varying possible values. An example of this is L8(24, 41, 2). The array of strength 2 contains 4 columns, each of which have 2 possible values, plus 1 column with 4 possible values. Such an array is set out below:
| 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 2 |
| 1 | 0 | 1 | 0 | 2 |
| 0 | 1 | 1 | 0 | 3 |
| 1 | 0 | 0 | 1 | 3 |
How do you get orthogonal arrays?
The creation of an orthogonal array is not simple. If there are several columns that can assume more than 2 values, it is more or less impossible to do manually. Fortunately, there is extensive literature on the subject, including books, articles and websites, with many examples and worked-out arrays that the tester can employ.
The book "Orthogonal arrays: Theory and Applications" [Hedayat, 1999]] is generally accepted as the standard work on orthogonal arrays.
One of the most extensive collections of orthogonal arrays on the Internet can be found on the site of N.J.A Sloane. An Internet search for "orthogonal arrays" will undoubtedly lead to this and many other useful sites.
Deriving test cases with orthogonal arrays
The application of pairwise testing (and stronger variants) is simple, thanks to the available tools that quickly generate the necessary test cases. Deriving the test cases using orthogonal arrays involves more work and is more complicated, but gives the extra advantage of the "balanced test cases": every combination of equivalence classes occurs with equal frequency. The tester will have to consider whether this extra advantage is worth the additional effort necessary.
For the enthusiasts, it is explained below how orthogonal arrays can be applied in order to derive a balanced set of test cases for N-wise testing:
- Determine the parameters of which the test case consists.
- Determine the equivalence classes of each parameter.
- Select the strength of the orthogonal array, based on the required strength of the test.
- Find a fitting orthogonal array.
- An orthogonal array does not exist for every quantity of parameters and equivalence classes. In that case, one has to be found that is 'just a bit too big'. This can be done in 2 ways and should then be used as follows:
- There are too many columns (more columns than parameters).
- The relevant columns can simply be omitted. This has no influence on the orthogonality of the array
- The maximum value of a column is too great. (The maximum value of "s" is greater than the number of equivalence classes of the parameter.)
- Here, the rows that contain the too-great value may not be casually omitted. These rows are necessary to realise the obligatory combinations of the other parameters. In this case, a too-great value in the column should be construed as "don't care value". A random equivalence class can therefore be selected.
- There are too many columns (more columns than parameters).
- An orthogonal array does not exist for every quantity of parameters and equivalence classes. In that case, one has to be found that is 'just a bit too big'. This can be done in 2 ways and should then be used as follows:
- Translate the orthogonal array into test cases.
Example
In order to explain this, the same example is used as worked out with pairwise testing, concerning the "book-ordering system":
Suppose that this system is to be tested with an average strength. The 5 steps for deriving the test cases proceed as follows:
Step 1: Determine the parameters of which the test case consists.
There are 4 parameters: "Number of books", "Sum", "Membership card", "Ordering period".
Step 2: Determine the equivalence classes of each parameter.
The parameters are arranged in ascending order according to the number of equivalence classes. This simplifies the search for a suitable orthogonal array (step 4).
| Number of books | 1 ; 2-8 ; >8 |
| Sum | <100 ; 100-250 ; >250 |
| Membership card | None; Silver; Gold; Platinum |
| Ordering period | Weekday; Weekend; Public holiday |
Step 3: Select the strength of the orthogonal array.
Since the system is to be tested with average strength, strength 2 is selected. For stronger testing, a higher strength can be selected. This mainly affects the search for a fitting orthogonal array (step 4). Otherwise, the 5 steps remain unchanged in this technique.
Step 4: Find a fitting orthogonal array.
There are 3 parameters with 3 equivalence classes and 1 parameter with 4 equivalence classes. This means that an orthogonal array must be found that approximates as far as possible:
LN(33, 41, 2)
Unfortunately, this orthogonal array does not exist. Therefore, one must be found that is just a bit bigger. The following 2 orthogonal arrays could be considered:
- L18(36, 61, 2)
- This consists of 18 rows and 7 columns. Of the first 6 columns (that can assume 3 values), 3 are superfluous and can be scrapped. The last column can assume 6 values, but of those, only 4 are required for our test. The column therefore has 2 superfluous values that may be entered randomly (the "don't-matter values").
- L16(45, 2)
- This consists of 16 rows and 5 columns. One column is superfluous and can be scrapped. The first 3 columns of the remainder of the table then contain 1 possible value too many, which counts among the "don't-care values".
The second array is selected, since it delivers the lowest number of required test cases. The L16(45, 2) looks as follows:
| 1 | 1 | 1 | 1 | 1 |
| 1 | 2 | 2 | 2 | 2 |
| 1 | 3 | 3 | 3 | 3 |
| 1 | 4 | 4 | 4 | 4 |
| 2 | 1 | 2 | 3 | 4 |
| 2 | 2 | 1 | 4 | 3 |
| 2 | 3 | 4 | 1 | 2 |
| 2 | 4 | 3 | 2 | 1 |
| 3 | 1 | 3 | 4 | 2 |
| 3 | 2 | 4 | 3 | 1 |
| 3 | 3 | 1 | 2 | 4 |
| 3 | 4 | 2 | 1 | 3 |
| 4 | 1 | 4 | 2 | 3 |
| 4 | 2 | 3 | 1 | 4 |
| 4 | 3 | 2 | 4 | 1 |
| 4 | 4 | 1 | 3 | 2 |
Step 5: Translate the orthogonal array into test cases
The selected orthogonal array is now cut to size and then filled in with the real values of the test parameters.
The last column of the array is removed. The first 3 parameters have only 3 possible values. For that reason, of the first 3 columns, the value "4" is replaced by a "~" , indicating that the value does not matter. The array then looks as follows:
| 1 | 1 | 1 | 1 |
| 1 | 2 | 2 | 2 |
| 1 | 3 | 3 | 3 |
| 1 | ~ | ~ | 4 |
| 2 | 1 | 2 | 3 |
| 2 | 2 | 1 | 4 |
| 2 | 3 | ~ | 1 |
| 2 | ~ | 3 | 2 |
| 3 | 1 | 3 | 4 |
| 3 | 2 | ~ | 3 |
| 3 | 3 | 1 | 2 |
| 3 | ~ | 2 | 1 |
| ~ | 1 | ~ | 2 |
| ~ | 2 | 3 | 1 |
| ~ | 3 | 2 | 4 |
| ~ | ~ | 1 | 3 |
In more detailThrough a clever selection from the "don't-matter values", a number of identical rows can be created: For the rows 4 and 15, the identical combination (1 3 2 4) can be selected and for the rows 10 and 16, the combination (3 2 1 3). With this, two rows are dropped and, with these, two test cases. However, this reduction is not compulsory and will be left out of consideration in the further process. |
Finally, the test parameters should be allocated to the columns of the array and the values in the columns replaced by an equivalence class. Which value is linked to which equivalence class is irrelevant, as long as they are consistently applied. As a reminder, the parameters are repeated below with their equivalence classes summed up.
| Number of books | 1 ; 2-8 ; >8 |
| Sum | <100 ; 100-250 ; >250 |
| Ordering period | Weekday; Weekend; Public holiday |
| Membership card | None; Silver; Gold; Platinum |
In our example, the final result then looks as follows. A "~" still indicates that a random selection of the available values may be made.
| Number of books | Sum | Ordering period | Membership card | |
|---|---|---|---|---|
| 1 | 1 | <100 | Weekday | None |
| 2 | 1 | 100-250 | Weekend | Silver |
| 3 | 1 | >250 | Public Holiday | Gold |
| 4 | 1 | ~ | ~ | Platinum |
| 5 | 2-8 | <100 | Weekend | Gold |
| 6 | 2-8 | 100-250 | Weekday | Platinum |
| 7 | 2-8 | >250 | ~ | None |
| 8 | 2-8 | ~ | Public Holiday | Silver |
| 9 | >8 | <100 | Public Holiday | Platinum |
| 10 | >8 | 100-250 | ~ | Gold |
| 11 | >8 | >250 | Weekday | Silver |
| 12 | >8 | ~ | Weekend | None |
| 13 | ~ | <100 | ~ | Silver |
| 14 | ~ | 100-250 | Public Holiday | None |
| 15 | ~ | >250 | Weekend | Platinum |
| 16 | ~ | ~ | Weekday | Gold |