10 min read
On this page

Whole-Program Analysis

Call Graph Construction

A call graph is a directed graph where nodes represent functions (procedures, methods) and edges represent call relationships. Accurate call graph construction is the foundation of interprocedural analysis — all subsequent analyses depend on knowing which functions may call which.

Challenges

Indirect calls: Function pointers (C/C++), virtual dispatch (OO languages), higher-order functions (functional languages), and dynamic dispatch (JavaScript, Python) make call targets statically ambiguous. The call graph construction must resolve these targets, typically using pointer or type analysis.

Mutual dependence: Call graph construction depends on pointer analysis (to resolve indirect calls), but pointer analysis depends on the call graph (to know which functions to analyze). This creates a chicken-and-egg problem. Solutions: iterate (compute both simultaneously to a fixed point), or use a conservative initial approximation.

Class Hierarchy Analysis (CHA)

For OO languages with single dispatch, CHA resolves virtual calls using the class hierarchy alone. A call o.m() where o has declared type T can invoke m() in T or any subclass of T that overrides m().

  • Cost: O(|classes| × |methods|) preprocessing, O(|subtypes|) per call site.
  • Precision: Very imprecise — includes all possible implementations regardless of what objects are actually created. But fast and simple.
  • Assumption: All subtypes in the class hierarchy might be instantiated.

Rapid Type Analysis (RTA)

RTA refines CHA by tracking which classes are actually instantiated (have a new expression) anywhere in the reachable program. A virtual call o.m() on declared type T resolves only to implementations in instantiated subtypes of T.

  • Improvement over CHA: Filters out classes that exist in the hierarchy but are never constructed. Significant in frameworks with deep hierarchies.
  • Cost: Linear scan to collect instantiated types, then per-call resolution as CHA.
  • Limitation: Still flow-insensitive and context-insensitive. Does not track which objects reach which call sites.

Variable Type Analysis (VTA)

VTA (Sundaresan et al., 2000) performs a type propagation analysis: track the set of possible runtime types flowing to each variable. Uses a type propagation graph — assignment edges propagate type sets. More precise than RTA because it considers data flow (which types actually reach which variables), but still flow-insensitive.

Points-To-Based Call Graph

The most precise practical approach: use pointer analysis to determine which function objects each function pointer or receiver variable can point to. The call graph and points-to sets are computed simultaneously (on-the-fly construction). Andersen-style or k-object-sensitive analysis produces precise call graphs for Java. For C/C++, field-sensitive Andersen's analysis is standard.

Interprocedural Analysis

Context Sensitivity

Intraprocedural analysis treats each function call as a black box or uses summaries. Interprocedural analysis crosses function boundaries, analyzing callee bodies in the context of each call site.

Context-insensitive: Merge all calling contexts. A function has one abstract state regardless of how it is called. Fast but imprecise — "data flow pollution" across unrelated call sites.

Context-sensitive approaches:

Cloning-based (call-string): Create a separate copy of the function for each calling context (defined by the last k call sites). k=1 is common. Exponential in k for recursive programs. The summary approach avoids cloning by computing input-output transfer functions.

Functional (summary-based): Compute a summary for each function: a transfer function mapping input abstract states to output abstract states. At call sites, apply the summary to the caller's state. The summary can be parameterized by calling context (context-sensitive summaries). This avoids re-analyzing the callee for each caller.

Object sensitivity: For OO languages, distinguish contexts by the receiver object's allocation site (or its allocation context). Demonstrated to be more precise than call-site sensitivity for Java by Milanova et al. and Smaragdakis et al.

IFDS Framework

The Interprocedural Finite Distributive Subset (IFDS) framework (Reps, Horwitz, and Sagiv, 1995) provides a polynomial-time algorithm for a broad class of interprocedural data flow analyses.

Requirements: The data flow domain must be a finite set D (e.g., set of variables, definitions, or taint labels). Transfer functions must be distributive (f(x ⊔ y) = f(x) ⊔ f(y)) and representable as functions from 2^D to 2^D. Distributive functions over finite sets can be represented as binary relations on D ∪ {0} (the representation relation).

Graph reachability formulation: IFDS reduces interprocedural data flow to a graph reachability problem on an exploded supergraph:

  • Each program point p is exploded into |D|+1 nodes: (p, 0), (p, d₁), ..., (p, dₙ).
  • Transfer function edges encode the binary relation: edge (p, dᵢ) → (q, dⱼ) means if fact dᵢ holds at p, then dⱼ holds at q.
  • Call/return edges enforce context sensitivity using matched-parenthesis reachability (CFL-reachability with Dyck language constraints).
  • A fact d holds at program point p iff (start, 0) can reach (p, d) via a valid (realizable) path.

Complexity: O(|E| × |D|³) where |E| is the number of supergraph edges. Polynomial, and practical for large programs with moderate-size domains.

Applications: Taint analysis, typestate analysis, copy constant propagation, uninitialized variable detection, secure information flow.

IDE Framework

The Interprocedural Distributive Environment (IDE) framework (Sagiv, Reps, and Horwitz, 1996) extends IFDS to handle environment transformers — transfer functions that map environments (variable → value) rather than just sets. The domain is (D → L) where L is a finite-height lattice.

Edge functions in IDE produce/consume values from L along each edge of the exploded supergraph. The framework composes edge functions along realizable paths, computing the meet-over-all-valid-paths solution.

Applications: Linear constant propagation (x = 2*y + 3), copy propagation with constants, typestate with values.

Heros and FlowDroid

Heros (Bodden, 2012): Generic implementation of the IFDS/IDE framework for Java (Soot-based). Provides the interprocedural infrastructure; users supply the domain D and transfer functions. Handles Java-specific features: virtual dispatch, exceptions, static initializers.

