【pwn】学pwn日记(堆结构学习)

【pwn】学pwn日记(堆结构学习)

1、什么是堆?

堆是下图中绿色的部分,而它上面的橙色部分则是堆管理器

我们都知道栈的从高内存向低内存扩展的,而堆是相反的,它是由低内存向高内存扩展的

【pwn】学pwn日记(堆结构学习)

堆管理器的作用,充当一个中间人的作用。管理从操作系统中申请来的物理内存,如果有用户需要,就提供给他。

2、了解堆管理器

【pwn】学pwn日记(堆结构学习)

注意:linux使用glibc

【pwn】学pwn日记(堆结构学习)

这里有两种申请内存的系统调用:

  1. brk
  2. mmap

第一种brk,是将heap下方的data段(bss属于data段),向上扩展申请的内存。

第二种mmap,其实下图中的shared libraries叫做mmap区域,也就是内存映射。如果使用这种方式申请内存,那么就在这块区域内开辟新的内存空间。

【pwn】学pwn日记(堆结构学习)

主线程可以用brk和mmap,如果主线程申请的空间过大,那么会使用mmap;如果申请的空间比较小,那么就会再data段上向上扩展一段空间

子线程只能使用mmap段

【pwn】学pwn日记(堆结构学习)

malloc就是向堆管理器申请一块内存空间

free就是将申请来的内存空间归还给堆管理器

用户使用malloc向堆管理器要内存,堆管理器通过brk和mmap向操作系统要内存

3、堆管理器的操作方式

首先了解三个关键词:

  • arena
  • chunk
  • bin

【pwn】学pwn日记(堆结构学习)

堆管理器可以与用户的内存交易发生于arena中

可以理解为堆管理器向操作系统批发来的有冗余的内存库存

每一个线程中都有一个arena分配区,每一个分配区都有一个控制结构

【pwn】学pwn日记(堆结构学习)

【pwn】学pwn日记(堆结构学习)

chunk是内存分配的最小单位,也是我们malloc过来的内存

chunk的size控制字段的最后三位分别是A、M、P

A代表是否是主线程arena中分配的内存

M代表这段区域是否是MMAP的

P用于标识上一个chunk的状态。当它为1时,表示上一个chunk处于释放状态,否则表示上一个chunk处于使用状态

我们来了解malloc_chunk各个成员的功能

  • prev_size:如果上一个chunk处于释放状态,用于表示其大小。否则作为上一个chunk的一个部分,用于保存上一个chunk的数据
  • size:表示当前size的大小,根据规定必须是2*SIZE_SZ的整数倍。默认情况下,SIZE_SZ在64位系统下是8字节,32位下是4字节。受到内存对齐的影响,最后3个比特位被用作状态标识,从高到低分别表示
    • NON_MAIN_ARENA:用于标识当前堆是否不属于主线程,1 表示不属于,0 表示属于。
    • IS_MAPPED:用于标识一个chunk是否是从mmap()函数得到的。如果用户申请一个相当大的内存,malloc会通过mmap分配一个映射段
    • PREV_INUSE:用于标识上一个chunk的状态。当它为0时,表示上一个chunk处于释放状态,否则表示上一个chunk处于使用状态
  • fd和bk:仅在当前chunk处于释放状态有效。chunk被释放后会加入相应的bin链表中,此时fd和bk指向该chunk在链表的下一个和上一个free chunk(不一定时物理相连的)。如果当前chunk处于使用状态,那么这两个字段是无效的,都是用户使用的空间
  • fd_nextsize和bk_nextsize:与fd和bk相似,仅在处于释放状态时有效,否则就是用户使用的空间。不同的是,它们仅仅用于large bin,分别指向前后第一个和当前chunk大小不同的chunk

4、各种chunk的结构

chunk有4种:

  1. alloced_chunk

  2. free_chunk

  3. top chunk

  4. ast_remainder chunk

1.alloced_chunk

  • 首先认识alloced chunk结构,alloced chunk就是处于使用状态的chunk,即pre_size和size组成的chunk header和后面供用户使用的user data。malloc函数返回给用户的实际上是指向用户数据的mem指针

【pwn】学pwn日记(堆结构学习)

