Lecture 9

Abstract

我们从无界字符串输入继续分析缓冲区溢出：越界写如何覆盖栈上的返回地址，又如何改变程序的控制流。随后把汇编指令进一步拆成机器能够识别的字节，以 Y86-64 为例，逐项建立操作码、寄存器编号与常数字段的编码。最后从程序员眼中的连续地址空间转向实际存储电路，比较 SRAM 与 DRAM，并说明行列选择怎样把大量存储单元组织成可寻址的内存。

一、从数组越界走到返回地址

回放 A 21:15

上一课的结构体把 int a[2] 放在 double d 前面。我们计算 a[i] 的地址时使用“基址加上下标乘元素大小”；机器执行写入时，并不会自动把这个地址限制在 a[0] 与 a[1] 的范围内。因此，i 增大以后，写操作可能覆盖 d 的部分字节，再继续向外破坏调用中的其他状态。

这个例子留下一个更严重的问题：如果覆盖的恰好是返回地址，会发生什么？返回地址虽然也是内存中的一组字节，却决定函数执行完以后从哪里继续。破坏普通数据会改变计算结果，破坏返回地址则会改变后续执行的位置。

我们沿用上一课的 gets 教学实现。它接收一个目的字符指针，从标准输入不断读字符，遇到换行或 EOF 才停止，最后补 \0。问题出在接口里没有缓冲区容量：它知道从哪里开始写，却不知道写到哪里必须停止。

现在用一个极小的缓冲区，把问题集中起来：

void echo(void) {
    char buf[4];
    gets(buf);
    puts(buf);
}

void call_echo(void) {
    echo();
}

echo 先读入一行，再打印这行。buf 能容纳 4 个字节，字符串结尾的 \0 也占一个字节，因此完整放在数组内的输入最多有 3 个普通字符。输入更多字符时，gets 仍会顺着地址继续写。

我们可能观察到：输入已经超过四个字符，程序却还能把它打印出来；继续增加输入长度以后，程序才出现段错误。这里需要分开两个边界：数组的合法边界与返回地址在具体栈帧中的位置。越过数组边界，并不等于下一字节马上就是返回地址；中间还可能有未使用空间。所以程序暂时看起来能运行，不能说明写入没有越界。

顺着汇编追踪局部空间

课堂示例中的 echo 为局部数据分配 24 字节，关键指令如下：

echo:
    subq $0x18, %rsp
    movq %rsp, %rdi
    call gets
    movq %rsp, %rdi
    call puts
    addq $0x18, %rsp
    retq

调用者也有自己分配和撤销的栈空间。画面中的完整调用序列为：

call_echo:
    subq $0x8, %rsp
    movl $0x0, %eax
    callq echo
    addq $0x8, %rsp
    retq

这次 callq echo 位于 0x4006be，下一条指令位于 0x4006c3，所以压入栈中的返回地址就是 0x4006c3。

先把 %rsp 减去 0x18=24，栈顶向低地址移动，腾出局部空间。随后把 %rsp 复制到 %rdi，把这块空间的起始地址作为 gets 的第一个参数。读入后再次把同一地址交给 puts，最后加回 24 字节并执行 retq。

设 echo 入口处 %rsp=s。进入前的 call echo 已把返回地址放在 $s$ 到 $s+7$。分配局部空间后，缓冲区从 $b=s-24$ 开始，因此栈布局为：

这里的 24 字节是整个局部分配量，buf 本身仍然只有 4 字节。输入字符写入 $b,b+1,b+2,\ldots$，地址不断增大；栈的分配方向向低地址，与字符串在缓冲区中的写入方向可以同时成立。

还要把终止字符计算在内。若输入有 $n$ 个普通字符，则 gets 写入的范围是

$$[b,b+n],$$

其中最后一个字节 $b+n$ 存放 \0。所以 $n=24$ 时，24 个普通字符填满偏移 0—23，终止字符就已经写到返回地址的第一个字节；不必等到第 25 个普通字符才开始破坏返回地址。

为什么往往在返回时才崩溃？

我们现在回答课堂中的追问：越界输入之后，程序是在读入时、打印时，还是返回时出问题？沿这份栈布局看，gets 可能先完成写入，puts 也可能把字符串打印出来。等到执行 addq $0x18,%rsp，栈顶重新移到原本存放返回地址的位置；retq 再从这里取出下一条指令地址。

