软件分析基础知识&作业

之前翔哥给我具体讲了讲软件分析的基础知识，翔哥的链接如下所示：

0x00 tai-e基本知识

Tai-e 是一个分析 Java 程序的静态程序分析框架，相比于已有的知名静态程序分析框架（如 Soot、Wala 等），Tai-e 要易学易用。Tai-e分为教学版/科研版，它们在分析能力和性能上有较大差距。

作业涵盖多种静态分析技术，包括编译优化（活跃变量分析、常量传播分析、死代码检测），基础程序分析（程序调用图构建、非上下文敏感指针/别名分析、各类经典上下文敏感指针/别名分析），以及程序分析在软件安全性的应用（污点分析）。

tai-e 利用 Soot 前端解析 Java 程序并帮助构建 Tai-e IR。Soot 有两个前端，分别处理 Java 源代码文件（.java）和字节码文件（.class）。其中，前者可以将源代码中的变量名保留至 IR 中，从而使得生成的 IR 更贴近源码，比后者的更易于理解，即tai-e可以输入java源代码文件或者字节码文件，都可以输出IR，但是输入java源代码文件更好。

实验作业中，待分析的程序都以 Java 源文件的格式提供。然而，Soot 的 Java 源文件前端已经过时（最高 Java 7 版本）且不够健壮。Soot 的字节码文件前端更加健壮（最高 Java 17 版本编译生成的 .class 文件）。分析真实世界的程序时，往往使用字节码。

0x01 活跃变量分析与迭代求解器

活跃变量分析基本原理

见Link。

代码相关的知识点

pascal.taie.analysis.dataflow.analysis.DataflowAnalysis

抽象的数据流分析类，是具体的数据流分析与求解器之间的接口，即具体的数据流分析（如活跃变量分析）需要实现它的接口，而求解器（如迭代求解器）需要通过它的接口来求解数据流。分析方向、边界条件、初始条件、meet 操作、transfer 函数。

pascal.taie.ir.exp.Exp

表示程序中的所有表达式。它含有很多子类，对应各类具体的表达式。在 Tai-e 的 IR 中，把表达式分为两类：LValue 和 RValue。有些表达式既可用于左值，也可用于右值，就比如Var。

pascal.taie.ir.stmt.Stmt

表示程序中的所有语句。每个表达式都属于某条特定的语句。每条语句至多只可能定义一个变量、而可能使用零或多个变量。

pascal.taie.analysis.dataflow.fact.SetFact<Var>

此泛型类用于把 data fact 组织成一个集合。它提供了各种集合操作，如添加、删除元素，取交集、并集等。data fact就是每一个basic block的输入，例如活跃变量分析，需要用0/1代表某变量是否是活跃的。

pascal.taie.analysis.dataflow.fact.DataflowResult

维护数据流分析的 CFG 中的 fact，可以通过它的 API 获取、设置 CFG 节点的 IN facts 和 OUT facts。

pascal.taie.analysis.graph.cfg.CFG

表示程序中方法的控制流图（control-flow graphs）。可以通过一个for循环遍历其中的所有节点。

pascal.taie.analysis.dataflow.solver.Solver

这是数据流分析求解器的基类，包含了求解器的抽象功能。Tai-e 会构建待分析程序的 CFG 并传给 Solver.solve(CFG)，这个类中有两组initialize/doSolve方法，分别处理前向和后向的数据流分析。

作业代码

// LiveVariableAnalysis.java
@Override
public SetFact<Var> newBoundaryFact(CFG<Stmt> cfg) {
    return new SetFact<Var>();
}

@Override
public SetFact<Var> newInitialFact() {
    return new SetFact<Var>();
}

@Override
public void meetInto(SetFact<Var> fact, SetFact<Var> target) {
    if (!fact.isEmpty())
        target.union(fact);
}

@Override
public boolean transferNode(Stmt stmt, SetFact<Var> in, SetFact<Var> out) {
    Optional<LValue> def = stmt.getDef();
    SetFact<Var> result = new SetFact<Var>();
    Collection<RValue> use = stmt.getUses();

    SetFact<Var> left = new SetFact<Var>();
    SetFact<Var> right = new SetFact<Var>();

    for (RValue u: use) {
        if (u instanceof Var)
            left.add((Var)u);
    }
    if (!out.isEmpty()) {
        right = out.copy();
        if (def.isPresent()) {
            LValue tmp = def.get();
            if (tmp instanceof Var)
                right.remove((Var)tmp);
        }
    }
    result.union(left);
    result.union(right);

    if (result.equals(in)) {
        return false;
    }
    else {
        in.set(result);
        return true;
    }
}

// Solver.java
protected void initializeBackward(CFG<Node> cfg, DataflowResult<Node, Fact> result) {
    Node exit = cfg.getExit();
    result.setInFact(exit, analysis.newBoundaryFact(cfg));

    for (Node n: cfg) {
        result.setInFact(n, analysis.newInitialFact());
        result.setOutFact(n, analysis.newInitialFact());
    }
}

// IterativeSolver.java
@Override
protected void doSolveBackward(CFG<Node> cfg, DataflowResult<Node, Fact> result) {
    boolean change = true;
    while (change) {
        change = false;
        for (Node n: cfg) {

            Fact fact = result.getOutFact(n);
            for (Node suc: cfg.getSuccsOf(n)) {
                Fact tmp = result.getInFact(suc);
                analysis.meetInto(tmp, fact);
            }
            result.setOutFact(n, fact);

            Fact in_fact = result.getInFact(n);
            Fact out_fact = result.getOutFact(n);
            boolean tmp = analysis.transferNode(n, in_fact, out_fact);

            if (tmp)
                change = true;
        }
    }
}

0x02 常量传播和 Worklist 求解器

常量传播基本原理

程序的P点有一个变量x，判断在P点是否可以保证x是一个常量。

Iterative Algorithm都是前驱的block先merge完，再将结果输入到后面的block。而Worklist Algorithm是先把前驱block的输出输入到要分析的block，然后将要分析的block的输出统一merge。如下图所示，Worklist Algorithm更准：

