DGF Tool Energy Allocation Strategies

DGF工具能量分配策略一览

AFL

本节聚焦AFL 及其衍生工具在 seed fuzzing 过程中的能量分配策略（power schedule），即决定“从某个种子输入生成多少额外测试用例”的算法。以 AFLFast 提供的六种策略为基准，给出简明对比和使用建议。

参考：https://github.com/lhxdz/afl-mix?tab=readme-ov-file

ps：冷热程度指有多少其他输入已经跑过同一条路径

AFL 标志	策略名称	能量公式	核心思想	简言之
`-p fast`（默认）	FAST	$FAST$	指数放大低频路径能量，快速收敛	偏袒“冷门”路径，给的测试用例更多；热门路径反之
`-p coe`	COE (cut-off exponential)	$COE$	高频路径直接“断电”，资源全给罕见路径	检测到某路径太热门（超过平均值）就直接断电（0 个新用例），冷门路径才继续深究
`-p explore`	EXPLORE	$EXPLORE$	线性均衡，与路径频率无关	一视同仁，每个种子按 AFL 原始评分给能量，不看冷热。
`-p quad`	QUAD	$QUAD$	二次曲线惩罚高频路径	冷门路径奖励得更快（二次曲线），热门路径被二次方打压。
`-p lin`	LIN	$LIN$	线性惩罚高频路径	冷门路径奖励、热门路径惩罚都按线性比例，节奏比较温柔。
`-p exploit`	EXPLOIT (原生 AFL)	$LIN$	恒定能量，仅依赖 AFL 原始性能分	只按“跑得快不快、覆盖新不新”给能量，完全不考虑路径冷热。

符号释义

α(i)：AFL 原生性能评分（执行时间、块转移覆盖率等）
β：全局常数，防止能量爆炸
s(i)：种子 i 被 fuzz 的次数
f(i)：触发与 i 相同路径的输入总量
μ：所有路径的平均输入数

快速实践指南

单机 fuzz：保持默认 -p fast 即可。
并行集群：
- master 用 -p exploit 稳定产生种子；
- slaves 组合 -p coe / -p fast / -p explore 以覆盖低频路径。
若使用 AFL++，可直接在命令行追加对应 -p 参数，无需额外补丁。

AFLGo

与追求广覆盖的 AFL/AFLFast 不同，AFLGo 专为**定向灰盒模糊测试（DGF）设计，其能量分配核心在于“越靠近目标代码的种子，获得的 fuzz 轮次越多”。算法基于模拟退火（Simulated Annealing）**动态调节，公式与参数如下表所示。

AFLGo 变量	定义/作用
d(s,T)	种子 s 到目标集合 T 的平均基本块距离（静态分析得出，越小越近）
d̃(s,T)	归一化距离：d̃ = d / d_max ∈ [0,1]，0 表示最近，1 表示最远
T_exp	退火温度：T_exp = 20^(−t/tₓ)，t 为已用时间，tₓ 为“利用阶段”起始参数
p_afl(s)	AFL 原生能量（由执行速度、路径稀有度决定）
p(s,T)	退火比例因子：p = (1−d̃)·(1−T_exp) + 0.5·T_exp
E(s,T)	最终能量：E = p_afl(s) · 2^(2 log₂(MAX)·(p−0.5))，MAX≈30

根据格式可以得到能量分配规则

在时间较小时，温度影响较大，而距离影响较小
随着时间推移，T_exp 递减，距离影响较大
因此系统从“全局探索”逐步过渡到“局部深究”。

快速实践

编译：afl-clang-fast + -targets= 生成含距离信息的二进制。
运行：afl-fuzz 追加 -z targets.txt 即启用 AFLGo；无需额外 -p 参数。
并行：官方脚本自动为各实例划分不同目标区间，避免能量冲突。

Beacon

Beacon 是面向“混合符号执行引导的定向模糊测试”工具，核心目标是在最短 CPU 时间内到达用户指定的目标地址/断言。其能量分配策略以距离-稀缺联合权重（Distance-Scarcity Weight, DSW）为核心，同时引入梯度冷却（Gradient Cooling）机制抑制过度消耗。

关键公式与参数如下表所示。

Beacon 符号	定义/作用
d(s,t)	种子 s 到目标 t 的动态最短路径距离（插桩实时计算，单位：基本块数）
r(s)	稀缺度：r(s)=1/(hit(s)+ε)，hit(s) 为触发该种子路径的输入次数
α	距离权重系数，默认 0.7（用户可通过 `--alpha` 调整）
β	稀缺权重系数，默认 0.3（满足 α+β=1）
w(s,t)	联合权重：w(s,t)=α·d̃(s,t)⁻¹+β·r(s)；d̃ 为归一化距离
T(k)	梯度冷却温度：T(k)=w_max·e^(−k/k₀)，k 为当前轮次，k₀ 为冷却常数
E(s,t)	最终能量：E(s,t)=E₀·w(s,t)/T(k)，E₀ 为基准能量（默认 1000）

能量分配规则总结

越靠近目标（d 越小）且越罕见（r 越大）的种子，联合权重 w 越高；
随着 fuzz 轮次 k 增加，温度 T(k) 指数下降 → 高权重种子能量被进一步放大；
当 T(k) 接近 0 时，能量几乎只流向离目标最近的稀缺路径。

