Lune

S&P2024Top-tier venue

DY Fuzzing: Formal Dolev-Yao Models Meet Cryptographic Protocol Fuzz Testing

Max Ammann, Lucca Hirschi, Steve Kremer

Abstract

Critical and widely used cryptographic protocols have repeatedly been found to contain flaws in their design and their implementation. A prominent class of such vulnerabilities is logical attacks, e.g. attacks that exploit flawed protocol logic. Automated formal verification methods, based on the Dolev-Yao (DY) attacker, formally define and excel at finding such flaws, but operate only on abstract specification models. Fully automated verification of existing protocol implementations is today still out of reach. This leaves open whether such implementations are secure. Unfortunately, this blind spot hides numerous attacks, such as recent logical attacks on widely used TLS implementations introduced by implementation bugs.

We answer by proposing a novel and effective technique that we call DY model-guided fuzzing, which precludes logical attacks against protocol implementations. The main idea is to consider as possible test cases the set of abstract DY executions of the DY attacker, and use a novel mutation-based fuzzer to explore this set. The DY fuzzer concretizes each abstract execution to test it on the program under test. This approach enables reasoning at a more structural and security-related level of messages represented as formal terms (e.g. decrypt a message and re-encrypt it with a different key) as opposed to random bit-level modifications that are much less likely to produce relevant logical adversarial behaviors. We implement a full-fledged and modular DY protocol fuzzer. We demonstrate its effectiveness by fuzzing three popular TLS implementations, resulting in the discovery of four novel vulnerabilities.

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.

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

  • From Specs to Apps: Verifying and Monitoring Models of Signal and WhatsApp cites SpecMon: Modular Black-Box Runtime Monitoring of Security Protocols
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers6

  1. GoldenFuzz: Generative Golden Reference Hardware FuzzingLichao Wu, Mohamadreza Rostami, Huimin Li, Nikhilesh Singh et al.NDSS 2026 · 3 citations
  2. SpecMon: Modular Black-Box Runtime Monitoring of Security ProtocolsKevin Morio, Robert KünnemannCCS 2024 · 2 citations
  3. Automated Side-Channel Analysis of Cryptographic Protocol ImplementationsFaezeh Nasrabadi, Robert Künnemann, Hamed NematiCCS 2026 · 2 citations
  4. From Specs to Apps: Verifying and Monitoring Models of Signal and WhatsAppMoustafa Said, Aurora Naska, Kevin Morio, Robert KünnemannCCS 2026
  5. ELFuzz: Efficient Input Generation via LLM-driven Synthesis Over Fuzzer SpaceChuyang Chen, Brendan Dolan-Gavitt, Zhiqiang LinUSENIX Security 2025

Builds on28

  1. Evaluating Fuzz TestingGeorge Klees, Andrew Ruef, Benji Cooper, Shiyi Wei et al.CCS 2018 · 753 citations
  2. Key Reinstallation Attacks: Forcing Nonce Reuse in WPA2Mathy Vanhoef, Frank PiessensCCS 2017 · 437 citations
  3. NAUTILUS: Fishing for Deep Bugs with GrammarsCornelius Aschermann, Tommaso Frassetto, Thorsten Holz, Patrick Jauernig et al.NDSS 2019 · 291 citations
  4. HACL*: A Verified Modern Cryptographic LibraryJean Karim Zinzindohoué, Karthikeyan Bhargavan, Jonathan Protzenko, Benjamin BeurdoucheCCS 2017 · 258 citations
  5. Verified Models and Reference Implementations for the TLS 1.3 Standard CandidateKarthikeyan Bhargavan, Bruno Blanchet, Nadim KobeissiS&P 2017 · 233 citations

Related papers

  1. Linear-time Temporal Logic guided Greybox FuzzingRuijie Meng, Zhen Dong, Jialin Li, Ivan Beschastnikh et al.ICSE 2022 · 29 citations
  2. Bleem: Packet Sequence Oriented Fuzzing for Protocol ImplementationsZhengxiong Luo, Junze Yu, Feilong Zuo, Jianzhong Liu et al.USENIX Security 2023
  3. Systematic Fuzzing and Testing of TLS LibrariesJuraj SomorovskyCCS 2016 · 136 citations
  4. Model-Guided Fuzzing of Distributed SystemsEge Berkay Gulcan, Burcu Kulahcioglu Ozkan, Rupak Majumdar, Srinidhi NagendraOOPSLA 2025 · 3 citations
  5. SemFuzz: A Semantics-Aware Fuzzing Framework for Network Protocol ImplementationsYanbang Sun, Quan Luo, Yuelin Wang, Qian Chen et al.WWW 2026
Dusk over the sea between two cliffs drawn in fine vertical lines