Implicit dynamic frames

An important, challenging problem in the verification of imperative programs with shared, mutable state is the frame problem in the presence of data abstraction. That is, one must be able to specify and verify upper bounds on the set of memory locations a method can read and write without exposing that method's implementation.

Separation logic is now widely considered the most promising solution to this problem. However, unlike conventional verification approaches, separation logic assertions cannot mention heap-dependent expressions from the host programming language, such as method calls familiar to many developers. Moreover, separation logic-based verifiers are often based on symbolic execution. These symbolic execution-based verifiers typically do not support non-separating conjunction, and some of them rely on the developer to explicitly fold and unfold predicate definitions. Furthermore, several researchers have wondered whether it is possible to use verification condition generation and standard first-order provers instead of symbolic execution to automatically verify conformance with a separation logic specification.

In this article, we propose a variant of separation logic called implicit dynamic frames that supports heap-dependent expressions inside assertions. Conformance with an implicit dynamic frames specification can be checked by proving the validity of a number of first-order verification conditions. To show that these verification conditions can be discharged automatically by standard first-order provers, we have implemented our approach in a verifier prototype and have used this prototype to verify several challenging examples from related work. Our prototype automatically folds and unfolds predicate definitions, as required, during the proof and can reason about non-separating conjunction which is used in the specifications of some of these examples. Finally, we prove the soundness of the approach.