Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

GREYONE: Data Flow Sensitive Fuzzing

作者:Shuitao Gan, Chao Zhang, Peng Chen, Bodong Zhao, Xiaojun Qin, Dong Wu, Zuoning Chen

单位: State Key Laboratory of Mathematical Engineering and Advanced, Institute for Network Science and Cyberspace, Tsinghua University, Beijing National Research Center for Information Science and Technology, ByteDance AI lab National Research Center of Parallel Computer Engineering and Technology.

出处:USENIX Security ‘20

原文:GREYONE: Data Flow Sensitive Fuzzing

Abstract

本文工作针对当前传统的动态污点分析需要大量人工、不准确且缓慢的局限,讨论如何使用污点分析更好地利用数据流特征来指导fuzzer。

作者提出了一种新颖的数据流敏感的fuzzing方案GREYONE。其总体工作流程类似于AFL,包括种子生成与更新,种子选择,种子突变,测试和跟踪等步骤。其亮点在于引入了fuzzing驱动的污点推断(Fuzzing-driven Taint Inference,FTI)以推断变量的污点属性。在变异种子的过程中,根据FTI提供的污点分析结果来确定要突变的字节和要探索的分支的优先级及如何突变。GREYONE补充了数据流特征来调整fuzzing的方向,使用另一种基于数据流特征的约束一致性,即污染变量与未接触分支中期望值的距离,向种子队列中添加一致性更高的测试用例从而提升突变效率。

作者在LAVA数据集和19个程序中对GREYONE进行了评估。结果表明,就代码覆盖率和漏洞发现而言,它的性能优于各种先进的fuzzer。在LAVA数据集中,GREYONE发现了所有列出的错误和336个未列出的错误。在现实世界的程序中,GREYONE总共发现了105个新的安全漏洞,其中41个被CVE确认。

1 Introduction

基于进化突变的模糊测试的核心任务是确定进化方向,以及在何处和如何突变种子输入,以便有效地探索难以访问的代码并满足复杂的数据流约束以触发潜在的漏洞。

  • 利用符号执行来解决控制流约束。但是符号执行不方便扩展到大型应用程序,也不能解决许多复杂的约束(例如单向函数)。
  • 深度学习和强化学习来预测要突变的字节和采取何种突变动作,目前效果不明显。
  • 数据流分析指导指导模糊测试。例如用于定位校验和、识别分支指令中使用的字节和值。

数据流分析指导fuzzing待解决的问题

RQ1:如何进行轻巧而准确的污点分析以提供fuzzing效率?

传统的动态污点分析有一些局限性:

  • 首先,需要大量的人工。 例如,VUzzer仅支持x86平台,必须使用自定义污点传播规则以本机或中间表示形式解释每条指令。还必须为外部函数调用或系统调用建立污点模型。
  • 其次,不够准确。 例如,某些污染的数据值可能会影响控制流,进而进一步影响其他数据,从而形成隐式数据流。 如果忽略了隐式数据流,则会导致污点不足甚至传播断开;如果全部计算这些流,则会导致污点标记过于宽泛。
  • 最后,它非常慢,导致fuzzing效率低下。

RQ2:如何用污点结果有效地引导突变?

利用推断的污点属性,VUzzer 突变了分支指令中使用的输入字节,并用期望值(例如,幻数)不精确地替换了它们。 REDQUEEN进一步标识输入的所有直接副本,即直接在分支约束(例如,幻数和校验和)中使用的输入字节,并将其替换为期望值。但是,它们既不能解决与输入的间接副本有关的分支约束(间接用于分支约束的输入字节),也不能对要探索的分支和要突变的字节进行优先级排序

RQ2:如何使用数据流特征调整fuzzer的演变方向?

