迈向透明可变的二进制反汇编器

在过去的一个冬季，我有幸作为研究生实习生加入Trail of Bits，在Peter Goodman和Artem Dinaburg的指导下工作。实习期间，我开发了Dr. Disassembler——一个基于Datalog的透明可变二进制反汇编框架。尽管该项目仍在进行中，但本篇博客文章将介绍Dr. Disassembler设计背后的高层愿景，并讨论我们当前原型中的关键实现决策。

引言

二进制反汇编异常困难。许多反汇编任务（例如代码/数据区分和函数边界检测）是不可判定的，需要精心设计的启发式方法和算法来覆盖广泛的现实二进制语义。理想的反汇编器具备两个关键特性：（1）透明性，即其底层逻辑可访问和解释；（2）可变性，即允许临时交互和细化。遗憾的是，尽管如今有大量反汇编工具可用，但没有一个同时具备透明性和可变性。

大多数现成的反汇编器（如objdump、Dyninst、McSema和Angr）执行“运行即完成”的反汇编，尽管它们的底层启发式方法和算法确实是开源的，但即使是最轻微的更改（例如切换启发式方法）也需要完全重新构建工具并重新生成反汇编。相反，流行的商业反汇编器如IDA Pro和Binary Ninja提供了丰富的用户编写插件接口，但这些工具几乎完全是专有的，无法完全审查其核心启发式方法和算法的不足之处。因此，逆向工程师不得不在两类反汇编器之间做出选择：充满模糊性的或零灵活性的。

在本博客文章中，我介绍了我们对于透明可变二进制反汇编平台的愿景。我们的方法受到最近的反汇编工具如ddisasm和d3re的启发，这些工具使用Soufflé Datalog引擎。Dr. Disassembler使用Trail of Bits内部开发的增量差分Datalog引擎Dr. Lojekyll来指定反汇编过程。下面，我将描述Dr. Disassembler的关系视图如何迈向透明可变的反汇编——简化新启发式方法、算法和追溯更新的集成——而无需为每个增量更新执行从头开始的反汇编。

背景：反汇编、Datalog和Dr. Lojekyll

反汇编是将二进制可执行文件从机器代码翻译成人类可解释的程序汇编语言表示的过程。在软件安全中，反汇编构成了许多关键任务（如二进制分析、静态重写和逆向工程）的支柱。在Trail of Bits，反汇编是我们可执行文件到LLVM提升工作（如Remill和McSema）的关键第一步。

在高层次上，反汇编器首先解析二进制的逻辑部分，以精确定位包含可执行代码的部分。然后，指令解码将机器代码转换为更高级的指令语义。此过程使用两种策略之一：线性扫描或递归下降。

线性扫描反汇编器（如objdump）从第一个字节索引开始，对每个可能的字节执行指令解码。然而，在像x86这样的变长指令集架构上，天真地将所有字节视为指令的线性扫描反汇编器可能会对非指令字节（例如内联跳转表）执行指令解码。为了克服这个问题，许多现代反汇编器通过恢复元数据（例如调试信息）或应用数据驱动的启发式方法（例如函数入口模式）来改进其分析。

另一方面，递归下降反汇编器（如IDA Pro）遵循观察到的控制流，仅在恢复的分支目标地址上选择性地重新启动线性扫描。虽然恢复跳转表的目标地址通常是可靠的，但恢复间接调用的目标是一个更具挑战性的问题，其中常见情况的可靠性尚未出现。

Datalog是一类称为逻辑编程的编程语言中较受欢迎的成员之一。与围绕程序控制流和状态构建的命令式编程语言（如Python、Java、C和C++）相比，逻辑编程（如Prolog和Datalog）仅围绕逻辑语句构建。在我们二进制反汇编的使用案例中，逻辑语句可用于捕获二进制中对应于合理函数入口点的地址：（1）直接调用指令的目标，（2）常见函数序言，或（3）符号表中包含的任何函数地址。此使用案例在Dr. Lojekyll语法中如下所示：

清单1：此查询检索所有合理函数入口点的集合。这里，“free”表示查询必须找到所有匹配后续子句的候选者。在有界子句（例如给定某个固定地址）中，使用标签“bound”代替（参见清单5）。

从逻辑编程的角度来看，上述代码片段解释如下：如果存在对FuncEA的直接调用、从FuncEA开始的已知函数入口指令序列或FuncEA处的函数符号，则地址FuncEA处存在一个合理的函数。

