Dynamically discovering likely program invariants to support program evolution

Explicitly stated program invariants can help programmers by identifying pr ogram properties that must be preserved when modifying code. In practice, h owever, these invariants are usually implicit. An alternative to expecting programmers to fully annotate code with invariants is to automatically infe r likely invariants from the program itself. This research focuses on dynam ic techniques for discovering invariants from execution traces. This articl e reports three results. First, it describes techniques for dynamically dis covering invariants, along with an implementation, named Daikon, that embod ies these techniques. Second, it reports on the application of Daikon to tw o sets of target programs. In programs from Gries's work on program derivat ion, the system rediscovered predefined invariants. In a C program lacking explicit invariants, the system discovered invariants that assisted a softw are evolution task. These experiments demonstrate that, at least for small programs, invariant inference is both accurate and useful. Third, it analyz es scalability issues, such as invariant detection runtime and accuracy, as functions of test suites and program points instrumented.