数据流分析
Note. 程序安全愈来愈受到重视，特别是在区块链领域，数据上链后无法篡改是把双刃剑，一方面是不用担心数据能够被恶意删改，但另外一方面如果当初上传的是错误的数据就无法修复。把程序缺陷扼杀在摇篮之中，是最有效也是成本最低的质量保障手段。另外像区块链领域涉及到资产的智能合约，安全性保障更应该得到保障。程序静态分析在程序缺陷分析已经发挥了巨大作用，本章将介绍静态分析领域的数据流分析技术。内容翻译自Dataflow Analysis，后面将进一步介绍开源的数据流分析工具Phasar，以及如何基于开源的数据流分析工具，来检测智能合约的漏洞。这一章主要介绍数据流分析的理论知识，后面将进一步介绍实际开发以及基于开源项目的应用。
## 1. 数据流分析作用
编译器能够基于代码本地信息作出优化，比如下面的代码：
x = a + b;
x = 5 * 2;
编译优化器很容易就识别出：
- 第一行对x的赋值是没有任何意义的，因为赋值之后x没有被使用到（因为生成机器码的时候，编译器可以把这条语句从程序中删除掉）
- 其次表达式5 * 2的结果可以在编译时计算得到，能直接把第二行赋值语句简化为x = 10;
然而，一些优化需要更加“全局”的信息。比如下面的代码：
a = 1;
b = 2;
c = 3;
if (...) x = a + 5;
else x = b + 4;
c = x + 1;
在这个例子中，对变量c的初始赋值（第3行）是没有意义的，另外x + 1的结果可以简化为7（因为不管程序走哪个分支，x的值最后都会变成6）。但是对于编译器来说，想发现这样的优化仅靠检测当前连续几行代码是远远不够的。一个更加全局的分析就很有必要了，这样的话编译器能知道程序中每一行运行完之后类似下面的信息：
- 哪些变量实质上是常量（可以减少运行时重复计算变量的值，提升程序运行效率）
- 哪些变量在重定义之前会被使用到
为了能得到这些有用的属性，我们将使用数据流分析技术。数据流分析一般在程序的控制流图(CFG)上进行，目标是计算出程序执行路径上的所有程序信息（CFG上每个节点信息）。
## 2. 数据流分析例子：常数传播&活跃变量分析
下面是两个阐述数据流分析问题的例子：常数传播和活跃变量分析。所用的示例程序都是如下所示：
1. k = 2;
2. if (...) {
3. a = k + 2;
4. x = 5;
5. } else {
6. a = k * 2;
7. x = 8;
8. }
9. k = a;
10. while (...) {
11. b = 2;
12. x = a + k;
13. y = a * b;
14. k++;
15. }
16. print(a+x);
常数传播
常数传播的作用是找出程序中变量是否具有常量值，如果是的话就可以在编译期间把变量变为常量，提升程序运行效率。更形式化的描述是，每个CFG节点n所计算得到的信息是成对的集合，每一对格式为（变量名，变量值）。如果节点n存在对（x，v），那么就表示无论程序的执行路径如何，在到达节点n的时候，变量x的值都为v。
下面是标注有常数传播信息的CFG：
活跃变量分析
活跃变量的作用是判定程序中运行过程中有哪些变量是“活”的，如果某个变量的值在被覆盖掉之前曾经被使用过，那么这个变量就是“活”的。CFG每个节点的活跃变量是在节点马上结束后所计算出来的变量集合。下面是每个节点标注有活跃变量集合的CFG：
## 3. 定义数据流问题
## 4. 求解数据流问题
### 4.1 MOP求解方案
### 4.2 求解等式集合
### 4.3 迭代算法
### 4.4 数据流分析之格点模型
#### 4.4.1 目的
#### 4.4.2 背景
##### 4.4.2.1 偏序集合
##### 4.4.2.2 格点模型
##### 4.4.2.3 单调&分布函数
##### 4.4.2.4 不动点
##### 4.4.2.5 基于旧网格产生新网格
##### 4.4.2.6 格点理论小结
#### 4.4.3 数据流分析之Kildall格点模型
### 4.5 总结