2019 A Review of Machine Learning Applications in Fuzzing

摘要

在过去的几十年中，模糊在改进软件开发和测试方面发挥了重要作用。最近对模糊化的研究集中在机器学习（ML）的应用上，为克服模糊化过程中的挑战提供了有用的工具。本文综述了最大似然法在模糊化中的应用研究现状。具体来说，本综述讨论了ML在模糊化中的成功应用，简要探讨了遇到的挑战，并推动了未来解决模糊化瓶颈的研究。

内容

在本次调查中，我们重点关注三种主要的ML类型，每种类型都适用于不同类型的任务。监督学习用于训练模型以识别给定数据点的类标签，例如图像是否包含特定对象。这种类型的ML需要数据集，其中每个数据点都有一个明确的标签。无监督学习用于训练模型，以发现数据点之间的模式或相似性，而不是标记类。当数据没有显式标签时，使用这种类型的ML。强化学习用于训练模型（通常称为管理者），以便在环境中采取一组最佳行动。这种类型的ML会奖励代理在环境中执行的每一个操作。与监督学习类似，奖励充当代理的标签，并提供要采取的最佳行动的指示。因此，可以训练代理人采取一系列行动，从而获得最高的回报。这三种类型中的每一种都可以采用一种特殊形式的ML，称为深度学习。深度学习是指一种分层学习，可用于学习一组数据点的基本特征和结构[25]。
Types of Fuzzers：基于突变、基于生成和进化。mutation-based, generation-based, and evolutionary.

Pre-Fuzzing: Program Knowledge.
Stage 1: Generate Inputs.
符号执行是一种静态分析技术，可以帮助生成新的输入，从而增加模糊器的覆盖范围。虽然符号执行不是一种模糊器，但Driller[56]和SAGE[23]等工具将模糊和符号执行结合起来，以改进输入生成。我们在这里单独讨论符号执行，因为它可以为基于变异和进化的模糊器生成新输入提供信息。高成本意味着必须巧妙地使用符号执行；它通常用于寻找通过随机探索难以找到的路径。为了降低这一成本，模糊器将符号执行与其标准输入生成技术配对[23]。符号执行引擎可以通过“跟踪”有趣的输入来限制路径，例如。G只允许新的符号状态在有限数量的分支中偏离输入。然而，计算成本和路径爆炸仍然是重大障碍。大量的研究工作正试图在符号执行中解决这些研究挑战[31,43,56]。
Stage 2: Select Inputs.
无论是智能地调度输入，减少活动输入的数量，还是保持输入较小，这些技术都试图减少模糊器发现新的有趣程序状态所需的时间。然而，有效利用fuzzer有限的计算时间仍然是一个研究挑战。在下一个阶段中，模糊器发送选定的输入，监视程序的结果操作，并识别感兴趣的程序状态。
Stage 3: Monitor Program.
模糊程序需要关于如何对程序进行检测以及什么构成有趣的程序状态的程序知识。人类用户通常会提供这些信息，但如何定义一个有趣的程序状态仍然是一个研究挑战。在脆弱性评估案例中，哪些可观察到的行为与识别缺陷或脆弱性最相关？一旦fuzzer识别出一个有趣的程序状态，它就需要向用户提供该状态的描述以供分析。程序状态描述因fuzzer而异。例如，在崩溃时，一个fuzzer可能只提供导致崩溃的输入，而另一个fuzzer可能提供完整的内核转储，即在故障点捕获程序内存。评估之后（下一阶段），该信息可能会指导进一步的模糊迭代。
Stage 4: Evaluate Inputs.
许多模糊程序使用代码覆盖率来衡量输入的效用：如果输入导致执行新的代码部分（通常是新的基本块），则该输入增加了覆盖率，并获得了较高的评级。libFuzzer工具使用一个类似的度量，即数据覆盖率，如果在代码中先前探索过的比较中出现新的数据值，该度量也会对输入进行很高的评级。一些模糊程序使用bug发现作为度量；导致崩溃的输入被评为高级别。
Post-Fuzzing: Interesting Program States.
在模糊化过程之后，用户分析模糊器输出的有趣的程序状态。这个过程通常是高度手工的，并且得益于软件工程相关领域的研究。对于每个输出状态，用户分析该状态以确定该状态中有趣行为的根源。通常，用户在程序执行相关输入时手动观察，并希望确定根本原因。然后，用户决定根本原因是新的缺陷还是漏洞。模糊程序通常输出大量有趣的程序状态。用户必须进行分类，以确定哪些有趣的程序状态值得进一步调查。不幸的是，输出程序状态通常具有相同的根本原因。更糟糕的是，具有相同根源的国家可能会出现截然不同的情况。例如，内存损坏漏洞可能会导致程序的许多不同部分崩溃，内存映像大不相同，因为无法立即观察到该漏洞的影响。一些自动化工具试图消除fuzzer输出的重复数据[28]或根本原因，但这些工具往往不完善，分类和根本原因分析仍然是研究挑战。

