Side Note: n-wise combinatorial testing
The testing techniques we have looked at so far are all based on system specifications and their associated considerations. If there are no direct dependencies between individual inputs (i.e., all inputs can be feely combined), mathematics can help us select appropriate combinations and design the corresponding test cases.
Here is a simple example to get you started. If we have three Boolean input parameters that can be freely combined, we have eight possible combinations, as shown in table 5-16.
Table 5-16All combinations of three Boolean parameters
How do things change if we only look at the following four combinations?
Table 5-17Selection of four combinations
These four combinations give us the following situation: If we look at only two parameters, we see that for the parameter pairings A/B, B/C, and A/C, all four combinations of results are covered (true/true, true/false, false/true, and false/false). In other words, all four combinations result whichever combination of two columns we choose.
The core concept of combinatorial pair-wise testing
This illustrates the core concept of pair-wise testing. Instead of testing all possible combinations of all parameters, you only need to test all combinations of two, three or more parameters, although these combinations do then have to be tested completely.
Case Study: A sports club offers various types of sports
To clarify the process, here is a more complex example. A sports club offers its members table tennis, gymnastics, volleyball, basketball, handball, and fitness training. For organizational reasons, each sport is assigned to a department, with volleyball, basketball, and handball combined under “ball sports”. This also reflects the differing costs of the various sports. The result is four basic types of sports (table tennis, gymnastics, ball sports, fitness) that club members can choose from. These options give members a total of 16 different combinations of sports. However, we can cover all the possible pair–wise combinations (table tennis/gymnastics, table tennis/ball sports, table tennis/fitness, gymnastics/ball sports, gymnastics/fitness, and ball sports/fitness), each with its own four combinations, using just six test cases. These are shown in table 5-18.
Table 5-18Types of sports (all four combinations for gymnastics and ball sports are highlighted)
This example shows that some combinations occur more often than others. For example, for table tennis/gymnastics, the Yes/Yes and No/No pairings both occur twice, while all other combinations occur only once.
It is also clear that more “interesting” combinations, such as no sports (No/No/No/No) or all sports (Yes/Yes/Yes/Yes), don’t occur at all.
Table 5-19A selection of five combinations
There is more than one way to select test cases that cover all four pairs of parameters. Table 5-19 fulfills this condition using just five combinations.
Orthogonal and Covering Arrays
A little bit of math
The example shown in table 5-16, with its three Boolean parameters, is very simple. In practice, you will have to combine multiple parameters with more than two possible values, and the selections you make have to follow a strictly defined process. This process is based on a so-called orthogonal array, which is a two-dimensional array in which every combination of two columns contains all possible combinations of the values in both columns.
Orthogonal arrays guarantee even distribution of combinations and are often used in the process of statistical experiment design, whereby the factors being investigated must not be mixed with each other and should be equally distributed. In an orthogonal array, every combination occurs the same number of times, whichever pair of columns you select.
Tables 5-16 and 5-17 are orthogonal arrays. Each true/false combination occurs exactly twice in every combination of two columns in table 5-16 (for example, see parameters B and C, rows 1/5, 2/6, 3/7, and 4/8). In table 5-17, every combination occurs exactly once for any combination of two columns.
Covering Arrays
Covering Arrays are similar to orthogonal arrays but differ in that every combination occurs at least once. They are therefore not able to fulfill the “even distribution of values” requirement. This is not a major drawback when testing and offers the benefit of smaller arrays compared with the orthogonal technique. Covering arrays are sometimes referred to as “minimal” or “optimum” arrays if coverage of possible combinations is reduced to its absolute minimum. Our sports club example requires an orthogonal array with eight rows (from a possible 16) if any two columns are to contain all possible true/false combinations. In this case, each would appear twice.
If we do without the limitation of each combination occurring the same number of times, we end up with the covering array shown in table 5-18 (with six combinations). Table 5-19 (with its five combinations) reduces the level of complication again to produce the corresponding minimal covering array.
Orthogonal and covering arrays represent a mathematical model for selecting a smaller but nevertheless complete set of input combinations. The covering array that table 5-19 is based on contains all possible sports pairings without having to list all 16 possible combinations.
n-wise Testing
Pair-wise Testing
Pair-wise testing is limited to all discrete combinations of pairs of parameters values—i.e., the n in the heading = 2. Both of the examples above illustrate paired combinations. However, pair-wise testing doesn’t guarantee even distribution, and only ensures that each pair occurs at least once. The objective of pair-wise testing is to identify failures that occur due to the interaction of pairs of parameters. Including three or more interwoven parameters in the combinations increases the reliability of the test process.
The corresponding technique is called “n-wise testing”, which determines all possible discrete combinations of n-parameter values.
Case Study: A sports club offers various types of sports (continued)
Table 5-20 extends our previous example to illustrate the principle of n-wise testing for combinations of three parameters. The eight possible combinations of table tennis, gymnastics, and fitness training are highlighted (in this respect, test case 6 is redundant due to test case 5). The table is based on a covering array in which the individual combinations occur different numbers of times (i.e., it is not an orthogonal array).
Table 5-20A covering array for all 3s combinations of sports
As you can see, this technique involves more combinations. For four parameters (i.e., n = 4), a table offering complete coverage would contain 24 = 16 possible permutations. The variable n is therefore referred to as the “strength” of a covering array. We will steer clear of too much math and stick to the practical applications of the technique.
So far, we have only considered parameters that can take on the values true or false. However, some parameters can be represented by a range of values, as in the example below. In such cases, orthogonal arrays are not always practical, while covering arrays usually fit the bill.
Case Study: Testing effort and vehicle variants
n-wise testing can be used to drastically reduce the number of required test cases. To illustrate the principle, let’s take a look at the example. We recall that the product owner wanted to calculate the number of possible equipment variants for each vehicle and came up with the following results:
10 models, each with 5 different types of engine; 10 types of wheel rims, each with summer or winter tires; 10 colors, each in matt, gloss, or pearl effect; and 5 different entertainment systems. These options give us 10×5×10×2×10×3×5 = 150,000 different combinations25.
So how do we use combinatorial test design techniques to reduce this huge number of potential test cases?
1s combinations
Consider the following: Each possible value for each of the seven parameters (10 vehicle types, 5 engines, 10 wheel rim types, 2 tire types, 10 colors, 3 paint effects, and 5 entertainment systems) should occur in at least one test case. We begin by selecting the parameter(s) with the highest number of values (in this case, vehicle type, wheel rim type, and color, each with 10 different values). This gives us a maximum of 10 test cases required to cover each value in at least one test case (see table 5-21). However, this is not a particularly good solution, as the resulting 10 test cases cover only a small selection of the available combinations.
Table 5-21Every possible parameter value occurs in at least one test case (1s combinations)
2s combinations
So how do things look if we want to test every possible combination of two out of seven parameters? A quick scan of the table shows that we require a total of at least 100 test cases just to check all combinations of colors and wheel rims26. Can we perhaps “handle” the other pair–wise combinations of the other parameters using these tests? Yes, we can.
Table 5-22Test cases with 2s combinations (excerpt)
Table 5-22 shows a portion of the table containing all 100 test cases. The test case numbers are taken from the online table. The 10 test cases in the table here combine Rim1 with each available color, but also cover other pairs. For example, test case 0 also tests Model1 & Engine2, Model1 & Rim1, Model1 & Summer, Model1 & White, Model1 & Gloss, Model1 & Ent2. It also tests Engine2 & Rim1, Engine2 & Summer, Engine2 & White, Engine2 & Gloss, Engine 2 & Ent2, and also Rim1 & Summer and so on.
With these 100 test cases, each vehicle type is combined with each value for all the other parameters at least once, and the same is true for all the other parameters too.
3s combinations
What about 3s combinations? Table 5-23 shows some (but not all) of the combinations for the parameters with fewer possible values (5x engine, 2x tires, and 3x paint effect). The table doesn’t include the 18 test cases that are derived from the 6 combinations for Engine3, Engine4, and Engine5.
Table 5-23Test cases for 3s combinations (excerpt)
A total of 1,014 test cases are necessary to cover 3s combinations for all seven parameters—or, more precisely, any three of the seven parameters are completely combined with their possible values. The complete table with its 1,014 test cases is available for download at [URL: Softwaretest Knowledge].
n-wise testing can significantly reduce the number of test cases
Using an automated tool (see below), enables the team to determine the required number of test cases for other combinations too. 4s combinations result in 5,374 test cases, 5s in 25,000 test cases, 6s in 75,000 test cases, and 7s combinations provide complete coverage (i.e., 150,000 test cases).
From 1.7 days to 17 minutes!
Based on these data, the product owner and the testing/QA leader decide to perform the 3s combinations with 1,014 test cases. Both consider the 17 minutes required to execute the entire test suite to be justifiable, compared with the 1.7 days required to execute tests for all 150,000 possible combinations. They also assign three experienced testers to perform a maximum of two hours’ exploratory testing on the test object.
Expected results?
The only issue remaining is to determine the expected results for the 1,014 selected test cases. The decision is taken to implement an additional mini-application that calculates the expected prices for all these combinations, independent of the VSR-II system’s calculate_price() method. The prices it calculates serve as the basis for the pass/fail decisions. To ensure that the new mini-app does not perform incorrect calculations, the most experienced coder is given the job of programming it and a code review is agreed upon.
Side Note
Test Cases
The rows in the covering arrays list the combinations of (input) parameters that need to be converted into test cases. To effectively decide whether a test reveals a failure, the parameter values have to be precisely defined, potential preconditions have to be recorded, and the expected result noted.
Defining Exit Criteria
Use each parameter value once or combine all parameter values with each other?
There are two techniques for test objects with multiple, freely combinable parameters:
- Each parameter value occurs in at least one test case. The maximum number of test cases is then equal to the number of values that the parameter with the most values has.
- All possible combinations of parameter values are to be combined and assigned to separate test cases. However, the sheer number of test cases this can produce often results in an unjustifiably large testing effort, or is simply beyond the scope of the project.
Both techniques are relatively simple to illustrate and explain. If each value is to be used in a single test case, it is easy to achieve the required coverage—i.e., every parameter value is tested. Based on the example with three Boolean parameters shown in table 5-16, we would only need to use combinations 1 and 8 (or instead 2 and 7, 3 and 6, or 4 and 5) to achieve complete coverage. To cover all possible combinations, we would have to use all eight rows of the table for the test cases. Complete coverage is the exit criterion that determines whether testing is complete and can be terminated.
n-wise testing is often the best compromise
n-wise testing is a great technique for determining a number of test cases that lies between these two extremes. The scope of the test (i.e., whether it is based on 2s, 3s, 4s combinations, and so on) is up to the tester to decide, and usually depends on the importance of the test object. The greater the risks involved in a system failure, the more thoroughly the test object needs to be tested. Furthermore, n-wise test cases are defined so that a specific combination of values is always tested completely, which also provides a definition of the required coverage. For example, if all 3s combinations of sports are to be tested, all nine test cases listed in table 5-20 have to be executed. The required coverage is thus achieved and the exit criterion fulfilled.
The exit criterion for an n-wise test is derived from the selected number of combinations. The greater the value n the more combinations there are, and the greater the number of test cases that have to be designed and executed. In order to achieve 100% test coverage, all test cases have to be executed, although impossible combinations can be excluded before testing begins (see below). If the value n is very large, achieving 100% coverage involves a lot of effort and is often not a practical solution.
An alternative technique is to increase n by 1 once a failure has been discovered and remedied, and to repeat the process until no more failures occur on the next level up. Because it involves a lot more effort than simple pair-wise testing, this particular technique is only really suitable for mission-critical test objects.
Benefits and Limitations
Reducing the number of test cases reduces testing thoroughness
Combinatorial test design techniques for deriving test cases are convincing and easy to follow. They provide testers with the certainty of testing a systematically derived set of test cases, even if all possible test cases cannot be included in the test suite. This technique also offers tiered testing based on varying combinations (2s, 3s, …) that cover everything from basic coverage (i.e., each parameter value occurs in at least one test case) to complete coverage of every possible combination of parameters and values.
This creates test cases that don’t actually exist in practice, so these have to be filtered out before testing begins. The remaining test cases also have to be adapted to factor in any dependencies between parameters.
This technique is highly practical but not a magical solution to all of a tester’s problems. The mathematical approach helps to formulate useful sets of test cases, but additional test cases are usually required too. If we take a closer, test-oriented look at tables 5-19 and 5-20, we discover the following:
Drawback: Some combinations are ignored
- 2s combinations (table 5-19):
- There is no test case that includes all four categories of sports
- Apart from Test Case 1 (no sports selected), all other test cases include some combination of three categories of sports
- There are no test cases that combine two categories of sports
- 3s combinations (table 5-20):
- There are no test cases that include all four categories of sports
- There are no test cases for which no categories of sports are selected
- There is only one test case that combines two categories of sports (Test Case 6: Yes/No/Yes/No)
In spite of these apparent drawbacks, n-wise testing is a great way to test multiple parameters. The tester needs to be aware of the pros and cons of the technique and, if necessary, adapt or augment the resulting tests accordingly.
Remember: there is no single testing technique that can reliably identify all the defects in a system. You will always need to apply a selection of testing techniques that are suited to the test object at hand.
Leave a Reply