【论文分享】Fuzzing: A Survey for Roadmap

1. Introduction

Fuzzing存在三个主要的问题

• sparse defect space of inputs

• strict valid input space

• automatic execution of various targets

sparse defect space of inputs 缺陷在应用中是稀疏的，只有特定的输入会触发缺陷。因为fuzzing的主要目的是发现目标程序的缺陷，所以fuzzing理论需要生成属于缺陷空间的输入。一些安全错误在浅层，所以在很短的fuzz时间就被找出来了。然而，许多安全错误需要fuzzing去检查更复杂的执行路径，并且去求解很窄的路径约束。因此，一个高效的fuzzing算法需要对程序和错误有很深的理解。因为缺陷通常是未知的，基于测试程序和漏洞的理解的fuzzing理论会把计算资源导向更有可能存在缺陷的代码区域。

gap2：strict valid input space。fuzzing被用在很多应用里，每个应用需要自己的输入。现代的应用特别大，会导致更复杂的输入规格。因此，需要去生成目标应用所接受的合法输入。而且，为了提高fuzzing的效率，生成的输入最好是能够执行不同的执行状态。这需要fuzzing去开发更高级的方案去生成合法的输入。没有系统地分析测试程序，几乎是不可能准确地限制输入空间。比如，一个随机变异的PDF文件可能会违法PDF的规格。fuzzing需要小心地去变异pdf文件，来让生成的输入属于合法的输入空间。

gap3：various target 。 由于fuzzing重复地执行测试程序，fuzzing的过程需要自动化、高效。由于测试程序和漏洞的多样性，执行的环境也各有千秋。对于某些程序来说，直接fuzz就可以了。但是，其他的程序需要额外的操作才能自动化地测试，比如硬件。而且，安全错误也需要自动的指示器来记录潜在的漏洞。程序的crash是很常用的指示器，能够自动从操作系统那里俘获异常。然而，许多其他的安全错误的表现形式并不是crash，比如数据竞争。这些漏洞需要精心设计指示器，才可以在fuzzing的过程中自动记录。

2. Overview

首先介绍一些概念。一个输入会被保留为种子，当这个输入能够获取比较好的fitness。fitness是一个衡量输入好坏的指标，比如代码覆盖率。然后，fuzzer会选择种子去做变异。变异操作符，叫做mutators。当一个种子从种子池中选出来，能量调度就会去确定分配给种子的能量。能量指的是当前fuzz轮次，变异的次数。

fuzzing分为三部分，input generator，executor和defect monitor。input generator为executor提供很多输入，executor基于输入运行程序。同时fuzzing监控执行，看有没有发现漏洞。

fuzzing可以基于输入的生成分为两种类型。一种是generation-based，另一种是mutation-based。generation-based的fuzzing基于语法/合法的语料库生成输入。就是直接从种子池里拿。mutation-based会对现有的输入进行变异来生成新的输入。给定一个种子池，基于变异的fuzzing会通过种子调度，字节调度和变异调度来获取输入。

从执行时能获取的信息的多少，又可以分为黑盒，灰盒和白盒。黑盒fuzzing不知道每次执行时的内部状态。这些fuzzer通常通过输入格式或者不同的输出状态来优化fuzzing的过程。白盒fuzzing能获取到每次执行的所有内部信息，因此能够系统性地区探索目标程序的状态空间。白盒fuzzing通常利用动态符号执行去分析程序。灰盒fuzzig获取执行的状态的信息介于黑盒和白盒之间，比如只知道内部执行状态的边覆盖率。

最常见的执行状态是代码覆盖率或者边覆盖率的信息。使用覆盖率的基本假设是发现更多的执行状态能够增加发现漏洞的可能性。同时，由于使用fuzzing的目的不同，执行状态的信息也不局限于代码覆盖率。这些信息可以是协议实现的状态机，面向对象程序的合法执行，并发实现的别名覆盖率，深度学习模型的神经元覆盖率，或者android智能电视的执行日志。

fuzzer通常使用崩溃来作为安全漏洞的指示器，因为崩溃提供了一个很直接的记录。然而一些缺陷并不会触发crash，因此，fuzzer也使用一些其他的漏洞指示器，比如物理安全违反。指示器只是揭示潜在的安全问题，后续可以用其他的安全工具或者人工去验证。

3. Fuzzing Theory

3.1 Seed Set Selection

• 最小化种子集合
• 避免计算资源消耗在已经探索比较好的区域
• 看作是MSCP问题（minimal set cover problem），最小化包含所有元素的子集。
• NP难问题，现有的方法采用贪心多项优化算法来获取最小子集

3.2 Seed Schedule

基本概念

• 种子就是程序的输入
• 种子在程序中执行，有一条路径。所以很多时候，可以把种子当成是程序的一条路径

核心问题

• 哪些种子参加下一轮的变异

• 要花多少时间在这些种子上

  • 实际实现的时候，用变异的次数来代替时间

fitness

• 是什么

  • 衡量种子（输入）质量的指标

