CSAPP Ch3：程序的机器级表示

1 导言

学习汇编代码，我们能够理解编译器的优化能力，并分析代码中隐含的低效率。高级语言提供的抽象层会隐藏我们想要了解的程序的行为。另外一个例子，程序遭受攻击的许多方式中，都涉及程序存储运行时控制信息的方式的细节。

2 程序编码

gcc的转化过程：

1. C预处理器扩展源代码，插入所有#include命令指定的文件，并扩展所有用#define声明指定的宏；
2. 其次，编译器产生每个源文件的汇编代码；
3. 接下来，汇编器将汇编代码转化为二进制目标代码文件；目标代码是机器代码的一种形式，包含所有指令的二进制表示，但是还没有填入全局值的地址；
4. 最后，链接器将两个目标代码文件与实现库函数的代码合并，并产生最终的可执行代码文件

有两种重要的抽象：

1. 由指令集体系结构或指令集架构来定义机器及程序的格式和行为，它定义了处理器状态、指令的格式，以及每条指令对状态的影响；
2. 机器级程序使用的内存地址是虚拟地址，提供的内存模型看上去是一个非常的大的字节数组。存储器系统的实际实现时将多个硬件存储器和操作系统软件组合起来。

对C程序员隐藏的处理器状态细节包括：

• 程序计数器（PC，用%rip%表示）给出将要执行的下一条指令地址；
• 整数寄存器包含16个命名的而为之，分别存储64位的值；
• 条件码寄存器保存着最近执行的算数或逻辑指令的状态信息，用来实现控制或数据流中的条件变化；
• 一组向量寄存器可以存放一个或多个整数或浮点数值；

程序内存包含：程序的可执行机器源码，操作系统需要的一些信息，用来管理过程调用和返回的运行时栈，以及用户分配的内存块（比如调用malloc分配的）；

编译相关命令：

-s 编译成.s汇编文件
-c 编译+汇编成.o目标文件
-o 编译+汇编+链接，直接生成可执行文件

其中gdb的使用命令如下：

(gdb)x/14xb multstore # 其中x为打印，x表示16进制，b表示字节，multstore是函数地址

要查看机器代码文件，使用反汇编器：

objdump -d mstore.o

其中机器指令的一些特性包括：

• 指令长度1到15不等，常用的指令以及操作数较少的指令所需的字节数少，不太常用或者操作数较多的指令所需字节数较多；
• 设计指令格式的方式是，从某个特定位置开始，可以将字节唯一的解码成机器指令；
• 指令中后缀的q是一种传送数据大小的表示；
• 部分nop指令的插入是为了使哈桑农户代码变为16字节，使得就存储器性能而言，能更好的放置下一个代码块；

要在C程序中使用汇编代码，有两种方法：

1. 直接用汇编语言编写源码，在链接阶段将他们与C语言程序链接起来；
2. 在C语言程序中使用内联汇编；

两种汇编代码格式（根据编译时的-masm=intel或者-masm=at&t）进行判断：intel格式省略了后缀，省略了寄存器名字前面的%，用不同的方式来描内存中的位置；和AT&T格式列出操作数的顺序相反，源在前，目的地址在后。

3 数据格式

因为Intel是从16位扩展到32位的，有如下几个术语：

• 8位：字节，后缀为b
• 16位：字，后缀为w
• 32位：双字，后缀为l
• 64位：四字，后缀为q
• 浮点数：32位，4个字节，后缀为s
• 双精度浮点数：64位，8个字节，后缀为l

4 访问信息和常用指令

对于生成8字节结果的指令，对于剩下的字节的处理，有两种方式：

1. 生成1字节和2字节数字的指令会保持剩下的字节不变；
2. 生成4字节数字的指令会把高位4个字节置为0。

操作数形式：

• 源操作数：常数（立即数，用$开头）、寄存器（r开头，R[r]表示它的值）或内存（M[Addr]）
  • 其中寻址使用Imm（rb,ri,s)表示，Imm是里立即数偏移，rb是基址寄存器，ri是变址寄存器，s是比例因子，s必须是1、2、4或8，地址的计算公式为Imm+R[rb]+R[ri]*s
• 目的操作数：寄存器、内存
• 其中，寄存器部分的大小必须与指令最后一个字符指定的大小匹配。

关于数据转移指令和pushq，popq指令：

