Consider the program text in Figure 13.3 and a test set S containing just one test case:

n = 2, A[0] = 10, A[1] = 5

If we execute the program using S, then all statements are executed at least once. If our criterion to judge the adequacy of a test set is that 100% of the statements are executed, then S is adequate. If our criterion is that 100% of the branches are executed, then S is not adequate, since the (empty) else branch of the if statement is not executed by S.

Figure 13.3. Erroneous selection sort procedure

A test adequacy criterion thus specifies requirements for testing. It can be used in different ways: as stopping rule, as measurement, or as test case generator. If a test adequacy criterion is used as a stopping rule, it tells us when sufficient testing has been done. If statement coverage is the criterion, we may stop testing if all statements have been executed by the tests done so far. In this view, a test set is either good or bad; the criterion is either met, or it isn't. If we relax this requirement a bit and use, say, the percentage of statements executed as a test quality criterion, then the test adequacy criterion is used as a measurement. Formally, it is a mapping from the test set to the interval [0, 1]. Note that the stopping-rule view is in fact a special case of the measurement view. Finally, the test adequacy criterion can be used in the test selection process. If 100% statement coverage has not been achieved yet, an additional test case is selected that covers one or more untested statements. This generative view is used in many test tools.

Test adequacy criteria are closely linked to test techniques. For example, coverage-based test techniques keep track of which statements, branches, and so on, are executed, and this gives us an easy handle to determine whether a coverage-based adequacy criterion has been met or not. The same test technique, however, does not help us in assessing whether all error-prone points in a program have been tested. In a sense, a given test adequacy criterion and the corresponding test technique are opposite sides of the same coin.

Suppose we wish to test some component P which sorts an array A[0 .. n-1] of integers, 1 ≤ n ≤1 000. Since exhaustive testing is not feasible, we are looking for a strategy in which only a small number of tests are exercised. One possible set of test cases is the following:

Let n assume values 0, 1, 17 and 1 000. For each of n = 17 and n = 1 000, choose three values for the array A:

In following this type of constructive approach, the input domain is partitioned into a finite, small number of subdomains. The underlying assumption is that these subdomains are equivalence classes, i.e. from a testing point of view each member from a given subdomain is as good as any other. For example, we have tacitly assumed that one random array of length 17 is as good a test as any other random array of length i with 1 < i < 1000.

Suppose the actual sorting algorithm used is the one from Figure 13.3. If the tests use positive integers only, the output will be correct. The output will not be correct if a test input happens to contain negative integers.

The test set using positive integers only does not reveal the fault because the inputs in the subdomains are not really interchangeable (instead of comparing the values of array entries, the algorithm compares their absolute values). Any form of testing which partitions the input domain works perfectly if the right subdomains are chosen. In practice however, we generally do not know where the needles are hidden, and the partition of the input domain is likely to be imperfect.

Both functional and structural testing schemes use a systematic means to determine subdomains. They often use peculiar inputs to test peculiar cases. Their intention is to provoke failure behavior. Their success hinges on the assumption that we can indeed identify subdomains with a high failure probability. Though this is a good strategy for fault detection, it does not necessarily inspire confidence.

The user of a system is interested in the probability of failure-free behavior. Following this line of thought, we are not so much interested in the faults themselves, but rather in their manifestations. A fault which frequently manifests itself will, in general, cause more damage than a fault which seldom shows up. This is precisely what we hinted at above when we discussed fault detection and confidence building as possible test objectives.

If failures are more important than faults, the goal pursued during the test phase may also change. In that case, we will not pursue the discovery of as many faults as possible but will strive for high reliability. Random testing does not work all that well if we want to find as many faults as possible — hence the development of different test techniques. When pursuing high reliability, however, it is possible to use random input.

In order to obtain confidence in the daily operation of a software system, we have to mimic that situation. This requires the execution of a large number of test cases that represent typical usage scenarios. Random testing does at least as good a job in this respect as any form of testing based on partitioning the input domain.

This approach has been applied in the Cleanroom development method. In this method, the development of individual components is done by programmers who are not allowed to actually execute their code. The programmer must then convince himself of the correctness of his components using manual techniques such as stepwise abstraction (see also Section 13.4).

In the next step, these components are integrated and tested by someone else. The input for this process is generated according to a distribution which follows the expected operational use of the system. During this integration phase, one tries to reach a certain required reliability level. Experiences with this approach are positive.

The quantitative assessment of failure probability brings us into the area of software reliability. Section 13.10 is devoted to this topic.

In the early days of computing, programs were written and then debugged to make sure that they ran properly. Testing and debugging were largely synonymous terms. Both referred to an activity near the end of the development process when the software had been written, but still needed to be 'checked out'.

Today's situation is rather different. Testing activities occur in every phase of the development process. They are carefully planned and documented. The execution of software to compare actual behavior with expected behavior is only one aspect out of many.

Gelperin and Hetzel (1988) identify four major testing models. These roughly parallel the historical development of test practices. The models and their primary goals are given in Table 13.1.

