分析对malloc单链表的新保护机制

 

0x00 绪论

2020年5月21日，Checkpoint Research发表了一篇文章，详细说明了对Malloc多个版本进行的一个安全修补及其影响，包括GLibC中所使用的Malloc。这个补丁试图修复用作bin数据结构的单链表存在的不安全因素。本文中，我将深入分析该安全修补的工作原理，及其对二进制漏洞利用的影响。我们将特别关注GLibC的Malloc中加入的修补，不过这种缓解措施的原理可以直接用于其他版本的Malloc（但具体实现要有所变动）。

 

0x01 GLibC Malloc

要理解本文其余部分，先要初步认识GLibC Malloc里的数据结构。本文只讲其中两种主要的数据结构：chunks和bins。

Chunks

Chunks是用户主要打交道的对象。chunk有两种主要状态：分配和空闲。下图展示一个空闲chunk：

第一个字段是前一个chunk的大小（prev_size），只在前面的chunk空闲时才用这个字段。第二个字段是chunk大小，包括chunk的数据部分大小和关于本chunk的一些元数据（大小字段的头3个位）。

在空闲chunk中，第三个字段用于存储指向其他空闲chunk的指针，这个字段称为前驱指针，或者叫Fd字段。第四个字段和第三个差不多，存的是后继指针，或者叫bk。Fd和bk指针在chunk被分配时是不用的，而是作为chunk的数据部分。对于本文，要知道的就是这些了。关于GLibC的细节，请见Sploitfun的出色文章。

Bins

GLibC中，bins是目前空闲的chunk的一个列表。所有bins都以某种链表结构存在。有几种不同的bins，其chunk大小和速度不同。在本文中，我们只需知道两种bins：fastbins和tcache。

tcache和fastbins都是空闲chunk的单链表，这表示Fd指针（chunk的第三个字段）指向bin中下一个空闲chunk。这两种bins都不使用bk指针。Fastbins和tcache还有很多差异，比如速度、安全检查等，但是在本文中，所需知道的就是这些。

 

0x02 单链表的安全问题

最早的unlink利用发布之初，人们在GLibC中加入了许多安全性和完整性检查，防止chunk破坏。其他bins（unsorted, small和large）用的是双链表，可以加入许多检查来确保chunk或bin没被破坏。但是，对于单链表，这些检查无法实现，这很遗憾，但是为什么不行呢？

一旦拥有覆盖单链表Fd指针的能力，就可以将该指针指向内存中的任意位置。用户调用Malloc时，这个伪造的chunk（包含我们写入的Fd指针地址）就会返回给用户。到此，因为指针指向任意位置，我们就可以写入那个地方。利用这个原语，就可以用多种方法达到代码执行，例如覆盖函数指针，或者在此之上创建其他原语。

 

0x03 安全更新

如上所述，Malloc中的单链表Fd指针容易被利用，对安全造成极大威胁。因此，Checkpoint Research决定对单链表加入新的安全保障。加入的措施可以归结为二：强制chunk对齐和指针修饰（pointer mangling）。以下讨论这二者。

强制chunk对齐

Malloc只分配以8字节（32位）或16字节（64位）为单位的chunks。因此，chunks只应以0x8（仅对于32位）或0x0结尾。新加入的安全检查验证给定chunk对齐到了预期的位置。下图展示了有效的chunk所能指向的位置。

这样一个简单的完整性检查限制了伪造chunk创建的位置，32位下减少了7个位置，64位下减少了15个位置。后文将会对其意义加以讨论。

指针修饰

这个修补大致来说就是fastbin和tcache的Fd指针加入了混淆，阻止没有地址泄露的利用和相对覆盖这两种方法。

指针修饰的公式如下：

| New_Ptr = (L >> 12) XOR P |，其中L是存储位置，P是fastbin/tcache的Fd指针。

Fd指针和存储位置被ASLR随机化，New_ptr因此也随机化了。

简单来说，这公式就是把指针的存储位置和Fd指针自身相异或。异或前，存储位置先被右移12位，这是因为存储位置和Fd指针的低12位是可以确定的。因此，想要对Fd指针的头12位随机化就必须移位。不然，相对覆盖仍然可以轻而易举地利用，因为末12位总是一样的。

