（计算机软件与理论专业论文）cc程序分析中若干关键技术的研究.pdf

摘要 本文的研究作为软件系统安全性分析项目的一部分，主要涉及了程序分析器中 的若干关键技术，包括控制流图、控制依赖图、和类层次图理论与实现。它们是 面向对象系统依赖图的组成部分，构造这些图形表示的目的是为安全性分析提供 手段。 文中使用g c c 抽象语法树的映像文件作为程序分析的基础，简化了词法、语法 分析的过程。在此基础上，通过分析抽象语法树获取类及方法的信息，建立类层 次图；同时遍历抽象语法树，以语法制导的方式构造控制流图；控制依赖图的实 现采用基于图论的方法，首先计算后必经结点树，再根据结点的必经边界集合计 算控制依赖。本文的研究基本完成了对这几种图的构造，但是面向对象的一些特 征，如多态，对过程间控制流和控制依赖关系带来的影响仍然有待于深入研究。 关键词：程序分析控制流图控制依赖图类层次圈抽象语法树 a b s t r a c t s o m ek e yt e c h n i q u e si nt h ef i e l do fp r o g r a ma n a l y s i sh a v eb e e ns t u d i e di nt h i s p a p e r , 私ap a r to f ap r o j e c to f s a f e t ya n a l y s i so fs o f t w a r es y s t e m i n c l u d i n gt h e o r ya n d i m p l e m e n t a t i o no fc o n t r o lf l o wg r a p h ( c f g ) ，c o n t r o ld e p e n d e n c eg r a p h ( c d g ) a n d c l a s sh i e r a r c h yg r a p h ( c h g ) a l lo ft h e ma r ee n c o d e di n a i l o b j e c t - o r i e n t e ds y s t e m d e p e n d e n c eg r a p h ( o o s d g ) i n l ei m p l e m e n t a t i o no f o o s d g d u m po fg c c sa b s t r a c ts y n t a xt r e e ( a s t 】i s u s e dt o s i m p l i f yl e x i c a l a n ds e m a n t i c a n a l y s i s t h ea l g o r i t h mg e t si n f o r m a t i o no f c l a s s e sa n dm e t h o d so nt h ea s tt ob u i l dc h g a n dc f gi ss y n t a x d i r e c t e de x t r a c t e db v p a s s i n gt h r o u g h t h ea s t g r a p h t h e o r yi su s e di nt h ec o n s t r u c t i o no f c d g f i r s t l y , c f g i sr e v e r s e dt or e v e r s e d - c f gt h e np o s t - d o m i n a t o rt r e ea n dd o m i n a n c ef r o n t i e r a r e c o m p u t e do r d e r l y f i n a l l y ，c d gi sb u i l ta c c o r d i n gt h ed o m i n a n c ef r o n t i e r t h i sp a p e r c o m p l e t e sc o n s t r u c t i o no ft h e s eg r a p h s h o w e v e r , t h ei n f l u e n c eo fo b j e c t - o r i e n t e d l a n g u a g e sc h a r a c t e r s ，s u c ha sp o l y m o r p h i s m ，p o l y m o r p h i s mt oi n t e r - p r o c e d u r ec o n t r o l f l o wa n dc o n t r o ld e p e n d e n e ei ss t i l lf o r f i 1 r t h e rs t u d y k e y w o r d ：p r o g r a ma n a l y s i s c o n t r o lf l o wg r a p b ( c f g ) c o n t r o l d e p e n d e n c eg r a p h ( c d g ) c l a s sh i e r a r c h yg r a p h ( c h g ) a b s t r a c ts y n t a x t r e e ( a s t ) 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：苎! ) 墨! 叠 日期 关于论文使用授权的声明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果是署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全 部或部分内容，可以允许采用影印、缩放或其他复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本论文属于保密在一年后适用本授权书。 本人签名： 导师签名： 日期 第一章概述 第一章概述 1 1 问题的提出 本文的工作源于“十五”预研课题“软件系统安全性分析”。该课题主要面向 军事电子信息系统，重点解决被广泛应用的程序设计语言c c + + 的程序分析技术 和面向不同领域的软件安全模式构建技术，最终提供一组与安全分析相关的方法， 并研制出一个基于静态分析的软件系统安全检查工具原型。 随着网络技术的发展和自由软件的广泛使用，软件的安全，特别是军事领域软 件的安全已越来越受到人们的重视，它已经成为影响计算机安全的最大问题之一。 由于计算机的安全性隐患( 包括无意的和人为的) 大量存在于软件系统中，如系 统入侵、信息窃取、病毒、以及由于程序设计语言自身问题造成的各种安全漏洞 等，使得软件通常不够健壮，导致软件在使用阶段会发生意想不到的软件故障， 从而造成重大损失。 对于自主开发的软件，主要通过测试的方法检查所有可能的不安全因素。这需 要对软件的功能、特性等具有深刻了解，并且根据软件特性设计完备的测试集。 显然这种动态测试的方法并不适用于使用可重用软件的情况。因此，如何能在静 态( 不运行) 时尽量检测出软件的安全性问题，避免不必要的损失，成为当静计 算机安全领域中需要研究的一个重要课题。 针对这一问题，学者们撼出了不同的解决方案。如应用于固定的代码提供者和 使用者之间的携带验证代码( p r o o f - c a r r y i n g c o d e ，简称p c c ) “”3 技术；基于演绎 推理和归纳推理的定理证明“”“”“”技术；基于时序逻辑和自动机理论的模型 检验。”“。”“删1 技术。目前主流的验证软件安全性的方法是基于程序 分析的安全性检查。 1 2 程序分析 程序分析的目的是不用运行程序而提取程序运行时的信息。程序分析是静态安 全性检查的基础，任何方法都建立在程序分析的基础之上。人们在该领域进行了 长期、大量的研究工作，具体归纳为以下几种方法。 ( 1 ) 基于词法分析的安全性扫描【v 嘲0 0 1 ( 2 ) 基于信息流的安全性分析”州“”1 阻叽“”1m 1 ” ( 3 ) 基于语法和简单语义分析的安全性检查4 “删 2c ，c + + 程序分析中若干关键技术的研究 这三种方法中，第一种方法具有简单、高效的优点，但是精度较低，不适用 于精确的静态分析，而且可检查出的安全性漏洞种类有限；第二种方法的主要弱 点是要求在验证时知道变量的安全类，因此不适合对某些软件如遗产代码( 1 e g a c y c o d e ) 等的分析：第三种方法的工作原理非常类似于编译器系统，它以语法分析 和语义规则为基础，同时加入简单的控制瀛和数据流分析。因此这种方法具有较 高的分析效率和可扩展性，并且可以通过向程序中加入注释信息的方式发现软件 中广泛存在的安全性漏洞+ 如程j 芋中出现机率最多的内存访问漏洞( 包括存储区 的非法使用、空指针的脱引用、缓冲区溢出等等) 。它的另一个优点是可适用于对 大规模程序的分析。 1 3 解决问题的总体方案 我们建立的软件安全分析工具的总体框架如图1 1 所示。在该框架下，不同 的安全性分析方法的区别仅在于程序分析方法和规则的内容不同。此框架的特点 在于，它将与安全相关的具体模式从程序分析中剥离出来，从而以不同的方法解 决最适合解决的问题。 图1 1 简化的安全性分析模型 此框架中的主要部分有： ( 1 ) 程序分析器 程序分析嚣是安全性检查的基础，它的主要作用是解析c i c + + i 嬲，对程 序进行控制流，数据流分析和类层次分析，构建面向对象的程序依赖图，为安全 分析提供分析平台。该部分中需要解决的问题主要有 提取和表示程序中的信息。 第一章概述 基于过程的传统的程序分析方式的扩充，以适应分析面向对象程序的需要。 保证程序分析和安全分析之间的独立性。 为安全分析提供一个多层次化的接口，是安全分析可以在词法，语法，语义 等不同的层次上进行。 ( 2 ) 安全分析器 安全分析器的主要作用是根据安全性规则，形成一定的安全模式，在程序分 析器提取的信息的基础上，使用多种分析手段，查找程序中的安全性漏洞。这一 部分应重点解决的问题有： 结合程序分析提供的接口，将安全模式的数学模型转换为具体的实现。 实现安全分析和安全模式的分离，即安全模式的可扩充性。 ( 3 ) 安全性规则 安全性规则是在对安全漏洞分类的基础上形成的，对安全漏洞的一种描述。 它具有普遍性和特定性的特点，朗每一条安全性规则只针对某一类特定的安全漏 洞，并且是对这一类漏洞的共同特点形成的具有普遍适用性的描述。该部分需要 解决的重点问题有 对安全漏洞进行有效的分类。 将安全漏洞抽象为数学模型。 1 4 本论文的研究工作 本文主要涉及到原型中程序分析器部分若干关键技术，重要包括控制流图、控 制依赖图、和类层次图的设计与构造。程序分析器分析的目标是c c + + 语言编写的 源程序，为了适应分析面向对象语言的需要，文中使用面向对象的系统依赖图作 为分析时程序的静态表示。 文中首先讨论程序分析器部分的总体设计，以及程序分析和安全分析之间的 接口，这一部分主要解决的问题是如何表示程序的信息，以及分析接口的设计。 接下来重点研究了程序分析器中三种图的算法和实现。其中控制流图表示程序的 控制流信息，文中主要研究了在g c c 的抽象语法树上以语法制导的方式获取控制 流图问题；控制依赖图是系统依赖圈的重要组成部分，文中研究了以控制流图为 基础，通过构造后必经结点树的方法获得控制依赖图的方法；另一个重点研究的 问题是类层次图的表示，以及c + + 语言特点对类层次图带来的影响和在g c c 的抽象 语法树上提取类层次图的方法。 4 c ，c + + 程序分析中若干关键技术的研究 1 5 论文组织 论文的其他部分是如下组织的。在第二章中，介绍了程序分析器部分的整体框 架，和安全分析接口的设计方案。在第三章中，研究了程序分析器中三种图和它 们的关键技术，分别是：控制流图，控制依赖图和类层次图。第四章着重于这三 种图在具体实践中的实现。 第二章程序分析器部分简介 第二章程序分析器部分简介 程序分析器是软件静态安全分析工具的一个组成部分，它的主要作用是解析 c c + + 源程序，提取程序中的信息，对程序进行控制流，数据流分析和类层次分析， 构建面向对象的系统依赖图，为安全分析提供分析平台。 2 i 1 程序依赖图 2 1 面向对象的系统依赖图 程序依赖图( p r o g r a md e p e n d e n c eg r a p h ，p d g ) 是程序的一种图形表示，它包 括控制依赖子图( c o n t r o ld e p e n d e n c es u b g r a p h ，c d s ) 和数据依赖子图( d a t a d e p e n d e n c es u b - g r a p h ，d d s ) ”一。其中c d s 包含了程序中的控制依赖；d d s 是一个程序中语句之间所有数据依赖的集合。d d s 包含语句间的数据依赖，可通过 在c d s 的结点之间插入数据依赖边来构造d d s 。 2 1 2 系统依赖图 程序依赖图是为单个过程定义的，但实际的程序一般是由多个过程组成的。系 统依赖图( s y s t e md e p e n d e n c eg r a p h ，s d g ) 就是来描述由多个过程相互作用而构 成的复杂程序。形式地说，它是由一个p d g 和一组过程依赖图( p r o c e d u r e d e p e n d e n c eg r a p h ，p r d g ) 构成的有向、带标记的多重图“。p d g 模型化软件系 统中的主程序，p r d g 模型化软件系统中的多个过程体。s d g 可以用来处理过程间 的数据流和控制流，并能表示参数传递。 2 1 3 面向对象的系统依赖图 传统的s d g 只能描述过程程序，要描述面向对象的程序，必须扩充s d g 增加能 够全面描述面向对象程序静态特征的表示方法。为此，a k r i s h n a s w a m y k “5 州【8 n 9 4 1 在s d g 中加入类层次子图( c l a s sh i e r a r c h ys u b g r a p h ，c h s ) ，得到面向对象的 系统依赖图( o b j e c t 一0 r i e n t e ds y s t e md e p e n d e n c eg r a p h ，o o s d g ) 。o o s d g 是类层 次子图、控制依赖子图和数据依赖予图、过程依赖子图这几种表示方法的并集。 其中类层次子图用图形来表示类间的继承关系。 2 2 程序分析器的整体框架 图2 1 程序分析器部分框架圉 程序分析器的整体流程如图2 1 所示，其中阴影部分是本文中重点解决的关键 问题。程序分析器的构造可以分为下面几个部分： ( 1 ) 建立抽象语法树( a b s t r a c ts y n t a xt r e e ，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 ) 编译c c + + 源程序 产生的抽象语法树映像( d u m p ) 文件作为建立抽象语法树的基础。抽象语法树是g c c 编译器前端对程序的一种中间表示，它含有g c c 后端进行编译需要的关于源程序 的所有信息。g c c 的抽象语法树可以通过编译时提供的参数存放于文件中。就是抽 象语法树映像文件。我们可以通过很简单的词法和语法分析就将映像文件恢复到 内存中，这样做避免了对源程序进行复杂的词法和语法分析，又保持了和g c c 的 一致性，面向实际的编译环境。程序分析器的第一个任务就是完成对映像文件的 分析，将抽象语法树恢复到内存中。 ( 2 ) 建立符号表 符号表中记录了程序中每个符号的信息。建立符号表的主要目的是为安全分析 提供方便。 ( 3 ) 建立控制流图( c o n t r o lf l o wg r a p h ，c f g ) c f g 建立在a s t 的基础上，控制流信息能够指出在程序的每个程序点接下来可 能执行的程序点，它是进行控锚依赖和数据依赖分析的基础。本文中使用的建立 第二章程序分析器部分简介 c f g 的方法是，遍历a s t ，对于不同结构的语句进行不同的处理，以语法制导的方 式建立控制流图。 ( 4 ) 建立o o s d g 程序分析的核心任务是建立3 1 节介绍的o o s d g 。它的构造包括下面几个部分。 从抽象语法树中提取类及方法的信息，建立c h s ；建立后必经结点树 ( p o s t d o m i n a t o rt r e e ，p d t ) ，根据结点的必经边晃( d o m i n a n c ef r o n t i e r ，d f ) 集 合计算c d s ；根据到达一定值信息和指针别名信息计算d d s 。 2 3 程序分析器提供的接口 接口的设计应当符合层次性和独立性的原则。 ( 1 ) 层次性 程序分析器提供的接口要能使安全分析在词法，语法，和语义等不同的层次上 进行，我们在程序分析器中为安全分析提供了两种分析接口。一种建立在抽象语 法树的基础上，安全分析可以在遍历抽象语法树时进行词法和语法分析。另一种 建立在控制流图的基础上，安全分析可以在控制流图中获取程序的控制流，数据 流信息，也可以向上获得函数所在类的类层次信息，从而进行语义一级的分析。 这两种方法可以结合起来使用，也就是说，程序在访问抽象语法树时可以根据抽 象语法树和控制流图的关系，获得控制流图的信息，反之亦然。 ( 2 ) 独立性 程序分析器提供的接口还必须与安全分析互相独立，这样安全分析就能够在不 改动分析接口的情况下进行扩充。为此我们使用设计模式中的访问者模型 ( v i s i t o r ) 封装对抽象语法树和控制流图的访问，使用创建者模型( b u i i d e r ) 封装每条安全规则对应的安全分析程序，简单的说就是v i s i t o r 负责结点访问， b u i i d e r 负责对结点分析。接口框架如图2 。2 所示。图中只表示出抽象语法树的 v i s i t o r 和两个在抽象语法树上进行安全分析的b u i i d e r ( c o n c r e t e b u i l d e r l ， c o n c r e t e b u i i d e r 2 ) 。在分析的过程中，v i s i t o r 负责遍历抽象语法树，访向到一 个新的结点，调用该结点的访问函数，如访问到函数定义结点，则调用 v i s i t f u n cd e c l 0 函数。在函数中，根据b u i l d e r 的列表，逐一调用所有b u i i d e r 的函数定义结点分析函数p r o c e s s f u n c _ d e c l ( ) 。 这种接口方式的优点在于，将对结点的访问和对结点的分析分离，保证安全分 析的独立性；同时由于结点访问函数根据b u i i d e r 列表逐一调用结点分析函数， 所有的b u i i d e r 都分析完一个结点后才进行下一个结点的分析，所以不同的安全 分析可以并行的进行，从而减少对结点的访问次数，提高效率；另外，针对不同 规则的安全分析被封装在不同的b u i l d e r 中，也保证了安全分析之间的独立性； 在分析的过程中，如果在进入结点时调用分析函数，可以进行继承属性的计算 如果在离开结点时调用分析函数，可以进行综合属性的计算。 圈2 2 程序分析器提供的接口模型 2 4 上一级研究生所做的工作 程序分析器作为软件安全分析原型工具的一部分，从上一级研究生开始，已经 进行了相当的研究工作。他们在阅读了许多关于软件安全和程序分析技术的论文 之后，进行了大量的研究工作，最终确立圈1 1 所示的一个简化的软件安全分析工 具模型，设计出程序分析部分的总体框架，提出在程序切片的基础上进行程序分 析的方案，研究并部分地进行了将程序分析罄嵌入到g c c 编译器中的实践。 总体方案上，他们直接将程序分析嵌入到g c c 编译器中，利用g c c 的抽象语 法树进行分析。我们的实现中没有使用这一方案，而是利用抽象语法树的映像文 件进行分析。另外他们强调使用程序分层切片的方法，但是因为面向对象的切片 技术目前还不成熟，面向对象语言的一些特征，如动态绑定使得在程序的静态表 示- - o o s d g 上进行的切片难以做到精确，所以我们没有采用。就与本文相关的部 分具体地讲，陆伸达独m l 完成了部分语句控制流图的生成，并且程序中不能含有 循环嵌套和g o t o 语句：李慧贤【+ 0 3 】完成了后必经结点树的算法设计，她希望使用 一种扩展的后必经结点树的形式，作为控制依赖的优化表示，以减少空间的开销。 但是本文认为，使用传统的控制依赖图表示方法在空间上是可以接受的，这一部 分将在3 ，2 8 讨论。任凌燕1 “0 3 】完成了类层次图的设计，但因程_ | 芋嵌于g c c 中所 第二章程序分析器部分简介 9 限，分析只能在函数级进行，算法的效率较低。 他们的研究基本确立了项目发展的方向，也给本文的工作带来了很大的帮助， 使我们少走t * t t 多的弯路。我们实现的o o s d g 是面向对象程序切片的基础，虽 然本文中没有使用程序切片的方法，但随着项目的深入和面向对象程序切片技术 的成熟，在以后的工作中切片技术仍然是研究的一个重要的课题。 第三章关键技术的解决方案 第三章关键技术的解决方案 本章的工作致力于三个方面的问题。首先是控制流图，控制流图是程序理解的 重要手段，也是建立控制依赖图和数据依赖图的基础。对于程序分析器来说，控 制流图是程序分析器中重要的一环；本章解决的第二个问题是控制依赖图的计算， 确定了从控制流图计算控制依赖的算法，郎首先建立后必经结点树，然后计算每 个结点的必经边界集合，最后确定结点的控制依赖关系；类层次图是本章关注的 另一个问题，对于面向对象程序分析来说，类层次图是描述程序中类之间，类与 成员间关系的重要手段。 3 1 1 控制流图的概念 3 1 控制流图的关键技术 对于程序分析来说，理解程序的控制流是十分必要的。控制流信息指出在程序 的每个程序点接下来可能执行的程序点。传统的控制流分析是在基本块的构造的 控制流图基础上进行的，用于编译的程序优化阶段，主要分析控制流图中的块和 循环结构，其中的基本块是指一连续的语句序列( 通常为三地址码) 。在基本块中， 控制流从块的开始进入，并从它的末尾离开，没有停止或分支的可能性。对于三 地址码这样的低级语言来说，对应的控制流图很容易构造，因为程序中从一点到 另一点的控制流信患是很明确的。但对于高级语言，情况就不同了：在源程序中 的控制流信患往往是不明确的，这是由于在高级语言中存在复杂的语句结构，并 且函数可以像数据一样被传递，并可以在程序中的任意一点调用。所以需要控制 流分析去求解高级语言中的控制流信息。 定义3 1 控制流图”“”舢是一个有向图6 = ( kd ，矿是结点的集合， f 是有向边的集合。其中结点表示语句。边v 表示从到v 可能的控制流。当 控制流图的边离开一个条件( 谓词结点) 时标记为t ( 表示t r u e ) 或f ( 表示f a l s e ) ， 否则没有标记。逆控制流圈( r e v e r s ec o n t r o lf l o wg r a p h ，r c f 6 ) 是一个有向图 矿，它于控制流图6 相对应，与占有相同的结点，对于6 中任意边n 矿 中有边附茁相对应。 令( “力仨f 表示控制流图中的边h n 则称是v 的前趋，v 称为“的后继； 语句矿的所有前驱组成的集合称为矿的直接前驱集，记为p r e 以曲，旷的所有后继 1 2 c c h 程序分析中若干关键技术的研究 组成的集合称为甲的直接后继集，记为s u c c ( 神。另外，为g 增加了两个特殊的结 点：s t a r t 称为开始结点或入口，它没有前趋，从它可到达每个结点；s t o p 称为 退出结点或出口，它没有后继，从每个结点都可到达它。一个程序可能有几个结 束语句。为了保证控制流图中终点的唯一性，所以在图中加入一个虚结点翩岛p ， 并将所有结柬语句对应的结点都指向它。为了方便求控制依赖，加入一条从s t a r t 到s t o p 的边，这样在后面求控制依赖时就不用再扩充一个谓词结点了。 c 程序中语句基本上可分为以下几种类型： ( 1 ) 简单语句：一般的表达式语句、函数调用语句等： ( 2 ) 复合语句：i f 语句、w h i l e 语句、f o r 语句、d o - w h i l e 语句、s w i t c h 语句 等，这些语句影响整个程月中的控制流程； ( 3 ) 谓词部分：即条件语句和循环语句的判断部分，为了方便处理，在建立结 点时可以将信息加入到复合语句结点的信息里，并将这种复合语句称为谓 词结点。 ( 4 ) 跳转语句；跳转语句又分为结构化转移语句和非结构化转移语句。结构化 转移语句包括b r e a k 、c o n t i n u e 语句，非结构化转移语句包括g o t o 语句。 对于c + + 语言，基本的语句类型与c 语言相同，增加了n e w 和d e l e t e 语句。 对于n e w 和d e l e t e 语句，实际上在编译过程中处理成调用对应对象的构造酯数和 析构函数，因此对于这两种语句的处理可以等同于函数调用语句。本文中暂时先 不考虑函数和方法调用语句，把它们当成简单语句来处理a 传统的控制流图的边离开一个条件( 谓词结点) 时至多有两条边，标记为r ( 表 示t r u e ) 或，( 表示f a l s e ) ，否则没有标记。c c + + 语言中的s w i t c h 语句是一个 特殊的语句，从这条语句出发，可能有多于两条边。针对这种特点，本文对控制 流图的概念进行了拓展，把s i t c h 语句的条件作为一个特殊的谓词结点，离开该 结点的边可以有多条，并不做标记。 3 1 2 控制流图的具体形式 在本节中我们使用语句的行号来表示该行的语句。 ( 1 ) 简单语句 简单语句包括表达式语句和函数调用语句，它的控制流图如图3 i 所示，形式 比较简单，只有一条没有标记的边从简单语句结点出发连向下一个结点。 第三章关键技术的解决方案 0 0 1 ：a=a+b 0 0 2 ：b + + ： 图3 1 简单语句的控制流图 ( 2 ) i f 语句 i f 语句是分支转移语句，它的控卷4 流图如图3 2 。一般情况下，从i f 语句的 谓词结点出发两条边，分别标记为t 和f ，标记为t 的边指向t h e n 子旬中第一条 语句，标记为f 的边指向e l s e 子句中的第一条语句。从t h e n 和e l s e 子句的最后 一条语句分别有一条无标号边指向i f 语句的下一条语句。如果t h e n 或e l s e 子句 为空，则从谓词结点指向该子句首语句的边直接指向i f 语句的下一条语句。 图3 3v h i l e 语句的控制漉图 ( 4 ) d o - w h i l e 语句 d o - w h i l e 语句也是循环语句，它的控制流图与w h i l e 语句的控制流图类似， 只是控制流进入语句的位置不同，具体形式如图3 4 所示。在w h i l e 语句中控制 流先进入条件语句，再进入循环体；而在d o w h i l e 语句中，控制流的进入的顺序 刚好相反。从谓词结点出来的标号为t 的边指向d o _ w h i l e 语句体的第一条语句， 聿 ! ! 曼丝竺壅壹坌堑生薹王羞焦堇莶盟墅塞 标号为f 的边指向d o j h i l e 语句的下一条语句。 l ：曲 0 0 2 ：a + + ： 0 0 3 ：b = a + b 0 0 4 ： j 蚰i l e b 0 ) ： 0 0 5 ：p r i n t f ( 材，b ) ： 图3 4d 0 1 h i l e 语句的控制漉凋 ( 5 ) f o r 语句 f o r 语句豹控制流相对于其他循环语句复杂，如图3 5 所示。控制流首先进入 的是f o r 语句韵初始赋值语句0 0 2 。然后从初始赋值语句流向f o r 语句的条件语句 0 0 3 ，如果条件满足，则沿着标号为t 的控制流边流向f o r 语句的语句体，反之则 沿着标号为f 的控制流边流向f o r 语句的下一条语句。当进入语句体的控制流从 f o r 语句的语句体的最后一条语句中流出时，将沿着一条无标号的控制流边进入 f o r 语句的改变步长表达式0 0 4 ；最后再从表达式部分流出，进入f o r 语句的条件 语句。 1 ：f a r ( 0 0 2 ：i = o ： 0 0 3 ：i ( i o ： 0 0 4 ：i 抖) s ： 0 0 6 ：a = a + l o o t ： 8 ：p r i n t f ( 材i ) 图3 5f o r 语句的控制流图 ( 6 ) s w i t c h 语句 s w i t c h 属于分支转移语句，从s w i t c h 条件语句出发的控制流边都是无标号的。 控制流在s w i t c h 条件语句选择满足条件的分支进入，如果没有满足条件的分支， 则进入d e f a u l t 分支，如图3 6 所示。 ( 7 ) b r e a k 语句 b r e a k 语句是结构化转移语句。b r e a k 语句会将控制流引向直接嵌套b r e a k 语 句的循环语句后的第一条语句，使程序跳出循环，即存在一条由b r e a k 语句到循 环语句后第一条语句的无标号的控制流边，如图3 7 所示。 ( 8 ) c o n t i n u e 语句 c o m i n u e 语句也是结构化的转移语句，c o n t i n u e 语句会将控制流引向直接嵌套 c o n t i n u e 语句的循环语句的入口处，直接进行下一次循环，即存在一条由c o n t i n u e ) 甲萤 第三章关键技术的解决方案 语句到循环语句条件的无标号的控制流边，如图3 8 所示。 ( 9 ) g o t o 语句 g o t o 语句是非结构化的转移语句，g o t o 语句会将控制流引向相应的标号语句， 即存在一条由g o t o 语句到相应标号语句的无标号的控制流边，如图3 9 所示。 0 0 1 0 0 2 0 0 3 0 0 4 0 0 5 0 0 6 0 0 7 0 0 1 0 0 2 0 0 3 0 0 4 0 0 5 0 0 6 0 0 7 s w i t c h ( i ) c a s el ： a + + ： b r e a k ： c a t s e2 ： b + + ： b r e a k c a s e3 ： b r e a k ， p r i n t f ( _ | d i 图3 6s w i t c h w l l i l e ( a 0 ) i a + + ： i f ( b o ) i f ( b ( 1 ) b2 b 一8 ： 图3 8c o n t i n u e 语句的控制流图 眦啪似l量|耋晰瞄啪兰! 0 0 1 0 0 2 0 0 3 0 0 4 0 0 5 i f ( a 0 ) g o t ol a a 。a _ b b ：1 ： 0 1 1 ：l a ：p r i n t f ( 。m a ) 图3 9g o t o 语句的控制流图 图3 1 0 是一个完整的程序和它的控制流图。 图3 1 0 程序和它的控制流图 3 2 控制依赖的关键技术 控制依赖的概念最早是由f e r r a n t e 9 “8 7 1 等人提出的，它被用于模拟条件分支 语句对程序行为的影响。控制依赖是程序控制结构的属性，因为它能够根据控制 流图来严格的定义。直观地讲，一个语句w 控制依赖于语句“，如果“是一个影响 w 执行的条件。例如一个i f = t h e n - e l s e 结构，位于条件语句两侧的语句控制依赖于 该谓词。 3 2 1 后必经结点 定义3 2 嘲“酬令占= ( k 匐是一个控制流图，如果从开始结点s t a r t 】口 0 ， o t l e1 n ： m叫m，扼。 趴 订。 令p = ( ，= w o , - 二肌。婚：力是在c f g 中的一条路径，半必经结点路 径定义为，如果对1sj5 扣1 有昕 v ，则p 是条半必经结点路径。一条从 “到y 的半必经结点路径不包括所有在树7 上u 和p 之间的结点。 半必经结点的性质使它成为计算必经结点中间步骤。对于任意结点”( ”，) ， 矿的半必经结点s d o m ( 驴) 在，中是矿的真祖先，而矿的直接必经结点面历( 曲又是 s d o m ( w ) 的祖先( 不一定是真祖先) 。因此如果我们用边集( ( s d o m ( w ) ，曲l 酽矿 并且矿一替换g 中没有出现在7 中的非树边，结点的必经结点不会发生变化。 这样如果有了深度优先生成树和半必经结点，就可以计算必经结点。半必经结点 根据下面的定理计算。 定理3 2 ：对于任意结点矿( 矿，) ， c ，c + + 程序分析中若干关键技术的研究 s d o m ( w ) = m i n ( v i ( h 神f 并且p 旷) u s d o m ( u ) l d j f ，并 且g 中存在边( h 计，t 上存在一条路径“_ 订) 为了计算半必经结点，l t 算法维护一个动态的森林只它是深度优先生成树， 的一个子图。也是一个辅助的数据结构。所以，中的边( h 曲l 它连接父结点 v 和它的儿子结点乳初始化时，包含所有结点，但不包括，中的边，即所有结点 都作为单结点树，森林f 支持下列操作： l i n k ( nl i j ：把边( h 曲，加入到，中。在，中有p a r e n t ( w ) = n 而 在f 中结点r 和矿是树的根结点。 e v a l ( 访：如果结点p 是森林中一棵树的根，返回“否则，令，是森林中 包含结点p 的树的根，返回在路径，叶r 上的一个结点，r ，其s e m i ( u ) 的值最小。 其中的s e m i ( d 表示结点p 对应数组中的值，它是这样定义的： ( 1 ) 在结点y 被深度优先遍历前，s e m i 例= 0 。 ( 2 ) 在y 被深度优先遍历后，但它的半必经结点还未计算之前，s e m i ( 订的值 是d f s ( 订。 ( 3 ) 在v 的半必经结点被计算后，s e m i ( 订的值是p 半必经结点的深度优先搜 索序号。 从作用上来讲，l i n k 操作是构造森林，e v a l 操作是从森林中提取信息。 根据定理，l t 算法按深度优先搜索序号递减的顺序遍历，中的结点，以如下 方法计算半必经节点： 算法3 i 半必经结点算法 输入：控制流图g 深度优先生成树， 输出：s e m i 数组 方法：f o rr vi nr e v e r s ed f so r d e rd o f o r ( i v , 订芒ad o u ：e v a l ( 曲 s e m i ( 订= m i n ( s e m i ( u ) ，s e m i ( 订 d o n e l i n k ( 订 d o n e 口 引理3 2 对任何一个结点甲乒，i d o m ( w ) _ s d o m ( w ) 。 引理3 3 令结点n 甲满足而那么p i d e m ( w ) 或者i d o m ( w ) 一i d a m ( 订。 引理3 4 令酽，o 假设s d o m ( w ) 一口一甲对每个，满足s d o m ( u ) s d o m ( 矽) 。 那么i d o m ( 井= s d o m ( 而。 引理3 5 令w n 令，是在满足s d o m ( i r ) _ ，_ w 的所有，结点中s d o m ( u ) 值 第三章关键技术的解决方案 最小的一个结点。那么s d o m ( u ) ss d o m ( w ) 且i d o m ( u ) = i d o m ( 矿) 。 引理3 6 令矿，令，是在满足s d o m ( 曲寸斗旷的所有结点中s d o m ( 曲值 最小的一个结点。那么 胁m ( w ) ：i s d o m ( w ) i f ，( s d o m 。( w ) 。面棚( “) ) 式3 1 。咖m 【w ) _ 、“，砌p 刑括e 瓦3 l 上述引理在参考文献 l e n g 7 9 中给出了证明。引理3 ，6 给出了计算直接必经 结点的方法，它可以从引理3 4 和3 5 推出。满足s d o m ( w ) 一l i - - ) 的结点即为 在树，的路径上s d o m ( 神和矿之间的结点。所以当s d o m ( u ) 值为所有可能的“中 最小的一个结点时，若有s d o m ( 矽) = s d o m ( u ) 成立，则对于s d o m ( w ) 和w 之间其 它的结点，肯定有s d o m ( d ) s d o m ( 0 ，所以s d o m ( f f ) s d o m ( 曲，即对所有 满足s d o m ( 力+ “呻的结点u 有s d o m ( u ) s d o m ( 力成立，这正是引理3 4 的情 况。当s d o m ( w ) s d o m ( u ) 时，实际上就是s d o m ( 曲 s d o m ( 曲，这是引理3 5 的 情况。 l t 算法的第三步，根据引理3 6 计算每个结点的直接必经结点。它也可以分 为两步，先隐式定义每个结点的直接必经结点，然后以增序显式定义每个结点的 直接必经结点。 3 2 4 后必经节点算法 对于本文应用中需要的后必经节点树，实际上相当于在逆控制流图中求必经结 点。可以对乙t 算法进行扩充，用以计算后必经节点。扩充的方法主要是首先对输 入的控制流图进行逆转，就是说将s t o p 结点作为逆转后的控制流图的s 删斤，结点， 并将所有的有向边的指向逆转。 l t 算法扩充后的计算后必经节点的算法如下： 算法3 2 构造后必经结点树的算法 输入：控制流图g 输出：后必经结点树，d f s 数组 方法；其中控制流图的结点数为胁边数为肪这里i p d o m ( 订表示v 的直接后必 经结点，记录半后必经结点的值仍用s e m i ( 以。 1 把输入的控制流图( k 曰转换成逆控制流图( kp ) ，保持每个结点在 控制流图中的编号不变，用该编号标识每个结点： 2 初始化变量，将表示半后必经结点的s e m i 数组元素全部置为零： 3 在逆控制流图上执行一个深度优先搜索，得到树咒对结点按它们在搜 c c + + 程序分析中若干关键技术的研究 索中被到达的顺序从1 到疗编号，将这个编号值记录在d f s 数组中。 并对所有结点瞧矿置s e m i ( 访= d f s ( 力。并初始化在后面步骤中将 要用到的变量： 4 按算法3 。l 计算所有结点瞪矿的s e m i 值； 5 应用引理3 6 中式( 3 1 ) 隐式的定义每个结点的直接后必经结点。求出 在路径s d o m ( 矽) 一上的s d o m ( u ) 值最小的一个结点从s d o m ( 曲) 。 那么。如果s e m i ( 曲 ；2 + s i z e 【c h i mp 】) a n c e s t o r c m l ai l l 】= s ； c h i l di s = c h i l d 【c h i l d p 】； e l s e s i z e 【c h i l di s 】= s i z e 嘲； s = a n c e s t o r i s t 嘲埘m ； ) ) l a b e l 跚zl a b e l w j ； s i z e i v 2s i z e m + s i z e 【w 】； 第四章实现方法与具体实现 i f ( s i z e 【v 】 2s e m i 1 a b e l 【v 】? l a b e l 【v 】：l a b e l 【a n c e s t o r 【v i i ； 口 ，口 其中的c o m p r e s 函数的类c 语言实现如下： c o m p r e s s ( v ) i f ( a n c e s t o r a n c e s t o rm 】_ 0 ) c o m p r e s s ( a n c e s t o rm ) ； i f ( s e m i 【l a b e l a n c e s t o r 【v i i s e m i 1 a b e l 【v 】1 ) l a b e l v 】= l a b e l a n c e s t o r 【v 】； a n c e s t o r v 】= a n c e s t o r 【a n c e s t o r 【v 】 ； 在第二步中首先计算s 鲫i e w 的值，使s e m i 矿 = 历门 s e m i ( e v a l ( 曲) i ( 曲 岔。因为根据e y a l 操作的性质，如果结点y 是森栋中棵树的根，返回n 否 则，令，是森林中包含结点p 的树的根，返回在路径，斗r