• movq指令只能以表示为32位补码数字的立即数作为源操作数，然后符号扩展到64位；
• movabsq指令能够以任意64位立即数值作为源操作数，并且只能以寄存器为目的；
• movz表示在从小位移动到大位的过程中，采用0扩展；
• movs表示在从小位移动到大位的过程中，采用符号扩展；
• etlq只能作用于寄存器%eax和%rax，相当于monvslq %eax, %rax
• %rsp保存栈顶的地址，pushq S是先减顶再压值，popq是先弹值再加顶

关于算数逻辑指令：

• leaq rS,D等效于D<-&S，目的是加载有效地址，它不读取内存数据，不触及内存；但是可以为后面的内存引用产生指针，目的操作数必须是一个寄存器；还可以用于计算（利用Imm（rb,ri,s)寻址公式）；
• SAL和SHL均为左移，左移是在右边补上0
• SAR和SHR均为右移，但是前者是算数右移，后者是逻辑右移，前者是在前面补1，后者是在前面补上0
• 一元和二元操作
  • 一元操作的目的和源是同一个。操作数可以是寄存器或内存位置；
  • 二元操作的第二个操作数既是源，也是目的，可以是寄存器或内存位置；第一个操作数还可以是常数；
• 移位操作：移位操作先给出移位量，第二项是要移位的数，可以进行算术和逻辑右移；移位量可以是一个立即数，或者放在单字节寄存器%cl中，移位量以%cl的低m位决定，高位会被忽略），目的操作数可以是寄存器或内存位置。

关于一些特殊的算术操作：

• imulq S是有符号全乘法，idivq S是有符号除法；
• mulq是无符号全乘法，divq是无符号除法；
• cqto转换位八字；
• 其中两个乘法的操作数都是64位，都要求一个参数在%rax中，另一个作为指令的源操作数给出；乘积为127位，高64位放在%rdx中，低64位在%rax中；
• 两个除法都以128位的一个数为操作数（存储方式和上述乘积结果的存储方式相同），另一个直接给出，商存储在%rax中，余数存储在%rdx中；
• cqto隐含的将64位的%rax进有符号扩展，扩展在%rdx中，然后再进行除法；

5 控制

除了整数寄存器，CPU还维护一组单个位的条件码寄存器，可以检测这些寄存器来执行条件分支指令，最常用的条件码有：

• CF：进位标志，用来检测无符号操作的溢出；
• ZF：零标志，判断最近操作的结果是否为0；
• SF：符号标志，最近的操作得到的结果为负数；
• OF：溢出标志，用来检测有符号操作的溢出（正溢出或负溢出）

假设用ADD指令完成等价于C表达式t=a+b的功能，然后根据下面的表达式来设置条件码：

CF (unsigned)t < (unsigned)a
ZF (t == 0)
SF (t<0)
OF (a<0 == b<0) && (t<0 != a<0)

leaq指令不改变任何条件码，因为它是用来进行地址计算的，除此以外其他指令都会设置条件码。

还有两种指令会改变条件码，但是不设置任何的寄存器：

• CMP指令：通过两个操作数之差来设置条件码
• TEST指令行为与AND指令相同。典型的用法是两个操作数是一样的，或者一个操作数是一个掩码，用来指示哪些位应该被测试；

访问条件码：

• 使用set指令根据条件码来对某些值进行设置：如setl表示小于时候设置（注意这里l不是操作数大小）
• 一条set指令的目的操作数是低位单字节寄存器元素之一，或者是一个字节的内存位置，指令会将这个字节设置为0或1
• 有符号比较
  • 当没有发生溢出时（OF为0）
    • 当a-b<0时a<b，那么有SF=1
    • 而当a-b>=0，即a>=b时，SF=0
    • a=b时，ZF=1
  • 当发生溢出时（OF=1）
    • 当a-b<0时，有a>b（SF=1）
    • 反之亦然
    • a=b时，ZF=1
  • 综上，溢出和符号位的亦或，以及和ZF的组合提供了a和b的测试
• 无符号比较'
  • a<b时，a-b<0，CF=1
  • a=b时，ZF=1
  • 综上，进位符号和零标志的组合决定了a和b的测试
• 注意：机器代不会将每个程序值和数据类型联系起来，大多数情况下机器代码对有符号和无符号都执行一样的指令，这是因为许多算术运算对无符号和补码算术运算的位级行为相同。有些情况需要用不同的指令来处理有符号和无符号的操作，例如使用不同版本的右移、除法和乘法指令，以及不同的条件码组合。

关于跳转指令：

• 在产生目标代码文件时，汇编器会确定所有的带标号指令的地址，并将跳转目标（目的指令的地址）编码为跳转指令的一部分；
• 有直接跳转和间接跳转两种
  • 直接跳转：跳转目标作为指令的一部分编码，是给出一个标号作为跳转目标，例如.L1
  • 间接跳转：写法是* 后面跟一个操作数指示符，比如jmp *%rax
