Interprocedural Summaries and the Context-Sensitivity Bill

A helper that returns its argument unchanged is trivial to analyze in isolation: the return value is the parameter. A caller that passes a validated pointer gets a validated pointer back; a caller that passes an unchecked one gets an unchecked one back. A context-insensitive analysis summarizes the helper once, merges both callers, and concludes that the return may be unchecked. The summary is sound and useless, and the false positive it causes is not in the helper.

The call graph comes first, and it is an approximation

Before a function can be summarized, the analyzer must know who calls it. For direct calls to statically named functions, the edge is syntactic. For everything else the answer is a set of possible targets.

Class hierarchy analysis resolves a virtual call by the declared receiver type and adds every override in every subclass. It is cheap, needs only the class hierarchy, and over-approximates badly in programs with large frameworks. Rapid type analysis narrows the set to classes that are actually instantiated somewhere in the program, which removes dead subclasses but still merges distinct objects. Points-to analysis resolves the receiver to a set of allocation sites, which is more precise and far more expensive; the underlying relation is the subject of May-Alias Analysis and Points-To Sets.

Function pointers, higher-order functions, reflection, and dynamic property lookup make the call graph fundamentally incomplete. A tool has three choices: include a conservative “unknown target” node that taints everything it touches, ignore the call and accept unsoundness, or require annotations and models for the dynamic boundary. The first is safe and noisy, the second is precise and wrong, and the third is what production analyzers do for standard libraries, with hand-written models for the parts that matter.

A summary is a transfer function for a whole function

A summary is a compact description of a function’s effect, strong enough for callers to use without re-analyzing the body. The simplest summary is a pair of sets: the inputs the function reads and the globals it writes. That is enough for a linter that wants to know whether calling a function can invalidate a cached fact.

A more precise summary is a relation between input and output states. For a taint analysis, the summary might say “the return value is tainted if parameter 0 is tainted, and parameter 1 is never tainted”. For a nullness analysis, it might say “the return is non-null if parameter 0 is non-null”. For a resource analysis, it might say “the function acquires one handle and releases it on every normal return, but not on the exceptional path”.

Summaries compose. If f calls g, the summary of f is computed from the summary of g rather than from its body. Composition is what makes whole-program analysis scale: each function is analyzed once per context, and callers only read a small relation. The body analysis itself runs over the function’s control-flow graph, built as described in Control-Flow Graphs and Dominance, so any imprecision in the graph propagates into the summary. The composition must respect the analysis’s abstraction, which is why summaries for may analyses are joined and summaries for must analyses are intersected, mirroring the lattice rules from Monotone Dataflow and Fixpoint Convergence.

Recursion breaks the one-pass composition. A recursive function’s summary depends on its own summary, so the analyzer must iterate over strongly connected components of the call graph until the summaries stop changing. The fixpoint is over the same lattice, and termination relies on the same finite-height argument. Mutual recursion is handled the same way, with the entire component iterated together.

Context sensitivity is the choice of how much caller identity to keep

A context-insensitive analysis has one summary per function. A context-sensitive analysis has one per context, where the context is some abstraction of the calling stack. The common forms are:

• Call-string sensitivity, also called k-CFA: the context is the last k call sites. With k = 1, a function called from two sites is analyzed twice; with k = 2, the context includes the caller’s caller, and the count grows.
• Functional sensitivity: the context is the abstract input state, so two calls with the same abstract arguments share a summary. This merges call sites that behave identically and separates those that do not.
• Object sensitivity: for object-oriented languages, the context is the receiver object’s allocation site, which captures the common pattern of one helper per object.
• Type sensitivity: the context is the receiver’s class, a cheaper approximation of object sensitivity.

The precision gain is real but uneven. A utility called from hundreds of sites with the same argument shape gains nothing from call-string sensitivity and pays for hundreds of summaries. A callback invoked on objects of two different classes gains a lot from object sensitivity, because the field it reads has a different type in each. This is why the choice is empirical: it depends on the codebase’s idiom, not on a universal rule.

def summary_key(func, context):
    # Context-insensitive: context is ().
    # 1-CFA: context is the last call site.
    # Functional: context is a canonical hash of the abstract input state.
    return (func, context)

The key is the whole design. Everything downstream, including caching, invalidation, and the fixpoint over recursion, is indexed by it. A key that is too coarse merges unrelated facts; a key that is too fine creates a cache that never hits and an analysis that never finishes.

Closed-world and modular analysis pull in opposite directions

A whole-program analyzer assumes it can see every caller. That assumption lets it compute a call graph, propagate facts from entry points, and discard unreachable code. It is also false for any code that ships as a library, is loaded as a plugin, or is called from a language runtime the analyzer does not model.

A modular analyzer assumes the opposite: each function must be analyzable with only its own body and the summaries of its callees, and the result must hold for any caller. That forces summaries to be conservative in the inputs they accept and guarantees they remain valid under separate compilation. The cost is precision at every boundary: a function that is only ever called with non-null arguments must still be summarized as if it could receive null, unless the language has a non-null type that the analyzer trusts.

Most real tools mix the two. The main application is analyzed as a closed world, and the standard library and third-party packages are treated as opaque with handwritten models. When a model is missing, the conservative fallback is usually “this call may do anything”, which is sound and produces the familiar cluster of findings around every unfamiliar API.

Where the approximation shows up as a finding

The consequences for a linter are predictable. A context-insensitive summary of a generic container will merge elements of different types and report a type confusion that cannot occur. A call graph that includes an override never reached at runtime will report a resource leak in dead code. A missing model for a logging API will report that user input reaches a sink when the sink is a formatter that escapes it.

None of these are implementation defects in the narrow sense; they are the visible edge of the abstraction, and they are why The Structure of False Positives separates context merging and missing models into distinct categories. The useful response is to make the abstraction visible: report the call chain that produced the finding, so the user can see which edge was assumed, and allow that edge to be refined by an annotation or a model. A finding that says “tainted data reaches execute via render at line 40” can be triaged in seconds; the same finding with only the sink location cannot.