🤔



# FOX: Coverage-guided Fuzzing as Online Stochastic Control



## 作者

- Dongdong She - 香港大学 - 漏洞挖掘、模糊测试
- Adam Storek - 哥伦比亚大学 - 
- Yuchong Xie - 香港大学 - 模糊测试
- Seoyoung Kweon - 哥伦比亚大学 - 
- Prashast Srivastava - 哥伦比亚大学 - 模糊测试
- Suman Jana - 哥伦比亚大学 - 机器学习、漏洞检测、模糊测试



## 传统方案

**Scheduler**: 传统覆盖率引导的模糊测试采用较为粗粒度的反馈(覆盖率反馈)选择进一步突变的样本，这种做法严重依赖先前产生的提升覆盖率的种子。随着模糊测试的进行，该调度方法往往会退化成为循环方法。

- 数据流引导的模糊测试: 先前有研究提出了反馈粒度更为精细的数据流引导的模糊测试，但是其往往会带来语料库爆炸的问题。



**Mutator**: 目前的Mutator和程序分支是无关的，其独立于分支逻辑执行随机突变，很显然存在盲目性。

- 污点分析: 虽然污点分析提供了分支定制的突变操作，但是其开销是无法接受的



总结来说，目前虽然**Fuzzer = Scheduler + Mutator**，但是当前的Fuzzer往往都是将其拆分为两个目标不同、数据交换很少的独立实体。



## 作者的方法论

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

覆盖率引导的模糊测试可以定义为一个**在线优化**问题，其目的是最大化目标程序的边缘覆盖率。

对于任意一个目标程序$P$，其输入样例长度为$M$；在每次模糊迭代$i$中，Fuzzer会从当前种子库$S_i$中选择一个种子$S_i[u_i]$，其中$u_i$为所选种子的索引。然后Fuzzer针对样本$S_i[u_i]$ 应用变异器$mut(\cdot)$ 生成新的输入$x$，而后程序将该变异输入执行并使用函数$cov(x,S_i)$来计算变异输入$x$和种子语料$S_i$实现的代码覆盖率提升。根据覆盖率结果Fuzzer会选择是否将输入样本$x$输入到语料库$S_i$中以生成语料库$S_{s+1}$，其目的可以总结为最大化$K$个阶段的代码覆盖率

可以形式化表示为: $Maximize\sum^K_{i=1}[cov(mut(S_i[u_i]),S_i)]$

> Q1: 啥是在线优化问题?
>
> 在线优化问题是机器学习中的一个概念，在线学习代表了一系列机器学习算法，特点是每来一个样本就能训练，能够根据线上反馈数据，实时快速地进行模型调整，使得模型及时反映线上的变化，提高线上预测的准确率。相比之下，传统的批处理方式需要一次性收集所有数据，新数据到来时重新训练的代价也很大，因而更新周期较长，可扩展性不高。

如此以来就将模糊测试的覆盖率提升问题转化为一个**最优控制问题**，在最优控制问题中主要目标是在给定状态空间和控制空间的情况下找到最优控制策略。在目前的模糊测试方案中，状态空间可以定义为Fuzzer在每个阶段的状态，即当前的语料库$S_i$；而控制空间则对应于Fuzzer作出的选择，例如选择样本进行突变。

**状态空间**: Fuzzer 在任何给定阶段的所有可能的配置或者状态，简单来说就是第$i$阶段的语料库信息，用$S_i$来表示

**控制空间**: 包括所有可能影响系统行为的决策，简单来说就是在每个阶段选择哪一个种子，用种子语料$S_i$中的索引$u_i$表示

综上，由于Mutator的随机性质，Fuzzing过程是动态随机的，从形式上看，作者将动态步骤定义如下

$x \leftarrow mut(S_i[u_i]) \\ g_i = E[cov(x,S_i)] \\ S_{i+1} \leftarrow update(S_i, x, g_i) $

**目标函数**: 目标函数定义了系统的目标或预期结果，简单来说其目标是使得$K$个阶段的预期总覆盖最大，形式化表示为$Maximize\sum^K_{i=1}g_i$

**制约因素**: 系统需要满足的限制条件，简单来说就是总执行时间(每个阶段$t_i$的执行时间总和)不得超过Fuzzing处理活动的总时间预算$T$，形式化表示为$\sum^K_{i=1}t_i\le T $



从形式上讲，$cov(x,S_i)$可以建模为一个随机变量，该变量计算在阶段$i$中有多少个未被覆盖的条件分支被针对输入$x$的随机突变操作而翻转；故作者提出了一个指示函数$cov_b(x,S_i)$其结果是一个布尔值，如果在阶段$i$中条件分支$b$因为输入$x$而翻转则结果为$1$，反之为$0$。由此可以得出函数$cov$的数学期望为$g_i=\sum_{b\in B_i}E[cov_b(x,S_i)]$。

