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

📄 arXiv: 2604.06559v1 📥 PDF

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

分类: cs.SE, cs.LG

发布日期: 2026-04-08

备注: 19 pages

💡 一句话要点

ExplainFuzz：利用概率电路实现可解释和约束条件的测试用例生成

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 模糊测试 概率电路 测试生成 软件测试 上下文无关文法

📋 核心要点

  1. 现有模糊测试方法难以生成符合实际数据分布且具有上下文相关性的输入，同时缺乏可解释性。
  2. ExplainFuzz利用概率电路（PCs）学习和查询语法结构化输入上的分布，实现可解释和可控的测试生成。
  3. 实验表明，ExplainFuzz提高了生成输入的质量和多样性，并显著提升了bug触发率。

📝 摘要（中文）

理解和解释生成的测试输入的结构对于有效的软件测试和调试至关重要。现有的方法，包括基于语法的模糊测试器、概率上下文无关文法（pCFGs）和大型语言模型（LLMs），都存在严重的局限性。它们经常产生不符合实际数据分布的格式错误的输入，难以捕捉上下文相关的概率依赖关系，并且缺乏可解释性。我们介绍了ExplainFuzz，一个测试生成框架，它利用概率电路（PCs）来学习和查询基于语法的测试输入上的结构化分布，并具有可解释性和可控性。从上下文无关文法（CFG）开始，ExplainFuzz编译一个语法感知的PC，并在现有输入上训练它。然后通过采样生成新的输入。ExplainFuzz利用PC的条件能力来结合特定于测试的约束（例如，查询必须具有GROUP BY），从而实现约束概率采样以生成满足语法和用户提供的约束的输入。我们的结果表明，ExplainFuzz提高了生成输入的连贯性和真实性，与pCFGs、语法无关的PCs和LLMs相比，实现了显著的困惑度降低。通过利用其原生的条件能力，ExplainFuzz显著提高了满足用户提供的约束的输入的多样性。与语法感知的突变模糊测试相比，ExplainFuzz在SQL中将错误触发率从35%提高到63%，在XML中从10%提高到100%。这些结果证明了学习到的输入分布相对于突变模糊测试的强大之处，后者通常仅限于探索种子输入的局部邻域。这些能力突出了PCs作为语法感知、可控测试生成的基础的潜力，该测试生成可以捕获上下文相关的概率依赖关系。

🔬 方法详解

问题定义：现有模糊测试方法，如基于语法的模糊测试器、pCFGs和LLMs，在生成测试输入时存在诸多问题。它们难以生成符合实际数据分布的输入，无法有效捕捉上下文相关的概率依赖关系，并且缺乏可解释性，使得调试和理解测试过程变得困难。这些局限性导致生成的测试用例质量不高，难以有效发现软件中的潜在错误。

核心思路：ExplainFuzz的核心思路是利用概率电路（PCs）来学习和表示输入数据的结构化概率分布。通过将上下文无关文法（CFG）编译成语法感知的PC，ExplainFuzz能够捕获输入数据中的语法规则和概率依赖关系。然后，通过在现有输入上训练PC，可以学习到输入数据的真实分布。利用PC的条件能力，可以根据用户提供的约束条件进行概率采样，生成满足特定要求的测试用例。

技术框架：ExplainFuzz的整体框架包括以下几个主要阶段：1) CFG编译：将上下文无关文法（CFG）编译成语法感知的概率电路（PC）。2) PC训练：在现有的输入数据上训练PC，学习输入数据的概率分布。3) 约束条件输入：接收用户提供的约束条件，例如特定的语法规则或语义要求。4) 概率采样：利用PC的条件能力，根据约束条件进行概率采样，生成满足要求的测试用例。5) 测试执行：将生成的测试用例输入到目标软件中进行测试。

关键创新：ExplainFuzz最重要的创新点在于将概率电路（PCs）引入到模糊测试中，并利用其强大的概率建模和条件推理能力。与传统的模糊测试方法相比，ExplainFuzz能够更有效地学习和表示输入数据的结构化概率分布，并根据用户提供的约束条件生成高质量的测试用例。这使得ExplainFuzz能够发现更多潜在的软件错误，并提高测试效率。

关键设计：ExplainFuzz的关键设计包括：1) 语法感知的PC结构：PC的结构设计需要能够有效地表示CFG中的语法规则和概率依赖关系。2) PC训练方法：需要选择合适的训练方法，以确保PC能够准确地学习输入数据的概率分布。3) 约束条件编码：需要将用户提供的约束条件编码成PC可以理解的形式，以便进行条件概率采样。4) 采样算法：需要选择高效的采样算法，以确保能够快速生成大量的测试用例。

📊 实验亮点

实验结果表明，ExplainFuzz在生成输入的连贯性和真实性方面优于pCFGs、语法无关的PCs和LLMs，实现了显著的困惑度降低。此外，ExplainFuzz在SQL和XML测试中，分别将bug触发率从35%提高到63%和从10%提高到100%，显著优于语法感知的突变模糊测试。

🎯 应用场景

ExplainFuzz可应用于各种软件测试场景，特别是在需要生成结构化输入数据的领域，如数据库系统、编程语言编译器、网络协议实现等。它能够提高测试效率，发现更多潜在的软件缺陷，并为软件开发人员提供更有效的调试工具。未来，ExplainFuzz有望成为自动化测试和软件质量保证的重要组成部分。

📄 摘要（原文）

Understanding and explaining the structure of generated test inputs is essential for effective software testing and debugging. Existing approaches--including grammar-based fuzzers, probabilistic Context-Free Grammars (pCFGs), and Large Language Models (LLMs)--suffer from critical limitations. They frequently produce ill-formed inputs that fail to reflect realistic data distributions, struggle to capture context-sensitive probabilistic dependencies, and lack explainability. We introduce ExplainFuzz, a test generation framework that leverages Probabilistic Circuits (PCs) to learn and query structured distributions over grammar-based test inputs interpretably and controllably. Starting from a Context-Free Grammar (CFG), ExplainFuzz compiles a grammar-aware PC and trains it on existing inputs. New inputs are then generated via sampling. ExplainFuzz utilizes the conditioning capability of PCs to incorporate test-specific constraints (e.g., a query must have GROUP BY), enabling constrained probabilistic sampling to generate inputs satisfying grammar and user-provided constraints. Our results show that ExplainFuzz improves the coherence and realism of generated inputs, achieving significant perplexity reduction compared to pCFGs, grammar-unaware PCs, and LLMs. By leveraging its native conditioning capability, ExplainFuzz significantly enhances the diversity of inputs that satisfy a user-provided constraint. Compared to grammar-aware mutational fuzzing, ExplainFuzz increases bug-triggering rates from 35% to 63% in SQL and from 10% to 100% in XML. These results demonstrate the power of a learned input distribution over mutational fuzzing, which is often limited to exploring the local neighborhood of seed inputs. These capabilities highlight the potential of PCs to serve as a foundation for grammar-aware, controllable test generation that captures context-sensitive, probabilistic dependencies.