🤔



# Critical Code Guided Directed Greybox Fuzzing for Commits



## 作者

- Yi Xiang - 浙江大学、浙江大学 NGICS 平台

- Xuhong Zhang - 浙江大学博导、江淮前沿技术协同创新中心 - 可信计算、
- Peiyu Liu - 浙江大学、浙江大学 NGICS 平台 - 
- Shouling Ji - 浙江大学博导 - 机器学习、模糊测试
- …

- Wenhai Wang - 浙江大学博导、浙江大学 NGICS 平台 - 控制系统安全



## 传统做法

针对与新提交内容的Fuzz

- 现有的定向模糊器主要集中于达到单一目标，而忽视了对其他受影响代码的多样化探索。因此，它们可能会忽略在远离变更站点的地方崩溃的错误
- 在多目标场景中缺乏直接性



现有方法无法解决的问题

- 如何快速、彻底地测试受影响的代码？到达目标后，如何探索受影响代码的不同程序状态?
- 如何以智能和轻量级的方式处理多个目标的定向模糊测试?

## 作者的方案

**Key insight: 在生成可探索不同程序状态的输入的同时，保留关键代码的执行**



作者细分出来两种代码

- 路径前缀代码(path-prefix Code): 能影响变化点的控制流的代码
  - 罕见的路径前缀代码: 表示通向目标的新路径

- 数据后缀代码(data-suffix Code): 与变化点中使用的关键变量有数据依赖关系的代码
  - 罕见的数据后缀代码: 表示可能影响受影响代码的新数据值

在变异种子时，会检查它是否执行了任何关键代码。如果发现了关键代码，我们就会为种子生成一个突变掩码，并应用细粒度突变来维持其在生成输入中的执行。否则，我们会采用粗粒度变异来增强种子的多样性。

在模糊处理过程中，我们会根据种子是否到达目标来选择目标边缘。如果种子没有到达目标，我们就从种子执行的路径前缀代码中选择离目标 "最近 "的边作为目标边。通过只改变不偏离目标边的输入字节，我们会逐渐生成更接近目标的输入。如果种子已经达到目标，我们会从路径前缀和数据后缀中选择最罕见的执行边作为目标边，对受影响的代码进行全面测试。



> Q1: 如何自动化定义关键代码，如何轻量级观察是否执行了关键代码？
>
> 通过ICFG反向查找所有从起始到达目标点的路径将其作为路径前缀代码
>
> 通过SVFG也就是前向数据流分析来定位相关数据流依赖的代码作为数据后缀代码

> Q5: ICFG识别完整性问题?开销问题?
>
> 

### 整体架构

