🤖 machine learning

ExplainFuzz: Explainable and Constraint-Conditioned Test Generation with Probabilistic Circuits

本文提出了 ExplainFuzz，一种基于概率电路的测试生成框架，它通过学习语法感知的结构化分布并支持约束条件，显著提升了生成测试输入的合理性、可控性及触发软件缺陷的效率。

原作者： Annaëlle Baiget, Jaron Maene, Seongmin Lee, Benjie Wang, Guy Van den Broeck, Miryung Kim

发布于 2026-04-09

📖 1 分钟阅读☕ 轻松阅读

原作者： Annaëlle Baiget, Jaron Maene, Seongmin Lee, Benjie Wang, Guy Van den Broeck, Miryung Kim

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

这篇论文介绍了一个名为 ExplainFuzz 的新工具，它的任务是帮程序员生成“测试数据”来检查软件（比如数据库或编译器）有没有漏洞。

为了让你更容易理解，我们可以把整个软件测试过程想象成**“给一位挑剔的餐厅主厨（软件）送各种奇怪的食材（测试数据），看看他会不会被噎住或者把厨房炸了（发现 Bug）”**。

1. 以前的方法有什么毛病？

在 ExplainFuzz 出现之前，大家主要用三种方法来生成这些“食材”，但它们都有明显的缺点：

老式“随机拼凑法”（传统 Fuzzing）：
- 比喻： 就像让一个只会背菜谱的机器人，随机把“盐”、“糖”、“酱油”倒进锅里。
- 问题： 虽然倒进去的东西符合“盐、糖、酱油”的语法（比如都是液体），但组合起来可能是一碗“咸糖水”，根本没法吃（无效数据）。而且它只会围着原来的几样菜打转，很难发现新花样。
大语言模型（LLM，如 ChatGPT）：
- 比喻： 就像请了一位博学但有点“神神叨叨”的大厨来写菜谱。
- 问题： 他写出来的菜谱看起来很像那么回事，但你问他“为什么这里要放醋？”他却答不上来（黑盒，不可解释）。而且让他写一万种不同的菜谱，他可能会卡壳，或者写得不够快。
概率上下文无关文法（pCFG）：
- 比喻： 就像给机器人设定了固定的概率：如果有“盐”，就有 30% 的概率加“糖”。
- 问题： 它太死板了。它不知道“盐”和“糖”在特定情况下（比如做甜点时）应该一起出现，但在做咸菜时就不该一起出现。它缺乏对上下文的敏感度。

2. ExplainFuzz 是怎么做的？（核心魔法）

ExplainFuzz 引入了一个聪明的“概率电路”（Probabilistic Circuits, PCs）作为大脑。我们可以把它想象成一个**“拥有超级记忆和逻辑推理能力的智能主厨助手”**。

它的工作流程分为三步：

第一步：学习（编译与训练）

做法： 助手先阅读一本“经典菜谱书”（现有的测试数据），同时手里拿着一本“语法字典”（语法规则）。
比喻： 它不只是死记硬背菜谱，而是学会了**“为什么”**。比如，它发现：“哦，原来只要主菜里有‘鱼’，后面大概率会跟‘姜’和‘葱’，而且‘姜’和‘葱’的比例是固定的。”
关键点： 它把语法规则和真实数据的学习结合在了一起，既懂语法，又懂现实世界的规律。

第二步：解释（可解释性）

做法： 在生成新菜谱前，你可以问它问题。
比喻： 你可以问助手：“如果我想做一道带‘辣’味的菜，出现‘辣椒’的概率是多少？”或者“如果我已经放了‘鱼’，那么放‘姜’的概率会增加吗？”
优势： 以前的工具是黑盒，你不知道它为什么生成这个数据。ExplainFuzz 能让你看清它生成数据的逻辑，就像看得到它的思考过程一样。

第三步：定向生成（约束条件）

做法： 这是它最厉害的地方。你可以给它下达具体的“约束指令”。
比喻： 你可以对助手说：“帮我生成 100 道必须包含‘鱼’和‘辣椒’，但绝对不能有‘糖’的菜。”
优势： 以前的工具很难精准控制。如果我想专门测试“带鱼”的情况，老方法可能得生成一万道菜才能碰巧遇到几道。但 ExplainFuzz 可以直接锁定这个条件，高效地生成大量符合特定要求的测试数据。

