课程实验

CSAPP 2e Bomb Lab 笔记

这个 Lab 训练的是分析汇编代码和使用 GDB 调试的能力。题目是一个二进制文件 bomb，和只包含 main 函数的 bomb.c，使用者需要借助工具，在六个 Phase 中分别输入对应的文本，来解除 “炸弹”。一旦输入错误，就会 “引爆炸弹”。

每个人生成的 bomb 内容可能不尽相同，但思路相似，这里只以我做到的版本为例。

实验文件 （是 32 位）：https://git.cyp0633.icu/cyp0633/CSAPP-labs/src/branch/master/LAB3-bomblab

环境：Ubuntu 22.04, GDB 12.0.90

参考资料：

前期准备

最基础的一点是，你需要对汇编语言有一定的了解，起码能够大概熟悉 CSAPP 前三章的内容。

正如上文所说，最好先熟悉一下 GDB 的使用，边写边查也不是不行，但很容易拖慢速度。可以看看 https://www.cnblogs.com/acceptedzhs/p/13161213.html，或者 参考资料 1 中的 gdb 命令速查，非常有用。 可以在 GDB 中执行 layout asm 来打开下面的视图，事半功倍：

GDB 分屏

此外，还需要准备一份反汇编代码，objdump -d bomb > bomb.s 就可以将 bomb 反汇编，并将代码保存到 bomb.s 中。也可以在 GDB 中进行反汇编。当然，1800 行的汇编代码应该不会有人去完全研究，所以只能结合调试来做。

你还需要一个能够计算十六进制的计算器。如果你使用 Windows，可以使用自带计算器；在 Linux 下，可以使用 Python。

除此之外，如果你有二进制文件分析的经验，你也可以直接使用 angr 等工具直接找到答案，达成速通。

Phase 1

查看 bomb.c 得到 Phase 1 相关的 C 代码。

c 
1
2
3
4
5

    input = read_line();             /* Get input                   */
    phase_1(input);                  /* Run the phase               */
    phase_defused();                 /* Drat!  They figured it out!
          * Let me know how they did it. */
    printf("Phase 1 defused. How about the next one?\n");

可以看出，程序先使用 read_line() 函数读取输入，并让 input 变量指向它。然后将其传给 phase_1。此时 char 指针应该存储在 4(%esp) 中。然后查看 phase_1 的反汇编代码。包括 read_line 之类的函数并不需要详细了解，因为我们可以很容易看出来它干了什么。

asm 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

08048b90 <phase_1>:
 8048b90: 83 ec 1c              sub    $0x1c,%esp
 8048b93: c7 44 24 04 0c a2 04  movl   $0x804a20c,0x4(%esp)
 8048b9a: 08 
 8048b9b: 8b 44 24 20           mov    0x20(%esp),%eax
 8048b9f: 89 04 24              mov    %eax,(%esp)
 8048ba2: e8 43 05 00 00        call   80490ea <strings_not_equal>
 8048ba7: 85 c0                 test   %eax,%eax
 8048ba9: 74 05                 je     8048bb0 <phase_1+0x20>
 8048bab: e8 45 06 00 00        call   80491f5 <explode_bomb>
 8048bb0: 83 c4 1c              add    $0x1c,%esp
 8048bb3: c3                    ret

程序看起来像是构建了 strings_not_equal 的两个参数，test 指令用于判断返回的值是否为 0（参见 Stack Overflow），如果为 0 代表不相等，就跳转到 explode_bomb。

我们可以直接从两个参数入手，一个是我们输入的内容，另一个 0x804a20c 自然就指向了我们想要的字符串。进入 gdb，打断点，使用 x/s 0x804a20c 读取那个位置的字符串，然后输入 c 继续运行，将其输入即可。解出 Phase 1 答案是 “You can Russia from land here in Alaska.”。

建议将断点打到 read_line 上，如果打到 phase_1 上，便无法在读到答案之后输入文字，可能要炸一次炸弹。

Phase 1 解决

Phase 2

关键词：循环

main 函数中关于 Phase 2 的部分和 Phase 1 差不多，那么我们直接来看反汇编。

asm 
 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

08048bb4 <phase_2>:
 8048bb4: 56                    push   %esi
 8048bb5: 53                    push   %ebx
 8048bb6: 83 ec 34              sub    $0x34,%esp
 8048bb9: 8d 44 24 18           lea    0x18(%esp),%eax
 8048bbd: 89 44 24 04           mov    %eax,0x4(%esp)
 8048bc1: 8b 44 24 40           mov    0x40(%esp),%eax
 8048bc5: 89 04 24              mov    %eax,(%esp)
 8048bc8: e8 4f 06 00 00        call   804921c <read_six_numbers>
 8048bcd: 83 7c 24 18 00        cmpl   $0x0,0x18(%esp)
 8048bd2: 75 07                 jne    8048bdb <phase_2+0x27>
 8048bd4: 83 7c 24 1c 01        cmpl   $0x1,0x1c(%esp)
 8048bd9: 74 1f                 je     8048bfa <phase_2+0x46>
 8048bdb: e8 15 06 00 00        call   80491f5 <explode_bomb>
 8048be0: eb 18                 jmp    8048bfa <phase_2+0x46>
 8048be2: 8b 43 f8              mov    -0x8(%ebx),%eax
 8048be5: 03 43 fc              add    -0x4(%ebx),%eax
 8048be8: 39 03                 cmp    %eax,(%ebx)
 8048bea: 74 05                 je     8048bf1 <phase_2+0x3d>
 8048bec: e8 04 06 00 00        call   80491f5 <explode_bomb>
 8048bf1: 83 c3 04              add    $0x4,%ebx
 8048bf4: 39 f3                 cmp    %esi,%ebx
 8048bf6: 75 ea                 jne    8048be2 <phase_2+0x2e>
 8048bf8: eb 0a                 jmp    8048c04 <phase_2+0x50>
 8048bfa: 8d 5c 24 20           lea    0x20(%esp),%ebx
 8048bfe: 8d 74 24 30           lea    0x30(%esp),%esi
 8048c02: eb de                 jmp    8048be2 <phase_2+0x2e>
 8048c04: 83 c4 34              add    $0x34,%esp
 8048c07: 5b                    pop    %ebx
 8048de9: 83 7c 24 18 0e        cmpl   $0xe,0x18(%esp)
 8048dee: 76 05                 jbe    8048df5 <phase_4+0x38>
 8048c08: 5e                    pop    %esi
 8048c09: c3                    ret

