On The Boolean Algebra of Shape Analysis Constraints

Abstract

Shape analysis is a promising technique for statically verifyingand extracting properties of programs that manipulatecomplex data structures. We introduce a new characterizationof constraints that arise in parametric shapeanalysis based on manipulation of three-valued structuresas dataflow facts.We identify an interesting syntactic class of first-orderlogic formulas that captures the meaning of three-valuedstructures under concretization. This class is broader thanpreviously introduced classes, allowing for a greater flexibilityin the formulation of shape analysis constraints inprogram annotations and internal analysis representations.Three-valued structures can be viewed as one possible normalform of the formulas in our class.Moreover, we characterize the meaning of three-valuedstructures under “tight concretization”. We show that theseemingly minor change from concretization to tight concretizationincreases the expressive power of three-valuedstructures in such a way that the resulting constraints areclosed under all boolean operations. We call the resultingconstraints boolean shape analysis constraints.The main technical contribution of this paper is a naturalsyntactic characterization of boolean shape analysis constraintsas arbitrary boolean combinations of first-order sentencesof certain form, and an algorithm for transformingsuch boolean combinations into the normal form that correspondsdirectly to three-valued structures.Our result holds in the presence of arbitrary shape analysisinstrumentation predicates. The result enables the reduction(without any approximation) of the entailment andthe equivalence of shape analysis constraints to the satisfiabilityof shape analysis constraints. When the satisfiabilityof the constraints is decidable, our result implies that theentailment and the equivalence of the constraints are alsodecidable, which enables the use of constraints in a compositionalshape analysis with a predictable behavior.