• 除了jmp，其他的跳转指令都是有条件的，这些指令的名字与跳转条件与SET指令的名字匹配
• 条件跳转只能是直接跳转
• 跳转目标一般用符号标号书写，有几种不同的编码，最常用的是PC相对的，会将目标指令地址和紧跟在跳转指令后面那条指令的i地址的差值作为编码，地址偏移量可以编码为1、2、4个字节；
• 第二种编码方法是给出绝对地址，用4个字节直接指定目标；
• 当执行PC相对寻址时，程序计数器的值是跳转指令后面那条指令的地址，而不是跳转指令本身的地址。PC相对寻址的好处在于，指令编码比较简洁（因为是差值），并且目标代码可以不做任何改变就移到内存中不同的位置；
• rep和reptz的用法在于：实现重复的字符串操作。在AMD给编译器编写者的指导意见书中可以看到，他们建议用rep后面跟ret的组合来避免使ret指令成为条件跳转指令的目标。如果没有rep指令，当ret指令通过跳转指令到达时，处理器不能正常预测ret指令的目的。这里的rep指令实际上就是一种空操作，以此作为跳转目的插入它，除了能使代码在AMD上运行的更快以外，不会改变代码的其他行为。

关于用条件传送来实现条件分支：

• 因为通过控制的条件转移可能比较低效，一种替代的策略是使用数据的条件转移。这种方法计算一个条件操作的两种结果，然后再根据条件选择是否满足从中选取一个，只需要一条条件转移指令实现。
• 其计算过程是，首先在寄存器中存储一个分支的结果。利用条件转移指令测试另一个分支的情况，如果该分支满足，则把另一个分支的值赋给寄存器。
• 该方法能够提高效率的原因是：流水线通过重叠连续指令的步骤来获得高性能，例如在取同一条指令的同时，执行它前面一条指令的算术运算。要做到这一点，要求能够实现确定要执行的指令序列，这样才能保持流水线中充满了待执行的指令。当机器遇到分支时，只有当分支求值条件完成后，才能决定分支往哪边走。一旦分支预测错误，就会浪费很多时钟周期，导致程序性能严重下降。如果使用条件转移指令，我们可以保证流水线是满的。
• 条件转移指令与SET指令结合，只有当条件满足时，才从源地址运送值到目的地址。不支持单字节的条件传送。
• 同条件跳转不同，处理器无需预测测试的结果就可以执行条件传送，处理器只是读原值，检查条件码，要么更新目的寄存器，要么保持不变。
• 注意，因为两种情况都求值，因此可能存在某个操作有副作用但是被执行了的情况，比如解引了空指针。

do-while循环部分较为简单，这里不解释了。

关于while循环，有两种翻译方法：

第一种是jump to middle（跳转到中间）：

	goto test;
loop:
	body-statement
test:
	t=test-expr
	if(t)
		goto loop;

第二种是guarded-do：

t=test-expr;
if(!t)
	goto done
do
	body-statement
	while(test-expr);
done

或者

t = test-expr
if(!t)
	goto done;
loop:
	body statement
	t=test-expr
	if(t)
		goto loop;
done

for循环部分较为简单，这里不解释了。

关于switch-case语句（具体案例需要看书P159-162，这里不方便解释）：

• 主要使用跳转表的结构，跳转表是一个数组，其中表项i是一个代码段的地址，这个代码段相当于实现当开关索引等于i时程序应该采取的动作。
• 程序代码用开关索引之来执行一个跳转表内的数组引用，确定跳转指令的目标；
• 使用跳转表的优点是，执行开关语句的时间与开关情况的数量无关。
• gcc根据开关情况的数量和开关情况值的稀疏程度来翻译开关语句。
• 当开关数量比较多，且值的跨度范围比较小时，就会使用跳转表

可能出现的情况：

• 情况标号跨过一个不连续的区域（比如部分情况没有标号）；
• 有些情况有多个标号；
• 有些情况会落入其他情况之中；

6 过程

关于过程：

• 过程是一种概述，过程的形式多种多样：包括函数、方法、子例程、处理函数等，但是它们有一些共有的特性；
• 假设P过程调用Q，Q返回到P，过程包括
  • 传递控制
    • 用callq和retq：callq可以是直接的，也可以是间接的，格式同jmp相同；
  • 传递数据
    • 6个以内的参数可以通过寄存器传递，分别为%rdi %rsi %rdx %rcx %r8 %r9
    • 6个以内的数可以通过寄存器传递，超过6个要用栈来传递。设有n个参数要传递且$n>7$，那么我们需要将其保存在栈上。其中第7个参数是保存在栈顶的。通过栈传递参数时，所有的数据大小都向8的倍数对齐。
  • 分配和释放内存
