Another more sophisticated strategy for testing conditionals is
known as domain testing [How82], illustrated in Figure 5-31 below. Domain testing
concentrates on linear inequalities. In the figure, the inequality the
program should use for the test is
j <= i + 1.
We test the inequality with three test points - two on the boundary
of
the valid region and a third outside the region but between the i
values of the other two points. When we make some common mistakes in
typing the inequality, these three tests are sufficient to uncover
them, as shown in the figure.
A potential problem with path coverage is that the paths chosen to
cover the CDFG may not have any important relationship to the program's
function. Another testing strategy known as data flow testing
makes use of def-use analysis (short for
definition-use analysis). It selects paths that have some relationship
to the program's function.
 |
| Figure
5-31. Domain testing for a pair of variables. |
The terms def and use come from compilers, which use def-use
analysis for optimization [Aho86].
A variable's value is defined when an assignment
is
made to the variable; it is used when it appears
on
the right side of an assignment (sometimes called a c-use
for computation use) or in a conditional expression (sometimes called p-use
for predicate use).
A def-use pair is a definition of a variable's
value and a use of that value. Figure
5-32 below shows a code fragment and
all the def-use pairs for the first assignment to a. Def-use analysis
can be performed on a program using iterative algorithms. Data flow
testing chooses tests that exercise chosen def-use pairs.
The test first causes a certain value to be assigned at the
definition and then observes the result at the use point to be sure
that the desired value arrived there. Frankl and Weyuker [Fra88] have defined criteria for
choosing which def-use pairs to exercise to satisfy a well-behaved
adequacy criterion.
 |
| Figure
5-32. Definitions and uses of variables. |
Testing Loops
We can write some specialized tests for loops. Since loops
are common
and often perform important steps in the program, it is worth
developing loopcentric testing methods. If the number of iterations is
fixed, then testing is relatively simple. However, many loops have
bounds that are executed at run time. Consider first the case of a
single loop as follows:
for (i = 0; i < terminate(); i++)
proc(i,array);
It would be too expensive to evaluate the above loop for all
possible termination conditions. However, there are several important
cases that we should try at a minimum. These cases are summarized below.
- Skipping the loop entirely [if possible, such as when terminate()
returns 0 on its first call].
- One loop iteration.
- Two loop iterations.
- If there is an upper bound n on the number of loop iterations
(which may come from the maximum size of an array), a value that is
significantly below that maximum number of iterations.
- Tests near the upper bound on the number of loop iterations, that
is, n ' 1, n, and n + 1.
We can also have nested loops such as the following:
for (i = 0; i < terminate1(); i++)
for (j = 0; j < terminate2(); j++)
for (k = 0; k < terminate3(); k++)
proc(i,j,k,array);
There are many possible strategies for testing nested loops. One
thing to keep in mind is which loops have fixed versus variable numbers
of iterations. Beizer [Bei90] suggests an inside-out strategy for
testing loops with multiple variable iteration bounds. First,
concentrate on testing the innermost loop as above - the outer loops
should be controlled to their minimum numbers of iterations. After the
inner loop has been thoroughly tested, the next outer loop can be
tested more thoroughly, with the inner loop executing a typical number
of iterations. This strategy can be repeated until the entire loop nest
has been tested. Clearly, nested loops can require a large number of
tests. It may be worthwhile to insert testing code to allow greater
control over the loop nest for testing.
