堆：于动态中绽放灵魂

Time: 2020-02-04 Tags: binary
Link: 堆：于动态中绽放灵魂

什么是堆？

如果内存中只存在栈，那么对于面向过程的变成语言来说显然是不够的。这时，堆就可以充当一个很重要的角色。

堆(heap)是一个很大的内存空间。常常占据整个虚拟内存的绝大部分。程序可以申请一块连续的内存，并且自由地使用它。这块内存在程序主动放弃之前都会一直有效。在不同的平台上，堆的分配方式有所不同。在pwn中，我们一般指Linux进程堆分配。

堆的生长方向是从低地址向高地址生长的。对堆操作的是由堆管理器（ptmalloc2）来实现的，而不是操作系统内核。

堆的创建和释放

malloc函数

#include <stdlib.h>
void *malloc(size_t size);

malloc函数成功申请后返回一个指针 ，指向大小至少为size字节的内存块。

free函数

#include <stdlib.h>
void free(void *ptr);

free函数会释放由p指向的内存块，这个内存块可以是由malloc函数或者readlloc函数分配的。

当释放后的内存块再次释放时，会产生错误(double free)。

内存分配有关的函数

两个系统调用，一个是brk()系统调用，一个是mmap()系统调用。

brk函数

int brk(void* end_data_segment)

brk实际上是设置进程数据段的结束地址。如果我们把数据段的结束地址向高地址移动，那么扩大的那部分空间就可以被我们使用，把这块空间作为堆空间是最常见的做法之一。glibc中还有一个兄弟函数叫sbrk，它实际上是对brk函数的包装。

mmap函数

当虚拟地址空间不映射到某个文件的时候，我们称这块空间为匿名空间。匿名空间就可以拿来做堆空间。

void* mmap(
	void *start,
    size_t length,
    int prot,
    int flags,
    int fd,
    off_t offset);

prot和flags两个参数用于设置申请的空间权限(可读、可写、可执行)以及映射类型(文件映射、匿名空间等)，最后两个参数是用于文件映射时指定文件描述符和文件偏移的。

glibc中的malloc函数对于小于128kb的申请会从现有的堆空间里分配一段并且返回，对于大于128kb的申请会用mmap分配一段匿名空间，然后在匿名空间内为用户分配空间。

malloc——用mmap实现：

