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

摘要 本文致力于完成面向对象程序( c + + ) 切片工具中数据依赖图的构造，因为数据 依赖图的构造可以归结到程序中到达一定值信息的求解，所以本文主要阐述了到达 一定值的求解算法及相关的数据流分析问题，并讨论了算法的程序实现，以及在程 序切片中的应用。 文中工作使用的到达定值求解算法是对编译器代码优化领域中经典的到达一 定值迭代求解算法的修改，使其适用于程序切片领域。在实现程序切片工具时， 本文利用g c c 编译器的前端完成对c + + 程序的分析，在g c c 生成的抽象语法树 基础上实现程序切片。在实现到达定值求解算法时，因为算法基于控制流图，本 文提出了一种抽象语法树到控制流图的转换算法，并将其程序实现。在生成的控 制流图的基础上，根据到达定值的求解算法，最终完成算法的程序实现。本文中 工作基本上可以处理各种复杂数据类型存在时，程序中到达一定值信息的求解， 但在数组和指针存在时，分析的精度有待提高。 关键字：数据流分析程序切片数据依赖控制流图抽象语法树 a b s t r a c t t h i s p a p e ri s d e d i c a t e dt ot h ec o n s t r u c t i o no fd a t ad e p e n d e n c eg r a p ho fa n o b j e c t - o r i e n t e dp r o g r a ms l i c i n gt 0 0 1 f o rt h ec o n s t r u c t i o no fd a t ad e p e n d e n c eg r a p h c o m e sd o w nt ot h e o b t a i n i n go fr e a c h i n g d e f i n i t i o n si n f o r m a t i o n ，a na l g o r i t h mf o r r e a c h i n gd e f i n i t i o n sa n dr e l a t e di s s u e sa b o u td a t af l o wa n a l y s i sa r ed i s c u s s e d a n dt h e i m p l e m e n t a t i o no ft h ea l g o r i t h m a n di t s a p p l i c a t i o n i n p r o g r a ms l i c i n g a r ea l s o d i s c u s s e d ， t h ea j g o d t h r nf o rr e a c h i n gd e f m i f i o n si nt h ep a p e ri st h em o d i f i c a t i o no ft h e c l a s s i c a li t e r a t i v ea l g o r i t h mi nt h ef i e l do f c o m p i l e rc o d eo p t i m i z a t i o n ，s ot h a ti tc a nb e a p p l i e d t op r o g r a ms l i c i n g i nt h ei m p l e m e n t a t i o no ft h ep r o g r a ms l i c i n gt o o l ，t h ef r o n t e n do fg c ci su t i l i z e dt op a r s et h ec + + p r o g r a ma n dp r o g r a ms l i c i n gi sc o n s t r u c t e d b a s e do nt h ea s t ( a b s t r a c ts y n t a xt r e e ) p r o d u c e db yg c c w h e ni m p l e m e n t i n gt h e a l g o r i t h mf o rr e a c h i n gd e f i n i t i o n s a na l g o r i t h mt ot x a r t s f o m at h ea s t o ft h ea n a l y z e d p r o g r a m t oi t sa c c o r d i n gc f g ( c o n t r o lf l o w 日a p h ) i sr e p r e s e n t e da n di m p l e m e n t e df o r t h er e a s o no fc f oa st h eb a s eo ft h ea l g o d t h mf o rr e a c h i n gd e f i r t i t i o n s a f t e rt h e c o n s t r u c t i o no fc f qt h ea l g o f i t h mf o rr e a c h i n gd e f i n i t i o n si s i m p l e m e n t e dw i t ht h e i n f o r m a t i o no b t a i n e df r o mt h ea s to ft h ep r o g r a m t h i sp a p e rc a l lg e n e r a t er e a c h i n g d e f m i f f o n si n f o r m a t i o nf o r p r o g r a m w i t hv a r i o u sd a l 口t y p ew h i l et h ep r e c i s i o nn e e d st o b ei m p r o v e di nm e p r e s e n c eo f a r r a y a n d p o i n t e r k e y w o r d ：d a t af l o wa n a l y s i s c o n t r o lf l o wg r a p h p r o g r a ms l i c i n g d a t a d e p e n d e n c e a b s t r a c ts y n t a xt r e e 创新性声明 x 砖s 3 j 3 ；1 本人声明所呈交的学位论文是我个人在导师的指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得西安电子科技 大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研 究工作所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文若有不实之处，本人承担一切相关责任。 本人签名 囟塔 日期：7 _ 0 0 3 - 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容 ，可以允许采用影印、缩印或其他复制手段保存论文。 本人签名 导师签名 陛! 垫 丝 i 日期：塑塑：! ! 兰 日期：地! ：! ： 第一章绪论 第一章绪论 1 1 研究背景 随着网络技术的发展和自由软件的广泛使用，软件的安全，特别是军事领域软 件的安全已越来越受到人们的重视。由于计算机的安全性隐患( 包括无意的和人 为的) 大量存在于软件系统中，如系统入侵、信息窃取、病毒、以及由于程序设 计语言自身问题造成的各种安全漏洞等，使得在软件的使用阶段会发生意想不到 的错误，从而造成重大损失。 对于自主开发的软件，主要通过测试的方法检查所有可能的不安全因素。这需 要对软件的功能、特性等具有深刻了解，并且根据软件特性设计完备的测试集， 但这种方法需要消耗大量的人力和物力。因此，如何能在程序静态不运行时自动 检测出软件源程序中存在的一些安全性问题。避免不必要的损失，成为当前计算 机安全领域中需要研究的一个重要课题。 1 2 国内外研究现状和典型方法的比较 国内外在软件的安全性分析领域做了大量的研究，提出了一些可行的静态的 安全性分析方法，劳且构造了相应的软件安全性分析工具。但现存的各种方法各 存利弊，均存在适用范围较小这一问题。目前现存的安全性分析工具多是分析c 、j a v a 语言的，缺少分析c 抖语言的工具。现有的静态的安全性分析方法可分形 式化验证的方法( 其中包括模型检验，定理证明) ，携带代码验证，基于词法分析的 安全性扫描，基于语法和简单语义分析的安全性检查，基于信息流的安全性分析 等。 1 2 1 定理证明与模型检验 定理证明和模型检验的共同特征是以形式化方法为主的理论验证。 ( 1 ) 定理证明( t h e o r e mp r o v i n g ) 定理证明口1 基于符号逻辑， 应用逻辑和集合的定律( 1 a w ) 对一个假设的集 面向对象程序切片中的数据流分析 合进行推理，得到一个所要求的结果，并根据结果报告指出在特定证明中的哪一 步是不合法的。定理证明的理论基础是演绎推理和归纳推理。将所验证的软件系 统表示成逻辑公式i ，被验证的属性表示成逻辑公式s ，检查推理最终是否满足i s 。 ( 2 ) 模型检验( m o d e lc h e c k i n g ) 模型检验【3 】【4 】( 5 【6 】的基础是有限状态自动机。它列举一个系统能够处于的所有可 能状态，检查每个状态是否违反由用户制定的规则和条件，并根据分析结果报告 导致不合法状态的步骤。模型检验的理论基础是时序逻辑和自动机理论。它将所 要检验的属性表示成时序逻辑公式，系统表示成有限状态自动机，在遍历有限状 态自动机时，检查自动机所有状态是否满足所给属性。 ( 3 ) 定理证明和模型检验的简化工作模型 定理证明和模型检验能够发现程序中存在复杂语义上的错误，从而准确发现程 序中潜在的安全性漏洞，但现存的定理证明工具和模型检验工具普遍分析源程序 的形式化的表示( 数学描述) ，丽不是以源程序作为输入，如定理证明工具需要程 序中存在的不变式，模型检验需要源程序的数学模型。通常可以通过程序分析( 数 据流分析，控制流分析，程序切片) 工具来自动完成程序中不变式的提取和源程 序的模型的生成。程序分析工具通过对源程序进行数据流分析和控制流分析提取 源程序中存在的不变式u 2 1 1 3 】，程序切片提取程序的精简了的模型8 9 1 0 0 】。定理证 明和模型检验的简化模型如下图1 1 所示，从中不难看出，程序分析是它们的共 周基础。此处的程序分析，除了语法分析之外，更需要涉及语义的分析，包括控 制流分析和数据流分析f l l 】。 第一章绪论 证明结果 满足不满足且给出 反例 ( a ) 定理证明模型( b ) 模型检验模型 图1 1 定理证明和模型检验的简化工作模型 1 2 2 携带验证代码 p c c 7 1 ( p r o o f - c a r r y i n gc o d e ，简称p c c ) 的基本思想十分类似于密码。首先， 为代码定义一组安全策略。然后，代码提供者在编制程序时必须遵守这些安全策 略，并在程序源代码中加入验证的代码以证明源程序的代码遵守了这些安全策略； 最后由代码使用者确认这些代码的安全性。 1 2 3 基于词法分析的安全性扫描 基于词法分析的安全性扫描u 4 1 1 5 1 【1 6 1 对源代码只进行词法分析。通过静态扫描 源代码找出潜在的安全漏洞，一旦发现就给出警告信息。它的基本方法是将一个 或多个源代码文件作为输入，并将每个文件分解为词法记号流，比较记号流中的 标识符和预先定义的安全性漏洞字典。例如一但发现c 源程序中存在s t r c p y ，s t r c a t 等字符串操作函数即认为存在缓冲区溢出这种安全性漏洞，因为这些函数可能引 起缓冲区溢出，此时的安全性漏洞字典包含s t r c p y ，s t r c a t 等。 1 2 。4 基于语法和简单语义分析的安全性检查 基于语法和简单语义分析的安全性检查【1 7 】【1 8 1 的工作原理非常类似于编译器 系统，它以语法分析和语义规则为基础，同时加入简单的控制流分析和数据流分 析。因此这种方法具有较赢的分析效率和可扩展性，并且可以通过向程序中加入 !耍旦翌墨矍窒望苎主塑垫塑望坌塑一 注释信息的方式发现软件中广泛存在的安全性漏洞。如程序中出现机率最多的内 存访问漏洞，包括存储区的非法使用、空指针的脱引用、缓冲区溢出等等。它的 另一个优点是可适用于对大规模程序的分析。 1 2 5 基于信息流的安全性分析 长期以来，特别是随着网络技术的发展，计算机系统中的信息安全一直倍受 关注，主流方法是基于类型推理的信息流验证和检测【l9 】。信息流验证和检测方法 通过建立安全信息流验证的格模型( 1 a t t i c em o d e l ) 来提出了一种验证机制来确保 程序中信息流的安全性。该方法为信息指定一个集合的“安全类”，并用“流关系” 定义安全类之间允许的信息流，将程序中每个存贮对象绑定到特定的安全类。当 一个操作( 或者一系列的操作) 使用某些对象( 如x ) 的值，获得其他对象( 如y ) 的值，则引起从x 到y 的信息流。当且仅当给定的流策略中x 的安全类可以流向 y 的安全类，从x 到y 的信息流是允许的。 1 3 所采用技术方案的具体实施途径 根据上述分析可以看出，不同的安全性分析方法的区别仅在于程序分析方法 和安全性规则的内容不同。如上述的安全性漏洞字典、语义规则( 部分的) 、流策 略、基于程序分析的形式化验证中的属性规范等均属于安全性规则的范畴。 本文提出了图1 2 所示的框架，此框架的特点在于它将与安全相关的具体模式 从程序分析中剥离出来，从而以不同的方法解决最适合解决的问题。因为c c 抖 是编写系统程序的主流语言，c c + + 语言在多个领域得到了广泛的应用，同时 c ，c 十+ 由于其自身的语言特性，在提供给程序员对系统底层( 如对内存，外设) 灵 活的控制能力的同时，也带来了一些潜在的安全性问题( 如指针的错误使用，会 带来内存漏洞) 。所以本文选择c c + + 语言编写的源程序作为分析的目标，因为c 语言在语法上是c + + 语言的子集，本文将c ，c + + 程序统一当作c + + 程序来处理。 构建安全性规则的基础是寻求不同安全性漏洞的安全模式。由于软件系统， 特别是分布式环境的软件系统的多样性和复杂性，使得安全性漏洞种类繁多，不 可能解决所有这些问题。根据安全性漏洞的表现形式和在程序中出现的频度，以 及对系统造成的危害程度，本文确定了若干认为重要和具有代表性的安全模式， 第一章绪论 并根据这些安全模式的特征构建相应的安全规则。 分布式环境下安全性漏洞大多出现在以下几个方面【2 1 】：与c c + + 类型机制 漏洞相关的访问控制问题，如数组越界( 缓冲区溢出) 、指针非法或无效引用、不 加限制的类型转换等：与多进程相关的并发控制问题，如共享内存的不一致、 超时死等、缺少异常处理等；与分布式环境相关的信息流问题，如不明信息的 流入或大量信息的流出等。 程序分析是安全性检查的基础，根据不同的安全漏洞和对应的安全模式，程 序分析可以在词法、语法、语义等任何级别上进行。基于过程的传统程序分析方 法已经很成熟，如词法分析、语法分析、控制流分析、数据流分析等。 对于程序分析的研究，侧重于以下三个方面：将传统的程序分析技术( 特别 是控制流和数据流分析) 向面向对象的程序设计语言扩展；寻求当分析规模和复 杂性急剧增加的情况下降低程序分析复杂度的方法；研究与实现将不同的安全 性规则嵌入不同的程序分析中的方法。 图1 2 简化的安全性分析模型 1 4 程序分析 程序分析2 川是对源程序进行数据流分析，控制流分析获取程序中数据流和控 制流信息的一个过程。在软件的安全性分析中程序分析负责提取程序中某些信息， 以便和安全性规则相匹配，发现其中的安全性漏洞。程序分析包括控制流分析， 面向对象程序切片中的数据流分析 数据流分析，依赖分析等。因为程序切片在软件的安全性分析中有着十分重要的 作用，如在模型检验中自动提取程序模型，精简验证的程序的大小。同样在检测 程序中的一些安全性漏洞中，如缓冲区溢出，数组下标越界等问题1 2 ”，程序切片 可以辅助推导出变量或实参值的范围，从而能够更精确定位潜在的安全性漏洞。 所以在讨论常用的数据流分析算法同时，作为其一个非常熏要的应用，本文将讲 述如何在面向对象程序切片中应用数据流分析。 1 5 程序切片 程序切片技术在程序调试，测试，程序理解，逆向工程和软件维护等方面有 着广泛的应用。程序切片【2 4 】是一组可能影响到程序中某个点的某个变量v 的值的 语句或者谓词的集合。而( v ，i ) 被称作切片准则。这里v 也可以是一组变量。自 从m a r k w e i s e r 2 2 1 提出切片的概念，随着程序依赖图l ，系统依赖图】的出现，传 统的程序切片技术走向成熟。1 9 9 4 年以来，面向对象的程序切片逐渐成为研究的 主流。a k r i s h n a s w a m y 2 5 】利用一种面向对象的程序依赖图( o p d g ，0 b i e c t o r i e n t e d p r o g r a md e p e n d e n c eg r a p h ) 来计算面向对象的语句切片，但是o p d g 不能表示动 态绑定等问题，未讨论数据依赖的生成。m j h a r r o l d t 2 6 】和d l i a n g ，l d l a r s e n 2 7 】扩 展系统依赖图来计算面向对象程序的切片，在一定程度上解决了动态绑定和对象 参数的问题。这些程序切片方法都是基于依赖图的，而构造0 0 程序的依赖图是 非常复杂的工作，而且构造过程中容易出错，这会导致切片的结果不正确，造成 前功尽弃，李必信等提出了分层切片【2 8 】【2 9 】【3 0 】的思想，利用逐步求精的方法来得 到面向对象程序的分层切片。基于分层切片的思想，本文着手构造分析c + + 语言 的程序切片工具c s l i c e r 。 1 5 1c s l i c e r 的设计思想 面向对象的程序有着清晰的层次结构，如c + + 语言类由方法和成员变量组成， 方法由语句组成。c s l i c e r 在不同的层次分别构造不同的依赖图，并得到切片，以 满足不同的需要。 为了便于表述，本文给出下面一组概念【2 8 】： 类级切片：程序关于切片准则( v ，i ) 的类级切片是程序中可能影响到程序中点 i 的某个变量v 的值的类的集合。 方法级切片：程序关于切片准则( v ，i ) 的方法级切片是程序中可能影响到点i 的某个变量v 的值的类的方法和成员变量的集合。 需要指出，只要某个类、方法包含一条可能影响到某个变量v 的语句或谓词， 就认为这个类或方法可能影响v 。如果存在一条语句或谓词可能影响变量v ，而这 第一章绪论 条语句又使用了变量j ，则变量j 可能影响变量v 。 分层切片模型把c + + 源程序按逻辑结构分为三个层次，即类层、类中方法和 成员变量层，方法中的语句和变量层。 基于分层切片模型和切片准则，得到如下面向对象的分层切片算法的主要思 想：考虑切片准则( v ，i ) ，其中v 是任何一个方法中的一个变量或变量的集合，i 是方法中的一条语句。使用分层切片的方法来计算关于切片准n ( v ，i ) 的程序切片 ( 下面的p 代表可能包括多个类的c + + 源程序) 。 ( 1 ) 类层：计算类层次中影响切片准则( v ，i ) 的类，并把不影响切片准则或不 受切片准则影响的类从类层次结构中删除，从而得到关于切片准则( v ，i ) 的类间切片s ( p ) 。 ( 2 ) 成员方法和成员变量层：在上层基础上进一步计算单个类中影响切片准则 或受切片准则影响的成员方法和成员变量，删除那些与切片准则无关的成 员方法和成员数据，然后得到类内切片s ( p ) ，且有s ( j p ) 。s ”( j p ) ( 3 ) 语句和局部变量层：在上面工作的基础上进一步计算方法中与切片准则有 关的变量和语句，删除那些与切片准则无关的变量，语句和控制谓词等。 这一步的工作与传统的面向过程的程序切片一样，最后得到程序切片s ( j d ) ， 同时满足s ( j d ) 3s ”( | d ) is ( | d ) 。至此，得到了一个面向对象程序关于切片 准n ( v ，i ) 的程序切片。 1 5 2c s l i c e r 的实现 在实现c s l i c e r 时，本文确定一个c + + 语言的语法子集作为分析对象，而不考 虑模板，命名空间、异常等问题。c s l i e e r 可分成三层：语法分析层，依赖图生成 层，切片层。如图1 3 所示。 面向对象程序切片中的数据流分析 图1 3 分层切片工具的体系结构 语法分析层对c + + 源程序进行传统的语法分析和语义分析，并将得到的信息 以抽象语法树( a s t ) 的形式加以存储，本文采用自由软件基金会的开放源代码的编 译器g c c ( g n uc o m p i l e rc o l l e c t i o n ) 弛j 的前端来完成a s t 的生成，从而 避免繁杂的c + + 语法分析和语义分析。 依赖图生成层利用生成的a s t 中包含的信息，生成类级依赖图( c l d g ) ，方 法级依赖图( m l d g ) 和语句级依赖图( p d g ) 。 切片生成层利用三种依赖图逐级生成类级切片、方法级切片和语句级别切 片，语句级别切片又称为过程内切片1 2 4 l 。 1 5 2 1 依赖图生成层 i 类级依赖图( c l a s sl e v e ld e p e n d e n c eg r a p h ，c l d g ) 类级依赖图用来表示c + + 类之间的继承，实现和创建关系。c l d g 也是一个二 元组( n c ，e ) ，n c 是类的集合，e 是边的集合。若类c 1 中直接创建了一个属于 类c 2 的对象，在这里不妨说c 1 和c 2 有创建关系。如果类a 中直接创建了类b 的对象，则a 和b 之间有一条双向的“创建边”。如果类b 继承了类a ，则有一 条继承边从b 到a 。另外假设所有的函数和全局变量属于一个不存在的类s t a t i c 。 2 方法级依赖图( m e t h o dl e v e ld e p e n d e n c e g r a p h ，m l d g ) 第一章绪论 c + + 的类中成员函数和成员变量可以通过以下两种情况发生依赖关系：( 1 ) 多个 成员函数因共享某个( 某些) 成员变量而形成的直接定义或使用关系，简称 m s v ( m e t h o d ss h a r i n g v a r i a b l e s ) 关系；( 2 ) 通过调用其它成员函数来间接使用成员 变量而形成的调用关系，简称c r v ( c a l lr e l a t i o nv a r i a b l e s ) 关系。方法级依赖图刻 画了类成员变量和成员函数之间的m s v 和c r v 两种关系。而c r v 可以通过m s v 来反映。此时本文把成员函数的参数和返回值看作特殊的成员变量。而成员函数 中定义或使用的成员变量也被看作成员函数的隐含参数。如果成员函数m l 调用了 成员函数m 2 ，则m l 对m 2 的参数变量( 包括隐含参数) 进行了定义，同时，m l 使用了m 2 的返回值。以下提到的变量指成员变量或参数变量( 包括隐含参数) 。 方法级依赖图的生成算法描述如下： 1 如果一个类的成员函数m 使用了某个变量i ，则从m 到i 有一条使用边。 2 如果一个类的成员函数m 定义了一个变量i ，则从i 到m 有一条定义边。 3 如果类c 1 的成员函数m 1 可能调用类c 2 的成员函数m 2 ，则类c 2 的所有子 类的成员函数m 2 ( 可能被覆盖) 的参数( 包含隐含参数) 有一条定义边到成 员函数m 1 。 3 语句级依赖图( p d g ) 语句级的依赖图采用传统的程序依赖图f 2 4 1 ( p d g ) ，分别包含语句之间的数据 依赖和控制依赖。作为本论文中的工作，这部分依赖图的生成将在第四章中详细 描述。 1 类级切片 1 5 2 2 切片生成层 类级切片根据切片准则去除一些无关的类。 类级切片算法： 1 切片准则( v ，i ) 定位切片点i 所在的类c ，然后根据c l d g 找出c 结点沿创建边 能够到达的结点集合i 。 2 c l d g 找出从i 中的结点出发沿继承边可到达的结点集合i l ，i 和i l 的并集就 是要找的关于( v ，i ) 的切片s ( 尸) 2 方法级切片 方法级切片在类级切片的基础上进一步去除无关的类和成员函数。 方法级切片算法：由于基类的成员函数和成员变量会被子类继承，因此，首先 ! !耍鱼型墨堡空塑生主塑壑塑亟坌塑 根据切片准则( v ，i ) 定位切片点所在的成员函数的集合m o ，v 也可能代表多个 变量的集合v o ，然后根据m l d g 找出和i t l 结点有m s v 和c r v 关系的结点。算 法如下： 1 根据类级切片的第1 步，去除掉不属于集合i 中的类： 2 m = m o ：v = v 0 ： 3 i f m = ) t h e n 算法结束： f o r m 中的每一个结点m l 找出由m l 出发，有使用边到达的未被标记变量结点的集合v 1 ；v = v o r v 1 ： e n d f o r 标记所有属于m 的结点；m = ) ； 4 i f v = lt h e n 算法结束： f o r v 中的每一个结点v 1 找出由v 1 出发，有定义边到达的未标记变量结点的集合m 1 ；m = m o rm 1 ； e n d f o r 标记所有属于v 的结点；v = ) ； 5 回到第2 步。 算法结束后，所有被标记的变量和成员函数的集合就是要找的关于切片准则 ( v ，i ) 的方法级的切片s ( p ) 。 3 语句级的切片 采用传统的图的可达性算法，根据切片准则( v ，i ) ，后向查找沿数据依赖边和 控制依赖边可到达的所有语句结点的集合。 1 6 论文的主要工作 本文工作致力于完成面向对象程序( c 十一切片工具中数据依赖图的构造，因为 数据依赖图的构造可以归结到程序中到达定值信息的求解，所以本文主要阐述了 到达定值的求解算法以及相关的数据流分析问题，并讨论了算法的程序实现，以及 在程序切片中的应用。 文中工作使用的到达定值求解算法是对编译器代码优化领域中经典的到达 定值迭代求解算法的修改，使其适用于程序切片领域。在实现程序切片工具时， 利用g c c 编译器的前端完成对c + + 语言的词法分析、语法分析、语义分析，从而 使切片工具在语法上能够支持最新的c r + 语言标准，在g c c 生成的抽象语法树基 第一章绪论 础上实现程序切片，在程序实现到达定值求解算法时，因为求解算法基于控制流 图，本文提出了一种抽象语法树到控制流图的转换算法，并将其程序实现。在生 成控制流图后，需要获得各个控制流图结点处定义和使用的变量的信息，这些信 息需要在生成控制流图结点的同时从结点对应的抽象语法树结点处获得，通过对 各种情况下程序对应的抽象语法树的归纳总结，本文找到了获得各个控制流图结 点处定义和使用变量的统一的方法，根据到达定值的迭代求解算法，最终完成算 法的程序实现。 本文中工作基本上可以处理各种复杂数据类型存在时，到达定值信息的求解， 但在数组，指针存在时，分析的精度有待加强，可以采用数组区域分析和较为精 确的指针分析来提高分析的精度。 本文的章节安排如下： 第二章主要介绍g c c 的体系结构，g c c 的抽象语法树的具体表示形式，g c c 源程序中程序分析代码的嵌入等。第三章主要阐述了到达定值的求解算法以及 相关的数据流分析问题。第四章讲述了面向对象程序切片中到达定值求解算法 的实现。 面向对象程序切片中的数据流分析 第二章语法分析与抽象语法树 2 1c + + 源程序对应的抽象语法树的生成 在对c + + 源程序进行程序分析前( 数据流分析，控制流分析) ，通常需要对源 程序进行词法、语法分析。这些分析从源程序中提取信息，将源程序转换成其相 应的内存形式( 中间表示) ，以便后续分析可以方便地查询信息，提高查询速度， 减少查询的代价。本文选择a s t ( 抽象语法树) 【l l 】作为中间表示。通常源程序对 应的a s t 作为一种树结构，能够比较直观地表示出源程序语言的语法结构，具有 较高的存储效率，遍历和操作a s t 十分方便。 从c + + 源程序生成其相应的a s t 形式是后续的程序分析的基础。a s t 的具体 形式的选择，即a s t 中包含的信息的多少，影响程序分析的效率。a s t 中包含的 信息在满足程序分析需要的同时，包含的其他信息越少，分析的时空效率越高。 a s t 能否正确地生成决定后续的程序分析的成败。 如何选择a s t 的具体形式和正确地生成a s t 是项目的关键。因为c + + 的语法 结构相当复杂，为其选择相应的a s t 形式不但需要对其语法了如指掌，更需要相 当丰富的工程经验。编程实现从c + + 到a s t 的转换十分繁杂，需要大量的工作量。 为了保证生成的a s t 的正确性，需要做大量的测试工作。选择和生成一种能够表 示多种语言( c ，c + + ，j a v a ，a d a ) 的通用抽象语法树就更难了。通用的抽象语 法树将有利于程序分析工具对多种语言的支持。很多流行的编译器都将a s t 作为 其中间表示，编译器的a s t 需要包含足够详细的信息以便完成代码生成，在代码 生成前编译器需要通过数据流分析来完成代码优化。因为程序切片中的数据流分 析算法借鉴编译器代码优化领域中的数据流分析算法，只是粒度较粗而已( 基于 语句) ，所以本文选择编译器前端来生成a s t 。对于程序切片而言，编译器前端生 成的a s t 中包含的信息应该是冗余的，虽然这会影响分析的效率，但是因为耗时 的控制流分析和数据流分析基于控制流图( 从a s t 中提取控制流信息生成的) ，所 以对效率的影响不是太大。 程序分析部分需要对编译器前端生成的a s t 进行分析，因此要求编译器开放 源代码，以便能够提取编译器前端的代码或者将程序分析部分的代码嵌入到编译 器的源代码中，本文采用了后者。 在现存的开放源代码的c + + 编译器中( g c c 3 2 】【3 3 】1 3 4 】，s u i f 3 5 1 ，o p e nc - f + 3 6 ) 以美国自由软件基金会( f r e e s o f t w a r e f o u n d a t i o n ) 的g c c ( g n uc o m p i l e r c o l l e c t i o n ) 的影响力最广，最为稳定和成熟。g c c 是一个向上可接收多种语言， 第二章语法分析与抽象语法树 向下可支持多种平台的编译系统。g c c 在支持多平台的同时，依然能够生成简洁 的代码，这是其他编译器所达不到的。g c c 对最新的c + + 标准( i s o i e c1 9 9 8 ) 的支持最为完全，好于v c + + ，远好于o p e nc + + ，s u i f 的c + + 前端需要购买。 g c c 因为其优良的性能而得到了广大程序员的认可，成为了l i n u x u n i x 平台 c c + + 标准的编译器，从而得到了广泛的测试，系统不断更新。g c c 作为一个开 放源代码的遍译器汇集了全世界编译器爱好者的智慧，版本不断更新，支持的语 言和机器越来越多，这也是其它编译器所不具备的。 g c c 的抽象语法树作为一种通用的中间表示，可以表示多种语言( c + + ，c ， j a v a ，a d a ) 的语法特征，方便了后端的程序分析工具向其他语言的移植。最重 要的是g c c 的抽象语法树经过了广泛的测试，不会因为a s t 的错误引发后续分 析的失败。g c c 的抽象语法树提供各种精度的信息，o p e nc + + 生成的树结构粒 度较粗，程序分析不能获得精确的结果，可扩展性较差。g c c 的树结构十分稳定， 变化较小，s u i f 的树结构新版本同原版本相比发生了很大的变化。 所以本文选择g c c 作为下一步工作的基础，重用g c c 的前端来完成对c + 十 源程序的语法分析、语义分析，生成其相应的a s t 。利用g c c 提供的a p i 来完成 对a s t 的解析、遍历和操作，在a s t 的基础上进行下一步分析。 g c c 在提供多语言、多平台支持的同时，也致使其程序代码十分庞大( 大约 8 0 m ) 。本文只需要g c c 的前端来完成抽象语法树的生成，并不需要其完成整个 编译过程。所以需要对g c c 的源代码系统进行定制，或者通过g c c 的命令行选 型来控制g c c 编译c + + 程序的过程，使其在生成抽象语法树后停止编译。本文采 用了两者相结合的方法，具体方法将在2 2 4 节中讲述。 g c c 是整个程序切片系统的基础，本文将在2 2 节对其进行较为详细的介绍。 s u i f 、o p e nc + + 虽然未被本系统所采用，但这些编译器系统同样十分优秀。因为 这些系统同g c c 一样是开放的，可扩展的，s u i f 甚至提供了数组数据依赖分析 模块。这些系统同g c c 相比，程序代码短小，容易分析。只是本文更看重g c c 对c + + 语言的更为完全的支持，g c c 的抽象语法树更为稳定和通用而已。s u i f 在 并行编译领域，o p e nc + + 在程序理解、逆向工程领域都得到了广泛的应用，所以 在2 3 和2 4 节将对s u i f 和o p e nc 抖作简要介绍。 面向对象程序切片中的数据流分析 2 2g c c ( g n x ic o m p i l e rc o l l e c t i o n ) 2 2 1g c c 简介 g c c 是美国自由软件基金会( f r e e s o f t w a r ef o u n d a t i o n ) 开- 发的且流传广泛的编 译程序集合的简称( g n uc o m p i l e rc o l l e c t i o n ) 。该编译程序集合是一个向上可接牧多 种语言，向下可支持多种平台韵编译系统。它辑接收筑语言有c ，c 抖，o b j e c t c + + 和f o r t r a n ，j a 、，a ，a d a 。 c 程序 j a v a 程序 机器描避文件 目标机器辐述宏 j a 、，a p a r s e r 兰 ，_ e 乏 语法树 篁 r t l 生戍 r t l 中间语言 机器无关的优化 j u m p 优化 公共子表迭式删除 循环优化 数据流分析 机器相关的优化 擂今调度 局部寄存嚣分配 全局寄存嚣分配 j u m p 优化 延迟分, ) i a , t , 4 9 j r 蝙代码生成 汇编代骂 a d a 程序 a d a p a r s e r o b 压c t 、 、! ：竺生， 主 。售拒c tc ，+ p a r s e r 图2 1g c c 的体系结构 g c c 编译系统主要由三部分组成：与语言相关的蘩端、与语言无关的后端以 及与机器相关的机器描述。g c c 的前端由与源语言关系密切的语法分析、语义分 析部分组成，它对源程序进行分析后将其转换为撼象语法树。g c c 的后端为编译 蒜善 第二章语法分析与抽象语法树 系统的主体部分，它将抽象语法树转换成后端中间语言r t l ，在此中间语言基础 上进行各种优化，并完成代码生成。机器描述部分则描述g c c 所运行的宿主机 和目标机的操作系统、体系结构、指令系统等有关系统与硬件的情况，并提供给 编译程序的后端使用。这样，采用不同的机器描述，将得到适合于在不同机器与 系统上运行的g c c 版本。图2 1 是g c c 的体系结构，它反映了这三部分的关系与 作用。这三部分既相对分离又相互配合，完美地实现了g c c 面向多语种、支持多 平台的思想。 面对众多不同的系统与体系结构，支持多平台的编译程序，必须解决三个根 本的问题：1 需要设计一种对目标机恰当的描述，这种机器描述既要能描述系统与 硬件的共性，也要能描述它们各自的特性，同时还要适合于编译程序的处理；2 需 要设计出一种较好的中间语言，这种中间语言应当在适当的层次上，向上能支撑 多语言的映射，向下能适合多平台转换并且适合于进行各种优化；3 在机器描述与 编译主体之间需要仔细地设计一种统一接口。g c c 编译系统的独特设计解决了这 三个问题，从而获得了成功。 2 2 2g c c 的抽象语法树 g c c 的抽象语法树作为一种通用的中间表示，不仅可以表示各种语言通用的 语法结构，同时也包含特定类型的树结点来表示各种语言特有的语法结构。g c c 的抽象语法树表示中包含各种类型的树结点，分别与语言不同层次的语法结构相 对应，g c c 的抽象语法树表示十分直观。 ( 1 ) c + + 中的标识符( 变量名，函数名) 在g c c 的抽象语法树中有相应类型的 树结点i d e n t i f i e rn o d e 。 ( 2 ) c h 中的各种类型在抽象语法树中有相应类型的树结点与之对应，如s t m c t ， c l a s s 对应c o r df 即e ，u n i o nt y p e 和u n i o n 对应，a r ra yt y p e 和数组对应，f u n c t i o nt y p e 和函数的返回类型对应，m e t h o dt y p e 和类中成员函数的返回类型对应等。 ( 3 ) c + + 中的各种声明在抽象语法树中有相应类型的树结点与之对应，如 c o n s t _ d e c l 与常量声明对应，v a rd e c l 与变量声明对应， t e m p l a t e _ d e c l 与模板声明对应，p a r a m _ d e c l 与参数声明对应， t y p ed e c l 与t y p e d e f 声明相对应等。 ( 4 ) 对于c + + 中的成员函数和函数，g c c 抽象语法树中的f u n c t i o nd e c l 类型树结点与之对应。 ( 5 ) c + + 中的c l a s s 作为一种抽象数据类型，与抽象语法树中的r e c o r dt y p e 6面向对象程序切片中的数据流分析 类型的树结点对应。 ( 6 ) c + + 中的各种语句在抽象语法树中有相应类型的树结点与之对应： 如f o rs t m t 对应f o r 语句，w h i l es t m t 对应w h i l e 语句，i fs t m t 对应i f - e l s e 语句，s w i t c hs t m t 对应s w i t c h 语句，e x p rs t m t 对应各 种表达式语句( 赋值语句，函数调用语句) 等。 ( 7 ) g c c 抽象语法树中表达式类型的树结点对应c + + 中各种表达式。 p l u se x p r 和数学表达式中加法表达式相对应。各种常量中， i n t e g e rc s t 对应整形常量，等等。 g c c 的抽象语法树是一种层次化的中间表示。同c + + 语言中的语法嵌套相对 应，各级语法结构对应的抽象语法树也是嵌套的。如每个函数对应的抽象语法树 结点中包含函数中语句对应的抽象语法树结点的引用，类对应的抽象语法树结点 中包含类中成员变量和成员函数对应的抽象语法树结点的引用。而类中的成员函 数比较特别，成员函数对应的抽象语法树结点中包含所属类的抽象语法树结点的 引用。 g c c 的各种抽象语法树在g c c 源程序中均用相同的类型t r e e 来表示，树( t r e e ) 是中间表示所使用的核心数据结构。一个t r e e 类型的变量可以是一个树结点，也 可以是一棵子树。 在g c c 中，t r e e 类型的声明为： t y p e d e f u n i o nt r e e _ n o d e + t r e e ； 因此，t r e e 本身就是指针类型。由于t r e e 的类型为u n i o n ，而t r e en o d e 中的各 个域对应不同类型的抽象语法树结点的声明，所以t r e e 类型的变量可以指向各种 类型的抽象语法树结点。 g c c 的各种抽象语法树均提供相应的a p i ( 以宏的形式提供) ，以便从抽象语 法树结点中提取各种信息和操作语法树，方便了后续分析和代码生成。 2 2 3g c c 的抽象语法树及其a p i 的使用 在简要介绍了g c c 的抽象语法树后，本节将以图的形式介绍各种类型的抽象 语法树结点的具体形式，如何利用g c c 提供的a p i 遍历抽象语法树，从抽象语法 树结点中获得特定信息。因为g c c 的抽象语法树结点种类较多，本节中只介绍本 文中使用的部分抽象语法树结点。 ( 1 ) 函数结点 函数和成员函数表示为f u n c t i o n d e c l 类型的树结点。假定有一个指向函 数对应的树结点的指针，称作f n d e c l ( 在g c c 源程序中，全局变量 c u r r e n t _ f u n c t i o n _ d e c l 为一个指向当前被分析函数对应的抽象语法树结点的指 第二章语法分析与抽象语法树 针