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

Tattoo

发布日期: 2020-07-19 16:50:53 浏览量: 78
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

最近在看“静态分析”技术相关的文章,看到这个系列的笔记和视频教程,感觉介绍得很好,通俗易懂,而且还比较详细,故转载分享,同时也备份保留下,方便自己今后阅读。(PS:建议大家一边看笔记,一边看视频,加深理解)
原作者:bsauce
原文链接:https://www.jianshu.com/p/5ab79839f686

首先非常感谢南京大学李樾谭添老师的无私分享,之前学习程序分析是看的北大熊英飞老师的ppt,但是很多地方没看懂,正如李樾老师所说的那样,熊英飞老师的授课涵盖非常广,不听课只看ppt的话,理解起来还是很有难度的。但李樾老师的视频就讲解的非常易懂,示例都是精心挑选的,所以墙裂推荐。

推送门南大课件 南大视频课程 北大课件


目录

  1. 介绍
  2. Context Sensitive Pointer Analysis:Rules
  3. Context Sensitive Pointer Analysis:Algorithms
  4. Context Sensitivity Variants—上下文的选取

重点

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

1.上下文不敏感的问题

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

(1)问题

问题:上下文不敏感时,分析常量传播这个问题,由于没有明确调用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:每种上下文对应一个节点,标记调用者行数。克隆多少数据,后面会讨论。

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

堆抽象上下文示例

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

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

2.Context Sensitive Pointer Analysis:Rules

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

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

call指令规则

  • 上下文对于Dispatch(oi, k)(找目标函数)没有影响,根据oi指向和函数签名k找到目标函数。select(c, l, c’:oi, m)根据调用时的信息来给调用目标函数选择上下文(c是调用者的上下文,l是调用者的行号,c’:oi是x对象的指向集合,m是目标函数),ct表示目标函数的上下文(后面会将如何Select如何选择上下文)。c是可以累积的,一连串的调用,上下文将用一连串的行数来表示。

  • 传递this变量:ct:mthisc^t:m_{this}是目标函数ct:mc^t:m的this变量

  • 传递参数:ct:mpjc^t:m_{pj}是目标函数ct:mc^t:m的第j个形参。

  • 传递返回值:ct:mretc^t:m_{ret}是目标函数ct:mc^t:m的返回值

3.Context Sensitive Pointer Analysis:Algorithms

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

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

符号

  • S:可达语句的集合(就是RM中的语句)
  • Sm:函数m中的语句
  • RM:可达函数的集合
  • CG:调用图的边

算法:被调用函数的上下文暂时用ct表示,之后会解释Select()函数。

  1. 先处理New、Assign指令。AddReachable(c:m)只多了上下文。
  2. 遍历WL,Propagate()和原来相同。
  3. 处理Store、Load指令,AddEdge()只多了上下文。
  4. 处理Call指令,ProcessCall(),多了一行ct=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提出。

Select(c,l,c’:oi,m) = (l’,…,l’’, l)

问题:如果函数调用自身,导致无限递归,如何限制上下文长度?

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

示例:采用1-Call-Site。

  1. interface Number { int get(); }
  2. class One implements Number { public int get() { return 1; }}
  3. class Two implements Number { public int get() { return 2; }}
  4. 1 class C {
  5. 2 static void main() {
  6. 3 C c = new C();
  7. 4 c.m();
  8. 5 }
  9. 6
  10. 7 Number id(Number n) {
  11. 8 return n;
  12. 9 }
  13. 10 void m() {
  14. 11 Number n1,n2,x,y;
  15. 12 n1 = new One();
  16. 13 n2 = new Two();
  17. 14 x = this.id(n1);
  18. 15 y = this.id(n2);
  19. 16 x.get();
  20. 17 }
  21. 18 }
WL 正处理 PFG 指针集 RM CG 处理语句 算法语句
1 {[]:C.main()} 3 AddReachable(mentry)—加入RM
2 [<[]:c, {o3}>] 3 AddReachable(mentry)—处理New
3 [] <[]:c, {o3}> pt([]:c) ={o3}; While开头,Propagate()—遍历WL更新指针
4 [⟨[4]:C.mthis, {o3}⟩] 4 ProcessCall()—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,13 ProcessCall():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⟩] 14 ProcessCall():Select(c,l,c’:oi)选择上下文ct=[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)}; 15 ProcessCall()同理
13 [] [⟨[4]:n1, {o12⟩,⟨[4]:n2, {o13⟩] While开头—遍历WL更新指针
14 [] 16 While开头,ProcessCall()—处理x.get()

上下文不敏感vs上下文敏感(1-Call-Site)

(2)Object Sensitivity

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

Select(c,l,c’:oi,m) = [oj, … , ok, oi] (c’ = [oj, … , ok])

示例:选取1-object,最终pt(x)=o3pt(x)=o_3

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

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

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

(3)Type Sensitivity

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

Select(c,l,c’:oi,m) = [𝑡′,…,𝑡′′,InType(𝑜𝑖)] 其中𝑐′ = [𝑡′, … , 𝑡′′]

(4)总体对比

精度:object > type > call-site

效率:type > object > call-site

本课老师提出选择上下文的方法,对代码的特点有针对性的选择上下文方法,见A Principled Approach to Selective Context Sensitivity for Pointer Analysis。厉害了!

上传的附件

发送私信

人生最好的三个词:久别重逢,失而复得,虚惊一场

93
文章数
34
评论数
最近文章
eject