3. 效果如何？（实战表现）

作者在两个领域（SQL 数据库查询和 XML 数据格式）做了测试，结果非常惊人：

更真实、更像人写的： 它生成的数据比以前的方法更连贯，更像真实的用户操作（困惑度更低）。
发现 Bug 的能力更强：
- 在 SQL 测试中，它把发现 Bug 的成功率从 35% 提升到了 63%。
- 在 XML 测试中，它更是从 10% 飙升到了 100%！
- 比喻： 以前的方法像是在大海里随便撒网，偶尔能捞到一条鱼（Bug）；ExplainFuzz 像是拿着声呐，精准定位鱼群，然后一网打尽。
多样性更高： 它不仅能找到 Bug，还能找到更多种不同方式来触发同一个 Bug。这意味着它能更全面地测试软件的弱点。

总结

ExplainFuzz 就像是给软件测试领域装上了一套**“带导航和说明书的自动驾驶系统”**。

它不像老式方法那样盲目乱撞。
它不像大模型那样让人摸不着头脑。
它懂语法（保证数据合法），懂概率（模仿真实数据分布），懂逻辑（能解释为什么这么生成），还能听指挥（按你的要求生成特定数据）。

最终，它帮助程序员用更少的时间、更聪明的方法，发现更多、更深层次的软件漏洞，让软件变得更安全、更可靠。

ExplainFuzz 技术总结

1. 研究背景与问题定义

在软件测试（特别是编译器和数据库测试）中，生成高质量、结构化的测试输入至关重要。然而，现有的测试输入生成方法存在以下核心局限：

基于语法的模糊测试（Grammar-based Fuzzing）： 如 Grammarinator，虽然能生成语法正确的输入，但通常依赖随机扩展或局部种子变异。它们缺乏对输入分布的系统性控制，难以捕捉上下文敏感的统计依赖（例如：SQL 中 HAVING 子句的出现概率通常依赖于 GROUP BY 的存在），导致生成的输入往往不自然或无法反映真实数据分布。
概率上下文无关文法（pCFGs）： 虽然引入了规则概率，但假设产生式规则之间是独立的，无法建模长距离的上下文依赖。
大型语言模型（LLMs）： 虽然能生成高质量输入，但作为“黑盒”缺乏可解释性，且难以在采样过程中进行细粒度的约束控制，计算成本也较高。
缺乏可解释性与可控性： 现有方法难以让开发者理解输入空间的探索情况，也无法通过特定约束（如“必须包含 JOIN 子句”）系统性地调整生成行为。

核心问题： 如何构建一个既能捕捉上下文敏感的概率依赖，又具备可解释性和约束可控性的测试输入生成框架？

2. 方法论：ExplainFuzz

ExplainFuzz 是一个基于**概率电路（Probabilistic Circuits, PCs）**的测试生成框架。它通过以下步骤实现语法感知、可解释且受约束的输入生成：

2.1 核心架构

预处理（Preprocessing）：
- 语法重构： 将 ANTLR 格式的上下文无关文法（CFG）转换为适合编译的形式（如将内联字面量替换为命名 Token）。
- 种子扩增与匿名化： 利用 Grammarinator 扩增种子集，并将具体词法单元（如具体表名、数字）转换为抽象 Token（如 ID, Numeric），以便模型学习语法结构而非具体值。
PC 编译（PC Compilation）：
- 将 CFG 编译为语法感知的概率电路（Grammar-aware PC）。
- 采用类似 CYK 算法的自底向上构建方式：为每个非终结符和序列位置构建求和节点（Sum nodes，表示选择），为每条产生式规则构建乘积节点（Product nodes，表示组合）。
- 该电路能够表示所有长度在 $n$ 以内的合法语法序列的分布。
训练（Training）：
- 使用匿名化后的种子输入训练 PC，学习语法 Token 之间的概率分布，特别是那些标准 CFG 无法表达的上下文敏感依赖。
推理与生成（Inference & Generation）：
- 可解释性查询： 利用 PC 的线性时间推理能力，回答如“输入中包含 JOIN 的概率是多少？”或“给定 GROUP BY，出现 HAVING 的概率是多少？”等问题。
- 约束条件采样（Constraint-Conditioned Sampling）： 利用 PC 的原生条件推理能力，在生成过程中强制满足特定约束（例如：强制生成包含 GROUP BY 的 SQL 查询），同时保持语法的合法性和语义的连贯性。
- 具体化（Concretization）： 将生成的抽象 Token 序列映射回具体的可执行输入（如将 ID 替换为真实的列名，Numeric 替换为符合类型的数值）。