上一段话纯属一派胡言，经过查证，Worklist Algorithm与Iterative Algorithm与如何merge无关。从下面的算法流程图来看，上图的差异应该体现在$\mathrm{IN}[B]=\bigsqcup_{P\text{ a predecessor of }B}\mathsf{OUT}[P]$这一步，如果是$\operatorname{F}(X\cap Y)$，那么$\mathrm{IN}[B]$应该是${(a,NAC),(b,NAC)}$；如果是$\mathrm{F}({X})\cap\mathrm{F}({Y})$，那么$\mathrm{IN}[B]$应该是${(a,1),(a,9),(b,1),(b,9)}$；

如果使用Iterative Algorithm分析常量传播，那么转换函数以及相应标注如下：

最终的算法结构如下（与活跃变量分析不同）：

此算法不好的点是：如果有任意OUT变化了，所有的block都要重新计算。而对应的Worklist Algorithm为：

为什么活跃变量分析是backward的，而常量分析是forward的呢？

在某个点的变量是否活跃，是由后面的程序决定的。而在某个点的定义是否是常量，是由前面的程序决定的。

May Analysis 与 Must Analysis

May Analysis的初始fact为0，最终找出有哪些不是0的fact。例如Reaching Definitions Analysis，其意思是：假设有程序点p与q，在p点定义了变量x，且从p到q之间没有再定义x，那么说x的定值到达了p在此环境下，fact=0代表不可到达，fact=1代表可到达，我们想找不可达的，这样的话就可以把对应的语句删掉。May Analysis，程序满足一条路径即可。

Must Analysis的初始fact为1，最终找出不是1的fact。例如Constant Propagation，其意思是：有程序点p与q，在q点定义了变量x，在q点使用了变量x，q点之前，再没有分支重新定义变量x，那么fact=1代表可常量传播，fact=0代表不可常量传播，我们想找可常量传播的，这样的话就可以传播常量。Must Analysis，程序必须满足所有路径。

代码相关的知识点

由于在java中，boolean/byte/char/short等类型在运行时都以int的形式进行计算，因此实现int类型的常量传播即可。其他的数据类型可以忽略。

只需要关注以下3种语句：（1）常量，x=1；（2）变量，x=y；（3）二元运算表达式，x=a+b或者x=a>>b等等。其中二元运算如下：

对于逻辑运算符（与或），请详细看作业中的描述，就是将逻辑运算符转为语义等价的语句，并且进行处理。对于方法调用，字段load而言，进行保守的近似处理，即当作x=NAC。对于字段存储等其他语句而言，只需要使用恒等函数作为transfer函数即可。

pascal.taie.ir.IR。

每个实例存储了一个java方法的各种信息，例如变量、参数、语句。

pascal.taie.ir.exp.Exp。

其有很多子类，其中pascal.taie.ir.exp.Var代表IR中的变量，pascal.taie.ir.exp.IntLiteral代表程序中的整数常量。pascal.taie.ir.exp.BinaryExp代表程序中的二元表达式，它有很多子类，每个子类代表上表中支持的运算符，且BinaryExp 的两个操作数都是 Var 类型的。

pascal.taie.ir.stmt.DefinitionStmt。

stmt的子类，表示程序中所有赋值语句。

pascal.taie.analysis.dataflow.analysis.DataflowAnalysis。

其中有具体数据流分析算法需要实现的接口，会被求解器调用。

pascal.taie.analysis.dataflow.analysis.constprop.Value。

分析格上的抽象值，例如getNAC()返回 NAC，getUndef() 返回UNDEF，makeConstant(int)返回给定整数在格上对应的抽象值。

pascal.taie.analysis.dataflow.analysis.constprop.CPFact。

表示常量传播中的 data facts，即一个从变量（Var）到格上抽象值（Value）的映射。

pascal.taie.analysis.dataflow.analysis.constprop.ConstantPropagation。

实现了 DataflowAnalysis。

作业代码

// solver.java
protected void initializeForward(CFG<Node> cfg, DataflowResult<Node, Fact> result) {
    Node entry = cfg.getEntry();
    Fact cp_fact = analysis.newBoundaryFact(cfg);
    // inFact and outFact all need set
    result.setOutFact(entry, cp_fact);
    result.setInFact(entry, cp_fact);

    for (Node n: cfg) {
        if (!cfg.isEntry(n)) {
            result.setInFact(n, analysis.newInitialFact());
            result.setOutFact(n, analysis.newInitialFact());
        }
    }
}

// WorkListSolver.java
@Override
protected void doSolveForward(CFG<Node> cfg, DataflowResult<Node, Fact> result) {
    Queue<Node> queue = new LinkedList<>();

    for (Node n: cfg)
        queue.offer(n);

    while (!queue.isEmpty()) {
        boolean changed = false;
        // pick basic block B from Worklist
        Node cur = queue.poll();
        // IN[B] = UNION(OUT[P])
        Fact fact = result.getInFact(cur);
        for (Node pred: cfg.getPredsOf(cur)) {
            Fact tmp = result.getOutFact(pred);
            analysis.meetInto(tmp, fact);
        }
        result.setInFact(cur, fact);
        // OUT[B] = genB UNION (IN[B]-killB)
        Fact in_fact = result.getInFact(cur);
        Fact out_fact = result.getOutFact(cur);
        changed = analysis.transferNode(cur, in_fact, out_fact);

        if (changed)
            for (Node succ: cfg.getSuccsOf(cur))
                if (!queue.contains(succ))
                    queue.offer(succ);
    }

}

// ConstantPropagation.java
@Override
public CPFact newBoundaryFact(CFG<Stmt> cfg) {
    // point to function args
    List<Var> vs = cfg.getIR().getParams();
    CPFact cp_fact = new CPFact();
    for (Var v: vs) {
        if(canHoldInt(v)) {
            cp_fact.update(v, Value.getNAC());
        }
    }
    return cp_fact;
}

@Override
public CPFact newInitialFact() {
    return new CPFact();
}

