Objectives.

Combinatorial Interaction Testing (CIT) is a black box system testing technique that samples inputs, configurations and parameters and combines them in a systematic fashion.

When used properly it can be a powerful tool in the hands of a software tester.

Goals:

1. Gain an understanding of the basic principles behind CIT.

2. Learn what makes CIT a powerful tool for software testers.

1

First let's take a look at the origins of CIT. The concepts behind CIT were first introduced in the mathematical study of Combinatorics.

Combinatorics is the study of enumeration, combination and permutation of sets of elements and the mathematical relations that characterize their properties.

Written around 300 BC the Bhagabati Sutra was one of the earliest books to feature a problem dealing with combinatorics.

The problem was that given 6 spices, how many ways were there to select combinations of one, two and three spices.
Let's solve using the choose function.

2

Choose function

Given a number n and a number r, where 0 ≤ r ≤ n, the choose function is a way of determining the number of distinct r-element subsets that exist within n-elements.
Mathematicaly it can be represented by the formula


Now lets solve the problem.

3

Given 6 different spices there are 6 different ways to choose 1 spice, 15 different ways to choose 2, and 20 different ways to choose 3 adding up to a total of 41 combinations.

The more common use of the choose function is found within Pascal's Triangle.

Pascal's Triangle is defined as a triangular array of the binomial coefficents in a triangle. This means that Pascal's Triangle can actually be created by using the choose function.

An example should illustrate what we mean.

4

Pascal's Triangle

5

Pascal's Triangle

6

Pascal's Triangle

7

The choose function is a very powerful tool in the study of statistics, which ties into combinatorics.

The next major step came with the Father of modern statistical science, Ronald Fisher.

R.A. Fisher was an english statistician whose work included a methodology for designing experiments that serves as the basis for many of the principals of CIT.

In addition, his work on "Studies in Crop Rotation" provide an excellent example of testing using orthogonal arrays.

8

The goal of these experiments was to find the effects of mixing different combinations of potato and fertilizer.
To do this the field was layed out in a grid broken up using an orthogonal array (these will be covered in a later tutorial).

The concept was radical because it provided a way to statistically analyise data that differed by a number of factors or combination of factors. The existing approach was changing one factor at a time which was relatively inefficent.

Now that you have some background knowledge on the subject let's turn our attention to the main topic, CIT.

9

One of the major aspects of CIT is finding out what to test.

For instance a web browser has many configurations that may change the way you view or access data over the web.

It is very important that all the configurations work with each other and do not negatively affect your ability to use the internet.

Let's take a closer look at a web browser example.

10

Web Browser Configuration

11

Web browser Configuration

12

Web browser Configuration

13

Here we have made a table of all the browser options and their possible settings.

In CIT the options are more commonly refered to as factors and their settings are either values or levels.

14

Web browser Configuration

15

Multiplying the first two columns,
We have 3 x 2 , or 6, possible configurations.

16

Web browser Configuration

17

For each of the 6 content values, we have 3 cookies values.

We multiply our previous 6 by 3 and we get 18 configuration possibilities.

18

Web browser Configuration

19

We continue to multiply all configuration options resulting in 144 configurations

20

Web browser Configuration

21

Once again, we multiply by 2 for each option resulting in a total of 576 configurations.

22

For each of the 576 configurations there can be a number of tests to run, clearly not the most efficient design.

CIT can be used to generate a much smaller amount of configurations that will not cover all combinations but instead will cover all pairwise combinations between factors.

The more difficult aspect of CIT is finding what the actual tests should be.

Before we go into that here is a quick question to make sure you understand how to find the number of configurations.

23

Quiz

Look at this example.

How many configurations are possible?

24

Here you can see how we multiplied all of our options to get the total number of configurations.

The question is what to do with this information?

25

Creating functional tests derived from software's specifications is not a new concept. In June of 1988 Thomas J. Ostrand and Marc J Balcer published a paper on The Category Partition Method for Specifying and Generating Functional Tests
The concepts in this paper served as an early guide to what CIT is accomplishing.

The Test Specifiaction Language outlined in the paper could be used to reduce the number of configurations by using constraints created by the tester.

For example a constraint on the quiz question might be that both Strikethrough and Double Strikethrough cannot selected at the same time.

26

However, because the constraints have to be entered by the tester the process is slow and in the end does not guarantee a reasonable set of configurations to test.

CIT will instead sample the exhaustive set of configurations by focusing on the interactions between factors. The sample size can be increased by increasing the strength of the interactions between factors.

This means that testing every pairwise combination will have less tests, but might not catch some problems that arise when testing all 3-way combinations

Let's look at an easy example and try to find the pairwise combinations by hand.

27

Paragraph Effects Configuration

28

Paragraph Effects Configuration

29

We multiply all values to get the total number of configurations which is 12

30

Paragraph Effects

31

Paragraph Effects

32

Paragraph Effects

33

Paragraph Effects

34

Paragraph Effects

35

Paragraph Effects

36

Paragraph Effects

37

In this small example it wasn't too difficult to create the pairwise covering array by hand, however when dealing with systems that thousands or even hundreds of configurations this is not feasable.

There exist a large number of generated arrays of varying strengths found online that can be referenced (Some examples found under links) in addition to programs that exist which can generate covering arrays given some input.

Remember the web configuration example that had 576 configurations?

Let's see how we might run it through a program

38

The goal is to create a covering array that will guarantee that all pairwise combinations of these factors will be tested.

To use a program we need to create a represention of this information that our program can read.

First we need to tell the program the strength of the covering array, in this case we want pairwise, so 2.

Next is the number of factors being tested. It's simple enough to count them and know we have 8.

39

Finally we need to go through all the factors in order and list the number of values each one has.

For instance, the first factor has 3 values, the second has 2 values, the third has 3 values, and the last five all have 2 values. Please note that in the actual generation of these arrays there are no commas between values.

Giving us this text representation.

2
8
3		, 1
2		, 1
3		, 1
2		, 5

40

Web Configuration

41

Web Configuration

42

Recap.

Combinatorial Interaction Testing is a powerful tool for testing with practical applications in Software Engineering.

By finding out the total number of possible configurations and then designing an array that tests pairwise configurations you can reduce the size of your test suite in an intelligent manner.

43