用差分模糊测试摧毁x86_64指令解码器

TL;DR: x86_64解码很难，其可用实现的数量和多样性使其特别适合差分模糊测试。我们开源了mishegos，这是一个用于指令解码器的差分模糊测试器。你可以用它来发现自己的解码器和分析工具中的差异！

起初，有指令解码

反编译和逆向工程工具是庞大而复杂的野兽，处理着二进制分析中最难的问题：变量类型和布局恢复、控制流图推断，以及为手动和自动检查而进行的可靠提升到高阶表示。

这些任务的核心是准确的指令解码。自动化工具需要忠实提取指令语义来自动化分析，而逆向工程师在尝试手动理解时期望得到准确的反汇编列表（或明确定义的失败模式）。

指令解码被隐含地视为已解决的问题。分析平台通过鼓励分析师将反汇编输出视为基本事实，而不考虑解码器中的潜在错误或输入中的对抗性指令序列，给分析师一种错误的信心感。

Mishegos挑战了这一假设。

(x86_64) 指令解码很难

真的很难：

与ARM和MIPS等RISC ISA不同，x86_64具有可变长度指令，这意味着解码器实现必须逐步解析输入以知道要获取多少字节。一条指令的长度可以在1字节（例如，0x90，nop）到15字节之间。更长的指令可能在语义上有效（即，它们可能描述有效的前缀、操作和字面量组合），但实际的硅实现最多只会获取和解码15字节（参见Intel x64开发者手册，§2.3.11）。

x86_64是一个40年前的16位ISA的32位扩展的64位扩展，该ISA设计为与50年前的8位ISA源代码兼容。简而言之，它是一团糟，每一代都增加和删除功能，重用或重载指令和指令前缀，并引入越来越复杂的支持模式和特权边界之间的切换机制。

许多指令序列具有重载的解释或看似合理的反汇编，这取决于活动处理器的状态或兼容模式。即使给出了相对精确的编译目标或预期执行模式信息，反汇编器也需要做出有根据的猜测。

x86_64指令格式的复杂性在可视化时尤其明显：

即使上面的图形也没有完全捕捉到x86_64的细微差别——它忽略了ModR/M和比例索引基址（SIB）字节的内部复杂性，以及操作码扩展位和各种扩展操作码的转义格式（传统转义前缀、VEX转义和XOP转义）。

总而言之，这些复杂性使x86_64解码器实现特别适合通过差分模糊测试进行测试——通过将变异引擎一次连接到几个不同的实现并比较每组输出，我们可以快速找出错误和缺失的功能。

为x86_64指令构建“滑动”变异引擎

鉴于这种布局以及我们对x86_64上最小和最大指令长度的了解，我们可以构建一个变异引擎，通过“滑动”策略探测解码管道的大部分：

1. 生成一个最多26字节的初始指令候选，包括结构上有效的前缀和修饰过的ModR/M和SIB字段。
2. 提取候选的每个“窗口”，其中每个窗口最多15字节，从索引0开始向右移动。
3. 一旦所有窗口耗尽，生成一个新的指令候选并重复。

为什么最多26字节？见上文！x86_64解码器最多只接受15字节，但生成长的（可能）语义上有效的x86_64指令候选并“滑动”通过意味着我们可以测试解码中的可能边缘情况：

• 未能处理多个重复的指令前缀。
• 发出无意义的前缀或反汇编属性（例如，在非字符串操作上接受和发出重复前缀，或在不可原子化的东西上使用锁前缀）。
• 未能正确解析ModR/M或SIB字节，导致不正确的操作码解码或错误的位移/立即数缩放/索引。

所以，一个最大的指令候选，用紫色显示（带有虚拟位移和立即数值，用灰色显示）如…

f0 f2 2e 67 46 0f 3a 7a 22 8e 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f

…产生12个“窗口”候选用于实际模糊测试。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

