Separation logic

In computer science, separation logic ^[1] is an extension of Hoare logic, a way of reasoning about programs. It was developed by John C. Reynolds, Peter O'Hearn, Samin Ishtiaq and Hongseok Yang, ^{[1] [2] [3] [4]} drawing upon early work by Rod Burstall. ^[5] The assertion language of separation logic is a special case of the logic of bunched implications (BI). ^[6] A CACM review article by O'Hearn charts developments in the subject to early 2019. ^[7]

Overview

Separation logic facilitates reasoning about:

• programs that manipulate pointer data structures—including information hiding in the presence of pointers;
• "transfer of ownership" (avoidance of semantic frame axioms); and
• virtual separation (modular reasoning) between concurrent modules.

Separation logic supports the developing field of research described by Peter O'Hearn and others as local reasoning, whereby specifications and proofs of a program component mention only the portion of memory used by the component, and not the entire global state of the system. Applications include automated program verification (where an algorithm checks the validity of another algorithm) and automated parallelization of software.

Assertions: operators and semantics

Separation logic assertions describe "states" consisting of a store and a heap, roughly corresponding to the state of local (or stack-allocated) variables and dynamically-allocated objects in common programming languages such as C and Java. A store ${\displaystyle s}$ is a function mapping variables to values. A heap ${\displaystyle h}$ is a partial function mapping memory addresses to values. Two heaps ${\displaystyle h}$ and ${\displaystyle h'}$ are disjoint (denoted ${\displaystyle h\,\bot \,h'}$) if their domains do not overlap (i.e., for every memory address ${\displaystyle \ell }$, at least one of ${\displaystyle h(\ell )}$ and ${\displaystyle h'(\ell )}$ is undefined).

The logic allows to prove judgements of the form ${\displaystyle s,h\models P}$, where ${\displaystyle s}$ is a store, ${\displaystyle h}$ is a heap, and ${\displaystyle P}$ is an assertion over the given store and heap. Separation logic assertions (denoted as ${\displaystyle P}$, ${\displaystyle Q}$, ${\displaystyle R}$) contain the standard boolean connectives and, in addition, ${\displaystyle \mathbf {e} \mathbf {m} \mathbf {p} }$, ${\displaystyle e\mapsto e'}$, ${\displaystyle P\ast Q}$, and ${\displaystyle P{-\!\!\ast }\,Q}$, where ${\displaystyle e}$ and ${\displaystyle e'}$ are expressions.

• The constant ${\displaystyle \mathbf {e} \mathbf {m} \mathbf {p} }$ asserts that the heap is empty, i.e., ${\displaystyle s,h\models \mathbf {e} \mathbf {m} \mathbf {p} }$ when ${\displaystyle h}$ is undefined for all addresses.
• The binary operator ${\displaystyle \mapsto }$ takes an address and a value and asserts that the heap is defined at exactly one location, mapping the given address to the given value. I.e., ${\displaystyle s,h\models e\mapsto e'}$ when ${\displaystyle h([\![e]\!]_{s})=[\![e']\!]_{s}}$ (where ${\displaystyle [\![e]\!]_{s}}$ denotes the value of expression ${\displaystyle e}$ evaluated in store ${\displaystyle s}$) and ${\displaystyle h}$ is otherwise undefined.
• The binary operator ${\displaystyle \ast }$ (pronounced star or separating conjunction) asserts that the heap can be split into two disjoint parts where its two arguments hold, respectively. I.e., ${\displaystyle s,h\models P\ast Q}$ when there exist ${\displaystyle h_{1},h_{2}}$ such that ${\displaystyle h_{1}\,\bot \,h_{2}}$ and ${\displaystyle h=h_{1}\cup h_{2}}$ and ${\displaystyle s,h_{1}\models P}$ and ${\displaystyle s,h_{2}\models Q}$.
• The binary operator ${\displaystyle -\!\!\ast }$ (pronounced magic wand or separating implication) asserts that extending the heap with a disjoint part that satisfies its first argument results in a heap that satisfies its second argument. I.e,. ${\displaystyle s,h\models P-\!\!\ast \,Q}$ when for every heap ${\displaystyle h'\,\bot \,h}$ such that ${\displaystyle s,h'\models P}$, also ${\displaystyle s,h\cup h'\models Q}$ holds.

The operators ${\displaystyle \ast }$ and ${\displaystyle -\!\!\ast }$ share some properties with the classical conjunction and implication operators. They can be combined using an inference rule similar to modus ponens

${\displaystyle {\frac {s,h\models P\ast (P-\!\!\ast \,Q)}{s,h\models Q}}}$

and they form an adjunction, i.e., ${\displaystyle s,h\cup h'\models P\ast Q\Rightarrow R}$ if and only if ${\displaystyle s,h\models P\Rightarrow Q-\!\!\ast \,R}$ for ${\displaystyle h\,\bot \,h'}$; more precisely, the adjoint operators are ${\displaystyle \_\ast Q}$ and ${\displaystyle Q-\!\!\ast \,\_}$.

Reasoning about programs: triples and proof rules

In separation logic, Hoare triples have a slightly different meaning than in Hoare logic. The triple ${\displaystyle \{P\}\ C\ \{Q\}}$ asserts that if the program ${\displaystyle C}$ executes from an initial state satisfying the precondition ${\displaystyle P}$ then the program will not go wrong (e.g., have undefined behaviour), and if it terminates, then the final state will satisfy the postcondition ${\displaystyle Q}$. In essence, during its execution, ${\displaystyle C}$ may access only memory locations whose existence is asserted in the precondition or that have been allocated by ${\displaystyle C}$ itself.

In addition to the standard rules from Hoare logic, separation logic supports the following very important rule:

${\displaystyle {\frac {\{P\}\ C\ \{Q\}}{\{P\ast R\}\ C\ \{Q\ast R\}}}~{\mathsf {mod}}(C)\cap {\mathsf {fv}}(R)=\emptyset }$

This is known as the frame rule (named after the frame problem) and enables local reasoning. It says that a program that executes safely in a small state (satisfying ${\displaystyle P}$), can also execute in any bigger state (satisfying ${\displaystyle P\ast R}$) and that its execution will not affect the additional part of the state (and so ${\displaystyle R}$ will remain true in the postcondition). The side condition enforces this by specifying that none of the variables modified by ${\displaystyle C}$ occur free in ${\displaystyle R}$, i.e. none of them are in the 'free variable' set ${\displaystyle {\mathsf {fv}}}$ of ${\displaystyle R}$.

Sharing

Separation logic leads to simple proofs of pointer manipulation for data structures that exhibit regular sharing patterns which can be described simply using separating conjunctions; examples include singly and doubly linked lists and varieties of trees. Graphs and DAGs and other data structures with more general sharing are more difficult for both formal and informal proof. Separation logic has, nonetheless, been applied successfully to reasoning about programs with general sharing.

In their POPL'01 paper, ^[3] O'Hearn and Ishtiaq explained how the magic wand connective ${\displaystyle {-\!\!*}}$ could be used to reason in the presence of sharing, at least in principle. For example, in the triple

${\displaystyle \{(x\mapsto -)\ast ((x\mapsto 42){-\!\!*}P)\}\ [x]=42\ \{P\}}$

we obtain the weakest precondition for a statement that mutates the heap at location ${\displaystyle x}$, and this works for any postcondition, not only one that is laid out neatly using the separating conjunction. This idea was taken much further by Yang, who used ${\displaystyle {-\!\!*}}$ to provide localized reasoning about mutations in the classic Schorr-Waite graph marking algorithm. ^[8] Finally, one of the most recent works in this direction is that of Hobor and Villard, ^[9] who employ not only ${\displaystyle {-\!\!*}}$ but also a connective ${\displaystyle \cup \,\!\!\!\!\!*}$ which has variously been called overlapping conjunction or sepish, ^[10] and which can be used to describe overlapping data structures: ${\displaystyle P\cup \!\!\!\!\!*Q}$ holds of a heap ${\displaystyle h}$ when ${\displaystyle P}$ and ${\displaystyle Q}$ hold for subheaps ${\displaystyle h_{P}}$ and ${\displaystyle h_{Q}}$ whose union is ${\displaystyle h}$, but which possibly have a nonempty portion ${\displaystyle h_{P}\cap h_{Q}}$ in common. Abstractly, ${\displaystyle P\cup \!\!\!\!\!*Q}$ can be seen to be a version of the fusion connective of relevance logic.

Concurrent separation logic

A Concurrent Separation Logic (CSL), a version of separation logic for concurrent programs, was originally proposed by Peter O'Hearn, ^[11] using a proof rule

${\displaystyle {\frac {\{P_{1}\}C_{1}\{Q_{1}\}\quad \{P_{2}\}C_{2}\{Q_{2}\}}{\{P_{1}*P_{2}\}C_{1}\parallel C_{2}\{Q_{1}*Q_{2}\}}}}$

which allows independent reasoning about threads that access separate storage. O'Hearn's proof rules adapted an early approach of Tony Hoare to reasoning about concurrency, ^[12] replacing the use of scoping constraints to ensure separation by reasoning in separation logic. In addition to extending Hoare's approach to apply in the presence of heap-allocated pointers, O'Hearn showed how reasoning in concurrent separation logic could track dynamic ownership transfer of heap portions between processes; examples in the paper include a pointer-transferring buffer, and a memory manager.

Commenting on the early classical work on interference freedom by Susan Owicki and David Gries, O'Hearn says that explicit checking for non-interference isn't necessary because his system rules out interference in an implicit way, by the nature of the way proofs are constructed.

A model for concurrent separation logic was first provided by Stephen Brookes in a companion paper to O'Hearn's. ^[13] The soundness of the logic had been a difficult problem, and in fact a counterexample of John Reynolds had shown the unsoundness of an earlier, unpublished version of the logic; the issue raised by Reynolds's example is described briefly in O'Hearn's paper, and more thoroughly in Brookes's.

At first it appeared that CSL was well suited to what Dijkstra had called loosely connected processes, ^[14] but perhaps not to fine-grained concurrent algorithms with significant interference. However, gradually it was realized that the basic approach of CSL was considerably more powerful than first envisaged, if one employed non-standard models of the logical connectives and even the Hoare triples.

An abstract version of separation logic was proposed that works for Hoare triples where the preconditions and postconditions are formulae interpreted over an arbitrary partial commutative monoid instead of a particular heap model. ^[15] Later, by suitable choice of commutative monoid, it was surprisingly found that the proof rules of abstract versions of concurrent separation logic could be used to reason about interfering concurrent processes, for example by encoding the rely-guarantee technique which had been originally proposed to reason about interference; ^[16] in this work the elements of the model were considered not resources, but rather "views" of the program state, and a non-standard interpretation of Hoare triples accompanies the non-standard reading of pre and postconditions. Finally, CSL-style principles have been used to compose reasoning about program histories instead of program states, in order to provide modular techniques for reasoning about fine-grained concurrent algorithms. ^[17]

Versions of CSL have been included in many interactive and semi-automatic (or "in-between") verification tools as described in the next section. A particularly significant verification effort is that of the μC/OS-II kernel mentioned there. But, although steps have been made, ^[18] as of yet CSL-style reasoning has been included in comparatively few tools in the automatic program analysis category (and none mentioned in the next section).

O'Hearn and Brookes are co-recipients of the 2016 Gödel Prize for their invention of Concurrent Separation Logic. ^[19]

Verification and program analysis tools

Tools for reasoning about programs fall on a spectrum from fully automatic program analysis tools, which do not require any user input, to interactive tools where the human is intimately involved in the proof process. Many such tools have been developed; the following list includes a few representatives in each category.

• Automatic Program Analyses. These tools typically look for restricted classes of bugs (e.g., memory safety errors) or attempt to prove their absence, but fall short of proving full correctness.
  • A current example is Facebook Infer, a static analysis tool for Java, C, and Objective-C based on separation logic and bi-abduction. ^[20] As of 2015 hundreds of bugs per month were being found by Infer and fixed by developers before being shipped to Facebook's mobile apps ^[21]
  • Other examples include SpaceInvader (one of the first SL analyzers), Predator (which has won several verification competitions), MemCAD (which mixes shape and numerical properties) and SLAyer (from Microsoft Research, focussed on data structures found in device drivers)
• Interactive Proof. Proofs have been done using embeddings of Separation Logic into interactive theorem provers such as the Coq proof assistant and HOL (proof assistant). In comparison to the program analysis work, these tools require more in the way of human effort but prove deeper properties, up to functional correctness.
  • A proof of the FSCQ file system ^[22] where the specification includes behaviour under crashes as well as normal operation. This work won the best paper award at the 2015 Symposium on Operating System Principles.
  • Verification of a large fragment of the Rust type system and some of its standard libraries in the RustBelt project using the Iris framework for separation logic in The Coq proof assistant.
  • Verification of an OpenSSL implementation of a cryptographic authentication algorithm, ^[23] utilizing verifiable C
  • Verification of key modules of a commercial OS kernel, the μC/OS-II kernel, the first commercial pre-emptive kernel to have been verified. ^[24]
  • Other examples include the Ynot ^[25] library for the Coq proof assistant; the Holfoot embedding of Smallfoot in HOL; Fine-grained Concurrent Separation Logic, and Bedrock (a Coq library for low-level programming).
• In Between. Many tools require more user intervention than program analyses, in that they expect the user to input assertions such as pre/post specs for functions or loop invariants, but after this input is given they attempt to be fully or almost fully automatic; this mode of verification goes back to classic works in the 1970s such as J King's verifier, and the Stanford Pascal Verifier. This style of verifier has recently been called auto active verification, a term which intends to evoke the way of interacting with a verifier via an assert-check loop, analogous to the interaction between a programmer and a type-checker.
  • The very first Separation Logic verifier, Smallfoot, was in this in-between category. It required the user to input pre/post specs, loop invariants, and resource invariants for locks. It introduced a method of symbolic execution, as well as an automatic way to infer frame axioms. Smallfoot included Concurrent Separation Logic.
  • SmallfootRG is a verifier for a marriage of separation logic and the classic rely/guarantee method for concurrent programs.
  • Heap Hop implements a separation logic for message passing, following the ideas in Singularity (operating system).
  • VeriFast is an advanced current tool in the in-between category. It has demonstrated proofs ranging from object-oriented patterns to highly concurrent algorithms and to systems programs.
  • Viper is a state-of-the-art automated verification infrastructure for permission-based reasoning. It mainly consists of a programming language and two verification backends, one based on symbolic execution and another one on verification condition generation (VCG). ^[26] Based on the Viper infrastructure, several frontends for various programming languages have emerged: Gobra for Go, Nagini for Python, Prusti for Rust, and VerCors for C, Java, OpenCL, and OpenMP. These frontends translate the frontend programming language into Viper to then use a Viper verification backend for proving the input program's correctness.
  • The Mezzo Programming Language and Asynchronous Liquid Separation Types include ideas related to CSL in the type system for a programming language. The idea to include separation in a type system has earlier examples in Alias Types and Syntactic Control of Interference.

The distinction between interactive and in-between verifiers is not a sharp one. For example, Bedrock strives for a high degree of automation, in what it terms mostly-automatic verification, where Verifast sometimes requires annotations that resemble the tactics (little programs) used in interactive verifiers.

Decidability and complexity

The satisfiability problem for a quantifier-free, multi-sorted fragment of separation logic parameterized over the sorts of locations and data can be shown to be PSPACE-complete. ^[27] An algorithm for solving this fragment in DPLL(T)-based SMT solvers has been integrated into cvc5. ^[28] Extending this result, satisfiability for an analog of the Bernays–Schönfinkel class for separation logic with uninterpreted memory locations can also be shown to be PSPACE-complete, whereas the problem is undecidable with interpreted memory locations (e.g., integers) or further quantifier alternations ^[29]

References

1. Reynolds, John C. (2002). "Separation Logic: A Logic for Shared Mutable Data Structures" (PDF). LICS.
2. Reynolds, John C. (1999). "Intuitionistic Reasoning about Shared Mutable Data Structure". In Davies, Jim; Roscoe, Bill; Woodcock, Jim (eds.). Millennial Perspectives in Computer Science, Proceedings of the 1999 Oxford–Microsoft Symposium in Honour of Sir Tony Hoare. Palgrave.
3. Ishtiaq, Samin; O'Hearn, Peter (2001). "BI as an assertion language for mutable data structures". Proceedings of the 28th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. ACM. pp. 14–26. doi:10.1145/360204.375719. ISBN   1581133367. S2CID   2652274.{{cite book}}: |journal= ignored (help)
4. O'Hearn, Peter; Reynolds, John C.; Yang, Hongseok (2001). "Local Reasoning about Programs that Alter Data Structures". CSL. CiteSeerX   10.1.1.29.1331 .
5. Burstall, R. M. (1972). "Some techniques for proving programs which alter data structures". Machine Intelligence . 7.
6. O'Hearn, P. W.; Pym, D. J. (June 1999). "The Logic of Bunched Implications". Bulletin of Symbolic Logic . 5 (2): 215–244. CiteSeerX   10.1.1.27.4742 . doi:10.2307/421090. JSTOR   421090. S2CID   2948552.
7. O'Hearn, Peter (February 2019). "Separation Logic". Commun. ACM. 62 (2): 86–95. doi: 10.1145/3211968 . ISSN   0001-0782.
8. Yang, Hongseok (2001). "An Example of Local Reasoning in BI Pointer Logic: the Schorr−Waite Graph Marking Algorithm". Proceedings of the 1st Workshop on Semantics' Program Analysis' and Computing Environments for Memory Management.
9. Hobor, Aquinas; Villard, Jules (2013). "The ramifications of sharing in data structures" (PDF). ACM SIGPLAN Notices. 48: 523–536. doi:10.1145/2480359.2429131.
10. Gardner, Philippa; Maffeis, Sergio; Smith, Hareth (2012). "Towards a program logic for Java Script" (PDF). Proceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '12. pp. 31–44. doi:10.1145/2103656.2103663. hdl:10044/1/33265. ISBN   9781450310833. S2CID   9571576.
11. O'Hearn, Peter (2007). "Resources, Concurrency and Local Reasoning" (PDF). Theoretical Computer Science. 375 (1–3): 271–307. doi: 10.1016/j.tcs.2006.12.035 .
12. Hoare, C.A.R. (1972). "Towards a theory of parallel programming". Operating System Techniques. Academic Press.
13. Brookes, Stephen (2007). "A Semantics for Concurrent Separation Logic" (PDF). Theoretical Computer Science. 375 (1–3): 227–270. doi:10.1016/j.tcs.2006.12.034.
14. Dijkstra, Edsger W. Cooperating sequential processes (EWD-123) (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. ( transcription ) (September 1965)
15. Calcagno, Cristiano; O'Hearn, Peter W.; Yang, Hongseok (2007). "Local Action and Abstract Separation Logic" (PDF). 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007). pp. 366–378. CiteSeerX   10.1.1.66.6337 . doi:10.1109/LICS.2007.30. ISBN   978-0-7695-2908-0. S2CID   1044254.
16. Dinsdale-Young, Thomas; Birkedal, Lars; Gardner, Philippa; Parkinson, Matthew; Yang, Hongseok (2013). "Views" (PDF). ACM SIGPLAN Notices. 48: 287–300. doi:10.1145/2480359.2429104.
17. Sergey, Ilya; Nanevski, Aleksandar; Banerjee, Anindya (2015). "Specifying and Verifying Concurrent Algorithms with Histories and Subjectivity" (PDF). 24th European Symposium on Programming. arXiv: 1410.0306 . Bibcode:2014arXiv1410.0306S.
18. Gotsman, Alexey; Berdine, Josh; Cook, Byron; Sagiv, Mooly (2007). "Thread-Modular Shape Analysis". Verification, Model Checking, and Abstract Interpretation (PDF). Lecture Notes in Computer Science. Vol. 5403. pp. 266–277. doi:10.1007/978-3-540-93900-9_3. ISBN   978-3-540-93899-6.{{cite book}}: |journal= ignored (help)
19. "2016 Gödel Prize". European Association for Theoretical Computer Science. Retrieved 2022-08-29.
20. Separation logic and bi-abduction, page, Infer project site.
21. Open-sourcing Facebook Infer: Identify bugs before you ship. C Calcagno, D DIstefano and P O'Hearn. 11 June 2015
22. Using Crash Hoare Logic for Certifying the FSCQ File System, H Chen et al, SOSP'15
23. Verified correctness and security of OpenSSL HMAC. Lennart Beringer, Adam Petcher, Katherine Q. Ye, and Andrew W. Appel. In 24th USENIX Security Symposium, August 2015
24. A Practical Verification Framework for Preemptive OS Kernels. Fengwei Xu, Ming Fu, Xinyu Feng, Xiaoran Zhang, Hui Zhang and Zhaohui Li:. In CAV 2016: 59-79
25. The Ynot Project homepage, Harvard University, USA.
26. Viper: A Verification Infrastructure for Permission-Based Reasoning, P. Müller, M. Schwerhoff, and A. J. Summers, VMCAI'16
27. Reynolds, Andrew; Iosif, Radu; Serban, Cristina; King, Tim (2016). "A Decision Procedure for Separation Logic in SMT". In Artho, Cyrille; Legay, Axel; Peled, Doron (eds.). Automated Technology for Verification and Analysis. Lecture Notes in Computer Science. Cham: Springer International Publishing. pp. 244–261. arXiv: 1603.06844 . doi:10.1007/978-3-319-46520-3_16. ISBN   978-3-319-46520-3.
28. Barbosa, Haniel; Barrett, Clark; Brain, Martin; Kremer, Gereon; Lachnitt, Hanna; Mann, Makai; Mohamed, Abdalrhman; Mohamed, Mudathir; Niemetz, Aina; Nötzli, Andres; Ozdemir, Alex; Preiner, Mathias; Reynolds, Andrew; Sheng, Ying; Tinelli, Cesare (2022). "cvc5: A Versatile and Industrial-Strength SMT Solver". In Fisman, Dana; Rosu, Grigore (eds.). Tools and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science. Cham: Springer International Publishing. pp. 415–442. doi: 10.1007/978-3-030-99524-9_24 . ISBN   978-3-030-99524-9.
29. Reynolds, Andrew; Iosif, Radu; Serban, Cristina (2017). "Reasoning in the Bernays-Schönfinkel-Ramsey Fragment of Separation Logic". In Bouajjani, Ahmed; Monniaux, David (eds.). Verification, Model Checking, and Abstract Interpretation. Lecture Notes in Computer Science. Cham: Springer International Publishing. pp. 462–482. doi:10.1007/978-3-319-52234-0_25. ISBN   978-3-319-52234-0.