（计算机软件与理论专业论文）c语言的程序依赖图的构造和应用研究.pdf

摘要 本文主要研究软件安全性分析工具前端的设计和实现。总结了传统的面向过 程程序分析技术向面向对象程序分析扩展的理论和方法，对程序分析技术几个关 键算法做了改进。首先，分析了c + + 抽象语法树的结构和特点，提出了解析和遍 历c + + 抽象语法树的方法，并给出具体实现；然后，提出了一种新的指针别名信 息表示方法和基于该表示方法的过程内指针别名分析框架：最后，根据已有面向 对象程序依赖图构造方法，设计并实现了基于抽象语法树的程序分析器，对其中 数据依赖的计算和指针别名信息的采集方法进行了重点介绍。此外，本文讨论了 程序分析技术与安全性分析相互结合的问题，分析并比较了两类安全检测方法的 检测范围和能力。 关键词：抽象语法树控制流数据流指针别名程序依赖图 a b s t r a c t t h ed e s i g na n di m p l e m e n t a t i o no f t h ef r o n te n do f s o f t w a r es a f e t ya n a l y s i st o o li s i n v e s t i g a t e d i nt h i s p a p e r c u r r e n to b j e c t o r i e n t e dp r o g r a ma n a l y s i st e c h n i q u e s i m p r o v e df r o mt r a d i t i o n a l o n ea r es u m m a r i z e da n ds e v e r a lk e ya l g o r i t h m sa r e i m p r o v e d f i r s t l y , s t r u c t u r e sa n df e a t u r e so fa b s t r a c ts y n t a xt r e e sa r ea n a l y z e da n d m e t h o d so fp a r s i n ga n dt r a v e r s i n gt h e ma l ep r e s e n t e d an e wp r e s e n t a t i o no fp o i n t e r a l i a si si n t r o d u c e d ，b a s e do nw h i c ha na l g o r i t h mo fi n t r a - p r o c e d u r a la l i a sa n a l y s i si s d e s i g n e d a c c o r d i n gt o t h ec u r r e n to 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 c o n s t r u c t i o nm e t h o d s ，ap r o g r a ma n a l y z e rb a s e do na b s t r a c ts y n t a xt r e e si sd e s i g n e d a n di m p l e m e n t e d ，a n dc o m p u t a t i o no fd a t ad e p e n d e n c ea n dc o l l e c t i o no fp o i n t e ra l i a s a r ei n t r o d u c e di nd e t a i l b e s i d e s ，h o wt oa s s o c i a t ep r o g r a ma n a l y s i sw i t hs a f e t y a n a l y s i si sd i s c u s s e da n dt h es c o p ea n dc a p a b i l i t yo ft w ok i n d s o fs a f e t ya n a l y s i s m e t h o d sa l ec o m p a r e d k e y w o r d s ：a b s t r a c ts y n t a xt r e e c o n t r o lf l o wd a t af l o w p o i n t e ra l i a s p r o g r a md e p e n d e n c eg r a p h y 1 0 0 8 0 7 8 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩放或其他复制手段保存论文。 本学位论文属于保密在上年解密后适用本授权书。 本人签名 导师签名 日期：丛生f ! 翌 日期：堑生垒： ：! 第一章绪论 第一章绪论 1 1 研究背景 随着网络技术的发展以及自由软件的广泛使用，软件的安全性嘲口璐9 6 1 越 来越受到人们的重视，尤其在军事领域对软件的安全性要求更严格。计算机的安 全性隐患大量存在于软件系统中，如程序设计语言自身语言机制造成的安全漏洞、 软件设计过程中失误造成的安全漏洞等，使得软件通常不够健壮，导致软件在使 用阶段会发生意想不到的故障，造成重大损失。 对于自主开发的软件，主要通过测试的方法检查所有可能豹安全错误。这需 要对软件的功能、特性等具有深刻了解， 软件错误难于在测试过程中发现并定位， 根据软件特性设计完备的测试集。某些 原因是：( 1 ) 错误可能在程序多次执行 中才会出现一次：( 2 ) 其危害的显现需要运行相当长的时期；( 3 ) 不同的平台下 程序有不同的行为，使其不易显现；( 4 ) 程序中大量的操作以及复杂控制流程使 错误不易定位。并且这种动态测试的方法不适用于可重用软件。因此，静态( 不 运行) 的检测并定位软件的安全性，避免不必要的损失，成为当前计算机安全领 域中需要研究的一个重要课题。 软件系统安全性分析工具可以被广泛地应用于对软件安全性有严格要求的领 域，提高软件安全性。我们所研究的程序分析技术和软件安全性分析方法，具有 一定的普遍性，对其它相关工作，如程序理解、逆向工程、遗产继承、程序切片 等均具有理论和实际指导意义。 1 2 总体方案 针对软件安全性这一重要问题，许多学者提出了不同的解决方法。最早出现 的方法是定理证明 s u t 01 】【l 腿。3 1 ( t h e o r e i np r o v i n g ) ，它是基于符号逻辑、应用逻 辑推理规则的形式化验证方法；八十年代初e c l a r k e 等人【。l a 0 0 】提出的一种基 于自动机理论的模型检验( m o d e lc h e c k i n g ) 的方法，也是一种形式化的方法， 用于验证程序的正确性；1 9 9 7 年卡奈基梅隆大学的g e o r g e c n e c u l a 刖“”1 提出的 携带验证代码( 陬斌如哪桩g c o d e ，p e c ) 技术，适于在遵守一定安全策略的代码 提供者和使用者之间使用，确傈软件安全性：随着网络技术的发展，计算机系统 中的信息流安全一直倍受关注，基于类型推理田e n7 7 1 的信息流验证和检测是处理 这类安全问题的主要方法。 c + 十语言的程序依赖图的构造和应用研究 以上各种分析方法存在复杂度高，使用范围小，对分析人员理论基础要求高， 不易于广泛使用等缺点。基于程序分析的软件安全性检测方法是将程序分析技术 与软件安全故障模式相互结合发展而来的一种静态检测软件安全故障! e v a 9 6 】f s 。”恻 的方法，利用词法分析、语法分析处理源程序文本，提取程序基本信息，在此基 础上进行控制流分析8 e l 翻、数据流分析 b a r7 研以及依赖分析 l e n7 9 】【队“9 4 1 ，建立 程序依赖图【d 丌“】和系统依赖图降0 1 】作为下一步安全性分析的基础。通过对分布 式环境下软件出现的各类安全漏洞的分析，提取软件安全故障模式的数学模型和 实现模型，在安全故障模式的指导下，对源程序进行安全性分析，检测并定位系 统潜在的安全隐患。具有自动化程度高，对使用人员要求低，可检测安全漏洞范 围广等特点。我们的安全分析工具采用图1 1 所示的安全性分析模型，安全模式 从程序分析过程中分离出来，使安全模式具有相对独立性，便于对安全模式进行 扩充，以实现安全模式指导下的安全分析。 图11 安全性分析梗型 程序分析器是整个分析工具的前端，它负责对源程序进行处理，提取软件的 安全性信息，以便于使用的形式提供给安全分析器，并为安全分析器提供分析的 入口：安全分析器是分析工具的后端，在安全模式的指导下，利用程序分析器提 供的信息检测并定位安全漏洞的位置。经过安全分析工具的处理后产生的输出为 ( 1 ) 软件安全性分析报告；( 2 ) 带有安全性注释的源程序。根据课题的砩究勇标 并对各种程序设计语言的语言特性进行比较，选用标准c + + 语言作为分析和研究 的对象。本课题组上一届同学对当前程序分析技术进行了总结，设计了程序安全 性分析工具的基本框架，并在g c c 源码中嵌入了部分程序分析的代码，为我们 后继工作的开展积累了丰富的理论和实践经验 第一章绪论 1 。3 论文主要工作 程序分析器是软件安全分析工具的前端，作为软件安全性分析的基础，程序 分析器负责以尽可能小的时间、空间复杂度从源程序中提取安全性分析所需的各 种信息，提供给安全分析器利用，主要包括抽象语法树( a b s t r a c ts y n t a xt r e e ，简 称a s t ) 、符号表、程序依赖图( p r o g r a md e p e n d e n c eg r a p h ，简称p d g ) 、类层 次子图、类依赖图和系统依赖图( 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 ，暂时不提供妨g 。系统依赖图是由多个程序 依赖图等构成的多图，程序依赖图是系统依赖图的基础，在获得每个过程的程序 依赖图后，通过程序分析器第四个模块的集成可以生成系统依赖图。 本人主要负责程序分析器中抽象语法树文件的解析、符号表的建立和程序依 赖图中数据依赖子图的建立。本文的主要工作是：研究传统的面向过程程序分析 技术向面向对象程序分析扩展的理论和方法，明确程序分析器的功能和任务，总 结创建c + + 程序依赖图的理论和方法，扩展程序分析技术几个关键算法，研讨程 序分析与安全性分析相互结合的问题，最后给出了c + + 程序分析器中解析抽象语 法树文件、建立数据依赖和指针别名信息部分州吲的具体实现方法。 1 4 论文组织结构 本文组织结构为；第一章对项目研究背景和总体方案等做简单介绍。第二章 给出了程序分析技术的发展现状和前景，分析了程序分析器的功能和任务，对程 序分析器所提供的各种信息的概念及其作用进行阐述。第三章给出了程序分析所 使用的各种关键技术的解决方案，包括抽象语法树文件的解析与遍历方法、符号 表信息的收集、过程内数据依赖的计算与指针别名信息的收集等：讨论了程序分 析与安全性分析相互结合的问题。第四章介绍了程序分析器的具体实现方法，对 程序分析器体系结构各部分所使用的算法和数据结构进行了详细的阐述，介绍了 g l i b 库中定义的数据结构及其操作，给出了各个算法所使用的程序框架。第五章 通过对一个有代表性的例程进行分析，给出了程序分析器分析后的结果，然后分 析了程序分析器的效率。最后对本文进行概括和总结。 第二章程序分析简介 第二章程序分析简介 2 1 程序分析技术发展现状 程序分析技术是一种源程序的静态分析技术。源程序是以语句和基本块为单 位组织起来的整体，程序的运行就是控制单元在语句和基本块之问流动的过程。 控制单元的流向取决于语句或基本块之间存在的依赖关系，这种依赖关系既包括 语句或基本块在程序流程中所处的位置也包括语句或基本块对数据定值的影响。 程序分析技术在词法分析和语法分析的基础上，通过对源程序进行控制流分析和 数据流分析产生包含控制依赖和数据依赖等信息的系统依赖图。系统依赖图是一 种图结构，是源程序的种中间表示形式，直观而形象的描述了程序的框架结构 和依赖信息，提高了分析和理解程序的准确性。 2 1 1 传统程序分析技术 传统程序分析技术主要针对面向过程程序的分析与优化中。最初，数据流分 析的概念来自编译器中间代码优化和代码生成阶段 a h 0 8 “，是编译器为了更好的 进行优化和代码生成所采用的技术。它把程序作为一个整体来收集信息并将信息 分配给流图的各个基本块进行优化。这些数据流信息包括到达一定值、可用表达 式、活跃变量、定值一引用链，指针分析、别名分析等，通常可以应用这些信息 来完成公共子表达式删除，复写传播、循环不变量的计算、代码外提、归纳变量 删除、死代码删除等编译器的代码优化行为。经过多年的发展，传统程序分析技 术逐步走向成熟，形成了一套较为完整的理论和实践方法。传统程序分析技术广 泛应用于程序理解，逆囱工程等，也是面向过程程序切片 t i p9 5 工具的基础，在系 统依赖图基础上已经实现许多面向过程程序设计语言的切片工具，比如c 语言等。 2 1 2 面向对象程序分析技术 面向对象的程序设计语言加入了类，对象，数据封装，继承，虚拟函数，多 态等特性，传统程序分析技术在分析面向对象程序时，难于处理这些新加入的语 言特性。面向对象的程序分析技术在传统分析技术基础上增加了类层次分析、成 员函数作用域分析以及虚拟函数动态绑定分析等部分，达到了分析面向对象程序 的目的。 c + + 语言的程序依赖图的构造和应用研究 传统的表示方法不足以表示面向对象程序，可以采用如下两种策略解决这一 问题。 策略l ：引入全新的适合描述面向对象程序的表示方法。如类层次子图可用 来表示类之间的继承关系，可见方法类层次子图可用来静态反映类层次子图各节 点的可见方法，虚函数调用图可用来解决复杂虚函数调用问题。 策略2 ：改进已有的图形表示方法，扩充其功能以使其具有表示面向对象 程序的能力。如动态面向对象程序依赖图可用来表示面向对象程序的动态行为， 面向对象的程序依赖图可用来表示面向对象语言中的多态性和动态绑定等问题， 程序依赖网可用来表示并发面向对象程序等。 这些图形表示方法从不同角度表示面向对象程序。它们基本上都是为某个目 的而设计的，分别表示了面向对象程序的部分特性。例如面向对象程序依赖图不 能用来表示过程间的行为，而动态面向对象程序依赖图则只能表示系统的动态行 为。 目前比较好的解决方法为，通过对系统依赖图进行扩充得到了面向对象的系 统依赖图，其基本组成包括：过程依赖子图、类依赖子图、类层次子图、控制依 赖子图和数据依赖子图。与传统系统依赖图相比，新增类层次子图和类依赖子图 描述类之间的继承关系，确定类中的控制依赖和数据依赖关系，给出类的数据成 员与成员函数的入口，记录所包含的虚拟函数等。类层次子图表示类间的继承关 系，是方法和类定义的一种融合。它包含每个类的首部结点和在类中定义的每个 方法的首部结点，它的边把每个类的曹部结点和与其具有继承关系的类的相应的 首部结点连接起来，由方法首部表示的方法结点连接到定义该方法的类的首部结 点。子类中没有重新表示从超类中继承的方法，因而消除了对继承方法的重复表 示。类层次子图不表示方法的任何实现细节，不是个程序的完全的静态表示。 类依赖子图能够在不清楚调用环境的情况下，确定一个类中的控糊依赖和数据依 赖关系。在类依赖子图中，方法由过程依赖子图来表示，每种方法都有一个方法 入口节点。类依赖子图也包含一个类入口节点，并通过类成员边把它和类中每个 方法的入口节点连接起来。当一个类和另一个类或系统结合时，通过类入口节点 和类成员边能够很快访问方法的信息。目前，已经有相当多建立面向对象程序系 统依赖图的理论和方法，大量应用于面向对象程序切片【事0 1 蹲方面。但还都存在一 定的问题需要解决，包括时间复杂度高，糖确度低等缺点。 2 2 程序分析器的结构 采用面向对象的程序分析技术，我们在l i n u x 环境下构建了c + + 程序分析器 作为安全分析工具的前端。程序分析器完成的主要功能为，以源程序经编译后产 第二章程序分析简介 生的抽象语法树文件为输入，通过对抽象语法树文件的解析在内存中重构抽象语 法树；在抽象语法树基础上建立程序控制流图、控制依赖子图、数据依赖子图和 指针别名信息，综合形成程序依赖图；建立类依赖子圈和类层次子图；将程序依 赖图、类依赖子图和类层次子图结合，生成整个系统的系统依赖图：最后为安全 性分析提供接口，将系统依赖图提供给安全分析器使用，作为安全分析器的输入。 程序分析器采用图2 1 的基本框驾，分为四个部分，分别是( 1 ) 抽象语法树文件 的解析器：( 2 ) 抽象语法树遍历模块；( 3 ) 控制流图遍历模块；( 4 ) 系统依赖图 综合模块。源程序经过前三个模块的处理产生每个过程的程序依赖图，经过第4 个模块的处理生成最后的系统依赖图。 图2 1 程序分析器框架 以抽象语法树文件作为程序分析器输入，这是因为( 1 ) 构造c - h 语言完整 的词法和语法分析器作为程序分析器的基础相对比较复杂；( 2 ) l i n u x 环境下 g c d s t a o 习编译系统使用抽象语法树作为一个层次的中间表示，抽象语法树具有良 好的抽象层次，可以较好的表示各种语言的语法特征，对抽象语法树的遍历过程 相当于源程序的语法分析过程，遍历过程中对特定树节点的处理操作相当于语法 分析过程中的语义动作，可以实现对语言特性的处理，提取源程序信息。这样， 使用经过g c c 编译产生抽象语法树，可以对所有c h 程序进行正确的语法分析， 为后面的程序依赖图的建立提供良好的支持。 c 十+ 语言的程序依赖图的构造和应用研究 2 2 1 抽象语法树文件的解析器 上文提出使用g c c 编译器编译产生的抽象语法树作为程序分析器的输入， 实际应用中有两种操作抽象语法树的方案可供选择。首先g c c 编译器的源码中 包含抽象语法树结构和操作的定义，包含处理编译过程产生的抽象语法树的源代 码，因此可以通过在g c c 中嵌入程序分析的代码实现程序分析器。另外，g c c 编译器存在编译参数- f d u m p - a s t - o r i g i n a t 可以将源程序经过语法分析后产生的抽 象语法树结构以文本形式输入到以o r i g i n a l 结尾的文件中，通过一个解析器可以 对该文件进行解析，在内存中重新构造抽象语法树。由于g c c 编译器规模比较 庞大、源文件之间关联关系复杂、修改难度高，因此选用第二种方案。抽象语法 树文件解析器正是第二种方案的一个具体实现，它以g c c 编译器产生的抽象语 法树文件作为输入，通过对该文件进行一遍词法分析和语法分析，在内存中重构 抽象语法树，然后将解析后的抽象语法树作为输入提供给抽象语法树的遍历模块。 2 2 2 抽象语法树的遍历模块 抽象语法树的遍历模块主要负责建立程序的控制流图、创建符号表、类依赖 图和类层次子图、记录每个控制流节点所产生的定值一使用对、收集类层次关系 和指针别名等信息。抽象语法树上不同结点代表了语言的不同语法特性和程序信 息，通过遍历每个抽象语法树节点，在所关心的结点上加入特定的处理函数可以 实现该模块的功能。例如w h i l es t m t 节点代表w h i l e 语句在抽象语法树上的首节 点，如图2 2 所示。程序分析过程中，需要对w h i l e 循环语句进行处理以在程序 的控制流图上产生对应的控制流节点，因此处理该节点时，添加了产生控制流节 点并将其加入控制流图的相关操作。其中咖es t m t 节点的c o n d 分支对应了循环 的条件，处理该分支时建立一个w h i l e 循环的头节点，它既是循环的开始点，也 是循环体返回的节点：幻a y 分支代表循环体，对6 0 咖内的节点，根据其节点类 型执行特定的操作，建立控制流节点或进行其它处理。同理，针对能够产生或改 变程序定僮信息的节点加入相应的操作函数，能够将定值信息记录下来为以后生 成数据依赖做准备。经过抽象语法树遍历模块的处理，产生了以控制流图为载体 的包含程序定值信息和指针别名等信息的图结构作为下一步分柝的输入。 第二章程序分析简介 9 图2 2w hi ie 循环对应韵抽象语法树 另外，面向对象程序所特有的类依赖子图和类层次子图也在这个模块建立。 2 2 3 控制流图的遍历模块 程序分析器的第三部分是控制流图的遍历模块，该模块根据数据流方程的迭 代求解算法和过程内指针别名分析算法，利用上一模块为其提供的控制流图和定 值信息，在控制流图上迭代计算数据依赖和指针别名，建立单个过程的程序依赖 图。数据流方程的迭代求解算法和过程内的指针别名分析算法是一种在控制流图 上反复迭代的算法，对控制流图进行多次遍历直到控制流节点的到达一定值信息 收敛为止。获得控制流节点的到达一定值信息后，再根据节点的定值使用对，计 算数据依赖和指针别名，并将结果填加到控制流图对应节点上形成程序依赖图。 2 2 4 系统依赖图综合模块 系统依赖图是由程序依赖图、类层次子图、类依赖子图、控制依赖子图和数 据依赖子图构成的一个多图。程序分析器前三个模块生成程序依赖图、类层次子 图、类依赖子图、控制依赖子图和数据依赖子图，在第四个模块利用特定算法综 合形成面向对象程序的系统依赖图。构造面向对象系统依赖图的算法按类层次子 图的拓扑结构从底到顶的顺序依次分析每个类c 的方法，判断哪些方法需要重新 建立过程依赖子图。具体做法是，对每个在基类中声明的方法m ，如果m 直接或 间接调用了一个在c 中重定义的虚方法，算法就会在为基类中方法m 建立的程序 1 0 c + + 语言的程序依赖图的构造和应用研究 依赖图的基础上构造新的程序依赖图，如果m 没有直接或间接调用在c 中重定义 的任何方法，则算法重用为基类中的州而建立的程序依赖图。然后算法使用定连 边将程序依赖图的每个调用位置和被调用方法的入口连接起来，最后处理参数传 递问题。 2 3 程序分析器提供的信息 程序分析器提供给安全分析器的信息包括如下几个部分： ( 1 ) 抽象语法树既是程序分析器分析的基础，也是安全分析器进行安全分 析器的基础，因此需要为安全分析器提供使用抽象语法树的入口。 ( 2 ) 符号表为了便于安全分析器查找和使用各种符号信息，将各种符号信 息收集整理生成符号表，提供给安全分析器。 ( 3 ) 系统依赖图由程序依赖图、类层次子图、类依赖子图等组成。系统依 赖图是安全分析过程必备的信息，是检测多数安全性漏洞所必须的信息。 2 3 1 抽象语法树 抽象语法树是整个程序分析器的基础，是程序分析器处理的对象也是程序分 析器信息的来源。抽象语法树具有语言无关性和平台无关性，很多编译系统采用 中间语法树作为编译过程的中间表示，其中比较著名的是g c c 编译系统。 g c c ( g n uc o m p i l e rc o l l e c t i o n ) 编译系统是美国自由软件基金会( f r e e s o f t w a r ef o u n d a t i o n ) 资助开发的g n u 项目，它能够对多种程序设计语言进行编 译，支持多种平台的编译程序集合，是l i n u x 下使用最为广泛，最稳定的编译器。 g c c 编译系统主要由三部分组成：( 1 ) 与语言相关的前端( 2 ) 与语言无关的后 端( 3 ) 与机器相关的的机器描述部分。为了能够在多种平台下进行编译，g o c 使用的中间代码必须能够向上支撑各种程序设计语言到中间代码的映射，向下支 持跨平台代码转换和在多种平台下进行优化。因此g c c 编译系统使用两个层次 的中间代码，分别为抽象语法树层和寄存器转移语言( r e g i s t e r t r a n s f e r 加g u a g e ， 简称r t l ) 层，来满足上述要求。抽象语法树是? 种通用的中闻代码形式，既可 以表示各种语言共有的语法结构，也可以表示某些语言特有的语法结构，是一种 与语言无关的通用表示。抽象语法树易于转换成寄存器转移语言，丽寄存器转移 语言适合在不同平台下进行优化，这使得g c c 的中间代码具有良好通用性。 前面提到，使用g c c 的编译参数- f d u m p - a s t - o r g i n a l 可以将g c c 编译过程产 生的抽象语法树输出到以o r g i n a l 结尾的文本文件中，通过对该文件进行解析可以 在内存中重建抽象语法树，提供给程序分析器和安全分析器使用。抽象语法树是 第二章程序分析简介 程序分析器的基础，是建立系统依赖图的必要信息：安全分析器需要利用抽象语 法树的遍历过程模拟语法分析过程，检测某些安全性漏洞。因此，程序分析器除 了提供抽象语法树的数据结构以外，还需要为安全分析器提供一个遍历框架，以 实现语法分析过程的模拟。抽象语法树既是程序分析器信息的来源，也是后端安 全分析器进行安全性分析的载体。 2 3 2 符号表 因为g c c 编译器采用抽象语法树作为一层中间表示，源程序的基本信息都 保存在抽象语法树上，不存在传统的符号表记录程序符号信息。而在进行安全性 分析时，需要快速查找各种符号的类型、大小、在源程序的位置，以及符号之间 的作用域关系等，因此在遍历抽象语法树过程中根据安全性分析的需求建立符号 表是有意义的。 各种符号在抽象语法树上也是以树型结构存在的。 例如：i n t ( * t e m p ) 卢，= 沮三i 声明了一个指向整型数组的指针t e m p ，并被初 始化为n u l l ，抽象语法树上该声明对应子树如图2 3 所示。 圈2 3 符号表信息在抽象语法树上的体现 符号声明语句在抽象语法树上对应一个声明节点，符号表元素的信息存在于 以声明节点为根结点的子树中，包括所声明的变量名、作用域、初始值、类型、 大小、在源程序中的位置和内存中对齐位置等。 c + + 语言的程序依赖图的构造和应用研究 2 3 3 程序依赖图 许多程序测试和分析技术依赖于控制依赖或者数据依赖信息，某些测试技术 根据控制依赖或者数据依赖信息选择测试数据、确定测试集合。我们的程序分析 器提供程序依赖图作为安全分析器进行安全性分析的输入，程序依赖图的节点代 表语句或者代码块，边代表控制依赖或者数据依赖信息。有几种建立程序依赖图 的方法，包括语法制导建立程序依赖图【“a r9 3 】和基于控制流图的建立方法等。本 文选用后一种方案。首先，利用语法分析过程建立程序的控制流图，收集定制信 息；然后根据控制流图计算后必经结点信息，产生控制依赖( c c r9 0 ；最后根据定 值信息在控制流图上迭代计算节点的数据依赖和指针别名信息形成程序依赖图。 2 3 3 1 控制流图及其作用 控制流图以语句或者基本块作为控制流图的节点，边代表了语句或基本块之 间控制流的流向。 定义2 1 控制流图是一个有向图g = 仍e 矿是结点的集合，e 是有向边 的集合。其中结点表示语句或基本块，边“一v 表示从u 到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 ， 并将所有结束语句对应的结点都指向它。 口 控制流图是程序依赖图中数据依赖和控制依赖信息的载体，控制流节点中包 含对应的存储数据依赖和控制依赖信息的域。控制流图除了是程序依赖凰的基础 以外，也是进行程序安全性分析的基础，它是处理一大类安全性漏洞所必须访问 和使用的数据。很多安全性漏洞与程序中复杂的控制流程有关，比如某些存储泄 漏问题的产生，就是由于控制流未能到达释放存储空河操作所在的路径而导致存 储分配和释放操作不匹配，造成内存泄漏。 2 3 3 2 控制依赖子图及其作用 控制依赖的概念【蹦。8 7 】最早是由f e r r a n t e 等人提出的，它被用予模拟条件分支 第二章程序分析简介 语句对程序行为的影响。控制依赖是程序控制结构的属性，因为它能够根据控制 流图来严格的定义。直观地讲，一个语句w 控制依赖于语句u ，如果是一个影 响w 执行的条件。例如一个乒髓翻印娅结构，位于条件语句两侧的语句控制依赖 于该谓词。存在嵌套语句、多重分支和非结构化的控制流时，直观的含义是不可 靠的，我们介绍一种形式化的、图论的定义。 在给出控制依赖的形式化定义以前，先介绍一下必经结点和后必经节点的概 念，其中后必经结点的概念来自于必经结点的概念。 定义2 2 令g = ( e 日是一个控制流图，如果从开始结点s t a r t 起，每条到 达结点w 的路径均包含结点v ，就称g 中结点v 是另一个结点w ( w v ) 的必经 结点( d o m i n a t o r ) 。如果v 是w 的必经结点，并且w 的每个其它的必经结点又是 y 的必经结点，那么结点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 ) 。 口 定理2 1 1 a h o7 2 i 在控制流图g = ( 目中除开始结点外的每个结点有一个唯 一的直接必经结点。由边 ( i d o m ( w ) ，w ) 】w v 一 s t a r t ) 构成的以s t a r t 为根 的有向树称为g 的必经结点树，则有v 是w 的必经结点当且仅当在必经结点树中 v 是w 的一个祖先。 根据必经结点的定义，将开始结点改成退出结点，相应的可以得到后必经结 点的定义。 定义2 3 令g = ( hd 是一个控制流图，如果每一条从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 = i p d o m ( v ) 。 口 后必经结点的定义中不包括路径的初始结点，所以一个结点不会是它自身的 后必经结点。同必经的概念一样，后必经也是一种传递关系。根据定理2 1 ，结点 之间的后必经关系也将构成一种树状结构，该结构被称作后必经结点树。 下面基于前面讲述的控制流图和后必经结点的概念，给出标准的控制依赖的 定义。 定义2 4 令g 是一个控制流图，u 和w 是g 中的结点。w 是控制依赖于结 点z ，的，当且仅当： 存在一条从“到w 的有向路径p ，v ( 不包括结点“和w ) 是p 中任意一 个结点，那么w 是v 的后必经结点； 如果w w ，那么w 不是群的后必经结点。 4 c + + 语言的程序依赖图的构造和应用研究 口 从上面的定义可以看出，如果结点w 控制依赖于结点，那么u 必须有两个 出口。沿着其中的一个出口，总是导致执行w ，而另外一个出口则导致w 不被执 行。 控制依赖记录了控制流流向某个控制流节点所依赖的其它节点编号，是静态 确定程序执行路径的必要条件。 2 3 3 3 数据依赖子图及其作用 一个从结点9 到结点p 的数据依赖边表示如果g 和p 代表的程序成分的相对顺序 被颠倒，则程序的计算就会改变，数据依赖是结点表示的语句之间数据的定义和 使用关系。数据依赖可以被区分为不同的类型，包括流依赖、输出依赖和反依赖， 其中流依赖与程序分析密切相关。 定义2 5 程序点g 数据依赖于程序点p ，当且仅当对某个数据存储空间l o c ，存 在一条执行路径，程序从p 执行到g 的路径上没有对f o c 的写操作出现。如果p 点对f o c 执行写操作，g 点对，d c 读，那么p 与口之间存在流依赖：如果p 和g 都对f o c 写，则两 点存在输出依赖，如果p 读l o c 而g 对l o c 执行写操作，则存在反依赖。 口 在本文中，程序依赖图只包含流依赖边。它是通过数据流方程来计算的，如果 获得了各个结点的到达定值信息，数据依赖的计算将十分直接，因此数据依赖的 求解可归结为到达定值信息的获得。 程序依赖图包括从g 到p 的流依赖边，只有当如下所有条件都成立： ( 1 ) p 是对变t x 定值的结点。 ( 2 ) 4 是使用娜向结点。 ( 3 ) 控制流可以通过一条没有变i x 的其它定义的执行路径由p 到达口。也就 是说，在程序的标准控制流图中存在一条路径，它能够使在p 处舶q 定值 到达坷处x 的使用。 一个从结点g 到结点p 的流依赖被表示为g r p 。 流依赖可以被进一步分为循环携带的和循环独立的一个流依赖譬一f 滋循环l 携带，表示为q - - t c ( z ) p ，如果下述条件也成立： ( 4 ) 存在一个执行路径既满足上述的条件( 3 ) 还包括一个循环语句朋| 臼谓诃 的回边。 ( 5 ) g 和p 都包含在循环工中。 一个流依赖g 伊是循环独立的，表示为拿一“p ，如果除了上述条件( 1 ) ，( 2 ) 和( 3 ) 外，还存在一条执行路径既满足( 3 ) 又不包括围绕乎帮p 的任意循环语旬 第二章程序分析简介 的回边。从p 到g 可能有多条执行路径，因此依赖g 一郇j p 和口一n p 可能同时存在。 数据依赖记录了节点之间定值和使用数据之间相互影响，相互依赖关系，它 是进行局部数据估值，谓词定值，循环和分支条件判定等的必要信息。 2 3 3 4 指针别名信息及其作用 定义2 6 当程序里面存在指针数据类型或者存在通过传送地址方式进行的过 程调用时，两个或两个以上的表达式就可能代表同一内存地址，称这些代表同一 内存地址的表达式互为别名。由于指针数据类型的存在而引起的别名称为指针别 名。 口 指针别名的存在c + + 语言的典型特征，也是c + + 动态安全性问题产生的重要 原因。当对某一指针别名信息不明确的时候，所有的数据流分析及相关性分析都 必须采用保守的估计，即假设次指针指向所有变量，这种假设必然给分析的准确 性带来很大的影响，因此加强指针别名的分析以获取更加准确的指针别名信息是 提高分析准确性的必要措施。 2 3 4 类层次子图和类依赖图 类层次子图和类依赖子图描述类之间的继承关系，确定类中的控制依赖和数 据依赖关系，给出类的数据成员与成员函数的入口，记录所包含的虚拟函数等。 类层次子图用图形来表示类间的继承关系，是方法和类定义的一种融合；类依赖 子图能够在不清楚调用环境的情况下，确定一个类中的控制依赖和数据依赖关系。 在类依赖子图中，方法由过程依赖子图来表示，每种方法都有一个方法入口节点。 类依赖子图也包含一个类入口节点，并通过类成员边把它和类中每个方法的入口 节点连接起来。当一个类和另一个类或系统结合时，通过类入口节点和类成员边 能够很快访问方法的信息。类层次图主要用于处理与d h 继承机制相关的动态安 全性问题；类依赖图用于分析类的成员及成员函数存在的安全隐患。 2 3 5 面向对象的系统依赖图 程序分析器最终需要建立面向对象的系统依赖图。传统的系统依赖图降0 1 】是 在控制流图、数据流图、控制依赖子图、数据依赖子图和程序依赖图基础上建立 起来的，是多个图构成的集合。形式的说，系统依赖图是由一组程序依赖图构成 的有向、带标记的多重图。程序依赖图模型化软件系统的各个过程体，系统依赖 6 c + + 语言的程序依赖图的构造和应用研究 图模型化整个软件系统。系统依赖图可以用来处理过程闻的数据流和控制流，并 能表示参数传递，允许过程间分析。面向对象程序除了包含些过程或方法外， 还存在继承、多态、动态绑定等特性，所以传统的系统依赖图还不足以描述这些 面向对象的概念。通过对传统系统依赖图进行扩充，得到一种面向对象的系统依 赖图，新增类层次子图和类依赖子图描述类之间的继承关系，记录类中的控制依 赖和数据依赖关系，给出类的数据成员与成员函数的入口，记录所包含的虚拟函 数等。面向对象的系统依赖图是安全分析器分析与c _ h 动态特性相关的安全漏洞 所必须的信息。 第三章关键技术的解决方案 第三章关键技术的解决方案 本文工作主要涉及到以下几个难点： ( 1 ) 抽象语法树文件的解析与遍历。g c c 编译系统使用的抽象语法树具有 自身的结构特点，其对应抽象语法树节点类型较多，不同树节点对应c + + 程序的 不同语法结构，并且每个树节点都包含记录该节点信息的若干分支，弄清楚所关 心的树节点和节点分支的含义非常关键。完整并正确的遍历抽象语法树，从中抽 取信息是正确建立程序依赖图和后端安全分析器进行安全性分析的基础。 ( 2 ) 过程内数据依赖的计算。数据依赖的计算是建立程序依赖图过程中比较 复杂的一步，在获得控制流图节点的定值和使用信息后，需要使用数据流方程的 迭代求解算法逐步计算直到收敛。其中，获得定值信息和使用信息需要对抽象语 法树进行一次遍历，迭代求解算法需要对控制流图进行多次遍历。数据依赖的计 算是程序分析器中耗时较长的一部分。 ( 3 ) 指针别名信息的采集。指针别名的表示方式有多种，包括别名对、指向 表示法和扩展指向表示法等，需要选择一种适合我们安全分析器使用的别名表示 方式。指针别名问题被认为是不可精确确定的问题，过分追求指针别名信息的准 确性会造成时间复杂度的大幅度提高，因此，指针别名计算过程需要在精度和时 间上作出一个良好的权衡。 ( 4 ) 软件安全性问题具有很多表现形式，针对不同安全问题必须为安全分析 器提供不同的处理接口，并使得安全分析器能够快速有效查找安全性信息。这是 程序分析器设计中的难点。 3 1 抽象语法树文件的解析与遍历方法 3 1 1 抽象语法树文件的结构 g c c 编译系统以函数为基本单元进行编译处理，每个函数与一棵抽象语法树 相对应。在抽象语法树文件中，以“；f u n c t i o n ”开始的行代表一棵语法树的开始， 该行包含抽象语法树所对应函数的各种信息，包括函数名，参数列表，返回值以 及编译过程中经过绑定后的函数名等。 例如，对于函数i n t t e s t ( i n t n u m ) 其对应的抽象语法树第一行是 ：f u n c t i o ni n tt e s t ( i n t ) j 4 t e s t i ) 其中z 4 t e s t i 是编译器绑定后的函数名。 c + + 语言的程序依赖圈的构造和应用研究 该行下面是抽象语法树所有节点的列表。每个节点形如： jf u n c t i o n _ d e c ln a m e ： 2t y p e ：秽s r c p ：e x a m p l e c p p ：2 c e x l e r n 6 d 咖j 4 节点第一部分 j 称作节点标号，是抽象语法树上区分该节点的唯一标志， 也是访问该节点的索引；其后的节点标识符f u n e t l o nd e c l 是该节点的名字并代表 该节点的含义，这里f u n c t i o n代表该节点是一个函数声明节点，函数体从该_decl 节点开始逐渐展开形成树型结构；其余部分为节点标记所组成的列表。每个节点 标记形如：n a m e ：岳油，对应该节点的一个分支，结点标记的列表记录了该节点连 接到其它节点的所有分支。节点标记由标记标签t a g l a b e l 和标记值t a g v a l u e 组成，其中标记值可以为空。标记标签是该分支的名称，标记值是该分支连接的 目标。例如：上面节点的第一个节点标记是n a m e ： 2 ，n a m e 为节点标记标签， 2 为标记值，代表该节点第一个分支是n a m e 分支，其指向耳标为 2 节点。抽 象语法树上存在两种特殊的节点标记，一种是标记标签由两个单词组成的节点标 记，比如算术操作运算的左操作数由印和0 两个单词组成；另一种是标记值可以 为空的标记，比如上面节点的e x t e r n 标记。我们以n u m b e r 表示节点编号，1 d n e t 表示节点名字，t a g l i s t 表示节点标记的列表，抽象语法树节点的结构可以表示 为： n u m b e r1 d e n tt a g l i s t 以t a g l a b e l 表示节点标记标签，t a g v a l u e 表示节点标记值，t a g l i s t 的 每个元素可以表示为： 掰g 肌b e lt a g v a l u e 第四章以语法规则的形式给出了抽象语法树文件的结拇特征。抽象语法树由 具有上述结构的树节点构成，通常以函数声明节点f u n c t i o n _ d e c l 作为树根结点， 在根节点处逐渐展开，形成完整树结构。 例如，对于如下程序段： d 7 i n t m a i n o d 8厂 0 9 i n t a = o b = o ，c zo ： j d i