深入理解Glibc堆的实现（上）

在阅读本文之前，建议大家先读一下 这篇文章 ，其中讨论了一个过时的但很重要的内存损坏漏洞，我将之称为“堆栈缓冲区溢出”。除此之外，我还假设如果我作为攻击者如何利用这些漏洞来控制远程程序并使其运行恶意shellcode。

在测试中，我发现如果要使用一种称为“stack canaries”的漏洞缓解措施，则攻击者则难以利用这些堆栈缓冲区溢出漏洞，除非，他们使用额外的漏洞才能利用它们。

Stack Canaries是已知的放置在缓冲器和控制数据之间的一个随机值，当缓冲器溢出时，最先被破坏的就是这个值。

当开发人员使用各种基于堆栈的漏洞缓解机制时，攻击者通常会使用与堆相关的漏洞(如Use-after-free漏洞、double free漏洞和堆溢出漏洞)来构建漏洞。这些基于堆的漏洞比基于堆栈的漏洞更难理解，因为针对基于堆的漏洞的攻击技术可能非常依赖于堆分配器的内部实现的实际工作方式。

Use-after-free漏洞（简称UaF漏洞）是当前最流行的高危内存破坏漏洞。目前针对UaF漏洞的检测工作并不完善，原因是UaF漏洞产生的特征是分配内存、释放内存、使用已释放的内存并按顺序出现，而这3种事件可能出现在程序的任何位置，需要跟踪较长的执行序列并搜索潜在的危险事件序列才能检测到该漏洞，这很大程度上提高了检测的难度。

Double Free其实就是同一个指针free两次。虽然一般把它叫做double free。其实只要是free一个指向堆内存的指针都有可能产生可以利用的漏洞。double free的原理其实和堆溢出的原理差不多，都是通过unlink这个双向链表删除的宏来利用的。只是double free需要由自己来伪造整个chunk并且欺骗操作系统。

因此，在讨论利用基于堆的漏洞之前，我将先讨论堆的工作方式。首先，我会介绍一些概念，并讨论如何创建新的堆块。其次，我将深入探讨如何释放和回收这些块。

堆的工作方式会根据实现的平台不同，而存在不同的堆实现。例如，Google Chrome的PartitionAlloc与FreeBSD中使用的jemalloc堆分配器非常不同。Linux中默认的glibc堆实现与堆在Windows中的工作方式也有很大不同。因此，我将主要关注glibc堆分配器，即在 Linux 设备上默认运行的C/ c++程序中，堆分配是如何工作的。这个堆派生自ptmalloc堆实现，而它实际上又是从更老的dlmalloc（Doug Lea malloc）内存分配器派生而来的。

堆是什么，它的用途是什么?

堆被C和c++程序员用来在程序执行期间手动分配新的进程内存区域，程序员要求堆管理器通过调用堆函数(如malloc)来分配这些内存区域。然后，程序员可以使用、修改或引用这些分配的内存区域，直到 程序员 不再需要它，并通过调用free将分配返回给堆管理器为止。

下面是一个C程序如何在堆上分配、使用和释放结构的示例:

typedef struct 
{
    int field1;
    char* field2;
} SomeStruct;
int main()
{
    SomeStruct* myObject = (SomeStruct*)malloc(sizeof(SomeStruct));
    if(myObject != NULL)
    {
        myObject->field1 = 1234;
        myObject->field2 = “Hello World!”;
        do_stuff(myObject);
free(myObject);
    }
    return 0;
}

只要程序员遵循一些简单的规则，堆管理器就可以确保每个活动分配不会相互重叠，这也是大多数C和c++程序依赖堆的一个原因。

下图列出了程序员在使用堆时必须遵循的一些基本规则，以及程序员违反这些规则会发生的一些漏洞类别。在后面的文章中，我将更详细地讨论所有这些与堆相关的漏洞。

当然，malloc和free并不是C和c++程序员与堆交互的唯一方式。c++开发人员常常通过c++操作符new和new[]来分配内存。这些分配必须使用相应的c++操作符delete和delete[]来释放，而不是使用free。程序员还可以通过与malloc兼容的堆函数(如calloc、realloc和memalign)分配内存，这些堆函数和malloc一样，最终通过free释放。

为了简单起见，我将首先讨论malloc和free。一旦理解了这两个函数，其他大多数堆函数就会变得非常容易理解。

下面是一个c++程序如何在堆上分配、使用和释放结构的示例:

class SomeClass
{
public:
    int field1;
    char* field2;
};
int main()
{
    SomeClass* myObject = new SomeClass();
    myObject->field1 = 1234;
    myObject->field2 = “Hello World!”;
    do_stuff(myObject);
    delete myObject;
    return 0;
}

内存块和块分配策略

假设程序员通过malloc请求10个字节的内存，为了满足这个请求，堆管理器需要做的不仅仅是找到程序员可以写入的随机的10字节区域，它还需要存储关于分配的元数据，此元数据会与程序员可以使用的10字节区域一起被存储。

