sec4fun
0%

论文阅读：Automatic Techniques to Systematically Discover New Heap Exploitation Primitives

发表于 更新于 分类于
本文字数： 8.9k 阅读时长 ≈ 8 分钟

基于堆分配器的元数据的利用技术由于通用性和强大性被广泛研究。但这一类技术总是被看作艺术，因为只能针对特定的分配器去人工探索新技术。而本文提出了一种自动探索堆利用原语的方法。

工作介绍

Main Idea：本文提出了一个可以自动化地系统性挖掘堆利用原语的工具ARCHEAP.其主要思想是通过分析确定一组现代堆分配器的通用设计和漏洞的根本原因作为模型，并通过提供堆操作和攻击功能作为操作，让工具去自主地探索空间，与fuzz中的空间概念相似。

堆利用技术受偏爱的原因

  • 与应用独立
    • 不需要对应用内部进行很深入的了解(相比其他利用技术，比如ROP等)
  • 功能强大
    • 可以绕过很多的现代强力保护措施

堆利用技术发展历程

堆利用技术

上图是堆利用技术在社区中的研究发展。但由于堆利用技术的这种所谓的艺术性，导致社区很难理解各种堆分配器（及跨不同版本）的安全隐患。而且当前的研究也具有很强的偏向性，比如ptmalloc2是被研究的最彻底的一个堆分配器，其他的则不然。

工作的三个难点(类比fuzz):

  • 生成具有准确数据的特定步骤序列
  • 设计一种快速的方法来评估堆利用的可能性
    • fuzz通过segment fault来识别有趣的测试用例。
  • 如何精简结果以便更好的理解生成的测试用例
    • 模糊测试器生成的测试用例通常是多余且晦涩的，因此要求用户花费不可忽略的时间和精力来分析最终结果

作者认为解决上述问题的关键点在于：抽象出堆分配器的内部共通点(通用设计模块)以及堆利用的root causes.

现代堆分配器的通用模块：binning, in-place metadata, and cardinal data

使用上述通用模块构建模型。后续工作基于此模型

  • 将堆操作(如malloc)与攻击功能操作(比如UAF)进行变异与合成。
  • 使用基于shadow-memory的检测来进行有效性评估
  • 当ARCHEAP找到新的利用原语时，它就会生成有效的PoC代码
    • 使用delta调试(已发表工作)，将冗余测试用例减少到最小的等效

主要贡献：

  • 证明堆分配器具有共同的设计，并且设计了一种有效的方法来评估利用技术。
  • 设计实现了 针对各种分配器自动发现堆利用技术的工具ARCHEAP，并对其原型进行了评估。
  • 新利用技术发现
    • 在ptmalloc2中发现了五项新技术
    • 在tcmalloc，jemalloc和DieHarder等各种分配器中发现了几项技术
  • 开源：https://github.com/sslab-gatech/ArcHeap
    • 但并未公开代码，只公开了五个发现的新堆利用技术

堆分配器分析

所有的堆分配器都普遍在意两个目标

  • 高性能
  • 低内存消耗(指管理堆需要的内存)

分配器的通用设计

  • binning：内存块按大小分组管理

    • 小内存块关注性能，大内存块关注内存使用情况

  • in-place metadata：大多数堆管理的元数据都在payload附近(即靠近用户能使用的内存区域)

    • 因为这样做可以利用cache提高性能

  • cardinal data：元数据一般并未做编码，以便快速查询和内存使用

由此导致的工作需要注意的地方

  • 考虑到binning的话，需要一个更好的采样方法以探索分配器的多个大小组

    • 如果直接在2^64^空间中统一选择一个大小，则在ptmalloc2中选择最小大小组的可能性（<2^7^）几乎为零（2^-57^）

  • in-place 和cardinal data限制了元数据的位置和域，从而减少了搜索空间

    • 根据这些设计原则，就只需要关注具有特定形式（即指针或大小）的块边界中的元数据。

ptmalloc2堆分配研究

论文以ptmalloc2作为讨论的默认版本。

**metadata(元数据)**：ptmalloc2中的chunk结构如下

chunk

Binning:ptmalloc2使用bin来堆不同大小的chunk分类管理

  • fastbin、small bin、large bin等。fastbin是一个单链表数组，每个单链表上的chunk大小相同。
  • smallbin和largebin中每个bin都是一个双向链表。其中small bin每条链上大小相同，large bin上每一条则按照从大到小存放一定范围的chunk
  • unsorted bin存放回收的chunk的双链表

