【课程笔记】南大软件分析课程8—指针分析-上下文敏感（...

roger

【课程笔记】南大软件分析课程8—指针分析-上下文敏感（...

目录：

1.介绍2.Context Sensitive Pointer Analysis：Rules3.Context Sensitive Pointer Analysis：Algorithms4.Context Sensitivity Variants—上下文的选取

重点：

·上下文敏感指针分析的完整算法（一般其他教程中很少涉及到）。·上下文敏感概念，堆对象的上下文敏感表示，上下文敏感指针分析的规则。·上下文的三种选择，以及效率、准确度的对比。

1.上下文不敏感的问题

说明：上下文敏感分析是对指针分析的准确性提升最有效的技术。

（1）问题

【课程笔记】南大软件分析课程8—指针分析-上下文敏感（...

8-1-1-上下文不敏感.png

问题：上下文不敏感时，分析常量传播这个问题，由于没有明确调用id()的上下文，会把不同的调用混合在一起，对id函数内的变量n只有一种表示（没有对局部变量进行区分），导致n指向的对象集合增大，将i识别为非常量NAC。实际上，x.get()的值只来自于One()对象，i应该是常量1。

解决：根据调用的上下文（主要有3种：如根据调用点所在的行数——call-site sensitivity）来区分局部变量。

（2）上下文敏感分析

概念：

·call-site sensitivity (call-string)：根据调用点位置的不同来区分上下文，3：id(n1) / 4：id(n2)。·Cloning-Based Context Sensitivity：每种上下文对应一个节点，标记调用者行数。克隆多少数据，后面会讨论。

【课程笔记】南大软件分析课程8—指针分析-上下文敏感（...

8-1-2-上下文敏感.png　　

·Context-Sensitive Heap：面向对象程序（如Java）会频繁修改堆对象，称为heap-insensitive。所以不仅要给变量加上下文，也要给堆抽象加上下文，称为heap context（本课程是基于allocate-site来进行堆抽象的）。

堆抽象上下文示例：

【课程笔记】南大软件分析课程8—指针分析-上下文敏感（...

8-1-3-堆抽象上下文敏感.png

堆抽象上下文不敏感：如果不区分8 X x = new X();调用的堆抽象的上下文，导致只有1个o8.f，把两个上下文调用产生的o8.f指向集合都合并了，得出了o8.f的错误指向的结果。

堆抽象上下文敏感：用不同的调用者来区分堆抽象，如3:o8、4:o8是不同的堆抽象。所以说，既要根据上下文的不同来区分局部变量，也要区分堆抽象，例如：3:p是给变量加上下文，3:o8是给堆抽象加上下文。

2.Context Sensitive Pointer Analysis：Rules

标记：根据调用者的行数来区分不同上下文，只要区分了函数、变量、堆对象，就能够区分实例域、上下文敏感的指针（变量+对象域）。C—上下文（暂时用调用点的行数表示），O—对象，F—对象中的域。

【课程笔记】南大软件分析课程8—指针分析-上下文敏感（...

8-2-1-标记.png

规则：跟之前区别不大，只是增加了个上下文标记，注意load表示和之前有区别。

【课程笔记】南大软件分析课程8—指针分析-上下文敏感（...

8-2-2-规则.png

call指令规则：

