用概率电路生成可解释的测试用例，提升真实性和漏洞发现率
ExplainFuzz: Explainable and Constraint-Conditioned Test Generation with Probabilistic Circuits
- 基于上下文无关语法构建概率电路，实现结构化输入生成
- 在SQL和XML测试中，漏洞触发率从35%提升至63%，最高达100%
- 支持约束条件控制，生成符合要求且多样化的测试数据
理解并解释生成测试用例的结构对有效软件测试与调试至关重要。现有方法——包括基于语法的模糊测试、概率上下文无关文法（pCFG）和大语言模型（LLMs）——存在显著缺陷：常生成无效输入，无法反映真实数据分布，难以捕捉上下文相关的概率依赖关系，且缺乏可解释性。本文提出ExplainFuzz，一种利用概率电路（PCs）学习并查询语法驱动测试输入的结构化分布的测试生成框架，实现可解释、可控的输入生成。从上下文无关文法（CFG）出发，ExplainFuzz编译出语法感知的概率电路，并在已有输入上进行训练，通过采样生成新输入。借助概率电路的条件化能力，可引入测试特定约束（如查询必须含GROUP BY），实现满足语法和用户约束的条件化采样。实验表明，ExplainFuzz显著提升了生成输入的一致性与真实性，相比pCFG、无语法感知的概率电路及大语言模型，困惑度大幅降低。通过其原生条件化能力，输入多样性显著增强。相较于语法感知的变异模糊测试，ExplainFuzz在SQL测试中漏洞触发率从35%提升至63%，在XML测试中从10%提升至100%。结果证明，学习得到的输入分布相比传统变异模糊测试具有更强探索能力，后者通常局限于种子输入的局部邻域。这些能力凸显了概率电路作为语法感知、可控测试生成基础的巨大潜力，可精准建模上下文敏感的概率依赖关系。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。