AFL fuzzing的艺术

在本篇文章中,作者Brendan Dolan-Gavit将会为大家详细讲述他的关于AFL fuzzing的经验与理解。

他用以前文章中用过的一个测试用例测试了AFL对于寻找LAVA设置在程序中错误的能力。在测试过程中,他发现了AFL中一个可能无害的错误,以及影响其性能的有趣因素。尽管它的界面异常简单,AFL还是需要一些调整,因为有一些意想不到的错误会决定成败。

American Fuzzy Lop,简称为AFL,是谷歌Michal Zalewski开发的一款强大的覆盖引导fuzzer。从2013年发布以来,它已经在安全领域广受称赞。鉴于其取得的惊人的成功,于是作者迫切地想要知道它是如何应对一个自动生成的错误的。

最开始Brendan使用的是以前他的文章中使用过的一个程序,并且在其中添加了一个错误。每当 file_entry 的前四个字节被设置为 0x6c6175de 或 0xde75616c,就会触发由LAVA添加的这个错误,错误会导致 printf 变成无效的格式字符串,程序调用崩溃。

在验证错误可被有效触发之后,作者用 afl gcc 进行了编译并开始模糊化运行。为了顺利开始测试,他在程序中使用了包含整型和浮点 file_entry 类型的格式良好的输入文件︰

0000000: 4156 414c 0000 0000 0200 0000 7212 8357 AVAL........r..W

0000010: 6c69 6768 7400 0000 0000 0000 0000 0000 light...........

0000020: 0200 0000 4a78 de11 706c 616e 636b 0000 ....Jx..planck..

0000030: 0000 0000 0000 0000 0100 0000 c308 d440 ...............@

幸运的是,因为作者拥有一个24核服务器,所以他马力全开运行了四天半(一个使用-M ,其他的使用-S),满心期待着它可以在这段时间里找到输入值。

但是结果不如人意。

大约200亿次执行之后,AFL找到了zilch。

与此同时,在作者的Twitter上,他的好友John Regehr建议他看看AFL过去实现的是什么样的覆盖。作者这才意识到,事实上,他完全不知道AFL是怎么进行检测的。

深入发掘AFL的检测机理

基础版的afl-gcc和afl-clang工具其实都非常简单。它们分别包括gcc和clang,然后修改其编译过程,发出中间程序集代码(使用-S 选项)。最后做一些简单的字符串匹配 (C ,ew) 来找出在何处添加AFL的覆盖日志记录功能。你可以用 AFL 保存它使用 AFL_KEEP_ASSEMBLY 环境变量生成的程序集代码,然后就可以看到它的一切行为了。(事实上人们最近也的确使用LLVM pass添加了一种新的检测方式)

原程序代码

在AFL的仪表已添加相同的代码

看到如图所示生成的程序集之后,你会意识到if语句分支对应的代码得不到检测。这是个潜在的问题,因为如果没有任何记录告诉它输入值已经达到目标,AFL就没办法覆盖程序的每一个部分。

看一下afl-as的源代码(检测程序集的程序)。仔细观察这部分的代码。

AFL在汇编代码中跳过紧接着的p2align指令

根据这个意见,它应该只会影响在 OpenBSD 下编译的程序。然而,你会发现起初想要检测的分支也被影响了,即使运行环境是Linux,不是OpenBSD,程序中也没有跳转表。

.L18模块应使用AFL,但在对其语句后,它是正确的。

因为不是在OpenBSD环境下,所以你可以直接去掉了if语句。作为备用的变通方法,还可以把 "-fno-align-labels -fno-align-loops -fno-align-jumps"添加到编译命令中去(但是会损失可能较慢的二进制文件)。更改之后你需要重新启动运行,再一次期待AFL可以很快发现这个错误。

可是再一次失败了。17个小时的运行之后什么都没有发现,所以我们需要回到制图板。作者现在还是相当确信他找到了AFL的一个错误,但是修复这个错误并不能帮助它找到我感兴趣的那个错误。(备注:或许再等待四天就可以找到错误了。另一方面,AFL 的周期计数器已经变成了绿色,表示它认为没有必要继续了。)

