遗传算法初窥

0x00:

读Fuzzing相关的paper的时候遇到了关于遗传算法的问题，其实AFL晒样本也是用了遗传算法，个人的话一直没去探究，正好读paper遇到了，就搜了一下，找到了一篇好文 getting-started-genetic-algorithms-python-tutorial，看完之后一下子明了，并且大呼过瘾 (好文章啊!)

0x01 : 达尔文进化论

达尔文认为，生物之间存在着生存争斗，适应者生存下来，不适者则被淘汰，这就是自然的选择。生物正是通过遗传、变异和自然选择，从低级到高级，从简单到复杂，种类由少到多地进化着、发展着。

0x02 : 遗传算法简述

这个算法的核心理念很简单：如果一个种群想持续发展下去，就必须不断的提高自身，去适应环境，在使用过程中会个体会产生变异，适应环境的变异会保留下来，遗传给后代，这么一代一代的筛选下来，留下来的都是最适应环境的个体。

我们拿Fuzz举例，每一个样本进去所触发的路径、执行时间都有差异，那么如何去筛选出有效的样本，从而从这些样本再次迭代出新一代样本，从而让我们的Fuzz更加有效呢？

这时候我们需要一个评分规则（类比环境适应能力），评分越高，那么适应能力就越好，在这次样本变异中变异的部分（特性）会被保留下来，遗传给下一代。

参考AFL，它使用了路径等信息计算一个评分，评分高的样本保留（触发路径多），那么从这些样本中迭代，就容易产生更“优秀”的样本文件。

下图遗传算法的简单描述:

0x03 : 举个栗子

例子来自getting-started-genetic-algorithms-python-tutorial

1. demo简述

这里创建一个已知长度的密码破解程序 -。- （这不就是暴力破解吗，是的没错，但是思维方式要换一换啦）

我们针对没错输入的字符串（个体）进行评估，得到一个评分（适应环境性），这个评分指示着和正确密码的接近程度。算法如下：

fitness score = (number of char correct) / (total number of char)

随后对输入的串进行变异（进化，进化，进化…），然后对于新一代的群体，进行评分，挑选合适的个体作为第二代，然后从第二代中迭代产生新的个体。

产生下一代的方式也很简单，比如我们有两个个体叫做Tom和Jerry，他们的后代名字的字母就从两者名字字母中取就好了。

经历上述的过程，一代一代的进化，最终一定会得到正确的密码。

2. 一点问题

但是问题来了！这也是今天我在看论文时发现的一个问题-。-

Bloating: 
Bloating [16] is a phenomenon that adversely affects input generation in evolutionary computing. 
There are two types of bloating: structural and functional bloating.

主要分为两类：Structural Bloating和Functional Bloating。

第一种主要是经过多代的迭代后，经过xx代，个体的平均规模不受控制的增长从而导致代码效率下降，后续的增长也无异于提高适应度（适应度，就是例子中的fitness）。

第二种是指在进化过程中，如果只挑选好的样本（高评分），那么你得到的样本会快速收敛在一个范围内，也就是说，你的样本的特征就趋于一个方向。对于我们这个密码破解程序，当然ok啦，但是对于Fuzz的话显然是不行的，我们需要多种多样的样本而不是趋近于某一种类型的样本。

3. 代码

原文作者的代码在这里：
getting-started-genetic-algorithms-python-tutorial_source_code

运行结果：

$ python3 passwordTuto.py
solution: "banana" de fitness: 100.0
18.69589400291443

0x04 : 一点个人看法

我觉得这个算法对于漏洞挖掘，无疑是增强型buff，通过合理的使用，能够有效的提升样本质量，从而提高fuzz的效率。但是文中提到的Bloating的问题，无疑也是需要去考虑然后加以干预的。

0x05 : 参考及引用

1. getting-started-genetic-algorithms-python-tutorial
2. getting-started-genetic-algorithms-python-tutorial_source_code
3. IFuzzer: An Evolutionary Interpreter Fuzzer using Genetic Programming