Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Automatic Techniques to Systematically Discover New Heap Exploitation Primitives

作者:Insu Yun, Dhaval Kapil, Taesoo Kim,

单位:Georgia Institute of Technology, Facebook

会议:USENIX Security 2020

出处:Automatic Techniques to Systematically Discover New Heap Exploitation Primitives

Abstract & Introduction

堆漏洞已经现在成为系统软件中最常见、且最严重的漏洞。根据微软的报告,堆漏洞在其产品在2017发现的漏洞中占53%。堆漏洞主要是通过篡改metadata、利用底层分配器的机制完成利用。堆漏洞的exploit有两个特点:普适性强(application independence)和影响力大(bypassing modern mitigation),所以堆漏洞的利用方式被众多安全研究人员所关注。

然而目前发现利用堆漏洞的攻击方式仍然是人工的、特定于堆分配器的、特定于堆分配器版本的。这就使得安全研究人员需要花费大量的时间才能够发现、理解不同堆分配器(不同版本)的堆漏洞利用方式。

作者实现了一款自动化工具 ARCHEAP,能够自动化的发现堆利用原语,而不需要考虑堆的内部实现。与fuzzing类似,ARCHEAP通过指定堆分配器和漏洞根本原因(root causes of vulnerabilities),让计算机自动化进行堆操作(分配、释放)和读写操作,来发现堆利用原语。

作者的贡献在于:

  • 作者展示了堆分配器的common designs,并设计了一种高效的、使用shadow memory来评估exploit有效性的方法。
  • 设计并实现了ARCHEAP,能够对多种堆分配器自动化的根据漏洞发现其利用方式。
  • ARCHEAP发现了五种针对ptmalloc2新的利用方式,以及多种利用方式(针对于tcmalloc、jemalloc、DieHarder等)。并在发现新利用方式的方面优于目前最好的工具,HeapHopper。

Background: Heap Allocator的介绍

Common designs

作者对数个堆分配器进行了研究,发现它们的common designs:

  • binning:垃圾回收机制
  • In-place metadata:堆块的元数据就地存放(与数据区域相邻)
  • Cardinal data:堆管理器内部的指针列表(main_arena)

image-20200524185531543

ptmalloc2: glibc’s Heap Allocator

ptmalloc2 是glibc所使用的堆分配器。作者以ptmalloc2为例,介绍了ptmalloc2所使用到的堆块结构、垃圾回收机制。

Metadata

image-20200524222435827

Binning

ptmalloc有多种bins:fast bin, small bin, large bin, unsorted bin, and tcache。每种bin都有自己的特点以实现其目标。

  • fast bin
  • Small bin
  • Large bin
  • Unsorted bin
  • tcache

Complex Modern Heap Exploits

随着越来越多的安全检查机制的引入,对于堆漏洞的利用也不同于上古时代,能找到对于堆分配器通用的利用方式(unsafe unlink)。堆漏洞的利用方式也愈发复杂。安全研究人员仍热衷于研究能够复用的堆漏洞的利用方式(部分如Table 4所示)。

image-20200602022339976

image-20200602022339976

Heap Abstract Model

作者从两方面对堆漏洞利用进行了抽象:漏洞的类型、漏洞利用的影响。

漏洞的类型

四种常见的堆漏洞:

  • Overflow (OF): Writing beyond an object boundary
    • Off-by-one (O1): 单字节溢出
    • Off-by-one NULL (O1N):零字节溢出(作者认为单字节溢出的利用与应用程序功能高度相关、难以通用,因此不特殊考虑)
  • Write-after-free (WF): Reusing a freed object.
  • Arbitrary free (AF): Freeing an arbitrary pointer.
  • Double free (DF): Freeing a reclaimed object.

Impact of exploitation

