Skip to the content.

Data Flow Analysis

Overview of Data Flow Analysis

数据流分析的核心:How Data Flows on CFG?

将这句话展开来,所谓数据流分析就是:

How application-specific Data (对数据的抽象:+, -, 0 等……)Flows (根据分析的类型,做出合适的估算) through the ​ Nodes (数据如何 transfer, 如 + op + = +) and ​ Edges (控制流如何处理,例如两个控制流汇入一个BB) of ​ CFG (整个程序) ?

不同的数据流分析,有着不同的data abstraction, flow safe-approximation(流动安全近似值)策略,transfer functions&control-flow handlings(转移函数和控制流处理)

在这里就能明白数据流中的Node、Edge代表的含义,比例CodeQL中就用了这个Node,Edge含义。

Preliminaries of Data Flow Analysis

Input and Output States 输入输出状态

image-20220106101314075

image-20220106101321479

在数据流分析中,我们会把每一个PP关联一个数据流值,代表在该点中可观察到的抽象的程序状态。

关于转移方程约束的概念

分析数据流有前向和后向两种:

image-20220106101522854

关于控制流约束的概念

每条语句 s 都会使程序状态发生改变。

B 的输出自然是其输入在经过多次转换后得到的状态。

而 B 的输入要根据数据流分析的需求,对其前驱应用合适的 meet operator 进行处理。后向分析时亦然。

image-20220106101549323

image-20220106112924290

image-20220106134548103


不会涉及到的概念
**>>>Hint** * 函数调用 Method Calls * 我们将分析的是过程本身中的事情,即 Intra-procedural。而过程之间的分析,将在 Inter-procedural Analysis 中介绍</br> * 变量别名 Aliases</br> * 变量不能有别名。有关问题将在指针分析中介绍。</br>

Reaching Definitions Analysis 到达定值分析

基本概念

image-20220106135805834

到达定值可以用来分析未定义的变量。例如,我们在程序入口为各变量引入一个 dummy (假的)定值。当程序出口的某变量定值依然为 dummy,则我们可以认为该变量未被定义。

对于一条赋值语句 D: v = x op y,该语句生成了 v 的一个定值 D,并杀死程序中其它对变量 v 定义的定值。

到达定值中的数据流值

image-20220106135940828

到达定值的转移方程

image-20220106140329511

到达定值的数据流处理

image-20220106140347669

到达定值的算法

image-20220106140400120

这是一个经典的迭代算法。


Live Variables Analysis 活跃变量分析

基本概念

image-20220106141954614

这个算法可以用于寄存器分配,当一个变量不会再被使用,那么此变量就可以从寄存器中腾空,用于新值的存储。

活跃变量中的数据流值

image-20220106142111766

活跃变量的转移方程和控制流处理

image-20220106142254888

活跃变量的算法

image-20220106142411079


Available Expression Analysis 可用表达式分析

基本概念

可用表达式可以用于全局公共子表达式的计算。也就是说,如果一个表达式上次计算的值到这次仍然可用,我们就能直接利用其中值,而不用进行再次的计算。

可用表达式分析中的数据流值

image-20220106142521184

可用表达式的转移方程和控制流处理

image-20220106142534366

可用表达式的算法

image-20220106142742011

总结

image-20220106142801134