## Viktor Kuncak.
*Modular Data Structure Verification*.
PhD thesis, EECS Department, Massachusetts Institute of Technology,
February 2007.

This dissertation describes an approach for automatically
verifying data structures, focusing on techniques for
automatically proving formulas that arise in such
verification. I have implemented this approach with my
colleagues in a verification system called Jahob. Jahob
verifies properties of Java programs with dynamically
allocated data structures.
Developers write Jahob specifications in classical
higher-order logic (HOL); Jahob reduces the verification
problem to deciding the validity of HOL formulas. I present
a new method for proving HOL formulas by combining automated
reasoning techniques. My method consists of 1) splitting
formulas into individual HOL conjuncts, 2) soundly
approximating each HOL conjunct with a formula in a more
tractable fragment and 3) proving the resulting
approximation using a decision procedure or a theorem
prover. I present three concrete logics; for each logic I
show how to use it to approximate HOL formulas, and how to
decide the validity of formulas in this logic.
First, I present an approximation of HOL based on a
translation to first-order logic, which enables the use of
existing resolution-based theorem provers.
Second, I present an approximation of HOL based on field
constraint analysis, a new technique that enables decision
procedures for special classes of graphs (such as monadic
second-order logic over trees) to be applied to arbitrary
graphs.
Third, I present an approximation using Boolean Algebra with
Presburger Arithmetic (BAPA), a logic that combines
reasoning about sets of elements with reasoning about
cardinalities of sets. BAPA can express relationships
between sizes of data structures and invariants that
correlate data structure size with integer variables. I
present the first implementation of a BAPA decision
procedure, and establish the exact complexity bounds for
BAPA and quantifier-free BAPA.
Together, these techniques enabled Jahob to modularly and
automatically verify data structure implementations based on
singly and doubly-linked lists, trees with parent pointers,
priority queues, and hash tables. In particular, Jahob was
able to prove that data structure implementations
satisfy their specifications, maintain key data structure
invariants expressed in a rich logical notation, and never
produce run-time errors such as null dereferences or out of
bounds accesses.

[ bib |
http ]
Back