《Binary Rewriting without Control Flow Recovery》论文笔记

一、概述

二进制重写技术在很多场景下都有大用，例如修复、加固、插桩、打补丁、调试等等。而大部分二进制重写技术都依赖于从输入二进制中恢复控制流信息，这是因为这些二进制重写技术通常都涉及指令移动等等，这就必须调整其他跳转指令的相对跳转偏移，即修复跳转目标集。

但问题在于，从二进制文件中恢复控制流信息是相当困难的：

• 一种方法是依赖于特定的二进制元数据，例如调试符号来恢复重定位信息，但并非所有二进制都会包含这类元数据（strip）
• 另一种方法是使用静态二进制分析技术来恢复，但通常效果不佳，而且不能应用于大小较大的二进制文件。

因此大部分二进制重写技术都依赖于一组甚至多组假设，例如特定编译器、特定编程语言等等。这样一来这些二进制重写技术都存在着局限性，难以扩展，同时也没办法处理大型程序，比如 chrome。

这篇论文向我们展示了一种基于 x86_64 的二进制重写技术，称为 e9patch。其中，e9 表示的是 jmpq rel32 的 opcode：0xe9。这种二进制重写技术的优点在于控制流无关（control flow agnostic），即无需任何控制流信息的知识。其二进制重写方法保留了跳转目标集，无需控制流恢复。因此， 这个工具相当的鲁棒，而且还可以 patch 诸如 chrome 等等大小大于 100MB 的二进制程序。

除了普通的二进制程序以外，e9patch 还可以为 shared objects 或 libraries 打补丁。

二、背景

控制流无关的二进制重写技术无需知道跳转目标集，它把每一条指令都当作潜在的跳转目标，并在控制流执行到该指令时，保留该指令的语义（注意，这里保留的是指令的语义，而不是原始指令）。即二进制中所有的指令满足以下三个条件中的任意一个:

• 原始指令的保留
• 替换为操作上等效的指令
• 替换为执行特定目的的指令，例如修复和插桩等等

以下是几种控制流无关的二进制重写技术，e9patch 将在这些技术的基础上进行扩展。

B0: int3 断点

这应该是原理最简单的技术。通过把特定指令 patch 成 int3 断点，当控制流执行到此处时便会触发 SIGTRAP，此时控制流被信号处理例程接管（在某些用途下甚至是调试器接管，例如 trapfuzz），这样一来要 patch 的工作便可以在信号处理例程中进行。

其缺点是：性能开销很大。中断和信号处理例程的切换，会涉及到用户-内核层上下文的切换，时间开销可能会上一个数量级。

B1: Jumps

这种方式会将目标指令替换成一条 jmpq rel32 指令，使得控制流在执行到此处时，跳转至 trampoline 里，之后在 trampoline 中执行 patch 的指令，并在需要时执行原先被 patch 的那条指令。这种方法的一个应用场景是 inline hook：

但这种方法同样存在着局限性。对于 jmpq rel32 指令来说，该指令的大小为 5 个字节。如果待 patch 的指令其指令大小大于等于5个字节，则直接将 jmpq 指令替换上去，此时这种重写技术还是控制流无关的。

但问题在于，如果待 patch 的指令小于 5 字节呢？以上图为例，将 mov edi, edi 指令替换成 jmpq 后，会一并覆盖掉下面两条指令。如果该函数中存在某条 jmp 指令跳转至被覆盖的那两条指令，则会触发异常，因为跳转目标的 opcode 已经被纂改。

B2: Instruction Punning

这个技术要重点说明一下，因为 e9patch 是基于这项技术进行的扩展。

除了上述两种方法以外，还有一种方法是专门处理一种可以与其他指令安全重叠的 jmpq 指令，这种方法称为 指令双关(Instruction Punning)。基本思想是找到与任何重叠指令共享相同字节表示的相对偏移量值，之后使用该相对偏移量，用 jmpq 指令安全地替换被 patch 的指令。

举个简单的例子，:

mov %rax, (%rbx)
add $32, %rax

对应到机器码便是下图中的 original：

假设我们需要 patch 掉 mov $rax, (%rbx)，instruction punning 便可以重用下条指令的前两个字节（0x48 0x83），使得在 patch 点凑出了一个五字节的 jmpq 指令（ jmpq 0x8348xxxx），同时避免修改下条指令的 opcode。