@Override
public void meetInto(CPFact fact, CPFact target) {
    Set<Var> keyset = fact.keySet();
    if (!keyset.isEmpty()) {
        for (Var k: keyset) {
            Value v1 = fact.get(k);
            Value v2 = target.get(k);
            Value result = meetValue(v1, v2);
            target.update(k, result);
        }
    }
}

public Value meetValue(Value v1, Value v2) {
    if (v1.isNAC() || v2.isNAC())
        return Value.getNAC();
    else if (v2.isUndef())
        return v1;
    else if (v1.isUndef())
        return v2;
    else if (v1.isConstant() && v2.isConstant() && v1.getConstant() != v2.getConstant())
        return Value.getNAC();
    else if (v1.isConstant() && v2.isConstant() && v1.getConstant() == v2.getConstant())
        return v1;
    else
        return Value.getNAC();
}

@Override
public boolean transferNode(Stmt stmt, CPFact in, CPFact out) {
    // focus on definition (x = .. | x = m(..))
    if (stmt instanceof DefinitionStmt<?,?>) {
        LValue lv = ((DefinitionStmt<?, ?>) stmt).getLValue();
        RValue rv = ((DefinitionStmt<?, ?>) stmt).getRValue();
        if (lv instanceof Var && canHoldInt((Var)lv)){
            CPFact tf = in.copy();
            tf.update((Var)lv, evaluate(rv, in));
            return out.copyFrom(tf);
        }
    }
    return out.copyFrom(in);
}


public static Value evaluate(Exp exp, CPFact in) {
    Value v = null;
    if (exp instanceof IntLiteral) {
        // x = c
        v = Value.makeConstant(((IntLiteral) exp).getValue());
    } else if (exp instanceof Var) {
        // x = y
        v = in.get((Var) exp);
    } else if (exp instanceof BinaryExp) {
        // x = y op z
        if (exp instanceof ArithmeticExp) {
            // + - * / %
            Value left = in.get(((ArithmeticExp) exp).getOperand1());
            Value right = in.get(((ArithmeticExp) exp).getOperand2());
            ArithmeticExp.Op op = ((ArithmeticExp) exp).getOperator();
            if ((op == ArithmeticExp.Op.DIV || op == ArithmeticExp.Op.REM) && right.isConstant() && right.getConstant() == 0) {
                v = Value.getUndef();
            } else if (left.isConstant() && right.isConstant()) {
                if (op == ArithmeticExp.Op.ADD)
                    v = Value.makeConstant(left.getConstant() + right.getConstant());
                else if (op == ArithmeticExp.Op.SUB)
                    v = Value.makeConstant(left.getConstant() - right.getConstant());
                else if (op == ArithmeticExp.Op.MUL)
                    v = Value.makeConstant(left.getConstant() * right.getConstant());
                else if (op == ArithmeticExp.Op.DIV)
                    v = Value.makeConstant(left.getConstant() / right.getConstant());
                else
                    v = Value.makeConstant(left.getConstant() % right.getConstant());
            } else if (left.isNAC() || right.isNAC()) {
                v = Value.getNAC();
            } else {
                v = Value.getUndef();
            }
        } else if (exp instanceof ConditionExp) {
            // == != < > <= >=
            Value left = in.get(((ConditionExp) exp).getOperand1());
            Value right = in.get(((ConditionExp) exp).getOperand2());
            ConditionExp.Op op = ((ConditionExp) exp).getOperator();
            if (left.isConstant() && right.isConstant()) {
                if (op == ConditionExp.Op.EQ) {
                    if (left.getConstant() == right.getConstant())
                        v = Value.makeConstant(1);
                    else
                        v = Value.makeConstant(0);
                } else if (op == ConditionExp.Op.GE) {
                    if (left.getConstant() >= right.getConstant())
                        v = Value.makeConstant(1);
                    else
                        v = Value.makeConstant(0);
                } else if (op == ConditionExp.Op.LE) {
                    if (left.getConstant() <= right.getConstant())
                        v = Value.makeConstant(1);
                    else
                        v = Value.makeConstant(0);
                } else if (op == ConditionExp.Op.GT) {
                    if (left.getConstant() > right.getConstant())
                        v = Value.makeConstant(1);
                    else
                        v = Value.makeConstant(0);
                } else if (op == ConditionExp.Op.LT) {
                    if (left.getConstant() >= right.getConstant())
                        v = Value.makeConstant(1);
                    else
                        v = Value.makeConstant(0);
                } else if (op == ConditionExp.Op.NE) {
                    if (left.getConstant() != right.getConstant())
                        v = Value.makeConstant(1);
                    else
                        v = Value.makeConstant(0);
                }
            } else if (left.isNAC() || right.isNAC()) {
                v = Value.getNAC();
            } else {
                v = Value.getUndef();
            }
        } else if (exp instanceof ShiftExp) {
            // << >> >>>
            Value left = in.get(((ShiftExp) exp).getOperand1());
            Value right = in.get(((ShiftExp) exp).getOperand2());
            ShiftExp.Op op = ((ShiftExp) exp).getOperator();
            if (left.isConstant() && right.isConstant()) {
                if (op == ShiftExp.Op.SHL) {
                    v = Value.makeConstant(left.getConstant() << right.getConstant());
                } else if (op == ShiftExp.Op.SHR) {
                    v = Value.makeConstant(left.getConstant() >> right.getConstant());
                } else if (op == ShiftExp.Op.USHR) {
                    v = Value.makeConstant(left.getConstant() >>> right.getConstant());
                }
            } else if (left.isNAC() || right.isNAC()) {
                v = Value.getNAC();
            } else {
                v = Value.getUndef();
            }
        } else if (exp instanceof BitwiseExp) {
            // | & ^
            Value left = in.get(((BitwiseExp) exp).getOperand1());
            Value right = in.get(((BitwiseExp) exp).getOperand2());
            BitwiseExp.Op op = ((BitwiseExp) exp).getOperator();
            if (left.isConstant() && right.isConstant()) {
                if (op == BitwiseExp.Op.OR) {
                    v = Value.makeConstant(left.getConstant() | right.getConstant());
                } else if (op == BitwiseExp.Op.AND) {
                    v = Value.makeConstant(left.getConstant() & right.getConstant());
                } else if (op == BitwiseExp.Op.XOR) {
                    v = Value.makeConstant(left.getConstant() ^ right.getConstant());
                }
            } else if (left.isNAC() || right.isNAC()) {
                v = Value.getNAC();
            } else {
                v = Value.getUndef();
            }
        } else {
            System.out.println("unexpect BinaryExp");
            v = Value.getNAC();
        }
    } else {
        System.out.println("unexpect Type");
        v = Value.getNAC();
    }
    return v;
}

