Constraint-guided Directed Greyb

2021-10-06 本文已影响0人佩玖吟

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

基本块距离

两个基本块间的最小距离
$d(B_1,B_2)=\left\{ \begin{aligned} 0& & if\space B_1=B_2 \\ min(d(B_s,B_2)+1),\forall B_s & & if\space B_1 \leadsto B_2 \\ \infin & & else \end{aligned} \right.$
$B_s$ 是 $B_1$ 的后继节点，如果 $B_1$ 包含 call 指令，也可以为调用的基本块

目标点距离

当前基本块到目标位置的基本块距离，因为目标点的执行是有顺序的，所以我们不需要使用调和平均来平衡距离
$D_{TARGET}^n=d(B^n,B^*)$

Data Condition Distance

单个数据条件的距离

image-20211004132510165.png

如果比较为 true， $\hat{d}_□(\vec{n})=0$ ， $□$ 表示比较符号，如果 $\vec{n}$ 中有整数未定义，说明前置条件未执行到，距离为 $\infin$

给定数据条件 $Q$ ，则数据条件的距离
$\hat{d}^n(Q)=min(\hat{d}_□(\vec{n})),\forall \hat{n} \in Var^n(Q)$
$Var^n(Q)$ 为执行到 $B^n$ 所捕获到的变量， $□$ 表示数据条件 $Q$ 的比较操作，基本上 $\hat{d}^n(Q)$ 等于到 $B^n$ 捕获的所有变量的最小距离，如果有变量未捕获到， $\hat{d}^n(Q)$ 为 $\infin$ 。

多个数据条件的距离

$\hat{Q}=[Q_1,Q_2,...]$ 为一系列数据条件， $\rho$ 为第一个未满足的数据条件的下标，数据条件的距离为
$D_{DATA}^n=c_{data}·N_{unsat}+min(c_{data},\hat{d}^n(Q_{\rho}))$
$N_{unsat}=N(\hat{Q})-\rho$ 为未满足的数据条件的数量， $c_{data}$ 是单个数据条件的最大距离

Constraint distance

单个约束的距离是目标位置距离和数据条件距离之和
$D^n=D_{TARGET}^n+D_{DATA}^n$

Before the target site

$D^n=d(B^n, B^*)+c_{data}·N(\vec{Q})$

在到达目标位置前，到达目标位置的距离为 $d(B^n, B^*)$ ，同时，数据条件距离为最大值，因为到达目标位置前，并不是所有引用的变量都被捕获。
At the target site

$D^n=0+D_{DATA}^n$

到达目标位置，约束距离只由数据条件距离决定。
When constraint satisfied

$D^n = 0$

Total distance

总距离
$\pmb{D}^n=c_{con}·(N(\vec{B^*})-\tau^n)+min(c_{con},D_{\tau^n}^n)$
$\tau^n$ 是第一个未满足的约束的下标， $c_{con}$ 是单个约束的最大距离， $N(\vec{B^*})$ 是目标位置的数目

When no constrain satisfied

$\pmb{D}^n=c_{con}·(N(\vec{B^*})-1)+min(c_{con},D_1^n)$
When last constraint remains

$\pmb{D}^n=min(c_{con}, D_M^n)$
When all constraints satisfied

$\pmb{D}^n=0$

种子距离为执行过程中的最小距离
$\pmb{D}(s)=min(\pmb{D}^n),\forall n$

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> 设置为改变的条件， $<data\_cond>=(C_{pre}\&\&!C_{post})||(C_{post}\&\&!C_{pre})$
C3

如果替换了变量，将 <target_site> 设置为替换的变量，<data_cond> 测试补丁前后的变量的值是否相同
C4

如果前面的条件都不满足，返回到 data-condition-free constraint，将 <target_site> 设置为所有更改的程序位置

如果更改的程序位置不止一个，向每个更改位置插入一个 sentinel 函数，绑定到一个目标站点。

Seed scoring

首先给距离短的种子更高的评分，同时，一些距离为局部最小值不能进一步缩小，为了避免这种情况，CAFL 根据模糊测试的次数以及 stuck depth（种子不能减少到比父种子更少距离的深度）来指数级缩小种子分数。
$\pmb{S}(s)=(\pmb{D}_{max}-\pmb{D}(s))·pow(c_{fuzz},NumFuzzed(s))·pow(c_{stuck,StuckDepth(s)})$
$\pmb{D}_{max}=c_{con}·N(\vec{B}^*)$ 是最大的距离， $c_{fuzz}$ 和 $c_{stuck}$ 是 scale-down factors，设为 0.95 和 0.85