CSCPP——Bomb Lab Report

Bomb Lab

姓名:张钏楠

学号:SA21011017

实验介绍

本报告为中科大研究生课程计算机系统Lab2——Bomb Lab(参考CMU CSAPP Lab1 )的实验报告,主要记录实验 2 二进制炸弹拆解过程以及主要思考。Bomb Lab 对应课本第三章,根据 Randal 所说,这一章也是整本书最重要的章节,我们需要学习代码的机器表示并在这个层次进行问题思考与代码分析。有很多 High Level 觉得很复杂的事情(比如递归)在底层看并无复杂。学习本章的过程也更好的熟悉并理解机器代码以及和 C 语言的关系。

实验环境

Lenovo Laptop

  • CPU: AMD Ryzen 5 2.10GHz
  • RAM: 16GB
  • OS: Ubuntu 20.04

实验详解

Phase 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(gdb) disas phase_1
Dump of assembler code for function phase_1:
0x08048b80 <+0>: push %ebp
0x08048b81 <+1>: mov %esp,%ebp
0x08048b83 <+3>: sub $0x8,%esp
0x08048b86 <+6>: movl $0x8049928,0x4(%esp)
0x08048b8e <+14>: mov 0x8(%ebp),%eax
0x08048b91 <+17>: mov %eax,(%esp)
0x08048b94 <+20>: call 0x8049067 <strings_not_equal>
0x08048b99 <+25>: test %eax,%eax
0x08048b9b <+27>: je 0x8048ba2 <phase_1+34>
0x08048b9d <+29>: call 0x804962e <explode_bomb>
0x08048ba2 <+34>: leave
0x08048ba3 <+35>: ret
End of assembler dump.

阅读反汇编代码,我们发现0x08048b94 <phase_1+20>call 了 strings_not_equal,我们只需要找到比对的字符串。在栈中我们发现程序分配了空间给一个地址,合理猜测有可能是比对字符串的起始地址。我们使用 gdb 打印,x/s 0x8049928字符串内容。

答案

1
I am not part of the problem. I am a Republican.

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
27
28
(gdb) disas phase_2
Dump of assembler code for function phase_2:
0x08048ba4 <+0>: push %ebp
0x08048ba5 <+1>: mov %esp,%ebp
0x08048ba7 <+3>: sub $0x28,%esp
0x08048baa <+6>: lea -0x1c(%ebp),%eax
0x08048bad <+9>: mov %eax,0x4(%esp)
0x08048bb1 <+13>: mov 0x8(%ebp),%eax
0x08048bb4 <+16>: mov %eax,(%esp)
0x08048bb7 <+19>: call 0x8048fd4 <read_six_numbers>
0x08048bbc <+24>: movl $0x1,-0x4(%ebp)
0x08048bc3 <+31>: jmp 0x8048be3 <phase_2+63>
0x08048bc5 <+33>: mov -0x4(%ebp),%eax
0x08048bc8 <+36>: mov -0x1c(%ebp,%eax,4),%edx
0x08048bcc <+40>: mov -0x4(%ebp),%eax
0x08048bcf <+43>: dec %eax
0x08048bd0 <+44>: mov -0x1c(%ebp,%eax,4),%eax
0x08048bd4 <+48>: add $0x5,%eax
0x08048bd7 <+51>: cmp %eax,%edx
0x08048bd9 <+53>: je 0x8048be0 <phase_2+60>
0x08048bdb <+55>: call 0x804962e <explode_bomb>
0x08048be0 <+60>: incl -0x4(%ebp)
0x08048be3 <+63>: cmpl $0x5,-0x4(%ebp)
0x08048be7 <+67>: jle 0x8048bc5 <phase_2+33>
0x08048be9 <+69>: leave
0x08048bea <+70>: ret
End of assembler dump.

阅读反汇编代码,phase_2 前面阶段是输入六个整数。由0x08048bc3 <phase_2+31>的无条件 jump 到结尾和0x08048be7 <phase_2+67>的条件跳转 jle,为 while 循环的跳转至中间翻译。阅读中间的反汇编代码,观察判断是比较相邻输入的差是否为 5。所以只要满足+5 的等差数列就是符合条件的正确答案。

答案组合(多种)

