AFL改进小试

Posted by rk700 on February 2, 2018

在阅读学习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。