模糊比较

为了帮助判断fuzzer效用，Klees最近提出了一个fuzzer比较框架[30]。Klees呼吁通过指定来控制比较：基线模糊器、目标程序的基准套件、性能指标、与基线相当的配置参数，以及足够数量的统计测试试验[30]。具有已知缺陷的小数据集可用于以这种方式比较和验证模糊器。然而，不幸的是，这些比较在计算上是昂贵的，并且，如前所述，结果不一定是泛化的。实际上，在为这个框架开发出全面的基准之前，用户将不得不依靠自己的直觉来指导决策，决定将哪个fuzzer用于特定的程序，如何配置或调整该fuzzer，以及该fuzzer是否表现得足够好。有效的模糊比较仍然是一个重大的研究挑战。

机器学习在模糊化中的应用

ML已被用于在模糊化过程中生成新的输入，并在较小程度上改进后模糊化。无监督学习在输入生成中得到了最成功的应用，如AFL[34]等模糊工具将遗传算法（GAs）集成到输入生成过程中。最近也有监督学习和强化学习（RL）在输入生成中的应用[4,5,9,51]。此外，所有三种类型的ML都已应用于符号执行[10,40,50,64]，主要用于减少约束方程的求解时间。监督和非监督学习都已应用于后模糊过程，主要用于碰撞分类和根本原因分类[15,33,39]。有趣的是，我们知道在两个领域没有研究：输入最小化和语料库最小化。这些模糊化过程往往不是大的瓶颈，这可能是缺乏研究的原因。
Generate Inputs
遗传算法。输入生成最常用的ML技术是GAs[17,18,21,34,37]。GAs是一种受生物进化启发的无监督ML，通常是进化模糊器中的核心输入生成算法。使用遗传算法时涉及3个主要步骤：1）生成少量基本输入，2）对输入执行转换，以及3）测量转换输入的性能。根据所选指标，在性能最好的输入端重复此过程。在模糊器的情况下，输入的基本群体由一组种子程序输入组成。遗传算法将变异这些种子输入，以探索代码空间，目的是发现代码中的新路径。由于能够在先前成功输入的基础上构建，GAs已成功用于输入生成。
虽然传统的代码覆盖率是适应度函数最常用的指标，但也使用了更高级的启发式方法，如动态马尔可夫模型（DMM）启发式方法[55]。在这项工作中，程序控制图被表示为一个马尔可夫过程，即控制图各边具有转移概率的随机过程。DMM启发式使用马尔可夫模型和转移概率创建适应度函数。与代码覆盖率不同，此设置允许更精确地控制fuzzer，将其引导到代码中可能包含bug或缺陷的特定部分。适应度函数的选择是模糊行为的一个重要决定因素，因此，开发新的适应度函数来诱导期望的模糊行为可能是一个很有前途的研究领域。特别是，允许对模糊程序进行更细粒度控制的适应度函数对于特定的模糊目标可能更为有利。此外，策略性地组合或交替使用多个指标也可能有助于实现模糊化目标。

