Functional Testing of Complex Conditions

Revision 1.0 by Dmitry Mugtasimov

Disclaimer: Readers may use the provided information and bundled software at their own risk. In no
event shall the author be liable for any damage or loss caused by any use or misuse of the provided
information or bundled software.

Introduction
Functional testing is not a complicated problem for short complex conditions. However, as complex
conditions increase in size, designing a good test set can become a nightmare.

I faced this problem while testing a loan processing system that turned out to be very complicated. It was
implementing a long and branchy business process. Transitions between stages were conditional and the
conditions were complex. Many of them combined more than eight simple conditions. I could not use an
intuitive approach to design tests for these transitions. The increase of the problem complexity required a
qualitative change in the level of formalization. The first steps of formalization were done during the
project and helped to accomplish the task. Later I decided to write an article describing the approach in a
formal yet understandable way. My special thanks to Olga Sharay for her invaluable feedback that really
helped to make this article better.

The article describes a test set generation algorithm for a given complex condition. There are intuitive and
strict descriptions of the algorithm. An intuitive description is useful to catch the general idea of the
algorithm and to design test sets for comparatively short complex conditions. A strict description may be
applied to any longer complex conditions.

Complex Condition
A complex condition is a logical condition that contains two or more simple conditions properly combined
with brackets, AND and OR logical operators.

Complex condition examples:

