csapp lab2 拆炸弹

发布于 1970年 01月 01日 08:00

1. 实验内容#

包含一个二进制应用bomb,需要根据该应用猜测程序的运行过程。程序主体包含了六个函数phase_1phase_6,每个函数会根据用户的输入做出反应,当输入符合要求时,会炸弹拆解成功,进入到下一步,否则炸弹爆炸,打印"Boom!!!"并退出

2. 预置知识#

二进制程序反汇编:objdump

gdb调试工具:gdb

寄存器信息(x86):注意用于传递参数的rdi/rsi/rdx/rcx以及r8 r9,储存返回值的寄存器rax

image-20220112193901217

3. 实验解答#

main函数分析#

  • if else的汇编实现:cmp+jne+jmp指令,cmp判断条件,jne进入下一个分支,jmp跳出if-else代码段
  • 函数调用的过程:
    • 在调用者中将函数参数传递到rdi rsi rdx rcx r8 r9等寄存器中
    • 调用callq进入函数
    • 在被调用函数中将需要使用的寄存器压栈,比如后文在phase_2函数中,先将rbp rbx压栈
    • 执行函数
    • 将压栈的寄存器弹出,恢复到初始状态
    • 返回,返回前会将函数的结果移动到寄存器rax中
Copy
0000000000400da0 <main>: 400da0: 53 push %rbx #后面需要使用,所以将旧值压栈 // 对应读取文件的三个判断 // edi为函数的第一个参数,也就是main函数的输入 // edi = 1: stdin输入 // edi = 2: 从文件读入 // 其他:报错 # 第一种情况 400da1: 83 ff 01 cmp $0x1,%edi 400da4: 75 10 jne 400db6 <main+0x16> 400da6: 48 8b 05 9b 29 20 00 mov 0x20299b(%rip),%rax # 603748 <stdin@@GLIBC_2.2.5> 400dad: 48 89 05 b4 29 20 00 mov %rax,0x2029b4(%rip) # 603768 <infile> 400db4: eb 63 jmp 400e19 <main+0x79> # 第二种情况 400db6: 48 89 f3 mov %rsi,%rbx 400db9: 83 ff 02 cmp $0x2,%edi 400dbc: 75 3a jne 400df8 <main+0x58> 400dbe: 48 8b 7e 08 mov 0x8(%rsi),%rdi 400dc2: be b4 22 40 00 mov $0x4022b4,%esi 400dc7: e8 44 fe ff ff callq 400c10 <fopen@plt> 400dcc: 48 89 05 95 29 20 00 mov %rax,0x202995(%rip) # 603768 <infile> 400dd3: 48 85 c0 test %rax,%rax 400dd6: 75 41 jne 400e19 <main+0x79> 400dd8: 48 8b 4b 08 mov 0x8(%rbx),%rcx 400ddc: 48 8b 13 mov (%rbx),%rdx 400ddf: be b6 22 40 00 mov $0x4022b6,%esi 400de4: bf 01 00 00 00 mov $0x1,%edi 400de9: e8 12 fe ff ff callq 400c00 <__printf_chk@plt> 400dee: bf 08 00 00 00 mov $0x8,%edi 400df3: e8 28 fe ff ff callq 400c20 <exit@plt> # 第三种情况 400df8: 48 8b 16 mov (%rsi),%rdx 400dfb: be d3 22 40 00 mov $0x4022d3,%esi 400e00: bf 01 00 00 00 mov $0x1,%edi 400e05: b8 00 00 00 00 mov $0x0,%eax 400e0a: e8 f1 fd ff ff callq 400c00 <__printf_chk@plt> 400e0f: bf 08 00 00 00 mov $0x8,%edi 400e14: e8 07 fe ff ff callq 400c20 <exit@plt> // 初始化bomb 400e19: e8 84 05 00 00 callq 4013a2 <initialize_bomb> // 开始6个阶段的测试 # 输出两句问候 # 0x402338:Welcome to my fiendish little bomb. You have 6 phases with # 0x402378:which to blow yourself up. Have a nice day! # 函数调用的过程就是先将参数移动到rdi rsi等寄存器中,然后使用callq命令进入函数,函数的执行结果放到rax中 400e1e: bf 38 23 40 00 mov $0x402338,%edi 400e23: e8 e8 fc ff ff callq 400b10 <puts@plt> 400e28: bf 78 23 40 00 mov $0x402378,%edi 400e2d: e8 de fc ff ff callq 400b10 <puts@plt> # phase_1 # 调用read_line函数,并将他的结果从rax移动到rdi中,作为下一个调用的函数的参数 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> # phase_2,同phase_1 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> # phase_3 400e60: bf ed 22 40 00 mov $0x4022ed,%edi 400e65: e8 a6 fc ff ff callq 400b10 <puts@plt> 400e6a: e8 2f 06 00 00 callq 40149e <read_line> 400e6f: 48 89 c7 mov %rax,%rdi 400e72: e8 cc 00 00 00 callq 400f43 <phase_3> 400e77: e8 48 07 00 00 callq 4015c4 <phase_defused> # phase_4 400e7c: bf 0b 23 40 00 mov $0x40230b,%edi 400e81: e8 8a fc ff ff callq 400b10 <puts@plt> 400e86: e8 13 06 00 00 callq 40149e <read_line> 400e8b: 48 89 c7 mov %rax,%rdi 400e8e: e8 79 01 00 00 callq 40100c <phase_4> 400e93: e8 2c 07 00 00 callq 4015c4 <phase_defused> # phase_5 400e98: bf d8 23 40 00 mov $0x4023d8,%edi 400e9d: e8 6e fc ff ff callq 400b10 <puts@plt> 400ea2: e8 f7 05 00 00 callq 40149e <read_line> 400ea7: 48 89 c7 mov %rax,%rdi 400eaa: e8 b3 01 00 00 callq 401062 <phase_5> 400eaf: e8 10 07 00 00 callq 4015c4 <phase_defused> # phase_6 400eb4: bf 1a 23 40 00 mov $0x40231a,%edi 400eb9: e8 52 fc ff ff callq 400b10 <puts@plt> 400ebe: e8 db 05 00 00 callq 40149e <read_line> 400ec3: 48 89 c7 mov %rax,%rdi 400ec6: e8 29 02 00 00 callq 4010f4 <phase_6> 400ecb: e8 f4 06 00 00 callq 4015c4 <phase_defused> # 正常退出,main函数返回0,也就是将0存到rax寄存器中 400ed0: b8 00 00 00 00 mov $0x0,%eax 400ed5: 5b pop %rbx 400ed6: c3 retq 400ed7: 90 nop 400ed8: 90 nop 400ed9: 90 nop 400eda: 90 nop 400edb: 90 nop 400edc: 90 nop 400edd: 90 nop 400ede: 90 nop 400edf: 90 nop

