Will you still compile me tomorrow? static cross-version compiler validation

Chris Hawblitzel, Shuvendu K. Lahiri, Kshama Pawar, Hammad Hashmi, Sedar Gokbulut, Lakshan Fernando, Dave Detlefs, Scott WadsworthESEC/SIGSOFT FSE 2013 · DOI

TL;DR

This paper introduces a novel cross-version compiler validation technique that compares the assembly output of different compiler versions, significantly reducing false alarms compared to traditional translation validation. This method, applied to the .NET CLR JIT compiler, effectively identifies correctness and performance bugs with a low false alarm rate, making compiler validation more practical for daily development.

What Problem Does This Paper Address?

Compilers are incredibly complex, and adding new features or optimizations can inadvertently introduce bugs. For Just-In-Time (JIT) compilers, these bugs can cause already deployed programs to crash or even introduce security vulnerabilities. While regression testing is standard, it's not foolproof. Traditional compiler validation methods like translation validation, which use theorem provers to check semantic equivalence between source and compiled code, suffer from a high rate of "false alarms" – instances where the prover fails to prove equivalence even when the code is correct. This makes it difficult for developers to sift through the noise and find actual bugs. This paper aims to address this by developing a more practical and less noisy approach to compiler validation.

Methods

The core of this work is cross-version compiler validation. Instead of comparing source code to compiled output, the authors compare the assembly output generated by different versions of the same compiler. This is done across various dimensions:

  • Time: Comparing compiler versions over several months (e.g., monthly check-ins).
  • Architecture: Comparing x86 and ARM outputs.
  • Compilation Scenarios: Comparing JIT compilation with a mostly-ahead-of-time (MDIL) approach.
  • Optimization Levels: Comparing optimized vs. unoptimized code.

To achieve this, they encode assembly language instructions into the Boogie verification language. They then use the SymDiff tool to compare these Boogie encodings, feeding the result to the Boogie verifier and the Z3 SMT solver to prove semantic equivalence.

A key innovation is their root-cause analysis. When the validator flags a difference (a potential bug or false alarm), it automatically generates counterexample traces. The root-cause analysis then processes these traces to identify the most likely source of the divergence, grouping these causes into "buckets" to simplify human inspection. This significantly reduces the manual effort required to investigate differences.

Datasets

The experiments were conducted on the .NET Common Language Runtime (CLR) JIT compiler. The input consisted of 16 test programs, including:

  • Publicly available Silverlight libraries.
  • Six large bytecode files from the Bartok compiler test suite.

These programs were compiled using the CoreCLR subset of the CLR, which is used for mobile code and is considered security-critical. The authors also modified the CLR to emit symbolic information for addresses and fields, and to provide more detailed type information for method calls, which were crucial for the validator's operation.

Key Insights and Ideas

  • Cross-version validation is surprisingly effective and less noisy: Comparing different compiler versions over time yields a much lower false alarm rate (2.2%) than traditional translation validation (10-40%). This is because compiler development often focuses on refactoring or adding features without altering existing behavior, leading to syntactically identical or semantically very similar outputs.
  • Root-cause analysis is crucial for practicality: Simply flagging differences isn't enough. The ability to automatically pinpoint why two pieces of code differ and group these reasons into buckets dramatically reduces the human effort needed to analyze potential bugs.
  • Syntactic identity is common but insufficient: While many methods remain syntactically identical across compiler versions (especially for x86), semantic differences can still exist and require deeper analysis. For newer architectures like ARM, syntactic differences are more common, making semantic validation even more critical.
  • Optimization levels introduce more divergence than time: Validating optimized vs. unoptimized code resulted in a significantly higher false alarm rate (19%) compared to month-to-month comparisons, highlighting the complexity introduced by optimization passes.
  • False alarms can reveal performance bugs: Some differences flagged as false alarms for correctness turned out to be real performance regressions, suggesting that the validation process can uncover issues beyond strict functional correctness.

Key Results

  • The cross-version validator achieved an average false alarm rate of 2.2% for month-to-month comparisons.
  • The root-cause analysis successfully grouped 53% to 96% of differences into small numbers of buckets, significantly reducing manual analysis effort.
  • The tool found 12 previously unknown bugs in the CLR compiler, including 6 correctness bugs and 6 performance regressions.
  • For fault injection experiments, the tool had a false negative rate of 3%, indicating good effectiveness in catching actual bugs.
  • Validation of optimized vs. unoptimized code yielded a 19% false alarm rate.
  • Validation of x86 vs. ARM code had a 29% false alarm rate, making it less practical for frequent use but potentially useful for bootstrapping new architectures.

Limitations and Future Work

  • Unsoundness: The validator is not 100% sound due to assumptions about memory aliasing, the run-time system, and simplified loop handling (unrolling). This can lead to missed bugs (false negatives) or incorrect alarms (false positives). For instance, the byte-accurate memory model was sacrificed for performance, potentially missing bugs related to memory overlaps.
  • Loop Handling: Loops are unrolled a fixed number of times (n=2), meaning differences that manifest only after more iterations might be missed.
  • Exception Handling: The current model assumes thrown exceptions exit the method, potentially missing semantic differences in exception handlers.
  • Performance Bottlenecks: While generally efficient, some complex methods can cause theorem prover timeouts, limiting the scope of validation.
  • Future Work: The authors suggest further research into more sophisticated memory models, improved loop handling, and potentially combining their dataflow-graph-based root-cause analysis with MAX-SAT techniques for even better bug localization. They also note that the false alarm rate is dependent on how often the validator is run, suggesting that more frequent runs (e.g., after each check-in) would further reduce the effective false alarm rate.

Summary updated

BibTeX
@inproceedings{hawblitzel2013will,
  author = {Chris Hawblitzel and Shuvendu K. Lahiri and Kshama Pawar and Hammad Hashmi and Sedar Gokbulut and Lakshan Fernando and Dave Detlefs and Scott Wadsworth},
  title = {{Will you still compile me tomorrow? static cross-version compiler validation}},
  booktitle = {ESEC/SIGSOFT FSE},
  year = {2013},
  doi = {10.1145/2491411.2491442},
}
Figure