0x03 死代码检测

除去程序中的死代码，通过组合前两次作业的分析方法来检测死代码。死代码指的是程序中不会被执行的代码，或者执行结果永远不会被其他计算过程用到的代码。本次作业只关心两种死代码：不可达代码与无用赋值。

不可达代码分为分支不可达代码与控制流不可达代码。

（1）控制流不可达代码（return后的语句）很容易检测：从方法入口开始，遍历CFG并标记可达语句，遍历结束时，没有被标记的语句就是控制流不可达的。

（2）对于分支不可达代码（常量if判断），需要预先对被检测代码应用常量传播分析，通过它来告诉我们条件值是否为常量，然后在遍历 CFG 时，不进入相应的不可达分支。

无用赋值：局部变量在一条语句中被赋值，但再也没有该语句后面的语句读取。我们需要对被检测的代码实施活跃变量分析，如果赋值语句左侧的变量是无用变量，则可以标记为无用赋值。但有一个例外，例如x=m()，即使x没有被用到，但是m()方法可能有副作用，可能改变了其他的某些值，因此不能被删除。

代码相关的知识点

本次作业无需关注由于删除死代码而产生的新的子代码，例如，删除line-3与line-5，那么：

int deadAssign() {
    int a, b, c;
    a = 0;     // dead assignment
    a = 1;
    b = a * 2; // dead assignment
    c = 3;
    return c;
}

a=1会变为新的死代码。

Tai-e在运行死代码检测之前会自动运行活跃变量分析与常量传播分析，DeadCodeDetection.analyze提供了获得两种分析算法对目标IR进行分析的结果。

任务：完成DeadCodeDetection的analyze API，以IR作为输入，输出IR中死代码的集合。

pascal.taie.analysis.graph.cfg.Edge。

表示CFG中的边，使用方法getKind()可以得知边的种类。CFG中的节点是Stmt，边的种类与作业相关的有4种（IF_TRUE/IF_FALSE/SWITCH_CASE/SWITCH_DEFAULT），如下所示：

pascal.taie.ir.stmt.If。

Stmt的子类，表示程序中的if语句。while循环与for循环在Tai-e的IR中会被转换为If语句。

pascal.taie.ir.stmt.SwitchStmt。

Stmt的子类，表示程序中的switch语句。

pascal.taie.ir.stmt.AssignStmt。

表示程序中的赋值语句，其与pascal.taie.ir.stmt.DefinitionStmt的关系为：

解决思路

作业代码

结果显示，表明有误报。没太理解这里面的误报是什么意思？不就是和答案相比较么？

