Reliable software testing is a time consuming operation. In addition to the time spent by the tester in identifying, locating, and correcting bugs, a significant time is spent in the execution of the program under test and its instrumented or fault induced variants. When using mutation based testing to achieve high reliability, the number of such variants can be large. Providing a software testing tool that can efficiently exploit the architecture of a parallel machine implies providing more computing power to the software tester and hence an opportunity to improve the reliability of the product being developed. In this thesis, we consider the problem of utilizing high performance computers to improve the quality of software. We describe three approaches to the parallelization of mutant execution on three architectures: MIMD, Vector, and MIMD with vector processors. We describe the architecture of the P$\sp\rm M$othra system designed to provide the tester a transparent interface to parallel machines. A prototype, constructed by interfacing the Mothra system to an Ncube through a scheduler, was used to conduct the experiments reported in this dissertation. Analysis of algorithms developed and experimental results obtained on these three architecture are presented. Our results enable us to conclude that the MIMD machine, as typified by the Ncube, is superior to some other architectures for mutation based software testing.

A method for high-performance, software testing, called mutant unification, is described. The method is designed to support program mutation on parallel machines based on the single instruction multiple data stream (SIMD) paradigm. Several parameters that affect the performance of unification have been identified and their effect on the time to completion of a mutation test cycle and speedup has been studied. Program mutation analysis provides an effective means for determining the reliability of large software systems and a systematic method for measuring the adequacy of test data. However, it is likely that testing large software systems using mutation is computation bound and prohibitive on traditional sequential machines. Current, implementations of mutation tools are unacceptably slow and are only suitable for testing relatively small programs. The proposed unification method provides a practical alternative to the current approaches. The method also opens up a new application domain for SIMD machines.

A novel technique for automatically generating test data is presented. The technique is based on mutation analysis and creates test data that approximate relative adequacy. It is a fault-based technique that uses algebraic constraints to describe test cases designed to find particular types of faults. A set of tools (collectively called Godzilla) that automatically generates constraints and solves them to create test cases for unit and module testing has been implemented. Godzilla has been integrated with the Mothratesting system and has been used as an effective way to generate test data that kill program mutants. The authors present an initial list of constraints and discuss some of the problems that have been solved to develop the complete implementation of the technique.

Mutation analysis is a powerful technique for testing software systems. The Mothra software testing project uses mutation analysis as the basis for an integrated software testing environment. Mutation analysis requires executing many slightly differing versions of the same program to evaluate the quality of the data used to test the program. The current version of Mothra includes a complete language system that translates a program to be tested into intermediate code so that it and its mutated versions can be executed by an interpreter. In this paper, we discuss some of the unique requirements of a language system used in a mutation-based testing environment. We then describe how these requirements affected the design and implementation of the Fortran 77 version of the Mothra system. We also describe the intermediate language used by Mothra and the features of the language system that are needed for software testing. The appendices contain a full description of the intermediate language and the mutation operators used by Mothra. The design and implementation techniques that were developed for Mothra are applicable for constructing not just software testing systems, but any type of program analysis system or language system for a special-purpose application. In particular, we discuss decisions made and techniques developed by the Mothra team that can be useful in such applications as debuggers, program measurement tools, software development environments and other types of program analysis systems.

Available soon...

Available soon...

Available soon...

Available soon...

Available soon...

A theory of fault-based program testing is defined and explained. Testing is fault-based when it seeks to demonstrate that prescribed faults are not in a program. It is assumed that a program can only be incorrect in a limited fashion specified by associating alternate expressions with program expressions. Classes of alternate expressions can be infinite. Substituting an alternate expression for a program expression yields an alternate program that is potentially correct. The goal of fault-based testing is to produce a test set that differentiates the program from each of its alternates. A particular form of fault-based testing based on symbolic execution is presented. In symbolic testing, the output from the system is an expression in terms of the input and the symbolic alternative. Equating this with the output from the original program yields a propagation equation whose solutions determine those alternatives which are not differentiated by this test. Since an alternative set can be infinite, it is possible that no finite test differentiates the program from all its alternates. Circumstances are described as to when this can be decided