遗传算法在模糊测试领域的应用

1.遗传算法介绍

遗传算法最早是由美国的 John holland于20世纪70年代提出，该算法的特点是根据大自然中生物体进化规律通过淘汰不合格的进化，保留合格的样本后继续进化。整个过程模拟达尔文生物进化论的优胜劣汰原则，满足自然选择的遗传学机理，构建一个生物进化过程的计算模型，整个过程高度模拟了自然进化过程，寻找可以满足条件的优秀个体，寻找局部或者全局最优解的方法。该算法充分利用数学的方式并结合计算机工程化仿真模拟及计算，将复杂问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。在求解一些较为复杂的组合优化问题时，相对其他常规的计算方法,有着独特的优势。遗传算法目前已经可以应用到多个需要复杂计算的工程领域，例如：组合优化、信号处理、机器学习、控制工程和人工生命科学等领域，本文简单介绍遗传算法在模糊测试领域的一点应用。尝试解决模糊测试在海量变异样本中寻找最优解的过程。

2.模糊测试介绍

模糊测试（Fuzzing），是一种通过向目标测试设备系统或软件，输入非预期的测试数据，并通过监视器监视异常输出来发现设备、系统或者软件脆弱性的方法，模糊测试可以应用的领域很多，例如、通信协议、文件、软件等等，本文只针对通信协议进行介绍。

报文的模糊测试的测试样本生成主要有两种方式：

1、基于变异：基于变异的模糊测试方法是一种基于已知样本的前提下，通过改变、重组等方法，对已知样本的结构和内容进行变异，以得到新的模糊测试输入样本的方法。

2、基于生成：基于生成的模糊测试方法是一种从无到有的过程，此方法会根据给定的规约、模型或语法规范等条件下生成输入样本。

3.遗传算法如何应用于模糊测试

遗传算法应用于模糊测试是模糊测试中基于生成的方式进行的，遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的初始群体数据，在对通信协议进行变异前，需要准备一些初试的报文，作为遗传算法的初始数据。

3.1 遗传算法的流程：

(1)选择初始群体。

(2)设定适应度函数，模糊测试一般采用监视器进行反馈。

(3)变异点选择及变异规则适配。

(4)计算适应度，通过监视器捕捉是否可以导致异常。

(5)选择、交叉、变异。

(6)适应度捕获，选择出下一代有效个体。

(7)重复(4)(5)(6)寻找最优解。

在选择好初试群里和适变异交叉函数后，变异点的选择往往具有盲目性，是需要重点解决的问题。

3.2 变异点选择

通信协议的数据在不知道规约的情况下，可以暂时作为无类型数据进行处理，变异点的选择成为难点，因为随机选择变异点盲目性过高，导致适应度计算不收敛，所以需要通过一定手段进行变异点的确定。

3.2.1 信息熵的应用

在变异点选择上，通过信息熵的某些特性进行选择是一种适应性较强的方法。具体操作如下：

1、数据切片及纵向分组计算熵：通过纵向对齐的方式对报文的数据进行切片，然后计算多个切片的信息熵后，形成一个离散的信息熵曲线。

2、极值判定：在信息熵的极值点往往代表着此区域有局部或者全局的信息量最大或者最小的分布，选择这些点往往可以给变异提供更多的有效空间，如下图：

3.3 交叉及变异

选择好变异点后，可以通过变异函数输出变异值，再和初始群体的样本进行交叉，生成后代，作为测试样本发送给测试目标，如果测试目标产生的一些异常，说明找到了满足条件的后代，可以作为第一代有效后代样本进行特征保存，并作为输入，继续进行后续交叉和变异，产生更优的后代，以此迭代选择，寻找最优解。

3.4 相关性判定及应用

遗传算法的交叉和变异可以在某一个点上进行，也可以在多个点上进行，单点的交叉变异相对简单，但是效果一般，多点的交叉、变异会给计算带来指数级增长，为了解决这个问题，可以通过字段相关性进行约束，降低遗传算法在多字段应用的复杂度及计算量，前文介绍到变异点的选择可以通过信息熵极值进行，同样，字段相关性判定可以通过多组信息熵的矩阵进行，在对比多组信息熵后，可以根据熵的相关性来判定报文字段的相关性，如下图所示：

4.案例分享

协议模糊测试的适应度判定通过协议监视器来反馈，一个后代是否可以触发异常，可以通过监视器的反馈直接获取，例如下图是在测试某国际知名品牌的PLC的时候，产生的监视器异常。

通过上图可以看到，第一代有效后代的样本，可以影响服务端口的稳定性，端口出现了反复的开启和关闭。

经过反复的交叉、变异后，得到的最终后代报文，使得设备的服务端口完全关闭，如下图：

综上，通过遗传算法寻找最优解的方式，在模糊测试领域具有一定的效果。

原文始发于微信公众号（威努特工控安全）：遗传算法在模糊测试领域的应用