Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

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

作者:Haijun Wang^1^ ^2^, Xiaofei Xie^3^, Yi Li^3^, Cheng Wen^2^, Yuekang Li^3^, Yang Liu^3^ ^4^, Shengchao Qin^5^ ^2^, Hongxu Chen^3^, and Yulei Sui^6^

单位:^1^Ant Financial Services Group, ^2^Shenzhen University, ^3^Nanyang Technological University, ^4^Zhejiang Sci-Tech University, ^5^Teesside University, and ^6^University of Technology Sydney

出处:ICSE ‘20

原文:Typestate-Guided Fuzzer for Discovering Use-after-Free Vulnerabilities

Abstract

现有基于覆盖率的模糊测试框架通常使用控制流图覆盖率来引导模糊测试的过程。然而单一的使用控制流图覆盖率并不能有效地发现例如UaF(use-after-free)等类型的漏洞。这是因为触发UaF漏洞往往需要以某种特定的顺序执行一长串的操作序列,这对于现有的模糊测试框架来说是非常困难的。

因此作者将UaF漏洞抽象为类型状态(typestate)属性,并提出了类型状态引导的模糊测试框架UAFL来发现违反该类型状态属性的漏洞。作者首先执行静态类型状态分析来找到可能违反类型状态属性的操作序列。这些操作序列随后被用来引导UAFL逐步地生成违反该类型状态属性的测试用例。此外作者还采用了信息流分析来提升UAFL的有效性。

作者选取了14个流行的现实程序对UAFL进行了深入的评估。结果表明UAFL发现漏洞的效率要明显优于其它现有的模糊测试框架,其发现了10个之前未知的漏洞,其中包括5个新的CVE漏洞。

1 Introduction

与其它类型的漏洞相比,UaF漏洞被普遍认为是更加难以被检测的。主要原因在于为了成功触发UaF漏洞,程序需要首先分配一片内存,随后释放这片内存,最后再使用这片内存。这些操作在程序中可能并不具有局部性,这就导致检测UaF漏洞变得异常困难。

为此作者提出了类型状态引导的模糊测试框架UAFL来发现违反特定类型状态属性的漏洞。作者认为许多常见的漏洞都可以被视为违反了某种特定的类型状态属性。作者首先执行了类型状态分析来识别可能违反类型状态属性的操作序列。作者随后提出了两种策略来提升UAFL的有效性:

  • 作者将操作序列覆盖率作为反馈来引导UAFL逐步地生成覆盖这些操作序列的测试用例;
  • 作者部署了信息流分析来推断测试输入是如何影响程序状态的,并利用这些信息设计了一种有效的变异策略来防止不必要的变异。

2 Motivating Example

20200726150152

20200726150358

现有基于覆盖率的模糊测试框架通常只单一地考虑控制流图中边的覆盖率,其难以追踪一串操作序列的覆盖率。因此对于这些模糊测试框架来说,检测例如UaF等违反时序内存安全的漏洞是非常困难的。

UAFL的工作流程包括以下两个阶段:

  • Phase1:类型状态分析。基于UaF漏洞的类型状态属性,UAFL首先执行静态类型状态分析来收集时序关系违反该类型状态属性的操作序列;
  • Phase2:类型状态引导的模糊测试。UAFL将前一阶段收集得到的操作序列作为引导来逐步地生成执行这些操作序列的测试用例。

3 Typestate Analysis

20200726160120

对于特定类型状态属性来说,一串不被有限状态自动机接受的操作序列代表非法序列,其可能违反了该类型状态属性。直观的说,由一串操作序列所触发的漏洞便可以被抽象为类型状态属性。

20200726160104

值得注意的是,UAFL采用了路径不敏感的可达性分析来实现类型状态分析,这可能导致误报,即部分被识别到的操作序列可能并没有违反类型状态属性。因此,作者通过模糊测试来进一步确认这些操作序列的合法性。

4 Typestate-Guided Fuzzing

基于静态类型状态分析识别到的操作序列,作者通过操作序列引导的插桩来控制模糊测试的过程,从而在运行时逐步地生成覆盖这些操作序列的测试用例。作者主要提出了两种策略来提升UAFL的有效性:

  • 作者提出了基于操作序列的引导策略,这可以引导UAFL逐步地生成覆盖这些操作序列的测试用例;
  • 作者提出了自适应的变异策略来配合上述引导策略。UAFL采用信息流分析来构建测试输入与程序变量之间的关系。基于该关系,UAFL自适应地变异测试输入来改变程序变量的状态。

20200726164808

4.1 Instrumentation

20200726164736

总的来说,UAFL的插桩主要包括以下三个步骤:

  • 通过共享内存$OP_mem[]$来记录操作序列中的语句是否被执行;
  • 通过共享内存$OPE_mem[]$来记录操作序列是否被执行;
  • 通过共享内存$IFA_mem[]$为之后的信息流分析记录分支语句判断条件中变量的值。

