【软件分析/静态程序分析学习笔记】7.指针分析(Pointer Analysis)入门_童年梦的博客-程序员信息网

技术标签: 编程语言  静态分析学习笔记  

写在前面的话

本渣有幸成为南京大学软件学院研究生,在前往仙林校区蹭课的时候偶然发现了这门宝藏课程,听了以后感觉深有收获,但又因为课程难度较大,国庆假期归来发现遗忘较多,因此开了一坑来记录自己对每节课知识点的理解。也由于这是本人第一次开坑写博客,结构内容自有诸多不合理之处,希望有问题的地方大家可以指出。


系列文章目录

1.静态程序分析(Static Program Analysis)介绍
2.中间表示(Intermediate Representation)
3.数据流分析(Data Flow Analysis) (上):可达性分析(Reaching Definitions)
4.数据流分析Data Flow Analysis) (下):存活变量分析(Live Variables Analysis)及可用表达式分析(Available Expressions Analysis)
5.数据流分析基础(Data Flow Analysis-Foundations)
6.过程间分析(Interprocedural Analysis)
7.指针分析(Pointer Analysis)入门
8.指针分析基础知识(Pointer Analysis Foundations)


一、动机

动机
在上一篇文章中,我们讲到了一种过程间分析的算法CHA,这是一种牺牲了精度来换取效率的算法,可以根据对象的类型进行分析,得到这个对象调用的方法可能是在哪定义的。然而这种算法对精度的牺牲自然会导致一些我们不想看到的"严谨",就像上图所示,采用CHA算法会从对象n对应的类Number中寻找get()的定义,找不到后会从Number的子类寻找,因此经过CHA的分析n.get()的返回值是NAC。然而显而易见,由于n是One类型创建的,所以返回值应该是1才对,这就需要用到指针分析了。


二、指针分析

2.1 什么是指针分析

我们首先介绍一下指针分析的三个特征:

  • 一个基本的静态分析:计算一个指针能指向哪个内存位置。
  • 对于OO语言(主要是Java)来说:计算一个一个指针(variable或field)指向哪个对象。
  • 作为一个may分析:计算指针指向的过拟合的对象集,即一个指针可能指向哪些对象?、

以上三个特征便可以看出指针分析到底是一种什么样的分析算法,其中需要解释一下的是第二条特征。不同于cpp,Java并没有真正的指针,或者说Java的指针被封装在代码底层,我们接触不到,而此处的指针指的是那些存储非数据而是地址的变量,例如T x = new T()中的x存储了新创建的一个类型为T的对象的地址,是一个指针。

2.2 一个指针会指向哪里

接下来用一个例子来具体感受一个指针会指向哪里:
例子
右侧表格是左侧程序每个变量指针指向的对象,接下来一个个看。
第一、二行定义了a和x,分别指向A和B没问题;
第三行调用了A类中的set()函数,this指向当前对象,同时也是调用了这个方法的a指向的new A,而b指向自己新创建的new B;
而y指向了a.getB()返回的this.b所指向的new B;
下方的A.b即this.b,指向传入参数x的new B。

2.3 Pointer Analysis 和 Alias Analysis

Pointer Analysis是指针分析;
Alias Analysis是别名分析;
这是两个密切相关但是不同方面的分析,主要体现在:
指针分析主要分析指针指向哪个对象,而别名分析主要分析两个指针是否指向同一个对象。
这个点了解一下区别就可,不细说了。

2.4 指针分析的应用

指针分析有很多的应用场景,例如可用于

  • 优化代码
  • 查bug
  • 安全性分析
  • 验证测试

等技术场景。


三、指针分析中的关键因素

指针分析是一个复杂的系统,有不同的因素影响了这个系统的效率和精度,我们需要在此之间找到一个平衡,下图就是其中最重要的四个因素
在这里插入图片描述
四个因素分别是:堆抽象、上下文敏感、流敏感、分析范围,第三列则是一些最为广泛使用的选择策略。

3.1 堆抽象