现有的进化类型fuzzers通常会朝着增加代码覆盖率的方向发展。例如,AFL 将可找到新代码的测试用例添加到种子队列中,并从队列中一次选择一个进行变异。已经提出了许多其他解决方案,例如AFLfast和CollAFL,以进一步改善选择种子的方式,从而加快进化速度。但是,他们仅考虑控制流特征,而不考虑数据流特征(例如,污点属性或约束一致性),并且可能会在突变过程中浪费精力以探索难以到达的分支。

作者的解决方案

作者提出了一种新颖的数据流敏感fuzzing方案GREYONE,以解决上述问题。

fuzzing驱动的污点推断(FTI)

Fuzzing-driven Taint Inference(FTI)通过进行引导模糊测试阶段来推断变量的污染情况,在此阶段中,系统地更改每个输入字节(一次一个)并监视变量的值。如果在更改输入字节时变量的值发生变化,可以推断出前者受到污染并取决于后者。

实验表明,FTI比传统的污点分析更准确,例如,能够发现2到4倍的依赖性(没有误报)。此外,它避免了编写污染传播规则的人工工作,并且在运行时非常快。这种轻巧而完善的解决方案可以扩展到大型程序。

污点引导的变异

输入字节对代码覆盖率的贡献不同。作者利用FTI提供的污染情况对输入字节进行排序。更具体地说,对影响更多未触发的分支的输入字节进行优先突变,并对依赖于更优先的输入字节的未触发的分支进行优先探索。探索分支时,将输入的直接副本精确替换为期望值,从而按优先级对依赖的输入字节进行突变。

一致性指导的进化

许多模糊测试工具(例如AFL)都使用控制流特征(例如代码覆盖率)来指导进化。为了有效地探索难以到达的分支(例如,与输入的间接副本相关的分支),作者建议使用数据流特征来调整进化方向。 首先,将具有更高一致性的测试用例添加到种子队列中,使模糊测试器逐渐提高总体一致性,并最终满足未触及分支的约束。然后,将优先选择具有较高一致性的种子从突变队列中进行选择,从而加快了对新分支的探索。这种演化可以更快地满足约束条件,例如Angora中使用的梯度下降。但这可以避免陷入局部最小值,并带来长期稳定的改进。此外,将正在进行的突变转移到具有更高动态一致性的新种子上。实验表明,它显着提高了突变效率。

贡献总结

  • 提出了一种以污点分析为指导的突变策略,该策略能够优先确定要探索的分支和要突变的输入字节,并确定如何突变。
  • 提出一种新的一致性指导的进化解决方案,通过考虑数据流特征(包括污点属性和约束一致性)来调整fuzzing的方向。
  • 在19个经过广泛测试的开源应用程序上对其进行了评估,表明它的性能优于各种先进的模糊测试仪。
  • 在19个应用程序中发现了105个未知漏洞,并帮助供应商改进产品。

2 Design of GREYONE

GREYONE的总体工作流程类似于AFL,包括种子生成/更新,种子选择,种子突变和测试/跟踪等步骤。

亮点:

  • fuzzing驱动的污点推断(FTI),以推断变量的污点。通过对输入种子执行字节级突变并对其进行试探性的测试。该测试期间,监视程序变量的值变化。变量的值更改后,就可以推断出它是受污染的,并且取决于变异的输入字节。此外,还可以识别所有使用直接输入副本的污染变量。

  • 借助FTI提供的污点属性,进一步指导fuzzer以更有效的方式对种子进行变异。优先确定要突变的输入字节和要探索的分支。此外,确定如何更改输入字节,包括输入的直接和间接副本。

  • 通过一致性指导的演变来调整fuzzing的方向。除了代码覆盖之外,还跟踪测试过程中污染变量的约束一致性,并向种子队列中添加一致性更高的测试用例,从而使模糊测试程序逐渐增加一致性并到达未触及的分支。然后,优先选择具有较高一致性的种子以从队列中进行选择,从而加快了进化过程。此外,一旦找到具有更高一致性的新种子,就会将正在进行的突变动态地转移到该新种子上,从而提高了突变效率。

2.1 Fuzzing-driven Taint Inference

污点推断

