程序数据流静态分析指北

本文整理自南京大学（NJU）《软件分析》，包含 Intro、IR、应用三部分。

南京大学 Static Program Analysis

Introduction

莱斯定理（Rice's Theorem）

"Any non-trivial property of the behavior of programs in a r.e. language is undecidable"

不存在 Perfect static analysis

Sound & Complete

报告范围 Sound 会更多，为了保证程序可靠，会尽可能多地报 bug，但是可能存在误报。Complete 为了确保不“冤枉”程序，会保证所报的 bug 均是确切的 bug，从而导致漏报。

几乎所有的静态分析都是 Sound，如图：

图中仅分析了蓝色路径会得到错误的结论 —— Safe Cast，而 Sound 需要考虑到所有的情况进而得到 Not Safe Cast 的结论。

Useful Static Analysis —— 在 Sound 的前提下，精度与速度间进行有效平衡。

Abstraction & Over-approximation

​ abstraction 是把具体域映射成抽象域。e.g. 抽象域可以包括：

，over-approximation 再对抽象域进行运算关系 (transfer functions) 与控制流 (control flow) 的近似。

Intermediate Representation

Compiler

AST vs. IR

// do i = i + 1; while (a[i] < v)

IR 三地址码
1: i = i + 1
2: t1 = a[i]
3: if t1 < v goto 1

3-Address Code(3AC)

右侧只能有一个操作符，e.g.

c = a + b + 3 => t1 = a + b; c = t1 + 3;

地址（Address）可以由以下部分组成:

• Name: a, b, c

• Constant: 3

• Compiler-generated temporary: t1

常见的三地址码形式

x = y bop z
x = uop y
x = y
goto L
if x goto L
if x rop y goto L

/**
x, y, z: addresses
bop: binary arithmetic or logical operation
uop: unary operation (minus, negation, casting)
L: a label to represent a program location
rop: relational operator (>, <, ==, >=, <=, etc.)
goto L: unconditional jump
if … goto L: conditional jump
**/

Static Single Assignment(SSA)

• Give each definition a fresh name

• Propagate fresh name to subsequent uses

• Every variable has exactly one definition

// 3AC
p = a + b
q = p - c
p = q * d
p = e - p
q = p + q

// SSA
p1 = a + b
q1 = p1 - c
p2 = q1 * d
p3 = e - p2
q2 = p3 + q1

Control Flow Analysis

• Usually refer to building Control Flow Graph (CFG)

• CFG serves as the basic structure for static analysis

• The node in CFG can be an individual 3-address instruction, or (usually) a Basic Block (BB)

Basic Blocks(BB)

Basic blocks (BB) are maximal sequences of consecutive three-address instructions with the properties that.

• 入口为第一个指令

• 出口为最后一个指令

禁止中途进出

Control Flow Graphs(CFG)

• The nodes of CFG are basic blocks

• There is an edge from block A to block B if and only if

  • There is a conditional or unconditional jump from the end of A to the beginning of B

  • B immediately follows A in the original order of instructions and A does not end in an unconditional jump

• It is normal to replace the jumps to instruction labels by jumps to basic blocks

Data Flow Analysis

How Data Flows on CFG

Data-flow analysis is to find a solution to a set of safe-approximation-directed constraints on the IN[s]’s and OUT[s]’s, for all statements.

• constraints based on semantics of statements (transfer functions)

• constraints based on the flows of control

Notations for Constraints

Transfer Function

Control Flow

Applications

Reaching Definitions Analysis

基本概念

• 假定 x 有定义 d (definition)，如果存在一个路径，从紧随 d 的点到达某点 p，并且此路径上面没有 x 的其他定义点，则称 x 的定义 d 到达 (reaching) p。

• 如果在这条路径上有对 x 的其它定义，我们说变量 x 的这个定义 d 被杀死 (killed) 了

在实践中这个算法可以用来检测未定义的变量：e.g. 每一个变量 v 在 CFG 入口会有一个虚拟定义（dummy definition），虚拟定义 v 到达使用 v 的某点 p 时，那么 v 可能会在定义前被使用。

Transfer Function & Control Flow

Algorithm

OUT[entry] = NULL;
for (each basic block B(排除 entry)) {
	OUT[B] = NULL;
}
while (changes to any OUT occur) {
	for (each basic block B(排除 entry)) {
		IN[B] = Union(所有前驱 OUT[P]);
		OUT[B] = gen(B) Union (IN[B] - kill(B));
	}
}

e.g.

• 首先让所有 BB 和入口的 OUT 为空。因为你不知道 BB 中有哪些 D（definition）。

• 当任意 OUT 发生变化，则分析出的定值可能需要继续往下流动，所需要修改各 BB 的 IN 和 OUT。

• 先处理 IN，然后再根据转移方程完成更新 OUT。

• 在转移方程中，kill 与 gen 相关的 bit 不会因为 IN 的改变而发生改变，而其它 bit 又是通过对前驱 OUT 取并得到的，因此其它 bit 不会发生 1 => 0 的情况。所以，OUT 是不断增长的，而且有上界，因此算法最后必然会停止。

• 因为 OUT 没有变化，不会导致任何的 IN 发生变化，因此 OUT 不变可以作为终止条件。我们称之为程序到达了不动点（Fixed Point）

Live Variables Analysis

基本概念

• 变量 x 在程序点 p 上的值是否会在某条从 p 出发的路径中使用

• 变量 x 在 p 上活跃，当且仅存在一条从 p 开始的路径，该路径的末端使用了 x，且路径上没有对 x 进行覆盖。

在被使用前，v 没有被重新定义过，即没有被 kill 过。

这个算法可以用于寄存器分配。

Transfer Function & Control Flow

Algorithm

IN[exit] = NULL;
for (each basic block B(排除 exit)) {
	IN[B] = NULL;
}
while (changes to any IN occur) {
	for (each basic block B(排除 exit)) {
		OUT[B] = Union(所有后继 IN[S]);
		IN[B] = use(B) Union (OUT[B] - def(B));
	}
}

e.g.

• 考虑 BB 及其后继 S。若 S 中，变量 v 被使用，那么我们就把 v 放到 S 的 IN 中，交给 BB 来分析。

• 在一个 BB 中，若变量 v 被使用，那么我们需要添加到我们的 IN 里。而如果 v 被定义，那么在其之上的语句中，v 都是一个非活跃变量，因为没有语句再需要使用它。

• 对于转移方程，IN 是从后继 OUT 中删去重新赋值的变量，然后并上使用过的变量。在同一个 BB 中，变量 v 的 def 先于 use ，那么实际上效果和没有 use 是一样的。

Available Expressions Analysis

基本概念

• x + y 在 p 点可用的条件：从流图入口结点到达 p 的每条路径都对 x + y 求了值，且在最后一次求值之后再没有对 x 或 y 赋值

如果一个表达式上次计算的值到这次仍然可用，我们就能直接利用其中值，而不用进行再次的计算。

Transfer Function & Control Flow

Algorithm

OUT[entry] = NULL;
for (each basic block B(排除 entry)) {
	OUT[B] = ALL;
}
while (changes to any OUT occur) {
	for (each basic block B(排除 entry)) {
		IN[B] = Merge(所有前驱 OUT[P]);
		OUT[B] = gen(B) Union (IN[B] - kill(B));
	}
}

e.g.

一开始确实无任何表达式可用，因此被初始化为空集是自然的。其它 BB 的 OUT 被初始化为全集是因为当 CFG 存在环时，一个空的初始化值，会让取交集阶段直接把第一次迭代的 IN 设置成 0，无法进行正确的判定了。

Analysis Comparison