20199318 2019-2020-2 《网络攻防实践》综合实践
1.实验背景
本次实践的目的是对漏洞挖掘软件SlowFuzz开展实验，探究其性能的好坏，并对实验结果进行分析。
1.1 Fuzzing
Fuzzing是一种通过向目标系统提供非预期的输入并监视异常结果来发现软件漏洞的方法。
1.2 Fuzzing的作用
（1）Fuzzing技术首先是一种自动化技术，即软件自动执行相对随机的测试用例。
（2）Fuzzing技术本质是依赖随机函数生成随机测试用例，随机性意味着不重复、不可预测，可能有意想不到的输入和结果。
（3）根据概率论里面的“大数定律”，只要我们重复的次数够多、随机性够强，那些概率极低的偶然事件就必然会出现。Fuzzing技术就是大数定律的典范应用，足够多的测试用例和随机性，就可以让那些隐藏的很深很难出现的Bug成为必然现象。
1.3算法复杂性漏洞
当应用程序的最坏时间/空间复杂性显著高于特定用户控制输入的相应平均情况时，会出现算法复杂性漏洞。当满足这些条件时，攻击者可以通过提供触发最坏情况行为的输入，对易受攻击的应用程序发起拒绝服务攻击
2.SlowFuzz介绍
SlowFuzz，是一个独立于域的框架，用于自动查找算法复杂性漏洞。
2.1测试用例
SlowFuzz的测试用例是基于变异生成的，根据已知数据样本通过变异的方法生成新的测试用例。
2.2变异操作
变异策略决定了应用哪种变异操作以及在输入中设置哪些字节进行修改以生成新的变异输入。SlowFuzz支持以下的变异操作：
（1）从输入中添加/删除新的/现有的字节；
（2）随机修改输入中的位/字节；
（3）随机更改输入字节子集的顺序；
（4）随机更改其值在数字（即0x30-0x39）的ASCII码范围内的字节；
（5）仅使用用户提供的字典中的字符或字符串，对字节进行变异。
2.3 变异策略
SlowFuzz引入了几种新的变异策略，专门用于识别显示程序最坏情况复杂性的输入
（1）Random Mutations:随机变异是SlowFuzz支持的最简单的变异策略。在这种变异策略下，随机选择上述变异操作之一并应用于输入，只要它不违反给定测试情况的其他约束，例如超过审计员指定的最大输入长度。这种策略类似于流行的进化模糊算法，如AFL和lib-Fuzzer用于发现崩溃或内存安全问题。
（2）Mutation priority：在此策略下，变异操作是基于其在先前执行期间成功地产生Slow unit的概率ϵ来选择的。作者给每一种变异操作分配一个分数，表示变异成功增加指令数的概率。然后以概率ϵ在所有变异操作中选择得分最高的变异操作。以（1-ϵ）概率随机选取其它变异操作。
（3）Offset priority：该策略在每一步中随机选择要应用的变异操作，但要变异的偏移量是基于在增加执行的指令数时成功的先前历史来选择的。变异偏移量是基于先前执行的结果以概率ϵ和随机以概率（1-ϵ）来选择的。在第一种情况下，我们根据以前的执行选择最有希望的偏移量（每个偏移量的分数范围为0到1，表示偏移量的变异导致指令数量增加的次数百分比）。
（4）Hybrid：该策略是上述变异和偏移优先级的组合。在每一次变异中，以概率ϵ选择得分最高的偏移量和操作。然后以1-ϵ的概率随机选择其它的变异操作和偏移量。
3.实验与评估
主要从以下两个方面对SlowFuzz进行评估：
（1）SlowFuzz是否能够生成与给定算法实现的理论最坏情况复杂度相匹配的输入？
（2）SlowFuzz是否能够有效地找到导致实际应用程序性能下降的输入？
3.1实验设计
（1）将SlowFuzz应用于不同的排序算法；
（2）将SlowFuzz应用于易受复杂性攻击的PCRE正则表达库；
（3）将SlowFuzz应用于易受复杂性攻击的PHP 的默认哈希表实现；
（4）将SlowFuzz应用于bzip2程序。
3.2具体实验
3.2.1排序实验
在简单的快速排序和插入排序上运行SlowFuzz100万代，对64字节大小的文件进行排序。最终的实验结果如下图所示。
从上图可以看出：SlowFuzz生成的快速排序和插入排序的输入，分别达到理论最坏情况的83.74%和84.97%。
3.2.2 正则表达式实验
观察SlowFuzz是否能产生具有超线性和指数匹配时间的正则表达式。进行100次实验，每次实验都让SlowFuzz执行100万代。最终的实验结果如下图所示。
在上述100次实验中，SlowwFuzz总共生成33343个正则表达式，其中27142个被拒绝为无效，而6201个是导致减速的有效正则表达式。在有效的正则表达式中，765个是超线性的，78个是指数的。本实验证明，SlowFuzz在不知道正则表达式匹配语义的情况下，成功地生成了需要超线性和指数匹配时间的正则表达式。
3.2.3 哈希表实验
哈希表是各种软件中的一种核心数据结构。哈希表查找和插入操作的性能显著影响整体应用性能。PHPv5.x利用DJBX33A散列函数使用字符串键进行散列。本次实验我们利用SlowFuzz生成输入，并观察该输入采用DJBX33A散列时发生碰撞的次数。并且我们已知理论最坏情况下的碰撞次数为64。实验结果如下图所示。
SlowFuzz在不知道哈希函数的任何细节的情况下，SlowFuzz的进化引擎在大约40小时的模糊处理后，使用单个CPU达到了理论最坏情况的31.25%。
3.2.4 bzip解压缩实验
上图描述了bzip2二进制解压缩SlowFuzz生成的每个输入所需的时间。我们注意到，在Fuzzing的第一个小时，SlowFuzz产生的输入在bzip2的解压过程中不会表现出明显的减速。特别是，SlowFuzz语料库在Fuzzing第一小时的每一个输入中都在大约0.0006秒内被解压。然而，随着时间的增加我们观察到SlowFuzz成功地实现了解压时间达到0.18s到0.21s。达到了300倍的减速。
4.结论
通过本此实验中，我们可以看到fuzzing中常用的进化搜索技术可以用来发现算法复杂性漏洞。类似的策略应该适用于发现其他类型的DOS攻击，如电池耗尽、内存或硬盘归档等。设计适合度函数和变异方案来检测这些漏洞一直都是一个热门的研究问题。除了进化技术，使用其他机制，如深度学习或蒙特卡罗搜索技术，也可以适用于寻找最坏情况下资源使用的输入。