weekly report: 2017.09.14-2017.09.19

周报

2017.09.14 ~ 2017.09.19

这周的工作相比前几周进展也不是很大，主要问题还是集中于 slicing 的实现上。由于进展不大，因此这次的周报主要记录一下这周内所做过和尝试过的事情。

jpdg

就像上周说的，打算利用 jpdg 提供的源码自行实现 PDG/SDG 和 slice，因此这周花了一些时间在 jpdg 的源码上，但由于没有找到非常明确的 PDG/SDG 的实现算法，因此看的过程还是比较艰苦。目前还打算继续看下去，感觉对理解 PDG/SDG 应该帮助很大。

Soot built-in PDG

因为看 jpdg 的过程还是挺累的，因此除此之外还在想着到底能不能利用 soot 内置的 ProgramDependenceGraph 来实现 slice。

首先说一下上次提到的异常："java.lang.RuntimeException: PDG construction: A and B are not supposed to be the same node!"。

这周 check 了好多遍代码都没有发现问题，把代码打平(抽离所有不必要的成分，如 Config 等，只保留与 soot 相关的部分)后再次运行也是会产生同样的问题，所以这周就咨询了两位学长和 Lili：两位学长都说没有碰到过类似的异常并且说只简单地用过；Lili 说使用了内置的 PDG 但没有出现类似问题，有时间也会帮我排查一下(非常感谢 Lili)。鉴于此，再次感觉是我代码的问题，于是再次进行了代码打平，却依然有错误，因此，我把焦点放在了这几行代码上，因为正是这几行代码的加入使得整个程序崩溃：

// add a transform to generate PDG
packManager.getPack("jtp").add(new Transform("jtp.pdg_transform", new BodyTransformer() {
    @Override
    protected void internalTransform(Body body, String s, Map<String, String> map) {
        Env.v().setPdg(new HashMutablePDG(new BriefUnitGraph(body)));
    }
}));

仔细观察后(因为 soot 的文档里根本没提到 PDG，这几行代码是从一篇博客中看到的)发现，这个 transform 会聚焦在 Body 上，而我们知道，Body 是 Method 所具有的东西，换言之，这个方法会在类的每个 method 上都会被调用，因此可以知道，soot 内置的 PDG 是狭义的 PDG（仅对某个方法或者基本块进行 PDG 的构建，PDG 中不涉及方法调用），而非 SDG，因此我尝试了下面的方式来检测是否有成功的方法：

// add a transform to generate PDG
packManager.getPack("jtp").add(new Transform("jtp.pdg_transform", new BodyTransformer() {
    @Override
    protected void internalTransform(Body body, String s, Map<String, String> map) {
        String methodSignature = body.getMethod().getSignature();
        try {
            Env.v().getPdgMapping().put(
                    methodSignature,
                    new HashMutablePDG(new BriefUnitGraph(body)));
        } catch (Exception e) {
            System.out.println("Error in generating PDG for " + methodSignature);
        }
    }
}));

结果成功了，这样就知道，上述 transform 会在某些方法上产生异常，大多数方法还是可行的，到 soot 的 issues 下查类似的问题(之前查的一直是"java.lang.RuntimeException: PDG construction: A and B are not supposed to be the same node!"，而不是"Work thread failed, null ponter..."，所以才没有任何收获)才发现确实有这个 bug。因此利用上述的代码就成功的对大部分的方法进行了 PDG 的构建。

接下来说一下有了上述 PDG 进行 slice 还需要的一些条件。

就像上次提到的，soot 内置的 PDG 有一个很大的缺陷，它提供的 PDG 是 CDG only 的，里面并没有与 DDG 相关的任何信息，因此如果使用上述方式对每个方法都进行 PDG 的构建，接下来我们还需要：

加入一个 intra-procedural 的 analysis 来对 DDG 进行捕获
利用 CallGraph 来生成一些与 SDG 相关的信息

与 Lili 聊过，她也是这样来实现的，Lili 还提到，只需少量与 SDG 相关的信息便可以有比较好的结果。

利用 Soot built-in PDG 实现

有了上述的思路，我使用了如下的实现，但目前还是存在问题，先说下代码，再说问题。

首先是 callsite 的定位，对于 callsite 我们利用 method + unit 来定位其发生的位置：