// DeadCodeDetection.java
@Override
public Set<Stmt> analyze(IR ir) {
    // obtain CFG
    CFG<Stmt> cfg = ir.getResult(CFGBuilder.ID);
    // obtain result of constant propagation
    DataflowResult<Stmt, CPFact> constants =
        ir.getResult(ConstantPropagation.ID);
    // obtain result of live variable analysis
    DataflowResult<Stmt, SetFact<Var>> liveVars =
        ir.getResult(LiveVariableAnalysis.ID);
    // keep statements (dead code) sorted in the resulting set
    Set<Stmt> deadCode = new TreeSet<>(Comparator.comparing(Stmt::getIndex));
    // TODO - finish me
    // Your task is to recognize dead code in ir and add it to deadCode
    Set<Stmt> nodes = cfg.getNodes();
    for (Stmt n: nodes) {
        boolean isDeadCode = deadCode.contains(n);
        Stmt entry = null;
        Edge<Stmt> source_edge = null;

        // judge RET
        if (cfg.getPredsOf(n).isEmpty() && !cfg.isEntry(n)) {
            entry = n;

            // traverse branch and update deadcode set
            Set<Stmt> deadcode_set_update = deadcodeSetFromEntry(source_edge, entry, cfg, deadCode);
            deadCode.addAll(deadcode_set_update);
        }

        // judge IF & SWITCH
        if (n instanceof If) {
            // get condition params
            ConditionExp exp = ((If) n).getCondition();
            Var op1 = exp.getOperand1();
            Var op2 = exp.getOperand2();
            ConditionExp.Op op = exp.getOperator();

            // get op1/op2 value using constant result
            CPFact fact = constants.getOutFact(n);
            Value op1_value = fact.get(op1);
            Value op2_value = fact.get(op2);

            // judge condition
            boolean is_true = false;
            if (op1_value.isConstant() && op2_value.isConstant()) {
                int op1_constant_value = op1_value.getConstant();
                int op2_constant_value = op2_value.getConstant();
                if (op == ConditionExp.Op.EQ) {
                    if (op1_constant_value == op2_constant_value)
                        is_true = true;
                } else if (op == ConditionExp.Op.GE) {
                    if (op1_constant_value >= op2_constant_value)
                        is_true = true;
                } else if (op == ConditionExp.Op.GT) {
                    if (op1_constant_value > op2_constant_value)
                        is_true = true;
                } else if (op == ConditionExp.Op.LE) {
                    if (op1_constant_value <= op2_constant_value)
                        is_true = true;
                } else if (op == ConditionExp.Op.LT) {
                    if (op1_constant_value < op2_constant_value)
                        is_true = true;
                } else {
                    System.out.println("Condition op error");
                }
            }

            if (op1_value.isConstant() && op2_value.isConstant()) {
                /* update deadcode set */
                Set<Edge<Stmt>> edges = cfg.getOutEdgesOf(n);

                // ensure deadcode branch entry
                if (is_true) {
                    for (Edge<Stmt> e: edges) {
                        if (e.getKind() == Edge.Kind.IF_FALSE) {
                            entry = e.getTarget();
                            source_edge = e;
                        }
                    }
                } else {
                    for (Edge<Stmt> e: edges) {
                        if (e.getKind() == Edge.Kind.IF_TRUE) {
                            entry = e.getTarget();
                            source_edge = e;
                        }
                    }
                }

                // traverse branch and update deadcode set
                Set<Stmt> deadcode_set_update = deadcodeSetFromEntry(source_edge, entry, cfg, deadCode);
                deadCode.addAll(deadcode_set_update);
            }

        } else if (n instanceof SwitchStmt) {
            // get params p
            Var p = ((SwitchStmt) n).getVar();
            Set<Edge<Stmt>> case_condition_edges = cfg.getOutEdgesOf(n);

            // get p value using constant result
            CPFact fact = constants.getOutFact(n);
            Value p_value = fact.get(p);

            /* update deadcode set */
            if (p_value.isConstant()) {
                int p_constant_value = p_value.getConstant();

                // judge go CASE or DEFAULT
                boolean exec_default = true;
                for (Edge<Stmt> e: case_condition_edges) {
                    if (e.getKind() == Edge.Kind.SWITCH_CASE) {
                        int case_value = e.getCaseValue();
                        if (p_constant_value == case_value)
                            exec_default = false;
                    }
                }

                // update
                for (Edge<Stmt> e: case_condition_edges) {
                    if (e.getKind() == Edge.Kind.SWITCH_CASE) {
                        int case_value = e.getCaseValue();
                        // maybe deadcode
                        if (p_constant_value != case_value) {
                            entry = e.getTarget();
                            source_edge = e;
                            // traverse branch and update deadcode set
                            Set<Stmt> deadcode_set_update = deadcodeSetFromEntry(source_edge, entry, cfg, deadCode);
                            deadCode.addAll(deadcode_set_update);
                        }
                    } else if (e.getKind() == Edge.Kind.SWITCH_DEFAULT && !exec_default) {
                        entry = e.getTarget();
                        source_edge = e;
                        // traverse branch and update deadcode set
                        Set<Stmt> deadcode_set_update = deadcodeSetFromEntry(source_edge, entry, cfg, deadCode);
                        deadCode.addAll(deadcode_set_update);
                    }
                }
            }
        }

        // judge not live and not call
        if (n instanceof AssignStmt<?,?>) {
            Optional<LValue> def = n.getDef();
            SetFact<Var> fact = liveVars.getOutFact(n);
            if (def.isPresent()) {
                LValue tmp = def.get();
                if (tmp instanceof Var) {
                    if (!fact.contains((Var) tmp)) {
                        // traverse branch and update deadcode set
                        deadCode.add(n);
                    }
                }
            }
        }
    }
    return deadCode;
}

private static Set<Stmt> deadcodeSetFromEntry(Edge<Stmt> source_edge, Stmt entry, CFG<Stmt> cfg, Set<Stmt> cur_deadcode) {
    Set<Stmt> deadcode_update = new TreeSet<>(Comparator.comparing(Stmt::getIndex));
    Queue<Stmt> wl = new LinkedList<>();

    // judge entry is deadcode or not
    boolean entry_is_deadcode = true;
    if (source_edge != null) {
        Set<Edge<Stmt>> entry_in_edges = cfg.getInEdgesOf(entry);
        for (Edge<Stmt> in_e: entry_in_edges) {
            if (!in_e.equals(source_edge) && !cur_deadcode.contains(in_e.getSource()))
                entry_is_deadcode = false;
        }
    }
    if (!entry_is_deadcode)
        return deadcode_update;

    deadcode_update.add(entry);
    wl.offer(entry);

    // deadcode propogation
    while (!wl.isEmpty()) {
        Stmt cur = wl.poll();
        Set<Edge<Stmt>> edges = cfg.getOutEdgesOf(cur);
        for (Edge<Stmt> e: edges) {
            Stmt targ = e.getTarget();
            // judge target is deadcode or not
            boolean targ_is_deadcode = true;
            Set<Edge<Stmt>> targ_in_edges = cfg.getInEdgesOf(targ);
            for (Edge<Stmt> te: targ_in_edges) {
                if (!e.equals(te) && !cur_deadcode.contains(te.getSource()))
                    targ_is_deadcode = false;
            }

            if (targ_is_deadcode && targ.getIndex() < cfg.getIR().getStmts().size()) {
                deadcode_update.add(targ);
                wl.offer(targ);
            }
        }
    }
    return deadcode_update;
}

0x04 类层次结构分析与过程间常量传播

本作业为 java 实现一个类层次分析（class hierarchy analysis，CHA），并实现过程间常量传播与数据流传播的 worklist 求解器。本次作业需要实现一个基于类层次结构（CHA）的调用图，只需关注 int 的常量传播，但是需要更准确的处理方法调用。与保守处理方法调用的过程内常量传播相比，过程间常量传播可以达到更好的精度。

Java 函数调用的四种类型

（1）invokestatic，调用静态方法，在编译时确定要调用的目标方法，属于静态绑定。静态方法是属于类而不是实例的，因此可以直接调用类的静态方法。

public class ExampleClass {
    public static void staticMethod() {
        System.out.println("This is a static method.");
    }
    
    public static void main(String[] args) {
        ExampleClass.staticMethod(); // 使用 invokestatic 调用静态方法
    }
}

（2）invokespecial：调用实例方法，包括私有方法、构造方法和通过 super 关键字调用的超类方法。在编译时确定要调用的目标方法，属于静态绑定，它主要用于调用与特定对象关联的方法。

public class ExampleClass {
    private void privateMethod() {
        System.out.println("This is a private method.");
    } 
    public ExampleClass() {
        System.out.println("This is a constructor.");
    }
    
