Boosting Program Reduction with the Missing Piece of Syntax-Guided Transformations
summary
Introduces Structure Form Conversion as a new syntax-guided transformation and implements three methods including Smaller Structure Replacement and Structure Canonicalization integrated into Perses and Vulcan to produce SFCPerses and SFCVulcan. SFCPerses makes C, Rust, and SMT-LIBv2 outputs 36.82%, 18.71%, and 41.05% smaller on average at 3.65×, 16.99×, and 1.42× the runtime of Perses; SFCVulcan yields 14.51%, 7.65%, and 7.66% smaller results at 1.56×, 2.35×, and 1.42× Vulcan time. On 3,796 C inputs triggering 46 bugs the prototypes canonicalize 442 and 435 more duplicates to identical programs than Perses and Vulcan.
AI-written summary · about
chapters (7)
- 0:00Program reduction intro
- 1:28Compiler debugging applications
- 3:13Canonicalization goal
- 6:01Syntax-guided limits
- 8:48Structure form conversion
- 11:21Benchmarks and baselines
- 13:07Summary and tools
related talks
17mPushing the Limit of 1-Minimality of Language-Agnostic Program Reduction
38mSurgical Refactoring of Non-Tested Code – A Worked Example
30mGenerating Conforming Programs With Xsmith
13mEfficient Semantic Comparison of GraphQL Queries
41mCan you make that smaller? An introduction to test-case reduction
20mSemantic Reification: A New Paradigm for Random Program Generation
20mAutomatic Repair of Regular Expressions
20mTaking out the Toxic Trash: Recovering Precision in Mixed Flow-Sensitive Static Analyses