【课程笔记】南大软件分析课程7——指针分析基础

Tattoo

发布日期: 2020-07-19 11:55:31 浏览量: 98
评分:
star star star star star star star star star star
*转载请注明来自write-bug.com

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

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

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


目录

  1. 指针分析规则
  2. 如何实现指针分析
  3. 指针分析算法
  4. 指针分析如何处理函数调用(过程间指针分析)

重点

理解指针分析的规则、指针流图PFG、指针分析算法。

理解指针分析调用函数的规则、过程间指针分析算法、实时调用图构建。

1.指针分析规则

首先分析前4种语句:New / Assign / Store / Load。

指针分析的域和相应的记法:变量/函数/对象/实例域/指针,用pt表示程序中的指向关系(映射)。

规则:采用推导形式,横线上面是条件,横线下面是结论。

  • New:创建对象,将new T()对应的对象oi加入到x的指针集。

  • Assign:将y的指针集加入到x对应的指针集。

  • Store:让oi的field指向oj。

  • Load:Store的反操作。

2.如何实现指针分析

算法要求:全程序指针分析,要容易理解和实现。

本质:在指针(变量/域)之间传递指向信息。Andersen-style分析(很普遍)——很多solving system把指针分析看作是一种包含关系,eg,x = y,x包含y。

问题:当一个指针的指向集发生变化,必须更新与它相关的其他指针。如何表示这种传递关系?PFG。

PFG:用指针流图PFG来表示指针之间的关系,PFG是有向图

  • Nodes:Pointer = V U (O x F) 节点n表示一个变量或抽象对象的域。
  • Edges:Pointer X Pointer 边x -> y 表示指针x指向的对象may会流入指针y。

Edges添加规则:根据程序语句 + 对应的规则。

示例:

PTA步骤

  1. 构造PFG(根据以上示例,PFG也受指向关系影响)

  2. 根据PFG传播指向信息

3.指针分析算法

(1)过程内PTA算法

符号

  • S:程序语句的集合。
  • WL:Work list,待合并的指针信息,二元组的集合,<指针n,指向的对象集合pts>。pts将被加入到n的指向集pt(n)中。
  • PFG:指针流图。

步骤:对每种语句都是基于第1小节的规则来实现。

  1. 对S中所有类似New x = new T()的语句,将<x, {oi}>加入到WL。

  2. 对S中所有类似Assign x = y的语句,调用AddEdge()y -> x加入到PFG,<x, pt(y)>加入到WL(传播指向信息)。

  3. 遍历WL,取一个元素<n, pts>,除去pts中与pt(n)重复的对象得到Δ\Delta,调用Propagate(n,Δ\Delta)将Δ\Delta加入到pt(n),且取出PFG中所有n指向的边n->s,将<s, pts>加入到WL(根据PFG将指向信息传递给同名指针)。

  4. 如果n表示一个变量x(x跟Store/Load指令相关),对Δ\Delta中的每个对象oi。对S中所有类似 Store x.f = y 的语句,调用AddEdge()y -> oi.f加入到PFG,<oi.f, pt(y)>加入到WL(传播指向信息);对S中所有类似Load y = x.f的语句,调用AddEdge()oi.f -> y加入到PFG,<y, pt(oi.f)>加入到WL(传播指向信息)。

问题

  1. 为什么要去重?避免冗余,英文叫做Differential propagation差异传播。

  2. 指针集用什么数据结构存储?混合集 Hibra-set,集合元素小于16个用hash set,大于16个用big-rector 位存储。

  3. 开源项目有哪些?SootWALAChord

(2)示例

  1. 1 b = new C();
  2. 2 a = b;
  3. 3 c = new C();
  4. 4 c.f = a;
  5. 5 d = c;
  6. 6 c.f = d;
  7. 7 e = d.f;

4.指针分析如何处理函数调用

构造调用图技术对比

  • CHA:基于声明类型,不精确,引入错误的调用边和指针关系。

  • 指针分析:基于pt(a),即a指向的类型,更精确,构造更准的CG并对指针分析有正反馈(所以过程间指针分析和CG构造同时进行,很复杂)。

  1. void foo(A a) { // pt(a) = ???
  2. ...
  3. b = a.bar(); // pt(b) = ??? 把a的指向分析清楚了,就能确定a.bar()到底调用哪个对象的bar()函数,那么b的指向也明确了。
  4. ...
  5. }

(1)调用语句规则