这样，当控制流执行到 mov 指令所对应的位置时，控制流便可以进行 jmpq 跳转。同时如果存在其他指令需要跳转至 add 指令时，add 指令也可以很好的工作，因为 add 指令的 opcode 并没有修改。

指令双关中的这个双关，指的是下条指令中的 opcode，既可以表示该指令，又可以表示 jmpq 的部分偏移量。

但这种方法同样存在局限性。注意到 jmp 中的相对跳转偏移高地址两个字节已经被下个指令的 opcode 给定死了。因此可跳转的内存空间被局限住了，只能相对跳转至相对偏移在 0x83480000~0x8348ffff 这个范围内的内存空间。这个范围的内存空间并非总是可用的，有可能这个范围正对应于：

• 另一个 trampoline 的内存区域
• 其他代码段或数据段
• 无效地址范围，例如 NULL 或下溢至负地址范围

以这个图为例，相对偏移量 0x8348xxxx 实际上是一个负数（32位偏移）。当相对偏移量为负数时，实际跳转至的位置可能在 NULL 周围甚至下溢至负地址范围，而这部分内存空间可能很难 mmap 到。

因此，指令双关技术只能给部分指令打上 patch，可 patch 的覆盖率不高。

三、设计

e9patch 基于上面 B1/B2 的方法，做了一系列改进。在说明具体改进之前，我们先说明该工具所基于的假设：

• 被 patch 的指令不能被自读取（例如自校验）或自写入。
• instrument 或 patch 是用户透明的，即程序行为不会通过某种侧通道（例如计时器、文件描述符等）而发生更改。
• 输入二进制本身没有使用指令覆盖或指令双关技术。

可以看到这里的假设相对于先前说的依赖编译器、依赖特定语言、依赖二进制元数据等放宽了很多，e9patch 都不依赖这些东西。

e9patch 并不内嵌反汇编器，而是靠用户来输入目标程序的指令信息（例如指令相对偏移和指令大小等等）。这样做的目的是为了实现更好的灵活性，用户可以在只知部分指令信息的情况下完成局部插桩，提高效率；而且还便于 e9patch 嵌入其他的设计中。

接下来我们来讲讲 e9patch 所提供的三种新策略。这里我们看看基于以下指令的一个示例：

Ins1: mov %rax, %(rbx)
Ins2: add $32, %rax
Ins3: xor %rax, %rcx
Ins4: cmpl $77, -4($rbx)

为了便于说明，这里给出几种假设：

1. 假设要 patch 的指令是 Inst1

2. 假设相对跳转偏移为负数时所对应的内存空间是无效的，即不可分配。

   因此先前介绍的 Instruction Punning 技术不可用，因为其相对跳转偏移为负数。

T1: Padded Jumps

通常 jmpq 的机器码长度为 5 个字节：1 字节的 opcode 和 4 字节的相对偏移。而实际上，还存在一种方法可以使用更多字节来对 jmpq 进行编码：使用冗余指令前缀形式的额外字节来填充跳转指令。

x86_64 中存在一些不会影响相对跳转指令语义的指令前缀，例如 REX 前缀、段重写前缀 (es,ss等等) 以及操作数重写前缀(0x66)。在这个例子中，我们可以使用指令前缀来对 jmpq 指令进行填充，以将相对偏移的字节表示向高地址处移动。

图中 T1(a) 使用了一个指令前缀 REX (0x48) 进行填充，填充后的 jmpq 范围为 0xc08348XX。由于该偏移量为一个负数值，因此不能使用，需要继续填充。

这里 e9patch 在 T1(a) 的基础上填充了段重写前缀 es (0x26)，填充后即为 T1(b) 的效果。可以看到此时 T1(b) 中 jmpq 的相对跳转指令为 0x20c08348，不再是个正数，因此该 jmpq 大概率可以跳转至一个可被分配的内存空间。

通过上面的这个例子我们可以看到策略 T1 的优点、缺陷和特性：

• 优点：可以通过额外写入一些指令前缀，来发现并使用新的有效相对跳转偏移

• 缺点：T1 适用性依赖于指令长度。如果指令长度较短，则 T1 能进行补丁尝试的次数将较少。这也意味着 T1 不能适用于单字节指令的 patch。

• 特性：每一次新的补丁尝试将会缩小 trampoline 可操作的内存地址范围。例如:

  • B2 相对跳转的可操作内存范围：0x83480000~0x8348ffff（范围：0x10000字节）
  • T1(a)：0xc0834800~0xc08348ff（范围：0x100字节）
  • T1(b): 0x20c08348（范围：0字节）

  这之所以被我归类到特性而非缺点，是因为 e9patch 只会在当前前缀所对应的内存空间不满足使用条件时才会继续增加前缀。不满足条件的内存空间范围再大也没有什么用处。

