LaPluma

Keep it simple and stupid.

0%

NJU静态分析|A3-DeadCode Detection

发表于 更新于 分类于 阅读次数：
本文字数： 9.3k 阅读时长 ≈ 17 分钟

NJU Static Program Analysis | Assignment-3 Dead-Code Detection.

2024.11.7已更新

实验信息&食用指南

见本博客A1 & A2

Tips: 实验指南和框架代码仍然是最一手最正确的资料, 对于实验指南中已涉及的信息, 本记录不会过多赘述.

实验目标

基于Tai-e 框架实现一个 死代码检测 算法.

实验简析

实验指南没有给出实现的框架, 因此至此已有完成本次知识的全部基础知识(活跃变量分析 & 常量传播算法).

故本次实验主要考察对A1, A2的实验理解, 有遗忘或有不清楚的读者还望移步至官方教学视频复习后再完成本次实验.

  • 死代码检测是一个Must Analysis , 允许漏报而不允许错报.

  • 由分支不可达的特性, 采用Forward Analysis 比较符合死代码检测的特性.

  • 为了走一遍CFG 便得到结果, 我们可以将全部Stmt加入DeadCodeSet中, 将不是死代码的Stmt删去. 留下的便是死代码.

  • 此处笔者采用BFS算法进行CFG遍历, 使用Set Traveled避免环路影响.

伪代码框架

死代码检测的大致框架伪代码如下:

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
liveVarsResult <- LiveVarsAnalysis(IR)
constantResult <- ConstantAnalysis(IR)
DeadcodeSet <- all stmt in IR
TraveledSet <- empty
BFSlist <- entry
while(BFSlist is not empty){
    pickup a stmt from BFSlist
    TraveledSet <- stmt
    //handle jump Stmt
    if (stmt is if or switch){
        DeadcodeSet remove stmt
        // ConditionExp is Constant may cause Unreachable DeadCode
        if (if/switch ConditionExp is Constant by ConstantResult){
            BFSlist <- Target Stmt of Constant ConditionExp Path
        }
        else{
            BFS <- succ of stmt not in Travaled
        }
    }
    //handle Assign Deadcode
    else if (stmt is AssignStmt){
        if(stmt is not DeadAssign by LiveVarsResult || stmt has SideEffect){
            DeadcodeSet remove stmt
        }
        BFSlist <- succ of stmt not in Travaled
    }
    //normal Stmt
    else{
        DeadCodeSet remove stmt
        BFSlist <- succ of stmt not in Travaled
    }
}

更新:

Compare: ir.getStmts() & cfg.getNodes()

笔者一开始未意识到这个问题, IR 中是不包含Entry和Exit的. 换句话说, Entry和Exit是由CFG 生成的. 因此, 在初始化时, 需要使用ir.getStmts()而不是cfg.getNodes(), 否则在面对Infinity Loop 时, Exit节点会错误的被当作Dead Code.

CFG生成细节

完成本实验最重要的部分莫过于CFG 的结构, 实验指南没有为我们提供所有的实现细节, 而且CFGBuilder部分的代码对我们来说是不公开的. 那我们该如何获取关于CFG 的细节?

框架代码提供的接口

好在tai-e框架为我们提供了Class Assignment来分析自测样例, 输出*.dot文件到./output/目录下, 可以使用[Graphviz]可视化*.dot文件. 使用细节见上述链接中的官方文档.

笔者所使用的IDE 为JetBrian IDEA 2023.1.4 Community版本, Class Assignment运行配置如下.

在终端中进入工作目录(此处为output/)执行以下命令:

1
$ dot -Tpng ClassMethod.dot -o ClassMethod.png

然后我们就可以得到*.dot文件的可视化CFG 结果.

根据自测样例推测CFG的生成逻辑

经过前两次的实验, 普通节点和跳转的关联顺序在CFG 中是简单的, for和while的循环结构在tai-e中转化为简单的goto stmt. 因此此处笔者着重说明If和Switch在Tai-e 框架中的处理方式.

控制流不可达代码

源代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
public class ControlFlowUnreachable {

    static int foo() {
        int x = 1;
        return x;
        dead(); // unreachable
        x = 3; // unreachable
    }

    static void dead() {
    }
}

