Skip to content

Spark Call Graphs

Spark is a context-insensitive, field-sensitive, Andersen-style points-to analysis. It builds a pointer assignment graph (PAG) from the reachable methods and propagates allocation sites through it. Spark can be used in two ways:

  • On the fly: the call graph grows together with the points-to sets. A virtual call is only resolved to the run-time types of the objects its receiver may point to. This gives the precise call graph from the tutorial's comparison.
  • CHA-seeded (the default): Spark computes points-to sets on a CHA call graph that is built up front. The call graph you get back is that CHA graph. Use this mode when you only need points-to sets.

Start with the call graph tutorial for the shared options. For context-sensitive analyses, see Qilin.

Dependencies

1
2
3
4
5
<dependency>
    <groupId>org.soot-oss</groupId>
    <artifactId>sootup.spark</artifactId>
    <version>2.0.0</version>
</dependency>

1
compile "org.soot-oss:sootup.spark:2.0.0"

Building via CallGraphConfig

1
2
3
4
5
6
7
8
CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(mainMethod))
        .into(SparkCallGraphConfig::from)
        .sparkOptions(SparkOptions.builder().onFlyCallGraph(true).build())
        .build()
        .computeCallGraph();

1
2
3
4
5
6
7
8
CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(mainMethod))
        .into(SparkCallGraphConfig::from)
        .sparkOptions(SparkOptions.defaultOptions()) // onFlyCallGraph = false
        .build()
        .computeCallGraph(); // = the CHA graph Spark was seeded with

With CHA seeding, the shared callResolver, virtualCallResolver and seedEntryPointClinits settings configure the CHA graph. In on-the-fly mode they are not used, and Spark currently doesn't model <clinit> calls at all. reflectionModel and dynamicInvokeResolver apply in both modes.

SparkOptions

Every option, with its default:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
SparkOptions options =
    SparkOptions.builder()
        .onFlyCallGraph(true) // grow the call graph with the points-to sets (default: false)
        .ignoreBaseObjects(false) // true: field-based instead of field-sensitive
        .typesForSites(false) // true: one abstract object per type, not per `new`
        .simpleEdgesBidirectional(false) // true: unification-based (Steensgaard-like)
        // accepted, but not implemented yet:
        .parmsAsFields(false)
        .returnsAsFields(false)
        .mergeStringBuffer(true)
        .simulateNatives(true)
        .build();
Option Default Effect
onFlyCallGraph false Build the call graph together with the points-to sets instead of using CHA. Much more precise call graph
ignoreBaseObjects false Field-based analysis: a.f and b.f are the same node, no matter what a and b point to. Cheaper, less precise
typesForSites false One abstract object per type instead of per new statement. Smaller points-to sets, less precise
simpleEdgesBidirectional false Make assignment edges bidirectional, which turns the analysis into a unification-based (Steensgaard-style) one. Cheaper, much less precise
parmsAsFields false Not implemented yet, no effect. In Soot: model parameters as field-reference nodes
returnsAsFields false Not implemented yet, no effect. In Soot: model return values as field-reference nodes
mergeStringBuffer true Not implemented yet, no effect. In Soot: one abstract object for all StringBuffer/StringBuilder allocations
simulateNatives true Not implemented yet, no effect. In Soot: model the effects of JDK native methods. Qilin does model them

For example, with one abstract object per type:

1
2
3
4
5
6
7
8
CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(mainMethod))
        .into(SparkCallGraphConfig::from)
        .sparkOptions(SparkOptions.builder().onFlyCallGraph(true).typesForSites(true).build())
        .build()
        .computeCallGraph();

In the running example, this makes no difference, since every class is instantiated only once.

The Spark facade: points-to sets

To get the points-to analysis as well as the call graph, use Spark.builder():

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
Spark spark =
    Spark.builder()
        .view(view)
        .entryPoints(List.of(mainMethod))
        .sparkOptions(SparkOptions.builder().onFlyCallGraph(true).build())
        .reflectionModel(ReflectionModel.none()) // default
        .dynamicInvokeResolver(DynamicInvokeResolver.bootstrapMethodHandles()) // default
        .build();
CallGraph cg = spark.getCallGraph(); // solves on first access
PointsToAnalysis pta = spark.getPointsToAnalysis();

PointsToAnalysis answers queries for a Value in a method:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
// the receiver of `square.area()` in main
Local square =
    view.getMethod(mainMethod).get().getBody().getStmts().stream()
        .filter(stmt -> stmt instanceof InvokableStmt)
        .filter(stmt -> stmt.getPositionInfo().getStmtPosition().getFirstLine() == 13)
        .map(stmt -> ((InvokableStmt) stmt).getInvokeExpr().get())
        .map(invoke -> ((AbstractInstanceInvokeExpr) invoke).getBase())
        .findFirst()
        .get();

Set<Type> types = pta.reachingTypes(square, mainMethod); // {Square, Triangle}
Query Result
reachingObjects(value, method) the allocation sites (AllocationNodes) value may point to
reachingTypes(value, method) the run-time types of those objects
aliases(value, method) the PAG nodes that may point to a common object
getPointsToMap() the raw PAG node → allocation sites map, for debugging

spark.getPag() gives access to the pointer assignment graph itself. PAGVisualizer can render it.

Using your own call graph

In the default mode, you can pass a call graph you have already built, e.g. a CHA graph with your own <clinit> or scoping settings:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
ReflectionModel reflection = ReflectionModel.none();
DynamicInvokeResolver indy = DynamicInvokeResolver.bootstrapMethodHandles();
// e.g. a CHA graph with custom <clinit>/scoping settings
CallGraph cha =
    new ClassHierarchyAnalysisAlgorithm(
            view,
            new DefaultCallResolver(view),
            VirtualCallResolver.all(),
            true, // seedEntryPointClinits
            reflection,
            indy)
        .initialize(List.of(mainMethod));

Spark spark =
    Spark.builder()
        .view(view)
        .callGraph(cha) // used as-is; ignored when onFlyCallGraph is true
        .reflectionModel(reflection) // use the same instances the graph was built with
        .dynamicInvokeResolver(indy)
        .build();
PointsToAnalysis pta = spark.getPointsToAnalysis();

Use the same reflection model and invokedynamic resolver

Build the call graph with the same ReflectionModel and DynamicInvokeResolver instances that you give to Spark. Otherwise the reflective and invokedynamic edges in the graph won't match the PAG. callGraph(...) is ignored (with a warning) when onFlyCallGraph is true.

Next: Qilin · CHA & RTA · back to the tutorial