Short Answer and Discussion (400 words total)

Software Unit Test Coverage and Adequacy HONG ZHU

Nanjing University

PATRICK A. V. HALL AND JOHN H. R. MAY

The Open University, Milton Keynes, UK

Objective measurement of test quality is one of the key issues in software testing. It has been a major research focus for the last two decades. Many test criteria have been proposed and studied for this purpose. Various kinds of rationales have been presented in support of one criterion or another. We survey the research work in this area. The notion of adequacy criteria is examined together with its role in software dynamic testing. A review of criteria classification is followed by a summary of the methods for comparison and assessment of criteria.

Categories and Subject Descriptors: D.2.5 [Software Engineering]: Testing and Debugging

General Terms: Measurement, Performance, Reliability, Verification

Additional Key Words and Phrases: Comparing testing effectiveness, fault- detection, software unit test, test adequacy criteria, test coverage, testing methods

1. INTRODUCTION

In 1972, Dijkstra claimed that “program testing can be used to show the presence of bugs, but never their absence” to per- suade us that a testing approach is not acceptable [Dijkstra 1972]. However, the last two decades have seen rapid growth of research in software testing as well as intensive practice and experiments. It has been developed into a validation and verification technique indispensable to software engineering discipline. Then, where are we today? What can we claim about software testing?

In the mid-’70s, in an examination of the capability of testing for demonstrat- ing the absence of errors in a program,

Goodenough and Gerhart [1975, 1977] made an early breakthrough in research on software testing by pointing out that the central question of software testing is “what is a test criterion?”, that is, the criterion that defines what constitutes an adequate test. Since then, test crite- ria have been a major research focus. A great number of such criteria have been proposed and investigated. Consider- able research effort has attempted to provide support for the use of one crite- rion or another. How should we under- stand these different criteria? What are the future directions for the subject?

In contrast to the constant attention given to test adequacy criteria by aca-

Authors’ addresses: H. Zhu, Institute of Computer Software, Nanjing University, Nanjing, 210093, P.R. of China; email: ^[email protected]&; P.A.V. Hall and J.H.R. May, Department of Computing, The Open University, Walton Hall, Milton Keynes, MK76AA, UK. Permission to make digital / hard copy of part or all of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage, the copyright notice, the title of the publication, and its date appear, and notice is given that copying is by permission of the ACM, Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and / or a fee. © 1997 ACM 0360-0300/97/1200–0366 $03.50

ACM Computing Surveys, Vol. 29, No. 4, December 1997

demics, the software industry has been slow to accept test adequacy measure- ment. Few software development stan- dards require or even recommend the use of test adequacy criteria [Wichmann 1993; Wichmann and Cox 1992]. Are test adequacy criteria worth the cost for practical use?

Addressing these questions, we sur- vey research on software test criteria in the past two decades and attempt to put it into a uniform framework.

1.1 The Notion of Test Adequacy

Let us start with some examples. Here we seek to illustrate the basic notions underlying adequacy criteria. Precise definitions will be given later.

—Statement coverage. In software test- ing practice, testers are often re- quired to generate test cases to exe- cute every statement in the program at least once. A test case is an input on which the program under test is executed during testing. A test set is a set of test cases for testing a program. The requirement of executing all the statements in the program under test is an adequacy criterion. A test set that satisfies this requirement is con- sidered to be adequate according to the statement coverage criterion. Sometimes the percentage of executed statements is calculated to indicate how adequately the testing has been performed. The percentage of the statements exercised by testing is a measurement of the adequacy.

—Branch coverage. Similarly, the branch coverage criterion requires that all control transfers in the program un- der test are exercised during testing. The percentage of the control trans- fers executed during testing is a mea- surement of test adequacy.

—Path coverage. The path coverage cri- terion requires that all the execution paths from the program’s entry to its exit are executed during testing.

—Mutation adequacy. Software testing is often aimed at detecting faults in

software. A way to measure how well this objective has been achieved is to plant some artificial faults into the program and check if they are de- tected by the test. A program with a planted fault is called a mutant of the original program. If a mutant and the original program produce different outputs on at least one test case, the fault is detected. In this case, we say that the mutant is dead or killed by the test set. Otherwise, the mutant is still alive. The percentage of dead mu- tants compared to the mutants that are not equivalent to the original pro- gram is an adequacy measurement, called the mutation score or mutation adequacy [Budd et al. 1978; DeMillo et al. 1978; Hamlet 1977].

From Goodenough and Gerhart’s [1975, 1977] point of view, a software test adequacy criterion is a predicate that defines “what properties of a pro- gram must be exercised to constitute a ‘thorough’ test, i.e., one whose success- ful execution implies no errors in a tested program.” To guarantee the cor- rectness of adequately tested programs, they proposed reliability and validity requirements of test criteria. Reliability requires that a test criterion always produce consistent test results; that is, if the program tested successfully on one test set that satisfies the criterion, then the program also tested success- fully on all test sets that satisfies the criterion. Validity requires that the test always produce a meaningful result; that is, for every error in a program, there exists a test set that satisfies the criterion and is capable of revealing the error. But it was soon recognized that there is no computable criterion that satisfies the two requirements, and hence they are not practically applica- ble [Howden 1976]. Moreover, these two requirements are not independent since a criterion is either reliable or valid for any given software [Weyuker and Os- trand 1980]. Since then, the focus of research seems to have shifted from seeking theoretically ideal criteria to

Test Coverage and Adequacy • 367

ACM Computing Surveys, Vol. 29, No. 4, December 1997

the search for practically applicable ap- proximations.

Currently, the software testing litera- ture contains two different, but closely related, notions associated with the term test data adequacy criteria. First, an adequacy criterion is considered to be a stopping rule that determines whether sufficient testing has been done that it can be stopped. For in- stance, when using the statement cover- age criterion, we can stop testing if all the statements of the program have been executed. Generally speaking, since software testing involves the pro- gram under test, the set of test cases, and the specification of the software, an adequacy criterion can be formalized as a function C that takes a program p, a specification s, and a test set t and gives a truth value true or false. Formally, let P be a set of programs, S be a set of specifications, D be the set of inputs of the programs in P, T be the class of test sets, that is, T 5 2D, where 2X denotes the set of subsets of X.

Definition 1.1 (Test Data Adequacy Criteria as Stopping Rules). A test data adequacy criterion C is a function C: P 3 S 3 T 3 {true, false}. C(p, s, t) 5 true means that t is adequate for testing program p against specification s accord- ing to the criterion C, otherwise t is inad- equate.

Second, test data adequacy criteria provide measurements of test quality when a degree of adequacy is associated with each test set so that it is not sim- ply classified as good or bad. In practice, the percentage of code coverage is often used as an adequacy measurement. Thus, an adequacy criterion C can be formally defined to be a function C from a program p, a specification s, and a test set t to a real number r 5 C(p, s, t), the degree of adequacy [Zhu and Hall 1992]. Formally:

Definition 1.2 (Test Data Adequacy Criteria as Measurements). A test data adequacy criterion is a function C, C: P 3 S 3 T 3 [0,1]. C(p, s, t) 5 r means

that the adequacy of testing the pro- gram p by the test set t with respect to the specification s is of degree r accord- ing to the criterion C. The greater the real number r, the more adequate the testing.

These two notions of test data ade- quacy criteria are closely related to one another. A stopping rule is a special case of measurement on the continuum since the actual range of measurement results is the set {0,1}, where 0 means false and 1 means true. On the other hand, given an adequacy measurement M and a degree r of adequacy, one can always construct a stopping rule Mr such that a test set is adequate if and only if the adequacy degree is greater than or equal to r; that is, Mr(p, s, t) 5 true N M(p, s, t) $ r. Since a stopping rule asserts a test set to be either ade- quate or inadequate, it is also called a predicate rule in the literature.

An adequacy criterion is an essential part of any testing method. It plays two fundamental roles. First, an adequacy criterion specifies a particular software testing requirement, and hence deter- mines test cases to satisfy the require- ment. It can be defined in one of the following forms.

(1) It can be an explicit specification for test case selection, such as a set of guidelines for the selection of test cases. Following such rules one can produce a set of test cases, although there may be some form of random selections. Such a rule is usually referred to as a test case selection criterion. Using a test case selection criterion, a testing method may be defined constructively in the form of an algorithm which generates a test set from the software under test and its own specification. This test set is then considered adequate. It should be noticed that for a given test case selection criterion, there may exist a number of test case generation algo- rithms. Such an algorithm may also involve random sampling among many adequate test sets.

368 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

(2) It can also be in the form of specify- ing how to decide whether a given test set is adequate or specifying how to measure the adequacy of a test set. A rule that determines whether a test set is adequate (or more generally, how adequate) is usually referred to as a test data adequacy criterion.

However, the fundamental concept underlying both test case selection cri- teria and test data adequacy criteria is the same, that is, the notion of test adequacy. In many cases they can be easily transformed from one form to an- other. Mathematically speaking, test case selection criteria are generators, that is, functions that produce a class of test sets from the program under test and the specification (see Definition 1.3). Any test set in this class is ade- quate, so that we can use any of them equally.1 Test data adequacy criteria are acceptors that are functions from the program under test, the specifica- tion of the software and the test set to a characteristic number as defined in Def- inition 1.1. Generators and acceptors are mathematically equivalent in the sense of one-one correspondence. Hence, we use “test adequacy criteria” to de- note both of them.