1
2
3
1 6 11 16 21 26
250 255 260 265 270 275
...

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
38
39
40
41
42
43
44
45
46
(gdb) disas phase_3
Dump of assembler code for function phase_3:
0x08048beb <+0>: push %ebp
0x08048bec <+1>: mov %esp,%ebp
0x08048bee <+3>: sub $0x28,%esp
0x08048bf1 <+6>: movl $0x0,-0x8(%ebp)
0x08048bf8 <+13>: movl $0x0,-0x4(%ebp)
0x08048bff <+20>: lea -0x10(%ebp),%eax
0x08048c02 <+23>: mov %eax,0xc(%esp)
0x08048c06 <+27>: lea -0xc(%ebp),%eax
0x08048c09 <+30>: mov %eax,0x8(%esp)
0x08048c0d <+34>: movl $0x8049959,0x4(%esp)
0x08048c15 <+42>: mov 0x8(%ebp),%eax
0x08048c18 <+45>: mov %eax,(%esp)
0x08048c1b <+48>: call 0x8048868 <sscanf@plt>
0x08048c20 <+53>: mov %eax,-0x4(%ebp)
0x08048c23 <+56>: cmpl $0x1,-0x4(%ebp)
0x08048c27 <+60>: jg 0x8048c2e <phase_3+67>
0x08048c29 <+62>: call 0x804962e <explode_bomb>
0x08048c2e <+67>: mov -0xc(%ebp),%eax
0x08048c31 <+70>: mov %eax,-0x14(%ebp)
0x08048c34 <+73>: cmpl $0x7,-0x14(%ebp)
0x08048c38 <+77>: ja 0x8048c80 <phase_3+149>
0x08048c3a <+79>: mov -0x14(%ebp),%edx
0x08048c3d <+82>: mov 0x8049960(,%edx,4),%eax
0x08048c44 <+89>: jmp *%eax
0x08048c46 <+91>: addl $0x277,-0x8(%ebp)
0x08048c4d <+98>: subl $0x1b8,-0x8(%ebp)
0x08048c54 <+105>: addl $0x396,-0x8(%ebp)
0x08048c5b <+112>: subl $0x181,-0x8(%ebp)
0x08048c62 <+119>: addl $0x2a2,-0x8(%ebp)
0x08048c69 <+126>: subl $0x194,-0x8(%ebp)
0x08048c70 <+133>: addl $0x194,-0x8(%ebp)
0x08048c77 <+140>: subl $0x1a1,-0x8(%ebp)
0x08048c7e <+147>: jmp 0x8048c85 <phase_3+154>
0x08048c80 <+149>: call 0x804962e <explode_bomb>
0x08048c85 <+154>: mov -0xc(%ebp),%eax
0x08048c88 <+157>: cmp $0x5,%eax
0x08048c8b <+160>: jg 0x8048c95 <phase_3+170>
0x08048c8d <+162>: mov -0x10(%ebp),%eax
0x08048c90 <+165>: cmp %eax,-0x8(%ebp)
0x08048c93 <+168>: je 0x8048c9a <phase_3+175>
0x08048c95 <+170>: call 0x804962e <explode_bomb>
0x08048c9a <+175>: leave
0x08048c9b <+176>: ret
End of assembler dump.

输入两个数,输入第一个参数应小于 7,default 情况为引爆炸弹。

整体表达式,case 从不同地方起始运算

1
2
3
4
  + 0x277 - 0x1b8 + 0x396 - 0x181 + 0x2a2 - 0x194 + 0x194 - 0x1a1
| | | | | | | |
case: 0 1 2 3 4 5 6 7
ans: 981 350 790 642 257 -417 -13(illegal)-417(illegal)

答案组合(有多种),但注意尾部还有一个判断参数 1 是否大于 5 的限制:

