《Breaking the x86 ISA》 Christopher Domas 2017 论文笔记
处理器并非一个可信的代码执行黑盒，现代 x86 芯片中不乏秘密指令和硬件缺陷。
本文中，作者展示了一种基于 Page Fault Analysis 和一些新的处理器模糊测试技术的测试方案，
可以遍历 x86 指令集的指令空间。该方法揭露了 x86 的关键缺陷，未知机器指令和俯拾皆是的软件问题，
以及商用 hypervisor 中的缺陷。
以本论文的工作为基础，开发了新的开源分析工具 sandshifter，
帮助用户审计处理器上的缺陷、后门和隐藏功能。
历史上的 x86 指令集问题
- Pentium F00F 和 Cyrix comma bug
- Intel’s mysterious Appendix H, 内容是在早期 x86 设计中的 ICE 执行模式
- 利用后门的方式，如 AMD 和 VIA 的密码保护寄存器
Pentium F00F
f00f bug 是一个发现于 1997 年的设计缺陷，在执行 F0 0F C7 C8 是，会导致处理器停止全部的功能，除非物理启动。
因为 F0 0F C7 C8 对应的指令是 lock cmpxchg8b eax (locked compare and exchange of 8 bytes in register eax)，
也被称为 invalid operand with locked CMPXCHG8B instruction bug。
该指令序列的执行并不需要任何特殊权限，cmpxchg8b 指令应当比较的是 edx 和 eax，操作数应为内存中的 8 bytes 数据地址。
然而，eax 替换了内存地址作为操作数，这是一个无效操作数。
在正常情况下，这会导致处理器异常，然而当使用 locked 前缀 （通常用于避免两个处理器处理同一个内存地址的数据导致的相互影响），
CPU 错误地使用了锁定总线周期数，导致错过了非法指令异常 handler 描述符没有被读取。locked read 必须匹配 locked write，
CPU 总线接口在这期间禁止其它内存访问，直到相应的写发生。而非法指令异常抛出后，指令停止执行，使得处理器访存总线锁死，
无法执行任何功能，必须物理重置。
为了绕过这一缺陷，需要打断错误的总线使用模式，intel 提供了一个不直观的设定，强制处理器在含有描述符和可能抛出异常的访存指令前，
抛出 intervening page fault，使得操作系统可以进行总线使用模式检查。
方法
本文的目标是：找到一种方式系统的穷尽搜索 x86 指令集，以找到隐藏或未在文档中出现的指令和指令级别的缺陷。
为达成这一目标，我们应当生成所有潜在的 x86 指令，执行它，并观察结果。这其中主要的难点在于 x86 指令集本身的复杂度：
- x86 指令集的长度可以长达 15 bytes，这使得简单的迭代搜索不可行
- 随机选择可能的指令也只能覆盖潜在搜索空间的很小一部分
一种降低搜索空间的方式是按照 x86 参考手册中的格式生成指令，但这种方法不能找到隐藏指令，而忽略无效指令相关的错误。本文提出了一种基于观察指令长度变更的搜索算法压缩指令的搜索空间。
tunneling instruction generation
作者将这种指令搜索算法称为 tunneling 的算法流程如下：
- 生成一个 15 bytes 的 buffer 作为生成的初始指令，不妨初始化为 0
- 通过执行该指令，获得以字节为单位的指令长，并生成新指令继续迭代
- 如果递增后结果导致指令长增加，则在新增加的 byte 上递增
- 如果在最后一字节上递增 256 次（即遍历全部可能性），则在前一个 byte 继续递增
该技术高效地遍历了有意义的 x86 指令搜索空间，相较于在 15 byte 空间上逐 bit 随机的空间，有所压缩，也跳过了相对不重要的立即数部分（不能使指令长度增加，只会枚举立即数中的一部分可能性）。这使得模糊测试可以专注于指令格式意义，包括 prefixes, opcodes, 和操作数选择等。
tunneling 方法当且仅当有可靠的方法确定任意一条 x86 指令（即使未在指令文档上）的长度为前提。由于隐藏指令不能被反汇编，一个可行的获取指令长度的选择是 x86 trap 标志位（gdb 进行单步调试所插入的标志位，在这里也进行类似于单步的计算，int 3 是一种特殊的 1-byte 中断，如果 debugger 设定了 trap flag，会在每个指令执行后默认执行 int 1，允许调试器执行单步指令，而不必每次插入 int 3），执行该条指令，并观察执行前后的指令指针值。然而，这种方法需要指令成功执行，对抛出异常的错误指令是无效的，因为错误指令没有执行，指令指针也没有改变。想找到所有隐藏指令或缺陷指令，找到兼容错误指令的方法是其中关键。
此外，实际上，当该方法运行在某个特权 ring 上时，如果希望执行的指令需要更高的权限，就会造成一些问题。如 inc eax 可以在 ring 3（用户态）执行，执行 mov eax, cr0则需要 ring 0（内核态）执行，rsm 只能在 ring -2（系统管理模式 System Management Mode）。为了保证方法有效性，fuzzer 应当可以确认哪些指令需要更高的特权执行，即使它没有相应的权限。
Page Fault Analysis
为了有效的确定，指令长度，即使是错误指令，作者介绍了一种称作 ”Page Fault Analysis“ 的技术。通过把指令递增的移过页边界，当指令有效部分跨越页边界时，就会触发页错误。
一个候选指令生成后，将它放入内存，使它的第一个字节在一个可执行页的最后字节处，而剩下的字节，位于后续的不可执行内存页中。接下来执行该指令，如果在取指令过程中抛出异常，处理器触发 #GP 中断，页边界地址会作为该异常的参数返回。这表示当前指令的一部分在不可执行页中。任何其它结果都表示该指令被成功从内存取出，即已完整存在于可执行页内。逐次递增指令在可执行页的长度，使得不再出现 #GP 中断，或异常返回的参数不再是页边界地址为止，这时在可执行页中的指令长度是指令有效长度。
通过这种方法，使得我们可以解析错误指令的有效长度，可以认为错误指令的有效长，就是 CPU 解码错误指令时停止的字节。分析非法指令的方法也启发了对特权指令的分析：一个非法指令，会抛出 #UD 异常，而一个特权指令会抛出 #GP 异常。通过官产抛出的异常，fuzzer 即使在 ring 3 也能有效探索 ring 0 到 ring -2 的特权指令空间。
avoid system crash
模糊测试硬件指令，很重要的一点是避免系统永久性破坏系统或处理状态。一个基本的保障是使用 ring 3 权限运行 fuzzer，以确保操作系统不会被破坏，至多破坏了进程状态，导致 fuzzer 自身 crash。
当生成的指令向 fuzzer 的地址空间中写入时，很容易破坏 fuzzer 的运行状态。这一问题，可以通过将所有寄存器设置为 0 解决，使得基于寄存器的寻址都指向 0，即 NULL，避免了像正常地址空间的写入。
将地址为 0 的页映射到内存中还有助于分析一些类型的指令细节。例如，不映射地址为 0 页时，mov eax, ]ecx + 8*edx 和 mov cr0, eax 会触发 #GP 异常。因为抛出的异常类型相同，fuzzer 不能确定哪个是因为需要特权执行而失败，哪个不是。通过映射 0 到内存中，用户态可执行的指令可以成功执行，帮助了 fuzzer 区分特权指令。
带移位的内存访问（memory access with a displacement） 也可能导致进程状态被破坏。例如 inc [0x0804a10c] 在 32 bit 平台上会命中数据段，不管寄存器的初始状态。然而在 tunneling 算法一次只会操作指令中的一个字节，因此只会覆盖 inc [0x0000000c]、inc [0x0000a100]、inc [0x00040000]、inc [0x08000000]。实际上，8bit + 4 Byte align 单 byte 的枚举只会影响 1kB 的数据，在 32 bit 空间中，实际发生破坏的可能性仅是四百万分之一。
resume coherent execution state
通过在待测指令执行前置位 x86 trap flag，并 catch 单步中断可以解决测试前后程序状态维护的问题。通过这种方式，可以再任意的跳转和顺序指令后重新获得控制权。
总结
通过 tunneling 指令发现算法，作者成功将 15 bytes 的完全随机指令空间（约 10^36）压缩到数百万条量级。并开源了 sandshifter，该工具实现了指令生成、指令执行、观察指令长和与反汇编器和架构文档比对预期值来发现错误，任何的差异都会记录到日志中。
注，指令在 disassembler 中的结果并不可信，QEMU 中的运行结果与实际裸机执行的结果亦有差异，手册和裸机执行结果才是标准