静态程序分析

通过编写程序来分析代码是否存在缺陷来保证代码的正确性

程序分析的一些功能

• 可靠性

  空指针异常分析、内存泄漏分析

• 安全

  私有信息泄漏分析、注入攻击分析

• 编译优化

  四代码消除、循环优化

• 可读性

  IDE方法调用关系图、类型标注

正确性

目前的程序分析代码都不能保证分析的完全正确

这是由于代码分析的复杂度是NP问题，在有限时间内，不能快速找到所有正确的答案，因此大部分的静态分析都采用近似的方法，来找到近似解

过程内分析

一个变量正负判断的例子

pl-var

通过对变量的正负号抽象

来近似的得出解

三地址码与数据流图

pl-3addr

程序分析一般不直接分析源代码

而是通过把源代码转换为三地址码

然后把三地址码转换为控制流图（CFG）

然后再分析程序得出结果

CFG的INPUT和OUTPUT

pl-cfg

对于每个数据流的块，都有一个或者多个输入，和一个或者多个的输出

他们的关系如上图

pl-out

CFG计算OUT的方法如上

变量可达性分析

定义

pl-reaching-def

当变量v在p点定义

并在p到q的所有路径上

不存在v的重定义

那么称变量p点上的v，在q点可达

伪代码如下

pl-rd-code

过程如下

pl-rd-pro

计算过程通过不断迭代，并最终稳定在一个状态，那么此状态则为程序分析的结果

变量使用分析（live var analysis）

定义

pl-live-var

在程序p点定义的变量v

并在后续节点q使用了v

并在p到q点之间变量v没有被重定义

那么称变量v的定义在程序p点是live的

伪代码如下

pl-live-var-code

过程如下

通过从下往上计算

pl-live-pro

表达式可重用分析

定义

表达式v在程序p点定义

并在程序q点被再次使用

而且表达式的变量没有改变在p到q之间

那么称表达式v在程序q点可重用

伪代码如下

pl-exp

过程如下

pl-exp-pro

过程间分析

pl-const

如果没有过程间分析

那么通过常量传播算法

n = bar(42);得出n可以为任何值，不是常量

但如果加入了过程间分析

那么可以得到n = 43；为常量

调用图构建（Call graph construction）(CHA)

函数调用图

pl-cha-function

找到一个类函数的实际调用函数

pl-cha-disp

通过分析类B的函数foo，由于没有定义，则在父类A中寻找，找到则返回A.foo()

通过对象的类名找到方法的所有可能的实现

B b = ...

b.foo

那么foo有可能在B的所有子类中实现

也有可能在父类中实现

pl-cha-resolve

例子

pl-cha-sample

CHA的优点

快

缺点

只根据变量的类型来判定对象，使得结果不精确

算法

pl-cha-code

过程中

pl-cha-pro

过程间数据流图(ICFG)

pl-icfg
pl-icfg-sample

通过CHA得到函数调用链

在调用链上加入输入边和返回边

结合CFG数据流图

得到ICFG

算法过程

pl-icfg-pro

指针分析

CHA的缺陷

pl-cha-weak

通过CHA的分析，可以得到n.get的函数有可能式类Zero/One/Two的实现

那么通过常数传播算法，得出n不是常数

但这是严重不精确的

指针分析通过把n的实现类考虑进来，来加强分析的精度

pl-pa

指针分析过程解析

pl-pa-prc

指针分析的模型

特征	选择
内存抽象	与对象的创建位置有关
	存储无关，之分析类名
上下文敏感性	上下文敏感
	上下文不敏感
流敏感性	流敏感
	流非敏感
分析范围	全程序分析
	程序特定位置分析

内存抽象-Allocation-Site抽象

pl-allocation-site

通过给每行给一个表示oj，来表示对象创建的位置

上下文敏感性

pl-contex-sen

左图为上下文敏感

右图为上下文不敏感

敏感代表对于某次函数调用，是否把所有的函数调用入口的数据都聚合起来，还是把每个上下文都分开处理

分析证明，上下文敏感精度更高，在实际应用中，比非敏感分析要好很多

流敏感性

pl-flow

左边为流敏感

右边为流非敏感

他们的区别是，流敏感对每行代码都保存着一个独立的set，来标志这行代码的状态

而流非敏感则对整个程序只用一个set来包含整个程序的状态，它跟代码的执行顺序无关

分析证明，流非敏感精度不足，但足以应对大部分情况

分析范围

pl-scope

左边为全程序分析

右边为局部分析

由于只是分析z.bar()的调用，所以代码的第四行有足够的信息可以得出结果

但实践证明，局部分析的代价并没有大幅的减少，因此目前大部分的分析都是全局分析为主

指针分析关注的语句

pl-pa-not-care

它不关注流控制语句

pl-pa-care

它关注赋值语句

规则

pl-pa-rule

PFG例子

pl-pfg

PFG算法伪代码

pl-pfg-code

过程间指针分析（IPA）

伪代码

pl-ifa-code

解析

通过PFG算法得到每个变量的类型

加入对变量指定类型的函数分析

得到对象调用的函数的位置

继续解析对象的函数

不断递归

实现全部函数的指针分析

在PFG中加入敏感性，可以提高精度

pl-pfg-sen

CFL可达性IFDS

pl-ifds

通过加入上下文无关文法的入边和出边的关系

可以得到程序哪些路径是合法

哪些是不合法的

IFDS

pl-ifds-