在软件漏洞挖掘中，使用Fuzzing测试仍然比较广泛。Fuzzing测试是一种通过向目标系统提供非预期输入并监视异常结果来发现软件漏洞的方法^[1-5]。通过对测试样本进行变异，输入目标程序并监控其是否发生异常。但是，传统Fuzzing方法具有较强的盲目性，具体表现在：1) 工作效率低，在多数情况下测试用例都是重复相同的路径；2) 未测量Fuzzing过程中的程序执行状态，对测试用例的使用情况并无有效的反馈；3) 对异常的分析与分类较粗糙，导致后期漏洞分析工作效率较低。本文针对Fuzzing测试方法中存在的问题进行分析，深入研究相应的改进与优化方法，以进一步提高Fuzzing挖掘漏洞的效率，增强Fuzzing的实用性。

1 方法描述

Fuzzing过程可被形式化地描述为F(Σ,T,P,M)={(E₁,t₁),(E₂,t₂),…,(E_n,t_n)}，其中，F表示Fuzzing过程，Σ表示初始样本集，T表示Fuzzing所消耗的总时间，P表示Fuzzing的目标程序，M表示对初始样本的变异方式。经过Fuzzing过程后，输出二元组(E_i,t_i)，其中E_i表示目标程序产生的异常，t_i表示该异常产生的时间戳。通过对异常进行分析，判断其产生原因及可利用性，又可以确定是否为漏洞：Π(E)=(Bug|None)。

本文对传统Fuzzing过程中存在的不足进行研究，并从样本选取、Fuzzing过程监视、异常分析与分类3个方面进行优化，提出相应的改进方法，进一步提高Fuzzing的工作效率。

1.1 样本集精简优化

Fuzzing过程前需要一个初始样本集来进行变异，初始样本集一般可从2 种途径获得：1) 从互联网上海量爬取样本文件；2) 人工构造。传统Fuzzing的方法通常是得到初始样本集后便直接开始进行变异与测试，不考虑重复样本，因此造成大多数样本文件使目标程序执行着相同的路径，重复计算量极大。为表明重复量，本文对1 000个样本文档对微软的Word程序进行测量，发现将近80%的文件并未探测到新的路径，仅是在重复其他样本执行过的路径。

为了减少样本的重复率，提高Fuzzing过程的效率，本文提出一种精简集方法，即通过对初始样本集Σ进行精简处理，计算出初始样本集的子集ω，该子集满足｛ω|ω⊆Σ∧ λ(ω)=λ(Σ)｝，其中，λ为覆盖率计算函数，表示该样本所对应的代码覆盖。

例如，某目标程序P中包含12个基本块：B={b₁,b₂,b₃,b₄,b₅,b₆,b₇,b₈,b₉,b₁₀,b₁₁,b₁₂}。使用初始样本集Σ={s₁,s₂,s₃,s₄,s₅,s₆},其中:λ(Σ)=B，λ(s₁)={b₁,b₁₂}，λ(s₂)={b₁,b₂,b₃,b₄}，λ(s₃)={b₁,b₃,b₅,b₇,b₈,b₁₁,b₁₂}，λ(s₄)={b₁,b₂,b₃,b₄,b₆}，λ(s₅)={b₁,b₂,b₉,b₁₀,b₁₂}，λ(s₆)={b₁,b₂,b₃,b₇,b₈,b₉,b₁₀,b₁₂}。经过计算后得到精简集ω={s₃,s₄,s₅}⇒ λ(ω)=λ(Σ)。

从多个集合中计算最小覆盖集为经典NP-hard问题^[6]，因此难以计算最优解，只能采用近似逼近的算法，本文根据程序代码覆盖的分布特征及经验数据总结，设计了一种贪心逼近的求解算法来计算最小覆盖集，该算法的实现细节如图1所示。

该算法的过程主要为：1) 对所有样本的覆盖率进行排序；2) 合并所有样本的覆盖率M，并在合并过程中，选取具有独有代码覆盖的样本集E，即该样本可覆盖程序中其他样本不可覆盖的位置，这些样本必然包含在最小覆盖集中；3) 总体样本集去掉E后得到新的总覆盖率，根据贪心算法，从大覆盖率的样本开始去重，直到达到总覆盖率为止算法完成。这种算法的时间复杂度为O(n²)，且随着样本数的增加，所消耗的时间增加的越快。因此，在实际应用中，对数万级的样本计算最小覆盖集时，本文采用分治的思想，将样本集平均的分成数个较小的样本集，并行地使用该算法进行计算，最后再对所有结果再进行一次最小覆盖集计算，这种方法也较好地提高了最小覆盖集的计算效率。

