Conditional Contextual Refinement
Youngju Song, Minki Cho, Dongjae Lee, Chung-Kil Hur, Michael Sammler, Derek Dreyer
Abstract
Much work in formal verification of low-level systems is based on one of two approaches: refinement or separation logic. These two approaches have complementary benefits: refinement supports the use of programs as specifications, as well as transitive composition of proofs, whereas separation logic supports conditional specifications, as well as modular ownership reasoning about shared state. A number of verification frameworks employ these techniques in tandem, but in all such cases the benefits of the two techniques remain separate. For example, in frameworks that use relational separation logic to prove contextual refinement, the relational separation logic judgment does not support transitive composition of proofs, while the contextual refinement judgment does not support conditional specifications. In this paper, we propose Conditional Contextual Refinement (or CCR, for short), the first verification system to not only combine refinement and separation logic in a single framework but also to truly marry them together into a unified mechanism enjoying all the benefits of refinement and separation logic simultaneously. Specifically, unlike in prior work, CCR’s refinement specifications are both conditional (with separation logic pre- and post-conditions) and transitively composable. We implement CCR in Coq and evaluate its effectiveness on a range of interesting examples.
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.
19 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
- Melocoton: A Program Logic for Verified Interoperability Between OCaml and C cites DimSum: A Decentralized Approach to Multi-language Semantics and Verification
- Melocoton: A Program Logic for Verified Interoperability Between OCaml and C cites CompCertM: CompCert with C-assembly linking and lightweight modular verification
- DimSum: A Decentralized Approach to Multi-language Semantics and Verification cites Interaction trees: representing recursive and impure programs in Coq
- DimSum: A Decentralized Approach to Multi-language Semantics and Verification cites Simuliris: a separation logic framework for verifying concurrent program optimizations
- DimSum: A Decentralized Approach to Multi-language Semantics and Verification cites CompCertM: CompCert with C-assembly linking and lightweight modular verification
- Fair Operational Semantics cites Interaction trees: representing recursive and impure programs in Coq
- Fair Operational Semantics cites Simuliris: a separation logic framework for verifying concurrent program optimizations
- Fully Composable and Adequate Verified Compilation with Direct Refinements between Open Modules cites DimSum: A Decentralized Approach to Multi-language Semantics and Verification
- Fully Composable and Adequate Verified Compilation with Direct Refinements between Open Modules cites Interaction trees: representing recursive and impure programs in Coq
- Fully Composable and Adequate Verified Compilation with Direct Refinements between Open Modules cites CompCertM: CompCert with C-assembly linking and lightweight modular verification
- Simuliris: a separation logic framework for verifying concurrent program optimizations cites Interaction trees: representing recursive and impure programs in Coq
- Stuttering for Free cites DimSum: A Decentralized Approach to Multi-language Semantics and Verification
- Stuttering for Free cites Fair Operational Semantics
- Stuttering for Free cites Interaction trees: representing recursive and impure programs in Coq
- Stuttering for Free cites Simuliris: a separation logic framework for verifying concurrent program optimizations
- Stuttering for Free cites Armada: low-effort verification of high-performance concurrent programs
- Stuttering for Free cites CompCertM: CompCert with C-assembly linking and lightweight modular verification
Cited by top-tier papers19
- DimSum: A Decentralized Approach to Multi-language Semantics and VerificationMichael Sammler, Simon Spies, Youngju Song, Emanuele D'Osualdo et al.POPL 2023 · 18 citations
- Stuttering for FreeMinki Cho, Youngju Song, Dongjae Lee, Lennard Gäher et al.OOPSLA 2023 · 11 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
- Fair Operational SemanticsDongjae Lee, Minki Cho, Jinwoo Kim, Soonwon Moon et al.PLDI 2023 · 10 citations
- Fully Composable and Adequate Verified Compilation with Direct Refinements between Open ModulesLing Zhang, Yuting Wang, Jinhua Wu, Jérémie Koenig et al.POPL 2024 · 10 citations
Builds on6
- Interaction trees: representing recursive and impure programs in CoqLi-yao Xia, Yannick Zakowski, Paul He, Chung-Kil Hur et al.POPL 2020 · 133 citations
- A Secure and Formally Verified Linux KVM HypervisorShih-Wei Li, Xupeng Li, Ronghui Gu, Jason Nieh et al.S&P 2021 · 72 citations
- CompCertM: CompCert with C-assembly linking and lightweight modular verificationYoungju Song, Minki Cho, Dongjoo Kim, Yonghyun Kim et al.POPL 2020 · 49 citations
- Simuliris: a separation logic framework for verifying concurrent program optimizationsLennard Gäher, Michael Sammler, Simon Spies, Ralf Jung et al.POPL 2022 · 33 citations
- Armada: low-effort verification of high-performance concurrent programsJacob R. Lorch, Yixuan Chen, Manos Kapritsos, Bryan Parno et al.PLDI 2020 · 25 citations
Related papers
- CRIS: The Power of Imagination in Hybrid VerificationYonghee Kim, Taeyoung Yoon, Sanghyun Yi, Jaehyung Lee et al.PLDI 2026
- 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
- Proof Automation for Linearizability in Separation LogicIke Mulder, Robbert KrebbersOOPSLA 2023 · 8 citations
- Compositional Non-Interference for Fine-Grained Concurrent ProgramsDan Frumin, Robbert Krebbers, Lars BirkedalS&P 2021 · 20 citations
- A Verified Foreign Function Interface between Coq and CJoomy Korkut, Kathrin Stark, Andrew W. AppelPOPL 2025 · 3 citations