快速实践

编译：clang-beacon -targets=targets.txt 生成带距离插桩的二进制。
运行：./beacon-fuzz -i in -o out -t targets.txt [可选 --alpha=0.6]。
并行：官方脚本 beacon-parallel.py 自动为各实例分配不同 k₀ 值，避免冷却同步。

WindRanger

WindRanger 是面向多目标定向灰盒模糊测试（DGF）的工具，其核心创新在于“多级优先级队列 + 距离驱动能量分配”机制，可在一次 fuzzing 会话中同时逼近多个目标（偏差基本块 DBB），并确保测试资源向最易触发新路径的种子快速收敛。关键公式与参数如下表所示。

WindRanger 符号	定义 / 作用
DBB	Deviation Basic Block：待覆盖的目标基本块
d(s, DBB)	种子 s 到目标 DBB 的静态最短路径距离（单位：基本块数）
L(s, DBB)	为每个 DBB 维护的种子列表，按 d(s, DBB) 升序排序
Q₁	一级优先级队列：每个 DBB 对应列表头部种子（距离最近）
Q₂	二级优先级队列：同一 DBB 列表中剩余种子
E(s)	种子实时能量：E(s) = E₀ · (1 / (d(s, DBB)+ε))，ε 防止除零
T_select	队列选择策略：先耗尽 Q₁ 再取 Q₂，确保最近种子优先突变

能量分配规则总结

距离越短 -> 排序越靠前 -> 进入 Q₁ -> 获得高能量 E(s)；
距离越远 ->落入 Q₂ -> 能量随 d 线性衰减，甚至长期不被选中；
每轮 fuzz 只从当前最高优先级队列取种子，形成“探索→利用”过渡。

快速实践

编译：clang-windranger -targets=targets.txt 生成带 DBB 距离的二进制。
运行：./windranger-fuzz -i in -o out -t targets.txt
并行：官方脚本自动为不同 DBB 建立独立队列，避免队列间饥饿。

DAFL

DAFL（Data-dependency Aware Fuzzing with Lightweight slicing）是以数据依赖为核心的定向灰盒模糊测试工具。其能量分配机制在传统 AFL 能量公式基础上，引入语义相关性评分（semantic-relevance score）进行比例再缩放，使 fuzz 资源优先流向与漏洞触发点数据依赖更紧密的种子。

关键公式与参数如下表所示。

DAFL 符号	定义 / 作用
scr_s	种子 s 的语义相关性评分（由静态数据依赖切片计算得出，越大越相关）
scr_avg	当前种子池内所有种子的平均语义相关性评分
E_AFL(s)	AFL 原生能量（基于执行速度、路径稀有度等 AFL 传统因子）
E_DAFL(s)	DAFL 调整后能量：E_DAFL(s) = (scr_s / scr_avg) × E_AFL(s)
ε	极小常数，避免除零
种子池排序	每轮按 scr_s 降序重排，循环队列指针不重置，防止饥饿

能量分配规则总结

数据依赖越紧密（scr_s 越高）的种子，获得 E_DAFL(s) 线性放大；
依赖关系稀疏（scr_s 低）的种子，能量被等比例压缩；
每轮重新排序队列保证高相关性种子始终优先，且不会产生饥饿。

快速实践

编译：afl-clang-dafl -targets=targets.txt 生成带数据依赖插桩的二进制。
运行：./dafl-fuzz -i in -o out -t targets.txt（无需额外 -p 参数）。
并行：官方脚本 dafl-parallel.py 为不同目标 DBB 维护独立 scr_avg，避免跨目标干扰。

已知效果

与 AFLGo 相比，基于数据依赖的能量分配平均提速 1.27×；
与原生 AFL 相比，DAFL 平均复现时间缩短 1.93×，并解决 AFL 无法触达的 4 个超时案例。

DAFL实验消融/对比配置

配置名称	数据依赖切片	语义相关评分 scr_s	能量公式	种子池策略	适用场景 / 研究目的
DAFL_noasan	是	是	E = (scr_s/scr_avg)·E_AFL	动态重排	评估 ASan 运行时开销对能量分配的影响
DAFL_naive	否	否（直接scr_s=1）	E = E_AFL	动态重排	退化为传统 AFL，验证切片+评分带来的增益
DAFL_selIns	是	是	E = (scr_s/scr_avg)·E_AFL	动态重排	仅插桩数据依赖相关的指令，评估插桩开销与精度权衡
DAFL_semRel	否	是	E = (scr_s/scr_avg)·E_AFL	动态重排	关闭切片，验证语义评分单独贡献
DAFL_seedpool	是	是	E = (scr_s/scr_avg)·E_AFL	固定大小（1000）	评估动态种子池策略对覆盖率的影响
DAFL_energy	否	是	仅能量公式有效，不重新排序	无重排	验证排序机制与能量放大机制的独立贡献

使用示例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


# 完整 DAFL
CC=afl-clang-dafl make
./dafl-fuzz -i in -o out -t targets.txt

# 关闭 ASan
AFL_NO_ASAN=1 CC=afl-clang-dafl make
./dafl-fuzz -i in -o out -t targets.txt

# 退化为 AFL（naive）
AFL_DAFL_NAIVE=1 CC=afl-clang-dafl make
./dafl-fuzz -i in -o out -t targets.txt