一种软件模糊测试方法论文和设计-戚兰兰

全文摘要

本发明提出了一种软件模糊测试方法，所述方法包括如下步骤：基于软件测试阶段获取的历史数据、测试用例及日志信息，提取并建立基于自适应逼近漏洞模型AAMV的探测数据样本；基于细粒度污点动态分析所述探测数据样本中的漏洞相关输入元素，生成基于探测数据样本的输入数据；基于所述输入数据的混合符号执行以生成高覆盖率的探测数据。提出了一种基于树结构的自适应逼近漏洞模型AAMV，指导探测数据生成，提高软件漏洞分析效力。细粒度污点分析查找脆弱点相关输入元素，缩小输入元素的变异空间。提高了模糊测试技术的代码覆盖率。基于OMMutator算子的多维探测数据生成技术在脆弱点命中率相同情况下极大减少了探测数据规模。

主设计要求

1.一种软件模糊测试方法，用于提高软件漏洞分析效率，其特征在于，所述方法包括如下步骤：S1、基于软件测试阶段获取的历史数据、测试用例及日志信息，提取并建立基于自适应逼近漏洞模型AAMV的探测数据样本，所述探测数据样本包括：软件漏洞相关输入元素和软件漏洞无关输入元素；S2、基于细粒度污点动态分析所述探测数据样本中的软件漏洞相关输入元素，生成基于探测数据样本的输入数据，具体包括：根据目标程序潜在软件漏洞运行的反馈信息，构造逼近函数选择相应的遗传算法操作，通过迭代运算的方式生成越来越逼近异常的基于探测数据样本的输入数据；S3、基于所述输入数据的混合符号执行生成高覆盖率的探测数据，具体包括：混合符号执行把所述输入数据进行格式变换，通过把转化后的所述输入数据中的数据元素作为符号值，收集程序路径上对输入数据的约束条件，通过约束求解，生成高覆盖率的探测数据；S4、基于所述高覆盖率的探测数据进行模糊测试以检测是否存在软件漏洞；所述自适应逼近漏洞模型AAMV具体为：AAMV＝(s,L,I,C,V,OP,Result)；OP＝{T,M,BDDTaint,Symb,Slv}；Result＝{sampletree,mediumtree,newtree,testcase}；其中，s表示某个样本数据；L＝{l1,l2,…,li,…,lp},L表示叶子结点集合,l表示网络协议或文件结构中的一个语义单位；I＝{i1,i2,…,ij,…,iq}，I表示中间结点集合,i表示网络协议或文件结构中的一个语义单位；C表示约束条件的集合，描述结点或结点之间的约束条件；V表示目标软件运行s可以覆盖到的软件漏洞集合，V＝{v1,v2,…,vi},vi表示目标应用程序中的第i个覆盖的软件漏洞；OP表示相关操作的集合；T表示转换操作的集合，T＝{T1，T2}，T1，T2是两个不同的转换操作；M表示变异算子的集合，M＝{m1,…,mi,…,mw,OMMutator}；其中，mi表示第i个单维变异算子，集合中包括w个单维变异算子，OMMutator表示一个有导向的多维变异算子；BDDTaint表示查找软件漏洞相关输入元素操作；Symb表示混合符号执行操作；Slv表示一个约束关系维护操作；sampletree表示一个根据结构或者协议知识解析样本数据s得到的样本树,mediumtree表示中间树,newtree表示新树,testcase表示测试例。

设计方案

1.一种软件模糊测试方法，用于提高软件漏洞分析效率，其特征在于，所述方法包括如下步骤：

S1、基于软件测试阶段获取的历史数据、测试用例及日志信息，提取并建立基于自适应逼近漏洞模型AAMV的探测数据样本，所述探测数据样本包括：软件漏洞相关输入元素和软件漏洞无关输入元素；

S2、基于细粒度污点动态分析所述探测数据样本中的软件漏洞相关输入元素，生成基于探测数据样本的输入数据，具体包括：

