[OOPSLA23] Pushing the Limit of 1-Minimality of Language-Agnostic Program Reduction

Описание: Pushing the Limit of 1-Minimality of Language-Agnostic Program Reduction (Video, OOPSLA1 2023)
Zhenyang Xu, Yongqiang Tian, Mengxiao Zhang, Gaosen Zhao, Yu Jiang, and Chengnian Sun
(University of Waterloo, Canada; University of Waterloo, Canada; University of Waterloo, Canada; University of Waterloo, Canada; Tsinghua University, China; University of Waterloo, Canada)

Abstract: Program reduction has demonstrated its usefulness in facilitating debugging language implementations in practice, by minimizing bug-triggering programs. There are two categories of program reducers: language-agnostic program reducers (AGRs) and language-specific program reducers (SPRs). AGRs, such as HDD and Perses, are generally applicable to various languages; SPRs are specifically designed for one language with meticulous thoughts and significant engineering efforts, e.g., C-Reduce for reducing C/C++ programs.


Program reduction is an NP-complete problem: finding the globally minimal program is usually infeasible. Thus all existing program reducers resort to producing 1-minimal results, a special type of local minima. However, 1-minimality can still be large and contain excessive bug-irrelevant program elements. This is especially the case for AGR-produced results because of the generic reduction algorithms used in AGRs. An SPR often yields smaller results than AGRs for the language for which the SPR has customized reduction algorithms. But SPRs are not language-agnostic, and implementing a new SPR for a different language requires significant engineering efforts.


This paper proposes Vulcan, a language-agnostic framework to further minimize AGRs-produced results by exploiting the formal syntax of the language to perform aggressive program transformations, in hope of creating reduction opportunities for other reduction algorithms to progress or even directly deleting bugirrelevant elements from the results. Our key insights are two-fold. First, the program transformations in all existing program reducers including SPRs are not diverse enough, which traps these program reducers early in 1-minimality. Second, compared with the original program, the results of AGRs are much smaller, and time-wise it is affordable to perform diverse program transformations that change programs but do not necessarily reduce the sizes of the programs directly. Within the Vulcan framework, we proposed three simple examples of fine-grained program transformations to demonstrate that Vulcan can indeed further push the 1-minimality of AGRs. By performing these program transformations, a 1-minimal program might become a non-1-minimal one that can be further reduced later.


Our extensive evaluations on multilingual benchmarks including C, Rust and SMT-LIBv2 programs strongly demonstrate the effectiveness and generality of Vulcan. Vulcan outperforms the state-of-the-art language-agnostic program reducer Perses in size in all benchmarks: On average, the result of Vulcan contains 33.55%, 21.61%, and 31.34% fewer tokens than that of Perses on C, Rust, and SMT-LIBv2 subjects respectively. Vulcan can produce even smaller results if more reduction time is allocated. Moreover, for the C programs that are reduced by C-Reduce, Vulcan is even able to further minimize them by 10.07%.

Article: https://doi.org/10.1145/3586049

Supplementary archive: https://doi.org/10.5281/zenodo.8197652 (Badges: Artifacts Available)

ORCID: https://orcid.org/0000-0002-9451-4031, https://orcid.org/0000-0003-1644-2965, https://orcid.org/0000-0002-3463-2802, https://orcid.org/0000-0002-5939-349X, https://orcid.org/0000-0003-0955-503X, https://orcid.org/0000-0002-0862-2491

Video Tags: Program Reduction, Automated Debugging, Test Input Minimization, oopslaa23main-p117-p, doi:10.1145/3586049, doi:10.5281/zenodo.8197652, orcid:0000-0002-9451-4031, orcid:0000-0003-1644-2965, orcid:0000-0002-3463-2802, orcid:0000-0002-5939-349X, orcid:0000-0003-0955-503X, orcid:0000-0002-0862-2491, Artifacts Available

Presentation at the OOPSLA1 2023 conference, October 22–27, 2023, https://2023.splashcon.org/track/spla...
Sponsored by ACM SIGPLAN,