![](https://blogdownload.oss-cn-hangzhou.aliyuncs.com/202405282259585.png)



#### 目标合并

作者的目标主要是新commit上去的代码，一般来说一个commit包含的功能的patch是相似的。

> 说人话就是多个commit可能是与同一个功能相关的patch，作者提出了一种算法以功能点作为聚类将多个patch点合并

由于一个函数中的变化有很多相似的前提条件，因此我们将同一个函数中的所有变化位点合并为一个。首先构造目标函数的支配树，然后将目标函数中每个初始目标的直接支配树作为该函数的合并目标。



> Q2: 没明白怎么合并目标
>
> 简单来说就是将所有存在更改的站点打上污染tag，然后生成支配树如果这些tag在一颗支配树中就认为是同一个目标，对其进行合并



#### 距离算法

$Definition$: 包含合并目标的基本块称为目标基本块$T_b$​

$Definition$: 一个基本块m到每个目标块$T_b$的距离为$d_b(m,T_b)$​

$Definition$: 两个基本块$m_1$和$m_2$之间的距离$d_b(m_1,m_2)$为两个基本块之间的最短路径所包含的基本块数量

$Definition$: 对于一个边$e_{ij}$来说，其中$i、j$分别表示边的起点和终点。将边$e_{ij}$到基本块$T_b$的距离$d_e(e,T_b)$定义为 $d_e(e,T_b)=d_b(j,T_b)$ 

$Definition$: 令$\varphi(s)$为种子$s$的执行路径，对于每个目标$T_b$我们定义种子$s$的输入距离$d_s(s,T_b)$为$d_s(s,T_b)=\frac{\sum_{m\in\varphi(s)}d_b(m,T_b)}{|\varphi(s)|}$ 其中$\varphi(s)=\{m \in \phi(s) and d_b(m,T_b) \ne NaN \}$



> Q3: 这个距离定义和AFLGO有什么区别？
>
> 没有区别

#### 关键代码识别

- 路径前缀代码: 指所有能够导致目标代码执行的代码。它包括ICFG中与目标代码直接或间接相连的代码块。

- 数据后缀代码: 包括依赖于初始目标中使用关键变量的代码



![](https://blogdownload.oss-cn-hangzhou.aliyuncs.com/202406050934133.png)

在此例子中，开发者对第14行也就是基本块g进行了修补将`x=y+5`修补为`x=y-5`，将Patch基本块中被写入的变量作为污染变量，向后传递污染使用被污染变量的基本块并将其作为数据后缀代码。在这个例子中`数据后缀代码为:i、k` 而路径前缀代码比较直接，就是从起点导向目标块的路径，在这个例子中`路径前缀代码为:a、b、e、f`



#### 关键代码导向的模糊测试

针对于定向模糊测试有两个重要的种子生成指标

1. 是否能够到达目标位置
2. 在到达目标位置之后能否保持目标位置的可达性而后继续生成不同的输入

整体WAFLGO的算法大致如下

![](https://blogdownload.oss-cn-hangzhou.aliyuncs.com/202406102114001.png)



**目标达到阶段**

![](https://blogdownload.oss-cn-hangzhou.aliyuncs.com/202406102118429.png)

> 简单来说，就是挑选覆盖到离目标最近的边的种子进行变异，同时在执行过程中记录覆盖次数，当覆盖次数大于阈值时进行回退，继续变异覆盖到除了该边外离目标站点最近的边

> Q4: 这样做的合理性在哪里，和传统的AFLGO基于距离的定向模糊测试有什么区别?
>
> 没有区别，后文作者提到了这种做法跟AFLGO传统的模拟退火算法没啥区别，但是反馈粒度更细。



**综合测试阶段**

在此阶段中主要利用路径前缀代码和数据后缀代码进行多样化变异。

当有测试样例到达目标位置之后仍然会继续根据最近的边进行变异，只有当所有的边覆盖次数都超过阈值时测试会转向数据后缀代码。在此基础上会选定覆盖次数最少得数据后缀代码的边作为目标继续测试。

![](https://blogdownload.oss-cn-hangzhou.aliyuncs.com/202406050934133.png)

在此例中，如果给出一个种子其能够覆盖到$a \rightarrow b \rightarrow e \rightarrow g \rightarrow i \rightarrow j \rightarrow l$，最开始选定的测试边为$e_{eg}$而后是$e_{be}$、$e_{ab}$，当所有的边都到达指定的阈值之后就将$e_{ik}$作为目标边进行Fuzz。



**变异掩码生成**

使用的方法非常简单，就是使用一组预定义好的突变算子逐字节的对种子进行变异，如果变异某字节之后仍然能够到达目标边就将对应字节标记为可变异字节，并且更新掩码。在随后的变异中可变异字节将会以更高的概率被选中进行变异。

> Q5: 这样做如果某个边是依赖于多个字节同时进行变异呢?
>
> 没有影响



#### 种子选择和能量调度

作者首先维护了一个`高优先级队列`，其内部主要保存新触发关键代码的种子，在变异过程中有更高的概率选中高优先级队列中的种子进行变异。

在能量调度方面，在未覆盖目标之前采用的是跟AFLGO一样的模拟退火算法，并且会将更多能量分配给更接近最稀有执行目标的种子。在覆盖目标之后将忽略模拟退火算法而关注数据后缀代码的代码覆盖度，从而会将更多能量分配给覆盖更多数据后缀代码的输入。



### Question

仍然存在调用图识别不全等问题，而且对于如此细粒度的跟踪开销仍然是个巨大的问题。

同时在**目标到达阶段**其实仍然是AFLGO那套东西，模拟退火算法只是粒度更细，真实效果存在疑问。

[Paper] Critical Code Guided Directed Greybox Fuzzing for Commits

🤣



# SDFUZZ: Target States Driven Directed Fuzzing

## 作者



## 传统方案

之前的定向模糊法存在的一个主要问题是，它们通常会探索大量无法触发崩溃的程序代码和路径。在 DGF 的探索阶段，大多数现有方法都遵循 AFLGo 的解决方案，利用覆盖率反馈来扩大对不同代码区域的探索。许多代码区与目标站点无关，也不是到达目标站点所必需的。这些代码区仍在进行不必要的探索。在探索阶段，先前的定向模糊器利用基于控制流图（CFG）和调用图（CG）的距离度量。距离度量没有考虑路径条件，如控制流和数据流条件。因此，由于控制流或数据流条件不可满足而无法在目标站点触发漏洞的执行仍可能获得较短的距离，并被过分看好。这样就会浪费过多的测试工作。

缓解上述问题的解决方案是，首先确定引发崩溃所需的程序代码/路径，然后只对所需的代码/路径进行模糊测试。SieveFuzz 分析程序间控制流图（ICFG）以确定到达目标站点所需的函数，并在执行到非所需函数时终止执行[32]。Beacon 通过后向区间分析计算到达目标站点的先决条件，并提前终止不满足先决条件的执行[14]。SelectFuzz [20] 可静态识别目标站点的控制地数据依赖代码。但是，它们过度估计了允许的程序代码和路径集，大大限制了其性能。这是因为他们的分析是保守的。它们只考虑了控制流的可达性，却没有分析触发漏洞的其他条件，例如目标站点的预期到达顺序[16]。鹰眼[3]和 CAFL [16]在设计距离度量时包含了调用跟踪。但是，它们并没有利用这些代码/路径来排除不需要的代码/路径。



## 作者方案

通过对目标状态的新发现来缓解 DGF 中不必要的探索问题，目标状态包括触发漏洞的目标站点的预期调用轨迹和到达顺序。特别是，DGF 的主要任务，如崩溃再现和漏洞验证，都提供了对漏洞的详细描述，如目标站点位置和相关漏洞信息，如崩溃转储、回溯[10]和源-汇流[35]。目标站点位置描述了漏洞发生的位置；漏洞信息还解释了如何触发漏洞的有趣程序状态（即目标状态）。定向模糊的目标不仅是到达目标站点位置，还包括动态暴露漏洞。受此启发，我们不仅要将模糊测试推向目标站点，还要推向有趣的目标状态。因此，除了排除无法到达目标站点的探索之外，我们还进一步避免了无法到达目标状态的不必要执行。

在运行时，SDFUZZ 会维护运行时程序状态，定期将其与目标状态进行比较，并探测是否存在偏差。在随后执行测试用例时，如果出现无法挽回的偏差，就会立即终止。如果 ICFG 上有程序路径，偏差函数调用有可能更新为目标状态中指定的预期函数调用，则偏差可以恢复。



更新的反馈机制

- SDFUZZ 通过计算模糊试验的最佳运行时程序状态与目标状态的相似度得分，计算新的目标状态反馈。
- SDFUZZ 改进了 DGF 中广泛采用的距离度量。在 CG 中，SDFUZZ 没有使用根据经验配置的常量系数（如 AFLGo 中的 10）作为函数间的程序间距，而是使用了一种新的加权程序间距，它近似于调用方函数调用被调用方函数的几率。

> Q1: 作者是如何定义状态的
>
> 在这项工作中，我们将目标站点的预期调用轨迹和到达顺序定义为目标状态。我们将程序状态（PS）形式化为函数调用的堆栈（调用位置）。程序状态中的每个项目都是函数名和调用位置（(Func, Loc)）的元组。漏洞或错误的目标状态（TS）就是它被触发时的程序状态。要达到目标状态，其中的函数必须以正确的顺序达到或调用。

$Definition\ 1: PS=[(Func_1, Loc_1), (Func_2, Loc_2),...,(Func)n,Loc_n]$

$Definition\ 2: TS_s=[TS_1, TS_2,...,TS_n]$

![](https://blogdownload.oss-cn-hangzhou.aliyuncs.com/202405080917700.png)

 

![](https://blogdownload.oss-cn-hangzhou.aliyuncs.com/202405080918626.png)

针对上述样例可以描述为

![](https://blogdownload.oss-cn-hangzhou.aliyuncs.com/202405080918544.png)



### 整体架构

![](https://blogdownload.oss-cn-hangzhou.aliyuncs.com/202405080923688.png)

1. SDFUZZ 首先自动提取目标状态，并将其解析为指定格式。
2. SDFUZZ 确定达到目标状态所需的代码，并从模糊测试中删除其他不需要的代码。
3. SDFUZZ 采用两维反馈机制，主动引导测试达到目标状态

> Q2: “一旦 SDFUZZ 发现测试用例的剩余执行无法达到目标状态，它就会提前终止执行，从而提高模糊吞吐量（即单位时间内的执行次数）” 怎么确定?
>
> 其实就是对比程序状态列表，如果程序步入了不在列表中的函数，就检查ICFG查看该函数是否在可能到达目标函数的路径上，如果不在就终止执行。



#### 提取目标状态



##### Vulnerability reports

崩溃转储由漏洞触发时的活动函数调用记录组成，如图 2 所示。每条记录包含函数名称（如 option1）和调用位置（如 file.c:15）。因此，我们首先使用正则表达式搜索漏洞报告中包含此类信息的描述。提取后，我们进一步解析，以确定它们是否符合公式 1 中定义的格式。我们还会根据漏洞类型和描述自动对目标状态进行排序。例如，一个UAF漏洞通常包含多个目标状态。我们将按照free和use地点对目标状态进行排序。

##### Static Analysis Result

SDFUZZ 还能从静态分析结果中自动提取目标状态。由于不同的静态分析工具采用不同的方式来表示其结果，因此自动提取自然必须针对每种静态分析工具进行专门设计。我们目前开发的 SDFUZZ 与一种流行的静态分析工具 SVF [34, 35]相协调。据我们所知，目标状态也可以从其他静态分析工具（如 CodeQL [9] 和 Joern [39]）中提取，只需对结果进行额外的解析即可。运行此类静态分析工具通常需要程序的源代码。



#### Selective Instrumentation

我们的解决方案是有选择性地为代码覆盖率反馈检测所需的代码，而不是直接将其从源代码或可执行文件中删除。我们提出了一种函数级算法（如算法 1 所示）来识别所需的代码。该算法将一组目标状态（TS）和目标程序的 ICFG（ICFG）作为输入。目标状态中出现的函数（即目标状态函数）与漏洞相关，并直接作为所需函数（第 5 行）。此外，这些目标状态函数还可能依赖于其他函数。我们的算法首先会进行程序内反向分析，以确定目标状态函数所依赖的函数（第 6 行）。`如果在具有函数调用位置的基本程序块和目标状态函数的基本程序块之间存在程序内路径，则该函数将被包括在内。`

![](https://blogdownload.oss-cn-hangzhou.aliyuncs.com/202405080940489.png)



#### Early Termination

为了提前终止执行，我们必须预测执行最终能否到达目标状态。这很困难，因为程序状态会在程序执行过程中动态更新，例如通过函数调用和返回。鉴于现代程序的高复杂性，它们所能展现的程序状态空间可能是巨大的。



**Runtime Program State Monitoring.** SDFUZZ 监控运行时的函数调用，并记录函数调用的堆栈。这些函数通过函数调用或返回从堆栈中push或pop。通过函数调用位置，SDFUZZ 可以区分在不同位置调用的相同函数。程序状态跟踪可能会导致状态爆炸[38]，并造成很大的开销。我们只跟踪与目标状态相关的函数的状态，从而缓解了这一问题。特别是，SDFUZZ 只在程序调用或返回目标状态下的函数时更新和检查程序状态，以防提前终止。

**An unrecoverable deviation based solution.** 多目标漏洞的目标状态是函数调用的有序列表数组，每个列表针对一个目标点。因此，我们的算法（如算法 2 所示）将某个时间点的当前程序状态 (PS)、先前达到的目标状态 (reachedTSs)、有序目标状态 (TSs) 和 ICFG 作为输入。它对目标状态进行迭代，以找到在测试用例的模糊测试过程中未达到的第一个目标状态（第 3-6 行）。如果所有目标状态都已达到，算法将直接返回（第 7-8 行）。否则，算法将检查偏差函数调用，尤其是通过根偏差函数检查第一个偏差-根偏差（第 10 行）。根偏差表示程序状态开始偏离未达到的目标状态的位置。这是通过反复比较调用点（第 20-26 行）来找到第一个偏差。

![](https://blogdownload.oss-cn-hangzhou.aliyuncs.com/202405080952720.png)

如果出现任何偏差（第 11 行），我们的算法会根据 ICFG 进一步衡量剩余的执行是否能恢复偏差以达到目标状态（第 12 行）。如果一个执行程序的程序状态出现无法恢复的偏差，就会被立即终止。我们的算法会检查程序的 ICFG，并探测是否存在从根偏差代码位置到目标状态中预期函数调用的程序路径。这样的路径意味着偏差可能会在未来的执行中恢复，因为执行可以从根偏差函数调用返回并运行到预期函数调用。因此，可能恢复偏差的执行不会终止。



### Two-Dimensional Feedback

为了快速将模糊推向目标状态，SDFUZZ 按照目标状态反馈和种子距离这两个属性对语料库中的种子进行排序。一般来说，SDFUZZ 会优先选择目标状态反馈较好、距离较短的种子。它将目标状态反馈作为主要排序属性，将距离作为次要排序属性。原因是目标状态反馈捕捉到的运行时上下文更精确，能更好地帮助接近目标状态。SDFUZZ 还改进了 AFLGo 的能量调度算法，根据二维反馈为种子分配能量。

#### Target State Feedback

找到第一个未达到的目标状态（nextTS）后，SDFUZZ 使用根偏差指数计算相似度得分。如果当前程序状态与第一个未达到的目标状态（nextTS）不完全匹配，SDFUZZ 会首先通过计算匹配偏差 Idx 与其大小之比来衡量当前程序状态与目标状态的匹配程度（第 13 行）。我们的算法还考虑了之前达到的目标状态，并将达到的目标状态的比率和大小相加得出分数。分数会根据目标状态的数量进一步归一化，然后返回。如果当前程序状态与 nextTS 匹配，我们的算法会直接返回已达到目标状态的比例（第 16 行）。由于执行一个测试用例时可能会多次调用该算法，因此我们将最佳得分作为测试用例的结果。



#### Distance Feedback

先前的距离度量并不精确，因为它们对 CG 中的每条边都一视同仁。SDFUZZ 通过精确的边缘权重来减轻不精确性。边缘权重有望反映调用方函数调用被调用方函数的机会。SDFUZZ 根据调用点权重计算边缘权重。

我们将调用方函数调用被调用方函数的调用点权重定义为 `从调用方函数的起点到被调用方函数的调用点的过程内距离（即 AFLGo中最短路径上的基本块距离）`。

由于同一个被调用函数可能有多个调用点，因此程序间边权重是调用方函数$ f_i() $和被调用方函数 $f_j() $之间的最短调用点权重$weight( f_i, f_j)$。

$Weight(f_i,f_j)=\min(d_{f_i}(BB_{f_i-start},BB_{f_j-call-site}))$ 其中$d_{f_i}$是函数$f_i$的程序内距离

$interDistance(f_s,f_e)=\min(\sum_{(fi,f_j) \in path}wegitht(f_i,f_j))$

[Paper] SDFUZZ: Target States Driven Directed Fuzzing

👍



# A Memory Model for Static Analysis of C Programs

## 作者

## 常见的内存模型

### Name Binding Model
内存被看做是"Name-Value"的键值对的形式，在求值和赋值表达式的时候将左侧变量名称绑定到右侧表达式的值上，此内存模型较为常见。但是因为C语言中包含指针，所以不能模拟C语言的语义。

```c
int x, y;
int *p = &x;
x = 3;
*p = 4;
y = x;
```
考虑上例，其中变量$p$是一个指向变量$x$的指针，指针的存在带来了别名问题(Aliasing Problem)。别名问题是指两个或者多个名称可以表示相同的存储位置。我们在修改一个名称的值的时候也应该修改与之关联的所有名称的值，但是在名称绑定模型中并没有探测到所有名称的别名的能力，所以不能模糊C语言的语义。

### Array Simulation Model
`Name Binding Model`最大的问题是没有内存位置的概念，但是C语言中的指针是通过操作内存位置的值来实现的，所以由此提出了`Array Simulation Model`。简单来说该模型将所有的内存视为一个数组，如果在一个数组中分配所有的变量，那么所有针对变量的操作都可以转化成为对于一个数组元素的操作，同时该模型通过将数组元素的索引和变量内存位置的对应引入了内存位置的概念。

上述例子可以使用`Array Simulation Model`进行转化
```c
Assume mem[] is the memory simulation array.
Memory allocation:
x: mem[1], y: mem[2], p: mem[3]
mem[3] = 1; // p = &x; mem[3] is ’p’,
            // 1 is x’s simulation location.
mem[1] = 3; // x = 3;
mem[mem[3]] = 4; // dereference ’*’ means
                 // we have to nest mem[]’s
mem[2] = mem[1]; // y = x;
```

`Array Simulation Model`解决了内存位置的问题，但是要求每个变量都有固定的位置。在现实中我们并不一定能够确定所有的内存对象的具体大小，例如一个变长数组或者一个位置大小的堆块，该模型就无法使用。所以针对这个弊端提出了针对`Array Simulation Model`的改进，其将一个单独的大数组更换为多个小数组，每个内存对象都有一个对应的数组，但是在这种形式下很难表示复合对象，例如
```c
struct s
{
  int d;
} sa[2];
```
如果我们使用单个数组来表示该结构则存在和未改进版本同样的问题，如果使用多个数组则会丢失内存对象之间的层次关系。

## 作者的内存模型



### Region Based Ternary Model
使用两个映射对于内存状态进行建模: 一个变量环境将位置与每个变量关联，一个存储将值和每个位置关联。形式上，作者将变量环境$Env$的映射定义成为

$Env = Var \rightarrow Loc$ , 其中 $Loc$ 是一组位置的集合。

将映射 $store$ 形式化定义为:

$Store = Loc \rightarrow Value$

在此基础上作者定义了一种新的内存位置表示方法$Region$, $Region$是一个抽象的内存块，对应C语言中的左值表达式。根据C语言的标准，$lvalue$表示一个对象类型的表达式。也就是说，一个左值表达式有一个关联的内存对象，所以我们使用一个抽象区域来表示这个内存对象。此外，表示相同内存对象的左值表达式应该具有与之对应的相同区域。

作者定义了几种 $Region$，
- 对于显式声明的变量，作者提供了变量声明标识$VarRegion$。每一个变量都一个唯一对应的$VarRegion$。
    - 如果变量是数组或者结构类型，则其有一个称为$element$或者$field$的子对象，为了表示内存之间的层次结构，引入了子区域的概念，一个区域可以指向另一个区域的子区域。一个Super Region的指针可以指向另外一个Super Region的子区域
- 对于数组元素有$ElementRegion$及其Super Region指针指向其他数组区域。
    - $ElementRegion$由他们的数组区域和索引来标识
- 对于Struct元素有$FieldRegion$及其Super Region指针指向其他Struct区域。
    - $FieldRegion$由他们的结构区域和字段声明来标识
- 针对C语言中的三种存储类: local(stack)、global(static)、dynamically allocated(heap)，也有三种类型的$MemSpaceRegion$与之对应
    - 所有的局部变量都将 $stack MemSpaceRegion$ 作为他们的Super Region
    - 所有的全局变量都将 $static MemSpaceRegion$ 作为他们的Super Region
    - 所有动态分配的对象都将 $heap MemSpaceRegion$ 作为他们的Super Region
- 在静态分析中，有时候会使用符号值。假设函数参数和全局变量在函数的入口处保存符号值，如果符号变量是一个指针则可能指向一个未知的内存块，所以使用 $SymbolicRegion$ 表示符号指针指向的内存块。
    - $SymbolicRegion$由指向他们的符号指针的值来标识。

除了存储类之外，内存对象还有 $extents$ 或者 $size$ 属性。一些对象的 $extents$ 是显式定义的，例如一个字符变量的 $extents$ 是一个字节。但是动态分配对象的 $extents$ 是不确定的。所以我们使用从一个对象关联的 $Region$ 到他的 $extent$ 的映射，即 $Region - extent$ 映射对来记录该信息。

$extent$ 可以有多种形式
- 具体整数值(concreate interger value)
- 符号未知值(symbolic unknown value)

内存的状态由 $Region$ 的绑定来进行建模。绑定通常有两种形式
- 直接绑定(direct binding): 在赋值表达式中，一般都为直接绑定。例如`x = 3;`，我们通过直接绑定将`x`的 $Region$ 与`3`进行绑定。
- 默认绑定(default binding): 默认绑定通常是在 $Super Region$ 上使用，例如`bzero(buf);`，我们可以使用默认绑定将`buf`的 $Region$ 与`0`进行绑定，否则我们需要将`buf`中的每个元素的 $Region$ 与`0`进行绑定，显然开支非常大。

#### Region View

C语言允许指针类型之间进行转换给静态分析工具带来了很大的困难。
```c
void *p = malloc(10);
char *buf1 = (char *) p;
buf1[0] = ’a’;
int *buf2 = (int *) p;
buf2[0] = 0;
char c = buf1[0];
```
这种代码模式在系统程序中相当常见，程序员通常分配一个通用类型的内存块，然后根据需要将其转换成为不同类型。这种使用(滥用)方法，本质是在C语言中可以存在无类型的泛型内存块。在上述的代码中，由$p$指向的内存块就是这样的存在，后面将其转换成为`char *`和`int *`可以理解成为在其上安装了一个 $view$，当他被`buf1`指针操作的时候即被视作是`char`类型，当他被`buf2`操作的时候就被视作是`int`类型。

我们使用从 $Region$ 到 $view$ 的映射来表示一些匿名类型的区域。将一个泛型的内存块强制转换为某种类型相当于向这块内存块添加一个 $view$。我们创建一个匿名类型的区域来表示 $view$，然后在将泛型内存块强制转换到另一个类型的时候，将创建一个新的匿名类型区域来表示这个新的 $view$。

一个 $Region$ 可以同时拥有多个 $view$ 但是同时只能有一个 $view$ 生效。

![](https://blogdownload.oss-cn-hangzhou.aliyuncs.com/20240501230941.png)

在上述例子中，模型的行为表示为，当表达式`buf1[0]='a'`之后`buf[0]`的值为`a`。但是当表达式`buf[2]=0`之后，我们不仅将`buf2[0]`的值设置为`0`，同时还删除了`buf1[0]`的绑定，当`c`被赋值成为`buf1[0]`的时候，我们可以发现`buf1[0]`是一个未定义的值。


#### Simulation of C Semantics

在上述模型的基础上，作者对对其进行了扩充。作者将程序状态(program state)由两个映射进行建模: $Enviroment$(环境)、$Store$(存储)。

作者将 $Enviroment$ 定义成`由表达式到值的映射`

$Env: Expr\rightarrow SVal$ 其中 $Expr$ 是C表达式的一个元素，$SVal$ 是一种抽象值。

作者将 $Store$ 定义为`从Region到Value的映射`

$Store: Region \rightarrow SVal$ 其中 $Region$ 是内存对象的抽象表示。

##### Abstract Value
我们将符号模拟中出现的值分为两类
- 位置相关的 $loc$，$loc$ 表示抽象内存位置，简单来说指针都是 $loc$
- 非位置相关的 $non-loc$，具体整数、符号整数等都是 $non-loc$

##### l-value and r-value
根据C语言中的定义，表达式分为lvalue和rvalue，引用对象的$Expr$是lvalue表达式，其他都是rvalue表达式。我们将表达式的左值定义为预期关联的内存对象的内存位置。如果表达式是左值表达式，则表达式的右值为与内存对象相关联的值；如果表达式不是左值表达式，则表达式的右值表示为语义值。

[Paper] A Memory Model for Static Analysis of C Programs

🤔



# Titan : Efﬁcient Multi-target Directed Greybox Fuzzing

## 作者



## 传统方案

传统定向模糊测试只能针对单一目标，且现有方法没有意识到目标之间的相关性，因此随着目标数量的增加，可能会退化为无定向模糊处理。最终，模糊器无法有效地为多个目标选择种子和生成输入，我们称之为协同无知问题。

现有的定向模糊测试方案通过寻找最接近目标的潜在种子来提高直接性，以及通过拒绝无法达到目标的输入来避免能量浪费。

### 传统的距离算法

- AFLGo：将测试输入到目标基本区块的距离定义为区块 B 与目标之间的平均距离，其中 B 的范围是输入执行路径所到达的区块。
- Hawkeye：通过考虑调用轨迹的相似性来优化距离度量，其直觉是漏洞是由一连串调用指令而非单一程序点触发的。
- CAFL：通过观察到在触发崩溃之前应到达多个前置点来进一步提高度量的精确度。因此，它设置了漏洞崩溃转储中的所有调用点，并要求模糊器按顺序到达这些调用点。
- MC2：将定向模糊转化为蒙特卡洛计数模型，并利用每个分支的执行频率来近似估计达到目标的难度，并优先选择达到目标难度最低的种子。

### 种子剪枝方案

- FuzzGuard：训练了一个分类器作为预测器，以过滤测试输入，从而使达到目标概率较高的输入以较高的优先级执行。
- Beacon：由于重现错误应满足路径条件，因此它以可证明的方式进一步完善了剔除功能。它使用静态分析来推断达到目标的先决条件，并在执行过程中违反先决条件时删除输入。



阻碍现有定向模糊器高效覆盖多个目标的主要问题是，它们无法区分不同目标之间的相关性，主要表现为路径条件重叠、冲突和独立。

![](https://blogdownload.oss-cn-hangzhou.aliyuncs.com/202404242142730.png)

## 作者方案

为了解决协同无知问题，我们的主要见解是模糊器可以利用多个目标可行条件之间的相关性，即独立性和矛盾性，来协同生成针对这些目标的输入。更具体地说，如果我们获得了与给定目标相关的变量的解空间，模糊器就可以区分目标之间的相关性，从而精确地指导种子调度和突变，从而高效地达到多个目标。

如果此时存在两个个种子$A(a,b,c,d):(6,3,1,1)$，$B(a,b,c,d):(5,0,3,1)$

- 首先，矛盾相关性表明触发这些目标的条件是否存在冲突。因此，我们可以为满足不同目标条件的种子分配不同的优先级。例如，$target\ 1$和$target\ 2$对变量$b$的条件有冲突（即$b>1$和 $b\le1$）。因此，模糊器可以对$target\ 2$使用种子$A$，对$target\ 1$使用种子 $B$​，以提高种子调度的有效性。
- 独立性相关性表明，多个输入字节可以独立影响不同的目标。因此，模糊器可以尝试同时改变这些输入字节，以接近多个目标，从而减少达到目标所需的执行时间。例如，在例子中，由于 a 和 d 是独立的，模糊器可以针对$target\ 1$和$target\ 3$同时改变它们的值。

![](https://blogdownload.oss-cn-hangzhou.aliyuncs.com/202404242031401.png)

我们首先根据不同目标的路径条件近似值发现它们之间的相关性。然后，我们通过检查目标的近似值是否冲突来确定目标之间的相关性。因此，模糊器可以通过识别和使用相关性，而不是仅仅依赖控制流距离，获得对多个目标的精确反馈。

条件的关系显示了检测多个目标的潜力。如果我们能对这些关系进行精确推理，定向模糊就能有效地达到多个目标。首先，模糊器可以利用冲突相关性来区分到达不同目标（如目标 1 和 2）的难度，从而更准确地为多个目标选择种子。其次，模糊器可以通过使用独立相关性为多个目标更有效地生成输入，例如，同时改变目标 1 和目标 3 的独立字节 b 和 d。



利用新的细粒度反馈，我们引入了两种优化的输入生成技术：

1. 协同感知调度策略，通过对种子进行细粒度排序，找到可能到达最多目标的种子。
2. 以多目标为导向的突变，可生成接近多个目标的输入，并减少所需的执行次数。



### 静态条件推断器

给定一组目标程序点，我们设计了两阶段静态分析：推断达到每个目标的先决条件，以及计算区分多个目标的相关性。

**先决条件推断**: 首先，我们将前提条件推断为达到目标代码的程序变量的必要条件。为了便于计算条件，我们利用区间域来过度近似达到目标的路径条件的可行搜索空间。从形式上看，静态分析可以推断出以下信息

$Definition1(Multi-target\ Reachability\ Summary)$: 给定一段程序目标点$T\subseteq N$，多目标可达性总结表达为$\bigcup_{t\in T}S_t$，其中$S_t(n)\sube Var\times Interval$并且$(v,itv)\in S_t(n)$。表明要达到目标程序点$t$，在执行程序点$n\in N$之前变量$ v $必须位于区间$itv$​中。



![](https://blogdownload.oss-cn-hangzhou.aliyuncs.com/202404242031401.png)

通过$Definition1$在之前的例子中可以推断出如下数据

$S_{t1}(l_5)=flag:[1,1],a:(5,+\infin),b:[0,1]$

$S_{t2}(l_5)=flag:[0,0],a:(5,+\infin),b:(1,+\infin),c:(2,+\infin)$

$S_{t3}(l_5)=d:(3,+\infin)$

其中$l_i$表示在$i$行之前的程序位置，$S_{t1}-S_{t3}$表示$target1-target3$



**相关推断**: 不同目标的推断变量范围可能存在许多相关性。例如，考虑上例中的多目标可达性总结。到达$target1$和$target2$都需要相同范围的变量$ a$，但它们对变量$ b $的范围有排他性要求：

$Definition2(Correlation\ among\ Multiple\ Targets)$: 假设静态分析结果为$\bigcup_{t\in T}S_t$，给定变量$v$和程序点$l$，我们定义条件是否重叠、独立、冲突如下

$independent(v,l,t_1,t_2)=(v\in S_{t1}(l)\wedge v\notin S_{t2}(l)) \vee (v\in S_{t2}(l)\wedge v \notin S_{t1}(l))$

$conflict(v,l,t_1,t_2) = S_{t1}(l)(v)\cap S_{t2}(l)(v) = \oslash $

$overlap(v,l,t_1,t_2)=S_{t1}(l)(v)\cap S_{t2}(l)(v)\neq \oslash$



通过$Definition2$在之前的例子中可以推断出

$overlap(a,l_5,t_1,t_2)$

$conflict(b, l_5,t_1,t_2)$

$independent(c,l_5,t_1,t_2)$

$independent(d,l_5,t_1,t_3)$

$independent(d,l_5,t_2,t_3)$



### 协同定向模糊测试



#### 协同感知种子调度

首先，我们根据图 2 所示的直觉来确定种子应考虑的目标。具体来说，如果到达的变量属于重叠相关或独立相关（如图 2 中的 a) 和 c) 所示），我们就认为种子可以到达这些目标，因为相交的搜索空间表明它们可以同时被覆盖。我们使用冲突相关性为当前种子筛选目标：如果当前种子无法满足目标的先决条件，我们可以暂时不考虑该目标。

$Example$：假设目前存在两个种子$A(a,b,c,d):(6,3,1,1)$，$B(a,b,c,d):(6,0,1,1)$。将它们分别用于$target1$和$target2$。根据种子执行中观察到的 b 值，我们认为 A 更有可能触发目标 2，而 B 则更有可能触发目标 1。

其次，我们需要对种子的重点目标进行优先排序，因为达到每个目标的难度都可能不同。具体来说，我们把达到一个目标视为满足相关联的多个变量的条件。应该优先考虑其值满足大多数变量条件的种子输入。因此，我们通过分析执行反馈来检查执行过程中满足的前提条件的数量。例如，在前面的例子中，由于 B 满足了目标 2 的 a 和 b 这两个变量的前提条件，而 A 只满足了目标 1 的 a 这一个变量的前提条件，因此我们将 B 优先于 A。因此，通过细粒度的反馈测量，我们可以选择最有希望的种子来覆盖多个目标。

![](https://blogdownload.oss-cn-hangzhou.aliyuncs.com/202404242142730.png)



#### 面向多个目标的突变

我们在每次运行时对接近多个目标的种子进行突变，以减少多余的执行次数。我们利用独立相关性来改变与独立变量相关的多个字节。具体来说，我们首先使用基于推理的污点分析，动态推断出可影响自相关变量值的输入字节。然后，我们分别对影响自变量的字节进行突变，从而使模糊器能够以较少的突变接近多个目标。

> Q1: 污点分析的性能开销?





#### 静态协同推理

对于每个程序点$v'$，算法通过迭代应用每个程序语句stmt的语义转移函数$transfer$，计算出到达$ t $的前提条件(第 5-7 行)。根据计算出的`multi-target reachability summary`，可以根据$Definition4$​得到一个种子的多个目标之间的相关性。

$Definition4(Correlations\ of\ a\ seed)$: 给定一个种子$S$，假设$S$可以到达程序位置$(v_1,l_1), ...,(v_n,l_n)$，其中变量$v_i$在$l_i$定义，则种子$S$的相关集为

$C(S)=\{r(v_i,l_i,t_j,t_k)\}|i\in(1,n),r\in\{independent,conflict,overlap\}$ 其中$(t_j,t_k)$为目标对



​