【论文阅读】Sleuth: A Switchable Dual-Mode Fuzzer to Investigate Bug Impacts Following a Single PoC

(1) Crash Analyzer（崩溃分析器）与 Crash Summary（崩溃摘要）#

为了不盲目探索，我们需要一种机制来评估当前崩溃点的”潜力”。Sleuth 引入了 Crash Summary，定义为一个元组 <P, (O, N)>：

• P (Crash Position)：崩溃位置。Sleuth 提取 ASAN 报告的堆栈帧并计算哈希，用来唯一标识控制流。
• (O, N)：O 是访问越界时相对于 victim 对象的偏移量（Offset），N 是访问的字节数。这俩参数代表了崩溃点当前的数据流状态。

例如，在列表 1 的第 17 行通过溢出缓冲区触发了崩溃。假设缓冲区的边界地址是 10，通过崩溃访问的地址是 15，并且能够读取 3 个字节。那么 P 的值是第 17 行，O 是 5，N 是 3。通常，一个 P 可能对应多个 (O, N) 对。

为什么这么设计？

这就好比给崩溃点做了一次指纹提取。如果 P 不变，但 (O, N) 变了，说明我们在同一个位置探索出了新的数据流状态，值得继续深挖（深度探索）。如果 P 和 (O, N) 都不变了，说明这个点挖干了，得换个地方（广度探索）。

(2) Static Analyzer（静态分析器）与 MRG#

广度探索时，怎么知道哪些未探索的代码区域最有可能隐藏着同一个漏洞的 Impact？靠瞎跑肯定不行。Sleuth 使用 LLVM 层的静态分析（基于 SVF 的指向分析和污点分析）构建了一个内存关联图 Memory-Relevant Graph (MRG)。

构建过程（参见上图）：

1. 污点分析 Taint Analysis：从初始崩溃点出发，把引起崩溃的变量作为 Source，反向追踪它的定义链（Definition Chain），直到追踪到没有新的定义为止。同时，向前追踪 Sink 点（读写访问），收集所有与这个内存对象相关的变量。以图 3(a) 为例：首先提取第 17 行的初始崩溃位置，并识别指针 dst 指向受害对象；然后将 dst 作为源位置，向回追踪到第 13、12、2 行这些定义的位置，定义的变量 dst、in、out 指向相关的内存对象（图 3b)；最后执行正向分析，并识别第 20 行和 29 行可能包含潜在影响。
2. 级别分布 Level Distribution：追踪出来的节点太多了，得有优先级。论文设计了一个 Level 公式。简单来说，如果两个变量之间有数据流依赖，说明它们”距离近”；距离初始漏洞对象越近的代码块，触发同一个漏洞的概率越高。在污点分析之后，执行层级分布过程，构建一个仅包含与内存相关对象定义和使用位置的记忆相关图（MRG）。

$L(e) = \begin{cases} 1 & e.n_j = t \\ 1 & e.n_i \vDash t \rightsquigarrow n_i \\ \min(L(e_{pre})) + 1 & \text{other causes} \end{cases}$

翻译一下就是： 既然这个内存对象是导致崩溃的元凶，那么任何跟它有数据流交集的代码块，都是潜在的”犯罪同伙”，我们按照亲疏关系（Level）给它们排个优先级。这样 Fuzzer 在广度探索时，就能优先跑向那些”嫌疑最大”的代码块。

最后，通过 LLVM Pass 把 MRG 的信息（Level 等）插桩到程序的基本块（Basic Block）中。

代码插装#

代码插装的目的是把 MRG 变成 Fuzzer 能吃的覆盖率。

先说为什么不能直接用 AFL 那套 edge coverage。

AFL 的 edge coverage 本质是记录 prev_loc ^ cur_loc，也就是”上一个基本块到当前基本块”的跳转。但 Sleuth 的 MRG 里，一条边连接的两个基本块很可能在 CFG 上根本不相邻，中间隔了十万八千里。你没法用传统 prev_loc 去表示”我是从 MRG 里的哪个起点走到这个终点的”。

所以 Sleuth 自己设计了一套插桩算法，也就是论文里的 Algorithm 1: Memory-Relevant Instrumentation：

算法输入输出：

• 输入：目标程序 P，以及预分析阶段生成的 memory-relevant graph G。
• 输出：插桩后的程序。

先看伪代码：

1
Input: target program P, and memory-relevant graph G
2
Output: instrumented program P
3
1  BB ← ∅
4
2  Level ← {}
5
3  InFlow ← {}
6
4  E ← get_edges(G)
7
5  for e ∈ E do
8
6      insert Level[e] ← get_level(e, G)
9
7      bb_end, bb_start ← get_basic_block(e)
10
8      BB ← BB ∪ bb_end ∪ bb_start
11
9      insert InFlow[bb_end] ← bb_start
12
10 for b ∈ InFlow[i], 0 ≤ i < len(InFlow) do
13
11     P ← instrument_global(b, s, 0)
14
12 for f ∈ P do
15
13     for b ∈ f do
16
14         if b ∈ BB then
17
15             P ← instrument_tag(b, random())
18
16 for b ∈ f do
19
17     if b ∈ InFlow then
20
18         P ← instrument_cov(tag(b), tag(InFlow[b]), Level)
21
19 return P

