TL;DR
This paper introduces Athena, a novel compiler testing tool that uses guided stochastic program mutation to find deep, hard-to-trigger bugs in compilers like GCC and LLVM. By employing Bayesian optimization and Markov Chain Monte Carlo (MCMC) sampling, Athena generates diverse test programs that effectively explore compiler optimizations, leading to the discovery of significant bugs.
What Problem Does This Paper Address?
Compiler bugs are a serious concern, as they can lead to incorrect program execution, security vulnerabilities, and a loss of trust in software. While traditional testing methods and random program generation (fuzzing) have found many bugs, they often struggle to uncover "deep" bugs. These bugs are triggered by complex sequences of compiler optimizations and require highly specific program mutations that are difficult to generate randomly. Existing approaches like Orion, which randomly deletes unexecuted statements, are limited by their simple mutation strategy and can exhaust their search space without finding these deeper issues. The challenge is to systematically explore the vast space of possible program mutations to uncover these elusive bugs.
Methods
The core of Athena's approach is a guided mutation strategy based on Equivalence Modulo Inputs (EMI). EMI generates test variants that are guaranteed to be semantically equivalent to a seed program for a given input. Unlike previous EMI tools that only deleted code, Athena introduces two key innovations:
- Code Insertion and Deletion: Athena supports both deleting and inserting code into unexecuted regions of a program. This significantly expands the search space for generating variants, allowing for much greater diversity.
- Guided Mutation via MCMC: To navigate this expanded search space effectively, Athena employs Markov Chain Monte Carlo (MCMC) sampling guided by an objective function. This function aims to maximize the "program distance" between a generated variant and the original seed program. Program distance is a metric that captures changes in control flow, data flow, and size. By favoring variants that are significantly different from the seed, MCMC helps to explore regions of the program space that are more likely to trigger compiler bugs.
The process involves:
- Extracting statement candidates from existing code and the seed program.
- Using a database of these candidates to insert code into unexecuted regions of the seed program.
- Applying MCMC to guide the selection of mutations (insertions and deletions) to generate diverse variants.
- Compiling and executing these variants to detect compiler errors.
Datasets
The paper does not introduce new benchmark datasets. Instead, it utilizes:
- Seed Programs: Generated by Csmith [30], a well-known random C program generator.
- Statement Candidates: Extracted from existing code, including the SPEC CINT2006 benchmarks [25] and the seed programs themselves.
Key Insights and Ideas
- Insertion is Crucial for Deep Bugs: Simply deleting code (like Orion) is insufficient. The ability to insert new code, especially complex statements, into unexecuted regions is vital for creating the necessary program diversity to expose deep bugs.
- Guided Exploration Outperforms Blind Mutation: Randomly mutating code is like searching for a needle in a haystack. By using an objective function that prioritizes diversity and MCMC to guide the search, Athena can much more efficiently find the "needles" (bugs) in the vast space of possible program variants.
- Program Distance as a Diversity Metric: Defining a meaningful metric for program diversity (program distance) that considers control flow, data flow, and size is key to guiding the MCMC sampler effectively.
- EMI's Strength in Compiler Testing: The EMI approach is powerful because it provides a way to generate test cases with known semantics, simplifying the process of identifying compiler errors without needing multiple compiler implementations.
Key Results
Athena was tested on GCC and LLVM compilers over 19 months, yielding significant results:
- 72 New Bugs Found: Athena discovered 72 new bugs in GCC and LLVM.
- High Confirmation and Fix Rate: Developers confirmed all 72 bugs and fixed 68 of them.
- Serious Bugs Identified: 17 out of 40 GCC bugs were marked as P1 (most severe, release-blocking).
- Deep Bugs Discovered: The paper provides evidence that Athena is effective at finding "deep bugs" that require sophisticated mutation sequences, which Orion could not find.
- Coverage Improvement: Athena significantly improved line coverage compared to Orion, with 10 Athena variants achieving better coverage than 100 Orion variants.
Limitations and Future Work
- Ergodicity and Symmetry: The paper acknowledges that their mutation process is not perfectly symmetric, meaning it might be harder to revert from a mutated state to a previous one in a single step. This is addressed by leaving syntactic markers for deleted statements.
- Computational Cost: While effective, the MCMC-guided approach can be computationally intensive, potentially taking longer than simpler methods like Orion for shallow bugs.
- Reducing Large Test Programs: A key challenge for future work is effectively reducing the large test programs generated by Athena after bugs are found, especially when they involve multiple directories and source files.
- Extending to Other Domains: The authors suggest that the mutation strategy could be generalized to other domains beyond C compilers.
- Merging External Code: Integrating real-world code snippets into Csmith-generated seeds for mutation is noted as a challenging area for future research.
Summary updated