read_six_numbers 很容易让人联想，本题的答案是六个数字。

浅看一眼 read_six_numbers 函数的反汇编（不需要全看懂），可以得出六个数字的地址是 0x8(%esp) 一直到 0x1c(%esp)，对应 phase_2 中从 0x18(%esp) 开始（也可以在 gdb 中对比寄存器得出）。由 0x8048bd4 的语句来看，如果第二个数不是 2，就会触发 explode_bomb；由 0x8048bcd，如果第一个数不是 0，也会爆炸。

从 0x8048be2 到 0x8048c02 似乎是一个循环。8048bfa 和 8048bfe 的两条 lea 语句是这个循环的初始化部分，因为这只在 0x8048bd9 处被调用，正常来说则会跳过这两段。如果这六个数用 C 形容为 int num[6]，那么 esi 就是 num+6，是循环的界限，ebx 的初值就是 num+2，是循环的起始（前两个数已经验证过了），相当于 int i=2。

初始化之后开始看循环体，从 0x8048be2 到 0x8048bf6。首先给 eax 寄存器赋值为 num[i-1]+num[i-2]，然后将其与 num[i] 比较。如果不相等，就爆炸。否则，将 ebx 增 4，相当于 i++。再将其与边界 esi 比较，如果不相等，继续循环。

这样，这六个数字的规律就出现了：是前面多了一个 0 的斐波那契数列，0，1，1，2，3，5。

Phase 2 解决

Phase 3

关键词：跳转表

Phase 3 反汇编代码太长了，就不一股脑放出来了。

asm 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

 8048c0a: 83 ec 3c              sub    $0x3c,%esp
 8048c0d: 8d 44 24 2c           lea    0x2c(%esp),%eax
 8048c11: 89 44 24 10           mov    %eax,0x10(%esp)
 8048c15: 8d 44 24 27           lea    0x27(%esp),%eax
 8048c19: 89 44 24 0c           mov    %eax,0xc(%esp)
 8048c1d: 8d 44 24 28           lea    0x28(%esp),%eax
 8048c21: 89 44 24 08           mov    %eax,0x8(%esp)
 8048c25: c7 44 24 04 5e a2 04  movl   $0x804a25e,0x4(%esp)
 8048c2c: 08 
 8048c2d: 8b 44 24 40           mov    0x40(%esp),%eax
 8048c31: 89 04 24              mov    %eax,(%esp)
 8048c34: e8 27 fc ff ff        call   8048860 <__isoc99_sscanf@plt>

反汇编代码中，一上来就像是构建了一个调用函数的参数列表，似乎有五个参数，均为 4 字节。往下看，果不其然调用了 sscanf。在 Shell 中执行 man sscanf 查看 Linux 自带手册，发现它类似于 scanf，只不过输入源是指定的字符串。对照参数列表，发现 0x804a25e 处是固定的，不随外界改变，同时又在 0x4(%esp) 即第二个参数位置，那么很可能是 format 部分。执行 print (char*)0x804a25e，得到 "%d %c %d"，这就对应了第 3、4、5 个参数（设为 int a，char b，int c）的格式了。这里记下，**a = esp+0x8、 **b = esp+0xc 和 **c = esp+0x10，由 leal 指令反推， *a = esp+0x28， *b = esp+0x27， *c = esp+0x2c。

asm 
1
2
3
4
5
6
7

 8048c39: 83 f8 02              cmp    $0x2,%eax
 8048c3c: 7f 05                 jg     8048c43 <phase_3+0x39>
 8048c3e: e8 b2 05 00 00        call   80491f5 <explode_bomb>
 8048c43: 83 7c 24 28 07        cmpl   $0x7,0x28(%esp)
 8048c48: 0f 87 f5 00 00 00     ja     8048d43 <phase_3+0x139>
 8048c4e: 8b 44 24 28           mov    0x28(%esp),%eax
 8048c52: ff 24 85 70 a2 04 08  jmp    *0x804a270(,%eax,4)

然后将 sscanf 的返回值与 2 比较。查看手册得，它会返回格式化字符串中匹配到参数的数量。如果少于 3 个参数，一样会引爆炸弹。它还会将 0x28(%esp) 即 a 与 7 比较，如果大于 7，也会引爆炸弹，那么第一个数的取值被限制在了 0~7。

之后很明显是一个跳转表的结构，看起来像来自一个 switch 语句，大胆猜测是第一个参数为 0-7 的每种结果。比较简单的一种方法，是在跳转表跳转语句处打断点，将 a 直接先代入 0-7 中的一种，步进查看分支的地址，也可以分别使用 p/x *address 来直接把完整的跳转表挖出来。这里以 a = 0 为例，其他的应该也差不多。

asm 
1
2
3
4
5
6
7

 8048c59: b8 68 00 00 00        mov    $0x68,%eax
 8048c5e: 81 7c 24 2c 8b 01 00  cmpl   $0x18b,0x2c(%esp)
 8048c65: 00 
 8048c66: 0f 84 e1 00 00 00     je     8048d4d <phase_3+0x143>
 8048c6c: e8 84 05 00 00        call   80491f5 <explode_bomb>
 8048c71: b8 68 00 00 00        mov    $0x68,%eax
 8048c76: e9 d2 00 00 00        jmp    8048d4d <phase_3+0x143>