“展开”常量

仔细想了一下AFL还需要什么才能找到这个错误,突然,作者意识到它找到错误的概率相当低。AFL看到新的覆盖时只会优先测试用例。在我们的测试程序中,它不得不需要在文件的准确位置中猜测两个具体的32位触发值,概率太小了。

那AFL是怎样生成CDATA标记的呢? libxml2 有宏展开一组字符串,然后用简单的if语句逐字符比较。这使得AFL 可以发现有效的字符串字符,因为每个正确的字符将添加新的覆盖范围,并导致进一步模糊化输入值。

我们也可以把这些应用于测试程序中。我们不检查固定常数 0x6c6175de,而是单独地比较每个字节。这使得 AFL 可以一次确定触发器的一个字节。新的代码是这样︰

if (strcmp(header.magic_password, "h4ck3d by p1gZ")) goto terminate_now;...or:

if (header.magic_value == 0x12345678) goto terminate_now;

一旦我们用afl gcc编译,AFL只要三分钟就可以用单一CPU发现一个错误!

AFL发现bug

这也使作者更加肯定,将整体分解为字节大小的模块是十分值得去尝试的,这样可以更加容易地让理编译通过。至于字符串比较,人们可以在strcmp / memcmp内联实现替代。

隐藏的覆盖陷阱

在调查覆盖问题的时候,你会注意到AFL有一个新的编译器:afl-clang-fast。这个模块是由 László Szekeres贡献的,执行仪器仪表作为 LLVM 通行证,而不是通过修改生成的程序集代码。因此,AFL会变的更坚固,检测选项也会变得更多。

因此,即使我们已经在源代码中添加了不同的if语句,生成 的LLVM 语句看起来更像我们的原始语句。

使用LLVM的仪器模式,AFL将不再发现我们的错误。

让AFL字典更智能

虽然我们能够让AFL产生触发输入显示错误的调整程序,这已经很好了,但是,如果我们能让它在我们的原始程序中发现的bug就好了。

AFL使用困难,是因为它们需要一次猜测一个32位的输入。对于这一点来说,需要搜索的空间相当大:即使假设它开始系统地在文件的右侧快速查询字节位,它将平均采取20亿个执行才能找到正确的值。当然,除非它有一些理由相信,在该文件的一部分工作将进行改进覆盖,它不会专注于正确的文件位置,因为这使其更加不可能会找到正确的输入。

然而,我们可以允许AFL选择不完全随机的输入来接入。AFL的一个特点是,当它在进行模糊测试是支持使用字典的值。这基本上是一组标记,它可以利用在变异的文件而不是随机选择的值。因此,一个典型的诀窍是把程序中发现的所有常量和字符串都添加到字典中。如下,使用AFL从一个二进制中提取常量和字符串的被污染的脚本:

#!/bin/bash

objdump -d "${1}" | grep -Eo '\$0x[0-9a-f]+' | cut -c 2- | sort -u | while read const; do echo $const | python -c 'import sys, struct; sys.stdout.write("".join(struct.pack(" > testcases/$const; done

i=0; strings "${1}"| while read line; do echo -n "$line" > testcases/string_${i} ; i=$[ $i + 1 ] ; done

结论一旦我们给AFL一个字典,它将会在15分钟内发现94%(149/159) 的错误

看到我们自己设置的错误之后,我们发现了一些关于AFL有趣的事情:

·AFL发现错误的能力和覆盖检测的能力息息相关,检测能力和AFL的错误和不同的编译时间有关。

·代码结构也会严重影响AFL性能,看似微小的差异就会产生巨大的影响。

最后,这就是我们希望用LAVA做出的结果。通过仔细检查当前的错误检测工具,你们将会更好地理解它们的工作原理并且找出发现错误更好的办法。