CAPS: An Efficient Whole-Program Critical Paths Search Framework for Large-Scale Software

Bo Jiang, Professor, Peiyang Li, Zixin Liu, Yuening Su, Hao Wang, Bo JiangSeke 2023 · DOI

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.

The CAPS framework architecture, illustrating the three main phases: scale reduction, global graph generation, and path search optimization.

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.
Illustration of graph segmentation using barrier nodes to decompose complex paths into manageable 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

BibTeX
@inproceedings{professor2023caps,
  author = {Bo Jiang, Professor and Peiyang Li and Zixin Liu and Yuening Su and Hao Wang and Bo Jiang},
  title = {{CAPS: An Efficient Whole-Program Critical Paths Search Framework for Large-Scale Software}},
  booktitle = {Seke},
  year = {2023},
  doi = {10.18293/seke2023-123},
}
Figure