上面是 a = 0 分支的汇编代码。首先给 eax 赋值，这个之后会用到。然后比较了 c 与 0x18b 即 395，不相等则会引爆炸弹。如果相等，则再次进行一次跳转：

asm 
1
2
3
4
5

 8048d4d: 3a 44 24 27           cmp    0x27(%esp),%al
 8048d51: 74 05                 je     8048d58 <phase_3+0x14e>
 8048d53: e8 9d 04 00 00        call   80491f5 <explode_bomb>
 8048d58: 83 c4 3c              add    $0x3c,%esp
 8048d5b: c3                    ret

比较 al 与 b，不相等的话引爆炸弹。al 是将 eax 的 0-7 位拎出来。eax = 0x68 = 0x0000 0068，那么 al = 0x68。不记得的话，也可以通过 GDB 执行 info registers al 查看。在 Shell 执行 man ascii 打开 ASCII 码表，寻找 HEX=68，对应的是 h。

于是我们得出了 a、b、c 的值。a 和 c 的值是联动的，一个组合为 0 和 395，而 b 固定为 h。

Phase 3 解决

Phase 4

关键词：递归

asm 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

 8048dbd: 83 ec 2c              sub    $0x2c,%esp
 8048dc0: 8d 44 24 1c           lea    0x1c(%esp),%eax
 8048dc4: 89 44 24 0c           mov    %eax,0xc(%esp)
 8048dc8: 8d 44 24 18           lea    0x18(%esp),%eax
 8048dcc: 89 44 24 08           mov    %eax,0x8(%esp)
 8048dd0: c7 44 24 04 af a3 04  movl   $0x804a3af,0x4(%esp)
 8048dd7: 08 
 8048dd8: 8b 44 24 30           mov    0x30(%esp),%eax
 8048ddc: 89 04 24              mov    %eax,(%esp)
 8048ddf: e8 7c fa ff ff        call   8048860 <__isoc99_sscanf@plt>
 8048de4: 83 f8 02              cmp    $0x2,%eax
 8048de7: 75 07                 jne    8048df0 <phase_4+0x33>
 8048de9: 83 7c 24 18 0e        cmpl   $0xe,0x18(%esp)
 8048dee: 76 05                 jbe    8048df5 <phase_4+0x38>

这道题一开始也调用了 sscanf，和 Phase 3 差不多。那么方法也一样，熟练地使用 print (char*)0x804a3af，得到格式化的形式为 "%d %d"，就是两个整型。设两个参数分别为 a、b，那么有 *a = esp + 0x18，*b = esp + 0x1c。如果参数不为 2 个，就会引爆炸弹。

后面还将 a 与 0xe 即 14（无符号）比较，限制 $a \le 14$ 时跳转到 0x08048df5，否则引爆炸弹。那么这个地方干了什么呢？

asm 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

 8048df5: c7 44 24 08 0e 00 00  movl   $0xe,0x8(%esp)
 8048dfc: 00 
 8048dfd: c7 44 24 04 00 00 00  movl   $0x0,0x4(%esp)
 8048e04: 00 
 8048e05: 8b 44 24 18           mov    0x18(%esp),%eax
 8048e09: 89 04 24              mov    %eax,(%esp)
 8048e0c: e8 4b ff ff ff        call   8048d5c <func4>
 8048e11: 85 c0                 test   %eax,%eax
 8048e13: 75 07                 jne    8048e1c <phase_4+0x5f>
 8048e15: 83 7c 24 1c 00        cmpl   $0x0,0x1c(%esp)
 8048e1a: 74 05                 je     8048e21 <phase_4+0x64>
 8048e1c: e8 d4 03 00 00        call   80491f5 <explode_bomb>
 8048e21: 83 c4 2c              add    $0x2c,%esp
 8048e24: c3                    ret

这一段先为 func4 的调用构建了参数，func4 的三个参数分别是 a、0 和 0xe 即 14。然后分别校验了两个条件，是 func4 的返回值即 eax = 0 和 b=0。既然输入文本的两个部分约束都给出了，只需要枚举 $0 \le a \le 14,\ b=0$ 的每一种可能，总能够找到至少一个答案。幸运的是，试出的第一个组合 0 0 就是一个解。

但是为了追求完美，我们还需要看看 func4 干了什么。设传入的三个参数分别为 x、y、z，则：

asm 
 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

