（计算机软件与理论专业论文）cc程序中指针有效性的静态检测.pdf

摘要 本文针对c c + + 程序中使用无效指针引起的安全漏洞做静态检测。首先分析 了漏洞的表现形式和产生原因，构建安全规则。然后在程序分析时，采用语法制 导翻译的方法并结合安全规则实现对指针的静态检测。 文中采用自下而上的分析方法，并结合契约思想，实现了对指针的跨过程检 查。针对控制流分支，提出一种流敏感的分析方法，通过对控制流语句的分析和 路径的跟踪记录，模拟程序的动态执行，给出比较充分的路径遍历方案，可以获 得比较精确的分析结果。本文的检查方法实现在c c + + 静态检查工具x d c h e c k 中，实验证明该方法是有效的。 关键词：指针分析指针无效引用静态检测流敏感跨过程检查 a b s t r a c t s t a t i c a l l yc h e c k i n gt h es a f e t yv u l n e r a b i l i t i e sc a u s e db yu s i n gi n v a l i dp o i n t e r si n c c + + p r o g r a m si ss t u d i e di nt h i sp a p e r b ya n a l y z i n gt h er e p r e s e n t a t i o n sa n dc a u s e s o ft h es a f e t yv u l n e r a b i l i t i e s ，s a f e t yr u l e sw e r ec o n s t r u c t e d ，w i t hw h i c hw ec a nd e t e c t i n v a l i dp o i n t e rr e f e r e n c e su s i n gt h es y n t a x d i r e c t e dt r a n s l a t i o nm e t h o dd u r i n gt h e p r o g r a ma n a l y s i s b a s e do nb o t t o m u da n a l y s i sa n dc o n t r a c tt h e o r y , t h i sp a p e ri m p l e m e n t e dt h e i n t e r - p r o c e d u r a lc h e c ko f t h ep o i n t e rv a l i d i t y f l o w - s e n s i t i v ea n a l y s i sw a su s e dt ot r e a t w i t hc o n d i t i o n a ls t a t e m e n t s ，b ya n a l y z i n gc o n d i t i o n a ls t a t e m e n t sa n dt r a c i n ge x e c u t t o n p a t h st h r o u g ht h es o u r c ec o d ew ec a ns i m u l a t et h ee x e c u t i o no ft h ep r o g r a ma n dg e t p r e c i s ec h e c kr e s u l t t h em e t h o dp r o p o s e d i nt h i sp a p e rw a si m p l e m e n t e di n x d c h e c k ，as t a t i c a l l yc h e c k i n gt o o lf o rc 1 2 4 - bp r o g r a m ，e x p e r i m e n t a lr e s u l t s i l l u s t r a t et h a tt h i sm e m o di se f f e c f i v c k e y w o r d s ：p o i n t e ra n a l y s i s i n v a l i dp o i n t e rr e f e r e n c es t a t i cc h e c k i n g f l o w - s e n s i t i v i t y i n t e r - p r o c e d u r a lc h e c k i n g 创新性声明 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得西安电子科技大学 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究工 作所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文若有不实之处，本人承担一切相关责任。 本人签名塞 圣堑 日期：础! ：墨：12 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其他复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密在年解密后适用本授权书。 本人签名：弛蔓益日期：型! ! ：2 ：12 导师签名日期：们z 2 第一章绪论 第一章绪论 1 1研究背景 本文的研究基于“十五”预研课题“软件安全性故障模式分析”，软件的安全 问题是系统是否稳定的关键因素，软件安全主要分为两大类： ( 1 ) 软件本身由于语言设计的限制导致运行过程中出现不可预期的错误； ( 2 ) 外界针对软件本身的设计缺陷所作的恶意攻击。 本课题针对第一类问题，对c ，c h 程序设计语言在软件开发过程中可能引起 的缺陷进行研究和总结，并研制出一个基于静态分析的软件系统安全检查工具 ( x d c h e c k ) 。该工具可以在软件运行之前发现程序中潜在的错误，从而提高程 序的可靠性，避免不必要的损失。 本文论述的内容为课题中的指针有效性检查模块。c c + + 是当前主流的程序 设计语言之一，其指针由于操作方便、灵活和执行效率高等优点，在程序中被广 泛使用。但由于没有对指针的指向作限制，指针可能指向无效或非法地址，如果 指向的内容不合法，引用或修改该地址的内容必然会导致程序执行紊乱，出现不 可预知的错误。由于这些错误都是程序执行时才出现的，编译时不会检查，并且 有些错误是不可再现的，所以查找和修复这些错误往往比较困难。同时由于程序 中分支结构的存在，程序的一次运行不能覆盖所有的程序分支，有些错误不能通 过程序的运行暴露出来，随着程序规模的扩大，状态空间急剧增大，导致很多安 全隐患在程序测试阶段很难被发现。因此需要辅助的查错工具来检查这些错误， 从而在程序执行前对可能导致错误的语句给出警告，保证程序的安全性，同时方 便程序员修复错误，提高编码质量和效率。 课题中上几届的工作中部分实现了对过程内简单指针的安全检查，没有考虑 跨过程和控制流的影响。 1 2研究现状 静态检查的解决方法包括基于词法分析的安全性扫描f l 】、基于语法和简单语 义分析的安全性检查1 7 】等多种。为了作指针的有效性检查，首先必须对指针进行 分析。n u r i t d a r 总结了指针分析中必需的五种技术0 2 ： ( 1 ) 指针问别名关系的查找技术； ( 2 ) 分析程序控制流结构的流敏感技术； 2 c ，c + + 程序中指针有效性的静态检测 ( 3 ) 分支语句的分析技术； ( 钔指针问关系的分析方法： ( 5 ) 程序中的数据结构的处理方法。 目前存在多种指针分析算法1 1 3 , 1 7 ，它们之间的差异主要在于对影响分析的各 种因素的考虑不同，比如是否考虑控制流信息、是否考虑函数调用环境、对复合 类型数据结构是否作为整体处理等，各种算法均在精度和效率之间做不同的取舍。 w i l l i a mr b u s h 提出的方法【l ，通过静态条件下的路径分析，模拟程序的动态执 行，可以给出比较精确的结果。此方法借鉴了动态分析的思路，避免了别名分析 的弱点。本文对控制流分支的处理方式类似于该方法。 目前存在的指针分析或检查工具有很多，其中使用较多的有l i n t 【2 6 】、s p l i n t l 5 l 等。l i n t 和s p l i n t 是两种功能相近的静态代码检测工具，可以检查出程序中很多 潜在的错误，它们都要求程序员根据需要向程序中加入注释信息才能完成相应的 安全检查，其检错效果与程序中注释的工作量有关，并且这些工具中存在的严重 问题是经常会给出错误的报告1 5 1 ，这些不正确的警告信息会对排错工作产生负面 影响，从而影响了错误检测工作的顺利进行。复旦大学并行处理研究所开发的c 程序分析工具a g a s s i z 系统1 1 1 1 ，对c 程序中的指针作了详细的数据流、控制流 分析以及跨过程分析，但其目的主要是程序的并行优化。 1 3 1 系统功能 1 3x d c h e c k 系统总体概述 x d c h e c k 对c c + + 程序设计语言在软件开发过程中可能引起的缺陷进行安 全检查，检查内容包括：缓冲区边界检查、资源泄漏检查、指针合法性检查、异 常安全检查、与类型转换和控制流相关的安全检查、c + 十类定义的合法性检查、 危险函数检查等，较完整的覆盖了常见的各类漏洞。 x d c h e c k 支持可扩展的安全规则定义。指针有效性检查模块关心的是指针 的指向，而对于库函数，由于无法得到其对应的抽象语法树，因此库函数对指针 指向的影响就无法从静态分析中得知。为此，x d c h e c k 提供外置安全规则功能， 用户只需将关注的库函数对指针指向的影响和要求，按规定的格式添加到配鼹文 件中，即可实现对该函数的安全检查。 x d c h e c k 可以以整个项目为单位执行安全检查。通过读取输入的文件列表， 并依次编译每一个文件获取项目中所有代码的抽象语法树，并在该抽象语法树的 基础上执行安全分析。以项目为单位执行安全检查使得x d c h e c k 可以真币支持 第一章绪论 跨过程安全检查，从而大大提高检查的准确性。 1 3 2 系统框架 x d c h e c k 的程序框架如下图所示。 图1 1x d c h e c k 程序框架结构 如图1 1 所示，x d c h e c k 按功能分为两个部分，即一个前端程序和一个后 端程序。 前端程序负责向程序员提供一个命令行界面，并从程序员提供的命令行输入 中获得项目的源代码文件列表。然后，调用g c c 编译器对给定的源代码文件进 行编译，并获取其中间语法表示结构。最后，将中间语法树文件列表直接提交给 后端。 4 c 妃+ + 程序中指针有效性的静态检测 后端程序负责实际的安全检查，主要分为如下五个模块： ( 1 ) 契约分析模块：该模块负责从配置文件中读取程序的安全模式描述，并根 据该描述构造安全模式的内部表示。 ( 2 ) 符号表提取模块：该模块负责遍历所有的程序中间表示，从中抽取程序中 的各种符号的信息，包括类型系统、和函数记录。同时该模块也负责根据 得到的类型构造变量信息记录生成器，该生成器可以用于在后续的安全检 查过程中构造变量记录节点。 ( 3 ) 函数调用关系分析模块：该模块负责分析并处理整个项目中所有函数的调 用依赖关系，并根据该依赖关系确定后续安全检查过程中各个函数的分析 顺序。 ( 4 ) 主安全检查模块：该模块负责遍历每一个中间语法树，并在遍历过程中执 行安全检查。该模块是x d c h e c k 安全检查功能的主要实现部分，其内 部包含七个子模块，分别对各类程序安全漏洞执行安全检查。 ( 5 ) 错误报告模块：该模块负责接收安全检查器分析过程中得到的错误信息， 并根据程序员制定的格式将错误信息整理为错误报告并输出。 1 4论文的主要工作及论文组织 本论文所做的工作是c c 十+ 静态检测工具x d c h e c k 中的指针有效性检查模 块，本文以课题中上凡届的工作为基础，考虑到n m i t d a r 的五条要求，重新设计 数据结构和算法，主要工作如下： ( 1 ) 通过对指针非法使用的表现进行分析归类，设计了指针有效性检查的安全 规则。 ( 2 ) 设计并实现了指针有效性检查模块的总体框架，并与契约模块相结合，实 现了对指针的跨过程检查。 ( 3 ) 设计数据结构和算法，记录变量的作用域，解决了指针指向的变量超出作 用域问题。采用新的数据结构表示变量信息，将对简单指针的检查扩展到 结构体内指针和多重指针，并有效的处理了指针别名。 ( 4 ) 重点研究了控制流分支对指针状态的影响，提出一种流敏感的分析方法， 通过对控制流语句的分析和路径的跟踪记录，模拟程序的动态执行，给出 比较充分的路径遍历方案，解决了控制流分支引起的指针状态不确定问 题。 ( 5 ) 本文设计的检查方法实现在静态检测工具x d c h e c k 中，通过对大量实 例的分析，验证了该方法的正确性。 论文的组织结构为： 第一章绪论 第一章为绪论部分，主要介绍指针分析的研究背景和国内外的相关研究现状， 分析了各种方法的优点和不足，并介绍了本课题的研究成果x d c h e c k 的系统功 能及系统架构。 第二章为指针非法使用的表现及检查方案，分四部分论述，分别为：指针非 法使用的表现及产生原因分析，变量及变量状态的记录方式，安全检查所需信息 的提取和根据安全规则进行安全检查。 第三章为指针有效性检查的关键技术，分别论述了指针检查中的五个关键问 题和解决方法，五个关键问题为：1 ) 指针指向的变量超出作用域；2 ) 程序分支 弓l 起的指针状态的不确定性：3 ) 共享指针内容引起的依赖问题；4 ) 跨过程的指 针检查；5 ) 结构体内指针和多重指针的处理方法。 第四章为实例分析，通过实例来验证指针有效性检查的正确性。 第五章为结束语。 第二章指针非法使用的表现及检查方案 7 第二章指针非法使用的表现及检查方案 2 1指针非法使用的表现及产生原因分析 内存中供用户使用的存储空间可以分为三部分：程序区、静态存储区和动态 存储区。静态存储空间在程序结束时才会释放，而动态存储空间可以在程序执行 期间释放。动态存储区又可以分为栈和堆。在函数执行时，函数内局部变量的存 储单元都可以在栈上创建，函数执行结束后这些存储单元自动被释放。堆空间是 一块自由存储空问，需要人为申请和释放，其分配方式称为动态内存分配。程序 在运行的时候用m a l l o e 或n e w 申请任意大小的内存，程序员负责用f r e e 或d e l e t e 释放内存。指针的非法使用错误都是由于内存不合法引起的，可分为两类：指针 无效引用和释放不合法地址。指针的有效性即合法性，表示指针指向的地址为有 效地址。 2 1 1 指针无效引用 引用指向无效地址的指针是c ，c + + 程序员易犯的错误，由于此时指针的值无 法确定，因此对指针的任何引用操作必然会导致错误。指针无效引用包括以下几 种情况： ( 1 ) 指针定义时未初始化，这时指针指向的地址无效，若未给它赋有效地址而 直接引用则会出错。 ( 2 ) 指针开始时指向某一有效空间，在程序的执行过程中该空间被释放，这时 指针指向的地址非法。若此后程序继续引用它，则可能导致错误发生。 ( 3 ) 指针指向的变量超出了作用域。在c ，c + + 中每个语句块( ) 中都允许程 序员定义变量，这些变量只在被定义的语句块内有效，当程序执行到语句 块之外时，这些变量就会被自动释放。如果在此语句块内将某个语句块外 的指针指向语句块内定义的某个局部变量，则当程序执行到该语句块结束 对，该指针指向的对象就会自动失效，如果此时引用该指针，程序就会发 生不可预料的错误。 ( 4 ) 空指针即指针的值为n u l l 或零值，对此地址的任何取值和写入操作都 是非法的。 ( 5 ) 当无效指针作为s t r e p y 0 等函数的参数时，可能导致内存被破坏，从而引 起程序执行不正常。 c c + + 程序中指针有效性的静态检测 无效引用的后果不一定是程序异常终止，程序仍可能正常运行。无效引用的 后果取决于许多因素： ( 1 ) 不同类型的硬件体系对不同地址空间的内存施加了何种级别的安全管理： ( 2 ) 指针存储的无效地址在操作系统中指向哪一类内存( 栈、堆、自由空间、 静态存储区或代码段) ； ( 3 ) 不同编译器的代码生成引擎对指针的零值如何定义； ( 4 ) 程序库的不同实现对内存管理采取的机制不同。 因此无效引用结果往往是无法预知的，这类错误难以手工检查和改正。 图2 1 的例子中，第3 行声明了一个指针变量s t r ，当程序执行到第4 行时， s t r 被赋值为指向堆区分配的段空间。程序执行到第5 行，s t r 指向的空间被释放， 此时，s t r 指向的地址变为无效地址，因此第6 行通过s t r c p y 修改该地址的内容就 会破坏内存。程序执行到s t r c p y 时可能不会出错，但由于内存被破坏，在程序后 继的执行过程中就可能出现不可预料的错误。 2 1 2 释放不合法的地址 图2 1 指针无效引用实例 “释放内存”这一概念必须针对堆内存，而不是静态数据区或是栈。由于 c c h 指针自身不能确定自己指向的究竟是哪一类内存，所以c c + + 程序员可以 对任何指针作释放操作。如果程序员使用函数库释放的内存指针不是指向一个合 法堆空间的首地址，则该函数库就可能由于按照自己的释放规则而破坏内存中的 有关信息。释放非法内存的可能情况有如下三种： ( 1 ) 释放栈中或静态存储区中分配的内存空间；栈空间和静态存储空间是由 c c + + 运行时库自动分配的。显然，这些空间中的内存不需要用户手工释 放。如果程序员在代码中手工释放这些内存，就会改写其它部分的内存空 间，从而造成数据的非法访问。 ( 2 ) 释放某个无效指针指向的内存地址；由于无效指向地址是随机的，因此其 合法性无法确知，对其进行释放内存操作产生的后果无法预知。 第二章指针非法使用的表现及检查方案9 ( 3 ) 释放动态分配的内存空间的某个中间地址；在c c + + 的内存分配策略中， 当堆中内存被分配时，返回的总是内存的首地址，因此内存的分配函数总 是根据该首地址确定其对应的内存信息；因此在回收时，内存回收函数也 必须通过首地址才能正确找到对应的内存信息。如果程序员释放的是堆空 间内存块的某个中间地址，则内存释放函数必然无法找到正确的内存信 息，而会将原本不该改写的数据进行修改，进而引发无法预料的错误。 对于上述三个问题，按照检查方法不同，本文完成对前两个问题的检查。 2 2指针有效性检查模块的整体结构 x d c h e c k 通过抽象语法树( a b s t r a c ts y t o xt r e e ，筋矽爿s 获取源程序信 程内检查时得到函数的契约信息，并保存在契约模块，遇到函数调用则从契约模 b 矗 a s t 一节点卜一变量信息e 三j 三j 契约模块l 0c ，c + + 程序中指针有效性的静态检测 ( 3 ) 整数c u r r e n tl e v e l ，表示当前的作用域深度； ( 4 ) 整型数组n u m b e r o f v a r s ，下标为作用域深度，数组值为该作用域内声明 的变量数量： ( 5 ) 死代码标志b e l o w _ b r e a k ，表示当前语句是否为死代码； ( 6 ) 函数调用标志i s _ s i n g l e _ c a l l ，表示函数调用是单独出现还是出现在别的语 句中。 2 3变量及变量状态的记录方式 任何一种指针分析算法首先面对的问题便是指针指向信息表示法的选择，较 常采用的是e ma n li 提出的p o i n t - t o 表示法f 2 6 】，即用三元组( e ，t ，c ) 来表示指针表达 式和它所指向的目标。其中e 为指针类型的表达式，t 为e 所指向的目标表达式， c 的取值可为d 和p ，c 取值为d 时表示e 确定指向t ，c 取值为p 时表示e 可能 指向t 。本文采用的方法类似于上述的p o i n t - t o 表示法，但不是用三元组来表示的， 而是以变量为中心通过变量契约来记录指针指向的信息。 2 3 1 变量信息的存储结构 指针有效性检查模块与系统中的其它模块存在交互关系，为了方便传递数据， 采用了与其它模块一致的数据结构g e n e r i e v a r l n f o 来表示变量信息。由于该数据 结构的属性比较多，下面仅列出本文中用到的属性。 变量信息的数据结构： s t r u c tg e n e r i c v a r l n f o g s t r i n g *n a m e ； 变量名称 g s t r i n g +m a n g l e dn a m e ； 改造后的变量名称 i n t p a r a mi d ；参数编号 g e n e r i c t y p e l n f o t i n f o ； 类型信息 g e n e r i c v a r l n f o + d e r e f _ v i n f o ；指向的变量信息 g s l i s t + f i e l dv i n f ol i s t ； 成员信息链表 s t r u c tc o n t r a c t * c o n t r a c t ； 契约信息 ) ； 其中： n a m e 为变量的实际名称： m a n g l e d _ n a m e 为改造后的变量名称，用以唯一标识变量，避免不同作用域的 第二章指针非法使用的表现及检查方案 变量重名，改造方法为在变量名称后加上文件名和行号，中间以冒号隔开，形如 “v a r ：f i l e c ：2 4 ”： p a r a mi d 用来表示该变量为第几个参数，若不是参数则置为1 ，该属性在跨 过程检查中用到： t i n f o 用来表示变量的类型，本文仅针对指针类型和结构体( 联合体) 类型； d e r e fv i n f o 表示指针指向的变量信息： f i e l d _ v i n f o _ l i s t 为一链表，若变量为结构体类型，则该链表按照结构体成员的 定义顺序，依次记录结构体中每一个数据成员的对应的变量信息： c o n t r a c t 为变量契约，记录指针的状态等信息，变量契约的详细内容将在2 3 3 节中介绍。 2 3 2 指针状态的分类 通过分析2 1 节中指针非法使用的表现形式，可以发现此类问题的共同特点 就是使用指针时指针的状态不合法，因此为了实现安全检查必须跟踪并记录指针 的状态。根据指针指向的地址类型不同将指针的状态分为如下几类： ( 1 ) p o i n tt ok i n i n i t i a l i z e d指针未初始化，指向随机地址 ( 2 ) p o i n tt on u l l指针指向空地址 ( 3 ) p o i n tt oe x c e e ds c o p e指针指向的变量超出作用域 ( 4 ) p o i n tt of r e e d指针指向的空间已被释放 ( 5 ) p o i n tt og l o b a l指针指向全局数据区的变量 ( 6 ) p o i n tt os t a c k 指针指向栈变量 ( 7 ) p o i n tt os t a t i c 指针指向静态变量 ( 8 ) p o i n tt och e a p指针指向c 堆 ( p o i n tt oc p ph e a p指针指向c + + 堆 ( 1 0 ) p o i n tt oa r r a y 指针指向数组 ( 1 1 ) p o i n tt os i n g l e 指针指向单一地址而非连续地址 ( 1 2 ) p o i n tt of u n c t i o n 指针指向函数地址 另外，为了处理某些情况下指针状态无法获得的问题，引入了未知状态 u n k o w ns 耵m i s ，安全检查时总认为该状态是合法的，从而消除由于指针状 态无法获得而引起的误报。 2 3 3 指针状态的契约结构 本文的跨过程检查是通过调用契约模块提供的接口实现的，为了方便与契约 1 2 c ，c + + 程序中指针有效性的静态检测 模块交互，采用了变量契约的数据结构来表示指针的状态，下面先介绍一下变量 契约的概念。 从函数f 的入口开始分析，为使到语句s 前所有对变量v 的操作均安全，v 必须满足的状态集合称为v 在s 处的前置条件；分析完语句s 后v 的状态集合 称为v 在s 处的后置条件。变量v 在语句s 处的前置和后置条件( 简称前后置 条件) 称为v 在s 处的变量契约。 变量契约的后置条件表示指针的状态，契约的前置条件主要针对参数和全局 变量，在跨过程检查中使用。下面介绍契约模块变量契约的数据结构。 s t r u c tc o n t r a c t c o n t r a c t t y p et y p e ； 契约类型 s t r u c tg e n e r i c v a r l n f o * v i n f o ：变量信息 g s l i s t * c o n t r a c ta l i a s1 i s t ；别名链表 i n tn t hp a r a m ； 参数编号 s t r u c tf u n e t i o n l n f o * f i n f o ； 函数信息 g b o o l e a ni s _ c o n t r 0 1f l o ws t a t u s _ d e t e r m i n e d ； 控制流标志 c h a r + p r e _ c o n d i t i o n _ e x p r e s s i o n ； 前置条件表达式 c e t r e e n o d e p r e _ c o n d i t i o n _ e x p r e s s i o nt r e er o o t ；前置条件树 c h a r p o s t _ c o n d i t i o n _ e x p r e s s i o n ； 后置条件表达式 c e t r e e n o d e + p o s t _ c o n d i t i o n _ e x p r e s s i o nt r e er o o t ；后置条件树 ； 其中： t y p e 表示契约的类型，分为全局变量、参数和返回值三种类型： v i n f o 为契约所属的变量信息： e o m r a c t a l i a s l i s t 保存与该变量互为别名的变量契约； n t h _ p a r a m 表示该契约为函数的第几个参数，若不是参数则置为一l ； f i n f o 为契约所在函数的信息； i s _ c o n t r o l _ f l o w _ s t a t u s _ d e t e r m i n e d 表示指针的状态在当前作用域内是否是确 定的，若是则为t r u e ，否则为f a l s e ，用以处理控制流分支引起的指针状态不 确定的问题； p r ec o n d i t i o ne x p r e s s i o n 为指针前置条件的字符串表示； p r e为前置条件的树形存储结构的根；c o n d i t i o n e x p r e s s i o n t r e er o o t p o s t是用字符串表示的指针后置条件即指针的状念集；_condition_expression p o s t为指针状态集的树形存储结构的根。c o n d i t i o ne x p r e s s i o nt r e er o o t 2 4 安全检查所需信息的提取 第二章指针非法使用的表现及检查方案 整个安全分析和检查都是在遍历被分析的源程序的抽象语法树的时候完成 的。抽象语法树是程序的一种中间表示形式，能够包含整个编译单元的完整表示， 比较直观的表现出源程序的语法结构，并具有较高的存储效率。本文使用的a s t 是利用g c c 编译被分析的源程序生成的。 2 4 1 抽象语法树简介 g c c ( g n u c o m p i l e r c o l l e c t i o n ) 是美国自由软件基金会开发且被广泛应用 的编译程序集合的简称。该编译程序集合是一个向上可接收多种语言，向下可支 持多种平台的编译系统。它所接收的语言有c ，c + + ，o b j e c tc + + 和f o r t r a n ， j a v a ，a d a 。g c c 编译系统主要由三部分组成：与语言相关的前端、与语言无 关的后端以及与机器相关的机器描述【1 4 1 。g c c 的前端由与源语言关系密切的语 法分析、语义分析部分组成，它对源程序进行分析后将其转换为抽象语法树。g c c 的后端为编译系统的主体部分，它将抽象语法树转换成后端中间语言r t l ，并在 此中间语言基础上进行各种优化，完成代码生成。机器描述部分则描述g c c 所 运行的宿主机和目标机的操作系统、体系结构、指令系统等有关系统与硬件的情 况，并提供给编译程序的后端使用。这样，采用不同的机器描述，将得到适合于 在不同机器与系统上运行的g c c 版本。 抽象语法树( a b s t r a c ts y t a xt r e e ，筋薪4 s 是程序的一种中间表示形式， 能够比较直观地表示出源程序信息，并具有较高的存储效率；对a s t 遍历和操作 十分方便。因此，它不仅被用于编译的语义分析阶段，而且在程序分析等其他领 域也具有广泛的应用。在a s t 的基础上，可以进行程序优化，生成机器代码：也 可以生成控制流、数据流图，进行程序分析；还可以建立源程序浏览器、智能编 辑器、文本自动生成器和解释器等等。 c c c 的抽象语法树作为一种通用的层次化的中间表示，不仅可以表示各种 语言通用的语法结构，同时也包含表示各种语言特有语法结构的特定类型的树节 点。同c + + 语言中的语法嵌套相对应，各级语法结构对应的抽象语法树也是嵌套 的。 ( 1 ) c c + + 中的函数，在g c c 抽象语法树中对应f u n c t i o nd e c l 类型节点。 ( 2 ) c 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 r u t 对应s w i t c h 语句；e x p rs t m t 对应各种表达式语句等。 ( 3 ) g c c 抽象语法树中表达式类型的树节点对应c c 抖中各种表达式，如： m o d i f y 对应赋值表达式：对应函数调用表达式； 对应数_ 学e x 表p r 达式中加法表达式等c a 。l l _ e x p r p l u se x p r 1 4 c c 什程序中指针有效性的静态检测 ( 4 ) c c + + 中的各种声明在抽象语法树中有相应类型的树节点与之对应，如： e o n s td e e l 与常量声明对应，- c a l d e c l 与变量声明对应，t e m p l a t e 与d e c l 模板声明对应，p a r a m _ d e e l 与参数声明对应，t y p e _ d e c l 与t y p e d e f 声明 相对应等。 ( 5 ) c ，c + + 中的各种类型在抽象语法树中有相应类型的树节点与之对应，如 s t r u e t ，c l a s s 对应r e c o r d _ t y p e ，f u n c t i o n t y p e 和函数的返回类型对应， m e t h o dt y p e 和类中成员函数的返回类型对应等。 ( 6 ) c c h 中的标识符( 变量名，函数名) 在g c c 的抽象语法树中有相应类 型的树节点i d e n t i f i e rn o d e 。各种常量中，i n t e g e rc s t 对应整形常量，等 等。 2 4 2 信息提取过程与方法 指针有效性检查模块针对的漏洞都是由于使用指针时指针的状态不合法引起 的，因此为了实现安全检查首先必须作指针的指向分析，获得指针变量指向的目 标并记录指针的状态。指向分析是作其它更深层次分析的前提，指针的指向有两 种情况：可能指向和肯定指向，本文中采用指针的状态集来描述指针的指向，若 指针的状态集中只有一个状态则该指针的指向为肯定的，若有多个状态则每个状 态皆为可能指向。 在遍历抽象语法树的过程中对于影响指针状态的节点展开分析，提取并记录 节点的属性值。遍历a s t 时，从a s t 的根节点即函数声明节点开始遍历，每个 节点都会被遍历两遍，第二遍遍历在该节点的子节点都被遍历完时进行。 影响指针变量状态的节点主要包括变量声明节点、赋值表达式节点和函数调 用节点。函数调用属于跨过程分析，将在3 4 节中详细论述。下面着重描述变量 声明节点和赋值表达式节点的处理方法。 2 4 2 1 变量声明节点的安全分析算法 源程序中每定义一个变量都会对应于a s t 中的一个变量声明节点即v a rd e c l 节点。此类节点的作用是记录变量的详细信息，它包括名为n a m e 、t y p e 及s i z e 等 属性，其变量名、类型等都可以通过遍历这些子树获得。节点结构如图2 3 。 第二章指针非法使用的表现及检查方案 1 5 p 图2 3 语句i n t + p ；的v a r _ d e c l 节点结构图 下面通过给变量声明节点构造产生式，并添加相应的语义规则来形式化描述 节点属性的获取过程。 属性定义；t y p e 为变量类型；n a m e 为变量名称；s t a t u s 为指针状态。 ( 1 ) v a rd e e l v a r i a b l e ；变量声明 i fv a r _ d e c l t y p e = p o i n t e r _ t y p e 一对指针类型变量处理 t h e nb e g i n v a r i a b l e t y p e - 2p o i m e r _ t y p e ； v a r i a b l e n a m e ：= v a r _ d e c l n a m e ； v a r i a b l e s t a t u s ：2p o i n t t o u n i n i t i a l i z e d ； e n d ； lv a r i a b l e = e x p r e s s i o n ；一声明时初始化 i fv a r _ d e c l t y p e = p o i n t e r _ t y p e t h e nb e g i n v a r i a b l e t y p e ：= p o i n t e r t y p e ； v a r i a b l e a a n l e ：= v a r _ d e c l n a m e ； v a r i a b l e s t a t u s ：= e x p r e s s i o n s t a t u s ； e n d ： ) 遍历a s t 时采用自顶向下深度优先的遍历方式，遇到关注的节点则按相应的 语义规则对节点展开分析并提取属性信息或检查状态的合法性。变量声明时有两 种情况：声明时未初始化和声明时同时初始化。上述产生式针对这两种情况进行 描述，对于指针类型的变量：如果声明时没有初始化则指针状态设为 p o i n t _ t 0 一u n i n i t i a l i z e d ；如果声明时同时初始化，则先分析e x p r e s s i o n ，根 据e x p r e s s i o n 不同的表现形式得到相应的指针状态，然后再将此状态赋给指针信 息变量记录保存。 1 6 c c + + 程序中指针有效性的静态检测 采用语义规则来抽象的描述节点信息的处理过程比较形象、直观，上述的语 义规则中仅对指针变量的状态获取思想作了简单介绍，对于一些相关问题没作描 述。在具体实现中，为变量声明节点绑定节点处理函数e l t o rv a td e c l ，此函数的 主要作用是：获取声明变量的详细信息，包括名称、类型以及结构体的成员信息 等，若变量是指针类型，则同时取得指针状态，并生成该变量信息的契约结构来 保存该状态。最后将生成的变量信息结点添加到当前作用域的变量链表中保存。 c c + + 中，赋值运算符= 的计算顺序是从右向左进行的，所以若存在连续 赋值，则最右边的赋值操作首先被执行，然后将值依次向左传递，例如下面的两 条变量声明语句： c h a r + p ； c h a r + q = p = ( c h a r + ) m a l l o c ( s i z e o f ( c h a r ) 41 0 ) ； 第二条声明语句中存在连续赋值，首先将p 的值赋为空间长度为l o 个字符的 内存地址，然后再将p 的值赋给q 。所以指针变量q 的值是在p 被赋值之后才得 到的，因此为了在分析过程中准确计算出指针q 的状态，必须保证变量q 的 v a r d e c l 节点的子节点“p = ( c h a r + ) m a l l o c ( s i z e o f ( c h a r ) + 1 0 ) ”先被分析，然后根据 指针p 的状态得到q 的状态信息。基于上述原因，变量声硬节点的信息提取过程 在该节点的子节点遍历完后即第二遍遍历时进行，下面给出变量声明节点的安全 分析算法。 算法2 1 ：变量声明节点的安全分析算法 输入：变量声明节点，该节点所在的a s t ，本模块共用的数据结构 输出：获取并记录声明变量的详细信息，生成该变量的契约结构 步骤： ( 1 ) 如果是第一次遍历该节点，在节点遍历开始时，设置函数调用标志位 i ss i n g l e ( 2 ) 如果是第二次遍历该节点，在节点遍历结束后，设置函数调用标志位 i ss i n g l e _ c a l l 为真值； ( 3 ) 如果该语句为程序中的死代码，执行( 1 4 ) ； ( 4 ) 根据当前分支取得当前作用域变量链表c u r r e n tv 醒l i s t ； ( 5 ) 获取变量名称、变量所在文件名称和行号，组合得到变量的 m a n g l e d _ n a m e ，并将m a n g l e d _ n a m e 压入栈v a l i d v a r s t a c k 中： ( 6 ) n u m b e ro fv a r s c u r r e n t _ l e v e l + + ； ( 7 ) 如果变量为指针类型、数组类型或结构体，则创建变量信息结构v i n f o ； ( 8 ) 如果变量为结构体类型并且声明时初始化，则调用结构体赋值算法3 1 3 处理结构体之间的赋值，然后执行( 1 3 ) ； ( 9 ) 如果变量为指针类型或数组类型，则创建变量信息v i n f o 的契约结构 第二章指针非法使用的表现及检查方案 c o n t r a c t ，设置c o n t r a c t 的i sc o n t r o lf l o ws t a t u sd e t e r m i n e d 为t r u e ： ( 1 0 ) 如果变量声明时同时初始化，则调用算法2 2 ，根据表达式e x p r e s s i o n 的 不同表现形式得到指针相应的状态s t a t u s ：如果e x p r e s s i o n 为指针变量，则 建立两变量之间的别名关系； ( 1 1 ) 如果声明时未初始化，则设置s t a t u s 为p o i n tt ou n i n i t i a l i z e d ； 0 2 ) 根据s t a t u s 设置c o n t r a c t 中记录的交量状态； ( 1 3 ) 将v i n f o 加入到当前作用域变量链表c u r r e n tv a tl i s t 中保存； 0 4 ) 结束。 对于指向连续空间地址的指针变量，仅记录指针指向首地址时的状态，若指 囱酋地址外的地址则等同于指向首地址时的状态，如p 十+ 的状态等同于p 的状态， 如果出现指针越界的情况，则由缓冲区静态检查模块负责检查。上文中提到影响 指针变量状态的表达式表现形式很多，因此指针状态的获取方式也相应的有所不 同，下面给出根据表达式计算指针状态的算法描述。 算法2 。2 ：根据表达式计算指针状态 输入：表达式节点e x p r ，该节点所在的 ，本模块共用的数据结构_ s t m t a s t 输出：该表达式对应的指针状态或指针状态集 方法： b e g i n s w i t c h 表达式节点类型b e g i n c a s e 变量声明节点v a r _ d e c l ： c a s e 参数声明节点p a r md e c l ： 取得变量或参数的名称v a l - n a m e ； 从控制流链表中查找到v a rn a m e 对应的变量信息v i n f o ； r e t u r nv i n f o c o n t r a c t 中的指针状态： c a s e 问号表达式e o n d _ _ e x p r ： 分别取得问号表达式真假情况下对应的指针状态； r e t u r n 真假情况下对应的指针状态的并集； c a s e 自增表达式i n c r e m e n t