CSAPP实验2:BombLab

发表于 | 分类于 |

实验简介

​ Bomb LAB 目的是熟悉汇编。

​ 一共有7关，六个常规关卡和一个隐藏关卡，每次我们需要输入正确的拆弹密码才能进入下一关，而具体的拆弹密码藏在汇编代码中。实验中的bomb实际上是一个程序的二进制文件，该程序由一系列phase组成，每个phase需要我们输入一个字符串，然后该程序会进行校验，如果输入的字符串不满足拆弹要求，那么就会打印BOOM!!!

​ 完成整个实验的思路是通过objdump对bomb进行反编译（objdump -d bomb > bomb.txt），获取所有的汇编代码。提取每个阶段对应的代码并借助gdb进行分析，逐一拆弹。

Github地址：Bomb Lab

准备

汇编复习

类型 语法 例子 备注
常量 符号$ 开头 $-42, $0x15213 一定要注意十进制还是十六进制
寄存器 符号 % 开头 %esi, %rax 可能存的是值或者地址
内存地址 括号括起来 (%rbx), 0x1c(%rax), 0x4(%rcx, %rdi, 0x1) 括号实际上是去寻址的意思

一些汇编语句与实际命令的转换：

指令 效果
mov %rbx, %rdx rdx = rbx
add (%rdx), %r8 r8 += value at rdx
mul $3, %r8 r8 *= 3
sub $1, %r8 r8--
lea (%rdx, %rbx, 2), %rdx rdx = rdx + rbx*2

比较与跳转是拆弹的关键，基本所有的字符判断就是通过比较来实现的，比方说 cmp b,a 会计算 a-b 的值，test b, a 会计算 a&b，注意运算符的顺序。例如

1
2
cmpl %r9, %r10
jg   8675309

等同于 if %r10 > %r9, jump to 8675309

各种不同的跳转：

指令 效果 指令 效果
jmp Always jump ja Jump if above(unsigned >)
je/jz Jump if eq / zero jae Jump if above / equal
jne/jnz Jump if !eq / !zero jb Jump if below(unsigned <)
jg Jump if greater jbe Jump if below / equal
jge Jump if greater / eq js Jump if sign bits is 1(neg)
jl Jump if less jns Jump if sign bit is 0 (pos)
jle Jump if less / eq x x

举几个例子

1
2
cmp $0x15213, %r12
jge deadbeef

若 %r12 >= 0x15213，则跳转到 0xdeadeef

1
2
cmp %rax, %rdi
jae 15213b

如果 %rdi 的无符号值大于等于 %rax，则跳转到 0x15213b

1
2
test %r8, %r8
jnz (%rsi)

如果 %r8 & %r8 不为零，那么跳转到 %rsi 存着的地址中。

x86-64寄存器规则： 默认函数的第一个参数是%rdi 第二个参数%rsi 第三个参数%rdx

反汇编

1
2
3
4
5
6
7
8
9
10
# 检查符号表
# 然后可以寻找跟 bomb 有关的内容
objdump -t bomb | less 

# 反编译
# 搜索 explode_bomb
objdump -d bomb > bomb.txt

# 显示所有字符
strings bomb | less

GDB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
gdb bomb
help	# 获取帮助

break explode_bomb	# 设置断点
break phase_1

run	# 开始运行

disas # 反汇编

info registers	# 查看寄存器内容

print $rsp	# 打印指定寄存器

stepi	# （单步跟踪进入）执行一行代码，如果函数调用，则进入该函数 可以使用s简化

n	# （单步跟踪） 执行一行代码，如果函数调用，则一并执行

x/4wd $rsp	# 检查寄存器或某个地址，查看内存地址里面的内容（常用）

用 ctl+c 可以退出，每次进入都要设置断点（保险起见），炸弹会用 sscanf 来读取字符串，了解清楚到底需要输入什么。

Phase 1

1
2
3
4
5
6
7
8
9
Dump of assembler code for function phase_1:
   0x0000000000400ee0 <+0>:    sub    $0x8,%rsp
   0x0000000000400ee4 <+4>:    mov    $0x402400,%esi
   0x0000000000400ee9 <+9>:    callq  0x401338 <strings_not_equal>
   0x0000000000400eee <+14>:    test   %eax,%eax
   0x0000000000400ef0 <+16>:    je     0x400ef7 <phase_1+23>
   0x0000000000400ef2 <+18>:    callq  0x40143a <explode_bomb>
   0x0000000000400ef7 <+23>:    add    $0x8,%rsp
   0x0000000000400efb <+27>:    retq