作者将通过堆漏洞达到的影响做了分类,一共分为以下四类:

  • Arbitrary-chunk (AC): 返回任意地址的堆块
  • Overlapping-chunk (OC): 堆块重叠
  • Arbitrary-write (AW): 任意地址写
  • Restricted-write (RW): 有一定条件的内存写

攻击者可以通过利用堆漏洞获得上述的能力,结合程序功能劫持控制流。

Threat Model

为了描述堆漏洞利用技巧,作者假定攻击者的能力为:

  1. 攻击者能够以任意顺序分配和释放任意数量、任意大小的堆块
  2. 攻击者能够向堆块中合法的内存区域写入任意数据
  3. 攻击者能够出发某种类型的bug(Overflow、Write-after-free、Arbitrary free、Double free其中一种)

Technical Challenges

作者的目标是自动化探索新的堆漏洞利用技巧,然而存在以下挑战:

  • fuzzing如何自动化探索heap space(malloc的size,和写入的数据应该如何设置)
  • exploit有效性检验,该如何检查所进行的操作达到了期望的影响(如何判断任意地址写的发生)
  • 生成可读的exploit

Design

image-20200529184349883

Generate Actions

ARCHEAP能够随机的进行五种类型的操作:allocation, deallocation, buffer writes, heap writes, and bug invocation。

  • Allocation,ARCHEAP使用malloc进行内存分配,并将返回的指针保存起来以便后续释放时使用。考虑到堆分配器有针对于不同bins的管理机制、释放时的堆块合并、利用时的堆块转移等,ARCHEAP设计了一个用于选择分配堆块大小的策略。
    • image-20200529195606774
    • Random size,ARCHEAP将 $2^0$ ~ $2^{20}$分为四组($[2^0, 2^5)$, $[2^5, 2^{10})$, …),在四组中随机的选取值作为size,这样可以使的有超过1/4的size在fastbin的范围内。
    • 与之前chunk相同的size,因为相同bin中的堆块之间会有interact(堆块合并、unlink…)。
  • Deallocation,ARCHEAP会从已分配的堆块中随机选取堆块,使用free进行释放。会避免double free
  • Heap & Buffer write,ARCHEAP会向堆块的合法区域或全局buffer中写入随机的数据,为了避免过于随机导致搜索空间过大,其只使用Table 5中的方式生产随机数据,并会对数据引入一定的噪声,形如$ax+b$。
  • Bug invocation,ARCHEAP能够触发六种类型的漏洞:overflow, write-after-free, off-by-one overflow, off-by-one NULL overflow, double free, arbitrary free。ARCHEAP会多次触发其中的一种漏洞。

用户可以指定:堆块大小的范围、漏洞类型、impacts、允许的actions以及knowledge(如堆地址、全局buffer地址、堆块指针数组地址)。

image-20200529202127046

Detect Impacts

ARCHEAP能够检测四种堆漏洞的impacts:arbitrary chunk (AC), overlapping-chunk (OC), arbitrary-write (AW), and restricted-write (RW)

  • AC和OC:作者通过在malloc后储存返回指针的地址和malloc的size,并对检查指针是否在已分配的堆块范围内,以判断是否有堆块重叠的发生。
  • AW和RW:ARCHEAP为global buffer和储存chunk ptr的数组设置了shadow memory(减少搜索空间),ARCHEAP会在各项操作后检查shadow memory。当在allocation或deallocation时发现shadow memory状态不匹配时,则认为是发现了RW;heap/buffer write时发现,则认为是AW。

example:

image-20200602120732580

Generating PoC via Delta-Debugging

在得到模糊测试生产的POC后,ARCHEAP会对POC进行裁剪,去除冗余操作,生成易读的POC。

作者的思路很简单:对于每一个操作,如果去掉后不会对结果造成影响,则认为其是多余的。

image-20200601143747054

Applications

ARCHEAP可以应用于以下三个方面:

New Heap Exploitation Techniques

