（计算机软件与理论专业论文）程序安全检查中的函数依赖分析.pdf

摘要 本文研究了c c + + 程序安全检查中的函数依赖分析。给出了一种低损失解除 递归函数依赖的算法。该算法通过分析程序语义，将函数调用划分为有条件调用 和必然调用。利用这些信息生成条件性程序调用图，并在图中低损失地解除递归 函数依赖关系，从而得到能引导跨过程静态安全检查的函数依赖拓扑序列。此外， 还设计并实现了一种精确性可调节的函数指针分析算法。该算法依据函数调用上 下文的经验性信息引导分析过程，尽量提高分析效率并降低时间开销。是一种介 于上下文敏感与非敏感之间，控制流敏感以及域敏感的算法。通过修改经验性信 息的结构可以得到两种分析精度不同的方法。 关键词：函数依赖安全检查函数指针上下文敏感流敏感 a b s t r a c t f u n c t i o nd e p e n d e n c ea n a l y s i si nc c + + p r o g r a ms a f e t yc h e c ki ss t u d i e di nt h i s p a p e r ar e c u r s i v ef u n c t i o nd e p e n d e n c ee l i m i n a t i n gm e t h o di sp r o p o s e dw h i c hc a u s e s l e s sl o s so ff u n c t i o nd e p e n d e n c ei n f o r m a t i o n i nt h i sm e t h o d ，f u n c t i o nc a l l sa r e p a r t i t i o n e di n t ot w ot y p e sd e p e n d i n go nt h ec o n d i t i o nt h ec a l l sa r ei n v o k e d ：o n ei st h e c o n d i t i o n a la n dt h eo t h e ri st h em u s t t h e np r o g r a mc a l lg r a p hw i t ht h i si n f o r m a t i o ni s c o n s t r u c t e d a f t e re l i m i n a t i n gt h ec i r c l e si nt h eg r a p hc a u s e db yr e c u r s i v ef u n c t i o n s ，a t o p o l o g i c a lo r d e ro ff u n c t i o nd e p e n d e n c ec a nb eg e n e r a t e dw h i c hi su s e dt og u i d et h e i n t e r - p r o c e d u r a ls a f e t yc h e c k b e s i d e s , af u n c t i o np o i n t e ra n a l y s i sa l g o r i t h mi s p r e s e n t e d i tg a t h e r sf u n c t i o np o i n t e rv a l u e si nt h ep r o g r a m st ob ea n a l y z e db a s e do rt h e e x p e r i e n c ei n f o r m a t i o no ff u n c t i o nc o n t e x t si na ne f f i c i e n tw a y t h er e s u l ti sb e t w e e n c o n t e x t - s e n s i t i v ea n dc o n t e x t - i n s e n s i t i v e a n di sf l o w - s e n s i t i v ea sw e l la sf i e l d s e n s i t i v e b ym o d i f y i n gt h ea r c h i t e c t u r eo ft h ee x p e r i e n c ei n f o r m a t i o n , t w ot y p e so fa n a l y z i n g m e t h o d sa r eg e n e r a t e dw i t l ld i f f e r e n te f f i c i e n c ya n dc o s t k e y w o r d s ：f u n c t i o nd e p e n d e n c e c o n t e x t - s e n s i t i v e s a f e t yc h e c k f u n c t i o np o i n t e r f l o w s e n s i t i v e 创新性声明 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得西安电子科技大学 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究工 作所做的任何贡献均己在论文中作了明确的说明并表示了谢意。 申请学位论文若有不实之处，本人承担一切相关责任。 本人签名：翌壁丝日期：鲨生玺! 目1 7 日 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其他复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密在年解密后适用本授权书。 本人签名：翌仝丝日期：翌! 釜! 旦，目 导师签名： 第一章绪论 第一章绪论 1 1 研究背景 本文的研究源于某实际开发项目，随着计算机科学的发展，软件涵盖的领域 日益扩大，软件的安全性已成为系统是否稳定可靠的关键，逐渐为人们所关注， 特别在军事、航天等领域软件安全受到了更加高度的重视。它主要分为两类： ( 1 ) 软件本身由于设计缺陷导致运行过程中出现不可预期的错误： ( 2 ) 外界针对软件本身的设计缺陷所作的恶意攻击。 本文主要研究第一类问题，即分析软件本身存在的安全问题。研究和总结 c c + + 源程序中可能存在的指针非法弓 用和内存泄露等指针相关的安全漏洞，并设 计一个基于静态分析的程序安全检查工具。该工具可对c c + + 程序源代码进行基 于指针状态数据流分析的安全检查，力求达到较高的检查精度。 本文重点讨论了该静态安全检查工具中的函数依赖分析，即研究函数调用产 生的函数依赖关系对跨过程静态安全检查的作用，并分析函数指针以得到函数指 针的指向信息，从而提高函数依赖分析及安全检查的精度。在c c + + 程序的静态 安全检查中，需以函数之间的调用依赖关系来引导检查过程。函数递归增加了函 数依赖分析的难度，如何处理递归函数依赖并顺利引导跨过程分析成为一个难点。 目前相关的文献很少，有些解除函数递归的算法虽然效率较高，但是损失了较多 的函数依赖。此外，函数指针会影响函数依赖，因此需要分析函数指针并将其纳 入安全检查范围。常见的函数指针分析是为了获得精确的程序调用图，如s c a n z h a n g 和b a r b a r agr y d e r 等人在生成c 程序的程序调用图时使用的f a 函数指针 分析法【1 】【2 】，其精确性并不满足安全检查的需求。其它通用的指针分析算法如 s t e e n s g a a r d 算法 3 1 1 4 1 和a n d e r s o n 算法1 4 1 在效率和精确性上各有优势，但都不适合安 全检查。因为安全检查不仅要考虑函数指针对函数调用关系的影响，还需要明确 函数指针随控制流的变化。 1 2 软件安全性检查工具 软件的安全性检查依据是否需要运行被检查的软件可分为动态和静态两种。 动态方法如动态测试等，静态方法包括定理证明、模型检验、自动验证等。静态 方法与动态方法相比具有无需运行被检查软件的优点。 基于程序分析的静态检查方法是一种重要的软件静态检查方法，它通过对程 序源代码的分析来查找软件中存在的安全漏洞，经过数十年的发展，针对程序中 常见的一些安全漏洞等，已经积累了大量的研究成果，并且分析技术也较为成熟， 2 程序安全检查中的函数依赖分析 并出现了许多程序安全性的规范与标准，如工业界的m i s r ac 编程规范【5 1 、n a s a 的软件安全报告与安全编程指南f 6 】f 7 】等，这些规范和指南有的侧重于指导开发者编 写安全的程序，有的侧重于指出常见的安全漏洞。与此同时，也出现了许多实用 的程序静态安全检查工具。 p r e f i x 和p r e f 缸t m j ，p r e f i x 是一种通过定义c c + + 程序中各种语句的前后置 条件，并利用该条件来执行安全性检查的工具。p r e f a s t 是在p r e f i x 的基础上发 展出来的后续工具，在程序的执行效率方面有所提高。这两个工具的特点是都专 注于提高程序检查的准确性。 s p l i n t g j 和p c i i n d l 0 1 ，s p l i n t 是一个开放源代码项目，主要面向c 程序的安全检 查，而p c i i n t 是一个商业软件，它能够检查c + + 程序，可检查的漏洞范围比s p l i n t 大。两者都是从支持用户添加注释来引导安全检查的l i n t 发展起来的。 这些工具可以检查出大部分常见的安全漏洞，但是对诸如函数指针等复杂的 语言机制，支持的力度还是比较弱的，因此在分析大量使用了函数指针的程序时， 效果并不好。 本文研究的静态安全检查工具是在某c ，c + + 静态安全检查工具的基础上开发 的。该工具作为研究基础具有如下特点：使用g c c ( g c cc o m p i l e rc o l l e c t i o n ) 前 端分析待检查的程序源代码来生成以抽象语法树( a b s t r a c ts y n t a xt r e e ，a s t ) 为 主的程序中间表示，然后分析a s t 收集符号表信息，并获得函数依赖关系。将得 到的符号表以及根据函数依赖排序后的各函数的a s t 交给后端安全分析模块处 理。该工具支持以完整程序代码为单位的自下而上检查，采用了一种基于契约的 安全检查方法【l “，使用契约描述安全规则，并允许程序员通过外部配置文件修改 或添加契约，从而修改或添加安全规则来控制安全检查行为。该工具可检查缓冲 区越界访问、资源泄漏、指针非法引用、控制流、类定义、异常等常见的安全漏 洞。但是该工具存在如下弱点：前端过于依赖g c c 生成的程序中间表示，处理递 归函数依赖时损失了较多的函数依赖信息且未分析函数指针，安全检查主要依靠 遍历a s t ，控制流和数据流分析较弱。本文研究的c ，c + + 静态安全检查工具与该 工具相比做出了如下改进： ( 1 ) 采用自定义的前端模块完成对c c + + 代码的语法分析，可以根据安全检 查的需要搜集程序信息，生成适合安全检查的程序中间表示如控制流图等，独立 性较强。该前端模块是由程序分析器生成器a n t l r t l 2 生成的。a n t l r 是一种l l ( k ) 分析器生成器，它能按用户定义的a n t l r 源程序自动生成分析器。 ( 2 ) 处理递归函数依赖时的依赖损失较小，能分析函数指针，能提供较完善 的函数依赖关系，并将函数指针纳入安全检查范围。 ( 3 ) 以数据流分析为主，主要检查指针相关的安全漏洞，力求提高指针相关 安全漏洞的检查精度，如内存泄露、指针非法引用等。 第一章绪论 本文研究的c ，c + + 静态安全检查工具的整体框架图如图1 1 所示。 源代码 前端 t+ l 语法分析li 配置管理l 毽曼曩篓箩lt 配置信息 如搏县喜l 一 控制流图的生成 l 携带抽象语法树的控制流图 i 后端 t 函数依赖分析契约配置管理 卜_ t 指针别名分析k函数契约引擎 依赖 指针别名信目1r 信息 ，r 0 契约信息 指针引用有效性和资源泄露检查 + - l 错误报告管理l 契 约 配 置 文 件 图1 1c c + + 程序静态安全检查工具整体框架 该工具可大体分为两部分：前端i ”】和后端。前端负责分析待检查程序的源代码， 收集符号信息、生成a s t 和控制流图。后端依据前端生成的信息，在数据流分析 过程中采用基于契约的安全检查方法，检查程序中存在的安全漏洞，并生成详细 的错误报告。可细分为如下模块： ( 1 ) 函数依赖分析：通过分析程序的语义，解除递归函数依赖并尽量降低对 函数依赖造成的损失。分析程序中的函数指针，获得函数指针的指向信息以及函 数指针对函数依赖的影响。生成函数调用拓扑序列，以此确定后续安全检查分析 各个函数的次序。该模块是本文的主要研究内容。 ( 2 ) 指针别名分析f 1 4 】：采用自顶向下的分析方法，交替记录过程内和跨过程 的指针别名信息，供后续的跨过程安全检查使用。 ( 3 ) 契约配置管理和契约引擎【”】：制定安全规则和方法，设计和实现程序分 析和安全检查模块所需的契约相关的存储结构和方法，为后续安全检查提供必要 的信息。 ( 4 ) 指针引用有效性和资源泄漏检查以及错误报告管理【l6 j ：以函数依赖拓扑 序列引导分析各函数的次序，通过数据流分析来完成安全检查，检查过程中采用 基于契约的安全分析方法。安全漏洞以错误报告的形式输出。 1 3 论文的主要工作及论文的组织 本文主要研究了c c + + 程序静态安全检查中的函数依赖，并设计和实现了 4 程序安全检查中的函数依赖分析 c c + + 静态安全检查工具中的函数依赖分析部分，具体工作内容如下： ( 1 ) 研究递归函数依赖对跨过程静态安全检查的影响，提出一种低损失解除 递归函数依赖的算法。 ( 2 ) 提出一种适合静态安全检查的函数指针分析算法，分析函数指针对函数 依赖的影响。把函数指针分析的结果纳入安全检查的范围。 本文共分四章，各章内容安排如下： 第一章绪论分析了软件安全及静态安全检查的现状并着重探讨了函数依赖 分析的现状，介绍了本文研究的静态安全检查工具的整体框架以及本人所做的工 作。 第二章静态安全检查中的函数依赖详细探讨了函数依赖的表现形式，以及函 数依赖对跨过程静态安全检查的作用，并分析了函数递归调用对函数依赖的影响， 研究了现有的解除递归依赖的算法，然后设计并实现了一种基于程序语义的低损 失解除递归依赖的算法。最后引入了一种“还债”的降低函数依赖损失的思想。 第三章函数依赖分析中的函数指针分析首先研究了常见的函数指针数据 流分析算法，然后提出了一种适合静态安全检查的经验性信息驱动的算法并给出 了它的设计与实现。最后，将该算法与传统算法进行了比较。 第四章结束语总结了本文所作的研究工作，分析了工作成果及不足之处。 第二章静态安全检查中的函数依赖 5 第二章静态安全检查中的函数依赖 2 1 相关技术 定义2 1 控制流图( c o n t r o lf l o wg r a p h ，c f g ) 有向图g = ( v ，e ) ，v 是节点的集合，e 是有向边的集合。其中节点表示语 句，边u v 表示从u 到v 可能的控制流。令缸v ) e 表示g 中的边u v ，称u 是v 的前趋，v 称为u 的后继，把这种表示顺序程序的有向图g 称为控制流图， 以下简称c f g 。 图2 1 是一个c f g 的例子。图中节点0 代表函数调用语句f o 。节点1 代表i f 语句，从节点1 分出t 和f 两个分支，节点2 、4 都是赋值语句，节点3 是返回语 句。 图2 1c f g 基于契约的跨过程安全检查方法是指将跨过程分析转化为过程内分析。契约 是程序语句的前置条件和后置条件的集合，即该语句能够正确、安全执行需要满 足的前提条件和正确执行后应该产生的结果。该方法自底向上分析程序中的各个 函数，位于调用关系底层的函数优先被分析，获得底层函数的契约后，再分析位 于调用关系上层的函数。各函数的契约在分析过程中被不断更新并用来检查每个 函数调用点处的当前状态是否满足被调用函数契约中的前置条件，以此来检查程 序的安全性。函数依赖分析生成的函数依赖拓扑序列可以反映上述函数调用的顺 序，可以引导后续模块分析各个函数的次序，因此函数依赖分析模块位于前端模 块之后，安全检查模块之前。 6 程序安全检查中的函数依赖分析 2 2 1 函数依赖和程序调用图 2 2 函数依赖 在跨过程静态安全检查中，需要一种能够描述函数之间调用关系的结构，最常 用的结构是函数依赖关系图和程序调用图。它们都是用来描绘程序中各函数之间 调用关系的静态结构。其中程序调用图更直观，易于理解和使用。 定义2 2 函数依赖 设a 、b 为两个函数，如果a 调用了函数b ，则称a 依赖于b ，记为b a 。 定义2 3 函数依赖关系图 若将任意函数依赖b a 中的a 、b 表示为结点，“一”表示为从b 到a 的有 向边，则对任意程序p ，所有函数的依赖关系集合就可以表示为一个有向图g ，称 为p 的函数依赖关系图。 定义2 4 程序调用图( p r o g r a mc a l lg r a p h ，p c g ) 如果将函数依赖关系图中的b a 反向，则程序p 的函数依赖关系图就被转化 为p 的程序调用图，以下简称p c g 。 由于p c g 直观地反映了函数间的调用关系，因此本文只用p c g 来表示函数之 间的调用和依赖关系。 图2 2 函数依赖关系图图2 3p c g 图2 2 和2 3 是某程序的函数依赖关系图及p c g 。从p c g 可见m a i n 函数调用 了f o o 和b a r ，而f o o 调用了f u n l 、t i m 2 以及f u n 3 。 2 2 2 函数依赖拓扑序列 定义2 5 拓扑排序( t o p o l o g i c a ls o n l 和拓扑序列( t o p o l o g i c a lo r d e r ) 对一个有向无环图g ( v ，e ) 进行拓扑排序m ，是将g 中所有顶点排成一个 线性序列，使图中任意一对顶点u 和v ，若 e e ，则i 1 在线性序列中出现在 v 之前。通常，这样的线性序列称为满足拓扑次序( t o p o l o g i c a lo r d e r ) 的序列，简称 拓扑序列。 第二章静态安全检查中的函数依赖 7 函数依赖拓扑序列是反映程序中函数调用顺序的一个偏序序列。如果程序p 中存在函数a 调用函数b ，即p 的程序调用图g 中存在a b ，那么在g 的拓扑 序列l 中，a 的位置比b 靠近头部。靠近序列尾部的函数处于p c g 较底层的位置， 靠近序列头部的函数处于p c g 较顶层的位置。 对图2 3 拓扑排序得到的拓扑序列如表2 1 所示： 表2 1 图2 3 的拓扑序列 从函数依赖拓扑序列尾部开始，以自底向上的顺序分析程序中的各个函数， 在分析过程中生成并检查各函数的契约，从而将跨过程安全检查转化为过程内检 查。由表2 1 可知，被调用的函数在拓扑序列中位于调用者之后，在安全检查中先 被分析，从而得到了被调用函数的契约，当检查到这些函数的调用点时，就可以 将它们的契约取出，并对调用点处的参数状态等上文进行检查。依据拓扑序列的 逆序检查各个函数，直到分析完毕，从而完成基于契约的跨过程静态安全检查。 2 2 3 函数递归对函数依赖的影响 1 函数递归 函数递归调用在高级程序设计语言里广泛存在，它可以分为两种： ( 1 ) 直接递归调用 如果程序p 中存在某函数a ，且a 中存在对自己的调用，那么就称这种递归 调用为直接递归调用，直接递归调用反映到p c g 中，是一个只有一条边构成的环。 ( 2 ) 问接递归调用 如果程序p 中存在函数a 、b ，且函数a 调用了函数b ，b 调用了c ，c 调用 了其它函数，如此调用下去，在后续调用的函数里，如果再次出现a ，则称程序p 中存在a 的间接递归调用。反映到p c g 中，是一个至少包含两条边的环。 图2 4 中函数b a r 为直接递归调用，函数f o o 调用f u n l ，f u n l 调用f u n 4 ，f u n 4 调用f u n 3 ，f u n 3 调用f o o ，属于间接递归调用。 s 程序安全检查中的函数依赖分析 图2 4 含有递归调用的p c g 一个可终止的程序在进入递归调用后，必定会在某条件满足后退出递归，否 则程序会永不停息的递归下去。因此可以判定构成递归的所有函数调用中，至少 有一个位于条件分支中，如位于i f - t h e n - e l s e 的某个分支中。 在自底向上的跨过程静态安全检查中，生成拓扑序列的前提是p c g 无环，但 是递归函数的存在使图中存在环。这样就无法确定该环中各个函数的调用顺序， 从而无法引导跨过程分析。因此要解除p c g 中的环，即解除递归函数依赖。 2 解除递归函数依赖的原则 p c o 中的环意味着函数递归调用，虽然可以通过解除环中某些边来解除递归 函数依赖，但是被解除的边对应的函数依赖信息随之丢失。 g 是程序p 的p c g ，假设存在两种解除环的策略s t r a t e g y l 和s t r a t e g y 2 ，它们 分别要解除x 和y 条边。 如果x 0 d oi f 如s p a t h 栈顶节点与某个非栈顶节点相同，即发现了环 t h e n 记录从栈项节点到栈中相同节点之间所有的节点到c i i c l e s 中； b l i s t = s b r o t h e r s p a t h t o p ； w h i l eb l i s t 为空或b l i s t 中的节点都被访问过 d op o p ( s p a t h ) ； b l i s t = s b r o t h e r s p a t h t o p ； i fs p a t h t o p = o t h e nb r e a k ； j f 在b l i s t 找到一个未被访问过的兄弟节点n t h e np o p ( s p a t h ) ； i n n o d e = i n ： e l s e 取出s p a t h s p a t h t o p 的所有孩子到列表l i s t 中； i f l i s t 为空或l i s t 中的节点都被访问过 t h e nb l i s t = s b r o t h e r s p a t h t o p ； w h i l e b l i s t 为空或b l i s t 中的节点都被访问过 d op o p ( s p a t h ) ； 。 b l i s t = s b r o t h e r s p a t h t o p i fs p a t h t o p - - - o ) 1 5 t h e f p = b a r ； 1 6 r e s u l t = f o o ( t h e f p ) ； 1 7 e l s e 18 t h e f p = f u n ； 1 9 r e s u l t = f 0 0 0 h e r p ) ； 2 0， 2 1 r e t u l t l 0 ： 2 2， 程序安全检查中的函数依赖分析 t h e f d = b a r r e s u l # f o o ( t h e f p ) 图3 6 函数m a i n 的c f g p j 调用d f s s c a l l 算法深度优先遍历m a i n 函数的c f g ，对每个c f g 节点调用 p r o c e s s c f g n o d e 算法，当分析第1 l 、1 2 号节点时，p r o c e s s c f g n o d e 发现该节点 是函数指针变量定义节点，于是在当前函数指针信息中加入函数指针变量r e s u l t 和也e f p 。当分析到1 4 号节点时，p r o c e s s c f g n o d e 判断出这是一条条件选择语句 的节点，于是选择一条分支进行深度优先遍历，假设选择了t 分支。分析到1 5 号 节点时，p r o c e s s c f g n o d e 判断出该节点是一个语句表达式节点，取出其a s t 并调 用p r o c c s s a s t 处理，p r o c e s s a s t 判断出这是一条赋值语句，于是调用p r o c e s s a s s i g n 完成赋值动作，修改当前经验性信息，使t l l e f p 指向b a r ，并在该节点保存新的指 向信息。当分析到1 6 号节点时，同理，p r o c e s s c f g 判断出1 6 号节点是一个语句 表达式节点，调用p r o c e s s a s t 处理，p r o e e s s a s t 判断出这是一条包含函数调用的 赋值语句。首先调用p r o c e s s f u n c c a l l 处理函数调用，然后利用函数调用的返回值 完成赋值动作。由于被调用的函数f o o 目前没有经验性信息，因此要分析f o o 的 c f g 。首先从当前函数指针信息中取出t h e f p 的指向信息作为实参，新建并初始化 一个函数指针信息结构作为f o o 内部的当前函数指针信息，使邱的指向与l c f p 相同，即昂指向b a r 。并将m a i n 函数的当前函数指针信息入栈保存。分析f o o 的 第三章函数依赖分析中的函数指针分析 4 l c f g 后得到了f o o 的经验性信息为：“b a r ) - b a r o p 当形参审指向b a r 时，返回值 为b a r 。从栈中弹出m a i n 函数的函数指针信息作为当前函数指针信息。将返回值 作为斌值语句的值赋给r e s u l t ，并更新当前函数指针信息的内容，在1 6 节点保留 更新后的信息，完成了p r o c e s s a s s i g n 的处理。当分析到2 1 号节点时，分析到c f g 的结束位置，开始回溯，当回溯到1 4 号节点时，开始分析i f 的另一条分支，即f 分支。分析1 8 号节点时类似于1 5 号节点，分析1 9 号节点时类似于1 6 号节点， 即先处理函数调用再处理赋值。由于f o o 的经验性信息已存在，因此取出其经验性 信息与当前函数调用上文( 此处为函数实参) 作比较，由于此时的实参为f u n ，而 经验性信息为“b 缸 - b a r ，因此，经验性信息中不包含函数调用上文的内容，即 不匹配，需要重新分析f o o 的c f g 。分析结束后，得到f o o 的返回值为f u n 。f o o 的经验性信息被扩充为“b 鸲f u n b a r , f u n ，它表示当形参邱指向b a r 或者f u n 时，返回值为 b a r , 缸l 。返回到m a i n 后，处理1 9 号节点的赋值语句，r e s u l t 被更 新为t i m 。修改当前函数指针信息并在该节点保存。当到达2 0 号节点时，由于前 面在分析t 分支时，2 0 号节点没有保存指针信息，2 0 号节点与1 6 号节点共享信 息。通过比较1 6 号和1 9 号两个节点的信息可知，在交汇点2 0 号节点，应该将两 者的当前函数指针相关信息合并后保存。由于2 0 号节点的信息被更新，因此仍需 对2 0 号节点进行深度优先遍历，这样分析会继续到2 l 号节点。分析完毕后，回 溯直到对m a i n 的c f g 深度优先遍历完毕。最终1 6 号节点处r e s u l t 指向b a r ，1 9 号节点处r e s u l t 指向f u n ，函数f 0 0 的经验性信息位 b 鸡f u n b a r , f u n 。 6 修改经验性信息的结构以调节分析精度和效率 在笔者提出的算法中，直接取出经验性信息的内容作为结果是上下文非敏感 的，因为它依赖统计得到的数据，而通过分析被调函数的c f g 获得的结果是上下 文敏感的。前者是精确结果的超集，但由于经验性信息在扩充的同时即被使用， 因此所得结果又是上下文非敏感结果的子集，其精确性比上下文非敏感高。可见， 本算法综合了上述两种情况，达到了介于上下文敏感和非敏感之间的分析效果。 在某些情况下，如被分析的代码规模较小时，宜采用上下文敏感的分析方法。 当代码规模较大时，宜采用介于上下文非敏感与敏感之间的分析方法。为满足变 化的需求，通过修改经验性信息的结构来实现两种分析方法，这两种分析方法对 应的经验性信息为；集合对应型经验性信息和元素对应型经验性信息。前者与后 者相比，前者对应的分析方法效率较高，精确性相对较低，后者精确性较高，达 到了上下文敏感，但分析效率较低。因此可以根据需要选择采用哪种算法。 ( 1 ) 集合对应型经验性信息( s e t b a s e d ) 算法p r o c e s s a s t 和p r o c e s s f u n c c a l l 采用介于上下文非敏感与敏感之间的方 法，经验性信息的上文与下文的对应关系是集合之间的对应关系，他们的内容是 分析到目前的所有可能值，这种方法可称为s e t - b a s e d 法。上述算法都是s e t b a s e d 4 2 程序安全检查中的函数依赖分析 型算法。 下面是采用s e t - b a s e d 型算法( 即上述算法) 分析一段代码得到经验性信息的 过程及经验性信息的结构。 代码实例3 5 0 1 t y p e d e f h a t ( f u n c p t r ) o ； 0 2i n tf u n c a 0 0 3h a tf u n c b 0 ) 0 4f u n c p t rf o o ( f u n c p t rf p ) 0 5r e t u r nf p ； 0 6 0 7i n tm a i n 0 0 8f u n c p t rm y f u n c - - f o o ( f u n c a ) ； 0 9 m y f u n c = f o o ( f t m c b ) ； 1 0 m y f u n c = f o o ( f u n c b ) ； l l 分析到第8 行时，函数f o o 的实参为f u n c a ，通过分析f o o 的c f g ，得到其当 前返回值为f u n c a ，并将其并入到经验性返回值集合中得至ut f u n c a ，如表3 4 所示。 表3 4 当前参数审 经验性参数当前返回值经验性返回值 分析f o o 前 f u n c a 空空 空 分析f o o 后 f u n c a f u n c a f u n c a f u n c a 当分析到第9 行时，函数f o o 的实参为f u n c b ，而经验新信息中的经验性参数 中没有f u n c b ，因此f o o 要被重新分析。经过分析，得到了函数f o o 的当前返回值 为f u n c b ，并记入经验性信息的经验性返回值中，如表3 5 所示。 表3 5 当前参数币 经验性参数当前返回值经验性返回值 分析f o o 前 f u n c b f u n c a 空 f u n c a 分析f o o 后 f u n c b f u n c a ，f u n c b f u n c b f u n c a ，f u n c b 在分析第1 0 行时，当前的实参为f u n c b ，但由于经验信息中的经验性参数中 已经存在f u n c b 了，因此不必再次分析f o o 函数的c f g ，直接取出经验性返回值 f 2 ，f 3 1 1 f 1 ，f 2 ，f 3 f 1 ，f 2 ，1 3 ) f 1 ，f 2 ，f 3 f l ，f 2 ( f 2 ) f 2 ，t 3 1 2 n ，f 2 ，f 3 f 1 ，f 2 ，f 3 ) f l ，f 2 ，f 3 n ，f 2 ) f 2 ) f 2 ，t 3 ) 表3 1 2s e t b a s e d 与e l e m b a s e d 型算法的结果 s e t - b a s e de l e m b a s e d 行号 p t r lp t r 2p t rp t r lp t r 2p t r 0 8 f 1 ) f 2 空 f l f 2 ) 空” 0 9 f 2 ) f 2 空 f 2 f 2 空 1 0 也) 岔) 晓 f 2 ， f 2 f 2 1 l f 2 ) f 2 f 3 ) f 2 f 2 f 3 1 2 f 2 ， f 2 f 2 ，f 3 ) 霞)f f 2 ， f 2 ， 3 5 函数指针分析前后的函数依赖的比较 通过函数指针分析，使函数依赖更加精确，p c g 中的边更多，拓扑序列更接 近程序本身。下面针对代码实例3 。7 分别就采用函数指针分析与不采用函数指针分 析所得到的p c g 和拓扑序列作出比较。 函数指针分析 前生成的p c g 函数指针分析 后生成的p c g 图3 7 函数指针分析前后p c g 的比较 亳 大詈 薯 程序安全检查中的函数依赖分析 表3 1 3 函数指针分析前后生成的拓扑序列的比较 i是否分析函数指针拓扑序列 i否 f 1 ，也，f 3 ，m a i n ，c a l l e r 是f 1 ，m m n ，c f l l e r , f 2 ，f 3 在代码实例3 7 中，如果函数依赖分析时不考虑函数指针，就无法得到c a l l e r 函数中p 仃的指向，因此也就无法得知c a l l e r 函数内部究竟调用了哪个函数。由此 生成的拓扑序列如表3 1 3 第一行所示，后期跨过程安全检查对各个函数的分析顺 序为：c f l l e r 、m a i n 、f 3 、亿、n 。首先对c f l l e r 函数进行安全检查，当检查到第5 行时，由于无法获取函数指针信息，因此无法对该调用进行安全检查。检查完c a l l e r 函数后，生成了c a l i 盯的契约。然后检查m a i n 函数，在第1 0 行，m a i n 调用了c a l l e r 函数，于是，取出c f l l e r 的契约与当前调用上文进行比较。由于c a l l e r 函数内部虽 然利用函数指针p t r 对f 2 和f 3 进行了调用，但这种依赖信息因为未分析函数指针 而无法获得，因此c f l l e r 的契约信息是不精确的，导致m a i n 函数对c f l l e r 的调用 点处利用c a l l e f 的契约所作的安全检查结果也是不精确的。此外 当采用了函数指针分析之后，所得到的拓扑序列如表3 1 3 第二行所示，跨过 程安全检查对各个函数的分析顺序为f 3 ，f 2 ，c a l l e r ，m a n ，f 1 。先检查f 3 和f 2 ，生成 了这两个函数的契约，再检查c f l l e r ，由于p t r 参数的指向信息已经在前面的函数 指针分析模块得到，因此当检查到第5 行时，可以知道c a l l e r 调用了f 2 和f 3 ，因 此取出岔和f 3 的契约分别在该调用点进行安全检查，检查完c a l l e r 后，生成了c a l l e r 的契约，再检查m a m ，依次类推使基于契约的跨过程静态安全检查的精确性得到 了保证。 可见函数指针分析的引入不但使函数依赖更精确，提高了跨过程安全检查中 函数分析顺序的精确性，也将函数指针纳入了安全检查，扩大了安全检查的范围。 第四章结束语 第四章结束语 本文着重研究了c ，c + + 静态安全检查中的函数依赖，并完成了一个c c + + 静 态安全检查工具中函数依赖模块的设计与实现。主要做了以下工作： ( 1 ) 通过分析递归函数依赖的特点，设计并实现了一种低损失解除递归函数 依赖的算法，该算法首先分析程序的语义，获得函数调用的条件性信息，构建附 带这些信息的c p c g - ，然后利用这些条件性信息完成查找、解除递归环以及拓扑排 序的工作，生成能引导跨过程安全检查的拓扑序列。然后，进一步探讨了如何降 低函数依赖的损失，并引入了一种“还债”的思想。 ( 2 ) 在比较了传统的函数指针分析算法的基础上，设计并实现了一种适合静 态安全检查的函数指针分析算法。该算法在跨过程函数指针数据流分析中自顶向 下模拟程序执行流程，以经验性信息驱动分析过程，介于上下文敏感与不敏感之 间，是一种流敏感且域敏感的算法，并实现了可调节的精确性。 上述工作提高了函数依赖的精确性，使跨过程静态安全检查的函数分析顺序 更接近程序本身，而且将函数指针也纳入安全检查范围，提高了安全检查的精度。 但是，本文所作的工作中依然存在一些不足之处： ( 1 ) 处理递归函数依赖时仍需要解除递归，损失函数依赖信息，虽然提出了 “还债”的思想，但是实现难度较大需要进一步研究。 ( 2 ) 函数指针分析的e l e m - b a s e d 算法在处理含有大量函数指针相关参数的函 数时效率较低，有待进一步改善，在实现时优先选择了s e t b a s e d 型算法。_ 致谢 致谢 感谢我的导师刘坚老师。刘老师在本文的研究过程中始终以严谨的治学态要 求我们，并且在百忙之中不断对工作的进展和出现的问题进行指导，这种精神始 终感染着每个人，为我们能够顺利完成工作打下了坚实的基础。无论是在学习上 还是研究中以及论文的编写过程中，刘老师一贯的一丝不苟的精神以及严谨的态 度是所有工作成果的保证，我们学到了很多。 感谢张立勇老师，张老师定期地检查研究的进展以及出现的问题，及时地与 刘老师沟通，并帮助我们解决了很多难点，使我们受益匪浅。 感谢在研究和论文撰写中帮助过我的其他同学：曹俊亮、蒋辉、马志宇、施 珍珍，以及张延春师姐及其他师兄对我的指导和帮助，他们对我提供了多方面的 支持。 感谢我的父母兄弟，这么多年的学习生活，是他们一直在支持我，关心我， 无论生活，学习都无微不至。 感谢所有关心和帮助过我的老师、同学和朋友们，在此一并表示我真诚的谢 意。 参考文献 【2 】 【3 】 【5 】 【6 】 7 1 8 】 【9 】 【lo 】 【1 1 】 【1 2 】 【1 3 】 【1 4 】 f 】5 】 【1 6 【1 7 】 1 8 】 【1 9 】 参考文献 s c a nz h a n g , b a b a r agr y d e r , w i l l i a ml a n d i p r o g r a md e c o m p o s i t i o nf o rp o i n t e ra l i a s i n g ： as t e pt o w a r dp r a c t i c a la n a l y s e s p r o c e e d i n g so ft h e4 t ha c ms i g s o f ts y m p o s i u mo n f o u n d a t i o n so f s o f t w a r ee n g i n e e r i n gn e w y o r k , 1 9 9 6 u s a ：a c mp r e s s ，1 9 9 6 ，8 1 9 2 ， a r mm i l a n o v a , a t a n a sr o t m t e v , b a r b a r ag r y d e r p r e c i s ec a l lg r a p h sf o rcp r o g r a m sw i t h f u n c t i o np o i n t e r s a u t o m a t e ds o f h v a r ee n g i n e e r i n g , 2 0 0 4 ，11 ( 1 ) ：7 - 2 6 b a j a m es t e e n a g a a r d p o i n t s - t oa n a l y s i si na l m o s tl i n e a r li m e p r o c e e d i n g so ft h e2 3 r d a c ms i g p l a n s i g a c ts y m p o s i u mo np r i n c i p l e so fp r o g r a m m i n gl a n g u a g e s ，n e w y o r k , 1 9 9 6 u s a ：a c m p r e s s ，1 9 9 6 ，3 2 - 4 1 m a n u v i rd