堆(随便写一写,当笔记用)

开始学习堆的知识,便整这个博客当笔记用用,将平时视频里看到的东西记录一下。

arena

内存分配区,可以理解为堆管理器所持有的内存池

操作系统 –> 堆管理器 –> 用户

物理内存 –> arena –> 可用内存

堆管理器与用户的内存交易发生于arena中,可以理解为堆管理器向操作系统批发来的有冗余的内存库存

相当于使用操作系统有的是物理内存,堆管理器只在操作系统与用户之间,用来使用户利用堆的一个东西,

在用户使用堆管理器开始利用堆时,堆管理器便会将物理内存中的可用片段放入arena中,在收到堆管理器的所需大小,便将其中的物理内存转换为可用内存供用户使用。arena中的内存的大小是大于用户所需要的内存的。

如果在C语言中使用malloc这个函数如:

1
void* ptr = malloc(0x100)

当执行完这行代码后堆管理器便会在arena中找到一块大小为0x100的区域作为分配给用户的堆的区域

同时我们所获得这个ptr是个指针,指向是通过malloc()后得到的一块内存区域chunk的中间。

每次 malloc 申请得到的内存指针,其实指向 user data 的起始处

chunk

用户申请内存的单位,也是堆管理器管理内存的基本单位

malloc()返回的指针指向一个chunk的数据区域

image-20240409213854456

chunk相当于一段内存区域的状态,在不同的时候有不同的chunk,如下

image-20240409215156595

像在C语言中执行

1
void* ptr = malloc(0x100)

完这行代码后对于malloc分配的0x100便是chunk,而此时的chunk状态便是malloc chunk,而再执行

1
free(ptr)

将这段内存释放,那这段内存区域也就是chunk便会成为 free chunk的状态。这段内存区域并不会消失

相当于用户在通过堆管理器获得一段内存空间作为堆,在使用完成之后,用free将其释放。

这段内存区域,在malloc之后从原本的物理内存变为malloc chunk,以供使用,在free后并不会直接还原为物理内存,而是继续存放在堆管理器中以便下次使用,为了方便的存放,这段内存区域便会变为free chunk的状态存放在堆管理器中。(也是为了节约时间,内存还为物理内存需要进行系统调用)

先来看看malloc chunk的结构

分为3个部分,prev siz,size和剩下的存放数据的地段

image-20240410203227873

在理论上size的最后3个位置应该都是,并且是固定的0,无论这个chunk怎么变,都应该是0,于是这3个位置便被利用起来,用分别存放AMP。

在看看free chunk的结构

对于free chunk他就是之前那个malloc chunk在通过free函数后将其释放后的堆管理器,其构造与malloc chunk的差别在于在size与数据段中间多了fd和bk这部分。其他的相同(free chunk有很多种,这只是其中一种)

先来看看在chunk中共有的P位置所存放的数据及其含义。

这里的p存放的是用来检测这一个chunk的上一个chunk的含义,所返回的数据。

如果检测到这个chunk的上一个是一个malloc chunk和其他的数据,变回返回一个1,存放在这个位置,

如果检测到这个chunk的上一个是一个free chunk的话变回返回一格0,存放在这位置

而当这个p的值为0,便可以知道当前这个chunk以及上面的chunk都是free chunk,此时这两个chunk变回合并为同一个free chunk,将下面的chunk从管理器中去除,整体变为上一个chunk的数据段,上一个chunk中的size则扩大到上下两个chunk合并后的整个chunk的大小。

image-20240410212049191

free chunk出了这种结构之外还有两种另外的结构

image-20240410214307841

chunk在代码段的实现

image-20240416163709790

理论上来说所有的chunk的出现都需要这几行代码的经过产生相应的区域,但由于程序为了节约时间对于不同的时间与不同状态的chunk其结构并不相同,并不是全部都包含由这些结构。不同的chunk有不同的结构,在上文中有所显示。

在chunk中,其存储数据的方式和栈的存储方式相反,堆的存储方式为由高地址向低地址不断存储的图,但在堆的chunk中,其结构最上方prev size为最低的地址然后依次向下增大,输入的数据在数据段中从低到高不断增大的地址存放

在前文中得到的ptr指针所指向的便是控制字段size往下的数据段的开头,方便数据的直接存放。

在一个申请的有堆的程序中,在执行完malloc后的各各段的地址如下

image-20240416170351224

蓝色字体便是程序中的堆的所在地址和长度,其位置在data段的正上方,紧邻这data段中的的bss区(前提是其堆的大小不算太大)

