AFL 遗传算法部分

遗传算法介绍

参考：https://www.zhihu.com/question/23293449

介绍

遗传算法(Genetic Algorithm)遵循『适者生存』、『优胜劣汰』的原则，是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。

遗传算法模拟一个人工种群的进化过程，通过选择(Selection)、交叉(Crossover)以及变异(Mutation)等机制，在每次迭代中都保留一组候选个体，重复此过程，种群经过若干代进化后，理想情况下其适应度达到近似最优的状态。

自从遗传算法被提出以来，其得到了广泛的应用，特别是在函数优化、生产调度、模式识别、神经网络、自适应控制等领域，遗传算法发挥了很大的作用，提高了一些问题求解的效率。。

遗传算法组成

• 编码 -> 创造染色体
• 个体 -> 种群
• 适应度函数
• 遗传算子
• 选择
• 交叉
• 变异
• 运行参数
• 是否选择精英操作
• 种群大小
• 染色体长度
• 最大迭代次数
• 交叉概率
• 变异概率

  编码与解码

  实现遗传算法的第一步就是明确对求解问题的编码和解码方式。

对于函数优化问题，一般有两种编码方式，各具优缺点

实数编码：直接用实数表示基因，容易理解且不需要解码过程，但容易过早收敛，从而陷入局部最优

二进制编码：稳定性高，种群多样性大，但需要的存储空间大，需要解码且难以理解

个体与种群

『染色体』表达了某种特征，这种特征的载体，称为『个体』。

一个个体里有一条染色体。许多这样的个体组成了一个种群，其含义是一个点集。

适应度函数

遗传算法中，一个个体(解)的好坏用适应度函数值来评价，在本问题中，f(x)就是适应度函数。适应度函数值越大，解的质量越高。

适应度函数是遗传算法进化的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。

遗传算子

我们希望有这样一个种群，它所包含的个体所对应的函数值都很接近于f(x)在[0,9]上的最大值，但是这个种群一开始可能不那么优秀，因为个体的染色体串是随机生成的。如何让种群变得优秀呢？不断的进化。

每一次进化都尽可能保留种群中的优秀个体，淘汰掉不理想的个体，并且在优秀个体之间进行染色体交叉，有些个体还可能出现变异。

种群的每一次进化，都会产生一个最优个体。种群所有世代的最优个体，可能就是函数f(x)最大值对应的定义域中的点。如果种群无休止地进化，那总能找到最好的解。但实际上，我们的时间有限，通常在得到一个看上去不错的解时，便终止了进化。

对于给定的种群，如何赋予它进化的能力呢？(选择、交叉和变异)

然而在AFL中呢？

首先使用初始测试数据或随机值初始化遗传算法中的种群,种群中的每个个体对应一个测试数据。然后跟踪被测程序处理这些测试数据的过程并记录执行路径信息，同时监控程序的执行状态,提取造成程序崩溃(Crash)的测试数据.接下来使用执行路径信息计算每个个体的适应度.最后通过对个体进行选择、交叉和变异生成新的测试数据并开始新一轮的测试。

背景

对输入数据格式未知的二进制程序进行模糊测试时，主要使用基于变异的测试数据生成方法。使用随机变异并不能取得很好的测试效果,近些年来,研究人员开始使用符号执行、污点分析、进化算法等方法来辅助生成测试数据的过程以此来克服随机变异的缺陷。

基于符号执行的方法将测试数据作为符号值处理。它们在程序处理这些符号值的过程中搜集路径上的约束信息，然后通过约束求解生成新的测试数据用于测试不同的执行路径.理论上,使用符号执行能够达到100%的代码覆盖率，然而随着程序复杂程度的增加,路径爆炸、复杂约束求解等问题严重限制符号执行的应用范围。符号执行并不适用于复杂程序。

基于污点分析的方法利用动态污点分析技术将软件的输入数据标记为污染源,记录污点的传播过程并提取关键污点信息,用于指导新的测试用例生成。整个测试数据生成过程主要关注污点所在的一些关键执行路径,对其他路径的测试较少。基于进化算法的方法将测试数据转换为进化算法能够处理的格式,通过进化算法的引导生成新的测试数据，其中应用最广泛的是遗传算法.目前研究人员在使用遗传算法指导测试数据的生成过程中需要预定义一条或多条执行路径,最终生成符合预设的执行路径的测试数据,并不能够对其他路径进行测试。

AFL 代码插桩理解（AFL+QEMU）

那机器会怎么做才能让2留下来提高突变达到crash的几率？

QEMU增强插桩

AFL+符号执行

更详细内容代码插桩的理解参考资料(简单易懂)：2016_SH_Li_Kang_The_Hype_and_Reality_of_AI_in_Vulnerability_Discovery

• AFL+QEMU(增强代码插桩，而AFL的输入生成是一个基于插桩代码导向的遗传算法)上面参考资料中这部分写的比较详细
• AFL+符号执行

正题

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

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

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

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

———————–分割线———————–

基于遗传算法的二进制程序模糊测试方法将测试数据转化为遗传算法中种群的个体，使用个体在进化过程中的改变产生新的测试数据。

