|
EXPERIENCE WITH THE COST OF DIFFERENT COVERAGE GOALS FOR TESTING
By: Brian Marick
In coverage-based testing, coverage conditions are generated from the program text. For example, a
branch generates two conditions: that it be taken in the false direction and in the true direction. The proportion
of coverage conditions a test suite exercises can be used as an estimate of its quality. Some coverage
conditions are impossible to exerise, and some are more cost-effectively eliminated by static analysis.
The remainder, the feasible coverage conditions, are the subject of this paper.
What percentage of branch, loop, multi-condition, and weak mutation coverage can be expected from
thorough unit testing? Seven units from application programs were tested using an extension of traditional
black box testing. Nearly 100% feasible coverage was consistently achieved. Except for weak mutation,
the additional cost of reaching 100% feasible coverage required only a few percent of the total time. The
high cost for weak mutation was due to the time spent identifying impossible coverage conditions.
Because the incremental cost of coverage is low, it is reasonable to set a unit testing goal of 100% for
branch, loop, multi-condition, and a subset of weak mutation coverage. However, reaching that goal after
measuring coverage is less important than nearly reaching it with the initial black box test suite. A low initial
coverage signals a problem in the testing process.
1. Introduction
One strategy for testing large systems is to test the low-level components ("units") thoroughly before combining
them. The expected benefit is that failures will be found early, when they are cheaper to diagnose
and correct, and that the cost of later integration or system testing will be reduced. One way of defining
"thoroughly" is through coverage measures. This paper addresses these questions:
(1) What types of coverage should be measured?
(2) How much coverage should be expected from black box unit testing?
(3) What should be done if it is not achieved?
This strategy is expensive; in the last section, I discuss ways of reducing its cost. A different strategy is to
test units less thoroughly, or not at all, and put more effort into integration and system testing. The results
of this study have little relevance for that strategy, though they may provide some evidence in favor of the
first strategy.
Note on terminology: "unit" is often defined differently in different organizations. I define a unit to be a
single routine or a small group of closely related routines, such as a main routine and several helper routines.
Units are normally less than 100 lines of code.
1.1. Coverage
Coverage is measured by instrumenting a program to determine how thoroughly a test suite exercises it.
There are two broad classes of coverage measures. Path-based coverage requires the execution of particular
components of the program, such as statements, branches, or complete paths. Fault-based coverage
requires that the test suite exercise the program in a way that would reveal likely faults.
1.1.1. Path-based Coverage
Branch coverage requires every branch to be executed in both directions. For this code
if (arg > 0)
{
counter = 0; /* Reinitialize */
}
branch coverage requires that the IF’s test evaluate to both TRUE and FALSE.
Many kinds of faults may not be detected by branch coverage. Consider a test-at-the-top loop that is
intended to sum up the elements of an array:
sum = 0;
while (i > 0)
{
i -= 1;
sum = pointer[i]; /* Should be += */
}
This program will give the wrong answer for any array longer than one. This is an important class of
faults: those that are only revealed when loops are iterated more than once. Branch coverage does not
force the detection of these faults, since it merely requires that the loop test be TRUE at least once and
FALSE at least once. It does not require that the loop ever be executed more than once. Further, it doesn’t
require that the loop ever be skipped (that is, that i initially be zero or less). Loop coverage [Howden78]
[Beizer83] requires these two things.
Multi-condition coverage [Myers79] is an extension to branch coverage. In an expression like
if (A && B)
multi-condition coverage requires that A be TRUE in some test, A be FALSE in some test, B be TRUE in
some test, and B be FALSE in some test. Multi-condition coverage is stronger than branch coverage; these
two inputs
A == 1, B == 1
A == 0, B == 1
satisfy branch coverage, but do not satisfy multi-condition coverage.
There are other coverage measures, such as dataflow coverage [Rapps85] [Ntafos84]. They are not measured
in this experiment, so they are not discussed here.
1.1.2. Fault-based Coverage
In weak mutation coverage [Howden82] [Hamlet77], we suppose that a program contains a particular simple
kind of fault. One such fault might be using <= instead of the correct < in an expression like this:
if (A <= B)
Given this program, a weak mutation coverage system would produce a message like
"gcc.c", line 488: operator <= might be <
This message would be produced until the program was executed over a test case such that (A £B ) has a
different value than (A
(A £B )¹(A
or, equivalently, that
A =B
Notice the similarity of this requirement to the old testing advice: "always check boundary conditions".
Suppose we execute the program and satisfy this coverage condition. In this case, the incorrect program
(the one we’re executing) will take the wrong branch. Our hope is that this incorrect program state will
persist until the output, at which point we’ll see it and say "Bug!". Of course, the effect might not persist.
However, there’s evidence [Marick90] [Offutt91] that over 90% of such faults will be detected by weak
mutation coverage. Of course, not all faults are such simple deviations from the correct program; probably
a small minority are [Marick90]. However, the hope of weak mutation testing is that a test suite thorough
enough to detect such simple faults will also detect more complicated faults; this is called the coupling
effect [DeMillo78]. The coupling effect has been shown to hold in some special cases [Offutt89], but more
experiments are needed to confirm it in general.
There are two kinds of weak mutation coverage. Operator coverage is as already described -- we require
test cases that distinguish operators from other operators. Operand coverage is similar -- for any operand,
such as a variable, we assume that it ought to have been some other one. That is, in
my_function(A)
we require test cases that distinguish A from B (coverage condition A ¹B ), A from C, A from D, and so on.
Since there may be a very large number of possible alternate variables, there are usually a very large
number of coverage conditions to satisfy. The hope is that a relatively few test cases will satisfy most of
them.
1.2. Feasible Coverage Conditions
All coverage techniques, not just mutation coverage, generate coverage conditions to satisfy. (A branch,
for example, generates two conditions: one that the branch must be taken true, and one that it must be
taken false.) Ideally, one would like all coverage conditions to be satisfied: 100% coverage. However, a
condition may be impossible to satisfy. For example, consider this loop header:
for(i = 0; i < 4; i++)
Two loop conditions cannot be satisfied: that the loop be taken zero times, and that the loop be taken once.
Not all impossible conditions are this obvious. Programmer "sanity checks" also generate them:
phys = logical_to_physical(log);
if (NULL_PDEV == phys)
fatal_error("Program error: no mapping.");
The programmer’s assumption is that every logical device has, at this point, a physical device. If it is
correct, the branch can never be taken true. Showing the branch is impossible means independently checking
this assumption. There’s no infallible procedure for doing that.
In some cases, eliminating a coverage condition may not be worth the cost. Consider this code:
if (unlikely_error_condition)
halt_system();
Suppose that halt_system is known to work and that the unlikely error condition would be tremendously
difficult to generate. In this case, a convincing argument that unlikely_error_condition indeed
corresponds to the actual error condition would probably be sufficient. Static analysis - a correctness argument
based solely on the program text - is enough. But suppose the code looked like this:
if (unlikely_error_condition)
recover_and_continue();
Error recovery is notoriously error-prone and often fails the simplest tests. Relying on static analysis
would usually not be justified, because such analysis is often incorrect -- it makes the same flawed implicit
assumptions that the designer did.
Coverage conditions that are possible and worth testing are called feasible. Distinguishing these from the
others is potentially time-consuming and annoyingly imprecise. A common shortcut is to set goals of
around 85% for branch coverage (see, for example, [Su91]) and consider the remaining 15% infeasible by
assumption. It is better to examine each branch separately, even if against less deterministic rules.
1.3. Coverage in Context
For the sake of efficiency, testing should be done so that many coverage conditions are satisfied without the
tester having to think about them. Since a single black box test can satisfy many coverage conditions, it is
most efficient to write and run black box tests first, then add new tests to achieve coverage.
Test design is actually a two stage process, though the two are usually not described separately. In the first
stage, test conditions are created. A test condition is a requirement that at least one test case must satisfy.
Next, test cases are designed. The goal is to satisfy as many conditions with as few test cases as possible
[Myers79]. This is partly a matter of cost, since fewer test cases will (usually) require less time, but more a
matter of effectiveness: complex test cases are more "challenging" to the program and are more likely to
find faults through chance.
After black box tests are designed, written, and run, a coverage tool reports unsatisfied coverage conditions.
Those which are feasible are the test conditions used to generate new test cases, test cases that
improve the test suite. Our hope is that there will be few of them.
1.4. The Experiment
Production use of a branch coverage tool [Zang91] gave convincing evidence of the usefulness of coverage.
Another tool, GCT, was built to investigate other coverage measures. It was developed at the same
time as a variant black box testing technique. To tune the tool and technique before putting them to routine
use, they were used on arbitrarily selected code from readily available programs. This early experience
was somewhat surprising: high coverage was routinely achieved. A more thorough study, with better
record-keeping and a stricter definition of feasibility, was started. Consistently high coverage was again
seen, together with a low incremental cost for achieving 100% feasible coverage, except for weak mutation
coverage. These results suggest that 100% feasible coverage is a reasonable testing goal for unit testing.
Further, the consistency suggests that coverage can be used as a "signal" in the industrial quality control
sense [DeVor91]: as a normally constant measure which, when it varies, indicates a potential problem in
the testing process.
2. Materials and Methods
2.1. The Programs Tested
Seven units were tested. One was an entire application program. The others were routines or pairs of routines
chosen from larger programs in widespread use. They include GNU make, GNU diff, and the RCS
revision control system. All are written in C. They are representative of UNIX application programs.
The code tested ranged in size from 30 to 272 lines of code, excluding comments, blank lines, and lines
containing only braces. The mean size was 83 lines. Size can also be measured by total number of coverage
conditions to be satisfied, which ranged from 176 to 923, mean 479. On average, the different types of
coverage made up these percentages of the total:
Branch 7.5%; Loop 3.0%; Multi 2.7% Operator 16.1% ; Operand 70.7%
In the case of the application program, the manual page was used as a specification. In the other cases,
there were no specifications, so I wrote them from the code.
The specifications were written in a rigorous format as a list of preconditions (that describe allowable
inputs to the program) and postconditions (each of which describes a particular result and the conditions
under which it occurs). The format is partially derived from [Perry89]; an example is given in Appendix
A.
2.2. The Test Procedure
The programs were tested in five stages. Each stage produced a new test suite that addressed the shortcomings of its predecessors.
2.2.1. Applying a Variant Black Box Technique
The first two test suites were developed using a variant black box testing technique. It is less a new technique
than a codification of good practice. Its first stage follows these steps:
Black 1: Test conditions are methodically generated from the form of the specification. For example, a
precondition of the form "X must be true" generates two test conditions: "X is true" and "X is false",
regardless of what X actually is. These test conditions are further refined by processing connectives like
AND and OR (using rules similar to cause-effect testing [Myers79]). For example, "X AND Y" generates
three test cases:
X is true, Y is true.
X is false, Y is true.
X is true, Y is false.
Black 2: Next, test conditions are generated from the content of the specification. Specifications contain
cliches [Rich90]. A search of a circular list is a typical cliche. Certain data types are also used in a cliched
way. For example, the UNIX pathname as a slash-separated string is implicit in many specifications.
Cliches are identified by looking at the nouns and verbs in the specification: "search", "list", "pathname".
The implementations of these cliches often contain cliched faults.1 For example:
(1) If the specification includes a search for an element of a circular list, one test condition is that the list
does not include the element. The expectation is that the search might go into an infinite loop.
(2) If a function decomposes and reconstructs UNIX pathnames, one test condition is that it be given a
pathname of the form "X//Y", because programmers often fail to remember that two slashes are
equivalent to one.
Because experienced testers know cliched faults, they use them when generating tests. However, writing
the cliches and faults down in a catalog reduces dependency on experience and memory. Such a catalog
has been written; sample entries are given in Appendix B.
Black 3: These test conditions are combined into test cases. A test case is a precise description of particular
input values and expected results.
The next stage is called broken box testing2. It exposes information that the specification hides from the
user, but that the tester needs to know. For example, a user needn’t know that a routine uses a hash table,
but a tester would want to probe hash table collision handling. There are two steps:
Broken 1: The code is scanned, looking for important operations and types that aren’t visible in the
specification. Types are often recognized because of comments about the use of a variable. (A variable’s
declaration does not contain all the information needed; an integer may be a count, a range, a percentage,
or an index, each of which produces different test conditions.) Cliched operations are often distinct blocks
of code separated by blank lines or comments. Of course, the key way you recognize a cliche is by having
seen it often before. Once found, these cliches are then treated exactly as if they had been found in the
specification. No attempt is made to find and satisfy coverage conditions. (The name indicates this: the
box is broken open enough for us to see gross features, but we don’t look at detail.)
Broken 2: These new test conditions are combined into new test cases.
In production use, a tester presented with a specification and a finished program would omit step Black3.
Test conditions would be derived from both the specification and the code, then combined together. This
would minimize the size of the test suite. For this experiment, the two test suites were kept separate, in
order to see what the contribution of looking at the code would be. This also simulates the more desirable
case where the tests are designed before the code is written. (Doing so reduces elapsed time, since tests
can be written while the code is being written. Further, the act of writing concrete tests often discovers
errors in the specification, and it’s best to discover those early.)
In this experiment, the separation is artificial. I wrote the specifications for six of the programs, laid them
aside for a month, then wrote the test cases, hoping that willful forgetfulness would make the black box
testing less informed by the implementation.
2.2.2. Applying Coverage
After the black and broken box tests were run, three coverage test suites were written. At each stage,
cumulative coverage from the previous stages was measured, and a test suite that reached 100% feasible
coverage on the next coverage goal was written and run. The first suite reached 100% feasible branch and
loop coverage, the next 100% feasible multi-condition coverage, and the last 100% feasible weak mutation
coverage. The stages are in order of increasing difficulty. There is no point in considering weak mutation
coverage while there are still unexecuted branches, since eliminating the branches will eliminate many
weak mutation conditions without the tester having to think about them.
In each stage, each coverage condition was first classified. This meant:
(1) For impossible conditions, an argument was made that the condition was indeed impossible. This
argument was not written down (which reduces the time required).
(2) Only weak mutation conditions could be considered not worthwhile. The rule (necessarily imprecise)
is given in the next section. In addition to the argument for infeasibility, an argument was made
that the code was correct as written. (This was always trivial.) The arguments were not written
down.
(3) For feasible conditions, a test condition was written down. It described the coverage condition in
terms of the unit’s input variables.
After all test conditions were collected, they were combined into test cases in the usual way.
2.2.2.1. Feasibility Rules
Weak mutation coverage conditions were never ruled out because of the difficulty of eliminating them, but
only when a convincing argument could be made that the required tests would have very little chance of
revealing faults. That is, the argument is that the coupling effect will not hold for a condition. Here are
three typical cases:
(1) Suppose array is an input array and array[0]=0 is the first statement in the program. If array[0] is
initially always 0, GCT will complain that the initial and final value of the array are never different.
However, a different initial value could never have any effect on the program.
(2) In one program, fopen() always returned the same file pointer. Since the program doesn’t manipulate
the file pointer, except to pass it to fread() and fclose(), a different file pointer would not detect a
fault.
(3) A constant 0 is in a line of code executed by only one test case. In that test case, an earlier loop
leaves an index variable with the value 0. GCT complains that the constant might be replaced by the
variable. That index variable is completely unused after the loop, it has been left with other values in
other tests, and the results of the loop do not affect the execution of the statement in question. Writing
a new test that also executes the statement, but with a different value of the index variable, is
probably useless.
2.2.2.2. Weak mutation coverage
Weak mutation coverage tools can vary considerably in what they measure. GCT began with the singletoken
transformations described in [Offutt88] and [Appelbe??], eliminating those that are not applicable to
C. New transformations were added to handle C operators, structures, and unions. Space does not permit a
full enumeration, but the extensions are straightforward. See [Agrawal89] for another way of applying
mutation to C.
Three extensions increased the cost of weak mutation coverage:
(1) In an expression like (variable < expression ), GCT requires more than that variable ¹alternate. It
requires that variable
(2) Weak sufficiency also applies to compound operands. For example, when considering the operator
*ptr, GCT requires *ptr ¹*other_ptr , not just ptr ¹other_ptr . (Note: [Howden82] handles compound
operands this way. It’s mentioned here because it’s not an obvious extension from the transformations
given in [Offutt88], especially since it complicates the implementation somewhat.)
(3) Variable operands are required to actually vary; they cannot remain constant.
See [Agrawal89] for another way of applying mutation to C.
2.2.3. What was Measured
For each stage, the following was measured:
(1) The time spent designing tests. This included time spent finding test conditions, ruling out infeasible
coverage conditions, deciding that code not worth covering (e.g., potential weak mutation faults) was
correct, and designing test cases from test conditions. The time spent actually writing the tests was
not measured, since it is dominated by extraneous factors. (Can the program be tested from the command
line, or does support code have to be written? Are the inputs easy to provide, like integers, or
do they have to be built, like linked lists?)
(2) The number of test conditions and test cases written down.
(3) The percent of coverage, of all types, achieved. This is the percent of total coverage conditions, not
just feasible ones.
(4) The number of feasible, impossible, and not worthwhile coverage conditions.
2.2.4. An Example
LC is a 272-line C program that counts lines of code and comments in C programs. It contains 923 coverage
conditions.
The manpage was used as the starting specification; 101 test conditions were generated from it. These test
conditions could be satisfied by 36 test cases. Deriving the test conditions and designing the test cases took
2.25 hours. Four faults were found.3
These coverages were achieved in black box testing:
More to see http://www.testing.com/writings/experience.pdf
Other Resource
... to read more articles, visit http://sqa.fyicenter.com/art/
|