Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

FuzzGen: Automatic Fuzzer Generation

作者:Kyriakos Ispoglou, Daniel Austin, and Vishwath Mohan; Mathias Payer

单位:Google Inc.; EPFL;

会议:USENIX Security 2020

链接:原文 代码

Fuzz很重要,很有效,但都是面向program而非library的。library的接口上看不出来函数间的依赖关系、函数参数上的规范,而调用序列和参数规范对于API的工作都是很重要的,因此直接给API喂随机输入很难得到有意义的结果。所以,对library的fuzz,现在主要是靠人工手写一个小程序,然后对这个程序做fuzz。

libFuzzer是一个对library的fuzz辅助工具,需要人工提供桩代码,其中API的依赖关系、对哪些函数做fuzz、对哪些参数用随机输入仍然是人工考虑的。

本文的工作FuzzGen从系统中已有使用库的代码出发,通过对整个系统进行分析,整理出抽象API依赖图(A2DG),并基于依赖图生成libFuzzer的桩代码,从而进行不需人工干预、能较好地平衡宽度和深度的fuzz。作为验证,本文在Debian和AOSP上选了7个库,找到了17个未补的漏洞,6个给了CVE;平均覆盖率达约55%,比手写的高了约7%;

API-aware Fuzz的困难

作者选用libmpeg2这个库来说明问题。这个库要求在对视频解码之前,先要初始化一个decoder object。如果一个fuzzer要对视频解码的API进行测试,而不先进行完整的初始化,则会引起非预期的错误。如给函数指针或缓冲区长度赋一个随机值,虽然可以导致崩溃,但这并不是bug而是单纯由使用错误造成的。

视频解码的函数依赖其他的初始化函数进行,而这种依赖关系在代码库的层面是缺乏描述的,只有使用了库的代码中才存在这些信息(被称为library consumer)。依赖关系可能是

  • API之间的先后关系、条件关系,即控制流上的依赖性;
  • API之间可能有直接的数据共享(参数);

在API之间共享状态的数据结构在Fuzz时不应该被修改。但这种依赖关系是很难分析的,因为有:

  • 存在一个API有多个分派路径的情况
  • 指针嵌套的复杂性

相关工作

Fuzz的分类包括:

  • 输入来源:生成/变异
  • 对目标程序的知识情况:黑盒/白盒/灰盒

路径覆盖率是Fuzz工作中常用的评价指标。很多工作都存在着覆盖率墙,即一定程度后生成的新输入都无法覆盖到新的路径,目前主要的解决思路包括增加约束求解、调整待解输入的排序。本文可以对一个库生成多个长短有异的的测试例,这也是一种方法。

对于库的测试,有一个叫FUDGE的相关工作,分析单个consumer、提取代码片段来组成测试例。本文的FuzzGen显然是一个更灵活的方案。

有一些对API使用做检查的工作,用到的方法包括动态分析、符号执行、专家规则。本文使用全程序分析。

设计

FuzzGen的分析过程同时需要库和consumer。通过一个全程序分析,FuzzGen可以从中习得API的合理调用序列。相比于人工,FuzzGen可以从多个consumer中学习,能够覆盖更多的库使用情况。其过程可分为三个阶段。

  • API Inference: 确定哪些是API
  • A2DG Construction: 从控制流和数据流两方面构造A2DG
  • Fuzzer Stub Synthesis: 生成桩代码

image-20200509145405503

确定API

即找出库里的函数,哪些是API。本文选择将库声明的所有函数 $F{lib}$ 与consumer所有头文件引用的函数 $F{incl}$ 的并集认定为API函数集 $F_{API}$。

可能存在过近似,即将目标库引用的另一个库判定为库函数。作者通过链接测试来排除这些过近似的情况。(?)

生成A2DG

image-20200508233244011

A2DG的控制流部分即以API为节点的有向图,与CFG类似但只保留API,边上保留参数信息。

  1. 建立基本A2DG。直接对LLVM中的基本块进行操作,保证每个块中有且仅有一个API call,并进行跨函数的图集成。作者考虑了递归;函数指针可能引起过近似,即可能生成一些不存在的调用路径。

  2. 多个A2DG合并。对不同的consumer可能生成不同的A2DG,可以基于其中相同的节点进行合并(相同API,相同参数)。可能造成不一致状态,即两个路径的调用序列可能存在冲突。

    image-20200508233019790

这个阶段可能有些假阳性,但作者对所有最终生成的桩代码进行了检查,表示实际出现的很少。

合并之后涉及到图的展开,类似于拓扑排序,但实际上对同一层级的函数不区分先后,运行时依输入选择。

参数流分析

进一步为A2DG添加数据流信息。又分为Value-Set Inference、Dependency Analysis两个过程:

Value-Set Inference目的是确定每个参数的可能值和类型,从而确定哪些参数要fuzz,该怎么fuzz。先对API进行函数内数据流分析,标记参数的可能值以及属性(是否是常量,是否被修改,etc);然后通过后向切片在consumer中进行跨函数分析;两者结果不同的需要合并,目前倾向于以跨函数分析的结果为准,因为这些是实际使用的代码。

Dependency Analysis分析参数之间的依赖关系,同样先进行函数内分析,然后通过跨函数分析来连接结果,这个过程中确定出每条边所代表的参数。

这个阶段可以解析出一些API内部的错误处理逻辑,但A2DG上最终不保留这些部分。

桩代码生成

把有向图序列化成代码。需要注意平衡宽度和深度。

比较有趣的是他再生成的代码中,加了一些根据随机输入的判断,这样一来fuzzer本身就能够在一定程度上改变控制流。

评估

image-20200509154307691

主要选择的是解码库,和专家规则进行了对比,而不选择直接对consumer做fuzz作为基准,考虑到这样一来consumer的质量对fuzz结果的影响过大。提到libmpeg2需要人工进行几周的学习,而自动化生成仅需几分钟;前三个库都使用以command为参数的单一接口函数。

作者发现并非consumer越多越好,A2DG可能会越来越复杂,但并不包括新的目标路径,因此需要对Consumer进行一定的选择。目前的指标为 $D_c$(Density of Consumer),即consumer中API调用的密度。

image-20200509160143354

image-20200509155955832

image-20200509160017626

Android测试

总体来讲人工写的stub更加的精简(代码行数),性能更好(单位时间执行数),更加定向(找到的bug数量),而FuzzGen能达到更高的覆盖率。但其实也只有libhevc的人工样例优势明显。

Debian测试

Debian上consumer的选择要充分很多。人工样例的执行速度会更慢一些,因为其中包括了循环,而机器生成的样例中没有。作者提到对于视频库的fuzz,对多帧进行解析会构造出更复杂的内部状态。