通过形式化某分支$b$翻转的概率为$Pr(b\ flips | mut(S_i[u_i]))$ 而 $x \leftarrow mut(S_i[u_i])$，所以可以结合上述公式推到出$g_i=\sum_{b\in B_i}Pr(b\ flips |mut(S_i[u_i]))$ 



而后为了能够估计$Pr(b\ flips |mut(S_i[u_i])$ 的值，作者引入了**forontier node**和**horizon node**的概念，作者将CFG视作$G=(N,E)$其中$N$为一组基本块，$E$表示这些基本块之间的控制流转换，在给定一个语料库$S$的前提下，可以根据代码覆盖率信息将$N$分类为一组未访问的节点$U$和一组访问过的节点$V$

形式化表示为$V=\{n|n\in N,S.cov(n)=1\} \\ U=\{n|n \in N , S.cov(n)=0\}$ ，其中$S.cov$表示在语料库中是否到达节点$n$；作者将**forontier node**定义为一组已访问的节点，并且其主导所有未访问的节点 [这不就是前驱结点么..] $F = \{v|(v,u)\in E,v\in V, u \in U\}$

> Q2: 啥啥啥?
>
> 这里借鉴了文章`Effective Seed Scheduling for Fuzzing with Graph Centrality Analysis`的概念，但是没看懂

为了通过**forontier node**来反应覆盖率，作者只关注和条件跳转相关联的**forontier node**，即**forontier branch**。第$i$个阶段的**forontier branch**用$FB_i$来表示。假设第$i$个阶段的**forontier node**都涉及到对谓词$Q_b$的判断，谓词根据关系$f_b(x)\ R_b\ 0$来判断真假，其中$R_b$表示条件类型$(<,\le,>,\ge,=,\ne)$，x表示输入用例。翻转分支则表示找到一个输入$x'$，其是得$Q_b(f_b(x')) \ne Q_b(f_b(x))$，也就是说使条件的真假翻转。如果通过对Fuzzer的改造，使得Fuzzer在Fuzz过程中可以感知到每个**forontier branch** $b\in FB_i$的二元组$(Q_b(f_b(x),R_b))$，如此便可以定义分支距离算法

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

FOX: Coverage-guided Fuzzing as Online Stochastic Control

🤔



# CAMFuzz: Explainable Fuzzing with Local Interpretation



## 作者



## 核心思想

目前主流的研究思路是解锁未覆盖到的代码块，但是作者认为并不是所有未解锁的代码块都是有用的；同时对于需要解锁的代码块进行分析目前的主流方案是符号执行或者是数据流分析，但是目前的符号执行或者数据流分析仍然存在许多的问题；同时机器学习方案在模糊测试中存在不稳定或模型训练时间过长的问题。

针对上述问题，作者提出了一种名为CAMFuzz的新型解决方案，其利用了可解释人工智能和程序理解能力来分析首先需要解锁程序中的哪些代码块，应该优先变异哪些字节来到达目标区域，并且应该怎么变异。



## 整体框架

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

- Training: 目标是能够训练处一个模拟程序行为的模型，给定一个种子输入，模型就可以预测代码覆盖图。作者选择使用**分类模型**实现这个目标，最后使用一个GAP层来替代最后一个卷积层后的全连接层
- Local Explanation: 使用GAP层来定位输入中的对象，而后让其来帮助我们进行解释；直观上来讲，我们已经训练了一个从输入到程序代码块的映射，我们给出一个目标代码块，`Local Explanation`模块应该给出与该代码块所相关的字节位置
- Magic Value Identification



### Training



**Data preprocess**

作者选择的训练数据为`原始种子文件`和`覆盖率图`

针对`原始种子文件`，首先找到最大的种子而后将其他种子使用`\x00`填充到目标大小；而后将所有种子文件输入到目标程序中获取覆盖率图。通常来说Fuzzer输出的种子是不平衡的[即大部分种子覆盖到大部分都能覆盖到的代码块，只有少量种子可以覆盖到稀有代码块]，所以为了解决这种种子不平衡的问题，作者在获得覆盖率图后会对种子队列进行剪枝以平衡种子。



**model**

作者使用CNN模型来将种子映射到覆盖率图，在理想情况中给定一个训练好的模型$f$和一个输入$(x_1,x_2,...,x_n)$，这个模型可以预测一个代码块$cov_i$能否被覆盖。但是针对该模型作者做了三个改动

- 使用GAP层而不是全连接层
- 将最后一个卷积层所产生的特征图的形状设置为128
- 为了解决代码块数量过多的情况，作者设计了一种分段训练算法

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





**Local interpretaion**

作者引用了一种名为*CAM*的本地解释技术，其背后思想是

