Modular Pluggable Analyses for Data Structure Consistency
Authors:
- 30 November 2006
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. 32 (12) , 988-1005
Abstract
Hob is a program analysis system that enables the focused application of multiple analyses to different modules in the same program. In our approach, each module encapsulates one or more data structures and uses membership in abstract sets to characterize how objects participate in data structures. Each analysis verifies that the implementation of the module 1) preserves important internal data structure consistency properties and 2) correctly implements a set algebra interface that characterizes the effects of operations on the data structure. Collectively, the analyses use the set algebra to 1) characterize how objects participate in multiple data structures and to 2) enable the interanalysis communication required to verify properties that depend on multiple modules analyzed by different analyses. We implemented our system and deployed several pluggable analyses, including a flag analysis plug-in for modules in which abstract set membership is determined by a flag field in each object, a PALE shape analysis plug-in, and a theorem proving plug-in for analyzing arbitrarily complicated data structures. Our experience shows that our system can effectively 1) verify the consistency of data structures encapsulated within a single module and 2) combine analysis results from different analysis plug-ins to verify properties involving objects shared by multiple modules analyzed by different analysesKeywords
This publication has 60 references indexed in Scilit:
- Reasoning with specifications containing method calls and model fields.The Journal of Object Technology, 2005
- Generalized typestate checking using set interfaces and pluggable analysesACM SIGPLAN Notices, 2004
- Verification of Object-Oriented Programs with Invariants.The Journal of Object Technology, 2004
- Verification of non-functional programs using interpretations in type theoryJournal of Functional Programming, 2003
- Cosmological lower bound on the circuit complexity of a small problem in logicJournal of the ACM, 2002
- Parametric shape analysis via 3-valued logicACM Transactions on Programming Languages and Systems, 2002
- On the frame problem in procedure specificationsIEEE Transactions on Software Engineering, 1995
- Extending typestate checking using conditional liveness analysisIEEE Transactions on Software Engineering, 1993
- Generalized finite automata theory with an application to a decision problem of second-order logicTheory of Computing Systems, 1968
- Weak Second‐Order Arithmetic and Finite AutomataMathematical Logic Quarterly, 1960