Fuzzing战争: 从刀剑弓斧到星球大战

Fuzzing这个事物大概可以上溯到1950年，当计算机还在读取打孔卡作为输入的时候。那时候的工程师会从垃圾箱里随机检出一些废弃卡片，或者在卡上随机打孔作为输入来测试自己的程序。在1988年，Barton Miller在课堂上将Fuzzing这个名词正式确定，从此拉开三十年波澜壮阔的序幕。

广义上的Fuzzing并不是漏洞挖掘中的专属内容，而是DevSecOps和Continous Integration质量保证中必不可少的一环，甚至可以延伸到完备图灵自动机的美妙梦想。在起初，人们通常以monkey testing来指代最原始的fuzz，就像著名的无限猴子定理一样：让一只猴子在打字机上随机地按键，当按键时间达到无穷时，几乎必然能够打出任何给定的文字，比如莎士比亚的全套著作，当然也有可能包含一套Nginx RCE。

但很显然，随机化的输入虽然终究能覆盖所有的输入空间，在人类未来可预见的算力水平下近乎天方夜谭。刘慈欣在《诗云》中有一个宏大的故事：宇宙神级文明为了写出最优雅的诗，而把整个太阳系的物质作为存储器，采用枚举遍历的办法把所有文字的排列组合全部生成并存储了下来。但最后神却发现，即使理论上这里存储了所有的诗句，他也无法在可接受的时间内找出目标来，因为美妙这个词本身就是主观而无法定量界定的。以神的算力尚且无法完成，以人的算力就更不可能了。随着软件复杂度大爆炸式的增加，dumb fuzzing的随机生成方式相当于在东方明珠上向下扔一只钉子，寄希望它能刚好掉进楼下某个人举着的酒杯里。

从刀剑弓斧到热兵器时代

为了解决以上问题，在学术界，结合动态执行的symbolic execution在一段时间成为了主流，KLEE[1]即是其中的扛鼎之作。在Z3 Solver和LLVM bitcode infrastructure的加持下，KLEE能够自动解析各式各样的条件代码语句并生成输入，进而辅助fuzzing。

KLEE solving maze

而在工业界，一般分两种做法：

• peach为代表的模版流派：研究人员通过XML等方法定义输入数据的格式，这种常见于文件格式和协议的fuzzer。

• 依赖于样本的收集和变异的样本流派：例如早年间IE和Flash的fuzzer很多依托于通过爬虫搜集的大量样本集合。

整体来说，那个时代工业界的fuzz是各流派的独门秘籍，每个人都有自己的秘不外传的实现，热闹非凡但原理上大同小异。虽然这些方案看起来都非常home brew，在早期的软件复杂度和质量的前提下，人们依然能够取得较好的成果。但随着软件复杂度的摩尔式增长和SDL开发流程的全面引入，停留在热兵器时代的fuzzer们发现，自己开始跟不上软件发展的潮流了。

从越南战争到海湾战争

所有信息安全面临的问题都能在军事界找到类似的场景。美军在越战之中投放了前所未有的火力和军队，但依然遭受了惨重的伤亡乃至最后停战。越战的问题集中反应在火力杀伤效率的低下，面对防御严密的目标，攻击方只有两种选择

1. 特种部队渗透或地面强攻。但这需要大量情报和兵力支持，并极有可能遭受大量伤亡。

2. 提高航空兵和地面炮火火力密度，寄希望于火力扇面能够覆盖目标。但这只会进一步造成火力的浪费，同时仍然无法保证毁伤效率。

越战美军遭遇狙击手冷枪后无法发现目标，只能召唤火力盲目覆盖

这和fuzzing技术当时面临的问题是类似的。针对越来越复杂的目标，纯粹堆计算资源的dumb fuzz效果已经可以忽略不计，但程序分析本身是一个NP-hard问题，符号执行的方法极易引起路径爆炸，对于复杂的软件最终会撞到资源墙上。而工业界的方法过于强调样本或格式指引而非程序指引，要么需要投入大量的前期精力编制模板，或者在缺乏context的情况下两眼一抹黑撞大运。

直至80年代末期，人们所设想的现代战争形式依然是拼消耗的钢铁洪流对撞，两伊战争的结果更是给这个理论增加了注脚。萨达姆在海湾阴云密布时，仍然充满了信心，仗百万精兵要让多国部队血流漂橹。

然平静之下，暗流涌动。针对以上问题，电子技术的发展和成熟及应用催生着新一代的信息化军事革命，并最终在海湾战争中完美登台亮相。多国联军以摧枯拉朽之势击败了伊拉克军队，彻底颠覆了过往的战争形势，震撼了全球：

• 精确制导武器极大提升了火力发现和打击的效率 - 精准原则

• C4ISR数据链指挥系统带来了从古至今所有军人梦寐以求的战场单向透明 - 敏捷原则

漫长的黑夜预示着黎明，更精准、更敏捷的划时代fuzzer即将登场。

横扫千军如卷席

随着LLVM工具链的成熟和计算资源的大发展，基于编译器插桩的coverage-feedback driven fuzzer渐渐成为了答案之一。正如美军在海湾战争展示的新军事革命一样，AFL的诞生则宣告着这个永恒的问题出现了一个高分答案。

可爱的AFL实际上有着锋利的牙齿

