Abstract
定向灰盒测试驱动种子到达目标位置，用于 crash reproduction 和 proof-of-concept generation。但是目前 DGF 因为没有考虑有序的目标点和数据条件，要经历很长时间的模糊测试。
本文提出了 constraint-guided DGF，满足一系列约束而不仅仅是到达目标点，将约束定义为目标点和数据条件的组合，并按指定顺序驱动种子满足约束。
Introduction
DGF 需要花费很长时间来识别目标位置，主要因为以下两个限制：
-
DGF 假设目标点是相互独立的，不考虑目标点之间的顺序依赖
如 UAF 漏洞，只有先 free 再 use 才能触发
-
DGF 不考虑目标位置的数据条件，并且忽略满足这些条件的种子
如缓存溢出，接近边界的种子要更容易触发漏洞；基于补丁的 PoC 生成，其中更改的数据条件可能涉及固定崩溃的原因。因为 DGF 不知道数据条件，使用基于控制流的距离可能会对种子进行错误的优先级排序，从而影响种子调度。
本文提出了 CDGF，目标是满足一系列约束条件，并按顺序对更好地满足约束条件地种子进行优先级排序。约束由单个目标位置和可选的多个数据条件组成，当程序到达目标位置并满足目标位置的数据条件时，视为满足约束。当存在多个约束时，约束必须按指定顺序满足。
为了衡量种子满足约束的程度，CDGF 基于约束的距离定义了种子距离。另外，本文介绍了从附加信息源（即来自内存错误检测器的崩溃转储和来自补丁的变更日志）自动生成约束的算法。
Contributions:
- 本文提出了 CDGF，使用有序的目标位置和数据条件来增强传统的 DGF
- 本文使用给定的附加信息源自动生成约束，总共支持七种崩溃类型和四种更改日志类型
- 使用 CDGF 实现了 CAFL
Background and Motivation
Directed Greybox Fuzzing
距离计算使用调和平均
Usage Example
-
Static Analyzer Verification
静态分析对潜在漏洞的诊断，包括漏洞位置和假定的数据条件，存在误报率，所以可以通过将目标位置设置为漏洞位置，利用 DGF 进行验证。
-
Crash Reproduction
一个 Poc 输入通过不能保证漏洞被修复，将漏洞位置和相关位置设置为目标位置。
-
PoC Generation
攻击者的主要目标是具有未修补漏洞的系统，并且补丁已经发布。攻击者可以分析补丁更改日志，利用 DGF 为未打补丁的系统生成 PoC 输入。
Limitation
-
Independent Target Sites
认为目标位置是独立的，不考虑到达漏洞位置需要先到达的位置
-
No Data Condition
Requirements
- Ordered target sites
- Data conditions
Constraint-guided DGF
Overview
CDGF 为以下两种情况的种子赋予更短的距离：
- 满足更多的约束
- 比另一个种子更接近于第一个未满足的约束
单个约束的距离为到目标位置（DGF-style）和数据条件（Angora-style）的距离之和。如果前面的约束未满足，距离定为最大值。
Constraints
Definition
-
Variable capturing
到达目标位置后，捕获目标位置用到的变量
-
Data condition
数据条件是捕获到的变量之间的布尔表达式，变量可以是先前捕获的
-
Orderedness
Distance of Constraints
Target Site Distance
基本块距离
两个基本块间的最小距离
是
的后继节点，如果
包含 call 指令，也可以为调用的基本块
目标点距离
当前基本块到目标位置的基本块距离，因为目标点的执行是有顺序的，所以我们不需要使用调和平均来平衡距离
Data Condition Distance
单个数据条件的距离
image-20211004132510165.png
如果比较为 true，，
表示比较符号，如果
中有整数未定义，说明前置条件未执行到，距离为
给定数据条件 ，则数据条件的距离
为执行到
所捕获到的变量，
表示数据条件
的比较操作，基本上
等于到
捕获的所有变量的最小距离，如果有变量未捕获到，
为
。
多个数据条件的距离
为一系列数据条件，
为第一个未满足的数据条件的下标，数据条件的距离为
为未满足的数据条件的数量，
是单个数据条件的最大距离
Constraint distance
单个约束的距离是目标位置距离和数据条件距离之和
-
Before the target site
在到达目标位置前，到达目标位置的距离为
，同时，数据条件距离为最大值，因为到达目标位置前，并不是所有引用的变量都被捕获。
-
At the target site
到达目标位置，约束距离只由数据条件距离决定。
-
When constraint satisfied
Total distance
总距离
是第一个未满足的约束的下标，
是单个约束的最大距离，
是目标位置的数目
-
When no constrain satisfied
-
When last constraint remains
-
When all constraints satisfied
种子距离为执行过程中的最小距离
Constraint Generation
Crash Dump
崩溃转出的约束生成是指选择适当模板的错误类型。本文合成了三个模板，支持七种错误类型。
-
nT template
多个目标位置，处理 use-after-free、double-free、use-of-uninitialized-value
image-20211004153444589.png
-
Avoiding wrapper functions
为了使目标位置更具代表性，本文检查 caller 是否包含 "alloc"、"free"、"mem" 之类的关键字来避免选择 memory wrappers
-
Constraint description
-
Corresponding bug types
-
2T+D template
两个目标位置和数据条件，处理 stack-buffer-overflow、heap-buffer-overflow
image-20211004153512832.png
-
1T+D template
一个目标位置和数据条件，处理 assertion-failure 和 divide-by-zero
image-20211004153528996.png
Patch Changelog
和 1T+D 类似，<target_site> 表示补丁修改的位置，<data_cond> 表示变更的数据条件。
为了找到合适的约束，patch changelog 和预定义的案例相匹配，早起的案例可能更直接的指向 bug 的原因，下面介绍了案例匹配：
-
C1
如果引入新的 exception check，将 <target_site> 设置为源位置，<data_cond> 设置为引入的 exception conditions，假设导致 return 或带有 "throw" 或 "error" 关键字的条件 suggest exception checks
-
C2
如果分支条件改变了，将 <target_site> 设置为改变的条件，
-
C3
如果替换了变量，将 <target_site> 设置为替换的变量，<data_cond> 测试补丁前后的变量的值是否相同
-
C4
如果前面的条件都不满足，返回到 data-condition-free constraint，将 <target_site> 设置为所有更改的程序位置
如果更改的程序位置不止一个，向每个更改位置插入一个 sentinel 函数，绑定到一个目标站点。
Seed scoring
首先给距离短的种子更高的评分，同时，一些距离为局部最小值不能进一步缩小，为了避免这种情况，CAFL 根据模糊测试的次数以及 stuck depth（种子不能减少到比父种子更少距离的深度）来指数级缩小种子分数。
是最大的距离，
和
是 scale-down factors，设为 0.95 和 0.85
网友评论