public class Callsite {

    private SootMethod method;

    private Unit unit;

    public Callsite(SootMethod m, Unit u) {
        this.method = m;
        this.unit = u;
    }

    ...
}

之前提到过，对于 model，有 method，field 和 iface 这么几种：

对于 method，利用 callgraph 的 edgesInto 来定位对某个方法的调用。
对于 field 和 iface，还没有找到合适的 API 来定位。

代码里利用 List<Callsite> computeCallsites(ApiContext model) 这个方法来对上述的 model 进行定位。

private List<Callsite> computeCallsites(ApiContext model) {
    CallGraph callGraph = Scene.v().getCallGraph();
    Scene scene = Scene.v();

    String type = model.getApi().getClass().toString().split(" ")[1];
    List<Callsite> callsites = new ArrayList<>(128);

    // get callsites of the specific api
    switch (type) {
        case ApiField.TAG: {
            ApiField apiField = (ApiField) model.getApi();
            SootField sootField = scene.getField(apiField.getSiganiture());

            // TODO I have no idea how to get the callsite of a specific field

            break;
        }

        case ApiMethod.TAG: {
            ApiMethod apiMethod = (ApiMethod) model.getApi();
            SootMethod sootMethod = scene.getMethod(apiMethod.getSiganiture());

            Iterator<Edge> edges = callGraph.edgesInto(sootMethod);

            while (edges.hasNext()) {
                Edge edge = edges.next();
                callsites.add(new Callsite(edge.src(), edge.srcUnit()));
            }

            break;
        }

        case ApiIface.TAG: {
            ApiIface apiIface = (ApiIface) model.getApi();
            SootClass sootIface = scene.getSootClass(apiIface.getSiganiture());

            // TODO I have no idea how to get the callsite of a specific interface

            break;
        }

        default: throw new RuntimeException("Invalid api type: " + type);
    }

    return callsites;
}

假设我们已经找到了定位，接下来是进行 slice 工作，代码中利用 List<Unit> runBackwardSlicingFor(Callsite callsite) 这个方法来进行：

private List<Unit> runBackwardSlicingFor(Callsite callsite) {

    // TODO run backward slicing here

    List<Unit> slice = new ArrayList<>(128);
    Map<String, ProgramDependenceGraph> pdgMapping = Env.v().getPdgMapping();
    ProgramDependenceGraph pdg = pdgMapping.get(callsite.getMethod().getSignature());

    // callsite unit
    Unit callsiteUnit = callsite.getUnit();
    PDGNode srcNode = null;

    // find the corresponding PDGNode
    for (PDGNode n : pdg) {
        PDGNode.Type type = n.getType();
        Iterator<Unit> iterator = null;

        // get iterator
        if (type.equals(PDGNode.Type.CFGNODE)) {
            iterator = ((Block) n.getNode()).iterator();
        } else if (type.equals(PDGNode.Type.REGION)) {
            iterator = ((Region) n.getNode()).getUnitGraph().iterator();
        }

        // get srcNode
        if (iterator != null) {
            while (iterator.hasNext()) {
                if (iterator.next().equals(callsiteUnit)) {
                    srcNode = n;
                    break;
                }
            }
        }

        if (iterator != null && srcNode != null) {
            break;
        }
    }

    // find the slice in pdg
    List<PDGNode> dependents = srcNode.getBackDependets();

    // TODO find suitable api to get the slice in Unit

    return slice;
}

问题

可以看到，上述代码中有几处 TODO，正是目前需要解决的几个问题，这里提一下：

如何对 field 和 iface 进行定位
PDG 目前已经可以构建，并且可以成功得到针对某个 callsite 的依赖节点，但却无法明确地获得其对应的 Unit
如何添加一个 intra-procedural 的 data-flow analysis 来对 DDG 进行捕获

思考

可以说，上面三个问题中，阻碍开发进行的正是第二个问题，这也是亟需 Lili 帮助的一个问题。不过总结一下也容易看出来，这些问题归到底是对 soot 的不熟练造成的(感觉文档确实写的不是很清楚，使得上手非常困难)。

另外，还发现了几篇关于 slice 的文章，这里推荐一下。

connglli / ELEGANT