Provides a class for performing customized inter-procedural data flow.

The class in this module provides an interface for performing inter-procedural data flow from a custom set of source nodes to a custom set of sink nodes. Additional data flow edges can be specified, and conversely certain nodes or edges can be designated as barriers that block flow.

NOTE: The API of this library is not stable yet and may change in the future.

Technical overview

This module implements a summarization-based inter-procedural data flow analysis. Data flow is tracked through local variables, imports and (some) object properties, as well as into and out of function calls. The latter is done by computing function summaries that record which function parameters and captured variables may flow into the function’s return value.

For example, for the function

function choice(b, x, y) {
  return b ? x : y;
}

we determine that its second and third (but not the first) parameter may flow into its return value.

Hence when we see a call a = choice(b, c, d), we propagate flow from c to a and from d to a (but not from b to a).

The inter-procedural data flow graph is represented by class PathNode and its member predicate getASuccessor. Each PathNode is a pair of an underlying DataFlow::Node and a DataFlow::Configuration, which can be accessed through member predicates getNode and getConfiguration, respectively.

Implementation details

Overall, flow is tracked forwards, starting at the sources and looking for an inter-procedural path to a sink.

Function summaries are computed by predicate flowThroughCall. Predicate flowStep computes a “one-step” flow relation, where, however, a single step may be based on a function summary, and hence already involve inter-procedural flow.

Flow steps are classified as being “call”, “return” or “level”: a call step goes from an argument to a parameter, an return step from a return to a caller, and a level step is either a step that does not involve function calls or a step through a summary.

Predicate reachableFromSource computes inter-procedural paths from sources along the flowStep relation, keeping track of whether any of these steps is a call step. Return steps are only allowed if no previous step was a call step to avoid confusion between different call sites.

Predicate onPath builds on reachableFromSource to compute full paths from sources to sinks, this time starting with the sinks. Similar to above, it keeps track of whether any of the steps from a node to a sink is a return step, and only considers call steps for paths that do not contain a return step.

Finally, we build PathNodes for all nodes that appear on a path computed by onPath.