堆管理器还需要确保分配在32位系统上是8字节对齐的，或者在64位系统上是16字节对齐的。如果程序员只想存储文本字符串或字节数组之类的数据，那么对齐就不重要了。但是如果程序员打算使用分配来存储更复杂的数据结构，那么对齐会对程序的正确性和性能产生很大的影响。由于malloc无法知道程序员将在分配中存储什么，因此堆管理器必须默认确保所有分配都是对齐的。

此分配元数据会和对齐填充字节与malloc将返回给程序员的内存区域一起被存储，出于这个原因，堆管理器在内部分配的内存“块”比程序员最初要求的略大。当程序员要求10个字节的内存时，堆管理器会发现或创建一个新的内存块，该内存块足以存储10个字节的空间以及元数据和对齐填充字节。然后，堆管理器将此块标记为“已分配”，并返回一个指向块内对齐的10字节“用户数据”区域的指针。此时，程序员将该区域视为malloc调用的返回值。

块分配的基本策 略

那么堆管理器如何在内部分配这些块呢?

首先，让我们看看分配小bin内存的策略，分配小bin内存是堆管理器的主要工作。我将在下面更详细的解释这些步骤，一旦我们完成了这些步骤，就可以查看大规模分配的情况。

分配小bin内存的策略是这样的：如果存在先前释放的内存块，并且该块大到足以为请求提供服务，则堆管理器将使用该释放的块进行新分配。否则，如果堆顶部有可用空间，堆管理器将从可用空间中分配一个新块并使用它。还有一种情况就是，堆管理器将要求内核向堆的末尾添加新内存，然后从这个新分配的空间分配一个新块。如果所有这些策略都失败，分配将无法得到服务，malloc将返回NULL。

从空闲块分配

从概念上讲，分配先前释放的块非常简单。当内存被发送回空闲块时，堆管理器会在一系列称为“bin”的不同链表中跟踪这些已释放的块。当发出分配请求时，堆管理器会搜索那些bin，以寻找足够大的空闲块来满足请求。如果找到一个块，它可以从bin中删除该块，将其标记为“已分配”，然后将指向该块的“用户数据”区域的指针作为malloc的返回值返回给程序员。

出于性能原因，有几种不同类型的bin，即快速bin、未排序bin、小bin、大bin和每线程tcache机制。

从堆的顶部分配

如果没有可用的空闲块可以为分配请求提供服务，则堆管理器必须从头开始构造新的块。为此，堆管理器首先查看堆末尾的空闲空间（有时称为“顶部块”或“剩余块”），以查看是否有足够的空间。如果存在，则堆管理器将从该可用空间中生成一个新的块。

在堆的顶部请求内核提供更多内存

一旦堆顶部的可用空间用完，堆管理器将不得不要求内核向堆的末尾添加更多内存。

在初始堆上，堆管理器要求内核通过调用sbrk在堆的末尾分配更多内存。在大多数基于Linux的系统上，这个函数在内部使用一个名为“brk”的系统调用。这个名称最初的意思是“更改程序中断位置”，不过说法太复杂，即它在程序加载到内存之后向该区域添加了更多内存。因为这是堆管理器创建初始堆的位置，所以这个系统调用的作用是在程序初始堆的末尾分配更多内存。

最终，使用sbrk扩展堆会失败。因为堆最终会变得非常大，以至于进一步扩展会导致它与进程地址空间中的其他内容发生冲突，比如内存映射、共享库或线程的堆栈区域。一旦发生这种情况，堆管理器将使用对mmap的调用将新的非连续内存附加到初始程序堆。

如果mmap也失败，那么进程就不能分配更多内存，malloc返回NULL。

通过MMAP进行堆外（OFF-HEAP）分配

非常大的分配请求会在堆管理器中得到特殊处理。这些大块使用对mmap的直接调用在堆外分配，并且使用块元数据中的标记来标记该事实。当这些巨大的分配稍后通过对free的调用返回给堆管理器时，堆管理器通过munmap将整个mmaped区域释放回系统。

默认情况下，这个阈值在32位系统上最小为128KB，最大为512KB，在64位系统上是32MB，如果堆管理器检测到这些大型分配正在被临时使用，则此阈值也会动态增加。

arena

arena的引进是为了解决多线程内存分配竞争的问题，在多线程应用程序中，堆管理器需要保护内部堆数据结构免受可能导致程序崩溃的竞争条件的影响。在ptmalloc2之前，堆管理器通过在每个堆操作之前简单地使用一个全局互斥锁来实现这一点，以确保在任何给定时间只有一个线程可以与堆交互。

尽管此策略有效，但堆分配器的使用率和性能都非常高，因此会导致使用大量线程的应用程序出现严重的性能问题。为此，ptmalloc2堆分配器引入了“arena”的概念。每个arena本质上是一个完全不同的堆，它完全独立地管理自己的块分配和空闲bin。每个arena仍然使用互斥锁序列化对其内部数据结构进行访问，但是只要线程与不同的arena交互，就可以安全地执行堆操作，而不会彼此冲突。