正常情况下，取出的值是 call echo 后一条指令的地址。返回地址被覆盖以后，取出的却是输入字符和 \0 拼出来的值。处理器据此转移控制，因而可能跳到无效位置并触发段错误，也可能跳到另一个有效但错误的位置。这就把一次数据写入错误连接到了控制流错误。

画面中的输入为 012345678901234567890123，共 24 个普通字符，加上终止字符共写入 25 字节。返回地址原来的最低有效字节是 c3，被最后的 00 覆盖后，0x4006c3 变为 0x400600。示例先打印出这行输入，随后报告 Segmentation fault，与返回时才使用损坏地址的推理相符。

局部纠正：调用前把 %eax 清零，不能解释为“普通函数只有返回零才正确”。返回寄存器的数值由函数返回类型和语义决定；void echo 没有整数返回值要求。

二、输入数据怎样变成控制流

回放 A 36:09

再往前推一步：如果输入内容不只是随意的长字符串，而是有意安排过的字节，覆盖返回地址就可能成为代码注入（code injection）的入口。

我们在图中区分三部分：局部缓冲区内放入的机器指令字节；把写入位置延伸到返回地址之前的 padding；以及覆盖原返回地址的新值。新值指向缓冲区中那些指令的起点。当函数返回，retq 把新值装入指令指针 %rip，控制权就可能转入输入中的代码。

只把指令字节放进缓冲区，还没有完成控制转移。关键在于返回地址也要被改变，使程序实际走到那段字节。因此我们需要同时理解数据所在的位置、越界写到达的位置，以及返回时读取的位置。这也说明，栈上既有普通数据又有控制信息，是这个例子能够产生严重后果的原因。

从源头限制写入长度

第一种保护方式是改正输入代码，使输入操作知道目的容量。课堂用 fgets 替换无界的 gets：

void echo(void) {
    char buf[4];
    fgets(buf, 4, stdin);
    puts(buf);
}

第二个参数给出缓冲区容量。成功读取时，它最多放入 sizeof buf - 1 个字符，再保留一个字节写 \0。我们的 buf[4] 因而最多接收 3 个字符。接口把“从哪里开始”与“最多写多少”一起交给输入函数，边界才能受到控制。

这个例子中的 4 也可以写成 sizeof buf，直接由数组容量给出限制。页面同时列出为字符串复制指定长度、为 scanf 的 %s 指定合适最大宽度的思路：每次写入都要与目的空间相配。

让栈地址难以预测

第二种方法是随机化布局。图中的想法是在栈的起始位置引入随机偏移，使每次运行时局部缓冲区的实际地址不再固定。原先试图覆盖成某个确定地址的输入，就难以事先知道应该写什么值。

随机化针对的是代码注入依赖的地址知识：要让返回地址指向缓冲区，必须知道缓冲区在哪里。把位置变成运行时的不确定量，会增加攻击成功的难度。

在缓冲区和关键状态之间放置 canary

第三种方法是栈 canary。我们在局部缓冲区与返回地址等关键状态之间放入一个事先保存好的特殊值，并在返回前检查它是否仍然相同。顺着地址向外覆盖的输入若先经过 canary，就会改写它；检查发现变化以后，程序终止这次执行，避免继续使用已经损坏的返回地址。

这个名字借用了矿井中用金丝雀预警危险的比喻：先检查一个敏感的信号，再决定能否继续。源头的边界检查、地址随机化和 canary 分别作用于写入边界、地址预测与破坏检测，关注的是这条错误链中的不同环节。

三、为什么还要学习指令编码？

回放 A 43:00

我们已经能读 movq、比较、跳转、函数调用等汇编，但助记符仍是人使用的表示。机器取到的是内存中的二进制位串。接下来的问题是：怎样把“做什么”“操作哪些数据”放进这些位，让硬件能够辨认？

指令集体系结构（ISA）提供软件与硬件之间的接口。软件按照规定的指令及其行为编写程序；支持这个 ISA 的处理器按照相同语义执行。这样，我们可以讨论程序中的加法、分支和访存，而不必先知道每台处理器内部如何搭建电路。指令编码则把接口进一步落实成明确的位字段，为后面分析取指、译码与执行提供基础。

