FOX: Coverage-guided Fuzzing as Online Stochastic Control [CCS 2024]

本文提出了一种端到端的在线随机控制模型，用于覆盖引导的模糊测试。该方法包含一个新的调度器和可以适应分支逻辑的自定义修改器，最大化在多个阶段实现的聚合边缘覆盖。该调度器利用细粒度的分支距离度量来识别前沿分支，其中可能实现新的覆盖。突变器利用分支距离信息进行高效和有针对性的种子突变，以最小的开销实现鲁棒的进展。

在FuzzBench数据集和复杂的真实程序 (共38个测试程序) 上进行的 6 CPU 年的测试结果表明，与目前最先进的模糊测试器相比，FOX在独立程序上的覆盖率平均提高了26.45%，在FuzzBench程序上的覆盖率平均提高了6.59%。

Theory

定向灰盒模糊测试的边覆盖率最大化描述为，找到 $u_i$ 下表序列，使得所有 K 次迭代下基于种子库 $S_i$ 突变的所有种子 $mut(S_i[u_i])$ 的累积覆盖率最大。如公式 (1) 所示.

该问题是一个在线优化问题 [28]，因为模糊器只能在每个阶段先后应用变异操作后观察 cov 函数的输出。在在线优化环境中，决策者 (在本例中是fuzzer) 必须在不完全知道目标函数未来各阶段值的情况下在每个阶段做出选择。模糊测试器的目标是最大化测试阶段序列的累积覆盖率。

Stochastic Optimal Control Problem

在最优控制问题中，主要目标是给定状态空间和控制空间，找到最优控制策略。模糊测试场景中，状态空间表示模糊测试器在每个阶段的状态，即当前的种子语料库 $S_i$，控制空间对应于模糊测试器所做的选择，例如选择变异的种子。

建模为随机最优控制问题，一共有5个关键组件

状态空间 包含系统在任何给定阶段的所有可能配置或状态。在模糊测试的背景下，它包含了关于阶段i的当前种子语料库的信息，记为 $S_i$。

控制空间 包含了所有可能影响系统行为的决策。在模糊测试环境中，它指在每个阶段选择哪个种子，用种子语料$Si\ (1 \le u_i \le |S_i|)$ 中的索引 $u_i$ 表示。

Fuzzer Dynamics. 三个步骤: 变异种子得到 $x$，输入目标程序获得覆盖率 $g_i$，更新状态 $S_{i+1}$。

目标函数 定义了系统的目标或期望的结果。在模糊测试的背景下，它的目标是最大化 K 个阶段的总覆盖率增益：

约束 表示系统需要满足的限制。模糊测试通常受到资源限制，比如总执行时间 (即每个阶段的执行时间之和 $t_i$) 不能超过模糊测试活动的总时间预算 $T$：

根据为不同种子生成的不同程序输入是独立分布的假设，对特定分支 $b$ 的覆盖进行建模，记为$cov_b (x, S_i)$，其中 $x \leftarrow mut (S_i [u_i])$ 为遵循伯努利分布的随机变量 $x$，其成功概率为$Pr (b\ flip | mut (S_i [u_i]))$。

在基于图中心性的种子调度中，作者利用了与She等人提出的地平线节点 (horizon node) 密切相关的前沿节点 (frontier node) 的概念。根据代码覆盖信息将N分为未访问的节点集U和已访问的节点集V。与She等人 [49] 将horizon节点识别为一组位于已访问和未访问代码区域边界的未访问节点不同，作者将 frontier 节点定义为一组已访问节点，它们支配所有未访问节点：

为了使用边界节点来理解覆盖率，只关注包含导致条件跳转的控制指令的边界节点子集 $FB_i$。对于条件类型 (<, ≤, >, ≥, =, ≠)，给定前沿分支 $b \in FB_i$，定义分段线性函数计算分支距离，$f_b(x) = x - const$，const 为条件跳转的比较值.

Optimal-control-based Scheduler

使用贪心方法求解优化问题，目标是在流式环境下高效选择种子，从而最大化分支条件分支距离下降的概率。

两步求解：步骤 (a)：为每个分支 b，找到能最大化 $Pr\left(\delta_b \text { decreases } \mid mut\left(S_i\left[u_i\right]\right)\right)$ 的种子。步骤 (b)：选择具有最大概率 $Pr$ 的分支 $b$ 并更新种子与分支距离。

数据结构: 使用映射 $T_S$ 来维护每个阶段 $i$ 的分支 $b$ 与对应的最优种子 $T_S[b].s$ 和分支距离 $T_S[b].d$

更新规则：

Optimizing Mutation

通过优化变异阶段，提高所有前沿分支的分支距离减少概率。

本地线性下界估计 (Local Search) 通过局部搜索构造一个线性下界近似器，用于分支距离函数 $\delta_b(x)$​。线性近似器提供一个局部下界，确保在当前点 $x$ 的邻域 $N(x)$ 内，分支距离的估计稳定。并采用最小化“欠估计误差” (under-approximation error) 的策略，而非平均误差，保障后续牛顿法的稳定性。

牛顿法 (Newton’s Method) 如果局部搜索得到了有效梯度 $g$ (即非零向量) ，则利用牛顿法优化输入。沿着梯度方向 $g$ 更新输入 $x=x-\frac{\delta_b(x)}{g}$ 目标是找到一个 $x$，使得分支距离 $\delta_b(x)$ 变为 0，从而触发分支翻转。

References

[28] Elad Hazan et al. 2016. Introduction to online convex optimization. Foundations and Trends® in Optimization (2016).

[49] Dongdong She, Abhishek Shah, and Suman Jana. 2022. Effective Seed Scheduling for Fuzzing with Graph Centrality Analysis. 2022 IEEE Symposium on Security and Privacy (SP) (2022), 2194–2211.