1
2
3
4
5
6
0 981
1 350
2 790
3 642
4 257
5 -417

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
24
(gdb) disas phase_4
Dump of assembler code for function phase_4:
0x08048cd0 <+0>: push %ebp
0x08048cd1 <+1>: mov %esp,%ebp
0x08048cd3 <+3>: sub $0x28,%esp
0x08048cd6 <+6>: lea -0xc(%ebp),%eax
0x08048cd9 <+9>: mov %eax,0x8(%esp)
0x08048cdd <+13>: movl $0x8049980,0x4(%esp)
0x08048ce5 <+21>: mov 0x8(%ebp),%eax
0x08048ce8 <+24>: mov %eax,(%esp)
0x08048ceb <+27>: call 0x8048868 <sscanf@plt>
0x08048cf0 <+32>: mov %eax,-0x4(%ebp)
0x08048cf3 <+35>: cmpl $0x1,-0x4(%ebp)
0x08048cf7 <+39>: jne 0x8048d00 <phase_4+48>
0x08048cf9 <+41>: mov -0xc(%ebp),%eax
0x08048cfc <+44>: test %eax,%eax
0x08048cfe <+46>: jg 0x8048d05 <phase_4+53>
0x08048d00 <+48>: call 0x804962e <explode_bomb>
0x08048d05 <+53>: mov -0xc(%ebp),%eax
0x08048d08 <+56>: mov %eax,(%esp)
0x08048d0b <+59>: call 0x8048c9c <func4>
0x08048d10 <+64>: mov %eax,-0x8(%ebp)
0x08048d13 <+67>: cmpl $0x157,-0x8(%ebp)
0x08048d1a <+74>: je 0x8048d21 <phase_4+81>

根据反汇编0x8048d0b <phase_4+59>行和0x8048d13 <phase_4+67>行可知 phase 4 调用了一个递归函数fun4,将最后的返回结果与 0x157(十进制为 343)进行比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(gdb) disas func4
Dump of assembler code for function func4:
0x08048c9c <+0>: push %ebp
0x08048c9d <+1>: mov %esp,%ebp
0x08048c9f <+3>: sub $0x8,%esp
0x08048ca2 <+6>: cmpl $0x0,0x8(%ebp)
0x08048ca6 <+10>: jg 0x8048cb1 <func4+21>
0x08048ca8 <+12>: movl $0x1,-0x4(%ebp)
0x08048caf <+19>: jmp 0x8048ccb <func4+47>
0x08048cb1 <+21>: mov 0x8(%ebp),%eax
0x08048cb4 <+24>: dec %eax
0x08048cb5 <+25>: mov %eax,(%esp)
0x08048cb8 <+28>: call 0x8048c9c <func4>
0x08048cbd <+33>: mov %eax,%edx
0x08048cbf <+35>: mov %edx,%eax
0x08048cc1 <+37>: shl $0x3,%eax
0x08048cc4 <+40>: mov %eax,%ecx
0x08048cc6 <+42>: sub %edx,%ecx
0x08048cc8 <+44>: mov %ecx,-0x4(%ebp)
0x08048ccb <+47>: mov -0x4(%ebp),%eax
0x08048cce <+50>: leave
0x08048ccf <+51>: ret
End of assembler dump.

阅读fun4反汇编结果发现该函数判断输入参数小于等于 0 时,返回 1,否则递归调用fun4(x-1),得到的结果乘 7 后返回,相当于以下 c 代码:

1
2
3
4
5
6
7
8
9
int fun4(int x) {
int result= 1;
if (x<=0){
return result;
} else{
result = fun4(x-1);
return 7*result;
}
}

易知0x157 = 343 = 7^3,所以答案:

1
3

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
(gdb) disas phase_5
Dump of assembler code for function phase_5:
0x08048d23 <+0>: push %ebp
0x08048d24 <+1>: mov %esp,%ebp
0x08048d26 <+3>: sub $0x18,%esp
0x08048d29 <+6>: mov 0x8(%ebp),%eax
0x08048d2c <+9>: mov %eax,(%esp)
0x08048d2f <+12>: call 0x804903d <string_length>
0x08048d34 <+17>: mov %eax,-0x4(%ebp)
0x08048d37 <+20>: cmpl $0x6,-0x4(%ebp)
0x08048d3b <+24>: je 0x8048d42 <phase_5+31>
0x08048d3d <+26>: call 0x804962e <explode_bomb>
0x08048d42 <+31>: movl $0x0,-0x8(%ebp)
0x08048d49 <+38>: jmp 0x8048d6b <phase_5+72>
0x08048d4b <+40>: mov -0x8(%ebp),%edx
0x08048d4e <+43>: mov -0x8(%ebp),%eax
0x08048d51 <+46>: add 0x8(%ebp),%eax
0x08048d54 <+49>: movzbl (%eax),%eax
0x08048d57 <+52>: movsbl %al,%eax
0x08048d5a <+55>: and $0xf,%eax
0x08048d5d <+58>: movzbl 0x804a5c0(%eax),%eax
0x08048d64 <+65>: mov %al,-0xf(%ebp,%edx,1)
0x08048d68 <+69>: incl -0x8(%ebp)
0x08048d6b <+72>: cmpl $0x5,-0x8(%ebp)
0x08048d6f <+76>: jle 0x8048d4b <phase_5+40>
0x08048d71 <+78>: movb $0x0,-0x9(%ebp)
0x08048d75 <+82>: movl $0x8049983,0x4(%esp)
0x08048d7d <+90>: lea -0xf(%ebp),%eax
0x08048d80 <+93>: mov %eax,(%esp)
0x08048d83 <+96>: call 0x8049067 <strings_not_equal>
0x08048d88 <+101>: test %eax,%eax
0x08048d8a <+103>: je 0x8048d91 <phase_5+110>
0x08048d8c <+105>: call 0x804962e <explode_bomb>
0x08048d91 <+110>: leave
0x08048d92 <+111>: ret
End of assembler dump.

