开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 系统运维 -> 堆溢出基础 -> 正文阅读

[系统运维]堆溢出基础

堆基础

前言

堆栈溢出（pwn一般简称栈溢出）和堆溢出，只相差一个字，但内容却完全不同。

堆栈（pwn中的栈），在可执行程序的text区，是从高地址向低地址扩展，是存放局部变量的地方，在编译时由编译器静态分配。

堆，是在可执行程序的heap区，从低地址向高地址扩展，是存放由malloc等函数动态分配数据的地方。其结构关系在内存中的映射如图4－1。当然，还有其他的data区等。

一、“堆”是什么？

在程序运行过程中，堆可以提供动态分配的内存，允许程序申请未知的内存。堆其实就是程序虚拟地址空间的一块连续线性区域，它由低地址往高地址增长。我们称管理堆的那部分程序为：堆管理器

堆管理器位于程序与内核之间，主要做：
1、响应用户申请内存的请求
2、管理用户所释放的内存

目前 Linux 标准发行版中使用的堆分配器是 glibc 的堆分配器：ptmalloc2，主要通过 mallo/free 来分配和释放内存块

不同的线程维护不同的堆称为：per thread arena

主线程创建的堆称为：main arena

arena 指的是堆内存区域本身，并不是结构；主线程的 main arena 通过 sbrk 创建；其他线程的 arena 通过 mmap 创建

malloc_state 管理 arena 的核心结构，包含堆的状态信息、bins 链表等；main arena 对应的 malloc state 结构存储在 glibc 全局变量中；其他线程 arena 对应的 malloc_state 存储在 arena 本身中

bins 用来管理空闲内存块，通常用链表的结构来进行组织

chunks 内存块结构

二、堆和栈的区别

堆不同于栈，堆是动态分配的(由操作系统内核或者堆管理器)，只有在程序中需要时才会分配。在 CTF 的 pwn 程序中，栈是程序加载进内存后就会出现，而堆是由 malloc、alloc、realloc 函数分配内存后才会出现。

三、堆实现步骤

1.分配过程

ptmalloc在开始时，若请求的空间小于mmap分配阈值（mmap threshold，默认值为128KB）时，主分配区会调用sbrk()增加一块大小为 (128 KB + chunk-size) align 4KB的空间作为heap，若大于mmap分配阈值，则ptmalloc直接使用mmap()映射一块大小为chunk的内存作为heap。非主分配区会调用mmap映射一块大小为HEAP-MAX-SIZE（32位系统上默认为1MB，64位系统上默认为64MB）的空间作为sub-heap。当用户请求内存分配时，首先会在这个区域找一块合适的chunk给用户。当用户释放heap中的chunk时，ptmalloc又会使用fast bins和bins来组织空闲chunk。
若brk!=brk-start，若用户申请内存，先判断所需分配chunk的大小是否满足chunk-size<=max-fast（max-fast默认为64B），如果是的话则转到下一步。
首先尝试在fast bins中取一个所需大小的chunk分配给用户。如果可以找到，则分配结束。否则转到下一步。
判断所需大小是否在small bins中，即判断chunk-size < 512B是否成立。如果chunk大小处在small bins中，则转下一步，否则转6步
根据所需分配的chunk的大小，找到具体所在的某个small bin，从该bin的尾部摘取一个恰好满足大小的chunk。若成功，则分配结束，否则，转到下一步。
到了这一步，说明需要分配的内存较大。ptmalloc首先遍历fast bins中的chunk，并将相邻的chunk进行合并，并链接到unsorted bin中，然后遍历unsorted bin中的chunk，如果unsorted bin只有一个chunk，并且这个chunk在上次分配过程中被使用过，并且所需分配的chunk大小属于small bins，并且chunk的大小大于等于需要分配的大小，这种情况下就直接将该chunk进行切割，分配结束，否则将根据chunk的空间大小将其放入small bins或是large bins中，遍历完成后，转入下一步
到了这一步，说明需要分配的内存较大。或者small bins和unsorted bins中都找不到合适的chunk，并且fast bins和unsorted bins中所有的chunk都清除干净了。从large bins中按照“smallest-first，best-fit”原则，找一个合适的chunk，从中划分一块所需大小的chunk，并将剩下的部分链接回到bins中。若操作成功，则分配结束，否则转到下一步。
如果搜索fast bins和bins都没有找到合适的chunk，那么就需要操作top chunk来进行分配了。判断top chunk大小是否满足所需chunk的大小，如果是，则从top chunk中分出一块来。否则转到下一步。
到了这一步，说明top chunk也不能满足分配要求，所以，于是就有了两个选择: 如果是主分配区，调用sbrk()，增加top chunk大小；如果是非主分配区，调用mmap来分配一个新的sub-heap，增加top chunk大小；或者使用mmap()来直接分配。在这里，需要依靠chunk的大小来决定到底使用哪种方法。判断所需分配的chunk大小是否大于等于 mmap分配阈值，如果是的话，则转下一步，调用mmap分配，否则跳到第11步，增加top chunk 的大小。
使用mmap系统调用为程序的内存空间映射一块chunk_size align 4kB大小的空间。然后将内存指针返回给用户。
判断是否为第一次调用malloc，若是主分配区，则需要进行一次初始化工作，分配一块大小为(chunk_size + 128KB) align 4KB大小的空间作为初始的heap。若已经初始化过了，主分配区则调用sbrk()增加heap空间，非主分配区则在top chunk中切割出一个chunk，使之满足分配需求，并将内存指针返回给用户。