代码对应IR如下:

1
2
3
4
5
-------------------- <ControlFlowUnreachable: int foo()> --------------------
[0@L4] x = 1;
[1@L5] return x;
[2@L6] invokestatic <ControlFlowUnreachable: void dead()>();
[3@L7] x = 3;

CFG 可视结果如下:

不难发现, 控制流不可达代码在可视化图中的表示是独立于Entry到Exit 路径的子图

If Stmt

我们先来看看最基础的情况:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class UnreachableIfBranch {

    int branch() {
        int x = 10;
        int y = 1;
        int z;
        if (x > y) {
            z = 100;
        } else {
            z = 200; // unreachable branch
        }
        return z;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
-------------------- <UnreachableIfBranch: int branch()> --------------------
[0@L4] x = 10;
[1@L5] y = 1;
[2@L7] if (x > y) goto 4;
[3@L7] goto 7;
[4@L7] nop;
[5@L8] z = 100;
[6@L7] goto 9;
[7@L7] nop;
[8@L10] z = 200;
[9@L10] nop;
[10@L12] return z;

可以从可视化CFG 中获取不少信息.

  • [line]:if(ConditionExp) goto [line] 是if stmt结构的入口(图中为2: if(x > y) goto 4), tai-e框架会为if stmt结构提供一个统一的nop出口(图中为9: nop).
  • if结构会根据ConditionExp的T/F取值生成Edge, 分为IF_FALSE和IF_TRUE, Edge Target分别为T/F 的代码块. 可以观测到框架会为T/F的代码块添加一个nop stmt作为代码块的起始(图中为4: nop和7: nop).

如果我们不显式指定else结构:

1
2
3
4
5
6
7
8
9
10
11
12
class UnreachableIfBranch {

    int branch() {
        int x = 10;
        int y = 1;
        int z;
        if (x > y) {
            z = 100;
        }
        return z;
    }
}
1
2
3
4
5
6
7
8
9
-------------------- <UnreachableIfBranch: int branch()> --------------------
[0@L4] x = 10;
[1@L5] y = 1;
[2@L7] if (x > y) goto 4;
[3@L7] goto 6;
[4@L7] nop;
[5@L8] z = 100;
[6@L8] nop;
[7@L13] return z;
  • 可以看到if结构的IF_FALSE对应的代码块消失, IF_FALSE直接跳转到if结构的结束nop语句.(图中为6: nop)

Tips:

如果显式写出else但else为空体, tai-e框架会生成一条nop语句对应该else空体, 感兴趣的读者可以自行测试, 笔者在此不再赘述.

通过阅读框架代码中的Class If extends JumpStmt和Class JumpStmt可以知晓, If将JumpStmt的成员变量target和对应方法(如getTarget())和If结构中的IF_TRUE对应起来, 因此此时的Edge IF_FALSE其实等价于FALL_THROUGH, IF_FALSE的target是一条指向真正False代码块的goto stmt. 通过阅读框架代码, 便不难理解为何CFG 要这样处理IF结构.

if-else的嵌套等价于普通的if-else的组合.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class UnreachableIfBranch {

    int branch() {
        int x = 10;
        int y = 1;
        int z;
        if (x > y) {
            z = 100;
        }
        else if(x < y) {
            z = 200; // unreachable branch
        }
        else{
            z = 300;
        }
        return z;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
-------------------- <UnreachableIfBranch: int branch()> --------------------
[0@L4] x = 10;
[1@L5] y = 1;
[2@L7] if (x > y) goto 4;
[3@L7] goto 7;
[4@L7] nop;
[5@L8] z = 100;
[6@L7] goto 16;
[7@L7] nop;
[8@L10] if (x < y) goto 10;
[9@L10] goto 13;
[10@L10] nop;
[11@L11] z = 200;
[12@L10] goto 15;
[13@L10] nop;
[14@L14] z = 300;
[15@L14] nop;
[16@L14] nop;
[17@L16] return z;

Switch Stmt

与If一样, 我们先来看看一般情况:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class UnreachableSwitchBranch {

    void lookupSwitch() {
        int x = 1;
        int y = x << 3;
        int z;
        switch (y) {
            case 2:
                z = 2;
                break;
            case 4:
                z = 4;
                break;
            case 8:
                z = 8;
                break;
            default:
                z = 0;
                break;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
-------------------- <UnreachableSwitchBranch: void lookupSwitch()> --------------------
[0@L4] x = 1;
[1@L5] %intconst0 = 3;
[2@L5] y = x << %intconst0;
[3@L7] goto 17;
[4@L7] nop;
[5@L9] z = 2;
[6@L10] goto 20;
[7@L10] nop;
[8@L12] z = 4;
[9@L13] goto 20;
[10@L13] nop;
[11@L15] z = 8;
[12@L16] goto 20;
[13@L16] nop;
[14@L18] z = 0;
[15@L19] goto 20;
[16@L7] goto 20;
[17@L7] nop;
[18@L7] nop;
[19@L7] lookupswitch (y) {2->4, 4->7, 8->10, default->13};
[20@L7] nop;
[21@L7] return;
  • 与If一致, [line]: [method]switch([var]) {[branch]}是Switch结构的起点(图中为19: lookupswitch(y) {2->4, 4->7, 8->10, default->13}). 同样会生成一条nop stmt表示Switch结构的出口.
  • 经过笔者的多次测试, tai-e框架的Switch语句处理有些的微妙的奇怪之处. 与If不同, Switch语句的入口在line num上位于Switch结构的最后部分, 到达该入口需要经过两条nop stmt, 并且会在CASE和DEFAULT代码块之外添加一个到Switch结构出口的goto stmt. 然而由于DEFAULT一定存在(下文会解释), 因此这条goto语句一定为死代码, 不存在一条从Entry到该语句的路径.

Tips: 笔者认为这是一个非常奇怪的处理, 猜测可能跟Soot生成的字节码有关(Tai-e框架基于Soot搭建) 该猜想未证实.

  • 笔者推测CASE和DEFAULT代码块中的第一条nop语句来源是case 2:和default:, 即Tai-e框架选择保留了原来的控制信息语句(控制信息在CFG中体现为Edge), 但将其替换成了nop语句(该推测在不显示指定default时得到部分证实).

不显式指定default时:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class UnreachableSwitchBranch {

    void lookupSwitch() {
        int x = 1;
        int y = x << 3;
        int z;
        switch (y) {
            case 2:
                z = 2;
                break;
            case 4:
                z = 4;
                break;
            case 8:
                z = 8;
                break;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
-------------------- <UnreachableSwitchBranch: void lookupSwitch()> --------------------
[0@L4] x = 1;
[1@L5] %intconst0 = 3;
[2@L5] y = x << %intconst0;
[3@L7] goto 14;
[4@L7] nop;
[5@L9] z = 2;
[6@L10] goto 17;
[7@L10] nop;
[8@L12] z = 4;
[9@L13] goto 17;
[10@L13] nop;
[11@L15] z = 8;
[12@L16] goto 17;
[13@L7] goto 17;
[14@L7] nop;
[15@L7] nop;
[16@L7] lookupswitch (y) {2->4, 4->7, 8->10, default->17};
[17@L7] nop;
[18@L7] return;
  • 可以观测到CFG 会添加未被显式写出的default, 但不生成default指向的代码块(如果显示写出default但为空体, 会保留nop和goto跳转, 笔者在此不再赘述, 感兴趣的读者可以自行测试), 而是直接指向Switch结构的出口.

case & break

了解java语法性质的读者应该理解笔者在本小结的标题.

我们来看看如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Main {
    public static void main(String[] args) {
        int option = 2;
        switch (option) {
        case 1:
            System.out.println("Selected 1");
        case 2:
            System.out.println("Selected 2");
        case 3:
            System.out.println("Selected 3");
        default:
            System.out.println("Selected other");
        }
    }
}

与预期不同, 这段代码的输出如下:

1
2
3
4
> java Main
Selected 2
Selected 3
Selected other

当switch匹配2成功时, 如果不加break, 会顺次匹配在case 2:之后的所有case. 这称为case的穿透性.

我们来看看CFG是如何处理这种情况的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class UnreachableSwitchBranch {

    void lookupSwitch() {
        int x = 1;
        int y = x << 3;
        int z;
        switch (y) {
            case 2:
                z = 2;
                break;  // unreachable case
            case 4:
                z = 4;
                break; // unreachable case
            case 8:
                z = 8;
                //break;
            default:
                z = 0;
                break; // unreachable case
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
-------------------- <UnreachableSwitchBranch: void lookupSwitch()> --------------------
[0@L4] x = 1;
[1@L5] %intconst0 = 3;
[2@L5] y = x << %intconst0;
[3@L7] goto 16;
[4@L7] nop;
[5@L9] z = 2;
[6@L10] goto 19;
[7@L10] nop;
[8@L12] z = 4;
[9@L13] goto 19;
[10@L13] nop;
[11@L15] z = 8;
[12@L15] nop;
[13@L18] z = 0;
[14@L19] goto 19;
[15@L7] goto 19;
[16@L7] nop;
[17@L7] nop;
[18@L7] lookupswitch (y) {2->4, 4->7, 8->10, default->12};
[19@L7] nop;
[20@L7] return;
  • 这是一个符合预期的处理, 也是一个非常自然而然的想法.

DeadCodeDetection

本次实验只需要完成Class DeadCodeDetection中的analysis()方法.

准备工作

将A1, A2中完成的活跃变量分析和常量传播代码copy到本次实验A3的工作目录中. 需要注意的是, 本次活跃变量分析部分不使用IteratorSovler而是使用BackwardWorklist, 此部分代码需要额外完成.

Tips: 不要过多的依赖诸如ChatGPT或Copilot的书写代码功能, 其生成的代码很可能存在潜在的不易发现的bug(你猜我为什么会加这个Tips). 实际上, JetBrain IDEA的成员变量和方法补全功能已经足够好使, 使用Copilot的代码补全反而可能造成一些不必要的麻烦.

控制流不可达代码实现细节

实验指南已写明该部分的具体原理, 此处涉及一些实现细节.

  • 通过恰当的维护BFSlist可以仅遍历可达代码(主要处理If和Switch), 因此初始化所有的Stmt为DeadCode, 遍历到即排除其为死代码是一个不错的选择.
  • 无论使用BFS还是DFS, 都要处理环路引起的Infinity Loop, 一个简单的方法是创建一个Traveled Set保证每个Stmt仅会被遍历到一次(同样的, 对于BFSList维护也可以通过类似的技巧提升效率).
  • 遍历一次就能得到结果依托于不需要处理由删除死代码产生的死代码(例子可见实验指南).
  • 关于图的遍历方式, 笔者在此推荐使用CFG的顶层方法getSuccOf()和getOutEdge(), 而不是If Stmt和Switch Stmt中的方法. 这两个跳转语句的实现因为继承自JumpStmt所以细节上可能与想象中有所差异, 如果一定要使用, 还请小心谨慎的阅读API注释以获取详细信息.
  • 关于ConditionExp的处理, 可以复用A2中实现的evaluate()方法.

无用赋值代码实现细节

同上, 原理部分请参见实验指南.

  • 继承AssignStmt的子类有足足十几个, 可以从lib反编译或者科研版代码中获取相关细节, 关于副作用(Side Effect)在框架代码中已给出API, 解释了哪些派生类可能引起副作用.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* @return true if given RValue has no side effect, otherwise false.
*/
private static boolean hasNoSideEffect(RValue rvalue) {
    // new expression modifies the heap
    if (rvalue instanceof NewExp ||
            // cast may trigger ClassCastException
            rvalue instanceof CastExp ||
            // static field access may trigger class initialization
            // instance field access may trigger NPE
            rvalue instanceof FieldAccess ||
            // array access may trigger NPE(None Pointer Exception)
            rvalue instanceof ArrayAccess) {
        return false;
    }
    if (rvalue instanceof ArithmeticExp) {
        ArithmeticExp.Op op = ((ArithmeticExp) rvalue).getOperator();
        // may trigger DivideByZeroException
        return op != ArithmeticExp.Op.DIV && op != ArithmeticExp.Op.REM;
    }
    return true;
}
  • 小心, 不要忘记判断lValue是否为Var, 与之前相同, 我们只需要处理Var类型的语句.

总结

本次实验难度某种意义上低于A1, 是一个比较简单的实验, 旨在考察对分析结果的应用能力. 祝早日AC!