（计算机软件与理论专业论文）java程序分层及概率依赖性分析.pdf

摘要 摘要 程序依赖性分析是软件工程领域中一项重要而基础的活动，它是对已有程序分析与理解的基础，并 在程序切片、逆向工程、软件测试以及软件重构等软件工程各个领域都有着重要的意义。j a v a 语言由于 其优越的跨平台性，在异构网络系统中使用愈加频繁。随着软件产品的急剧增多，越来越多的遗产代码 需要进行分析、理解、复用，对j a v a 程序进行依赖性分析的必要性也与日俱增。 由于j a v a 程序设计语言完全面向对象的特性，现有的依赖性方法已不能完全满足其分析要求。本文 在回顾传统依赖性分析方法基础之上，详细阐述了一种分层次的糊粒度依赖性分析方法，按照白顶向h 逐步求精的原则依次分析j a v a 程序在包级别、类级别以及方法级别上的依赖关系，并在语句级别的分析 中，按照按需细化的原则，只对所关心的语句进行依赖性分析，降低了系统依赖性分析的代价。在语句 级别的依赖性分析中，本文还进一步讨论了程序执行期间语句执行的概率信息，并提出了考虑语句执彳了 概率的依赖性分析方法。分别分析程序中不同的控制结构与方法调用方式，对其后续程序语句的执行概 率的影响，从而更加准确地描述程序在执行期间的依赖关系。本文介绍了分层次及概率依赖性分析在软 件重构、软件度量阻及软件测试等方面的一些应用。通过府用依赖性分析技术于软件重构中，对软件重 构的指标进行量化度量，并提出了基于模糊聚类技术的软件重构方法，可以对软件重构活动进行相对客 观的指导；基于对类中方法数目与它们之问的概率依赖信息综合考虑，本文对娄内聚度缺乏度量提出一 种改进，进一步提高类内聚度缺乏度量的准确性。 最后，在进行理论分析的基础上，本文给出了实现队上研究内容的原型系统的实现细节，并展望了 未来的工作方向。 关键字：面向对象依赖性分析粗粒度概率重构软件度量 东南人学硕士学位论文 a bs t r a c t p r o g r a md e p e n d e n c ea n a l y s i si so n eo ft h ei m p o n a ma n df l l n d a m e n t a ia c i i v i c i e sms o r e w a r ee n g m e e r l n g i t st 1 1 eg m u n d w o r ko fp r o g r a ma n a i y s l sa n du n d e r s t a n d i l l g ，a n di t s l m p o n a n 【mm o s ta r e ao fs o t 、t w a r e e “g i n e e r i n g ，s u c ha sp r o g r a n ls l i c i “g ，r e v e r s ee n g i n e e n n g ，s o n w a r et e s t l n ga 1 1 d s o f t w a r er e f k t o r i “gj a v a p r o g r a m “n gl 柚g u a g ei su s e dm o r ea n dm o r ef r e q u e n t l yi nt h eh e t e m g e n e o u sn e t w o r ks y s t e mb e c a u s eo fl t s s u p e n o rp l a t f o r mi n d e p e n d e n c e t h em o r ej a v as o f t w a r ep r o d u c tw eh a v e ，t h em o r e1 e g a c yc o d en e e dt ob e a n a l y s e d ，t ob eu n d e r s t o o d ，曲dt ob er u s e d t h en e c e s s i l yo fa n a l y s l n gm ed 。p e n d e n c eo fj a v 8p r o g 硎1 1 s i n c r e a s e sg r a d u a l l y n o w a d a y s ，d e p e n d e n c ea n a l y s i sm e t h o d so nh a n dc a 衄o ta c c o l n l o d a t et h ea n a l y s i n gr e q u i r e m e n to fj a v a p r o g r 黝i n g1 a n g u a g ef o ri t sc o m p l e t e l yo o o r i e n tc h a r a c t e r i s t i c t h l st h e s l si n t r o d u c e sah l e r a r c h l c a la n d c o a r s e g r a m e dd e p e n d e n c ea n a l y s i st e c h n 0 1 0 9 ya f t e rr e v j e w i “gt h et r a d i t i o n a l d e p e n d e n c ea n a l y s l s t e c h n o l o g i e sa n da n a l y s et h ed e p e n d e n c eo fj a v 3p r o g m m sa tt h ep a c k a g el e v e l ，t h ec l a s sl e v e la n dt h ef u n c t l o n l e v e lr e s p e c t i v e l yb yt h 。p r i n c i p l eo f ”t o pd o w n ，p r e c i s es t e p w i s e ”a tt h es t a t e m e n t1 e v e l ，m ep a r t i c u l a r s t a t e j m e n t sa r ea n a l y s 甜mo r d e rt or e d u c et h ec o s lo fc o n s t r u c t i n gt h ew h o e p r o g r a md e p e n d e n c er e l a t i o n s h 】p a tt h es t a t e m e n tl e v e l ，m e nm n n i n gp r o b a b l l i t yo f 血es t a t e m e n t sl nn l n t l m e1 sd l s 吼l s s e da n dt h er n e t h o do f d 。p e n d e n c ea n a l y s i sw h i c hc o n c e m i “gt h en l n n i n gp r o b a b i l i t yo fs t a t e m e n t sl sp r o p o s e dw ed i s c u s s e dm e e 髓c to fd l f f e r e n tk i n d s 。fc o n t r 0 1s t a t e m e n t sa n dm e i h o d sc a l il np r o b a b i t i t yo fs 。q u e n ts t a t e m e n t s ，s ot 1 1 a tw e c a nd e s c r i b e 血er u n t i m ed e p e n d e n c er e l a t l o n s h i pi nm o r ed e t a i l s t h e 血e o r ya i l dt h ea p p l l c a t i 。no fi h e d e p e n d e n c ea n a i y s i sc o n c e m l n gt h ep r o b a b i 工i t yi si n t r o d u c e ds e q u e n t i a l l yi nt h et h e s i s k 王n t r o d u c ean o v e l i e c h n o l o g yo f 印p l y i n gm ef u 2 z yc i u s t er i n gt c c l l l l o l o g yt os 。胁a r er e f a c t o r i n g ，w h l c hc a “q u a n i l f yt h e c h f a r a c t e r so fs o r w a r er e f k t 。r i n ga n dh e l pt h ep r o g r 删n e ft or c f a c t o 。p r o g r a m sm a1 1 1 0 r e 。b j e c t i v ew a yw 毫 a l s op m p o s ea ni r n p r o v e m e n io f l c o m ( l a c ko f c o h e s j 彻m e 研c ) b a s e do nt h ec o n s i d e r a f 】蚰0 f 出e 删m b e f so f a n d 廿1 ed e p e n d e n c ep r o b a b l l i t yo f t h em e t h o d si nt h ec l a s s ，w h i c hc a ni m p r o v et h ea c c u r a c yo fl c o m a tt h el a s tp a r to fm et h e s i s ，4p r o t o t y p eo ft h et h e o r i c a lr e s e a r c hl s i m p i e m e n t e da n dt h 。p r o s p e c to ft h e f h t u r ew o r kj sd r e s e n t e d k e y w o r d s ：o b j e c t o r i e n t e d ，d e p e n d e n c ea n a l y s l s ，c o a r s eg r a i n ，p r o b a b l l l ty ，r e f k t o r 血野s o f t w a r cm e t r i c s 东南大学学位论文独创性声明 本人声明所早交的学位论文是我个人在导师指导f 进行的研究t 作及取得的研究成果。尽我所知，除 了文中特别加以标注和致i 9 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获 得东南人学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同忐列本研究所做的任俐责献 均已在论文中作了明确的说明并表示了谢意。 研究生签名：玺黛日期：童竺! 垒笙! 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图节馆有权保留本人所送交学位论文的复印什和电子文档， 可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密 期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布 ( 包括f 0 登) 授权东南大学研究生院办理。 研究生签名：圣菱 导师签名 期： 第一章引高 1 1 选题依据 第一章引言 随着计算机技术的不断发展，软件的规模成指数级扩大，而软件的复杂度也同步增长。作为程序开 发与测试人员，若要对原有的软什进行维护与测试，则首先必须要对程序的行为进行分析理解。面对越 来越庞大的软件规模，手t 分析的可能性已经基本被否决。我们必须寻找一种可以自动对程序进行分析 的方法，为开发测试人员提供一些相关信息，以帮助其进行下一步的t 作。程序依赖性分析是一种比较 有效的程序分析技术。它通过分析程序语句之间的数据依赖关系与控制依赖关系，从而可以使得开发人 员可以从一个更高的角度来观察整个软件系统，更好的把握系统的特性与行为。 面向对象的程序设计方法已经逐渐成为软件开发技术中的主流。如何准确的分析面向对象程序中的 各种依赖关系对于开发出高质量的应用程序具有重要的指导意义。多数的面向的对象设计语言为了兼顾 结构化的程序设计方法，在其语言特性中还保留着结构化的编程风格，例如c + + ，o b i e c tp a s c a l 等等。 而某些语言则采用完全的面向剥象的程序设计方法，对于任何程序都需要至少一个类来实现，例如j a v a 等等。在这些完全面向对象的语言中，j a v a 是与平台无关的，故其普适性较好。随着网络技术的不断发 展，以及多种网络应用框架的实现使得用j a v a 实现程序变得越来越容易，同时也使得j a v a 的用户人群 也越来越庞大。为了结合理论与实际，我们采用j a v a 语言作为本文的研究对象。 1 2 研究历程与现状 早在计算机出现之始，计算机只是作为一种科学计算的工具，而此时的程序殴计方式主要是编写机 器码。随着硬件技术的不断发展，计算机逐步摆脱了这种处境而成为一种通用的工具。采用机器码忙写 的程序可读性很差，很难进行维护和再次开发。 此后，程序员渐次使用了汇编语言与高级程序设计语言。这大大提高了程序的可读性与可理解- 陛。 高级程序设计语言的出现，使得软件开发从科学家的专利编程普通t 程技术人员都能使用的解决问题的 方法。而随着软件开发的广泛应用，人们常常发现软件开发的质量，效率，预算等等不能达到预期的目 标。这一问题被称为软件危机。为解决“软件危机”，在1 9 6 8 年的n a t o 软什会议上，与会专家首次提 出了“软件工程”这一一概念。此后，自顶向_ f ，逐步精化的结构化程序设计成为软件开发技术的主流， 软件开发得到了快速的发展。但是结构化的开发方法仍然没有解决软件危机。随后出现的面向对象的程 序设计的思想，也未能解决这一问题。f r e d e r i c kb r o o k s 在其经典著作人，【= j 神话中指出：实际上并没 有解决这一问题的“银弹”。 为了追求更高的软件质量，以及软件的可维护性，我们必须要对程序进行分析，理解。切片技术是 理解和分析程序的基础。所谓切片就是“可能影响变革v 在程序p 中某点状态口的所有语句和谓词的 集合” 3 】，而二元组毋v 则称为切片标准。它由m a r kw e i s e r 于1 9 7 9 年在其博士论文中首次提出，该 技术自提出以来在软件理解、测试、维护以及逆向下程中都得到了广泛并h 有效的应用，同时也得到多 方面的发展。目前主要的切片技术有以下几种： m a r kw e i s e r 方法 1 ，2 ，3 】：该方法由m a r kw e l s e r 提出。它通过遍历程序的控制依赖关系，利用数据 流方程与信息流方程来获取程序的数据依赖关系与控制依赖关系，从而获得过稃内的程序切片。这一方 法思想比较直接，但是存在调用上r 文问题，会引起程序切片的不准确。 h r b 力法【4 ：该方法由h o r w l t z 、r 。p s 、b 1 n k l e y 提出。它首先构建程序的系统依赖图并通过对所 得的系统依赖图进行两次遍历，来获得程序的切片。其优点足切片结果精确，但是构造系统依赖圈比较 复杂，尤其在构建面向对象程序的系统依赖图的时候，对丁i 面向对象程序设计语占中的某屿特性，如继 东南大学硕士学位论文 承、多态等，很难对其做准确描述。此外，每次生成切片都要遍历整个系统依赖圈，时间耗费较大。 h d c 方法 5 ：该方法由h w a n g 、d u 、c h o u 提出。它主要解决递归稗序的切片查找问题。该方法的 优点在于无调用上卜文问题，但是对于某些递归程序，该方法的时问复杂度会早指数级上升。 c h e n 方法 3 3 】：该方法由c h e nz h e n g q i a n g 提出。它是一种组合式、渐增式的切片技术，它强调 分析过程中的重用，以子程序作为切片的一个基本单元，对于程序间的切片，它封装了子程序内部的依 赖关系，而只对外部发布程序间依赖关系。此外它提出了“部分切片”的概念，即在计算切片的时候并 不是对于整个系统依赖图进行遍历，而只是查找某些特定的信息进行分析，这使得切片的效率得到较人 的提高。 l i 方法 3 4 】：该方法由l ib i x m 提出，其主要目的是解决面向对象程序的切片问题。它针对面向对 象程序的系统依赖图构造复杂，且容易山错的缺点，提出了分层计算切片的方法。它利用面向对象程序 中较为清晰的层次概念，逐步细化系统依赖图，具有较好的实用性。 此外还有一些其他的对于面向对象程序切片技术的一些扩展，例如，z h a oj a n j u n 提出了动态面向 对象依赖图以及系统依赖图网，以解决面向对象程序的动态切片与并发切片的问题：m j h a n d l d 利用 基本的系统依赖图对程序中的对象以及整个程序构建切片。在众多的方法中，在实际中虑用最为厂泛的 是h r b 的基于系统依赖图的两次遍历算法，有很多其他方法是在其基础之上做进一步的改进而得到的。 1 3 研究内容 如上所述，切片技术自提出以来，在多个领域得到了广泛的应用。它抽取了程序代码中分折人员所 关心的语句，而摒弃了无关内容，方便了程序的理解与测试。人们通过构造程序切片，可咀更方便的理 解程序的结构，可以更有效的构造程序的测试用例，可以更直接的发现程序中的对象。根据不同的分析 需求，我们可以将切片分成静态切片、动态切片、条件切片、不定形切片等。静态切片完全分析程序在 各种输入情况下的数据依赖关系与控制依赖关系，但是在时间与空间上的耗费过人，比较适合于程序的 分析与理解。w e j s e r 在最初提出的切片概念就属于这一范畴。动态切片则与之相反，它只针对某次运行 时刻的特定的数据输入来分析程序语句之间的控制依赖与数据依赖关系，故每次的时间与空间上的耗费 较低，但是它每次得到的切片结果往往不尽相同，常用于程序的测试。条件切片则避免了静态切片与动 态切片所体现的两个极端，它只对满足某个输入条件的特定子集的输入情况对程序进行切片分析。不定 型切片在不改变程序语意的条件，可以对程序结构进行一定的调整，简化程序使之可以更适合于程序的 理解。 通过研究，我们发现： 第一，面向对象技术的成熟与广泛使用暴露传统切片分析技术的一些弱点，如刘于程序的动态行为 的描述能力不够。由于程序的多态行为，在进行程序依赖性分析的时候，往往会使得系统依赖幽的规模 急剧膨胀。在实际使用中，一次构造完整的系统依赖图的耗费过高，而且也f i 是十分必要。在结合面向 对象程序的特点基础上，我们提出一种层次化的依赖性分析模型，并按照“自顶向下，逐步求精，按需 细化”的思想，在构建粗粒度的系统依赖图的基础上，逐步构建分析中所需精度的系统依赖图。 其次，以上这些传统切片技术由于其不同的特点在不同的应用领域中，各有优劣。但是它们都有一 个共同的不足，即所有的切片技术在对程序进行依赖性分析的时候将所有的语句的执行概率都看成是一 致的。但是实际上，情况并非如此。由于控制结构会改变程序的流向，所以被控制结构控制的程序语句 的执行就不可能如我们想象的那样具有同等的执行概率。如图1 1 示例程序所示，该程序只是简单的输 出l 到l o o 之间的整数，每输出l o 个数之后换行。由于判断语句5 的存在，使得后续受其控制的语句块 6 、7 与语句8 的执行概率不一样。从程序中我们可以明显看出，由于整形变量l 每次只是递增i ，在程 序的执行过程中，的取值不能铍l o 整除的概率是能被1 0 整除的概率的9 倍，故而语句8 的执行概率 是语句块6 、7 的执行概率的9 倍。而住一般的依赖性分析中，我们往往将其刚等看待。 第一章引言 由于忽视了这种由于控制依赖关系而引起的语句之间的概率的依赖关系，我们对于程序的分析往往 是不够精确的。例如在程序测试中，如果我们对于具有不同执行概率的程序段同等对待，那么对于那些 执行概率较低的程序段，测试的强度往往不够，在极端情况下，测试用例无法覆盖某些程序段。为此， 在分析面向对象程序的依赖性分析的基础上，我们在本文中分析了由于各种控制结构如选择结构如 i f e l s e 、s w i t c h 语句，循环结构如w h i l e 循环、f o r 循环语句，分支结构如b r e a k 、c o n t i n u e 与r e t u m 语 句等引起的依赖性的概率，并讨论了子程序之间由于引入关系、参数传递所引起的依赖性的概率，以及 异常处理所引起的依赖性的概率。 在构建系统的概率依赖图的基础上，我们分析了基丁概率系统依赖图的程序内聚度与耦合度的度量 方法，将概率的特性加入程序度量方法，改进了c k 度量对于面向对象程序内聚度缺乏度量的计算方法， 并利用模糊聚类技术，提出概率系统依赖关系了在软件重构、软件测试方面的一些应用。 1 4 论文结构 本文的主要章节的内容安排如下： 第一章为“引言”，主要介绍程序切片技术的一些基本概念与依赖性分析的背景知识，并简单分析现 有的各种切片技术共同存在的不足之处，提山本课题的可行性与必要性，最后简单介绍本文的结构。 第二章为“依赖性分析的基本概念”，主要介绍依赖性分析的一些基本概念，常见的切片方法的特点 以及他们之间的比较，并简单介绍面向对象程序的依赖性分析技术所需要注意的几个问题。 第三章为“j a v a 分层及概率依赖性分析”。这部分是本文的重点所在，主要讨论了面向对象程序在 逻辑上的层次结构，以及由控制语句引起的语句之间的概率依赖关系和由引入语句引起的模块之间的概 率依赖关系。在此基础之上讨论了面向对象程序的依赖性分析方法。 第四章为“分层及概率依赖性分析的应用”。本章结合获得面向对象程序的概率依赖关系，介绍依赖 性分析在软件重构中的应用，其中着重介绍了如何对依赖概率应用模糊聚类技术，改进重构活动；简单 讨论了基于依赖性的程序度量，并对现有的c k 度量中l c o m 提出一些改进；最后简单介绍了概率依赖 性分析在软什测试中的应用。 第五章为“系统设计与实现”，主要介绍了一个j a v a 程序的概率依赖性分析系统的实现。重点介绍 了系统设计中设计思想、基本框架、重要数据结构，以及依赖性分析算法，并讨论j ，系统实现中存在的 一些问题。 第六章为“总结”，该部分主要总结本人在本课题上己完成的工作，提出了还需要在进一步研究加以 改进的地方，并介绍了概率依赖性分析在软什一| = 程领域中的应用前景。 东南大学硕士学位论文 第二章依赖性分析的基础理论 程序单元之间数据流与控制流引发它们之间的数据依赖与控制依赖关系这些依赖关系影响着程序 的外部行为。依赖性分析方法主要有两种：一种是沿着程序执行流程顺序分析，称之为正向分析：一种 则正好相反，它从程序中的某个特定点出发，逆着程序执行流程反向分析，称之为逆向分析。正向分析 可以获得整个程序的依赖关系，而逆向分析则可咀得到该特定点对于程序中其他单元的依赖关系。当前 对于依赖性的分析主要是基于程序流图。在本章中，本文将介纠依赖性分析中的一些基本概念详细讨 论各种程序结构的控制流图。在此基础之上，介绍现有的各种廿j 片技术，并根据应用中的一些实际问题， 指出了这些切片技术存在的不足。 2 1 依赖性分析的基本概念 依赖性分析技术是程序切片的基础，也是分析和理解程序的一种重要方法。依赖性分析在程序调试、 软件测试、软件度量、代码维护、以及软件逆向工程中都有着广泛而重要的应片j 。用非形式化的语言描 述，所谓程序间的依赖性是指：程序块a 的取值或者流向会受到程序块b 的影响，那么我们称程序块a 依赖于程序块b 。如果程序块a 的取值会受到程序块b 的影响，那么我们称程序块a 数据依赖于程序 块b ：如果程序块a 的执行与否决定于程序块b ，那么我们称程序块a 控制依赖于程序块b 。我们提到 的依赖性分析主要是考虑程序之间的数据依赖与控制依赖。程序流图是依赖性分析的主要工具。f 面， 我们先介绍一下几个基本概念。 2 1 1 程序流图 程序流图( c f g ) 是一种通用的表示顺序程序流向的一种方法，它反映了程序中语句以及模块之间 的执行顺序与调_ h ；j 关系。控制流图可以用四元组c s ，e ，s 。s 。 表示。其中s 为图上的节点集合， 程序中的每个语句都对应于控制流图上的一个节点；e 为图中的边集，e f fs 。，s ：s ，且语句 s 】执行之后，s z 可能成为下一条执行语句) ：s 。表示程序的入ms 。表示程序的出口。一个程序可能 有一个或者多个返回语句，可以在图中设置一个虚拟节点，将其作为所有的返回语句的后继节点，从们 保证控制流图的完整性。 若s l 8 2 e ，那么称s 1 是s 2 的直接前驱，记为p r e ( s 1 5 2 ) ，相应的称s 2 是s i 的直接后继；语句s 的所有直接前驱的集台称为s 的直接前驱集，并记为p r e d ( s ) 。s 的所有直接后继组成的集合称为s 的直 接后继集，记为s u c c ( s ) 。【3 3 】将语句序列 记为p a c h ，p a t h 是一条可执行路径当且 仅当任意i 都有p r e ( s ，s ) 。在c f g 中，若s l ，s 2 之间存在一条可执行路径，且s l s 2 ，则称s l 是s 2 的 前驱记为p r c + ( 8 i ，8 2 ) ；反之，称s 2 是s i 的后继，记为s u c c + ( 8 l ，8 2 ) 。 4 第二章依赖性分析的基础理论 从程序入口到程序出口的任意条可执行路径，如果存在两个节点s ，s ! ，每条经过s ，的路径都要 经过s 2 ，那么称s 2 是s 1 的必经节点。 图2 1 是一个示例程序及其c f g 。在图中，e n t r y 是程序入口节点，e x i t 是程序出口节点：1 是2 的 直接前驱，f 2 ，3 是4 的直接前驱：1 、2 、3 分别是4 的前驱；l 是2 的必经节点：4 分别是l 、2 、3 后 向必经节点。 2 1 2 控制依赖 对于程序控制流图中的两个节点s ，s ：，若语句s 2 的执行与否决定于语句s ，的状态或s t 中变量的取 值，那么我们称语句s ：控制依赖于语句s ；若在语句s 。到s ：的执行路径在，不存在一个节点s ，使得 s 2 控制依赖于s 3 ，那么我们称s 2 控制流直接依赖于s l 。 定义2 1 若下列三个条件满足，则s i 控制流直接依赖于s 2 ，记为c d ( s ，s z ) 。【3 3 】 1 )s 2 与s l 间存在一可执行路径p a t h ； 2 )对p a 血上每个节点s ( s 2 除外) 都有p r e d ( s 1 ，s ) ； 3 ) p r e d ( s l ，s 2 ) a 控制依赖由控制流所引发，同时也影响数据流的分析，是依赖性分析的基础。在程序设计中，有三 种主要的控制结构，分别为顺序结构，判断结构与循环结构。顺序结构的语句在执行过程中依次执行， 而依赖主要是由于控制结构改变程序流向所引起的，在分析控制依赖的过程中，我们可以将顺序结构的 语句简单看成一个程序节点而不予考虑。因此我们只考虑判断结构、衙环结构等会影响程序流程的语句。 除此之外还有其他的一些原因会引起控制依赖，例如过程调用、异常处理等。 2 1 3 数据依赖 在讨论了程序的控制依赖之后，我们再来考虑一下程序的数据依赖。 在程序p 中，若有一变量v 。在语句s ，处被定义，而在语句s ：被引用，那么变量v 在执行过程中的 改动有可能影响到与”l 有关的变量v 2 在8 2 处的定义与取值，我们称语句8 2 数据依赖于s 。如果在从s l 到s ：的执行过程中，没有其他语句对变量v 进行操作或是改变，我们称s ：直接数据依赖丁s 。下面我 们给出程序控制流图中节点s 的有关定义，并在此基础之上给出数据依赖关系的形式化定义 3 3 】。 1 )定义集d e f ( s ) = ( x | x 是语句s 中值被改变了的变量 ： 2 )引用集r e “s ) = 倒x 是语句s 中引用的变量) ； 3 )输入集i n ( s ) = ( t ，x ) 1x d e f ( t ) 且存在一个从t 到s 的路径，在这个路径上不存在语句t ( t7 t ) ， 使得x d e “t ； 4 )输出集o u t ( s ) = ( t ，x ) l ( t ，x ) h 1 ( s ) x 硅d e f ( s ) ) u ( ( s ，x ) ix d e “s ) 。 子程序入口节点的输出集o u t 为所有形参。沿着程序执行流程由前至后，集合t n 和o u t 记录了各 变晕定义位置的变化，一个节点的输入集i n 足其所有直接前驱输出集o u t 的并集，即： i n ( s ) =u o u t ( s 1 ) 。 设s 。与s ：为控制流图中的两个节点，v 为变量，若下列三个条件满足，则称s 。关于变量v 数据流 直接依赖于s 2 ，记为d d “s i ，8 2 ，v ) 。 1 ) 8 2 对变量v 进行了定义，即v d e f ( s 2 ) ； 2 ) s i 执行时使用了v 的值，即v r e f ( s 1 ) ： 3 )s ：与s 1 间存在一可执行路径，且在此路径上，没有语句对v 进行煎新定义。 设s j 与8 2 是程序p 中两个语句，若存在变量v 满足d d 。( s i ，s 2 ，v ) ，! j ! j 称语句s 1 数据依赖s 2 ，记为 d d f 8 i ，5 2 ) 。 性质2 1 对于程序控制流图上任意两个节点s 1 、5 2 ，! j i | j 有 v ( v r e “s 1 ) ( s 2 ，v ) i n ( s 1 ) ) jd d ( s 1 ，s ! ) 5 东南大学硕上学位论文 在图2 ，】中，我耵j 得出：d e f ( 3 ) = t e f n p ，r e f ( 4 ) = t e m p ，i n ( 4 ) = ( 1 t e m p ) ，( 3 ，t e m p ) ) ，o u t ( 3 ) = ( 4 ， t e m p ) ，d d ( 4 ，1 ) ，d d ( 4 ，3 ) 。 2 1 4 程序依赖图 在之前进行的依赖性分析中，我们是基于程序流图来考虑的。这种方法实现比较简单，但是在实用 中不够直观。为此，我们采用一种图形化的方法来更加直观的表示程序语句之间的依赖关系。 程序依赖图p d g 是一个二元组( s ，e ) ，s b s 是对应于语句的顶点集，边集e 。e 1 u 岛，其中： e _ s - ，s 刊语句5 ，的执行与否直接取决于语句曲的执行状态 为控制依赖边： e 2 = l ( x ，y s 2 ) d c p d ( s 】) v ( x ，y ，s 2 ) d e p _ r ( s 1 ) 为数据依赖边，包括定义依赖和引用依 赖。 对于程序p 中的两个语句s 1 ，s 2 ，若有d d ( s 】，8 2 ) 或者c d ( s 1 s 2 ) 成立，则称则称s i 直接依赖于s 2 ，记 为d e p ( 8 】，s 2 ) 性质2 2 在顺序程序中，方法间的数据依赖与控制依赖具有传递性，即：对于方法p 中的三个语句 s l 、s 2 、s 3 ，若有d e p ( s 】，s 2 ) 且d e p ( s 2 ，s 3 ) ，则d e p ( s i ，s 3 ) 亦成立。 根据以上性质，我们可以定义传递依赖关系如下： 对于方法p 中的三个语句s 。、s z 、s 3 ，s 一传递依赖于，记为d e p ，( s i ，s 3 ) 。当且仅当f 面两个条件之 一成立： 1 ) d e p ( s l ，s 3 ) 2 ) s 2 ( d 。p ( s l ，s 2 ) d e p + ( s 2 ，s 3 ) ) 图2 3 是图21 所示m i n 方法的程序依赖图。在图上，由丁直接标明了依赖关系，所以我们可以很 清晰的了解程序语句之间的关系。结合程序控制流图，我们得出：3 控制依赖于2 ，而4 数据依赖丁1 ， 3 ，从而我们可以进一步推出4 传递依赖于2 。 2 1 5 系统依赖图 在实际的程序设计中，一项工程往往是很多子程序之间的协作。随着羊旱序规模的急剧增氏，一个项 目常常需要多个程序员的合力完成。为了能更好的1 办同二 作，必须程序进一步进行子过程之间的依赖性 分析。 子程序之间的依赖性主要来源于以f 儿方面： 1 方法调用引起的控制依赖与数据依赖。 方法之间调用或者方法自身的递归调用从广义上讲也是一种控制结构。它将程序的执行流程从一个 方法转移到另一个方法中，同时还进行了相应的参数传递。一般情况下，参数传递叮以分为二种形式： 传值，传结果，传5 1 j 。在传值的参数传递中，亓；参的值是不可以改变的，我们可以将看成r n 模式在 传结果的参数传递中，参数一般都是方法、函数的返同值，我们可以将其看成。叭模式：在传引川的参 数传递中，传入的形参的值在方法中是可读可写的，在返同渊州者时，形参的值可能发生改变，我”j 可 6 第二章依赖性分析的基础理论 以将其看成f h o w 模式。在j a v a 中参数传递都是传值的。 2 全局变量与局部变量引起的数据依赖。 不仅仅方法调用会引起数据依赖，全局变量与局部变量由丁其在全局或某一范围内对r 多个方法是 可见的，他们对于某个全局变量或局部变量的共同读写就构成了他们之间的数据依赖关系。剥于全局变 量、局部变量，可根据其定义修饰符来判断它是否可写，从而将其对应成加模式或是、f 一。“f 模式。 例如，对于被定义为f i m l 的参数，它就只能被定义一次。 上文刚刚提到程序依赖图无法表示方法之间的依赖性关系。前人对程序依赖图做了多种扩充，并利 用扩充后的依赖图来描述子程序间数据依赖和控制依赖关系。我们在此主要介绍应用最，。泛的系统依赖 图( s d g ) 【4 】和基于系统依赖图的切片方法。 系统依赖图( s d g ) 包含组成系统的各个子程序的程序依赖图。为了描述子程序间的参数传递过程， 引入了五种新的节点：加删d l 抽、加瑚a 厶。州、o c m d l 加、口c m d 。“和c 口胁抛。如果某参数是只读的，则 称为觑类型参数；如果某参数是只写的，则称为o 类型参数：如果某参数是可读可写的，则称为f 月o 类型参数。在s d g 中，每个加”口，珈节点表示一个只读形参：加m n ，o “描述只写形参；对每个可读可 写的形参则用一个加，m d l 抽和一个j 白圳d f _ o 埘两个节点剥应id c m d 厶1 月和口c f “- o 洲描述与形参对应的 实参；c d z h f 把是调用节点。全局变量作为子程序的参数。 加口f _ m 和加m d l o 以控制依赖于所在子程序的入r 节点；c f “a ，一m 和c m l 。洲控制依赖于调用点 c n t ! 一s t c e 。 在s d g 中，c 口，f 边连接子程序调用节点与被调用子程序的入r 节点；参数边表示参数传递过稃： p r n m e f e ，m 如r m e f e r o “o 边连接a c f “a f i n 与加r m n f m 节点( 加r m d f _ o “f 与a c f “a f o “f 节点) 。 2 2 程序切片 有了以上的基础知识，我们就可以进一步对程序进行切片分析。 切片技术于1 9 7 9 年由w e l s e r 在其博士论文f 1 中提出。所谓切片，简单而言就是指对程序p 中的菜 个语句s 的某个变量v 有影响的语句。利用这一技术，可以让程序员可以更加专注于他所关心的相关程 序语句可以更有效的进行程序调试、程序理解。 对程序p 、程序点s 和变量集n 其切片是由程序p 中的部分语句组成，这些语句的执行可能影响s 处r 中变量的值。其中，勺，p 称为一切片标准。 在实际程序设计中，往往在行代码中会包含对多个变量的赋值或引用，所以切片分析常刚于计算 程序中关于某个语句的切片，即切片标准为 ，它等价于 y ) 3 t e m p = y ； 4r e t u r nt e m p ； ) s t a t i ci n tm m ( m tx ，m iy ) 1 i n t t e m p 2 x ； 2 i f ( x y ) 3 t e m p = y ； 4 r e t u r n t e l n “ ( b ) 动志切片( c ) 条件切片 ( 其中阴影部分是切片标准 的切片) 图2 5程序2 1 ( a ) 的各种切片 2 2 2 现有切片的不足 尽管已有的切片技术已经得到较为成熟的发展，可以较好地应用于不同的需求之r 。例如静态切片 在程序理解、维护方面拥有广泛的应用，而动态切片则在程序间试与软什测试中拥有一席之地，条件切 片试图避免静态与动态切片的两种极端现象，不定形切片则在程序分析、可测试性转换方面有着明显的 优势，但是这些切片技术仍旧存在着一些不足。 首先，这些切片都是语句级别的切片。由于在语句层次上，其分析所需考虑的细节较多，故在构建 系统依赖图的时候代价昂贵。同时，语句级别的语义抽象层次较低，不能很好满足程序分析中的各种需 要。如需要进行对程序进行程序的理解或是模式的提取，我们只有从类层次或是方法层次来分析程序的 依赖性，才能较直接地获得我们所需要程序问的信息。 其次，在上述提到的多种切片技术中，尽管它们对于程序的输入输出参数有不同的假设，对于输入 参数有不同的条件制约，对于是否能对稃序进行变换也有不同的约定，但是总体而言，它们都具有一个 共同的不足：对于依赖关系的概率考虑不足。在实际程序的运行过程中，程序各部分之间的依赖关系荠 不是一成不变的。从图1 1 所示程序我们发现，在某些情况下，切片标准依赖于某个语句，而在其他情 况下，切片标准并不一定依赖于该语句。如果忽略这一点，往往会在软件开发中带来一定的负面影响。 例如，如果在程序中存在某个执行概率较低的语句块，该语句块执行时会自动申请一段存储空间，而该 语句块在执行完毕之后并没有释放所持有的存储空间。随着程序执行时间的增长，该语句块的执行次数 也逐渐增加，到达一定极限之后，就可能引起系统的崩溃。 因为现有的切片技术中的依赖性分析方法存在着以上的不足，为了更好、更准确地对程序进行依赖 性分析，本文将在下文中深入讨论面向对象程序的分层依赖性分析与概率依赖性分析。 2 3 本章小结 本章回顾了依赖性分析中的一些基本概念，以及程序切片的定义，并介耋f ；了各种传统的切 的特点 及其适用环境。通过分析各种切片技术的特点，本文发现它们所使用的依赖性分析存在的不足：首先， 对程序的依赖性分析缺乏层次，而不太适应于面向对象程序的依赖性分析；其次，来考虑程序执行时刻， 语句间的执行概率引起依赖关系不确定的特点，而使得对程序的依赖性分析不够精确。针对这两点不足， 本文在后续章节中将深入讨论如何改进已有分析技术，使得其更加适合于面向对象j a v a 程序的依赖性分 析，并能够得到更高的分析精度。 东南大学硕二学位论文 第三章j a v a 分层及概率依赖性分析 在上一章中，本文回顾了依赖陛分析与切片技术基本知识，也提出了现有切片技术中存在的不足。 为了解决这个问题，本文提出了一种分层次的、考虑语句执行概率的依赖性分析方法。通过对面向对象 系统进行分层次的依赖性分析，可以降低依赖性分析的复杂度；考虑语句执行概率的依赖性分析可以增 强程序依赖性分析的动态特性。在本章中，本文将阐述面向对象程序依赖性分析的特点，以及针对这些 特点进行依赖性分折的策略。在此基础上，详细阐述j a v a 程序的分层次依赖性分析与基于程序执行概率 的依赖性分析。 3 1 面向对象程序依赖性分析 3 1 1程序开发技术发展简介 设计程序的目的本质上是为了解决现实世界中的某项任务，所以程序开发的过程也就是将现实中的 对象映射到讨算机领域中的一个过程。程序设计语言就是将现实模型抽象为计算模型的一种工具。 在计算机技术发展的初期，程序开发人员直接使用机器语言进行程序设计，此时，数据与执行代码 并无区别，这类程序设计与计算机硬件底层最为接近，机器代码涉及过多的机器实现细节，而对于二现实 世界的抽象层次最低，软件开发的效率也最为低下。汇编语言是机器语言的一种改进形式。采用汇编语 言，程序开发人员可以将程序的数据与执行代码分离，大大提高了程序开发的效率，同时汇编语占还采 用比较有含义的变量名称、操作符向计算机传送相应的数据和执行指令，使得程序变得更加清晰，易于 维护。但是汇编语言还是偏向下硬件，其本质上是一种助记符，它的每个操作符只是对应一个或几个基 本的机器代码，对于现实模型的抽象能力还是比较低下，所以采用汇编语言进行程序设计还是一个相当 繁琐的过程。 二十世纪六、七十年代，计算机硬件技术得到了极大的发展，计算机的处理能力与计算述度也得到 极大的提高。程序设计开发的目标由注重程序的执行效率逐步转向关注程序的可读性、 】_ 维护性1 ，可移 植性，高级程序设计语言应运而生并得到了广泛的应用。高级程序设计形式化的记法来书写程序，同时 这种记法也比较接近自然语言。这使得软件的可读性有了显著的提高，提高了软件的开发效率。同时由 于其采用了与机器无关的语言，程序的可移植性较好。这一时期的主要代表语言有f o r t r a n ，a 1 0 2 乩c 以及p a s c a l 。但是随着硬件技术的发展，软件的规模也逐步膨胀，最终导致了“软什危机”。为解决软件 危机，开发人员提出了软件工程的概念，也提出了多种软件开发方法，其z t 最主要的是结构化程序设计。 结构化程序设计的主要设计思想是“自顶向f ，逐步求精”。该方法对后续的软件开发技术的发展有着重 要的影响。 尽管结构化