Qilin Pointer Analysis and Call Graphs

Qilin is a framework of context-sensitive points-to analyses. Like Spark, it builds the call graph on the fly together with the points-to sets. With context sensitivity, the call graph can be more precise than Spark's, see the comparison in the call graph tutorial. For the options that all call graph algorithms share, read the tutorial first.

Dependencies

MavenGradle

<dependency>
    <groupId>org.soot-oss</groupId>
    <artifactId>sootup.qilin</artifactId>
    <version>2.0.0</version>
</dependency>

compile "org.soot-oss:sootup.qilin:2.0.0"

How to create a pointer analysis

For the core context-sensitivity variants (insensitive, call-site, object, type, and their hybrid variants), use the type-safe PointerAnalysisFactory - no singletons, no string patterns, and independent Views (or repeated calls against the same View) can be analyzed concurrently since nothing is cached on View or held in JVM-global state:

Java

ClassType entrypoint = view.getIdentifierFactory().getClassType("dacapo.antlr.Main");
PointerAnalysisConfig config = PointerAnalysisConfig.builder()
    .contextSensitivity(ContextSensitivity.objectSensitive(2, 1)) // 2-object-sensitive, 1-level heap ctx
    .build();
PTA pta = PointerAnalysisFactory.create(view, entrypoint, config);
pta.run();

Other ContextSensitivity factory methods: insensitive(), callSite(k[, hk]), objectSensitive(k[, hk]), typeSensitive(k, hk), hybridObjectSensitive(k, hk), hybridTypeSensitive(k, hk).

The research-toolkit variants (bean, zipper, eagle, turner, mahjong, selectx, data-driven, tunneling, context debloating) go through the same PointerAnalysisFactory/ContextSensitivity pair - see the table below for their factory methods.

Resolving reflection, native methods, and invokedynamic

Some call targets can't be derived from a method's own bytecode. Qilin resolves these through a shared qilin.core.effect.MethodEffectModel hook, applied once per method just before its body is turned into constraints:

Reflection (Class.forName, Method.invoke, ...) - off by default; set PointerAnalysisConfig.builder().reflectionLogPath(path) to a Tamiflex trace log to resolve it.
Native methods - a fixed table of simulated JDK natives (Object.clone, Thread.start0, ...); unrecognized natives are left unmodeled.
invokedynamic (lambdas/method references) - on by default (PointerAnalysisConfig.isResolveDynamicInvoke()). Resolves the common case - a lambda body or method reference whose target is a plain static method - directly from the bootstrap's MethodHandle constant, no log needed. Captured (closure) lambdas, constructor references (Foo::new), and unbound instance method references are not yet resolved.

How to use pointer analysis results

First, we can use Qilin's pointer analysis to get a On-the-Fly constructed callgraph:

OnFlyCallGraph cg = pta.getCallGraph();

Second, we can use it to get the points-to results for some interested local variables, fields, etc.

PointsToSet pts0 = pta.reachingObjects(method, v0);
PointsToSet pts1 = pta.reachingObjects(method, v1, f); // PTS(v1.f)

Third, we can check whether two variables, a and b, are aliases by checking whether there is an object that exists in both of their points-to sets:

boolean mayAlias = pta.isMayAlias(method, a, b);

isMayAlias also special-cases null/String/class constants (e.g. two null constants always may-alias, a null never may-aliases a non-null value). It accepts Local references plus those constants; passing any other Value kind throws IllegalArgumentException.

A Full list of Pointer Analyses

Qilin's toolbox includes a rich set of pointer analyses, which are given below:

Note that k used below is a concrete small constant like 1 or 2, and hk the heap-context depth (defaults vary by variant - see ContextSensitivity's Javadoc for each factory method).

`ContextSensitivity` factory method	Description	Reference
`insensitive()`	Andersen's context-insensitive analysis	Paper
`callSite(k[, hk])`	k-callsite-sensitive pointer analysis (denoted kCFA).	Paper
`objectSensitive(k[, hk])`	k-object-sensitive pointer analysis (denoted kOBJ).	Paper
`typeSensitive(k, hk)`	k-type-sensitive pointer analysis (denoted kTYPE).	Paper
`hybridObjectSensitive(k, hk)`	hybrid k-object-sensitive pointer analysis.	Paper
`hybridTypeSensitive(k, hk)`	hybrid k-type-sensitive pointer analysis.	Paper
`beanObjectSensitive()`	BEAN-guided 2OBJ. Only k=2 is supported.	Paper
`dataDrivenObjectSensitive()`	Data-driven 2OBJ. Only k=2 is supported.	Paper
`dataDrivenCallSite()`	Data-driven 2CFA. Only k=2 is supported.	Paper
`dataDrivenHybridObjectSensitive()`	Data-driven hybrid-2OBJ. Only k=2 is supported.	Paper
`mahjongObjectSensitive(k, hk)`	MAHJONG-guided kOBJ.	Paper
`mahjongCallSite(k, hk)`	MAHJONG-guided kCFA.	Paper
`eagleObjectSensitive(k)`	EAGLE-guided kOBJ.	Paper
`turnerObjectSensitive(k)`	TURNER-guided kOBJ.	Paper
`zipperObjectSensitive(k, hk)`	ZIPPER-guided kOBJ.	Paper
`zipperCallSite(k, hk)`	ZIPPER-guided kCFA.	Paper
`tunnelingObjectSensitive/CallSite/TypeSensitive/HybridObjectSensitive(k, hk)`	Tunneling context sensitivity, per underlying variant.
`selectxCallSite(k)`	SELECTX-guided kCFA.	Paper

Context debloating is a config toggle layered on top of an object-sensitive variant (the default k-obj, or zipperObjectSensitive/mahjongObjectSensitive/eagleObjectSensitive), not a separate factory method: set PointerAnalysisConfig.builder().ctxDebloating(true) and pick a debloatApproach (CONCH, DEBLOATERX, COLLECTION for the Zipper-cd algorithm, or MOON). Debloating paper, DebloaterX paper.

Qilin call graphs

Building via `CallGraphConfig`

CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(mainMethod))
        .into(QilinCallGraphConfig::from)
        .mainClass(mainClass) // required: Qilin analyzes exactly one main class
        .pointerAnalysisConfig(config) // optional, default: PointerAnalysisConfig.builder()
        .build()
        .computeCallGraph();

Qilin analyzes exactly one main class, so mainClass(...) is required. Unless you set singleEntry(true), Qilin also models the JVM's start-up code. That model references JDK 8 internals, so with a JDK 9+ runtime in the view (e.g. DefaultRuntimeAnalysisInputLocation), set singleEntry(true).

Shared settings on CallGraphConfig.builder() take precedence over the matching PointerAnalysisConfig settings:

Shared option	`PointerAnalysisConfig` option it overrides
`seedEntryPointClinits` (default for Qilin: `false`)	`seedEntryPointClinits`
`virtualCallResolver`	`clinitVirtualCallResolver`. Qilin only consults it for `<clinit>` calls
`reflectionModel` (only if set)	`reflectionModel` / `reflectionLogPath`
`dynamicInvokeResolver` (only if set)	`dynamicInvokeResolver`
`callResolver`	not used by Qilin

CallGraph cg =
    CallGraphConfig.builder()
        .view(view)
        .entryPoints(List.of(mainMethod))
        // these overwrite the matching PointerAnalysisConfig settings:
        .seedEntryPointClinits(true)
        .virtualCallResolver(
            new SuppressClinitCallResolver(view)) // -> clinitVirtualCallResolver
        .dynamicInvokeResolver(DynamicInvokeResolver.none())
        .into(QilinCallGraphConfig::from)
        .mainClass(mainClass)
        .pointerAnalysisConfig(
            PointerAnalysisConfig.builder()
                .contextSensitivity(ContextSensitivity.callSite(1))
                .singleEntry(true)
                .evaluate(false))
        .build()
        .computeCallGraph();

Running the analysis directly

You get the same call graph from the PTA object, together with all points-to queries shown above:

PointerAnalysisConfig config =
    PointerAnalysisConfig.builder()
        .contextSensitivity(ContextSensitivity.callSite(1))
        .singleEntry(true)
        .evaluate(false)
        .build();
PTA pta = PointerAnalysisFactory.create(view, mainClass, config);
pta.run();
OnFlyCallGraph cg = pta.getCallGraph(); // implements sootup.callgraph.CallGraph

Every `PointerAnalysisConfig` option

