Statement Coverage

White-box testing is concerned with the degree to which test cases exercise or cover the logic (source code) of the program. The ultimate white-box test is the execution of every path in the program, but since in a program with loops the execution of every path is usually infeasible, complete path testing is not considered here as a viable testing goal.

If one backs completely away from path testing, it may seem that a useful coverage criterion is to require every statement in the program to be executed at least once. Unfortunately, this is a weak criterion, so we can say that writing enough test cases such that every statement is executed at least once is a necessary, but in no way sufficient, criterion for a reasonable white-box test.

Decision Coverage

A stronger logic-coverage criterion is known as decision coverage or branch coverage. This criterion states that one must write enough test cases such that each decision has a true and false outcome at least once. Another way of stating it is that each branch direction must be traversed at least once. Examples of branch or decision statements or DO statements (or PERFORM UNTIL in Cobol), IF statements, and multiway GO TO statements.

Decision coverage can be shown to usually satisfy statement coverage. Since every statement is on some subpath emanating from either a branch statement or from the entry point of the program, every statement must be executed if every branch direction is executed. However, there are at least three exceptions. One is the pathological situation where the program has no decisions. A second occurs in programs or subroutines with multiple entry points; a given statement might only be executed if the program is entered at a particular entry point. The third exception is statements within ON-units; traversing every branch direction will not necessarily cause all ON-units to be executed. Since we have deemed statement coverage to be a necessary condition, decision coverage, a seemingly better criterion, should be defined to include statement coverage. Hence, decision coverage requires that each decision have a true and false outcome, and that each statement be executed at least once. An alternative and easier way of expressing it is that each decision have a true and false outcome, and that each point of entry (including ON-units) be invoked, at least once.

The above discussion considers only two-way decisions or branches and has to be modified for programs containing multi-way decisions. Examples are PL/I programs containing SELECT (CASE) statements or GO-TO label-variable statements, Fortran programs containing arithmetic (three-way) IF statements or computed or arithmetic GO TO statements, and Cobol programs containing ALTERed GO TO statements or GO-TO-DEPEND ING-ON statements. For such programs, the criterion is exercising each possible outcome of all decisions at least once and invoking each point of entry to the program or subroutine at least once.

Decision coverage is a stronger criterion than statement coverage, but it is still rather weak.

Condition Coverage

A criterion that is sometimes stronger than decision coverage is condition coverage. In this case, one writes enough test cases such that each condition in a decision takes on all possible outcomes at least once. Since, as with decision coverage, this does not always lead to the execution of each statement, an addition to the criterion is that each point of entry to the program or subroutine, as well as ON-units, be invoked at least once. For instance, the branching statement

DO K=0 TO 50 WHILE (J+K<QUEST)

contains two conditions: is K less than or equal to 50, and is J + K less than QUEST? Hence test cases would be required for the situations K = 50, K > 50 (i.e., reaching the last iteration of the loop), J + K < QUEST, and J + K = QUEST.

Figure 1: A small program to be tested.

Figure 1 has four conditions: A > 1, B = 0, A = 2, and X > 1. Hence enough test cases are needed to force the situations where A > 1, A=1, B = 0, and B ? 0 are present at point a and where A = 2, A ? 2, X > 1, and X = 1 at point b. A sufficient number of test cases satisfying the criterion, and the paths traversed by each, are

A=2, B=0, X=4 ace
A=1, B=1, X=1 adb

Note that although the same number of test cases were generated for this example, condition coverage is usually superior to decision coverage in that it may (but does not always) cause every individual condition in a decision to be executed with both outcomes, where decision coverage does not. For instance, the DO statement

DO K=0 TO 50 WHILE (J+K<QUEST)

is a two-way branch (execute the loop body or skip it). If one is using decision testing, the criterion can be satisfied by letting the loop run from K = 0 to 51, without ever exploring the circumstance where the WHILE clause becomes false. With the condition criterion, however, a test case would be needed that generated a false outcome for the condition J + K < QUEST.

Although the condition-coverage criterion appears, at first glance, to satisfy the decision-coverage criterion, it does not always do so. If the decision IF (A&B) is being tested, the condition-coverage criterion would allow one to write two test cases—A is true, B is false, and A is false, B is true—but this would not cause the THEN clause of the IF to execute. The condition-coverage tests for the earlier example covered all decision outcomes, but this was only by chance. For instance, two alternative test cases

A = 1, B = 0, X = 3
A = 2, B = 1, X = 1