先 gdb bomb，然后设置断点 break explode_bomb 和 break phase_1

这段代码还是挺好理解的，保存Stack pointer,将$0x402400传给%esi,调用位于0x401338的strings_not_equal函数，比较%eax是否为0，不为零则调用explode_bomb函数，为零则返回设置断点 phase_1和explode_bomb，输入命令r运行会在断点处停下，此时随便输入一个字符串用于测试“abcd”，然后disas查看反汇编代码：=>箭号为当前运行的位置

mark

查看寄存器内容 info register，eax就是rax的低位用print $eax 打印出来，是一个地址用x/s $eax，查看出地址里的内容，发现是输入字符串

mark

用stepi 逐步执行，执行完 mov 之后，把地址中的内容传到%esi中，用print查看！得到字符串，这就是第一关的答案。退出后新建一个文本 touch sol.txt，方便之后输入

mark

mark

Phase 2

这次我们有了第一关的答案，进入gdb后设置好断点，和命令参数。

mark

试运行，在phase_1停住，然后continue，答案正确，触发 phase_2的断点，这次输入abc

mark

反汇编Phase2部分的代码

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
Dump of assembler code for function phase_2:
=> 0x0000000000400efc <+0>:    push   %rbp
   0x0000000000400efd <+1>:    push   %rbx
   0x0000000000400efe <+2>:    sub    $0x28,%rsp
   0x0000000000400f02 <+6>:    mov    %rsp,%rsi
   0x0000000000400f05 <+9>:    callq  0x40145c <read_six_numbers>   #读取6个数字
   0x0000000000400f0a <+14>:    cmpl   $0x1,(%rsp)                  #第一个数字和1比较，不相等则爆炸
   0x0000000000400f0e <+18>:    je     0x400f30 <phase_2+52>        #相等，跳转到<52>
   0x0000000000400f10 <+20>:    callq  0x40143a <explode_bomb>
   0x0000000000400f15 <+25>:    jmp    0x400f30 <phase_2+52>
   0x0000000000400f17 <+27>:    mov    -0x4(%rbx),%eax               #将(%rbx)前一个数字存到%eax
   0x0000000000400f1a <+30>:    add    %eax,%eax                     #%eax数字加倍
   0x0000000000400f1c <+32>:    cmp    %eax,(%rbx)                   #%eax和(%rbx)比较，=(%rbx)则跳过爆炸
   0x0000000000400f1e <+34>:    je     0x400f25 <phase_2+41>
   0x0000000000400f20 <+36>:    callq  0x40143a <explode_bomb>
   0x0000000000400f25 <+41>:    add    $0x4,%rbx                     #(%rbx)地址+4，下一个数字
   0x0000000000400f29 <+45>:    cmp    %rbp,%rbx                     #比较%rbp和%rbx，循环是否结束 
   0x0000000000400f2c <+48>:    jne    0x400f17 <phase_2+27>
   0x0000000000400f2e <+50>:    jmp    0x400f3c <phase_2+64>
   0x0000000000400f30 <+52>:    lea    0x4(%rsp),%rbx                #指向第2个数字，%rbx保存第2个数字地址
   0x0000000000400f35 <+57>:    lea    0x18(%rsp),%rbp               #0x18 = 0x0 + 4 bit * 6 个数字 
   0x0000000000400f3a <+62>:    jmp    0x400f17 <phase_2+27>
   0x0000000000400f3c <+64>:    add    $0x28,%rsp
   0x0000000000400f40 <+68>:    pop    %rbx
   0x0000000000400f41 <+69>:    pop    %rbp
   0x0000000000400f42 <+70>:    retq   
End of assembler dump.

根据Phase1,很敏感的会发现movl $0x4025c3, %esi这行。通过之前一样的方法，得到0x4025c3内存里的字符串

1
2
(gdb) x/s $esi
0x4025c3:    "%d %d %d %d %d %d

再根据bomb[0x40148a] <+46>: callq 0x400bf0 ; symbol stub for: __isoc99_sscanf这句，猜一下，立马就能联想到scanf("%d %d %d %d %d %d",a,b,c,d,e,f);，也就是说，输入的格式已经确定了。

解读出循环中，从1开始，是一个等比数列，公比为2。1 2 4 8 16 32

