Skip to main content

Model checking for symbolic-heap separation logic with inductive predicates

Brotherston, James and Gorogiannis, Nikos and Kanovich, Max and Rowe, Reuben (2016) Model checking for symbolic-heap separation logic with inductive predicates. In: Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. POPL Principles of Programming Languages . ACM, New York, USA, pp. 84-96. ISBN 978-1-4503-3549-2. (doi:10.1145/2914770.2837621) (KAR id:59465)

Abstract

We investigate the model checking problem for symbolic-heap separation logic with user-defined inductive predicates, i.e., the problem of checking that a given stack-heap memory state satisfies a given formula in this language, as arises e.g. in software testing or runtime verification.

First, we show that the problem is decidable; specifically, we present a bottom-up fixed point algorithm that decides the problem and runs in exponential time in the size of the problem instance.

Second, we show that, while model checking for the full language is EXPTIME-complete, the problem becomes NP-complete or PTIME-solvable when we impose natural syntactic restrictions on the schemata defining the inductive predicates. We additionally present NP and PTIME algorithms for these restricted fragments.

Finally, we report on the experimental performance of our procedures on a variety of specifications extracted from programs, exercising multiple combinations of syntactic restrictions.

Item Type: Book section
DOI/Identification number: 10.1145/2914770.2837621
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 9 Formal systems, logics
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Reuben Rowe
Date Deposited: 06 Dec 2016 12:14 UTC
Last Modified: 23 Apr 2022 22:07 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/59465 (The current URI for this page, for reference purposes)

University of Kent Author Information

Rowe, Reuben.

Creator's ORCID:
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.