On Interaction Effects in Greybox Fuzzing [ICSE 2026]

作者假设应用到种子上变异算子的顺序对灰盒模糊测试的效果有影响. 在实验上, 作者对包含所有可能变异算子效果的数据集构建线性模型, 并切实观察到猜测的交互作用. 这指引作者通过选择更有潜力的变异序列来提高 fuzzing 效果.

论文提出 MuoFuzz, 学习并选择最有潜力的变异序列. 在给定上一个变异算子的情况下, MuoFuzz 学习下一个变异算子会生成有趣输入的条件概率. 接着从学到的概率中采样以生成变异序列. 作者将 MuoFuzz 与 AFL++ (固定每个算子的选择概率) 和 MOPT (孤立优化每个算子的选择概率) 进行比较, 在 Fuzzbench 和 Magma 上取得最大的代码覆盖率, 并发现 4 个被 AFL++ 遗漏的漏洞和 1 个同时被 AFL++ 和 MOPT 遗漏的漏洞.

Open URL: https://doi.org/10.5281/zenodo.17391100

The Interaction Effect

Dataset Collection

为了收集 mutators pair , 作者挑选 13 个目标程序, 用 AFL++ 来 fuzz, 有 3 项修改

将 length of mutator sequences 限制为 2, 当 l > 2 时会出现计算困难
对变异器均匀采样, 保证每个 mutator pair 数量相当
维护 $\mathcal M \times \mathcal M$ 矩阵 $N(i, j)$ 记录每个 mutator pair 生成 interesting inputs 的数量

运行 20 个 trials, 拿到 20 个矩阵 $N(i, j)^k, k \in \{1, 2, ..., 20\}$ , 分别运行 $T = \{1, 5, 20\}$ hours.

Model Fitting

使用线性模型来拟合并预测每个 mutator pair 的 interesting inputs 生成数量. 不用高阶模型, 因为不必要.

设交互作用项为 $\gamma_{ij}$ , 为了检验交互作用项有显著影响, 采用 two-way Analysis of Variance (ANOVA, 双因素方差分析) 对矩阵中每个做零假设检验 null hypothesis that $\gamma_{ij} = 0$ , 之后作者分别用包含交互项的线性模型和不包含交互项的线性模型拟合给定下 interesting inputs 数量.

Results

双因素方差分析发现包含交互项的模型拟合优度更高, 说明变异序列对 interesting inputs 生成有显著影响.

Methods

"We propose a method, MuoFuzz, for generating mutator sequences where the probability of selecting the next mutator is conditioned on the previously selected one"

"We reduce the problem of generating a mutator sequence $<m_1, m_2, ..., m_l>$ to the problem of learning the conditional probability $Pr(m_n = j\ |\ m_{n-1} = i)$ of selecting j as the next mutator in the sequence given that the previously selected mutator is i."

生成变异序列的算法思想:

随机挑选变异算子 $m_1$
固定 $m_1$ , 按概率分布挑选 $m_2$
重复该过程, 挑选第 n 个变异算子 $m_n$

$m_n \sim Pr(j)=Pr\left(m_{n} = j \mid m_{n-1}\right)$

MuoFuzz 工作流分为

训练阶段: 学习条件概率 $Pr(m_n = j\ |\ m_{n-1} = i)$ , 概率按给定 i 时的 interesting inputs 数量估计

和

指导变异阶段: 经过 T hours 的训练阶段后, MuoFuzz 进入指导变异阶段, 按学到的条件概率, 采样下一个 mutator 形成 mutator sequences.

Training Phase

训练阶段在 AFL++ 基础上运行, 将 length of mutator sequence 设为 2, 随机采样 mutators, 并根据 interesting inputs 数量更新 $N(i, j)$ 矩阵. 条件概率定义为

$Pr(j)=Pr\left(m_n=j \mid m_{n-1}=i\right)=\frac{N(i, j)}{\sum_{j=1}^{|\mathcal{M}|} N(i, j)}$

这是 freetype 目标程序的条件概率训练结果

Guided Mutation Phase

变异序列长度 $2 < l < 16$ , 最优长度按 $\epsilon-greedy$ 算法调整, 将最优长度选择问题建模为多臂老虎机问题, 用 Upper Confidence Bound (UCB) 求解

挑选最初 mutator, 有两种策略: 1.均匀采样每个 mutator; 2.按 interesting inputs 生成总数加权采样, 设第 i 个 mutator 的采样概率为

$s_i=\sum_{j=1}^{|\mathcal{M}|} N(i, j)+\sum_{j=1}^{|\mathcal{M}|} N(j, i)-N(i, i)$

为什么不用条件概率 $Pr\left(m_n \mid m_{n-1} m_{n-2} \ldots m_{n-p}\right)$ ? 因为维度灾难: 只考虑 $Pr\left(m_n=j \mid m_{n-1}=i\right)$ 时的条件概率矩阵是 32 ^ 2 = 1024 大小, 当 p = 2 时, 矩阵大小为 32 ^ 3 = 32768, 计算开销急速增大. 而且对于 32 ^ 3 种组合, 在训练阶段无法完全覆盖, 因为有些组合没有生成 interesting inputs.

Evaluation

How does MuoFuzz compare to AFL++ and MOPT in terms of code coverage?

How does MuoFuzz compare to AFL++ and MOPT in terms of bugs found?

MuoFuzz 比 AFL++ 多挖出 3 个 bug
MuoFuzz 和 MOPT 总 bug 数是一样的, SSL001 只被 MOPT 挖到, SQL010 只被 MuoFuzz 挖到

How do different hyperparameters affect the performance of MuoFuzz?

消融实验, 对比 p > 1 时的效果, 对比最优序列长度 length 的结果, 对比第一个 mutator 选择的结果, 对比 training time 的选择结果, 对比概率矩阵在跨程序目标的泛化性

On Interaction Effects in Greybox Fuzzing