0%

静态程序分析课程笔记(数据流分析-理论基础)

Iterative Algorithm

  • 对于一个含 $k$ 个节点的CFG,每个迭代算法对于每个node $n$ 更新$\mathrm{OUT}[n]$。

  • 假设迭代算法的研究对象(domain)是$V$,定义一个k元组$V^k=\left(\mathrm{OUT}\left[\mathrm{n}_{1}\right], \mathrm{OUT}\left[\mathrm{n}_{2}\right], \ldots, \mathrm{OUT}\left[\mathrm{n}_{\mathrm{k}}\right]\right)$,$V^k\in(V_1 \times V_2 \times \dots \times V_k)$,$V^k$ 即一次迭代产生的输出,每次迭代会更新$V^k$,可以将每次迭代经过transfer functions和control-flow handing的过程抽象为$F: V^k\rightarrow {V^{k}}’$

  • 当$V^k\rightarrow {V^{k}}’$时,即$X=F(X)$ ,称$F(x)$在$X$处到达了不动点,$X$为$F(x)$的不动点,

Poset & partial order(偏序集和偏序)

We define poset as a pair (P, ⊑) where ⊑ is a binary relation that defines a partial ordering over P, and ⊑ has the following properties:

(1) $\forall x \in P, x \sqsubseteq x$ (Reflexivity, 自反性)
(2) $\forall x, y \in P, x \sqsubseteq y \wedge y \sqsubseteq x \Rightarrow x=y \quad$ (Antisymmetry,反对称性)
(3) $\forall x,y,z \in P, x \sqsubseteq y \wedge y \sqsubseteq z \Rightarrow x \sqsubseteq z $ (Transitivity,传递性)

偏序集为一个二元组$(P, \sqsubseteq)$,$P$为一集合,$\sqsubseteq$为在集合上的一种比较关系,这个二元组为偏序集当且仅当集合元素在关系上满足自反性、反对称性和传递性。

偏序的含义:一个集合中的任意两个元素不一定存在顺序关系(任意两元素不一定能比较大小)

Uppper and Lower Bounds(上界和下界)

Given a poset (P, ⊑) and its subset $S$ that $S\subseteq P$, we say that $u\in P$ is an upper bound of $S$, if $\forall x \in P, x\sqsubseteq u$. Similarly, $l∈P$ is an lower bound of $S$, if $\forall x \in P, l\sqsubseteq u$.

如图,$\{a,b,c\}$是$S$的上界(灰色),$\{\}$是$S$的下界:

image-20200804204606009

最小上界、最大下界

We define the least upper bound (lub or join) of $S$, written $⊔S$, if for every upper bound of $S$, say $u, ⊔S⊑u$. Similarly, We define the greatest lower bound (glb or meet) of $S$, written $⊓S$, if for every lower bound of $S$, say $l, l⊑⊓S$.

特别的,对于仅有两个元素的集合$S=\{a,b\}$,$\sqcup S$ 可以写为$a \sqcup b$,同理 $\sqcap S$可以写为 $a\sqcap b$。

注意:(最小)上界和(最大)下界是针对集合中的特定子集的,而上下界本身不一定在子集中,并且:

  • 不是所有偏序集均存在lub或者glb(如先前灰色的集合就不含lub)
  • 如果一个偏序集存在lub和glb,那么它是唯一的
    • 证明: 设$g_1$ 和$g_2$ 同为 P 的glb,那么根据定义 $g_1\sqsubseteq (g_2 = \sqcap P)$ 并且$g_2\sqsubseteq (g_1 = \sqcap P)$,又因为反对称性,所以$g_1=g_2$

Lattice, Semilattice, Complete and Product Lattice

Lattice(格)

Given a poset $(P, ⊑), ∀a,b∈P$, if $a⊔b$ and $a⊓b$ exist, then $(P,⊑)$ is called a lattice.

如果一个偏序集的任意两个元素都有最小上界和最大下界,那么这一偏序集是一个

Semilattice

最小上界和最大下界只存在一个的偏序集称半格,只存在最小上界称为“join semilattice”,只存在最大下界称为“meet semilattice”。

Complete Lattice,top & bottom(全格,$\top$ 和 $\perp$)*

Given a lattice $(P,⊑)$, for arbitrary subset $S$ of $P$, if $⊔S$ and $⊓S$ exist, then $(P,⊑)$ is called a complete lattice.

一个偏序集的任意子集均存在最小上界和最大下界,那么这个偏序集成为全格

每个全格都存在一个最大元素 top($\top=\sqcup P$)和最小元素bottom($\perp=\sqcap P$)

所有元素有限的格(finite lattice)均是全格。(反之不成立)

Product Lattice

