（计算机应用技术专业论文）面向对象软件动态模型抽象与转换技术研究.pdf

摘要 摘要 随着软件系统日益复杂和庞大，软件开发、维护以及进化的大部分工作和主 要成本集中在对现有系统的理解上。在软件领域中，逆向工程的目标是利用工程 化的方法和技术分析软件系统组件及其之间的相互关联，并以另一种方式或更高 抽象层次的形式来描述该系统。逆向工程是一种辅助程序理解的重要手段。 论文通过对逆向工程规范活动的分析，以模型抽象为研究重点，结合面向对 象软件系统固有的动态特性，采用以动态分析为主、静态分析为辅的研究思路， 提出了一组用于实现面向对象软件逆向工程中动态模型抽取以及动态模型转换的 机制和算法。这些机制和算法都已经在逆向工程工具集x d r e ( x i d i a nr e v e r s e e n g i n e e r i n g ，西电逆向工程) 中实现。为了验证算法的正确性、有效性以及相关 综合性能，本文对其还进行了系统的实验研究。作者研究工作的具体内容如下： ( 1 ) 为了实现动态模型之间的自动转换，首先分析了u m l 序列图和状态图之 间的关系，说明在序列图和状态图之间进行自动转换是可行的。其次，对b k 算 法的核心思想进行了分析，并给出了b k 算法与动态模型转换之间的联系。基于 上述分析，根据动态分析获取的信息以及结合动态模型转换的特点，应用b k 算 法从两个不同的抽象层次( 对象级和进程级) 实现了由多个u m l 序列图自动合 成状态图的工作，分别得到了对象级状态图和进程级状态图。最后，通过实验结 果验证了动态模型自动转换算法的正确性和有效性；并对该算法的效率进行了分 析。 ( 2 ) 提出了一种合并模式的匹配算法。由于合成的简单状态图不能适应复杂软 件系统的要求，因此有必要对简单状态图进行进一步地抽象。本文提出了一种根 据用户给定的合并模式对合成的简单状态图进行再抽象的方法。其主要思想是， 用户给定一种合并模式，在简单状态图中寻找与这种模式相匹配的状态和迁移， 并将它们合并，从而进一步提高合成的状态图的抽象层次。 ( 3 ) 提出了一种基于x o r 状态的分层抽象简单状态图的方法。在简单状态图 中引入层次概念，是增加状态图可理解程度的一种重要手段。通过对x o r 状态 语义的分析，提出了一种寻找简单状态图中具有异或关系的状态，从而形成超状 态的思想，以提高状态图的抽象层次，并给出了实现算法。 ( 4 ) 给出了在简单状态图中添加u m l 概念的方法。无论采用何种算法，所生 成的状态图只能是实际系统的一个近似描述，而且并不完全符合u m l 的标准。 通过对简单状态图特性的分析，发现在包含两种特殊子图的情况下，可以添加 u m l 概念，并给出了形成u m l 中的内部动作、进入动作、退出动作和迁移上的 摘要 动作的规则和条件。 ( 5 ) 提出了一种基于类中的非公有方法创建层次状态图的方法。该方法已经在 x d r e 中实现。 关键词：逆向工程动态模型程序理解屡次状态图面向对象模式 a b s t r a c t a b s t r a c t 1 1 1 f o rt h ec o m p l e x i t yo fs o f t w a r es y s t e m s ，t h em a i nw o r k so fs o f t w a r ed e v e l o p m e n t ， m a i n t e n a n c ea n de v o l u t i o nh a v eb e e nf o c u s e do nt h ec o m p r e h e n s i o no fe x i s t i n g s y s t e m s i nt h er e s e a r c hf i e l do fs o f t w a r e ，t h ea i m o fr e v e r s ee n g i n e e r i n gi st oi d e n t i f y t h ec o m p o n e n t sa n dt h e i rr e l a t i o n s h i p s ，c r e a t er e p r e s e n t a t i o n so ft h es y s t e mi na n o t h e r f o r mo ra tal l i g h e rl e v e lo f a b s t r a c t i o n r e v e r s ee n g i n e e r i n gi sau s e f u lw a yt op r o g r a m c o m p r e h e n s i o n a f t e ra n a l y z et h ep r i m a r yp h a s e so fr e v e r s ee n g i n e e r i n g , t h i sp a p e rm a i n l yf o c u s o nt h et o p i c so ft h em o d e la b s t r a c t i o na n dt h em o d e lt r a n s f o r m a t i o n a c c o r d i n gt ot h e d y n a m i cp r o p e r t yo fo b j e c to r i e n t e ds o f t w a r es y s t e m s ，ag r o u po fm e c h a n i s ma n d a l g o r i t h m st h a tc a nb eu s e dt oe x t r a c td y n a m i cm o d e la n d t r a n s f o r mb e t w e e nd i f f e r e n t d y n a m i cm o d e l so fs u c hs y s t e m s a r ep r o v i d e d a l lt h ea l g o r i t h m sh a v e b e e n i m p l e m e n t e d i nx d r e ( x i d i a nr e v e r s ee n g i n e e r i n g ) t 0 0 1 i no r d e rt ov e r i f yt h e c o r r e c t n e s s ，v a l i d i t ya n do t h e rr e l a t e dp e r f o r m a n c eo ft h e s ea i g o r i t i m a s ，s y s t e m a t i c e x p e r i m e n ti sc o n d u c t e di nt h ep a p e r ( 1 ) i no r d e rt oi m p l e m e n tt h ea u t o m a t i ct r a n s f o r m a t i o n sb e t w e e nd i f f e r e n td y n a m i c m o d e l s t h er e l a t i o n s h i pb e t w e e nu m ls e q u e n c ed i a g r a m sa n ds t a t e c h a r td i a g r a m si s f i r s ta n a l y z e d t h er e s u l ts h o w st h a ti ti sp o s s i b l et ot r a n s f o r mb e t w e e ns e q u e n c e d i a g r a m sa n ds t a t e c h a r td i a g r a m s t h e nt h em a i ni d e ao fb ka l g o r i t h mi ss t u d i e da n d b a s e do nw h i c ht h er e l a t i o n s h i pb e t w e e nb ka l g o r i t h ma n dd y n a m i cm o d e l t r a n s f o r m a t i o ni sp r o v i d e d a c c o r d i n gt ot h ef e a t u r eo fd y n a m i cm o d e lt r a n s f o r m a t i o n a n dt h ei n f o r m a t i o nc o l l e c t e db yd y n a m i ca n a l y s i s ，t h eb ka l g o r i t h mi sa p p l i e dt o a u t o m a t i c a l l ys y n t h e s i z es t a t e c h a r td i a g r a m sf r o ma s e to fu m ls e q u e n c ed i a g r a m sa t t w ol e v e l s ：o b j e c t - l e v e la n dp r o c e s s l e v e l f i n a i l y ，as y s t e m a t i ce x p e d m e n ti s c o n d u c t e dt op r o v et h ea c c u r a t e n e s sa n dv a l i d a t i o no ft h i sa p p r o a c h a n a l y s e so ft h e e f f i c i e n c yo f t h es y n t h e s i sa l g o r i t h ma r ep r o v i d e d ( 2 ) b e c a u s eo ft h ed r a w b a c k so ff l a ts t a t e c h a r td i a g r a m s 。w ep r o p o s e dt o r e - a b s t t a c ts u c hd i a g r a m sb ya ni n t e r a c t i v ew a ya c c o r d i n gt ot h em e r g ep a t t e r n sg i v e n b yn s e r s u s i n gt h e s em e r g ep a r e n t ss t o r e di nx d r e ，w ec a nm a k ea u t o m a t i c a l l y m a t c hp a t t e r n sc o n t a i n e di nt h eo r i g i n a lf i a ts t a t e c h a r td i a g r a ma n di m p r o v ei t sa b s t r a c t l e v e l t h ea l g o r i t h mo f p a t t e r nm a t c h i n gi sp r o v i d e di nt h i sd i s s e r t a t i o n ( 3 ) a na p p r o a c hf o ra u t o m a t i c a l l yg e n e r a t i n gh i e r a r c h i c a ls t a t e c h a r td i a g r a m s w a b s t r a c t b a s e do i lh a r e l sx o rs t a t e si sp r o p o s e d i n t r o d u c i n gh i e r a r c h yt oaf i a ts t a t c c h a l t d i a g r a mi sac o m m o nw a y t oi m p r o v ei t sr e a d a b l e n e s s b ya n a l y z i n gt h es e m a n t i c so f x o rs t a t e s ，a ni d e ao fs e a r c h i n gx o rs t a t e si nf l a ts t a t e c h a l td i a g r a m st of o r m s u r p e r s t a _ t c si sp r o p o s e d t h ea l g o r i t h mi sp r o v i d e di n t h i sd i s s e r t a t i o n ( t ) a na p p r o a c hf o ra d d i n gu m l c o n c e p t st of l a ts t a t e c h a r td i a g r a m si sp r o v i d e d w h a t e v e rt r a n s f o r m a t i o nm e t h o d sa l eu s e d , t h er e s u l ts t a t e e h a r td i a g r a m sa l e a p p r o x i m a t et o t h er e a ls y s t e m sb e h a v i o r s o nt h eo t h e rh a n d ，t h e s es t a t e c h a r t d i a g r a m sa g en o tf u l l ys a r i s 聊n gt h es y n t a xa n ds e m a n t i c so fu m l b ya n a l y z i n gt h e p r o p e r t i e so ff l a ts t a t e c h a r td i a g r a m s ，w ef m di ns u c hac a s et h a taf l a ts t a t e h a r t d i a g r a mm a y c o n t a i no n eo f t w os u b - d i a g r a m so rb o t hw ec a na d du m lc o n c e p t st oi t t h er u l e sa n de o n d i f i o n st of o r mu m li n t e r n a la c t i o n s ，e n t r ya c t i o n s ，e x i ta c t i o n sa n d a c t i o ne x p r e s s e sa t t a c h e dt ot r a n s i t i o n sa r eg i v e n ( 5 ) a na p p r o a c hf o rg e n e r a t i n gh i e r a r c h i c a ls t a t e c h a r td i a g r a ma c c o r d i n gt ot h e p u b l i cm e t h o d so f ac l a s si sp r o p o s e d a n dt h ea p p r o a c hi si m p l e m e n t e d i nx d r e ， k e y w o r d ：r e v e r s ee n g i n e e r i n gd y n a m i cm o d e lp r o g r a mc o m p r e h e n s i o n h i e r a r e h i e a ls t a t e c h a r td i a g r a m 0 b j e c to r i e n t e d p a t t e r n 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学分和优良的科学道德，本人声明所里交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他入已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本入签名：戳日期幽。兰： 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留 送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容， 可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合 学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 导师签名： 日期丑坚 日期垒生丕j ! ：塑： 第一章绪论 第一章绪论 1 1 研究背景与意义 随着软件系统日益复杂和庞大，软件开发大部分工作和主要成本集中于对现 有系统的维护。据调查统计【l , 2 1 ，目前用于软件维护的资源和时间占到软件开发总 投入的5 0 - 8 0 。而在软件维护活动中，理解系统是其首要问题。f i e l d s t a ( 1 和 h a m l e n 经过调查发现【3 】，软件维护中，4 7 的时间用于理解目标系统。因此，采 用工程化的手段分析软件系统，从而理解其结构和行为，对提高其维护效率、降 低其运作成本意义重大。 随着软件的不断维护和演化，许多软件系统逐渐成为遗产系统( l e g a c y s y s t e m ) t 4 】。它们在系统结构和行为组织上逐渐陈旧，需要对其进行大幅度地改进 以适应新的软、硬件环境和模型。但由于这类系统往往承担着业务逻辑实现的关 键任务，也蕴涵着一个领域多年积累的经验和知识，加上用户和管理的原因，这 类系统一般不能采用重新开发的方式来进化1 5 , 6 。同时，遗产系统中的文档或者不 存在、或者经过多次维护后与源代码不一致，加上原系统设计者和开发者的变迁， 能提供目标系统完整可靠信息的往往只有程序代码了。为了能持续性地演化和再 工程遗产系统，程序理解( p r o g r a m ，印，拍p 脚 铆) 显得至关重要 7 , s , 9 , 1 0 , t h ，并且逐 渐成为主要的软件维护活动。通过对目标系统的分析，了解其结构组织和行为逻 辑，可以为这类软件的维护提供指导和帮助，保证其沿着正确的方向演化。逆向 工程( r e v e r s ee n g i n e e r i n g ) 在这个过程中扮演了重要的角色 1 2 , 1 3 】。 近十几年来，随着互联网的发展，自由软件的再工程和重构已经越来越普遍 1 1 4 】。利用自由软件的资源进行软件开发的模式已经对传统软件开发模式提出了挑 战。自由软件往往缺乏系统的、完整的文档，通常也没有统一的设计，不同开发 人员都可以对其进行修改。就已有的文档而言，大多也只是对程序本身的辅助说 明，真正反映系统真实的和准确的框架信息都隐藏在源程序中。因此，逆向工程 为这类软件的重用和进化提供了至关重要的支持。 要理解已有的软件系统，需同时考虑其静态模型和动态模型。静态模型描述 软件的结构，动态模型描述其运行时的行为。不管是静态分析还是动态分析，最 终都可以产生关于软件结构的信息。动态分析还可以得到顺序事件踪迹信息、并 发行为信息以及内存管理信息等。获取目标系统的设计模型是进行程序理解的一 种手段。抽象出的静态模型可以用来确定软件系统的体系结构框架以及软件系统 当前的总体结构；而动态模型可以用来支持调试、寻找从来没有被执行过的程序 !西安电子科技大学博士学位论文：面向对象软件动态模型抽象与转换技术研究 片段【l 引，以及理解软件系统的行为。 面向对象技术的出现，在软件系统设计界引起了很大的变革。它将数据和作 用在数据之上的操作结合起来，使得软件系统更容易维护、扩充，对系统的分析 过程也更符合人类的思维模型。因此很快成为流行的软件开发方法。但是，对面 向对象机制不加选择的使用以及分析设计方法中的缺陷也快速导致了新一代不灵 活的遗产系统f 1 6 1 ，而面向对象技术本身并没有提高软件系统的可理解度。例如， 多态和动态绑定使得我们难以判断运行时哪个方法被真正地调用；继承性意味着 在系统运行过程中，每个对象不但执行它所属的类所定义的行为，而且也可能执 行其父类所定义的行为。这些都使得面向对象软件系统内的组件关系复杂，造成 软件理解上的困难。因此对于面向对象系统，抽取反映软件动态行为的信息显得 尤为重要1 1 7 1 。 在面向对象系统开发过程中，从需求到最终的实现通常会对系统的不同侧面 进行建模，模型之间的转换成为开发过程中的一个关键活动。实现模型转换的 种方法是定义一组模型转换技术。这些模型转换技术的作用是，说明如何利用某 个模型中所包含的信息来定义另外一个模型，以及需要设计人员提供哪些辅助信 息。 在目前的面向对象开发过程中，模型转换是以种非正规的方式进行的【i “。 在文献憎御，2 1 】中虽然提出了一些一般启发规则来辅助用户进行决策，但是没有给 出整体的模型转换方法。这样，在从一个模型到另个模型的转换过程中，就有 可能会出现错误。 正是因为当今软件发展的这些特征和因此而面临的这些新问题，为了更好地 对软件进行维护、再工程和进化，程序理解和逆向工程就显得越来越重要，现在 已经成为软件工程学科的重要分支之一。从| 9 9 4 2 0 0 6 年期间已经连续召开了1 3 次逆向工程国际会议( w o r k i n gc o n f e r e n c eo nr e v e r s ee n g i n e e r i n g ，w c r e ) 。从 1 9 9 3 - - 2 0 0 6 年期间已经连续召开了1 4 次程序理解国际研讨会( t h ei n t e r n a t i o n a l w o r k s h o po f p r o g r a mc o m p r e h e n s i o n ，i w p c ) 。在软件工程、软件维护、面向对象 技术等类的主流国际会议上，近年来也对上述问题设立了相应的专题进行论文交 流和讨论。例如，在欧洲面向对象程序设计国际会议( e u r o p ec o n f e r e n c eo n o b j e c t - o r i e n t e dp r o g r a m m i n g ，e c o o p ) 上，已经连续6 年召开了面向对象软件 再工程国际研讨会( i n t e r n a t i o n a lw o r k s h o po no b j e c t o r i e n t e dr e e n g m e e r i n g ， w o o r ) 。在这种背景下，结合实际项目的需求，对逆向工程方法与技术进行研 究有着重要的理论和实践意义。 第一章绪论 1 2x d r e 逆向工程工具框架 本文的研究范畴属于面向对象软件系统的逆向工程。研究工作的项目背景是 我们研究所承担的课题“系统应用软件逆向工程工具研究”。该项目的主要目标是 设计和开发一套逆向工程工具，以完成符合u m l 标准的动态模型逆向生成、符 合u m l 标准的静态模型逆向生成与分层抽象的实现，并将生成的模型无缝集成 到r a t i o n a lr o s e 开发环境中，从而为提高信息系统的面向对象开发、维护和重用 水平提供有效的支持。 基于本项目的要求，到目前我们已经设计并完成了逆向工程工具集x d r e ( x i d i a nr e v e r s ee n g i n e e r i n g ) 的第三个版本x d r e 3 0 。在x d r e 3 0 中，逆向工程 的对象是符合a n s i 标准的c + + 软件系统，运行平台为u n i x ( s o l a r i s 、l i n u x 等) 和w i n d o w s ( 9 5 、9 8 、2 0 0 0 、n t 等) 操作系统。基于我们已有的工作基础【2 2 】， 逆向产生的、符合u m l 标准的不同层次序列图、层次化的进程结构图、不同层 次状态图以及类图的高层抽象架构图都已经无缝集成到r a t i o n a lr o s e 2 0 0 3 中【2 3 1 ， 全面支持目标系统的再工程活动。x d r e 与本文工作相关的框架如图1 1 所示1 。 图1 - 1x d r e 的动态模型抽象与转换框架 x d r e 0 7 2 以动态分析为主，辅助一定的静态分析，抽取数据、抽象模型，并 从多个角度以符合u m l 和r a t i o n a lr o s e 标准的视图来展现逆向产生的结果。在 图1 1 中，动态分析1 2 4 ，2 5 0 6 1 模块利用植入的方法收集动态信息，通过控制动态信 息产生的范围来提高收集到的信息的可用性，也为产生进程间交互剧情信息提供 支持；然后通过过滤1 2 7 ，分别产生反映对象间交互和进程间交互的剧情图【矧。这 1 除了图1 1 所列举的功能模块外，x d r e 3 0 还实现了系统静态高层架构图的抽象与恢复、进程结构图的抽 象与恢复、序列图、用例图与活动图的逆向生成等功能。由于它不是本文研究的主体内容，在此就没有列出， 详细资料可参见【2 s , 2 9 , 3 q ”2 , 1 。 一4 西安电子科技大学博士学位论文：面向对象软件动态模型抽象与转换技术研究 些剧情图都作为x d r e 的状态图合成模块的输入，通过状态图合成算法分别生成 反映对象行为的对象状态图和迸程行为的进程状态图。为了增加状态图的可读性。 降低复杂度，使生成的状态图能够更好地反映系统动态行为，通过状态图分层抽 象对合成的状态图进行了迸一步地抽象，最终生成迸程级和对象级的层次状态图。 这些抽象后的模型和视图最后都被集成到r o s e 中。 现在许多逆向工程工具的信息表示方法基本由各种工具自己定义，没有一个 标准，因此难以互通和互操作。为了提高了x d r e 与其他相关工具之间的互通和 互操作水平，我们采用具有良好扩充性、且目前被广泛接受的v f i j ”】作为中问 数据的存储和交换格式。同时，由于x i v l l 具有与语言和平台无关的特性，它可 以很好地解决逆向工程中的基本活动不发生在同一平台和环境下的闯题。例如， 在x d r e 3 0 中，人机交互和结果呈现都发生在w i n d o w s 环境下，而软件植入、 信息收集、过滤以及模型抽象的环境则与目标系统相同，既可以是w i n d o w s 平台， 也可以是u n i x 平台。基于x m l 的通用性和易理解性，描述植入范围和高层抽象 封装模式的配置文件也用x m l 表达。 u m l 是面向对象软件的标准化建模语言【j 5 j 6 如，由于其简单、统一，又能 充分表达软件设计中的动态和静态信息，目前已成为可视化建模语言事实上的工 业标准。r a t i o n a lr o s e 是u m l 协会主要成员r a t i o n a l 公司所推出的一套 可视化建模工具，它支持以u m l 为基础、遵循r u p 过程框架的软件开发过程 3 9 , 4 0 l 。同对，r o s e 也支持用户自定义的数据类型，具有良好的扩充接口。以r o s e 中的u m l 标准视图表述逆向工程的结果，能充分保证工具的有效性、通用性和 易理解性。x d r e 利用r o s e 扩充接口【2 2 挪】和u m l 的版型( 跏彤。铆旭) 扩充机制口4 1 ， 有效地把逆向工具菜单命令、人机交互界面、高层行为交互抽象模型图、以及层 次化的状态图无缝集成在r o s e 中，为目标系统的理解和再工程提供了良好支持。 在r a t i o n a lr o s e 2 0 0 3 中，x d r e 3 0 的嵌入式集成如图l - 2 所示。 第一章绪论 图i 2 ) r e 逆向工程工具在r a t i o n a lr o s e 中的无缝集成 1 3 论文的主要工作与组织结构 基于以上讨论的研究背景和项目背景，本文对逆向工程和程序理解的相关技 术进行了研究。基于我们在u m l 和r o s e 扩充方面已有的研究和工作成果【2 2 3 3 1 ， 本文研究的重点是面向对象软件系统动态模型之间的转换技术，以及对转换后的 动态行为模型进行分层抽象的技术。由于面向对象软件系统的固有动态特性，本 文采用动态分析为主，静态分析为辅的研究思路，从多个环节、多个角度、不同 层次讨论了数据的收集和过滤以及模型的抽取和抽象。本文研究工作的主要内容 如下： 1 为了实现动态模型之间的自动转换，首先分析了i h m ，序列图和状态图之间 的关系，说明在序列图和状态图之间进行自动转换是可行的。其次，对b k 一6 西安电子科技大学博士学位论文：面向对象软件动镕噬型抽j 塞兰转垫登研壅 算法p 8 1 的核心思想进行了分析，并给出t b k 算法与动态模型转换之间的 联系。基于上述分析，结合动态模型转换的特点，对b k 算法进行了一定趵 扩充。根据动态分析获取的信息，应用b k 算法从两个不同的抽象层次( 对 象级和进程级) 实现了由多个u m l 序列图自动合成简单状态图的工作，分 别得到了对象级状态图和进程级状态图。最后，通过实验结果验证了动态 模型自动转换算法的正确性和有效性；并对该算法的效率进行了分析。 2 提出了一种合并模式的匹配算法。由于合成的简单状态图不能适应复杂 软件系统的要求，因此有必要对简单状态图进行进一步地抽象。本文提 出了一种根据用户给定的合并模式对合成的简单状态图进行再抽象的方 法。其主要思想是，用户给定一种合并模式，在简单状态图中寻找与这 种模式相匹配的状态和迁移，并将它们合并，从而进一步提高合成的状 态图的抽象层次。 3 提出了一种基于x o r 状态的分层抽象简单状态图的方法。在简单状态图 中引入层次概念，是增加状态图的可理解程度的一种重要手段。通过对 x o r 状态语义的分析，提出了一种寻找简单状态图中具有异或关系的状 态、从而形成超状态的思想，以提高状态图的抽象层次，并给出了实现 算法。 4 提出了一种基于类中非公有方法创建层次状态图的方法。该方法已经在 x d r e 中实现。 5 给出了在简单状态图中添加u m l 概念的方法。无论采用何种算法，所生 成的状态图只能是实际系统的一个近似描述，而且并不完全符合u m l 的 标准。通过对简单状态图特性的分析，指出在包含两种特殊子图的情况 下，可以添加u m l 概念，并给出了形成u m l 中的内部动作、进入动作、 退出动作和迁移上的动作的规则和条件。 在逆向工程关键技术的研究和x d r e 的设计实现过程中，作者的角色是负责 项目研究和工具开发的分析与设计，重点的工作目标是研究本项目中面向对象软 件系统逆向工程关键活动中的技术难点，主体的工作内容是分析研究符合本项目 特点和要求的动态模型转换方法、机制和策略。除了定义、分析并抽象出了以上 给出的若干方法和模型外，作者也给出了实现这些方法和机制的核心算法，并通 过理论分析和系统实验讨论了这些算法的收敛性、有效性以及相关综合性能。而 这些核心算法的代码实现工作以及其他细节性的程序开发工作由课题组其他相关 成员负责实施完成【4 l , 4 2 , 3 1 。 全文共分七章，第一章为绪论，介绍了本文研究工作的背景和意义，给出了 x d r e 的相关框架，列举了本文研究工作的主要内容。第二章简要介绍了逆向工 程的概念、方法和工具。第三章介绍了b k 算法的核心思想及其与动态模型转换 第一章绪论 的联系，并给出了应用b k 算法p 8 j 从一组u m l 序列图合成u m l 状态图的主要思 想与核心算法。第四章针对合成算法生成的简单状态图的弱点，探讨了对简单状 态图进行进一步抽象的方法。提出了基于用户选定的合并模式的自动匹配方法， 给出了在简单状态图上添加u m l 概念的方法。在第三、四章工作的基础上，第 五章提出了将层次性引入简单状态图的思想，并给出了基于x o r 状态和类中非 公有方法的自动生成层次状态图生成方法。第六章给出了验证第三、四、五章中 所给算法的实验及其结果和对实验结果的分析。最后，第七章对研究成果进行了 总结，给出了需要进一步研究的问题。 !西安电子科技大学博士学位论文：面向对象软件动态模型抽象与转换技术研究 第二章逆向工程概述 2 1 基本概念 逆向工程的概念起源于对商业或军事领域硬件的分析，其目的是在不了解或 很少了解最初生产过程的情况下，从最终产品推断出其设计方案。m g r e k o f f 把 逆向工程定义为“通过有序地检查一个复杂硬件系统的样本，从而得到它的一组 规范的过程”【4 3 l 。实施该过程的通常不是开发人员，其目的是为了构造出一个原 硬件系统的克隆。在软件领域中，逆向工程更多的是为了恢复错误的、不完整的 或难以获得的文档信息，其目标不再是复制系统，而是获得对一个系统和它的结 构在设计层的充分理解，从而帮助维护，增强性能，或支持替换 4 3 , 4 4 ，5 引。 在软件领域，c h i k o f s k y 和c r o s s 把逆向工程定义为一个分析软件系统组件及 其之间相互关联，并且以另一种方式或更高层次抽象的形式来描述系统的过程 【4 5 1 。其基本原理是抽取软件系统的主要部分而隐藏其细节，然后使用抽取出的实 体在高层上描述软件系统。逆向工程抽取的实体应比源代码更容易推理和接近应 用领域，同时在高层上对软件系统的抽象表示更为简洁和易于理解l 蛔。逆向工程 的研究对象是已有的软件系统，而不是需求。逆向工程可以从任意一个抽象层或 生存周期阶段开始，而不一定都是从源代码开始的。另外，逆向工程本身并不会 改变目标系统，也不会基于被逆向的系统创建一个新系统，它只是一个检查的过 程，不是一个改变或复制的过程。以下是几个与逆向工程相关的概念【4 5 】。 文档再生( r e d o c u m e n t a t i o n ) ：指在同一抽象层次内，创建或重建语义等 价的表示。它是逆向工程最简单的形式【4 7 1 ，仅涉及在同一层次上产生( 如 果不存在) 或修正文档。文档再生不会改变目标系统1 4 引。 设计恢复( d e s i g nr e c o v e r y ) ：运用领域知识及可能的外部信息在较高的 抽象层次上产生系统模型。设计恢复是逆向工程的一个子集，领域知识、 外部信息、演绎和模糊推理都被加到对目标系统的分析中，以识别有意 义的高层抽象。t e db i g g e r s t a f f 认为，设计恢复结合了代码、现存的设计 文档( 如果有的话) 、个人经验和关于问题和应用域的一般知识，它要处 理的信息远比从传统的软件工程表示和代码中所获得的要多1 4 9 1 。设计恢 复也不会改变目标系统，但是设计恢复跨越了几个层次。 结构重组( r e s t r u c t u r i n g ) ：在同一抽象层次内对系统的横向转换，同时 保持原系统的外部行为不变( 功能和语义) 。其目的是调整系统以适应变 化的环境。结构重组改变了系统，但不改变功能。 第二章逆向工程概述 再工程( r e e n g i n e e r i n g ) ：是为了重建一个目标软件系统而检查它，改变 它，然后以新的形式实现它。它改变了目标系统，涉及了软件的多个抽 象层次或生命期阶段。 文档再生和设计恢复都没有改变目标系统，属于逆向工程范畴【5 0 】。文档再生 强调在同一抽象层次把问题本身转化为另一种表示，往往是可视化的图形表示， 以增进对原有程序的理解；而设计恢复却涉及了从源程序到设计的变换，即包括 了两个阶段或两个抽象层次，它所得到的信息远比从设计文档中得到的多。再工 程是为了建造一个新系统而分析和改变目标系统，而逆向工程是为了获锝对目标 系统的理解而分析它，它不能改变软件系统本身。结构重组改变了目标系统的形 式，只是为了使之适应新的标准和变化的环境，而系统的外部功能不变。再工程 通常包括某种形式的逆向工程，然后进行某种形式的正向工程或结构重组垆”。 2 2 规范活动 逆向工程是一个检查和分析的过程，并不改变且标系统。通过标识组件、发 现其间关系并抽象系统，逆向工程可以辅助对系统的理解。从目标系统源代码开 始，逆向工程通常包含三个规范活动【4 ”o 】：( 1 ) 数据抽取( e x t r a c t i o n ) ：( 2 ) 模 型抽象；( 3 ) 结果呈现( r e p r e s e n t a t i o n ) 。 原始数据是抽象和呈现高层抽象结果的基础，通常隐藏在程序代码中，因而 数据抽取是逆向工程的一项基本活动 5 2 , 5 3 , 5 4 , 5 7 1 。作为构造抽象表示的基础，所抽 取的数据应当客观实际，并且，基于有益于理解的出发点，抽取的数据要尽量准 确且有用。为此，数据抽取应从多个角度、采用多种手段来实现。 数据收集是数据抽取的基本过程。它所采用的技术包括静态分析、动态分析 和获取非正式数据( 如调查) 等。静态分析通常通过分析程序源代码、构造带有 语法单位及其依赖关系的抽象语法树来完成。采用基于编译的成熟技术，可以收 集到准确和可靠的静态信息数据。源代码植入技术是产生运行时信息的最常用方 法1 5 引。它通常的做法是在目标程序代码中加入新的代码，这些代码仅仅用于收集 运行时信息。除此而外，通过修改编译器来产生事件轨迹也是可能的。文献【5 5 5 q 通过使用一个类似调试器的方案收集动态信息，文斛1 5 】通过修改j d k 调试器产生 动态事件，收集j a v a 程序运行时产生的事件踪迹信息。 数据过滤是数据抽取的关键操作之一。为理解大型系统所收集的数据可能非 常巨大，以至于超出了用户吸收的能力。要理解系统，关键在于了解什么和忽略 什么1 5 9 。数据过滤是从丰富的原始数据中抽取对系统理解有帮助的组件及其关 系，其目的是辅助系统理解。数据过滤通常是在信息产生后进行，为了控制有效 数据的产生，也可以在数据收集阶段，通过控制一些影响收集策略、范围和内容 9 一1 0 西安电子科技大学博士学位论文：面向对象软件动态模型抽象与转换技术研究 的参数，来达到抽取有效、有用数据的目的。 除了程序代码，领域信息和专家知识对数据的有效抽取也有重要作用 c o 川。 在数据收集前期，一个好的收集策略和方案的确定往往需要具备一定领域知识的 专家介入；在数据过滤阶段，过滤原则也不能背离被分析软件系统所在领域的特 征。领域信息和专家知识会使得抽取的数据更准确、更可靠、更有用。 模型抽象是辅助用户理解目标系统高层单元及其之间依赖和交互关系的主要 过程。通过对初始模型的抽象，可以提取隐藏在细节数据中的系统设计时的模型 信息。模型抽象的基础是数据抽取阶段抽取的、反映系统真实结构和行为信息的 数据。但这些数据只反映了附加在程序代码上的低层结构单元关系和行为交互序 列，是程序空间到设计空间的第一层映射。为了能从多个角度、不同层面理解目 标系统的整体框架和行为特征，就需要进一步建立从低层次模型到高层次模型的 映射关系，并从多个角度来抽象出目标系统的设计模型，甚至是需求模型。模型 抽象是一项比较复杂的工作，除了抽象规则、方案和算法外，也需要领域知识和 专家的介入。半自动化的模型抽象方法能产生出有益于用户全面理解目标系统的 高层模型。 结果呈现是逆向工程的最后一个环节，也是直接影响到程序理解效果的主要 步骤。不同类型的信息和模型都有各自的呈现方式，例如呈现静态信息的解析树、 数据流图、控制流图、类层次图等；展现动态模型的剧情图、协同图和状态图等。 其目的都是为了让用户更好地理解系统。现在的许多逆向工程工具都以图形化的 视图来表达目标系统的逆向抽取和抽象结果 4 9 ，9 6 , 9 7 , 1 0 8 , | 5 7 , 1 5 8 , 7 7 , 7 5 ，大多数工具也 都有各自的图形符号语言和规范 1 0 8 , 1 5 7 , 1 5 8 j 。通常有三种视图可用于描述抽取出的 数据：静态模型、动态模型以及混合模型。静态模型仅包含静态信息，动态模型 仅包含动态信息，而混合模型既包含了静态信息又包含了动态信息。除此之外， 有的工具还把收集到的信息的度量( m e t r i c s ) 值附加到结果呈现中 1 5 , j o s ，从多个 角度尽可能多地表达目标系统的信息。 2 2 1 使用单个视图 将动态信息和静态信息在同一个模型上显示的优点是，能够清晰地描述静态 信息和动态信息之间的关联。而且在合并动态信息和静态信息的同时，可以提高 模型的质量。例如，如果程序中使用了多态机制，静态分析就无法确定所调用的 是哪一个方法，这只有在程序运行时才能确定。这时就需要动态分析来确定所调 用的具体方法。 但是由于静态分析和动态分析所抽象的是不同的信息，因此要建立同时包含 了静态信息和动态信息的视图是比较困难的。静态信息抽象的往往是子系统，而 第二章逆向工程概述 动态信息抽象的通常都是用例或者行为模式。这就要求用户首先确定，是从静态 的角度还是从动态的角度来创建抽象模型。例如对于一个由银行、银联和a t m 构成的银行系统，在该系统中可以使用a t m 取款或者查账。从静态分析的角度 来看，a t m 和银行就是子系统；而从动态分析的角度，“使用a t m 取款”和“使 用a t m 查账”是两个不同的用例。要实现这两个用例，就必须在a t m 和银行之 间进行通信。 其次，构成这种混合模