实验简介

浏览bomb.c可知,本实验一共有6个关卡,由phase_1为例,该实验的运行格式如下:

1
2
3
4
5
6
/* Hmm...  Six phases must be more secure than one phase! */
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");

显然,题目需要从标准输入或者文件输入参数,然后调用phase类函数来检查输入参数是否正确,想要获取到正确的密码,我们需要检查对应的参数储存在哪块地址。

Phase_1

实验过程:

于是使用反汇编bomb可执行程序:

1
objdump -d bomb > bomb.asm

bomb.asm中查找main函数所对应的汇编代码,可以发现如下片段:

1
2
3
4
5
6
7
8
400e32: e8 67 06 00 00         callq  40149e <read_line>
400e37: 48 89 c7 mov %rax,%rdi
400e3a: e8 a1 00 00 00 callq 400ee0 <phase_1>
400e3f: e8 80 07 00 00 callq 4015c4 <phase_defused>
400e44: bf a8 23 40 00 mov $0x4023a8,%edi
400e49: e8 c2 fc ff ff callq 400b10 <puts@plt>
400e4e: e8 4b 06 00 00 callq 40149e <read_line>
400e53: 48 89 c7 mov %rax,%rdi

400e32处调用了read_line函数,可以看出是在获取标准输入,下一步执行mov %rax,%rdi,表示将返回值存入到了%rdi寄存器中,然后立即调用phase_1函数,于是我们找到phase_1函数:

1
2
3
4
5
6
7
8
9
0000000000400ee0 <phase_1>:
400ee0: 48 83 ec 08 sub $0x8,%rsp
400ee4: be 00 24 40 00 mov $0x402400,%esi
400ee9: e8 4a 04 00 00 callq 401338 <strings_not_equal>
400eee: 85 c0 test %eax,%eax
400ef0: 74 05 je 400ef7 <phase_1+0x17>
400ef2: e8 43 05 00 00 callq 40143a <explode_bomb>
400ef7: 48 83 c4 08 add $0x8,%rsp
400efb: c3 retq

观察到phase_1首先将栈顶指针向下移了8位,然后将0x402400地址存入%esi(%rsi)寄存器中,然后调用了strings_not_equal这个函数,然后测试返回值是否为0,如果不为0将栈顶指针加8直接返回,否则直接调用explode_bomb函数(看名字是引爆炸弹),所以我们现在应该去strings_not_equal这个函数内查看:

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
0000000000401338 <strings_not_equal>:
401338: 41 54 push %r12
40133a: 55 push %rbp
40133b: 53 push %rbx
40133c: 48 89 fb mov %rdi,%rbx
40133f: 48 89 f5 mov %rsi,%rbp
401342: e8 d4 ff ff ff callq 40131b <string_length>
401347: 41 89 c4 mov %eax,%r12d
40134a: 48 89 ef mov %rbp,%rdi
40134d: e8 c9 ff ff ff callq 40131b <string_length>
401352: ba 01 00 00 00 mov $0x1,%edx
401357: 41 39 c4 cmp %eax,%r12d
40135a: 75 3f jne 40139b <strings_not_equal+0x63>
40135c: 0f b6 03 movzbl (%rbx),%eax
40135f: 84 c0 test %al,%al
401361: 74 25 je 401388 <strings_not_equal+0x50>
401363: 3a 45 00 cmp 0x0(%rbp),%al
401366: 74 0a je 401372 <strings_not_equal+0x3a>
401368: eb 25 jmp 40138f <strings_not_equal+0x57>
40136a: 3a 45 00 cmp 0x0(%rbp),%al
40136d: 0f 1f 00 nopl (%rax)
401370: 75 24 jne 401396 <strings_not_equal+0x5e>
401372: 48 83 c3 01 add $0x1,%rbx
401376: 48 83 c5 01 add $0x1,%rbp
40137a: 0f b6 03 movzbl (%rbx),%eax
40137d: 84 c0 test %al,%al
40137f: 75 e9 jne 40136a <strings_not_equal+0x32>
401381: ba 00 00 00 00 mov $0x0,%edx
401386: eb 13 jmp 40139b <strings_not_equal+0x63>
401388: ba 00 00 00 00 mov $0x0,%edx
40138d: eb 0c jmp 40139b <strings_not_equal+0x63>
40138f: ba 01 00 00 00 mov $0x1,%edx
401394: eb 05 jmp 40139b <strings_not_equal+0x63>
401396: ba 01 00 00 00 mov $0x1,%edx
40139b: 89 d0 mov %edx,%eax
40139d: 5b pop %rbx
40139e: 5d pop %rbp
40139f: 41 5c pop %r12
4013a1: c3 retq

完整的strings_not_equal如上图所示。首先函数将三个寄存器的内容压入栈中进行保护,然后分别将%rdi,%rsi中的内容移入至%rbs,%rbp中,然后调用string_length函数,通过函数名可以猜测该函数用来检测字符串的长度,然后返回时将返回值赋值给%r12d寄存器,随后将%rbp(地址$0x402400)的内容赋值给%rdi,随后几行分别再次调用string_length函数并进行与1的比较,也就是检测字符串的长度是否与目标字符串的长度吻合,如果吻合的话,继续向下执行。否则跳转至:

1
2
3
4
5
40139b:  89 d0                  mov    %edx,%eax
40139d: 5b pop %rbx
40139e: 5d pop %rbp
40139f: 41 5c pop %r12
4013a1: c3 retq

即返回1。

继续向下观察,发现汇编指令中首先检查输入的首字符是否为空字符,即’/0’,即以下指令:

1
2
40135c:  0f b6 03               movzbl (%rbx),%eax
40135f: 84 c0 test %al,%al

这里将%rbx中的内容(即标准输入内容)取出,放入%eax中并进行了符号位扩展,如果为0的话就直接向下跳转,因为我们的目的是寻找目标字符串,所以不必管跳转内容,直接向下运行即可。

接着可以观察到以下指令:

1
cmp    0x0(%rbp),%al

即将%rbp(即内存$0x402400中的内容)与标准输入的第一个字符进行比对,由此看来,答案就呼之欲出了!标准密码就藏在地址$0x402400中。

于是我们在命令行使用gdb进行调试:

1
2
3
gdb bomb
(gdb) b explode_bomb
(gdb) x/s 0x402400/*查看密码*/

于是命令行输出:

1
0x402400:       "Border relations with Canada have never been better."

于是运行:

1
(gdb) run

根据提示输入标准输入:

1
Border relations with Canada have never been better.

输出信息:

1
Phase 1 defused. How about the next one?

于是第一关就圆满地结束了!

运行结果:

Phase_2

实验过程:

同样地,在main函数里寻找关于phase_2函数的汇编代码:

1
2
3
4
400e4e: e8 4b 06 00 00         callq  40149e <read_line>
400e53: 48 89 c7 mov %rax,%rdi
400e56: e8 a1 00 00 00 callq 400efc <phase_2>
400e5b: e8 64 07 00 00 callq 4015c4 <phase_defused>

可知输入放在了%rdi寄存器中。

下面查询phase_2的汇编代码:

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
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 callq 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 callq 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 callq 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 retq

400efe: sub $0x28,%rsp400f02: mov %rsp,%rsi 分配了一块 40 bytes 大小的空间,并将其地址传给了 %rsi 寄存器。

1
%rsi = %rsp