通过最小覆盖集计算后所得到的精简样本集合ω，可达到初始样本集Σ的代码覆盖率，对最小覆盖集算法进行正确性的验证：λ(ω)=λ(Σ)。

本文提出的样本集精简化方法，可对原始海量样本集进行覆盖集精简化处理，Fuzzing过程只需对精简样本集进行变异并测试，在保证了代码覆盖率的前提下，可大量节省测试时间成本。

1.2 测试过程样本调整

在Fuzzing测试中，样本测试过程包括对样本的变异与测试，样本集中的第i个样本的总测试时间T_i为变异次数m_i乘以对m_i次变异后样本的测试时间t_i。

因此可得出Fuzzing测试总时间$T = \sum\limits_{i = 1}^{\left\lfloor \omega \right\rfloor } {{T_i}} $。其中：|ω|表示样本的数量；T_i为每个样本的测试时间片，可表示为${T_i} = {m_i} \times \sum\limits_{l = 1}^{{m_i}} {{t_l}} $，即$T = \sum\limits_{i = 1}^{\left\lfloor \omega \right\rfloor } {\left( {{m_i} \times \sum\limits_{l = 1}^{{m_i}} {{t_l}} } \right)} $。

在大多数的传统Fuzzing方案中，所有样本都被平均处理，一般表现为2种形式：1) 变异次数平均，每个样本变异m次；2) 样本的测试时间片相同，即每个样本的总测试时间T_i恒定。通常情况下，每个变异样本的测试时间相差并不大，即t_i≈T_i/m_i。

本文所提出的Fuzzing优化方法遵循如下经验性总结：对代码覆盖率高、探测路径能力强的样本进行Fuzzing测试，更容易发现软件中的安全漏洞。因此，将所有样本都均等处理的策略存在不足，每个样本的代码覆盖情况都不相同，变异后探测新路径的能力也相差较大，优质样本(代码覆盖率高、探测未知代码能力强)被Fuzzing测试的程度不够，而较差的样本消耗了过多时间。为此，本文提出一种对样本的评估模型，为每个样本计算独立的权值，作为Fuzzing过程中的参考依据，使得优质的样本能得到较多的测试时间片。

本文提出的权值计算模型为

${{W}_{i}}=\frac{{{\lambda }_{i}}\times \left( 1+{{\mathbb{R}}_{i}} \right)}{\lambda }\times k$

其中：W_i表示第i个样本的权值；λ_i表示第i个样本对应的代码覆盖率；λ表示所有样本的总覆盖率；${{\mathbb{R}}_{i}}$_i 表示该样本第一次变异后所探测的新代码占原来代码的比重；k为时间片系数，由用户提供，用以控制Fuzzing的总时间。

因此，加权后的Fuzzing总时间$T = \sum\limits_{i = 1}^{\left\lfloor \omega \right\rfloor } {\left( {{W_i} \times {T_i}} \right)} $，当权值W=1时，该策略等同于传统的平均处理样本的方案。加权后的时间片可较好地体现出Fuzzing过程中的优化原则，对于代码覆盖率高、路径探测能力强的样本，权值W也越大，因此可分配的Fuzzing时间片也越大，更能发挥优质样本的作用。

除此之外，本文还给出2种Fuzzing测试过程的启发式：1) 在Fuzzing过程中，若连续对某样本进行n_thres次变异都无法探测到新的代码路径，则停止对该样本的Fuzzing测试，切换到下一个样本；2) 在Fuzzing过程中，若连续对m_thres个样本进行变异，都呈现出变异后代码覆盖率急剧下降的特征，则停止整个Fuzzing过程。因为导致这种情况的原因可能为目标程序中存在完整性校验机制，经过变异的样本无法通过检查导致目标程序中止。已有研究人员对绕过校验机制进行了较深入的研究^[7-8]。