• 都有哪些

  • bug的数量

    • ILP问题

      • 不考虑执行状态的话，最大化漏洞数量的问题可以简化为整数线性遍程问题。
      • 用线性约束来最大化漏洞数量，比如用time budget的上界来表示每个种子。
      • 通过求解ILP问题，可以计算出每个种子的time budget。

    • WCCP问题

      • weighted Coupon Collector’s Problem

      • WCCP会去估计发现新的一个bug需要多长的时间

        • 消费者获得一个新的消费券前需要买多少东西是一个问题
        • 每个发现的bug可以当作是消费券，WCCP的目标是去预测要花费多少（比如time budget）才能获取新的消费券（新的漏洞）

      • 为了预测漏洞的到达时间，WCCP需要知道所有漏洞的分布，而这需要通过已发现的漏洞来估计得到。

      • fuzzing会用wccp预测的时间给每个种子最少时间去fuzzing然后找到新的漏洞。

    • 这两种问题都会为更有可能发现漏洞的种子分配更多的时间预算。

    • 方法的缺点

      • 由于漏洞在测试程序中是稀疏的，基于漏洞数量去做优化很容易陷入局部最优。
      • 因此fuzzing过程中只会对发现漏洞的代码区域去测试，就不会去探索更多的代码区域
      • 结果会错过一些复杂条件触发的漏洞

  • 状态转化（马尔可夫链）

    • 基于执行状态去计算fitness，因为执行状态可以提供fuzzing更多的信息

    • 现有的很多方法都是基于代码覆盖率来计算fitness，因为大的代码覆盖率意味着发现漏洞的可能性更大

    • 一种用来对状态转化建模的理论是马尔科夫链

      • 表示从一个状态转化到另一个状态的随机过程

    • block transition

      • 基本块到另外一个基本块的转化，这是有概率的
      • 在执行过程中，AB被执行了70次，AC被执行了30次，那么基本块A到B的概率就是0.7，基本块A到C的概率就是0.3
      • 对于一条路径，比如ABDEG，他的转化概率是多少呢？AB，BD，DE，EG的转化概率分别是0.3，0.25，0.6，0.8，所以ABDEG的转化概率就是0.3x0.25x0.6x0.8=0.036
      • 所以种子也可以看作是一条路径，也可以计算其转化概率
      • 越低的转化概率说明这个种子越好。低转化概率说明这条路径走得不是很频繁，也说明这部分区域探索得不是很好。

    • path transition

      • 路径到另外一条路径的转化是基于变异的，这个转化过程也可以用马尔科夫链来建模
      • 路径转化的概率是通过前一次执行来计算的
      • 在AFLFast中，状态i发现新状态j所需的最小能量是1/pij，pij是转化概率。
      • 因此，AFLFast会分配更多能量到频率更少的路径中（路径转化概率低的路径）
      • 同样的变种在AFLGo和AFLChurn中也有存在

    • 缺点

      • 需要所有状态的转化概率才可以做一个好的决定
      • 然而在fuzzing的过程中，有很多的状态是没有检查过的，也就说明马尔可夫决策不是最优的

    • 优化方案

      • block transition

        • rule of three

      • path transition

        • Round-Robin schedule

  • 状态转化（多臂赌博机）

    • 来源

      • traversing all seeds or focus on a specific seed
      • exploration vs exploitation problem

    • 什么是多臂赌博机？

      • 一个玩家通过观察赌博机的奖励情况来最大化总的奖励

      • exploration

        • 玩所有的arms来获取奖励的期望值

      • exploitation

        • 只选择最高奖励期望的arms玩

      • fuzz中的建模

        • 种子ti可以看作是赌博机的一个arm
        • 奖励是种子ti发现的一条新路径

    • EcoFuzz

      • 考虑到fuzzing的过程中，种子的数量逐渐增加，种子的奖励期望逐渐下降
      • EcoFuzz提出了多臂赌博机的一种变种来解决问题
      • 选择性地给没有fuzz过的种子赋予能量（exploration）
      • 衡量一个种子的奖励期望的公式是 1- pii/根号i，pii是自转化概率（种子t的变异会导致同一条路径的概率）
      • 逻辑是低自转化概率意味着种子的变异大概率能够发现其他的路径。
      • 因此，Ecofuzz更喜欢获得低自转化概率的种子

    • AFL-HIER

      • 也把路径转化当成是多臂赌博机问题（MAB）
      • EcoFuzz使用一个指标（边覆盖率）来获取新种子
      • AFL-HIER使用多维度的覆盖率指标，比如函数，边，基本块，来添加indeed种子。
      • MAB算法使用的是UCB1

  • 状态发现

    • 来源

      • 马尔可夫和多臂赌博机都是当成是状态转换问题来做。
      • 然而，fuzzing的主要目标是发现新的状态，比如新的代码覆盖率，新的crash，新的bug
      • 所以fuzzing的过程可以当成是种群发现问题。

    • 种群发现问题

      • 简介

        • 生态学家会从自然界中收集很多的样本，而样本中的种群可能是稀有的，或者是很普通的。
        • 生态学家基于样本来推断全部种群的属性，包括未发现的。

      • 重要假设

        • 未发现种群的属性可以由已发现的稀有种群来解释
        • 这个假设暗示fuzzing可以通过给稀有种群分配更多的能量来发现新的状态

      • 建模

        • fuzzer生成的输入可以是收集的样本，程序的输入空间是全部种群（全集）。

        • fuzzing基于特定的指标把输入分类为不同的种群

          • 一个执行路径可以当成是一个种群
          • 所有执行该路径的输入都是属于同一个种群
          • 这种情况下，一个稀有的种群就是一条很少走过的路径

    • Entropic

      • 认为fuzzing就是一个学习的过程

      • 逐渐学习到程序行为的信息

      • 用香农定理来测量种群发现的有效性

      • 香农定理的初始公式是H=-∑i pi log(pi)

        • pi是选择一个种群的概率
        • H大意味着有更多的信息，也就是收集的样本包含更多的种群。

      • 发现种群的比率量化了fuzzing过程的效率

      • 从香农定理里推断，熵值衡量了一个种子种群发现的效率。

        • pit 是种子t变异后生成输入属于种群Si的概率
        • 种子t的学习率是基于概率pit和一个熵估计器来计算的

      • 总之，更多的能量会被分配给更大学习率的种子，比如那些更高效地发现新种群的种子会被赋予更多的能量

3.3 Byte Schedule

• 确定种子的哪个byte的变异频率

• 大部分的模糊测试工具都是基于执行信息启发式的来选择字节，或者随机的

• 字节调度比起种子调度需要对程序有更深的理解，比如路径约束，数据流信息

• 因此，现有的fuzzer尝试解决一个更简单的问题：字节的重要性。也就是哪个字节影响fuzzing的过程

• NEUZZ and MTFuzz

  • 用深度学习模型对输入字节和分支行为的关系进行建模
  • 深度学习模型的梯度量化了字节的重要性，因为一个字节的梯度如果大，说明了字节轻微的扰乱会对分支行为造成比较大的影响
  • 对于后续的变异，fuzzing会去选择高重要性的字节去变异

• AFLChurn

  • 基于种子的fitness来量化字节的重要性

    • 种子的fitness反映了种子的质量
    • 因此可以针对那些提高了种子质量的字节来进行变异

  • 使用蚁群优化算法来学习哪些字节影响了种子的质量

    • 就像蚁群搜索食物一样，如果一个字节的变化提高了种子的fitness，fuzzing就增加这个字节的分数。
    • 当fuzzing一直测试时，所有字节的分数就会随时间下降，就像蚁群的气味衰减一样

