paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Input Algebras

输入代数
ICSE 2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE)2021匹配度 2/10 · 论文聚焦基于语法的测试生成与输入模式特化,属于程序测试/形式化方法的大领域,但与用户画像中静态分析、LLM/Agent 结合、浮点程序分析或贝叶斯程序分析等核心方向没有直接交集。引用 6 inbox
Rahul Gopinath, Hamed Nemati, Andreas Zeller
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:提出输入代数与语法变换器,通过任意布尔模式组合特化语法,支持定向测试生成与校验。

基于语法的测试生成器能高效产生语法合法的测试输入,并让用户精确控制生成内容,但针对特定测试目标调整语法或生成器往往很繁琐。本文提出“语法变换器”概念,可对语法进行特化,以包含或排除特定模式,例如“电话号码不能以 011 或 +1 开头”。作者称这是首个支持模式任意布尔组合的方法,为测试者提供了更强的定向测试构造灵活性。得到的特化语法可与任意基于语法的 fuzzer 配合,用于定向测试生成,也可作为验证器检查是否满足给定特化条件,从而拓展使用场景。在真实世界 bug 上的评估表明,特化语法在生成和验证目标输入两方面都较为准确。

问题
基于语法的测试生成器难以针对特定测试目标灵活调整语法或生成器,以包含或排除特定输入模式。
方法
提出 grammar transformer(语法变换器)与输入代数,通过任意布尔组合的模式对语法进行特化,生成可用于测试生成或作为验证器的特化语法。
评估
在真实世界 bug 上进行评估,显示特化语法在生成目标输入和验证目标输入两方面均准确有效。
原文摘要(Abstract)

Grammar-based test generators are highly efficient in producing syntactically valid test inputs, and give their user precise control over which test inputs should be generated. Adapting a grammar or a test generator towards a particular testing goal can be tedious, though. We introduce the concept of a grammar transformer, specializing a grammar towards inclusion or exclusion of specific patterns: "The phone number must not start with 011 or +1". To the best of our knowledge, ours is the first approach to allow for arbitrary Boolean combinations of patterns, giving testers unprecedented flexibility in creating targeted software tests. The resulting specialized grammars can be used with any grammar-based fuzzer for targeted test generation, but also as validators to check whether the given specialization is met or not, opening up additional usage scenarios. In our evaluation on real-world bugs, we show that specialized grammars are accurate both in producing and validating targeted inputs.

链接与引用

DOI 原文 · DBLP

BibTeX
@inproceedings{GopinathNZ21,
  title = {Input Algebras},
  author = {Rahul Gopinath and Hamed Nemati and Andreas Zeller},
  booktitle = {ICSE},
  year = {2021},
  doi = {10.1109/icse43902.2021.00070}
}