March 2002
Volume 4 • Number 2

Contents

SOFTWARE TESTING
Test Vector Generation: Current Status and Future Trends
by Selim Aissi

CSQE Body of Knowledge areas: Software Verification and Validation, Test Planning and Design

Although test vector generation is the most challenging and costly step of software testing, there are not enough commercial tools that support this testing activity. Because of the various categories of software testing and their relevant adequacy criteria, most of the research has focused on partial solutions and heuristics.

This article covers the most important advancements in the area of automated test vector generation. Between the early specification-based testing methods of Howden in the early 1970s and the constraint-based testing methods of Weyuker, Offutt, and others in the 1990s, various major techniques emerged to automate the generation of test vectors as well as to reduce their numbers to useable subsets. It has been a challenge, however, to implement these methodologies into commercial tools. This article addresses those challenges and describes some of the currently commercialized testing techniques for code- and specification-based test vector generation.

The most commonly used bases for automated test vector generation include the source code, control flow graphs, design representations, and specifications. Currently, model-based development tools are increasing in use because they provide tangible benefits by supporting simulation and code generation, in addition to the traditional design and analysis. The key challenge is to translate development-oriented modeling languages into a form that is suitable for automated test vector generation. This article addresses this approach and its potential uses.

Key words: CASE tools, code-based testing, specification-based testing, test case generation, testing methodology

INTRODUCTION

In recent years, the use of embedded processors as controllers has exploded. Embedded microprocessor-based controllers are showing up everywhere, from the most sophisticated safety-critical applications, such as avionics systems, to everyday consumer products, such as home appliances.

Software development is becoming more and more of a bottleneck given the pressure to decrease product development time while increasing the range of functionality and quality expected of the software. These considerations, coupled with the dearth of competent software professionals, are leading to an increased use of automated software development tools, including tools that automate the generation of source code and documentation. These automation packages feature programming in a graphical, higher-level, more abstract way than programming languages such as C, C++, Ada, or Java.

The use of good software development practices and code generation packages does not obviate the need for thorough software testing. Many stages are required in the overall testing process to ensure product quality. This testing must be conducted at various levels ranging from unit testing of the smallest segments of the software through system testing. Additional layers of acceptance may be required once the software is integrated with the hardware and then with the remainder of the system.

The objective of software testing is to find defects and provide confidence that the deliverable will meet the user’s expectations. There are several theoretical and practical limitations that make this objective impossible to obtain for many products (Collofello 1988). The major limitations are the theoretical foundations, the impracticality of testing all data, the impracticality of testing all paths, and the problem of proof of correctness.

Some of the initial theoretical foundations for software testing were presented by Goodenough and Gerhart (1975). Howden claims one of the most important theoretical results in software testing and analysis is that no general-purpose testing or analysis procedure can be used to prove program correctness. He provided proof of this result in his classic book (Howden 1987).

For most software applications, it is impractical to try to test the program with all possible inputs, because of a combinatorial explosion (Beizer 1983; Howden 1987). For those inputs selected, a testing oracle is needed to determine the correctness of the output for a particular test input (Howden 1987).

Also, for most software applications, it is impractical to try to test all execution paths through the program under test, because of a combinatorial explosion (Beizer 1983). It is also impossible to develop an algorithm for generating test vectors for paths in an arbitrary software application because of the inability to determine path feasibility (Adrion, Branstad, and Cheriavsky 1986).

With regard to the concept of proof of correctness, Howden (1987) claims there is no such thing as an absolute proof of correctness. Instead, he proposes that there are proofs of equivalency. Therefore, unless a formal specification can be shown to be correct and reflect exactly the user’s expectations, no claim of product correctness can be made (Beizer 1983; Howden 1987).

Software testing can only be formalized and quantified when a solid basis for test vector generation can be defined (Offutt and Liu 1997). Bases that are commonly used include the source code, control flow graphs, design representations, and specifications. Both code-based and specification-based testing are valuable, and they are complementary.

Back to top