（计算机软件与理论专业论文）面向对象程序切片中类层次图的研究.pdf

摘要 面向对象程序切片中类层次图的研究是本论文研究的课题，它是面向对象程 序分析的一部分。本论文在研究现有的基于过程的程序切片和面向对象的程序切 片的基础上，结合面向对象程序设计语言c + + 的特征，提出一种新的层次化切片 c + + 程序的方法及其分层切片模型。通过构造类层依赖图、方法层依赖图和语句层 依赖图，对c + + 程序进行分层切片。本论文设计和实现了c + + 程序的类层次图， 为面向对象数据依赖分析和控制依赖分析提供上层框架。该类层次图有效的表示 了类之间的继承和创建等基本的依赖关系，基本解决了c + + 程序表示中继承、多 态等问题。同时，本论文对c + + 程序中嵌套类、友元、模板、结构、联合、局部 类和名字空间等特征在类层次图中的表示提出了解决方案。 关键词：面向对象程序切片类层次图依赖图分层切片 a b s t r a c t t h i sp a p e rd e a l sw i t hc l a s sh i e r a r c h yg r a p hi no b j e c t o r i e n t e dp r o g r a ms l i c i n g ， w h i c hi sap a r to f o b j e c t - o r i e n t e dp r o g r m na n a l y s i st e c h n i q u e b a s e do i lt h ep r o g r a m s l i c i n gt e c h n i q u e sa v a i l a b l eo fi n t r a - p r o c e d u m l ，i n t e r - p r o c e d u r a la n do b j e c t o r i e n t e d p r o g r a m an e w m e t h o do f s l i c i n gc + + p r o g r a mh i e r a r c h i c a l l yi sp r e s e n t e di nt h i sp a p e r b yc o n s t r u c t i n gc l a s s l e v e ld e p e n d e n c e g r a p h ，m e t h o dl e v e ld e p e n d e n c eg r a p ha n d s t a t e m e n tl e v e ld e p e n d e n c eg r a p h c + + p r o g r a mc a nb es l i c e dl e v e lb yl e v e l ac l a s s h i e r a r c h yg r a p ho fc 什p r o g r a m i sd e s i g n e da n di m p l e m e n t e di nt h i sp a p e r , w h i c hc a n r e p r e s e n t t h eb a s i ci n h e r i t a n c ea n dc r e a t i o n d e p e n d e n c e r e l a t i o n s a m o n gc l a s s e s e f f e c t i v e l y f u r t h e r m o r e ，f o rn e s t e dc l a s s ，f r i e n d , t e m p l a t e ，s t r u c t u r e ，u n i o n ，l o c a lc l a s s a n d n a m e s p a c e i nc + + s o l u t i o np r o p o s a l sa r ep r e s e n t e di nt h ep a p e r k e y w o r d s ：0 b j e c t - o r i e n t e dp r o g r a ms l i c i n g h i e r a r c h i c a ls l i c e c l a s sh i e r a r c h yg r a p h d e p e n d e n c eg r a p h 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：坐l 盔整日期：2 生堕：堡 关于论文使用授权的声明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果是署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩放或其他复制手段保存论文。 本人签名 导师签名 经凌垄 型! 堡 日期 r 期 2 0 0 37 ，l j 地! ：! 至 第一章绪论 第一章绪论 1 1 研究背景 随着网络技术的发展和自由软件的广泛使用，软件的安全，特别是军事领域 软件的安全已越来越受到人们的重视。由于计算机的安全性隐患( 包括无意的和 人为的) 大量存在于软件系统中，如系统入侵、信息窃取、病毒、以及由于程序 设计语言自身问题造成的各种安全漏洞等，使得在软件的使用阶段会发生意想不 到的错误，从而造成重大损失。 对于自主开发的软件，主要通过测试的方法检查所有可能的不安全因素。这 需要对软件的功能、特性等具有深刻了解，并且根据软件特性设计完备的测试集。 显然这种动态测试的方法并不适用于使用可重用软件的情况。因此，如何能在静 态时尽量检测出软件的安全性问题，避免不必要的损失，成为当前计算机安全领 域中需要研究的一个重要课题。 本课题是十五预研“软件安全性故障模式分析”项目的一部分。该项目重点 解决被广泛应用的程序设计语言c ，c + + 的程序分析技术和面向不同领域的软件安 全模式构建技术，最终提供一组与安全分析相关的方法，并研制出一个基于静态 分析的软件系统安全检查工具原型。 1 2 软件安全性分析 根据软件提供者与使用者之间是否存在约定关系，可以将静态的安全性分析 分为两大类：( 1 ) 包含约定信息的“携带验证代码”；( 2 ) 不含约定信息的“程序 分析”。两类方法基于的理论基础是形式语言与自动机、数理逻辑、形式语义、类 型理论、编译技术等。而这些方法可以分析的对象，是当前被广泛应用的分布式 系统和网络系统。 1 2 1 携带验证代码 携带验证代码( p r o o f - c a r r y i n gc o d e ，简称p c c ) i 】的基本思想类似于密码技 术。首先为代码定义组安全策略；然后代码提供者在编制程序时遵守这些安全 策略，并在程序源代码中加入验证代码以证明源代码遵守了这些安全策略：最后 由代码使用者确认这些代码的安全性。通过该机制使得计算机系统能够确定执行 一个不可信来源提供的程序是安全的。因此任何p c c 系统都至少包含四个核心部 分：( 1 ) 用来表达安全性原则的形式化的规格说明语言( 基于一阶逻辑) ；( 2 ) 代 码使用的形式化语义( 程序与规格说明相关联的逻辑形式) ：( 3 ) 用柬表达证明的 面向对象程序切片中类层次图的研究 语言( 断言+ 不变式) ；( 4 ) 使证明有效的推导系统( 证明编译器) 。 p c c 可以应用于固定的代码提供者和使用者之间，为基于网络的应用提供了 一种可靠的静态检验方法。但是，对于没有固定关系的软件提供者和使用者来讲， 该方法并不适用。 1 2 2 程序分析 程序分析是静态安全性检查的基础，任何方法都建立在程序分析的基础之上。 人们在该领域进行了长期、大量的研究工作，具体归纳为以下几种主流方法。 1 2 2 1 定理证明与模型检验 定理证明和模型检验的共同特征是以形式化方法为主的理论验证，程序分析 是它们的共同基础。此处的程序分析，除了语法分析之外，还涉及到语义的分析， 它包括控制流分析和数据流分析。 ( 1 ) 定理证( t h e o r e mp r o v i n g ) t 2 j 1 3 1 定理证明的理论基础是演绎推理和归纳推理。它将所验证的软件系统表示成 逻辑公式i ( 通常为一阶逻辑，如h o a r c 逻辑) ，需要验证的属性表示成逻辑公式s ， 推理是否i 推导出s 。定理证明主要适用于顺序的、具有较多非线性数据结构( 如 树或图) 、且规模较小的应用程序。定理证明的优点是可验证具有无限状态的应用 程序。而它的缺点是：自动化程度低，半可判定且无反例：需要使用者具有 较深厚的数学和逻辑知识基础，这一要求实质上否决了该方法在工程实际中的应 用。 ( 2 ) 模型检验( m o d e lc h e c k i n g ) 1 4 1 1 5 【6 】 7 1 模型检验的理论基础是时序逻辑和自动机理论。它将所要检验的属性表示成 时序逻辑公式，系统表示成有限自动机，在遍历有限自动机时，检查自动机所有 状态是否满足所给属性。模型检验可以应用于具有比较复杂控制结构的顺序的、 分布的、并发的、且规模较小的程序。模型检验的优点是自动化程度高，可判定 且可提供反例，对验证人员的水平要求较低。而它的缺点是只能检验有限状态的 应用程序，并且随着程序规模的扩大和程序复杂性的增加引起状态爆炸。虽然 g i l l e sb a m l e 【8 】等人已提出了一些方法，试图去解决状态爆炸问题，但是距离实际 应用还有相当的距离。 1 2 2 2 基于程序分析的安全性检查 可以通过词法分析、或者语法分析和简单的语义分析来检查软件系统中的许 多安全漏洞。 ( 1 ) 基于词法分析的安全性扫描【9 】f 1 0 1 第一章绪论 该类方法对源代码只进行词法分析。通过静态扫描源代码找出潜在安全漏洞， 一旦发现就给出警告信息。它的基本方法是将一个或多个源代码作为输入，并将 每个文件分解为记号流，比较记号流中的标识符和预先定义的安全性漏洞字典。 这类方法具有简单、高效的优点，但是精度较低，不适用于精确的静态分析。另 外可检查出的安全性漏洞种类有限。 ( 2 ) 基于语法和简单语义分析的安全性检查列 该种方法的工作原理非常类似于编译器系统，它以语法分析和语义规则为基 础，同时加入简单的控制流和数据流分析。因此这种方法具有较高的分析效率和 可扩展性，并且可以通过向程序中加入注释信息的方式发现软件中广泛存在的安 全性漏洞，如程序中出现机率最多的内存访问漏洞( 包括存储区的非法使用、空 指针的脱引用、缓冲区溢出等等) 。另外该种方法可适用于对大规模程序的分析。 1 2 2 3 基于信息流的安全性分析 信息流验证和检测方法“】t 5 i 【”1 【”1 基于类型推理，通过建立安全信息流验证的 格模型提出了一种验证机制来确保程序中信息流的安全性。该方法为信息指定一 个“安全类”的集合，并用“流关系”定义安全类之间允许的信息流，将程序中 每个存贮对象绑定到特定的安全类。从某对象x 到某对象y 的信息流是允许的， 当且仅当给定的流策略中x 的安全类可以流向y 的安全类。 该方法利用了安全类之间格结构的特定属性，因此可以较容易地嵌入到编译 器中。但它要求在验证时知道变量的安全类，因此不适合对某些软件如遗产代码 ( 1 e g a c yc o d e ) 等的分析。 1 2 3 软件安全性分析所采用的技术方案 根据上述分析可以看出，不同的安全性分析方法的区别仅在于程序分析方法 和规则的内容不同。如上述的安全性漏洞字典、注释信息、流策略等，均属于安 全性规则的范畴。我们确定的研究方案如图1 1 所示。其特点在于，它将与安全相 图1 1 简化的安全性分折模型 面向对象程序切片中类层次幽的研究 关的具体模式从程序分析中剥离出来，从而以不同的方法解决最适合解决的问题。 程序分析是安全性检查的基础，根据不同的安全漏洞和对应的安全模式，程 序分析可以在词法、语法、语义的任何级别上进行。基于过程的传统程序分析方 法已经很成熟，如词法分析、语法分析、控制流分析、数据流分析等等。针对本 课题的特点，对于程序分析的研究，侧重于将传统的程序分析方法向面向对象程 序设计语言的扩充，着重研究支持面向对象的程序切片技术。 1 3 程序切片综述 程序切片( p r o g r a ms l i c i n g ) 是一种程序分析和理解技术。它的概念是由m a r k w e i s e r 【1g 】于1 9 7 9 年在他的博士论文中首先提出的。一个程序p 的切片准则是一个 二元组 ，其中，i 是p 中的一条语句，v 是p 中变量的集合。程序p 关于切片 准则 的切片是影响p 中i 点变量v 的所有语句和谓词的集合，或受p 中i 点 变量v 影响的所有语句和谓词的集合。前者称为后向( b a c k w a r d ) 切片，而后者称 为前向( f o r w a r d ) 切片。程序切片在程序的理解、调试、测试、分解和集成、软 件维护、软件重用、逆向工程、程序并行化等领域具有广泛的应用。 1 3 1 传统的基于过程的切片 传统的基于过程的切片技术考虑一个过程或几个过程的切片。具有代表性的研 究工作有：w e i s e rl l s 提出的切片算法是基于数据流分析的，通过遍历控制流图 ( c o n t r o lf l o wg r a p h ，简称为c f g ) ，利用数据流方程和信息流方程来分析数据依 赖和控制依赖关系计算过程内切片( i n t r a - p r o c e d u r a ls l i c e ) 和跨过程切片 f i n t e r - p r o c e d u r a ls l i c e ) 。o t t e n s t e i n 等提出了基于程序依赖图 r o g r a md e p e n d e n c e c , r a p h , 简称为p d g ) 1 勺t ：) - j 片算法，将过程切片问题转换成依赖图的图形可达性问 题。h o r w i t z 等【2 0 ) ( s y s t e md e p e n d e n c eg r a p h ，简称为s d g ) 表示有过 程和过程调用的程序，并给出一个基于系统依赖图表示的两阶段程序跨过程切片 算法。这些方法都是基于传统的结构化程序，切片只局限在一个过程内或几个过 程间。 1 3 1 1 过程依赖图 过程依赖图9 1 将单个过程用有向图表示。其中，结点表示该过程中出现的语 句和谓词表达式：另外，每个过程依赖图包括一个入口结点，用来表示进入该过 程的入口。边表示过程元素间的控制依赖或数据依赖关系。非形式化的说，若语 句结点i 有两个出口，从一个出口必然导致语句结点j 被执行。而从另一个出口不 会导致结点i 被执行，则结点j 控制依赖于结点i 。该种依赖主要体现为条件语句 或循环语句的语句体内的语句控制依赖于条件或循环语句的谓词判断部分。若变 第一章绪论 量x 在语句结点i 处被定义，在语句结点j 处被引用，则结点j 数据依赖于结点i 。 这些依赖关系是根据程序的控制流图c f g 2 。1 来定义的。根据c f g 和必经结点 1 9 l 2 q 计算控制依赖；根据c f g 和数据流分析算法1 2 0 】 2 l l 来计算数据依赖。 1 3 1 _ 2 系统依赖图 系统依赖图( s d g ) t 2 。i 能够表示有过程和过程调用的程序。一个系统依赖图是过 程依赖图的集合，其中每个过程对应一个过程依赖图。 系统依赖图将调用位置的过程依赖图连接起来。调用位置用调用结点表示。 为了模拟由函数调用引起的参数传递，系统依赖图将过程入口结点与形参结点相 结合：对于过程的每个形参，存在一个形式输入结点；对于可能被该过程修改的 每个形参，存在一个形式输出结点。另外，系统依赖图将一个过程中每个调用位 置与调用结点及实参结点集合相结合：对于调用位置的每个实参，存在一个实际 输入结点；对于被调用过程可能修改的每个实参，存在一个实际输出结点。在过 程入口和调用位置处，全局变量被当作参数来处理。因此，这些全局变量也有实 际输入、实际输出、形式输入和形式输出结点。已知这些结点，可使用数据流分 析算法1 2 1 1 来计算过程中参数和语句间的数据依赖。 系统依赖图用一条调用边连接调用结点到被调用过程的p d g 的入口结点。此 外，系统依赖图用参数边表示参数传递：参数输入边连接实际输入结点到形式输 入结点：参数输出边连接形式输出结点到实际输出结点。 图1 2 给出了一个有过程调用的程序及其系统依赖图。图中，圆表示程序语句， 用语句号来标记。椭圆表示参数结点，实参用a ii n 或a io u t , t , 记，形参用f ii n 或 f i 记。粗线表示控制依赖，实线表示数据依赖，虚线表示过程调用和参数绑_out示 定。例如，语句c 4 控制依赖于语句s 3 的谓词表达式的值，因此在s d g 中存在一条 控制依赖边( s 3 ，c 4 ) 。s 1 处s l i m 的值传递给c 4 中的a d d 0 ，因此存在一条数据依赖边 ( s l ，c 4 - a 1i n ) 。对于调用点c 4 ，m a i n 函数中调用函数a d d 的实参s l i m 和i 分别与e 8 处被调用函数a d d 的形参x 和y 之间存在参数绑定，因此存在参数输入边( c 4 - a 1i n ， e 8 - f 1i n ) 和( c 4 一 a 2i n ，e 8 f 2i n ) ，以及参数输出边( e 8 一 f 1 o u t ，c 4 a 1 )。_out 1 3 1 3 基于过程的程序切片 在传统基于过程的程序中主要考虑过程内和过程间的各种数据依赖和控制依 赖，可用图形可达算法【2 2 1 或两阶段图形可达算法f 2 0 1 1 划来计算切片。切片基于过程 的程序，需要四个步骤来完成：( 1 ) 为单个过程构造过程依赖圈。( 2 ) 若程序由 单个过程组成，则跳到第( 3 ) 步；若程序由多个过程组成，则为其构造系统依赖 图。( 3 ) 基于图形可达性算法或两阶段图形可达性算法切片依赖图，获得切片后 的依赖图。( 4 ) 从切片后的依赖图中获得切片后的程序。下面给h o r w i t z 等人【2 0 1 面向对象程序切片中类层次图的研究 提出的系统依赖图上的两阶段图形可达性算法来计算跨过程切片。 e 0i n t m a i n ( ) s li n ts u m = 0 ： s 2i n l i = l ： s 3 i 印1 i ) c 4 s 1 1 1 1 1 1 1 = a d d ( s u m ，i ) ； c 5 i = a d d ( i ，1 ) ； ) s 6 p r l n 咀“d ”s u m ) ； s p r i m t i i “d ”，i ) ； e 8i n a d d ( i n ti ，i n ty ) s ，r e t u r nx + y ； 参数结点的对应关系 a ii n ：xi d - - 一s u i t i a 2i 1 3 ：yi r t = i a io u t ：s u i o - - xo u t a 3hxi r f i a 4i 1 1 ：yi r f l a 3o u t ；i - - - - xo u t f 1i i t ：x = xi 1 1 1 = 2 i n ：y - = y i 1 1 f 1o u t ：x0 1 j r i = - x - 控制依赖 一一卜调用，形式输入 形式输出 图12 一个带过程调用的简单c 程序及其系统依赖图 为了便于只沿着合法的调用返回序列的路径计算跨过程切片，s d g 使用总结 边表示越过一个过程调用时的依赖传递流，该依赖传递流可能由数据依赖、控制 依赖或由二者共同引起。若与实际输入结点相关的值影响与实际输出结点相关的 值，则存在一条总结边连接实际输入结点到实际输出结点。 该切片算法分两阶段完成。假设关于过程p 中的某个结点s 切片系统依赖图g 。 阶段l 后向遍历除参数输出边以外的所有边，并标记所有到达的结点。该阶段识别 了那些可以到达s 的，无论是在p 中或是在( 直接和传递) 调用p 的过程中的结点。 从阶段1 中标记的所有结点出发，阶段2 后向遍历除了调用边和参数输入边以外的 所有边并标记到达的结点。该阶段识别了通过被p ( 传递) 调用的过程到达s 的 结点或通过被( 传递) 调用了p 的过程所调用的过程到达s 的结点。跨过程切片的 结果为阶段l 和阶段2 中被标记的所有结点集合，以及结点集所引入的边的集合。 与简单的图形可达性算法【2 2 相比由于两阶段切片算法利用调用位置的综合 信息来说明被调用过程的调用上下文，因此该算法计算更精确的切片。 图1 3 给出了图1 _ 2 中的程序关于切片准n 的完整切片，以及与其对应的 切片后的程序。第一阶段遍历，算法标记了结点s 7 ，e o ，s 2 ，c 5 - a 3 _ o u t ，c 5 - a 4 一i n ， c 5 - a 3i n c 5 ，s 3 。从阶段l 得到的已标记的结点出发，第二阶段遍历标记了结 点e g - f ) o u t ，s 9 ，e 8 f 2i n ，e 8 f 1i n 。切片结果为这些已标记的结点和引入 的边的集合。 第一章绪论 e 0i n t m a i n o s 2i n t i = l ： s 3 i f ( i 1 1 ) c 5 i = a d d ( i ，1 ) ； s 7 p r i n t f ( “d ”j ) ； ) e 8i a ta d d ( i n t i ，i n t y ) s 9r e t u r nx + y ； 卜数据 控制依赖 一一卜调用，形式输 形式输出 图13 关于切片准则 0 ) c 1 2 f 1 ( ) ； ) ； c e l 3c l a s sb ：p u b l i ca f s 1 4i n ty ， p u b l i c ： e 1 5 b 0 c 1 6 a 0 ； s 1 7 y = o ； ) e 1 8v o i df 1 0 s 1 9 y = = y + x ； ) e 2 0v o i df 3 0 s 2 1 y = 3 ； c e 2 2c l a s sc p r i v a t e ： $ 2 3 a e p ； p u b l i c ： e 2 4 c ( i n ti ) $ 2 5 i f ( i 一0 ) $ 2 6 c p = n e w a ； e l s e $ 2 7 印= n e w b ； ) e 2 8 v o i d f 4 ( aa ) $ 2 9 a f l o ； ) ) ； e 3 0i n tm a i n 0 s 3 1bb ： $ 3 2 c + c = n e w c ( 1 ) ； $ 3 3 c - f 4 ( b ) ； $ 3 4r e t u r n0 ： 图2 2 一个c + + 程序 思二霪= ：篡 图2 3c + + 程序的类层依赖图 方法层依赖图的构造综合了m a r r yj e a nh a r r o l d 2 5 1 3 8 l 和李必信等”2 汹1 提 出的方法，如下所示： 为一个类中的每个成员方法创建一个方法头结点，并用一条类成员边连接该 面向对象程序切片中类层次图的研究 类的类头结点到其成员方法的方法头结点。 为每个成员方法引入参数结点：为方法中引用的每个变量创建形式输入结点， 为方法中修改的每个变量创建形式输出结点。需要特殊处理的是：( ”由于一个 类的成员变量可被该类的所有成员方法访问，因此可将其看作该类成员方法的全 局变量，为成员方法中引用或修改的成员变量创建形式输入结点和形式输出结点。 ( 2 ) 由于一个类的成员变量在被构造函数分配之前不能被引用，因此省略了构造 函数中成员变量的形式输入结点；类似的，由于一个类的成员变量在被析构后不 能被修改，因此省略了析构函数中成员变量的形式输出结点。 方法m 1 调用方法m 2 表示m 1 定义了m 2 的形式输入参数，并使用了m 2 的 形式输出参数。此处引入使用边和定义边来表示参数传递，如下所示： ( 1 ) 若一个类中的方法m 使用了某个变量i ，则从m 到i 存在一条使用边。 ( 2 ) 若一个类中的方法m 定义了某个变量i ，则从i 到m 存在一条定义边。 ( 3 ) 若类a 中的方法m 1 调用类b 的公有方法m 2 ，则从b 及b 的所有子 类中的方法m 2 的所有形式输入结点到m 1 均存在一条定义边，从m 1 到b 及b 的所有子类中的方法m 2 的形式输出结点均存在一条使用边。 调用关系在存在多态时更复杂，将在第三章中详细讨论。 图2 4 给出图2 2 中的c + + 程序的方法层依赖图。例如，方法珂1 是类a 的成 ：莲程章：o 舭姘点一愀 l 曼苎jo 于- 图24c + + 程序的方法层依赖图 第二章c 程序分层切片模型 员方法，因此存在一条类成员边( c e l ，e 1 0 ) 。皿) 引用并修改了变量x ，因此坦) 的 形式输入结点e 1 0 一 f 1 一i n 和形式输出结点e 1 0 一 f 1 一o u t 均为x ，并且存在一条使 用边( e 1 0 ，e 1 0 f l _ i n ) ，一条定义边( e 1 0 一 f lo u t ，e 1 0 ) 。由于疗( ) 调用了成员方法 n 0 ，因此存在一条定义边( e 6 f 1 一i n ，e 1 0 ) 和一条使用边( e i o ，e 6 一 f l _ o u t ) 。 2 2 _ 3 语句层依赖图 语句层依赖图是对一个类成员方法的语句进行分析而得到的。语句层依赖图 类似于传统的系统依赖图，结点之间存在数据依赖和控制依赖。可使用与构造系 统依赖图类似的方法来构造语句层依赖图。该层涉及到各种类型的数据依赖和控 制依赖关系，因此其依赖图最复杂。语句层依赖图比较庞大，此处不再给出图2 2 中c h 程序的语句层依赖图。 2 3 逐步求精切片算法 已知一个c + + 程序和切片准n ，用逐步求精切片算法计算程序切片。 2 3 1 类层切片算法 首先删除类层中与切片准则 无关的类，算法如下： ( 1 ) 根据切片准贝j j ，定位切片点v 所在的类c 。 ( 2 ) 从代表c 的类头结点出发，根据类层依赖图找出沿着创建边能够到达 的结点集合c r 。 ( 3 ) 根据类层依赖图，从c r 中的结点出发，找出沿着继承边能够到达的结 点集合i n 。 ( 4 ) c r 与i n 的并集为该c + + 程序关于切片准则 的类层切片。 考虑图2 2 中c + + 程序关于切片准n 的类层切片。c = d u m m y ，c r = ( c e l 3 ，c e 2 2 ，d u m m y ) ，i n = c e i ) ，因此得到的类层切片为 c e l ，c e l 3 ，c e 2 2 ， d u m m y ) a 2 3 2 方法层切片算法 在类层切片的基础上进一步删除无关的类及方法。由于基类的成员方法和成 员变量会被其派生类继承，因此，首先根据切片准则 定位切片点p 所在的方 法集合m 0 ，v 也可能代表多个变量的集合v 0 ，然后根据方法层依赖图找出与m 0 中结点相关的结点。算法如下： 根据类层切片，删除无关的类： 令m = m o ：v = v 0 ； 面向对象程序切片中类层次图的研究 w h i l e ( m 不空或v 不空1 i f ( m 不空1 f o r m 中的每个结点m l 从m l 出发，找出沿着使用边到达的未标记的结点集合v 1 ： v = v 1 ； ) 标记m 中所有结点； i f ( v 不空) f o r v 中的每个结点v 1 从v 1 出发，找出沿着定义边到达的未标记的结点集合m 1 ； m = m 1 ； 标记v 中所有结点： ) 算法结束后，所有被标记的变量和方法的集合为该c + + 程序关于切片准则 的方法层切片。 考虑图2 2 中c + + 程序关于切片准则 的方法层切片。m = m 0 = e 3 0 ， v = v o = b 。从m 中的结点出发，沿着使用边到达的未标记结点集合v l 为 e 2 8 - f l _ o u t ，e 2 8 - f 2 _ o u t ，e 2 4 一 f 5 _ o u t ，e l5 - f 2 _ o u t 。令v = v 1 ，并标记m 中 的结点。再从v 中的结点出发，沿着定义边到达的未标记结点集合m 1 为 e 2 8 ，e 2 4 ， e 1 5 1 。令m = m 1 ，并标记v 1 中的结点。重复上述步骤，直到m 和v 均为空， 算法结束。图2 4 中用粗线标注的所有结点及相关边的集合构成该程序关于切片准 则 的方法层切片。 2 3 3 语句层切片算法 可采用传统的过程内和跨过程切片的方法计算该层切片。 第二章c + + 程序分层切片模型 2 4 分层切片模型的优点 由于分层切片模型用分层的概念表示c + + 程序本质上的抽象层次，因此比其它 c + + 程序切片技术更清晰地描述了c + + 程序中类之间的各种依赖关系和消息传递机 制。对于粗粒度切片或细粒度切片，该层次化切片方法更高效。此外，该方法也 便于对不完整的程序系统进行切片，如适用于自下而上开发过程中缺少调用上下 文，自上而下开发过程中缺少被调用的过程，以及类库等情况。 面向对象程序切片中类层玖幽的研究 第三章类层次图的关键技术 类层次图为c + + 程序的数据依赖分析和控制依赖分析提供整体框架，它主要 考虑c + + 程序中类与类之间，类及其成员之间的关系。它包括类层依赖图和部分 方法层依赖图。类层次图在方法层体现在表示由于继承、多态等机制引起的类及 其成员之间的关系。 3 1 单个类的类层次图 一个类由成员方法和成员变量组成。类具有封装性，其成员可被声明为公有、 保护或私有的。公有成员在任何地方都可被访问：保护成员从类的外部不能被访 问，但可被其派生类访问；而私有成员只能在类内部被访问。 尽管一个类的实例一对象的成员变量的可见性是受限的，但在方法调用对象 的过程中，这些成员变量的值是保持的。虽然这些成员变量可能在其对象的成员 方法外部( 如对于调用该对象方法的一个过程) 不可见，但在面向对象程序分析 中必须能够表示：该过程在调用对象的方法时对该对象的成员变量存在依赖关系。 这在某种意义上方便了计算跨过程调用、跨类调用时的数据依赖。因此，在构造 类层次图时，对一个类成员的公有、保护和私有声明，不作处理。 构造单个类的类层次图步骤如下： ( 1 ) 为单个类创建一个类头结点。 ( 2 ) 为该类的每个成员方法创建一个方法头结点。 ( 3 ) 为每个成员方法引入相应的形式输入结点和形式输出结点( 参见 2 2 2 节) 。 ( 4 ) 用类成员边分别连接类头结点到其每个成员方法的方法头结点。 当一个类与其他类或系统结合时。能通过类头结点和类成员边很快访问到其 成员方法的信息。 3 2 类之间的基本依赖关系 类之间的基本依赖关系有继承关系和创建关系。 3 2 1 继承关系 继承是c + + 语言的一个重要机制，它允许一个派生类继承其基类的属性( 成 员方法和成员变量) ，并且可以在某些方面扩展、约束、重置或替代其父类的属性。 对于一个派生类，类层次图表示派生类和其基类之间，以及和派生类中定义的新 第三章类层次图的关键技术 方法之间的关系。继承机制方便了代码重用，因此构造一个派生类的类层次图应 该重用基类中的信息，只计算在派生类中定义的信息。 3 2 1 1 继承的访 可控制 继承可以公有继承，也可保护继承或私有继承。对于不同的继承方式其访 问控制不同。 公有继承时，基类中为公有、保护和私有成员在派生类中仍保持为公有、保 护和私有。保护继承时，基类中公有和保护成员在派生类中变成保护成员，而基 类中私有成员在派生类中变成私有成员。私有继承时，基类中公有、保护和私有 成员在派生类中均变成私有成员。 由于通过不同的继承方式得到的派生类都继承了其基类中的成员方法和成员 变量，从程序分析的角度来看它们相同。因此，在构造类层次图时，对继承方式 不作处理。 3 2 1 2 存在派生类的类层次图 当存在派生类时，为派生类中定义的每个方法构造一个表示，并重用从基类 中继承的所有方法的表示。基本步骤如下： ( 1 ) 使用单个类的类层次图构造方法为基类构造类层次图。 ( 2 ) 为派生类创建一个类头结点。 ( 3 ) 用一条继承边连接派生类的类头结点到其基类的类头结点。 ( 4 ) 用类成员边连接派生类的类头结点到派生类中定义的每个方法的方法 头结点。 ( 5 ) 对于从基类继承的方法，用一条成员边连接派生类类头结点到该方法 的方法头结点。 ( 6 ) 对于派生类中的方法，其形式输入结点表示：该方法可能引用的形参、 派生类或基类中的成员变量，和全局变量。类似的，其形式输出结点 表示：该方法可能修改的形参、派生类或基类中的成员变量，和全局 变量。 根据上述方法，需要重点解决如下问题： ( 1 ) 确定需要构造新表示的方法。 ( 2 ) 确定派生类中每个方法的参数结点。 ( 3 ) 考虑重置对派生类表示的影响。 3 2 1 3 重置 c + + 的虚函数机制允许在基类中声明一个方法，而在每个派生类中重置该方 面向对象程序切片中类层次圈的研究 法。该机制引起多态，即它允许在运行时间从一个方法调用的可能方法子集中确 定应该调用哪个方法。为了获得c + + 的多态行为，被调用的成员方法必须是虚函 数，并且对象必须通过指针或引用来访问。当直接操作一个对象( 而不是通过指 针或引用) 时，其确切类型是编译器己知的，不需要运行时间检查。因此，多态 引用具有静态和动态类型：静态类型是