🤔



# ARCUS: Symbolic Root Cause Analysis of Exploits in Production Systems
## 作者

- Carter Yagemann - 佐治亚理工学院 - 漏洞检测、成因分析
- Matthew Pruett - 佐治亚理工学院研究所 - 漏洞检测
- Simon P. Chung - 佐治亚理工学院 - 漏洞检测
- Kennon Bittick - 佐治亚理工学院研究所 
- Brendan Saltaformaggio - 佐治亚理工学院 - 漏洞检测、Web方向
- Wenke Lee - 佐治亚理工学院研究所 - Fuzz

> **VulChecker: Graph-based Vulnerability Localization in Source Code**



## 思路

作者针对漏洞的RCA和修复提出了一种新思路，即利用Intel PT技术，来监控程序的错误的控制流，一旦程序被打上错误标记，ARCUS会将其捕捉并发向分析系统。分析系统会利用快照将错误流重建然后根据一系列模板发现冲突点确定漏洞根本成因。主要的检测思路是，在重建快照之后，将攻击者可以控制的参数更改为符号值，然后进行执行观察符号值的传播，一旦符号值污染到关键参数则确定漏洞触发，而后向前寻找符号值是怎么传进来的，在哪里产生的，以确定漏洞根本成因。

基本定位流程为：

1. 识别成为符号的代码指针：符号值向后传播即可
2. 识别污染其成为符号值的基本块：生成控制流依赖图CDG来定位
3. 寻找控制污染块执行的基本块
4. 测试附加约束是否可以修复漏洞

### 堆栈溢出的检测思路

堆栈溢出根本特征是控制流劫持，在重建快照之后，沿着攻击者执行路径进行重建中间状态时观察PC是否被污染成为符号值即可。在发现PC被污染成为符号值之后即确定存在堆栈溢出。从这一点开始，模块查看先前的状态以确定是什么导致符号数据进入PC。由于劫持只能发生在间接控制流传输时，因此先前的状态必须执行以返回、间接调用或间接跳转结束的基本块

**控制流被污染 + 之前的基本块为返回、间接调用或间接跳转结束的基本块**

### 整数溢出检测思路

**操作可能溢出 = 标记溢出的寄存器 + 寄存器传播到另外一个函数时 确定发生整数溢出**



### UAF和Double Free检测思路

**内部针对所有的malloc和free维护一个bin并且记录大小，一旦违背操作规则则发生UAF和Double Free**



### 格式化字符串检测思路

**如果违背指向格式字符串的指针是具体的，且驻留在只读存储器中/字符串的内容是完全具体的/所有附加参数都指向映射的内存地址则为格式化字符串漏洞**

[Paper] ARCUS: Symbolic Root Cause Analysis of Exploits in Production Systems

🤔



# BENZENE: A Practical Root Cause Analysis System with an Under-Constrained State Mutation



## 作者

- Younggi Park - 高丽大学、国防部
- Hwiwon Lee - 高丽大学、国防部
- Jinho Jung - 国防部
- Hyungjoon Koo - 成均馆大学
- Huy Kang Kim - 高丽大学



## 现有的RCA方案

- 基于AURORA的统计学方案
  - 缺点：用于崩溃探索的Fuzz技术不足以有效的收集RCA中适当的非崩溃行为；trace非常耗时
- ARCUS 预制规范模板的符号执行及崩溃重放
  - 缺点：无法解决符号执行带来的路径爆炸和约束求解的问题；不能预定义所有漏洞类型



## 理论基础

崩溃必须满足每个崩溃触发条件。也就是说，崩溃的存在必须满足一组条件（即谓词）才能产生给定的崩溃，这意味着如果集合中的任何谓词已被否定，则不会发生崩溃，并且正常行为与崩溃行下的一个或多个谓词相矛盾。

我们假设目标程序（P）的行为对于给定的输入 I 具有明确的执行路径（即确定性）。我们将 P 中的漏洞表示为 V。然后可能有多个 I 因 V 而触发崩溃，每次崩溃的执行路径是唯一的。

## 提取RCA的思路