- 使用GAP层替代全连接层
- 利用 GAP 后面的最后一个卷积层生成的特征图中的部分信息和 GAP 生成的权重来生成定位信息

作者最后只生成了大小为128的热力图，其给出的解释是如果保持特征图的形状和原始输入相同会有大量的卷积运算从而拖累模型训练进度。



**Node selection**

[Paper] AMFuzz: Explainable Fuzzing with Local Interpretation

😱



# FairFuzz: A Targeted Mutation Strategy for Increasing Greybox Fuzz Testing Coverage



## 作者

- Caroline Lemieux - 加利福尼亚大学 - 机器学习、模糊测试
- Koushik Sen - 加利福尼亚大学 - 模糊测试、机器学习、LLM、智能合约模糊测试



## 作者思路

FairFuzz主要针对传统模糊测试中无目的随机变异的问题提出了两个解决方法

- 识别在模糊测试过程中很少命中的程序分支的种子，而后提高其优先级使得Fuzzer更多的倾向于没有充分覆盖的分支
- 通过针对命中稀有分支的种子进行变异测试，确定覆盖对应分支的关键字节并生成掩码以保证关键字节不被变异



## 方法论



### Mutation Mask

**Definition 1.** 定义Mutation为一个元组$(c,m)$，其中$m$为突变所影响的字节数，$c$为突变类型

- $O$: 使用一些值覆写从$k$字节开始的$m$个字节的内容
- $I$: 在$k$字节处插入$m$字节的内容
- $D$: 在$k$字节处删除$m$字节的内容

**Definition 2.** 定义突变掩码是一个输入$x$和测试目标$T$的函数 $mask_{x,T}:N \rightarrow P(\{O,I,D\})$。对于任意输入$x$的一个位置$i$输入到函数中，其将返回一个变异策略${O,I,D}$的子集，如果其满足$(mutate(x,(c,1),i),T)$为真，我们则认为$c\in mask_{x,T}(i)$为真；也就是说如果$c$在集合$mask_{x,T}(i)$中，那么在$x$的第$i$个位置应用突变$c$后，得到的输入将满足目标$T$

具体来说，算法如下

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

针对于最关心的掩码生成部分，算法很简单粗暴，直接针对每个字节变异一遍计算掩码即可

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

[Paper] FairFuzz: A Targeted Mutation Strategy for Increasing Greybox Fuzz Testing Coverage

🤔



# Better Pay Attention Whilst Fuzzing



## 作者

- Shunkai Zhu - 浙江大学 - 机器学习、模糊测试
- Jingyi Wang - 浙江大学 - 机器学习
- Jun Sun - 新加坡管理大学 - 模糊测试、智能合约、神经网络
- Jie Yang - 浙江大学 - 社交网络、机器学习
- Xingwei Lin - 蚂蚁集团 - 模糊测试、漏洞挖掘、LLM
- TianyiWang - 浙江大学
- Liyi Zhang - 浙江大学 - 模糊测试 - Monarch: A Fuzzing Framework for Distributed File Systems.
- Peng Cheng - 浙江大学 - 漏洞挖掘、机器学习



## 作者的思路

目前主流的基于覆盖率引导的模糊测试工具存在两个问题

- 默认选择覆盖新分支的种子进行模糊测试: 起初是生效的，但是随着时间推移覆盖新分支的种子愈发稀少并且间隔较远
- 丰富的变异算子对种子进行变异: 当测试进行到一定时间之后，解锁特定区域的代码块需要针对某个特定的字节进行变异，但是目前的变异算子无法满足。

针对这些问题目前的解决方案有

- 符号执行/约束求解: 通过识别与程序流相关的字节来改变输入用例中最相关的字节，但是仍然存在随着突变的进行对某些特定字节进行破坏的问题
- 机器学习过滤无关种子: 通过机器学习来过滤队列中无关的种子，但是其效果往往不好并且存在不可解释性的问题



所以作者为了解决以上问题提出了ATTFuzz

- ATTUZZ 根据覆盖未覆盖分支的概率及其数量来估计奖励
- ATTUZZ 训练了一个模型，该模型预测在给定种子的某些字节上的某些突变的情况下是否会覆盖某个“奖励”块



## 形式化定义



**Definition 1. grey-box fuzzing problem**

作者将灰盒模糊测试定义成为一个含有标签的转换系统$P$，其中$P=(B,init,V,\phi,GC,T)$

- $B$: 一组有限的基本块集合
- $init \in B$: $init$表示程序唯一的入口点
- $V$: 一组有限的变量集合
- $GC$: 是一组以$[g]f$形式存在的`guarded command`，其中$g$为`guarded command`而$f$通常为会更新变量$V$的函数，$f$通常表示为基本块
- $T$: 是一个转移函数，表示$B\times GC \rightarrow B$



