NEUZZ: Efficient Fuzzing with Neural Program Smoothing
2019 IEEE Symposium on Security and Privacy
摘要
即使当前先进的fuzzer非常擅长寻找难以触发的软件漏洞。大多数fuzzer基于遗传算法来生成触发不同漏洞的输入。遗传算法虽然快并且易于部署，但是经常被无效的随机变异序列所限制。梯度引导的优化有希望成为遗传算法的替代。
梯度引导技术已经被证明了在域中解决高维结构优化问题时（例如机器学习通过有效利用梯度或基础函数的高阶导数），显著优于遗传算法。
然而，梯度引导方法并不能直接应用于模糊测试，因为现实世界的程序存在大量的不连续，在基于梯度引导的方法经常遇到的高原和山脊。
该问题可以通过创建一个平滑的代理函数来逼近目标程序的离散分支行为来解决。在本文中，我们提出了一种使用替代神经网络模型的新的程序平滑技术，可以增量地学习一个复杂的、真实世界程序地分支行为的平滑近似。我们进一步证明，这种神经网络模型可以与梯度引导的输入生成方法一起使用，以显著提高模糊过程的效率。
引言
由于安全漏洞往往是稀疏并且不规则地分布在一个程序中，大多数fuzzer的目标是通过提高代码覆盖率来提高发现漏洞的机会。随着语料库的增大，遗传算法在触发新的程序位置变得低效。
遗传算法的一个主要限制是他们无法利用潜在的优化问题的结构（例如，梯度或其他高阶导数）。
梯度引导优化（例如梯度下降）是一种很有前途的替代方法，已被证明在解决包括空气动力学计算和机器学习在内的不同领域的高维优化问题时，其性能显著优于进化算法。
然而，梯度引导优化算法不能直接用于fuzzing真实世界程序，因为他们通常包含大量的不连续行为（梯度不能精确计算的情况下），这是因为不同的程序分支有着不同的行为。该问题可以通过创建一个平滑处理函数来估计程序输入和目标程序分支的关系。不幸的是，现存的程序平滑技术，由于他们严重依赖于符号执行，因此存在一些基本限制。
在本文中，我们介绍了一种程序平滑技术，使用前馈神经网络，可以增量地学习复杂的、真实的程序分支行为的平滑近似，即由特定的给定输入来预测目标程序的控制流边缘。我们进一步提出了梯度引导搜索策略来计算，并且利用梯度平滑的近似来识别应该变异的位置，以此检测出目标程序的漏洞。
我们演示了如何通过在错误预测的程序行为上对模型进行增量再训练来改进神经网络模型。我们发现，前馈神经网络很自然地适合我们的任务，因为
（1）它们被证明具有近似复杂非线性函数的能力，就像普遍逼近定理所暗示的那样。
（2）它们支持高效和精确的计算梯度/高阶导数。
本文的主要贡献：
（1）我们是首次确定程序平滑对于采用有效的梯度引导技术进行模糊测试的重要性。
（2）我们引入了第一个使用代理神经网络的高效且可扩展的程序平滑技术，以有效地模拟目标程序的分支行为。我们进一步提出了一种增量学习技术，随着更多的训练数据可用，迭代地改进代理模型。
（3）我们证明代理神经网络模型的梯度可用于有效地生成程序输入，从而最大限度地增加目标程序中发现的错误数量。
（4）作为 NEUZZ 的一部分，我们设计、实施和评估我们的技术，并证明它在广泛的现实世界程序以及策划的错误数据集上显着优于 10 个最先进的模糊器。
本文其余内容
第二章总结了优化和梯度引导技术的必要背景知识。
第三章使用motivating example提供了一个我们技术的展望。
第四章和第五章介绍了我们的方法论以及实现过程中的细节。
第六章中进行了实验，后续是相关工作和总结。
第二章 背景知识
一个优化问题通常由三个部分组成：一个向量参数x，一个可以被最小化或者最大化的目标函数F(x)，一个约束函数的集合Ci(x)，既可以是等式约束也可以是不等式约束。优化过程的目标是找到参数向量x的具体的值，能够最大化/最小化F(x)并且满足所有约束Ci(x)如下所示：
这里，R、N和Q分别表示实数集、不等式约束指数和等式约束指数。
函数平滑度&优化
优化算法通常在一个循环中运行，从参数向量x的初始猜测开始，然后逐渐迭代以找到更好的解决方案。任何优化算法的关键组成部分是它用来从一个 x 值移动到下一个值的策略。 大多数策略利用目标函数 F、约束函数 Ci的值，以及梯度/高阶导数（如果可用）的值。
不同的优化方法收敛到最优解的能力和效率在很大程度上取决于目标函数F和约束函数Ci的性质。通常，较平滑的函数（即具有明确定义和可计算导数的函数）可以比具有许多不连续性（例如脊或高原）的函数更有效地优化。直观地说，目标/约束函数越平滑，优化算法就越容易精确计算梯度或高阶导数，并使用它们系统地搜索整个参数空间。
本文的剩余部分，我们特别关注无约束优化问题，因为它们很接近fuzzing，我们的目标域。对于无约束平滑优化问题，梯度引导方法在解决高维结构化优化问题上的性能明显优于进化策略。这是因为梯度引导技术有效地利用梯度/高阶导数来高效地收敛到最优解，如图1所示。
凸&梯度引导优化
对于一类称为凸函数的常见函数，梯度引导技术是高效的，并且可以始终收敛到全局最优解。
直观地说，如果连接函数图上任意两点的直线完全位于图的上方或上方，则函数是凸的。
更正式的，一个函数f被称为凸的，如果所有x和y的点对在域中满足以下性质
然而，在非凸函数中，梯度引导方法可能会局部最优解（假设目标是最大化）当客观函数比所有附近的可行点都大，但在整个可行参数值范围内的其他地方存在其他较大的值。然而，即使在这种情况下，简单的启发式方法，如从新的随机选择的起点重新启动梯度引导方法，在实践中也被证明是非常有效的
Fuzzing as unconstrained optimization
模糊测试可以看作一个无约束优化问题，目标通过固定数量的测试输入从而最大化在目标程序中发现的漏洞数量。因此，目标函数可以被看做Fp(x),当使用输入x执行目标程序p时，输入x触发了漏洞返回1。然而，这样的函数表现太差（即大部分包含平原和一些非常尖锐的过渡），无法有效地进行优化。
因此，大多数灰盒模糊测试工具会尝试将测试代码地数量最大化（例如，最大化边覆盖率）作为代理度量。这样的一个目标函数可以看作F'p(x)，F'返回被输入x覆盖的目标程序P的信息控制流边。注意F'比原始函数F更容易优化，因为执行新控制流边缘的所有可能程序输入的数量往往明显高于触发错误/安全漏洞的输入。
大多数的现存灰盒模糊测试工具使用进化技术以及其他特定领域的启发式算法作为其主要优化策略。在梯度引导优化中选择此类算法的关键原因是，由于不同程序路径上的行为显著不同，大多数实际程序包含许多不连续性。
这种不连续性可能会导致梯度引导优化陷入非最优解。在本文中，我们提出了一种使用神经网络对目标程序进行平滑处理的新技术，使其适用于梯度引导优化，并演示了模糊器如何利用这些策略显著提高其效率。
第三章 本文方法概述
图2给出了一个我们方法的概括展望。
神经网络平滑
平滑地逼近程序的不连续分支行为是精确计算梯度或梯度引导优化所需的高阶导数的必要条件。如果没有这样的平滑，梯度引导的优化过程可能会在不同的不连续/平台上卡住。平滑过程的目标是创建一个平滑的函数，它可以模仿程序的分支行为，而不会引入大错误（即，它与原始程序行为的偏差最小）。
我们使用一个前馈神经网络来完成这一目的。正如普遍逼近定理所暗示的那样，一个神经网络非常适合近似任意复杂的程序行为（非线性并且非凸）。并且，根据NNs的设计，其支持对我们的目的至关重要的高效梯度计算。我们通过使用现有测试输入或使用现有进化模糊测试生成的测试输入语料库来训练神经网络，如图2所示。
梯度引导优化
光滑神经网络模型经过训练后，可以有效地计算梯度和高阶导数，然后利用这些梯度和高阶导数更快地收敛到最优解。梯度引导算法地不同变体，如梯度下降法、牛顿法或拟牛顿法，如L-BFGS算法，使用梯度或高阶导数来加快收敛速度。平滑NNs使模糊输入生成过程能够潜在地使用所有这些技术。在本文中，我们设计、实现并评估了一种简单地梯度引导输入生成方案，该方法专门针对CGF。
增量学习
任何类型的现有测试输入（只要它们在目标程序中暴露不同的行为）都可以潜在地用于训练神经网络模型和引导模糊输入生成过程。在本文中，我们通过运行进化模糊器（如AFL）收集一组测试输入和相应的边缘覆盖信息来训练神经网络。
然而，由于用于训练神经网络模型的初始训练数据可能只覆盖程序空间的一小部分，我们通过增量训练进一步细化模型，因为在模糊化过程中观察到新的程序行为。增量训练中的关键挑战是，如果神经网络只在新数据上训练，它可能会完全忘记从旧数据中学习到的规则。
我们通过设计一种新的基于覆盖率的过滤方案来避免这个问题，该方案可以创建新数据的简要摘要，从而使神经网络能够有效地进行训练。
A motivating Example
如图3所示的一个例子。考虑这种情况，像AFL这样的进化fuzzer能够完成覆盖第二行和第九行的分支，而不能覆盖第五行的分支。这里的关键挑战是去找到a和b的值能够触发第5行的分支。进化模糊测试工具经常与这样的代码斗争，因为通过随机变异找到解决方案的概率非常低。
例如，图3(a)里显示表示代码段的原始函数。这里在a+b=0到a+b-c=0(c->+0)之间有一个sharp jump。
为了在模糊化过程中最大化边缘覆盖，进化模糊测试工具只能对输入进行随机突变，因为这种技术不考虑函数曲面的形状。相比值下，我们的神经网络平滑和梯度引导突变旨在利用梯度测量的函数曲面形状。
我们根据其他两个分支的程序行为训练神经网络模型。NN模型平滑地逼近程序行为，如图3(b)(c)所示。然后，我们使用神经网络模型执行更有效的梯度引导优化，以找到所需的a和b值，并逐步优化模型，直到找到所需的分支来执行目标错误。
第四章 主要方法
A.程序平滑
程序平滑是使得梯度优化技术适用于fuzzing真实世界程序不连续行为时的关键步骤。
除平滑函数之外，梯度引导优化技术在优化非平滑的函数时并不是非常有效，因为会被不同的不连续行为限制。平滑过程最小化不规则，从而使得梯度引导优化在不连续函数优化上更加显著有效。
一般来说，对于一个不连续函数f的平滑科研认为是和一个平滑的掩模函数g的卷积运算，从而产生一个新的平滑输出函数。一些流行的平滑掩模函数包括不同的高斯函数和sigmoid函数。
然而，对于很多实际的问题，不连续的函数f可能没有封闭形式的表示，因此不可能用解析法计算上述积分。在一些例子中，当使用离散形式
程序平滑技术可以分为两个类别：黑盒和白盒平滑。黑盒方法从f的输入空间中选取离散样本，利用这些样本数值计算卷积。与之相反的，白盒方法分析程序的语句/指令并且尝试使用符号分析和抽象解释来总结它们的效果。黑盒方法可能会引入较大的近似误差，而白盒方法会产生令人望而却步的性能开销，这使得它们在真实的程序中不可行。
为了避免这样的问题，我们使用神经网络以灰盒方法（例如，收集边缘覆盖率数据）学习程序行为的平滑近似。
B.神经的程序平滑
在本文中，我们提出了一种新的程序平滑方法，即使用替代神经网络模型学习和迭代改进目标程序的平滑逼近，基于观察到的程序行为。该代理神经网络可以平滑地推广到观察到的程序行为，同时还可以准确地建模潜在的非线性和非凸行为。神经网络一旦经过训练，就可以用于有效地计算梯度以及更高维度的导数来引导模糊测试输入生成过程。
为什么使用NNs？
正如普遍逼近定理[33]所暗示的那样，神经网络非常适合逼近复杂(可能是非线性和非凸的)程序行为。使用神经网络进行平滑程序逼近学习的优点如下:(1)神经网络能够准确地模拟复杂的非线性程序行为，并能够有效地训练。之前基于模型的优化工作使用了简单的线性和二次模型[24]，[23]，[71]，[52]。然而，这样的模型并不适合对具有高度非线性和非凸行为的真实软件建模;(2)神经网络支持其梯度和高阶导数的高效计算。因此，梯度引导算法可以在不增加额外开销的情况下计算和使用这些信息;(3)网络神经网络可以基于程序在类似输入上的行为，推广并学习预测程序在看不见的输入上的行为。因此，对于少量的输入样本，神经网络可以根据其行为学习整个程序的平滑近似。
NN训练
虽然神经网络可以用来模拟程序行为的不同方面，但在本文中，我们专门使用它们来模拟目标程序的分支行为（即，预测给定程序输入的控制流边缘）。使用神经网络建模分支行为的挑战之一是需要接受可变大小的输入。前馈神经网络与现实世界的程序不同，通常接受固定大小的输入。因此，我们设置了一个最大输入大小阈值，并在训练期间用空字节填充任何较小的输入。请主义，支持更大的输入并不是一个主要问题，因为现代NN可以轻松地扩展到数百万个参数。因此，对于较大的程序，如果需要，我们可以简单地增加阈值大熊啊。然而，我们的经验发现，相对适中的阈值产生最好的结果，较大的输入并不能显著提高建模的准确性。
在本文中，采用前馈全连接神经网络对目标程序的分支行为进行建模。前馈结构可以高效计算梯度和快速训练。
我们的平滑技术与训练数据的来源无关，因此NN可以在现有输入语料库中收集的任何边缘覆盖数据上训练。对于我们的原型实现，我们使用由现有的进化模糊器(如AFL)生成的输入语料库来训练我们的初始模型。
训练数据预处理
由训练数据进行的边缘覆盖通常倾向于有偏差，因为它只包含程序中所有边缘的一小部分标签。例如，一些边可能总是由训练数据的所有输入一起联系。在机器学习中，一组变迁之间的这种类型的相关性被称为多重共线性，它经常阻止模型收敛到一个小的损失值。为了避免这种情况，我们遵循常见的机器学习的降维实践，将训练数据中总是同时出现的边合并称一条边。此外，我们只考虑训练数据中至少被激活过一次的边缘。这些步骤将标签的数量从平均65536个显著减少到4000个左右。注意，我们在增量学习的每一次迭代中都重新运行数据预处理步骤，因此，随着模糊过程中发现新的边缘数据，一些合并的标签可能会被分割，因为它们的相关性可能会降低。
C.梯度引导的优化
不同的梯度引导优化技术，如梯度下降法、牛顿法活准牛顿法，如L-BFGS，可以使用梯度或高阶导数，以更快的收敛。平滑的神经网络使模糊输入生成过程可以通过支持梯度和高阶导数的高效计算来潜在地使用任何这些技术。在本文中，我们专门设计了一个简单地梯度引导搜索方案，该方案对较小地预测误差具有鲁棒性，以证明我们的方法的有效性。我们把对更复杂技术的探索留作以后的工作。
梯度的正式定义，表明每个输入字节应该改变多少，以影响神经网络中最后一层神经元的输出（表示程序中边缘覆盖的变化）f。在这里，每个输出神经元对应于一个特定的边，并计算一个0到1之间的值，总结给定的输入字节对特定边的影响。神经网络f输出神经元的梯度，输入被广泛用于对抗输入生成，和可视化理解DNNs。直观地说，在我们的设置中，基于梯度的引导的目标是找到将最终层神经元的输出从0改变到1的不同边缘的输入。
梯度引导的优化：算法1展示了梯度引导输入生成过程的概括。关键思想是识别具有最高梯度值的输入字节并改变它们，因为它们对NN表示更高的重要性，从而有更高的机会引起程序行为的重大变化。
从种子开始，我们迭代地生成新的测试输入。如算法1所示，在每次迭代中，我们首先利用梯度的绝对值来识别将导致未取边对应的输出神经元发生最大变化的输入字节。接下来，我们检查每个字节的梯度符号，以决定突变的方向(例如，增加或减少它们的值)，以最大化/最小化目标函数。从概念上讲，我们对梯度符号的使用类似于[39]中引入的对抗性输入生成方法。我们还将每个字节的突变限制在其合法范围内(0-255)。第6行和第10行表示使用clip函数实现这种边界。
我们以一个小的突变目标（算法1中的k）开始输入生成过程，并以指数增长目标字节数来进行突变，以有效地覆盖大的输入空间。
D.通过增量学习进行改进
梯度引导输入生成过程的效率很大程度上取决于代理神经网络对目标程序分支行为建模的准确性。为了获得更高的精度，我们在模糊过程中观察到发散的程序行为时，逐步细化神经网络模型。（也就是说，当目标程序的行为与预测的行为不匹配时）。我们使用增量学习技术来保持神经网络模型的更新，通过学习新的数据，当新的边缘被触发。
神经网络优化背后的主要挑战是防止神经网络模型在训练新数据时突然忘记它从旧数据中学习的信息。这种以往在深度学习文献中是一个众所周知的现象，一直被认为时稳定-可塑性困境的结构。为了避免这种遗忘问题，神经网络必须改变足够的权值来学习新的任务，但不能太大以致于导致它忘记之前学习的表示。
优化NN最简单的方法是将新的训练数据(即程序分支行为)与旧数据相加，重新从头开始训练模型。然而，随着数据点数量的增加，这种再培训变得越来越难以规模化。之前的研究试图解决这个问题，主要使用两种广泛的方法[44]，[51]，[31]，[75]，[29]，[40]，[76]。第一种方法试图保持新模型和旧模型的分离表示，以最小化使用分布式模型、正则化或创建多个模型的集合的遗忘。第二种方法维护旧数据的摘要，并根据新数据和汇总的旧数据对模型进行再训练，因此比完全再训练更有效。我们建议有兴趣的读者参考Kemker et al.[48]的调查以了解更多细节。
在本文中，我们使用基于边缘覆盖的过滤来只保留触发新分支的旧数据进行再训练。随着新的训练数据变得可用，我们识别实现新的边缘覆盖的那些，将它们与过滤后的旧训练数据放在一起，并重新训练NN。这种方法有效地防止了训练数据样本的数量随着再训练迭代次数的增加而急剧增加。我们发现我们的过滤方案可以很容易地支持多达50次迭代的再训练，同时仍然保持训练时间在几分钟以内。
第五章 实现
NN架构
我们的NN模型在Keras2.1.3[5]中实现，后端是Tensorflow-1.4.1[6]。该神经网络模型由三个全连接层组成。隐层使用ReLU作为激活函数。我们使用sigmoid作为输出层的激活函数来预测控制流边缘是否被覆盖。训练神经网络模型50个epoch(即整个数据集的50次完整通过)，以获得较高的测试精度(平均约95%)。由于我们使用的是一个简单的前馈网络，所以10个项目的训练时间都不到2分钟。即使使用Intel i7-7700运行在3.6GHz的纯CPU计算，训练时间也不到20分钟。
训练数据收集
对于每个测试的程序，我们在单核机器上运行AFL-2.5.2[88] 1小时，为NN模型收集训练数据。为10个项目收集的平均训练输入数量约为2K。得到的语料库以5:1的比例进一步分裂为训练数据和测试数据，其中使用测试数据来确保模型没有过拟合。我们使用10KB作为阈值文件大小从AFL输入语料中选择我们的训练数据(平均90% AFL生成的文件都在阈值以下)。
变异和重训练
NEUZZ通过迭代运行来生成1M突变，并对NN模型进行增量再训练。我们首先使用算法1中描述的突变算法产生1M的突变。我们将参数i设置为10，这将为种子输入生成5120个突变输入。接下来，我们在目标程序中随机选择100个输出神经元，代表100个未探索的边缘，从两个种子中产生10240个突变输入。最后，我们使用AFL的分叉服务器技术[54]执行带有1M突变输入的目标程序，并使用覆盖新边缘的所有输入进行增量再训练。
模型参数选择
NEUZZ的成功取决于训练模型和生成突变时不同参数的选择。在这里，我们通过经验探索了在四个程序中确保最大边缘覆盖的最优参数：readelf,libjpeg,libxml以及Mupdf.
第六章 实验
实验主要回答以下问题：
（1）NEUZZ是否可以较之现存的fuzzer发现更多的漏洞。
（2）NEUZZ是否覆盖率更嘎
（3）NEUZZ是否比其他RNN-based fuzzer效果更好。
（4）不同的模型选择如何影响NEUZZ的性能。
我们的实验设置包括以下两个步骤:首先，我们运行AFL一个小时，生成初始种子语料库。然后，我们使用相同的初始种子语料库，在固定的时间预算下运行每个模糊算子，比较它们的边缘覆盖率和发现的bug数量。具体来说，10个真实世界程序、LAVA-M数据集和CGC数据集的时间预算分别为24小时、5小时和6小时。
问题（1）的回答
问题（2）的回答
问题（3）的回答
现有的基于递归神经网络（RNN）的模糊控制器从过去的模糊测试经验中学习突变模式，以指导未来的突变[72]。这些模型首先从AFL产生的大量突变输入中学习突变模式（由关键字节组成）。接下来，他们使用突变模式构建AFL过滤器，该过滤器只允许关键字节上的突变通过，否决所有其他非关键字节的突变。我们选择了之前研究过的4个程序来评估NEUZZ与基于RNN的模糊器对100万个突变的性能。我们用相同的训练数据训练两个NN模型，然后让两个基于NN的模糊器运行，生成100万个突变，并比较两种方法获得的新代码覆盖率。
问题（4）的回答
NEUZZ的模糊化性能在很大程度上取决于训练后神经网络的准确性。正如在第五节中所描述的，我们通过经验发现，具有1个隐藏层的NN模型足以模拟真实世界程序的复杂分支行为。在本节中，我们通过探索1隐层架构的不同模型设置来进行消融研究，即线性模型、不加细化的神经网络模型和增量细化的神经网络模型。我们评估了这些模型对NEUZZ性能的影响。
我们通过去除隐藏层中使用的非线性激活函数来实现线性模型，从而使整个前馈网络完全线性化。该神经网络模型从AFL中训练相同的种子语料库。接下来，我们从被动学习模型中生成1M突变，并测量这些1M突变实现的边缘覆盖。最后，我们从100万个突变中过滤出锻炼未见边缘的突变输入，并将这些选择的输入添加到原始种子语料库中，以增量方式重新训练另一个NN模型，并使用它生成进一步的突变。结果汇总于表VIII。
我们可以看到，对于所有4个测试程序，两种NN模型(有或没有增量学习)都优于线性模型。这表明非线性神经网络模型比简单的线性模型更能近似程序的行为。我们还观察到，增量学习帮助神经网络实现显著更高的准确性，因此更高的边缘覆盖率。