阅读汇编代码,读取一个字符串,如果长度不为 6 会直接引爆炸弹。后面紧跟一个循环。阅读循环体内容我们可以发现,每次将输入的字符串转化为一个偏移量。

1
2
3
0x08048d54 <+49>:	movzbl (%eax),%eax
0x08048d57 <+52>: movsbl %al,%eax
0x08048d5a <+55>: and $0xf,%eax

and $0xf,%eax,对字母对应的 ASCII 值只取最低字节作为偏移,然后从起始地址 0x804a5c0 加偏移取出新字符。调用 gdb 指令x/s 0x804a5c0查看,同时查看我们最终要比对的字符串。

1
2
3
4
(gdb) x/s 0x804a5c0
0x804a5c0 <array.2482>: "isrveawhobpnutfg\022\002"
(gdb) x/s 0x8049983
0x8049983: "saints"

可以确定我们要加的偏移量为15011131

根据前面计算偏移的规则(注意低字节为 0 的字母为p),我们的答案是

1
aepkma

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
(gdb) disas phase_6
Dump of assembler code for function phase_6:
0x08048e27 <+0>: push %ebp
0x08048e28 <+1>: mov %esp,%ebp
0x08048e2a <+3>: sub $0x18,%esp
0x08048e2d <+6>: movl $0x804a630,-0x8(%ebp)
0x08048e34 <+13>: mov 0x8(%ebp),%eax
0x08048e37 <+16>: mov %eax,(%esp)
0x08048e3a <+19>: call 0x8048858 <atoi@plt>
0x08048e3f <+24>: mov %eax,-0xc(%ebp)
0x08048e42 <+27>: mov -0x8(%ebp),%eax
0x08048e45 <+30>: mov %eax,(%esp)
0x08048e48 <+33>: call 0x8048d93 <fun6>
0x08048e4d <+38>: mov %eax,-0x8(%ebp)
0x08048e50 <+41>: mov -0x8(%ebp),%eax
0x08048e53 <+44>: mov %eax,-0x4(%ebp)
0x08048e56 <+47>: movl $0x1,-0x10(%ebp)
0x08048e5d <+54>: jmp 0x8048e6b <phase_6+68>
0x08048e5f <+56>: mov -0x4(%ebp),%eax
0x08048e62 <+59>: mov 0x8(%eax),%eax
0x08048e65 <+62>: mov %eax,-0x4(%ebp)
0x08048e68 <+65>: incl -0x10(%ebp)
0x08048e6b <+68>: cmpl $0x4,-0x10(%ebp)
0x08048e6f <+72>: jne 0x8048e5f <phase_6+56>
0x08048e71 <+74>: mov -0x4(%ebp),%eax
0x08048e74 <+77>: mov (%eax),%eax
0x08048e76 <+79>: cmp -0xc(%ebp),%eax
0x08048e79 <+82>: je 0x8048e80 <phase_6+89>
0x08048e7b <+84>: call 0x804962e <explode_bomb>
0x08048e80 <+89>: leave
0x08048e81 <+90>: ret
End of assembler dump.