根据目标程序潜在软件漏洞运行的反馈信息，构造逼近函数选择相应的遗传算法操作，通过迭代运算的方式生成越来越逼近异常的基于探测数据样本的输入数据；

S3、基于所述输入数据的混合符号执行生成高覆盖率的探测数据，具体包括：混合符号执行把所述输入数据进行格式变换，通过把转化后的所述输入数据中的数据元素作为符号值，收集程序路径上对输入数据的约束条件，通过约束求解，生成高覆盖率的探测数据；

S4、基于所述高覆盖率的探测数据进行模糊测试以检测是否存在软件漏洞；

所述自适应逼近漏洞模型AAMV具体为：

AAMV＝(s,L,I,C,V,OP,Result)；

OP＝{T,M,BDDTaint,Symb,Slv}；

Result＝{sampletree,mediumtree,newtree,testcase}；

其中，s表示某个样本数据；

L＝{l_{1<\/sub>,l2<\/sub>,…,li<\/sub>,…,lp<\/sub>},L表示叶子结点集合,l表示网络协议或文件结构中的一个语义单位；}

I＝{i_{1<\/sub>,i2<\/sub>,…,ij<\/sub>,…,iq<\/sub>}，I表示中间结点集合,i表示网络协议或文件结构中的一个语义单位；}

C表示约束条件的集合，描述结点或结点之间的约束条件；

V表示目标软件运行s可以覆盖到的软件漏洞集合，V＝{v1,v2,…,vi},vi表示目标应用程序中的第i个覆盖的软件漏洞；

OP表示相关操作的集合；

T表示转换操作的集合，T＝{T_{1<\/sub>，T2<\/sub>}，T1<\/sub>，T2<\/sub>是两个不同的转换操作；}

M表示变异算子的集合，M＝{m_{1<\/sub>,…,mi<\/sub>,…,mw<\/sub>,OMMutator}；}

其中，m_{i<\/sub>表示第i个单维变异算子，集合中包括w个单维变异算子，OMMutator表示一个有导向的多维变异算子；BDDTaint表示查找软件漏洞相关输入元素操作；Symb表示混合符号执行操作；Slv表示一个约束关系维护操作；sampletree表示一个根据结构或者协议知识解析样本数据s得到的样本树,mediumtree表示中间树,newtree表示新树,testcase表示测试例。}

2.根据权利要求1所述的软件模糊测试方法，其特征在于，所述约束条件包括：长度关系、个数关系或者校验和。

3.根据权利要求1所述的软件模糊测试方法，其特征在于，所述自适应逼近漏洞模型AAMV中还包括：参数MAX表示每个软件漏洞运行的最大代数，常数α表示OMMutator中每代个体中生成的探测数据的数目。

4.根据权利要求2或3所述的软件模糊测试方法，其特征在于，所述多维变异算子OMMutator的运行时间复杂度为O(m)，其中m＝|V|。

5.根据权利要求4所述的软件模糊测试方法，其特征在于，所述污点动态分析过程具体为，

令影子内存为设计说明书

技术领域

在本发明属于软件模糊检测领域，涉及一种基于自适应逼近漏洞模型的模糊测试方法。

背景技术

模糊测试已发现大量未知安全漏洞，是一种快速有效的动态脆弱性分析技术，已被业界广泛使用。BSIMM的一份调查中显示，他们所调查的九个领先的安全产品团队全部在使用模糊测试技术，商业模糊测试领域的调查也显示，80%的领先的服务提供商和设备制造商正在使用模糊测试技术。比如微软公司旗下的产品，在正式发布之前发现安全漏洞的20%-25%均是由模糊测试分析到的。

目前，对模糊测试没有统一的定义，有人称其为Fuzz测试，有人称为杂凑。本发明统称为模糊测试（Fuzzing），通过向目标软件提供非正常的输入数据并监控运行中的异常来分析软件漏洞。模糊测试过程通常包含六个阶段：确定目标、识别输入、生成模糊测试探测样本、执行模糊探测数据、监控目标异常、确认漏洞可利用性。

