第 卷第 期 年 月... 文章编号 : - ( ) - - 基于 的 程序模型逆向转换 摘 樊波, 刘建宾 ( 北京信息科技大学计算机学院, 北京 ) 要 : 针对软件的维护和更新问题, 提出一种基于编译技术 以类图和过程蓝图作为 抽象模型的 程序模型逆向变换方法 从对逆向变换的核心思想 逆向变换规则和机制出发, 提出了从 源代码到 类图和过程蓝图的逆向变化规则, 并用数学的形式进行了精确的 定义 针对面向对象语言 设计了一个逆向变换支撑工具, 应用编译技术动态分析了 源 代码, 逆向转换生成 类图和过程蓝图的可视化模型 关键词 : ; 过程蓝图 ; 类图中图分类号 :. 文献标志码 :, - (,,, ) :,., -.. -., -. : ; ; 引言 随着计算机技术的发展, 软件系统的规模越来 越庞大, 结构越来越复杂, 这些给后继维护工作带来了很多困难, 软件投入使用后维护的开销也越来越 大 软件开发的大部分时间和主要成本集中于对现 有系统的维护, 理解系统是软件维护的首要问题, 尤其在相关文档不全的情况下, 维护一个大而复杂的 系统变得异常困难 维护阶段的关键, 也是最大的 难点在于阅读并且真正理解他人编写的程序 逆向 工程是解决软件在运行维护阶段所遇到的种种问题和提高遗产系统的可演化性的一个非常有效的途 径 逆向工程是对现有系统进行分析, 以最大的努 力去建立比代码抽象层次更高的表达式, 因此采用 合适的抽象模型是非常重要的 过程蓝图是一种可 视化过程建模语言, 它包括由抽象概念结构图 () 抽象逻辑结构图 () 和抽象实现结构图 () 组成的三层抽象外部表示视图 二级映射 [ ] 和统一内部结构 ( 统一建模语言 ), 是一种 面向对象的建模语言 它的主要作用是帮助用户对软件系统进行面向对象的描述和建模 ( 建模是通过 将用户的业务需求映射为代码, 保证代码满足这些 需求, 并能方便地回溯需求的过程 ), 它可以描述这 个软件开发从需求分析直到实现和测试的全过 [ ] 程 过程蓝图和 类图的结合可以很好地实 现可视化建模和程序源代码的有机统一 收稿日期 : - - 基金项目 : 北京市自然科学基金项目 ( ); 广东省自然科学基金项目 ( ); 北京市教委科技发展计划面上项目 ( ); 北京市管高等学校人才强教深化计划项目资助 ( ) 作者简介 : 樊波 ( ), 男, 内蒙古鄂尔多斯人, 硕士研究生, 主要从事逆向工程 软件方法 工具等方面的研究
第 卷 逆向转换流程 本文提出的基于 [ ] 编译生成技术的 - 程序模型逆向变换, 转换的目标是将 程序源 码转换生成容易理解的过程蓝图和 类图的可 视化模型, 辅助系统理解 逆向转换流程如图 所示 图 逆向转换流程 图 描述了逆向转换的流程, 可分为如下几个 步骤 : ) 构造产生 编译器 采用 自动产 生词法 语法分析器以及包含源码结构的, 运行 程序读入用 语法编写的源程序 (-.), 生成 语言编写的 词法分析器和 语法分析器, 同时也生成包含源码结构的相应类, 例如, 类代表一个 结构, 类的属 性 代表条件表达式, 属性代表 分支, 代表 分支 这个步骤的输入是. 文件, 输出是符合语法规则的 词法分析器和语法分析器 ) 源码分析转换 对源码的分析处理并 不是一件容易的事, 尤其在需要获取代码本身结构 信息和语义信息的情况下, 有了编译器可以使这项工作变得简单, 轻松 生成的编译器对输入 的源码逐个字符进行扫描, 提取出每一个单词, 例 如, 标识符 数 运算符等, 进行词法分析 接着语法分析器读入词法分析器生成的字符流, 进行语法分 析 检查源码的语法错误, 生成相应的源码结构 然后利用 分析每一个流程控制类, 提取源码 结构, 生成 文档 在生成的 文档记录有 类的基本信息, 如类属性 类方法 类之间的关系等 ) 提取 数据生成可视化模型 利用 提取解析 文档, 提取 的各种信息, 生成相应的可视化模型. 构造编译器 简介 编译技术是精确解析源代码的最佳方法 编译 器可以对每个单词, 如标识符 数 运算符等进行词 法分析, 也可以对单词流进行语法分析产生语法分析树, 可以准确地检测源码中的任何错误 现代的 编译程序都是语法制导的, 分析过程通常是先由词 法分析器读入每一个单词, 进行词法分析, 然后由语 法分析器读入词法分析器所识别的每一个单词, 产生源程序的语法结构 但是, 词法分析器和语法分 析器是非常复杂的程序, 如果人工设计完成工作量 会非常大 鉴于上述原因, 利用 自动生成编译器成为一种高效的途径 是一种应用非 常广的 编译器构造器, 这种构造器可以根据语 法规格说明产生 程序 输入一个遵循 语法规定格式的文件, 然后根据输入的文件自动生成相应的词法分析与语法分析程序 同时, 新版本 的 除了常规的词法分析和语法分析以外, 还 提供 等工具来帮助建立语法树. 构造编译器 运行, 读入用 语法规则编写的源 程序 ( 即 语言的语法规则 文法规则以及该文 法规则相关的语义动作说明 ), 生成 代码的 - 编译器 所以有了 会非常容易获得 -. 的编译器 构造编译器步骤如下 : ) 在命令行运行.; ) 编译生成的 文件 *.; ) 运行编译器 运行 命令后会生成如下几个 文件 :.( 语法分析器, 也即编译器的主程序 ),.( 词法分析器 ), -.,.( 单词 ), -.( 编译异常 ),. ( 常 量 ). 语法规则 的输入文档是一个词法和语法的规范 文件, 其中也包括一些动作的描述, 它的格式如下 : ::= " ""("< >")" " ""("<>")" ( )* <> 输入文档的关键词说明如下 : ): 这部分对产生的语法分析器 的特性进行说明 这部分的内容是可选的, 如果没 有设置某个特性, 将使用默认值, 每一个特性都有各
第 期 樊波等 : 一种视频关键语义对象的检测方法 自的默认值, 例如向前看单词个数特性 - 的默认值是 ) 分析器类的声明 : 这个部分指定了分析器类 的名字, 以及其他类中成员的声明 这个部分是必 须有的 声明如下 : ( ) { } ( ) 这里需要特别注意的一点是 和 后面的名称必须与分析器类的名 称一致 ) 词法声明 : 词法声明包括四种 :, -,, 其中, 用来说 明被忽略的串 用来说明在词法层次上识 别的 ) 语法声明和动作代码 : 这一部分生成的代码会直接插入分析器类声明的结束括号之前 一般而 言, 语法中的每一个非终结符都对应一个函数 ) 的语法表示记号 : * [ ] : 其中的内容是可选的 ; * +: 前面的内容出现一次或多次 ; * -: 前后构成的闭区间 ; * *: 前面的内容出现 次或多次 ; *?: 前面的内容出现 次或一次 ; * (): 改变运算的优先级, 把其中的内容作为 一个整体. 源码到过程蓝图的逆向转换 源码到抽象实现结构图的逆向映射规则 使用 构造生成的编译器读入 程序源码, 对源码进行逐字扫描, 生成包含程序结构信息 和语义信息的抽象语法树 () 解析抽象语法树 结点自动转换为用过程蓝图的逻辑结点类型和 操作表达式表示的实现结点, 然后通过人机交互方式填入自然语言表示的结点语义得到过程蓝图的逻 辑结点, 最后运用逻辑结点类型到概念结点类型的 逆向映射规则, 逻辑结点抽象为概念结点 表 给出了 源码到 节点再到过程蓝图逻辑和概 念结点的逆向映射规则 流程控制语句 表 源码与 过程蓝图逻辑和 概念结点的逆向映射规则 结点类型 逻辑结点类型 概念结点类型 语句 () 语句 () 语句? 多分支选择语句 情况分支 @ 否则情况分支 () 循环语句 * () 循环语句 () 循环语句 函数段 / 过程块! 类型 / 类 / 函数的声明语句 : 基本操作语句 标号语句 语句 的 子句 的 子句 跳转语句 > 跳转语句 抛出异常语句 跳转语句 过程蓝图的实现视图是用抽象逻辑结点类型和操作表达式表示的实现结点构成的树, 逻辑视图是 用抽象逻辑结点类型和自然语言表示的逻辑结点的树, 概念视图是用抽象概念结点类型和自然语言表 示的概念结点所构成的树 实现层视图的结点语义 来自程序中的注释和代码中提取的操作表达式, 逻辑和概念层视图的结点语义需人工理解后使用自然 语言正文进行输入. 逆向转换的语义聚集 语义聚集就是将多个同一层次的结点结合在一起, 产生一个新结点成为这些结点的父结点 进行 语义聚集需要满足如下几个条件 : ) 多个结点必须是同一层次的结点 ( 即有相同父结点的结点 ), 否则不能进行语义聚集 ) 进行语义聚集的结点必须是连续的多个结点, 否则会改变语义 ) 开始结点不能是根结点, 否则不能进行操作 进行语义聚集之前必须进行合法性验证, 可以
第 卷 通过比较两个结点的父结点是否相同来验证能否进 行语义聚集, 如果取得的两个父结点不相同, 则说明这两个结点不能进行语义聚集操作 如果满足语义 聚集的所有条件, 则进行语义聚集操作 语义聚集 的过程如下 : 首先得到开始结点, 获得兄长结点, 在 兄长结点后产生一个新结点作为语义聚集点 如果没有兄长结点就在开始结点的父结点插入第一个儿 子结点作为语义聚集点 然后将开始结点到终止结 点的所有结点剪切到语义聚集点下作为语义聚集点的儿子结点, 最后完成语义聚集操作 图 所示是 一个语义聚集 图 语义聚集 源码到 类图的逆向映射 类图是最常用的 图, 它用于描述系统的结构化设计 其中包括类关系以及与每个类关联的属 性及行为 类图可以由四元式 (, -,, ) 表示, 其中 表示类名, 表示类属性, 表示类方法, 表示类关系 各组成部分定义如下 : ::=[ ] [ : ] [ = ] -> :: = [ ] [ ( )*] [ : ] - > -> -> - 其中 表示类修饰符, 表示 类属性修饰符, 表示方法修饰符, - 表示泛化关系, 表示关联关系, 表示依赖关系, 表示聚合关系, 表示组成关系 表示方 法的参数集 以下给出 程序基本元素与类图的映射规则 : ) 类中的成员变量和方法分别转变为 类图中的属性和行为 ->. ->. ) 接口是一系列操作的集合, 它指定了一个类 所提供的服务 它直接对应于 中的一个接口 类型 接口既可用图标来表示, 也可由附加了 - 的一个标准类来表示 -> 接口类 ) 依赖关系是两个模型元素间的语义联系, 依赖 双方某一个模型元素变化必影响到另一个模型元 [ ] 素 依赖关系表现在局部变量 方法的参数 以 及对静态方法的调用 包括如下几种情况 : ( ).. 类 方法的参数是类 ( )..-. 类 方法的参数是类 的属性 ( ).. = 类 的方法的返回值是类 ( ). 类 调用类 ( ) 引入的类, 允许一个包访问别一个 包中的类 ( ) 类型 ) 关联关系是描述一组具有共同结构特征 行为 特征 关系和语义的链, 是一种结构关系, 指明一个 对象和另一个对象间的关系 对应于 中的一个类成员变量是另一个类的情况 关联在代码中一 般表示为属性 ( 成员变量 ). ((, )== ), 则 (, ) (, ) 其中 :== 表示类 与类 是一对 一的关联关系, (, ) 代表在类 中加入对类 [ ] 的一个引用 关联关系包括两个特殊关系, 分别是聚合关系 和组成关系 聚合关系表示一种整体和部分的关 系, 例如学院类是学校类的组成部分, 因此, 学院类 和学校类之间的关系是聚合关系 组成关系比聚合关系有更强的含义, 整体有管 理部分的职责 ) 泛化关系表示一般事物和特殊事物之间的关 系 泛化关系描述了类之间 的关系 泛化关系表示子类的对象可以用在父类对象出现的
第 期 樊波等 : 一种视频关键语义对象的检测方法 地方, 但是反过来不行 对应于 中的子类和超 类之间的关系, 中是通过 表示子类到父类的继承关系 关系. - > 泛化 = =.! = ) 实现关系是不继承结构只继承行为的关系, 也就是一个实体定义了一个合同, 另一个实体必须履 行这个合同 实现关系用于两种情况 : 第一, 在接口 和实现该接口的类之间 ; 第二, 在用例和实现该用例 的协作间 在 中 映射到 实现关系. - > 实现关系 = = [ ] 是一个开源项目, 它基于树型结构, 利 用纯 的技术对 文档实现解析 生成 序 列化以及多种操作 直接为 编程服务 它利用更为强有力的 语言的诸多特性, 把 和 的功能有效地结合起来 在使用设计 上尽可能隐藏原来使用 过程中的复杂性 利 用 处理 文档是一件轻松 容易的事 将一个 文档一次性加载到内存, 并将其 解析成一个树对象, 通过该对象的方法和属性实现 对 数据的管理 在 文档中数据是以标记和树形的形式出现的, 在 中有相应的类与之对应, 例如在 中用 类对象说明 的一个标记, 类对象对应 标记的属性 对 文档处理的第一步就是对文档解析, 将文档一 次性读入内存, 创建 对象 在解析 的过程中也可以进行语法验证 加载 数据有两种方法 : ) 从文件加载 这种方式是比较常见的方式, 下面代码显示了 读取方法 =(); =.( - ( ));=.- (); 是解析器对象, 是文档对 象, 是标记对象 ) 从字符串加载 这种方法也就是把字符串当成 文档, 通过 对象处理 如下代码显示了这种方法的思想 =(); = (); =.( ); =. (); 结论 本文主要介绍基于 的 程序模型逆 向转换方法, 采用 编译技术自动构造生成 编译器, 分析 源代码, 转换生成直观 容易 理解的过程蓝图和 类图可视化模型 提出了从 源代码到 类图的逆向映射机制以及 - 源代码到过程蓝图的逆向映射规则 由于采用 了成熟的编译技术, 使逆向转换更加准确 快捷, 再 加上独特的过程蓝图作为抽象模型, 这种方法在程序模型的表示和转换方面具有明显特色 参考文献 : [ ] 刘建宾. 过程蓝图设计方法学 [ ]. 北京 : 科学 出版社, [ ]. 软件开发方式 - 面向对 象分析与设计 [ ]. 姜南, 周志荣, 译. 北京 : 电子工业出版社, [ ]. [/].( - - )[ - - ].://... [ ] 张龙祥. 与系统分析设计 []. 北京 : 人民 邮电出版社, [ ] 陶长斌. 可视化面向对象 程序设计支持工具的研究 []. 汕头 : 汕头大学, [ ] 侯要红, 松涛. 应用程序设计 []. 北 京 : 机械工业出版社,