The first five chapters of this book help practical testers fill up their “toolbox” with various test criteria. While studying test criteria in isolation is needed, one of the most difficult obstacles to a software organization moving to level 3 or 4 testing is integrating effective testing strategies into the overall software development process. This chapter discusses various issues involved with applying test criteria during software development. The overriding philosophy is to think: if the tester looks at this as a technical problem, and seeks technical solutions, he or she will usually find that the obstacles are not as large as they first seem.

REGRESSION TESTING

Regression testing is the process of re-testing software that has been modified. Regression testing constitutes the vast majority of testing effort in commercial software development and is an essential part of any viable software development process. Large components or systems tend to have large regression test suites. Even though many developers don't want to believe it (even when faced with indisputable evidence!), small changes to one part of a system often cause problems in distant parts of the system. Regression testing is used to find this kind of problem.

It is worth emphasizing that regression tests must be automated. Indeed, it could be said that unautomated regression testing is equivalent to no regression testing. A wide variety of commercially available tools are available.

Test criteria are used in several ways, but the most common way is to evaluate tests. That is, sets of test cases are evaluated by how well they cover a criterion. Applying criteria this way is prohibitively expensive, so automated coverage analysis tools are needed to support the tester. A coverage analysis tool accepts a test criterion, a program under test, and a collection of test cases, and computes the amount of coverage of the tests on the program under test. This chapter discusses the design techniques used in these tools. We do not discuss individual tools, although many are available. We also do not discuss the user interface issues, but focus on the core internal algorithms for measuring coverage.

INSTRUMENTATION FOR GRAPH AND LOGICAL EXPRESSION CRITERIA

The primary mechanism used to measure coverage is instrumentation. An instrument is additional program code that does not change the functional behavior of the program but collects some additional information. The instrument can affect the timing in a real-time system, and could also affect concurrency. Thus, such applications require special attention. Careful design can make instrumentation very efficient.

For test criteria coverage, the additional information is whether individual test requirements have been met. An initial example of instrumentation is shown in Figure 8.1. It illustrates a statement that is added to record if the body of an “ifblock” has been reached.

This chapter discusses how to engineer the criteria from Chapters 2 through 5 to be used with several different types of technologies. These technologies have come to prominence after much of the research literature in software testing, but are now very common and account for a large percentage of new applications being built. Sometimes we modify the criteria, and sometimes simply discuss how to build the models that the existing criteria can be applied to. Some of these technologies, such as Web applications and embedded software, tend to have extremely high reliability requirements. So testing is crucial to the success of the applications. The chapter explains what is different about these technologies from a testing viewpoint, and summarizes some of the existing approaches to testing software that uses the technologies.

Object-oriented technologies became prominent in the mid-1990s and researchers have spent quite a bit of time studying their unique problems. A number of issues with object-oriented software have been discussed in previous chapters, including various aspects of applying graph criteria in Chapter 2, integration mutation in Chapter 5 and the CITO problem in Chapter 6. This chapter looks into how the use of classes affects testing, and focuses on some challenges that researchers have only started addressing. Most of these solutions that have not yet made their way into automated tools. The most important of these challenges is testing for problems in the use of inheritance, polymorphism, and dynamic binding.

We end this book with a discussion of three challenging areas in testing software. Although researchers have been interested in emergent properties for many years, the area, far from being “solved,” continues to escalate in terms of importance for industry. Likewise, testability is attracting renewed attention due to characteristics of some of the newer software technologies. Finally, we suggest some directions for software testing in practice and in the research arena.

TESTING FOR EMERGENT PROPERTIES: SAFETY AND SECURITY

Testing for emergent properties presents special challenges. This section offers high level guidance for engineers faced with testing systems where safety and/or security play an important role.

Emergent properties arise as a result of collecting components together into a single system. They do not exist independently in any particular component. Safety and security are classic emergent properties in system design. For example, the overall safety of an airplane is not determined by the control software by itself, or the engines by themselves, or by any other component by itself. Certainly, the individual behavior of a given component may be extremely important with respect to overall safety, but, even so, the overall safety is determined by the interactions of all of these components when assembled into a complete airplane. In other words, an airplane engine is neither safe nor unsafe considered by itself because an airplane engine doesn't fly by itself.

