Mutation Testing: Algorithms and Applications

Abstract

Software continues to be vital to the modern world, and as its ubiquity increases, its correctness becomes ever more valuable. Unfortunately, fundamental mathematical constraints on static analysis preclude the possibility of easy answers to the problem of correctness.

Modern software engineering relies upon software testing as an approximate method to establish correctness. Software testing, as exemplified by the use of test suites, provides the approximation desired, but does not present an obvious method to determine the accuracy of the approximation. Mutation testing is a technique that provides both an estimate of the quality of a test suite, as well as an avenue for its improvement.

Mutation testing is an area of active research, and while it is a useful tool for a software engineer, it is not a panacea for the problems of software testing. This dissertation covers research performed with the goals of both improving the state of the art in mutation testing, as well as applying mutation-testing techniques to solve other problems in software engineering.

This dissertation proposes new techniques in the field of mutation testing along three primary lines of research:

1. “Wild-caught mutants”. We propose a technique for the automatic generation of new mutation operators through the analysis of source-code control repositories.

2. Guided mutation testing. We propose a set of techniques to foster prioritization of time-consuming mutation-testing operations.

3. Automatic construction of test suites. We propose a technique that uses mutation-testing tools to aid in the process of automatic test-case generation and the automatic construction of entire test suites.