T2: Successor Eviction

如果使用 T1 方法时，再怎么 padding Ins1 也不存在可用的跳转偏移该怎么办？是不是可以尝试修改 Ins2 前几个字节的数据来对 Ins1 patch 提供条件？接下来就要介绍另一种策略，称为后继指令驱逐。其思路是：

1. 将相邻指令 Ins2 驱逐，换成一条 jmpq 指令。

2. 这条 jmpq 指令跳转至一个 trampoline2 上执行原有的 Ins2 指令，之后再调回来继续执行 ins3 即接下来的指令

注：将被驱逐的指令为 victim。

这样一来，Ins2 指令所对应的语义并没有被修改（因为 Ins2 确实被执行，与先前相比只是是在 trampoline2 中执行，同时多了两次跳转操作：调至 trampoline2 再跳回来）。但 Ins2 指令所在的内存地址，其上面的字节表示确确实实的发生了修改。这样一来，Ins1 便可以再次尝试使用 T1 策略来进行 patch，patch 成功后便可跳转至 trampoline1 中执行其他操作。

注意，两个 trampoline 是不一样的。

整个思路可以精简成：

尝试使用 T1 策略，发现 T1 策略无法 patch Ins1。为了修改 Ins1 所依赖的那些 Ins2 上的机器码，e9patch 先尝试使用 T1 策略来 patch Ins2。等 Ins2 patch 成功后，再来对 Ins1 重试 T1 策略。

整个过程仍然保证：

1. Ins2 的语义与原先一致
2. 程序跳转目标集不变

T3: Neighbour Eviction

如果相邻的指令不满足 patch 条件，同时 Successor Eviction 也不起作用，那该如何呢：

1. e9patch 会继续向后面找可用的机器码序列，作为其相对跳转偏移 rel32（高地址方向）

2. 找到后，就会在这里原地创建一个 jmpq 指令，即 T3(a)。

3. 之后，在被 patch 指令上 patch 一个相对短跳指令，跳转至这个新的 jmpq 指令处，也就是 T3(b)。

4. 注意到 Ins3 的机器码因为第二步的 patch 被修改。因此这里同样需要对 Ins3 做一个 patch 操作，patch 一个 jmpq 上去，使其跳转至 trampoline 执行 Ins3 指令。

   这样便可保证修改后与修改前 Ins3 指令的语义保持不变。（T3©）

T3 策略虽然较为复杂，但其功能较为强大，其关键之处在于 victim 的数量。假设指令平均长度为 4，那么短跳转大概可以跳转至 64 个潜在的 victim，因此大多情况下至少能找到一个合适的 victim，这个策略也将可 patch 指令的覆盖率提高至将近 100%。

以下是 T3 策略的示例：

S1: Reserve Order Patching

上面说的这些情况针对的都是 patch 单个指令的情况。但在实际情况中，通常用户可能会要求连续 patch 多条指令。

这里指的连续 patch 多条指令，不是指将这连续的指令 patch 成一个 trampoline jmp，而是指将连续指令的每一条指令都 patch 成多个 trampoline jmp。

我们再来看看这张图：

假设用户要将 Ins1 patch 成一个 trampoline1 jmp、Ins2 patch 成一个 trampoline2 jmp。那么如果我们先 patch Ins1 的话（T1(b)），可以看到 patch 后的 trampoline1 jmp 指令，会依赖 Ins2 中的机器码（因为 Ins1 jmpq rel32 中的相对偏移量现与 Ins2 的机器码重合）。

这种依赖关系会阻碍 Ins2 的 patch 过程，因为如果先 patch Ins1 再 patch Ins2 的话，Ins2 的 patch 过程可能会影响到 patch 后的 Ins1。

因此为了更好的管理多个 patch 的位置，e9patch 使用反向顺序补丁策略。其基本思想是：按照从高到低的地址顺序来 patch 指令，因为 指令双关 只能引入与后续指令的依赖关系。

e9patch 保存了每个指令机器码的状态，即锁定和未锁定，这可以使用一个 Bitmap 来保存。当某个机器码：

1. 被 e9patch 修改

2. 被用于指令双关的一部分机器码

则认为这个机器码是被锁定的。

