众所周知，在静态代码剖析中，数据流剖析是完成污点剖析的一种常用技能。

数据流剖析分为进程内的数据流剖析与进程间的数据流剖析。前者是对一个办法体内的数据流剖析，主要是根据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-数据流剖析

从上图能够看出，在构建ICFG时，依然保留了Call-to-return edges（调用点到回来点的边） ，虽然实际程序运行进程不会走这条边，可是这条边能够传递callee办法不需求的数据，这样就避免了在方针办法中一直保护其不需求的数据，能够提高功率。

声明

以上内容是根据南大教师程序剖析课程的总结，其中代码片段及截图等或许来源于该课程，特此说明~想要详细学习的童鞋能够转b.i.l.i.b.i.b.l.观看