A Formal Analysis of the Fault-Detecting Ability of Testing Methods.
Several relationships between software testing criteria, each induced by a relation between the corresponding multisets of subdomains, are examined. The authors discuss whether for each relation R and each pair of criteria, C/sub 1/ and C/sub 2/, R(C/sub 1/, C/sub 2/) guarantees that C/sub 1/ is better at detecting faults than C/sub 2/ according to various probabilistic measures of fault-detecting ability. It is shown that the fact that C/sub 1/ subsumes C/sub 2/ does not guarantee that C/sub 1/ is better at detecting faults. Relations that strengthen the subsumption relation and that have more bearing on fault-detecting ability are introduced.
Introduction
Over the last several years, researchers have defined a wide variety of software testing
techniques, studied their properties, and built tools based on some of them. Recently,
there has been increasing interest in the question of how techniques compare to one
another in terms of their ability to expose faults.
Aspects of this problem have been addressed through experiments [2], simulations [1,
7], and analysis [9, 14]. While these approaches offer certain insights, the results lack
generality, either because of the inherent nature of experimentation and simulation, or
because of the assumptions underlying the simulations and analyses. In particular those
simulations and analyses [1, 7, 14] investigated criteria that partition the input domain
of the program into disjoint subdomains. In this paper, we analyze the more realistic
situation in which the criteria divide the input domain into overlapping subdomains. We
Author's address: Computer Science Dept., Polytechnic University, 333 Jay St., Brooklyn, N.Y.
11201. Supported by NSF Grant CCR-8810287 and by the New York State Science and Technology
Foundation Center for Advanced Technology program.
y Author's address: Courant Institute of Mathematical Sciences, New York University, 251 Mercer
Street, New York, NY 10012. Supported by NSF grant CCR-8920701 and by NASA grant NAG-1-1238.
characterize various relationships between criteria, and show circumstances under which
we can conclude that test suites chosen using one criterion are more likely to expose
faults than test suites chosen using another. We also apply these results to compare
well-known control flow based and data flow based techniques.
Subsumption has frequently been used to compare criteria. Criterion C 1 subsumes
criterion C 2 if every test suite that satisfies C 1 also satisfies C 2 . In this paper, we show
that according to three probabilistic measures of fault-detecting ability, the fact that C 1
subsumes C 2 does not guarantee that C 1 is better at detecting faults than C 2 . These
measures are related to two different test data selection strategies. We also explore the
question of how the subsumes relation can be strengthened in order to obtain a relation
that has more bearing on fault-detecting ability. We define two natural relations, covers
and partitions, each of which is stronger than subsumes, and show that, in the worst case,
neither of them provide much additional insight into fault-detecting ability. Finally, we
define two variations of these relations, properly covers and properly partitions, and prove
that when C 1 properly covers or properly partitions C 2 , C 1 is guaranteed to be better at
detecting faults than C 2 when assessed using certain reasonable probabilistic measures.
1.1 Preliminary Definitions
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. 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 .
Therefore, f0; but it is not the case that f0; 1; 1g ' f0; 1; 2g.
A test suite is a multi-set of test cases, each of which is a possible input to the
program. 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. These techniques are sometimes referred to as
partition testing, but in fact, most of them subdivide the input domain into overlapping
subdomains, and thus do not form a true partition of the input domain. In this paper,
we will refer to such strategies as subdomain-based testing. In subdomain strategies
based on the program's structure, each subdomain consists of all elements that cause a
particular code element to be executed. For example, in branch testing, each subdomain
consists of all inputs that cause execution of a particular branch; in path testing, each
subdomain consists of all inputs that cause execution of a particular path; in data flow
testing using the all-uses criterion, each subdomain consists of all inputs that execute
any path from a particular definition of a variable v to a particular use of v without any
intervening redefinition of v. Other subdomain-based testing strategies include mutation
testing, in which each subdomain consists of all inputs that kill a particular mutant;
specification-based testing techniques, in which each subdomain consists of inputs that
satisfy a particular condition or combination of conditions mentioned in the specification;
and exhaustive testing, in which each subdomain consists of a single point. In most of
these strategies, most programs and specifications give rise to overlapping and duplicate
subdomains.
A test data adequacy criterion is a relation C ' Test Suites\ThetaPrograms\ThetaSpecifications,
that, in practice, is used to determine whether a given test set T does a "thorough" job
of testing program P for specification S. If C(T; holds, we will say "T is adequate
for testing P for S according to C", or, more simply, "T is C-adequate for P and S".
A testing criterion C is subdomain-based if, for each program P and specification S,
there is a non-empty multi-set SDC (P; S) of subdomains (subsets of the input domain),
such that C requires the selection of one or more test cases from each subdomain in
If C requires the selection of more than one test case from a given subdomain,
they need not be distinct. 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, the same set of test cases might cause the execution of two
different statements, and hence appear twice in the multi-set of subdomains arising from
the statement testing criterion. Depending on the details of the criterion and the test
selection strategy, it may then be necessary to choose test cases from such a subdomain
more than once. Note that since SDC 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 criterion.
Subdomain-based criterion C is said to be applicable to (P,S) if and only if there exists
a test suite T such that C(T; and 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 specifically noted. In fact, many of the criteria
that have been defined and discussed in the software testing literature are not
universally applicable. In path-based or structural criteria, this occurs because infeasible
paths through the program can lead to testing requirements that can never be fulfilled
(represented by empty subdomains belonging to SDC (P; S)), while in mutation testing
this occurs due to mutants that are equivalent to the original program. However, it
is the universally applicable analogs of those criteria (obtained by removing the empty
subdomain from SDC (P; S)) that are actually usable in practice. It is important to note
that the relationship between the universally applicable analogs of criteria may be different
than that between the original criteria. For example, in [3] we defined universally
applicable analogs of the data flow testing criteria defined in [12, 13], and showed that
while the all-du-paths criterion subsumes the all-uses criterion, the universally applicable
analog of all-du-paths does not subsume the universally applicable analog of all-uses.
In order to illustrate some of our points with realistic examples, we review the definitions
of several well-known criteria. Since some of these criteria are based on program
structure, it is necessary at this point to make certain assumptions about the programs
under test. We will limit attention to programs that are written in Pascal with no goto
statements. 1 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. 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 NFA have
the possibility of referencing an undefined variable. Although the question of whether
a given program satisfies NFA is undecidable, it is possible to check the stronger, no
anomalies property (NA), which requires that every path from the start node to a use of
a variable v to pass through a node having a definition of v. Furthermore, NA can be
enforced by adding a dummy definition of each variable to the start node.
The all-edges criterion (also known as branch testing) requires that every edge in the
program's flow graph be executed by at least one test case. Data flow testing criteria [8,
10, 11, 13] require that the test data exercise paths from points at which variables are
defined to points at which their values are subsequently used. Occurrences of variables in
the program under test are classified as being either definitions, in which values are stored,
or uses, in which values are fetched. In [13] variable uses are further classified as being
either p-uses, i.e., uses occurring in the Boolean expression in a conditional statement,
or c-uses, i.e., uses occurring in assignment statements or arguments in a procedure
call. The all-uses criterion [13] requires that the test data cover every definition-use
association (dua) in the program, where a dua 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. 2 A test case
covers dua (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 [13] is a restricted version of all-uses that
only requires that the test data cover every (d,u,v) in which u is an edge with a p-use
of variable v. Precise definitions of the criteria for the subset of Pascal in question are
given in [3].
Notice that these criteria are not universally applicable; in fact, for many programs
the all-p-uses and all-uses criteria are not applicable because some dua is not executable.
For example, any program having a for loop whose bounds are non-equal constants has
an unexecutable dua involving the initialization of the counter variable and the edge
exiting the loop. Such a dua is unexecutable because the only executable path from the
definition to the use traverses the loop at least once, and in so doing, redefines the counter
variable [3]. In the sequel we will use the terms all-edges, all-p-uses, and all-uses to refer
to the universally applicable analogs of these criteria, unless otherwise specifically noted.
This assumption is used in the proof of Theorem 5, below.
2 A definition-clear path with respect to v is a path in which none of the nodes, except perhaps the
first and last, have a definition of variable v.
A program satisfies the no syntactic undefined p-uses property (NSUP) if for every
p-use of a variable v, there is a path from program entry to the p-use along which v is
defined. Rapps and Weyuker showed that for the class of programs that satisfies NSUP,
for the original (not universally applicable) criteria, all-p-uses subsumes all-edges. In [3],
we showed that a stronger restriction on the class of programs considered is needed to
make subsumption hold for the universally applicable analogs of the criteria. Namely,
we required the no feasible undefined p-uses property (NFUP), which requires that for
every p-use of a variable v, there is an executable path from program entry to the p-use
along which v is defined. Since any program that satisfies NFA also satisfies NFUP, for
the class of programs we are considering, all-uses subsumes all-edges.
Detecting Ability of Subdomain Criteria
In this section, we define three probabilistic measures of the fault-detecting ability of a
testing criterion. In [1, 7, 14] the probability that a test set generated to satisfy some
subdomain-based testing strategy would expose a fault was compared to the probability
that a randomly generated test set of the same size would expose a fault. In contrast, we
are interested in comparing the probability that test sets generated to satisfy different
subdomain-based strategies will detect at least one fault.
We will focus on two conceptually simple test selection strategies. The first requires
the tester to independently randomly select test cases from the domain until the adequacy
criterion has been satisfied. The second strategy assumes that the domain has
first been divided into subdomains and then requires independent random selection of a
predetermined number, n, of test cases from each subdomain. We assume throughout
that the random selection is done using a uniform distribution. These strategies, Sel 1
and Sel 2 , are shown in Figure 1.
Our analytical results on the fault-detecting ability of subdomain criteria are based
on the assumption that test suites are selected using Sel 1 or Sel 2 . In practice it is rare
to use either of these strategies, but rather something closer to a combination of the two.
Typically a tester begins by selecting some test cases. Sometimes these test cases are
chosen because the tester believes they have some particular significance, and sometimes
they are chosen in a more ad hoc fashion. After some amount of testing, the tester
checks to see which features of the program still need to be exercised in order to satisfy
the criterion and tries to select test cases accordingly. This corresponds to selecting test
cases from the appropriate subdomains in a manner similar to the second strategy. Thus,
for example, one might select an all-edges adequate test suite by generating an initial
test suite, checking to see which edges had not yet been covered, and then selecting test
cases specifically aimed at covering each of the edges that remain unexercised.
Note that when Sel 1 is used, a test case that lies in the intersection of two or more
subdomains may "count" toward each subdomain, while when using Sel 2 it will not.
test suite;
repeat
t := a uniformly randomly selected element of the input domain;
add t to T
until T is C-adequate
test suite;
for each subdomain D 2 SDC (P; S) do
begin
for to n do
begin
t := a uniformly randomly selected element of D;
add t to T

Figure

1: Two test suite selection strategies
Thus, Sel 1 may lead to selection of substantially smaller test suites than Sel 2 (1):
Also note that if the multi-set SDC contains m copies of some subdomain D,
then Sel 2 (n) requires that n test cases be selected independently from D m different
times, for a total of m \Theta n test cases from D. This can make Sel 2 sensitive to details of
the definitions of the testing criterion. For example, the number of all-edges subdomains
for a given program P will depend on details of the construction of the P's flow graph,
such as whether or not an extra exit node is added to the graph. One could avoid such
problems by assuming that duplicate elements of SDC (P; S) are removed before test
case selection. However, in practice one usually works with predicates describing the
subdomains, rather than with explicit lists of their elements. Since it is undecidable
whether two predicates are equivalent, it is not always possible to identify duplicate
subdomains. Consequently, we do not assume that duplicates have been eliminated.
Obviously there are many reasonable measures of fault-detecting ability that could
be defined. Our measures are related to the probability that a test suite will expose
a fault. Following the notation used in [14], given a program P, specification S, and
criterion C, we let d the number of failure-causing inputs in D i , where
g.
As Weyuker and Jeng [14] have noted, the fault-detecting ability of a criterion is
related to the extent to which failure-causing inputs are concentrated by its subdomains.
The first measure we consider is
Let D max denote a subdomain that has the highest concentration of failure-causing inputs,
i.e., a subdomain for which m i =d i is maximal. Since we are considering subdomain-based
criteria, any C-adequate test set contains at least one test case from D max . When using
Sel 1 or Sel 2 , each element of D max is equally likely to be selected to "represent" D max ,
and therefore M 1 gives a crude lower bound on the probability that a C-adequate test
suite selected using Sel 1 or Sel 2 will expose at least one fault.
The second measure we consider is
Y
gives the exact probability that a test set chosen using Sel 2 (1) will expose at least
one fault. Duran and Ntafos [1] and Hamlet and Taylor [7] performed simulations investigating
whether hypothetical partition testing strategies (i.e., subdomain-based testing
strategies in which the subdomains are pairwise disjoint) are more likely to expose
faults than random testing according to this measure. Weyuker and Jeng investigated
similar questions analytically [14]. In this paper, we investigate the more realistic
case of subdomain-based criteria in which the subdomains may intersect, and compare
subdomain-based criteria to one another rather than to random testing.
One problem with using M 2 as a measure is that one subdomain-based criterion C 1
may divide the domain D into k 1 subdomains while another criterion C 2 divides D into
subdomains where Then, in a sense, M 2 gives C 1 an unfair advantage since
test cases while C 2 only requires k 2 , and hence M 2 is comparing the
fault-detecting qualities of different sized test suites. In order to correct this imbalance,
we first define a measure that is a generalization of M 2 . Instead of always selecting one
test case per subdomain, n test cases are chosen per subdomain. We call this measure
Y
Of course this measure still has the deficiency cited above that different numbers of
test cases might be needed to satisfy C 1 and C 2 . The reason M 3 is a useful generalization
of M 2 is that it allows us to adjust for the test suite size differences. Letting k 1 and
denote the number of subdomains of C 1 and C 2 , respectively, for program P and
specification S, and letting compensate for the inequality in test set
size by comparing
M 3 is actually a special case of the measure called P p in [1, 7, 14]. In those papers,
a strategy could select a different number of test cases for each subdomain, whereas M 3
requires the same number to be selected from each subdomain.
3 Relations between criteria
In this section, we define five relations between criteria: the narrows, covers, partitions,
properly covers, and properly partitions relations. We compare these relations to one
another and to the subsumes relation, illustrate the relations with examples, and examine
what knowing that C 1 narrows, covers, partitions, properly covers, or properly partitions
C 2 for program P and specification S tells us about the relative values of each measure
of fault-detecting ability. Specifically, we investigate whether for each relationship R, for
every program P and specification S,
The resulting theorems are summarized in Table 1.
Many relations that have been previously studied in connection with fault-detecting
ability depend on the distribution of failure-causing inputs. These include Gourlay's
properly sometimes always sometimes
covers
properly always always sometimes
partitions C 2

Table

1: Summary of Results
power relation [6] and the better and probbetter relations proposed by Weyuker, Weiss,
and Hamlet [15]. In contrast, each of the relations between criteria introduced here is
induced by a relation between the corresponding multi-sets of subdomains. Thus, for
these relations the question of whether specification
depends purely on the way the criteria divide the input domain into subdomains, and
not on such factors as the way failure-causing inputs are distributed in the input domain.
Consequently, the results here are very general. If we prove that
that C 1 is at least as good as C 2 according to some probabilistic measure and if we
prove that holds for all programs and specifications in some class, then we are
guaranteed that C 1 is at least as good as C 2 for testing programs in that class, regardless
of which particular faults occur in the program.
3.1 The narrows relation
for every subdomain
there is a subdomain D 0 2 SDC1 (P; S) such that D 0 ' D. This notion
is known as refinement in point set topology. C 1 universally narrows C 2 if for every
program, specification pair (P,S), C 1 narrows C 2 for (P,S).
Observation 1 For each program P and specification S, the narrows relation is reflexive
and transitive. If SDC2
The next theorem shows that the narrows relation is closely related to the subsumes
relation. However, the question of whether C 1 narrows C 2 deals only with the relationships
between the multi-sets of subdomains induced by the two criteria, while the question
of whether C 1 subsumes C 2 may involve additional considerations, such as the number of
test cases from each subdomain required by each criterion. For example, consider criteria
such that for any (P,S), C 1 and C 2 give rise to the same set of subdomains,
but C 2 requires selection of two test cases from each subdomain whereas C 1 only requires
selection of one test case from each subdomain. Trivially, C 1 universally narrows C 2 .
However, C 1 does not subsume C 2 , since a test suite consisting of one element from each
subdomain is C 1 -adequate but not C 2 -adequate. As the next theorem shows, as long as
the criteria require selection of at least one element from each subdomain (as opposed to
requiring selection of at least k elements for some k ? 1) subsumption is equivalent to
the universally narrows relation.
Theorem 1 Let C 1 and C 2 be subdomain-based criteria, each of which explicitly requires
selection of at least one test case from each subdomain. Then C 1 subsumes C 2 if and only
if C 1 universally narrows C 2 .
Proof:
Assume C 1 universally narrows C 2 . Let T be a test suite that is C 1 -adequate for some
program P and specification S. T contains at least one element from each subdomain in
Thus, since each subdomain in SDC2 (P; S) is a superset of some subdomain
belonging to SDC1 T contains at least one element from each subdomain in
Conversely, assume C 1 does not universally narrow C 2 . There exists a program P and
a specification S such that some subdomain D 2 SDC2 (P; S) is not a superset of any
subdomain of SDC1 (P; S). Thus, for each D 0 2 SDC1 T be a
test suite obtained by selecting one element from D 0 \Gamma D for each D 0 2 SDC1 . Then T
is C 1 -adequate but not C 2 -adequate for (P,S). So C 1 does not subsume C 2 . 2
The next group of theorems establish that the fact that a criterion C 1 narrows criterion
does not guarantee that C 1 is better able to detect faults than C 2 , according to any
of our three measures.
Theorem 2 There exists a program P, specification S, and criteria C 1 and C 2 such that
Proof:
Let P be a program whose input domain is the integers between \GammaN and N , where
N ? 1. Let C 1 be the criterion that requires selection of at least one test case that is
zero and at least one test case that is non-zero. Let C 2 be the criterion that requires
selection of at least one test case that is greater than or equal to zero and at least one
test case that is less than or equal to zero. Suppose
That is, suppose P is correct on all inputs except and
There exists a program P, specification S, and criteria C 1 and C 2 such that
Proof:
be as in the proof of Theorem 2. Let
That is, P is incorrect on all inputs except
each d i , and m 1 are as above, but
There exists a program P, specification S, and criteria C 1 and C 2 such that
Proof:
Let P, S, C 1 , and C 2 be as in Theorem 3. Since jSDC1
so
1):Corollary 1 For each measure M i , there exists criteria C 1 and C 2 , program P and
specification S such that C 1 subsumes C
3.2 The covers relation
The next relation we examine, the covers relation, strengthens the narrows relation in a
natural way. The covers relation is interesting to examine because many criteria that had
previously been shown to subsume the all-edges criterion actually also cover all-edges.
for every subdomain
there is a non-empty collection of subdomains fD belonging
to SDC1 (P; S) such that D 1 universally covers C 2 if for every program,
specification pair (P,S), C 1 covers C 2 for (P,S).
Observation 2 For each program P and specification S, the covers relation is reflexive
and transitive. If C 1 covers C 2 for (P,S) then C 1 narrows C 2 for (P,S). If SDC2
The following example illustrates the distinction between the narrows and covers
relations.
Example 1:
Consider the criteria in the proof of Theorem 2. Since D 1 ' D 3 and D 1 ' D 4 , C 1 narrows
. However, since D 3 6= D 1 , D 3 6= D 2 , and D 3 6= (D 1 [ does not cover C 2 . 2
We next show that the all-p-uses and all-uses criteria universally cover the all-edges
criterion.
Theorem 5 The all-p-uses criterion universally covers the all-edges criterion.
Proof:
Let P be a program, let e be an executable edge in P, and let D e be the subdomain
corresponding to e, that is, the set of inputs that execute paths that cover edge e.
Case 1: e has a p-use of some variable v. 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 dua v)g. Since the program
satisfies the NFA property, every feasible path from the start node to e passes through
at least one of the
Case 2: e does not have a p-use of any variable. Then, since P has no goto statements,
there are edges e do have p-uses of variables, s.t. D
em . To
see this, let s be the innermost nested conditional or repetitive statement such that e is
in the subgraph corresponding to s. If s is an if-then, if-then-else, or case statement
is the edge going from the decision node toward e; if s is a while or
for statement then is the edge entering the loop; if s is a repeat statement
are the back-edge of the loop and the edge exiting the loop.
If e is not contained in any conditional or repetitive statement, e are the edges
out of the first decision node encountered on a path beginning at the start node. By case
1, each D e i is a union of all-p-uses subdomains; thus the union of all of these all-p-uses
subdomains equals D e . 2
Corollary 2 The all-uses criterion universally covers the all-edges criterion.
Proof:
For any program P and specification S, SD all\Gammap\Gammauses so by Observation
2, all-uses covers all-p-uses. Since covers is a transitive relation (Observation 2),
all-uses covers all-edges. 2
The next group of theorems shows that the fact that C 1 covers C 2 does not guarantee
that C 1 is better than C 2 according to any of the measures.
Theorem 6 There exists a program P, specification S, and criteria C 1 and C 2 such that
Proof:
Let P be a program whose input domain is the integers between \GammaN and N , where N - 1,
let
let C 1 and C 2 be the criteria whose subdomains are g.
P. Let S be a specification such that the only
failure-causing inputs are \GammaN and N . Then
S):Note that in the proof of Theorem 6, the fact that the failure-causing inputs lie outside
the intersection of D 2 and D 3 contributes to the fact that D 1 has a higher concentration
of failure-causing inputs than D 2 or D 3 . We next show that this phenomenon can
occur with "real" adequacy criteria, by exhibiting a program and specification for which
Example 2:
Consider the program shown in Figure 2. 3 Assume that the inputs x and y lie in the
range . The executable edges and executable definition-
p-use associations are shown in column 2 of Table 2. Their corresponding subdomains
are shown in column 3 of Table 2.
Assume that 3 - MAX - N . Notice that
MAX otherwise
On any input (x; y) such that y - MAX \Gamma 2, the path taken will go through either node
4 or node 5 on the first traversal of the loop (depending on the parity of x+ y), and then
will alternate between going through node 4 and going through node 5 on subsequent
traversals of the loop. Consequently, among all the inputs that cause execution of edge
(6,3), all of them except those in which both of the definition-use
associations (4,(6,3),y) and (5,(6,3),y).
We now manufacture a specification for which the program will fail on precisely
those inputs that lie within the subdomain corresponding to edge (6,3), but outside the
intersection of subdomains corresponding to (4,(6,3),y) and (5,(6,3),y), i.e., in D
3 Note that the fact that the program has the same statement in both branches of the if-then-else
statement is merely a convenience which makes it easy to achieve the desired behavior. It is certainly
possible to devise a program without this characteristic which also has the desired behavior.
dua
a (1,2) whole input domain n 2 n
l (2,(3,5),y) even(y
or
or
or
or
or ((y - MAX) and odd(y
or ((y - MAX) and even(y

Table

2: Subdomains of Program shown in Figure 2
program P(input,output);
const
var
begin
-3- repeat if odd(y+x)
-4- then y := y +1
-5- else y := y +1;
-6- until (y ?= MAX);
end.

Figure

2: Program for which M 1
MAX otherwise
The subdomains for the all-edges criterion are shown in the first eight rows of Table 2,
while those for the all-p-uses criterion are shown in the last ten rows. Thus,
Note that this last inequality holds since MAX - 3 by assumption.We next investigate the relationship between covering and measure M 2 .
Theorem 7 There exists a program P, specification S, and criteria C 1 and C 2 such that

Figure

3: Program illustrating M 2 (all-uses;
Proof:
By Corollary 2, it suffices to exhibit a program P and specification S for which
whose flow graph is shown
in

Figure

3. Assume that the input domain is fxj0 - x ! 200g, that c is a constant, and
that the specification S is such that the set of failure-causing inputs is f0; 197; 198; 199g.
The subdomains arising from the all-edges and all-uses criteria and the corresponding
values of m and d are as shown in Table 3. Notice that each criterion induces nine subdomains
for this program, and in each case two of the subdomains contain no failure-causing
inputs.
Since
and
dua

Table

3: Subdomains of Program shown in Figure 3
The following corollary follows from the fact that the number of all-edges subdomains
is equal to the number of all-uses subdomains in the program in Figure 3.
Corollary 3 There exists a program P, specification S, and criteria C 1 and C 2 such
that
3.3 The partitions relation
partitions C 2 for (P,S) if for every subdomain
there is a non-empty collection fD of pairwise disjoint sub-domains
belonging to SDC1 (P; S) such that universally partitions
for every program/specification pair (P,S), C 1 partitions C 2 for (P,S). Note that the
term partition is used here in the strict mathematical sense.
Observation 3 For each program P and specification S, the partitions relation is reflexive
and transitive. If C 1 partitions C 2 for (P,S) then C 1 covers C 2 for (P,S). If
The next example illustrates the distinction between the covers and partitions relations

Example 3:
Consider again the program whose flow graph is shown in Figure 2. The executable
edges and executable definition-p-use associations and the corresponding subdomains
are shown in Table 2.
Recall that the all-p-uses criterion universally covers the all-edges criterion. To see
that all-p-uses does not partition all-edges for this program, consider edge (6;
main g). The only elements of SD all\Gammap\Gammauses that are contained in D g are Dm=D n and
since all the other subdomains contain inputs in which y - MAX \Gamma 1. Since
D n and D o have a non-empty intersection, and neither is equal to D g , all-p-uses does not
partition all-edges for this program.
The executable definition-c-use associations for this program are shown in Table 4.
Note that for each definition-c-use association except (1,2,input), there is a definition-p-
use association with the same subdomain. Consequently, the above argument also shows
that for this program all-uses does not partition all-edges since the set of definition-use
associations for the all-uses criterion is simply the union of the sets of associations for
all-p-uses and all-c-uses. 2
Next, we examine the relationship between partitioning and fault exposing ability, as
assessed by the measures
id def-c-use assoc. equiv. def-p-use assoc.
x (4,7),y) (4,(6,7),y) [q]
y (5,7,y) (5,(6,7),y) [r]

Table

4: Definition-c-use associations of Program shown in Figure 2
Theorem 8 If C 1 partitions C 2 for program P and specification S then M 1
Proof:
be disjoint subdomains belonging to SDC1
such that
each
, so
, and therefore M 1
Theorem 9 There exists a program P, specification S, and criteria C 1 and C 2 such that
Proof:
Consider again the program and specification in the proof of Theorem 7, for which
was shown to be less than M 2 (all-edges; All-uses partitions all-
edges for this program, since the only element of SD all-edges that does not belong to
SD all-uses is fxj0 - x ! 200g, which is equal to a union of disjoint elements of SD all\Gammauses ,
Corollary 4 There exists a program P, specification S, and criteria C 1 and C 2 such that
3.4 The properly covers relation
We have seen that the fact that C 1 covers C 2 does not guarantee that C 1 is better at
detecting faults according to M 2 . However, when an additional constraint on the nature
of the covering is added, the situation improves.
m g, and let SDC2
g. C 1
properly covers C 2 for (P,S) if there is a multi-set
such that M ' SDC1 (P; S) and
n;kn
Note that the number of occurrences of any subdomain D 1
i;j in the above expression is
less than or equal to the number of occurrences of that subdomain in the multi-set SDC1 .
universally properly covers C 2 if for every program P and specification S, C 1 properly
covers C 2 for (P,S).
Observation 4 The properly covers relation is reflexive and transitive. If C 1 properly
covers C 2 for (P,S) then C 1 covers C 2 for (P,S). If SDC2
properly covers C 2 for (P,S). If the elements of SDC2 (P; S) are disjoint (i.e., if C 2 induces
a true partition of the input domain), then C 1 covers C 2 if and only if C 1 properly covers
The next example illustrates the distinction between the covers and properly covers
relations.
Example 4:
Consider a program P with integer input domain fxj0 - x - 3g, and criteria C 1 and C 2
such that
3g. Then D
so C 1 covers (in fact partitions) C 2 . However C 1 does not properly cover C 2 because the
subdomain D b is needed in the coverings of both D d and D e , but only occurs once in the
multi-set SDC1 .
On the other hand consider criterion C 3 where g. C 3 does
properly cover C 2 ; it is legitimate to use D b twice in the covering, since it occurs twice in
SDC3 . Note that such duplication of subdomains frequently occurs in real subdomain-
based criteria; for example, in Table 2, D
Also consider C 4 with subdomains D
Then C 4 properly covers C 2 because D
subdomain is contained in the intersection of C 2 subdomains, there is no danger that one
of them will need to be used more than once in covering all the C 2 subdomains. 2
Example 5:
The next example also illustrates the the properly covers relation. We show that for the
program P in Figure 2, all-uses properly covers all-edges, but all-p-uses does not properly
cover all-edges.
Consider the subdomains arising from the edges and definition-p-use associations of
shown in Table 2 and the definition-c-use associations shown in Table 4. Recall that
all-c-uses . Note that
Since the multi-set
this is a proper covering. On the other hand, when the subdomains arising just from
the all-p-uses criterion are used to cover the all-edges subdomains, it is necessary to
use some subdomains more often than they occur in the multi-set SD all-p-uses
Consequently, all-p-uses does not properly cover all-edges for P and S. 2
The next three theorems show that if C 1 properly covers C 2 , then C 1 is guaranteed
to be better according to M 2 , but not necessarily according to M 1 or M 3 .
Theorem There exists a program P, specification S, and criteria C 1 and C 2 such
that C 1 properly covers C 2 for P and S, but M 1
Proof:
Consider again the program P and specification S in Figure 2. As shown in Example 5,
all-uses properly covers all-edges for P and S. Since for this program M 1 (all-p-uses;
shows that M 1 (all-edges;
On the other hand, the fact that C 1 properly covers C 2 does guarantee that it is
better according to M 2 .
Theorem 11 If C 1 properly covers C 2 for program P and specification S, then M 2 (C
In fact, given program P, specification S, and criteria C 1 and C 2 such that C 1 covers C 2 for P
and S, one can always manufacture a criterion C 0such that C 0properly covers C 2 for P and S, and
simply adding duplicates of certain C 1 subdomains to SDC1 (P; S).
The following lemma is proved in the Appendix:
Y
We now prove Theorem 11.
Proof:
Assume C 1 properly covers C 2 for program P and specification S. Let SDC2
m g, and let
be a multi-set such that M ' SDC1 (P; S) and
n;kn
Then
Y
Line (2) follows from Lemma 1, and line (3) holds because no D 1
i;j occurs more times in
the product in line (2) than in the product in line (3). Consequently, M 2 (C
Theorem 12 There exists a program P, specification S, and criteria C 1 and C 2 such that
Proof:
3g. As shown in Example 4, (where C 1 was
called properly covers (in fact properly partitions) C 2 . Let P be a program with
an integer input domain fxj0 - x - 3g that is correct with respect to its specification
for every input except
and
so
3.5 The properly partitions relation
g, and let SDC2
g. C 1
properly partitions C 2 for (P,S) if there is a multi-set
such that M ' SDC1
n;kn
and for each i, the collection fD 1
g is pairwise disjoint. C 1 universally properly
partitions C 2 if for every program P and specification S, C 1 properly partitions C 2 for
(P,S).
Observation 5 The properly partitions relation is reflexive and transitive. If C 1 properly
partitions C 2 for (P,S) then C 1 partitions C 2 for (P,S) and C 1 properly covers C 2 for
(P,S). If SDC2 properly partitions C 2 for (P,S). If the
elements of SDC2 (P; S) are pairwise disjoint (i.e., if C 2 induces a true partition of the
input domain) then C 1 partitions C 2 if and only if C 1 properly partitions C 2 .
Theorem 13 If C 1 properly partitions C 2 for program P and specification S then M 1
Proof:
If C 1 properly partitions C 2 for (P,S) then C 1 partitions C 2 for (P,S), so the result follows
from Theorem 8. 2
Theorem 14 If C 1 properly partitions C 2 for program P and specification S then
Proof:
If C 1 properly partitions C 2 for (P,S) then C 1 properly covers C 2 for (P,S), so the result
follows from Theorem 11. 2
Theorem 15 There exists a program P, specification S, and criteria C 1 and C 2 such that
Proof:
In the proof of Theorem 12, C 1 properly partitions C 2 . 2
In this paper, we have defined several relationships between software testing criteria, each
induced by a relation between the corresponding multi-sets of subdomains. We have also
investigated whether for each of these relations R,
at detecting faults than C 2 , according to various measures. Each of our three measures
of fault-detecting ability is related to the probability that a test suite selected according
to a particular strategy will detect a fault.
The first relation examined was the narrows relation, which was shown to be closely
related to a commonly used means of comparing criteria called subsumption. We showed
that the fact that criterion C 1 narrows criterion C 2 does not guarantee that C 1 is better
at detecting faults than C 2 according to any of the measures. The next relation examined
was the covers relation, which strengthens the narrows relation in a natural way. Some
well known pairs of criteria, such as all-uses and all-edges are related to one another
according to this relation. We also showed that the fact that criterion C 1 covers criterion
does not guarantee that C 1 is better at detecting faults than C 2 according to any
of the measures. The partitions relation further strengthens the covers relation. While
the fact that C 1 partitions C 2 does guarantee that C 1 is better according to one of the
does not guarantee that C 1 is better according to the other measures.
The last two relations between criteria, the properly covers and properly partitions
relations were designed to overcome some of the deficiencies of the covers and partitions
relations. We proved that the fact that C 1 properly covers C 2 does guarantee that C 1 is
better than C 2 according to measure M 2 , and that the fact that C 1 properly partitions
guarantees that C 1 is better than C 2 according to measures M 1 and M 2 .
Since for most criteria of interest the universally narrows relation is equivalent to the
subsumes relation, one could interpret our results as saying that subsumption is a poor
basis for comparing criteria. However, it is important to note that the results here are
worst case results in the sense that we consider only whether or not the fact that one
criterion subsumes another guarantees improved fault-detecting ability. The question
of what C 1 subsuming (or narrowing, covering, or partitioning) C 2 tells us about their
relative ability to detect faults in "typical" programs remains open.
We have recently shown that the all-p-uses and all-uses criteria do properly cover a
variant of branch testing known as decision coverage and investigated the relationships
among several other subdomain-based criteria, including other data flow testing criteria,
mutation-testing, and multiple-condition coverage [5]. Other directions for future analytical
research include finding conditions on programs that guarantee that C 1 properly
covers C 2 for various well-known criteria C 1 and C 2 ; finding conditions under which C 1
is guaranteed to be better than C 2 according to M 3 , and finding weaker conditions that
guarantee that C 1 is better than C 2 according to M 2 . Our results also suggest several
more pragmatic research problems, including the design of new criteria that are guaranteed
to properly cover commonly used criteria such as all-edges, and the design of test
data selection tools that approximate the selection strategies upon which our results are
based.

Acknowledgments

Some of the results in this paper appeared in the Proceedings of the ACM SIGSOFT '91
Conference on Software for Critical Systems [4].



--R

An evaluation of random testing.
An experimental comparison of the effectiveness of the all-uses and all-edges adequacy criteria
An applicable family of data flow testing criteria.
Assessing the fault-detecting ability of testing methods
Analytical comparison of several testing strategies.
A mathematical framework for the investigation of testing.
Partition testing does not inspire confidence.
A data flow analysis approach to program testing.
Some observations on partition testing.
A data flow oriented program testing strategy.
On required element testing.
Data flow analyisis techniques for program test data selection.
Selecting software test data using data flow information.
Analyzing partition testing strategies.
Comparison of program testing strate- gies
--TR
Selecting software test data using data flow information
An Applicable Family of Data Flow Testing Criteria
Some observations on partition testing
Partition Testing Does Not Inspire Confidence (Program Testing)
Analyzing Partition Testing Strategies
Comparison of program testing strategies
An experimental comparison of the effectiveness of the all-uses and all-edges adequacy criteria
Assessing the fault-detecting ability of testing methods
Data flow analysis techniques for test data selection

--CTR
Dick Hamlet, What can we learn by testing a program?, ACM SIGSOFT Software Engineering Notes, v.23 n.2, p.50-52, March 1998
Antonia Bertolino , Lorenzo Strigini, Using testability measures for dependability assessment, Proceedings of the 17th international conference on Software engineering, p.61-70, April 24-28, 1995, Seattle, Washington, United States
Weyuker , T. Goradia , A. Singh, Automatically Generating Test Data from a Boolean Specification, IEEE Transactions on Software Engineering, v.20 n.5, p.353-363, May 1994
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
R. K. Singh , Pravin Chandra , Yogesh Singh, An evaluation of Boolean expression testing techniques, ACM SIGSOFT Software Engineering Notes, v.31 n.5, September 2006
W. Eric Wong , Yu Qi , Kendra Cooper, Source code-based software risk assessing, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
Silvia Regina Vergilio , Jos Carlos Maldonado , Mario Jino, Constraint Based Criteria: An Approach for Test Case Selection in the Structural Testing, Journal of Electronic Testing: Theory and Applications, v.17 n.2, p.175-183, April 2001
Sandro Morasca , Stefano Serra-Capizzano, On the analytical comparison of testing techniques, ACM SIGSOFT Software Engineering Notes, v.29 n.4, July 2004
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
W. E. Howden , Yudong Huang, Software trustability analysis, ACM Transactions on Software Engineering and Methodology (TOSEM), v.4 n.1, p.36-64, Jan. 1995
Phyllis G. Frankl , Elaine J. Weyuker, An analytical comparison of the fault-detecting ability of data flow testing techniques, Proceedings of the 15th international conference on Software Engineering, p.415-424, May 17-21, 1993, Baltimore, Maryland, United States
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
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
Dick Hamlet, Foundations of software testing: dependability theory, ACM SIGSOFT Software Engineering Notes, v.19 n.5, p.128-139, Dec. 1994
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
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
J. Weyuker, More Experience with Data Flow Testing, IEEE Transactions on Software Engineering, v.19 n.9, p.912-919, September 1993
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 , 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
Christoph C. Michael , Jeffrey Voas, The ability of directed tests to predict software quality, Annals of Software Engineering, 4, p.31-64, 1997
Chi Keen Low , T. Y. Chen , Ralph Rnnquist, Automated Test Case Generation for BDI Agents, Autonomous Agents and Multi-Agent Systems, v.2 n.4, p.311-332, November 1999
Silvia Regina Vergilio , Jos Carlos Maldonado , Mario Jino , Inali Wisniewski Soares, Constraint based structural testing criteria, Journal of Systems and Software, v.79 n.6, p.756-771, June 2006
Philip J. Boland , Harshinder Singh , Bojan Cukic, Comparing Partition and Random Testing via Majorization and Schur Functions, IEEE Transactions on Software Engineering, v.29 n.1, p.88-94, January
P. G. Frankl , E. J. Weyuker, Provable Improvements on Branch Testing, IEEE Transactions on Software Engineering, v.19 n.10, p.962-975, October 1993
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
W. Eric Wong , Tatiana Sugeta , J. Jenny Li , Jos C. Maldonado, Coverage testing software architectural design in SDL, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.42 n.3, p.359-374, 21 June
Prem Devanbu , Stuart G. Stubblebine, Cryptographic verification of test coverage claims, ACM SIGSOFT Software Engineering Notes, v.22 n.6, p.395-413, Nov. 1997
Mrcio Eduardo Delamaro , Jos Carlos Maldonado , Alberto Pasquini , Aditya P. Mathur, Interface Mutation Test Adequacy Criterion: An Empirical Evaluation, Empirical Software Engineering, v.6 n.2, p.111-142, June 2001
Marcio E. Delamaro , Jos C. Maldonado , Aditya P. Mathur, Interface Mutation: An Approach for Integration Testing, IEEE Transactions on Software Engineering, v.27 n.3, p.228-247, March 2001
C. C. Michael , G. McGraw , M. A. Schatz, Generating Software Test Data by Evolution, IEEE Transactions on Software Engineering, v.27 n.12, p.1085-1110, December 2001
P. G. Frankl , S. N. Weiss, An Experimental Comparison of the Effectiveness of Branch Testing and Data Flow Testing, IEEE Transactions on Software Engineering, v.19 n.8, p.774-787, August 1993
Premkumar Thomas Devanbu , Stuart G. Stubblebine, Cryptographic Verification of Test Coverage Claims, IEEE Transactions on Software Engineering, v.26 n.2, p.178-192, February 2000
Michael Ellims , James Bridges , Darrel C. Ince, The Economics of Unit Testing, Empirical Software Engineering, v.11 n.1, p.5-31, March     2006
Hong Zhu , Lingzi Jin , Dan Diaper , Ganghong Bai, Software requirements validation via task analysis, Journal of Systems and Software, v.61 n.2, p.145-169, March 2002
Matthew B. Dwyer , John Hatcliff , Robby Robby , Corina S. Pasareanu , Willem Visser, Formal Software Analysis Emerging Trends in Software Model Checking, 2007 Future of Software Engineering, p.120-136, 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;software testing criteria;program testing;subdomains;system recovery;multisets;formal analysis;subsumption relation;probabilistic measures