Reading Papers - White-Box Fuzzing
# Grammar-Based White-Box Fuzzing
# PLDI'08 - GWF
GWF 是(已知)最早的 grammar-based fuzzer 。
Taxonomy : generation-based / coverage-guided / white-box fuzzing
Tag : grammar-based fuzzing
对于输入高度结构化的程序,例如编译器、文本解释器等,在其多阶段处理过程中通常含有大量的控制流分叉,这使得 white-box fuzzing 难以到达被测程序的深处,严重限制其有效性。
GWF 利用合法输入的语法规范来增强 white-box fuzzing ,由两个部分组成:
high-level 的符号化约束:不同于传统 white-box fuzzing 直接将输入转化为符号值,GWF 将 tokenizer(事先由人工标记的被测程序中的函数)返回的 grammar token 符号化,据此生成约束。
自定义的约束求解器,用于求解符号化的 grammar token 上的约束。
例如解释器的一个有效输入 function f() {}
对应于一组 token , , , , , ,grammar-based 的约束求解器可以直接判断出只能变异 以维持输入的有效性。
每个输入 都有一个关联的限界 ,表示生成 的父路径约束的深度。如果路径约束 的长度 ,则生成另外的约束 ,并据此生成新的实际输入。
context-free 的约束求解器不能处理 的情况(?没看懂),为此可以将 转化为下推自动机,将 转化为有限状态自动机,然后计算 和 的乘积(一个下推自动机)。
# ASE'16 - MoWF
MoWF 基于输入模型定向地生成合法的文件输入。
Taxonomy : generation-based / directed / white-box fuzzing
Tag : grammar-based fuzzing
KEY Idea :在文件处理程序中,某些分支是否被执行仅取决于 (1) 特定数据块的存在 (2) 数据块中的字段的特定值 (3) 数据块的完整性。
MoWF 是 MoBF 和 WF 的某种结合,旨在解决曾经难以解决的问题:
MoBF (model-based black-box fuzzing) 基于输入模型(指定了数据块的格式和完整性约束)随机生成有效的文件输入。模型保证生成的输入是合法的,但 black-box fuzzing 仍然是随机的本质。
WF (white-box fuzzing) 能够为数据库中的字段生成特定值,但不能高效地添加或删除数据块、或是处理完整性约束(例如 checksum ,size_of ,offset_of 等),并且 WF 需要有效的初始种子来启动。
GWF (grammar-based white-box fuzzing) 能够基于上下文无关文法生成有效的文件输入,但是 GWF 会将约束转换为正则表达式后求解,其表达能力比路径约束要弱得多(?为什么)。此外,GWF 同样不能处理完整性约束。
本质上,输入模型在 MoWF 中的作用是裁剪搜索空间,因此模型不需要是完整的;此外,white-box fuzzing 会系统性地探索未被裁剪的部分,从而构造出所有的“半有效”文件 (semi-valid) 。
注意:本文的 motivating example 比较长,请参阅论文原文。
考虑 KEY Idea (1) ,即那些由特定数据块的存在或不存在决定能否执行到的分支,经验表明,这样的分支通常会涉及输入中的枚举类型 (enumerable type) 的字段。MoWF 识别并探索这些分支的方法如下:
首先利用污点分析技术识别输入中会影响已覆盖分支的字节。
然后根据输入模型获取这些数据字段的类型,如果是枚举类型,且分支的两边没有被全部覆盖,且未执行侧的分支条件能够缩短到目标位置的距离,则认为该条件分支是关键的。
最终由 file stitcher 在 fragment pool 中检索候选数据块,分别尝试连接到文件输入中,生成多个新的文件输入。
考虑 KEY Idea (2) ,即那些仅当某些数据字段取特定值时才能执行到的分支,利用 selective symbolic execution 从关键分支的否定开始探索 semi-valid file 的局部搜索空间。在探索过程中,integrity check 会被识别和绕过,并在稍后修复潜在的无效文件。
MoWF 的工作流程如下:
初始时,如果没有目标位置,则利用静态分析尝试找出潜在的危险位置;如果没有初始输入种子,则尝试基于输入模型生成一些。
首先从输入种子中选择最接近目标位置的文件,并将其他文件视为捐赠者,由 file cracker 分解为碎片后添加到 fragment pool 中,以用于 file stitcher 的输入生成过程中。
利用前述方法识别出关键的条件分支。对于每个关键分支,利用 file stitcher 来对分支条件取反。
将用户标记为可修改的所有数据字段的值符号化,生成同时包含符号值和具体值的文件输入,交由传统的 white-box fuzzing 执行 selective symbolic execution 。
# Taint-Based White-Box Fuzzing
# ICSE'09 - BuzzFuzz
BuzzFuzz 是(已知)最早的基于污点分析实现的 fuzzer 。
Taxonomy : mutation-based / directed / white-box fuzzing
Tag : taint-based fuzzing
BuzzFuzz 提出了 directed white-box fuzzing ,旨在生成 well-formed 的测试输入,避免因输入格式不合法而无法深度探索程序,更有效地查找安全漏洞。
将给定的一组函数的所有调用视为攻击点,默认使用预设的 library APIs 和 system calls 或人工提供的一组函数。
对于给定的输入和每个对攻击点的调用,通过污点分析获取输入中每个字节与函数调用实参之间的关系,在 fuzzing 时仅对输入中的相关部分进行变异。
对于相关部分的字节,默认的变异策略为使用对应类型的极端值进行替换,例如 int 类型的变量 max/min int ,0/1/-1 等。
BuzzFuzz 的工作流程如下:
首先对被测程序进行插桩,在运行时刻维护一个从每个地址到一组 input bytes 的映射,记录输入中哪些字节的值会影响到当前变量的值。
然后执行被测程序,报告每个攻击点的所有参数的污点信息,并在下一轮变异时仅针对输入的相关部分。
BuzzFuzz 像大多数污点跟踪技术一样不会考虑由控制流和数组访问产生的间接污点关系:例如某部分输入会改变 if 分支的选择,进而影响到对应代码段内各变量的值;例如不会将数组索引的污点信息传播到整个数组;等等。
BuzzFuzz 是 source-level 的插桩和污点分析,需要被测程序的源码。
# S&P'10 - TaintScope
TaintScope 在 BuzzFuzz 的基础上提出了 checksum-aware fuzzing ,旨在生成能通过 checksum/integrity check 的测试输入。
Taxonomy : mutation-based / directed / white-box fuzzing
Tag : taint-based fuzzing
输入中的 checksum 和 normal data 存在特殊的映射关系。过去的 fuzzing 技术都没有明确考虑这一点;而符号执行技术尽管在一定程度上解决了该问题,却并不能准确处理具有复杂校验计算过程的 checksum 。
TaintScope 利用污点分析来检测和绕过 checksum / integrity check ,并结合使用 concolic execution 修复输入中的 checksum 。仅将利用污点分析识别出的相关字段转换为符号值,而将大多数输入保留为具体值,这使得符号执行工具仅需考虑简单的路径约束。
KEY Idea :假设程序中存在特殊的分支谓词,执行 well-formed 的输入时这些分支总是 true/false ,而执行 malformed 的输入时这些分支总是 false/true ,这样的分支谓词很可能对应于某种 checksum / integrity check 。
checksum 通常用于保护输入中相当数量的连续字节的完整性,因此重新计算 checksum 的过程必定会关联输入中相当数量的字节。因此,TaintScope 在条件跳转指令处检查与对应值关联的污点标记数,如果超过一个预设的阈值则将其视为潜在的 checksum / integrity check 。同时,这意味着与其比较的另一个值所关联的污点标记正对应着输入中的 checksum 的位置。
- 这可能产生过多的候选者,需要进一步根据 KEY Idea 的结论进行筛选,即分别使用 well-formed 和 malformed 的输入执行并观察条件跳转情况。此外,checksum / integrity check 通常在程序的最开始,因此筛选后剩下的第一个候选者通常就是目标。
TaintScope 的工作流程如下:
首先使用 well-formed 的输入执行被测程序,进行污点分析,记录输入中每个字节与特定函数调用的实参之间的关系、以及与每个条件跳转指令之间的关系。
根据条件跳转指令的污点信息检测潜在的 checksum / integrity check 。
不考虑 checksum 而仅根据特定函数调用的污点信息生成输入(基本上是 malformed 的),用于执行被测程序,然后根据 Bypass Info 中的规则在 checksum / integrity check 的位置(通过修改
eflags
)改变程序的执行路径,使其通过检查。如果输入导致程序崩溃,则使用 concolic execution 修复输入中的 checksum ,使其能在原始程序中执行相同的路径。
TaintScope 与 BuzzFuzz 一样不考虑由控制流和数组访问产生的间接污点关系。
TaintScope 只需要被测程序的二进制可执行文件,但假设 well-formed 的输入是另外可获取或可构造的。
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01