课堂也用专用集成电路（ASIC）作对照。视频解码器、信号处理等专用硬件，可以接收数据地址和启动等控制信号，完成预先设计好的工作。通用处理器则用一条条指令描述可组合的操作。我们在这里关注后者：一串位如何表达可执行的操作序列。

一条指令首先要表达两个方面：

不同指令需要的操作数数量和形式不同。addq 使用两个寄存器，立即数搬运要携带常数，跳转要给出目的地址，而 nop 不需要显式操作数。编码必须让这些差异可以被唯一识别。

四、用 Y86-64 建立一套可读的编码

回放 B 05:14

我们采用 CSAPP 中的 Y86-64。它保留了熟悉的 64 位寄存器、搬运、算术、跳转、调用和栈操作，用较简单的格式展示完整的编码方法。指令类别如下：

nop 看起来“什么也不干”，但它仍占据一个指令位置。后面学习流水线时，我们会看到在某些位置插入空操作的用途；课堂还以指令预取的工作举例，说明代码本身也需要提前进入指令缓存。这里先抓住 nop 的语义：没有新的数据操作，不等于它不存在于指令流中。

平铺编号，还是先分类再编号？

课堂数出这组指令共 27 条。如果把每条指令直接编一个不同号码，我们至少需要

$$\lceil\log_2 27\rceil=5$$

位，因为 $2^4=16<27\leq32=2^5$。这是按 27 种选择计算的信息位数。

Y86-64 采用另一种组织：先用 4 位标记大类，再用 4 位标记类内功能。第一个字节分成

$$\underbrace{\text{icode}}_{4\text{ bits}} \quad \underbrace{\text{ifun}}_{4\text{ bits}}.$$

例如四种 OPq 共享 icode=6，再用 ifun=0,1,2,3 区分加、减、按位与、按位异或。条件跳转与条件搬运也各自共享一类。这样得到的是规则清楚的分组格式，而不是单纯追求最少位数。

表中每个十六进制字符表示 4 位，rA:rB 表示两个半字节合成一个寄存器字节；f 是所选功能号。Y86-64 的最长指令为 10 字节：1 字节操作码、1 字节寄存器编号，再加 8 字节常数。

功能号的对应关系是：

这也解释了为何无条件搬运可以与条件搬运共用 icode=2：把 ifun=0 看作不附加条件的情况即可。

五、寄存器也需要编号

回放 B 15:14

机器字节中不会保存 %rax 这样的文本名字，而是保存它的编号。一个半字节能表示 16 种值。Y86-64 把 0—E 分给 15 个程序寄存器，把 F 留作“没有寄存器”的标记：

%rip 是指令指针，不是表中用 F 编号的第十六个普通寄存器。

看见 rA、rB 时，还要结合指令理解角色。对于 addq rA,rB，前者是一个源，后者既提供另一个源又接收结果：

$$R[rB]\leftarrow R[rB]+R[rA].$$

而在 rmmovq rA,D(rB) 中，rB 给出地址基址，最终被写入的是内存。不能机械地把第二个寄存器字段都叫作结果寄存器。

课堂例子：编码 addq

把下面一条指令写成机器字节：

addq %rax, %rsi

第一字节中，算术类是 6，加法功能号是 0，得到 60。第二字节中，源 %rax 编号为 0，目的 %rsi 编号为 6，得到 06。完整编码是：

60 06

反向读也相同：先从 60 确定这是寄存器加法，再从 06 确定操作数，执行 %rsi ← %rsi + %rax。操作码告诉我们怎样解释后面的位，寄存器字段告诉我们到哪里取值及把结果放在哪里。

加法还根据结果设置条件码；这组 OPq 会更新 ZF、SF、OF，为后续条件跳转和条件搬运提供判断依据。因此，指令的功能既包括寄存器中的结果，也包括条件状态的变化。

课堂题：哪些指令的编码已经完整？

回放 B 19:11

题目给出各指令的操作码，以及需要时的寄存器字节，但暂时没有任何立即数、位移或目标地址字段，要求判断：Which instruction is complete?

我们逐类检查所需信息：

所以缺的并不是更多的寄存器编号，而是数值字段。下一步正是把这些数值也放进指令。

六、立即数与位移放在哪里？

回放 B 19:11

