Finding deep compiler bugs via guided stochastic program mutation

Citations Over TimeTop 1% of 2015 papers

Abstract

Compiler testing is important and challenging. Equivalence Modulo Inputs (EMI) is a recent promising approach for compiler validation. It is based on mutating the unexecuted statements of an existing program under some inputs to produce new equivalent test programs w.r.t. these inputs. Orion is a simple realization of EMI by only randomly deleting unexecuted statements. Despite its success in finding many bugs in production compilers, Orion’s effectiveness is still limited by its simple, blind mutation strategy. To more effectively realize EMI, this paper introduces a guided, advanced mutation strategy based on Bayesian optimization. Our goal is to generate diverse programs to more thoroughly exercise compilers. We achieve this with two techniques: (1) the support of both code deletions and insertions in the unexecuted regions, leading to a much larger test program space; and (2) the use of an objective function that promotes control-flow-diverse programs for guiding Markov Chain Monte Carlo (MCMC) optimization to explore the search space. Our technique helps discover deep bugs that require elaborate mutations. Our realization, Athena, targets C compilers. In 19 months, Athena has found 72 new bugs — many of which are deep and important bugs — in GCC and LLVM. Developers have confirmed all 72 bugs and fixed 68 of them.

Related Papers

• → MPI-aware compiler optimizations for improving communication-computation overlap(2009)43 cited
• Operational refinement for compiler correctness(2012)
• → Verified Density Compilation for a Probabilistic Programming Language(2023)6 cited
• A Prolog Compiler for the PLM(1984)
• → Towards a framework for the general intensional programming compiler in the GIPSY(2004)13 cited