Post

NJU静态分析 - Lab8 - 污点分析

NJU静态分析 - Lab8 - 污点分析

分析

在污点分析中,我们需要处理一种特殊的对象:污点对象。这种对象有什么特性呢?

  • 污点对象的上下文为空上下文
  • 污点对象只会在method call中产生
  • 污点对象没有方法,不会引发method call
  • 污点对象的传播方式在普通对象的基础上新增了三种:Base-to-resultArg-to-baseArg-to-result

根据上述性质,我们可以设计出污点分析的算法

算法

生成新污点对象

新污点对象只会在method call中产生并传递给等号左边的变量,且该method必须是Source,于是我们可以在processCall函数中找到新的污点对象并将其加入WorkList中:(注意静态方法和实例方法都有可能产生污点对象,建议可以更改processCall函数使其能同时处理静态方法和实例方法,例如可以声明为:processCall(CSVar, CSObj, Invoke, Context),并通过CSVar是否为null来判断方法类型)

1
2
3
4
5
6
7
8
9
10
11
Var receiveVar = callSite.getResult();
if (receiveVar != null) {
    PointsToSet pointsToSet = PointsToSetFactory.make();
    for (CSObj taintObj : taintAnalysis.getTaintObj(callSite, callee)) {
        pointsToSet.addObject(taintObj);
    }
    if (!pointsToSet.isEmpty()) {
        // Add to taintWorkList for taint propagation
        taintWorkList.addEntry(csManager.getCSVar(currentContext, receiveVar), pointsToSet);
    }
}

(注意这里的WorkList是taintWorkList,原因后续会提到)


传播污点对象

污点对象的传播方式包含了所有普通对象的传播方式,因此重合的部分可以直接调用propagate函数。而新增的三条传播方式只会在method call中出现,因此可以在处理method call时增加对这三种方法的实现:

1
2
3
4
5
6
7
8
9
// base-to-result
Var resultVar = callSite.getResult();
if (resultVar != null) {
    CSObj newTaint = taintAnalysis.baseToResultTransfer(method, diffObj.getObject());
    if (newTaint != null) {
        CSVar result = csManager.getCSVar(base.getContext(), resultVar);
        taintWorkList.addEntry(result, PointsToSetFactory.make(newTaint));
    }
}
1
2
3
4
5
// arg-to-base
CSObj newTaint = taintAnalysis.argToBaseTransfer(method, index, diffObj.getObject());
if (newTaint != null) {
    taintWorkList.addEntry(base, PointsToSetFactory.make(newTaint));
}
1
2
3
4
5
6
7
8
9
// arg-to-result
Var resultVar = callSite.getResult();
if (resultVar != null) {
    CSVar result = csManager.getCSVar(varCS.getContext(), resultVar);
    CSObj newTaint = taintAnalysis.argToResultTransfer(method, index, diffObj.getObject());
    if (newTaint != null) {
        taintWorkList.addEntry(result, PointsToSetFactory.make(newTaint));
    }
}

收集TaintFlows

收集TainFlows的方式也非常简单,只需要在做完指针分析之后遍历一遍callSite,找到是否有匹配的Sink即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
private Set<TaintFlow> collectTaintFlows() {
    Set<TaintFlow> taintFlows = new TreeSet<>();
    PointerAnalysisResult result = solver.getResult();
    CallGraph<CSCallSite, CSMethod> callGraph = result.getCSCallGraph();
    callGraph.reachableMethods().forEach(csMethod -> {
        JMethod method = csMethod.getMethod();
        Set<Sink> sinks = getSinksOf(method);
        if (!sinks.isEmpty()) {
            for (CSCallSite csCallSite : callGraph.getCallersOf(csMethod)) {
                Invoke callSite = csCallSite.getCallSite();
                Context context = csCallSite.getContext();
                List<Var> args = callSite.getInvokeExp().getArgs();
                for (Sink sink : sinks) {
                    int index = sink.index();
                    Var var = args.get(index);
                    CSVar csVar = csManager.getCSVar(context, var);
                    for (CSObj csObj : csVar.getPointsToSet()) {
                        Obj obj = csObj.getObject();
                        if (manager.isTaint(obj)) {
                            taintFlows.add(new TaintFlow(manager.getSourceCall(obj), callSite, index));
                        }
                    }
                }
            }
        }
    });
    return taintFlows;
}

设计

由于污点对象不会触发method call,因此污点对象的存在不会使callGraph中产生新的调用边。也就是说,即使在指针分析中不处理污点对象,得到callGraphpointerFlowGraph都是完整的,而又由于污点对象的传播需要三条新规则,如果把这三条新规则糅合到processCall函数中,势必会造成函数体的臃肿。因此作者的处理方式是,在第一轮指针分析中只寻找Source,并将新的污点对象置于单独的WorkList中,而不对污点对象进行传播。在第一轮指针分析之后,我们已经得到了完整的callGraphpointerFlowGraph,此时再进行一遍污点对象专属的指针分析。这样做也不会过多的影响效率,因为我们要处理的对象只剩下了污点对象:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
private void taintAnalysis() {
    while (!taintWorkList.isEmpty()) {
        WorkList.Entry entry = taintWorkList.pollEntry();
        Pointer pointer = entry.pointer();
        PointsToSet pointsToSet = entry.pointsToSet();
        PointsToSet diff = propagate(pointer, pointsToSet, taintWorkList);

        if (pointer instanceof CSVar varCS) {
            for (CSObj diffObj : diff) {
                for (CSVarRecord record : getCallSitesOfVar(varCS)) {
                    Invoke callSite = record.callSite();
                    JMethod method = record.method();
                    int index = record.index();
                    CSVar base = record.base();
                    if (index == BASE) {
                        // base-to-result
                        ...
                    } else {
                        if (base != null) {
                            // arg-to-base
                            ...
                        }
                        // arg-to-result
                        ...
                    }
                }
            }
        }
    }
}
This post is licensed under CC BY 4.0 by the author.