翻译一下：

第 1-4 行：初始化。

• BB 用来收集所有涉及到的基本块。
• Level 存每条 MRG 边的 level，也就是”这条边离漏洞对象有多近”。
• InFlow 是一个 map，记录每个 bb_end 可能从哪些 bb_start 过来。
• E 是 MRG 里所有边。

第 5-9 行：遍历 MRG 的每条边。

对每条边 e：

• 拿到它的 level，塞进 Level[e]。
• 找到这条边的起点基本块 bb_start 和终点基本块 bb_end。
• 把这两个基本块都加入 BB 集合。
• 在 InFlow 里记录：bb_end 的前驱包含 bb_start。如果 bb_start 和 bb_end 是同一个基本块，论文说 Sleuth 不会保留这个 bb_start，避免自环干扰。

第 10-11 行：给每个 bb_start 插一个全局哨兵变量 s，初始值为 0。

这个 s 就是”执行标记”。程序跑到这个基本块，就把 s 置 1；没跑到就还是 0。后面在 bb_end 处要靠它来判断”这次执行到底有没有经过某个前驱”。

第 12-15 行：给 BB 里的每个基本块插一个随机 tag。

tag(b) 就是一个随机数，用来唯一标识基本块 b。你可以把它理解成基本块的身份证号。

第 16-18 行：在边级别插桩 instrument_cov。

对每个 bb_end，Sleuth 会插一段 coverage 计算逻辑。它读取所有可能前驱 bb_start 的哨兵 s，如果某个前驱执行过，就把它的 tag 贡献出来。最终得到一个值，表示”这次执行是从哪些 MRG 起点到达了这个终点”。

具体的覆盖率公式是：

1
tag(bb_end) ⊕ (tag(bb_start_1) ∧ bb_start_1 → s)
2
           ⊕ ...
3
           ⊕ (tag(bb_start_n) ∧ bb_start_n → s)

这里：

• bb_start_i → s 就是前面插的全局哨兵，执行过是 1，没执行是 0。
• tag(bb_start_i) ∧ (bb_start_i → s)：如果这个前驱执行过，就保留它的 tag；没执行过，就变成 0。
• 全部异或起来，再和 tag(bb_end) 异或，得到当前 bb_end 的 MRG 覆盖指纹。
• 因为一个 bb_end 可能对应多条 MRG 边，每条边有自己的 level，Sleuth 取这些边里最小的 level 作为这个 bb_end 的 level。

举个具体例子：

假设 bb_end 有两个前驱 bb_start_A 和 bb_start_B，tag 分别是 0x1234 和 0x5678。本次执行只经过了 A，没经过 B：

• A 的哨兵 s = 1，B 的哨兵 s = 0。
• 计算：tag(end) ^ (0x1234 & 1) ^ (0x5678 & 0) = tag(end) ^ 0x1234。
• 这样 Fuzzer 就能区分”从 A 来”和”从 B 来”。如果两个都经过，就异或两个 tag，得到另一个不同的值。

Fuzzer 看到新的 cov 值，就知道发现了一条新的 MRG 边覆盖。

核心逻辑是：Sleuth 用”全局哨兵 + 随机 tag + 异或”把 MRG 里那些不相邻的边，压成了一个 Fuzzer 能识别的 coverage 值，同时把 level 打包进 map，让广度探索知道该往哪跑。

动态切换策略 (Switching Strategy)#

预分析阶段结束后，程序已经被插桩，Crash Summary 和 MRG 信息也都有了。接下来就是 Fuzzing 循环。

Sleuth 要解决的核心问题是：什么时候继续深挖当前崩溃点？什么时候放弃，去别处找新崩溃点？

它不靠静态分配时间，而是靠一个 Monitor 持续观察 Crash Summary 的变化。

Sleuth 在 Fuzzing 循环里挂了一个 Monitor 组件，它持续监控两个指标：

• τ：距离上一次发现新崩溃位置 P 的时间间隔。
• ε：距离上一次发现新的 (O, N) 对的执行间隔。

状态机逻辑如下：

• 初始默认是深度探索模式。
• 如果 τ > maxTime（默认 8 分钟）或 ε > maxExec（默认 50000 次执行），且没有发现新的 Crash Summary，说明当前崩溃点已经被榨干了，Monitor 触发切换，进入广度探索模式。
• 在广度探索模式下，一旦发现了新的崩溃位置 P（说明找到了新的可探索点），立刻切回深度探索模式。

双模式探索 (Dual-Mode Exploration)#

两个模式下，种子队列的保留和选择策略是截然不同的：

• 种子保留：哪些变异结果有资格进入队列。
• 种子选择：下一轮从队列里挑哪个种子去变异。

这套组合的逻辑非常清晰：深度模式死磕数据流，广度模式借着静态分析的指引去扩宽控制流。

• 插桩解决的是”MRG 边怎么表示成 Fuzzer 能吃的 coverage”；
• 切换策略解决的是”什么时候换模式”；
• 双模式调度解决的是”换模式后选哪些种子”。