400f05: callq 40145c 调用函数 read_six_numbers。从函数名推测其作用可能为读入 6 个数。

观察函数read_six_numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
000000000040145c <read_six_numbers>:
40145c: 48 83 ec 18 sub $0x18,%rsp
401460: 48 89 f2 mov %rsi,%rdx
401463: 48 8d 4e 04 lea 0x4(%rsi),%rcx
401467: 48 8d 46 14 lea 0x14(%rsi),%rax
40146b: 48 89 44 24 08 mov %rax,0x8(%rsp)
401470: 48 8d 46 10 lea 0x10(%rsi),%rax
401474: 48 89 04 24 mov %rax,(%rsp)
401478: 4c 8d 4e 0c lea 0xc(%rsi),%r9
40147c: 4c 8d 46 08 lea 0x8(%rsi),%r8
401480: be c3 25 40 00 mov $0x4025c3,%esi
401485: b8 00 00 00 00 mov $0x0,%eax
40148a: e8 61 f7 ff ff callq 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 callq 40143a <explode_bomb>
401499: 48 83 c4 18 add $0x18,%rsp
40149d: c3 retq

先看开始的部分:

1
2
3
4
5
6
7
8
9
40145c: 48 83 ec 18            sub    $0x18,%rsp
401460: 48 89 f2 mov %rsi,%rdx
401463: 48 8d 4e 04 lea 0x4(%rsi),%rcx
401467: 48 8d 46 14 lea 0x14(%rsi),%rax
40146b: 48 89 44 24 08 mov %rax,0x8(%rsp)
401470: 48 8d 46 10 lea 0x10(%rsi),%rax
401474: 48 89 04 24 mov %rax,(%rsp)
401478: 4c 8d 4e 0c lea 0xc(%rsi),%r9
40147c: 4c 8d 46 08 lea 0x8(%rsi),%r8

译成C语言:

1
2
3
4
5
6
7
8
int* pos[3];                       
num0_pos = start_pos;
num1_pos = start_pos + 1;
tmp_pos = start_pos + 5;
pos[1] = tmp_pos; tmp_pos = start_pos + 4;
pos[0] = tmp_pos;
num3_pos = start_pos + 3;
num2_pos = start_pos + 2;

于是得到各地址保存的位置:

1
2
3
4
5
6
%rdx = %rsi
%rcx = %rsi + 4
%r8 = %rsi + 8
%r9 = %rsi + 12
0x0(%rsp) = %rsi + 16
0x8(%rsp) = %rsi + 20

由上一节知,%rsi 寄存器存放的是调用者 %rsp 寄存器中的内容,因此这 6 个地址分别对应调用者栈里开始的 6 个连续 int 的地址。

回到phase_2函数部分

由之前的分析,我们确定了函数 read_six_numbers 的具体作用。此时栈内保存的信息为:

1
2
3
4
5
6
0x0(%rsp) = nums[0]
0x4(%rsp) = nums[1]
0x8(%rsp) = nums[2]
0xc(%rsp) = nums[3]
0x10(%rsp) = nums[4]
0x14(%rsp) = nums[5]

其中,nums[0] ~ nums[5] 表示输入的字符串中解析得到的(前)6 个整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
400f0a: 83 3c 24 01            cmpl   $0x1,(%rsp)
400f0e: 74 20 je 400f30 <phase_2+0x34>
400f10: e8 25 05 00 00 callq 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 callq 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 retq

这段的结构比较复杂。先直译成含 goto 语句的 C 语言代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    if (nums[0] == 1)               
goto L_400f30;
explode_bomb();
goto L_400f30;
L_400f17:
target = *(cur_pos - 1);
target *= 2;
if (*cur_pos == target)
goto L_400f25;
explode_bomb();
L_400f25:
cur_pos += 1;
if (cur_pos != end_pos)
goto L_400f17;
goto L_400f3c; L_400f30:
cur_pos = nums + 1;
end_pos = nums + 6;
goto L_400f17; L_400f3c:
return target;

整理得到:

1
2
3
4
5
6
7
8
9
10
if (nums[0] != 1)    
explode_bomb();
end_pos = nums + 6;
for (cur_pos = nums + 1; cur_pos != end_pos; ++cur_pos)
{
target = *(cur_pos - 1) * 2;
if (*cur_pos != target)
explode_bomb();
}
return target;

通过这段代码,需要输入的 6 个整数就很显然了——第 1 个整数应当为 1,之后的每个整数都是前一个数的 2 倍。于是需要输入的 6 个整数依次为 1, 2, 4, 8, 16, 32

由之前的分析,本关密码即为 1 2 4 8 16 32

gdb 中输入 Phase 2 的密码

1
That's number 2.  Keep going!

运行结果:

phase_3

实验过程

main函数和前面实验过程一样,直接看phase_3函数:

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
0000000000400f43 <phase_3>:
400f43: 48 83 ec 18 sub $0x18,%rsp
400f47: 48 8d 4c 24 0c lea 0xc(%rsp),%rcx
400f4c: 48 8d 54 24 08 lea 0x8(%rsp),%rdx
400f51: be cf 25 40 00 mov $0x4025cf,%esi
400f56: b8 00 00 00 00 mov $0x0,%eax
400f5b: e8 90 fc ff ff callq 400bf0 <__isoc99_sscanf@plt>
400f60: 83 f8 01 cmp $0x1,%eax
400f63: 7f 05 jg 400f6a <phase_3+0x27>
400f65: e8 d0 04 00 00 callq 40143a <explode_bomb>
400f6a: 83 7c 24 08 07 cmpl $0x7,0x8(%rsp)
400f6f: 77 3c ja 400fad <phase_3+0x6a>
400f71: 8b 44 24 08 mov 0x8(%rsp),%eax
400f75: ff 24 c5 70 24 40 00 jmpq *0x402470(,%rax,8)
400f7c: b8 cf 00 00 00 mov $0xcf,%eax
400f81: eb 3b jmp 400fbe <phase_3+0x7b>
400f83: b8 c3 02 00 00 mov $0x2c3,%eax
400f88: eb 34 jmp 400fbe <phase_3+0x7b>
400f8a: b8 00 01 00 00 mov $0x100,%eax
400f8f: eb 2d jmp 400fbe <phase_3+0x7b>
400f91: b8 85 01 00 00 mov $0x185,%eax
400f96: eb 26 jmp 400fbe <phase_3+0x7b>
400f98: b8 ce 00 00 00 mov $0xce,%eax
400f9d: eb 1f jmp 400fbe <phase_3+0x7b>
400f9f: b8 aa 02 00 00 mov $0x2aa,%eax
400fa4: eb 18 jmp 400fbe <phase_3+0x7b>
400fa6: b8 47 01 00 00 mov $0x147,%eax
400fab: eb 11 jmp 400fbe <phase_3+0x7b>
400fad: e8 88 04 00 00 callq 40143a <explode_bomb>
400fb2: b8 00 00 00 00 mov $0x0,%eax
400fb7: eb 05 jmp 400fbe <phase_3+0x7b>
400fb9: b8 37 01 00 00 mov $0x137,%eax
400fbe: 3b 44 24 0c cmp 0xc(%rsp),%eax
400fc2: 74 05 je 400fc9 <phase_3+0x86>
400fc4: e8 71 04 00 00 callq 40143a <explode_bomb>
400fc9: 48 83 c4 18 add $0x18,%rsp
400fcd: c3 retq

