软件分析实验笔记丨A6

作业目标

为 Java 实现一个上下文敏感的指针分析框架。
作为指针分析的一部分，随着指针分析一起实现调用图（call graph）构建。
实现几种常见的上下文敏感策略（context sensitivity variants）。

新的分析规则

在这一节中，我们引入与上次实验类似的新的指针分析规则来处理静态字段、数组索引和静态方法调用，主要区别在于上下文的部分

静态字段的处理很简单：我们只需要在静态字段和变量之间传值。我们用 T.f 表示静态字段 T.f 的指针，然后定义如下规则来处理静态字段的 store 和 load：

类型	语句	规则（在上下文c下）	PFG 边
Static Store	T.f = y		T.f ← c:y
Static Load	y = T.f		c:y ← T.f

常规指针分析不区分对不同数组索引（位置）的 load 和 store。假设 c’:o_i 代表一个具有上下文c’的数组对象，那么我们用 c’:o_i[∗] 表示一个指向数组中所有对象的指针（无论保存在数组的什么位置）。基于这样的处理，我们定义了数组 store 和 load 的规则：

类型	语句	规则	PFG 边
Array Store	x[i] = y		c':o_u[*] ←c:y
Array Load	y = x[i]		c:y ← c':o_u[*]

静态方法的处理与实例方法大体相同，除了（1）我们不需要在 receiver object 上进行 dispatch 以解析（resolve）出被调用的方法，（2）我们不需要传 receiver object。因为静态方法的处理不需要考虑 receiver object，因此它的处理规则也比实例方法更简单：

类型	语句	规则	PFG 边
Static Call	r = T.m(a1,...,an)		c:a₁ → c^t:m_p1 ... c:a_n → c^t:m_pn c:r ← c^t:m_ret

实现

实现 Solver 类

Solver 类中已经有部分实现好的代码：Solver 类的构造方法中包含了设置堆模型（heap model）和 context selector 的相关代码；Solver.initialize() 方法中包含了初始化 context sensitivity (C.S.) manager、worklist、指针流图和调用图并将它们 store 到 Solver 的字段中的相关代码，从而可以直接使用这些字段。和上次作业一样，我们需要完成以下 5 个API：

void addReachable(CSMethod)

这个方法实现了 AddReachable 函数。

这里和 A5 的区别是 stmtProcessor 并没有提前初始化。且采用了 CS 方法，很多类进行了改变。这里要再了解五个类，Context 、CSManager 、ContextSelector 、PointsToSetFactory 、CSCallGraph 、CSElement 。Context 表示上下文敏感的指针分析中的上下文；CSManage 管理所有需要用到上下文的元素和所有上下文敏感的指针。也就是说，CSElement 或 Pointer 的所有子类的实例（每当你需要用到时）都需要通过这个类的相关 API 来取得；ContextSelector 是上下文敏感指针分析框架和具体的上下文敏感策略（如调用点敏感、对象敏感等）之间的接口。该类有 4 个 API，其中一个 API 返回空上下文，另外三个 API 分别为静态方法、实例方法和堆对象（heap object）选择上下文。本次作业中，当我们在上下文敏感指针分析中处理 Invoke 和 New 语句时，需要使用本类的各个子类中的方法来生成目标方法（Invoke 语句）和新创建对象（new 语句）的上下文。我们需要完成本类的六个子类中的方法；PointsToSetFactory 创建 PointsToSet 的静态工厂方法，可以用该类中的两个 make() 方法来创建 PointsToSet 的实例；CSCallGraph 表示上下文敏感的调用图，它和你上一次作业用的 DefaultCallGraph 非常类似，区别仅为现在调用点和方法被表示为 CSCallSite 和 CSMethod。你需要使用其中的 addReachableMethod(CSMethod) 以及 addEdge(Edge) 这两个 API 来修改调用图；CSElement 表示指针分析中需要用到上下文的元素，每个这样的元素都和一个上下文相关联。它有四个子类，分别表示四种需要用到上下文的元素：

CSVar：表示一个带上下文（Context）的变量（Var）。
CSObj：表示一个带上下文（Context）的抽象对象（Obj）。
CSCallSite：表示一个带上下文（Context）的调用点（Invoke）。
CSMethod：表示一个带上下文（Context）的方法（JMethod）。

