Tai-e 指针分析PTA初探

了解了IR，再来了解下最常用的PTA 指针分析是如何实现的。

0x01 指针分析PTA原理

1.1 定义

upload successful

我们将分析一个指针可能指向的内存区域（Memory Location），以程序（Program）为输入，以程序中的指向关系（Point-to Relation）为输出的分析称作指针分析（Pointer Analysis）。

这里先看简单的上下文不敏感的分析，举例说明

有个程序，求解运行foo()之后的变量/字段指向关系

1
2
3
4
5
class A {
    B b;
    void setB(B b) { this.b = b; }
    B getB() { return this.b; }
}
1
2
3
4
5
6
void foo() {
    A a = new A();
    B x = new B();
    a.setB(x);
    B y = a.getB();
}

结果如下：
upload successful

注：

  • 此处是上下文不敏感分析

1.2 指针分析的关键因素

upload successful

这里仅做提及，后续再详细分析。

1.3 上下文敏感的指针分析算法

upload successful

指针分析这块原理很多，只是捡了几个重点的贴出来，强烈建议去看两位老师的课件。

0x02 Tai-e IR

在前面一文《Tai-e 分析之IR》中，我们跟踪了Tai-e 是如何利用Soot，再通过Transfrom和各种Converter build Tai-e自己的IR。

IR是整个PTA分析的前提。

这里单独讲讲几个重要的基础IR。

2.1 Var IR

Tai-e的Var IR也有些特殊，在Var初始化的时候，会生成相关的Var属性

  • method: 所属method
  • name
  • type
  • index
  • constValue
  • relevantStmts: 存储该Var相关的特殊stmts
    • loadFields
    • storeFields
    • loadArrays
    • storeArrays
    • invokes
      1
      2
      3
      4
      5
      6
      * Relevant statements of a variable, say v, which include:
      * load field: x = v.f;
      * store field: v.f = x;
      * load array: x = v[i];
      * store array: v[i] = x;
      * invocation: v.f();

其中的relevantStmts是该Var相关的一些特殊Stmt，方便后续的程序分析。

居然是在这一步做的。

在后续的分析中，会获取Var相关Field，比如StoreFiled的逻辑：

Var

1
2
3
4
public List<StoreField> getStoreFields() {
    return relevantStmts.getStoreFields();
}
Var$RelevantStmts
1
2
3
private List<StoreField> getStoreFields() {
    return unmodifiable(storeFields);
}

重点讲解下Var$RelevantStmts内部类。

upload successful

疑问：relevantStmts是IR的时候就已经关联上了，还是在后续分析的时候关联上的?

答案是IR build的时候，其构建过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
addStoreField:172, Var (pascal.taie.ir.exp)
<init>:42, StoreField (pascal.taie.ir.stmt)
caseAssignStmt:605, MethodIRBuilder (pascal.taie.frontend.soot)
apply:217, JAssignStmt (soot.jimple.internal)
lambda$buildStmts$1:251, MethodIRBuilder (pascal.taie.frontend.soot)
accept:-1, MethodIRBuilder$$Lambda$244/0x0000000800ebcf78 (pascal.taie.frontend.soot)
forEach:75, Iterable (java.lang)
buildStmts:251, MethodIRBuilder (pascal.taie.frontend.soot)
build:226, MethodIRBuilder (pascal.taie.frontend.soot)
buildIR:53, IRBuilder (pascal.taie.frontend.soot)
getIR:192, JMethod (pascal.taie.language.classes)
addEntryPoint:788, DefaultSolver (pascal.taie.analysis.pta.core.solver)
onStart:65, EntryPointHandler (pascal.taie.analysis.pta.plugin)
accept:-1, CompositePlugin$$Lambda$311/0x0000000800ef0820 (pascal.taie.analysis.pta.plugin)
forEach:1511, ArrayList (java.util)
onStart:99, CompositePlugin (pascal.taie.analysis.pta.plugin)
initialize:265, DefaultSolver (pascal.taie.analysis.pta.core.solver)
solve:245, DefaultSolver (pascal.taie.analysis.pta.core.solver)
runAnalysis:119, PointerAnalysis (pascal.taie.analysis.pta)
analyze:107, PointerAnalysis (pascal.taie.analysis.pta)
analyze:64, PointerAnalysis (pascal.taie.analysis.pta)

upload successful
此刻unit为Soot的JAssignStmt，其apply会调用caseAssignStmt 接口

upload successful
lhs属于FieldRef，因此最终会将storeField stm添加在该Var IR的relevantStmts属性中。

0x03 PTA 数据结构

3.1 CSVar