The primary goal of the demonstration model is to make sure that the program runs and solves the problem. The strategy is like that of a constructive mathematical proof. If the software passes all tests from the test set, it is claimed to satisfy the requirements. The strategy gives no guidelines as to how to obtain such a test set. A poorly chosen test set may mask poor software quality. Most programmers will be familiar with the process of testing their own programs by carefully reading them or executing them with selected input data. If this is done very carefully, it can be beneficial. This method also holds some dangers, however. We may be inclined to consider this form of testing as a method to convince ourselves or someone else that the software does not contain errors. We will then, partly unconsciously, look for test cases which support this hypothesis. This type of demonstration-oriented approach to testing is not to be advocated.

Proper testing is a very destructive process. A program should be tested with the purpose of finding as many faults as possible. A test can only be considered successful if it leads to the discovery of at least one fault. (In a similar way, a visit to your physician is only successful if he finds a 'fault' and we generally consider such a visit unsatisfactory if we are sent home with the message that nothing wrong could be found.) In order to improve the chances of producing a high quality system, we should reverse the strategy and start looking for test cases that do reveal faults. This may be termed a proof by contradiction. The test set is then judged by its ability to detect faults.

Since we do not know whether any residual faults are left, it is difficult to decide when to stop testing in either of these models. In the demonstration-oriented model, the criteria most often used to determine this point in time seem to be the following:

The first criterion is pointless, since it does not tell us anything about the quality of the test effort. If there is no money at all, this criterion is most easily satisfied. The second criterion is pointless as well, since it does not tell us anything about the quality of the test cases.

The destruction-oriented model usually entails some systematic way of deriving test cases. We may then base our stop criterion on the test adequacy criterion that corresponds to the test technique used. An example of this might be: 'We stop testing if 100% of the branches are covered by the set of test cases and all test cases yield an unsuccessful result'.

Both these models view testing as one phase in the software development process. As noted before, this is not a very good strategy. The life-cycle-testing models extend testing activities to earlier phases. In the evaluation-oriented model, the emphasis is on analysis and review techniques to detect faults in requirements and design documents. In the prevention model, emphasis is on the careful planning and design of test activities. For example, the early design of test cases may reveal that certain requirements cannot be tested and thus such an activity helps to prevent errors from being made in the first place. Test-driven development falls into this category as well.

We may observe a gradual shift of emphasis in test practice, from a demonstration-like approach to prevention-oriented methods. Though many organizations still concentrate their test effort late in the development life cycle, various organizations have shown that upstream testing activities can be most effective. Quantitative evidence of this is provided in Section 13.8.3.

Testing need not only result in software with fewer errors. Testing also results in valuable knowledge (error-prone constructs and so on) which can be fed back into the development process. In this view, testing is a learning process, which can be given its proper place in an improvement process.

The verification and validation techniques applied during this phase are strongly dependent upon the way in which the requirements specification has been laid down. Something which should be done at the very least is to conduct a careful review or inspection in order to check whether all aspects of the system have been properly described. As we saw earlier, errors made at this stage are very costly to repair if they go unnoticed until late in the development process. (Boehm, 1984b) gives four essential criteria for a requirements specification:

Testing a requirements specification should primarily be aimed at testing these criteria.

The aim of testing the completeness criterion is to determine whether all components are present and described completely. A requirements specification is incomplete if it contains such phrases as 'to be determined' or if it contains references to undefined elements. We should also watch for the omission of functions or products, such as back-up or restart procedures and test tools to be delivered to the customer.

A requirements specification is consistent if its components do not contradict each other and the specification does not conflict with external specifications. We thus need both internal and external consistency. Moreover, each element in the requirements specification must be traceable. It must, for instance, be possible to decide whether a natural language interface is really needed.

According to Boehm, feasibility has to do with more than functional and performance requirements. The benefits of a computerized system should outweigh the associated costs. This must be established at an early stage and necessitates timely attention to user requirements, maintainability, reliability, and so on. In some cases, the project's success is very sensitive to certain key factors, such as safety, speed, availability of certain types of personnel; these risks must be analyzed at an early stage.

Lastly, a requirements specification must be testable. In the end, we must be able to decide whether or not a system fulfills its requirements. So requirements must be specific, unambiguous, and quantitative. The quality-attribute scenario framework from (Bass et al., 2003) is an example of how to specify such requirements; see also Section 6.3.

Many of these points are raised by (Poston, 1987). According to Poston, the most likely errors in a requirements specification can be grouped into the following categories:

Using a standard format for documenting the requirements specification, such as IEEE Standard 830 (discussed in Chapter 9), may help enormously in preventing these types of errors occurring in the first place.

Useful techniques for testing the degree to which criteria have been met are mostly manual (reading documents, inspections, reviews). Scenarios for the expected use of the system can be devised with the prospective users of the system. If requirements are already expressed in use cases, such scenarios are readily available. In this way, a set of functional tests is generated.

At this stage also, a general test strategy for subsequent phases must be formulated. It should encompass the choice of particular test techniques; evaluation criteria; a test plan; a test scheme; and test documentation requirements. A test team may also be formed at this stage. These planning activities are dealt with in Section 13.3.

The criteria mentioned previously (completeness, consistency, feasibility, and testability) are also essential for the design. The most likely errors in design resemble the kind of errors one is inclined to make in a requirements specification: missing, wrong, and extraneous information. For the design too, a precise documentation standard is of great help in preventing these types of errors. IEEE Standards 1471 and 1016, discussed in Chapters 11 and 12, respectively, are examples of such standards.

