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

Tattoo

发布日期: 2020-07-17 11:33:24 浏览量: 67
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

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

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

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


目录

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

重点

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

1.Motivation

指针分析必要性

2.指针分析

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

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

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

区别

  • 指针分析:分析指针所有可能指向的对象。

  • 别名分析:分析两个指针是否指向相同的对象,可通过指针分析来推导得到。

应用:基本信息(别名分析/调用图),编译优化(嵌入虚拟调用),漏洞(空指针),安全分析(信息流)。

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

指标:精度(precision)& 效率(efficiency)。

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

(1)堆抽象(内存建模)

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

  1. // 示例
  2. for (...) {
  3. A a = new A();
  4. }

技术概览

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

Allocation-Site原理:将动态对象抽象成它们的创建点(Allocation-Site),来表示在该点创建的所有动态对象。Allocation-Site个数是有限的。

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

(2)上下文敏感 Context Sensitivity

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

  • Context-sensitive:根据某函数调用上下文的不同,多次分析同一函数。

  • Context-insensitive:每个函数只分析一次。

(3)流敏感 Flow Sensitivity

问题:考虑语句顺序(控制流)的影响 vs 把程序当做无序语句的集合。

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

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

指针分析示例

(4)分析范围 Analysis Scope

问题:分析程序的哪一部分?

  • Whole-program 全程序:分析全程序的指向关系。

  • Demand-driven 需求驱动:只分析影响特定域的指针的指向关系。

4.分析哪些语句

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

Java指针类型

  1. Lacal variable: x

  2. Static field:C.f (有时称为全局变量)——不分析

  3. Instance field: x.f (对象的field)

  4. Array element: array[i] ——不分析,因为静态分析无法确定下标,所以将array中所有成员映射到一个field中,等价于Instance field,所以不重复分析。如下图所示:

影响指针指向的语句

  1. 1. New: x = new T()
  2. 2. Assignx = y
  3. 3. Store x.f = y
  4. 4. Load y = x.f
  5. 5. Call r = x.k(a,...)
  6. - Static call C.foo()
  7. - Special call super.foo() / x.<init>() / this.privateFoo()
  8. - **Virtual call**:x.foo()

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

  1. x.f.g.h = y;
  2. // 转化为
  3. t1 = x.f;
  4. t2 = t1.g;
  5. t2.h = y;
上传的附件

发送私信

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

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