The DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
Separation logic: a logic for shared mutable data structures
Abstract
In joint work with Peter O'Hearn and others, based on early ideas of Burstall, we have developed an extension of Hoare logic that permits reasoning about low-level imperative programs that use shared mutable data structure. The simple imperative programming language is extended with commands (not expressions) for accessing and modifying shared structures, and for explicit allocation and deallocation of storage. Assertions are extended by introducing a "separating conjunction" that asserts that its subformulas hold for disjoint parts of the heap, and a closely related "separating implication". Coupled with the inductive definition of predicates on abstract data structures, this extension permits the concise and flexible description of structures with controlled sharing. In this paper, we survey the current development of this program logic, including extensions that permit unrestricted address arithmetic, dynamically allocated arrays, and recursive procedures. We also discuss promising future directions.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
An axiomatic basis for computer programming
Hoare, C. A. R. (1969) · Communications of the ACM · doi:10.1145/363235.363259 · Cited by 4,002
Harel, D., Kozen, D. C., & Tiuryn, J. (2000) · Cited by 1,439
Local Reasoning about Programs that Alter Data Structures
O’Hearn, P., Reynolds, J., & Yang, H. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44802-0_1 · Cited by 705
Self-citationThe Logic of Bunched Implications
O’Hearn, P. W., & Pym, D. J. (1999) · Bulletin of Symbolic Logic · doi:10.2307/421090 · Cited by 579
BI as an assertion language for mutable data structures
Ishtiaq, S., & O'Hearn, P. W. (2011) · ACM SIGPLAN Notices · doi:10.1145/1988042.1988050 · Cited by 489
Implementation of the typed call-by-value λ-calculus using a stack of regions
Tofte, M., & Talpin, J.-P. (1994) · Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '94 · doi:10.1145/174675.177855 · Cited by 337
BI as an assertion language for mutable data structures
Ishtiaq, S. S., & O'Hearn, P. W. (2001) · Proceedings of the 28th ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/360204.375719 · Cited by 287
Alias Types for Recursive Data Structures
Walker, D., & Morrisett, G. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45332-6_7 · Cited by 191
Hoare, C. A. R. (1971) · Communications of the ACM · doi:10.1145/362452.362489 · Cited by 180
Hoare, C. A. R. (1978) · Springer eBooks · doi:10.1007/978-1-4612-6315-9_10 · Cited by 156
Cited by
Dafny: An Automatic Program Verifier for Functional Correctness
Leino, K. R. M. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-17511-4_20 · Cited by 940
A survey of symbolic execution techniques
Baldoni, R., Coppa, E., D’elia, D. C., Demetrescu, C., & Finocchi, I. (2019) · ACM Computing Surveys · doi:10.1145/3182657 · Cited by 708
Resources, concurrency, and local reasoning
O’Hearn, P. W. (2007) · Theoretical Computer Science · doi:10.1016/j.tcs.2006.12.035 · Cited by 552
Jhala, R., & Majumdar, R. (2009) · ACM Computing Surveys · doi:10.1145/1592434.1592438 · Cited by 418
Iris from the ground up: A modular foundation for higher-order concurrent separation logic
JUNG, R., KREBBERS, R., JOURDAN, J.-H., BIZJAK, A., BIRKEDAL, L., & DREYER, D. (2018) · Journal of Functional Programming · doi:10.1017/s0956796818000151 · Cited by 372
RustBelt: securing the foundations of the Rust programming language
Jung, R., Jourdan, J.-H., Krebbers, R., & Dreyer, D. (2018) · Proceedings of the ACM on Programming Languages · doi:10.1145/3158154 · Cited by 368
Gated Graph Sequence Neural Networks
Li, Y., Tarlow, D., Brockschmidt, M., & Zemel, R. S. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1511.05493 · Cited by 362
Smallfoot: Modular Automatic Assertion Checking with Separation Logic
Berdine, J., Calcagno, C., & O’Hearn, P. W. (2006) · Lecture Notes in Computer Science · doi:10.1007/11804192_6 · Cited by 316
Separation logic and abstraction
Parkinson, M., & Bierman, G. (2005) · Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/1040305.1040326 · Cited by 309
A type and effect system for deterministic parallel Java
Bocchino, R. L., Adve, V. S., Dig, D., Adve, S. V., Heumann, S., Komuravelli, R., Overbey, J., Simmons, P., Sung, H., & Vakilian, M. (2009) · ACM SIGPLAN Notices · doi:10.1145/1639949.1640097 · Cited by 295
Language support for fast and reliable message-based communication in singularity OS
Fähndrich, M., Aiken, M., Hawblitzel, C., Hodson, O., Hunt, G., Larus, J. R., & Levi, S. (2006) · Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 2006 · doi:10.1145/1217935.1217953 · Cited by 289
Compositional shape analysis by means of bi-abduction
Calcagno, C., Distefano, D., O'Hearn, P., & Yang, H. (2009) · Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/1480881.1480917 · Cited by 279
Iris: Monoids and Invariants as an Orthogonal Basis for Concurrent Reasoning
Jung, R., Swasey, D., Sieczkowski, F., Svendsen, K., Turon, A., Birkedal, L., & Dreyer, D. (2015) · Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages · doi:10.1145/2676726.2676980 · Cited by 276
A type and effect system for deterministic parallel Java
Bocchino, R. L., Adve, V. S., Dig, D., Adve, S. V., Heumann, S., Komuravelli, R., Overbey, J., Simmons, P., Sung, H., & Vakilian, M. (2009) · Proceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications · doi:10.1145/1640089.1640097 · Cited by 265
“First, SL is a low-level specification language: it generally treats memory as a single array of words, on which notions of objects and linked data structures must be defined using SL predicates [40, 35].”
BackgroundViper: A Verification Infrastructure for Permission-Based Reasoning
Müller, P., Schwerhoff, M., & Summers, A. J. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-49122-5_2 · Cited by 265
Using Crash Hoare logic for certifying the FSCQ file system
Chen, H., Ziegler, D., Chajed, T., Chlipala, A., Kaashoek, M. F., & Zeldovich, N. (2015) · Proceedings of the 25th Symposium on Operating Systems Principles · doi:10.1145/2815400.2815402 · Cited by 211
Enhancing Automated Loop Invariant Generation for Complex Programs with Large Language Models
Liu, R., Chen, M., Wu, L.-I., Ke, J., & Li, G. (2024) · arXiv · doi:10.48550/arxiv.2412.10483 · Cited by 9
“Separation Logic (SL) [36] is an extension of Hoare logic to reason about memory structures and the interactions of programs with dynamically allocated memory.”
Eilers, M., Schwerhoff, M., Summers, A. J., & Müller, P. (2025) · Lecture Notes in Computer Science · doi:10.1007/978-3-031-98668-0_5 · Cited by 2
Evaluating the Ability of GPT-4o to Generate Verifiable Specifications in VeriFast
Rego, M., Fan, W., Hu, X., Dod, S., Ni, Z., Xie, D., DiVincenzo, J., & Tan, L. (2025) · 2025 IEEE/ACM Second International Conference on AI Foundation Models and Software Engineering (Forge) · doi:10.1109/forge66646.2025.00035 · Cited by 2
“However, related work has not explored whether or not off-the-shelf LLMs can generate specifications based on a permissions logic, like separation logic [26], that can be verified by auto-active verifiers such as VeriFast, Gillian, and Viper.”
Metadata
- Authors
- Reynolds, J. C.
- Venue
- Proceedings 17th Annual IEEE Symposium on Logic in Computer Science
- Publisher
- IEEE Comput. Soc
- Published
- 2003-06-25
- Pages
- 55-74
- ISSN
- 1043-6871 (ISSN-L)
- OpenAlex
- W2137628566
- Cited by
- 2,156
- References
- 12
- FWCI
- 55.97
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.