Satisfiability Modulo Heap-Based Programs

Quang Loc Le, Jun Sun, Wei-Ngan Chin

    Research output: Contribution to conferencePaper

    170 Downloads (Pure)

    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 languageEnglish
    DOIs
    Publication statusE-pub ahead of print - 13 Jul 2016
    Event28th International Conference on Computer Aided Verification - Toronto, Canada
    Duration: 17 Jul 201623 Jul 2016
    http://i-cav.org/2016/

    Conference

    Conference28th International Conference on Computer Aided Verification
    Abbreviated titleCAV 2016
    CountryCanada
    CityToronto
    Period17/07/1623/07/16
    Internet address

    Fingerprint Dive into the research topics of 'Satisfiability Modulo Heap-Based Programs'. Together they form a unique fingerprint.

  • Cite this

    Le, Q. L., Sun, J., & Chin, W-N. (2016). Satisfiability Modulo Heap-Based Programs. Paper presented at 28th International Conference on Computer Aided Verification, Toronto, Canada. https://doi.org/10.1007/978-3-319-41528-4_21