Abstract
Eliminating vulnerabilities from low-level code is vital for securing software. Static analysis is a promising approach for discovering vulnerabilities since it can provide developers early feedback on the code they write. But, it presents multiple challenges not the least of which is understanding what makes a bug exploitable and conveying this information to the developer. In this paper, we present the design and implementation of a practical vulnerability assessment framework, called Melange. Melange performs data and control flow analysis to diagnose potential security bugs, and outputs well-formatted bug reports that help developers understand and fix security bugs. Based on the intuition that real-world vulnerabilities manifest themselves across multiple parts of a program, Melange performs both local and global analyses. To scale up to large programs, global analysis is demand-driven. Our prototype detects multiple vulnerability classes in C and C++ code including type confusion, and garbage memory reads. We have evaluated Melange extensively. Our case studies show that Melange scales up to large codebases such as Chromium, is easy-to-use, and most importantly, capable of discovering vulnerabilities in real-world code. Our findings indicate that static analysis is a viable reinforcement to the software testing tool set.
Introduction
Static analysis tools for C/C++ generally face a trade-off between speed and depth. Shallow tools, such as grep-based scanners, are fast but prone to high false-positive rates. Conversely, deep analysis tools like the Clang Static Analyzer provide path-sensitivity but are typically limited to single-file boundaries. In modern, object-oriented C++ projects like Chromium or Firefox, this "local-only" approach creates a significant blind spot: vulnerabilities often span multiple source files where object definitions and usages are decoupled.
Mélange is designed to bridge this gap. It provides a staged static analysis framework that combines fast, local path-sensitive analysis with a demand-driven global analysis stage. This allows it to identify complex cross-file bugs—such as type confusion and uninitialized memory reads—without the computational impossibility of whole-program path-sensitive analysis.
The Mélange Architecture
The core of Mélange is a staged pipeline integrated into the standard LLVM/Clang compiler toolchain. The process begins with Build Interception, where Mélange "hooks" into the existing compilation process (e.g., make) to analyze code without requiring build configuration changes.
As illustrated in the architecture above, the analysis is split into two primary stages:
- Source Analyzer (Local): This stage uses an extended version of the Clang Static Analyzer to perform path-sensitive searches within individual files. It employs "Declaration Tainting" to track the state of class members and flags potential "candidate" bugs.
- Whole-Program (WP) Analyzer (Global): To maintain scalability, the WP analyzer only investigates the candidates flagged in the first stage. It operates on LLVM Bitcode to trace call chains across the entire project, utilizing Class Hierarchy Analysis (CHA) to resolve virtual function calls in C++.
Local Analysis Foundations
The local stage leverages the robust infrastructure of the Clang Static Analyzer. By extending its Data Flow Analysis (DFA) engine, Mélange can perform sophisticated symbolic execution within a single translation unit before passing suspicious paths to the global stage.
This staged approach ensures that the heavy lifting of global analysis is only performed on code paths that have already been triaged as suspicious, effectively scaling deep analysis to codebases with millions of lines of code.
Experimental Evaluation
The researchers evaluated Mélange using the NIST Juliet Benchmark and several massive production codebases, including the PHP Interpreter, MySQL, Chromium (14M+ LOC), and Firefox.
Key Results
- Bug Discovery: Mélange identified five known type-confusion vulnerabilities in PHP and three confirmed defects in Chromium and Firefox. Most significantly, it discovered a previously unknown uninitialized memory read in Firefox (Bug 1168091), which was subsequently triaged by Mozilla.
- Performance: The tool demonstrated impressive scalability, analyzing the entire Chromium codebase in approximately 13 hours and MySQL in just over 4 hours. This performance makes it suitable for integration into nightly build cycles.
- Accuracy: On the Juliet benchmark, Mélange achieved a True Positive Rate (TPR) between 57% and 88% across various vulnerability classes (CWEs 457, 843, 194, and 195).
Limitations and Future Work
While effective, Mélange currently lacks sophisticated alias analysis, which can lead to false positives when objects are initialized via pointers. Additionally, while the local stage is path-sensitive, the global stage is currently path-insensitive to maintain performance, occasionally resulting in "impossible" call chains. Future iterations aim to incorporate aggressive devirtualization and statistical ranking methods like "Z-Ranking" to further reduce the manual effort required for report validation.
Conclusion
Mélange demonstrates that staged, demand-driven analysis is a viable path forward for securing large-scale C++ software. By focusing global analysis resources on candidates identified through local path-sensitive triage, Mélange provides a practical balance between depth and scalability, successfully uncovering real-world vulnerabilities in some of the world's most complex codebases.
Summary updated