Fuzz Testing（模糊测试）

Fuzz Testing（模糊测试）是一种简单有效的黑盒测试技术，本文将在传统的Fuzz基础之上向你介绍一种结构化Fuzz思想， 并提出结构化Fuzz三步走方案将尝试把Fuzz做到极致。 希望本文可以使你重新看待Fuzz技术，并在实际测试项目中找到Fuzz的乐趣 。
传统Fuzz简介
简而言之，Fuzz就是：
用随机坏数据攻击一个程序，然后等着观察哪里遭到了破坏。
Fuzz的技巧在于，它是不符合逻辑的：自动模糊测试不去猜测哪个数据会导致破坏（就像人工测试员那样），而是将尽可能多的杂乱数据投入程序中
Fuzz的基本流程非常简单：
给定一个字符串模版，或者说给定一段二进制数据，按照一定的比例随机地改变其中的若干字节，从而生成一份新的数据，测试者再用这份Fuzz后的数据进行测试以发现bug。
这种Fuzz会有什么问题呢？
可以看到，这种传统的Fuzz流程只能对无结构的、线性的、一维的数据进行Fuzz，而有些时候这种裸露的二进制数据是对我们不可见的， 或者说在我们的自动化测试中使用的往往是上层可读的带有结构化的数据，比如Hash、Array或其他。
对于这样的情况，单纯的线性Fuzz技术就无从下手了。 为了能够完全说明这一点，我们来看个例子。
一个例子
某模块的查询接口是如下： （已做转义）

下面是自动化case的片段：

可以看到，case里面使用了Ruby中的Hash对象（类似于JavaScript里的JSON）来构造数据，这么做给我们测试带来了很大的便利，易用性很好。
当这个Hash数据经过编码之后得到的二进制数据（片断）如下：

很明显，这段数据一般人是很难读懂的，现在假设我想对这个模块进行Fuzz测试，那么我有两种选择。

两种选择
第一种选择
一种就是对这份二进制数据进行Fuzz然后发给被测模块，这么做对于纯结构体的接口来讲应该是有显著效果的，但是对于自解释的编解码方式来讲，结果可能会让人非常沮丧。
根据笔者的个人经验，这样的Fuzz有90%以上的可能性导致被测模块报同一个错误，那就是数据包解析异常然后这个包就被无情的丢弃了。
现在回过头来看看Fuzz的初衷，初衷是想测试模块内部的处理逻辑是否有bug，而结果是还没进入到内部就在外围被封杀了。
这是一件很郁闷的事情，当然如果我就是想测试编解码功能是不是够健壮那又另当别论。
第二种选择
另一种Fuzz的选择则是对上层使用的Hash对象进行Fuzz，然后用Fuzz之后的Hash对象进行编码，再把编码后的二进制数据发给被测模块。
这种Fuzz最大的好处就是既不会被模块的外围解析给封杀，又能够充分发挥Fuzz的作用，可以深入到程序内部。
二者的区别
我画了两个示意图来说明二者的区别：

