CSAPP-Lab2-BombLab_jmp *0x402470(,%rax,8)

实验主页

Tips：实验前最好先把 bomp 反汇编到一个文件中，方便在调试时查看

开启调试器，以汇编的形式展示程序：

$ gdb --silent bomb
Reading symbols from bomb...
(gdb) layout asm
1
2
3

phase_1

第一个炸弹是一道开胃小菜，很容易解除，下面就直接给出解法了：

首先通过阅读源程序的提示，我们找到了第一个炸弹的入口函数 phase_1：

注意上一条mov指令，它将 $rax 赋给第一参数寄存器 %rdi，而 %rax 存放的明显是上一个函数 read_line 的返回值——指向读入字符串的指针

下面在这个函数处打断点，并运行，进入这个函数：

在这里将一个常量 0x402400 赋给了 %rsi（第二参数寄存器），然后执行了判断字符串是否相等函数

继续浏览下面的汇编代码，后面程序的行为就是：如果 strings_not_euqal 返回非零值，炸弹爆炸

所以解除这个炸弹的方法就是：输入一个与 0x402400 处存储的字符串相同的字符串，下面查看这块内存存储的字符串：

所以我们需要输入的字符串就是：

"Border relations with Canada have never been better."
1

至此，第一个炸弹解除

---

phase_2

第二个炸弹明显棘手一些，但是如果我们足够冷静，细心，一步步地列出程序在执行完成每一条指令后寄存器组和栈的状态，还是能够正确地分析出来的。下面给出一点提示，你可以看完提示后再去考虑这个炸弹如何解除

提示1：这个炸弹的考点是数组和循环，以及函数调用时的参数的传递

如果你觉得这个提示不够劲爆的话，下面再给出一个提示。当然，如果你不想看到这个提示，别点下面的链接就好了：

这个提示是关于一个函数的用法说明，我相信你会需要查阅这个内容的

ok，下面我们开始拆除第二个炸弹。先来看看 phase_2 的实现：

0000000000400efc <phase_2>:
  400efc:	55                   	push   %rbp
  400efd:	53                   	push   %rbx
  400efe:	48 83 ec 28          	sub    $0x28,%rsp
  400f02:	48 89 e6             	mov    %rsp,%rsi
  400f05:	e8 52 05 00 00       	call   40145c <read_six_numbers>
  
  400f0a:	83 3c 24 01          	cmpl   $0x1,(%rsp)
  400f0e:	74 20                	je     400f30 <phase_2+0x34>
  400f10:	e8 25 05 00 00       	call   40143a <explode_bomb>
  400f15:	eb 19                	jmp    400f30 <phase_2+0x34>
  400f17:	8b 43 fc             	mov    -0x4(%rbx),%eax
  400f1a:	01 c0                	add    %eax,%eax
  400f1c:	39 03                	cmp    %eax,(%rbx)
  400f1e:	74 05                	je     400f25 <phase_2+0x29>
  400f20:	e8 15 05 00 00       	call   40143a <explode_bomb>
  400f25:	48 83 c3 04          	add    $0x4,%rbx
  400f29:	48 39 eb             	cmp    %rbp,%rbx
  400f2c:	75 e9                	jne    400f17 <phase_2+0x1b>
  400f2e:	eb 0c                	jmp    400f3c <phase_2+0x40>
  400f30:	48 8d 5c 24 04       	lea    0x4(%rsp),%rbx
  400f35:	48 8d 6c 24 18       	lea    0x18(%rsp),%rbp
  400f3a:	eb db                	jmp    400f17 <phase_2+0x1b>
  400f3c:	48 83 c4 28          	add    $0x28,%rsp
  400f40:	5b                   	pop    %rbx
  400f41:	5d                   	pop    %rbp
  400f42:	c3                   	ret    
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

首先是两个无聊的压栈操作，然后将栈指针 %rsp 减去 0x28开辟一块空间（挺大的？）

比较关键的是它在里面调用了一个函数 read_six_numbers，这个名字启发我们或许我们需要输入六个数字来拆除炸弹。涉及到函数调用时，我们先考虑传递给它的参数是什么：

• 第一参数寄存器 %rdi：没有变，我们回到 main 函数中查看，在调用 phase_2 之前，执行了 mov %rax,%rdi 语句：将我们输入的字符串的指针赋给了 %rdi
• 第二参数寄存器 %rsi：存储了当前栈指针的值

后面的参数寄存器没有用到

执行完这个函数后，比对栈顶的值是否=1，若等于则跳转到 0x400f30 继续执行，否则炸弹爆炸。看来我们需要保证栈顶的值=1，而且这个值是32位的，因为 cmpl 有 l 后缀

phase_2 我们就先看到这里，接下来看看 read_six_numbers 怎么实现：

000000000040145c <read_six_numbers>:
  40145c:	48 83 ec 18          	sub    $0x18,%rsp
  401460:	48 89 f2             	mov    %rsi,%rdx		# 指向调用 read_six_numbers() 之前栈顶
  401463:	48 8d 4e 04          	lea    0x4(%rsi),%rcx	# 第4参数寄存器，指向 %rsi + 4
  401467:	48 8d 46 14          	lea    0x14(%rsi),%rax
  40146b:	48 89 44 24 08       	mov    %rax,0x8(%rsp)	# 第7参数，指向 %rsi + 20
  401470:	48 8d 46 10          	lea    0x10(%rsi),%rax
  401474:	48 89 04 24          	mov    %rax,(%rsp)		# 第8参数，指向 %rsi + 16
  401478:	4c 8d 4e 0c          	lea    0xc(%rsi),%r9	# 第6参数寄存器，指向 %rsi + 12
  40147c:	4c 8d 46 08          	lea    0x8(%rsi),%r8	# 第5参数寄存器，指向 %rsi + 8
  401480:	be c3 25 40 00       	mov    $0x4025c3,%esi	# 第2参数寄存器，指向格式字符串常量
  401485:	b8 00 00 00 00       	mov    $0x0,%eax
  40148a:	e8 61 f7 ff ff       	call   400bf0 <__isoc99_sscanf@plt>
  40148f:	83 f8 05             	cmp    $0x5,%eax
  401492:	7f 05                	jg     401499 <read_six_numbers+0x3d>
  401494:	e8 a1 ff ff ff       	call   40143a <explode_bomb>
  401499:	48 83 c4 18          	add    $0x18,%rsp
  40149d:	c3                   	ret    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