mark

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
Dump of assembler code for function phase_3:
=> 0x0000000000400f43 <+0>:    sub    $0x18,%rsp
   0x0000000000400f47 <+4>:    lea    0xc(%rsp),%rcx
   0x0000000000400f4c <+9>:    lea    0x8(%rsp),%rdx
   0x0000000000400f51 <+14>:    mov    $0x4025cf,%esi                
   0x0000000000400f56 <+19>:    mov    $0x0,%eax
   0x0000000000400f5b <+24>:    callq  0x400bf0 <__isoc99_sscanf@plt> # 调用函数sscanf
   0x0000000000400f60 <+29>:    cmp    $0x1,%eax                     # 说明%eax>1，即输入参数个数>1，跳过爆炸
   0x0000000000400f63 <+32>:    jg     0x400f6a <phase_3+39>
   0x0000000000400f65 <+34>:    callq  0x40143a <explode_bomb>
   0x0000000000400f6a <+39>:    cmpl   $0x7,0x8(%rsp)                # 说明第一个数0x8(%rsp)<7，否则爆炸
   0x0000000000400f6f <+44>:    ja     0x400fad <phase_3+106>
   0x0000000000400f71 <+46>:    mov    0x8(%rsp),%eax                # 第一个数存到%eax
   0x0000000000400f75 <+50>:    jmpq   *0x402470(,%rax,8)            # 跳转，起始地址0x402470+ rax*8（第一个数）内数据所指行数
   0x0000000000400f7c <+57>:    mov    $0xcf,%eax                    # case0：   0xcf = 207
   0x0000000000400f81 <+62>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f83 <+64>:    mov    $0x2c3,%eax                   # case2:    0x2c3
   0x0000000000400f88 <+69>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f8a <+71>:    mov    $0x100,%eax
   0x0000000000400f8f <+76>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f91 <+78>:    mov    $0x185,%eax
   0x0000000000400f96 <+83>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f98 <+85>:    mov    $0xce,%eax
   0x0000000000400f9d <+90>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f9f <+92>:    mov    $0x2aa,%eax
   0x0000000000400fa4 <+97>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400fa6 <+99>:    mov    $0x147,%eax
   0x0000000000400fab <+104>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400fad <+106>:    callq  0x40143a <explode_bomb>
   0x0000000000400fb2 <+111>:    mov    $0x0,%eax
   0x0000000000400fb7 <+116>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400fb9 <+118>:    mov    $0x137,%eax                # 1    0x137
   0x0000000000400fbe <+123>:    cmp    0xc(%rsp),%eax             # 比较第2个数
   0x0000000000400fc2 <+127>:    je     0x400fc9 <phase_3+134>
   0x0000000000400fc4 <+129>:    callq  0x40143a <explode_bomb>
   0x0000000000400fc9 <+134>:    add    $0x18,%rsp                 # rsp+24
   0x0000000000400fcd <+138>:    retq

查看地址内的内容，为输入格式，需要输入两个数，后面的 cmp $0x1,%eax 表明输入参数大于1个，

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

看到多个分片语句，反应类似siwtch语句，所以第一个数字是用来进行跳转的

mark

p/x 命令查看跳转表，可以看到

mark

用 p/x可以看跳转表的地址，但是没有x/s直观。用 x/s 命令可以查看跳转表，如case0，对应的就是<phase_3+57>，内容是$0xcf,%eax ，所以（0，207）就是一组输入，同理还可以得到其他的解

（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
(gdb) x/s *(0x402470)
0x400f7c <phase_3+57>:    "\270", <incomplete sequence \317> //0:0xcf
(gdb) x/s *(0x402470+8)
0x400fb9 <phase_3+118>:    "\270\067\001"    //1:0x137    
(gdb) x/s *(0x402470+16)
0x400f83 <phase_3+64>:    "\270\303\002"    //2:0x2c3
(gdb) x/s *(0x402470+24)
0x400f8a <phase_3+71>:    "\270"            //3:0x100
(gdb) x/s *(0x402470+32):
0x400f91 <phase_3+78>:    "\270\205\001"    //4:0x185
(gdb) x/s *(0x402470+40)
0x400f98 <phase_3+85>:    "\270", <incomplete sequence \316>    //5:0xce
(gdb) x/s *(0x402470+48)
0x400f9f <phase_3+92>:    "\270\252\002"    //6:0x2aa
(gdb) x/s *(0x402470+56)
0x400fa6 <phase_3+99>:    "\270G\001"       //7:0x147
(gdb) x/s *(0x402470+64)
0x7564616d:    <error: Cannot access memory at address 0x7564616d>

