摘要：现有的灰盒模糊测试工具（Greybox Fuzzers，简称GF）在测试引导性方面存在明显不足，比如难以有效地将测试引导至特定的高风险变更或补丁、关键系统调用、危险代码位置，或是试图重现漏洞时涉及的堆栈追踪中的相关函数。为此，有研究者提出了“定向灰盒模糊测试”（Directed Greybox Fuzzing，简称DGF）的概念，其核心目标是生成能高效触达指定程序位置的输入。为实现这一目标，他们设计了一种基于模拟退火策略的能量分配机制：该机制会逐步给予更接近目标位置的测试用例（种子）更多的执行机会（能量），而对距离目标较远的种子则降低优先级。在实验中，研究人员基于该方法实现了名为AFLGo的工具，结果显示DGF不仅优于传统的无方向灰盒模糊测试，同时在效果上也超越了依赖符号执行的定向白盒模糊方法。该方法还被用于补丁验证和崩溃复现等场景，并已集成进Google的持续模糊测试平台OSS-Fuzz。由于具备明确的定向性，AFLGo在多个已被广泛模糊测试、具安全敏感性的项目（如LibXML2）中发现了39个漏洞，其中17个获得了CVE编号。
白盒模糊测试：是一种基于程序内部信息（如源码或字节码）进行输入生成的模糊测试方法。它通常结合程序分析技术（如符号执行、抽象解释或路径约束求解）来系统性探索程序路径，目的是最大化代码覆盖并触发潜在缺陷。需要源码或中间表示
灰盒模糊测试：是一种在不知道完整程序逻辑的前提下，通过轻量级运行时插桩收集反馈信息（如路径覆盖）来指导输入生成的模糊测试方法。它在效率与效果之间寻求平衡。不需要源码，仅需可执行文件并配合插装机制
黑盒模糊测试：是一种完全不依赖程序内部结构，仅依赖输入输出行为的模糊测试方法。它通过盲目地变异输入并观察程序响应来发现异常行为。不需要源码或执行信息
代码插装：在程序的原始代码或中间表示中，插入额外的代码或逻辑，以在程序运行时收集特定信息或实现特定目的的技术。它通常用于调试、性能分析、安全检测、测试覆盖率评估、模糊测试等场景。静态插装需要源码，动态插装不需要源码
引言
灰盒模糊测试（Greybox Fuzzing，简称GF）被广泛认为是当前漏洞检测领域的主流技术。该方法通过轻量级插桩手段，在几乎不影响程序性能的前提下，为每个输入所覆盖的执行路径分配一个唯一标识。模糊测试过程中，新输入通过对初始种子输入进行变异产生，若这些新输入触发了此前未覆盖或具有探索价值的路径，就会被加入模糊器的待测队列。AFL作为该技术的代表工具，不仅在实际应用中揭示了大量高危漏洞，还曾成功从“空白输入”生成结构合法的图像文件，并吸引了大量安全研究人员参与其功能扩展与改进。引出灰盒模糊测试
然而，现有的灰盒模糊测试工具在测试引导方面依然存在明显局限。具备引导能力的模糊测试器对于安全研究人员而言是一种重要的辅助工具，定向灰盒模糊测试。与传统的无方向模糊测试不同，定向模糊器会将大部分测试资源集中用于抵达特定的目标位置，避免将计算能力浪费在与目标无关的程序部分上。这类工具通常适用于一些特定场景：
- 在补丁测试中，可以将变更语句设定为模糊测试的目标位置，以“心脏出血”漏洞的引入为例，其相关的提交记录明确展示了这一问题。如果模糊器能够聚焦于这些具体改动位置，便有更高的可能性发现由修改引发的功能回退或安全缺陷。
- 崩溃复现场景中，可以将堆栈追踪中的方法调用位置设为测试目标。当线上环境出现崩溃问题时，开发团队通常只能收到堆栈追踪信息和部分运行环境参数，而出于用户隐私保护的考虑，具体触发崩溃的输入数据往往无法获取。此时，定向模糊测试工具能够帮助内部团队快速重现问题，从而定位和修复故障源头。
- 静态分析报告验证中，可以将静态分析工具标记为潜在风险的语句位置设为模糊测试目标。以某个工具识别出第1480行代码可能存在缓冲区溢出为例，定向模糊器能够生成特定输入，验证该隐患是否真实存在，从而辅助确认漏洞的可达性和实际影响。
- 信息流检测场景中，也可以将敏感源和敏感汇作为模糊测试的目标位置。为了发现数据泄露类漏洞，安全研究人员通常希望构造出既能触发包含隐私信息的敏感数据源，又能到达将数据暴露给外部环境的敏感汇的执行路径。定向模糊器在这一类任务中表现出较高的效率，能够有效生成所需的执行流程，从而揭示潜在的敏感信息泄漏风险。
目前，大多数定向模糊测试工具仍以符号执行为核心方法。符号执行是一种白盒模糊测试技术，它结合程序分析与约束求解，能够合成出覆盖不同程序路径的输入。在实现定向模糊测试器时，符号执行因其系统化的路径探索能力，一直是被优先采用的技术手段。假设在控制流图中存在一条通往目标位置的路径π，符号执行引擎可以为这条路径构造出一个路径条件，即一阶逻辑公式φ(π)，该公式在且仅在所有能够覆盖路径π的输入上成立。若该条件可满足，SMT（可满足性模理论）求解器便能生成一个实际输入t，作为公式φ(π)的解，从而使输入t成功触发包含目标位置的路径π。符号执行是一种白盒模糊测试技术，该技术需要源码
定向符号执行（DSE）将可达性问题转化为一个迭代求解约束的过程。由于大多数路径在实际中都是不可行的，因此搜索过程通常是通过逐步找到可行路径以接近中间目标来推进的。举个例子，补丁测试工具 Katch 使用符号执行引擎 Klee 来尝试到达某个被修改的代码语句。如果将图 1 中的第 1480 行设为目标，Katch 可能首先找到了一条可行路径 π₀，该路径可以到达第 1465 行这个中间目标。接下来，Katch 会将路径 π₀ 所对应的约束条件 φ(π₀) 与条件 (hbtype == TLS1_HB_REQUEST) 一起提交给约束求解器，以生成一个能够真正触达第 1480 行目标位置的输入。与灰盒模糊测试工具不同，基于符号执行的白盒模糊测试方法在实现定向模糊测试时，具备天然的便利性。
然而，DSE 的有效性是以效率为代价的。它在每次迭代中都需要耗费大量时间进行繁重的程序分析与约束求解。具体来说，DSE 通过程序分析找出那些需要被反转的分支，以便更接近目标位置；然后，根据这些路径上的指令序列构建路径条件；最后，使用约束求解器判断这些条件是否可满足。而在 DSE 生成一个输入的时间内，灰盒模糊测试工具可以执行数量级多得多的输入。这就为开发轻量级且具备定向能力的灰盒模糊测试工具提供了机会。以相同的初始输入为起点，当目标是图 1 中的某次提交时，定向灰盒模糊器 AFLGo 能在不到 20 分钟内触发 Heartbleed 漏洞，而 DSE 工具 Katch 即使运行 24 小时也无法触发该漏洞。定向灰盒模糊测是效率更高
这项研究提出了一种名为定向灰盒模糊测试（DGF）的方法，其核心目标是引导模糊测试尽可能地接近程序中的特定目标位置。从整体上看，DGF 将可达性问题建模为一个优化问题，并借助特定的元启发式算法来最小化生成输入与目标之间的“距离”。为计算这一“种子距离”，方法首先会静态计算并插装每个基本块到目标位置的距离。尽管这种距离度量是跨过程的，但其新颖之处在于，仅需对整个调用图进行一次分析，并分别对每个过程内控制流图分析一次即可。在运行时，模糊器会收集每个被执行的基本块的距离值，并通过求平均得到当前输入的种子距离。为了最小化该距离，DGF 所采用的元启发式方法是模拟退火，并通过“功率调度”机制实现。功率调度决定了每个种子的能量，也就是用于模糊测试该种子所花费的时间。与所有灰盒模糊技术类似，DGF 通过将分析工作转移到编译阶段，从而有效降低了运行时的开销。
与现有的定向白盒模糊测试方法不同，DGF 将程序中目标位置的可达性问题转化为一个优化问题，而传统方法则是将这一问题建模为一个迭代的约束求解过程。
研究动机
以 Heartbleed 漏洞为案例和出发点，研究者探讨了定向模糊测试的两种不同实现路径。传统上，定向模糊测试通常依赖于符号执行方法。在这里，研究对比了基于符号执行引擎 Klee 的补丁测试工具 Katch 与本文提出的定向灰盒模糊测试实现 AFLGo，后者正是基于灰盒策略开发的一种新型定向模糊工具。
Heartbleed漏洞：（CVE-2014-0160）是一种严重漏洞，它破坏了通过被认为是安全的协议（如 SSL/TLS）传输的数据的机密性与完整性。图 1 展示了引入该漏洞的提交代码片段。值得注意的是，Heartbleed 的利用不需要中间人攻击（MITM）。设想一个场景：Bob 持有一个秘密，而攻击者 Mallory 试图获取它。Bob 首先从 Mallory 发来的消息中读取消息类型和负载数据；如果该消息属于特定类型，Bob 会将响应消息的类型与负载设置为相同。随后，Bob 会将负载字段指定数量的字节从输入消息（pl）复制到输出消息（bp）中。如果 pl 实际分配的空间小于负载字段所声明的长度，Bob 就可能在复制过程中将自己的秘密一并泄露出去。Heartbleed 在被引入 OpenSSL 库两年后才被发现，期间这一漏洞已经被广泛传播。截至 2016 年 4 月，仍有约 25 万台设备处于易受攻击状态。
补丁测试：Heartbleed 漏洞是在 2011 年新年前夕被引入的，源于一次实现名为 Heartbeat 的新功能的提交（编号 4817504d）。如果当时使用一种以变更语句为目标位置的定向模糊测试工具，或许就能在漏洞被引入时及时发现，从而避免其大范围传播。如今，OpenSSL 的代码规模已接近 50 万行，而引入该漏洞的那次提交仅新增了 500 多行代码。显然，在整体代码中只有少量最近变更部分可能存在缺陷的情况下，对整个 OpenSSL 进行无差别的模糊测试无疑是一种资源浪费。相比之下，定向模糊测试能更高效地聚焦这些新增或修改部分。当前，大多数补丁测试工具都采用定向符号执行的方法，例如 Katch、PRV、MATRIX、CIE、DiSE，以及 Qi 等人提出的测试工具。其中，Katch 被广泛认为是自动化补丁测试领域的代表工具，且易于获取，因此被选作动机示例中的比较对象。
尽管基于定向符号执行的白盒模糊测试在效果上表现出色，但其代价也极其高昂。由于依赖重量级的程序分析过程，像 Katch 这样的工具在生成有效输入时往往耗时较长。在实际实验中，Katch 在 24 小时内都无法检测出 Heartbleed 漏洞。AFLGo 是一种高效的定向灰盒模糊测试工具，每秒可生成并执行数千个输入，在不到 20 分钟的时间内就能触发 Heartbleed 漏洞。它所实现的定向灰盒模糊测试技术几乎不依赖运行时程序分析，仅在编译或插桩阶段进行轻量级分析。定向灰盒模糊测是效率更高
研究内容
定向灰盒模糊测试（DGF）是一种以用户指定的目标位置为导向的漏洞检测技术，在保持灰盒模糊测试高效性的同时，避免了运行时程序分析的开销——所有相关分析都在编译阶段完成。这种方法易于并行扩展，便于根据计算资源的变化动态分配任务。此外，DGF 支持同时指定多个目标位置，并引入了一种跨过程的距离度量方式，用于衡量测试输入与目标位置之间的接近程度。这一距离在插桩阶段就被预先计算完毕，运行时可高效读取。虽然该距离度量覆盖多个过程，但其程序分析实际是基于调用图（CG）与过程内控制流图（CFG）进行的过程内分析，相比真正的跨过程分析可实现平方级别的性能节省。CG 与 CFG 都可以直接从 LLVM 编译框架中获取。基于这一新颖的距离定义，DGF 进一步提出了一种新的功率调度策略，并引入模拟退火中的经典指数冷却机制。该机制会逐步为更接近目标位置的种子分配更多能量，而对距离较远的种子则减少资源投入，从而更有效地引导模糊测试过程。
灰盒模糊测试
为了阐明定向灰盒模糊测试的实现方式，研究首先介绍了灰盒模糊测试的基本原理，并指出了距离插桩与基于退火的功率调度机制在其中的具体实现位置。“模糊测试”这一术语起源于 1990 年代，当时 Miller 等人使用随机测试工具对 UNIX 工具的可靠性进行了研究。如今，模糊测试根据程序分析程度的不同通常分为三类：（1）黑盒模糊测试不依赖任何程序内部信息，只需能执行程序本体即可；（2）白盒模糊测试则依赖符号执行，涉及复杂的程序分析与约束求解；（3）灰盒模糊测试介于两者之间，它通过轻量级的插桩手段获取程序的部分结构信息。在没有程序分析负担的前提下，灰盒模糊测试通常比白盒测试更高效；而在获取部分内部结构信息的基础上，它的有效性也往往优于完全盲目的黑盒模糊测试。
以 AFL 和 LibFuzzer 为代表的基于覆盖信息的灰盒模糊测试器（CGF）通常通过轻量级插桩来获取程序的覆盖情况。例如，AFL 的插桩机制能够记录基本块之间的跳转关系，以及大致的分支命中次数。这类模糊器会依据覆盖信息来判断哪些输入应被保留用于进一步模糊测试、接下来应选择哪个输入进行变异，以及为每个输入分配多少测试时间。在此基础上，研究者对插桩机制进行了扩展，使其还能记录每个选中种子与预设目标位置之间的距离。为了计算这种距离，需要在调用图和过程内控制流图中查找目标节点的最短路径，这些结构可以直接从 LLVM 中获取。最短路径分析采用的是经典的 Dijkstra 算法实现。
算法 1 展示了基于覆盖信息的灰盒模糊测试（CGF）的基本工作流程。模糊器接收一组初始种子输入 S，并在一个持续循环中不断从中选择输入 s，直到达到超时时间或测试被终止。输入选择的过程由函数 chooseNext 实现，例如，AFL 的策略是按添加顺序从一个循环队列中依次选取种子。选定输入 s 后，CGF 会通过 assignEnergy（第 3 行）计算该输入应生成的新测试用例数量 p，该步骤中也融入了基于模拟退火的功率调度策略。随后，模糊器根据预定义的变异操作对 s 进行随机修改，生成 p 个新输入，变异逻辑由 mutate_input（第 5 行）实现。AFL 常用的变异策略包括位翻转、简单算术运算、边界值替换以及代码块的插入与删除等。如果某个新输入 s′ 能覆盖新的分支，就会被加入循环队列（第 9 行）；若 s′ 导致程序崩溃，则将其加入崩溃输入集合 S✗（第 7 行）。如果该崩溃输入具有特异性，还会被标记为“唯一崩溃”，用于后续分析。
Böhme 等人指出，基于覆盖的灰盒模糊测试（CGF）可以被建模为一个马尔可夫链。在该模型中，状态 i 表示程序中的一条具体执行路径，而从状态 i 转移到状态 j 的概率 pij 表示：对一条路径 i 上的种子进行模糊变异后，生成的新种子执行路径 j 的可能性。研究发现，CGF 工具会明显更频繁地执行某些“高频路径”，而其他路径则较少被覆盖。马尔可夫链的平稳分布密度形式化地描述了模糊器在经过若干轮测试后某条路径被触发的概率。为了解决高频路径过度占用资源的问题，研究者提出了一种方法，通过根据路径邻域的密度调整每个种子生成的新输入数量，从而引导模糊器更多地探索低频路径。这一策略被集成进 AFL 的衍生版本 AFLFast 中。在此框架下，每个种子 s 所生成的新输入数量被称为该种子的“能量”，其大小由“功率调度”机制决定。需要注意的是，能量是马尔可夫链中局部状态的属性，而与之相对的模拟退火中的“温度”则是一个全局属性。能量对应每个种子生成的新输入的数量