CSAPP笔记&实验
本章属于第一部分:程序的结构和执行. 包括:

• 基础 Basics

• 控制 Control

• 过程 Procedures

• 数据 Data

Procedures

3.7 过程 Procedures

过程

过程是软件中一种很重要的抽象. 它提供了一种封装代码的方式, 用一组指定的参数和一个可选的返回值
实现某种功能, 在程序的其他位置可以调用这个过程. 不同编程语言中, 过程的形式多样:函数(function)、
方法(method)、子例程(subroutine)、处理函数(handler)等, 它们具有一些共有特性.

机制

假设过程P调用过程Q, Q执行后返回P. 这些动作包括下面一个或多个机制:

• 传递控制 Passing control : 进入过程Q时, 程序计数器(PC/rip)必须被设置为Q过程的起始地址;
  Q返回时, 要把程序计数器设置为P调用Q语句的下一条语句的地址

• 传递数据 Passing data : P必须能够向Q提供参数, Q必须能向P返回一个值.

• 分配和释放内存 Memory management : 进入Q时, 可能需要为局部变量分配空间; 在返回前
  又要释放这些空间.

x86-64的过程实现包括一组特殊指令和一些对机器资源(例如存储器和程序内存)使用的约定规则.

3.7.1 运行时栈

栈管理 stack discipline

C语言过程调用机制的一个关键特性(大多数语言也是如此)在于使用了栈数据结构提供的后进先出的
内存管理原则. 在过程P调用过程Q的例子中, 当Q在执行时, P以及所有向上追溯到P的调用链的过程,
都时暂时被挂起的.

内存管理

当Q运行时, 只需要为局部变量分配新的存储空间, 或者设置到另一个过程的调用.另一方面, 当Q返回时,
任何它所分配的局部存储空间都可以被释放. 因此程序可以用栈来管理它的过程所需要的存储空间, 栈和
程序寄存器存放着传递控制和数据、分配内存所需要的信息.

通过3.4.4节我们知道, x86-64的栈向低地址增长, 栈顶指针rsp指向栈顶元素. 将栈指针减小一个适当
的量可以为没有指定初始值的数据在栈上分配空间(我们会在汇编代码中经常看到). 类似的, 可以通过
增加栈指针来释放空间.

栈帧 stack fram

当x86-64过程需要的存储空间超过寄存器能够存放的大小时, 会在栈上分配空间, 这部分称为过程的栈帧.

上图给出了运行时栈的通用结构, 可以看到正在执行的过程(Q)总是在栈顶, 其上按调用顺序包括过程P和
之前的过程. 当过程P调用过程Q时, 会把返回地址压入栈中, 指明了当Q返回时, 要从P程序的哪个位置
继续执行. 我们把这个返回地址作为过程P的栈帧的一部分, 因为它存放的是和P相关的状态.

Q的代码会扩展当前栈的边界, 分配它的栈帧所需的空间. 在这个空间中, 它可以保存寄存器的值, 分配
局部变量空间, 为它调用的过程设置参数. 大多数过程的栈帧都是定长的, 在过程开始时就分配好了.
但有些过程需要边长的帧, 这个问题会在3.10.5讨论.

为了提高空间和时间效率, x86-64过程只分配自己所需要的栈帧部分. 如果过程需要6个或更少的参数, 那么
所有参数可以通过寄存器传递; 此外如果过程不需要保存返回地址(不调用其他过程, 有时称为叶子过程),
这样的过程就不需要栈帧.

3.7.2 转移控制

call & ret by using stack

在过程P调用过程Q的例子中, 将控制从函数P转移到函数Q只需要简单地把程序计数器PC设为过程Q的起始位置.
而当Q返回时, 处理器必须记录好它需要继续执行P的代码位置. 在x86-64中, 上述
过程由call和ret指令实现.
call label :

• 将返回地址push到栈中

• 跳转到label对应地址

ret :

• 将对应call存储的返回地址pop到rip寄存器中

