一种基于人工鱼群算法的软件漏洞检测方法

摘要

本发明涉及软件漏洞检测技术领域，公开了一种基于人工鱼群算法的软件漏洞检测方法，该方法，基于人工鱼群算法构建用于执行种子变异模型，通过种子文件的状态参数计算出种子的路径能量参数，基于路径能量参数确定单个种子最优状态和种子队列最优状态，从而挑选出待变异的最优种子。本发明解决了现有技术存在的模糊测试过程中漏洞检测效果差、效率低、难以追踪程序执行情况等问题。

权利要求

1.一种基于人工鱼群算法的软件漏洞检测方法，其特征在于，基于人工鱼群算法构建用于执行种子变异模型，通过种子文件的状态参数计算出种子的路径能量参数，基于路径能量参数确定单个种子最优状态和种子队列最优状态，利用人工鱼群算法构建种子变异模型，获取最优种子，从而挑选出待变异的最优种子；

获取最优种子包括以下步骤：

S31，获取种子的基本状态信息；

S32，计算每个种子适应度的值，获取全局最优解种子的状态；

S33，对每个种子开展评估，根据评估结果确定种子变异方式；

步骤S31中，基本的状态信息包括队列中种子的总数Num、种子的存储空间占用大小Size、种子执行时间TimeExc、种子的代码路径覆盖率FwRate、低频路径占比LowRate、路径深度Depth、路径分支数Branch、种子被评估次数SelectNum、种子聚集度因子Ω、种子程序执行耗时的阈值Time；

步骤S32中，计算公式为：

；

其中，

TimeAssess=种子程序执行耗时/所有种子的平均耗时；

SizeAssess=种子的存储空间占用大小/所有种子的平均大小。

2.根据权利要求1所述的一种基于人工鱼群算法的软件漏洞检测方法，其特征在于，包括以下步骤：S1，原始种子数据集获取：获取原始种子数据集；

S2，生成种子队列：利用原始种子数据集生成种子队列，并将种子队列依次输入软件程序，利用代码插桩跟踪程序运行状态，记录路径覆盖范围指标、路径深度指标、分支路径数指标；

S3，最优种子获取：利用人工鱼群算法构建种子变异模型，获取最优种子；

S4，程序运行：将最优种子输入软件程序运行，观察最优种子程序运行状态；

S5，异常判断：判断程序是否异常；若是，则记录运行状态；若否，则更新种子的全局状态，并返回步骤S2。

3.根据权利要求2所述的一种基于人工鱼群算法的软件漏洞检测方法，其特征在于，步骤S33中，种子变异方式为觅食型变异，确定种子变异方式为觅食型变异的方法为：将全局最优解的种子设为Xmax，当前种子的状态为i，在当前种子队列位置附近随机选中种子Xj，在求解路径能量参数最大值的过程中，若Poweri小于Powerj，则向Xmax和Xj的矢量和方向步进一个种子的位置增加量；

一个种子的位置增加量=(0,1)之间的随机值*种子突变字节数*（Xj种子的状态矢量+最优解种子Xmax的状态矢量‑Xi种子的状态矢量）/种子大小差值；

如果不满足觅食型变异条件，则需再次随机进行种子选择，评估当前种子是否符合变异条件；如果评估Select_num次后仍旧不符合条件，则随机选择字节进行变异。

4.根据权利要求3所述的一种基于人工鱼群算法的软件漏洞检测方法，其特征在于，步骤S33中，种子变异方式为群聚型变异，确定种子变异方式为群聚型变异的方法为：将全局最优解的种子设为Xmax，当前种子的状态为i，参照当前种子代码路径覆盖率数值周围紧邻的伙伴种子数目n和中心位置Xz，假如当前种子位置中心的程序适应度和当前种子位置中心种子数的比率大于聚集度因子Ω和当前种子程序适应度的乘积，说明伙伴种子的中心可触发不少的程序崩溃，并且伙伴种子间的聚集度不高，则可以向Xz和Xmax的矢量和方向进行变异；如果不满足群聚型变异条件，则进行觅食型变异。

