TitleQuickly detecting relevant program invariants
Publication TypeConference Paper
Year of Publication2000
AuthorsErnst MD, Czeisler A, Griswold WG, Notkin D
Conference NameICSE 2000, Proceedings of the 22nd International Conference on Software Engineering
Date or Month PublishedJune
Conference LocationLimerick, Ireland

Explicitly stated program invariants can help programmers by characterizing certain aspects of program execution and identifying program properties that must be preserved when modifying code. Unfortunately, these invariants are usually absent from code. Previous work showed how to dynamically detect invariants from program traces by looking for patterns in and relationships among variable values. A prototype implementation, Daikon, accurately recovered invariants from formally-specified programs, and the invariants it detected in other programs assisted programmers in a software evolution task. However, Daikon suffered from reporting too many invariants, many of which were not useful, and also failed to report some desired invariants.

This paper presents, and gives experimental evidence of the efficacy of, four approaches for increasing the relevance of invariants reported by a dynamic invariant detector. One of them{ –- }exploiting unused polymorphism{ –- }adds desired invariants to the output. The other three{ –- }suppressing implied invariants, limiting which variables are compared to one another, and ignoring unchanged values{ –- }eliminate undesired invariants from the output and also improve runtime by reducing the work done by the invariant detector.

Downloadshttp://plse.cs.washington.edu/daikon/ Daikon implementation http://homes.cs.washington.edu/~mernst/pubs/invariants-relevance-icse200... PDF
Citation KeyErnstCGN2000:Relevance