在程序中如果我们申请了一块长度为0x100的堆,那当程序执行完malloc函数后我们所得到的chunk的大小并不就是0x100,一般是0x111,这多出来的0x11包括8字节的prev size和size这两个控制字段,已经一个在size的末尾的p(在上文中有介绍)。

因此指向堆的指针所指向的并不是chunk的开头,而是chunk中的数据段的开头

image-20240416211427476

prev size的复用

在chunk中的开头的第一个prev size的控制字节是用来存放这个chunk的上面一个free chunk的大小的,它有且只有这一个作用。在一个程序中如果一开始申请的是0x20的长度的堆,那程序中会分配相应大小的chunk用来使用,然后在使用完这个chunk后将其释放,这个chunk便回成为free chunk存放在堆管理器中,方便以后的使用。

在这之后如果我们在程序中再次申请一个堆,程序会先在已有的chunk中寻找有没有适合的free chunk,然后将这个free chunk变为能使用的chunk用于使用,如果此时我们向程序申请一个大小为0x28的长度的堆,似乎之前我们申请的那个堆长度不够不能再使用了。但实际上,在程序中所有的chunk是放在一起的,也正因此才回有prev size的使用。当程序发现现在我们需要的chunk的大小与之前那个已经有的chunk只差一个字段,刚好是prev size等一个控制字段的大小,然后当我们把之前申请的那个chunk从free chunk转化为malloc chunk后,后发现一个问题,此时下一个chunk的开头prev size没有用了,他的上面不是free chunk 然后他刚好在上一个chunk的数据段的下面,而此时的数据段刚好差这一个长度,因此程序会将他直接转化为上一个chunk的数据段,以满足其的使用。这边是prev size的复用。

简单来说便是,在程序中一开始申请了长度为x的堆,后来把他释放了,之后在申请一个长度为x到x+8的堆,程序会将之前申请的那个chunk再次使用,两次使用的chunk会是同一个chunk

物理链表

在chunk中第一个控制字段prev size用于存放上一个chunk的长度,再结合自身的位置便回,可以知道上一个chunk的初始位置,一个chunk知道上一个chunk的初始地址,构成物理链表

bin中的逻辑链表

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

bin的结构是一个数组,有一个又一个的指针构成,每一个指针都指向一个相应大小的free chunk的初始位置,在被指向的free chunk中有一个fd控制字段,这个控制字段也存放的是一个指针,执向的是与这个chunk大小相同的的chunk初始位置。在bin作为最开始的指针指向相应大小的chunk,fd在指向相同大小的chunk,这个便是逻辑链表,如图(释放的顺序的从下往上释放,最下面的那个fd段为0的chunk为第一个释放的chunk)

这个bin的地址中的指向是刚刚释放的chunk,如最下面的chunk在释放后,bin的指向就这是他,等着后面的chunk在次被释放后bin的指向便会改变为新的释放的chunk。

image-20240418143002441

用指针的方式将相同大小的chunk连接起来,存放在bin中方便之后的寻找

在bin中还有一种双向链表,将相同的大小的的chunk互相链接起来,以便使用,其基本结构如下,通过两个bin指针与chunk中fd,bk的不断指向构成,其中在使用中,为依次使用,从靠近bin的顺序被依次调用。

image-20240411162059021

image-20240418151335033

LIFO指其中的chunk的调用和栈上的调用方式一样,先进先出。

管理的free chunk在64位的程序下位32位的程序的两倍的大小

image-20240418152210990

image-20240418152258402

堆的再分配机制

在程序中的有关与堆的分配机制中,在后期有关于新的堆的寻找的中会先去寻找在之前生成chunk得程度够不够当前的malloc所需的长度,只要在之前的malloc的有过长度长出当前需要的malloc的长度,并且之前的那个chunk已经被free了,那程序便会直接将之前的那个free chunk 在现在的malloc中将其转化为可有的chunk,如果之前的那个chunk的长度超过当前的chunk这需要的长度,程序依然会将这个free chunk转化为新的chunk,但是只会使用需要的长度,对于之前那个chunk里的多余的长度,则会在分配之后自动生成一个新的free chunk。prev size和size等控制字段会在其中自动填充形成一个新的free chunk。

**use after free **

使用一个低权限的指针,指向一块存放重要数据的地方,使得可以利用这个非法的指针,对所指向的重要数据进行修改。

