💻 computer science

On Interaction Effects in Greybox Fuzzing

该论文提出了一种名为 MuoFuzz 的灰盒模糊测试工具，通过建模并学习突变算子之间的交互效应以动态选择最优突变序列，从而在代码覆盖率和漏洞发现能力上超越了 AFL++ 和 MOPT 等现有工具。

原作者： Konstantinos Kitsios, Marcel Böhme, Alberto Bacchelli

发布于 2026-04-24

📖 1 分钟阅读☕ 轻松阅读

原作者： Konstantinos Kitsios, Marcel Böhme, Alberto Bacchelli

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇文章介绍了一种名为 MuoFuzz 的新型软件测试工具，它的核心思想是：在寻找软件漏洞时，改变“动作”的顺序，效果会大不相同。

为了让你更容易理解，我们可以把软件漏洞测试（Fuzzing）想象成**“开锁”或者“烹饪”**。

1. 背景：传统的“乱试”方法

想象你面前有一把复杂的锁（也就是我们要测试的软件），你需要用各种工具（比如螺丝刀、铁丝、锤子等，对应软件里的32 种变异算子）去尝试打开它。

传统的做法（如 AFL++）： 就像是一个新手厨师，手里有一堆调料（突变算子）。他每次炒菜（测试）时，都是随机抓一把调料撒进去。比如，先撒点盐，再随机抓点糖，或者先切块再翻炒。他不管刚才撒了什么，下一次撒什么都是完全随机的，或者按照一个固定的比例来撒。
问题： 这种方法虽然也能偶尔做出美味佳肴（发现漏洞），但效率不高。因为有些调料搭配在一起（比如“先撒盐再放糖”）可能味道很好，而“先放糖再撒盐”可能就很难吃。传统方法忽略了这种**“搭配顺序”**的重要性。

2. 核心发现：顺序很重要（交互效应）

作者们做了一个大胆的实验：他们把 32 种工具两两组合，看看哪种组合能最快打开锁（发现新的代码路径）。

发现： 他们惊讶地发现，工具 A 紧接着工具 B 使用，和工具 B 紧接着工具 A 使用，产生的效果截然不同。
比喻： 就像做菜，如果你先“切肉”再“炒肉”，肉很嫩；如果你先“炒肉”再“切肉”，肉就老了。或者像开锁，先用“铁丝”试探锁芯，再用“锤子”敲击，可能比反过来更有效。
结论： 工具之间不是独立的，它们之间存在**“化学反应”**（交互效应）。

3. 解决方案：MuoFuzz（聪明的厨师）

基于这个发现，作者开发了一个叫 MuoFuzz 的新工具。它不再随机乱撒调料，而是学会了**“看前一步，定后一步”**。

它的学习过程（训练阶段）：
在开始正式测试的前几个小时，MuoFuzz 会像个勤奋的实习生。它会尝试各种组合，并记笔记：
- “哦，刚才用了‘工具 A'，紧接着用‘工具 B'，成功发现了新路径！”
- “刚才用了‘工具 A'，紧接着用‘工具 C'，没什么反应。”
  它把这些经验记在一个概率表里。
它的执行过程（引导阶段）：
正式测试开始后，MuoFuzz 就变聪明了：
- 如果它刚才用了“工具 A"，它会查表：“根据经验，接下来用‘工具 B'成功的概率最高！”于是它果断选择 B。
- 如果刚才用了“工具 C"，它可能会觉得“接下来用‘工具 D'比较好”。
- 比喻： 这就像是一个老练的侦探。如果他在现场发现了一个脚印（前一个动作），他就能推断出嫌疑人下一步最可能去哪里（下一个动作），而不是盲目地到处乱跑。

4. 实验结果：真的更有效吗？

作者把 MuoFuzz 和目前世界上最强的两个测试工具（AFL++ 和 MOPT）进行了对比。

AFL++： 随机撒调料（固定概率）。
MOPT： 虽然知道哪些调料好用，但它认为每种调料是独立的，只优化单个调料，不关心搭配顺序。
MuoFuzz： 知道“先 A 后 B"比“先 B 后 A"好。

结果：