污点推断分为以下三个步骤,如算法1所示。

  • 字节级突变。使用一组预定义的突变规则(例如,单比特翻转,多比特翻转和算术运算)一次对一个字节的种子输入进行突变。对于每个种子输入S和每个输入偏移pos,可以以此方式导出一组新的测试用例BLM(S,pos)。 > 不会同时更改多个字节。首先,如果多个字节发生突变​​,从而导致欠染或过染问题,将无法精确确定哪个字节负责潜在值的更改。其次,单字节突变产生较少的测试用例,并引入较少的性能开销。

  • 变量值监视。将生成的测试用例提供给测试,并在测试过程中监视程序变量的值。为了支持监视,使用特殊的值跟踪代码对目标应用程序进行检测。 > 仅监视在路径约束中使用的变量。首先,监视更少的变量要快得多。其次,仅这些变量将影响路径探索,仅监视它们以探索所有分支就足够了。
  • 污染推断。在测试每个测试用例集BLM(S,pos)之后,检查在路径约束中使用的每个变量的值是否保持不变。如果变量var的值发生变化,可以推断出var被污染,并取决于输入种子S的后一个字节。

与传统污点分析的比较。

与传统的污点分析相比,FTI需要更少的人工工作,并且更加轻巧和准确。

手动工作。传统的taint分析需要大量人工。通常,必须使用自定义的特定于指令的传播规则来解释每个指令/状态,或者将其翻译为中间表示形式,然后使用通用的传播规则进行分析。而FTI是独立于体系结构的,不需要额外的努力即可移植到新平台。

速度。 FTI非常快。首先,它基于静态代码检测,而不是动态二进制检测。其次,它仅监视路径约束中使用的变量的值,而不监视所有程序变量。第三,它不需要使用自定义规则来解释单个指令。

准确性。 FTI比传统的污点分析解决方案更准确,不受隐式数据流、外部函数或系统调用的影响。但是,由于字节级突变引起的fuzzing不完整,FTI可能仍然存在污染不足的问题。

2.2 Taint-Guided Mutation

基于变异的fuzzer将以某些方式变异种子输入并生成新的测试用例,以探索新的代码并触发潜在的漏洞。 GREYONE利用FTI提供的污点来确定要突变的字节和要探索的分支的优先级,以及确定如何突变。

优先处理要突变的字节

如图3所示,种子输入S的偏移pos处的每个输入字节可能会影响多个变量,然后影响多个分支。作者认为,如果一个输入字节可以影响更多未触及的分支,则应优先于其他输入字节。

优先考虑的分支

作者认为依赖于更多高权重输入字节的未触及分支应优先于其他未触及分支。

确定何处以及如何进行突变

利用输入字节和未开发分支的权重,可以进一步确定种子突变策略。

在哪里变异?

  • 给定一个种子和它的程序路径,将按照分支权重从高到低的顺序逐条探索该路径上未触及的相邻分支。
  • 探索特定的未触及邻居分支时,将以字节权重的降序逐一更改其相关的输入字节。

如何变异输入的直接副本?如前所述,输入的直接副本应与未触及分支中期望的值匹配。因此,在突变期间,将输入字节的直接副本替换为准确的期望值(用于幻数和校验和等)。

如何获得期望值?有两种情况。如果期望一个常数值(例如魔术数),用FTI记录该常数值。如果期望使用运行时计算的值(例如校验和),则首先输入格式错误的输入以进行测试,然后使用FTI获取期望的运行时值。接着使用记录的值(有微小的变化)来修补相关的输入字节。

如何变异输入的间接副本?如果某些输入字节影响未触及的分支,但未在分支中使用它们的直接副本,则按照字节权重的降序逐个更改这些字节。更具体地说,将对每个相关字节应用随机位翻转和算术运算。与FTI中使用的字节级突变不同,在此阶段可以将多个相关的字节一起突变。一致性指导进化解决方案将使突变动态地转移到更好的种子上,从而可以大大改善间接拷贝的突变。