CSVar 可以简单理解成PTA分析结果“指向关系图”中的变量/属性。
它是上下文敏感的Var，其中Var是Tai-e IR概念，其有以下字段

  • var: 对应的IR Var
  • context: 上下文
  • pointToSet: 指向的值的集合
  • index
  • successors
  • outEdges
  • filters
    upload successful

如上图，其中红框中的n1\n2等，就是CSVar。

在后文的重要结构workList。pointerEntries中，其key就大部分是CSVar

upload successful

3.2 PointToSet

PointToSet 是CSVar的可能值集合。CSVar中自带也有pointToSet属性。

它的Set的值是CSObj类型（堆敏感值，后续上下文敏感分析再细讲）。

upload successful
同样的，如上图，其中”{}”大括号内的就是PointToSet，比如o1、o2。

3.3 WorkList

WorkList 是在DefaultSolver中的重要变量，是整个指针分析的核心。

它内部存在着待分析的pointerEntries和callEdges，整个指针分析的核心逻辑就是从WorkList队列中出取值，进行处理，处理期间也可能会对WorkList进行入队列，直至WorkList 为空，停止分析。

3.3.1 pointerEntries

pointEntry 通常由一组（CSVar、PointToSet）组成，其入队列的api为

DefaultSolve#addPointsTo

1
2
3
4
@Override
public void addPointsTo(Pointer pointer, PointsToSet pts) {
    workList.addEntry(pointer, pts);
}

3.3.2 callEdges

在队列中具有高优先级，优先处理这一类元素。

同样的，其api为DefaultSolve#addCallEdge

1
2
3
4
@Override
public void addCallEdge(Edge<CSCallSite, CSMethod> edge) {
    workList.addEntry(edge);
}

0x04 PTA流程跟踪

PTA分析包装在PointerAnalysis（在pascal.taie.analysis.pta）， 我们从这里开始跟踪。

4.1 AnalysisManager

在进入PointerAnalysis 之前，还由AnalysisManager包了一层。我们在前文《Tai-e 初探》 中有提到Tai-e 有很多程序分析功能，PTA只是其中一个。

AnalysisManager 就是这一层的封装，对应的调用栈如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
analyze:64, PointerAnalysis (pascal.taie.analysis.pta)
runProgramAnalysis:148, AnalysisManager (pascal.taie.analysis)
runAnalysis:135, AnalysisManager (pascal.taie.analysis)
lambda$execute$0:104, AnalysisManager (pascal.taie.analysis)
get:-1, AnalysisManager$$Lambda$227/0x0000000800ea3010 (pascal.taie.analysis)
runAndCount:93, Timer (pascal.taie.util)
lambda$execute$1:103, AnalysisManager (pascal.taie.analysis)
accept:-1, AnalysisManager$$Lambda$226/0x0000000800ea2bb8 (pascal.taie.analysis)
forEach:1511, ArrayList (java.util)
execute:102, AnalysisManager (pascal.taie.analysis)
executePlan:152, Main (pascal.taie)
lambda$main$0:61, Main (pascal.taie)
run:-1, Main$$Lambda$109/0x0000000800d2b000 (pascal.taie)
lambda$runAndCount$0:112, Timer (pascal.taie.util)
get:-1, Timer$$Lambda$110/0x0000000800d2b458 (pascal.taie.util)
runAndCount:93, Timer (pascal.taie.util)
runAndCount:111, Timer (pascal.taie.util)
runAndCount:107, Timer (pascal.taie.util)
main:52, Main (pascal.taie)

4.2 PointerAnalysis

实际上PointerAnalysis 也只是一层包装，具体逻辑是在solver和plugin中实现的。

这里有几个变量涉及到前文中几个重要的概念

heapModel：堆模型，负责指针分析中的“值”处理，用以区分它们的上下文
selector：上下文选择器，用于区分“变量”的上下文
这两个都后续再深入研究探讨，这里简单介绍下它们的功能，了解接口即可。

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
31
32
33
34
35
36
37
38
public PointerAnalysisResult analyze() {
    AnalysisOptions options = getOptions();
    // 根据配置，生成heapModel 堆模型
    HeapModel heapModel = new AllocationSiteBasedModel(options);
    ContextSelector selector = null;
    String advanced = options.getString("advanced");
    // 根据配置中的cs字段，生成上下文管理器
    String cs = options.getString("cs");
    if (advanced != null) {
        if (advanced.equals("collection")) {
            selector = ContextSelectorFactory.makeSelectiveSelector(cs,
                    new CollectionMethods(World.get().getClassHierarchy()).get());
        } else {
            // run context-insensitive analysis as pre-analysis
            PointerAnalysisResult preResult = runAnalysis(heapModel,
                    ContextSelectorFactory.makeCISelector());
            if (advanced.startsWith("scaler")) {
                selector = Timer.runAndCount(() -> ContextSelectorFactory
                                .makeGuidedSelector(Scaler.run(preResult, advanced)),
                        "Scaler", Level.INFO);
            } else if (advanced.startsWith("zipper")) {
                selector = Timer.runAndCount(() -> ContextSelectorFactory
                                .makeSelectiveSelector(cs, Zipper.run(preResult, advanced)),
                        "Zipper", Level.INFO);
            } else if (advanced.equals("mahjong")) {
                heapModel = Timer.runAndCount(() -> Mahjong.run(preResult, options),
                        "Mahjong", Level.INFO);
            } else {
                throw new IllegalArgumentException(
                        "Illegal advanced analysis argument: " + advanced);
            }
        }
    }
    if (selector == null) {
        selector = ContextSelectorFactory.makePlainSelector(cs);
    }
    return runAnalysis(heapModel, selector);
}