只有操作码和寄存器字节，还不能表达所有指令。irmovq 需要立即数，内存搬运需要位移，跳转与调用需要目标地址。这些值各用一个 8 字节常数字段保存。

课堂例子：立即数搬运

irmovq $0x2951, %rdi

先写 30，表示立即数到寄存器搬运。它没有源寄存器，所以寄存器字节的高半字节填 F；目的 %rdi 编号为 7，得到 F7。

剩下的常数 $0x2951$ 要占满 8 字节。按数值的高位到低位写是

00 00 00 00 00 00 29 51

按小端序存入指令流，则低有效字节先出现：

51 29 00 00 00 00 00 00

合起来，完整 10 字节为：

30 F7 51 29 00 00 00 00 00 00

小端序作用于这里的 8 字节常数。首字节 30 中的 icode、ifun，以及寄存器字节 F7 中两个字段的顺序，都按照格式表定义的位置解释。

课堂例子：寄存器写入内存

rmmovq %rsi, 0x2591(%rsp)

这条指令把 %rsi 中的 8 字节数据写入地址

$$R[\%rsp]+0x2591.$$

0x2591 是加到基址上的位移。编码时，rmmovq 首字节为 40，源 %rsi 是 6，基址 %rsp 是 4，寄存器字节为 64；位移按同样的小端顺序存放：

40 64 91 25 00 00 00 00 00 00

局部纠正：回放此页把源寄存器排成 $rsi，应为 %rsi；这里的源是寄存器，位移确为画面中的 0x2591。

内存到寄存器的 mrmovq 也用这个结构：首字节变为 50，rA 标记接收数据的寄存器，rB 给出地址基址，再附加 8 字节位移。至此，四种搬运形式都能得到完整表示。

七、跳转目标与相对地址

回放 B 22:07

jle label 中的 label 在汇编文本中是一个名字，编码时最终需要得到可以决定下一次取指位置的数值。Y86-64 的跳转用首字节 7f 选择条件，后接 8 字节目标地址；例如 jle 首字节为 71。call 首字节为 80，也后接 8 字节目标。两者没有显式寄存器操作数，因此没有寄存器字节，总长度都是 9 字节。

课堂接着比较绝对地址与相对地址。绝对地址直接给出目的地 $T$；相对地址则保存某个约定基准 $P$ 到目标的差值

$$\Delta=T-P, \qquad T=P+\Delta.$$

以 x86 的常见 PC 相对调用为例，$P$ 取紧接调用指令之后的地址。如果代码整体移动 $K$ 字节，则新的目标与基准同时变化：

$$(T+K)-(P+K)=T-P=\Delta.$$

位移不变，因而这段代码可以在整体移动后仍保持相同的内部跳转关系；附近目标也常能用较短位移表示。这里的 Y86-64 教学格式选择直接保存 8 字节绝对目标，x86-64 的 PC 相对格式则展示了另一种设计选择。

课堂提出的设计问题是：如果目标地址所需的位数超过为它预留的字段，或者希望把目标字段压缩到 4 字节，怎么办？一种办法是加长指令，直接装入更大的地址；另一种办法是在可表示范围内保存相对位移。前者格式直接但占空间，后者把“目标有多大”改为“目标离基准有多远”的表示问题。

八、指令为什么有不同长度？

回放 B 24:30

现在回看格式表：halt 只要一个字节，寄存器加法只要两个字节，带 8 字节常数的搬运则要十个字节。操作所需信息不同，采用变长格式就可以让简单指令少占空间。

但取指和译码也因此必须辨认长度。读出第一字节以后，硬件要判断后面有没有寄存器字节、有没有常数字段，从而找到下一条指令的起点。我们已经看到 Y86-64 是怎样让这种判断保持规则的：icode 确定字段结构，ifun 再确定具体功能。

定长格式采用另一种折中。若所有指令都占 $L$ 字节，顺序执行时下一条位置直接是 $PC+L$，取指和边界识别更简单；代价是简单操作也占同样宽度，某些位可能没有用上。变长格式往往有利于代码紧凑，定长格式便于规则化的硬件设计。

课堂以 x86-64 的变长指令和定长 RISC 格式作比较。x86-64 一条指令可以长达 15 字节；本节的 Y86-64 表最长是 10 字节。比较编码时，我们同时考虑存储空间与取指、译码逻辑，而不能只数操作码用了多少位。