    public static void main(String[] args) {
        ExampleClass obj = new ExampleClass(); // 使用 invokespecial 调用构造方法
        obj.privateMethod(); // 使用 invokespecial 调用私有方法
    }
}

（3）invokeinterface：调用接口方法，这个指令会在运行时根据对象的实际类型进行动态绑定，并调用实现该接口的对象的对应方法。

interface ExampleInterface {
    void interfaceMethod();
}

class ExampleClass implements ExampleInterface {
    @Override
    public void interfaceMethod() {
        System.out.println("This is an interface method.");
    }
  
    public static void main(String[] args) {
        ExampleInterface obj = new ExampleClass();
        obj.interfaceMethod(); // 使用 invokeinterface 调用接口方法
    }
}

（4）invokevirtual：调用普通的虚方法，在运行时根据对象的实际类型进行动态绑定，并调用相应的方法，它允许在继承层次结构中进行方法的动态分派。

class ParentClass {
    public void virtualMethod() {
        System.out.println("This is a virtual method from the parent class.");
    }
}

class ChildClass extends ParentClass {
    @Override
    public void virtualMethod() {
        System.out.println("This is a virtual method from the child class.");
    }
    
    public static void main(String[] args) {
        ParentClass obj = new ChildClass(); 
        obj.virtualMethod(); // 使用 invokevirtual 调用虚方法
    }
}

Java 中的一些新特性会让方法调用的情形更复杂，比如 Java 8 开始允许接口定义默认方法，在此我们不考虑这些。

interface ExampleInterface {
    void abstractMethod(); // 抽象方法
    // 默认方法
    default void defaultMethod() {
        System.out.println("This is a default method.");
    }
}

class ExampleClass implements ExampleInterface {
    @Override
    public void abstractMethod() {
        System.out.println("This is an implementation of the abstract method.");
    }
}

public class Main {
    public static void main(String[] args) {
        ExampleClass obj = new ExampleClass();
        obj.abstractMethod();
        obj.defaultMethod();
    }
}

类层次分析（CHA）相关的知识点

pascal.taie.analysis.graph.callgraph.DefaultCallGraph。

代表了程序的调用图。它提供了 API 来获取到调用图的信息，它还提供了一些修改调用图的 API。（1）callSitesIn(JMethod)，返回所有调用方法JMethod的调用点；（2）contains(JMethod)，返回当前调用图是否含有JMethod，即JMethod在当前调用图中是否可达；（3）addReachableMethod(JMethod)，向当前调用图中添加方法JMethod并将方法标记成可达的；（4）addEdge(Edge<Invoke, JMethod>)，向当前调用图中添加一条调用边。

pascal.taie.analysis.graph.callgraph.CallKind。

表示调用图中边的种类，包括 INTERFACE、VIRTUAL、SPECIAL 和 STATIC。

pascal.taie.analysis.graph.callgraph.Edge<Invoke,JMethod>。

表示调用图中的边，每一条边从调用点（call site，Invoke 类型）出发，指向被调用方法（callee method，类型为 JMethod）。在创建一条边的时候，你需要向构造方法提供调用类型（边的种类）、调用点和被调用方法的信息。

pascal.taie.ir.stmt.Invoke。

Stmt 的子类，该类表示程序中的方法调用以及调用图中的调用点，它提供了一些 API 来获取调用点的各种信息，例如使用 getMethodRef() 来获取目标方法的签名信息。

pascal.taie.ir.proginfo.MethodRef。

Tai-e 中的目标方法引用，它包含了调用点所调用的目标方法的签名信息。（1）getDeclaringClass()，返回声明该方法的类；（2）getSubsignature()，返回被调用方法的子签名（subsignature）。

pascal.taie.language.classes.JMethod。

表示 Tai-e 中的 Java 方法，每个 JMethod 的实例关联着一个方法并包含该方法的各种信息。（1）isAbstract()，判断该 JMethod 是否是一个没有方法体的抽象方法；

pascal.taie.language.classes.JClass。

表示 Tai-e 中的 Java 类。每个 JClass 的实例关联着一个类并包含该类的各种信息。（1）getSuperClass()，返回该类的父类；（2）getDeclaredMethod(Subsignature)，根据子签名返回该类中声明的对应方法；（3）isInterface()，判断该类是否是一个接口。

pascal.taie.language.classes.Subsignature。

表示 Tai-e 中的子签名。一个方法的子签名只包含它的方法名f和方法签名的描述符，例如，下面方法 foo 的子签名是T foo(P,Q,R)，而它的完整签名是<C: T foo(P,Q,R)>。

pascal.taie.language.classes.ClassHierarchy。

getDirectSubclassesOf(JClass)返回直接继承该类的子类；getDirectSubinterfacesOf(JClass)返回直接继承该接口的子接口；getDirectImplementorsOf(JClass)返回直接实现了该接口的类。

pascal.taie.analysis.graph.callgraph.CHABuilder。

通过 CHA 来建立调用图，这是我们要完成的函数，主要完成 dispatch|resolve|BuildCallGraph 3 个函数。

Virtual call 的 dispatch：例如 o.foo()

例如：

class A {
	void foo() {...}
}
class B extends A {}
A o = new B();
o.foo();

假设此时 o 的类型为 A，foo 函数签名为 m。我们使用 Dispatch(c,m) 来模拟运行时阶段的 method dispatch 过程。如果 A 包括与 m 的签名相同的 m’ 方法，且 m’ 方法是非抽象的，那么 Dispatch(A,m)=m’，否则 Dispatch(A,m)=Dispatch(A’,m)（其中 A’ 是 A 的父类）。

Call 的 resolve

以如下代码举例：

class C extends B {
	T foo(P p, Q q) {
		...
		super.foo(p, q)
	}
}

对上述代码实施 CHA resolution 的步骤 resolve(super.foo(p,q))：

super.foo(p,q)的类是 B。

再比如，有代码：