5.根据权利要求4所述的一种基于人工鱼群算法的软件漏洞检测方法，其特征在于，步骤S33中，种子变异方式为追尾型变异，确定种子变异方式为追尾型变异的方法为：将全局最优解的种子设为Xmax，当前种子的状态为Xi，参照当前种子代码路径覆盖率数值周围紧邻有最大Powerj的伙伴Xj，假如Xj程序适应度和附近伙伴种子数的比率大于聚集度因子Ω和当前种子程序适应度的乘积，说明伙伴种子Xj可触发不少的程序崩溃，并且附近种子间的聚集度不高，则可以向Xj和Xmax的矢量和方向进行变异。

6.根据权利要求4所述的一种基于人工鱼群算法的软件漏洞检测方法，其特征在于，步骤S33中，种子变异方式为跳跃型变异，确定种子变异方式为跳跃型变异的方法为：选中种子队列中低频路径占比超过一半、路径深度大于3、触发新路径的种子，随机设定被选种子的变异参数；其中，某被选种子的变异后状态=目前状态+(0,1)随机值*设定的参数*被选种子的代码路径覆盖率。

说明书

一种基于人工鱼群算法的软件漏洞检测方法

技术领域

[0001] 本发明涉及软件漏洞检测技术领域，具体是一种基于人工鱼群算法的软件漏洞检测方法。

背景技术

[0002] 随着计算机和计算机网络的普及应用，软件产业得到了飞速发展，已从国防技术、医疗卫生、金融证券等专业领域进入到了普通人的日常生活中。软件功能越来越强，软件的复杂度也随之上升，致使软件的安全性不可控。另一方面，通过对软件进行漏洞挖掘来获取高价值0day漏洞，利用这类漏洞对目标进行隐蔽和精确的打击，而安全防护系统由于不具备检测此类漏洞的能力，所以这种攻击往往会对目标系统造成严重影响，且不容易追根溯源。由此可以看出，如何提升软件程序安全性已迫在眉睫。

[0003] 漏洞检测是提高软件可靠性及安全性的有效手段，可以尽早的发现漏洞，进而通知软件厂商进行修复，避免漏洞被黑客利用。软件漏洞检测的时效性要求导致之前主要凭借手工经验进行的检测活动不能适应技术的发展，应用软件的复杂度不断增加导致手工检测需要占用极大的人力成本，需要经验丰富的研究人员花费巨大精力对程序执行流程进行逆向分析，周期长效率低。所以，自动漏洞挖掘和检测技术是研究的重点方向。目前常见的自动漏洞挖掘技术包括模糊测试、污点分析、符号执行等，而模糊测试是这些方向中非常有效的技术之一。

[0004] 模糊测试作为重要的漏洞挖掘和检测技术方向，虽然其效果显著，但目前的缺点也不可小视，比如：

[0005] (1)当软件程序输入的数据结构复杂度高时，随机生成的种子文件很有可能通不过程序起始阶段的校验函数或语法解析函数，往往导致效果很不理想；

[0006] (2)已有的模糊测试效率低下，其生成的种子文件目标性不明确，为保证其基本的代码覆盖能力，会构造出大量冗余的种子文件，无形中加重了测试引擎的负担，使其模糊测试的效果不甚理想；

[0007] (3)目前的模糊测试技术在生成种子文件时一般采用随机机制或者预定义模板方式，在没有对目标程序进行深入逆向分析时，很难清晰构建出程序执行流程，也就无法追踪程序执行情况。

发明内容

[0008] 为克服现有技术的不足，本发明提供了一种基于人工鱼群算法的软件漏洞检测方法，解决现有技术存在的模糊测试过程中漏洞检测效果差、效率低、难以追踪程序执行情况等问题。

[0009] 本发明解决上述问题所采用的技术方案是：

[0010] 一种基于人工鱼群算法的软件漏洞检测方法，基于人工鱼群算法构建用于执行种子变异模型，通过种子文件的状态参数计算出种子的路径能量参数，基于路径能量参数确定单个种子最优状态和种子队列最优状态，从而挑选出待变异的最优种子。

[0011] 作为一种优选的技术方案，包括以下步骤：

[0012] S1，原始种子数据集获取：获取原始种子数据集；

[0013] S2，生成种子队列：利用原始种子数据集生成种子队列，并将种子队列依次输入软件程序，利用代码插桩跟踪程序运行状态，记录路径覆盖范围指标、路径深度指标、分支路径数指标；