void *malloc(size_t nbytes)
{
    void* ret = mmap(0, nbytes, PROT_READ | PROT_WRITE
                    MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
    if (ret == MAP_FAILED)
        return 0;
    return ret;
}

堆的基本结构

struct malloc_chunk 
{
      
  INTERNAL_SIZE_T      prev_size;  
  INTERNAL_SIZE_T      size;       
      
  struct malloc_chunk* fd;         
  struct malloc_chunk* bk;
      
  struct malloc_chunk* fd_nextsize;
  struct malloc_chunk* bk_nextsize;
};

  1. prev_size字段。只有在前面一个堆块是空闲的时候才有指，用来指示前一个堆块的大小。前面一个堆块在使用时，他的值始终为 0。

  2. size字段。用来指示当前堆块的大小，后三位有特殊意义：

    • NON_MAIN_ARENA 堆块是否位于主进程
    • IS_MAPPED 堆块是否是mmap分配的
    • PREV_INUSE 前一个堆块是否被分配，前一个堆块被分配的话，此位为1

  3. fd、bk

    chunk 处于分配状态时，从 fd 字段开始是用户的数据。

    chunk 空闲时，会被添加到对应的空闲管理链表中

    通过 fd 和 bk 可以将空闲的 chunk 块加入到空闲的 chunk 块链表进行统一管理

    fd 指向下一个（非物理相邻）空闲的 chunk

    bk 指向上一个（非物理相邻）空闲的 chunk

  4. fd_nextsize、bk_nextsize 只有 chunk 空闲的时候才使用，用于较大的 chunk

    fd_nextsize 指向前一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。

    bk_nextsize 指向后一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。

例如，在64位系统中，malloc(8)会申请0x21大小的堆块。

16是分配的最小字节数，两个8分别是prev_size、size字段的大小，1是PERV_INUSE的值

指针与地址

在 IDA 伪代码中的指针形式形如下面的情况：

*(qword_6020A8 + 8)

汇编代码等同于：

.text:0000000000400F85                 mov     rax, cs:qword_6020A8
.text:0000000000400F8C                 mov     rax, [rax+8]

在pwn的堆中，经常会有一些像“笔记管理系统”这样的题目。这些“笔记”很多是用链表来连接的，记录了当前 note 的大小、属性、内容等等。

*(qword_6020A8 + 16) 代表从 qword_6020A8 这个地址出再往后偏移 16 个字节，取到这个地址存储的值，接着把 1 赋值给这个地方（也就是把 1 存入这个地址）

依次类推就可以在不连续的内存空间中，把整个 note 的数据结构存储下来了。

申请堆块的本质

堆管理器 ptmalloc2 主要是通过 malloc/free 函数来分配和释放内存块。

ptmalloc2 的作用通俗的讲就是相当于一个”中间商”，在程序想要申请向系统申请堆空间时，这里的 ptmalloc2 就会申请一块很大的空间，并根据算法从这些内存中把空间真正的分配给程序。

#include <stdlib.h>
#include <malloc.h>

int main(){

        char *p;
        p = malloc(10);

        return 0;
}

放在gdb里面调试，在call malloc@plt处下断点 pwndbg> b *0x555555554657

使用vmmap，发现没有heap段。执行n，再使用vmmap，出现堆段。

 0x555555756000     0x555555777000 rw-p    21000 0      [heap]

大小为132kb:

>>> (0x555555777000-0x555555756000)/1024
>>> 132.0

这132KB的堆空间叫做arena，此时因为是主线程分配的，所以这个区域叫做 main arena。

也就是说这 132 KB 是”厂家”（内核）批发给”中间商”（ptmalloc2）的货物，以便下次程序在向系统申请小内存的时候，直接去”中间商”去取就行了，他就会在这 132KB 中按照要申请”货物”的多少进行分配下去。若”中间商”缺货了话，ptmalloc2 就继续去找”厂家”（系统内核）去取货。

查看已分配的堆内存分布

刚刚我们已经动态执行了malloc函数，保存的堆指针在ax寄存器中，

RAX  0x555555756260 ◂— 0x0

我们用下面的指令查看堆空间：

pwndbg> x/32gx 0x555555756260-0x10

-0x10是为了看到堆的头部

main_arena 与 top chunk

main_arena

刚刚介绍了main_arena了，我们使用指令可以查看main_arena：

pwndbg> x/32gx &main_arena
0x7ffff7dcfc40 <main_arena>:	0x0000000000000000	0x0000000000000000
0x7ffff7dcfc50 <main_arena+16>:	0x0000000000000000	0x0000000000000000
0x7ffff7dcfc60 <main_arena+32>:	0x0000000000000000	0x0000000000000000
0x7ffff7dcfc70 <main_arena+48>:	0x0000000000000000	0x0000000000000000
0x7ffff7dcfc80 <main_arena+64>:	0x0000000000000000	0x0000000000000000
0x7ffff7dcfc90 <main_arena+80>:	0x0000000000000000	0x0000000000000000
0x7ffff7dcfca0 <main_arena+96>:	0x0000555555756270	0x0000000000000000
0x7ffff7dcfcb0 <main_arena+112>:	0x00007ffff7dcfca0	0x00007ffff7dcfca0
0x7ffff7dcfcc0 <main_arena+128>:	0x00007ffff7dcfcb0	0x00007ffff7dcfcb0
0x7ffff7dcfcd0 <main_arena+144>:	0x00007ffff7dcfcc0	0x00007ffff7dcfcc0
0x7ffff7dcfce0 <main_arena+160>:	0x00007ffff7dcfcd0	0x00007ffff7dcfcd0
0x7ffff7dcfcf0 <main_arena+176>:	0x00007ffff7dcfce0	0x00007ffff7dcfce0
0x7ffff7dcfd00 <main_arena+192>:	0x00007ffff7dcfcf0	0x00007ffff7dcfcf0
0x7ffff7dcfd10 <main_arena+208>:	0x00007ffff7dcfd00	0x00007ffff7dcfd00
0x7ffff7dcfd20 <main_arena+224>:	0x00007ffff7dcfd10	0x00007ffff7dcfd10
0x7ffff7dcfd30 <main_arena+240>:	0x00007ffff7dcfd20	0x00007ffff7dcfd20

top chunk

顾名思义，是堆中第一个堆块。相当于一个”带头大哥”，程序以后分配到的内存到要放在他的后面。

简单点说，也就是在程序在向堆管理器申请内存时，没有合适的内存空间可以分配给他，此时就会从 top chunk 上”剪切”一部分作为 chunk 分配给他

free和bins

bins 这个概念是与内存回收相关的，也就是堆管理器会根据用户已经申请到的内存空间大小进行释放，来决定放入哪类 bins 当作去。bins 直接翻译过来就是”垃圾桶”的意思，所以在系统在决定使用哪个 bins 时可以看作为”垃圾的分类”。

主要的 bins 分为以下几类，据空闲的 chunk 的大小以及使用状态将 chunk 初步分为 4 类：fast bins，small bins，large bins，unsorted bin。

free函数

#include <stdlib.h>
#include <string.h>

int main(){

        char *p;

        p = malloc(10);

        memcpy(p,"Hello",5);
        free(p);
        return 0;
}

程序将Hello复制到申请的堆空间里。

在memcpy处下断点，n后查看堆空间，再单步调试，free后再查看堆空间。

之后查看main_arena

小总结

调用 free 函数以后程序做了两件事： 1.清空此堆块的 user data 2.将此堆块的指针存储到 main_arena 中了（或是 fast bin 中）

fastbin

顾名思义，就是为了快速重新分配回内存而存在的一个结构。

fast bin 的特性

1.使用单链表来维护释放的堆块 也就是和上图一样，从main_arena 到 free 第一个块的地方是采用单链表形式进行存储的，若还有 free 掉的堆块，则这个堆块的 fk 指针域就会指针前一个堆块。

2.采用后进先出的方式维护链表（类似于栈的结构） 当程序需要重新 malloc 内存并且需要从fastbin 中挑选堆块时，会选择后面新加入的堆块拿来先进行内存分配

smallbin

  1. small bins 中每个 chunk 的大小与其所在的 bin 的 index 的关系为：chunk_size = 2 * SIZE_SZ *index。
  2. small bins 中一共有 62 个循环双向链表，每个链表中存储的 chunk 大小都一致。
  3. small bins 中每个 bin 对应的链表采用 FIFO 的规则，所以同一个链表中先被释放的 chunk 会先被分配出去。
  4. fast bin 中的 chunk 是有可能被放到 small bin 中去的。

largebin

  1. large bins 中一共包括 63 个 bin，每个 bin 中的 chunk 的大小不一致，而是处于一定区间范围内。
组数量公差
13264B
216512B
384096B
4432768B
52262144B
61不限制

unsortedbin

  1. unsorted bin 可以视为空闲 chunk 回归其所属 bin 之前的缓冲区。
  2. unsorted bin 只有一个链表。unsorted bin 中的空闲 chunk 处于乱序状态。

  3. unsorted Bin 在使用的过程中，采用的遍历顺序是 FIFO 。

  4. 初始情况下，我们可以将 unsorted chunk 作为 top chunk。

参考文章

CTF pwn 中最通俗易懂的堆入坑指南 https://www.anquanke.com/post/id/163971

堆概述 https://wiki.x10sec.org/pwn/heap/heap_overview/#_5

堆相关数据结构 https://wiki.x10sec.org/pwn/heap/heap_structure/


萌ICP备20224060号
如果这篇博客帮助到你，可以留言夸夸我~
CC BY-NC 4.0 （除特别声明或转载文章外）