复杂的现代堆利用技术

攻击者一旦发现了破坏堆元数据（例如overflow）或不正确使用堆API（例如double free）的漏洞，则下一步是将漏洞开发为更有用的利用原语，例如实现任意写入。

起初有一些针对大多数分配器的通用技术，比如unsafe unlink这种技术，但由于堆分配器的安全检查增加，这些技术往往会快速的失效。下图是研究人员研究并共享出来的一些堆利用技术，其中后面五项为论文工作发现的堆利用技术：

堆利用技术

堆抽象模型

堆抽象模型使得能够描述独立于基础分配器的堆利用技术。作者专注于对抗模型，为简洁省略了明显的堆API（即malloc和free）。

抽象堆利用技术

论文从两个方面抽象一个堆利用技术

  • Bug的类型：被用来将程序引入未预料状态。
    • overflow(OF)
      • 越界写
      • 可以用来修改后续chunk的元数据
      • 由于溢出可以导致很多的利用方式，又根据开发者常见错误细分：
        • Off-by-one (O1)：常见于开发错误：循环边界控制
        • Off-by-one NULL (O1N)，常见于开发错误：字符串拷贝
      • 注意一点：任意读写并没有被纳入其中，因为这两者一般要求过于特定，以及依赖特定的应用程序，不适合通用化。
    • write-after-free(WF)
      • 写入一个被free的对象
      • 可以用来修改free的元数据
    • Arbitraty- free(AF)
      • free一个任意指针
      • 会破坏堆管理操作完整性(如，free一个构造出来的元数据堆块)
    • Double free
      • 释放一个已经回收了的对象
      • 会破坏堆管理操作完整性（如，堆管理结构中链接多个相同的回收指针）；
  • 利用技术的影响。根据最终的结果分为以下四类：
    • Arbitrary-chunk (AC)
      • 劫持下一次malloc分配以返回想要的任意指针。
    • Overlapping-chunk (OC)
      • 劫持下一个malloc以返回攻击者可控制（例如可重写）的chunk内部的chunk。
    • Arbitrary-write (AW)
      • 将堆漏洞发展成一个任意地址写
    • Restricted-write (RW)
      • 与AW相似，不过会有部分限制。

威胁模型

攻击者可以发起的合法动作包括：

  • 可以分配任意大小的对象，并以任意顺序释放对象
    • 意味着攻击者可以使用任意大小作为惨呼调用任意数量的malloc调用，并以任意顺序调用free
  • 可以在合法的内存区域（即图1中的有效负载或全局内存）上写入任意数据
    • 尽管这种合法行为在很大程度上是理论上的应用，但是可以检查出所有可能的滥用机会
  • 攻击者只能触发一种类型的bug。
    • 在实践中允许多次触发同一类型的bug。

如果堆利用技术所需的功能少于此处描述的功能则更好(在这种情况下会做一个旁注以更好地加以说明)

技术挑战

论文工作的目标是实现在任何堆分配器的情况下自动探索新类型的堆利用技术-不需要像AFL一样要求源代码

  • 系统地发现未知类型的堆利用方案技术
  • 综合评估流行堆分配器的安全性

主要难点与解决方案

  • 堆空间自主推理(?)–Autonomous reasoning of the heap space
    • 搜索空间太大问题，原因在于
      • 大量的可能顺序
      • 堆API的参数
      • 堆和全局缓冲区中的数据组成
    • 本文工作方法
      • 使用了一种随机搜索算法，该算法可有效地探索较大的搜索空间
      • 抽象出了现代堆分配器的通用设计，以进一步减少搜索空间
  • 设计开发技术–Devising exploitation techniques
    • 系统需要验证候选者是否有价值。
      • 评估探索过程中利用的影响（即上文所述AC，OC，AW和RW），而不是合成一个完整的exp。
      • 通过使用shadow-memory，可以在运行时快速检测出上述影响。
  • Normalization
    • 随机搜索能有效地探索大的搜索空间，但这种算法发现的利用技术往往是冗余并且无关紧要的，需要时间来分析结果
    • 利用增量调试技术(delta-debugging)[76]来最小化多余的动作，并将发现的结果转换为基本类

自动化探索堆利用技术-ARCHEAP

ARCHEAP系统概述

系统结构如下：