3.4 Mutation Operator Schedule

• 目的：能够发现新状态的变异器应该有更大的概率被选择

• classfuzz

  • 假设马尔可夫蒙特卡洛方法可以对变异调度的过程进行建模

  • 使用Metropolis-Hastings算法去解决变异调度的问题

  • 为每个变异器计算发现新状态的成功率

  • 随机选择下一个变异器，然后根据当前变异器和选择的变异器的成功率来接受或者拒绝。

    • 和马尔可夫决策过程类似
    • 已知当前变异器i，给定下一个变异器j，根据pij的概率大小来进行选择

• MOPT

  • 粒子群算法PSO来对变异选择的过程进行建模
  • PSO使用几个粒子群，并且逐渐将他们移动到最佳位置
  • 每个变异器是一个粒子，位置是选择变异器的概率
  • 一个粒子找到他最合适的位置是当这个粒子在这个位置时能够找到最多的新状态。
  • 因此，所有的粒子会逐步逼近他们最好的位置，从而构建了选择变异器的概率分布。
  • 然后fuzzing就会基于概率分布来选择变异器。

3.5 Diverse Information for Fitness

• seed retention

  • 通过变异种子来保留输入，如果输入能探索新的执行状态，就保留该种子

  • 在下一轮选择种子的时候，可能就会选择保留下来的种子

  • 大多数的基于覆盖率的模糊测试基于边覆盖率来保留种子

  • 为了提高漏洞的发现率，要使用更敏感的代码覆盖率来揭示执行状态的更多信息

  • 为特定的场景需要设计新类型的fitness

    • 深度学习模型
    • 自动驾驶车辆

3.5.1 Sensitive Code Coverage

• bitmap的哈希碰撞问题

  • 构建一个bitmap，类似一张表格，里头的元素是边【bi，bj】，bi，bj则是表示基本块
  • 然后对bi，bj计算哈希来表示一条单独的边
  • 但是有可能出现不同的边的表示结果是一样的

• 边覆盖率不一定能保证路径覆盖全

  • 比如有两个输入分别走了ABDEG和ACDFG

  • ACDEG这条路径的种子就不会被保留，因为没有增加边的覆盖率

  • 解决：

    • 组合单独的bitmap

      • bitmap的组合会引入很多的种子，就需要权衡fuzzing的效率和覆盖率的敏感性

    • dynamic principal component analysis

      • 减少数据集的密度

    • 提高边覆盖率的敏感性

      • 路径哈希
      • 调用上下文
      • 多级覆盖率
      • 代码复杂性

• 提高分支的敏感性

  • x[3]-0x44的值要比examined或者not exanined 更敏感

3.5.2 Diverse Fitness

• legality of execution result

  • 面向对象程序会有方法调用序列，结果要么是合法的要么是抛出异常。fuzzing会生成和获取新的方法调用序列，这些序列能够探索新的和合法的对象状态

• state machine of protocol implementations

  • 状态机包含状态和转换其状态的输入
  • 由于协议的复杂性，fuzzer通过往状态机里添加状态来推断状态机的状态。
  • 状态机从一个初始状态启动
  • fuzzer对当前状态进行变异来探索新的状态
  • 漏洞就基于状态机进行分析，来搜索有漏洞的转换

• safety policy of robotic vehicles

  • 交通工具引擎的温度
  • 当输入靠近规则的违反边界时，就会保留这部分的种子

• fitness of deep learning system

  • 深度学习系统的fuzzing是为了提高他们的鲁棒性和可靠性

  • 为此提出了多种fitness

    • neuron coverage
    • loss function for augmenting the training data
    • operator-level coverage

• validation log of android smartTVs

  • 验证日志是Android智能电视的执行信息
  • 这些日志被用来推断合法的输入，并用来提取输入的边界

• behavioral asymmetry of different testing

  • 对比测试中，通过观察两种不同实现，有相同功能，相同输入的情况下的不一致情况来发现漏洞

• alias coverage for data race

  • 目的是为了检查内核文件系统的数据竞争
  • data race是两个线程没有很好的同步去访问共享内存位置
  • alias coverage会去追踪两个可能互相交互的内存访问

• dangerous locations for bugs

  • 危险位置是有概率触发漏洞的代码区域
  • fuzzer可以针对这些位置进行测试来提高fuzzing的效果和效率
  • 对于并发缺陷，位置通常在原子操作违反，数据竞争，可疑的进程交互的区域
  • 对于非并发缺陷，可疑位置可以通过补丁测试，崩溃复现，静态报告，信息流检查得出。
  • 或者也可以从内存访问，sanitizer检查，commit历史记录获取

3.6 Evaluation Theory

• 评估能帮助提高fuzzing的性能

• 一个合格的评估需要包括

  • 有效的实验语料
  • 公平的评估环境
  • 合理的fuzz时间
  • 全面的对比指标

这部分总结如下：

• fuzzing理论缩小了输入空间和漏洞空间的差距
• fuzzing理论基于程序行为，比如bug arrival，状态转化，状态发现来构建fuzzing的过程
• 大部分的理论都在种子调度阶段构建
• 几乎所有的fuzzer保留种子都是使用遗传算法

4. Search Space of Inputs

fuzzer使用优化方法来解决生成输入的搜索问题。如果fuzzer可以减少输入空间的大小，就会提高fuzzing的性能。为了实现这个目标，fuzzer把一个输入的相关字节分好组，然后用特定的变异器对每个组进行定制的变异。假设一个输入包含$a\times b$个字节，并且被平均分为a个部分，相比$256^{a\times b}$的搜索空间，分成组后的搜索空间是$a\times 256^b$，相关的字节会出现在三个部分：一同构成同一数据结构，影响同一路径约束和语法上属于同一部分。变异器包含字节变异和块变异。就能够按需对相关字节进行变异了。

4.1 Byte-constraint Relation

对于大多数路径约束来说，他们只会被输入的一小部分所影响。如果一个fuzzer只变异相关的字节，fuzzing的性能就会大幅提升。比如说，要想满足a[2]==33的这一条件，如果只是随机变异的话，就需要生成$256^{11}$个输入（数组a长度为11），而如果知道只要变异第3个字节的话，就只需要256个输入。

