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

引言

众所周知，数据流分析是实现污点分析的一种常用技能
数据流分析分为过程内的数据流分析与过程间的数据流分析。前者是对一个方法体内的数据流分析，重要是基于CFG分析，不涉及方法调用；后者是基于差别方法间的数据流分析，重要是基于ICFG+CG分析，会涉及方法调用。
一、过程内数据流分析

1. CFG的构建

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

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

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

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

1. x = y bop z  // bop 是双目操作符（Binary Operator），可以是算数运算符，也可以是逻辑运算符
2. x = uop y  // uop 是单目操作符（Unary Operator），可能是取负、按位取反或者类型转换
3. x = y
4. goto L  // goto 是无条件跳转，L 是标签（Label），是标记程序位置的助记符，本质上还是地址
5. if x goto L  // if... goto 是条件跳转
6. 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匹配的方法都视为可能的目的方法，示例：

1. class A {
2.     void foo() { ... }
3. }
5. class B extends A { }
7. class C extends B {
8.     void foo() { ... }
9. }
11. class D extends B {
12.     void foo() { ... }
13. }

复制代码

类层级布局如下：

现有以下代码片段：

1. void resolve() {
2.     C c = ...;
3.     c.foo();A a = ...;
4.     a.foo();B b = new B();
5.     b.foo();
6. }

复制代码

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构建示例：

1. class A {
2.     static void main() {
3.         A.foo();
4.     }
6.     static void foo() {
7.         A a = new A();
8.         a.bar();
9.     }
11.     void bar() {
12.         C c = new C();
13.         c.bar();
14.     }
15. }
17. class B extends A {
18.     void bar() { }
19. }
21. class C extends A {
22.     void bar() {
23.         if (...) {
24.             A.foo();
25.         }
26.     }
27.    
28.     void m() { }
29. }

复制代码

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  ，连接调用边和返回边的信息可以从调用图中获得。因此，过程间控制流图的精度取决于调用图的精度。
示例：

1. static void main() {
2.     int a, b, c;
3.     a = 6;
4.     b = addOne(a);
5.     c = b - 3;
6.     b = ten();
7.     c = a * b;
8. }
10. static int addOne() {
11.     int y = x + 1;
12.     return y;
13. }
15. static int ten() {
16.     return 10;
17. }

复制代码

构建的ICFG如下：

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

id：CodeAnalyzer，名称：CodeAnalyzer Ultra
开源仓库推荐

https://github.com/HaHarden/CPGPractise

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。