Write your own analysis in Qilin

On this page, we discuss how to write a new pointer analysis in Qilin. For developers who just want to use pointer analyses provided in Qilin in their own client analyses, please refer to Qilin-as-a-lib.

The Programming Task

We want to build a new pointer analysis, named CollectionsPTA, that will analyze the methods in all the subclasses of {java.util.Collection, java.util.Dictonary, java.util.Map, java.util.Arrays, java.util.Collections} context-sensitively under 3OBJ but all the remaining methods in the program context-insensitively.

ColloctionsPTA

The source code of this task could be found here.

ColloctionsPTA is quite simple. Its code is shown below:

package qilin.pta.tools;

import qilin.core.parm.ctxcons.CollectionCtxConstructor;
import qilin.parm.heapabst.AllocSiteAbstractor;
import qilin.parm.heapabst.HeuristicAbstractor;
import qilin.parm.select.CtxSelector;
import qilin.parm.select.HeuristicSelector;
import qilin.parm.select.PipelineSelector;
import qilin.parm.select.UniformSelector;
import qilin.pta.PTAConfig;

public class CollectionsPTA extends BasePTA {
    public CollectionsPTA() {
        this.ctxCons = new CollectionCtxConstructor();
        CtxSelector us = new UniformSelector(3, 2);
        if (PTAConfig.v().getPtaConfig().enforceEmptyCtxForIgnoreTypes) {
            this.ctxSel = new PipelineSelector(new HeuristicSelector(), us);
        } else {
            this.ctxSel = us;
        }
        if (PTAConfig.v().getPtaConfig().mergeHeap) {
            System.out.println(".... Heuristic...");
            this.heapAbst = new HeuristicAbstractor(pag);
        } else {
            this.heapAbst = new AllocSiteAbstractor(pag);
        }
        System.out.println("CollectionsPTA ...");
    }
}

In its constructor method, we have initialized its three context-sensitivity-controlling parameters. The context selector ctxSel and the heap abstractor heapAbst are defined exactly according to 3OBJ. The only difference is that the context constructor ctxCons has been replaced by a newly designed constructor CollectionCtxConstructor.

CollectionCtxConstructor

CollectionCtxConstructor's implementation is given below:

package qilin.core.parm.ctxcons;

import qilin.core.PTAScene;
import qilin.core.context.ContextElement;
import qilin.core.context.ContextElements;
import qilin.core.pag.CallSite;
import qilin.core.pag.ContextAllocNode;
import qilin.parm.ctxcons.CtxConstructor;
import soot.*;

import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class CollectionCtxConstructor implements CtxConstructor {
    private final Set<Type> collections = Stream.of(
        RefType.v("java.util.Collection"),
        RefType.v("java.util.Dictionary"),
        RefType.v("java.util.Map"),
        RefType.v("java.util.Arrays"),
        RefType.v("java.util.Collections")
    ).collect(Collectors.toSet());


    @Override
    public Context constructCtx(MethodOrMethodContext caller, ContextAllocNode receiverNode, CallSite callSite, SootMethod target) {
        boolean flag = false;
        RefType declClassType = target.getDeclaringClass().getType();
        for(Type type : collections) {
            if(PTAScene.v().getOrMakeFastHierarchy().canStoreType(declClassType, type)) {
                flag = true;
                break;
            }
        }
        // if target method is not a method declared in any subclasses of collections, return empty context.
        if (!flag) {
            return emptyContext;
        }
        // otherwise, construct the callee context as kOBJ.
        Context callerContext = caller.context();
        if (receiverNode == null) { // static invoke
            return callerContext;
        }
        Context context = receiverNode.context();
        assert context instanceof ContextElements;
        ContextElements ctxElems = (ContextElements) context;
        int s = ctxElems.size();
        ContextElement[] cxtAllocs = ctxElems.getElements();
        ContextElement[] array = new ContextElement[s + 1];
        array[0] = receiverNode.base();
        System.arraycopy(cxtAllocs, 0, array, 1, s);
        return new ContextElements(array, s + 1);
    }
}

The logic in the constructCtx method is also straightforward. If a target method is not declared in a subclass of collections, then an empty context is returned. Otherwise, it constructs a context exactly according to kOBJ.

Test CollectionsPTA

The test code is given below:

import driver.PTAOption;
import qilin.core.PTA;
import qilin.pta.tools.CollectionsPTA;
import qilin.util.Stopwatch;

public class Main {
    public static void main(String[] args) {
        Stopwatch stopwatch = Stopwatch.newAndStart("Pointer Analysis");
        new PTAOption().parseCommandLine(args);
        driver.Main.setupSoot();
        PTA pta = new CollectionsPTA();
        pta.run();
        stopwatch.stop();
        System.out.println(stopwatch);
    }
}

With the following arguments:

-lcs
-mh
-apppath
/home/hedj/Work/QiLinOfficial/artifact/benchmarks/dacapo2006/luindex.jar
-reflectionlog
/home/hedj/Work/QiLinOfficial/artifact/benchmarks/dacapo2006/luindex-refl.log
-libpath
/home/hedj/Work/QiLinOfficial/artifact/benchmarks/dacapo2006/luindex-deps.jar
-mainclass
dacapo.luindex.Main
-jre=/home/hedj/Work/QiLinOfficial/artifact/benchmarks/JREs/jre1.6.0_45

We can obtain the analysis results for luindex as follows:

Time (sec):                                       11.552
#Reachable Method (CI):                           7304
#Call Edge(CI):                                   37598
#May Fail Cast (Total):                           849
#Virtual Call Site(Polymorphic):                  1151
#Avg Points-to Target without Native Var(CI):     16.969554710403298