导图社区 程序分析
- 12
- 0
- 0
- 举报
程序分析
南京大学软件分析课的思维导图，包含IR（Intermediate Representation）中间表示、soundiness、IFDS、Datalog-Based、security等详细知识点，制作不易，欢迎点赞收藏吧！
编辑于2024-10-31 16:20:50- 软件分析
- 程序分析
- 相似推荐
- 大纲
程序分析
引言
什么是静态分析
静态分析：分析程序P去了解它的行为并且在运行程序之前判断该程序是否满足一些性质
动态测试是一种执行软件各种输入以验证输出与预期结果相符的方法
为什么学习静态分析
program reliability（程序可靠性）
空指针引用
内存泄露
program security（安全）
private information leak（个人信息泄露）
injection attack（注入攻击）
complier optimization（编译优化）
死代码消除
code motion（编译优化）
program understanding（程序理解）
IDE call hierarchy（调用层级）
type indication（类型指示）
PL（programming language） 和 static analysis（静态分析）
Rice's theorem（莱斯定理）：递归可枚举语言（r.e.）的所有非平凡（nontrival）性质都是不可判定的
r.e.（recursively enumerable）：图灵机可以辨别
trivial：不满足任一re语言或者满足所有的re语言，否则就是non-trival的
non-trival：interesting 性质：与程序运行时行为有关的properties
静态分析的特征和例子
sound and complete（perfect static analysis不存在）
sound（may-analysis）：overapproximate
complete（must-analysis）：underapproximate
userful static analysis（能用就行）
compromise soundness（false negatives 漏报，即不考虑sound）
compromise completeness（false positive 误报，即不考虑complete）
大多数都妥协completeness：sound但是不完全精确（fully-precise）的静态程序分析
soundness的必要性
soundness对静态分析应用很重要，例如编译优化和程序验证
soundness对其他不要求soundness的应用一样很可取，例如bug检测，soundness越好越多的bug可以被发现
保证（或靠近）soundness，同时在分析精度和分析速度之间做好平衡
static analysis= abstraction（抽象）+ over-approximation
例子：判断符号
用处：检查除0错误，检查数组负索引（-1）
abstraction：将具体的ints域映射到抽象的signs符号域上
除了正负和0，还有unknown（？判断）以及undefined（除0的没意义的数）
over-approximation
transfer functions（转换函数）（在该问题中要保证sound）
决定如何不同程序语句如何处理抽象值
通过分析的问题和不同程序语句的语义（semantics）来定义
control flows（控制流，meet，merge，汇聚点）
实际操作不可能去枚举所有的路径
需要理解的问题
静态分析和动态测试的区别
静态分析：静态分析是指在不执行程序代码的情况下，对源代码、字节码或二进制代码进行分析，以发现潜在的错误和缺陷
动态测试：动态测试是指在程序运行时，通过执行代码来验证软件的功能和性能是否符合预期
理解soundness，completeness，false negative和false positives
为什么静态分析需要soundness
还有一点，应该是不会漏报，会把所有的bug都检测出来
分析得更加全面，不会错过bug
如何理解abstraction 和 over-approximation
IR（Intermediate Representation）中间表示
Compilers(编译器) 和 static analyzers(静态分析器)
compiler(编译原理相关)：将源代码（高级语言）翻译成机器语言，其中经过了语法分析，词法分析，语义分析等等
静态分析器位于翻译器到代码产生器的过程中，用于代码优化，差错等等。其中使用的为中间表示IR
AST vs IR
AST：抽象语法树（贴近语法）
high-level并且贴近语法结构
通常语言相关
适用于快速类型检查
缺少控制流信息
IR：常用三地址码
例子：
特征
low-level并且贴近机器码
通常与语言无关（independent，例如java和c）
简洁，紧凑，均匀
包含控制流信息
通常被认为是静态分析的基础
IR：三地址码（3AC）
最多只有一个操作在右边，每一个三地址码最多包含三个地址
地址可以是
变量名：a,b,c
常量：3
临时变量：t1
每类指令都有自己的三地址码形式
bop（二元算数逻辑操作）：x = y bop z
uop（一元运算符，取负、取否、变量和地址的强制转换）：x = uop y
赋值：x = y
无条件跳转：goto L（L 为 程序某个位置的标签）
条件跳转：if x goto L
rop（大于，小于，==等）：if x rop y goto L
3AC在Taie中的应用
经典程序分析框架（JAVA）
通用型框架（soot）
指针分析框架（doop）
数据流分析框架（spotbugs、checker framework）
存在问题：学习成本高、不易于使用、分析效率不够高、扩展性不够好
一些用例（这里晚点看看要不要加吧）
do-while loop
method call
四种方法调用
invokespecial：调用构造函数、父类函数、私有函数
invokevirtual：实例函数调用（virtual dispatch）
invokeinterface：与invokevirtual类似，无法优化，检查接口实现
invokestatic：调用静态方法
java7有一个invokedynamic：JVM上运行的静态类、动态语言
格式：method signature:class name/return type/name(parameter1 type,para2 .......)
class
SSA（Static Single Assignment）IR的另一种表示
所有的等式在SSA中都是可以区分的（通过不同的名字）
每一个定义都有全新的名字
传播新名字到后续的使用中
每一个变量都有一个精确的定义（一个变量代表一个等式）
控制流中需要使用合并运算符F（phi-function）在合并点选择值
如果控制流通过真的部分就取值x0,否则就是x1
为什么选择SSA（优点）
流信息间接地体现到了唯一的变量名中（可能帮助传递一些更简单的分析，例如通过SSA流不敏感分析中获取部分精确的流敏感分析）？？？？？
定义与使用对（Define-and-Use pairs）是显式的
更有效的facts存储以及传播在一些按需的任务中
一些优化任务有更好的性能通过SSA，例如条件常量传播，全局值编号
为什么不使用SSA（缺点）
SSA可能会引入过多的变量和phi函数
可能有性能问题当翻译为机器码时，因为复制操作
BB（basic blocks）基本块
定义：连续的三地址码的最大序列
性质
只能从入口进入（块中的第一条指令）
只能从末端退出（块中的最后一条指令）
构造基本块的算法
输入：一系列三地址码
输出：程序P的基本块列表
方法
1.决定P中的基本块的开头（leader）
P的第一条指令是一个leader
条件跳转和无条件跳转的目标指令是leader
紧跟着条件跳转和无条件跳转的下一条指令也是一个leader
2.为P建立BBs
一个basic block包含一个leader和所有的后续指令直到下一个leader
Control Flow Graphs（CFG）控制流图（控制流分析CFA）
静态分析的基础结构
CFG的结点可能是3AC或者BB
构造CFG的算法
CFG中的node是BB
块A到块B有边（边的构造）
从A到B有条件或者无条件跳转
B在原来的指令顺序中紧跟着A且A不是以无条件跳转为出口
A是B的前驱（predecessor），B是A的后继（successor）（可以有多个）
小tip
还可以将跳转到对应标签改为跳转到对应的块
条件跳转天然有两个出口
通常还会加两个结点（entry和exit）（便于初始化）
与可执行的IR无关
从Entry到BB的边包含IR的第一条IR指令
从任一BB到Exit的边包含可以成为最后一条IR指令
注意，要加上exit和entry才是完整的算法
需要理解的问题
compliers和static analyzers的关系
了解三地址码和其普遍形式
如何在IR的基础上构造基本块
如何在BBs的基础上构造控制流图
DFA-AP(application)
课件
overview
特定应用的数据如何流过CFG的node和edges
node：BBs或者statements（Transform function）(各种操作)
特定于应用程序(abstraction)
牺牲completeness保证sound，但是不保证精度（may analysis）
输出信息可能是真的
要求must-approximation（must analysis）
输出信息必须是真的
但都是为了保证安全性和正确性(safe-approximation)
edge（control flows handling）（合并操作）
不同的数据流分析应用有不同的数据抽象以及不同的流近似安全的策略即不同的转换函数以及控制流处理
预备知识
输入和输出状态（Input and Output States）
每一次IR语句的执行都将一个input转化为一个新的output state
输入（输出状态）与program point（PP）之前的（之后的）语句（statement）相关
每个DFA应用，都会将一个程序点（PP）联系一个代表一个所有可能的能在该点被观测到的程序状态的抽象数据流值（data-flow value）
DFA是为了发现一个解决方案，对所有的statements的IN和OUT进行近似安全的直接的约束
基于statement的语句的约束（transform function）
基于控制流的约束
转化函数的约束的符号
前向分析Forward Analysis：
反向分析Backward Analysis：
BB内的控制流
BBs之间的控制流
三种数据流分析
Reaching Definitions Analysis（可达定义分析）
未涉及的问题
方法调用
只是过程内的分析（没有方法调用）
会在过程间分析具体讲解
别名分析
变量没有别名（两个变量指向同一个地址）
解决方法会在指针分析中给出
问题定义（may analysis）
一个定义d在程序点p可达程序点q，如果有一条从p到q的路径其中d没有被“kill”掉沿着这条路径
变量v的定义是一个为该变量v赋值的statement
变量v的定义从p到q可达即：1.有一条从p到q的路径；2.这条路径上没有新的v的定义
用处
可以用于错误检测，检测出未定义的变量，例如变量v到了一个程序点，且v被使用但是v可能（may）未被初始化
数据流
facts/values
程序里所有变量的定义
可以通过位向量来表示
transfer function
gen =
控制流（control flow）
变量v在stmtD中赋值语句，且kill掉了所有在程序中v的定义，同时其他的输入定义不受影响
算法
输入
输出
方法
Live Variables Analysis（活变量分析）
目的：为了告诉v的变量值在程序点p是否可以沿着一些CFG的路径且被使用（v的值未被重新定义），如果v在程序点p的值被使用了则v在程序点p是live的，否则是dead
活变量的信息可以被寄存器分配使用，即在一些点所有寄存器都是满的但是我们需要使用其中一个，所以希望能够选择一个带有死变量的寄存器去替换
符号表示（abstraction）
data flow value/facts
程序中所有的变量
可以被表示为位向量
分析方向：反向分析
meet function：
tips：决定某个寄存器中的变量是否为活变量，是看其后继结点的IN中该变量是否为活变量
transfer function：
算法
输入：CFG（每个BB的defB和useB都已经计算好了）
输出：每个BB的IN和OUT
伪代码：
边界条件：反向传播一般都是设置exit为空集
may analysis一般设置为空（从top的全是零变成了一些1）
must analysis一般设置为全集（从bottom的全是1变成了一些0）
Available Expression Analysis（可用表达式分析）
must analysis
定义：如果所有从entry到p的路径must经过表达式（x op y），且之后没有x或y的重定义，则在程序点p上表达式（x op y）是available的
这意味着在程序点p，可以使用表达式（x op y）的结果来代替表达式，减少运算时间
同时可用表达式分析的信息可以用于全局通用的子表达式
抽象：
dataflow values/facts
程序里所有的表达式
可以使用位向量来代表
safe-approximation
对于一个IR：a = x op y
out里添加表达式（x op y）（gen）
删除IN里所有包含变量a的表达式（kill）
所有的从entry到程序点P的路径都必定经过表达式（x op y）
但为了安全分析，可能会有漏报（实际可用，但是分析成了不可用，under-approximation）
算法
注意初始条件
总结：
需要理解的问题
三个数据流分析
reaching definition
live variables
available expressions
说出三种数据流分析的不同和类似的地方
理解迭代算法并且说出为什么最终会停止
结果只会增长，是单调的
好像考试不考
gen和kill不变
fact要么被kill，要么流到out
当一个fact留在out中（通过gen生成或者survivor），他会一直留在out中
OUT永远不会缩小
fact集合是有限的
一定有一个iteration中out不会有任何东西添加
DFA-FD(foundamental)
迭代算法的另一视角
给定一个有k个节点的CFG（程序），在每次迭代中迭代算法会为每一个node n更新OUT[n]
假设数据流分析中value的值域为V，则我们可以定义一个k元组，代表每次迭代之后各个结点的值，符号为
每一次迭代可以认为是通过一个transfer functions以及control-flow的处理进行映射
算法会迭代地输出一系列的K元组直至其在连续的两次迭代中不再发生变化
不动点：X是函数F的一个不动点如果满足
相关问题
偏序（particial order）
偏序集（一个对（P,£））（注意不是小于等于，而是符号的抽象）
性质
自反性
反对称性
传递性
常见的符号有
小于等于
子字符串
子集
偏序意味着在P中的一对元素是可以无法比较的，即并不是P中所有的一对元素都必须满足偏序关系
上下界
上界
最小上界（least upper bound或者lub or meet），写作
下界
最大下界（greatest lower bound或者glb or join），写作
注意：并非所有的偏序结构都有lub或glb，但只要有glb或者lub，那就是唯一的
证明，可以用性质一和性质二证明
lattice，semilattice，complete and product lattice
给定一个偏序集，对于里面的任意两个元素都有glb和lub，则称该偏序集为一个格（lattice）
例子
小于等于关系
最小上界为max
最大下界为min
子集关系
半格
如果只有最小上界，则称为join semilattice（join半格）
如果只有glb，则称为meet semilattice（meet半格）
全格（complete lattice）
给定一个lattice，对于任意的一个子集S，如果都存在lub和glb，则称该偏序集为complete lattice
注意，glb和lub不一定在子集S里面
全格里最大的元素称为top，写作T
最小的元素称为bottom，写作反过来的T
每一个有穷的格都是全格，但是反过来不成立
例如(0,1)有bound，但是也是无穷的
大多集中在数据流分析中（有穷的）
product lattice（乘积格）
定义
子主题
product lattice也是一个lattice
如果product lattice L是complete lattices的product，则L也是complete的
通过lattice的数据流分析框架
一个数据流分析框架(D,L,F)中包含
D:数据流的方向：前向（forwards）或者反向（backwards）
L：一个lattice包含了values V的值域，以及meet∩或者join∪操作符
F：从V到V的转换函数集合
数据流分析可以看作迭代地在lattices的值上应用转换函数以及meet/join 操作符
单调性以及不动点定理
要解决的问题
算法是否能保证会停止或者到达不动点，是否总是有解
如果是，是否只有一种解或者不动点，如果有超过一个，该解决方案是否为最好的（或者最准确的）
最大或最小不动点
什么时候算法会到达不动点，或者我们什么时候可以获得结果
单调性：一个函数f:L→L是单调的，如果对于所有的x，y属于L都有，
不动点定理：给定一个全格（L，≤），如果有函数f是单调的，且L是又穷的，则f最小的不动点可以通过迭代发现，会有x = f(x)
到达最小不动点
到达最大不动点
证明
不动点存在
pigeonhole理论
不动点定理的相关的迭代算法
证明函数f是单调的
每次迭代实际上就是运用了函数F（每个node的转换函数以及控制流影响的join\meet function）
transfer function（gen/kill）是单调的
而join/meet不一定单调，需要证明（ppt160页左右
为什么算法会到达不动点
一个格的高度h为格内从bottom到top的最长路径的长度
假设在每次迭代中只有一步在格中
如果lattice的高度为h，CFG中node的个数为k
最多需要i = h*k次迭代即可到达不动点
may/must analysis，lattice视角
may analysis：求最小不动点
must analysis：求最大不动点
MOP和distributivity（可分配性）
MOP（解决方案的精确度）
meet-over-all-paths Solution
假设对于一个路径P（从entry到Si）的转化函数Fp为该路径上所有statement的组合：
MOP在每个路径的结束计算数据流值并且运用join\meet操作到这些值中去找lub/glb
有的路径不会执行所以会导致精度丢失
没有边界的（unbound）并且不可枚举的会导致实际不可操作（指数爆炸）
不同：
our：
MOP:
mop更精确
distributivity
如果满足则是可分配的
但F是可分配的则MOP和OURS精度一致
位向量或者Gen/Kill问题是可分配的
但有些问题是不可分配的
常量传播
常量传播
x在程序点p是否会有一个常量
输出为对(x,v)的集合，x为变量，v为x的值
DLF
D：前向传播
F
worklist algorithm
去除冗余部分，只有有变化的OUT才进行处理，将后继放入WL中，之后进行处理
需要理解的问题
理解迭代算法的函数视角
lattice和全格的定义
理解不动点理论
如何使用lattice总结may和must analyses
MOP和迭代算法产生的结果之间的联系
常量传播分析
WL算法
过程间分析（inter）
1、目的
迄今所有的分析都是过程内分析，如何处理方法调用
可以做最保守的分析，为了safe-approximation
但是会不精确
需要过程间分析，可以沿着过程间数据流边传播数据流信息
例如：调用和返回边
避免了过度假设导致精度的丢失
为了进行过程间分析，需要调用图
2、调用图构造(CHA)
Call Graph
代表了程序中的调用关系
从callsites到目标方法(callee)的call edges的集合
应用
所有过程间分析的基础
程序优化
程序理解
程序调试
程序测试
调用图构造是为了OOPLs（面向对象的语言）（主要是java）
类继承分析（CHA Class hierarchy analysis）
Rapid Type analysis(RTA)
Variable type analysis(VTA)
Pointer analysis(k-CFA)
CHA效率更好，但是PTA更精确
java里的方法调用
前两个比较容易处理，最后一个才是构造调用图的关键
virtual call 的 Method dispatch（派遣）
运行时，virtual call主要通过recv obj的类型和callsite的方法签名来判断
signature可以看作是方法的一个身份（soot采用的就是这种形式）
signature = class type + method name+descriptor
discriptor = return type + parameter type
dispatch函数：dispatch(c,m)
注意，要函数名和descriptor（参数和返回值）一致
没找到就去父类找
CHA
输入：整个程序的类继承信息（继承结构）
输出：基于在callsite的recvobj的类型得到virtual call
dispatch算法：
static call：比较简单
special call
private instance method：类中可以立即找到
constructor：同样也可以找到，但是也可能调用了父类的constructor
superclass instance method：类是唯一的，返回目标方法同样唯一
virtual call
subclass包含了所有直接的或简洁的subclass
会向下找dispatch，如果这个类没有对应方法还会向上寻找
特点：
优点
快！只考虑了callsite的recv var的类型，以及继承层次
忽视了数据和控制流信息
缺点
不准！容易引入虚假的目标方法
下一节再说
通常用法：IDE
调用图构造算法：
从入口方法开始处理（主要是main方法）
对每一个可达方法m，通过CHA的（resolve(cs)）对每一个callsite的方法resovle目标方法
重复直到没有新的方法被发现
3、过程间控制流图（interprocedural Control-Flow Graph）
CFG代表了单个方法的结构
Normal edges
call-to-return edges
ICFG代表了整个程序的结构
有了ICFG才能进行过程间分析
ICFG包含了程序中方法的CFGs，外加两个新的类型的边
Call edges:从callsite 到对应的callee的入口结点
Return edges:从callees的出口结点到对应callsite的下一个statement（return site）
这两种类型的连接边的信息来自call graph
连接callsite 和return site的边叫call-to-return edges（为什么要这条边）
ICFG = CFG+call&return edges
4、过程间数据流分析
转化函数也要添加一个edge transfer
Call edge transfer：transfer数据流从callsite到callee的entry node（沿着call edges）
return edge transfer：transfer data从callee的exit node到return site（沿着return edges）
过程间常量传播（interprocedural constant propagation）
Call edge transfer:传递参数
return edge transfer：传返回值
Node transfer：与过程内常量传播一致，除了对于调用的结点来说，transfer function是一个恒等函数，要先排除左边变量，让edge transfer来处理
call-to-return edges允许分析去传播本地数据流（即非函数调用的左值）
没有这条边就需要其他的方法去传播本地数据流，这样的效率非常低
需要kill掉左变量，左变量的值会通过return edges返回。否则会导致不精确
总结：
需要理解的问题
如何通过类层级分析构造call graph
过程间控制流图的理论
过程间数据流分析的理论
过程间常量传播
PTA
1、目的
CHA只考虑类继承
指针分析可以基于指向关系，就是更精确
2、pta的介绍
静态分析的基础
计算一个指针可以指向内存中的哪一个部分
对于面向对象程序（java）
计算一个指针可以指向那些对象
may-analysis
计算over-approximation？？？
会返回指针和对象之间的关系
指针分析和别名分析
指针分析：一个指针会指向什么对象
别名分析：两个指针是否指向同一个对象
别名信息可以从指针分析的结果中推导出来
应用：
基本信息：call graph，aliases
编译优化：virtual call inlining
bug检测：空指针检测
安全分析：信息流分析
等等。。。。
3、pta的关键要素（key factor）
heap abstraction
动态执行中，堆中对象可以是无穷的因为循环或者递归
为了保证终止，堆抽象模型会动态地分配，无穷的具体对象会被抽象为有穷的抽象对象以便静态分析
allocation-site abstraction
模型是通过对象的分配的位置来区分对象的
每一个allocation site都有一个抽象对象去代表所有allocate的对象
创建点在程序中是有限的，因此抽象obj也必定是有限的
context sensitivity
如何为调用的上下文建模
不同上下文可能指向的对象不同
context-sensitive
每次都会分析上下文
context-insensitive
只分析一次上下文（merge）
可能会丢失精度
但比较简单所以先学这个
flow sensitivity
flow-sensitive
语句顺序（执行顺序保持不变）敏感（流敏感）
每个程序点都维护者一个指向关系的映射
迄今所有学习过的数据流分析都是流敏感的
可能会更准确，但是还是要看语言
flow-insensitive
整个程序只维护一个映射关系
简单所以先学这个
analysis scope
whole-program
计算所有指针的指向信息
提供信息给所有可能的应用
简单，全面
demand-driven
只计算可能影响特定感兴趣的指针的指向关系
提供信息给特定的应用
计算量小
结果safe就ok了
4、concerned statements（相关语句）
不直接影响指针的不会分析
pointer in java
Local variable:x
本地变量（数量最多）
Static field:C.f
有时可以被看作全局变量
Instance field:x.f
会被建模为一个obj(被x指向)带有域f
Array element:array[i]
忽视索引，建模为一个obj(被array指向)带有single field，叫做arr，可能被所有存储在数组里的值指向
类似instance field
pointer-affecting statements
创建New:x = new T()
赋值Assign:x=y
存Store:x.f=y
取Load:y = x.f
复杂的内存存取会通过引入临时变量转化成三地址码
函数调用Call:r=x.k(a,...)
Static call:C.foo()
Special Call:super.foo()/x.<init>()/this.privateFoo()
好处理
Virtual Call：x.foo()
可能有多个目标函数
要理解的问题
什么是指针分析
理解指针分析四个要素
理解在指针分析中分析的是什么
pta-fd（PTA基础）
1、指针分析规则
domain和notations（域以及符号表示）
Variables变量：x,y∈V
Fields域：f,g∈F
Objects对象：oi,oj∈O
Instance fields实体域:oi.f,oj.f∈O×F
Pointers指针：Pointer = V∪(O×F)
Points-to relations指向关系：pt:
p(O)是O的幂集
pt(p)是p的指向集
Rule
2、如何实现指针分析
指针分析算法
全程序的指针分析算法
为了好理解而设计的
容易follow和实现的
指针分析就是在指针间传播指针信息
为指针解决一个包含约束的系统
使用图graph去连接相关的指针
PFG:指针流图（P25）
有向图：代表程序里的obj如何在pointers之间流动
Node：代表一个变量或者一个抽象对象的一个域
Edge：Pointer×Pointer：一个x→y的边意味着，x指向的对象可能（may）会流向指针y（y也会指向）
使用PFG，指针分析可以通过PFG上计算传递闭包进行解决
当pt(x)改变，则传播变化的部分到x的后继
实现关键：当pt(x)改变时，则需要传播变化的部分给与x相关的指针
实现指针分析
1.建立PFG
2.传播PFG中的指向信息(point-to information)
二者相互依赖
建立PFG时需要知道相应field的指向关系(指针信息)才能建边
PFG是在指针分析时动态更新的
3、指针分析算法
PFG：边的集合
WL
包含了要处理的指向信息
WL的条目<n,pts>是指针n和指向对象集合pts，意味着pts要传播到pt(n)里
AddEdge
如果边不存在则加边
同时source不为空时要传播指针信息给target（确保每一个被s指向的obj也会被t指向）
对assign、load和store都会有处理
Propagate
如果pts为空则什么都不做（去重可能会导致pts为空）
先在该结点传播添加指向信息（修改指针集）
之后结点的后继也要添加该指向信息，所以先添加到wl中（传播变化部分到后继结点）
Solve
处理new和assign
new：初始化分析
Assign：往PFG里加边
处理WL
先获取一个目标
排除pt(n)中已有的对象（差异传播）
为什么要差异传播
避免传播和处理冗余的指向信息
有的指向信息已经在pt(n)以及n的后继里了，无需再次传播
可以提高效率
差异传播的Δ，之后还会用于域的传播，以及函数调用
传播变量
如果处理的是一个var，还需要处理load和store语句
新的指向关系可能会引入新的pfg边
base变量可能指向新的obj
这里也可以解决别名问题
例子（p70）
至今需要理解的问题
理解指针分析规则rule
理解指针流图PFG
理解指针分析算法
4、带方法调用的指针分析
过程间指针分析需要call graph协助
CHA和PTA的区别
CHA
基于base变量a来获取目标方法
不准确，会引入虚假的调用边和指向关系
PTA
基于pt(a)来获取目标方法
更精确，同时用于call graph和指向关系
on-the-fly call graph construction
规则
方法调用过程中需要做的事情
dispatch(oi,k)
根据方法签名和对应oi的类型获取目标方法
传rece obj到this
mthis为m的this变量
recv obj应该只流到对应方法的this指针中
直接用recv会让所有的obj到流到所有的this指针中
为什么不需要添加x→mthis的边（虚线）
会引入虚假的指向关系给this变量
传参
mpj：m的第j个变量
传返回值
mret：有方法m的返回值的变量
指针分析和call graph的构造是相互依赖的
有函数调用时，base的指针集需要指针分析，但是指针分析又依赖于call graph
建立base.method()的CG也要指针分析
call graph会构造一个可达世界reachable world
入口方法（main）是可达的
其他的可达方法会被逐渐发现随着分析
只有可达的方法和stmt会被分析
算法（黄色为新增部分）
新增集合
S:可达语句的集合（只分析可达语句）
Sm：方法m中的stmt
RM：可达方法的集合
CG：call graph的边
输入为entry，要从entry（main）中慢慢发现可达的
AddReachable：用来拓展可达世界
如果方法m不在RM中，则将m添加到RM同时可达的语句也添加进来
对于方法内的new和assign语句进行处理
为什么只处理new和assign
Load和Store需要x的信息，要根据指针集的内容才能进行处理，所以放在之后处理
AddEdge方法和之前一致
同样处理load和store
如果和函数调用相关则进行processCall(x,oi)
oi是流入x的新对象，会带来新的call graph，所以需要处理一下新情况
取出x相关的调用语句
dispatch获取目标方法
传递recvobj给目标方法的this指针
this改变说明x改变了
判断调用边是否存在Call graph中
为什么需要判断oi这个新对象的方法是否在CG中
决定CGedge的是oi的类型
之前可能有相同类型的obj来了
不存在则添加到CG中，同时方法m添加为可达
传参，传返回值
构造CG on the fly
会加大WL
输出为
指向关系pt
调用图CG
这是一个全程序算法了
例子：p126
要理解的问题
指针分析中方法调用的规则
过程间指针分析算法
理解on-the-fly call graph construction
pta-cs（上下文敏感的PTA）
引言
上下文敏感可以提升指针分析的精度，跨函数过程间分析也可以使用，来提高进度
上下文不敏感的问题
会有false positive
1、introduce
上下文不敏感导致的不精确
动态执行中一个方法可能在不同的上下文中被多次调用
参数不同，返回值也不同
不同的上下文，方法的变量可能会指向不同的对象
CI指针分析中，不同上下文的obj是混在一起的，并且传播到程序中的其他部分（通过返回值或者副作用side-effort），这会导致虚假的数据流
上下文敏感
CS通过区分不同的上下文中不同数据流建模调用上下文，这样可以提升精度
最老的以及著名的上下文敏感策略叫做call-site sensitivity(call-string)
即通过一个call sites的链（调用点的串）来代表一个方法的不同的上下文（调用栈的抽象）
method的call site
caller的call site
caller的caller的call-site等等
Cloning-Based Context Sensitivity
实现CS的最直接的方法
每个方法被一个或多个上下文标识
每个变量也被一个上下文标识（通过继承他们定义的方法的上下文）
基本上每个方法和其变量都被克隆了，每个上下文都有一个clone
CS Heap
OO程序（面向对象程序，例如java）基本上都是heap-intensive（堆密集的）
OO会频繁地修改对象
heap-intensive：对象大多会存储在堆区
实际中，为了提高精度，CS应该在用在堆抽象中
抽象对象也要加上上下文（heap contexts）
常用的选择就是继承obj被allocate的方法的上下文
CSheap抽象，提供了一个更细粒度的堆抽象，相比于单纯的allocation-site抽象
为什么CS heap可以提高精度
动态运行时一个allocation site可以在不同的调用的上下文中产生多个对象
不同的obj可能被不同的数据流操作，例如：存储不同的值到其对应的fields中
指针分析中，没有堆上下文去分析这种代码可能会丢失精度通过合并不同上下文的数据流到同一个抽象obj中（丢失精度）
相反，通过堆抽象从同一个allocation site中区分不同的obj可以提升精度
对比：
var和heap的上下文都有才能更精确分析
2、上下文敏感指针分析规则
domain（域）和notations（符号）
rule
注意，这里的不同的c是可以相同的
函数调用
dispatch：与上下文感觉好像暂时不是很相关
select（最关键的函数）：为目标方法选择上下文，基于在call site中可用的信息
c:调用者的上下文
ct:callee的上下文
l:call site
当前需要理解的东西
CS的概念
CSheap的概念
为什么CS和CSheap可以提高精确度
CS pta的rules
3、上下文敏感指针分析算法
CS的PFG
Node：CSPointer = (C×V)∪(C×O×F)
一个结点n代表了一个上下文敏感的变量或者一个上下文敏感的抽象对象的一个域
有了CS，node会被附上上下文
Edge：CSPointer×CSPointer
同样也是may流到下一个结点
算法
solver（主体）
符号解释翻译：
S：可达语句（stmt）的集合
Sm:方法m里的stmt
RM：上下文敏感的可达方法（一定是带有上下文的）的集合
CG：上下文敏感的CG边
WL要可达
之后x和y之类的store和load语句的上下文相同，因为实在同一个函数里的
AddReachable
与CI的类似，只不过都添加了同一个上下文
AddEdge和propagate不变
ProcessCall
最关键的函数：select
选择callee的上下文
除了入口方法caller，其余的caller的上下文都是在处理对应的call的时候产生的
之后就是传this，建立CG图中的边，传参以及传返回值
4、上下文敏感的变体（select细讲）
select方式不同会有不同的变种
select(c,l,c':oi)
c:caller context
l:call site
c':oi : 带有heap context的recv obj
context insensitivity（上下文不敏感）可以看作是上下文敏感的特殊情况
select(_,_,_) = []
返回同一个上下文
常用的三个变种
Call-site sensitivity（调用点）
每个上下文包含call site的一个列表（call chain调用链）
在方法调用中，可以通过添加call site到caller context调用者上下文中作为callee context被调用函数的上下文
本质上是调用栈的抽象(call stacks)
因为根本没有用到堆抽象，只有函数的上下文
select(c,l, )
问题，递归调用时可能会产生很长（无限长）的上下文
例子：p104
K-Limiting Context Abstraction（
目的
确保指针分析会终止
防止有太多的上下文导致指针分析爆炸
方法：设置一个上限去限制context的长度，符号为k
对于call-site sensitivity，每个上下文包含call chains的最后的k个call site
实际中k的值一般很小（通常小于等于3）
method context和heap context可能会使用不同的k
例如k = 2的method context，m = 1的heap context
k-Call-Site Sensitivity/k-CFA
1-call-site/1-CFA
select( ,l, ) = [l] (直接选取call site作为上下文)
但是有递归会导致不精确的问题
2-call-site/2-CFA
select(c,l, ) = [l'',l]，其中c=[l',l'']
一般至少两层
层数越多，上下文区分越细，精度越高
例子（119页）
Object sensitivity（对象）(与callsite很不一样)
每个上下文都是抽象obj（通过allocation site来区分）的列表
在方法调用中，使用recvobj以及其堆上下文作为callee的上下文
在不同的obj上区分数据流的操作
select(,c':oi) = [oj,...,ol,oi]，其中c'=[oj,.....,ok]
基于allocation site敏感
例子：p145
与callsite的对比：p153
只记前一个的call site（来源），如果是同一个调用点就容易出问题
而obj是自己的来源（最开始的地方）
但是理论上精度是无法比较的
实际上在OO语言里，obj sensitivity的表现会比callsite好
总结：
测试下来在oo语言里，准确度和效率都比callsite好
Type sensitivity（类型）
基于object sensitivity
每个上下文都包含了types的列表
方法调用中，使用recv obj的allocation site的类型以及recvobj的堆上下文作为callee的上下文（一定要注意是创建这个对象的类的type）
是obj敏感的一种粗粒度的抽象
select(,c':oi) = [t',...,t'',InType(oi)]，其中c'=[t',...,t'']
同一个k-limiting，精度会比obj低
但是有更好的效率，通过将allocation sites 合并到同一个type中作为上下文
但是比call-site好
总结：
要理解的问题
上下文敏感的指针分析的算法
常见的上下文敏感的变体
常见的变种的之间的区别和关系
security
引言
常见的攻击
注入错误
信息泄露
1、信息流安全(information flow security)
防止不想要的信息流，保护信息安全
访问控制（Access Control）和信息流安全
Access Control(保护隐私数据的标准方法)
检查程序是否有权力或权限去访问特定信息
考虑信息如何被访问
但是信息被获取后程序会做什么无法保证
Information flow security（end-to-end）
跟踪信息流是如何在整个程序中流动的去确保程序可以安全地处理这些信息
与信息如何传播相关
一个实际的系统需要access和flow control去满足所有的安全需求
Information flow
概念：如果变量x中的信息传递到y，则有一个信息流x→y
Information Flow Security
将程序中的变量分成不同的等级
指定这些级别中允许的流动，即信息流动方案（policy）
最经典的是two-level policy，即一个变量可以被分为两种安全等级
H：high security，安全信息
L：low security，可以被观察的信息
安全等级可以被建模为偏序：L≤H
限制不同安全等级之间的信息流动
noninterference policy（非干涉政策）
要求高等级的变量信息不会在low level的变量信息上造成影响（高信息不能混入低信息）
直观上看，不能通过观察low var总结出任何关于high var的信息
确保格中信息流只会从low流向high
2、Confidentiality and Integrity（保密性和完整性）
Confidentiality
防止安全信息泄露（high to low）
信息流安全的另一个视角
Integrity
防止不可信的信息污染关键的信息
注入错误
Command injection
SQL injection
XSS attacks
完整性 广泛的定义
保证数据的correntness，completeness和consistency
correntness（正确）：重要的信息不被不可信的数据污染
completeness（完整）：数据库系统应该完整的存储所有数据
Consistency（一致）：一个文件传输系统应该保证两端的文件内容是一致的
完整性比保密性更难实现（更广泛）
二者
是对称的，可以用相同的技术手段解决两种问题
Confidentiality：读保护：low不能读high
Integrity：写保护：high不能写入low信息
3、Explicit Flows and Covert Channels显示流和隐藏信道
explicit flow：例如通过赋值造成信息流动
Implicit flows
例子：
这种也算信息泄露，可以通过publik判断secret是否为负数
控制流被secret信息影响时可能会导致implicit flow（隐式流）
任何在secret control下的副作用造成的区别编码的关于控制的信息都有可能变成可观测的，并且泄露secret信息
用副作用反推high info secret
判断方法
程序是否终止
终止信道 termination channels
运行时间是否增加
时间信道 timing channels
抛异常
exceptions
数组负索引（类似的必定报错的错误）
Covert/Hidden Channel
Channel
通过一个计算系统来传递信息的机制被称为channel
利用机制的目的不是为了transfer消息的信道被称为covert channels
还有例如电量消耗速度，缓存cache命中率等等
与explicit flows相比，explicit flows会携带更多信息，所以这个课主要关注explicit flows
如何防止不希望的信息流，即执行信息流策略
4、Taint Analysis（污点分析）
最常用的数据流分析，可以将数据分为两个类型
污点数据（感兴趣的数据）：一些类型的标签会与数据相关联
其他数据：非污点数据
污点数据的来源被称为sources。实际操作中，污点数据通常来源于一些方法的返回值
污点分析会跟踪污点数据会如何在程序中流动，并且观察是否污点数据会不会特定位置（sinks）
实际中，sinks通常是一些敏感方法
应用
Confidentiality
Source：secret数据的来源
Sink：leakage可能会泄露数据的方法
信息泄露
Integrity
Source：source of untrusted data不可信数据的来源
Sink：critical computation重要计算
Injection errors
污点分析可以检测这两个不希望的信息流
如何利用指针分析进行污点分析
将污点数据作为一个特殊的objects
将sources作为一个特殊的污点数据的allocation site
利用指针分析去传播污点数据
domains 和 notations
ti是来自i的污点数据，自带一个call site的信息，是一种特殊的object
inputs and outputs
inputs
sources：源方法的集合（返回污点数据的方法的call）
sinks：带有敏感参数的sink方法的集合（污点数据流到这些方法的参数）
outputs
taintflows：source和sink calls的对的集合
例如：<i,j,k>意味着call site i（调用了source方法）的污点数据可能会流到call site（调用了sink method） j的第k个参数
rule
处理source（产生污点数据）
和指针分析相同的部分
处理sinks（产生污点流信息）
注意，i从0开始计数
例子：p77
要理解的问题
信息流安全的概念
保密性和完备性
显式流和隐藏信道
使用污点分析去侦测不希望的信息流
Datalog-Based
1、引言
imperative（命令式编程） 和 declarative（声明式编程）
命令式：怎么去做
非常接近于实现的语言
指针分析中（很多细节很难实现）
如何实现worklist
使用arraylist 还是linked list
哪一个WL条目应该被第一个处理
如何实现指针集
使用哈希表还是位向量
如何连接PFG中的结点以及pointers
如何将变量和相关的语句相关联
声明式：做什么
精炼，简单
细节少
实现规整
succinct简明
readable（logic-based specification）可读性高
Easy to implement 易实现
2、datalog介绍
一个逻辑声明式（declarative logic）语言（prolog逻辑编程语言的一个子集）
最初是作为数据库查询语言的
现在有很多应用
程序分析
声明式网络协议
大数据
云计算
datalog = data + logic（and，or，not）
无副作用
无控制流
分支
循环
异常
没有函数
不是图灵完备（turing-complete）
predicates（谓词，断言）
datalog里，谓词（relation关系）是statement（陈述）的集合
谓词是data的一个table（表）
一个fact是属于表里的一行，说明一个断言对于特定的值的组合是真的
两种谓词（断言）
EDB(extensional database)外延型数据库
断言是提前定义好的
relations关系是不可变的immutable
可以看作输入关系
Body可以是EDB或IDB
IDB(intensional database)内生型数据库
只通过rules建立的
relations是通过rules推导的
可以看作输出关系(output relations)
head只能是IDB
Atoms原子
原子是datalog的基础元素，代表了断言的形成
Terms
variables变量：代表任何值
constants常量
Atom（Cont.）
P(X1,X2,...,Xn)这种被称为relational atom 关系原子
当断言p包含X1，X2,.....,Xn的这个元组时这个关系原子就是真的
除了关系原子，datalog还有arithmetic atoms算数型原子
datalog rules（logic）
rule规则是表达逻辑推断的一种方式
rules同时可以说明事实是如何推断的
rules的格式为
意味着如果body（前提）是true的则head（结果）也是true的
“,”逗号可以看作逻辑与and
逻辑或
";"使用；
逻辑或的顺序比逻辑与低
写多条带有相同head的rules
negation非
可以写作!B(...)，读作not B(...)
recursion(递归)
datalog支持递归规则，允许IDB断言被自己（直接或间接地）推导
例如可以计算可达性信息（传递闭包）
没有递归，datalog只能表达基本的关系表的查询
有递归就能够进行更复杂的程序分析例如指针分析
recursion 和 negation
datalog里，一个原子的recusion和negation必须是分开的
否则rules里可能会有矛盾并且推断会不收敛
这里面存在环
如何解读rules
考虑所有的子目标中变量的值的组合
类似数据库的处理逻辑
顺序不会影响结果
如果有一个combination使得所有的子目标都为真，则head atom（带有相应的值）也是真的
可能用短路求值
head的断言由所有为真的atoms组成
datalog program = facts + rules
initial data初始数据来自哪里？
rule safety
每一个变量都出现在一个不是非关系型(non-negated relational)原子中
有两种rules是不安全的
x是无穷的，会导致A也是无穷的关系
datalog里，只有safe的rules才是允许的
datalog程序的执行
EDB + rules→datalog engine→IDB
datalog engine通过给出的rules和EDB推断facts直到没有新的facts被推断
单调性：datalog是单调的因为facts不能被删除
termination终止：datalog程序一定会终止
datalog是单调的
IDB断言的可能值是有限的（rule safety）
图灵完备的可能会有死循环
3、datalog的指针分析
datalog配置
EDB：从程序语法上可以提出的指向关系信息
IDB：指针分析结果
Rules：指针分析规则
方法调用
EDB和IDB
EDB
VCall:在l语句调用了x变量的k方法
Dispatch：根据obj和method给出对应的方法
thisvar：方法的this指针
IDB
Reachable：可达的方法m
CallGraph：在l位置调用了方法m
处理this指针：
传参：
EDB
Argument：在语句l里，第i个参数的变量ai
parameter：方法m的第i个参数pi
传返回值
EDB
MethodReturn：方法m的返回变量v
callreturn：在l的stmt的返回变量r
全程序的指针分析：
注意有一个程序的入口m（main函数）
同时只有m可达才会进行new操作（varpointsto会限定可达方法）
别的语句都会依赖于varpointsto，不是可达的方法是不会被触发的
4、datalog的taint analysis（污点分析）
EDB和IDB
EDB：
source：源方法
sink：sink方法
Taint：l:产生污点数据的callsite，以及污点数据t
IDB：
从sr的源call可能会流到sink call sn的第i个参数
rules：
优缺点：
优点
简洁且可读性高
容易实现
可以受益于现成的datalog引擎
缺点
受限的表达式
有些逻辑表达式是不可能或者不容易表达的
不能完全控制性能
需要理解的东西
datalog语言
如何通过datalog实现指针分析
如何通过datalog实现污点分析
IFDS
1、Feasible and realizable paths，可行以及可实现的路径
Infeasible paths(不可行路径)
CFG中不对应正式执行的路径，动态执行时不是所有的路径都会经过的
要程序分析的结果尽可能没有（或者越少越好）被infeasible paths污染
但给定一个路径，判断其是否为feasible，是不可判断的（undecidable）
realizable path可实现路径
return与相对应的call相匹配的path称为realizable paths（一般在跨函数调用里）
可实现路径可能不会被执行，但是unrealizable paths一定不会被执行
通过识别realizable paths从而避免unrealizable paths污染分析结果
如何做到
2、CFL-Reachability
概念：一个路径连接了A和B，或者说B对于A来说是可达的。只有这个path的edge的label串联可以在context-free language中形成一个word。A path is considered to connect two nodes A and B, or B is reachable from A, only if the concatenation of the labels on the edges of the path is a word in a specified context-free language
在语言L中，一个有效的句子必定是遵循L的语法的
一个context-free language是通过context-free grammar产生的（学过编译原理会更明白一点）
CFG是一个正式的语法，所有的产生式都遵循着以下格式：S→α
S：非终结符
α：一个终结符的串与/或非终结符，或empty空字符串
context-free意味着S可以被替换为α，不用考虑S的源头
通过CFL部分解决Balanced-Parenthesis问题
每一个右括号")i"都会被之前的左括号"(i"匹配，但是反之不成立
每一个callsite i，会标志call edge"(i"和 return edge")i"
其他的边标志为e
一个路径是realizable path如果这个路径的word是在language L里（realizable）
语法：
3、Overview of IFDS（IFDS框架）不是所有程序分析都可用这个来表达
使用图可达的一个程序分析框架（不是使用传播）
定义
Interprocedural全程序分析（过程间的）
Finite有限的
domain有限
Distributive可分配的
Subset子集
IFDS是为了在有穷域（finite domains）带有可分配（distributive）的流函数（flow function）的过程间（interprocedural）数据流分析
提供了meet-over-all-realizable-paths（MRP）的solution
只meet realizable paths，从而提高了精度
但同时提高了复杂度
MRP（Meet-Over-All-Realizable-Paths）
一个path p的function记为pfp，是p上所有边（有时是node）的流函数的组合
RPaths(start,n)意味着所有从start结点到n结点的realizable paths（path的word在language L(realizable)中）的集合
算法
输入：程序P，数据流分析问题Q
目的
为P创建一个supergraphG*并且为G*里的边定义flow functions基于Q
为P建立分解后的supergraphG#通过将流函数转化为representation relations(graphs)
Q可以被看作一个graph reachability problems被解决通过应用Tabulation algorithm在G#上（寻找MRP solutions）
令n为一个程序点，data fact d（IN和OUT里的元素）属于MRP_n，如果有一条realizable path在G#中可以从<Smain,0>到<n,d>
4、Supergraph and Flow Functions
Supergraph
IFDS中一个程序看为G* = （N*，E*），这被称为SuperGraph
G*包含了每一个方法的flow graph（所有的方法的flow graph构成了supergraph）
每一个流图Gp都有唯一的一个起点Sp和唯一的出口结点Ep
一个过程间call 会有一个call结点Callp，以及一个return-site结点Ret_p。可以通过这两个结点对call进行区分。
G*对每个函数调用都有三条边
一个程序内的从Callp到Retp的call-to-return-site的边
一个过程间的call-to-start边从Callp到被调用函数的sp
一个过程间的exit-to-return-site 边，从被调用函数的ep到Retp
设计流函数（Design Flow Functions）
应用：Possibly-uninitialized variables(可能may未初始化的变量)
对N*中的每个结点，判断可能未初始化的变量集合在执行到达n之前（应用）
创建supergraph
使用匿名函数
λEparam·Ebody
例子
5、Exploded Supergraph and Tabulation Algorithm：分解
创建分解的supergraph G#
每一个流函数可以使用带有2(D+1)点(最多(D+1)^2条边)来表示，其中D是数据流的facts的有限集
将信息流f转化为representation relation，Rf的定义如下：
必须有0-0的一条边
如果空输入也会有y，则0会有到y
空输入无法产生y，但是输入x会产生y，则x→y（常见于条件语句）
例子如下：
给定一个exploded supergraph使用tabulation algorithm去识别MRP solutions
蓝圈意味着是从<Smain,0>到该realizable的
tabulation algorithm
给定一个exploded supergraph G#，该算法可以获得MRP solution通过寻找所有的从<Smain,0>的realizability paths
让n为一个程序点，data fact d∈MRPn，只要有一个realizable path 在G#中从<Smain,0>到<n,d>(d的圆圈变成蓝色)
算法实现：
复杂度：O(ED^3)
E:边的数量
D:domain的size
核心工作算法
startnode肯定可达，只要之前的结点可达
处理exit node时，call-to-return匹配就开始工作，找到对应的call site p'(Callp',Callp'')并且之后开始寻找与之相对应的return-sites(Retp',Retp'')
实际上有一个summary edge从<Call,dm>到<Ret,dn>被加入，用于指示dn是reachable的从dm通过调用方法p'。这时，一些方法（例如p''）可能还没有开始处理，所以需要之后再去处理。通过这种reachable path可以减少冗余的工作
6、Understanding the distributivity of IFDS（IFDS的可分配性）
可以使用IFDS做常量传播吗？
常量传播有无穷的域
Distributivity
，并也可以
IFDS每次只能处理一个输入
这种处理不了，z的值取决于x和y
用图无法表达两个变量同时存在
常量传播时无法定义F如果只知道x或y的值
一个简单的规则去判断该分析能否使用IFDS
当给定一个statement S,处理S本身，如果还需要考虑其他多个input data facts去得到正确的outputs，则这个分析不是distributivity的并且不能使用IFDS来表达
在IFDS中，每一个data fact（circle小圆圈）和他的传播（edges）可以被独立地处理，并且不会影响最终结果的正确性
IFDS可以做指针分析吗？
只考虑四种情况：
可以看出少了连线，因为需要别名信息（alias information）
而别名信息需要考虑x,y两个输入，IFDS是处理不了的
所以指针分析不是distributive的
需要理解的问题
理解CFL-Reachability
理解IFDS的基本思想
理解什么问题可以被IFDS解决
soundiness
1、Soundness和soundiness
Soundness：Conservative approximation（保守估计）：分析会捕捉所有的程序行为或者分析结果会给所有的可能的程序结果建模
但真实的程序能否达到一个完全sound的analysis呢？：不能
为什么
静态分析的hard language feature
采用激进的保守的分析这些特征会导致分析结果太不精确，导致分析无用
结果（论文中）
可能直接省略了
对于这些hard feature还是under-approximated的
没有合适地处理好这些特征
这样会误导读者
非专家可能会觉得是sound的然后依赖这些结果
专家会难以推断分析结果如果没有明确解释如何对待这些feature
Soundiness
Sound：要求捕捉所有的动态行为
soundy：一个soundy analysis意味着analysis绝大部分是sound的，对hard/specific language features有well-identified unsound treatment。
捕捉所有的动态行为同时带有基于一定合理的规则unsoundly处理的具体的hard language features
unsound：在其设计里故意忽略特定的行为，为了更好的效率，精度和可达性
2、Hard language feature：java reflection（反射）（难以处理的语言特征）
reflection有class，field和method（Metaobject）
这些都是run-time时的，动态的值难以在静态时捕捉
为什么需要反射
松耦合
如何分析反射
String Constant analysis + Pointer Analysis
要将所有的东西都表示为string
但是如果string value是静态时无法分析的则会有问题
例如在配置文件，网络，命令行，加密等等
Type Inference + String analysis + Pointer Analysis
当string arguments不能静态获取时，可以通过在使用的points推导反射目标
assisted by dynamic analysis由动态分析来协助
最常用的，利用测试用例解反射对象
动态运行的结果交给静态分析用
简单准确（一定是真的），也挺快的
但是soundiness不行，这取决于test的个数
3、Hard Language feature：native code（本地代码调用、跨语言调用）
java底层的JNI会调用C/C++库
native声明，这些都是一些平台相关代码
跨语言（按照JNI的规则）
之后的代码是平台独立的
linux：os:write(c++)
Windows: WriteFile(c)
JNI(Java Native Interface)
什么是JNI
一个JVM的函数模块，允许java和本地代码（c/c++）进行交互
为什么需要JNI
需要一些平台依赖的特征（与OS进行交互）
什么文件系统，麦克风之类的
复用已有的库（大多数用c/c++写的）
为什么native code难以分析
JNI函数允许创建obj，访问field，调用method等等在本地代码中
如何处理native code
manually models the critical native code手动建模重要的本地代码
就用java代码替换native code
需要理解的问题
理解soundiness：目的和理论
理解为什么java reflection和native code难以分析
为什么要0→0
传统的数据流分析，为了判断data fact a是否在程序点p中，需要在分析结束之后看OUT
data fact是通过流函数的组合传播的，reachability是直接通过检索OUT的最终结果判断的
同样的情况在IFDS，data fact a是否在p中存在，取决于是否有一条路径从<Smain,0>（初始化节点）到<n4，a>，reachability是通过边的连接在"pasted"（粘贴的） representation relations判断的
λS.{a}意味着无论S的输入是什么，p都有a。但是如果没有0→0则会没有相对应的代表关系，就无法连接 或者"pasted"together。就像在传统的数据流分析中流函数无法组合一样
因此IFDS不能产生正确的solutions通过这种disconnected representation relations
需要"glue edge"0→0