AFL (Americal Fuzzy Lop，logo是美洲本地可爱的长毛兔) 由Michał Zalewski在2014年发布并开源，并迅速像AK47统治枪械市场一样成为了fuzzing系列工具的de facto standard，数年间斩获上万CVE。

1. 基于编译时插桩和自定义bitmap的方法维护coverage信息，以简洁的方式巧妙地解决了以往获取coverage效率太低的问题

2. 基于fork/exec的方式极大提高了fuzz效率

3. coverage导向的遗传进化算法简单但惊人地有效

4. 在设计上即支持多进程甚至跨集群并联

在先驱者探明道路之后，后继者雨后春笋般涌现出来。LLVM也推出了自己的实现libfuzzer，以in-process mode取代了fork mode。基于AFL和libfuzzer的体系，结合protobuf定义，模版化fuzz也以structure-aware fuzzing的名义重返舞台。内核领域的对应者syzkaller也取得了极大成功。这类方法统称为Coverage-based greybox fuzzing(CGF)，如秋风扫落叶一般横扫各大系统软件，进而成功入关获得了学术界的注意。

CCS'16中Marcel Bohme, et al[2]将工业界的这项革命成果正式通过Markov Chain的方式予以理论化，即Fuzzing实际上是不断变化的马尔可夫链，马尔可夫链的各个节点代表了程序的各种状态，而种子选择和样本变异的策略将直接影响结点之间的转移概率。那么衡量CGF Fuzzer效率的指标自然就是发现新节点的概率是否足够大，以及节点之间转移的概率*次数（命名为能量，注意这里的能量并不是指省电费降低服务器负载的概念，而是说对各个样本和路径的单位fuzz投入和需要生成的input数量，笔者认为称为FI, fuzzing investment更合适）是否足够均衡。

Markov Chain for CGF Fuzzer

在能量体系的武装下，Marcel等人提出了AFLFast对AFL设计中存在的能量问题做了进一步改进。Marcel等观测发现，AFL的默认调度算法存在着两个问题

• 常量平均分配启动方式会导致额外的FI被浪费，影响启动效率

• 高密度到达区域会进一步消耗更多的FI，导致低密度区域无法触达，造成恶性循环

针对这些问题，AFLFast在FI调度算法和搜索策略上进行了改进，在真实Fuzz目标-binutils上获得了比AFL高1-2个数量级的发现，在24小时内发现了原始AFL未能发现的4个CVE，平均达到19倍的效率提升。Team Codejitsu在美国国防部和DARPA组织的CGC - 基于人工智能的自动化漏洞挖掘大赛上，使用AFLFast获得了漏洞发现数目单项挑战的亚军。

AFLFast vs AFL

在系统层面，Wen Xu等在ACM CCS 2017[3]上提出了AFL原始实现中fork和多实例样本同步中存在的问题：

1. 即使fork模式已经节省了大量的binary载入时间，但在多核集群上大量实例并行执行时，fork本身仍然会成为昂贵的操作（新建页表、锁开销）等。事实上我们需要维护的只是内存页的COW快照，而不用维护一个新父子进程的完整实例。

2. 多实例同步依赖于小文件队列的读写，在文件metadata上会浪费较多时间，同时对文件系统造成不必要的压力

通过新增snapshot等syscall来解决以上问题，最终在多核机器上取得了至少40%的性能提升。

AFLOPT vs AFL

在Zalewski于2018年宣布挂印归隐后，社区接过了AFL发展的任务，并以AFL++的形式继续发布。AFL++引入了上述研究在内的多种优化，继续在各大服务器里冲锋陷阵，繁荣的新时代已然到来。

使命召唤：未来战争

未来战争是什么形式？未来的Fuzzing又是什么形式？笔者并无意断言也无法断言，但仍愿管窥一二抛砖引玉

• 随着5G时代的到来和音视频流载体业务的愈发盛行（短视频、直播、在线会议等），多媒体库和相关业务承载着越来越多的关注，Fuzzing的触角也在从传统的软件延伸到全链路的各个环节。

• DARPA组织的Cyber Grand Challenge尝试将漏洞挖掘与AI进行结合，而最终的结果证明了CGF及其改进版仍是距离自动化漏洞挖掘和利用这一伟大目标最为实际的路径。

• 得益于虚拟化技术的进步和RISC for server computation的普及，CGF在跨平台blackbox binary上也变的可行，车联网、IOT、基带、工控固件、closed-source binaries中仍有无穷无尽的漏洞等待发掘。

在历史洪流的大背景下，漏洞军火化不再是遮遮掩掩的话题，而逐渐露出了真刀真枪国家对抗的原本面目。互联网设施的安全保卫和对等威慑能力的建设和实施，包括ClusterFuzz/OSSFuzz这样基础平台的建设，已经是时代摆在面前的课题。

在后续系列文章中，笔者将结合上述展望，尝试再度展开一二，敬请期待。

如果ClusterFuzz/OSSFuzz被军用会怎么样？或者说，DARPA、CIA内部是否肯定有类似的设施？

[1] KLEE - KLEE LLVM Execution Engine https://klee.github.io/

[2] Coverage-based Greybox Fuzzing as Markov Chain - https://www.comp.nus.edu.sg/~abhik/pdf/CCS16.pdf

[3] Designing New Operating Primitives to Improve Fuzzing Performance - https://gts3.org/~wen/assets/papers/xu:os-fuzz.pdf