[0014] S3，最优种子获取：利用人工鱼群算法构建种子变异模型，获取最优种子；

[0015] S4，程序运行：将最优种子输入软件程序运行，观察最优种子程序运行状态；

[0016] S5，异常判断：判断程序是否异常；若是，则记录运行状态；若否，则更新种子的全局状态，并返回步骤S2。

[0017] 作为一种优选的技术方案，步骤S3包括以下步骤：

[0018] S31，获取种子的基本状态信息；

[0019] S32，计算每个种子适应度的值，获取全局最优解种子的状态；

[0020] S33，对每个种子开展评估，根据评估结果确定种子变异方式。

[0021] 作为一种优选的技术方案，步骤S31中，基本的状态信息包括队列中种子的总数Num、种子的存储空间占用大小Size、种子执行时间TimeExc、种子的代码路径覆盖率FwRate、低频路径占比LowRate、路径深度Depth、路径分支数Branch、种子被评估次数SelectNum、种子聚集度因子Ω、种子程序执行耗时的阈值Time。

[0022] 作为一种优选的技术方案，步骤S32中，计算公式为：

[0023] ；

[0024] 其中，

[0025] TimeAssess=种子程序执行耗时/所有种子的平均耗时；

[0026] SizeAssess=种子的存储空间占用大小/所有种子的平均大小。

[0027] 作为一种优选的技术方案，步骤S33中，种子变异方式为觅食型变异，确定种子变异方式为觅食型变异的方法为：

[0028] 将全局最优解的种子设为Xmax，当前种子的状态为i，在当前种子队列位置附近随机选中种子Xj，在求解路径能量参数最大值的过程中，若Poweri

[0029] 一个种子的位置增加量=(0,1)之间的随机值*种子突变字节数*（Xj种子的状态矢量+最优解种子Xmax的状态矢量‑Xi种子的状态矢量）/种子大小差值；

[0030] 如果不满足觅食型变异条件，则需再次随机进行种子选择，评估当前种子是否符合变异条件；如果评估Select_num次后仍旧不符合条件，则随机选择字节进行变异。

[0031] 作为一种优选的技术方案，步骤S33中，种子变异方式为群聚型变异，确定种子变异方式为群聚型变异的方法为：

[0032] 将全局最优解的种子设为Xmax，当前种子的状态为i，参照当前种子代码路径覆盖率数值周围紧邻的伙伴种子数目n和中心位置Xz，假如当前种子位置中心的程序适应度和当前种子位置中心种子数的比率大于聚集度因子Ω和当前种子程序适应度的乘积，说明伙伴种子的中心可触发不少的程序崩溃，并且伙伴种子间的聚集度不高，则可以向Xz和Xmax的矢量和方向进行变异；如果不满足群聚型变异条件，则进行觅食型变异。

[0033] 作为一种优选的技术方案，步骤S33中，种子变异方式为追尾型变异，确定种子变异方式为追尾型变异的方法为：

[0034] 将全局最优解的种子设为Xmax，当前种子的状态为Xi，参照当前种子代码路径覆盖率数值周围紧邻有最大Powerj的伙伴Xj，假如Xj程序适应度和附近伙伴种子数的比率大于聚集度因子Ω和当前种子程序适应度的乘积，说明伙伴种子Xj可触发不少的程序崩溃，并且附近种子间的聚集度不高，则可以向Xj和Xmax的矢量和方向进行变异。

[0035] 作为一种优选的技术方案，步骤S33中，种子变异方式为跳跃型变异，确定种子变异方式为跳跃型变异的方法为：

[0036] 选中种子队列中低频路径占比超过一半、路径深度大于3、触发新路径的种子，随机设定被选种子的变异参数；其中，某被选种子的变异后状态=目前状态+(0,1)随机值*设定的参数*被选种子的代码路径覆盖率。

[0037] 本发明相比于现有技术，具有以下有益效果：

[0038] （1）本发明在进行待变异种子挑选过程时，需要考虑种子的多类状态信息，利用人工鱼群算法能把种子状态信息以较小的运算开销作用于待变异种子挑选，另外，对初始种子集的要求不高、局部收敛快以及鲁棒性较强；该变异模型在对大型软件程序进行模糊测试时能更高效选中优秀种子进行变异，提升模糊测试效率；