堆利用技术

ARCHEAP遵循模糊测试的常规模式：测试生成，崩溃检测和减量测试，但针对堆利用进行了量身定制。

  • 根据用户提供的模型规范生成一个堆动作序列
    • 规范是可选项，默认下ARCHEAP将生成每一个可能的动作。
    • ARCHEAP可以制定的堆动作包括堆分配、释放、缓冲区写入、堆写入和bug调用
  • 执行过程中，ARCHEAP会评估所执行的测试用例带来的利用影响，
    • 类似于模糊测试中的检测崩溃
  • 当ARCHEAP发现一个新的漏洞时会将堆动作最小化，并产生PoC代码，其中只包含一组必要的动作。
    • 这种最小化是为了帮助对发现的技术进行post-analysis，与false positive无关；并且由于ARCHEAP在运行时的直接进行了分析，所以在评估中没有产生false positive。

基于抽象堆生成action

ARCHEAP随机生成五种类型的堆相关动作：Allocation、deallocation、buffer writes、heap writes和bug invocation。为了减少搜索空间，ARCHEAP使用现代分配器的常见设计习惯在抽象堆模型之上制定每个动作。

堆利用技术

Allocation

通过标准化的API，malloc()分配内存；对象的地址存储到其内部数据结构(container)；还存放了对象的块大小以及状态

  • 简单的方式是以随机大小分配内存，但针对分配器需要更多的考虑。采用的是随机选择一组大小，然后分配一个大小在此组中的对象(图中I1)
    • 当前的分组为[2^0^,2^5^)、[2^5^,2^10^)、[2^10^,2^15^)、[2^15^,2^20^)四组，这样可以使得对于fastbin大小范围内的测试选择机会更大一些。
  • 考虑到对象与同一容器中的其他对象进行交互,需要在同一bin中分配多个内存对象。(图中I2)
    • 做法：ARCHEAP分配了一个对象，该对象的大小与另一个对象的大小有关。
  • 为了找到由分配器中的常见错误引起的技术，ARCHEAP还使用专门的大小(I3,I4)
    • 比如预定义的常量（例如零或负数）来评估边界处理等

deallocation

使用free从堆容器中释放随机选择的堆指针

  • 为了避免double free(这个bug会在bug invocation部分涉及，这里不应该出现)，ARCHEAP会检查对象的状态。 如果ARCHEAP选择了已经释放的指针会忽略释放操作

heap & buffer writes

将随机数据写入堆对象或全局缓冲区

  • 堆利用技术，写入的数据在位置和数值上应该是准确的，fuzz的纯随机生成不可行
    • 方案
      • 利用堆分配器的临近元数据设计来修剪其搜索空间，只从一个对象的开始或结束处写入有限数量(MAX_WRITE)的值,原型中是8个
      • 并且写入的不是完全随机的值,是ARCHEAP的产生随机值(表5中P1-4部分),可以用于分配器中的大小或指针
      • 生成的值同时引入了系统性噪声，看表5可知，线性变换或对齐等
  • 并且只在有效的堆区域中写入数据(没有溢出等bug，因为这个是其他步骤专门引入)，确保操作的合法性

bug invocation

ARCHEAP会特意构建bug操作以确保bug的产生发生。当前，ARCHEAP处理堆中的六个错误：overflow、write-after-free、off-by-one overflow、off-by-one NULL overflow、double free、arbitrary free。ARCHEAP允许重复执行同一bug来模拟攻击者再次触发该bug的情况。

  • 对于overflow和off-by-one，ARCHEAP使用malloc_usable_size() API获取实际堆大小以确保溢出
  • 对于ptmalloc2，由于存在内存损坏错误，ptmalloc2的malloc_usable_size()不准确,ARCHEAP使用专用的单行例程来获取实际大小。
  • 在DOUBLE和write-after-free中，ARCHEAP检查目标块是否已被释放。 如果尚未释放，则ARCHEAP将忽略此bug操作并等待下一个操作

Model specifications

用户可以选择提供模型规范，以指导ARCHEAP专注于某种类型的利用技术或限制目标环境的条件。当前接受五种类型的模型规范：chunk sizes, bugs, impacts, actions和knowledge。

  • 前四种很显然
  • knowledge指的是有关攻击者破解ASLR的能力(即某些地址的先验知识)
    • 用户可以指定攻击者可能知道的三种地址类型：堆地址，全局缓冲区地址和容器地址,以影响ARCHEAP将来的数据生成