在更高层次上，逻辑和函数编程是称为声明式编程的更广泛范式的一部分。与命令式语言（如Python、Java、C和C++）不同，声明式语言仅规定输出结果应是什么样子。例如，在前一个检索函数入口点的例子中，我们的主要关注点是最终结果——函数入口点的集合——而不是到达那里所需的逐步计算。虽然逻辑和声明式编程的内容远不止这里提供的简化解释，但逻辑编程的关键优势在于其将数据表示为语句的简洁性。

这就是Datalog的闪光点。假设在填充我们的“事实”数据库（部分、函数和指令）之后，我们想要进行一些调整。例如，假设我们正在分析一个位置无关的“hello world”二进制文件，其函数

的反汇编如下：

清单2：重定位调用目标的示例

我们还知道存在以下重定位条目：

清单3：清单2示例的重定位条目信息

在运行时，动态链接器将更新0x526处调用的操作数以指向printf@PLT。当调用发生时，printf@PLT然后转移到printf的全局偏移表（GOT）条目，执行继续到外部printf。

如果您熟悉IDA Pro或Binary Ninja，您会认识到这两种工具都会调整重定位调用以指向外部符号本身。在二进制分析的上下文中，这很有用，因为它“修复”了否则不透明的调用，其目标仅通过动态链接揭示。在Datalog中，我们可以简单地用几行代码来适应这一点：

清单4：此导出消息重写调用以跳过其中间过程链接表（PLT）条目。这里，“#export”表示该消息将更改Datalog数据库中的某些事实。

瞧！我们对间接调用的表示不再需要通过PLT进行中间重定向。作为奖励，我们可以维护一个关系表来将每种类型的调用映射到其目标。考虑到这个例子，我们设想了许多可能性，其中复杂的二进制语义可以通过关系表（例如指向分析、分支目标分析等）建模，以使二进制分析更加简化和人类可解释。

Dr. Lojekyll是Trail of Bits的新Datalog编译器和执行引擎，也是Dr. Disassembler构建的基础。它采用发布/订阅模型，其中Dr. Lojekyll编译的程序“订阅”消息（例如地址X处存在指令）。当接收到消息时，程序可能会引入新消息（例如指令A和B之间存在直落分支）或删除先前的消息。编译的程序还可以向外部方（例如独立服务器）发布消息，然后这些外部方可以从Datalog端“查询”数据关系。

Dr. Lojekyll的发布/订阅模型非常适合需要“撤销”类功能的任务。在二进制反汇编中，这为人在环二进制分析和更改开辟了许多可能性（想象一下Compiler Explorer，但用于二进制文件）。在撰写本文时，Dr. Lojekyll支持将Datalog编译为Python程序，并正在逐步支持C++。

介绍Dr. Disassembler

传统的“运行即完成”反汇编器即时执行其分析，将它们限制在从一开始获得的任何结果——即使是错误的结果。相反，Datalog使我们能够将所有分析移到反汇编后，从而简化即插即用细化和追溯更新的集成。凭借其无痛语法，Datalog轻松代表了用户编写反汇编插件和扩展的最强大和表达力最强的平台之一。我们将透明可变反汇编的愿景实现为一个原型工具Dr. Disassembler。虽然Dr. Disassembler理论上可以使用任何Datalog引擎（例如DDLog），但我们目前使用Trail of Bits自己的Dr. Lojekyll。本篇博客文章中讨论的Dr. Disassembler实现使用Dr. Lojekyll的Python API。然而，在撰写本文时，由于Python的许多性能限制，我们已经开始开发基于C++的实现。在这里，我介绍我们初始（及即将推出）的Dr. Disassembler实现的高层设计。

图1：Dr. Disassembler的高层架构

反汇编过程

Dr. Disassembler的反汇编工作流包括三个组件：（1）解析，（2）解码，和（3）后处理。在解析中，我们扫描二进制的部分以精确定位包含指令的部分，以及任何可恢复的元数据（例如入口点、符号和导入/导出/本地函数）。对于每个识别的代码部分，我们开始将其字节解码为指令。我们的指令解码过程将每个指令映射到两个关键字段：其类型（例如调用、跳转、返回和其他所有内容）和其传出边。

恢复控制流

使用Datalog的一个优势是能够将复杂的程序语义表达为一系列简单、递归的关系。然而，在处理控制流时，纯递归方法通常会破坏某些分析，如函数边界检测：递归分析将跟随控制流到每个指令的目标，并从那里恢复分析。但是，与调用不同，跳转不是“返回”指令；因此对于过程间跳转，函数将不会重新进入，从而导致反汇编器错过包含跳转指令的函数中的剩余指令。

