Browse Theses

Modern software pervasively uses structurally complex data such as linked data structures. The standard approach to generating test suites for such software, manual generation of the inputs in the suite, is tedious and error-prone. This dissertation proposes a new approach for generating suites with structurally complex test inputs; presents a technique that automates this approach; describes the Korat tool that implements this technique for Java; and evaluates the effectiveness of Korat in testing a set of data-structure implementations.

Our approach allows the developer to describe the properties of valid test inputs using a familiar implementation language such as Java. Specifically, the user provides an imperative predicate—a piece of code that returns a truth value—that returns true if the input satisfies the required property and false otherwise. Korat implements our technique for solving imperative predicates: given a predicate and a bound on the size of the predicate's inputs, Korat automatically generates the bounded-exhaustive test suite that consists of all inputs, within the given bound, that satisfy the property identified by the predicate. To generate these inputs, Korat systematically searches the bounded input space by executing the predicate on the candidate inputs. Korat does this efficiently by pruning the search based on the predicate's executions and by generating only non-isomorphic inputs.

Bounded-exhaustive testing is a methodology for testing the code on all inputs within the given small bound. Our experiments on a set of ten linked and array-based data structures show that Korat can efficiently generate bounded-exhaustive test suites from imperative predicates even for very large input spaces and that these test suites can achieve high statement, branch, and mutation coverage. Moreover, the use of our technique for generating structurally complex test inputs has enabled testers in industry to detect faults in real, production-quality applications. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)