🤔



# 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)，然后使用注意力层来将注意力权重分配到每个特征中，最后根据加权特征使用全连接层进行分类。

[Paper] Better Pay Attention Whilst Fuzzing

[Misc] LLVM SanitizerCoverage分析

😅



# TargetFuzz: Using DARTs to Guide Directed Greybox Fuzzers



## 作者



## 现有做法

目前没有针对DFG的种子语料库或者种子选择方法，目前的主要工作都是基于覆盖率引导的模糊测试的语料库，这些语料库可能会给DFG带来负面影响。

> Q1: 有什么负面影响？

## 主要想法

提出了一个定向模糊测试种子库。

TargetFuzz 使用一种种子选择策略来选择 DART 语料库中的种子，该策略考虑了种子距离而不仅仅是代码覆盖率。该策略从一个大型种子库中选择与修改后的目标区域 "接近 "的种子子集。配备 DART 语料库的 DGF 工具将大部分模糊时间预算用于强调修改过的代码区域，而不是无关的程序组件。

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

- BSCG: 基线种子语料库生成器。由多个覆盖率引导的模糊测试器并行收集语料库，一般只有在初次运行或者目标程序发生重大变化时才会重新收集基线种子。
- SRA: 种子筛选。SRA对基线种子语料库进行筛选只保留产生相同代码覆盖率的最小种子集。
- TSS: 从累积的种子语料库中选择种子子集，并输出特定目标的种子语料库(DART语料库)。在选择 DART 语料库的种子时，TSS 会考虑种子距离，只选择与修改代码区域接近的种子。在模糊测试结束之后TargetFuzz会检测是否产生新的崩溃，而后将Fuzzer生成的新种子重新提供给SRA。



### BSCG

为了生成基线种子语料库，我们使用了四种不同的基于覆盖率的模糊器基于覆盖率的模糊器是 AFL [18]、Angora [8]、MOpt-AFL [32] 和 honggfuzz [21]。对于我们测试的每个软件，我们在一定的时间限制内使用每个模糊器运行单独的模糊测试会话。一旦模糊测试会话结束，我们收集每个模糊器输出队列中所有增加覆盖率的种子，并将它们组装到基线种子语料库中。