Skip to content

Call Graph Construction

A call graph shows the method calling relationship of a program. It is a directed graph, whose nodes represent different methods, and edges represent caller -> callee relationship.

SootUp contains several call graph construction algorithms. Below, we show how you can use each of these.

Creating the Type Hierarchy

All the call graph construction algorithms require the view to access the type hierarchy for resolving method calls based of sub typing relationship. Below, we show how to create a type hierarchy:

1
2
3
4
5
6
String cpString = "src/test/resources/Callgraph/binary";
List<AnalysisInputLocation> inputLocations = new ArrayList();
inputLocations.add(new JavaClassPathAnalysisInputLocation(cpStr));
inputLocations.add(new DefaultRuntimeAnalysisInputLocation());

JavaView view = new JavaView(inputLocations);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
String userdir = System.getProperty("user.dir");
String sootCp = userdir + File.separator + "target" + File.separator + "test-classes"+ File.pathSeparator + "lib"+File.separator+"rt.jar";
String targetTestClassName = target.exercise1.Hierarchy.class.getName();
G.reset();
Options.v().set_whole_program(true);
Options.v().set_soot_classpath(sootCp);
Options.v().set_no_bodies_for_excluded(true);
Options.v().process_dir();
Options.v().set_allow_phantom_refs(true);
Options.v().setPhaseOption("jb", "use-original-names:true");
Options.v().set_prepend_classpath(false);
SootClass c = Scene.v().forceResolve(targetTestClassName, SootClass.BODIES);
if (c != null)
    c.setApplicationClass();
Scene.v().loadNecessaryClasses();

Hierarchy hierarchy = new Hierarchy();

Defining an Entry Method

All call graph construction algorithms require an entry method to start with. In java application, you usually define the main method. However, it is possible to define arbitrary entry methods depending on your needs. Below, we show how to define such an entry method:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
JavaClassType classTypeA = view.getIdentifierFactory().getClassType("packageNameA.A");

MethodSignature entryMethodSignature =
    view.getIdentifierFactory()
        .getMethodSignature(
            classTypeA,
            "calc",
            VoidType.getInstance(),
            Collections.singletonList(classTypeA)
        );

1
2
3
String methodSigStr = "<packageNameA.A: void calc(packageNameA.A)";
MethodSignature entryMethodSignature = view
                    .getIdentifierFactory().parseMethodSignature(methodSigStr));

1
2
String targetTestClassName = "packageNameA.A";
SootMethod src = Scene.v().getSootClass(targetTestClassName).getMethodByName("doStuff");

Class Hierarchy Analysis

Class Hierarchy Analysis (CHA) algorithm is the most sound call graph construction algorithm available in SootUp. It soundly includes all implementers of an interface, when resolving a method call on an interface. You can construct a call graph with CHA as follows:

1
2
3
4
5
6
CallGraphAlgorithm cha = new ClassHierarchyAnalysisAlgorithm(view);

CallGraph cg = cha.initialize(Collections.singletonList(entryMethodSignature));

cg.callsFrom(entryMethodSignature).stream()
    .forEach(tgt -> System.out.println(entryMethodSignature + " may call " + tgt);

1
2
3
4
5
6
7
8
CHATransformer.v().transform();
SootMethod src = Scene.v().getSootClass(targetTestClassName).getMethodByName("doStuff");
CallGraph cg = Scene.v().getCallGraph();
Iterator<MethodOrMethodContext> targets = new Targets(cg.edgesOutOf(src));
while (targets.hasNext()) {
    SootMethod tgt = (SootMethod)targets.next();
    System.out.println(src + " may call " + tgt);
}

Rapid Type Analysis

Rapid Type Analysis (RTA) algorithm constructs a rather precise version of the call graph that the CHA constructs. It refines CHA by considering only the instantiated implementers of an interface, when resolving a method call on an interface. You can construct a call graph with RTA as follows:

1
2
3
4
5
6
CallGraphAlgorithm rta = new RapidTypeAnalysisAlgorithm(view);

CallGraph cg = rta.initialize(Collections.singletonList(entryMethodSignature));

cg.callsFrom(entryMethodSignature).stream()
    .forEach(tgt -> System.out.println(entryMethodSignature + " may call " + tgt);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
Transform sparkConfig = new Transform("cg.spark", null);
PhaseOptions.v().setPhaseOption(sparkConfig, "enabled:true");
PhaseOptions.v().setPhaseOption(sparkConfig, "rta:true");
PhaseOptions.v().setPhaseOption(sparkConfig, "on-fly-cg:false");
Map phaseOptions = PhaseOptions.v().getPhaseOptions(sparkConfig);
SparkTransformer.v().transform(sparkConfig.getPhaseName(), phaseOptions);
SootMethod src = Scene.v().getSootClass(targetTestClassName).getMethodByName("doStuff");
CallGraph cg = Scene.v().getCallGraph();
Iterator<MethodOrMethodContext> targets = new Targets(cg.edgesOutOf(src));
while (targets.hasNext()) {
    SootMethod tgt = (SootMethod)targets.next();
    System.out.println(src + " may call " + tgt);
}

Qilin Pointer Analysis

Qilin builds a call graph on the fly with the pointer analysis. You can construct a call graph with Qilin as follows:

==="SootUp"

1
2
3
4
5
String MAINCLASS = "dacapo.antlr.Main"; // just an example
PTAPattern ptaPattern = new PTAPattern("insens"); // "2o"=>2OBJ, "1c"=>1CFA, etc.
PTA pta = PTAFactory.createPTA(ptaPattern, view, MAINCLASS);
pta.run();
CallGraph cg = pta.getCallGraph();