深度学习和神经网络。深度学习（DL）和神经网络（NNs）已应用于输入生成，特别是用于改进基于生成和基于变异的模糊器。递归神经网络（RNN）[36]是应用于模糊化的最常见的DL方法。特别是，长期短期记忆（LSTM）[36]网络，RNN的一种变体，已被研究用于输入生成。在一项研究中，Godefroid等人使用LSTM为基于生成的模糊器中的PDF文件创建输入语法[24]。LSTM在许多类型的序列生成任务中表现出了希望[27]。然而，Godefroid等人发现，模糊化和LSTM输入语法学习的目标经常相互冲突：LSTM倾向于生成格式良好的输入，而模糊化者则致力于生成探索新程序状态的示例输入。为了避免这一悖论，使用了抽样策略来挑选LSTM生成的输入，最终创建了一个在格式良好和格式错误的输入之间具有强大平衡的输入语法。实验结果表明，使用ML生成输入语法对于提高代码覆盖率是一种很有前途的技术。
在另一项研究中，Rajpal等人将DL集成到AFL中，通过选择要变异的输入字节来增加模糊覆盖率[5]。NN用于生成热图，指示在任何特定字节发生变异时增加代码覆盖率的预测可能性。比较了用于生成热图的四种不同的序列学习架构：1）标准LSTM，2）双向LSTM[36]，它向前和向后处理输入序列，3）Seq2Seq[14]，它将一个序列转换为另一个序列，4）Seq2Seq的一种变体，它使用注意机制来关注输入的最重要部分[3]。虽然在某些情况下，每个模型都增加了代码覆盖率，但总体而言，标准LSTM模型的性能略优于其他模型。实验上，DL增强AFL在ELF、XML和PDF格式上优于标准AFL，而在PNG格式上，标准AFL优于DL增强AFL。
生成输入的另一种方法是对程序行为建模，使用模型选择最有希望的输入。NEUZZ方法使用浅层神经网络将程序行为建模为光滑连续函数[51]。训练神经网络，根据种子输入预测程序的分支行为。实验发现，训练过程中产生的梯度，特别是较大的梯度，有助于识别哪些输入字节控制分支行为。NEUZZ利用这些信息来指导fuzzer突变，使其在一些程序上在实验上优于标准fuzzer，包括AFL和Angora。
Chen等人还通过Angora fuzzing工具对程序行为进行建模[12]。Angora使用离散函数表示从程序起点到特定分支约束的路径。然后在函数表示中的小离散间隔上执行梯度下降，以找到满足约束的一组输入，并通过该特定分支移动程序。总的来说，该方法证明了快速解决分支约束的能力，并且在某些程序上的实验性能优于AFL和符号执行。
Cheng等人[13]采用了另一种使用DL生成输入的替代方法。该方法使用RNN通过程序预测新路径。然后将这些路径输入Seq2Seq模型，该模型为模糊器生成新的种子输入，以执行预测的路径。这项初步研究表明，实验生成的语料库增加了PDF、PNG和TFF格式的模糊代码覆盖率。
用于输入生成的DL和NN应用显示出良好的前景，但在更普遍的使用方面仍然存在障碍。首先，DL模型需要大量的训练计算时间，因此训练很可能无法实际集成到模糊化过程中。另一种方法可能是为单个项目训练单个模型，但这也可能不切实际。许多研究试图缓解这些问题。例如，Rajpal等人通过在模糊化开始之前仅在一小部分输入上训练神经网络来规避训练成本[5]。另一方面，She等人通过仅使用最有用的数据点进行再培训，在整个模糊化过程中使用了简化形式的模型再培训[51]。这两种方法都减少了训练时间，但对模糊性能的总体影响尚不清楚。减少数据量的另一种方法是开发在程序之间传输先前训练过的模型的方法。这些方法可能会消除或减少模糊化以前未开发的程序所需的模型训练量，但不清楚这些方法如何影响性能。
DL应用程序实现模糊化的第二个障碍是跨文件格式的性能一致性。其中许多研究表明，对于某些文件格式（如PDF），DL始终比以前的基线提高了模糊性能，而其他格式无法与最先进的技术竞争。未来的研究对于理解DL和NNs对于特定文件格式的适用性可能是有益的