During the architectural design phase, a high-level conceptual model of the system is developed in terms of components and their interaction. This architecture can be assessed, for example by generating scenarios which express quality concerns, such as maintainability and flexibility, in very concrete terms and evaluating how the architecture handles these scenarios; see also Section 11.5.

During the design phase, we decompose the total system into subsystems and components, starting from the requirements specification. We may then develop tests based on this decomposition process. Design is not a one-shot process. During the design process a number of successive refinements will be made, resulting in layers showing increasing detail. Following this design process, more detailed tests can be developed as the lower layers of the design are decided upon.

We may also test the design itself. This includes tracing elements from the requirements specification to the corresponding elements in the design description, and vice versa. Well-known techniques for doing so are, amongst others, simulation, design walkthroughs, and design inspections.

In the requirements engineering phase, the possibilities for formally documenting the resulting specification are limited. Most requirements specifications make excessive use of natural language descriptions. For the design phase, there are ample opportunities to formally document the resulting specification. The more formally the design is specified, the more possibilities we have for applying verification techniques, as well as formal checks for consistency and completeness.

During the implementation phase, we do the 'real' testing. One of the most effective techniques to find errors in a program text is to carefully read that text, or have it read. This technique has been successfully applied for a long time. Somewhat formalized variants are known as 'code inspection' and 'code walkthrough'. We may also apply the technique of stepwise abstraction: the function of the code is determined in a number of abstraction steps, starting from the code itself. We may try to prove the correctness of the code using formal verification techniques. The various manual test techniques are discussed in Section 13.4.

There are many tools to support the testing of code. We may distinguish between tools for static analysis and tools for dynamic analysis. Static analysis tools inspect the program code without executing it. They include tests such as: are all variables declared and given a value before they are used? Dynamic analysis tools are used in conjunction with the actual execution of the code, for example tools that keep track of which portions of the code have been covered by the tests so far.

All of the above techniques are aimed at evaluating the quality of the source code as well as its compliance with design specifications and code documentation.

It is crucial to control the test information properly while testing the code. Tools may help us to do so, for example, test drivers generate the test environment for a component to be tested, test stubs simulate the function of a component not yet available, and test data generators provide us with data. In bottom-up testing, we will, in general, make much use of test drivers, while top-down testing implies the use of test stubs. The test strategy (top-down versus bottom-up) may be partly influenced by the design technique used. If the high level, architectural design is implemented as a skeletal system whose holes yet have to be filled in, that skeletal system can be used as a test driver.

Tools (test harnesses and test systems) may also be profitable while executing the tests. A simple and yet effective tool is one which compares test results with expected results. The eye is a very unreliable medium. After a short time, all results look OK. An additional advantage of this type of tool support is that it helps to achieve a standard test format. This, in turn, helps with regression testing.

On average, more than 50% of total life-cycle costs is spent on maintenance. If we modify the software after a system has become operational (because an error is found late on, or because the system must be adapted to changed requirements), we will have to test the system anew. This is called regression testing. To have this proceed smoothly, the quality of the documentation and the possibilities for tool support, are crucial factors.

In a retest-all approach, all tests are rerun. Since this may consume a lot of time and effort, we may also opt for a selective retest, in which only some of the tests are rerun. A regression test selection technique is then used to decide which subset should be rerun. We would like this technique to include all tests in which the modified and the original program produce different results, while omitting tests that produce the same results.

Suppose our library system needs to be able to prevent borrowing of items by members that are on a black list. We could start by redesigning part of the system and implementing the necessary changes: a new table, BlackList, and appropriate checks in method Borrow. We also have to decide when members are put on the black list, and how to get them off that list. After having done all the necessary analysis and design, and implemented the changes accordingly, we devise test cases to test for the new functionality.

This order of events is completely reversed in test-driven development (TDD). In test-driven development, we first write a few tests for the new functionality. We may start very simple, and add a test in the start-up method to ensure that the black list is initially empty:

assertEquals(0, BlackList)

Of course, this test will fail. To make it succeed, we have to introduce BlackList, and set it equal to 0. At the same time, we make a list of things still to be done, such as devising a proper type for BlackList, including operations to add and remove members to that list, an update of Borrow to check whether a person borrowing an item is on the black list, and so on. This list of things to be done is similar to the backlog used by architects while architecting a system (see Section 11.2).

After we have made the simple test work, the new version of the system is inspected to see whether it can be improved. Another small change is contemplated. We may for example decide to make BlackList into a proper list, and write some simple tests to see that after adding an item to the list, that item is indeed in the list. Again, the test will fail and we update the system accordingly. Possibly, improvements can be made now since the library system probably contains other list-type classes that we can inherit from and some duplicate code can be removed. And so on.

Test-driven development is one of the practices of eXtreme Programming (see Section 3.2.4). As such, it is part of the agile approach to system development which favors small increments and redesign (refactoring) where needed rather than big design efforts. The practice is usually supported by an automated unit testing framework, such as JUnit for Java, that keeps track of the test set and reports back readable error messages for tests that fail (Hunt and Thomas, 2003). The assertEquals method used above is one of the methods provided by the JUnit framework. The framework allows for a smooth integration of coding and unit testing. On the fly, a test set is built that forms a reusable asset during the further evolution of the system. JUnit and similar frameworks have greatly contributed to the success of test-driven development.