class A {
	T foo(P p, Q q) {...}
}
A a = ...
a.foo(x,y)

可以重写的函数，在调用时都是 virtual call。那么经过上述的 resolve 步骤后，receiver variable c 是 A，之后就是遍历 A 的子类，然后做 dispatch(A的子类,m)。

感觉类型之间的赋值都是父类要承接子类的对象。举个例子：

class A {
	void foo() {...}
}
class B extends A {}
class C extends B {
	void foo() {...}
}
class D extends B {
	void foo() {...}
}
C c = ...
c.foo()

A a = ...
a.foo()

B b = ...
b.foo()

首先，c.foo()/a.foo()/b.foo() 都是 virtual call，那么 resolve(c.foo()) = {C.foo()}，resolve(a.foo()) = {A.foo(), C.foo(), D.foo()}，resolve(b.foo()) = {A.foo(), C.foo(), D.foo()}。

Call Graph 构建

从入口函数开始，对于每一个可到达的方法 m，对于函数的每一个调用（call site），都执行 resolve，直到没有新的函数加入。

具体的例子可以看 link 的 P57。

CHA 的特点

快速，只需要考虑 receiver variable 的类型，以及其层次关系，忽略了数据流与控制流。但是不准确，很容易有冗余，例如 resolve(b.foo()) = {A.foo(), C.foo(), D.foo()}，其中 C.foo() 与 D.foo() 是不可能调用的。

函数间的常量传播知识点

Edge transfer

过程间（函数间）常量传播与过程内常量传播类似，区别是过程间常量传播使用了 edge transfer，因此可以更准确的处理方法调用和返回。过程内数据流分析中，如果想要计算节点的 INfact，需要 meet 该节点前驱的 OUTfact。但是在过程间数据流分析中，INfact 是前驱的 OUTfact 进行 edge transfer 之后再 meet 的结果。

例如，对于过程间调用来说，如下是一个过程间调用的 CFG（ICFG）：

为了计算第 4 条语句的 IN fact，也就是方法 addOne() 的 entry 节点的 IN fact，我们需要对 2-4 这条边应用 edge transfer，这样使得第 2 条语句的 OUT fact（a=6）转换为 x=6，并最终 meet 结果 x=6 到第四条语句的 IN fact中。我们可以定义相关的 edge transfer 函数，其以 ICFG 的一条边和边的源节点为输入。

过程间的常量传播中，我们需要处理 4 种类型的边：

Normal edge。与过程间调用无关的边，无需进行处理，即 transferEdge(edge, fact) = fact。
Call-to-return edge（2->3）。针对方法调用 x = m(…)，edge transfer 会把等号左侧的变量（x）与其 value 从 fact 中 kill 掉。对于类似于 m(…) 的调用，不做处理。
Call edge（2->4）。edge transfer 将实参在调用点中的值传递给被调用函数的形参。Edge transfer 首先从调用点的 OUTfact 中获取实参的值，然后返回新的 fact，这个 fact 把形参映射到值。例如：transferEdge(2-4, {a=6})={x=6}。
Return edge（6->3）。edge transfer 函数将被调用方法的返回值传递给调用点等号左侧的变量。它从被调用方法的 exit 节点的 OUT fact 中获取返回值（可能有多个），然后返回一个将调用点等号左侧的变量映射到返回值的 fact。例如，transferEdge(6-3, {x=6,y=7}) = {b=7}。如果该调用点等号左侧没有变量，那么 edge transfer 函数仅会返回一个空 fact。

过程间的 worklist 求解器

与过程内的 worklist 大致相同，不同点是：（1）节点的 INfact 要对前驱的 OUTfact 进行 edge transfer 之后再 meet；（2）需要初始程序中所有的 IN/OUTfact，但是只需要对 ICFG 的 entry 方法设置 boundary fact。

作业代码

// CHABuilder.java
private CallGraph<Invoke, JMethod> buildCallGraph(JMethod entry) {
    DefaultCallGraph callGraph = new DefaultCallGraph();
    callGraph.addEntryMethod(entry);
    // initialize
    Queue<JMethod> wl = new LinkedList<>();
    wl.offer(entry);
    while (!wl.isEmpty()) {
        JMethod m = wl.poll();
        if (callGraph.reachableMethods().noneMatch(mm -> mm.equals(m))) {
            callGraph.addReachableMethod(m);
            Set<Invoke> all_cs_m = callGraph.getCallSitesIn(m);
            for(Invoke cs_m: all_cs_m) {
                Set<JMethod> T = resolve(cs_m);
                for (JMethod mm: T) {
                    // add cs -> mm to CG
                    callGraph.addEdge(new Edge<>(CallGraphs.getCallKind(cs_m), cs_m, mm));
                    wl.add(mm);
                }
            }
        }
    }
    return callGraph;
}

private Set<JMethod> resolve(Invoke callSite) {
    Set<JMethod> T = new HashSet<>();
    JMethod m = callSite.getMethodRef()
        .getDeclaringClass()
        .getDeclaredMethod(callSite.getMethodRef().getSubsignature());
    assert m != null;
    if (callSite.isStatic()) {
        // T = {m}
        T.add(m);
    } else if (callSite.isSpecial()) {
        // T = {dispatch(c^m, m)}
        JClass c_m = callSite.getMethodRef().getDeclaringClass();
        JMethod dispatch_ret = dispatch(c_m, callSite.getMethodRef().getSubsignature());
        if (dispatch_ret != null) {
            T.add(dispatch_ret);
        }
    } else if (callSite.isVirtual() || callSite.isInterface()) {
        // isVirtual and isInterface is same process
        // T = {dispatch(c', m)}
        JClass c = callSite.getMethodRef().getDeclaringClass();
        Collection<JClass> c_sub = new ArrayList<>();;
        c_sub.add(c);
        while (!c_sub.isEmpty()) {
            Collection<JClass> c_sub_new = new ArrayList<>();
            for (JClass c_sub_single: c_sub) {
                JMethod dispatch_re = dispatch(c_sub_single, callSite.getMethodRef().getSubsignature());
                if (dispatch_re != null) {
                    T.add(dispatch_re);
                }
                c_sub_new.addAll(hierarchy.getDirectSubclassesOf(c_sub_single));
                c_sub_new.addAll(hierarchy.getDirectImplementorsOf(c_sub_single));
                c_sub_new.addAll(hierarchy.getDirectSubinterfacesOf(c_sub_single));
            }
            c_sub = c_sub_new;
        }
    } else {
        System.out.println("call type error.");
    }
    return T;
}