在很多情况下我们会使用char* ptr = malloc(0x100)这个命令用于申请一个堆块,这样ptr便会返回一个指向chunk中数据区的指针,我们便可以通过这个指针向这个chunk的数据区中读入数据,当我们不在需要这个堆时,便可以使用free(ptr)这个命令将我们刚刚申请这个堆块释放掉,但是此时有一个必须要注意的一点是,虽然此时之前的chunk已经被free掉了,但是ptr这个指针并没有被释放,它以然指向的是之前的那个chunk的数据段,虽然由于此时的free chunk,并不能被利用,但在后面如果我们再次申请一个长度小于或等于之前的那个堆的长度时,更具堆的再分配机制,程序会将之前的那个chunk从free的状态转化为能正常使用的状态,那么由于在之前分配的堆的指针并没有被我们清零,那个指针执向着之前的那个chunk 的数据区,在这里将之前那个free chunk转化为能用的chunk,由于ptr指向的位置不变,依然是这个chunk的数据区,故在这里prt这个指针也同时执向了这个新的堆的数据区,并拥有对其读写的功能。在有的题目中我们可能没有操作新的这个指针的能力但我们可以通过操作之前那个没有被清理的指针对当下这个对于这个指针进行修改。

双重释放漏洞

对同一个堆块进行两次释放,导致在再申请时,两个不同的指针指向了同一个堆块。

在一个程序中先申请了3个堆块,A·B·C,大小都为8,我们在使用之后将其free掉,但是在free的过程中时,由于这些堆块的大小为8,故在被free调后会被放入到fast bin中,在这里这些堆的排列方式与栈上数据的排列方式相反,先进先出,后进后出。我们在使用完A,B,C这中3个堆块后,先free(A),此时A这个堆块便会被放入fast bin中,然后在free(B),B这个堆块变会被放入A堆块的下方,然后再我们在free(A),虽然我们在之前已经free过了,但这里程序并不会报错而是继续执行下去,导致在fast bin中出现一下情况

image-20240512150800024

在fast bin有两个A堆块(这里并不能直接对A堆块连续free两次,中间还是要加上一个其他堆块的),由之前的关于堆的分配,我们这里如果在向程序申请3个堆块并且大小相同的情况下,程序会直接从fast bin中分配出去,这里假设我们再次申请,D,E,F,3个大小都为8的堆块。根据fast bin中后进后出的顺序,程序会从上往下对fast bin在分配,于是问题便出现了,在fast bin中有两个A堆块,但是程序不知道,于是程序便会,将这段A地址进行两次分配。导致D和F分配的堆块都是之前的A的地址,这两个指针也同时指向这个地址,使得我们可以使用其中一个对宁外一个指针的内容进行修改,从而到达我们漏洞的使用。

使用这种方式攻击栈

在之前的第二次对堆块的申请中,如果我们申请两次将fast bin下面的A和B申请掉,导致fast bin中还有一个A堆块,但是由于我们之前已经将A堆块申请为D的堆块,那么此时fast bin中的指针和D这个指针会同时指向原本的A的堆块的地址,而我们通过D指针对A进行修改时,会同时对fast bin指向的地址一起修改。

由于在fast bin中堆块的链接是通过其中的fd控制字段指向下一个堆块的起始地址从而实现链接的。

这里虽然fast bin和D指向的是同一块地址区域,但是由于D指向的是一块能使用的chunk,而fast bin指向的是一块free chunk,这两者的区别就在于free chunk多了一个fd的控制字段,在fast bin中用于指向下一个free chunk的起始地址。

image-20240512165122150

但是在D中的chunk由于不是free chunk,没有fd字段,程序为了最大的利用率于是变会在将A堆块分配给D是将fd字段一同加入到数据段中,因此我们在通过D指针对A堆块进行修改时,最先输入的字节的内容在fast bin指向的A堆块中会自动被识别为fd的值,作为指向下一个free chunk的指针。这里D指针指向的和fast bin中的A堆块是同一个地址,故我们在使用D指针修改时能同时修给fast bin中的值。

这里由于程序不会对我们输入fd进行检查,于是我们便可以对我们输入到A堆块的最开始的字节的数据做手脚,从而是fast bin中的链接的free chunk的值再多一个,而这多出来的便是我们自行输入修改的。

假设我们需要对栈上的某一块地址进行修改,我们便可以先使用D指针向A堆块输入要修改的栈的地址的上两个字节的地址,然后在fast bin中A堆块的便会将fd字段也修改成那个栈上的地址。导致程序误以为在fast bin中多了一个free chunk,然后当我们再向程序申请堆块时,如果申请的长度与A的大小相同,程序变回将fast bin中的A再次分配出去,然后我们再一次申请堆块时,由于fast bin中A堆块已经分配出去,而原本A堆块中fd字段指向的是栈上的地址,于是这一次对堆的申请,程序会将fast bin中最近是栈的地址空间当做可用的free chunk,从而分配出去。以供我们进行修改,但是由于这里程序依然是将栈上的地址作为堆块分配出去,然后fd这个字段指向的地址是堆块的开头地址,因此栈上的地址依然会有两个字节被程序认为是chunk的prev size和size字段,而不能使用,只有两个字节下面的地址才是数据段,才能被我们所修改。因此我们在对A堆块fd修改时,要输入的是要修改的栈上地址的上面两个字节的地址才能在后面malloc到栈上地址,修改时修改到我们需要的数据。

