Please note: This PhD defence will take place in TBD.
Zhenyang Xu, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Chengnian Sun
Program reduction is a widely used technique for testing and debugging language processors. Given a program that triggers a bug in a language processor, program reduction searches for a canonical and minimal program that triggers the same bug, thereby facilitating bug deduplication and simplifying debugging. Among various reduction approaches, language-agnostic reducers (AGRs) have emerged as an important class of techniques because they do not rely on language-specific knowledge and can thus be applied across a wide range of programming languages. This generality makes AGRs especially valuable for languages lacking specialized reduction tools. However, previous AGRs support only a limited set of program transformations, which restricts their minimization and canonicalization capability and results in substantial performance gap compared to language-specific reducers (SPRs).
This thesis aims to enhance both the canonicalization and minimization capabilities of AGRs, thereby narrowing the performance gap between AGRs and SPRs. It comprises the following three contributions.
The first work aims to improve the minimization capability of AGRs. As previously mentioned, previous AGRs support only a limited set of transformations. Once a 1-minimal result is obtained and no further transformation can reduce the program, the reduction process terminates. However, such a 1-minimal result may still contain excessive bug irrelevant program elements. To address this limitation, this work proposes a framework named Vulcan. Vulcan employs an AGR as the main reducer and introduces a set of auxiliary reducers that perform aggressive program transformations. When the main reducer can no longer make progress, Vulcan invokes one of its auxiliary reducers to create new reduction opportunities, and then re-applies the main reducer to further minimize the program. In addition to the framework, this work also presents three example aggressive program transformations: Identifier Replacement, Subtree Replacement, and Tree-Based Local Exhaustive Enumeration. Evaluation on a multilingual benchmark suite (referred to as Bench-Reduce) which includes C, Rust, and SMT-LIBv2 programs, demonstrates that Vulcan outperforms the state-of-the-art AGR, Perses, in terms of minimization. On average, Vulcan produces results with 33.55%, 21.61%, and 31.34% fewer tokens than Perses on C, Rust, and SMT-LIBv2 benchmarks, respectively.
The second work focuses on enhancing the canonicalization performance of AGRs. A reducer with strong canonicalization capability can minimize differences among programs that trigger the same bug, thereby greatly facilitating bug deduplication. However, prior AGRs exhibit poor canonicalization performance, primarily because they treat tokens as atomic and irreducible units. To address this limitation, this work proposes T-Rec, a fine-grained, lexical syntax–guided program reduction technique that can effectively reduce and canonicalize each token in a program. Evaluation results show that integrating TRec into Vulcan enables the elimination of 1,315 additional duplicates in a benchmark suite containing 3,796 programs that expose 46 unique bugs (referred to as Bench-Cano). Moreover, T-Rec further reduces the size of Vulcan’s results on Bench-Reduce by up to 53.73.
The third work aims to further enhance both the minimization and canonicalization performance of AGRs by introducing additional program transformations. Specifically, this work proposes SFC, a novel syntax-guided transformation technique that has been overlooked by prior syntax-guided AGRs. To apply SFC effectively and efficiently in program reduction, three SFC-based reduction methods are designed: Smaller Structure Replacement, Identifier Elimination, and Structure Canonicalization. Evaluation results show that integrating these SFC-based methods into Vulcan yields an average 8.2% reduction in output size on Bench-Reduce. Moreover, when combined with T-Rec, the SFC-based methods enable Vulcan to eliminate an additional 435 duplicates in Bench-Cano.
Collectively, these studies significantly advance the effectiveness of language-agnostic program reduction in both minimization and canonicalization. By integrating the proposed approaches, the prior state-of-the-art AGR, Perses, can produce results that are on average 43% smaller on Bench-Reduce and eliminate 1,750 additional duplicates in Bench-Cano.