一些模糊测试的论文

感觉在我写 fuzzer 之前还有好多要看……

NAUTILUS: Fishing for Deep Bugs with Grammars

CHALLENGES

  • Generation of syntactically and semantically valid inputs
  • Independence from corpora
  • High coverage of target functionality
  • Good performance

DESIGN OF NAUTILUS

通过源码编译插桩获取代码覆盖度信息,解析语法文件生成少量初始输入(1000个)并发送给调度程序,通过执行样本观察是否有新的路径被发现,如果有则根据语法精简样本并将精简后样本加入到队列中。调度程序根据是否有新的路径发现执行 Input Generation 或者 Mutation。对于加入到队列中的样本根据语法进行畸变。畸变方法包括用新生成的子树替换原队列中的子树或者将对探索新路径有帮助的样本进行结合。畸变后将样本加入到队列用于测试。
Xnip2019-02-23_18-08-14.jpg-149.3kB
emmmm 其实就是把基于畸变的模糊测试工具中常用到根据测试样本代码覆盖度的信息保留对提高代码覆盖度有帮助的样本保留并畸变,但是其实根据代码覆盖度来反应模糊测试的效率也只在那些对测试样本有格式要求的情景下有效(比如 pdfpng) 之类的,应用到根据语法生成样本的效果就没那么明显,DOM XML 之类的不太复杂的还好, javascript 因为其本身语言特性其实这个根据代码覆盖度的反馈其实作用应该不大,记得之前看过一个为语法文件的所有 rule 都分配一个 random id 类比于 AFL 的边覆盖度测量来从 rule 方面观察模糊测试的效率,其实我觉得这种应用在 js 的模糊测试上要比基于代码覆盖度的要好,如果有大佬能提出来一种对 javascript 测试效率做衡量的标准……该多好啊(现在好像也没啥方法,如果我写我会把这两个都加进去吧)

Generation

生成的样本应尽量包含不同层面的语法(和上面说的为 rule 分配 id 效果类似,但是不知道它是怎么实现的)以增加代码覆盖度。Fuzzer 的内部使用树而不是字符串来表示。

  • Naive Generation
  • uniform generation (其实这个方法我之前想到过,可是想到不就就看到了这个论文,不过这些都是参考的基于畸变的模糊测试提出来的方案,可以参考 Vuzzer 的基本块权重,也不是什么新的)

Minimization

Subtree Minimization

对于每个非终端节点,生成最小的子树。依次替换样本中的非终端节点为最小生成子树,当新的样本仍能触发之前新发现的路径时,用最小子树替换原来的子树,否则就丢弃畸变后的样本。(这个思路也很好)
Xnip2019-02-24_10-57-27.jpg-112kB

Recursive Minimization

Xnip2019-02-24_11-00-34.jpg-219.9kB

Mutation

Random Mutation

随机选择树种的一个节点并根据非终端节点生成新的子树替换它的子树

Rules Mutation

sequentially replaces each node of the input tree with one subtree generated by all other possible rules(这个 all other possible rules 是指其他的所有,还是父节点有的规则? )

Random Recursive Mutation

Xnip2019-02-24_11-36-23.jpg-186.9kB
这种方法有依据吗?????迷

Splicing Mutation

合并找到新路径的样本:用另外一个队列中的样本的子树去替换正在畸变的样本中具有相同非终端节点的子树

AFL Mutation

畸变是在将子树转换为文本之后,所以这种畸变会产生很多的无效样本,会触发一些解析阶段的 bug。在畸变完成后将畸变规则加入到 Custom Rule。(Custom Rules are not added to the grammar, they are saved locally with the tree)

  • Bit Flips
  • Arithmetic Mutations
  • Interesting Values

Xnip2019-02-24_12-05-41.jpg-165.4kB
这个畸变方法感觉也很不错

Unparsing

Target Application Instrumentation

ANTLR Parser

Preparation Phase

  • min(n)
  • p(n, l, r)
  • p(n, l)

Fuzzing Phase

State

  • init
  • det
  • detafl
  • random

                                               Xnip2019-02-24_13-20-07.jpg-101kB

CodeAlchemist: Semantics-Aware Code Generation to Find Vulnerabilities in JavaScript Engines

BACKGROUND

JavaScript and the Type System

javascript 是动态类型语言,可以运行时改变类型,也可以在运行时生成代码。

