Automatically Inferring Temporal Properties for Program Evolution
Fifteenth IEEE International Symposium on Software Reliability Engineering (ISSRE 2004)
Saint-Malo, France, 2-5 November 2004
It is important that program maintainers understand important properties of the programs they modify and ensure that the changes they make do not alter essential properties in unintended ways. Manually documenting those properties, especially temporal ones that constrain the ordering of events, is difficult and rarely done in practice. We propose an automatic approach to inferring a target system's temporal properties based on analyzing its event traces. The core of our technique is a set of pre-defined property patterns among a few events. These patterns form a partial order in terms of their strictness. Our approach finds the strictest properties satisfied by a set of events based on the traces. We report results from experiments on two sets of programs: student solutions for a class assignment, and several recent versions of OpenSSL. Comparing properties inferred from different implementations led us to discover important behavioral differences which revealed flaws in the programs. Differences in automatically inferred temporal properties can provide useful information to programmers evolving complex, often unspecified, programs whose correctness depends on preservation of undocumented temporal properties.
Keywords: Invariants, temporal properties, concurrent programming, dynamic analysis, property patterns, program evolution, software reliability.
Complete Paper (12 pages) [PDF]