• 栈上的局部存储
  • 大部分的情况下，都可以在寄存器中实现参数传递，但是部分情况下，数据仍然需要存储在内存中，这些情况包括
    • 寄存器不足够存放所有的本地数据
    • 对一个局部变量使用地址运算符&，因此必须为它产生一个地址
    • 某些局部变量是数组或结构，因此必须能够通过数组或结构访问到
  • 寄存器的使用和分配遵循一定的惯例，因为我们需要保证当一个过程（调用者）调用另一个过程（被调用者）时，被调用者不会覆盖调用者稍后会使用的寄存器。为此，x86-64采用了一组统一的寄存器使用惯例。
    • 根据惯例，%rbx, %rbp, %r12-%r15被划分为被调用者保存寄存器。被调用者保存意思是被调用的过程需要保证在程序返回时，这几个寄存器的值和调用它的时候是一样的。（相当于借了别人的东西，无论是不是使用了，都需要保证这几个东西在归还的时候和借用的时候是一样的）这样调用者就不会担心自己借给别人的寄存器中的值被破坏。通常的做法是，要么被调用的过程压根就不用这些值，要么就把这些值都压在栈上。
    • 所有其他寄存器，除了%rsp，都是调用者保存寄存器。任何函数都能修改他们，因此该函数有责任保存好这些寄存器的值。

7 数组分配和访问

这部分主要是地址的计算，leaq的使用，还有一些汇编中的地址计算方法。具体的细节需要通过看书上的例子，暂不总结。

8 异质的数据结构

本节主要的内容为：

• 结构体的存储讲解
• union和结构体的差别，以及union的适用范围
  • 如某个字段的数据类型不确定，如某个二叉树结点的值，既可能是两个指针，也可能是两个double类型值，那么就用union并在一起，通过加入一个枚举类型，来判断这个节点的类型；
  • 还可以使用union来获取一个double值的unsigned类型对应值（不同的数据位表示相同，但是数值不同）
  • 注意union中有数组的时候，数组的值在大端序和小端序机器上排列方式不同；
• 数据的对齐
  • 对齐的好处：简化了形成处理器和内存系统之间接口的硬件设计。
  • 对齐原则是：任何K字节的基本对象的地址都必须是K的倍数。
  • 实现方式是：编译器在汇编代码中放入命令，指明全局数据所需的对齐，如.align 8

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

9.1 函数指针

函数指针提供了一个很强大的存储和像代码提供引用的功能，这些引用可以被程序某个其他部分调用，比如我们定义一个函数：

int fun(int x, int *p); // 定义函数 fun
int (*fp)(int, int*);  // 声明一个指针fp，该条语句的意思是，这个指针指向的函数，必须接受int和in*类型的参数，然后返回一个int类型
fp = fun; // 让函数指针指向这个函数

接下来我们可以使用这个指针来调用这个函数：

int y = 1;
int result = fp(3,&y);

其中，函数指针的值是该函数机器代码表示中的第一条指令的地址。

9.2 内存越界和缓冲区溢出

一个典型的问题在于使用gets函数，gets函数没有办法确定是否为保存整个字符串分配了足够的空间，因此如果用户输入的字符串长度超过了之前分配的大小，就会溢出到不合法的存储区域中。一个经典的案例是如果用户输入的字符串过长，字符串可能会覆盖掉该函数的返回地址，因此在执行ret语句时，可能就会跳转到不合法的区域中去。尤其是在使用缓冲区溢出攻击时，我们如果在获取到了函数的汇编代码，我们可以刚好让自己跳转的字符串覆盖掉返回地址，让该函数返回到我们想要它返回的地方。我们可以在程序中插入恶意代码，让该函数返回到恶意代码处，执行恶意代码。这就是一种缓冲区溢出攻击。或者通过缓冲区溢出，让自己的攻击代码覆盖原有的代码，以此诱惑系统执行。

相比gets函数，一个更好的版本是使用fgets函数，该函数包括一个参数，限制读入的最大字节数。类似gets的可能产生缓冲区溢出漏洞的函数还有strcpy、strcat、sprintf等等，这些都要谨慎使用。

一个缓冲区溢出的经典案例是蠕虫。注意蠕虫和病毒的差别在于，蠕虫可以自己运行，并且将自己的等效副本传播到其他机器，而病毒能将自己添加到包括操作系统在内的其他程序中，但它不能独立运行。