[0039] （2）本发明在构建种子变异选择模型时以种子的路径能量（人工鱼群算法中的适应度）为选择依据时，种子队列在整个模糊测试的过程中不间断的进行迭代更新，结合种子的多维度信息动态计算种子的能量参数，消除因为考虑的维度不够造成评价失衡，强化了模糊测试过程中新路径发现能力，以突破程序各项指令条件约束，抵达程序嵌套的深处；

[0040] （3）本发明能够优先发现低频路径下的程序异常，扩展了路径执行深度，并综合考虑执行的时效，提高模糊测试效率；

[0041] （4）本发明在种子变异模型中设定了觅食型变异、群聚型变异、追尾型变异、跳跃型变异四个变异方式，以平衡测试效果和执行时间，并且能提高种子间的差异化，支撑测试持续运行能力。

附图说明

[0042] 图1为本发明所述的一种基于人工鱼群算法的软件漏洞检测方法的框架示意图；

[0043] 图2为本发明实施例1所展示的一种基于人工鱼群算法的软件漏洞检测方法的流程图。

具体实施方式

[0044] 下面结合实施例及附图，对本发明作进一步的详细说明，但本发明的实施方式不限于此。

[0045] 实施例1

[0046] 如图1至图2所示，本发明提出一种基于人工鱼群算法的软件漏洞检测方法，应用于软件漏洞检测技术领域，其中种子变异模型采用人工鱼群算法，实现对种子的觅食型变异、群聚型变异、追尾型变异、跳跃型变异；引入路径能量参数作为人工鱼群中的适应度值，基于队列中种子的总数、种子的存储空间占用大小、种子执行时间、种子的代码路径覆盖率、低频路径占比、路径深度、路径分支数、种子被评估次数等状态值引导能量参数的设定。种子文件覆盖低频路径时，给予该种子文件的能量参数高权值，以探索更多的程序路径分支。本方案可以有效提升种子文件在模糊测试过程中的路径深度，覆盖更多代码块，获得更好的漏洞检测效果。

[0047] 本发明涉及的技术术语解释如下：

[0048] 软件漏洞：

[0049] 软件漏洞指的是计算机系统或软件在安全方面的缺陷，使得系统或其应用数据的保密性、完整性、可用性、访问控制等面临威胁。这些在程序运行过程中的缺陷或不足会在一定条件下被激发，引起程序处理逻辑的失控。

[0050] 模糊测试：

[0051] 模糊测试（fuzz testing, fuzzing）是一种自动化的软件隐藏漏洞测试技术。其核心思想是将变异生成的随机种子文件数据输入到被测软件程序中，并观察程序异常输出，如崩溃，断言（assertion）失败，以发现可能的程序缺陷或错误，比如内存泄漏。模糊测试时常用于挖掘计算机系统或软件的安全漏洞。

[0052] 程序路径：

[0053] 软件程序载入种子文件后，依据转换成机器指令的执行逻辑运行，执行后会得到唯一的指令序列，称之为程序路径。

[0054] 人工鱼群算法：

[0055] 水域中的鱼类需要通过不断觅食来维持自身的生存发展，研究表明，鱼类在寻觅食物的过程中会聚集在食物丰富的水域。而人工鱼群算法就是利用鱼类的这类特性来实现最优解，通过构造人工鱼来模仿鱼的基本动作如聚集、觅食、追尾等，实现局部到全局的寻优。

[0056] 本发明针对现有模糊测试技术存在生成的种子文件冗余度高、最优种子选择方法参考的维度少、对探索到的低频路径不够重视等问题，提出一种基于人工鱼群算法的软件漏洞检测方法，以期提升种子文件在模糊测试过程中的路径深度，覆盖更多代码块，获得更好的漏洞挖掘效果。本方法采用人工鱼群算法来构建种子队列的变异模型，通过种子文件的状态参数计算出种子的路径能量参数（人工鱼群算法中的适应度），基于路径能量确定单个种子最优状态和种子队列最优状态，以便挑选出待变异的最优种子。

[0057] 本发明中针对软件模糊测试的人工鱼群种子变异方法主要包含以下步骤：

