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

指令解码的开端

反编译和逆向工程工具是处理二进制分析中最难题的复杂系统：变量类型和布局恢复、控制流图推断，以及为手动和自动检查提供高阶表示。所有这些任务的核心是准确的指令解码。自动化工具需要精确提取指令语义，而逆向工程师在手动分析时期望获得准确的反汇编列表（或明确定义的失败模式）。

指令解码被隐式视为已解决的问题。分析平台通过鼓励分析师将反汇编输出视为绝对真理，而不考虑解码器中的潜在错误或输入中的对抗性指令序列，给他们带来错误的信心。Mishegos对这一假设提出了挑战。

x86_64指令解码的艰巨性

x86_64解码异常困难：

• 与ARM和MIPS等RISC ISA不同，x86_64具有可变长度指令，这意味着解码器实现必须逐步解析输入以知道要获取多少字节。指令长度可以从1字节（例如0x90，nop）到15字节不等
• x86_64是一个40年前16位ISA的32位扩展的64位扩展，设计为与50年前8位ISA源兼容。简而言之，这是一团乱麻，每一代都增加和删除功能，重用或重载指令和指令前缀，并引入越来越复杂的支持模式和权限边界之间的切换机制
• 许多指令序列具有重载解释或看似合理的反汇编，具体取决于活动处理器的状态或兼容模式。即使给定相对精确的编译目标或预期执行模式信息，反汇编器也需要做出有根据的猜测

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

即使上面的图形也没有完全捕捉x86_64的细微差别——它忽略了ModR/M和scale-index-base（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"进程中：

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

代码库目前实现了五个worker：

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

由于简单的ABI，Mishegos worker往往极其简单。例如，Capstone的worker只有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 worker的源代码

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

鸟瞰图：

理解噪声

Mishegos产生大量输出：在不太快的Linux服务器上（在Docker内部！）进行60秒的单次运行产生约100万个群组，或400万个捆绑输出（每个worker每个输入1个输出，配置了4个worker）：

每个输出群组结构为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特别急切地报告了（无意义的）前缀，而其他解码器则静默地丢弃它们作为无关内容。

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

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

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

这些都有对抗性应用：

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

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表的大小上限：

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

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

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

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

图14：有趣的有符号表示

图15：未记录的操作码差异！

图16：仅XED和Zydis

图17：当然，libbfd完全且重复错误

上面的结果是在存储库的修订版88878dc上捕获的。您可以通过在手动模式下运行模糊测试器来重现它们：

M=1 mishegos ./workers.spec <<< "36f03e4efd" > /tmp/mishegos

重要启示

对于逆向工程师和程序分析师：x86_64指令解码是困难的。您依赖的工具集合实际上并不可靠。给定Mishegos的输出，构造混淆您的工具和浪费您时间的对抗性二进制文件是可能的（甚至微不足道）。我们已经向上游报告了其中一些问题，但不要误解：信任您的解码器完美报告字节序列的机器行为将会让您吃亏。

并非一切都是悲观和沮丧。如果您需要准确的指令解码（您确实需要！），您应该使用XED或Zydis。libopcodes在指令支持方面经常接近Zydis和XED，但 consistently记录误报并将仅前缀解码为有效指令。Capstone定期报告误报和漏报。udis86（上面未显示）行为类似于libopcodes，并且鉴于其维护不稳定，不应使用。

这篇文章是我们团队关于解析的变幻莫测的众多文章之一。请关注此空间，等待Evan Sultanik关于多语言和精神分裂解析的文章。