4.3 DefaultSolver

PointerAnalysis.java

1
2
3
4
5
6
7
8
9
10
11
12
private PointerAnalysisResult runAnalysis(HeapModel heapModel,
                                          ContextSelector selector) {
    AnalysisOptions options = getOptions();
    Solver solver = new DefaultSolver(options,
            heapModel, selector, new MapBasedCSManager());
    // The initialization of some Plugins may read the fields in solver,
    // e.g., contextSelector or csManager, thus we initialize Plugins
    // after setting all other fields of solver.
    setPlugin(solver, options);
    solver.solve();
    return solver.getResult();
}

4.3.1 Fields

  • propTypes
  • workList: 前文提到的WorkList结构，是整个指针分析的重点
  • options: 用户配置
  • heapModel: 堆模型
  • contextSelector: 上下文选择器
  • csManager: 上下文管理的，整个指针分析的结果
  • ptrManager: 指向关系
  • objManager: obj
  • mtdManager: method
  • callSites: call
  • hierarchy: 从World获取的类继承关系hierarchy = World.get().getClassHierarchy();
  • typeSystem: 从World获取的类型系统typeSystem = World.get().getTypeSystem();
  • ptsFactory
  • callGraph
  • pointerFlowGraph: 最终的PFG，其实最终还是放在csManager。

caManager只见get不见add/set

csManager中的几个feild是如何add值的？

1
2
3
4
private CSVar getCSVar(Context context, Var var) {
    return vars.computeIfAbsent(var, context,
            (v, c) -> new CSVar(v, c, counter++));
}

答案是用了computeIfAbsent，不存在则添加。

其他一些类似结构也都是如此处理的。

4.3.2 API

workList相关

其实前文也提到了两个关于workList的API

  • addPointsTo(Pointer pointer, PointsToSet pts)：增加待处理的指向关系

  • addCallEdge(Edge<CSCallSite, CSMethod> edge)：增加待处理的call调用关系
    还有一些派生的添加WorkList的API

  • addPointsTo(Pointer pointer, Context heapContext, Obj obj)

  • addVarPointsTo(Context context, Var var, PointsToSet pts)

  • addVarPointsTo(Context context, Var var, CSObj csObj)

  • addVarPointsTo(Context context, Var var, Context heapContext, Obj obj)
    其最终都是调用的addPointsTo(Pointer pointer, PointsToSet pts)向workList 中增加pointerEntry。

除此还有一些重点的API，一一讲解下

addEntryPoint(EntryPoint entryPoint)

EntryPoint是入口函数，一般是Main方法，Tai-e内置了一些隐式入口，比如Thread#run等，具体逻辑在EntryPointHandler plugin插件中。

addEntryPoint提供了统一的分析入口API，指针分析从此开始。

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
31
32
33
34
35
36
37
38
39
40
public void addEntryPoint(EntryPoint entryPoint) {
	// 空上下文
    Context entryCtx = contextSelector.getEmptyContext();
    // 入口函数，IR格式
    JMethod entryMethod = entryPoint.getMethod();
    // 组合成上下文方法
    CSMethod csEntryMethod = csManager.getCSMethod(entryCtx, entryMethod);
    // callGraph 添加
    callGraph.addEntryMethod(csEntryMethod);
    // 触发所有插件的新增CSMethod逻辑，具体逻辑看插件的处理
    // 注意这里会触发StmtProcessor，后文再讲
    addCSMethod(csEntryMethod);
    // 获取IR
    IR ir = entryMethod.getIR();
    // pass this objects
    if (!entryMethod.isStatic()) {
    	// 针对目前的entryPoint，获取this obj
        for (Obj thisObj : entryPoint.getThisObjs()) {
        	// 在workList中添加一条待处理的pointEntry
            // 其中Var为entryCtx和ir组合
            // Obj为entryCtx和this obj
            addVarPointsTo(entryCtx, ir.getThis(), entryCtx, thisObj);
        }
    }
    // 处理参数
    // pass parameter objects
    for (int i = 0; i < entryMethod.getParamCount(); ++i) {
        Var param = ir.getParam(i);
        // 判断是否是是配置的IR类型，比如
        // null，默认false
        // reference（ArrayType/ClassType），默认true
        // 内置primitiveType白名单
        if (propTypes.isAllowed(param)) {
        	// 每一个参数param及paramObj，放入WorkList队列中
            for (Obj paramObj : entryPoint.getParamObjs(i)) {
                addVarPointsTo(entryCtx, param, entryCtx, paramObj);
            }
        }
    }
}

