Lune

POPL2022Top-tier venue

Certifying derivation of state machines from coroutines

Mirai Ikebuchi, Andres Erbsen, Adam Chlipala

Abstract

One of the biggest implementation challenges in security-critical network protocols is nested state machines. In practice today, state machines are either implemented manually at a low level, risking bugs easily missed in audits; or are written using higher-level abstractions like threads, depending on runtime systems that may sacrifice performance or compatibility with the ABIs of important platforms (e.g., resource-constrained IoT systems). We present a compiler-based technique allowing the best of both worlds, coding protocols in a natural high-level form, using freer monads to represent nested coroutines , which are then compiled automatically to lower-level code with explicit state. In fact, our compiler is implemented as a tactic in the Coq proof assistant, structuring compilation as search for an equivalence proof for source and target programs. As such, it is straightforwardly (and soundly) extensible with new hints, for instance regarding new data structures that may be used for efficient lookup of coroutines. As a case study, we implemented a core of TLS sufficient for use with popular Web browsers, and our experiments show that the extracted Haskell code achieves reasonable performance.

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • EverCrypt: A Fast, Verified, Cross-Platform Cryptographic Provider cites Verified Correctness and Security of mbedTLS HMAC-DRBG
  • EverCrypt: A Fast, Verified, Cross-Platform Cryptographic Provider cites Simple High-Level Code for Cryptographic Arithmetic - With Proofs, Without Compromises
  • Foundational Integration Verification of a Cryptographic Server cites Verified Correctness and Security of mbedTLS HMAC-DRBG
  • Foundational Integration Verification of a Cryptographic Server cites EverCrypt: A Fast, Verified, Cross-Platform Cryptographic Provider
  • Foundational Integration Verification of a Cryptographic Server cites Simple High-Level Code for Cryptographic Arithmetic - With Proofs, Without Compromises
  • OwlC: Compiling Security Protocols to Verified, Secure, High-Performance Libraries cites EverCrypt: A Fast, Verified, Cross-Platform Cryptographic Provider
  • OwlC: Compiling Security Protocols to Verified, Secure, High-Performance Libraries cites Interaction trees: representing recursive and impure programs in Coq
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. Foundational Integration Verification of a Cryptographic ServerAndres Erbsen, Jade Philipoom, Dustin Jamner, Ashley Lin et al.PLDI 2024 · 8 citations
  2. OwlC: Compiling Security Protocols to Verified, Secure, High-Performance LibrariesPratap Singh, Joshua Gancher, Bryan ParnoUSENIX Security 2025

Builds on5

  1. Simple High-Level Code for Cryptographic Arithmetic - With Proofs, Without CompromisesAndres Erbsen, Jade Philipoom, Jason Gross, Robert Sloan et al.S&P 2019 · 147 citations
  2. Interaction trees: representing recursive and impure programs in CoqLi-yao Xia, Yannick Zakowski, Paul He, Chung-Kil Hur et al.POPL 2020 · 133 citations
  3. EverCrypt: A Fast, Verified, Cross-Platform Cryptographic ProviderJonathan Protzenko, Bryan Parno, Aymeric Fromherz, Chris Hawblitzel et al.S&P 2020 · 114 citations
  4. Verified Correctness and Security of mbedTLS HMAC-DRBGKatherine Q. Ye, Matthew Green, Naphat Sanguansin, Lennart Beringer et al.CCS 2017 · 59 citations
  5. Perceus: garbage free reference counting with reuseAlex Reinking, Ningning Xie, Leonardo de Moura, Daan LeijenPLDI 2021 · 31 citations

Related papers

  1. Noise*: A Library of Verified High-Performance Secure Channel Protocol ImplementationsSon Ho, Jonathan Protzenko, Abhishek Bichhawat, Karthikeyan BhargavanS&P 2022 · 22 citations
  2. CryptOpt: Verified Compilation with Randomized Program Search for Cryptographic PrimitivesJoel Kuepper, Andres Erbsen, Jason Gross, Owen Conoly et al.PLDI 2023 · 12 citations
  3. Formal Security and Functional Verification of Cryptographic Protocol Implementations in RustKarthikeyan Bhargavan, Lasse Letager Hansen, Franziskus Kiefer, Jonas Schneider-Bensch et al.CCS 2025 · 1 citation
  4. 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
  5. Hyperblock Scheduling for Verified High-Level SynthesisYann Herklotz, John WickersonPLDI 2024 · 3 citations
Dusk over the sea between two cliffs drawn in fine vertical lines