前面都是一些传送指令，修改一些寄存器和内存的值，应该是为了函数调用准备参数

关键点是 call 400bf0 <__isoc99_sscanf@plt> 的指令，它调用了库中的 sscanf() 函数，这个函数的原型如下：

int sscanf(const char *str, const char *format, ...)
1

它的原理与 scanf() 函数类似，一种调用示例如下：

sscanf(str_buf, "%s %s %d %d", weekday, month, &day, &year );
1

第一个参数是源字符串，第二个参数是一个格式字符串常量，后面的不定参数是要保存的目的地址。围绕这个函数，我们看看传递给它的参数：

• 第一参数寄存器 %rdi：一直没有变，还是指向我们输入的字符串
• 第二参数寄存器 %rsi： 被赋予一个常量 $0x4025c3，这应该是格式字符串常量的地址
• 第三参数寄存器 %rdx：回到 phase_2 函数中查看，mov %rsp,%rsi 将栈顶指针赋给了 %rsi，然后在 read_six_numbers() 函数中， mov %rsi,%rdx 又将原来的栈顶指针赋给了 %rdx。所以，第三参数寄存器指向了一块栈上的内存，具体地，是在调用 read_six_numbers() 函数之前的栈顶（这个位置的下一个数据就是 read_six_numbers() 的返回地址）
• 第四参数寄存器 %rcx：指向 %rsi + 4 的位置
• 第五参数寄存器 %r8：指向 %rsi + 8 的位置
• 第六参数寄存器 %r9：指向 %rsi + 12 的位置
• 第七参数：此时已经超过了寄存器能保存的参数上限，剩下的参数要保存在 read_six_numbers() 函数的栈帧中，而且参数是逆向压栈的（虽然这里使用了mov操作栈的内存空间）。所以第七参数被保存在 %rsp + 8 的位置，它的内容指向 %rsi + 20 的内存位置。也就是下面这两行代码：

  401467:	48 8d 46 14          	lea    0x14(%rsi),%rax
  40146b:	48 89 44 24 08       	mov    %rax,0x8(%rsp)	# 第7参数，指向 %rsi + 20
1
2

• 第八参数：第八参数被保存在 %rsp + 16的位置，它的内容指向 %rsi + 16 的内存位置。也就是下面这两行代码：

  401470:	48 8d 46 10          	lea    0x10(%rsi),%rax
  401474:	48 89 04 24          	mov    %rax,(%rsp)		# 第8参数，指向 %rsi + 16
1
2

注意在函数返回后，它检查返回值是否>5：若大于，则跳转到 401499 继续执行；否则炸弹爆炸。这也印证我们要输入的内容是6个数字

根据上面我们分析得到的线索，先输入“1 2 3 4 5 6”是一个不错的尝试

下面让程序运行起来，一边运行一边记录寄存器组和栈的状态变化：

我已经把第一个字符串写入了 feedin 文件，这样只需在程序运行时指明参数即可，避免了重复输入字符串

注意如何在gdb中加入命令行参数：

(gdb) run argv
1

进入到 phase_2 函数之后，在执行 call 40145c <read_six_numbers> 之前，程序的状态如下：

注意此时 %rsi 和 %rsp 都指向栈顶位置，下一步 call 40145c <read_six_numbers> 时，根据 call 指令的语义，会将返回地址（call的下一条指令的地址）压栈

进入到 read_six_numbers 后，程序的状态如下：

此时 %rsp 指向的是返回地址，函数 phase_2 的栈帧到这里就结束了

再次强调这时 %rsi 的值是 e090（实际上是 0x7fffffffe090，我简写了），指向了函数 phase_2 栈帧中紧挨着返回地址的那个四字，下面将会看到这个地址很重要

这个函数的核心在于 sscanf() 调用，前面的操作都是一系列的参数准备，我们在上面已经分析过了，下面直接运行到 call 400bf0 <__isoc99_sscanf@plt>：

可见，这个函数的前2个参数分别指向了我们输入的字符串和格式字符串；后6个参数都是地址（指针），分别指向栈上的6个int型数据，这正好印证了 read_six_numbers() 的功能：读入六个数字，它将会把这6个数字保存在 e090 开始的数组中

这个分析过程也启发我们：C程序的核心在于函数，同样的，在汇编层面，也要以函数调用为突破口，分析它的参数和返回值

执行完 sscanf() 函数后，程序会比对返回值是否>5。若返回值小于等于5，则炸弹爆炸。我们检查 %rax 的值，为6，因为我们输入了6个数字

所以 read_six_numbers() 安全地返回，没有引爆炸弹。下面继续分析 phase_2() 函数：

从 read_six_numbers() 函数中退出后，%rsp 指向e090的位置，程序会比对 (%rsp) 的值是否为1。若否，则炸弹爆炸

我们查看这个位置的内存：

刚好为1（因为我们输入的第一个数就是1），所以我们可以“安全地”向下执行：

在jump之前，主要寄存器的的指向如上所示。下面执行jump继续执行：

这时程序将 %rbx - 4 处的值取到 %rax。可知，这个值就是 e090 处存储的 1 。接下来将其2倍，再与 %rbx 处的值比对，若不相等，则爆炸。所以 %rbx 处的值应为2。回忆我们的输入，%rbx 处的值正好为2，所以程序继续执行：

