精读:CollAFL: Path Sensitive Fuzzing

0x01 Why

目前流行的fuzzing(如AFL)通常使用较为简单的coverage information,这种覆盖的不准确和不完整给fuzzing带来了严重的局限性。首先,它会导致路径冲突,从而影响fuzzing挖掘出导致新崩溃的潜在路径。更重要的是,它也会影响fuzzing的最优决策。此外,学术界的大部分研究的是Coverage-guided fuzzing,很少有目光真正的投在Coverage上,所以CollAFL做了这一块的内容。

0x02 What

对AFL中的coverage inaccuracy 和seed选择策略做了改进,改进后的工具称为CollAFL

0x03 How

本文主要做了两个改进。第一,在AFL中,AFL要用到一个64KB bitmap来保存Coverage的信息,在AFL进行fuzzing的时候,会发生碰撞,两个快构成一个边,AFL为边赋了hash值,这个hash就代表这条边,可是不同的边计算出的hash可能是一样的,于是就发生了Collision , Collision可能会导致某些input到达新的路径,但AFL却没有将该input作为seed,本文主要针对这一点,采用了一个新的算法,解决了路径hash collision问题。第二,在seed选择的时候,CollAFL会优先选择对Coverage有贡献的seed。

CollAFL的具体做法如下。

对于hash Collision问题。

在AFL中,给定边A->B,其hash算法如下:

图片 1.png

其中prev和cur分别是基本块A和B的key, 由于key的随机性,两个不同的边可能具有相同的hash值。于是CollAFL对其进行了改进,改进如下。
给定两个带有prev和curkey的块A和B,如下图所示:

图片 2.png

其hash算法如下:

3.png

其中,<x,y,z>是要确定的参数,不同的边可能不同。AFL使用的公式是该算法的一种特殊形式,即对于所有边/块,
<x=0,y=1,z=0>。Fmul的计算过程与AFL相同,开销相同。

但是,此算法不能保证为给定的应用程序找到解决方案,因为应用程序中有太多的基本块,因此不能遍历所有可能的参数。即使可以这样做,也不能保证解决方案的存在,因为基本块的key是随机分配的。

因此,CollAFL进一步将所提出的hash计算算法改进如下:

  • 具有Single Precedent块的hash算法

如果一个块只有一个Precedent块,如下图所示:

4.png

可以在结束块中直接为该边分配一个hash,算法如下:

5.png

其中prev和cur是分配给块A和B的key,参数c是要确定的唯一常量。

  • 具有Multiple Precedents块的hash算法

如果一个块B有Multiple Precedents块,如下图所示:

6.png

即如果B具有多个传入边缘,则必须动态计算块B中的hash,算法如下:

7.png

其中prev和cur是块A和块B的key,它构建了一个离线哈希表,所有边的唯一hash以unsolvable block结尾,不同于所有其他边的hash。在运行时,它查找这个预先计算的哈希表,以获取这些边的哈希值,并使用它们的起始块和结束块作为key。需要注意的是,在运行时,哈希表查找操作比以前的算法Fmul和Fsingle慢得多。

  • 整体缓解方案

在确保bitmap size大于边数的情况下,根据不同的类型,使用Fmul、Fsingle和Fhash这三个hash计算公式,如下所示:

8.png

对于种子选择问题,CollAFL提供了三个选择策略。

  • CollAFL-br

拥有更多未受影响的邻近分支的种子将优先于模糊,该策略使用未接触的临近分支数作为测试用例t的权重,计算公式如下:

9.png

此公式只在且仅当边缘<bb,bb_i>未被任何先前的测试用例覆盖,否则为0。

通过此公式,可用权重来考虑种子的选择,即权重更高的种子将被优先考虑模糊化,值得注意的是,随着测试的进行,先前运行的测试用例集将发生变化,因此所接触的函数的返回值也将发生变化。因此,测试用例的权重是动态的。

  • CollAFL-desc

拥有更多未受影响的邻近后代的种子将优先考虑模糊,该策略使用未接触的邻近后代的数量作为测试用例t的权重,计算公式如下:

10.png

其中函数IsUntouched与CollAFL-br策略中使用的相同,函数NumDesc返回从参数基本块开始的子代路径数。其形式定义如下:

11.png

需要注意的是,这里的权重不是确定的,因为函数IsUntouched是动态的。但是,对于每个基本块,子路径的数量是确定的。

  • CollAFL-mem

拥有更多内存访问操作的种子将优先于模糊,该策略使用内存访问操作的数量作为测试用例t的权重,其计算公式如下:

12.png

其中,函数NumMemInstr返回参数基本块中的内存访问操作数,可以静态计算。因此,与前两个策略不同,以这种方式计算的权重是确定性的。

以上策略,总的来说,第一个策略,考虑的是,每个种子会走一条路径,一条路径实际有不同分支的,有些分支是被其他种子测过,有的分支没有。然后CollAFL统计这个种子多样分支被测过,有多少分支没有被测过,于是就有可能出现两个种子。第一个种子有一个分支没测过,第二个种子有N个分支没测过。CollAFL选择的就是后者,因为在第二个进行变异的时候有非常大的概率,种子存在没有被触发、测试过的分支。

第二个策略是在第一个策略基础上的改进,策略一中的分支记为初始值,此处分支后面会跟着一些子路径,所以也要考虑子路径的数目,因此计数不再是初始值,而是把后面的分支根据路径数量加进来。

第三个策略,考虑的是内存访问,CollAFL统计这个种子所走的路径,基本块访问的数量,那些访问数量多的,优先级就相应高一点。

0x04 Result

  • 在24个实际应用程序中发现了157个新的安全漏洞,其中95个被CVE确认。可惜的是,作者没有开源CollAFL

0x05 Question

确保bitmap size大于边数的原理?

答:上文中提到了AFL中的hash计算公式: ,在这个公式里,其计算结果能够保证小于等于cur或者prev的值,而cur或者prev 的值小于等于64k,bitmap 则可以认为是一个数组(如:bitmap[64]), 前面边的hash值的计算结果就是bitmap数组下标的引用,例如某个边hash值计算的结果为100,则AFL就设置bitmap[100]非零,表示该边已经走过,所以需要确保bitmap size的值要大于边数。

在很多实际情况下的工程中,测试人员是只有二进制的程序,AFL原生提供了qemu的方式去fuzz二进制,但是效率太低,从哪方面考虑解决这个问题?

答:在AFL中,qemu,llvm,afl-gcc都是为了插桩得到edge的信息。而llvm和afl-gcc都是针对源代码,qemu是针对binary。qemu可视为一个虚拟机,目的是为了给binary提供运行环境,因为binary的插桩其实是比较困难的,所以直接用qemu的运行状态来得到fuzzing想要的插桩效果,这些操作本质都是给插桩服务的。因此如果要解决qemu的速度问题,本质就是要找到合适的binary插桩方式,或者找到更好的“虚拟机”。

以上两个问题感谢师兄解答

「一键投喂 软糖/蛋糕/布丁/牛奶/冰阔乐!」

panda

(๑>ڡ<)☆谢谢老板~

使用微信扫描二维码完成支付

本文共有4244个字。标签:AFLCollAFL
版权声明:本文为作者原创,如需转载须联系作者本人同意,未经作者本人同意不得擅自转载。
添加新评论
暂无评论