Automating separation logic using SMT

R. Piskac, T. Wies, D. Zufferey, 8044 (2013) 773–789.

OA 2013_CAV_Piskac.pdf 309.18 KB

Conference Paper | Published | English

Scopus indexed
Series Title
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.
Publishing Year
Date Published
773 - 789
CAV: Computer Aided Verification
Conference Location
St. Petersburg, Russia
Conference Date
2013-07-13 – 2013-07-19

Cite this

Piskac R, Wies T, Zufferey D. Automating separation logic using SMT. 2013;8044:773-789. doi:10.1007/978-3-642-39799-8_54
Piskac, R., Wies, T., & Zufferey, D. (2013). Automating separation logic using SMT. Presented at the CAV: Computer Aided Verification, St. Petersburg, Russia: Springer.
Piskac, Ruzica, Thomas Wies, and Damien Zufferey. “Automating Separation Logic Using SMT.” Lecture Notes in Computer Science. Springer, 2013.
R. Piskac, T. Wies, and D. Zufferey, “Automating separation logic using SMT,” vol. 8044. Springer, pp. 773–789, 2013.
Piskac R, Wies T, Zufferey D. 2013. Automating separation logic using SMT. 8044, 773–789.
Piskac, Ruzica, et al. Automating Separation Logic Using SMT. Vol. 8044, Springer, 2013, pp. 773–89, doi:10.1007/978-3-642-39799-8_54.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
MD5 Checksum


Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar