Lune

NDSS2021Top-tier venue

Hunting the Haunter - Efficient Relational Symbolic Execution for Spectre with Haunted RelSE

Lesly-Ann Daniel, Sébastien Bardin, Tamara Rezk

Abstract

Spectre are microarchitectural attacks which were made public in January 2018. They allow an attacker to recover secrets by exploiting speculations. Detection of Spectre is particularly important for cryptographic libraries and defenses at the software level have been proposed. Yet, defenses correctness and Spectre detection pose challenges due on one hand to the explosion of the exploration space induced by speculative paths, and on the other hand to the introduction of new Spectre vulnerabilities at different compilation stages. We propose an optimization, coined Haunted RelSE, that allows scalable detection of Spectre vulnerabilities at binary level. We prove the optimization semantically correct w.r.t. the more naive explicit speculative exploration approach used in state-of-the-art tools. We implement Haunted RelSE in a symbolic analysis tool, and extensively test it on a wellknown litmus testset for Spectre-PHT, and on a new litmus testset for Spectre-STL, which we propose. Our technique finds more violations and scales better than state-of-the-art techniques and tools, analyzing real-world cryptographic libraries and finding new violations. Thanks to our tool, we discover that indexmasking—a standard defense for Spectre-PHT—and well-known gcc options to compile position independent executables introduce Spectre-STL violations. We propose and verify a correction to index-masking to avoid the problem.

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.

27 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

  • Automatic Detection of Speculative Execution Combinations cites Spectre Attacks: Exploiting Speculative Execution
  • Automatic Detection of Speculative Execution Combinations cites Spectector: Principled Detection of Speculative Information Flows
  • Automatic Detection of Speculative Execution Combinations cites ret2spec: Speculative Execution Using Return Stack Buffers
  • Automatic Detection of Speculative Execution Combinations cites Cats vs. Spectre: An Axiomatic Approach to Modeling Speculative Execution Attacks
  • Automatic Detection of Speculative Execution Combinations cites SoK: Practical Foundations for Software Spectre Defenses
  • Spectector: Principled Detection of Speculative Information Flows cites Spectre Attacks: Exploiting Speculative Execution
  • Spectector: Principled Detection of Speculative Information Flows cites ret2spec: Speculative Execution Using Return Stack Buffers
  • Spectector: Principled Detection of Speculative Information Flows cites A Systematic Evaluation of Transient Execution Attacks and Defenses
  • ret2spec: Speculative Execution Using Return Stack Buffers cites Spectre Attacks: Exploiting Speculative Execution
  • A Systematic Evaluation of Transient Execution Attacks and Defenses cites Spectre Attacks: Exploiting Speculative Execution
  • A Systematic Evaluation of Transient Execution Attacks and Defenses cites ret2spec: Speculative Execution Using Return Stack Buffers
  • Cats vs. Spectre: An Axiomatic Approach to Modeling Speculative Execution Attacks cites Spectre Attacks: Exploiting Speculative Execution
  • Cats vs. Spectre: An Axiomatic Approach to Modeling Speculative Execution Attacks cites Spectector: Principled Detection of Speculative Information Flows
  • InSpectre Gadget: Inspecting the Residual Attack Surface of Cross-privilege Spectre v2 cites Spectre Attacks: Exploiting Speculative Execution
  • InSpectre Gadget: Inspecting the Residual Attack Surface of Cross-privilege Spectre v2 cites Spectector: Principled Detection of Speculative Information Flows
  • InSpectre Gadget: Inspecting the Residual Attack Surface of Cross-privilege Spectre v2 cites ret2spec: Speculative Execution Using Return Stack Buffers
  • SoK: Practical Foundations for Software Spectre Defenses cites Spectre Attacks: Exploiting Speculative Execution
  • SoK: Practical Foundations for Software Spectre Defenses cites Spectector: Principled Detection of Speculative Information Flows
  • SoK: Practical Foundations for Software Spectre Defenses cites ret2spec: Speculative Execution Using Return Stack Buffers
  • SoK: Practical Foundations for Software Spectre Defenses cites A Systematic Evaluation of Transient Execution Attacks and Defenses
  • SoK: Practical Foundations for Software Spectre Defenses cites Cats vs. Spectre: An Axiomatic Approach to Modeling Speculative Execution Attacks
  • Axiomatic hardware-software contracts for security cites Spectre Attacks: Exploiting Speculative Execution
  • Axiomatic hardware-software contracts for security cites Spectector: Principled Detection of Speculative Information Flows
  • Axiomatic hardware-software contracts for security cites Cats vs. Spectre: An Axiomatic Approach to Modeling Speculative Execution Attacks
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers27

  1. SoK: Practical Foundations for Software Spectre DefensesSunjay Cauligi, Craig Disselkoen, Daniel Moghimi, Gilles Barthe et al.S&P 2022 · 59 citations
  2. Cats vs. Spectre: An Axiomatic Approach to Modeling Speculative Execution AttacksHernán Ponce de León, Johannes KinderS&P 2022 · 35 citations
  3. InSpectre Gadget: Inspecting the Residual Attack Surface of Cross-privilege Spectre v2Sander Wiebing, Alvise de Faveri Tron, Herbert Bos, Cristiano GiuffridaUSENIX Security 2024 · 32 citations
  4. Axiomatic hardware-software contracts for securityNicholas Mosier, Hanna Lachnitt, Hamed Nemati, Caroline TrippelISCA 2022 · 26 citations
  5. Automatic Detection of Speculative Execution CombinationsXaver Fabian, Marco Guarnieri, Marco PatrignaniCCS 2022 · 19 citations

Builds on12

  1. Spectre Attacks: Exploiting Speculative ExecutionPaul Kocher, Jann Horn, Anders Fogh, Daniel Genkin et al.S&P 2019 · 2,435 citations
  2. SOK: (State of) The Art of War: Offensive Techniques in Binary AnalysisYan Shoshitaishvili, Ruoyu Wang, Christopher Salls, Nick Stephens et al.S&P 2016 · 1,085 citations
  3. A Systematic Evaluation of Transient Execution Attacks and DefensesClaudio Canella, Jo Van Bulck, Michael Schwarz, Moritz Lipp et al.USENIX Security 2019 · 442 citations
  4. ret2spec: Speculative Execution Using Return Stack BuffersGiorgi Maisuradze, Christian RossowCCS 2018 · 282 citations
  5. Spectector: Principled Detection of Speculative Information FlowsMarco Guarnieri, Boris Köpf, José F. Morales, Jan Reineke et al.S&P 2020 · 177 citations

Related papers

  1. An Analysis of Speculative Type Confusion Vulnerabilities in the WildOfek Kirzner, Adam MorrisonUSENIX Security 2021 · 40 citations
  2. SpecTaint: Speculative Taint Analysis for Discovering Spectre GadgetsZhenxiao Qi, Qian Feng, Yueqiang Cheng, Mengjia Yan et al.NDSS 2021
  3. SpecSafe: detecting cache side channels in a speculative worldRobert Brotzman, Danfeng Zhang, Mahmut Taylan Kandemir, Gang TanOOPSLA 2021 · 3 citations
  4. Place Protections at the Right Place: Targeted Hardening for Cryptographic Code against Spectre v1Yiming Zhu, Wenchao Huang, Yan XiongUSENIX Security 2025
  5. SpecCFI: Mitigating Spectre Attacks using CFI Informed SpeculationEsmaeil Mohammadian Koruyeh, Shirin Haji Amin Shirazi, Khaled N. Khasawneh, Chengyu Song et al.S&P 2020 · 74 citations
Dusk over the sea between two cliffs drawn in fine vertical lines