Boosting Program Reduction with the Missing Piece of Syntax-Guided Transformations

doi:10.1145/3763053

Boosting Program Reduction with the Missing Piece of Syntax-Guided Transformations

2025-10-01

0

PRE

AI

DOI：10.1145/3763053

原文求助

摘要

En 中文

程序缩减是一种在测试和调试语言处理器中广泛使用的技术。给定一个触发语言处理器中错误的程序，程序缩减搜索一个规范化和最小化的程序，该程序触发相同的错误，从而促进错误去重并简化调试过程。为了在不牺牲通用性的情况下提高缩减性能，先前的研究利用了编程语言的正式语法作为指导。引入了两种关键的语法引导变换——兼容子结构提升和量化节点缩减——以增强这一过程。虽然这些变换在一定程度上被证明是有效的，但它们过度地修剪了搜索空间，阻碍了发现许多更小的结果。因此，整体缩减性能仍有显著的改进潜力。为此，我们提出了一种新颖的语法引导变换，称为结构形式转换（SFC），以补充上述两种变换。基于SFC，我们引入了三种缩减方法：更小结构替换、标识符消除和结构规范化，旨在有效且高效地利用SFC进行程序缩减。通过将这些缩减方法集成到先前的语言无关程序缩减器Perses和Vulcan中，我们实现了两个原型SFCPerses和SFCVulcan。广泛的评估表明，SFCPerses和SFCVulcan在最小化和规范化方面均显著优于Perses和Vulcan。具体而言，与Perses相比，SFCPerses在C、Rust和SMT-LIBv2基准测试上产生的程序平均小36.82%、18.71%和41.05%，其时间成本分别为Perses的3.65倍、16.99倍和1.42倍。类似地，SFCVulcan生成的程序比Vulcan生成的程序小14.51%、7.65%和7.66%，其执行时间成本分别为Vulcan的1.56倍、2.35倍和1.42倍。此外，在一个包含3,796个触发46个唯一错误的C程序的基准测试套件实验中，SFCPerses和SFCVulcan分别比Perses和Vulcan多将442个和435个重复程序（触发相同错误的程序）缩减为相同的程序。

Keyword:

Program Reduction

Test Input Minimization

Automated Debugging

Boosting Program Reduction with the Missing Piece of Syntax-Guided Transformations

摘要

期刊

机构