疑问：以上只见到了this、param 添加到workList，里面的各个IR呢？后文StmtProcessor详细解读

propagate(Pointer pointer, PointsToSet pointsToSet)

功能：目的是将Pointer内原有的pointsToSet和新的pointsToSet整合。

先看参数Pointer，他是个接口，有以下的一些实现：

  • AbstractPointer
  • CSVar
  • ArrayIndex
  • InstanceField
  • StaticField
    其中AbstractPointer是抽象实现，其他是个是指针分析最终要求解的结果中的“Variable/Field”
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    private PointsToSet propagate(Pointer pointer, PointsToSet pointsToSet) {
        logger.trace("Propagate {} to {}", pointsToSet, pointer);
        // 先取出原pointer的filter
        Set<Predicate<CSObj>> filters = pointer.getFilters();
        if (!filters.isEmpty()) {
        	// 待处理的pointsToSet先过一遍filter，组合成新的pointsToSet
            // apply filters (of the pointer) on pointsToSet
            pointsToSet = pointsToSet.objects()
                    .filter(o -> filters.stream().allMatch(f -> f.test(o)))
                    .collect(ptsFactory::make, PointsToSet::addObject, PointsToSet::addAll);
        }
        // 原pointer的pointsToSet添加上所有新的符合filter的pointsToSet
        PointsToSet diff = getPointsToSetOf(pointer).addAllDiff(pointsToSet);
        // TODO：待添加分析
        if (!diff.isEmpty()) {
            pointerFlowGraph.getOutEdgesOf(pointer).forEach(edge -> {
                Pointer target = edge.target();
                edge.getTransfers().forEach(transfer ->
                        addPointsTo(target, transfer.apply(edge, diff)));
            });
        }
        return diff;
    }

    TODO: 边的处理待解释，猜测如果是有指向关系，那么把也要把新的pts合并过去。

analyze

analyze是整个Solver的核心逻辑，围绕workList，从中取值并处理，直至为空，整个指针分析过程完毕。

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 void analyze() {
    while (!workList.isEmpty() && !isTimeout) {
        WorkList.Entry entry = workList.pollEntry();
        if (entry instanceof WorkList.PointerEntry pEntry) {
            Pointer p = pEntry.pointer();
            PointsToSet pts = pEntry.pointsToSet();
            PointsToSet diff = propagate(p, pts);
            if (!diff.isEmpty() && p instanceof CSVar v) {
            	// 处理InstanceStore
                processInstanceStore(v, diff);
                processInstanceLoad(v, diff);
                processArrayStore(v, diff);
                processArrayLoad(v, diff);
                processCall(v, diff);
                plugin.onNewPointsToSet(v, diff);
            }
        } else if (entry instanceof WorkList.CallEdgeEntry eEntry) {
            processCallEdge(eEntry.edge());
        }
    }
    if (!workList.isEmpty() && isTimeout) {
        logger.warn("Pointer analysis stops early as it reaches time limit ({} seconds)," +
                " and the result may be unsound!", timeLimit);
    } else if (timeLimiter != null) { // finish normally but time limiter is still running
        timeLimiter.stop();
    }
    plugin.onFinish();
}

其中有涉及到几种类型的处理

  • PointerEntry
  • InstanceStore
  • InstanceLoad
  • ArrayStore
  • ArrayLoad
  • Call
  • CallEdgeEntry
  • CallEdge

processInstanceStore(CSVar baseVar, PointsToSet pts)

疑问：是指的课件中的存储吗？