Java运行时会将创建的很多的对象放在堆里以供调用,堆抽象就是对其建模。
为了确保终止性,堆抽象会将动态执行时无限的域映射到静态分析时有限的域,再进行静态分析:在这里插入图片描述
在这里插入图片描述
堆抽象有很多种方法,最常用到的就是Allocation sites的抽象技术,这是一种Store based model,基于内存中地址的模型。
我将Allocation site翻译为抽象点,每个抽象点对应一个抽象对象,这个抽象对象代表被分配的所有具体对象,而系统通过抽象点对具体对象建模。
下面举个例子说明这种抽象关系:
在这里插入图片描述
动态运行时在for语句中创建了多个具体的对象a,而通过Allocation sites的技术抽象为一个抽象对象。

3.2 上下文敏感

上下文的敏感指的是系统模拟如何调用上下文,例如记录一个方法的传参、返回地址等,其中的上下文指的是被调方法的上下文。在这里插入图片描述
左侧是上下文敏感的做法,对于每次调用方法的时候都会分别记录那次方法的上下文信息,而右侧是不敏感的做法,会将不同的调用合并,每个方法不论调用多少次都只会分析一次。

3.3 流敏感

流敏感指的是如何对控制流进行建模,我们之前学习到的算法都是流敏感的:在这里插入图片描述
左侧是流敏感的分析,严格按照控制流的顺序进行分析,会在每个程序点都列出当前所有的指针指向;
右侧是流不敏感的分析,不考虑控制流的顺序,会将所有可能的指向一起加入域中。
由于流敏感分析的时候很多情况下域中的指向对象不可替换,因此开销很大,流不敏感的分析此时便可派上用处。

3.4 分析范围

分析分为整体分析和按需求分析。其中整体分析就是分析整个程序,不需要解释;按需求分析就是分析需要的代码行及相关的代码

1 x = new A();
2 y = x;
34 z = new T();
5 z.bar();

例如我要分析第五行的指针指向何处,只需要分析第四行即可。

3.5 总结

在这里插入图片描述
总结一下:

  • 堆抽象:针对对象,选择Allocation-site抽象技术;
  • 上下文敏感:针对方法,后续两种都会用到;
  • 流敏感:针对控制流,为了减小开销,使用流不敏感的;
  • 分析范围:由于并不知道得到需要分析处的指针指向需要从哪开始分析,有可能从头分析,消耗资源也很大,因此选择整体分析。

四、相关的语句

由于

  • if-else
  • switch-case
  • for/while/do-while
  • break/continue

四种语句并不会改变指针的指向,所以不考虑这四种语句的影响,主要分析以下四种类型的对象

  • Local variable: x
  • Static field: C.f
  • Instance field: x.f
  • Array element: array[i]

第一个局部变量x不用赘述;
第二个静态域C.f某些时候也可看作全局变量,一般不会碰到;
第三个实例域x.f建模为 一个由x指向的对象 + 一个域f;
第四个数组元素在处理的时候会将其下标忽略,统一指向一个域,将array[i]全部抽象映射到array.arr的域中。

然后是五种会改变指针指向的操作:在这里插入图片描述
这四种操作的需要牢记,将会在下一篇文章中具体分析。


五、总结

本文大概写了一下指针分析是什么,有哪些关注点,可以粗浅地了解一下什么是指针分析,具体的分析将在下一篇文章中进行。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/zhang971105/article/details/109538402

智能推荐

S7-1500 CPU 和显示屏的固件更新说明_zhoulibo0922的博客-程序员信息网

1、通过 STEP 7 (TIA-Portal) 进行在线固件更新;2、使用 SIMATIC 存储卡卡进行离线固件更新 (STEP 7、TIA-Portal)

[Linq]LINQ的左连接、右连接、内连接_厦门德仔的博客-程序员信息网_c# linq 左连接