1. 从所有谓词中提取出普通崩溃谓词
2. 从普通崩溃谓词中提取出根本成因

## 作者的思路

本质上和AURORA类似，只是引入了一种`运行时直接状态突变的欠约束状态突变方案`来实现崩溃探索

- 为了解决目前针对崩溃样例和非崩溃样例获取的难题，作者引入了状态突变来有效地收集与给定崩溃相关的不同行为
- 为了解决从大量普通崩溃谓词中定位根本成因的难题，作者去除了比较过程，选择用行为相似度定位根本成因

> 状态突变：这是一种针对 RCA 量身定制的突变技术，可在运行时突变目标程序状态。该技术背后的关键思想是，导致崩溃的输入的一部分最终存储在处理器寄存器或进程存储器中。
>
> ![](https://blogdownload.oss-cn-hangzhou.aliyuncs.com/202402210011766.png)
>
> > Q1. 这样做状态空间不是更大了么，如何快速缩小状态空间?
> >
> > 我们采用三种突变策略来使我们的技术实用且稳健（§6.2）。令执行的指令为$i\in\Omega$，其中$\Omega$表示某个程序中的所有指令。现在我们在执行指令$(i)$的那一刻定义一个状态为$S_i(R,M)$，其中寄存器和存储器的当前状态分别表示为$R$和$M$。为了描述状态突变$(T)$，我们定义两个属性：1个类型：$t\in\{opr,mem\}$，其中$opr$和$mem$表示要从中进行突变的源操作数或内存，以及 2 个值：$v \in Z_n = \{x|x\in所有可表示的n位整数\}$然后，状态突变可以正式写为$T_i(t,v,v'):S_i(R,M)\rightarrow S'_i(R',M')$ 其中状态转换是用值 $v$到$v′$ 类型$(t)$。例如，图 4 中 i := lea esi, [rax+rax*4] 上的状态突变可以写为 $T_i(rax, 0, 255): S_i(R,M)\rightarrow S'_i(R',M')$注意，BENZENE 仅关注源操作数中的值突变，因为目标操作数中的值由其源自动确定。
> >
> > - 突变总结：在高层次抽象来看上，BENZENE类似于 LibFuzzer和内存中模糊测试，我们通过分叉创建新进程来探索函数级别的程序行为。一旦提取了这些目标函数，我们就会以每个函数固定次数的迭代来重复状态突变。在每次迭代中，我们选择一个突变目标 Si(R,M)。当达到突变目标（Si）时，我们执行状态突变（Ti），相应地修改程序的当前状态。突变后，我们继续该过程直到终止并监视（非）崩溃。请注意，改变程序状态会使其容易发生意外崩溃；因此，我们设计了相关的突变策略。
> >
> > - 函数级Fork：由于程序中有大量指令，我们需要缩小状态突变的位置范围。为了解决这个问题，我们采用函数的粒度来进行突变过程（ 例如图 7 中的 Foo()）。具体来说，我们提取了与崩溃站点无效内存访问相关的函数列表。这可以在动态二进制分析期间使用函数信息和崩溃起源来执行（§5）。一旦确定了目标函数（例如 10 分钟），我们就为每个目标函数迭代一个状态突变 (F)；即，1 在目标函数内选择状态突变 Ti : S → S′（即 i ∈ F），2 执行指令，3 监视突变结果（即崩溃或非崩溃）。对于每次迭代，该过程都会在目标函数的入口处分叉。
> > - 变异目标的选择：对于目标函数的每个分叉过程，我们必须选择一个状态 Si(R,M) 作为突变候选。尽管我们将突变范围限制在目标函数内，但仍然存在突变目标选择问题。对于目标函数的每个分叉过程，我们必须选择一个状态 Si(R,M) 作为突变候选。尽管我们将突变范围限制在目标函数内，但函数内仍然存在大量指令。为了解决这个问题，我们将指令缩小到引用外部值（来自函数边界外部）的指令选择池（即 i ∈ P，P ⊂ F）。背后的直觉是某个函数的行为可以由外部值（例如参数或全局变量）决定；因此，改变它们可以帮助产生理想的行为。我们利用 DFG (§5) 来识别在二进制级别使用此类外部值的指令。考虑图 7 中的 inst2，其中 inst2 的传入边为 (rcx, inst1)。影响值（即 rcx 中的值）源自外部函数（例如调用者）。由于inst2采用外部引用值，因此我们选择Sinst2（R，M）作为P中的突变目标。相比之下，数据流来自inst2的inst3可以从P中排除，因为rax依赖于rcx。值得注意的是，我们的方法与调用约定（即子例程如何从调用者那里获取参数的方案，例如 stdcall、cdecl 或 fastcall）无关，因为我们检查值是否来自寄存器或具有函数边界的记忆。
> >
> > ![](https://blogdownload.oss-cn-hangzhou.aliyuncs.com/202402231058756.png)
> >
> > - Bag of Values: 由于其固有的不稳定性，欠约束的状态突变很容易导致不期望的无效崩溃。我们仔细的观察启发式地揭示了经常触发此类无效崩溃的两种主要情况：改变引用用户定义的数据类型（例如结构）的指针和改变具有不同范围的约束变量（例如枚举类型、数组索引）。为了处理这两种情况，我们维护一个Bag of Value (BoV) λ，以指导进一步的突变。该袋子在内部收集每个 Si(R,M) 的一组观察值（根据指令从源）。因此，可以从 Ti(t, v, v') 的 (即 v' ∈ λ) 中选择突变候选者 (v')。该策略背后的直觉是，共享相同数据流的值很可能具有相同的数据类型。这有助于观察可接受的行为，而不必担心二进制文件上的复杂类型推断。然而，它提供了在可接受的时间限制内覆盖大突变空间的机会。我们通过回溯 DFG 中的传入边（即，直到 DFG 中具有单个源边的点）（例如图 7 中的 3），从执行指令的存储值中培养每 S 的 BoV。 BoV 感兴趣的是一个特殊的值，它可以进入一个分支（例如，来自 cmp rax 的 0x40，0x40），使我们能够有效地收集非崩溃行为，例如模糊测试中的先前工作[76]、[111]、[ 124]。如果 BoV 超过预定义的大小（例如 1024），BENZENE 会进行随机抽样。使用 BoV，BENZENE 生成随机值 (RV)，为每个突变周期从 BoV 或 RV 中概率选择一个值（例如 50%）。请注意，我们禁用了 ASLR，因为每个突变的内存布局在突变期间必须保持一致。
>
> 
>
> > Q2. 直接更改状态空间按理来说是存在可能没有对应输入的，没有对应输入获取到的崩溃或者非崩溃谓词就是没有意义的？
> >
> > 人们可能会提出确保这种状态突变的行为有效性的问题，因为强制修改程序的中间状态通常会导致后续执行无效（例如，无法到达的状态）。然而，与模糊测试相比，我们的状态突变不需要推理输入的验证，而是利用突变本身来获得非崩溃行为。在这方面，我们的突变技术被称为欠约束状态突变，它是从欠约束符号执行中借用的。也就是说，即使存在不可行状态，非崩溃行为也是不满足崩溃条件的（副）产品，这可以帮助寻找根本原因（即崩溃条件）的候选谓词。举例来说，图 1 中第 4 行中 im1->sx 从 0xfff 到 0x0 的突变会导致非崩溃，因为它不包含崩溃条件下的谓词之一 [im1->sx > 0x0]。尽管此突变通过引导无法到达的分支（即，没有循环的转义）而导致不可行的执行，但其行为对于获取 RCA 的谓词很有用。我们在第 6.3 节中详细阐述了在约束不足的状态突变下崩溃行为的有效性。
> >
> > ![](https://blogdownload.oss-cn-hangzhou.aliyuncs.com/202402210046908.png)
> >
> > 虽然我们的欠约束状态突变技术主要集中于收集非崩溃行为，但有必要收集最小的崩溃行为集，因为我们利用了 AURORA 谓词合成的方法（等式 1）。然而，与可以确认其有效性的非崩溃行为相比，很难确定由状态突变引起的崩溃是否与原始崩溃相关联。例如，如果最初表示特定指针的目标被突变为无效整数（例如 0x1），则崩溃（与错误无关）将毫无意义。这种无效的崩溃通过在方程 1 中引入大量噪声而显着阻碍了准确崩溃条件的合成。基于先前的反向执行分类技术 [78]、[79]、[121]，我们将某个崩溃分类为同一类别，如果遵循相同的数据流。然而，为每次崩溃执行构建 DFG 的成本很高，开销也很大。为了解决这个问题，我们设计了一种崩溃分类技术，可以将具有给定崩溃（即根本原因）的执行与具有无效状态突变的执行区分开来，同时产生较低的开销。该技术需要满足以下两个条件：1 由状态突变触发的崩溃站点（即地址）与初始崩溃相同，2 执行与崩溃起源相关的指令。如果状态突变的崩溃满足上述条件，我们记录此行为；否则，我们将丢弃它。显然，我们的方法可能会通过仅考虑 V 导致的所有可能崩溃的子集来合成过度近似的崩溃条件；然而，CR 仍将与子集一起保留。换句话说，CR 必须满足非崩溃不能满足的崩溃（一部分）。
>
> 
>
> > Q3. 
> >
> > 





> 行为相似度：这种方法的关键见解是，在常见的崩溃情况下，非崩溃行为必须与一个或多个谓词相矛盾。我们的方法基于以下事实：给定崩溃和非崩溃之间的代码覆盖率越接近，就越有可能通过与崩溃中的谓词相矛盾来揭示 V 的根本原因。例如，表 1 列出了四种非崩溃行为（#1-4），每种行为至少与 C* 中的一个谓词（即灰色单元格）相矛盾。在这种情况下，与第一个非崩溃输入 (#1) 相矛盾的谓词 (p1) 最有可能成为 CVE2019-6977 的根本原因，因为 #1 是最接近初始崩溃（即 IC）的行为。利用主成分分析来计算非崩溃行为的相似度得分
>
> ![](https://blogdownload.oss-cn-hangzhou.aliyuncs.com/202402210020054.png)





## 整体框架结构



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

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

BENZENE 首先构建一个矩阵来描述每个收集到的行为的边缘覆盖范围，然后计算初始崩溃和非崩溃行为的覆盖范围之间的相似性得分。接下来，BENZENE 合成基于非崩溃行为描述崩溃条件的谓词。最后，BENZENE 使用崩溃条件的综合和每个非崩溃行为的相似性分数对导致给定崩溃的所有谓词进行排名。

欠约束状态变异可能会造成许多无意义的崩溃，所以归类有意义的崩溃至关重要。如果一个崩溃由状态突变触发的崩溃站点（即地址）与初始崩溃相同且执行与崩溃起源相关的指令。如果状态突变的崩溃满足上述条件，我们记录此行为；否则，我们将丢弃它。

- 边缘覆盖矩阵：与 AFL类似，我们利用广泛采用的边缘覆盖图来衡量模糊技术的性能。 BENZENE 在 64 KB 大小的地图上记录每个收集的行为的边缘覆盖信息（即基本块之间发生的转换）。地图随着迭代突变而不断更新。通过n种不同的行为，我们可以获得n（行）×64 KB（列）大小的边缘覆盖矩阵。一个值得注意的副作用是，具有非崩溃行为的执行的覆盖图将保持更新，直到程序终止，而具有崩溃行为的执行则不会。这不可避免地会导致用于比较的覆盖图之间存在显着差异，这阻碍了我们寻找与原始崩溃类似的非崩溃行为的主要目标。为了缓解这个问题，我们利用一个观察点来通知我们何时停止更新覆盖图。准确地说，观察点监视崩溃起源之一（第 6.3 节）；一旦执行了崩溃触发的指令（来自给定的崩溃），覆盖图更新将被暂停以供后续执行。
- 基于 PCA 的相似度。为了减少边缘覆盖矩阵的维度，我们应用 PCA为每个收集的行为获得紧凑的覆盖图（图 8 中的 1）。然后，我们计算非崩溃行为的覆盖范围与初始崩溃之间的欧几里德距离（即 L2 范数）。 BENZENE 通过相似性分数（图 8 中的 2）确定具有某种非崩溃行为的执行与原始崩溃行为的执行有多接近：即距离越小，分数越接近。这种相似性评分允许对所有收集到的接近初始崩溃执行的非崩溃行为进行优先级排序。

[Paper] BENZENE: A Practical Root Cause Analysis System with an Under-Constrained State Mutation

🤔


# AIFORE: Smart Fuzzing Based on Automatic Input Format Reverse Engineering

> 1. 不同输入字段的边界在哪里
> 2. 这些字段属于哪些类型
> 3. 如何利用输入格式知识指导Fuzz

## 作者

## 作者的观点

输入字段的结构和语义由处理他们的基本块来定义而不是输入规范。

## 现有的方法

### 现有输入字段边界识别的方法

现有的输入字段识别有统计分析和动态污点分析将同一个指令处理的字节分组到一个字段分组中。这样的做法存在的问题就是，一条指令可能在循环中处理多个输入字段，并且一个长字段大概率是被多个指令所处理，因为一条指令无法处理超过机器字长的数据。

### 现有的输入字段类型识别方法

现有的解决方案一般依赖于先验知识，例如strcpy的参数类型，但是这种方式需要大量的人工介入并且只能识别程序的变量类型而不是语义类型。

### 现有的利用格式知识指导Fuzz的方法

现有的方案都是针对结构良好的种子分配更多的能量以执行更多的突变，但是大部分方案都是没有字段间关系约束的，无法区分种子质量。

## 作者的方法

### 识别输入字段边界的方法

首先使用动态污点分析来确定每个基本块处理了哪些输入字节，因为单个不可分割的字段可能会被一个基本块中的多个指令处理但是大概率不会被多个基本块处理。根据污点分析结果使用`最小聚类算法`来确定不可分割字段的边界。

### 识别输入字段类型的方法

构建深度学习模型来预测基本块处理输入字段的类型和语义。

### 利用现有的格式知识指导Fuzz的方法

首先选择代码覆盖率显著不同的测试用例，其次选择在模糊测试中测试频率较低的种子。



## 设计架构

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

在模糊测试过程中，如果一个种子带来了大于3%的平均覆盖率提升，则将其标记为有价值的种子，而后使用AIFORE分析其格式，并且使用知识模型（提取的字段边界和字段类型知识）进行模糊测试。其中AIFORE使用污点分析构建输入字节和处理字节的基本块之间的映射关系，然后分别调用`Field Boundary Analysis`、`Field Type Classification`、`Fuzzing with Power Scheduling`三个模块。

其中`Field Boundary Analysis`模块主要是将输入分割成为字段；`Field Type Classisfication`模块主要是使用CNN模型预测字段类型信息；最终结合字段边界信息和字段类型信息组成`格式模版（Format Template）`，其为一个pit文件，对于每个字段记录其边界和起始位置、大小、类型。





### 字段边界识别

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

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



从BB中拆分字段的算法如算法1所示，首先从二进制程序中提取出所有的BB，然后针对二进制程序进行污点分析。利用污点分析出来的污染地址与BB做对应，将其存储在一个字典`BB_to_taint`中，而后针对字典中每一个受污染的BB，收集并合并在一个BB中处理的字节，而后根据BB和BB中受污染的字段来进行分割，针对于连续字节将作为同一个字段进行划分。例如图3中的第四行(18,19)字节将作为一个字段进行分割。

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



### 字段类型分类

这里的分类主要是想针对BB分类以提取出字段的语义类型，例如偏移量或者校验和等信息。而不是程序变量类型，例如int或者string。作者将所有字段分为了六种语义

- SIze：此类型的字段主要表示输入文件中一个或多个字段组成的数据块长度。例如ELF文件格式中偏移量为0x28的字段`e_ehsize`表示ELF文件头的大小。
- Enumeration：此类字段只能采取一组有限的有效值，例如在ELF文件格式中的`e_type`字段只能使用ELF格式中定义的七种有效值之一。
- Magic number：幻数。
- String：字符串文字，可以为ASCII、Unicode或者其他编码形式。
- Checksum：校验和，此类字段用于完整性验证，常见于媒体文件、压缩文件、字体格式中。
- Offset：偏移，此类字段用于指示输入中另一个数据块的位置，例如ELF文件格式中偏移为0x20处的`e_shoff`表示节头的偏移量。

作者选用深度学习来使用机器学习以对BB进行字段类型分类，并且使用向前切片以合并对字段的重要操作。

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



### Fuzz的能量调度

1. 应该优先针对哪些种子执行格式提取?
2. 如何平衡突变过程中针对不同格式变体的模糊测试？

首先针对初始种子进行分析以构建格式模型，而后在格式模型的指导下针对种子进行变异，如果新突变的种子有价值那么就重新分析其结构。如果Fuzzer长时间内无法获得新的覆盖范围的话，就将Fuzzer的能量分配给那些尚未完全变异的格式。



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

针对不同的字段变异方式也不同，针对每个字节Mutator会将其作为一个整体进行变异，例如Size字段会将其更改为一个合理值而不是位翻转。针对没有格式知识的字节，Mutator将使用AFL中的默认突变方式。

[Paper] AIFORE: Smart Fuzzing Based on Automatic Input Format Reverse Engineering

👍


# 1dFuzz: Reproduce 1-Day Vulnerabilities with Directed Differential Fuzzing


> TCS: 尾随调用序列
>
> 定向差分模糊测试
>
> SecretPatch数据集



## 作者



## 复现1Day的困难

- 如何识别未开源的补丁位置?
  - 现有方案: 根据控制流图比较来定位补丁位置[静态] 根据程序执行轨迹来定位补丁位置[动态] 依靠深度学习提取二进制代码特征[机器学习]
    - 现有方案的缺点: 编译优化会导致二进制文件之间存在差异会影响定位结果、无法区分功能更新和漏洞补丁
- 如何针对补丁生成PoC?
  - 现有方案: 符号执行、定向模糊测试
    - 现有方案缺点: 符号执行无法应用于大型项目中、定向模糊测试很难确定在模糊测试中是否触发漏洞



## 作者提出的方法

经过大规模研究之后发现，大部分补丁都会检查输入有效性，如果输入无效则退出。针对同一个PoC在修补之后的程序当中和未修补的程序当中在修补位置会产生不同的执行跟踪。简单来说就是执行同一个PoC在执行最后的N个函数中执行跟踪是不同的。即TCS[尾随调用序列]不同

- 定位补丁位置的方法: 构建修补之后和未修补二进制程序的调用图并对齐其中的函数，通过静态分析找到具有不同被调用函数的序列的对齐函数，这些对齐的函数将标记为修补函数

- 针对补丁生成PoC的方法: 采用定向模糊测试方案生成PoC，针对修补过后和修补之前的二进制程序进行差异测试，跟踪测试期间两个二进制程序调用的函数序列，并在最后N个函数不同时确定PoC。



## TCS: 尾随调用序列

TCS的理论基础是大部分的补丁修补都如图所示，是针对之前版本的漏洞增加校验，如果校验不通过则退出。这表明，如果为修补前和修补后的二进制程序提供同一个PoC，那么在二进制程序中在补丁之后将会有不同的执行流，即使不知道补丁位置，但是通过执行流仍然可以观察到修补前和修补后的二进制程序在函数调用序列的尾部存在分叉。

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

**作者给出定义: TCS，尾随调用序列。在给定程序P和输入I，在程序P退出前的最后N个函数调用表示为TCS(P, I, N)**



### TCS合理性验证

作者通过针对从1999到2018年中所有关于C/C++的漏洞补丁进行统计，确定在此期间的漏洞补丁有71.3%都具有TCS特征。由此验证了TCS合理性。



## 架构设计

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

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

首先，针对修补前和修补后的二进制程序首先将其从CFG层面将其对齐，然后通过比较函数调用图来定位补丁位置，最后使用定向差分模糊测试来探索补丁位置，并且使用基于TCS的sanitizer来捕获PoC。



### 二进制代码对齐

首先，反汇编二进制程序并识别所有的函数和直接调用，然后根据直接调用关系静态构建函数调用图。其次，利用动态执行收集间接调用关系，在动态执行中对于每个间接调用都在函数调用图上增加一条从调用者到被调用者的边。

针对同一个PoC在常理上除了修补相关的函数，调用的大部分函数都是相似的。也就是说在跟踪中两个执行流具有高度相似的函数序列，可以用于对齐两个调用图中的子图。如此可以依赖跟踪来逐渐对齐两个二进制程序中的函数。



#### 对齐流程

针对在未修补二进制的函数调用图中未匹配到的函数$f$和在修补后的二进制函数调用图中未匹配到函数$f'$ 对其计算相似度

1. 出入度相似度: 当两个函数在调用图中存在相似的出入度时，其更有可能匹配 $score=\frac{min(I_f,I_{f'})}{max(I_f,I_{f'})}+\frac{min(O_f,O_{f'})}{max(O_f,O_{f'})}$ 
2. 函数参数寻址方式相似度: 调用函数有许多种传参方式，1dFuzz记录了各种调用函数时参数的寻址类型 

$score=\frac{\sum min(MC_{addr},MC'_{addr})}{\sum min(MC_{addr}+MC'_{addr})/2}$ 其中$MC_{addr}$表示在修补前函数调用图中使用特定寻址方式的参数数量，$MC'_{addr}$表示在修补后函数调用图中使用特定寻址方式的参数数量

3. Caller相似度: 如果未修补函数调用图中函数$f$有Caller$f_p$，修补之后的函数调用图中函数$f'$有Caller$f'_p$，且$f_p$和$f'_p$在匹配集中，则为函数对$(f_p,f'_p)$加一分 
4. 针对所有函数进行迭代计算相似度，每轮都会更新分数。如果上轮中函数对$(f_p,f'_p)$匹配则本轮中为该函数对加0.5分



### 1dLoc - 补丁定位工具

通过深度优先算法通用遍历对齐之后的每个函数对的CFG中的所有路径，并且收集每个路径上的被调用函数序列，比较这两组调用函数序列检查是否不同，如果一个调用序列中存在另外一个中不存在的函数调用，则将对其的函数标记为候选Patch函数。



### 1dSan - 定向模糊测试辅助工具

主要架构如图所示，为了同时测试修补前和修补后的二进制程序并检查其TCS，使用相同的输入和相同的运行环境测试两个二进制程序。为了效率其并不会记录所有被调用函数的列表，只会记录最后调用的N个函数。其将驻留在Fuzzer中而不是Binary中，其会在测试用例结束之后比较函数列表缓冲区，如果不同则抛出异常。

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



### 定向差分模糊测试

- 距离算法: 给定源函数和目标函数的情况下，如果源函数有多个调用站点可以调用到目标函数，则认为源函数更容易进入目标函数。换句话来说，这样的调用者和被调用者之间的距离更短，所以针对调用图中的每个边，统计计算Caller函数中有多少个调用站点可以调用Callee并将其个数表示为$CN$，计算其距离为$1+\frac{1}{2\times CN}$。在计算完函数调用图中每条边的距离之后就可以得到从源函数到目标函数的最短路径距离。

[Paper] 1dFuzz: Reproduce 1-Day Vulnerabilities with Directed Differential Fuzzing

😀



# Profile-Driven System Optimizations for Accelerated Greybox Fuzzing


## 优化方面

- fork server -> persistent mode with efficient state recovery
- OS interaction



## 先前的优化方向

- 优化测试用例的调度
- 优化测试用例的变异
- 优化测试用例的保留



## 为什么选择fork server方向优化

- 传统情况下 AFL和AFL++都运行在fork server模式下 但是分叉子进程需要开销大量时间[复制页表 COW等]

- 如果单纯使用persistent mode往往由于没有恢复初始状态 先前一次的模糊测试往往会影响到后续模糊测试的状态
- 现有提出的snapshot mode 经过测试也会抵消persistent mode带来的速度优势

## 为什么选择OS interaction方向优化

- 现代操作系统为Fuzz提供了许多不必要的操作 占据了许多的时间开销



## 传统fork server优化方法 [Snapshot mode]

- 定制内核 在执行测试用例之前对进程内存进行快照
- 将所有页面设置成为ReadOnly 并且执行COW
- 完成测试用例恢复所有存在修改的页面

## 传统fork server优化方法 [Persistent mode]

- 不需要恢复内存 不需要恢复状态 不需要定制内核
- 但是没有清理状态 导致要求使用Persistent mode需要目标的状态可以自动完全重置 并且不会造成资源泄露并且要求早期的执行不会影响后续的执行
- 在大多数情况下需要人工Patch原本的程序以恢复状态

## fork server优化方法 [Profile-driven State Recovery]

- 采用persistent mode
- 针对Persistent mode中需要重置的资源: 全局变量、内存资源、内核数据结构、文件描述符等
- 针对persistent mode中状态恢复的问题 在分析阶段使用测试用例动态分析目标程序 了解操作了哪些全局变量、环境变量
- 在运行测试用例之前快速重置全局变量和环境变量
- 可以设置为定期运行重置

## OS交互层面优化 [Profile-driven OS Abstraction]

- 大多数情况下执行用例和OS的交互都是进行文件交互 使用VFS来处理对文件的操作 直接将文件读取到内存中以减少文件操作开销
- 管理内存中文件的数据和元数据 避免和IO设备进行交互
- 在用户空间运行所有内容 避免中断和上下文切换
- 只保留与Fuzz相关的功能 删除如日志等与Fuzz无关的操作

- 可以使用独立的VFS来为每个模糊测试实例提供服务 避免文件系统争用
- 可以重置VFS达到快速重置文件描述符的目的

## 影响Fuzzer性能的因素

- Fuzzer的性能取决于算法因素和系统因素
- 算法因素: 
  - 测试用例的调度: 优先对哪些测试用例进行变异和变异多长时间
  - 测试用例的变异: 变异算法
  - 测试用例的评价标准: 代码覆盖率、调度上下文、路径覆盖率
- 系统因素: 系统因素主要影响Fuzzer如何实现Fuzz过程



## 测试IO影响

- 使用ext4文件系统和tmpfs文件系统对比IO开销



## profiling phase 分析阶段

- 针对内存资源: 不需要处理 在Presistent mode执行1000次之后执行一次fork 如此自动回收内存资源
- 针对全局变量: 在分析阶段对测试用例进行动态分析 观察操作了哪些全局变量并记录 在执行测试用例之前重置这些全局变量
  - 随着Fuzz的进行可能会影响新的全局变量: 使用AFL的稳定性指标 观察到稳定性下降就重新执行分析阶段 重新记录影响的全局变量
- 针对环境变量: 使用`setenv`和`unsetenv`获取环境变量
- 针对文件系统: 首先构建一个VFS，检测对应IO文件的属性 如果存在分析阶段没有发现的文件 VFS会将其映射到本地文件系统中
  - 现存文件: 如果在分析阶段 打开或者写入一个现存文件, 对于这样的文件在VFS中创建一个保留文件数据和元数据的副本 其中文件路径在VFS中保持一致
  - 不存在的文件: 如果在分析阶段 打开一个不存在的文件，对于这样的文件在VFS中创建一个空白节点，表示该路径下的文件不存在
  - 新建文件: 忽略新建文件的请求 因为VFS支持新建文件
  - 测试用例: 为测试用例分配共享内存以保存文件 并且方便Fuzzer可以直接访问其进行更新
  - 标准输入/输出: 在VFS中维护一个缓冲器以模拟标准输入
  - Socket: 在VFS中添加一个虚拟文件以充当套接字 其保存在内存中

## 如何检测全局变量变动

- 传统做法: 将全局数据段设置为只读 当写入全局变量时会触发异常以捕获对应全局变量
- 本文做法: 为全局变量添加存储或地址获取操作的检查 

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

> 具体是如何实现的扫描全部的全局变量?
>
> 开发了一个llvm插件 以实现在编译器优化之后扫描全局变量