Typestate-Guided Fuzzer for Discovering Use-after-Free Vulnerabilities报告人:jxin本文发表于软件工程顶级会议ICSE 20，第一作者是来自蚂蚁金服集团的王海军博士。 一、主要内容 1. 关注点 程序中已分配的内存区域在释放后再次被访问，就会产生Use-after
Typestate-Guided Fuzzer for Discovering Use-after-Free Vulnerabilities
报告人:jxin
本文发表于软件工程顶级会议ICSE 20，第一作者是来自蚂蚁金服集团的王海军博士。
一、主要内容
1. 关注点
程序中已分配的内存区域在释放后再次被访问，就会产生Use-after-Free漏洞（Double-Free漏洞可以看作是Use-after-Free的特例），可能导致数据损坏、信息泄漏、拒绝服务和任意代码执行攻击。作者在文中提到最近的一份报告，在NVD数据库中大约80%的UaF漏洞被评为高严重性或严重性漏洞，相比之下，只有约50%的堆/栈缓冲区溢出漏洞被评为高严重性。
2. 问题原因
当前主流的以覆盖率为导向的模糊测试工具主要是通过控制流图CFG的边覆盖来引导fuzzing过程，这种方法虽然在发现堆/栈缓冲区溢出等类型的漏洞方面具有强大能力，但在分析检测UaF/DF的漏洞上却并不高效。主要原因在于，触发UaF漏洞的条件，不仅仅是简单地覆盖CFG中的某一条边，而是需要按特定顺序来遍历CFG图中一连串的边序列，对应在程序中就是执行一系列操作：即首先分配内存，然后终止内存的生存期，最后再对内存进行解引用。这些操作可能并不都位于某一个代码块中，给模糊测试工具的检测带来了挑战。
3. 解决方案
作者提出了将UaF漏洞建模成一种具有一定type-state类型状态属性的状态机模型，并提出了基于状态机导向的模糊测试技术。作者开发了基于类型状态导向的模糊测试工具UAFL，用于检测程序中违背类型状态属性而导致的Use-after-Free漏洞。
具体分为两个阶段：第一阶段是静态的类型状态分析，找出程序中潜在的违反类型状态属性的操作序列，第二阶段是模糊测试，Fuzzing的过程由前面找到的操作序列引导，来逐步生成能够触发类型状态属性冲突的测试用例。在此过程中，作者还采用了信息流分析来提高模糊测试的效率。
二、类型状态分析
文章的前半部分围绕typestate analysis（类型状态分析）这一技术展开论述。类型状态分析是形式化验证中广泛使用的一项技术。作者认为，典型的UaF和DF内存破坏型漏洞可以用类型状态机来建模。
如图所示，要触发UaF漏洞，程序必须经过[malloc->free->use]这样一个操作序列。类似的，要触发DF漏洞，需要出现空指针解引用，也要经过[nullify->dereference]这样的操作序列。本文的主要思想实际上就是通过类型状态分析，从而在fuzzing过程中引导程序的操作序列去抵达[malloc->free->use]的情况。
作者在文中使用了一个例子来具体描述类型状态分析的过程。该例子从readelf中简化而来，它包含一个UaF漏洞（CVE-2018-20623）。在该例子中，当语句（第4、7、10和14行）被执行时，就会触发UaF漏洞。
Line 4：为指针ptr1分配内存；
Line 7：ptr1赋值给ptr2，ptr2成为别名；
Line 10：ptr1和ptr2指向的内存被释放；
Line 14：ptr2再次被访问。
如果第4→7→10→14行在某一时序下被执行，则可以触发UaF漏洞。
至此，就完成了对于典型UaF漏洞的类型状态分析。已识别的操作序列（即4→7→10→14）体现了满足UaF模式的一系列操作时序：首先执行内存分配，然后通过内存释放，最后到达内存使用。此外，这一过程中还包含了对指针别名的分析，即标注源代码第7行中ptr1和ptr2是别名关系。作者在实现中利用插桩技术指明4->7、7->10、10->14是覆盖此操作序列的边，UAFL就会标识出遵循此malloc→free→use模式的所有操作序列。
整个算法的描述如下图所示。算法输入是程序P，输出是操作序列的集合S。算法先找到程序中所有分配内存的声明语句SM, M是通过SM分配的内存对象(Line 2)；然后遍历每个(m, sm)(Line 3)：
（1）通过指针分析，计算该指针的别名，即指向同一内存空间的指针 (Line 4)；
（2）识别该内存空间所有指针是否存在free操作 (Line 5)；
（3）同样地，寻找所有指针的use操作 (Line 6)；
（4）最后，生成操作序列<sm, sf , su>，放入输出集合S (Line 7)
三、类型状态机引导的模糊测试
通过上个阶段的类型状态分析，识别出可能违背类型状态属性的操作序列之后，作者进一步提出了两个策略来改善fuzzer的效率：一是以操作序列覆盖作为反馈，来逐步引导生成能够满足操作序列条件的测试用例；二是使用信息流分析的方法来推算测试输入是如何影响程序的状态，避免产生不必要的变异。
为了实现所提出的两种策略，作者在UAFL中进行了两种插桩：操作序列插桩和信息流插桩。其中，操作序列插桩就是在通过状态机分析识别出操作序列之后（例子中的4→7→10→14），将该操作序列作为引导信息插桩输入到程序中。信息流插桩的目的在于通过信息流分析来建立输入与变量之间的联系。例如，上例中Buf的第2和第4字节与第8、9行相关，为了能到达第10行代码，则据此信息流分析的结果引导生成测试用例。
在程序的控制流图CFG中，用节点表示用其行号标记的语句，图（a）的灰色节点就表示了从上述例子的类型状态分析得到的操作序列。作者用这个例子，模拟了AFL在边覆盖率引导下的种子变异流程。假设初始种子是“aaaaaaa”，AFL产生三个变异，分别是：“aaaseen”、“aurseaa”和“faraeaa”（图（b）所示）。尽管这四个测试用例都不能触发UaF漏洞，但是四条程序路径已经覆盖了CFG的所有边，于是在它们之后变异生成的测试用例都不会覆盖新的边，也就将被AFL所丢弃。考虑到AFL是以边的覆盖率为导向，很难高效地生成一个能满足上述类型状态操作序列4→7→10→14的测试用例。
在类型状态机引导的模糊测试阶段，UAFL会在操作序列的指导下，生成测试用例，逐步引导程序向malloc→free→use操作序列执行，如图中（c）的类型状态分析步骤所示。假设UAFL在图（b）的测试用例基础上继续变异，以操作序列（即4→7→10→14）为指导，UAFL能够生成逐渐覆盖（整个）操作序列的新测试用例。例如，基于“aaaseen”，UAFL可以生成 “auaseen”。此测试用例曾被AFL丢弃，因为与以前的“aaaseen”和“aurseaa”相比，它没有覆盖新的CFG边。然而，由于它覆盖了操作序列中的7→10边（即malloc→free），UAFL将其加入到测试池中进行进一步的变异，生成“furseen”，它覆盖了操作序列4→7→10→14（即malloc→free→use），从而得以发现UaF漏洞。
作者在文中提到，UAFL在这个例子上运行了大约15分钟就发现了UaF漏洞，而AFL运行24小时依然没有发现该漏洞。
四、整体流程
下图给出了UAFL的整体工作流程，图中直观描绘了UAFL技术方法的两个阶段：上半部分是类型状态分析与插桩，下半部分是类型状态引导的模糊测试。
在类型状态分析阶段，UAFL首先执行静态分析以捕获程序中的操作序列，跟踪其是否违反类型状态属性的时序归约关系。不过随着程序规模的增长，类型状态分析也可能会产生较大的时间开销。在Fuzzing循环期间，UAFL首先从测试池中选择一个种子，测量该种子的质量，并使用Power Schedule策略为其分配能量。接下来，UAFL采用自适应变异策略对该种子进行变异，产生新的种子。在这里，使用了信息流分析的插桩来调整产生自适应变异策略。生成新种子后，UAFL会检查其对操作序列是否产生新的覆盖。如果满足，新的种子被认为是interesting的，并加入到测试池中进行下一步变异。
五、实验评估
作者实现了UAFL的工具原型，并将其与当下主流的测试工具进行了对比，包括：AFL（AFL 2.52b）、AFLFast（Böhme2017）、MOPT（2019）、FairFuzz（Lemieux2018）、Angora（Chen2018）、QSYM（Yun2018），数据集是14款现实中广泛使用的程序（如下表所示）。经过24小时8次实验，得到的结果是：UAFL在发现Use-after-Free漏洞所需的时间，均优于上述这些State-of-the-Art的fuzzer。作者发现了10个未知的UaF漏洞，并申请了5个新的CVE。
六、总结思考
通过本文可以看出，以代码覆盖率为导向的模糊测试技术在发现Use-after-Free漏洞上确实存在一定的局限。作者提出的静态类型状态分析方法，在诸如UaF/DF之类的逻辑错误漏洞的检测方面具备较强的针对性，也说明了静态分析获得的状态机模型对于模糊测试的必要性。
【论文作者】Haijun Wang
【论文链接】https://www.scedt.tees.ac.uk/s.qin/papers/icse2020-uafl.pdf
【论文来源】软件工程顶级会议ICSE 20
【报告人】jxin
【单位】国防科技大学软件安全智能并行分析实验室
