Compositional Non-Interference for Fine-Grained Concurrent Programs
Dan Frumin, Robbert Krebbers, Lars Birkedal
Abstract
Non-interference is a program property that ensures the absence of information leaks. In the context of programming languages, there exist two common approaches for establishing non-interference: type systems and program logics. Type systems provide strong automation (by means of type checking), but they are inherently restrictive in the kind of programs they support. Program logics support challenging programs, but they typically require significant human assistance, and cannot handle modules or higher-order programs.To connect these two approaches, we present SeLoC—a separation logic for non-interference, on top of which we build a type system using the technique of logical relations. By building a type system on top of separation logic, we can compositionally verify programs that consist of typed and untyped parts. The former parts are verified through type checking, while the latter parts are verified through manual proof.The core technical contribution of SeLoC is a relational form of weakest preconditions that can track information flow using separation logic resources. SeLoC is fully machine-checked, and built on top of the Iris framework for concurrent separation logic in Coq. The integration with Iris provides seamless support for fine-grained concurrency, which was beyond the reach of prior type systems and program logics for non-interference.
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.
11 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
- Proof Automation for Linearizability in Separation Logic cites Mechanized logical relations for termination-insensitive noninterference
- Asynchronous Probabilistic Couplings in Higher-Order Separation Logic cites Mechanized logical relations for termination-insensitive noninterference
Cited by top-tier papers11
- Transfinite Iris: resolving an existential dilemma of step-indexed separation logicSimon Spies, Lennard Gäher, Daniel Gratzer, Joseph Tassarotti et al.PLDI 2021 · 32 citations
- Asynchronous Probabilistic Couplings in Higher-Order Separation LogicSimon Oddershede Gregersen, Alejandro Aguirre, Philipp G. Haselwarter, Joseph Tassarotti et al.POPL 2024 · 23 citations
- Mechanized logical relations for termination-insensitive noninterferenceSimon Oddershede Gregersen, Johan Bay, Amin Timany, Lars BirkedalPOPL 2021 · 14 citations
- CommCSL: Proving Information Flow Security for Concurrent Programs using Abstract CommutativityMarco Eilers, Thibault Dardinier, Peter MüllerPLDI 2023 · 9 citations
- Proof Automation for Linearizability in Separation LogicIke Mulder, Robbert KrebbersOOPSLA 2023 · 8 citations
Related papers
- 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
- Program Logics à la CarteMax Vistrup, Michael Sammler, Ralf JungPOPL 2025 · 4 citations
- Beyond Backtracking: Connections in Fine-Grained Concurrent Separation LogicIke Mulder, Lukasz Czajka, Robbert KrebbersPLDI 2023 · 2 citations
- Deadlock-Free Separation Logic: Linearity Yields Progress for Dependent Higher-Order Message PassingJules Jacobs, Jonas Kastberg Hinrichsen, Robbert KrebbersPOPL 2024 · 12 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
