[Paper] RandSet：用于 Fuzzing 种子调度的随机语料库缩减

Source: arXiv - 2602.22729v1

（请提供您希望翻译的正文内容，我将保持上述来源链接不变并翻译其余部分。）

概述

本文介绍了 RandSet，一种轻量级、随机化的技术，用于在保持（甚至提升）其向目标程序提供的输入多样性的同时，缩减模糊测试器的种子语料库。通过将语料库缩减视为集合覆盖问题并在求解过程中注入随机性，RandSet 将语料库削减至原始大小的几百分之一，从而显著缓解了阻碍现代模糊测试器的“种子爆炸”瓶颈。

关键贡献

• Randomized set‑cover formulation – 将语料库缩减视为集合覆盖问题，并使用快速的概率算法求解，产生一个既小又多样的种子子集。
• Low‑overhead integration – 在三款主流模糊测试工具（AFL++、LibAFL 和 Centipede）上实现了 RandSet，仅产生 1–4 % 的运行时开销，使其在高频种子调度中实用。
• Empirical validation – 在独立程序、FuzzBench 基准以及 Magma 漏洞发现套件上展示，RandSet 将语料库大小降低至原始的 ≈4–6 %，平均提升 +16 % 覆盖率，并比之前的最先进技术多发现最多 7 个真实漏洞。
• Diversity‑first design – 表明在缩减步骤中引入随机性自然会产生比 cull_queue、AFL‑cmin 或 MinSet 等确定性缩减器更为多样的种子选择。

方法论

1. 特征提取 – 每个种子通过其在执行时触发的 特征（例如代码分支、输入标记）的集合来表示。
2. 集合覆盖问题 – 目标是挑选一个最小的种子子集，使其合并后的特征集合覆盖完整语料库中观察到的所有特征。
3. 随机贪婪算法 – 与其精确求解 NP‑难的集合覆盖问题，RandSet 会在“最有价值”候选池中（即覆盖未覆盖特征数量最多的种子）随机反复挑选种子。此随机性：
   • 确保每次运行得到 不同 的精简子集，保持多样性。
   • 运行时间为 O(|C| · log |F|)（|C| = 语料库规模，|F| = 特征数量），相较于执行目标程序的成本可忽略不计。
4. 调度 – 模糊测试器的常规种子选择循环被重定向到精简子集。由于子集非常小，调度器可以使用更丰富的启发式策略（例如优先队列、能量分配），而不会产生原始的爆炸性开销。

结果与发现

• 多样性： RandSet 的精简集合包含比确定性 reducer 更广泛的唯一特征，后者往往将许多种子压缩为少数“代表”。
• 速度： 随机贪婪步骤即使在数万种子的语料库中也能在毫秒级完成，实现 每次迭代 的精简（即模糊器可以频繁重新运行 RandSet）。
• 兼容性： 不需要对底层模糊引擎进行任何更改；RandSet 直接接入现有的种子队列管理 API。

实际意义

• 可扩展的模糊测试流水线 – 团队可以让模糊器连续运行数周，而不会因不断增长的语料库而产生内存和 CPU 压力。
• 更好的资源分配 – 拥有一个体积小且高质量的种子池，开发者可以采用更激进的变异策略、对每个种子使用更长的执行时间，或在更多核心上进行并行模糊测试。
• 改进的 CI 集成 – 持续集成的模糊测试任务常常受到时间限制；RandSet 的低开销意味着每分钟 CI 能获得更多覆盖率，且更早发现漏洞。
• 跨模糊器采纳 – 由于 RandSet 可与 AFL++、LibAFL 和 Centipede 配合使用，任何已经使用这些工具的项目只需导入一个库并进行少量配置即可采用它。

限制与未来工作

• 特征定义依赖 – RandSet 的有效性取决于特征提取的质量（分支覆盖、标记化等）。特征质量差或过于粗糙可能导致子集次优。
• 随机性方差 – 虽然随机性提升了多样性，但也会导致可重复性上的非确定性；作者建议在需要时固定随机种子以实现确定性运行。
• 动态程序行为 – 对于行为随时间显著变化的程序（例如有状态的服务器），静态特征集可能会变得陈旧；未来工作可以探索 自适应 特征更新。
• 超越覆盖的扩展 – 当前的形式侧重于覆盖特征；将 RandSet 扩展以纳入其他度量（例如触发崩溃的潜力、输入大小多样性）是一个开放的研究方向。

作者

• Yuchong Xie
• Kaikai Zhang
• Yu Liu
• Rundong Yang
• Ping Chen
• Shuai Wang
• Dongdong She

论文信息

• arXiv ID: 2602.22729v1
• Categories: cs.SE, cs.CR
• 出版日期: 2026年2月26日
• PDF: Download PDF