upload successful

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private void processInstanceStore(CSVar baseVar, PointsToSet pts) {
    Context context = baseVar.getContext();
    Var var = baseVar.getVar();
    // 获取Var中的StoreField，参考前文Var结构一节
    for (StoreField store : var.getStoreFields()) {
    	// 右侧的Var
        Var fromVar = store.getRValue();
        if (propTypes.isAllowed(fromVar)) {
            CSVar from = csManager.getCSVar(context, fromVar);
            // 获取filed
            JField field = store.getFieldRef().resolve();
            // pts每一个Obj
            pts.forEach(baseObj -> {
            	// 
                if (baseObj.getObject().isFunctional()) {
                	// 获取其对应的field
                    InstanceField instField = csManager.getInstanceField(baseObj, field);
                    // 如课件图，在最终的PFG图中，增加一条oi->oj的边
                    addPFGEdge(from, instField, FlowKind.INSTANCE_STORE);
                }
            });
        }
    }
}

疑问：途中是oi->oj，这里实际是Pointer->Pointer(CSVar->InstanceField)。

顺带看看addPFGEdge(Pointer source, Pointer target, FlowKind kind,Transfer transfer)

addPFGEdge(Pointer source, Pointer target, FlowKind kind,Transfer transfer)

1
2
3
4
5
6
7
8
9
10
11
12
13
public void addPFGEdge(Pointer source, Pointer target, FlowKind kind,
                       Transfer transfer) {
    // source的边Edge添加一条边
    PointerFlowEdge edge = pointerFlowGraph.getOrAddEdge(kind, source, target);
    if (edge != null && edge.addTransfer(transfer)) {
    	// 获取source原本的pts
        PointsToSet targetSet = transfer.apply(edge, getPointsToSetOf(source));
        if (!targetSet.isEmpty()) {
        	// 添加到workList中
            addPointsTo(target, targetSet);
        }
    }
}

注意：可以看出，addPFGEdge不只是增加一条边，还有把原来的source pts整合进target中，不需要再单独的addPointsTo。

1
2
3
4
public PointerFlowEdge getOrAddEdge(FlowKind kind, Pointer source, Pointer target) {
	// Var中添加一条边
    return source.getOrAddEdge(kind, source, target);
}

AbstractPointer.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public PointerFlowEdge getOrAddEdge(FlowKind kind, Pointer source, Pointer target) {
    if (successors.add(target)) {
        PointerFlowEdge edge = new PointerFlowEdge(kind, source, target);
        outEdges.add(edge);
        return edge;
    } else if (kind == FlowKind.OTHER) {
        for (PointerFlowEdge edge : outEdges) {
            if (edge.target().equals(target)) {
                return edge;
            }
        }
    }
    return null;
}
  • successors 添加target
  • outEdges 添加一条到target的边

processInstanceLoad(CSVar baseVar, PointsToSet pts)

upload successful

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void processInstanceLoad(CSVar baseVar, PointsToSet pts) {
    Context context = baseVar.getContext();
    Var var = baseVar.getVar();
    for (LoadField load : var.getLoadFields()) {
        Var toVar = load.getLValue();
        if (propTypes.isAllowed(toVar)) {
            CSVar to = csManager.getCSVar(context, toVar);
            JField field = load.getFieldRef().resolve();
            pts.forEach(baseObj -> {
                if (baseObj.getObject().isFunctional()) {
                    InstanceField instField = csManager.getInstanceField(baseObj, field);
                    addPFGEdge(instField, to, FlowKind.INSTANCE_LOAD);
                }
            });
        }
    }
}

类似的逻辑，不赘述

upload successful

processArrayStore(CSVar arrayVar, PointsToSet pts)

ArrayStore 与FieldStore类似

  • store field: v.f = x;

  • store array: v[i] = x;

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    private void processArrayStore(CSVar arrayVar, PointsToSet pts) {
        Context context = arrayVar.getContext();
        Var var = arrayVar.getVar();
        for (StoreArray store : var.getStoreArrays()) {
            Var rvalue = store.getRValue();
            if (propTypes.isAllowed(rvalue)) {
                CSVar from = csManager.getCSVar(context, rvalue);
                pts.forEach(array -> {
                    if (array.getObject().isFunctional()) {
                        ArrayIndex arrayIndex = csManager.getArrayIndex(array);
                        // we need type guard for array stores as Java arrays
                        // are covariant
                        addPFGEdge(from, arrayIndex,
                                FlowKind.ARRAY_STORE, arrayIndex.getType());
                    }
                });
            }
        }
    }

    upload successful

  • 注意$r5原本的pts，是个newarray

  • $r5[%intconst0] = %classconst2

那么同样还是store的逻辑

  • from 是 %classconst2
  • target 是$r5[%intconst0]

    注：原课件中只有考虑InstanceField的情况，并没有考虑Array[i]元素，大同小异。
    疑问：除了Array还有Map、Collection之类的基础结构，Array支持吗？