在获取了字节-约束关系之后，一个很native的变异策略就是去随机变异这些相关的字节。另外一种方式是把相关的字节设置到0-255之间。然而这两种方法都不是很有效，因为他们不知道生成的输入的质量如何。如果推断字节关系的过程可以获取到程序比较指令的值，fuzzing就可以变异相关的字节，选择输入靠近约束的值。如果一个输入能够和路径约束匹配更多的字节，说明这个输入取得了进步。而且，fuzzing可以使用梯度下降算法去变异相关的字节，并且去求解路径约束。

4.1.1 动态污点分析。动态污点分析是常见的技术来构造输入字节和路径约束的关系。DTA在输入中做标记，然后执行的时候传播标签。如果一个变量获取到了标签，说明这个变量和数据是相联的。fuzzers利用DTA去构建输入字节和安全敏感点的关系。

4.1.2 关系推断。DTA需要很重的人工，也会由于不清晰的数据流导致不准确的关系。因为fuzzing需要用很多的测试样例来检查程序，一个轻量级的方法是在运行时推断字节的关系。

一个方法是，观察如果一个字节的变异是否改变了一个变量的值，比较指令的结果，或者是命中了分支。如果是的话，字节就会连接到变量，比较指令或者分支。

另一个方法是，使用深度学习来件里输入字节和分支行为的联系。

4.2 Concolic Execution

concolic execution把程序变量当作是符号变量，追踪路径的约束，并且使用约束求解器为一个特定的路径去生成一个具体的输入。换句话说，concolic execution通过求解路径约束来减小搜索空间。同时使用fuzzing和符号执行的技术叫做hybrid fuzzing。hybrid fuzzing使用fuzzing来执行程序路径，使用concolic execution去求解路径上的约束。fuzzing由于其随机的特性很难求解路径约束。虽然concolic execution在求解路径约束上很有效，但要把它应用到每条执行路径上还是很耗时的。因此，conconlic execution在fuzzing探索不到更多的路径的时候，才用来去求解fuzzing不能满足的路径约束。

hybrid fuzzing的一个改进是去找到最难的路径，然后交给concolic execution去求解。除了路径选择以外，hybird fuzzing的性能也可通过开发合适的约束求解器去提升。现阶段的SMT求解器在求解约束上还存在两个问题，一个是复杂约束，另一个是路径爆炸。为了缓解这个问题，约束求解器只符号化被输入影响的路径约束。另一个改进是发现许多路径约束都是线性的或者单调的。因此，约束求解器以一种灰盒的方式实现。比如，用线性函数去估计约束的行为。有趣的是，研究者开始使用fuzzing来求解路径约束。比如，JFS把SMT表达式翻译成一个程序，并且使用覆盖率导向的fuzzing去探索程序。当fuzzing生成的输入到达特定位置的时候，就解出了表达式。

约束求解器可以通过目标的特征来进行提升。对于嵌套条件，Pangolin提出了一种多面的路径抽象来求解嵌套路径约束。这种多面路径约束保留了历史约束的解答结果，并且复用历史结果来满足当前路径约束的可达性。比如说，为了求解14行的路径约束，输入需要先满足13行的条件。为了使用混合测试对需要高度结构化输入的程序进行测试，Godefroid首先把语法里的tokens符号化，然后使用上下文无关约束求解器去生成新的输入。

4.3 Program Transformation

program transformation的目的是去移除sanity 检查，来防止fuzzing不能发现更多的执行状态。移除掉这些检查，fuzzing可以探索程序里更深的代码，从而发现潜在的bug。当然移除这个也会引入很多bug位置的误报。不过这个可以用符号执行解决。因此，program transformation通过关注可能会导致漏洞的输入来缩小搜索空间。

4.4 Input Model

许多应用需要高度结构化的输入，比如协议的实现，文本对象模型引擎，javascrip 引擎，pdf阅读器，系统调用，编译器等。输入模型指定了构造高度结构化输入的规则，包括结构，格式和输入的数据约束。为了生成满足规则的输入，生成过程会严格按照指定的操作来。如果一个输入违反了目标程序的语法或者语义，输入会在早期被程序所丢掉。换句话说，输入空间受控于输入模型。

4.4.1 Accessible models or tools 许多模糊测试基于现有的输入模型或者现有的工具来生成合法的输入。根据空规范来生成输入需要大量的工程实现。而且，由于规格解析起来比较复杂，这个过程很容易出错。研究社区开源了一些工作能够生成高度结构化的输入，比如QuickCheck，ANTLR。比如NAUTILUS和Superion基于ANTLR生成输入。然后，NAUTILUS和Superion使用代码覆盖率来优化变异过程。在一些场景中，输入模型可以是生成的输入的类型（比如API参数的类型或者物理信号）比如，cyber-phsical 系统中的驱动器的数据就可以是二进制值，开或者关。

4.4.2 Integration of Implementation 另外一种方法是把fuzzing和目标应用软件整合在一起。这种整合可以让fuzzing去检查目标引用的特定属性。比如，TLS-Attachker创建了一个框架，可以基于每个段的类型来生成输入，并且操纵协议信息的顺序。这个框架包含了完整的Transport Layer Security协议实现。

4.4.3 Intermediate Representation 一个更复杂的方法是将输入模型转换为IR。对于高度结构化的输入，基于原始输入文件来变异很难保留原来的语法和语义。因此，研究者将原始文件翻译成IR，相对而言更简单和统一。Fuzzer对IR进行变异，然后将变异后的IR转换为原始输入格式。这种变异策略能够保存语法和语义的正确性，并且生成更多样的输入。比如，IR被用来测试数据库管理系统，DOM 引擎或者fuzz不同的语言处理器。

4.5 Fragment Recombination

基于输入规格，另一种生成输入的方式是通过碎片重组的方式来生成新的输入文件。fragment recombination的基本思想是把输入文件分成许多小块，然后通过组合这些小块来生成新的输入文件。每个小块都满足输入的规格，所以重组之后的文件仍然是语法正确的。理想情况，重组后的输入会执行一条新的执行路径或者发现新的bug。