减轻污点问题。由于测试不完整,FTI可能存在污染不足的问题。因此,对于任何未触及的分支,FTI报告的其从属输入字节可能是不完整的。为了探索该分支,还必须对丢失的依赖输入字节进行突变。更具体地说,除了对FTI报告的从属输入字节进行突变之外,还以很小的概率随机对其相邻字节进行突变。

2.3 Conformance-Guided Evolution

AFL系的fuzzer使用控制流特征(例如代码覆盖率)来指导fuzzing的方向。为了有效地探索难以到达的分支(例如与输入的间接副本相关的分支),作者使用补充数据流特征来调整模糊测试的发展方向。

作者注意到,对于未触及分支中使用的每个污染变量,需要翻转其相关输入字节的某些位以使其与期望值匹配。某些测试用例比其他用例需要更少的位翻转。所需的工作量与约束一致性相关,即,污染变量与未接触分支中期望值的距离。具有较高一致性的种子更可能产生执行未触及分支的测试用例。

基于此观察,使用种子的约束一致性来调整模糊测试的演变方向。会相应地修改种子更新和种子选择策略,以使模糊测试朝这个方向发展。模糊测试期间生成的测试用例更有可能具有较高的一致性,并最终满足难以到达的约束。

一致性计算

约束一致性指示目标(例如种子)与路径约束匹配多少:

  • 完整分支的一致性。
  • 基本块的一致性。(未触及的邻居分支的最高一致性)
  • 测试用例的一致性。

一致性指导的种子更新

除了查找新代码的测试用例之外,还向种子队列添加具有更高约束一致性的测试用例。为了有效地支持这种新的种子更新方案,作者提出了一种新颖的种子队列结构。 二维种子队列。 传统的种子队列通常保存在一个链表中,其中每个节点代表一个探索唯一路径的种子。作者扩展每个节点以包括探索相同路径,具有相同一致性但具有不同块一致性的多个种子,以形成二维种子队列,如图4所示。

种子队列更新。 图4还显示了在以下三种情况下如何更新种子队列。

  • A 新路径。 如果测试用例找到新代码,则它将与其他覆盖率指导的模糊测试器(例如AFL)一样,作为新节点添加到种子队列中。
  • B Samepath但更高的一致性。如果测试用例没有找到任何新代码,但是一致性比队列中相应节点(具有相同路径)中的种子更高,则该节点将被仅由该测试用例组成的新节点替换。
  • C 相同的路径和一致性,但基本块一致性不同。 如果测试用例探索相同的路径,并且与队列中相应节点中的种子具有相同的一致性,但是与该节点中的种子具有不同的基本块一致性分布,那么将把该测试用例追加到该节点上

值得注意的是,在最后一种情况下,由于测试用例具有基本块一致性的唯一分布,因此它可以派生新的测试用例以快速触发某些基本块的未触及的相邻分支,因此很有用。

比较。这种种子更新策略使模糊测试器逐渐提高整体一致性,并以与Angora中使用的梯度下降算法可比的速度快速满足未触及分支的约束。但是它可以避免陷入像Angora这样的局部最小值中。honggfuzz还比较了分支语句中操作数的相等性。如果分支的平等性增加,则会将测试用例添加到种子队列中。但是,它不排除与触摸分支相关的比较指令,这对分支探索没有用。此外,基本块内部可能具有多个比较指令,但并非所有比较指令都与分支相关。最后,它缺乏本文提出的高效二维种子队列结构,也限制了其效率。

动态突变库

如果要替换的种子被正在进行的突变所使用,由于新种子更好,因此会将突变重新建立到新种子上。该操作可以即时完成,如图1中的红线所示。实验表明,这种优化技术非常有效。例如,它可以将在LAVA数据集中发现相同数量错误的速度提高三倍。

一致性指导的种子选择

作者建议在种子选择过程中优先选择具有较高一致性的种子。

3 Implementation

Static Analysis and Instrumentation.

