Introduction to Combinatorial Testing
In this section we will explain the basic concepts regarding Combinatorial Testing.
System Under Test (SUT)
Imagine that we are working on an online service that offers a web page and a mobile application, both parts sharing the same code base.
We are interested on finding potential bugs on these platforms before releasing them. To achieve that, we want to run several tests in our application to catch as many failures as possible, and from now on we will refer to the application that we are testing as System Under Test (SUT).
Let’s define the set of parameters that our SUT exposes:
Notice that there are a set of combinations that do not make sense to be applied in our SUT:
Whenever the OS is Linux, Windows or Mac, the Orientation must be Landscape and the Platform cannot be App.
When the Platform is Safari, the OS must be Mac or iOS.
For iOS and Android the Resolution cannot be 4K.
We can specify those constraints using Propositional Logic:
Note
We define a System Under Test (SUT) as a system that exposes a finite set of parameters p of finite domain (called SUT parameters), and a set of constraints \(\varphi\) that implicitly represent the parameterizations that the system accepts (called SUT constraints).
Test cases, parameter tuples and \(t\)-tuples
Now that we have our SUT perfectly defined, we can start thinking on how to test it.
A Test case for our SUT will be a complete assignment of values for each one of the parameters of our SUT. For example, \(\{(OS, W), (Pl, F), (Re, K), (Or, L)\}\) would be a possible test case.
Taking into account the definition of our SUT, we could generate a Test suite of 160 test cases that will exhaustively test all the combinations of our four parameters and their values. From these 160 test cases, we must remove the ones that are not consistent with our SUT constraints (for example, all the test cases that have \((OS, A)\) and \(Re, K\)). After applying this filter we will reduce our test suite to 70 tests.
Note
Notice that, although in this simple example we could try to apply all these test cases, it is usually impractical to exhaustively test our SUT. For example, for the gcc compiler (which has 189 parameters of domain 2 and 10 of domain 3), we would need more than \(4.6 \cdot 10^{61}\) tests (if we consider that a test needs 1s to be executed, we would need \(1.5 \cdot 10^{54}\) years).
We can try to reduce the size of our test suite by relaxing our problem. Now, instead of exhaustively testing all the possible combinations in our SUT, we will test all the combinations of just \(t\) parameters.
Here we are making the reasonable assumption that failures are produced by the interaction of few parameters, so they can be detected by just testing the interaction of small subsets of parameters.
For our example we will consider interactions of 2 parameters. We refer to the size of the interactions that we are considering as the strength (also refered as \(t\)). In particular, we will consider the following combinations of parameters (what we call parameter tuples):
For each one of these parameter tuples, we have to test all the valid combinations of its values (what we call t-tuples). For example, for the \((Pl, Or)\) parameter tuple, we have the following \(t\)-tuples for strength \(t=2\):
By applying the same principle to the remaining parameter tuples we find that there are 82 \(t\)-tuples for \(t=2\) in our SUT. From these 82 tuples, there are 69 allowed tuples (i.e. they are consistent with the SUT constraints) and 13 forbidden tuples (i.e. they are not consistent with the SUT constraints).
Covering Arrays
As we have seen in the previous section, we needed 70 tests to exhaustively check the parameters of our SUT, and we had 69 \(2\)-tuples.
The first approach that we could take to reduce the number of test cases is to just test the \(2\)-tuples by creating a test case for each tuple, what will save use one test.
Note
If we apply a test case for each \(t\)-tuple in the gcc compiler we will reduce from \(4.6 \cdot 10^{61}\) to \(82,809\). It is a great improvement, but we can do it better!
However, notice that the rest of the parameters must have a value assigned (even if it is its default value). So we can reduce the number of tests by fitting several \(t\)-tuples in one test. For example, consider the example test case \(\{(OS, W), (Pl, F), (Re, K), (Or, L)\}\), where we can find the following \(2\)-tuples:
Then, we can improve the number of required test cases to test all the \(2\)-tuples by applying this principle through a matematical object that is called Covering Array (CA).
Note
We define a Covering Array (CA) (denoted by \(CA(N;t,S)\)) as a set of \(n\) test cases for a SUT model \(S\) such that all \(t\)-tuples are at least covered by one test case.
In particular, we focus on Mixed Covering Arrays with Constraints (MCAC), where Mixed means that parameters domains can have different cardinalities, and with Constraints that we support SUT constraints.
Building a Covering Array for a given SUT is a complex problem that we can solve using any of the state-of-the-art algorithms implemented in ctlog. In particular, here we present a Covering Array with just 22 test cases for our SUT:
OS |
Pl |
Re |
Or |
|---|---|---|---|
W |
F |
F |
L |
L |
C |
H |
L |
M |
F |
H |
L |
A |
C |
W |
P |
i |
S |
F |
P |
L |
F |
K |
L |
A |
A |
F |
L |
M |
C |
K |
L |
W |
C |
H |
L |
W |
C |
W |
L |
L |
C |
F |
L |
i |
F |
W |
P |
i |
A |
H |
P |
i |
C |
H |
L |
M |
S |
W |
L |
A |
F |
H |
L |
L |
C |
W |
L |
M |
S |
K |
L |
M |
S |
H |
L |
W |
F |
K |
L |
i |
A |
W |
L |
M |
F |
F |
L |
Note
For the gcc compiler, we can reduce the test suite to check all the valid interactions of 2 parameters from \(82809\) test cases to just \(15\) by building a CA.
Optimal Covering Arrays
In general, we will be interested on Covering Arrays as small as possible 1. Then, we might ask about which is the optimal CA for a given SUT and strength (i.e. the CA with the smallest number of test cases). This is what the Covering Array Number problem tries to solve:
Note
The Covering Array Number (CAN) (denoted by \(CAN(t,S)\)) is the minimum \(N\) for which there exists a \(CA(N;t,S)\).
The Covering Array Number problem is to find a CA of size \(CAN(t,S)\).
For our example, we can use the maxsat-mcac algorithm in ctlog to find an optimal CA, which will reduce from 22 test case to just 21:
OS |
Pl |
Re |
Or |
|---|---|---|---|
L |
C |
K |
L |
L |
F |
F |
L |
L |
C |
H |
L |
L |
C |
W |
L |
W |
F |
K |
L |
W |
C |
F |
L |
W |
F |
H |
L |
W |
F |
W |
L |
M |
S |
K |
L |
M |
S |
F |
L |
M |
C |
H |
L |
M |
F |
W |
L |
i |
C |
F |
P |
i |
S |
H |
P |
i |
S |
W |
P |
A |
A |
F |
L |
A |
A |
H |
P |
A |
F |
W |
P |
i |
A |
W |
L |
A |
C |
H |
L |
i |
F |
H |
L |
This has been a quick summary on the most important concepts on Combinatorial Testing that might be required to use ctlog. You can check the Hands-on CTLog section to see a hands-on example on how to practically apply ctlog to generate the CAs that we showed in this section.
Footnotes
- 1
If the execution of the test is quick and we want to scale to higher strength or SUTs with high number of parameters and domains, we might not care much about smaller CAs.