08048d5c <func4>:
 8048d5c: 56                    push   %esi ;save registers
 8048d5d: 53                    push   %ebx
 8048d5e: 83 ec 14              sub    $0x14,%esp ;allocate stack
 8048d61: 8b 54 24 20           mov    0x20(%esp),%edx ;edx=x
 8048d65: 8b 44 24 24           mov    0x24(%esp),%eax ;eax=y
 8048d69: 8b 5c 24 28           mov    0x28(%esp),%ebx ;ebx=z
 8048d6d: 89 d9                 mov    %ebx,%ecx ;ecx=z
 8048d6f: 29 c1                 sub    %eax,%ecx ;ecx=z-y
 8048d71: 89 ce                 mov    %ecx,%esi ;esi=z-y
 8048d73: c1 ee 1f              shr    $0x1f,%esi ;esi is sign bit of z-y, biased bit
 8048d76: 01 f1                 add    %esi,%ecx ;ecx=z-y+sign(z-y)
 8048d78: d1 f9                 sar    %ecx ;ecx=(z-y)/2
 8048d7a: 01 c1                 add    %eax,%ecx ;ecx=y+(z-y)/2=(y+z)/2
 8048d7c: 39 d1                 cmp    %edx,%ecx ;(z+y)/2<=x?
 8048d7e: 7e 17                 jle    8048d97 <func4+0x3b> ;if so, goto 0x8048d97
 8048d80: 83 e9 01              sub    $0x1,%ecx ;ecx--
 8048d83: 89 4c 24 08           mov    %ecx,0x8(%esp) ;z(func4)=ecx
 8048d87: 89 44 24 04           mov    %eax,0x4(%esp) ;y(func4)=eax
 8048d8b: 89 14 24              mov    %edx,(%esp) ;x(func4)=edx=x
 8048d8e: e8 c9 ff ff ff        call   8048d5c <func4> ;recursive call
 8048d93: 01 c0                 add    %eax,%eax ;eax=eax+eax (return value)
 8048d95: eb 20                 jmp    8048db7 <func4+0x5b> ;return eax
 8048d97: b8 00 00 00 00        mov    $0x0,%eax ;eax=0
 8048d9c: 39 d1                 cmp    %edx,%ecx ;ecx<=x?
 8048d9e: 7d 17                 jge    8048db7 <func4+0x5b> ;if so, return 0
 8048da0: 89 5c 24 08           mov    %ebx,0x8(%esp) ;z(func4)=ebx
 8048da4: 83 c1 01              add    $0x1,%ecx ;ecx++
 8048da7: 89 4c 24 04           mov    %ecx,0x4(%esp) ;y(func4)=ecx
 8048dab: 89 14 24              mov    %edx,(%esp) ;x(func4)=edx=x
 8048dae: e8 a9 ff ff ff        call   8048d5c <func4> ;recursive call
 8048db3: 8d 44 00 01           lea    0x1(%eax,%eax,1),%eax ;eax=2*eax+1, return value
 8048db7: 83 c4 14              add    $0x14,%esp ;restore stack pointer
 8048dba: 5b                    pop    %ebx ;restore registers
 8048dbb: 5e                    pop    %esi
 8048dbc: c3                    ret

首先得把 func4 的代码分析一遍，顺便写点注释，走一步看一步，把每一步要干什么先弄明白。0x8048d73 处取符号位加上去的操作是一个偏置，为了让算术右移 1 位和除以 2 的行为一致，可以阅读 CSAPP 原书来了解。光看汇编来分析整体行为有一定的难度，我们不妨试着把它 “意译” 成 C 代码。（感谢 @404NotFound 的提醒，第 10 行条件应为 a==x）

asm 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

int func4(int x, int y, int z)
{
    int a = (y + z) / 2, ret;
    if (a> x)
    {
        a--;
        ret = func4(x, y, a);
        return 2 * ret;
    }
    if (a == x)
    {
        return 0;
    }
    a++;
    ret = func4(x, a, z);
    return ret * 2 + 1;
}

可以代入 a 的各个情况，自行跑一跑这个函数，记录返回 0 的情况，很容易跑出来所有答案。

Phase 4 解决

Phase 5

关键词：不同长度的 MOV 指令

这道题比较抽象，难度不仅仅在汇编上。

asm 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

 8048e25: 53                    push   %ebx
 8048e26: 83 ec 28              sub    $0x28,%esp
 8048e29: 8b 5c 24 30           mov    0x30(%esp),%ebx
 8048e2d: 65 a1 14 00 00 00     mov    %gs:0x14,%eax
 8048e33: 89 44 24 1c           mov    %eax,0x1c(%esp)
 8048e37: 31 c0                 xor    %eax,%eax
 8048e39: 89 1c 24              mov    %ebx,(%esp)
 8048e3c: e8 8a 02 00 00        call   80490cb <string_length>
 8048e41: 83 f8 06              cmp    $0x6,%eax
 8048e44: 74 4c                 je     8048e92 <phase_5+0x6d>
 8048e46: e8 aa 03 00 00        call   80491f5 <explode_bomb>
 8048e4b: 90                    nop
 8048e4c: 8d 74 26 00           lea    0x0(%esi,%eiz,1),%esi

这一段的主要作用就是检查了输入字符串的长度，限制了长度为 6。有几处代码不太好理解：%gs: 似乎保证了栈的完整性（见 此处）；异或自身是比较快的将寄存器置 0 的方式（见 此处）；而 0x8048e4c 处的指令，其实是又一个 nop（见 此处）。此外，我们设 *a = 0x14 + eax，这段代码还令 a=0x14=20， ebx=esp+0x30。

asm 
1
2
3
4
5
6
7

 8048e52: 0f b6 14 03           movzbl (%ebx,%eax,1),%edx
 8048e56: 83 e2 0f              and    $0xf,%edx
 8048e59: 0f b6 92 90 a2 04 08  movzbl 0x804a290(%edx),%edx
 8048e60: 88 54 04 15           mov    %dl,0x15(%esp,%eax,1)
 8048e64: 83 c0 01              add    $0x1,%eax
 8048e67: 83 f8 06              cmp    $0x6,%eax
 8048e6a: 75 e6                 jne    8048e52 <phase_5+0x2d>

一个 jmp 指令带我们到了 0x8048e92，粗看一眼结构像个循环。给 eax 赋初值 0 之后，就又跳到了 0x8048e52。循环内的部分就是如上所示。在这里，eax 从 0 到 6 的每一次循环中：

  • 将 ebx+eax 处的字符截取低 4 位，存入 edx
  • edx 作为索引，在 0x804a290+edx 处取 1 个字节
  • 将这个字节存到 esp+0x15+eax

自然会想到取 0x804a290 中的内容，是 “maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"，因为索引只有 4 位，所以有效的只有 “So” 前面的部分。可以看出，经过这个循环，在 0x15+esp 处形成了另一个长度为 6 的字符串。