为了支持本文提出的策略,需要首先使用静态分析来分析目标应用程序,并在运行时收集一些信息。借助Clang执行一些基本的过程间控制流分析,并获得控制流图和其他必要信息。 覆盖范围跟踪。正如CollAFL指出的那样,在传统的覆盖率跟踪解决方案(例如AFL)中存在严重的哈希冲突问题。作者在GREYONE中复制CollAFL的缓解解决方案。 符合性跟踪。为了支持一致性跟踪,作者对每个分支语句(包括条件分支和switch语句)进行检测,以计数其操作数的相等位数(通过__builtin_popcount之类的操作)。 变量值监视FTI在模糊过程中依赖变量值监视。作者对应用程序进行检测,以记录在路径约束中使用的变量的值。更具体地说,作者为所有此类变量分配唯一的ID,并将其值存储在位图中(以ID为键),类似于存储AFL使用的代码覆盖的位图。

4 Evaluation

4.1 Experiment Setup

基准模糊测试进行比较。 作者将GREY-ONE与几种著名的基于进化突变的fuzzer进行了比较,包括AFL,VUzzer,Angora,CollaAFL,Honggfuzz和QSYM。

测试的应用程序。 选择目标应用程序时要考虑几个因素,包括受欢迎程度,测试频率,开发活动性和功能多样性。 最后,作者选择了19种流行的开源Linux应用程序(经过测试时为最新版本)。此外,作者还将LAEY-M数据集上的GREYONE评估为其他模糊测试。

性能指标。 作者选择漏洞发现和代码覆盖率作为用于比较每个fuzz er与GREYONE效率的两个主要指标。 对于代码覆盖率,主要考虑了路径覆盖率(即队列中种子的数量)和边缘覆盖率(即边缘命中的数量)。 对于漏洞发现,跟踪了由不同fuzzer检测到的唯一崩溃的增长趋势。进一步利用了包括afl-collect,AddressSanitizer和UBSan在内的工具对重复崩溃进行重复数据删除并确定独特的漏洞。

初始种子。 请注意,污点分析引擎FTI依赖于字节级突变。 如果不提供初始种子,它将性能很差,从而降低了GREYONE的效率。 因此,作者没有使用空种子测试目标应用程序,而是使用10个初始种子测试每个目标应用程序。

缓解随机性。 由于基于突变的fuzzer都依赖于随机突变,因此在测试过程中可能会出现性能抖动。 作者采取了两项措施来缓解随机性问题: * 首先,将每个实验进行5次,然后评估平均效果以及最小和最大性能。 * 其次,我们要测试目标应用程序更多的时间,直到模糊测试器达到相对稳定的状态(即,模糊测试器的性能顺序不再改变)为止。 实验表明,在测试这些应用程序60小时后,模糊测试器将变得稳定。因此在实验中测试了每个应用程序60小时。

4.2 Vulnerability Discovery

表1显示了在19个实际应用中由6个不同的模糊测试器发现的独特漏洞(在5次运行中累积)的数量。 在测试时,每个应用程序都是最新版本。

总计,AFL,CollAFL,Honggfuzz,VUzzer和Angora在所有应用程序中分别发现了21、34、18、6和12个漏洞。 GREYONE共发现了105个独特漏洞,并涵盖了其他模糊测试者发现的所有漏洞。 换句话说,GREYONE的漏洞发现比第二好的Fuzzer(即CollAFL)多出209%。 特别是,在这19个应用程序中,只有GREYONE报告了包括nm,tiff2pdf和libsass在内的三个应用程序是易受攻击的。 总之,在漏洞发现方面,GREYONE的性能明显优于其他5个模糊测试器。

4.3 Unique Crashes Evaluation

通常,fuzzer发现的崩溃越独特,其发现的漏洞也就越多。因此,独特的崩溃次数也是模糊测试的重要指标。由于随机性,作者不仅评估了平均值,还评估了5次运行中发现的唯一崩溃的最大次数。

