程序分析笔记整理:Pointer Analysis(指针分析): Context Sensitivity(上下文敏感)
上下文敏感是Java语言提升指针分析精度的最有效方法!
主要分为四部分:
1.为什么需要?对比不敏感区别?
2.怎么做?
3.算法;
4.框架算法-2的变种均可实现;
可以在上图中看出,如果考虑上下文的话,此时x.get()返回的应该是1和2,而不应该是NAC(Not A Constant),就如下图所示。
什么是上下文以及上下文敏感(Context Sensitivty, CS)?
在动态运行时,一个方法被多次调用的时候会有不同的调用上下文(Calling Context),主要可以体现在每次调用时的参数不同、返回点也可能不同。
上下文敏感与不敏感(CI)的对比
Imprecision of Context Sensitivity:不同的上下文会导致不同的object的混合与传播,如果不做上下文敏感分析,会形成虚假的数据流;
CS对比CI来说开销更高,需要花费更多的时间;
CS的目的:区分不同情况下的数据流,来尽可能提升精度。
CS的策略(Rules):
Oldest Rule:使用call-site chain: this method, caller, caller's caller…类似于把调用栈抽象了。
Clone-based CS:每一个方法和变量都会被clone一份出来,然后具体分析。
CS-Heap:
- OO-Program,比如Java是Heap Sensitive的;
- 所以为了提升精度,CS将会用到堆抽象上:意思就是Object也要加上context,通常在object被allocate的时候加;
为什么加CS Heap会有用呢?
如上图,x.f是CS的,不同的newX的context导致这个field会有不同,如果不考虑CS的话,还是会导致mixed的情况,如下图所示:
动态运行时,x1与x2应该指向不同的对象,但是如果用CI Heap的话,那么x1与x2会指向同一个对象o8,从而产生了虚假的数据流o2,注意这里是变量有上下文的,所以n1与n2会指向不同的对象;
上图是采用了CS Heap来对这个程序进行分析,对o8对象加一个context,消除了虚假的数据流。
CI+CS Heap并没有起到效果。
下面是一些记号:
注意这里field不需要C,因为它挂靠在某个Object上,只需要关注Object即可。
Select通过传入所在方法上下文、Callsite、CS的receive-object,调用方法的信息,然后来查找构造所需要的上下文。注意传参的时候只会传递给特定上下文(ct),比如这里的context 2与3,避免产生mixed,返回值的处理也是如此。
实现指针分析最关键的就是写这些Rules。