覆盖率更高： 在 13 个测试程序中，MuoFuzz 有 10 个表现最好，覆盖了更多的代码区域。
发现更多漏洞： 它发现了 AFL++ 漏掉的 4 个漏洞，甚至发现了一个连 AFL++ 和 MOPT 都没找到的“隐藏彩蛋”（漏洞）。
速度更快： 达到同样的测试深度，MuoFuzz 花的时间更少。

5. 总结与启示

这篇文章告诉我们，在软件安全测试中，“怎么做”和“按什么顺序做”同样重要。

以前的思维： 只要我有足够的工具，随机组合总能撞大运。
现在的思维（MuoFuzz）： 我要学习工具之间的配合默契。就像优秀的乐队，乐手之间知道谁先谁后，才能演奏出最完美的乐章，而不是每个人只顾自己乱弹。

一句话总结：
MuoFuzz 就像是一个学会了“套路”的测试专家，它不再盲目乱撞，而是根据上一步的动作，智能地选择下一步的最佳策略，从而更高效地揪出软件里的 Bug。

论文技术总结：灰盒模糊测试中的交互效应 (On Interaction Effects in Greybox Fuzzing)

1. 研究背景与问题 (Problem)

灰盒模糊测试 (Greybox Fuzzing) 是一种通过变异种子输入来发现软件漏洞的自动化测试技术。以 AFL++ 为代表的现代模糊测试器通常包含 32 种预定义的变异算子（Mutators），如位翻转、字节删除、字典插入等。

核心问题：
现有的主流模糊测试策略（如 AFL++ 和 MOPT）在生成变异序列时，通常假设变异算子是相互独立的。

AFL++：使用固定的概率分布来选择变异算子。
MOPT：使用遗传算法优化每个变异算子的独立选择概率，但依然假设算子之间没有关联。

研究假设：
作者提出假设：变异算子之间存在交互效应 (Interaction Effect)。即，某个变异算子 $A$ 之后紧接着应用变异算子 $B$ ，产生“有趣输入”（覆盖新代码的输入）的概率，并不等于 $A$ 和 $B$ 各自独立概率的简单组合。如果利用这种交互效应，可以显著提高模糊测试的效率。

2. 方法论 (Methodology)

为了验证假设并解决该问题，作者提出了 MuoFuzz，一种能够学习并利用变异算子间条件概率的新型模糊测试器。

2.1 验证交互效应的存在 (RQ1)

作者首先通过实验验证交互效应是否存在：

数据收集：在 13 个目标程序上运行修改后的 AFL++。强制变异序列长度 $l=2$ ，并均匀随机选择变异算子对 $(i, j)$ ，统计每对算子产生的“有趣输入”数量 $N(i, j)$ 。
模型拟合：构建线性模型 $\hat{N}(i, j) = \mu + \alpha_i + \beta_j + \gamma_{ij}$ 。其中 $\gamma_{ij}$ 代表算子 $i$ 和 $j$ 之间的交互项。
统计分析：使用双因素方差分析 (Two-way ANOVA) 检验交互项 $\gamma_{ij}$ $γ_{ij}$ 的显著性。
- 结果：在绝大多数目标程序中，交互项解释了显著的方差 ( $p < 0.0001$ )，证实了变异算子之间存在显著的交互效应。

2.2 MuoFuzz 的设计 (MuoFuzz)

基于上述发现，MuoFuzz 采用两阶段策略来生成变异序列：

阶段一：训练阶段 (Training Phase)

目标：学习条件概率 $Pr(m_n = j | m_{n-1} = i)$ ，即在已知上一个变异算子是 $i$ 的情况下，下一个算子选为 $j$ 产生有趣输入的概率。
过程：
1. 运行 AFL++（限制序列长度为 2，均匀随机选择算子）一段时间 $T_{train}$ （默认 1 小时）。
2. 统计每对算子 $(i, j)$ 产生的有趣输入数量 $N(i, j)$ 。
3. 计算条件概率矩阵：
  $Pr(j|i) = \frac{N(i, j)}{\sum_{k=1}^{|M|} N(i, k)}$
4. 该矩阵构成了一个马尔可夫链的转移概率矩阵。

阶段二：引导变异阶段 (Guided Mutation Phase)

