Introduction
Static taint analysis is a fundamental technique in software security, used to track the flow of untrusted external inputs (sources) to sensitive execution points (sinks). While powerful, applying this analysis to massive software projects remains a significant challenge. The Clang Static Analyzer (CSA), a widely used tool, generates an "ExplodedGraph" that represents every possible program state. For large-scale applications, this graph becomes prohibitively large and redundant, leading to "state explosion" where analyzers exhaust memory or time before identifying critical vulnerabilities.
To address these scalability issues, we present CAPS (Critical Paths Search), a framework designed to make whole-program taint analysis feasible for large codebases by significantly reducing graph complexity and optimizing search algorithms.
Methodology
The CAPS framework operates in three distinct phases to transform raw static analysis data into an efficient, searchable model.
1. ExplodedGraph Scale Reduction
The first phase focuses on pruning the massive ExplodedGraph generated during intra-procedural analysis. CAPS aggressively reduces the graph size by:
- Merging Synonymous Nodes: Combining nodes that share the same state and adjacent locations.
- Merging Channel Nodes: Simplifying linear paths that lack branching logic.
- Deleting Redundant Nodes: Removing nodes that do not carry symbolic information related to tainted parameters.
This preprocessing step ensures that only the "critical" parts of the graph—those relevant to potential taint flows—are retained.
2. Global Exploded Graph Generation
Once individual functions are reduced, they are imported into a Neo4j graph database. CAPS then "stitches" these disparate intra-procedural graphs together by inserting call edges between functions. This creates a unified, persistent, and searchable global model of the entire software project, moving the analysis out of volatile compiler memory.
3. Path Search Optimization
To navigate the global graph efficiently, CAPS employs two primary algorithmic optimizations:
- Loop Deletion: The graph is converted into a Directed Acyclic Graph (DAG) by identifying and removing back-edges through Depth-First Search (DFS) traversal.
- Graph Segmentation: To prevent the exponential growth of potential paths, CAPS identifies "barrier nodes" to divide the search space into smaller segments.
By treating the final path as a Cartesian product of these segments (e.g., $FormerPathSet \otimes LatterPathSet$), the framework avoids the traditional path explosion problem.
Experimental Evaluation
The effectiveness of CAPS was evaluated using three large-scale GNU open-source projects: Tar (102k LoC), Mailutils (209k LoC), and M4 (142k LoC). These projects represent complex, real-world software where standard inter-procedural analysis often fails.
Key Results
- Graph Reduction: CAPS achieved an average reduction of 81.96% in nodes and 78.45% in edges across the test suite. In the case of the M4 project, node reduction reached 85%.
- Search Efficiency: Using the Weighted Rate Ratio (WRR) metric, CAPS demonstrated superior performance compared to standard DFS.
- Speedup: The framework provided significant performance gains, with an average speedup of 41.56x for Mailutils. Even in the most challenging case (Tar), CAPS remained over 7 times faster than the baseline approach.
Conclusion and Future Work
The CAPS framework demonstrates that the primary bottleneck in large-scale static analysis is graph redundancy. By focusing on symbolic-carrying nodes and utilizing graph database technology for whole-program queries, CAPS enables efficient vulnerability detection in massive codebases.
Future work will focus on improving symbolic inference for complex data types (such as structs and floating-point numbers) to prevent "breakpoints" in taint chains and exploring more advanced graph algorithms to further enhance search completeness and speed.
Summary updated