dcLunatic's blog

递归攻击——入门1

C 递归攻击
字数统计: 1.3k阅读时长: 4 min
2018/10/04 Share

递归攻击——入门1

递归概要

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

1
2
3
4
5
6
7
8
9
uint32_t factorial(uint32_t number)
{
    if (number <= 1)
    {
        return 1;
    }
 
    return number * factorial(number -1);
}

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

1
2
3
4
5
6
7
8
9
int is_odd(int number)
{
    return number == 0 ? 0 : is_even(abs(number) - 1);
}
 
int is_even(int number)
{
    return number == 0 ? 1 : is_odd(abs(number) - 1);
}

栈溢出导致拒绝服务

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

使用递归攻击未初始化的栈变量

递归在漏洞利用中的另一个作用是攻击未初始化的栈变量。
正如前面提到的，x86 调用约定中规定函数参数由调用者压入栈中。
如果攻击者能够控制递归中函数参数的值，他们就能通过初始化未初始化的栈变量来控制栈。
编译器假设当你申明一个变量时，你会初始化它（在使用之前）。

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
/**
 *使用递归攻击未初始化的栈变量--污染栈
 *编译器会在栈中会为栈变量分配一个虚拟地址，即使是未初始化的栈变量。
 *而由于函数调用的栈帧会重叠（因为重用），所以一个未初始化的栈变量通常会包含上次使用过的遗留数据，直到它被初始化。
 *而基于这个，我们就可以来尝试写一段程序了。
 *
 */
void takeInt(int integer)
{
    if (integer == 1337)
        printf("How could this be? Integer was never initialized!\n");
}
 
void recursiveFunc(int n)
{
    static int i = 0;
    i++;
    if (i == 10)
        return;
    else
        recursiveFunc(n);
}
 
void function()
{
    int j;
    takeInt(j);
}
 
int main(int argc, char **argv)
{
    int n = atoi(argv[1]);
    recursiveFunc(n);
    function();
    return 0;
}

/**************************************************************************************************
* We can use it in console as follow:
*  $ gcc dirtyStack.c -o dirtyStack
*  $ ./dirtyStack 1337
* And the result is:
*  How could this be? Integer was never initialized!
* 
* 很明显，integer并没有给初始化，但是为什么条件判断会是真呢？
* 其实在递归调用的时候，栈指针会被不断修改成更低的内存地址，
* 而n和返回地址一起给压入栈中。而这样子，每当函数调用一次，我们便会有更大的机率访问到我们的未初始化变量。
* 但是，在返回地址和函数参数之外，栈中也会有其他的数据生成，这就使得在攻击未初始化变量增加了难度。
* 而且，要使用你自己的数据覆盖到未初始化的变量的偏移地址也是十分困难的，即使在没有其他指令清楚它的值的时候，
* 你的变量要给引用也很困难。
*
* 注：编译运行结果与gcc版本也有一定的关系，有些版本的gcc指令生成的时候会有所不同。
* 可能高版本的gcc编译生成的指令有其他的优化，使得运行结果不一样。
* 后面我会附上二进制文件。
* 有兴趣的也可以自己使用调试工具如OD等动态跟踪一下整个运行的过程，
* 也可以利用这个自行解决问题。
**************************************************************************************************/

总结

复杂的递归程序通常难以理解，因此会导致一些程序错误。
无限的递归调用可以用于破坏栈，在某些条件下，递归能被用于影响栈的布局以攻击未初始化的变量。
如果你对例子中的递归漏洞感兴趣，我推荐这个项目。

Project Zero: Exploiting Recursion in the Linux Kernel

原文作者：dcLunatic

原文链接：http://dclunatic.github.io/%E9%80%92%E5%BD%92%E6%94%BB%E5%87%BB%E2%80%94%E2%80%94%E5%85%A5%E9%97%A81.html

发表日期：October 4th 2018, 9:04:42 pm

更新日期：July 11th 2021, 9:13:49 pm

版权声明：转载的时候,记得注明来处

CATALOG
  1. 1. 递归攻击——入门1
    1. 1.1. 递归概要
      1. 1.1.1. 栈溢出导致拒绝服务
      2. 1.1.2. 使用递归攻击未初始化的栈变量
      3. 1.1.3. 例子
      4. 1.1.4. 总结
Total : 39
2021
2018
java IO TIO 性能分析 线程通信 class文件 克隆 函数式接口 字节与字符的区别 多线程 序列化 kali virtualbox Java 网络编程 Lock 锁 Linux 进程管理 反射 类加载机制 steam linux command calculate 拷贝烧录 文件目录详解 内网穿透 ngrok 同步锁 vim 编码 clipboard makefile 编译器 file volatile arch 独立显卡 C 递归攻击 python