. Major research results in the area of software testing techniques:

This diagram shows the most influential ideas, theory, methods and practices in the area of software testing,

emphasizing on testing techniques. There are two columns in the diagram marked “Concept” and “Theory

&Methods”. The items appear in “Concept” column contains the leading technical viewpoints about the goals of

testing software since the year 1950. The two sub-columns of “Theory & Method” classify theoretical and

methodological research results in functional-based and structural-based.

7

Before the year 1975, although software testing was widely performed as an important part of software

development, it remained an intuitive, somehow ad hoc collection of methods. People used principle

functional and structural techniques in their testing practices, but there was little systematic research on

methods or theories of these techniques.

In 1975, Goodenough and Gerhart gave the fundamental theorem of testing in their paper Toward a Theory

of Test Data Selection [5]. This is the first published research attempting to provide a theoretical

foundation for testing, which characterizes that a test data selection strategy is completely effective if it is

guaranteed to discover any error in a program. As is mentioned in section 2, this gave testing a direction to

uncover errors instead of not finding them. The limitation of the ideas in this paper is also analyzed in

previous section. Their research led to a series of successive research on the theory of testing techniques.

In the same year, Huang pointed out that the common test data selection criterion – having each and every

statement in the program executed at least once during the test – leaves some important classes of errors

undetected [10]. As a refinement of statement testing criterion, edge strategy, was given. The main idea

for this strategy is to exercise every edge in the program diagraph at least once. Probe insertion, a very

useful testing technique in later testing practices was also given in this research.

Another significant test selection strategy, the path testing approach, appeared in 1976. In his research,

Howden gave the strategy that test data is selected so that each path through a program is traversed at least

once [8]. Since the set of program paths is always infinite, in practice, only a subset of the possibly infinite

set of program paths can be tested. Studies of the reliability of path testing are interesting since they

provide an upper bound on the reliability of strategies that call for the testing of a subset of a program’s

paths.

The year 1980 saw two important theoretical studies for testing techniques, one on functional testing and

one on s tructural.

Although functional testing had been widely used and found useful in academic and industry practices,

there was little theoretical research on functional testing. The first theoretical approach towards how

systematic design methods can be used to construct functional tests was given in 1980 [9]. Howden

discussed the idea of design functions, which often correspond to sections of code documented by

comments, which describe the effect of the function. The paper indicates how systematic design methods,

such as structured design methodology, can be used to construct functional tests.

The other 1980 research was on structural testing. If a subset of a program’s input domain causes the

program to follow an incorrect path, the error is called a domain error. Domain errors can be caused by

incorrect predicates in branching statements or by incorrect computations that affect variables in branch

statement predicates. White and Cohen proposed a set of constraints under which to select test data to find

domain errors [18]. The paper also provides useful insight into why testing succeeds or fails and indicates

directions for continued research.

The dawn of data flow analysis for structural testing was in 1985. Rapps and Weyuker gave a family of

test data selection criteria based on data flow analysis [16]. They contend the defect of path selection

criteria is that some program errors can go undetected. A family of path selection criteria is introduced

followed by a discussion of the interrelationships between these criteria. This paper also addresses the

problem of appropriate test data selection. This paper founded the theoretical basis for data-flow based

program testing techniques.

In 1989, Richardson and colleagues proposed one of the earliest approaches focusing on utilizing

specifications in selecting test cases [14]. In traditional specification-based functional testing, test cases are

selected by hand based on a requirement specification, thus makes functional testing consist merely

heuristic criteria. Structural testing, on the other hand, has the advantage of that the applications can be

automated and the satisfaction determined. The authors extended implementation-based techniques to be

applicable with formal specification languages and to provide a testing methodology that combines

8

specification-based and implementation-based techniques. This research appeared to be the first to

combine the idea of structural testing, functional testing, and formal specifications.

Another research towards specification-based testing appeared in 1990. Boolean algebra is the most basic

of all logic systems and many logical analysis tools incorporate methods to simplify, transform, and check

specifications. Consistency and completeness can be analyzed by using Boolean algebra, which can also be

used as a basis for test design. The functional requirements of many programs can be specified by decision

tables, which provide a useful basis for program and test design. Boolean algebra is trivialized by using

Karnaugh-Veitch charts. Beizer described the method of using decision tables and Karnaugh-Veitch

charts to specify functional requirements in his book [2]. This was among the earliest approaches to select

test based on existing, well-known Boolean algebra logic in test data selection.

In the early 1990s, there was an increasing interest in estimating and predicting the reliability of software

systems. Before Jalote and colleagues’ study in 1994 [11], many existing reliability models employed

functional testing techniques and predicted the reliability based on the failure data observed during testing.

The application of these models requires a fair amount of data collection, computation, and expertise and

computation for interpreting the results. The authors propose a new approach based on the coverage

history of the program, by which a software system is modeled as a graph, and the reliability of a node is

assumed to be a function of the number of times it gets executed during testing-the larger the number of

times a node gets executed, the higher its reliability. The reliability of the software system is then

computed through simulation by using the reliabilities of the individual nodes. With such a model,

coverage analysis tools can easily be extended to compute the reliability also, thereby fully automating

reliability estimation.

