FixReverter:为 fuzz benchmark 插入真实 bug 的方法

文章目录

要实现一个 fuzzing benchmark,必不可少的一步是制作 bug 数据集,以往的工作要么耗费人力使用真实 CVE,要么牺牲现实性自动插入人工合成的 bug,而我们之前讲过的 Magma 虽然使用了 forward-porting 来将真实 bug 插入到软件的最新版本,但获得 ground-truth 仍离不开大量人力。今天推荐的文章 FixReverter 则独具慧眼地从大量 CVE 的修复中总结出三种 bugfix pattern,通过语法匹配来自动识别程序中的 bugfix ,逆转这些 bugfix 即可自动插入具有现实性的 bug。我们在一个月前就注意到了这个工作,但文章直到上周 USENIX Security 2022 会议进行时才公布,还获得了 distinguished paper award。

背景动机

和 Magma 一样,为了证明自己发明新 benchmark 的必要性和优越性,作者上来先规定了四个小目标(Goal):

  • 目标程序应当和现实世界相关
  • 程序中应当包含现实 bug
  • 要能清晰地判定 bug 触发以避免去重(deduplication)的问题
  • benchmark 要能抵抗过拟合(overfitting)

实际上这几个目标和 Magma 所提出的理想 benchmark 属性有所重合,Magma 中定义的 diversity 已包含了前两个目标强调的现实性,第三个目标则体现为 Magma 中的 verifiablity,这些目标已经被 Magma 用来对 FuzzBench, UniFuzz, CGC 等 benchmark 进行了批判。而最后一个目标防止 overfitting 其实 Magma 作者也有考虑,其在论文中表示这是 static benchmark 的通病,不过 Magma 采用 forward-porting 快速更新目标程序可以一定程度上减缓这个问题。

FixReverter 就利用抗过拟合这一点证明了自己工作的价值:自动注入 bug 来构建的 benchmark 可以抵御 overfitting,而且和 LAVA 这种注入合成 bug 的方法不同,FixReverter 通过观察大量 bugfix 归纳出了三种常见修复模式(bugfix pattern),可以通过自动匹配并逆转程序中的修复模式来达到注入现实 bug 的效果,作者还基于 FixReverter 开发了 RevBugBench,并集成到 FuzzBench 中对 5 种 fuzzer 进行了评测。

Bugfix Pattern

通过观察六个开源软件和 Magma 数据集中一共 814 个 CVE,作者最终使用了 170 个 CVE 匹配出三种通用的修复模式,即 conditional-abort (ABORT), conditional-execute (EXEC) 和 conditional-assign (ASSIGN)。

ABORT 就是在下游代码解引用(dereference)某一变量之前检查其是否满足某一不变式(invariant),若不满足则直接跳出控制流,如下图就是 ABORT 模式修复空指针解引用的一个例子:

EXEC 就是在现有条件语句里再加上一个布尔表达式来检查条件体里被解引用的变量是否满足某一不变式,这样的修复使 true 分支的条件更为严格,如下图就是 EXEC 模式修复空指针引用的一个例子:

ASSIGN 就是在下游代码解引用某一变量之前加上一个 if 语句给变量赋新值,如下图就是 ASSIGN 模式修复越界写错误的一个例子:

这三种模式都和条件语句相关,解引用代码所处的位置可能在条件表达式内或是随后的程序中,这影响了不同 pattern 所适用的语义条件(semantic condition)。

FixReverter

整体架构如下图所示:

首先用上下文无关文法(context-free grammar, CFG)定义了下图所示的修复模式和条件表达式:

在这些密密麻麻的语法中,有一些终结符(terminal)代表 tracer,用来识别被解引用的变量。

FixReverter 用 Clang LibTool 实现了语法匹配器(syntax matcher)来读入上面提到的这些语法文件,将其转化为状态机,然后以访问者模式遍历 Clang AST,在遇到的每个语句中寻找 token 并喂给状态机来匹配定义的 pattern,收集到的 token 会被放入 JSON 文件中以供后续阶段使用。

FixReverter 的静态可达性和依赖分析(static reachability & dependence analysis)会收集 syntax matcher 输出的 tracer,判断其是否在给定的入点可达,以及随后的解引用是否依赖于 tracer。从污点分析的角度看,tracer 就是 source,随后的解引用是 sink,比如读写 traced pointer。当 bugfix 被逆转,程序直接执行到 sink 处就可能触发 bug。

静态分析的具体实现基于 Phasar 框架,并扩展了其现有的 IFDSTaintAnalysis 模块,解决了其中一些问题,但仍受限于其 unsound 的控制流分析,可能会导致漏报。