通过在Fuzzing过程中对样本的执行效果进行监控与分析，根据样本的代码覆盖率及探测新路径的能力，动态地调整不同样本的测试时间片，以使优质的样本可以得到较充分的变异与测试，进而提高软件异常产生的可能性。

1.3 异常分析与分类

Fuzzing过程完成后，可能会产生大量的目标程序异常信息。安全研究人员往往需要对这些大量的异常信息进行深入分析，研究异常产生的原因，判断该异常是否为漏洞，这个过程可形式化地描述为

$\begin{align} & \prod{\left( {{c}_{i}} \right)}= \\ & \left\{ \begin{matrix} {{b}_{i}},if\left( \exists {{s}_{i}} \right)\left( \left( P\left( {{s}_{i}} \right)\mapsto {{c}_{i}} \right)\wedge \text{exploitable}\left( {{c}_{i}} \right) \right); \\ 0,\text{otherwise}. \\ \end{matrix} \right. \\ \end{align}$

其中：Π表示异常分析过程，c_i表示异常，s_i表示输入，P表示目标程序，exploitable表示可利用性谓词。当存在某个异常所对应的输入，且该异常为可利用时，则认为该异常为安全漏洞。

在大量的异常中分析是否存在漏洞时，比较繁琐的一项任务是对异常进行分析，由于产生异常数量较多，但是存在大多异常都由同一个漏洞引起的情况，因此需要在异常分析工作前先对异常信息进行分类，以减少异常分析的工作量。

传统的异常分析方法(如MSEC的exploitable插件)较简单，仅依靠对调用栈及异常上下文信息计算哈希来区分不同的异常，这种方法可排除大量的重复异常，但仍存在一些不足：1) 异常产生环境的不确定性导致异常分类不够准确；2) 污点传播策略不够完整。这些问题导致对异常的分析与分类产生偏差，为此，本文在exploitable插件的基础上，提出一种较完善的异常分析与分类方法，能够较准确地对异常进行分析与归类，以辅助后期的可利用性分析。

1) 排除不可再现性异常。

给定一个特定的测试环境，对所有产生异常的输入进行再现性测试，并对异常进行简要的分析，使用异常哈希进行标识，删除异常哈希值相同的异常信息，再对异常信息进行简要的分析。经分析后，可将异常归纳为如下几类(见表1)。此过程可去除掉一部分由不同环境(如内存耗尽、特殊环境变量)引起的、不具有可再现性的异常。

2) 基于污点传播的异常分类方法。

将产生异常的输入作为污点源，通过基于污点传播的数据流分析方法，来监控污点数据在程序中的流动情况。通过污点源与异常上下文间的关系分析，可判断该异常是否具有可利用性。此外，污点传播还可辅助安全研究人员利用代码编写漏洞。对于污点传播算法，研究者已经在近年来提出并实现了数个原型系统^[9-11]。

本文采用基于对比的污点引入方法，将产生异常的样本与原始样本进行比对，并将差异部分设置成污点。再次加载目标程序，采用在线的污点传播方案监控程序执行直到异常发生，分析污点数据与异常上下文之间的关系。

考虑如下3种情况：

a) T_taint(input)$ \mapsto $pc.

其中：T_taint为污点传播函数，input指输入，pc指程序指针，这种情况指污点输入影响程序指令指针，即程序控制流指向可控的位置，可利用性非常高。该漏洞一般是由缓冲区溢出引起，漏洞产生原因位于异常触发以前，需向前回溯分析。

b) T_taint(input)$ \mapsto $ Addr_access.

其中，Addr_access为指令访问地址，这种情况指污点输入影响指令访问内存的地址，可利用性较高。当污点输入同时影响读取和写入地址时，该漏洞可利用性较高。该类型漏洞产生原因不定，可能为缓存区溢出，也可能是程序设计问题。

c) T_taint(input)$ \mapsto $ Val_env.

其中,Val_env为当前指令的上下文环境，这种情况指污点输入影响当前指令的某个寄存器或所访问到内存中的值，具有一定可利用性。该漏洞往往需向前或向后追踪若干条指令才能发现可利用的位置，或者结合其他漏洞完成组合式的利用。该漏洞产生的原因位于异常触发之间，需向前回溯分析。