The way of working in each iteration of test-driven development consists of the following steps:

In pure eXtreme Programming, iterations are very small, and may take from a few minutes up to, say, an hour. But test-driven development can also be done in bigger leaps and can be combined with more traditional approaches.

Test-driven development is much more than a test method. It is a different way of developing software. The effort put into the upfront development of test cases forces one to think more carefully of what it means for the current iteration to succeed or fail. Writing down explicit test cases subsumes part of the analysis and design work. Rather than producing UML diagrams during requirements analysis, we produce tests. And these tests are used immediately, by the same person that implemented the functionality that the test exercises. Testing then is not an afterthought, but becomes an integral part of the development process. Another benefit is that we have a test set and a test criterion to decide on the success of the iteration. Experiments with test-driven development indicate that it increases productivity and reduces defect rates.

We all read, and reread, and reread our program texts. It is the most traditional test technique we know of. It is also a very successful technique for finding faults in a program text (or a specification or a design).

In general, it is better to have someone else read your texts. The author of a text knows all too well what the program (or any other type of document) ought to convey. For this reason, the author may be inclined to overlook things, suffering from some sort of trade blindness.

A second reason why reading by the author himself might be less fruitful, is that it is difficult to adopt a destructive attitude towards one's own work. Yet such an attitude is needed for successful testing.

A somewhat institutionalized form of reading each other's programs is known as peer review. This is a technique for anonymously assessing programs for quality, readability, usability, and so on.

Each person partaking in a peer review is asked to hand in two programs: a 'best' program and one of lesser quality. These programs are then randomly distributed amongst the participants. Each participant assesses four programs: two 'best' programs and two programs of lesser quality. After all the results have been collected, each participant gets the (anonymous) evaluations of their programs, as well as the statistics of the whole test.

The primary goal of this test is to give the programmer insight into his own capabilities. The practice of peer reviews shows that programmers are quite capable of assessing the quality of their peers' software.

A necessary precondition for successfully reading someone else's code is a business-like attitude. Weinberg (1971) coined the term egoless programming for this. Many programmers view their code as something personal, like a diary. Derogatory remarks ('how could you be so stupid as to forget that initialization') can disastrously impair the effectiveness of such assessments. The opportunity for such an antisocial attitude to occur seems to be somewhat smaller with the more formalized manual techniques.

Walkthroughs and inspections are both manual techniques that spring from the traditional desk-checking of program code. In both cases, it concerns teamwork and the product to be inspected is evaluated in a formal session, following precise procedures.

Inspections are sometimes called Fagan inspections, after their originator (Fagan, 1976, 1986). In an inspection, the code to be assessed is gone through, statement by statement. The members of the inspection team (usually four people) get the code, its specification, and the associated documents a few days before the session takes place.

Each member of the inspection team has a well-defined role. The moderator is responsible for the organization of inspection meetings. He chairs the meeting and ascertains that follow-up actions agreed upon during the meeting are indeed performed. The moderator must ensure that the meeting is conducted in a businesslike, constructive way and that the participants follow the correct procedures and act as a team. The team usually has two inspectors or readers, knowledgeable peers that paraphrase the code. Finally, the code author is a largely silent observer. He knows the code to be inspected all too well and is easily inclined to express what he intended rather than what is actually written down. He may, though, be consulted by the inspectors.

During the formal session, the inspectors paraphrase the code, usually a few lines at a time. They express the meaning of the text at a higher level of abstraction than what is actually written down. This gives rise to questions and discussions which may lead to the discovery of faults. At the same time, the code is analyzed using a checklist of faults that often occur. Examples of possible entries in this checklist are:

The result of the session is a list of problems identified.

These problems are not resolved during the formal session itself. This might easily lead to quick fixes and distract the team from its primary goal. After the meeting, the code author resolves all the issues raised and the revised code is verified once again. Depending on the number of problems identified and their severity, this second inspection may be done by the moderator only or by the complete inspection team.

Since the goal of an inspection is to identify as many problems as possible in order to improve the quality of the software to be developed, it is important to maintain a constructive attitude towards the developer whose code is being assessed.^[23] The results of an inspection therefore are often marked confidential. These results should certainly not play a role in the formal assessment of the developer in question.

In a walkthrough, the team is guided through the code using test data. The test data is mostly of a fairly simple kind, otherwise tracing the program logic soon becomes too complicated. The test data serves as a way of starting a discussion, rather than as a serious test of the program. In each step of this process, the developer may be questioned regarding the rationale of the decisions. In many cases, a walkthrough boils down to some sort of manual simulation.

Both walkthroughs and inspections may profitably be applied at all stages of the software life cycle. The only precondition is that there is a clear, testable document. It is estimated that these review methods detect 50–90% of defects (Boehm and Basili, 2001). Both techniques serve not only to find faults: if properly applied, these techniques may help to promote team spirit and morale. At the technical level, the people involved may learn from each other and enrich their knowledge of algorithms, programming style, programming techniques, error-prone constructions, and so on. Thus, these techniques also serve as a vehicle for process improvement. Under the general umbrella of 'peer reviews', they are part of the CMM level 3 key process area Verification (see Section 6.6).