解修饰（demangling）指针和上面的公式一模一样。修饰后的指针为P，存储位置L不变。异或后，原来的Fd指针就回来了。

这里对指针修饰做了概述。如果想了解更多，请见GLibC修补的作者的文章。

 

0x04 安全意义

以上对Malloc进行的两点改动对二进制漏洞利用的意义有轻有重，以下详细讨论其意义。

 

0x05 强制chunk对齐的意义

虽然改动看起来很少，但对Malloc来说却是巨大的一改。对于64位二进制文件，强制chunk对齐将把伪造chunk的位置限制为每16个地址中只有1个可用。这使得漏洞利用的难度增加了，尤其是在用户几乎不能控制程序中的值的那些二进制中。虽然利用漏洞还远远没到不可能的地步，但是每增加一点约束，利用就更复杂、更困难一点。在将来，要使伪造chunk可用，所有fastbin和tcache chunks都得进行对齐。

对__malloc_hook的fastbin attack

需要考虑的另一种情形是经典的函数指针（__malloc_hook）覆盖攻击，通过此攻击可以达到代码执行。从fastbin分配chunk时，chunk大小会经过验证，确保和fastbin大小相同。如果验证失败，Malloc就会中止。为了绕过这个安全检查，__malloc_hook附近的一个地址（__memalign_hook）以未对齐的方式被使用，来得到有效的chunk大小0x7F。这种攻击的例子可以看这里。加入对齐约束之后，这种攻击对fastbins就不再可行了。

 

0x06 指针修饰的意义

在Checkpoint Research的文章中，概述了指针修饰的主要目的：阻止部分覆盖和完全覆盖（在没有内存地址泄漏的情况下）。下面将予以讨论。

再见了，字节相对覆盖

在此修补出现之前，堆chunk指针的部分覆盖非常普遍。部分覆盖顾名思义就是：覆盖指针的一部分。

例如，把指针从0x80000080更改为0x80000040，我们就可以将堆chunk指向完全不同的位置。这个简单的技巧将使我们能够将chunk指向不同的位置，而无需知道堆上的实际地址！利用部分覆盖的另一个例子可以在不含地址泄露的House of Roman中看到，其中在3个不同的地方使用相对覆盖来实现远程代码执行。

现在，在没有堆泄漏的情况下，相对覆盖就需要暴力穷举才能完成了。在需要某个特定字节的情况下，该漏洞利用仅能以1/256的机会有效，即暴力穷举所有可能字节。由于增加了一层非确定性的计算，漏洞利用比以前的Malloc版本更难了。

在非堆位置进行tcache bin/fastbin攻击变得更困难

常见的一种攻击是将Fd指针设置为某函数指针的位置。这之所以可行，是因为用该函数指针分配chunk时，该指针可以被其他东西（例如system或one_gadget）覆盖。如前所述，__malloc_hook是一个很好的目标。覆盖函数指针攻击的一个例子如下：

1.泄露LibC地址，确定__malloc_hook的位置
2.将一个chunk释放到tcache bin中
3.覆盖tcache chunk的Fd指针，指向__malloc_hook
4.分配指向__malloc_hook的chunk
5.将__malloc_hook的值设为system或一个one_gadget，来达到代码执行

上述的攻击非常常见，只需一个LibC地址泄露即可进行。加入指针修饰后，这种攻击不再有效。想伪造指向GLibC的堆指针，必须在第3步覆盖指针前先修饰这个指针，这就大大增加了漏洞利用的难度。

此外，有了指针修饰，想在栈、.bss节或者在PLT/GOT里创建伪造chunk，就必须先泄露堆。这和上面所解释的LibC的情况一样，只是拓展到了其他非堆的位置。总的来说，这使得堆利用难度大大增加了。

泄露堆地址

一开始了解到指针修饰时，我以为fastbin和tcache指针泄露都无效了。但是，捣鼓了一会儿之后，我发现一种解修饰指针的方法，可以在堆泄露前进行。

 

0x07 堆泄露前解修饰（demangling）指针

回忆一下修饰和解修饰指针的算法：| New_Ptr = (L >> 12) XOR P |，其中L是存储位置，P是fastbin/tcache的Fd指针。

