Please note: This PhD seminar will take place in DC 3102.
Mengxiao (Max) Zhang, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Chengnian Sun
Program reduction is a practical technique widely used for debugging compilers. To report a compiler bug with a bug-triggering program, one needs to minimize the program by removing bug irrelevant program elements first. Though existing program reduction techniques, such as C-Reduce and Perses, can reduce a bug-triggering program as a whole, they overlook the fact that the degree of relevance of each remaining token to the bug varies.
To this end, we propose Pairwise Program Reduction (PPR), a new program reduction technique for minimizing a pair of programs w.r.t. certain properties. Given a seed program Ps, a variant Pv derived from Ps, and the properties Ps and Pv exhibit separately (e.g., Pv crashes a compiler whereas Ps does not), PPR not only reduces the sizes of Ps and Pv, but also minimizes the differences between Ps and Pv. The final result of PPR is a pair of minimized programs that still preserve the properties, but the minimized differences between the pair highlight the critical program elements that are highly related to the bug.
To thoroughly evaluate PPR, we manually constructed the first pairwise benchmark suite from real-world compiler bugs (20 bugs in GCC and LLVM, 9 bugs in Rustc and 9 bugs in JerryScript). The evaluation results show that PPR significantly outperforms the baseline: DD, a variant of Delta Debugging. Specifically, on large and complex programs, PPR’s reduction results are only 0.6% of those by DD w.r.t. program size. The sizes of the minimized variants (i.e., Pv) by PPR are also comparable to those by Perses and C-Reduce; but PPR offers more for debugging by highlighting the critical, bug-inducing changes via the minimized differences. Evaluation on Rust and JavaScript demonstrates PPR’s strong generality to other languages.
200 University Avenue West
Waterloo, ON N2L 3G1
Canada