此时，%rbx 加4后指向 e098，不等于 %rbp，程序继续跳转：

程序循环执行刚才的逻辑：将 %rbx - 4 处的值取到 %rax，再将这个值2倍后比对是否与 %rbx 处的值相同。

• 若相同，则将 %rbx + 4 后判断其是否等于 %rbp（相当于一个边界）

  • 若不等，则继续循环
  • 若相等，则跳出循环，进而跳出函数

• 若不同，则引爆炸弹

将上面的逻辑用高级语言表达：

while (rbx != rbp) {
	eax = M[rbx - 4] * 2;
	if (eax != M[rbx]) {
		explode_blob();
	} else {
		rbx += 4;
	}
}
1
2
3
4
5
6
7
8

再次判断时，发现 %rbx 处的值=3，并不与 %rax 的值相等。为了不让炸弹爆炸，方便我们继续调试，我们可以通过 set var 指令将 (%rbx) 处的值修改为4。程序就可以继续执行：

再次执行到 cmp 指令时同理，将 (%rbx) 处的值修改为8，程序继续执行：

将 (%rbx) 处的值修改为16，程序继续执行：

将 %rbx 处的值修改为32，程序继续执行：

可见，phase_2() 函数终于执行完了，我们也得到了要输入的6个数字：1, 2, 4, 8, 16, 32

至此，第二个炸弹被拆除，我们要输入的字符串是：

"1 2 4 8 16 32"
1

---

phase_3

将 phase2 的破解结果写入 feedin 文件中，重新调试：

有了第2个炸弹的拆解经验，第3个炸弹就显得小case了。如上图所示，我们先试着输入字符串“abc”，然后让程序继续运行：

程序再次调用了 sscanf() 函数，第1参数寄存器 %rdi 仍然指向是我们输入的字符串；第2参数寄存器指向了一个格式字符串常量，查看得知这个格式串为：

"%d %d"
1

于是，我们得知需要输入两个数字来破解第三个炸弹。我们尝试输入的“abc”是错的，重新调试并输入。这次我们输入"1 2"：

注意在调用 sscanf() 之前，第3参数寄存器和第4参数寄存器分别指向 e0bc 和 e0b8，也就是栈顶下面的两个双字，如下图所示：

sscanf() 会将读到的2个整数保存在这两个位置

我们继续向下执行，程序检查返回值，若其小于等于1，则引爆炸弹。这也印证了我们需要输入两个整数

然后，程序会比对 e0b8 处的值是否大于7，若大于，则引爆炸弹。所以，如果你尝试的输入和我不一样，第一个数字大于7的话，现在需要修改一下

接着，程序来到了一条间接跳转指令 jmp *0x402470(,%rax,8)。显然，我们来到了一个 switch-case 语句结构。程序将 %rsp + 8 = e0b8 的处的值赋给 %rax，然后 %rax 充当跳转表的索引值

查看 0x402470 处的跳转表，发现这里有8个表项（每个表项是一个长度为4字的跳转地址）

由于我们输入的第一个数字为1，所以会跳转到第1个表项指向的地址，也就是0x400fb9

到了这里，一切似乎都明朗了起来：程序将 %rax 赋予 0x137，然后比对其是否与 e0bc 处的值相等，若相等，则安全退出函数，否则引爆炸弹。所以我们需要保证 eobc 处的值为 0x137。但是回想我们的输入，这个位置保存的值是2，所以我们需要将其修改为 0x137，如下图所示：

修改好后，我们拆除了第3个炸弹。0x137 = 311，所以我们需要输入的字符串是：

"1 311"
1

当然，还存在其他的输入能够破解炸弹，这里就不一一列举了

---

phase_4

这次我们先看一看 phase_4() 的代码：

000000000040100c <phase_4>:
  40100c:	48 83 ec 18          	sub    $0x18,%rsp
  401010:	48 8d 4c 24 0c       	lea    0xc(%rsp),%rcx
  401015:	48 8d 54 24 08       	lea    0x8(%rsp),%rdx
  40101a:	be cf 25 40 00       	mov    $0x4025cf,%esi
  40101f:	b8 00 00 00 00       	mov    $0x0,%eax
  401024:	e8 c7 fb ff ff       	call   400bf0 <__isoc99_sscanf@plt>
  401029:	83 f8 02             	cmp    $0x2,%eax
  40102c:	75 07                	jne    401035 <phase_4+0x29>
  40102e:	83 7c 24 08 0e       	cmpl   $0xe,0x8(%rsp)
  401033:	76 05                	jbe    40103a <phase_4+0x2e>
  401035:	e8 00 04 00 00       	call   40143a <explode_bomb>
  40103a:	ba 0e 00 00 00       	mov    $0xe,%edx
  40103f:	be 00 00 00 00       	mov    $0x0,%esi
  401044:	8b 7c 24 08          	mov    0x8(%rsp),%edi
  401048:	e8 81 ff ff ff       	call   400fce <func4>
  40104d:	85 c0                	test   %eax,%eax
  40104f:	75 07                	jne    401058 <phase_4+0x4c>
  401051:	83 7c 24 0c 00       	cmpl   $0x0,0xc(%rsp)
  401056:	74 05                	je     40105d <phase_4+0x51>
  401058:	e8 dd 03 00 00       	call   40143a <explode_bomb>
  40105d:	48 83 c4 18          	add    $0x18,%rsp
  401061:	c3                   	ret    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

分析知，与 phase_3 很类似，我们也需要输入两个数字，否则会引爆炸弹。

而且根据指令 cmpl $0xe,0x8(%rsp)，输入的第一个数不能超过14

接下来，程序调用了一个名字叫 func4 的函数，为它准备的参数如下：

• 第一参数寄存器 %edi：是我们输入的第一个数
• 第二参数寄存器 %esi：0
• 第三参数寄存器 %edx：14