2.free_chunk

  • 再认识free chunk中最常见的几种
    • small bin、unsorted bin
    • 这两种结构如下图所示

【pwn】学pwn日记(堆结构学习)

  • 如果下面的这个chunk被free了,并且标志位P=0(也就是上一个chunk是free chunk),那么会变成这样的一个大的free chunk

【pwn】学pwn日记(堆结构学习)

  • large bin free chunk 的结构

【pwn】学pwn日记(堆结构学习)

  • fast bin free chunk的结构

【pwn】学pwn日记(堆结构学习)

3.top chunk

  • 我们再来看top chunk
    • 在整个堆初始化后,会被当成一个free chunk,称为top chunk,每次用户申请内存的时候,如果bins中没有合适的chunk,malloc就会从top chunk中进行划分,如果top chunk的大小不够,那么会调用brk()扩展堆的大小,然后从新生成的top chunk中进行切分。

4.last remainder chunk

  • 再看last_remainder chunk
  • 首先我们需要知道用户申请内存的过程,在底层是如何实现的
    • 首先,如果申请的内存小于64bytes,在fastbin中查找并给出
    • 如果申请大于64bytes,那么在unsorted bin中查找
    • 如果unsorted bin中没有适合申请内存大小的bin段,那么unsorted bin进行遍历合并一部分free chunk,在这些合并后的chunk中找合适的
    • 如果还没找到那么就向top chunk在申请一些内存
    • 如果top chunk的内存都不够,如果仅仅比top chunk大一点,那么向操作系统要一点,通过brk()的方式扩展top chunk的空间
    • 如果比top chunk大了很多很多,那么通过mmap()的方式映射一块内存给和用户
  • 说了这么多过程,last remainder chunk在哪里出现了呢?
  • 其实在第二步就出现了,因为glibc的特性,在unsorted bin中查询到了比用户申请的内存大的chunk段,malloc就会返回这一段的size之后的指针。而如果我们的这段内存其实比用户申请的大了那么一点,多出来的就会变成我们的last remainder chunk,然后这一部分再在prev size中又进入了unsoorted bin中

5、chunk在glibc中的实现

【pwn】学pwn日记(堆结构学习)

chunk的结构体如上图,但是我们发现其实除了large bin free chunk之外,其他的chunk都没有用结构体中的所有变量

首先来看一个程序

【pwn】学pwn日记(堆结构学习)

我们申请了一个0x100空间大小的heap,用空指针prt指向malloc返回的地址,然后再通过free()函数释放这段空间

我们用gcc编译一下,得到了一个a.out的elf文件

【pwn】学pwn日记(堆结构学习)

我们使用gdb对这个elf文件进行调试

我们执行到malloc执行完毕的时候查看vmmap

【pwn】学pwn日记(堆结构学习)

我们可以看到两个细节:

  1. 第一个细节:虽然我们申请的是0x100大小的heap,但是这里第一次申请却有0x21000大小的区域。为什么会申请这么大的空间呢?这个就与我们刚刚了解到的arena有关了

    【pwn】学pwn日记(堆结构学习)

    我们知道操作系统会将内存分配给堆管理器,然后堆管理器再调用给用户。

    这个过程我们可以怎么理解呢?

    就像堆管理器向操作系统批发了一大块内存空间,然后再对用户进行一小份一小份的售卖。

    所以我们这里看到的0x21000大小的区域其实是操作系统给堆管理器的(也就是我们上面说的top chunk),然后我们的第二次调用malloc就从这一大份的内存空间中给出

  2. 第二个细节:我们发现我们申请的heap区域是在data段的高地址处,这也印证了我们刚刚说的如果主线程申请的内存区域比较小,那么是通过brk的方式在data段的高地址申请一块区域

一个小插曲:

我们想知道在x64下,能最小分配的堆空间是多大呢?

我们继续在刚刚的gdb调试中,输入fastbin

【pwn】学pwn日记(堆结构学习)

我们最小的chunk被free掉之后就会放入fastbin中,可以看到最小的fastbin是0x20的大小,为什么是0x20的大小呢?

【pwn】学pwn日记(堆结构学习)