3. 主要贡献

可解释且可控的生成框架： 首次将概率电路引入测试生成，提供了对输入分布的透明视图（通过概率查询）和基于约束的系统性控制（通过条件采样）。
提升的连贯性与真实性： 相比 pCFG、无语法感知的 PC（PC-HMM）和 LLM，ExplainFuzz 能更有效地捕捉上下文敏感的概率依赖。在 7 个领域的测试中，其困惑度（Perplexity）比 pCFG 降低了 1.27 倍。
基于条件采样的定向生成： 证明了通过条件约束可以显著提高生成输入触发特定缺陷的能力。在 SQL 和 XML 测试中，条件采样分别将 Bug 覆盖率提升了 23.6% 和 17.5%，并显著增加了触发同一 Bug 的不同输入数量（多样性）。
超越传统变异模糊测试： 与 Grammarinator 相比，ExplainFuzz 通过学习全局分布而非局部变异，显著提高了 Bug 触发率。在 SQL 中从 35% 提升至 63%，在 XML 中从 10% 提升至 100%。

4. 实验结果

研究在 SQL 和 XML 两个领域进行了详细评估，对比了 ExplainFuzz 与 Grammarinator、pCFG、PC-HMM 及 LLM（GPT-2）。

RQ1（连贯性与真实性）：
- ExplainFuzz 在 7 个领域中的 5 个（SQL, B, CSV, HTML, JSON）取得了最低的困惑度，表明其生成的输入最接近真实数据分布。
- 尽管 PC-HMM 在某些领域（如 REDIS）表现较好，但它无法保证语法正确性（MLIR 领域解析率仅 12.9%），而 ExplainFuzz 始终生成语法合法的输入。
RQ2（定向采样的影响）：
- 通过条件约束（如强制包含 CDATA 或 JOIN），ExplainFuzz 能够发现未条件化版本无法触发的新 Bug。
- 在 XML 测试中，条件化生成使 Bug 覆盖率从 82.5% 提升至 100%，且每个 Bug 触发的不同输入数量平均增加了 121 个。
RQ3（Bug 触发输入多样性）：
- Bug 覆盖率： 相比 Grammarinator，ExplainFuzz 在 SQL 中将覆盖率从 35.3% 提升至 39.7%，在 XML 中从 10% 提升至 82.5%。
- 输入多样性： ExplainFuzz 每个种子集平均多产生 417 个（SQL）和 1587 个（XML）独特的 Bug 触发输入。
- 定性分析： ExplainFuzz 生成的输入在语义上更合理（例如正确选择列名而非使用 SELECT *），结构更丰富（包含深层嵌套和复杂子查询），而 Grammarinator 往往局限于种子附近的局部变异。

5. 意义与价值

填补了生成式测试的空白： 解决了传统模糊测试缺乏全局分布建模和 LLM 缺乏可控性的问题。
可解释性驱动调试： 开发者不仅可以生成测试用例，还可以“询问”模型理解输入空间的概率结构，从而更精准地设计测试策略。
高效的条件控制： 提供了一种无需重新训练模型即可动态调整生成目标（如“只生成包含特定子句的查询”）的机制，极大地提升了测试效率。
验证了概率电路在软件工程中的潜力： 证明了 PCs 在处理结构化数据分布、平衡表达能力与推理效率方面具有独特优势，为未来的智能测试工具奠定了基础。

总结： ExplainFuzz 通过结合上下文无关文法与概率电路，成功构建了一个既懂语法结构、又懂统计规律，且完全可控的测试生成系统，显著提升了软件缺陷发现的效率和深度。