Quickly detecting relevant program invariants

摘要

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.