强化学习。两个小组应用强化学习（RL）[29]，[2]进行输入生成。Becker等人使用SARSA算法[29]对发送到主机的网络数据包进行变异，从而模糊IPv6协议[4]。SARSA算法同时考虑代理的当前状态和行为，以确定最佳行为。Bottinger等人使用深度Q学习网络[42]学习描述PDF格式的基于生成的模糊器输入的语法[9]。深度Q学习网络使用深度神经网络将状态映射到动作。
这些研究为RL应用程序的输入生成提供了重要的见解。首先，他们表明，程序表示对于培训成功的RL代理至关重要。Becker等人使用有限状态机来表示IPv6协议的行为，其中每个状态表示主机对特定数据包的当前响应，状态之间的转换表示数据包的可能突变。Bottinger等人还使用一种有限状态机，即马尔可夫决策过程来表示问题。马尔可夫决策过程的特征是状态之间的随机转换。在本研究中，状态表示模糊器的特定种子输入，而转换表示该状态下种子输入的概率重写规则。因此，Becker和Bottinger都证明了使用有限状态机作为问题表示来训练RL代理生成输入的实用性。
其次，它们提供了有效定义代理奖励函数的见解，这通常是RL最具挑战性的方面。Becker等人创建了一个多部件基于以下标准的奖励函数：从单个输入调用的程序函数数量、是否存在错误以及程序响应消息的潜在损坏或延迟[4]。错误的存在向代理发出了最强的信号，表明它已经到达了代码空间中一个有趣的部分。即使在没有错误信号的情况下，程序响应也用于引导代理。因此，奖励函数的每一部分在引导代理人方面都发挥着独特的作用，如果忽略这些标准，可能会导致代理人的效率降低。Bottinger等人试验了多种不同的奖励函数，一种使用代码覆盖率，另一种使用执行时间，第三种结合代码覆盖率和执行时间。在这两项研究中，奖励函数都影响了模糊者对输入空间的探索。例如，当Bottinger使用执行时间作为奖励时，代理学习导致程序快速终止的输入。Becker和Bottinger的工作表明，需要仔细定义奖励函数，同时考虑软件程序类型、寻找的bug类型、可用的模糊度量以及最终的模糊目标。
标准模糊器尚未实现RL，应用程序仍处于理论状态。这一领域的关键第一步是更深入地理解奖励函数。具体地说，目前还不清楚奖励功能应该如何依赖于项目，或者是否存在普遍有效的奖励功能。例如，每个项目是否可以使用相同的奖励功能，或者每个独特的项目是否需要独特的奖励功能？文件格式（如PDF和PNG）如何影响奖励功能的定义？
RL面临的另一个挑战是理解代理的可转移性。目前尚不清楚是否有必要为每个独特的项目培训一名新的RL代理，这样做可能不切实际。因此，研究和创造可转移代理可能是未来研究的必要步骤。

