Master’s Thesis Presentation • Software Engineering • Enabling Language-specific Transformations in Language-agnostic Program Reduction

Please note: This master’s thesis presentation will take place in DC 2564.

Gaosen Zhao, Master’s candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Chengnian Sun

When a program P triggers a bug in a language implementation, program reduction can reduce P by removing program elements that are irrelevant to the bug, to facilitate debugging. Program reduction has been widely used in communities of various language implementations. Generally, program reduction techniques can be classified into language-agnostic program reducers (ARs) and language-specific program reducers (SRs). ARs work generally well in a wide range of languages but usually produce less optimal results than SRs due to lacking domain knowledge of specific languages. However, SRs require extensive engineering effort to leverage the domain knowledge, and can only function in their target language but not in other languages.

To combine the benefits of both ARs and SRs and minimize the gap between the two, a novel, general transformation framework is introduced, Metis, to enable language-specific transformations in language-agnostic program reduction. Specifically, Metis allows users to easily specify language-specific program transformations to further minimize the results by SRs, and the users only need to know the syntax of the target language and a concise domain-specific language named MTL (Metis Transformation Language) provided by Metis; Metis automatically processes the transformation rules inscribed in MTL by performing pattern matching and subsequent rewriting operations on the parse tree of the program under reduction.

We comprehensively evaluated Metis on two benchmark sets of C and SMT-LIBv2 programs, and the results demonstrate that Metis yields much smaller programs than the state-of-the-art language-agnostic program reducer by 35.8% on average. We also compared Metis with two SRs: ddSMT and C-Reduce. Metis produces results of comparable size to ddSMT, but with a noticeable 28.9% shorter reduction time; while falling short of matching the reduced program size by C-Reduce, Metis saves 82.4% of queries and achieves a speed improvement of 30.6% less runtime.