首先看到进入函数后首先把栈顶指针%rsp寄存器向下减了8位,然后将(%rsp+8)和(%rsp+12)中的内容存在%rdx和%rcx寄存器中。再往后看,出现了一个奇怪的地址,我们将这个地址打印出来,显示的是“%d %d”,这个同第二题一样,表示我们输入的格式,应该输入两个数,中间使用空格进行区分。

然后调用了<__isoc99_sscanf@plt>函数,将返回值与1进行比较,如果输入的数量大于1,则进行跳转,否则引爆炸弹。经过与前面进行比较与推断,可知分辨要将输入的两个数保存在%rdx和%rcx寄存器中。然后将0x8(%rsp)即%rdx的数值与7进行比较,如果大于7的话,就引爆炸弹,否则继续执行,考虑到跳转指令使用的ja指令,由此可知对应的第一个数的输入范围是[0,7]。向下看,发现将0x8(%rsp)中的值放到了%eax中。

下一条指令使用的是jmpq *0x402470(,%rax,8),这是一条switch语句的命令,根据输入的第一个参数的内容对基于*0x402470的首地址进行跳转,第一个参数有八个取值,从0到7,我们逐一测试。

这里以nums[0]取1为例,此时0x402470(,%rax,8)的值为0x402470 + 1 * 8 = 0x402478。使用gdb查看改地址存放的地址:

1
(gdb) x/g 0x402470 + 1 * 8

输出信息:

0x402478: 0x0000000000400fb9

因此 400fb9: mov $0x137,%eax 即为 nums[0]1 时跳转到的语句。

类似地,我们可以得到 nums[0] 取 [0, 7] 时对应的整个跳转表,从而得到以下 C 语言代码:

1
2
3
4
5
6
7
8
9
10
11
switch (nums[0]) {                          *// result in %eax*   
case 0: result = 0xcf; break; *// 0x400f7c*
case 1: result = 0x137; break; *// 0x400fb9*
case 2: result = 0x2c3; break; *// 0x400f83*
case 3: result = 0x100; break; *// 0x400f8a*
case 4: result = 0x185; break; *// 0x400f91*
case 5: result = 0xce; break; *// 0x400f98*
case 6: result = 0x2aa; break; *// 0x400f9f*
case 7: result = 0x147; break; *// 0x400fa6* } *// 0x400fbe*
if (result != nums[1]) *// nums[1] = 0xc(%rsp)* explode_bomb();
return result;

通过这段代码,可以发现 nums[0] 经跳转后得到的新数 result 就应当为 nums[1]

于是得到本关的 8 组解:

1
0 207`, `1 311`, `2 707`, `3 256`, `4 389`, `5 206`, `6 682`, `7 327

输入:

1
0207

输出信息:

1
Halfway there!

Phase_4

实验过程

找到phase_4函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
<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 callq 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 callq 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 callq 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 callq 40143a <explode_bomb>
40105d: 48 83 c4 18 add $0x18,%rsp
401061: c3 retq

得到:

1
2
%rdx = %rsp + 8
%rcx = %rsp + 12

由上一关的分析,本关密码同样应当是输入 2 个整数(之间有且仅有一个空格),这 2 个整数将被保存在之前 2 个参数所提供的 2 个地址中。

因此读取完毕后,栈内保存的信息为:

1
2
0x8(%rsp) = nums[0]
0xc(%rsp) = nums[1]

其中,nums[0]nums[1] 表示输入的字符串中解析得到的(前)2 个整数。

401029: cmp $0x2,%eax 和 40102c: jne 401035 判断函数 sscanf 的返回值是否等于 2,是则继续执行之后的语句,否则直接跳到 401035: callq 40143a 引爆炸弹。同上一关的说明,即检查是否成功读入且仅读入了 2 个整数,如果不是则直接引爆炸弹。

40102e: cmpl $0xe,0x8(%rsp) 和 401033: jbe 40103a 判断 0x8(%rsp) 的值(即 nums[0],也就是输入的第 1 个整数)是否不超过 14,是则直接跳到 40103a: mov $0xe,%edx,否则执行 401035: callq 40143a 引爆炸弹。

因此,输入的第 1 个整数应当不超过 14(无符号数),即其取值范围为 [0, 14]。

40103a: mov $0xe,%edx、40103f: mov $0x0,%esi 和 401044: mov 0x8(%rsp),%edi 将 %edx、%esi、%edi 寄存器分别赋值为 0xe0x00x8(%rsp)

1
2
3
%edi = 0x8(%rsp) = nums[0]
%esi = 0
%edx = 14

401048: callq 400fce 调用函数 func4,也就是本关的主体部分。

4.2.2 观察函数 func4

在 bomb.asm 中找到函数 func4 对应的汇编语句:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
<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
callq 400fce <func4> 400fee: 01 c0
add %eax,%eax 400ff0: eb 15
jmp 401007 <func4+0x39> 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
callq 400fce <func4> 401003: 8d 44 00 01
lea 0x1(%rax,%rax,1),%eax 401007: 48 83 c4 08
add $0x8,%rsp 40100b: c3
retq

400fe9 和 400ffe: callq 400fce 都调用了函数 func4 自身,可见这是一个递归函数。

试译成 C 语言代码(经整理及部分改写,类似 2.2.3 节的处理流程):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
*// key in %edi, low in %esi, high in %edx* 
int func4(int key, int low, int high) {
int length = high - low; *// length in %eax*
unsigned sign = length >> 31; *// sign in %ecx*
int half_len = (length + sign) >> 1; *// half_len in %eax* *// half_len = length /= 2*
int mid = half_len + low; *// mid in %ecx*
int result; *// result in %eax*
if (mid > key) {
high = mid - 1;
result = func4(key, low, high) * 2;
} else if (mid >= key) { *//
mid == key* result = 0; }
else
{ *// mid < key*
low = mid + 1;
result = func4(key, low, high) * 2 + 1;
}
return result;
}
4.2.3 回到函数 phase_4

%eax = func4(nums[0], 0, 14)

1
2
3
4
5
6
7
1234567  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 callq 40143a <explode_bomb>
40105d: 48 83 c4 18 add $0x18,%rsp
401061: c3 retq

40104d: test %eax,%eax 和 40104f: jne 401058 判断函数 func4 的返回值是否为 0,是则继续执行之后的语句,否则直接跳到 401058: callq 40143a 引爆炸弹。

因此,输入的第 1 个整数 nums[0] 需要使函数 func4(nums[0], 0, 14) 的返回值为 0,其中 nums[0] 的取值范围为 [0, 14]。

401051: cmpl $0x0,0xc(%rsp) 和 401056: je 40105d 判断 0xc(%rsp) 的值(即 nums[1],也就是输入的第 2 个整数)是否为 0,是则直接跳到 40105d: add $0x18,%rsp 弹栈返回,否则执行 401058: callq 40143a 引爆炸弹。

因此,输入的第 2 个整数应当为 0

4.2.4 确定输入的第 1 个整数

事实上,由于 nums[0] 的取值范围有限,直接遍历然后测试返回值是否为 0 即可。测试代码如下:

1
2
3
4
5
6
7
8
9
10
void Solution() {
const int kBegin = 0;
const int kEnd = 14;
printf("The solutions are:");
for (int i = kBegin; i <= kEnd; ++i) {
if (func4(i, kBegin, kEnd) == 0)
printf(" %d", i);
}
printf("\n");
}

输出结果:

1
The solutions are: 0 1 3 7

即为第 1 个整数可能的值。

综上,本关密码即为 0 0, 1 0, 3 0, 7 0

4.2.5 测试

这里以 7 0 为例,在 gdb 中输入 Phase 4 的密码:

1
7 0

输出信息:

1
So you got that one.  Try this one.

5. Phase 5: pointers

5.1 本关密码

9ON567(不唯一)

5.2 解题过程

%rdi = input

5.2.1 观察函数 phase_5

在 bomb.asm 中找到函数 phase_5 对应的汇编语句:

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
<phase_5>:
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 callq 40131b <string_length>
40107f: 83 f8 06 cmp $0x6,%eax
401082: 74 4e je 4010d2 <phase_5+0x70>
401084: e8 b1 03 00 00 callq 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 callq 401338 <strings_not_equal>
4010c2: 85 c0 test %eax,%eax
4010c4: 74 13 je 4010d9 <phase_5+0x77>
4010c6: e8 6f 03 00 00 callq 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>
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 callq 400b30 <__stack_chk_fail@plt>
4010ee: 48 83 c4 20 add $0x20,%rsp
4010f2: 5b pop %rbx
4010f3: c3 retq

401067: mov %rdi,%rbx 将 %rdi 寄存器上保存的地址传给了 %rbx 寄存器。

%rbx = %rdi = input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
401063:   48 83 ec 20             sub    $0x20,%rsp
...
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)
...
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 callq 400b30 <__stack_chk_fail@plt>
4010ee: 48 83 c4 20 add $0x20,%rsp
4010f2: 5b pop %rbx
4010f3: c3 retq

