Typestate-Guided Fuzzer for Discovering Use-after-Free Vulnerabilities

---

Remarks

Conference: ICSE 2020
Full Paper: https://www.scedt.tees.ac.uk/s.qin/papers/icse2020-uafl.pdf
Open-source: No

---

Summary

• 针对的问题：Use-after-free (UaF)漏洞的检查需要更可靠的技术。
• 目前的解决方案：目前主流的基于代码覆盖率导向的Fuzzing技术对于use-after-free漏洞存在一定的盲区。要触发UaF漏洞，不仅需要覆盖单个边缘，还需要按特定顺序遍历某些（长）边序列，这对现有的Fuzzer是一个巨大的挑战。
• 提出的创新方案概述：作者将Uaf漏洞建模成一种具有一定type-state属性的状态机模型， 并提出了基于状态机导向的模糊测试技术。具体来说，Fuzzing的过程由操作序列指导，以逐步生成触发type-state属性冲突的测试用例。此外，作者还采用了信息流分析来提高模糊测试的效率。
• 实验效果：UAFL在发现use-after-free漏洞所需的时间方面，明显优于一些主流的fuzzer，包括AFL、AFLFast、FairFuzz、MOpt、Angora和QSYM。作者发现了10个未知的UaF漏洞，并申请了5个新的CVE。这也说明了目前常用的的基于代码覆盖率导向的模糊测试技术在发现use-after-free漏洞上具有盲点，强调了基于状态机导向的模糊测试的必要性。

---

Introduction

Use-after-free漏洞的危害性就不在此多说了，UaF一般指访问了被释放后的内存区域时，可能导致数据损坏、信息泄漏、拒绝服务和任意代码执行攻击。根据最近的报告，在NVD数据库中，大约80%的UaF漏洞被评为高严重性或严重性漏洞。相反，只有大约50%的堆缓冲区溢出漏洞被视为高严重性漏洞。与其他漏洞（例如堆栈/堆缓冲区溢出漏洞）相比，UaF漏洞通常更难检测。主要原因是，要成功触发UaF，需要按特定顺序执行一系列操作-首先分配内存，然后终止内存的生存期，最后再对内存进行解引用。这些操作可能不集中在某一代码块中完成，这使得检测变得更具挑战性。

要触发UaF漏洞，程序必需要经过[malloc->free->use]这样一个操作序列。类似的，要触发空指针解引用，也要经过[nullify->dereference]这样的操作序列。因此本文的主要思想实际上就是引导程序的操作序列去抵达[malloc->free->use]这样的情况。

Approach

本文使用一个简单的例子来阐述UAFL的工作原理。如下图所示。该例子是从readelf中简化而来的，它包含一个UaF漏洞（即CVE-2018-20623）。后文还会给出出其控制流图（CFG），其中节点表示用其行号标记的语句。

当语句（第4、7、10和14行）执行时，会触发UaF漏洞。具体地说，指针ptr1指向在第4行分配的内存，然后ptr1和ptr2在第7行变成别名。ptr1（和ptr2）指向的内存在第10行被释放，但ptr2在第14行再次访问。让我们先思考一个问题，仅仅使用代码覆盖率作为Fuzzing的导向，足以保证高概率找出这个Uaf漏洞么？

现有的基于覆盖的模糊测试技术通常是单独考虑CFG边缘的覆盖，并且它们仅限于跟踪一系列边缘的覆盖。例如，对于路径A→B→C，AFL单独计算A→B和B→C的命中，但无法细化到路径A→B→C的命中。因此，现有的基于覆盖率导向的模糊测试工具很难检测到一些漏洞（如UaF和double free），这些漏洞违反了时态内存安全malloc→free→use。如下图所示，如果第4→7→10→14行是临时执行的（即（a）中的灰色节点），则可以触发UaF漏洞。让我们来模拟一下AFL的流程。假设初始种子是“aaaaaaa”，AFL产生三个突变体“aaaseen”、“aurseaa”和“faraeaa”，如（b）所示。这四条程序路径覆盖了CFG的所有边缘，但它们都不能触发UaF漏洞。此外，由于这四个测试用例已经覆盖了CFG的所有边缘，因此它们之后的突变体都不会覆盖新的边，也就都不会被fuzzer丢弃。考虑到边缘的单独覆盖（例如AFL），很难生成一个能够覆盖4→7→10→14的测试用例。