用于符号执行的机器学习。在这里，我们简要地介绍了目前正在探索的用于改进符号执行的不同ML技术。如第2节所述，符号执行有助于为模糊器生成有效的新输入，但计算成本和路径爆炸仍然是重要的障碍。ML中的一些研究工作探索了改进约束求解的可行性，这可以支持模糊器输入生成的符号执行。不幸的是，目前使用ML的努力无法与使用图形算法的最先进方法相匹敌[31]；它们仅仅是可行性的探索。
有监督学习用于求解约束方程。在一项研究中，图形神经网络用于识别指示约束方程是否具有有效解的特征[10]。在另一项研究中，Wu使用logistic回归和Monte Carlo方法相结合的方法来确定初始值，以增加找到约束方程有效解的概率。蒙特卡罗方法用于确定初始有希望的值，而逻辑回归用于表明使用这些选定值的约束方程解的有效性。合并这些新的初始值会减少Minisat解算器的运行时间[64]。在另一项研究中，LSTM（即DL）被训练用于求解约束方程[50]。虽然LSTM无法击败最先进的约束求解器，但他们能够从未接受培训的领域求解约束方程，这表明DL模型具有推广能力。Shiqi等人开发的另一种方法使用NNs表示约束方程[52]。然后通过梯度下降法发现这些约束方程的解。一般来说，每项研究都提供了解决约束方程的独特方法。虽然不能和当前的技术水平竞争，但它们为使用监督学习减少求解约束方程所需的计算时间提供了一个强有力的起点。
Mairy等人使用RL改进了局部邻域搜索方法[40]。局部邻域搜索方法通过寻找约束方程各子集的解并组合这些子集形成最终解，迭代地寻找约束方程的解。为了发现有用的子集，这些局部邻域搜索方法必须智能地探索可能子集的空间。指导RL代理选择更有可能产生有效解决方案的子集，以减少找到此类解决方案所需的时间。
一项研究工作使用ML来减少解搜索空间的大小，而不是直接求解约束方程。Li等人将路径约束的典型集合重新表述为一个优化问题，并试图减少不可行路径的数量，即。E由于约束冲突而无法到达的路径[35]。他们使用ML技术RACOS[67]，一种可以很好地扩展到高维问题的优化技术，来解决优化问题；然而，仅对335行的非常小的程序进行了分析。
使用ML改进符号执行的初步探索显示了希望；然而，在这里应用ML的实用性还有待观察。目前的研究通常局限于小问题，这些小问题无法与最先进的技术相媲美。此外，本研究还未应用于第2节中描述的模糊器和符号执行技术的组合。ML是否有助于改进这些组合技术是一个悬而未决的问题。