asm 
1
2
3
4
5
6
7
8

 8048e6c: c6 44 24 1b 00        movb   $0x0,0x1b(%esp)
 8048e71: c7 44 24 04 67 a2 04  movl   $0x804a267,0x4(%esp)
 8048e78: 08 
 8048e79: 8d 44 24 15           lea    0x15(%esp),%eax
 8048e7d: 89 04 24              mov    %eax,(%esp)
 8048e80: e8 65 02 00 00        call   80490ea <strings_not_equal>
 8048e85: 85 c0                 test   %eax,%eax
 8048e87: 74 10                 je     8048e99 <phase_5+0x74>

循环之后，call 了一个 strings_not_equal，显然其中一个参数是我们刚刚形成的字符串，另一个在 0x804a257。读取它，结果是 “bruins”。不算结束符号，正好六个字符。如果两个字符串相等的话，炸弹就可以解除了。我们所要做的，就是反推六个索引字符。每个字符只需要结尾四位符合索引值、属于可打印的值就可以了，所以可以有多种答案，比如 “-&#$(’”。

上面的流程，可以用一张图表示：

图解

好了，又解决一道题。

Phase 5 解决

Phase 6

关键词：链表

本 Phase 核心部分跳来跳去的，巨难。第一部分是熟悉的读 6 个数字，设 *a=0x10+esp，这里就不再赘述了。

asm 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

 8048eca: be 00 00 00 00        mov    $0x0,%esi ;set esi as i, i=0
 8048ecf: 8b 44 b4 10           mov    0x10(%esp,%esi,4),%eax ;eax = a[i]
 8048ed3: 83 e8 01              sub    $0x1,%eax ;eax = a[i] - 1
 8048ed6: 83 f8 05              cmp    $0x5,%eax ;compare eax with 5
 8048ed9: 76 05                 jbe    8048ee0 <phase_6+0x2f> ;if a[i] <= 5, dont explode
 8048edb: e8 15 03 00 00        call   80491f5 <explode_bomb>
 8048ee0: 83 c6 01              add    $0x1,%esi ;i++
 8048ee3: 83 fe 06              cmp    $0x6,%esi ;if i < 6, jump to 8048eef
 8048ee6: 75 07                 jne    8048eef <phase_6+0x3e>
 8048ee8: bb 00 00 00 00        mov    $0x0,%ebx
 8048eed: eb 38                 jmp    8048f27 <phase_6+0x76>
 8048eef: 89 f3                 mov    %esi,%ebx ;ebx=j=i
 8048ef1: 8b 44 9c 10           mov    0x10(%esp,%ebx,4),%eax ;eax = a[j]
 8048ef5: 39 44 b4 0c           cmp    %eax,0xc(%esp,%esi,4) ;compare a[i-1] and a[j]
 8048ef9: 75 05                 jne    8048f00 <phase_6+0x4f> ;if a[i-1] == a[j], explode
 8048efb: e8 f5 02 00 00        call   80491f5 <explode_bomb>
 8048f00: 83 c3 01              add    $0x1,%ebx ;j++
 8048f03: 83 fb 05              cmp    $0x5,%ebx ;if j<=5, jump to 8048ef1
 8048f06: 7e e9                 jle    8048ef1 <phase_6+0x40>
 8048f08: eb c5                 jmp    8048ecf <phase_6+0x1e> ;jump to next i of outer loop

上面是第二部分，代码里写了注释，包含了我对此代码的初步分析。观察可得，esi 和 ebx 是两个循环变量，对于每个 esi，ebx 都要变一个来回，这证明了实际上是两层循环，esi 设为 i，是外层循环的循环变量，ebx 设为 j，是内层循环的循环变量。用 C 表示可能会好懂些：

c 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

for (int i = 0; i < 6;)
{
    if ((a[i] - 1 > 5 || a[i] - 1 <0) && a[i] != 0)
    {
        explode_bomb();
    }
    i++;
    for (int j = i; j <= 5; j++)
    {
        if (a[i - 1] == a[j])
        {
            explode_bomb();
        }
    }
}

简单来说，就是保证了数组 a 中值均小于等于 6，且两两不相等。或者说，是 1-6 的一个排列（减 1 正是为了去除 0 的情况）。循环完成后，跳转到 0x8048f27，进入第三部分。从这里开始就变得十分抽象了，但暂时没有懂的话不用急，会懂的。

asm 
1
2
3
4
5
6
7

 8048f27: 89 de                 mov    %ebx,%esi
 8048f29: 8b 4c 9c 10           mov    0x10(%esp,%ebx,4),%ecx
 8048f2d: 83 f9 01              cmp    $0x1,%ecx
 8048f30: 7e e4                 jle    8048f16 <phase_6+0x65>
 8048f32: b8 01 00 00 00        mov    $0x1,%eax
 8048f37: ba 3c c1 04 08        mov    $0x804c13c,%edx
 8048f3c: eb cc                 jmp    8048f0a <phase_6+0x59>

在这段代码运行之前，在 0x8048eed 处，ebx 已经被归零了，这里大胆猜测它是一个索引变量，这里将其设为 k。而按照这个来推断的话，ecx 首先被赋值 a[k]。然后分了 ecx 是否小于等于 1 的情况（没有 0，相当于是否等于 1），如果不是，先给 eax 赋 1，再将 edx 赋一个像是地址的立即数。eax 可能是另一个索引变量，这里设为 l。这里先来看 ecx=1 的情况。

asm 
1
2
3
4
5

 8048f16: ba 3c c1 04 08        mov    $0x804c13c,%edx
 8048f1b: 89 54 b4 28           mov    %edx,0x28(%esp,%esi,4)
 8048f1f: 83 c3 01              add    $0x1,%ebx
 8048f22: 83 fb 06              cmp    $0x6,%ebx
 8048f25: 74 17                 je     8048f3e <phase_6+0x8d>

将 1 单独拎出来，或许和单独构建之后的数依赖的某种头有关。这里也将刚刚遇见过的一个立即数赋给了 edx，那么不得不对其产生怀疑，那就用 GDB 进行一个内存的读。

读取 edx 即 0x804c13c 处的结果