The year 1997 saw good results in both functional and structural testing techniques. In this year a

framework for probabilistic functional testing was proposed. Bernot and colleagues introduce the

formulation of the testing activity, which guarantees a certain level of confidence into the correctness of the

system under test, and gives estimate of the reliability [1]. They also explain how one can generate

appropriate distributions for data domains including most common domains such as intervals of integers,

unions, Cartesian products, and inductively defined sets.

Another interesting research in 1997 used formal architectural description for rigorous, automatable method

for integration test of complex systems [4]. In this paper the authors propose to use the formal specification

language CHAM to model the behavior of interest of the systems. Graph of all the possible behaviors of

the system in terms of the interactions between its components is derived and further reduced. A suitable

set of reduced graphs highlights specific architectural properties of the system, and can be used for the

generation of integration tests according to a coverage strategy, analogous to the control and data flow

graphs in structural testing. This research is among the trend of using formal methods in testing techniques

since later 1980s.

From late 1990s, Commercial Off The Shelf (COTS) software and Unified Modeling Language (UML)

UML have been used by increasing number of software developers. This trend in development therefore

calls the corresponding testing techniques for the UML components. In their 2000 paper [7], Hartmann and

colleagues at Siemens addressed the issue of testing components by integrating test generation and test

execution technology with commercial UML modeling tools such as Rational Rose. The authors present

their approach to modeling components and interactions, describe how test cases are derived from these

component models and then executed to verify their conformant behavior. The TnT environment of

Siemens is used to evaluate the approach by examples. Test cases are derived from annotated Statecharts.

Another most recent research is also an approach to test component-based software. In 2001, Beydeda and

colleagues proposed a graphical representation of component-based software flow graph [3]. Testing is

made complicated with features, such as the absence of component source code, that are specific to

component-based software. The paper proposes a technique combining both black-box and white-box

strategies. A graphical representation of component software, called component-based software flow graph

(CBSFG), which visualizes information gathered from both specification and implementation, is described.

It can then be used for test case identification based on well-known structural techniques. Traditional

9

structural testing techniques can be applied to this graphical representation to identify test cases, using data

flow criterion. The main components are still tested with functional techniques.

5 Technology maturation

The maturation process of how the testing techniques for software have evolved from an ad hoc, intuitive

process, to an organized, systematic technology discipline is shown in Figure 3. Three models are used to

help analyzing and understanding the maturation process of testing techniques. A brief introduction on

these models followed.

5.1 Redwine/Riddle software technology maturation model

The Redwine/Riddle is the backbone of this maturation study. In 1985, Redwine and Riddle viewed the

growth and propagation of a variety of software technologies in an attempt to discover natural

characteristics of the process as well as principles and techniques useful in transitioning modern software

technology into widespread use. They looked at the technology maturation process by which a piece of

technology is first conceived, then shaped into something usable, and finally “marketed” to the point that it

is found in the repertoire of a majority of professionals. Six phases are described in Redwine/Riddles

model:

Phase 1: Basic research.

Investigate basic ideas and concepts, put initial structure on the problem, frame critical research

questions.

For testing techniques, the basic research phase ended in the mid to late 1950s, when the targets of

testing were set to make sure the software satisfies its specification. Initial researches began to try to

formulate the basic principles for testing.

Phase 2: Concept formulation.

Circulate ideas informally, develop a research community, converge on a compatible set of ideas,

publish solutions to specific subproblems.

The concept formulation process of testing focused between late 1950s and mid 1970s, when the

arguments of the real target of testing came to an end and theoretical researches began. The milestone

of the end of this phase is the publication of Goodenough and Gerhart’s paper on testing data selection.

Phase 3: Development and extension.

Make preliminary use of the technology, clarify underlying ideas, and generalize the approach.

The years between mid 1970s and late 1980s are the development and extension phase of testing

techniques. Various testing strategies are proposed and evaluated for both functional and structural

testing during this period. Principles of testing techniques were built up gradually during this period.

Phase 4: Internal enhancement and exploration.

Extend approach to another domain, use technology for real problems, stabilize technology, develop

training materials, show value in results.

Starting from late 1980s, researches on software testing techniques entered the internal exploration

stage. The principles defined during the last period were accepted widely and used in larger scales of

real problems, technologies began to stabilize and expand. People can now hire testing specialists or

10

companies to do the testing job for them. More and more courses and training programs are given in

universities and companies.

Phase 5: External enhancement and exploration.

Similar to internal, but involving a broader community of people who weren’t developers, show

substantial evidence of value and applicability.

Testing techniques started their prosperity in mid 1990s. Along with the advance of programming

languages, development methods, abstraction granularity and specification power, testing became

better facilitated and challenged with more complex situations and requirements of different kinds of

systems. Effective specification and development methods are borrowed employed during testing.

Phase 6: Popularization.

Develop production-quality, supported versions of the technology, commercialize and market

technology, expand user community.

Although the testing activities have been carried out everywhere and all the time, we don’t think

research on testing techniques have entered its popularization period. Testing techniques vary with

different systems and development methods. Even if specialist companies can be hired to do testing

job, there lacks a common basis for the industry to share and utilize academic research result, as well

as to use good practices from other enterprises. We are going to discuss this in future sections.