UAFL的插桩是在基本块层面进行的。值得注意的是,操作序列与执行路径往往是不同的。执行一条操作序列可能需要涉及一串控制流图中的边。为了提供更细粒度的引导来覆盖操作序列,作者还额外考虑了与操作序列中的基本块有支配关系的其它基本块。

4.2 Information Flow Analysis based Mutation

对于如何变异测试输入从而更快的覆盖操作序列这一问题,UAFL的基本思路是首先识别测试输入的哪些部分可以改变特定分支语句判断条件中程序变量的值,随后集中资源来变异测试输入中的这些部分直到满足该判断条件。作者通过信息流分析来识别测试输入与分支语句判断条件中程序变量的关系。

20200726164828

变量$x$到变量$y$信息流强度的计算方式如下:

$IFStrength(x, y, V_x, V_y) = H(x, V_x) - H(x y, V_x, V_y)$
$V_x$与$V_y$分别是变量$x$与$y$的值域。$H(x, V_x)$代表变量$x$的信息熵。$H(x y, V_x, V_y)$代表在已知变量$y$分布的前提下,变量$x$的条件信息熵。

UAFL通过变异测试输入的每个字节并记录分支语句判断条件中程序变量的值来进行采样。基于采样得到的信息流强度,UAFL计算得到测试输入每个字节的变异概率。直观的说,从测试输入的某个特定字节到分支语句判断条件中程序变量的信息流强度越高,该字节的变异概率也就越高。

4.3 Seed Selection & Power Scheduling

UAFL通过三级队列的方式来组织测试用例池中的种子。具体来说,对于一个新生成的种子,如果该种子覆盖了一条新的操作序列,UAFL便将其加入第一级队列;如果该种子覆盖了一条新的控制流图中的边,UAFL便将其加入第二级队列;否则UAFL便将该种子加入第三级队列。

模糊测试框架的功率调度策略决定了给某个种子分配变异机会的数量。UAFL将更多的变异机会分配给与操作序列更加接近的种子,从而让这些种子可以有更多的变异机会来覆盖更多的操作序列。

5 Evaluation

作者希望在评估的过程中回答以下问题:

  • RQ1:针对UaF漏洞的静态类型状态分析的效果如何?
  • RQ2:UAFL发现UaF漏洞的效果如何?
  • RQ3:UAFL采取了操作序列反馈与基于信息流的变异两种策略,这两种策略的效果如何?
  • RQ4:UaF漏洞相关代码的覆盖率如何?

为了验证UAFL的有效性,作者选取了以下6个具有代表性的现有模糊测试框架,这些测试框架分别采用了多种先进技术来提升模糊测试的有效性:1)AFL;2)AFLFast;3)FairFuzz;4)MOpt;5)Angora;6)QSYM。

作者选取了14个流行的现实程序作为评估的基准程序。在选取这些基准程序时,作者考虑了以下因素:1)在现有工作中被测试的频率;2)在终端用户中的受欢迎程度;3)功能的多样性。

模糊测试框架的有效性严重依赖于随机变异的结果,因此在评估中可能会存在性能偏差。作者在评估中运行每个模糊测试框架24小时,重复每次评估8次,计算评估结果的统计性能,并将程序提供的样例输入作为初始种子,从而尽可能的消除评估中可能存在的性能偏差。

5.1 Static Typestate Analysis Statistics (RQ1)

20200726193259

评估结果表明,UAFL执行的静态类型状态分析所引入的时间开销是可接受的,其平均为1,148秒(0.32小时)。操作序列反馈与基于信息流的变异这两种策略分别需要插桩平均19.2%与13.3%的基本块,更少的插桩也意味着UAFL可以集中更多的资源在测试可能违反UaF漏洞类型状态属性的操作序列上。

5.2 Vulnerability Detection Results (RQ2) & Evaluation of the Strategies (RQ3)

20200726193327

20200726193352

评估结果表明,UAFL在大多数情况下要明显优于其它现有的模糊测试框架。与AFL、AFLFast、FairFuzz、MOpt、Angora与QSYM相比,UAFL的性能提升分别有3.25倍、3.16倍、2.63倍、3.35倍、6.00倍与3.80倍。

UAFL采用的两种策略都是有效的。UAFLNoIF与其它现有模糊测试框架的比较结果说明了操作序列反馈的有效性。UAFL与UAFLNoIF的比较结果说明了基于信息流的变异的有效性。

5.3 Code Coverage (RQ4)

作者只计算了类型状态分析识别出的操作序列的代码覆盖率,这是因为1)只有这些操作序列可以帮助UAFL发现UaF漏洞;2)该代码覆盖率可以评估生成的测试用例与UaF漏洞的接近程度,从而可以揭示生成测试用例的质量。

20200726193420

与其它现有模糊测试框架相比,UAFL与UAFLNoIF对UaF漏洞相关代码的覆盖率更高,这也同时解释了为什么UAFL与UAFLNoIF发现UaF漏洞的效果更好。