Automating Separation Logic Using SMT

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.

Speaker Details

Damien Zufferey is a PhD student in Thomas A. Henzinger’s group at the Institute of Science and Technology Austria (IST Austria). He received a Master in computer science from EPFL in 2009, then he moved to IST Austria where he is working on verification of distributed systems. More specifically, he applies infinite-states model-checking techniques to mobile processes. His research interests range across program analysis, formal methods and programming languages. During the winter 2011-2012 he has done an internship at MSR in the RiSE group working with Shaz Qadeer and Ethan Jackson.

Series:
Microsoft Research Talks
Date:
Speakers:
Damien Zufferey
Affiliation:
Institute of Science and Technology Austria

Series: Microsoft Research Talks