Heap--初探--chunk的获取与释放
原理学习
CTF-PWN
发布日期:   2020-09-07
文章字数:   2.9k
阅读时长:   12 分
阅读次数:  

什么是堆

堆不同于栈，堆是动态分配的（由操作系统内核或者堆管理器），只有在程序中需要时才会分配。在 CTF 的 pwn 程序中，栈是程序加载进内存后就会出现，而堆是由 malloc、alloc、realloc 函数分配内存后才会出现。
其生长方向是正常的从低地址向高地址生长，栈的高地址向低地址生长就像个异类。堆可以申请到的内存空间比栈要大很多，在 linux 的 4G 的虚拟内存空间里最高可以达到 2.9 G 的空间。
对堆的操作是由堆管理器（ptmalloc2）进行的,并不是操作系统。

堆管理器就像是一个批发商，在malloc分配堆空间时就会向操作系统‘进货‘ 当然就像商人一样进一大批货物（堆空间）这样在程序多次进行malloc申请内存时就不需要频繁的访问操作系统，可以直接向堆管理器进行请求，大量减少了系统调用的开销，提高程序运行性能。

堆的定义与结构

在程序的执行过程中，我们称由 malloc 申请的内存为 chunk **。这块内存在 ptmalloc 内部用 malloc_chunk 结构体来表示，当程序申请的 chunk 被 free 后，会被加入到相应的空闲管理列表中。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;
};
一般来说，size_t 在 64 位中是 64 位无符号整数，32 位中是 32 位无符号整数。

字段解释：

  • prev_size, 如果该 chunk 的物理相邻的前一个chunk是空闲的话，那该字段记录的是前一个 chunk 的大小 (包括 chunk 头)。否则，该字段可以用来存储物理相邻的前一个 chunk 的数据。这里的前一 chunk 指的是较低地址的 chunk 。

  • size ，该 chunk 的大小，大小必须是 2 * SIZE_SZ 的整数倍。如果申请的内存大小不是 2 * SIZE_SZ 的整数倍，会被转换满足大小的最小的 2 * SIZE_SZ 的倍数。32 位系统中，SIZE_SZ 是 4；64 位系统中，SIZE_SZ 是 8。 该字段的低三个比特位对 chunk 的大小没有影响，它们从高到低分别表示

    • NON_MAIN_ARENA，记录当前 chunk 是否不属于主线程，1 表示不属于，0 表示属于。
    • IS_MAPPED，记录当前 chunk 是否是由 mmap 分配的。
    • PREV_INUSE，记录前一个 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）。

其对应结构：Free chunk

Malloced chunk

注意事项:
32位或64位分配的到的堆分别要4字节对齐，8字节对齐即他们的大小分别是4和8的倍数。
在64位中（同32）又因为chunk头是必须要有的所以会占据16字节大小，所以在64位中malloc最小分配到的chunk大小是16字节。size字段记录了本chunk的完整大小而，chunk大小一定是8的倍数，所以size最后的三bit位没用会被置零（100=4，1000=8）但是设计者为了极值利用每一点空间就把这三位定义了其数据意义（前文所提到的）但是我们主要抓住最后一位带表的意义：前一个chunk是否是free状态，1代表是malloced状态，0代表free状态

堆的开辟–malloc

其实除了malloc函数还有realloc，calloc函数也能开辟堆空间，但我们先了解最常用的malloc
malloc函数：

#include <stdlib.h>
void *malloc(size_t size);   //在使用malloc的时候要进行强制类型转换为指针类型

malloc函数申请地址成功后返回一个指针，指向大小为至少size字节的内存块，结合上面的结构图即malloced chunk的user_data_start处的地址作为指针返回，其下方用来存放用户数据，空间大于等于malloc所申请的内存（8字节对齐嘛）
回到之前我们所提到的：堆管理器’进货‘，在我们执行malloc之前ptmalloc2就会向系统申请一块较大的内存，来让用户多次申请。举个例子：

*RIP  0x4004f4 (main+13) <— call   0x4003f0
────────────────────────────────────────────────────────────[ DISASM ]─────────────────────────────────────────────────────────────
   0x4004ef <main+8>               mov    edi, 0x24
 ► 0x4004f4 <main+13>              call   malloc@plt <malloc@plt>
        size: 0x24

   0x4004f9 <main+18>              mov    qword ptr [rbp - 8], rax
   0x4004fd <main+22>              mov    eax, 0
   0x400502 <main+27>              leave  
   0x400503 <main+28>              ret    

   0x400504                        nop    word ptr cs:[rax + rax]
   0x40050e                        nop    
   0x400510 <__libc_csu_init>      push   r15
   0x400512 <__libc_csu_init+2>    push   r14
   0x400514 <__libc_csu_init+4>    mov    r15, rdx
