（计算机科学与技术专业论文）面向理解的oore关键技术研究.pdf

浙江人学博士论文 捅要 面向对象技术将数据结构和在数据结构上的操作结合起来，使得软件系统更 容易维护、扩充，对系统的分析过程也更符合人类的思维模式。但o o 技术不是 万能药，o o 巾的继承、多态、动态绑定的使用导致o o 软件内组件关系复杂，而 对面向对象机制的不加选择的使用和分析设计方法中的缺陷也快速导致了新一 代的不灵活的遗产系统。o o 软件系统的维护、重工程、重用、重结构和演化已 经成为关键的事务，而支持这些活动，辅助o o 软件理解的面向对象软件逆向工 程( o o r e ) 的技术研究和 _ 具研制也越来越重要。 软件逆向工程本身是一个设计知识发现、知识抽象的过程，而面向对象软件 和传统软件相比有着自己的语言特点和不同的设计知识内容。文中通过对面向对 象程序中知识类别和逆向工程过程的分析，总结出了o o r e 的基本知识内容，并 以此为分类线索综述了日前此领域中具有代表性的技术、工具和研究方向。 许多逆向工程研究在采用技术上没有能坚持以辅助理解为核心，本文以辅助 理解为最高目标，研究了o o r e 的几个关键技术，并提出了面向理解的逆向工程 框架a u t o o r e ，它针对o o 软件的特点，构建时更多强调的是高层的抽象，以 及对软件理解的支持。 代码抽取是o o r e 的起点，从起点开始支持理解是逆向工程的重要目标， a u t o o r e 在j a v a 抽取中，抽取模型采用文中提出的j a v a 词法和语义两个模型， 利用一个基于j a v a 扩展类层次图( e c h g ) 的多态调用点分析算法，得到更精确 的静态对象关系。抽取过程有三个阶段：构造系统的e c h g ，扫描程序的源代码 和多态点分析得到系统的词法层次模型，通过基于规则的推理转换词法模型为语 义模型。 抽象是a u t o o r e 的核心，它首次采用对象系统的语义关系抽取数据为输入， 利用基于m s t 表示的、聚集目标结合了程序认知心理学理论的软件聚集方法，得 到一个具有丰富语义的、组织为树状的、分层的聚集集合。文中还提出了对o o 类之间的语义关系进行量化、压缩的方法，并对o o 类聚集中关系的类型语义的 相对权重进行了试验研究。 o o 系统中类是关键的软件对象，辅助高效理解类是o o r e 中的一个重要环 节。文中依据学习构造理论提出了个类的理解模型，并实现了一个辅助理解类 的可视化工具m f v - c l a s s 集成虱 a u t o o r e 中。m f v c l a s s 结合了o o 的度量数据 在多种视图中，从不同的侧面揭示类所涵盖的内容，提供给软件人员一个多源的 理解环境。 关键词：面向对象逆向工程，程序理解，程序分析，a u t o o r e ，软件聚集，刈 象模型，软件可视化，o o 软件度量 浙江大学博上论文 a b s t r a c t a l t h o u g hm o s ts y s t e m s s t a r to f fi nac l e a na n dw e l l d e s i g n e ds t a t e ，w i t ht i m et h e y t e n dt og r a d u a l l yd e c a yi nq u a l i t y t h em a i n t e n a n c e ，r e e n g i n e e r i n g ，a n de v o l u t i o no f o b j e c t o r i e n t e d s o f t w a r e s y s t e m sh a v eb e c o m ev i t a l m a t t e r si n t o d a y ss o f t w a r e i n d u s t r y t h er e v e r s ee n g i n e e r i n ga n ds o f t w a r ec o m p r e h e n s i o na r ct h eb a s eo f t h e s e a c t i v i t i e s t h ed i f f e r e n c e sb e t w e e n o b j e c t o r i e n t e dl a n g u a g e a n d p r o c e d u r a ll a n g u a g e d e m a n do t h e rr e v e r s ee n g i n e e r i n gt e c h n i q u e s i nt h i st h e s i s ，t h ed e s i g nk n o w l e d g ei n o h 3 e c t - o r i e n t e dd e s i g na n dt h es o f t w a r er e v e r s ee n g i n e e r i n gp r o c e s sa r et h o r o u g h l y a n a l y z e d a c c o r d i n g t ot h e a n a l y s i sr e s u l t s ，t h i s t h e s i s g i v e s t h ec o n t e n t so f o b j e c t o r i e n t e ds o f t w a r e r e v e r s ee n g i n e e r i n g ( o o r e ) ，a n d p r o p o s e sac l a s s i f ym e t h o d a b o u ti t s t e c h n i q u e s t h i sp a p e ra l s od e s c r i b e sa u t o o r e ，a no o r et o o lf o r s o f t w a r ec o m p r e h e n s i o n i ti n v o l v e s s p e c i a lt e c h n o l o g yi nh o wt og e tp r e c i s eo o c o m p o n e n t r e l a t i o n sa n dh o wt oh i 曲- l e v e la b s t r a c t i o no f0 0 s y s t e m r e v e r s e e n g i n e e r i n g m e t h o d sa i ma t e x t r a c t i n g a c c u r a t ea n dc o n s i s t e n t i n f o m l a t i o nf r o mc o d et oa l l e v i a t et h ed i f f i c u l t i e so fp r o g r a mu n d e r s t a n d i n g ，b u t m a n ye x t r a c t i o nm e t h o d sf o c u so nt h et o o l sa u t o m a t i o n ，n o to nt h es e m a n t i co ft h e e x t r a c t i n gr e s u l t i na u t o o r e ，a n o v e la p p r o a c ht oe x t r a c tj a v as e m a n t i cr e l a t i o n a l m o d e li s p r e s e n t e d t o g e tp r e c i s eo b j e c t r e l a t i o n a l r e s u l t ，t h e j a v ac o d e p o l y m o r p h i s mi n v o k el o c a t i o n i sf o r m a ld e f i n e da n dap r o g r a n a a n a l y s i sm e t h o d b a s e do ne x t e n d e dc l a s sh i e r a r c h yg r a p h ( e c h g ) i sp r o p o s e d t h ee x t r a c tp r o c e s s h a v et h r e es t e p s ：c o n s t r u c t i n ge c h go fj a v as y s t e mf r o m j a v ap r o f i l e ，e x t r a c t i n g s y s t e m s i e x i c a lr e l a t i o n a lm o d e l b ys c a n n i n g s o u r c ec o d ea n d a n a l y z i n g t h e p o l y m o r p h i s mc a l l i n gl o c a t i o n ，c o n s t r u c t i n gt h es e m a n t i cm o d e lb yr u l e b a s e dm o d e l m a p p i n g o f l e x i c a lm o d e l p r o g r a mc o m p r e h e n s i o ni st h ek e yi s s u ei no o r e a ne f f e c t i v ea p p r o a c ht o i m p r o v et h ep r o c e s so fp r o g r a mc o m p r e h e n s i o ni st od r a wah i g h l e v e l ，a b s t r a c tv i e w o fs o f t w a r e s y s t e mb y a c l u s t e r i n g m e t h o d d i f f e r e n tf r o mo t h e r r e s e a r c h e s ， a u t o o r eu s e st h e p r o p o s e dj a v as e m a n t i cm o d e la si n p u td a t a ，a n dg i v e sa t r e e l i k e d ，h i e r a r c h i c a ls t r u c t u r e da n ds e m a n t i cc l u s t e rs e t t h ec l u s t e r i n gm e t h o di s b a s e do nam i n i m u m s p a n n i n g t r e et h a tr e p r e s e n t st h es o f t w a r es y s t e m t h e c l u s t e r i n g o b j e c t i v ef u n c t i o ni sd e s i g n e da c c o r d i n gt ot h es o f t w a r em o d u l a r i z a t i o nm e t r i ca n d 1 1 1 浙江大学博士论文 c o g n i t i o np s y c h o l o g yt h e o r y t h i st h e s i sa l s op r o p o s e sas i m i l a r i t ym e t r i co f c l a s s e s a n dt h ec o m b i n em e t h o do ft h es e m a n t i cr e l a t i o n s h i p ，a n de x p l o r e st h eo p t i m i z a t i o n o fs e m a n t i cm e a s u r e m e n t c l a s s e sa r ek e ys o f t w a r ec o m p o n e n t si na no b j e c t o r i e n t e ds o f t w a r es y s t e m i n m a n yi n d u s t r i a l0 0 s o f t w a r es y s t e m s ，t h e r ea r es o m ec l a s s e st h a th a v ec o m p l i c a t e d s t r u c t u r ea n d r e l a t i o n s h i p s i ti sac h a l l e n g ef o rs o f t w a r ee n g i n e e r st ou n d e r s t a n dt h e s e c l a s s e se f f i c i e n t l y t h i st h e s i sp r o p o s e sac l a s sc o m p r e h e n s i o nm o d e la c c o r d i n gt o c o n s t m c t i v i s t l e a r n i n gt h e o r y ，a n di m p l e m e n t s as o f t w a r ev i s u a l i z a t i o nt o o l ( m f v c l a s s ) t oh e l pi nt h ec o m p r e h e n s i o no fac l a s s t h et o o lp r o v i d e sm u l t i p l e v i e w so fc l a s st ou n c o v e rm a n i f o l df a c e t so fc l a s sc o n t e n t s i te n a b l e sv i s u a l i z i n g t h r e eo b j e c t 。o r i e n t e dm e t r i c so f c l a s s e st oh e l pu s e r sf o c u so n u n d e r s t a n d i n gp r o c e s s k e yw o r d s ：0 0 r e ，p r o g r a mc o m p r e h e n s i o n ，p r o g r a ma n a l y s i s ，a u t o o r e s o f t w a r ec l u s t e r i n g ，o b j e c tr e l a t i o n a l m o d e l ，s o f t w a r ev i s u a l i z a t i o n ，o b j e c t o r i e n t e d s o f t w a r em e t r i c s 第1 章序论 “在面向对象技术的益处被广泛认识的同时。对面囱对象枕翻的不瓤选择 的使麓和分析设i f i , y 2 冲的缺陷也快速导致7 靓一代的不灵活的遗产系统，。 c a s a9 8 1 1研究动机 在整个软件生存期内，软件维护是软件工程中开销最大的部分，所占的比 重从7 0 年代以来越来越高，一般大型软件的软件维护费用都在4 0 8 0 之间 【m a r t 8 3 。因此如何提高软件维护的效率以减少软件成本是工业界非常注重的 问题。而近来软件界经过y 2 k 问题的经历，对软件维护工作的重要性和其维护方 法、工具研究的重要性更得到了广泛的认识。1 0 0 家公司般要维护3 5 0 0 万行代 码，并且每年用于增强、修改等又有1 0 的代码加进去，导致软件大小在7 年中 要扩大一倍 b u s s 9 4 1 ，因此程序的演化也是一个很棘手的问题。据估；, t - 5 0 9 0 的演化工作是花费在程序理解上的，而提高理解效率的最良好和可行的方法 是软件逆向工程 n e l s 9 6 1 。 发达国家由于在六、七十年代，许多领域就应用了计算机软件，存在了许 多用传统语言编写的系统，因此对传统语言的系统的维护技术得到了充分的研 究，并有了许多可以利用的工具。八十年代初出现了第一代的面向对象技术，在 软件系统设计界引起了很大的变革。它将数据结构和在数据结构上的操作结合起 来，使的软件系统更容易维护、扩充，对系统的分析过程也更符合人类的思维模 式。因此很快成为流行的软件开发方法。 但o o 技术不是万能药，在o o 技术的益处被广泛认识的同时，对面向对象机 制的不加选择的使用和分析设计方法中的缺陷也快速导致了新一代的不灵活的 遗产系统 c a s a 9 8 。并且o o 技术并没有提高软件系统的可理解度，如o o 中继 承、多态、动念绑定的使用，以及o o 设计原则鼓励设计更小的方法、更多的特 殊类以利于重用等，这都使得o o 软件内组件关系复杂，造成软件理解上的困难。 二十多年的时间o o 的流行，也导致今天许多大的o o 遗产系统的存在。 我国软件的大量出现和应用也起始于9 0 年代，而此时面向对象技术已经比 较成熟，因此没有很多用传统语言编写的遗产系统，更多的是面向对象的系统。 至今经过十几年的积累，由于系统的文档不能和代码同步、文档丢失、人员变动 等原因的影响，对于许多比较火的系统的维护，凭借原始的软件维护方法，工j p 界已经感到有些力不从心。可以预测在不远的将来，对遗产面向对缘系统的维护 工作，是我国软件界面 i ；的一个重大的课题。 本论文针对上述需求的存在，经过对面向刘象软件和传统程序在特性、设 计知识等方面进行了分析对比，定义了面向对象软件逆向工程( o o r e ) 的基本 内容，并实现了一个i 面向理解的面向对象软件逆向工程框架a u t o o r e ，研究了 其中的一些关键技术。给出了面向对象软件逆向工程“做什么”、“如何做”和 “结果如何”的研究内容。 1 2 研究要点 对于传统软件系统的逆向工程，国外有不少的研究项目，但是对o o 系统的 专门研究很少，且不少研究是将传统程序逆向工程的研究方法用于o o 软件系统， 没有紧密结合o o 软件的特点；或是对o o r e 的某个侧面进行研究，没有对o o r e 进行系统化的研究，并且许多研究在技术上没有重视对软件理解的支持。本文集 中于辅助软件理解这个研究核心，通过对o o 软件和传统软件系统的特点进行对 比分析，给出了o o r e 的内容，研究了面向理解的o o r e 中的一些关键技术。 本文认为在面向理解的o o r e 研究中，下面几点是技术研究的重点： 1 ) 关系的精确抽取问题：对象问的关系抽取为o o r e 活动提供起点，是整 个o o r e 过程的基石。在关系抽取中，如何有效处理o o 中的多态问题， 得到精确的o o 对象关系是o o r e 成败的关键。 2 ) 关系的高层语义抽象问题：在o o 中高层的视图对理解有指导的作用， 而o o 中理解的难点是系统中对象、对象关系数目巨大，如何得到简化 的高层抽象视图，而又能不减少语义，是o o 逆向工程中两难的问题。 3 ) 单个类的理解支持：o o r e 研究都是在类的层次上进行的，对于一个类 本身的理解却没有工具支持，由于在实际o o 系统中存在一些类，它们 本身就是一个很复杂的事物，如f u j a b a 系统中的类 d e u n ip a d e r b o m f u j a b a b a s i c j a v a f a c t o r y 共有1 2 2 个方法，有6 0 0 0 多行代 码。因此如何辅助对单个类详细信息的理解，是o o r e 中的重点。 4 ) 对理解的支持：软件理解是软件维护、演化、再工程、重结构的起始点 和基础，在这些活动中，有5 0 9 0 的工作是花费在程序理解上的， 因此如何提高理解效率，是o o r e 技术研究、工具构造上始终要考虑的 内容。 浙江人学博士论文 5 1 由于传统系统设计中采用的由卜- 向下模块划分和功能划分，因此更易于 找到理解起点和进行功能代码匹配，而o o 系统的应用域模型分散在不 同的类或予系统中，理解某一个功能的对应实现代码更困难。因此存 o o r e z 具中如何支持数据浏览，也是个重要方面。 1 3主要工作和创新点 本文通过对面向对象软件和传统程序在代码特征、没计过程、蕴含知识等方 面进行分析比较，在此基础上按照知识抽象层次由低到高定义了o o r e 的三层基 本内容，把o o 逆向过程和正向工程可以在设计知识层关联起来。并依照逆向结 果中知识的可理解程度将o o 软件的逆向工程研究分为四个层次。 本文依照支持o o 软件理解的中心思想研制了辅助o o 软件系统理解o o r e 环 境a u t o o r e ，它提供o o 软件系统由粗到细的、多层次的、一致性的视图之问 的浏览。a u t o o r e 包括语言抽取器、抽取信息存储库、软件抽象工具、i 叮视化 显示部分。a u t o o r e 中研究并集成了许多基于o o 软件特点的技术：如抽取中 强调o o 抽取的精确性和结果的易理解性，注重软件对象的抽象技术，集成了面 向理解的软件度量，结合了认知心理学的原理在工具的知识表达、可视化结果输 出中等。在这些研究工作，总结起来有以下创新： 1 ) 在面向理解的o o r e 中对o o 多态的处理和用于测试、编译的处理方法是 有区别的，本文针对o o r e 的对象关系抽取，提出了j a v a 程序的代码多 态调用点的概念，并在此基础上提出了个基于e c h o 的多态分析算法 用于j a v a ( 弋玛抽取中，得到更精确的类型关系。 2 ) 首次利用0 0 对象语义关系模型作为聚集输入，从根基上支持软件理解， 并提出了基于m s t 表示的、结合了程序认知心理学理论的软件对象聚集 方法。 3 ) 提出一一套对o o 软件中类之间的语义关系进行量化、压缩的方法。并列 语义关系的相对权重大小进行了详细的研究。 4 ) 根据学习理论中的构造理论，提出了软件人员理解o o 系统中单个类的 理解模型。并实现了辅助类理解的可视化工具m f v c l a s s ，它结合0 0 的 度量数据，提供单个类的内部、外部视图，利用颜色、大小、形状等可 视化信息来传达一个类所代表的知识。 5 ) 提出了r n 研发量用于分离面向对象软件中的域相关对象。 浙江人学博j ：论文 1 4论文结构 本论文共分七个章节，第一章是弓1 言，介绍木文研究的动机、要点、主要 贡献和论文结构。第二章首先介绍了软件逆向工程研究的背景，并解释了软件逆 向工程的基，小= 概念、研究目标和相关研究领域，然后还对o o r e 的技术进行了综 述，介绍了o o 逆向工程的一些研究和工业界的工具。 逆向工程是软件维护、软件重工程、软件重用和软件重结构中的起点，它 本身是一个设计知识发现、知识抽象的过程，而面向对象软件和传统软件相比有 着自己的语言特点和不同的设计知识内容。第三章首先通过对o o 和传统程序的 特点进行对比分析，总结出了而向对象软件逆向工程的基本知识内容，将o o 逆 向工程和正向工程在设计知识层次上关联起来。最后介绍了文中实现的面向理解 的o o r e 框架a u t o o r e 和它的一些特性。 从代码中抽取信息支持理解是逆向工程的重要任务，然而许多抽取方法对 结粜信息的语义末加重视。第四章介绍了程序分析技术、j a v a 语义多态的代码表 现和基于e c h g 的j a v a 码语义关系抽取方法。给出了j a v a 语义模型的形式定义， 并从j a v a 扩展类层次图( e c h g ) 出发，提出了j a v a 代码中的多态渊用点的概念 和一个基于e c h g 的多态调用点分析算法，用于j a v a 程序抽取中得到更精确的静 态对象关系。本文的语义抽取过程有三个阶段：构造系统的e c h g ，扫描程序的 源代码和多态点分析得到系统的词法层次模型，通过基于规则的推理转换词法模 型为语义模型。 第血章综述了软件抽象的技术，介绍了基于m s t 的对象语义聚集方法。在 面向对织逆向工程中，辅助理解的一个有效方法是通过合适的聚集方法提供软件 系统高层的抽象视图。因此软件对象的聚集方法应以辅助理解为最高目标，这体 现在对象相似度的取法、聚集目标、聚集组织等上面。本文方法采用对象系统的 语义关系抽取数据为输入，利用基于m s t 表示的、聚集目标结合了程序认知心理 学理论的软件聚集方法，得到一个具有丰富语义的、树状的系统划分结果。此方 法计算简单，聚集结果稳定，适合于大的工业o o 软件系统的聚集。本章还提出 了对0 0 软件中类之间的语义关系进行量化、压缩的方法，并对0 0 类聚集中关系 的类型语义的相对权重进行了试验研究。试验结果表明在应用系统划分中，组合、 聚集关系占更重要的地位。 第六章介绍o o 度量体系，以及0 0 度量在逆向工程中的应用。0 0 程序的度 量表达了o o 程序在整体上或局部从统计的观点来看的一些性质，可以看作足将 系统作为整体来考察时的内部关系，它能揭示在设计时未知、也没有表达出来的 4 浙江人学陴士论文 内容。 第七章首先简要介绍了软件可视化研究的内容以及软件理解的模型，然后 介绍了本文实现的辅助理解类的可视化工具：m f v c l a s s 。面向对象软件系统中 类是关键的软件对象，在许多工业的0 0 系统中，总存在着具有复杂的内部结构 和关系的一些类，因此在软件维护、软件重工程、重结构等逆向工程活动中，如 何高效理解单个类是面向对象软件逆向工程中的一个重要环节，也是工业界而临 的一个难题。文中依据学习构造理论提出了一个类的理解模型，并实现了一个辅 助理解类的可视化工具m f v c l a s s 。m f v c l a s s 中结合了0 0 的度量数据在多种视 图中，从不同的侧面揭示类所涵盖的内容，提供给软件人员一个多源的理解环境。 文中实例验证了理解模型的f 确性，以及工具本身的可用性。 第八章是本文的结论和展望。 浙江人学博、i ：论文 第2 章o o r e 技术综述 2 1 软件工业界存在的问题 工业软件系统的复杂度和大小在不断增加。重写这些软件花费巨大，因此 需要理解已经存在的代码，需要对其进行逆向工程以进行修改、重用。而对这些 复杂系统的理解、重用存在着许多的障碍。 首先工业软件系统经常像一个“ab i g b a l lo f m u d ”f o o t 9 7 ：它“具 有随意的结构，无计划的、任意扩张的、臃肿的、纵横交错的、如意式面条的代 码丛。”有许多原因使得有良好结构的代码变的无序而过时，而软件开发过程的 时间缺乏和不停息的修改是良好代码变为泥潭的主要动力。时间的压力使得软件 系统缺乏良好的设计。任何商业软件都有“尽快交工”压力，而在开发进度与软 件质量之间达到理想的平衡是一个工程难题。一些调查表明，2 3 的项目超出了 估算的时间。大型项目平均超出计划交付时问的2 0 n 5 0 ，项目越大，超出时 间越长 j o n e 9 4 。 二是软件系统又是不断变化、修改的，变化压力来自多方面：一是客户需 求的变化，二是技术、运行平台等的变化，三是系统本身的一些错误修改。在系 统维护中，一般是在系统运行中快速修改代码，而不经完全测试就又投入运行。 此外维护工作还经常是由一些缺乏经验的程序员来进行，它们不只是要面对复杂 的问题，还要处理不熟悉领域的代码。而事实上，有经验的程序员都倾向于转换 到其它感兴趣的工程和领域，带走了大量的领域相关知识，而这些是维护者所缺 乏的。这些都加速了软件系统的逐渐变形、老化，更加偏离了原来的设计，这种 积累使系统逐渐变的不可用和不可维护。 三是对于遗产系统的维护和重用中，文档方面存在很多的问题，许多系统 都存在丢失、分散的或者错误的文档的情况 c a s a 9 8 ，w i l d 9 2 1 ，因此软件系统 最正确的设计知识只存在于代码中。此外程序员有时也没有自动文档化他们的代 码，代码的逻辑在程序员实现它以后似乎是自我证明正确的，但是几个月后它看 起来却不是这样。 四三是过时的编程工具、平台或过期的硬件使得难以发现知道这种技术或 愿意处理这类问题的人。t ；匕女i y 2 k 问题，使得突然需求大量的专家去测试那些现 在不再用的语言写的系统。 五是软件工业界快速的雇员更换，使得现有的维护人员中，没有人全面理 浙江大学博1 。论文 解原来的设计决定，或需要更多的资源去理解原来的软件系统。 最后是在软件系统中到处都有复制的代码处在，它意味着程序员习惯c o p y 和p a s t e 。重复代码可以导致代码臃肿、错误扩散和降低灵活度( 一个变化要修改 许多地方) f b a x t9 8 ，d u c a9 9 。 上述问题的存在推动了软件工程界对于软件逆向。j j 程、软件重用、软件重 结构、软件重构造( r e f a c t o r i n g ) 、软件自动移植技术等方面的研究，而其中 软件逆向1 j 程是这些技术的基础。 2 2软件逆向工程 2 2 i软件逆向工程的概念 “逆向工程”词来自硬件领域，是通过检查样品来开发复杂硬件系统规 约的过程 r e k 0 8 5 1 ，主要指研究他人的系统，发现其工作原理，以达到复制硬 件系统的目的。在软件工程中，逆向工程可用于描述发现、理解软件系统和其结 构原理的过程，更多的应用于辅助系统的维护和重用等。 c h i k o f s k y 和c r o s s 定义逆向工程为一个分析目标系统的过程 c h i k9 0 1 ，它 包括如下两个部分：一是分辨它的组件并分析组件之间的依赖关系，二是建立系 统另外的、或在更高抽象级别上的表达形式。f t i l l 9 5 将抽取和抽象的两个步骤 进一步精化为建模、抽取和抽象三个步骤： 建模( m o d e l ) 采用概念建模技术构造应用程序的领域模型。 抽取( e x t r a c t ) 利用适当的抽取机制从目标系统巾收集原始数据。 抽象( s b s t r a c t ) 对目标系统进行抽象，以辅助系统理解并允许浏览、分析 和表示抽象结果。 2 2 2 软件逆向工程的目标 软件系统逆向工程的首要目的是增加系统在维护和新开发时的总的叮理解 性。总结起来具体要完成下列任务： a ) 处理复杂性：软件系统越来越复杂，人工方法已经很难有效维护、理解， 研究逆向工程技术和c a s e 3 - 具辅助控制软件系统的复杂性是软件成功 的关键。 b )自动生成系统的其它视图：代码的图形表示可以大大促进理解。自动由 7 代码生成数据流网、控制流图、类图、实体关系图等是软件逆向工程的 基础部分。 c 1 映射应用程序领域和问题域：计算机程序表示了应用领域中的问题，但 是程序通常h i 包含问题的提示，逆向工程的任务之一是重构应用程序领 域到题域的映射。 d ) 映射具体和抽缘级别；软件开发过程从高层抽象到详细设计再到具体实 现。逆向工程则反向运作，从具体细节创建抽象表示。 e ) 重新发现高层结构：程序是具有良好定义的高层结构的载体。但是因为 时间流失和不断维护等上节所述一些问题的存在，这些高层结构可能已 经丢失。 f ) 帮助重用：逆向工程可以帮助或自动检测、筛选在遗产软件系统中的候 选重用组件。 蓟恢复丢失的设计知识：在软件代码的不断修改中，有许多业务规则被加 入而没有反映在文档中，这部分知识可以通过逆向工程来恢复。此外还 有一些知识，如反映代码质量的一些度量数据只有通过逆向工程才可以 发现。 h ) 检测边缘效应( s i d ee f f e c t s ) ：软件修改或加入的部分可能会带入新的 问题，面对原来的代码运行有一定的影响。这种影响无法在正向工程中 反映出来。 浙江大学博 + 论文 2 2 3软件逆向工程相关领域 ( 石刁一厂 、t o d a y s t o m o n o w g d m胛“d 正向工程 重文档和设计美观：生成立 档或设计桓型，不己复变代码 仃、一厂 l 一 灿d e s i 出y 8黧怒d e s i g n u u k l 逆向工程 一- 、s y ，、 o 、三o y 、 重结构：转换系统， 重工程：秉境功能改变 但是功能不变 一一圃 一 s y s t o m - i s s , s t e m - 2 软件重用 重构形：按照规则重新 沮织开发成黝活动 图2 1 ：软件逆向t 程相关领域概念 传统软件工程研究和开发集中在有计划的开发情况下的系统质量和生产率 上，而软件逆向工程是一个致力于开发工具和方法，以辅助理解和管理正在不断 增多的遗产系统的研究领域。遗产系统有两个含义：是你已经投入相当的时问和 金钱，并使用了很长时间的软件系统，而将来你又必须继承它，二是此软件系统 对你是有价值、有用的。对于遗产系统的利用，可以通过软件重用、重工程等方 法让其价值得到体现。而逆向工程技术正是这些技术的基本起点。图2 1 给出了 和逆向工程相关的一些研究领域的定义，简要解释如下： 重文档：生成系统文档，可以是文字描述、伪代码、流程图、数据流图 等，是代码的另外表达形式。 设计发现：生成、发现软件系统设计模型，得到软件系统的抽象表示。 重结构：转换系统的结构，使系统具有如易于扩展、易于维护等良好的 特性，但是功能保持不变 重工程：在保持系统大部分功能下，对系统进行扩充、修改。 软件重用：分辨、提取系统中可用在另外软件系统中的组件，加以封装、 改造用在别的系统实现中。 重构形：按照规则重新组织开发成果的活动。如面向对象软件系统的重 9 浙江大学博十论文 构形经常包括对方法、属性或类蕈新命名、重新定义或对方法、属性或 类完全的重新构造。重构形可以应用于设计、分析和代码结果上。 2 2 4软件逆向工程技术分类 对于软件逆向工程技术，g e r a 9 9 将其分为形式化技术和非形式化技术。 非形式化方法是这些基于代码的词法结构，并依赖于模式匹配及用户驱动的聚集 技术的方法。非形式化技术易于产生结构和功能抽象，模式匹配和聚集技术是非 形式的是因为被构造的设计陈述是非形式化的，并且这些技术缺乏严格方法米验 证在源和设计之间的1 致性。形式化技术是基于一些形式化的方法从源代码来导 出其规格，形式化的基础可以归结为数学逻辑，所以每一步都可以形式化的验证。 两者主要的不同是对于形式化规格语言的应用。形式化规格语言有良好定义的旬 法和语义，因此形式化技术又可以用来构造证明的关联引用规则，用来严格验证 逆向工程过程的每一步的正确性。 非形式化技术又可以分为基于计划的和基于解析的两种子类型，基于计划 的技术主要依赖用模式匹配来分辨代码中的“c l i c h ”或计划，这是研究界和商业 组织的主流。一个程序计划是程序中承担一些抽象功能的一个讨算单元所包含的 描述，它可以是连续的或分散的代码段。基于解析的技术是用编程语言的句法结 构特点分析一个程序，用来构造源代码的高层结构抽象。 ”“”“ “6 1 、9 a r 。n g 一“ 。“ 、t r a n s la t l 。n 图2 2 ：软什逆向j 二程技术分类 g e r a 9 9 1 如果一1 个逆向工程技术的步骤有一个形式化的数学基础，那么它是形式化 的。它把源程序作为输入，生成一个形式化的规格。形式化的逆向工程技术可以 分为两类：基于知识或转换规则的转换技术和应用推导或翻译规则翻泽技术。软 件转换和软件翻译都是把一个规格从一种形式改变到另一种形式而保持软件的 语义不变，但是它们在不同的自动化程度进行。它们主要的不同是应用域和编程 语言的高层知识结合到转换和翻译规则中的程度不同。对于转换，规则一般涉及 浙江大学博上论文 转换编程语句的聚集为简单的、等价的语句，或简洁的形式化规格。为处理不同 的聚集组合，需要很多的规则。而翻译涉及许多基丁单个原子语句，如赋值、条 件和循环的较简单的规则，只需要很少的规则，如语言编译器可以看为一个翻译 器。 2 3 o o r e i ) , o 技术综述 o o r e 技术包括范围很广泛，涉及了软件系统的各个方面，如代码、文档、 维护过程、程序理解、系统重工程、重构造等，下面只介绍和代码逆向工程有关 的技术。 2 3 1 对象间的实际关系抽取 刘象问的实际关系抽取是最基本的o o 软件逆向活动，它是高层抽象的基础。 由于在o o 程序中考察的对象可有文件、类或对象、方法、成员、语句 r a y s 0 0 。 这些考察的对象相同类别之间有复杂的关系，不同类别之间也存在着复杂的关 系，对这些关系的辨别、提取一直是研究的重点。 o o 程序中的不同实体之间的关系总结如图2 5 ，其中“t y p e ”代表o o 程序中 的类、接口等类型。 g f l 2 5 ：面向对象程序- p 各实体的关系 浙江大学博十论文 由上图可以看出，在这些实体的关系中，语句足构成其它实体的基本单位， 语上j 之间的关系在传统的语言中，。般用流程图、数据流 n h e c h 7 7 1 等来表示。 对语句之阳j 的关系的抽取就是如佃得到这些和程序在同等抽象层次上的图形表 达。对语句之间的关系抽取，在对传统的程序逆向工程研究中已经做了很全面的 工作：在文 g a n n 9 9 1 中对其技术、丌发出的工具进行了很好的分类和评价。原 来用于传统语言的许多技术可以用 二o o 中，如可以用流程图米表达类或对象中 的一个方法的实现。但是由于o o 程序中处理的基本数据对象是类，而不是简单 的数据类型，【此更增加了处理的复杂性 h a r r 9 5 。 在图2 5 的各个实体的关系中，类是承载关系的一个核心的实体。类内部的 方法或成员一般没有复杂的关系，而不同类或对象的方法通过类这个桥梁才有了 相互的联系。因此对o o 程序的关系抽取和理解更多的是在类的语言层次上进行 的。 2 , 3 1 1抽取基本方法 为了解决面向对象中的多态问题，在确定对象之间关系的具体类型的过程 中，可以用在编译优化中的技术盘i j c h a ( c l a s sh i e r a r c h ya n a l y s i s ) f d e a n 9 5 方 法，它通过对整个程序的实际类型结构进行分析，得到实际执行方法的类型。它 首先记录一个对象的静态声明类型t d ，然后结合程序的类继承图，决定一个虚 拟调用可能的目标类型集合，此集合一般为静态声明类t d 的予类集。 r t a ( r a p i dt y p ea n a l y s i s ) b a c 0 9 6 1 是对c h a 的改进，它利用了额外的 数据清除c h a 产生的可疑的调用关系，主要是用了对象中具体实例化的类型来 检奄具体激活方法执行的实际类型。r t a 是流程和上下文无关的，并可以得到更 精确的分析结果。 据统计c h a 可以解决5 0 左右的多态，而r t a 可以解决8 0 左右的多态调 用 b a c 0 9 7 。此外更精确的面向对象程序分析方法有别名分析方法c h o l 9 3 ， h 1 n d 9 9 ，以及在文 p a l s 0 1 介绍的其它类型引用分析方法等。这些方法大都要 记录每一个语句的内容，是流程及上下文有关的，并有高的时间和空间复杂度。 2 3 ，1 2静态关系抽取模型 对象或类之间的静态关系抽取模型有许多种，现在常用的是已经得到工业 界普遍认可的、半正则的u m l 类图。采用u m l 类图表示的c a s e 工具现在有r o s e 、 t o g e t h e r 、u m l s t u d i o 、i d e o g r a r n i cu m l 、c o d el o g i c 等 u m lp j ，虽然它们主要 12 浙江大学博上论殳 是正向工程的建模工具，但都加入了一些软件逆向工程的组件，能得到系统基本 的u m l 类图。但是它们逆向过程中对于类之间关系的抽取一般都比较粗略，不 能得到类之间的一些精细关系和动态关系。 d a n i e lj a c k s o n 在他们的工具w o m b l e j a c k 0 1 中用了一种类似u m l 类图的 对象模型，其q j 节点代表一个对象或对象集合，在两节点之间有两种边：一种是 由节点a 指向节点b 的带有标签r 的边，表示关系r 由一个顺序对( a ，b ) 构成； 另一种是由节点a 指向节点b 的带有大的三角箭头的未标注边，表示a 是b 的予 集。边上面可以通过标注表达对象关系的数目特性( m u l t i p l i c i t y ) 和其变化特性 ( m u t a b i l i t y ) 。 对象静态关系表示的另一种是k u a n g 提出的对象关系图( o r d ) k u n g 9 9 1 ， 它可以用公式o r d = ( v ，e ) 来表示，其中v 为系统的对象集合，e 呈( v v ) ，表 示对象两两之间的关系。k u a n g 定义了对象之问的继承( i n h e r e n t ) 、访问 ( a s s o c i a t i o n ) 、聚集( a g g r e g a t i o n ) 三种关系在0 0 程序中的表现形式，并进 一步将聚集分为自动、静态、动态方式，将访问分为友好函数、友好类、友好操 作和参数传递方式。根据上述的关系定义，可以抽取系统的