2.释放过程

判断传入的指针是否为0，如果为0，则什么都不做，直接return。否则转下一步。
判断所需释放的chunk是否为mmaped chunk，如果是，则调用munmap()释放mmaped chunk，解除内存空间映射，该该空间不再有效，访问该区域会报错。如果开启了mmap分配阈值的动态调整机制，并且当前回收的chunk大小大于mmap分配阈值，将mmap分配阈值设置为该chunk的大小，将mmap收缩阈值设定为mmap分配阈值的2倍（？？没看懂为什么），释放完成，否则跳到下一步。
判断chunk的大小和所处的位置，若chunk_size <= max_fast，并且chunk并不位于heap的顶部，也就是说并不与top chunk相邻，则转到下一步，否则跳到第5步。（因为与top chunk相邻的小chunk也和 top chunk进行合并，所以这里不仅需要判断大小，还需要判断相邻情况）
将chunk放到fast bins中，chunk放入到fast bins中时，并不修改该chunk使用状态位P。也不与相邻的chunk进行合并。只是放进去，如此而已。这一步做完之后释放便结束了，程序从free()函数中返回。
判断前一个chunk是否处在使用中，如果前一个块也是空闲块，则合并。并转下一步。
判断当前释放chunk的下一个块是否为top chunk，如果是，则转第8步，否则转下一步。
判断下一个chunk是否处在使用中，如果下一个chunk也是空闲的，则合并，并将合并后的chunk放到unsorted bin中。注意，这里在合并的过程中，要更新chunk的大小，以反映合并后的chunk的大小。并转到第9步。
如果执行到这一步，说明释放了一个与top chunk相邻的chunk。则无论它有多大，都将它与top chunk合并，并更新top chunk的大小等信息。转下一步。
判断合并后的chunk 的大小是否大于FASTBIN-CONSOLIDATION-THRESHOLD（默认64KB），如果是的话，则会触发进行fast bins的合并操作，fast bins中的chunk将被遍历，并与相邻的空闲chunk进行合并，合并后的chunk会被放到unsorted bin中。fast bins将变为空，操作完成之后转下一步。
判断top chunk的大小是否大于mmap**收缩阈值（默认为128KB），如果是的话，对于主分配区，则会试图归还top chunk中的一部分给操作系统。
判断top chunk的大小是否大于mmap收缩阈值（默认为128KB），如果是的话，对于主分配区，则会试图归还top chunk中的一部分给操作系统。但是最先分配的128KB空间是不会归还的，ptmalloc 会一直管理这部分内存，用于响应用户的分配请求；如果为非主分配区，会进行sub-heap收缩，将top chunk的一部分返回给操作系统，如果top chunk为整个sub-heap，会把整个sub-heap还回给操作系统。做完这一步之后，释放结束，从 free() 函数退出。可以看出，收缩堆的条件是当前free的chunk大小加上前后能合并chunk的大小大于64k，并且要top chunk的大小要达到mmap收缩阈值，才有可能收缩堆。，ptmalloc 会一直管理这部分内存，用于响应用户的分配请求；如果为非主分配区，会进行sub-heap收缩，将top chunk的一部分返回给操作系统，如果top chunk为整个sub-heap，会把整个sub-heap还回给操作系统。**做完这一步之后，释放结束，从 free() 函数退出。可以看出，收缩堆的条件是当前free的chunk大小加上前后能合并chunk的大小大于64k，并且要top chunk的大小要达到mmap收缩阈值，才有可能收缩堆。

四、glibc

malloc函数

malloc (size_t n)

返回一个指针，指向新分配的至少为n字节的块，或为空

如果没有可用空间。此外，在失败时，errno为

在ANSI C系统上设置为ENOMEM。

