Stuttering for Free
Minki Cho, Youngju Song, Dongjae Lee, Lennard Gäher, Derek Dreyer
Abstract
One of the most common tools for proving behavioral refinements between transition systems is the method of simulation proofs, which has been explored extensively over the past several decades. Stuttering simulations are an extension of traditional simulations—used, for example, in CompCert—in which either the source or target of the simulation is permitted to “stutter” (stay in place) while the other side steps forward. In the interest of ensuring soundness, however, existing stuttering simulations restrict proofs to only perform a finite number of stuttering steps before making synchronous progress —a step of reasoning in which both sides of the simulation progress forward together. This restriction guarantees that a terminating program cannot be proven to simulate a non-terminating one. In this paper, we observe that the requirement to eventually achieve synchronous progress is burdensome and, what’s more, unnecessary: it is possible to ensure soundness of stuttering simulations while only requiring asynchronous progress (progress on both sides of the simulation that may be achieved with only stuttering steps). Building on this observation, we develop a new simulation technique we call FreeSim (short for “freely-stuttering simulations”), mechanized in Coq, and we demonstrate its effectiveness on a range of interesting case studies. These include a simplification of the meta-theory of CompCert, as well as the DTrees library, which enriches the ITrees (Interaction Trees) library with dual non-determinism.
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.
7 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
- A Family of Sims with Diverging Interests cites Interaction trees: representing recursive and impure programs in Coq
- A Family of Sims with Diverging Interests cites Simuliris: a separation logic framework for verifying concurrent program optimizations
- Coinductive Proofs for Temporal Hyperliveness cites Interaction trees: representing recursive and impure programs in Coq
- Coinductive Proofs for Temporal Hyperliveness cites Simuliris: a separation logic framework for verifying concurrent program optimizations
- Lilo: A Higher-Order, Relational Concurrent Separation Logic for Liveness cites Conditional Contextual Refinement
- Lilo: A Higher-Order, Relational Concurrent Separation Logic for Liveness cites Simuliris: a separation logic framework for verifying concurrent program optimizations
- Conditional Contextual Refinement cites Interaction trees: representing recursive and impure programs in Coq
- Conditional Contextual Refinement cites Simuliris: a separation logic framework for verifying concurrent program optimizations
- Conditional Contextual Refinement cites CompCertM: CompCert with C-assembly linking and lightweight modular verification
- Verifying Asynchronous Hyperproperties in Reactive Systems cites Coinductive Proofs for Temporal Hyperliveness
- Simuliris: a separation logic framework for verifying concurrent program optimizations cites Interaction trees: representing recursive and impure programs in Coq
Cited by top-tier papers7
- SNIP: Speculative Execution and Non-Interference Preservation for Compiler TransformationsSören van der Wall, Roland MeyerPOPL 2025 · 7 citations
- Coinductive Proofs for Temporal HyperlivenessArthur Correnson, Bernd FinkbeinerPOPL 2025 · 5 citations
- Lilo: A Higher-Order, Relational Concurrent Separation Logic for LivenessDongjae Lee, Janggun Lee, Taeyoung Yoon, Minki Cho et al.OOPSLA 2025 · 3 citations
- Verifying Asynchronous Hyperproperties in Reactive SystemsRaven Beutner, Bernd FinkbeinerOOPSLA 2025 · 2 citations
- A Family of Sims with Diverging InterestsNicolas ChappePOPL 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
- Simuliris: a separation logic framework for verifying concurrent program optimizationsLennard Gäher, Michael Sammler, Simon Spies, Ralf Jung et al.POPL 2022 · 33 citations
- Conditional Contextual RefinementYoungju Song, Minki Cho, Dongjae Lee, Chung-Kil Hur et al.POPL 2023 · 29 citations
- The high-level benefits of low-level sandboxingMichael Sammler, Deepak Garg, Derek Dreyer, Tadeusz LitakPOPL 2020 · 26 citations
Related papers
- Fully Verified Instruction SchedulingZiteng Yang, Jun Shirako, Vivek SarkarOOPSLA 2024 · 1 citation
- Compiling with continuations, correctlyZoe Paraskevopoulou, Anvay GroverOOPSLA 2021 · 10 citations
- Formally Verified Native Code Generation in an Effectful JIT: Turning the CompCert Backend into a Formally Verified JIT CompilerAurèle Barrière, Sandrine Blazy, David PichardiePOPL 2023 · 27 citations
- Commutativity for Concurrent Program Termination ProofsDanya Lette, Azadeh FarzanCAV 2023 · 3 citations
- Verified Density Compilation for a Probabilistic Programming LanguageJoseph Tassarotti, Jean-Baptiste TristanPLDI 2023 · 6 citations
