TL;DR
Mélange is a staged static analysis framework designed to find complex vulnerabilities in massive C/C++ codebases like Chromium and Firefox. By combining fast, local path-sensitive analysis with a "demand-driven" global analysis stage, it successfully identifies cross-file bugs—such as type confusion and uninitialized memory reads—that traditional tools often miss.
What Problem Does This Paper Address?
Static analysis tools generally fall into two camps: fast but shallow (like grep-based scanners) or deep but local (like the Clang Static Analyzer). Shallow tools produce too many false positives, while deep tools usually stop at file boundaries.
In modern, object-oriented C++ projects, this "local-only" approach is a major blind spot. Because object definitions and their usages are often split across different source files, vulnerabilities frequently span these boundaries. However, performing a full, path-sensitive analysis on a whole program with millions of lines of code is computationally impossible. Mélange seeks a "middle ground" that provides global visibility without sacrificing scalability.
Methods
The authors propose a staged analysis pipeline integrated directly into the standard LLVM/Clang compiler toolchain:
- Build Interception: Mélange uses a build interceptor to "hook" into the existing compilation process (e.g.,
make). This allows it to analyze the code without requiring developers to change their build configurations. - Stage 1: Source Analyzer (Local): Using an extended version of the Clang Static Analyzer, Mélange performs a path-sensitive search within individual source files. It uses a technique called Declaration Tainting to track the state of class members and flags "candidate" bug reports.
- Stage 2: Whole-Program (WP) Analyzer (Global): This is the "demand-driven" secret sauce. Instead of analyzing the entire program from scratch, the WP analyzer only investigates the candidates flagged in Stage 1. It operates on LLVM Bitcode to trace call chains across the entire project, using Class Hierarchy Analysis (CHA) to resolve virtual function calls in C++.
- Diagnostics: It produces developer-friendly reports that include both the local source-level path to the bug and the global call chain required to trigger it.
Datasets
The researchers evaluated Mélange using a mix of synthetic benchmarks and massive real-world projects:
- NIST Juliet Benchmark (v1.2): A standard suite of C/C++ test cases for measuring True Positive and False Positive rates across various Common Weakness Enumerations (CWEs).
- Production Codebases:
- PHP Interpreter: Used to test known type-confusion vulnerabilities.
- Chromium (v38): Over 14 million lines of code.
- Firefox (May 2015 revision): A massive C++ browser engine.
- MySQL (v5.7.7): A widely used database management system.
Key Insights and Ideas
- Demand-Driven Scaling: The most important insight is that global analysis doesn't have to be exhaustive. By using local analysis to "triage" potential bugs, the global stage can focus its heavy lifting only on suspicious code paths.
- Bridging the Abstraction Gap: Mélange successfully bridges the gap between source-level analysis (Clang AST) and whole-program analysis (LLVM IR) by using metadata to map IR instructions back to specific lines of source code.
- The "Cautious" Approach: In security, missing a bug (False Negative) is often worse than a bit of extra noise (False Positive). The authors found that Mélange "errs on the side of caution," catching significantly more bugs in the Juliet benchmark than Clang SA, even if it required more manual validation.
Key Results
- Bug Discovery: Mélange identified 5 known type-confusion vulnerabilities in PHP and 3 confirmed defects in Chromium and Firefox.
- New Findings: Most notably, the tool discovered a previously unknown uninitialized memory read in Firefox (Bug 1168091), which was subsequently reported and triaged by the Mozilla team.
- Performance: Despite the complexity of global analysis, Mélange is fast enough for nightly builds. It analyzed the 14-million-line Chromium codebase in approximately 13 hours and MySQL in just over 4 hours.
- Benchmark Accuracy: On the Juliet benchmark, Mélange achieved a True Positive Rate (TPR) between 57% and 88% across different vulnerability classes (CWEs 457, 843, 194, and 195).
Limitations and Future Work
- Alias Analysis: The current implementation lacks sophisticated alias analysis. If an object is initialized via a pointer or reference (aliasing), Mélange might miss the initialization and flag a false positive uninitialized read.
- Path Insensitivity in Global Stage: While the local stage is path-sensitive, the whole-program stage is currently path- and context-insensitive to maintain speed. This can lead to "impossible" call chains being reported.
- Manual Validation: The tool still requires a human to review the final reports to filter out remaining false positives.
- Future Directions: The authors suggest incorporating more aggressive devirtualization and "Z-Ranking" (a statistical method to rank bug reports by likelihood) to further reduce the manual effort required by developers.
Summary updated