Incorporate Qilin Pointer Analysis

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, or COLLECTION for the Zipper-cd algorithm). Debloating paper, DebloaterX paper.

Qilin Pointer Analysis

Qilin builds a call graph on the fly with the pointer analysis, for both core and toolkit context-sensitivity variants, through the same PointerAnalysisFactory:

SootUp

ClassType MAINCLASS = view.getIdentifierFactory().getClassType("dacapo.antlr.Main"); // just an example
PointerAnalysisConfig config = PointerAnalysisConfig.builder()
    .contextSensitivity(ContextSensitivity.zipperObjectSensitive(2, 1)) // ZIPPER-guided 2OBJ, e.g.
    .build();
PTA pta = PointerAnalysisFactory.create(view, MAINCLASS, config);
pta.run();
OnFlyCallGraph cg = pta.getCallGraph();