为了统一递归和线性下降反汇编方法，我们开发了非控制流后继指令的概念：对于任何无条件转移跳转或返回指令，我们记录从该指令到下一个顺序指令的人工直落边。尽管此边对实际程序没有影响，但它有效地编码了逻辑“下一个”指令，从而统一了我们的线性和递归分析。这些非控制流后继边是我们递归分析（如指令分组和函数边界检测）的关键。

后处理

在解析和解码的每个步骤中，我们将找到的任何有趣对象发布到我们的Dr. Lojekyll数据库。这些核心对象——符号、部分、函数、指令和转移——构成了我们启发式和递归分析的基础模块。Dr. Disassembler背后的基本方法是“吞噬”尽可能多的反汇编信息，无论正确与否，然后在Datalog端细化所有内容。因为我们认为每条信息都可能是正确的，我们可以在观察到任何新信息时追溯更新我们的反汇编；与传统的运行即完成工具不同，这不需要从头开始重新反汇编。

示例导出和查询

Dr. Disassembler通过专注于反汇编工件本身而不是获取它们所需的无数步骤来简化二进制分析。为了展示Dr. Disassembler的许多功能，本节重点介绍了由Dr. Disassembler的两个基本构造——“导出”（更改/删除事实的消息）和“查询”（检索关于事实的信息）——促进的严格二进制分析任务的几个实现示例。

查询：将指令分组到函数中

给定任意函数地址FuncEA，此查询返回该函数中包含的所有指令的地址。两个消息形成此查询：（1）function(u64 StartEA)和（2）instruction(u64 InsnEA, type Type, bytes Bytes)。

清单5：一个示例Dr. Disassembler查询，返回函数中包含的指令的地址

导出：主导无效指令的指令

此导出返回所有控制流导致无效指令（即指令解码失败）的指令。此启发式方法对于Dr. Disassembler过滤掉在解码每个可能的字节序列时不可避免地发生的许多“垃圾”指令序列至关重要。

如前面的例子，我们围绕两个核心消息构建此关系：（1）instruction和（2）raw_transfer(u64 StartEA, u64 DestEA)，后者包含从二进制恢复的未更改控制流（即尚未进行如清单4中的更改）。

清单6：一个示例Dr. Disassembler导出，用所有控制流导致无效指令的指令更新数据库

导出：函数间填充

此导出返回所有作为函数间“填充”的指令地址（例如不属于任何函数的NOP）。这里，我们使用以下消息：（1）function，（2）section，（3）raw_transfer，和（4）basic_block(u64 BlockEA, u64 InsnEA)。识别函数间填充是细化我们函数-指令分组的关键步骤。

清单7：一个示例Dr. Disassembler导出，用所有作为函数间“填充”的指令地址更新数据库

未来工作和扩展

我们的直接计划是将Dr. Disassembler扩展到一个完整的C++实现。除了提高工具的性能外，我们预计此过渡将为二进制分析研究开辟许多新途径：

简化的二进制分析平台：当代二进制分析平台具有丰富的开发自定义分析插件接口，但其API的纯粹复杂性经常使用户因陡峭的学习曲线而瓶颈。作为下一步，我们希望将Dr. Disassembler发展成一个成熟的二进制分析平台，具备促进用户插件轻松创建和自定义所需的所有功能。
用于二进制分析和转换的GUI界面：通过使用Dr. Disassembler的可变反汇编表示，我们可以开发新界面，实现二进制可执行文件的实时分析和编辑（例如帮助开发人员可视化切换不同启发式方法如何影响分析结果）。我们这里的最终目标是类似于Compiler Explorer的东西……但用于二进制文件！
暴露分析盲点：我们的Dr. Disassembler原型设计为使用多个二进制解析器和指令解码器的输出。展望未来，我们希望使用Dr. Disassembler作为一个平台，开发自动化技术来识别这些竞争工具在何处彼此一致和不一致（例如在代码-数据区分、分支目标分析等方面）并精确定位它们的弱点。

如果任何这些想法引起您的兴趣，请随时与Trail of Bits的我（Stefan Nagy）或Peter Goodman联系。

我们将在https://github.com/lifting-bits/dds发布我们的Dr. Disassembler原型Python实现，并提供此帖子的PDF版本。祝反汇编愉快！

如果您喜欢这篇文章，请分享： Twitter LinkedIn GitHub Mastodon Hacker News