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

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

过程内数据流分析

CFG的构建

把程序转换为IR(此处采用3AC)表示。3地址码中的地址可能有如下的几种类型：名字（Name），包括变量（Variable）、标签（Label）用于指示程序位置，方便跳转指令的书写、字面常量（Literal Constant）、编译器生成的临时量（Compiler-Generated Temporary）。每一种指令都有其对应的 3 地址码形式。

找程序的Leader集合L，进而划分Basic Block。程序入口、跳转指令的目标指令、跳转指令的下一条指令。一个Leader到下一个Leader之前就是一个BB。

连接Basic Block。程序控制流的产生来源于两个地方：天然的顺序执行和跳转指令。

过程间数据流分析

CG 方法调用图

Java中的方法调用类型。Static Call：调用静态方法；Special Call：调用构造方法、私有方法、基类实例方法；Virtual Call：调用其他实例方法。所以在构建方法调用图时，最关键的是要处理好Virtual Call的情况。

CG的构建方法。类层级结构分析（Class Hierarchy Analysis，CHA）、快速类型分析（Rapid Type Analysis，RTA）、变量类型分析（Variable Type Analysis，VTA）、指针分析（Pointer Analysis，k-CFA）。上面的四种方法自上而下精度越来越高，但是效率也越来越低。本文只关注CHA的方式。

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

ICFG 过程间控制流图

ICFG的构建。ICFG要在CFG基础上添加call Edges（调用边）、return Edges（返回边）。ICFG = CFGs + call & return edges，连接调用边和返回边的信息可以从调用图中获得。因此，过程间控制流图的精度取决于调用图的精度。

公主号推荐

id：CodeAnalyzer，名称：CodeAnalyzer Ultra

开源仓库推荐

https://github.com/HaHarden/CPGPractise

标签：游戏攻略