（计算机软件与理论专业论文）基于控制流图的指针引用合法性检查.pdf

摘要 本文以基于控制流图的数据流分析技术为基础，研究c c + + 程序中指针引用 的合法性检查。首先分析指针非法引用的各种表现形式和产生原因，构建具体的 检查规则；然后以控制流图为数据流分析的中间表示，对指针的无效引用和指针 引用造成的资源泄漏进行检查；同时结合函数依赖分析获取的拓扑序列，采用自 下而上的分析方法实现跨过程的安全检查。 为了提高检查结果的准确性和检查过程的效率，提出了一种基于控制流图的 改进数据流分析方法。通过获取和分析控制流信息模拟程序的动态执行，并结合 记录指针变量状态的方法实现对指针非法引用的检查。 文中的检查方法己应用到一个具体的安全检查工具上，实践证明该方法是有 效的。论文最后讨论了目前开发过程中有待完善和进一步研究的问题。 关键词：安全检查控制流图数据流分析指针无效引用资源泄漏 a b s t r a c t b a s e do nd a t af l o wa n a l y s i st e c h n o l o g i e so nc f g ( c o n t r o lf l o wg r a p h ) ，p o i n t e r r e f e r e n c ev a l i d i t yc h e c k i n go fc c 抖p r o g r a mi ss t u d i e di nt h i sp a p e r f i r s to fa 1 1 a g r o u po fs a f e t yc h e c k i n gr u l e sa r ec o n s t r u c t e db ys t u d y i n gr e p r e s e n t a t i o n sa n dc a u s e so f i n v a l i dp o i n t e rr e f e r e n c e t h e nt h ei n v a l i dp o i n t e rr e f e r e n c ea n dr e s o u r c el e a kc a nb e c h e c k e db yu s i n gc f g 勰t h ei n t e r m e d i a t er e p r e s e n t a t i o no fd a t af l o wa n a l y s i s a n da b o t t o m t l pa n a l y s i sp a t t e mi sa d o p t e di nt h ei n t e r - p r o c e d u r a lc h e c k 、i t l lt h et o p o l o g i c s e q u e n c eo ff u n c t i o nd e p e n d e n c e f o rs a t i s l y i n ga c c u r a c ya n de f f i c i e n c yr e q u i r e m e n t s ，a ni m p r o v e dm e t h o do fd a t a f l o wa n a l y s i si s p r o p o s e di nt h i sp a p e r t h ec h e c ko fi n v a l i dp o i n t e rr e f e r e n c ei s i m p l e m e n t e db yr e c o r d i n gp o i n t e rv a r i a b l es t a t u si nt h ep r o c e s so fp r o g r a me x e c u t i o n s i m u l a t e db ya c q u i r i n ga n da n a l y z i n gc o n t r o lf l o wi n f o r m a t i o n t h em e t h o dp r o p o s e di nt h i sp a p e ri si m p l e m e n t e di nas a f e t yc b e c k e rf o rc c + + p r o g r a m ，e x p e r i m e n t a lr e s u l t si l l u s t r a t et h a tt h i sm e t h o di se f f e c t i v e a n dal i s to f d r a w b a c k so ft h ec u r r e n ti m p l e m e n t a t i o na n dt h ei m p r o v e m e n tt h a tm a yb ea p p l i e di n t h ef u r t h e rd e v e l o p m e n ta r ea l s op r o p o s e d k e y w o r d s ：s a f e t yc h e c k i n gc f gd a t a f l o wa n a i y s i s i n v a l i dp o i n t e r r e f e r e n c er e s o u r c el e a k 创新性声明 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特j $ l j ；l l l 以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得西安电子科技大学 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究工 作所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文若有不实之处，本人承担一切相关责任。 本人签名： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其他复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密在年解密后适用本授权书。 本人签名： 导师签名： 日期：2 丑垒! 童! 璺 日期：丝z 厶，0 第一章绪论 第一章绪论 1 1 研究背景 随着计算机技术和网络技术的飞速发展和广泛应用，软件安全问题成为一个 日益突出的问题，特别是军事领域的软件安全问题已越来越受到人们的重视。 一般的，存在于计算机软件系统中的安全性隐患，有系统外部的攻击如系统 入侵、信息窃取和病毒等，也有系统自身问题造成的各种安全漏洞。这些都会使 得软件在使用阶段出现意想不到的错误，从而造成重大损失。本文主要以c c + + 程序设计语言为研究对象，采用静态程序分析技术和静态检查方法研究由于软件 系统自身问题造成的各种安全漏洞【2 】【3 】【4 】，并将各种分析技术和检查方法应用到 一个具体的安全检查工具上。 c c + + 程序设计语言中由于指针非法引用造成的安全问题有：指针的无效引用 和指针引用造成的资源泄露等，本文以这两种类型的问题为研究对象讨论指针引 用的合法性检查。 1 1 1 程序分析和静态检查 程序分析【5 】技术是以程序为处理对象，按需求对其进行各种分析的技术，目的 是提高程序的性能，判定程序的正确性。程序分析在程序理解、程序测试、程序 优化和程序重构等方面有着重要的作用。 不同的程序分析技术7 l 侧重于不同的方面： 1 1 从不同的角度分析程序，包括静态分析方法、动态分析方法和概念分析 方法等； 劲针对程序的不同方面进行分析，程序分析可以分为数据流分析和控制流 分析等； 3 ) 针对不同类型程序的分析技术，程序分析可分为顺序命令式程序的分析、 对象式程序的分析和并发程序的分析等。 以上各种程序分析技术依据学术领域和项目工程领域的不同需求各有所用。 其中，程序安全检查是程序分析的一个重要应用，目前学术研究领域中已经提出 了多种程序安全检查方法，如代码验证( c o d ev a l i d a t i o n ) 、模型检查( m o d e l c h e c k i n g ) 、进化测试( e v o l u t i o n a r yt e s t i n g ) 等。但是目前在常见开发项目中被广 泛使用的主要有两类方法，程序测试和静态程序安全检查。本文主要关注的是静 态程序安全检查。 2 基于控制流图的指针引用合法性检查 1 1 2 相关工作 本文主要以c c + + 程序设计语言中指针非法引用造成的问题为研究对象设计 和实现一个安全检查工具。目前用于c c + + 程序的静态程序安全检查工具【8 】和资源 泄漏检查工具已有很多，且多数都已实用化。不同的检查工具采用的安全检查方 法也不同，其中具有代表性的包括： ( 1 ) c o v e f i t y t 9 l c o v e r i t y 是由斯坦福大学计算机系统实验室为提高软件的可靠性和安全性而 研制的静态检查工具。c o v e r i t y 检查范围包括可能造成实际运行中系统崩溃的错 误，可被黑客茅用的源代码缺陷以及多线程程序中的错误等。目前c o v e r i t y - i - 具 已经被应用于l i n u x 内核源代码的安全性分析，并在多家商业公司中作为内部项目 开发时使用的代码安全检查工具。 ( 2 ) 微软静态检查工具家族 微软p p r c ( p r o g r a m m e rp r o d u c t i v i t yr e s e a r c hc e n t e r ) 是帮助微软开发耐用、 高性能和高可靠性安全产品的研究中心。它研究和开发的静态程序分析和检查工 具有：p r e f i x 、p r e f a s t t l 0 1 、f x c o p 、s d v 、a e g i s 和e s p l l “。其中p r e f i x 及其后 继产品p r e f a s t 和e s p 以c c + + 程序为检查对象。 p r e f i x 是j o n a t h a np i n c u s 设计并实现的基于程序分析的安全检查工具，它使 用前置条件和后置条件的概念定义c c + + 程序中各种语句的安全性条件，并利用 该条件执行语法安全检查；作为p r e f i x 的后续产品，p r e f a s t 专注予提高程序安 全检查的执行效率。p r e f i x 和p r e f 如t 都专注于提高检查结果的准确性。e s p 是 针对微软视窗系统启动的一组程序分析和安全检查项目。 ( 3 1s p l i n t l l 2 】和p c i i n t t l 3 1 s p l i n t 和p c i i n t 都是l i n t 工具的后继产品，s p l h a t 是一个开放源代码的项目， 目前只专注于c 语言安全检查。s p l i n t 主要采用类似早期l i n t 使用的程序员手工添 加注释的方法进行程序检查，并在诸如p o p t h 】等开放源代码项目中获得了应用。 而p c i i n t 则为商业软件，同样从l i n t 衍生。与s p l i m 相比，p c i i n t 增加了完善的对 c + + 安全检查的支持，可以覆盖更多的c c + + 安全漏洞。 ( 4 ) 检查和监测内存泄露的工具 目前，在实际的工程中，有许多适用于不同平台针对不同程序设计语言的内 存泄露检查工具。如l i n u x 下的内存泄露检查工具v a l g r i n d i ”】、m a l l o e d e b u g 和 k c a c h e g r i n d l l 6 1 等；w i n d o w s 下的内存泄露检查工具b o u n d c h e c k e t 、m u t e k b u g t r a p p e r 和p u r i t y l l 。1 ( w i n d o w s 版本) 等。其中，p u f f f y 的强大之处是可以找到应用程序中 全面的内存问题，它是一个r u n - t i m e 的工具，也就是说只有在程序运行过程中， 根据程序的运行情况来查看在某种运行条件下是否有内存的问题，它可以在一个 第一章绪论 非常复杂的程序中查找内存错误，包括多线程的程序，它也可以被用于测试： v a l g r i n d 是一个开源的内存泄露检查工具，它和g c c 【1 8 1 下的调试工具g d b 配合使 用对c ，c + + 程序中的内存泄露进行检查。 除了上述工具外，实际的项目工程领域和学术研究领域中同样有其他一些商 业化产品得到广泛应用，如c o d e w i z a r d l l 9 1 和s t l l i n t t 2 0 1 等。 1 2 项目框架及本文工作在项目中的位置 1 2 1 项目背景和框架 本文来源于一个实际科研项目所在课题。该课题专注于在制定的一组c c + + 程序设计的安全规范基础上，研究、设计并实现一个针对c c + + 程序的静态安全 检查工具。它的整体框架如图1 1 所示： 源代码( 源代码列表) 前端 j 上上 诱沾钋新 配置管理 t a s t 和符号表 配置信息 控制流图的生成 携带a 。t 信息的c ，g 后端工 函数依赖分析契约配置管理j 一 i 曩 指针别名分析r _ 簇i契约引擎i 别名信息 怎 t l契约信息 j 指针引用的有效性和资源泄露检查 i i 7 l错误报告管理 契 约 配 置 文 件 i 一一一一一一一一一一一一。一一一一一一一一一一一一一一一一 图1 1c c + + 安全检查工具框架图 c c + + 安全检查工具分为前端和后端两部分内容。其中，前端是后端分析和设 4 基于控制流图的指针引用合法性检查 计的基础，它的主要功能是通过分析项目源代码，为后端收集分析和检查需要的 各种信息，例如符号信息和控制流信息等。 1 ) 语法分析：通过源程序的语法分析，收集程序中的类型信息、变量信息 和函数信息等，并生成以函数为单位的抽象语法树： 2 ) 配置管理：负责提供用户配置和管理工具运行参数的接口。用户可以根 据实际需要，配置和管理工具运行需要的参数。例如根据实际分析项目 的规模配置符号表等。 3 ) 控制流图的生成：通过遍历抽象语法树，生成携带抽象语法树信息的控 制流图，作为后端分析和检查实现的基础。 后端主要是以数据流分析为主的安全检查实现部分，主要包括以下几个功能 模块： 4 ) 函数依赖分析：通过遍历控制流图以及函数指针的数据流分析，获取所 有函数的调用依赖关系，并根据该依赖关系产生函数调用的拓扑序列， 以此确定后续分析和安全检查的函数次序； 5 ) 指针别名分析( 主要指跨过程的指针别名分析) ：以控制流图和函数调用 的拓扑排序为基础，采用自上而下的分析方法，确定并记录跨过程的指 针别名信息，为后续的跨过程安全检查提供支持； 6 ) 契约配置管理和契约引擎的设计实现：以可定制的契约为研究对象，构 建程序分析和安全检查模式的存储结构和方法，为后续安全检查提供必 要的信息； 7 ) 指针引用的有效性与资源泄露检查：以控制流图为数据流分析的中间表 示，对指针引用的有效性和资源泄漏进行检查； 8 ) 错误报告管理：接受安全检查过程中得到的错误信息，并整理成错误报 告以支持多种模式的错误信息输出机制。 1 2 2 本文工作和组织 1 本文的工作 本文在项目的开发过程中负责设计和实现指针引用的有效性和资源泄露检查 模块。具体的工作有： ( 1 ) 设计和实现控制流图，为前端语法分析提供容器支持并为后端数据流分析 提供基本的载体； ( 2 ) 分析指针非法引用的表现和原因，定义并归纳整理指针变量的引用状态； 基于已有研究成果i ”，制定分析和检查实现过程中具体的检查规则： ( 3 ) 设计和实现基于控制流图的指针引用的有效性和资源泄露检查模块的总 第一章绪论 体框架，针对检查过程中遇到的一系列问题给出相应的解决方案，并加以 设计和实现； ( 4 ) 设计和实现错误报告管理模块，支持多种模式下的错误信息输出机制； ( 5 ) 设计测试用例并进行结果对比分析，进行方法的正确性和有效性验证。 2 本文的组织结构 本文第一章介绍了当前课题的研究现状，并对本文的项目和所做的工作做了 一个简要的介绍。本文的后续内容安排如下： 本文第二章是指针引用合法性检查的基础，介绍了本文在项目中使用到的工 具和技术，描述了数据流分析载体控制流图的设计和实现，并在讨论了指针非法 引用的表现和产生原因后确立了本文安全检查的方法和具体的检查规则。 本文第三章指针引用合法性检查模块的设计、实现及关键技术，详细讨论和 描述了指针引用合法性检查模块设计和实现过程中的方法和技术，并对关键问题 提出了具体的解决方案。本文第二章和第三章是本文的主要内容。 本文第四章实例分析，通过具体的实例分析和结果对比验证指针引用合法性 检查方法的正确性。 本文第五章是本文的结束语部分，通过总结本文已完成的工作并列举不足之 处和未完成的内容，展望未来工作重点和下一步的研究方向。 第二章指针日l 用合法性检查的基础 第二章指针引用合法性检查的基础 指针引用的合法性检查，是基于源代码语句级别的程序分析。它是以分析器 自动生成工具a n t l r 生成的控制流图为中间表示，以函数依赖分析的拓扑排序结 果为基础，由契约引擎配合支持的采用记录指针变量状态方法的静态检查。 2 1 使用到的工具和技术 2 1 1a n t l r 和抽象语法树 分析器自动生成工具a n t l r 【2 1 】( a n o t h e rt o o lf o rl a n g u a g er e c o g n i t i o n ) 是 项目前端语法分析使用到的工具( 见图1 1 框架图) 。a n t l r 是由s a n f r a n c i s o 大 学t e r e n c ep a r r 等人开发的一种分析器自动生成工具，它采用l l ( k ) 文法并支持多 种目标语言。a n t l r 作为一个免费、开源的工具，已经在研究领域和商业领域得 到广泛使用。 a n t l r 集词法分析、语法分析和语义处理于一身，可以生成词法分析器、语 法分析器和抽象语法树遍历框架( t r e ew a l k e 0 。它采用e b n f ( 扩展巴克斯范式) 来 描述词法规则、语法规则和抽象语法树结构，并且支持在同一个文件中描述词法 规则、语法规则和抽象语法树结构，易于使用、阅读和维护。 对比l e x 和y a c c ，分析器自动生成工具a n t l r 有如下优点： 1 1a n t l r 采用的l l ( k ) 方法是自顶向下的分析方法，生成的目标程序非常 直观且易于调试； 2 1a n t l r 提供了语法预测和语义预测两种机制来帮助分析，可以在一定 程度上处理上下文相关文法； 3 1a n t l r 提供两种错误报告和恢复机制， 另一种是分析器异常处理机制。 抽象语法树( a s t ，a b s t r a c ts y n t a xt r e e ) 是一 种程序分析的中间表示。文中使用的a s t 是绑定在 控制流图上由a n t l r 的a s t 自动生成机制生成的 信息。该a s t 的树状结构如图2 1 。控制流图上的 遍历分析同时也有对绑定在控制流图上的a s t 信 息的获取和使用。 一种是简单的错误提示机制， 图2 1a n t l r 生成的a s t 结构 8 基于控制流图的指针引用合法性检查 2 1 2 函数依赖分析 设4 、丑均为函数，若在彳的函数体中调用了曰，则称4 依赖于b 。对任意程 序p ，其所有函数的调用依赖关系可以表示为一个有向图。 函数间依赖关系1 2 2 1 取决于两个因素：函数调用形式和调用依赖关系。函数调 用形式是指函数间依赖关系存在的方式，其中c 程序支持函数名调用和函数指针 调用的形式。函数调用依赖关系是在函数调用形式的基础上确定主调函数和被调 函数间的数据依赖关系。函数间调用依赖关系表现为：1 ) 实参与形参的依赖关系； 2 ) 函数的返回值对主调函数上下文的影响；3 ) 全局变量或动态空间对主调函数上 下文的影响；4 ) 函数抛出的异常对程序控制流的影响等。 函数依赖分析的结果是函数的拓扑排序。自下而上分析最基本的原则是被调 用的函数先分析，函数依赖分析的拓扑排序结果是后端跨过程分析和检查的基础， 是自下而上分析得以顺利实现的前提。 2 1 3 契约引擎 契约【2 3 】凹1 分为变量契约和函数契约。变量契约由变量的前置条件和后置条件 组成，针对一条具体的语句，变量的前置条件是指变量在到达当前语句前必须满 足的条件，变量的后置条件是执行当前语句后变量能够满足的条件。 函数契约又分为函数参数契约、函数使用到的全局变量契约和函数的返回值 契约，也就是说，函数契约是一组变量契约，即一组前后置条件的集合。变量契 约的前置条件主要针对函数参数和全局变量，在跨过程检查中使用。 论文中使用的基于记录指针变量状态的检查方法，是契约的一种应用，将指 针变量状态满足的一个条件视为一种契约。针对一条具体的语句，指针变量状态 的前置条件是指到达当前语句前指针变量必须要满足的状态或状态集合；后置条 件是执行当前语句后指针变量能够满足的状态或状态集合。 例如语句“f t e e ( s t r ) ；”，s 打是一个指针变量，则在执行该语句前，s t r 必须满足 的前置条件是指向一段有效的内存空间或为空指针，使用指针变量状态的形式表 示为“p o i n tt och e a p ”或“p o i n tt on u l l ”即指向c 的堆或n u l l 指 针( 具体细节在2 6 节中讨论) ：同样，执行完该语句后，s 仃的变量状态更新为 “p o i n tt of r e e d ”，表明s 仃指向一段被释放的空间，这是s t r 的后置条件。 2 1 4 指针别名分析 当程序中有两个或两个以上的指针指向同一块内存空间时，这些指针关于该 内存空间形成别名关系。此时通过其中的任何一个指针对该内存空间的操作都会 第二章指针引用合法性检查的摹础 9 影响到其它的指针，也就是说互为别名的各指针状态总保持一致。指针变量的合 法性检查，必需考虑指针的别名关系。例如，语句块结束处的指针变量如果未释 放分配的资源但和其他指针变量具有别名关系，则可能不会造成资源泄露。 指针别名关系的建立主要在指针相互赋值时建立。当两个指针不再指向同一 块内存空间时则别名关系解除，这主要包括两种情况：指针被重新赋值和指针指 向的空间被释放。 2 1 5 程序分析的中间表示 程序分析中，抽象语法树作为一个重要的程序中间表示，能够比较直观地表 示出源程序信息，并具有较高的存储效率。但是，a s t 的树状结构无法表示一些 复杂的控制流信息，如跳转语句等。文中选择绑定有a s t 信息的控制流图作为程 序分析的直接中间表示，原因有如下几条： 1 ) 控制流图的通用性和直观的遍历机制； 2 ) 控制流图能够表示任意控制流结构的程序，包括各种跳转语句； 3 ) 部分程序不能或难以转化为成a s t 的形式。 数据流分析是一种重要的程序分析技术，它利用“定值一引用”的方法跟踪程 序中的变量来获取所需的信息。控制流图能够表示任意控制流结构的程序，保证 数据流分析能够覆盖所有分支，它是安全检查具有更高精确度的前提，故论文中 选择控制流图作为程序分析和数据流分析的中间表示。 2 2 控制流图的设计与实现 2 2 1 控制流图 控制流图【2 5 1 ( c f g ，c o n t r o lf l o wg r a p h ) 是程序的一种中间表示形式，它反 映了程序中语句、模块之间的执行顺序和相互调用关系。它的定义如下： 定义2 1 控制流图是一个有向图g = ( 矿，e ) ，陧节点的集合，e 是有向边的集 合。其中节点表示语句，边“寸v 表示从u n r 可能的控制流向。令( “，v ) e 表示控 制流图中的边u 斗v ，并且称是v 的前趋，v 称为”的后继；对于一条具体的语句s ， 它的所有前驱节点组成的集合称为s 的前驱节点集合，记为p r e 仁砂，s 的所有后继节 点组成的集合称为s 的后继节点集合，记为s “c c 御。 c f g 有唯一的入口节点s t a r t 和唯一的出口节点s t o p ，每个节点可以有多个 后继节点。一般的，控制流图上分支节点i f 有两个后继节点，则称连接它两个后继 节点的两条出边分别有属性“t ”( 真) 和“f ”( 假) 。而且，对于c f g 中的任意节点 1 0基于控制流图的指针引用合法性检查 ，一定存在一条从s t a r t n 自勺路径和从 7 至0 s t o p 的路径。 c f g 是流图概念在程序语句级别的一个扩展，程序中每条语句在c f g 中有相应 的节点对应，在c f g 中用语句行号来代表。通常假设一行只有一条语句，在c f g 对应的数据结构中通常为每个语句节点分配唯一的节点号，以便区分一行有多条 语句的情况，c f g 中的边表示程序中语句间的控制流向。 c c + + 程序中语句可分为表达式语句，条件分支语句，循环语句，结构化转移 语句，非结构化转移语句等几大类。本文处理的对象包括简单语句( 包括一般的 表达式语句) ，分支结构的i f 和s w i t c h 语句，循环结构的f o r 和w h i l e 语句，结构 化的跳转语句b r e a k 和c o n t i n u e 以及非结构化的跳转语句g o t o 等，由此能够描述 由上述语句组成程序生成的正确的c f g 。 下面给出程序中各种语句对应的c f g 。对于每种语句给出相应的实例，在实 例中给出了源程序( 位于图的左部) 及其对应的c f g ( 位于图的右部) 。在c f g 中，每个语句节点分别用语句节点对应的行号来表示；边上标记属性“t ”和“f ” 分别表示满足条件的流向和不满足条件的流向，默认情况下为“t ”，不在边上进 行标记；以下表示方法中省略了入口节点和出口节点，书写格式中的语句节点不 区分大小写。 1 、简单语句 简单语句包括一般的表达式语句和函数调用语句等，它的c f g 如图2 2 所示， 形式比较简单，只有一条没有标记属性的边从简单语句的一个节点出发连向下一 个节点。 0 0 1 0 0 2 a = j + a ： 0 0 3b + + 0 0 4， 奉 ( a )( b ) 图2 2 简单语句的控制流图实例 2 、i f 语句 i f 语句是分支结构语句的一种，它的c f g 如图2 3 所示。一般情况下，i f 语句 对应的c f g 会从条件节点引出两条出边，并分别标记属性“t ”和“f ”( 真或假) ， 标记为“t ”的边指向满足条件的第一个语句节点，标记为“f ”的边指向不满足 条件的第一个语句节点；最后i f 语句的满足条件的最后一个语句节点和不满足条件 的最后一个语句节点分别由一条无属性标记的出边指向分支结构的汇合语句节 点。如果分支结构i 储句满足条件的语句节点为空或不满足条件的语句节点为空， 第一二章指针引用合法性检查的基础 则由i 龉句不为空的最后一个语句节点直接引出一条出边到i f 语句的汇合语句节 点。 f 2 0 0 3 0 0 4 0 0 5 ( a )( b ) 图2 3i f 语句的控制流图实例 3 、s w i t c h 语句 s w i t c h 也属于分支结构的语句，如图2 4 所示。从s w i t c h 条件语句节点出发的 边都是无属性标记的。控制流在s w i s h 条件语句选择满足条件的分支进入，如果 没有满足条件的分支，则进入d e f a u l t 分支。s w i t c h 语句所有分支的最后条语句 都引出一条无属性标记的出边到汇合语句节点。 s w i t c h ( i ) c a s e l ： a + + 。 b r e a k ； c a s e 2 ： b + + ： b r e a k ； d e f a u t ； c + + ： b r e a k ； ) c o u t a b c e n d l ： ajldj 图2 4s w i t c h 语句的控制流图实例 4 、w 1 l i k 语句 w h i l e 语句为循环语句的一种，如图2 5 所示。w h i l e 语句对应的c f g 从条件 语句节点处引出两条分别标记有属性“t ”和“f ”的出边，标记“t ”的边指向循 环体中的第一条语句，标记“f ”的出边指向w h i l e 语句结构后的第一条语句，循 环体的最后一条语句由一条无属性标记的出边指向条件语句节点，如果循环体为 空，则由条件语句节点引出一条标记“t ”的边指向条件语句节点自身。 在w h i l e 语句的控制流图中，连接w h i l e 条件语句节点的至少有三条边，一条 是无属性标记沿控制流流入的边，另外两条分别是标记“t ”和“f ”的出边。 0 吖 ； + x x o x x e = ( s + 扦 e x 咖暑!瞄瞄瞄|耋晰她澌m星! 1 2基于控制流图的指针引用台法性检查 0 0 1 w h i l e ( a o ) f 0 0 2a + + 0 0 3 b2a + 1 ： 0 0 4 0 0 5c o u t a b e n d l ； a )lb ， 图2 5d o - w h i l e 语句的控制流图实例 5 、d o w h i l e 语句 d o - w h i l e 语句也是循环语句的一种，它的c f g 与w h i l e 语句的c f g 类似，所 不同的是指向循环体的入边语句节点位置不同，如图2 6 所示。其中，w h i l e 语句 的条件语句节点在整个循环的前端，而d o w h i l e 语句的条件语句节点在循环体的 最后，因此，对同一个算法采用这两种不同的表示方法时，d o - w h i l e 语句会比w h i l e 语句至少多执行一次循环体中的语句。 0 0 1 d o 0 0 2a + + ： 0 0 3b = a + 1 ： 0 0 4 ) w h i l e ( a 0 ) 0 0 5c o u t a b e n d l ； 爹 ( a ，( d ) 图2 6d o - w h i l e 语句的控制流图实例 6 、f o r 语句 f o r 语句的c f o 比其他循环语句的更复杂，如图2 7 所示。控制流首先流向f o r 语句的初始赋值语句节点0 0 2 ，然后进入6 w 语句的条件语句节点0 0 3 ，如果条件 满足，则沿着标记有属性“t ”的出边指向f o r 语句循环体的第一个语句节点；否 则，沿着标记有属性“f ”的出边指向3 r 语句结构的下一个语句节点。对于进入 循环体的控制流，从f o r 语句循环体的最后一个语句节点引出一条无属性标记的出 边指向矗) r 语句改变步长的表达式语句节点0 0 4 ；最后从0 0 4 引出一条无属性标记 的出边指向f o r 语句的条件语句节点。 第二章指针引用合法性检查的基础 0 0 1f o r ( 0 0 2i = o ： 0 0 3i 1 0 ： 0 0 4i + + 、 0 0 5 1 0 0 6a + = i ： 0 0 7l 0 0 8 c o u t a e n d l ； a ，bj 图2 7f o r 语句的控制流图实例 7 、b r e a k 语句 b r e a k 语句是结构化转移语句，它的c f g 如图2 8 所示。b r e a k 语句会将控制 流引向直接嵌套b r e a k 语句的循环体后的第一条语句，即存在一条由b r e a k 语句到 循环后第一个语句节点的无属性标记的控制流出边。 0 0 1 w h i l e ( a 0 ) 0 0 2a + + ： 0 0 3 i f ( b 1 0 0 4 b r e a k ； 0 0 5b = b 一： 0 0 6) 0 0 7 c o u t a b 0 、 ( i5 i + j ： ) f i = 1 0 ； b r e a k ； ) j = i + 1 0 ； 图2 1 l 函数实例及其对应的控制流图 ，胁晶 = “ l 叭 幽 姒 叫耋!螂泓!耋晰m啷啪川呲咐晰m啪啪薹|瞄叫 第二章指针引用合法性检查的基础 2 2 2 控制流图的设计 1 存储结构的选择 c f g 是数据流分析的基础，数据流分析需要对c f g 频繁的遍历以获取足够的 信息，遍历包括正向的遍历和逆向的遍历。c f g 存储结构的选取直接影响后续分 析和检查的效率。从图的常用存储结构如数组，邻接表和十字链表来看，十字链 表占用的存储空间较少，双向遍历也比较方便。 2 c f g 的十字链表存储结构 十字链表( o r t h o g o n a ll i s t ) 是有向图的一种链式存储结构。可以看成是将有 向图的邻接表和逆邻接表结合起来使用的一种链表。在十字链表中，对应于c f g 的每条边是一个节点，对应于c f g 的每个语句节点也是一个节点。这些节点的结 构如图2 1 2 所示： 边节点： i ! ! ! 竺! 竺i ! ! ! ! 竺! ! l ! ! ! 型! ! ! l竺| 二竺! i 竺! ! 坐竺l 语匍臣互匝互回 语句节点：l _ l 二j 二j 2 1 2 十字链表的节点结构 其中，边节点中至少有以下五个域： 尾节点( t a i lv e r t e x ) ：控制流流入的节点或边指向的节点； 头节点( h e a dv e r t e x ) ：控制流流出的节点或引出边的节点； 同头节点链域( h e a dl i n k ) ：具有相同头节点的下一条边； 同尾节点链域( t a i l li n k ) ：具有相同尾节点的下一条边； 边的类型域( e d g e _ t y p e ) ：标记边上属性的类型，这是一个枚举变量，其取值 为“t ”或“f ”等。 语句节点至少有以下三个域： 语句节点信息( i n f o ) ：含有语句基本信息的域，比如语句节点类型、编号和 作用域信息等； 第一条入边( f i r s ti n ) ：以该语句节点为尾节点的第一条入边； 第一条出边( f i r s to u t ) ：以该语句节点为头节点的第一条出边。 另外，可以通过增加边节点或语句节点属性域的方法来保存额外的信息。实 践证明，这种十字链表形式的存储结构，能够完整的保存c f g 的信息，并能支持 方便高效的遍历机制。 2 2 3 控制流图的实现 由前几节的讨论可知，一个程序的c f g 由它的语句节点和边节点组成，它的 1 6 基于控制流图的指针引用合法性检查 类图表示如图2 1 3 所示。 其中，c o n t r o l _ f l o w _ g r a p h 是程序的c f g ，c o n t r o l _ f l o w _ e d g e _ n o d e 代表边 节点，c o n t r o l _ f l o w _ v e r t e xn o d e 是语句节点，它是一个抽象类，其他的类是从语 句节点类继承出的子类，分别对应不用类型的语句节点。另外，绑定在c f g 上的 a s t 信息以成员变量形式定义在c f g 语句节点中。 图2 1 3 控制流图的类图表示 2 3 指针引用方式 c c + + 是当前主流的程序设计语言之一，其指针作为一个记录某块内存起始地 址的变量，它的值是内存块的首地址，由于它具有操作方便、灵活和执行效率高 等优点，在程序中被广泛使用。但是，也正是由于它使用方式的多种多样，导致 不加判断的使用指针会给系统或程序带来较多的安全隐患。如图2 1 4 所示。 i n t m a i n ( ) c h a ra n a y 2 0 ； i n t + p t r 2a r r a y ； p 圩+ = 5 ；t t p t r 的加法算术运算 图2 1 4 指针越界实例 p 扛是一个指向i n t 类型的指针，第5 行p 仃进行了加法的算术运算。在执行第 5 行之前，p t r 指向数组a r r a y 以第0 个元素开始的四个字节，程序执行完第5 行的 第二章指针引用合法性检查的基础 1 7 操作后，p 仃已经指向了数组a r r a y 的合法范围之外的地址，最终导致指针越界。指 针的这种引用方式在语法上是允许的，但在程序执行过程中可能会造成不可预料 的后果或错误。 本文以普通指针，文件指针和结构体指针为主要研究和检查的对象，对在程 序或系统中出现的几类指针造成的安全漏洞进行检查。 2 4 指针非法引用的表现及产生原因分析 c c + + 程序语言中由于没有对指针的指向作限制，指针可能指向无效或非法地 址，如果指向的内容不合法，引用或修改该地址的内容必然会导致程序执行紊乱， 出现不可预料的错误。由于这些错误都是程序执行期间才出现的，并且某些错误 是不可再现的，所以查找和修复这些错误往往比较困难。 从根本上讲，指针非法引用的错误是由于对内存空间的不合法操作或管理不 当引起的，为了使用一种统一的方法对指针非法引用的错误进行分析和检查，本 文在以往工作口3 】幽的基础上，进一步分析指针非法引用的表现，将指针非法引用 的错误分为以下三类：指针的无效引用、释放不合法地址空间和指针引用造成的 资源泄露。其中，指针的无效引用表示指针指向的地址是无效或不确定的。 2 4 1 i 指针的无效引用 指针的无效引用是指引用的指针是无效的，即引用指针的值是无法确定的， 因此，对无效指针的任何引用操作都可能导致错误。 指针的无效引用包括以下几种情况： 1 ) 指针已定义但未初始化：此时指针指向的地址是无效的，直接引用此类 指针的操作必然导致错误； 2 ) 指针指向的空间被释放：指向某一有效空间的指针在程序执行过程被释 放，此时指针指向地址是不确定的，直接引用此类指针的操作可能导致错误。特 殊情况下，在没有其他指针对内存空间操作时，释放该指针指向空间后即刻对该 指针的引用可能不会出现错误； 3 ) 指向局部变量的指针( 或指向的变量超出作用域的指针) ：指针是记录某 块内存起始地址的变量，要使指针有效，则必须确保这块内存有效。由于在每个 语句块中都允许程序员自定义变量，这些变量只在被定义的语句块内有效，当程 序执行到语句块结束语句时，这些变量就会被自动释放。如果在此语句块内将某 个语句块外的指针指向语句块内定义的某个局部变量，则当程序执行到该语句块 结束时，该指针指向的内存会被自动释放，即指针指向的内存块失效，因此，在 基于控制流图的指针引用台法性检查 该语句块外对该指针的引用可能会造成不可预料的错误； 4 ) 空指针即指针的值为n u l l 的指针，对它的任何取值和写入操作必然导 致错误。c 程序鼓励程序员在释放一个指针指向的空间后将该指针置成n u l l 指 针，一方面，对n u l l 指针的取值和写入非法操作的检查方便且易于实现；另一 方面，由于c 对n u l l 指针调用f r e e 函数是允许的，且不会出现潜在的错误，如 此可防止对一个指针变量多次释放资源的错误操作； 5 ) 调用库函数m a l l o e ，r e a l l o c ，e a l l o c 等不成功时返回n u l l ，未判断而引用 该指针可能造成指针引用错误。 无效引用的后果不一定是程序异常终止，程序仍可能正常运行，但运行结果 是不可预料的。无效引用的后果取决于许多因素，例如： 1 ) 指针存储的无效地址在操作系统中指向内存地址( 栈、堆、自由空间、 静态存储区或代码段) 的不同导致系统处理方式的不同； 2 ) 不同编译器的代码生成机制对空指针的定义不同等。 因此无效引用结果往往是无法预知的，这类错误难以手工检查和改正。 图2 1 5 中，第3 行声明了一个指针变量s 仃，当程序执行到第4 行时。s 仃被赋 值为指向一段堆分配的空间。程序执行到第5 行，s 仃指向的空间被释放，此时， s t r 指向的地址变为无效地址，因此第6 行通过s t r e p y 修改该地址的内容就会破坏 内存。程序执行到s t r c p y 时可能不会出错，但由于内存空间可能已经被破坏，在 程序后继的执行过程中可能会出现不可预料的错误。 i n t m a i n 0 c h a r + s i r ； s l r2 ( c h a r ) m a l l o e ( s i z e o f ( c h a r ) + l o ) ； f r e e ( s i r ) ； s i r e p y ( s t r ，”h e l l o ! ”) ；s t r 指向的地址已经无效 图2 ，1 5 引用已释放指针实例 2 4 2 释放不合法地址 “释放内存空问”这一概念必须针对堆内存，而不是静态存储区或栈空间。 由于c c + + 指针自身不能确定自己指向的究竟是哪一类内存，所以c c + + 程序员 可以对任何指针进行释放操作。如果程序员使用库函数释放的内存指针不是指向 一个合法的堆空间首地址，则调用该库函数的释放操作就可能破坏内存中的有关 信怠。一般而言，释放非法内存空间有如下几种表现： 1 ) ，释放栈或静态存储区中的内存空间：栈空间和静态存储区的空闻是由 第二章指针引用合法性检查的基础 1 9 c c + + 运行时自动分配的，如果程序员在代码中释放这些内存空间。就可能改写其 它变量的内存空间，造成不可预料的错误； 2 ) 释放某个无效指针指向的内存空间：由于无效指针指向地址是不