Dynamically discovering likely program invariants to support program evolution
Michael D. Ernst, Jake Cockrell, William G. Griswold et al. · IEEE Transactions on Software Engineering · 2001
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 (1981) 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.
Cited by 1,050 works. doi:10.1109/32.908957
Authors
References
- A Discipline of Programming
- Representation of Events in Nerve Nets and Finite Automata
- An axiomatic basis for computer programming
- Learning Logical Definitions from Relations
- The Science of Programming
- Partial evaluation and automatic program generation
- Extended static checking
- Discovering models of software processes from event-based data
- Experiments on the effectiveness of dataflow- and control-flow-based test adequacy criteria
- Abstraction and Specification in Program Development