比较难想到的一点是，你直接读取 0x804c13c 处的一个 word，是读不到什么有用的信息的，但也不是完全无迹可寻。首先引人注意的是这个变量的名字 “node1”，让人不由得考虑链表的结构：如果能够依据此扩展显示的范围，向上图一样多显示几个 word，就能够发现端倪。这样很容易能够推断出 node 的结构：4 个字节的内容，4 个字节的序号，4 个字节的下一节点地址。接着往下读，发现 node 从 1 到 6，可能对应了刚刚我们输入的六个值。即使不一次读 3 个也没关系，也能够观察到 node 标签。

很巧的是，8048f1b 处的基址 0x28，正好和 a 数组基址 0x10 差了 24 个字节，也就是 6 个双字变量。那么上面的汇编代码所要做的事情，就是将编号为 1 的节点地址存储到 a 数组之后。之后将 ebx 也就是 k 自增 1，如果等于 6 则跳出这个循环，否则直接 fallthrough。按理说，单单是 a[k]=1 的情况不需要又是自增又是判断。那么，如果不为 1 呢？

asm 
1
2
3
4
5
6
7
8
9

 8048f32: b8 01 00 00 00        mov    $0x1,%eax
 8048f37: ba 3c c1 04 08        mov    $0x804c13c,%edx
 8048f3c: eb cc                 jmp    8048f0a <phase_6+0x59> 

 8048f0a: 8b 52 08              mov    0x8(%edx),%edx
 8048f0d: 83 c0 01              add    $0x1,%eax
 8048f10: 39 c8                 cmp    %ecx,%eax
 8048f12: 75 f6                 jne    8048f0a <phase_6+0x59>
 8048f14: eb 05                 jmp    8048f1b <phase_6+0x6a>

我在这里拼接了两段汇编代码，它们原本并不是连续的。现在 edx 寄存器保存了刚刚链表的首节点地址，而 0x8048f0a 处的指令，是将 edx+8 中的内容赋给 edx。再次联想到刚刚所说的节点结构，每个节点地址 + 8 位置的变量正是保存了下一个节点地址，这相当于 C 语言中的 p = p -> next。然后将 eax 即 l 自增 1，直到 l = a [k]。那么 C 语言代码大概是这样：

c 
1
2
3
4
5
6

do
{
    p = p->next;
    l++;
} while (l != a[i]);
asm("jmp 0x8048f1b");

接下来跳转到 0x8048f1b，这也是刚刚 a[k]=1 的情况中，越过赋初值的语句处。

asm 
1
2
3
4

 8048f1b: 89 54 b4 28           mov    %edx,0x28(%esp,%esi,4)
 8048f1f: 83 c3 01              add    $0x1,%ebx
 8048f22: 83 fb 06              cmp    $0x6,%ebx
 8048f25: 74 17                 je     8048f3e <phase_6+0x8d>

这块代码的行为应该不需要过多解释了，两部分结合来看，所做的事情就是将第 a[k] 个节点的地址，填入 esp+0x28 这个数组（设置为 n）中的第 k 个位置。连起来，翻译成 C 语言：

c 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

int l;
node *head = 0x804c13c, *p, *n[6];
for (int k = 0; k < 6; i++)
{
    if (a[k] == 1)
    {
        n[k] = head;
    }
    else
    {
        p = head;
        l = 1;
        do
        {
            p = p->next;
            l++;
        } while (l != a[k]);
        n[k] = p;
    }
}

从 0x8048f3e 开始，到 0x8048f5a，是第四部分。

asm 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

 8048f3e: 8b 5c 24 28           mov    0x28(%esp),%ebx
 8048f42: 8d 44 24 2c           lea    0x2c(%esp),%eax
 8048f46: 8d 74 24 40           lea    0x40(%esp),%esi
 8048f4a: 89 d9                 mov    %ebx,%ecx
 8048f4c: 8b 10                 mov    (%eax),%edx
 8048f4e: 89 51 08              mov    %edx,0x8(%ecx)
 8048f51: 83 c0 04              add    $0x4,%eax
 8048f54: 39 f0                 cmp    %esi,%eax
 8048f56: 74 04                 je     8048f5c <phase_6+0xab>
 8048f58: 89 d1                 mov    %edx,%ecx
 8048f5a: eb f0                 jmp    8048f4c <phase_6+0x9b>
 8048f5c: c7 42 08 00 00 00 00  movl   $0x0,0x8(%edx)

这一段的主要作用是将各节点按照在 n 中的顺序重新连起来，并将尾节点 next 设为 null。它遍历了 p 中 5 对相邻两节点的组合，并对每个组合，将前一个节点连到后一个节点上，而它的关键就在 0x8049f4e：将后一个节点的地址写入到前一个节点的 next 部分。对这一段要整体去把握，如果尝试理解每一句的意思是很有困难的。

asm 
1
2
3
4
5
6
7
8
9

 8048f63: be 05 00 00 00        mov    $0x5,%esi
 8048f68: 8b 43 08              mov    0x8(%ebx),%eax
 8048f6b: 8b 00                 mov    (%eax),%eax
 8048f6d: 39 03                 cmp    %eax,(%ebx)
 8048f6f: 7d 05                 jge    8048f76 <phase_6+0xc5>
 8048f71: e8 7f 02 00 00        call   80491f5 <explode_bomb>
 8048f76: 8b 5b 08              mov    0x8(%ebx),%ebx
 8048f79: 83 ee 01              sub    $0x1,%esi
 8048f7c: 75 ea                 jne    8048f68 <phase_6+0xb7>

进入第五部分，这一部分干的事情是将上面提到的 5 个组合 反向 遍历一遍，并要求前一个节点的值大于等于后一个，即要求最后链表的值是降序排列的。 现在题目的条件就完全显露出来了，我们可以根据节点的值来确定输入六个数的顺序。按原顺序（重新连接之前），可以得出：