Definition 1.3 (Test Data Adequacy Criteria as Generators [Budd and An- gluin 1982]). A test data adequacy cri- terion C is a function C: P 3 S 3 2T. A test set t [ C(p, s) means that t satis- fies C with respect to p and s, and it is said that t is adequate for (p, s) accord- ing to C.

The second role that an adequacy cri- terion plays is to determine the observa- tions that should be made during the testing process. For example, statement coverage requires that the tester, or the testing system, observe whether each statement is executed during the pro-

cess of software testing. If path cover- age is used, then the observation of whether statements have been executed is insufficient; execution paths should be observed and recorded. However, if mutation score is used, it is unneces- sary to observe whether a statement is executed during testing. Instead, the output of the original program and the output of the mutants need to be re- corded and compared.

Although, given an adequacy crite- rion, different methods could be devel- oped to generate test sets automatically or to select test cases systematically and efficiently, the main features of a testing method are largely determined by the adequacy criterion. For example, as we show later, the adequacy criterion is related to fault-detecting ability, the dependability of the program that passes a successful test and the number of test cases required. Unfortunately, the exact relationship between a partic- ular adequacy criterion and the correct- ness or reliability of the software that passes the test remains unclear.

Due to the central role that adequacy criteria play in software testing, soft- ware testing methods are often com- pared in terms of the underlying ade- quacy criteria. Therefore, subsequently, we use the name of an adequacy crite- rion as a synonym of the corresponding testing method when there is no possi- bility of confusion.

1.2 The Uses of Test Adequacy Criteria

An important issue in the management of software testing is to “ensure that before any testing the objectives of that testing are known and agreed and that the objectives are set in terms that can be measured.” Such objectives “should be quantified, reasonable and achiev- able” [Ould and Unwin 1986]. Almost all test adequacy criteria proposed in the literature explicitly specify particu- lar requirements on software testing. They are objective rules applicable by project managers for this purpose.

For example, branch coverage is a

1 Test data selection criteria as generators should not be confused with test case generation software tools, which may only generate one test set.

Test Coverage and Adequacy • 369

ACM Computing Surveys, Vol. 29, No. 4, December 1997

test requirement that all branches of the program should be exercised. The objective of testing is to satisfy this requirement. The degree to which this objective is achieved can be measured quantitatively by the percentage of branches exercised. The mutation ade- quacy criterion specifies the testing re- quirement that a test set should be able to rule out a particular set of software faults, that is, those represented by mu- tants. Mutation score is another kind of quantitative measurement of test qual- ity.

Test data adequacy criteria are also very helpful tools for software testers. There are two levels of software testing processes. At the lower level, testing is a process where a program is tested by feeding more and more test cases to it. Here, a test adequacy criterion can be used as a stopping rule to decide when this process can stop. Once the mea- surement of test adequacy indicates that the test objectives have been achieved, then no further test case is needed. Otherwise, when the measure- ment of test adequacy shows that a test has not achieved the objectives, more tests must be made. In this case, the adequacy criterion also provides a guideline for the selection of the addi- tional test cases. In this way, adequacy criteria help testers to manage the soft- ware testing process so that software quality is ensured by performing suffi- cient tests. At the same time, the cost of testing is controlled by avoiding redun- dant and unnecessary tests. This role of adequacy criteria has been considered by some computer scientists [Weyuker 1986] to be one of the most important.

At a higher level, the testing proce- dure can be considered as repeated cy- cles of testing, debugging, modifying program code, and then testing again. Ideally, this process should stop only when the software has met the required reliability requirements. Although test data adequacy criteria do not play the role of stopping rules at this level, they make an important contribution to the assessment of software dependability.

Generally speaking, there are two basic aspects of software dependability as- sessment. One is the dependability esti- mation itself, such as a reliability fig- ure. The other is the confidence in estimation, such as the confidence or the accuracy of the reliability estimate. The role of test adequacy here is a con- tributory factor in building confidence in the integrity estimate. Recent re- search has shown some positive results with respect to this role [Tsoukalas 1993].

Although it is common in current soft- ware testing practice that the test pro- cesses at both the higher and lower levels stop when money or time runs out, there is a tendency towards the use of systematic testing methods with the application of test adequacy criteria.

1.3 Categories of Test Data Adequacy Criteria

There are various ways to classify ade- quacy criteria. One of the most common is by the source of information used to specify testing requirements and in the measurement of test adequacy. Hence, an adequacy criterion can be:

—specification-based, which specifies the required testing in terms of iden- tified features of the specification or the requirements of the software, so that a test set is adequate if all the identified features have been fully ex- ercised. In software testing literature it is fairly common that no distinction is made between specification and re- quirements. This tradition is followed in this article also;

—program-based, which specifies test- ing requirements in terms of the pro- gram under test and decides if a test set is adequate according to whether the program has been thoroughly ex- ercised.

It should not be forgotten that for both specification-based and program-based testing, the correctness of program out- puts must be checked against the speci- fication or the requirements. However,

370 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

in both cases, the measurement of test adequacy does not depend on the results of this checking. Also, the definition of specification-based criteria given previ- ously does not presume the existence of a formal specification.

It has been widely acknowledged that software testing should use information from both specification and program. Combining these two approaches, we have:

—combined specification- and program- based criteria, which use the ideas of both program-based and specification- based criteria.

There are also test adequacy criteria that specify testing requirements with- out employing any internal information from the specification or the program. For example, test adequacy can be mea- sured according to the prospective us- age of the software by considering whether the test cases cover the data that are most likely to be frequently used as input in the operation of the software. Although few criteria are ex- plicitly proposed in such a way, select- ing test cases according to the usage of the software is the idea underlying ran- dom testing, or statistical testing. In random testing, test cases are sampled at random according to a probability distribution over the input space. Such a distribution can be the one represent- ing the operation of the software, and the random testing is called representa- tive. It can also be any probability dis- tribution, such as a uniform distribu- tion, and the random testing is called nonrepresentative. Generally speaking, if a criterion employs only the “inter- face” information—the type and valid range for the software input—it can be called an interface-based criterion:

—interface-based criteria, which specify testing requirements only in terms of the type and range of software input without reference to any internal fea- tures of the specification or the pro- gram.

In the software testing literature, peo- ple often talk about white-box testing and black-box testing. Black-box testing treats the program under test as a “black box.” No knowledge about the implementation is assumed. In white- box testing, the tester has access to the details of the program under test and performs the testing according to such details. Therefore, specification-based criteria and interface-based criteria be- long to black-box testing. Program- based criteria and combined specifica- tion and program-based criteria belong to white-box testing.

Another classification of test ade- quacy criteria is by the underlying test- ing approach. There are three basic ap- proaches to software testing:

(1) structural testing: specifies testing requirements in terms of the cover- age of a particular set of elements in the structure of the program or the specification;

(2) fault-based testing: focuses on de- tecting faults (i.e., defects) in the software. An adequacy criterion of this approach is some measurement of the fault detecting ability of test sets.2

(3) error-based testing: requires test cases to check the program on cer- tain error-prone points according to our knowledge about how programs typically depart from their specifica- tions.

The source of information used in the adequacy measurement and the under- lying approach to testing can be consid- ered as two dimensions of the space of software test adequacy criteria. A soft- ware test adequacy criterion can be classified by these two aspects. The re- view of adequacy criteria is organized according to the structure of this space.

2 We use the word fault to denote defects in soft- ware and the word error to denote defects in the outputs produced by a program. An execution that produces an error is called a failure.

Test Coverage and Adequacy • 371

ACM Computing Surveys, Vol. 29, No. 4, December 1997

1.4 Organization of the Article

The remainder of the article consists of two main parts. The first part surveys various types of test data adequacy cri- teria proposed in the literature. It in- cludes three sections devoted to struc- tural testing, fault-based testing, and error-based testing. Each section con- sists of several subsections covering the principles of the testing method and their application to program-based and specification-based test criteria. The second part is devoted to the rationale presented in the literature in support of the various criteria. It has two sections. Section 5 discusses the methods of com- paring adequacy criteria and surveys the research results in the literature. Section 6 discusses the axiomatic study and assessment of adequacy criteria. Fi- nally, Section 7 concludes the paper.

2. STRUCTURAL TESTING

This section is devoted to adequacy cri- teria for structural testing. It consists of two subsections, one for program-based criteria and the other for specification- based criteria.

2.1 Program-Based Structural Testing

There are two main groups of program- based structural test adequacy criteria: control-flow criteria and data-flow crite- ria. These two types of adequacy crite- ria are combined and extended to give dependence coverage criteria. Most ade- quacy criteria of these two groups are based on the flow-graph model of pro- gram structure. However, a few control- flow criteria define test requirements in terms of program text rather than using an abstract model of software structure.

2.1.1 Control Flow Adequacy Crite- ria. Before we formally define various control-flow-based adequacy criteria, we first give an introduction to the flow graph model of program structure.

A. The flow graph model of program structure. The control flow graph stems from compiler work and has long

been used as a model of program struc- ture. It is widely used in static analysis of software [Fenton et al. 1985; Ko- saraju 1974; McCabe 1976; Paige 1975]. It has also been used to define and study program-based structural test ad- equacy criteria [White 1981]. In this section we give a brief introduction to the flow-graph model of program struc- ture. Although we use graph-theory ter- minology in the following discussion, readers are required to have only a pre- liminary knowledge of graph theory. To help understand the terminology and to avoid confusion, a glossary is provided in the Appendix.

A flow graph is a directed graph that consists of a set N of nodes and a set E # N 3 N of directed edges between nodes. Each node represents a linear sequence of computations. Each edge representing transfer of control is an ordered pair ^n1, n2& of nodes, and is associated with a predicate that repre- sents the condition of control transfer from node n1 to node n2. In a flow graph, there is a begin node and an end node where the computation starts and finishes, respectively. The begin node has no inward edges and the end node has no outward edges. Every node in a flow graph must be on a path from the begin node to the end node. Figure 1 is an example of flow graph.

Example 2.1 The following program computes the greatest common divisor of two natural numbers by Euclid’s al- gorithm. Figure 1 is the corresponding flow graph.

Begin input (x, y); while (x . 0 and y . 0) do

if (x . y) then x: 5 x 2 y else y: 5 y 2 x

endif endwhile; output (x 1 y);

end

It should be noted that in the litera- ture there are a number of conventions of flow-graph models with subtle differ-

372 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

ences, such as whether a node is al- lowed to be associated with an empty sequence of statements, the number of outward edges allowed for a node, and the number of end nodes allowed in a flow graph, and the like. Although most adequacy criteria can be defined inde- pendently of such conventions, using different ones may result in different measures of test adequacy. Moreover, testing tools may be sensitive to such conventions. In this article no restric- tions on the conventions are made.

For programs written in a procedural programming language, flow-graph models can be generated automatically. Figure 2 gives the correspondences be- tween some structured statements and their flow-graph structures. Using these rules, a flow graph, shown in Figure 3, can be derived from the program given in Example 2.1. Generally, to construct a flow graph for a given program, the program code is decomposed into a set of disjoint blocks of linear sequences of statements. A block has the property that whenever the first statement of the block is executed, the other statements are executed in the given order. Fur- thermore, the first statement of the block is the only statement that may be executed directly after the execution of a statement in another block. Each block corresponds to a node in the flow graph. A control transfer from one block

to another is represented by a directed edge between the nodes such that the condition of the control transfer is asso- ciated with it.

B. Control-flow adequacy criteria. Now, given a flow-graph model of a pro- gram and a set of test cases, how do we measure the adequacy of testing for the program on the test set? First of all, recall that the execution of the program on an input datum is modeled as a traverse in the flow graph. Every execu- tion corresponds to a path in the flow graph from the begin node to the end node. Such a path is called a complete computation path, or simply a computa- tion path or an execution path in soft- ware testing literature.

A very basic requirement of adequate testing is that all the statements in the program are covered by test executions. This is usually called statement cover- age [Hetzel 1984]. But full statement coverage cannot always be achieved be- cause of the possible existence of infea- sible statements, that is, dead code. Whether a piece of code is dead code is undecidable [Weyuker 1979a; Weyuker 1979b; White 1981]. Because state- ments correspond to nodes in flow- graph models, this criterion can be de- fined in terms of flow graphs, as follows.

Definition 2.1 (Statement Coverage Criterion). A set P of execution paths

Figure 1. Flow graph for program in Example 2.1.

Test Coverage and Adequacy • 373

ACM Computing Surveys, Vol. 29, No. 4, December 1997

satisfies the statement coverage crite- rion if and only if for all nodes n in the flow graph, there is at least one path p in P such that node n is on the path p.

Notice that statement coverage is so weak that even some control transfers

may be missed from an adequate test. Hence, we have a slightly stronger re- quirement of adequate test, called branch coverage [Hetzel 1984], that all control transfers must be checked. Since control transfers correspond to edges in flow graphs, the branch coverage crite- rion can be defined as the coverage of all edges in the flow graph.

Definition 2.2 (Branch Coverage Crite- rion). A set P of execution paths satis- fies the branch coverage criterion if and only if for all edges e in the flow graph, there is at least one path p in P such that p contains the edge e.

Branch coverage is stronger than statement coverage because if all edges in a flow graph are covered, all nodes are necessarily covered. Therefore, a test set that satisfies the branch cover- age criterion must also satisfy state- ment coverage. Such a relationship be- tween adequacy criteria is called the subsumes relation. It is of interest in the comparison of software test ade-

Figure 2. Example flow graphs for structured statements.

Figure 3. Flow graph for Example 2.1.

374 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

quacy criteria (see details in Section 5.1.3).

However, even if all branches are ex- ercised, this does not mean that all com- binations of control transfers are checked. The requirement of checking all combinations of branches is usually called path coverage or path testing, which can be defined as follows.

Definition 2.3 (Path Coverage Crite- rion). A set P of execution paths satis- fies the path coverage criterion if and only if P contains all execution paths from the begin node to the end node in the flow graph.

Although the path coverage criterion still cannot guarantee the correctness of a tested program, it is too strong to be practically useful for most programs, because there can be an infinite number of different paths in a program with loops. In such a case, an infinite set of test data must be executed for adequate testing. This means that the testing cannot finish in a finite period of time. But, in practice, software testing must be fulfilled within a limited fixed period of time. Therefore, a test set must be finite. The requirement that an ade- quacy criterion can always be satisfied by a finite test set is called finite appli- cability [Zhu and Hall 1993] (see Sec- tion 6).

The statement coverage criterion and branch coverage criterion are not fi- nitely applicable either, because they require testing to cover infeasible ele- ments. For instance, statement cover- age requires that all the statements in a program are executed. However, a pro- gram may have infeasible statements, that is, dead code, so that no input data can cause their execution. Therefore, in such cases, there is no adequate test set that can satisfy statement coverage. Similarly, branch coverage is not fi- nitely applicable because a program may contain infeasible branches. How- ever, for statement coverage and also branch coverage, we can define a fi- nitely applicable version of the criterion by requiring testing only to cover the

feasible elements. Most program-based adequacy criteria in the literature are not finitely applicable, but finitely ap- plicable versions can often be obtained by redefinition in this way. Subse- quently, such a version is called the feasible version of the adequacy crite- rion. It should be noted, first, that al- though we can often obtain finite appli- cability by using the feasible version, this may cause the undecidability prob- lem; that is, we may not be able to decide whether a test set satisfies a given adequacy criterion. For example, whether a statement in a program is feasible is undecidable [Weyuker 1979a; Weyuker 1979b; White 1991]. There- fore, when a test set does not cover all the statements in a program, we may not be able to decide whether a state- ment not covered by the test data is dead code. Hence, we may not be able to decide if the test set satisfies the feasi- ble version of statement coverage. Sec- ond, for some adequacy criteria, such as path coverage, we cannot obtain finite applicability by such a redefinition.

Recall that the rationale for path cov- erage is that there is no path that does not need to be checked by testing, while finite applicability forces us to select a finite subset of paths. Thus, research into flow-graph-based adequacy criteria has focused on the selection of the most important subsets of paths. Probably the most straightforward solution to the conflict is to select paths that contain no redundant information. Hence, two no- tions from graph theory can be used. First, a path that has no repeated occur- rence of any edge is called a simple path in graph theory. Second, a path that has no repeated occurrences of any node is called an elementary path. Thus, it is possible to define simple path coverage and elementary path coverage criteria, which require that adequate test sets should cover all simple paths and ele- mentary paths, respectively.

These two criteria are typical ones that select finite subsets of paths by specifying restrictions on the complexity of the individual paths. Another exam-

Test Coverage and Adequacy • 375

ACM Computing Surveys, Vol. 29, No. 4, December 1997

ple of this type is the length-n path coverage criterion, which requires cover- age of all subpaths of length less than or equal to n [Gourlay 1983]. A more complicated example of the type is Paige’s level-i path coverage criterion [Paige 1978; Paige 1975]. Informally, the criterion starts with testing all ele- mentary paths from the begin node to the end node. Then, if there is an ele- mentary subpath or cycle that has not been exercised, the subpath is required to be checked at next level. This process is repeated until all nodes and edges are covered by testing. Obviously, a test set that satisfies the level-i path coverage criterion must also satisfy the elemen- tary path coverage criterion, because elementary paths are level-0 paths.

A set of control-flow adequacy criteria that are concerned with testing loops is loop count criteria, which date back to the mid-1970s [Bently et al. 1993]. For any given natural number K, the loop count-K criterion requires that every loop in the program under test should be executed zero times, once, twice, and so on, up to K times [Howden 1975]. Another control-flow criterion con- cerned with testing loops is the cycle combination criterion, which requires that an adequate test set should cover all execution paths that do not contain a cycle more than once.

An alternative approach to defining control-flow adequacy criteria is to spec- ify restrictions on the redundancy among the paths. McCabe’s cyclomatic measurement is such an example [Mc- Cabe 1976; McCabe 1983; McCabe and Schulmeyer 1985]. It is based on the theorem of graph theory that for any flow graph there is a set of execution paths such that every execution path can be expressed as a linear combina- tion of them. A set of paths is indepen- dent if none of them is a linear combina- tion of the others. According to McCabe, a path should be tested if it is indepen- dent of the paths that have been tested. On the other hand, if a path is a linear combination of tested paths, it can be considered redundant. According to

graph theory, the maximal size of a set of independent paths is unique for any given graph and is called the cyclomatic number, and can be easily calculated by the following formula.

v~G! 5 e 2 n 1 p,

where v(G) denotes the cyclomatic num- ber of the graph G, n is the number of vertices in G, e is the number of edges, and p is the number of strongly con- nected components.3 The adequacy cri- terion is then defined as follows.

Definition 2.4 (Cyclomatic-Number Criterion). A set P of execution paths satisfies the cyclomatic number crite- rion if and only if P contains at least one set of v independent paths, where v 5 e 2 n 1 p is the cyclomatic number of the flow graph.

McCabe also gave an algorithm to generate a set of independent paths from any given flow graph [McCabe 1976]. Paige [1978] has shown that the level-i path coverage criterion subsumes McCabe’s cyclomatic number criterion.

The preceding control-flow test ade- quacy criteria are all defined in terms of flow-graph models of program structure except loop count criteria, which are defined in terms of program text. A number of other test adequacy criteria are based on the text of program. One of the most popular criteria in software testing practice is the so-called multiple condition coverage discussed in Myers’ [1979] classic book which has proved popular in commercial software testing practice. The criterion focuses on the conditions of control transfers, such as the condition in an IF-statement or a WHILE-LOOP statement. A test set is said of satisfying the decision coverage criterion if for every condition there is at least one test case such that the condition has value true when evalu-

3 A graph is strongly connected if, for any two nodes a and b, there exists a path from a to b and a path from b to a. Strongly connected compo- nents are maximal strongly connected subgraphs.

376 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

ated, and there is also at least one test case such that the condition has value false. In a high-level programming lan- guage, a condition can be a Boolean expression consisting of several atomic predicates combined by logic connec- tives like and, or, and not. A test set satisfies the condition coverage crite- rion if for every atomic predicate there is at least one test case such that the predicate has value true when evalu- ated, and there is also at least one test case such that the predicate has value false. Although the result value of an evaluation of a Boolean expression can only be one of two possibilities, true or false, the result may be due to different combinations of the truth values of the atomic predicates. The multiple condi- tion coverage criterion requires that a test set should cover all possible combi- nations of the truth values of atomic predicates in every condition. This crite- rion is sometimes also called extended branch coverage in the literature. For- mally:

Definition 2.5 (Multiple Condition Coverage). A test set T is said to be adequate according to the multiple-con- dition-coverage criterion if, for every condition C, which consists of atomic predicates (p1, p2, . . . , pn), and all the possible combinations (b1, b2, . . . , bn) of their truth values, there is at least one test case in T such that the value of pi equals bi, i 5 1, 2, . . . , n.

Woodward et al. [1980] proposed and studied a hierarchy of program-text- based test data adequacy criteria based on a class of program units called linear code sequence and jump (LCSAJ). These criteria are usually referred to as test effectiveness metrics in the literature. An LCSAJ consists of a body of code through which the flow of control may proceed sequentially and which is ter- minated by a jump in the control flow. The hierarchy TERi, i 5 1, 2, . . . , n, . . . of criteria starts with statement coverage as the lowest level, followed by branch coverage as the next lowest level. They are denoted by TER1 and

TER2, respectively, where TER repre- sents test effectiveness ratio. The cover- age of LCSAJ is the third level, which is defined as TER3. The hierarchy is then extended to the coverage of program paths containing a number of LCSAJs.

Definition 2.6 (TER3: LCSAJ Cover- age)

TER3 5

number of LCSAJs exercised at least once

total number of LCSAJs.

Generally speaking, an advantage of text-based adequacy criteria is that test adequacy can be easily calculated from the part of program text executed dur- ing testing. However, their definitions may be sensitive to language details. For programs written in a structured programming language, the application of TERn for n greater than or equal to 3 requires analysis and reformatting of the program structure. In such cases, the connection between program text and its test adequacy becomes less straightforward. In fact, it is observed in software testing practice that a small modification to the program may result in a considerably different set of linear sequence code and jumps.

It should be noted that none of the adequacy criteria discussed in this sec- tion are applicable due to the possible existence of infeasible elements in a program, such as infeasible statements, infeasible branches, infeasible combina- tions of conditions, and the like. These criteria, except path coverage, can be redefined to obtain finite applicability by only requiring the coverage of feasi- ble elements.

2.1.2 Data-Flow-Based Test Data Ad- equacy Criteria. In the previous sec- tion, we have seen how control-flow in- formation in the program under test is used to specify testing requirements. In this section, data-flow information is taken into account in the definition of testing requirements. We first introduce the way that data-flow information is

Test Coverage and Adequacy • 377

ACM Computing Surveys, Vol. 29, No. 4, December 1997

added into the flow-graph models of pro- gram structures. Then, three basic groups of data-flow adequacy criteria are reviewed. Finally, their limitations and extensions are discussed.

A. Data-flow information in flow graph. Data-flow analysis of test ade- quacy is concerned with the coverage of flow-graph paths that are significant for the data flow in the program. Therefore, data-flow information is introduced into the flow-graph models of program struc- tures.

Data-flow testing methods are based on the investigation of the ways in which values are associated with vari- ables and how these associations can effect the execution of the program. This analysis focuses on the occurrences of variables within the program. Each variable occurrence is classified as ei- ther a definition occurrence or a use occurrence. A definition occurrence of a variable is where a value is bound to the variable. A use occurrence of a variable is where the value of the variable is referred. Each use occurrence is further classified as being a computational use or a predicate use. If the value of a variable is used to decide whether a predicate is true for selecting execution paths, the occurrence is called a predi- cate use. Otherwise, it is used to com- pute a value for defining other variables or as an output value. It is then called a computational use. For example, the as- signment statement “y :5 x1 1 x2” con- tains computational uses of x1 and x2 and a definition of y. The statement “if x1 , x2 then goto L endif” contains predicate uses of x1 and x2.

Since we are interested in tracing the flow of data between nodes, any defini- tion that is used only within the node in which the definition occurs is of little importance. Therefore a distinction is made between local computational uses and global computational uses. A global computational use of a variable x is where no definition of x precedes the computational use within the node in which it occurs. That is, the value must

have been bound to x in some node other than the one in which it is being used. Otherwise it is a local computa- tional use.

Data-flow test adequacy analysis is concerned with subpaths from defini- tions to nodes where those definitions are used. A definition-clear path with respect to a variable x is a path where for all nodes in the path there is no definition occurrence of the variable x. A definition occurrence of a variable x at a node u reaches a computational use occurrence of the variable at node v if and only if there is a path p from u to v such that p 5 (u, w1, w2, . . . , wn, v), and (w1, w2, . . . , wn) is definition-clear with respect to x, and the occurrence of x at v is a global computational use. We say that the definition of x at u reaches the computational occurrence of x at v through the path p. Similarly, if there is a path p 5 (u, w1, w2, . . . , wn, v) from u to v, and (w1, w2, . . . , wn) is defini- tion-clear with respect to x, and there is a predicate occurrence of x associated with the edge from wn to v, we say that u reaches the predicate use of x on the edge (wn, v) through the path p. If a path in one of the preceding definitions is feasible, that is, there is at least one input datum that can actually cause the execution of the path, we say that a definition feasibly reaches a use of the definition.

Three groups of data-flow adequacy criteria have been proposed in the liter- ature, and are discussed in the follow- ing.

B. Simple definition-use association coverage—the Rapps-Weyuker-Frankl family. Rapps and Weyuker [1985] proposed a family of testing adequacy criteria based on data-flow information. Their criteria are concerned mainly with the simplest type of data-flow paths that start with a definition of a variable and end with a use of the same variable. Frankl and Weyuker [1988] later reexamined the data-flow ade- quacy criteria and found that the origi- nal definitions of the criteria did not

378 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

satisfy the applicability condition. They redefined the criteria to be applicable. The following definitions come from the modified definitions.

The all-definitions criterion requires that an adequate test set should cover all definition occurrences in the sense that, for each definition occurrence, the testing paths should cover a path through which the definition reaches a use of the definition.

Definition 2.7 (All Definitions Crite- rion). A set P of execution paths satis- fies the all-definitions criterion if and only if for all definition occurrences of a variable x such that there is a use of x which is feasibly reachable from the def- inition, there is at least one path p in P such that p includes a subpath through which the definition of x reaches some use occurrence of x.

Since one definition occurrence of a variable may reach more than one use occurrence, the all-uses criterion re- quires that all of the uses should be exercised by testing. Obviously, this re- quirement is stronger than the all-defi- nition criterion.

Definition 2.8 (All Uses Criterion). A set P of execution paths satisfies the all-uses criterion if and only if for all definition occurrences of a variable x and all use occurrences of x that the definition feasibly reaches, there is at least one path p in P such that p in- cludes a subpath through which that definition reaches the use.

The all-uses criterion was also pro- posed by Herman [1976], and called reach-coverage criterion. As discussed at the beginning of the section, use occur- rences are classified into computational use occurrences and predicate use oc- currences. Hence, emphasis can be put either on computational uses or on predicate uses. Rapps and Weyuker [1985] identified four adequacy criteria of different strengths and emphasis. The all-c-uses/some-p-uses criterion re- quires that all of the computational

uses are exercised, but it also requires that at least one predicate use should be exercised when there is no computa- tional use of the variable. In contrast, the all-p-uses/some-c-uses criterion puts emphasis on predicate uses by requiring that test sets should exercise all predi- cate uses and exercise at least one computational use when there is no predicate use. Two even weaker criteria were also defined. The all-predicate- uses criterion completely ignores the computational uses and requires that only predicate uses need to be tested. The all-computation-uses criterion only requires that computational uses should be tested and ignores the predicate uses.

Notice that, given a definition occur- rence of a variable x and a use of the variable x that is reachable from that definition, there may exist many paths through which the definition reaches the use. A weakness of the preceding criteria is that they require only one of such paths to be exercised by testing. However, the applicability problem arises if all such paths are to be exer- cised because there may exist an infi- nite number of such paths in a flow graph. For example, consider the flow graph in Figure 1, the definition of y at node a1 reaches the use of y at node a3 through all the paths in the form:

~a1, a2! ∧ ~a2, a2!n ∧ ~a2, a3!, n $ 1,

where ∧ is the concatenation of paths, pn is the concatenation of p with itself for n times, which is inductively defined to be p1 5 p and pk 5 p ∧ pk21, for all k . 1. To obtain finite applicability, Frankl and Weyuker [1988] and Clarke et al. [1989] restricted the paths to be cycle-free or only the end node of the path to be the same as the start node.

Definition 2.9 (All Definition-Use- Paths Criterion: Abbr. All DU-Paths Criterion). A set P of execution paths satisfies the all-du-paths criterion if and only if for all definitions of a vari- able x and all paths q through which

Test Coverage and Adequacy • 379

ACM Computing Surveys, Vol. 29, No. 4, December 1997

that definition reaches a use of x, there is at least one path p in P such that q is a subpath of p, and q is cycle-free or contains only simple cycles.

However, even with this restriction, it is still not applicable since such a path may be infeasible.

C. Interactions between variables—the Ntafos required K-tuples criteria. Ntafos [1984] also used data-flow information to analyze test data adequacy. He stud- ied how the values of different variables interact, and defined a family of ade- quacy criteria called required k-tuples, where k . 1 is a natural number. These criteria require that a path set cover the chains of alternating definitions and uses, called definition-reference interac- tions (abbr. k–dr interactions) in Ntafos’ terminology. Each definition in a k–dr interaction reaches the next use in the chain, which occurs at the same node as the next definition in the chain. Formally:

Definition 2.10 (k–dr interaction). For k . 1, a k–dr interaction is a se- quence K 5 [d1(x1), u1(x1), d2(x2), u2(x2), . . . , dk(xk), uk(xk)] where

(i) di( xi), 1 # i , k, is a definition occurrence of the variable xi;

(ii) ui( xi), 1 # i , k, is a use occur- rence of the variable xi;

(iii) the use ui( xi) and the definition di11( xi) are associated with the same node ni11;

(iv) for all i, 1 # i , k, the ith defini- tion di( xi) reaches the ith use ui( xi).

Note that the variables x1, x2, . . . , xk and the nodes n1, n2, . . . , nk need not be distinct. This definition comes from Ntafos’ [1988] later work. It is different from the original definition where the nodes are required to be distinct [Ntafos 1984]. The same modification was also made by Clark et al. [1989] in their formal analysis of data flow adequacy criteria.

An interaction path for a k–dr inter-

action is a path p 5 (n1) p p1 p (n2) p . . . p (nk21) p pk21 p (nk) such that for all i 5 1, 2, . . . , k 2 1, di(xi) reaches ui(xi) through pi. The required k-tuples criterion then requires that all k–dr interactions are tested.

Definition 2.11 (Required k-Tuples Criteria). A set P of execution paths satisfies the required k-tuples criterion, k . 1, if and only if for all j–dr interac- tions L, 1 , j # k, there is at least one path p in P such that p includes a subpath which is an interaction path for L.

Example 2.1 Consider the flow graph in Figure 2. The following are 3–dr interaction paths.

~a1, a3, a2, a4! for the 3–dr

interaction @d1~ x!, u1~ x!, d2~ y!,

u2~ y!, d3~ x!, u3~ x!#; and

~a1, a2, a3, a4! for the 3–dr

interaction @d1~ y!, u1~ y!, d2~ x!,

u2~ x!, d3~ y!, u3~ y!#.

D. Combinations of definitions—the Laski-Korel criteria. Laski and Korel [1983] defined and studied another kind of testing path selection criteria based on data-flow analysis. They observed that a given node may contain uses of several different variables, where each use may be reached by several defini- tions occurring at different nodes. Such definitions constitute the context of the computation at the node. Therefore, they are concerned with exploring such contexts for each node by selecting paths along which the various combina- tions of definitions reach the node.

Definition 2.12 (Ordered Context). Let n be a node in the flow graph. Suppose that there are uses of the vari- ables x1, x2, . . . , xm at the node n.

4 Let

4 This assumption comes from Clark et al. [1989]. The original definition given by Laski and Korel

380 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

[n1, n2, . . . , nm] be a sequence of nodes such that for all i 5 1, 2, . . . , m, there is a definition of xi on node ni, and the definition of xi reaches the node n with respect to xi. A path p 5 p1 p (n1) p p2 p (n2) p . . . p pm p (nm) p pm11 p (n) is called an ordered context path for the node n with respect to the sequence [n1, n2, . . . , nm] if and only if for all i 5 2, 3, . . . , m, the subpath pi p (ni) p pi11 p . . . p pm11 is definition clear with re- spect to xi21. In this case, we say that the sequence [n1, n2, . . . , nm] of nodes is an ordered context for n.

Example 2.2 Consider the flow graph in Figure 1. There are uses of the two variables x and y at node a4. The node sequences [a1, a2], [a1, a3], [a2, a3], and [a3, a2] are ordered contexts for node a4. The paths (a1, a2, a4), (a1, a3, a4), (a2, a3, a4), and (a3, a2, a4) are the ordered context paths for them, respectively.

The ordered context coverage requires that an adequate test set should cover all ordered contexts for every mode.

Definition 2.13 (Ordered-Context Cov- erage Criterion). A set P of execution paths satisfies the ordered-context cov- erage criterion if and only if for all nodes n and all ordered contexts c for n, there is at least one path p in P such that p contains a subpath which is an ordered context path for n with respect to c.

Given a node n, let {x1, x2, . . . , xm} be a nonempty subset of the variables that are used at the node n, the nodes ni, i 5 1, 2, . . . , m, have definition occurrences of the variables xi, that reach the node n. If there is a permuta- tion s of the nodes which is an ordered context for n, then we say that the set {n1, n2, . . . , nm} is a context for n, and an ordered context path for n with re- spect to s is also called a definition context path for n with respect to the

context {n1, n2, . . . , nm}. Ignoring the ordering between the nodes, a slightly weaker criterion, called the context-cov- erage criterion, requires that all con- texts for all nodes are covered.

Definition 2.14 (Context-Coverage Cri- terion). A set P of execution paths sat- isfies the context coverage criterion if and only if for all nodes n and for all contexts for n, there is at least one path p in P such that p contains a subpath which is a definition context path for n with respect to the context.

E. Data-flow testing for structured data and dynamic data. The data flow testing methods discussed so far have a number of limitations. First, they make no distinction between atomic data such as integers and structured or aggregate data such as arrays and records. Modifi- cations and references to an element of a structured datum are regarded as modifications and references to the whole datum. It was argued that treat- ing structured data, such as arrays, as aggregate values may lead to two types of mistakes [Hamlet et al. 1993]. A com- mission mistake may happen when a definition-use path is identified but it is not present for any array elements. An omission mistake may happen when a path is missed because of a false inter- mediate assignment. Such mistakes oc- cur frequently even in small programs [Hamlet et al. 1993]. Treating elements of structured data as independent data can correct the mistakes. Such an ex- tension seems to add no complexity when the references to the elements of structured data are static, such as the fields of records. However, treating ar- rays element-by-element may introduce a potential infinity of definition-use paths to be tested. Moreover, theoreti- cally speaking, whether two references to array elements are references to the same element is undecidable. Hamlet et al. [1993] proposed a partial solution to this problem by using symbolic execu- tion and a symbolic equation solver to determine whether two occurrences of

[1983] defines a context to be formed from all variables having a definition that reaches the node.

Test Coverage and Adequacy • 381

ACM Computing Surveys, Vol. 29, No. 4, December 1997

array elements can be the occurrences of the same element.

The second limitation of the data-flow testing methods discussed is that dy- namic data were not taken into account. One of the difficulties in the data-flow analysis of dynamic data such as those referred to by pointers is that a pointer variable may actually refer to a number of data storage. On the other hand, a data storage may have a number of references to it, that is, the existence of alias. Therefore, for a given variable V, a node may contain a definite definition to the variable if a new value is defi- nitely bound to the variable at the node. It has a possible definition at a node n if it is possible that a new value is bound to it at the node. Similarly, a path may be definitely definition-clear or possibly definition-clear with respect to a vari- able. Ostrand and Weyuker [1991] ex- tended the definition-use association re- lation on the occurrences of variables to a hierarchy of relations. A definition- use association is strong if there is a definite definition of a variable and a definite use of the variable and every definition-clear path from the definition to the use is definitely definition-clear with respect to the variable. The associ- ation is firm if both the definition and the use are definite and there is at least one path from the definition to the use that it is definitely definition-clear. The association is weak if both the definition and the use are definite, but there is no path from the definition to the use which is definitely definition-clear. An association is very weak if the definition or the use or both of them are possible instead of definite.

F. Interprocedural data-flow test- ing. The data-flow testing methods discussed so far have also been re- stricted to testing the data dependence existing within a program unit, such as a procedure. As current trends in pro- gramming encourage a high degree of modularity, the number of procedure calls and returns executed in a module continues to grow. This mandates the

efficient testing of the interaction be- tween procedures. The basic idea of in- terprocedural data-flow testing is to test the data dependence across procedure interfaces. Harrold and Soffa [1990; 1991] identified two types of interproce- dural data dependences in a program: direct data dependence and indirect data dependence. A direct data depen- dence is a definition-use association whose definition occurs in procedure P and use occurs in a directly called proce- dure Q of P. Such a dependence exists when (1) a definition of an actual pa- rameter in one procedure reaches a use of the corresponding formal parameter at a call site (i.e., a procedure call); (2) a definition of a formal parameter in a called procedure reaches a use of the corresponding actual parameter at a re- turn site (i.e., a procedure return); or (3) a definition of a global variable reaches a call or return site. An indirect data dependence is a definition-use associa- tion whose definition occurs in proce- dure P and use occurs in an indirectly called procedure Q of P. Conditions for indirect data dependence are similar to those for direct data dependence, except that multiple levels of procedure calls and returns are considered. Indirect data dependence can be determined by considering the possible uses of defini- tions along the calling sequences. When a formal parameter is passed as an ac- tual parameter at a call site, an indirect data dependence may exist. Given this data dependence information, the data- flow test adequacy criteria can be easily extended for interprocedural data-flow testing. Harrold and Soffa [1990] pro- posed an algorithm for computing the interprocedural data dependences and developed a tool to support interproce- dural data-flow testing.

Based on Harrold and Soffa’s work, Ural and Yang [1988; 1993] extended the flow-graph model for accurate repre- sentation of interprocedural data-flow information. Pande et al. [1991] pro- posed a polynomial-time algorithm for determining interprocedural definition-

382 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

use association including dynamic data of single-level pointers for C programs.

2.1.3 Dependence Coverage Criterion— an Extension and Combination of Data- Flow and Control-Flow Testing. An ex- tension of data-flow testing methods was made by Podgurski and Clarke [1989; 1990] by generalizing control and data dependence. Informally, a state- ment s is semantically dependent on a statement s9 if the function computed by s9 affects the execution behavior of s. Podgurski and Clarke then proposed a necessary condition of semantic depen- dence called weak syntactic dependence as a generalization of data dependence. There is a weak syntactic dependence between two statements if there is a chain of data flow and a weak control dependence between the statements, where a statement u is weakly control- dependent on statement v if v has suc- cessors v9 and v0 such that if the branch from v to v9 is executed then u is neces- sarily executed within a fixed number of steps, whereas if the branch v to v0 is taken then u can be bypassed or its execution can be delayed indefinitely. Podgurski and Clarke also defined the notion of strong syntactic dependence: there is a strong syntactic dependence between two statements if there is a chain of data flow and a strong control dependence between the statements. Roughly speaking, a statement u is strongly control dependent on state- ment v if v has two successors v9 and v0 such that the execution through the branch v to v9 may result in the execu- tion of u, but u may be bypassed when the branch from v to v0 is taken. Pod- gurski and Clarke proved that strong syntactic dependence is not a necessary condition of semantic dependence.

When the definition-use association relation is replaced with various depen- dence relations, various dependence- coverage criteria can be obtained as ex- tensions to the data-flow test adequacy criteria. Such criteria make more use of semantic information contained in the

program under test. Furthermore, these dependence relations can be efficiently calculated.

2.2 Specification-Based Structural Testing

There are two main roles a specification can play in software testing [Richardson et al. 1992]. The first is to provide the necessary information to check whether the output of the program is correct [Podgurski and Clarke 1989; 1990]. Checking the correctness of program outputs is known as the oracle problem. The second is to provide information to select test cases and to measure test adequacy. As the purpose of this article is to study test adequacy criteria, we focus on the second use of specifications.

Like programs, a specification has two facets, syntactic structure and se- mantics. Both of them can be used to select test cases and to measure test adequacy. This section is concerned with the syntactic structure of a specifi- cation.

A specification specifies the proper- ties that the software must satisfy. Given a particular instance of the soft- ware’s input and its corresponding out- put, to check whether the instance of the software behavior satisfies these properties we must evaluate the specifi- cation by substituting the instance of input and output into the input and output variables in the specification, re- spectively. Although this evaluation process may take various forms, de- pending on the type of the specification, the basic idea behind the approach is to consider a particular set of elements or components in the specification and to calculate the proportion of such ele- ments or components involved in the evaluation.

There are two major approaches to formal software functional specifica- tions, model-based specifications and property-oriented specifications such as axiomatic or algebraic specifications. The following discussion is based on these types of specifications.

Test Coverage and Adequacy • 383

ACM Computing Surveys, Vol. 29, No. 4, December 1997

2.2.1 Coverage of Model-Based For- mal Functional Specifications. When a specification is model-based, such as those written in Z and VDM, it has two parts. The first describes the state space of the software, and the second part specifies the required operations on the space. The state space of the soft- ware system can be defined as a set of typed variables with a predicate to de- scribe the invariant property of the state space. The operations are func- tions mapping from input data and the state before the operation to the output data and the state after the operation. Such operations can be specified by a set of predicates that give the precondi- tion, that is, the condition on the input data and the state before the operation, and postconditions that specify the rela- tionship between the input data, output data, and the states before and after the operation.

The evaluation of model-based formal functional specifications is fairly similar to the evaluation of a Boolean expres- sion in an imperative programming lan- guage. When input and output variables in the expression are replaced with an instance of input data and program out- puts, each atomic predicate must be ei- ther true or false. If the result of the evaluation of the whole specification is true, then the correctness of the soft- ware on that input is confirmed. Other- wise, a program error is found. How- ever, the same truth value of a specification on two instances of input/ output may be due to different combina- tions of the truth values of the atomic predicates. Therefore it is natural to require that an adequate test cover a certain subset of feasible combinations of the predicates. Here a feasible combi- nation means that the combination can be satisfied; that is, there is an assign- ment of values to the input and output variables such that the atomic predi- cates take their corresponding values in the predicate combination. In the case where the specification contains nonde- terminism, the program may be less nondeterministic than the specification.

That is, some of the choices of output allowed by the specification may not be implemented by the program. This may not be considered a program error, but it may result in infeasible combinations.

A feasible combination of the atomic predicates in the preconditions is a de- scription of the conditions that test cases should satisfy. It specifies a sub- domain of the input space. It can be expressed in the same specification lan- guage. Such specifications of testing re- quirements are called test templates. Stocks and Carrington [1993] suggested the use of the formal functional specifi- cation language Z to express test tem- plates because the schema structure of Z and its schema calculus can provide support to the derivation and refine- ment of test templates according to for- mal specifications and heuristic testing rules. Methods have also been proposed to derive such test templates from mod- el-based specification languages. Amla and Ammann [1992] described a tech- nique to extract information from for- mal specifications in Z and to derive test templates written in Z for partition testing. The key step in their method is to identify the categories of the test data for each parameter and environ- ment variable of a functional unit under test. These categories categorize the in- put domain of one parameter or one environment variable according to the major characteristics of the input. Ac- cording to Amla and Ammann, there are typically two distinct sources of catego- ries in Z specifications: (a) characteris- tics enumerated in the preconditions and (b) characteristics of a parameter or environment variable by itself. For pa- rameters, these characteristics are based on their type. For environment variables, these characteristics may also be based on the invariant for the state components. Each category is then further divided into a set of choices. A choice is a subset of data that can be assigned to the parameter or the envi- ronment variable. Each category can be broken into at least two choices: one for the valid inputs and the other for the

384 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

invalid inputs. Finer partitions of valid inputs are derived according to the syn- tactic structure of the precondition predicate, the parameters, or the invari- ant predicate of the environment vari- ables. For example, the predicate “A ∨ B” is partitioned into three choices: (a) “¬ (A ∨ B)” for the set of data which are invalid inputs; (b) “A” for the subset of valid inputs which satisfy condition A; (3) “B” for the subset of valid inputs which satisfy the condition B.

Based on Amla and Ammann’s [1992] work, Ammann and Offutt [1994] re- cently considered how to test a func- tional unit effectively and efficiently by selecting test cases to cover various sub- sets of the combinations of the catego- ries and choices when the functional unit has more than one parameter and environment variable. They proposed three coverage criteria. The all-combi- nations criterion requires that software is tested on all combinations of choices; that is, for each combination of the choices of the parameters and the envi- ronment variables, there is at least one test datum in the combination. Let x1, x2, . . . , xn be the parameters and envi- ronment variables of the functional unit under test. Suppose that the choices for xi are Ai,1, Ai,2, . . . , Ai,ki, ki . 0, i 5 1, 2, . . . , n. Let C 5 {A1,u1 3 A2,u2 3 . . . 3 An,un u 1 # ui # ki and 1 # i # n}. C is then the set of all combinations of choices. The all combination criterion can be formally defined as follows.

Definition 2.15 (All-Combination Cri- terion). A set of test data T satisfies the all-combination criterion if for all c [ C, there exists at least one t [ T such that t [ c.

This criterion was considered to be inefficient, and the each-choice-used cri- terion was considered ineffective [Am- mann and Offutt 1994]. The each- choice-used criterion requires that each choice is used in the testing; that is, for each choice of each parameter or envi-

ronment variable, there is at least one test datum that belongs to the choice. Formally:

Definition 2.16 (Each-Choice-Used Criterion). A set of test data T satis- fies the each-choice-used criterion if the subset E 5 {e u e [ C and ?t [ T.(t [ e)} satisfies the condition:

@i.~1 # i # n

f~Ei 5 $Ai,1 , Ai,2 , . . . , Ai,ki%!!,

where

Ei 5 $eu ?X1 , . . . , Xi21 ,

Xi11 , . . . , Xn .~X1 3 . . . 3 Xi21 3 e

3 Xi11 3 . . . 3 Xn [ E!%.

Ammann and Offutt suggested the use of the base-choice-coverage criterion and described a technique to derive test templates that satisfy the criterion. The base-choice-coverage criterion is based on the notion of base choice, which is a combination of the choices of parame- ters and environment variables that represents the normal operation of the functional unit under test. Therefore, test cases of the base choice are useful to evaluate the function’s behavior in normal operation mode. To satisfy the base-choice-coverage criterion, software needs to be tested on the subset of com- binations of choices such that for each choice in a category, the choice is com- bined with the base choices for all other categories. Assume that A1,1 3 A2,1 3 . . . 3 An,1 is the base choice. The base- choice coverage criterion can be for- mally defined as follows.

Definition 2.17 (Base-Choice-Coverage Criterion). A set of test data T satis- fies the base-choice-coverage criterion if the subset E 5 {e u e [ C ∧ ?t [ T.(t [ e)} satisfies the following condition:

E $ ø i51

n

Bi ,

Test Coverage and Adequacy • 385

ACM Computing Surveys, Vol. 29, No. 4, December 1997

where

Bi 5 $A1,1 3 . . . 3 Ai21,1 3 Ai, j 3 Ai11,1

3 . . . 3 An,1u j 5 1, 2, . . . , ki%.

There are a number of works on spec- ification-based testing that focus on der- ivation of test cases from specifications, including Denney’s [1991] work on test- case generation from Prolog-based spec- ifications and many others [Hayes 1986; Kemmerer 1985; McMullin and Gannon 1983; Wild et al. 1992].

Model-based formal specification can also be in an executable form, such as a finite state machine or a state chart. Aspects of such models can be repre- sented in the form of a directed graph. Therefore, the program-based adequacy criteria based on the flow-graph model can be adapted for specification-based testing [Fujiwara et al. 1991; Hall and Hierons 1991; Ural and Yang 1988; 1993].

2.2.2 Coverage of Algebraic Formal Functional Specifications. Property- oriented formal functional specifications specify software functions by a set of properties that the software should pos- sess. In particular, an algebraic specifi- cation consists of a set of equations that the operations of the software must sat- isfy. Therefore checking if a program satisfies the specification means check- ing whether all of the equations are satisfied by the program.

An equation in an algebraic specifica- tion consists of two terms as two sides of the equation. A term is constructed from three types of symbols: variables representing arbitrary values of a given data type, constants representing a given data value in a data type, and operators representing data construc- tors and operations on data types.

Each term has two interpretations in the context of testing. First, a term rep- resents a sequence of calls to the opera- tions that implement the operators specified in the specification. When the variables in the term are replaced with constants, such a sequence of calls to

the operations represents a test execu- tion of the program, where the test case consists of the constants substituted for the variables. Second, a term also repre- sents a value, that is, the result of the sequence of operations. Therefore, checking an equation means executing the operation sequences for the two terms on the two sides of the equation and then comparing the results. If the results are the same or equivalent, the program is considered to be correct on this test case, otherwise the implemen- tation has errors. This interpretation allows the use of algebraic specifica- tions as test oracles.

Since variables in a term can be re- placed by any value of the data type, there is a great deal of freedom to choose input data for any given sequence of oper- ations. For algebraic specification, values are represented by ground terms, that is, terms without variables. Gaudel [Bouge et al. 1986; Bernot et al. 1991] and her colleagues suggested that the selection of test cases should be based on partitioning the set of ground terms according to their complexity so that the regularity and uni- formity hypotheses on the subsets in the partition can be assumed. The complexity of a test case is then the depth of nesting of the operators in the ground term. Therefore, roughly speaking, the selection of test cases should first consider con- stants specified by the specification, then all the values generated by one applica- tion of operations on constants, then val- ues generated by two applications on con- stants, and so on until the test set covers data of a certain degree of complexity.

The following hypothesis, called the regularity hypothesis [Bouge et al. 1986; Bernot et al. 1991], formally states the gap between software correctness and adequate testing by the preceding ap- proach.

Regularity Hypothesis

@x~complexity~ x! # K f t~ x!

5 t9~ x!! f @x~t~ x! 5 t9~ x!! (2.1)

386 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

Informally, the regularity hypothesis assumes that for some complexity de- gree k, if a program satisfies an equa- tion t(x) 5 t9(x) on all data of complex- ity not higher than k, then the program satisfies the equation on all data. This hypothesis captures the intuition of in- ductive reasoning in software testing. But it cannot be proved formally (at least in its most general form) nor vali- dated empirically. Moreover, there is no way to determine the complexity k such that only the test cases of complexity less than k need to be tested.

2.3 Summary of Structure Coverage Criteria

In summary, when programs are mod- eled as directed graphs, paths in the flow graph should be exercised by test- ing. However, only a finite subset of the paths can be checked during testing. The problem is therefore to choose which paths should be exercised.

Control-flow test data adequacy crite- ria answer this question by specifying restrictions on the complexity of the paths or by specifying restrictions on the redundancy among paths. Data-flow adequacy criteria use data-flow infor- mation in the program and select paths that are significant with respect to such information. Data-flow and control-flow adequacy criteria can be extended to dependence coverage criteria, which make more use of semantic information contained in the program under test. However, none of these criteria use in- formation about software requirements or functional specifications.

Specification-based structure cover- age criteria specify testing require- ments and measure test adequacy ac- cording to the extent that the test data cover the required functions specified in formal specifications. These criteria fo- cus on the specification and ignore the program that implements the specifica- tion.

As discussed in Section 1, software testing should employ information con- tained in the program as well as infor-

mation in the specification. A simple way to combine program-based struc- tural testing with specification-based structure coverage criteria is to mea- sure test adequacy with criteria from both approaches.

3. FAULT-BASED ADEQUACY CRITERIA

Fault-based adequacy criteria measure the quality of a test set according to its effectiveness or ability to detect faults.

3.1 Error Seeding

Error seeding is a technique originally proposed to estimate the number of faults that remain in software. By this method, artificial faults are introduced into the program under test in some suitable random fashion unknown to the tester. It is assumed that these arti- ficial faults are representative of the inherent faults in the program in terms of difficulty of detection. Then, the soft- ware is tested and the inherent and artificial faults discovered are counted separately. Let r be the ratio of the number of artificial faults found to the number of total artificial faults. Then the number of inherent faults in the program is statistically predicted with maximum likelihood to be f/r, where f is the number of inherent faults found by testing.

This method can also be used to mea- sure the quality of software testing. The ratio r of the number of artificial faults found to the total number of artificial faults can be considered as a measure of the test adequacy. If only a small pro- portion of artificial faults are found dur- ing testing, the test quality must be poor. In this sense, error seeding can show weakness in the testing.

An advantage of the method is that it is not restricted to measuring test qual- ity for dynamic testing. It is applicable to any testing method that aims at find- ing errors or faults in the software.

However, the accuracy of the measure is dependent on how faults are intro- duced. Usually, artificial faults are

Test Coverage and Adequacy • 387

ACM Computing Surveys, Vol. 29, No. 4, December 1997

manually planted, but it has been proved difficult to implement error seeding in practice. It is not easy to introduce artificial faults that are equivalent to inherent faults in diffi- culty of detection. Generally, artificial errors are much easier to find than in- herent errors. In an attempt to over- come this problem, mutation testing in- troduces faults into a program more systematically.

3.2 Program Mutation Testing

3.2.1 Principles of Mutation Ade- quacy Analysis. Mutation analysis is proposed as a procedure for evaluating the degree to which a program is tested, that is, to measure test case adequacy [DeMillo et al. 1978; Hamlet 1977]. Briefly, the method is as follows. We have a program p and a test set t that has been generated in some fashion. The first step in mutation analysis is the construction of a collection of alter- native programs that differ from the original program in some fashion. These alternatives are called mutants of the original program, a name borrowed from biology. Each mutant is then exe- cuted on each member of the test set t, stopping either when an element of t is found on which p and the mutant pro- gram produce different responses, or when t is exhausted.

In the former case we say that the mutant has died since it is of no further value, whereas in the latter case we say the mutant lives. These live mutants provide valuable information. A mutant may remain alive for one of the follow- ing reasons.

(1) The test data are inadequate.

If a large proportion of mutants live, then it is clear that on the basis of these test data alone we have no more reason to believe that p is correct than to be- lieve that any of the live mutants are correct. In this sense, mutation analysis can clearly reveal a weakness in test data by demonstrating specific pro- grams that are not ruled out by the test

data presented. For example, the test data may not exercise the portion of the program that was mutated.

(2) The mutant is equivalent to the original program.

The mutant and the original program always produce the same output, hence no test data can distinguish between the two. Normally, only a small percent- age of mutants are equivalent to the original program.

Definition 3.1 (Mutation Adequacy Score). The mutation adequacy of a set of test data is measured by an adequacy score computed according to the follow- ing equation.

Adequacy Score S 5 D

M 2 E

where D is the number of dead mutants, M is the total number of mutants, and E is the number of equivalent mutants.

Notice that the general problem of deciding whether a mutant is equiva- lent to the original program is undecid- able.

3.2.2 Theoretical Foundations of Mu- tation Adequacy. Mutation analysis is based on two basic assumptions—the competent programmer hypothesis and the coupling effect hypothesis. These two assumptions are based on observa- tions made in software development practice, and if valid enable the practi- cal application of mutation testing to real software [DeMillo et al. 1988]. However, they are very strong assump- tions whose validity is not self-evident.

A. Competent programmer assump- tion. The competent programmer hy- pothesis assumes that the program to be tested has been written by competent programmers. That is, “they create pro- grams that are close to being correct” [DeMillo et al. 1988]. A consequence drawn from the assumption by DeMillo et al. [1988] is that “if we are right in our perception of programs as being close to correct, then these errors should

388 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

be detectable as small deviations from the intended program.” In other words, the mutants to be considered in muta- tion analysis are those within a small deviation from the original program. In practice, such mutants are obtained by systematically and mechanically apply- ing a set of transformations, called mu- tation operators, to the program under test. These mutation operators would ideally model programming errors made by programmers. In practice, this may be only partly true. We return to muta- tion operators in Section 3.2.3.

B. Coupling effect assumption. The second assumption in mutation analysis is the coupling effect hypothesis, which assumes that simple and complex errors are coupled, and hence test data that cause simple nonequivalent mutants to die will usually also cause complex mu- tants to die.

Trying to validate the coupling effect assumption, Offutt [1989; 1992] did an empirical study with the Mothra muta- tion-testing tool. He demonstrated that a test set developed to kill first-order mutants (i.e., mutants) can be very suc- cessful at killing second-order mutants (i.e., mutants of mutants). However, the relationship between second-order mu- tants and complex faults remains un- clear.

In the search for the foundation of mutation testing, theories have been de- veloped for fault-based testing in gen- eral and mutation testing in particular. Program correctness is usually taken to mean that the program computes the intended function. But in mutation analysis there is another notion of cor- rectness, namely, that a certain class of faults has been ruled out. This is called local correctness here to distinguish it from the usual notion of correctness.

According to Budd and Angluin [1982] local correctness of a program p can be defined relative to a neighborhood F of p, which is a set of programs containing the program p itself. Precisely speaking, F is a mapping from a program p to a

set of programs F(p). We say that p is locally correct with respect to F if, for all programs q in F(p), either q is equivalent to p or q fails on at least one test point in the input space. In other words, in the neighborhood of a pro- gram only the program and its equiva- lents are possibly correct, because all others are incorrect. With the compe- tent programmer hypothesis, local cor- rectness implies correctness if the neighborhood is always large enough to cover at least one correct program.

Definition 3.2 (Neighborhood Ade- quacy Criterion). A test set t is F-ade- quate if for all programs q Þ p in F, there exists x in t such that p(x) Þ q(x).

Budd and Angluin [1982] studied the computability of the generation and rec- ognition of adequate test sets with re- spect to the two notions of correctness, but left the neighborhood construction problem open.

The neighborhood construction prob- lem was investigated by Davis and Weyuker [1988; 1983]. They developed a theory of metric space on programs written in a language defined by a set of production rules. A transition sequence from program p to program q was de- fined to be a sequence of the programs p1, p2, . . . , pn such that p1 5 p and pn 5 q, and for each i 5 1, 2, . . . , n 2 1, either pi11 is obtained from pi (a for- ward step) or pi can be obtained from pi11 (a backward step), using one of the productions of the grammar in addition to a set of short-cut rules to catch the intuition that certain kinds of programs are conceptually close. The length of a transition sequence is defined to be the maximum of the number of forward steps and the number of backward steps in the transition sequence. The distance r(p, q) between program p and q is then defined as the smallest length of a tran- sition sequence from p to q. This dis- tance function on the program space can be proved to satisfy the axioms of a metric space, that is, for all programs p, q, r,

Test Coverage and Adequacy • 389

ACM Computing Surveys, Vol. 29, No. 4, December 1997

(1) r( p, q) $ 0; (2) r( p, q) 5 0 if and only if p 5 q; (3) r( p, q) 5 r(q, p); (4) r( p, r) $ r( p, q) 1 r(q, r).

Then, the neighborhood Fd(p) of pro- gram p within a distance d is the set of programs within the distance d accord- ing to r; formally, Fd(p) 5 {q u r(p, q) # d}. Davis and Weyuker introduced the notion of critical points for a program with respect to a neighborhood. Intu- itively, a critical point for a program is a test case that is the unique input to kill some mutant in the neighborhood set. Formally:

Definition 3.3 (Critical Points). An input c is a F-critical point for p with respect to F if there exists a program q [ F such that for all x Þ c, p(x) 5 q(x) but p(c) Þ q(c).

There is a nice relationship between critical points [Davis and Weyuker 1988] and adequate test sets. First, F-critical points must be members of any F-adequate test sets. Second, when the distance d increases, the neighbor- hood set Fd(p) as well as the set of critical points increase in the sense of set inclusion. That is, if c is Fd(p)- critical, then for all « $ d, c is also

F«(p)-critical. Finally, by studying min- imally adequate test sets, Davis and Weyuker [1988] obtained a lower bound of the numbers of non-critical points that must be present in an adequate test set.

3.2.3 Mutation Transformations. Now let us consider the problem of how to generate mutants from a given program. A practical method is the use of mutation operators. Generally speaking, a muta- tion operator is a syntactic transforma- tion that produces a mutant when applied to the program under test. It applies to a certain type of syntactic structure in the program and replaces it with another. In current mutation testing tools such as Mothra [King and Offutt 1991], the muta- tion operators are designed on the basis of many years’ study of programmer er- rors. Different levels of mutation analysis can be done by applying certain types of mutation operators to the corresponding syntactical structures in the program. Ta- ble I from Budd [1981], briefly describes the levels of mutation analysis and the corresponding mutation operators. This framework has been used by almost all of the mutation testing tools.

3.2.4 The Pros and Cons. Using a mutation-based testing system, a tester

Table I. Levels of Analysis in Mutation Testing

a An erroneous expression may coincidentally compute correct output on a particular input. For example, assume that a reference to a variable is mistaken by referring to another variable, but in a particular case these two variables have the same value. Then, the expression computes the correct output on the particular input. If such an input is used as a test case, it is unable to detect the fault. Coincidental correctness analysis attempts to analyse whether a test set suffers from such weakness.

390 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

supplies the program to be tested and chooses the levels of mutation analysis to be performed. Then the system gener- ates the set of mutants. The tester also supplies a test set. The testing system executes the original program and each mutant on each test case and compares the outputs produced by the original program and its mutants. If the output of a mutant differs from the output of the original program, the mutant is marked dead. Once execution is com- plete, the tester examines any mutants that are still alive. The tester can then declare a mutant to be equivalent to the original program, or can supply addi- tional test data in an effort to kill the mutant.

Reports on experiments with muta- tion-based testing have claimed that the method is powerful and has a num- ber of attractive features [DeMillo and Mathur 1990; DeMillo et al. 1988].

(1) Mutation analysis allows a great de- gree of automation. Mutants are generated by applying mutation op- erators and are then compiled and executed. The outputs of the mu- tants and the original programs are compared and then a mutation ade- quacy score is calculated. All these can be supported by mutation-test- ing software such as that of Mothra [DeMillo et al. 1988; King and Of- futt 1991].

(2) Mutation-based testing systems pro- vide an interactive test environment that allows the tester to locate and remove errors. When a program un- der test fails on a test case and a mutant does not, the tester should find it easy to locate and remove the error by considering the mutation operator applied and the location where the mutation operator is ap- plied.

(3) Mutation analysis includes many other testing methods as special cases. For example, statement cov- erage and branch coverage are spe- cial cases of statement analysis in mutation testing. This can be

achieved by replacing a statement or a branch by the special statement TRAP, which causes the abortion of the execution.

The drawback of mutation testing is the large computation resources (both time and space) required to test large- scale software. It was estimated that the number of mutants for an n-line program is on the order of n2 [Howden 1982]. Recently, experimental data con- firmed this estimate; see Section 5.3 [Offutt et al. 1993]. A major expense in mutation testing is perhaps the sub- stantial human cost of examining large numbers of mutants for possible equiva- lence, which cannot be determined ef- fectively. An average of 8.8% of equiva- lent mutants had been observed in experiments [Offutt et al. 1993].

3.3 Variants of Program Mutation Testing

Using the same idea of mutation analy- sis, Howden [1982] proposed a testing method to improve efficiency. His test- ing method is called weak mutation test- ing because it is weaker than the origi- nal mutation testing. The original method was referred to as strong muta- tion testing. The fundamental concept of weak mutation testing is to identify classes of program components and er- rors that can occur in the components. Mutation transformations are then ap- plied to the components to generate mu- tants of the components. For each com- ponent and a mutant of the component, weak mutation testing requires that a test datum be constructed so that it causes the execution of the component and that the original component and the mutant compute different values. The major advantage of weak mutation test- ing is efficiency. Although there is the same number of mutants in weak muta- tion testing as in strong mutation test- ing, it is not necessary to carry out a separate program execution for each mutant. Although a test set that is ade- quate for weak mutation testing may not be adequate for the strong mutation

Test Coverage and Adequacy • 391

ACM Computing Surveys, Vol. 29, No. 4, December 1997

testing, experiments with weak muta- tion testing such as Offutt and Lee’s [1991] and Marick’s [1991] suggest that it can still be an effective testing method.

From a more general view of muta- tion-testing principles, Woodward and Halewood [1988] proposed firm muta- tion testing. They regarded mutation testing as the process of making small changes in a program and comparing the outcomes of the original and changed versions. They identified a set of parameters of such changes and com- parisons. The basic idea of firm muta- tion testing is to make such parameters explicit so that they can be altered by testers. Strong and weak mutation test- ing are two extremes of the firm-mutation testing method. The advantage of firm- mutation testing is that it is less expen- sive than strong-mutation testing but stronger than weak-mutation testing. In addition, firm-mutation testing provides a mechanism for the control of fault intro- duction and test results comparison. The major disadvantage of firm-mutation testing is that there is no obvious system- atic basis on which to select the parame- ters and the area of program code.

Returning to frameworks for strong mutation testing, ordered mutation test- ing was proposed to improve efficiency without sacrificing effectiveness. The idea is to construct an order # between mutants such that mutant b is stronger than a (written a # b) if for any test case t, t kills b implies that t necessar- ily kills a. Therefore, mutant b should be executed on test cases before the execution of a, and a is executed only when the test data failed to kill b. A similar ordering can also be defined on test data. Given a mutant q of program p, q should be executed on test data t before the execution on test data s if t is more likely to kill q than s is. Ordering on mutation operators was proposed to achieve the ordering on mutants in early ’80s by Woodward et al. [1980] and Riddell et al. [1982], and reap- peared recently in a note by Duncan and Robson [1990]. A mutation opera- tion f is said to be stronger than f9 if for all programs p, the application of f

to p always gives a mutant that is stronger than the mutants obtained by the application of f9 to p at the same location. Taking the relational opera- tor 5 as an example, mutants can be generated by replacing “5” with “Þ”, “#”, “$”, “,”, and “.”, respectively. In- tuitively, replacing “5” with “Þ” should be stronger than replacing with “,”, because if the test data are not good enough to distinguish “5” from “Þ”, it would not be adequate for other rela- tional operators. Based on such argu- ments, a partial ordering on relational operators was defined. However, Wood- ward [1991] proved that operator order- ing is not the right approach to achiev- ing mutant ordering. The situation turns out to be quite complicated when a mutation operator is applied to a loop body, and a counterexample was given. Experiments are needed to see how ef- fective ordered mutation testing can be and to assess the extent of cost saving.

It was observed that some mutation operators generate a large number of mutants that are bound to be killed if a test set kills other mutants. Therefore, Mathur [1991] suggested applying the mutation testing method without apply- ing the two mutation operators that produce the most mutants. Mathur’s method was originally called con- strained mutation testing. Offutt et al. [1993] extended the method to omit the first N most prevalent mutation opera- tors and called it N-selective mutation testing. They did an experiment on se- lective testing with the Mothra muta- tion testing environment. They tested 10 small programs using an automatic test-case generator, Godzilla [DeMillo and Offutt 1991; 1993]. Their experi- mentation showed that with full selec- tive mutation score, an average nonse- lective mutation score of 99.99, 99.84 and 99.71% was achieved by 2-selective, 4-selective, and 6-selective mutation testing, respectively. Meanwhile, the average savings5 for these selective mu- tations were 23.98, 41.36, and 60.56%,

5 The savings are measured as the reduction of the number of mutants.

392 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

respectively [Offutt et al. 1993]. Mathur theorized that selective mutation test- ing has complexity linear in program size measured as the number of variable references, and yet retains much of the effectiveness of mutation testing. How- ever, experimental data show that the number of mutants is still quadratic although the savings are substantial [Offutt et al. 1993].

3.4 Perturbation Testing

While mutation testing systematically plants faults in programs by applica- tions of syntactic transformations, Zeil’s perturbation testing analyses test effec- tiveness by considering faults in an “er- ror” space. It is concerned with faults in arithmetic expressions within program statements [Zeil 1983]. It was proposed to test vector-bounded programs, which have the following properties: (1) vector- bounded programs have a fixed number of variables on a continuous input do- main; (2) in the flow-graph model, each node n in the flow graph is associated with a function Cn that transforms the environment v to a new environment v9. Here, environment is a vector (x1, x2, . . . , xn, y1, y2, . . . , ym) which consists of the current values of the input vari- ables xi and the values of the intermedi- ate and output variables yi. The func- tions associated with nodes are assumed to be in a class C which is closed under function composition. (3) each node may have at most two out- ward arcs. In such cases the node n is also associated with a predicate Tn, which is applied to the new environ- ment obtained by applying Cn and com- pared with zero to determine the next node for execution. It was assumed that the predicates are simple, not combined with and, or, or other logical operators. (4) the predicates are assumed to be in a class T which is a vector space over the real numbers R of dimension k and is closed under composition with C. Exam- ples of vector spaces of functions include the set of linear functions, the set of

polynomial functions of degree k, and the set of multinomials of degree k.

There are some major advantages of vector boundedness. First, any finite- dimensioned vector space can be de- scribed by a finite set of characteristic vectors such that any member of the vector space is a linear combination of the characteristic vectors. Second, vec- tor spaces are closed under the opera- tions of addition and scalar multiplica- tion. Suppose that some correct function C has been replaced by an erroneous form C9. Then the expression C 2 C9 is the effect of the fault on the transforma- tion function. It is called the error func- tion of C9 or the perturbation to C. Since the vector space contains C and C9, the error function must also be in the vector space. This enables us to study faults in a program as functional differences be- tween the correct function and the in- correct function rather than simply as syntactical differences, as in mutation testing. Thus it builds a bridge between fault-based testing and error-based test- ing, which is discussed in Section 4.

When a particular error function space E is identified, a neighborhood of a given function f can be expressed as the set of functions in the form of f 1 fe, where fe [ E. Test adequacy can then be defined in terms of a test set’s ability to detect error functions in a particular error function space. Assuming that there are no missing path errors in the program, Zeil considered the error func- tions in the function C and the predi- cate T associated with a node. The fol- lowing gives more details about perturbation of these two types of func- tions.

3.4.1 Perturbation to the Predicate. Let n be a node in a flow graph and Cn and Tn be the computation function and predicate function associated with node n. Let A be a path from the begin node to node n and CA be the function com- puted through the path. Let T9 be the correct predicate that should be used in place of Tn. Suppose that the predicate is tested by an execution through the

Test Coverage and Adequacy • 393

ACM Computing Surveys, Vol. 29, No. 4, December 1997

path A. Recall that a predicate is a real-valued function, and its result is compared with zero to determine the direction of control transfer. If in a test execution the error function e 5 T9 2 Tn is evaluated to zero, it does not affect the direction of control transfer. There- fore the error function e 5 T9 2 Tn cannot be detected by such an execution if and only if there exists a positive scalar a such that

Tn ° CA~v0! 5 aT9 ° CA~v0!,

for all initial environments v0 which cause execution through path A, where ° is functional composition. The subset of T that consists of the functions satisfying the preceding equation is called the blind- ness space for the path A, denoted by BLIND(A). Zeil identified three types of blindness and provided a constructive method to obtain BLIND(A) for any path A. Assignment blindness consists of func- tions in the following set.

null~CA! 5 $eue [ T ∧ @v. e ° CA~v! 5 0%.

These functions evaluate to zero when the expressions computed in CA are sub- stituted for the program variables. After the assignment statement “X :5 f(v)”, for example, the expression “X 2 f(v)” can be added into the set of undetect- able predicates. Equality blindness con- sists of equality restrictions on the path domain. To be an initial environment that causes execution of a path A, it must satisfy some restrictions. A re- striction can be an equality, such as x 5 2. If an input restriction r(v0) 5 0 is imposed, then the predicate r(v) 5 0 is an undetectable error function. The fi- nal component of undetectable predi- cates is the predicate Tn itself. Because Tn(v) compared with zero and aTn(v) compared with zero are identical for all positive real numbers a, self-blindness consists of all predicates of the form aTn(v). These three types of undetect- able predicates can be combined to form more complicated undetectable error functions.

Having given a characterization theo- rem of the set BLIND(A) and a con- structive methods to calculate the set, Zeil defined a test-path selection crite- rion for predicate perturbations.

Definition 3.4 (Adequacy of Detecting Predicate Perturbation). A set P of paths all ending at some predicate T is perturbation-test-adequate for predicate T if

ù p[P

BLIND~ p! 5 B.

Zeil’s criterion was originally stated in the form of a rejection rule: if a program has been reliably tested on a set P of execution paths that all end at some predicate T, then an additional path p also ending at T need not be tested if and only if

ù x[P

BLIND~ x! # BLIND~ p!.

Zeil also gave the following theorem about perturbation testing for predicate errors.

THEOREM 3.1 (Minimal Adequate Test Set for Predicate Perturbation Testing). A minimal set of subpaths adequate for testing a given predicate in a vector bounded program contains at most k subpaths, where k is the dimension of T.

3.4.2 Perturbation to Computations. The perturbation function of the compu- tation associated with node n can also be expressed as e 5 C9 2 Cn where C9 is the unknown correct computation. However, a fault in computation func- tion may cause two types of errors: do- main error or computation error. A com- putation error can be revealed if there is a path A from the begin node to the node n and a path B from node n to a node that contains an output statement M, such that for some initial environ- ment v0 that causes the execution of paths A and B

M ° CB ° Cn ° CA~v0!

Þ M ° CB ° C9 ° CA~v0!.

394 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

A sufficient condition of this inequality is that M ° CB ° e ° CA(v0) Þ 0. The set of functions that satisfy the equation M ° CB ° e ° CA(v0) 5 0 for all v0 that execute A and B is then the blindness space of the test execution through the path A followed by B.

A domain error due to an erroneous computation function Cn can be re- vealed by a path A from the begin node to node n and a path B from node n to a node m with predicate Tm, if for some initial environment v0 that causes the execution of paths A and B to node m.

Tm ° CB ° Cn ° CA~v0!

Þ aTm ° CB ° C9 ° CA~v0!.

In other words, the erroneous computa- tion may cause domain error if the fault affects the evaluation of a predicate. The blindness space of a test path for detecting such perturbations of a com- putation function can be expressed by the equation: Tm ° CB ° e ° CA(v0) 5 0, where e 5 Cn 2 C9.

A solution to the two preceding equa- tions was obtained for linear-dominated programs, which are bounded vector programs with the additional restric- tions that C is the set of linear trans- formations and T is the set of linear functions [Zeil 1983]. The solution es- sentially consists of two parts: assign- ment blindness and equality blindness, as in predicate perturbation, and blind- ness due to computation CB masking out differences between Cn and C9. An adequacy criterion similar to the predi- cate perturbation adequacy was also de- fined.

The principle of perturbation testing can be applied without the assumptions about the computation function space C and the predicate function space T, but selecting an appropriate error function space E. Zeil [1983] gave a characteriza- tion of the blindness space for vector error spaces without the condition of linearity. The principle of perturbation testing can also be applied to individual test cases [Zeil 1984]. The notion of

error space has been applied to improve domain-testing methods as well [Afifi et al. 1992; Zeil et al. 1992], which are discussed in Section 4.

Although both mutation testing and perturbation testing are aimed at de- tecting faults in software, there are a number of differences between the two methods. First, mutation testing mainly deals with faults at the syntactical level, whereas perturbation testing fo- cuses on the functional differences. Sec- ond, mutation testing systematically generates mutants according to a given list of mutation operators. The pertur- bation testing perturbs a program by considering perturbation functions drawn from a structured error space, such as a vector space. Third, in muta- tion testing, a mutant is killed if on a test case it produces an output different from the output of the original program. Hence the fault is detected. However, for perturbation testing, the blindness space is calculated according to the test cases. A fault is undetected if it remains in the blindness space. Finally, al- though mutation testing is more gener- ally applicable in the sense that there are no particular restrictions on the software under test, perturbation test- ing guarantees that combinations of the faults can be detected if all simple faults are detected, provided that the error space is a vector space.

3.5 The RELAY Model

As discussed in perturbation testing, it is possible for a fault not to cause an error in output even if the statement containing the fault is executed. With the restriction to linear-domained pro- grams, Zeil provided conditions on which a perturbation (i.e., a fault), can be exposed.

The problem of whether a fault can be detected was addressed by Morrel [1990], where a model of error origina- tion and transfer was proposed. An er- ror is originated (called “created” by Morrel) when an incorrect state is intro- duced at some fault location, and it is

Test Coverage and Adequacy • 395

ACM Computing Surveys, Vol. 29, No. 4, December 1997

transferred (called “propagated” by Mor- rel) if it persists to the output.

The RELAY model proposed by Rich- ardson and Thompson [1988; 1993] was built upon Morrel’s theory, but with more detailed analysis of how an error is transferred and the conditions of such transfers. The errors considered within the RELAY model are those caused by particular faults in a module. A poten- tial fault is a discrepancy between a node n in the module under test and the corresponding node n* in the hypotheti- cally correct module. This potential fault results in a potential error if the expression containing the fault is exe- cuted and evaluated to a value different from that of the corresponding hypo- thetically correct expression. Given a potential fault, a potential error origi- nates at the smallest subexpression of the node containing the fault that eval- uates incorrectly. The potential error transfers to a superexpression if the su- perexpression evaluates incorrectly. Such error transfers are called compu- tational transfer. To reveal an output error, execution of a potential fault must cause an error that transfers from node to node until an incorrect output results, where an error in the function computed by a node is called a context error. If a potential error is reflected in the value of some variable that is refer- enced at another node, the error trans- fer is called a data-flow transfer. This process of error transfer is illustrated in Figure 4.

Therefore the conditions under which a fault is detected are:

(1) origination of a potential error in the smallest subexpression contain- ing the fault;

(2) computational transfer of the poten- tial error through each operator in the node, thereby revealing a con- text error;

(3) data-flow transfer of that context error to another node on the path that references the incorrect con- text;

(4) cycle through (2) and (3) until a potential error is output.

If there is no input datum for which a potential error originates and all these transfers occur, then the potential fault is not a fault. This view of error detection has an analogy in a relay race, hence the name of the model. Based on this view, the RELAY model develops revealing con- ditions that are necessary and sufficient to guarantee error detection. Test data are then selected to satisfy revealing con- ditions. When these conditions are in- stantiated for a particular type of fault, they provide a criterion by which test data can be selected for a program so as to guarantee the detection of an error caused by any fault of that type.

3.6 Specification-Mutation Testing

Specification-fault-based testing at- tempts to detect faults in the implemen- tation that are derived from misinter- preting the specification or the faults in the specification. Specification-fault- based testing involves planting faults into the specification. The program that

Figure 4. RELAY model of fault detection.

396 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

implements the original specification is then executed and the results of the execution are checked against the origi- nal specification and those with planted faults. The adequacy of the test is deter- mined according to whether all the planted faults are detected by checking.

Gopal and Budd [1983] extended pro- gram-mutation testing to specification- mutation testing for specifications writ- ten in predicate calculus. They identified a set of mutation operations that are applied to a specification in the form of pre/postconditions to generate mutants of the specification. Then the program under test is executed on test cases to obtain the output of the program. The input/output pair is used to evaluate the mutants of the specification. If a mutant is falsified by the test cases in the eval- uation, we say that it is killed by the test cases; otherwise it remains alive.

Gopal and Budd [1983] noticed that some alterations to specifications were not useful as mutation operators. For example, replacing the various clauses in the specification by the truth values “true” or “false” tends to generate mu- tants that are trivial to kill and appear to be of little practical significance.

In an investigation of mutation opera- tors for algebraic specifications, Wood- ward [1993] defined his set of mutation operators based on his analysis of errors in the specifications made by students. He considered algebraic specifications as term-rewriting systems. The original specification and the mutants of the spec- ification are compiled into executable codes. When the executions of the original specification and a mutant on a given test case generate two different outputs, the mutant is regarded as dead. Otherwise, it is alive. In this way the test adequacy is measured without executing the program.

3.7 Summary of Fault-Based Adequacy Criteria

Fault-based adequacy criteria focus on the faults that could possibly be con- tained in the software. The adequacy of

a test set is measured according to its ability to detect such faults.

Error seeding is based on the assump- tion that the artificial faults planted in the program are as difficult to detect as the natural errors. This assumption has proved not true in general.

Mutation analysis systematically and automatically generates a large number of mutants. A mutant represents a pos- sible fault. It can be detected by the test cases if the mutant produces an output different from the output of the original program. The most important issue in mutation-adequacy analysis is the de- sign of mutation operators. The method is based on the competent-programmer and coupling-effect hypotheses. The principle of mutation-adequacy analysis can be extended to specification-based- adequacy analysis. Given a set of test cases and the program under test, mu- tation adequacy can be calculated auto- matically except for detection of equiva- lent mutants.

However, measuring the adequacy of software testing by mutation analysis is expensive. It may require large compu- tation resources to store and execute a large number of mutants. It also re- quires huge human resources to deter- mine if live mutants are equivalent to the original program. Reduction of the testing expense to a practically accept- able level has been an active research topic. Variants such as weak mutation testing, firm mutation testing, and or- dered mutation testing have been pro- posed. Another approach not addressed in this article is the execution of mu- tants in parallel computers [Choi et al. 1989; Krauser et al. 1991]. This re- quires the availability of massive paral- lel computers and very high portability of the software so that it can be exe- cuted on the target machine as well as the testing machine. In summary, al- though progress has been made to re- duce the expense of adequacy measure- ment by mutation analysis, there remain open problems.

Perturbation testing is concerned with the possible functional differences

Test Coverage and Adequacy • 397

ACM Computing Surveys, Vol. 29, No. 4, December 1997

between the program under test and the hypothetical correct program. The ade- quacy of a test set is decided by its ability to limit the error space defined in terms of a set of functions.

A test case may not reveal a fault. The RELAY model analyzed the condi- tion under which a test case reveals a fault. Therefore, given a fault, test cases can be selected to satisfy the conditions, and hence guarantee the detection of the fault. This model can also be used as a basis of test adequacy criteria.

4. ERROR-BASED ADEQUACY CRITERIA AND DOMAIN ANALYSIS

Error-based testing methods require test cases to check programs on certain error-prone points [Foster 1980; Myers 1979]. The basic idea of domain analysis and domain testing is to partition the input-output behavior space into subdo- mains so that the behavior of the soft- ware on each subdomain is equivalent, in the sense that if the software behaves correctly for one test case within a sub- domain, then we can reasonably assume that the behavior of the software is cor- rect for all data within that subdomain. We may wish, however, to take more than one test case within each subdo- main in order to increase our confidence in the conformance of the implementa- tion upon this subdomain. Given a par- tition into subdomains, the question is how many test cases should be used for each subdomain and where in the sub- domain these test cases should be cho- sen. The answers to these questions are based on assumptions about the where- abouts of errors. However, theoretical studies have proved that testing on cer- tain sets of error-prone points can de- tect certain sets of faults in the program [Afifi et al. 1992; Clarke et al. 1989; Richardson and Clarke 1985; Zeil 1984; 1983; 1989a; 1989b; 1992].

Before considering these problems, let us first look at how to partition the behavior space.

4.1 Specification-Based Input Space Partitioning

The software input space can be parti- tioned either according to the program or the specification. When partitioning the input space according to the specifi- cation, we consider a subset of data as a subdomain if the specification requires the same function on the data.

For example, consider the following specification of a module DISCOUNT INVOICE, from Hall and Hierons [1991].

Example 4.1 (Informal Specification of DISCOUNT INVOICE Module). A company produces two goods, X and Y, with prices £5 for each X purchased and £10 for each Y purchased. An order consists of a request for a certain num- ber of Xs and a certain number of Ys. The cost of the purchase is the sum of the costs of the individual demands for the two products discounted as ex- plained in the following. If the total is greater than £200, a discount of 5% is given; if the total is greater than £1,000, a discount of 20% is given; also, the company wishes to encourage sales of X and give a further discount of 10% if more than thirty Xs are ordered. Nonin- teger final costs are rounded down to give an integer value.

When the input x and y to the module DISCOUNT INVOICE has the property that x # 30 and 5*x 1 10* y # 200, the output should be 5*x 1 10*y. That is, for all the data in the subset {(x, y) u x # 30, 5*x 1 10*y # 200}, the re- quired computation is the same function sum 5 5*x 1 10*y. Therefore the sub- set should be one subdomain. A careful analysis of the required computation will give the following partition of the input space into six subdomains, as shown in Figure 5.

It seems that there is no general me- chanically applicable method to derive partitions from specifications, even if there is a formal functional specifica- tion. However, systematic approaches to analyzing formal functional specifica- tions and deriving partitions have been

398 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

proposed by a number of researchers, such as Stocks and Carrington [1993]. In particular, for formal specifications in certain normal forms, the derivation of partitions is possible. Hierons [1992] developed a set of transformation rules to transform formal functional specifica- tions written in pre/postconditions into the following normal form.

P1~ x1 , x2 , . . . , xn!

∧ Q1~ x1 , x2 , . . . , xn , y1 , y2 , . . . , ym! ∨

P2~ x1 , x2 , . . . , xn!

∧ Q2~ x1 , x2 , . . . , xn , y1 , y2 , . . . , ym! ∨

· · ·

PK~ x1 , x2 , . . . , xn!

∧ QK~ x1 , x2 , . . . , xn , y1 , y2 , . . . , ym! ∨

where Pi(x1, x2, . . . , xn), i 5 1, 2, . . . , K, are preconditions that give the condi- tion on the valid input data and the state before the operation. Qi(x1, x2, . . . , xn, y1, y2, . . . , ym), i 5 1, 2, . . . , K, are postconditions that specify the relationship between the input data, output data, and the states before and after the operation. The variables xi are input variables and yi are output vari- ables.

The input data that satisfy a precon- dition predicate Pi should constitute a subdomain. The corresponding compu- tation on the subdomain must satisfy the postcondition Qi. The precondition predicate is called the subdomain’s do- main condition. When the domain con- dition can be written in the form of the conjunction of atomic predicates of in- equality, such as

exp1~ x1 , x2 , . . . , xn!

# expr~ x1 , x2 , . . . , xn! (4.1)

exp1~ x1 , x2 , . . . , xn!

, expr~ x1 , x2 , . . . , xn!, (4.2)

then the equation

exp1~ x1 , x2 , . . . , xn!

5 expr~ x1 , x2 , . . . , xn! (4.3)

defines a border of the subdomain.

Example 4.2 (Formal specification of the DISCOUNT INVOICE module). For the DISCOUNT INVOICE module, a formal specification can be written as follows.

~ x $ 0 ∧ y $ 0! f ~sum 5 5x 1 10y!

~sum # 200! f ~discount1 5 100!

Figure 5. Partition of input space of DISCOUNT INVOICE module.

Test Coverage and Adequacy • 399

ACM Computing Surveys, Vol. 29, No. 4, December 1997

~sum . 200! ∧ ~sum # 1000!

f ~discount1 5 95!

~sum . 1000! f ~discount1 5 80!)

~ x # 30! f ~discount2 5 100!

~ x . 30! f ~discount2 5 90!

~total 5 round~sum z discount1

z discount2/10000!!,

where round is the function that rounds down a real number to an integer value; x is the number of product X that a customer ordered; y is the number of product Y that the customer ordered; sum is the cost of the order before dis- count; discount1, discount2 are the per- centages of the first and second type of discount, respectively; and total is the grand total cost of the purchase.

When this specification is trans- formed into the normal form, we have a clause with the following predicate as precondition.

~ x $ 0! & ~ y $ 0! & ~sum # 200!

& not~sum . 200 & sum # 1000!

& not~sum . 1000! & ~ x # 30!

& not ~ x . 30!

and the following predicate as the corre- sponding postcondition,

~discount1 5 100! & ~discount2 5 100!

& ~total 5 round~sumpdiscount1

pdiscount2/10000!!.

The precondition defines the region A in the partition shown in Figure 5. It is equivalent to

~ x $ 0! & ~ y $ 0! & ~sum # 200!

& ~ x # 30!. (4.4)

Since sum 5 5*x 1 10*y, the borders of the region are the lines defined by the following four equations:

x 5 0, y 5 0, x 5 30,

5*x 1 10*y 5 200.

They are the x axis, the y axis, the borders a and g in Figure 5, respec- tively.

Notice that the DISCOUNT INVOICE module has two input variables. Hence the border equations should be under- stood as lines in a two-dimensional plane as in Figure 5. Generally speak- ing, the number of input variables is the dimension of the input space. A border of a subdomain in a K-dimensional space is a surface of K 2 1 dimension.

4.2 Program-Based Input-Space Partitioning

The software input space can also be partitioned according to the program. In this case, two input data belong to the same subdomain if they cause the same “computation” of the program. Usually, the same execution path of a program is considered as the same computation. Therefore, the subdomains correspond to the paths in the program. When the program contains loops, a particular subset of the paths is selected according to some criterion, such as those dis- cussed in Section 2.1.

Example 4.3 Consider the following program, which implements the DIS- COUNT INVOICE.

Program DISCOUNT_INVOICE (x, y: Int)

Var discount1, discount2: Int; input (x, y); if x # 30 then discount2 : 5 100 else discount2 : 5 90 endif; sum : 5 5*x 1 10*y; if sum # 200 then discount1 : 5 100 elseif sum # 1000

400 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

then discount1 : 5 95 else discount1 : 5 80 endif; output (round(sum*discount1 *discount2/10000))

end

There are six paths in the program; see Figure 6 for its flow graph. For each path there is a condition on the input data such that an input causes the exe- cution of the path if and only if the condition is satisfied. Such a condition is called the path condition, and can be derived mechanically by, say, symbolic execution [Girgis 1992; Howden 1977; 1978; Liu et al. 1989; Young and Taylor 1988]. Therefore, path conditions char- acterize the subdomains (i.e., they are domain conditions). Table II gives the path conditions of the paths.

Notice that, for the DISCOUNT IN- VOICE example, partitioning according to program paths is different from the partitioning according to specification. The borders of the x axis and the y axis

are missing in the partitioning accord- ing to the program.

Now let us return to the questions about where and how many test cases should be selected for each subdomain. If only one test case is required and if we do not care about the position of the test case in the subdomain, then the test adequacy is equivalent to path cov- erage provided that the input space is partitioned according to program paths. But error-based testing requires test cases selected not only within the sub- domains, but also on the boundaries, at vertices, and just off the vertices or the boundaries in each of the adjacent sub- domains, because these places are tradi- tionally thought to be error-prone. A test case in the subdomain is called an on test point; a test case that lies out- side the subdomain is called an off test point.

This answer stems from the classifica- tion of program errors into two main types: domain error and computation

Figure 6. Flow graph of DISCOUNT INVOICE program.

Test Coverage and Adequacy • 401

ACM Computing Surveys, Vol. 29, No. 4, December 1997

error. Domain errors are those due to the incorrectness in a program’s selec- tion of boundaries for a subdomain. Computation errors are those due to the incorrectness of the implementation of the computation on a given subdomain. This classification results in two types of domain testing. The first aims at the correctness of the boundaries for each subdomain. The second is concerned with the computation on each subdo- main. The following give two sets of criteria for these two types of testing.

4.3 Boundary Analysis

White and Cohen [1980] proposed a test method called N 3 1 domain-testing strategy that requires N test cases to be selected on the borders in an N-dimen- sional space and one test case just off the border. This can be defined as the following adequacy criterion.

Definition 4.1 (N 3 1 Domain Ad- equacy). Let {D1, D2, . . . , Dn} be the set of subdomains of software S that has N input variables. A set T of test cases is said to be N 3 1 domain-test adequate if, for each subdomain Di, i 5 1, 2, . . . , n, and each border B of Di, there are at least N test cases on the border B and at least one test case which is just off the border B. If the border is in the domain Di, the test case off the border should be an off test point, otherwise, the test case off the border should be an on test point.

An adequacy criterion stricter than N 3 1 adequacy is the N 3 N criterion, which requires N test cases off the bor- der rather than only one test case off the border. Moreover, these N test cases are required to be linearly independent [Clarke et al. 1982].

Definition 4.2 (N 3 N Domain Ad- equacy). Let {D1, D2, . . . , Dn} be the set of subdomains of software S that has N input variables. A set T of test cases is said to be N 3 N domain-test adequate if, for each subdomain Di, i 5 1, 2, . . . , n, and each border B of Di, there are at least N test cases on the border B and at least N linearly inde- pendent test cases just off the border B. If the border B is in the domain Di, the N test cases off the border should be off test points, otherwise they should be on test points.

The focal point of boundary analysis is to test if the borders of a subdomain are correct. The N 3 1 domain-ade- quacy criterion aims to detect if there is an error of parallel shift of a linear border, whereas the N 3 N domain- adequacy is able to detect parallel shift and rotation of linear borders. This is why the criteria select the specific posi- tion for the on and off test cases. Con- sidering that the vertices of a subdo- main are the points at the intersection of several borders, Clark et al. [1982] suggested the use of vertices as test cases to improve the efficiency of bound-

Table II. Paths and Path Conditions

402 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

ary analysis. The criterion requires that the vertices are chosen as test cases and that for each vertex a point close to the vertex is also chosen as a test case.

Definition 4.3 (V 3 V Domain Ad- equacy). Let {D1, D2, . . . , Dn} be the set of subdomains of software S. A set T of test cases is said to be V 3 V domain- test adequate if, for each subdomain Di, i 5 1, 2, . . . , n, T contains the vertices of Di and for each vertex v of Di there is a test case just off the vertex v. If a vertex v of Di is in the subdomain Di, then the test case just off v should be an off test point; otherwise it should be an on point.

The preceding criteria are effective for detection of errors in linear domains, where a domain is a linear domain if its borders are linear functions. For nonlin- ear domains, Afifi et al. [1992] proved that the following criteria were effective for detecting linear errors.

Definition 4.4 (N 1 2 Domain Ad- equacy). Let {D1, D2, . . . , Dn} be the set of subdomains of software S that has N input variables. A set T of test cases is said to be N 1 2 domain-test adequate if, for each subdomain Di, i 5 1, 2, . . . , n, and each border B of Di, there are at least N 1 2 test cases x1, x2, . . . , xN12 in T such that

—each set of (N 1 1) test cases are in general position, where a set {xW i} con- taining N 1 1 vectors is in general position if the N vectors xW i 2 xW 1, i 5 2, 3, . . . , N 1 1, are linear-indepen- dent;

—there is at least one on test point and one off test point;

—for each pair of test cases, if the two points are of the same type (in the sense that both are on test points or both are off test points), they should lie on the opposite sides of the hyper- plane formed by the other n test points; otherwise they should lie on the same side of the hyperplane formed by the other n test points.

By applying Zeil’s [1984; 1983] work on error spaces (see also the discussion of perturbation testing in Section 3.4), Afifi et al. [1992] proved that any test set satisfying the N 1 2 domain-ade- quacy criterion can detect all linear er- rors of domain borders. They also pro- vided a method of test-case selection to satisfy the criterion consisting of the following four steps.

(1) Choose (N 1 1) on test points in general position; the selection of these points should attempt to spread them as far from one another as possible and put them on or very close to the border.

(2) Determine the open convex region of these points.

(3) If this region contains off points, then select one.

(4) If this region has no off points, then change each on point to be an off point by a slight perturbation; now there are N 1 1 off points and there is near certainty of finding an on point in the new open convex region.

4.4 Functional Analysis

Although boundary analysis focuses on border location errors, functional analy- sis emphasizes the correctness of com- putation on each subdomain. To see how functional analysis works, let us take the DISCOUNT INVOICE module as an example again.

Example 4.4 Consider region A in Figure 5. The function to be calculated on this subdomain specified by the spec- ification is

total 5 5*x 1 10*y. (4.5)

This can be written as f(x, y) 5 5x 1 10y, a linear function of two variables. Mathematically speaking, two points are sufficient to determine a linear function, but one point is not. Therefore at least two test cases must be chosen in the subdomain. If the program also com- putes a linear function on the subdo- main and produces correct outputs on

Test Coverage and Adequacy • 403

ACM Computing Surveys, Vol. 29, No. 4, December 1997

the two test cases, then we can say that the program computes the correct func- tion on the subdomain.

Analyzing the argument given in the preceding example, we can see that functional analysis is based on the fol- lowing assumptions. First, it assumes that for each subdomain there is a set of functions Ff associated with the do- main. In the preceding example, Ff con- sists of linear functions of two variables. Second, the specified computation of the software on this domain is considered as a function f *, which is an element of Ff. Third, it is assumed that the function f computed by the software on the subdo- main is also an element of Ff. Finally, there is a method for selecting a finite number of test cases for f * such that if f and f * agree on the test cases, then they are equivalent.

In Section 3.4, we saw the use of an error space in defining the neighbor- hood set Ff and the use of perturbation testing in detecting computation errors [Zeil 1984; 1983].

In Howden’s [1978; 1987] algebraic testing, the set of functions associated with the subdomain is taken as the polynomials of degree less than or equal to k, where k is chosen as the degree of the required function, if it is a polyno- mial. The following mathematical theo- rem, then, provides a guideline for the selection of test cases in each subdo- main [Howden, 1987].

THEOREM 4.1 Suppose that F contains all multinomials in n variables x1, x2, . . . , xn of degree less than or equal to k, and f, f * [ F. Let f(x1, x2, . . . , xn) 5 (i51

(k11)n aiti(x1, x2, . . . , xn), where ti(x1, x2, . . . , xn) 5 x1

i1x2 i2, . . . , xn

in, 0 # i1, i2, . . . , in # k. Then f and f * are identical if they agree on any set of m 5 (k 1 1)n values {^ci,1, ci,2, . . . , ci,n& u i 5 1, 2, . . . , m} such that the matrix M 5 [bij] is nonsingular, where bij 5 ti (cj,1, cj,2, . . . , cj,n).

Definition 4.5 (Functional Adequacy) [Howden 1978; 1987]. Let {D1, D2, . . . , Dn} be the set of subdomains of

software S. Suppose that the required function on subdomain Di is a multino- mial in m variables of degree ki, i 5 1, 2, . . . , n. A set T of test cases is said to be functional-test adequate if, for each subdomain Di, i 5 1, 2, . . . , n, T contains at least (ki 1 1)

m test cases cj 5 ^cj,1, cj,2, . . . , cj,m& in the subdo- main Di such that the matrix T 5 [bij] is nonsingular, where bij 5 ti (cj,1, cj,2, . . . , cj,m), and ti is the same as in the preceding theorem.

4.5 Summary of Domain-Analysis and Error-Based Test Adequacy Criteria

The basic idea behind domain analysis is the classification of program errors into two types: computation errors and domain errors. A computation error is reflected by an incorrect function com- puted by the program. Such an error may be caused, for example, by the exe- cution of an inappropriate assignment statement that affects the function com- puted within a path in the program. A domain error may occur, for instance, when a branch predicate is expressed incorrectly or an assignment statement that affects a branch predicate is wrong, thus affecting the conditions under which the path is selected. A boundary- analysis adequacy criterion focuses on the correctness of the boundaries, which are sensitive to domain errors. A func- tional-analysis criterion focuses on the correctness of the computation, which is sensitive to computation errors. They should be used in a complementary fashion.

It is widely recognized that software testing should take both specification and program into account. A way to combine program-based and specifica- tion-based domain-testing techniques is first to partition the input space using the two methods separately and then refine the partition by intersection of the subdomains [Gourlay 1983; Weyuker and Ostrand 1980; Richardson and Clarke 1985]. Finally, for each sub- domain in the refined partition, the re- quired function and the computed func-

404 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

tion are checked to see if they belong to the same set of functions, say, polyno- mials of degree K, and the test cases are selected according to the set of functions to which they belong.

A limitation of domain-analysis tech- niques is that they are too complicated to be applicable to software that has a complex input space. For example, pro- cess control software may have se- quences of interactions between the software and the environment system. It may be difficult to partition the input space into subdomains.

Another shortcoming of boundary- analysis techniques is that they were proposed for numerical input space such that the notions of the closeness of two points in the V 3 V adequacy, and “just off a border” in the N 3 N and N 3 1 adequacy can be formally defined. How- ever, it is not so simple to extend these notions to nonnumerical software such as compilers.

5. COMPARISON OF TEST DATA ADEQUACY CRITERIA

Comparison of testing methods has al- ways been desirable. It is notoriously difficult because testing methods are defined using different models of soft- ware and based on different theoretical foundations. The results are often con- troversial.

In comparing testing adequacy crite- ria, it must be made very clear in what sense one criterion is better than an- other. There are three main types of such measures in the software testing literature: fault-detecting ability, soft- ware reliability, and test cost. This sec- tion reviews the methods and the main results of the comparisons.

5.1 Fault-Detecting Ability

Fault-detecting ability is one of the most direct measures of the effective- ness of test adequacy criteria [Basili and Selby 1987; Duran and Ntafos 1984; Frankl and Weiss 1993; Frankl and Weyuker 1988; Ntafos 1984;

Weyuker and Jeng 1991; Woodward et al. 1980]. The methods to compare test adequacy criteria according to this mea- sure can be classified into three types: statistical experiment, simulation, and formal analysis. The following summa- rizes research in these three ap- proaches.

5.1.1 Statistical Experiments. The basic form of statistical experiments with test adequacy criteria is as follows.

Let C1, C2, . . . , Cn be the test ade- quacy criteria under comparison. The experiment starts with the selection of a set of sample programs, say, P1, P2, . . . , Pm. Each program has a collec- tion of faults that are known due to previous experience with the software, or planted artificially, say, by applying mutation operations. For each program Pi, i 5 1, 2, . . . , m, and adequacy criterion Cj, j 5 1, 2, . . . , n, k test sets Ti1

j , Ti2 j , . . . , Tik

j are generated in some fashion so that Tiu

j is adequate to test program Pi according to the criterion Cj. The proportion of faults riu

j detected by the test set Tiu

j over the known faults in the program Pi is calculated for every i 5 1, 2, . . . , n, j 5 1, 2, . . . , m, and u 5 1, 2, . . . , k. Statistical inferences are then made based on the data riu

j , i 5 1, . . . , n, j 5 1, . . . , m, u 5 1, 2, . . . , k.

For example, Ntafos [1984] compared branch coverage, random testing, and required pair coverage. He used 14 small programs. Test cases for each pro- gram were selected from a large set of random test cases and modified as needed to satisfy each of the three test- ing strategies. The percentages of mu- tants killed by the test sets were consid- ered the fault-detection abilities.

Hamlet [1989] pointed out two poten- tial invalidating factors in this method. They are:

(1) A particular collection of programs must be used—it may be too small or too peculiar for the results to be trusted.

(2) Particular test data must be created for each method—the data may have

Test Coverage and Adequacy • 405

ACM Computing Surveys, Vol. 29, No. 4, December 1997

good or bad properties not related to the testing method.

Hamlet [1989] was also critical: “It is not unfair to say that a typical testing experiment uses a small set of toy pro- grams, with uncontrolled human gener- ation of the test data. That is, neither (1) nor (2) is addressed.”

In addition to these two problems, there is, in fact, another potential inval- idating factor in the method. That is:

(3) A particular collection of known faults in each program must be used—it may not be representative of the faults in software. The faults could be too easy or too difficult to find, or there could be a different distribution of the types of faults. One particular test method or ade- quacy criterion may have a better ability to detect one type of fault than other types.

To avoid the effects of the potential invalidating factors related to the test data, Basili and Selby [1987] used frac- tional factorial design methodology of statistical experiments and repeated ex- perimentation. They compared two dy- namic testing methods (functional test- ing and statement coverage) and a static testing method (code review) in three iterative phases involving 74 sub- jects (i.e., testers) of various back- grounds. However, they only used four sample programs. The faults contained in the sample programs include those made during the actual development of the program as well as artificial faults. Not only the fault-detection ability, but also the fault-detection cost with re- spect to various classes of faults were compared. Since the test sets for dy- namic testing are generated manually and the static testing is performed man- ually, they also made a careful compar- ison of human factors in testing. Their main results were:

—Human factors. With professional programmers, code reading detected more software faults and yielded a

higher fault-detection rate than func- tional or structural testing did. Al- though functional testing detected more faults than structural testing did, functional testing and structural testing did not differ in fault-detec- tion rate. In contrast, with advanced students, the three techniques were not different in fault-detection rate.

—Software type. The number of faults observed, fault-detection rate, and to- tal effort in software testing all clearly depended on the type of soft- ware under test.

—Fault type. Different testing tech- niques have different fault-detection abilities for different types of faults. Code reading detected more interface faults than the other methods did, and functional testing detected more control faults than the other methods did.

Their experiment results indicated the complexity of the task of comparing software testing methods.

Recently, Frankl and Weiss [1993] used another approach to addressing the potential invalidating factor associ- ated with the test data. They compared branch adequacy and all-uses data-flow adequacy criteria using nine small pro- grams of different subjects. Instead of using one adequate test set for each criterion, they generated a large num- ber of adequate test sets for each crite- rion and calculated the proportion of the test sets that detect errors as an esti- mate of the probability of detecting er- rors. Their main results were:

—for five of the nine subjects, the all- uses criterion was more effective than branch coverage at 99% confidence, where the effectiveness of an ade- quacy criterion is the probability that an adequate test set exposes an error when the test set is selected randomly according to a given distribution on the adequate test sets of the criterion.

—in four of the nine subjects, all-uses adequate test sets were more effective

406 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

than branch-coverage adequate sets of similar size.

—for the all-uses criterion, the probabil- ity of detecting errors clearly depends on the extent of the adequacy only when the adequacy is very close to 100% (i.e., higher than 97%). In four of the subjects, such a dependence existed for the branch-coverage crite- rion over all the adequacy range.

The advantage of the statistical experi- ment approach is that it is not limited to comparing adequacy criteria based on a common model. However, given the potential invalidating factors, it is doubtful that it is capable of producing trustworthy results on pairs of ade- quacy criteria with subtle differences.

5.1.2 Simulation. Both simulation and formal analysis are based on a cer- tain simplified model of software test- ing. The most famous research that uses simulation for comparing software test adequacy criteria are Duran and Ntafos’ [1984] comparison of partition testing with random testing and Hamlet and Taylor’s [1990] repetition of the comparison.

Duran and Ntafos modeled partition testing methods by a finite number of disjoint subsets of software input spaces. Suppose that the input space D of a given software system is par- titioned into k disjoint subsets D1, D2, . . . , Dk and an input chosen at random has probability pi of lying in Di. Let ui be the failure rate for Di, then

u 5 O i51

k

piui (5.1)

is the probability that the program will fail to execute correctly on an input chosen at random in accordance with the input distribution. Duran and Ntafos investigated the probability that a test set will reveal one or more errors and the expected number of errors that

a set of test cases will discover.6 For random testing, the probability Pr of finding at least one error in n tests is 1 2 (1 2 u)n. For a partition testing method in which ni test cases are cho- sen at random from subset Di, the prob- ability Pp of finding at least one error is given by

Pp 5 1 2 P i51

k

~1 2 ui! ni. (5.2)

With respect to the same partition,

Pr 5 1 2 ~1 2 u ! n

5 1 2 S 1 2 O i51

k

piuiD n, where n 5 O

i51

k

ni . (5.3)

The expected number Ep of errors dis- covered by partition testing is given by

Ep~k! 5 O i51

k

ui (5.4)

if one random test case is chosen from each Di, where ui is the failure rate for Di.

If in total n random test cases are used in random testing, some set of actual values n 5 {n1, n2, . . . , nk} will occur, where ni is the number of test cases that fall in Di. If n were known, then the expected number of errors found would be

E~n, k, n! 5 O i51

k

~1 2 ~1 2 ui! ni!. (5.5)

6 Note that an error means that the program’s output on a specific input does not meet the specification of the software.

Test Coverage and Adequacy • 407

ACM Computing Surveys, Vol. 29, No. 4, December 1997

Since n is not known, the expected number Er of errors found by n random tests is

Er~k, n! 5 O n S E~n, k, n! z n!

z S P i51

k

pi niY P

i51

k

niDD 5 k 2 O i51

k

~1 2 piui! n.

(5.6)

They conducted simulations of vari- ous program conditions in terms of ui distributions and K, and calculated and compared the values of Pp, Pr, Ep, and Er. Two types of ui distributions were investigated. The first type, called hypo- thetical distributions, considered the situation where a test case chosen from a subset would have a high probability of finding an error affecting that subset. Therefore the uis were chosen from a distribution such that 2 percent of the time ui $ 0.98 and 98 percent of the time, ui , 0.049. The second type of ui distribution was uniform distributions; that is, the uis were allowed to vary uniformly from 0 to a value umax that varies from 0.01 to 1.

The main result of their simulation was that when the fault-detecting abil- ity of 100 simulated random test cases was compared to that of 50 simulated partition test cases, random testing was superior. This was considered as evi- dence to support one of the main conclu- sions of the paper, that random testing would be more cost-effective than parti- tion testing, because performing 100 random tests was considered less expen- sive than 50 partition tests.

Considering Duran and Ntafos’ result counterintuitive, Hamlet and Taylor [1990] did more extensive simulation and arrived at more precise statements about the relationship between parti- tion probabilities, failure rates, and ef- fectiveness. But their results corrobo- rated Duran and Ntafos’ results.

In contrast to statistical experiment,

imulation can be performed in an ideal testing scenario to avoid some of the complicated human factors. However, because simulation is based on a certain simplified model of software testing, the realism of the simulation result could be questionable. For example, in Duran and Ntafos’ experiment, the choice of the particular hypothetical distribution (i.e., for 2 percent of the time ui $ 0.98 and for 98 percent of the time ui , 0.049) seems rather arbitrary.

5.1.3 Formal Analysis of the Relation- ships among Adequacy Criteria. One of the basic approaches to comparing adequacy criteria is to define some rela- tion among adequacy criteria and to prove that the relation holds or does not hold for various pairs of criteria. The majority of such comparisons in the lit- erature use the subsume ordering, which is defined as follows.

Definition 5.1 (Subsume Relation among Adequacy Criteria). Let C1 and C2 be two software test data adequacy criteria. C1 is said to subsume C2 if for all programs p under test, all specifica- tions s and all test sets t, t is adequate according to C1 for testing p with re- spect to s implies that t is adequate according to C2 for testing p with re- spect to s.

Rapps and Weyuker [1985] studied the subsume relation among their origi- nal version of data-flow adequacy crite- ria, which were not finitely applicable. Frankl and Weyuker [1988] later used this relation to compare their revised feasible version of data-flow criteria. They found that feasibility affects the subsume relation among adequacy crite- ria. In Figure 7, the subsume relation that holds for the infeasible version of criteria but does not hold for the feasi- ble version of the criteria is denoted by an arrow marked with the symbol “*”. Ntafos [1988] also used this relation to compare all the data-flow criteria and several other structural coverage crite- ria. Among many other works on com- paring testing methods by subsume re-

408 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

lation are those by Weiser et al. [1985] and Clark et al. [1989]. Since the ade- quacy criteria based on flow analysis have a common basis, most of them can be compared; they fall into a fairly sim- ple hierarchy, as shown in Figure 7. A relatively complete picture of the rela- tions among test adequacy criteria can be built. However, many methods are incomparable; that is, one does not sub- sume the other.

The subsume relation is actually a comparison of adequacy criteria accord- ing to the severity of the testing meth- ods. The subsume relation evaluates ad- equacy criteria in their own terms, without regard for what is really of in- terest. The relation expresses nothing about the ability to expose faults or to assure software quality. Frankl and

Weyuker [1993a] proved that the fact that C1 subsumes C2 does not always guarantee that C1 is better at detecting faults.

Frankl and Weyuker investigated whether a relation on adequacy criteria can guarantee better fault-detecting ability for subdomain testing methods. The testing methods they considered are those by which the input space is divided into a multiset of subspaces so that in each subspace at least one test case is required. Therefore a subdomain test adequacy criterion is equivalent to a function that takes a program p and a specification s and gives a multiset7

{D1, D2, . . . , Dk} of subdomains. They

7 In a multiset an element may appear more than once.

Figure 7. Subsume relation among adequacy criteria.

Test Coverage and Adequacy • 409

ACM Computing Surveys, Vol. 29, No. 4, December 1997

defined a number of partial orderings on test adequacy criteria and studied whether these relations are related to the ability of fault detection. The follow- ing are the relations they defined, which can be regarded as extensions of the subsume relation.

Definition 5.2 (Relations among Test Adequacy Criteria). Let C1 and C2 be two subdomain test adequacy criteria and pc1(p, s) and pc2(p, s) be the multi- set of the subsets of the input space for a program p and a specification s ac- cording to C1 and C2, respectively.

—C1 narrows C2 for (p, s) if for every D [ pC2(p, s), there is a subdomain D9 [ pC1(p, s) such that D9 # D.

—C1 covers C2 for ( p, s) if for every D [ pC2( p, s), there is a nonempty collec- tion of subdomains {D1, D2, . . . , Dn} belonging to pC1( p, s) such that D1 ø D2 ø . . . Dn 5 D.

—C1 partitions C2 for ( p, s) if for every D [ pC2( p, s), there is a nonempty collection of pairwise disjoint subdo- mains {D1, D2, . . . , Dn} belonging to pC1( p, s) such that D1 ø D2 ø . . . ø Dn 5 D.

—Let pC1( p, s) 5 {D1, D2, . . . , Dm}, pC2( p, s) 5 {E1, E2, . . . , En}. C1

properly covers C2 for ( p, s) if there is a multiset M 5 {D1,1, D1,2, . . . , D1,k1, . . . , Dn,1, . . . , Dn,kn} # pC1( p, s) such that Ei 5 Di,1 ø Di,2 ø . . . ø Di,ki for all i 5 1, 2, . . . , n.

—Let pC1( p, s) 5 {D1, D2, . . . , Dm}, pC2( p, s) 5 {E1, E2, . . . , En}. C1 properly partitions C2 for ( p, s) if there is a multiset M 5 {D1,1, . . . , D1,k1, . . . , Dn,1, . . . , Dn,kn} # pC1( p, s) such that Ei 5 Di,1 ø Di,2 ø . . . ø Di,ki for all i 5 1, 2, . . . , n, and for each i 5 1, 2, . . . , n, the collection {Di,1, . . . , Di,ki} is pairwise disjoint.

For each relation R previously defined, Frankl and Weyuker defined a stronger relation, called universal R, which re- quires R to hold for all specifications s and all programs p. These relations have the relationships shown in Figure 8.

To study fault-detecting ability, Frankl and Weyuker considered two idealized strategies for selecting the test cases. The first requires the tester to independently select test cases at random from the whole input space ac- cording to a uniform distribution until the adequacy criterion is satisfied. The second strategy assumes that the input space has first been divided into subdo-

Figure 8. Relationships among partial orderings on adequacy criteria.

410 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

mains and then requires independent random selection of a predetermined number n of test cases from each subdo- main. They used three different mea- sures, M1, M2, and M3 in the following definition of fault-detecting ability. In a later paper Frankl and Weyuker [1993b] also studied the expected num- ber of errors detected by a test method. This measure is E(C, p, s) in the follow- ing definition. Notice that these mea- sures are the same as those used by Duran and Ntafos [1984] except ui is replaced by mi/di; see also Section 5.1.2.

Definition 5.3 (Measures of Fault-De- tection Ability). Let pc(p, s) 5 {D1, D2, . . . , Dk} be the multiset of the subdo- mains of the input space of (p, s) ac- cording to the criterion C, di 5 uDiu, and mi be the number of fault-causing in- puts in Di, i 5 1, . . . , k. Define:

M1~C, p, s! 5 max 1#i#k

Smi di D (5.7)

M2~C, p, s! 5 1 2 P i51

k S1 2 mi di D (5.8)

M3~C, p, s, n! 5 1 2 P i51

k S1 2 mi di Dn, (5.9)

where n $ 1 is the number of test cases in each subdomain.

E~C, p, s! 5 O i51

k mi di

. (5.10)

According to Frankl and Weyuker, the first measure M1(C, p, s) gives a crude lower bound on the probability that an adequate test set selected using either of the two strategies will expose at least one fault. The second measure M2(C, p, s) gives the exact probability that a test set chosen by using the first sampling strategy will expose at least one fault. M3(C, p, s, n) is a generalization of M2 by taking the number n of test cases selected in each subdomain into ac- count. It should be noted that M2 and M3 are special cases of Equation (5.2) for Pp in Duran and Ntafos’ work that ni 5 1 and ni 5 n, respectively. It is obvious that M2 and M3 are accurate only for the first sampling strategy be- cause for the second strategy it is un- reasonable to assume that each subdo- main has exactly n random test cases.

Frankl and Weyuker [1993a,b] proved that different relations on the adequacy criteria do relate to the fault-detecting ability. Table III summarizes their re- sults.

Given the fact that the universal nar- rows relation is equivalent to the sub- sume relation for subdomain testing methods, Frankl and Weyuker con- cluded that “C1 subsumes C2” does not guarantee a better fault-detecting abil- ity for C1. However, recently Zhu [1996a] proved that in certain testing scenarios the subsumes relation can im- ply better fault-detecting ability. He identified two software testing scenar- ios. In the first scenario, a software tester is asked to satisfy a particular adequacy criterion and generates test

Table III. Relationships among Fault-Detecting Ability and Orderings on Adequacy Criteria (ki, i 5 1, 2, is the number of subdomains in pCi(p, s))

Test Coverage and Adequacy • 411

ACM Computing Surveys, Vol. 29, No. 4, December 1997

cases specifically to meet the criterion. This testing scenario is called the prior testing scenario. Frankl and Weyuker’s second sampling strategy belongs to this scenario. In the second scenario, the tester generates test cases without any knowledge of test adequacy crite- rion. The adequacy criterion is only used as a stopping rule so that the tester stops generating test cases only if the criterion is satisfied. This scenario is called posterior testing scenario. Frankl and Weyuker’s first sampling strategy belongs to the posterior sce- nario. It was proved that in the poste- rior testing scenario, the subsume rela- tion does imply better fault-detecting ability in all the probability measures for error detection and for the expected number of errors. In the posterior test- ing scenario, the subsume relation also implies more test cases [Zhu 1996a].

Frankl and Weyuker [1993b] also in- vestigated how existing adequacy crite- ria fit into the partial orderings. They studied the properly cover relation on a subset of data-flow adequacy criteria, a limited mutation adequacy (which is ac- tually branch coverage), and condition coverage. The results are shown in Fig- ure 9.

5.2 Software Reliability

The reliability of a software system that has passed an adequate test is a direct measure of the effectiveness of test ade- quacy criteria. However, comparing test adequacy criteria with respect to this measure is difficult. There is little work of this type in the literature. A recent breakthrough is the work of Tsoukalas et al. [1993] on estimation of software reliability from random testing and par- tition testing.

Motivated to explain the observations made in Duran and Ntafos’ [1984] ex- periment on random testing and parti- tion testing, they extended the Thayer- Lipow-Nelson reliability model [Thayer et al. 1978] to take into account the cost of errors, then compared random testing with partition testing by looking at the upper confidence bounds when estimat- ing the cost-weighted failure rate.

Tsoukalas et al. [1993] considered the situation where the input space D is partitioned into k pairwise disjoint sub- sets so that D 5 D1 ø D2 ø . . . ø Dk. On each subdomain Di, there is a cost penalty ci that would be incurred by the program’s failure to execute properly on an input from Di, and a probability pi

Figure 9. Universally properly cover relation among adequacy criteria.

412 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

that a randomly selected input will be- long to Di. They defined the cost- weighted failure rate for the program as a whole as

C 5 O i51

k

ci piui . (5.11)

Usually, the cost-weighted failure rate is unknown in advance, but can be esti- mated by

C < O i51

k

ci pi~ fi/ni!, (5.12)

where fi is the number of failures ob- served over Di and ni is the number of random test cases within the subdo- main Di. Given the total number n of test cases, Equation (5.13) gives the maximum likelihood estimate of the cost-weighted failure rate C.

C < O i51

k

cifi/n (5.13)

But Tsoukalas et al. [1993] pointed out that the real issue is how confident one can be in the estimate. To this end they sought an upper confidence bound on C. Therefore, considering finding the upper bound as a linear programming problem that maximizes (i51

k cipiui subject to cer- tain conditions, they obtained expressions for the upper bounds in the two cases of random testing and partition testing and calculated the upper bounds for various special cases.

The conclusion was that confidence is more difficult to achieve for random testing than for partition testing. This agrees with the intuition that it should be easier to have a certain level of con- fidence for the more systematic of the two testing methods. That is, it is easier to put one’s faith in partition testing. But they also confirmed the result of the empirical studies of the effective- ness of random testing by Duran and Ntafos [1984] and Hamlet and Taylor

[1990]. They showed that in some cases random testing can perform much bet- ter than partition testing, especially when only one test case is selected in each subdomain.

This work has a number of practical implications, especially for safety-criti- cal software where there is a significant penalty for failures in some subdo- mains. For example, it was proved that when no failures are detected, the opti- mum way to distribute the test cases over the subdomains in partition testing is to select ni proportional to ci pi, 0 # i # k, rather than select one test case in each subdomain.

5.3 Test Cost

As testing is an expensive software de- velopment activity, the cost of testing to achieve a certain adequacy according to a given criterion is also of importance. Comparison of testing costs involves many factors. One of the simplified measures of test cost is the size of an adequate test set. Weyuker’s [1988c, 1993] work on the complexity of data- flow adequacy criteria belongs to this category.

In 1988, Weyuker [1988c] reported an experiment with the complexity of data- flow testing. Weyuker used the suite of programs in Software Tools in Pascal by Kernighan and Plauger [1981] to estab- lish empirical complexity estimates for Rapps and Weyuker’s family of data- flow adequacy criteria. The suite con- sists of over 100 subroutines. Test cases were selected by testers who were in- structed to select “natural” and “atomic” test cases using the selection strategy of their choice, and were not encouraged to select test cases explicitly to satisfy the selected data-flow criterion. Then seven statistical estimates were computed for each criterion from the data (di, ti) where di denoted the number of deci- sion statements in program i and ti denoted the number of test cases used to satisfy the given criterion for pro- gram i. Among the seven measures, the most interesting ones are the least

Test Coverage and Adequacy • 413

ACM Computing Surveys, Vol. 29, No. 4, December 1997

squares line t 5 ad 1 b (where t is the number of test cases sufficient to satisfy the given criteria for the subject pro- gram and d is the number of decision statements in that program), and the weighted average of the ratios of the number of decision statements in a sub- ject program to the number of test cases sufficient to satisfy the selected crite- rion. Weyuker observed that (1) the co- efficients of d in the least-square lines were less than 1 for all the cases and (2) the coefficients were very close to the average number of test cases required for each decision statement. Based on these observations, Weyuker concluded that the experiment results reinforced our intuition that the relationship be- tween the required number of test cases and the program size was linear. A re- sult similar to Weyuker’s is also ob- served for the all du-paths criterion by Bieman and Schultz [1992].

The programs in the Kernighan and Plauger suite used in Weyuker’s experi- ment were essentially the same type, well designed and modularized, and hence relatively small in size. Address- ing the problem that whether substan- tially larger, unstructured and modular- ized programs would require larger amounts of test data relative to their size, Weyuker [1993] conducted another experiment with data-flow test ade- quacy criteria. She used a subset of ACM algorithms in Collected Algo- rithms from ACM (Vol. 1, ACM Press, New York, 1980) as sample programs that contained known faults and five or more decision statements. In this study, the same information was collected and the same values were calculated. The same conclusion was obtained. How- ever, in this study, Weyuker observed a large proportion of infeasible paths in data-flow testing. The average rates of infeasible paths for the all du-path cri- terion were 49 and 56% for the two groups of programs, respectively. Weyuker pointed out that the large number of infeasible paths implies that assessing the cost of data-flow testing only in terms of the number of test

cases needed to satisfy a criterion might yield an optimistic picture of the real effort needed to accomplish the testing.

Offutt et al. [1993] studied the cost of mutation testing with a sample set of 10 programs. They used simple and multi- ple linear regression models to establish a relationship among the number of generated mutants and the number of lines of code, the number of variables, the number of variable references, and the number of branches. The linear re- gression models provide a powerful ve- hicle for finding functional relationships among random variables. The coeffi- cient of determination provides a sum- mary statistic that measures how well the regression equation fits the data, and hence is used to decide whether a relationship between some data exists. Offutt et al. used a statistical package to calculate the coefficient of determina- tion of the following formulas.

Ymutant 5 b0 1 b1Xline 1 b2 Xline 2

Ymutant 5 b0 1 b1Xvar 1 b2 Xvar 2

Ymutant 5 b0 1 b1Xvar 1 b2Xvarref

1 b3Xvar Xvarref ,

where Xline is the number of lines in the program, Xvar is the number of vari- ables in the program, Xvarref is the num- ber of variable references in the pro- gram, and Ymutant is the number of mutants. They found that for single units, the coefficients of determination of the formulas were 0.96, 0.96, and 0.95, respectively. For programs of mul- tiple units, they established the follow- ing formula with a coefficient of deter- mination of 0.91.

Ymutant 5 b0 1 b1Xvar 1 b2Xvarref

1 b3Xunit 1 b4XvarXvarref ,

where Xunit is the number of units in the program. Therefore their conclusion was that the number of mutants is qua- dratic. As mentioned in Section 3, Of- futt et al. also studied the cost of selec-

414 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

tive mutation testing and showed that even for 6-selective mutation testing, the number of mutants is still qua- dratic.

5.4 Summary of the Comparison of Adequacy Criteria

Comparison of test data adequacy crite- ria can be made with respect to various measures, such as fault detection, confi- dence in the reliability of the tested software, and the cost of software test- ing. Various abstract relations among the criteria, such as the subsume rela- tion, have also been proposed and rela- tionships among adequacy criteria have been investigated. The relationship be- tween such relations and fault-detecting ability has also been studied. Recent research results have shown that parti- tion testing more easily achieves high confidence in software reliability than random testing, though random testing may be more cost-effective.

6. AXIOMATIC ASSESSMENT OF ADEQUACY CRITERIA

In Section 5, we have seen two kinds of rationale presented to support the use of one criterion or another, yet there is no clear consensus. The first kind of rationale uses statistical or empirical data to compare testing effectiveness, whereas the second type analytically compares test data adequacy criteria based on certain mathematical models of software testing.

In this section we present a third type of rationale, the axiomatic study of the properties of adequacy criteria. The ba- sic idea is to seek the most fundamental properties of software test adequacy and then check if the properties are satisfied for each particular criterion. Although the idea of using abstract properties as requirements of test ade- quacy criteria can be found in the liter- ature, such as Baker et al. [1986], Weyuker [1986, 1988a] is perhaps the first who explicitly and clearly em- ployed axiom systems. Work following

this direction includes refinement and improvement of the axioms [Parrish and Zweben 1991; 1993; Zhu and Hall 1993; Zhu et al. 1993; Zhu 1995a] as well as analysis and criticism [Hamlet 1989; Zweben and Gourlay 1989].

There are four clearcut roles that axi- omatization can play in software testing research, as already seen in physics and mathematics. First, it makes explicit the exact details of a concept or an argument that, before the axiomatiza- tion, was either incomplete or unclear. Second, axiomatization helps to isolate, abstract, and study more fully a class of mathematical structures that have re- curred in many important contexts, of- ten with quite different surface forms, so that a particular form can draw on results discovered elsewhere. Third, it can provide the scientist with a compact way to conduct a systematic exploration of the implications of the postulates. Finally, the fourth role is the study of what is needed to axiomatize a given empirical phenomenon and what can be axiomatized in a particular form. For instance, a number of computer scien- tists have questioned whether formal properties can be defined to distinguish one type of adequacy criteria from an- other when criteria are expressed in a particular form such as predicates [Hamlet 1989; Zweben and Gourlay 1989].

Therefore we believe that axiomatiza- tion will improve our understanding of software testing and clarify our notion of test adequacy. For example, as pointed out by Parrish and Zweben [1993], the investigation of the applica- bility of test data adequacy criteria is an excellent example of the role that axiomatization has played. Applicability was proposed as an axiom by Weyuker in 1986, requiring a criterion to be ap- plicable to any program in the sense of the existence of test sets that satisfy the criterion. In the assessment of test data adequacy criteria against this axiom, the data-flow adequacy criteria origi- nally proposed by Rapps and Weyuker in 1985 were found not applicable. This

Test Coverage and Adequacy • 415

ACM Computing Surveys, Vol. 29, No. 4, December 1997

leads to the redefinition of the criteria and reexamination of the power of the criteria [Frankl and Weyuker 1988]. Weyuker’s applicability requirements were defined on the assumption that the program has a finite representable input data space. Therefore any ade- quate test set is finite. When this as- sumption is removed and adequacy cri- teria were considered as measurements, Zhu and Hall [1993] used the term fi- nite applicability to denote the require- ment that for any software and any adequacy degree r less than 1 there is a finite test set whose adequacy is greater than r. They also found that finite ap- plicability can be derived from other more fundamental properties of test data adequacy criteria.

6.1 Weyuker’s Axiomatization of Program- Based Adequacy Criteria

Weyuker [1986] proposed an informal axiom system of test adequacy criteria. Her original purpose of the system was to present a set of properties of ideal program-based test adequacy criteria and use these properties to assess exist- ing criteria. Regarding test adequacy criteria as stopping rules, Weyuker’s ax- iom system consists of eleven axioms, which were later examined, formalized, and revised by Parrish and Zweben [1991; 1993].

The most fundamental properties of adequacy criteria proposed by Weyuker were those concerning applicability. She distinguished the following three appli- cability properties of test adequacy cri- teria.

AXIOM A1 (Applicability). For every program, there exists an adequate test set.

Assuming the finiteness of represent- able points in the input data space, Weyuker rephrased the axiom into the following equivalent form.

AXIOM A1 For every program, there exists a finite adequate test set.

Weyuker then analyzed exhaustive test- ing and pointed out that, although ex- haustive testing is adequate, an ade- quacy criterion should not always ask for exhaustive testing. Hence she de- fined the following nonexhaustive appli- cability.

AXIOM A2 (Nonexhaustive Applicabil- ity). There is a program p and a test set t such that p is adequately tested by t and t is not an exhaustive test set.

Notice that by exhaustive testing Weyuker meant the test set of all repre- sentable points of the specification do- main. The property of central impor- tance in Weyuker’s system is monotonicity.

AXIOM A3 (Monotonicity). If t is ade- quate for p and t # t9, then t9 is ade- quate for p.

AXIOM A4 (Inadequate Empty Set). The empty set is not adequate for any program.

Weyuker then studied the relation- ships among test adequacy and program syntactic structure and semantics. How- ever, her axioms were rather negative. They stated that neither semantic close- ness nor syntactic structure closeness are sufficient to ensure that two pro- grams require the same test data. More- over, an adequately tested program does not imply that the components of the program are adequately tested, nor does adequate testing of components imply adequate testing of the program.

Weyuker assessed some test adequacy criteria against the axioms. The main discovery of the assessment is that the mutation adequacy criterion defined in its original form does not satisfy the monotonicity and applicability axioms, because it requires a correctness condi- tion. The correctness condition requires that the program under test produces correct output on a test set if it is to be considered adequate. For all the ade- quacy criteria we have discussed, it is possible for a program to fail on a test case after producing correct outputs on

416 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

an adequate test set. Hence the correct- ness condition causes a conflict with monotonicity. The correctness condition does not play any fundamental role in mutation adequacy, so Weyuker sug- gested removal of this condition from the definition.8

Aware of the insufficiency of the ax- iom system, Weyuker [1988a] later pro- posed three additional axioms. The re- naming property requires that a test set be adequate for a program p if and only if it is adequate for a program obtained by systematic renaming variables in p. The complexity property requires that for every natural number n, there is a program p, such that p is adequately tested by a size-n test set but not by any size (n 2 1) test set. The statement coverage property requires that all ade- quate test sets cover all feasible state- ments of the program under test. These axioms were intended to rule out some “unsuitable notions of adequacy.”

Given the fact that Weyuker’s axioms are unable to distinguish most ade- quacy criteria, Hamlet [1989] and Zwe- ben and Gourlay [1989] questioned if the axiomatic approach could provide useful comparison of adequacy criteria. Recently, some of Weyuker’s axioms were combined with Baker et al.’s [1986] properties for assessing control- flow adequacy criteria [Zhu 1995a]. Control-flow adequacy criteria of subtle differences were distinguished. The as- sessment suggested that the cycle com- bination criterion was the most favor- able.

6.2 Parrish and Zweben’s Formalization and Analysis of Weyuker’s Axioms

Parrish and Zweben [1993; 1991] for- malized Weyuker’s axioms, but put them in a more general framework that involved specifications as well. They de- fined the notions of program-independent criteria and specification-independent cri- teria. A program-independent criterion

measures software test adequacy inde- pendently of the program, whereas a specification-independent criterion mea- sures software test adequacy indepen- dently of the specification. Parrish and Zweben explored the interdependence re- lations between the notions and the axi- oms. Their work illustrated the complex levels of analysis that an axiomatic the- ory of software testing can make possible. Formalization is not merely a mathemat- ical exercise because the basic notions of software testing have to be expressed pre- cisely and clearly so that they can be critically analyzed. For example, infor- mally, a program-limited criterion only requires test data selected in the domain of the program, and a specification-lim- ited criterion requires test data only se- lected in the domain of the specification. Parrish and Zweben formally defined the notion to be that if a test case falls out- side the domain, the test set is considered inadequate. This definition is counterin- tuitive and conflicts with the monotonic- ity axiom. A more logical definition is that the test cases outside the domain are not taken into account in determining test adequacy [Zhu and Hall 1993]. Parrish and Zweben [1993] also formalized the notion of the correctness condition such that a test set is inadequate if it contains a test case on which the program is incor- rect. They tried to put it into the axiom system by modifying the monotonicity ax- iom to be applied only to test sets on which the software is correct. However, Weyuker [1986] argued that the correct- ness condition plays no role in determin- ing test adequacy. It should not be an axiom.

6.3 Zhu and Hall’s Measurement Theory

Based on the mathematical theory of measurement, Zhu and Hall [1993; Zhu et al. 1993] proposed a set of axioms for the measurement of software test ade- quacy. The mathematical theory of mea- surement is the study of the logical and philosophical concepts underlying mea- surement as it applies in all sciences. It studies the conceptual structures of

8 The definition of mutation adequacy used in this article does not use the correctness condition.

Test Coverage and Adequacy • 417

ACM Computing Surveys, Vol. 29, No. 4, December 1997

measurement systems and their proper- ties related to the validation of the use of measurements [Roberts 1979; Krantz et al. 1971; Suppes et al. 1989; Luce et al. 1990]. Therefore the measurement of software test adequacy should conform to the theory. In fact, recent years have seen rapid growth of rigorous applica- tions of the measurement theory to soft- ware metrics [Fenton 1991].

According to the theory, measurement is the assignment of numbers to proper- ties of objects or events in the real world by means of an objective empirical oper- ation. The modern form of measurement theory is representational; that is, num- bers assigned to objects/events must represent the perceived relation be- tween the properties of those objects/ events. Readers are referred to Roberts’ [1979] book for various applications of the theory and Krantz et al.’s trilogy [1971; Suppes et al. 1989; Luce et al. 1990] for a systematic treatment of the subject. Usually, such a theory com- prises three main sections: the descrip- tion of an empirical relational system, a representation theorem, and a unique- ness condition.

An empirical relational system Q 5 (Q, R) consists of a set Q of manifesta- tions of the property or attribute and a family of relations R 5 {R1, R2, . . . , Rn} on Q. The family R of relations provides the basic properties of the manifestations with respect to the prop- erty to be measured. They are usually expressed as axioms derived from the empirical knowledge of the real world. For software testing, the manifestations are the software tests P 3 S 3 T, which consist of a set of programs P, a set of specifications S, and a set of test sets T. Zhu et al. [1994] defined a relation # on the space of software testing such that t1 # t2 means that test t2 is at least as adequate as t1. It was argued that the relation has the properties of reflexiv- ity, transitivity, comparability, bound- edness, equal inadequacy for empty tests, and equal adequacy for exhaus- tive tests. Therefore this relation is a

total ordering with maximal and mini- mal elements.

To assign numbers to the objects in the empirical system, a numerical sys- tem N 5 (N, G) must be defined so that the measurement mapping is a homo- morphism from the empirical system to the numerical system. It has been proved that for any numerical system (N, #N) and measurement g of test adequacy on N, there is a measurement m on the unit interval of real numbers ([0,1], #) such that g 5 t ° m, where t is an isomorphism between (N, #N) and ([0,1], #) [Zhu and Hall 1993; Zhu et al. 1994; Zhu 1995b]. Therefore properties of test adequacy measurements can be obtained by studying adequacy mea- surements on the real unit interval.

Zhu and Hall’s axiom system for ade- quacy measurements on the real unit interval consists of the following axi- oms.

AXIOM B1 (Inadequacy of Empty Test Set). For all programs p and specifica- tions s, the adequacy of the empty test set is 0.

AXIOM B2 (Adequacy of Exhaustive Testing). For all programs p and speci- fications s, the adequacy of the exhaus- tive test set D is 1.

AXIOM B3 (Monotonicity). For all pro- grams p and specifications s, if test set t1 is a subset of test set t2 , then the adequacy of t1 is less than or equal to the adequacy of t2.

AXIOM B4 (Convergence). Let t1, t2, . . . , tn, . . . [ T be test sets such that t1 # t2 # . . . # tn # . . . . Then, for all programs p and specifications s,

lim n3`

Cp s ~tn! 5 Cp

s S ø n51

`

tnD, where Cp

s (t) is the adequacy of test set t for testing program p with respect to specification s.

AXIOM B5 (Law of Diminishing Re- turns). The more a program has been tested, the less a given test set can fur-

418 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

ther contribute to the test adequacy. For- mally, for all programs p, specifications s, and test sets t,

@c, d [ T.~c # d f Cp s ~tuc!

$ Cp s ~tud!!,

where Cp s ~tuc! 5 Cp

s ~t ø c! 2 Cp s ~c!.

This axiom system has been proved to be consistent [Zhu and Hall 1993; Zhu et al. 1994]. From these axioms, a num- ber of properties of test data adequacy criteria can be proved. For example, if a test data adequacy criterion satisfies Axiom B2 and Axiom B4, then it is finitely applicable, which means that for any real number r less than 1, there is a finite test set whose adequacy is greater than or equal to r. Therefore an adequacy criterion can fail to be finitely applicable because of two reasons: not satisfying the adequacy of exhaustive test, such as requiring coverage of infea- sible elements, or not satisfying the con- vergence property such as the path-cov- erage criterion. Another example of derivable property is subadditivity, which can be derived from the law of diminishing returns. Here an adequacy measurement is subadditive if the ade- quacy of the union of two test sets t1 and t2 is less than or equal to the sum of the adequacy of t1 and the adequacy of t2.

The measurement theory of software test adequacy was concerned not only with the properties derivable from the axioms, but also with measurement-the- oretical properties of the axiom systems. Zhu et al. [1994] proved a uniqueness theorem that characterizes the admissi- ble transformations between any two adequacy measurements that satisfy the axioms. However, the irregularity of adequacy measurements was also for- mally proved. That is, not all adequacy measurements can be transformed from one to another. In fact, few existing adequacy criteria are convertible from one to another. According to measure- ment theory, these two theorems lay the

foundation for the investigation of the meaningfulness of statements and sta- tistical operations that involve test ade- quacy measurements [Krantz et al. 1971; Suppes et al. 1989; Luce et al. 1990].

The irregularity theorem confirms our intuition that the criteria are actually different approximations to the ideal measure of test adequacy. Therefore it is necessary to find the “errors” for each criterion. In an attempt to do so, Zhu et al. [1994] also investigated the proper- ties that distinguish different classes of test adequacy criteria.

6.4 Semantics of Software Test Adequacy

The axioms of software test adequacy criteria characterize the notion of soft- ware test adequacy by a set of proper- ties for adequacy. These axioms do not directly answer what test adequacy means. The model theory [Chang and Keisler 1973] of mathematical logic pro- vides a way of assigning meanings to formal axioms. Recently, the model the- ory was applied to assigning meanings to the axioms of test adequacy criteria [Zhu 1996b, 1995b]. Software testing was interpreted as inductive inference such that a finite number of observa- tions made on the behavior of the soft- ware under test are used to inductively derive general properties of the soft- ware. In particular, Gold’s [1967] induc- tive inference model of identification in the limit was used to interpret Weyuk- er’s axioms and a relationship between adequate testing and software correct- ness was obtained in the model [Zhu 1996b]. Valiant’s [1984] PAC inductive inference model was used to interpret Zhu and Hall’s axioms of adequacy mea- surements. Relationships between soft- ware reliability and test adequacy were obtained [Zhu 1995b].

7. CONCLUSION

Since Goodenough and Gerhart [1975, 1977] pointed out that test criteria are a central problem of software testing, test

Test Coverage and Adequacy • 419

ACM Computing Surveys, Vol. 29, No. 4, December 1997

criteria have been a major focus of the research on software testing. A large number of test data adequacy criteria have been proposed and various ration- ales have been presented for the sup- port of one or another criterion. In this article, various types of software test adequacy criteria proposed in the litera- ture are reviewed. The research on com- parison and evaluation of criteria is also surveyed. The notion of test adequacy is examined and its roles in software test- ing practice and theoretical research are discussed. Although whether an adequacy criterion captures the true notion of test adequacy is still a matter of controversy, it appears that software test adequacy criteria as a whole are clearly linked to the fault-detecting ability of software testing as well as to the dependability of the software that has passed an adequate test. It was predicted that with the ad- vent of a quality assurance framework based upon ISO 9001, which calls for spe- cific mechanisms for defect removal, the acceptance of more formal measurement of the testing process can now be antici- pated [Wichmann 1993]. There is a ten- dency towards systematic approaches to software testing through using test ade- quacy criteria.

ACKNOWLEDGMENT

The authors would like to thank the anonymous referees for their valuable comments.

APPENDIX

Glossary of Graph-Theory-Related Terminology

Complete computation path: A com- plete computation path is a path that starts with the begin node and ends at the end node of the flow graph. It is also called a computation path or execution path.

Concatenation of paths: If p 5 (n1, n2, . . . , ns), q 5 (ns11, . . . , nt) are two paths, and r 5 (n1, n2, . . . , ns, ns11, . . . , nt) is also a path, we say that r is

the concatenation of p to q and write r 5 p ∧ q.

Cycle: A path p 5 (n1, n2, . . . , nt, n1) is called a cycle.

Cycle-free path: A path is said to be cycle-free if it does not contain cycles as subpaths.

Directed graph, node, and edge: A directed graph consists of a set N of nodes and a set E # N 3 N of directed edges between nodes.

Elementary cycle and simple cycle: If the nodes n1, n2, . . . , nt in the cycle (n1, n2, . . . , nt, n1) are all different, then the cycle is called an elementary cycle. If the edges in the cycle are all different, then it is called a simple cycle.

Elementary path and simple path: A path is called an elementary path if the nodes in the path are all different. It is called a simple path if the edges in the path are all different.

Empty path: A path is called an empty path if its length is 1. In this case, the path contains no edge but only a node, and hence is written as (n1).

Feasible and infeasible paths: Not all complete computation paths neces- sarily correspond to an execution of the program. A feasible path is a complete computation path such that there exist input data that can cause the execution of the path. Otherwise, it is an infeasi- ble path.

Flow graph: A flow graph is a di- rected graph that satisfies the following conditions: (1) it has a unique begin node which has no inward edge; (2) it has a unique end node which has no outward edge; and (3) every node in a flow graph must be on a path from the begin node to the end node.

Flow graph model of program struc- ture: The nodes in a flow graph repre- sent linear sequences of computations. The edges in the flow graph represent control transfers. Each edge is associ- ated with a predicate that represents

420 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

the condition of control transfer from the computation on the start node of the edge to that on the end node of the edge. The begin node and the end node in the flow graph are where the computation starts and finishes.

Inward edges and outward edges of a node: The edge ^n1, n2& is an inward edge of the node n2. It is an outward edge of the node n1.

Length of a path: The length of a path (n1, n2, . . . , nt) is t.

Path: A path p in a graph is a se- quence (n1, n2, . . . , nt) of nodes such that ^ni, ni11& is an edge in the graph, for all i 5 1, 2, . . . , t 2 1, t . 0.

Start node and end node of an edge: The node n1 is the start node of the edge ^n1, n2& and n2 is the end node of the edge.

Start node and end node of a path: The start node of a path (n1, n2, . . . , nt) is n1, and nt is the end node of the path.

Strongly connected graph: A graph is strongly connected if for any two nodes a and b, there exists a path from a to b and a path from b to a.

Subpath: A subsequence nu, nu11, . . . , nv of the path p 5 (n1, n2, . . . , nt) is called a subpath of p, where 1 # u # v # t.

REFERENCES

ADRION, W. R., BRANSTAD, M. A., AND CHERNI- AVSKY, J. C. 1982. Validation, verification, and testing of computer software. Comput. Surv. 14, 2 (June), 159 –192.

AFIFI, F. H., WHITE, L. J., AND ZEIL, S. J. 1992. Testing for linear errors in nonlinear com- puter programs. In Proceedings of the 14th IEEE International Conference on Software Engineering (May), 81–91.

AMLA, N. AND AMMANN, P. 1992. Using Z speci- fications in category partition testing. In Pro- ceedings of the Seventh Annual Conference on Computer Assurance (June), IEEE, 3–10.

AMMANN, P. AND OFFUTT, J. 1994. Using formal methods to derive test frames in category- partition testing. In Proceedings of the Ninth Annual Conference on Computer Assurance (Gaithersburg, MD, June), IEEE, 69 –79.

BACHE, R. AND MULLERBURG, M. 1990. Meas- ures of testability as a basis for quality assur- ance. Softw. Eng. J. (March), 86 –92.

BAKER, A. L., HOWATT, J. W., AND BIEMAN, J. M. 1986. Criteria for finite sets of paths that characterize control flow. In Proceedings of the 19th Annual Hawaii International Confer- ence on System Sciences, 158 –163.

BASILI, V. R. AND RAMSEY, J. 1984. Structural coverage of functional testing. Tech. Rep. TR- 1442, Department of Computer Science, Uni- versity of Maryland at College Park, Sept.

BASILI, V. R. AND SELBY, R. W. 1987. Com- paring the effectiveness of software testing. IEEE Trans. Softw. Eng. SE-13, 12 (Dec.), 1278 –1296.

BAZZICHI, F. AND SPADAFORA, I. 1982. An auto- matic generator for compiler testing. IEEE Trans. Softw. Eng. SE-8, 4 (July), 343–353.

BEIZER, B. 1983. Software Testing Techniques. Van Nostrand Reinhold, New York.

BEIZER, B. 1984. Software System Testing and Quality Assurance. Van Nostrand Reinhold, New York.

BENGTSON, N. M. 1987. Measuring errors in op- erational analysis assumptions, IEEE Trans. Softw. Eng. SE-13, 7 (July), 767–776.

BENTLY, W. G. AND MILLER, E. F. 1993. CT cov- erage—initial results. Softw. Quality J. 2, 1, 29 – 47.

BERNOT, G., GAUDEL, M. C., AND MARRE, B. 1991. Software testing based on formal specifica- tions: A theory and a tool. Softw. Eng. J. (Nov.), 387– 405.

BIEMAN, J. M. AND SCHULTZ, J. L. 1992. An em- pirical evaluation (and specification) of the all du-paths testing criterion. Softw. Eng. J. (Jan.), 43–51.

BIRD, D. L. AND MUNOZ, C. U. 1983. Automatic generation of random self-checking test cases. IBM Syst. J. 22, 3.

BOUGE, L., CHOQUET, N., FRIBOURG, L., AND GAU- DEL, M.-C. 1986. Test set generation from algebraic specifications using logic program- ming. J. Syst. Softw. 6, 343–360.

BUDD, T. A. 1981. Mutation analysis: Ideas, ex- amples, problems and prospects. In Computer Program Testing, Chandrasekaran and Radic- chi, Eds., North Holland, 129 –148.

BUDD, T. A. AND ANGLUIN, D. 1982. Two notions of correctness and their relation to testing. Acta Inf. 18, 31– 45.

BUDD, T. A., LIPTON, R. J., SAYWARD, F. G., AND DEMILLO, R. A. 1978. The design of a pro- totype mutation system for program testing. In Proceedings of National Computer Confer- ence, 623– 627.

CARVER, R. AND KUO-CHUNG, T. 1991. Replay and testing for concurrent programs. IEEE Softw. (March), 66 –74.

Test Coverage and Adequacy • 421

ACM Computing Surveys, Vol. 29, No. 4, December 1997

CHAAR, J. K., HALLIDAY, M. J., BHANDARI, I. S., AND CHILLAREGE, R. 1993. In-process evaluation for software inspection and test. IEEE Trans. Softw. Eng. 19, 11, 1055–1070.

CHANDRASEKARAN, B. AND RADICCHI, S. (EDS.) 1981. Computer Program Testing, North- Holland.

CHANG, C. C. AND KEISLER, H. J. 1973. Model Theory. North-Holland, Amsterdam.

CHANG, Y.-F. AND AOYAMA, M. 1991. Testing the limits of test technology. IEEE Softw. (March), 9 –11.

CHERNIAVSKY, J. C. AND SMITH, C. H. 1987. A recursion theoretic approach to program test- ing. IEEE Trans. Softw. Eng. SE-13, 7 (July), 777–784.

CHERNIAVSKY, J. C. AND SMITH, C. H. 1991. On Weyuker’s axioms for software complexity measures. IEEE Trans. Softw. Eng. SE-17, 6 (June), 636 – 638.

CHOI, B., MATHUR, A., AND PATTISON, B. 1989. PMothra: Scheduling mutants for execution on a hypercube. In Proceedings of SIGSOFT Symposium on Software Testing, Analysis and Verification 3 (Dec.) 58 – 65.

CHUSHO, T. 1987. Test data selection and qual- ity estimation based on the concept of essen- tial branches for path testing. IEEE Trans. Softw. Eng. SE-13, 5 (May), 509 –517.

CLARKE, L. A., HASSELL, J., AND RICHARDSON, D. J. 1982. A close look at domain testing. IEEE Trans. Softw. Eng. SE-8, 4 (July), 380 –390.

CLARKE, L. A., PODGURSKI, A., RICHARDSON, D. J., AND ZEIL, S. J. 1989. A formal evaluation of data flow path selection criteria. IEEE Trans. Softw. Eng. 15, 11 (Nov.), 1318 –1332.

CURRIT, P. A., DYER, M., AND MILLS, H. D. 1986. Certifying the reliability of software. IEEE Trans. Softw. Eng. SE-6, 1 (Jan.) 2–13.

DAVIS, M. AND WEYUKER, E. 1988. Metric space- based test-data adequacy criteria. Comput. J. 13, 1 (Feb.), 17–24.

DEMILLO, R. A. AND MATHUR, A. P. 1990. On the use of software artifacts to evaluate the effectiveness of mutation analysis for detect- ing errors in production software. In Proceed- ings of 13th Minnowbrook Workshop on Soft- ware Engineering (July 24 –27, Blue Mountain Lake, NY), 75–77.

DEMILLO, R. A. AND OFFUTT, A. J. 1991. Con- straint-based automatic test data generation. IEEE Trans. Softw. Eng. 17, 9 (Sept.), 900 – 910.

DEMILLO, R. A. AND OFFUTT, A. J. 1993. Experi mental results from an automatic test case generator. ACM Trans. Softw. Eng. Methodol. 2, 2 (April), 109 –127.

DEMILLO, R. A., GUINDI, D. S., MCCRACKEN, W. M., OFFUTT, A. J., AND KING, K. N. 1988. An extended overview of the Mothra software testing environment. In Proceedings of SIG-

SOFT Symposium on Software Testing, Anal- ysis and Verification 2, (July), 142–151.

DEMILLO, R. A., LIPTON, R. J., AND SAYWARD, F. G. 1978. Hints on test data selection: Help for the practising programmer. Com- puter 11, (April), 34 – 41.

DEMILLO, R. A., MCCRACKEN, W. M., MATIN, R. J., AND PASSUFIUME, J. F. 1987. Software Test- ing and Evaluation, Benjamin-Cummings, Redwood City, CA.

DENNEY, R. 1991. Test-case generation from Prolog-based specifications. IEEE Softw. (March), 49 –57.

DIJKSTRA, E. W. 1972. Notes on structured pro- gramming. In Structured Programming, by O.-J. Dahl, E. W. Dijkstra, and C. A. R. Hoare, Academic Press.

DOWNS, T. 1985. An approach to the modelling of software testing with some applications. IEEE Trans. Softw. Eng. SE-11, 4 (April), 375–386.

DOWNS, T. 1986. Extensions to an approach to the modelling of software testing with some performance comparisons. IEEE Trans. Softw. Eng. SE-12, 9 (Sept.), 979 –987.

DOWNS, T. AND GARRONE, P. 1991. Some new models of software testing with performance comparisons. IEEE Trans. Rel. 40, 3 (Aug.), 322–328.

DUNCAN, I. M. M. AND ROBSON, D. J. 1990. Or- dered mutation testing. ACM SIGSOFT Softw. Eng. Notes 15, 2 (April), 29 –30.

DURAN, J. W. AND NTAFOS, S. 1984. An evalua- tion of random testing. IEEE Trans. Softw. Eng. SE-10, 4 (July), 438 – 444.

FENTON, N. 1992. When a software measure is not a measure. Softw. Eng. J. (Sept.), 357– 362.

FENTON, N. E. 1991. Software metrics—a rigor- ous approach. Chapman & Hall, London.

FENTON, N. E., WHITTY, R. W., AND KAPOSI, A. A. 1985. A generalised mathematical theory of structured programming. Theor. Comput. Sci. 36, 145–171.

FORMAN, I. R. 1984. An algebra for data flow anomaly detection. In Proceedings of the Sev- enth International Conference on Software En- gineering (Orlando, FL), 250 –256.

FOSTER, K. A. 1980. Error sensitive test case analysis (ESTCA). IEEE Trans. Softw. Eng. SE-6, 3 (May), 258 –264.

FRANKL, P. G. AND WEISS, S. N. 1993. An exper- imental comparison of the effectiveness of branch testing and data flow testing. IEEE Trans. Softw. Eng. 19, 8 (Aug.), 774 –787.

FRANKL, P. G. AND WEYUKER, J. E. 1988. An applicable family of data flow testing criteria. IEEE Trans. Softw. Eng. SE-14, 10 (Oct.), 1483–1498.

FRANKL, P. G. AND WEYUKER, J. E. 1993a. A

422 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

formal analysis of the fault-detecting ability of testing methods. IEEE Trans. Softw. Eng. 19, 3 (March), 202–213.

FRANKL, P. G. AND WEYUKER, E. J. 1993b. Prov- able improvements on branch testing. IEEE Trans. Softw. Eng. 19, 10, 962–975.

FREEDMAN, R. S. 1991. Testability of software components. IEEE Trans. Softw. Eng. SE-17, 6 (June), 553–564.

FRITZSON, P., GYIMOTHY, T., KAMKAR, M., AND SHAHMEHRI, N. 1991. Generalized algorith- mic debugging and testing. In Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation (To- ronto, June 26 –28).

FUJIWARA, S., V. BOCHMANN, G., KHENDEK, F., AMALOU, M., AND GHEDAMSI, A. 1991. Test selection based on finite state models. IEEE Trans. Softw. Eng. SE-17, 6 (June), 591– 603.

GAUDEL, M.-C. AND MARRE, B. 1988. Algebraic specifications and software testing: Theory and application. In Rapport LRI 407.

GELPERIN, D. AND HETZEL, B. 1988. The growth of software testing. Commun. ACM 31, 6 (June), 687– 695.

GIRGIS, M. R. 1992. An experimental evalua- tion of a symbolic execution system. Softw. Eng. J. (July), 285–290.

GOLD, E. M. 1967. Language identification in the limit. Inf. Cont. 10, 447– 474.

GOODENOUGH, J. B. AND GERHART, S. L. 1975. Toward a theory of test data selection. IEEE Trans. Softw. Eng. SE-3 (June).

GOODENOUGH, J. B. AND GERHART, S. L. 1977. Toward a theory of testing: Data selection criteria. In Current Trends in Programming Methodology, Vol. 2, R. T. Yeh, Ed., Prentice- Hall, Englewood Cliffs, NJ, 44 –79.

GOPAL, A. AND BUDD, T. 1983. Program testing by specification mutation. Tech. Rep. TR 83- 17, University of Arizona, Nov.

GOURLAY, J. 1983. A mathematical framework for the investigation of testing. IEEE Trans. Softw. Eng. SE-9, 6 (Nov.), 686 –709.

HALL, P. A. V. 1991. Relationship between specifications and testing. Inf. Softw. Technol. 33, 1 (Jan./Feb.), 47–52.

HALL, P. A. V. AND HIERONS, R. 1991. Formal methods and testing. Tech. Rep. 91/16, Dept. of Computing, The Open University.

HAMLET, D. AND TAYLOR, R. 1990. Partition testing does not inspire confidence. IEEE Trans. Softw. Eng. 16 (Dec.), 206 –215.

HAMLET, D., GIFFORD, B., AND NIKOLIK, B. 1993. Exploring dataflow testing of arrays. In Pro- ceedings of 15th ICSE (May), 118 –129.

HAMLET, R. 1989. Theoretical comparison of testing methods. In Proceedings of SIGSOFT Symposium on Software Testing, Analysis, and Verification 3 (Dec.), 28 –37.

HAMLET, R. G. 1977. Testing programs with the aid of a compiler. IEEE Trans. Softw. Eng. 3, 4 (July), 279 –290.

HARROLD, M. J., MCGREGOR, J. D., AND FITZ- PATRICK, K. J. 1992. Incremental testing of object-oriented class structures. In Proceed- ings of 14th ICSE (May) 68 – 80.

HARROLD, M. J. AND SOFFA, M. L. 1990. Inter- procedural data flow testing. In Proceedings of SIGSOFT Symposium on Software Testing, Analysis, and Verification 3 (Dec.), 158 –167.

HARROLD, M. J. AND SOFFA, M. L. 1991. Select- ing and using data for integration testing. IEEE Softw. (March), 58 – 65.

HARTWICK, D. 1977. Test planning. In Proceed- ings of National Computer Conference, 285– 294.

HAYES, I. J. 1986. Specification directed mod- ule testing. IEEE Trans. Softw. Eng. SE-12, 1 (Jan.), 124 –133.

HENNELL, M. A., HEDLEY, D., AND RIDDELL, I. J. 1984. Assessing a class of software tools. In Proceedings of the Seventh ICSE, 266 –277.

HERMAN, P. 1976. A data flow analysis ap- proach to program testing. Aust. Comput. J. 8, 3 (Nov.), 92–96.

HETZEL, W. 1984. The Complete Guide to Soft- ware Testing, Collins.

HIERONS, R. 1992. Software testing from formal specification. Ph.D. Thesis, Brunel Univer- sity, UK.

HOFFMAN, D. M. AND STROOPER, P. 1991. Auto- mated module testing in Prolog. IEEE Trans. Softw. Eng. 17, 9 (Sept.), 934 –943.

HORGAN, J. R. AND LONDON, S. 1991. Data flow coverage and the C language. In Proceedings of TAV4 (Oct.), 87–97.

HORGAN, J. R. AND MATHUR, A. P. 1992. Assess- ing testing tools in research and education. IEEE Softw. (May), 61– 69.

HOWDEN, W. E. 1975. Methodology for the gen- eration of program test data. IEEE Trans. Comput. 24, 5 (May), 554 –560.

HOWDEN, W. E. 1976. Reliability of the path analysis testing strategy. IEEE Trans. Softw. Eng. SE-2, (Sept.), 208 –215.

HOWDEN, W. E. 1977. Symbolic testing and the DISSECT symbolic evaluation system. IEEE Trans. Softw. Eng. SE-3 (July), 266 –278.

HOWDEN, W. E. 1978a. Algebraic program test- ing. ACTA Inf. 10, 53– 66.

HOWDEN, W. E. 1978b. Theoretical and empiri- cal studies of program testing. IEEE Trans. Softw. Eng. SE-4, 4 (July), 293–298.

HOWDEN, W. E. 1978c. An evaluation of the ef- fectiveness of symbolic testing. Softw. Pract. Exper. 8, 381–397.

HOWDEN, W. E. 1980a. Functional program testing. IEEE Trans. Softw. Eng. SE-6, 2 (March), 162–169.

Test Coverage and Adequacy • 423

ACM Computing Surveys, Vol. 29, No. 4, December 1997

HOWDEN, W. E. 1980b. Functional testing and design abstractions. J. Syst. Softw. 1, 307–313.

HOWDEN, W. E. 1981. Completeness criteria for testing elementary program functions. In Pro- ceedings of Fifth International Conference on Software Engineering (March), 235–243.

HOWDEN, W. E. 1982a. Validation of scientific programs. Comput. Surv. 14, 2 (June), 193–227.

HOWDEN, W. E. 1982b. Weak mutation testing and completeness of test sets. IEEE Trans. Softw. Eng. SE-8, 4 (July), 371–379.

HOWDEN, W. E. 1985. The theory and practice of functional testing. IEEE Softw. (Sept.), 6 –17.

HOWDEN, W. E. 1986. A functional approach to program testing and analysis. IEEE Trans. Softw. Eng. SE-12, 10 (Oct.), 997–1005.

HOWDEN, W. E. 1987. Functional program test- ing and analysis. McGraw-Hill, New York.

HUTCHINS, M., FOSTER, H., GORADIA, T., AND OS- TRAND, T. 1994. Experiments on the effec- tiveness of dataflow- and controlflow-based test adequacy criteria. In Proceedings of 16th IEEE International Conference on Software Engineering (May).

INCE, D. C. 1987. The automatic generation of test data. Comput. J. 30, 1, 63– 69.

INCE, D. C. 1991. Software testing. In Software Engineer’s Reference Book, J. A. McDermid, Ed., Butterworth-Heinemann (Chapter 19).

KARASIK, M. S. 1985. Environmental testing techniques for software certification. IEEE Trans. Softw. Eng. SE-11, 9 (Sept.), 934 –938.

KEMMERER, R. A. 1985. Testing formal specifi- cations to detect design errors. IEEE Trans. Softw. Eng. SE-11, 1 (Jan.), 32– 43.

KERNIGHAN, B. W. AND PLAUGER, P. J. 1981. Software Tools in Pascal, Addison-Wesley, Reading, MA.

KING, K. N. AND OFFUTT, A. J. 1991. A FOR- TRAN language system for mutation-based software testing. Softw. Pract. Exper. 21, 7 (July), 685–718.

KOREL, B., WEDDE, H., AND FERGUSON, R. 1992. Dynamic method of test data generation for distributed software. Inf. Softw. Tech. 34, 8 (Aug.), 523–532.

KOSARAJU, S. 1974. Analysis of structured pro- grams. J. Comput. Syst. Sci. 9, 232–255.

KRANTZ, D. H., LUCE, R. D., SUPPES, P., AND TVER- SKY, A. 1971. Foundations of Measurement, Vol. 1: Additive and Polynomial Representa- tions. Academic Press, New York.

KRAUSER, E. W., MATHUR, A. P., AND REGO, V. J. 1991. High performance software testing on SIMD machines. IEEE Trans. Softw. Eng. SE-17, 5 (May), 403– 423.

LASKI, J. 1989. Testing in the program develop- ment cycle. Softw. Eng. J. (March), 95–106.

LASKI, J. AND KOREL, B. 1983. A data flow ori-

ented program testing strategy. IEEE Trans. Softw. Eng. SE-9, (May), 33– 43.

LASKI, J., SZERMER, W., AND LUCZYCKI, P. 1993. Dynamic mutation testing in inte- grated regression analysis. In Proceedings of 15th International Conference on Software Engineering (May), 108 –117.

LAUTERBACH, L. AND RANDALL, W. 1989. Ex- perimental evaluation of six test techniques. In Proceedings of COMPASS 89 (Washington, DC, June), 36 – 41.

LEVENDEL, Y. 1991. Improving quality with a manufacturing process. IEEE Softw. (March), 13–25.

LINDQUIST, T. E. AND JENKINS, J. R. 1987. Test case generation with IOGEN. In Proceedings of the 20th Annual Hawaii International Con- ference on System Sciences, 478 – 487.

LITTLEWOOD, B. AND STRIGINI, L. 1993. Valida- tion of ultra-high dependability for software- based systems. C ACM 36, 11 (Nov.), 69 – 80.

LIU, L.-L. AND ROBSON, D. J. 1989. Symbolic evaluation in software testing, the final re- port. Computer Science Tech. Rep. 10/89, School of Engineering and Applied Science, University of Durham, June.

LUCE, R. D., KRANTZ, D. H., SUPPES, P., AND TVER- SKY, A. 1990. Foundations of Measurement, Vol. 3: Representation, Axiomatization, and Invariance. Academic Press, San Diego.

MALAIYA, Y. K., VONMAYRHAUSER, A., AND SRIMANI, P. K. 1993. An examination of fault expo- sure ratio. IEEE Trans. Softw. Eng. 19, 11, 1087–1094.

MARICK, B. 1991. The weak mutation hypothe- sis. In Proceedings of SIGSOFT Symposium on Software Testing, Analysis, and Verifica- tion 4 (Oct.), 190 –199.

MATHUR, A. P. 1991. Performance, effective- ness, and reliability issues in software test- ing. In Proceedings of the 15th Annual Inter- national Computer Software and Applications Conference (Tokyo, Sept.), 604 – 605.

MARSHALL, A. C. 1991. A Conceptual model of software testing. J. Softw. Test. Ver. Rel. 1, 3 (Dec.), 5–16.

MCCABE, T. J. 1976. A complexity measure. IEEE Trans. Softw. Eng. SE-2, 4, 308 –320.

MCCABE, T. J. (ED.) 1983. Structured Testing. IEEE Computer Society Press, Los Alamitos, CA.

MCCABE, T. J. AND SCHULMEYER, G. G. 1985. System testing aided by structured analysis: A practical experience. IEEE Trans. Softw. Eng. SE-11, 9 (Sept.), 917–921.

MCMULLIN, P. R. AND GANNON, J. D. 1983. Com- bining testing with specifications: A case study. IEEE Trans. Softw. Eng. SE-9, 3 (May), 328 –334.

MEEK, B. AND SIU, K. K. 1988. The effectiveness of error seeding. Alvey Project SE/064: Qual-

424 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

ity evaluation of programming language pro- cessors, Report No. 2, Computing Centre, King’s College London, Oct.

MILLER, E. AND HOWDEN, W. E. 1981. Tutorial: Software Testing and Validation Techniques, (2nd ed.). IEEE Computer Society Press, Los Alamitos, CA.

MILLER, K. W., MORELL, L. J., NOONAN, R. E., PARK, S. K., NICOL, D. M., MURRILL, B. W., AND VOAS, J. M. 1992. Estimating the probabil- ity of failure when testing reveals no failures. IEEE Trans. Softw. Eng. 18, 1 (Jan.), 33– 43.

MORELL, L. J. 1990. A theory of fault-based testing. IEEE Trans. Softw. Eng. 16, 8 (Aug.), 844 – 857.

MYERS, G. J. 1977. An extension to the cyclo- matic measure of program complexity. SIG- PLAN No. 12, 10, 61– 64.

MYERS, G. J. 1979. The Art of Software Testing. John Wiley and Sons, New York.

MYERS, J. P., JR. 1992. The complexity of soft- ware testing. Softw. Eng. J. (Jan.), 13–24.

NTAFOS, S. C. 1984. An evaluation of required element testing strategies. In Proceedings of the Seventh International Conference on Soft- ware Engineering, 250 –256.

NTAFOS, S. C. 1984. On required element test- ing. IEEE Trans. Softw. Eng. SE-10, 6 (Nov.), 795– 803.

NTAFOS, S. C. 1988. A comparison of some structural testing strategies. IEEE Trans. Softw. Eng. SE-14 (June), 868 – 874.

OFFUTT, A. J. 1989. The coupling effect: Fact or fiction. In Proceedings of SIGSOFT Sympo- sium on Software Testing, Analysis, and Veri- fication 3 (Dec. 13–15), 131–140.

OFFUTT, A. J. 1992. Investigations of the soft- ware testing coupling effect. ACM Trans. Softw. Eng. Methodol. 1, 1 (Jan.), 5–20.

OFFUTT, A. J. AND LEE, S. D. 1991. How strong is weak mutation? In Proceedings of SIG- SOFT Symposium on Software Testing, Anal- ysis, and Verification 4 (Oct.), 200 –213.

OFFUTT, A. J., ROTHERMEL, G., AND ZAPF, C. 1993. An experimental evaluation of selec- tive mutation. In Proceedings of 15th ICSE (May), 100 –107.

OSTERWEIL, L. AND CLARKE, L. A. 1992. A pro- posed testing and analysis research initiative. IEEE Softw. (Sept.), 89 –96.

OSTRAND, T. J. AND BALCER, M. J. 1988. The category-partition method for specifying and generating functional tests. Commun. ACM 31, 6 (June), 676 – 686.

OSTRAND, T. J. AND WEYUKER, E. J. 1991. Data- flow-based test adequacy analysis for lan- guages with pointers. In Proceedings of SIG- SOFT Symposium on Software Testing, Anal- ysis, and Verification 4, (Oct.), 74 – 86.

OULD, M. A. AND UNWIN, C., EDS. 1986. Testing in Software Development. Cambridge Univer- sity Press, New York.

PAIGE, M. R. 1975. Program graphs, an alge- bra, and their implication for programming. IEEE Trans. Softw. Eng. SE-1, 3, (Sept.), 286 –291.

PAIGE, M. R. 1978. An analytical approach to software testing. In Proceedings COMP- SAC’78, 527–532.

PANDI, H. D., RYDER, B. G., AND LANDI, W. 1991. Interprocedural Def-Use associations in C programs. In Proceedings of SIGSOFT Symposium on Software Testing, Analysis, and Verification 4, (Oct.), 139 –153.

PARRISH, A. AND ZWEBEN, S. H. 1991. Analysis and refinement of software test data ade- quacy properties. IEEE Trans. Softw. Eng. SE-17, 6 (June), 565–581.

PARRISH, A. S. AND ZWEBEN, S. H. 1993. Clarify- ing some fundamental concepts in software testing. IEEE Trans. Softw. Eng. 19, 7 (July), 742–746.

PETSCHENIK, N. H. 1985. Practical priorities in system testing. IEEE Softw. (Sept.), 18 –23.

PIWOWARSKI, P., OHBA, M., AND CARUSO, J. 1993. Coverage measurement experience during function testing. In Proceedings of the 15th ICSE (May), 287–301.

PODGURSKI, A. AND CLARKE, L. 1989. The impli- cations of program dependences for software testing, debugging and maintenance. In Pro- ceedings of SIGSOFT Symposium on Software Testing, Analysis, and Verification 3, (Dec.), 168 –178.

PODGURSKI, A. AND CLARKE, L. A. 1990. A for- mal model of program dependences and its implications for software testing, debugging and maintenance. IEEE Trans. Softw. Eng. 16, 9 (Sept.), 965–979.

PRATHER, R. E. AND MYERS, J. P. 1987. The path prefix software testing strategy. IEEE Trans. Softw. Eng. SE-13, 7 (July).

PROGRAM ANALYSIS LTD., UK. 1992. Testbed technical description. May.

RAPPS, S. AND WEYUKER, E. J. 1985. Selecting software test data using data flow informa- tion. IEEE Trans. Softw. Eng. SE-11, 4 (April), 367–375.

RICHARDSON, D. J. AND CLARKE, L. A. 1985. Partition analysis: A method combining test- ing and verification. IEEE Trans. Softw. Eng. SE-11, 12 (Dec.), 1477–1490.

RICHARDSON, D. J., AHA, S. L., AND O’MALLEY, T. O. 1992. Specification-based test oracles for re- active systems. In Proceedings of 14th Inter- national Conference on Software Engineering (May), 105–118.

RICHARDSON, D. J. AND THOMPSON, M. C. 1988. The RELAY model of error detection

Test Coverage and Adequacy • 425

ACM Computing Surveys, Vol. 29, No. 4, December 1997

and its application. In Proceedings of SIG- SOFT Symposium on Software Testing, Anal- ysis, and Verification 2 (July).

RICHARDSON, D. J. AND THOMPSON, M. C. 1993. An analysis of test data selection criteria us- ing the relay model of fault detection. IEEE Trans. Softw. Eng. 19, 6, 533–553.

RIDDELL, I. J., HENNELL, M. A., WOODWARD, M. R., AND HEDLEY, D. 1982. Practical aspects of program mutation. Tech. Rep., Dept. of Compu- tational Science, University of Liverpool, UK.

ROBERTS, F. S. 1979. Measurement Theory, En- cyclopedia of Mathematics and Its Applica- tions, Vol. 7. Addison-Wesley, Reading, MA.

ROE, R. P. AND ROWLAND, J. H. 1987. Some the- ory concerning certification of mathematical subroutines by black box testing. IEEE Trans. Softw. Eng. SE-13, 6 (June), 677– 682.

ROUSSOPOULOS, N. AND YEH, R. T. 1985. SEES: A software testing environment support system. IEEE Trans. Softw. Eng. SE-11, 4, (April), 355– 366.

RUDNER, B. 1977. Seeding/tagging estimation of software errors: Models and estimates. Rome Air Development Centre, Rome, NY, RADC-TR-77-15, also AD-A036 655.

SARIKAYA, B., BOCHMANN, G. V., AND CERNY, E. 1987. A test design methodology for pro- tocol testing. IEEE Trans. Softw. Eng. SE-13, 5 (May), 518 –531.

SHERER, S. A. 1991. A cost-effective approach to testing. IEEE Softw. (March), 34 – 40.

SOFTWARE RESEARCH. 1992. Software Test- Works—Software Testers Workbench System. Software Research, Inc.

SOLHEIM, J. A. AND ROWLAND, J. H. 1993. An empirical-study of testing and integration strategies using artificial software systems. IEEE Trans. Softw. Eng. 19, 10, 941–949.

STOCKS, P. A. AND CARRINGTON, D. A. 1993. Test templates: A specification-based testing framework. In Proceedings of 15th Interna- tional Conference on Software Engineering (May), 405– 414.

SU, J. AND RITTER, P. R. 1991. Experience in testing the Motif interface. IEEE Softw. (March), 26 –33.

SUPPES, P., KRANTZ, D. H., LUCE, R. D., AND TVER- SKY, A. 1989. Foundations of Measurement, Vol. 2: Geometrical, Threshold, and Probabi- listic Representations. Academic Press, San Diego.

TAI, K.-C. 1993. Predicate-based test genera- tion for computer programs. In Proceedings of 15th International Conference on Software Engineering (May), 267–276.

TAKAHASHI, M. AND KAMAYACHI, Y. 1985. An empirical study of a model for program error prediction. IEEE, 330 –336.

THAYER, R., LIPOW, M., AND NELSON, E. 1978. Software Reliability. North-Holland.

TSAI, W. T., VOLOVIK, D., AND KEEFE, T. F. 1990. Automated test case generation for programs specified by relational algebra que- ries. IEEE Trans. Softw. Eng. 16, 3 (March), 316 –324.

TSOUKALAS, M. Z., DURAN, J. W., AND NTAFOS, S. C. 1993. On some reliability estimation problems in random and partition testing. IEEE Trans. Softw. Eng. 19, 7 (July), 687– 697.

URAL, H. AND YANG, B. 1988. A structural test selection criterion. Inf. Process. Lett. 28, 3 (July), 157–163.

URAL, H. AND YANG, B. 1993. Modeling software for accurate data flow representation. In Pro- ceedings of 15th International Conference on Software Engineering (May), 277–286.

VALIANT, L. C. 1984. A theory of the learnable. Commun. ACM 27, 11, 1134 –1142.

VOAS, J., MORRELL, L., AND MILLER, K. 1991. Predicting where faults can hide from testing. IEEE Softw. (March), 41– 48.

WEISER, M. D., GANNON, J. D., AND MCMULLIN, P. R. 1985. Comparison of structural test coverage metrics. IEEE Softw. (March), 80 – 85.

WEISS, S. N. AND WEYUKER, E. J. 1988. An ex- tended domain-based model of software reli- ability. IEEE Trans. Softw. Eng. SE-14, 10 (Oct.), 1512–1524.

WEYUKER, E. J. 1979a. The applicability of pro- gram schema results to programs. Int. J. Comput. Inf. Sci. 8, 5, 387– 403.

WEYUKER, E. J. 1979b. Translatability and de- cidability questions for restricted classes of program schema. SIAM J. Comput. 8, 5, 587– 598.

WEYUKER, E. J. 1982. On testing non-testable programs. Comput. J. 25, 4, 465– 470.

WEYUKER, E. J. 1983. Assessing test data ade- quacy through program inference. ACM Trans. Program. Lang. Syst. 5, 4, (Oct.), 641– 655.

WEYUKER, E. J. 1986. Axiomatizing software test data adequacy. IEEE Trans. Softw. Eng. SE-12, 12, (Dec.), 1128 –1138.

WEYUKER, E. J. 1988a. The evaluation of pro- gram-based software test data adequacy crite- ria. Commun. ACM 31, 6, (June), 668 – 675.

WEYUKER, E. J. 1988b. Evaluating software complexity measures. IEEE Trans. Softw. Eng. SE-14, 9, (Sept.), 1357–1365.

WEYUKER, E. J. 1988c. An empirical study of the complexity of data flow testing. In Pro- ceedings of SIGSOFT Symposium on Software Testing, Analysis, and Verification 2 (July), 188 –195.

WEYUKER, E. J. 1993. More experience with data-flow testing. IEEE Trans. Softw. Eng. 19, 9, 912–919.

WEYUKER, E. J. AND DAVIS, M. 1983. A formal

426 • Zhu et al.

ACM Computing Surveys, Vol. 29, No. 4, December 1997

notion of program-based test data adequacy. Inf. Cont. 56, 52–71.

WEYUKER, E. J. AND JENG, B. 1991. Analyzing partition testing strategies. IEEE Trans. Softw. Eng. 17, 7 (July), 703–711.

WEYUKER, E. J. AND OSTRAND, T. J. 1980. Theo- ries of program testing and the application of revealing sub-domains. IEEE Trans. Softw. Eng. SE-6, 3 (May), 236 –246.

WHITE, L. J. 1981. Basic mathematical defini- tions and results in testing. In Computer Pro- gram Testing, B. Chandrasekaran and S. Radicchi, Eds., North-Holland, 13–24.

WHITE, L. J. AND COHEN, E. I. 1980. A domain strategy for computer program testing. IEEE Trans. Softw. Eng. SE-6, 3 (May), 247–257.

WHITE, L. J. AND WISZNIEWSKI, B. 1991. Path testing of computer programs with loops us- ing a tool for simple loop patterns. Softw. Pract. Exper. 21, 10 (Oct.).

WICHMANN, B. A. 1993. Why are there no mea- surement standards for software testing? Comput. Stand. Interfaces 15, 4, 361–364.

WICHMANN, B. A. AND COX, M. G. 1992. Prob- lems and strategies for software component testing standards. J. Softw. Test. Ver. Rel. 2, 167–185.

WILD, C., ZEIL, S., CHEN, J., AND FENG, G. 1992. Employing accumulated knowledge to refine test cases. J. Softw. Test. Ver. Rel. 2, 2 (July), 53– 68.

WISZNIEWSKI, B. W. 1985. Can domain testing overcome loop analysis? IEEE, 304 –309.

WOODWARD, M. R. 1991. Concerning ordered mutation testing of relational operators. J. Softw. Test. Ver. Rel. 1, 3 (Dec.), 35– 40.

WOODWARD, M. R. 1993. Errors in algebraic specifications and an experimental mutation testing tool. Softw. Eng. J. (July), 211–224.

WOODWARD, M. R. AND HALEWOOD, K. 1988. From weak to strong— dead or alive? An anal- ysis of some mutation testing issues. In Pro- ceedings of Second Workshop on Software Testing, Verification and Analysis (July) 152– 158.

WOODWARD, M. R., HEDLEY, D., AND HENNEL, M. A. 1980. Experience with path analysis and testing of programs. IEEE Trans. Softw. Eng. SE-6, 5 (May), 278 –286.

WOODWARD, M. R., HENNEL, M. A., AND HEDLEY, D. 1980. A limited mutation approach to program testing. Tech. Rep. Dept. of Compu- tational Science, University of Liverpool.

YOUNG, M. AND TAYLOR, R. N. 1988. Combining static concurrency analysis with symbolic ex-

ecution. IEEE Trans. Softw. Eng. SE-14, 10 (Oct.), 1499 –1511.

ZEIL, S. J. 1983. Testing for perturbations of program statements. IEEE Trans. Softw. Eng. SE-9, 3, (May), 335–346.

ZEIL, S. J. 1984. Perturbation testing for com- putation errors. In Proceedings of Seventh International Conference on Software Engi- neering (Orlando, FL), 257–265.

ZEIL, S. J. 1989. Perturbation techniques for detecting domain errors. IEEE Trans. Softw. Eng. 15, 6 (June), 737–746.

ZEIL, S. J., AFIFI, F. H., AND WHITE, L. J. 1992. Detection of linear errors via domain testing. ACM Trans. Softw. Eng. Methodol. 1, 4, (Oct.), 422– 451.

ZHU, H. 1995a. Axiomatic assessment of con- trol flow based software test adequacy crite- ria. Softw. Eng. J. (Sept.), 194 –204.

ZHU, H. 1995b. An induction theory of software testing. Sci. China 38 (Supp.) (Sept.), 58 –72.

ZHU, H. 1996a. A formal analysis of the sub- sume relation between software test adequacy criteria. IEEE Trans. Softw. Eng. 22, 4 (April), 248 –255.

ZHU, H. 1996b. A formal interpretation of soft- ware testing as inductive inference. J. Softw. Test. Ver. Rel. 6 (July), 3–31.

ZHU, H. AND HALL, P. A. V. 1992a. Test data adequacy with respect to specifications and related properties. Tech. Rep. 92/06, Depart- ment of Computing, The Open University, UK, Jan.

ZHU, H. AND HALL, P. A. V. 1992b. Testability of programs: Properties of programs related to test data adequacy criteria. Tech. Rep. 92/05, Department of Computing, The Open Univer- sity, UK, Jan.

ZHU, H. AND HALL, P. A. V. 1993. Test data adequacy measurements. Softw. Eng. J. 8, 1 (Jan.), 21–30.

ZHU, H., HALL, P. A. V., AND MAY, J. 1992. Inductive inference and software testing. J. Softw. Test. Ver. Rel. 2, 2 (July), 69 – 82.

ZHU, H., HALL, P. A. V., AND MAY, J. 1994. Un- derstanding software test adequacy—an axi- omatic and measurement approach. In Math- ematics of Dependable Systems, Proceedings of IMA First Conference (Sept., London), Oxford University Press, Oxford.

ZWEBEN, S. H. AND GOURLAY, J. S. 1989. On the adequacy of Weyuker’s test data adequacy axioms. IEEE Trans. Softw. Eng. SE-15, 4, (April), 496 –501.

Received November 1994; revised March 1996; accepted October 1996

Test Coverage and Adequacy • 427

ACM Computing Surveys, Vol. 29, No. 4, December 1997