private void addReachable(CSMethod csMethod) {
    // TODO - finish me
    if(!callGraph.contains(csMethod)){
        // add m to RM
        callGraph.addReachableMethod(csMethod);
        // S ∪= Sm
        for(Stmt s : csMethod.getMethod().getIR()){
            // 交给访问者模式处理
            StmtVisitor stmtProcessor = null;
            s.accept(stmtProcessor);
        }
    }
}

private class StmtProcessor implements StmtVisitor<Void>

这里是对 addReachable 中的不同的 stmt 类型的处理，主要是加入了上下文的处理。

private class StmtProcessor implements StmtVisitor {
    private final CSMethod csMethod;
    private final Context context;
    private StmtProcessor(CSMethod csMethod) {
        this.csMethod = csMethod;
        this.context = csMethod.getContext();
    }
    // TODO - if you choose to implement addReachable()
    //  via visitor pattern, then finish me
    @Override
    public Void visit(New stmt) {
        // new 语句
        Obj o = heapModel.getObj(stmt);
        // 含上下文的变量
        CSVar csVar = csManager.getCSVar(context,stmt.getLValue());
        // heap context
        Context context1 = contextSelector.selectHeapContext(csMethod,o);
        // 含上下文的对象
        CSObj csObj = csManager.getCSObj(context1,o);
        workList.addEntry(csVar,PointsToSetFactory.make(csObj));
        return null;
    }
    @Override
    public Void visit(Copy stmt) {
        // 赋值语句
        CSVar lVar = csManager.getCSVar(context,stmt.getLValue());
        CSVar rVar = csManager.getCSVar(context,stmt.getRValue());
        addPFGEdge(rVar,lVar);
        return null;
    }
    @Override
    public Void visit(LoadArray stmt) {
        // 数组 load
        return null;
    }
    @Override
    public Void visit(StoreArray stmt) {
        // 数组 store
        return null;
    }
    @Override
    public Void visit(LoadField stmt) {
        if(stmt.isStatic()){
            // 这里只对静态处理
            // 字段 load
            CSVar lVarPtr = csManager.getCSVar(context,stmt.getLValue());
            StaticField rStaticField = csManager.getStaticField(stmt.getFieldRef().resolve());
            addPFGEdge(rStaticField,lVarPtr);
        }
        return null;
    }
    @Override
    public Void visit(StoreField stmt) {
        if(stmt.isStatic()){
            // 字段 store
            CSVar rVarPtr = csManager.getCSVar(context,stmt.getRValue());
            StaticField lStaticField = csManager.getStaticField(stmt.getFieldRef().resolve());
            addPFGEdge(rVarPtr,lStaticField);
        }
        return null;
    }
    @Override
    public Void visit(Invoke stmt) {
        // 这里类似于 ProcessCall 的处理，不过是静态方法
        if(stmt.isStatic()){
            // 同样这里只对静态方法调用处理
            CSCallSite csCallSite = csManager.getCSCallSite(context,stmt);
            Var lVar = stmt.getLValue();
            JMethod m = resolveCallee(null,stmt);
            // 静态方法的上下文
            Context context1 = contextSelector.selectContext(csCallSite,m);
            CSMethod csMethod1 = csManager.getCSMethod(context1,m);
            Edge edge = new Edge<>(CallKind.STATIC, ,csMethod);
            if(callGraph.addEdge(edge)){
                // 如果添加边成功，说明边不在 CG 中
                addReachable(csMethod1);
                InvokeExp invoke = stmt.getInvokeExp();
                for(int i = 0; i < invoke.getArgCount(); i++){
                    // 参数到参数的传递
                    CSVar aPtr = csManager.getCSVar(context,invoke.getArg(i));
                    CSVar pPtr = csManager.getCSVar(context1,m.getIR().getParam(i));
                    addPFGEdge(aPtr,pPtr);
                }
            }
            if(lVar != null){
                // 有返回值对返回值做相应处理
                CSVar lPtr = csManager.getCSVar(context,lVar);
                for(Var ret : m.getIR().getReturnVars()){
                    CSVar retPtr = csManager.getCSVar(context1,ret);
                    addPFGEdge(retPtr,lPtr);
                }
            }
        }
        return null;
    }
}