九、从连续地址空间走到实际内存

回放 B 26:29

从 ISA 与程序员的视角看，内存像按地址排列的一长串字节。代码、数据、堆、共享映射和运行时栈，都放在这个地址空间中。处理器给出地址，把指令或数据取回来，执行计算以后再把结果写回寄存器或内存。

实际硬件要把这个抽象做出来。我们先画一个 RAM（random access memory，随机访问存储器）接口：输入 $n$ 位地址，指定一个存储位置；数据端口每次传送 $k$ 位；写使能信号决定是否将输入数据写入所选位置，读操作则从所选位置取得内容。

若有 $n$ 位地址、每个地址对应 $k$ 位数据，则这个接口可表示

$$2^n\text{ 个位置},\qquad 2^n k\text{ bits 的总容量}.$$

“随机访问”在这里指能够按地址选择位置。接下来我们要问的是：其中每一位究竟靠什么电路保存，又怎样把许多位接起来？

理想内存与设计折中

理想内存可以有无限容量，访问没有延迟，几乎不占面积、不消耗能量，还能同时传送无限多的数据。把这些目标放在同一块实际电路上，就会遇到取舍。

容量变大，电路规模与连接范围会增加；追求更快访问，往往需要面积和成本更高的单元；增加端口以同时进行更多访问，也会使电路更复杂。我们区分两个性能量：延迟是一次访问从发出到得到结果所需的时间，带宽是单位时间能够传送的数据量。更多端口能提高并行访问能力，却不是免费得到的。

这正是后面建立存储层次的动机。先理解不同存储单元的速度、密度和成本，才能理解为什么系统会同时采用多种存储技术。

十、SRAM：用反馈保存一位

回放 B 34:41

SRAM 是 static random access memory，静态随机访问存储器。我们从前面时序逻辑中见过的交叉耦合反相器重新出发：两个反相器首尾相接，一侧为 1，另一侧就为 0；反馈又把这组状态维持下去。这样得到两个稳定状态，可以表示一个 bit。

如果内部节点是 $Q$ 与 $\overline Q$，稳定时满足

$$Q=\neg\overline Q, \qquad \overline Q=\neg Q.$$

因此 $(Q,\overline Q)=(1,0)$ 与 $(0,1)$ 都能自洽地保存。

仅仅保存还不够，我们还要选择何时把这个单元接到外部。课堂图在两侧加访问晶体管，由同一条字线（word line）控制，连接到一对位线（bit lines）。选中这一行时，访问通路导通，内部状态可参与读写；未选中时，单元维持原状态。

我们数一下图中的晶体管。一个 CMOS 反相器由一个 p 型和一个 n 型晶体管组成，两个反相器共四个；两条访问通路再各用一个，共计

$$2\times2+2=6.$$

这就是典型六晶体管 SRAM 单元，每个单元保存一位。它在供电期间依靠反馈保持状态，不需要像 DRAM 那样周期刷新。

课堂追问它与 D latch、D flip-flop 的联系。它们都能保存状态，但我们先前构造锁存器、触发器时，还要增加使能或时钟控制逻辑：D latch 对使能电平敏感，D flip-flop 则在指定时钟边沿采样。SRAM 单元集中解决阵列中的一位存储与选通问题，因此可以采用这里更简洁的结构。

十一、DRAM：把一位保存成电荷

回放 B 39:11

DRAM 是 dynamic random access memory，动态随机访问存储器。它采用更小的单元：一个电容保存电荷，一个访问晶体管控制电容与位线之间的连接。课堂先用充电表示 1、放电表示 0，说明这一位数据的物理载体。

读出并不是把电容当成一个始终能强驱动整根位线的电源。我们先把位线预充到约 $V_{DD}/2$，再打开字线，让存储电容与位线连接。如果单元原先电压较高，电荷分享会使位线略高于中间值；如果原先较低，位线会略低于中间值。感应电路识别这点偏差，再把它放大成明确的逻辑 1 或 0。

用课堂的数值直觉，若满幅电压取 1 V，中间值约为 0.5 V。我们关心的是接通以后相对 0.5 V 的微小上升或下降，而不是等待位线靠单元直接达到完整的 1 V 或 0 V。

