Group of Software Security In Progress

Not All Coverage Measurements Are Equal: Fuzzing by Coverage Accounting for Input Prioritization

作者:Yanhao Wang, Xiangkun Jia, Yuwei Liu, Kyle Zeng, Tiffany Bao, Dinghao Wu, and Purui Su > > 单位:TCA/SKLCS, Institute of Software, Chinese Academy of Sciences, QiAnXin Technology Research Institute, Pennsylvania State University, School of Cyber Security, University of Chinese Academy of Sciences, Arizona State University, and Cyberspace Security Research Center, Peng Cheng Laboratory > > 会议:NDSS 2020 > > 论文链接:Not All Coverage Measurements Are Equal: Fuzzing by Coverage Accounting for Input Prioritization

Abstract

基于覆盖率的模糊测试(coverage-based fuzzing)已经被广泛应用在现实存在的软件应用上,以寻找其中潜藏的漏洞。该技术使用语句覆盖率与分支覆盖率等信息来指导模糊测试输入的变异,从而能够在无需输入格式等信息的前提下生成覆盖更多代码进而发现更多漏洞的输入。

当前基于覆盖率的模糊测试实现保留所有覆盖新语句或新分支的模糊测试输入,以用于后续的输入变异,其并不关心这些语句或分支的安全影响。从测试软件的角度来说该实现是合理的,因为测试的目的是覆盖软件应用的全部代码。然而从寻找漏洞的角度来说该实现却是有缺陷的,因为1)现有实现依旧无法在合理的时间内覆盖软件应用的全部代码;2)人们始终希望尽早发现漏洞,从而能够及时修复它们。此外在面对启用反模糊测试(anti-fuzzing)的软件应用时,现有实现寻找漏洞的效率也出现了明显的降低。

因此作者提出了覆盖率审计(coverage accounting),其根据三个不同层面(函数、循环与基本块)的标准来评估覆盖率的安全影响。作者设计了一种确定模糊测试输入优先顺序的新方案并开发了一个用于寻找内存破坏漏洞的灰盒模糊测试框架TortoiseFuzz。作者在30个现实存在的软件应用上评估了TortoiseFuzz,并将其与4个灰盒模糊测试框架(AFL、AFLFast、FairFuzz与MOPT)与2个混合模糊测试框架(QSYM与Angora)进行了对比。TortoiseFuzz与QSYM的评估结果相当,二者都能够比其它5个模糊测试框架发现更多的漏洞,而TortoiseFuzz消耗的内存仅有QSYM的2%左右。TortoiseFuzz发现了20个之前未知的漏洞,其中包括15个新的CVE漏洞。

1 Introduction & Background

AFL使用分支覆盖率来指导模糊测试输入的变异,而libFuzzer则同时支持分支覆盖率与基本块覆盖率。AFL保留所有覆盖新分支的模糊测试输入,并在确保覆盖所有新分支的前提下根据大小与延迟来确定输入的优先顺序。现有实现通过增加调用上下文与内存访问地址等更细粒度的信息来进一步优化AFL原始的分支覆盖率方案。

然而各个分支包含漏洞的可能性是不同的,现有实现却都忽略了这一点,并将所有分支同等对待。于是那些不太可能包含漏洞的模糊测试输入被视为与其它输入同样重要,并被进一步用来变异与测试。因此人们需要一种确定模糊测试输入优先顺序的新方案来发现更多漏洞,同时尽可能避免反模糊测试的影响。

文章提出了一种确定模糊测试输入优先顺序的新方案覆盖率审计。作者认为任何通过增加额外信息来优化分支覆盖率方案的现有实现都无法避免反模糊测试的影响,因为这些实现的根本问题在于它们将所有分支的覆盖率同等对待。此外内存破坏漏洞与内存访问操作密切相关,为了有效地寻找这些漏洞,作者认为应当关注并覆盖与内存访问操作相关的分支。作者从函数、循环与基本块这三个不同的层面来评估并标记安全敏感的分支,并在确保覆盖所有这些分支的前提下根据它们的覆盖率来确定模糊测试输入的优先顺序。

作者开发了一个基于覆盖率的灰盒模糊测试框架TortoiseFuzz,其并不依赖于污点分析(taint analysis)或符号执行(symbolic execution)。该框架仅在AFL的输入排序(input prioritization)这一步骤中引入了覆盖率审计。

20201120041831

输入排序的目的是为后续的变异与测试选择模糊测试种子。基于覆盖率的模糊测试使用当前测试的覆盖率信息来指导后续模糊测试输入的选择。AFL使用分支覆盖率来确定模糊测试输入的优先顺序,该步骤包含输入过滤(input filtering)与队列淘汰(queue culling)这两个阶段。输入过滤的目的是根据分支覆盖率来过滤掉无用的模糊测试输入,而队列淘汰的目的是为后续的变异与测试确定模糊测试输入的优先顺序。

2 Coverage Accounting

作者提出了一种通过评估并标记安全敏感的分支来确定模糊测试输入优先顺序的新方案覆盖率审计。该方案需要满足两方面的要求:

  • 覆盖率审计应当是轻量级的,因为该方案的目的之一是通过优先测试可能包含漏洞的模糊测试输入来缩短发现漏洞的时间;
  • 覆盖率审计不应依赖于污点分析或符号执行,因为该方案需要避免反模糊测试的影响。

由于内存破坏漏洞与内存访问操作直接相关,作者设计了一种针对内存错误的覆盖率审计来评估各个分支包含漏洞的可能性。

