（计算机应用技术专业论文）基于切片技术的面向对象程序测试技术研究.pdf

r e s e a r c ho ns o f t w a r et e s t i n g o fo b j e c t i o l u e n t e dp r o g r a m s b a s e do np r og r a m s l i c i n g ad i s s e r t a t i o ns u b m i t t e dt o s o u t h e a s tu n i v e r s i t y f o rt h ea c a d e m i cd e g r e eo fm a s t e ro fe n g i n e e r i n g b y g a oj i a n p i n g s u p e r v i s e db y p r o f e s s o rl i uy a ju n d e p a r t m e n to fc o m p u t e rs c i e n c e & e n g i n e e r i n g s o u t h e a s tu n i v e r s i t y a p r i l2 0 1 0 东南大学学位论文独创性声明 本人卢明所呈交的学位论文是我个人在导师指导下进行的研究1 ：作及取得的研究成果。尽我所知，除 了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获 得尔南大学或其它教育机构的学位或证书而使用过的材料。与我一同j i ：作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示了谢意。 研究生签名：l 潍日期：上尘盟 东南大学学位论文使用授权声明 东南人学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电子文档， 可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密 期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括以电子信息形式刊登) 论文的全部内容或中、 英文摘要等部分内容。论文的公布( 包括以电子信息形式刊登) 授权东南人学研究生院办理。 ) 研究生签名：件导师签名： 摘要 软件测试作为软件生存周期中的重要阶段，对于发现、纠正软件错误以及保证软件质量具有重要意义。 程序切片是一种程序分析理解技术，具有简化问题，缩小目标范闱等特点。基丁_ 切片技术的软件测试是一 种全新的软件测试技术，它把对整个料序的测试转化为只对某个程序切片的测试。根据程序的不同切片米 缩小软件的测试范围，并提高软件测试的效率。同时由于程序切片考虑程序存在的各种依赖关系( 不仅仅 是数据依赖和控制依赖) ，使得测试的准确性得剑提高。 面向对象程序特有的层次结构以及消息传递、类、对象、继承、多态、动态联编等特性使得适埘丁 过程化的分析技术不足以表示面向对象的程序系统，层次切片是一种根据面向对象科序的内在层次特性利 用分层方法计算的切片，是程序测试中缩小软件的测试范围、提高软件测试效率的有效方法。给定切片准 则，层次切片包含了影响兴趣变量的包、类、方法及语句。本文在对面向对象软件的特点和j a v a 分层特性 研究的基础上，提出了一种基于层次切片的面向对象程序逐层求精的测试方法。本文的主要一1 ：作有： 1 分析j a v a 语言在包、类或接口、成员方法和成员数据等级别的依赖关系。 2 根据兴趣变量所映射的各层次切片准则对j a v a 程序各层次级别的依赖图进行不同粒度的切片，计 算得到兴趣变量所影响的程序部分：包级切片、类级切片、方法级切片、语句级切片。 3 逐步求精，在各层次切片的基础上进行软件测试。 最后，在进行理论分析的基础上，本文给出了实现以上研究内容的原型系统及其实现细节，并眨望了 未来的j r 作方向。 关键词：软件测试，程序切片，面向对象，层次切片，j a v a a b s 订a c t s o f t w a r et e s t i n gi sa ni m p o r t a n tp h a s ei nt h el i f e c y c l eo fs o f t w a r ea n di si m p o a a n tf o re r r o r sf i n d i n g ， c o r r e c t i n ga n ds o f t w a r eq u a l i t ya s s u r a n c e t h ep r o g r a ms l i c i n gt e c h n i q u ei sak i n do ft e c h n i q u eu s e dt oa n a l y s e s a n du n d e r s t a n d sap r o g r a m ，w h i c hp o s s e s s e st h ec h a r a c t e r i s t i c so fp r o b l e ms i m p l i f i c a t i o na n dt a r g e tl o c a l i z a t i o n s l i c e - b a s e dt e s t i n gm a k e sp r o g r a m - s l i c et e s t i n ge q u a lt ow h o l e p r o g r a mt e s t i n gw h i c hc a nr e d u c et h es i z eo f s o f t w a r et e s t i n g ，a n dt h et e s t i n ge f f i c i e n c yi si m p r o v e d a n da l s o ，a sar e s u l to fp r o g r a ms l i c i n gt oc o n s i d e r p r o g r a m sf o rt h ev a r i o u sd e p e n d e n c i e s ( b u tn o to n l yd a t ad e p e n d e n c ea n dc o n t r o ld e p e n d e n c e ) ，s om a k et o i m p r o v et h ea c c u r a c yo fs o f t w a r et e s t i n g o b j e c t o r i e n t e dp r o g r a m ss p e c i a ll e v e ls t r u c t u r e ，m e s s a g et r a n s f e ra n do t h e rc h a r a c t e r i s t i cs u c ha sc l a s s ， o b j e c t ，i n h e r i t a n c e ，p o l y m o r p h i s ma n dd y n a m i cb i n d i n g ，e t c ，w h i c hm a k e st h ea n a l y z i n g t e c h n i q u ef o r p r o c e d u r e - o r i e n t e dp r o g r a m n o tc a t e rf o rt h eo b j e c t o r i e n t e dp r o g r a m m i n gs y s t e m h i e r a r c h i c a lp r o g r a ms l i c i n g w h i c hi ss t r a t i f i e dc a l c u l a t e db a s e do nt h ei n h e r e n tl e v e lc h a r a c t e r i s t i c so fo b j e c t - o r i e n t e dp r o g r a m si sa ne f f e c t i v e t e c h n i q u ef o rn a r r o w i n gt h e e r r o r s t ot h er e l e v a n tp a r t so fa p r o g r a ma n di m p r o v i n gt h ee f f i c i e n c yw h e n d e b u g g i n g g i v e nah i e r a r c h i c a ls l i c i n gc r i t e r i o n ，t h eh i e r a r c h i c a ls l i c ec o n t a i n so n l yt h o s ep a c k a g e s ，c l a s s e s ， m e t h o d sa n ds t a t e m e n t st h a ta c t u a l l ya f f e c tt h ev a r i a b l e si nt h es l i c i n gc r i t e r i o n b a s e do nt h ea n a l y s e so ft h e c h a r a c t e r i s t i c so fo b j e c t o r i e n t e ds o f t w a r ea n dt h eh i e r a r c h i c a lc h a r a c t e r i s t i c so fj a v a ，t h i sp a p e rp r o p o s e sa m e t h o ds t e pb ys t e pt on a r r o wt h es c o p eo fo b j e c t - o r i e n t e dp r o g r a mb a s e do nh i e r a r c h i c a ls l i c i n g t h em a i n c o n t r i b u t i o n so ft h i st h e s i sa r es h o w na sf e l l o w s ： 1 a n a l y s i so fj a v al a n g u a g ed e p e n d e n c ei nt h ep a c k a g e ，c l a s so ri n t e r f a c e ，m e m b e rm e t h o d sa n d m e m b e rv a r i a b l e s 2 a c c o r d i n gt ot h em a p p e di n t e r e s tv a r i a b l es l i c i n gc r i t e r i o no fj a v ap r o g r a m sa ta l ll e v e l sd e p e n d e n c e g r a p h ，c a l c u l a t e d t h e i m p a c t o fv a r i a b l ei n t e r e s t p r o g r a mc o m p o n e n t s ：p a c k e t l e v e ls l i c i n g ， c l a s s - l e v e ls l i c i n g ，m e t h o d - l e v e ls l i c i n g ，s t a t e m e n t - l e v e ls l i c i n g 3 s t e pb ys t e p ，s o f t w a r et e s t i n go nb a s i so fa l ll e v e l ss l i c i n g a tt h el a s tp a r to ft h et h e s i s ，ap r o t o t y p eo ft h et h e o r e t i c a lr e s e a r c hi si m p l e m e n t e da n dt h ep r o s p e c to ft h e f u t u r ew o r ki sp r e s e n t e d k e yw o r d s ：s o f t w a r et e s t i n g ，p r o g r a ms l i c i n g ，o b j e c t - o r i e n t e d ，h i e r a r c h i c a ls l i c i n g ，j a v a 目录 于| 蜀要i a b s t r a c t i i 目录i 第1 章引言1 1 1 选题依据1 1 2 国内外研究现状1 1 3 主要研究内容2 1 4 本文的组织结构3 第2 章程序切片技术4 2 1 程序切片简介4 2 1 1 程序切片的发展：4 2 1 2 程序切片的定义4 2 2 程序切片分类5 2 2 1静态切片与动态切片5 2 2 2 前向切片与后向切片5 2 2 3 面向对象切片6 2 2 4 其他切片技术6 2 3 程序切片技术的应用6 2 4本章小结7 第3 章面向对象程序切片8 3 1 面向对象程序特点分析8 3 2 程序依赖图和系统依赖图9 3 2 1 程序依赖图9 3 2 2系统依赖图9 3 3 扩充面向对象特点的系统依赖图分析1 0 3 3 1 面向过程程序依赖图存在问题1 0 3 3 2 面向对象程序依赖性分析1 0 3 3 3 面向对象系统依赖图1 1 3 4 面向对象程序切片1 2 3 5 本章小结一1 2 第4 章逐步求精的测试分析方法1 3 4 1 j a v a 语言的特点1 3 4 2 j a v a 层次模犁1 4 4 3 j a v a 依赖性分析1 5 4 3 1 包间依赖性分析1 5 4 3 2 类间依赖性分析1 5 4 3 3 方法间依赖性分析1 6 4 3 4 语句间依赖性分析1 6 4 4 分层次系统依赖图1 7 4 4 1包级依赖图1 7 4 4 2 类或接口依赖图1 7 4 4 3方法级依赖图1 8 4 4 4 语句级依赖图1 9 4 5 层次切片1 9 4 6 逐步求精的分析方法2 0 4 6 1程序的切片准则2 1 4 6 2 释序执行阶段2 l 4 6 3 测试分析阶段2 1 4 7 本章小结2 2 第5 章测试系统设计与实现2 3 5 1测试系统实验环境2 3 5 2设计思想2 3 5 3系统总体结构2 3 5 4 主要模块没计与实现2 4 5 4 1 抽象语法树分析构建模块2 4 5 4 2系统依赖图构建模块2 8 5 4 3层次切片计算模块3 1 5 s运行实例3 1 5 6 实验结果分析3 3 5 7 本章小结3 3 第6 章总结与展望3 4 致谢3 5 参考文献3 6 读硕士学位期间发表的学术论文3 9 第一章0 l 击 1 1 选题依据 第1 章引言 随着现代化软作产业的迅猛发展，软件功能需求的日益复杂以及由此带来复杂科度不断提高的软件没 计，使得软件开发中山现错误或缺陷的机会越来越多。与此| 一j 时。市场对软件质量的重视程度也越来越高， 导致了软件测试在软件项目实施过程中的重要性日益突出，软什测试已成为软件开发环。订中软件质量保 证、软件可靠性提高的关键步骤。 程序切片是一种程序理解分析技术，最早由m a r k w e i s e r 1 1 提出，它从语义角度对程序进行分解，通过 切片准则识别源代码中影响已知变量值的所有语句。在程序测试中，利刖科序切片有助于缩小源程序代码 测试范围得到相对于特定兴趣变量的程序切片集，对切片集的测试效果与整个程序的测试效果等同。这样 可以将对程序的测试缩小到一个很小的范同，有利丁对程序进行查找和错误定位。此外，程序切片技术对 于程序理解、分析、软件度量等提供了理论和技术支持。 面向对象编程近年来已经广为流行，已逐渐代替被j 泛使用的面向过程的开发方法。面向对象语言正 逐渐成为主流。由丁面向对象软住：本身所具有的特点，决定了它与传统的面向过程方法在开发思想上有着 根本的不同，面向对象软件具有类、继承、封装等特性，而过程软件则以功能模块间的控制流稃为重点。 由于面向对象程序的复杂性，简单使用以往对过程型程序进行切片的方法是不合适的，为了获得更准确、 更有效的面向对象样序切片，l a r s e n 和m jh a r r o l d l 2 提出了对象切片技术，这种技术主要通过扩展系统依 赖图来实现。由于参考文献1 2 1 提出的面向对象系统依赖图较为复杂且易出错，由此可能导致切片结果的不 准确。如何解决面向对象技术引入的新问题，更加准确有效的计算出切片是目前该技术研究的重点。 综上所述，本课题旨在通过对面向对象系统中涉及的相关技术进行深入研究分析，通过构建抽象语法 树得到j a v a 样序的系统依赖图，然后基丁该系统依赖图实现j a v a 程序的包、类、方法及语句级层次切片。 通过相关测试用例的输入实现对面向对象j a v a 程序的分析、测试。 1 2 国内外研究现状 基于程序切片的软件测试是一种以程序或程序和需求相结合为基础的测试，它根据程序的不同切片来 缩小软件的测试范围、提高软件测试的效率、辅助测试数据的自动生成等。同时由丁程序切片不仅考虑了 数据依赖和控制依赖，还考虑了程序存在的其他各种依赖关系，使得测试的准确性得剑提高。 程序切片技术最早由m a r k w e i s e r 1 提出，他论述了通过遍历程序依赖图得到过程内切片的技术。此后， h o r w i t z 通过将程序依赖图扩展为系统依赖图从而得到过程问切片，解决了切片技术中的过程调用问题； 而k o r e l 和l a s k i 3 4 引入了动态切片( d y n a m i c s l i c i n g ) 的概念、dl i a n g 和mjh a r r o l d 提出了适用于面向对 象程序的对象切片( o b j e c ts l i c i n g ) 技术【5 l 、k e i t hb r i a n 6 1 等人提出了适用于同归测试方面的分解切片 ( d e c o m p o s i t i o ns l i c i n g ) 技术以及c o n f o r a 7 等人提出主要用于程序理解和软件重用方面的条件切片 ( c o n d i t i o n e ds l i c i n g ) 技术。 现在基于各种不同切片的软件测试方法主要有基于静态切片的软件测试方法、基于动态切片的软件测 试方法以及针对于面向对象程序的软件测试方法等。静态切片是在编译时间，即程序尚朱运行时进行切片， 该技术对程序的输入不作任何假设，所作的分析完全以程序的静态信息为依据。因此静态切片包含了所有 与兴趣点处变量相关的语句，考虑了程序中所有可能的执行路径。其缺点是：容易包含不相关节点，具 1 东南人学硕，l j 学位论文 有很大的冗余性。主要是由于程序的执行路径无法静态判断，尤其是数组和指针变量无法静态确定。使 刚该技术的t 作量较人。因为要分析程序所彳丁可能的执行轨迹，静态切片技术一般刖丁程序理解与软件维 护方面。实际应用中，人们往往更关注某一变鼙的前向静态切片与后向静态切片的测试【8 j 。 动态切片是与程序中某个特定输入相关的科序切片，对兴趣变苗和输入米说与源程序产生相同的计 算。该技术出现较晚，现有研究成果人多是基丁后向分析的。动态切片计算过程使川用户的实际输入产生 的精确数据流信息进行分析，由丁动态切片只考虑某个特定输入，而静态切片要考虑所有可能的输入，通 常情况下比静态切片要小得多，因而动态切片要比静态切片精确得多。但是，动态切片的计算需要保留程 序的执行历史( e x e c u t i o nh i s t o r y ) 记录，占用的空问较大，尤其是对r 人规模的程序或者是循环次数较多 的程序，所消耗的资源不容小觑。实际应州中，通常将动态切片与程序执行历史( 程序后向执行) 相结合 进行测试9 】【1 0 l 。 由予面向对象程序一些新的概念与特性，如类、对象、动态绑定、封装、继承、消息传递以及多态， 因此面向对象程序切片不仅要考察语句和数据之间的依赖关系，还要考察各个类之间的关系。目前对它的 研究更多是侧重丁静态切片这一部分，而且基本都是基于依赖图的。李必信等人提出了一种逐步求精的基 于面向对象程序的分层切片方法【1 1 1 。在实际软件测试应用中，通常将对传统的系统依赖图进行面向对象的 扩充、切片准则的修改结合传统切片方法用于面向对象程序的测试1 2 】【”】。 由此可见，对于基于程序切片的软件测试技术，应具备在对程序准确测试精度基础上针对降低系统资 源开销的能力，而上述诸系统人多限制在某特定方面，能够有效兼顾各方的基于切片软件测试系统实现尚 未成型。 1 3 主要研究内容 根据j a v a 语言的具体特点，对j a v a 源程序按语句级、方法级( 过程级) 、类级、包级结构等进行分层： 首先对源程序进行分层，抽象出分层切片模型，并确定层次之间的各种依赖关系和流关系；然后在不同层 次上进行数据流和控制流以及依赖关系分析，建立各种流图和依赖关系图，从顶层出发利用切片算法( 两 阶段图形可达性算法) 结合各种切片准则分别计算各个层次不同粒度的切片，切片算法在层次之间移动时 采用逐步求精的算法( 如图1 - 1 所示) 。 包级依赣图 类级依鞭图 包级切片 类级切片 语句级依赖图语句级切片 图1 - 1 自顶向下逐步求精算法模型 本文以国家8 6 3 项目“基于维护和演化的软件质量保障关键技术研究( 2 0 0 7 a a 0 1 2 1 4 1 ) ”为背景，研 究基于切片技术面向对象软件测试的相关问题，主要研究内容集中在以下几个方面： ( 1 ) 系统各层次级依赖分析 可以把j a v a 源程序按逻辑结构分为四个层次，即包层、类或接口层、类或接口中的成员方法和成 2 第一章弓言 员数据层、方法中的语句和变鼍层。每个j a v a 文件由一个或若干包组成，包间通过i m p o r t 语句或通过类 中使， f j 的包前缀产生依赖关系；包中的类或接口通过继承、实现及类成员间的调川产生依赖关系；类或接 口中的成员数据和方法通过相互调用产生依赖关系；方法间通过若干语句和若干变量实现。通过抽象语法 树( a s t ：a b s t r a c ts y n t a x t r e e ) 构建系统依赖图( 控制依赖和数据依赖) 。 ( 2 ) 各级依赖关系基础上的切片生成技术 在系统依赖图的基础上通过兴趣变量映射的各层次切片准则计算变量的值所影响程序部分。通过 不同粒度切片的综合运用，可以得剑j a v a 程序各层次的切片，采j j 逐步求精的方法，通过较小的分析代价 米精确分析程序错误所在。 ( 3 ) 基于切片技术的错误定位 通过程序测试输入集及相关运行结果输出，由包级切片定位出错概率最人的包；进一步计算包中 相关类层次切片继而定位出错概率最人的类；计算类中相关方法层次切片定位出错概率最大的方法；最后 由方法中语句切片确定引起错误的根源以及错误影响范围。 1 4 本文的组织结构 本文共分为六章，具体章：肖安排如下： ， 第一章弓i 言：介绍了论文的研究背景、论文的主要研究内容及论文结构安排。 第二章程序切片技术概述：介绍程序切片的基本概念、发展、分类及其应用。 第三章面向对象程序切片：分析了面向对象软件的特点：封装、继承、多态以及面向对象程序依赖性； 介绍了面向对象软件基于过程型系统依赖图的扩充，即面向对象程序依赖图。 第四章j a v a 程序层次切片：从面向对象程序的逻辑层次入手，介绍了j a v a 程序的四层层次模型，分析了 各层次之间的依赖性关系，并提出了各分层的依赖图构建方法及其层次切片的计算，最后提出了逐步求精 的d e b u g g i n g 分析方法。 第五章系统设计与实现：给出实验系统的环境、设计思想、体系结构以及开发流程等，以及各层次中依 赖关系分析中用到的数据结构、相关算法等。 第六章总结与展望：对本文工作进行了总结并给出了对下一步工作的展望。 3 东南人学硕f j 学位论文 第2 章程序切片技术 本章首先简单介绍了程序切片技术的一些基本概念，其次介绍了现有科序切片的一些分类，并重点介 绍了目前为止程序切片技术在软件测试中的一些应州，以便深入理解程序切片技术对丁软件测试的作咐。 2 1 程序切片简介 程序切片技术是一种基丁数据流和控制流对程序分析、理解的技术，它通过一个切片准则提取出程序 中影响兴趣点变量值的所有语句，从而将程序减少到只包含与某个特定计算相关的那些语句以达到分析和 理解程序的目的。本节详细介绍程序切片技术的发展历史、定义及相关应用。 2 1 1 程序切片的发展 程序切片的基本思想是由m w e i s e r 于1 9 7 9 年在他的博十论文中首先提出，随后他义在1 9 8 1 年的国 际软件上程大会( i c s e 8 1 ) 上以及1 9 8 4 年的i e e et r a n s a c t i o no ns o f t w a r ee n g i n e e r i n g 国际权威杂志上发表文 章进一步形式地阐述了程序切片技术的基本思想。此后，在他的基础上义有许多人提出了不同的程序切片 ， 的定义和用于切片的算法。经过3 0 年的发展，程序切片技术现已得到了很人的丰富与发展。切片思想总 。 的发展情况可以分为以下三个阶段： 第一阶段( 1 9 7 9 1 9 8 4 ) ：基丁控制流图切片阶段。这一阶段主要是m a r kw e i s e r 进行的研究1 1 儿1 4 j ，该 阶段的特点是切片算法是基于控制流图( c f g ：c o n t r o lf l o wg r a p h ) 的，并利用数据流方程和信息流方程 来获得某个程序的切片。这类切片算法在计算那些顺序结构的程序以及具有简单的基本结构的程序时比较 适用。但对丁结构比较复杂的程序，利用该算法也就无能为力了。 第二阶段( 1 9 8 4 1 9 9 4 ) ：基于依赖图切片阶段。这一阶段主要是基r 程序依赖图( p d g ) 和系统依赖 图( s d g ) 的切片算法。首先是o t t e n s t e i n s 1 s 等人在1 9 8 4 年至1 9 8 7 年之间分别引入了基丁程序依赖图( p d g ： p r o g r a md e p e n d e n c eg r a p h ) 的图形可达性算法，以便用丁计算程序过程内后向切片( i n t r a p r o c e d u r a l b a c k w a r ds l i c e ) 。随后，h o r w i t z ，t r e p s 和d b i n k l e y l l 6 分别于1 9 8 8 年，1 9 9 0 年和1 9 9 2 年引入前向切片概 念及其算法和过程间切片概念以及基于系统依赖图( s d g ) 的两阶段图形可达性算法。同时，k o r e l 和l a s k i 【l 7 j l 嵋1 分别于1 9 8 8 年和1 9 9 0 年引入动态切片的概念和算法。这一阶段应该说是程序切片技术发展最成熟的阶段。 其中，最著名的就是产生了两阶段图形可达性程序切片算法。 第三阶段( 1 9 9 4 至今) ：面向对象程序切片阶段。从1 9 9 4 年开始，随着面向对象编程语言及设计方 法的兴起，开始了针对面向对象的程序切片技术的研究。这一阶段的程序切片研究以面向对象程序为主。 与此同时，还出现了程序切片的多种变体，如无定型切片，体系结构切片，条件切片以及规约切片等 1 9 1 1 2 0 l 【2 1 】1 2 2 】。这一时期的主要代表人物有f r a n kt i p ，m a n j e a nh o r r a l d ，c h r i s t o p hs t e i n d l ，m a r kh a r m a n 和z h a o j i a n j u n 等人。 2 1 2 程序切片的定义 程序切片就是指将一个程序中用户对某个兴趣点s 处的变量v 而言( 称为切片准则) 的代码都抽 取出来组成一个新的程序，这个新的程序就是源程序的切片，两者在功能上是等效的。根据切片准则的不 同，生成的切片不尽相同。任何形式的程序切片都可以通过对这个基本标准进行扩展而得到。 定义1 1 控制依赖：令g 是一个控制流图一( c f g ) ，n 和m 是g 中的节点，若节点n 、m 满足下列条 件，则n 控制依赖于m 。 4 第一二币程序切j 1 技术 1 1 ) 从n 剑m 之间存在一条可执行路径p ； ( 2 ) 对于路径p 上除n 、m 外的其他节点n ，节点n 都是n 的后必经点； ( 3 ) 节点n 不是：箝点m 的后必经点。 定义1 2 数据依赖：设n 和m 为c f 6 中的两个节点，v 为一变量，若节点n 、m 满足f 列条件，则r l 数据依赖于m 。 ( 1 ) m 对变量v 进行了定义，即v e d e f m ； 2 ) n 执行时使用了v 的值，即v u s e n ； 、( 3 ) 存在一条由节点m 到n 的路径p ，对丁路径上的其他一1 ，点m p 一 m ，n ) ，v 圣d e f m 】。 一般情况下，程序切片不仅与兴趣点定义和使川的变量有关，还与影响该变量的值的语句和渭词以及 受该变量的值影响的语句和谓词有关。 2 2 程序切片分类 白切片技术提出以来，伴随着各自领域的发展出现了许多略有不同的定义、相关的切片准则以及计算 切片的算法。按照切片准则不同，程序切片可分为静态切片和动态切片、前向切片和后向切片( 或过程内 切片和过程间切片) 、面向对象切片以及条件切片、分解切片等其他切片。 2 2 1 静态切片与动态切片 静态切片( 切片准则 ) 指对源程序进行静态分析，考察所有输入输出情况下的语句间的依赖关系， 它完全以程序的静态信息为分析的依据。分析所有的输入输出关系，因此静态切片包含了某个兴趣点变量 影响的所有相关语句，考虑了程序中所有可能的执行路径。动态切片( 切片准l 贝l j ：在输入为x 时， 影响变量v 在n 处的语句谓词集合) 指对程序某次执行的特定信息进行切片，即仅对丁程序中某一特定执 行路径的分析。该类切片方法中程序的执行受剑监控，一个动态切片包含了在特定输入时实际影响某个兴 趣点变量值的所有语句。静态切片和动态切片的区别如图2 - 1 所示。 r e a df x l ： v = 2 古x ： i ff y ) x x = x i ： y y 青y ； e 1 8 e x = x 2 ： y 2 y x ； w r i t ef x ) ； l 2 3 4 _ i 3 6 7 8 9 ：x = x 一1 ： y 2 y y ： e 1 - s e f - x = x 2 ： y 。y x ； w r i t ef x j ： ( a ) 源程序 ( b ) 1 2 3 4 _ - 3 6 7 8 9 ：x = x 一1 ： y ；y + y ： e l s e x = x 舌2 ： y 2 y x ； 州七ef x j ： ( c ) 图2 - i 静态切片和动态切片的区别 图2 - 1 中，( a ) 是源程序；( b ) 在最后一条语句处计算兴趣变量x 的静态切片；( c ) 当输入x = i 时在最后一 条语句处计算动态切片。 2 2 2 前向切片与后向切片 前向切片指所有可能受程序兴趣点处变量影响的语句和谓词集合。与此相反，后向切片指所有可能影 响兴趣点处变量的语句谓词集合。前向切片和后向切片的区别如图2 2 所示。 5 辫辫 东南人学顾一i ：学位论文 r e a df x l ： v = 2 x ： i ff v ) x 1 x = x 一1 ： y 2y y ； e l s ej x = x 2 ： y = y x ； 1r e a df x i ： 2 、= 二x ： 3i f 卜) x l 4：x = x 一1 ： 5v = v ：； 6e l s e 7x = x 士2 ： 8v = v x ： ( a ) 语句4 的前向切片 ( b ) 语句4 的后向切片 图2 2 前向切片和后向切片的区别 2 2 3 面向对象切片 自w e i s e r 提出程序切片概念后，虽然提出了许多川于过程型程序的切片算法，但由于面向对象程序 的一些新特性，如类、对象、封装、继承及多态等，使得简单使川以往过程型科序的切片算法失效。为了 获得更准确、更有效的面向对象程序切片，i a r s e n 和m jh a r r o l d l 2 l 提出了对象切片技术，这种技术主要通 过扩展系统依赖图来实现。面向对象的系统依赖图虽然能够形象直观地描述程序的结构以及各种依赖关 系，提高分析、理解稃序的准确性，但面向对象系统依赖图复杂而且在建立过程中容易出错，影响切片计 算的准确性。目前对它的研究主要侧重丁静态切片部分。如何以更准确、更高效的方法计算出面向对象程 序切片是目前该技术研究的重点。 2 2 4 其他切片技术 条件切片：由c a n f o r a 等人提出的条件切片f 2 3 】通过增加一个条件对静态切片准则进行扩充，根据这种 切片算法，把满足该切片条件的那些输入作为分析对象，这个条件对应着程序的某个初始状态。条件切片 主要用于程序理解和软件重用方面。 分解切片：f hkbg a l l a g h e r 等人提出了分解切片1 2 4 l 一种以将程序分解成不同模块为目的的切片技术。 分解切片是一组关注某一变量的切片构成的集合，可以捕获对某一变量的所有计算。分解切片不依赖于语 句在程序中的位置，将构成分解切片的程序切片按照一定的规则组成网格，利用这个网格实现对程序的分 解。使得可以直观的判断出一个模块中哪些语句和变量可以被安全地修改，即这种修改不会影响其他模块， 以及哪些语句和变量不能随意被修改。 2 3 程序切片技术的应用 由于程序切片具有简化问题，缩小目标范围的特性，这项技术在程序调试、软件测试、同归测试、软 件理解及软件维护等许多方面有着j “泛的应用圳1 2 州。 1 、程序调试：在程序调试过程中，对程序中存在的错误进行错误定位是一项斟难的工作，程序切片 技术可以帮助程序员很容易做剑这一点。在对大型软件项目的调式过程中，经常会遇剑对于某些输入会产 生正确结果，而对另一些输入则会产生错误结果。对于这种情况，如果采用多次运行程序，逐条语句跟踪 的方法，将会耗费大量的时间。而采用程序切片工具，可以构造输入语句的前向切片和输出语句的动态切 片，并取两者的交集。这样可以极大地缩小考察的程序范围。 2 、软件测试：对一个软件进行大规模测试后，对软件进行了某种, i v j 、的修改，是否要对程序进行重 新测试，是一个相当重要的问题。从程序切片的角度去考虑这个问题，首先应该找到程序新旧版本之间的 6 第一二章程序切”技术 不同之处。比较二者的切片和依赖图，对那些具有相同切片的。肖点不川考虑( ，点在新版本中的作川相 同) ；将那些在新版本依赖图中出现，而在i r 版爪依赖图中不出现的节点，标记出米“影响点”，通过计算 它的静态切片和前向切片，并取两者的交集。这样，如果要对程序进行重新测试，仅仅需要对此交集进行 测试，以减少一i ：作量的消耗。 3 、 回门测试：当软件系统修改后，为了保证系统的正确性以及修改后不会带来副作f j ，需要对其进 行重新测试，即同归测试。同门测试不同丁软件开发过程中的测试，冈为已经存在一些测试州例供选择。 对丁这些测试用例，可以全部重新测试一遍或者选择一部分进行测试。完全重新测试可能会消耗人量的资 源，并且大部分情况下只有一小部分代码会受到修改的影响，冈此，只有那些影响的代码需要重新测试。 对通过分解切片获得的补充部分便不需要重新测试。程序切片技术可以帮助我们获得那些受影响的代码， 从而有助予选择测试川例，进一步分析需要测试的代码、简化测试过程等。 4 、 软件理解：由于构造程序的切片实际上是构造初始程序的一个简化版本，所以科序切片有助丁对 程序进行理解。切片时移去释序中那些与兴趣点无关的部分( 语句和谓词等) ，从而提供了一种从源程序 中提取构件的一种手段。软什构架越来越被认为是软件系统设计阶段最重要的层次，利川构架切片可以帮 助理解软件的构架，为了计算一个构架切片，可以利用一个构架信息流图来表示软件构架中的信息流。对 软件构架的切片实际上是从软件源代码获得构架的一种有效机制。另外采用程序切片还可以理解函数的行 为。 其他应用：j z h a o 等人分别从不同的层次讨论过基于切片的可重用组件的提取问题f 2 7 j ；m h a r m a n 首 次将程序切片技术应用于模块间的耦合度量 2 8 1 ；k b g a l l a g h e r 和j r l y l e 利用程序切片技术解决软件安全问 题2 4 1 等。 实际上，程序切片技术的应用1 f 常广泛，在软件开发的各个阶段都可以发挥其巨人的作用。 2 4 本章小结 本章回顾了程序切片发展及定义，并介绍了各种传统的切片的特点其相关应用。通过分析各种切片技 术的