图中右边的Fuzz形式就是本文所要重点介绍的结构化Fuzz思想，也可以叫做二维Fuzz思想。
虽然从图中看二者的差别并不算大，但实际上结构化Fuzz与传统的线性Fuzz比较起来会变得复杂很多，不仅仅是简单的升级版（这里暂且不谈）。
然而任何事情都需要从简单容易的做起，所以下面笔者会先介绍简单版的结构化Fuzz的实现原理及实际效果，然后再跟大家讨论完整的结构化Fuzz。
结构化Fuzz的简单实现
结构化Fuzz如何实现对一个Hash对象的Fuzz呢？
一种很简单的思路是这样的：
对Hash对象里的每一个元素进行Fuzz，
如果元素还是Hash，那么继续对子Hash进行Fuzz，
如果元素是String、Number，那么就可以进行线性Fuzz了。
这其实就是一种递归的思想，最终返回Fuzz后的Hash对象实际上就是所有的子孙元素中String、Number被Fuzz后的结果。
Fuzz之后的Hash在结构上没有任何变化，只不过某些元素的值发生了改变。 这样的Fuzz之后的数据再经过编码打包发送，就能够顺利的躲过程序外围检查并深入到程序内部。
结构化Fuzz三步走
在简单版的实现里面我们更多的是把一种理论变成了现实，现在我们停下来思考一下，结构化Fuzz相比传统线性Fuzz有哪些特点？
结构化Fuzz的特点
1、结构化的数据无法再用流的方式来进行Fuzz了，但是可以通过“递归遍历”+“流处理”相结合的方式来替代。
2、结构化的数据一般都是异构的，所有元素不要求是同一种类型，或者说看成同一种类型，其他如长度、容量等都没限制。
3、很重要的一点，如果说线性Fuzz是在一维空间里面Fuzz，那么结构化Fuzz就是在二维空间里面Fuzz ，不光是元素本身的值，它与旁边元素的值的关系，甚至排列的顺序等等都有可能成为新的Fuzz点，其变化复杂度是一个数量级的提升。
4、变化复杂度变大、遍历的加入、异构等等，可能意味着结构化Fuzz很难再像传统Fuzz那样在不断发散过程中有一个收敛过程，而且时间消耗会变得巨大，如何让结构化Fuzz更快更有效的进行？
结构化Fuzz的这些特点说明了我们需要尝试一些新的东西才能满足需求，传统Fuzz没有这么做是因为它根本不需要。
SPIKE的格式化Fuzz其实也是有着同样的出发点，不过其需要配置来指定不同字段字段的属性和特点，看起来比较笨拙一点。而结构化Fuzz可以做得更 纯洁更Fuzz一些。说到底还是Hash结构本身的异构特点和固定的编解码接口所带来的好处 。
基于这些思考，三步走其实是解决三大问题，走完这三步大概才算是真正完整的结构化Fuzz了吧~~~
第一步 解决单个元素的随机性和特殊值问题
这个问题的由来是这样的，Fuzz是全随机的，在Fuzz过程中用户无法进行干预。 当然这也是Fuzz的特点，因为Fuzz就是要出其不意，所以不能受正常思维的影响。
但是的确是有些时候，我们明确知道一些特殊值很可能会导致问题，并希望这些值也能被Fuzz到。 比如Number中可能有0、-1、65536、4294967296……，String中有空字符串、UTF8与GBk交界字符、各种转义字符、重复的 字符串……，同样Array可能有空数组，顺序颠倒的数组……，等等，甚至用户可以自己设定一批特殊值。
随机性与特殊值并不矛盾，是否使用特殊值同样也是随机的，也就是说我们只是把随机到特殊值的权值给调高了，这样既保留了Fuzz出其不意的特点又能兼顾测试者的意图。
普通Fuzz还有个问题就是它并不会改变数据的大小，也就是说，你给我100个字节，那么我fuzz之后仍然会返回给你100个字节，一个不多也一个不少。
这么做是有道理的，因为传统Fuzz经常处理的是二进制数据，为了保证它们的有效性在数据大小上不能有太多改变，否则很可能直接被程序外围封杀了。
但是对于结构化Fuzz来讲，数据的表现都是上层的对象，无论你怎么改变都会保证最终打包成一个有效的二进制数据，所以我们没必要遵循这个大小不变的传统，我们可以更加肆无忌惮的Fuzz。
第二步 解决多元素直接异常组合的问题
第一步我们解决了单一元素的Fuzz问题，但二维Fuzz并不只跟单一元素有关，如果结构体中的元素很多，就会带来一些新的问题。
假设一个Hash有100个子孙元素，我要验证其中每个元素为空的异常情况，如果我每次只改变一个元素的话，那么我要测试100次，如果我一次改变100个元素的话，那么整个Hash都变成一个空壳子了，肯定是无效的。
这个时候Pairwise的思想就可以派上用场了，经过paiwise之后原来100次的被压缩成了16次，如果是1000次那么会被压缩成22次。简而 言之，这第二步就是利用pairwise算法来解决多元素之间异常组合爆炸问题，进一步加快结构化Fuzz的速度。
第三步 解决快速收敛问题
解决快速收敛的问题，也即数据模版的局限性问题。 这个问题是这样的，很多时候对于一个模块进行的Fuzz测试，如果刚开始的几分钟没有发现bug，那么很可能后面很长一段时间内都很难发现bug了。
为什么会这样呢？ 大概有两个方面
一是我们提供的数据模版有局限性，毕竟只有一份数据模版啊，虽说举一能反三，但也有巧妇难为无米之炊啊，到最后可能翻来覆去的始终都是类似的数据了。
二是Fuzz的发散算法问题，二维Fuzz的特点使其很难按照一维Fuzz全随机的方式来进行，发散算法的好坏将直接关系到Fuzz的有效性和高效性。
解决第一个问题大概有两种思路：
一是使用多份模版 。
二是在Fuzz过程中开始收敛的时候，使用Fuzz之后的数据作为模版再次Fuzz，利用“小鸡生小鸡”的原理来扩大数据多样性 。
解决第二个问题就很困难了（很可能已经超出笔者的知识范围），目前的思路是：
A、机器学习算法应该会不错，不过Fuzz过程中如何取得正反馈是一个难点。
B、广度优先的发散算法，尽早发现更近的bug，同时避免走入一个死胡同，如下图

图中正中心是一份模版数据，向外一圈一圈的都是fuzz之后的数据，四个象限代表fuzz的四个方向，红色的点表示能发现bug的数据。 如果fuzz一开始就走入了右上角的那个方向，并且一直在错误的方向上向外发散没能收敛回来，那么肯定是个杯具了。
如果是广度优先发散算法，那么会先把最内圈扫一遍，再扫次内圈，这样逐层的向外扩展。 这样既能尽快的发现内圈的bug（假设内圈的bug应该是最多的），又能使fuzz一直都具备生命力，随着时间的推移最终会发现外圈的那个遥远的bug。
总结
有的时候我们为了敏捷为了效率会进行灰盒甚至全白盒测试，但Fuzz告诉我们，黑盒测试同样可以很高效很敏捷，更重要的是它使测试更有乐趣了。
Fuzz是一项简单的测试技术，但它却能揭示出程序中的重要 bug，我们有理由把Fuzz继续发扬光大，将Fuzz进行到底 。

本文转自网络由网络安全攻防研究室(www.91ri.org)信息安全小组收集整理。