T1-T3 的这些策略限制了：

1. patch 操作将不能修改被锁定的机器码（但是仍然可以利用，或者重叠）

2. 仅锁定当前 patch 位置后的字节（为了便于管理依赖）

   这使得 T3 的短跳 rel8 只能是正数，将可跳转的范围（即可被驱逐的指令个数）缩小一半。

   但是实际上这种限制在实验中影响很小。

M1: Memory and File Size Management

最后我们来考虑一下 trampoline 的内存存放位置。在先前的策略中我们可以看到，trampoline 的内存地址受到指令双关中相对偏移量的限制。例如：

• T1(b) 的 trampoline addr 为 0x20c08348

• T3(b) 中的 trampoline addr 为 0x4dfc7b83

这之中相差了非常远的内存距离，会影响 trampoline 的打包，导致高内存碎片和低内存利用率。同时离散的 trampoline 也会大大增加其保存在 ELF 文件中的大小。

那么很明显有一种方法可以缓解这种低效率的情况：将多个 trampoline 尽可能地放到同一个虚拟页中。只是最坏情况下是一个 trampoline 存放至一个内存页中。

因此 e9patch 还使用了一种机制称为 Physical Page Grouping：

尝试将多个存放在不同 virtual page 中的 trampoline，聚拢并存放到同一个 physical page。

以上图为例，先前是一个 Physical Page P(a) 对应于一个 Virtual Page V(a)。这种对应关系会占用大量的物理内存。但执行 Physical Page Grouping 后，映射关系是一个 Physical Page P(b) 对应于多个 Virtual Page V(b)，这样可以节省下大量的物理内存。

注：一个跨越 Page 的 trampoline 被视为两个 mini trampoline。

从 V(a) 到 P(b) 的这种 grouping 算法称为分区算法。分区算法的实现有很多种，这里 e9patch 选择的是最简单的贪心算法，而且性能较为不错。

Physical Page Grouping 也有自身的副作用：

1. 会将那些没有用到的 trampoline 加载进冗余的内存位置。由于这些冗余的 trampoline 并没有被使用，因此不会影响到程序的行为。
2. 会导致同一物理内存被多次映射至虚拟空间中，映射次数可能会超过默认的最大映射次数 vm.max_map_count = 65536。有两种解决方法：
   1. 使用 sudo 修改默认最大内存映射次数，不太现实。
   2. 控制 e9patch 的划分精度参数 M（聚拢 trampoline 所使用的最大物理页面个数），增加所使用的物理页面个数 P(b)，从而降低每个物理内存的映射次数。通常 M >= 64 时，单个二进制文件的物理内存页面映射次数便会始终小于默认内存最大映射次数。

四、实现

e9patch 的输入：

1. 未被 patch 的二进制程序
2. 二进制程序的指令信息，包括位置和指令大小
3. 待 patch 的指令位置信息集合
4. trampoline 集合

输出：一个使用上述策略的被 patch 程序。重写后的二进制文件相当于原始文件的插入式替换，无需额外依赖项。

实现中有两个点需要注意：

1. 新的 trampoline 被添加至 ELF 文件的末尾，防止移动现有的数据或代码，以避免修改复杂的 ELF header。
2. 存放 trampoline 的新物理页面必须在程序加载期间映射到程序的虚拟地址空间。在具体实现中，e9patch 将一个 mini loader 集成到了输出的二进制文件中，并将入口点替换成 mini loader 的入口点。待将 trampoline 所对应的虚拟页面映射完成后，再将控制流返回到真正的入口点。

e9patch 同时支持 PIE 和 non-PIE 的二进制文件。而且 PIE 程序会比 non-PIE 程序更好被 patch，因为 PIE 的代码通常会被加载到内存地址较高的位置，而 non-PIE 会被加载到内存地址较低的位置，而这与 NULL 更近。

某些情况会影响到 e9patch 的使用：

• L1: 虚拟内存短缺。对于一些具有非常大的代码段或者数据段的程序可能会限制 trampoline 的使用空间，因为 jmpq 的偏移是 32 位的，如果代码段和数据段太大，则可能会无法跳转至堆空间中。

• L2: patch 单字节指令。e9patch 无法 patch 单字节指令，这会影响到包括 push、pop、ret 在内的指令。

• L3: patch 超大量的指令 。如果尝试 patch 相当多指令的话，可能会因为机器码依赖关系而降低 patch 覆盖率。