十六进制值 0x12d0x360x2470x3e60x27c0xd0
十进制值 30154583998636208

第一个当然要选择最大的，就是 998，对应 4；第二个是 636，对应 5…… 这样推出答案，就是 4 5 3 1 6 2。

Phase 6 解决

Secret Phase

关键词：二叉搜索树

在 bomb.c 中，作者已经暗示了一个 missing 的 secret phase 的存在。但是第六个 phase 完成后，程序会自动退出，所以我们首先需要另辟蹊径，找一个能够 call 出 secret phase 的地方，而它就在 phase_defused 中。

在每次 phase 结束之后，都会调用一次 phase_defused。而它的反汇编代码中，有很多跳转语句可能直接跳过 secret phase 的调用过程。那么直接先分析它的反汇编代码。

asm 
1
2
3
4
5
6

 8049366: 81 ec 8c 00 00 00     sub    $0x8c,%esp
 804936c: 65 a1 14 00 00 00     mov    %gs:0x14,%eax
 8049372: 89 44 24 7c           mov    %eax,0x7c(%esp)
 8049376: 31 c0                 xor    %eax,%eax
 8049378: 83 3d c8 c3 04 08 06  cmpl   $0x6,0x804c3c8
 804937f: 75 72                 jne    80493f3 <phase_defused+0x8d>

这是第一个可能跳过的地方。它将 0x804c3c8 指向的内容和 0x6 相比，查到在这之外有 read_line 和 skip 调用了这个地址，但我懒得分析，于是在 0x8049378 处打断点，在每次运行到此处的时候观察它的值（可以用 GDB 的 display 功能）。结果是十分巧合的，每解开一个 phase，这个变量都会 + 1。

0x804c3c8 的内容

而这个变量的 label 正好叫 num_input_string，代表已经输入的字符串数量，再结合下一行代码来看，如果没有输够六个，就直接跳过去。也就是说，只有在第六个 phase 之后，才有机会进入 secret phase。

asm 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

 8049381: 8d 44 24 2c           lea    0x2c(%esp),%eax
 8049385: 89 44 24 10           mov    %eax,0x10(%esp)
 8049389: 8d 44 24 28           lea    0x28(%esp),%eax
 804938d: 89 44 24 0c           mov    %eax,0xc(%esp)
 8049391: 8d 44 24 24           lea    0x24(%esp),%eax
 8049395: 89 44 24 08           mov    %eax,0x8(%esp)
 8049399: c7 44 24 04 09 a4 04  movl   $0x804a409,0x4(%esp)
 80493a0: 08 
 80493a1: c7 04 24 d0 c4 04 08  movl   $0x804c4d0,(%esp)
 80493a8: e8 b3 f4 ff ff        call   8048860 <__isoc99_sscanf@plt>
 80493ad: 83 f8 03              cmp    $0x3,%eax
 80493b0: 75 35                 jne    80493e7 <phase_defused+0x81>

这是第二个可能跳过的地方。我们先前已经熟悉了 sscanf 的参数设定，这次使用 GDB 读取 0x804a409 的字符串，得到 “%d %d %s”，这意味着我们需要输入两个数和一个字符串。跳过的条件是少于三个参数。

这里奇怪的是，为什么在没有输入的情况下，仍然有 0x804c4d0 作为源字符串？在运行到此处时读取它，发现在使用原正确答案输入的时候，读取到的是 “0 0”，恰巧和 Phase 4 的正解之一相同。为了进一步验证这一想法，可以尝试将第四题的所有正解代入，比对输入的正解和读取到的字符串，此处不再详述。结果是确实相同。

再想到 Phase 4 也使用了 sscanf，多余的参数并不会影响识别，所以第四题必须多输入一个字符串。

asm 
1
2
3
4
5
6
7

 80493b2: c7 44 24 04 12 a4 04  movl   $0x804a412,0x4(%esp)
 80493b9: 08 
 80493ba: 8d 44 24 2c           lea    0x2c(%esp),%eax
 80493be: 89 04 24              mov    %eax,(%esp)
 80493c1: e8 24 fd ff ff        call   80490ea <strings_not_equal>
 80493c6: 85 c0                 test   %eax,%eax
 80493c8: 75 1d                 jne    80493e7 <phase_defused+0x81>

这一段将 0x804a412 指向的字符串（读取得 “DrEvil”）与 0x2c+esp 处的字符串（即刚刚多输入的那个）相比，如果不相等则跳过。

现在进入 Secret Phase 的条件就很清楚了：在第四题的答案后加入一串 “DrEvil”。按要求输入后，果然弹出了几行文字提示，进入了传说中的 Secret Phase。下面是它的部分反汇编代码：

asm 
1
2
3
4
5
6
7

 8048fd9: e8 8e 02 00 00        call   804926c <read_line>
 8048fde: c7 44 24 08 0a 00 00  movl   $0xa,0x8(%esp)
 8048fe5: 00 
 8048fe6: c7 44 24 04 00 00 00  movl   $0x0,0x4(%esp)
 8048fed: 00 
 8048fee: 89 04 24              mov    %eax,(%esp)
 8048ff1: e8 da f8 ff ff        call   80488d0 <strtol@plt>

首先调用了一个 read_line，读取一行字符串。然后构建了 strtol 的三个参数，分别是刚刚输入的字符串、0 和 10。在 Shell 中输入 man strtol 来查看文档，内容如下。

strtol 手册内容

可以看到这个函数的功能是将一个字符串转换为长整型。第一个参数是字符串的起始地址；第二个参数是结束地址，这里传入一个 0 代表 NULL；第三个参数则是进制，这里为 10。返回值是转换结果。

那么这一整串代码的作用，就是输入一个整数。

