数据流分析

Brief Introduction

Data flow analysis(简称DFA)研究的问题就是How data flows on CFG?

更进一步讲，就是：

​ How application-specific data flows the nodes (BBs/statements) and edges (control flows) of CFG (a program)?

从定义中我们可以提炼出几个DFA的重点：

• application-specific Data(数据) => Abstraction
  • 首先是对data做abstraction，比如$+-O⊥\top$。
• 流经Nodes (BBs/statements) => Transfer function
  • 对于CFG中的nodes，我们需要用transfer function来进行处理，比如$+ op - = -; +op+=+$。
• 通过Edges (control flows) => Control-flow handling
  • 对于edges，我们需要处理控制流，例如需要在merge处对上游分支做union。

不同的数据流分析应用（application）有着不同的数据抽象（data abstraction）和不同的流安全近似策略（flow safe-approximation strategies），即不同的transfer functions和control-flow handlings。

Preliminaries of Data Flow Analysis

• 每一次IR statement的执行都会将输入状态(input state)转换成新的输出状态(output state)

• 某个IR语句的输入（输出）状态与该语句之前（之后）的程序点（program point）关联。

  • 程序点（program point）的存在是为了方便我们观察数据抽象域的状态。

输入输出状态转换通常有三种情形：

• 无分支(左)：后一个语句的input等于前一的语句的output。
  • $IN[s2]=OUT[s1]$
• 出现分支(中)：后邻所有语句的input等于前一个语句的output。
  • $IN[s2]=IN[s3]=OUT[s1]$
• 分支合并(右)：使用meet operator $\bigwedge$ 执行merge操作。meet operator根据实际情况取值，包括$ \cap ; \cup$。
  • $IN[s2]=OUT[s1] \bigwedge OUT[s3]$

在数据流分析应用（application）中，我们通常将每个program point与一个数据流值（data-flow values）关联，此data-flow value代表了在该点上可以观察到的所有可能的程序状态的抽象集合。

对于一个application来说，所有可能的data-flow values构成的集合称为该application的域（domain）。

在上面这个例子中，我们将关注点放在数据的正负上，因此抽象域取${+;-;….}$，在DFA中不同的关注点与目的决定了我们对抽象域的定义也不同。

⭐在以上这些内容的基础上，我们可以说，数据流分析的目的就是要为一个“以safe-approximation为导向”的约束（constraints）集合，为所有语句（statements）s，在IN[s]和OUT[s]上，找到一个解（solution）。

1. 基于语句语义的约束（表示为transfer functions）。
2. 基于控制流的约束。

对于transfer functions的约束来说，有两类分析：

1. 前向分析（forward analysis），根据输入求输出：$OUT[s]=f_s(IN[s])$
2. 后向分析（backward analysis），根据输出求输入：$IN[s]=f_S(OUT[s])$

对于控制流的约束来说，也有两类情况：

1. BB内控制流：$IN[s_{i+1}]=OUT[s_i],;i=1,2,…,n-1$
2. BB间控制流：$IN[B]=IN[s_1],;OUT[B]=OUT[s_n]$