• Class = "Qualified" AND Score => 500
• (Department = "Sales" AND Volume > 30000) OR (Department = "Marketing" AND Salary >
1500) OR (Location = "Moscow" AND (Position = "Senior Engineer" OR StartDate <
#01.01.2005#))

Simple conditions are underlined in the examples. A simple condition is a logical condition that may be
estimated to be TRUE or FALSE and does not contain AND and OR logical operators.

Simple condition examples:

• Department = "Sales"
• Volume > 30000
• a * (b + c) < d * e
• Name LIKE 'D%'
• Region NOT IN ('Moscow', 'SPB')
• IsNull(Age)
• Traveled to Spain more than twice
1
These examples show that a simple condition may contain any special comparison operators, functions
and even textual descriptions.

Common Problem Statement

A specification of a complex condition is given. Design a non-redundant test set to check that the complex
condition is implemented as specified.

Intuitive Solution
The algorithm is based on three simple ideas:
• Assume that the specified complex condition is implemented by using AND, OR and brackets (not
as a truth table).
• Test each simple condition independently.
• Avoid false positives and false negatives while testing each simple condition.

These ideas lead to a simple strategy. Identify simple conditions. For each simple condition fix variables
of other simple conditions in values that make the whole complex condition dependent only on the chosen
simple condition. Thus, if the chosen simple condition is TRUE, then the whole complex condition is
TRUE and if the chosen simple condition is FALSE, then the whole complex condition is FALSE. It
makes two tests out of each simple condition. Some tests are duplicated, so keep only distinct tests.

For example, the given complex condition is Department = "Sales" AND Volume > 30000. Simple
conditions are underlined.

Start with Department = "Sales". There is only one other simple condition Volume > 30000. This simple
condition should be equal to TRUE, because otherwise the whole complex condition does not depend on
Department = "Sales". For example, for Volume = 30000 the complex condition will always be equal to
FALSE regardless of the value of Department. If Volume > 30000, say Volume = 30001, then the whole
complex condition does depend on Department = "Sales". If Department = "Sales" is TRUE, then the
whole complex condition is TRUE too. If the simple condition is FALSE, say Department = "Marketing",
then the whole complex condition is FALSE, as well.

Thus there are two tests for the first simple condition:
• Department = "Sales", Volume = 30001
• Department = "Marketing", Volume = 30001

The second condition also makes two tests:

• Department = "Sales", Volume = 30001
• Department = "Sales", Volume = 30000

The test Department = "Sales", Volume = 30001 is duplicated, thus it is included in the final test set only
once:
• Department = "Sales", Volume = 30001
• Department = "Marketing", Volume = 30001
• Department = "Sales", Volume = 30000

This intuitive approach is good to catch the idea of the algorithm and may be used for short complex
conditions. Unfortunately, it fails on longer complex conditions. Strict description solves this problem.

2
Strict Description of the Algorithm
The algorithm operates on a tree built from a given complex condition. If the reader is not familiar with
tree data structure and related terminology, I refer him or her to the Wikipedia article "Tree (data
structure)".

There are three high level steps:

1. Prepare data structure required for the algorithm.
2. Apply the algorithm
3. Express tests in terms of actual variables

Prepare data structure

The algorithm works on a tree representing a given complex condition. Prepare the tree according to
description in the next paragraph.

Identify and name simple conditions. Identify logical operators. Create a tree that satisfies the following
description. A logical operator which is applied the last becomes the root node (or just root). Operands of
each logical operator become its child nodes (or children) that makes all logical operators internal nodes
(or just nodes) and all simple conditions leaf nodes (or just leaves). If the same logical operators have the
same priority, then they merge into the same node and their operands become children of this node.

See the examples in Table 1 for clarification.

Table 1 – Example Trees

Complex Condition Representing Tree
Department = "Sales" AND Volume > 30000 Cond1
Department = "Sales "
AND
Cond1: Department = "Sales"
Cond2: Volume > 30000 Cond2
Volume > 30000

Department = "Sales" AND Two ANDs merged into one node with 3 children:
Volume > 30000 AND Cond1
Position = "Sale" Department = "Sales "

Cond1: Department = "Sales" Cond2

AND
Cond2: Volume > 30000 Volume > 30000
Cond3: Position = "Sale"
Cond3
Position = "Sale"

3
 Complex Condition Representing Tree
Department = "Sales" AND Volume > 30000 Cond1
OR Department = "Sales "
AND
Department = "Marketing" AND Salary > 1500
Cond2
Cond1: Department = "Sales" Volume > 30000
OR
Cond2: Volume > 30000
Cond3: Department = "Marketing" Cond3
Cond4: Salary > 1500 Department = "Marketing"
AND

Cond4
Salary > 1500

Apply the algorithm

The algorithm operates on the tree which is built on the previous step. The algorithm contains an external
loop (1) which iterates over simple conditions, internal loop and recursion. Internal loop (1.3) iterates over
marked nodes. Recursion (1.4) iterates over nodes with assigned value. The recursion is required, because
each of its iterations may produce new nodes with assigned value which should also be iterated over.

Step-by-step description of the algorithm:

1. For each simple condition in the tree do:
1.1. Draw a path from the root of the tree to the simple condition
1.2. Mark nodes on the path
1.3. For each marked node do:
1.3.1. If the marked node is OR operator then assign FALSE to its direct not marked children
1.3.2. If the marked node is AND operator then assign TRUE to its direct not marked children
1.4. Recursively for each node with assigned value do (until all not marked nodes have an assigned
value):
1.4.1. If the assigned value of the node is FALSE then assign FALSE to all its direct children
1.4.2. If the assigned value of the node is TRUE and the node is OR operator then assign TRUE
to one of its direct children and FALSE to the other direct children
1.4.3. If the assigned value of the node is TRUE and the node is AND operator then assign TRUE
to all its direct children
1.5. Set simple conditions to their assigned values
1.6. Set marked simple condition to TRUE
1.7. Store values of simple conditions as a positive test
1.8. Set marked simple condition to FALSE
1.9. Store values of simple conditions as a negative test
1.10. Reset path, mark up and assigned values
2. Identify duplicates and keep only distinct tests

Demonstration of the algorithm is given in this article as a solution to an example problem.

Express tests in terms of actual variables

The algorithm creates tests in terms of simple conditions. However, their values cannot be entered into the
system directly. Thus tests should be expressed in terms of actual variables which are used in the complex
condition.

4
For example, for a given complex condition, Department = "Sales" AND Volume > 30000, tests may be
represented in terms of simple conditions as shown in Table 2.

Table 2 – Tests in terms of simple conditions

Condition Name Condition Definition Positive Negative
Test Tests
1 2 3
Cond1 Department = "Sales" 1 0 1
Cond2 Volume > 30000 1 1 0
Complex Condition Department = "Sales" AND Volume > 30000 1 0 0
(expected result)
Legend: 1 – TRUE, 0 – FALSE

In order to express tests in terms of actual variables, we should choose such values of actual variables that
make the simple condition TRUE or FALSE according to the test definition. Table 3 represents tests in
terms of actual variables.

Table 3 – Tests in terms of actual variables

Condition Name Condition Definition Actual Positive Negative Tests
Variable Test
1 2 3
Cond1 Department = "Sales" Department Sales Marketing Sales
Cond2 Volume > 30000 Volume 30001 30001 30000
Complex Condition Department = "Sales" – TRUE FALSE FALSE
(expected result) AND Volume > 30000

Once tests in terms of actual variables are ready they can be implemented as manual, data-driven or
automated tests.

Example Problem
The example problem is more complex than previous examples. This intends to show that the algorithm
can be applied to longer complex conditions. The solution to the problem will take you through a full path
from problem statement to a final test set.

Problem statement
The system under test should be implemented according to the given specification. The specification says
that the employee is eligible for an annual bonus if he or she satisfies the following complex condition:
(Department = "Sales" AND Volume > 30000) OR
(Department = "Marketing" AND Salary > 1500) OR
(Location = "Moscow" AND
(Position = "Senior Engineer" OR StartDate < #01.01.2005#))

Design a non-redundant test set to check that the complex condition is implemented as specified.

5
Problem solution
Identify and name simple conditions:
(Department = "Sales" AND Volume > 30000) OR
(Department = "Marketing" AND Salary > 1500) OR
(Location = "Moscow" AND
(Position = "Senior Engineer" OR StartDate < #01.01.2005#))

Cond1: Department = "Sales"

Cond2: Volume > 30000
Cond3: Department = "Marketing"
Cond4: Salary > 1500
Cond5: Location = "Moscow"
Cond6: Position = "Senior Engineer"
Cond7: StartDate < #01.01.2005#

Rewrite the complex condition in terms of the defined simple conditions:

(Cond1 AND Cond2) OR
(Cond3 AND Cond4) OR
(Cond5 AND (Cond6 OR Cond7))

Represent the complex condition as a tree. See Figure 1.

Cond1
Department = "Sales "
AND

Cond2
Volume > 30000

Cond3
Department = "Marketing"
OR AND

Cond4
Salary > 1500

Cond5
Location = "Moscow"
AND

Cond6
Position = "Senior Engineer "
OR

Cond7
StartDate < #01.01.2005 #

Figure 1

6
Apply the algorithm. See Table 4.

Table 4 – Step-by-step algorithm application

Step Result
1. For each simple condition in the tree do Cond1, Cond2, Cond3, Cond4, Cond5, Cond6, Cond7
ITERATION 1: Cond1
1.1. Draw a path from the root of the Cond1
Department = "Sales "
AND
tree to the simple condition
Cond2
Volume > 30000

Cond3
Department = "Marketing"
OR AND

Cond4
Salary > 1500

Cond5
Location = "Moscow"
AND

Cond6
Position = "Senior Engineer "
OR

Cond7
StartDate < #01.01.2005 #

1.2. Mark nodes on the path Cond1

Department = "Sales"
AND

Cond2
Volume > 30000

Cond3
Department = "Marketing "
OR AND

Cond4
Salary > 1500

Cond5
Location = "Moscow"
AND

Cond6
Position = "Senior Engineer "
OR

Cond7
StartDate < #01.01.2005#

1.3. For each marked node do Cond1

Department = "Sales"

1.3.1. If the marked node is AND

T

OR operator then assign Cond2

Volume > 30000

FALSE to its direct not

Cond3
marked children OR
F
AND
Department = "Marketing "

1.3.2. If the marked node is Cond4

AND operator then assign Salary > 1500

TRUE to its direct not Cond5

F
Location = "Moscow"
marked children AND

Cond6
Position = "Senior Engineer "
OR

Cond7
StartDate < #01.01.2005#

7
 Step Result
1.4. Recursively for each node with First level of recursion
assigned value do (until all not Cond1
Department = "Sales"

marked nodes have an assigned AND

T

value) Cond2
Volume > 30000

1.4.1. If the assigned value of F

Cond3
the node is FALSE then OR
F
AND
Department = "Marketing "

assign FALSE to all its direct F

Cond4
children Salary > 1500

1.4.2. If the assigned value of F

Cond5
F
Location = "Moscow"
the node is TRUE and the AND

node is OR operator then F

Cond6
Position = "Senior Engineer "
assign TRUE to one of its OR

direct children and FALSE to Cond7

StartDate < #01.01.2005#

the other direct children

1.4.3. If the assigned value of
Second level of recursion
the node is TRUE and the Cond1
node is AND operator then AND
Department = "Sales"

assign TRUE to all its direct T

Cond2
Volume > 30000
children
F
Cond3
F
Department = "Marketing "
OR AND
F
Cond4
Salary > 1500

F
Cond5
F
Location = "Moscow"
AND
F
Cond6
F
Position = "Senior Engineer "
OR
F
Cond7
StartDate < #01.01.2005#

1.5. Set simple conditions to their Cond2..Cond7 are set to T, F, F, F, F, F respectively.

assigned values
1.6. Set marked simple condition to Cond1 is set to TRUE
TRUE T
T
Cond1
Department = "Sales"
AND
T
Cond2
Volume > 30000

F
Cond3
T F
Department = "Marketing "
OR AND
F
Cond4
Salary > 1500

F
Cond5
F
Location = "Moscow"
AND
F
Cond6
F
Position = "Senior Engineer "
OR
F
Cond7
StartDate < #01.01.2005#

1.7. Store values of simple Positive test Cond1..Cond7: T, T, F, F, F, F, F

conditions as a positive test

8
 Step Result
1.8. Set marked simple condition to Cond1 is set to FALSE
FALSE F
F
Cond1
Department = "Sales"
AND
T
Cond2
Volume > 30000

F
Cond3
F F
Department = "Marketing "
OR AND
F
Cond4
Salary > 1500

F
Cond5
F
Location = "Moscow"
AND
F
Cond6
F
Position = "Senior Engineer "
OR
F
Cond7
StartDate < #01.01.2005#

1.9. Store values of simple Negative test Cond1..Cond7: F, T, F, F, F, F, F

conditions as a negative test
1.10. Reset path, mark up and Before reset
assigned values T, F
T, F
Cond1
Department = "Sales"
AND
T
Cond2
Volume > 30000

F
Cond3
T, F F
Department = "Marketing"
OR AND
F
Cond4
Salary > 1500

F
Cond5
F
Location = "Moscow"
AND
F
Cond6
F
Position = "Senior Engineer "
OR
F
Cond7
StartDate < #01.01.2005 #

After reset
Cond1
Department = "Sales "
AND

Cond2
Volume > 30000

Cond3
Department = "Marketing"
OR AND

Cond4
Salary > 1500

Cond5
Location = "Moscow"
AND

Cond6
Position = "Senior Engineer "
OR

Cond7
StartDate < #01.01.2005 #

9
 Step Result
ITERATION 2: Cond2 Positive test Cond1..Cond7: T, T, F, F, F, F, F
Negative test Cond1..Cond7: T, F, F, F, F, F, F
T
Cond1
T, F
Department = "Sales"
AND
T, F
Cond2
Volume > 30000

F
Cond3
T, F F
Department = "Marketing"
OR AND
F
Cond4
Salary > 1500

F
Cond5
F
Location = "Moscow"
AND
F
Cond6
F
Position = "Senior Engineer "
OR
F
Cond7
StartDate < #01.01.2005 #

ITERATION 3: Cond3 Positive test Cond1..Cond7: F, F, T, T, F, F, F

Negative test Cond1..Cond7: F, F, F, T, F, F, F
F
Cond1
F
Department = "Sales"
AND
F
Cond2
Volume > 30000

T, F
Cond3
T, F T, F
Department = "Marketing "
OR AND
T
Cond4
Salary > 1500

F
Cond5
F
Location = "Moscow"
AND
F
Cond6
F
Position = "Senior Engineer "
OR
F
Cond7
StartDate < #01.01.2005 #

ITERATION 4: Cond4 Positive test Cond1..Cond7: F, F, T, T, F, F, F

Negative test Cond1..Cond7: F, F, T, F, F, F, F
F
Cond1
F
Department = "Sales"
AND
F
Cond2
Volume > 30000

T
Cond3
T, F T, F
Department = "Marketing"
OR AND
T, F
Cond4
Salary > 1500

F
Cond5
F
Location = "Moscow"
AND
F
Cond6
F
Position = "Senior Engineer "
OR
F
Cond7
StartDate < #01.01.2005 #

10
 Step Result
ITERATION 5: Cond5 Positive test Cond1..Cond7: F, F, F, F, T, T, F
Negative test Cond1..Cond7: F, F, F, F, F, T, F
F
Cond1
F
Department = "Sales"
AND
F
Cond2
Volume > 30000

F
Cond3
T, F F
Department = "Marketing"
OR AND
F
Cond4
Salary > 1500

T, F
Cond5
T, F
Location = "Moscow "
AND
T
Cond6
T
Position = "Senior Engineer "
OR
F
Cond7
StartDate < #01.01.2005 #

ITERATION 6: Cond6 Positive test Cond1..Cond7: F, F, F, F, T, T, F

Negative test Cond1..Cond7: F, F, F, F, T, F, F
F
Cond1
F
Department = "Sales"
AND
F
Cond2
Volume > 30000

F
Cond3
T, F F
Department = "Marketing"
OR AND
F
Cond4
Salary > 1500

T
Cond5
T, F
Location = "Moscow"
AND
T, F
Cond6
T, F
Position = "Senior Engineer"
OR
F
Cond7
StartDate < #01.01.2005 #

ITERATION 7: Cond7 Positive test Cond1..Cond7: F, F, F, F, T, F, T

Negative test Cond1..Cond7: F, F, F, F, T, F, F
F
Cond1
F
Department = "Sales"
AND
F
Cond2
Volume > 30000

F
Cond3
T, F F
Department = "Marketing"
OR AND
F
Cond4
Salary > 1500

T
Cond5
T, F
Location = "Moscow"
AND
F
Cond6
T, F
Position = "Senior Engineer "
OR
T, F
Cond7
StartDate < #01.01.2005 #

11
 Step Result
2. Identify duplicates and keep only Positive tests: Negative tests:
distinct tests T, T, F, F, F, F, F* F, T, F, F, F, F, F*
T, T, F, F, F, F, F T, F, F, F, F, F, F*
F, F, T, T, F, F, F* F, F, F, T, F, F, F*
F, F, T, T, F, F, F F, F, T, F, F, F, F*
F, F, F, F, T, T, F* F, F, F, F, F, T, F*
F, F, F, F, T, T, F F, F, F, F, T, F, F*
F, F, F, F, T, F, T* F, F, F, F, T, F, F

* – distinct tests
Legend: T – TRUE, F – FALSE

Table 5 represents tests in terms of simple conditions.

Table 5 – Tests in terms of simple conditions

Simple Positive Tests Negative Tests
Condition 1 2 3 4 5 6 7 8 9 10
Cond1 1 0 0 0 0 1 0 0 0 0
Cond2 1 0 0 0 1 0 0 0 0 0
Cond3 0 1 0 0 0 0 0 1 0 0
Cond4 0 1 0 0 0 0 1 0 0 0
Cond5 0 0 1 1 0 0 0 0 1 0
Cond6 0 0 1 0 0 0 0 0 0 1
Cond7 0 0 0 1 0 0 0 0 0 0
Complex TRUE TRUE TRUE TRUE FALSE FALSE FALSE FALSE FALSE FALSE
Condition
(expected
result)
Legend: 1 – TRUE, 0 – FALSE

Table 6 contains conversion to actual variables for all simple conditions. Using this table it is easy to
express tests in terms of actual variables. If you need a simple condition to be TRUE or FALSE according
to the test definition, just take actual variables from the corresponding cell. Alternatively you may
generate values online each time you need them.

Table 6 – Conversion from simple conditions to actual variables

Simple Simple Condition Definition Actual Variables
Condition For TRUE For FALSE
Cond1 Department = "Sales" Department = "Sales" Department = "Marketing"
Cond2 Volume > 30000 Volume = 30001 Volume = 30000
Cond3 Department = "Marketing" Department = "Marketing" Department = "Sales"
Cond4 Salary > 1500 Salary = 1501 Salary = 1500
Cond5 Location = "Moscow" Location = "Moscow" Location = "New York"
Cond6 Position = "Senior Engineer" Position = "Senior Engineer" Position = "Sale"
Cond7 StartDate < #01.01.2005# StartDate = 31.12.2004 StartDate = TODAY

12
Final manual Test 1 is shown in Table 7. This test may be delivered to a test engineer for execution.

Table 7 – Implementation of Test 1

Step Description Expected Result Comments
Create a new employee with the New employee is successfully created with Step provides Cond1,
following attributes: attributes: Cond3, Cond4, Cond5
• Department = "Sales" • Department = "Sales" and Cond6 explicitly.
• Salary = 1500 • Salary = 1500 Cond7 is provided
• Location = "New York" • Location = "New York" implicitly by creating
• Position = "Sale" • Position = "Sale" an employee TODAY.
Create a new contract for 30 001 1. New contract for 30 001 USD is Step provides Cond2.
USD on behalf of the created successfully created.
employee. 2. New contract belongs to the employee.
Run annual bonus report. The new employee is included in the Step checks the
annual bonus report. expected result.

Does the Algorithm Really Work?

It can be shown experimentally that the test set generated by the algorithm detects most of the real life
defects. Table 8 contains 10 implementations of complex conditions specified in the example problem.
There are one correct and nine buggy implementations. The rightmost column contains tests that detect the
defect (failed tests).

Table 8 – Complex condition implementation

Correct (Department = "Sales" AND Volume > 30000) OR None:
Implementation (Department = "Marketing" AND Salary > 1500) OR correct
(Location = "Moscow" AND (Position = "Senior implementa-
Engineer" OR StartDate < #01.01.2005#)) tion
Buggy 0: (Department = "Sales" ANDOR Volume > 30000) OR Failed tests:
wrong logical (Department = "Marketing" AND Salary > 1500) OR 5, 6
operator (Location = "Moscow" AND (Position = "Senior
Engineer" OR StartDate < #01.01.2005#))
Buggy 1: (Department = "Sales" AND Volume >= 30000) OR Failed tests:
wrong (Department = "Marketing" AND Salary > 1500) OR 6
comparison (Location = "Moscow" AND (Position = "Senior
operator Engineer" OR StartDate < #01.01.2005#))
Buggy 2: (Department = "Sales" AND Volume > 30000) ORAND Failed tests:
wrong logical (Department = "Marketing" AND Salary > 1500) OR 1, 2
operator (Location = "Moscow" AND (Position = "Senior
Engineer" OR StartDate < #01.01.2005#))
Buggy 3: (Department = "Sales" AND Volume > 30000) OR Failed tests:
wrong variable (Department = "Marketing" AND SalaryVolume > 8
1500) OR
(Location = "Moscow" AND (Position = "Senior
Engineer" OR StartDate < #01.01.2005#))
Buggy 4: (Department = "Sales" AND Volume > 30000) OR Failed tests:
wrong (Department = "Marketing" AND Salary >< 1500) 2
comparison OR
operator (Location = "Moscow" AND (Position = "Senior
Engineer" OR StartDate < #01.01.2005#))

13
 Buggy 5: (Department = "Sales" AND Volume > 30000) OR Failed tests:
wrong constant (Department = "Marketing" AND Salary > 8
15001490) OR
(Location = "Moscow" AND (Position = "Senior
Engineer" OR StartDate < #01.01.2005#))
Buggy 6: (Department = "Sales" AND Volume > 30000) OR Failed tests:
wrong (Department = "Marketing" AND Salary > 1500) OR 3, 4, 10
comparison (Location =<> "Moscow" AND (Position = "Senior
operator Engineer" OR StartDate < #01.01.2005#))
Buggy 7: (Department = "Sales" AND Volume > 30000) OR Failed tests:
missed simple (Department = "Marketing" AND Salary > 1500) OR 3
condition (Location = "Moscow" AND (Position = "Senior
Engineer" OR StartDate < #01.01.2005#))
Buggy 8: (Department = "Sales" AND Volume > 30000) OR None:
Extra simple (Department = "Marketing" AND Salary > 1500) OR defect
condition (Location = "Moscow" AND (Position = "Senior remained
Engineer" OR StartDate < #01.01.2005#)) OR undetected
Status = "Retired"
Buggy 9: (Department = "Sales" AND Volume > 30000) OR Failed tests:
Extra simple (Department = "Marketing" AND Salary > 1500) OR 3, 4
condition (Location = "Moscow" AND (Position = "Senior
Engineer" OR StartDate < #01.01.2005#)) AND
Status = "Retired"

The table shows that many defects are detected by positive tests. It also shows that some defects are
detected only by negative tests. Finally, it shows that most of the defects are detected by the generated test
set.

There is "Buggy 8" implementation containing a defect which remained undetected. This issue is
discussed in the next section.

Test set and complex condition variants are implemented in Java and bundled with this article in the form
of binaries and source code. The reader may run the test set automatically to ensure the results. Optionally,
the reader may create their own buggy implementations of complex condition to check the algorithm.
Technical details can be found in the supplied documentation.

Algorithm Properties
The described algorithm is good enough for most real life applications. The generated test set checks that
each simple condition is implemented as specified and all simple conditions are combined by logical
operators and bracket as specified.

The algorithm properties include advantages and disadvantages, possibilities and limitations, special and
exceptional cases and other remarkable points which are discussed in this section.

14
Remarkable advantages of the algorithm:
• Generated test set detects most real life defects
• Small number of tests
• Successful on long complex conditions
• Predictable quality of test set
• Allows automated test set generation

Predictable quality is achieved by detection of certain kinds of defects:

• Missing simple condition
• Incorrect simple condition
• Incorrect logical operator
• Incorrect brackets (with limitations)

The algorithm generates a small number of tests compared to all possible combinations of input values. In
the example problem there are 7 simple conditions, each taking one of two possible values. The number of
all possible combinations is 27 = 128 which means 128 tests to achieve full coverage. With the described
algorithm this number is reduced to 10 tests.

An intuitive approach that may be used for short complex conditions fails for longer ones. The described
algorithm may be used for complex conditions of any length.

Automated test set generation is allowed by implementing the described algorithm as a computer program.
This article is bundled with an implementation in Java.

Disadvantages of the algorithm sum up of its limitations, special and exceptional cases.

The most significant limitation is that the algorithm does not guarantee detection of extra simple
conditions. In "Buggy 8" implementation (Table 8) there is an extra simple condition "Status = "Retired".
The algorithm did not generate any test to detect the defect. Such behavior comes from the nature of the
coverage scheme accepted for specification-based testing. The simple condition "Status = "Retired" was
not specified as a part of the complex condition, so no special test is created to check that it exists or not.
Detection of overimplemented features is an infinitively complex task, because it is never known what and
in which way it was overimplemented. Because of this, the described limitation should not be solely
considered as a limitation of the algorithm, but as a general limitation of specification-based functional
testing.

Although the generated test set does not guarantee detection of extra simple conditions, they still may be
detected. The probability of detection depends on logical operators, variables and their default values. For
example, in the "Buggy 9" implementation (Table 8) such a defect was successfully detected.

A second important limitation comes from the assumption that the specified complex condition is
implemented by using AND, OR and brackets, but not as a truth table. An assumed implementation puts
restrictions, which allows a decrease in the number of tests. If the specified complex condition is
implemented as a truth table, the test set should include all combinations of inputs id order to be reliable.

Another limitation of the algorithm is an assumption that simple conditions do not depend on each other.
The algorithm says nothing about cases when simple conditions can not be set independently. In such
cases, dependencies should be resolved manually. For example, for complex conditions, (Department =
"Sales" AND Volume > 30000) OR (Department = "Sales" AND Salary > 1500) it is impossible to set
first underlined simple condition to TRUE and second to FALSE. Both simple conditions are either TRUE

15
or FALSE. In other cases, conditions may depend on each other in a more complicated way that is even
harder to resolve. This article does not describe how to resolve such dependencies.

The algorithm is limited to AND and OR logical operators. If other logical operators are used in a
complex condition (i.e. NOT, XOR), they are considered as a part of simple condition. For example, in "A
> 30 AND NOT B > 0 XOR C = 3" there are two simple conditions "A > 30" and "NOT B > 0 XOR C =
3". In practice XOR is almost never used in business logic and there is no problem in considering NOT as
a part of simple condition.

There is a known limitation in detecting of wrong brackets. If a complex condition is specified as Cond1
AND (Cond2 OR Cond3) or (Cond1 OR Cond2) AND Cond3, then the omission of brackets may not be
detected. There is a simple workaround for that. For first complex condition ensure that the test set
contains these negative tests: { Cond1 = F; Cond2 = T; Cond3 = F }, { Cond1 = F; Cond2 = F; Cond3 = T
}. For second complex condition ensure that the test set contains these negative tests: { Cond1 = T; Cond2
= F; Cond3 = F }, { Cond1 = F; Cond2 = T; Cond3 = F }. For complex condition from the example
problem one more negative test should be added: { Cond1..Cond7: F, F, F, F, F, F, T }.

There are a couple of notes on providing value for actual variables.

First of all, it is important to provide values for all variables involved in complex condition. It guarantees
the absence of false positives and false negatives. For example, for complex condition A = 0 OR B = 0 it
is essential to keep B not equal to 0 when testing the case of A = 0, otherwise it is not clear which simple
condition made the complex condition TRUE.

Another important point is choosing values for actual variables. Boundary values are preferable, because
they allow detection of wrong strict or not strict inequality operators. See "Buggy 1" implementation
(Table 8) as an example of such a defect.

Note that some of the defects can be detected by only one test in the test set. For this reason any regression
testing should include the complete test set.

Algorithm Implementation
The described algorithm is implemented as a Java console application and bundled with this article in the
form of binaries and source code. It generates test set in terms of simple conditions. The reader may use
the implementation at their own risk. Modifications to source code are permitted only in the case of
keeping the original copyright record. For technical details, please refer to the supplied documentation.

Conclusion
The described algorithm allows test engineers to generate a non-redundant test set for a specified complex
condition. It is good enough for practical purposes, especially on long complex conditions. The algorithm
may be performed either manually or automatically with the help of the supplied software
implementation.

Any feedback, questions or comments on any part of the article, including the supplied software, is
appreciated.

© 2007 Dmitry Mugtasimov

16