processArrayLoad(CSVar arrayVar, PointsToSet pts)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private void processArrayLoad(CSVar arrayVar, PointsToSet pts) {
    Context context = arrayVar.getContext();
    Var var = arrayVar.getVar();
    for (LoadArray load : var.getLoadArrays()) {
        Var lvalue = load.getLValue();
        if (propTypes.isAllowed(lvalue)) {
            CSVar to = csManager.getCSVar(context, lvalue);
            pts.forEach(array -> {
                if (array.getObject().isFunctional()) {
                    ArrayIndex arrayIndex = csManager.getArrayIndex(array);
                    addPFGEdge(arrayIndex, to, FlowKind.ARRAY_LOAD);
                }
            });
        }
    }
}

upload successful

同样的，对于r1 = r0[%intconst0]

  • from 是r0[%intconst0]
  • target 是r1

processCall(CSVar recv, PointsToSet pts)

upload successful

Call过程是最复杂的，以示例代码中的tt为例

1
2
3
4
5
6
7
8
9
10
11
String content = args[0];
String methodNmae = args[1];
InvokeDemo tt = new InvokeDemo(content);
// 1. 测试污点为参数
Method method = tt.getClass().getMethod("echo", String.class);
method.invoke(tt, content);

// 2. 测试污点为method
Method method2 = tt.getClass().getMethod(methodNmae);
method2.invoke(tt);
upload successful

和它相关的有三个invoke。

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
31
32
33
34
35
private void processCall(CSVar recv, PointsToSet pts) {
    Context context = recv.getContext();
    Var var = recv.getVar();
    for (Invoke callSite : var.getInvokes()) {
        pts.forEach(recvObj -> {
            // resolve callee
            // 获取method
            JMethod callee = CallGraphs.resolveCallee(
                    recvObj.getObject().getType(), callSite);
            if (callee != null) {
                // select context
                // 获取method上下文
                // 注意这里method上下文的获取方式，后续上下文敏感再详细跟踪
                CSCallSite csCallSite = csManager.getCSCallSite(context, callSite);
                Context calleeContext = contextSelector.selectContext(
                        csCallSite, recvObj, callee);
                // build call edge
                CSMethod csCallee = csManager.getCSMethod(calleeContext, callee);
                // 增加一条CallEdge，放入WorkList
                addCallEdge(new Edge<>(CallGraphs.getCallKind(callSite),
                        csCallSite, csCallee));
                // pass receiver object to *this* variable
                // 
                if (!isIgnored(callee)) {
                	// 这个逻辑还是比较简单的，没有想象中复杂
                    // 就是将method里面的this，指向调用者原本的pts
                    addVarPointsTo(calleeContext, callee.getIR().getThis(),
                            recvObj);
                }
            } else {
                plugin.onUnresolvedCall(recvObj, context, callSite);
            }
        });
    }
}

详细看看isIgnored逻辑

1
2
3
4
private boolean isIgnored(JMethod method) {
    return ignoredMethods.contains(method) ||
            onlyApp && !method.isApplication();
}

upload successful

  • 内置黑名单
  • 如果配置了onlyApp参数，那么只分析app内部代码，不分析考虑jdk等代码

如果不涉及native代码，onlyApp=false，那么可以分析出jdk内部的传播（CodeQL是不会去分析jdk代码的，因此需要自己完善jdk里面的污点传播关系）

  1. addCallEdge
    upload successful
  2. addVarPointsTo
    upload successful

疑问：这些个workList pointerEntry 是哪里添加的？尤其这个invoke类型

综合来讲，processCall只是添加了一个函数内部this->obj的workList.pointerEntry，更复杂的在processCallEdge。

addCSMethod(CSMethod csMethod)

答案是在前文提到的addEntryPoint中，有一步是addCSMethod(csEntryMethod)，最终会执行stmtProcessor.process(csMethod, stmts);

1
2
3
4
5
6
7
8
9
10
11
12
public void addCSMethod(CSMethod csMethod) {
    if (callGraph.addReachableMethod(csMethod)) {
        // process new reachable context-sensitive method
        JMethod method = csMethod.getMethod();
        if (isIgnored(method)) {
            return;
        }
        processNewMethod(method);
        addStmts(csMethod, method.getIR().getStmts());
        plugin.onNewCSMethod(csMethod);
    }
}
1
2
3
public void addStmts(CSMethod csMethod, Collection<Stmt> stmts) {
    stmtProcessor.process(csMethod, stmts);
}

