引言之前我们讲到栈被操作系统安排在进程的高地址处它是向下增长的。但这只是对栈相关知识的“浅尝辄止”。那我们今天这节课就会跟着前面的脉络让你可以更深刻地理解栈的运行原理。栈是每一个程序员都很熟悉的话题但你敢说你真的完全了解它吗我相信你在工作中肯定遇到过栈溢出StackOverflow的错误比如在写递归函数的时候当漏掉退出条件或者退出条件不小心写错了就会出现栈溢出错误。我们也经常听说缓冲区溢出带来的严重的安全问题这在日常的工作中都是要避免的。所以今天这节课我们继续深入探讨一下栈这个话题我会带你基于“符合人的直观思维”也就是函数的层面和 CPU 的机器指令层面多角度来理解栈相关的概念。这样你以后遇到与栈相关的问题的时候才知道如何着手进行排查。最后我们还会通过一个缓冲区溢出攻击栈的案例看看我们在日常工作中如何提升代码的健壮度和安全性。函数与栈帧当我们在调用一个函数的时候CPU 会在栈空间这当然是线性空间的一部分里开辟一小块区域这个函数的局部变量都在这一小块区域里存活。当函数调用结束的时候这一小块区域里的局部变量就会被回收。这一小块区域很像一个框子所以大家就命名它为 stack frame。frame 本意是框子的意思在翻译的时候被译为帧现在它的中文名字就是栈帧了。所以我们可以说栈帧本质上是一个函数的活动记录。当某个函数正在执行时它的活动记录就会存在当函数执行结束时活动记录也被销毁。不过你要注意的是在一个函数执行的时候它可以调用其他函数这个时候它的栈帧还是存在的。例如A 函数调用 B 函数此时 A 的栈帧不会被销毁而是会在 A 栈帧的下方再去创建 B 函数的栈帧。只有当 B 函数执行完了B 的栈帧也被销毁了CPU 才会回到 A 的栈帧里继续执行。我们举个例子说明一下就很好理解了。你可以看一下这个代码#include stdio.h void swap(int a, int b) { int t a; a b; b t; } void main() { int a 2; int b 3; swap(a, b); printf(a is %d, b is %d\n, a, b); }你可以看到在 swap 函数中a 和 b 的值做了一次交换但是在 main 函数里打印 a 和 b 的值a 还是 2b 还是 3。这是为什么呢从栈帧的角度这个问题就非常容易理解在 main 函数执行的时候main 的栈帧里存在变量 a 和 b。当 main 在调用 swap 方法的时候会在 main 的帧下面新建 swap 的栈帧。swap 的帧里也有局部变量 a 和 b但是明显这个 a、b 与 main 函数里的 a、b 没有任何关系不管对 swap 的帧里的 a/b 变量做任何操作都不会影响 main 函数的栈帧。接下来我们再通过一个递归的例子来加深对栈的理解。由于递归执行的过程会出现函数自己调用自己的情况也就是说一个函数会对应多个同时活跃的记录即栈帧。所以理解了递归函数的执行过程我们就能更加深刻地理解栈帧与函数的关系。当我们在谈递归时我们在谈什么我们先看一下最经典的递归问题汉诺塔。汉诺塔问题是这样描述的有三根柱子记为 A、B、C其中 A 柱子上有 n 个盘子从上到下的编号依次为 1 到 n且上面的盘子一定比下面的盘子小。要求一次只能移动一只盘子且大的盘子不能压在小的盘子上那么将所有盘子从 A 移到 C 总共需要多少步这道题的详细分析过程是一种递归推导的过程不是我们这节课的重点如果你对解法感兴趣的话可以自己查找相关资料。我们这里重点来讲解递归程序执行的过程中栈是怎么样变化的这样可以帮助我们理解栈的基本工作原理。你先看一下汉诺塔问题的求解程序#include stdio.h void move(char src, char dst, int n) { printf(move plate %d form %c to %c\n, n, src, dst); } void hanoi(char src, char dst, char aux, int n) { if (n 1) { move(src, dst, 1); return; } hanoi(src, aux, dst, n-1); move(src, dst, n); hanoi(aux, dst, src, n-1); } int main() { hanoi(A, C, B, 5); }这段代码可以打印出借由 B 柱子将 5 个盘子从 A 搬移到 C 的所有步骤。这个的核心是 hanoi 函数在深入分析代码的执行过程之前我们可以先从符合直观思维的角度尝试理解 hanoi 函数。hanoi 函数有四个参数。第一个 src 代表要搬的起始柱子开始时是 A第二个代表目标柱子开始时是 C第三个代表可以借用的中间的那个柱子开始时是 B第四个参数代表一共要搬的盘子总数开始时是 5。代码的第 13 行的意义是如果要从 A 搬 5 个盘子到 C可以先将 4 个盘子搬到 B 上然后第 14 行代表将第 5 个盘子从 A 搬到 C第 15 行代表把 B 上面的 4 个盘子搬到 C 上去。第 8 行的判断是说当只搬一个盘子的时候就可以直接调用 move 方法。以上就是递归程序的设计思路。下面我们再具体分析这个代码的执行过程。为了简便起见我们选择 n3 进行分析。可以看到当程序在执行 hanoi(A, C, B, 3) 时CPU 会为其创建一个栈帧这一帧里记录着变量 src、dst、aux 和 n。此时 n 为 3所以代码可以执行到第 13 行然后就会调用执行 hanoi(A, B, C, 2)。这代表着将 2 个盘子从 A 搬到 B同样 CPU 也会为这次调用创建一个栈帧当这一次调用执行到第 13 行时会再调用执行 hanoi(A, C, B, 1)代表把一个盘子从 A 搬到 C。不过由于这一次调用 n 为 1所以会直接调用 move 函数打印第一个步骤“把盘子 1 从 A 搬到 C”。接下来程序就会回到 hanoi(A, B, C, 2) 的栈帧继续执行第 14 行打印第二个步骤”把盘子 2 从 A 搬到 B”。然后再执行第 15 行也就是执行 hanoi(C, B, A, 1)。这一步的栈帧变化你可以看下面这张图。我们看到在调用 hanoi(C, B, A, 1) 的时候由于 n 等于 1所以就会打印第三个步骤“把盘子 1 从 C 搬到 B”此时 hanoi(C, B, A, 1) 就执行完了。那么接下来程序就退回到 hanoi(A, B, C, 2) 的第 15 行的下一行继续执行也就是函数的结束这就意味着 hanoi(A, B, C, 2) 也执行完了。这个时候程序就会回退到最高的一层 hanoi(A, C, B, 3) 的第 14 行继续执行。这一次就打印了第四个步骤“把盘子 3 从 A 搬到 C”此时的栈帧如上图 (b) 所示。然后程序会执行第 15 行再次进入递归调用创建 hanoi(B, C, A, 2) 的栈帧。当它执行到第 13 行时就会再创建 hanoi(B, A, C, 1) 的栈帧此时栈的结构如上图c所示。由于 n 等于 1这一次调用就会打印第五个步骤“把盘子 1 从 B 搬到 A”。再接着就开始退栈了回到 hanoi(B, C, A, 2) 的栈帧继续执行第 14 行打印第六个步骤“把盘子 2 从 B 搬到 C”。然后执行第 15 行也就是 hanoi(A, C, B, 1)此时 n 等于 1直接打印第七个步骤“把盘子 1 从 A 搬到 C”。接下来就执行退栈这一次每一个栈帧都执行到了最后一行所以会一直退到 main 函数的栈帧中去。退栈的过程比较简单你自己思考一下就好了。这样我们就完成了一次汉诺塔的求解过程。在这个过程中呢我们观察到先创建的帧最后才销毁后创建的帧最先被销毁这就是先入后出的规律也是程序执行时的活跃记录要被叫做栈的原因。那么在这里呢我还想让你做一个小练习。我想让你试着用我们上面分析栈变化的方法来分析使用深度优先算法打印全排列的程序这会让你更加深入地理解栈的运行规律同时掌握深度优先算法的递归写法。res [] def make(n, level): if n level: print(res) return for i in range(1, n1): if i not in res: res.append(i) make(n, level1) res.pop() make(3, 0)从指令的角度理解栈好了前面递归的例子是从人的直观思维的角度去理解栈但是在 CPU 层面机器指令又是怎样去理解栈的呢我们还是通过一个例子来考察一下int fac(int n) { return n 1 ? 1 : n * fac(n-1); }这是一个使用递归的写法求阶乘的例子源码是比较简单的我们可以使用 gcc 对其进行编译然后使用 objdump 对其反编译观察它编译后的机器码。# gcc -o fac fac.c # objdump -d fac然后你可以得到以下输出40052d: 55 push %rbp 40052e: 48 89 e5 mov %rsp,%rbp 400531: 48 83 ec 10 sub $0x10,%rsp 400535: 89 7d fc mov %edi,-0x4(%rbp) 400538: 83 7d fc 01 cmpl $0x1,-0x4(%rbp) 40053c: 74 13 je 400551 fac0x24 40053e: 8b 45 fc mov -0x4(%rbp),%eax 400541: 83 e8 01 sub $0x1,%eax 400544: 89 c7 mov %eax,%edi 400546: e8 e2 ff ff ff callq 40052d fac 40054b: 0f af 45 fc imul -0x4(%rbp),%eax 40054f: eb 05 jmp 400556 fac0x29 400551: b8 01 00 00 00 mov $0x1,%eax 400556: c9 leaveq 400557: c3 retq我们来分析一下这段汇编代码。第 1 行是将当前栈基址指针存到栈顶第 2 行是把栈指针保存到栈基址寄存器这两行的作用是把当前函数的栈帧创建在调用者的栈帧之下。保存调用者的栈基址是为了在 return 时可以恢复这个寄存器。第 3 行的作用呢是把栈向下增长 0x10这是为了给局部变量预留空间。从这里你可以看出来运行 fac 函数要是消耗栈空间的。试想一下如果我们不加 n1 的判断那么 fac 函数将无法正常返回会出现一直递归调用回不来的情况这样栈上就会出现很多 fac 的帧栈会造成栈空间耗尽出现 StackOverflow。这里的原理是操作系统会在栈空间的尾部设置一个禁止读写的页一旦栈增长到尾部操作系统就可以通过中断探知程序在访问栈末端。第 4 行是把变量 n 存到栈上。其中变量 n 一开始是存储在寄存器 edi 中的存储的目标地址是栈基址加上 0x4 的位置也就是这个函数栈帧的第一个局部变量的位置。变量 n 在寄存器 edi 中是 X86 的 ABI 决定的第一个整型参数一定要使用 edi 来传递。第 5 行将变量 n 与常量 0x1 进行比较。在第 6 行如果比较的结果是相等的那么程序就会跳转到 0x400551 位置继续执行。我们看到在这块代码里0x400551 是第 13 行它把 0x1 送到寄存器 eax 中然后返回就是说当 n1 时返回值为 1。如果第 5 行的比较结果是不相等的又会怎么办呢那第 6 行就不会跳转而是继续执行第 7 行。7、8、9 这三行的作用就是把 n-1 送到 edi 寄存器中也就是说以 n-1 为参数调用 fac 函数。这个时候调用的返回值在 eax 中第 11 行会把返回值与变量 n 相乘结果仍然存储在 eax 中。然后程序就可以跳转到 0x400556 处结束这次调用。理解了 fac 函数的汇编指令以后我们再重点讨论 callq 指令。执行 callq 指令时CPU 会把 rip 寄存器中的内容也就是 call 的下一条指令的地址放到栈上在这个例子中就是 0x40054b然后跳转到目标函数处执行。当目标函数执行完成后会执行 ret 指令这个指令会从栈上找到刚才存的那条指令然后继续恢复执行。栈空间中的 rbp、rsp以及返回时所用的指令都是非常敏感的数据一旦被破坏就会造成不可估量的损失。不过你在重现这个例子一定要注意我们使用不同的优化等级产生的汇编代码也是不同的。比如如果你用以下命令进行编译得到的二进制文件中将不再使用 rbp 寄存器。# gcc -O1 -o fac fac.c至于这个结果我这里就不再展示了我想让你自己动手试一下然后在留言区和我们分享。到这里我们已经从人的大脑的理解角度和机器指令的角度让你加深了对栈和栈帧的理解。现在我们就从理论转向实操举一个通过缓冲区溢出来破坏栈的例子。通过这个例子你就知道在平时的工作中应该如何避免写出被黑客攻击的不安全代码。栈溢出下面这个测试是我精心构造的例子。因为是演示用的所以我就把各种无关的代码去掉了只保留了关键路径上的代码。你先看一下代码#include stdio.h #include stdlib.h #define BUFFER_LEN 24 void bad() { printf(Haha, I am hacked.\n); exit(1); } void copy(char* dst, char* src, int n) { int i; for (i 0; i n; i) { dst[i] src[i]; } } void test(char* t, int n) { char s[16]; copy(s, t, n); } int main() { char t[BUFFER_LEN] { w, o, l, d, a, b, a, b, a, b, a, b, a, b, a, b, }; int n BUFFER_LEN - 8; int i 0; for (; i 8; i) { t[ni] (char)((((long)(bad)) (i*8)) 0xff); } test(t, BUFFER_LEN); printf(hello\n); }你可以用 gcc 编译器来编译上面这个程序gcc -O1 -o bad bad.c -g -fno-stack-protector执行它你可以看到虽然在 main 函数里我们并没有调用 bad 函数但它却执行了。最后运行结果是“Haha, I am hacked”。我们首先来分析一下这个程序为什么会有这样的运行结果。当我们在调用 test 函数的时候会把返回地址也就是 rip 寄存器中的值放到栈上然后就进入了 test 的栈帧CPU 接着就开始执行 test 函数了。test 函数在执行时会先在自己的栈帧里创建数组 s数组 s 的长度是 16。此时栈上的布局是这样的通过计算我们可以知道返回地址是变量 s 的地址 16 的地方这就是我们要攻击的目标。我们只要在这个地方把原来的地址替换为函数 bad 的入口地址第 26 至 34 行所做的事情就可以改变程序的执行顺序实现了一次缓冲区溢出。简单地说数组 s 的长度是 16理论上我们只能修改以 s 的地址开始、长度为 16 的数据。但是我们现在通过 copy 函数操作了大于 16 的数据从而破坏了栈上的关键数据。也就是说我们针对函数调用的返回地址发起了一次攻击。所以test 函数的实现是不安全的。其实这种缓冲区溢出就是指通过一定的手段来达成修改不属于本函数栈帧的变量的目的而这种手段多是通过往字符串变量或者数组中写入错误的值而造成的。有两种常见的手段可以对这一类攻击进行防御。第一对入参进行检查尽量使用 strncpy 来代替 strcpy。因为 strcpy 不对参数长度做限制而 strncpy 则会做检查。比如上述例子中如果我们对参数 n 做检查要求它的值必须大于 0 且小于缓冲区长度就可以阻击缓冲区溢出攻击了。第二可以使用 gcc 自带的栈保护机制这就是 -fstack-protector 选项。你查 gcc 手册在 Linux 系统使用“man gcc”就能查到可以看到它的一些相关信息。当 -fstack-protector 启用时当其检测到缓冲区溢出时 (例如缓冲区溢出攻击时会立即终止正在执行的程序并提示其检测到缓冲区存在的溢出的问题。这种机制是通过在函数中的易被受到攻击的目标上下文添加保护变量来完成的。这些函数包括使用了 alloca 函数以及缓冲区大小超过 8bytes 的函数。这些保护变量在进入函数的时候进行初始化当函数退出时进行检测如果某些变量检测失败那么会打印出错误提示信息并且终止当前的进程。从 4.8 版本开始gcc 中的这个选项是默认打开的。如果我们在编译时不加 -fno-stack-protectorgcc 就会给可执行程序增加栈保护的功能。这样的话运行结果就会出现 Segment Fault导致进程崩溃。不过你要知道在遇到攻击时自己崩溃相比起去执行攻击者的恶意代码影响可就小多了。这里我们为了演示的方便使用 -fno-stack-protector 关闭了这个选项。不过在日常开发中这个选项虽然使得栈的安全大大加强了但它也有巨大的性能损耗。在一个实际的线上例子中关闭这个选项可以提升 8% 至 10% 的性能。当然这个选项也不是万能的攻击者依然能通过精心构造数据来达成它的目标。所以在写代码的时候你还是应该对缓冲区安全多加注意。总结这节课我们一起学习了栈帧的作用并通过汉诺塔程序的求解过程来分析了栈帧的创建和销毁的过程以此揭示了函数和栈帧的关系。栈帧就是函数的活动记录当函数被调用时栈帧创建当函数调用结束后栈帧消失。在程序的执行过程中尤其是递归程序的执行过程中你可以清楚地观察到栈帧的创建销毁满足后入先出的规律。这也是人们把管理函数的活跃记录的区域称为栈的原因。除了用人的直观思维来理解栈帧之外我还带你看了在汇编代码级别栈帧是怎么真实地被创建和销毁的或者说栈是怎么增长和收缩的。这会进一步加深你对栈的理解。这节课的最后我也通过一个缓冲区溢出的例子说明了在栈空间内使用缓冲区的时候你必须要十分小心要避免恶意的输入对缓冲区进行越界读写破坏栈的结构从而导致关键数据被修改。我们演示了一个破坏了调用者返回地址的例子以此来说明当返回地址被破坏以后攻击者可以让程序的控制流转向我们不希望的地方。很多人以为安全和攻击是做安全的同事才应该关心的问题这个想法是不对的。要想提高软件的整体水平每一个程序员都应该写出健壮而安全的代码。只有每一块砖都足够坚固我们才有可能建成一个安全可靠的建筑物。
引言之前我们讲到栈被操作系统安排在进程的高地址处它是向下增长的。但这只是对栈相关知识的“浅尝辄止”。那我们今天这节课就会跟着前面的脉络让你可以更深刻地理解栈的运行原理。栈是每一个程序员都很熟悉的话题但你敢说你真的完全了解它吗我相信你在工作中肯定遇到过栈溢出StackOverflow的错误比如在写递归函数的时候当漏掉退出条件或者退出条件不小心写错了就会出现栈溢出错误。我们也经常听说缓冲区溢出带来的严重的安全问题这在日常的工作中都是要避免的。所以今天这节课我们继续深入探讨一下栈这个话题我会带你基于“符合人的直观思维”也就是函数的层面和 CPU 的机器指令层面多角度来理解栈相关的概念。这样你以后遇到与栈相关的问题的时候才知道如何着手进行排查。最后我们还会通过一个缓冲区溢出攻击栈的案例看看我们在日常工作中如何提升代码的健壮度和安全性。函数与栈帧当我们在调用一个函数的时候CPU 会在栈空间这当然是线性空间的一部分里开辟一小块区域这个函数的局部变量都在这一小块区域里存活。当函数调用结束的时候这一小块区域里的局部变量就会被回收。这一小块区域很像一个框子所以大家就命名它为 stack frame。frame 本意是框子的意思在翻译的时候被译为帧现在它的中文名字就是栈帧了。所以我们可以说栈帧本质上是一个函数的活动记录。当某个函数正在执行时它的活动记录就会存在当函数执行结束时活动记录也被销毁。不过你要注意的是在一个函数执行的时候它可以调用其他函数这个时候它的栈帧还是存在的。例如A 函数调用 B 函数此时 A 的栈帧不会被销毁而是会在 A 栈帧的下方再去创建 B 函数的栈帧。只有当 B 函数执行完了B 的栈帧也被销毁了CPU 才会回到 A 的栈帧里继续执行。我们举个例子说明一下就很好理解了。你可以看一下这个代码#include stdio.h void swap(int a, int b) { int t a; a b; b t; } void main() { int a 2; int b 3; swap(a, b); printf(a is %d, b is %d\n, a, b); }你可以看到在 swap 函数中a 和 b 的值做了一次交换但是在 main 函数里打印 a 和 b 的值a 还是 2b 还是 3。这是为什么呢从栈帧的角度这个问题就非常容易理解在 main 函数执行的时候main 的栈帧里存在变量 a 和 b。当 main 在调用 swap 方法的时候会在 main 的帧下面新建 swap 的栈帧。swap 的帧里也有局部变量 a 和 b但是明显这个 a、b 与 main 函数里的 a、b 没有任何关系不管对 swap 的帧里的 a/b 变量做任何操作都不会影响 main 函数的栈帧。接下来我们再通过一个递归的例子来加深对栈的理解。由于递归执行的过程会出现函数自己调用自己的情况也就是说一个函数会对应多个同时活跃的记录即栈帧。所以理解了递归函数的执行过程我们就能更加深刻地理解栈帧与函数的关系。当我们在谈递归时我们在谈什么我们先看一下最经典的递归问题汉诺塔。汉诺塔问题是这样描述的有三根柱子记为 A、B、C其中 A 柱子上有 n 个盘子从上到下的编号依次为 1 到 n且上面的盘子一定比下面的盘子小。要求一次只能移动一只盘子且大的盘子不能压在小的盘子上那么将所有盘子从 A 移到 C 总共需要多少步这道题的详细分析过程是一种递归推导的过程不是我们这节课的重点如果你对解法感兴趣的话可以自己查找相关资料。我们这里重点来讲解递归程序执行的过程中栈是怎么样变化的这样可以帮助我们理解栈的基本工作原理。你先看一下汉诺塔问题的求解程序#include stdio.h void move(char src, char dst, int n) { printf(move plate %d form %c to %c\n, n, src, dst); } void hanoi(char src, char dst, char aux, int n) { if (n 1) { move(src, dst, 1); return; } hanoi(src, aux, dst, n-1); move(src, dst, n); hanoi(aux, dst, src, n-1); } int main() { hanoi(A, C, B, 5); }这段代码可以打印出借由 B 柱子将 5 个盘子从 A 搬移到 C 的所有步骤。这个的核心是 hanoi 函数在深入分析代码的执行过程之前我们可以先从符合直观思维的角度尝试理解 hanoi 函数。hanoi 函数有四个参数。第一个 src 代表要搬的起始柱子开始时是 A第二个代表目标柱子开始时是 C第三个代表可以借用的中间的那个柱子开始时是 B第四个参数代表一共要搬的盘子总数开始时是 5。代码的第 13 行的意义是如果要从 A 搬 5 个盘子到 C可以先将 4 个盘子搬到 B 上然后第 14 行代表将第 5 个盘子从 A 搬到 C第 15 行代表把 B 上面的 4 个盘子搬到 C 上去。第 8 行的判断是说当只搬一个盘子的时候就可以直接调用 move 方法。以上就是递归程序的设计思路。下面我们再具体分析这个代码的执行过程。为了简便起见我们选择 n3 进行分析。可以看到当程序在执行 hanoi(A, C, B, 3) 时CPU 会为其创建一个栈帧这一帧里记录着变量 src、dst、aux 和 n。此时 n 为 3所以代码可以执行到第 13 行然后就会调用执行 hanoi(A, B, C, 2)。这代表着将 2 个盘子从 A 搬到 B同样 CPU 也会为这次调用创建一个栈帧当这一次调用执行到第 13 行时会再调用执行 hanoi(A, C, B, 1)代表把一个盘子从 A 搬到 C。不过由于这一次调用 n 为 1所以会直接调用 move 函数打印第一个步骤“把盘子 1 从 A 搬到 C”。接下来程序就会回到 hanoi(A, B, C, 2) 的栈帧继续执行第 14 行打印第二个步骤”把盘子 2 从 A 搬到 B”。然后再执行第 15 行也就是执行 hanoi(C, B, A, 1)。这一步的栈帧变化你可以看下面这张图。我们看到在调用 hanoi(C, B, A, 1) 的时候由于 n 等于 1所以就会打印第三个步骤“把盘子 1 从 C 搬到 B”此时 hanoi(C, B, A, 1) 就执行完了。那么接下来程序就退回到 hanoi(A, B, C, 2) 的第 15 行的下一行继续执行也就是函数的结束这就意味着 hanoi(A, B, C, 2) 也执行完了。这个时候程序就会回退到最高的一层 hanoi(A, C, B, 3) 的第 14 行继续执行。这一次就打印了第四个步骤“把盘子 3 从 A 搬到 C”此时的栈帧如上图 (b) 所示。然后程序会执行第 15 行再次进入递归调用创建 hanoi(B, C, A, 2) 的栈帧。当它执行到第 13 行时就会再创建 hanoi(B, A, C, 1) 的栈帧此时栈的结构如上图c所示。由于 n 等于 1这一次调用就会打印第五个步骤“把盘子 1 从 B 搬到 A”。再接着就开始退栈了回到 hanoi(B, C, A, 2) 的栈帧继续执行第 14 行打印第六个步骤“把盘子 2 从 B 搬到 C”。然后执行第 15 行也就是 hanoi(A, C, B, 1)此时 n 等于 1直接打印第七个步骤“把盘子 1 从 A 搬到 C”。接下来就执行退栈这一次每一个栈帧都执行到了最后一行所以会一直退到 main 函数的栈帧中去。退栈的过程比较简单你自己思考一下就好了。这样我们就完成了一次汉诺塔的求解过程。在这个过程中呢我们观察到先创建的帧最后才销毁后创建的帧最先被销毁这就是先入后出的规律也是程序执行时的活跃记录要被叫做栈的原因。那么在这里呢我还想让你做一个小练习。我想让你试着用我们上面分析栈变化的方法来分析使用深度优先算法打印全排列的程序这会让你更加深入地理解栈的运行规律同时掌握深度优先算法的递归写法。res [] def make(n, level): if n level: print(res) return for i in range(1, n1): if i not in res: res.append(i) make(n, level1) res.pop() make(3, 0)从指令的角度理解栈好了前面递归的例子是从人的直观思维的角度去理解栈但是在 CPU 层面机器指令又是怎样去理解栈的呢我们还是通过一个例子来考察一下int fac(int n) { return n 1 ? 1 : n * fac(n-1); }这是一个使用递归的写法求阶乘的例子源码是比较简单的我们可以使用 gcc 对其进行编译然后使用 objdump 对其反编译观察它编译后的机器码。# gcc -o fac fac.c # objdump -d fac然后你可以得到以下输出40052d: 55 push %rbp 40052e: 48 89 e5 mov %rsp,%rbp 400531: 48 83 ec 10 sub $0x10,%rsp 400535: 89 7d fc mov %edi,-0x4(%rbp) 400538: 83 7d fc 01 cmpl $0x1,-0x4(%rbp) 40053c: 74 13 je 400551 fac0x24 40053e: 8b 45 fc mov -0x4(%rbp),%eax 400541: 83 e8 01 sub $0x1,%eax 400544: 89 c7 mov %eax,%edi 400546: e8 e2 ff ff ff callq 40052d fac 40054b: 0f af 45 fc imul -0x4(%rbp),%eax 40054f: eb 05 jmp 400556 fac0x29 400551: b8 01 00 00 00 mov $0x1,%eax 400556: c9 leaveq 400557: c3 retq我们来分析一下这段汇编代码。第 1 行是将当前栈基址指针存到栈顶第 2 行是把栈指针保存到栈基址寄存器这两行的作用是把当前函数的栈帧创建在调用者的栈帧之下。保存调用者的栈基址是为了在 return 时可以恢复这个寄存器。第 3 行的作用呢是把栈向下增长 0x10这是为了给局部变量预留空间。从这里你可以看出来运行 fac 函数要是消耗栈空间的。试想一下如果我们不加 n1 的判断那么 fac 函数将无法正常返回会出现一直递归调用回不来的情况这样栈上就会出现很多 fac 的帧栈会造成栈空间耗尽出现 StackOverflow。这里的原理是操作系统会在栈空间的尾部设置一个禁止读写的页一旦栈增长到尾部操作系统就可以通过中断探知程序在访问栈末端。第 4 行是把变量 n 存到栈上。其中变量 n 一开始是存储在寄存器 edi 中的存储的目标地址是栈基址加上 0x4 的位置也就是这个函数栈帧的第一个局部变量的位置。变量 n 在寄存器 edi 中是 X86 的 ABI 决定的第一个整型参数一定要使用 edi 来传递。第 5 行将变量 n 与常量 0x1 进行比较。在第 6 行如果比较的结果是相等的那么程序就会跳转到 0x400551 位置继续执行。我们看到在这块代码里0x400551 是第 13 行它把 0x1 送到寄存器 eax 中然后返回就是说当 n1 时返回值为 1。如果第 5 行的比较结果是不相等的又会怎么办呢那第 6 行就不会跳转而是继续执行第 7 行。7、8、9 这三行的作用就是把 n-1 送到 edi 寄存器中也就是说以 n-1 为参数调用 fac 函数。这个时候调用的返回值在 eax 中第 11 行会把返回值与变量 n 相乘结果仍然存储在 eax 中。然后程序就可以跳转到 0x400556 处结束这次调用。理解了 fac 函数的汇编指令以后我们再重点讨论 callq 指令。执行 callq 指令时CPU 会把 rip 寄存器中的内容也就是 call 的下一条指令的地址放到栈上在这个例子中就是 0x40054b然后跳转到目标函数处执行。当目标函数执行完成后会执行 ret 指令这个指令会从栈上找到刚才存的那条指令然后继续恢复执行。栈空间中的 rbp、rsp以及返回时所用的指令都是非常敏感的数据一旦被破坏就会造成不可估量的损失。不过你在重现这个例子一定要注意我们使用不同的优化等级产生的汇编代码也是不同的。比如如果你用以下命令进行编译得到的二进制文件中将不再使用 rbp 寄存器。# gcc -O1 -o fac fac.c至于这个结果我这里就不再展示了我想让你自己动手试一下然后在留言区和我们分享。到这里我们已经从人的大脑的理解角度和机器指令的角度让你加深了对栈和栈帧的理解。现在我们就从理论转向实操举一个通过缓冲区溢出来破坏栈的例子。通过这个例子你就知道在平时的工作中应该如何避免写出被黑客攻击的不安全代码。栈溢出下面这个测试是我精心构造的例子。因为是演示用的所以我就把各种无关的代码去掉了只保留了关键路径上的代码。你先看一下代码#include stdio.h #include stdlib.h #define BUFFER_LEN 24 void bad() { printf(Haha, I am hacked.\n); exit(1); } void copy(char* dst, char* src, int n) { int i; for (i 0; i n; i) { dst[i] src[i]; } } void test(char* t, int n) { char s[16]; copy(s, t, n); } int main() { char t[BUFFER_LEN] { w, o, l, d, a, b, a, b, a, b, a, b, a, b, a, b, }; int n BUFFER_LEN - 8; int i 0; for (; i 8; i) { t[ni] (char)((((long)(bad)) (i*8)) 0xff); } test(t, BUFFER_LEN); printf(hello\n); }你可以用 gcc 编译器来编译上面这个程序gcc -O1 -o bad bad.c -g -fno-stack-protector执行它你可以看到虽然在 main 函数里我们并没有调用 bad 函数但它却执行了。最后运行结果是“Haha, I am hacked”。我们首先来分析一下这个程序为什么会有这样的运行结果。当我们在调用 test 函数的时候会把返回地址也就是 rip 寄存器中的值放到栈上然后就进入了 test 的栈帧CPU 接着就开始执行 test 函数了。test 函数在执行时会先在自己的栈帧里创建数组 s数组 s 的长度是 16。此时栈上的布局是这样的通过计算我们可以知道返回地址是变量 s 的地址 16 的地方这就是我们要攻击的目标。我们只要在这个地方把原来的地址替换为函数 bad 的入口地址第 26 至 34 行所做的事情就可以改变程序的执行顺序实现了一次缓冲区溢出。简单地说数组 s 的长度是 16理论上我们只能修改以 s 的地址开始、长度为 16 的数据。但是我们现在通过 copy 函数操作了大于 16 的数据从而破坏了栈上的关键数据。也就是说我们针对函数调用的返回地址发起了一次攻击。所以test 函数的实现是不安全的。其实这种缓冲区溢出就是指通过一定的手段来达成修改不属于本函数栈帧的变量的目的而这种手段多是通过往字符串变量或者数组中写入错误的值而造成的。有两种常见的手段可以对这一类攻击进行防御。第一对入参进行检查尽量使用 strncpy 来代替 strcpy。因为 strcpy 不对参数长度做限制而 strncpy 则会做检查。比如上述例子中如果我们对参数 n 做检查要求它的值必须大于 0 且小于缓冲区长度就可以阻击缓冲区溢出攻击了。第二可以使用 gcc 自带的栈保护机制这就是 -fstack-protector 选项。你查 gcc 手册在 Linux 系统使用“man gcc”就能查到可以看到它的一些相关信息。当 -fstack-protector 启用时当其检测到缓冲区溢出时 (例如缓冲区溢出攻击时会立即终止正在执行的程序并提示其检测到缓冲区存在的溢出的问题。这种机制是通过在函数中的易被受到攻击的目标上下文添加保护变量来完成的。这些函数包括使用了 alloca 函数以及缓冲区大小超过 8bytes 的函数。这些保护变量在进入函数的时候进行初始化当函数退出时进行检测如果某些变量检测失败那么会打印出错误提示信息并且终止当前的进程。从 4.8 版本开始gcc 中的这个选项是默认打开的。如果我们在编译时不加 -fno-stack-protectorgcc 就会给可执行程序增加栈保护的功能。这样的话运行结果就会出现 Segment Fault导致进程崩溃。不过你要知道在遇到攻击时自己崩溃相比起去执行攻击者的恶意代码影响可就小多了。这里我们为了演示的方便使用 -fno-stack-protector 关闭了这个选项。不过在日常开发中这个选项虽然使得栈的安全大大加强了但它也有巨大的性能损耗。在一个实际的线上例子中关闭这个选项可以提升 8% 至 10% 的性能。当然这个选项也不是万能的攻击者依然能通过精心构造数据来达成它的目标。所以在写代码的时候你还是应该对缓冲区安全多加注意。总结这节课我们一起学习了栈帧的作用并通过汉诺塔程序的求解过程来分析了栈帧的创建和销毁的过程以此揭示了函数和栈帧的关系。栈帧就是函数的活动记录当函数被调用时栈帧创建当函数调用结束后栈帧消失。在程序的执行过程中尤其是递归程序的执行过程中你可以清楚地观察到栈帧的创建销毁满足后入先出的规律。这也是人们把管理函数的活跃记录的区域称为栈的原因。除了用人的直观思维来理解栈帧之外我还带你看了在汇编代码级别栈帧是怎么真实地被创建和销毁的或者说栈是怎么增长和收缩的。这会进一步加深你对栈的理解。这节课的最后我也通过一个缓冲区溢出的例子说明了在栈空间内使用缓冲区的时候你必须要十分小心要避免恶意的输入对缓冲区进行越界读写破坏栈的结构从而导致关键数据被修改。我们演示了一个破坏了调用者返回地址的例子以此来说明当返回地址被破坏以后攻击者可以让程序的控制流转向我们不希望的地方。很多人以为安全和攻击是做安全的同事才应该关心的问题这个想法是不对的。要想提高软件的整体水平每一个程序员都应该写出健壮而安全的代码。只有每一块砖都足够坚固我们才有可能建成一个安全可靠的建筑物。
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