这里的 %fs:0x28 是 FS 段寄存器(segment register)上偏移地址 0x28 上的数据。这是一个随机量,在这里起到 stack canary 的作用 。这部分代码即利用这个 stack canary 来确保 0x18(%rsp) 的数值(即栈底的 8 bytes)在函数前后没有发生改动,如果发生改动则执行 4010e9: callq 400b30 <__stack_chk_fail@plt> 调用系统函数 __stack_chk_fail 跳出,从而防止栈溢出(stack overflow)的问题。事实上,这段代码与本关的关系不大,这里就不做更多阐述了。

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

401078: xor %eax,%eax 将 %eax 寄存器设置为 0

%eax = 0

40107a: callq 40131b 调用函数 string_length。由 1.2.4 节的分析,函数 string_length 的返回值就是字符串 input 的长度。

40107f: cmp $0x6,%eax 和 401082: je 4010d2 判断返回值是否为 6,是则直接跳到 4010d2: mov $0x0,%eax,否则执行 401084: callq 40143a 引爆炸弹。

可见,输入的字符串的长度应当为 6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 callq 401338 <strings_not_equal>
4010c2: 85 c0 test %eax,%eax
4010c4: 74 13 je 4010d9 <phase_5+0x77>
4010c6: e8 6f 03 00 00 callq 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>
4010d9: 48 8b 44 24 18 mov 0x18(%rsp),%rax
...

剩下的内容也就是本关的主体部分。直观起见,试译成 C 语言代码(经整理及部分改写):

1
2
3
4
5
6
7
8
9
10
11
12
13
cur_char = 0;                                   // cur_char in %rcx
for (i = 0; i != 6; ++i) { // i in %rax
cur_char = input[i]; // input in %rbx
index = cur_char; // index in %rsp, later copied to %edx
index &= 0xf;
target_char = target[index]; // target_char in %edx, target in 0x4024b0
word[i] = target_char; // word in %rsp + 0x10
}
word[6] = '\0';
result = strings_not_equal(word, 0x40245e); // result in %eax
if (result != 0)
explode_bomb();
return result;

其中,由 1.2.5 节的分析,函数 strings_not_equal 的作用为检查两个字符串是否相等,是则返回 0,否则返回 1。同时也可以知道 0x40245e 这个地址指向的是一个字符串。

可见,这段代码的作用为:

  1. 构造一个 6 位的新字符串 word,遍历输入的字符串 input 的 6 个字符,以字符 input[i] 的最低 4 位二进制数为索引 index,依次将 word[i] 设置为字符 target[index](可以推测出 0x4024b0 这个地址指向的也是一个字符串,这里设为 target),最后将 word[6] 设置为 '\0' 作为字符串结束符;
  2. 检查字符串 word0x40245e 指向的字符串是否相等,是则直接返回,否则引爆炸弹。

因此,由 0x40245e 指向的字符串倒推得对应的 6 个索引 index,再根据这些 index 得到输入的字符串 input 的 6 个字符,就可以得到本关的密码。

5.2.2 确定目标字符串 word 的值

使用 gdb 查看地址 0x40245e 存放的内容:

1
(gdb) x/s 0x40245e

输出信息:

1
0x40245e:       "flyers"

这就是我们需要构造的目标字符串 word 的值。

5.2.3 确定 6 个索引 index 的值

使用 gdb 查看地址 0x4024b0 存放的内容:

1
(gdb) x/s 0x4024b0

输出信息:

1
2

0x4024b0 <array.3449>: "maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"

这就是字符串 target 的值,我们需要将 word[i] 分别设置为字符 target[index]。于是得到对应的 6 个 index 的值为:0x9, 0xf, 0xe, 0x5, 0x6, 0x7index 是 4 位二进制数,因此其取值范围为 [0x0, 0xf])。

5.2.4 确定输入的 6 个字符

由于索引 index 是字符 input[i] 的最后 4 位(二进制),通过 ASCII 码表 [^6] 找到最后 4 位为 index 的字符即可。于是得到对应的 6 个字符为:9, O, N, 5, 6, 7(答案不唯一,这里就不一一列举了)。

因此,本关密码即为 9ON567

5.2.5 测试

在 gdb 中输入 Phase 5 的密码:

1
9ON567

输出信息:

1
Good work!  On to the next...

6. Phase 6: linked lists / pointers / structs

6.1 本关密码

1
4 3 2 1 6 5

6.2 解题过程

%rdi = input

6.2.0 观察函数 phase_6

在 bomb.asm 中找到函数 phase_6 对应的汇编语句:

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
<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 callq 40145c <read_six_numbers>
40110b: 49 89 e6 mov %rsp,%r14
40110e: 41 bc 00 00 00 00 mov $0x0,%r12d
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 callq 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
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 callq 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>
40114d: 49 83 c5 04 add $0x4,%r13
401151: eb c1 jmp 401114 <phase_6+0x20>
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
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>
40116f: be 00 00 00 00 mov $0x0,%esi
401174: eb 21 jmp 401197 <phase_6+0xa3>
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>
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>
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>
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 callq 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>
4011f7: 48 83 c4 50 add $0x50,%rsp
4011fb: 5b pop %rbx
4011fc: 5d pop %rbp
4011fd: 41 5c pop %r12
4011ff: 41 5d pop %r13
401201: 41 5e pop %r14
401203: c3 retq

发现这段代码相当长,所以这里就不逐句分析了,直接逆向工程。

6.2.1 第一部分(4010f4 ~ 40110b)
1
2
3
4
5
6
7
8
9
10
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 callq 40145c <read_six_numbers>
40110b: 49 89 e6 mov %rsp,%r14

