Skip to content

Call Graphs: a Step-by-Step Tutorial

A call graph records which methods a program may call. Its nodes are methods. Each edge is one call: a caller, a callee, and the invoke statement in the caller that makes the call (CallGraph.Call). Most interprocedural analyses need a call graph, e.g. the taint analysis and the typestate analysis.

The hard part is the virtual call. For shape.area() the compiler only knows the static type Shape, so a call graph algorithm has to estimate which area() implementations can run there. Algorithms differ in how precise that estimate is and how much it costs. This tutorial uses one small program to show the difference, then walks through every configuration option.

All code on this page comes from tests in sootup.examples/src/test/java/sootup/examples/callgraph/. It compiles, and it does what the comments say.

Dependencies

CHA and RTA are in sootup.callgraph. Spark needs sootup.spark, and Qilin needs sootup.qilin. See Installation.

Step 1: Load the program into a View

Every algorithm works on a View. Add the program under analysis as an application input location, and the Java runtime as a library input location:

1
2
3
4
5
6
7
8
List<AnalysisInputLocation> inputLocations =
    List.of(
        // the program under analysis: SourceType.Application
        new JavaClassPathAnalysisInputLocation(
            "src/test/resources/CallgraphComparison/binary", SourceType.Application),
        // the JDK of the running JVM: SourceType.Library
        new DefaultRuntimeAnalysisInputLocation());
JavaView view = new JavaView(inputLocations);

The runtime is needed because every program calls into the JDK, even if only Object.<init>(). Without it, those targets can't be resolved. By default, the algorithms record calls into library methods but don't analyze library method bodies. callResolver changes that.

Step 2: Choose the entry points

A call graph starts at one or more entry methods and contains everything reachable from them. For an application, the entry point is usually main:

1
2
3
4
ClassType mainClass = view.getIdentifierFactory().getClassType("Main");
MethodSignature mainMethod =
    view.getIdentifierFactory()
        .getMethodSignature(mainClass, view.getIdentifierFactory().getMainSubSignature());

You can also parse the signature from a string:

1
2
MethodSignature mainMethod =
    view.getIdentifierFactory().parseMethodSignature("<Main: void main(java.lang.String[])>");

Any method can be an entry point, e.g. every public method of a library, or the handler methods of a framework. If you pass no entry points, CHA and RTA start from every main(String[]) method of the application.

Step 3: Pick an algorithm

The running example

1
2
3
public interface Shape {
  double area();
}

Circle, Square, Triangle and Hexagon implement Shape. Each area() returns a constant.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public class Main {

  static Shape id(Shape s) {
    return s;
  }

  public static void main(String[] args) {
    Shape circle = new Circle();
    circle.area(); // call site 1

    Shape triangle = id(new Triangle()); // the result is never used
    Shape square = id(new Square());
    square.area(); // call site 2
  }
}

At run time, call site 1 (line 9) calls Circle.area() and call site 2 (line 13) calls Square.area(). Nothing else is ever called. This is what each algorithm computes:

Algorithm Call site 1 circle.area() Call site 2 square.area() Reasoning
CHA Circle, Square, Triangle, Hexagon Circle, Square, Triangle, Hexagon Every class that implements Shape
RTA Circle, Square, Triangle Circle, Square, Triangle Only classes that the program instantiates with new somewhere. Hexagon is gone
Spark, Qilin insensitive() Circle Square, Triangle Only objects that can actually flow into the variable. Both new Triangle() and new Square() pass through id(), which is analyzed once, so its return value may be either
Qilin callSite(1) Circle Square id() is analyzed separately for each call site, so id(new Square()) returns only a Square. Exact

From top to bottom, the algorithms get more expensive and more precise. Every algorithm over-approximates: it may report calls that never happen, but it doesn't miss calls the program makes (within the limits of static analysis). Every extra edge makes the analyses built on top of the call graph slower and less precise. For example, a taint analysis on the CHA graph would also track flows through Hexagon.area().

CallGraphComparisonTest asserts exactly this table.

More context is not automatically more precision

