Reading Papers - Kernel Fuzzing
# Syscall Semantics Exploration
# CCS'17 - IMF
IMF 收集由相同输入驱动内核执行所产生的不同 syscall trace ,尝试从中分析 syscall 之间的依赖关系。
Taxonomy : kernel fuzzing / syscall semantics exploration / fuzzing seed generation
Tag : trace parsing
KEY Idea :在 non-determinism 的影响下,以相同输入驱动内核执行会产生不同的 syscall trace ,但是将这些 trace 结合分析却能推断出 "constant factors" ,即蕴含于其中的 syscall 之间的依赖关系。
可以将系统调用之间的依赖关系划分为 order dependency 和 value dependency 。
IMF 的工作流程如下:
以相同的输入驱动内核执行,收集大量的 syscall trace log 。
对于预设的 ,从所有 log 中提取具有最长公共前缀的 个 log ,记此公共前缀为 。这编码了 order dependency 。
将在所有 个 log 中以相同值出现的输入参数标记为 constant input parameter 。
按序遍历 中的每个 syscall ,如果其参数值曾在先前的 syscall 中出现过(无论是输入参数还是输出返回值),则将其标记为存在依赖关系。这编码了 value dependency 。
这种方式推断出的 value dependency 准确率不足,IMF 以如下方式进行改善:
将 constant input parameter 从数据流中排除;
对 个 log 单独再计算 value dependency 后取其交集。该方法同样源于上述 KEY Idea 。
IMF 最终将推断出的 syscall 依赖关系编码为 AST(称为 API model),参数值直接从 log 中提取相同值。对于既不是 constant 又不存在依赖的参数,随机从 个 log 中选取一个。
# SEC'18 - MoonShine
MoonShine 利用静态分析提取系统调用对 kernel 内部数据结构的读写行为,推断系统调用之间的隐式依赖关系,并据此进行 seed distillation ,以免真实程序生成的 syscall trace 过长而影响了 fuzzing 的效率。
SEC'18 - MoonShine - Optimizing OS Fuzzer Seed Selection with Trace Distillation
Taxonomy : kernel fuzzing / syscall semantics exploration / fuzzing seed generation
Tag : fuzzing seed distillation / trace parsing / static analysis / greedy strategy
仅基于语法规则生成 syscall trace 是困难的:这需要通过建模等方法维护系统调用之间的依赖关系,否则难以保证输入生成的有效性。此外,人工编写 hard-coded rules 是 error-prone 且 not scalable 的。
另一种可行的方法是从真实程序的执行中提取 syscall trace 。然而这些 trace 通常过长且可能包含大量冗余(来自循环结构),直接使用会严重影响 fuzzing 的效率,需要进行 seed distillation 。
- 通用的 test case minimization 方法不适用于 syscall trace ,即便在保证不降低代码覆盖率的条件下进行裁剪,也会严重破坏 syscall 之间的依赖关系,降低 seed 的变异价值,同时裁剪效率大受影响(盲目尝试)。
# MoonShine 处理依赖关系
KEY Idea :利用系统调用之间的依赖关系进行 seed distillation 。在我看来,这是在规避直接生成的困难的同时,既利用已有 seed 来获取依赖关系,又利用依赖关系来改善 seed 。
MoonShine 将系统调用之间的依赖关系划分为两类:
显式依赖 (explicit dependencies) :若 syscall 的返回值被用作 syscall 的输入参数,则称 显式依赖于 (explicitly depends on) 。
隐式依赖 (implicit dependencies) :若 syscall 的执行修改了 kernel 内部的某个共享对象 ,而 syscall 程序代码的控制流上的某个分支表达式又引用了 ,则称 隐式依赖于 (implicitly depends on) 。
显式依赖:
对于显式依赖,MoonShine 直接分析 syscall trace 并构建 dependency graph :
图上包含 result nodes 和 argument nodes 两类节点,维护对应系统调用的 syscall id 及其返回值或参数值(包括数值、类型、语义)。
从 result node 到 argument node 的边表示 的取值依赖于返回了 的系统调用。
每条边都表示了一组显式依赖关系。
隐式依赖:
MoonShine 对 kernel 的每个 syscall 实现进行源码级的控制流分析,推断其对内核对象的读写访问。
简单的控制流分析存在 over-estimate 和 under-estimate 的问题,可以设计 fine-grained 的分析算法来改善这些问题,但会降低分析的性能:
over-estimate :条件分支中对内核对象的访问可能仅限于特定值,例如
if (flag == FLAG_XXX)
,该情况下将对象写入为其它值并不会影响该系统调用的控制流。under-estimate :内核对象可能存在别名,而内核中复杂的指针引用使得一般的分析技术无法保证其分析结果的可靠性。
# Seed Distillation
MoonShine 基于贪心策略的 seed distillation 算法流程如下:
对于给定的 syscall trace ,将其中的所有 syscall 按照各自单独的 edge coverage 从大到小排序。
算法维护所有已选取 syscall 各自单独的 edge coverage 的并集 。
MoonShine 依次选取每个 syscall ,如果 自身单独的 edge coverage 相对于 没有新的覆盖,则将 舍弃,否则计算 的显式依赖和隐式依赖,然后将 及其依赖的变量值和系统调用合并,加入选取集。
在 MoonShine 的依赖关系分析算法中,显式依赖分析过程与隐式依赖分析过程相互调用彼此,这是因为 MoonShine 对 syscall trace 的分析是顺序从前往后的,必须先完成对上游的依赖分析。
- 相互调用不会影响算法的终止性;因为迭代总是会使 seed 扩大规模,最终至少会回到未经 seed distillation 的状态。
# ICSE'22 - Demystifying UD
本文以静态分析结合人工分析的方式 measure 了 state-of-the-art kernel fuzzer 未能解决的 dependency challenges 。
ICSE'22 - Demystifying the Dependency Challenge in Kernel Fuzzing
Taxonomy : kernel fuzzing / syscall semantics exploration / fuzzing effect measurement
Tag : static analysis / manual analysis
定义 unresolved condition (UC) 为被触及但仅被解析为 true/false 其中之一的分支条件,其值无法触发对另一分支的探索。
定义 unresolved dependency (UD) 为涉及读取全局内存的 UC ,也就是说满足该分支条件必须具有特定的内核状态。
定义 write statement (WS) 为涉及写入全局内存的指令,定义 effective write statement (EWS) 为可能将 UD 所引用的全局变量修改为其所需的值的 WS 。因此,UD 具有对一至多个 EWS 的依赖关系,可能是显式或隐式的,定义类似于 SEC'18 - MoonShine 。
本文的 measurement study 旨在回答以下三个问题:
state-of-the-art kernel fuzzer 有多少未覆盖的分支与 UD 有关?
UD 背后的 root cause 是什么,以及此类依赖对于深度探索 kernel 而言是否重要?
我们可以做些什么来解决这些 UD ?
本文设计了用于 measurement study 的 pipeline infrastructure ,由自动化检查组件与必要的人工分析过程共同组成:
首先,使用特定的 fuzzer 对特定的内核模块进行长时间的 fuzzing ,收集代码覆盖信息并据此获得 UC 。
然后,利用静态分析技术来判断每个 UC 是否为 UD ,以及可能影响到每个 UD 的所有 WS 。
其一是静态污点分析:初始时将所有全局变量设为 tainted ,然后将被污染且未曾被双向评估的控制流汇点标记为 UD 。
其二是静态别名分析:搜索可能写入 UD 中的全局变量的指令。
最后,人工分析每个 WS 是否为 EWS ,并分析未能触发 EWS(从而未能解析 UD)的原因。
- 如果写入的值是静态可确定的(例如常数),则静态分析可以解决;除此以外的部分都只能人工评判。
本文的实验内容非常多(事实上就是本文的主体核心);实验结果详见论文原文。
# ATC'22 - KSG
KSG 利用动态分析技术提取 syscall 的 submodule entries ,收集相应路径上的输入类型和取值范围约束,并据此生成 syscall specifications 。
Taxonomy : kernel fuzzing / driver fuzzing / syscall semantics exploration / fuzzing seed generation
Tag : fuzzing seed distillation / trace parsing / static analysis / greedy strategy
;
# Hybrid Fuzzing
# NDSS'20 - HFL
HFL 尝试解决了在 kernel 上进行 fuzzing 或 symbolic execution 所面临的三类技术挑战,成功将 hybrid fuzzing 实际应用于 kernel 。
Taxonomy : kernel fuzzing / hybrid fuzzing
Taxonomy : generation-based / coverage-guided / specification-based / hybrid fuzzing
Tag : symbolic execution
本文总结了在 kernel 上进行 fuzzing 或 symbolic execution 所面临的三类技术挑战:
TODO. challenge 2 should be thought more: how did related fuzzers (IMF, MoonShine) solve this problem?
Solution for Challenge 1.
对于(我们感兴趣的)间接控制流,HFL 实现了一个 offline translator 将其转换为等价的直接控制流:
首先进行 context-insensitive, flow-insensitive, field-sensitive 的过程间数据流分析,找到对系统调用参数有依赖的间接控制流(?this is because we are not interested in control transfer patterns, which are not controllable by syscall parameter mutation)。
对于过滤后的每个函数指针表,以类似于 loop unrolling 的方式将其展开为 if/else 分支序列。
// before translation
ucma_function_pointer_t ucma_table[] = {
[RDMA_CREATE_ID] = ucma_create_id,
[RDMA_DESTROY_ID] = ucma_destroy_id,
...
}
ret = ucma_table[hdr.cmd](...);
// after translation
if (hdr.cmd == RDMA_CREATE_ID) {
ret = ucma_create_id(...);
} else if (hdr.cmd == RDMA_DESTROY_ID) {
ret = ucma_destroy_id(...);
} else ...
Solution for Challenge 2.
对于依赖于特定系统状态的情况,
HFL 首先对 kernel 进行过程间指针分析以获取一系列的 candidate dependency pairs ,这指的是分别读/写同一地址的两个内存访问指令。随后开始执行 concolic execution :
为减少误报,HFL 在 concolic execution (?) 执行到 candidate dependency pair 时(无论二者顺序)检查其是否真的访问了同一地址,过滤出 true dependency pairs 。
HFL 基于 true dependency pairs 推断依赖关系:执行写操作的系统调用应当发生在执行读操作的系统调用之前,因为后者所需的值可能需要由前者准备好。
HFL 实时地将 concolic engine 推断出的依赖关系传递给 fuzzer ,以用于后续的输入生成过程。
Solution for Challenge 3.
对于具有结构嵌套的系统调用参数,HFL 结合 kernel-specific knowledge 利用 concolic execution 分析参数结构:
HFL 考虑 kernel 中的数据传输函数(例如
copy_to_user
,copy_from_user
等)的 callsites ,以及前文所述的结构嵌套参数的常见形式。HFL 运行已有 workload ,利用 concolic execution 传递污点信息,分析指针指向以及嵌套数据长度,构建出参数的具体内存结构,在 fuzzing 过程中将其用作 syscall interface 的一部分。
# Concurrency
详见 Kernel Testing / Kernel Concurrency 。
- S&P'19 - Razzer
- S&P'20 - Krace
- S&P'23 - SegFuzz
# Driver Fuzzing
# CCS'17 - DIFUZE
DIFUZE 利用静态分析技术。本文亦是我已知最早成体系的 interface-aware driver fuzzing 工作。
CCS'17 - DIFUZE - Interface Aware Fuzzing for Kernel Drivers
Taxonomy : kernel fuzzing / driver fuzzing / complex interface mining
Tag : static analysis
# SEC'22 - StateFuzz
StateFuzz 将 state-aware fuzzing 的思想引入 driver fuzzing ,基于若干 insight 对 driver 的程序状态进行建模,利用静态分析技术识别相关变量,并设计对应的 feedback 来指导 fuzzing 过程。
SEC'22 - StateFuzz - System Call-Based State-Aware Linux Driver Fuzzing
Taxonomy : kernel fuzzing / driver fuzzing
Tag : state-aware fuzzing / static analysis / static symbolic execution
# StateFuzz 建模程序状态
作者人工调查了一些开源的 state-rich programs 中对程序状态的定义,证实了用变量来存储程序状态是常见的行为。
基于对 kernel 以及 driver 代码实现的理解,作者认为 driver 中用于表示程序状态的变量具有以下特征,并称具备这些特征的变量为 state-variable :
具有很长的 lifetime(例如是全局变量),以具备跨越不同的程序状态来维护状态信息的能力。
可以被用户的行为(例如通过系统调用)所修改。
能够(直接或间接地)影响程序的控制流,或影响程序中用于共享内存访问的指针。
会被不同的程序行为(例如 driver 中两个不同的 ioctl handler)共享读写。
一方面,满足条件的 state-variable 数量仍然很大;受到传统 coverage-guided fuzzer 通常仅追踪 edge coverage(两个 relevant basic block 的组合)而不是 path coverage(所有 basic block 的组合)的启发,StateFuzz 仅考虑 relevant state-variable pairs 作为程序状态的表示。
若程序中存在控制流或共享内存访问指针,两个 state-variable 都能直接或间接地影响到,则称二者是 relevant state-variable 。
作者运行 48h 实验将 1/2/3/4 个 state-variable 的组合作为程序状态的表示来指导 fuzzing ,结果表明 2/pair 的方案具有最高的 code coverage 和 value range coverage 。
另一方面,每个 state-variable 的值域都很大(例如 ),但其实际取值范围却可能很小(通常是少数离散值、或是小得多的值域);StateFuzz 将 state-variable 的值域划分为几个子域(称为 value range),在 fuzzing 时仅追踪每个 value range 是否被命中。类似地,StateFuzz 仅考虑 relevant state-variable pair 对应的 value range pair 。
此外,基于常规的测试思路,StateFuzz 还追踪每个 state-variable 的极值作为 value range 的补充;当 state-variable 的新值突破了已命中值域的范围,则 StateFuzz 认为发现了新的程序状态。
# StateFuzz 识别程序状态
StateFuzz 依据上一节所述的特征,利用静态分析技术来识别 state-variable ;随后,StateFuzz 对源代码的 AST 进行静态符号执行:
推断每个 state-variable 的取值范围;
将探索过程中同时出现在一个 path constraint 内的 state-variable 组合地标记为 relevant state-variable pair ;
探索得到的 path constraint 同样隐含了对 value range 的合理划分。
为避免路径爆炸,StateFuzz 仅在单文件内(即 intra-module)进行静态符号执行。
# StateFuzz 工作流程
StateFuzz 将 value range 和极值纳入 feedback loop 中,与 code coverage 共同指导 fuzzing 过程;任何一项的突破都会将当前输入标记为值得进一步探索。
# ISSTA'22 - PrIntFuzz
PrIntFuzz
Taxonomy : kernel fuzzing / driver fuzzing
Tag : static analysis / virtual device simulation
;
# Uncategorized (to-be-reread)
# SOSP'21 - HEALER
Key Idea :考虑系统调用之间的 influence relation ,即一个 syscall 的执行是否会影响后续 syscall 的执行行为,并利用 influence relation 实现 guided fuzzing 。
HEALER 为每个系统调用序列 构建一个 的布尔矩阵, 表示 是否执行会改变 的 execution trace 。
HEALER 从两方面“学习”出 influence relation 矩阵:
static learning :若 的返回值类型和 的参数类型是 compatible 的,则令 。
dynamic learning :首先在 coverage 不变的前提下尽可能将系统调用序列最小化,然后对每个 ,观察在跳过 的情况下 的 coverage 是否变化。只考虑直接后继的原因是避免将间接影响纳入 influence relation 中。
在 fuzzing 过程的前期,influence relation 还未包含足够的信息,不具有指导意义,因此会更多地随机选择 syscall ,此概率随迭代次数的增加而逐渐减小。
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01