DGF Overview

定向灰盒测试相关技术核心策略时间顺序梳理速览

AFL(American Fuzzy Lop 2014)

传统灰盒：全图覆盖，无定向

变异策略

确定性：bit/byte flip（翻转）、整数加减、边界值、字典
随机叠加（Havoc）：纯随机组合多种变异操作（如插入、删除、替换）
拼接（Splicing）：将两个种子拼接后执行 havoc 变异

反馈引导策略

边覆盖率（Edge Coverage）：插桩追踪 CFG 边的命中情况，作为变异方向的反馈
上下文敏感边覆盖：区分同一 CFG 边在不同调用上下文下的命中情况，提升精度
路径覆盖（PathAFL）：记录完整路径哈希，避免路径碰撞
Ngram 插桩：记录最近前 N 个分支的历史状态

AFLGo （2017）

首次提出“定向”概念，距离制导。（DGF 的起点）

AFL（基于覆盖率引导）->AFLGo（定向制导）

距离度量（Distance Metric）

静态阶段

用 LLVM 生成调用图 CG + 过程间控制流图 ICFG。
对每个基本块到目标块跑 Dijkstra，算出最短路径长度 distance(b)。
一个种子到目标的距离取它所有覆盖块距离的 加权平均。
距离越小，优先级越高；距离为 0 表示已命中目标。

多目标扩展：若同时定向 N 个目标，可维护最小距离或平均距离两种模式（-m 选项）。

能量调度（Power Schedule）

AFLGo 把 AFL 的 perf_score 公式改造成 Simulated Annealing (SA) 形式，解决“过早收敛”与“局部最优”。

1
2
3


double T = 1.0 / pow(20.0, progress_to_tx);          // 温度随时间衰减
double p = (1.0 - normalized_d) * (1.0 - T) + 0.5*T; // 距离+时间双因子
perf_score *= pow(2.0, 2*log2(MAX_FACTOR)*(p-0.5));

总结一下模拟退火：早期系统鼓励探索，距离较远也给予能量（算力）；后期系统愈发挑剔，只给近距离种子变异机会。

种子队列管理

主队列（AFL ）：按覆盖率排队。
优先队列（AFLGo 新增）：按距离排序；每次 fuzz 80% 概率从优先队列取种子。

变异策略

确定性阶段（固定套路）
- 与 AFL 相同（bit/byte flip, arith, interest, dictionary）。
- 距离度量不会缩短确定性阶段，只是打分，保证兼容性。
Havoc / Splicing
- 距离越小的种子 获得的 havoc 轮次越多（由 power_factor 决定）。
- 对“已到达目标”的种子，AFLGo 会额外给 二次变异 机会，以探索目标附近的新分支（patch 回归测试常用）。

WindRanger（ICSE 2022）

核心是用“走错路口”指路：Deviation Basic Block（DBB）。

DBB 机制

静态找“一步错即永远到不了目标”的块
动态过滤：仅保留种子真实触发者（它在执行时真的走错的路口）

距离

仅累加 DBB 到目标的最短路径 × 难度系数（该系数青睐简单分支）

调度

Favored 队列（90 %）：按 DBB 距离排序
Less-favored 队列（10 %）：保留全局探索

Beacon（IEEE S&P 2022）

核心是运行时剪枝：Weakest Precondition。

核心

静态：推导最小充分条件 WP，插入 assert(WP)
动态：断言失败立即退出路径

代价

复杂循环下 WP 爆炸，静态耗时显著

注意：与 DAFL 的“非侵入”不同，Beacon会 修改被测程序 本体。

参考资料

Böhme, M., Pham, V.-T., Nguyen, M.-D., and Roychoudhury, A. 2017. Directed Greybox Fuzzing. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS ’17). ACM, New York, NY, USA, 2329–2344. https://doi.org/10.1145/3133956.3134020
Du, Z., Li, Y., Liu, Y., and Mao, B. 2022. Windranger: A Directed Greybox Fuzzer Driven by Deviation Basic Blocks. In Proceedings of the 44th International Conference on Software Engineering (ICSE ’22). ACM, New York, NY, USA, 2440–2451. https://doi.org/10.1145/3510003.3510197
Huang, H., Guo, Y., Shi, Q., Yao, P., Wu, R., and Zhang, C. 2022. Beacon: Directed Grey-box Fuzzing with Provable Path Pruning. In Proceedings of the 2022 IEEE Symposium on Security and Privacy (SP ’22). IEEE, 36–50. https://doi.org/10.1109/SP46214.2022.9833709
Zalewski, M. 2018. American Fuzzy Lop (AFL). GitHub repository, https://github.com/google/AFL