Post-Fuzzing: Interesting Program States
如第2节所述，用户对fuzzer输出的有趣的程序状态进行分类，然后进行分析，通常是手动的。用户通过以下方式对程序状态进行分类：1）评估唯一性[46]，2）分析分类状态以确定可生产性和根本原因，以及，3）模糊漏洞评估时，确定根本原因是否可利用。ML主要用于分类崩溃（分类）或分类错误（根本原因分析），尽管Yan等人使用了贝叶斯方法和！exploitable可利用工具，用于提高确定漏洞可利用性的可靠性[65]。
Dang等人通过使用凝聚层次聚类（一种无监督的学习技术，将具有类似特征的数据点进行聚类）将具有类似调用堆栈的崩溃分组，从而对崩溃进行了分类[15]。他们在调用堆栈上引入了自己的相似性度量，即位置相关模型，允许他们使用未标记的调用堆栈数据集进行训练。他们在微软的各种产品上测试了他们的模型，在很多情况下都优于以前的碰撞相似性识别方法。
有几次尝试使用ML对软件中的bug进行分类。Harsh等人使用多种监督技术（包括决策树、支持向量机和朴素贝叶斯）对根本原因分类进行了实验[33]。然而，他们指出，由于缺乏标记数据，应用监督技术可能具有挑战性。为了克服标记数据的缺乏，Harsh等人还试验了无监督和半监督技术。不幸的是，这项研究中的技术是有限的，因为bug类别非常广泛，并且是特定于系统的。
在另一项研究中，Long等人使用ML来确定根本原因，并生成修补程序来修复相关错误[39]。他们的工具Prophet使用一个参数化的对数线性概率模型，该模型学习识别决定代码必须如何修复的重要特征。这项工作的一个重要方面是Prophet模型的可解释性；模型参数可用于确定生成特定面片的各种特征的重要性。这种可解释性很重要，因为它可以帮助用户理解生成特定补丁的原因。
有监督的ML技术用于更频繁地识别软件领域之外的根本原因[53]。在一个实例中，决策树和支持向量机用于工业生产系统的根本原因分析[16]。在另一个例子中，NN用于工业储罐系统内的故障定位[54]。支持向量机在加速电路板故障定位方面也显示出了希望[66]。虽然这些研究都没有直接应用于软件，但有可能扩展研究以帮助软件领域的根本原因分析。
挑战 。ML很少应用于后模糊任务，原因有二：1）ML结果和算法通常难以解释，2）适当的训练数据集稀疏。
首先，大多数ML分类技术返回的是预测，而不是解释。这使得用户很难确定预测的标签是否正确以及应用该标签的原因。例如，在根本原因分析中，用户会发现很难理解根本原因在代码中的显示位置，无论是验证标签还是纠正根本原因[33]。此外，ML算法通常建立难以映射到领域知识的不透明规则。
第二，我们几乎没有可用的标记数据集，而且还不清楚什么构成了强大的、可概括的基准数据集。在为后期模糊任务构建数据集时，有几个没有明确答案的问题必须解决，例如：•应该包括哪些可能的bug？•应该表示哪些编程语言？•如何为ML算法编码错误及其根本原因，特别是考虑到根本原因是细微差别的，并且可能因系统而异？
Seed selection
使用ML.Wang等人进行了一项广泛的研究，使用NNs选择更可能导致代码中的漏洞模糊的输入[62]。虽然这项研究显示了有希望的结果，但诸如训练模型到新项目的可转移性等挑战仍然存在。与输入生成一样，模型可移植性仍然是ML应用于种子选择的潜在瓶颈。
先前的种子选择研究指出了未来ML研究的另一种可能性。种子选择必须平衡使用具有已知性能水平的当前输入与探索具有未知但可能更好性能的新输入[63]。RL算法通常成功地应用于这些类型的场景，这些场景需要在探索新输入和利用当前输入之间取得平衡。因此，RL算法可能非常适合于确定最佳种子调度。未来的研究可能包括1）为最佳种子选择创建奖励函数，2）确定离线RL代理在程序之间的可转移性，以及3）在模糊化过程中集成在线RL代理。
Input and Corpus Minimization
据我们所知，还没有任何关于使用ML的输入最小化或orpus最小化的研究。我们假设缺乏研究的两个原因。首先，输入最小化和语料库最小化都不是一个很大的瓶颈。最大的瓶颈存在于输入生成和后模糊化过程中，因此，大多数研究倾向于集中在这些领域。其次，输入或总语料库大小的最小化自然不适合ML技术。虽然输入生成和（在较小程度上）后模糊化通常可以表述为ML问题，但通常使用启发式方法成功实现最小化[45]。

总结

由于模糊问题更自然地适用于无监督和强化学习技术，因此监督学习很少用于支持模糊过程。ML最常用于支持模糊化过程的生成输入阶段。目前，无监督方法通过AFL等工具提供最大的好处，使无监督算法成为其工作流程的一部分。相反，强化学习和深度学习正在探索可能的改进，但尚未普遍使用。ML还被应用于分析后模糊化过程中有趣的程序状态，帮助分类崩溃并支持根本原因分析。然而，ML并没有被应用到模糊过程的选择输入阶段，可能是因为这个阶段不是一个主要的瓶颈。此外，ML还未用于评估后模糊期间碰撞的再现性。在模糊化过程的某些部分缺少ML可能是由于许多因素造成的，包括缺少训练数据、程序之间传输模型的困难以及难以计算的训练时间。