Abstract
In this work, we present a semi-decision procedure for a fragment of separation logic with user-defined predicates and Presburger arithmetic. To check the satisfiability of a formula, our procedure iteratively unfolds the formula and examines the derived disjuncts. In each iteration, it searches for a proof of either satisfiability or unsatisfiability. Our procedure is further enhanced with automatically inferred invariants as well as detection of cyclic proof. We also identify a syntactically restricted fragment of the logic for which our procedure is terminating and thus complete. This decidable fragment is relatively expressive as it can capture a range of sophisticated data structures with non-trivial pure properties, such as size, sortedness and near-balanced. We have implemented the proposed solver and a new system for verifying heap-based programs. We have evaluated our system on benchmark programs from a software verification competition.
Original language | English |
---|---|
DOIs | |
Publication status | E-pub ahead of print - 13 Jul 2016 |
Event | 28th International Conference on Computer Aided Verification - Toronto, Canada Duration: 17 Jul 2016 → 23 Jul 2016 http://i-cav.org/2016/ |
Conference
Conference | 28th International Conference on Computer Aided Verification |
---|---|
Abbreviated title | CAV 2016 |
Country/Territory | Canada |
City | Toronto |
Period | 17/07/16 → 23/07/16 |
Internet address |