（计算机软件与理论专业论文）面向对象程序切片中的控制流分析.pdf

摘要 摘要 控制流分析是程序切片的关键技术 它主要是用来求取语句间的控制依赖关 系 由于程序切片技术在软件安全性分析 程序验证 软件维护等方面有着广泛 的应用 并占据重要的地位 因此 研究程序切片中的控制流分析具有实际意义 在研究现有控制流分析理论的基础上 本文采用基于图论的方法求取控制依 赖关系 该方法具有很好的可扩展性和通用性 它主要是通过将控制流图转化成 后必经结点树 再根据后必经结点树寻找控制依赖关系 在详细讨论控制依赖计 算的基础上 提出了一种控制依赖图的优化表示方法 即用扩充的后必经结点树 和控制依赖集合数组来表示控制依赖关系 并基于这种方法高效地实现了三种控 制依赖集合的查询 c d 集合 依赖于同一语句的语句集 的查询 c o n d s 集合 为 同一语句所依赖的语句集 的查询和c d e q u i v 集合 具有相同c o n d s 集合的语句集 的查询 关键词 控制流分析程序切片控制依赖后必经结点 a b s t r a c t a b s t r a c t c o n t r o lf l o wa n a l y s i si sak e yt e c h n o l o g yo f p r o g r a ms l i c i n g w h i c hi sm a i n l yu s e d t of i n dt h ec o n t r o ld e p e n d e n c er e l a t i o nb e t w e e ns e n t e n c e s p r o g r a ms l i c i n gi sw i d e l y u s e da n dp l a y sa ni m p o r t a n tr o l ei nt h ef i e l d so f t h es a f e t ya n a l y s i so f s o f t w a r e p r o g r a m v e r i f i c a t i o na n ds o f t w a r em a i n t e n a n c e e t c s oi ti sn e c e s s a r yt os t u d yc o n t r o lf l o w a n a l y s i si np r o g r a ms l i c i n g a f t e rs t u d y i n gt h ea v a i l a b l et h e o r yo fc o n t r o lf l o wa n a l y s i s a na p p r o a c hb a s e do n t h eg r a p ht h e o r yi su s e dt of i n dt h er e l a t i o no fc o n t r o ld e p e n d e n c e w h i c hi se x t e n s i b l e a n da l l p u r p o s e c o n t r o lf l o wg r a p hi st r a n s l a t e di n t op o s t d o m i n a t o rt r e e a n dt h e m l a f i o no fc o n t r o ld e p e n d e n c ei sf o u n di nt e r mo ft h ep o s t d o m i n a t o rt r e e a f t e r d i s c u s s i n gt h ec o m p u t a t i o no fc o n t r o ld e p e n d e n c ei nd e t a i l a no p t i m a lr e p r e s e n to f c o n t r o ld e p e n d e n c ei sp r e s e n t e dh e r e w h i c hi n c l u d e st h ep o s t d o m i n a t o rt r e ea n dt h e a r r a yo fc o n t r o ld e p e n d e n c es e t s t h r e ek i n d so fc o n t r o ld e p e n d e n c es e tq u e r i e sa r e c o m p l e t e de f f i c i e n t l yb a s e do nt h ea p p r o a c h w h i c ha r et h ec ds e tq u e r y t h ec o n d ss e t q u e r y a n dt h ec d e q u i vs e tq u e r y t h ec ds e ti st h es e to fs e n t e n c e sc o n t r o ld e p e n d e n c e o nt h es a n l es e n t e n c e t h ec o r d ss e ti st h es e to ft h es e n t e n c e so nw h i c has e n t e n c ei s d e p e n d e n t t h ec d e q u i vs e ti st h es e to fs e n t e n c e sh a v i n gt h es 锄e c o n d ss e t k e y w o r d c o n t r o lf l o wa n a l y s i s p r o g r a ms l i c i n g c o n t r o ld e p e n d e n c e p o s t d o m i n a t o r 第一章绪论 第一章绪论 1 1 研究背景 本文工作源自于 十五 预研课题 软件安全性故障模式分析 该课题主要 面向军事电子信息系统 旨在研制出一个基于静态分析的软件系统安全检查工具 随着网络技术的发展和自由软件的广泛使用 软件的安全 特别是军事领域 软件的安全已越来越受到人们的重视 它已经成为影响计算机安全的最大问题之 一 由于计算机的安全性隐患 包括无意的和人为的 大量存在于软件系统中 如系统入侵 信息窃取 瘸毒 以及由于程序设计语言自身问题造成的各种安全 漏洞等 使得软件通常不够健壮 导致软件在使用阶段会发生意想不到的软件故 障 从而造成重大损失 对于自主开发的软件 主要通过测试的方法捡查所有可能的不安全因素 这 需要对软件的功能 特性等具有深刻了解 并且根据软件特性设计完备的测试集 显然这种动态测试的方法并不适用于使用可重用软件的情况 因此 如何能在静 态 不运行 时尽量检测出软件的安全性问题 避免不必要的损失 成为当前计 算机安全领域中需要研究的一个重要课题 由于军事应用领域中要求软件系统具有很高的安全性 软件系统安全性分析 工具可以被广泛地应用于军事应用领域中的软件分析 以提高军事应用软件的安 全性 在研制工具过程中我们所研究的一组方法 具有一定的酱遍性 对其它相 关工作 如逆向工程 遗产继承等均具有理论和实际指导意义 针对软件安全性这一重要问题 许多学者提出了不同的解决方式 如 早期 的基于程序逻辑中的公理和推理规则的形式化验证方法一定理证明 t h e o r e m p r o v i n g 它也是出现最早的方法 八十年代初e c l a r k e 等人闭提出的一种基于 自动机理论的模型检验 m o d e lc h o k i n g 的方法 这也是一种形式化的方法 用 于验证程序的正确性 1 9 9 7 年卡奈基梅隆大学的g e o r g ec n e c u l a l 3 提出的携带验 证代码 p i l 0 0 艇锄蜘玛c o 曲 f c c 技术 用于固定的代码提供者和使用者之间 随 着网络技术的发展 计算机系统中的信息安全一直催受关注 同时出现了一种基 手类型推理的信息流验证和检测 4 l 方法 由于软件的规模越来越大 目前主流的 验证软件安全性的方法是基于程序分析的安全性检查 它已成为该领域研究的热 点 面向对象程序切片中的控制流分析 1 2 静态程序分析 程序分析的目的是不用实际的运行程序而提取程序运行时的信息 程序分析 是静态安全性检查的基础 几乎所有方法都建立在程序分析的基础之上 人们在 该领域进行了长期 大量的研究工作 可以通过词法分析 或者语法分析加简单 的语义分析来检查软件系统中的许多安全漏洞 1 1 基于词法分析的安全住扫描 基于词法分析的安全性扫描 5 对源代码只进行词法分析 通过静态扫描源代 码找出潜在的安全漏洞 一旦发现就给出警告信息 它的基本方法是将一个或多 个源代码作为输入 并将每个文件分解为记号流 比较记号流中的标识符和预先 定义的安全性漏洞字典 这类方法具有简单 高效的优点 但是精度较低 不适 用于精确的静态分析 另外 可检查出的安全性漏洞种类有限 f 2 1 基于语法加简单语义分析的安全性检查 基于语法加简单语义分析的安全性检查 6 1 的工作原理非常类似于编译器系 统 它以语法分析和语义规则为基础 同时加入简单的控制流 阳数据流分析 因 此这种方法具有较高的分析效率和可扩展性 并且可以通过向程序中加入注释信 息的方式发现软件中广泛存在的安全漏洞 如程序中出现机率最多的内存访问漏 洞 包括存储区的非法使用 空指针的脱引用 d c r e f e r e n e e 缓冲区溢出等等 它 的另一个优点是可适用于对大规模程序的分析 图1 1 简化的安全性分析模型 第一章绪论 3 经过分析和比较 我们发现基于程序分析的安全性检查可适用于对大规模程序 的分析 这种方法具有较高的分析效率和可扩展性 我们将主流的安全性分析方 法归结为一个普遍适用的框架 见图1 1 此框架的特点在于 它将与安全相关 的具体模式从程序分析中剥离出来 从而以不同的方法解决最适于解决的问题 程序分析是软件安全性检查的基础 根据不同的安全漏洞和对应的安全模式 程序分析可以是在词法 语法 语义的任何级别上进行 程序分析器的研究内容 包括 传统的语法分析 数据流分析 控制流分析 传统分析方法向面向对象程 序设计语言的扩充 跨过程的程序切片和支持面向对象的分层切片等 这也正是 我们现阶段的工作 分析的对象是广泛使用的c c 语言编写的程序 1 3 论文的主要工作 人们在理解大型的计算机程序时必须对其进行分解 分解不仅对人们分析问 题是非常有用的 而且分解得到的过程和抽象数据类型也是很有用的 对于程序 分析来说 程序分解也应是它的第一步 这会降低程序分析的复杂度 所以 在 程序分析中我们采用了基于程序依赖图和图形可达性的程序切片 p r o g r a ms l i c i n g 方法 控制依赖信息捕捉谓词语句 如i f 语句 w h i l e 语句等 对程序行为的影响 数据依赖信息捕捉数据交互对程序行为的影响 程序切片方法就是使用数据依赖 和控制依赖信息来识别出可能在语义上影响一条语句的所有语句集合 从而完成 分析的任务 本文所傲的主要工作是 将控制流分析应用于程序切片方法中 其主要作用 是求出程序语句间的控制依赖关系 首先由开放编译器g c c g n uc o m p i l e r c o l l e c t i o n 得到c c 源程序的抽象语法树 a b s t r a c ts y n t a xt r e e a s t 基于语 法树将源程序转换成控制流图 c o n t r o lf l o wg r a p h c f g 然后在控制流图上通过 控制流分析为程序切片求解语句间的控制依赖关系 构造表示c c h 源程序的系 统依赖图中的控制依赖子图 在该图上可以求取与切片准则有控制依赖关系的语 句集合 主要的研究内容包括 1 对程序切片的研究 2 对程序进行控制流分析 3 对构造控制依赖子图的关键技术的研究 4 设计与实现控制依赖子图和控制依赖集合的查询 第二章程序切片的基本方案 第二章程序切片的基本方案 2 1 程序切片综述 程序切片是一种基于数据流和控制流分析的自动分解程序的方法 它不但应用 于程序分析 在程序调试 自动并行 程序集成 逆向工程等方面也起着重要作 用 程序切片的概念最早由m a r k w e i r d 7 1 9 7 9 年在他的博士论文中提出 后来他 又在1 9 8 4 年的文章闱中进一步阐述了程序切片的思想和实现算法 非形式化地说 满足下列两个条件的程序称为切片 一个程序切片对应一个特 定的切片准厕 s l i c i n gc r i t e r i o n vi 1 其中v 表示变量的集合 i 指程序中的某个点 一般指某条语句 2 程序p 的切片s 可通过从p 中删除0 条或多条和切片准则不相关的语句得 到 但要保证程序p 和切片s 的关于切片准则f v i 的行为相同 w e i r 论述了通过遍历控制流图 利用数据流方程和信息流方程来分析数据依 赖和控制依赖关系 从而得到过程内切片 i n u a l o c e d u r a l s l i c e 的技术 后来 o t t e n s t e i n 等人仰提出基于程序依赖图 p r o g r a md e p e n d e n c eg r a p h p d g 的切片 算法 将过程切片问题转换成依赖图的图形可达性闯题 h o r w i t z 等人 lo j 用系统依 赖图 s y s t e m d e p e n d e n c e g r a p h s d g 表示有过程调用的程序 并给出了一个基 于s d g 表示的跨过程切片算法 这些方法都是基于传统结构化的程序 切片局限 在一个过程内或几个过程之间 随着对象技术及其思想的日益普及 1 9 9 4 年以来 面向对象程序的切片技术 的研究逐渐成为主流 结构化程穿的切片技术与嚣向对象程序的切片技术区别在 于 前者的分析粒度是基于语句或者是数据的 只要建立起详细 准确的体现控 制流和数据流的过程依赖图或系统依赖图 并在此基础上进行切片 就可以对源 程序进行很好的理解 后者的分析对象是面向对象的源程序 面向对象程序设计 语言的基本特征有继承 多态 封装 数据抽象 动态绑定等 因此 面向对象 程序切片不仅要考察语句或数据之间的依赖关系 还要考察各个类之间的关系 而传统的系统依赖图并不能准确 完整地反映这些关系 因此 我们需要对传统 的面向过程的切片技术进行面向对象的扩充 目前 面向对象程序切片技术具有代表性的研究工作有 a k r i s h n a s w a m y 等 人 1 1 利用面向对象的程序依赖图 o b j e c t o r i e n t e dp r o g r a md e p e n d e n c eg r a p h o p d g 表示面向对象程序的继承关系 多态性关系以及动态绑定等 从很大程度 6 面向对象程序切片中的控制流分析 上解决了面向对象程序的切片问题 f r a n kt i p 1 2 1 用类层次图来解决c 程序的类 层次中的类切片 在国内 南京大学李必信等人 1 3 1 提出面向对象程序分层切片的 思想 利用逐步求精的方法得到面向对象程序的切片 2 2 分层切片模型 1 基于过程的程序切片 在传统的基于过程的程序切片中 主要考虑过程内和过程间的数据流和控制 流信息 切片的上下文问题可以转化为系统依赖图上的图形可达性问题 为了对 这种基于过程的程序进行切片 需要三个步骤 1 构造系统依赖图g 2 基于 图形可达性算澍卅或两阶段图形可达性算法1 1 0 l 对g 进行切片 获得切片后的系统 依赖图g 3 从g 获得切片程序 2 面向对象程序的分层切片 由于面向对象中类和它的实例 对象 的存在 增加了切片的困难 每个对 象具有自己的数据集合 因此切片具有更深的意义 分层切片模型i l 习用分层的概 念表示面向对象程序本质上的抽象层次 比其它面向对象切片技术更清晰地描述 了面向对象程序中类之间的各种关系和消息传递机制 由于c 程序的语法与j a v a 存在许多相似点 如类 继承 多态等 所以我们借鉴李必信等人的思想 对其 分层切片模型进行了改进 以适应对c 程序的切片 并在此基础上采用逐步求 精算法来分层计算c 面向对象程序的切片 相对于纯粹面向对象语言j a v a 而言 c h 语言中还包含过程式的内容 而且 c 中还有指针 这些都增加了对c 程序进行切片的难度 而且目前的研究要么 是对单纯过程式的语言 要么是对纯粹面向对象的语言 那么处理c 语言的关 键是 这二者如何结合 我们提出的解决方法是将c 中过程式的内容归为一个 假设的类 全局变量将成为这个虚设的类的数据成员 c h 程序的主函数和一些其 它的普通函数将成为该类的方法 这样c 程序整个由类构成 并具有不同的抽 象层次 因此 可以对c 汁程序进行层次化分析 即分别在类层 方法层 语句 层上对c 程序进行切片 由于c 程序中不存在j a v a 中包的概念 这里我们去 掉了包层切片 改进后所得到的c 莳层次化切片模型分为三层 类屡 方法层 语句层 如图2 1 所示 这三个层次上都有对应的数据结构描述相应模块之间的 关系 它们是 类层依赖图 方法层依赖图 语句层依赖图 这些依赖图是分层 切片算法的基础 经过我们的假设 c 面向对象程序有着清晰的层次结构 程序由类组成 类 第二章程序切片韵基本方案 类层切片尊 厂颈壅丽 颡i n e 日目t l 一 l 方法层切片 i 方法层依赖图j l 一 i 语句层切片爵 f 语句层依赖图i 圄 切片层次中间表示算法综合切片库 图2 1c 程序分层切片模型 由方法和成员变量组成 方法由语句和变量组成 我们在这些层次上构造不同的 依赖图 通过遍历图得到相应的不同粒度的切片 基于分层切片模型和切片准则 v i 1 得到下述c 程序切片的主要思想 1 类层 首先根据准则 v i 确定所有与包含v 和i 的类有关 有继承 消 息传递 数据依赖或控制依赖等形成的直接或间接关系 的类 如果某个 类的某个方法中某条语句影响切片准则或受切片准则影响 则把该类包含 到切片集合中 否则 在进行下一步切片时不予考虑 通过这种方法得到 关于切片准则 i 的程序切片的一个粗略版本s p 代表整个c 源程 序 2 方法层 在类层基础上 迸一步计算单个类中影响切片准则或受切片准则 影响的变量和方法 删除那些与切片准则无关的变量和方法 得到方法级 切片版本s p 3 语句层 在前面工作的基础上 进一步计算过程或方法中与切片准则有关 的变量和语句 删酴那些与切片准则无关的变量 语句和控制谓词等 最 后得到语句级切片s p 至此 就可得到一个c 程序关于切片准则 v i 的程序切片 在每个层次上 我们仍然采用传统的基予依赖圈的算法 但在某些问题的处 理上 例如继承 多态性等 则对传统的依赖图进行了一些面向对象的扩充 2 3 源程序信息提取方案 2 3 i 程序依赖图和系统依赖图 程序依赖图 p d g 是程序的一种图形表示 它把控制依赖和数据依赖包含在单 个的结构中 如果给定程序中的语句x 和y 则x 和y 可以通过控制流或者数据 流来彼此关联 p d g 的形式定义由一个控制依赖子图 c o n t r o ld e p e n d e n c e s u b g r a p h c d s 一个c f g 和一个数据依赖子图 d a t a d e p e n d e n c e s u b g r a p h d d s 8 面向对象程序切片中的控制流分析 组成一j 其中c d s 包含了程序中的控制依赖 c f g 描述了一个程序中的控制流 d d s 是一个程序中语句之间所有数据依赖的集合 d d s 包含语句间的数据依赖 可通过在c d s 的结点之间插入数据依赖边来构造d d s 程序依赖图通常是为单个 过程的程序而定义的 但是 实际的程序一般是由多个过程组成的 系统依赖图 就是来描述由多个过程相互作用而构成的复杂程序 形式地说 它是由一个程序 依赖图和一组过程依赖图 p r o c e d u r ed e p e n d e n c eg r a p h p r d 构成的有向 带标记 的多重图 l p d g 模型化软件系统中的主程序 p r d g 模型化软件系统中的多个 过程体 s d g 可以用来处理过程间的数据流和控制流 并能表示参数传递 2 3 2 扩充面向对象特点的系统依赖图 s d g 允许过程间分析 但是传统的s d g 必须经过面向对象的扩充以后才能够 描述面向对象的程序 要做到对面向对象程序的全面的分析和理解 必须有一种 能全面描述面向对象程序静态特征的表示方法 为此 我们对s d g 进行面向对象 扩充 得到扩充面向对象特征的系统依赖 o b j e c t o r i e n t e ds y s t 咖d e p e n d e n c e g r a p h o o s d g 其中主要对s d g 加入类层次子图 这样 o o s d g 是类层次子 图 控制依赖子图和数据依赖子图 过程依赖子图这几种表示方法的并集 类层次子图 c l a s s h i e r a r c h ys u b g r a p h c h s 用图形来表示类间的继承关系 是方法和类定义的一种融合 类层次子图包含每个类的首都结点和在类中定义的 每个方法的首部结点 类层次子图中的边把每个类的首部结点和与其具有继承关 系的类的相应的首部结点连接起来 由方法酋部表示的方法结点被连接到定义该 方法的类的首部结点 子类中没有重新表示从超类中继承的方法 因而消除了对 继承方法的重复表示 因为类层次子图不表示方法的任何实现细节 所以不是一 个程序的完全的静态表示 控制依赖子图 每个方法和过程的实现包含在这层表示中 在该图中包含方 法和过程内所有语句或谓词表达式 控制依赖边表示一个语句或表达式执行时依 赖的控制条件 方法和普通过程的控制依赖予图具有类似性 所以这里采用的是 基于过程的构造方法 数据依赖子图 一个面向对象程序的运行环境比一个过程程序的运行环境要 复杂得多 在数据依赖子图上 对象被加到表示中 这使得把消息动态地绑定到 对象中的特定方法得到完全解决 其它传统类型的数据依赖信息也得到表示 过程依赖子图 由于方法和过程具有类似性 所以在构造它们自身的依赖图 时 仍采用的是基于过程的方法 控制依赖子图和数据依赖子图的并集就构成了 过程依赖子图 每个过程依赖子图包含一个入口结点 表示过程的入口 为了模 型化参数传递 o o s d g 为每个过程入口结点附上形参输入和形参输出结点 第二章程序切片的基本方案9 2 3 3 构造依赖图的实现方案 在实现方案中 关键是要为c c 源程序构造出层次化的依赖图这种中间表 示 由于过程依赖子图实际由控制依赖子图和数据依赖子图构成 所以在构造依 赖图时 只要构造类层次图 控制依赖子图和数据依赖子图就可以了 首先就需 要对源程序进行词法分析和语法分析 这个工作类似于编译器的工作 所以我们 利用开放编译器g c c 的前端对源程序进行词法和语法分析 并基于从g c c 得到 的抽象语法树实现后续分析 这使得切片工具在语法上能够支持最新的c c 语 言版本 我们首先构造各级依赖图以提取源程序的信息 具体实现方案如图2 2 所 示 下面对方案图中的每一部分做以简单的介绍 图2 2 程序切片系统的体系结构 构造类层次子图对 我们直接从a s t 中提取类及方法的信息 从而找出类之 间依赖关系 继承关系 聚合关系 以及类定义中方法通过互相调用或共用 某些成员变量而产生依赖关系 实际上它包含了类级和方法级的依赖图 控制依赖子图是语句级依赖图的一部分 这一级的构造最为复杂 该子图表 示的是一个语句或表达式执行时依赖的控制条件 首先将a s t 转换成控制流 图g 再由g 构造后必经结点树t 然后在t 上根据后必经关系 寻找语句 间的控制依赖关系 面向对象程序切片中的控制流分析 数据依赖子图同控制依赖子图一样 也是语句级依赖图的一部分 它也是基 于控制流图来构造的 数据流分析沿着所有的控制路径 把到达 定值信息存 储为引用 定义链 u d 链 它是所有能够到达变量的某个引用的定值表 然后根据u d 链求取语句间的数据依赖关系 指针别名分析主要是求出所有可能的别名对 它实际上是数据依赖分析的一 部分 精确的指针分析能够增加数据流分析的精度 指针是c c 语言中的 难点所在 所以它的分析也很复杂 因此把它单独作为一个模块 2 4 程序切片的实现环境 程序切片系统采用l i n u x u n i xc o m p a t i b l e 操作系统平台 并基于符合c c 语言国际标准的 开放源代码的编译器g c c 我们通过该编译器对c c 源程序 进行词法 语法分析 得到它的抽象语法树 将其作为切片系统的输入 同时还 采用了支持面向对象技术开发的词 语法分析器生成器f l e x 和b i s o n y a c c c o m p a t i b l e 采用g c c 编译器生成源程序的中间表示有很多优点 g c c 是美国自由软件基金会f f r e es o f t w a r ef o u n d a t i o n 开发的且流传广泛 的编译程序集合的简称 该编译程序集合是一个向上可接收多种语言 向 下可支持多种平台的编译系统 它所接收的语畜有c c o b j e c t i v e c f o r t r a n j a v a 和a d a 这有利于我们研制的工具将来向支持多语种 支持多平台的方向扩展 另外 g c c 对源语言的中间表示是抽象语法树 a s t a s t 包含了源程序 的所有信息 而且g c c 提供了大量的宏调用 通过这些宏可以得到a s t 上的各级信息 这也是g c c 优予其它编译器之处 如对于o l c i l c 十所提 供的a s t 主要给出了操作类的接1 3 而对一般的过程及变量的操作则需 要使用者自己完成 g c c 功能强大 并被全世界的编程精英们不断完善 随着语言标准的变化 它也不断的升级 所以永远支持最新的c 忿 语言版本 这非常有利于我 们检验工具的更新与升级 第三章构造控制依赖图的关键技术 第三章构造控制依赖图的关键技术 一股用控制依赖图来表示语句阉的控制依赖关系 所以计算控制依赖关系就 是构造控制依赖图 在控制依赖图上可以求出与切片准则有控制依赖关系的语句 集合 这 章首先讲述了控制流分析的目的 并确定了通过控制流分析求取控制 依赖所采用的方法 然后讲述了控制流图的概念和结构 以及后必经结点的概念 和求取的算法 最后着重阐述了文中所提出的控制依赖图的优化表示方法 本章 中的控制依赖图指的就是前面提到的控制依赖予图 3 1 控制流分析 在设计和实现程序分析和程序变换中 理解程序的控制流是十分必要的 控制 流信息指出在程序中的每个程序点接下来可能执行的程序点 传统的控制流分析1 1 4 主要应用于程序优化 分析是在基本块构造的控制流图上进行的 主要分析控制 流图中的块和循环结构 其中基本块是由中间代码来构造的 对于低级语言的控 制流图很容易构造 因为程序中从一点到另一点的控制流信息是很明确的 但对 于高级语言 情况就不同了 在源程序中的控制流信息往往是不明确的 这是由 于在高级语言中存在复杂的语句结构 并且函数可以像数据一样被传递 并可以 在程序中的任意一点调用 所以需要控制流分析去求解高级语言中的控制流信息 在本文的工作中 将控制流分析应用于程序切片领域 其主要作用是求出程序 语句间的控制依赖关系 我们的切片算法主要基于程序依赖性 即根据语句间的 控制依赖关系和变量间的数据依赖关系求出影响切片准则的切片集合 其中语句 间的控制依赖关系指的是 在控制流图中的谓词缩点作为控制点决定控制流能否 到达某些结点 那么这些结点控制依赖于该谓词结点 在文中通过控制流分析 求出程序中所有语句间可能存在的控制依赖关系 用来为程净切片服务 求取控制依赖的方法主要有两种 一种是基于语法制导的方式 另一种是基于 圈论的方法 用前一种方法求控制依赖关系 主要是根据程序中语旬的语法结构 来构造控制依赖 这就需要对于不同的语句结构采用不同的控制依赖构造方式 这使得对于每种语句结构 都需要单独考患构造方式 所以构造控制依赖关系时 非常复杂 不具备通用性 后一种方法是首先将程序转化成控制流图o 再将g 转化成后必经结点树t 最焉在t 上求取控制依赖关系 这种方法具有很好的可 扩展性 因为它将程序转换成了控制流图 而控制流图以结点和边这种统一的形 式表示程序语句 这样在分析时就可以对语句采取相同的处理策略 另外 控制 1 2 面向对象程序切片中的控制流分析 流图也是比较容易构造的 图论有着深厚的理论基础 为控制依赖关系建立一个 图的模型 根据图论可以为控制依赖关系定出规范的定义 这便于用统一的解法 对所有语句结构求解控制依赖关系 因此 本文将基于图论的方法求解语句间的 控制依赖关系 3 2 控制流图 引入控制依赖是为了近似的表示程序的控制流关系 控制依赖是从通常的控 制流图中得出的 在建立控制依赖图时使用了控制流分析 在c 程序中方法是 一组语句和谓词的有序集合 这一点使得方法与结构化程序的过程很相似 所以 下面给出的控制流图定义具有通用性 接着讲述了几种语句结构在控制流图中的 表现形式 3 2 1 控制流图的定义 定义3 1 控制流图是一个有向圈g k 占 v 是结点韵集合 e 是有向边 的集合 其中结点表示语句 边 v 表示从 到v 可能的控制流 令 v e 表 示控制流图中的边 v 则称群是v 的前趋 v 称为甜的后继 语句w 的所有前 驱组成的集合称为w 的直接前驱集 记为p r e d w w 的所有后继组成的集合称为 w 的直接后继集 记为s u c c w 另外 为g 增加了两个特殊的结点 s t a r t 称为 开始结点或入口 它没有前趋 从它可到达每个结点 s t o p 称为退出结点或出口 它没有后继 从每个结点都可到达它 一个程序可能有几个结束语句 为了保证控制流周中终点的唯一性 所以在图 中加入一个虚结点s t o p 并将所有结束语句对应的结点都指向它 为了方便求 控制依赖 我们加入一条从s t a r t 到s t o p 的边 这样在后面求控制依赖时就不 用再扩充一个谓词结点了 l c c 程序中语句基本上可分为以下几种类型 1 简单语句 一般的赋值语句 输入输出语句等 2 复舍语句 i f 语句 w h i l e 语句 6 漩语句 d o w h i l e 语句等 这些语句影响整个程序中的控制流程 3 谓词部分 即条件语句和循环语句的判 断部分 为了方便处理 在建立结点时可以将信息加入到复合语句结点妁信息里 并将这种复合语句称为谓词结点 4 跳转语句 包括b r e a k c o n t i n u e r e t u r n g o t o 语句 这里暂时先不考虑c 中的方法调用结点及l l e w 语句 把它们当成简单语 句来处理 当控制流图的边离开一个条件 谓词结点 时标记为t 表示t r u e 或 f 表示f a l s e 否则没有标记 第三章构造控制依赖图的关键技术 3 2 2 语句的控制流图 1 1 顺序语句 顺序语句的控制流图形式最简单 只需用一条没有标记的边将一个结点连向下 一个结点就可以了 如下图3 1 所示 其中a b 为语句标号 用来代表该行语句 在下面图中语句的标号与这里含义相同 i oa i l u b r e t u r ni i r u 上 图3 1 顺序语句的控制流图 2 1 i f 语句 i f 语句的控制流图有两个出边 一个指向条件为真时的语句 另一个指向条件 为假时的语句 并分别在这两条边上标记t 和f 表示见下例 图3 2i 鼯句的控制流图 3 1w h i l e 循环语句 在w h i l e 语句的控制流图中 连向w h i l e 条件结点语句至少有三条边 一条是 由循环形成的入边 另外两条是出边分别标记为t 和f 其中标有f 的边指向w h i l e 语句结束后的第一条语句 图3 3w h i l e 语句的控制流图 4 1d o w h i l e 循环语句 d o w h i l e 语句的控制流图与w h i l e 语句的控制流图类似 只是控制流进入语句 的位置不同 在w h i l e 语句中控制流先进入条件语句 再进入循环体 而在d o w h i l e 语句中 控制流的进入的顺序刚好相反 实例如下 0 l 2 一 e 一 s f l l e a b c 0 k n 1 k 一 1 ln a b 面向对象程序切片中的控制流分析 d o a 1 1 b 1w h i l e i 0 图3 4d o w h i l e 语句的控制流图 5 g o t a 语句 g o t o 语句的控制流图为从g o t o 语句连向有标号的语句 见下例 图3 5g o t o i 吾句的控制流图 6 1c o n t i n u e 语句 c o n t i n u e 语句在循环语句体内 控制流在c o n t i n u e 语句处跳至循环入口 进行 下一次循环 下例表示了其构造 a w h i l e b i f i x c e o l l t i n u e d x 7 1b r e a k 语句 图3 6 w h i l e b i f x c b r e a k d x 图3 7b r e a k 语句的控制流图 上 奏吖9上 l 协 一 第三章构造控制依赖图的关键技术 b r e a k 语句在循环语句体内 控制流图在b r e a k 语句处跳出循环体 结束循环 b r e a k 语句的控制流图示例如图3 7 所示 图3 8 是一个完整的程序和它的控制流图的例子 其中每个语句前的字母是该语 句的标号 用来标识该条语句 本文将以这个例子贯穿始终 i n t f x m i n t i n t b 口 i f a b d o 6 b b a c i f a 5 1 d a 一 e l s e p a h w h i l e a 一5 e l s e g gaio c m n n l o 图3 s 函数f u n 和它的控制流图 3 3 后必经结点树的构造 控制依赖的概念是基于后必经结点的概念建立起来的 为了更好的讲清楚控 制依赖的概念 这里先介绍后必经结点的概念以及建立后必经结点树的算法 3 3 1 后必经结点的概念 后必经结点的概念来自于必经结点的概念 下面先介绍必经结点的概念 然后 引出后必经结点 定义3 2 令g 以毋是一个控制流图 如果从开始结点s t a r t 起 每条到 达结点w 的路径均包含结点1 就称g 中结点v 是另一个结点w w v 的必经 结点 d o m i n a t o r 如果v 是w 的必经结点 并且w 的每个其它的必经结点又是v 的必经结点 那么结点v 是的结点w 的直接必经结点 i m m e d i a t ed o m i n a t o r 表 示为v i d o m w a 定理3 1 1 6 在控制流图g kd 中除开始结点外的每个结点有一个唯一的 直接必经结点 f l qj 也 i d o m w w 1w v s 删 构成的以s t a r t 为根的有向 1 6 面向对象程序切片中的控制流分析 树称为g 的必经结点树 则有v 是w 的必经结点当且仅当在必经结点树中v 是 的一个祖先 根据必经结点的定义 将开始结点改成退出结点 相应的可以得到后必经结点 的定义 定义3 3 令g e 句是一个控制流图 如果每一条从v 到退出结点s t o p 不包括v 的路径均包含w 就称结点w w v 是结点v 的后必经结点 p o s t d o m i n a t o r 如果w 是v 的后必经结点 并且v 的每个其它的后必经结点又 是w 的后必经结点 那么结点w 是的结点v 的直接后必经结点 i m m e d i a t e p o s t d o m i n a t o r 表示为w p d o m v 后必经结点的定义中不包括路径的初始结点 所以一个结点不会是它自身的 后必经结点 同必经的概念一样 后必经也是一种传递关系 根据定理3 1 结点 之间的后必经关系也将构成一种树状结构 该结构被称作后必经结点树 3 3 2 求后必经结点的算法 因为求后必经结点等价于在逆控制流图中求必经结点 所以这里讨论的是求必 经结点的算法 然后结合现有算法和本文中所使用的数据结构 给出了文中用来 求后必经结点的方法 在控制流图中求取必经结点树是全局流分析和程序优化中的一个最基本的问 题 这个问题首先被l o w r y 和m e d l o c k i7 在1 9 6 9 年提出来的 并给出了一个时间 复杂度为0 的算法 雄是图中的结点数 1 9 7 9 年i 七n g a u e r 和t a r j a n i s 提出了 一个时间复杂度为o m a m 以 的算法 这里龌逆阿克曼i 撇 h a v e r s c a o k e r m a u n s f u n c t i o n 该函数随嬲的增加增长极慢 取是图中的边数 后来 d o vh a r e l 1 州 又提出了一个线性时间算法 上述线性必经结点算法的可靠性依赖于复杂的数据结构 这使得它在应用中是 不太实际的 根据本文中所要解决的河题 这里对l e n g a u c r 的算法做一些改进 用来构造后必经结点树 该算法开始先在控制流图上执行一个深度优先搜索 d e p t h f a s ts e a r c h d f s 结果得到一棵生成树l 搜索从根结点 在c f g 中即为s t a r t 结点 开始 并 且在搜索过程中 按到达c f g 中结点的先后顺序对结点从1 到拧进行标注 即每 个结点被赋给一个深度优先的序号 这里用d f s c v 来表示 如果结点v 的深度优先 序号小于w 的深度优先序号 则有v v 则p 是一条半必经结点路径 一条从 到v 的半必经结点路径不包括所有在树r 上u 和v 之间的结点 结点v 的半必经结点 是v 的一个祖先 它的定义如下 定义3 4 一个结点v 的半必经结点用s d o m v 来表示 它定义为 s d o m v m i n uj 存在一条路径 w o w i w k 一1 w i v 并对l i k i 有w i v t a t b 图3 9 控制流图和它的深度优先生成树 例如 在图3 9 中 b 是由 a 得到的深度优先搜索生成树a 考虑结点c 其 中在结点旁边的数字是该结点的深度优先搜索序号 碍詹 c 5 路径 吐c me c 和 e c 是对于结点c 的所有半必经结点路径 因为在这些的路径的初始结点中 f 有最小的深度优先搜索序号 所以s d o m c 3 通过按结点深度优先序号递减的顺序遍历树l 来求取半必经结点 同时维护 一个动态的森林f 它是深度优先生成树r 的一个子图 也是一个辅助的数据结构 因此 包括在 中的边 址w et 用来在f 中连接父结点v 和它的儿子结点w 森林f 在初始化时包含所有结点 但不包括r 中的边 即所有结点都作为单 结点树 为了记录半必经结点的值 定义一个数组 用s e m i v 表示结点v 对应数 组中的值 它是定义如下的一个数 在结点v 被深度优先遍历前 s e m i v 10 1 8 面向对氰程序切片中的控制流分析 在v 被深度优先遍历后 但它的半必经结点还未计算之前 s e m i v 的值是 a f s v 在v 的半必经结点被计算后 s e m i v 的值是v 半必经结点的深度优先搜索 序号 森林 支持下列操作 l i n k v w 把边 v w t 加入到f 中 在r 中有p a r e n t w v 而在f 中 结点v 和w 是树的根结点 e v a l v 如果结点v 是森林中一棵树的根 返回v 否则 令 是森林中 包含结点v 的树的根 返回在路径 v 上任意一个结点u 其s e m i u 的 值最小 u p d a t e v 七 置s e m i v 为k 这里结点v 必须是一个单结点树 在维护森林f 的过程中 半必经结点如下计算 初始化时 对所有结点v v 置s e m i v 园詹 v 然后按深度优先搜索序号递减的顺序遍历丁中的结点 即v 在w 之前被遍 历当且仅当v 的序号大于w 的序号 当遍历一个结点v 时 调用u p d a t e v 妨 这里k r a i n s e m i e v a l w 1 w v e 在这个赋值后 s e m i v 就是 v 的半必经结点的深度优先搜索序号 遍历完结点1 i 以后 调用l 烈瓯p a 理n f v v 然后应用半必经结点和下面的引理 就可以为每个结点计算直接必经结点 这 6 个引理的证明在参考文献 1 3 1 中 其中弓i 理3 6 给出了计算壹接必经结点的方法 引理3 1 如果v 和w 是g 中的结点 并且有v w 那么任何从v 到w 的路 径一定包含一个v 和w 在 中共同的祖先 引理3 2 对任何一个结点w r i d o m w s d o m w 引理3 3 令结点v w 满足v w 那么v i a o m w 或者i d o m w 厶i d o m v 引理3 4 令w r 假设s d o m w 毒 w 对每个甜满足s d o m u 2s d o m w 那么i d o m w s d o m w 引理3 5 令w r 令 是在满足s d o m w 毒 3w 的所有 结点中s d o m u 值最小的一个结点 那么s d o m u s d o m w 且i d o m u i d o m w 引理3 6 令w 令u 是在满足s d o m w w 的所有u 结点中s d o m u 值最小的一个结点 那么 i d o m w 艺淼 鬈掣鄙砌 枷 为了下面的应用 这里对引理3 6 中求直接必经结点的公式稍做解释 实际上 引理3 6 可以由弓l 理3 4 和引理3 5 直接锝出 满足s d o m w w 的结点 即为在树丁的路径上s d o m w 和w 之间的结点 所以当s a o m u y 值为所有可能的 第三章构造控制依赖图的关键技术1 9 中最小的一个结点时 若有s d o m w s d o m u 成立 则对于s d o m w 和w 之间其 它的结点u 肯定有s d o m u s d o m u 所以s d o m u s d