输入一组解，成功

mark

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
Dump of assembler code for function phase_4:
=> 0x000000000040100c <+0>:    sub    $0x18,%rsp
   0x0000000000401010 <+4>:    lea    0xc(%rsp),%rcx
   0x0000000000401015 <+9>:    lea    0x8(%rsp),%rdx
   0x000000000040101a <+14>:    mov    $0x4025cf,%esi            //%d %d
   0x000000000040101f <+19>:    mov    $0x0,%eax
   0x0000000000401024 <+24>:    callq  0x400bf0 <__isoc99_sscanf@plt>
   0x0000000000401029 <+29>:    cmp    $0x2,%eax                // 参数数量为2
   0x000000000040102c <+32>:    jne    0x401035 <phase_4+41>
   0x000000000040102e <+34>:    cmpl   $0xe,0x8(%rsp)           // 第一个参数<=14
   0x0000000000401033 <+39>:    jbe    0x40103a <phase_4+46>
   0x0000000000401035 <+41>:    callq  0x40143a <explode_bomb>
   0x000000000040103a <+46>:    mov    $0xe,%edx                //14
   0x000000000040103f <+51>:    mov    $0x0,%esi                //0
   0x0000000000401044 <+56>:    mov    0x8(%rsp),%edi           //a1
   0x0000000000401048 <+60>:    callq  0x400fce <func4>         //把a1,0,14分别作为参数传到func4
   0x000000000040104d <+65>:    test   %eax,%eax                //%eax！=0，爆炸，所以fun4调用后要使得%eax=0
   0x000000000040104f <+67>:    jne    0x401058 <phase_4+76>
   0x0000000000401051 <+69>:    cmpl   $0x0,0xc(%rsp)           //第二个数据为0
   0x0000000000401056 <+74>:    je     0x40105d <phase_4+81>
   0x0000000000401058 <+76>:    callq  0x40143a <explode_bomb>
   0x000000000040105d <+81>:    add    $0x18,%rsp
   0x0000000000401061 <+85>:    retq   
End of assembler dump.

跟上题一样，先看看可疑的0x4025cf中的内容

看到输入格式和上题一样都是两个整数。在执行 callq 0x400bf0 <__isoc99_sscanf@plt> 指令后，返回值（参数数量）存储于%eax，然后判断%eax是否等于2，若不等于则爆炸。否则执行cmpl $0xe,0x8(%rsp) ，该指令将输入的第一个数和常数0xe进行比较，如果第一个数>0xe，拆弹失败。否则跳转到0x40103a执行 

1
2
3
0x000000000040103a <+46>:    mov    $0xe,%edx                //14
0x000000000040103f <+51>:    mov    $0x0,%esi                //0
0x0000000000401044 <+56>:    mov    0x8(%rsp),%edi           //a1

这三条指令用来设置func4的参数，根据x86-64寄存器使用规范，第1,2,3,个参数分别存储在寄存器%edi，%esi，%edx中
在查看func4对应的代码之前，先观察执行callq 400fce <func4>指令之后phase_4的操作：test %eax,%eax指令检查%eax的值是否等于0，如果不等于0，则会引爆炸弹，否则执行指令cmpl $0x0,0xc(%rsp)，该指令将输入的第二个数与0做比较，如果相等，那么phase_4正常退出，拆弹成功。因此，phase_4的第二个输入值即为0。经过以上的分析，可以意识到phase_4的核心目标在于要让func4执行后，%eax的值等于0，这取决于输入的第一个数。接着需要分析func4执行的操作，其对应代码如下所示。

反汇编func4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
0000000000400fce <func4>:
  400fce:    48 83 ec 08              sub    $0x8,%rsp    //x = %edi    y = %esi   z = %edx
  400fd2:    89 d0                    mov    %edx,%eax    //
  400fd4:    29 f0                    sub    %esi,%eax    //t = z-y    t = %eax
  400fd6:    89 c1                    mov    %eax,%ecx    //
  400fd8:    c1 e9 1f                 shr    $0x1f,%ecx   //k=t>>31    t = %ecx
  400fdb:    01 c8                    add    %ecx,%eax    //t = t+k
  400fdd:    d1 f8                    sar    %eax         //t>>1
  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:(+0x24)    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:(+0x39)    48 83 c4 08       add    $0x8,%rsp
  40100b:    c3                       retq

