Provable Improvements on Branch Testing.
This paper compares the fault-detecting ability of several software test data adequacy criteria. It has previously been shown that if C/sub 1/ properly covers C/sub 2/, then C/sub 1/ is guaranteed to be better at detecting faults than C/sub 2/, in the following sense: a test suite selected by independent random selection of one test case from each subdomain induced by C/sub 1/ is at least as likely to detect a fault as a test suite similarly selected using C/sub 2/. In contrast, if C/sub 1/ subsumes but does not properly cover C/sub 2/, this is not necessarily the case. These results are used to compare a number of criteria, including several that have been proposed as stronger alternatives to branch testing. We compare the relative fault-detecting ability of data flow testing, mutation testing, and the condition-coverage techniques, to branch testing, showing that most of the criteria examined are guaranteed to be better than branch testing according to two probabilistic measures. We also show that there are criteria that can sometimes be poorer at detecting faults than substantially less expensive criteria.
Introduction
Although a large number of software testing techniques have been proposed during the
last two decades, there has been surprisingly little concrete information about how effectively
they detect faults. This is true both in the case of theoretical analyses and
Author's address: Computer Science Dept., Polytechnic University, 6 Metrotech, Brooklyn, N.Y.
11201. Supported in part by NSF Grant CCR-9206910 and by the New York State Science and Technology
Foundation Center for Advanced Technology program.
y Author's address: Computer Science Dept., Courant Institute of Mathematical Sciences, New York
University, 251 Mercer Street, New York, NY 10012. Supported in part by NSF grant CCR-8920701
and by NASA grant NAG-1-1238.
empirical studies. In fact there are not even generally agreed-upon notions of what it
means for one testing strategy to be more effective than another.
Most previous comparisons of software testing criteria have been based on the subsumes
relation. Criterion C 1 subsumes criterion C 2 if for every program P , every test
suite that satisfies C 1 also satisfies C 2 . Unfortunately, it is not clear what the fact that
us about their relative effectiveness. Weiss has argued that subsumption
is more useful for comparing the cost of criteria than their effectiveness [22].
Hamlet [13] pointed out that it is possible for C 1 to subsume C 2 , yet for some test
suite that satisfies C 2 to detect a fault while some test suite that satisfies C 1 does not.
Weyuker, Weiss, and Hamlet [24] further investigated the limitations of subsumption
and other relations of that nature including Gourlay's power relation [12], and a newly
proposed relation, the "better" relation.
In contrast, our approach is probabilistic. It is based on the fact that for a given
program, specification, and criterion, there are typically a large number of test suites
that satisfy a given test data adequacy criterion. Often, some of these suites will detect
a fault, while others do not. For this reason, we will compare adequacy criteria by
comparing the likelihood of detecting a fault and the expected number of faults detected
when test suites for each criterion are selected in a particular way. This not only allows us
to compare existing criteria in a concrete way, but also corresponds to a very reasonable
intuitive notion of what it means for one criterion to be better at detecting faults than
another.
In [8, 10] we explored the conditions under which one adequacy criterion is guaranteed
to be at least as good as another according to a certain probabilistic measure of fault-
detecting ability. That analysis was based on investigating how software testing criteria
divide a program's input domain into subsets, or subdomains. We showed that it is
possible for C 1 to subsume C 2 yet for C 2 to be better at detecting faults according to
this measure. A simple example illustrates how this can happen. Assume the domain
D of a program P is f0; 1; 2g, and 0 is the only input on which P fails. Assume that
selection of a test case from the subdomain f0; 1g and a test case from the
subdomain f2g and that C 2 requires selection of a test case from the subdomain f0; 1g
and a test case from the subdomain f0; 2g. Since every test suite that satisfies C 1 also
Selecting one test case from each subdomain yields two
possible test suites, f0; 2g and f1; 2g, only one of which will cause P to fail.
There are four possible C 2 -adequate test suites, f0; 0g, f0; 2g, f1; 0g, and f1; 2g, three
of which will cause P to fail. Thus, a test suite selected to satisfy C 2 is more likely to
detect a fault than one selected to satisfy C 1 .
this situation occurred because the only input that caused a failure was a
member of both subdomains of C 2 , but was a member of only one subdomain of C 1 .
Furthermore, overlapping subdomains are a common occurrence in software testing; most
testing criteria defined in the literature give rise to overlapping subdomains, often even
for very simple programs. Thus, as the examples below illustrate, this phenomenon is
not a mere theoretical curiosity, but one that occurs with real testing criteria and real
programs.
As a response to this type of problem, we introduced a stronger relation between
criteria, the properly covers relation, and proved that if C 1 properly covers C 2 , then
when one test case is independently randomly selected from each subdomain using a
uniform distribution, the probability that C 1 will detect at least one fault is greater than
or equal to the probability that C 2 will detect a fault [8, 10]. This is a powerful result
provided that the model of testing used is a reasonable model of reality. We will address
this issue in Section 2.1.
If we can show that C 1 properly covers C 2 for all programs in some class P, then we
will be guaranteed that C 1 is at least as good as C 2 (in the above sense) for testing any
program P in P, regardless of the particular faults that occur in P. On the other hand, if
does not properly cover C 2 for some program P , then even if C 1 subsumes C 2 , C 2 may
be more likely than C 1 to detect a bug in P . In this paper, we use the above result to
explore the relative fault-detecting ability of several well-known testing techniques. We
also introduce another measure of fault-detecting ability and show that if C 1 properly
covers C 2 , then C 1 is also at least as good as C 2 according to this new measure.
Three families of techniques that have been widely investigated are data flow testing,
mutation testing, and the condition-coverage techniques. We compare the relative fault-
detecting ability of criteria in these families to branch testing, showing that most of
the criteria examined are guaranteed to be better than branch testing according to the
probabilistic measures mentioned above, but that there are criteria that can sometimes
be poorer at detecting faults than substantially less expensive criteria.
Background and Terminology
A multi-set is a collection of objects in which duplicates may occur, or more formally,
a mapping from a set of objects to the non-negative integers, indicating the number
of occurrences of each object. We shall delimit multi-sets by curly braces and use set-theoretic
operator symbols to denote the corresponding multi-set operators throughout.
For a multi-set S 1 to be a sub-multi-set of multi-set S 2 , there must be at least as many
copies of each element of S 1 in S 2 as there are in S 1 . In the sequel, when we say that
some procedure is applied to each element of a multi-set
that the procedure is applied exactly n times: once to e 1 , once to e 2 , etc., without regard
for whether e
The input domain of a program is the set of possible inputs. We restrict attention
to programs with finite input domains, but place no bound on the input domain size.
Since real programs run on machines with finite word sizes and with finite amounts of
memory, this is not an unrealistic restriction. A test suite is a multi-set of test cases,
each of which is an element of the input domain. We investigate test suites rather than
test sets because it is easier in practice to allow occasional duplication of test cases
than to check for duplicates and eliminate them. A test data adequacy criterion is a
relation C ' Programs \Theta Specifications \Theta Test Suites that is used to determine whether
a given test suite T does a "thorough" job of testing program P for specification S. If
say "T is adequate for testing P with respect to S according
to C ", or, more simply, "T is C-adequate for P and S". In addition to providing a
means for evaluating test suites, adequacy criteria can serve as the basis for test selection
strategies, as discussed below.
Many systematic approaches to testing are based on the idea of dividing the input
domain of the program into subsets called subdomains, then requiring the test suite
to include elements from each subdomain. The manner in which the input domain is
subdivided may be based on the structure of the program being tested (program-based
testing), the structure or semantics of its specification (specification-based testing), or
some combination thereof. As a group, these techniques have generally been referred to
as partition testing strategies, but in fact, most such strategies divide the input domain
into overlapping subdomains, and thus do not form true partitions of the input domain.
In this paper, we will refer to these strategies as subdomain-based testing.
More precisely, a testing criterion C is subdomain-based if, for each program P and
specification S, there is a non-empty multi-set of subdomains, SDC (P; S), such that C
requires the selection of one or more test cases from each subdomain in SDC (P; S). Note
that one could define adequacy criteria that require the selection of at least k test-cases
from each subdomain, for some k ? 1. However, we restrict attention here to criteria
that only require at least one test case per subdomain. This is not a serious limitation
since virtually all criteria discussed in the literature only require the selection of at least
one test case per subdomain. To model criteria that do explicitly require k ? 1 test cases
per subdomain, we could include k copies of each subdomain in SDC (P; S) and select one
test case from each copy. However, if this is done, the test selection strategy described
below may select a test suite with less than k distinct test cases from a subdomain.
In general, SDC (P; S) is a multi-set, rather than a set, because for some criteria it
is possible for two different requirements to correspond to the same subdomain. For
example, consider the all-statements criterion, in which each subdomain corresponds to
the set of inputs that cause the execution of a particular statement in the program. If
two different statements are executed by the same test cases, identical subdomains occur
in the multi-set of subdomains. This can happen either because the structure of the flow
graph dictates that every path covering one statement also covers another or because the
semantics of the program force two seemingly independent statements to be traversed
by exactly the same test cases. Of course, given a criterion C for which the multi-set
contains duplicates, one can define a new criterion C 0 in which the duplicates
are eliminated, but, as we shall discuss below, it is frequently easier to keep the duplicates
(and hence select "extra" test cases) than to check to see whether duplicates exist.
Note that since SDC (P; S) is assumed to be non-empty and at least one test case
must be chosen from each subdomain, the empty test suite is not C-adequate for any
subdomain-based criterion. A subdomain-based criterion C is applicable to (P,S) if and
only if there exists a test suite T such that C(P; holds. C is universally applicable
if it is applicable to (P; S) for every program, specification pair (P; S). Note that since
the empty test suite is not C-adequate, C is applicable to (P; S) if and only if the empty
subdomain is not an element of SDC
Throughout this paper all testing criteria discussed will be universally applicable
subdomain-based criteria, unless otherwise noted. In fact, many of the criteria that have
been defined and discussed in the software testing literature are not universally applicable
[7]. For example, the all-statements criterion, which requires every statement in
the program to be executed, is not applicable to any program that has a statement that
cannot be exercised by any input. However, it is the universally applicable analogs of
those criteria that are actually usable in practice. That is, the form of statement testing
that is really used requires every executable statement to be exercised. Formally, these
versions are obtained by removing the empty subdomains from SDC (P; S). But determining
whether a subdomain is empty is in general undecidable. However, in practice,
it is often easy for testers to determine whether a subdomain is empty by inspecting the
program code or specification. Another way that testers pragmatically deal with this
issue is to make a tacit assumption that there is never more than some percentage x of
unexecutable statements (or branches, or whatever the relevant program artifact being
covered) and then require that (100 \Gamma x)% of the statements be exercised. Of course, it is
possible that more that x percent of the code is unexecutable, and then the tester is faced
with the same problem. In any case, our analysis will formally assess only the universally
applicable versions of any adequacy criterion. Note that the relationship between the
universally applicable analogs of criteria may be different than that between the original
criteria [7]. This will be discussed in Section 3.
Given a program P and a specification S, a failure-causing input t is one such that
the output produced by P on input t does not agree with the specified output. We will
say that a test suite T detects a fault in program P if T contains at least one failure-
causing input. Note that we are not concerned here with determining the particular
problem in P that caused the failure, only with determining that some problem exists.
Intuitively, a good testing strategy is one that is likely to require the selection of one or
more failure-causing inputs, if any exist.
2.1 The Model
There are many different ways to select a test suite that satisfies a given adequacy
criterion. We would like to be able to compare the likelihoods that test suites that
satisfy given adequacy criteria detect faults, without regard to how those test suites were
selected. However this problem is too vague to analyze, since the likelihood that a C-
adequate test suite detects a fault can only be defined with respect to a given probability
distribution on the space of test suites satisfying C. Such distributions may be defined
in some precise way, or may arise in practice from testers manually selecting test cases
which they consider to be "natural". Since the notion of what is "natural" differs from one
person to another, such distributions cannot be formally analyzed and are also extremely
difficult to study empirically.
Thus, in order to carry out an analysis of fault-detecting ability, we need to use a
test selection model that is well-defined, is not obviously biased in some criterion's favor,
and is not too far from reality. With this in mind, we assume that the tester selects
a test suite that satisfies a subdomain-based criterion C by first dividing the domain
based on SDC (P; S), and then for each D i 2 SDC randomly selecting an element
of D i . In the sequel, we let d the size of subdomain D i , let m i be the number of
failure-causing inputs in D i and let
Y
Assuming one test case is independently selected from each subdomain according to a
uniform distribution, M gives the probability that a test suite chosen using this test
selection strategy will expose at least one fault. This measure has previously been investigated
in [4, 10, 14, 23] and was called M 2 in [10]. Note that if SDC (P; S) contains a
duplicate subdomain D model requires independent selection of one test case
from each copy of the subdomain.
In several earlier works that compared the effectiveness of testing criteria, [4, 14,
23] the test selection procedure was actually specified as part of the criterion, thereby
obscuring the distinction between test selection and evaluation of test adequacy. For
example, Duran and Ntafos [4] and Hamlet and Taylor [14] compare random testing and
partition testing. For partition testing they speak of "dividing a program's input domain
into classes whose points are somehow 'the same' '' so that "it is sufficient to try one
representative from each class"([14], p. 1402). Weyuker and Jeng [23] compared partition
testing strategies and random testing using a generalized form of test data selection in
which n i test cases were independently selected from each subdomain D i . Again the test
case selection procedure was integrated into the testing criterion.
Note, that all of these papers based their assessments of effectiveness on the measure
M . In addition, in all of these cases, it was assumed that the subdomain division was
performed before any test cases were selected, and that selection from each subdomain
was independent.
In contrast, in this paper we make the role of the selection criterion explicit. It could
be argued that this test selection model does not accurately reflect testing practice because
testers sometimes allow each test case to "count" toward all of the subdomains to
which it belongs. We argue that in fact, our test selection model is not very far from
reality in many cases. In particular, specification-based testing is frequently done by
first determining the test requirements, and then selecting test cases for each requirement
without regard for whether a test case also fulfills additional requirements. This
is especially true when system testing is done by an independent testing group, and test
cases are derived from the specification even before the implementation is complete. In
addition, we expect that as automated test generation tools targeted to program-based
testing techniques become more available, it will also become common to select test suites
for these criteria in a manner similar to the above strategy. Manually crafting test cases
is often far more costly than test case execution, so test suite size is an important issue
under these circumstances, but when the generation is done automatically, it may well be
easier to generate test cases for each test condition (subdomain) than to generate a test
case for a condition, execute it to see which additional conditions have been inadvertently
exercised, and remove them from consideration.
One further note: in practice, most proposed adequacy criteria are monotonic. This
means that if a test suite is adequate for the criterion, then any test suite formed by
adding test cases to the suite is also adequate. But by using our selection method, these
"extra" test cases cannot be added. In a sense we are comparing test suites containing
only elements required by the criterion.
2.2 Relations Among Testing Criteria
In [8, 10], we explored several relations R among subdomain-based criteria, asking
whether S). The most commonly used
relation in the literature for comparing criteria is the subsumes relation. Recall that
criterion C 1 subsumes criterion C 2 if and only if for every program P and specification
S, every test suite that satisfies C 1 also satisfies C 2 . We showed that the fact that C 1
subsumes C 2 does not guarantee that M(C 1 ; simple example illustrating
this appeared in Section 1, above. We therefore introduced a stronger relation
among criteria, the properly covers relation, which is more relevant for comparing the
fault-detecting abilities of criteria.
In order to explain the intuition motivating the properly covers relation and its relationship
to subsumption, we first mention two weaker relations, the narrows and covers
relations, also defined in [8, 10].
for every subdomain
there is a subdomain D 0 2 SDC1 (P; S) such that D 0 ' D. C 1 universally
narrows C 2 if for every program, specification pair
In [10], we showed that for criteria that require selection of at least one element
from each subdomain (as opposed to explicitly requiring selection of k elements for some
only if C 1 universally narrows C 2 . Thus, for all of the
criteria considered in the current paper, the universally narrows relation is equivalent to
subsumption.
for every subdomain D 2
there is a collection fD of subdomains belonging to SDC1
such that universally covers C 2 if for every program, specification
In [10] we showed that various well-known criteria are related to one another by the
covers relation. We then showed that it is possible for C 1 to cover C 2 for (P; S), and still
have S). The problem arises when one subdomain of C 1 is used
in covering two or more subdomains of C 2 . We therefore introduced the properly covers
relation which overcomes this problem.
m g, and let SDC2
g. C 1
properly covers C 2 for (P,S) if there is a multi-set
such that M is a sub-multi-set of SDC1 (P; S) and
n;kn
Note that the number of occurrences of any subdomain D 1
in M is less than or equal to
the number of occurrences of that subdomain in the multi-set SDC1 . In other words, C 1
properly covers C 2 if each of C 2 's subdomains can be ``covered'' by C 1 subdomains (i.e.,
can be expressed as a union of some C 1 subdomains), and furthermore, this can be done
in such a way that none of C 1 's subdomains occurs more often in the covering than it
does in SDC1 . C 1 universally properly covers C 2 if for every program P and specification
The following example illustrates the properly covers relation.
Example 1:
Consider a program P whose input domain is fxj1 - x - 10g. Let C 2 be the criterion
whose subdomains for program P are D 2= fxj1 - x - 6g and D 2= fxj4 - x - 10g.
Let C 1 be the criterion whose subdomains are D 1
properly covers C 2 for P since D 2
2 and D 2
5 . In this case
g with D 1
note that it is possible for one criterion to have more subdomains than another,
without properly covering it. This is the case for the criterion C 0obtained from C 1 by
removing subdomains D 1. C 0narrows but does not properly cover C 2 . 2
Observation 1 For any (P; S), the narrows, covers, and properly covers relations are
all transitive. If C 1 properly covers C 2 , then C 1 covers C 2 . If C 1 covers C 2 then C 1
narrows C 2 . If SDC2
The following theorem is proven in [10]:
Theorem 1 If C 1 properly covers C 2 for program P and specification S, then
Thus, if we can show that C 1 universally properly covers C 2 , then we are guaranteed
that test suites chosen to satisfy C 1 (according to the above test selection strategy) are
at least as likely to detect faults as those chosen to satisfy C 2 .
Another reasonable measure of the fault-detecting ability of a criterion is the expected
number of failures detected. Again, let SDC g. Assuming independent
random selection of one test case from each subdomain, using a uniform distribution, this
is given by
We now show that if C 1 properly covers C 2 for a given program, specification pair, then
C 1 is also guaranteed to do at least as well as C 2 according to the measure E. Examples 2
and 6, below, show that this is not necessarily the case if C 1 subsumes C 2 , but does not
properly cover C 2 .
Theorem 2 If C 1 properly covers C 2 for program P and specification S, then E(C
Proof:
We begin by noting that if
d
d
(1)
where d is the size of D and m is the number of failure-causing inputs in D. Let
n g and let
be a sub-multi-set of SDC1 (P; S) such that
For and for each i, let d (k)
i be the size of D k
i be the number of failure-
causing inputs in D k
i . For each
i;j be the size of D 1
i;j be the number of
failure-causing inputs in D 1
i;j . Then
d (2)
(2)
d (1)
d (1)
Note that (3) follows from (1) and (2), since for each i, D 2
. Since M
is a sub-multi-set of SDC1 summation (4) involves all the summands in (3), and
perhaps some additional ones. The result follows immediately from the fact that each
summand is non-negative. 2
Theorems 1 and 2 can easily be generalized to selection strategies in which non-uniform
distributions on subdomains are used, provided the distributions on overlapping
subdomains satisfy a certain compatibility property. A number of strategies for using an
arbitrary distribution on the entire input domain to induce such compatible distributions
on the subdomains are discussed in [6].
2.3 Program Structure
Testing criteria that are based only on the structure of the program being tested are called
program-based (or structural or white-box) techniques. For such criteria, the multi-set
SD C (P; S) is independent of the specification. The criteria we consider in the remainder
of this paper are all program-based. However, it is important to note that Theorems 1
and 2 hold for any subdomain-based criteria, regardless of the basis for the division of the
domain. Thus, specification-based (or functional or black-box) subdomain-based criteria
could also be compared using techniques similar to those used in this paper.
We sometimes represent a program by its flow graph, a single-entry, single-exit directed
graph in which nodes represent sequences of statements or individual statements,
and edges represent potential flow of control between nodes. A path from node n 1 to
node n k is any sequence (n of nodes such that for each is an
edge. A suffix of a path (n path is
feasible if there exists some input that causes it to be executed and infeasible otherwise.
A variable v has a definition in node n if n contains a statement in which v is assigned
a value. Variable v has a use in node n if n contains a statement in which v's value is
fetched. A use of a variable occurring in the Boolean expression controlling a conditional
or loop statement is sometimes associated with each of the edges leaving that node, and
called a predicate use or p-use. A definition of v in node d reaches a use of v in node or
edge u if there is a definition-clear path with respect to v from d to u, i.e., a path from d
to u along which v is not redefined.
Since the criteria we consider here are based on program structure, it is necessary
to select a fixed language for the programs under test. For this reason, we will limit
attention to programs written in Pascal. Our results do not depend in any essential
way on this choice of language. We will also assume that every program has at least one
conditional or repetitive statement, and that at least one variable occurs in every Boolean
expression controlling a conditional or repetitive statement in the program. Note that
this variable occurrence may be implicit, as in the use of the input file variable in the
statement, while not eof do S.
If the first requirement is not satisfied, then every input traverses exactly the same
path through the program. If the latter requirement is not fulfilled, the Boolean expression
will always evaluate to true or will always evaluate to false, and the other branch
will be unexecutable. Note that we do not require that programs be "well-structured"
or goto-less. In contrast, for reasons described in Section 3 below, we did have this
requirement in our earlier paper [10].
We also require programs to satisfy the no feasible anomalies (NFA) property: every
feasible path from the start node to a use of a variable v must pass through a node having
a definition of v. This is a reasonable property to require, since programs that do not
satisfy this property have the possibility of referencing an undefined variable. 1 Although
there is no algorithm to check whether or not the NFA property holds, it is easy to check
the stronger no anomalies property, which requires that every path from the start node
to a use of v, whether feasible or not, pass through a node having a definition of v.
An algorithm for this is presented in [5]. It is also possible to enforce the no anomalies
property by considering the entry node to have definitions of all variables.
Branch testing, also known as decision-coverage, is one of the most widely discussed
subdomain-based criteria. A decision is a maximal Boolean expression controlling the
execution of a conditional statement or loop. For example, in the statement if
S, the Boolean expression (x=1) and (y=1) is a decision. In the
decision-coverage criterion, there are two subdomains for each decision, one consisting
of all inputs that cause it to evaluate to true at some point during execution and one
consisting of all inputs that cause it to evaluate to false at some point during execution 2 .
Note that these two subdomains are not necessarily disjoint since if the decision is within
1 Clarke et al. [2] have pointed out that a program may legitimately have a feasible definition-clear
path with respect to v from the start node to a call to procedure Q that defines reference parameter v.
In such cases, the NFA property can be enforced by considering the argument v to be defined before it
is used in the call to Q. Indeed, if this is not the actual data flow, then Q or P may attempt to reference
an undefined variable.
In [10] we investigated a different variant of branch testing, called all-edges, in which each edge in
the program's flow graph gives rise to a subdomain. The distinction between all-edges and decision
coverage is discussed in [9].
a loop, a single test case may cause the decision to evaluate to true on one iteration of
the loop and to false on another iteration.
In the remainder of the paper, we use the universally properly covers relation to
compare various criteria to the decision-coverage criterion and to each other. We thereby
exhibit criteria that are guaranteed to be at least as good as decision-coverage according
to the two measures of fault-detecting ability M and E. In each case, we compare criteria
strictly subsumes C 2 . It therefore follows that for these criteria,
does not universally properly cover C 1 . We thus focus attention on the question of
whether or not C 1 universally properly covers C 2 .
3 Data Flow Testing
Several of the criteria that have been proposed as more powerful alternatives to branch
testing involve the use of data flow information. These criteria are based on data flow
analysis, similar to that done by an optimizing compiler, and require that the test data
exercise paths from points at which values are assigned to variables, to points at which
those values are used. In this section we examine several data-flow based testing criteria
and show that each universally properly covers the decision-coverage criterion, and thus
can be viewed as being better at detecting faults than branch testing. We also compare
various data flow testing criteria to one another.
The all-uses criterion [18, 19] requires that test data cover every definition-use association
in the program, where a definition-use association is a triple (d; u; v) such that d is
a node in the program's flow graph in which variable v is defined, u is a node or edge in
which v is used, and there is a definition-clear path with respect to v from d to u 3 . We
will frequently refer to a definition-use association as an association. A test case t covers
association (d; u; v) if t causes a definition-clear path with respect to v from d to u to be
executed. Similarly, the all-p-uses criterion [18, 19] is a restricted version of all-uses that
requires that test data cover every association (d; u; v) in which u is an edge with a p-use
of variable v. Precise definitions of the criteria for a subset of Pascal similar to the one
in question are given in [7].
All-uses universally properly covers all-p-uses. All-p-uses universally properly
covers decision-coverage.
Proof:
Since SD all-p-uses all-uses universally properly covers all-p-
uses.
3 Note that if u is an edge, (n; m), the covering path must be of the form, must
include both the head and the tail of the edge.
The proof that all-p-uses universally properly covers decision-coverage is similar to
the proof in [10] that all-p-uses universally covers all-edges. Let P be a program, let d be
a decision in P, and let D d be the subdomain consisting of all inputs that cause decision
d to evaluate to true (alternatively we could let D d be the subdomain consisting of all
inputs that cause decision d to evaluate to false). Let e be the edge that is executed if
and only if d evaluates to true (or to false). Since we are only interested in the feasible
analog of decision-coverage, we can assume that D d 6= ;, i.e. that e is feasible.
Let v be a variable occurring in decision d. Let be the definitions of v for
which there is a feasible definition-clear path with respect to v from ffi i to e. For each
be the subdomain ftjt covers association v)g. Recall that we are
limiting attention to programs that satisfy the NFA property. Thus, every feasible path
from the start node to e passes through at least one of the
any test case that exercises one of the must exercise edge e,
Since each outcome of each decision in P gives rise to a distinct set of associations,
all-p-uses universally properly covers decision-coverage. 4 2
We next consider Ntafos' required k-tuples criteria [17]. These criteria require the
execution of paths going from a variable definition to a use that is influenced by the
definition, via a chain of intervening definitions and uses. A k-dr interaction is a sequence
of variables along with a sequence s of distinct statements such that
variable X i is defined in s i , used in s i+1 , and there is a definition-clear path with respect
to X i from s i to s i+1 . Note that the value assigned to X 1 in s 1 can influence the value
of X k\Gamma1 which is used at s k . The required k-tuples criterion requires that each k-dr
interaction be exercised, i.e., that a path s 1 executed where p i is a
definition-clear path with respect to X i . Certain requirements based on control flow are
also included.
Clarke et al. [2] pointed out certain technical problems with the original definition
and defined the required k-tuples+ criterion by making the following two modifications:
1. all l-dr interactions must be exercised for l - k, and
2. the statements s i in the path need not be distinct.
They showed that required k-tuples+ subsumes required (k\Gamma1)-tuples+, and that required
subsumes all-uses. Without modification (1), required k-tuples fails to
subsume required (k\Gamma1)-tuples, and without modification (2), required 2-tuples fails to
subsume all-uses.
In [10] we showed that all-p-uses universally covers, but does not universally properly cover all-
edges. In order to do so, we restricted attention to programs with no goto statements. Both the failure
to universally properly cover and the need to restrict the class of programs arose due to edges in P 's flow
graph that did not have any p-use. Such edges are an artifact of the conventions we used for building
flow graphs, not a fundamental aspect of program structure. When we consider the decision-coverage
version of branch testing rather than the all-edges version, these extraneous edges cease to exist, and
the problems disappear.
Lemma 2 For all k - 2, the required (k+1)-tuples+ criterion universally properly covers
the required k-tuples+ criterion. The required 2-tuples+ criterion universally properly
covers all-uses.
Proof:
This follows immediately from the fact that for k - 2,
SD all-uses next consider Laski and Korel's criteria [15], which have subsequently become
known as context-coverage and ordered-context-coverage. These criteria consider paths
through definitions of all variables used in a given statement. Let X
that are all used in node n. An elementary data context for n is a set fffi
is a definition of X i and there is a path p from the start node to node n such that
has a suffix that is a definition-clear path with respect to X i from ffi i
to n. Thus, control can reach n with variables having the values that were
assigned to them in nodes respectively. The context-coverage criterion requires
execution of such a path for each context. Clarke et al. [2] defined the context-coverage+
criterion by making the following modifications:
1. each subset of the set of variables used in node n gives rise to a context;
2. the execution of paths to the successors of node n is required.
They showed that context-coverage+ subsumes all-uses. Modification (1) was motivated
by the fact that there may be a definition-clear path with respect to X i from the start
node to a use of X i in n. Since we are assuming the NFA property, in the class of
programs considered here, no such path can be feasible. Furthermore, since there are 2 k
subsets of a set of k variables, modification (1) may lead to extremely large numbers of
subdomains.
The Laski and Korel definitions associated uses occurring in decisions with the decision
node, not with the edges leaving that node. Modification (2) was added in order to
insure that context-coverage subsumed branch testing. Alternatively, this can be achieved
by distinguishing p-uses from c-uses and associating p-uses with edges, as in [18, 19]. In
the remainder of the paper, we will use the term context-coverage to refer to the original
Laski-Korel criterion, with this minor modification. We use the notation
to denote the context arising from definitions of X i in nodes ffi i and uses of X
node or edge u.
Laski and Korel also introduced the ordered-context-coverage criterion [15]. An ordered
elementary data context for node n is a permutation of an elementary data context
for n. The criterion requires that each ordered-context be exercised by a path that visits
the definitions in the given order.
Lemma 3 Ordered-context-coverage universally properly covers context-coverage. Context-
coverage universally properly covers decision-coverage.
Proof:
By Observation 1, the fact that ordered-context-coverage universally properly covers
context-coverage follows immediately from the definitions. The proof that context-
coverage universally properly covers decision-coverage is similar to that of Lemma 1.
vk be the variables occurring in the decision in node n, let m be a successor
node of n, let D be the decision-coverage subdomain corresponding to (n; m), let
l g be the set of contexts corresponding to edge (n; m), and let D
be the corresponding subdomains. Consider a test case t 2 D. Let be the last
definitions of respectively, before the first occurrence of (n; m) in the path
executed by t. Clearly, is one of the contexts C i , so t 2 [D i .
Conversely, assume t 2 [D i . By the definition of context-coverage (as modified to
associate p-uses with edges), t executes a path that includes (n; m), and hence t 2 D.
Since each edge from each decision gives rise to a distinct set of contexts, the covering
is proper. 2
Note that if a statement s uses variables v and the number of definitions of
reach s is a i , then the number of executable contexts arising from this single
statement may be as high as
a i . Furthermore, the number of executable ordered
contexts arising from each context may be as high as k!. Thus both context-coverage
and ordered-context-coverage have the potential of being extremely expensive criteria.
In contrast, the number of definition-use associations arising from statement s is
a i .
One might expect context-coverage and ordered-context-coverage to be guaranteed to
be better at exposing faults than simpler data flow testing criteria. Hamlet has argued
that such criteria should be good at concentrating failure-causing input [13]. In fact, this
is not always the case. We next show that these criteria are not guaranteed to be better
at detecting faults than the all-p-uses criterion.
Lemma 4 Context-coverage does not universally properly cover all-p-uses or all-uses.
Ordered-context-coverage does not universally properly cover all-p-uses or all-uses.
Proof:
Consider the following program:
P(x,y:
begin
else x := 0;

Figure

1: Program for which context-coverage does not properly cover all-p-uses.
else y := 0;
else .
A flow graph for this program is shown in Figure 1. Note that the decision in node
8 always evaluates to true, thus control always follows edge (8; 9). This is purely a
convenience to simplify the descriptions of the subdomains and the calculations of M
and E.
The only variable used on edges (2; 3) and (2; 4) is x. Consequently, the def-p-use
subdomains arising from these p-uses are identical to the context subdomains arising
from them. Similarly, the subdomains arising from def-p-use associations (1; (5; 6); y)
and (1; (5; 7); y) are identical to the corresponding context subdomains.
The only difference between the two criteria comes from the decision involving both
variables x and y. The def-p-use associations arising from this decision give rise to
subdomains shown in the first three columns of Table 1, and the
contexts arising from this decision give rise to subdomains D 5
Observe that D must be used in
any covering of D 2 or D 4 , and hence context-coverage does not properly cover all-p-uses
for this program.
The ordered-contexts of this program are identical to the contexts. This is because
every path from the start node to edge (8,9) passes through a definition of x in node 4
id subdomain dua=context d m

Table

1: Subdomains of all-p-uses, context-coverage, and ordered-context-coverage
or node 5 before it passes through a definition of y in node 6 or node 7. Thus ordered-
context-coverage does not properly cover all-p-uses for this program.
The fact that context-coverage and ordered-context-coverage do not universally properly
cover all-uses follows from the transitivity of the universally properly covers relation.Example 2:
Now consider the specification,
Note that P (x; of the failure-causing
inputs are in D 8 , as well as in some other subdomains. Based on the values of d i and m i
shown in Table 1,
M(all-p-uses;
where A is the probability that no failure-causing input is selected from any of the
subdomains arising from uses other than the ones on edge (8; 9), and
E(ordered-context-coverage;
E(all-p-uses;
where B is the expected number of failure-causing input selected from any of the sub-domains
arising from uses other than the ones on edge (8; 9). Thus, for this program,
all-p-uses is better than context-coverage or ordered-context-coverage according to the
measures M and E. 2
Note that this program also illustrates how 2 k contexts can arise from a statement
using k variables, and thus even (unordered) context-coverage may be prohibitively expensive

Summarizing the lemmas in this section, we have
Theorem 3 All-uses, all-p-uses, required-k-tuples, context-coverage, and ordered-context-
coverage all universally properly cover decision-coverage. For k - 2, Required-(k+1)-
universally properly covers required-k-tuples+. Required 2-tuples universally properly
covers all-uses. Neither context-coverage nor ordered-context-coverage universally
properly covers all-p-uses or all-uses.
We conclude this section by mentioning two other data flow testing criteria, the all-
du-paths criterion [19] and the all-simple-OI-paths criterion [20]. Roughly speaking, the
all-du-paths criterion requires the execution of particular paths from variable definitions
to uses, while the all-simple-OI-paths criterion requires the execution of particular types
of paths that cover chains of definitions and uses leading from inputs to outputs. The
restrictions on the kinds of paths considered arise from control flow considerations - in
all-du-paths, attention is restricted to simple paths, i.e. paths in which all nodes, except
possibly the first and last, are distinct, while in the all-simple-OI-paths criterion,
attention is restricted to paths that traverse certain loops zero, one, or two times. Rapps
and Weyuker showed that all-du-paths subsumes all-uses and Ural and Yang showed
that all-simple-OI-paths subsumes all-du-paths. However, these results were based on
the original (non-applicable) versions of the criteria. We have previously shown that
when one considers instead the applicable analogs of the criteria, all-du-paths does not
even subsume branch testing [7]. Similar problems arise with all-simple-OI-paths. Con-
sequently, by careful placement of faults in executable portions of the code that are not
included in any executable du-path or in any executable simple OI-path, it is possible to
construct programs for which these criteria are less likely to expose a fault than branch
testing.
4 Mutation Testing
We next consider the mutation testing criterion [3]. Unlike the other criteria examined
so far, mutation testing is not a path-oriented criterion. Instead, it considers a test suite
T adequate for testing program P if T distinguishes P from each of a set of variants of
called mutants. These mutants are formed by applying mutation operators, which are
simple syntactic changes, to the program. In mutation testing, the subdomains are of
the form ftjP (t) 6= P 0 (t)g where P 0 is a particular mutant of P .
Obviously the number and nature of the subdomains will depend on exactly which
mutation operators are used. It is well-known that if the mutation operators include the
following two operators, then mutation testing subsumes branch testing [1]:
1. replace a decision by true
2. replace a decision by false.
Since these are the only mutation operators that are directly relevant to our comparison
of mutation testing to branch testing, we will use the term limited mutation testing to
refer to mutation testing with only these two operators.
To see that limited mutation testing subsumes decision-coverage, consider a decision
d in program P . Let D d=T be the decision-coverage subdomain arising from the true
outcome of this decision. Let P 0 be the mutant in which d is replaced by false, let D P 0
be the corresponding mutation testing subdomain, and let t 2 D P 0
i.e. t is an input
such that P (t) 6= P 0 (t). Therefore, t must cause d to evaluate to true at least once -
otherwise there would be no distinction between the computations of P and P 0 on t. Thus
' D d=T . However, as the proof of the following theorem shows, D P 0
and D d=T are
not necessarily identical, because even though the "wrong" branch is taken in the mutant,
the output may not be affected. This observation allows the construction of programs
for which decision-coverage is more likely to detect a fault than limited mutation testing.
Theorem 4 Limited mutation testing does not universally cover decision-coverage.
Proof:
Consider the following program
begin
if C(x) then y := x div 2 -integer part of x/2 -
else y := x/2;
Note that when x is even, the output is x=2 regardless of whether or not C(x) holds.
Let P 0 be the mutant in which C(x) is replaced by true and let P 00 be the mutant in
which C(x) is replaced by false. The subdomains arising from these mutants are
fxjnot C(x) and Odd(x)g
and the subdomains arising from decision-coverage are
Thus no even element of either DC=F or DC=T belongs to either of the limited mutation
testing subdomains, so limited mutation testing does not cover decision-coverage
for this program. 2
Example 3:
Let P be the above program and let S be any specification such that there is at least
one failure-causing input and all failure-causing inputs are even. Then
first glance, one might attribute this rather surprising result to the highly restricted
form of mutation testing considered. We therefore now consider mutation testing with
additional mutation operators. Each application of a mutation operator gives rise to an
additional non-empty subdomain, provided that the mutated program is not equivalent
to the original program. Thus, additional mutation operators can certainly increase the
fault-detecting ability. However, most mutation operators proposed in the literature do
not necessarily lead to proper coverage of branch testing. We therefore believe that, even
with the addition of other mutation operators, it will be possible to construct programs
for which mutation testing is less likely to detect faults than branch testing when assessed
using either M or E.
5 The Condition Coverage Family
Several criteria based on considering the individual conditions that comprise a decision
have been proposed. We will refer to these criteria as the condition-coverage family. Consider
a conditional statement controlled by a compound predicate, such as if
then S. Branch testing would require the selection of a test case that makes the predicate
and B) evaluate to true and a test case that makes evaluate to false.
Note that it is possible to adequately test this statement using the branch testing strat-
egy, without ever having the sub-expression B be false simply by selecting one test case
making both A true and B true and another making A false and B true. Similarly the
statement if or B) then S can be adequately branch-tested without B ever evaluating
to true. Myers [16] argued that this is a weakness of branch testing, since a fault
P(x,y:
begin
else

Figure

2: A simple program.

Figure

3: Flow graph of program from Figure 2.
such as B being the wrong expression could go undetected when using branch testing. He
therefore introduced three new criteria, condition-coverage, decision-condition-coverage,
and multiple-condition-coverage intended to overcome this deficiency.
Recall that a decision is a maximal Boolean expression controlling the execution of
a conditional statement or loop and that decision-coverage requires that every decision
take on the value true at least once during testing and also take on the value false at
least once. For example, consider the program shown in Figure 2, A flow-graph of this
program is shown in Figure 3. In this program, (x=1) and (y=1) is a decision.
A condition is a Boolean variable, a relational expression, or a Boolean function
occurring in a decision. For this example, (x=1) is a condition, as is (y=1). Thus a
decision is made up of conditions. Condition-coverage requires that every condition take
on the value true at least once and take on the value false at least once. For this
example, two test cases are sufficient to satisfy condition-coverage. Test suites of the
among others, would satisfy the criterion.
Decision-condition-coverage requires that every decision take on the value true at
least once and take on the value false at least once and that every condition take on
the value true at least once during testing and take on the value false at least once. In
this example, the same test suite that satisfied condition-coverage would satisfy decision-
condition-coverage.
Multiple-condition-coverage requires that every combination of truth values of conditions
occurs at least once during testing. 5 For the example of Figure 2, multiple-
condition-coverage would require four test cases:
Note that the number of subdomains arising from multiple condition coverage is
where n is the number of decision statements in P , and c i is the number of conditions
in the i th decision in P . Thus, in the worst case the number of test cases required by
multiple-condition-coverage is exponential in the number of conditions in P , while the
numbers of test cases required by decision-coverage, condition-coverage, and decision-
condition-coverage are all at worst linear in the number of conditions.
Example 4:
Consider again the program shown in Figure 2. Recall that the input domain of this
program is and that the decision-
coverage subdomains are SD dc
Let
5 There is some variation in the meaning of the term multiple-condition-coverage in subsequent software
testing literature. Our usage of the terms here is consistent with Myers' definitions.
These are the subdomains corresponding to the conditions and their negations, so the
multi-set of subdomains arising from condition-coverage is
SD cc
The multi-set of subdomains arising from decision-condition-coverage is
SD dcc
Finally, let
These subdomains, along with D 1 correspond to the combinations of conditions, so the
multi-set of subdomains arising from multiple-condition-coverage is
SD mcc g:Notice that for this program the condition-coverage and decision-condition-coverage
criteria give rise to non-disjoint subdomains. More generally, programs exist for which
each of the criteria in this family have non-disjoint subdomains. There are several reasons
for this. First, the conditions in a compound predicate need not be mutually exclusive.
Second, each condition or negation of a condition overlaps with the decision in which it
occurs or the negation of that decision. Furthermore, even the subdomains arising from
a particular decision or condition and its own negation, or from different combinations
of conditions and their negations may intersect; this can occur when the decision occurs
within a loop - a single test case may cause the decision (or condition or combination of
conditions) to evaluate to true on one iteration of the loop and to false on another.
Myers points out (though not using this terminology) that condition-coverage does
not subsume decision-coverage but decision-condition-coverage does. He then points out
what he considers to be a deficiency in decision-condition-coverage: it is possible to satisfy
decision-condition-coverage without executing all the branches in the transformed flow
graph in which compound decisions are broken into series of decisions containing only
individual conditions. Myers introduced multiple-condition-coverage to overcome this
deficiency. He indicates (correctly) that multiple-condition-coverage subsumes decision-
condition-coverage and concludes that multiple-condition-coverage is superior to decision-
condition-coverage. Summarizing the criteria, Myers says,
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.([16], p. 44)
Given that Myers recommends multiple-condition-coverage as a minimal criterion, in
spite of its expense, in a book that is widely used by testing practitioners, it is worth investigating
whether multiple-condition-coverage is really good at detecting faults. We show
that both decision-condition-coverage and multiple-condition-coverage universally properly
cover decision-coverage, but that multiple-condition-coverage does not universally
properly cover decision-condition-coverage. We exhibit a program for which decision-
condition-coverage is better than multiple-condition-coverage according to both M and
Before examining the relationship between the criteria, we note that one could argue
that decision-condition-coverage has an "unfair advantage" over multiple-condition-
coverage in the program in Figure 2 because in this particular program there are more
decision-condition-coverage subdomains than multiple-condition-coverage subdomains.
In fact, the reason multiple-condition-coverage fails to properly cover decision-condition-
coverage is much more fundamental than that. To illustrate this, we introduce a "pared-
down" version of decision-condition-coverage, which we call minimized-decision-condition-
coverage. Note that the decision-condition-coverage criterion has several redundant sub-
domains. Any test case satisfying obviously satisfies both A and B. Similarly,
any test case satisfying either not A or not B satisfies not B). So the subdomains
corresponding to A, B, and not and B) can be eliminated from consideration.
Redundant subdomains arising from a disjunctive clause can be eliminated in a similar
manner.
More precisely, for the minimized-decision-condition-coverage criterion, the multi-set
of subdomains SD mdcc (P; S) is obtained as follows: for each decision d of the form A
and B, include the subdomain D d=T consisting of those inputs that make d evaluate to
true, the subdomain DA=F consisting of those inputs that make A evaluate to false,
and the subdomain DB=F consisting of those inputs that make B evaluate to false;
for each decision d of the form A or B include the subdomain D d=F consisting of those
inputs that make d evaluate to false, the subdomain DA=T consisting of those inputs
that make A evaluate to true, and the subdomain DB=T consisting of those inputs that
make B evaluate to true; for all other decisions, include all of the corresponding decision-
condition-coverage subdomains. Note that for any program, the number of subdomains
arising from minimized-decision-condition coverage is less than or equal to the number
arising from multiple-condition-coverage.
Example 5:
Consider the program shown in Figure 2. For any specification S, the subdomains arising
from minimized-decision-condition-coverage are
SD mdcc g;Theorem 5 The relations among the condition-coverage family of criteria are as follows:
1. Decision-condition-coverage universally properly covers decision-coverage.
2. Multiple-condition-coverage universally properly covers decision-coverage.
3. Minimized-decision-condition-coverage universally properly covers decision-coverage.
4. Decision-condition-coverage universally properly covers minimized-decision-condition-
coverage.
5. Multiple-condition-coverage does not universally properly cover minimized-decision-
condition-coverage.
6. Multiple-condition-coverage does not universally properly cover decision-condition-
coverage.
7. Multiple-condition-coverage does not universally properly cover condition-coverage.
Proof:
We prove parts 3, 5 and 7. The rest of the proof is straight-forward and can be found
in [9]. To see part 3, let D 2 SD dc (P; S). By definition of decision-coverage, D is either
D d=T or D d=F for some decision d. Case 1: d is of the form A and B and D is D d=T .
Then D 2 SD mdcc . Case 2: d is of the form A and B and D is D d=F . Then DA=F and
Case 3: d is of the form A or B and D is
D d=T . Then DA=T and DB=T 2 SD mdcc and Case 4: d is of the
form A or B and D is D d=F . Then D 2 SD mdcc . If d is not a conjunct or disjunct of two
conditions then D 2 SD mdcc . In each of these cases, D is a union of minimized-decision-
condition subdomains arising from this decision d. Since each decision gives rise to its
own collection of minimized-decision-condition subdomains, the covering is proper.
To see part 5, consider again the program in Figure 2. Recall that SD mcc
It is possible to express each minimized-
decision-condition subdomain as a union of multiple-condition-coverage subdomains, as
follows:
id subdomain d m

Table

2: Subdomain, sizes, and numbers of failures for program in Example 6
Notice that the subdomain D 9 only occurs once in SD mcc (P; S) but occurs twice in the
covering of SD mdcc (P; S), and that both of these occurrences are necessary in the sense
that any covering of SD mdcc (P; S) must have at least two occurrences of D 9 . There-
fore, multiple-condition-coverage does not properly cover minimized-decision-condition-
coverage for this program.
The proof of part 7 is almost identical. Since D 5 must be used
more than once in any covering of SD cc
We now use this result to exhibit a program for which each of the criteria discussed
in this section, except for decision-coverage, is better than multiple-condition-coverage
according to measures M and E.
Example
Let P be the program in Examples 4 and 5 and, as in Example be a
specification such that P (x;
10. The values for m and d for each subdomain are shown in Table 2. Note
that since all of the 45 failure-causing inputs lie in subdomains D 5 , D 6 , and D 9 , and no
failure-causing inputs lie in D 1 , D 7 , or D 8 , the minimized-decision-condition criterion has
a greater chance of selecting a failure-causing input than the multiple-condition-coverage
criterion, even though there are more subdomains (and hence more test cases) induced
by the multiple-condition-coverage criterion than by the minimized-decision-condition
criterion. In particular:
d 6
criterion
decision-coverage 0.45 0.45
condition-coverage 0.75 1.00
decision-condition-coverage 0.86 1.45
minimized decision-condition-coverage 0.75 1.00
multiple-condition-coverage 0.56 0.56

Table

3: Values of M and E for the program from Example 5.
whereas
d 7
d 9
Similarly,
E(mdcc;
d 6
whereas
E(mcc;
d 7
d 9
The values of M and E for condition-coverage and decision-condition-coverage, shown
in

Table

3, illustrate that multiple-condition-coverage also performs worse than these
criteria for this program and specification, according to these measures. As noted above,
multiple-condition-coverage requires more test cases for this program than are required
by minimized-decision-condition-coverage, so this example also illustrates that bigger test
suites are not necessarily better. 2
Myers' motivation for introducing multiple-condition-coverage was that it is possible
to satisfy decision-condition-coverage without covering all of the edges in the flow graph
arising from assembly code. This concern may have arisen from an analogy with hardware
testing, where wires connecting gates are the analogs of branches in assembly code.
Even though this is not an issue for software testing, there is some intuitive motivation
for requiring that such edges be executed. The "low-level" flow graph has edges corresponding
to the evaluations of subexpressions in a condition. If the program has an
erroneous subexpression of the form A and B, the subdomain consisting of those inputs
that make the subexpression evaluate to true may concentrate the failure-causing inputs
more than the subdomains true corresponding to the individual con-
ditions. Similarly, if the program has an erroneous subexpression of the form A or B,
the subdomain consisting of those inputs that make the subexpression evaluate to false
may concentrate the failure-causing inputs more than the subdomains
false corresponding to the individual conditions. Consequently, selecting test cases
from the subexpression subdomains can increase the likelihood of detecting that type
of fault. Several criteria, including the multi-value expressions criterion [11, 21], that
capture this intuition and do properly cover decision-condition-coverage, but whose cost
is linear in the number of conditions, are discussed in [9].
6 Conclusion
We have compared the fault-detecting ability of several software testing criteria. This
comparison was done according to carefully defined notions of what it means for criterion
C 1 to be better at detecting faults than criterion C 2 . In particular, we investigated
whether test suites chosen by randomly selecting one element from each subdomain induced
by C 1 are at least as likely to include at least one failure-causing input as are test
suites chosen in the same manner to satisfy C 2 .
We had previously shown that if C 1 universally properly covers C 2 , then C 1 is better
than C 2 , in that sense. In this paper, we extended this result by using the expected
number of failures exposed as the basis for comparison. We showed that if C 1 properly
covers C 2 , the expected number of failures exposed by test suites selected using this same
strategy is guaranteed to be at least as large for C 1 as for C 2 . Note that if C 1 universally
properly covers C 2 , then C 1 is guaranteed to be at least as good as C 2 according to these
measures, for any program, regardless of what faults are in the program.
We showed that the all-p-uses, all-uses, required-k-tuples+, context-coverage, ordered-
context-coverage, minimized-decision-condition-coverage, decision-condition-coverage, and
multiple-condition-coverage, all universally properly cover decision-coverage. However,
limited mutation testing subsumes but does not universally properly cover decision-
coverage. Furthermore, multiple-condition-coverage subsumes but does not universally
properly cover decision-condition-coverage; context-coverage subsumes but does not universally
properly cover all-uses or all-p-uses; and ordered-context-coverage subsumes but
does not universally properly cover all-uses or all-p-uses. These relations are summarized
in

Figure

4. In each case for which C 1 fails to universally properly cover C 2 , we exhibited
a simple program for which
Since multiple-condition-coverage, context-coverage, and ordered-context-coverage each
potentially require a number of test cases which is exponential in some aspect of the
program size, this calls into question their usefulness. We emphasize that the results

Figure

4: Summary of Relations between criteria. A solid arrow from C 1 to C 2 indicates
that C 1 universally properly covers C 2 , a dotted arrow from C 1 to C 2 indicates that C 1
subsumes but does not universally properly cover any relation that is not explicitly
shown in the figure and that does not follow from transitivity along with the fact that
universally properly covers implies subsumption, does not hold.
presented here show the existence of programs and specifications for which C 2 is better
at detecting faults than C 1 in situations when C 1 subsumes but does not universally
properly cover C 2 . They are based on the fact that when C 1 does not properly
cover C 2 for program P , it is often possible to find a specification S (or equivalently,
to find a distribution of failure-causing inputs) for which M(C 2 ;
and E(C 2 ; However, even for such a program P , there are other
specifications S 0 (or equivalently, other distributions of failure-causing inputs) for which
even when
does not universally properly cover C 2 , it may be the case that C 1 properly covers C 2
for the particular program that is being tested, and thus C 1 is guaranteed to be at least
as likely as C 2 to detect a fault in that program, but not necessarily in others.
There are several implications of these results for the testing practitioner. If C 1
universally properly covers C 2 , the practitioner is guaranteed to be more likely to detect
a fault using C 1 than using C 2 , provided that tests are selected using the strategy described
earlier. On the other hand, if C 1 does not properly cover C 2 for the program under test,
the practitioner should be warned that even if C 1 requires many more test cases than
may be less likely to detect a fault. Thus, criteria which are relatively low in
the hierarchy of criteria induced by the properly covers relation, may be of questionable
value. On the other hand, it certainly could happen that such criteria are indeed good
at detecting faults in "typical" programs. This paper does not address that question;
in fact, in the absence of a precise notion of what constitutes a "typical" program, such
questions can only be answered through the accumulation of anecdotal evidence.
We also note that it seems reasonable to conjecture that using test selection strategies
that closely approximate the one described here will yield similar results in practice.
However, more analytical and/or empirical research will be needed to bear this out for
particular approximation strategies. One might argue that this approach is "making the
real world fit the model", but in fact doing so may be justified. In software engineering,
unlike the physical sciences, we can exercise some significant control over the real world
when there is some benefit from doing so. For example, it may be reasonable to devise
test data selection strategies that closely resemble the ones used in our model. The payoff
for this would be that the tester has precise knowledge about the relative fault-detecting
ability of criteria, without prior knowledge of the nature of the faults in a program.
Our investigation also sheds some light on how to develop new criteria that are provably
better than an existing criterion C. One possibility is to take a criterion C 0 that
universally covers but does not universally properly cover C, find those subdomains of
C 0 that are used k ? 1 times in the covering of C, and include k duplicates of each such
subdomain, or equivalently, choose k test cases from each such subdomain.
Finally, we note again that our results are based on a test suite selection procedure
that is an idealization of the way test suites are selected in a typical testing environment.
It is assumed that test cases are selected only after the domain has been divided into
subdomains. In practice, these testing criteria are generally used as the basis for evaluating
the adequacy of test suites, not for selecting test cases. This suggests two open
problems: develop practical test selection algorithms that approximate the strategy used
here, and conduct theoretical studies similar to this one based on measures that more
closely reflect existing test selection strategies.

Acknowledgments

: The authors would like to thank the anonymous referees for carefully
reading the manuscript and making several useful suggestions. Some of the results
presented in this paper appeared in the Proceedings of the IEEE 15th International Conference
on Software Engineering, May 1993.



--R

Mutation analysis: Ideas
A formal evaluation of data flow path selection criteria.
Hints on test data selection: Help for the practicing programmer.
An evaluation of random testing.
Data flow analysis in software reliability.
Test selection for analytical comparability of fault-detecting ability
An applicable family of data flow testing criteria.
Assessing the fault-detecting ability of testing methods
Analytical comparison of several testing strategies.
A formal analysis of the fault detecting ability of testing methods.

A mathematical framework for the investigation of testing.
Theoretical comparison of testing methods.
Partition testing does not inspire confidence.
A data flow oriented program testing strategy.
The Art of Software Testing.
On required element testing.
Data flow analyisis techniques for program test data selection.
Selecting software test data using data flow information.
A structural test selection criterion.
Comparison of structural test coverage metrics.
Comparing test data adequacy criteria.
Analyzing partition testing strategies.
Comparison of program testing strate- gies
--TR
Selecting software test data using data flow information
A structural test selection criterion
An Applicable Family of Data Flow Testing Criteria
Comparing test data adequacy criteria
Theoretical comparison of testing methods
A Formal Evaluation of Data Flow Path Selection Criteria
Partition Testing Does Not Inspire Confidence (Program Testing)
Analyzing Partition Testing Strategies
Comparison of program testing strategies
Assessing the fault-detecting ability of testing methods
Experimental results from an automatic test case generator
Data Flow Analysis in Software Reliability
Data Abstraction, Implementation, Specification, and Testing
Art of Software Testing
A Formal Analysis of the Fault-Detecting Ability of Testing Methods
Data flow analysis techniques for test data selection

--CTR
Bingchiang Jeng , Elaine J. Weyuker, A simplified domain-testing strategy, ACM Transactions on Software Engineering and Methodology (TOSEM), v.3 n.3, p.254-270, July 1994
Alberto Avritzer , Elaine J. Weyuker, The Automatic Generation of Load Test Suites and the Assessment of the Resulting Software, IEEE Transactions on Software Engineering, v.21 n.9, p.705-716, September 1995
Alberto Avritzer , Elaine J. Weyuker, Generating test suites for software load testing, Proceedings of the 1994 ACM SIGSOFT international symposium on Software testing and analysis, p.44-57, August 17-19, 1994, Seattle, Washington, United States
Istvn Forgcs, An exact array reference analysis for data flow testing, Proceedings of the 18th international conference on Software engineering, p.565-574, March 25-29, 1996, Berlin, Germany
Phyllis G. Frankl , Oleg Iakounenko, Further empirical studies of test effectiveness, ACM SIGSOFT Software Engineering Notes, v.23 n.6, p.153-162, Nov. 1998
Allen S. Parrish , Stuart H. Zweben, On the Relationships Among the All-Uses, All-DU-Paths, and All-Edges Testing Criteria, IEEE Transactions on Software Engineering, v.21 n.12, p.1006-1009, December 1995
Finding failures by cluster analysis of execution profiles, Proceedings of the 23rd International Conference on Software Engineering, p.339-348, May 12-19, 2001, Toronto, Ontario, Canada
Giovanni Denaro , Sandro Morasca , Mauro Pezz, Deriving models of software fault-proneness, Proceedings of the 14th international conference on Software engineering and knowledge engineering, July 15-19, 2002, Ischia, Italy
Tsong Yueh Chen , Yuen Tak Yu, On the Expected Number of Failures Detected by Subdomain Testing and Random Testing, IEEE Transactions on Software Engineering, v.22 n.2, p.109-119, February 1996
Sandro Morasca , Stefano Serra-Capizzano, On the analytical comparison of testing techniques, ACM SIGSOFT Software Engineering Notes, v.29 n.4, July 2004
R. M. Hierons, Comparing test sets and criteria in the presence of test hypotheses and fault domains, ACM Transactions on Software Engineering and Methodology (TOSEM), v.11 n.4, p.427-448, October 2002
Andy Podgurski , Wassim Masri , Yolanda McCleese , Francis G. Wolff , Charles Yang, Estimation of software reliability by stratified sampling, ACM Transactions on Software Engineering and Methodology (TOSEM), v.8 n.3, p.263-283, July 1999
D. F. Yates , N. Malevris, An objective comparison of the cost effectiveness of three testing methods, Information and Software Technology, v.49 n.9-10, p.1045-1060, September, 2007
Walter J. Gutjahr, Partition Testing vs. Random Testing: The Influence of Uncertainty, IEEE Transactions on Software Engineering, v.25 n.5, p.661-674, September 1999
Hong Zhu, A Formal Analysis of the Subsume Relation Between Software Test Adequacy Criteria, IEEE Transactions on Software Engineering, v.22 n.4, p.248-255, April 1996
Phyllis Frankl , Dick Hamlet , Bev Littlewood , Lorenzo Strigini, Choosing a testing method to deliver reliability, Proceedings of the 19th international conference on Software engineering, p.68-78, May 17-23, 1997, Boston, Massachusetts, United States
Elaine J. Weyuker, Using operational distributions to judge testing progress, Proceedings of the ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
Phyllis G. Frankl , Richard G. Hamlet , Bev Littlewood , Lorenzo Strigini, Evaluating Testing Methods by Delivered Reliability, IEEE Transactions on Software Engineering, v.24 n.8, p.586-601, August 1998
Phyllis G. Frankl , Yuetang Deng, Comparison of delivered reliability of branch, data flow and operational testing: A case study, ACM SIGSOFT Software Engineering Notes, v.25 n.5, p.124-134, Sept. 2000
Yuen Tak Yu , Man Fai Lau, A comparison of MC/DC, MUMCUT and several other coverage criteria for logical decisions, Journal of Systems and Software, v.79 n.5, p.577-590, May 2006
Richard A. DeMillo , Aditya P. Mathur , W. Eric Wong, Some Critical Remarks on a Hierarchy of Fault-Detecting Abilities of Test Methods, IEEE Transactions on Software Engineering, v.21 n.10, p.858-861, October 1995
Mary Jean Harrold, Analysis and Testing of Programs with Exception Handling Constructs, IEEE Transactions on Software Engineering, v.26 n.9, p.849-871, September 2000
Alessandro Orso , Saurabh Sinha , Mary Jean Harrold, Classifying data dependences in the presence of pointers for program comprehension, testing, and debugging, ACM Transactions on Software Engineering and Methodology (TOSEM), v.13 n.2, p.199-239, April 2004
Antonia Bertolino, Software Testing Research: Achievements, Challenges, Dreams, 2007 Future of Software Engineering, p.85-103, May 23-25, 2007
Hong Zhu , Patrick A. V. Hall , John H. R. May, Software unit test coverage and adequacy, ACM Computing Surveys (CSUR), v.29 n.4, p.366-427, Dec. 1997
fault-detecting ability;program testing;condition-coverage techniques;branch testing;software testing;software test data adequacy;programming theory;data flow testing;program debugging;independent random selection;probabilistic measure;test suite;mutation testing