电容会漏电，保存的电荷不能无限期维持；因此系统需要周期性地读出并恢复各单元，这就是刷新（refresh）。“动态”这个名字对应的正是保存内容需要持续刷新这一特征。

我们现在比较两者：

寄存器、SRAM 缓存、DRAM 主存提供了不同速度和容量的存储位置。我们由此开始看到：内存的硬件实现有层次，程序使用的地址抽象却可以保持统一。

电路中的扰动也可能改变程序数据

回放 B 43:20

课堂以 RowHammer 补充一个物理层面的例子。DRAM 单元排成行列，反复激活某些行可能扰动附近行，使附近存储单元在刷新前发生位翻转。于是，程序没有正常写入某个位置，该位置的内容也可能因硬件扰动而改变，进而破坏数据或程序行为。

局部纠正：这里讨论的经典 RowHammer 是 DRAM 的行扰动问题，参见原始论文；其机制不能直接归到上述六晶体管 SRAM 单元。

它与前面的缓冲区溢出从不同方向揭示同一件事：软件里的数值最终由实际的内存状态承载。一个通过越界写改变邻近字节，另一个通过物理扰动改变邻近单元。

十二、用行列选择组织存储阵列

回放 B 46:00

单个 SRAM 或 DRAM 单元只保存一位，我们需要把许多单元组织起来。课堂先从二维阵列说明：行选择信号选中一行，使该行的数据进入读出通路或行缓冲区（row buffer）；随后列选择从中选出需要的部分。

假设一行有 4 个候选组，要选择其中一个，列编号至少需要

$$\log_2 4=2$$

位。列选择逻辑可以用多路选择器（MUX）完成：行缓冲区提供各候选输入，列地址作为选择信号，输出所选组。这里是选择电路，而不是用按位与掩码来保存某一组。

地址拆成两部分

若阵列有 $2^r$ 行、每行 $2^c$ 个位置，那么选择一个位置共需 $r+c$ 位地址。按课堂先行后列的约定，把地址的前 $r$ 位交给行译码器，把后 $c$ 位交给列选择逻辑。行译码器将二进制行号转换成仅一条字线有效的信号；列逻辑再从选中行中取得目标位置。

课堂用一个 $4\times4$ SRAM 阵列继续追踪这一过程，16 个单元分别标记为 0000 到 1111。先用地址中的两位选行，再用另外两位选列。我们可以逐步检查：两位行号有 4 种选择，两位列号也有 4 种选择，合起来能够区分 $4\times4=16$ 个位置。每个位置存一位，总容量是 16 bit，地址宽度是 4 bit。

例如图中框出的 Word line 2 对应行号 10，这一行四个单元的地址依次为 1000、1001、1010、1011。若读取 1001，先由高两位 10 选第三行，再由低两位 01 通过 MUX 选第二列，得到该地址存的一位数据。

读某一位的过程仍然回到单元的访问通路：所选行的字线导通，内部状态接上位线；再由列选择取得目标输出。行列译码解决“选谁”，单元电路解决“怎样保存和读出”，两部分合起来才构成一个可按地址访问的 RAM。

最后回顾的是一个 6 bit memory：两行、每行三位，利用前面学过的 D 型存储元件构造。这里只有两个可寻址的三位字，因此地址 Addr[0] 只需一位；地址为 0 时选上行，为 1 时选下行，三个数据端分别对应 Bit₂、Bit₁、Bit₀。

若地址位为 $a$、写使能为 $w$，图中的两行写入使能分别为

$$e_0=\neg a\land w,\qquad e_1=a\land w.$$

只有所选行在写使能有效时接收三个输入位；读出一侧则用行号分别选通各行的 Q，再把每列两行的选通结果合成一个输出。我们由此分清：6 bit 是总容量，1 bit 是地址宽度，3 bit 是每个地址对应的数据宽度。

来源与补全：本篇据 2026-10-15 A（185278）与 B（182998）完整转写及实际回放画面整理，并衔接上一课的 gets 与结构体越界例子。指令格式、功能号及寄存器编号核对 CSAPP 第三版 §4.1.2—§4.1.3（印刷页 392—396）；SRAM、DRAM 和阵列组织核对 §6.1.1（印刷页 617—620）。地址跟踪、终止字符位置与编码拆分补齐中间计算步骤；本课止于行列寻址。课前纸面测验未展示题面，现有音画不足以恢复题干。