用 AFL 玩超级玛丽：通过Fuzzing探索程序空间状态以发现更多执行路径

今年S&P顶会上有一篇研究论文"IJON: Exploring Deep State Spaces via Fuzzing"，他们通过改造AFL来探测程序的空间状态，以发现更多程序行为，并拿游戏"超级玛丽"来作演示：

当前最流行的Fuzzing技术就是基于覆盖率的方法，Edge Coverage应该是当前最有效的覆盖率统计方法，比BasicBlock方式多记录调用边界，而afl对覆盖率的探测很多是暴力猜解的，一些afl家族工具也对其进行扩展，比如切割多字节指令为单字节作数据比较，提取cmp指令的一些常量操作值作变异。但是，这种方法对于一些特定的代码结构，若不去探测程序状态空间的中间点，就很难触发新的覆盖路径。

何为程序状态空间？

状态空间代表程序所有可能状态的集合，状态代表内存和寄存器的一种配置，以及系统提供的状态(比如文件描述符、类似原语)。状态空间比代码覆盖统计空间更大，若改造AFL就需要实现对状态空间的支持，以优化测试用例达到状态的多样性。

论文主要贡献

1. 分析当前主流Fuzzer的反馈机制，并实现如何用它们表示状态空间；

2. 扩展当前主流的覆盖反馈Fuzzer的能力，允许分析人员通过程序状态空间解决当前业界方法无法解决的路径约束问题；

3. 展示了可信平台模块(TPM)、复杂格式解析器、超级马里奥游戏、迷宫和散列映射实现的软件仿真器的状态空间，演示其是如何被Fuzzer有效探索到的。顺便，解决掉一些CGC挑战集合中的难题（CGC专门为机器人自动打CTF而设计的题目，与真实软件场景还是有差异的），也发现了一些真实软件的漏洞（其实就是一个偏门的dmg2img工具而已）。

主要设计原理

作者设计了一套源码注释原语，其实就是给源码加个一两行补丁代码，用来干预Fuzzer的反馈功能。在可交互的Fuzzing会话中，分析人员可以人工介入去分析一直无法触达的执行路径，然后为其增加补丁代码解决路径探索障碍的问题。

afl-gcc或afl-clang本身就是对gcc/clang编译器的封装，添加一些编译选项，以及代码插桩的功能，作者为其编写了个链接库，以实现前面所说的注释原语，包括一些自定义函数和宏等，通过它能够访问AFL用于存储覆盖信息的位图（其实是个哈希表），直接添加和设置条目上去，将状态值直接反馈给Fuzzer。同时，也允许相同的edge coverage存储到不同的覆盖位图中，因为不同的状态值可能触发的是同一处edge coverage，这代表它能够实现更细粒度的反馈，为此它还提供扩展用于存储覆盖位置的共享内存区域。对于状态空间爆炸的问题，也会提供"爬山算法”（hill-climbing）作出优化选择。

作者对超级玛丽作了修改，使所有的键盘命令都可以从标准输入中读取，并且马里奥只能不停地向右跑，只要停下来就死掉，这个设计主要是为节省时间。

作者还用改造后的Ijon与AFL作对比，运行12小时的AFL看其能打到哪一关，而使用注释原语的Ijon只几分钟就通过了大部分的关卡，有些确实过不了。下图是超级玛丽打喷火怪兽那关，线条是Fuzzer发现的所有执行路径，对比还是比较明显的，AFL暴力探测的密集度比较明显，更关键还是没通关，至少从作者统计图上看是如此的。

论文链接：https://www.syssec.ruhr-uni-bochum.de/media/emma/veroeffentlichungen/2020/02/27/IJON-Oakland20.pdf

本文始发于微信公众号（漏洞战争）：用 AFL 玩超级玛丽：通过Fuzzing探索程序空间状态以发现更多执行路径