以下为节选2016_NDSS_Driller论文翻译部分

A.Fuzzer特征
现代Fuzzer实现许多特征以更好地识别崩溃输入。在这一节中，我们将列出并描述最重要的AFL特征，并提到它们是如何由Driller使用的。
遗传模糊测试：
AFL通过遗传算法生成输入，根据遗传螺旋规则（转录，插入等）对输入进行变异并通过适应度函数对它们进行排序。对于AFL，适应度函数基于唯一代码覆盖率——即，触发不同于其他输入触发的路径的执行路径。《一个遗传算法在AFL中应用的概述》
状态转移跟踪：
AFL跟踪从其输入中看到的控制流转换的并集，作为源和目标基本块的元组。输入将基于它们对新的控制流转换的发现取得遗传算法中的“繁殖”优先权，这意味着能让应用以不同方式执行的输入在未来输入的生成中获得优先权。《适应度函数的计算部分》
循环“bucketization”：
对模糊引擎和导向性执行引擎来说，处理循环都是一个复杂的问题。为了帮助减小循环的路径空间大小，使用以下的启发式算法。当AFL检测到路径包含循环的迭代时，触发二次计算以确定该路径是否适合繁殖。AFL确定执行的循环迭代次数，并将其与先前导致路径进入相同循环的输入作比较。这些路径都被放入标号为它们循环迭代计数（即，1，2，4，8）的对数对应的“buckets”中。每一个“bucket”中的路径被认为是遗传算法中的育种。这样，每个循环必须只考虑log（n）条路径，而不是n条路径的天真方法。
去随机化：
程序随机化干扰了遗传fuzzer对输入的评估——在给定的随机种子下产生有趣路径的输入在另一个种子下可能不会这样做。我们预先将AFL的QEMU后端设置为一个特定的随机种子，以确保一致的执行。稍后，当发现崩溃输入时，我们使用导向性执行引擎来恢复其他任何依赖于随机性的“挑战-响应”行为或漏洞。例如，一个二进制程序中的“挑战者推送”过程将随机数据回送给用户，并期望用户以相同的数据回应它。如果不去除随机化，模糊测试组件可能每次都会失败，并且探索非常少的路径。如果随机值是常数，则程序每次都接受相同的输入，让fuzzer（或者导向性执行组件）自由地找到这个值并随后进一步探索。在发现程序崩溃点后，可以通过符号方式对随机值进行建模，如V-D4节所述，并且可以相应地修补崩溃输入。
这些特征使得AFL能够快速发现应用程序中一条特别的路径，在一个给定分区内路径搜索是首要任务。然而，模糊测试地局限性是众所周知的。

精简：
遗传模糊测试：根据遗传规则，对输入进行变异，通过适应度排序（适应度函数基于唯一代码覆盖率——触发不同于其他输入触发的执行路径）
状态转移跟踪：使能够给应用提供状态转移的输入获得优先权。
循环“bucketiztion”桶化：减小循环路径空间（从n条中抽取log（n）条放入桶中）
去随机化：避免使用模糊搜索中的随机功能？

种群初始化

在遗传算法中，种群由若干数量的个体组成，每个个体可以抽象表示为染色体，设染色体的长度为D，那 么 种 群 中 的 第i 个 个 体 可 以 表 示 为 Xi =(xi,1,xi,1,xi,1,…,xi,D ) 。种群初始化的过程就是为Xi 中每一个基因xi,d赋值。本文中，每个xi,d代表一个字节，长度 D 即为测试数据的字节数。存在初始测试数据时,使用初始测试数据的每一个个字节分别为每一个xi,d赋值。在其他情况下，使用随机赋值的方式初始化整个种群。初始化完成之后，每个个体的染色体数据即为一条测试数据的内容，可直接将其转换为下一步所需的测试数据。

跟踪执行被测程序

跟踪执行被测程序需要进行两方面的工作： 1)监控当前的测试数据是否会造成被测程序崩溃; 2)记录程序执行路径.程序在崩溃时会发送一个错误 信号 (如 SIGILL、SIGSEGV、SIGABRT)，因 此通过接收程序发送的信号可以监控程序是否崩溃。 一个程序可以被划分为许多基本块，程序执行的过程就是不断重复执行一个基本块、跳转到另外一个基本块的过程。通过跟踪记录当前正在被执行的基本块可以得到程序执行路径。

每个基本 块只有一 个入口和一个出口，且仅会从入口处 开 始 执 行 并 从出 口 离 开，因此可以使用每个基本 块 的 入口地址表示一个基本块。一个简单程序中的几个基本块如图2所示.使用 QuickEmulator(QEMU)进行插桩能够获取程序执行过程中的基本块信息。用户模式下 QEMU 模拟执行程序的过程中将程序划分为基本块进行翻译和执行，通过在 QEMU 执行一个基本块之前插入一段输出当前正在执行的基本块的信息的代码，能够在 QEMU 模拟执行程序时得到程序执行过程对应的基本块序列。