首先读入 6 个整数(详见 2.2.2 节),保存到栈中。

%rsi = %r13 = %r14 = %rsp
0x00(%rsp) = nums[0]
0x04(%rsp) = nums[1]
0x08(%rsp) = nums[2]
0x0c(%rsp) = nums[3]
0x10(%rsp) = nums[4]
0x14(%rsp) = nums[5]

其中,nums[0] ~ nums[5] 表示输入的字符串中解析得到的(前)6 个整数。

6.2.2 第二部分(40110e ~ 401151)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
40110e:   41 bc 00 00 00 00       mov    $0x0,%r12d
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 callq 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
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 callq 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>
40114d: 49 83 c5 04 add $0x4,%r13
401151: eb c1 jmp 401114 <phase_6+0x20>
401153: 48 8d 74 24 18 lea 0x18(%rsp),%rsi
...

试译成 C 语言代码(经整理及部分改写):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// cur_pos = nums;                              // cur_pos in %r13, nums in %rsp
next_index = 0; // next_index in %r12d
while (true) {
cur_num = *cur_pos; // cur_pos in %r13, later copied to %rbp
if (--cur_num > 5) // cur_num in %eax
explode_bomb();
++next_index;
if (next_index == 6)
break;
for (i = next_index; i <= 5; ++i) { // i in %ebx, later copied to %rax
next_num = nums[i]; // next_num in %eax
if (next_num == *cur_pos)
explode_bomb();
}
++cur_pos;
}

通过这段代码,可以得知输入的 6 个整数需要满足以下条件:

  1. 减 1 后不能超过 5(无符号数),即其取值范围为 [1, 6];
  2. 必须互不相同。

因此,这 6 个整数是 1 ~ 6 的一个全排列。

6.2.3 第三部分(401153 ~ 40116d)
1
2
3
4
5
6
7
8
9
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
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>

试译成 C 语言代码(经整理及部分改写):

1
2
3
4
5
6
7
begin_pos = rsp;                             // begin_pos in %r14
end_pos = rsp + 6; // end_pos in %rsi
minuend = 7; // minuend in %ecx
for (i = begin_pos; i != end_pos; ++i) { // i in %rax
new_num = minuend - *i; // new_num in %edx
*i = new_num;
}

可见,保存在栈中的这 6 个整数 nums[i] 被依次修改成了 7 - nums[i]

6.2.4 第四部分(40116f ~ 4011a9)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
40116f:   be 00 00 00 00          mov    $0x0,%esi
401174: eb 21 jmp 401197 <phase_6+0xa3>
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>
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>
4011ab: 48 8b 5c 24 20 mov 0x20(%rsp),%rbx
...

这是本关的主体部分。试译成 C 语言代码(经整理及大量不影响原意的改写):

1
2
3
4
5
6
7
for (i = 0; i != 6; ++i) {          // i in %rsi
cur_num = nums[i]; // cur_num in %ecx, nums in %rsp
p_node = 0x6032d0; // p_node in %edx
for (j = 1; j < cur_num; ++j) // j in %eax
p_node = *(++p_node); // assure that p_node is always a pointer
ptrs[i] = p_node; // ptrs in %rsp + 0x20
}

可见,根据被修改后的这 6 个整数 nums[i],这段代码在 ptrs[i](即 *(%rsp + 0x20 + i * 0x8))中存放经过 nums[i] - 1p_node = *(++p_node); 操作的地址 p_node,其中 p_node 的初始值为 0x6032d0

可以看出这实际就是将链表的 6 个结点以 nums[i] 为索引顺序存到栈中。每次操作就是将 p_node 指向下一个结点,因此经过 nums[i] - 1 次操作得到的 p_node 就是 nums[i] 号结点的地址 p_node(nums[i])

ptrs[i] = p_node(nums[i])

由之前的分析,nums[i] 是 1 ~ 6 的一个全排列,由此可以得到这 6 个结点的地址。

以进行 1 次操作为例,使用 gdb 查看此时 p_node 的值(原 p_node + 0x8 所指向的内容):

1
(gdb) x/xw 0x6032d8

输出信息:

1
0x6032d8 <node1+8>:     0x006032e0

这就是 2 号结点的地址 p_node2

用同样的方式得到 6 个结点的地址:

p_node1 = 0x6032d0
p_node2 = 0x6032e0
p_node3 = 0x6032f0
p_node4 = 0x603300
p_node5 = 0x603310
p_node6 = 0x603220

