本文发表于S&P 2021, 第一作者是来自南京大学的Chengbin Pang博士，这篇工作是他在史蒂文斯理工学院访问期间完成。
本文通过研究九种流行的开源工具来系统化二进制反汇编。作者人工阅读了工具的源代码后，使用3,788 个二进制文件进行了完备的实验评估。本文研究对反汇编策略进行了全面的描述，将它们分为算法和启发式两类。同时，作者测试并报告了单个算法对每个工具结果的影响。作者发现，虽然所有工具都使用原则性算法，但它们仍然严重依赖启发式算法来增加代码覆盖率。根据所使用的启发式方法，不同的覆盖率与正确性会有所取舍，从而导致工具具有不同的优势和劣势。作者设想这些发现将帮助用户选择正确的工具并协助研究人员改进二进制反汇编技术。
二进制程序的反汇编是逆向工程和软件安全性中的一项关键任务，它是无数软件分析工作的核心组成部分。然而，要正确对一个二进制程序进行反汇编是困难的。主要是由于将程序编译为机器代码时发生的信息丢失(例如符号和类型)以及用于实现语言功能的结构的复杂性(例如跳转表、嵌入代码中的数据等)。
二进制反汇编在过去十年中取得了显著的进步，各种开源工具，商业工具可以供研究人员选择，这些工具总体可以分为两类：算法类(产生具有一些正确性保证的结果。它们主要利用来自二进制文件（例如符号）、机器（例如指令集）和/或 ABI（例如调用约定）的知识。)，启发式规则类(通常不提供正确性保证。)
每种工具都采用不同的策略，技术细节并不总是完全记录或公开。且实施的策略随着时间的推移而演变，进一步偏离了文档。以上造成了阻碍这些二进制分析研究人员深入了解其原理。为了帮助研究人员深入了解现有工作的策略方法，必须回答几个问题：1.现有反汇编工具中使用了哪些算法和启发式方法，它们如何交互？2.与算法相比，启发式方法的覆盖率和准确性是多少？有trade off吗？现有的反汇编工具会犯什么错误，根本原因是什么？
基于以上问题，作者对现有的反汇编工作进行了系统性研究，最终做出以下贡献：
1.从算法和启发式的角度，对二进制反汇编工作进行了系统化的研究
2.开发了一个框架，可以自动生成groundtruth，基于这个框架作者构建了一个数据集用来评估各项工具
3.作者对已有的工具进行了完备的实验，以及各项工作的优缺点
4.作者提升了对二进制反汇编策略和工具的理解，为以后的改进提供了方向
文章主要关注四个方面：
1）反汇编：恢复二进制文件汇编指令的过程，一个完美的反汇编工作可以将代码和数据区域分离，能正确识别出哪些是指令。
2）符号化：符号化确定交叉引用，或者精确地确定二进制文件中代码和数据对象的引用值。根据引用的位置和目标的位置，有四种类型：代码到代码 (c2c)、代码到数据 (c2d)、数据到代码 (d2c) 和数据到数据 (d2d)。
3）识别函数入口点
4）重建CFG图
文章主要选取的目标测试程序按如下要求：
1.由主流编译器和链接器生成的
2.二进制文件中可能包含手写的汇编代码
3.没有被混淆
4.二进制文件被strip过
5.只考虑 x86/x64 二进制文件
6.能够在 Linux 或 Windows 操作系统上运行
文章选取的目标工具按如下要求：
1.具有独立的二进制分析功能
2.能够在无用户交互的情况下进行分析
3.是开源工具，能够深入源码研究具体的策略
4.有其他工具没有完全覆盖的独特策略
5.可以运行目标二进制文件来支持定量评估
比如JakStabw无法运行目标二进制，RetDec策略太简单，BinCat需要交互,所以作者都没有选择。
作者认为反汇编粗略可以分为两大类：线性扫描和递归下降
1）线性扫描连续扫描预先选择的代码范围并识别有效指令，一般来说，线性扫描策略可以通过它如何选择扫描范围以及如何处理扫描过程中的错误来描述。作者根据这两个方面来总结算法。
1.所有工具都遵循基本的方法来选择要扫描的代码区域：它们处理由符号指定的代码范围.symtab和.dynzyme部分 (①)，然后是代码部分中的剩余空白。在一般意义上，这些范围全面地封装了合法指令。对于处理扫描过程中的错误各工具有自己的方法。
2.objdump会将无效的操作码跳过一个字节，然后继续扫描。PSI在碰到操作码错误时，会后向追踪到上一个控制流转移指令，然后用nop指令填充控制转移指令后的部分，然后重新运行线性扫描。
线性扫描积极扫描所有可能的代码，因此，最大限度地恢复指令。但是，由于代码中的数据，它可能会遇到错误。为了解决错误，现有的工具依靠启发式方法进行修正，这种方法不够全面，而且效用有限。
2）递归下降会从给定的代码地址开始，按照控制流进行反汇编。这个策略则需要考虑三个部分：如何选择代码地址，如何解析控制流，如何处理递归反汇编留下的代码空白。
严格的递归下降确保了正确性，但通常会导致覆盖不足。为了扩大代码覆盖范围，现有的工具包含了许多破坏正确性保证的积极的启发式方法。
1.对于数据单元的提取
1）如8的策略，大部分工具首先识别作为潜在指针的数值。他们搜索所有指令以识别常量操作数并扫描非代码区域以查找数据单元。
2）如9的策略，所有工具都假定数据单元的大小与机器大小相同，32 位二进制文件中的 4 个字节和 64 位二进制文件中的 8 个字节
3）angr,Ghidra对于交叉引用使用到的地址没有对齐要求，直接提取
2.数据单元类型推断
1）在操作数提取中，ANGR 和 GHIDRA 在可能的情况下推断数据单元的类型。ANGR 识别数据单元的内存负载。如果加载的值流向浮点指令，ANGR 将数据单元标记为浮点。GHIDRA 使用更激进的策略：数据必须满足3个条件才会被视为指针，在下一步交叉引用建立会说
3. 交叉引用建立
1)对于每个常数操作数，ANGR，UROBOROS 和 MCSEMA 寻求将其作为代码指针来符号化，检查操作数是否指向合法指令。
2) GHIDRA 还有两个额外的规则:操作数限制范围，如不能是[0-4095]中的值，策略12 对代码的交叉引用必须是函数入口。GHIDRA不合理的地方在于，比如异常处理的指针，是不会指向函数入口的。
3）策略13在检查过程中，ANGR 将数据区域的边界扩大了1,024个字节，GHIDRA 采用了类似的思想，因为许多指针用偏移量取消了引用。
4.地址表
除了常量操作数，这些工具还通过定位地址表的方式来解析指针，通常，确定地址表取决于表大小的选择和将数据单元识别为指针的规则。
1）表大小的选择：策略14中 GHIDRA 认为2是地址表的最小尺寸，其他认为1是地址表的最小尺寸。
2）将数据单元识别为指针的规则：
a. ANGR 排除了作为浮点数的表条目
b. 15 MCSEMA 排除可能与字符串重叠的表条目。
c. GHIDRA 不包括指向已恢复函数中间的表条目。
d. 给定一个非分解代码条目，GHIDRA 使用上述方法扩展递归下降。
5. 最后ANGR 在暴力搜索数据区域时使用一种特殊的策略。给定一个位置，ANGR 依次检查内部数据是指针、 ASCII/Unicode 字符串还是整数序列。如果有任何类型匹配，ANGR 将跳过相关字节，然后继续搜索。
III-C 函数入口识别
大多数工具会使用单独的策略来识别main函数.
1.main函数
1)有工具会分析 _ start 函数，并按照调用约定推断 _ start 传递给 _ _ libc _ start _ Main 的第一个参数。
2)还有工具会在调用 _ _ libc _ start _ main 的附近搜索各种架构的特征，以获取 main的地址。
2.一般函数
为了识别非主要函数的入口，这些工具采用了一种混合方法，包括三个部分:
1）策略6中会寻找.symtab和.dynsym部分中的剩余符号，以确定已知的良好函数。策略7考虑.eh_frame部分来识别有展开信息的函数。
2）策略8都将直接调用的目标视为函数入口。策略9另外解析某些间接调用以确定更多的函数入口。dynINST、 GHIDRA、 ANGR 和 RADARE2将tail call的目标作为函数入口
3）策略18 中DYNINST, GHIDRA, ANGR, BAP, RADARE2都使用基于模式的方法来进一步恢复函数。GHIDRA、ANGR 和 RADARE2 根据常见的序言（或结尾）查找函数条目；DYNINST（默认）和 BAP 使用预先训练的决策树模型查找函数条目策略19 ANGR 采用了一种激进的方法: 在对递归下降留下的代码间隙进行线性扫描时，它将每个已识别代码段的开始处理为一个新入口。
函数入口的识别大多采用混合方法、混合算法和启发式算法。
III-D CFG 重建
CFG 重建包括许多任务。作者主要关注具有挑战性的问题: 解析间接跳转/调用、检测尾部调用和查找不返回的函数。不讨论直接跳转/调用，因为它们在反汇编后很容易建立。
一.间接跳转
DYNINST, GHIDRA, ANGR三种工具都会采用值集分析来分析间接跳转目标
1. RADARE2只使用pattern处理跳转表。如果索引的上限超过512，RADARE2将丢弃跳转表()。
2. GHIDRA 将一个间接跳转看作一个跳转表。与 RADARE2类似，GHIDRA 丢弃索引绑定在1024()以上的跳转表。
3. 策略10 ANGR在给定间接跳转时将操作数作为源，并向后运行切片,在切片区域中用VSA识别可能的目标。策略22 ANGR 的公共版本将切片限制在基本块的最多三个级别，用效用换取效率。ANGR 还采用策略21的启发式方法，其阈值非常大: 100,000。
二.间接调用
1. GHIDRA 基于常量传播找到间接调用的目标。
2. ANGR 也使用常量传播来处理间接调用，但只考虑当前的基本块。
3. Tail call:
1）RADARE2使用一种简单的启发式方法来确定尾部调用: 跳转与其目标之间超过某个阈值的距离。
2）如果跳转与其目标之间的代码跨越多个函数，GHIDRA 将跳转确定为Tail call。
3）GHIDRA 进一步将条件跳转排除在考虑范围之外。
4）DYNINST 采取了复杂的策略。如果目标是已知函数的开始，则将跳转视为尾部调用。
5) ANGR 采用与 DYNINST 类似的策略。它首先识别跳转，其目标是已知函数的开始。如果不满足，ANGR则 需要四个条件来检测尾部调用:
a. 25 跳转是无条件的;
b. 26 跳转处的堆栈根据堆栈高度变化;
c. 27 目标不能是函数体的中间;
d. 28 tail call的目标地址不能被任何条件跳转到达
三.非返回函数
首先，它们收集一组已知不返回的库函数或系统调用。其次，从这组初始函数中，工具可以进一步发现其他函数。
ANGR、 RADARE2和 DYNINST 使用相同的思想: 它们扫描每个函数，如果没有发现 ret 指令，它们就认为该函数是不返回的。
函数中的所有路径都以对非返回函数的调用结束 ，则 BAP 认为该函数是非返回函数。
CFG重建总的来说如下:
1.现有工具采用各种启发式方法来解决间接跳转。这些启发式方法主要是为了准确性而衍生的，引入的错误较少，但覆盖范围有限。
2.现有工具采用了不同的策略来检测尾调用。这些策略严重依赖于函数入口检测，因此会受函数识别的准确性影响。
3.现有工具使用了很多策略来检测Non-returning Function以确保更高的正确性
IV 实验
反汇编实验结果
L 和 W 是 Linux 和 Windows 的缩写。Pre 和 Rec 表示精确度和召回率。Ave/Min 显示所有二进制文件的平均/最小结果。特定于每个优化级别的最佳/最差结果分别标记为蓝色/红色
线性扫描工具如 OBJDUMP 和 ANGR，具有很高的覆盖率。递归工具的覆盖率较低，有些只能恢复不到 80% 的指令（BAP 和 RADARE2）。
另一方面在精度方面，有相反的结果。无论编译器、架构和优化级别如何，递归工具都具有很高的精度（超过 99.5%）。线性工具不太精确。在最坏的情况下，OBJDUMP 的精度下降到 85% 左右。这种差异主要是因为递归工具大多遵循控制流，确保正确性。但是，线性工具会扫描每个字节，并且当数据出现在代码中时经常会出错
启发式的使用：启发式主要是为了增强线性扫描的正确性与递归下降的覆盖率
FP方面：对于线性工具（例如., OBJDUMP），所有误报都是由错误识别填充字节或代码中的数据作为代码引起的。对于递归工具，最常见的错误原因包括1.将非法位置视为函数入口；2.缺少非返回函数并假设对它们的调用失败；3.跳转表解析不正确。
FN方面，线性工具都是由于Fp的副作用，递归则是未覆盖到。
符号化实验结果
一般而言，开源工具的覆盖率（平均 98.35%）远高于商业工具（平均 88.63%）。在最坏的情况下，差异甚至更大。这是因为开源工具会暴力破解所有常量操作数和数据单元，而商业工具采用更保守的策略。
令人惊讶的是，开源工具的精度也很高（平均为 99.92%）。根据我们的观察，高精度是因为（1）基于启发式的检查通常具有限制性，（2）大多数基准程序的数据较少，在具有更多数据的程序上，工具更容易出错
大部分误报都是由于数值和指针之间的冲突。ANGR 和 GHIDRA 则会在检查外部参照目标的合法性时会扩大数据区域的边界导致误报。
漏报方面：ANGR 和 MCSEMA 的大多数误报是因为它们排除了与推断字符串重叠的指针。MCSEMA 还遗漏了 23.64% 的指向数据区域之外位置的外部引用。GHIDRA，因为它假设地址表的最小大小和代码指针总是指向函数条目而产生漏报。
函数入口实验结果
函数入口识别是很大的挑战。即使使用了启发式的方法也无法得到很好的效果
误报的通用原因：
1.基于签名的检测错误地匹配函数入口
2.不正确的尾调用
3.不正确的反汇编
工具特殊的FP:
ANGR 产生了 78.41% 的误报，因为它激进策略中的将线性扫描发现的连续代码块第一条指令视为函数入口；GHIDRA 产生了 99.94% 的误报，因为异常信息还带有指向函数中间的指针；RADARE2，积极地基于外部引用推断代码指针，带来了 93%的误报
漏报通用原因相似：
1.工具可能会错过跳转表的目标，并且无法识别目标代码或其后继代码调用的函数，跳转表对 ANGR 和 DYNINST 的影响较小，因为 ANGR 使用线性扫描来补偿跳转表，而 DYNINST 对跳转表的覆盖率很高。
2.工具无法识别很多尾调用，因此错过了目标指示的函数
3.遗漏的非返回函数会阻止检测到许多函数条目
4.错误识别的函数可能与真实函数重叠，使真实函数无法识别
5.有的函数不能通过递归和模式到达
CFG重建实验结果
在这一部分中，作者测量了 5 个目标：(1) 基本块之间的过程内边的构建；(2) 直接调用的调用图；(3) 间接跳转和间接调用；(4) 尾调用；(5) 不返回函数。
1.这些工具可以高精度地恢复大部分边信息
2.工具具有不同的处理跳转表的能力。平均而言，GHIDRA 和 DYNINST 可以解析超过 93% 的跳台，准确率约为 90%。RADARE2 和 ANGR 具有相似的覆盖率（大约 75%），而 ANGR 具有更高的准确度（96.27%对90%）。与开源工具相比，商业工具具有更高的覆盖率（96.5%对84.8%）和准确性（99%对92.96%）。
3.工具可以有限的支持间接调用
4.现有工具在检测尾调用方面并不完美。覆盖率从 71.7%（DYNINST）到 91.28%（BINARY NINJA）；精度从 67.39% (DYNINST) 到 90.21% (GHIDRA) 不等
工具可以以非常高的精度检测不返回功能（对于许多工具来说几乎 100%）。但是，它们的覆盖范围有限，尤其是在 Windows 二进制文件上。
V 总结
二进制中复杂的结构很常见，启发式方法对于处理复杂结构是必不可少的。启发式本质上引入了对覆盖率-准确性的权衡。启发式显著的增加了覆盖率，但同时会导致新的错误。工具之间相辅相成，现有工具使用的启发式和算法虽然有所重叠但也有许多差异，这体现了工具的不同优势，表明工具的选择应该是针对特定需求的。社区对现有工具的评估不够充分导致研究人员对工具的局限性不够了解，未来的改进需要更广泛、更深入的评估。
VI QA
Q1：文章回答的核心问题或者说目标是什么，作者是如何回答的？
A1：核心目标是为了缩小该领域内研究人员研究工具的信息鸿沟，作者认为需要回答以下三个问题：
1、现有工具中使用的算法和启发式方法都有哪些，它们是如何相互作用的？
2、与算法方法相比，启发式方法的覆盖率和准确性如何?
3、现有的反汇编工具会产生哪些错误，其根本原因是什么？
作者选取了九种流行的开源工具，提出了一种系统化的二进制反汇编研究方案。作者对这些工具进行了定性和定量研究，不仅是每个工具的整体上入手，也深入研究了这些工具各自的算法和启发式方法。
具体来讲，作者对这些工具的定性研究是基于手动检查源代码来回答问题1，避免在文档和出版物中的歧义和过时的信息。
定量研究则是以作者自行构建的二进制文件的语料库作为benchmark，实际测试和评估分析这些工具的整体效果和所使用策略、方法的对照试验效果来回答问题Q2-Q3。
作者构建了一个基于LLVM、GCC、Gold Linker和Visual Studio的分析框架，在构建语料库的同时自动收集ground-truth。通过单独测量不同反编译阶段来评估工具，以量化不同策略的效果。
Q2：文章的Contribution是什么？
A2：提出了一种对二进制反编译算法和启发式规则的系统化研究。这是第一个可以回答Q1-Q3问题的研究，并且是首次对introduction中提出的三个问题进行了解答的文章。
开发实现了一个基于编译器的框架，用于自动端到端收集二进制反编译实验所需的ground-truth，并以此构建了一个benchmark，用来评估各种工具、算法和启发式规则的效果。
作者通过他们的专业知识，对开源反编译工具做了全面的评价和对算法、启发式规则效果的深入分析。
增强了研究人员对于领域研究内开源反编译工具和策略的理解，能够促进领域研究，推动研究和工具的发展。
Q3：有三个工具被排除了原因是什么
A3：JAKSTAB因为工具对二进制文件的解析问题，无法执行本文benchmark中的二进制文件，从而无法进行定量评估。
RetDec没有提出独特的策略，它的策略被其它工具覆盖了。
BinCat的分析需要用户交互才能完成。
Q4：文章4个主要的发现是什么？
A4：1.二进制中复杂的结构很常见，启发式方法对于处理复杂结构是必不可少的。2.启发式本质上引入了对覆盖率-准确性的权衡。启发式显著的增加了覆盖率，但同时会导致新的错误。3.工具之间相辅相成，现有工具使用的启发式和算法虽然有所重叠但也有许多差异，这体现了工具的不同优势，表明工具的选择应该是针对特定需求的。4.社区对现有工具的评估不够充分导致我们对工具的局限性不够了解，未来的改进需要更广泛、更深入的评估
Q5：这些反汇编策略可以分哪两类？递归下降与线性扫描这两个策略执行反编译各有什么优缺点？
A5：线性扫描积极地扫描所有可能的代码，从而最大限度地恢复指令，其覆盖率很高但是由于代码中存在数据，可能会遇到错误，正确率不能保证，有很多FN，FP。为了解决错误，现有工具依赖启发式进行更正，但不够全面，实用性有限。严格的递归下降确保了正确性，但覆盖范围不足。为了扩大代码覆盖范围，现有工具结合了许多破坏正确性的激进启发式方法。
Q6：反汇编一个二进制代码的挑战在于哪里
A6：a. 程序编译成二进制代码后会造成符号，类型等信息的缺失 b. 使用了高级语言的语法特性造成的复杂结构使得反汇编难度增加
文案：XZH
戳“阅读原文”即可查看论文原文哦~
复旦白泽战队
一个有情怀的安全团队
还没有关注复旦白泽战队？
公众号、知乎、微博搜索：复旦白泽战队也能找到我们哦~
原文始发于微信公众号（复旦白泽战队）：白泽带你读论文丨SoK: All You Ever Wanted to Know About x86/x64 ...
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论