Given lattices $L_1=(P_1,⊑_1),L_2=(P_2,⊑_2),…,L_n=(P_n,⊑)n)$, if for all $i$, $(P_i,⊑_i)$ has $⊔i$(least upper bound) and $⊓_i$(greatest lower bound), then we can have a product lattice $L^n=(P,⊑)$ that is defined by:

  • $P=P_{1} \times \ldots \times P_{n}$
  • $\left(x_{1}, \ldots, x_{n}\right) \sqsubseteq\left(y_{1}, \ldots, y_{n}\right) \Leftrightarrow\left(x_{1} \sqsubseteq y_{1}\right) \wedge \ldots \wedge\left(x_{n} \sqsubseteq y_{n}\right)$
  • $\left(x_{1}, \ldots, x_{n}\right) \sqcup\left(y_{1}, \ldots, y_{n}\right)=\left(x_{1} \sqcup_{1} y_{1}, \ldots, x_{n} \cup_{n} y_{n}\right)$
  • $\left(x_{1}, \ldots, x_{n}\right) \sqcap\left(y_{1}, \ldots, y_{n}\right)=\left(x_{1} \sqcap_{1} y_{1}, \ldots, x_{n} \sqcap_{n} y_{n}\right)$

Product Lattice仍是Lattice,若每个子格为全格,那么乘积也是全格。

Data Flow Analysis Framework via Lattice

一个数据流分析框架可以表示为一个三元组$(D,L,F)$ ,其中:

  • D:指数据流分析的方向,i.e., forward or backward;
  • L:指lattice,该格表示所有domain值域,以及meet($\sqcap$)或join($\sqcup$)操作;
  • F:一组transfer function。

Monotonicity and Fixed Point Theorem

Monotonicity(单调性)

A function $f: L→L$ ($L$ is a lattice) is monotonic if $∀x,y∈L$, $x⊑y⟹f(x)⊑f(y)$

普通函数的单调性的推广

Fixed-Point Theorem

Given a complete lattice ($L,⊑$), if (1) $f:L→L$ is monotonic and (2) $L$ is finite, then the least fixed point of $f$ can be found by iterating $f(⊥), f(f(⊥)), \dots, f^k(⊥)$ until a fixed point is reached the greatest fixed point of $f$ can be found by iterating $f(\top),f(f(\top)),\dots, f^k(\top)$ until a fixed point is reached.

如果f单调且L有界,那么f存在不动点,从$⊥$开始迭代执行$f$可得最小不动点,从$\top$开始迭代可得最大不动点。

证明:
(1) Existence
由$\perp$定义以及$f:L\rightarrow L$可得

又因$f$是单调的,因此

由于L是有限(finite)的,因此总会存在一个k,有

(2)Least Fixed Point(数归法,证明最小)

假设我们有另一个不动点x,i.e., $x=f(x)$

由$\perp$的定义,我们有$\perp \sqsubseteq x$;

下面用数归法证明:

由于 $f$ 是单调的,因此

对于$f^i(\perp)\sqsubseteq f^i(x)$,由于 $f$ 是单调的,因此有

因此对于任意i,有

又因为$x=f(x)$,所以存在一个i,有$f^i(\perp)\sqsubseteq f^i(x)=x$,因此有

因此$f^i(\perp)$ 是最小不动点。

Relate lterative Algorithm to Fixed Point Theorem

如何将迭代算法和不动点定理联系起来?

  1. 程序中每一个状态为一个product lattice
  2. Transfer function和join/meet fucntion可以视为F

image-20200812205336289

下面只需要证明Transfer function和 join/meet function均为单调的即可

  1. Transfer function是单调的,因为通过之前分析,所有Gen/Kill的函数都是单调的;

  2. Join/meet function是单调的,证明如下

    要证Join/meet function,就是要证$\forall x, y, z \in L, x \sqsubseteq y \Rightarrow x\sqcup z \sqsubseteq y \sqcup z$

    由 $\sqcup$ 定义可得,$y \sqsubseteq y \sqcup z$,

    由于$\sqsubseteq$传递性,$x \sqsubseteq y$,因此$x \sqsubseteq y \sqcup z$,因此 $y \sqcup z$ 是 $x$ 的上界,

    注意到 $y \sqcup z$ 也是 $z$ 的上界,而$x\sqcup z$ 是 $x$ 和 $z$ 的最小上界,

    因此 $ x \sqsubseteq y \Rightarrow x\sqcup z \sqsubseteq y \sqcup z$

讨论算法复杂度

定义格的高度即从top至bottom的最长路径长,

The height of a lattice $h$ is the length of the longest path from Top to Bottom in the lattice.

最坏情况即一次迭代,只变化一个单位高度,因此复杂度为$O(h \times k)$.

May/Must Analysis, A Lattice View*

任何分析初始状态都从unsafe至safe。

个人对safe和unsafe的理解:针对于分析结果而言,处理所有分析结果后,程序行为正常为safe,反之为unsafe,极端的safe是无用的(如安全扫描中的模式匹配)
image-20200812214731510

Must和May分析的示意图如上图所示,对于Must分析,每个代码块都是从 $\top$ 开始的,因为在程序一开始,算法认为所有的待分析对象都是“合格”的(例如存活表达式分析中,算法认为每个表达式都是成活的)——这是一个不安全的状态,经过不断迭代,算法逐渐下降到最大不动点,虽然已经过了truth点(漏报),但是这已经是最好情况了(越往下走越safe但是结果也没意义了),对这些结果做优化能确保程序不出错(safe)。

