一句话：提出无需预先反汇编的线性时间后向静态二进制分析，基于超集控制流图并避免非法路径污染。
二进制分析通常需先反汇编并识别函数，但 x86 等变长指令集上二者互为依赖：精确反汇编需要静态分析，静态分析又需要反汇编。本文提出无需先确定反汇编的静态分析：把二进制每个偏移都视为指令，穷举反汇编并构造超集控制流图（CFG）。该 CFG 混合合法与意外指令，非法路径会污染合法结果。关键洞见是采用后向分析，可在不知道哪些是指令的情况下保证目标指令处结果准确。分析总时间为 O(n)，可为 n 字节二进制所有 n 个偏移给出结果，比需反复分析的已有技术快数个数量级。
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 O(n) total time, it yields analysis results for every one of the n offsets in an n-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.
@article{NguyenPJS26,
title = {Analyzing Bytes: Pre-Disassembly Static Binary Analysis},
author = {Huan Nguyen and Soumyakant Priyadarshan and Chencheng Jiang and R. Sekar},
journal = {Proceedings of the ACM on Programming Languages},
volume = {10},
number = {PLDI},
year = {2026},
doi = {10.1145/3808292}
}