Lune

PLDI2026Top-tier venue

Analyzing Bytes: Pre-Disassembly Static Binary Analysis

Huan Nguyen, Soumyakant Priyadarshan, Chencheng Jiang, R. Sekar

Abstract

Binary code analysis plays a central role in numerous applications in software security, performance optimization, reverse engineering, and so on. Existing techniques need to first disassemble binaries into functions in assembly code before an analysis can be performed. However, disassembly and function identification have proven to be major challenges for complex variable-length instruction sets such as the x86. A recent trend has been to use static analysis to improve the accuracy of these tasks. This raises a chicken-and-egg problem: a disassembly is needed for static analysis, but a static analysis is needed for accurate disassembly! We overcome this problem by developing a novel static analysis approach that can operate before committing to a disassembly. Our analysis operates on the output of exhaustive disassembly that considers each possible offset in a binary as an instruction, and constructs what is known as a super-set control-flow graph (CFG). The central technical challenge in analyzing this CFG is that it mixes legitimate instructions with unintended ones, causing analysis results from invalid code paths to pollute legitimate ones. To overcome this challenge, we begin with a key new insight that if we focus on backward analyses, we can ensure accuracy of analysis results at intended instructions even though we have no idea where these intended instructions are! Moreover, our analysis operates in time that is linear in the size of the binary. Specifically, in 𝑂 (𝑛) total time, it yields analysis results for every one of the 𝑛 offsets in an 𝑛-byte binary. For this task, it is orders of magnitude faster than previous techniques, as the previous techniques typically need to repeat the analysis many times.

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.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • RetroWrite: Statically Instrumenting COTS Binaries for Fuzzing and Sanitization cites Ramblr: Making Reassembly Great Again
  • RetroWrite: Statically Instrumenting COTS Binaries for Fuzzing and Sanitization cites SOK: (State of) The Art of War: Offensive Techniques in Binary Analysis
  • RAZOR: A Framework for Post-deployment Software Debloating cites Ramblr: Making Reassembly Great Again
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on23

  1. 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
  2. A Tough Call: Mitigating Advanced Code-Reuse Attacks at the Binary LevelVictor van der Veen, Enes Göktas, Moritz Contag, Andre Pawlowski et al.S&P 2016 · 227 citations
  3. RetroWrite: Statically Instrumenting COTS Binaries for Fuzzing and SanitizationSushant Dinesh, Nathan Burow, Dongyan Xu, Mathias PayerS&P 2020 · 187 citations
  4. Ramblr: Making Reassembly Great AgainRuoyu Wang, Yan Shoshitaishvili, Antonio Bianchi, Aravind Machiry et al.NDSS 2017 · 155 citations
  5. RAZOR: A Framework for Post-deployment Software DebloatingChenxiong Qian, Hong Hu, Mansour Alharthi, Simon Pak Ho Chung et al.USENIX Security 2019 · 132 citations

Related papers

  1. Parallel binary code analysisXiaozhu Meng, Jonathon M. Anderson, John M. Mellor-Crummey, Mark W. Krentel et al.PPoPP 2021 · 9 citations
  2. DeepDi: Learning a Relational Graph Convolutional Network Model on Instructions for Fast and Accurate DisassemblySheng Yu, Yu Qu, Xunchao Hu, Heng YinUSENIX Security 2022
  3. Disa: Accurate Learning-based Static Disassembly with AttentionsPeicheng Wang, Monika Santra, Mingyu Liu, Cong Sun et al.CCS 2025
  4. Accurate Disassembly of Complex Binaries Without Use of Compiler MetadataSoumyakant Priyadarshan, Huan Nguyen, R. SekarASPLOS 2023 · 7 citations
  5. Semantics-Guided Control-Flow Reconstruction for Firmware Binaries via Static AnalysisFengjuan Gao, Qingjie Zhu, Yi Zhang, Yu Wang et al.FSE 2026
Dusk over the sea between two cliffs drawn in fine vertical lines