Which kind of context helps depends on the code. id() is static, so it has no receiver object. An object-sensitive analysis (ContextSensitivity.objectSensitive(2, 1)) therefore has no context to tell the two id(...) calls apart, and reports Square and Triangle at call site 2, just like the context-insensitive analysis. A call-site-sensitive analysis distinguishes the two calls by their call sites. For code that routes objects through instance methods (getters, containers, builders), object sensitivity is usually the better choice.

Which one should I use?

  • CHA: start here. Fast and simple, and it needs no knowledge about objects. Also the base graph for Spark.
  • RTA: almost as fast as CHA, and usually noticeably smaller. A good default for whole-program analyses.
  • Spark: context-insensitive points-to analysis. Use it when you also need points-to sets, or when RTA is too imprecise.
  • Qilin: the full range of context-sensitive points-to analyses. Use it when precision matters more than run time.

Each family has its own page with all of its options:

Step 4: Build the call graph

CallGraphConfig.builder() gives every algorithm the same shape. Set the shared properties, choose the family, set the family's own options (if any), then call build() and computeCallGraph():

1
2
3
4
5
6
7
CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(mainMethod))
        .cha()
        .build()
        .computeCallGraph();

1
2
3
4
5
6
7
CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(mainMethod))
        .rta()
        .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.builder().onFlyCallGraph(true).build())
        .build()
        .computeCallGraph();

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(mainMethod))
        .into(QilinCallGraphConfig::from)
        .mainClass(mainClass)
        .pointerAnalysisConfig(
            PointerAnalysisConfig.builder()
                .contextSensitivity(ContextSensitivity.insensitive())
                .singleEntry(true) // only main(), no JVM start-up model
                .evaluate(false)) // skip the statistics printout
        .build()
        .computeCallGraph();

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(mainMethod))
        .into(QilinCallGraphConfig::from)
        .mainClass(mainClass)
        .pointerAnalysisConfig(
            PointerAnalysisConfig.builder()
                .contextSensitivity(ContextSensitivity.callSite(1)) // 1-call-site-sensitive
                .singleEntry(true)
                .evaluate(false))
        .build()
        .computeCallGraph();

.cha() and .rta() are built in. Spark and Qilin are in their own modules, so you enter them with .into(SparkCallGraphConfig::from) and .into(QilinCallGraphConfig::from).

You can also create the algorithm objects yourself, see SootUp CHA & RTA.

Step 5: Shared options

These options go on CallGraphConfig.builder() before you choose the family. The examples use CHA. The other families support the same options, with the exceptions listed in Which family uses which option.

callResolver: which methods get analyzed

A CallResolver is asked once for every method the algorithm reaches, before the method's body is loaded. It returns a CallFilter that decides which calls in the method get resolved:

  • CallFilter.all(): every call.
  • CallFilter.none(): no call. The body is not even loaded. The method stays in the call graph as a node, but has no outgoing edges.
  • CallFilter.of(stmt -> ...): only the calls in statements the predicate accepts.

The default is DefaultCallResolver. It returns none() for library methods, so the JDK is not analyzed:

1
2
3
4
5
6
7
8
CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(mainMethod))
        .callResolver(new DefaultCallResolver(view)) // the default: don't look into the JDK
        .cha()
        .build()
        .computeCallGraph();

To analyze library methods too (this can make the graph, and the run time, much bigger):

1
2
3
4
5
6
7
8
CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(mainMethod))
        .callResolver(CallResolver.all()) // also expand library (JDK) methods
        .cha()
        .build()
        .computeCallGraph();

To find out which methods were reached but not analyzed, e.g. when you're looking for an expected method that is missing:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
ExcludedCallsCollectingCallResolver resolver = new ExcludedCallsCollectingCallResolver(view);
CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(mainMethod))
        .callResolver(resolver)
        .cha()
        .build()
        .computeCallGraph();

// which methods were reached but not expanded? -> <java.lang.Object: void <init>()>
Set<MethodSignature> notExpanded = resolver.getVisitedExcludedMethods();

