课程网站为Static Program Analysis | Tai-e

本次实验为作业 8：污点分析

作业目标

  • 为 Java 实现污点分析。
  • 最后一次作业！ヾ(≧▽≦*)o

在这次作业中，我们需要基于第 6 次作业实现的上下文敏感的指针分析来为 Java 实现污点分析（taint analysis）。为了让此次的污点分析不仅仅是个玩具，我们会在这次作业中学习一个叫做污点传播（taint transfer）的技术，这样实现的污点分析就能够应用到生产实践中检测安全漏洞了。此外，taie 也提供了可配置的污点分析框架，帮助方便地设置污点分析中所需要的诸如 sources、sinks 等数据。

实现污点分析

分析范围

在这一小节中，我们来定义一下在这次作业中所需要实现的污点分析。和第 13 讲介绍的污点分析一样，我们会把一些特定的方法（通常是产生数据的 API）视作 taint sources，调用这些方法的语句会返回污点数据；为了和指针分析中的对象对应，这些污点数据也被叫做污点对象（taint objects）。我们也把一些特定方法的某些参数视作 taint sinks。此外，为了达到更高的精度，需要实现一个上下文敏感的污点分析。作为参考，已经写好了处理 sources 和 sinks 的规则：

这里，Sources 是二元组 ⟨m,u⟩ 的集合，其中 m 表示一个被视作 source 的方法的签名，而 u 是该方法返回的污点对象的类型。我们用 tlu 来表示一个污点对象，其中 u 是这个对象的类型，l 表示创建这个对象的调用点（call site）。简单起见，只需要使用空上下文作为污点对象的堆上下文（heap context）。

污点传播. 污点分析和指针分析看起来很相似，因为他们本质上都在跟踪程序中数据的流动——指针分析跟踪的是抽象的对象，污点分析跟踪的是污点对象。但是他们又有些微妙的不同：污点分析中的污点是一个更加抽象的概念——它与数据的内容相关联，因此它可以在不同的对象之间传播。我们把这样的现象叫做污点传播（taint transfer）。下面我们通过一个例子来学习这个概念：

String taint = getSecret(); // source
StringBuilder sb = new StringBuilder();
sb.append("abc");
sb.append(taint); // taint is transferred to sb
sb.append("xyz");
String s = sb.toString(); // taint is transferred to s
leak(s); // sink

假设我们把 getSecret() 和 leak() 分别视作 source 和 sink，那么在这个例子中，第 1 行的代码首先通过方法调用获得了一份字符串类型的秘密数据（即污点对象）并把它保存在了变量 taint 中。然后，这份秘密数据会经过两次污点传播流入到第 7 行的 sink 中：

  1. 第 4 行的方法调用 append() 把 taint 中包含的内容添加到了 sb 的末尾，于是 sb 指向的 StringBuilder 对象中也包含了秘密数据，故而该对象也应该被视作污点对象。换句话说，第 4 行的 append() 方法把污点从变量 taint 指向的对象传播到了变量 sb 指向的对象中。
  2. 第 6 行的方法调用 toString() 把 StringBuilder 对象转化成了包含相同内容的 String 对象，因此这个 String 也包含了秘密数据。换句话说，toString() 把污点从变量 sb 指向的对象中传播到了变量 s 指向的对象中。

然而，课上讲解的污点分析算法由于无从知道程序中 API 的含义，例如它不知道上面例子中的 append() 和 toString() 方法可以在不同的对象之间传播内容（特别是敏感数据），因而它不会像我们先前所描述的那样顺利地传播污点。结果就是，很多安全漏洞都会被遗漏。又因为上述模式在现实中的代码中很常见，所以我们需要对这些方法进行额外处理。

我们的解决方法是告诉污点分析哪些方法会引发污点传播以及它们是如何传播污点的。在这次作业中，当一个引发污点传播的方法 foo 被调用时，有以下三种污点传播的模式：

  1. Base-to-result：如果 receiver object（由 base 指向）被污染了，那么该方法调用的返回值也会被污染。StringBuilder.toString() 是这样一类方法。
  2. Arg-to-base：如果某个特定的参数被污染了，那么 receiver object（由 base 指向）也会被污染。StringBuilder.append(String) 是这样一类方法。
  3. Arg-to-result：如果某个特定的参数被污染了，那么该方法调用的返回值也会被污染。String.concat(String) 是这样一类方法。

注意，因为静态方法没有 base 变量，所以他们不会引起 base-to-result 和 arg-to-base 的污点传播。此外，一些方法可能会引起多种污点传播，例如 String.concat(String) 不仅会引发 arg-to-result 的传播，也会引发 base-to-result 的传播。这是因为，它的返回值中同时包含了参数和 receiver object 的内容。

处理污点传播. 本质上，污点传播指的是某个方法调用会在调用点把污点从一些变量传播到另外一些变量中。在这样的传播过程中，我们把污点的来源称为 from 变量，把目标称为 to 变量。例如，对于一个 base-to-result 的污点传播，from 变量指的是调用点中的 base 变量，to 变量指的是调用点中接收返回值的变量。

为了处理污点传播，我们为污点分析定义一种新的输入，叫做 TaintTranfers。它是由四元组 ⟨m,from,to,u⟩ 所构成的集合，其中 m 表示会引发污点传播的方法，而污点会从 from 所表示的变量中传播到 to 所表示的变量中。u 表示传播后的污点（由 to 指向）的类型。具体来说,

  • m 是引发污点传播的方法的签名；
  • from 要么是一个从 0 开始的整数索引，用来表示调用点中的实参，要么是字符串“base”，表示 base 变量。
  • to 是字符串“base”，表示 base 变量，要么是字符串“result”，表示调用点中接收返回值的变量；
  • u 是传播后污点对象的类型。我们之所以需要这个信息，是因为污点传播有可能改变污点对象的类型。例如，StringBuilder.toString() 就会把污点从一个 StringBuilder 类型的对象上传播到一个 String 类型的对象上。所以，我们需要用 u 来告诉分析算法传播后污点对象是什么类型。当污点对象类型在传播前后不一样时，这就很有用了。

基于 TaintTransfers，我们下面给出应对三种污点传播模式的污点分析规则：

类型 语句 规则
Call (base-to-result) l: r = x.k(a1,...,an)
Call (arg-to-base) l: r = x.k(a1,...,an)
Call (arg-to-result) l: r = x.k(a1,...,an)

配置污点分析. 为了让污点分析用起来灵活，我们设计了可配置的污点分析框架。该框架支持你使用 YAML 格式来配置 sources、sinks和污点传播。作业包中路径为 src/test/resources/pta/taint/taint-config.yml 的文件可以作为参考样例。

配置文件由一条条数据构成。表示 source 的数据格式是：

{ method: <METHOD_SIGNATURE>, type: <TYPE_NAME> }

其中

  • <METHOD_SIGNATURE> 是 source 方法的签名；
  • <TYPE_NAME> 是调用该方法返回的污点对象的类型名称。

在指针分析中，每个对象都有类型，污点对象也不外乎如是。所以，我们需要在配置文件中指明污点对象的类型，这样污点分析在处理 source 方法调用的时候才能创建出类型正确的污点对象。

表示 sink 的数据格式是：

{ method: <METHOD_SIGNATURE>, type: <INDEX> }

其中

  • <METHOD_SIGNATURE> 是 sink 方法的签名；
  • <INDEX> 是指向方法参数的索引，一般是包含敏感信息的参数（通常也只有参数才会被设置为sinks）。它从0开始计数。

表示污点传播的数据格式是：

{ method: <METHOD_SIGNATURE>, from: <INDEX>, to: <INDEX>, type: <TYPE_NAME> }

这里的四个元素刚好对应了前面定义的 TaintTransfers 中的四元组。

具体实现

Solver 中要实现的 5 个方法和作业 6中的一样，只不过现在需要再添加一些代码来支持污点分析。但是要注意，不要直接用作业 6中的 Solver.java 来替换本次作业中的同名文件，因为这次作业中的 Solver.java 中还包含了一些和污点分析相关的框架代码。

在这次作业中，可能会需要分析指针集的结果来帮助开发和调试污点分析。但是附有上下文信息的指针集很可能会看得头疼，所以我们这次把 CISelector（上下文不敏感）指定为默认的上下文策略。希望这能让调试变得轻松一点。

在 TaintAnalysiss 类中，除了 collectTaintFlows()，也需要实现处理 sources 和污点传播的逻辑。这次作业是开放式的，所以需要自己想办法实现污点分析，比如考虑设计什么样的数据结构和辅助方法加入到 TaintAnalysiss 中。

提示：
  1. 在 TaintAnalysiss 的构造函数中，已经给出了解析配置文件的代码，并把解析的结果保存在了 config 字段中，可以直接使用它。此外，也初始化了 TaintManager 对象并将其保存在了 manager 字段中，可以通过它来管理污点对象。如果实现还需要做一些初始化工作，也可以在构造函数中代码。
  2. 在这次作业中，指针分析和污点分析互相依赖，所以 Solver 和 TaintAnalysiss 各自保存了指向对方的引用，即 Solver 中的 taintAnalysis 字段和 TaintAnalysiss 中的 solver 字段。需要想清楚如何利用这两个引用字段实现两个分析之间的交互。如果有需要的话，也可以向这两个类中添加自己需要的字段和方法。
在这次作业中，需要补全下面列出的两个类中的方法：

pascal.taie.analysis.pta.cs.Solver:

  • void addReachable(CSMethod)
  • void addPFGEdge(Pointer,Pointer)
  • void analyze()
  • PointsToSet propagate(Pointer,PointsToSet)
  • void processCall(CSVar,CSObj)

pascal.taie.analysis.pta.plugin.taint.TaintAnalysiss:

  • Set<TaintFlow> collectTaintFlows()：返回一个集合，其中包含污点分析检测到的所有 taint flows。提示：你可以在这个方法中实现处理 sink 的规则。

其中我修改和添加的地方如下：

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
    ...
    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,csCallSite,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){
                // 有返回值对返回值做相应处理
                // 加入污点分析的内容
                Obj taint = taintAnalysis.makeTaint(stmt, m);
                if(taint != null){
                    CSObj csTaint = csManager.getCSObj(contextSelector.getEmptyContext(), taint);
                    workList.addEntry(csManager.getCSVar(context, lVar), PointsToSetFactory.make(csTaint));
                }
            }
        }
        return null;
    }
}

这里将对调用方法的处理修改为污点分析，其余部分未改变已省略。

private void processCall(CSVar recv, CSObj recvObj) {
    // TODO - finish me
    Var var = recv.getVar();
    Obj o = recvObj.getObject();
    Context c = recv.getContext();
    // recv 作为 arg
    if(taintAnalysis.isTaint(o)){
        for(CSMethod csMethod : callGraph.reachableMethods().toList()){
            if(!csMethod.getContext().equals(c)){
                continue;
            }
            for(Stmt stmt : csMethod.getMethod().getIR()){
                if(stmt instanceof Invoke invoke){
                    for(Var arg : invoke.getInvokeExp().getArgs()){
                        if(var.equals(arg)){
                            JMethod caller = invoke.getMethodRef().resolve();
                            if (taintAnalysis.isArgToBase(caller)) {
                                Var base = ((InvokeInstanceExp) invoke.getInvokeExp()).getBase();
                                workList.addEntry(csManager.getCSVar(c, base), PointsToSetFactory.make(recvObj));
                            }
                            if (taintAnalysis.isArgToResult(caller)) {
                                workList.addEntry(csManager.getCSVar(csMethod.getContext(), invoke.getLValue()), PointsToSetFactory.make(recvObj));
                            }
                        }
                    }
                }
            }
        }
    }
    // recv 作为 base
    for(Invoke callSite : var.getInvokes()){
        if(taintAnalysis.isTaint(o)){
            if(taintAnalysis.isBaseToResult(callSite.getMethodRef().resolve())){
                workList.addEntry(csManager.getCSVar(c, callSite.getLValue()), PointsToSetFactory.make(recvObj));
            }
            continue;
        }
        JMethod callee = resolveCallee(recvObj, callSite);
        CSCallSite csCallSite = csManager.getCSCallSite(c, callSite);
        Context ct = contextSelector.selectContext(csCallSite, recvObj, callee);
        workList.addEntry(csManager.getCSVar(ct, callee.getIR().getThis()), PointsToSetFactory.make(recvObj));
        CSMethod csCallee = csManager.getCSMethod(ct, callee);
        if(callGraph.addEdge(new Edge<>(CallGraphs.getCallKind(callSite), csCallSite, csCallee))){
            addReachable(csCallee);
            InvokeExp invoke = csCallSite.getCallSite().getInvokeExp();
            JMethod m = csCallee.getMethod();
            Context context = csCallSite.getContext();
            Context context1 = csCallee.getContext();
            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(callSite.getLValue() != null){
                // 有返回值对返回值做相应处理
                CSVar lPtr = csManager.getCSVar(context,callSite.getLValue());
                for(Var ret : m.getIR().getReturnVars()){
                    CSVar retPtr = csManager.getCSVar(context1,ret);
                    addPFGEdge(retPtr,lPtr);
                }
            }
        }
        for (Var arg : callSite.getInvokeExp().getArgs()) {
            for (CSObj csObj : csManager.getCSVar(c, arg).getPointsToSet()) {
                if (taintAnalysis.isTaint(csObj.getObject())) {
                    if (taintAnalysis.isArgToBase(callee)) {
                        workList.addEntry(recv, PointsToSetFactory.make(csObj));
                    }
                    if (taintAnalysis.isArgToResult(callee)) {
                        workList.addEntry(csManager.getCSVar(c, callSite.getLValue()), PointsToSetFactory.make(csObj));
                    }
                }
            }
        }
    }
}