首先在x64下,一个地址的内存大小就为0x8,那么我们的一个最小的chunk,就像上图一样,用pre size记录上一个chunk大小,用size记录自己的大小,size下面是一个fd,在下面是data,所以如果要最小的话,一共是4个0x8,那么就是0x20的大小

那么同理,在x86下,一个地址的内存大小为0x4,所以就是上面的图从中砍了一半,剩下左半部分是有效的,那么最小的堆在x86中就是0x10的大小

回到主线:

我们在test.c中使用malloc申请的是0x100的大小空间,但是实际上,堆管理器会给我们0x110的chunk,这多出来的0x10实际上就是prev size和size的大小,我们能够使用的data段就是这个0x100大小空间

【pwn】学pwn日记(堆结构学习)

这个时候我们又有一个问题了,我们是通过空指针prt当再malloc的返回值,那么我们的ptr指针在哪里呢?其实我们pte指针是指向0x100这个数据段的,而并非prev size这个chunk的开头部分

【pwn】学pwn日记(堆结构学习)

我们再回到调试,输入heap观察堆,可以发现我们申请的0x100大小的空间其实是0x111,这是为什么呢?(其他的heap、chunk区域可能是程序的缓冲区之类的)

【pwn】学pwn日记(堆结构学习)

这个0x111其实是0x100+0x10+0x1得来的

0x10就是prev size+size的大小

0x1其实是size最后的3bit中的P=1

然后我们再来看ptr这个指针,我们刚刚说了ptr这个malloc返回的指针处在size之后的data段开头

【pwn】学pwn日记(堆结构学习)

我们申请的0x100大小的heap的addr是0x55555555559290,而我们ptr这个指针指向的地址是0x555555552a0,我们发现其实是heap的addr+0x10,也就是在pre size和size之后,印证了我们刚刚的结论

再来一个小插曲:

这个插曲是关于prev size的覆用

首先说一个结论,我们申请0xn0大小的空间和申请0xn8大小的空间,堆管理器给我们的内存是一样的,为什么呢?

【pwn】学pwn日记(堆结构学习)

因为prev size的作用是记录相邻的低地址的free chunk的大小,而如果prev size上面是一个malloced chunk,那么prev size就没有作用了,这个时候堆管理器体现出了节省内存的思想,将prev size进行覆写,从而获得0x8的内存大小

6、bin和链表

  • bin是什么?在英文中,bin是垃圾桶的意思,就如字面意思一样,bin是管理堆的回收。

  • bin管理arena中空闲的chunk的结构,并且以数组的形式存在,数组元素为相应大小的chunk链表的链表头。bin存在于arena的malloc_state中

  • 在chunk被释放的时候,glibc会将它们重新组织起来,构成不同的bin链表。当用户再次申请的时候,就会从其中寻找合适的chunk返回给用户。

  • 不同大小区间的chunk被划分到不同的bin中,再加上一种特殊的fast bin,一共是4种:fast bin、small bin、large bin、unsorted bin

  • 关于chunk中的链表有两种:

    1. 物理链表
    2. 逻辑链表
    • 物理链表就是每一个prev size记录了前面一个free chunk的大小,从而可以指向上一个prev size,形成了一个物理链表。这种链表是物理层面上的相邻
    • 而逻辑链表不是物理层面的互相连在一起,而是通过chunk中的指针来连接,比如fastbin就是由fd连到下一个prev size,然后按照这样的结构延续下去的一个结构。逻辑链表就是将同类型的chunk通过指针连接在一起。
  • 在bin中我们一般都是讨论逻辑链表

  • fastbins如下图所示,我们可以从中看出逻辑链表的结构特点

【pwn】学pwn日记(堆结构学习)

  • 逻辑链表的好处是什么呢?如果我们想要再free之后重新申请一块区域,这个时候在bins中就会寻找适配的bin来还原内存空间。而这些空间恰好是被逻辑链表连在一起的,这样就可以提供刚好合适的内存空间给用户,不会造成浪费

  • bin有两种结构:双向链表和单向链表,除了fastbin是单向链表,其余的bin都是双向链表

  • 我们的bin中有两个bin数组:

    1. fastbinsY:装有NFASTBINS个fast bin,NFASTBINS一般是7
    2. bins:是一个bin数组,一共有126个bin,按顺序分别是:
      • bin[1]是unsorted bin
      • bin[2]~bin[63]是small bin
      • bin[64]~bin[126]是large bin

