问题描述
Dr. Evil 投放了一个二进制炸弹（bomb），你需要向它输入正确的内容才能解除，否则炸弹就会被引爆。所幸的是，我们得到了 bomb 的主要源代码文件 bomb.c，通过其内容我们发现拆除它实际上分为 6 个阶段（phase），每个阶段都要我们输入一行字符串。但是从源文件中除了函数名外没有更多的信息了，我们目前唯一的破解办法是分析 bomb 程序的机器语言（汇编）描述，寻找各个阶段期望的输入。
网络上关于 Bomb Lab 的答案五花八门，因为“炸弹”确实有很多种：据说选修 CSAPP 的学生都将会得到一个独属于他们的“炸弹”，书本的配套资源也为自习的同学提供了练习的选择。所以在这篇文章中我不侧重于答案是什么，而是针对各个 phase 我的一些求解思路，一方面给读者提供一种参考，另一方面希望借此巩固我的知识基础。
Phase 1：访问地址
最开始时我用过反汇编工具 objdump -d 得到了 bomb 的汇编源码，它长到让人顿时失去了分析的兴致。不过，由 C 源码中我们看到各个 phase 的求解其实有一个统一的范式：
input = read_line();
phase_1(input);
phase_defused();
虽然我们不知道函数到底是如何实现的，但是从名字中也可以分析出 read_line 函数从某个地方（stdin 或者某个文件，从 main 函数开头的配置可以推测出来）得到字符串 input，并输入到判定函数 phase_1，如果失败程序直接退出，否则执行 phase_defused 函数表示这个 phase 已被解决。所以我们只需要分析 phase_1 函数的细节即可，其他 phase 也是这样。
为了体验上更舒适，我实际上利用了 gdb 来分析汇编，因为它可以很方便地显示出程序当前时刻各寄存器以及某个地址的值。具体的用法推荐看 Bomb Lab 说明中的推荐资源。这里使用 disassemble phase_1 得到的结果如下：
0x0000000000400ee0 <+0>: sub $0x8,%rsp
0x0000000000400ee4 <+4>: mov $0x402400,%esi
0x0000000000400ee9 <+9>: call 0x401338 <strings_not_equal>
0x0000000000400eee <+14>: test %eax,%eax
0x0000000000400ef0 <+16>: je 0x400ef7 <phase_1+23>
0x0000000000400ef2 <+18>: call 0x40143a <explode_bomb>
0x0000000000400ef7 <+23>: add $0x8,%rsp
0x0000000000400efb <+27>: ret
需要指出，这里的汇编片段采用 AT&T 语法。不愧是 phase_1，看起来就不难分析。我们不妨逐行看：
sub $0x8,%rsp
这一行和倒数第二行的 add $0x8,%rsp 一起作为栈空间的申请和释放，不过说实话我看不出来这一段哪里用到了空出来的栈空间，AI 解释说这是为了保证 call 指令要求的对齐：总之不是特别重要了。接下来是一个函数调用：
mov $0x402400,%esi
call 0x401338 <strings_not_equal>
这里把一个值传给寄存器 %esi，并调用了一个名为 strings_not_equal 的函数（这一看就知道干了什么）。我们知道，对于函数调用，%edi 这一系作为第一个参数，而 %esi 为第二个参数。%edi 在之前的过程没有被更改过，仍然为传入 phase_1 的第一个参数，即输入的字符串。到这里相比读者已经知道 phase_1 就是比较输入和某个特定的字符串是否相等来判断是否通过，接着看剩余的部分：
test %eax,%eax
je 0x400ef7 <phase_1+23>
call 0x40143a <explode_bomb>
这里是一个 if 语句，test %eax,%eax 是一个常用的办法，常常和后面的 je 部分一起判断 %eax 是否为 0，如果是则执行跳转。可以看到如果不跳转程序就会调用 explode_bomb 函数，所以正确的情况下 %eax 为 0。%eax 作为函数 strings_not_equal 的返回值，为 0 极有可能代表 false，也就是指两个字符串相等。综上，要解决 phase_1 只需要输入的字符串和给定的字符串相等。诚然我们没分析 strings_not_equal 的具体实现，不应该这么妄下结论，但事实可以作为佐证。为了获取这个给定的字符串，我们使用 gdb 的 x/s 命令，得到地址 0x402400 实际上存储的字符串是
Border relations with Canada have never been better.
将这个作为输入，我们发现 phase_1 通过了。顺便我们也确信了 strings_not_equal 函数的返回值含义。
Phase 2: 数列
这个 phase 也不长，先看反汇编结果：
0x0000000000400efc <+0>: push %rbp
0x0000000000400efd <+1>: push %rbx
0x0000000000400efe <+2>: sub $0x28,%rsp
0x0000000000400f02 <+6>: mov %rsp,%rsi
0x0000000000400f05 <+9>: call 0x40145c <read_six_numbers>
0x0000000000400f0a <+14>: cmpl $0x1,(%rsp)
0x0000000000400f0e <+18>: je 0x400f30 <phase_2+52>
0x0000000000400f10 <+20>: call 0x40143a <explode_bomb>
0x0000000000400f15 <+25>: jmp 0x400f30 <phase_2+52>
0x0000000000400f17 <+27>: mov -0x4(%rbx),%eax
0x0000000000400f1a <+30>: add %eax,%eax
0x0000000000400f1c <+32>: cmp %eax,(%rbx)
0x0000000000400f1e <+34>: je 0x400f25 <phase_2+41>
0x0000000000400f20 <+36>: call 0x40143a <explode_bomb>
0x0000000000400f25 <+41>: add $0x4,%rbx
0x0000000000400f29 <+45>: cmp %rbp,%rbx
0x0000000000400f2c <+48>: jne 0x400f17 <phase_2+27>
0x0000000000400f2e <+50>: jmp 0x400f3c <phase_2+64>
0x0000000000400f30 <+52>: lea 0x4(%rsp),%rbx
0x0000000000400f35 <+57>: lea 0x18(%rsp),%rbp
0x0000000000400f3a <+62>: jmp 0x400f17 <phase_2+27>
0x0000000000400f3c <+64>: add $0x28,%rsp
0x0000000000400f40 <+68>: pop %rbx
0x0000000000400f41 <+69>: pop %rbp
0x0000000000400f42 <+70>: ret
有点长了，是不是？
程序的控制流向
于我而言，分析汇编代码最大的挑战在于跳转。在刚开始练习时，我常常被跳来跳去的程序搞得焦头烂额——因为我试图像以前学习高级语言那样逐行分析程序，罔顾了失去抽象的汇编代码的冗杂。重新整理思路时，我了解到可以把跳转语句作为转折点分析程序的控制流向。以这个 phase 为例，它的控制流可以表示如下：
不难看到，这段代码里存在 2 个分支结构和 1 个循环结构。接下来我将逐部分来分析。
深入分析
首先是第 0 到 14 个字节处，代码先是将 %rbp 和 %rbx 入栈，我们知道这俩是 callee-saved，这么做可以保证函数调用不影响调用者的环境（更详细的描述见 CSAPP）。接着代码中在栈空间分配了大小为 0x28 字节即 40 字节的空间，并将栈顶指针放到寄存器 %rsi 中：结合后面的 call 段，我们不难推测出这是把 %rsp 的值作为函数 read_six_numbers 的参数，并配合 %rdi 指向的输入字符串实现从输入字符串读取 6 个数字，并将结果存到栈上。至于存的顺序，我们在这里其实无法判断，只能分析 read_six_numbers 函数的实现：
0x000000000040145c <+0>: sub $0x18,%rsp
0x0000000000401460 <+4>: mov %rsi,%rdx
0x0000000000401463 <+7>: lea 0x4(%rsi),%rcx
0x0000000000401467 <+11>: lea 0x14(%rsi),%rax
0x000000000040146b <+15>: mov %rax,0x8(%rsp)
0x0000000000401470 <+20>: lea 0x10(%rsi),%rax
0x0000000000401474 <+24>: mov %rax,(%rsp)
0x0000000000401478 <+28>: lea 0xc(%rsi),%r9
0x000000000040147c <+32>: lea 0x8(%rsi),%r8
0x0000000000401480 <+36>: mov $0x4025c3,%esi
0x0000000000401485 <+41>: mov $0x0,%eax
0x000000000040148a <+46>: call 0x400bf0 <__isoc99_sscanf@plt>
0x000000000040148f <+51>: cmp $0x5,%eax
0x0000000000401492 <+54>: jg 0x401499 <read_six_numbers+61>
0x0000000000401494 <+56>: call 0x40143a <explode_bomb>
0x0000000000401499 <+61>: add $0x18,%rsp
0x000000000040149d <+65>: ret
在这里我们看到了一系列的移动操作（mov 和 lea），结合后面调用 sscanf 我们不难推测这里正是把栈上的一块连续空间分成 6 块作为该函数的参数。具体地说，如果把这块空间的起始地址记为 n，则该函数 sscanf 的形参依次为：
| 形参 | 值 |
|---|---|
%rdi | 输入的字符串 |
%rsi | $0x4025c3 |
%rdx | n |
%rcx | n + 4 |
%r8 | n + 8 |
%r9 | n + 12 |
(%rsp) | n + 16 |
0x8(%rsp) | n + 20 |
从 sscanf 的定义可知 %rsi 存储的应该是格式字符串，利用 gdb 调试得到的实际结果为 "%d %d %d %d %d %d"，跟我们想得一样。
由此，我们也得到函数 read_six_numbers 最终读取的 6 个 32 位整数的顺序，现在回到 phase_2 接着往下看。紧接着的 cmp 段判断输入的第一个数字是否为 1，如果不是就执行 explode_bomb——所以输入的第一个数字就是 1；如果用 arr 表示所得 6 个数字组成的数组，该信息也可以表示为 arr[0]=1。52 到 57 字节处执行了 2 个 mov 操作，使得：
| 寄存器 | 值 |
|---|---|
%rbx | arr + 1 |
%rbp | arr + 6 |
这一步可以看成是循环的初始化操作，结合接下来的循环部分我们其实可以把它翻译成 C 代码段：
int *cursor = arr + 1; // lea 0x4(%rsp),%rbx
int *guard = arr + 6; // lea 0x18(%rsp),%rbp
while (cursor != guard) { // cmp %rbp,%rbx
int last = *(cursor - 1); // mov -0x4(%rbx),%eax
last *= 2; // add %eax,%eax
if (last != *cursor) { // cmp %eax,(%rbx)
explode_bomb();
}
cursor += 1; // add $0x4,%rbx
}
这里的转换并不复杂，想必大家一看能明白。从 C 代码中大家不难分析出输入的数组是公比为 2 的等比数列，我就不再赘述了。
Phase 3: Switch
按照惯例，先看反汇编结果：
0x0000000000400f43 <+0>: sub $0x18,%rsp
0x0000000000400f47 <+4>: lea 0xc(%rsp),%rcx
0x0000000000400f4c <+9>: lea 0x8(%rsp),%rdx
0x0000000000400f51 <+14>: mov $0x4025cf,%esi
0x0000000000400f56 <+19>: mov $0x0,%eax
0x0000000000400f5b <+24>: call 0x400bf0 <__isoc99_sscanf@plt>
0x0000000000400f60 <+29>: cmp $0x1,%eax
0x0000000000400f63 <+32>: jg 0x400f6a <phase_3+39>
0x0000000000400f65 <+34>: call 0x40143a <explode_bomb>
0x0000000000400f6a <+39>: cmpl $0x7,0x8(%rsp)
0x0000000000400f6f <+44>: ja 0x400fad <phase_3+106>
0x0000000000400f71 <+46>: mov 0x8(%rsp),%eax
0x0000000000400f75 <+50>: jmp *0x402470(,%rax,8)
0x0000000000400f7c <+57>: mov $0xcf,%eax
0x0000000000400f81 <+62>: jmp 0x400fbe <phase_3+123>
0x0000000000400f83 <+64>: mov $0x2c3,%eax
0x0000000000400f88 <+69>: jmp 0x400fbe <phase_3+123>
0x0000000000400f8a <+71>: mov $0x100,%eax
0x0000000000400f8f <+76>: jmp 0x400fbe <phase_3+123>
0x0000000000400f91 <+78>: mov $0x185,%eax
0x0000000000400f96 <+83>: jmp 0x400fbe <phase_3+123>
0x0000000000400f98 <+85>: mov $0xce,%eax
0x0000000000400f9d <+90>: jmp 0x400fbe <phase_3+123>
0x0000000000400f9f <+92>: mov $0x2aa,%eax
0x0000000000400fa4 <+97>: jmp 0x400fbe <phase_3+123>
0x0000000000400fa6 <+99>: mov $0x147,%eax
0x0000000000400fab <+104>: jmp 0x400fbe <phase_3+123>
0x0000000000400fad <+106>: call 0x40143a <explode_bomb>
0x0000000000400fb2 <+111>: mov $0x0,%eax
0x0000000000400fb7 <+116>: jmp 0x400fbe <phase_3+123>
0x0000000000400fb9 <+118>: mov $0x137,%eax
0x0000000000400fbe <+123>: cmp 0xc(%rsp),%eax
0x0000000000400fc2 <+127>: je 0x400fc9 <phase_3+134>
0x0000000000400fc4 <+129>: call 0x40143a <explode_bomb>
0x0000000000400fc9 <+134>: add $0x18,%rsp
0x0000000000400fcd <+138>: ret
我们依旧先分析结构。根据跳转指令，程序的控制流向可以表示为：
严谨地说，这个图是有问题的：因为程序在第 50 个字节处存在一个间接跳转，
jmp *0x402470(,%rax,8)
这条指令根据 %rax 的值得到存储在内存上的用于跳转的地址（*(0x402470 + %rax * 8)）。这很有可能影响程序的结构，所以，我们先用 gdb 看看它有可能跳转到的位置：
%rax | 跳转到的地址 | 相对函数入口的偏移（字节） |
|---|---|---|
| 0 | 0x400f7c | 57 |
| 1 | 0x400fb9 | 118 |
| 2 | 0x400f83 | 64 |
| 3 | 0x400f8a | 71 |
| 4 | 0x400f91 | 78 |
| 5 | 0x400f98 | 85 |
| 6 | 0x400f9f | 92 |
| 7 | 0x400fa6 | 99 |
当 %rax 为其他数时得到的地址没有意义，所以我们只能找到这些（后面更详细的分析能够佐证这一事实）。不难看出来跳转到的位置有一个规律：
mov <xx>,%eax
jmp 0x400fbe <phase_3+123>
即先是给 %eax 赋值，然后跳转到 123 字节的位置——那里是一个决定这个 Phase 能否通过的判断。如此一来，想必整个程序的结构读者也比较清晰了，接下来再对各部分分别分析。
0 ~ 24 字节部分，程序先申请了一块栈上的空间，然后把其上两个地址赋给 %rdx 和 %rcx。接着，程序把内存上的某个地址赋给了 %esi，（结合之前的经验和后面的 sscanf，我们其实不难推测这里应该是一个格式字符串），用 gdb 分析后得到其内容为 "%d %d"。可见，这一部分是从输入字符串中读取两个整数放到栈上，其中第一个数放在 0x8(%rsp)，第二个数放在 0xc(%rsp)。第 32 个字节位置的比较只是为了保证得到的是两个数。
接着到了第 39 个字节的位置，这里比较得到的第一个是否比 7 大，如果是则调用 explode_bomb，因此我们输入的第一个数不大于 7。随后程序把得到第一个数的值赋给寄存器 %eax，并根据它的值来进行间接跳转。由此我们也能知道为什么前面的内容中 %rax 取值只有那几个。
接下来的部分我们已经总结了规律，这些分支最后都会到同一个位置：
cmp 0xc(%rsp),%eax
也就是说，在分支内完成赋值后又那这个值与我们输入的第二个数比较，如果相同则函数正常返回，Phase 通过；否则将调用 explode_bomb。
总结一下，这个 Phase 可以理解成预先定义了一个“数组”，我们的输入其实是猜测某个索引的数是什么。从反汇编结果中我们其实已经知道了这个“数组”是：
[207, 311, 707, 256, 389, 206, 682, 327]
未完待续……
说明：我这学期有嵌入式系统的课程，会涉及 ARM 的汇编。为了避免跟 x86 搞混，这一章我先搁置了（很长时间！！！）。不过需要指出，在 Phase 2 中提到的方法仍旧适用于后面更复杂的 Phase 的分析。
剧透一下，其实有 7 个 phase，不妨猜猜那一个被藏在了什么地方。