（计算机应用技术专业论文）面向程序理解的转换系统研究.pdf

摘要 程序理解在软件维护、遗留系统的现代化改造以及软件逆向工程等领域的关 键技术。它具有重大现实意义和经济价值，不但可以避免重复劳动，提高软件生 产的效率和质量，而且可以将大量的遗产系统转化为易演化系统，从而充分有效 地利用这些遗留系统。论文在软件复用和转换通用性基础上提出了适用于多种程 序范型理解的转换系统模型并且实现之。目前，通用的转换系统有如m i c r o s o f t 公 司i p ，r e a s o n i n gs y s t e m s 技术有限公司的r e a s o n i n 9 5 和s c i c o m p 技术有限公司的 s c i n a p s e 等。为此，转换系统的研究对繁荣我国软件产业和实现我国软件产业可 持续发展具有积极的意义。 论文通过深入的调研和在参阅国内外大量文献的基础上，对转换系统进行了 较为深入的研究，主要的内容和技术创新包括： 1 、描述了当前程序理解中的技术现状，同时对程序理解的意义和方法以及程 序设计决策也进行了详细的阐述。 2 、论文提出了多范型理解的转换系统模型并且实现了该模型。 范型理解是一种能够用于多种程序语言结构分析且具有交互界面的程序结构 分析器。范型理解的引入大大的提高了软件重用性和软件易于维护性。 3 、论文针对高级语言理解中存在嵌套与并列的问题提出了理解程序设计语言 中嵌套和并列的算法并且实现之。 4 、最后作者利用设计的转换系统，用p a s c a l 语言进行了测试达到了预期目 标。 关键词：转换系统；范型理解；程序理解；遗留系统；软件复用；逆向工程 a b s t r a c t p r o g r a mu n d e r s t a n d i n gi sa tt h ev e r yh e a r to fs o f t w a r em a i n t e n a n c e ，l e g a c y s y s t e mm o d e r n i z a t i o na n ds o f t w a r er e e n g i n e e r i n g ，e t c s o f t w a r er e v e r s ee n g i n e e r i n g h a sg r e a tp r a c t i c a la n de c o n o m i cv a l u e i tc a nn o to n l ya v o i dr e d u p l i c a t el a b o ra n d i m p r o v ee f f i c i e n c ya n dq u a l i t yo fs o f t w a r ep r o d u c t i o n ，b u ta l s oc h a n g eap l e n t yo f l e g a c ys y s t e m si n t ot h es y s t e m st h a tc a nb ee v o l v e de a s i l yi no r d e rt ou t i l i z et h e s e u s e f u lr e s o u r c e a d e q u a t e l y t h et h e s i sp u t s f o r w a r dt ob e a p p l i c a b l e t ot h e t r a n s f o r m a t i o ns y s t e mm o d e lt h a tv a r i o u sp r o g r a mp a t t e r nc o m p r e h e n d i n ga n dp e r f o r m i tb a s eo ns o f t w a r er e u s ea n dt r a n s f o r m a t i o ng e n e r a l a t p r e s e n t ，t h eg e n e r a l t r a n s f o r m a t i o ns y s t e mi sn o tm u c h ，s u c ha sm i c r o s o f tc o m p a n yi p ，r e a s o n i n gs y s t e m s t e c h n i q u e l i m i t e dc o m p a n yr e a s o n i n 9 5a n ds c i c o m pt e c h n i q u el i m i t e dc o m p a n y s c i n a p s e t h e r e f o r e ，t r a n s f o r m a t i o ns y s t e m o fr e s e a r c ht o p r o s p e ra n dk e e p s u s t a i n a b l ed e v e l o p m e n to u rc o u n t r ys o f t w a r ei n d u s t r yh a sap r o f o u n ds i g n i f i n c ea n d p o s i t i v em e a n i n g w i t ht h eb a c k g r o u n do ft h o r o u g hi n v e s t i g a t i o n ，b a s e do nr e a d i n gt h el a r g e q u a n t i t y o fd e m o s t i ca n do v e r s e a sl i t e r a t u r e s ，t h et h e s i sp r o c e e d e dt h e t h o r o u g h r e s e a r c hf o rt h et r a n s f o r m a t i o n t h em a i nc o n t e n t sa n dt e c h n i c a li n n o v a t i o no ft h i s t h e s i si n c l u d e ： 1 t h et h e s i sd e s c r i b e st h et e c h n o l o g yd e v e l o p m e n to fp r o g r a mu n d e r s t a n d i n ga t p r e s e n t 。a tt h es a m et i m e ，t h et h e s i sd e t a i l sp r o g r a mu n d e r s t a n d i n go fs i g n i f i c a n c e ， m e t h o da n dp r o g r a md e s i g nd e c s i o n 2 t h et h e s i sp u tf o r w a r dt r a n s f o r m a t i o ns y s t e mm o d e lt h a tp a t t e r nc o m p r e h e n d a n ds p e c i f i ct h a tm o d e l p a t t e r nc o m p r e h e n s i o ni sak i n do fc a n n i n gu s e df o rv a r i o u s p r o g r a ml a n g u a g ec o n s t r u c t i o na n a l y s i sa n dt h ep r o g r a mc o n s t r u c t i o na n a l y s i sm a c h i n e t h a ti th a v ef r i e n d l yi n t e r f a c e p a t t e r nc o m p r e h e n s i o no fp u t i n gf o r w a r dl e a dt o i m p r o v es o f t w a r er e u s ea n ds o f t w a r em a i n t e n a n c e 3 t h et h e s i sp u tf o r w a r dt on e s t i n ga n dj u x t a p o s e da l g o r i t h m si nt h eh i g hp r o g r a m l a n g u a g ea n dp e r f o r mt h e m 4 a i m i n ga t t h ep r a c t i c a lp r o b l e m ，t h et h e s i sm a k e su s eo ft h et r a n s f o r m a t i o n s y s t e mo ft h ed e s i g nf i n a l l y ，p r o c e e d i n gw i t ht h el a n g u a g eo fp a s c a l t ot e s tc o m e st o ae x p e c tt h et a r g e t k e y w o r d s ：t r a n s f o r m a t i o ns y s t e m ： g e n e r i cc o m p r e h e n s i o n ；p r o g r a m u n d e r s t a n d i n g ；l e g a c ys y s t e m s o f t w a r er e u s e ，；s o f t w a r er e v e r s e e n g i n e e r i n g 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：董务君孑 日期：跏肄印月；p 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“4 ”) 作者签名：- 舅 生r a 霸- - 猡军 导师签名：锄 日期：西吨琢年月；o 日 日期：擀够月；o 日 1 1 研究背景 第一章前言 软件维护、遗留代码的现代化改造以及软件的再工程问题等都是软件界普遍 关注的话题眦l 。它们自软件开发或投入使用之时起就被提上日程，而且必将伴随 和见证i t 业同后的最新发展，舍之不去，挥之不掉。以上这些问题的有效解决 般都很大程度依赖于程序理解：利用现代化分析工具或转换系统对遗留代码进行 白盒，黑盒、动态静态分析，提取信息，获取抽象描述，从而达到重构具有现代意 识的各类文档和领域模型。显然，程序理解是一项相当复杂的工作1 1 3 】。方法上我 们需要将传统的人工阅读方法与分析工具或自动化转换手段有机地融合，技术上 则要求所研发的工具具有较强的壮健性，能处理应付多样化的事物描述。只有合 适地解决了这些矛盾，程序理解方有望获得突破性进展。 随着计算机技术的飞速发展，计算机应用的领域不断扩大，人们希望计算机 能够解决各个领域更多、更复杂的问题，从而也对计算机软件产品的功能、质量、 丌发成本和时间提出了越来越高的要求。计算机软件在各个领域经过了几十年应 用的积累，特别是自九十年代以来，应用软件系统的规模越来越大，功能越来越 复杂，使得更多的大型软件的开发必须考虑到原先己运行了多年的系统，包括系 统的需求、设计决策、业务逻辑、业务规则、历史数据等等，称之为遗留系统l s f l e g a c ys y s t e m ) 。l s 是一种巨大的、长期的投资，因此如何充分利用这些有用的 资产对遗留系统现代化改造和新系统的开发显得尤为重要。由此，产生出理解原 来的系统的问题。在利用遗留系统前必须充分理解系统，而在很多情况下遗留系 统完整可靠的信息是其程序代码，其它很多信息必须由此导出。 通过程序理解获得足够的信息才能让系统按照期望的方式进行现代化改造。 因此，程序理解是遗留系统成功进行现代化改造的关键问题之一。辅助程序理解 的方法技术有多种，如手工浏览源代码、静态或动态分析目标系统、或者收集和 分析系统的度量数据。但是，从很大来说，这些方法的胜利实施都依赖于程序理 解技术和转换系统工具的设计对遗留系统进行现代化改造。程序理解通过分析标 识系统元素，发现元素间的关系和产生系统的不同形式和层次的抽象表示，完成 应用程序领域到问题域的映射、重新发现高层结构等任务【4 1 。 1 2 研究现状 无论是在国内还是国外，对程序理解的研究都己经有十几年的时间了，虽然 已经形成了一定的研究规模，也发表了不少的研究文献，但是程序理解仍然属于 相当不成熟的领域，这主要表现在对理论和实践的研究都还处于早期的探究阶段， 并未形成统一的、系统化的、科学化的程序理解的理论和方法。 在国外，程序理解是作为软件维护的一部分出现的。卡内基梅隆大学软件工 程研究所c m u s e i 成立了专门的再工程中心，致力于通过软件逆向工程进行程序 理解技术的研究、增强和实践推广。其中，c h i k o f s 等人于1 9 9 3 年发起的逆向工 程会议每年举行一次，研究和讨论软件逆向工程的问题、技术及其支持工具。大 量的研究成果都集中在程序理解的辅助工具上。程序理解技术发展至今，己经研 制开发出许多工具，下面介绍一些典型的工具 5 1 。 1 2 1r a t i o n a ir o s e 工具 r o s e r o s er e a l t i m e ( r o s er t ) 提供的逆向工程工具，可以从多种程序设计语 言源程序中自动产生静态设计模型，但目前只能逆向产生类图。r o s e a r c h i t e c t 是 u s c ( u n i v e r s i t yo fs o u t h e r nc a l i f o r n i a ) 与r a t i o n a l 合作开发的一种可视化工具，用 于对u m l 类图中的实体进行基于规则的等价合并，以突出地呈现系统的软件体系 结构成份。 1 2 2m o r a l e i s v is 工具 m o r a l er m i s s i o no r i e n t e da r c h i t e c t u r a ll e g a c ye v o l u t i o n ) 是d a r p a 资助的 一个e d c s ( e v o l u t i o n a r yd e s i g no fc o m p l e xs o , w a r e ，复杂软件的进化式设计) 类 课题。课题中与逆向工程有直接关系的是i s v i s ( i n t e r a c t i o ns c e n a r i ov i s u a l i z e r ) 工 具。这种工具的功能包括：读入源程序文件，解析后产生静态信息文件；利用源 代码、静态信息文件以及用户提供的相关的信息，产生获取动态信息所需的代码； 执行插入上述代码后的目标系统，产生动态事件跟踪信息，并自动转变成剧情； 用户通过所产生的剧情视图进行交互式分析。 1 2 3a u g u s t - | i 工具 a u g u s t i i 是一个数据逆向工程工具。该工具以c o b o l 记录格式或d b 2 数据 定义等各种各样的数据资源为输入，产生概念数据模型，使用户能够理解当前的 环境并转向新的数据技术。其输出能用作许多不同软件包如c a s e 工具和商业数 据库管理系统的输入。 1 2 4m ic r o s o f tv is i 02 0 0 2 工具 有三个不同版本；标准版提供图表解决方案，帮助业务专业入员共享他们日 常处理的信息、并加以可视化：专业版增加了新的功能，帮助技术专业人员对现 有创意、信息和系统加以可视化，并建立新创意、信息和系统的原型；企业版带 有企业网络工具附件，l t 专业人员就可以获得高级网络图表和文档能力。该环境 对于正向工程的支持类似于r a t i o n a lr o s e ，而逆向工程则只支持m i c r o s o f 的语言 产品，可以从v i s u a lb a s i c 、v i s u a lc + + 及v i s u a lj 十十自动生成u m l 类图，但每 种语言使用的逆向工程技术各不相同。对于j + + 和v i s u a lb a s i c 是利用开发环境的 对象模型来收集静态结构信息；对于c + + 则是浏览信息文件( b s c 文件) 用作结构 2 信息的来源。虽然v i s u a lb a s i c 和j + + 逆向工程都使用开发环境的对象模型，但j + + 对象模型提供了更完整的信息，因此可得到更完整的逆向工程u m i 模型。v i s u a l c 十+ 中的浏览信息、文件包含的信息最少，因此它所生成的u m l 模型不如v i s u a l j + + 和v i s u a lb a s i c 逆向工程得到的u m l 模型完整。 1 2 5s n i f f + 工具 s n i f f + 不是一个单纯的逆向工程工具，而是一个开放的、可扩展、伸缩的 c c + + 程序设计环境，具有逆向工程能力。s n i f f + 提供了一个有效而轻便的环境， 用户界面友好。s n i f f + 适用于不能完全解析的半成品软件系统，在产生可打印的视 图和测览半成品系统等方面也具有特色【6 l 。 1 2 6j b p a s 工具 j b p a sr j a d eb i r dp r o g r a ma n a l y s i ss y s t e m ) 是一个针对c + + 语言的程序理解系 统，由一个c + + 分析器前端和一组分析工具组成。该系统是北大青鸟基于异构平 台、具有多信息源接口的应用系统集成( 组装) 环境青鸟i i i 型( j b 3 ) 系统1 7 】一的组 成部分。该系统针对c + + 语言，采用增量分析技术对程序源代码进行静态分析； 用e e rf e u h a n c e d e n t i t y r e l a t i o n s h i p ) ) 勾c + + 程序建立概念模型并抽取程序信息， 将信息保存在数据库中：按照不同的用户需求组织程序信息，辅助用户理解c + 十 程序；逆向生成源程序的o o d ( o b j e c t o r i e n t e dd e s i g n ) 文档和r o s e 文档( 但实际 所需的时间很长，对于1 0 万行源代码的程序，大约需要6 小时) 。该系统中的面 向对象测试支持工具( o b j e c t o r i e n t e dt e s t i n gs u p p o r t e r ) 能, 够利用插装技术跟踪程 序的运行，以辅助测试用例的生成。 程序理解是种重要的软件工程技术。它为遗留系统的现代化改造提供了理 论和技术上的支持”】，是转换系统的有效支持手段。它在软件复用、大型软件的开 发等领域扮演着重要的角色。同时，程序理解由一些工具辅助完成，否则，手工 完成这项工作费时费力，不仅会导致整个结果无用而且费用非常昂贵。就目前许 多典型的国内外程序理解相关工具而言，对常规静态模型的理解支持已经比较广 泛，但是对于面向对象的程序，必须进行动态模型的理解，才能真止获得程序的 行为特征。同时，各种工具都有很强的前提条件，例如所支持的程序设计语占、 操作系统和数据库平台、调试工具和系统支撑工具、面向对象建模语言、人机交 互语言和界面等，在不同的前提条件下工具的支持能力有很大的区别。为此，对 转换系统的辅助工具进行深入的研究非常有必要。 在国内，由于遗留系统还不够多，而且对软件的后期维护也不太重视，所以 对程序理解的研究也比较少，北京大擘以杨芙清院士为首开发的“青鸟软件生产 线系统”中的青鸟逆向工程工具是其中一项实质性的成果。但是仅有这一项成果 是远远满足不了程序理解的需要的，很显然，遗留系统的复杂性和软件逆向工程 形式的多样性使得这项成果并非对所有的程序理解均可以提供有效的支持，因此 对转换系统辅助工具的深入研究具有实际意义，尤其是对系统化的、科学化的转 换系统辅助工具理论和方法的研究。 总之，为了软件重用和软件可维护性以及遗留系统的现代化，本人认为对转 换系统辅助工具研究非常有必要。 1 3 论文的内容与结构 本文在程序理解和转换通用性的基础上，首先提出了适用于多种程序范型理 解的转换系统的系统架构【8 1 ，其次论文就转换系统原则和架构进行了深入研究。再 次论文研究了转换系统的系统实现。最后论文研究了转换系统的应用原理和就 p a s c a l 语言给出了测试实例。论文的结构安排如下： 第一章前言，阐述了论文的研究背景、程序理解的研究现状，并且简要介绍 了论文的内容和结构。 第二章程序理解技术述评，研究了程序理解的意义、方法和程序理解的设计 决策。 第三章转换系统及架构，研究了转换系统定义、类型以及方法和重写规则。 本章最后提出了转换系统的架构。 第四章系统实现原理，研究了转换系统辅助工具的实现原理和实现技术并且 予以编码实现。 第五章应用原理与实例，给出了辅助工具的应用原理，就p a s c a l 语言给出 了测试实例。 最后总结与展望，对转换系统辅助工具进行总结和给出了下一步要做的工作。 4 第二章程序理解述评 2 1 软件逆向工程的定义及相关概念 在软件工程领域，程序理解几乎是与逆向工程是同一术语。术语“逆向工程” ( r e v e r s ee n g i n e e r i n g ) 来自于硬件领域，是通过检查样品开发复杂硬件系统规约的 过程i ，主要指研究他人的系统，发现其工作原理，以达到复制硬件系统的目的1 1 0 】。 但随着软件业的发展，逆向工程这一术语被引入软件工程领域，软件逆向工程可 以用于描述揭示己有系统工作原理的过程【1 “，或者是用于描述创建现有文档的联 机文档的过程1 1 2 j 等。当然逆向工程还适用于软件的其它领域，比如图象滤波、自 由曲面建模等。我们研究的对象是在软件工程领域中。 在软件工程领域中，迄今为止还没有软件逆向工程的标准定义。一般将软件 逆向工程定义为包含抽取和抽象这两个步骤的过程1 1 3 1 ：第一步分析目标系统，标 识目标系统的元素以及它们之间相互关系，第二步创建不同形式或更高抽象层次 的系统表示。s c o t trt l l l e y 将两个步骤进一步细化为建模、抽取和抽象三个步骤 【1 4 1 ： l 、建模( m o d e l ) ；采用概念建模技术构造应用程序的领域模型。 2 、抽取( e x t r a c t ) ：利用适当的抽取机制从目标系统中收集原始数据。 3 、抽象( a b s t r a c t l ：对目标系统进行抽象，以辅助系统理解并允许浏览、分 析和表示抽象结果。 国家自然科学学科发展战略报告计算机科学技术部分中是这样定义软件逆向 工程的1 1 5 l ：从可运行的程序系统出发，生成对应的源程序、系统结构以及相关设 计原理和算法思想的文档等。从这个定义可以看出，软件逆向工程可以用于较低 级的抽象层次，例如把可执行程序转换为源代码，但主要是用于将源代码转换为 更高抽象层次上的表示，如控制图、数据流图和类关系图1 1 6 】等。 下面列举的是与软件逆向工程紧密联系的几个术语1 1 7 j ： l 、正向工程( f o r w a r de n g i n e e r i n g ) ：按照问题定义、可行性分析、需求分析、 概要设计、详细设计、编码和测试的软件生存周期顺序开发系统的过程。正向工 程实际上就是把一个系统高层抽象和独立于设计的逻辑实现转变成物理实现的过 程。 2 、再文档( r e d o c u m e n t a t i o n ) ：指在同一抽象层次上创建系统表示。由于种种 正向工程 7 止侧 止i 玎j 需求 l 设计 l 实现 设计恢复 设计恢复 一 ， f 厂 f 重构 再 i 重构 再t 程 i 厂、 f蠢 l 再工程 重 l 鳓 逆向1 _ 程 图2 1 逆向t 程及其相关过程 原因，现有的文档可能不够充分、正确和详细，因而源代码本身成了系统客观可 靠的信息源。再文档利用已有的源代码为软件系统逆向生成精确的文档，是软件 逆向工程最古老的类型之一。再文档所生成的文档通常是联机文本，但是，也可 以产生其它形式的文档，如超文本、交叉索引和图形视图等。 3 、结构化再文档( s t r u c t u r a lr e d o c u m e n t a t i o n ) ：用逆向工程重建系统总体结构 文档的过程称为“结构化再文档”。文档在程序理解中有着重要作用，但是，大多 数软件文档都是描述程序的算法和数据结构的小粒度( i n t h e s m a l l ) 文档，注重于刻 划系统的各个具体部分，很少描述系统的总体结构。对大型遗留系统而言，理解 系统的总体结构比理解单个算法更为重要。 4 、设计恢复( d e s i g nr e c o v e r y ) ：指结合对系统的观察和有用的外部信息f 如领 域知识1 标识更高层次的抽象表示。再文档和结构化再文档都是仅仅根据源代码生 成文档，因此有着内在的局限性。从设计角度能够更深入地理解系统，设计恢复 利用领域知识、外部信息( 如规约文档和设计文档) 、演绎和模糊推理得到深层抽象， 这种抽象的层次比直接检索系统所得的抽象层次更高。设计恢复能够产生完全理 解系统做什么、怎么做以及为什么做等所需要的信息，是提高软件构件可复用性 f r e u s a b i l i t y ) 的要途径。 5 、重构( r e s t r u c t u r i n g ) ：重构是在保持系统外部行为的前提下改变同一抽蒙层 次上的表示。重构的只是系统内部的结构，例如数据处理机制、程序算法等，而 系统的输入输出关系是不变化的，即相同的输入产生相同的输出。重构可以发生 在软件开发过程的任何阶段，包括需求分析阶段、设计阶段和实现阶段。 6 6 、再工程( r e e n g i n e e r i n g ) ：再工程通过逆向工程、重构和正向工程的结合把现 有系统重组为新的形式【1 8 l 。再工程可以是对整个软件开发过程进行再工程，也可 以是软件开发过程的局部进行再工程，例如，在设计阶段可以通过再工程重新作 需求分析，根据新的需求分析将设计翻新；在实现阶段可以通过再工程将系统重新 设计，以新的形式实现系统。 2 2 程序理解的重要性与定义 软件逆向工程是软件工程学中日益引起人们兴趣的一个领域。它是指分析目标 系统，标识目标系统组件及其相互关系，创建不同形式或更高抽象层次的系统表 示的过程。它的目标是理解软件系统以促进性能提高、纠错、建档、再设计或使 用另外一种语言重新编程| 】。 在f e l d s t a d 和h a m l e n 的报告中指出：在系统性能提高和纠错任务中，分别有 4 2 和6 2 的时间花在理解活动上。这些活动包括阅读文档，细读源代码和理解 将要对系统做的改变。所以不论是对目标系统进行概念建模、数据抽取还是系统 抽象，主要依赖于通过分析程序源代码来抽取程序结构和控制流信息。因此，程 序理解是软件逆向工程主要的实现手段和行为活动1 2 ，它贯穿整个软件逆向工程， 并且是决定软件逆向工程成败的关键。 通俗地讲，程序理解f 2 1 】就是通过一定的设施和方法来弄清楚一个程序是“做什 么的”以及“如何做的”。如果对它进行精确定义，可以把程序理解看作这样的任 务：以软件维护、升级和再工程为目的，在不同的抽象级别上建立基本软件的概 念模型( m e n t a lm o d e l s ) ，包括从代码本身的模型到基本应用领域的模型，即建立从 问题应用域到程序设计实现域的映射集，如图2 2 所示。 2 3 程序理解的任务 程序理解的任务2 2 就是要揭示程序的功能与实现机制，即理解系统的外部行为 和内部构造，其具体任务可分解如下： 映射集 图2 2 程序理解任务 1 、通过检查单个的程序设计结构，程序被典型地表示成抽象语法树、符号表 或普通源文本，这其中包括手工代码阅读，人工制品提取，程序分析，静态分析， 7 动态分析几个过程。 2 、尽量做到程序隐含信息的显性表示及程序内部关系的可视化。如控制流和 数据流分析，各种程序视图的构造等。 3 、从源代码中提取信息，并存放在通用的数据库中，然后通过查询语言对数 据库进行查询。 4 、检查程序构造过程中的结构关系，明确表示程序组成部分之间的依赖关系。 5 、识别程序的高层概念，如标准算法、数掘结构、语法及语义匹配等。 在进行程序理解时，如果程序具有良好的结构，那么理解任务会变得相对容 易一些，但是如果程序不具备良好的结构，程序员就必须对程序源代码进行更仔 细的分析，了解设计者是如何用程序解决各种问题的。因此程序设计人员在程序 设计阶段应该对程序所要解决的问题进行说明，这样做可以使设计者的想法对他 人保持开放，在以后解决软件运行和维护过程中出现的意外问题时，其他的程序 理解者或程序维护员可以更容易地掌握设计者的思想。但是并非所有的设计者在 编码前都会对要解决的问题进行详尽的分析，并对它们进行注释，这种注释说明 不够完整、不够详细时，对程序的分析会更复杂。 2 4 程序理解的方法 程序理解是把源程序抽象成便于理解的各种实体，常用的程序理解方法有：词 法分析、语法分析、程序依赖图和程序切片技术。 1 、词法分析 词法分析【2 3 2 6 1 的任务是对输入的字符串形式的源程序按顺序进行扫描，在扫描 的同时，根据源代码的词法规则识别具有独立意义的单词符号，并产生与其等价 的属性字流作为输出。通常属性字流即是对识别的单词给出的标记符号的集合。 2 、语法分析 语法分析1 2 3 - 2 6 1 就是按照语言既定的语法规则，对字符串形式的源程序进行预防 检查，并识别出相应的语法成分。它的处理依据就是语言的文法规则，其分析结 果是识别出的无语法错误的语法成分，可以用语法树的形式来表示。常用的语法 分析有两种，它们分别是自顶向下的分析技术和自底向上的分析技术。 自顶向下的分析技术从推导角度看是从推导符出发，试图构造一个推导，由它 推导出与输入符号串相同的符号串。自顶向下的识别过程是一个不断建立直接推 导的过程，每一步都是把句型中的某个非终结符号替换为相对于该非终结符号的 简单短语。从语法树角度看，自顶向下分析过程将以识别符号为根节点，试图向 下构造一个语法树，其末端结点符号串正好与输入符号串相同。通常有递归下降 分析技术和预测分析技术( l l ( 1 ) 方法) 。 自底向上的分析技术是从输入符号串出发，试图把它规约成识别符号。从语法 树的角度出发，自底向上的分析过程是将以输入符号串为语法树的末端结点符号 串，试图向着根结点方向往上构造语法树，使识别的符号正好是语法树的根结点。 基于自底向上分析技术对输入符号串进行语法分析的算法称为自底向上识别算 法。目前有多种实现自底向上分析技术的算法，如简单优先分析算法和特别适用 自动生成的l r ( k ) 分析方法。 论文采用l l ( 1 ) 预测分析方法进行t l 顶向下的语法分析。 3 、程序依赖图 程序依赖图用来表示程序中的模块、变量和函数之间依赖关系的视图。在这种 图中，节点表示程序的语句，边表示语句之间的依赖关系，主要的依赖关系是控 制依赖关系和数据依赖关系【2 ”。后来，程序依赖图被扩充成系统依赖图，使得被 分析的程序可以包含若干个程序调用。在系统依赖图中，有一个程序依赖图表示 主程序，然后每个程序依赖图表示程序中的每个过程调用。在系统依赖图中，在 处理过程间调用时，又定义了一些不同种类的边，这些边分别表示不同的依赖关 系。 4 、程序切片技术 程序切片是一种代码分析技术，它从语义的角度将程序进行分解，它能够根据 一个切片标准，识别源代码中影响已知点的变量值的所有语句1 2 7 1 。切片可以通过 静态方法进行：不需要关于执行的信息，也可以通过动态方法进行，通过执行该 应用程序。静态切片能够回答哪些语句可能能够影响变量的值，而动态切片能够 回答哪些语句的确影响了变量的值。因此，动态切片能够为应用提供更简化的切 片。但是，动态切片的获得依赖于某一特定的输入，因此不具备静态切片的普遍 性。 2 5 程序设计决策 2 5 1 设计决策的分类 设计决策是程序设计人员在程序设计阶段做出的一系列决策，这些设计决策把 解决方案分解成为若干片断，并指明这些片断是如何协同工作以解决问题并达到 最终的要求1 28 1 。因此很自然地，要在对代码设计决策的认知基础上建立软件逆向 工程的方法学，而且，对在软件逆向工程中被探测到的有关设计决策的信息所做 的表述，应该被构建为可以用于反映实现这些被探测到的设计决策的代码段之间 的相互关系。 程序理解基于对源代码设计决策的探测【2 9 】，设计决策和其组织方式是程序理解 所希望得到的结果。设计决策根据它们所能提供的抽象种类可以分为下面这几种： 1 、怎样将程序与问题进行合成与分解：程序是由几部分构成的，问题也被分 解成更小、更容易解决的子问题。代码中的模块以及数据结构反映了这种决策的 结果。 2 、组件设计为封装的还是插入的：各组件之间相互作用，如果这种作用是有 限的而且是通过明显的接口发生的，这些组件就被称为封装组件。但如果考虑到 效率的因素，如果两个或两个以上的格局( p l a n ) 是使用相同代码段或者用相同的数 9 据结构实现的，那么对应于这些格局的组件就被称为插入组件。 3 、组件设计为通用的还是专用的：经常有某些组件很相似，可以通过总结这 些相似组件的共性构造更高层次的参数化组件一类，把这些相似组件作为类的多 种实例添加其特有的某些属性后得以实现。在面向对象编程中，这个过程经常反 过来，即首先生成通用性的组件( 类) ，然后再把特例( 实例) 加上去。 4 、怎样描述解决方案：在从问题域到方案域的映射转变过程中，我们所做的 设计决策可以使程序组件成为某些应用域实铡的模型。如果考虑到效率，高层次 的编程结构可以用来描述成为其它更接近机器特性的结构，例如使用一个数组来 描述堆栈。诸如a d a 之类的编程语言正呈现出支持明确描述的特性，但是对使用 更旧的编程语言编写的程序的理解仍然需要对这些设计决策的探测。 5 、怎样通过设置变量来控制过程：程序是由控制结构组织而成的计算序列。 设置变量是存储以后将要用到的中间结果的常用解决方法，目的是为了避免重复 计算和简化计算表达式。对变量的注释是非常重要的设计决策，但很遗憾，这也 是最容易被忽视的，我们经常轻易地就忽略了加上适当的注释和设计思想。 6 、不确定的设计决策：在某些场合，软件工程师将决策如何表述输入与输出 参数之间关系。这一点在逻辑编程语言中特别突出，诸如p r o l o g 。一个表示高层 细节的简单的参数关系，能够产生取决于参数模型( 输入输出设计) 的可供选择的 功能。这种设计决策具有不确定性，但是它应该在条件允许的情况下，在设计阶 段的尽量早的时期彻底明确地做出。 2 5 2 假想设计决策与实际设计决策 c h i k o f s k y 和c r o s s 把程序理解定义为：通过分析一个目标系统、识别系统的 各个组件以及它们之间的关系，生成另外一种形式或者更高抽象层次的系统表示 的过程。通常，这意味着通过分析程序的源代码为系统建立一个再工程的框架设 计。为了便于理解，再工程的设计必须要建立在己有的软件设计基础之上。当然， 再工程的设计会反映软件工程师进行程序理解时的偏爱。 由于再工程的设计与原来的设计通常是有区别的，再工程的设计中必须要有设 计决策集把它与原来的设计对应起来。有时设计决策比较复杂也比较难辨认，同 步细化策略便是其中一个辨认这些设计决策的方法，它要求软件工程师假定一个 概念模型、一个假想的软件设计以及把它们联系起来的初始设计决策集。初始的 设计决策集在设计过程中被更新，以便记录实际代码的特殊复杂性( e x t r a c o m p l e x i t y ) 。由于特殊复杂性，理解实际软件结构的大部分工作都花在解决实际 设计决策与假想设计决策的矛盾上。一旦把这个矛盾解决了，软件工程师就有两 套设计决策集了，一套对应概念模型和实际代码，另一套对应概念模型和再工程 设计。 在对实际系统的程序分析过程中，有以下几种方法来解决假想设计决策和实际 设计决策的矛盾： 1 、更新假想概念模型，条件是程序所表现出来的外部行为与假想概念模型所 期望得到的外部行为之间存在重大差异。 2 、更新程序文本，条件是发现了实际设计决策的错误，必须在分析完成前纠 正这样的错误。 3 、拒绝假想设计决策，条件是假想设计决策所支持的外部行为和程序支持的 外部行为虽然相同，但是其实现方法不同，不同方法所产生的差异会与其它己经 被接受的设汁决策产生矛盾，即这个假想设计决策对其它设计决策会产生影响。 4 、接受假想设计决策，条件是假想设计决策所支持的外部行为和程序支持的 外部行为相同，其实现方法也相同，或者虽然实现方法不相同，但是不同方法所 产生的差异被其它设计决策所掩盖，即这个假想设计决策对其它设计决策不会产 生影响。在评估假想设计决策以及解决设计决策矛盾的过程中，软件工程师经常 要跟踪数据流程和控制流程，目的是为了寻找丢失的或隐藏的数据、操作以及数 据结构。由于特定的被分析的设计决策的注释通常不是丢失了，而仅仅是被其它 设计决策隐藏了起来，所以跟踪数据流程和控制流程需要对源代码进行仔细的、 有工具支持的分析。 另外，在解决设计决策冲突时，软件工程师应该能回退( r e g r e s s i o n ) 并能改变原 来的假想设计决策。回退不仅与被分析的设计决策有关，还与生成假想设计决策 的设计决策有关。满足回退要求的最直接的方法就是建立目志( 1 0 9 ) ，日志记录每 一天中的所有操作，在结束一天的操作之后，将其中关键的若干环节记录存档， 其余不重要的中问环节可以删除，这样做既保证能够回退，又不会占用太多的存 储空间。 2 6 解析程序设计决策 2 6 1 解析设计决策的过程 假想设计决策是用假想的概念模型生成的个理想化的设计，另外，代码层 分析通过解析实际设计决策对源代码进行简化和抽象。为了对代码的结构进行彻 底的分析，我们经常要从程序文本中提取大量的数据并对之进行处理。例如，如 果假想设计决策把系统分割成许多顺序执行的简单的功能函数，这其中包括异常 处理函数，代码层分析就要验证这些设计决策然后用更详细的描述来代替它。代 码层分析把正常的执行路径与那些带有异常情况的执行路径分开，另外，它还更 新实际设计决策的结构来与假想设计决策相对应，用的方法是重新安排程序的定 义部分。 无论是代码层分析还是推导假想设计决策，软件工程师都必须有很相当广泛的 各种领域的知识，为的是更好地解析程序设计决策。 设计决策可以分为高层设计决策和低层设计决策，高层设计决策构造整个系统 的结构，并且规划各模块之间的联系机制。而低层设计决策则构造模块内部的数 据表示和控制结构【3 0 1 。 2 6 2 解析高层设计决策 高层设计决策会影响整个程序的控制机制，这个设计决策最重要的作用是描 述整个系统的结构，结构中可能包含操作顺序、内存管理、访问控制以及数据表 示等。原来系统的程序控制机制是由编程语言的原语以及运行环境提供的，运行 环境包括编程语言的运行环境和操作系统。框架机制则对这些程序控制机制进行 补充，在复杂的系统中，附加的程序控制是通过定制的运行在应用系统上的代码 或者预定义的运行环境内的代码实现的。 通常使用中间层的设计语言，例如伪代码，来表示一个简单的程序控制模型。 在这个模型中，程序的控制机制实际上是应用系统自己决定的，并且是以低层服 务的形式出现的。通过对程序控制描述的抽象使软件模型更加清晰，并把应用层 的程序控制逻辑隐藏起来。 在解析软件结构中的主程序控制机制时，应该首先对整个系统作模块分析，将 系统分割成若干互相联系的模块，然后找出模块之问的联系线索。这里用实时控 制程序来说明这一点：大多数的实时控制程序都是用控制结构和数据结构相结合 的综合机制来支持系统行为的，通常一个实时控制程序为若干个中断源提供中断 服务，并且提供了调度这些中断服务的算法，这些中断服务程序和调度算法在其 它的运行环境下是不一定能够实现的，它们通过程序中包括异常处理、继承、动 态内存管理、垃圾自动收集以及结构共享等线索联系起来。比如，在系统自检子 程序中，常用各种方法束支持j 顿序执行。当系统自检到某一处发现错误时，系统 不是马上发出警告，而是将这个错误信息按照一定的格式插入到内存中的等待队 列中去排队等待执行，并且设置控制开关或标志a g ) 的值汜录系统状态，程序 继续按顺序执行下去直至自检子程序执行完毕然后根据控制开关或标志量的值 来控制程序其它任务或过程的流程。 一般说来，在系统设计时，划分模块都遵守信息隐藏( i n f o r m a t i o nh i d i n g ) 的原 则p ”，即模块内部的数据与过程对不需要了解这些数据与过程的模块来说是隐藏 起来的。这一点在表示解析所得到的高层设计决策时一定要注意。另外，广义性 ( g e n e r a l i z a t i o n ) 对表示主程序控制机制也起着非常重要的作用。例如，在结构化良 好的程序中，一些过程和任务是通过数据藕合的方式相互作用的，但低层设计决 策在如何通过常数和控制藕合来模拟数据藕