软件分析（南大）

https://www.bilibili.com/video/av91858985

non-trivial properties: the properties related with run-time behaviors of programs

sound & complete

soundess or completeness

图片.png

静态分析：

abstract：将具体值转化成我们所关注的方面的抽象域，如希望知道每个变量的正负，则抽象域则是+ - 0 等。
over-approximation：
2.1 transfer function：定义一个转化规则，然后将程序语句中的值转化成抽象值。相当于图中的节点

2.2 control flow：程序逻辑转化为控制流。相当于图中的箭头

编译器和静态分析器的关系：静态分析一般是在IR上进行，IR由词法分析，语法分析，简单的语义分析，转化得到。

为什么要用IR做静态分析，而不是AST？

3-address code（3AC）：右侧最多一个操作符。
JVM指令：

invokespecial: call constructor, ca11 superclass methods, ca11 private methods
invokevirutal: instance methods ca11 (virtual dispatch)
invokeinterface: cannot optimization, checking interface implementation
invokestatic: call static methods
Java 7: invokedynamic -> Java static typing ，dynamic language runs on JVM|

method signature的构造：class name: return type method name (parameter types)
Basic block：出口和入口都只能有一个的最大连续指令集合

may analysis & must analysis: 两个都是safe的，所以合起来也叫safe-analysis。

Reaching Definitions Analysis： $OUT[B] = gen_{(B)} \cup (IN[B]-kill_B)$

Live Variable Analysis: $IN[B] = use_B \cup (OUT[B] - def_B)$

Available Expression Analysis: $OUT[B] = gen_{(B)} \cup (IN[B]-kill_B)$

Domain: 取决于关注的点
Direction: RD是看前面Point P的Definition是否能到Point Q，所以Forward下来就行；LV是需要看Point P的variable在后面路径中是否还有使用，需要Backward来判断；AE也是关注前面Point P的Expression是否在Point Q还有效，所以也是Forward。
May/Must: 其实就是AE是可以有漏报但不能有误报，毕竟如果某条路径中表达式的值改变了，那么该表达式的结果就不应该保留，所以它用了Must。在RD中，在使用Variable x之前，只要有一条路径没有定义就应该报错，所以应该是over-approximation；在LV中，如果使用Must，则意味着后面只要有一条路径中Variable x用不到了，就把x从寄存器中移除，但是一旦某条路径用到了x，则会出现错误。所以即便用May存在误报，也不能用Must；在AE中，如果使用May，则在expression中变量更改的那条路径中会导致汇总的那个状态直接出错。
Initialization: 如果在Must中，初始化都为∅，则会导致汇总的时候，∩操作的出错。

fixed point: X = F(X)

partial order:

lattice: poset中任意两个元素都有lub和glb。

complete lattice: poset中任意子集都有lub和glb

如何用lattice来表示一般的Data Flow Analysis：

暂时b站上的视频就这么多

最后编辑于：2020.08.15 09:40:39