Zoo: A Framework for the Verification of Concurrent OCaml 5 Programs using Separation Logic
Clément Allain, Gabriel Scherer
Abstract
The release of OCaml 5, which introduced parallelism in the OCaml runtime, drove the need for safe and efficient concurrent data structures. New libraries like Saturn address this need. This is an opportunity to apply and further state-of-the-art program verification techniques.
We present Zoo, a framework for verifying fine-grained concurrent OCaml 5 algorithms. Following a pragmatic approach, we defined a limited but sufficient fragment of the language to faithfully express these algorithms: ZooLang. We formalized its semantics carefully via a deep embedding in the Rocq proof assistant, uncovering subtle aspects of physical equality. We provide a tool to translate source OCaml programs into ZooLang syntax embedded inside Rocq, where they can be specified and verified using the Iris concurrent separation logic. To illustrate the applicability of Zoo, we verified a subset of the standard library and a collection of fined-grained concurrent data structures from the Saturn and Eio libraries.
In the process, we also extended OCaml to more efficiently express certain concurrent programs.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
2 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- RefinedC: automating the foundational verification of C code with refined ownership types cites The future is ours: prophecy variables in separation logic
- A Verified Parallel Scheduler for OCaml 5 cites Retrofitting effect handlers onto OCaml
- A Verified Parallel Scheduler for OCaml 5 cites The future is ours: prophecy variables in separation logic
- RefinedRust: A Type System for High-Assurance Verification of Rust Programs cites RefinedC: automating the foundational verification of C code with refined ownership types
- RefinedRust: A Type System for High-Assurance Verification of Rust Programs cites Verus: Verifying Rust Programs using Linear Ghost Types
Cited by top-tier papers2
Builds on11
- Verus: Verifying Rust Programs using Linear Ghost TypesAndrea Lattuada, Travis Hance, Chanhee Cho, Matthias Brun et al.OOPSLA 2023 · 86 citations
- RefinedC: automating the foundational verification of C code with refined ownership typesMichael Sammler, Rodolphe Lepigre, Robbert Krebbers, Kayvan Memarian et al.PLDI 2021 · 83 citations
- The future is ours: prophecy variables in separation logicRalf Jung, Rodolphe Lepigre, Gaurav Parthasarathy, Marianna Rapoport et al.POPL 2020 · 62 citations
- Retrofitting effect handlers onto OCamlK. C. Sivaramakrishnan, Stephen Dolan, Leo White, Tom Kelly et al.PLDI 2021 · 56 citations
- RefinedRust: A Type System for High-Assurance Verification of Rust ProgramsLennard Gäher, Michael Sammler, Ralf Jung, Robbert Krebbers et al.PLDI 2024 · 29 citations
Related papers
- Diaframe: automated verification of fine-grained concurrent programs in IrisIke Mulder, Robbert Krebbers, Herman GeuversPLDI 2022 · 27 citations
- Melocoton: A Program Logic for Verified Interoperability Between OCaml and CArmaël Guéneau, Johannes Hostert, Simon Spies, Michael Sammler et al.OOPSLA 2023 · 10 citations
- A Relational Separation Logic for Effect HandlersPaulo Emílio de Vilhena, Simcha van Collem, Ines Wright, Robbert KrebbersPOPL 2026 · 3 citations
- Proof Automation for Linearizability in Separation LogicIke Mulder, Robbert KrebbersOOPSLA 2023 · 8 citations
- Data-driven abductive inference of library specificationsZhe Zhou, Robert Dickerson, Benjamin Delaware, Suresh JagannathanOOPSLA 2021 · 15 citations
