SAST-数据流分析-精讲

众所周知，数据流分析是实现污点分析的一种常用技术

数据流分析分为过程内的数据流分析与过程间的数据流分析。前者是对一个方法体内的数据流分析，主要是基于CFG分析，不涉及方法调用；后者是基于不同方法间的数据流分析，主要是基于ICFG+CG分析，会涉及方法调用。

一、过程内数据流分析

1. CFG的构建

1.1.把程序转换为IR(此处采用3AC)表示

3地址码中的地址可能有如下的几种类型：

• 名字（Name），包括
  • 变量（Variable）
  • 标签（Label）
    • 用于指示程序位置，方便跳转指令的书写
• 字面常量（Literal Constant）
• 编译器生成的临时量（Compiler-Generated Temporary）

每一种指令都有其对应的 3 地址码形式，一些常见的 3 地址码形式如下：(x, y, z是变量的地址)

x = y bop z  // bop 是双目操作符（Binary Operator），可以是算数运算符，也可以是逻辑运算符
x = uop y  // uop 是单目操作符（Unary Operator），可能是取负、按位取反或者类型转换
x = y 
goto L  // goto 是无条件跳转，L 是标签（Label），是标记程序位置的助记符，本质上还是地址
if x goto L  // if... goto 是条件跳转
if x rop y goto L // rop 是关系运算符（Relational Operator），运算结果一般为布尔值

1.2.找程序的Leader集合L，进而划分Basic Block

• 程序入口
• 跳转指令的目标指令
• 跳转指令的下一条指令

（一个Leader到下一个Leader之前就是一个BB）

1.3.连接Basic Block

程序控制流的产生来源于两个地方：

• 天然的顺序执行
  • 这是计算系统天然存在的一种控制流
• 跳转指令
  • 这是人为设计添加的一种控制流

示例

二、过程间数据流分析

1.CG 方法调用图

1.1.Java中的方法调用类型

• Static Call：调用静态方法 --> 编译时明确
• Special Call：调用构造方法、私有方法、基类实例方法 --> 编译时明确
• Virtual Call：调用其他实例方法 --> 运行时明确(多态，最常见)

所以在构建方法调用图时，最关键的是要处理好Virtual Call的情况

1.2.CG的构建方法

• 类层级结构分析（Class Hierarchy Analysis，CHA）
• 快速类型分析（Rapid Type Analysis，RTA）
• 变量类型分析（Variable Type Analysis，VTA）
• 指针分析（Pointer Analysis，k-CFA）

上面的四种方法自上而下精度（Precision）越来越高，但是效率（Efficiency）也越来越低。

本文只关注CHA的方式：

CHA

在方法调用点处，只关注caller的声明类型T及callee的方法签名sig，会把T及其子类中所有与sig匹配的方法都视为可能的目标方法，示例：

class A {
    void foo() { ... }
}

class B extends A { }

class C extends B {
    void foo() { ... }
}

class D extends B {
    void foo() { ... }
}

类层级结构如下：

现有以下代码片段：

void resolve() {
    C c = ...;
    c.foo();A a = ...;
    a.foo();B b = new B();
    b.foo();
}

CHA算法会对于每一个接收变量的声明类型本身及其子类关于调用点处的函数签名进行方法派发的操作，将所有找到的目标方法加入结果之中。因此，结果如下：

• Resolve(c.foo()) = {C.foo()}
• Resolve(a.foo()) = {A.foo(), C.foo(), D.foo()}
• Resolve(b.foo()) = {A.foo(), C.foo(), D.foo()}

我们需要注意一下的是第三个调用点， A.foo() 也在其结果之内，因为对于 B 类本身的方法派发得到的结果是 A.foo()

并且，CHA的Resolve算法只关心声明类型，因此 new B() 其实并没有在算法中发挥作用，从而我们 Resolve(b.foo()) 产生了两个虚假（Spurious）的目标调用 C.foo() 和 D.foo()

CG构建示例：

class A {
    static void main() {
        A.foo();
    }

    static void foo() {
        A a = new A();
        a.bar();
    }

    void bar() {
        C c = new C();
        c.bar();
    }
}

class B extends A {
    void bar() { }
}

class C extends A {
    void bar() {
        if (...) {
            A.foo();
        }
    }
    
    void m() { }
}

CHA最终构建的CG如下：

在上述例子当中需要注意的是，虽然 A a = new A() ，但是解析 a.bar() 的目标方法时候，依旧会对 A 以及 A 的所有子类作 Dispatch ，故而会有3条从 a.bar() 出发的边。

最后我们会发现存在一个不可达的方法（Unreachable Method） C.m() ，那么这个方法中的代码就是死代码（Dead Code，即在任何情况下控制流都不能到达的代码）。

CHA的应用：IDE中的目标方法提示

2.ICFG 过程间控制流图

2.1.ICFG的构建

ICFG要在CFG基础上添加call Edges（调用边）、return Edges（返回边）

ICFG = CFGs + call & return edges ，连接调用边和返回边的信息可以从调用图中获得。因此，过程间控制流图的精度取决于调用图的精度。

示例：

static void main() {
    int a, b, c;
    a = 6;
    b = addOne(a);
    c = b - 3;
    b = ten();
    c = a * b;
}

static int addOne() {
    int y = x + 1;
    return y;
}

static int ten() {
    return 10;
}

构建的ICFG如下：

从上图可以看出，在构建ICFG时，仍然保留了Call-to-return edges（调用点到返回点的边），虽然实际程序运行过程不会走这条边，但是这条边可以传递callee方法不需要的数据，这样就避免了在目标方法中始终维护其不需要的数据，可以提高效率。