SAST-数据流分析方法-理论-Toy模板网

这篇具有很好参考价值的文章主要介绍了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

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

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

示例

SAST-数据流分析方法-理论

二、过程间数据流分析

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() { ... }
}

类层级结构如下：
SAST-数据流分析方法-理论

现有以下代码片段：

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如下：
SAST-数据流分析方法-理论

在上述例子当中需要注意的是，虽然 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如下：
SAST-数据流分析方法-理论