递归是一种计算机编程技术，它是指某个程序，子程序，函数或算法不断调用自身一次或多次，直到满足某个条件。人们一直在争论递归应该怎么使用，以及是否应该使用它。递归是每个程序员必备的技能。然而，它的不正确使用可能会导致使程序流变复杂，以及使代码产生漏洞。这也使得某些编程标准明确地禁止它的使用，以及禁止其他复杂的流程结构，比如说 goto 。总而言之，递归代码难以理解，从而导致程序出错。在这篇文章中，我会介绍递归，以及如何在漏洞研究中利用它。此外，我还会分享一个我使用中级中间语言写的跨平台的Binary Ninja 插件，用于在汇编代码中定位递归位置。

递归可以分为两类，直接递归和间接递归。直接递归出现在程序调用自身的时候。直接递归的例子很多，比如数学算法，列表排序和二叉搜索树。直接递归的例子如下所示，这个例子返回某个整数的阶乘（一系列递减整数的乘积）。

间接递归是提程序调用另一个程序，并最终调用原始程序。我发现的间接递归最实际的使用是在目录遍历程序中， 在这样的程序里，程序在树中导航，另一个程序处理文件。如果这个文件是目录，就调用原始程序。另一个例子是，判断某个数是偶数还是奇数，如下所示。

##　栈溢出导致拒绝服务
递归的问题通常出现在没有合理的估计递归调用的次数时。当函数由 x86 处理器执行时，返回地址和函数参数被压入栈中。在递归调用中，栈以指数级增长。如果递归层数太深，就会在分配的栈大小超出时发生栈溢出。递归引发的栈溢出非常难以利用，通常会导致拒绝服务。这是因为，随着递归调用的进行，栈持续增长，使得栈溢出超出了栈顶。在栈上面（大多数时候）有一个防护页，用于预防栈破坏其他内存区域。当然也有技术能够跳过这个防护页，溢出到堆中。这一技术要求递归函数申请足够大的栈变量以及堆内存靠近防护页的另一端。关于防护页的更多相关资料请戳这里。

递归在漏洞利用中的另一个作用是攻击未初始化的栈变量。正如前面提到的，x86 调用约定中规定函数参数由调用者压入栈中。如果攻击者能够控制递归中函数参数的值，他们就能通过初始化未初始化的栈变量来控制栈。编译器假设当你申明一个变量时，你会初始化它（在使用之前）。
基于这个假设，编译器会在栈中为栈变量分配一个虚拟地址。在未初始化的栈变量中，编译器会在栈中为栈变量分配空间。因为函数调用的栈帧会有重叠（会被重用），一个未初始化的栈变量通常包含上次使用过后留下来的垃圾数据，直到它被初始化。为了证明这一过程是怎么发生的，我写了一个非常好的程序，我想我能凭此得到下一次的图灵奖。

上面这个程序接收一个命令行整数参数并调用 recursive_function，调用了 10 次。然后程序调用 func 函数，func 里会传递一个 j 作为变量给 take_int 函数并调用它。这一代码的漏洞存在于 func 函数中。变量 j 被申明之后，在传给 take_int 前没有初始化。让我们编译并运行这个程序，并在命令中把1337作为参数传给这个程序。

尽管 j 没有初始化，take_int 中的条件（检查 j 是否等于1337）明显为真，但是为什么呢？在 recursive_func 函数运行结束返回 main 后，栈中的情况像下图所示。在重复递归调用时，栈指针被不断修改成更低的内存地址，而 n（0x00000539）和返回地址一起被压入栈中。函数每递归一次，我们就有更大的可能用我们提供的值在 take_int 中访问到我们的未初始化的变量。在返回地址和函数参数之外，栈中也会有 recursive_func生成的其他的数据。这是在实际应用中攻击未初始化变量的困难之处。使用你的数据覆盖到未初始化变量的偏移地址非常困难，即使在没有其他指令清除它的值的情况下，你的变量想要被引用也非常困难。

递归调用之后的栈布局

在 take_int 被调用之前，栈已经被 0x00000539 污染了。在下面的图片中，在 0x00000644 位置，应该包含值 j 的操作数（栈偏移），被复制作为 take_int 的第一个参数。然而, [ebp-0xc] 并没有包含值 j，因为 j 没有被初始化。相反，它上面的值是 0x00000539，这是 recursive_func调用之后遗留下来的。

take_int 调用

下一张截图中描述的是 take_int 函数的代码。最重要的指令在 000005d1 上。这条指令就是 arg1(j) 被间接引用并与常量值 0x00000539 比较的指令。这一调用发生的在 recursive_func 调用之后。这两个比较的值是相等的。因此，这一程序没有进入 000005d8 处的分支，而是执行了这一反常的 print 输出。

take_int 没有引用未初始化栈变量 j
这一例程的执行结果可能根据你的 gcc 的版本以及编译方式的不同而产生不同的变化。我是用 6.3.0 20170516 版本的 gcc 编译的。如果你使用另一不同版本的 gcc 编译。这一结果可能会不同。你传递的参数除了可能会覆盖未初始化栈变量 j 之外，还可能会覆盖返回地址或是栈中的其他数据。这都取决于指令是怎么编译的。如果你运行这个例子一直没有成功，你可以在下面评论或是通过email截图给我，我会发送我的二进制文件给你。

作为我研究递归的部分成果，我使用 Binary Ninja 的API和中级中间语言开发了一个插件用于在汇编代码中定位递归的位置。这个插件可以识别直接递归和间接递归，并在递归函数和它们的调用指令处进行注释。它通常产生一个由 BN（Binary Ninja） 的 UI 渲染的 markdown 页面，在其中包含了递归代码的位置。它对 BN 支持的所有架构编译的二进制代码生效。这一插件是我写出来用于辅助静态分析 Binjago 插件集的一部分。插件注释过后的指令截图如下所示。这一插件可以在这里找到。

Binjago 递归代码注释

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！