（计算机软件与理论专业论文）基于关系数据库的程序逆向分析架构研究.pdf

摘要 逆向工程从可运行的程序系统出发，生成对应的源程序、系统结构以及相关设计原 理和算法思想的文档等。它具有重大现实意义和经济价值，不但可以避免重复劳动，提 高软件生产的效率和质量，而且可以将大量的遗产系统转化为易演化系统，从而充分有 效地利用这些有用资产。虽然近年对软件逆向工程的研究己有不少，但是它仍然属于一 个未充分发展的领域，并未形成统一的标准、方法和过程，因此很有必要进行深入研究。 逆向工程适用于软件生存周期的各个阶段和各种抽象层次，包括需求、设计和实现。 它可用于低级的抽象层次，例如把程序二进制代码转换为源代码。但主要用于将程序源 代码转换为更高抽象层次的表示，如控制流图、数据流图和类关系图等。 一般将逆向工程定义为包含两个步骤的过程：第一步分析目标系统，标识系统对象 及其关系；第二步创建不同形式或更高抽象层次的系统表示。 本文从理论、方法和应用三方面对软件逆向工程中的若干问题进行了研究，着眼于 探索逆向工程中信息收集、信息抽取和信息抽象表示的理论和方法，探讨基于关系数据 库的程序逆向分析架构的设计。 本文的主要工作包括： 1 介绍逆向工程的定义、相关概念，以及现有的一些逆向工程工具，综述了逆向工 程分析技术的研究进展。 2 提出了一种基于关系数据库的程序逆向分析架构。架构以关系模型理论为基础， 将程序语言中的各种组件看作一个个各自独立并与其它组件有联系的实体，并采用将实 体间关系包含在其属性中的方法，用关系数据库存储程序信息。在架构上应用程序理解 和分析技术从扩展的源程序中提取程序信息，将信息存储于关系数据库中，并开发数据 库应用程序对信息进行说明或可视化地显示，从而帮助用户快速地理解软件。 3 以c 语言源程序的逆向分析为例，对架构设计作了相应诠释。 关键词：逆向工程；程序理解；遗产系统：再工程；关系模型 a b s t r a c t r e v e r e n g i i l e e r i l 培s t a r t s 埘t ht h ee x e c u t a b l ep m g 舢s y s t e m s ，a n dg 鼬t e st l l e u r c c c o d e ，t h e 咖t u r eo fs y s t c m ，a n dt h ed o c 啪e n t so f c o n _ e l a t i v ed e s i g nt t l e o r i e sa n da l g o r i t l l l i l s r e v e r 辩e n g i n c e r i i l gh 鸽g r e a lp r a c t i c a l 锄de c o m i cv a l u c hc a nn o to i l l ya v o i dr c d u p l i c a t c l a b o ra l l di m p m v ee 衔c i e n c y 锄dq u a l i t yo f f h 硼聆p 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 i i t ot h es y s t e n l st l l a tc 越b ce v o l v c de 鹋i l y mo r d e rt 0u t n i z ct h e s el l s e f i l l r e s o l l r c ea d e q 峨l y a l t l l o u g ht h e r eh 私b e e nm u c hr c s e a r c ho nr e v e r e n g i n e c r i n gi i lr e c e m y e a r s ，r c v e r e n g i n e e r i i l gi ss t i l lag r c a n yu r i d e v e l o p e df i e l d t h el l i l i f o m ls t 锄捌，m e t l l o d a n dp l o c e s sh a v e n 、b e e ng 咖翰t e dy e t t h l 珥，i ti sn e c e s s a r yt o 他a r c h t l l et c c l l l l i q u eo f r e v e f s ee n 酉袱r i n gd e 印l y r e v e r 辩肋g i n e 响gi sa p p l i c a b l et ot h ev a r i o l l ss t a g c so ft h es o f h r el i f ec y d e 孤d v 撕o u sa b s 自吼c tl e v e l s ，i n c l u d i i l gd e m a n d ，d e s i g n 肌di l l l p i e r l l e n l 孤i o n i tc a nb eu 骶dt om e i o w e rl e v e lo fa b s n 砸i o l l ，s u c h 硒p u tt l l eb i n a r yc o d em t 0s o u r c cc o d e b u tf b rt l l es o u r c e c o d ew i l lb ec o n w ! n e di 1 1 _ t 0ak g l l e rl e v e lo fa b s t m c tl e v e l ，s u c h 嬲c o n t r o ln o w 鲫h d a t a n o w d i a g m m 觚dc l 勰sr e l a t i o i l s h j p s 掣a p i l r 删e r 西n e e r i l l gi sg e 毗r a l l yd e f i n e d 嬲m ep r o c e s sc o n s i s t so f 佃os t e p s ：f i r s t ，觚a ：l y s i s o ft l l et a r g e ts y 蛳釉锄d 瓤n gs y s t e mo b j e c ta n dt h e i rr c l a t i o n s h i p t h es c c o n dc 疵a l l i g h c r1 e v e lo f a b s 仃a c t i o no rd i 丘b r e i l tf o m ss y s t e m b lt l l i st 1 1 e s i st h e 瓤i n l o rl u c u b 船t e so ns e v e m lp r o b l e m so ft h et e c h i l i q u e so f v e r 辩 锄舀n e e r i n gt l l m u g ht h e 硒p e c t so ft l l c o r y ，m c n l o d 柚d 印p l i c a t i o n e m p h 船i 瑚t l l es t i l d yo f t l l ei n f o n n a l i o nc o u e c t i o n i i d - o n m t i o nc 】( t 阳c t i o na n dt h ea b s l m c ts a i do fi n f b n t i i i it t l e f i e l do f r e v e r 辩e i l g i i l e c f i n g ，觚dt h ed e s i 印o f af h r m w o r ko f p r o 蓼锄f e v e r 辩a 1 1 a l y s i sb a s c d o nr e l a t i o n a ld a t 臼l b a s e t l l i sp a p e rf i r s ti n l d u c e st h ec o n c e 埘o no f 佗v e t e n g i n r i l l ga n ds 伽e 由o o l s 璐c di n “ a n dt h ed e v e l o p m 雌to f r e v e 瑙ee n g i n e e r i n gi sa l s od i s c u s s c di nt l l ep a p e r a p r o g m mr c v e r 姐a l y s i s 觑i m e w o r kb 嬲e d r e l a t i o n a ld a 舾b 觞ei sp r e s e m e di i lm i s p l p 既t h e 丘锄e w o r ki sb 嬲e do nt h et l l c o 哆o fr e l a t i o i l a lm o d e l 锄dt a ：k e se hc o m p o m m i n p r o g 舢l 觚g u a g e s 嬲as 印撇t e d 铷t i t yw h i c hh 嬲r e l a t i o 璐、i t ho 惭c o m p o n e n t s i i lt t l em m l e w 诎，t h ei n f o 咖a t i o ni ss t o r e di nf o m lo f 陀l a t i o n a l 加b a b y 蛐g r c l a t i o n sb t 出v 咖e n t m e si 1 1 _ t oi t s 砌b u t e s t h m u g ht h el l s eo fm e 鼬e w o 咄t h ep r o 母卸咀 i i l f o m l a t i o ni sr e t r i e v e d 舶mt h ee x t c l l d e ds o u r c ep r o 掣锄b yt l l et c c l l l l o l o g yo fp r o 孕狮 u n 出嬲t a n d i l l ga i l da l l a l y z i i 坞，a n di ss t o r e di i lar e l a t i o i l a l 出l 诅b a ，t h e ni ss h o w e d “s u a l l yb y d a t a _ b a s ca p p l i c a t i o n ，w l l i c hh e l p s 自s t 哪d e r s t 柚d i n go f s o f a tt b ee n d ，t h ep a p e rd e s c r i b e st h e 丘a i i l e w o r kc a r e m i l y ，t a _ k i n gs o u r c ep r o g m m so fc l 锄g u a g e 雒缸c x 枷p l e k e yw o r d s ：r e v e r e n g i n e e r i n g ；p r 0 掣锄c o m p r e h e l l s i o n ；l e 群虻ys y s t 锄；r o e n g i i l e e r i l l g ； r e l a t i o n a lm o d e l i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：盔寝日期：协卵年午月加日 j|扩l 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：马棼日期：沙7 年争月b 日 导师签名： 够f 纱 日期：乒彳年印月加日 ， 1 1 研究背景 第一章前言 逆向工程( r e v e r s ee n g i n e e r i n g ) 的概念起源于硬件领域，逆向工程是对产品 设计过程的一种描述。在工程技术人员的一般概念中，产品设计过程是一个从无 到有的过程，即设计人员首先在大脑中构思产品的外形、性能和大致的技术参数 等，然后通过绘制图纸建立产品的三维数字化模型，最终将这个模型转入到制造 流程中，完成产品的整个设计制造周期。这样的产品设计过程我们称为“正向设 计”过程。逆向工程产品设计可以认为是一个“从有到无”的过程。简单地说， 逆向工程产品设计就是根据已经存在的产品模型，反向推出产品设计数据( 包括 设计图纸或数字模型) 的过程，从这个意义上说，逆向工程在工业设计中的应用 已经很久了。近年来，随着计算机技术的广泛应用，逆向工程技术也开始应用在 软件开发领域。在软件领域中，逆向工程就是分析目标系统，认定系统的构件及 其交互关系，同时以抽象为原则，采用其他形式如文档、图形或数据库等对系统 进行表示。就软件领域逆向工程的现状而言，逆向工程一般是对已有软件系统的 源代码进行分析，以获得系统设计层次上的理解。随着从头开发软件的减少，利 用现有的系统就相应地增多，因此逆向工程成为软件工程的研究热点之一。 1 2 研究意义 软件逆向工程( s o f t w a r er e v e r s ee n g i n e e r i n g ) 是软件科学和计算机科学的一 个分支，这门学科综合了编译反编译，加密解密，系统分析，程序理解等多种 计算机技术于一身，从可运行的程序系统或遗产系统出发，通过逆向工程生成对 应的源程序、系统结构以及相关的设计原理和算法思想的文档等【l l 。由于以下几 个方面的主要原因，它已成为国家自然科学学科发展战略确定的优先发展的计算 机软件技术之一： 1 由于目前的软件生产技术还没有达到人们所期望的程度，每一次都从头 开始开发软件已经不再能够适应社会对软件需求的不断增长【2 】。为了避免重复的 劳动，充分利用现有软件系统，通过提高现有软件产品的利用率，来提高软件的 生产效率和质量，缓解软件危机，这就必须要充分利用和改造现有的软件，对现 有的软件在充分理解的基础上进行再设计、再工程，使得软件功能得到大幅度提 高以满足用户的需要，软件理解( s o r w a r eu n d e r s t a n d i n g ) 、再设计( r e d e s i g n ) 和再 工程( r e e n g i n e e r i n g ) 都是逆向工程的形式之一，再工程是在现有系统的基础上， 经过修改、重组组装成新的形式，以达到再利用的目的i 1 。 2 目前运行的许多系统由于某些原因，例如其运行环境的改变，或者是根 据业务的需要对其功能进行添加或调整，导致他们必须进行演化后才能继续使 用，这些系统在经历了多年的运行维护之后，包含了许多的知识：如系统需求、 实际决策和业务规则等，这些知识可以看作是系统的遗产，也因此被称为遗产系 统( l e g a c ys y s t e m ) 。通过软件的逆向工程将这些遗产系统转化为易于演化的系统 【s 】，是充分有效地利用这些有用资产的良好途径，逆向工程可以使我们由遗产系 统完整可靠的程序源代码出发，导出其他不同形式的信息【6 1 。 3 现今的商业社会把软件科学纳入了一种相对封闭的范畴，为了追求最大 的利润，一些软件业的霸主试图进行知识的垄断，它的直接体现就是鼓励普通用 户和大多数程序员把软件看作“黑箱”一一一个不用你关心里面的代码组织结构， 只需要知道输入输出，把软件的生产变成类似车间加工的一道道工序。很多现 代软件工程技术，诸如0 0 p ( 0 b j e c t0 r i e n t e dp r o g r a m m i n g ，面向对象的程序设计) 等都有类似的思想。当然都有其合理之处，但却隔断了人们深入研究软件科学的 通路。e r i cs r a y m o n d 在评述微软内部对付丌源软件( o p e ns o u r c es o f t w a r e ) 的万 圣节备忘录一文中曾经这样说道：“好的程式设计者知道如何写程序，伟大的程 序设计者知道如何重写( 或再利用) m ”。而作为开放源代码的前期工程，逆向工程 对整个开放源代码工程有着至关重要的作用，因此利用逆向工程技术破解软件， 对于打破软件垄断，特别是对于我国繁荣民族软件有着至关重要的意义。 软件的逆向工程方面还是属于相当不成熟的领域，理论和实践的研究都还处 于早期的探索研究阶段，这是因为一方面逆向工程本身的技术特点导致其存在重 重困难，另一方面逆向工程受到法律的严格限制，目的是保护知识产权。因此在 法律允许的范围内，很有必要对以再利用为目的的逆向工程的理论和方法进行深 入的研究。 在国内，由于遗产系统还不够多，而且对软件的后期维护还不太重视，所以 对逆向工程的研究也比较少。北京大学以杨芙清院士为首开发的“青鸟软件生产 线系统”中的青鸟逆向工程工具是其中一项实质性的成果【l l 。但是仅有这一项成 果是远远满足不了逆向工程的需要的，很显然，遗产系统的多样性和逆向工程形 式的多样性使得这项成果并非对所有的逆向工程均可以提供有效的支持，因此对 逆向工程的深入研究仍具有实际意义，尤其是对系统化的、科学化的逆向工程的 理论和方法的研究。 1 3 国内外研究现状 无论是在国内还是国外，对逆向工程的研究都已经有十几年的时白j 了，虽然 已经形成了一定的研究规模，也发表了不少的研究文献，但是逆向工程仍然属于 相当不成熟的领域，这主要表现在对理论和实践的研究都还处于早期的探究阶 2 段，并未形成统一的、系统化的、科学化的逆向工程的理论和方法。逆向工程最 早是在国外作为软件维护的一部分出现的。c m us e i 成立了专门的再工程中心， 致力于通过逆向工程进行程序理解技术的标识、增强和实践推广。c h i k o f s k y 等 人于1 9 9 3 年发起的逆向工程会议每年举行一次，研究和讨论逆向工程的问题、技 术及其支持工具【9 】。大量的研究成果都集中在程序理解的辅助工具上，例如，i b m 日本研究员研制的基于知识的代码理解工具p r o m p t e r 、美国y a i e 大学计算机系 研制的对p a s c a l 语言进行联机分析和理解的工具p r o u s t 、意大利的g a n t o n i o l 等人1 9 9 6 年推出的代码和结构分析工具一一c a n t o 等。 目前逆向工程分析技术主要分为两类：静态分析和动态分析【l o j 。静态分析技 术一直是编译技术的核心，编译器优化是标准的静态分析。对目标系统的静态分 析不必运行系统，所以分析可以进行得比较早，甚至在系统的开发阶段就可以开 始。静态分析技术发展至今，主要有以下几类】： 1 词法分析和语法分析 该方法直接对程序源码进行分析，已经发展得比较成熟。通过词法分析可以 得到程序信息的多种有用表示，其中最常用的是交叉引用列表。另外，借助词法 分析还可以建立软件复杂度测量的标准。通过语法分析可以得到两类表示：分析 树( p a r s et r e e ) 和抽象语法树a s t ( a b s t r a c ts y n t a ) 【t r e e ) 。其中，分析树只是指导分 析过程，是比较原始的结果。分析树显示了程序语句的分解过程，包含和程序的 实际含义无关的信息，去除分析树的无关信息后得到a s t ，a s t 只包含和程序 实际内容相关的细节，是更复杂的程序分析工具的基础。 2 图形化方法 图形化方法包括控制流分析、数据流分析以及程序依赖图。 ( 1 ) 控制流分析对执行语句的若干可执行路径进行分析，确定程序的控制结 构，建立控制流图。 ( 2 ) 数据流分析是在不执行程序的情况下，收集程序数据的运行时信息，分 析程序中数据对象之间的关系。数据流分析关注程序中的数据使用、定义及依赖 关系，对确定系统的逻辑构件及其交互关系很重要。 ( 3 ) 程序依赖图是数据流分析的进一步改进，比数据流分析更复杂。在程序 依赖图中，节点表示语句和谓词表达式( 或运算符和操作数) ，边表示该节点的操 作所依赖的数据值和控制条件。程序依赖图将控制流和数据流放在一起处理，清 楚地描述了程序中每个操作的数据依赖和控制依赖。如果同时需要控制流图和数 据流图的相关信息，使用程序依赖图就很方便。 3 静态切片 切片技术是将程序简化为和某个特殊计算相关的语句的技术，来源于数据流 分析方法。切片技术自动将程序分解为较小的称为切片的代码段，使关注点确定 在一个较小范围而不必关注整个程序。一个程序切片是“影响”指定值的程序语 句和判定表达式组成的集合，包含捕获程序行为子集的原来程序的一部分。为了 计算切片必须知道程序中语句之间的依赖关系，这种依赖关系可以通过分析数据 流和控制流自动从源程序中得到。切片技术可大致分为两类：静态切片和动态切 片。静态切片被定义为“可能影响”一个值的所有语句，其相关计算只利用静态 获得的信息，并且是从切片的标准开始，以向后遍历的方式收集语句和控制谓词。 在静态切片的实际计算中可以根据控制流和数据流依赖对间接相关的语句进行 分析，也可以借助于程序依赖图或信息流关系等方式。 4 抽象解释 抽象解释是对程序语言的语义形式上构建一个保守的近似，用基于语义的分 析来确定程序的动态属性。和程序的语法属性可以用b n f 范式表达类似，程序 的语义属性可由一种数学方法一一指称语义( d e n o t a t i o n a ls e m a n t i c s ) 来描述。在指 称语义中，程序的含义用多种称为语义域的数据类型来表示。例如，程序的变量 和值之间的绑定状态由一种类表域表示。基于原始的语义域来定义替换函数，借 助这种方法可以进行静态分析。例如，如果要确定指定变量的值是否被子程序改 变，不必去关心变量可能取的值，可以为变量的赋值语句解释语义函数，只用一 个简单的布尔变量就可以标识变量是否改变，这种再解释的过程就是抽象解释。 动态分析是数据的聚集、压缩和抽象的过程，用于理解系统的运行时行为。 静态分析是在不执行目标系统的情况下对程序源代码进行分析，动态分析则是通 过目标系统的一次或多次运行进行分析m i 。动态分析可以收集到解决某个问题必 需的信息。许多和执行相关的，如内存管理、代码使用及执行效率等软件性能对 全面评估一个软件系统至关重要。这些性能只有在分析软件的动态行为时才可以 发现，在静态分析时则不可见。动态分析技术主要有以下几类： 1 植入技术 程序植入是为了收集程序的运行时信息而修改当前程序的技术【1 3 】。基本的程 序植入技术是以不影响原有程序的语义为前提，在程序的关注位置插入代码。当 植入后的新系统运行时，这些代码可以按照特定协议将动态信息传递到指定位置 或转交给动态信息收集机制，从而提供调试信息、性能分析信息或对象之间的消 息传递信息。程序植入是获取目标系统运行时信息最常用的方式。植入可以在不 同的抽象层次进行，例如硬件级、库级、源代码级和机器指令级。 2 部分求值 大型实时系统具有复杂的状态机体系结构，会引用大量全局变量和嵌套的条 件语句。从整体上分析这类系统会很繁杂，而且效果不会太好，可以只针对系统 的某些特殊行为进行分析。部分求值p e ( p a r “a le v a l u a t i o n ) 技术有助于进行该类 大型系统的分析。p e 是一种程序转换，根据给定的不同运行参数选项，将大型 4 系统分成较小的部分进行分析。p e 的基本过程分为两步：根据部分已知的输入 数据，进行与其相关的计算，优化控制流，通过程序转换，将计算结果变换成程 序代码，生成例化的程序；运行例化的滞留程序( r e s i d u “p r o g r a m ) 完成其余计算。 3 动态切片 动态切片技术使用的是动态的数据流和控制流分析方法，程序的语句问依赖 关系是在以特定数据为输入的程序执行后确定的1 1 4 j 。一个动态切片可看作是删除 原来程序的零个或多个语句得到的可执行程序，包括了“确实影响”一个值的所 有语句，是静态切片的子集。动态切片的确定和程序执行历史相关。利用了程序 特殊执行的信息，只考虑程序特殊执行中存在的依赖。 逆向工程技术发展至今，商业领域和学术研究领域都已经研制开发出许多工 具。在过去的研究中，大部分工具对静态逆向的支持更成熟一些。下面介绍一些 典型的逆向工程工具l ： 1 r i g i r i g i 是一个交互式的可视化工具，帮助理解和再文档软件系统。该工具主要 由三部分构成：静态信息解析器、静态信息库以及交互式窗口图形编辑器。r i g i 提供了一个可扩展、可裁剪的逆向工程环境，采用半自动的工具从软件表示中提 取数据信息，将信息存入低层库，将目标系统抽象为子系统的分层结构。r i g i 可以与一种支持面向对象动态建模的环境s c e d 协同使用，分别得出目标系统源 程序的静态信息和动态信息。还可以与p b s ( p o r t a b l eb o o k s h e l f ) 和d a l i 工具集联 合使用。 2 i s v i s 这种工具的功能包括：读入源程序文件，解析后产生静态信息文件；利用源 代码、静态信息文件以及用户提供的相关的信息，产生获取动态信息所需的代码； 执行植入上述代码后的目标系统，产生动态事件跟踪信息，并自动转变成剧情； 用户通过所产生的剧情视图进行交互式分析。 3 r a t i o n a lr o s e r o s er e a l t i m e r o s e a r c h i t e c t r o s e i b 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 c mc a i i f o m i a ) 与r a t i o n a l 合作开发的一种可视化工 具。用于对u m l 类图中的实体进行基于规则的等价合并，突出地呈现系统的软 件体系结构成份。 4 i m a g i x 4 d 一个c c + + 程序的静态理解工具，它可以提供多层次的视图，以表示从高 层设计到实现的细节、类和函数的依赖关系等。l m a g i x 4 d 以二维图形的形式展 示关键信息，使得用户的注意力集中在回答特定问题的视图上。i m a g i x 4 d 提供 了产生大量视图的能力以及从源代码生成文档的能力。它提供的交互式询问功能 对迅速理解程序很有帮助。 5 青鸟程序理解系统j b p a s j b p a s ( 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 ) 系统一一 的组成部分【。】。该系统是北京大学以杨芙清院士为首开发的“青鸟软件生产线系 统”中的青鸟逆向工程工具中的一项实质性的成果，它针对c + + 语言，采用增量 分析技术对程序源代码进行静态分析：用e e r ( e n h a n c e de n t i t y r e l a t i o n s h i p ) 为 c + + 程序建立概念模型并抽取程序信息，将信息保存在数据库中，按照不同的用 户需求组织程序信息，辅助用户理解c + + 程序，逆向生成源程序的0 0 d ( o b i e c t o r i e n t e dd e s i g n ) 文档和r o s e 文档( 但实际所需的时间很长，对于l o 万行源 代码的程序，大约需要6 小时) 。该系统中的面向对象测试支持工具 ( o b j e c t 0 r i e n t e dt e s t i n gs u p p o r t e r ) 能够利用插装技术跟踪程序的运行，以辅助测 试用例的生成。 1 4 研究的主要内容 逆向工程通过分析目标系统，标识目标系统中的组件以及它们之间的相互关 系，达到创建不同形式或更高抽象层次的系统表示的目的。从源程序出发，由源 代码求详细设计与总体设计，由总体设计求软件需求分析，逆向生成对应的系统 结构以及相关设计原理和算法思想的文档等1 1 6 l 。它包含两项主要的工作，一项是 从可运行的程序系统出发，逆向生成对应的源程序；另一项是从源程序出发，逆 向生成对应的系统结构以及相关设计原理和算法思想的文档等。因此，本文的研 究着眼于探索逆向工程中信息收集、信息抽取和信息抽象表示的理论和方法，探 讨基于关系数据库的程序逆向分析架构的设计，结合关系数据库理论提出一种基 于关系数据库的程序逆向分析架构，并以c 语言程序逆向分析为例对基于关系数 据库的逆向分析架构的设计作了相应诠释。由此确定本文的研究内容如下： 1 抽取系统信息 逆向工程涉及对遗产系统的理解，在很多情况下，遗产系统完整可靠的信息 是其源程序代码，其它信息必须由此导出，程序理解的目的在于获取足够的系统 信息以便于创建系统的表示”。因此，程序理解是逆向工程中的关键技术之一。 本文采用了定制的词法分析器以及利用y a c c ( y e ta n t h e rc o m p i l e r c o m p i l e r ) 生 成的语法分析器静态分析源代码。其中抽取的系统信息具体包括函数、语句、表 达式、变量、常量等，如抽取出的函数信息包括函数名，函数参数，函数返回值 类型等信息。 6 2 知识组织 在逆向工程过程中，会使用到很多数据，同时也会产生很多数据，对于这些 数据必须用适当的数据模型保存起来，以便实现有效的存储和检索，辅助对系统 组件及其相互关系的分析，并反映用户对系统特性的了解程度【1 6 1 。早期的软件分 析系统的数据结构大多数建立在一些表格上，在本文中采取一种将实体间关系包 含在其属性中的方法以关系数据库存储程序信息，这样做允许利用关系数据库提 供强大的查询语言，对数据进行存取，支持对数据的共享，从而能够提高工具的 效率。 3 系统信息应用 系统信息应用部分实现对原程序信息的多种应用。如对系统信息实现可视化 表示，通过对程序理解所获取知识的遍历、分析，创建包括数据流图、程序结构 图等多种视图来表现分析结果，达到对目标系统理解的目的l 。 1 5 论文结构 本文的主要结构如下：第一章前言。对研究背景、研究意义做了简要阐述， 结合国内外研究的现状，介绍了现今已有的逆向工程工具并对本文的研究内容进 行了概要说明。第二章逆向工程概述。对逆向工程及其相关概念进行了介绍，说 明了逆向工程的三个规范活动，介绍了逆向工程中的难点与重点一一程序理解。 同时还介绍了开发逆向工程辅助工具的原则，指出了开发自动化逆向工程工具存 在的困难，及未来逆向工程辅助工具开发的方向。第三章基于关系数据库的程序 逆向分析架构的设计。提出了一种基于关系数据库的逆向分析架构，并介绍了各 模块功能。第四章c 语言程序逆向分析。以c 语言程序的逆向分析为例对该架 构的设计步骤作了相应的诠释。 1 6 小结 本章对逆向工程的研究背景及研究意义进行了阐述，并介绍了国内外的研究 现状和现有的部分逆向工程工具。本章后半部分对研究的内容进行了简要的说 明，同时介绍了本论文的结构。 7 第二章逆向工程概述 2 1 逆向工程的定义及相关概念 逆向工程( r e v e r s ee n g i n e e r i n g ) 来自于硬件领域，是通过检查样品来开发复 杂硬件系统规约的过程，主要为了商业或军事利益而分析研究他人的硬件系统， 发现其工作原理，以达到复制硬件系统的目的1 2 0 l 。随着软件业的发展，逆向工程 这一术语被引入软件工程领域，逆向工程可以用于描述揭示已有系统工作原理的 过程，或者是用于描述创建现有文档的联机文档的过程等应用【2 l 】f 2 z j 。当然逆向工 程还适用于软件的其它领域，比如图像滤波、自由曲面建模等。 在软件工程领域中，迄今为止还没有做出关于逆向工程的标准定义。一般将 逆向工程定义包含两个步骤的过程：第一步分析目标系统，标识目标系统中的对 象以及它们之间相互关系，第二步创建不同形式或更高抽象层次的系统表示。 s c o t tr t i l l e y 将两个步骤进一步精化为建模、抽取和抽象三个步骤】。 1 建模( m o d e l ) ：采用概念建模技术构造应用程序的领域模型。 2 抽取( e x t r a c t ) ：利用适当的抽取机制从目标系统中收集原始数据。 3 抽象( a b s t t a c t ) ：对目标系统进行抽象，以辅助系统理解并允许浏览、分 析和表示抽象结果。 逆向工程适用于软件生命周期的各个阶段和各个抽象层次，包括需求、设计 和实现l 。逆向工程可以用于较低级的抽象层次，例如把可执行程序转换为源代 码，但主要是用于将源代码转换为更高抽象层次上的表示，如控制图、数据流图 和类关系图等l z t l 。 下面列举的是与逆向工程联系紧密的几个术语1 4 l ： 1 正向 二程( 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 m a t i o n ) 指在同一抽象层次上创建系统表示。由于种种原因，现有的文档可能不够充 分、正确和详细，因而源代码本身成了系统客观可靠的信息源。再文档利用己有 的源代码为软件系统逆向生成精确的文档，是逆向工程最古老的类型之一。再文 档所生成的文档通常是联机文本，但是，也可以产生其它形式的文档，如超文本， 交叉索引和图形视图等。 3 结构化再文档( s t r i l c t u r a lr e d o c u m e n t a t i o n ) 8 用逆向工程重建系统总体结构文档的过程称为“结构化再文档”。文档在程 序理解中有着重要作用，但是，大多数软件文档都是描述程序的算法和数据结构 的小粒度( i n t h e s m a l l ) 文档。注重于刻画系统的各个具体部分，很少描述系统的 总体结构。对大型遗产系统而言，理解系统的总体结构比理解单个算法更为重要。 4 设计恢复( d e s i g nr e c o v e r y ) 设计恢复是指结合对系统的观察和有用的外部信息( 如领域知识) 标识更高 层次的抽象表示。再文档和结构化都是仅仅根据源代码生成文档，因此有着内在 的局限性。设计恢复利用领域知识、外部信息( 如规约文档和设计文档) 、演绎和 模糊推理得到深层抽象，这种抽象的层次比直接检索系统所得的抽象层次更高， 能够更深入地从设计角度理解系统。设计恢复能够产生完全理解系统做什么、怎 么做以及为什么做等所需要的信息，是提高软件构件可复用性( r e u s a b i l i t y ) 的主 要途径。 5 重构( r e s t r u c t u “n g ) 重构是在保持系统外部行为的前提下改变同一抽象层次上的表示。重构的只 是系统内部的结构，例如数据处理机制、程序算法等，而系统的输入、输出关系 是不变化的，即相同的输入产生相同的输出。重构可以发生在软件开发过程的任 何阶段，包括需求分析阶段、设计阶段和实现阶段。 6 再工程( r e e n g i n e e r i n g ) 再工程通过逆向工程、重构和正向工程的结合把现有系统重组为新的形式 ( 2 7 】。再工程可以是对整个软件开发过程进行再工程，也可以是对软件开发过程的 局部进行再工程。例如，在设计阶段可以通过再工程重新做需求分析，根据新的 需求分析将设计翻新；在实现阶段可以通过再工程将系统重新设计，以新的形式 实现系 再 工 程 图2 1 逆向上程与其相丈过程的关系 9 2 2 逆向工程的规范活动 逆向工程并不改变目标系统，它只是一个分析检查的过程，而不是一个修改 的过程。逆向工程通过标识系统组件及发现这些组件之间的关系，对系统做出抽 象的表示，从而辅助对系统的理解。它涉及的对象可分为三类【2 】： 1 数据( d a t a ) 作为学习、推理和讨论基础的实际信息，这些数据包括系统源程序、源代码 注释、需求分析、分析文档、设计文档、用户手册以及观测到的系统的外部行为 等。 2 知识( k n o w l e d g e ) 所有内容的总和，包括数据和从数据中推导出的关系与规则，例如在程序理 解过程中得到的各种中间结果和对系统各予模块产生的层次结构图等。 3 信息( i n f o r m a t i o n ) 相互交织的交流知识，这些信息包括所有的数据和知识，以及软件工程人员 的各种非正式的思路和建议。 基于这三类对象，s c o t tr t i l l e y 等人给出了逆向工程的三个规范活动：数据 收集、知识组织和信息浏览】。 1 数据收集 原始数据的收集是构造和浏览高层抽象的基础，因而数据收集是逆向工程的 一项基本活动m j 。而且作为构造抽象表示的基础，数据收集不能误导或误解，必 须客观实际。因此，数据收集时，应尽量遵循下列原则： ( 1 ) 采用成熟的技术 数据收集所采用的技术包括静态分析、动态分析和获取非止式数据( 如调查) 等，其中最流行的是分析程序源代码，构造带有语法单位及其依赖关系的抽象语 法树。在编译领域中，语法分析和交叉索引等技术已经很成熟。采用基于编译的 成熟技术，可以得到预期的结果，使收集的数据更加准确和可靠。 ( 2 ) 利用多种数据 遗产系统有四种数据来源：系统源代码，包括系统的数据结构、规则控制 进程、报表格式以及计算机的编码指令等：系统行为，即系统用户所看到的系 统功能和性能；系统文档，包括需求分析、分析文档、设计文档、用户手册和 源代码注释；系统的设计者和维护者。系统的多种数据从不同的方面刻画了系 统对象及其关系，从而为更深入详细的理解系统提供了基础p o l 。利用系统源代码 以外的其它数据，能够更好地辅助软件工程人员理解那些难以理解的系统，如大 型遗产系统。例如。软件工程专家常常利用源代码注释理解系统，调查系统设计 者和维护者可以获得他们的经验，从而使数据更准确、更可靠。 ( 3 ) 过滤数据 1 0 为理解大型系统所收集的数据量可能是巨大的，以至于超出了人们吸收理解 的能力。人们要理解系统，首先必须吸收其中的数据，而系统理解的关键之一在 于清楚了解什么和忽略什么】。数据过滤是从丰富的数据源中抽取所选择的对象 及其关系，因而，在辅助系统理解中起着重要作用。 2 知识组织 对成功的系统理解而言，所收集的数据必须用适当的数据模型保存起来，以 便实现有效的存储和检索，辅助对系统组件及其相互关系的分析，并反映用户对 系统特性的了解程度。数据模型捕捉了系统的本质属性及其关系，它应该可以有 效地支持知识组织。知识组织技术可以用来创建、表示和推理数据模型，因此对 知识组织技术有下列要求： ( 1 ) 知识的组织是面向人的而不是面向计算机的 传统的数据模型。如层次模型、网络模型和关系模型，都是从适于计算机操 作的角度上建模组织数据的。而逆向工程的建模，如概念建模1 3 2 】，则要求以满足 人们的理解为出发点来捕捉系统组件及其相互关系，它强调的是知识组织，而不 是数据组织，知识组织是按照系统实体及其语义关系模型建模的。面向对象的数 据模型所刻画的系统组件及其相互之间的关系是面向人的，而不是面向计算机 的，其抽象机制能够帮助软件工程人员有效地组织和理解目标系统的知识。 ( 2 ) 要能够支持领域分析 当前的逆向工程技术主要以程序分析技术捕捉的程序结构为基础，但是程序 结构自身并不足以反映程序所应用的问题域。领域分析可视为解决这个问题的有 效途径之一。领域分析是指通过标识，组织和表示领域元素及其组成结构来揭示 它们在问题域中的联系m l 。因此数据模型应该按领域组织目标系统的知识，识别 系统中的标准组件，从而为逆向工程提供有效的辅助支持作用。 ( 3 ) 要具有可扩展性 对人型系统而言，逆向工程产生的数据是巨大而且是复杂的，为了实现有效 的存储、检索和分析，就必须使用可扩展的逆向工程数据库来存储和检索逆向工 程中所得到的知识数据。可扩展的逆向工程数据库存储所有的数据与知识，并支 持对系统的增量分析，所以它能够提高系统理解的效率，特别是在大型系统的理 解中。 3 信息浏览 因为大多数程序理解的活动都是在信息浏览时进行的，因而信息浏览可能是 逆向工程三个规范活动中最重要的一个。信息浏览通过遍历存储着目标系统各种 信息的逆向工程数据库，按照指定的标准来分析和过滤信息，并以多种机制表达 所得到的信息，辅助程序理解中的假设一一验证的迭代工程。 ( 1 ) 遍历( n a v i g a t i o n ) 对大型系统而言，逆向工程所产生的信息结构并不是线性的，而是一个相互 交织的多维信息网。网中的链接代表了逆向工程所产生的组件之间的层次关系、 继承关系、数据流、控制流和其它关系。遍历采用定向( 如地图、多窗口、历史 树、路径和复合结点l 等) 和高级模式匹配等机制，辅助人们测览逆向工程知识 组织阶段所产生的多维信息结构】。 ( 2 ) 分析( a n a l y s i s ) 分析多维信息结构是程序理解的关键。分析从原始数据中推导并抽取那些不 是显式存在的信息，并产生关于系统的深层视图。为了辅助用户从多方面理解系 统，可以利用编