Your own resolver can cut off a class or package, and fall back to the default for everything else:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
CallResolver libraryDefault = new DefaultCallResolver(view);
CallResolver skipCircle =
    caller ->
        caller.getDeclaringClassType().getClassName().equals("Circle")
            ? CallFilter.none() // Circle's methods: body is not even loaded
            : libraryDefault.tryAdvanceMethod(caller); // everything else: default behaviour

CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(mainMethod))
        .callResolver(skipCircle)
        .cha()
        .build()
        .computeCallGraph();

Or decide per statement:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// resolve only those calls whose target is not declared in java.*
CallResolver noJdkCalls =
    caller ->
        CallFilter.of(
            stmt ->
                stmt.getInvokeExpr()
                    .map(
                        invoke ->
                            !invoke
                                .getMethodSignature()
                                .getDeclClassType()
                                .getPackageName()
                                .getName()
                                .startsWith("java."))
                    .orElse(true));

CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(mainMethod))
        .callResolver(noJdkCalls)
        .cha()
        .build()
        .computeCallGraph();

Excluding a method only removes its outgoing edges

A CallResolver only decides whether a method's own calls get resolved. Calls into the method from other methods stay in the call graph.

virtualCallResolver: which resolved targets to keep

A VirtualCallResolver is asked after a call has been resolved, once per possible target. That includes the static initializers (<clinit>) that the call triggers. It returns an ExplorationVerdict:

Verdict Edge added? Callee analyzed?
EXPLORE_METHOD (default) yes yes
STOP_AFTER_CALL yes not via this edge
STOP no no 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
VirtualCallResolver resolver =
    (caller, callee, stmt) -> {
      String targetClass = callee.getDeclClassType().getClassName();
      if (targetClass.equals("Hexagon")) {
        return ExplorationVerdict.STOP; // no edge at all
      }
      if (targetClass.equals("Triangle")) {
        return ExplorationVerdict.STOP_AFTER_CALL; // edge, but callee is not expanded
      }
      return ExplorationVerdict.EXPLORE_METHOD; // edge, callee is expanded (default)
    };

CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(mainMethod))
        .virtualCallResolver(resolver)
        .cha()
        .build()
        .computeCallGraph();

The default is VirtualCallResolver.all(). SuppressClinitCallResolver and AppOnlyClinitCallResolver handle static initializers, see the next section. Both take an optional second resolver, which decides about all other targets:

1
2
3
4
5
6
7
VirtualCallResolver noHelper =
    (caller, callee, stmt) ->
        callee.getDeclClassType().getClassName().equals("Helper")
            ? ExplorationVerdict.STOP
            : ExplorationVerdict.EXPLORE_METHOD;
// first drop JDK <clinit>s, then ask noHelper about everything else
VirtualCallResolver resolver = new AppOnlyClinitCallResolver(view, noHelper);

seedEntryPointClinits: static initializers

The JVM runs a class's static initializer (<clinit>) before the class is first used. The second example program has two of them:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public class App {

  static final Object LOCK = new Object(); // static field initializer: App.<clinit>

  public static void main(String[] args) throws Exception {
    Registry.register(); // runs Registry.<clinit> first

    Runnable task = () -> Helper.work(); // invokedynamic: lambda
    task.run();

    Plugin plugin = (Plugin) Class.forName("MyPlugin").newInstance(); // reflection
    plugin.start();
  }
}

1
2
3
4
5
6
7
8
9
public class Registry {
  static {
    init(); // static initializer: Registry.<clinit>
  }

  static void init() {}

  static void register() {}
}

Registry.register() triggers Registry.<clinit>, and the algorithm finds this call while it walks through main. App.<clinit> is different: the JVM runs it before main, so no statement in the program calls it. seedEntryPointClinits(true) adds the <clinit> of each entry point's class as an extra root.

Together, the seed flag and the virtualCallResolver reproduce the four classic <clinit> modes of Soot and Qilin:

Mode seedEntryPointClinits virtualCallResolver App.<clinit> Registry.<clinit> JDK <clinit>s (e.g. Class.<clinit>)
FULL true new SuppressClinitCallResolver(view) yes – –
ON_THE_FLY false VirtualCallResolver.all() – yes yes
APP false new AppOnlyClinitCallResolver(view) – yes –
NONE false new SuppressClinitCallResolver(view) – – –