1、左连接:var LeftJoin = from emp in ListOfEmployeesjoin dept in ListOfDepartmenton emp.DeptID equals dept.ID into JoinedEmpDeptfrom dept in JoinedEmpDept.DefaultIfEmpty()select new {EmployeeName = emp.Name,DepartmentName = dept

字符型图片验证码识别完整过程及Python实现_风中追风风的博客-程序员信息网

1摘要验证码是目前互联网上非常常见也是非常重要的一个事物,充当着很多系统的防火墙功能,但是随时OCR技术的发展,验证码暴露出来的安全问题也越来越严峻。本文介绍了一套字符验证码识别的完整流程,对于验证码安全和OCR识别技术都有一定的借鉴意义。文章更新:2017-09-20本文的基于传统的机器学习SVM的源码共享:介绍文章:http://www.cnblogs.com/bee...

ArcGIS学习总结(九)——将.kml转换为.shp_Arcgiser的博客-程序员信息网_kml转shp

打开ArcMap,选择ArcToolbox->Conversion Tools->From KML->KML To Layer在打开的对话框中选择Input KML File,其他选项默认即可。本次所选择的kml文件中包含了点和线。点击ok,弹出进度条对话框,转换完成以后对话框自动关闭。...

C语言字符串输入函数 scanf,gets,fgets 的比较与解析_OneLine_的博客-程序员信息网_c语言中文件的字符串输入函数是

想先讲一下,关于输入字符串输入如果是单个字符输入 要在输入前后都要加上 getchar() 读取空字符个人经验,如有错误请指出。原博地址:https://blog.csdn.net/jzqt_t/article/details/38315675许多ACMer在做ACM题时经常会被一些字符串输入搞混,如果认为几个字符串输入函数的功能基本一样那就大错特错了。今天把C语言中的三个字符串输入函数(scan...

随便推点

顺藤摸瓜RocketMQ之刷盘机制debug解析_jianjun_fei的博客-程序员信息网

Rocketmq 刷盘机制三个文件在rocketmq里面存在这样三个文件indexfileconsumequeuecommitlog其中indexfile和consumequeue可以理解为索引文件,indexFileconsumeQueuecommitlog刷盘

kali工具之Beef_wulanlin的博客-程序员信息网

*本工具仅供技术分享、交流讨论,严禁用于非法用途。简介Browser Exploitation Framework(BeEF) BeEF是日前最强大的浏览器开源渗透测试框架,通过X55漏洞配合JS脚本和 Metasploit进行渗透; BeEF是基于Ruby语言编写的,并且支持图形化界面,操作简单主要功能信息收集:1.网络发现2.主机信息3.Cookie获取4.会话劫持5.键盘记录6.插件信息持久化控制:1.确认弹框2.小窗口3.中间人社会工程:1

linux的traceroute命令详解_雪域白狼的博客-程序员信息网_traceroute6

traceroute命令详解traceroute [-46dFITUnrAV] [-f first_ttl] [-g gate,...]        [-i device] [-m max_ttl] [-p port] [-s src_addr]        [-q nqueries] [-N squeries] [-t tos]        [-l flow_label] [-w wait...

测试人生 | 突破“大专学历+半路转行”标签,从拉垮到测试团队骨干,走到这一步很知足_霍格沃兹测试开发的博客-程序员信息网

原文链接️ 关注霍格沃兹测试学院公众号,回复「面试」,领取测试开发面试真题合集!编者按:本文是霍格沃兹测试学院学员 @XiaoW 分享的测试人生故事,作为学习群阳光活跃的“学习小王子”,背后竟有如此曲折和令人钦佩的经历,这种积极向上的力量极具感染力,也发人深省,当幸福来敲门时,你是否做好了准备?在霍格沃兹测试学院收获很多,应学院的邀请,分享下我个人的测试技术成长经历,深感荣幸,请大家多多指教!为告别频繁出差,从传统制造业转向 IT 行业我转行进入 IT 行业有 2 年多时间了,在这之前,一直

自适应滤波:维纳滤波器——LCMV及MVDR实现_weixin_33734785的博客-程序员信息网

作者:桂。时间:2017-03-24  06:52:36链接:http://www.cnblogs.com/xingshansi/p/6609317.html 声明:欢迎被转载,不过记得注明出处哦~ 【读书笔记03】前言西蒙.赫金的《自适应滤波器原理》第四版,上一篇看到维纳滤波基本形式:最优化问题,且无任何条件约束。这次看到有约束的部分,简单整理一下思路: ...

MD5摘要算法的几种解密方法,分享md5免费解密网站_哈客部落的博客-程序员信息网_md5解密

在一个md5解密交流群看到有人讨论MD5算法解密,消息有上百条,但是具体怎么解密却没人讨论。所以,今天就这个话题浅谈一下MD5摘要算法的几种解密方法,以及分享使用MD5免费解密网站如何进行md5加密解密,大家可要轻点喷。...

推荐文章

热门文章

相关标签