详细逻辑下面StmtProcess讲，堆栈如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
addPointsTo:734, DefaultSolver (pascal.taie.analysis.pta.core.solver)
addPointsTo:741, DefaultSolver (pascal.taie.analysis.pta.core.solver)
addPointsTo:746, DefaultSolver (pascal.taie.analysis.pta.core.solver)
addVarPointsTo:761, DefaultSolver (pascal.taie.analysis.pta.core.solver)
visit:587, DefaultSolver$StmtProcessor$Visitor (pascal.taie.analysis.pta.core.solver)
visit:570, DefaultSolver$StmtProcessor$Visitor (pascal.taie.analysis.pta.core.solver)
accept:55, New (pascal.taie.ir.stmt)
lambda$process$0:564, DefaultSolver$StmtProcessor (pascal.taie.analysis.pta.core.solver)
accept:-1, DefaultSolver$StmtProcessor$$Lambda$324/0x0000000800ef54e0 (pascal.taie.analysis.pta.core.solver)
forEach:75, Iterable (java.lang)
process:564, DefaultSolver$StmtProcessor (pascal.taie.analysis.pta.core.solver)
addStmts:827, DefaultSolver (pascal.taie.analysis.pta.core.solver)
addCSMethod:820, DefaultSolver (pascal.taie.analysis.pta.core.solver)
addEntryPoint:787, DefaultSolver (pascal.taie.analysis.pta.core.solver)
onStart:59, EntryPointHandler (pascal.taie.analysis.pta.plugin)

4.4 StmtProcess

背景是addEntryPoint->addCSMethod，简单来讲addCSMethod中有一步就是解析所有的子IR，放入workList。

其中用到了StmtProcess$Vistor，它针对不同的stmt IR，有不同的Visit接口

  • New
  • Copy
  • Cast
  • LoadField
  • StoreField
  • Invoke

upload successful

注：这个PFG边的逻辑才是Tai-e中实现的，还有一种图示，是oi->oj的指向。

4.1 Visitor API

visit(New stmt)

New 类型逻辑是简单的，添加workList pointerEntry

  • var 为stmt的左值
  • obj 比较复杂，因为是new 了一个新的对象，因此需要根据该对象的类型，生成一个obj
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    public Void visit(New stmt) {
        // obtain context-sensitive heap object
        NewExp rvalue = stmt.getRValue();
        // 重点：从stmt生成Obj
        // 新生成的obj，也会被放在heapModel中
        Obj obj = heapModel.getObj(stmt);
        Context heapContext = contextSelector.selectHeapContext(csMethod, obj);
        // 添加workList
        addVarPointsTo(context, stmt.getLValue(), heapContext, obj);
        // 如果右边的值是一个Array类型，会进一步处理Array相关
        if (rvalue instanceof NewMultiArray) {
            processNewMultiArray(stmt, heapContext, obj);
        }
        // 如果是Finalize，再说
        if (hasOverriddenFinalize(rvalue)) {
            processFinalizer(stmt);
        }
        return null;
    }
    根据stmt生成obj的具体逻辑如下（部分逻辑可以在options中配置）

AbstractHeapModel

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public Obj getObj(New allocSite) {
    Type type = allocSite.getRValue().getType();
    if (isMergeStringObjects && type.equals(string)) {
        return getMergedObj(allocSite);
    }
    if (isMergeStringBuilders &&
            (type.equals(stringBuilder) || type.equals(stringBuffer))) {
        return getMergedObj(allocSite);
    }
    if (isMergeExceptionObjects && typeSystem.isSubtype(throwable, type)) {
        return getMergedObj(allocSite);
    }
    return doGetObj(allocSite);
}

AllocationSiteBasedModel

1
2
3
protected Obj doGetObj(New allocSite) {
    return getNewObj(allocSite);
}

AbstractHeapModel

1
2
3
4
protected NewObj getNewObj(New allocSite) {
    return newObjs.computeIfAbsent(allocSite,
            site -> add(new NewObj(site)));
}
1
2
3
4
5
protected <T extends Obj> T add(T obj) {
    objs.add(obj);
    obj.setIndex(counter++);
    return obj;
}
1
2
3
NewObj(New allocSite) {
    this.allocSite = allocSite;
}

Demo:
stmt: $r3 = new InvokeDemo

upload successful
注意：此处新生成的obj，已经被放置在heapModel中了

TODO: 未深入跟踪Array的处理和Finalize的处理，有空再做

visit(Copy stmt)

upload successful

copy最简单，只需要

增加一条PFG边（addPFGEdge 会间接调用addPointsTo）

1
2
3
4
5
6
7
8
9
public Void visit(Copy stmt) {
    Var rvalue = stmt.getRValue();
    if (propTypes.isAllowed(rvalue)) {
        CSVar from = csManager.getCSVar(context, rvalue);
        CSVar to = csManager.getCSVar(context, stmt.getLValue());
        addPFGEdge(from, to, FlowKind.LOCAL_ASSIGN);
    }
    return null;
}

visit(LoadField stmt)

upload successful

同样的，增加一条PFG边