phase_1#

phase_1比较简单,中间只涉及一个string_not_equal函数,用户输入的内容input被放在了rdi寄存器中了(main函数的分析),然后将0x402400中的内容放到了第二个参数寄存器esi,那么说明这里面就是正确答案。使用print (char*)0x402400即可查看到,内容是Border relations with Canada have never been better.

指令:

  • test:对两个数做AND操作,当与操作的结果为0,将ZF置1
  • je:相当于jz,看ZF标志位,当ZF为0时跳转
Copy
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_2#

根据代码可知,phase_2中先将输入的字符串解析成为6个数字,然后使用循环判断它是不是1 2 4 6 8 16

问题:

为什么要在栈中分配40个字节作为read_six_numbers的返回值?

Copy
0000000000400efc <phase_2>: # 后面要用到rbp rbx寄存器,先压栈 400efc: 55 push %rbp 400efd: 53 push %rbx # 可以看出栈指针被当做第二个参数传递给了read_six_numbers函数,此处的28为十六进制数, 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> # cmp + je + jmp,典型的if-else结构 # 首先是将rsp中的值和1比,不相等时炸弹爆炸,说明存储的数字序列中第一个为1 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 # rbx对应array[i],eax对应array[i-1] 400f1a: 01 c0 add %eax,%eax # 对应2*array[i-1] 400f1c: 39 03 cmp %eax,(%rbx) # 2*array[i-1] == array[i]? 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> # 循环初始化,rbp充当end的角色,rbx为循环的变量,18对应十进制为24,刚好6个数字,说明该序列包含了6个数 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> # 恢复初始状态,read_six_numbers的结果也丢失了 400f3c: 48 83 c4 28 add $0x28,%rsp 400f40: 5b pop %rbx 400f41: 5d pop %rbp 400f42: c3 retq

进一步分析read_six_numbers函数:

看不懂了。。。。。反正就是调用了ssacnf函数,第二个参数时一个字符串"%d %d %d %d %d %d"

Copy
// 用于传递参数的rdi/rsi/rdx/rcx以及r8 r9,储存返回值的寄存器rax 000000000040145c <read_six_numbers>: 40145c: 48 83 ec 18 sub $0x18,%rsp # rdi中装的是input字符串,rsi装的是rsp栈指针 # rsi: rsp # rdx: rsp # rcx: rsp + 4 # r8: rsp + 12 # r9: rsp + 8 # rsp + 8: rsp + 20 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

phase_3#

依然是scanf+判断,第一个数字被放进rsp+8,第二个被放进rsp+12,这里出现了switch,注意jmpq的用法。最后的答案应该是:

0 0xcf, 1 0xc3, 2 0x100...

Copy
0000000000400f43 <phase_3>: # 在栈上开辟出24个字节的空间,依然是调用sscanf函数 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> # eax < 1会跳转,成功 400f65: e8 d0 04 00 00 callq 40143a <explode_bomb> 400f6a: 83 7c 24 08 07 cmpl $0x7,0x8(%rsp) # rsp+8 < 7会跳转,失败 400f6f: 77 3c ja 400fad <phase_3+0x6a> 400f71: 8b 44 24 08 mov 0x8(%rsp),%eax # 这相当于一个switch指令,跳转表的基地址为0x402470,每个单元的长度为8,按rax的值进行下标访问 # 不过也能猜到从400f7c就是我们要的 # (gdb) x/8a0x402470 # 0x402470: 0x400f7c <phase_3+57> 0x400fb9 <phase_3+118> # 0x402480: 0x400f83 <phase_3+64> 0x400f8a <phase_3+71> # 0x402490: 0x400f91 <phase_3+78> 0x400f98 <phase_3+85> # 0x4024a0: 0x400f9f <phase_3+92> 0x400fa6 <phase_3+99> 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 # rsp+12刚好是第二个数 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

phase_4#

Copy
000000000040100c <phase_4>: # 依然是sscanf函数 # 字符串格式为:%d %d,说明解析出来的是两个整数 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> # 小于或者等于时跳转,rsp + 8 < 14,否则会爆炸 401035: e8 00 04 00 00 callq 40143a <explode_bomb> # 用于传递参数的rdi/rsi/rdx/rcx以及r8 r9,储存返回值的寄存器rax # func4(rsp + 8, 0x0, 0xe) # 第一个数只能根据func4获得 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) # 关于第二个数,等于0的时候正常,说明第二个数是0 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

恶心。。。。竟然有一个递归函数

  • 递归函数的汇编写法
  • 注意寻址方式,见课本p121
  • lea的用法:将有效地址写入到寄存器,以lea (%rax,%rsi,1),%ecx为例,(%rax,%rsi,1)是一个比例变址寻址,表示MM[%rax + %rsi * 1]
  • 注意AT&T汇编的格式

根据汇编改写的递归程序可知,0~7都是答案

Copy
# func4(x, y, z) 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 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

y = 0, z = 14

mid = (y + z) / 2;

if(x <= mid) {

​ if(z >= x) {

​ return 0;

​ } else {

​ y = mid + 1;

​ return 2*func(x, y, z) + 1;

​ }

} else {

​ z = mid-1;

​ return 2*func(x, y, z);

}

edx: z, esi: y, edi: x, eax: tmp1, ecx: tmp2

phase_5#

Copy
# 用于传递参数的rdi/rsi/rdx/rcx以及r8 r9,储存返回值的寄存器rax 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 # eax = 0,计算字符串的长度 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> # 说明字符串的长度必须是6 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 # ch[i],将第一个字符取出来 40108f: 88 0c 24 mov %cl,(%rsp) 401092: 48 8b 14 24 mov (%rsp),%rdx # 将ch[i]放到rdx中 401096: 83 e2 0f and $0xf,%edx # 取低4位,可以忽略 #"maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?" #str # rsp空出了20个字节, 401099: 0f b6 92 b0 24 40 00 movzbl 0x4024b0(%rdx),%edx # str[ch[i]]的内容放到edx中,类似于整数数组 4010a0: 88 54 04 10 mov %dl,0x10(%rsp,%rax,1) # rdx,将上一个内容放到(rsp + i + 0x10) 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) # 在创建的字符串那加一个结束符,我们的新字符串是从rsp+10~rsp+16 4010b3: be 5e 24 40 00 mov $0x40245e,%esi # "flyers",比较函数的第二个参数 4010b8: 48 8d 7c 24 10 lea 0x10(%rsp),%rdi #比较函数的第一个参数,也就是新创建的字符串的首地址 # maduiersnfotvbyl # 9 15 14 5 6 7 --> char # 9 f e 5 6 7 (0x-7x) # 9: 水平制表符 结束符 ) 9 I Y i y # f: shift 单元分隔符 / ? O _ o DEL(Delete) # e: SO(Shift Out) RS(Record Separator) . > N ^ n ~ # 5: % 5 E U e u # 6: & 6 F V f v # 7: ' 7 G W g w 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

phase_6#

第一段:读6个数字,没什么可说,结果存在rsp到rsp+4*5(rsp+0x14)

Copy
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 callq 40145c <read_six_numbers>

