😅



# 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]。对于我们测试的每个软件，我们在一定的时间限制内使用每个模糊器运行单独的模糊测试会话。一旦模糊测试会话结束，我们收集每个模糊器输出队列中所有增加覆盖率的种子，并将它们组装到基线种子语料库中。

[Paper] TargetFuzz: Using DARTs to Guide Directed Greybox Fuzzers

🤔



# Auto Off-Target: Enabling Thorough and Scalable Testing for Complex Software Systems



## 作者

- Tomasz Kuchta - 三星电子
- Bartosz Zator - 三星电子

> 二人长时间未在学术圈活跃



## 作者的思路

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

整体架构如图，作者主要解决的是传统的`OT`自动合成技术

> OT(off-target)技术: 其实就是harness自动合成，但是作者的初衷并不是针对于Fuzz进行改进而是将其余平台(MIPS、ARM)平台的部分C语言代码，通过AOT(Auto off-target)技术将其在保留数据流依赖关系的前提下迁移到x86平台上进行编译从而摆脱仿真的困扰而直接进行测试。

$Definition:$ 如果存在一个测试手机基带相关代码的需求，$old\ host$为原手机、$target$为基带协议栈、$off-target$为基带相关功能、$new\ host$为x86_64的主机。

$Definition:$ $build\ info$主要手机的事已编译文件、链接模块、使用编译器Flag的列表以及有关模块、源文件和中间文件之间的依赖关系，这些信息是在目标系统的完整构建过程中提取的。

$Definition:$ $code\ info$包括函数、类型、全局变量 （globals）、类型、全局变量和函数之间的引用的源代码，以及代码元数据，包括变量赋值、强制转换和结构类型成员取消引用。代码信息由代码处理器在构建信息或构建配置的帮助下从原始源文件生成



通过将所有的目标相关代码识别出来，作者提出了一种新的截止算法(Cut off)来决定保留哪些功能，去除哪些功能

$Definition:$ 被保留的的函数称为内部函数(Internal Functions)而被忽略的函数则称为外部函数(External Functions)

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

**传统问题:** 即使将一段目标函数的harness合成出来了，但是其参数的初始化仍然是个问题。

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

如上图，如果参数`y`未被正确初始化则在12行会造成空指针解引用问题，但是如果能够在原系统中正常初始化的话则不会出现这个问题，所以如果在12行发生崩溃则有可能是一个FP。



针对于这种情况作者提出了三种方法来自动化解决FP的问题。

**smart init:** 基于静态分析的启发式方法，该方法将自动识别相关的类型、全局变量和结构体并对其进行初始化。

> 同时AoT提供了一个可配置Json接口，供用户选择感兴趣的函数和参数并指定相关参数的初始化方案

智能启动算法主要基于对`类型转换(显式、隐式)、结构体成员的访问、offsetof操作符`进行hook，对于函数的每个输入参数，AoT 都会以类似于以 DFS 方式逐行读取代码的方式，解析有序的事件轨迹。从初始参数类型开始，AoT 会在遇到上述事件类型时相应地修改类型。

## 整体架构

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



## 复现流程

```bash
# CAS
$ sudo apt install git cmake libclang-dev python3-dev gcc-9-plugin-dev build-essential linux-headers-$(uname -r) python-futures flex bison libssl-dev
$ git clone https://github.com/Samsung/CAS.git && cd CAS
$ export CAS_DIR=$(pwd)
$ cd tracer && make && sudo make modules_install
$ cd $CAS_DIR && mkdir build_release && cd build_release
$ cmake -DCMAKE_BUILD_TYPE=Release -DCMAKE_C_COMPILER=clang-12 -DCMAKE_CXX_COMPILER=clang++-12 ..
$ make -j12 && sudo make install
$ export PATH=${CAS_DIR}:$PATH
$ etrace -w /home/test/Desktop/OT/Target -l ./compile.sh
$ cas parse
$ cas postprocess
$ cas cache
$ export PYTHONPATH=${CAS_DIR}:$PYTHONPATH
$ export CLANG_PROC=${CAS_DIR}/clang-proc/clang-proc
$ ${CAS_DIR}/examples/extract-cas-info-for-ftdb .nfsdb.img
$ ${CAS_DIR}/clang-proc/create_json_db -P $CLANG_PROC
$ ${CAS_DIR}/tests/ftdb_cache_test --only-ftdb-create db.json

# AoT
$ git clone https://github.com/Samsung/auto_off_target.git && cd auto_off_target
$ export AOT_DIR=$(pwd)
$ cd .. && cd libxml2
$ echo "{ \"BASserver\": \"https://localhost\" }" > cfg.json
$ export PYTHONPATH=${PYTHONPATH}:${CAS_DIR}
$ echo "[]" > init.json
$ ${AOT_DIR}/src/aot.py --config=cfg.json --product=libxml2 --version=0.0.1 --build-type=eng --import-json=db.json --rdm-file=rdm.json --init-file=init.json 
$ ${AOT_DIR}/src/aot.py --config=cfg.json --product=libxml2 --version=0.0.1 --build-type=eng --db=db.img --output-dir out_dir --functions xmlSnprintfElementContent --external-inclusion-margin 1 --init --verify-struct-layout

```

[Paper] Auto Off-Target: Enabling Thorough and Scalable Testing for Complex Software Systems

🤔



# 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表达式。我们将表达式的左值定义为预期关联的内存对象的内存位置。如果表达式是左值表达式，则表达式的右值为与内存对象相关联的值；如果表达式不是左值表达式，则表达式的右值表示为语义值。