在分析func4之前，不要忘了传递到func4的三个参数分别存储于寄存器%edi、%esi和%edx，其值分别为x(输入的第一个数)、0和14。在0x400fe9处执行了指令callq 400fce <func4>，因此func4很可能是个递归函数，我们将func4翻译成等价的C代码，如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void func4(int x, int y, int z) {
    int t = z - y;
    int k = t >> 31;
    t = (t + k) >> 1;
    k = t + y;
    if(k <= x) {
        t = 0;
        if(k >= x) {
            return;
        }else {
            y = k + 1;
            func4(x, y, z);
        }
    }else {
        z = k - 1;
        func4(x, y, z);
       }
}

func4的目的是要让函数退出后%eax的值为0，而在0x400ff2处mov $0x0,%eax显示的将%eax的值设置为0，该指令对应于C代码中的t = 0。并且，func4执行递归的退出条件为k == x，其中x对应于输入的第一个数，而k则可以通过一系列计算得到，由于y = 0且z = 14，易知k = 7，因此输入的第一个数即为7。将字符串7 0作为phase_4的输入，拆弹成功，如下图所示。

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
Dump of assembler code for function phase_5:
=> 0x0000000000401062 <+0>:    push   %rbx
   0x0000000000401063 <+1>:    sub    $0x20,%rsp
   0x0000000000401067 <+5>:    mov    %rdi,%rbx            //把字符串起始地址保存在%rbx中
   0x000000000040106a <+8>:    mov    %fs:0x28,%rax
   0x0000000000401073 <+17>:    mov    %rax,0x18(%rsp)
   0x0000000000401078 <+22>:    xor    %eax,%eax         //%eax清零
   0x000000000040107a <+24>:    callq  0x40131b <string_length>
   0x000000000040107f <+29>:    cmp    $0x6,%eax         //字符串输入长度=6
   0x0000000000401082 <+32>:    je     0x4010d2 <phase_5+112>
   0x0000000000401084 <+34>:    callq  0x40143a <explode_bomb>
   0x0000000000401089 <+39>:    jmp    0x4010d2 <phase_5+112>
   0x000000000040108b <+41>:    movzbl (%rbx,%rax,1),%ecx    //
   0x000000000040108f <+45>:    mov    %cl,(%rsp)
   0x0000000000401092 <+48>:    mov    (%rsp),%rdx
   0x0000000000401096 <+52>:    and    $0xf,%edx
   0x0000000000401099 <+55>:    movzbl 0x4024b0(%rdx),%edx
   0x00000000004010a0 <+62>:    mov    %dl,0x10(%rsp,%rax,1)
   0x00000000004010a4 <+66>:    add    $0x1,%rax
   0x00000000004010a8 <+70>:    cmp    $0x6,%rax
   0x00000000004010ac <+74>:    jne    0x40108b <phase_5+41>
   0x00000000004010ae <+76>:    movb   $0x0,0x16(%rsp)
   0x00000000004010b3 <+81>:    mov    $0x40245e,%esi        //字符串 flyers
   0x00000000004010b8 <+86>:    lea    0x10(%rsp),%rdi
   0x00000000004010bd <+91>:    callq  0x401338 <strings_not_equal>
   0x00000000004010c2 <+96>:    test   %eax,%eax
   0x00000000004010c4 <+98>:    je     0x4010d9 <phase_5+119>
   0x00000000004010c6 <+100>:    callq  0x40143a <explode_bomb>
   0x00000000004010cb <+105>:    nopl   0x0(%rax,%rax,1)
   0x00000000004010d0 <+110>:    jmp    0x4010d9 <phase_5+119>
   0x00000000004010d2 <+112>:    mov    $0x0,%eax
   0x00000000004010d7 <+117>:    jmp    0x40108b <phase_5+41>
   0x00000000004010d9 <+119>:    mov    0x18(%rsp),%rax
   0x00000000004010de <+124>:    xor    %fs:0x28,%rax
   0x00000000004010e7 <+133>:    je     0x4010ee <phase_5+140>
   0x00000000004010e9 <+135>:    callq  0x400b30 <__stack_chk_fail@plt>
   0x00000000004010ee <+140>:    add    $0x20,%rsp
   0x00000000004010f2 <+144>:    pop    %rbx
   0x00000000004010f3 <+145>:    retq   