存储位置和Fd指针很可能是同样位数，而且高12位相同。当位置被移位之后，会进行如下计算：(P的最左边12位) XOR (0)。这泄露了指针的高12位。

比如，以存储位置0x987654987和Fd指针0x987654321为例。在下图中，存储位置已经被移位了。

从式中容易看出我们为什么泄露了指针的最左12位，因为这一部分是和0x0做的异或。

还可以观察到一件关键的事：Fd指针的set 1和存储位置的set 2是一样的！为什么这件事很关键呢？对于异或操作，如果两个值都已知，那第三个值就可以还原出来，因为异或是可逆的。现在我们知道输出和存储位置，就可以计算出Fd指针的相应位！只需将两个已知值异或即可。如下所示：

完整算法

将上述过程进行推广，就可以还原存储地址和经过修饰的指针的Fd指针。我们只做了一个假设：Fd指针和存储位置的高12位是相同的。上述过程可以继续直到指针末尾。算法如下：

1.首先，我们知道堆的头12位。由于移位，对第1轮迭代来说，存储位置指针的一些位就白送给我们了。后续的迭代则可以利用步骤3的输出。
2.其次，用这已知的位和修饰后指针的次高12位异或。输出的是Fd指针中的12位，见上图。
3.最后，如果Fd指针和存储位置指针的位不同，那么下一轮我们可以用两指针间的相对偏移把位加减回来，给出一组新的已知位值。
4.重复上述操作，直到走到修饰后指针的末尾。步骤1的已知位就是上一轮步骤3的输出。

结束时，输出就包含Fd指针和存储地址了。

注意：存储位置的末12位无法还原，因为它们在移位中丢失了。不过，因为这些位是确定性的，所以算法结束后可以加回来。要修饰Fd指针的话，末12位是没用的，移位会把它们移走。

修饰指针

用上述的算法，可以实时解修饰指针！不只是理论上可行，而且实际可用！我写了脚本来进行修饰和解修饰（包括无地址泄露的解修饰）。

脚本工具放在了mdulin2/mangle，可以去玩玩。repo里还有一份LibC和加载器（包含新的Malloc源码）、修改过的Malloc Playground，通过pwntools实现了友好的Python界面，还有一些如何绕过修饰缓解措施的例子。不仅有命令行界面，还有可导入的接口。我希望类似的东西可以默认加入到GEF和pwndbg中。

 

0x08 总结

总而言之，二进制漏洞利用还远远没到结束的那天。但是，这对于Malloc的安全性来说是一次大的改进。总体来看，有下列影响：

1.伪造chunks都必须对齐（减少了伪造chunk所能位于的位置数目）
2.相对覆盖现在需要大量的暴力穷举（很可能需要穷举一整个字节）才能进行
3.伪造Fd指针需要和存储位置进行修饰，这需要堆泄露
4.对Fd指针的堆泄露现在需要解修饰才能进行
5.非堆位置的伪造chunks现在需要进行堆泄露

希望你喜欢这篇文章，并且学到了Malloc的有趣知识。感谢@seiranib发表前审阅本文。如有问题或意见，欢迎联系我。Maxwell “ꓘ” Dulin致意。

 

0x09 尾注

文中进行了几处简化，目的是让普通人看懂，因此省略了一些内容，或者没有完整进行解释。下面是简化的地方：

• 修饰算法中的数12其实是常量PAGE_SHIFT，但在通常情况下，这个常量就是12。
• prev_size字段仅在下面的chunk空闲且不在tcache和fastbin中时才使用。这是因为tcache和fastbin不会对chunk的in_use位进行复位，就算chunk是空闲的。
• 理论上，如果对分配进行精心控制，相对字节的暴力穷举可以做到1/16的正确率。但是需要其他复杂的技巧，超出了本文的范围。
• Fastbin和tcache bins有许多差异，本文未进行解释，因为没有必要。想知道bins的更多信息的话，请见Azeria Labs的这篇好文。
• 另一篇文章的研究者进行了类似的研究。本文研究是独立进行的，得到了类似的结论，其他研究者只是先于本文发表了他们的结果而已。