示例

这里以函数mulstore调用函数mul2为例说明call和ret的执行情况.

mulstore执行到call语句时rip存储对应call语句地址.

call指令: 将call指令的下一条指令的地址push进栈中, 并将mul2起始地址放入指令指针rip中.

![

mul2执行到ret指令.

ret指令: pop %rip, 将返回地址从栈弹入rip中.

应用将返回地址压入栈的简单机制就能让函数在正确位置返回, 对于复杂函数的调用也是运用相同的规则,
因为C语言的标准调用/返回机制刚好和栈提供的FILO的内存管理方法吻合.

3.7.3 数据传送

参数传递

x86-64中大部分数据传送是通过寄存器实现的, 例如前两个参数会在寄存器rdi和rsi中. 当过程P调用过程
Q时, P的代码必须首先把参数复制到适当的寄存器中, 而当Q返回时过程P可以通过访问rax获取Q的返回值.

x86-64中可以通过寄存器最多传递6个整型(整数/指针)参数, 且之前以及介绍寄存器的命名和参数顺序. 如果
一个函数有大于6个整型参数, 超出6的部分就要通过栈来传递.

如上图, 若Q需要n($n>6$)个参数, 参数7~n需要保存在栈中(Q的栈帧), 而参数7地址相对最小. 通过栈传递的参数, 所有的数据大小都要向8的倍数对齐. 过程Q可以通过寄存器和栈访问参数. 如果Q也需要调用超过6个参数的函数, 同样的Q要在Q栈帧的参数构造区(argument build area)为超出6的参数分配空间.

示例

以需要8个参数的proc函数为例.

(up主大佬图片有点错误, 少了指针引用符号*)

栈中数据大小都是8的倍数, 所以char类型的a4也占了8个字节; 栈顶rsp指向返回地址, a4和ap4分别
在rsp + 8和rsp + 16的位置.

3.7.4 栈上的局部存储 local storage in stack

在有些情况下, 局部变量必须存放在内存中

• 寄存器不足够存放所有本地数据(如上面超过6个参数的函数)

• 对某一局部变量使用地址运算符&, 必须能够为它产生一个内存地址

• 某些局部变量是数据或结构, 必须能够通过数组或结构引用被访问到.

一般来说, 过程通过减少栈顶指针在栈上分配空间, 分配结构作为栈帧的局部变量部分.

包含&的示例

函数swap_add交换指针指向的值并返回和; caller创建局部变量arg1和arg2的指针, 传递给swap_add.

观察caller的汇编代码理解如何实现对使用&的局部变量的存储.

sub指令通过减小栈指针为局部变量分配空间. 分别叫arg1和arg2分配在rsp和rsp+8的位置上, 并
将对应地址传入swap_add并调用. 最后返回时add指令释放栈帧. 通过sub和add栈指针rsp, 运行时栈
提供了一种简单的, 在需要时分配、函数完成时释放局部存储的机制.

一个更复杂的例子

call_proc调用上面提到的有8个参数的proc函数.

对于x1 ~ x4, 因为对它们有取地址&操作, 从图可以看出分别对局部变量按其字节大小从高地址到低地址
分配内存. 因为proc需要8个参数, 所以超过6的第7个和第8个参数要按低地址到高地址顺序分配内存.
注意对局部变量存储时大小没有要求, 而传递的参数大小需要是8的倍数.

当call_proc调用proc后, 因为需要压入返回地址, 所以第7个参数和第8个参数分别在rsp + 8
和 rsp + 16的位置.

寄存器的局部存储空间 local storage in register

caller/callee-save

寄存器组是唯一被所有进程都共享的资源.

为确保过程P调用过程Q后, 过程Q不会覆盖P稍后会使用的寄存器值, x86-64采用了一组
统一的寄存器使用管理, 即我们之前提到的caller-save & callee-save.

过程Q保持一个寄存器不变

• 压根就不改变它

• push寄存器原始值在栈中暂存在保存的寄存器部分(saved registers), 在返回前弹出旧值回寄存器

示例

以函数P调用两次函数Q为例.

• callee-save : 最开始的两个push和最后的两个pop.

• caller-save : 第一次调用Q前因为Q会用到rdi, 所以在调用前把rdi放入rbp暂存.

3.7.6 递归过程 recursive procedures

前面描述的寄存器和栈的使用规则使得x86-64过程能够递归地调用它们自身. 每个被调用还未返回的过程
在栈中都有它们自己的私有空间, 因此多个未完成调用的局部变量不会相互影响. 此外栈为每个过程提供
了适当的内存申请和释放的策略.

示例

以计算参数n在二进制表示中1的个数的递归实现函数pcount_r为例.

pcount_r汇编代码首先把参数n暂存在rbx中(caller-save); 设置好参数后调用pcount_r; 计算最终结果.

可以发现对pcount_r自身的调用相比于调用其他函数而言没有任何特殊指令. 也就是递归调用于普通的
函数调用相同.

Data

3.8 数组分配和访问

C语言中的数组是一种将标量数据(基本数据)聚合成更大数据类型的方式. C语言的一个不同寻常的特点是
可以产生指向数组中元素的指针, 并对这些指针进行运算.

3.8.1 基本原则 basic principle

数组声明

T $A$[N];
起始地址表示为$x_A$. 这个声明有两个效果

• allocate memory 在内存中分类一个$L * N$字节的连续区域, L是数据类型T的字节大小.

• 引入标识符A, 可用来作为指向数组开头的指针, 值为$x_A$

对于第i个元素, 其地址为$x_A + i * L$

3.8.2 指针运算 pointer arithmetic

带数据类型伸缩的加法

C语言允许对指针进行运算, 而计算出来的值会根据该指针引用的数据类型大小进行伸缩. 如果
p是指向类型为T的数据指针, p值为$x_p$, 那么表达式$p + i$的值为$x_p + L * i$.

&与*

单操作数操作符&产生指针, *间接引用指针. 某对象表达式Expr, &Expr给出该对象地址;
某地址表达式AExpr, *AExpr给出该地址的值. 也就是A[i]等价于*(A + i), 计算第i个元素
地址, 然后访问这个内存位置.

示例

假设整型数组E起始地址在rdx中, 索引i在rcx中. 结果存放在eax(数据)或rax(指针)中.

从汇编代码可以看到E[i]地址的伸缩计算非常契合mov/leaq指令运算的伸缩和加法特性. 最后一个例子
表明可以计算两个指针之差(无法计算之和), 结果的数据类型为long, 值等于地址之差除以数据类型大小.

3.8.3 嵌套的数组 nested arrays

嵌套数组也被称为二维数组.

两种理解方式

int A[5][3]; 

有两种理解方式 :

• 二维数组, 类似与矩阵排列

• 数组的数组, 例子可以认为是包含5个元素的数组, 每个元素需要12个字节存储3个整数.

所以例子等价于

typedef int row3_t[3];
row3_t A[5];

存储方式

因为我们将内存视为很大的一维数组, 所以在内存存储时需要将二维数组->一维, 这里采用行优先的方式.
也就是首先存储第0行的所有元素, 接着存储第1行所有元素.

内存访问

对数组 T $D$[R][C];
它的数组元素D[i][j]的内存地址为 &$D[i][j] = x_D + L(C * i + j )$. L时数据类型T的字节大小.

对上$5 * 3$的数组A的元素A[i][j]地址计算如图.

3.8.4 定长数组 fixed-sized arrays

C语言编译器能够优化定长多维数组上的操作代码. 这里展示优化等级为-O1是GCC采用的优化.

示例

首先声明定长整型数组.

#define N 16
typedef int fix_matrix[N][N] 

求两个定长数组第i行和第k列内积的函数.

首先编译器会对代码做出优化 : 将数组引用->指针间接引用. 下面是优化过的C代码.

int fix_prod_ele_opt(fix_matrix A, fix_matrix B, long i, long k)
{
    int *Aptr = &A[i][0]; //Aptr指向A的第i行连续元素
    int *Bptr = &B[0][k]; //Bptr指向B的第j列连续元素
    int *Bend = &B[0][N]; //Bend作为终止哨兵
    int result = 0;
    do //不需要初始判断 可能因为是定长数组, 长度大于0所以肯定有多次操作
    {
        result += *Aptr * *Bptr; //A[i][k] * B[k][j]     
        Aptr ++;                 //将Aptr移动至下一列
        Bptr += N;               //将Bptr移动至下一行
    }while( Bptr != Bend );      //终止条件测试
    return result;
}

生成三个指针的汇编代码.

A in %rdi, B in %rsi, i in %rdx, k in %rcx;
A[i] = A + i * 4 * N = A + 64i --> 前两行汇编指令 Aptr in %rdi
B[0][k] = B + 4 * k --> 第三行汇编代码 Bptr in %rcx
B[N][k] = B + N * 4 * N + 4 * k = B[0][k] + N * 4 * N = Bptr + 1024 --> 第四行代码 Bend in % rsi

计算result(%eax).

(这里up主大佬有一处错误, 最后判断是否退出循环应是 cmpq %rsi, %rcx).

可以看到因为是定长数组, 所以汇编代码中出现很多常数值参与运算.

3.8.5 变长数组 variable-size arrays

历史上, C曾经只支持大小在编译时就确定的多维定长数组, 对变长数组程序员需要用malloc或calloc
为数组分配内存空间. ISO C99引入一种功能, 允许数组的维度是表达式, 在数组分配时才计算出来.

在C中可以对变长数组声明 :
int A[$expr1$][$expr2$];
在遇到声明时, 通过$expr1$和$expr2$求值来确定数组维度.

示例1

例如访问n * n数组的元素A[i][j].

参数n必须在参数A[n][n]之前, 这样函数才能在遇到A[n][n]时计算出数组维度. 元素A[i][j]的地址为
$x_A + 4(n * i) + 4j = x_A + 4 * (n * i + j)$. 与定长数组元素地址计算类似; 此外使用了乘法
指令计算$n * i$, 而不是移位和leaq的伸缩加法. 乘法指令耗时更高, 但不可避免.

示例2

以计算变长数组的第i行和第k列内积为例.

原始版本, 与定长数组没有区别(N -> n).

编译器优化版本, 代码用循环变量j用来索引元素和判断是否结束循环.

汇编代码.

这里用存储在寄存器的4n增加Bptr的值. 可以看出除了不用常量和移位运算而只能用存储在寄存器的值
和mul命令计算地址外, 变长数组和定长数组没有其他区别.

3.9 异质数据结构

C语言提供两种将不同类型对象组合到一起创建数据类型的机制 :

• 结构(structure), 使用关键字struct, 将多个对象集合到一个单位中

• 联合(union), 使用关键字union, 允许用几种不同类型来引用一个对象

3.9.1 结构 structure

C用struct声明创建一个数据类型, 将可能不同类型的对象聚合到一个对象中. 用名字引用结构体的各个部分.
结构体在内存中连续存储, 指向结构体的指针为其首地址. 编译器会保存各个字段(field)的字节偏移, 用
基地址 + 偏移量引用各个结构元素.

示例

结构体每个元素按顺序在内存中连续存放.

为访问结构体字段, 编译器产生代码要将结构体的地址加上适当的偏移. 例如访问结构体中的数组的第i个元素地址.

这里偏移量offset = 0, 所以访问方式与访问数组一致.

对结构体单链表进行操作.

可以看到对不同字段的访问遵循基地址r + 偏移量offset的方式.

3.9.2 联合 union

联合提供了能够规避C语言类型的一种方式, 允许多种类型引用同一内存块.

内存分布

相比于结构体, 联合的所有地段引用的都是内存的起始地址, 并且内存的大小取决于最大字段
的大小. 例子中最大字段大小为8B, 所以联合大小为8B.

应用

一种应用情况是我们知道对数据结构不同字段的使用是互斥的.

例如一个二叉树数据结构, 其内部结点存储左右孩子结点的指针, 叶子结点存储两个double类型的数据.
每个节点都需要32字节, 且每次只使用一半的字节. 所以可以用联合声明二叉树结构.

不过上述编码有一个问题 : 无法确定一个节点是内部节点还是叶子节点. 通常的方法是引入一个枚举
类型, 再创建一个结构体, 包含枚举标签和这个联合.

这个结构需要24个字节 : type占4字节, 联合体占16字节, 中间需要加入4字节间隙(数据对齐).
在本例中相比于给代码造成的麻烦, 使用联合带来的节省是很小的. 对于有较多字段的数据机构
联合的使用才更划算.

另一个应用是联合可以访问不同数据类型的位模式.
例如我们使用简单的强制类型转换 :

    double d = xxx.y;
    unsigned long u = (unsigned long) d;

除d = 0.0的情况外, u和d的位模式会很不一样。 而用联合进行相同的类型转换 :

我们用一种类型来存储, 用另一种类型访问. 因为联合使用同一内存块, 所以u和d位模式相同.

3.9.3 数据对齐 alignment

基本原则

很多计算机系统对基本数据类型的合法地址做出一些限制, 这种对齐限制简化了处理器和内存系统之间的
接口的硬件设计. 例如假设一个处理器每次从内存取8个字节, 数据地址如果是8的倍数则用一个内存操作
来读/写; 否则需要执行两次内存访问.

无论数据是否对齐, x86-64硬件都能正确工作. 不过建议还是要数据对齐提高内存系统性能.
对齐原则 : 任何K字节的基本对象的地址必须是K的倍数.

结构体对齐

1. 结构体内部 : 每个地段都需满足对齐原则, 可能需要在字段的分配中加入间隙(不被使用的字节).

2. 整个结构体 :

   • 每个结构体需要按K字节对齐(K是结构体中最大字段的字节大小)

   • 初始地址&结构体长度是K的倍数

初始地址保证最大字段地址是K的倍数; 长度保证如果存在结构体数组对最大字段仍满足对齐要求.

结构体长度是K的倍数 :

结构体长度为K为满足结构体数组的对齐要求 :

为节省内存空间, 声明结构体时最好先声明字节大的字段, 再声明字节小的字段.

3.10 在机器级程序中将控制与数据结合起来 advanced topics

到目前为止, 我们已经分别讨论机器级代码如何实现程序的控制部分和不同的数据结构. 本节中我们
会看看数据和控制如何交互. 首先深入审视指针->复习符号调式器GDB的使用->机器级代码研究缓冲
区溢出->机器级程序如何实现函数要求的栈空间大小在每次执行都可能不同的情况.

3.10.3 内存越界引用和缓冲区溢出

C对数组引用不做任何边界检查, 而函数的局部变量和状态信息(例如保存寄存器的值和返回地址)都存放在
栈中. 这两种情况结合在一起就能导致严重的程序错误 : 对越界数组元素的写操作会破坏存储在栈中的
状态信息. 当程序使用这个被破坏的状态, 试图重新加载寄存器或执行ret指令时, 会出现严重错误.

缓冲区溢出 buffer overflow

示例1

在第一章时我们提到过一个越界内存引用的例子.

fun函数对$x_A + 4 * i$的地址位置($x_A$为结构体首地址)进行写操作, 但可能会超出数组边界.

如果越界引用的地址位置保存程序的关键信息, 则可能引起段错误(segmentation fault).

示例2

通常在栈中分配某个字符数组来保存一个字符串, 如果函数不检测输入字符数目, 字符串长度可能
会超出为字符数组分配的空间.

上代码给出库函数gets的一个实现, 它从标准输入读入一行, 将读入字符复制到s指出的位置, 但
gets并没有确定是否为保存整个字符串分配足够空间.

这里故意将传冲区设置的很小, 超过3个字符的字符串都会导致写越界. 观察对应的汇编代码 :

echo函数在栈上分配了24字节的空间. 并把%rsp作为gets的地址参数. 观察echo执行时栈的组织 :

如果输入字符不超过23个, 虽然超出字符数组的大小, 但并没有破坏关键的echo返回地址, 因为中间
有一部分未被使用的栈空间.

如果输入字符串过长就会破坏echo的返回地址, 导致段错误.

这里输入刚好是24个字符时, echo返回地址的最低位变成0(null), 可能会跳转至一个可以运行的位置.

如果跳转的位置没有破坏栈空间, 最终可能会ret回main函数.

攻击代码 exploit code

传冲区溢出的一个更加致命的使用就是让程序执行它本来不想执行的代码. 我们可以输入包含可执行代码
的字节编码(exploit code), 并用一个执行exploit code的指针覆盖返回地址.

例子中Q在调用gets后输入exploit code, 并将P的返回地址用执行exploit code的指针覆盖. 当Q执行
到ret时就会跳转到我们希望执行的exploit code.

3.10.4 对抗传冲区溢出攻击 thwarting buffer overflow attacks

缓冲区溢出攻击的普遍发生给计算机系统造成了许多麻烦. 现代编译器和操作系统实现了很多机制, 以限制
入侵者通过缓冲区溢出攻击获得系统的控制.

1. 栈随机化 randomized stack offsets

为插入攻击代码, 攻击者既要插入代码又要插入指向这段代码的指针. 而产生这个指针需要知道这个
字符串在栈中的位置.
对于运行相同程序和操作版本的系统来说, 在不同机器间栈的位置是固定的. 因此攻击者可以很容易
确定栈地址并设计一个在许多机器上都能实施的攻击, 许多系统受同一病毒的攻击被称为安全单一化.

栈随机化的思想是栈的位置在程序每次运行时都有变化. 实现方式是在程序开始时, 栈分配一段0 ~ n字间
间的随机大小空间, 这样每次程序的起始地址每次运行时都不一样, 增加了成功攻击一个系统的难度.

2.栈破坏检测 stack corruption detection

计算机的第二道防线是能够检测何时栈已经被破坏. 在C中没有可靠方法防止对数组的越界引用, 但我们
能够在发生越界造成有害结果前, 尝试检测到它.

例如栈保护者(stack protector)机制, 在栈帧中任何局部缓冲区和栈状态之间存储一个特殊的
金丝雀值(canary, 历史上用这种鸟检测煤矿中是否含有毒气体)/哨兵值(guard value), 在程序运行时
随机产生. 在恢复寄存器状态和从函数返回前, 判断金丝雀值是否被改变.

指令参数%fs:40指明金丝雀值用段寻址(一种寻址方式)从内存读入, 并存储在局部变量buf的上方. 将
金丝雀的值存放在只读的段中, 这样攻击者就不能覆盖存储的金丝雀值. 函数在返回前用存放在栈位置
处的值和金丝雀值比较(xor指令), 若相等则正常退出, 否则代码调用一个错误处理例程.

限制可执行代码区域

最后一招是消除攻击者向系统插入可执行代码的能力. 一种方法是限制哪些内存区域能够存放可执行
代码. 在典型的程序中, 只有保存编译器产生的代码的那部分内存才是需要时可执行的.

图中我们将栈作为不可执行部分, 那么将可执行代码保存在栈中也没有作用.

栈随机化、栈保护和限制哪部分内存可以存储可执行代码是用于最小化程序缓冲区攻击漏洞的三种
常见机制. 它们都对程序员透明(程序员不需要做特殊努力), 并且带来的性能代价都很小. 另一个
防止程序被攻击的方式是写安全的代码(使用安全的库函数, 对数组越界做判断等).

面向返回编程攻击 return-oriented programming attacks