$P$的具体执行是一个序列$\pi=<(v_0,b_0),gc_0,(v_1,b_1),gc_1,...,(v_k,b_k)，gc_k,...>$

- $v_i$：是$V$的估值
- $b_i$：$b_i \in B$
- $gc_i$：$gc_i = [g_i]f$，使得$(b_i,gc_i,b_{i+1}) \in T$，$v_i \models g_i$并且对于所有的$i$、$v_0 \models \phi$和$b_0=init$都有$v_{i+1}=f_i(v_i)$



作者使用$\Pi$来描述一组具体执行，当且仅当$b$在序列中时才可以说$\pi \in \Pi$覆盖了基本块$b$；当且仅当存在具体执行$\pi \in \Pi $覆盖了基本块$b$时，才可以说$\Pi$可以到达基本块$b$



**Definition 2. Pre-dominate Block**

作者也同样形式化定义了支配块(前驱块)的概念

给定一个基本块$b$，其支配块$D_b = {b'|b' \in B\  \& \  \exist\ g:(b',gb',b) \in T}$

直观上讲，基本块$b$的支配块$D_b$是可以一步转移到基本块$b$的基本块



**Definition 3. Labeled discrete-time Markov chain(DTMC)**

一个(标记的)离散时间马尔科夫链(DTMC)可表示为一个元组$M=(B,P_r,\mu)$

- $B$: $B$是$P$中所有基本块的集合
- $P_r$:  $P_r = B \times B \rightarrow R^+$是标记转移概率函数，对于所有的$b \in B$有 $\sum_{b' \in B} P_r(b, b') = 1$ 
- $\mu$：$\mu$是初始概率分布使得$\sum_{b \in B}\mu_b=1$

如果对初始程序施加初始分布，就可以将程序抽象成为一个DTMC。程序中每一个基本块都可以成为DTMC中的一个状态，并且每两个基本块之间的边都与一个条件概率相关。



**Definition4. Conditional Probability**

令$\#(b_1,b_2)$表示为模糊测试过程中基本块$b_1$转移到基本块$b_2$的次数；$\#b_1$表示基本块$b_1$的执行次数；$n$是ICFG中基本块$b_1$的出度。

则基本块$b_1$转移到$b_2$的条件概率为 $P_r(b_1,b_2)=\frac{1+\#(b_1,b_2)}{\#b_1+n}$

作者在分子和分母上分别添加1和$n$，这样做的意义是即使$b_1$和$b_2$一次都没有执行过，在使用拉普拉斯变换时会将边缘转移概率估计为$\frac{1}{\#b_1+n}$而不是0，方便后续计算奖励



**Definition 5. Reward of a basic block**

定义基本块$b$的奖励为 $R_b$，其中$b \in B$；定义基本块$t$为基本块$b$一步可以到达的基本块，其中$t \in T$，有方程组

$R_b =\begin{cases} 1+\sum_{t \in T}\{P_r(b,t)\times R_t\},&if\ b \notin visited  \\ \sum_{t \in T}\{p_r(b,t) \times R_t\}, &if b \in visited \end{cases}$

对于无法使用静态提取的间接调用，作者选择使用Fuzz的数据来动态补充ICFG



**Definition 6. Convert seed file into a series of vector**

作者将种子文件转化为变量$XD\times N=<v_1,v_2,...,v_n>,v_{m_{D\times1}},v_{p_{D\times1}}$

- $D$: $D$是字节嵌入的维度
- $N$: $N$是种子文件的最大长度
- 





## 整体框架

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

- 数据收集阶段：收集运行中的所使用的种子文件和突变算子，并且使用bitmap来收集覆盖率信息
- 奖励计算阶段
- 模型训练阶段
- 变异策略更新阶段



作者首先使用Fuzzer来收集和跟踪相关执行数据，主要包括执行过程中使用的种子文件、变异方法和每次执行所覆盖的范围，当模糊测试的覆盖增长陷入到瓶颈的时候激活ATTFuzz。

ATTFuzz的主要思想是采用深度学习的方法，预测种子和变异的组合是否可以覆盖到某些基本块。为了避免为每个基本块进行训练的数据不足和开销过大的问题，作者采用标记过后的离散时间马尔科夫链的形式构建程序的抽象。而后基于离散时间马尔科夫链寻找支配块，最后获取不同变异算子下种子的热图，最后通过训练注意力模型来指导选择更有价值的字节和更合适的变异算子进行变异直到克服当前瓶颈。



作者首先根据**Definition 4**和**Definition 5**来确定每个基本块的奖励，而后根据**Definition 6**来将种子文件抽象成为一个向量，而后根据目标的不同，使用不同的神经网络提取其特征(图像使用CNN，文本格式使用RNN)，然后使用注意力层来将注意力权重分配到每个特征中，最后根据加权特征使用全连接层进行分类。