[0058] （1）获取原始种子数据集，利用剪枝工具剔除掉过大的文件和重复文件。

[0059] （2）生成种子队列，并依次输入软件程序，利用代码插桩跟踪程序运行状态，记录路径覆盖范围、路径深度、分支路径数等指标。

[0060] （3）利用人工鱼群算法构建种子变异模型，获取最优种子。具体流程如图2所示，实现如下：

[0061] 1）首先获取基本的状态信息，比如队列中种子的总数Num、种子的存储空间占用大小Size、种子执行时间TimeExc、种子的代码路径覆盖率FwRate、低频路径占比LowRate、路径深度Depth、路径分支数Branch、种子被评估次数SelectNum、种子聚集度因子Ω和种子程序执行耗时的阈值Time。

[0062] 2）因为路径能量参数越高代表种子效果越好，所以可以用路径能量值Power作为适应度值。计算每个种子适应度的值，获取全局最优解种子的状态。

[0063] ；

[0064] 其中，

[0065] TimeAssess=种子程序执行耗时/所有种子的平均耗时；

[0066] SizeAssess=种子的存储空间占用大小/所有种子的平均大小。

[0067] 3）对每个种子开展评估，根据评估结果确定种子变异方式，包括觅食型变异、群聚型变异、追尾型变异、跳跃型变异。

[0068] A、觅食型变异

[0069] 将全局最优解的种子设为Xmax，当前种子的状态为i，在其队列位置附近随机选中种子Xj，在求解路径能量参数最大值的过程中，Poweri

[0070] 一个种子的位置增加量单位=(0,1)之间的随机值*种子突变字节数*（Xj种子的状态矢量+最优解种子Xmax的状态矢量‑Xi种子的状态矢量）/种子大小差值。

[0071] 如果不满足觅食型变异条件，则需再次随机进行种子选择，评估其是否符合变异条件；如果在评估Select_num次后仍旧不符合条件，则随机选择字节进行变异。

[0072] B、群聚型变异

[0073] 将全局最优解的种子设为Xmax，当前种子的状态为i，参照当前种子代码路径覆盖率数值附近的伙伴种子数目n和中心位置Xz，假如中心的程序适应度和中心种子数的比率相比于聚集度因子Ω和当前种子程序适应度的乘积更大，说明伙伴种子的中心可触发不少的程序崩溃，并且伙伴种子间的聚集度不高，则可以向Xz和Xmax的矢量和方向进行变异。

[0074] C、追尾型变异

[0075] 将全局最优解的种子设为Xmax，当前种子的状态为Xi，参照当前种子代码路径覆盖率数值附近有最大Powerj的伙伴Xj，假如Xj程序适应度和附近伙伴种子数的比率相比于聚集度因子Ω和当前种子程序适应度的乘积更大，说明伙伴种子Xj可触发不少的程序崩溃，并且附近种子间的聚集度不高，则可以向Xj和Xmax的矢量和方向进行变异。

[0076] D、跳跃型变异

[0077] 选中种子队列中低频路径占比高、路径深度大、触发新路径的种子，随机设定被选种子的变异参数。

[0078] 某被选种子的变异后状态=目前状态+(0,1)随机值*设定的参数*被选种子的代码路径覆盖率。

[0079] 采用随机参数设定，主要是为了让某些低频路径覆盖度高或者触发新路径的种子跃过目前局部最优条件。

[0080] 4）执行种子变异后，及时将变异后种子添加到队列。

[0081] 5）更新种子队列的全局状态信息，特别是最优种子状态。

[0082] （4）将最优种子输入程序运行，程序中的状态调度模块确定当前模糊测试的运行状态，程序异常（例如程序崩溃）则从种子池中选择距离最短，执行次数少且发现路径多的种子，然后按照种子的距离确定该种子的能量，距离近的种子分配比较多的能量；接着对被选择的种子进行适应性变异，对距离小的种子主要采用细粒度变异，防止其生成的测试用例的执行路径偏离目标代码区域，记录运行状态。此阶段通过模糊测试，对获得的软件漏洞崩溃测试用例进行分析，获得可疑漏洞的位置信息和发生原因，找到与可疑漏洞匹配的崩溃。采用源码行级别的匹配，匹配崩溃发生的行与可疑漏洞行，如果一致就说明该崩溃用例能够触发该可疑漏洞，表示匹配成功，将该崩溃用例作为触发可疑漏洞的输入，获得一份漏洞验证报告，包括可疑漏洞位置、触发该漏洞的输入、崩溃发生原因。