现有模糊测试技术普遍存在以下两个问题：

（1）测试效率低，由于模糊测试不能清楚了解被测目标的内部逻辑情况，从而产生了大量无效测试数据。

（2）代码覆盖率低，已有模糊测试用例的产生依赖于有限的一种生产技术，而且测试数据用例一旦产生就不做优化处理。

发明内容

为解决上述技术问题，本发明提出了一种基于自适应逼近漏洞模型的模糊测试方法，指导探测数据生成，提高软件漏洞分析效力。

根据本发明的实施例，本发明提出了一种软件模糊测试方法，所述方法包括如下步骤：

S1、基于软件测试阶段获取的历史数据、测试用例及日志信息，提取并建立基于自适应逼近漏洞模型AAMV的探测数据样本；

S2、基于细粒度污点动态分析所述探测数据样本中的软件漏洞相关输入元素，生成基于探测数据样本的输入数据；

S3、基于所述输入数据的混合符号执行生成高覆盖率的探测数据；

S4、基于所述探测数据进行模糊测试以检测是否存在漏洞。

优选的，所述自适应逼近漏洞模型AAMV具体为，

AAMV＝(s,L,I,C,V,OP,Result)；

OP＝{T,M, BDDTaint,Symb,Slv}；

Result={sampletree, mediumtree, newtree,testcase}；

其中，s表示某个样本数据；

L={l<\/i>_{1<\/i><\/sub>,l<\/i>2<\/i><\/sub>,…,l<\/i>i<\/i><\/sub>,…,l<\/i>p<\/i><\/sub>},L表示叶子结点集合, l<\/i>表示网络协议或文件结构中的一个语义单位；}

I={i<\/i>_{1<\/i><\/sub>,i<\/i>2<\/i><\/sub>,…,i<\/i>j<\/i><\/sub>, …,i<\/i>q<\/i><\/sub>}，I表示中间结点集合,i<\/i>表示网络协议或文件结构中的一个语义单位；}

C表示约束条件的集合，描述结点或结点之间的约束条件；

V表示目标软件运行s可以覆盖到的漏洞集合，V={v1,v2, …, vi},vi表示目标应用程序中的第i个覆盖的漏洞；

OP表示相关操作的集合；

T表示转换操作的集合，T={T_{1<\/sub>，T2<\/sub>}，T1<\/sub>，T2<\/sub>是两个不同的转换操作；}

M表示变异算子的集合，M ={ m<\/i>_{1<\/sub>,…,m<\/i>i<\/i><\/sub>,…,m<\/i>w<\/i><\/sub>, OMMutator}；}

假定有w个单维变异算子，OMMutator表示一个有导向的多维变异算子；BDDTaint表示查找漏洞相关输入元素操作；Symb表示混合符号执行操作；Slv表示一个约束关系维护操作；sampletree表示一个根据结构或者协议知识解析样本数据s得到的样本树,mediumtree表示中间树, newtree表示新树,testcase表示测试例。

优选的，所述约束条件包括长度关系、个数关系或者校验和。

优选的，所述自适应逼近漏洞模型AAMV中还包括，参数MAX表示每个漏洞运行的最大代数，常数α表示OMMutator中每代个体中生成的探测数据的数目。

优选的，所述多维变异算子OMMutator的运行时间复杂度为O(m)，其中m=|V|。

优选的，所述探测数据样本包括漏洞相关输入元素和漏洞无关输入元素，其中漏洞相关输入元素只占很少一部分，样本中的绝大部分探测数据是漏洞无关输入元素。

优选的，基于细粒度污点动态分析所述探测数据样本中的漏洞相关输入元素，生成基于探测数据样本的输入数据，具体为，所述查找漏洞相关输入元素操作的BDDTaint实现动态细粒度污点分析，负责对轨迹上的每条指令进行语法和语义解析。

