Compositional Verification in Concurrent Separation Logic with Permissions Regions
Quang Loc Le · 2025
Read Compositional Verification in Concurrent Separation Logic with Permissions Regions by Quang Loc Le (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-18115.txt.
Introduction
Le builds a part-wise proof kit for shared-store code in this twenty twenty-five paper. Split-proof logic lets coders prove code that shares store bits tween threads. Its share marks split store rights, yet tools lacked part-wise proof flow.
Inside, fresh proof rules let each thread's proof stand on its own feet. A tail-find step works out the left store a proof frame must keep. Set count bounds on store splits ride in the step as plain facts. A test tool runs the kit on ten hard shared-store codes. Some of those codes sat past the reach of past proof tools.
Catalog record
| CREATOR | Quang Loc Le |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 96 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-18115
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Compositional Verification in Concurrent Separation Logic with Permissions Regions Quang Loc Le Abstract Concurrent separation logic with fractional permissions ( CSL-Perm ) provides a promising reasoning system to verify most complex sequential and concurrent fine-grained programs. The logic with strong and weak separating conjunctions offers a solid foundation for producing concise and precise proofs. However, it lacks automation and compositionality support. This paper addresses this limitation by introducing a compositional verification system for concurrent programs that manipulate regions of shared memory. The centre of our system is novel logical principles and an entailment procedure that can infer the residual heaps in the frame rule for a fragment of CSL-Perm with explicit arithmetical constraints for memory heaps’ disjointness. This procedure enables the compositional reasoning for concurrent threads and function calls. We have implemented the proposal in a prototype tool called CoSl , tested it with 10 challenging concurrent programs, including those beyond the state-of-the-art, and confirmed the advantage of our approach. 1 Introduction This paper introduces a novel compositional verification system for concurrent separation logic with permissions regions ( CSL-Perm ) [ 3 , 8 , 27 ] , a promising reasoning system for analysing heap-alternating concurrent programs. While the state-of-the-art CSL-Perm , presented in [ 8 ] , includes both strong separating conjunction * (to reason about disjointness of heap manipulation) and weak separating conjunction \circledast (to reason on shared resources), our system takes a step further by providing automated and compositional verification. We demonstrate the effectiveness of our system by applying it to verify 10 challenging fine-grained algorithms. In the following, we delve into the development of CSL-Perm and compositional analysis, as well as our motivations and contributions. Compositional verification for inter-procedures. One of the key challenges in program analysis is local reasoning about heap-mutating programs. Separation logic (SL) [ 30 ] provides a well-established framework for local reasoning. It includes separating conjunction * to specify the disjointness of heap memory: A*B is a heap that can be split in two separate parts satisfying A and B ; each part, A and B , can be analysed independently and locally via the following frame rule. {\color[rgb]{0,0,1}{\left\{P\right\}}}{C}{\color[rgb]{0,0,1}{\left\{Q\right\}}} (\mathrm{Frame{*}-SL}) (\dagger{:}~\mathit{Modify(C)}\cap\mathit{FreeVar(F)}=\emptyset) {\color[rgb]{0,0,1}{\left\{P*F\right\}}}{C}{\color[rgb]{0,0,1}{\left\{Q*F\right\}}} This rule reads: The valid Hoare triple {\color[rgb]{0,0,1}{\left\{P\right\}}}{C}{\color[rgb]{0,0,1}{\left\{Q\right\}}} can be extended to any separated symbolic heap F whenever the program C does not modify the free variables of F . Frame inference technique further advances local reasoning by inferring the frame F automatically. By so doing, it enables the compositional verification and achieves scalability for inter-procedural analysis [ 17 ] (i.e., the analysis performance is proportional to the number of procedures rather than the number of procedure calls). Frame inference, the foundation of bi-abduction [ 9 ] , has established in academic and industrial settings: The Infer team at Meta implemented it to catch thousands of bugs in Meta’s codebases [ 19 , 25 ] . Compositional verification for concurrent threads. There have been some preliminary efforts to transfer compositional verification to concurrency world using concurrent separation logic (CSL) [ 31 ] . CSL extends SL to reason about coarse-grained programs with concurrent threads (those include semaphores, conditional critical regions or monitors). In those programs, each thread owns a separate portion of resources. CSL proposed to utilise the separating conjunction to specify separated ownership of resources: P_{1}*P_{2} is a resource whose ownership can be split into two parts owned by P_{1} and P_{2} separately. Program analysis can obtain the thread-modular reasoning via the following inference rule. {\color[rgb]{0,0,1}{\left\{P_{1}\right\}}}{C_{1}}{\color[rgb]{0,0,1}{\left\{Q_{1}\right\}}} {\color[rgb]{0,0,1}{\left\{P_{2}\right\}}}{C_{2}}{\color[rgb]{0,0,1}{\left\{Q_{2}\right\}}} (\mathrm{Concurrency-CSL}) Non-interference condition {\color[rgb]{0,0,1}{\left\{P_{1}*P_{2}\right\}}}{C_{1}||C_{2}}{\color[rgb]{0,0,1}{\left\{Q_{1}*Q_{2}\right\}}} The rule reads: If C_{1} and C_{2} are non-interference concurrent processes (i.e., C_{1} does not modify free variables in P_{2} and Q_{2} and vice versa), then we can analyse these threads independently in the separated ownership P_{1} and P_{2} and combined their analysis results Q_{1} and Q_{2} afterwards. However, the rule above does not work for fine-grained programs in which threads interferes each other (e.g., a program with two threads sharing read-only variables). To support concurrent fine-grained programs, Bornat et at. [ 3 ] presented the first proposal of CSL-Perm . They introduced fractional permission over shared heaps, e.g., A^{\pi} is a heap A which owns \pi permission. If a thread owns full permission over a resource, it could modify it; otherwise, it has read-only permission. Furthermore, the logic specifies shared heaps using weak separating conjunction \circledast (where it is usually written as * ). For instance, A^{0.5}\circledast A^{0.5} means A divides into two parts, each owning 0.5 permissions on A . It also introduces (\mathrm{Frame}\circledast) and (\mathrm{Concurrency}) by replacing * with \circledast in rules (\mathrm{Frame{*}-SL}) and (\mathrm{Concurrency-CSL}) to reason about shared heaps in concurrent fine-grained programs. However, this logic cannot specify heaps’ disjointness precisely; for instance, essential entailments such as A^{0.5}*B^{0.5}\models(A*B)^{0.5} is valid in CSL but A^{0.5}\circledast B^{0.5}\models(A\circledast B)^{0.5} is false in CSL-Perm . Consequently, it can support neither coarse-grained nor most sequential heap-manipulating programs. To bridge the gap of CSL-Perm [ 3 ] , Le et al. presented an ad-hoc fix to reason on the disjointness [ 27 ] . However, this fix only works for precise formulas [ 6 ] . Recently, Brotherston et al. introduced {\mathsf{SL}_{\mathsf{LP}}} , a unified separation logic with both strong separating conjunction * and and weak separating conjunction \circledast , that can reason about both interfered threads, disjointness of threads and sequential heap-manipulating programs [ 8 ] . {\mathsf{SL}_{\mathsf{LP}}} includes heap labels and fractional permissions, e.g., (\alpha\land A)^{\pi} is a heap A which has label \alpha and owns \pi permission, and novel logical principles to retain the heaps’ disjointness when switching between * and \circledast . However, while this logic demonstrated such a principle for identical heap formulas, i.e., (\alpha\wedge A)^{\pi_{1}}\circledast(\alpha\wedge A)^{\pi_{2}}\models(\alpha\wedge A)^{\pi_{1}\oplus\pi_{2}} , it did not show those principles for arbitrary formulas. Hence, a proof system based on {\mathsf{SL}_{\mathsf{LP}}} might not be as strong as the authors had expected. Moreover, a study on a frame inference procedure in {\mathsf{SL}_{\mathsf{LP}}} , which is essential for automation and compositional reasoning, is still missing. Since the two conjunctions * and \circledast may be alternately nested, developing a frame inference procedure on this logic is non-trivial. Lastly, beside of (\mathrm{Frame}\circledast) for \circledast , {\mathsf{SL}_{\mathsf{LP}}} includes another frame rule (\mathrm{Frame}*) for * . Another unanswered question is how the analysis could efficiently decide which frame rule could be applied at a program point. Contributions. This paper addresses the aforementioned challenges. We develop a compositional verification with a frame inference procedure for \mathsf{SL}_{\mathsf{aLP}} , an analogy of {\mathsf{SL}_{\mathsf{LP}}} [ 8 ] . In our logic, we write @_{\alpha}A^{\pi} for a heap A which has label \alpha and owns \pi permission and introduce arithmetical operators over heap labels \alpha to keep track of the heaps’ disjointness. These operators are essential to support both frame rules. Moreover, we make the following primary contributions. • We present new distribution principles that retain disjointness over arbitrary formulas so that our system can transform back and forth between the two separating conjunctions. • We propose a frame inference procedure for \mathsf{SL}_{\mathsf{aLP}} that implements the distribution principles via inference rules. The new principles enable our reasoning system to be more precise than the one in [ 8 ] , as it could recover * from \circledast . • We introduce a