Satisfiability modulo heap-based programs
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...
Saved in:
| Main Authors: | , , |
|---|---|
| 格式: | text |
| 語言: | English |
| 出版: |
Institutional Knowledge at Singapore Management University
2016
|
| 主題: | |
| 在線閱讀: | https://ink.library.smu.edu.sg/sis_research/4937 https://ink.library.smu.edu.sg/context/sis_research/article/5940/viewcontent/Satisfiability.pdf |
| 標簽: |
添加標簽
沒有標簽, 成為第一個標記此記錄!
|
| 機構: | Singapore Management University |
| 語言: | English |
| 總結: | 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. |
|---|