对于May分析,每个代码块从 $\perp$ 开始,即在一开始,算法认为所有分析对象都是不合格的(例如定义可达性分析中,算法认为每一条定义都没有新的定义)——这是May类型的不安全状态,经过不断迭代,算法逐渐上升到最小不动点,同样也过了truth(误报),这也是分析的最好情况,算法依旧停留在safe区域。

Distributivity(分配性) and MOP

MOP(Meet-Over-All-Paths Solution)

设 $s_x$ 为每一个statments,设 $F_p$ 是一个路径 $P$ 上的 transfer function,那么$MOP[S_i]=\sqcup/\sqcap_{\text{A path }P\text{ from Entry to }S_{i}} F_p(OUT[Entry])$.

image-20200814215920162

就是说,之前数据流分析的结果是流敏感的,而 MOP 的结果是路径敏感的,

例如下图所示的数据流,数据流分析的结果是 $\mathrm{IN}\left[\mathrm{s}_{4}\right]=f_{s_{3}}\left(f_{s_{1}}(\mathrm{OUT}[ entry ]) \sqcup f_{S_{2}}( OUT [ Entry ])\right)$,而MOP是 $ \mathrm{MOP}\left[\mathrm{s}_{4}\right]=f_{S_{3}}\left(f_{s_{1}}(\mathrm{OUT}[ entry ])\right) \sqcup f_{S_{3}}\left(f_{S_{2}}(\mathrm{OUT}[ Entry ])\right)$(注意$f_{s_3}$的位置)

image-20200814220329588

Iterative Algorithm v.s. MOP

MOP比Iterative分析更精确,也就是说路径敏感比敏感更精确,下面为证明(这里只需证明两条路径的情况,其它数归即可):

由 $\sqcup$ 的定义得 $\mathrm{x} \sqsubseteq \mathrm{x} \sqcup \mathrm{y}$ 且 $\mathrm{y} \sqsubseteq \mathrm{x} \sqcup \mathrm{y}$;

因为 $F$ 是单调的,因此有 $F(x) \sqsubseteq F(x \sqcup y)$ 且 $F(y) \sqsubseteq F(x \sqcup y)$;

因此$F(x\sqcup y)$ 是 $F(x)$ 和 $F(y)$ 的上界;

又因为$F(x)\sqcup F(y)$是 $F(x)$ 和 $F(y)$ 的最小上界;

因此 $ F(x) \sqcup F(y) \sqsubseteq F(x\sqcup y)$,即$MOP \sqsubseteq Ours$。

然而,当F是distributive(F满足分配率)时,Interative和MOP一样准确。

BitVector或是Gen/Kill问题(set union/intersection for join/meet)都是满足分配率的

Constant Propagation

Given a variable $x$ at program point p, determine whether $x$ is guaranteed to hold a constant value at $p$

对于在程序点 $p$ 的一个变量 $x$,判断 $x$ 是否为在 $p$ 点为一个常量

分析结果:对于每一个CFG节点,对应一个 $(x,v)$ 集合,$x$ 是变量,$v$ 是 $x$ 的值

Lattice

Domain: UNDEF → {…, -2, -1, 0, 1, 2, …} → NAC ,→ 表示 $\sqsubseteq$ 关系

Meet Operator $\sqcap$:

  • $\mathrm{NAC} \sqcap v= \mathrm{NAC}$
  • $\mathrm{UNDEF} \sqcap v= v$
  • $c \sqcap v= \mathrm{NAC}$ (c 为一常量)
  • $c \sqcap c= c$
  • $c_1 \sqcap c_2 = \mathrm{NAC}$

Transfer Function

讨论transfer function,对于一个赋值语句 s: x= ... 来说,定义其 F 为

  • s: x=c; $gen=\{(x,c)\}$
  • s: x=y; $gen=\{(x, val(y))\}$
  • s: x=y op z; $gen=\{(x, f(x,z))\}$

而 $f(x,z)$ 有三种情况:

function不满足分配性

如下图所示,$F(X\sqcap Y)$ 中C的值为NAC,而$F(X) \sqcap F(Y)$中 C 的值为10,因此F不满足分配性。

image-20200815173321586

Worklist Algorithm

Iterative Algorithm的优化,Iterative 存在冗余的计算,而Worklist只计算有变化的node:

1
2
3
4
5
6
7
8
9
10
11
OUT[entry] =∅;
for(each basic block B\entry)
OUT[B] =∅;
Worklist←all basic blocks
while (Worklist is notempty)
Pick a basic block B from Worklist
old_OUT= OUT[B]
IN[B] =⊔OUT[P]; # join/meet P为B的前置代码块
OUT[B] = genB U (IN[B] - killB); # transfer function
if(old_OUT≠OUT[B])
Add all successors of B to Worklis

总结

本节课主要介绍格,接着用格抽象描述数据流分析,解释为什么迭代算法能够到达最大/最小不动点,接着比较了流敏感和路径敏感的准确性,最后介绍worklist算法,以提升迭代算法的效率。