fuzzer首先会将输入文件解析为一棵树，比如抽象语法树，这样可以保留语法正确性。为了合适地解析输入，输入语料库的东西需要是合法的。一种获取合法输入预料的方式是从网络上下载。除了合法性，fuzzer还需要收集之前导致过问题的输入。基本的假设是一个新的bug也可能仍然在，或者靠近之前发现bug的地方。导致问题的输入已经走过了复杂的触发非法行为的执行路径，因此重新组合这部分路径可能会走相似，或者旁边的路径，能够帮助fuzzer发现更深的代码区域。第二阶段，输入文件会被拆分为很多碎片放在碎片池子里。因为fuzzer会将输入解析为AST，碎片可以是包含非终结节点的子树。因此，fuzzer重新组合满足语法的兼容的碎片，一般是通过随机选择，基因算法或者机器学习。相比于语法正确性，语义正确性也同样影响fuzzing的有效性。例如，为了生成语义和语法正确的JavaScrip输入，CodeAlchemist 对带有约束的碎片进行标记。也就是不同的碎片只在满足约束的情况下才进行组合。

4.6 Format Inference

如果拿不到输入模型，生成合法输入的一个不错的方案是去推断输入的格式。而且，一个输入模型只能生成特定格式的输入。为了支持更多格式的输入，开发者需要利用新的输入模型，并且选择合适的输入模型来生成输入。因此，格式推断比基于模型的方法可扩展性更高。

4.6.1 基于语料

为了推断格式，一个直接的方法是从合法输入的语料中学习。由于缺少输入模型，研究者构建了端到端的深度学习模型去替代输入模型。RNN是更好的深度学习模型来生成结构化的输入。然而，这个替代的方法可能会生成很多非法输入。比如，对于DeepFuzz来说，生成合法输入的比率是82.63%。为了提高这个比率，需要重新处理下训练数据。比如，当生成PDF文件时，训练数据应该是包含PDF对象的序列而不是文本数据。至于智能合约，训练数据就是一序列的交易。相似的是，lipfuzzer训练对抗语言学模型来生成声音命令，其中训练数据是通过语言学结构来表示的。同时，fuzzing可以基于合法输入语料来生成上下文无关文法。生成的语法可以用来生成高度结构化的输入。

4.6.2 基于覆盖率 基于语料库的方法需要有覆盖所有输入规格的训练数据。而且目前的技术还不是很practical。同时，这些技术没有使用到内部执行时的状态。可能会导致较低的代码覆盖率。输入的格式说明了不同字节的关系。因此，基于代码覆盖率，fuzzer推断byte-to-byte关系来加速fuzzing的过程。比如，GRIMOIRE，使用代码覆盖率来推断目标程序所需要的格式。他的目的是去识别一个输入的格式边界。具体来说，他会去改变输入中的一些字节，然后检查这些变化是否会导致不同的代码覆盖率。如果代码覆盖率和之前一样，那些字节就可以随机变异，如果不一样，就要小心地变异那些字节。Profuzzer首先定义了6种数据类型包含大多数的输入内容。然后基于边覆盖率的分布，他去推断每个字节的类型，合并属于同一类型的连续字节。

4.6.3 函数编码 和前面提到的针对输入的方法不同，一些fuzzer搜索编码了输入格式的代码区域。因为这些代码区域和结构化的输入有关系，fuzzer在对格式编码前做变异。虽然测试程序的源码可能没法获取到，但是有相应的实现可以生成良好的结构化输入。比如，社区中开源了很多工具可以生成高度结构化的数据。对于物联网设备，他们中的大部分都是通过companion applications来控制的，能够生成与目标设备通讯的信息。通过定位到与编码格式相关的代码区域，就可以实现对函数参数或者计算格式的指令的变异。比如说，IoTfuzzer会去hook掉一些函数，然后对这些函数的参数进行变异。

4.7 Dependency Inference

格式推断主要是为了满足语法要求，但有可能生成带有错误数据依赖的输入。比如，在fig6的代码片段2中，一个错误发生在2-5行，因为方法errf没有定义。许多程序的输入需要有正确的数据依赖，通常包含一个语句的序列。比如，内核代码里的系统调用序列，应用里的API，面向对象程序里的对象处理，只能合约的abstract binary interface。另一方面，大部分的应用需要在使用数据前进行定义，另一方面，一些语句的输出可能是其他语句的参数。

4.7.1 document or source code

序列的数据依赖通常通过静态分析来推断。因为许多应用都有文档或者源码来解释他们的接口。研究者基于这些资源来推断他们的依赖。这些资源包含了如何使用接口和使用接口的预先条件。当fuzzing生成的输入包括接口时，fuzzing也要去生成接口的前置条件。否则，生成的输入会在前期就被reject掉。因此，如果有测试程序的源码，一个好的方案是结合静态分析和动态分析。

4.7.2 Real-world Program

许多真实的程序实现代码去调用接口，这部分的代码已经考虑接口的数据依赖。因此，fuzzing可以生成新的程序来基于这些真实程序的切片来调用接口。同时，数据依赖可以通过分析真实程序的日志所得到。执行的日志包含了接口的顺序。而且，执行的日志隐含了接口间参数的数据依赖信息。为了获取显式或者隐式的信息，当执行真实程序的时候，fuzzing可以hook掉每个接口，然后记录相应的信息。

Gap2：输入空间的减少依赖于如何把输入字节按照语法/语义分组。对字节进行分组的好处是能提高fuzzing探索更多执行状态的效率。也就是fuzzing更可能去满足路径约束，从而发现更深的代码区域。

5. Automation

自动执行是应用fuzzing理论和减少输入空间方法的基础。fuzzing重复的执行程序，并且监控程序的执行，看有没有异常，然后异常会被进一步地拿去验证是否是bug。因此，为了成功的fuzzing，需要满足三个要求：

• 自动地，重复地运行程序。大部分的fuzzer能够成功测试命令行程序，但是不能直接用来测试其他的程序，比如硬件、多语言的软件。
• 自动识别潜在的bug。现阶段使用crash作为潜在bug的标志。然而许多的bug的表现形式并不是crash，比如data race。
• 高速fuzzing。高的执行速度意味着可以在有限的时间内跑更多的测试样例，从而更有机会发现缺陷。

5.1 Automatic Execution of PUTs

fuzzing被用在各种的应用中，需要不同的工程实现去自动化fuzzing的过程。这个部分主要介绍几种fuzzing成功自动化测试的应用。

5.1.1 command-line Programs