优选的，所述污点分析过程具体为，

令影子内存为S={rg}，其中，r表示寄存器编号或者内存地址，g表示集合关系的压缩表示ROBDD结构；

令Q代表程序执行上下文，对于程序执行上下文Q和影子内存S，T(S,Q)表示指令的污点传播函数，用来描述执行指令时污点数据的传播过程，给定执行轨迹<I,N>，I代表指令序列，N代表轨迹上的指令总数，假定T_{j<\/sub>()代表第j条指令的污点传播函数，S0<\/sub>和Q0<\/sub>分别表示初始影子内存和初始上下文，计算出Tj<\/sub>Tj-1<\/sub>…T0<\/sub>(S0<\/sub>,Q0<\/sub>)以完成污点分析。}

优选的，所述基于所述输入数据的混合符号执行生成高覆盖率的探测数据，包括：混合符号执行把所述输入数据进行格式变换，通过把转化后的所述输入数据中的数据元素做为符号值，收集程序路径上对输入数据的约束条件，通过约束求解，生成高覆盖率的探测数据。优选的，所述符号执行通过把转化后的所述输入数据当做符号值，还包括，漏洞相关输入元素视为符号值，而对其他输入元素使用真实值；或者，仅在测试目标中使用符号执行即符号域，其他环境转换为具体执行即具体域。

优选的，所述符号执行包括，

rec代表真实执行上下文环境，记录寄存器的真实值；sec代表符号化上下文环境，记录寄存器的符号值；内存地址\/物理寄存器标记为r，符号值标记为t，sec就是r到t的映射，记为{rt}；

分别取出轨迹上的每条指令j，并根据轨迹中记录的j的上下文来更新真实执行环境rec，进一步调用指令翻译函数translateBinarytoIR，将指令j翻译至LLVM中间代码，在中间代码上进行符号计算。

优选的，若没有发现漏洞，则产生的探测数据最大数目为α×MAX×m。

本发明结合动态细粒度污点分析、混合符号执行及遗传算法变异技术，提出了一种基于树结构的自适应逼近漏洞模型AAMV，指导探测数据生成，提高软件漏洞分析效力。细粒度污点分析查找脆弱点相关输入元素，缩小输入元素的变异空间。混合符号执行及约束求解技术提供了对路径深度执行的能力，提高了模糊测试技术的代码覆盖率。基于OMMutator算子的多维探测数据生成技术在脆弱点命中率相同情况下极大减少了探测数据规模。

附图说明

图1为本发明提出的软件模糊测试方法流程图；

图2为本发明提出的AAMV模型探测数据生成流程图；

图3为本发明提出的BMP格式图像文件中的相关输入元素示例图；

图4为本发明提出的文件读取系统调用模拟算法图；

图5为本发明提出的面向二进制指令的符号执行算法图；

具体实施方式

以下结合附图对本发明的具体实施方式作出详细说明。

模糊测试：发现大量未知安全漏洞，是一种快速有效的动态脆弱性分析技术，已被业界广泛使用。

模糊测试生成技术：旨在如何构造易于触发漏洞异常操作的探测数据。

软件漏洞是造成信息安全问题的主要根源之一。如何有效的分析出漏洞已成为信息安全领域研究重点。对于未公开的复杂数据格式，目前的模糊测试方法基本采用对正常探测样本数据随机变异生成探测数据。由于这种探测数据的生成方式过于盲目，严重制约了模糊测试工具的能力和效率。究其原因，没有很好的利用程序内部状态信息引导模糊测试生成探测数据。由于缺少引导性，故生成的探测数据就没有针对性，常常会指向同一条执行路径，探测数据的路径覆盖率较低，无法保证探测的全面性，故存在漏报。本发明结合动态细粒度污点分析、混合符号执行及遗传算法变异技术，提出了一种基于树结构的自适应逼近漏洞模型AAMV，指导探测数据生成，提高软件漏洞分析效力。细粒度污点分析查找脆弱点相关输入元素，缩小输入元素的变异空间。混合符号执行及约束求解技术提供了对路径深度执行的能力，提高了模糊测试技术的代码覆盖率。基于OMMutator算子的多维探测数据生成技术在脆弱点命中率相同情况下极大减少了探测数据规模。