如果n为零，malloc返回最小大小的块。(最低

大小在大多数32位系统上是16字节，在64位系统上是24或32字节

系统)。

在大多数系统中，size_t是unsigned类型，因此调用

使用负面参数会被解释为大量的请求

它经常会失败。n的最大支持值

不同的系统是不同的，但在所有情况下都小于最大值

size_t的可表示值。

free函数

free(void * p)

释放由p指向的内存块，这是以前已经存在的

使用malloc或相关例程(如realloc)进行分配。

如果p为零，它没有作用。它可以是任意的(也就是坏的!)

如果p已经被释放，则返回结果。

除非禁用(使用mallopt)，否则释放非常大的空间将会

在可能的情况下，自动触发操作

将未使用的内存返回给系统，从而减少程序占用空间。

内存分配背后的系统调用

无论是 malloc 函数还是 free 函数，我们动态申请和释放内存时，都经常会使用，但是它们并不是真正与系统交互的函数。这些函数背后的系统调用主要是 (s)brk 函数以及 mmap, munmap 函数。

(s)brk

对于堆的操作，操作系统提供了 brk 函数，glibc 库提供了 sbrk 函数，我们可以通过增加 brk 的大小来向操作系统申请内存。

初始时，堆的起始地址 start_brk 以及堆的当前末尾 brk 指向同一地址。根据是否开启 ASLR，两者的具体位置会有所不同

不开启 ASLR 保护时，start_brk 以及 brk 会指向 data/bss 段的结尾。
开启 ASLR 保护时，start_brk 以及 brk 也会指向同一位置，只是这个位置是在 data/bss 段结尾后的随机偏移处。

mmap

一般在多线程中使用，故不怎么出现。

作用：创建独立的匿名映射段
匿名映射的目的主要是可以申请以 0 填充的内存，并且这块内存仅被调用进程所使用。

Arena 头部结构:malloc_state

struct malloc_state
{
  /* Serialize access.  */
  mutex_t mutex;
  /* Flags (formerly in max_fast).  */
  int flags;
  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];
  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;
  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;
  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];
  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];
  /* Linked list */
  struct malloc_state *next;
  /* Linked list for free arenas.  */
  struct malloc_state *next_free;
  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

chunk

我们称由 malloc 申请的内存为 chunk，这块内存在 ptmalloc 中被称为 malloc_chunk 结构体表示

无论一个 chunk 的大小如何，处于分配状态还是释放状态，它们都使用一个统一的结构。虽然它们使用了同一个数据结构，但是根据是否被释放，它们的表现形式会有所不同

/*
  This struct declaration is misleading (but accurate and necessary).
  It declares a "view" into memory allowing access to necessary
  fields at known offsets from a given base. See explanation below.
  这种结构声明是有误导性的(但准确且必要)。

它将一个“视图”声明到内存中，允许必要的访问

给定基的已知偏移量的字段。请参阅下面的解释。
*/
struct malloc_chunk {
  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */
  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;
    
  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

prev_size

如果前一个 chunk 是空闲的话，记录物理相邻前一个 chunk 的大小；否则存储前一个的数据

size

该 chunk 的大小，必须是 2*SIZE_SZ 的整数倍，后三位分别是：
● NON_MAIN_ARENA（A）：表示该 chunk 属于主分配区（1）或者非主分配区（0）
● IS_MAPPED（M）：记录当前 chunk 是否是由 mmap 分配的，M 为 1 表示该 chunk 是从 mmap 映射区域分配的，否则是从 heap 区域分配的
● PREV_INUSE（P）：记录前一个 chunk 块是否被分配。一般来说，堆中第一个被分配的内存块的 size 字段的 P 位都会被设置为 1，以便于防止访问前面的非法内存。当一个 chunk 的 size 的 P 位为 0 时，我们能通过 prev_size 字段来获取上一个 chunk 的大小以及地址。这也方便进行空闲 chunk 之间的合并。

fd、bk

chunk 处于分配时从 fd 字段开始就是用户数据了，chunk 空闲时会被添加到对应的空闲管理链表中
● fd：指向下一个（非物理相邻）空闲的 chunk
● bk：指向上一个（非物理相邻）空闲的 chunk
● 通过 fd 和 bk 可以将空闲的 chunk 块加入到空闲的 chunk 块链表进行统一管理

fd_nextsize， bk_nextsize

也是只有 chunk 空闲的时候才使用，不过其用于较大的 chunk（large chunk）
● fd_nextsize：指向前一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。
● bk_nextsize：指向后一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。
一般空闲的 large chunk 在 fd 的遍历顺序中，按照由大到小的顺序排列。这样做可以避免在寻找合适 chunk 时挨个遍历。