（计算机软件与理论专业论文）逆向工程技术研究.pdf

【摘要】 逆向工程技术研究 在软件维护及再工程中，对遗留系统进行逆向工程是不可或缺的，而在逆向 工程巾一个很重要的工作就是对遗留系统进行程序理解。从源代码得到系统的设 计视图，不仅对程序理解，而且对进一步开发系统有重大的意义。现有重现设训 工具，一般采用的方法就是静态分析，而静态分析无法获得程序的动态运行状况， 在没有充分考虑动态分析的重要性的情况下，使得所取得的成果具有较大的局限 性。 针对面向对象软件系统。本文提出了一种从运行时期信息重现动态模型的方 法。首先提出系统动态信息轨迹的元模型和高层交互图的元模型。其中，系统动 态信息轨迹的元模型是动态分析的关键；高层交互图是用于对系统动态方面建模 的视图，它可以转换为各类的交互图。本文接着给出了上述两种元模型之间的转 换规! 1 1 0 ( 用o c l 描述) 。最后本文实现了代码植入工具c t t f ( 基于j a v a 语言) ， 以及从动态信息重现交互图的工具r c d t 。 【关键字】 逆向j ：程，程序理解，面向对象，动态分析，设计重现 【分类号】 丁p 3 】1 复旦人学硕，l 学位论文 逆向t 程技术”究 r e s e a r c ho nr e v e r s ee n g i n e e r i n g t e c h n i q u e s a b s t r a c t i nr e c e n ty e a r s ，l o t so fo r g a n i z a t i o n sf a c et h ep r o b l e ma b o u tt h eu n d e r s t a n d i n g a n de v o l u t i o no fl e g a c ys y s t e m s ；i th a sb e c o m em o r ea n dm o r ei m p o r t a n ti ns o f t w a r e r e s e a r c hf i e l d r e v e r s ee n g i n e e r i n gi st h ef i r s ts t e po fs o f t w a r em a i n t e n a n c e ，s o f t w a r e r e e n g i n e e r i n g ，s o f t w a r er e u s ea n ds o f t w a r er e s t r u c t u r e r e v e r s ee n g i n e e r i n gc a na i d s y s t e m a t i ce v o l u t i o nb yp r o v i d i n gab e t t e ru n d e r s t a n d i n go fs u b j e c ts y s t e m sd e s i g n a n do v e r a l la n do v e r a l ls t r u c t u r ea n di ti so n eo ft h ec r u e l a lt e c h n i q u e si nt h e m a i n t e n a n c em a de v o l u t i o no fl e g a c ys y s t e m s i ta c t u a l l yi sad e s i g nr e c o v e r ya n d k n o w l e d g ea b s t r a c t i n gp r o c e s s s e v e r a lt o o l sa l ea v a i l a b l ef o rr e v e r s ee n g i n e e r i n gt h e d y n a m i cb e h a v i o ra n ds t a t i cs t r u c t u r eo fe x i s t i n gs o f t w a r e b u tm a j o r i t yo ft h o s e r e s e a r c h e sf o c u s e do nt l l es t a t i cc h a r a c t e r so f s o f t w a r e w h i l ea r el a c ko f af l e x i b l ea n d p o w e r f u l s t a t i c d e s c r i p t i o na n d as e r i e so fm e t h o dc o n c e m i n gw i t hd y n a m i c a n a l y z i n g r e c o v e r i n gd v n m n i cm o d e l sf r o mr u nt i m ei n f o r m a t i o ni sa ni m p o r t a n ta s p e c to f s o f t w a r e s y s t e mm a i n t e n a n c ea n dr e v e r s ee n g i n e e r i n g ；t h i st h e s i sp r e s e n t s a l l a p p r o a c ht od e t e c ta n dd e c i p h e rd y n a m i ci n f o r m a t i o no ft a r g e tp r o g r a m sa n dr e c o v e r t h ec o r r e s p o n d i n gs c e n a r i od i a g r a m s 1 1 1 ea p p r o a c hi sc o m p o s e do ft w op a r t s ：c o d e i n s t m m e n t a t i o na n dm o d e lr e c o v e r y t h em e t h o d o l o g yo fc o d ei n s t r u m e n t a t i o ni s p r o v i d e dt oc o l l e c td y n a m i ci n f o r m a t i o n ag e n e r i cm e t h o d o l o g yo f m o d e lr e c o v e r yi s i n t r o d u c e dt oa n a l y z eat r a c ef i l e t h et r a n s f o r m a t i o no fat r a c ef i l ei n t oas c e n a r i o d i a g r a mi sf o r m a l l yd e f i n e du s i n go c le x p r e s s i o n s a n du m lc l a s sd i a g r a m s ( m e t a m o d e l st os t r u c t u r et h ei n f o r m a t i o ni nt r a c ef i l e sa n dd e s i g nd i a g r a m s ) t o o l s ， f o rb o t hc o d ei n s t n m l e n t a t i o n ( c t t f ) a n dm o d e lr e c o v e r y ( r c d t ) ，a r ed e v e l o p e d k e y w o r d r e v e r s ee n g i n e e r i n g ；p r o g r a mc o m p r e h e n s i o n ；o b j e c t - o r i e n t e d ；d y n a m i ca n a l y s i s d e s i g nr e c o v e r y 复旦人学硕士学位论文 逆向t + 程技术研究 第1 章引言 在软件维护及再工程中，需要对遗留系统逆向工程。而逆向工程一个很重要 的工作就是得到软件系统的设计视图。通过分析静态信息，可以得到如系统的对 象图等些模型，但这对整个逆向工程过程来说，是远远不够的，我们希望能得 到软件系统的高层动态视图，如协作图、序列图等，因为这些视图无法简单地从 静态信息得到，更需要动态信息的参与。如何从遗留系统中获取这些静态和动态 信息，进而如何对所获取的信息加以处理，最终得到高层视图，是本文重点研究 的问题。 1 1 逆向工程概述 1 1 1 背景与现状 在软件的整个生存周期中，应用环境常常会发生变化，导致已有软件系统不 能适应新的需求。为延长软件系统的生命周期，就必须对其进行维护和改善。扼 统计，软件开发支出的5 0 到7 5 用于软件的维护 2 2 。如果软件系统规模不是 很大，在已有系统不能完全满足需要时通常会开发一个新系统代替原有系统。但 随着软件丌发技术的发展，软件系统的规模和复杂度增大，重新开发新系统和维 护现有系统相比开销要大得多，越来越多的厂商开始选择维护、再工程和改进现 有系统。软件维护是对软件进行分析、理解、修改以适应新需求的过程。对已有 软件的分析和理解是软件维护、再工程和改进的基础。软件逆向工程的目标就是 通过分析已有软件提供对其设计和总体结构的较好理解，支持软件系统的维护和 演化。逆向工程作为软件工程的一个重要分支，是解决遗产系统发展最快的领域。 同时逆向工程作为一种辅助手段也可以应用于软件生存周期的其它阶段，例如丌 发阶段，包括需求、设计和实现。 1 1 2 相关概念 1 逆向工程和再工程 再工程和逆向工程经常在同样的上下文中被提及。c h i k o f s k y 和c r o s s 1 是 这样定义它们的： 逆向工程：是分析一个主体系统的过程，用来识别系统组件及其相互关系， 复旦大学硕士学位论文 逆向t 程技术研究 产生系统的另一种表示形式或更高层的系统抽象。 这就是说，逆向工程本质上关注的是如何理解一个系统以及它是如何上作 的。 再工程：是检查和“改变主题系统”，用一种新的形式和这种新形式的 实现来重建它。 另外，再工程关注的是重建一个系统，通常是修改一些已有的和将要发生的 问题，更重要的是对进一步开发和扩展做准备。 再工程的主要目的是为遗留系统转化为可演化系统提供一条现实可行的途 径。再工程是一个工程过程，它将逆向工程、重构和正向工程组合起来，将玑存 系统重新构造为新的形式。再工程的过程包括决策分析、系统理解和系统演化二三 个子过程。 图1 1 再t 程子过程 正向工程：是这样一个传统过程，即从高层抽象和逻辑的、与实现无关的殴 计，到系统的物理实现的转变过程。 如果说正向工程是从高层的需求和模型向具体实现转换，逆向工程就是从具 体实现向更抽象模型的回归，再工程就是从一种具体实现向另一种具体实现转 换。下图说明了这一点： 复旦火学顶士学位论文 逆向工程技术佃究 图1 2 再工程和逆向工程 要关注的重点是，再工程不仅仅是转换源码，而是从各个层次转换一个系统。 正因为这个原因，同时谈论逆向工程和再工程很有意义。在典型的遗留系统中， 可以发现不仅是源码，所有的文档和描述都不一致。由于人们不可能转换所不理 解的东西，逆向工程就成为再工程的一个前提条件。 2 逆向工程和面向对象技术 尽管本文中所讨论的许多技术可以运用到任何软件系统中，我们还是选择面 向对象的遗留系统作为重点。 现实世界中的事物抽象到问题空间就称为对象。在面向对象技术中，对象 被定义为“对一组信息和在其上的操作”【4 】，其中的信息就是数据，它反映的 是对象的属性状态，操作则是对对象的处理。面向对象系统就是由对象组成的复 杂系统，系统中所有对象的状态共同构成系统的状态，对象总是从一个初始状态 出发，在对象之间的相互作用过程中不断改变着自身的状态。一个对象请求另一 个对象执行某一处理或回答某些信息的要求称为“消息”，对象与对象之削的相 互作用就是通过消息来实现的。 使用面向对象技术能极大的提高软件的可维护性。而且它还有很多其他的优 点，例如提高软件开发率，提高软件的可靠性和安全性等等。面向对象技术获得 了极大欢迎，终于成为九十年代软件界最大的热点【8 】。随着发展，面向对象技 术形成了o o p ( 面向对象编程) 、o o d ( 面向对象设计) 、o o a ( 面向对象分析) ， 成为完整的软件开发方法学。面向对象技术的最大优点就是软件的可维护性好。 复旦大学硕士学位论史 3 逆向工程技术研究 大部分有关软件工程的讨论都是如何进行正向的软件项目开发，而少有提及 如何处理有价值的遗留系统。而在现实中，许多人在工作中面临的都是处理现有 的代码。一些遗留系统经多年的修改，功能已经比较稳定，用户也清楚如何避免 它出错，而放心使用。但这些系统往往用传统的过程式语言编写，即使早期采用 面向对象技术的人们发现，有些重要的遗留系统甚至采用1 a v a 实现的，但期望 获得的好处，却没有实现。 从这些经验中得出的错误结论是：“对象技术不好，我们需要其他东西。”我 们已经看到涌现出许多新的技术：模式、构件、u m l 、m d a 等等。然而我们要认 识到，一部分软件变成遗留系统并不是由于时间的原因，而是由于没有以再工程 方式开发和改写系统的速度造成的 2 8 。对象技术相当好，但我们得小心对待它 们。要理解这个观点，考虑一下，既然面向对象系统被认为具有灵活性、可维护 性和重用性等众多好处，为什么遗留系统的问题还是会出现在面向对象系统巾 呢? 1 ) 首先，任何人如果曾使用过一套由价值、已有的面向对象代码库，会发 现很难找到对象。更真实的感觉是，面向对象应用系统的结构一般是隐 蔽的。所看到的是一大堆类和类继承的层次关系。但这些都无法告诉你， 在运行时刻存在哪些对象，以及这些对象之间是如何合作完成所期望的 结果。理解一个面向对象系统是一个逆向工程的过程，通过本文描述的 技术，可以获得系统的高层视图，而再进一步，再工程后的代码，就是 一个结构更透明、更易理解的系统。 2 ) 其次，任何人如果想要扩展已有的面向对象系统，必须认识到“重用并 不是无代价的”。事实上，重用任何一段代码都是很困难的，除非在设计 时就考虑到重用性。 任何一个成功的软件系统都会受到遗留系统某些症状的影响。面向对象的遗 留系统，只要它的结构和设计无需再响应变化的需求，它就是一个成功的面向对 象系统。形成“连续不断地进行再工程的文化”是获得灵活的、可维护的面向对 象系统的首要条件。 1 1 3 用途与目标 逆向工程的概念借自工程学科。它在大到软件工程领域，小到软件维护领域 都很流行，特别是逆向工程能够帮助程序理解。 系统的组件是软件生存周期不同阶段的产品，例如，需求规格说明、体系结 构和详细设计、实现源代码。虽然逆向工程可以从这些产品的任何种丌始，但 是最常见的切入点还是程序源代码，这主要是因为经过多年的进化之后，系统得 复日欠学硕i：学位论文4 逆向工程技术研究 规格说明或设计信息可能已经不准确，或不能得到了。这通常是因为没有对以前 实施的维护任务进行详尽的记录。 逆向工程的目标是通过使维护人员能够理解软件系统做什么、如何做和软什 系统的体系结构表示，为实施更改提供便n u 6 1 。这种目标追求的是恢复已损失 的信息，促进在不同平台之间进行的迁移，改进或提供新的文档，提取可重用的 组件，降低维护工作量，处理复杂性，预测副作用，辅助向c a s e 环境的迁移以 及开发类似或竞争产品。下表归纳了这些目标： 目标意义 1 、恢复已损失的信息1 、维护 2 、促进在不同平台之间进行的迁移a 、增强理解，帮助标识错误 3 、改进或提供新的文档b 、帮助标识和提取受适应性和完 4 、提供替换视图善性更改影响的组件 c 、提供文档和系统的替换视图 5 、提取可重用的组件2 、重用：支持标识和提取可重用的组 件 6 、处理复杂性3 、提高系统质量 7 、预测副作用 8 、降低维护工作量 表1 1 逆向工程的目标和意义 1 2 本文的研究意义与创新 软件系统总是经常的变动和改进。为了在已有的软件系统上实施变动，工程 师必须要理解软件系统。软件开发的现实性就是开发团队经常在错误或过时文档 与没有原来丌发人员支持下实施维护任务。 在这种情形下，如果有合适的工具支持理解软件就很重要。有许多的方法和 工具可以提供帮助。如度量方法、程序可视化和动画技术、设计一致性检查等。 这些方法、工具帮助工程师从原来的软件本身逆向设计一个概念模型。 考虑到软件的模型，在这里我们详细区分了结构模型和行为模型。结构模型 描述了原始软件是怎么组织的以及在继承关系、包或模块问是怎么处理的。而行 为模型描述了这些原始软件如何在运行时相互协作以实现一定的功能。大多数程 序理解工具和逆向工程工具只利用到了静态信息来抽取软件的模型。然而，对面 向对象软件来说，一个类对象分支和多态令其很难确定运行时的真实情景，利用 复口大学硕一l 学位论文 静态信息抽取的模型只是限制在与程序行为有关的传递信息中。 为了更好的理解程序行为，工程师转向那些利用在程序执行时收集的动态信 息的工具。大多数这些工具显示了所有在运行期消息交换，给出了比较低层粒度 的信息。这些方法重现了详细的模型，并且依赖于可视化和导航技术来帮助丁程 师确定和变动任务有关的信息。 在我们研究中，我们探究了与这些工具不同使用动态信息方法的可行性。虽 然大多数方法保留了出现在执行追踪中时间元素，它们要么以表现为在一个时序 图中的垂直时间线，要么是通过动画技术模拟或实时呈现 3 0 。我们决定完全忽 略时间元素。我们探究了在没有时间标度下，动态信息如何帮助形成软件高层和 底层设计的概念。 我们的动机：虽然我们想获得低层运行时信息，然而逆向工程不是除错或调 试，我们也要帮助形成软件行为的概念。在对软件实施变动时，我们希望能压缩 ( c o m p a c t ) 高层视图，这些视图可以显示软件各部分之间的关系并指出什么地 方是需要关注的。我们需要低层视图来理解软件特定部分在运行时对象间的交 互，而不是软件的每一部分。我们想要知道在实现一定功能时都涉及了软件的哪 一部分，而它们的作用又是如何。这样我们就要一种方法，它可以抽取不沧是高 层还是低层的视图，但是这种低层视图又不是把所有低层的信息都呈现出来。我 们需要一种方法能帮助我们关注于所感兴趣的部分，而不是罗列所有细节。 1 2 1 本文的实现目标和解决的主要问题 本文提出一种解决方案，用以提取、解读所需要的动态信息，并重现目标系 统的交互图。 主要的创新点： 1 分析了交互情景图的特性，这种情景图可以描述目标系统的动态行为； 识别、标识出用以产生交互图的动态信息；对提取和解读动态信息进行 了探讨。 2 提供适用于j a v a 源代码的轨迹( t r a c e ) 产生语句的代码植入方法：在 经过处理的程序执行时，识别出有关操作、返回语句和控制流结构的运 行时期信息。这一方法用j a v a 程序定义，但不是只适用于j a v a ，可以 很容易应用到其它面向对象语言。 3 提供了一种广泛的建模方法，用来解读动态信息和逆向工程情景图。从 一系列的执行期间信息中，识别并解读了对象间的交互。同时提取了与 条件有关的信息，这些信息被实现为发送接受消息。这种方法的设计与 复旦人学硕：l ：学位论文 6 逆向丁程技术圳t 实现是与上述源代码植入方法无关的。并且，虽然它是针对从j a v a 程序 中逆向工程交互图的角度来设计的，但只要通过预先定义的格式收集到 并记录下动态信息，完全可以适用于那些利用面向对象程序语占实现的 软件系统中，从而重现情景图模型。 4 设计、实现了工具，证实了方法的可行性。虽然重现的交互图是使用简 洁的文本形式而不是一种图形可视形式，但它表达了完整的消息轨迹， 并提供了目标系统的行为的描绘。它可以转换为基于x m l 的元模型交换 文件( x m i ) 。x m i 可以在u m l 建模工具之间很容易地交换元模型，这样 就可以引入到任何u m lc g s e 工具中，以利用图形形式将交互图可视化。 1 3 本文组织结构 本文的第二章介绍了逆向工程的一些当前技术，指出它们的特点与局限性， 并且介绍了本文将要采用的一些方法和概念。 第三章介绍软件设计视图模型，并提出交互图的元模型。 第四章提出利用植入技术对系统进行动态分析的方法，从而获得系统的令面 信息，并给出了信息轨迹文件的元模型及植入工具的实现。 第血章通过分析交互图元模型和信息轨迹元模型，给出了它们之间的转换规 则，并利用这些规则，实现高层视图重现工具。 第六章对全文进行了总结。 复旦人学硕上学位论文 逆向丁程技术 究 第2 章技术综述 逆向工程中的研究内容、抽象层次和分析技术是我们关注的要点，将在这 章中详细介绍。 2 1 逆向工程的概念与内容 c h i k o f s k y 和c r o s s 给出逆向工程的定义为一个分析目标系统的过程 6 ，它 包括如下两个部分： 1 分辨它的组件并分析组件之间的依赖关系： 2 建立系统的另外的或在更高抽象级别上的表达形式。 上述逆向工程定义的两部分本质上是一个知识恢复、知识发现的过程。对于 软件这种无形的人工产物来说，逆向工程的主要目的首先是重现考察对象所体现 的原有设计知识，其次是能发现一些在设计中没有明显表示出的、存在于设计人 员头脑中的设计知识。 面向对象软件中所蕴涵的设计知识和传统程序是不同的，这些不同反映在对 系统组件的确定、组件之间的关系、系统结构的定义、子系统的划分等上面，也 反映在对于设计知识和内容的表达形式上。传统软件中基本组件一般为子系统、 过程、函数、数据结构，它们之间的关系是引用、调用、访问等关系。而面向对 象系统中考察的基本组件是类、对象、方法，它们的依赖关系有相互的依赖，和 同类型自己的依赖。面向对象软件在本质上不同于传统软件之处是关系的不同， 它有更加复杂的组件关系。如继承、泛化、访问、多态、动态绑定等。对于设计 知识的表达，面向对象一般用类图、协作图等表示，而传统程序用流程图柬表达。 设计知识是在不同的阶段形成的，对于o o p 设计过程，按照o m t 的定义分为 4 个阶段：系统分析、系统设计、对象设计、代码实现。系统分析阶段分辨出了 系统的域对象和根据域对象间的相互关系得到系统的整体框架，此阶段的设计知 识反映了应用域的逻辑构成，决定了系统的抽象结构框架和基本构件，是系统高 层的视图。系统设计阶段对分析得到的域对象和逻辑结构进行抽象和修改，使它 能更好地映射到计算机软件的一些概念上， 这里面包含的设计知识有各种对象之间关系的采用、取舍，对局部结构的选 择，对意外情况的处理方法等。对象设计阶段主要是对设计对象进行细化，如对 类继承层中的方法如何分配、划分，接口如何进行设计等。代码实现阶段融入了 具体面向对象语占本身的知识：表达了如何将设计映射到具体的语言上面。 复旦人学硕士学位论文 逆向工程技术_ 究 依据对面向对象系统中设计知识的分析 1 8 ，可以按照知识抽象层次由低剑 高来定义面向对象软件逆向工程的内容： 1 ) 面向对象语言本身的语义知识获得，一般用语法分析器来得到： 2 ) 面向对象设计知识的获得，它包括了较广的范围，如对象间关系的抽取， 子系统的分割，方法的大小划分和实现，意外情况的处理，设计模式、 域模型向计算机模型的映射等； 3 ) 应用域知识的重现，可由系统的框架抽象、域模型的抽取、文档分析方 法等得到。 2 2 逆向工程的层次 逆向工程的基本目的是帮助软件理解，而软件理解是软件中存在模式和人脑 中存在模式的匹配。对当前面向对象软件逆向工程方法的研究，按照它们抽取的 设计知识的抽象层次，即生成结果的可理解程度将面向对象软件的逆向工程研究 分为如下4 个层次 1 9 ： 1 ) 对象间的关系抽取。对象间的实际关系指的是已有定义的，如继承、聚 集、访问等基本的静念对象关系和一些对象之间的协作等动态关系，它 们是在设计中明确定义的简单关系内容。 2 ) 设计模式的识别。每一个设计模式都集中于一个特定的面向对象设计问 题或设计要点，表达的是面向对象系统的局部结构。 3 ) 面向对象程序的度量。面向对象程序的度量表达了面向对象程序在整体 上或局部从统计的观点来看的一些性质，可以看作是将系统作为整体来 考察时的内部关系，它能揭示在设计时未知、也没有表达出来的内容。 4 ) 系统结构和域模型的抽象。域结构表达的是应用域中的固有关系，它是 通过系统分析得到的域的抽象结果。虽然在代码中间蕴涵了此部分内容， 但是由于程序语义和应用域内语义的区别，对此部分内容的逆向 ：程要 采用更多的输入源，软件文档、域对象和软件对象的映射关系等。 2 2 1 对象间的关系抽取 对象问的实际关系抽取是最基本的面向对象软件逆向活动，它是高层抽象的 基础。由于在面向对象程序中考察的对象可有文件、类或对象、方法、成员、语 句。这些考察的对象相同类别之问有复杂的关系，不同类别之间也存在着复杂的 关系，对这些关系的辨别、提取一直是研究的重点。面向对象程序中的不同实体 之问的关系总结如下图所示。其中“类型”代表面向对象程序中的类、接口等类 复旦人学硕上学位论文 9 逆m 工程技术研究 型。 由图中可以看出，在这些实体的关系中，语句是构成其他实体的基本单位， 语句之间的关系在传统的语言中，一般用流程图、数据流图等来表示。对语句之 | 、日j 的关系的抽取就是如何得到这些和程序在同等抽象层次上的图形表达。对语句 之间的关系抽取，在对传统的程序逆向工程研究中已经做了很全面的工作；在义 献 9 中对其技术、丌发出的工具进行了很好的分类和评价。原来用于传统语吉。 的许多技术可以用于面向对象中，如可以用流程图来表达类或剐象中的一个方法 的实现。但是由于面向对象程序中处理的基本数据对象是类，而不是简单的数据 类型，因此更增加了处理的复杂性。 在下图的各个实体的关系中，类是承载关系的一个核心的实体。 引肭 图2 1 实体间的关系 类内部的方法或成员一般没有复杂的关系，而不同类或对象的方法通过类这 个桥梁才有了相互的联系。因此对面向对象程序的关系抽取和理解更多的是在类 的语言层次上进行的。 为了解决面向对象中的多态问题，在确定对象之间关系的具体类型的过程 中，可以用在编译优化中的技术如c h a ( c l a s sh i e r a r c h ya n a l y s i s ) 方法，它 通过对整个程序的实际类型结构进行分析，得到实际执行方法的类型。它首先记 录一个对象的静态声明类型。它首先记录一个对象的静态声明类型t d ，然后结 合程序的类继承图，决定一个虚拟调用可能的目标类型集合，此集合一般为静态 声明类t d 的子类集。r t a ( r a p i dt y p ea n a l y s i s ) 是对c h a 的改进，它利用了 复旦大学硕十学位论文 1 0 逆向工程技术f 究 额外的数据清除c h a 产生的可疑的调用关系，主要是用了对象中具体实例化的类 型来检查具体激活方法执行的实际类型。r t a 是流程和上下文无关的，并可以得 到更精确的分析结果。据统计，c h a 可以解决5 0 左右的多态，而r t a 可以解决 8 0 左右的多态调用。此外，更精确的面向对象程序分析方法有别名分析方法， 以及其他类型引用分析方法等。这些方法大都要记录每一个语句的内容，是流程 及上下文有关的，并有较高的时间和空间复杂度 2 3 。 2 2 2 设计模式的识别 一个设计模式集中于一个特定的面向对象设计问题或设计要点，表达的是面 向对象系统的局部结构。一个设计模式要命名、抽象和确定一个通用设计结构的 主要方面，这些设计结构能被用来构造可复用的面向对象设计。设计模式确定了 所包含的类和实例，它们的角色、协作方式以及职责分配。对设计模式的拙驳和 辨别可以使得维护人员对系统的结构和功能有一个更高层次的理解 2 。 j o c h e ns e e m a n n 通过逐层抽象的方法得至1 3 a v a 代码的某些常见设计模式。它 首先抽取类、接口和方法，三者的8 种关系，形成关系图，并通过将方法之问的调 用、创建等关系简化为类之间的关系而得到简化的关系图。然后对类之| 日j 的关系 进行合并、推理，取得类之间的访问( a s s o c i a t i o n ) 、聚集( a g g r e g a t i o n ) 和 指派( d e l e g a t i o n ) 三种类关系。再根据提出的几种常见面向对象设计模式的结 构标准，在上述结果关系图中进行匹配来发现设计模式。对面向对象的多念问题 文中进行了处理，但没有提及在关系图中搜索的方法。 a n t o n i o l 用源代码和设计信息为输入，第l 步转换为a o l ( a b s t r a c to b j e c t l a n g u a g e ) ，在a o l 的基础上进行处理，因此可以独立于具体语言。第2 步是x c a o i 。 进行解析得到a s t ( a b s t r a c ts y n t a xt r e e ) 。第3 步是对a s t 进行抽取得到系统 关系数据、软件度量数据等。最后是具体的搜索、模式匹配过程。在搜索中依次 利用软件度量限制条件、设计模式的最短路径限制、设计模式的结构限制和设计 模式的指派关系限制来减少搜索空间，防止在模式匹配中出现组合爆炸。 文中 还建立了用元组形式表示的设计模式的形式化特征库。此方法能找到程序中8 0 的设计模式。 k r a m e r 和p r e c h e l t 开发了自动发现设计模式的p a t 系统 2 0 。它用o o c a s e t 具抽取c 程序的头文件信息并转化为o m t 表达的格式，然后自动转化为p r o l o g 表达 方法，0 0 设计模式也是由系统自动将o m t 表示格式转化为一个p r o o g 规则。在抽 取的信息中设计模式的具体搜索采用t p r o l o g 查询的方法，是n p r o l o g 引擎来完 成的。p a t 系统是用来发现程序中关于系统结构方面的设计模式，能找到程序t ； 1 4 9 6 1 5 的设计模式，其精确度依赖于抽取工具得到信息的精确度。 复旦大学硕十学位论文 1i r u d o l fk k e l l e r 等指出了在大型软件系统中发现设计模式的重要性，认为 许多设计模式由于应用域的不同而有不同的程序表现形式，因此更需要人工的参 与。他们实现了一个逆向工程环境s p o o l ，可以由人工方法或自动方法在程序抽 取信息中发现模式。s p o o l 中在程序源代码抽取得到更详细程序信息，并有可视 化的浏览工具来辅助信息查询。文中还以t e m p l a t em e t h o d ，f a c t o r ym e t h o d ， b r i d g e - i 个设计模式分别在3 个实验系统中的发现过程为例说明了s p o o l 的具体 应用。 2 2 3 程序的度量 软件度量是用软件的统计数字表示软件的某些特性，如软件质量、丌发过程 的优劣等。度量在软件逆向工程中也有着重要的地位：一个是用它来分离高复杂 度和低复杂度的目标系统，使维护工作分配合理；二用来分辨复杂或紧密耦合的 部分，指明那些部分不易于修改和重用，或指出需要重结构、重设计的部分。 s e r g ed e m e y e r 等丌发的工具c o d e c r a w l e r 结合了软件度量特性和程序可视化 来表示程序的内容 1 1 。文中采用的面向对象软件度量分为3 类，分别是1 8 个对 类特性的度量、7 个对类方法特性的度量和2 个对类的属性的度量。它们用各种剀 如树图、关联图、直方图、分类图、面对图、圆饼图等结合起来可视化地表示各 种不同的度量内容，由此揭示面向对象软件系统的整体内部特征。 t a r j as y s t a 在开发的s h i m b a 系统中实现了由c h i d a m b e r 和k e m e r e r 提出的部 分软件度量 1 2 。其中继承度量有继承树深度( d i t ) 、子类数目( n o c ) 两个； 复杂性度量有圈复杂度( c c ) 和类的加权方法数( w m c ) ；通信度量有一个类的 响应度( r f c ) 、对象之间的耦合度( c b o ) 、方法的内聚缺乏度( l c o m ) 。并t e j 上述度量为指导来对对象进行进一步的聚合、查询，得到高层抽象的视图。文中 还用逆向工程过程得到的度量数据发现一些反常信息，为程序维护提供了高层的 指导。 2 2 4 系统结构恢复和高层抽象技术 1 ) 系统结构恢复 对于面向对象程序的理解一般是采用由上到下的理解模型，而面向对象程序 的系统结构是它最上层的信息，它也是应用域知识的体现。因此，如何恢复系统 结构是面向对象软件逆向工程的重点。按照p o s t m a n 等人的定义系统结构逆向工 程可以分3 个阶段：抽取系统结构信息阶段取得初始的信息，高层抽象阶段得到 一个可以理解的结构，系统结构表达阶段定义如何描述得到的结构 7 。 复日大学硕士学位论文 1 2 逆向丁程技术研究 s e i 的结构恢复工具d e l i 分5 个阶段：视图抽取阶段得到系统的基础数据，数 据库构造阶段将上阶段的数据表示为三元组并转换为关系数据放到数据库，融合 视图阶段融合由不同来源，如代码、文档等，以及不同方式得到的系统的数据； 结构重建阶段包括可视化显示和交互、模式定义和识别两个步骤，这是一个解释 性的、交互的、重复的过程，其中模式定义采用s q l 语句，由查询结合人的交互 来得到识别的目的；最后是结构分析阶段。 a r t 工具预先定义了常见的几个系统结构模型的应用域表示方法和在具体语 言中的表示方法，然后利用r e f i n e 工具的解析、存储查询机制来恢复基于类型的 系统结构，如客户服务器、管道和过滤器等系统结构。对应于每种系统结构， 都有相应的由基于a s t 的查询语言表示的识别器集合。系统可以由上到下地利用 识别器在源码中寻找，以验证预先的结构假设。 2 ) 高层抽象技术 由于软件理解是程序结构和环境与理解人员的关于世界的概念知识的关联， 而理解人员的关于世界的概念知识一般是关于应用域的知识、常用算法等抽象程 度高的知识，这些知识一般都是用非f 则的方法表示的，如用文字叙述的软件文 档。如何将软件信息抽象为高层的概念，减小程序表达的概念和人的认知概念的 距离，是逆向工程中更高层的任务 3 2 。 一个直接的方法是a n t o n i o l 的将软件文档片断和对应其实现的程序源代码 关联。他们的方法其出发点是在程序设计中，程序设计人员会使用有意义的标谚 符名称，如变量名、类型名、方法名等来表达他们对应用域的理解。对在文档中 抽取到的词通过预先建立的一个随机语言估计模型取得它的语言模型，然后利用 b a y e s i a n 分类方法将代码中抽取到的标识符名字在语言模型中进行打分，以得到 最优的关联匹配。 g r e g o rs n e l t i n g 等人利用概念分析的技术来发现类的成员继承和分配问题 并改造它，优化了系统设计。概念分析开始于二元关系，它通过对概念的内涵和 外延的构造来得到一个概念。g r e g o rs n e l t i n g 通过对有继承关系的类层和用到 此类层的应用集合进行分析，构造出了表示此类层在特定上下文中应用的内容的 格子( 1 a t t i c e ) 。在构造格子中，格子对象是类的变量，格子的属性为类的成 员。然后通过概念分析算法分析类层中方法的分布，并得到重新优化的类层次结 构。 a l e x a n d e re g y e d 认为抽象就是隐藏不重要的信息而合成的新的、高层的元 素又能表达低层的关系，如何兼顾两者是抽象技术要解决的核，t l , 问题。他将抽象 过程分为分类器抽象过程和关系抽象过程。对于关系抽象有两个优点：一是可以 应用于关系不能维持层状分类的情况；二是多样的对象关系类型允许语义更十富 复旦大学硕士学位论文 逆向1 二程技术目f 宄 的抽象。文中提出了一些类关系的抽象规则，规则可以用以下公式表示： c 1 一 r 1 r 2 c l 一 r 3 一c 3 式中c 表示类，r 表示关系，关系r 是有方向性的。文中对继承、访问、依赖 和聚集：类对象间的关系共定义了4 7 条约简规则，并对每条规则指定了相应的u _ 信度。有了上述规则后就可以在抽取到的类关系图基础上，用序列推理来得到高 层的更抽象的关系图。 d e r er a y s i d e 等人提出了一个新的对象聚集方法，最后得到系统的一个树状 的聚集结果。文中对类之间的关系类型定义了不同的权值，权值大小表示关系的 紧密程度，用户可以用指定权值大小的方法来得到好的聚集结果。其聚集算法主 要步骤如下：1 、选取活动点，按照聚集中的类结点数目进行规范化后，选取使 聚集的外部依赖最小的结点；2 、选取聚合点，按照聚集后的对象集合对外部的 依赖最小的原则选取；3 、合并上两类结点；4 、重复上面3 个步骤，直到结果为 一个结点。此算法可描述为分层的、单调的、独占的、固有的、聚结的、序列化 的聚集算法。 2 3 逆向工程分析技术 逆向工程分析技术主要分为两类：静态分析和动态分析 2 1 。传统的静态分 析技术对逆向工程研究一直有极高的价值，能有效地分析过程式程序的控制流及 数据流。但随着遗产系统类型的演化，动念分析技术的作用越来越重要。例如， 基于面向对象技术、使用动态绑定和多态的程序，必须进行动态分析才能获取相 关信息；面向对象程序中常用到大型共享库和大量间接调用，导致静态分析时可 能执行到的路径数量和整体分析的规模剧增，从分析的效率和准确性考虑必须进 行动态分析。 2 3 1 静态分析 静态分析技术直是编译技术的核心，编译器优化是标准的静态分析。对目 标系统的静态分析不必运行系统，所以分析可以进行的比较早，甚至在系统的丌 发阶段就可以开始。静态分析技术发展至今，主要有以下几类 2 3 ： 1 ) 词法分析和语法分析。 该方法直接对程序源码进行分析，已经发展得比较成熟。通过词法分析可以 得到程序信息的多种有用表示，其中最常用的是交叉引用列表。另外，借助词法 分析还可以建立软件复杂度测量的标准。通过语法分析可以得到两类表示：分析 树( p a r s et r e e ) 和抽象语法树a s t ( a b s t r a c ts y n t a xt r e e ) 。其中，分析树 复旦大学硕上学位论文 14 逆向工程披术赴玎究 只是指导分析过程，是比较原始的结果。分析树显示了程序语句的分解过程，包 含和程序的实际含义无关的信息。去除分析树的无关信息后得到a s t ，a s t 只包 含和程序实际内容相关的细节，是更复杂的程序分析工具的基础。 2 ) 图形化方法。 图形化方法包括控制流分析、数据流分析以及程序依赖图 2 9 。 a ) 控制流分析对执行语句的若干可执行路径进行分析，确定程序的控 制结构，建立控制流图。控制流分析有两种形式：过程内 ( in t r a p r o c e d u r a l ) 分析和过程间( in t e r p r o c e d u r a l ) 分析。过 程内分析通过构建控制流图c f g ( c o n t r o lf l o wg r a p h ) 进行，可确 定子程序内语句的执行顺序。构建c f g 必须先确定子程序的基本块 ( b a s i cb l o c k ) 。一个基本块对应c f g 中一个节点，是一些连续语 句的最大集合。在该语句集合中，控制只能从第一条语句开始，也 只能从最后一条语句经条件分支或非条件分支转出。就是说基本块 的第一句执行，基本块中所有语句都会执行。基本块可以直接通过 遍历a s t 确定，再用控制流弧线连接基本块来创建c f g 。过程问控制 流分析是确定系统子程序之阃可能的控制流路径的过程，用调用图 ( c a l lg r a p h ) 表示。调用图给出了一个系统中对子程序的可能调 用。调用图是树、有向无环图还是一般的图由系统结构决定。调用 图中的结点和子程序对应，节点之间的有向弧标识出调用关系。 b ) 数据流分析是在不执行程序的情况下，收集程序数据的运行时信息， 分析程序中数据对象之间的关系。数据流分析关注程序中的数据使 用、定义及依赖关系，对确定系统的逻辑构件及其交互关系很重要。 数据流比控制流分析要复杂得多，例如，控制流分析只需分析循环 的可能性，数据流则必须确定循环体内变量的变化情况。通过数据 流分析还可以获取很多抽象层次要求较低的信息，如过程依赖、变 量之间的依赖及指定代码段修改的数据等相关信息。 c ) 程序依赖图是数据流分析的进一步改进，比数据流分析更复杂。在 程序依赖图中，节点表示语句和谓词表达式( 或运算符和操作数) ， 边表示该节点的操作所依赖的数据值和控制条件。程序依赖图将摔 制流和数据流放在一起处理，清楚地描述了程序中每个操作的数掘 依赖和控制依赖。如果同时需要控制流图和数据流图的相关信息， 使用程序依赖图就很方便。 3 ) 静态切片。 切片技术是将程序简化为和某个特殊计算相关的语句的技术，来源于数掘流 复旦大学预士学位论文 分析方法 2 7 。切片技术自动将程序分解为较小的称为切片的代码段，使关注点 确定在一个较小范围而不必关注整个程序。一个程序切片是“影响”指定值的程 序语句和判定表达式组成的集合，包含捕获程序行为子集的原来程序的一部分。 为了计算切片必须知道程序中语句之间的依赖关系，这种依赖关系可以通过分析 数据流和控制流自动从源程序中得到。切片技术可大致分为两类：静态切片和动 态切片。静态切片被定义为“可能影响”一个值的所有语句，其相关计算只利用 静态获得的信息，并且是从切片的标准开始，以向后遍历的方式收集语句和控制 谓词。在静态切片的实际计算中可以根据控制流和数据流依赖对间接相关的语句 进行分析，也可以借助于