PointerAnalysisConfig.Builder config =
    PointerAnalysisConfig.builder()
        // what to analyze and how precisely
        .contextSensitivity(ContextSensitivity.objectSensitive(2, 1)) // default: insensitive()
        .heapAbstractionPolicy(PointerAnalysisConfig.HeapAbstractionPolicy.ALLOC_SITE)
        .singleEntry(true) // default false: also model JVM start-up (needs a JDK 8 rt)
        .preciseArrayElement(false)
        .stringConstants(false) // true: one object per string constant
        .preciseExceptions(false)
        .enforceEmptyContextForIgnoreTypes(false)
        // <clinit> modelling, see the call graph tutorial
        .seedEntryPointClinits(false)
        .clinitVirtualCallResolver(VirtualCallResolver.all())
        // reflection and invokedynamic
        .reflectionLogPath(null) // path to a TamiFlex refl.log
        .reflectionModel(null) // or any sootup.callgraph.reflection.ReflectionModel
        .resolveDynamicInvoke(true)
        .dynamicInvokeResolver(DynamicInvokeResolver.bootstrapMethodHandles())
        // guided / debloated analyses
        .preAnalysisOnly(false) // only run the pre-analysis of a guided analysis
        .ctxDebloating(false)
        .debloatApproach(PointerAnalysisConfig.DebloatApproach.CONCH)
        .turnerConfig(PointerAnalysisConfig.TurnerConfig.DEFAULT)
        // output
        .analysisName(null) // name used for the output directory
        .outputDirectory("")
        .dumpJimple(false) // currently has no effect
        .dumpPointsToSet(false)
        .dumpLibraryPointsToSet(false)
        .dumpStats(false)
        .evaluate(false); // default true: compute and print statistics afterwards

Option	Default	Effect
`contextSensitivity`	`insensitive()`	The analysis variant, see the full list
`heapAbstractionPolicy`	`ALLOC_SITE`	`ALLOC_SITE`: one abstract object per `new` statement. `HEURISTIC_MERGE`: one object per type for `StringBuffer`, `StringBuilder` and all `Throwable`s
`singleEntry`	`false`	`true`: only the main method is an entry point. `false`: also model the JVM start-up (needs a JDK 8 runtime)
`seedEntryPointClinits`	`false`	Add the main class's `<clinit>` (and its superclasses') as roots. See static initializers
`clinitVirtualCallResolver`	`VirtualCallResolver.all()`	Decides which discovered `<clinit>` calls are modeled
`preciseArrayElement`	`false`	Give array-element nodes the array's element type instead of `Object`, so type filtering applies
`stringConstants`	`false`	`true`: one abstract object per string constant. `false`: one object for all string constants
`preciseExceptions`	`false`	Track thrown exceptions per method. `false`: all exceptions flow through one global node
`enforceEmptyContextForIgnoreTypes`	`false`	Analyze the methods of certain types (e.g. `StringBuilder`) without context
`reflectionLogPath`	`null`	A TamiFlex `refl.log` to resolve reflection with
`reflectionModel`	`null`	Any `ReflectionModel`. Takes precedence over `reflectionLogPath`
`resolveDynamicInvoke`	`true`	Resolve `invokedynamic` (lambdas, method references)
`dynamicInvokeResolver`	`bootstrapMethodHandles()`	How `invokedynamic` is resolved. See invokedynamic
`preAnalysisOnly`	`false`	Guided and debloated analyses: only run the pre-analysis
`ctxDebloating`	`false`	Context debloating on top of an object-sensitive variant
`debloatApproach`	`CONCH`	`CONCH`, `DEBLOATERX`, `COLLECTION` (Zipper-cd) or `MOON`
`turnerConfig`	`DEFAULT`	For `turnerObjectSensitive`: `DEFAULT`, or only `PHASE_ONE` / `PHASE_TWO` of Turner's pre-analysis
`analysisName`	`null`	Name used for the statistics and output files
`outputDirectory`	`""`	Where the dumps and statistics are written
`dumpJimple`	`false`	Accepted, but currently has no effect
`dumpPointsToSet`	`false`	Write the points-to sets of the application's locals
`dumpLibraryPointsToSet`	`false`	Also write the points-to sets of library locals
`dumpStats`	`false`	Write the statistics. Implies `evaluate`
`evaluate`	`true`	Compute and print statistics after the analysis. Turn it off when you only need the results: the alias statistics are quadratic in the number of locals

Two examples, merged heap objects and context debloating:

Heap abstractionContext debloating

PointerAnalysisConfig.Builder config =
    PointerAnalysisConfig.builder()
        .contextSensitivity(ContextSensitivity.insensitive())
        // one object per type for StringBuffer, StringBuilder and Throwables
        .heapAbstractionPolicy(PointerAnalysisConfig.HeapAbstractionPolicy.HEURISTIC_MERGE)
        .singleEntry(true)
        .evaluate(false);

PointerAnalysisConfig.Builder config =
    PointerAnalysisConfig.builder()
        .contextSensitivity(ContextSensitivity.objectSensitive(2, 1))
        .ctxDebloating(true) // only on object-sensitive variants
        .debloatApproach(PointerAnalysisConfig.DebloatApproach.DEBLOATERX)
        .singleEntry(true)
        .evaluate(false);

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