A CS Student's Odyssey
0%

二进制炸弹实验（逆向工程）

发表于 更新于 分类于 ，
该实验的内容主要为根据可执行文件反汇编生成的汇编代码，逆向推测出C源程序的功能，得到C程序的结构。根据汇编代码推测出C源程序的switch结构、递归函数、单链表、二叉树等。

二进制炸弹实验

实验的内容是，对给定的可执行文件，输入指定的字符串，然后程序正常退出。由于源程序未知，因此需要反汇编将可执行文件生成汇编程序，再通过汇编程序逆向分析出源程序。程序由多个关卡组成，如果每一个关卡输入的字符串错误，炸弹就会爆炸，程序异常退出。

第一关：字符串比较

C程序

1
2
3
input = read_line();                /* Get input                   */
phase_1(input);                 /* Run the phase               */
phase_defused();                /* Drat!  They figured it out!

汇编程序

1
2
3
4
5
6
7
8
9
10
11
12
13
  400e32:	e8 67 06 00 00       	call   40149e <read_line>
  400e37:	48 89 c7             	mov    %rax,%rdi
  400e3a:	e8 a1 00 00 00       	call   400ee0 <phase_1>

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       	call   401338 <strings_not_equal>
  400eee:	85 c0                	test   %eax,%eax
  400ef0:	74 05                	je     400ef7 <phase_1+0x17>
  400ef2:	e8 43 05 00 00       	call   40143a <explode_bomb>
  400ef7:	48 83 c4 08          	add    $0x8,%rsp
  400efb:	c3                   	ret

题解

0x400ee9处的代码调用了strings_not_equal子程序，应该是字符串比较函数，函数的参数为%rdi和%rsi，其中%rdi为进入phase_1函数之前就从read_line函数获取到的字符串地址。所以%rsi为比较的字符串地址，打印0x402400处的字符串：

1
x/s 0x402400

结果如下：

1
2
(gdb) x/s 0x402400
0x402400:	"Border relations with Canada have never been better."

因此第一题的答案为：

1
Border relations with Canada have never been better.

第二关：循环结构

汇编程序

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

题解

观察read_six_numbers函数，是调用sscanf函数读取6个数字，并将读取到的数字保存在栈中。首先比较第一个数字：cmpl $0x1,(%rsp)，如果不相等就会调用explode_bomb函数，炸弹爆炸，因此第一个数字一定是1。
接下来比较第二个数字：cmp %eax,(%rbx)，此时%rbx的值为%rsp + 0x4(由0x400f30所得),保存的就是第二个数字，而%eax的值为2倍的-0x4(%rbx)的值，而-0x4(%rbx)指向第一个参数，因此第二个数为2。
比较第三个数字：cmp %rbp,%rbx，此时%rbp == %rsp + 0x18而%rsp == 0x08指向第三个数字，如果%rsp和%rbp相等，那么就会跳转到0x400f3c处的指令清除栈帧(add $0x28,%rsp)然后返回函数，否则就会继续跳转到0x400f17处，并且%rbx递增4。由于0x400f17代码的功能是比较当前数字是否为前一个数字的2倍，因此我们可以知道，6个数字分别为1、2、4、8、16、32。
因此第二题答案为：

1
1 2 4 8 16 32

第三关：switch结构

汇编代码

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       	call   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       	call   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 	jmp    *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       	call   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       	call   40143a <explode_bomb>
  400fc9:	48 83 c4 18          	add    $0x18,%rsp
  400fcd:	c3                   	ret

题解

观察到0x400f5b处为sscanf函数，且0x400f51处有mov $0x4025cf,%esi代码，向sscanf函数传递第二个参数，打印0x4025cf处的字符串得到：

1
2
(gdb) x/s 0x4025cf
0x4025cf:	"%d %d"

因此第三关要向程序输入两个数字。第二第三行代码lea 0xc(%rsp),%rcx和lea 0x8(%rsp),%rdx暗示sscanf函数很有可能把两个输入的数字保存在内存地址0x8(%rsp)和0xc(%rsp)处，因此在sscannf函数的后一行0x400f60设置断点:

1
(gdb) b *0x400f60

然后在第3步向程序输入21、23这两个数字，程序运行到这个断点时，打印栈指针的值并打印0x8(%rsp)和0xc(%rsp)处的值：

1
2
3
4
5
6
(gdb) p/x $rsp
$1 = 0x7fffffffe020
(gdb) p *0x7fffffffe028
$2 = 21
(gdb) p *0x7fffffffe02c
$3 = 23

因此可以知道第一个参数保存在0x8(%rsp)，第二个参数保存在0xc(%rsp)处。0x400f6a处的代码cmpl $0x7,0x8(%rsp)以及下一行的ja指令，说明第一个参数必须小于等于7,否则爆炸。
接下来两条指令 mov 0x8(%rsp),%eax和jmp *0x402470(,%rax,8)，第二条jmp指令很明显是一条在switch结构散转表中进行跳转的指令，将输入的第一个数字作为散转表的参数，打印0x402470处的散转表得到如下结果：

1
2
3
4
5
(gdb) x/8gx 0x402470
0x402470:	0x0000000000400f7c	0x0000000000400fb9
0x402480:	0x0000000000400f83	0x0000000000400f8a
0x402490:	0x0000000000400f91	0x0000000000400f98
0x4024a0:	0x0000000000400f9f	0x0000000000400fa6

再观察散传标跳转后面几条指令，都是先将一个值赋给%rax然后跳转到0x400fbe处，执行cmp 0xc(%rsp),%eax指令，将第二个数字与刚被值赋的%eax比较，如果不同则会爆炸，因此可能的答案有多种，例如，如果第一个数字为1，jmp指令执行后将跳转到0x400fb9处，将%eax与0x137即311比较，所有的答案可能为：

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

第四关：递归程序

汇编程序

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
0000000000400fce <func4>:                            %edi = x, %esi = a, %edx = b
  400fce:	48 83 ec 08          	sub    $0x8,%rsp
  400fd2:	89 d0                	mov    %edx,%eax     %eax = b
  400fd4:	29 f0                	sub    %esi,%eax     %eax = b - a
  400fd6:	89 c1                	mov    %eax,%ecx     %ecx = b - a
  400fd8:	c1 e9 1f             	shr    $0x1f,%ecx    %ecx = (b - a) >> 31 = 0 or 1;
  //如果b < a那么右移的结果为1，下面仅考虑b >= a
  400fdb:	01 c8                	add    %ecx,%eax     %eax = (b - a);
  400fdd:	d1 f8                	sar    %eax          %eax = (b - a) / 2;
  400fdf:	8d 0c 30             	lea    (%rax,%rsi,1),%ecx   %ecx = (a + b) / 2;
  400fe2:	39 f9                	cmp    %edi,%ecx            if(x >= (a + b) / 2);
  400fe4:	7e 0c                	jle    400ff2 <func4+0x24>
  400fe6:	8d 51 ff             	lea    -0x1(%rcx),%edx      %edx =  (a + b) / 2 - 1;
  400fe9:	e8 e0 ff ff ff       	call   400fce <func4>
  400fee:	01 c0                	add    %eax,%eax
  400ff0:	eb 15                	jmp    401007 <func4+0x39>
  
  400ff2:	b8 00 00 00 00       	mov    $0x0,%eax            %eax = 0
  400ff7:	39 f9                	cmp    %edi,%ecx            %ecx = (a+b)/2, %edi = x
  400ff9:	7d 0c                	jge    401007 <func4+0x39>  if(x<=(a+b)/2) return 0;
  400ffb:	8d 71 01             	lea    0x1(%rcx),%esi       %esi = (a+b)/2 + 1;
  400ffe:	e8 cb ff ff ff       	call   400fce <func4>
  401003:	8d 44 00 01          	lea    0x1(%rax,%rax,1),%eax return 2*func4(x, (a+b)/2 + 1, b) + 1;
  401007:	48 83 c4 08          	add    $0x8,%rsp
  40100b:	c3                   	ret  

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

题解

第四关同样也是先读取两个数字，第一个参数保存在0x8(%rsp)，第二个参数保存在0xc(%rsp)处。紧接着执行cmpl $0xe,0x8(%rsp)指令和jbe指令，只有第一个数字小于等于0xe即14才会跳过explode_bomb函数，不会触发爆炸。
接下来调用fun4函数，在调用前，向函数传递的三个参数依次分别为：%edi保存第一个数字的值，%esi的值为0，%edx的值为14。调用函数后的返回值必须为0才不会爆炸，同时注意到0x401051处的指令cmpl $0x0,0xc(%rsp)和下一条的je指令，得到第二个数字必须为0。
接下来求解第一个数字。带注释的func4函数如上所示，其中a = 0, b = 14。可以得到等价的C程序：

1
2
3
4
5
6
7
8
9
int func4(int x, int a, int b)
{
  if(x >= (a + b) / 2) 
  {
    if(x <= (a + b) / 2) return 0;
    else return 2 * func4(x, (a + b) / 2 + 1, b) + 1;
  }
  else return 2 * func4(x, a, (a + b) / 2 - 1);
}

将上述函数变形得到等价的函数：

1
2
3
4
5
6
int func4(int x, int a, int b)
{
  if(x == (a + b) / 2) return 0;
  else if(x > (a + b) / 2) return 2 * func4(x, (a + b) / 2 + 1, b) + 1;
  else return 2 * func4(x, a, (a + b) / 2 - 1);
}

由于func4函数的返回值必须为0，因此不能走函数内第二行的分支，否则return 2 * func4(x, a, b) + 1返回的必然是一个大于0的值。而a = 0, b = 14，因此x能取的值可以为(a + b) / 2 = 7，如果x!=7，那么x必然小于7，然后执行2 * func4(x, 0, 6)，因此x能取得第二个值为3，若不等于3，则x必然小于3，然后执行2 * func4(x, 0, 2)，因此x能取得第三个值为1，若不等于1，则x必然小于1，然后执行2 * func4(x, 0, 0)，因此x能取得第四个值为0。
因此答案为：

1
2
3
4
7 0
3 0
1 0
0 0

其实完整的C程序应该是：

1
2
3
4
5
6
7
8
9
10
11
12
int func4(int x, int a, int b)
{
  int i = b - a;
  i = (i + i >> 31) / 2;
  i= i + a;
  if(x >= i) 
  {
    if(x <= i) return 0;
    else return 2 * func4(x, i + 1, b) + 1;
  }
  else return 2 * func4(x, a, i - 1);
}

同样可以得到答案。

第五关：字符串ASCII码

汇编

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
0000000000401062 <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       	call   40131b <string_length>
  40107f:	83 f8 06             	cmp    $0x6,%eax
  401082:	74 4e                	je     4010d2 <phase_5+0x70>
  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>
  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>
  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

题解

输入字符串后会调用string_length函数检查字符串长度是否为6，因此输入的字符串长度必须为6。且字符串的起始地址为%rsp。最关键的是下面这一段函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
40108b:	0f b6 0c 03          	movzbl (%rbx,%rax,1),%ecx //%rbx => str, %rax = 0->5
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>

注意到0x4040bd处的指令是调用字符串比较函数，其中一个字符首地址为0x40245e，我们打印这个地址对应的字符串：

1
2
(gdb) x/s 0x40245e
0x40245e:	"flyers"

说明输入的字符串在经过一定的处理之后应该与”flyers”相等。我们在从第一行0x40108b处的指令开始看。其中%rbx指向字符串首地址，%rax的值从0增加到5作为变址寄存器取字符，并且只保留字符的低8位，然后movzbl 0x4024b0(%rdx),%edx指令将低8位的值作为下标，从0x4024b0地址处去取字符串。打印该地址处的字符串：

1
2
(gdb) x/s 0x4024b0
0x4024b0 <array.3449>:	"maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"

因此每次都要从这个字符串中取一个字符，最终组成”flyers”的字符串。那么每一次去取字符的下标依次为0x9、0xf、0xe、0x5、0x6、0x7。由于下标值为源输入字符串字符ASCII码值的低8位，因此源输入字符串字符的ASCII码值的高8位可以是2、3、4、5、6,因此答案为：

1
2
3
4
5
)/.%&'
9?>567
IONEFG
Y_^UVW
ionefg

第六关：单链表

汇编

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
89
90
91
92
93
94
95
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>
  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       	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
  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>
  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		node = node->left;
  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		//head node
  4011a9:	eb cb                	jmp    401176 <phase_6+0x82>
  
  4011ab:	48 8b 5c 24 20       	mov    0x20(%rsp),%rbx		%rbx = head
  4011b0:	48 8d 44 24 28       	lea    0x28(%rsp),%rax		%rax = %rsp + 0x28
  4011b5:	48 8d 74 24 50       	lea    0x50(%rsp),%rsi
  4011ba:	48 89 d9             	mov    %rbx,%rcx		%rcx = head
  
  									curNode = (%rsp + 0x20) 									
  4011bd:	48 8b 10             	mov    (%rax),%rdx		%rdx = nextNode
  4011c0:	48 89 51 08          	mov    %rdx,0x8(%rcx)		head->next = nextNode
  4011c4:	48 83 c0 08          	add    $0x8,%rax		nextNode++
  4011c8:	48 39 f0             	cmp    %rsi,%rax
  4011cb:	74 05                	je     4011d2 <phase_6+0xde>
  4011cd:	48 89 d1             	mov    %rdx,%rcx		%rcx = secNode
  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		%rax = head->next
  4011e3:	8b 00                	mov    (%rax),%eax		%eax = head->next->key
  4011e5:	39 03                	cmp    %eax,(%rbx)	     cmp head->next->key, head->key
  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>
  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                   	ret

题解

首先仍然是读取6个数字，并将读取到的数字保存在%rsp指向的内存地址处。注意到下面几行代码：

1
2
3
4
5
6
7
8
9
10
401100:	49 89 e5             	mov    %rsp,%r13
......
401106:	e8 51 03 00 00       	call   40145c <read_six_numbers>
......
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>

说明第一个数字小于等于6。接着的下面几行代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
40110e:	41 bc 00 00 00 00    	mov    $0x0,%r12d
......
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)       //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>

40114d:	49 83 c5 04          	add    $0x4,%r13
401151:	eb c1                	jmp    401114 <phase_6+0x20>

将后面5个数与第一个数进行比较，等于第一个数就会爆炸。由于0x40114d处的2条指令又会跳转到比较当前数字是否小于等于6的代码处，并且还会判断该数字后面的数字是否与他不相等，因此我们可以知道，总数输入6个数字，这6个数字都小于等于6,且互不相等。
接下来的这段代码：

1
2
3
4
5
6
7
8
9
10
11
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>

其功能是将0x7分别减去六个数字的值，并且保存在原来的内存位置之中。现在内存的视图如下：

地址 内容
0x20
0x1c
0x18
0x14 7-f
0x10 7-e
0x0c 7-d
0x08 7-c
0x04 7-b
0x00 7-a 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
401176:	48 8b 52 08          	mov    0x8(%rdx),%rdx		      //node = node->next;
40117a:	83 c0 01             	add    $0x1,%eax
40117d:	39 c8                	cmp    %ecx,%eax              //find 7-x th node
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         //head node

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              //the 1-st node?
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		      //head node
4011a9:	eb cb                	jmp    401176 <phase_6+0x82>

上面的代码两处都出现了0x6032d0地址，因此打印该地址处的信息：

1
2
(gdb) x 0x6032d0
0x6032d0 <node1>:	0x0000014c

因此该地址为node1节点的首地址。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(gdb) p/x *(node) 0x6032d0
$1 = {key = 0x10000014c, left_node = 0x6032e0, right_node = 0x2000000a8}
(gdb) p/x *(node) 0x2000000a8
Cannot access memory at address 0x2000000a8
(gdb) p/x *(node) 0x6032e0
$2 = {key = 0x2000000a8, left_node = 0x6032f0, right_node = 0x30000039c}
(gdb) x 0x6032e0
0x6032e0 <node2>:	0x000000a8
(gdb) p/x *(node) 0x6032f0
$3 = {key = 0x30000039c, left_node = 0x603300, right_node = 0x4000002b3}
(gdb) p/x *(node) 0x603300
$4 = {key = 0x4000002b3, left_node = 0x603310, right_node = 0x5000001dd}
(gdb) p/x *(node) 0x603310
$5 = {key = 0x5000001dd, left_node = 0x603320, right_node = 0x6000001bb}
(gdb) p/x *(node) 0x603320
$6 = {key = 0x6000001bb, left_node = 0x0, right_node = 0x0}

因此链表的结构为：

上面这部分代码的功能是依次找到第7-a、7-b、…、7-f个节点，并将该节点的地址保存在%rsp + 0x20为起始的地址中。因此内存视图为：

地址 内容
0x50 <-%rsi
0x48 node<7-f>
0x40 node<7-e>
0x38 node<7-d>
0x30 node<7-c>
0x28 node<7-b>
0x20 node<7-a>
0x1c
0x18
0x14 7-f
0x10 7-e
0x0c 7-d
0x08 7-c
0x04 7-b
0x00 7-a

再看下面这一段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
4011ab:	48 8b 5c 24 20       	mov    0x20(%rsp),%rbx		//%rbx = node<7-a>
4011b0:	48 8d 44 24 28       	lea    0x28(%rsp),%rax		//%rax = %rsp + 0x28
4011b5:	48 8d 74 24 50       	lea    0x50(%rsp),%rsi
4011ba:	48 89 d9             	mov    %rbx,%rcx		      //%rcx = node<7-a>

									                                      //cur = (%rsp+0x20) 		
4011bd:	48 8b 10             	mov    (%rax),%rdx		    //%rdx = nextNode
4011c0:	48 89 51 08          	mov    %rdx,0x8(%rcx)		  //cur->next = nextNode
4011c4:	48 83 c0 08          	add    $0x8,%rax		      //nextNode++
4011c8:	48 39 f0             	cmp    %rsi,%rax
4011cb:	74 05                	je     4011d2 <phase_6+0xde>
4011cd:	48 89 d1             	mov    %rdx,%rcx		      //%rcx = nextNode
4011d0:	eb eb                	jmp    4011bd <phase_6+0xc9>

上面这段代码的功能是将node<7-a>、node<7-b>、…、node<7-f>依次串成链表，于是得到：

再看下面的代码：

1
2
3
4
5
6
7
8
9
10
11
4011da:	bd 05 00 00 00       	mov    $0x5,%ebp
4011df:	48 8b 43 08          	mov    0x8(%rbx),%rax	//%rax = cur->next
4011e3:	8b 00                	mov    (%rax),%eax		//%eax = cur->next->key
4011e5:	39 03                	cmp    %eax,(%rbx)	  //cmp cur->next->key, cur->key
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>
......
401203:	c3                   	ret

其功能是比较当前节点的key值的低8字节与前一个节点的key值的低8字节进行比较，尤其注意mov (%rax),%eax和cmp %eax,(%rbx)说明只取key值的低8位。当前值不能小于前一个节点的值。由于单链表的key值的低8位依次为0x14c、0xa8、0x39c、0x2b3、0x1dd、0x1bb，因此链表只能为：

因此7-a、7-b、…、7-f对应的值依次为：3、4、5、6、1、2，所以答案为：

1
4 3 2 1 6 5

隐藏关卡：二叉树

如何进入隐藏关卡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
00000000004015c4 <phase_defused>:
  ...
  4015d8:	83 3d 81 21 20 00 06 	cmpl   $0x6,0x202181(%rip)        # 0x603760
  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       	call   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       	call   401338 <strings_not_equal>
  401613:	85 c0                	test   %eax,%eax
  401615:	75 1e                	jne    401635 <phase_defused+0x71>
  ...
  401630:	e8 0d fc ff ff       	call   401242 <secret_phase>

能够调用secret_phase函数，那么第一行0x4015d8代码处，0x202181(%rip)的值必须等于6，发现0x202181(%rip)的值就是0x603760，在这一行代码设置断点，发现每一关通过后，0x603760处的值都会加1,当来到第六关，打印这个值：

1
2
3
4
(gdb) p/x *0x603760
$1 = 0x6
(gdb) x 0x603760
0x603760 <num_input_strings>:	0x06

来到第六关后会调用sscanf函数，打印0x402619和0x603870处的内容可以得到：

1
2
3
4
(gdb) x/s 0x402619
0x402619:	"%d %d %s"
(gdb) x/s 0x603870
0x603870 <input_strings+240>:	"7 0"

事实上”7 0”字符串就是在第4关输入的字符串，在第4关之前，打印这两个地址处的内容：

1
2
3
4
(gdb) x/s 0x402619
0x402619:	"%d %d %s"
(gdb) x/s 0x603870
0x603870 <input_strings+240>:	""

就会发现0x603870处为空字符串，只有经过第4关才会向这个地址填充字符串。并且sscanf的返回值必须为3,因此第4关除了输入两个数字之外，还要输入一个字符串才能调用隐藏关卡，先随便输入一个字符串”hahaha”，因此第4关的时候输入： 7 0 hahaha。
继续往下看，发现程序调用了string_not_equal函数来比较字符串，因此必须保证0x402622处的字符串和0x10(%rsp)处的内容相等，打印这两个地址处的内容：

1
2
3
4
(gdb) x/s (0x10 + $rsp)
0x7fffffffdfd0:	"hahaha"
(gdb) x/s 0x402622
0x402622:	"DrEvil"

发现0x10(%rsp)指向的字符串就是第4关输入的两个数字之后的字符串，它应该等于”DrEvil”才会进入secret_phase阶段。因此第4关的完整答案为：

1
7 0 DrEvil or 3 0 DrEvil or 1 0 DrEvil or 0 0 DrEvil

隐藏关卡汇编程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
0000000000401242 <secret_phase>:
  401242:	53                   	push   %rbx
  401243:	e8 56 02 00 00       	call   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       	call   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       	call   40143a <explode_bomb>
  40126c:	89 de                	mov    %ebx,%esi
  40126e:	bf f0 30 60 00       	mov    $0x6030f0,%edi
  401273:	e8 8c ff ff ff       	call   401204 <fun7>
  401278:	83 f8 02             	cmp    $0x2,%eax		   //return value must be 2!!!
  40127b:	74 05                	je     401282 <secret_phase+0x40>
  40127d:	e8 b8 01 00 00       	call   40143a <explode_bomb>
  401282:	bf 38 24 40 00       	mov    $0x402438,%edi
  401287:	e8 84 f8 ff ff       	call   400b10 <puts@plt>
  40128c:	e8 33 03 00 00       	call   4015c4 <phase_defused>
  401291:	5b                   	pop    %rbx
  401292:	c3                   	ret

题解

首先调用read_line函数读取字符串，然后调用strtol函数转化为数字，注意strtol函数第三个参数%rdx的值为0xa说明是转化为10进制的数字。将转换后的值减去1,与0x3e8进行比较，不能低于这个值，否则炸弹爆炸，因此输入的值小于等于1001。随后调用fun7函数，在进入函数值前，两个参数分别为0x6030f0和输入的数字，并且fun7函数的返回值必须是2。打印0x6030f0处的值：

1
2
3
4
(gdb) x 0x6030f0
0x6030f0 <n1>:	0x00000024
(gdb) p/x *(node) 0x6030f0
$1 = {key = 0x24, left_node = 0x603110, right_node = 0x603130}

因此0x6030f0为节点n1的首地址。其数据结构应该是一个二叉树，整个二叉树节点的信息如下：

接下来看fun7函数，这是一个递归函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
0000000000401204 <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     //node = node->left
  401217:	e8 e8 ff ff ff       	call   401204 <fun7>
  40121c:	01 c0                	add    %eax,%eax
  40121e:	eb 1d                	jmp    40123d <fun7+0x39>
  401220:	b8 00 00 00 00       	mov    $0x0,%eax          //%edx = node->key
  401225:	39 f2                	cmp    %esi,%edx
  401227:	74 14                	je     40123d <fun7+0x39>
  401229:	48 8b 7f 10          	mov    0x10(%rdi),%rdi    //node = node->right
  40122d:	e8 d2 ff ff ff       	call   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                   	ret

转换成C函数应该是：

1
2
3
4
5
6
7
8
9
10
int fun7(struct Node* node, int x)
{
  if(node == NULL) return -1;
  if(node->key <= x)
  {
    if(node->key == x) return 0;
    else return 2 * fun7(node->right, x) + 1;
  }
  else return 2 * fun7(node->left, x);
}

由于返回值必须为2,因此找到x应该先进入root->left，再进入root->left->right，最后发现相等的值，返回0。因此x的值为0x16即22。
隐藏关卡的答案为：

1
22

总结一下，所有关卡的正确答案为：

1
2
3
4
5
6
7
Border relations with Canada have never been better.
1 2 4 8 16 32
0 207 or 1 311 or 2 707 or 3 256 or 4 389 or 5 206 or 6 682 or 7 327
7 0 DrEvil or 3 0 DrEvil or 1 0 DrEvil or 0 0 DrEvil
)/.%&' or 9?>567 or IONEFG or Y_^UVW or ionefg
4 3 2 1 6 5
22

运行结果为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
chu@chu:~/csapp/bomb$ ./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.
Phase 1 defused. How about the next one?
1 2 4 8 16 32
That's number 2.  Keep going!
2 707
Halfway there!
7 0 DrEvil
So you got that one.  Try this one.
ionefg
Good work!  On to the next...
4 3 2 1 6 5
Curses, you've found the secret phase!
But finding it and solving it are quite different...
22
Wow! You've defused the secret stage!
Congratulations! You've defused the bomb!