CHA, RTA and Spark default to true + all(), so they include all of them. Qilin defaults to ON_THE_FLY.

1
2
3
4
5
6
7
CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(appMain))
        .cha() // = seedEntryPointClinits(true) + VirtualCallResolver.all()
        .build()
        .computeCallGraph();

1
2
3
4
5
6
7
8
CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(appMain))
        .seedEntryPointClinits(false) // App.<clinit> is no longer a root
        .cha()
        .build()
        .computeCallGraph();

1
2
3
4
5
6
7
8
9
CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(appMain))
        .seedEntryPointClinits(true)
        .virtualCallResolver(new SuppressClinitCallResolver(view)) // drop discovered <clinit>s
        .cha()
        .build()
        .computeCallGraph();

1
2
3
4
5
6
7
8
9
CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(appMain))
        .seedEntryPointClinits(false)
        .virtualCallResolver(new AppOnlyClinitCallResolver(view)) // drop JDK <clinit>s only
        .cha()
        .build()
        .computeCallGraph();

reflectionModel: reflection

In general, static analysis can't know which class Class.forName("MyPlugin") loads. With the default, ReflectionModel.none(), reflective calls are treated as ordinary library calls, so in the example above MyPlugin.<init>() is never reached:

1
2
3
4
5
6
7
8
CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(appMain))
        .reflectionModel(ReflectionModel.none()) // the default
        .cha()
        .build()
        .computeCallGraph();

TamiFlex records the reflective calls of a real run in a log. TamiflexReflectionModel rewrites each logged call into plain Jimple (here: new MyPlugin and the constructor call) before the call graph algorithm sees the body:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// refl.log, recorded by running App with the TamiFlex Play-Out agent:
//   Class.forName;MyPlugin;App.main;11;;
//   Class.newInstance;MyPlugin;App.main;11;;
ReflectionModel tamiflex =
    new TamiflexReflectionModel(view, Path.of("src/test/resources/CallgraphFeatures/refl.log"));

CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(appMain))
        .reflectionModel(tamiflex)
        .cha()
        .build()
        .computeCallGraph();

ReflectionModel is a functional interface, so you can wrap a model or write your own. A model must return the same body every time it is asked about the same method: CHA, RTA, Spark and Qilin may ask more than once. To model more reflective APIs, extend AbstractReflectionModel. It finds the reflective calls, caches the rewritten bodies, and calls one hook per API (transformClassForName, transformMethodInvoke, ...).

1
2
3
4
5
6
7
8
9
// a ReflectionModel maps (method, body) to a body in which reflective calls are preceded by
// plain Jimple; here: apply the TamiFlex model to application methods only
ReflectionModel appOnly =
    (method, body) ->
        view.getClass(method.getDeclaringClassType())
                .map(SootClass::isApplicationClass)
                .orElse(false)
            ? tamiflex.resolve(method, body)
            : body;

dynamicInvokeResolver: lambdas and method references

Lambdas and method references compile to invokedynamic. The default resolver, DynamicInvokeResolver.bootstrapMethodHandles(), reads the target method from the bootstrap arguments. A lambda body (lambda$main$0) is reached through the functional object: in the example, task.run() calls it.

1
2
3
4
5
6
7
8
CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(appMain))
        .dynamicInvokeResolver(DynamicInvokeResolver.bootstrapMethodHandles()) // the default
        .cha()
        .build()
        .computeCallGraph();

1
2
3
4
5
6
7
8
CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(appMain))
        .dynamicInvokeResolver(DynamicInvokeResolver.none()) // lambdas are never called
        .cha()
        .build()
        .computeCallGraph();

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(appMain))
        // additionally: invokedynamic stmt -> lambda body, for code that never calls the lambda
        .dynamicInvokeResolver(
            DynamicInvokeResolver.bootstrapMethodHandles().withCreationSiteEdges())
        .cha()
        .build()
        .computeCallGraph();