第二段:注意到循环的翻译方式,这一段包含了两个循环。按顺序阅读,在401128到401130的自增+cmp+跳转,可以确定是循环的边界判断,r12d为一个循环的标志变量,看跳转的401153,直接进入到下一个流程,而401151直接跳转到401114,可以确定这是一个while循环,guard-done的翻译方式。

401114到401123包含了一个访存和判断,如果将r12d认为是循环变量i,rsp中存的数组记作array[],那这一块的代码框架为:

Copy
int i = 0; while(1) { int a = array[i]; if(a - 1 <= 5) bomb(); i = i + 1; if(i == 6) break; ... }

其中array[i]这一步其实是通过r13实现的,在外层循环中会对r13加4的操作,说明了数组中存放的是int型数据

看内层循环的边界判断401145到40114b,说明ebx存放的是内层的循环变量j,401132是j的初始化代码,初始值为i。401135到401140为内层循环的主体,401138读取了array[j],然后和a[i]比较,如果相等会爆炸。这样循环代码的框架可以被写成:

Copy
int i = 0; while(1) { int a = array[i]; if(a - 1 <= 5) bomb(); i = i + 1; if(i == 6) break; int j = i; for(int j = i; j + 1 <= 5; j++) { // 有点奇怪 if(array[j] == a) bomb(); } }
Copy
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> # 这个地方的自增+cmp+跳转,可以确定是循环的边界判断,r12d为一个循环的标志变量 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>

因此第二段的功能就是判断array[i]中每个数小于或者等于6,并且后一个和前一个不相等。

第三段:依然是一个循环,rsp+18为array最后一个元素结尾的位置,可以认为是array的end,r14为array的初始地址。循环的主体就三句话,功能是array[i] = 7 - array[i]。

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

第四段:还是包含了很多的循环,注意到401195是循环的出口。rsi用于rsp的访存,并且按4递增,可以将其看做是循环变量i。代码中包含了一个硬编码0x6032d0,查看内存发现是包含了node信息,每个node16B:

image-20220113215757789

从内存结构可以看出,从node的地址往后偏移8个字节就是next指针的位置,也就对应着mov 0x8(%rdx),%rdx。根据前文可知,array中存放了1 2 3 4 5 6,因此带入两个特殊值就能明白该函数的功能。

  • 当array[i] = 1。从40119d可知,此时会跳转到401183,直接将链表的首地址存到了(rsp+20)[i]处,这里需要注意(%rsp,%rsi,2)中2的含义,单位是32bit(4B)

  • 当array[i] = 3。会跳转到401176,eax初始值1,ecx为3,rdx的初始值为0x6032d0。对应的代码为:

    Copy
    do { rdx = rdx->next; eax += 1; }while(eax <= ecx);

    当循环结束时,rdx的值刚好是第3个节点的地址,然后将它存储到(rsp+20)[i]处。

因此这一部分代码个作用就是将节点的地址按照输入的数组的被7减之后的顺序存到rsp+20处,查看栈rsp+20处的内容:

image-20220113224428945

输入的数字为1 2 3 4 5 6,变换后为6 5 4 3 2 1,刚好是把节点的地址倒过来

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

第五段:

将rsp+20上的数组记作addr[0],addr[1],..., addr[5]

rbx-->addr[0], rax--> addr[1]的地址,rsi--> addr[6]的地址,充当循环的边界

rbx--> rcx

(rax)就是addr[1]--> rdx

rdx--> mem[rcx+0x8], rcx是addr[0],也就是将rdx赋值给地址为addr[0]的链表节点的next指针

rdx-->rcx,循环后rdx取下一个值

结束时rdx为addr[5],也就是链表的最后一个节点,只需要将其next指针设置为0

因此第五段是在重新排列链表

image-20220113235123645

Copy
# 初始化 4011ab: 48 8b 5c 24 20 mov 0x20(%rsp),%rbx # head 4011b0: 48 8d 44 24 28 lea 0x28(%rsp),%rax # head.next 4011b5: 48 8d 74 24 50 lea 0x50(%rsp),%rsi # end 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)

第六段:

一个链表的取value的过程,比较相邻的两个节点的value,要降序排列

原链表的节点为 14c 0a8 39c 2b3 1dd 1bb

降序排列的下标应该是3 4 5 6 1 2,变换前的应该是4 3 2 1 6 5

Copy
4011d9: 00 4011da: bd 05 00 00 00 mov $0x5,%ebp 4011df: 48 8b 43 08 mov 0x8(%rbx),%rax #rbx就是头结点的地址,偏移8就是next指针 4011e3: 8b 00 mov (%rax),%eax # next的value存到eax中 4011e5: 39 03 cmp %eax,(%rbx) # 比较next.value和value 4011e7: 7d 05 jge 4011ee <phase_6+0xfa> # value >=next.value跳转,也就意味着要降序排列 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> # 循环6次 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