Class API::Node

A node in the API graph, that is, a value that can be tracked interprocedurally.

The API graph is a graph for tracking values of certain types in a way that accounts for inheritance and interprocedural data flow.

API graphs are typically used to identify “API calls”, that is, calls to an external function whose implementation is not necessarily part of the current codebase.

Basic usage

The most basic use of API graphs is typically as follows:

1. Start with API::getTopLevelMember for the relevant library.
2. Follow up with a chain of accessors such as getMethod describing how to get to the relevant API function.
3. Map the resulting API graph nodes to data-flow nodes, using asSource, asSink, or asCall.

The following examples demonstrate how to identify the expression x in various basic cases:

# API::getTopLevelMember("Foo").getMethod("bar").getArgument(0).asSink()
Foo.bar(x)

# API::getTopLevelMember("Foo").getMethod("bar").getKeywordArgument("foo").asSink()
Foo.bar(foo: x)

# API::getTopLevelMember("Foo").getInstance().getMethod("bar").getArgument(0).asSink()
Foo.new.bar(x)

Foo.bar do |x| # API::getTopLevelMember("Foo").getMethod("bar").getBlock().getParameter(0).asSource()
end

Data flow

The members predicates on this class generally take inheritance and data flow into account.

The following example demonstrates a case where data flow was used to find the sink x:

def doSomething f
  f.bar(x) # API::getTopLevelMember("Foo").getInstance().getMethod("bar").getArgument(0).asSink()
end
doSomething Foo.new

The call API::getTopLevelMember("Foo").getInstance() identifies the Foo.new call, and getMethod("bar") then follows data flow from there to find calls to bar where that object flows to the receiver. This results in the f.bar call.

Backward data flow

When inspecting the arguments of a call, the data flow direction is backwards. The following example illustrates this when we match the x parameter of a block:

def doSomething &blk
  Foo.bar &blk
end
doSomething do |x| # API::getTopLevelMember("Foo").getMethod("bar").getBlock().getParameter(0).asSource()
end

When getParameter(0) is evaluated, the API graph backtracks the &blk argument to the block argument a few lines below. As a result, it eventually matches the x parameter of that block.

Inheritance

When a class or module object is tracked, inheritance is taken into account.

In the following example, a call to Foo.bar was found via a subclass of Foo, because classes inherit singleton methods from their base class:

class Subclass < Foo
  def self.doSomething
    bar(x) # API::getTopLevelMember("Foo").getMethod("bar").getArgument(0).asSink()
  end
end

Similarly, instance methods can be found in subclasses, or ancestors of subclases in cases of multiple inheritance:

module Mixin
  def doSomething
    bar(x) # API::getTopLevelMember("Foo").getInstance().getMethod("bar").getArgument(0).asSink()
  end
end
class Subclass < Foo
  include Mixin
end

The value of self in Mixin#doSomething is seen as a potential instance of Foo, and is thus found by getTopLevelMember("Foo").getInstance(). This eventually results in finding the call bar, due to its implicit self receiver, and finally its argument x is found as the sink.

Backward data flow and classes

When inspecting the arguments of a call, and the value flowing into that argument is a user-defined class (or an instance thereof), uses of getMethod will find method definitions in that class (including inherited ones) rather than finding method calls.

This example illustrates how this can be used to model cases where the library calls a specific named method on a user-defined class:

class MyClass
  def doSomething
    x # API::getTopLevelMember("Foo").getMethod("bar").getArgument(0).getMethod("doSomething").getReturn().asSink()
  end
end
Foo.bar MyClass.new

When modeling an external library that is known to call a specific method on a parameter (in this case doSomething), this makes it possible to find the corresponding method definition in user code.

Strict left-to-right evaluation

Most member predicates on this class are intended to be chained, and are always evaluated from left to right, which means the caller should restrict the initial set of values.

For example, in the following snippet, we always find the uses of Foo before finding calls to bar:

API::getTopLevelMember("Foo").getMethod("bar")

In particular, the implementation will never look for calls to bar and work backward from there.

Beware of the footgun that is to use API graphs with an unrestricted receiver:

API::Node barCall(API::Node base) {
  result = base.getMethod("bar") // Do not do this!
}

The above predicate does not restrict the receiver, and will thus perform an interprocedural data flow search starting at every node in the graph, which is very expensive.