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。 而在工业界，一般分两种做法： peach为代表的模版流派：研究人员通过XML等方法定义输入数据的格式，这种常见于文件格式和协议的fuzzer。 依赖于样本的收集和变异的样本流派：例如早年间IE和Flash的fuzzer很多依托于通过爬虫搜集的大量样本集合。整体来说，那个时代工业界的fuzz是各流派的独门秘籍，每个人都有自己的秘不外传的实现，热闹非凡但原理上大同小异。 虽然这些方案看起来都非常home brew，在早期的软件复杂度和质量的前提下，人们依然能够取得较好的成果。但随着软件复杂度的摩尔式增长和SDL开发流程的全面引入，停留在农耕时代的fuzzer们发现，自己开始跟不上软件发展的潮流了。 从越南战争到海湾战争 所有信息安全面临的问题都能在军事界找到类似的场景。美军在越战之中投放了前所未有的火力和军队，但依然遭受了惨重的伤亡乃至最后停战。越战的问题集中反应在火力杀伤效率的低下，面对防御严密的目标，攻击方只有两种选择 特种部队渗透或地面强攻。但这需要大量情报和兵力支持，并极有可能遭受大量伤亡。 提高航空兵和地面炮火火力密度，寄希望于火力扇面能够覆盖目标。但这只会进一步造成火力的浪费，同时仍然无法保证毁伤效率。 这和fuzzing技术后期面临的问题是类似的。针对越来越复杂的目标，纯粹堆计算资源的dumb fuzz效果已经可以忽略不计，但程序分析本身是一个NP-hard问题，符号执行的方法极易引起路径爆炸，对于复杂的软件最终会撞到资源墙上。而工业界的方法过于强调样本或格式指引而非程序指引，要么需要投入大量的前期精力编制模板，或者在缺乏context的情况下两眼一抹黑撞大运。 直至80年代末期，人们所设想的现代战争形式依然是拼消耗的钢铁洪流对撞，两伊战争的结果更是给这个理论增加了注脚。萨达姆在海湾阴云密布时，仍然充满了信心，仗百万精兵要让多国部队血流漂橹。 然平静之下，暗流涌动。针对以上问题，电子技术的发展和成熟及应用催生着新一代的军事革命，并最终在海湾战争中完美登台亮相。多国联军以摧枯拉朽之势击败了伊拉克军队，彻底颠覆了过往的战争形势，震撼了全球： 精确制导武器极大提升了火力发现和打击的效率 – 精准原则 C4ISR数据链指挥系统带来了从古至今所有军人梦寐以求的战场单向透明 – 敏捷原则 漫长的黑夜预示着黎明，更精准、更敏捷的划时代fuzzer即将登场。 横扫千军如卷席 随着LLVM工具链的成熟和计算资源的大发展，基于编译器插桩的coverage-feedback driven fuzzer渐渐成为了答案之一。正如美军在海湾战争展示的新军事革命一样，AFL的诞生则宣告着这个永恒的问题出现了一个高分答案。 AFL (Americal Fuzzy Lop，logo是美洲本地可爱的长毛兔) 由Michał Zalewski在2014年发布并开源，并迅速像AK47统治枪械市场一样成为了fuzzing系列工具的de facto standard，数年间斩获上万CVE。 基于编译时插桩和自定义bitmap的方法维护coverage信息，以简洁的方式巧妙地解决了以往获取coverage效率太低的问题 基于fork/exec的方式极大提高了fuzz效率 coverage导向的遗传进化算法简单但惊人地有效 在设计上即支持多进程甚至跨集群并联 在先驱者探明道路之后，后继者雨后春笋般涌现出来。LLVM也推出了自己的实现libfuzzer，以in-process mode取代了fork mode。基于AFL和libfuzzer的体系，结合protobuf定义，模版化fuzz也以structure-aware fuzzing的名义重返舞台。内核领域的对应者syzkaller也取得了极大成功。这类方法统称为Coverage-based greybox […]