1.fastbin

  • 除了fastbin的结构是单项链表,其他的bin都是双向链表。因为fastbin只有一个fd指针。
  • fastbin的工作方式是后进先出。
  • fastbin的P永远是1,因为就如同字面的fast意思一样,为了更快的释放和分配。这样就避免了fastbin被合并。也就是这样让它有了fast的属性
  • 那么我们为什么需要fastbin这种东西呢?
  • 因为fastbin的范围是从最小的0x20开始,有7个,也就是到0x80。我们的程序经常性的频繁的会申请一些小空间,如果一些很小的空间都需要被堆管理器频繁的接手,那就会变得非常麻烦,并且消耗资源。这就犹如我们在银行频繁的存入5块钱,然后下一秒又取出3块钱,又存1块钱,然后又取出10块钱。为了避免这样的情况出现,就有了fastbin的单链表。
  • 并且这也是为什么fastbin的工作方式是LIFO(后进先出),因为需要快速的管理小的内存空间。也是为什么P永远为1。
  • fastbin管理16、24、32、40、48、56、64bytes的free chunks(32位下默认)
  • 按照fastbinsY数组里从小到大的顺序,序号为0的fast bin中容纳的chunk大小为4*SIZE_SZ字节,随着序号增加,所容纳的chunk递增2*SIZE_SZ字节。
  • 【pwn】学pwn日记(堆结构学习)
  • 这里有一个小插曲:为什么fastbins中有bk指针?
    • 因为fastbin管理16~64bytes的free chunks,而smallbin管理16~504bytes的free chunks(32位下)
    • 并且如果unsotred bin在自己遍历的过程中,可能会将fastbin变为smallbin。
    • 在fastbin中,bk这个域没有任何用处

2.unsorted bin

在实践中,一个被释放的chunk常常很快就会被重新使用,所以将其先放入unsorted bin中,可以加快分配的速度。

  • unsorted bin仅仅占用一个,也就没有bins的说法,所以是bin[1]
  • unsorted bin管理刚刚释放还未分类的chunk(这也就是为什么叫unsorted bin)
  • 我们可以unsorted bin视为空闲的chunk回归其所属bin之前的缓冲区
  • 然后unsorted bin因为仅仅是单独的一个,所以结构如下图
  • 【pwn】学pwn日记(堆结构学习)
  • 当malloc了一个在large bin范围之内的chunk,并且在unsorted bin中没有找到满足用户要求的空间大小的free chunk,这个时候unsorted bin就会开始遍历进行可以合并的chunk进行合并(物理结构上相邻的两个或者多个free chunk),合并完成了就会把合并完成后从bin放入相对应的bins中

3.small bin

small bin使用频率介于fast bin和large bin之间。刚刚也提到了在unsorted bin 遍历的时候,fast bin可以变为small bin。

  • bin[2]~bin[63]
  • 62个循环双向链表
  • 先进先出(FIFO)的工作特性
  • 管理16、24、32、40、....、504 bytes的free chunks(32位下)
  • 每个链表中存储的chunk大小都一样
  • 【pwn】学pwn日记(堆结构学习)

4.large bin

  • bin[64]~bin[126]

  • 63个循环双向链表

  • 先进先出(FIFO)的工作特性

  • 管理大于504 bytes的free chunks(32位下)

  • large bin被分为了6组,每组bin能够容纳的chunk按顺序排成了等差数列,如下图所示

  • 【pwn】学pwn日记(堆结构学习)

  • large bin为了加快检索速度,fd_nextsize和bk_nextsize指针用于指向第一个与自己不同大小的chunk。所以只有在加入了大小不同的chunk时,这两个指针才会被修改。

内存申请和释放

这一块等到学到了再补上吧

上一篇:C. The Football Season (枚举) ( Codeforces Round #592 (Div. 2) )


下一篇:消除键盘缓冲区中多余输入数据