Ad Hoc Syntax-Guided Program Reduction

Jia Le Tian, Mengxiao Zhang, Zhenyang Xu, Yongqiang Tian, Yiwen Dong, Chengnian Sun

Abstract

Program reduction is a widely adopted, indispensable technique for debugging language implementations such as compilers and interpreters. Given a program 𝑃 and a bug triggered by 𝑃, a program reducer can produce a minimized program 𝑃∗ that is derived from 𝑃 and still triggers the same bug. Perses is one of the state-of-the-art program reducers. It leverages the syntax of 𝑃 to guide the reduction process for efficiency and effectiveness. It is language-agnostic as its reduction algorithm is independent of any language-specific syntax. Conceptually to support a new language, Perses only needs the context-free grammar 𝐺 of the language; in practice, it is not easy. One needs to first manually transform 𝐺 into a special grammar form PNF with a tool provided by Perses, second manually change the code base of Perses to integrate the new language, and lastly build a binary of Perses.

BibTeX

@inproceedings{Tian-al:FSE23,
  author    = {Jia Le Tian and
               Mengxiao Zhang and
               Zhenyang Xu and
               Yongqiang Tian and
               Yiwen Dong and
               Chengnian Sun},
  title     = {Ad Hoc {Syntax-Guided} Program Reduction},
  booktitle = {{ESEC/SIGSOFT} {FSE}},
  pages     = {2137--2141},
  publisher = {{ACM}},
  year      = {2023},
}

Ad Hoc Syntax-Guided Program Reduction

Abstract

Related papers