f0 f2 2e 67 46 0f 3a 7a 22 8e 00 01 02 03 04
f2 2e 67 46 0f 3a 7a 22 8e 00 01 02 03 04 05
2e 67 46 0f 3a 7a 22 8e 00 01 02 03 04 05 06
67 46 0f 3a 7a 22 8e 00 01 02 03 04 05 06 07
46 0f 3a 7a 22 8e 00 01 02 03 04 05 06 07 08
0f 3a 7a 22 8e 00 01 02 03 04 05 06 07 08 09
3a 7a 22 8e 00 01 02 03 04 05 06 07 08 09 0a
7a 22 8e 00 01 02 03 04 05 06 07 08 09 0a 0b
22 8e 00 01 02 03 04 05 06 07 08 09 0a 0b 0c
8e 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d
00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e
01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f

因此，我们的变异引擎花费大量时间尝试不同的前缀和标志序列，而相对较少的时间与（大多无关的）位移和立即数字段交互。

Mishegos: x86_64解码器的差分模糊测试

Mishegos采用上述“滑动”方法并将其集成到一个相当典型的差分模糊测试方案中。每个模糊测试目标都被包装到一个具有明确定义ABI的“工作进程”中：

• worker_ctor和worker_dtor：分别是工作进程设置和拆卸函数。
• try_decode：为每个输入样本调用，返回解码器的结果以及一些元数据（例如，消耗了多少字节的输入，解码器的状态）。
• worker_name：用于唯一标识工作进程类型的常量字符串。

代码库目前实现了五个工作进程：

• Capstone——一个流行的反汇编框架，最初基于LLVM项目的反汇编器。
• libbfd/libopcodes——流行的GNU binutils使用的支持库。
• udis86——一个较旧的、可能未维护的解码器（最后提交于2014年）。
• XED——英特尔的参考解码器。
• Zydis——另一个流行的开源反汇编库，强调速度和功能完整性。

由于简单的ABI，Mishegos工作进程往往非常简洁。例如，Capstone的工作进程只有32行：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <capstone/capstone.h>

#include "../worker.h"

static csh cs_hnd;

char *worker_name = "capstone";

void worker_ctor() {
  if (cs_open(CS_ARCH_X86, CS_MODE_64, &cs_hnd) != CS_ERR_OK) {
    errx(1, "cs_open");
  }
}

void worker_dtor() {
  cs_close(&cs_hnd);
}

void try_decode(decode_result *result, uint8_t *raw_insn, uint8_t length) {
  cs_insn *insn;
  size_t count = cs_disasm(cs_hnd, raw_insn, length, 0, 1, &insn);

  if (count > 0) {
    result->status = S_SUCCESS;
    result->len =
      snprintf(result->result, MISHEGOS_DEC_MAXLEN, "%s %s\n", insn[0].mnemonic, insn[0].op_str);
    result->ndecoded = insn[0].size;
    cs_free(insn, count);
  } else {
    result->status = S_FAILURE;
  }
}

图5：Capstone工作进程的源代码。

在幕后，工作进程通过槽并行接收输入和发送输出，这些槽通过由模糊测试引擎管理的共享内存区域访问。输入槽通过信号量轮询以确保每个工作进程已检索到用于解码的候选；输出槽用工作进程的名称和指令候选标记，以便以后收集到队列中。结果是一个相对快速的差分引擎，不需要每个工作进程在继续之前完成特定样本：每个工作进程可以以自己的速率消耗输入，只有输出槽的数量和队列收集限制整体性能。

鸟瞰图：

理解噪音

Mishegos产生大量输出：在一个不是特别快的Linux服务器上（在Docker内部！）进行60秒的单个运行产生大约100万个队列，或400万个捆绑输出（每个输入每个模糊测试工作进程1个输出，配置了4个工作进程）：

每个输出队列结构为一个JSON blob，看起来像这样：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

