Dynamically discovering likely program invariants to support program evolution

Download: PDF, ICSE 1999 paper (PDF), ICSE 1999 talk slides (PowerPoint), ICSE 1999 talk slides (PDF), Daikon implementation.

“Dynamically discovering likely program invariants to support program evolution” by Michael D. Ernst, Jake Cockrell, William G. Griswold, and David Notkin. IEEE Transactions on Software Engineering, vol. 27, no. 2, Feb. 2001, pp. 99-123.
A previous version appeared in ICSE '99: Proceedings of the 21st International Conference on Software Engineering, (Los Angeles, CA, USA), May 1999, pp. 213-224.
A previous version appeared as University of Washington Department of Computer Science and Engineering technical report UW-CSE-98-08-03, (Seattle, WA), August 27, 1998.

Abstract

Explicitly stated program invariants can help programmers by identifying program properties that must be preserved when modifying code. In practice, however, these invariants are usually implicit. An alternative to expecting programmers to fully annotate code with invariants is to automatically infer likely invariants from the program itself. This research focuses on dynamic techniques for discovering invariants from execution traces.

This article reports three results. First, it describes techniques for dynamically discovering invariants, along with an implementation, named Daikon, that embodies these techniques. Second, it reports on the application of Daikon to two sets of target programs. In programs from Gries's work on program derivation, the system rediscovered predefined invariants. In a C program lacking explicit invariants, the system discovered invariants that assisted a software evolution task. These experiments demonstrate that, at least for small programs, invariant inference is both accurate and useful. Third, it analyzes scalability issues such as invariant detection runtime and accuracy as functions of test suites and program points instrumented.

Download: PDF, ICSE 1999 paper (PDF), ICSE 1999 talk slides (PowerPoint), ICSE 1999 talk slides (PDF), Daikon implementation.

BibTeX entry:

@article{ErnstCGN2001:TSE,
   author = {Michael D. Ernst and Jake Cockrell and William G. Griswold
	and David Notkin},
   title = {Dynamically discovering likely program invariants to support
	program evolution},
   journal = {IEEE Transactions on Software Engineering},
   volume = {27},
   number = {2},
   pages = {99--123},
   month = feb,
   year = {2001}
}

(This webpage was created with bibtex2web.)

Back to Michael Ernst's publications.