跳转到内容
Jason's Study

AFLFast — 灰盒 Fuzz 的马尔可夫调度

是什么

AFLFast（CCS 2016）把 coverage-based greybox fuzzing 形式化为马尔可夫链：种子选择、能量分配、变异策略对应状态转移，指出现有 AFL 在探索新路径上效率不均。作者提出**能量调度（power schedule）**等改进，在相同时间内发现更多独特路径与 bug，影响 AFL++、libFuzzer 等后续调度器设计。

日常类比：fuzz 像撒网捕鱼；AFL 均匀撒；AFLFast 像看鱼群雷达——哪片水域（种子）更可能还有新鱼（新覆盖），就多撒几网。

为什么重要

现代 fuzz 的算法层入门：

  • 与 cadar-klee-2008：符号执行深但慢；AFLFast 快且可扩展
  • OSS-Fuzz / 内核安全默认 fuzz 引擎的理论参照之一
  • 理解 power schedule：为何某些种子被反复变异
  • 安全 CI：合并前跑 fuzz 是工业常规

核心要点

  1. Greybox：轻量插桩得覆盖反馈，无 heavy SMT。

  2. 种子队列：发现新覆盖的输入入队，优先变异。

  3. 马尔可夫视角：选种 + 变异 = 状态转移；平稳分布影响效率。

  4. 能量函数：按路径稀有度、深度分配变异次数（AFLFast 核心）。

  5. 与 AFL++：实现细节演进；思想是「非均匀调度」。

实践案例

案例 1：AFL 基础跑

Terminal window
afl-gcc -o parse parse.c
afl-fuzz -i in/ -o out/ -- ./parse @@

观察 queue 中 favored 种子。

案例 2：对比 uniform vs power schedule

同 binary、同时间预算，比 edges_found、unique_crashes。

案例 3：与 libFuzzer 结构 fuzz

对解析 API LLVMFuzzerTestOneInput；调度不同但覆盖反馈同源。

案例 4：补丁验证

对修复 CVE 的 commit 跑 fuzz 回归，确认新路径触达修复点。

案例 5：与双千 atlas 交叉阅读

写完本篇后，在 projects-atlas / papers-atlas 中打开同子类邻居各 1 篇，对比「实践案例」段是否覆盖：安装、最小命令、排障三条。缺一则补进你自己的实验笔记（不必改站正文）。

踩过的坑

  1. 字典与语料：无 seed 质量，调度救不了。

  2. 慢目标：超时设置不当会饿死队列。

  3. 非确定性：多线程目标 fuzz 结果抖；要单线程或 harness 隔离。

  4. 覆盖等价：边覆盖不等于安全；要 triage crash。

  5. 与 symex 二选一：大程序常 hybrid。

  6. 行数与模板：交付前用 quality-gate 扫一遍，避免关联链到未写 slug。

适用 vs 不适用场景

适用：

  • C/C++ 解析器、媒体编解码、网络协议 fuzz
  • 安全回归与 OSS 持续 fuzz
  • 学习现代 fuzz 调度

不适用：

  • 纯 Python 业务逻辑（可用 atheris/hypothesis 另一类）
  • 需严格证明性质（形式化/符号）
  • 无源码二进制-only（仍可用 QEMU 模式但更难）

历史小故事（可跳过）

  • 2013：AFL 发布改变安全测试文化。
  • 2016：AFLFast CCS 发表。
  • 2019+：AFL++ 集成多种 schedule。
  • 2024+：Google OSS-Fuzz 每日跑无数 harness。

学到什么

  • Fuzz 效率 = 反馈 + 调度算法。
  • 马尔可夫建模给启发式提供语言。
  • 与 cadar-klee-2008 组成动静态安全测试双壁。
  • 覆盖是代理目标，crash 才是一等公民。
  • 读论文能解释 AFL++ 文档里「power」参数。
  • 复习时可对照 atlas 枢纽与 written.txt 邻居 slug，检查双向链接是否闭环。
  • 动手跑通一个最小示例，比只读 README 更能记住参数含义与失败模式。
  • 把本文档当「面试前 10 分钟速览卡」：是什么 → 为什么 → 一个命令/实验。
  • 教别人时用「日常类比 + 一条命令」结构，反馈最好；复杂架构图留给二读。
  • 若关联 slug 尚未落站，先用纯文本记名，sync-written 后再改成 [[wikilink]]。

延伸阅读

关联

维护备注

  • 与专题路线图对照：确认 frontmatter 分类/子分类 与 research 表一致，避免 atlas 统计漂移。

  • 代码块尽量可拷贝运行；路径用占位符 /path/to 标注，避免泄露本机目录。

  • 写关联时优先已存在于 data/written.txt 的 slug，减少幽灵链接。

  • 若从 worktree cherry-pick 合并，合并后再跑一次 npm run atlas 刷新反向链接。

  • 本篇目标行数 150–200，与 study v3 quality-gate 对齐；扩写时优先加「实践案例」与「踩过的坑」，少堆外链。

  • 若 pipeline 复审要求 refine，只改被点名的 H2 段，避免整篇重写导致关联漂移。

反向链接