根据本发明的实施例，本发明提出了一种软件模糊测试方法，如图1所示，该方法包括如下步骤：

S1、基于软件测试阶段获取的历史数据、测试用例及日志信息，提取并建立基于自适应逼近漏洞模型AAMV的探测数据样本；

S2、基于细粒度污点动态分析所述探测数据样本中的漏洞相关输入元素，生成基于探测数据样本的输入数据；

S3、基于所述输入数据的混合符号执行以生成高覆盖率的探测数据；

S4、基于所述探测数据进行模糊测试以检测是否存在漏洞。

首先，建立基于自适应逼近漏洞模型AAMV的探测数据样本。

在本实施例中，提出的是一个基于树结构的自适应逼近漏洞模型（AdaptiveApproximation Model of Vulnerability， AAMV），指导探测数据生成，具体为，

AAMV＝(s,L,I,C,V,OP,Result)；

OP＝{T,M, BDDTaint,Symb,Slv}；

Result={sampletree, mediumtree, newtree,testcase}；

其中，s表示某个样本数据；

L={l<\/i>_{1<\/i><\/sub>,l<\/i>2<\/i><\/sub>,…,l<\/i>i<\/i><\/sub>,…,l<\/i>p<\/i><\/sub>},L表示叶子结点集合, l<\/i>表示网络协议或文件结构中的一个语义单位；}

I={i<\/i>_{1<\/i><\/sub>,i<\/i>2<\/i><\/sub>,…,i<\/i>j<\/i><\/sub>,…,i<\/i>q<\/i><\/sub>}，I表示中间结点集合,i<\/i>表示网络协议或文件结构中的一个语义单位；}

C表示约束条件的集合，描述结点或结点之间的约束条件；

V表示目标软件运行s可以覆盖到的漏洞集合，V={v1,v2, …, vi},vi表示目标应用程序中的第i个覆盖的漏洞；

OP表示相关操作的集合；

T表示转换操作的集合，T={T_{1<\/sub>，T2<\/sub>}，T1<\/sub>，T2<\/sub>是两个不同的转换操作；}

M表示变异算子的集合，M ={ m<\/i>_{1<\/sub>,…,m<\/i>i<\/i><\/sub>,…,m<\/i>w<\/i><\/sub>, OMMutator}；}

假定有w个单维变异算子，OMMutator表示一个有导向的多维变异算子；BDDTaint表示查找漏洞相关输入元素操作；Symb表示混合符号执行操作；Slv表示一个约束关系维护操作；sampletree表示一个根据结构或者协议知识解析样本数据s得到的样本树，sampletree中所有的结点由叶子结点L、中间结点I和约束条件C组成。mediumtree表示中间树, newtree表示新树,testcase表示测试例。

AAMV生成探测数据的过程如图2所示，第10行的常数MAX表示OMMutator每个漏洞运行的最大代数，第13行中的常数α表示OMMutator中每代个体中生成的探测数据的数目。

T<\/i>_{1<\/sub>转换s生成sampletree，OMMutator针对每个漏洞ve利用每代个体运行时的反馈信息设计逼近函数，选择相应的遗传操作，生成下一代探测数据。}

智能多维变异算子OMMutator的运行时间复杂度为O(m)，其中m=|V|。模糊测试在对目标程序进行多维变异探测的过程当中，如果发现漏洞则提前退出，如第21行所示，如没有发现漏洞，则产生的探测数据最大数目为α×MAX×m。既然α、MAX是由用户设定的常数，那么 OMMutator 的运行时间复杂度主要取决于探测数据的数目，则多维变异算子OMMutator的运行时间复杂度为O(m)。因此，基于自适应逼近漏洞模型中的探测数据生成技术不会带来样本数据的组合爆炸问题。