call语句规则:主要分为4步。

  1. 找目标函数m:Dispatch(oi, k)——找出pt(x),也即oi类型对象中的k函数。

  2. receiver object:把x指向的对象(pt(x))传到m函数的this变量,即mthism_{this}

  3. 传参数:pt(aj), 1<=j<=n 传给m函数,即p(mpj)p(m{pj}), 1<=j<=n。建立PFG边a1>ma_1->m{p1},…,an->m{pn}。

  4. 传返回值pt(mret)pt(m{ret})传给pt(r)。建立PFG边r<mr<-m{ret}。

问题:为什么PFG中不添加x>mthisx->m{this}边?因为mm{this}只和自己这个对象相关,而可能有pt(x)={new A, new B, new C},指定对象的x只流向对应的对象,是无法跨对象传递的。

(2)过程间PTA算法

问题:由于指针分析和CG构造互相影响,所以每次迭代只分析可达的函数和语句。然后不断发现和分析新的可达函数。

可达示例

算法:黄色背景的代码是和过程内分析不同的地方。

符号

  • mentry:入口main函数

  • Sm:函数m中的语句

  • S:可达语句的集合(就是RM中的语句)

  • RM:可达函数的集合

  • CG:调用图的边

步骤:基于调用规则来实现。

  1. 首先调用AddReachable(mentry)AddReachable(m^{entry}),将入口函数mentrym^{entry}的语句加到S中。处理New x = new T()语句,把<x, {oi}>加入到WL;处理Assign x = y语句,调用AddEdge(y, x)加入边到PFG。

  2. 跟过程内指针分析一样,遍历WL,取一个元素<n, pts>,除去pts中与pt(n)重复的对象得到Δ\Delta,调用Propagate(n,Δ\Delta)将Δ\Delta加入到pt(n),且取出PFG中所有n指向的边n->s,将<s, pts>加入到WL(根据PFG将指向信息传递给同名指针)。

  3. 如果n表示一个变量x(x跟Store/Load指令相关),对Δ\Delta中的每个对象oi。对S中所有类似 Store x.f = y 的语句,调用AddEdge()y -> oi.f加入到PFG,<oi.f, pt(y)>加入到WL(传播指向信息);对S中所有类似 Load y = x.f 的语句,调用AddEdge()oi.f -> y加入到PFG,<y, pt(oi.f)>加入到WL(传播指向信息)。

  4. 最后调用ProcessCall(x, oi),处理与x相关的call指令。取出S中类似r = x.k(a1,...,an)的调用语句L,首先调用Dispatch(oi, k)解出调用的目标函数m,把<mthis, {oi}>加入到WL(传递接收对象,上下文敏感分析将用到),将L->m这条调用边加入到CG;调用AddReachable(m)将新的语句加入到S,并处理New/Assign语句;调用AddEdge()将实参->形参返回值->r边加入到PFG(传递参数、返回值),并将<形参,pt(实参)><r,pt(返回值)>加入到WL。

问题:为什么ProcessCall(x, oi)中,要判断L->m这条边是否已经加入到CG?因为x可能指向多个对象,就会多次处理L这个调用指令,可能x中别的对象oj早就已经将这条边加入进去了。

(3)示例

  1. class A {
  2. static void main(){
  3. A a = new A();
  4. A b = new B();
  5. A c = b.foo(a);
  6. }
  7. A foo(Ax){...}
  8. }
  9. class B extends A {
  10. A foo(A y) {
  11. A r=newA();
  12. return r;
  13. }
  14. }
WL 正处理 PFG 指针集 RM CG 语句 算法语句
1 [] {} {} {} 初始化
2 [] {A.main()} 1,2 AddReachable(mentry)
3 [<a,{o3}>, <b,{o4}>] 3,4
4 [<b,{o4}>] <a,{o3}> pt(a)={o3}; while开头
5 [] <b,{o4}> pt(b)={o4} while开头
6 [] 5 ProcessCall(b, o4)
7 [<B.foothis, {o4}>] {5->B.foo(A)} m=Dispatch(o4, foo())=B.foo();添加到调用图
8 [<B.foothis, {o4}>, <r, o11>] {A.main(), B.foo()} AddReachable(B.foo());添加到可达函数
9 [<B.foothis, {o4}>, <r, o11>, <y, {o3}>] {a->y, r->c} AddEdge();添加参数边、返回值边
10 [<r, o11>, <y, {o3}>] <B.foothis, {o4}> pt(B.foothis)={o4}; while开头,B.foothis没有调用任何函数
11 [<y, {o3}>, <c, {o11}>] <r, o11> pt(r)={o11}; while开头
12 <y, {o3}>, <c, {o11}> pt(y)={o3};pt(c)={o11} while开头

如果是CHA的话,CG={5->B.foo(A), 5->A.foo(A)},错误识别为调用边。

结果:

问题:没有入口函数的?如对库函数处理,生成调用库函数的程序。

上传的附件

发送私信

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

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