End of assembler dump.

根据x86-64寄存器使用规范，%rdi寄存器存储的是第一个参数的值，由于输入的是字符串，因此%rdi存储的应该是输入字符串的起始地址。0x401067处的指令mov %rdi,%rbx将字符串起始地址保存在%rbx中，即%rbx为基址寄存器。指令xor %eax,%eax的作用是将%eax清零，接着调用string_length函数获取输入字符串的长度，并将长度值（返回值）存储于%eax。指令cmp $0x6,%eax将string_length的返回值与常数6作比较，若不相等则会引爆炸弹，由此可以得知，phase_5的输入字符串长度应该等于6。

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

待比较的字符串为flyers，且长度也为6。所以，接下来的关键任务是需要对循环操作进行分析，理解该循环操作对输入字符串做了哪些操作。提取循环操作的代码，如下所示。

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

由于%rbx存储的是输入字符串的起始地址，%rax初始化为0，其作用等价于下标，因此movzbl (%rbx,%rax,1),%ecx指令的作用是将字符串的第%rax个字符存储于%ecx，movzbl意味做了零扩展。接着，mov %cl,(%rsp)指令取%ecx的低8位，即一个字符的大小，通过内存间接存储至%rdx中。and $0xf,%edx指令将%edx的值与常数0xf进行位与，由指令movzbl 0x4024b0(%rdx),%edx可知，位与后的值将会作为偏移量，以0x4024b0为基址，将偏移后的值存储至%edx。最后，指令mov %dl,0x10(%rsp,%rax,1)以%edx低8位的值作为新的字符，对原有字符进行替换。综上，phase_5遍历输入字符串的每个字符，将字符的低4位作为偏移量，以0x4024b0为起始地址，将新地址对应的字符替换原有字符，最终得到flyers字符串。打印0x4024b0处的内容，如下图所示。

mark

例如，如果要得到字符f，那么偏移量应为9，二进制表示为1001，通过查找ASCII表，可知字符i的ASCII编码为01101001，满足要求。（或者字符y（01111001）所以解不唯一）剩余5个字符采用同样的策略可以依次求得，最终，phase_5的输入字符串的一个解为ionefg。

Phase 6

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
Dump of assembler code for function phase_6:
=> 0x00000000004010f4 <+0>:    push   %r14
   0x00000000004010f6 <+2>:    push   %r13
   0x00000000004010f8 <+4>:    push   %r12
   0x00000000004010fa <+6>:    push   %rbp
   0x00000000004010fb <+7>:    push   %rbx
   0x00000000004010fc <+8>:    sub    $0x50,%rsp
   0x0000000000401100 <+12>:    mov    %rsp,%r13
   0x0000000000401103 <+15>:    mov    %rsp,%rsi
   0x0000000000401106 <+18>:    callq  0x40145c <read_six_numbers>
   0x000000000040110b <+23>:    mov    %rsp,%r14           # %r14存储数组起始地址
   0x000000000040110e <+26>:    mov    $0x0,%r12d          # 将%r12d初始化为0
#################### Section 1:确认数组中所有的元素小于等于6且不存在重复值 ###################
   0x0000000000401114 <+32>:    mov    %r13,%rbp           # %r13和%rbp存储数组某个元素的地址，并不是第1个元素，意识到这点需要结合0x40114d处的指令
   0x0000000000401117 <+35>:    mov    0x0(%r13),%eax
   0x000000000040111b <+39>:    sub    $0x1,%eax        # 将%eax的值减1
   0x000000000040111e <+42>:    cmp    $0x5,%eax        # 将%eax的值与常数5做比较
   0x0000000000401121 <+45>:    jbe    0x401128 <phase_6+52>
   0x0000000000401123 <+47>:    callq  0x40143a <explode_bomb>
   0x0000000000401128 <+52>:    add    $0x1,%r12d        # 如果%eax的值小于等于5，%r12d加1
   0x000000000040112c <+56>:    cmp    $0x6,%r12d        # 将%r12d与常数6做比较
   0x0000000000401130 <+60>:    je     0x401153 <phase_6+95>
   0x0000000000401132 <+62>:    mov    %r12d,%ebx        # %ebx起了数组下标的作用