─────────────────────────────────────────────────────────[ SOURCE (CODE) ]─────────────────────────────────────────────────────────
In file: /home/hunter/how2heap/my_heap/test.c
   1 #include<stdio.h>
   2 #include<stdlib.h>
   3 
   4 int main()
   5 {
 ► 6     void* p = malloc(0x24);
   7     return 0;
   8 }
─────────────────────────────────────────────────────────────[ STACK ]─────────────────────────

此时还没执行malloc我们来看看vmmap

pwndbg> vmmap
LEGEND: STACK | HEAP | CODE | DATA | RWX | RODATA
          0x400000           0x401000 r-xp     1000 0      /home/hunter/how2heap/my_heap/a.out
          0x600000           0x601000 r--p     1000 0      /home/hunter/how2heap/my_heap/a.out
          0x601000           0x602000 rw-p     1000 1000   /home/hunter/how2heap/my_heap/a.out
    0x7ffff79e4000     0x7ffff7bcb000 r-xp   1e7000 0      /lib/x86_64-linux-gnu/libc-2.27.so
    0x7ffff7bcb000     0x7ffff7dcb000 ---p   200000 1e7000 /lib/x86_64-linux-gnu/libc-2.27.so
    0x7ffff7dcb000     0x7ffff7dcf000 r--p     4000 1e7000 /lib/x86_64-linux-gnu/libc-2.27.so
    0x7ffff7dcf000     0x7ffff7dd1000 rw-p     2000 1eb000 /lib/x86_64-linux-gnu/libc-2.27.so
    0x7ffff7dd1000     0x7ffff7dd5000 rw-p     4000 0      
    0x7ffff7dd5000     0x7ffff7dfc000 r-xp    27000 0      /lib/x86_64-linux-gnu/ld-2.27.so
    0x7ffff7fdc000     0x7ffff7fde000 rw-p     2000 0      
    0x7ffff7ff7000     0x7ffff7ffa000 r--p     3000 0      [vvar]
    0x7ffff7ffa000     0x7ffff7ffc000 r-xp     2000 0      [vdso]
    0x7ffff7ffc000     0x7ffff7ffd000 r--p     1000 27000  /lib/x86_64-linux-gnu/ld-2.27.so
    0x7ffff7ffd000     0x7ffff7ffe000 rw-p     1000 28000  /lib/x86_64-linux-gnu/ld-2.27.so
    0x7ffff7ffe000     0x7ffff7fff000 rw-p     1000 0      
    0x7ffffffde000     0x7ffffffff000 rw-p    21000 0      [stack]
0xffffffffff600000 0xffffffffff601000 r-xp     1000 0      [vsyscall]
pwndbg>

还没有出现堆，继续执行

pwndbg> vmmap
LEGEND: STACK | HEAP | CODE | DATA | RWX | RODATA
          0x400000           0x401000 r-xp     1000 0      /home/hunter/how2heap/my_heap/a.out
          0x600000           0x601000 r--p     1000 0      /home/hunter/how2heap/my_heap/a.out
          0x601000           0x602000 rw-p     1000 1000   /home/hunter/how2heap/my_heap/a.out
          0x602000           0x623000 rw-p    21000 0      [heap]                 ==============>堆空间出现
    0x7ffff79e4000     0x7ffff7bcb000 r-xp   1e7000 0      /lib/x86_64-linux-gnu/libc-2.27.so
    0x7ffff7bcb000     0x7ffff7dcb000 ---p   200000 1e7000 /lib/x86_64-linux-gnu/libc-2.27.so
    0x7ffff7dcb000     0x7ffff7dcf000 r--p     4000 1e7000 /lib/x86_64-linux-gnu/libc-2.27.so
    0x7ffff7dcf000     0x7ffff7dd1000 rw-p     2000 1eb000 /lib/x86_64-linux-gnu/libc-2.27.so
    0x7ffff7dd1000     0x7ffff7dd5000 rw-p     4000 0      
    0x7ffff7dd5000     0x7ffff7dfc000 r-xp    27000 0      /lib/x86_64-linux-gnu/ld-2.27.so
    0x7ffff7fdc000     0x7ffff7fde000 rw-p     2000 0      
    0x7ffff7ff7000     0x7ffff7ffa000 r--p     3000 0      [vvar]
    0x7ffff7ffa000     0x7ffff7ffc000 r-xp     2000 0      [vdso]
    0x7ffff7ffc000     0x7ffff7ffd000 r--p     1000 27000  /lib/x86_64-linux-gnu/ld-2.27.so
    0x7ffff7ffd000     0x7ffff7ffe000 rw-p     1000 28000  /lib/x86_64-linux-gnu/ld-2.27.so
    0x7ffff7ffe000     0x7ffff7fff000 rw-p     1000 0      
    0x7ffffffde000     0x7ffffffff000 rw-p    21000 0      [stack]