9.3 对抗缓冲区溢出攻击

现代操作系统对抗缓冲区溢出的方法有几种：

1. 栈随机化
   • 为了向系统中插入攻击代码，攻击者既要插入代码，也要插入指向这段代码的指针。要知道这个指针，我们就必须知道这个字符串放置的栈地址。过去程序的栈非常容易预测，因此许多系统都可以遭受到同一种病毒的攻击，这被称为安全单一化。
   • 栈随机化的思想使得栈的位置在每次运行时都有变化，实现的方式是程序开始时，在栈上分配一段0-n字节之间的随即大小的空间，程序不使用这段空间，但是它使得程序每次执行后续栈的位置发生了变化。分配的n必须足够大，来让足够多的栈地址变化，但是又要足够小，不至于浪费太多空间。
   • 在Linux系统中，栈随机化已经变成了标准行为。这类技术被称为地址空间布局随机化（ASLR）。使用这种技术，每次运行时程序的不同部分，都会加载到内存的不同区域中。
   • 当然，部分攻击者使用蛮力克服随机化，可以反复的用不同的地址进行攻击。一种常见的把戏是在实际的攻击代码前插入很长一段的nop指令。只要攻击者能够猜中这段序列中的某个地址，程序就会经过这个序列，到达攻击代码。这个序列常用的术语是空雪橇操作（nop sled）。
   • 因此栈随机化不能完全的提供安全保障。
2. 栈破坏检测
   • 栈破坏检测的核心思想是在发生了越界写的时候，在造成任何有害结果之前，尝试检测到它。
   • 最近的gcc版本在产生的代码中加入了一种栈保护者机制，来检测缓冲区越界。其思想是在栈帧中任何局部缓冲区与栈状态之间存储一个特殊的金丝雀值，也成为哨兵值。这个值是随机产生的，因此攻击者无法预测这个值是什么。那么在恢复寄存器状态和从函数返回之前，程序检查这个值是否发生了改变（通过存储金丝雀值到栈上，然后利用xorq异或指令，在程序运行结束后判断栈位置处的值，和已经保存到栈上的金丝雀值是否相同）。如果是，那么程序异常终止。
3. 限制可执行代码区域
   • 在典型的程序中，只有保存编译器代码的那部分才是需要可执行的，其他部分被限定为只允许读和写。
   • 虚拟内存在逻辑上被分成了页，典型的每页是2048字节或4096个字节。硬件支持多种类型的内存保护，许多系统允许控制3种访问形式：读、写和执行（将内存中的内容看作机器级代码）
   • 以前，x86体系结构将读和执行访问控制合并成1位，这样任何可读的都是可执行的。
   • 栈必须是可读可执行，栈上的字节可读可执行。很多机制限制了很多页是可读但是不可知性，但是这带来了严重的性能损失。
   • AMD为它的64位处理器的内存保护引入了NX位（不执行位），将读和执行模式分开，Intel也跟进了。有了这个特性，栈可以标记为可读和可写，但是不可执行。而检查页是否可执行由硬件来完成，效率上没有损失。
   • 有些类型的程序要求动态产生和执行代码的能力，例如即时编译技术为解释语言编写的程序动态的查收你哼代码，以提高执行性能。是否能够将可执行代码限制在由编译器在创建原始程序时产生的那个部分中，取决于语言和操作系统。

9.4 支持变长栈帧

• 前面的程序的特点在于，编译器能够预先确定需要为栈帧分配多少空间。但是有些函数，需要的局部存储是变长的。例如使用alloca标准库函数，可以在栈上分配任意字节数量的存储。当代码声明一个局部变长数组时，就会发生这种状况。
• 为了管理变长栈帧，x86-64代码使用寄存器%rbp作为栈指针（有时称为基指针）。代码必须把%rbp之前的值压到栈上，因为他是一个被调用者保存寄存器。然后在函数的执行过程中，都使得%rbp指向那个时刻栈的位置，然后用固定长度的局部变量相对于%rbp的偏移量来引用它们。
• 在调用这个过程是，首先需要压%rbp，将%rbp设置为当前的%rsp。然后分配空间，进行一系列操作（这时%rsp会发生变化）。而在调用结束后，会先令%rsp = %rbp，然后通过popq操作把过去的%rbp还原。
• 现代编译器支持带%rbp和不带%rbp混用，只要按照惯例将%rbp作为被调用者保存寄存器来处理即可。

10 浮点代码

这一节的内容感觉不是很常用，先放一放吧。