目标：利用学习到的概率分布生成更有效的变异序列。
过程：
1. 选择第一个算子：采用均匀随机选择（实验表明这比加权选择更能保持探索性）。
2. 后续算子选择：对于序列中的第 $n$ 个算子，根据第 $n-1$ 个算子 $m_{n-1}$ ，从学习到的条件概率分布 $Pr(\cdot | m_{n-1})$ 中进行采样。
3. 序列长度优化：使用 $\epsilon$ -greedy 多臂老虎机 (MAB) 算法动态调整序列长度 $l$ ，以平衡探索与利用。

2.3 为什么只考虑前一个算子？

作者尝试了考虑前 $p>1$ 个算子（如三元组），但发现由于组合爆炸（ $32^3 = 32768$ 种组合），在有限的训练数据下，绝大多数三元组从未被观察到（稀疏性问题），导致学习失败。因此，仅考虑前一个算子（二元组）是最佳平衡点。

3. 主要贡献 (Key Contributions)

实证发现：首次通过统计模型（线性模型 + ANOVA）在灰盒模糊测试中量化并证实了变异算子之间存在显著的交互效应。
提出 MuoFuzz：设计并实现了一种基于条件概率的变异策略。它不假设算子独立，而是根据前一个算子动态调整下一个算子的选择概率。
全面评估：在 FuzzBench (13 个程序) 和 MAGMA (8 个程序) 基准上进行了严格评估，证明了 MuoFuzz 在代码覆盖率和漏洞发现能力上优于 AFL++ 和 MOPT。

4. 实验结果 (Results)

4.1 代码覆盖率 (Code Coverage)

对比对象：AFL++ (固定概率) 和 MOPT (独立优化概率)。
FuzzBench 结果：
- MuoFuzz 在 13 个程序中的 10 个 上达到了最高的代码覆盖率。
- 在统计显著性上，MuoFuzz 比 AFL++ 高 9/13，比 MOPT 高 8/13。
- 效率提升：MuoFuzz 平均仅需 15 小时 即可达到 AFL++ 在 24 小时达到的覆盖率，比 AFL++ 快约 9 小时；比 MOPT 快约 7.5 小时。
例外情况：在交互效应较弱或不存在（如 openssl, libpng）的程序中，MuoFuzz 表现与基线持平或略低，证明了其性能提升确实依赖于交互效应的存在。

4.2 漏洞发现 (Bug Finding)

MAGMA 基准：
- MuoFuzz 发现了 4 个 AFL++ 未发现的漏洞。
- MuoFuzz 发现了 1 个 AFL++ 和 MOPT 均未发现的漏洞。
- 虽然总漏洞数与 MOPT 相近，但 MuoFuzz 触发了独特的漏洞行为，证明了其探索路径的独特性。

4.3 消融实验 (Ablation Study)

上下文长度：使用 $p=2$ （前两个算子）作为上下文会导致性能下降，验证了“维度灾难”的担忧。
序列长度：使用 MAB 动态选择序列长度优于使用 AFL++ 的默认分布。
第一个算子选择：均匀随机选择第一个算子优于基于历史表现的加权选择（后者降低了探索性）。
训练时间：1 小时的训练时间通常优于 0.5 或 2 小时。

5. 意义与启示 (Significance)

理论突破：打破了模糊测试中“变异算子独立”的传统假设，证明了算子组合的顺序和上下文对测试效果至关重要。
技术启示：
- 模糊测试的变异策略可以借鉴自然语言处理中的 N-gram 语言模型（特别是 Bigram 模型）思想。
- 未来的研究可以探索更复杂的序列生成模型（如 RNN 或 Transformer），甚至将种子输入的结构信息作为上下文纳入模型。
实践价值：MuoFuzz 提供了一种轻量级、无需复杂离线训练即可嵌入现有模糊测试器（如 AFL++）的方案，显著提升了漏洞挖掘效率，特别是在那些算子间存在强依赖关系的程序中。

总结：该论文通过严谨的统计分析和系统实现，证明了利用变异算子间的交互效应可以显著提升灰盒模糊测试的性能，并提出了 MuoFuzz 作为这一思想的有效实现，为软件安全测试领域提供了新的优化方向。