第16行显示AAMV在基于样本数据变异完探测数据之后，通过Slv修正相关输入元素的值，以满足输入元素之间的约束关系C。影响漏洞的输入元素由细粒度污点分析BDDTaint而获得，约束关系C是由基于混合符号执行技术Symbolic而求解得到，在满足约束条件的情况下变异影响漏洞的输入元素生成的探测数据会更加易于触发漏洞。

模糊测试中的正常样本是由漏洞相关输入元素和漏洞无关输入元素组成，漏洞相关输入元素只占很少一部分，绝大部分数据是漏洞无关输入元素，如图3所示，一个BMP格式图像文件有上千字节，对于BMP格式图像，修改像素输入元素时通常仅仅改变了图片的呈现效果，并不能触发漏洞。因为像素输入元素不会影响漏洞敏感操作。而漏洞敏感操作（比如内存分配等）通常会受到BMP图像文件头中的某些控制信息（比如图像高度、宽度）的影响。

我们首先需要识别出正常探测样本中的漏洞相关输入元素，然后有针对性地变异生成新的探测数据，进而对目标程序进行探测。由此生成的探测数据，既保留了原探测样本的正常结构，又变异了漏洞相关输入元素。相比传统模糊测试，该方法有效解决了盲目变异测试目标整体输入元素空间的问题，提高了探测效率，且生成的探测数据直接作用在漏洞敏感操作，更易于触发程序出现异常。

表1给出了细粒度污点分析的一个例子。表中的第一列代表顺序执行的程序代码。第一行程序表示从fr文件中读前4个字节并赋予a变量，前提条件文件句柄fr初始偏移为0；第二行程序表示再从fr文件中读4个字节并赋予b变量；第三行程序表示将a变量和b变量求和，然后将值赋予c变量。对应于第一列程序第二列显示了传统动态污点的分析步骤。若将fr标识为污点源，1表示是污点数据，a、b变量的值直接取自污点源，因此被标记为污点数据1；c变量的值与a、b变量都有关，随即也被标记为污点数据1。相较于第二列，第三列则显示了细粒度动态污点分析步骤。细粒度污点分析标记每个污点数据存储单元，通常一个字节一个标签。因此a变量与集合{0,1,2,3}相映射，b变量与集合{4,5,6,7}相映射；执行第三句程序时，由于变量c同时与a、b变量相关，c变量则与集合{0,1,2,3,4,5,6,7}相映射。

由于需标记与跟踪每一个污点数据单位。而一个污点数据单元又存在有赖于多个污点数据，如表1中的0数据单元同时有赖于a和c变量。所以一个污点数据单元的污点属性t就需要用集合结构来描述。若以字节为单位，污点数据的长度为x字节时，那么细粒度动态污点分析则需创建x个污点标签。再假定程序中污点数据单元又有赖于y个污点数据。极限状况下，每一个污点数据单元都有赖于y个污点数据。若污点标签用整数变量来标识，共需创建y∗x∗sizeof(int)大小的影子内存空间。细粒度动态污点分析过程中需要很大的内存空间。

还存在一个无法回避的问题，在细粒度动态污点分析过程中，会有大量集合合并操作。如c=a+b，如果a和b都标记为污点数据时，c变量映射到这两个变量相对应的污点属性合并集，即{0,1,2,3,4,5,6,7}。在细粒度动态污点分析过程中，x86机器指令层包含大量算术运算指令、逻辑运算指令类的二元操作指令。而一条二元操作指令极可能引发一系列集合的合并操作，这也将导致极严重的性能损耗。虽然有些污点分析系统实现了细粒度污点分析，但并未考虑如何减少分析过程中的内存消耗、提高细粒度污点分析的效率。本发明提出并实现一种基于归约有序二元决策图（简称ROBDD，Reduced Ordered Binary DecisionDiagram）的污点分析技术，该方法能够减少分析过程中的内存需求数量，提高细粒度动态污点分析的性能。