·上下文对于Dispatch(oi, k)（找目标函数）没有影响，根据oi指向和函数签名k找到目标函数。select(c, l, c':oi, m)根据调用时的信息来给调用目标函数选择上下文（c是调用者的上下文，l是调用者的行号，c':oi是x对象的指向集合，m是目标函数），c^t^表示目标函数的上下文（后面会将如何Select如何选择上下文）。c是可以累积的，一连串的调用，上下文将用一连串的行数来表示。·传递this变量：c^t^:mthis是目标函数c^t^:m的this变量·传递参数：c^t^:mpj是目标函数c^t^:m的第j个形参。·传递返回值：c^t^:mret是目标函数c^t^:m的返回值

【课程笔记】南大软件分析课程8—指针分析-上下文敏感（...

8-2-3-call规则.png3.Context Sensitive Pointer Analysis：Algorithms

区别：和过程间指针分析相比，仍然分为两个过程，分别是构造PFG和根据PFG传递指向信息。主要区别是添加了上下文。

PFG构造：边添加规则和之前一样，Assign、Store、Load、Call，Call需要加参数传递、返回值传递的边。

【课程笔记】南大软件分析课程8—指针分析-上下文敏感（...

8-3-1-上下文敏感PTA算法.png

符号：

·S：可达语句的集合（就是RM中的语句）·Sm：函数m中的语句·RM：可达函数的集合·CG：调用图的边

算法：被调用函数的上下文暂时用c^t^表示，之后会解释Select()函数。

1.先处理New、Assign指令。AddReachable(c:m)只多了上下文。2.遍历WL，Propagate()和原来相同。3.处理Store、Load指令，AddEdge()只多了上下文。4.处理Call指令，ProcessCall()，多了一行c^t^=Select(c,l,c':oi,m)，在找到调用目标函数之后，需选择被调用的函数的上下文。

4.Context Sensitivity Variants—上下文的选取

上下文的选取主要采用3类：

·Call-Site Sensitivity·Object Sensitivity·Type Sensitivity·...

说明：Select(c,l,c':oi,m)，c—调用者上下文，l—调用者，c':oi—接收对象（含堆的上下文信息）。

（1）Call-Site Sensitivity

原理：又称为k-call-site sensitivity / k-CFA，不断添加调用行号。1991年Olin Shivers[1]提出。

[size=1em]Select(c,l,c':oi,m) = (l',...,l'', l)

问题：如果函数调用自身，导致无限递归，如何限制上下文长度？

解决：k-limiting Context Abstraction。只取最后k个上下文，通常取k<=3。例如，函数的上下文通常取2，堆上下文通常取1。

示例：采用1-Call-Site。

interfaceNumber{ intget(); }
　　classOneimplementsNumber{ publicintget() { return1; }}
　　classTwoimplementsNumber{ publicintget() { return2; }}
　　1class C {
　　2staticvoid main() {
　　3             C c = new C();
　　4             c.m();
　　5}
　　6
　　7Number id(Number n) {
　　8return n;
　　9}
　　10void m() {
　　11Number n1,n2,x,y;
　　12          n1 = newOne();
　　13          n2 = newTwo();
　　14          x = this.id(n1);
　　15          y = this.id(n2);
　　16          x.get();
　　17}
　　18}
　　

WL正处理PFG指针集RMCG处理语句算法语句
1{[]:C.main()}3AddReachable(m^entry^)—加入RM
2[<[]:c, {o3}>]3AddReachable(m^entry^)—处理New
3[]<[]:c, {o3}>pt([]:c) ={o3}；While开头，Propagate()—遍历WL更新指针
4[⟨[4]:C.mthis, {o3}⟩]4ProcessCall()—this指针加入WL
5[⟨[4]:C.mthis, {o3}⟩]{[ ]:4 → [4]:C.m()}；ProcessCall()——函数加入CG
6[⟨[4]:C.mthis, {o3}⟩，⟨[4]:n1, {o12⟩，⟨[4]:n2, {o13⟩]没有参数/返回值{[]:C.main(), [4]:C.m()}12,13ProcessCall():AddReachable(m)处理m函数中的New
7[⟨[4]:n1, {o12⟩，⟨[4]:n2, {o13⟩]⟨[4]:C.mthis, {o3}⟩pt([]:c) ={o3}；pt([4]:C.mthis)={o3}；While开头，Propagate()—遍历WL更新指针
8[⟨[4]:n1, {o12⟩，⟨[4]:n2, {o13⟩]ProcessCall():处理m中的this调用
9[⟨[4]:n1, {o12⟩，⟨[4]:n2, {o13⟩]14ProcessCall():Select(c,l,c':o^i^)选择上下文c^t^=[14]
10[⟨[4]:n1, {o12⟩，⟨[4]:n2, {o13⟩]{[]:C.main()， [4]:C.m()，[14]:C.id(Number)}{[ ]:4 → [4]:C.m()；[4]:14 → [14]:C.id(Number)}；ProcessCall():AddReachable([14]:C.id(Number))
11[⟨[4]:n1, {o12⟩，⟨[4]:n2, {o13⟩][4]:n1→[14]:n→[4]:x；ProcessCall():AddEdge()参数边/返回值边
12[⟨[4]:n1, {o12⟩，⟨[4]:n2, {o13⟩][4]:n1→[14]:n→[4]:x；[4]:n2→[15]:n→[4]:y；{[]:C.main()， [4]:C.m()，[14]:C.id(Number)，[15]:C.id(Number)}{[ ]:4 → [4]:C.m()；[4]:14 → [14]:C.id(Number)，[4]:15 → [15]:C.id(Number)}；15ProcessCall()同理
13[][⟨[4]:n1, {o12⟩，⟨[4]:n2, {o13⟩]

【课程笔记】南大软件分析课程8—指针分析-上下文敏感（...

8-4-1-PFG.pngWhile开头—遍历WL更新指针
14[]

【课程笔记】南大软件分析课程8—指针分析-上下文敏感（...

8-4-2-RM.png

【课程笔记】南大软件分析课程8—指针分析-上下文敏感（...

8-4-3-CG.png16While开头，ProcessCall()—处理x.get()

上下文不敏感vs上下文敏感（1-Call-Site）：

【课程笔记】南大软件分析课程8—指针分析-上下文敏感（...

8-4-4-不敏感vs敏感.png（2）Object Sensitivity

原理：针对面向对象语言，用receiver object来表示上下文。对比1层的调用点敏感和对象敏感，时间和准确性上对象敏感显然更优，这是由面向对象语言的特点所确定的。

[size=1em]Select(c,l,c':oi,m) = [oj, ... , ok, oi] （c' = [oj, ... , ok]）

示例：选取1-object，最终pt(x)=o3。

【课程笔记】南大软件分析课程8—指针分析-上下文敏感（...

8-4-5-对象上下文示例.png

对比：对比1-Call-Site和1-object上下文，在这个示例中1-object明显更准确。原因是面向对象语言的特性，多态性产生很多继承链，一层一层调用子对象，其中最关键的是receiver object，receiver object决定了调用者的根源。本例有多层调用，若采用2-Call-Site就不会出错。

【课程笔记】南大软件分析课程8—指针分析-上下文敏感（...

8-4-6-callsite_vs_object.png

【课程笔记】南大软件分析课程8—指针分析-上下文敏感（...

8-4-6-callsite_vs_object2.png

示例2：在本示例中，1-Call-Site明显更准确。因为同一个receiver object用不同参数多次调用了子函数，导致局部变量无法区分。

【课程笔记】南大软件分析课程8—指针分析-上下文敏感（...

8-4-6-callsite_vs_object3.png

结论：所以理论上，对象敏感与callsite敏感的准确度无法比较。但是对于面向对象语言，对象敏感的准确度要优于callsite敏感。

（3）Type Sensitivity

原理：牺牲精度，提高速度。基于创建点所在的类型，是基于对象敏感粗粒度的抽象，精度较低。

[size=1em]Select(c,l,c':oi,m) = [