TL;DR
The paper introduces SUPA, a novel demand-driven pointer analysis for C programs that performs precise flow- and context-sensitive analysis with strong updates on-demand. By formulating the analysis as a budget-constrained reachability problem over a pre-computed sparse value-flow graph, SUPA delivers high precision with minimal time and memory overhead, making it ideal for resource-constrained environments like IDEs.
What Problem Does This Paper Address?
Pointer analysis is a foundational static analysis technique used to determine which memory locations a pointer can reference. To be highly precise, an analysis must be flow-sensitive (respecting the execution order of statements) and support strong updates (where a write to a single concrete object completely overwrites, or "kills," its previous value).
Historically, precise whole-program flow-sensitive analyses do not scale well to large codebases. To combat this, researchers developed demand-driven analyses, which only compute points-to information for specific variables of interest (queries). However, prior demand-driven approaches for C were largely flow-insensitive, meaning they had to resort to weak updates (merging old and new values conservatively), leading to a flood of false positives for client tools like bug detectors.
The challenge this paper tackles is: How can we perform precise, sparse strong-update pointer analysis on-demand without over-analyzing the entire program?
Methods
The authors present SUPA (Strong UPdate Analysis), which shifts the paradigm from traditional control-flow graph propagation to value-flow refinement.
The SUPA pipeline operates as follows:
- Pre-Analysis: SUPA first runs a fast, flow- and context-insensitive pointer analysis (Andersen's analysis) to construct an over-approximate Sparse Value-Flow Graph (SVFG). This graph maps out all potential def-use chains for both top-level and address-taken variables.
- On-Demand Backward Reachability: When a client issues a query, SUPA traverses the SVFG backwards from the query point to find the allocation sites.
- Value-Flow Refinement via Strong Updates: As it traverses backwards, SUPA validates whether value-flow paths are realizable by performing strong updates on-the-fly. If a strong update is found (e.g., a pointer definitely overwrites a singleton object), spurious value-flow edges are filtered out, preventing further unnecessary graph traversal.
- Hybrid Multi-Stage Framework: To balance precision and efficiency, SUPA organizes its analysis into stages with user-defined budgets (measured in maximum value-flow edges traversed). It starts with a highly precise Flow-Sensitive Context-Sensitive (FSCS) analysis. If the budget is exhausted, it gracefully downgrades to a Flow-Sensitive (FS) analysis, and eventually falls back to the pre-computed flow-insensitive data.
Datasets
The authors evaluated SUPA using 18 open-source C programs of varying sizes, totaling over 2.2 million lines of code (KLOC). The suite includes standard benchmarks and real-world applications such as:
- Utilities:
grep,sed,tar,gzip,make,bison - Large applications:
bash,vim,emacs,sendmail - Scientific/game applications:
milc-v6,gnugo
The primary client application used for evaluation was Uninitialized Pointer Detection (Uninit), a critical bug-checking tool that relies heavily on strong updates to prove whether local variables have been safely initialized before use.
Key Insights and Ideas
- Sparsity + Demand-Driven is Key: Instead of computing data-flow facts across all program points, SUPA only reasons about value flows along pre-computed def-use chains, skipping irrelevant code entirely.
- Early Filtering Saves Work: Performing strong updates during a backward traversal allows SUPA to "kill" paths early. The sooner a path is blocked by a strong update, the fewer statements the algorithm has to traverse.
- Graceful Degradation: The multi-stage framework ensures that the analysis never hangs on complex queries. It answers what it can with high precision under budget, and falls back to safer, coarser approximations when resources run out.
Key Results
- High Precision at Low Cost: With a modest budget of 10,000 edges, SUPA's single-stage flow-sensitive analysis (SUPA-FS) achieved 97.4% of the precision of a full, whole-program flow-sensitive analysis.
- Blazing Fast Response Times: On average, SUPA-FS answered queries in just 0.18 seconds while consuming a mere 65 KB of memory per query.
- Massive Scaling Wins: For
emacs(over 430 KLOC), a whole-program analysis took over two hours to complete. SUPA-FS produced the exact same answers for the client queries in less than 10 minutes under a budget of 2,000 edges. - Excellent Parallelizability: Because queries can be evaluated independently, a parallel implementation of SUPA-FS using Intel Threading Building Blocks achieved an average speedup of 3.05x (and up to 6.9x) on an 8-core machine.
Limitations and Future Work
While SUPA represents a major leap forward, the authors note a few areas for improvement:
- Budget Allocation: Currently, budgets are statically configured per stage. Dynamically allocating budgets based on query complexity or client needs remains an open problem.
- Path Sensitivity: SUPA does not track path correlations (branch conditions). Integrating path-sensitivity as an additional stage could further reduce false positives in bug detection.
Summary updated