0xffffffffff600000 0xffffffffff601000 r-xp     1000 0      [vsyscall]

我们主要到堆空间从0x602000 开始，到0x623000 结束，其整个大小为：132KB

>>> 0x623000 -0x602000
135168
>>> 135168/1024
132
>>>

这就是ptmalloc2商人的货物，是调用了brk和sbkr函数，当需求大于132字节就会调用mmap函数来获取一个更大的堆空间。
然后每当有malloc函数来向ptmalloc2申请空间时（在bins中没有符合大小的情况下），商人就会从货物中切一块对应大小的chunk，从低地址往高地址切，切了剩下的叫top chunk，原来的那个货物叫arena，由主线程分配的arena叫做main_arena.

堆的释放-free

用一个简单的例子来理解一下 free 函数的实现原理。

#include<stdio.h>
#include<stdlib.h>

int main()
{
    void* p = malloc(0x24);
    read(0,p,0x10);
    free(p);
    return 0;
}

gdb：

──────────────────────────────────────────────────────────────[ SOURCE (CODE) ]──────────────────────────────────────────────────────────────
In file: /home/matrix/test.c
    3 
    4 int main()
    5 {
    6     void* p = malloc(0x24);
    7     read(0,p,0x10);
 ►  8     free(p);
    9     return 0;
   10 }
──────────────────────────────────────────────────────────────────[ STACK ]──────────────────────────────────────────────────────────────────
00:0000│ rsp  0x7fffffffde90 —▸ 0x7fffffffdf80 ◂— 0x1
01:0008│      0x7fffffffde98 —▸ 0x602010 ◂— 'AAAAAAAB\n'   =====>输入的字符
02:0010│ rbp  0x7fffffffdea0 —▸ 0x400600 (__libc_csu_init) ◂— push   r15
03:0018│      0x7fffffffdea8 —▸ 0x7ffff7a2d840 (__libc_start_main+240) ◂— mov    edi, eax
04:0020│      0x7fffffffdeb0 ◂— 0x1
05:0028│      0x7fffffffdeb8 —▸ 0x7fffffffdf88 —▸ 0x7fffffffe2f0 ◂— '/home/matrix/a.out'
06:0030│      0x7fffffffdec0 ◂— 0x1f7ffcca0
07:0038│      0x7fffffffdec8 —▸ 0x4005b6 (main) ◂— push   rbp
────────────────────────────────────────────────────────────────[ BACKTRACE ]────────────────────────────────────────────────────────────────
 ► f 0           4005e7 main+49
   f 1     7ffff7a2d840 __libc_start_main+240
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
pwndbg> x/32gx 0x602010 -0x10   //这里-0x10因为malloc返回的是user_data_start地址 
0x602000:    0x0000000000000000    0x0000000000000031  ====>chunk_head
0x602010:    0x4241414141414141    0x000000000000000a  ====>user_data
0x602020:    0x0000000000000000    0x0000000000000000
0x602030:    0x0000000000000000    0x0000000000020fd1  ====>top chunk
0x602040:    0x0000000000000000    0x0000000000000000

可以发现size字段是0x31：首先size的最后三bit有P位是1，然后我申请了0x24字节，为了对齐ptmalloc2给了我0x20的user_data，0x10的chunk_head，显然这里的0x20不足满足我的0x24需求。但是下面的top chunk,
的Prev_size字段无意义（因为前一个chunk是malloced）也可以被上一个malloced chunk使用。所以就不在多分配了。所以我们申请得到chunk 大小位0x30但是可以使用下面top chunk的Prev_size。

继续执行：

In file: /home/matrix/test.c
    4 int main()
    5 {
    6     void* p = malloc(0x24);
    7     read(0,p,0x10);
    8     free(p);
 ►  9     return 0;
   10 }
──────────────────────────────────────────────────────────────────[ STACK ]──────────────────────────────────────────────────────────────────
00:0000│ rsp  0x7fffffffde90 —▸ 0x7fffffffdf80 ◂— 0x1
01:0008│      0x7fffffffde98 —▸ 0x602010 ◂— 0x0
02:0010│ rbp  0x7fffffffdea0 —▸ 0x400600 (__libc_csu_init) ◂— push   r15
03:0018│      0x7fffffffdea8 —▸ 0x7ffff7a2d840 (__libc_start_main+240) ◂— mov    edi, eax
04:0020│      0x7fffffffdeb0 ◂— 0x1
05:0028│      0x7fffffffdeb8 —▸ 0x7fffffffdf88 —▸ 0x7fffffffe2f0 ◂— '/home/matrix/a.out'
06:0030│      0x7fffffffdec0 ◂— 0x1f7ffcca0
07:0038│      0x7fffffffdec8 —▸ 0x4005b6 (main) ◂— push   rbp
────────────────────────────────────────────────────────────────[ BACKTRACE ]────────────────────────────────────────────────────────────────
 ► f 0           4005f3 main+61
   f 1     7ffff7a2d840 __libc_start_main+240