而作者提出的UAFL方法有两个阶段：基于typestate分析和typestate-guided fuzzing。在typestate分析阶段，UAFL首先执行静态typestate分析以捕获程序中的操作序列，跟踪违反typestate属性的时间关系。例如，要发现UaF漏洞，UAFL标识遵循malloc→free→use模式的所有操作序列。如下图中（c）的类型状态分析步骤所示，本文给出了满足UaF模式的已识别的操作序列（即4→7→10→14）。这个操作序列首先执行内存分配，然后通过内存释放，最后到达内存使用，并利用插桩技术指明4->7, 7->10, 10->14是覆盖率操作序列的边。值得注意的是，UAFL还执行指针别名分析，即源代码第7行中ptr1和ptr2是别名关系。
在typestate-guided fuzzing阶段，UAFL会在操作序列的指导下，生成测试用例，逐步引导程序向malloc→free→use操作序列执行。图（c）显示了UAFL的模糊测试过程。假设UAFL也生成了图2（b）的测试用例，并且覆盖了所有CFG边。以操作序列（即4→7→10→14）为指导，UAFL能够生成逐渐覆盖（整个）操作序列的新测试用例。例如，基于测试用例“aaaseen”，UAFL可以生成测试用例“auaseen”。此测试用例被AFL丢弃，因为与以前的测试用例“aaaseen”和“aurseaa”相比，它没有覆盖新的CFG边。然而，由于它覆盖了操作序列（即malloc→free）的7→10边，UAFL将其加入到测试池中进行进一步的变异，通过对测试用例auaseen进行变异，UAFL可以进一步生成新的测试用例f urseen，它覆盖了操作序列4→7→10→14（即malloc→free→use）。从而发现UaF漏洞。我们在这个例子上运行了UAFL，并在大约15分钟内发现了UaF漏洞。

---

Workflow

下图给出了UAFL的整体工作流程，在通过状态机分析识别出操作序列之后（例子中的4→7→10→14），我们将操作序列引导的信息通过插桩输入到程序中。为了实现所提出的两种策略，我们执行两种插桩：操作序列插桩和信息流插桩。在模糊循环期间，UAFL首先从测试池中选择一个测试用例（即种子）。然后，UAFL测量该种子的质量，并使用功率调度策略为其分配能量。接下来，采用自适应变异策略对该种子进行变异并产生新的种子。信息流分析用于产生自适应变异策略。生成新种子后，UAFL通过运行它们来检查是否有新的操作序列覆盖率。如果是这样，新的种子被认为是interesting的，并加入到测试池中进行进一步的变异。

---

Evaluation

作者实现了UAFL的工具原型，并将其与以下baseling fuzzers进行对比实验

• AFL [AFL 2.52b]
• AFLfast [Böhme2017]
• MOPT [2019]
• FairFuzz [Lemieux2018]
• Angora [Chen2018]
• QSYM [Yun2018]

Evaluation dataset: 14 widely-used real-world programs

Runtime: 24hours, 8 times

实验旨在回答以下四个研究问题：

• RQ1 - What is the effectiveness of the static typestate analysis for UaF vulnerabilities?
• RQ2 - How effective is UAFL in discovering UaF vulnerabilities?
• RQ3 - How effective are the two strategies in UAFL, i.e., operation sequence feedback and information flow based mutation?
• RQ4 - How is the code coverage relevant to UaF vulnerabilities?