As mentioned before, by inserting a constraint into a program, we shrink the domain for which it is defined. To reverse this process, we need to be able to speak of, and make use of, a set of subprograms. To this end, a new programming construct called a program set is now introduced. The meaning of a program set, or a set of programs, is identical to the conventional notion of a set of other objects. As usual, a set of n programs is denoted by {P1, P2, …, Pn}. When used as a programming construct, it describes the computation prescribed by its elements. Formally, the semantics of such a set is defined in Axiom 4.1.

Axiom 4.1

wp({P1, P2, …, Pn}, R) ≡ wp(P1, R) ⋁ wp(P2, R) ⋁ … ⋁ wp(Pn, R).

The choice of this particular semantics is explained in detail at the end of this chapter. A program set so defined has all properties commonly found in an ordinary set. For instance, because the logical operation of disjunction is commutative, a direct consequence of Axiom 4.1 is Corollary 4.2.

Corollary 4.2

The ordering of elements in a program set is immaterial, i.e.,

{P1, P2} ⇔ {P2, P1}.

Furthermore, because every proposition is an idempotent under the operation of disjunction, we have Corollary 4.3.

Corollary 4.3

P ⇔ {P} ⇔ {P, P} for any program P.

In words, a set is unchanged by listing any of its elements more than once.

In this chapter we discuss the concept of pathwise decomposition in more detail. First, we need to formally define some terms so that we can speak precisely and concisely.

In abstract, by pathwise decomposition we mean the process of rewriting a program into an equivalent program set, consisting of more than one element. To be more precise, we have the following definition.

Definition 5.1a

Given a piece of source code /\C;S, to decompose it pathwise is to find a program set {/\C1;S1, /\C2;S2, …, /\Cn;Sn} such that

1. /\C;S ⇔ {/\C1;S1, /\C2;S2, …, /\Cn;Sn},

2. n > 1,

3. Ci ⋀ Cj ≡ F for any i ≠ j, and

4. C1 ⋁ C2 ⋁… ⋁ Cn. ≡ C.

Presumably, it is written to implement a function that can be decomposed pathwise, as subsequently described.

Definition 5.1b

Given a function, say, f, to decompose it pathwise is to rewrite it in such a way that it includes a description of the following elements:

1. f: X → Y,

2. f = {f1, f2,…, fm},

3. X = X1 ⋃ X2 ⋃… ⋃ Xm,

4. fi: Xi → Y for all 1 ≤ i ≤ m.

Definition 5.2a

A set {/\C1;S1, /\C2;S2,…, /\Cn;Sn} of subprograms is said to be compact if, for any i ≠ j, Ci ⋀ Cj ≡ F implies that Si is not logically equivalent to Sj.

Intuitively, a program set is said to be compact if every subprogram computes a different function. We can characterize a set of subfunctions in a similar manner.

Consider a restrictive clause of this form:

By program state here we mean the aggregate of values assumed by all variables involved. Because this clause constrains the states assumable by the program, it is called a state constraint, or a constraint for short, and is denoted by /\C.

State constraints are designed to be inserted into a program to create another program. For instance, given a program of the form of Program 2.1, a new program can be created, as shown in Program 2.2.

Program 2.1

S1; S2.

Program 2.2

S1; /\C; S2.

Program 2.2 is said to be created from Program 2.1 by constraining the program states to C prior to execution of S2. Intuitively, 2.2 is a subprogram of 2.1 because its definition is that of 2.1 restricted to C. Within that restriction, 2.2 performs the same computation as 2.1.

A state constraint is a semantic modifier. The meaning of a program modified by a state constraint can be formally defined in terms of Dijkstra's (1976) weakest precondition as follows. Let S be a programming construct and C be a predicate, then for any postcondition R,

Axiom 2.3

wp(/\C;S, R) ≡ C ⋀ wp(S, R).

Of course a constraint can also be inserted after a program.