withCreationSiteEdges() also adds an edge from the invokedynamic statement to the lambda body. This helps when the view doesn't contain the code that calls the lambda, e.g. a lambda that is passed to a library you don't analyze.

Which family uses which option

Option CHA RTA Spark (CHA-seeded) Spark (on-the-fly) Qilin
callResolver ✓ ✓ ✓ (through CHA) – –
virtualCallResolver ✓ ✓ ✓ (through CHA) – <clinit> calls only
seedEntryPointClinits ✓ (default true) ✓ (default true) ✓ (through CHA) – ✓ (default false)
reflectionModel ✓ ✓ ✓ ✓ ✓ (overrides reflectionLogPath)
dynamicInvokeResolver ✓ ✓ ✓ ✓ ✓

Step 6: Query the call graph

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
List<MethodSignature> roots = cg.getEntryMethods(); // [<Main: void main(java.lang.String[])>]
Set<MethodSignature> nodes = cg.getMethodSignatures(); // every reachable method
int edges = cg.callCount();

Set<MethodSignature> callees = cg.callTargetsFrom(mainMethod); // methods main may call
Set<MethodSignature> callers = cg.callSourcesTo(squareArea); // methods that may call it

Set<CallGraph.Call> out = cg.callsFrom(mainMethod); // edges incl. the calling stmt
Set<CallGraph.Call> outInOrder = cg.sortedCallsFrom(mainMethod); // in stmt order
Set<CallGraph.Call> in = cg.callsTo(squareArea);
for (CallGraph.Call call : in) {
  System.out.println(
      call.sourceMethodSignature()
          + " line "
          + call.getLineNumber()
          + ": "
          + call.invokableStmt()
          + " -> "
          + call.targetMethodSignature());
}

boolean reachable = cg.containsMethod(squareArea);
boolean edge = cg.containsCall(mainMethod, squareArea, in.iterator().next().invokableStmt());

MutableCallGraph copy = cg.copy(); // independent copy you may modify

The area() targets per call site in Step 3 come from this helper:

1
2
3
4
5
6
7
8
Set<String> areaTargets(CallGraph cg, int line) {
  return cg.callsFrom(mainMethod).stream()
      .filter(call -> call.getLineNumber() == line)
      .map(CallGraph.Call::targetMethodSignature)
      .filter(target -> target.getName().equals("area"))
      .map(target -> target.getDeclClassType().getClassName())
      .collect(Collectors.toCollection(TreeSet::new));
}

To compare two call graphs, use diff:

1
2
3
CallGraphDifference difference = chaGraph.diff(rtaGraph);
// methods only CHA considers reachable
List<MethodSignature> onlyInCha = difference.uniqueBaseGraphMethods();

CallGraphDifference also has uniqueOtherGraphMethods(), intersectedMethods(), and the corresponding methods for calls.

Step 7: Export to DOT

exportAsDot() writes the graph in Graphviz format. The nodes are method signatures, and the edge labels are the line numbers of the calls:

1
String dot = cg.exportAsDot().collect(Collectors.joining("\n"));

1
2
3
4
5
6
7
String sortedDot =
    cg.exportAsDot(
            Comparator.comparing(
                    (CallGraph.Call call) -> call.sourceMethodSignature().toString())
                .thenComparing(call -> call.targetMethodSignature().toString())
                .thenComparing(CallGraph.Call::getLineNumber))
        .collect(Collectors.joining("\n"));

Render it with dot -Tsvg callgraph.dot -o callgraph.svg.

Limits: reflection, invokedynamic and static initializers

A call graph is only as complete as its model of the program. Calls that don't appear in the bytecode need extra help:

Coming from Soot

Soot SootUp
CHATransformer.v().transform() CallGraphConfig.builder()...cha()
cg.spark with rta:true CallGraphConfig.builder()...rta()
cg.spark with on-fly-cg:true .into(SparkCallGraphConfig::from) with onFlyCallGraph(true)
Scene.v().getCallGraph() the returned CallGraph. There is no global state
cg.edgesOutOf(m) cg.callsFrom(signature)
set_whole_program(true), loadNecessaryClasses() not needed: the View loads classes on demand

See also Migration Help.