【课程笔记】南大软件分析课程6——指针分析介绍（课时8）

roger

               

【课程笔记】南大软件分析课程6——指针分析介绍（课时8）

目录：

1.Motivation2.指针分析介绍3.影响指针分析的关键要素4.分析哪些语句

重点：

什么是指针分析？影响指针分析的关键因素是什么？指针分析要分析哪些指令？

1.Motivation

指针分析必要性：

【课程笔记】南大软件分析课程6——指针分析介绍（课时8）

6-1-PTA-motivation.png2.指针分析

目标：分析程序指针可以指向哪些内存。对于Java等面向对象语言，主要分析指针指向哪个对象。

说明：指针分析属于may analysis，分析的结果是某指针所有可能指向哪些对象，是个over-approximation集合。

示例：面向对象语言中的指针指向问题。对于setB()函数，this指向new A()，因为是调用者是a.setB()；setB()中的b是x传过来的，所以b指向new B()，A.b指向 new B()。

【课程笔记】南大软件分析课程6——指针分析介绍（课时8）

6-2-1-PTA示例.png

区别：

·指针分析：分析指针所有可能指向的对象。·别名分析：分析两个指针是否指向相同的对象，可通过指针分析来推导得到。

应用：基本信息（别名分析/调用图），编译优化（嵌入虚拟调用），漏洞（空指针），安全分析（信息流）。

3.影响指针分析的关键要素

指标：精度（precision）& 效率（efficiency）。

影响因素：本课程，我们主要分析分配点的堆抽象技术、上下文敏感/不敏感、流不敏感、全程序分析。

因素问题选项
Heap abstraction如何建模堆内存？· Allocation-site · Storeless
Context sensitivity如何建模调用上下文？· Context-sensitive · Context-insensitive
Flow sensitivity如何建模控制流？· Flow-sensitive · Flow-insensitive
Analysis scope分析哪部分程序？· Whole-program · Demand-driven（1）堆抽象（内存建模）

问题：程序动态执行时，堆对象个数理论上是无穷无尽的，但静态分析无法处理这个问题。所以为保证指针分析可以终止，我们采用堆抽象技术，将无穷的具体对象抽象成有限的抽象对象。也即，将有共性的对象抽象成1个静态对象，从而限制静态分析对象的个数。

// 示例
　　for(...) {
　　A a = new A();
　　}
　　

技术概览：

【课程笔记】南大软件分析课程6——指针分析介绍（课时8）

6-3-1-堆抽象技术概览.png

我们只学习Allocation-Site技术，最常见也最常被使用。

Allocation-Site原理：将动态对象抽象成它们的创建点（Allocation-Site），来表示在该点创建的所有动态对象。Allocation-Site个数是有限的。

示例：循环创建了3个对象，我们用O2来抽象表示这3个动态对象。

【课程笔记】南大软件分析课程6——指针分析介绍（课时8）

6-3-2-堆抽象示例.png（2）上下文敏感 Context Sensitivity

问题：考虑是否区分不同call-site对同一函数的调用。

·Context-sensitive：根据某函数调用上下文的不同，多次分析同一函数。·Context-insensitive：每个函数只分析一次。

【课程笔记】南大软件分析课程6——指针分析介绍（课时8）

6-3-3-上下文敏感示例.png（3）流敏感 Flow Sensitivity

问题：考虑语句顺序（控制流）的影响 vs 把程序当做无序语句的集合。

方法：流敏感会在每个程序点都保存一份指针指向关系映射，而流不敏感则对整个程序保存一份指向关系映射。

说明：目前流敏感对Java提升不大，不过在C中很有效，本课程分析的是Java，所以重点讨论流不敏感技术。

指针分析示例：

【课程笔记】南大软件分析课程6——指针分析介绍（课时8）

6-3-4-流敏感示例.png（4）分析范围 Analysis Scope

问题：分析程序的哪一部分？

·Whole-program 全程序：分析全程序的指向关系。·Demand-driven 需求驱动：只分析影响特定域的指针的指向关系。

4.分析哪些语句

问题：哪些语句会影响指针指向，那就只分析这些语句。

Java指针类型：

1.Lacal variable: x2.Static field:C.f （有时称为全局变量）——不分析3.Instance field: x.f （对象的field）4.Array element: array ——不分析，因为静态分析无法确定下标，所以将array中所有成员映射到一个field中，等价于Instance field，所以不重复分析。如下图所示：

【课程笔记】南大软件分析课程6——指针分析介绍（课时8）

6-4-1-数组处理.png

影响指针指向的语句：

1.New: x = new T()2.Assign：x = y3.Store：x.f = y4.Load：y = x.f5.Call：r = x.k(a,...)·Static call：C.foo()·Special call：super.foo() / x.<init>() / this.privateFoo()·Virtual call：x.foo()

复杂的内存访问可以通过引入临时变量，转化为三地址代码：

x.f.g.h = y;
　　// 转化为
　　t1 = x.f;
　　t2 = t1.g;
　　t2.h = y;
　　

参考

软件分析笔记4：指针分析[1]

References

[1] 软件分析笔记4：指针分析: https://www.cnblogs.com/crossain/p/12767883.html

---