表2列出了详细的评估结果,GREYONE在所有应用程序中均胜过所有其他模糊测试器。特别是在tiff2pdf,nm和libsass中,只有GREYONE报告了唯一的崩溃,其他fuzzer都失败了。

在5次运行中,GREEYONE在所有应用程序中平均发现716次独特的崩溃,比第二个最佳模糊测试器(即CollAFL)高出501%。在最大范围内,GREEYONE在所有应用程序中发现了1447次独特的崩溃,比第二名的模糊测试高出631%。

4.4 Code Coverage Evaluation

由于fuzzer只能在其探索的代码中找到漏洞,因此代码覆盖率是覆盖率指导的fuzzer的重要指标。

表3列出了每个fuzzer在十个应用中发现的唯一路径和边缘的平均数量。 此外,还评估了GREYONE与第二好的fuzzer相比的改进,并在表中显示。

就路径覆盖而言,在十个应用程序中有九个应用程序中,GREYONE的性能优于第二好的模糊测试器至少25%。 在上一个应用程序c ++ filt中,GREYONE的表现优于第二好的8%。 在新的边缘覆盖方面,GREYONE优于所有应用中第二好的模糊测试,平均提高了25.5%。

还评估了fuzzer开发的代码的增长趋势,GREYONE在所有应用程序中的增长趋势都比其他所有fuzzer强得多。

4.5 Evaluation on LAVA-M

发现错误。 表4显示了每个fuzzer在24小时内检测到的错误数量(5次运行的平均值)。 GREYONE在所有应用程序中发现2601个错误,包括LAVA-M中列出的所有错误。 此外,它在这四个应用程序中分别发现了327、4、4和1个未列出的错误,这表明GREYONE非常有效,并且比其他模糊测试者要好得多。

独特的崩溃。 得益于精确的taint引导突变和稳定的基于一致性的进化,GREYONE在发现独特的碰撞方面显示出强大而稳定的增长趋势。 与第二最佳的模糊测试器Angora相比,它发现的独特崩溃多大约1倍。

4.6 Heuristic Constraints Solving

利用FTI,GREYONE可以绕过各种复杂的约束。为了进一步评估其有效性,将其与最新的符号执行辅助fuzzerQSYM进行比较。

表5显示了5次运行,每次60小时的比较结果。尽管GREYONE占用较少的计算资源,但在代码覆盖率和漏洞发现方面都优于QSYM。与QSYM相比,GREEYONE平均发现的1.2倍唯一路径,1.12倍边缘,2.15倍唯一崩溃和1.52倍漏洞。

为了进一步证明约束解决方案的有效性,跟踪了路径覆盖率的增长趋势,如图6所示。在大多数主题中,可以发现GREYONE覆盖的路径比QSYM更快。 根据以上评估,当将GREYONE应用于混合模糊测试时,其启发式约束求解能力要优于符号约束求解器。

5 Further Analysis

进一步评估了GREYONE的数据流分析能力以及将此类数据流特征应用于模糊测试的结果,以更好地了解GREYONE的改进。

图7显示了FTI和DTA版本的GREYONE报告的未受污染的分支的比例:

  • DTA在所有应用程序中仍然存在严重的污点问题,
  • DTA错过了仅由FTI报告的所有未污染的分支机构。这些污点不足的问题多数是由隐式数据流引起的。
  • FTI的污染问题较少。例如,DTA在应用程序fig2dev中只能识别FTI报告的25%的taint。 平均而言,FTI发现的未污染分支比DTA多1.3倍。

Conclusion

在本文中,作者提出了一种新颖的数据流敏感的fuzzing方案GREYONE。 它通过监视变量值的变化来推断模糊过程中的污点,并进一步利用推断出的污点来指导种子突变。它还应用数据流特征一致性来调整模糊测试的发展方向,驱动模糊测试器迅速到达未触及的分支并触发潜在的漏洞。在代码覆盖率和漏洞发现方面,有较大优势,而其污点分析本身也比其他方法更轻便、准确。