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

指令解码的起源

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

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

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

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上最小和最大指令长度的了解，我们可以构建一个突变引擎，通过“滑动”策略探测解码管道的大部分：

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

为什么最多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个“窗口”候选用于实际模糊测试。

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——Intel的参考解码器。
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


#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特别急切，并报告（无意义的）前缀，而其他解码器则默默地将它们丢弃为无关紧要。

但一致的成