（计算机软件与理论专业论文）面向数据流的java程序指针分析技术研究.pdf

摘要 指针分析题许多程序分析工作的基础，它扶源程序中抽取各指针变量的指向信息、各表达式问的别名 信息，以及其它指针相关的信息，从而使后继分析能够准确地识别各程序点上访问的存储空间，判定它们 的运行时类型，劳进行指钟信息福芙的推导。多年来，入 | 】对指针分析技术进行了广泛悉深入的研究，取 得了许多研究成果，使得它在程序编译、程序变换、软件维护、软件逆向工程与再工程等领域得到广泛应 用，受到了广大软件研究人员的高度重视。 尽管如此，随着面向对象语言的不断动态亿，以及程序规模懿不断扩大，指针分析方法在走向应周的 过程中依然存在许多困难，如何保证分析精度和分析性能仍是十分值得研究的问题。为了进一步提高指针 分析的实用性，本文围绕程序数据流提取这一应用点，对j a v a 程序指针分析中的若干关键技术进行了深入 研究。文章首先针对语句层的数据流提取闻题，提出了点问确定剐名的概念，并给窿了一组利粥点间确定 别名优化依赖分析精度的方法；然后针对模块层的数据流提取，提出了一种基于贡献度的调用栈抽象模型， 并通过其实铡线程敏感的指针分析移关注点敏感的指针分橇震示了它在优化数据流分析效率方 面的效果。最簸，论文还讨论了一些与指针分系统实现有关的问题。 具体的，论文工作的主要成果表现在以下几个方面： 提出了点间确定别名的概念。这些别名能够描述不同程序点上访问路径之间的关系，相比子现有剐 名，具有更强的表达能力。根据点间确定别名的概念，给出了两种不同的计算点间确定别名的方 法，它钓分别基予数据流迭代稷值编号技术，英有不同鳇技术特点，为点阂确定别名的后继应用 奠定了基础。 给出了多种利用点间确定别名提高数据流分析精度的方法。利用点间确定别名荫先可以识别强更新 和相对更新，此癸它们还麓够焉于优化程序的副作用分析，识别不可实现的访阅路径组会和无效篦 过程间数据流，从而最终优化依赖图的构建。 提出了一耪基于霓献度的调鹰栈撼象模型，它结合一个调黑信息对分析耩度的贾献程度，来决定其 是否需要出现在最终的调用上下文中。以该模型为基础，指针分析方法可以利用有限长度的调用上 下文，最大程度地提高分析精度，这将使分析具有更佳的性价比。 戳基于贾瓤度豹调震棱抽象秀基硝，提出了一耱线程敏感的指锌分析方法霹一种关注点敏感的指针 分析方法。这两种方法都是面向应用的，且具有粗粒度的上下文敏感性。与已有的其它基于调用串 的指针分析方法相比，前者对于线程阀数据流的提取具有更好的精度一性能比，而后者充分考虑了 面向方面程序的结构特点，可以相当程度遣提赢方面间数据流识剐的效能。缀合关注熹敏感的指 针分析，本文还给出了一种高效的有臀通知识别方法。 关键词指针分析、别名、数据流、依赖性分析、副作用分析、多线程、面向方面 a b s t r a c t p o i n t e ra n a l y s i s ，w h i c he x t r a c t sp o i n t s t oi n f o r m a t i o n ，a l i a si n f o r m a t i o n ，a n do t h e rp o i n t e rr e l a t e di n f o r m a t i o n f r o map r o g r a m ，i st h ef o u n d a t i o no fm a n yo t h e rp r o g r a ma n a l y s e s w i t hp o i n t e ri n f o r m a t i o n ，t h ec l i e n ta n a l y s e sc a l l t h e r e b yf i g u r eo u tt h em e m o r yl o c a t i o n sa c c e s s e db ye a c hi n s t r u c t i o n ，d e t e r m i n et h er u n t i m et y p e so fs u c hm e m o r y l o c a t i o n sa n dm a k eo t h e rp o i n t e ri n f o r m a t i o nr e l a t e dd e d u c t i o n f o rd e c a d e s ，r e s e a r c h e sh a v em a d el o t so fd e e p s t u d i e so np o i n t e ra n a l y s i s ，o b t a i n i n gm a n yf r u i t f u la c h i e v e m e n t s ，t h er e s u l t so fw h i c hh a v ea k e a d yb e e nu s e di n c o m p i l i n g ，p r o g r a mt r a n s f o r m a t i o n , s o f t w a r em a i n t e n a n c e ，s o f t w a r er e v e r s ee n g i n e e r i n ga n do t h e ri m p o r t a n ta r e a s h o w e v e r , s i n c et h ep r o g r a m m i n gl a n g u a g e sb e c o m em o r ea n dm o r ed y n a m i ca n dt h es c a l eo fi n d u s t r i a lp r o g r a m sk e e p so ng r o w i n g ，p o i n t e ra n a l y s i ss t i l lf a c e sm a n ys e r i o u sp r o b l e m si nb o t he f f i c i e n c ya n dp r e c i s i o n t h e s e p r o b l e m sa r ed i f f i c u l tt os o l v ei ng e n e r i c , b u tt h e ym i g h t 酶s o l v e dw h e nt h ec l i e n ta p p l i c a t i o n sa r es p e c i f i e d 。u n d e r s u c hi n s p i r a t i o n , t h i sp a p e rs t u d i e dt h ep o i n t e ra n a l y s i so fj a v ap r o g r a m sw i t hj u s tt h ed a t a f l o wa n a l y s i su n d e rc o n c e n l 强ep a p e rf i r s t l yp r o p o s e dan o t a t i o nn a m e di n t e r s t a t e m e n tm u s ta l i a sf o rt h ec o m p u t a t i o no fs t a t e m e n tl e v e l d a t a f l o wa n dp r e s e n t e ds e v e r a lm e t h o d st or e f m et h ep r e c i s i o no fd a t a f l o wa n a l y s i sw i t hs u c ha l i a s e s 。t h e n , i tp r o - p o s e dac o n t r i b u t i o n b a s e dc a l ls t a c ka b s t r a c t i o nm o d e lf o rt h ec o m p u t a t i o no fm o d u l el e v e ld a t a f l o w a n di l l u s t r a t e d i t se f f e c t si nr e f i n i n gt h ee f f i c i e n c yo fd a t a f l o we x t r a c t i o nb yt w oi n s t a n c e so f t h em o d e l ，n a m e l yt h et h r e a d - s e n s i t i v e p o i n t e ra n a l y s i sa n dt h ec o n c e m s e n s i t i v ep o i n t e ra n a l y s i s f i n a l l y , t h ep a p e ra l s od i s c u s s e dm a n yi m p l e m e n t a t i o n r e l a t e dp r o b l e m so ft h ep r o p o s e dm e t h o d s 囊em a j o rc o n t r i b u t i o n so f t h i st h e s i sa r el i s t e db e l o w ： p r o p o s e dt h en o t a t i o no fi n t e r s t a t e m e n tm u s ta l i a s c o m p a r e dt ot h ee x i s t i n ga l i a sn o t a t i o n s ，t h ei n t e r s t a t e - m e n tm u s ta l i a si sm o r ee x p r e s s i v e ，a n di tc a nc l e a r l yd e s c r i b et h er e l a t i o nb e t w e e na c c e s sp a t h si nd i f f e r e n t p r o g r a mc i t e s 。a c c o r d i n gt ot h en e wa l i a sn o t a t i o n , t h ep a p e ra l s op r e s e n t e dt w om e t h o d st oc o m p u t et h ei n - t e r s t a t e m e n tm u s ta l i a s e s o n ei sb a s e do nd a t a f l o wi t e r a t i o n a n dt h eo t h e ri sb a s e do ng l o b a lv a l u er u m b e r i n g 强e yh a v ed i f f e r e n tt e c h n i q u es t r e n g t h s ，a n dc a n b eu s e d u n d e rd i f f e r e n ts i t u a t i o n s p r o p o s e ds e v e r a li n t e r s t a t e m e n tm u s ta l i a sb a s e dm e t h o d st oi m p r o v et h ep r e c i s i o no fd a t a f l o wa n a l y s e s w i t ht h e s ea l i a s e s ，o n ec a ne a s yi d e n t i f ys t r o n gu p d a t e sa n dr e l a t i v eu p d a t e s ，n l ei n t e r s t a t e m e n tm u s ta l i a s e s a l s oc a nb eu s e dt or e f i n ei n t e r p r o c e d u r a ls i d e - e f f e c ta n a l y s i s ，b e s i d e s , o n ec a n 璐es u c ha l i a s e st oi d e n t i 黟 i n v a l i dc o m b i n a t i o no fm e m o r ya c c e s s e sa n dd i s c a r di n f e a s i b l ei n t e r p r o c e d u r a ld a t a f l o w , a n dt h e r e b yi m * p r o v et h ep r e c i s i o no fd e p e n d e n c eg r a p hc o n s t r u c t i o n p r o p o s e dac o n t r i b u t i o n - b a s e dc a t ls t a c ka b s t r a c t i o nm o d e l ，w h i c hd e c i d e sw h e t h e rs o m ec a l li n f o r m a t i o n s h o u l de x i s ti nt h ec a l l i n gc o n t e x tb yi t sc o n t r i b u t i o nt ot h ep r e c i s i o no ff i n a la p p l i c a t i o n w i t hs u c hm o d e l ，a p o i n t e ra n a l y s i sc a r le x p l o i tl i m i t e dl e n g t ho fc a l l i n gc o n t e x t st oa c h i e v eb e s tp r e c i s i o n ，a n dt h i sw i l lm a k e t h ep o i n t e ra n a l y s i sm o r ec o s t - e f f e c t i v e p r o p o s e dat h r e a d s e n s i t i v ep o i n t e ra n a l y s i sm e t h o da n dac o n c e r n s e n s i t i v ep o i n t e ra n a l y s i sm e t h o db a s e d o nt h ec o n t r i b u t i o n - b a s e dc a l ls t a c ka b s t r a c t i o nm o d e l b o t ht h e s et w om e t h o d sa r ea p p l i c a t i o no r i e n t e d , a n d h a v ec o a r s ec o n t e x t - s e n s i t i v i t y c o m p a r e dt ot h ee x i s t i n gc a l ls t r i n gb a s e dp o i n t e ra n a l y s i sm e t h o d s ，t h e y h a v eb e t t e rp r e c i s i o n - c o s tr a t i o sf o ri n t e r - t h r e a dd a t a f l o wd e t e c t i o na n di n t e r - c o n c e r nd a t a f l o wd e t e c t i o nn - s p e c t i v e l y 嘲氆t h ec o n c e r n - s e n s i t i v ep o i n t e ra n a l y s i s ，t h i sp a p e ra l s op r e s e n t e d 蕊e f f i c i e n th a r m f u la d v i c e i d e n t i f i c a t i o nm e t h o df o ra s p e c o ，at y p i c a la s p e c t - o r i e n t e dp r o g r a m m i n gl a n g u a g e k e y w o r d s ：p o i n t e ra n a l y s i s ，a l i a s , d a t a f t o w , d e p e n d e n c ea n a l y s i s , s i d e - e f f e c ta n a l y s i s ，m u l t i - t h r e a d e d , a s p e c t - o r i e n t e d 东南大学学位论文 独创性声鼹及使用授权说臻 一、学位论文独餐性声端 本人声明所里交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含英毽入露经发表或撰写过酶研究盛栗，也不包食势获得末离大学或其它教育 机构的学位或证书丽使用过的材料。与我一周工作的同志对本研究所做的任何 嚣献均已在论文中作了明确的说髓并表示了谢意。 签名：型淫二蓬鬻：墨兰出 ：、美子学莅论文蓑霜授校熬说矮 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所遴交学 位论文的复印件和电子文档，可以采用影印、缩印或其窀复制手段保存论文。 本人电子文档嚣斑容帮羝凄论文的蠹容穗致。除在保密鬻蠹的僚密论文磐， 允许论文被查阕霸借阕，可以公蛮( 包撼刊登) 论文豹垒部或部分内容尊论文 的公布( 包括刊髓) 授权东南大学研究生院办理。 第一墩引言 1 1 选题依据 第一章引言 程序分析怒软件编译优化、测试、调试、验证等许多活动静基础。随着计算枫技术的飞速发震，软件 系统的数量越来越多，规模越来越大，复杂程度越来越高。在一些大型、长生命周期的软件开发、测试和 维护过程中，手工分析已经交得越采越不可行，越来越多的工作需要理论、技术与工具的支持。程序分析 技术已成为软件领域的个十分重要而又极其迫切的研究领域l l 。 在程序的分析中，指针( 包括j a v a 或其它语言中的引用) 信息是获得含指针程序的控制流倍息、数据 流信患以及其它信息嚣基础，指针分橇作势诲多分桥的必备基础始终是一顼重要的议题i 4 3 】【3 刀。瑗有指针分 析研究中，所涉及的语言不仅包括了传统的c 语言f 3 2 j l 埘】、p a s c a l 语言【6 5 l ，还包括新型的面向对象语言， 甚至是高阶程序设计语言【47 】；所涉及的程序结构也从简单语句，发展到了结构、数组、异常处理、复杂过 程调耀，甚至备种并发设施f 罐挎习；所分辑的内容也飙单纯豹别名关系抽取，扩震裂了指向信息分析、壤 空间抽象、数据结构形态分析等一系列分析。指针分析的方法则从开始的简单数据流迭代或约束传播，扩 展为舆有流敏感性、上下文敏感性、属性域敏感性、路径敏感等不同敏感性、不同性价比的方法簇。随着 研究酶不断深入，指针分析方法越来越实露鬣：，指针分析的应用也从简单的顺序程序优化，发震到并发程 序优化、错误棱测、程序安全性分析、软件维护等等一系列领域中。许多指针分析方法已经被集成在各种 商用编译工具霸软 孛开发环境中。 舀前，对于规模较小的程序，对于动态住较弱、使用指针较少的结构他程序，指向信息的分析已经较 为成熟。然而，对于规模更大、动态性更强的程序，现有指针分析方法还存在许多问题。这其中最大的问 题是对大型程序熬处理。大型程序动辄具有数十万甚至数百万行代码，指针分析方法嚣瞧羞空闻性能和时 间性能的双重挑战，一个真正实用的方法不仅需要有较高的分析精度，而且需要有较高的分析性能。指针 分析中的另一个挑战来自堆空间的处理。现有方法难以准确并高效地分析堆空间带来的别名等一系列问 题，谣蘧着程序语言魄墨益动态化，堆空翔的使用越来越普遍。为保证分析豹效采，崧须对堆空阁相关酶 指针分析技术进行更深入的研究。除了上述问题，新型的程序设计范式，特别是面向方面语言等也给分析 带来了很大挑战。指针分析方法必须考虑新语言的新语法特性，考虑这些特性给精度、性能等方面带来的 影确。另外，多核体系结构的普及也使得并发程序的指针分析成为个值得继续关注的方面。如何使指针 分析更好地服务于并发相关信息的提取，是一个特别需要考虑的问题。 本文在广泛调研豹基础上，结合国家杰蹴青年科学基金项基、国家重点基础研究发展规划9 7 3 、国家 自然科学基金项耳、国家博士点基金项目，以及江苏省盘然科学基金项目等，试图通过对指针分析基本理 论的研究，找出一组高性能、高精度的指针分析方法，以进一步推进指针分析技术的实用化。对于指针分 析，簧改进瑟向普遍应用麓分析算法存在匿大的困难。然焉，对予某些应用，结合应髑垒身的需求来优化 分析却是一条可行的道路。本文着熏以在软件理解与维护中广泛使用的数据流信息提取为应用目标，来优 化指针分析的精度和性能。在过程内，我们期塑找到一种辅助技术来弥补既有方法精度上的不足，特别地， 我们期望改善指针分析露予堆空闻的处理缝力，隧更好媲处理嚣囱对象程序；在过程阀，我稻凝望找毒一 种新的过程间分析模式，并用新的粗粒度的上下文敏感性来缓解现有上下文敏感指针分析方法性能上的劣 势。此外，论文还将对指针分析系统实现中的一些闻题进雩亍探索。 1 2 国内外研究现状 指针分析可按表示形式酶不蠢大致分药别名分析帮指囱分橇滞l 。别名分析寻找程序中表示同空闻的 表达式对，指向分析找出程序中每个指针的指向集。前者又分为可能别名分析和确定别名分析。可能别名 l 东南大学博士学位论文 是在部分程序执幸孑中成立酶舅| j 名关系，面确定别名燹| j 是在所有程序执行中都成立於剐名关系。 1 2 1 别名分析 由予指向信息较之爱名信息在表示上更麦紧凑，并且从指囱信怠可以导出可能剩名信息，因戴对可能 别名的分析已逐渐从纯粹的别名提取【4 2 】【5 2 】转向指向信息的分析，目前主要的可能别名分析都是指向分析。 在确定别名分析方面，擞于过去的别名分析主要针对c 程序，两c 程序中的指针多数是栈指针，且棱 空间上羽确定别名关系可以扶确定指内关系瞄】导出，因此确定鄹名分析本身并没有得到充分的研究。w l a n d i 和b r y d e r 仅提出了种单级指针的确定别名分析方法【5 2 l 。ra l t u c h e r 等人【3 】和s j a g a r m a t h a n 等人【4 7 】 透过分析扩展的唯一指自性来获 ! 霉确定别名，经是铁唯一指向性只熊导密程廖中的一小部分确定疑名关 系，并且在堆内存广泛使用的程序中，这种唯一指向性本身也很难成立。 对于j a v a 程序，越来越多的应用需要通过确定别名关系来识别表达式之间的关系f 1 3 】【1 4 】【2 1 】【3 3 儿3 6 】【4 3 】【6 8 l ， 瑟堆空阕懿褒震傻褥麸指向关系不能礁确地获褥别名关系，因此裂名分析，特别是确定别名分析又耋凝秀 人们所重视f 1 4 】i 儡】。然而，现有分析所获得的别名只能用于单一程序点上内存访问表达式之间关系的判断，而 在许多应用中，更有使用价值的是不同程序点上内存访问表达式之间的确定别名关系。这些别名并没有得到充 分的研究。探索它们酶表示方法、提取冀法以及应瓣技术将有较大的理论与实践意义。 除了可能别名和确定别名，近期的研究中，部分学者也开始探讨非别名的概念f l 】【2 l 】【5 1 】例。个非别名指出 两个表达式一定不访问相同的物理空闻。在堆空间的抽象中，不同的物理空间常常被抽象为搁同的抽象空间， 这使得可能别名的分析精度大为下降。仪通过提高堆空闻抽象的精度来改善分析较为困难，遴过非另n 名信息可 以在一定程度上弥补这种不足。非别名在程序理解、编译优化、并发程序共享和同步分析等领域中已经体现了 较大的价值。 1 2 2 指向分析 。在指向分析方瑟，早期的研究主要以中小援模憋c 程序为研究对象( 如 3 2 4 6 1 0 4 等) ，面近期静臻 究则多以大规模j a v a 程序为研究对象。本研究亦以大型j a v a 程序为研究对象。在j a v a 程序的指针分析中， 现有方法主要可分上下文不敏感指针分析【9 1 【5 6 j f 5 9 1 1 6 1 j 【8 3 】【1 0 2 】和上下文敏感指针分析f 1 9 1 1 4 6 】【6 6 】【7 2 j 【删【1 0 1 】1 1 0 3 】【1 0 5 1 两 类，上下文敏感酶算法考虑方法在不弱调用环境下药不露效梁，焉上下文不敏感的算法剩不考虑这种差异。 上下文不敏感的算法尽管高效，但其精度很难满足许多应用的需要【6 3 1 。而现有的上下文敏感方法尽管采用 了b d d 等一系列技术来进行优化【1 0 3 j 【l o 卿，但是性能仍并不十分理想，它们难以适用于大型程序的分析。 为了在保证耩度酶同时提高分析性能，n h e i n t z e 帮0 t a r d i e u 提出了一种需求驱动的指针分析转l l ， 该方法中，指针分析以用户的查询需求为驱动，当用户的查询较少时，这将可以大幅度地提高分析性能。 s 。g u y e r 秘c 。l i 的方法f 3 9 l 以及m 。s r i d h a r a n 等人的方法f 9 2 1 f 9 3 】也以用户的分析需求为驱动，它们能根据用户酶 需求自动对指针分析作出精化，直到得到用户满意的分析精度为止。 上述几种方法尽管是面向应用的，但是它们仅将应用的需求解释为指针信息的查询请求，这并不能充 分避表达应用的需求特征。另外，仅扶接针查诲爨发来优化指针分析，能力上也拢较有限。事实上，不霹 应用对分析的上下文敏感性宥着不同的需求。它们需要上下文敏感化，但不是过度的上下文敏感化。如果 能根据应用的需要进一步抽象调用上下文，进行粮粒度的上下文敏感指针分析，将有可能在提高指针分析 效率酶嚣时裰当程度的保证分析懿精度。 1 2 3 数据流提取相关的指针分析 关予指针分析在数据漉提取中的应臻，在过程恣，d 。a t k i n s o n 秘强g r i s w o l d 4 醚及d 。b i n l d e y 和j 聊善1 毽 研究了根据指向信息计算可达定义从而进行依赖性分析的问题，ao r s o 等人 7 3 】探讨了在含指针程序中数 据流依赖的分类问题。这些文献只是探讨了指针分析的应用，并没有由此回到指针分析本身。另外，他们 均没有深入鲍探讨堆内存上的数据流分析闯题。其它一些工佟则更多扶数据结构形态分析【s 8 】的危度来探讨 堆内存抽象对数据流分析的影响1 5 1 4 4 。数据结构形态分析尽管在描述堆空间关系方面比别名分析更为精确， 2 第一章引言 但它们代侩太离，难以适用于大型程序。 在过程间，h p a n d e 等人研究了含单级指针程序的过程间定义一引用关系提取1 7 4 1 ，a m i l a n o v a 等人研 究了指针分析对于上下文敏感定义- 7 1 用关系提取的影响m 】。这两篇文献巾，定义一引用关系的分析都是 基予数据流迭代的。对予大壅程痔，分析郡整仅通过全局空阚进行交互的模块之闻懿定义一弓l 髑关系，更 高效方法是直接分析模块的定义集和引用集，然后据此构造定义一引用关系，而这种方法需要较高精度的 指针分析，特别是需要尽可能地区分不同模块中使用的空闯。耳前，适用予这类分析的高精度、高性能指 针分析方法并没有得到究分的研究。一些算法菲常精确，但性能不理想，两另一些算法剃秀了傈证分析性 能，牺牲了太多的分析精度。如何设计一种具有高性价比的，精度和性能都能令人满意的算法，仍是个值 得深入探讨的阀题。 1 3 主要研究内容 目前指针分孝厅，特别是在瑟囱数据流摄取静指针分析方瑟尚有许多问题亟待解决。本文戬簏为契撬， 对指针分析展开了一系列深入研究。研究内容主要包含两个层面，分别是丽向语句层数据流关系提取的指 针分析技术和黼向模块层数据流关系提取的指针分析技术。 1 3 1 面向语句层数据流关系提取的指针分析 分析表明，点问确定别名，即男器些能够撼述不同程序点上内存访闯之间关系的确定别名，在数据流分析 中有广泛的用途，包括生成强更新、排除伪数据流、优化副作用分析等。两这种剐名目前并没有得到应育 的重视。为此，本文首先从点间别名出发研究了语句层数据流分析的优化，具体工作主要从三个方面展开： f 薹 点阀确定别名的概念研究我翻蓄先研究了点润确定别名的语义秘点间确定分类闻题，重点探讨点 间别名和一般别名的区别。以此为基础，我们还研究了点间确定别名的表示方法及其基本特点。 y ) t m p2x ： e l s e t m p 2 y ： r e m mt r a p ； ) 圈2 1c f g 示例 2 1 。2 调用图 调用图c g = e y ( t ) ，且x eu s e ( t ) 。 2 3 3 模块闯数据流 本文所关注的模块间数据流主要指模块间的直接定义引用关系，而模块间的间接数据流可以通过数据 依赖关系的传递，或系统依赖图1 4 5 l 上的遍历获得。对于模块阀的直接数据流，一种计算方式是对程序进行 全局数据流迭代l 蚓。这种方式考虑了程序豹控制结构，因此较为精确，但福应爵代价也很麓。另一静较为 简单的方式是对于模块脑和，一旦存在x m o d ( m ! ) 且x eu s e ( m 2 ) 就认为存在一条从脑到m 2 的数据流。 这种方式的优点是操作容易、性能好，缺点是因为没有考虑程序控制溅丙精度稍差。 哥前对语句闻和模块问数据流的分析，最主要的问题还是对含指针程序和使用雄空间程序的处理。指 针和堆空间的为程序引入了很大的动态性，它们给程序的静态分析带来了很大挑战。 2 。3 。4 依赣圈 依赖网是程序中依赖关系的图形化表示。通常依赖图中的点对应程序语句，边对应语句间的数据依赖 关系或控铡依赖关系。依赖边趔o 表承点的执行取决子材点的执行，或者点使用了材点定义憋变 量。单个方法对应的依赖图是方法依赖圈，而整个程序对应的依赖图通常称为系统依赖图( s d g ) i 4 列。s d g 上包含对方法调用的描述，每个方法对应一个表示其入口的控制节点，该控制节点依赖于具体的调用语句。 方法豹形式参数，蠢实际参数体瑗为s 丑睡主静形参节煮和实参节点，一组数据流依赖边被灞来描述参数闰 的数值传递。 h f o o ( h t tx ) l e t u n lk ) 鑫= l ： s ：b = f o o ( a ) ； c = b ： 圈2 6 铱濑图秀捌 图2 - 6 给出了一个简单的过程调用的例子，其中“a = 1 ”和“c = b ”节点对应了代码中的简单语句， “c a l l f o o 是语句s 对应调用点，“e n t r y f o o ”节点描述7 f o o o 方法的入网，它下面的“x = f o o 。i n ”和 f o o o u t = 羔”点分剐撼述了输入帮输密形参， f o o 。i n = a ”_ 鞫“b = f o o o u t ”点分别摇述了输入震输出实参。圈2 - 6 中的粗边是控制依赖边，而细边是数据依赖边。 2 4 本章小结 本章对指针分析_ 和数据流分析的背景进行了介绍，我们重点解释了一些文中所涉及的基本概念和和基 本方法。在指针分析中，本文主要关注的是确定羽名分析和上下文敏感麓指针分析，丽在数据流分析方丽， 我们主要关注的是副作用分析、语句问的数据流依赖和模块间的数据流。部分概念，我们还将在后继的篇 幅中做更深入介绍。 1 2 第三章点间确定豺名及其计算 第三章点闻确定别名及其计算 传统意义上的别名仅能描述某程序点上多个访问路径间的关系。除此乏外，还有另种描述不同程 序点上访闯路径问熬关系的别名。这种剩名在实际瘦震中用途缀广。数据流分析中胃焉它判定不同点上的 写操作之间是否存在覆盖关系，同步分析中可用它判断一个空间访问是否直接被锁保护，编译优化中可用 它识别冗余操俸。然而在相关研究中它们却并未得到足够的重视，不同程序点上访问路径之间的别名无论 在概念上狂分析方法上都亟待更多的研究。本章首先分析了已有别名在概念上存在的闼题，然后提出了点 间别名，特别是点间确定别名的概念，并给出两种计算点间确定别名的方法。这两种方法都是上下文不敏 感的，它们霹以在相对较少的对阌内获得程序中的大差点阂确定舞名信息。 3 1 点间确定别名的提出 3 1 1 已有别名概念及其闯题 一仑访闻路径在不周点上可雏育不同的状态，在掇事甥1 名的概念篱，我菲】用“撵点上的访闯路经伐”来特别 强调对r 点上访问路径0 【状态的关注。 透常个别名仅表示同一点土两个访问路径之闻的等价关系。它不熊搽述不游点上访闻路径之闻的关系，因 此不同点上的别名间一般并不具有传递性。比如，从拧l 点上的别名帛而g 驴和n 2 点上的别名豇而g j c 并不能获 知m 点的p x 和境点的蹦存在别名关系。在不含堆使用的程序中，从确定指向关系可导出不同程序点上的访问 路径之闻的确定别名关系1 3 2 。铡如，在如下程序毁中： v o i df o n ta ) i n t 4 p 2 & a ； i n t 幸q = & a ； p = l ； 毒鼋= 蠡； 语旬4 上有确定指囱关系矿溉语匀5 上有确定指向关系尹帐，由此哥| 豉推导出语萄4 上的肇帮语訇5 上的辜霉 始终访问相同的空间。然而，f l j 于j a v a 中所有的指针都是堆指针，指向关系p 一0 右端的抽象空间在个上下文 下可以表示多个不同对象，指向同样的抽象空间并不代表访问耐样的物理空间，因此即便是匕述推导也不再可行。 为表示不同程序点上访闯路径之阒的确定别名关系，必须引入新的、更药直接的别名表示。对于语句 朋点上的访问路径。讶铂一点上的访问路径p ，描述它们之间别名的最自然形式是锄：0 c ，”：p 。e b o d d e n 等人【1 4 l 即用类似方式来描述两程序点上表达式闯的关系。这种描述对菜些应用是有雳的，值它膏个致命缺陷，即 不能处理m 和月点出现多次的情况。以图3 1 为例，程序点扰和船反复执行多次，在未给出锄：o 【，l ：1 3 具体语义的情况下，难以表达到底是哪次所如现上的表达式0 【和哪次档出现上的表达式d 之间存在别名关 系，除非在包含_ ，| 秘嚣出现鳃语句块孛a 、多中的交豢均耒薰新定义。 | 以上分析| 表唆，对乎不同程彦点上访瀚路径阏关系鳇播述琴纹需要新的表示方式还霈要更为严格的定义。 3 。1 2 点闻别名及其分类 本文将相同或不l 鄙隍序点上的访问路径之间的别名关系统称为点间别名，而传统意义上的别名则称为 1 3 东南大学博士学位论文 点内剐名。点内别名可以看俸点闻别名静特铡。在不弓| 起混淆时，我嚣j 也用剃名来代指点间剐名。 定义3 1 程序点m 和程序点刀间的无向别名愀：r ：p 表示研各出现中的访问路径泖胛各出现中的访 闷路径表示粳恩的妨理空间。 定义3 1 给出了一个无向别名的严格描述。这种别名不能区分一条语句的多个出现，表达能力较为有 限。特别地，对于搬的不同出现中。袁示多个不同空间，或者辨的不同出现中眯示多个不同空间的情况，它 哭能表达可能靛剃名关系，丽不能表达确定别名关系。 为准确地描述语句点所上的访问路径泖语句点胛上的访问路径d 之间的关系，我们在点间别名上进一步扩 嶷上了流信息。按滤向不同，点闯别名可分为前向别名和后向别名，其定义如下： 定义3 2 程序点肌上的前向别名嘲：仪l ，c x 2 表示当程序流从别名源节点力的最近一次出现流向朋时，刀 出口的访问路径0 c l 和当前点臌入口的访问路径嘞表示相同的物理空间。 定义3 3 程序点搬上的后向别名 表示当程序流扶掰流向后继节点辫的第一次出现时，溺前 点加出口的访问路径0 【1 和r 入阴的访问路径0 e 2 表示相同的物理空间。 上述定义中，我嬲透过“辫前最近一个撵”秘“掰嚣下一个v ”表达了剐名所限定的语旬崮现。在搬 或甩可能出现多次的情况下，它更准确地指出了别名的具体含义。这里，有向别名仅关注“当前x ”和“前 一个y ”或“下一个y ”之间的关系，而许多应用所关注的也正是两个表达式相近的几个出现间的关系。 对于有向别名，当刀焉特殊符号i 代替时，心：a 1 ，钧 表示当前患上( 群当翦点入西) 的访问路径o 【l 和当前点上的访问路径o 【2 存在别名关系，m i ，上：畛表示当前点出口的访问路径仅l 和当前点出口的访问路径 锄存在别名关系。仅在这时别名关系才是对