FixReverter 的 bug 注入器(injecter)基于 Clang LibTool 实现,注入的代码能够区分 fuzz 执行中 not reached, reached, trigger 的三种状态,这部分和 Magma 类似,通过插入预处理宏来适应不同的场景。如下图所示,当 FRCOV 宏未定义时,原本的 ABORT 模式被替换为 if(0) continue,没有引入新的分支所以不会让控制流敏感的 fuzzer 产生 bias。而当定义了 FRCOV 宏之后,可以启用额外的逻辑来检查是否满足 trigger 条件,并和 reach 区分,用于之后的 traige 过程。此外,单个 injection 是否被开启也可以通过环境变量控制,最终会影响下图中 injectFlag[529] 的值。

当然这样注入的 bug 可能有一些质量并不高,RixReverter 会用 naive bug filter 筛除掉,具体来说就是导致程序自带单元测试失败,或是用 fuzz 的初始输入就能触发的 bug 会被丢弃。

当 fuzzer 导致程序产生 crash,作者还希望 FixReverter 报告原因,这并没有看上去那么简单,因为一个条件被触发并不意味着 dependent variable 一定(must)会被解引用,而只是能够(could)。运行单个输入可能触发好几个 injection,所以需要一个诊断(triage)的过程来判断哪些是产生 crash 的必要 bug,最终区分如下两类原因:

  • 当程序输入 $I$ 在注入单个 bug(假设为 $A$ )就足以导致 crash 时,认为是触发 $A$ 是 individual cause
  • 当程序输入只有在注入多个 bug(假设为 $A$, $B$)才导致 crash 时,认为触发原因是 combination of $A$ and $B$

Bug triage 的算法如下所示,就是先找 invidudual causes 再找 combination causes。

RevBugBench

有了 FixReverter 这个 bug 注入器后就能做一个 benchmark,作者共选择了 10 个目标程序,其中 8 个来自 FuzzBench,另外 2 个是 binutils 中常用的两个工具。如下表所示,经过语法匹配、静态分析和最终筛选之后一共注入了超过 7900 个 bug,静态分析丢弃了最初语法匹配所得 bug 中的 71% ,而 naive bug filter 只筛除了 102 个 bug。

FuzzBench 是一个集成了许多 fuzzer 的 benchmark 服务,但其主要关注的是代码覆盖率,用 stack trace 来区分 bug 的方式并不可靠,作者把 RevBugBench 集成到 FuzzBench 以对不同 fuzzer 探索现实应用中 bug 的能力做大规模且可复现的评估。具体来说扩展了 FuzzBench 的三个关键组件,即 benchmarks (target programs), measurer (on-the-fly result analyzer) 和 reporter (statistical analysis of results)。

最终在 AFL, libFuzzer, AFL++, Eclipser 和 FairFuzz 这 5 个 fuzzer 上的实验结果如下表所示,其中 MetaFuzzer 是所有 fuzzer 发现 bug 之和,代表了结果的上界。

不同 fuzzer 所发现 individual bugs 的文氏图如下:

这几个 fuzzer 之间比较的结果和 Magma 的结论一样,AFL++ 综合表现最好。不过更重要的是用 fuzz 的结果来评估 FixReverter 和 RevBugBench 本身的作用,作者考虑如下三个问题:

  • FixReverter 是否注入了 fuzzer 能发现的 bug?由于静态分析天然具有 conservative 和 overapproximate 的特性,注入的数千个 bug 中只触发了两百个 individual cause,但从不同 fuzzer 得到的结果看还是有大量 bug 能被发现。
  • FixReverter 是否能注入难以发现的 bug?根据上面的文氏图,只有约 40% 的 individual bug 能被所有 fuzzer 检测,约 19% 的 individual 只会被一种 fuzzer 检测,这说明 FixReverter 注入的 bug 不会对单个 fuzzer 过拟合。
  • RevBugBench 中的 fuzzer 是否能检测 combination causes?从表中结果来看,所有程序都能检测到 combination causes,不同 fuzzer 的相对性能在使用 individual causes 或 all causes 作为指标时表现相一致。

总结展望

作者通过观察 CVE 中的 bugfix pattern,运用语法匹配和静态分析来查找并逆转这些 pattern,提出了 FixReverter 这一自动注入 bug 的框架,让 benchmark 随着新插入的 bug 和新的 pattern 不断进化。

作者表示后续会在静态分析上进行改进,让结果更加 sound。还有就是扩展新的 bugfix pattern,作者计划引入新的 pattern 不涉及控制流变化,而是定义新的 semantic condition。

此外,作者在社交媒体上表示除了已经释出的 artifact,月末还将发布论文附录来介绍 artifacts,大家可以持续关注!

论文地址:https://www.usenix.org/system/files/sec22-zhang-zenong.pdf

Artifact 地址:https://zenodo.org/record/6831960

评论正在加载中...如果评论较长时间无法加载,你可以 搜索对应的 issue 或者 新建一个 issue