SoK: All You Ever Wanted to Know About x86/x64 Binary Disassembly But Were Afraid to Ask
It addresses the lack of systematization in binary disassembly, helping users select tools and aiding researchers in improving the field, though it is incremental as it organizes existing knowledge rather than introducing new methods.
The paper systematizes binary disassembly by studying nine open-source tools through manual code examination and experimental evaluation on 3,788 binaries, finding that tools use principled algorithms but rely on heuristics for coverage, leading to varying trade-offs between coverage and correctness.
Disassembly of binary code is hard, but necessary for improving the security of binary software. Over the past few decades, research in binary disassembly has produced many tools and frameworks, which have been made available to researchers and security professionals. These tools employ a variety of strategies that grant them different characteristics. The lack of systematization, however, impedes new research in the area and makes selecting the right tool hard, as we do not understand the strengths and weaknesses of existing tools. In this paper, we systematize binary disassembly through the study of nine popular, open-source tools. We couple the manual examination of their code bases with the most comprehensive experimental evaluation (thus far) using 3,788 binaries. Our study yields a comprehensive description and organization of strategies for disassembly, classifying them as either algorithm or else heuristic. Meanwhile, we measure and report the impact of individual algorithms on the results of each tool. We find that while principled algorithms are used by all tools, they still heavily rely on heuristics to increase code coverage. Depending on the heuristics used, different coverage-vs-correctness trade-offs come in play, leading to tools with different strengths and weaknesses. We envision that these findings will help users pick the right tool and assist researchers in improving binary disassembly.