image-20240512173005244

大致的结构如上图,通过对A中的fd的修改,使得fast bin中能指向栈上地址,然后通过对fast bin中的堆的申请,从而申请到栈上的地址做为堆块用于使用,对这个堆块修改,从而间接修改栈上的内容。

house_of_force

通过堆溢出,将top chunk的大小标记为整个地址空间。然后在通过malloc到我们需要修改的地址空间,再此malloc使程序将我们需要修改的地址空间当做chunk分配给我们,然后修改。

top chunk

  • 概念:当一个chunk处于一个arena的最顶部(即最高内存地址处)的时候,就称之为top chunk。
  • 作用:该chunk并*不属于任何**bin,而是在系统当前的所有free chunk(无论那种bin)都无法满足用户请求的内存大小的时候,将此chunk当做一个应急消防员,分配给用户使用。
  • 分配的规则:如果top chunk的大小比用户请求的大小要大的话,就将该top chunk分作两部分:1)用户请求的chunk;2)剩余的部分成为新的top chunk。否则,就需要扩展heap或分配新的heap了——在main arena中通过sbrk扩展heap,而在thread arena中通过mmap分配新的heap。

一般来说当我们在程序中malloc一个堆块后,程序分配给我们的chunk其上方就是top chunk的区域,其中包含的就是空闲状态的chunk,方便下次需要chunk时能快速调用。这两个chunk在程序中分配图如下:

在chunk中数据的填入,与下图中的箭头方向相同,从下往上填入。

image-20240516164904604

如果在我们得到的这个chunk中有堆溢出漏洞的发生,那么我填入的数据便会一直向上填入,在填入的过程中便会将top chunk的原数据覆盖,由于在top chunk中不会对数据进行检查判断是否被篡改,因此当我们填入的数据将top chunk中的size值覆盖为程序整个地址空间大小(32位是4gb,64位是8gb)时,程序会认为整个地址空间都是top chunk,导致我们在下次malloc时,程序在top chunk中寻找是否满足大小时,由于top chunk的size已经被我们修改为程序的整个地址空间了,于是程序会认为整个地址空间都是能被分配的chunk,于是我们在第二次malloc时无论需要的chunk大小是多少程序都会在分配给我们。

于是我们便可以直接从原本的top chunk的地址malloc一个新的chunk,并使这个新的chunk长度为从top chunk的起始地址到我们需要修改的栈上地址的起始空间的前两个字节的长度(在下一次malloc中需要两个字节作为prev size和size,使得我们需要修改的地方能直接成为我们chunk中的数据段,从而直接修改),使得程序将这一段空间作为chunk分配给我们(主要是为了下一次malloc时能直接将要修改的地址分配给我们使用不用将中间的数据区别覆盖·,这个起到一个垫脚石的作用),然后再malloc一段空间,使得程序将栈上的空间作为chunk提供给我们使用。,我们向这个chunk输入数据,从而修改栈上的数据到达目的。

image-20240516172821078

如果我们要修改得时date段的数据,那便要malloc的长度将使一个负数(date段的数据在chunk的下方),由于我们在之前的覆盖中已经将top chunk中的size的大小表为整个地址空间,于是我们在malloc一个负数时,程序会将top chunk的起始地址向下移动这个负数的长度。然后我们再malloc一个正数时,程序便会从我们刚刚移动过的top chunk的头地址可是分配一个相应大小的chunk以供使用。

因此我们只在栈溢出后malloc一个负数,其大小就是从top chunk的起始地址到要修改的date段地址的下两个字节的距离的负数(两个字节作为下个chunk的前两个控制字段),然后再malloc一个正数的chunk,输入数据便可以达到我们的目的。

image-20240516175155536

有关于各个bin的chunk进入与分配结构

tcachebins:

先进后出,后进先出

image-20240620150551052

分配的时候将从chunk4开始分配依次分配到chunk1。

unsortedbin

先进先出,后进后出。

image-20240620150930731

分配的时候从chunk1开始依次分配到chunk4。(要注意这几个chunk如果大小相同,并且相临,那么进入到unsortedbin后会直接合并为一个大chunk,然后在要分配时直接切割这个大chunk)