Automating separation logic using SMT

Ruzica Piskac, Thomas Wies, Damien Zufferey

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationComputer Aided Verification - 25th International Conference, CAV 2013, Proceedings
Pages773-789
Number of pages17
DOIs
StatePublished - 2013
Event25th International Conference on Computer Aided Verification, CAV 2013 - Saint Petersburg, Russian Federation
Duration: Jul 13 2013Jul 19 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8044 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other25th International Conference on Computer Aided Verification, CAV 2013
CountryRussian Federation
CitySaint Petersburg
Period7/13/137/19/13

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Automating separation logic using SMT'. Together they form a unique fingerprint.

  • Cite this

    Piskac, R., Wies, T., & Zufferey, D. (2013). Automating separation logic using SMT. In Computer Aided Verification - 25th International Conference, CAV 2013, Proceedings (pp. 773-789). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8044 LNCS). https://doi.org/10.1007/978-3-642-39799-8_54