Static specification inference using predicate mining
Authors:
Open Access
- 10 June 2007
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 42 (6) , 123-134
Abstract
The reliability and correctness of complex software systems can be significantly enhanced through well-defined specifications that dictate the use of various units of abstraction (e.g., modules, or procedures). Often times, however, specifications are either missing, imprecise, or simply too complex to encode within a signature, necessitating specification inference. The process of inferring specifications from complex software systems forms the focus of this paper. We describe a static inference mechanism for identifying the preconditions that must hold whenever a procedure is called. These preconditions may reflect both data flow properties (e.g., whenever p is called, variable x must be non-null) as well as control-flow properties (e.g., every call to p must bepreceded by a call to q ). We derive these preconditions using a ninter-procedural path-sensitive dataflow analysis that gathers predicates at each program point. We apply mining techniques to these predicates to make specification inference robust to errors. This technique also allows us to derive higher-level specifications that abstract structural similarities among predicates (e.g., procedure p is called immediately after a conditional test that checks whether some variable v is non-null.) We describe an implementation of these techniques, and validate the effectiveness of the approach on a number of large open-source benchmarks. Experimental results confirm that our mining algorithms are efficient, and that the specifications derived are both precise and useful-the implementation discovers several critical, yet previously, undocumented preconditions for well-tested libraries.Keywords
This publication has 29 references indexed in Scilit:
- Permissive interfacesACM SIGSOFT Software Engineering Notes, 2005
- DynaMine2005
- Joining dataflow with predicates2005
- Synthesis of interface specifications for Java classes2005
- Generalized Typestate Checking for Data Structure Consistency2005
- Mining Temporal Specifications for Error Detection2005
- Design and implementation of a fine-grained software inspection toolIEEE Transactions on Software Engineering, 2003
- Discovering all most specific sentencesACM Transactions on Database Systems, 2003
- Dynamically discovering likely program invariants to support program evolutionIEEE Transactions on Software Engineering, 2001
- Closure analysis in constraint formACM Transactions on Programming Languages and Systems, 1995