在阅读学习AFL源码的过程中，有一个变异阶段引起了我们的极大兴趣：havoc。AFL的做法，是将一系列变异随机组合到一起，因此这部分是不折不扣的“看天吃饭”。
然而，当我们搞清楚havoc的变异策略后，脑海中闪过的第一个想法就是：能不能减少一些“随机化”，尽量去变异那些“更重要”的字符，从而提高路径覆盖效率？于是，基于这一点，我们对AFL做了一些尝试改进，不过也踩了很多坑。
基本思路
在考虑具体实现之前，第一个问题，也是最重要的问题，就是我们的想法是不是正确的。很可惜，我们并没有从理论上证明，基于字符的“重要程度”有倾向地havoc，是可以提高路径覆盖率的。但是从直觉来讲，是讲的通的。
一般来说，文件可以分为“元数据”和“数据”两部分。例如，ELF文件中，program header, section header等属于“元数据”，而具体的指令就属于“数据”。文件解析工具会首先读取“元数据”，获取所需的flag, offset, length等，然后再根据这些信息，去读取和处理“数据”。于是，从我们的直觉和经验来讲，相比对“数据”的变异，变异“元数据”往往更容易引起新路径，从而也是性价比更高的方式。一个极端的例子就是，如果我们有一张PNG图片文件，那么即使把所有的RGB bytes全部变异掉，得到的也只是一张看上去完全不同的图片，从代码执行路径的角度来看并没有什么不同。于是，在havoc阶段，如果我们能提高“元数据”被变异的概率，那么新路径的发现概率，应该也会提高。
也许有读者会想，OK，那我就先选出所有的“元数据”，然后只对这些“元数据”进行变异，不就可以了吗？其实最开始我也是这么想的，但稍微仔细一思考，就会发现这种方式存在一个很严重的问题：还是以ELF文件为例，如果变异了“元数据”e_phoff，那么program header offset就会发生变化，如果运气不好，新指向的program header落入变异之前的“数据”区域，这部分bytes就会由“数据”变为“元数据”。对havoc而言，动辄几十乃至上百次变异组合，最终的“元数据”和“数据”，可能与起始时已经大相径庭了。
换句话说，随着对文件的不断变异，最初的“元数据”仍然是“元数据”的概率，也在逐渐减小。那么当这个概率降到一定程度时，最初的”元数据“信息已经不够准确，不再具有参考价值。此时，我们可以更新”元数据“信息，再指导之后的变异；我们最终使用的是另一种更省事的方法，即直接恢复到原始havoc的方式，进行无指导的随机选取。
如何判断”元数据“
现在，我们有了改进的基本思路。但是，如何判断一个文件中，哪些bytes是”元数据“，哪些bytes是”数据“，就是另一个关键问题了。我们当初设想了2种方式：基于变异引发新路径的概率，和基于AFL原有的effMap。
基于变异引发新路径的概率
这是我们首先想到的方式。具体来说，如果byte A是”元数据“，byte B是”数据“，那么变异byte A引发新执行路径的概率，就比变异byte B要高。通过贝叶斯公式可知，如果随机变异了一定次数后，变异某些bytes引发新路径的概率越高，那么这些bytes是”元数据“的概率就更大，这和我们的直觉也是相符的。
于是乎，在拿到一个文件之后，我们首先使用正常的havoc变异一段时间，并且对文件的每个byte记录两个数据：总共有多少次变异修改了这个byte，有多少次引发新路径的变异修改了这个byte。那么简单地用后者除以前者，就可以视为变异引发新路径的概率。接下来，我们按照概率从高到低进行排序，就可以得到最有可能是”元数据“的一批bytes。在之后的havoc变异中，我们就从这批bytes中依次选取byte进行变异。
在实现上还有一些细节的坑，这里就暂且不表了，因为这种方式的试验结果并不理想。。我们试验的环境是一个AFL master，开启IGNORE_FINDS，fuzz的目标是objdump -x。然而运行1天后，修改版AFL和原始AFL的新路径数量基本相同。当然，如果对这种方式有什么建议，也可以联系我们交流。
基于AFL原有的effMap
在上一种方式失败之后，我们暂时陷入了困境，一时间没有头绪。所以，我又回头开始读AFL的源码，试图找到一些启发。而看到AFL的effector map机制时，我突然觉得可以试试直接借用effMap来指导havoc变异。
按照effMap的原理，如果翻转一个byte之后，程序的执行路径发生了变化，那么这个byte很可能是属于”元数据“的。我们记录下这些bytes，作为“元数据”的近似，保存为这个文件的effBytes。在之后对该文件进行havoc变异时，首先从这些effBytes中随机选取进行变异。相比原始的havoc完全随机选择，这种情况下，“元数据”被变异的概率便提高了。
使用effMap指导havoc的另一个好处是，无需消耗大量计算资源，可以直接将deterministic阶段生成的effMap利用起来。相比之下，前一种通过概率选择的方式，还需要记录相关的次数、计算概率、排序，而这些额外的开销对于整体的fuzz效率还是有较大影响。
减小effBytes的范围
AFL原始的effBytes的判断方式，是检查翻转byte之后执行路径有没有发生变化。然而，在使用objdump -x对ELF文件试验时，我们发现几乎全部的bytes都是effBytes。那么这时上面的改进就没有什么意义了。
为此，我对ELF文件变异和objdump执行路径变异进行了简单的试验，发现许多”数据“bytes被翻转后，确实能够引起执行路径的变化。但是，这些”数据“bytes往往是一块块分布在文件中的，而每一块”数据“中的每个bytes被翻转后，执行路径往往是相同的。所以，我们就有了一个朴素的想法：如果翻转一个byte引起执行路径变化，而且翻转该byte与翻转其前一个byte的执行路径不同，此时才将其视为“有效”的。
这样处理之后，我们惊喜地发现，在同样的环境下，effBytes的占比，从开始的几乎100%，降到了约20%。当然，这样激进的选择方式，可能会遗漏一些属于“元数据”的bytes。读者可以试验类似的思路，例如：如果翻转某个byte的执行路径，与相邻的两个byte的执行路径不同，那么就将这个byte视为“有效”的。
试验结果与总结
测试环境与之前相同，我们使用的是一个master instance，开启IGNORE_FINDS，fuzz的目标是objdump -x。运行1天后，修改版AFL的新路径比原始AFL大致多8%。随后，我们又对readelf -aW进行了试验，其效果更为显著：运行1天后，修改版AFL的新路径比原始AFL大致多20%。由此可见，经过effMap指导的havoc变异，在新路径的发现效率上确实更高。
当然，我们的改进思路还有一些待完善的地方。第一，这种改进只对master有意义，因为slave没有deterministic阶段，也就没有effMap了；第二，如果目标运行在persistent mode，那么由于执行结果的稳定性小于100%，在effMap的生成时可能会产生错误，从而影响其准确性。不过，目前我的fuzz环境是1个master，1个slave，目标非persistent mode，因此这两个问题基本都没有影响。作为实际fuzz的结果，已经发现了objdump的两个CVE，CVE-2018-6323和CVE-2018-6543。