─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
pwndbg> x/32gx 0x602010-0x10
0x602000:    0x0000000000000000    0x0000000000000031
0x602010:    0x0000000000000000    0x000000000000000a  =====>前面的数据被清空了
0x602020:    0x0000000000000000    0x0000000000000000
0x602030:    0x0000000000000000    0x0000000000020fd1
0x602040:    0x0000000000000000    0x0000000000000000

free之后user_data的前8字节数据被清空，但是没有清空后面的\n 。这里咱们留一个伏笔~~，再输入AAAAAAAABBBBBBBB试一试：

──────────────────────────────────────────────────────────────[ SOURCE (CODE) ]──────────────────────────────────────────────────────────────
In file: /home/matrix/test.c
    4 int main()
    5 {
    6     void* p = malloc(0x24);
    7     read(0,p,0x10);
    8     free(p);
 ►  9     return 0;
   10 }
──────────────────────────────────────────────────────────────────[ STACK ]──────────────────────────────────────────────────────────────────
00:0000│ rsp  0x7fffffffddb0 —▸ 0x7fffffffdea0 ◂— 0x1
01:0008│      0x7fffffffddb8 —▸ 0x602010 ◂— 0x0
02:0010│ rbp  0x7fffffffddc0 —▸ 0x400600 (__libc_csu_init) ◂— push   r15
03:0018│      0x7fffffffddc8 —▸ 0x7ffff7a2d840 (__libc_start_main+240) ◂— mov    edi, eax
04:0020│      0x7fffffffddd0 ◂— 0x1
05:0028│      0x7fffffffddd8 —▸ 0x7fffffffdea8 —▸ 0x7fffffffe24a ◂— '/home/matrix/a.out'
06:0030│      0x7fffffffdde0 ◂— 0x1f7ffcca0
07:0038│      0x7fffffffdde8 —▸ 0x4005b6 (main) ◂— push   rbp
────────────────────────────────────────────────────────────────[ BACKTRACE ]────────────────────────────────────────────────────────────────
 ► f 0           4005f3 main+61
   f 1     7ffff7a2d840 __libc_start_main+240
─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
pwndbg> x/32gx 0x602000
0x602000:    0x0000000000000000    0x0000000000000031
0x602010:    0x0000000000000000    0x4242424242424242   <======
0x602020:    0x0000000000000000    0x0000000000000000
0x602030:    0x0000000000000000    0x0000000000020fd1   <======top chunk
0x602040:    0x0000000000000000    0x0000000000000000
0x602050:    0x0000000000000000    0x0000000000000000

果然后面的8字节不会被置零！想要解开这个谜团就不得不提到上古神将豳嗣了（bins）~~

上古神将：bins

传说当时的chunks界物资浪费严重，operating system被渐渐掏空，造物主为了制衡派遣bins神去帮chunks们学习垃圾分类…..
bins共有4位：fastbins unsortedbin smallbin largebins。如同俄罗斯套娃，这四位bin也有各自的小将

fastbins：专门回收小型垃圾（free chunks） 默认就是这7位，在32Bytes pallar world--operating system  他们的大小除以2即可
0x20: 0x0
0x30: 0x0
0x40: 0x0
0x50: 0x0
0x60: 0x0
0x70: 0x0
0x80: 0x0

unsortedbin ：大将一人，且听下回分解
smallbins：且听下回分解
largebins：且听下回分解

总结

free后的chunks会依据自己的完整大小放入不同的bins中，相应的也会清除某些数据但并不会全部清除。谜团众多请听下回分解~~。

赏

  转载请注明: Squarer Heap--初探--chunk的获取与释放

 上一篇
Heap--初探--bins神将 Heap--初探--bins神将
Previously on Heap–初探–chunk的获取与释放：我们当时最大的疑惑差不多就是Free后的chunks都怎么了，这里来逐一解答。 前情提要ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk
2020-09-07 CTF-PWN
原理学习
下一篇 
XCTF-CHALLENGE-greeting_150 XCTF-CHALLENGE-greeting_150
昨天好不容易装上pwndbg，总是因为最后./setup时报错，说python3.6找不到命令，在网上找了很多教程都没用，最后把了解到pwndbg相当于一个加强版的gdb，然后我就把gdb删了就顺利装上了😭废话少说，回到题目~~ chec
2020-09-03 CTF-PWN
xctf-pwn-challenge
  目录