Figure 5-29 below shows how to evaluate the basis set of a graph. The graph is represented as an incidence matrix. Each row and column represents a node; a 1 is entered for each node pair connected by an edge.

We can use standard linear algebra techniques to identify the basis set of the graph. Each vector in the basis set represents a primitive path. We can form new paths by adding the vectors modulo 2. Generally, there is more than one basis set for a graph.

The basis set property provides a metric for test coverage. If we cover all the basis paths, we can consider the control flow adequately covered. Although the basis set measure is not entirely accurate since the directed edges of the CDFG may make some combinations of paths infeasible, it does provide a reasonable and justifiable measure of test coverage.

Figure 5-29. The matrix representation of a graph and its basis set.

There is a simple measure, cyclomatic complexity [McC76], which allows us to measure the control complexity of a program. Cyclomatic complexity is an upper bound on the size of the basis set earlier. If e is the number of edges in the flow graph, n the number of nodes, and p the number of components in the graph, then the cyclomatic complexity is given by

M = e - n +2p. (EQ 5-3)

For a structured program, M can be computed by counting the number of binary decisions in the flow graph and adding 1. If the CDFG has higher-order branch nodes, add b ' 1 for each b-way branch. In the example of Figure 5-30 below, the cyclomatic complexity evaluates to 4. Because there are actually only three distinct paths in the graph, cyclomatic complexity in this case is an overly conservative bound.

Another way of looking at control flow"oriented testing is to analyze the conditions that control the conditional statements. Consider the following if statement:

if ((a == b) || (c =d)) { ... }

Figure 5-30. Cyclomatic complexity.

This complex condition can be exercised in several different ways. If we want to truly exercise the paths through this condition, it is prudent to exercise the conditional's elements in ways related to their own structure, not just the structure of the paths through them. A simple condition testing strategy is known as branch testing [Mye79]. This strategy requires the true and false branches of a conditional and every simple condition in the conditional's expression to be tested at least once. Example 5-13 below illustrates branch testing.

Example 5-13. Condition Testing with the Branch Testing Strategy
Assume that the code below is what we meant to write.

if (a || (b = c)) { printf("OK\n"); }

The code that we mistakenly wrote instead follows:

if (a && (b=c)) {printf("OK\n");}

If we apply branch testing to the code we wrote, one of the tests will use these values: a = 0, b = 3, c = 2 (making a false and b = c true). In this case, the code should print theOK term [0 || (3 = 2) is true] but instead doesn't print [0 && (3 = 2) evaluates to false]. That test picks up the error.

Let's consider another more subtle error that is nonetheless all too common in C. The code we meant to write follows:

if ((x == good_pointer) && (x-field1 == 3)) { printf("got the value\n"); }

Here is the bad code we actually wrote:

if ((x = good_pointer) && (x-field1 == 3)) { printf("got the value\n"); }

The problem here is that we typed = rather than ==, creating an assignment rather than a test. The code x = good_pointer first assigns the value good_pointer to x and then, because assignments are also expressions in C, returns good_pointer as the result of evaluating this expression.

If we apply the principles of branch testing, one of the tests we want to use will contain x != good_pointer and x-field1 == 3. Whether this test catches the error depends on the state of the record pointed to by good_pointer. If it is equal to 3 at the time of the test, the message will be printed erroneously.

Although this test is not guaranteed to uncover the bug, it has a reasonable chance of success. One of the reasons to use many different types of tests is to maximize the chance that supposedly unrelated elements will cooperate to reveal the error in a particular situation.