软件分析笔记4：指针分析
本文是对于南京大学李樾和谭添老师开设的《软件分析》课程视频的笔记总结。相对应的视频在可以再B站上观看。
1.Motivation
上节回顾
在笔记3里我学习了CHA有关的概念和用法，用一个例子来复习一下：
如上图所示，定义了一个接口Number，然后有三个类继承了该接口，实例化了一个Number对象n，那么利用CHA可以找到3个调用目标（因为n是Number类型，所以要去Number和所有Number的子类中寻找对应的调用目标），对于常量传输，x的值是NAC,因为调用了三个方法，返回的值可能是{0,1,2}，很明显这个结果是不准的因为实际上只会调用One中的方法，如果使用指针分析的方法则可以得到更精确的结果。
2.Introduction to pointer analysis
指针分析是最基础的静态分析，它最早的研究是从40多年之前开始的，它回答了程序中的指针指向哪个内存的问题，Java语言中的指针分析指的是一个指针指向程序中的哪个对象（Object)的问题.通常指针分析是一个may-analysis，分析的结果通常是一个指针可能指向哪些对象。
我们用一个实例来解释指针分析的内容：
如上图所示，对于左边的程序代码，通过分析前两句代码我们可以得到变量a指向new A(),变量x指向new B(),对于a.setB()方法很明显是指向A类中的对应方法，而对于setB()方法，方法中的this会指向new A()因为foo()中是a调用的setB()方法，而方法中的形参b则是由实参x传给他的，指向new B();因此对于setB方法中的“this.b = b;”,是new A.b指向了new B。
指针分析的输入就是一个程序代码，然后输出一个指向关系。
注意
指针分析和别名分析（aliases)有很多相似之处，但是指针分析并不等于别名分析，二者区别如下：
-
指针分析解答的是一个指针可能指向哪个对象的问题
-
别名分析解答的是两个指针是否能指向同一个对象的问题，如果是就认为二者互为别名。如下图所示：
- 别名分析可以通过指针分析推导出来。
指针分析的应用
- 可以用来计算其他基本信息（别名分析，调用图...)
- 编译优化
- 找Bug
- 安全性分析
- 等等......
指针分析是最基础的静态分析之一，也是很多其他分析的基础。
3.Key factors of pointer analysis
指针分析是一个非常复杂的系统，指针分析有两个指标即精度（precision)和速度（efficiency)，我们需要根据实际情况在这两者中进行取舍。为了方便做分析，我们需要了解一些影响指针分析的关键要素。有代表性的关键要素的简图如下：
3.1Heap Abstraction堆抽象
解决在指针分析中对内存建模的问题，在程序动态执行时，堆当中对象的数量理论上是无穷无尽的，但是静态分析没办法处理这个问题，所以为了保证指针分析可以终止，我们采用了堆抽象技术，将无穷的具体对象抽象成有限的抽象对象。
如上图所示，左边是动态的执行过程，右边使我们的静态分析，我们将有共性的部分动态对象抽象成一个静态对象，这样就可以限制静态分析对象的个数。
堆抽象有很多复杂的分支，如下图所示：
从图上可知堆抽象大概有两个流派，我们只学习Allocation-Site技术，因为它最常见也最常被使用。
Allocation-Site的思想就是将动态对象抽象成它们的创建点（Allocation-Site），它为程序中没一个创建点抽象出一个抽象点来表示在这个点创建的所有动态对象。一个简单示例如下：
如图所示，我们用了一个for循环创建了3个动态对象，在这里为了方便静态分析，我们用创建点O2来抽象代表这三个动态对象。
3.2Context sensitivity上下文敏感
解答了指针分析中如何调用上下文进行建模的问题。分为两种就是上下文敏感和上下文不敏感。
如上图所示，上下文敏感的思想就是在静态分析中会模拟动态分析中上下文的变化，对于一个方法不同的上下文分别分析。下图中因为两种方法是由不同的对象调用的（a和b)，因此我们将它们区分为两种，即图中的Context1和Context2，静态分析中也会分别分析，
上下文不敏感就是不会将不同上下文区分开，如下图所示就是将不同上下文都采用同一个方法，这样会丢失精度。
我们先从上下文不敏感开始分析。
3.3Flow Sensitivity流敏感
即解决对控制流分建模问题，跟上下文敏感一样，流敏感也分为流敏感和流不敏感两种。
流敏感就是对于程序中语句的顺序是敏感的，目前我们学到的所有数据流分析都是流敏感的。如下图所示，流敏感会记录每一步各个值的变化。
流非敏感就是会忽略掉语句之间的顺序（控制流顺序），一个map就记录了程序中所有的可能信息，对于上图中的代码，分析结果为：
因此流不敏感会丢失精度，要注意流敏感对不同的编程语言重要程度是不一样的，C中很有效，JAVA等则相对不明显，因此我们分析中多实用流不敏感的方式。
3.4Analysis Scope
即解决要分析程序哪个部分的问题，分为whole-program和demand-driven两种。
-
whole-program就是分析出程序中所有指针的指向
-
demand-driven就是分析出程序中特定某些部分指针的指向，举个例子就是在上面的程序中，如果我们要特定的分析第五行的代码，那么我们只需要z的信息就够了。通常来说驱动分析工作量相对于全程序分析要小，但是实际应用不一定更好。
-
我们优先学习全程序分析
4.Concerned Statements
指针分析的目标只关注能直接影响到指针指向的语句。
Java中的指针：
- Local variable:x
- Static field:C.f(有时候被称为全局变量)
- instance field:x.f（对象的field)
- Array element:array[i] （静态分析往往没办法确定下标，一般是将整个array存到一个field中）如下图，就是创建了一个数组对象，存储和读取都是对这个对象进行的。
直接影响到指针指向的语句
一般分为以下五种语句：
- New: x = new T()
- Assign: x = y
- Store: x.f = y
- Load: y = x.f
- Call: r = x.k(a,...)
- Static call C.get()
- Special call super.foo()
- Virtual call x.get()
5.指针分析的规则
为了循序渐进，在指针分析中，我们会先分析上面提到的五种语句中的前四种。
5.1指针分析的域和相对应的记法
如上图所示，用pt来表示程序中的指向关系（映射），由指针指向相应的指针集。#08 8530
5.2规则
如上图，该图采用了推导式的形式，横线上面的为条件，横线下面的为结论，横线上为空则代表无条件。
New
对于创建对象语句，我们就将new T()对应的对象oi加入到x的指针集中，如下图所示：
Assign
经过上图中语句，就是将y对应的指针集加入到x对应的指针集中。
Store
就是让OI的field指向Oj,实际上跟Assign很像。
Load
实际上就是Store的反操作。