除此之外，e9patch 不能处理那些 inline data 的情况，即 data 包含在 code 之中的情况。

不过通常情况下 L1并不适用于大部分程序; L2 和 L3 也与许多程序没有什么关系。

五、评估

主要从以下几个指标评估：

• patch 时间
• patch 覆盖率
• patch 后的二进制文件大小
• e9patch 实现原型的 scalability

e9patch 可应用与二进制加固、插桩和修复等等。patch 程序时， e9patch 主要为以下两种指令进行 patch：

1. 所有 jmp/jcc 跳转指令

   粗略模拟覆盖率插桩，因为 e9patch 在设计上没有基本块的信息，因此只是粗略的 patch 掉每个 jmp 指令。

2. 所有可能会写入堆指针的指令

   这里模拟的是二进制加固情况下，patch 掉写入堆指针相关的指令。

所有被 patch 的指令，都替换成一个除了执行原始指令以外的空 trampoline。以下是评估的结果：

#Loc: 总被 patch 的个数

Base%: B1+B2 策略

Succ%：总 patch 覆盖率

从上图可以看到：

• e9patch 的覆盖率相当的高，基本可以接近 100%。

• 在 baseline 覆盖率不高的情况下，T1-T3 策略可以将覆盖率极大的往高处升。

  这里尤其需要强调一下 T3 策略。T3 策略本身可 patch 的覆盖率就比较大，可以 patch 那些其他策略无法 patch 的指令。

• PIE 程序中任何一种 patch 策略都会比 non-PIE 程序中所对应的 patch 覆盖率要高很多。

• gamess 和 zeusmp 之所以覆盖率没有到 100% 是因为这两个程序都分配了相当大的 .bss 段（正对应于 L1）。当这两个程序使用 PIE 模式进行编译时可以达到 100% 的覆盖率。

• 在使用 physical page grouping 策略后，文件大小分别涨幅 +57% / +30% ，还算可以接受。

  在不使用该策略的情况下，大小涨幅分别是 +2239.83% / +568.96%，这就实在没法接受了。

之后是 scalability 的测试，这里是使用大型程序 chrome 和 firefox 的测试结果：

firefox 将大部分代码放置在 libxul.so 中。

测试时选择的测试集要求尽可能减小执行 JIT - JS 的代码执行时间。因为 e9patch 没法对 JIT 代码打 patch。

可以看到，chrome 引入了 ~+113% 的 overhead，firefox 引入了~+46% 的 overhead。firefox overhead 较低的一种可能原因是 firefox 花更多时间执行 JIT 代码，或者执行未被插桩的 shared object。

通过上面的内容可以看到， e9patch 可以很轻松的将 patch 规模扩展至上百兆文件大小的二进制程序。

最后是 e9patch 应用在二进制加固下的表现，这里先介绍一下测试用的二进制加固技术—— LowFat Pointer。其基本思想为：将程序虚拟内存空间分割为多个 large region，其中每个 region 负责分配一个给定的固定大小范围的对象：

• 第一个 Region 像往常一样包含程序文本、数据、bss等段。

• 后面的区域用于 LowFat 指针分配。例如，

  • Region #1用于大小为 1-16 字节的分配

  • Region #2 用于大小为 17-32 字节的分配

  • 等等

  此外，所有 LowFat 分配的对象都与分配大小边界对齐。这样一来，每一个 LowFat 指针的值都可以用于获取该对象的内存边界。

举个简单的例子：

p = malloc(10); // p = 0x8997f2820

由于指针 p 的值位于 0x800000000~0x1000000000 中，因此可以得知 p 所指向的内存大小为 16 字节（注意内存对齐）。

对于内存访问 q = 0x8997f2825，由于：

1. q 位于 0x800000000~0x1000000000 范围，因此 object size 大小为 16 字节
2. 由于 q 向下与 object size 对齐得到地址 0x8997f2820，这样便可得知 object 基地址

接下来对以下函数插桩：

char get(char *q, int i)
{
    return q[i];
}

得到该函数以检测 OOB：

char get(char *q, int i)
{
    char *q_base = base(q);
    size_t q_size = size(q);
    char *r = q + i;
    if (r < q_base || r >= q_base + q_size)
        report_oob_error();
    return *r;
}

而下图便是 e9patch 应用 LowFat 变体的实验结果：

而 lowfat 项目本身只能用在 C/C++ 语言中，而 e9patch 可以应用至任何语言的二进制文件中，因此 e9patch 相当的强大。