所以 func4 的调用如下：

int ret = func4(first_num, 0, 14);
1

接下来，程序检查返回值，若非0，则引爆炸弹。再检查我们输入的第二个数，若非0，则引爆炸弹，这说明我们输入的第二个数一定是0

根据上述分析，我们尝试输入“1 0”：

我们安全地到达了 call 400fce <func4>指令，下面分析这个函数（L2和F2这两个标签是我添加的）：

0000000000400fce <func4>:
  400fce:	48 83 ec 08          	sub    $0x8,%rsp
  400fd2:	89 d0                	mov    %edx,%eax
  400fd4:	29 f0                	sub    %esi,%eax

  400fd6:	89 c1                	mov    %eax,%ecx
  400fd8:	c1 e9 1f             	shr    $0x1f,%ecx
  400fdb:	01 c8                	add    %ecx,%eax
  400fdd:	d1 f8                	sar    %eax

  400fdf:	8d 0c 30             	lea    (%rax,%rsi,1),%ecx
  
  400fe2:	39 f9                	cmp    %edi,%ecx
  400fe4:	7e 0c                	jle    400ff2 <func4+0x24>
  400fe6:	8d 51 ff             	lea    -0x1(%rcx),%edx
  400fe9:	e8 e0 ff ff ff       	call   400fce <func4>

  400fee:	01 c0                	add    %eax,%eax
  400ff0:	eb 15                	jmp    401007 <func4+0x39>

  F2:
  400ff2:	b8 00 00 00 00       	mov    $0x0,%eax
  400ff7:	39 f9                	cmp    %edi,%ecx
  400ff9:	7d 0c                	jge    401007 <func4+0x39>

  400ffb:	8d 71 01             	lea    0x1(%rcx),%esi
  400ffe:	e8 cb ff ff ff       	call   400fce <func4>
  401003:	8d 44 00 01          	lea    0x1(%rax,%rax,1),%eax

  L2:
  401007:	48 83 c4 08          	add    $0x8,%rsp
  40100b:	c3                   	ret    
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

根据其中的 call 400fce <func4> 指令，这显然是一个递归函数。我们尝试将其逆向到C的源代码（保证函数在语义上是等价的）：

int func4(int edi, int esi, int edx) {
    int res = edx - esi;
    unsigned int ecx = res >> 31;
    res += ecx;
    res >>= 1;

    ecx = res + esi;
    if (ecx <= edi) {
        goto F2;
    } else {
        edx = ecx - 1;
        res = func4(edi, esi, edx);
        res *= 2;
        goto L2;
    }

F2:
    res = 0;
    if (ecx >= edi) {
        goto L2;
    } else {
        esi = ecx + 1;
        res = func4(edi, esi, edx);
        res = res * 2 + 1;
    }
    
L2:
    return res;
}
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

继续做逆向，去除程序中的goto语句：