Detecting Techniques by Impact

影响大致分为下面四类：arbitrarychunk(AC), overlapping-chunk (OC), arbitrary-write (AW)以及restricted-write (RW)

  • 检测AC和OC
    • ARCHEAP在malloc之后复制块的地址和大小， 使用这些存储的地址和大小可以快速检查操作后块是否与其数据结构（AC）或其他块（OC）重叠。
  • 检测AW和RW
    • shadow-memory,复制其数据结构，容器和全局缓冲区,在执行任何操作时检查影子内存的差异
    • 执行过程中，只要ARCHEAP执行可修改其内部结构的操作(合法的操作)，它会同步影子内存的状态
    • 只有在前面的操作通过堆分配器函数的内部操作修改ARCHEAP的数据结构时，才会导致两者发生差异
    • ARCHEAP将分析范围限制为它保存的数据结构来提高检测效率。
      • 通常堆利用技术可以破坏任何数据，从而导致对整个内存空间的扫描。但是，ARCHEAP发现的技术只能修改堆或数据结构
      • 进一步，ARCHEAP只能检查修改其数据结构的，而忽略堆中的，因为无法将利用与deallocation(在释放中修改元数据)引起的改变区分。
    • 根据引入差异的堆操作将AW与RW区分
      • 在allocation或deallocation中发生差异为RW
      • 否则（即heap or buffer write）为AW
      • 原因：allocation和deallocation动作中的参数很难任意控制;heap or buffer write则不然

运行实例

running example

Generating PoC via Delta-Debugging

为了找到利用的根本原因，ARCHEAP使用delta-debugging改进了测试用例。如下图算法

算法

算法大致思想：对于每个action，ARCHEAP重新评估在没有它时测试用例的影响。如果原测试用例和新测试用例的影响相同，则被认为是是多余的排除掉。

  • 前的算法仅限于每次评估一个单独的动作。它可以很容易地扩展到用一个序列或堆动作组合在一起进行检查
  • 评估表明，当前使用单个动作的方案一旦最小化，ARCHEAP就会使用每个动作和C代码之间的一对一映射将测试用例转换为像图中人类可理解的PoC

POC示例

Implementation

扩展AFL实现

  • 如果发现导致利用影响的操作，则会发送定义的信号SIGUSR2，修改AFL使得只在收到此信号后保存崩溃
  • 精心实现了生成器，除了用于复制动作的预定义动作之外，不要隐式调用堆API
    • 比如生成器使用标准错误进行日志记录，而不是使用标准输出因为其在内部调用malloc进行缓冲
  • 为了防止内部数据结构的意外损坏，生成器会在随机地址中分配其数据结构
    • 诸如溢出之类的错误操作无法修改数据结构，因为它们不会与堆块相邻。

Applications

发现的新的堆利用技术

新的堆利用技术

  • Unsorted bin into stack (UBS).
  • House of unsorted einherjar (HUE).
  • Unaligned double free (UDF).
  • Overlapping chunks using a small bin (OCS).
  • Fast bin into other bin (FDO).

不同类型的堆分配器

24小时的评估，它在10个分配器中的7个中发现了几种利用技术。(除Scudo，FreeGuard和Guarder之外)

实验评估

发现了一些事实

  • 这些分配器都容易受到double free的破坏
  • 仍然可以通过dlmalloc-2.8.6中的溢出来获得任意块。

ARCHEAP还成功地在分配器中找到了几种与ptmalloc2不同的堆利用技术。

  • ARCHEAP的模型基于分配器（第2.1节）中的通用设计，具有足够的通用性
    • 例如tcmalloc的目标是高性能计算，其设计与ptmalloc2的设计大不相同（例如，大量使用线程本地缓存）。但是仍然遵循模型
  • ARCHEAP在mimalloc-secure，DieHarder和Mesh中发现了三个错误。作者向开发人员报告了发现，两个被认可并被修补。并且自动生成的PoC已被添加到mimalloc作为其回归测试。

Evolution of Security Features

安全趋势