6.2.5 第五部分(4011ab ~ 4011d0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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>
4011d2: 48 c7 42 08 00 00 00 movq $0x0,0x8(%rdx)
4011d9: 00
...

试译成 C 语言代码(经整理及部分改写):

1
2
3
4
5
6
7
8
9
123456789begin_node = *ptrs;                 // begin_node in %rbx, ptrs in %rsp + 0x20
next_pos = ptrs + 1; // next_pos in %rax
end_pos = ptrs + 6; // end_pos in %rsi
for (cur_node = begin_node; next_pos != end_pos;
cur_node = next_node) { // cur_node in %rcx
next_node = *next_pos; // next_node in %rdx
*(cur_node + 1) = next_node;
++next_pos;
}c

可见,这段代码的作用为按在栈中地址由低到高顺序遍历链表的 6 个结点,将它们串联起来。

这里的 *(cur_node + 1) 实质上就是 cur_node->next(即 (*cur_node).next),因为链表中的结点其实是一个结构体(struct),结点所在的地址指向的是数据 val,加上 0x8 后指向的也就是指针 next。此处将该指针 next 指向了下一个结点。

6.2.6 第六部分(4011da ~ 401203)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 callq 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>
4011f7: 48 83 c4 50 add $0x50,%rsp
4011fb: 5b pop %rbx
4011fc: 5d pop %rbp
4011fd: 41 5c pop %r12
4011ff: 41 5d pop %r13
401201: 41 5e pop %r14
401203: c3 retq

试译成 C 语言代码(经整理及部分改写):

1
2
3
4
5
6
7
8
 12345678for (i = 5; i != 0; --i) {          // i in %ebp
next_node = *(cur_node + 1); // next_node in %rax, cur_node in %rbx
next_num = *next_node; // next_num in %eax
if (*cur_node < next_num)
explode_bomb();
cur_node = *(cur_node + 1);
}
return next_node;

由上一节的分析,*cur_nodecur_node->val*(cur_node + 1)cur_node->next。通过这段代码,可以发现链表各个结点的数据 val 需要是顺序递减的。

以 1 号结点 node1 为例,使用 gdb 查看其数据 val

1
(gdb) x/d 0x6032d0

输出信息:

1
0x6032d0 <node1>:       332

用同样的方式得到链表 6 个结点的数据:

p_node1->val = 332
p_node2->val = 168
p_node3->val = 924
p_node4->val = 691
p_node5->val = 477
p_node6->val = 443

按递减顺序排列后,可见在栈中地址由低到高应当分别为 3, 4, 5, 6, 1, 2 号结点。

6.2.7 确定输入的 6 个整数

由之前的分析,nums[i] 在第三部分的代码中被依次修改成了 7 - nums[i],而修改后的值分别对应栈中结点的标号 3, 4, 5, 6, 1, 2

因此,最开始输入的 6 个整数也就是 4, 3, 2, 1, 6, 5,本关密码即为 4 3 2 1 6 5

6.2.8 测试

在 gdb 中输入 Phase 6 的密码:

1
4 3 2 1 6 5

输出信息:

1
Congratulations! You've defused the bomb!

7. 结束了吗

在 bomb.c 文件的最后,留下了这样一句耐人寻味的话:

1
2
/* Wow, they got it!  But isn't something... missing?  Perhaps
* something they overlooked? Mua ha ha ha ha! */

这是因为,本 Lab 还有一个隐藏关!

8. Secret phase

8.1 本关密码

8.1.1 开启隐藏关的方法

在 Phase 4 输入的 2 个整数后再额外输入 1 个字符串 DrEvil,比如将输入的字符串修改为 7 0 DrEvil,其余环节不变。

8.1.2 隐藏关的密码
1
22, 20

8.2 解题过程

8.2.0 找到隐藏函数

好吧,实际上在 bomb.asm 中稍微往下翻翻就能找到一个名为 secret_phase 的函数。顾名思义,这应该就是隐藏关所对应的函数。

8.2.1 找到开启隐藏关的方法

事实上,前 6 关通过后,程序就自动终止了。那么应该如何进入这个隐藏关呢?

在 bomb.asm 搜索关键词 secret_phase,可以发现在函数 phase_defused 中出现了调用函数 secret_phase 的语句 401630: callq 401242。其中函数 phase_defused 就是每关通过后都会调用的函数。

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
004015c4 <phase_defused>:
4015c4: 48 83 ec 78 sub $0x78,%rsp
4015c8: 64 48 8b 04 25 28 00 mov %fs:0x28,%rax
4015cf: 00 00
4015d1: 48 89 44 24 68 mov %rax,0x68(%rsp)
4015d6: 31 c0 xor %eax,%eax
4015d8: 83 3d 81 21 20 00 06 cmpl $0x6,0x202181(%rip) # 603760 <num_input_strings>
4015df: 75 5e jne 40163f <phase_defused+0x7b>
4015e1: 4c 8d 44 24 10 lea 0x10(%rsp),%r8
4015e6: 48 8d 4c 24 0c lea 0xc(%rsp),%rcx
4015eb: 48 8d 54 24 08 lea 0x8(%rsp),%rdx
4015f0: be 19 26 40 00 mov $0x402619,%esi
4015f5: bf 70 38 60 00 mov $0x603870,%edi
4015fa: e8 f1 f5 ff ff callq 400bf0 <__isoc99_sscanf@plt>
4015ff: 83 f8 03 cmp $0x3,%eax
401602: 75 31 jne 401635 <phase_defused+0x71>
401604: be 22 26 40 00 mov $0x402622,%esi
401609: 48 8d 7c 24 10 lea 0x10(%rsp),%rdi
40160e: e8 25 fd ff ff callq 401338 <strings_not_equal>
401613: 85 c0 test %eax,%eax
401615: 75 1e jne 401635 <phase_defused+0x71>
401617: bf f8 24 40 00 mov $0x4024f8,%edi
40161c: e8 ef f4 ff ff callq 400b10 <puts@plt>
401621: bf 20 25 40 00 mov $0x402520,%edi
401626: e8 e5 f4 ff ff callq 400b10 <puts@plt>
40162b: b8 00 00 00 00 mov $0x0,%eax
401630: e8 0d fc ff ff callq 401242 <secret_phase>
401635: bf 58 25 40 00 mov $0x402558,%edi
40163a: e8 d1 f4 ff ff callq 400b10 <puts@plt>
40163f: 48 8b 44 24 68 mov 0x68(%rsp),%rax
401644: 64 48 33 04 25 28 00 xor %fs:0x28,%rax
40164b: 00 00
40164d: 74 05 je 401654 <phase_defused+0x90>
40164f: e8 dc f4 ff ff callq 400b30 <__stack_chk_fail@plt>
401654: 48 83 c4 78 add $0x78,%rsp
401658: c3 retq
401659: 90 nop
40165a: 90 nop
40165b: 90 nop
40165c: 90 nop
40165d: 90 nop
40165e: 90 nop
40165f: 90 nop

注意到以下片段:

1
2
3
4
5
6
7
8
9
10
11
12
13
4015d6:   31 c0                   xor    %eax,%eax
4015d8: 83 3d 81 21 20 00 06 cmpl $0x6,0x202181(%rip) # 603760 <num_input_strings>
4015df: 75 5e jne 40163f <phase_defused+0x7b>
...
40163f: 48 8b 44 24 68 mov 0x68(%rsp),%rax
401644: 64 48 33 04 25 28 00 xor %fs:0x28,%rax
40164b: 00 00
40164d: 74 05 je 401654 <phase_defused+0x90>
40164f: e8 dc f4 ff ff callq 400b30 <__stack_chk_fail@plt>
401654: 48 83 c4 78 add $0x78,%rsp
401658: c3 retq
401659: 90 nop
...

4015d6: xor %eax,%eax 将 %eax 寄存器设置为 0

4015d8: cmpl $0x6,0x202181(%rip) 和 4015df: jne 40163f 判断 0x202181(%rip) 的值是否为 6,是则继续执行之后的语句,否则直接跳到 40163f: mov 0x68(%rsp),%rax 返回(这一段详见 5.2.1 节关于 stack canary 的阐述)。

0x202181(%rip) 也就是 (0x603760) 存放的是什么?通过 gdb 发现,这个值的初始值为 0,而每通过一关后,这个值便加 1。结合注释(即变量名)# 603760,推测它表示输入过的字符串数量,实际上也就是通过的关卡数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
(gdb) x/d 0x603760
0x603760 <num_input_strings>: 0
(gdb) b phase_1
Breakpoint 2 at 0x400ee0
(gdb) b phase_2
Breakpoint 3 at 0x400efc
(gdb) r
Starting program: /root/Hakula/csapp/lab2/bomb
Welcome to my fiendish little bomb. You have 6 phases with
which to blow yourself up. Have a nice day!
Border relations with Canada have never been better.

Breakpoint 2, 0x0000000000400ee0 in phase_1 ()
(gdb) x/d 0x603760
0x603760 <num_input_strings>: 1
(gdb) c
Continuing.
Phase 1 defused. How about the next one?
1 2 4 8 16 32

Breakpoint 3, 0x0000000000400efc in phase_2 ()
(gdb) x/d 0x603760
0x603760 <num_input_strings>: 2
(gdb)

判断这个值是否为 6,也就是判断是否通过了全部 6 个关卡。因此这个隐藏关只有在 6 个关卡都顺利通过后才会开启。

剩下的片段也就是本函数与隐藏关相关的主体部分。

1
2
3
4
5
6
4015e1:   4c 8d 44 24 10          lea    0x10(%rsp),%r8
4015e6: 48 8d 4c 24 0c lea 0xc(%rsp),%rcx
4015eb: 48 8d 54 24 08 lea 0x8(%rsp),%rdx
4015f0: be 19 26 40 00 mov $0x402619,%esi
4015f5: bf 70 38 60 00 mov $0x603870,%edi
4015fa: e8 f1 f5 ff ff callq 400bf0 <__isoc99_sscanf@plt>

这段代码我们已经十分熟悉。0x402619 指向的应该是一个格式化字符串。使用 gdb 查看地址 0x402619 存放的内容:

1
(gdb) x/s 0x402619

输出信息:

1
0x402619:       "%d %d %s"

因此,在某处我们需要按这个格式输入 2 个整数和 1 个字符串。这 2 个整数将被保存在 0x8(%rsp)0xc(%rsp) 中,字符串将被保存在 0x10(%rsp) 中。需要注意的是这里还额外传入了一个地址 0x603870,根据我对系统函数 sscanf 的理解,这应当指的是那个被用来解析的字符串的地址。

读取完毕后,栈内保存的信息为:

0x8(%rsp) = nums[0]
0xc(%rsp) = nums[1]
0x10(%rsp) = password

其中,nums[0]nums[1] 表示 0x603870 指向的字符串中解析得到的(前)2 个整数,password 表示之后解析得到的(前)1 个字符串。

在函数 phase_defused 的入口处设置一个断点。

1
(gdb) b phase_defused

每通过一个关卡后,使用 gdb 查看地址 0x603870 存放的内容:

1
(gdb) x/s 0x603870

发现在通过 Phase 4 后,输出信息产生了变化:

1
0x603870 <input_strings+240>:   "7 0"

可见,0x603870 指向的是 Phase 4 中输入的字符串 7 0

1
2
3
4
5
6
4015ff:   83 f8 03                cmp    $0x3,%eax
401602: 75 31 jne 401635 <phase_defused+0x71>
...
401630: e8 0d fc ff ff callq 401242 <secret_phase>
401635: bf 58 25 40 00 mov $0x402558,%edi
...

4015ff: cmp $0x3,%eax 和 401602: jne 401635 判断函数 sscanf 的返回值是否为 3,是则继续执行之后的语句,否则直接跳到 401635: mov $0x402558,%edi,也就是跳过了隐藏关。

于是我们知道,在 Phase 4 中除了需要输入作为密码的 2 个整数外,还需要再额外输入 1 个字符串。这是开启隐藏关的前提条件。

1
2
3
4
5
6
7
8
9
401604:   be 22 26 40 00          mov    $0x402622,%esi
401609: 48 8d 7c 24 10 lea 0x10(%rsp),%rdi
40160e: e8 25 fd ff ff callq 401338 <strings_not_equal>
401613: 85 c0 test %eax,%eax
401615: 75 1e jne 401635 <phase_defused+0x71>
...
401630: e8 0d fc ff ff callq 401242 <secret_phase>
401635: bf 58 25 40 00 mov $0x402558,%edi
...

%rdi = 0x10(%rsp) = password
%esi = 0x402622

这段代码我们也已经十分熟悉。0x402622 指向的应该是一个字符串。使用 gdb 查看地址 0x402622 存放的内容:

1
(gdb) x/s 0x402622

输出信息:

1
0x402622:       "DrEvil"

此后,函数 strings_not_equal 检查 %rdi 和 %rsi 寄存器指向的字符串是否相等,即 password 是否等于 DrEvil,是则返回 0,否则返回 1

401613: test %eax,%eax 和 401615: jne 401635 判断函数 strings_not_equal 的返回值是否为 0,是则继续执行之后的语句,否则直接跳到 401635: mov $0x402558,%edi,也就是跳过了隐藏关。

因此,在 Phase 4 中需要额外输入的 1 个字符串就是 DrEvil

1
2
3
4
5
6
7
8
401617:   bf f8 24 40 00          mov    $0x4024f8,%edi
40161c: e8 ef f4 ff ff callq 400b10 <puts@plt>
401621: bf 20 25 40 00 mov $0x402520,%edi
401626: e8 e5 f4 ff ff callq 400b10 <puts@plt>
40162b: b8 00 00 00 00 mov $0x0,%eax
401630: e8 0d fc ff ff callq 401242 <secret_phase>
401635: bf 58 25 40 00 mov $0x402558,%edi
40163a: e8 d1 f4 ff ff callq 400b10 <puts@plt>

这段就是输出几行提示文本,待会儿我们可以直接看到。以及,调用函数 secret_phase 开启隐藏关。

8.2.2 开启隐藏关

运行到 Phase 4 时,在 gdb 中输入修改后的字符串:

1
7 0 DrEvil

继续跑完全部 6 个关卡,输出信息:

1
2
12Curses, you've found the secret phase!
But finding it and solving it are quite different...
8.2.3 观察函数 secret_phase

在 bomb.asm 中找到函数 secret_phase 对应的汇编语句:

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
<secret_phase>:
401242: 53 push %rbx
401243: e8 56 02 00 00 callq 40149e <read_line>
401248: ba 0a 00 00 00 mov $0xa,%edx
40124d: be 00 00 00 00 mov $0x0,%esi
401252: 48 89 c7 mov %rax,%rdi
401255: e8 76 f9 ff ff callq 400bd0 <strtol@plt>
40125a: 48 89 c3 mov %rax,%rbx
40125d: 8d 40 ff lea -0x1(%rax),%eax
401260: 3d e8 03 00 00 cmp $0x3e8,%eax
401265: 76 05 jbe 40126c <secret_phase+0x2a>
401267: e8 ce 01 00 00 callq 40143a <explode_bomb>
40126c: 89 de mov %ebx,%esi
40126e: bf f0 30 60 00 mov $0x6030f0,%edi
401273: e8 8c ff ff ff callq 401204 <fun7>
401278: 83 f8 02 cmp $0x2,%eax
40127b: 74 05 je 401282 <secret_phase+0x40>
40127d: e8 b8 01 00 00 callq 40143a <explode_bomb>
401282: bf 38 24 40 00 mov $0x402438,%edi
401287: e8 84 f8 ff ff callq 400b10 <puts@plt>
40128c: e8 33 03 00 00 callq 4015c4 <phase_defused>
401291: 5b pop %rbx
401292: c3 retq
401293: 90 nop
401294: 90 nop
401295: 90 nop
401296: 90 nop
401297: 90 nop
401298: 90 nop
401299: 90 nop
40129a: 90 nop
40129b: 90 nop
40129c: 90 nop
40129d: 90 nop
40129e: 90 nop
40129f: 90 nop

401243: callq 40149e 调用函数 read_line,其返回值(即输入的一行字符串 str)保存在 %rax 寄存器。

%rax = str

401248: mov $0xa,%edx 和 40124d: mov $0x0,%esi 将 %edx 和 %esi 寄存器分别设置为 100

%esi = 0
%edx = 10

400e37: mov %rax,%rdi 将 %rax 寄存器保存的地址传给了 %rdi 寄存器。

%rdi = %rax = str

401255: callq 400bd0 调用系统函数 strtol。可以推测出这个函数的作用是将字符串转化为整数,但我对它的参数用法不是很了解。查阅资料得,传入的第 1 个参数 %rdi 是被用来解析的字符串的地址 str,第 2 个参数 %esi 是字符串中需要解析部分的结束地址(这里我们传入的是 NULL,表示不使用这个参数),第 3 个参数 %edx 是这个整数的底数(这里我们传入的是 10,表示十进制)[^7]。最后函数返回值保存在 %rax 寄存器中。

总之,这部分的作用就是读入一个多位的整数。

%rax = num

其中,num 表示输入的字符串解析得到的多位整数。

400e37: mov %rax,%rbx 和 40125d: lea -0x1(%rax),%eax 将 %rax 的值传给了 %rbx 寄存器,然后 %rax 的值减 1。

%rbx = %rax = num
%eax = %rax - 1 = num - 1

401260: cmp $0x3e8,%eax 和 401265: jbe 40126c 判断 %eax 的值是否不超过 0x3e8,是则直接跳到 40126c: mov %ebx,%esi,否则执行 40143a: callq 40143a 引爆炸弹。

因此,输入的整数应当不超过 1001(无符号数)。

40126c: mov %ebx,%esi 和 40126e: mov $0x6030f0,%edi 将 %ebx 的值传给了 %esi 寄存器,将地址 0x6030f0 传给了 %edi 寄存器。

%edi = 0x6030f0
%esi = %ebx = num

401273: callq 401204 调用函数 fun7,也就是本关的主体部分。

401278: cmp $0x2,%eax 和 40127b: je 401282 判断函数 fun7 的返回值是否为 2,是则直接跳到 401282: mov $0x402438,%edi,否则执行 40143a: callq 40143a 引爆炸弹。

因此,函数 fun7 的返回值应当为 2

之后就是输出一行提示文本,以及一些收尾工作。

8.2.4 观察函数 fun7

在 bomb.asm 中找到函数 fun7 对应的汇编语句:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<fun7>:
401204: 48 83 ec 08 sub $0x8,%rsp
401208: 48 85 ff test %rdi,%rdi
40120b: 74 2b je 401238 <fun7+0x34>
40120d: 8b 17 mov (%rdi),%edx
40120f: 39 f2 cmp %esi,%edx
401211: 7e 0d jle 401220 <fun7+0x1c>
401213: 48 8b 7f 08 mov 0x8(%rdi),%rdi
401217: e8 e8 ff ff ff callq 401204 <fun7>
40121c: 01 c0 add %eax,%eax
40121e: eb 1d jmp 40123d <fun7+0x39>
401220: b8 00 00 00 00 mov $0x0,%eax
401225: 39 f2 cmp %esi,%edx
401227: 74 14 je 40123d <fun7+0x39>
401229: 48 8b 7f 10 mov 0x10(%rdi),%rdi
40122d: e8 d2 ff ff ff callq 401204 <fun7>
401232: 8d 44 00 01 lea 0x1(%rax,%rax,1),%eax
401236: eb 05 jmp 40123d <fun7+0x39>
401238: b8 ff ff ff ff mov $0xffffffff,%eax
40123d: 48 83 c4 08 add $0x8,%rsp
401241: c3 retq

401217 和 40122d: callq 401204 都调用了函数 fun7 自身,可见这是一个递归函数。

试译成 C 语言代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// p_node in %rdi, target in %esi
int fun7(int* p_node, int target) {
if (p_node == 0)
return 0xffffffff;
cur_num = *p_node; // cur_num in %edx
if (cur_num > target) {
p_node = *(p_node + 1);
result = fun7(p_node, target); // result in %eax
return result * 2;
} else if (cur_num == target) {
return 0;
} else { // cur_num < target
result = 0;
p_node = *(p_node + 2);
result = fun7(p_node, target);
return result * 2 + 1;
}
}

如此这个递归函数的作用就很清晰了。

8.2.5 确定输入的整数

接下来,使用 gdb 查看作为参数传入的地址 0x6030f0 开始的连续内存中的值(经试验可知第 60 个 8 bytes 之后的地址中存放的都是无关数据,因此这里只需显示前 60 个地址):

1
x/60xg 0x6030f0

输出信息:

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
0x6030f0 <n1>:   0x0000000000000024      0x0000000000603110
0x603100 <n1+16>: 0x0000000000603130 0x0000000000000000
0x603110 <n21>: 0x0000000000000008 0x0000000000603190
0x603120 <n21+16>: 0x0000000000603150 0x0000000000000000
0x603130 <n22>: 0x0000000000000032 0x0000000000603170
0x603140 <n22+16>: 0x00000000006031b0 0x0000000000000000
0x603150 <n32>: 0x0000000000000016 0x0000000000603270
0x603160 <n32+16>: 0x0000000000603230 0x0000000000000000
0x603170 <n33>: 0x000000000000002d 0x00000000006031d0
0x603180 <n33+16>: 0x0000000000603290 0x0000000000000000
0x603190 <n31>: 0x0000000000000006 0x00000000006031f0
0x6031a0 <n31+16>: 0x0000000000603250 0x0000000000000000
0x6031b0 <n34>: 0x000000000000006b 0x0000000000603210
0x6031c0 <n34+16>: 0x00000000006032b0 0x0000000000000000
0x6031d0 <n45>: 0x0000000000000028 0x0000000000000000
0x6031e0 <n45+16>: 0x0000000000000000 0x0000000000000000
0x6031f0 <n41>: 0x0000000000000001 0x0000000000000000
0x603200 <n41+16>: 0x0000000000000000 0x0000000000000000
0x603210 <n47>: 0x0000000000000063 0x0000000000000000
0x603220 <n47+16>: 0x0000000000000000 0x0000000000000000
0x603230 <n44>: 0x0000000000000023 0x0000000000000000
0x603240 <n44+16>: 0x0000000000000000 0x0000000000000000
0x603250 <n42>: 0x0000000000000007 0x0000000000000000
0x603260 <n42+16>: 0x0000000000000000 0x0000000000000000
0x603270 <n43>: 0x0000000000000014 0x0000000000000000
0x603280 <n43+16>: 0x0000000000000000 0x0000000000000000
0x603290 <n46>: 0x000000000000002f 0x0000000000000000
0x6032a0 <n46+16>: 0x0000000000000000 0x0000000000000000
0x6032b0 <n48>: 0x00000000000003e9 0x0000000000000000
0x6032c0 <n48+16>: 0x0000000000000000 0x0000000000000000

结合 8.2.4 节译出的函数 fun7 代码,可以发现这是一个二叉树。二叉树中每个结点是一个结构体,结点所在的地址指向的是数据 val,加上 0x8 后指向的是指针 left,加上 0x10 后指向的是指针 right

因此,fun7 函数中的 *p_nodep_node->val*(p_node + 1)p_node->left*(p_node + 2)p_node->right

根据之前 gdb 的输出信息绘制二叉树(数据已转化为十进制):

1
2
3
4
5
6
7
            36
/ \
8 50
/ \ / \
6 22 45 107
/ \ / \ / \ / \
1 7 20 35 40 47 99 1001

可以发现这其实是一个 BST(Binary Search Tree,二叉查找树),而函数 fun7 的作用为:

  1. 如果当前结点为 NULL,则返回 0xffffffff(直接爆了);
  2. 如果找到了 target,则返回 0
  3. 如果当前结点的值大于 target,则继续搜索左子树,返回时将左子树的返回值 * 2
  4. 如果当前结点的值小于 target,则继续搜索右子树,返回时将右子树的返回值 * 2 + 1

起始时从根结点 36 开始查找,现在问题转化为:求 target 为何值时,最终的返回值为 2

由之前的分析,返回值为 2 的条件为:

  1. 最终找到 target 的值(return 0),此后可以沿右路返回任意次(return 0);
  2. 然后沿左路返回(return 1);
  3. 最后沿右路返回(return 2)。

满足条件的结点的值有 2 个:22, 20,即为所求。

于是得到本关的 2 个解:22, 20

8.2.6 测试

这里以 22 为例,在 gdb 中输入 Secret phase 的密码:

1
22

输出信息:

1
2
12Wow! You've defused the secret stage!
Congratulations! You've defused the bomb!