（计算机应用技术专业论文）程序切片技术研究及其在软件回归测试中的应用.pdf

南京航空航犬人学硕十学位论文 摘要 程序切片技术是。种分解程序的技术，可将一个复杂的大程序根据需 要分解成满足计算需要的小程序，同时保持所选程序功能的相对完整性和 计算结果的作确性。本文首先广泛、深入地研究了程序切片理论，对目6 u 各 种程序切片技术进行归纳总结，并简单介绍了几个程序切片工具。然后简要 回顾了回归测试的基础理论及面临的问题，在此基础上，进一步研究了程 序切片技术在降低回归测试成本方面的应用。 根据对程序切片技术在回归测试领域内应用现状的分析，可知目前相 关研究工作都没有区分回归测试所要检验的修改类型可操作性不好，并 且无法充分发挥程序切片技术的优点。为此，本文提出了一种利用“条件 切片”技术，来专门检验对于循环和选择结构中“控制谓词”的修改的方 法，从而更进一步降低回归测试的成本。 最后，本文提出了一个“利用程序切片技术降低回归测试成本”的实 用框架。该框架一方面可对一个软件修改前后的两个版本进行比较计算 出新版本相对于旧版本的差别程序，使得对差别程序进行回归测试与对软 件新版本进行回归测试等效；另一方面，该框架能够有效复用软件旧版本 的测试套件和测试结果，进一步减小回归测试套件的大小，使得要重新运 行的测试用例数目大大减少。 关键字：程序切片，条件切片，回归测试，测试工具，测试成本 徉序切片技术研究及其住软件同9 1 测试中的戍_ l j a b s tr a c t p r o g r a ms l ic i n gisap r o g r a md e c o m p o s i t i o nt e c h n 0 1 0 9 y w h i c hc a n d i v id eal a r g e ，c o m p l e xp r o g r a min t oas m a l l e ro n ew h i l em a i n t a n i n g p a r to fi t sc o m p u t a t i o no fi n t e r e s t m e a n w h il e ，t h ei n t e g r it yo ft h e c h o s e nf u n c t i o n a l i t ya n dt h ec o f f e c t n e s so ft h e c o m p u t a t i o n c a n r e m a in u n c h a n g e d f ir s to f a 1 1 ，t h et h e o r i e s o f p r o g r a ms l i c i n g a r e d e e p l y i n v e s t i g a t e d a f t e rs u m m i n gu p t h e s es lic i n gt e c h n i q u e s ，t h e d is s e r t a t i o ng i y e ss o m eb r ie fi n t r o d u c t i o n so faf e ws l i c i n gt 0 0 1 s s e c o n d ly ，t h ef u n d e m e n t a l t h e o r i e sa n de x i s t i n gp r o b l e m s o f r e g r e s s i o nt e s t i n ga r ea l s or e v i e w e dh e r e o nt h is b a s is t h e a p p l ic a t o no fp r o g r a ms l ic i n ginr e d u c i n gt h ec o s to f r e g r e s s i o n t e s t i n g tss t u d i e d ， a c c o r d i n gt ot h ea n a l y s i so ft h ep r e s e n ta p p o a c h e so fa p p l y i n g p r o g r a ms l i c in gt e c h n i q u e si nr e g r e s s i o nt e s t i n g ，w ec a ni n d u c et h a t t h ea p p o a c h e sd on o td i s t i n g u i s ht h em o d i f i c a t i o nt y p et ob ec h e c k e d t h e r e f o r ，ap u r e n e wm e t h o d t h a tm a k eu s eo ft h e c o n c e p t o f “c o n d it i o n e ds l i c i n g ”inr e d u c i n gt h ec o s to fr e g r e s s i o nc o s t i s i n t r o d u c e d ，w h ic hd e a lw i t ht h ec h a n g einac o n t r o l p r e d i c a t e a tth ee n do ft h ed i s s e r t a t i o n ，ac o n c e p t u a l lm o d e lo fa p p l y i n g p r o g r a ms l i c i n gt e c h n i q u e st or e g r e s s i o nt e n t i n gisg iy e n i nt h is f r a m e w o r k ，t h em o d i f i e dp r o g r a mt or e r u nc a nr e d u c e dt oa ne q u i v a le n t s m a l le r o n e ，a n dt h es iz eo ft h e r e g r e s s i o nt e s ts u it e isr e d u c e d g r e a t l v k e yw o r d s ：p r o g r a ms l ic i n g ，c o n d i t i o n e ds 1 i c i n g ，r e g r e s s i o n t e s t i n g ，t e s t i n gt 0 0 1 ，t e s t in gc o s t 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工 作所取得的成果。尽我所知，除文中已经注明引用的内容外，本学位论文的研究 成果不包含任何他人享有著作权的内容。对本论文所涉及的研究工作做出贡献的 其他个人和集体，均已在文中以明确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允许论文被查 阅和借阅，可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名： 日期： 南京航空航天人学硕十学位论文 第一章绪论 1 1 程序切片技术研究现状 “程序切片”的概念最初由m a r kw e is e r 于1 9 7 9 年在他的博【= 论文 中提出，w e is e f 认为“切片”的思想符合人们调试程序时所做的智力抽象， 因此建议将程序切片集成到调试环境中。以后陆续出现了多种大同小异的 程序切片的提法及许多计算切片的方法，程序切片如此多样化的主要原因 是，不同方面的应用需要利用切片的不同性质，例如在“程序调试”时，要 求所得切片必须是可执行的，因此切片既要保持程序的语义属性，又要保 持程序的句法属性；而在“程序理解”中，则只需要切片保留程序的语义 属性而不必保留程序的句法属性。 程序切片是由程序中影响切片准则的部分构成，“切片准则”是对程 序中某个感兴趣点的值的计算，通常表示为二元组 。程序 中直接或剧接影响对“切片准则( s l i c i n gc r it e r i o r ) ”c 的值的计算的 部分，称为关于准则c 的程序切片。 v e n k a t e s h ”1 曾根据不同的角度，对切片进行了三种分类：( 1 ) “静态切 片( s t a t i cs lic in g ) ”和“动态切片( d y n a m ic s l i c i n g ) ”，前者的计算与 程序的输入无关，而后者则依赖于一些具体的测试用例；( 2 ) 在静态切片中 又分为“正向切片( f o r w a r ds l i c i n f f ) ”和“逆向切片( b a c k w a r ds iic in g ) ”； ( 3 ) “闭合切片( c l o s u r es l ic e ) ”与“可执行切片( e x e c u t a b les l i c e ) ” 程序语言的一些特征如过程、随意的控制流、复合数掘类型及指针和过程 问通讯等，每个方面都需要一个特殊的解决方案。 d b in k l e yk g a l l a g h e r ”和f r a n kt i p “1 分别对面向过程的传统程序 切片技术及计算算法进行了详尽、全面的综述。 随着程序切片技术不断成熟，程序切片的应用渗透到软件工程的各个 领域；而随着应用的不断推广和深入，又反过来推动了程序切片技术的进 一步发展。根据软件工程不同领域的应用需要，传统程序切片技术产生了 各种各样的变体，并且还不断有新型切片技术出现。例如“静态切片”技 术除了传统的“过程内切片”及“过程间切片”之外，根据回归测试的应 用需要，还衍生了“调用上下文切片”1 及“控制切片”“】技术。对于传统 的“动态切片”技术，还衍生了“准静态切片”1 和“相关切片”7 技术， 此外将静念切片和动态切片技术综合起束，还可以得到“混合切片”技 程序切片技术研究及其在软什同9 测试中的应川 术。 除了对传统程序切片技术进行小的改动以适应不同应用需要外，还出 现了新的切片类型： “无定形切片、“分解切片”j 和“基于条件说明 的切片”技术等。“基于条件说明的切片”技术发展很快，很多人先后提 出了“p 一切片”、“条件切片”1 、“逆向条件切片”“、“f i ；后条件 切片”和“基本说明的程序切片”“等多种“基于条件说明的切片”技 术的变体。 在进行程序切片研究的过程中，涌现了一些原型切片工具。如 c h o p s h o p 、g h i n s u h 、s p y d e r 1 “、u n r a v e l 1 、v a l s o f t i l 、c o d e s u r f e r f 州】、 o s t ”和c o n s i t 。2 。其中c h o p s h o p 、g h i n s u 、s p y d e r 、u n r a v e i 、v a l s o f t 、 c o d e s u r f e r 是基于c 程序设计语言的切片工具，除u n r a v e l 可同时用于“动 态切片”和“静态切片”之外，其它几个切片工具只能进行“静态切片”： o s t 是目前唯一一个用于“面向对象切片”的程序切片工具；c o n s i t 是唯 一一个用来进行“条件切片”的程序切片工具。 1 2 回归测试技术研究现状 回归测试是软件工程中的很重要的环节，在软件投入使用以后的软件 维护阶段，经常需要进行回归测试，以适应软件需求变化所导致的程序修 改，和及时纠正软件使用过程中发现的错误。 回归测试可能是“改进性的( p r o g r e s s i v e ) ”，或”改正性的 ( c o r r e c t i v e ) ”，前者包括重测程序规格说明的主要改动；后者在基本保 持不变的规格说明上执行，因此只需要重测不影响程序整体结构的小的修 改。 在回归测试中，如果对于程序初始开发阶段的全部测试用例集合，都 进彳亍重复执行，代价就会很高；，如果随机选择这些测试用例的一个子集， 测试结果将十分不可靠。因此，要完成回归测试的目标，选择一个合适的 测试用例子集，将是很有用的。回归测试的这个子问题就称为“回归测试 用例选择( r e g r e s s i o nt e s ts e l e c t i o n ) 问题”3 1 。 另外，随着软件的使用、不断修改和升级，软件规模将会迅速膨胀， 这对回归测试产生了负面影响。因此要在其上重新运行回归测试用例的程 序太大，结果每个测试用例的运行时间都很长，这无论对人力还是机时都 会造成很大的浪费。因此，研究人员提出很多方法来减小回归测试过程巾 要重新运行的程序的大小。 概括来说，目前回归测试技术的研究重点着艮于两个方面：一是在保 南京航空航天人学硕十学位论文 证满足所选测试覆盖的前提下，减少初始测试套件的大小；二是在能够保 证所有受到修改影响的组件得到测试的酊提下，尽量减少要运行测试用例 的程序的大小。 1 3 课题来源及研究内容 根据程序切片技术的特点，及回归测试技术面临的问题，本文研究了 程序切片技术在回归测试中的应用。目前已有一些学者在从事这方面的研 究，并用取得了一定的成绩。 a g r a w a l 等人”3 提出了利用“动态切片”及其变体技术“相关切片”来 降低回归测试成本的三个算法。三个算法都试图将回归测试的大量工作转 移到离线处理，离线处理通常包括计算各种不同的切片。每个算法都试图 在“原始程序”的测试用例集合中，选择一个最小的子集，用柬测试“修 改后程序”的继承功能。这些算法并不考虑寻找新的测试用例，来覆盖新 的功能。 b a t e s 和h o r w i t z ”3 提出了在单过程的程序中利用程序依赖图p d g 来减 小回归测试成本的算法：b i n k l e y 等人“4 给出了两个补充算法，用于操作包 含过程和过程调用的程序，以减少其回归测试成本：第一个算法可以降低 了测试用例必须在其上重新运行的程序的复杂度：给定修改前后的两个不 同程序版本，该算法生成一个更小的程序d i f f e r e n c e s ，以捕获两个不同程 序版本中不同的行为。第二个算法是对b a t e s 和h o r w i t z 所做工作的一个 过程间扩展，根据“所有结点”和“所有流边”准则执行测试用例选择操 作。两个算法都在程序的系统依赖图s d g 上操作。两个算法结合使用，可 以同时减少必须重新运行的测试用例数目，咀及必须在其上运行的程序的 大小。 r o t h e r m e l 和h a r r o l ”“用柬降低回归测试成本的技术，利用p d g ( s d o ) 作为底层表示，且有限地使用了程序切片技术。他们同时给出了过程内和 过程问程序的算法。 第一个算法称为“s e le c t t e s t s ”，当在程序修改前后的两个不同版本 上运行时，输出可能产生不同结果的原测试套件的一个子集t 。第二个算法， 称为“c o v e r a g e r e q s ”，利用f 向切片，顺着修改后程序的依赖图“行走 ( w a lk ) ，收集其终端点与修改前程序中不同的流依赖边。包含在恢切片中 的每个流依赖边全部( 即两端) 都要被t 所包含。 根据w e is e r 定义的计算程序切片的数据流模型，g u p t a 等人“提出了 一个基于w e is e f 介绍| e | 勺切片算法的回归测试方法。垓疗沾硅式地榆测因为 利序切片技术研究及其在软什同门测试中的应_ l 一个程序修改而受到影响的“定义使用一关联( d u p a i r s ) ”。它识别所 有需要在一次修改后重新测试的“d u - p a i r s ”。 尽管程序切片技术在降低回归测试成本方面的研究工作已经开展不 少，不过，修改这些技术在处理程序中选择结构及循环结构中控制谓词的 修改方面效率却很低。本文试图通过对当前程序切片技术进行深入研究， 以期在处理对控制谓词进行修改后的回归测试方面获得性能上的更大提 高。 此外，程序切片技术在回归测试中的应用尚无完整的计算模型可以遵 循，这给将程序切片技术实际应用于回归测试过程带了不便。本文试图提 出一个较完整的模型的框架，以指导如何利用程序切片技术来降低回归测 试成本。 1 4 本文组织安排 根据“利用程序切片技术降低回归测试成本”的总体目标，首先广泛、 深入地研究了目前程序切片技术的发展状况，并对传统程序切片技术、新 型程序切片技术及各种变体进行总结和对比。 然后，在研究程序切片技术的过程中，分别检验能否利用这些程序切 片技术来降低回归测试成本。接下来在已有程序切片技术在回归测试方面 的应用基础上，提出了利用“条件切片”技术对选择和循环结构中控制谓 词的修改进行回归测试，来进一步降低回归测试的成本。最后，本文提出 一个完整的将程序切片技术用于回归测试过程、降低回归测试成本的一个 框架。 本文的内容组织方式如下： 第一章：绪论。介绍了程序切片技术和回归测试技术的研究现状及课 题来源及研究内容。 第二章：程序切片技术。介绍和传统程序切片技术、新型程序切片技 术及其变体，并简单介绍了几个原型程序切片工具。 第三章：回归测试技术。介绍了软件测试、测试数据充分性准则、选 择性回归测试方法、基于数据流的回归测试、增量回归测试及回归测试用 例选择等几个问题。 第四章：程序切片技术在回归测试中的应用。总结了酊人利用程序切 片技术用于降低回归测试成本的方法并在最后提出了利用“条件切片” 技术处理对控制谓词修改后的回归测试问题，进一步降低此类回归测试成 本的方法。 南京航空航大人学硕十学位论文 第五章：利用程序切片技术降低回归测试成本的模型。基于前面几章 的研究内容，提出了一个利用程序切片技术降低回归测试成本的实用模型。 科序切片技术研究及其在软r 1 门测试中的府i l j 第二章程序切片技术 2 1 程序切片概述 最初提出程序切片概念的是m a r kw e i s e r 。w e i s e r 之所以引入程序 切片，是因为他发现程序员在调试过程中会在脑子罩对程序进行抽象。 程序切片可应用到软件工程的很多领域，例如程序调试( p r o g r a m d e b b u g g i n g ) 、程序分析( p r o g r a m a n a ly s is ) 、软件维护( s o l t w a r e m a i n t e n a n c e ) 、软件测试( s o f t w a r et e s t in g ) 、再工程( r e e n g i n e e r in g ) 、 组件复用( c o m p o n e n tr e u s e ) 、藕合性度量( m e a s u r i o g c o h e s i o n ) 、算法 调试( a l g o r i t h m i ed e b u g g i n g ) 、 程序差别和集成( p r o g r a m d i f f e r e n c in g ) 、程序集成( p r o g r a mi n t e g r a t i o n ) 等。由于不同的应用需 要用到切片的不同方面的特性，因此提出了许多不同的程序切片概念及多 种计算切片的方法。 f r a n kt i p ”1 全面、详细地综述了( 面向过程的) 程序切片算法。 程序切片( p r o g r a ms l i c i n g ) 是由程序的一部分组成的，这些部分潜 在地影响在某个感兴趣点的计算值，这个感兴趣点即切片准则( s 1 i c i n g c r i t e r i o n ) 。典型情况下，切片准则是由( 行号，变量) 对组成的。程序 中直接或间接影响切片准则c 处的计算值的部分，称为关于准则c 的程序 切片( p r o g r a ms l ic in g w i t hr e s p e c tt oc r i t e r j o nc ) 。计算程序切片 的过程就叫进行程序切片( p r o g r a ms l i c in g ) 。 根据计算切片的方向不同，程序切片可分为“逆向切片( b a c k w a r d s l ic e ) ，和“正向切片( f o r w a r ds l i c e s ) ”。w e is e r 提出的程序切片只 是“逆向静态切片”，b e r g e r e t t i 和c a r r e ”提出了“f 向静念切片”的 概念。逆向切片”是由程序p 中影响到给定点p 的所有结点集合( p d ( ；、 s d g 图中的结点) 组成。“征向切片”是由程序p 中受到给定点p 影响的所 有结点集合组成。二者的计算方法类似。 w e is e r 定义的程序切片s 是一个缩减的、可执行的程序，它是通过从 程序p 中移除语句的，并且使s 复制了p 的部分行为。另一个常见的切片 定义是，程序p 中的语句和控制谓词的一个子集，这些语句和控制嘴测对 准则的计算有直接或间接影响，但却不一定形成一个可执行的程序。对于 同一个切片准则，如果没有其它切片包含更少的语句，则这样一个切片称 为c 语句最少”的。w e i s er 论征了“语句最少切片”不一定是唯一的，而 南京航空肮犬人学硕十学位论文 且确定“语句最少切片”问题也是不可判定的。 2 2 静态程序切片技术 静态切片的计算不需要考虑程序的输入。 定义2 1 ( 静态切片s t a t i cs 1 i c i n g ) ： 程序p 关于变量x 在语句i - 1 处的一个“静态切片”s ( x ，n ) ，是程序p 的一个子程序，对于使p 正常终止的所有输入，它能跟p 一样，计算出x 在n 点的值，且计算结果一致。 对偶( x ，n ) 称为“切片准则”，这个切片可通过从p 中删除零条或更多 语句得到，这些语句可确信对x 在n 点的值没有影响。 给定一个程序p ，一个静态切片s ( x ，n ) 可通过计算p 在n 处关于x 的 数据依赖的传递闭包、和p 在n 处的控制依赖而得到。 因为一个程序设计语言具有很多特征，因此实现一个切片算法要考虑 的因素也很多，例如结构化程序、非结构化程序和面向对象程序的切片算 法存在差别；当程序中允许全局变量、静态变量、别名、指针、数组、任 意控制流、过程涮通讯等情况时，处理方法也各不相同。f r a n kt ip ”给出 了各种程序切片算法处理上述语言特征时的细节变化，以及三种主要的切 片算法( w e is e r 提出的数据流方程“d a t a f l o we q u a t i o n s ”、0 t t e n s t e i n ” 提出基于依赖图的方法“d e p e n d e n c eg r a p h b a s e d a p p r o a c h e s ”、 b e r g e r e t t i 和c a r r “提出的信息流关系“i n f o r m a t i o r l f lo wr e l a t i o r l s ”) 在处理上述语言特征时，各自的变通做法。 根据计算对象范围的不同，静态切片可分为过程内切片、过程侧切片： 调用上下文切片是介于二者之间的静态切片。静念切片还有一个变体形式， 控制切片。下面分别利用基于依赖图的概念和算法来进行介绍。 2 2 1 过程内切片 “过程内切片( 1n tr a p r o c e d ur a lp r o g r a ms ijc in g ) ”是指切片时只考 虑一个过程内部的语句，而不必考虑过程调用时的上下文信息。 通常的过程内切片算法是先将过程表示成“程序依赖图p d g ( p r o g r a m d e p e n d e n c eg r a p h ) ”的形式，在p d g 图的基础上进行切片。 一个不包含过程的程序，其程序依赖图p d g ，表示为g p ，是一个有标 记的、有向的、多重图。其中每个结点( v e r t e x ) 代表程序的一种构造，例 如“声明( d e c l a r a t i or 1 ) ”、“赋值语句( a s s i g n m e n t s t a t e m e n ts ) ”、 “控制旧词( c o n t r 0 1p r e d i c ar e ) ”，另外往往还有一个特殊的结点称为“入 程序切片技术研究及其在软什同门测试中的应川 口结点( e n t r yn o d e ) ”。一般说来，一个“入口结点”是代表函数体的一 棵树的树根。 边( e d g e ) 代表结点之问的各种依赖关系，可通过附着在其上的标记柬 区分。具体地况，要区分三种依赖：“控制( c o n t r 0 1 ) ”、“数据流( d a t l f 1 0 w ) ”和“声明( d e c l a r a t io n ) ”依赖。 定义2 2 ( 控制依赖) ：如果结点v 2 的执行是由v l 所代表的谓语在执 行时决定的，则称v 2 “控制依赖( c o n t r o ld e p e n d e n c e ) ”于v l ，- 从而定 义了从v l 到v 2 的控制依赖边。其中v l 代表控制谓词( 它总是入口结点或 谓词结点) ，v 2 代表直接嵌套于循环或条件中的组件。如果p 的任一组件 不从属于任何控制谓词，则它控制依赖于入口结点。 定义2 3 ( 数据流依赖) ：如果数据从v i 传播到v 2 ，则称v 2 “数据流依 赖( d a t af i o wd e p e n d e n c e ) ”于v 1 ，即如果将v 1 和v 2 互换位置，则程 序计算的值将不同。 定义2 4 ( 声明边) ：程序中对变量的声明和定义之间存在的依赖关系 表示为“声明边( d e c l a r a t i o ne d g e ) ”，它可看成是一种特殊的数据依赖。 定义2 - - 5 ( 切片内路径可达) ：从w 到s 0 结点的r 切片内路径s s 。o 可达” 定义为，g p 上从起始结点w 到目标结点s o 的一条路径，且其边代表数据、 控制或声明依赖。 定义2 6 ( 过程内p d 6 切片) ：设g p 是个程序依赖图，s o 是g p 中的一 个结点，则g p 关于s o 的p d g 切片( 表示为g p s o ) ，是由到s o 切片内路 径可达的所有结点w 所组成的g 的一个子圈。即也就是说，g p s 中的结点， 是从结点s 开始、沿所有边、逆向遍历图g p 时所遇到的所有结点。 例如： v o jdm a i n ( ) 1 i n t ，= 0 ： 2 i n ts u m = o 3 i n tp r o d u c t = l ： 4 w h i l e ( j ，圳， 5 f 删= s u m + ， 6 p r o d u c t = p r o d u c t * i ： 7 ，：= ，+ l 8 囊京航空航犬人学礁+ 学侮论文 图2 1 槲序依赖幽p d g 浚疆穿关予甥冀准烈绱，p r o d u c t ) 粒过程内锈冀为( 遣矮p o e 表示 刚2 2 笑丁叨片准i j i i j ( 6 ，p r o d u c t ) 的p d g 切片 程序切片技术研究及其庄软仆闸门测试中的麻刖 2 2 2 控制切片 定义2 7 ( 控制切片c o n t r 0 1s l ic in g ) ”1 程序依赖图g 关于结点v 的“控制切片”，是程序依赖图g 关于结点 v 的传统“逆向切片”，前提是： ( 1 ) g 包含了g 的所有结点和一个新的未标记的结点v ； ( 2 ) g 包含的g 的所有边和从v 的控制先驱到v 的新控制边。 因此，控制切片捕获的是v 执行的条件，而不是在v 处使用的值。 “控制切片”的另一个定义是，对“g 关于v 的控制先驱”的集合进行 的逆向切片。 要对结点v 进行“控制切片”，可先创建一个和v 具有相同“控制前 驱”、而无“流前驱”的新结点v ，然后对v 进行p d g 切片。 圈2 3 芙 。切片准j j ! | j ( 6 tp r o d u c t ) 的的控制切片 2 2 3 过程间切片 “过程间切片( 1n t er p r o c e d ur a ip r o e r a ms lic in g ) ”是当程序中存在 过程调用时的程序切片。过程间切片既要考过程调用的上下文，也要考虑 过程调用的参数传递。因此需要将p d g 扩展为s d g 。 一个“系统依赖图s d g ( s y s t e md e p e n d e n c eg r a p h ) ”，是一个对主 程序m 建模所得p d g 图、及对程序的k 个过程( p r o c e d u r e s ) f 。进行建模所 南京靛空航犬人学颈十学能沧文 得的l j 个过程依赖图( p r o d e d u r ed e p e n d e n c eg r a p h ) 的集合、及用来捕获 过程调用上下文的额外的结点和边所组成的。 2 2 3 。 系统依羧豳孛薮增泌结点 过程调用可用一个“调用结点( c a l l 一s i t en o d e ) ”来表示。 参数传递可用四种参数结点柬表示：在调用端，参数传递用两个结点 鬟合表示，“实入结点( a c t u a l i nn o d e s ) ”和“实出结点( a c t u a l o uz n o d e s ) ”：“实入结点”和“实出终点”均控制依赖于“调丽结点”。 在被调用的过程中，参数传递是由两个结点集合来表示，“形入结点 ( f o r m a 卜i nn o d e s ) ”鞠“形出结点( f o r m a l o u tn o d e s ) ”：“形入结 点”幕| “形瓣结点”均控涮茯蔌于被磷溪过程懿“入墨露点”。 每个参数都包含“实入结点”和“形入结点”，只有需要修改以作为 过程调用结果返回的参数才需要“实比结点”和“形出结点”。 2 ，2 ，3 2 系统婊赣鹫中耨缮的送 将p d g 涟接起来组成一个s d g ，需要增加三种过程间边。( i ) “调用边 ( c a l le d g e ) ”连接每个“调用点”羊口所调用过穆的“入口结点”。“入 瓣缝点”匏入菠就是钼疲予萤数熬瓤蠢“调矮终点”戆数蘸。( 2 ) “参数 进入边( p a r a m e t e r in e d g e ) ”，一条从“实入结点”到相应的“形入缩 点”的边。( 3 ) “参数输出边( p a r a m e e r o u te d g e ) ”：是条从“形出 结点”到糟暾的“实出终点”豹边。 系统依赖鹭必须髓够袭示在调稻结点和被调掰过程之闻鹃壹接依赖， 及因过程调用而引发的传递依赖。如果( 相应于实出结点的) “形出结点” 鼹从( 相应予实入结点的) “形入结点”切片内可达的，则称自“实入结 点”鬟“实熬结点”存在“传递蔽赣( t r a n s i s t a n c yd e p e n d e n c e ) ”，速麓 于说过程依赖圈在形出结点处的过程内切片包含形入结点。 如果一个函数返回德到调用结点，则返曰的值可能数掘依赖于一个或 多个实参，此时，这些参数应当包含在坜片内。“影峨一参数边 a f i e c tp a r a m e d g e ) ”藏怒表嚼这个“参数一遮圈馕”依赖。这个边是从彩响返回信静 实际参数的“实入结点”，到函数的“调用结点”的边。 “返回一控制边( r e t u r n c o n t r 0 1 ) ”：表明了过程中的返回语句和 綮鼗在返繇添匀嚣羲其镌语匈之瓣熬侬羧，兰程序在一个返露语句逶出羁， 这些语句将不能执行。 “返回一链接边( r e t u r n l in k ) ”：连接了个返回缩点利其相关 躲蕊数调曩i 结点。 程序切片技术研究及其住软件回归测试中的应州 过程“概要信息( s u m m a r yi n f o r m a t i o n ) ”：在每个调用结点处的传 递依赖边的集合定义为这个过程的“概要信息，”它是“传递依赖”、“影 响一参数依赖”和“返回一链接依赖”这三种依赖的并集。 例2 v o i dm a i n ( ) i n ts u m ； i n ti j i = 0 ； w h i i e ( i ：? ，。 将p r o j 。扩展到全部轨迹，可定义为将此函数分别应用于轨迹中的单 个状态对，再求其联结( c o n c a t e n a t i o n ) ： p r o j 。( r ) = p r o j c ( n l ，o1 ) p r oj 。( n k ，ok ) 定义2 一l3 ( 动态切片准则d y n a m i c s l i c i n gc r i t e r i o n ) ： 程序切片技术研究及其在软件回归测试中的麻川 程序p 在输入i 上的一个动态切片准则是一个三元组c = ( x ，n ，i ) ，其 中1 1 是程序p 中的一条语句，x 是p 中变量的一个子集。 定义2 1 4 ( 动态切片d y n a m i cs l i c i n g ) ： 程序p 关于一个动态切片准则c = ( x ，n ，i ) 的动态切片s d ( x ，n ，i ) 是任 何一个语法f 确、并且可执行的程序p ，并且： 1 p 是从p 中通过删除零条或更多语句得到的； 2 任何时候当p 在具有“状态轨迹”t 的输入r 上中断时，则p 也 在具有“状态轨迹”t 的输入上中断，并且p r o j ( n ，x ) ( t ) = p r o j ( n ，x ) ( t ) 一个“动态切片”包含了：对于程序的一个特定执行( 而不是对每个使 程序正常终止的执行) ，能够影响一个程序点处的某些变量值的那些语句。 现有计算“动态切片”的方法，都是基于“向后”分析，即，在记录 了程序的执行轨迹之后，“动态切片”算法在执行轨迹中向后回溯，来计 算“动态切片”。 2 3 2 准静态切片 v e n k a t e s h “1 提出了一种介于静态和动念切片之间的新的切片概念，称 为“准静态切片( o u a s i s t a r ics i i c in g ) ”，应用在某些输入变量固定而 其它输入变量变动时，要对程序行为进行分析的场合。 定义2 一1 5 ( 部分输入) 设v i 。= v l ，v 2 ，v n ) 是程序p 的一个输入变量集合，程序p 关于 v i n = v 1 ，v 2 ，v k ，v i n 三v i n 中变量的一个“部分输入( p a r t i a ii n p u t ) ” 是任何集合i = ( ( v l ，i l ) ，( v 2 ，i 2 ) ，( v k ，i k ) ) ，其中ij ( 1 j k ) 是与变量v j 相同类型的一个值。 定义2 一l6 ( 完备) 设v i n = ( v 1 ，v 2 ，v n ) 是程序p 的输入变量集，v i n = ( v l ，v 2 ，v k ) 是程序p 的输入变量的一个子集，v i n v i n ，i = ( ( v 1 ，i l ) ，( v 2 ，i 2 ) ， ( v k ，i k ) ) 是对程序的一个部分输入，则i 关于的v i n 一个“完备 ( c o m p 】e t i o n ) ”是任何部分输入i = ( ( v 1 ，i l ) ，( v 2 ，i 2 ) ，( v k ， i k ) ，( v n ，i n ) ) ，i 关于v i n 的所有“完备”表示的集合表示为c ( i ，v i n ) 。 定义2 1 7 ( 满足) 设v i n 是程序p 的输入变量的一个子集，f ( v i n ) 是关于v i n 中变量 的一个一阶逻辑公式，f ( v i n ) 的一个“满足( s a t is f a c t i o n ) ”是对程 序关于v i n 中变量的任意满足公式f 的部分输入i 。“满足集s ( f ( v i n ) ) ” 是关于f ( v in ) 的所有可能的“满足”。 南京航空航天大学硕十学位论文 定义2 1 8 ( 准静态切片准则) 设v i n 是程序p 的输入变量的个子集，i 是对v i n 中变量的一个部分 输入。程序p 的一个“准静态切片准则( q u a s is t a t i cs l ic i n gc r i t e r i o n ) ” 是一个三元组c = ( i ，n ，v ) ，其中n 是p 中的一个语句v 是p 中变量的一个 子集。 定义2 1 9 ( 准静态切片) 程序p 关于准静态切片准则c = ( i ，n ，v ) 的一个“准静态切片”是任何 语法正确且可执行的程序p 使得： 1 p 通过从p 中删除0 或多条语句得到； 2 任何时候p 在输入i 上停止时，i c ( i ，v in ) 且v i n 是 程序p 具有状态轨迹t 的输入变量集，那些p 也在具有状态轨迹t 的输 入i 上停止，且p r o j 。，( r ) = p r o j 。) ( t ) 。 2 3 3 相关切片 对“相关切片( r e le v a n t s iic in g ) ”的定义需要使用“隐含依赖” 的概念。 定义2 2 0