FlowDroid (Arzt et al., 2014): Taint analysis for Android apps built on Heros/IFDS. Tracks data flow from sources (GPS, contacts, microphone) to sinks (network, SMS, logs). Handles Android lifecycle (activities, services, broadcast receivers), inter-component communication (intents), and callbacks. The standard benchmark for Android taint analysis.

Modular and Compositional Analysis

Motivation

Whole-program analysis requires all code to be available and analyzed together. This is impractical for: large codebases (analysis time), libraries (code unavailable), incremental development (re-analysis on every change). Modular analysis addresses these by analyzing each module (function, class, package) independently.

Summary-Based Modularity

Analyze each function independently, computing a summary that characterizes its behavior abstractly. At call sites, the summary is instantiated with the caller's abstract state. Summaries must capture all relevant behaviors without reference to specific callers.

Challenges: Summaries for pointer-manipulating code require describing heap transformations (separation logic summaries, as in Infer). Summaries for higher-order functions require describing behavior for all possible function arguments.

Compositional Analysis

Bottom-up: Analyze callees first, compute summaries, then analyze callers using summaries. Works well when the call graph is acyclic (no recursion) or when recursive functions have bounded summaries.

Top-down: Start from the entry point, analyze the caller, and when a call is encountered, analyze the callee in the caller's context. Context-sensitive by construction. Can be demand-driven (analyze only functions relevant to a query).

Bi-directional: Combine bottom-up summaries with top-down refinement. Compute coarse summaries bottom-up, then refine with top-down context information.

Infer's Compositional Approach

Facebook's Infer analyzes each function independently using bi-abduction in separation logic. For a function call, Infer:

  1. Abduces the precondition: what heap structure must the caller provide?
  2. Frames the postcondition: what heap structure does the callee produce, and what does the caller retain?

Summaries are pre/post pairs in separation logic. At call sites, the caller's state is matched against the precondition; the postcondition is applied. This scales to millions of lines because each function analysis is independent — parallelizable and incremental.

Incremental Analysis

Motivation

During development, only a small fraction of code changes between builds. Re-analyzing the entire program is wasteful. Incremental analysis updates analysis results to reflect code changes without full re-computation.

Change Impact Analysis

Given a code change (diff), determine which analysis results are potentially affected. A conservative approach: invalidate all summaries of changed functions and their transitive callers. A precise approach: compare old and new transfer functions; only invalidate if the summary actually changed.

Incremental Datalog

Many analyses are expressed in Datalog (e.g., Doop for Java pointer analysis). Incremental Datalog engines (e.g., Soufflé with provenance, Differential Datalog/DDlog) support efficient updates: when input facts change, they incrementally update derived facts without full re-evaluation. Provenance tracking identifies which derived facts depend on which input facts.

IDE/CI Integration

Incremental analysis is critical for IDE integration (real-time feedback as the developer types) and CI pipelines (fast analysis on pull requests). Infer's --reactive mode analyzes only changed files and their dependents. RacerD and Pulse operate incrementally within Facebook's code review workflow.

Scalability Techniques

Demand-Driven Analysis

Instead of computing all facts for all program points, answer specific queries on demand. A query "is variable x tainted at line 42?" triggers backward exploration from line 42, analyzing only relevant code paths. CFL-reachability-based demand-driven pointer analysis (Sridharan and Bodden) and demand-driven IFDS (Duesterwald et al.) achieve this.

Parallel and Distributed Analysis

SCC-based parallelism: Strongly connected components of the call graph can be analyzed in topological order. Independent SCCs can be analyzed in parallel. Within an SCC (mutually recursive functions), analysis must iterate to a fixed point.

MapReduce/Spark-based analysis: Distribute analysis of independent functions across cluster nodes. Aggregate summaries centrally. Challenges: load balancing, summary communication overhead.

BDD and Datalog Representations

BDDs compactly represent large sets and relations. Datalog provides a declarative specification of analyses, compiled to efficient evaluation strategies by engines like Soufflé (compiled to parallel C++).

Soufflé optimizations: Semi-naive evaluation, auto-scheduling of join orders, parallelism via OpenMP, specialized data structures for common patterns. Analyzes million-line Java programs in minutes for standard pointer analysis configurations.

Standard compilation analyzes each translation unit (source file) independently. LTO defers optimization to link time, when all code is available.

ThinLTO (LLVM): Lightweight LTO that computes module summaries at compile time. At link time, summaries guide cross-module decisions (inlining, devirtualization) without loading full IR for all modules. Scalable to large projects (Chrome, LLVM itself).

Full LTO: Merge all LLVM IR modules into one, run the full optimization pipeline. Maximum optimization but long link times and high memory usage.

Whole-Program Devirtualization

With the full class hierarchy available, the linker can determine that a virtual call has a unique target and replace it with a direct call. Combined with inlining, this eliminates virtual dispatch overhead entirely.

  • Cross-module inlining: Inline functions defined in other translation units.
  • Dead code elimination: Remove unreachable functions.
  • Global variable optimization: Internalize globals that are not externally visible; constant propagation across modules.
  • Whole-program constant propagation: Propagate constant arguments through the call graph.

Profile-Guided Optimization (PGO)

Instrument the program, run it on representative inputs, collect execution profiles (branch frequencies, function call counts, cache behavior). Use the profile to guide optimizations at link time: hot function inlining, cold code separation, branch layout, register allocation priority.

AutoFDO: Use sampling-based profiles (from perf) rather than instrumented profiles. Lower-quality data but zero runtime overhead during profiling, enabling production profiling.