private JMethod dispatch(JClass jclass, Subsignature subsignature) {
    if (jclass != null) {
        JMethod m = jclass.getDeclaredMethod(subsignature);
        if (m != null && !m.isAbstract()) {
            // dispatch(c, m) = m'
            return m;
        } else {
            // dispatch(c, m) = dispatch(c', m)
            JClass super_class = jclass.getSuperClass();
            return dispatch(super_class, subsignature);
        }
    }
    return null;
}

// InterConstantPropagation.java
@Override
protected boolean transferCallNode(Stmt stmt, CPFact in, CPFact out) {
    // Refer to https://github.com/MirageLyu/Tai-e-assignments/blob/main/A4/tai-e/src/main/java/pascal/taie/analysis/dataflow/inter/InterConstantPropagation.java
    if (!out.equals(in)) {
        out.copyFrom(in);
        return true;
    }
    return false;
}

@Override
protected boolean transferNonCallNode(Stmt stmt, CPFact in, CPFact out) {
    return cp.transferNode(stmt, in, out);
}

@Override
protected CPFact transferNormalEdge(NormalEdge<Stmt> edge, CPFact out) {
    return out.copy();
}

@Override
protected CPFact transferCallToReturnEdge(CallToReturnEdge<Stmt> edge, CPFact out) {
    CPFact result = out.copy();
    Stmt source = edge.getSource();
    Optional<LValue> v = source.getDef();
    if (v.isPresent()) {
        LValue vv = v.get();
        if (vv instanceof Var) {
            result.remove((Var)vv);
        }
    }
    return result;
}

@Override
protected CPFact transferCallEdge(CallEdge<Stmt> edge, CPFact callSiteOut) {
    // transferEdge(2->4, {a=6}) = {x=6}
    CPFact result = newInitialFact();

    // caller args
    Stmt source = edge.getSource();
    assert source instanceof Invoke;
    List<Var> args_source = ((Invoke)source).getInvokeExp().getArgs();

    // callee args
    JMethod target = edge.getCallee();
    List<Var> args_target = target.getIR().getParams();
    assert args_target.size() == args_source.size();

    // pass caller args to callee args
    for (int i = 0; i < args_source.size(); i++) {
        Var v = args_source.get(i);
        Value val = callSiteOut.get(v);
        result.update(args_target.get(i), val);
    }

    return result;
}

@Override
protected CPFact transferReturnEdge(ReturnEdge<Stmt> edge, CPFact returnOut) {
    // transferEdge(6->3, {x=6,y=7}) = {b=7}
    CPFact result = newInitialFact();

    // get Var to update
    Stmt stmt = edge.getCallSite();
    Value val = Value.getUndef();
    for (Var var : edge.getReturnVars()) {
        val = cp.meetValue(val, returnOut.get(var));
    }
    if (stmt instanceof Invoke && ((Invoke) stmt).getLValue() != null) {
        result.update(((Invoke) stmt).getLValue(), val);
    }
    return result;
}

// InterSolver.java
private void initialize() {
    // every entry in function should have boundaryfact, which conflict to PPT
    icfg.entryMethods().forEach(entry_method -> {
        Node entry_node = icfg.getEntryOf(entry_method);
        result.setInFact(entry_node, analysis.newBoundaryFact(entry_node));
        result.setOutFact(entry_node, analysis.newBoundaryFact(entry_node));
    });

    icfg.forEach(node -> {
        if (icfg.entryMethods().noneMatch(entry_method -> node.equals(icfg.getEntryOf(entry_method)))) {
            result.setInFact(node, analysis.newInitialFact());
            result.setOutFact(node, analysis.newInitialFact());
        }
    });
}

private void doSolve() {
    for (Node n: icfg)
        workList.offer(n);

    while (!workList.isEmpty()) {
        boolean changed = false;
        // pick basic block B from Worklist
        Node cur = workList.poll();
        // IN[B] = UNION(transferEdge(OUT[P]))
        Fact fact = result.getInFact(cur);
        for (ICFGEdge<Node> pred: icfg.getInEdgesOf(cur)) {
            Fact tmp = analysis.transferEdge(pred, result.getOutFact(pred.getSource()));
            analysis.meetInto(tmp, fact);
        }
        result.setInFact(cur, fact);
        // OUT[B] = genB UNION (IN[B]-killB)
        Fact in_fact = result.getInFact(cur);
        Fact out_fact = result.getOutFact(cur);
        changed = analysis.transferNode(cur, in_fact, out_fact);

        if (changed)
            for (Node suc: icfg.getSuccsOf(cur))
                if (!workList.contains(suc))
                    workList.offer(suc);
    }
}

留言

作者: wd-z711
文章链接: https://wd-2711.tech/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-ND 4.0 许可协议。转载请注明出处!

⬆︎TOP

tai_e-static-analysis-with-homework

软件分析基础知识&作业

0x00 tai-e基本知识

0x01 活跃变量分析与迭代求解器

活跃变量分析基本原理

代码相关的知识点

作业代码

0x02 常量传播和 Worklist 求解器

常量传播基本原理

代码相关的知识点

作业代码

0x03 死代码检测

代码相关的知识点

解决思路

作业代码

0x04 类层次结构分析与过程间常量传播

Java 函数调用的四种类型

类层次分析（CHA）相关的知识点

Virtual call 的 dispatch：例如 o.foo()

Call 的 resolve

Call Graph 构建

CHA 的特点

函数间的常量传播知识点

Edge transfer

相关类

过程间的 worklist 求解器

作业代码

留言