Abstract
背景：即使最快的grammar fuzzer dharma依然要比简单的random fuzzer慢千倍
本文: 工具 F1
目的: 加快语法fuzzer产生新测试用例的速度
- 我们从头开始描述如何快速构建语法Fuzzer，从编程语言实现的角度处理Fuzzing。 （Q1. 这里不是语法Fuzzer本身的算法优化，而是构建Fuzzer的优化？Q2: 具体甚么是从编程语言实现的角度？）
- 从Python教科书方法开始，我们以分步的方式逐步采用和改编了功能编程和虚拟机实现技术中的优化技术，以及其他新颖的领域特定的优化方法。 (Q3: 功能编程和虚拟机实现技术中的优化技术，以及其他新颖的领域特定的优化方法具体是什么？）
实验: - 比最快的语法Fuzzer dharma提升了100-300倍的速度。
- 甚至比词汇随机模糊器快5–8倍
Intro
有趣的related works
- 竞品: Today, a large number of tools exist [26, 58, 59, 2, 24, 16, 54] that all provide grammar-based fuzzing.
- 自动生成语法: Recently, however, a number of approaches have been proposed to infer both regular languages [56] as well as context-free grammars either by grammar induction from samples [3] or by dynamic grammar inference from program code [28]. While these approaches require valid sample inputs to learn from, recent work by Mathis et al. [37] and Blazytko et al. [6] suggests that it is possible to automatically generate inputs that cover all language features and thus make good samples for grammar induction
Csmith [63]（生成有效的C程序）和JSFun-Fuzz [46]（针对Javascript）的情况那样固定。 诸如Gram-fuzz [24]，Grammarinator [26]，Dharma [38]，Domato [20]和CSS Fuzz [46]之类的模糊器允许用户将输入的for-mat指定为上下文无关的语法。 对于那些有限状态自动机就足够的情况，一些模糊器[13，60]允许将FSM作为输入模型。 也可以使用允许对输入进行上下文相关约束的模糊器[17]。
F1
使用有关语法的[Fuzzing Book]教科书章节中的简单Expr语法[65]，它可提供每秒103.82 KB的吞吐量。
如果一个人想要很长的输入（例如10兆字节）来对程序进行缓冲区和堆栈溢出压力测试，那么一个人就必须等待一分钟才能产生一个输入。
现在，将其与纯随机模糊器进行比较，例如直接使用dd if = / dev / urandom作为程序的输入（我们称为dev-random模糊器）。使用dev-random可以达到每秒23 MiB的速度，这甚至比最快的基于语法的模糊器dharma快一百倍，后者在Expr上产生174.12 KiB / s。
在CSS语法上，我们的F1原型在单个内核上产生的有效输入的最终吞吐量为每秒80,722千字节。这比迄今为止最快的语法模糊器dharma（仅产生CSS 242 KiB / s）dharma快333倍，甚至是dev-random模糊器的三倍。
这些结果使我们的F1原型机成为世界上产生有效输入的速度最快的模糊器。像F1这样的快速模糊器，不仅可以用于一般地节省用于模糊处理的CPU周期，而且还可以为需要高吞吐量的区域提供大量输入，包括CPU [36]，FPGA [32]，仿真器[ 18]和IOT设备[68]，所有这些都允许高速交互。它还允许压力测试硬件编码器和解码器（例如视频编码器），这些编码器在语法上需要有效，但很少见的输入可以从快速语法中获利.对实施加密和解密的硬件的旁道攻击可能要求证书使用具有有效值的信封，其中加密值是所包含的值之一，F1模糊器可以再次提供帮助。 最后，许多机器使用硬件实现的TCP / IP堆栈，这需要结构化的输入。 假定网络堆栈可以接受高吞吐量的流量，则可以使用F1对这些设备进行模糊处理。