JavaScript Runtime Errors

  • SyntaxError

    1
    eval(’break’); // SyntaxError
  • RangeError

    1
    var r = new Array(4294967296); // RangeError
  • ReferenceError

    1
    u; // ReferenceError
  • TypeError

    1
    var t = 10; t(); // TypeError
  • URIError

    1
    decodeURIComponent(’%’); // URIError

OVERVIEW

Semantics-aware Assembly

JS 文件种子拆分成 code bricks,每一个 code brick 代表一个抽象语法树, code bricks 可以是一条或一组语句组成。code brickspreconditionpostcondition 两个属性用于互相连接时判断是否能组合。当两个 code brick 合并时,前一个 code brickpostcondition 未匹配的符号将会被传递给合并后的 code brick
Jietu20190301-155023.jpg-108.9kB

challenges

  • how to break JS code into code bricks
  • maintain a pool of code bricks while minimizing its size and preserving its semantics
  • rename symbols in code bricks when we assemble them so as to avoid potential reference errors
  • figure out data dependencies between variables in each code brick in order to compute assembly constraints
  • design an effective way to infer types of variables
  • devise an effective way to combine code bricks with assembly constraints to build highlystructured code snippets

    CodeAlchemist Architecture

    Jietu20190301-161150.jpg-84.9kB

    SEED PARSER

    JS seed -> AST -> code bricks

    CONSTRAINT ANALYZER

    Analyze 函数通过数据流分析识别 code bricks 上被定义和使用的符号

    Instrument 函数通过动态插桩跟踪变量类型

    ENGINE FUZZER

    根据合成约束生成样本,定义配置文件来修改 code bricks 的组合方式。

    Running Example

    Jietu20190301-195340.jpg-111.8kB
    1
    U → Code Brick → D

For3-0 对应于整个 for-loop,没有定义新的变量。变量 i 被认为定义在 For3-1 内。
Jietu20190301-202127.jpg-54.4kB

CODEALCHEMIST DESIGN

Seed Fragmentization

LangFuzzAST 根据非终端节点生成一组子树,但是会造成不同子树的大量重叠。如果将 JS 根据表达式进行拆解,则无法形成高层次的代码结构,所以 CodeAlchemist 根据语句拆分种子文件。SEED PARSER 模块递归 AST 中的每条语句,返回一组 code bricks。对于块语句,将其分成两个 code bricks,one with the whole original body, and another with an empty body。如果块语句包含 guard ,则添加一个包含 body 语句的 code brick。通过将块语句分成 whole original bodyempty body 将会在保持原始语义结构的同时增加生成样本的复杂度。
Jietu20190301-215539.jpg-105.7kB

Code Brick Pool

去除语法不同语义相同的代码块。CodeAlchemist 将有相同 ASTcode brick 看做重复的 code brick。去除一些引起干扰的内置函数如 eval(因为 CodeAlchemist 还不能推断动态生成代码的约束集),去除无用代码,删除 pool 中无法再 js 引擎上运行的 code brick

Semantics-Preserving Variable Renaming

  • code brick pool 中语义相同的 code brick 去重并规范符号
  • when it assembles two code bricks, it renames symbols so that all the used variables can refer to variables of the same type.

对于 pre-defined symbols 不进行重命名

Data-Flow Analysis

通过数据流分析识别 code brick 中定义和使用的变量。路径不敏感的数据流分析导致错误的判断在 code brick 中使用和定义的变量。例如 if else 语句。

Type Analysis

Jietu20190302-115528.jpg-143.4kB

1
2
if (x < 42) y = 42;
else y = [];

  • 构建内置类型系统
  • 将部分变量类型设为 union 解决因路径不敏感导致的约束集中变量类型差异

    Code Brick Assembly

    Jietu20190302-122337.jpg-175.6kB

FuzzIL: Coverage Guided Fuzzing for JavaScript Engines

Skyfire: Data-Driven Seed Generation for Fuzzing

Superion: Grammar-Aware Greybox Fuzzing

Fuzzing with Code Fragments

IFuzzer: An Evolutionary Interpreter Fuzzer using Genetic Programming

Grammar-based Whitebox Fuzzing

paper links

NAUTILUS: Fishing for Deep Bugs with Grammars
FuzzIL: Coverage Guided Fuzzing for JavaScript Engines
CodeAlchemist: Semantics-Aware Code Generation to Find Vulnerabilities in JavaScript Engines