ARCHEAP可以通过指定漏洞和攻击者能进行的操作,自动化的生成利用脚本。作者分享了五个针对ptmalloc2的新利用方式:

  • Unsorted bin into stack
  • House of unsorted einherjar
  • Unaligned double free
  • Overlapping small chunks
  • Fast bin into other bin

Different Types of Heap Allocators

ARCHEAP能够对多种类型的堆分配器进行测试,而无需知道其实现细节。作者对除了ptmalloc2之外的十种堆分配器进行了测试。(dlmalloc, musl, jemalloc, tcmalloc, Microsoft mimalloc with its default and secure mode (noted as mimalloc-secure), LLVM Scudo, DieHarder, Mesh, FreeGuard, Guarder.)

运行24小时,在其中7个堆分配器中发现了利用方式。

除此之外,ARCHEAP还在三个堆分配器(mimalloc-secure, DieHarder, and Mesh)中发现了其实现上的bug。(未触发漏洞)

image-20200601150806847

Evolution of Security Features

作者在Ubuntu LTS: precise (12.04, libc 2.15), trusty (14.04, libc 2.19), xenial (16.04, libc 2.23), and bionic (18.04, libc 2.27)上分别生成POC,并测试其在其他版本的Ubuntu上验证POC的可用性,以此分析ptmalloc2安全性的趋势。

旧版本POC中利用技巧在新版本上被缓解,表明新版本引入的安全机制一定程度上缓解了原先的利用方式;而18.04中由于tcache的引入,使得堆漏洞更加容易被利用。

image-20200601171730385

Evaluation

作者主要从三个方面对ARCHEAP进行评估:与HeapHopper的性能对比;ARCHEAP探索security-critical state space的覆盖率;delta-debugging用于裁剪POC时的性能。

实验环境为:Intel Xeon E7-4820 with 256 GB RAM

与HeapHopper的对比

HeapHopper通过符号执行建立堆交互的模型,并使用该模型来评估堆分配器在特定情况下达到exploitation primitive的条件。作者为了证明与HeapHopper的差异,做了三个实验进行验证:1、在未建模的情况下发现未知利用方式(使用HeapHopper完成ARCHEAP的任务);2、部分建模的情况下发现已知利用方式(评估每种方法中建模的作用);3、完全建模的情况下发现已知利用方式(使用ARCHEAP完成HeapHopper的任务)

发现新的利用方式

image-20200601211639779

image-20200601212159001

部分建模的情况下发现已知利用方式

进行了下左图中的三个实验分别为:无建模、指定了size和指定了操作序列(TxnList)。ARCHEAP在无建模和指定size的条件下比HeapHopper发现了更多的漏洞。精确的模型在符号执行中起到关键作用,而对于模糊测试却没有作用。在给定操作序列的情况下,ARCHEAP难以在很短的序列中构造出复杂的fake chunk,从而导致指定TxnList时反而无法找到利用方式的情况。

image-20200601212709856

完全建模的情况下发现已知利用方式

上图右,HeapHopper在给定size和TxnList时优于ARCHEAP。

Security Check Coverage

为了验证ARCHEAP的覆盖效果,作者对ARCHEAP所触发的安全检查进行了统计,在ptmalloc2上运行了24个小时,ARCHEAP触发了21个检查中的18个。

C2、C4要求的条件十分严格,C21是与并发相关的检查,不在ARCHEAP的范围内。

image-20200601194913193

Delta-Debugging-Based Minimization

ARCHEAP使用delta-debug来最小化POC,作者表示在原始POC中有84.3%的操作是多余的,最小化后的POC平均只有26.1行。

image-20200601201027148

Conclusion

本文中作者提出了一种通过模糊测试的方式,自动化的发现堆漏洞利用的技术,ARCHEAP。

ARCHEAP通过利用抽象堆分配器、快速估计堆利用的可能性的方式,减少了模糊测试的搜索空间。

作者使用ARCHEAP对ptmalloc2及其他10种堆分配器进行了测试。