程序的初始(“main”)arena只包含我们已经看到的堆，对于单线程应用程序，这是堆管理器将使用的唯一arena。但是，当新线程加入进程时，堆管理器会分配并将辅助arena附加到每个新线程，以减少当线程试图执行malloc和free之类的堆操作时，进行不必要的等待。

对于每个加入进程的新线程，堆管理器都会尝试找到一个对应的空闲的arena，并将其附加到该线程。一旦所有可用的arena都被其他线程使用，堆管理器就会创建一个新的arena， 32位进程中的arena数量最多为2x cpu-cores，64位进程中的arena数量最多为8x cpu-core。一旦达到这个限制，堆管理器就会放弃，因为多个线程不得共享一个arena，且执行堆操作时需要其中一个线程等待另一个线程。

子堆

虽然子堆的工作方式与初始程序堆基本相同，但还是有两个主要区别。回想一下，初始堆位于程序加载到内存之后的位置，并由sbrk动态扩展。相反，每个子堆都使用mmap定位到内存中，堆管理器使用mprotect手动模拟子堆的增长。

当堆管理器想要创建子堆时，它首先要求内核保留一个内存区域，这个内存区域可以通过调用mmap增长为子堆。保留此区域不会直接将内存分配到子堆中，它只是要求内核不要在这个区域内分配线程堆栈、mmap区域和其他分配。

默认情况下，子堆的最大大小在32位进程上是1MB，在64位系统上是64MB。

这是通过向mmap请求标记为PROT_NONE的页面来实现的，该页面充当内核的提示，它只需要为该区域保留地址范围即可，还不需要内核为它附加内存。

使用sbrk增加初始堆的位置时，堆管理器会通过手动调用mprotect将区域中的页面从PROT_NONE更改为PROT_READ | PROT_WRITE，模拟将子堆“增长”到这个保留地址范围。这会导致内核将物理内存附加到这些地址，这实际上会导致子堆缓慢增长，直到整个mmap区域被填满。一旦整个子空间耗尽，arena就会分配另一个子堆。这就允许辅助arena几乎无限地增长，只有当内核耗尽内存或进程耗尽地址空间时才会最终停止。

注意：初始(“main”)arena只包含主堆，主堆位于程序二进制加载到内存的位置之后，并使用sbrk进行扩展。这是用于单线程应用程序的唯一arena，在多线程应用程序中，新线程被分配到辅助arena。使用arenas可以降低线程在执行堆操作之前需要等待互斥对象的可能性，从而加快程序的速度。与主arena不同，这些辅助arena从一个或多个子堆分配块，其在内存中的位置首先使用mmap建立，并通过使用mprotect增长。

块元数据

现在我已经介绍了分配块的所有方法，块不仅包含作为malloc返回值提供给程序员的“用户数据”区域，还包含元数据。但是这个块元数据记录了什么，它又位于何处?

因为堆管理器源代码将一个块末尾的元数据与下一个块开头的元数据相结合，并且存在或使用了几个元数据字段。所以，块元数据的位置具体取决于关于大块的各种特征。

本文，我们只看活动分配，它有一个size_t标头， size_t是表示长度(尺寸)的类型,这个类型是由 typedef unsigned int size_t; 定义的,一般用于保存一些长度信息,比如数组的长度、字符串的长度等。它位于给程序员的“用户数据”区域后面。这个字段(源代码调用mchunk_size)是在malloc期间编写的，之后由free决定如何处理分配的释放。

size_t值在32位系统上是4字节的整数，在64位系统上是8字节的整数。

mchunk_size存储了4条信息:块大小，以及称为“A”、“M”和“P”的三个位。这些都可以存储在相同的size_t字段中，因为块大小总是8字节对齐的或者在64位上是16字节对齐的，因此块大小的最低三个位总是零。

“A”标志用于告诉堆管理器该块是属于辅助arena，还是主arena。在空闲期间，堆管理器仅被赋予指向程序员想要释放的分配的指针，并且堆管理器需要确定指针所在的那个域。如果在块的元数据中设置了A标志，堆管理器必须搜索每个arena，并查看指针是否位于该arena的任何子堆中。如果未设置该标志，则堆管理器可能会中断搜索，因为它知道块就来自初始arena。

“M”标志用于指示块是通过mmap在堆外分配的巨大分配，当这个分配最终被传回free时，堆管理器会立即通过munmap将整个块返回给操作系统，而不是试图回收它。出于这个原因，释放的块永远不会设置此标志。

“P”标志令人困惑，因为它实际上属于前一个块。它表示前面的块是一个空闲块。这意味着，当这个块被释放时，它可以安全地连接到前一个块，从而创建一个更大的空闲块。

接下来，我将更详细地讨论如何将这些空闲块“合并”在一起，并讨论如何使用不同类型的“bin”分配和回收这些块。在这之后，我们还会研究一些不同类别的堆漏洞，以及攻击者如何利用这些漏洞远程控制易受攻击的程序。