fuzzing在测试命令行程序起到了巨大的成功。fuzzing在子进程中运行测试程序，并且喂给程序所需要的选项和输入。为了提高执行速度，fuzzing不重现执行程序的所有步骤。而是，克隆子进程，可以跳过预处理的步骤，比如把程序文件加载到内存的步骤。通常，fuzzing在整个过程中，只需要一个命令行选项作为输入。就是所，所有生成的输入都是基于该选项。因为不同的选项指出了不同的代码覆盖率，一个完整的测试需要遍历所有命令行选项。一个高效的方案是，如果一个输入对于其中一个选项是非法的，就跳过测试所有剩余的选项。这个操作是基于一个重要的假设：如果输入对于某个选项是非法的，他对于其他选项也是非法的。

5.1.2 Deep learning Systems

对深度学习系统的模糊测试类似于测试命令行程序。DLSs也是用fuzzing生成的输入来进行测试，然后fuzzing会尝试去生成fitness更好的输入。输入有训练数据，测试数据，或者基于不同目标的深度学习模型。从另一个方面来说，fitness可以是神经元的覆盖率，损失函数或者操作数级别的覆盖率。对于测试深度学习系统，fuzzing不仅仅检查缺陷，也检验模型的鲁棒性。

5.1.3 operation system kernels

相比命令行程序，操作系统内核更复杂。内核中有很多中断和内核线程，导致不确定的执行状态。为了像fuzz命令行程序一样fuzz内核，fuzzer使用hypervisor去运行目标内核。同时，利用Intel Pt获取代码覆盖率。虽然这种方式可以fuzz各种内核，并且还能获取反馈，但是需要手工构建语法和语义正确的输入。因为内核的输入包括文件系统镜像或者一序列的系统调用。fuzzer，可以以一种更加轻量的方式去测试内核。在分析或者推断系统调用的依赖后，fuzzer会去生成一序列的系统调用运行在目标内核上。然后fuzzer监控系统调用的序列是否会导致系统崩溃，也就是能不能发现潜在的bug。另一种方式去fuzz OS内核是去模拟外部设备。因为内核要和模拟的设备交互，就可以测试内核里的驱动。

5.1.4 Cyber-Physical Systems

Cyber-Physical System包含两个紧密连接的组件。计算元素和物理过程。一个广泛使用的是Programmable Logic Controller（PLC），能够控制actuator去管理物理过程，并且从传感器接收输入。当fuzzing CPS时，fuzzer可以替换PLCs，并且通过网络直接发送很多命令到制动器。另外一种方式是检查PLC的控制应用和运行时状况。然而，PLC二进制不能像命令行程序一样进行fuzz。因为PLC应用有很多种的二进制格式，而且和物理组件有很复杂的通信。因此，自动化这些应用的方法很多。基于PLC二进制和他们开发平台的分析，是有可能自动化的fuzz PLC二进制。

5.1.5 Internet of Things

物联网设备的fuzzing包含模拟和网络级的测试。模拟器可以不在硬件上执行程序，而原本是在IoT固件上运行的。在模拟器的帮助下，fuzzer可以以灰盒的形式去跑目标程序。另一方面，网络级别的fuzzing会以黑盒的方式去检查IoT设备。因为IoT设备可以通过网络和外界交流，fuzzer自动通过发送信息给IoT设备，然后等待IoT设备的执行结果。通过对请求进行分类，fitness就是分类的数目，也就是目的是去探索更多的分类。

5.1.6 Applications with Graphical User Interface

有GUI界面的程序运行比命令行程序要慢很多。而由于执行速度是fuzz中一个很关键的一个部分，所以，自动化GUI程序的方法通常是用一个更快的方式，比如以命令行的形式来替代GUI来执行。比如说，fuzzer可以对用户界面的交互进行建模，然后为安卓应用生成事件序列。而且，fuzzers可以利用harness，也就是准备好了执行的上下文，来直接触发GUI程序的目标函数。

5.1.7 Applications with Network

一些应用通过网络来接收输入，比如智能合约，协议的实现，云设备，安卓原生系统服务，自动驾驶工具。因此，可以本地生成输入，远程执行目标程序。自动测试的效率依赖于生成输入的值来以及反映执行状态的fitness。比如，智能合约的输入是一序列的合约交易，不同账号的信息。当收到交易时，智能合约中的函数就会在区块链的框架中执行。

5.2 Automatic Dectection of Bugs

许多安全bug可以被利用来控制系统，泄露隐私数据，或者导致服务器崩溃。检查bug的难点在于bug是不可预知的。一个检查器不知道bug的地方，在测试之前，也不知道目标程序有没有bug。因此，在fuzzing的过程中记录潜在的bug是很重要的。通常来说，fuzz是利用crash来发现bug的，或者基于bug的模式来设计指示器。这个部分主要介绍六种能被fuzzing发现的bug，包含memory-violation bugs, concurrency bugs, algorithm complexity, Spectre-type bugs, side-channels, and integer bugs.

5.2.1 Memory-violation Bugs

内存违反类漏洞是最古老也是最严重的漏洞。一个程序如果是内存安全的话，那么他的指针不能乱指。违反内存安全可以分为两类，一类是空间，一类是时间。空间就是我们都知道的越界。时间则是UAF那类的。就比如上面那个代码。虽然现在有许多办法去缓解内存违反的影响，大部分都没有用于实际，因为性能开销高，兼容性差，鲁棒性低等原因。

缓冲区溢出是一种内存安全漏洞，会写几个字节越界。Dowser是一个检查缓冲区溢出漏洞的工具，它认为缓冲区溢出主要是发生在循环的数组中的。为了检查循环中的缓冲区溢出，dowser对循环中访问缓冲区的指令进行打分，优先选择执行打分高的指令的输入。然后使用污点分析和concolic execution去求解路径约束。由于Dowser针对循环中的数组，只有一小部分的指令会被插桩。这样就提升了污点分析和concolic execution的执行速度。

UAF漏洞是另一种内存安全漏洞，主要包括三个步骤：1）分配内存给一个指针，2）释放该内存，3）重用指向那个内存的指针。这个漏洞模式让UAFL去生成输入能够覆盖潜在的UAF序列。潜在的UAF序列是通过静态的状态机分析来获取的。