将程序中每一个基本块b视为一个点,使用基本块的入口地址代表b,通过跟踪程序执行过程可获得一 个 基 本 块 的 序 列 (b1,b2,b3,…,bn ) .定义程序执行过程中 2 个连续基本块之间的跳转为e=(bk,bk+1 ) ,那么e就是以基本块为节点的程序控制 流图中的边(如图2所示).经过基本块到边的转换,程 序 的 执 行 路 径 可 以 表 示 成 边 的 序 列 Ee =(e1,e2,e3,…,en-1 ) .在序列Ee 中,某些边不可避免的将出现多次,即有可能存在x、y使序列中的ex 与ey 代表相同的边.合并这些相同的边将得到包含出现次数信息的边的集合 E’e= {e’1,e’2,e’3,…}.每条边出现的次数在不同的程序执行过程有可能是不同,根据出现次数的不同,将其分成8种不同的类 型:1、2、3、4~7、8~15、16~31、32~127、≥128.这8种类型能够在实际应用时使用一个字节的不同位进行表示,便于编程实现.经过分类后,将得到一个新的边的集合 E″e= {e″1,e″2,e″3,…}.使用上述过程处理种群中的每一个个体 Xi 对应的程序基本块序列,最终将得到程序的执行路径信息,即边的集合Ei={ei,1,ei,2,ei,3,…}.

适应度计算

测试数据生成过程中发现新的执行路径的测试数据有更重要的意义,而发现新的执行路径也就意味着发现新的边.定义整个模糊测试过程中所有曾经发现的边的集合为 Et= {et,1,et,2,et,3,…}.对于集合Et 中任意一条边et,i,假设最后一次发现这条 边的测试数据为 Xt,i,那么可以得到一个边与测试数据相对 应 的 集 合 Wt ={(et,1,Xt,1 ) ,(et,2,Xt,2 ) ,(et,3,Xt,3 ) ,…}.

个体Xi 的适应度f分为2个方面:发现的新的边的数量f1 和集合Wt 中与其相关的边的数量f2.使用函数f1 (Xi ) =card (Ei -Et ) 计算发现的新的边的数量;使用函数f2(Xi ) = ∑∈EiR (W (e) ,Xi ) 计算集合Wt 中与Xi 相关的边的数量,其中W (e) 为从集合Wt 中获取边e 对应的测试数据,R(x,y) 为一个二值函数,当x,y相同时函数返回1,其他情况下返回0.

当适应度计算时,首先计算每个个体的f1,然后更新集合Et 和 Wt,最后计算每个个体的f2.由于每轮测试完成后,均会更新用于计算适应度的2个集合,故对于上一轮中的个体,其适应度也将随之改变,且f1 将始终为0,而当本轮的个体的执行路径完全覆盖上一轮的某个个体的执行路径时,其f2也将为0.当2个个体进行适应度对比时,首先比较f1 的值,在无法区分的情况下比较f2 的值.

个体选择、交叉和变异

在程序中产生新的状态转换的突变测试用例被添加到输入队列中，并作为未来几轮fuzzing的起点。它们补充，但不能自动替换现有的发现。

与更贪婪的遗传算法相比，这种方法允许工具逐步探索底层数据格式的各种分离和可能相互不兼容的特性，如下图所示 ：

总的来讲，AFL维护了一个队列(queue)，每次从这个队列中取出一个文件，对其进行大量变异，并检查运行后是否会引起目标崩溃、发现新路径等结果。变异的主要类型如下：

• bitflip，按位翻转，1变为0，0变为1
• arithmetic，整数加/减算术运算
• interest，把一些特殊内容替换到原文件中
• dictionary，把自动生成或用户提供的token替换/插入到原文件中
• havoc，中文意思是“大破坏”，此阶段会对原文件进行大量变异，具体见下文
• splice，中文意思是“绞接”，此阶段会将两个文件拼接起来得到一个新的文件

其中，前四项bitflip, arithmetic, interest, dictionary是非dumb mode（-d）和主fuzzer（-M）会进行的操作，由于其变异方式没有随机性，所以也称为deterministic fuzzing；havoc和splice则存在随机性，是所有状况的fuzzer（是否dumb mode、主从fuzzer）都会执行的变异。 参考：https://blog.csdn.net/qq_32464719/article/details/80592902

Fuzz流程：

读取输入的初始testcase, 将其放入到queue中； 从queue中读取内容作为程序输入； 尝试在不影响流程的情况下精简输入； 对输入进行自动突变； 如果突变后的输入能够有新的状态转移，将修改后的输入放入queue中； 回到2。

参考

• https://gist.github.com/NicolleLouis/d4f88d5bd566298d4279bcb69934f51d
• https://blog.sicara.com/getting-started-genetic-algorithms-python-tutorial-81ffa1dd72f9
• http://muhe.live/2018/06/03/%E9%81%97%E4%BC%A0%E7%AE%97%E6%B3%95%E5%88%9D%E7%AA%A5/
• 用遗传算法进行变异，来实现最大覆盖
• https://www.jianshu.com/p/cc7a486e5adb
• https://gitlab.com/drmilk/docs/blob/master/Fuzz/Angora_%20Efficient%20Fuzzing%20by%20Principled%20Search.md