（计算机软件与理论专业论文）包含异常处理的java程序切片研究.pdf

硕士学位论文 摘要 程序切片是一种分析和理解程序的技术，通过分析程序语句之问的依赖性关 系自动分解源程序。程序切片技术在软件工程领域有广泛的应用，例如程序理解、 调试、维护、测试以及反向工程等。j a v a 系统依赖图( j s d g ) 可以用来表示j a v a 程序，在j a v a 系统依赖图中，结点表示语句或者谓词，边表示控制和数据依赖关 系。利用j a v a 系统依赖图，我们可以有效地计算程序切片。 e x c e p t i o n 是一类用于错误处理的特殊对象，它在j a v a 方法出错时被创建，并 利用t r y c a t c h f i n a l l y 机制抛出、检测和处理异常。当前的程序切片算法都不能正 确有效地处理异常结构，因为它们没有或不能正确的考虑异常引入的附加数据和 控制依赖关系。 在本文中讨论了异常结构对程序控制依赖和数据依赖的影响，采用了一种新 的策略来处理异常结构。新策略将t r y 、c a t c h 、f i n a l l y 块视为方法，并将可能抛出 异常的调用点视为谓词结点，这样可以表示异常对象附加的数据和控制依赖关系， 构造出包含异常处理结构的j a v a 系统依赖图。本文还提出了另外一种方法，为每 个调用点增加正常返回结点，对于可能抛出异常的调用点增加异常返回结点：为 每个方法增加正常退出结点，对于可能抛出异常的方法增加异常退出结点，并将 异常调用的返回结点视为谓词结点，用这种方法构造的系统依赖图更加精确。文 章还给出了适合这种系统依赖图构造的一些相关算法。 本文还给出了一种源程序分析框架，利用j a v a c c 和j t b 生成语法分析器和访 问器，实现对源程序信息的提取，并定义了一系列层次化的类结构保存源程序信 息。这些类结构能够保存源程序的结构信息，包括类之间关系，类与方法之间关 系，类与语句之间关系等。 最后，本文还实现了一个j a v a 程序切片原型系统，为j a v a 程序提供了软件分 析平台。通过这个平台，我们可以得到类层次图、方法调用图、方法控制流图、 方法控制依赖图、方法数据依赖图和程序切片。 关键词：软件分析；数据依赖；控制依赖；系统依赖图；异常处理 控制流；数据流；程序切片 包含异常处理的j a v a 程序切片研究 p r o g r a ms l i c i n gi s at e c h n i q u ew h i c hc a nb eu s e dt oa n a l y z ea n du n d e r s t a n da p r o g r a m b ya n a l y z i n gd e p e n d e n c er e l a t i o n so fs t a t e m e n t s ，i tc a nd e c o m p o s et h es o u r c e p r o g r a ma u t o m a t i c a l l y p r o g r a ms l i c i n gh a sm a n ya p p l i c a t i o n si ns o f t w a r ee n g i n e e r i n g s u c ha s p r o g r a mu n d e r s t a n d i n g ，d e b u g g i n g ，m a i n t e n a n c e ，t e s t i n g a n dr e v e r s e e n g i n e e r i n g j a v as y s t e md e p e n d e n c eg r a p h ( j s d g ) r e p r e s e n t saj a v ap r o g r a m ，i n w h i c hv e r t i c e sr e p r e s e n ts t a t e m e n t sa n dp r e d i c a t e s ，a n de d g e sr e p r e s e n tc o n t m la n d d a t ad e p e n d e n c e s s l i c e sc a nb ec o m p u t e de f f i c i e n t l yu s i n gt h ej s d g 、 e x c e p t i o ni sak i n do fs p e c i f i co b j e c tf o re r r o rh a n d l i n gi nj a v a ，w h i c hi sc r e a t e d w h e ne r r o r so c c u ra n da l s op r o v i d e sam e c h a n i s mo f “t r y c a t c h f i n a l l y ”t ot h r o wo u t ， d e t e c ta n dh a n d l er u n t i m ee r r o r s c u r r e n tp r o g r a m s l i c i n ga l g o r i t h m sd on o tc o r r e c t l y a n de f f i c i e n t l yd e a lw i t he x c e p t i o n h a n d l i n gc o n s t r u c t s ，b e c a u s et h e yd on o ta c c o u n t f o rt h ea d d i t i o n a lc o n t r o la n dd a t ad e p e n d e n c e si n t r o d u c e db ye x c e p t i o n s i nt h i s p a p e r ，w e d i s c u s st h ee f f e c t so f e x c e p t i o n o c c u r r e n c e sa n d e x c e p t i o n h a n d l i n gc o n s t r u c t i o n so nt h ed a t aa n dc o n t r o ld e p e n d e n c e so f ap r o g r a ma n d p r e s e n tan e wa p p r o a c ht o d e a lw i t he x c e p t i o n - h a n d l i n gc o n s t r u c t i o n s t h en e w a p p r o a c ht r e a t st r y c a t c h f i n a l l yb l o c ka s am e t h o da n dt r e a t st h ec a l l s i t et h a tm a y t h r o wo u ta ne x c e p t i o no b j e c ta sap r e d i c a t e t h u s ，t h ea p p r o a c hc a nr e p r e s e n tt h e a d d i t i o n a ld a t aa n dc o n t r o ld e p e n d e n c ei n t r o d u c e db ye x c e p t i o n - h a n d l i n gc o n s t r u c t i o n s a n dc o n s t r u c tj s d go ft h ej a v ap r o g r a mw i t he x c e p t i o n h a n d l i n gc o n s t r u c t i o n s t h i s p a p e r a l s o p r e s e n t s a n o t h e ra p p r o a c ht od e a lw i t he x c e p t i o n s ；t h a ti st oa d da n o r m a l - e x i tn o d ef o re v e r ym e t h o da n dt oa d de x c e p t i o n - e x i tn o d e sf o re v e r ym e t h o d t h a tm a yt h r o wo u te x c e p t i o no b j e c t s ，t oa d dan o r m a l - r e t u r nn o d ef o re v e r yc a l l s i t ea n d t oa d de x i t r e t u r nn o d ef o rt h ec a l l s i t et h a tm a yt h r o wo u to ra c c e p te x c e p t i o no b j e c t s t h i sa p p r o a c ha l s ot r e a t sr e t u r nn o d e so ft h o s ec a l l s i t e st h a tm a yr e c e i v ee x c e p t i o n o b j e c t sa sp r e d i c a t e s t h ej s d gi sm o r ep r e c i s et h a nt h ef o r m e ru s i n gt h i sa p p r o a c h t h e nt h i sp a p e rp r o v i d e sas e r i e so fp r o p e ra n dr e l e v a n ta l g o r i t h m st oc o n s t r u c tj s d g t h i sp a p e ra l s op r e s e n t saf r a m e w o r kf o rp r o g r a ma n a l y s i st h a tc a na n a l y z ea c o m m o np r o g r a mf o rj a v al a n g u a g e ，w h i c hg e n e r a t e sj a v ag r a m m a rp a r s e ra n dv i s i t o r u s i n gj a v a c ca n dj t bt o o l sa n dp e r f o r m st h ei n f o r m a t i o na b s t r a c tf r o mj a v as o u r c e p r o g r a m s w e a l s od e f i n eas e r i e so fh i e r a r c h yc l a s sc o n s t r u c t st op r e s e r v et h e i n f o r m a t i o no fp r o g r a m s w h a t sm o r e ，t h o s ec l a s sc o n s t r u c t sc a np r e s e r v et h e h i e r a r c h ya n do r g a n i z a t i o no ft h eo r i g i n a lp r o g r a mi n c l u d i n gt h er e l a t i o nb e t w e e nt w o c l a s s e s ，t h er e l a t i o nb e t w e e nac l a s sa n di t sm e t h o d s ，t h er e l a t i o nb e t w e e nam e t h o da n d 1 1 硕士学位论文 i t ss t a t e m e n t sa n dt h er e l a t i o nb e t w e e ns t a t e m e n t si nt h es a m em e t h o d a tl a s t ，w er e a l i z ea p r o t o t y p es y s t e mn a m e dj a v ap r o g r a ms l i c i n gs y s t e m t h i s s y s t e mp r o v i d e sap l a t f o r mf o ra n a l y s i so fj a v ap r o g r a m s t h r o u g ht h i sp l a t f o r m ，w e c a ng e tt h ec l a s sh i e r a r c h yg r a p h ，t h em e t h o dc a l lg r a p h ，t h em e t h o dc o n t r o lf l o wg r a p h ， t h em e t h o dc o n t r o ld e p e n d e n c eg r a p h ，t h em e t h o dd a t af l o wg r a p ha n dt h ep r o g r a m s l i c e k e yw o r d s ：s o f t w a r ea n a l y s i s ；d a t ad e p e n d e n c e ；c o n t r o l d e p e n d e n c e ；e x c e p t i o nh a n d l i n g ；c o n t r o lf l o w ； s l i c i n g 1 1 1 d e p e n d e n c e ；s y s t e m d a t af l o w ；p r o g r a m 包含异常处理的j a v a 程序切片研究 插图索引 图1 1 源程序及对应切片2 图2 1 系统依赖图的构成1 1 图2 2 一个j a v a 源程序1 4 图2 3s h m 方法的方法依赖图1 4 图2 4 程序( 续) 1 8 图2 5 对象扩展图2 0 图2 6 类依赖图2 0 图3 1 自然数的程序2 3 图3 2 异常处理示意2 7 图4 1 抛出异常方法的表示3 0 图4 2 调用点与被调用方法的关系3 1 图4 3 可能抛出异常调用点的控制关系3 2 图4 4 程序代码4 0 图4 5a l l a n 方法构造的系统依赖图4 1 图4 6 我们的方法构造的系统依赖图4 2 图5 1 系统总体框架4 6 图5 2 打开文件前4 9 图5 3 打开文件后4 9 图5 4 类层次图5 3 图5 5 方法调用图5 4 图5 6 类名和方法名的输入5 5 图5 7m a i n 方法的控制流图5 5 图5 8m a i n 方法的方法控制依赖图5 6 图5 9m a i n 方法的方法依赖图5 6 图5 1 0 切片标准输入5 7 图5 11 切片结果一5 7 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体己经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均己在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名：丑月如v日期：毗年y 月易日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密固。 ( 请在以上相应方框内打“”) 作者签名：王两愈、l 刷醴锄诋膨骅 日期：w 吖年f ，肿、日 日期：w 年厂月越日 硕士学位论文 1 1 研究背景 1 1 1 程序切片 第1 章绪论 程序切片是一种分析和理解程序的技术，通过分析程序语句之间的依赖性关 系自动分解源程序，程序切片技术在程序调试、回归测试、程序分析和理解、软 件维护以及反向工程1 1 叫等领域都有广泛的应用。 程序切片首先是由w e i s e r 在他的博士论文中提出来的【“，后来他又在1 9 8 1 年国际软件工程大会( i c s e 8 1 ) t 6 】以及1 9 8 4 年i e e e t r a n s a c t i o n s 上【7 】相继发表文章 进一步阐述了程序切片的思想和实现算法。w e i s e r 描述的程序切片定义如下： 定义一非形式化地，满足以下两个条件的程序称为切片： ( 1 ) 一个切片对应一个特定的切片准则 ，其中v 表示变量的集合， i 指程序中的某个点( 一般指某条语句) ； f 2 ) 程序p 对应切片准则 的切片s 可通过从p 中删除o 条或者多 条和切片准则不相关的语句得到，并且要保证程序p 和切片s 关于 切片准则( v i ) 的行为相同。 随着切片技术的发展，s h o r w i t z 等人给出了一个更精确的程序切片定义j ： 定义二一个程序切片是由程序中的一些语句和判定表达式组成的集合。这 些语句和表达式可能会影响在程序中的某个位置( 常用行号标识) p 上所定义的或 所使用的变量v 的值。 称为切片准则。 图1 1 给出了一个简单的c 语言源程序以及对应的程序切片。在这个程序中， 标号为s 7 语句的执行和i 的输出值只受b 1 中截取下来语句的影响，而与未截取下 来的语句无关。在这个程序中，语句s 7 只和b 1 中的这些语句相关，这些语句就 构成了这个程序对应于切片准则 的程序切片。类似地，可以得到这个程序 对应于切片准则 的程序切片如c 1 所示。 1 1 2 程序切片技术发展史 大体上说，程序切片技术的发展经历了从静态到动态、从前向到后向、从过 程内到过程间、从过程型程序到面向对象程序、从单一线程到多线程的发展过程。 包含异常处理的j a v a 程序切片研究 1 9 7 9 年【5 1 ，w e i s e r 等人提出了切片的概念，他们提出的切片属于静态切片， 而且只适用于单过程程序。这种静态切片技术在计算程序切片时使用静态的数据 流和控制流分析方法。该技术对程序的输入不做任何假设，所做的分析完全以程 序的静态信息为依据。 1 9 8 4 年1 9 ，o t t e n s t e i n 等人首先提出用程序依赖图表示程序，利用图可达性算 法可以有效地计算切片。但是这种方法也只能用来切单过程程序，实际的程序往 往包含多个过程。1 9 9 0 年【引，h o r w i t z 等人又提出了用系统依赖图描述程序，利 用两阶段的图可达性算法遍历系统依赖图来计算过程间切片，从而实现了过程间 程序切片。沿着图中的边进行后向遍历得到的切片称为后向切片，沿着边前向遍 历得到的切片称为前向切片。 e 1 m a i n ( ) e 1 m a i n ( ) e 1 m a i n ( ) s 2 i n ti ： s 2j n tj ：s 2i n ti ： s 3i n ts u m = 0 ； s 3 i n ts u m = o ； s 4 w h i l e ( i = l o ) s 4 w h i l e ( i = l o ) s 4 w h i l e ( i = l o ) s 5 s u m = s u m + i ； s 5 s u m = s u m + i ； s 6j + + ：s 6“+ ：s 6i + + ： ) s 7 p r i n t f ( “d ”，i ) ； s 7 p r i n t f ( “d ”，i ) ； ， s 8 p r i n t f ( “d ”s u m ) ； s 8 p r i n f f ( “d ”，s u m ) ； ) a ) 源程序b ) 对应切片c ) 对应切片 图1 1 源程序及对应切片 1 9 8 8 年【1 0 l ，k o r e l 等人提出了动态切片技术，他使用动态的数据流和控制流 分析方法，切片的计算过程依赖于程序的具体输入。输入不同，程序的执行路径 即不相同，从而使得程序切片也不相同。动态切片技术多用于程序调试和测试方 面。 1 9 9 1 年【“】，k bg a l l a g h e r 等人提出了分解切片技术，这种切片是由一组均关 注某一变量的程序切片构成的集合，可以捕获程序中对某一变量的所有计算。这 些构成分解切片的程序切片并非任意排列，而是按照一定的规则排列成网格。使 用分解切片技术，维护人员可以直观地判断出一个模块中哪些语句和变量可以被 安全地修改，而不必担心这种修改是否会影响到其他模块。由此就可以节省传统 软件维护过程模型中的回归测试时间。 硕士学位论文 1 9 9 7 年【1 2 】，mh a r m a n 等人提出了无定型切片的概念，这种切片技术主要应 用于程序调试领域，它在去除语句时适当地放宽约束，使得到的程序切片中包含 那些可能引起错误的语句。 静态切片只局限于对程序进行静态信息分析，过于片面；动态切片对程序的 分析以程序多次运行的测试结果为基础，这些测试结果依外界输入的不同而不同， 又过于复杂。为此，1 9 9 8 年i 1 3 i ，c a n f o r a 等人提出了条件切片。条件切片技术通 过增加一个条件扩展了传统的静态切片准则。在进行切片算法时，首先定义一个 对应着程序的某个或者某些初始状态的切片条件，只有满足该切片条件的那些输 入才会被分析。实际上，它是一种施加了一定条件的动态切片技术。如果存在从 满足条件的任一初始状态出发都不可能被执行的语句，则把这些语句去除掉后， 就得到了在这个切片条件下的程序切片，即条件切片。 面向对象设计与编程方法已经成为当前的主流软件设计与编制技术。由于面 向对象程序的复杂性，简单地套用以往对过程型程序进行切片的方法显然是不合 适的。为了获得更准确，更有效的程序切片，h o r r o l d “】等人对系统依赖图进行了 扩充，提出了类依赖图的概念，用来描述面向对象的程序。在系统依赖图构造之 后，利用h o r w i t z 8 】等人提出的两步切片算法来计算面向对象的程序切片。但是 这种方法的缺点是不能区别一个类的不同对象之间的成员变量，从而会在不同的 对象之间造成错误的依赖关系，计算出不准确的程序切片。t o n e l l a “ 对h o r r o l d 的方法进行了改进，当对象调用方法的时候，他将对象的所有成员变量作为参数 传递。l i a n g 1 6 j 等人提出了更好的方法，他将对象参数表示为一棵树，对象是根 结点，数据成员是叶子结点，这样能够更精确地表示对象。这种新的表示方法能 够区别同一个类的不同实例对象的数据成员，合理表示多态对对象参数和参数绑 定的影响。 在c + + 中，类可以多重继承，而在j a v a 中，类只允许单一继承，它的继承结 构比c + + 语言简单得多，这就使得继承类能够简单地重用基础类的方法定义。和 c 语言不同，在j a v a 语言中，方法重载时，也不需要定义为v i r t u a l 方法。而且在 j a v a 中，支持包和接口。由于j a v a 语言和c + + 语言有很多特性不同，k o v a c s l l 7 j 和z h a o 2 4 1 等人提出了专门针对j a v a 语言的程序切片，对j a v a 程序的特性进行了 描述，提出了接口、包、单一继承的表示方式。后来，徐保文【“i 等人又对面向j a v a 的程序切片方法进行了发展，并提出了对象切片、类切片和局部切片的概念。 1 1 3 包含异常处理的j a v a 程序切片 在j a v a 程序中，程序的执行可能会出现错误，当出现错误时，为了保证程序 能够继续正常地执行，j a v a 提供了一种异常处理机制。e x c e p t i o n 是一类特殊的对 包含异常处理的j a v a 程序切片研究 象，它在方法出错时被创建。当方法执行到可能出错的语句时，如果出错，该方 法将会抛出异常，程序中其他部分将被告之出现问题。异常抛出时，程序中相应 的异常处理部分，将会捕获异常，并对异常进行处理。在进行程序分析时，如果 不考虑异常处理结构的影响，将可能导致不正确的分析信息，从而导致程序切片 不准确。 如果异常处理结构很少出现，在程序分析时，为考虑异常处理结构的影响， 增加很多额外的开销，显然是不必要的。s i n h a 1 9 , 2 0 】等人对j a v a 程序中异常处理 结构的出现频率做了一下初步的统计，结果表明：所有的方法中，平均8 1 的方 法包含各种形式的异常处理结构；大约2 3 3 的类包含t f y 语句，2 4 5 的类包含 t h r o w 语句。在另一份研究中，r y d e r 等人【”j 也对j a v a 程序中异常处理结构的使 用频率进行了研究。在他们检验的方法中，有1 6 的方法包含异常处理结构。这 些数据都表明，在实际程序中，异常处理结构的使用频率还是相当高的。因此， 在进行程序切片时，语法分析考虑异常处理结构是必要的。 近年来，研究者们在不同的j a v a 程序分析方法中，已经开始考虑异常处理结 构的影响。c h o i 2 2 1 等人构造了控制流方式表示异常处理结构，并能实现对数据流 的表示。r o b i l l a r d l 2 3 j 等人对异常处理流进行了分析，并建立了一个工具以帮助对 程序中异常行为的理解。但是这些研究中，都没有人考虑到在控制依赖和程序切 片技术中考虑异常结构的影响。s i n h a 1 9 , 2 0 1 等人认为异常结构会引起过程间的控制 关系，提出了异常结构存在情况下过程问控制依赖关系的构造算法，并将之推广 应用到程序切片技术中。但是s i n h a 的方法也存在不足之处：( 1 1 没有将t r y 、c a t c h 、 f i n a l l y 等视为谓词结点，因此无法包含在程序切片当中；f 2 1 在切片过程中没有正 确考虑异常所带来的数据依赖关系。 1 2 程序切片技术的研究现状 1 2 1 当前研究中的问题 由于程序切片技术的广泛应用，近几年来程序切片技术得到了普遍关注。 o t t e n s t e i n 9 1 、h o r w i t z 8 】等人对面向过程语言的切片技术进行了研究，使之趋于成 熟。 随着面向对象技术的广泛应用，为了能表示面向对象的程序，h o r r o l d i “】、 t o n e l l a l l 5 1 、l i a n g 1 6 1 等人扩展了传统的系统依赖图，提出了面向对象的程序切片 方法。但是目前的研究也存在一些问题。 ( 1 ) 程序切片的不精确。在面向对象语言中，由于多态的存在，动态绑定是 普遍存在的。由于多态存在，无法在分析过程中，准确地确定对象的类型，在程 包含异常处理的j a v a 程序切片研究 象，它在方法出错时被创建。当方法执行到可能出错的语句时，如果出错，该方 法将会抛出异常，程序中其他部分将被告之出现l u j 题。异常抛出时，程序中相廓 的异常处理部分，将会捕获异常，并对异常进行处理。在进行程序分析时，如果 不考虑异常处理结构的影响，将可能导致不正确的分析信息，从而导致程序切片 不准确。 如果异常处理结构很少出现，在程序分析时，为考虑异常处理结构的影响， 增加很多额外的开销，显然是不必要的。s i n h a 1 9 , 驯等人对j a v a 程序中异常处理 结构的出现频率做了一下初步的统计，结果表明：所有的方法中，平均8 1 的方 法包含各种形式的异常处理结构；大约2 3 3 的类包含t r v 语句，2 4 5 的类包含 t h r o w 语f u 。在另一份研究中，r y d e r 等人 2 1 也对j a v a 程序中异常处理结构的使 用频率进行了研究。在他们检验的方法巾，有1 6 的方法包含异常处理结构。这 些数据都表明，在实际程序中，异常处理结构的使用频率还是相当高的。因此， 在进行程序切片时，语法分析考虑异常处理结构是必要的。 近年来，研究者们在不同的j a v a 程序分析方法中，已经开始考虑异常处理结 构的影响。c h o i 2 2 1 等人构造了控制流方式表示异常处理结构，并能实现对数据流 的表示。r o b i l l a r d ”j 等人对异常处理流进行了分析，并建立了一个工具以帮助对 程序中异常行为的理解。但是这些研究中，都没有人考虑到在控制依赖和程序切 片技术中考虑异常结构的影响。s i n h a 1 9 , 2 0 等人认为异常结构会引起过程间的控制 关系，提m 了异常结构存在情况下过程间控制依赖关系的构造算法，并将之推广 应用到程序切片技术中。但是s i n h a 的方法也存在不足之处：( 1 1 没有将t r y 、c a t c h 、 f i n a l l y 等视为谓词结点，因此无法包含在程序切片当中；( 2 ) 在切片过程中没有正 确考虑异常所带来的数据依赖关系。 1 2 程序切片技术的研究现状 1 2 1 当前研究中的问题 由于程序切片技术的广泛应用，近几年来程序切片技术得到了普遍关注。 o f t e n s t e i n 9 1 、h o t w i t z l 8 1 等人对面l 门过程语言的切片技术进行了研究，使之趋于成 熟。 随着面向对象技术的广泛应用，为了能表示面向对象的程序，h o r r o l d “j 、 t o n e l l a 【1 ”、l i a n g “】等人扩展了传统的系统依赖图，提出了面向对象的程序切片 方法。但是目前的研究也存在一些问题。 ( 1 1 程序切片的不精确。在面向对象语言中，由于多态的存在，动态绑定是 普遍存在的。由于多态存在，无法在分析过程中，准确地确定对象的类型，在程 普遍存在的。由于多态存在，无 去在分析过程中，准确地确定对象的类型，在程 4 包含异常处理的j a v a 程序切片研究 象，它在方法出错时被创建。当方法执行到可能出错的语句时，如果出错，该方 法将会抛出异常，程序中其他部分将被告之出现问题。异常抛出时，程序中相应 的异常处理部分，将会捕获异常，并对异常进行处理。在进行程序分析时，如果 不考虑异常处理结构的影响，将可能导致不正确的分析信息，从而导致程序切片 不准确。 如果异常处理结构很少出现，在程序分析时，为考虑异常处理结构的影响， 增加很多额外的开销，显然是不必要的。s i n h a 1 9 , 2 0 】等人对j a v a 程序中异常处理 结构的出现频率做了一下初步的统计，结果表明：所有的方法中，平均8 1 的方 法包含各种形式的异常处理结构；大约2 3 3 的类包含t f y 语句，2 4 5 的类包含 t h r o w 语句。在另一份研究中，r y d e r 等人【”j 也对j a v a 程序中异常处理结构的使 用频率进行了研究。在他们检验的方法中，有1 6 的方法包含异常处理结构。这 些数据都表明，在实际程序中，异常处理结构的使用频率还是相当高的。因此， 在进行程序切片时，语法分析考虑异常处理结构是必要的。 近年来，研究者们在不同的j a v a 程序分析方法中，已经开始考虑异常处理结 构的影响。c h o i 2 2 1 等人构造了控制流方式表示异常处理结构，并能实现对数据流 的表示。r o b i l l a r d l 2 3 j 等人对异常处理流进行了分析，并建立了一个工具以帮助对 程序中异常行为的理解。但是这些研究中，都没有人考虑到在控制依赖和程序切 片技术中考虑异常结构的影响。s i n h a 1 9 , 2 0 1 等人认为异常结构会引起过程间的控制 关系，提出了异常结构存在情况下过程问控制依赖关系的构造算法，并将之推广 应用到程序切片技术中。但是s i n h a 的方法也存在不足之处：( 1 1 没有将t r y 、c a t c h 、 f i n a l l y 等视为谓词结点，因此无法包含在程序切片当中；f 2 1 在切片过程中没有正 确考虑异常所带来的数据依赖关系。 1 2 程序切片技术的研究现状 1 2 1 当前研究中的问题 由于程序切片技术的广泛应用，近几年来程序切片技术得到了普遍关注。 o t t e n s t e i n 9 1 、h o r w i t z 8 】等人对面向过程语言的切片技术进行了研究，使之趋于成 熟。 随着面向对象技术的广泛应用，为了能表示面向对象的程序，h o r r o l d i “】、 t o n e l l a l l 5 1 、l i a n g 1 6 1 等人扩展了传统的系统依赖图，提出了面向对象的程序切片 方法。但是目前的研究也存在一些问题。 ( 1 ) 程序切片的不精确。在面向对象语言中，由于多态的存在，动态绑定是 普遍存在的。由于多态存在，无法在分析过程中，准确地确定对象的类型，在程 硕士学位论文 序切片时，就会造成多切的现象。程序运行的过程中，在条件语句当中，变量可 能被重新定义，这样后面使用这个变量的语句对这两条定义语句都会建立数据依 赖关系，而实际运行时，可能只对一条语句存在数据依赖关系。这样同样也会造 成程序多切的现象。在对象作为参数传递时，由于调用的方法可能只对对象的某 一个或者某几个成员变量进行了修改，而没有对对象的所有成员进行修改，在建 立系统依赖图时，如果将对象作为一个单独的结点表示，显然也是不合理的。 ( 2 ) 多进程程序切片的处理不完善。由于多进程并发程序执行的不确定性， 多进程程序切片存在许多难点。z h a o l 2 6 1 、c h e n g l 2 7 ，2 8 1 、g o s w a m i l 2 9 1 等人用图的可 达性来分析并发程序中语句之间的依赖关系，但其构造的并发程序间依赖关系是 不可传递的，这就使切片结果不准确。k r i n k e 3 0 1 通过附加的判断条件，构造了比 较精确的、不包含同步的并发程序依赖图，但是由于并发程序中同步是广泛存在 的，故该算法无法广泛应用。n a n d a ”j 将k r i n k e 的方法推广到包含同步的并发程 序中，时间的复杂度最大可达指数级，是个n p 难问题。 f 3 ) 异常结构对程序切片的影响。异常结构对程序运行过程中可能出现的错 误进行处理，在现代程序设计和编写中是广泛存在的。但是由于异常结构的特殊 性，在大多的程序切片方法中都没有考虑异常结构，从而使这些方法不符合实际 的程序。s i n h a i ”，2 0 1 提出了异常结构的表示方式，但是在切片过程中，会丢失t f v 、 c a t c h 、f i n a l l y 等结点，并且对异常结构所带来的数据依赖分析不准确。a l l e n ” 等人对s i n h a 的方法进行了改进，但是依然存在以下问题： 因为过程间控制依赖关系的存在，在过程间就会存在控制依赖边，这样 在程序切片时，如果出现对同一可能抛出异常方法的两次调用，就可能会出错； a l l e n 在切片过程中虽然考虑了异常结构所带来的数据依赖关系变化，却 忽略了因为异常的出现新产生的异常对象数据流，从而丢失了异常对象的数据依 赖关系； 在处理异常引起的控制流时，控制流没有从被调用方法返回调用点，会 造成原有的数据流错误。 1 2 2 国内的研究 东南大学的徐宝文等人对并行程序和j a v a 程序进行了深入的研究。针对并行 j a v a 程序1 1 8 , 3 3 i ，他们提出了并发程序流图、并发控制流图、并发程序依赖图来表 示并发程序，并且提出了一个切片算法来替代原有的两步程序切片算法，使程序 切片更准确。但是他们的方法时间复杂度最好为o ( n 4 ) ，仍然是指数级的。针对并 行a d a 程序 3 2 , 3 4 j ，他们提出了一种简洁、有效的并发程序表示方法并发程序 流图，讨论了由任务间同步引起的同步依赖和由访问共享变量引起的任务间数据 包含异常处理的j a v a 程序切片研究 依赖，建立了并发程序依赖图，并在此基础上给出了一种有效的并发程序依赖性 分析算法，得到一个比较精确的依赖集，较好地解决了并发程序依赖关系不可传 递的问题。动态切片仅仅包含那些实际影响切片准则中变量值的语句或谓词结点， 因此比静态切片更准确。徐宝文等人【3 5 , 3 6 】基于静态依赖分析，提出了自己的动态 切片方法，在程序执行过程中，他们使用程序依赖图和其他的静态信息减少需要 追踪的信息，从而大大提高了动态程序切片的效率。同时，基于这个切片模型， 提出了对方法、对象、类进行切片的方法。 南京大学的李必信、刘芳、郑国梁等人【3 7 叫0 1 打破传统的基于系统依赖图的程 序切片算法，提出了一种新型的切片方法一一类层次切片，采取分层的方式表示 程序，采取逐步精化的方式得到程序切片。但是他们的方法存在问题，只能分析 小型的程序，对于间接依赖关系层次非常多的大型程序和对象作为参数进行消息 传递的大型程序，可能会失效。 1 2 3 国外项目 a r i s t o t l ea n a l y s i ss y s t e m 这个系统【4 1 】是针对c 语占设计开发的，运行在s u n o s5 6 ( s o l a r i s2 6 ) 或者 更高的版本上，也可以运行在p e r l 上，它由m j h a r r o l d 领导a r i s t o t l e 小组开发 完成。a r i s t o t l e 系统主要提供程序的分析信息，这个系统本身并不是一个程序切 片工具，它只能为程序切片这样的一些软件工程工具的开发提供所需要的程序信 息。a r i s t o t l e 系统前端由程序和过程的控制流、数据流、符号表信息等组成，这 个前端主要由e d i s o nd e s i g ng r o u p sc 分析器【4 2 】辅助实现。它用数据库处理例程 访问存取分析信息，并且给用户提供了一个交互式的菜单使用工具，而且用户可 以以文本或者图形化方式查看结果。这个系统主要能实现和构造的分析信息有： 控制流图、控制依赖图、程序依赖图、数据依赖图、符号表、定义使用表、数据 流分析、控制流分析、控制图、过程间控制流图等等。 w i s c o n s i np r o g r a m s l i c i n gt o o l 这个工具 4 3 i 是由w i s c o n s i n 大学针对c 语言开发的，早期是免费提供的，现 在已经变成了一个商业化工具，商业化工具的名字是”c o d e s u r f e r ” 4 4 j 。w i s c o n s i n 切片工具能够实现后向、前向程序切片以及程序c h o p p i n g 。它主要有以下部分组 成： ( 1 ) 支持c 语言的前端平台，能够产生c 语言文件； ( 2 1 读c 语言文件并且产生控制流图的接口： f 3 1 系统依赖图模块，实现对系统依赖图的操作； ( 4 ) 建立系统依赖图的浏览器，通过它调用切片和c h o p p i n g 的操作，检验操 硕士学位论文 作的结果； ( 5 1 在批处理模式下运行切片工具的驱动。 这是一个比较完整和强大的工具，但是这个工具在开发时，仍然对可操作的 源程序做了假设和部分限制，因此对实际程序分析时还有待完善。 o b e r o ns l i c i n gt o o i ( o s t ) o s t 4 5 】是一个针对o b e r o n 2 语言开发的面向对象的程序切片系统。它在控制 流和数据流分析时，考虑到了继承、动念绑定、多态、函数的边影响、指针以及 由于参数引用所引起的别名等等，支持面向对象程序的过程间后向切片。由于别 名分析时考虑了变量的类型和它们声明的位置，所以别名分析算法很快而且有效。 静态切片结果是可视化的，它可以通过超文本从调用点链接到被调用的方法。 1 3 本课题的研究内容 程序切片通过分析源程序的数据依赖和控制依赖关系，达到自动分解源程序 的目的，在软件工程领域有广泛的应用。目前主要有两种方法【2 0 】计算程序切片， 一是沿着控制流传播数据流等式的解，还有一种是实现系统依赖图上的可达性算 法。本文主要针对包含异常处理的j a v a 程序，就第二种切片方法的后向静态程序 切片进