[0083] （5）将最优种子输入程序运行，程序中的状态调度模块确定当前模糊测试的运行状态，程序正常则从种子池中选择执行速度快，执行路径长的种子。然后按照种子的距离确定该种子的能量，能量高的种子拥有更多的变异次数，距离远的种子分配比较少的能量；接着对被选择的种子进行适应性变异，距离大的种子主要采用粗粒度变异。然后计算变异得到的新测试用例的距离，并且将该测试用例作为新的种子加入到种子池中，在迭代过程中不断获取距离更小的种子，最终会得到执行路径到达或者经过可疑漏洞位置的种子，并且在可疑漏洞位置附近发现崩溃用例，更新种子的全局状态，跳转执行步骤（2），以上过程循环往复。

[0084] 本发明采用人工鱼群算法来构建种子队列的变异模型，通过种子文件的状态参数计算出种子的路径能量参数（人工鱼群算法中的适应度），基于路径能量确定单个种子最优状态和种子队列最优状态，以便挑选出待变异的最优种子。在进行待变异种子挑选过程时，需要考虑种子的多类状态信息，利用人工鱼群算法能把种子状态信息以较小的运算开销作用于待变异种子挑选，另外，对初始种子集的要求不高、局部收敛快以及鲁棒性较强。该变异模型在对大型软件程序进行模糊测试时能更高效选中优秀种子进行变异，提升模糊测试效率。

[0085] 本发明在构建种子变异选择模型时以种子的路径能量（人工鱼群算法中的适应度）为选择依据时，种子队列在整个模糊测试的过程中不间断的进行迭代更新，结合种子的多维度信息动态计算种子的能量参数，消除因为考虑的维度不够造成评价失衡，强化了模糊测试过程中新路径发现能力，以突破程序各项指令条件约束，抵达程序嵌套的深处。

[0086] 本发明在确定如种子的路径能量时获取了存储空间占用大小Size、种子执行时间TimeExc、种子的代码路径覆盖率FwRate、低频路径占比LowRate、路径深度Depth、种子被评估次数SelectNum等种子基本状态信息，具体函数为：

[0087] ；

[0088] 基于上述能量计算函数，能够优先发现低频路径下的程序异常，扩展了路径执行深度，并综合考虑执行的时效，提高模糊测试效率。

[0089] 一种基于人工鱼群算法的模糊测试种子变异系统，用于实现所述的一种基于人工鱼群算法的软件漏洞检测方法，包括依次相连的以下模块：

[0090] 原始种子数据集获取模块：用以，获取原始种子数据集；

[0091] 生成种子队列模块：用以，利用原始种子数据集生成种子队列，并将种子队列依次输入软件程序，利用代码插桩跟踪程序运行状态，记录路径覆盖范围指标、路径深度指标、分支路径数指标；

[0092] 最优种子获取模块：用以，利用人工鱼群算法构建种子变异模型，获取最优种子；

[0093] 程序运行模块：用以，将最优种子输入程序运行，观察最优种子程序运行状态；

[0094] 异常判断模块：用以，判断程序是否异常；若是，则记录运行状态；若否，则更新种子的全局状态，循环生产种子队列；

[0095] 异常判断模块还与生成种子队列模块相连。

[0096] 本发明在种子变异模型中设定了觅食型变异、群聚型变异、追尾型变异、跳跃型变异四个变异方式，以平衡测试效果和执行时间，并且能提高种子间的差异化，支撑测试持续运行能力。

[0097] 如上所述，可较好地实现本发明。

[0098] 本说明书中所有实施例公开的所有特征，或隐含公开的所有方法或过程中的步骤，除了互相排斥的特征和/或步骤以外，均可以以任何方式组合和/或扩展、替换。

[0099] 以上所述，仅是本发明的较佳实施例而已，并非对本发明作任何形式上的限制，依据本发明的技术实质，在本发明的精神和原则之内，对以上实施例所作的任何简单的修改、等同替换与改进等，均仍属于本发明技术方案的保护范围之内。