5.2.2 Concurrency Bugs.

另外一种严重的安全漏洞是并发漏洞。这类漏洞可以分为两类，deadlock and non-deadlock。死锁漏洞发生在程序中的两个操作在互相等待对方释放资源。非死锁漏洞又可以分为两类，包括atomicity-violation 和 order-violation。原子操作违反漏洞是违反了一个代码区域的确定的顺序。比如上面的a图中，线程1调用了fputs函数，参数是p->info，结果线程2在执行fput之前把p->info置为空了。

顺序违反漏洞是两个访问内存操作的顺序错了。比如b图中，线程1在第3行才创建线程，线程2在创建线程前就用了mThd。

并发漏洞同样也会导致内存违反，比如UAF和double free。

一种发现死锁漏洞的方式去在lock order graph中发现环。因为每个节点表示一个锁，如果出现环就说明有死锁了。为了提高环的检查效率，MagicFuzzer迭代式地在图中移除不在环里的锁。然后基于随机调度器检查剩下的环。对于原子操作违反，ATOMFUZZER观察到一个经典的bug模式，一个原子块里的锁会重复获得，并且被俩个线程释放。具体原理有些复杂，不详细解释，可以看文章。

并发漏洞是由于线程不正确的切换导致的。检测并发漏洞的难点在于并发程序中有很多的切换，会导致状态爆炸的问题。CallFuzzer基于一个观察去缓解状态爆炸。一些切换是相同的，因为他们是来自于非交互指令的不同执行顺序。相同的切换意味着他们会产生相同的状态。CallFuzzer随机地选择一些没有互相交互的指令的线程，然后同时执行这些指令。因此，CallFuzzer可以高效地发现不同的切换。

5.2.3 Algorithmic Complexity

算法复杂性漏洞会发生在：当导致算法最坏的情况发生时，会严重影响算法的性能，导致拒绝服务攻击。比如上图的快速排序的例子。给定不同的数组，上面的算法会有不同的复杂性。比如给定数组[8,5,3,7,9]算法会执行37行这么多的代码。而如果数组是[1,5,6,7,9]，就会执行67行这么多的代码。增加的行数需要更多的计算资源。因此，最坏情况可以被攻击者利用来构造DoS工具。因此，SlowFuzz 通过指导模糊测试去执行更多数目的指令，来发现AC漏洞。相似的，HotFuzz，通过最大化individual method的资源消耗来检查java方法里的AC漏洞。MemLock是基于边覆盖率和内存消耗来检查ACbugs。上述提到的fuzzer直接生成AC bug的poc。相反，Singularity基于最坏的输入总是遵循着某种特定模式来生成程序。生成的程序是为了来生成输入？

5.2.4 Spectre-type Bugs

幽灵漏洞是一种微体系结构攻击，利用错误预测的分支来控制内存访问。比如，图10里，攻击者可以发送界内值到input变量里，就会训练分支训练器去推测第2行的条件是否一直是true。当攻击者发送越界值给输入，预测器就会错误预测分支的行为，导致第3-4行被推测执行。由于输入不满足第2行的条件，就会导致3-4行的出现越界读。因此，Specfuzz对目标程序进行插桩，来监控推测执行，可以强制执行预测错误的代码路径。然后，预测错误路径的非法内存访问就会被触发。

5.2.5 Side Channels

侧信道bug通过观察系统的非功能行为（执行时间）来泄露隐私信息。比如，if(a>0){} else{}这样的语句中，a是隐私数据，可以通过观察两个分支执行的时间来确定a的值是大于0还是小于0。一种特殊的侧信道是交JIT-induced side channels，是由于Just-In-Time优化导致的。和前面提到的幽灵漏洞很像，可以重复地运行程序来训练JIT编译器去优化两个分支的执行时间。然后，其中一个训练分支的时间就会和没训练分支的时间差很多，这样就足够区分了。最后，变量a的值就被泄露了。

5.2.6 Integre Bugs

整数溢出漏洞（上溢/下溢）发生在算术表达式的值超过了机器类型的范围。另一方面，整数转变漏洞发生在把一个整数类型转换成另一个整数类型里。为了检查整数漏洞，SmartFuzz会根据不同的整数漏洞添加特定的约束到符号模拟中。然后符号求解器求出可能触发整数漏洞的具体输入。

5.3 Improvement of Execution Speed

执行速度对fuzzing而言很重要，因为可以在有限的时间里跑更多的测试样例，也就能有更多的机会去发现缺陷。为此，研究者在提高fuzzing速度上做了许多工作，主要有二进制分析，优化执行过程，应用定制技术。

5.3.1 Binary Analysis

fuzzing主要用静态插桩来获取执行状态，因为静态插桩能提供给fuzzing更高的执行速度。一个广泛使用的静态分析工具是LLVM，是在编译的时候插桩。当涉及到闭源程序是，fuzzing就受限于二进制分析。问题是二进制插桩工具（Dyninst）在应用到fuzzing的时候产生了很高的运行开销。为了提高执行速度，RetroWrite使用静态二进制重写的方式。通过利用代码无关代码的relocation information信息来插桩汇编文件。因为RetroWrite可以插桩内联代码块，所以减少了运行开销。虽然很快，但是只支持64位的位置无关二进制。为了能够让fuzzing运行时开销低并且扩展性好，FIBRE通过4个修改IR的过程来插桩。这四个步骤是静态重写，inlining，追踪寄存器的liveness，考虑不同的二进制格式。上诉的重写技术只重写二进制一次，可能会导致unsound，尤其是对于去掉符号表的二进制。为了解决这个问题，STOCHFuzz提出了增量和随机重写技术。他会重写目标二进制好几次，逐渐修复之前几次重写结果导致的问题。

5.3.2 Execution Process

执行速度也可以在执行的时候来提升。UnTracer观察到大部分fuzzing过程中生成的测试样例并不会发现新的覆盖率。这说明追踪所有的测试样例，会导致严重的运行时开销。因此，UnTracer只追踪会增加覆盖率的测试样例来提高执行速度。在基本块的开头插入终端来实现的。当检查基本块的时候，UnTracer会把基本块的插桩移除，然后执行就不会在这个基本块中断了。由于基本块覆盖率损失了执行状态的信息，CSI-Fuzz使用边覆盖率来提高UnTracer。同时，Zeror通过选择性的在UnTracer和AFL插桩的二进制中切换来提高效率。