# 用于判断数组6个数是否存在重复值，若存在，引爆炸弹
   0x0000000000401135 <+65>:    movslq %ebx,%rax        # 将数组下标存储至%rax
   0x0000000000401138 <+68>:    mov    (%rsp,%rax,4),%eax        # 将下一个数存储至%eax
   0x000000000040113b <+71>:    cmp    %eax,0x0(%rbp)            # 将第1个数与%eax的值(当前数)做比较
   0x000000000040113e <+74>:    jne    0x401145 <phase_6+81>    # 若相等，引爆炸弹
   0x0000000000401140 <+76>:    callq  0x40143a <explode_bomb>
   0x0000000000401145 <+81>:    add    $0x1,%ebx                # 数组下标加1
   0x0000000000401148 <+84>:    cmp    $0x5,%ebx                 # 判断数组下标是否越界(<=5)
   0x000000000040114b <+87>:    jle    0x401135 <phase_6+65>
   0x000000000040114d <+89>:    add    $0x4,%r13                # %r13存储数组下一个数的地址
   0x0000000000401151 <+93>:    jmp    0x401114 <phase_6+32>
####################################### Section 1 end ######################################

################ Section 2：用7减去数组的每个元素，并将相减后的元素替换原有元素 #################
---Type <return> to continue, or q <return> to quit---
   0x0000000000401153 <+95>:    lea    0x18(%rsp),%rsi        # 0x18(%rsp)是数组的边界地址：0x18 = 24
   0x0000000000401158 <+100>:    mov    %r14,%rax            # 将数组起始地址存储于%rax
   0x000000000040115b <+103>:    mov    $0x7,%ecx
   0x0000000000401160 <+108>:    mov    %ecx,%edx            # %edx = 7
   0x0000000000401162 <+110>:    sub    (%rax),%edx            # %edx = 7 - 数组元素
   0x0000000000401164 <+112>:    mov    %edx,(%rax)            # 用相减后的元素(%edx)替换原有元素
   0x0000000000401166 <+114>:    add    $0x4,%rax                # %rax存储数组下一个元素的地址
   0x000000000040116a <+118>:    cmp    %rsi,%rax                # 判断是否越界
   0x000000000040116d <+121>:    jne    0x401160 <phase_6+108>
####################################### Section 2 end ######################################

########################## Section 3：根据输入数组重排结构体数组 ##############################
   0x000000000040116f <+123>:    mov    $0x0,%esi        # 将%esi初始化为0，作为数组下标
   0x0000000000401174 <+128>:    jmp    0x401197 <phase_6+163>
   0x0000000000401176 <+130>:    mov    0x8(%rdx),%rdx        # 0x8(%rdx)为下一个元素的地址
   0x000000000040117a <+134>:    add    $0x1,%eax
   0x000000000040117d <+137>:    cmp    %ecx,%eax            # %ecx存储了数组当前值(第%esi个元素)
   0x000000000040117f <+139>:    jne    0x401176 <phase_6+130>
   0x0000000000401181 <+141>:    jmp    0x401188 <phase_6+148>
   0x0000000000401183 <+143>:    mov    $0x6032d0,%edx        # %edx存储结构体数组第1个元素的地址
   0x0000000000401188 <+148>:    mov    %rdx,0x20(%rsp,%rsi,2)    # %rsi的初始值为0；该指令的作用是将结构体数组的第%ecx个元素的地址存储在内存的某个位置(以%rsp + 0x20为基地址，%rsi为偏移量)
   0x000000000040118d <+153>:    add    $0x4,%rsi        # 增加偏移量
   0x0000000000401191 <+157>:    cmp    $0x18,%rsi
   0x0000000000401195 <+161>:    je     0x4011ab <phase_6+183>
   0x0000000000401197 <+163>:    mov    (%rsp,%rsi,1),%ecx    # %ecx存储数组第%esi个元素
   0x000000000040119a <+166>:    cmp    $0x1,%ecx        # 将数组第%esi个元素与常数1做比较
   0x000000000040119d <+169>:    jle    0x401183 <phase_6+143>    # 实际上不会小于1，如果数组的第1个元素等于1，那么跳转至0x401183处
   0x000000000040119f <+171>:    mov    $0x1,%eax
   0x00000000004011a4 <+176>:    mov    $0x6032d0,%edx        # %edx存储结构体数组第1个元素的地址
   0x00000000004011a9 <+181>:    jmp    0x401176 <phase_6+130>
