遗传算法初窥

0x00:

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

0x01 : 达尔文进化论

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

0x02 : 遗传算法简述

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

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

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

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

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

GP

0x03 : 举个栗子

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

1. demo简述

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

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

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

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

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

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

2. 一点问题

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

1
2
3
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

运行结果:

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

result

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
文章目录
  1. 1. 0x00:
  2. 2. 0x01 : 达尔文进化论
  3. 3. 0x02 : 遗传算法简述
  4. 4. 0x03 : 举个栗子
    1. 4.1. 1. demo简述
    2. 4.2. 2. 一点问题
    3. 4.3. 3. 代码
  5. 5. 0x04 : 一点个人看法
  6. 6. 0x05 : 参考及引用
,