int func4(int edi, int esi, int edx) {
    int res = edx - esi;
    unsigned int ecx = res >> 31;
    res += ecx;
    res >>= 1;

    ecx = res + esi;
    if (ecx <= edi) {
        if (ecx >= edi) {
            return 0;
        } else {
            return 2 * func4(edi, ecx + 1, edx) + 1;
        }
    } else {
        return 2 * func4(edi, esi, ecx - 1);
    }    
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

将2层if简化为1层if，并调整中间变量：

int func4(int edi, int esi, int edx) {
    unsigned int res = edx - esi;
    res = res + (res >> 31);
    res >>= 1;

    int ecx = res + esi;
    if (ecx == edi) {
        return 0;
    } else if (ecx < edi) {
        return 2 * func4(edi, ecx + 1, edx) + 1;
    } else {
        return 2 * func4(edi, esi, ecx - 1);
    }
   
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

到了这里，一种非常tricky的破解方式是：不管这个函数的功能是什么，直接看他第一个参数取何值时返回0即可。因为在 phase_4 中会检查 func4 的返回值，若非0，则引爆炸弹。而初始调用时第二个和第三个参数是固定的，第一个参数的取值范围也是在0到14之间，这很容易列举出来：

#include <stdio.h>

int func4(int, int, int);

int main() {
    for(int i = 0; i < 15; ++i) {
        printf("i = %d, res = %d\n", i, func4(i, 0, 14));
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10

运行结果：

daniel@u22:~/csapp/labs/bomb$ ./main
i = 0, res = 0
i = 1, res = 0
i = 2, res = 4
i = 3, res = 0
i = 4, res = 2
i = 5, res = 2
i = 6, res = 6
i = 7, res = 0
i = 8, res = 1
i = 9, res = 1
i = 10, res = 5
i = 11, res = 1
i = 12, res = 3
i = 13, res = 3
i = 14, res = 7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

可见，第一个数输入 0, 1, 3, 7 这些值之一，都能破解炸弹。事实上，我们作为尝试输入的“1 0”正好破解了炸弹，nice try

ok，那么这个函数的功能是什么呢？我也不知道（原谅我数学很烂），或许我做二周目的时候会再重新思考一下这个问题

至此，第四个炸弹破解完成，我们需要输入的字符串是：

"7 0"
1

---

phase_5

先分析一波汇编代码，为我们的尝试找找方向：

0000000000401062 <phase_5>:
  # 放置canary值
  401062:	53                   	push   %rbx
  401063:	48 83 ec 20          	sub    $0x20,%rsp
  401067:	48 89 fb             	mov    %rdi,%rbx
  40106a:	64 48 8b 04 25 28 00 	mov    %fs:0x28,%rax
  401071:	00 00 
  401073:	48 89 44 24 18       	mov    %rax,0x18(%rsp)
  
  401078:	31 c0                	xor    %eax,%eax
  40107a:	e8 9c 02 00 00       	call   40131b <string_length>
  40107f:	83 f8 06             	cmp    $0x6,%eax
  401082:	74 4e                	je     4010d2 <phase_5+0x70>	#必须返回6
  401084:	e8 b1 03 00 00       	call   40143a <explode_bomb>
  
  401089:	eb 47                	jmp    4010d2 <phase_5+0x70>
  40108b:	0f b6 0c 03          	movzbl (%rbx,%rax,1),%ecx
  40108f:	88 0c 24             	mov    %cl,(%rsp)
  401092:	48 8b 14 24          	mov    (%rsp),%rdx
  401096:	83 e2 0f             	and    $0xf,%edx
  401099:	0f b6 92 b0 24 40 00 	movzbl 0x4024b0(%rdx),%edx
  4010a0:	88 54 04 10          	mov    %dl,0x10(%rsp,%rax,1)
  4010a4:	48 83 c0 01          	add    $0x1,%rax
  4010a8:	48 83 f8 06          	cmp    $0x6,%rax
  4010ac:	75 dd                	jne    40108b <phase_5+0x29>
  4010ae:	c6 44 24 16 00       	movb   $0x0,0x16(%rsp)
  4010b3:	be 5e 24 40 00       	mov    $0x40245e,%esi
  4010b8:	48 8d 7c 24 10       	lea    0x10(%rsp),%rdi
  4010bd:	e8 76 02 00 00       	call   401338 <strings_not_equal>
  4010c2:	85 c0                	test   %eax,%eax
  4010c4:	74 13                	je     4010d9 <phase_5+0x77>	# 必须返回0
  4010c6:	e8 6f 03 00 00       	call   40143a <explode_bomb>
  4010cb:	0f 1f 44 00 00       	nopl   0x0(%rax,%rax,1)
  4010d0:	eb 07                	jmp    4010d9 <phase_5+0x77>
  
  4010d2:	b8 00 00 00 00       	mov    $0x0,%eax
  4010d7:	eb b2                	jmp    40108b <phase_5+0x29>
  # 检查canary值并退出
  4010d9:	48 8b 44 24 18       	mov    0x18(%rsp),%rax
  4010de:	64 48 33 04 25 28 00 	xor    %fs:0x28,%rax
  4010e5:	00 00 
  4010e7:	74 05                	je     4010ee <phase_5+0x8c>
  4010e9:	e8 42 fa ff ff       	call   400b30 <__stack_chk_fail@plt>
  4010ee:	48 83 c4 20          	add    $0x20,%rsp
  4010f2:	5b                   	pop    %rbx
  4010f3:	c3                   	ret    
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
42
43
44
45
46

注意到 mov %fs:0x28,%rax，说明这段程序使用了“金丝雀”栈保护机制，具体的内容请见课本的第199页

简单来说这是一种防御攻击的手段：为了防止攻击者随意修改栈上的内容（比如修改返回地址，使得函数返回时跳转到malware的地址），我们将一个特定的值存入栈中，这个值称为“金丝雀值”(canary)，在函数返回前检查这个值有没有被修改过：若是，则 call 400b30 <__stack_chk_fail@plt>，程序异常退出；否则函数安全返回

至于为什么叫“金丝雀值”，因为历史上曾今用这种鸟察觉煤矿中的有毒气体（鸟类爱好者震怒）

所以程序的核心只在 401078 到 4010d7 之间

根据下面这段程序，我们必须输入一个长度为6的字符串：

  401078:	31 c0                	xor    %eax,%eax
  40107a:	e8 9c 02 00 00       	call   40131b <string_length>
  40107f:	83 f8 06             	cmp    $0x6,%eax
  401082:	74 4e                	je     4010d2 <phase_5+0x70>	#必须返回6
  401084:	e8 b1 03 00 00       	call   40143a <explode_bomb>
1
2
3
4
5

不妨尝试一下“123456”：

下面进入这个函数调试：

可见，%rdi 仍然指向我们输入的字符串，下面继续执行：

接下来程序将会跳转到 0x40108b 的位置，注意这段代码是一个循环：

40108b:	0f b6 0c 03          	movzbl (%rbx,%rax,1),%ecx
  40108f:	88 0c 24             	mov    %cl,(%rsp)
  401092:	48 8b 14 24          	mov    (%rsp),%rdx
  401096:	83 e2 0f             	and    $0xf,%edx
  401099:	0f b6 92 b0 24 40 00 	movzbl 0x4024b0(%rdx),%edx
  4010a0:	88 54 04 10          	mov    %dl,0x10(%rsp,%rax,1)
  4010a4:	48 83 c0 01          	add    $0x1,%rax
  4010a8:	48 83 f8 06          	cmp    $0x6,%rax
  4010ac:	75 dd                	jne    40108b <phase_5+0x29>
1
2
3
4
5
6
7
8
9

下面一边运行程序一边分析这个循环的功能：

可见，movzbl (%rbx,%rax,1),%ecx 首先将我们输入的第一个字节(0x31)存入 %ecx

接下来，执行：

  40108f:	88 0c 24             	mov    %cl,(%rsp)
  401092:	48 8b 14 24          	mov    (%rsp),%rdx
  401096:	83 e2 0f             	and    $0xf,%edx
1
2
3

将 %cl 的值传到栈顶的第一个字节，再将其传入 %rdx，接着再取 %edx 的最低4位，由于 0x31 & 0xf = 0x01，所以此时 %edx的值为1

在执行下一条 movzbl 0x4024b0(%rdx),%edx 指令之前，我们先看看这个地方存的是什么：

这是一个数组，里面具体的值我们先不管

movzbl 0x4024b0(%rdx),%edx 会将上面的数组的第 %rdx 项（一个字节）读入 %edx，然后 mov %dl,0x10(%rsp,%rax,1) 又会将这个字节写入内存的 e0c0 + %rax处。现在，%rdx 的值为1，所以程序会将数组的第1项（0x61）写入%edx，再将这个字节写入内存的 e0c0 位置，如上图所示

接下来，程序将 %rax 的值加1，若其不等于6则跳转到 0x40108b 继续循环

如果你继续执行几次，你就能总结出这个循环的功能了：它实现了一个哈希表，每次读入一个我们输入的字节，取其低4位，将这个值作为key，去 0x4024b0 处的哈希表取value，然后将这个value写入 0x10(%rsp,%rax,1)，一共执行6次，这6个字节存入了以 e0c0 为起始地址的字节数组

继续执行，直到跳出循环，我们查看 e0c0 的内容，发现其正是哈希表中对应的值，印证了我们的推断

接下来程序又调用了 strings_not_equal 函数，我们检查传递给它的参数：

• %rdi 指向栈上的字符数组，它由刚才的循环过程构造
• %rsi 指向一个字符串常量，内容如上图红圈所示，是"flyers"

若返回值非0，则引爆炸弹

现在我们清楚了，我们需要保证循环构造出来的字符串的内容保持与"flyers"一致。所以我们需要根据哈希表反向推断为了构造这个字符串需要输入什么：

• 0x66 is number 9, so the first letter we need to input is 0x39, which is ‘9’ in ascii coding table
• 0x6c is number 15, so the 2nd letter we need to input is 0x3f, which is ‘?’ in ascii coding table
• 0x79 is number 14, so the 3ed letter we need to input is 0x3e, which is ‘>’ in ascii coding table
• 0x65 is number 5, so the 4th letter we need to input is 0x35, which is ‘5’ in ascii coding table
• 0x72 is number 6, so the 5th letter we need to input is 0x36, which is ‘6’ in ascii coding table
• 0x73 is number 7, so the 6th letter we need to input is 0x37, which is ‘7’ in ascii coding table

至此，第5个炸弹已被拆除，需要输入的字符串是

"9?>567"
1

当然，也会存在其他的值，只要保证每个字符的低4位满足要求即可

---

phase_6

这个函数很长，我们分段来分析，首先是一系列压栈保护寄存器，然后调用 read_six_numbers 函数：

00000000004010f4 <phase_6>:
  4010f4:	41 56                	push   %r14
  4010f6:	41 55                	push   %r13
  4010f8:	41 54                	push   %r12
  4010fa:	55                   	push   %rbp
  4010fb:	53                   	push   %rbx
  4010fc:	48 83 ec 50          	sub    $0x50,%rsp
  401100:	49 89 e5             	mov    %rsp,%r13
  401103:	48 89 e6             	mov    %rsp,%rsi
  401106:	e8 51 03 00 00       	call   40145c <read_six_numbers>
1
2
3
4
5
6
7
8
9
10

执行完 read_six_numbers() 后，函数的栈帧状态如下图所示（我们输入“1 2 3 4 5 6”作为尝试）：

可见，我们输入的6个数被保存在栈顶的位置(e060)，每个数字占4个字节。接下来分析可知，程序进入了一段二重循环：

  40110b:	49 89 e6             	mov    %rsp,%r14
  40110e:	41 bc 00 00 00 00    	mov    $0x0,%r12d

loop1_begin
  401114:	4c 89 ed             	mov    %r13,%rbp
  401117:	41 8b 45 00          	mov    0x0(%r13),%eax
  40111b:	83 e8 01             	sub    $0x1,%eax
  40111e:	83 f8 05             	cmp    $0x5,%eax
  401121:	76 05                	jbe    401128 <phase_6+0x34>
  401123:	e8 12 03 00 00       	call   40143a <explode_bomb>

  401128:	41 83 c4 01          	add    $0x1,%r12d
  40112c:	41 83 fc 06          	cmp    $0x6,%r12d
  401130:	74 21                	je     401153 <phase_6+0x5f>
  401132:	44 89 e3             	mov    %r12d,%ebx
loop2_bein
  401135:	48 63 c3             	movslq %ebx,%rax
  401138:	8b 04 84             	mov    (%rsp,%rax,4),%eax
  40113b:	39 45 00             	cmp    %eax,0x0(%rbp)
  40113e:	75 05                	jne    401145 <phase_6+0x51>
  401140:	e8 f5 02 00 00       	call   40143a <explode_bomb>
  
  401145:	83 c3 01             	add    $0x1,%ebx
  401148:	83 fb 05             	cmp    $0x5,%ebx
  40114b:	7e e8                	jle    401135 <phase_6+0x41>
loop2_end
  40114d:	49 83 c5 04          	add    $0x4,%r13
  401151:	eb c1                	jmp    401114 <phase_6+0x20>
loop1_end
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

我们将其转化为C代码：

    int A[6] = {1,2,3,4,5,6}; //A = 0x7fffffffe060 = %rsp;
    long r13, r14, rbp;		//long = int*
    int r12d, eax, ebx;
    r13 = r14 = A;
    r12d = 0;

L114:
    rbp = r13;
    eax = *r13;
    if (--eax > 5) explode_bomb();
    if (++r12d == 6) goto L153;
    ebx = r12d;

L135:
    eax = ebx;
    eax = A[eax];
    if (eax == *rbp) explode_bomb();
    if (++ebx <= 5) goto L135;

    r13++;
    goto L114;

L153:
	...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

将其调整为两层循环：

    int A[6] = {1,2,3,4,5,6}; //A = 0x7fffffffe060 = %rsp;
    long r13, r14, rbp;
    int r12d, eax, ebx;
    r13 = r14 = A;
    r12d = 0;
   	//检查是否每个数字都不超过6（必须为正数），且都不重复
    for (; ;) {
        if (*r13 - 1 > 5) explode_bomb();
        if (++r12d == 6) break;
        for (ebx = r12d; ebx < 6; ++ebx) {
            eax = A[ebx];
            if (eax == *r13) explode_bomb();
        }
        r13++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

分析这个循环的功能可知，它检查了数组A（栈顶的6个输入数据）是否存在重复元素（若存在则爆炸），同时每个数字都不能超过6。注意到下面这段代码：

  40111b:	83 e8 01             	sub    $0x1,%eax
  40111e:	83 f8 05             	cmp    $0x5,%eax
  401121:	76 05                	jbe    401128 <phase_6+0x34>
  401123:	e8 12 03 00 00       	call   40143a <explode_bomb>
1
2
3
4

在判断每个元素是否超过6时，采用的方式是减去1再与5做比较，同时注意程序用的是无符号数的比较，这也就意味着如果输入负数（在无符号数中是一个很大的整数），程序将不会跳转，从而引爆炸弹。

于是我们推断出输入数据只能是 1 2 3 4 5 6，但是这些数字的顺序目前是未知的

下面的代码又是一段循环：

  401153:	48 8d 74 24 18       	lea    0x18(%rsp),%rsi
  401158:	4c 89 f0             	mov    %r14,%rax
  40115b:	b9 07 00 00 00       	mov    $0x7,%ecx

loop3_begin
  401160:	89 ca                	mov    %ecx,%edx
  401162:	2b 10                	sub    (%rax),%edx
  401164:	89 10                	mov    %edx,(%rax)
  401166:	48 83 c0 04          	add    $0x4,%rax
  40116a:	48 39 f0             	cmp    %rsi,%rax
  40116d:	75 f1                	jne    401160 <phase_6+0x6c>
loop3_end
1
2
3
4
5
6
7
8
9
10
11
12

这段代码翻译成C代码很简单：

    rsi = 0x7fffffffe078;
    rax = 0x7fffffffe060;
    ecx = 7;

L160:
    int edx = ecx - *rax;
    *rax = edx;
    rax++;
    if (rsi != rax) goto L160;
1
2
3
4
5
6
7
8
9

简化一下：

    rsi = 0x7fffffffe078;
    rax = 0x7fffffffe060;
L160:
    *rax = 7 - *rax;
    rax++;
    if (rsi != rax) goto L160;
1
2
3
4
5
6

我想，不必再转化为循环了。很明显，这段循环将数组中的每一个元素取出，求其对7的补，然后写回原位置

执行完循环后，原数组的每个值变成了相对于7的补。继续分析下面的代码：

  40116f:	be 00 00 00 00       	mov    $0x0,%esi
  401174:	eb 21                	jmp    401197 <phase_6+0xa3>
L176:
  401176:	48 8b 52 08          	mov    0x8(%rdx),%rdx
  40117a:	83 c0 01             	add    $0x1,%eax
  40117d:	39 c8                	cmp    %ecx,%eax
  40117f:	75 f5                	jne    401176 <phase_6+0x82>
  
  401181:	eb 05                	jmp    401188 <phase_6+0x94>

  401183:	ba d0 32 60 00       	mov    $0x6032d0,%edx
  
  401188:	48 89 54 74 20       	mov    %rdx,0x20(%rsp,%rsi,2)
  40118d:	48 83 c6 04          	add    $0x4,%rsi
  401191:	48 83 fe 18          	cmp    $0x18,%rsi
  401195:	74 14                	je     4011ab <phase_6+0xb7>
L197:
  401197:	8b 0c 34             	mov    (%rsp,%rsi,1),%ecx
  40119a:	83 f9 01             	cmp    $0x1,%ecx
  40119d:	7e e4                	jle    401183 <phase_6+0x8f>

  40119f:	b8 01 00 00 00       	mov    $0x1,%eax
  4011a4:	ba d0 32 60 00       	mov    $0x6032d0,%edx
  4011a9:	eb cb                	jmp    401176 <phase_6+0x82>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

我们初步将其翻译为C代码：

    int esi = 0;
    goto L197;
    
L176:
    rdx = *(rdx + 8);   //node->next
    eax++;
    if (eax != ecx) goto L176;

    goto L188

L183:
    rdx = 0x6032d0  //nodes
L188:
    rdx = 0x7fffffffe080 + 2 * rsi;
    rsi++;
    if (rsi == 24) goto L1ab;
    
L197:
    ecx = *(A + esi);
    if (ecx <= 1) goto L183;
    rax = 1
    edx = 0x6032d0  //nodes
    goto L176;

L1ab:
	...
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

程序直接跳转到L197的位置。在这里，程序取出数组的第一个值，如果其<=1，则跳转到L183；否则给寄存器赋值后跳转到L176

注意到edx被赋予了一个指针的值，我们查看这个指针指向什么内容：

这是一个单链表，而且其数据域有2个，其中一个从1到6，另一个取值范围很广，我们可以将1-6看作每个节点的id：

struct Node{
	int val;
	int id;		//1-6之间
	struct Node* next;
};
1
2
3
4
5

目前数组中第一个元素是6，所以并不会跳转到L183，程序继续向下执行，跳转到L176：

L176:
    rdx = *(rdx + 8);   //node->next
    eax++;
    if (eax != ecx) goto L176;
1
2
3
4

这段循环初始时 %rdx 指向单链表的头节点，然后以 %eax 做计数器，循环 %ecx 次，每次让 %rdx 指向下一个节点

所以其作用就是找到单链表的第 %ecx 个节点。最终让 %rdx 指向单链表的第 %ecx 个节点

为了印证我们的想法，我们输入“3 4 5 6 1 2“，其每个元素对7求补后得到“4 3 2 1 5 6”，第一个元素是4，所以rdx最终应指向第4个节点：

如上图所示，rdx最终指向了第4个节点，证明我们的结论是正确的

现在我们分析一下这整个循环的功能：

/********40116f********/
    long rsi = 0;
    goto L197;

L176:		//找到链表的第ecx个节点
    rdx = *(rdx + 8);   //node->next
    eax++;
    if (eax != ecx) goto L176;

    goto L188

L183:
    rdx = 0x6032d0  //nodes
L188:			//将rdx的值存入栈中，如果rsi==24，则处理完了所有数据，跳出循环
    0x7fffffffe080 + 2 * rsi = rdx;
    rsi++;
    if (rsi == 24) goto L1ab;
    
L197:
    ecx = *(A + rsi);   //esi是数组下标，ecx是数据
    if (ecx <= 1) goto L183;	//如果ecx<=1，则直接跳转到L183，省略了“找第ecx节点”的过程
    rax = 1
    edx = 0x6032d0  //nodes
    goto L176;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

综合上面的注释，这段循环的功能是：每次取出数组中的一个数据c，若c != 1，则在链表中找到第c个节点，将其地址保存在栈空间中，直到处理完这6个数据；若c == 1，则直接将 0x6032d0 存入栈空间。注意到，当c == 1时，保存的是 0x6032d0，这就是第一个节点的地址，这样前后的行为就一致了，而无需考虑c是多少：每次取出数组中的一个数据c，在链表中找到第c个节点，将其地址保存在栈空间中，直到处理完这6个数据

运行完这段循环后，栈空间上保存了每个节点的地址，形成了一个指针数组，每一项指向一个链表节点

对照内存中的链表，我们发现其顺序正是“4 3 2 1 6 5”，与数组的顺序一致

下面分析下一段循环：

  4011ab:	48 8b 5c 24 20       	mov    0x20(%rsp),%rbx
  4011b0:	48 8d 44 24 28       	lea    0x28(%rsp),%rax
  4011b5:	48 8d 74 24 50       	lea    0x50(%rsp),%rsi
  4011ba:	48 89 d9             	mov    %rbx,%rcx

  4011bd:	48 8b 10             	mov    (%rax),%rdx
  4011c0:	48 89 51 08          	mov    %rdx,0x8(%rcx)
  4011c4:	48 83 c0 08          	add    $0x8,%rax
  4011c8:	48 39 f0             	cmp    %rsi,%rax
  4011cb:	74 05                	je     4011d2 <phase_6+0xde>
  4011cd:	48 89 d1             	mov    %rdx,%rcx
  4011d0:	eb eb                	jmp    4011bd <phase_6+0xc9>
1
2
3
4
5
6
7
8
9
10
11
12

翻译到C：

/*******4011ab*********/
L1ab:
    long rbx = 0x603300;    //栈空间的第一个节点指针，指向node4
    long rax = 0x7fffffffe088;  //指向栈上的第二个节点指针
    long rsi = 0x7fffffffe0b0;  //指针数组的边界
    long rcx = rbx;         //指向第一个节点

L1bd:
    rdx = *rax;     //下一个节点的指针
    rcx->next = rdx;  
    rax += 8;
    if (rax == rsi) goto L1d2;  //break
    rcx = rdx;      //向后移动一个节点
    goto L1bd
1
2
3
4
5
6
7
8
9
10
11
12
13
14

循环初始化时，%rbx 存储了栈空间上第一个节点指针，%rax 指向栈空间的下一个节点指针，%rsi 存储了栈空间上指针数组的边界，%rcx 也指向了链表上第一个节点

进入循环后，%rdx 解引用 %rax，指向链表上的下一个节点，然后令 %rcx 的next域指向 %rdx。接着将 %rdx 赋给 %rcx，向后移动一个节点

然后 %rax 指向栈上的下一个值，继续循环直到rax碰到边界

可见，这段循环的作用就是将栈空间上存储的指针数组指向的每一个一个链表节点重新按照相邻的次序串起来

观察链表可知，现在的顺序正是4->3->2->1->6->5，符合我们的推断

分析最后一段循环：

  4011d2:	48 c7 42 08 00 00 00 	movq   $0x0,0x8(%rdx)
  4011d9:	00 
  4011da:	bd 05 00 00 00       	mov    $0x5,%ebp

  4011df:	48 8b 43 08          	mov    0x8(%rbx),%rax
  4011e3:	8b 00                	mov    (%rax),%eax
  4011e5:	39 03                	cmp    %eax,(%rbx)
  4011e7:	7d 05                	jge    4011ee <phase_6+0xfa>
  4011e9:	e8 4c 02 00 00       	call   40143a <explode_bomb>

  4011ee:	48 8b 5b 08          	mov    0x8(%rbx),%rbx
  4011f2:	83 ed 01             	sub    $0x1,%ebp
  4011f5:	75 e8                	jne    4011df <phase_6+0xeb>
1
2
3
4
5
6
7
8
9
10
11
12
13

整理为C代码：

L1d2:
    rdx->next = NULL;       //链表结尾置NULL
    ebp = 5;
L1df:
    rax = rbx->next;    //rbx初始指向链表第一个节点，rax则指向下一个
    eax = rax->val;
    if (rbx->val < eax) explode_bomb();     //若前一个比后一个小，则引爆炸弹
    rbx = rbx->next;
    if (--ebp != 0) goto L1df   //循环5次
1
2
3
4
5
6
7
8
9

这里又出现了炸弹，引爆条件是“前一个节点的值比后一个节点小”。因为这是一个遍历链表的操作，所以我们需要保证链表中val的值是递减的。注意这里比对的是val而不是id，因为val在id的前面，解引用一个链表指针会直接得到val值。这里考察了结构体的机器级操作

观察到此时链表的顺序为4->3->2->1->6->5，这是不满足要求的，因为按照val递减排序后，链表的顺序应该为3->4->5->6->1->2。由于程序会对每一个节点的值对7求补，所以我们需要输入“4 3 2 1 6 5”

现在终止程序，重新输入“4 3 2 1 6 5”：

我们终于成功了！至此，最后一个炸弹拆解完毕，我们需要输入的字符串是：

"4 3 2 1 6 5"
1