表1分析实例

二元决策图（简称BDD，Binary Decision Diagram）是被用来表达一个布尔函数的一种数据结构，即与布尔函数真值表等价。事实上，BDD是有向无环图(G, E)，且具有以下三点特征：

（1）含有一个根节点；

（2）含有两个出度为0的终节点，这两个节点分别标识为0和1；

（3）除终节点外，其他所有节点出度均为2；两条边分别为0边和1边，在BDD图中分别用虚、实线表示。

ROBDD是BDD结构的压缩图，它除去BDD结构中的同构子图与冗余节点。已被证明ROBDD也与布尔函数真值表等价，目前已是符号模型检验的不可缺少的组成部分，关键是各种集合操作均可在基于ROBDD的集合表达上进行。以整数集合为例子讨论，不失一般性。这里仅以4比特位可表示的整数为例子，把4个比特位依次等价于4个布尔变量：r_{0<\/sub>r1<\/sub>r2<\/sub>r3<\/sub>，r0<\/sub>表示最低比特位。这样整数就被抽象成赋值给4个布尔变量。假设整数x的二进制表达式为<a3<\/sub>,a2<\/sub>,a1<\/sub>,a0<\/sub>>，整数集合C就等价为布尔函数f(r3<\/sub>,r2<\/sub>,r1<\/sub>,r0<\/sub>)，当且仅当：}

xC⇒f<\/i>(a_{3<\/sub>,a2<\/sub>,a1<\/sub>,a0<\/sub>) =1}

xC⇒f<\/i>(a_{3<\/sub>,a2<\/sub>,a1<\/sub>,a0<\/sub>) =0}

若集合C1与布尔函数f1等价，且集合C2与布尔函数f2等价，那么集合C1∪C2也与f1f2等价。同理，集合C1∩C2也与f1f2等价。ROBDD结构是与布尔函数真值表等价已被证明，且ROBDD结构可以很好的描述集合关系，所以ROBDD结构支持各类集合操作。对于一个含有x个节点，一个含有y个节点的ROBDD结构，ROBDD结构的合并操作的复杂度为O(x∗y)。ROBDD结构需要的存储空间要比布尔函数真值表的需求小的多，原因是ROBDD结构有效除去了冗余信息，所以，ROBDD结构所表达集合的势通常远远大于ROBDD内部的结点数。

BDDTaint模块实现动态细粒度污点分析。负责对轨迹上每条指令进行语法和语义解析，令影子内存为S={rg}，这里r表示寄存器编号或者内存地址，g表示ROBDD结构。令Q代表程序执行上下文。对于程序执行上下文Q和影子内存S，T(S,Q)表示指令的污点传播函数，用来描述执行指令时污点数据的传播过程。给定执行轨迹<I,N>，I代表指令序列，N代表轨迹上的指令总数，假定T_{j<\/sub>()代表第j条指令的污点传播函数，S0<\/sub>和Q0<\/sub>分别表示初始影子内存和初始上下文。污点分析就是计算Tj<\/sub>oTj-1<\/sub>o…oT0<\/sub>(S0<\/sub>,Q0<\/sub>)的过程。}

最初引入污点数据的指令（如系统调用）的污点传播函数负责在影子内存S中初始化最初的污点映射关系。图4描述了文件读系统调用的污点传播函数。对于其他指令的污点传播函数，BDDTaint模块会根据指令的语义进行相应得处理。目前BDDTaint模块当前主要跟踪数据依赖关系之间的污点传播，支持绝大部分常用x86指令。

