Download: PDF, slides (PDF), Daikon implementation.
“Efficient incremental algorithms for dynamic detection of likely invariants” by Jeff H. Perkins and Michael D. Ernst. In FSE 2004: Proceedings of the ACM SIGSOFT 12th Symposium on the Foundations of Software Engineering, (Newport Beach, CA, USA), Nov. 2004, pp. 23-32.
Dynamic detection of likely invariants is a program analysis that generalizes over observed values to hypothesize program properties. The reported program properties are a set of likely invariants over the program, also known as an operational abstraction. Operational abstractions are useful in testing, verification, bug detection, refactoring, comparing behavior, and many other tasks.
Previous techniques for dynamic invariant detection scale poorly or report too few properties. Incremental algorithms are attractive because they process each observed value only once and thus scale well with data sizes. Previous incremental algorithms only checked and reported a small number of properties. This paper takes steps toward correcting this problem. The paper presents two new incremental algorithms for invariant detection and compares them analytically and experimentally to two existing algorithms. Furthermore, the paper presents four optimizations and shows how to implement them in the context of incremental algorithms. The result is more scalable invariant detection that does not sacrifice functionality.
Download: PDF, slides (PDF), Daikon implementation.
BibTeX entry:
@inproceedings{PerkinsE2004,
author = {Jeff H. Perkins and Michael D. Ernst},
title = {Efficient incremental algorithms for dynamic detection of
likely invariants},
booktitle = {FSE 2004: Proceedings of the {ACM} {SIGSOFT} 12th
Symposium on the Foundations of Software Engineering},
pages = {23--32},
address = {Newport Beach, CA, USA},
month = nov,
year = {2004}
}