####################################### Section 3 end ######################################

######################### Section 4：修改结构体数组元素的next域值 #############################
   0x00000000004011ab <+183>:    mov    0x20(%rsp),%rbx    # %rbx存储地址数组的第1个元素的值
   0x00000000004011b0 <+188>:    lea    0x28(%rsp),%rax    # %rax存储地址数组的第2个元素的地址
   0x00000000004011b5 <+193>:    lea    0x50(%rsp),%rsi
   0x00000000004011ba <+198>:    mov    %rbx,%rcx        # %rcx存储地址数组的第1个元素的值
# 下面用i和i+1来表示元素位置
   0x00000000004011bd <+201>:    mov    (%rax),%rdx    # %rdx存储地址数组的第i+1个元素的值
   0x00000000004011c0 <+204>:    mov    %rdx,0x8(%rcx)    # 把第i+1和元素的值存储于第i个结构体元素的next域中，next域的地址为0x8(%rcx)的值
   0x00000000004011c4 <+208>:    add    $0x8,%rax
   0x00000000004011c8 <+212>:    cmp    %rsi,%rax
   0x00000000004011cb <+215>:    je     0x4011d2 <phase_6+222>
   0x00000000004011cd <+217>:    mov    %rdx,%rcx
   0x00000000004011d0 <+220>:    jmp    0x4011bd <phase_6+201>
####################################### Section 4 end ######################################

######################### Section 5：判断结构体数组是否是递减序列 #############################
   0x00000000004011d2 <+222>:    movq   $0x0,0x8(%rdx)
   0x00000000004011da <+230>:    mov    $0x5,%ebp
   0x00000000004011df <+235>:    mov    0x8(%rbx),%rax
   0x00000000004011e3 <+239>:    mov    (%rax),%eax
   0x00000000004011e5 <+241>:    cmp    %eax,(%rbx)
   0x00000000004011e7 <+243>:    jge    0x4011ee <phase_6+250>
   0x00000000004011e9 <+245>:    callq  0x40143a <explode_bomb>
   0x00000000004011ee <+250>:    mov    0x8(%rbx),%rbx
   0x00000000004011f2 <+254>:    sub    $0x1,%ebp
   0x00000000004011f5 <+257>:    jne    0x4011df <phase_6+235>
####################################### Section 5 end ######################################

   0x00000000004011f7 <+259>:    add    $0x50,%rsp
   0x00000000004011fb <+263>:    pop    %rbx
   0x00000000004011fc <+264>:    pop    %rbp
   0x00000000004011fd <+265>:    pop    %r12
   0x00000000004011ff <+267>:    pop    %r13
   0x0000000000401201 <+269>:    pop    %r14
   0x0000000000401203 <+271>:    retq   
End of assembler dump.

分析清楚phase_6非常需要耐心，我将phase_6划分为5个Section，每个Section完成特定的功能，详细的注释直接附到了相关代码。前两个Section不难理解：Section 1确保输入数组的值的范围在1 ~ 6且不存在重复值；Section 2用7减去输入数组的每个元素，相当于求补。Section 3中出现了一个常数地址，使用gdb将该地址存储的内容打印出来，如下图所示。

可以意识到这其实是一个链表数据结构，链表的节点由3部分组成：value 1、value 2和一个地址值(next域，指向下一个节点)。Section 3根据我们输入的数组，按照数组元素的值将对应结构体数组中的元素的首地址存储到内存的某个位置(mov %rdx,0x20(%rsp,%rsi,2))。例如，假设输入数组为[3, 4, 5, 6, 1, 2]，那么Section 3首先会将结构体数组的第3个元素的地址存储到0x20(%rsp,%rsi,2)处，接着将结构体数组的第4个元素……依次类推。Section 4根据Section 3构建的地址数组，修改结构体数组的next域的值，实现单链表的排序操作。Section 5进行验证，要求单链表递减排序，若满足要求，那么拆弹成功。

综上，根据已有的结构体数组以及phase_6的操作，若要实现单链表的递减排序，应将第3个节点放在第1位，将第4个节点放在第2位……最终得到序列：[3, 4, 5, 6, 1, 2]。不要忘记Section 2中的求补操作，所以phase_6的输入序列应该为[4, 3, 2, 1, 6, 5]。

mark

reference

1.http://wdxtub.com/2016/04/16/thick-csapp-lab-2/