污点分析作为导向模糊测试的补充，基于混合符号执行的探测样本生成技术能对程序执行路径深度分析，能以代码覆盖率为指导，生成高覆盖率探测数据。符号执行通过把输入数据当做符号值，来收集程序路径上对输入数据的约束条件。再通过约束求解，就可以生成高覆盖率的探测数据。同样，在漏洞敏感操作前，如果操作数包含符号变量，可以进一步检查路径约束是否能确保该操作的安全。

混合符号执行一个无法回避的问题就是路径爆炸引起的执行效率低。大量符号计算会引起路径爆炸，大量的约束求解都会使混合符号执行效率极低，以至于大型应用程序无法符号执行。因此，许多经典符号执行系统目前主要应用在小型程序或者单元函数的测试上。

为了提高混合符号执行效率，我们采取了两种策略，一是仅把漏洞相关输入元素视为符号值，而对其他输入元素使用真实值。二是借鉴S2E选择性符号执行的思想，通常情况下需要探测的目标程序往往是很少的一部分，大部分是测试环境。因此我们仅在测试目标中使用符号执行即符号域，其他环境转换为具体执行即具体域，在具体域应用程序用具体值代替符号值执行时仅有一条执行路径，降低了符号执行的开销，有效缓解了路径爆炸问题。

符号执行模块在对执行轨迹重放过程中，一方面维护程序执行的真实上下文环境，另一方面维护程序执行的符号化上下文环境。图5给出了符号执行模块的算法。rec（real execution context）代表真实执行上下文环境，记录寄存器的真实值。sec（symbolic execution context）代表符号化上下文环境，记录寄存器的符号值。我们将内存地址\/物理寄存器标记为r，符号值标记为t，sec就是r到t的映射，记为{rt}。符号执行模块分别取出轨迹上的每条指令j，并根据轨迹中记录的j的上下文来更新真实执行环境rec。进一步调用指令翻译函数translateBinarytoIR，符号执行模块将指令j翻译至LLVM中间代码，在中间代码上进行符号计算。

为了使模糊测试技术能够有效分析出实际目标程序中对探测数据正确度和畸形度要求高的漏洞，本发明给出了一个自适应逼近漏洞模型AAMV。该模型首先应用细粒度动态污点分析获得漏洞相关的输入元素，然后结合混合符号执行和约束求解技术，有针对性更新与所变异元素有约束关系的其它输入元素，最后该模型中有导向的多维变异算子，会根据目标程序潜在漏洞运行的反馈信息，设计逼近函数选择相应的遗传算法操作，指导模糊测试生成技术生成越来越逼近异常的探测数据。根据对缓冲区溢出漏洞实例的测试数据显示，基于随机变异探测数据的zzuf平均需要生成探测数据上百万个，而本发明提出的基于AAMV模型的生成方法平均需要生成探测数据约二千多个，效率得到很大提升。

对于本领域技术人员而言，显然本发明实施例不限于上述示范性实施例的细节，而且在不背离本发明实施例的精神或基本特征的情况下，能够以其他的具体形式实现本发明实施例。因此，无论从哪一点来看，均应将实施例看作是示范性的，而且是非限制性的，本发明实施例的范围由所附权利要求而不是上述说明限定，因此旨在将落在权利要求的等同要件的含义和范围内的所有变化涵括在本发明实施例内。不应将权利要求中的任何附图标记视为限制所涉及的权利要求。此外，显然“包括”一词不排除其他单元或步骤，单数不排除复数。系统、装置或终端权利要求中陈述的多个单元、模块或装置也可以由同一个单元、模块或装置通过软件或者硬件来实现。第一，第二等词语用来表示名称，而并不表示任何特定的顺序。

最后应说明的是，以上实施方式仅用以说明本发明实施例的技术方案而非限制，尽管参照以上较佳实施方式对本发明实施例进行了详细说明，本领域的普通技术人员应当理解，可以对本发明实施例的技术方案进行修改或等同替换都不应脱离本发明实施例的技术方案的精神和范围。

设计图