Abstracts - 2006
The Hob Approach for Verifying Data Structure Consistency Properties
Patrick Lam, Viktor Kuncak, Karen Zee & Martin Rinard
Hob is a static analysis framework that verifies that program implementations satisfy their specifications. Using Hob, developers can apply multiple pluggable analyses to different parts of a program, applying each analysis to the modules for which it is most appropriate. Each Hob analysis plugin verifies that program modules 1) properly implement their specifications; and 2) respect the preconditions of the procedures that they call. Program modules often encapsulate data structures, and many data structures maintain a dynamically changing set of objects as their primary purpose; we have therefore found that set specifications allow developers to express crucial data structure interface properties, including in particular, the preconditions needed by typical data structure operations to successfully execute. Hob's common set specification language therefore enables different analyses to effectively communicate with each other.
The Hob project addresses the program verification problem [1, 6]. Our tool supports assume/guarantee reasoning and data refinement. The techniques embodied in the Hob tool are particularly suited for expressing and verifying data structure consistency properties: Hob allows static analysis plugins to verify that data structure preconditions hold upon entry to a data structure, that data structure operations preserve data structure invariants, and that data structure operations conform to their specifications.
Our technique is designed to support programs that encapsulate the implementations of complex data structures in instantiatable leaf modules, with these modules analyzed once by very precise, potentially expensive analyses (such as shape analyses or even analyses that generate verification conditions that must be manually discharged using a theorem prover or proof checker). The rest of the program uses these modules but does not directly manipulate the encapsulated data structures. These modules can then be analyzed by more efficient analyses that operate primarily at the level of the common set abstraction. Given the scalability issues associated with precise data structure verification techniques, this kind of approach is the only way to make these analyses viable in practice.
We have implemented our analysis framework  and populated this framework with four analysis plugins: 1) the flags plugin, which is designed to analyze modules that use a flag field to indicate the typestate of the objects that they manipulate ; 2a) the PALE plugin, which implements a shape analysis for linked data structures (we integrated the Pointer Analysis Logic Engine analysis tool  into our system); 2b) the Bohne analysis plugin, which implements field constraint analysis for carrying out shape analysis for data structures which use nondeterministic field constraints; and 3) the theorem proving plugin, which generates verification conditions designed to be discharged manually using the Isabelle interactive theorem prover . We have used our analysis framework to analyze several programs; our experience shows that it can effectively 1) verify the consistency of data structures encapsulated within a single module and 2) combine analysis results from different analysis plugins to verify properties involving objects shared by multiple modules analyzed by different analyses. We have observed that our approach reduces the program annotation effort, improves the performance of the resulting analysis, and extends the range of programs to which each component analysis is applicable in isolation.
We next describe the Hob approach. A program to be analyzed contains a number of modules. Each module is analyzed by an analysis plugin; plugins ensure that the module's implementation conforms to its specification and that the module satisfies all preconditions for the calls that it makes.
How Analysis Plugins Work
The basic task of an analysis plugin is to certify that the implementation
for a module conforms to its specification and that the module meets all
preconditions for calls that it makes. Implementation sections for modules
in our system are written in a standard Java-like memory-safe imperative
language supporting arrays and dynamic object allocation. Module specification
sections give preconditions and postconditions for procedures in the boolean
algebra of sets; these conditions are augmented with a
In general, the Hob system analyzes individual modules as follows. For
each module, Hob examines the implementation, specification, and abstraction
sections of that module, as well as the specifications of all procedures
that the module invokes. Hob first uses the abstraction function (from
the abstraction section) to translate the
We have coded up several benchmark programs, using our system during the development of the programs. Our benchmarks include a web browser, the water scientific computation benchmark, a minesweeper game, and programs with computational patterns from operating-system schedulers, air-traffic control, and program transformation passes. These benchmarks use a variety of data structures, and we have therefore implemented and verified sets, set iterators, queues, stacks, and priority queues. Our implementations range from singly-linked and doubly-linked lists and tree insertion (all verified using the PALE plugin) through array data structures (verified using the theorem proving plugin with the Isabelle theorem prover used to discharge verification conditions); our largest benchmark (water) contains approximately 2000 lines of implementation and 500 lines of specification.
The Hob project homepage is at
The future development of Hob will be primarily guided by the verification of additional benchmark programs. We have already started annotating these programs. We expect new benchmark programs to give us more experience using the Hob system and to help us select a productive future research direction.
This research was supported in part by DARPA Contract F33615-00-C-1692, NSF Grant CCROO-86154, NSF Grant CCROO-63513, and the Singapore-MIT Alliance.
 C. A. R. Hoare. The verifying compiler: still a Grand Challenge for computing research. ETAPS Invited Lecture, Warsaw, Poland, April 2003.
 Patrick Lam, Viktor Kuncak and Martin Rinard. Crosscutting techniques in program specification and analysis. In Proceedings of the Fourth Conference on Aspect-Oriented Software Development, pp. 169--180, Chicago, IL, USA, March 2005.
 Patrick Lam, Viktor Kuncak and Martin Rinard. Generalized typestate checking for data structure consistency. In Proceedings of the Sixth International Conference on Verification, Model Checking and Abstract Interpretation, pp. 430--447, Paris, France, January 2005.
 Patrick Lam, Viktor Kuncak and Martin Rinard. Hob: A Tool for Verifying Data Structure Consistency (tool demo). In Proceedings of the Fourteenth International Conference on Compiler Construction, pp. 237--241, Edinburgh, Scotland, April 2005.
 Anders Møller and Michael I. Schwartzbach. The Pointer Assertion Logic Engine. In Proceedings of the 2001 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pp. 221--231, Snowbird, UT, USA, June 2001.
 Charles Gregory Nelson. Techniques for Program Verification. Technical report, XEROX Palo Alto Research Center, 1981.
 Karen Zee, Patrick Lam, Viktor Kuncak and Martin Rinard. Combining theorem proving with static analysis for data structure consistency. In Proceedings of the International Workshop on Software Verification and Validation (SVV 2004), Seattle, WA, USA, November 2004.