void addPFGEdge(Pointer,Pointer)

这个方法实现了 AddEdge 函数，和A5相比没有变化。

private void addPFGEdge(Pointer source, Pointer target) {
    // TODO - finish me
    if(pointerFlowGraph.addEdge(source,target)){
        if(!source.getPointsToSet().isEmpty()){
            // pt(s) 不为空就加入 WL
            workList.addEntry(target,source.getPointsToSet());
        }
    }
}

void analyze()

这个方法实现了 Solve 函数的主要部分，即 while 循环部分，同样加入了上下文的处理。

private void analyze() {
    // TODO - finish me
    while(!workList.isEmpty()){
        WorkList.Entry entry = workList.pollEntry();
        Pointer n = entry.pointer();
        PointsToSet pts = entry.pointsToSet();
        PointsToSet delta = propagate(n, pts);
        if(n instanceof CSVar csVar){
            Var v = csVar.getVar();
            for(CSObj o : delta){
                for(StoreField storeField : v.getStoreFields()){
                    CSVar rVarPtr = csManager.getCSVar(csVar.getContext(),storeField.getRValue());
                    InstanceField field = csManager.getInstanceField(o,storeField.getFieldRef().resolve());
                    addPFGEdge(rVarPtr,field);
                }
                for(LoadField loadField : v.getLoadFields()){
                    CSVar lVarPtr = csManager.getCSVar(csVar.getContext(),loadField.getLValue());
                    InstanceField field = csManager.getInstanceField(o,loadField.getFieldRef().resolve());
                    addPFGEdge(field,lVarPtr);
                }
                for(StoreArray storeArray : v.getStoreArrays()){
                    CSVar rVarPtr = csManager.getCSVar(csVar.getContext(),storeArray.getRValue());
                    ArrayIndex index = csManager.getArrayIndex(o);
                    addPFGEdge(rVarPtr,index);
                }
                for(LoadArray loadArray : v.getLoadArrays()){
                    CSVar lVarPtr = csManager.getCSVar(csVar.getContext(),loadArray.getLValue());
                    ArrayIndex index = csManager.getArrayIndex(o);
                    addPFGEdge(index,lVarPtr);
                }
                processCall(csVar,o);
            }
        }
    }
}

PointsToSet propagate(Pointer,PointsToSet)

这个方法合并了算法中的两个步骤。它首先计算差集（Δ=pts−pt(n)），然后将 pts 传播到 pt(p) 中。它返回 Δ 作为调用的结果。依旧只是进行了上下文的信息添加。

private PointsToSet propagate(Pointer pointer, PointsToSet pointsToSet) {
    // TODO - finish me
    PointsToSet ptn = pointer.getPointsToSet();
    PointsToSet delta = PointsToSetFactory.make();
    // 计算 Δ
    for(CSObj o : pointsToSet){
        if(!ptn.contains(o)){
            ptn.addObject(o);
            delta.addObject(o);
        }
    }
    if(!delta.isEmpty()){
        for(Pointer p : pointerFlowGraph.getSuccsOf(pointer)){
            // 传播 n 的新指向关系给他 PFG 上的后继
            workList.addEntry(p,pointsToSet);
        }
    }
    return delta;
}

void processCall(CSVar,CSObj)

这个方法实现了 ProcessCall 函数，还是仅增加了上下文的信息。

