Automating Separation Logic Using SMT

Speaker  Damien Zufferey

Affiliation  Institute of Science and Technology Austria

Host  Shaz Qadeer

Duration  01:25:55

Date recorded  24 June 2013

Separation logic (SL) has gained widespread popularity because of its ability to succinctly express complex invariants of a program’s heap configurations. Several specialized provers have been developed for decidable SL fragments. However, these provers cannot be easily extended or combined with solvers for other theories that are important in program verification, e.g., linear arithmetic. In this paper, we present a reduction of decidable SL fragments to a decidable first-order theory that fits well into the satisfiability modulo theories (SMT) framework. We show how to use this reduction to automate satisfiability, entailment, frame inference, and abduction problems for separation logic using SMT solvers. Our approach provides a simple method of integrating separation logic into existing verification tools that provide SMT backends, and an elegant way of combining SL fragments with other decidable first-order theories. We implemented this approach in a verification tool and applied it to heap-manipulating programs whose verification involves reasoning in theory combinations. This is joint work with Rizca Piskac and Thomas Wies.

©2013 Microsoft Corporation. All rights reserved.
> Automating Separation Logic Using SMT