ProFuzzer：基于运行时类型探测的模糊测试技术
ProFuzzer: On-the-fly Input Type Probing for Better Zero-day Vulnerability Discovery
Remarks
Conference: S&P 2019
Full Paper: https://youwei1988.github.io/papers/SP2019.pdf
Slides: https://www.inforsec.org/wp/wp-content/uploads/2020/01/%E6%B8%B8%E4%BC%9F-ProFuzzer-Wei-You.pdf
POC: https://github.com/profuzzer
Abstract
Existing mutation based fuzzers tend to randomly mutate the input of a program without understanding its underlying syntax and semantics. In this paper, we propose a novel on-the-fly probing technique (called ProFuzzer) that automatically recovers and understands input fields of critical importance to vulnerability discovery during a fuzzing process and intelligently adapts the mutation strategy to enhance the chance of hitting zero-day targets. Since such probing is transparently piggybacked to the regular fuzzing, no prior knowledge of the input specification is needed. During fuzzing, individual bytes are first mutated and their fuzzing results are automatically analyzed to link those related together and identify the type for the field connecting them; these bytes are further mutated together following type-specific strategies, which substantially prunes the search space. We define the probe types generally across all applications, thereby making our technique application agnostic. Our experiments on standard benchmarks and real-world applications show that ProFuzzer substantially outperforms AFL and its optimized version AFLFast, as well as other state-of-art fuzzers including VUzzer, Driller and QSYM. Within two months, it exposed 42 zero-days in 10 intensively tested programs, generating 30 CVEs.
Summary
目前Fuzzer的问题：
缺少对输入结果的语义信息，它们执行的突变很大程度上是随机的；输入的搜索空间很大。
对于高效且可扩展的Fuzzing过程中至关重要的是深入理解目标程序的输入。 这样的输入通常是结构化数据，随机mutate可能产生大量的与原来输入结构不符的测试用例，即产生了大量无效的测试用例。
如何解决这个问题？
恢复输入的结构，对不同类型的字段采取专门的mutation策略，从而减小搜索的空间。
结构化的输入通常可以划分为具有特定语义的数据字段序列：例如，缓冲区大小，类别指示符等。这些字段的语义对于漏洞发现非常有用，可帮助模糊器确定字段到 mutate，合法值的范围，数据字段对程序执行的影响等。 利用这些信息，模糊器可以以更智能的方式运行，仅关注最有可能导致前所未有的执行路径的输入子空间。
Motivated by AFL’s mutation on random seed position, this paper proposed ProFuzzer which can probe different fields in input byte sequence by a lightweight way and use them to guide mutation.
Six field types are presented:
- Assertion. An input field of the assertion type has only a single valid value that allows the program to - - execute correctly.
- Raw data. Byte sequence that won’t affect execution path.
- Enumeration. Just several valid values in this field can pass the check.
- Loop count.
- Offset.
- Size.
They can efficiently influence the execution path and there are specific coverage reflections when fuzzer mutates fields corresponding to these six types. That’s the way to probe the fields while running instead of taint analysis or symbolic execution.
Introduction
模糊测试作为一种高效的自动化漏洞检测技术，已经被广泛应用于各类软件的安全测试中。现有的基于变异的模糊测试工具，在测试用例生成策略上依然具有较大的盲目性，无法针对目标文件格式和特定漏洞类型进行有效的变异。研究表明，AFL（ American Fuzzy Lop， 当前最流行的模糊测试工具）在24小时的测试过程中，超过60%的变异操作集中在不会产生任何新代码路径的无效字节上。如何提升变异策略的有效性是模糊测试领域的热点研究问题。
模糊测试仍存在的挑战：
- 基于生成的方法产生的输入尽管语法结构合理，确实减少了搜索空间，但它几乎没有提供各种输入可能对程序执行产生影响的线索：例如，一组输入是否都将导致相同的执行路径，因此仅其中之一应进行测试。此外，利用漏洞的输入甚至可能不遵循输入语法，因为如果某些输入字段与功能无关，则实现可能会选择忽略某些输入字段（例如，图像格式转换器可能忽略与渲染相关的字段）；也有错误的实现，甚至可能接受格式错误的输入。
- 基于变异的方法不需要关于输入模型的知识。相反，它使用一组合法的输入实例作为种子，并不断对其进行修改以探索各种执行路径。先前的研究已经研究了选择可能导致执行程序进入易受攻击的程序位置的正确种子的方法，以及确定可能增强代码覆盖率的关键输入字节的方法[9]，[10]。但是，对于给定的种子，变异通常是随机的，即使输入数据大小适中，变异也不会扩展。
- 高效和可扩展的模糊测试过程的关键是深入了解目标程序的输入。这样的输入通常是结构化数据，并且可以划分为具有特定语义的一系列数据字段：例如，缓冲区大小，类别指示符等。这些字段的语义对于发现漏洞非常有用，有助于模糊测试人员确定要更改的字段，合法值的范围，数据字段对程序执行的影响等。利用这些信息，模糊器可以更智能的方式操作，仅关注最有可能导致执行路径从未见过的输入的子空间。但是，此信息（字段及其语义）可能没有记录，也无法提供给模糊测试器，并且如果不进行深入的重量级分析过程，可能很难恢复。
本文的主要内容：
作者提出了一种称为ProFuzzer的模糊测试技术，该技术通过称为“探测”的轻量级随机模糊过程自动发现输入字段及其语义，以指导种子突变的在线进化。这种探测完全背负于常规的模糊测试，并且可以即时执行。更具体地说，ProFuzzer通过使一组种子变异来对目标程序执行两阶段模糊测试。在第一阶段（即探测阶段），它按顺序逐字节进行探测，即每次更改一个字节，针对目标程序枚举其值，然后移至下一个字节。此顺序的模糊测试步骤还会收集有关不同字节值下目标的执行路径的信息。该信息会自动进行在线分析，以恢复数据字段（将相关字节链接在一起）并确定其字段类型：例如，可以将其突变特定内容导致相同异常路径的连续字节分组为一个字段。在我们的研究中，我们确定了6种字段类型，这些字段类型对内容影响程序执行的方式进行了建模，例如大小，循环数和枚举，这些字段仅具有几个有效值，可以正确解释输入中的后续内容。这些类型与应用程序无关，描述了模糊相关的语义。数据字段及其类型的发现为第二阶段的模糊测试提供了指导，在此阶段，ProFuzzer对每个字段进行突变以利用可能导致攻击的值（例如，大数据量可能会利用缓冲区溢出漏洞），并根据字段类型探索合法值，以获得更好的覆盖范围。
Overview
下图以OpenJPEG的BMP输入文件为例，形象说明ProFuzzer的工作原理。图中，属于同一个输入域的相邻字节被框在了一起，这些字节具有相似的“变异—执行路径”模式。各个输入域按照“变异—执行路径”模式的特征进行分类。（0x1c， 0x1d）是一个枚举类型的输入域，其合法的枚举值是0x1， 0x4， 0x8， 0x10， 0x18， 0x20。路径探索型策略在对该输入域变异时，会将取值范围限定在所有合法的枚举值中。（0x16， 0x19）是一个长度类型的输入域，漏洞触发型策略会尝试各种边界值，例如文件的大小0xe3。
ProFuzzer的系统架构如下所示，包括四个功能模块：类型探测引擎、智能变异引擎、程序执行引擎、漏洞报告引擎。类型嗅探引擎的任务是为目标程序的每个输入文件进行产生一个类型模板，类型模板中包含了输入域的类型信息。智能变异引擎的任务是根据嗅探得到的类型模板，按预先制定的类型策略，对输入文件进行变异。程序执行引擎和漏洞报告引擎复用了AFL的底层部件，分别负责执行目标程序并收集路径覆盖信息，以及观测程序执行状态并报告异常。
Probing:
- 逐字节变异，尝试每个字节的256个值
- 根据256个值与程序行为直接的关系，相同行为的字段分到同一个group
- 为每个group恢复类型（ProFuzzer定义了6种类型），得到Template
- Template可以其它Seed重复使用，对不同类型的字节采用不同的mutation策略
Mutation:
- explore mutation：在有了template之后，分别对六种类型有不同的mutate策略
- exploit mutation：将特定类型的字段替换为特殊值
Approach
Profuzzer分为两个阶段：
第一阶段:通过逐字节突变，探测输入种子的字段和字段类型，尤其是在突变后，基于目标程序的行为变化（如执行路径的变化），Profuzzer能够识别输入字段是非常关键的。
第二阶段:由第一阶段得出的字段和字段类型来指导在线输入突变，不同的字段类型有不同的优先级和不同的突变策略。同一类型的字节组成的字段一起突变，这里的字段是之前探测到能产生路径覆盖的字节组合，所以这里的突变会更有方向，在不增加成本的同时扩大路径覆盖率。
四个组件组成：探测引擎，变异引擎，执行引擎和报告引擎。
探测引擎: 探测引擎的任务是根据给定二进制文件的种子输入生成类型模板。对于每个种子输入，ProFuzzer将遍历所有字节。对于每个字节，它遍历所有可能的值（0x00至0xff）并收集相应的执行配置文件。然后，从这些配置文件中提取一些指标（例如，由突变引起的边缘覆盖率变化），并将其用作字节的特征。然后，ProFuzzer将具有相似功能的连续字节分组到一个字段中。最后，它基于其可能值的变化与观察到的特征的相应变化之间的关系来确定每个字段的类型（例如，幻数字段可以通过以下模式来表征：所有突变发生在原始值中种子输入导致输入无效，因此执行时间短）。
变异引擎: 变异引擎使用探测到的模板（即字段和字段类型）来指导后续的突变。给出了两个方面的指导，第一是以具有成本效益的方式扩大覆盖范围。例如，ProFuzzer可以避免模糊原始数据字段，并专注于确定随后数据解释的变异字段。这将使我们能够到达原本难以到达的代码区域。在第二方面，领域信息可用于指导漏洞利用的产生。例如，缓冲区大小字段是许多漏洞的根本原因。已知某些突变模式对于大小域至关重要。
执行引擎和报告引擎: 作者使用标准的AFL执行和报告引擎。每次探测引擎或变异引擎请求执行应用程序时，执行引擎都会派生一个新进程。执行期间，它将自动收集执行配置文件。报表引擎监视执行情况，尤其是崩溃或挂起。
Evaluation
作者在10款常用开源软件上对ProFuzzer进行了功能验证和性能验证。测试所用的软件涉及图像处理、音频处理、文本处理和压缩处理等多种类型。同时，我们还将ProFuzzer同多款最新的模糊测试工具进行了对比。
ProFuzzer在两个月的部署实施中，挖掘出10款常用开源软件的42个未知安全漏洞，其中30个获得了CVE认证。这些安全漏洞未被其它模糊测试工具挖掘出来，有些漏洞甚至在目标软件中存在长达3年之久。
同其他模糊测试引擎相比，ProFuzzer多覆盖27% ～ 227%的代码路径，少使用53% ～ 79%的时间开销达到其它模糊测试工具的路径覆盖峰值，并且保持较高的有效变异率。
Personal Thoughts
亮点：
- 推断了输入的结构。通过观察程序的执行路径变化来发现输入字节和程序行为之间的关系，恢复了输入的六种类型的字段。
- 对六种类型的字段分别制定了mutation策略（将同一类型的连续字段当做一个整体来mutate，增加mutate成特定值的概率），减小了输入的搜索空间。
局限：
- 只是恢复了输入中六种类型的结构，并不是恢复出输入的完整的语义结构，还有六种类型之外的。
- 恢复字节类型是通过人工定制Rules实现的，限制了扩展性，而且有一定的FP和FN
与FairFuzz的比较：
- 目的上不同：
- ProFuzzer推断输入结构，通过观察程序的执行路径变化来发现输入字节和程序行为之间的关系，恢复了输入的六种类型的结构。分别为六种输入结构定制了不同的mutate策略，减少了无效输入的搜索。
- FairFuzz通过引导Fuzzer多执行稀有分支来提升覆盖率；为了多执行稀缺分支，FairFuzz提出了变异掩码的mutate策略，能保持进入稀缺分支的条件。
- Mutation策略不同：
- ProFuzzer是找出需要mutate的地方，分组、归类、整体性mutate。FairFuzz是找出不能mutate的地方。
- ProFuzzer的template通过为每个字节尝试所有256种可能后，根据行为进行归类，FairFuzz的overwritten, deleted, insertable经过一次试探。（FairFuzz的应用背景相当于assertion的情况，可能多个位置覆盖率相似度为1）
- ProFuzzer的template可重复使用，FairFuzz的mask不可重复使用