Program analysis is a problem area concerned with methodical extraction of information from programs. It has attracted a great deal of attention from computer scientists since the inception of computer science as an academic discipline. Earlier research efforts were mostly motivated by problems encountered in compiler construction (Aho and Ullman, 1973). Subsequently, the problem area was expanded to include those that arise from development of computer-aided software engineering tools, such as the question of how to detect certain programming errors through static analysis (Fosdick and Osterweil, 1976).

By the mid-1980s, the scope of research in program analysis had greatly expanded to include, among others, investigation of problems in data-flow equations, type inference, and closure analysis. Each of these problem areas was regarded as a separate research domain with its own terminology, problems, and solutions.

Gradually, efforts to extend the methods started to emerge and to produce interesting results. It is now understood that those seemingly disparate problems are related, and we can gain much by studying them in a unified conceptual framework. As the result, there has been a dramatic shift in the research directions in recent years. A great deal of research effort has been directed to investigate the possibilities of extending and combining existent results [see, e.g., Aiken (1999); Amtoft et al. (1999); Cousot and Cousot (1977); Flanagan and Qadeer (2003); and Jones and Nielson (1995)].

In the prevailing terminology, we can say that there are four major approaches to program analysis, viz., data-flow analysis, constraint-based analysis, abstract interpretation, and type-and-effect system (Nielson et al., 2005).

Presented in this appendix are four examples showing in various degrees of detail how the present method can be applied to programs written in C++.

Example A.1 shows how to insert constraints into a program to form a subprogram representing an execution path. It also shows how the rules developed in Chapter 3 can be used to simplify the subprogram to the extent possible.

Example A.2 shows that the present method is not only applicable to an execution path but also to the one that includes a loop construct as well. The analysis is done for all possible execution paths in the program, and thus the result constitutes a direct proof of the correctness.

The program in Example A.3 is adopted from a legacy software tool. A portion of this program (printed in boldface type) is difficult to understand. When the present method was used to analyze that part of the program, it was found that it consists of only nine feasible execution paths, despite of the fact that it contains three “for” loops and six “if” statements. Furthermore, it was found that all the path subprograms can be greatly simplified to explicate the function of the program.

The program in Example A.4 is a stack class. It is used to illustrate how the present method can be applied to an object-oriented program.

As demonstrated in the preceding chapters, inserting certain state constraints into a program often allows the resulting program to be simplified. The program so produced, however, is in general a subprogram of the original program. To simplify a program, therefore, one needs to simplify a set of its subprograms, and then recompose the program from the simplified subprograms. Now, if the inserted constraint is tautological (see Definition 3.9), the resulting program is equivalent to the original. Therefore, we may be able to simplify a program directly by using tautological constraints. The ability to find tautological constraints is important in that, when we work with a loop construct, we often need to find its loop invariants that may allow us to simplify the loop body. Because a loop invariant is a condition that is true just before the loop is entered, the tautological constraints that immediately precede the loop construct often give us the clues as to what might be the invariant of that loop. Subsequently given is a set of relations that can be used for this purpose.

Corollary 6.1

/\Q; x := E ⇔ /\Q; x := E;/\(Q′ ⋀ x = E′)x′→E−1

where (Q′ ⋀ x = E′)x′→E−1 is a predicate we construct by following the subsequent steps:

We obtain Q′ and E′ from Q and E, respectively, by replacing every occurrence of x with x′, and then replacing every occurrence of x′ with E−1.

Many years ago, I was given the responsibility of leading a large software project. The aspect of the project that worried me the most was the correctness of the programs produced. Whenever a part of the product became suspect, I could not put my mind to rest until the product was tested successfully with a well-chosen set of test cases and until I was able to understand the source code in question clearly and completely. It was not always easy to understand. That was when I started to search for ways to facilitate program understanding.

A program can be difficult to understand for many reasons. The difficulty may stem, for example, from the reader's unfamiliarity with the application area, from the obscurity of the algorithm implemented, or from the complex logic used in organizing the source code. Given the different reasons that difficulty may arise, a single comprehensive solution to this problem may never be found.

I realized, however, that the creator of a program must always decompose the task to be performed by the program to the extent that it can be prescribed in terms of the programming language used. If the reader could see exactly how the task was decomposed, the difficulty of understanding the code would be eased because the reader could separately process each subprogram, which would be smaller in size and complexity than the program as a whole.