cover all condition outcomes, but they cover only two of the four decision outcomes (they both cover path abe and hence do not exercise the true outcome of the first decision and the false outcome of the second decision).

Decision/Condition Coverage

The obvious way out of this dilemma is a criterion called decision/condition coverage. It requires sufficient test cases such that each condition in a decision takes on all possible outcomes at least once, each decision takes on all possible outcomes at least once, and each point of entry is invoked at least once.

A weakness with decision/condition coverage is that although it may appear to exercise all outcomes of all conditions, it frequently does not because certain conditions mask other conditions. To see this, examine Figure 2. The flowchart in Figure 4.2 is the way a compiler would generate machine code for the program in Figure 1. The multicondition decisions in the source program have been broken into individual decisions and branches because most machines do not have a single instruction that makes multicondition decisions. A more thorough test coverage, then, appears to be the exercising of all possible outcomes of each primitive decision. The two previous decision-coverage test cases do not accomplish this; they fail to exercise the false outcome of decision H and the true outcome of decision K. In this program, the condition-coverage test is equally deficient; the two test cases (which also happen to satisfy the decision/condition criterion) do not invoke the false outcome of decision I and the true outcome of decision K.

Figure 2: Machine code for the program in Figure 1.

The reason is that, as shown in Figure 2, results of conditions in and and or expressions can mask or block the evaluation of other conditions. For instance, if an and condition is false, none of the subsequent conditions in the expression need be evaluated. Likewise, if an or condition is found to be true, none of the subsequent conditions need be evaluated. Hence, errors in logical expressions are not necessarily made visible by the condition-coverage and decision/condition coverage criteria.

Multiple Condition Coverage

A criterion that covers this problem, and then some, is multiple-condition coverage. This criterion requires one to write sufficient test cases such that all possible combinations of condition outcomes in each decision, and all points of entry, are invoked at least once. For instance, four situations to be tested exist in the following sequence of statements:

NOTFOUND = '1'B;
DO I=1 TO TABSIZE WHILE (NOTFOUND); /*SEARCH TABLE*/
searching logic;
END;

1. I≤TABSIZE and NOTFOUND is true.

2. I≤TABSIZE and NOTFOUND is false (finding the entry before hitting the end of the table).

3. I>TABSIZE and NOTFOUND is true (hitting the end of the table without finding the entry).

4. I>TABSIZE and NOTFOUND is false (the entry is the last one in the table).

It should be easy to see that a set of test cases satisfying the multiple-condition criterion also satisfies the decision-coverage, condition-coverage, and decision/condition coverage criteria.

Returning to Figure 1, eight combinations must be covered by test cases:

1. A > 1, B = 0
2. A > 1, B ? 0
3. A ≤ 1, B = 0
4. A ≤ 1, B ? 0
5. A = 2, X > 1
6. A = 2, X = 1
7. A ≠ 2, X > 1
8. A ≠ 2, X = 1

Note, as was the case earlier, that cases 5–8 express values at the point of the second IF statement. Since X may be altered above this IF statement, the values needed at this IF statement must be "backedup" through the logic to find the corresponding input values.

These combinations to be tested do not necessarily imply that eight test cases are needed. In fact, they can be covered by four test cases. The test-case input values, and the combinations they cover, are

A = 2, B = 0, X = 4 covers 1, 5

A = 2, B = 1, X = 1 covers 2, 6

A = 1, B = 0, X = 2 covers 3, 7

A = 1, B = 1, X = 1 covers 4, 8

The fact that there are four test cases and that there are four distinct paths in Figure 4.1 is just coincidence. In fact, the above four tests cases do not cover every path; they miss the path acd. For instance, eight test cases would be needed for the following program:

IF ((X = Y) & (LENGTH(Z)=0) & END) THEN J=1;
ELSE I=1;

although it contains only two paths. In the case of loops, the number of test cases required by the multiple-condition criterion is normally much less than the number of paths.

Summary

In summary, for programs containing only one condition per decision, a minimum test criterion is a sufficient number of test cases to (1) evoke all outcomes of each decision at least once and (2) invoke each point of entry (e.g., entry point, ON-unit) at least once (to ensure that all statements are executed at least once). For programs containing decisions having multiple conditions, the minimum criterion is a sufficient number of test cases to evoke all possible combinations of condition outcomes in each decision, and all points of entry to the program, at least once. [The word "possible" is inserted because some combinations may be found to be impossible to create; for instance, only three combinations of conditions in the decision (A>2)&(A<10) can be created.]