2.1 Function Calls

在函数调用层面,作者将内存访问操作抽象为特定函数的调用。如果一个函数出现在了一处内存错误的调用栈中,那么该函数就很有可能涉及其它的内存错误,因为开发者很有可能重复犯错。因此作者认为应当优先测试覆盖这些函数的模糊测试输入。

作者检索了最近四年公布的所有CVE漏洞来收集这些漏洞涉及的函数,并根据各个分支调用这些函数的次数来评估它们包含内存破坏漏洞的可能性。

函数调用层面的评估标准为$Func(e) = card(C(dst_e) \cap F)$,$e$表示评估的分支,$F$表示CVE漏洞涉及函数的集合,$dst_e$表示分支$e$的目标基本块,$C(b)$表示基本块$b$调用函数的集合,$card(\cdot)$表示集合包含元素的个数。

20201120041917

2.2 Loops

由于开发者经常使用循环来访问数据,循环与缓冲区溢出等内存破坏漏洞也是密切相关的。因此作者认为应当优先测试覆盖循环的模糊测试输入,他们使用循环包含的后向分支来进行标记。

循环层面的评估标准为$Loop(e) = 1 \ \mbox{if} \ IsBackEdge(e) = \mbox{True} \ \mbox{else} \ 0$,$e$表示评估的分支,$IsBackEdge(e)$表示判断分支$e$是否为后向分支的函数。

2.3 Basic Blocks

在基本块层面,作者将内存访问操作抽象为内存访问指令的执行,这是最细粒度的覆盖率审计层面。作者根据各个基本块包含内存访问指令的个数来评估它们包含内存破坏漏洞的可能性。

基本块层面的评估标准为$BB(e) = card({i i \in dst_e \wedge IsContainMem(i)})$,$e$表示评估的分支,$dst_e$表示分支$e$的目标基本块,$IsContainMem(i)$表示判断指令$i$是否为内存访问指令的函数。

3 The Design of TortoiseFuzz

作者设计的目的是优先测试更有可能包含内存破坏漏洞的模糊测试输入,同时保证选中的输入能够覆盖尽可能多的分支。该设计面临三方面的挑战:

  • 如何恰当地定义需要被覆盖的分支并选择模糊测试输入来完全覆盖这些分支?
    • 由于内存破坏漏洞与内存访问操作密切相关,只有安全敏感的分支与漏洞直接相关,因此这些分支应当被输入完全覆盖;
  • 如何根据覆盖率审计来定义安全敏感的分支?
    • 作者为函数、循环与基本块这三个不同层面的评估标准设定了相应的阈值,评估结果超过对应阈值的分支将会被视为安全敏感的分支;
  • 如何引导模糊测试框架去覆盖包含漏洞的分支?
    • 作者认为一个模糊测试输入覆盖安全敏感分支的个数越多,该输入覆盖包含漏洞分支的可能性就越大。

TortoiseFuzz包含插桩(instrumentation phase)与模糊测试循环(fuzzing loop phase)这两个阶段。

20201120041945

20201120042024

4 Implementation & Evaluation

TortoiseFuzz是基于AFL开发的。作者在现实存在的软件应用上评估了覆盖率审计与TortoiseFuzz,并提出了五个研究问题:

  • RQ1:TortoiseFuzz能够发现现实存在的未知漏洞吗?
  • RQ2:与其它灰盒/混合模糊测试框架相比,TortoiseFuzz在现实存在软件应用上的评估结果如何?
  • RQ3:与其它评估标准相比,TortoiseFuzz使用的函数、循环与基本块这三个不同层面标准的评估结果如何?
  • RQ4:覆盖率审计能够优化其它模糊测试框架的评估结果吗?
  • RQ5:覆盖率审计能够避免反模糊测试的影响吗?

4.1 Experiment Setup

20201120042048

4.2 RQ1: Finding Zero-day Vulnerabilities

20201120042215

TortoiseFuzz发现了十类总共56个内存破坏漏洞,其中包括20个之前未知的漏洞与15个新的CVE漏洞。该工具能够在现实存在的软件应用中发现一定数量的未知漏洞。

4.3 RQ2: TortoiseFuzz vs. Other Fuzzers in Real-world Applications

20201120042239

TortoiseFuzz能够比AFL、AFLFast、FairFuzz、MOPT与Angora发现更多的漏洞,并与QSYM的评估结果相当。

20201120042307

20201120042448

尽管TortoiseFuzz的目的并非覆盖尽可能多的分支,但其达到的分支覆盖率能够与其它模糊测试框架相当。

TortoiseFuzz消耗的内存仅有QSYM的2%左右,因为混合模糊测试框架需要更多的资源来执行污点分析与符号执行等重量级的分析。

4.4 RQ3: Coverage Metrics

20201120042542

20201120042554

TortoiseFuzz使用的函数、循环与基本块这三个不同层面的评估标准能够优势互补,同时它们对于覆盖率审计来说都是必不可少的。

4.5 RQ4: Improving the State-of-the-art with Coverage Accounting

20201120042837

覆盖率审计能够被集成进其它模糊测试框架,并极大地提升它们寻找内存破坏漏洞的效率。

4.6 RQ5: Defending against Anti-fuzzing

20201120043046

20201120043054

在面对启用反模糊测试的软件应用时,与覆盖率审计相比AFL寻找漏洞的效率出现了明显的降低。与AFL相比TortoiseFuzz使用的函数、循环与基本块这三个不同层面的评估标准更加健壮。