private void processCall(CSVar recv, CSObj recv
    // TODO - finish me
    Var var = recv.getVar();
    for(Invoke invoke : var.getInvokes()){
        // 不用判断调用类型，这里都是非静态方法
        JMethod m= resolveCallee(recvObj,invoke
        CSCallSite csCallSite = csManager.getCS
        Context context = contextSelector.selec
        CSMethod csMethod = csManager.getCSMeth
        CSVar thisPtr = csManager.getCSVar(cont
        workList.addEntry(thisPtr,PointsToSetFa
        Edge edge = null;
        // 加边的类型
        if(invoke.isDynamic()){
            edge = new Edge<>(CallKind.DYNAMIC,
        }else if(invoke.isInterface()){
            edge = new Edge<>(CallKind.INTERFAC
        }else if(invoke.isVirtual()){
            edge = new Edge<>(CallKind.VIRTUAL,
        }else if(invoke.isSpecial()){
            edge = new Edge<>(CallKind.SPECIAL,
        }else {
            edge = new Edge<>(CallKind.OTHER,cs
        }
        if(callGraph.addEdge(edge)){
            addReachable(csMethod);
            InvokeExp invokeExp = invoke.getInv
            for(int i = 0; i < invokeExp.getArg
                // 参数到参数的传递
                CSVar aPtr = csManager.getCSVar
                CSVar pPtr = csManager.getCSVar
                addPFGEdge(aPtr,pPtr);
            }
            Var lVar = invoke.getLValue();
            if(lVar != null){
                CSVar lPtr = csManager.getCSVar
                // 有返回值对返回值做相应处理
                for(Var ret : m.getIR().getRetu
                    CSVar retPtr = csManager.ge
                    addPFGEdge(retPtr,lPtr);
                }
            }
        }
    }
}

实现常见的上下文敏感策略

具体而言，需要完成六个 context selector ，每个 selector 中都需要完成三个 API：两个 selectContext(…) 方法和一个 selectHeapContext(…) 方法。

即之前用到的API。对每个 k 层的 context selector，其堆上下文（heap context）的层数为 k−1，举例来说，对一层调用点敏感（1-call-site sensitivity），堆上下文的层数为 0（即没有堆上下文）；对两层调用点敏感（2-call-site sensitivity），堆上下文的层数为 1。

这里还要了解一个类 ListContext 。ListContext 实现了 Context 接口，它将每个上下文表示为一个由若干同类型元素组成的有序列表（对三种上下文敏感策略，该列表分别采用不同的元素来表示上下文：调用点敏感使用的元素为 Invoke，对象敏感使用的元素为 Obj，类型敏感使用的元素为 Type）。该类提供一系列静态工厂方法，即 make(…) 方法来创建上下文，我们需要利用这些方法来完成上面提到的六个上下文 selector。

pascal.taie.analysis.pta.core.cs.selector._1CallSelector

该类实现了一层调用点敏感。

public class _1CallSelector implements ContextSelector {
    @Override
    public Context getEmptyContext() {
        return ListContext.make();
    }
    @Override
    public Context selectContext(CSCallSite callSite, JMethod callee) {
        // TODO - finish me
        return ListContext.make(callSite.getCallSite());
    }
    @Override
    public Context selectContext(CSCallSite callSite, CSObj recv, JMethod callee) {
        // TODO - finish me
        return ListContext.make(callSite.getCallSite());
    }
    @Override
    public Context selectHeapContext(CSMethod method, Obj obj) {
        // TODO - finish me
        return getEmptyContext();
    }
}

pascal.taie.analysis.pta.core.cs.selector._1ObjSelector

该类实现了一层对象敏感。

public class _1ObjSelector implements ContextSelector {
    @Override
    public Context getEmptyContext() {
        return ListContext.make();
    }
    @Override
    public Context selectContext(CSCallSite callSite, JMethod callee) {
        // TODO - finish me
        return callSite.getContext();
    }
    @Override
    public Context selectContext(CSCallSite callSite, CSObj recv, JMethod callee) {
        // TODO - finish me
        return ListContext.make(recv.getObject());
    }
    @Override
    public Context selectHeapContext(CSMethod method, Obj obj) {
        // TODO - finish me
        return getEmptyContext();
    }
}

pascal.taie.analysis.pta.core.cs.selector._1TypeSelector

该类实现了一层类型敏感。

public class _1TypeSelector implements ContextSelector {
    @Override
    public Context getEmptyContext() {
        return ListContext.make();
    }
    @Override
    public Context selectContext(CSCallSite callSite, JMethod callee) {
        // TODO - finish me
        return callSite.getContext();
    }
    @Override
    public Context selectContext(CSCallSite callSite, CSObj recv, JMethod callee) {
        // TODO - finish me
        return ListContext.make(recv.getObject().getContainerType());
    }
    @Override
    public Context selectHeapContext(CSMethod method, Obj obj) {
        // TODO - finish me
        return getEmptyContext();
    }
}

pascal.taie.analysis.pta.core.cs.selector._2CallSelector

该类实现了两层调用点敏感。

public class _2CallSelector implements ContextSelector {
    @Override
    public Context getEmptyContext() {
        return ListContext.make();
    }
    @Override
    public Context selectContext(CSCallSite callSite, JMethod callee) {
        // TODO - finish me
        int len = callSite.getContext().getLength();
        if(len > 0){
            // 获取最后一个
            return ListContext.make(callSite.getContext().getElementAt(len - 1),callSite.getCallSite());
        }else{
            return ListContext.make(callSite.getCallSite());
        }
    }
    @Override
    public Context selectContext(CSCallSite callSite, CSObj recv, JMethod callee) {
        // TODO - finish me
        int len = callSite.getContext().getLength();
        if(len > 0){
            // 获取最后一个
            return ListContext.make(callSite.getContext().getElementAt(len - 1),callSite.getCallSite());
        }else{
            return ListContext.make(callSite.getCallSite());
        }
    }
    @Override
    public Context selectHeapContext(CSMethod method, Obj obj) {
        // TODO - finish me
        int len = method.getContext().getLength();
        if(len > 0){
            // 获取最后一个
            return ListContext.make(method.getContext().getElementAt(len - 1));
        }else{
            return getEmptyContext();
        }
    }
}

pascal.taie.analysis.pta.core.cs.selector._2ObjSelector

该类实现了两层对象敏感。

public class _2ObjSelector implements ContextSelector {
    @Override
    public Context getEmptyContext() {
        return ListContext.make();
    }
    @Override
    public Context selectContext(CSCallSite callSite, JMethod callee) {
        // TODO - finish me
        int len = callSite.getContext().getLength();
        if(len >= 2){
            return ListContext.make(callSite.getContext().getElementAt(len - 2),callSite.getContext().getElementAt(len - 1));
        }else if (len == 1){
            return ListContext.make(callSite.getContext().getElementAt(0));
        }else{
            return getEmptyContext();
        }
    }
    @Override
    public Context selectContext(CSCallSite callSite, CSObj recv, JMethod callee) {
        // TODO - finish me
        int len = recv.getContext().getLength();
        if(len > 0){
            return ListContext.make(recv.getContext().getElementAt(len - 1),recv.getObject());
        }else{
            return ListContext.make(recv.getObject());
        }
    }
    @Override
    public Context selectHeapContext(CSMethod method, Obj obj) {
        // TODO - finish me
        int len = method.getContext().getLength();
        if(len > 0){
            return ListContext.make(method.getContext().getElementAt(len - 1));
        }else{
            return getEmptyContext();
        }
    }
}

pascal.taie.analysis.pta.core.cs.selector._2TypeSelector

该类实现了两层类型敏感。

public class _2TypeSelector implements ContextSelector {
    @Override
    public Context getEmptyContext() {
        return ListContext.make();
    }
    @Override
    public Context selectContext(CSCallSite callSite, JMethod callee) {
        // TODO - finish me
        int len = callSite.getContext().getLength();
        if(len >= 2){
            return ListContext.make(callSite.getContext().getElementAt(len - 2),callSite.getContext().getElementAt(len - 1));
        }else if (len == 1){
            return ListContext.make(callSite.getContext().getElementAt(0));
        }else{
            return getEmptyContext();
        }
    }
    @Override
    public Context selectContext(CSCallSite callSite, CSObj recv, JMethod callee) {
        // TODO - finish me
        int len = recv.getContext().getLength();
        if(len > 0){
            return ListContext.make(recv.getContext().getElementAt(len - 1),recv.getObject().getContainerType());
        }else{
            return ListContext.make(recv.getObject().getContainerType());
        }
    }
    @Override
    public Context selectHeapContext(CSMethod method, Obj obj) {
        // TODO - finish me
        int len = method.getContext().getLength();
        if(len > 0){
            return ListContext.make(method.getContext().getElementAt(len - 1));
        }else{
            return getEmptyContext();
        }
    }
}