发现的一些有趣的趋势

  • 新的安全检查成功地减轻了在ptmalloc2的旧版本中发现的一些利用技术：libc维护很可能会对新的流行利用技术做出反应。
  • bionic内部设计的改变导致从先前版本生成的大多数PoC无效，这表明生成的PoC的微妙之处，需要精确的参数和API调用的顺序才能成功利用
    • 并不意味着新的bionic版本是安全的。如图所示新组件tcache确实使利用变得更加容易
  • 旨在提高性能的新组件tcache削弱了堆分配器的安全性，不仅使其易于攻击，而且引入了新的利用技术

Evaluation

这部分主要关注三个问题

  • ARCHEAP发现漏洞的能力与当前最先进的heaphopper相比如何
  • ARCHEAP如何详尽的探索安全敏感的状态空间
  • delta-debugging在去除多余的堆动作方面有多大的效果？

在256GB内存的Intel Xeon E7-4820上进行实验。对于种子，使用了256个随机字节(这个种子作何理解)，这些字节是用来表示状态探索的起点，并不关键，因为ARCHEAP在状态探索过程中趋于收敛。

与heaphopper比较

最近提出的HeapHopper是用来分析分配器的各种实现中的现有利用技术。HeapHopper强调完整性和可验证性，其方法（即符号执行）与ARCHEAP（即模糊测试）有所区分。Heaphopper的关键思想（用详细的模型指导状态探索）将其能力仅局限于验证已知利用技术的原始目的，这与此论文的方法可以发现未知技术不同。

比较从三个方面进行

  • 探索没有特定漏洞利用模型的未知技术（例如，将HeapHopper应用于ARCHEAP所作的工作）
  • 使用部分指定的模型来探索已知技术（即评估指定模型在每种方法中的作用）
  • 使用特定漏洞利用的模型探索已知技术

New techniques

每个实验进行三次，每次24小时。

这里没有考虑FDO，因为FDO是FD的超集，两者难以区分。

实验对比

可以看到。HeapHopper在没有利用模型时无法发现任何未知的堆利用技术，它遇到了一些符号执行的基本问题：

  • transactions的指数增长
  • 选择合适的size和顺序来触发利用的巨大搜索空间
    • 这个很好理解，HeapHopper本身目标是给定利用模型，比如参数和transactions个数然后探索，但对于未知技术，缺少了一些先前约束，自然会导致搜索空间巨大

Known techniques with specified models

这部分评估了给定的利用模型对各种方法的作用效果。给定的模型都是已知利用的模型，对发现新的没有帮助

实验结果图

上面这个图时heaphopper对已知技术的模型建立。

针对部分给定模型的测试，只取size和TxnList两个部分的信息。针对完全给定模型的测试，取所有的信息，实验结果如下：

实验结果图

可以清楚的看到在给定部分模型时，ARCHEAP好于heaphopper，但在完全给定模型(exploit-specific models)**时，heaphopper速度更快，并且发现了6个而archeap只发现了5个，这也说明了模型对符号执行相比fuzz影响更大**。

这不意味着archeap差于heaphopper，因为ARCHEAP本身目的是发现新利用技术，基于这种目的，一个准确的模型本应是不可获得的(heaphopper目的则是为了验证利用技术)。此外heaphopper还引入了false positive，但archeap没有。

Security Check Coverage

通过检查archeap触发的安全检查来评估。在24小时探索中，archeap触发了ptmalloc2中21个安全检查中的18个。如下图。

安全检查触发

只有C2,C4和C21为被触发。

  • C21是一个并发漏洞相关的检查，不在工作考虑范围内
  • C2和C4要求large chunk之间有严格的关系（例如，两个块的大小不相等但小于最小大小），这对于基于随机化的策略来说太过严格。

Delta-Debugging-Based Minimization

Delta-Debugging有效地减少了来自原始PoC的84.3％的冗余操作，得到平均包含26.1行的小型PoC（请参阅表12）。 尽管最小化做的比较初步的(每次测试消除一个独立的动作带来的影响)，但最终的PoC足够小使得可以手动分析以了解所发现技术的影响。

Delta-Debugging效果

Discussion and Limitations

Overfitting to fuzzing strategies

模糊策略可能不足以检查某些分配器。

  • 比如chunk元数据不临近payload(这与archeap的模型的核心部分相悖从而导致整个技术失效)

  • 比如分配器为其大小使用big-endian编码等。

对于这些分配器，则需要深入了解目标分配器来设计自己的模型

scope

前面说过archeap是只关注发现堆利用技术的，并没有涉及到具体的应用程序的上下文信息。而且archeap只关注用户空间，并没有应用到内核。