1
2
3
4
5
6
7
8
9
public Void visit(LoadField stmt) {
    if (stmt.isStatic() && propTypes.isAllowed(stmt.getRValue())) {
        JField field = stmt.getFieldRef().resolve();
        StaticField sfield = csManager.getStaticField(field);
        CSVar to = csManager.getCSVar(context, stmt.getLValue());
        addPFGEdge(sfield, to, FlowKind.STATIC_LOAD);
    }
    return null;
}

visit(StoreField stmt)

upload successful

同样的，增加一条PFG边

1
2
3
4
5
6
7
8
9
public Void visit(StoreField stmt) {
    if (stmt.isStatic() && propTypes.isAllowed(stmt.getRValue())) {
        JField field = stmt.getFieldRef().resolve();
        StaticField sfield = csManager.getStaticField(field);
        CSVar from = csManager.getCSVar(context, stmt.getRValue());
        addPFGEdge(from, sfield, FlowKind.STATIC_STORE);
    }
    return null;
}

visit(Invoke stmt)

upload successful

1
2
3
4
5
6
public Void visit(Invoke stmt) {
    if (stmt.isStatic()) {
        processInvokeStatic(stmt);
    }
    return null;
}
1
2
3
4
5
6
7
8
9
10
private void processInvokeStatic(Invoke callSite) {
    JMethod callee = CallGraphs.resolveCallee(null, callSite);
    if (callee != null) {
        CSCallSite csCallSite = csManager.getCSCallSite(context, callSite);
        Context calleeCtx = contextSelector.selectContext(csCallSite, callee);
        CSMethod csCallee = csManager.getCSMethod(calleeCtx, callee);
        // 增加一条调用边，交由processCallEdge去处理
        addCallEdge(new Edge<>(CallKind.STATIC, csCallSite, csCallee));
    }
}

出乎意料的是，只处理了InvokeStatic 静态方法。
实际上addCSMethod 知识被当作Method的初始化处理，复杂的都是交由DefaultSolver#processxxx 去处理。调用属于最复杂的。

4.5 DefaultSolver

和4.3相同，不过因为重要解释StmtProcessor的需要

4.3.1 API

接原4.3.1

processCallEdge

upload successful

processCallEdge

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
31
32
33
34
35
36
37
38
39
40
41
42
private void processCallEdge(Edge<CSCallSite, CSMethod> edge) {
	// callGraph 添加调用
    if (callGraph.addEdge(edge)) {
        // process new call edge
        CSMethod csCallee = edge.getCallee();
        // addCSMethod 分析被调用的Method
        addCSMethod(csCallee);
        if (edge.getKind() != CallKind.OTHER
                && !isIgnored(csCallee.getMethod())) {
            Context callerCtx = edge.getCallSite().getContext();
            Invoke callSite = edge.getCallSite().getCallSite();
            Context calleeCtx = csCallee.getContext();
            JMethod callee = csCallee.getMethod();
            InvokeExp invokeExp = callSite.getInvokeExp();
            // pass arguments to parameters
            for (int i = 0; i < invokeExp.getArgCount(); ++i) {
                Var arg = invokeExp.getArg(i);
                if (propTypes.isAllowed(arg)) {
                    Var param = callee.getIR().getParam(i);
                    CSVar argVar = csManager.getCSVar(callerCtx, arg);
                    CSVar paramVar = csManager.getCSVar(calleeCtx, param);
                    // 对于每一个参数
                    // 增加一条调用者参数到method参数的PFG边
                    addPFGEdge(argVar, paramVar, FlowKind.PARAMETER_PASSING);
                }
            }
            // pass results to LHS variable
            Var lhs = callSite.getResult();
            if (lhs != null && propTypes.isAllowed(lhs)) {
                CSVar csLHS = csManager.getCSVar(callerCtx, lhs);
                for (Var ret : callee.getIR().getReturnVars()) {
                    if (propTypes.isAllowed(ret)) {
                        CSVar csRet = csManager.getCSVar(calleeCtx, ret);
                        // 结果和调用callsite左值关联，添加一条PFG边
                        addPFGEdge(csRet, csLHS, FlowKind.RETURN);
                    }
                }
            }
        }
        plugin.onNewCallEdge(edge);
    }
}

4.5 CompositePlugin

以上只是最基础的指针分析的流程，污点分析、反射分析，这些都是通过插件实现的，在pta.plugin下面

  • exception
  • invokedynamic
  • natives
  • reflection
  • taint
    这些以后再单独的详细分析吧。

0x5 参考

  1. 6 指针分析-引入
  2. 通过实例一行一行分析JVM的invokespecial和invokevirtual指令
  3. Java 指针分析综述

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true