A potential danger of this type of review is that it remains too shallow. The people involved may become overwhelmed with information; they may have insufficient knowledge of the problem domain; their responsibilities may not have been clearly delineated. As a result, the review process does not pay off sufficiently.

Parnas and Weiss (1987) describe a type of review process in which the people involved have to play a more active role. They distinguish between different types of specialized design review. Each of these reviews concentrates on certain desirable properties of the design. As a consequence, the responsibilities of the people involved are clear. The reviewers have to answer a list of questions ('under which conditions may this function be called?', 'what is the effect of this function on the behavior of other functions?', and so on). In this way, the reviewers are forced to study carefully the design information received. Problems with the questionnaire and documentation can be posed to the developers, and the completed questionnaires are discussed by the developers and reviewers. Experiments suggest that inspections with specialized review roles are more effective than inspections in which review roles are not specialized.

A very important component of Fagan inspections is the meeting in which the document is discussed. Since meetings may incur considerable costs or time-lags, one may try to do without them. Experiments suggest that the added value of group meetings, in terms of the number of problems identified, is quite small.

The most complete static analysis technique is the proof of correctness. In a proof of correctness we try to prove that a program meets its specification. In order to be able to do so, the specification must be expressed formally. We mostly do this by expressing the specification in terms of two assertions which hold before and after the program's execution, respectively. Next, we prove that the program transforms one assertion (the precondition) into the other (the postcondition). This is generally denoted as:

{P} S {Q}

Here, S is the program, P is the precondition, and Q is the postcondition. Termination of the program is usually proved separately. The above notation should thus be read as: if P holds before the execution of S and S terminates, then Q holds after the execution of S.

Formally verifying the correctness of a not-too-trivial program is a very complex affair. Some sort of tool support is helpful, therefore. Tools in this area are often based on heuristics and proceed interactively.

Correctness proofs are very formal and, for that reason, they are often difficult for the average programmer to construct. The value of formal correctness proofs is sometimes disputed. We may state that the thrust in software is more important than some formal correctness criterion. Also, we cannot formally prove every desirable property of software. Whether we built the right system can only be decided upon through testing (validation).

On the other hand, it seems justified to state that a thorough knowledge of this type of formal technique will result in better software.

In the top-down development of software components, we often employ stepwise refinement. At a certain level of abstraction, the function to be executed will be denoted by a description of that function. At the next level, this description is decomposed into more basic units.

Stepwise abstraction is just the opposite. Starting from the instructions of the source code, the function of the component is built up in a number of steps. The function thus derived should comply with the function as described in the design or requirements specification.

To illustrate this technique, consider the search routine of Figure 13.4. We know, from the accompanying documentation for instance, that the elements in array a (from index 1 up to index a.length) are sorted when this routine is called.

Figure 13.4. A search routine

We start the stepwise abstraction with the instructions of the if statement on lines 6–13. x is compared with a[mid]. Depending on the result of this comparison, one of high, low, and found is given a new value. If we take into account the assignments on lines 3 and 5, the function of this if statement can be summarized as

stop searching (found = true) if x == a[mid], or
shorten the interval [low .. high] that might contain x, to an interval
[low' .. high'], where high' — low' < high - low

Alternatively, this may be described as a postcondition to the if statement:

(found == true and x == a[mid]) or
(found == false and x ∉ a[1 .. low' - 1] and
    x ∉ a[high' + 1 .. a.length] and high' - low' < high - low)

Next, we consider the loop in lines 4–14, together with the initialization on line 3. As regards termination of the loop, we may observe the following. If 1 ≤ a.length upon calling the routine, then low ≤ high at the first execution of lines 4–14. From this, it follows that low ≤ mid ≤ high. If the element searched for is found, the loop stops and the position of that element is returned. Otherwise, either high is assigned a smaller value, or low is assigned a higher value. Thus, the interval [low .. high] gets smaller. At some point in time, the interval will have length of 1, i.e. low = high (assuming the element still is not found). Then, mid will be assigned that same value. If x still does not occur at position mid, either high will be assigned the value low − 1, or low will be assigned the value high + 1. In both cases, low > high and the loop terminates. Together with the postcondition given earlier, it then follows that x does not occur in the array a. The function of the complete routine can then be described as:

result = 0  x ∉ a[1 .. a.length]
1 ≤ result ≤ a.length   x = a[result]

So, stepwise abstraction is a bottom-up process to deduce the function of a piece of program text from that text.

During the execution of a program, we follow a certain path through its control graph. If some node has multiple outgoing edges, we choose one of those (which is also called a branch). In the ideal case, the tests collectively traverse all possible paths. This all-paths coverage is equivalent to exhaustively testing the program.

In general, this is not possible. A loop often results in an infinite number of possible paths. If we do not have loops, but only branch instructions, the number of possible paths increases exponentially with the number of branching points. There may also be paths that are never executed (quite likely, the program contains a fault in that case). We therefore search for a criterion which expresses the degree to which the test data approximates the ideal coverage.

Many such criteria can be devised. The most obvious is the criterion which counts the number of statements (nodes in the graph) executed. It is called the all-nodes coverage, or statement coverage. This criterion is rather weak because it is relatively simple to construct examples in which 100% statement coverage is achieved, while the program is nevertheless incorrect.

Consider as an example the program given in Figure 13.5. It is easy to see that a single test, with n = 2, a[1] = 5, a[2] = 3, results in each statement being executed at least once. So, this one test achieves 100% statement coverage. However, if we change, for example, the test a[i] ≥ a[i - 1] in line 6 to a[i] = a[i - 1], we still obtain a 100% statement coverage with this test. Although this test also yields the correct answer, the changed program is incorrect.

We get a stronger criterion if we require that, at each branching node in the control graph, all possible branches are chosen at least once. This is known as all-edges coverage or branch coverage. Here too, 100% coverage is no guarantee of program correctness.

Nodes that contain a condition, such as the Boolean expression in an if statement, can be a combination of elementary predicates connected by logical operators. A condition of the form

i > 0 or j > 0

requires at least two tests to guarantee that both branches are taken. For example,

i = 1, j = 1

and

i = 0, j = 1

will do. Other possible combinations of truth values of the atomic predicates (i= 1, j= 0 and i= 0, j = 0) need not be considered to achieve branch coverage. Multiple condition coverage requires that all possible combinations of elementary predicates in conditions be covered by the test set. This criterion is also known as extended branch coverage.

Finally, McCabe's cyclomatic complexity metric (McCabe, 1976) has also been applied to testing. This criterion is also based on the control graph representation of a program. A basis set is a maximal linearly independent set of paths through a graph. The cyclomatic complexity (CV) equals this number of linearly independent paths (see also Section 12.1.4). Its formula is

Here, V(G) is the graph's cyclomatic number:

where

As an example, consider the program text of Figure 13.6. The corresponding control graph is given in Figure 13.7. For this graph, e = 15, n = 13, and p = 1. So V(G) = 3 and CV(G) = 4. A possible set of linearly independent paths for this graph is: {1-2-3-4-5-6-7-8-9-12-4, 5–7, 8-10-11, 4–13}.

Figure 13.6. An insertion routine

A possible test strategy is to construct a test set such that all linearly independent paths are covered. This adequacy criterion is known as the cyclomatic-number criterion.

Starting from the control graph of a program, we may also consider how variables are treated along the various paths. This is termed data flow analysis. With data flow analysis too, we may define test adequacy criteria and use these criteria to guide testing.

In data flow analysis, we consider the definitions and uses of variables along execution paths. A variable is defined in a certain statement if it is assigned a (new) value because of the execution of that statement. After that, the new value is used in subsequent statements. A definition in statement X is alive in statement Y if there exists a path from X to Y in which that variable is not assigned a new value at some intermediate node. In the example in Figure 13.5, for instance, the definition of flag at line 4 is still alive at line 9 but not at line 10. A path such as the one from line 4 to 9 is called definition-clear (with respect to flag). Algorithms to determine such facts are commonly used in compilers in order to allocate variables optimally to machine registers.

Figure 13.7. Control-flow graph of the insert routine from Figure 13.6

We distinguish between two types of variable use: P-uses and C-uses. P-uses are predicate uses, such as those in the conditional part of an if statement. All other uses are C-uses. Examples of the latter are uses in computations or I/O statements.

A possible test strategy is to construct tests which traverse a definition-clear path between each definition of a variable to each (P- or C-) use of that definition and each successor of that use. (We have to include each successor of a use to force all branches following a P-use to be taken.) We are then sure that each possible use of a definition is being tested. This strategy is known as all-uses coverage. A slightly stronger criterion requires that each definition-clear path is either cycle-free or a simple cycle. This is known as all-DU-paths coverage. Several weaker data flow criteria can be defined as well:

Program code can be easily transformed into a graph model, thus allowing for all kinds of test adequacy criteria based on graphs. Requirements specifications, however, may also be transformed into a graph model. As a consequence, the various coverage-based adequacy criteria can be used in both black-box and white-box testing techniques.

Consider the example fragment of a requirements specification document for our library system in Figure 13.8. We may rephrase these requirements a bit and present them in the form of elementary requirements and relations between them. The result can be depicted as a graph, where the nodes denote elementary requirements and the edges denote relations between elementary requirements; see Figure 13.9. We may use this graph model to derive test cases and apply any of the control-flow coverage criteria to assess their adequacy.

Figure 13.8. A requirements specification fragment

A very similar route can be followed if the requirement is expressed in the form of a use case. Figure 13.10 gives a possible rewording of the fragment from Figure 13.8. It uses the format from (Cockburn, 2001). The use case describes both the normal case, called the Main Success Scenario, as well as extensions that cover situations that branch off the normal path because of some condition. For each extension, both the condition and the steps taken are listed. Note that Figure 13.9 directly mimics the use case description from Figure 13.10. The use case description also allows us to straightforwardly derive test cases and apply control-flow coverage criteria.

Figure 13.9. Graph model of Figure 13.8

Generally speaking, a major problem in determining a set of test cases is to partition the program domain into a (small) number of equivalence classes. We try to do so in such a way that testing a representative element from a class suffices for the whole class. Using control-flow coverage criteria, for example, we assume that any test of some node or branch is as good as any other such test. In the above example, for instance, we assume that any execution of the node labeled 'check dept. budget' will do.

The weak point in this procedure is the underlying assumption that the program behaves equivalently on all data from a given class. If this assumption is true, the partition is perfect and so is the test set. This assumption will not hold, in general (see also Section 13.1.2).

Figure 13.10. Use case description of Figure 13.8

Text books on statistics often contain examples along the following lines:

If we want to estimate the number of pikes in Lake Soft, we proceed as follows:

Supposing that M′ out of the M pikes are found to be marked, the total number of pikes originally present in Lake Soft is then estimated as (M - M′) × N/M′.

A somewhat unsophisticated technique is to try to estimate the number of faults in a program in a similar way. The easiest way to do this is to artificially seed a number of faults in the program. When the program is tested, we discover both seeded faults and new ones. The total number of faults is then estimated from the ratio of those two numbers.

We must be aware of the fact that a number of assumptions underlie this method — amongst others, the assumption that both real and seeded faults have the same distribution.

There are various ways of determining which faults to seed in the program. A not very satisfactory technique is to construct them by hand. It is unlikely that we will be able to construct very realistic faults in this way. Faults thought up by one person have a fair chance of having been thought up already by the person that wrote the software.

Another technique is to have the program independently tested by two groups. The faults found by the first group can then be considered seeded faults for the second group. In using this technique, though, we must realize that there is a chance that both groups detect (the same type of) simple faults. As a result, the picture might well be distorted.

A useful rule of thumb for this technique is the following: if we find many seeded faults and relatively few others, the result can be trusted. The opposite is not true. This rule of thumb is more generally applicable: if, during testing of a certain component, many faults are found, it should not be taken as a positive sign. Quite the contrary, it is an indication that the component is probably of low quality. As Myers (1979) observed: 'The probability of the existence of more errors in a section of a program is proportional to the number of errors already found in that section.' The same phenomenon has been observed in some experiments, where a strong linear relationship was found between the number of defects discovered during early phases of development and the number of defects discovered later.

Suppose we have some program P which produces the correct results for some tests T₁ and T₂. We generate some variant P′ of P. P′ differs from P in just one place. For instance, a + is replaced by a —, or the value v₁ in a loop of the form

for (var = v1; var < v2; var++)

is changed into v₁ + 1 or v₁ − 1. Next, P′ is tested using tests T₁ and T₂. Let us assume that T₁ produces the same result in both cases, whereas T₂ produces different results. Then T₁ is the more interesting test case, since it does not discriminate between two variants of a program, one of which is certainly wrong.

In mutation testing, we generate a (large) number of variants of a program. Each of those variants, or mutants, slightly differs from the original version. Usually, mutants are obtained by mechanically applying a set of simple transformations called mutation operators (see Table 13.5).

Next, all these mutants are executed using a given test set. As soon as a test produces a different result for one of the mutants, that mutant is said to be dead. Mutants that produce the same results for all of the tests are said to be alive. As an example, consider the erroneous sort procedure in Figure 13.3 and the correct variant thereof which compares array elements rather than their absolute values. Tests with an array which happens to contain positive numbers only will leave both variants alive. If a test set leaves us with many live mutants, then that test set is of low quality, since it is not able to discriminate between all kinds of variant of a given program.

If we assume that the number of mutants that is equivalent to the original program is 0 (normally, this number will certainly be very small), then the mutation adequacy score of a test set equals D/M, where D is the number of dead mutants and M is the total number of mutants.

There are two major variants of mutation testing: strong mutation testing and weak mutation testing. Suppose we have a program P with a component T. In strong mutation testing, we require that tests produce different results for program P and a mutant P′. In weak mutation testing, we only require that component T and its mutant T3 produce different results. At the level of P, this difference need not crop up. Weak mutation adequacy is often easier to establish. Consider a component T of the form

if (x < 4.5) ...

We may then compute a series of mutants of T, such as

if (x > 4.5) ...
if (x = 4.5) ...
if (x > 4.6) ...

if (x < 4.4) ...
...

Next, we have to devise a test set that produces different results for the original component T and at least one of its variants. This test set is then adequate for T.

Mutation testing is based on two assumptions: the competent programmer hypothesis and the coupling effect hypothesis. The competent programmer hypothesis states that competent programmers write programs that are 'close' to being correct. So the program written may be incorrect but it differs from a correct version by relatively minor faults. If this hypothesis is true, we should be able to detect these faults by testing variants that differ slightly from the correct program, i.e. mutants. The coupling effect hypothesis states that tests that can reveal simple faults can also reveal complex faults. Experiments give some empirical evidence for these hypotheses.

A question that may be raised is whether, say, the all-uses adequacy criterion is stronger or weaker than the all-nodes or all-edges adequacy criteria. We may define the notion 'stronger' as follows: criterion X is stronger than criterion Y if, for all programs P and all test sets T, X adequacy implies Y adequacy. In the testing literature, this relation is known as 'subsume'. In this sense, the all-edges criterion is stronger than (subsumes) the all-nodes criterion. The all-uses criterion, however, is not stronger than the all-nodes criterion. This is caused by the fact that programs may contain statements which only refer to constants. For the following program:

if (a < b)
    System.out.println("0");
    else System.out.println("1");

the all-uses criterion will be satisfied by any non-empty test set, since this criterion does not require that each statement be executed. If we ignore references to constants, the all-uses criterion is stronger than the all-nodes criterion. With the same exception, the all-uses criterion is also stronger than the all-edges criterion.

A problem with any graph-based adequacy criterion is that it can only deal with paths that can be executed (feasible paths). Paths which cannot be executed are known as 'infeasible paths'. Infeasible paths result if parts of the graph are unreachable, as in

if (true)
    x = 1;
else
    x = 2;

The else branch is never executed, yet most adequacy criteria require this branch to be taken. Paths that are infeasible also result from loops. If a loop is of the form

for (i = 1; i < 10; i++)
    body

all feasible paths that traverse the resulting cycle in the graph will do so exactly ten times.

There does not exist a simple linear scale along which the strength of all program-based adequacy criteria can be depicted. For the criteria discussed in Sections 13.5 to 13.7, the subsume hierarchy is depicted in Figure 13.12, as far as it is known. An arrow A → B indicates that A is stronger than (subsumes) B. In most cases, the subsume relation holds for both the feasible and not feasible versions of the criteria. Arrows adorned with an asterisk denote relations which hold only for the not feasible version.

The subsume relation compares the thoroughness of test techniques, not their ability to detect faults. If an adequacy criterion is used to generate the next test case, the subsume relations of Figure 13.12 do not necessarily imply better fault detection. However, if some other tool is used to generate test cases, and the criterion is only used to decide when to stop testing, a stronger adequacy criterion implies better fault detection as well.

The theoretical upper bounds for the number of test cases needed to satisfy most of the coverage-based adequacy criteria are quadratic or exponential. Empirical studies, however, show that, in practice, these criteria are usually linear in the number of conditional statements.

A major problem with any test technique is to decide when to stop testing. As noted, functional and structural test techniques provide only weak means for doing so. Weyuker (1988) provides an interesting set of properties of test adequacy criteria. Although it is intuitively clear that any test adequacy criterion should satisfy all of the properties listed, it turns out that even some of the well-known test techniques such as all-nodes coverage and all-edges coverage fail to satisfy several of them.

Figure 13.12. Subsume hierarchy for program-based adequacy criteria

The characteristics identified relate to program-based adequacy criteria, i.e. criteria that involve the program's structure. The first four criteria, however, are fairly general and should apply to any test adequacy criterion. The following 11 properties are identified in (Weyuker, 1988):^[24]

As noted, the all-nodes and all-edges coverage metrics fail to satisfy the applicability criterion. This is rather unsatisfactory, since it implies that we may not be able to decide whether testing has been adequate. If 50% coverage has been obtained using either of these criteria, we do not know whether additional tests will help. It may be that the other 50% of the statements or branches is not executed by any input.

Both the all-nodes and all-edges criteria do not satisfy the antidecomposition and anticomposition criteria either. For example, if all statements of individual components are executed using some given test set, then this same test set is likely to satisfy that criterion on their composition. Further research along these lines is expected to deepen our insight into what test techniques may or may not accomplish.

The most common techniques for unit testing have been discussed in the previous sections. The effectiveness of those techniques is discussed by Basili and Selby (1987). They describe an experiment in which both professional programmers and students participated. Three techniques were compared:

Basili and Selby compared the effectiveness of these techniques as regards detecting faults, the associated costs, and the kinds of faults found. Some of the results of this experiment were:

Other experiments also indicate that there is no uniform 'best' test technique. Different test techniques tend to reveal different types of fault. The use of multiple test techniques certainly results in the discovery of more faults. It is difficult though to ascribe the discovery of faults to the use of a specific technique. It may well be that the mere fact that test techniques force us to pay systematic attention to the software is largely responsible for their success.

Several studies have reported on the fault-detection capabilities of (Fagan) inspections. Myers (1988) reports that about 85% of the major errors in the Space Shuttle software were found during early inspections. Inspections have been found to be superior to other manual techniques such as walkthroughs. Inspections were also found to have the additional benefit of improving both quality and productivity. There is some controversy about the added value of group meetings.

Finally, there is ample empirical evidence that early attention to fault detection and removal really pays off. Boehm's data, presented in the introduction to this chapter, can be augmented by other results, such as those of Collofello and Woodfield (1989). His data stems from a large real-time software project, consisting of about 700 000 lines of code developed by over 400 people. Some of his findings are reproduced in Table 13.6. For example, of the 676 design faults that could have been caught, 365 were caught during the design review (= 54%). The overall design review efficiency was not much different from code review efficiency, while the testing phase was somewhat less efficient. The latter is not all that surprising, since the design and code reviews are likely to have removed many of the faults that were easy to detect. These results again suggest that the use of multiple techniques is preferable to the use of a single technique.

The results become much more skewed if we take into account the cost-effectiveness of the different test techniques. The cost-effectiveness metric used is the ratio of 'costs saved by the process' to 'costs consumed by the process'. The costs saved by the process are the costs that would have been spent if the process had not been performed and faults had to be corrected later. The cost-effectiveness results found in this study are given in Table 13.7. These results indicate that, for every hour spent in design reviews and correcting design faults, more than eight hours of work are saved. The cost-effectiveness of the testing phase itself is remarkably low. This is not really surprising, since much time is wasted during the actual testing phase in performing tests that do not reveal any faults. These findings once more confirm the statement that early testing really pays off.