An Analysis of Combinatorial Test Design Techniques

I will omit to discuss here well-known and widely used test design techniques such as Equivalence Classes, Boundary Value Testing, and Pairwise Testing, I will discuss other, less common techniques. You can also read my article about issues with combinatorial test design techniques.

Decision Table Testing

Decision Tables are an excellent tool for documenting requirements and describing the functionality of an application. These tables are very convenient for describing the business logic of the application, and in addition to that, they can serve as a solid foundation for creating test cases. If the tested application lacks proper documentation, it is a good reason to use Decision Tables. Presenting requirements in a compact and simple form makes it quite easy to create test cases.

Approach:

Decision Tables describe the logic of the application based on the entities (properties/conditions) of the system state. Each decision table should only describe one state of the system.

Entity (Property) from 1 to M represents various properties of the system; they are presented in the table as input data that can be entered into the system. Actions from 1 to P are actions that can occur with the specified combination of entities. Depending on the combination of all input data of entities, actions take on the necessary values. Each rule defines a unique set of input data for all properties that lead to the execution of specific actions.

After composing the decision table, it is usually possible to simplify the table, for example, by removing some or all of the impossible scenarios. Then, the table can be transformed into test cases.

State-Transition Testing

State-transition testing, like decision table testing, is a valuable tool for documenting requirements and describing the structure and design of a system. Unlike Decision tables testing, which describes a specific system state, State-Transition testing describes how these states of the system can change. Diagrams define all events that occur during the operation of the application and how the application responds to these events.

Approach:

There are two types of visual representations of this technique:

1. State-Transition Diagrams
2. State-Transition Tables

State-Transition Diagrams

As an example, let's consider the reservation of airline tickets. It operates roughly as follows: Initially, customers provide the airline with information for reservation - departure location, destination, date, and time of departure. An airline employee serves as the interface between the customer and the ticket reservation system, using the information provided by the customer to create a reservation. After that, the customer's reservation is in the "Made" state. Additionally, after creating the reservation, the system starts a timer. When the timer expires, and the reserved ticket has not been paid for, the system cancels the reservation for that ticket.

The circle represents the state of the airline ticket reservation system, the "Made" state. The arrow indicates a transition to the "Made" state. The description below the arrow ("get_info") is an event originating from outside the system. The command in the description below the arrow (after "/") signifies that the system performed some action in response to the event - in this case, initiating a timer. The black circle indicates the start/entry point of the diagram.

If the timer does not expire, and we have paid for the reserved ticket, the system enters the "Paid" state. This is depicted by the arrow labeled "payMoney" and the transition from the "Made" state to the "Paid" state.

• State (represented as a circle on the diagram): This is the state of the system where it awaits one or more events. The state remembers the input data received so far and indicates how the system will react to the received events. Events can trigger actions and/or lead to a change in state.
• Transition (represented on the diagram as an arrow): This represents a transition from one state to another, occurring due to an event.
• Event (represented as a rectangle above the arrow): An event is something that causes the application to change its state. Events can come from outside the application, such as through the application's user interface. Simultaneously, the application itself can generate events, for example, an event like "timer expired." When an event occurs, the application may stay in the same state, change state, or perform an action. Events can have parameters; for instance, the "pay_money" event may have parameters such as "Cash," "Check," "DebitCard," or "CreditCard."
• Action (represented after "/" in the label above the transition): This is an action initiated by a change in state. It could be actions like "print ticket," "display on screen," etc. Typically, actions create outputs that serve as the system's output data. Actions occur during transitions; states themselves are passive.
• The entry point is shown on the diagram as a black dot.
• The exit point is shown on the diagram as a "bullseye" symbol.

State-Transition Tables

State-transition tables are tables that consist of four columns: Current State, Event, Action, and Next State.

The advantage of State-Transition Tables is that they define all possible State-Transition scenarios, not just the correct ones. Therefore, State-Transition Tables often lead to the discovery of undefined, undocumented State-Transition combinations, which are better to identify before writing the code.

• State-Transition Diagrams can be easily used for creating test cases. It is necessary to create a set of test cases that should cover all transitions at least once.
• From State-Transition Tables, it is also relatively straightforward to generate test cases. One needs to go through all valid combinations (if time allows or risks do not prohibit, it's possible to go through all invalid combinations as well).

Orthogonal Arrays

How many combinations exist for the pair of values "1" and "2"? {1,1}, {1,2}, {2,1}, and {2,2}. An orthogonal array is a two-dimensional array with a special property - in any two columns of the array, all combinations of values in those columns are present. That is, if you take any two columns from the orthogonal array, where values can only be "1" or "2", you will find the following rows for those columns - {1,1}, {1,2}, {2,1}, and {2,2}.

As an example, consider a system with three input parameters, each of which is binary (i.e., takes the value "1" or "2").

Orthogonal Array is represented as - L_4(2^3), where L_4 indicates that the orthogonal array has four rows, and (2^3) indicates that the array has three columns, with values that can be either "1" or "2".

L_4, where 4 is the number of rows

2^3, where 2 is the maximum value (== 2, 3, …, N) and 3 is the number of columns

Orthogonal Array - is a two-dimensional array with the following property: choose any two columns of the array, and you will find all combinations of values in those columns.

Using orthogonal arrays:

1. Identify variables (number of input data). It is necessary to select input data, any combinations of values which can logically exist.
2. Determine the number of values each variable can take. By the time the number of values is determined, other test design techniques should have already been applied to reduce the number of values (e.g., boundary values, equivalence classes, and any others).
3. Determine an orthogonal array where there will be a column for each variable (the column of the orthogonal array has as many value options as the variable).
4. Project the testing task onto the orthogonal array.
5. Write test cases.

AllPairs Algorithm

The essence of the AllPairs algorithm is that there is no need to test all combinations of values for all variables. Instead, it focuses on testing all combinations of values for each pair of variables.