这里同样也是根据规则修改为污点分析版本。

package pascal.taie.analysis.pta.plugin.taint;
import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;
import pascal.taie.World;
import pascal.taie.analysis.pta.PointerAnalysisResult;
import pascal.taie.analysis.pta.core.cs.context.Context
import pascal.taie.analysis.pta.core.cs.element.CSManag
import pascal.taie.analysis.pta.core.heap.Obj;
import pascal.taie.analysis.pta.cs.Solver;
import pascal.taie.ir.stmt.Invoke;
import pascal.taie.ir.stmt.Stmt;
import pascal.taie.language.classes.JMethod;
import java.util.*;
public class TaintAnalysiss {
    private static final Logger logger = LogManager.get
    private final TaintManager manager;
    private final TaintConfig config;
    private final Solver solver;
    private final CSManager csManager;
    private final Context emptyContext;
    private final Set argToBase ;
    private final Set argToResult;
    private final Set baseToResult;
    public TaintAnalysiss(Solver solver) {
        manager = new TaintManager();
        this.solver = solver;
        csManager = solver.getCSManager();
        emptyContext = solver.getContextSelector().getE
        config = TaintConfig.readConfig(
                solver.getOptions().getString("taint-co
                World.get().getClassHierarchy(),
                World.get().getTypeSystem());
        logger.info(config);
        baseToResult = new HashSet<>();
        argToBase = new HashSet<>();
        argToResult = new HashSet<>();
        processTransfer();
    }

在 TaintAnalysis.java 中加的初始化内容。

private Set collectTaintFlows() {
    Set taintFlows = new TreeSet<>();
    PointerAnalysisResult result = solver.getResult();
    // TODO - finish me
    // You could query pointer analysis results you need via variable result.
    List methodList = result.getCallGraph().reachableMethods().toList();
    for(JMethod method : methodList){
        for(Stmt stmt : method.getIR()) {
            if(stmt instanceof Invoke invoke){
                JMethod callee = invoke.getMethodRef().resolve();
                for(Sink sink : config.getSinks()){
                    if(callee.equals(sink.method())){
                        int index = sink.index();
                        Set set =  result.getPointsToSet(invoke.getInvokeExp().getArg(index));
                        for(Obj obj : set){
                            if(isTaint(obj)){
                                taintFlows.add(new TaintFlow(manager.getSourceCall(obj), invoke, index));
                            }
                        }
                    }
                }
            }
        }
    }
    return taintFlows;
}

污点分析

private void processTransfer(){
    for(TaintTransfer transfer : config.getTransfers()){
        JMethod method = transfer.method();
        int from = transfer.from(), to = transfer.to();
        // NOTE: base = -1, result = -2
        if(from == -1 && to == -2) {
            baseToResult.add(method);
        }
        if(from >= 0 && to == -1){
            argToBase.add(method);
        }
        if(from >= 0 && to == -2){
            argToResult.add(method);
        }
    }
}
public Obj makeTaint(Invoke invoke, JMethod m) {
    for(Source src : config.getSources()){
        if(src.method().equals(m)){
            return manager.makeTaint(invoke, src.type());
        }
    }
    return null;
}
public boolean isTaint(Obj obj) {
    return manager.isTaint(obj);
}
public boolean isArgToBase(JMethod callee) {
    return argToBase.contains(callee);
}
public boolean isArgToResult(JMethod callee){
    return argToResult.contains(callee);
}
public boolean isBaseToResult(JMethod callee){
    return baseToResult.contains(callee);
}

辅助函数

总结

并未通过全部测试，不过时间有限，就先做到这里了。