{
"input": "3626f3f3fc0f587c22",
"outputs": [
  {
    "ndecoded": 5,
    "len": 21,
    "result": "ss es repz repz cld \n",
    "workerno": 0,
    "status": 1,
    "status_name": "success",
    "worker_so": "./src/worker/bfd/bfd.so"
  },
  {
    "ndecoded": 5,
    "len": 5,
    "result": "cld \n",
    "workerno": 1,
    "status": 1,
    "status_name": "success",
    "worker_so": "./src/worker/capstone/capstone.so"
  },
  {
    "ndecoded": 5,
    "len": 4,
    "result": "cld ",
    "workerno": 2,
    "status": 1,
    "status_name": "success",
    "worker_so": "./src/worker/xed/xed.so"
  },
  {
    "ndecoded": 5,
    "len": 3,
    "result": "cld",
    "workerno": 3,
    "status": 1,
    "status_name": "success",
    "worker_so": "./src/worker/zydis/zydis.so"
  }
]
}

图8：来自Mishegos的示例输出队列。

在这种情况下，所有解码器都同意：输入的前五个字节解码为有效的cld指令。libbfd特别急切，报告了（无意义的）前缀，而其他解码器则默默地将它们丢弃为无关紧要。

但一致的成功的不是我们感兴趣的——我们想要差异，该死的！

差异可能出现在几个维度上：

• 一个或多个解码器在解码时消耗的字节数上存在分歧，尽管都报告成功。
• 一个或多个解码器报告失败（或成功），与其他解码器形成对比。
• 所有解码器报告成功并消耗相同数量的输入字节，但一个或多个在解码的重要组件上存在分歧（例如，实际的操作码或立即数/位移值）。

这些都有对抗性应用：

• 解码长度差异可能导致一连串不正确的反汇编，阻止自动化工具继续或让手动分析师负责重新对齐反汇编器。
• 直接解码失败可用于完全阻止使用易受攻击的工具或平台，或将恶意代码偷运过分析师。
• 组件差异可用于误导分析或人类分析师错误解释程序的行为。足够严重的差异甚至可用于掩盖恢复的控制流图！

Mishegos通过其分析工具发现这些差异类别，并通过mishmat（一个临时的HTML可视化）呈现它们。分析工具将语言无关的“过滤器”收集到“传递”中（想想LLVM），然后可以通过依赖图或基于感知的性能要求（即，最大的过滤器优先）对其内部过滤器进行排序。传递在./src/analysis/passes.yml中定义，例如：

1
2
3
4
5
6
7
8

# Find inputs that all workers agree are one size, but one or more
# decodes differently.
same-size-different-decodings:
- filter-any-failure
- filter-ndecoded-different
- filter-same-effects
- minimize-input
- normalize

图9：由几个过滤器组成的Mishegos分析传递示例

单个过滤器编写为小脚本，在stdin上获取队列并有条件地在stdout上发出它们。例如，filter-ndecoded-different：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

require "json"

STDERR.puts "[+] pass: filter-ndecoded-different"

count = 0
STDIN.each_line do |line|
  result = JSON.parse line, symbolize_names: true

  outputs_ndecoded = result[:outputs].map { |o| o[:ndecoded] }

  if outputs_ndecoded.uniq.size > 1
    count += 1
    next
  end

  STDOUT.puts result.to_json
end

STDERR.puts "[+] pass: filter-ndecoded-different done: #{count} filtered"

图10：Mishegos分析过滤器示例

过滤器还可以修改单个结果或整个队列。minimize-input过滤器将指令候选截断到指示的最长ndecoded字段，而normalize过滤器删除额外的空白，以便对单个汇编进行额外分析。

最后，可以通过分析命令行整体运行传递：

分析输出可以用mishmat可视化，并可选择HTML表的大小上限：

1

mishmat -l 10000 < /tmp/mishegos.sd > /tmp/mishegos.sd.html

最终，这产生了一些有趣的结果，如下所示（为可读性稍作重新格式化）。指令候选在左侧，单个解码器结果按列标记。libbfd列中的（bad）表示解码失败。（N/M）语法表示解码的字节数（N）和汇编字符串的总长度（M）：

图12：Capstone认为无意义的内容解码为有效的SSE指令。

图13：Capstone完全错过了一条指令。

图14：有趣的有符号表示。

| libbfd | capstone | zydis | xed | |——–|