其中0x08048e5f <phase_6+56>0x08048e65 <phase_6+62>很像列表的访问。p = p->next,寄存器保存指针值,指向位置偏移的值赋给指针自身。最后终止时指向值与 atoi 转换的结果是否一致。while 循环变量知循环了四轮。

fun6 的反汇编结果:

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
(gdb) disas fun6
Dump of assembler code for function fun6:
0x08048d93 <+0>: push %ebp
0x08048d94 <+1>: mov %esp,%ebp
0x08048d96 <+3>: sub $0x10,%esp
0x08048d99 <+6>: mov 0x8(%ebp),%eax
0x08048d9c <+9>: mov %eax,-0x10(%ebp)
0x08048d9f <+12>: mov 0x8(%ebp),%eax
0x08048da2 <+15>: mov %eax,-0x10(%ebp)
0x08048da5 <+18>: mov 0x8(%ebp),%eax
0x08048da8 <+21>: mov 0x8(%eax),%eax
0x08048dab <+24>: mov %eax,-0xc(%ebp)
0x08048dae <+27>: mov -0x10(%ebp),%eax
0x08048db1 <+30>: movl $0x0,0x8(%eax)
0x08048db8 <+37>: jmp 0x8048e1c <fun6+137>
0x08048dba <+39>: mov -0x10(%ebp),%eax
0x08048dbd <+42>: mov %eax,-0x4(%ebp)
0x08048dc0 <+45>: mov -0x10(%ebp),%eax
0x08048dc3 <+48>: mov %eax,-0x8(%ebp)
0x08048dc6 <+51>: jmp 0x8048dd7 <fun6+68>
0x08048dc8 <+53>: mov -0x4(%ebp),%eax
0x08048dcb <+56>: mov %eax,-0x8(%ebp)
0x08048dce <+59>: mov -0x4(%ebp),%eax
0x08048dd1 <+62>: mov 0x8(%eax),%eax
0x08048dd4 <+65>: mov %eax,-0x4(%ebp)
0x08048dd7 <+68>: cmpl $0x0,-0x4(%ebp)
0x08048ddb <+72>: je 0x8048deb <fun6+88>
0x08048ddd <+74>: mov -0x4(%ebp),%eax
0x08048de0 <+77>: mov (%eax),%edx
0x08048de2 <+79>: mov -0xc(%ebp),%eax
0x08048de5 <+82>: mov (%eax),%eax
0x08048de7 <+84>: cmp %eax,%edx
0x08048de9 <+86>: jg 0x8048dc8 <fun6+53>
0x08048deb <+88>: mov -0x8(%ebp),%eax
0x08048dee <+91>: cmp -0x4(%ebp),%eax
0x08048df1 <+94>: je 0x8048dfe <fun6+107>
0x08048df3 <+96>: mov -0x8(%ebp),%edx
0x08048df6 <+99>: mov -0xc(%ebp),%eax
0x08048df9 <+102>: mov %eax,0x8(%edx)
0x08048dfc <+105>: jmp 0x8048e04 <fun6+113>
0x08048dfe <+107>: mov -0xc(%ebp),%eax
0x08048e01 <+110>: mov %eax,-0x10(%ebp)
0x08048e04 <+113>: mov -0xc(%ebp),%eax
0x08048e07 <+116>: mov 0x8(%eax),%eax
0x08048e0a <+119>: mov %eax,-0x8(%ebp)
0x08048e0d <+122>: mov -0xc(%ebp),%edx
0x08048e10 <+125>: mov -0x4(%ebp),%eax
0x08048e13 <+128>: mov %eax,0x8(%edx)
0x08048e16 <+131>: mov -0x8(%ebp),%eax
0x08048e19 <+134>: mov %eax,-0xc(%ebp)
0x08048e1c <+137>: cmpl $0x0,-0xc(%ebp)
0x08048e20 <+141>: jne 0x8048dba <fun6+39>
0x08048e22 <+143>: mov -0x10(%ebp),%eax
0x08048e25 <+146>: leave
0x08048e26 <+147>: ret
End of assembler dump.

发现其中并没有根据参数调整的地方,GDB 运行至0x8048e74 <phase_6+77>,发现与地址0x804a5d0储存的值进行比较,打印为 530,所以我们最终答案为

1
530

实验结果

按照阶段依次输入上面分析的答案,运行结果截图如下: