Fully Composable and Adequate Verified Compilation with Direct Refinements between Open Modules
Ling Zhang, Yuting Wang, Jinhua Wu, Jérémie Koenig, Zhong Shao
Abstract
Verified compilation of open modules (i.e., modules whose functionality depends on other modules) provides a foundation for end-to-end verification of modular programs ubiquitous in contemporary software. However, despite intensive investigation in this topic for decades, the proposed approaches are still difficult to use in practice as they rely on assumptions about the internal working of compilers which make it difficult for external users to apply the verification results. We propose an approach to verified compositional compilation without such assumptions in the setting of verifying compilation of heterogeneous modules written in first-order languages supporting global memory and pointers. Our approach is based on the memory model of CompCert and a new discovery that a Kripke relation with a notion of memory protection can serve as a uniform and composable semantic interface for the compiler passes. By absorbing the rely-guarantee conditions on memory evolution for all compiler passes into this Kripke Memory Relation and by piggybacking requirements on compiler optimizations onto it, we get compositional correctness theorems for realistic optimizing compilers as refinements that directly relate native semantics of open modules and that are ignorant of intermediate compilation processes. Such direct refinements support all the compositionality and adequacy properties essential for verified compilation of open modules. We have applied this approach to the full compilation chain of CompCert with its Clight source language and demonstrated that our compiler correctness theorem is open to composition and intuitive to use with reduced verification complexity through end-to-end verification of non-trivial heterogeneous modules that may freely invoke each other (e.g., mutually recursively).
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.
6 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
- SECOMP: Formally Secure Compilation of Compartmentalized C Programs cites CompCertM: CompCert with C-assembly linking and lightweight modular verification
- Choice Trees: Representing Nondeterministic, Recursive, and Impure Programs in Coq cites Interaction trees: representing recursive and impure programs in Coq
- Choice Trees: Representing Nondeterministic, Recursive, and Impure Programs in Coq cites Promising 2.0: global optimizations in relaxed memory concurrency
- Unifying Compositional Verification and Certified Compilation with a Three-Dimensional Refinement Algebra cites Conditional Contextual Refinement
- Unifying Compositional Verification and Certified Compilation with a Three-Dimensional Refinement Algebra cites CompCertM: CompCert with C-assembly linking and lightweight modular verification
- Pyrosome: Verified Compilation for Modular Metatheory cites Interaction trees: representing recursive and impure programs in Coq
- Let It Flow: A Formally Verified Compilation Framework for Asynchronous Dataflow cites Interaction trees: representing recursive and impure programs in Coq
- Let It Flow: A Formally Verified Compilation Framework for Asynchronous Dataflow cites CompCertM: CompCert with C-assembly linking and lightweight modular verification
- CRIS: The Power of Imagination in Hybrid Verification cites Unifying Compositional Verification and Certified Compilation with a Three-Dimensional Refinement Algebra
- CRIS: The Power of Imagination in Hybrid Verification cites Conditional Contextual Refinement
- CRIS: The Power of Imagination in Hybrid Verification cites Interaction trees: representing recursive and impure programs in Coq
- Conditional Contextual Refinement cites Interaction trees: representing recursive and impure programs in Coq
- Conditional Contextual Refinement cites CompCertM: CompCert with C-assembly linking and lightweight modular verification
Cited by top-tier papers6
- Unifying Compositional Verification and Certified Compilation with a Three-Dimensional Refinement AlgebraYu Zhang, Jérémie Koenig, Zhong Shao, Yuting WangPOPL 2025 · 2 citations
- SECOMP: Formally Secure Compilation of Compartmentalized C ProgramsJérémy Thibault, Roberto Blanco, Dongjae Lee, Sven Argo et al.CCS 2024 · 1 citation
- Let It Flow: A Formally Verified Compilation Framework for Asynchronous DataflowZhengyao Lin, Yi Cai, Milijana SurbatovichPLDI 2026 · 1 citation
- Pyrosome: Verified Compilation for Modular MetatheoryDustin Jamner, Gabriel Kammer, Ritam Nag, Adam ChlipalaOOPSLA 2025
- CRIS: The Power of Imagination in Hybrid VerificationYonghee Kim, Taeyoung Yoon, Sanghyun Yi, Jaehyung Lee et al.PLDI 2026
Builds on10
- Interaction trees: representing recursive and impure programs in CoqLi-yao Xia, Yannick Zakowski, Paul He, Chung-Kil Hur et al.POPL 2020 · 133 citations
- CompCertM: CompCert with C-assembly linking and lightweight modular verificationYoungju Song, Minki Cho, Dongjoo Kim, Yonghyun Kim et al.POPL 2020 · 49 citations
- Promising 2.0: global optimizations in relaxed memory concurrencySung-Hwan Lee, Minki Cho, Anton Podkopaev, Soham Chakraborty et al.PLDI 2020 · 48 citations
- Conditional Contextual RefinementYoungju Song, Minki Cho, Dongjae Lee, Chung-Kil Hur et al.POPL 2023 · 29 citations
- Choice Trees: Representing Nondeterministic, Recursive, and Impure Programs in CoqNicolas Chappe, Paul He, Ludovic Henrio, Yannick Zakowski et al.POPL 2023 · 21 citations
Related papers
- CompCertOC: Verified Compositional Compilation of Multi-threaded Programs with Shared StacksLing Zhang, Yuting Wang, Yalun Liang, Zhong ShaoPLDI 2025
- CompCertELF: verified separate compilation of C programs into ELF object filesYuting Wang, Xiangzhe Xu, Pierre Wilke, Zhong ShaoOOPSLA 2020 · 26 citations
- Verified compilation of C programs with a nominal memory modelYuting Wang, Ling Zhang, Zhong Shao, Jérémie KoenigPOPL 2022 · 6 citations
- Certified and efficient instruction scheduling: application to interlocked VLIW processorsCyril Six, Sylvain Boulmé, David MonniauxOOPSLA 2020 · 21 citations
- Archmage and CompCertCast: End-to-End Verification Supporting Integer-Pointer CastingYonghyun Kim, Minki Cho, Jaehyung Lee, Jinwoo Kim et al.POPL 2025 · 1 citation