asm 
1
2
3
4

 8048ff6: 89 c3                 mov    %eax,%ebx
 8048ff8: 8d 40 ff              lea    -0x1(%eax),%eax
 8048ffb: 3d e8 03 00 00        cmp    $0x3e8,%eax
 8049000: 76 05                 jbe    8049007 <secret_phase+0x32>

这部分代码的作用是限制读取的整数在 $[1,1001]$ 范围内，减一是为了去除 0。

asm 
1
2
3
4
5

 8049007: 89 5c 24 04           mov    %ebx,0x4(%esp)
 804900b: c7 04 24 88 c0 04 08  movl   $0x804c088,(%esp)
 8049012: e8 6d ff ff ff        call   8048f84 <fun7>
 8049017: 83 f8 05              cmp    $0x5,%eax
 804901a: 74 05                 je     8049021 <secret_phase+0x4c>

这部分调用了 fun7，参数分别是像一个地址的立即数和刚刚输入的数。如果返回值为 5，则成功解决 Secret Phase。

下面是 fun7 的部分反汇编代码。

asm 
1
2
3
4

 8048f88: 8b 54 24 20           mov    0x20(%esp),%edx
 8048f8c: 8b 4c 24 24           mov    0x24(%esp),%ecx
 8048f90: 85 d2                 test   %edx,%edx
 8048f92: 74 37                 je     8048fcb <fun7+0x47>

首先很容易看出来 fun7 一开始是检查 edx 是否为 0，但暂时不知道那两个 mov 是什么意思。瞥一眼后面的代码，发现 edx 后面的地址多次作为参数被递归调用，于是决定看一眼 edx。

edx 指向及后面一部分内存的内容

label 后面有序号，预示着后面可能还有值的存在，将预览范围扩展到下一个 label 出现前，发现排列有一定的规律。这一块内存似乎表示了一个三元组，由值和两个地址构成，符合一个二叉树节点的形式。按照这个形式把它组织起来，如下图。节点并不是按顺序组织的，写的时候对每个节点只写其值和左右字节点的地址，会更方便。

画出的二叉树

我们惊奇地发现这是一棵二叉搜索树，而且是十分平衡的 AVL 树，刚刚筛选范围在 $[1,1001]$ 的目的，正是保证输入的值有位置可放。GDB 读到的 label 符合一个 $nxy$ 的格式，$x$ 代表层数（从 1 开始），$y$ 代表从左开始数的序号，如 $n46$ 正好是第四行第六个节点。传入 fun7 的第一个参数是 AVL 树的当前节点地址（而从 secret_phase 调用时是根节点地址），第二个参数是我们输入的数，分别放置在 edx 和 ecx 中，设为 node *p 和 int num。test 指令的目的是检查当前节点是否存在（如果不存在则地址为 0，相当于 NULL），不存在则返回 - 1。

asm 
1
2
3

 8048f94: 8b 1a                 mov    (%edx),%ebx
 8048f96: 39 cb                 cmp    %ecx,%ebx
 8048f98: 7e 13                 jle    8048fad <fun7+0x29>

这段代码比较了 num 和 p->val，如果前者不小于后者，则跳转。首先来看 num <p->val 的情况。

asm 
1
2
3
4
5
6

 8048f9a: 89 4c 24 04           mov    %ecx,0x4(%esp)
 8048f9e: 8b 42 04              mov    0x4(%edx),%eax
 8048fa1: 89 04 24              mov    %eax,(%esp)
 8048fa4: e8 db ff ff ff        call   8048f84 <fun7>
 8048fa9: 01 c0                 add    %eax,%eax
 8048fab: eb 23                 jmp    8048fd0 <fun7+0x4c>

这部分调用了 fun7(p->left, num)，然后把返回值乘以 2 再返回。

asm 
1
2
3

 8048fad: b8 00 00 00 00        mov    $0x0,%eax
 8048fb2: 39 cb                 cmp    %ecx,%ebx
 8048fb4: 74 1a                 je     8048fd0 <fun7+0x4c>

继续比较 num 和 p->val，如果相等，返回 0。那么剩下的就是 num > p->val 的情况。

asm 
1
2
3
4
5
6

 8048fb6: 89 4c 24 04           mov    %ecx,0x4(%esp)
 8048fba: 8b 42 08              mov    0x8(%edx),%eax
 8048fbd: 89 04 24              mov    %eax,(%esp)
 8048fc0: e8 bf ff ff ff        call   8048f84 <fun7>
 8048fc5: 8d 44 00 01           lea    0x1(%eax,%eax,1),%eax
 8048fc9: eb 05                 jmp    8048fd0 <fun7+0x4c>

调用 func7(p->right, num)，然后把返回值乘 2 加 1 再返回。

可以看到，func7 所做的就是 “搜索” 的操作，我们所期望的返回值 5 就是根据输入数和节点的关系，通过一层一层递归中的运算构建出来的。借此，我们可以反推 num 在树中的位置。

首先 num 肯定存在于树中，因为如果不存在，必会返回 - 1，无法通过计算得到。很容易能够得到唯一解：$5=((0 \times 2+1) \times 2) \times 2+1$，也就是从根节点出发，路径为右、左、右，得出输入的值为 0x2f，即 47。

在对应的位置输入 47（我这里直接暴力改寄存器和内存了），Secret Phase 也就被解决了。

Secret Phase 解决

如果你看到这里的话，那我大概可以祝贺你成功解开了 Bomb Lab。如果给予足够的时间，Bomb Lab 是可以带来很多乐趣的，可以说是一个非常巧妙的实验。从一片汇编代码中挖出数据结构再到理清逻辑，是非常有成就感的事情。如果你想对 Bomb Lab 有更多的研究，可以查看下面的 GitHub 仓库，里面疑似是 Bomb Lab 的指导者源码，用于生成炸弹。但如果你还没做完，建议不要进入查看，毕竟正推就没什么意思了，你说呢？

kiliczsh/cmu-binary-bomb