（计算机软件与理论专业论文）cc程序安全检查工具前端的设计与实现.pdf

摘要 本文在分析c ，c + + 程序安全检查工具框架的基础上，根据安全检查的特殊需 求，给出了一种基于分析器自动生成工具a n l r i 瓜构造c c + + 安全检查工具前端的 方法，并将此方法应用于实际开发过程中。使用此方法构造的前端通过分析软件 源代码为后端安全检查提供符号信息、抽象语法树和控制流图。 本文使用a n t l r 生成词法分析器、语法分析器、抽象语法树及其遍历框架， 重点讨论了符号表的设计与实现、抽象语法树的设计与实现和控制流图的生成。 实践表明，该前端能够满足工具安全检查的需要。 关键词：安全检查符号表抽象语法树控制流图a n t l r a b s t r a c t a c c o r d i n gt 0t h es p e c i f i cr e q u i r e m e f i t sf 研m es a 角t yc h e c k ，am e t h o db a s e do na p 盯s e rg e n 锄t o r ，a n r l r 氨叫c o n s t n j c t i n gn 坞硒i l t e n do fac c + + p r o g 舢s a f e t y c h e c k e ri sp r o p o s e da n di m p l e m e n t e di nt l l i sp a p e lt h e 丘o m - e n dp r o v i d e ss y m b o l i i l f o 皿a t i o i l ，a b s 仃a c ts y n t a xt 佗ea i l dc o n t r o ln o w 伊a p hf o rt l l eb a c k - e n do ft h es a f b t y c h e c k e rb ya l l a l y z i l l gt h es o u r c ec o d eo f m ep r o j e c t a n t l ri su t i l i z e dt oc o i l s 协l c tl e x e r ，p a r s e f ，a b s 仃a c ts y n t a x 订e e 柚d 仃e ep a r s e r a l s o ，m ed e s i 弘a n di n l p l e m e n 倒o no ft h es y m b o l 协b l c ，a b s 仃a c ts y n t a xt r e ea n dt h e c o 璐t m c t i o no f c o n 仃o lf l o wg m p ha r ed e t a i l e d l yd i s c l l s s e di l lt h ep a p e r ini sp r o v e dm 砒 t h e 丘o n t e n dc 蛆s a t i s 毋t h er e q u i r c m e n t sf o rt h es a f b t yc h e c k e r k e y w o r d s ：s a f b t yc h e c ks y m b o lt 曲l e a b s t r a c ts y n t a x1 t 钾 c o n t m lf i o wg r a p ha r l r 学位论文创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：莹熊盎2日期z 盟z ：! ：z 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名： 导师签名： 嘧使勃 圳哆 日期2 0 p 7 ，7 醐争 第一章绪论 第一章绪论 1 1 研究背景 c c + + 语言从产生至今已近三十年，在不同领域的软件开发中得到了广泛应 用。但在提供灵活控制能力的同时也带来了一些潜在的安全性问题，例如缓冲区 溢出、资源泄露和指针非法引用掣1 l 【2 l ，这些安全问题严重影响了软件的可靠性和 稳定性。 针对c ，c + + 程序的安全问题，国内外对c c + + 安全检查的研究已有相当长的 历史，同时出现了多种程序安全检查方法，如代码验证( c o d ev a l i d a t i o n ) 、模型 检查( m o d e lc h e c k i n g ) 和进化测试( e v o i u t i o 豫r yt e s t i n g ) 等。但目前广泛应用 于项目开发中的主要有两种方法：静态检查和动态检查。静态检查通过扫描源程 序，在词法分析、语法分析和语义分析过程中找出能够导致程序错误的结构异常、 控制流异常及数据流异常；而在动态检查过程中，需要设计一组或多组测试数据， 并实际运行被测程序，检查不按预定要求终结的循环、不该执行而实际执行的语 句及该执行而未执行的语句等程序错误，由于动态检查需运行被测程序，因此检 查精度较高，但由于设计的测试数据很难覆盖程序的所有运行情况，导致某些漏 洞无法被检测出来。目前提出了一种静态检查和动态检查相结合的方法【3 l 来进行程 序的安全检查，此方法还仅处于研究阶段。 目前用于c ，c 抖程序安全检查的工具已经很多，且大多数已经被广泛使用， 其中具有代表性有； ( 1 ) l i n t 【4 】及后继产品s p l i n t 【5 】和p c i i n t 6 】 l i m 及其后继产品都采用程序员手工添加注释的方法进行静态安全检查。其中 1 m 和s p l i n t 为开源的项目，只关注于c 语言的安全检查。而p c i i n t 为商业产品， 增加了对c 抖的安全检查。 ( 2 ) p i 汪f i x 及p r e f h s t l 7 1 p r e f l x 是一个自动化的静态安全检查工具，不需要程序员的手工干预。它采 用前置条件和后置条件的概念定义安全条件，并使用该条件进行安全检查。p i 也f a s t 为p r e f i x 的后继产品，其在p r e f i x 的基础上提高了检查效率，可用性更好。p r e f i x 和p r e f 弧t 都专注于提高检查精确度。 ( 3 ) v a l 鲥n d i s 】 v a i g r i i l d 是一个开源的程序检查工具，可以检查程序中的内存泄漏和无效内存 访问等漏洞。该工具为一个动态检查工具，通过运行被测程序检测程序中的漏洞。 2 c ，c + + 程序安全检查工具前端的设计与实现 ( 4 ) c o v e r i t y 【9 1 c o v e r i t y 是一个针对c 语言的静态检查工具，最初来自在元编译和模型检查等 领域的工作。该工具已经被应用于l i n u x 内核源代码安全性分析。 ( 5 ) c c u r c d 【1 0 】 c c u r c d 采用扩展的c 语言类型系统，允许用户为类型添加限定信息，按照制 订的一系列推导规则进行推导，检查内存泄漏、内存非法地址访问等错误，并以 动态检查为辅助方法来提高检查的精度。 本文来源于一个实际科研项目。此项目的目标是针对c ，c 什程序设计语言在 软件开发过程中可能引起的安全问题，研制一个基于静态分析的c c + + 软件系统 安全检查工具。 1 2c c + + 程序安全检查工具概述 c c + + 程序安全检查工具的目标是利用静态分析技术，检查c c + + 程序中的安 全漏洞。该工具支持以完整的软件源代码为单位的安全检查和可扩展的安全规则， 通过基于控制流和契约机制1 的数据流分析提高检查精度。 工具整体框架如图1 1 所示。 源代码( 源代码列表) 图1 1d c h 程序安全检查工具整体框架 第一章绪论 工具分为前端和后端两个部分。前端通过对软件源代码进行分析，为后端提 供分析需要的符号信息、抽象语法树和控制流信息。前端主要包括3 个部分： ( 1 ) 语法分析：通过对源程序进行语法分析收集程序的符号信息，包括类型信 息、变量信息和函数信息，同时生成以函数为单位的抽象语法树； ( 2 ) 配置管理：负责对工具中的参数进行配置，例如符号表相关的参数，此参 数可根据被分析项目的规模来设定；基本类型相关的参数，根据具体平台 设置基本类型所占的字节数等； ( 3 ) 控制流图生成：通过遍历抽象语法树生成携带抽象语法树信息的控制流 图，为后端分析提供必要的信息。 后端在前端提供的信息基础上，基于控制流和契约机制，通过自底向上的数 据流分析进行程序安全检查。后端分为5 部分： ( 1 ) 函数依赖分析：通过基于控制流图的函数指针数据流分析获取精确的函数 调用依赖关系。根据此依赖关系产生函数调用的拓扑序列，以此确定后续 对函数进行安全检查的次序； ( 2 ) 指针别名分析：基于控制流图和函数调用拓扑序列，采用白顶向下的方法 进行指针别名分析，保存的指针别名信息供后续的安全检查使用； ( 3 ) 契约配置管理和契约引擎的设计和实现：制定安全检查所需规则，设计和 实现安全检查模式所需的存储结构，为后续安全检查提供必要的信息； ( 4 ) 指针引用的有效性与资源泄露检查：基于控制流图和契约机制，采用自底 向上的方法进行数据流分析，对指针引用的有效性和资源泄漏进行检查； ( 5 ) 错误报告管理：负责对安全分析的结果进行收集和整理，支持多种错误信 息输出模式。 1 3 本文工作及内容组织 在c c 抖程序安全检查工具的开发过程中，本文负责的主要工作是设计和实 现工具的前端部分。本文给出了一种基于分析器自动生成工具a n t l r 【1 2 】构造 c c + + 程序安全检查工具前端的方法，使前端具有很好的可靠性和可扩充性，且为 后端提供足够的信息进行安全检查。本文的主要工作包括： ( 1 ) 符号表系统的设计与实现； ( 2 ) 抽象语法树的设计与实现； ( 3 ) 通过语法分析构造程序的符号表和抽象语法树； ( 4 ) 通过遍历抽象语法树构造程序的控制流图。 论文内容组织如下： 第一章分析了c ，c + + 安全检查的研究现状，并介绍了c ，c + + 程序安全检查工 4 c ，c + + 程序安全检查工具前端的设计与实现 具。 第二章介绍了分析器自动生成工具a n t l r ，并说明了如何使用a n t l r 构造 c c 抖程序安全检查工具前端。 第三章给出了c c + + 程序安全检查工具前端的整体结构，并详细介绍了符号 表的设计与实现、抽象语法树的设计与实现和控制流图的生成。 第四章分析了c c + + 程序安全检查工具前端设计和实现中的主要困难，并给 出了解决方案。 第五章给出一个具体的实例来说明c c + + 程序安全检查工具前端处理后的符 号表、抽象语法树和控制流图，并验证了其正确性。 第二章a n t l r 与c ，c + + 程序安全检查工具前端 第二章a n t l r 与c c + + 程序安全检查工具前端 c c 抖程序安全检查工具前端( 下文简称“前端”) 通过对c c 抖源程序进行 分析为后端提供检查需要的符号信息、抽象语法树和控制流信息等。前端首先由 词法分析器逐一读入源程序的字符，组成一个个的记号，如标识符、数、运算符 和类型等；然后，语法分析器读入由词法分析器输出的记号流，在语法分析的过 程中构建符号表和生成抽象语法树；最后通过遍历抽象语法树生成程序的控制流 图。因此词法分析器构造、语法分析器构造、抽象语法树的生成和抽象语法树的 遍历是前端构造中的几个重要部分。本文使用分析器自动生成工具a n 兀r 生成词 法分析器、语法分析器、抽象语法树和抽象语法树遍历框架，因此a n t l r 是前端 构造的基础。 2 1 分析器自动生成工具a n t l r 由于词法分析器构造相对简单，下面将重点对语法分析器和分析器自动生成 工具a n t l r 进行介绍。 2 ，l ，l 语法分析器 语法分析器分析语法结构的基本方法可分为自顶向下和自底向上两种i l ”，这 两种方法仅能处理文法的子集，如l l 文法和l f r 文法，但这两种文法足以描述程 序设计语言的大部分语法结构。自顶向下的分析方法用于分析l l 文法描述的语 言，自底向上的分析方法用于分析l r 文法描述的语言，因此自顶向下的分析也称 为l l 分析，自底向上的分析也称为l r 分析。 l l 分析为输入字符串寻找最左推导l l ”，即从文法的开始符号开始，自顶向下、 从左到右为输入字符串建立一棵分析树。l l 分析一次仅匹配一个产生式，即每遇 到一个输入记号就必须立刻决策使用哪个产生式进行匹配。若文法中存在左递归， 则l l 分析会进入无限循环，因此使用l l 分析时，要求消除文法中的左递归。 l r 分析采用归约的方法，从叶子到根构造分析树。u t 分析的一个状态表示 当前可以匹配的产生式集合，l r 分析并不立刻决定采用哪个产生式进行匹配，直 到完全匹配了某个产生式的右部才做出决策。 语法分析器与词法分析器进行交互识别语言的语法结构，并在识别语法结构 的过程中生成语言的中间表示及执行用户的语义动作，因此语法分析要求在文法 6 c ，c + + 程序安全检查工具前端的设计与实现 中嵌入语义动作。若在语法分析过程中遇到嵌入语义动作，该语义动作必须立刻 被执行，因此在文法中嵌入语义动作的位置可能会影响分析器的分析能力，甚至 可能引入大量的冲突，例如下面的类型定义和变量声明代码实例： 0 1 t y p e d e f i mm y t y p e ； 0 2 m y t y p en a g ； 其对应的文法如下： t y p e d e f _ s 协t ：r 忡e d e fd e c l a r a t i o n a d d 咖e n a m e ； ， v a r d e - s t a t：d e c l a n i o n a d dv 黜锄e ； ， 为了正确进行语法分析，当分析第1 行语句时，必须立即将m y l e 的信息填 入符号表。在第2 行遇到m y t y p e 时。就可以确定m y t y 弦是类型名丽不是标识榜， 通常在词法分析过程中通过访问符号表获取该记号的类别信息，如 t o k e n t y p e 、t o k e 卜l v a r 或t o k e m f u n c 。若仅向前看一个符号，为了使 分析器能正确地将m y t y p e 识别为类型名，语义动作“a d dt y p e n 锄e ”必须在匹配 类型定义产生式t y p e d e s 协t 中的；之前执行，如果语义动作在匹配；之后 执行，语法分析器向前看到的符号为标识符而不是类型名，导致语法分析失败。 为了避免回溯，l l ( 1 ) 分析要求文法中不存在左递归和左因子【1 5 】，需改写文法 消除左递归和提取左因子，从而产生难于理解、非自然的文法。向前看多个符号 的l l 分析增强了语法分析器的能力。在一定程度上避免了提取左因子，保持了文 法的自然性。l l 分析一次仅能匹配一个产生式，即每遇到一个输入记号就必须立 刻决策使用哪个产生式进彳亍匹配，因此l l ( k ) 文法中语义动作的位置不会影响l l 分析的能力。 l r 分析器的每一个分析状态表示可匹配的产生式集合，分析器并不立刻决定 采用哪个产生式进行匹配，直到完全匹配了某个产生式的右部。若l r ( k ) 文法中存 在嵌入语义动作，则该语义动作必须立刻被执行，即必须立刻决定使用哪个产生 式进行匹配，将会降低l r 分析的分析能力。若采用相同的k ，在最坏情况下l r o ( ) 的分析能力将与l l ( k ) 的分析能力等同。 目前广泛使用的语法分析器构造方法有两种二手工构造和使用工具自动生成。 由于l l 分析为自顶向下分析，相对比较简单，所以易于手工构造。相反，l r 分 析为自底向上分析，是一种逆向的过程，对于规模较大的语言，很难用手工的方 式构造，一般需借助语法分析器生成工具自动生成。采用语法分析器自动生成工 具构造语法分析器，程序员无需关注分析器的具体实现细节，只需用文法描述语 言的语法规则，并且添加相应语义动作，而不需要将时间和人力浪费在编写分析 器的实现代码上。 第二章a n t l r 与c ，c + + 程序安全检查工具前端 7 随着语法分析器自动生成技术的发展，已出现了很多的语法分析器自动生成 工具，其中具有代表性的有： ( 1 ) y a c c b i s o n 【1 6 j y a c c ( y e t a n o t l l e rc o m p i l e r - c o m p i l e r ) 是一个l a l r ( 1 ) 分析器自动生成工具， 是贝尔实验室在u n i x 上首次实现的，而且与词法分析器自动生成工具l e x 有直 接的接口。q 叮u 【1 7 】工程推出b i s o n ，是对y a c c 的扩充，同时和y a c c 兼容。y a c c 已经被广泛用来实现编译器，例如g c c 【】。 ( 2 ) c u p 【1 9 】 c u p ( j a v ab a s e dc o n s n l l c t o ro fu s e f u lp a r s e r s ) 是美国普林斯顿大学在1 9 9 6 开发的一种语法分析器自动生成工具，是用j a v a 实现的y a c c 。c u p 采用l a l r ( 1 ) 分析方法和j a v a 目标语言，与几e x 【2 0 1 是配套使用。 ( 3 ) a c c e n t 【2 1 1 a c c e n t ( a c o m p i l e rc o m p i l e rf o r t h ee n t i r ec l 勰so f c o m e x t f r e el a l l g u a g e s ) 是在l i n u x 上开发的共享软件，也是一个语法分析器自动生成工具。a c c e n t 生 成的分析器使用e 盯l e y f 2 2 1 算法，通过一个能动态生成状态集合的驱动程序进行语 法分析。因此a c c e n t 对输入的文法没有任何限制，能够支持上下文无关文法的 全集，但产生的语法分析器效率较低。 除了上述的工具外，还存在其它的自动生成工具，如a n t l r 、j a v a c c 【2 3 1 和 s a b l e c c l 2 4 1 等。在c c + + 程序安全检查工具前端构造中，使用a n t l r 来自动生成 词法分析器、语法分析器和抽象语法树遍历框架，下面将对其进行详细介绍。 2 1 2 分析器自动生成工具a n 瓜的特点 a n n ，r ( a n o t l l e rt o o lf o rl 柏g i l a g er e c o g i l i t i o n ) 是由s 锄f r a n c i s c o 大学 t e r e n c ep a r r 等人开发的一种分析器自动生成工具，它同时集成了词法分析器生成、 语法分析器生成、抽象语法树生成和抽象语法树遍历框架生成功能，且能够支持 j a v a 、c + + 和c # 等多种目标语言。a n t l r 是一个免费、开放源代码的工具，已 经在研究领域和商业领域得到了广泛地使用，它具有以下显著特征： ( 1 ) l l ( k ) 分析 a n t l r 生成l l ( k ) 的递归下降分析器。向前看符号的个数k 没有限制，程序 员可以根据文法的需要设定k 的最大值。在分析器中不是采用固定的k 值，而是 根据分析决策的需要动态调整k 的大小，从而提高了生成分析器的效率。在l l 分 析中，若文法中存在左递归，则l l 分析会进入无限循环，因此a n l l r 要求消除 文法中的左递归。 ( 2 ) 语法预测和语义预测1 2 5 】 c ，c + + 程序安全检查工具前端的设计与实现 a n t l r 提供语法预测和语义预测两种预测机制，它们用来处理复杂的语言结 构，如需向前看任意多个符号的语法结构或上下文相关的语法结构。 语法预测通过对语法结构进行预测来决策采用哪一个产生式进行匹配。进行 预测的语法结构的符号个数没有限制，而l l ( k ) 的预测中最多只能向前看k 个符号。 因此语法预测是对l l ( k ) 分析的一个补充，使其对某些语法结构可以向前看更多的 符号。例如下面的表达式语句和声明语句( 其中t 表示一个类型) ： t ( + a ) m = 7 ；赋值表达式 t ( + a ) ( i n t ) ； ，函数指针声明 区分这两个表达式需要向前看的符号个数是无法确定的，直到遇到记号“”， 才可以确定是表达式语句。a n t l r 采用语法预测来解决此问题，设计如下的产生 式： s t a t ：( d e c l a r a t i o n ) = - d e c l a r a t i o n e x p r e s s i o n 在第一个候选项中，“( d e c l a r a t i o n p ”表示预测到语法结构d e c l a r a t i o n 时，产 生式d e c i a r a t i o n 才会被匹配，否则匹配e x p r e s s i o n 。 语义预测通过运行时的语义信息来进行预测，例如根据符号表的信息来识别 上下文相关结构，包含两类：消除二义性语义预测和有效性语义预测。消除二义 性语义预测通过语义信息来消除文法的二义性，例如下面的函数调用和类型转换 表达式产生式： e x p r ： i s l e ( l ，t ( 1 ) ) ) ? i dl p 甜通ne x p rr p a r e n ，类型转换表达式 i i s f u n c ( l 1 ( 1 ”) ? i dl 脏ne x p rr p a r e n ，函数调用表达式 ； i s 聊e ( l 1 y 1 ) ) 和i s f u n c ( u ( 1 ) ) 是用户自定义的函数，根据符号表中的信息判断 向前看的第一个标识符是类型还是函数。消除二义性语义预测的语法为“f 条件表 达式 ? ”，且必须出现在产生式的最左边。若向前看的第一个符号为类型名，则采 用第一个产生式进行匹配；若为函数名，则采用第二个产生式匹配；否则，分析 失败。通过有效性语义预测来判断语义的有效性，其语法和消除二义性语义预测 的语法耜同，但可以出现在产生式的任何位置，例如下面的产生式： t y p e n 踟e ： i s t y p e n 锄e ( l t ( 1 ) ) ) ? d 其中，i s l 卯e n 锄e ( l t ( i ) ) 为用户自定义的函数，判断向前看的第一个符号是否 为类型名。当匹配咖e n 锄e 时，检查i d 是否为有效的类型名，若不是则报告错 误信息。 ( 3 ) 支持词法、语法和抽象语法树统一描述 a n t l r 支持三种分析对象：字符流、记号流和二叉树结构，可利用它生成词 第二章a n t l r 与c ，c + + 程序安全检查工具前端 9 法分析器、语法分析器和抽象语法树遍历框架。a n n r 可以根据用户添加的标记 自动生成抽象语法树，使用户从抽象语法树的具体生成过程中解脱出来，且生成 的抽象语法树易于修改，可扩充性好。 a n n ，r 采用e b n f ( e x t e n d e db a c k i l s _ n a u rf o m ) 统一描述词法规则、语法 规则和抽象语法树结构，且可以在同一文件中描述，易于阅读和维护。 使用a n t l r 实现一个简单的计算器( 完整实现参见附录a ) ，此计算器对屏 幕上输入的算术表达式求值，并将计算结果输出到屏幕上。此计算器的词法分析 器扫描源程序，识别出输入表达式中的记号：乘法运算符( s 髓r ) 、加法运算符 ( p l u s ) 、分号( s e m i ) 和整数( i n t ) 。词法规则采用a n r l r 文法描述如下( 其 中终结符首字母为大写字母) ： s t a r ：。+ ： p l u s ：t + ： s e m i ： ； d i g i t ：o 。9 ： i n t： ( d i g i t ) + ； 计算器的语法分析器以词法部分识别出的记号为输入，识别表达式的语法结 构，构造表达式的抽象语法树。语法规则采用a n l l 瓜文法描述如下( 其中首字母 大写的为终结符，首字母小写的为非终结符) ； e x p r ：m e x p r ( p l u s m e x p r ) s e m i ! ； m e x p r ：a _ t o m ( s t a r a t o m ) ； a t o m ：i n t ： 文法中的“! ”和“，、”为用户添加的生成抽象语法树的标记，“! ”表示前面的 终结符和非终结符对应的抽象语法树不作为新构造的抽象语法树的一部分；“，、” 表示前面的终结符对应的抽象语法树节点为当前构造的抽象语法树的根节点；未 加标记表示此符号对应的抽象语法树为当前构造的抽象语法树的孩子。 计算器对表达式求值的过程就是对抽象语法树后序遍历的过程，表达式抽象 语法树遍历的文法描述如下： e x p rr e t i l n l s 【n o a tr 】r 为产生式e x p r 对应函数的返回值 n o a ta ，b ；，定义函数局部变量 r = o ：初始化返回值 ) ： 撑( p l u sa = e x p rb = e x p r ) r = a + b ；) 计算加法表达式的值 i# ( s t a ra = e x p rb = e x p r ) r = a b ；) ，计算乘法表达式的值 l i ：i n t r = a t o f ( i - g e r r e x t o c _ s n o ) ； 获取整数 c c + + 程序安全检查工具前端的设计与实现 加法表达式和乘法表达式的抽象语法树结构采用广义表描述，形式为“撑( r o o t c l l i l d lc h i l d 2 ) ”，其中r o o t 为树的根节点；c h i l d l 和c l l i l d 2 为根r o o t 的第一个孩子 和第二个孩子。 ( 4 ) 错误处理机制 a n t l r 提供了两种错误报告和恢复机制，一种为简单、有效启发式的错误报 告机制，此机制可以满足大部分应用的需要。对于一些特殊的应用，需要更完善 的错误报告和恢复机制，为此a n t l r 提供了一种可扩充的错误报告和错误恢复框 架。 2 2 使用a n t l r 设计前端 2 2 1c c + + 程序安全检查工具前端 c c + + 程序安全检查工具前端的功能和c c + + 编译器前端的功能相似，通过语 法分析从源程序构造符号表和抽象语法树，然后在抽象语法树的基础上构造程序 的控制流图。 目前存在的c c + + 编译器，如g c c ，通过设置选项可以输出其中间表示 ( i n t e m e d i a t er e p r e s e n t a t i o n ) ，安全检查工具可以从中间表示中获取待检查代码的 有关程序信息，无需自己构造前端来进行安全检查f 2 6 】。c ，c + + 程序安全检查工具采 用独立的前端，而不是在g c c 编译器中间表示的基础上进行安全检查，主要有以 下几方面的原因： ( 1 ) 若c c + + 程序安全检查工具依赖于具体的编译器，会使系统依赖于具体的 平台环境，从而降低了系统可移植性； ( 2 ) g c c 的版本在不断更新，g c c 并不保证不同版本的中间表示保持兼容， 从而导致系统的可用性降低； ( 3 ) g c c 生成的中间表示针对的用户并不是普通用户，而是针对内部人员的使 用，例如调试人员等。因此中间表示可能会包含一些安全检查并不关心的 信息，而且有时可能会丢失一些安全检查需要的重要信息，严重影响了检 查质量。 c c + + 程序安全检查工具的前端提高了系统的可移植性和可扩充性，例如可以 通过前端获取源程序中函数的前置和后置条件，有利于同时使用多种不同的分析 方法，从而提高检查质量。 第二章a n t l r 与c ，c + 十程序安全检查工具前端 2 2 2a n t l r 在构造前端中的作用 本文使用分析器自动生成工具a n t l r 构造前端，构造方式如图2 1 所示。 词法规则描述- r 一一，词法分析器 抽象语妻麓笔纂= 习! 竺_ j ； c l a s s l 卯e i n f o r 的五个数据成员全部实现为列表，其中元素顺序和定义顺序一 致。 ( 1 ) f i e l d l i s t 用来记录数据成员列表。其中每一个元素为f i e l d i n f o r 结构。 f i e l d i n f o r 被用来表示类、结构体或联合体的数据成员信息。在定义函数 类型时，f i e l d i n f o r 结构也被用来表示函数类型的形式参数信息，其定义 信息如下： c l 嬲sf i e l d i n f o r ：p u b l i cd e c l a r a t o r s y m b o l p u b l i c ： 吼s i g n e d i n t i d ；编号 c h a r + n 锄e ：，名称 第三章c 妃+ + 程序安全检查工具前端的设计与实现 2 l b a s e l e i n f o t i i l f b f ； ，类型 i n t p r o p e r 哆；，其它标记，如默认为l ，可变长参数为- 2 p u b l i c ： 其它操作接口 ) ： ( 2 ) b a s e l i s t 用来记录基类列表。列表中的每个元素为指向b 嬲e t y p e i n f o r 的指 针，对应当前类型的一个基类类型。该列表中各个指针的顺序和该类型的 各个基类声明次序相同。 ( 3 ) v i m l a l l i s t 用来表示该类定义中各个基类是否为虚拟继承。每个元素的值 为布尔类型，若取真表示为虚拟继承，否则不是。元素顺序和b 船e l i s t 中 的元素顺序一致。 ( 4 ) d e r i v e d l i s t 用来记录该类的派生类列表。每个元素指向该类的一个派生类。 ( 5 ) m e t h o d l i s t 用来记录该类的成员函数列表。每个元素为指向一个成员函数 f u i l c t i o n 聊e i n f o r 的指针。 3 2 3 3 枚举类型信息的存储 枚举类型用关键字e n 啪，加上一个枚举类型名来定义，类型名后面跟一个花 括号括起来的枚举成员列表，枚举成员之间使用逗号分开。在默认情况下，第一 个枚举成员被赋以值o ，后面的每个枚举成员依次前面的加1 。用户也可以显式地 把一个值赋给一个枚举成员，而且此值不必是唯一的。 枚举类型采用结构e n 啪聊e i n f o r 存储，其中使用列表存储枚举类型成员的信 息，列表每个元素为e n 啪i t e m 。e n 眦n e m 包括成员名称和其对应的整数值，通 过e n 啪i t e m 可以访问对应e n 啪1 卯e i n f o r 信息。e n 啪i t e m 和e n u m t y p e i n f o r 结 构信息如下： c l 硒se n 岫i t e m ：p u b l i cb a s e t y p e i n f o r ，p u b l i cd e c l a r a t o r s y m b o l p r i v a t c ： e n 砌t y p e i n f o r + o 、n e r ；j 或员所属的e n i l i l l 卯e i n f o r 结构 i n tv a l u c ： 成员对应的整型编号 p u b l i c ：其它操作接口 ) ； c l 船se n 啪1 卸e i n f o r ：p u b l i cb 觞e 1 ) e i n f o r p 哦r a t e ： e n 啪i t e m “s te n u m i t e m l i 咄，成员列表 i n t m d e x ；，在构造过程中，成员编号 c ，c + + 程序安全检查工具前端的设计与实现 p u b l i c ： 其它操作接口 ) ； 3 2 3 4 指针、引用和数组类型信息的存储 在c c + + 语言中，指针、引用和数组类型需要保存的信息相似。指针需要保 存指针指向的类型；引用需要保存披引用的类型；数组需保存数组元素的类型。 对于这三种类型，前端采用类p a r b a s e t y p e i n f o r 来处理其相同的部分，在 p o i n t e r t 如e i n f o r 、r e f e r c n c e l 卯e i n f o f 和a 娥l y t y p e i n f o r 中处理不同的部分。它们 之间的关系如图3 7 所示。 图3 8 数组，指针和引用结构之间关系 p a r b a s e t y p e i n f o r 中e l e m e n t t y p e 表示成员类型，在指针类型中对应指针指向 的类型；在引用类型中对应引用的类型；在数组中对应数组元素类型。d i m 表示维 数。对于指针，d i m 表示多级指针的级数；对于数组，d i m 表示数组的维度；对于 引用，d i m 为l ，因为c + + 中，不允许出现引用的引用。 对于指针、引用和数组类型没有独立的名称，在处理中为了便于检索，应对 其构造内部名称，其规则如下： p o i n t e r t y p e n 锄e：= e 1 e m e n t t y p e n 咖e 审 r e f c r e n c e 聊e n 锄e ：= e l e m e n f 聊c n 锄e & 一 a r r a y t y p e n 锄e：= e l e m e n t t y p e n 锄e 【d i m e m s i o i l v a l 聆】 e l e m e n t t y p e n a m e：= e l e m e n t l y p e 的名称 d i m e 璐i o n v a l u e ：= a r r a y t y p e i n f o r 中成员a r r a y s i z e 的值 3 2 3 5 函数类型信息的存储 第三章c c + + 程序安全检查工具前端的设计与实现 函数类型采用f i l r i c 廿o n t y p e i n f o r 存储，f u n c t i o n 聊e i n f o r 继承自b 船e 聊e i n f o r 和d e c l a r a t o r s y i n b o l 。f 啪c t i o 嘶i n f o r 继承自 d e c l a r a t o r s y m b o l 的原因和 d e c l a r a t o r s v m b o l 结构将在标识符( d ) 抽象语法树节点c p p i d a s t 部分作详细介 绍。f 岫c t i o n t y p e i n f o r 的定义信息如下： c l 船sf 咖c t i o n t y p e i n f o r ：p u b l i cb 嬲e 1 卯e i n f o r ，p u b l i cd e c l a r a t o r s y n l b o l p r i v a t c ： p a r a m e t e r l i s t p a r 姗e t c r l i s t ； 参数列表 b 硒e 1 y p e i n f o r e t 啪t y p c ； ，返回值类型 f l l i l c t i o n s p e c i f i e r 如n c t i o n s p c c i f i c r ； ，函数修饰符 p u b l i c ： 其它操作接口 ； 其中p 甜a m e t e r l i s t 为参数列表，其元素类型为f i e l d i n f o r ，分别表示函数的形 式参数，该列表中元素的顺序和函数声明或定义时参数的顺序一致；r e t 啪t y p e 为 返回值类型，指向函数的返回值对应的类型信息结构；向n c t i o n s p e c i f i e r 表示函数 修饰符，有以下几种情况：i n l 妇、v i n i l a l 、e x p l i c “和s 协t i c 。 在前端构造的现阶段，还未考虑重载解析。采用一种简单的办法对函数名称 进行处理： ( 1 ) 对于全局函数，函数内部名即函数名，不需作任何处理； ( 2 ) 对于成员函数，函数名称的构造规则如下： f u n c t i o m t y p e n 锄e ：= c l 船s n 锄e ：r e “f 岫c t i o r l n 锄e r e a l f u n c t i o l l n a i i l e ：= 定义的函数名称 在前端中，函数类型作为函数定义信息的一部分或者用来构造函数指针类型， 用来构造函数指针类型的函数类型通常为匿名函数类型。 3 2 3 6 别名和常量类型信息的存储 别名类型指的是通过t y p e d e f 定义的类型，根据c c + + 规范，别名类型和其原 始类型等价。常量类型是指具有c o n s t 修饰符的类型，但是c o n s t 类型和其非c o m t 类型不等价。别名类型采用1 e d e f r y p e i n f o r 存储，常量类型采用t y p e d e f r e i n f o r 的别名类型c o 邮t t 如e i n f o r 存储。它们存储的信息完全相同，因此下面仅对 1 帅e d e n n f o r 进行介绍。 t y p e d e f r 如e i n f o r 的定义信息如下： c l 勰s 聊e d e f i 阳e i n f o r ：p u b l i cb 弱e 1 卯e i n f o f p r i v a ：t e ： c c + + 程序安全检查工具前端的设计与实现 b 硒e t y p e i n f o r +o r i g i i l a l t y p e ； 原始类型 p u b l i c ： b a s e t y p e i n f o b a s e t ) ，p e i n f o g e t o r i g i n a l t y p e ( ) ； g e 依e a l l y p e ( ) ； 获取原始类型 ，获取真实类型 ； g e 吸e a l t y p e ( ) 获取别名类型真实类型时，若别名类型的原始类型为别名类型， 则返回原始类型的真实类型。 3 2 4 函数定义信息的存储 函数的定义信息在符号表中有且仅有一个表项，此项的结构为 f l l i l c t i o n s y m b o l ，使用函数的内部名称作为关键字。f 吼c t i o n s y m b o l 记录函数的所 有信息，其定义信息如下： c l a s sf u n c t i o n s y m b o l ：p u b l i cc p p s y m b o l p r i v a t e ： f u n c t i 锄l t y p e i n 篮+ 缸1 c t i o n t y p e ； ，函数的类型信息 r e 肥p p a s t a s t ；函数体的抽象语法树 c o n t r o l f l o w g r a p h +c 瑶 函数体的控制流图 p u b l i c ： 其它操作接口 ) ； 其中f i l r l c t i o n l y p e 指向函数的类型结构，邪t 指向函数体的抽象语法树，c 龟指 向函数的控制流图。后端可以通过在符号表中检索获取函数定义信息。 在语法分析过程，可以获取函数的类型信息，并且构造函数体的抽象语法树。 再通过遍历函数体的抽象语法树构造函数的控制流图，抽象语法树和控制流图的 内容将在后续章节介绍。 3 2 5 变量定义信息的存储 前端的符号表内记录所有变量的定义信息，包括全局变量信息和局部变量信 息。全局变量存储在编号为2 的作用域内，局部变量信息存储在变量定义时所在 的作用域内。在符号表中使用v a r i a b l c s y m b o i 记录变量的信息，其定义信息如下： c l 髂sb a s e v 撕a b l e s y m b o l ：p 曲l i cc p p s y m b o l ，p u b l i cd e c l a r a t o r s y m b o l p r i v a t e ： b 勰e t y p e i n f o r v 卿； 变量的类型 第三章c 妃+ + 程序安全检查工具前端的设计与实现 i m s c o p e ； 变量定义所在的作用域