对这3种情况的漏洞进行分级处理，依次为高危、中危和低危。在后期的验证分析阶段，对这些漏洞的处理顺序按照危害等级从高危等级开始处理，可尽早发现可利用的漏洞，提高人工分析的效率。对于其他情况，如污点输入影响分支条件、函数参数或返回值等情况，这种漏洞的处理顺序往往可利用性较低，因此不对这些情况进行处理，直接将其标识为较低危害等级漏洞。

2 实验 2.1 系统实现

基于本文所提出的改进方法，以Peach作为底层Fuzzing平台，实现了相应的Fuzzing原型系统。Peach是一款开源的Fuzzing系统，支持协议格式自定义、分布式等功能，具有较优的变异策略和自动化测试流程，因此选取Peach作为Fuzzing的基本框架。所实现的Fuzzing平台结构图如图2所示，采用Intel商业化工具Pin^[12-19]作为二进制插装平台，编写相应插件完成样本的代码覆盖信息收集、异常分析时污点传播。

从图2中可看出，系统由3个模块构成，分别对应测试前准备、Fuzzing测试中、测试完成后3个阶段，最后的结果经过人工分析后成为漏洞成因、验证代码及危害评估。本文所提出的方法贯穿于整个Fuzzing测试流程：在测试前准备对样本进行精简化处理以减小原始样本集的规模；在Fuzzing测试过程中使用动态的样本选取模型来择优测试，以使优质样本得到充分的测试；在测试完成后，采用基于污点传播的异常分析与分类方法，提高人工分析的工作效率。

2.2 实验过程

1) 精简集处理的实验。

本文使用Google搜索引擎从网络上下载了数千个文件，包括DOC、AVI、ICO类型，并将其分成3组，分别以Winword、VLC Player、Xnview作为目标程序，应用本系统的精简集模块进行处理，实验数据见表2。

从表2中数据可看出，使用精简集处理后，样本减少到原始样本的40%以下，极大地减少了Fuzzing所需要的样本。为证明算法的正确性，分别使用精简集样本的代码覆盖率进行合并，与原始样本的代码覆盖率完全相同，可说明精简集算法正确。

2) 动态样本策略调整选取的实验。

同样使用上述几个程序进行测试，为较显著地通过实验来说明问题，本文选取了较旧的程序版本(Winword2003、VLC2.0.1 、Xnview1.98)作为测试对象，以尽快得出测试结论。测试时间阈值为1 000 min，Peach对每个样本变异100次，本系统采用动态调整策略与Peach的对比实验如表3所示。

经测试后，生成的异常数远大于表3中的数据，为使测试数据真实可靠，对产生的异常进行了简单分析，去掉重复的异常。从表3中数据可见，使用本系统测试所得的异常数量确实多于Peach原有的变异策略。

3) 异常分析与分类。

为了更清晰地对此模块的功能进行对比，禁用了动态策略调整模块，使用Peach原有的变异策略来进行测试，并对最终产生的异常进行分析与分类，实验数据如表4所示。

高危漏洞表示可利用漏洞，中危漏洞指不可利用、但某些关键数据可控的漏洞，低危漏洞指不可利用且无数据可控的漏洞。从表4中数据可看出，本系统的分类方法与最终人工分析的结果较为相近，尽管需要一定的时间成本用于污点传播过程，但节约了大量的人力成本，可作为后期异常分析的参考依据。

综上所述，本文所提的方法提高了传统Fuzzing测试的效率。将该方法部署在未知漏洞挖掘系统平台中，已发现大量软件漏洞，其中发现了金山WPS、KMPlayer、Xnview等软件中10个0day漏洞，已提交给国家漏洞库，出于安全性考虑，故不在此批露这些漏洞的细节。

3 结论

Fuzzing方法是目前相对比较有效的软件漏洞挖掘方法，但存在着盲目性较强、效率低等不足。本文针对这些不足，从样本处理、测试策略调整、异常分析与分类3个层面提出相应的改进与优化方法，并实现了对应的原型系统。在样本处理方面，提出一种精简集计算方法，可缩减原始样本的数量；在测试过程方面，提出一种动态策略调整方法，可使优质样本得到充分的变异与测试；在异常分析方面，提出一种基于污点传播的异常分析与分类方法，可进行较自动化的异常分析，有助于提高人工分析的效率。通过与传统Fuzzing进行对比实验，可说明本文提出的方法确实有效地改进了传统Fuzzing测试，具有较强的实用性。