对于混合模糊测试，concolic execution也被用来求解路径约束。然而，concolic execution中的符号模拟在构建路径约束的时候很慢，也是拖累混合测试的一个主要因素。QSYM通过一些耗时的模块来缓解性能瓶颈，比如IR翻译和快照。然后，只收集和求解部分的约束。虽然，QSYM生成的输入可能不是路径约束最准确的解，但是QSYM使用fuzzing去搜索合法的输入。Intriguer观察到QSYM仍然有很多性能瓶颈，因为求解了很多没必要的约束。Intriguer对更相关的指令进行符号模拟，这些更相关的指令是由动态污点分析来确定的。除了插桩和混合模糊测试，另外一种优化执行速度的方式是并行模式。Xu发现AFL在120核的时候运行速度很慢，他们设计了新的操作原语来提高执行速度。

5.3.3 Variour Applications 除了一般的应用以外，fuzzing也被用来检测目标的缺陷，比如IoT，内核和虚拟机监控器。由于这些目标，通常有特殊的特征，fuzzing会根据目标的特性定制，来实现更高效的测试。

虽然模拟是一种fuzz IoT固件的好方法，但是全系统的模拟会导致很低的吞吐量。全系统模拟的运行开销主要来自把虚拟地址翻译为内存访问和系统调用的模拟。FIRM-AFL通过结合用户模拟和全系统模拟来缓解开销，并且主要以用户模式来运行程序。为了fuzz VMM，Schumilo设计了一个OS和快速快照存储机制来高效地fuzz。对于文件系统，变异整个磁盘镜像降低了fuzzing的吞吐率，因为一个镜像很大。为了解决这个问题，JANUS只变异种子镜像的元数据，从而提高整个吞吐率。OS内核也会通过外围设备被攻击，比如发生在硬件和内核边界的漏洞。为了检测设备和驱动的通讯的缺陷，PeriScope提出了一种基于内核页表错误处理机制的fuzz。Windows应用和linux不同，因为他们大量使用图形化的界面，并且windows缺少方法去快速地克隆进程。WINNIE会生成一个harness去运行应用，来替代图形界面。同时，还未windows实现了一个fork来提高克隆进程的效率。BigFuzz把数据集中型扩展计算应用(DISC)转换成相似于语义的程序。因为DISC有很高的延迟，所以这样就可以测试生成的程序来提高运行速度。

gap3：要对程序自动执行，需要对这些应用有很深的了解。如果要设计自动记录安全错误的指标，需要对这些错误的属性进行深入地调查！

6. Directions of Future Research

**更多敏感的指标。**研究者已经做了很多功夫在提高代码覆盖率的效果和效率上，尤其是代码覆盖率的敏感性。最近，研究人员意识到代码覆盖率在发现漏洞上有局限性。因此，他们通过引入信息来扩展代码覆盖率。未来可以通过分析漏洞，并且基于漏洞的特征去检查他们。

**更复杂的fuzzing理论。**大部分的工作都是种子调度上做文章，然后其他的工作在别的fuzzing模块上做。由于fuzzing过程挺复杂的，很少有工作去重构整个fuzzing的流程。数学化地构建整个fuzzing的过程是很有意义的。也是有可能去制定超过一个fuzzing的过程的，比如利用博弈理论去同时考虑种子调度和字节调度。更大的方向是去考虑fuzzing的理论的缺陷。另一方面，用多种类型的fitness也是另一种构建更复杂fuzzing理论的方式。比如，未来工作就有可能去同时考虑漏洞的存在和状态切换来构建fuzzing的过程。

sound evaluation（因为模糊测试是一种complete的工具，他能给出漏洞的poc来证明漏洞，所以需要去证明他的soundness） 很少工作研究评估的soundness，但是没有下一个固定的结论。这些工作只是个sound evaluation提了个建议，比如说time budget或者其他评估指标。还有很多问题需要去回答。我们能够使用合成的漏洞或者真实漏洞当作是评估的语料吗？数据的测试能够区分两种fuzzing技术吗？要多长时间才停止fuzzing的过程？我们如何评估特殊的目标应用，比如硬件，当不存在其他对比的fuzz的时候呢？

可扩展的输入推断 当使用输入格式或者数据依赖时，fuzzing的效率会得到极大的提升。静态分析广泛用于格式推断和数据依赖推断。然而，静态分析是应用特定型的，需要考虑应用的特征来设计。现阶段，动态分析主要做的是格式推断，几乎没有工作做数据依赖推断。使用动态分析推断的方法扩展性要比静态分析好。未来工作也许会使用动态分析来推断数据依赖。

**高效的变异操作符。**几乎所有的fuzzer都在fuzzing的过程中使用固定的变异器。fuzzer根据目标应用的特征提前设计好了变异器，在fuzzing的过程中变异器不会有变化。有一些工作试图优化变异调度，但是没有工作是做可变化的变异器。在fuzzing的过程中，使用一个进化的变异器是否能够提高性能？因为变异器调度和字节调度紧密相关，所以可以考虑基于字节调度来设计变异器。而且，变异器对于高度结构化的输入可能有不同的属性。因此，对于高度结构化的输入的变异调度也值得研究。

**更多类型的应用。**fuzzing已经在命令行程序取得了比较好的成果。研究者也开始对更多类型的应用进行fuzz。由于不同应用的复杂性，fuzzing在检查更多类型的应用上效果不是很好。比如说，有工作去探索fuzz cyber-physcial系统，但是很难发挥fuzz的能力。因为执行速度很慢。一个潜在的方向是，对于那些比较难fuzz的程序，先提高他们的执行速度。

**更多类型的漏洞。**Fuzzing已经在内存漏洞，并发漏洞和算法复杂性漏洞上取得了很好的成果。然而在检查其他类型的漏洞上效果还不是很好，比如提权和逻辑漏洞。检测这些漏洞的难点在于如何设计一个漏洞指示器（indicator）。因为指示器反映了漏洞的特征，指示器的设计需要研究人员对fuzzing和目标bug有很好的理解。比如，当触发了逻辑漏洞时，程序运行并不会产生异常。为了设计好的逻辑漏洞指示器，需要对用来开发代码的功能要求有很深的理解。