（计算机应用技术专业论文）考虑指针别名的静态分析技术研究.pdf

_ ， j 1 ， 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 日期：印f 。年r 月弓日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 翩躲靼 日期：2 矿f 口年y 月哆日 - 厶 一 摘要 摘要 虽然当今编程语言层出不穷，但c 语言作为主流语言仍然被广泛地应用到各 种系统的开发中。因为当今软件开发的成本越来越高，如果稍有不慎，就可能造 成很严重的软件故障，从而造成相当严重的经济损失。应这方面的需求，软件测 试工具应运而生。作为软件测试工具，静态代码分析工具不用执行源代码程序就 可以检测软件中的错误或者是缺陷，再加上它对成本的要求比较低，所以被越来 越多的公司所采用。 尽管当前静态代码分析工具种类繁多，但是都存在着指针别名分析不够准确 的问题，有的工具忽略指针别名分析，有的工具则采用其他形式来代替指针别名 分析。由于指针别名分析的好坏将直接影响到静态分析工具代码分析的准确率， 所以针对当前代码分析工具存在的这些问题，设计和实现了指针别名分析算法， 并将此算法应用到自行开发的工具c c h e c k c r 中。 指针别名分析分为过程内指针别名分析和过程间指针别名分析。过程内采用 对控制流图进行数据流分析的方法，通过遍历程序的控制流图，记录下函数、参 数、变量的使用情况，并且根据c 语言的独特性设计了c 语言别名的规则集和关 于c 语言的过程内指针别名分析方法，并通过实例来验证了方法的正确性。因为 c 语言存在着参数传递和全局变量，使得过程内分析还不够完善，需要引入过程间 的指针别名分析，通过拓展调用图生成程序的联系图，增强联系图的属性，实现 了c 语言过程间的指针别名分析算法。 本论文在参考c t r e e 的基础上，使用面向对象的方法自行设计和实现了考虑 指针别名的静态代码分析工具c c h e c k e r ，设计了静态代码分析系统的架构图和系 统的各个功能模块，给出了代码分析的流程图，介绍了源代码静态分析工具中主 要的类和接口。考虑到缺陷或错误的级别、用户关注点和文件路径等等因素的影 响，有针对性地设计了静态分析工具的命令。通过和静态代码分析工具c p p c h e c k 做比较，c p p c h e c k 没有考虑指针别名分析，可以看出本工具在代码分析的准确率 上有了一定的提高，并且从实际应用中证实了该工具的实用性。 关键词：指针别名分析，调用图，联系图，控制流图，数据流分析 一 j a b s t r a c t a bs t r a c t a 1 t 1 1 0 u 曲t o d a y sp r 0 伊a m m 协gl 锄g u a g e se m e 唱ei n 髓d l e s s l y ，b u tt 1 1 ec1 觚g u a g e 於am a i n s 骶a ml 趾g u a g ei ss t i l l 埘d e l y 印p l i e dt 0m ed e v e l o p m 锄to fv 耐o u ss y s t 锄s m c a n w h i l e ，r e q u i r 锄t so nd e v e l o p e 腭a 他i n c r e 嬲i 1 1 9 1 yh i g h b e c a u s et o d a y s 址g h c o s to fs o 触盯ed e v e l o p m 跗t i fs l i g h t l yc 盯e l e s s ，y o um a yh a v eas 喇o l l ss o 觚a 托 伍1 u r e b e c a u s eo ft h i sd e m a n d ，s o 脚a r ct c s t i i l gt 0 0 l sc o m ei n t 0b 咖g a ss o 俞w a r c t c s t i n gt 0 0 1 s ，s t a t i cc o d e 缸a l y s i st o o l sc 缸d e t e c ts o 胁a r ee r r o r so rd e f e c t sw i t l l o u t i m p l 锄e n t i n gt 1 1 es o u r c ec o d ep r 0 笋a m i na d d i t i o n ，b e c 孤s eo f i t sr c l 撕v e l y1 0 wc o 瓯 s t a t i cc o d e 觚a l y s i st 0 0 1 sa r eu s e di nm o r e 孤dm o r cc o m p 觚i e s 灿t l l o u 曲t 1 1 e r e 盯ea 、i d em g e o fc u r r 髓ts 谢cc o d e 觚a l y s i st 0 0 l s ，血eq u e s t i o n i s 也a tp o i i l t e ra h 硒孤a l y s i si sn o tp r e c i s e ，s o m et 0 0 1 si g n o r e 也e “a sa n a l y s i s ，0 ru s c o n l e rf o m st or 印l a c et 1 1 ep o i n t e ra l i 嬲趾a l l y s i s a s 也ep o i n t e ra l i 嬲锄a l y s i sd i r e c t l y 世e c t sm ea c 跚r a c yo fs t a t i c 觚a l y s i st o o l s i n 、，i e wo fm o s ep r o b l e m si nc l l r r e n t 蛆a l y s i st 0 0 1 s ，w ed e s i g n 锄di n l p l e m e n t 也ea l g o r i m mo fp o 洫e ra l i 硒，t h i sa l g o r i 也m a p p l i e d t om es e l d e v e l o p c dt o o l s 一c c h e c k 既 p o i n t e ra l i 笛锄a l ”i si sd i 讥d e di n t 0m ep o i n t e ra h 邵趴a l y s i s 谢t l l i nt h ep r o c e s s 缸dt l l ei i l t e 印r o c e d l l r a lp o 血盯a n 觞觚a l y s i s w eu s e 也em e 吐l o do fi m p r 0 v e dc a l l 鲫h a 1 9 0 r i 也mt 0r e a l i z ei t s 撕笛锄a l y s i s p r o c e s s 谢t l l i n 也ec o m r 0 1f l o wg r a p hu s e st 1 1 e m e n l o do fd a t an o w 弛a l y s i s ，b yt r a l v e r s i i l gt 1 1 ep r o 铲锄c o n 仃d ln o w 伊a p h ，r e c o r d s 也e u s a g eo f 如n c t i o n s ，p a r 锄曲e r s 如dv 撕a b l e s b 嬲e d o nt 1 1 el l l l i q u 髓e s so f 也ec 1 趾g u a g e ，w ed e s i g nan l l es e to fa l i 蹈，am e m o do fp o i n t c ra l i 鹊姐a l y s i so nm ec l 孤g l l a g ew i t h i np r o c e s s ，觚dv 耐矽也em e m o dt 1 1 r o u 曲e x 锄p l e s b e c 孤s eo f 也e 懿i s t 锄c eo fp a r 锄e t e r s 跹d9 1 0 b a lv 耐a b l e s ，也e 髓a l y s i s 嘶m i n 也ep r o c e s si sn o t p e 疵c t i tn e e dt 0i i l 仃0 d u c e 也e 缸a l y s i so f 也ea l i 觞b 咖e 既劬c t i o n s t h r o u 曲 e x p 锄d i n g 也el i l l kg r a p ho f 也ec 2 l 1 1g r a p hg 锄训i o np r 0 伊锄t 0e n h 勰c e 也ep r o p e n i e s o f 也el i n k 黟印h ，吐l e1 a n g l l a g e i i l d 印铋d ta l g o r i t l l mi sd e s i 朗e d b 雒e do nn l ec t r e e ，衄sd i s s 叭鲥o nd e s i 印c d 锄di m p l 锄髓t c dt 1 1 es t a t i cc o d e 觚a l y s i st 0 0 1 卜- c c h e c k e ru s i n gt l l e 印p r o a c ho fo b j e c t - o r i t e d ，n l et o o lc o n s i d c r s 也e p o i n t e r “a s t h ed i s s e r t a t i o nd e s i g n e dt h es y s t e m 疵h i t e c t i l r ed i a 伊锄o fm es 谢c l i c o d e 趾a 1 v s i s 锄d 缸l c t i o nm o ( “e s ns h o w s 也en o wc h a nd i a 莎a mo fc o d ea i l a l y s l s a n dd e s 嘶b e sm em a i nc l a s s e s 锄di n t e r f a c e so ft l l es o w c ec o d es 切t l ca i l a l y s l s t o o l s t a b n gi n t oa c c o u n t 也e 撕b c to f 也el e v e lo fd e f e c t s0 re n 0 r s ，u s e r sc o n c e m s a 1 1 dn l e pa _ m s ，w ed e s i 印c o i n m 锄d so fs t a t i cc o d ea n a l y s i st 0 0 1 s b yc o m p a n n g 也e t o o lw e d e s i 印a 1 1 dc p p c h e c k ，c p p c h e c kd o e s n o t c o n s i d e r 也ep o m t e r 2 l 1 1 a s a n a l y s l s ， o b v i o u s l v 也a tm ec o d ea n a j y s i st 0 0 1h a s ac e n a i ni i n p r o v 锄e n to n 也ea c c u r a c y ，a 1 1 d p r a 甜c a la p p l i c 撕o np r 0 v e 也eu t i l 时o f m et 0 0 1 k e y w o r d s ：p 咖t e r a 1 i a l sa n a l y s i s ，c a l l 研a p h ，l i i l k 咖h ，c o n 仃0 1f 1 0 w 啦，d a t a f l o wa n a l y s i s i 目录 目录 第一章绪论 1 1 研究背景1 1 2 研究意义2 1 3 研究工作3 1 4 本文的组织结构4 第二章静态代码分析中的关键技术6 2 1 词法分析和语法分析6 2 2 控制流图分析9 2 2 1 深度优先搜索9 2 2 2 边的构造1 1 2 2 3 流图的深度12 2 3 本地分析和全局分析1 2 2 3 1 本地分析方法1 2 2 3 2 全局分析方法1 4 2 4 指针别名分析15 2 5 小结1 6 第三章指针别名分析算法的设计1 7 3 1 过程内指针别名分析1 7 3 1 1c 语言中的指针别名2 1 3 1 2 过程内指针别名识别程序2 2 3 1 3 过程内指针别名传递程序2 6 3 1 4 验证方法的正确性2 7 3 2 过程间指针别名分析3 2 目录 3 2 。1 基于调用图的指针别名分析3 3 3 2 2c 语言的过程间指针别名分析4 5 3 3 小结4 7 第四章静态代码分析工具的设计和实现。4 8 4 1 静态代码分析系统设计4 8 4 2 静态代码分析工具的实现5 0 4 2 1 静态代码分析系统流程5 0 4 2 2 主要类图和接口说明5 3 4 3 静态代码分析工具的命令设计。5 7 4 4 _ 、结5 8 第五章测试和分析。5 9 5 1 测试环境5 9 5 2 功能测试5 9 5 2 1 具体错误查找5 9 5 2 2 综合测试6 0 5 3 性能对比6 2 5 4 小结6 3 第六章总结和展望“ 6 1 主要工作6 4 6 2 未来工作6 5 至| 谢6 6 参考文献6 7 攻硕期间取得的研究成果 v 第一章绪论 1 1 研究背景 第一章绪论 代码分析是目前主流的验证软件安全性的方法之一，包括静态分析和动态分 析方法。静态分析是指在不执行代码的情况下对代码进行评估的过程。静态分析 十分强大，这是因为它允许对多种可能性进行快速考虑。一个静态分析工具能够 探查大量“如果将会 的想定情况，而不必为验证所有这些想定情况来 执行这些代码。静态分析尤其适合用于安全方面的检查，因为许多安全问题都发 生在一些隐蔽的、难以出现的情况下，这非常难以通过实际运行该代码来达到目 的。好的静态分析工具提供一种快速的方法，能对大量代码进行可靠而详尽的评 估。事实上，很多相当成熟的系统中还包含着错误，只凭测试人员手工测试很难 找出这些错误，而通过静态分析则已经发现了现存系统中的很多错误。静态分析【l 】 能够在开发早期发现错误，甚至，在程序首次运行之前就可以发现。及早发现错 误，不仅仅减少了修补错误所付出的费用，而且这种快速反馈中期可有助于指导 程序员的工作：程序员将有机会修正他们之前没有注意到而很可能会发生的错误。 动态分析通过向程序中植入分析代码，根据程序的运行结果检查程序中的安全漏 洞，它仅考虑程序中的单条执行路径，其分析是不完备的且增加了运行时开销【2 】。 目前情况下有很多的源代码静态分析工具，有一些商业的，也有一些开放源 代码组织许可下的开源工具。商业的c 源代码检测工具如p c l i l l t 【3 】、d o u b l e c ! h e c k 、 q a c 【4 1 、r e dl i z a r d sg o 锄a 【5 1 、l d r at c s t b e d 【6 】。这些工具往往产生太多的无用 信息，尤其是产生太多的误报。在这里，误报【7 】是指这样一种问题，即当程序中实 际不存在问题时，而报告了问题。大量的误报确实会带来很多困难。吃力地阅读 长长的误报列表，这不仅让人感觉像是进行体力劳动，而且，不得不查看长长的 误报列表还可能遗漏掉隐藏在列表中的重要结果。开源的检测工具如凡盯s 、 c l 锄g 、s p l i n t 【引、s p r 弱e 、b l a s t 、f r a m a - c 、c p p c h e c k 等等，一般都是国外的某 些大学或研究机构做学术研究而开发的。国内在这方面的研究几乎是一片空白， 北京邮电大学对这方面做了一些有益的尝试，并且申请了专利【9 】。 对于目前的属性验证工具来说，重点是程序的属性分析【l 们，如某个程序点是 否可达，多线程编程中是否存在互斥或者竞争状态等程序逻辑属性，当涉及到指 电子科技大学硕士学位论文 针别名分析时，不少工具采用了忽略【l l 】或者简化 1 2 】的办法，最终的代价是结果可 能出现误报或者是实际应用工具前需要手工修改相应的代码。指针分析工具则主 要用来分析程序中空指针的出现或者内存泄漏等物理属性情况【1 3 】，和其它静态技 术类似，指针分析受到可判定性问题的困扰，对大多数语言来说，所得到的解总 是一个近似解，另外指针分析的方法和属性验证方法迥异，从而使得指针分析的 用途总受到一定的限制。 在众多的指针别名分析方法中，国外学者e m 锄i 和w i l s o n 提出的方法影响较 大，e m 锄i 首次提出了指针别名信息的指向( p o 砬t o ) 表示法，能比较有效的表示 指针别名信息，并进而提出了一个上下文敏感的跨过程指针分析框架，但e m 锄i 的方法【1 4 】实际上相当于过程嵌入，在程序中包含指针运算或动态内存申请的情况 下无法正确进行指针分析，且不能有效处理实用的大程序。w i l s o n 提出的部分传 递函数伊t f ，p 州a 1t r a n s 向f u n 嘶o n ) 的概念比较有效的解决了上下文敏感的跨过 程指针分析问题，并能对一些大的实用程序进行有效分析，但分析某些大规模程 序时结果不够准确【1 5 16 1 。j i a l l w 锄z l l u 和s i m a nc a l m 锄对p t f 的概念进行了改进， 并引入布尔代数中的二叉决策图( b d d ，b i n a r yd e c i s i o nd i a 伊锄) m 1 8 】来获取函数 调用点及被调用函数处的程序状态和指针指向关系，该方法可获得较为准确的指 针别名信息，且效率较高。复旦大学并行处理研究所开发的c 程序分析工具a g a s s i z 系统【1 9 2 0 1 ，对c 程序中的指针作了详细的数据流、控制流分析以及跨过程分析， 但其目的主要是程序的并行优化。 尽管指针别名分析在近几年来取得了很大的进展，但仍然存在着不足之处， 具体表现在： 1 指针分析结果的应用没有得到进一步的研究。 2 指针分析没有和其他数据流问题结合。 指针分析的结果给出了在程序的任意一点，指针变量可能指向的变量集合。 然而单纯地给出此结果是不够的，指针分析如果仅停留在这一点上，无法有效地 保证其他过程间问题的精确性，同时也无法保证并行变换的有效进行。 因此，开发实用有效的指针分析算法，同时利用指针分析的结果结合c 语言 的其他过程间问题，是十分必要的。 1 2 研究意义 随着社会的发展，软件开发技术也在不断的发展，但c 语言作为古老的程序 2 第一章绪论 开发之一仍然在广泛的被应用到各种软件开发中，c 语言自身的缺陷所带来的问题 也不容忽视。能造成重大人员伤亡和巨大财产损失。例如：前苏联切尔诺贝利核 电站的发射性元素外泄事件和美国宾夕法尼亚州三里岛核电站事故；1 9 9 8 年8 月 到1 9 9 9 年5 月的1 0 个月间，美国的三枚运载火箭共发生了五次发射失败。这些 事件给社会带来了不可估量的损失，因此，进行软件故障诊断研究，具有重要的 意义【2 。记着当时在校外实习期间，在项目的测试阶段因为软件的内存泄露，公 司决定引入p c l i n t 对代码进行审查，不经意间接触到了静态代码分析工具，虽然 p c l i n t 的功能还比较有限，存在着各种误报和漏报，但是还是给开发工作带来了 很大的便利，大大节省了项目开发经费，其价值不容小觑。 国外很多大的软件开发公司在其开发的早期就引入了代码审查，国内对代码 审查还处于起步阶段，尤其对于广大的学生来说，更是很少用这样一个工具来进 行代码的自检，结果造成就养成了很多坏的习惯，对于软件开发素质的培养造成 了很大的伤害。如果能够开发一个用于代码审查的工具，并且这个工具可以以插 件的形式应用到各个主流的软件开发工具中去，那么将极大地提高软件的质量。 随着中国软件事业的发展，一批大的软件开发公司也逐渐涌现出来，那么代码审 查工具的应用也必将更加广泛，其市场价值肯定相当巨大。 1 3 研究工作 本论文源于教研室“核高基”课题数字电视s o c 嵌入式软件测试平台中代码 分析项目，该项目的目标是针对c 语言开发的项目进行代码分析，给出函数的调 用关系和次数，建立函数的调用图 2 2 2 3 2 4 】。原项目依托开源软件c t r 来实现，本 论文参考c t r c e ，基于语法树、控制流图和调用图的思想，设计和实现了指针别名 分析算法，并将其加入到自行开发的c 源代码静态分析工具c c h e c k e r 中，工具取 名c c h e c k e r 的原意是c 代码检查工具。 本文的工作是使用面向对象的方法自行设计和实现了考虑指针别名的静态代 码分析工具c c h e c k e r ，并设计和实现了其它静态代码分析工具中忽略掉的指针别 名分析算法。本论文的主要工作如下： 1 介绍了静态代码分析所采用的技术，并且分析了当前静态代码分析工具的 局限性，在此基础上针对程序指针别名分析提出了自己的解决方案。 2 针对其它静态代码分析工具存在的问题一忽略指针别名分析，而指针别名 分析的好坏是影响静态代码分析准确率的最重要因素之一。作为静态代码分析重 3 电子科技大学硕士学位论文 要组成部分的指针别名分析，本论文基于语法树、控制流图和调用图的思想，设 计和实现了过程内和过程间指针别名分析算法，并且验证了此算法。 3 使用面向对象的方法自行设计和实现了静态代码分析工具，并给出了静态 代码分析的架构图，各个功能模块和流程图，给出了系统的主要类和接口。考虑 到缺陷或错误的级别、用户关注点和文件路径等等因素的影响，有针对性地设计 了静态代码分析工具的命令。 4 过程内指针别名分析首先给出了c 语言的指针别名规则，设计了c 语言的 过程内指针别名分析算法，并用示例验证算法的正确性。针对过程内分析的局限 性，在过程内分析的基础上，根据控制流图构造程序的调用图，然后在此基础上 构造程序的结合图和成对结合图，设计了过程间指针别名分析算法。 5 通过测试现有c 语言开源项目的源代码，验证了c c h e c k e r 的可行性。通过 和静态分析工具c p p c h e c k 作比较，c p p c h e c k 没有考虑指针别名分析，从测试结 果可以看出c c h e c k e r 在代码分析的准确率上有了一定的提高。从c c h e c k e r 执行 时间和测试代码行的关系图得出c c h e c k e r 运行时间随着代码量的大小成线性增 长。 1 4 本文的组织结构 论文共分为6 章，组织结构如下： 第一章为绪论部分，分析了静态代码分析的研究现状，讨论了指针别名分析 在静态代码分析中的作用及相关的研究现状，阐述了论文的内容和组织结构。 第二章首先阐述了静态代码分析技术，包括词法分析、语法分析、控制流分 析、本地分析和全局分析等等，其次对其它静态代码分析工具忽略的指针别名分 析做了描述。因为控制流分析是过程内指针别名分析的基础，所以对控制流分析 技术做了详尽的描述，包括流图的搜索、流图的深度等等。 第三章设计和实现了静态分析工具中的指针别名算法。因为指针别名分析是 关乎静态分析工具最重要的因素之一，所以在介绍静态代码分析工具c c h e c k e r 的 设计和实现之前单独用一章来指针别名分析算法的设计和实现。本章首先介绍了 针对c 语言设计的指针别名规则集。然后指针别名分析分为过程内和过程间两部 分来分开讨论，对过程内指针别名分析设计了别名识别程序和别名传递程序，过 程间指针别名分析给出了基于调用图的分析算法，并且通过示例来验证了算法的 有效性。 4 第一章绪论 第四章设计静态代码分析工具c c h e c k e r 的整个系统框架和框架中各个部分的 功能，然后给出了静态代码分析系统的流程图，并且对项目涉及的主要类和接口 做了介绍。考虑到缺陷或错误的级别、用户关注点和文件路径等等因素的影响， 有针对性地设计了静态代码分析工具的命令。 第五章设计有针对性的测试用例，来测试工具的功能。通过对大型项目的测 试，得到的数据和其它的静态代码分析工具测试所得数据做比较，可以看出本工 具在代码分析的准确率上有了一定的提高。从c c h e c k c r 执行时间和测试代码行的 关系图得出c c h e c k e r 运行时间随着代码量的大小成线性增长。 第六章对本文所做工作做了总结和展望。概括论文所做的主要工作和创新点， 同时指出不足和未来研究的方向。 5 电子科技大学硕士学位论文 第二章静态代码分析中的关键技术 本章将介绍设计静态代码分析工具需要的基本技术。词法分析和语法分析是 静态代码分析的基础。由它们生成的符号表和抽象语法树，则是生成控制流图和 调用图的基础。静态代码分析工具主要是在控制流图和调用图的基础上来分析代 码中的错误或者是缺陷，所以对控制流图分析做了较为详细的介绍。又因为对指 针别名分析的好坏影响到静态代码分析工具的正确率，而现有静态分析工具往往 都忽略指针别名分析，这一章的最后就指针别名分析的技术做些简要的介绍， 为第三章设计指针别名算法做个铺垫。 2 1 词法分析和语法分析 工具针对源代码的操作，首先是将这些代码转化为一系列的记号，并沿途丢 掉程序文本中那些不重要的部分一比如空白和注释。这种记号流的创建称作词法 分析2 5 1 。词法规则通常使用正则表达式来识别记号。表2 1 给出了一组简单的词 法规则，可用于处理下列c 语言程序片段： i f ( r e t ) 可能为t r u e m a t 【x y 】= e n dv a l ； ) 表2 1 词法分析规则 i f r e m mi f ； ( r e m ml p a r e n ；) ) r e t u ml 理a r e n ； r e t u m l b r a c k e t ； 】 r e t u n lr b r a c k e t ；) r e m m e q u a l ； r e t u ms e m i ；) t 、n + 严i 印o r e 、v h i t e s p a c e 八奉 严i g n o r ec o m m e n t s 【a - z a z 【a z a - z o - 9 r e m m ；) 6 第二章静态代码分析中的关键技术 这段代码产生出下列记号序列： i fl p a r e ni d ( r e t )r p a r e ni d ( m a t )l b r a c k e ti d ( x )r b r a c k e tl b r a c k e t i d ( y )r b r a c k e te q u a li d ( e n d v a l )s e m i c t r e e 的词法分析基于u n 通用的词法分析生成器f l e x 来生成，f l e x 最初 由v 确p a x s o n 于1 9 8 7 年用c 语言写成。f l e x 是一个生成扫描器的工具，能够 识别文本中的词法模式【2 6 】。f 1 e ) 【读入给定的输入文件，如果没有给定文件名的话， 则从标准输入读取，从而获得一个关于需要生成的扫描器的描述。此描述叫做规 则，由正则表达式和c 代码对组成。f l e x 的输出是一个c 代码文件一c x c ， 其中定义了谢c x o 函数。编译输出文件并且和- l n 库链接生成一个可执行文件。 当运行可执行文件的时候，它分析输入文件，为每一个正则表达式寻找匹配。当 发现一个匹配时，它执行与此正则表达式相关的c 代码。 语言解析器使用与一种上下文环境无关的语法来匹配上述的记号流。这种语 法由一组产生式构成，用以对语言中的符号( 元素) 进行描述。下面列出了一组 产生式规则，这些产生式规则能够用来解析上述的示例记号流。 s t m t ：= i f s t m ta s s i g n s t m t if s t m t：= i fl p a r e ne x p rr p a r e ns t m t e x p r ：= l v a l a s s i g n s t m t ：= 1 v a le q u a le x p rs 叫i 1 v a l ：i d a r r a c c e s s a r r - a c c e s s：= i da r r - i n d e x + a r r i d x：= l b r a c k e te x p rp b r a c k e t 解析器通过将上面提到的记号流与这些产生式规则进行匹配而执行一种派 生。如果每个符号都与派生出此符号的那个符号相连接，那么一棵解析树就形成 了。图2 1 显示了使用上面产生式规则创建的一棵解析树。这里，省略了那些不携 带名称的终结符号，从而使这棵解析树种的重要部分更加明显。如果你想创建自 己的解析器，一种传统的方式就是借助于历史悠久的u n i x 程序l c x 和c ，可作 为用c 语言实现自己的解析器的开始。 基于一棵解析树来进行重要的分析，这不仅是可行的，而且，某些特定类型 的格式检查可基于解析树执行得特别好，这是因为解析树中包含了关于代码的最 为直接的表示一就像程序员所写的一样【2 7 1 。当然，由于多种原因，基于解析树来 执行复杂的分析可能有些困难。这种树中的节点是直接从语法的产生式规则派生 而来的，而这些规则会引入一些非终结符号，这种符号的存在纯粹是为了使得解 析易于进行并且没有歧义，而不是为了产生更易理解的树；通常来说，要进行这 7 皇王型垫奎堂堕主堂垡笙茎一 _ - - _ - _ _ _ _ _ - - _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ - - _ _ _ _ _ _ _ - _ _ _ _ _ i _ _ _ _ _ _ _ _ _ _ _ - 一一 种分析，较好的做法是在程序文本中，提取走语法中的细节和句法的修饰成分。 完成这项工作的数据结构称作抽象语法树。a s t 的目的就是提供一种适合于后期 进行分析的标准化的程序版本。a s t 通常是通过将树状结构代码与语法的产生式 规则相关联而构建的。 e x p r 上 l v a l d ( r e t ) i fs 廿i l t i d ( m a t ) 上 a 丌d x 胀。岛。v 叫a r ri d x a r r l d xl u 【匕n u v a l j 土 1 l 焉 王 。姜x ，y ， 图2 1 产生式规则所派生的一棵解析树 。孑天、， m啦 t 一 咖i 巨： s _sa 。 咖土 一 第二章静态代码分析中的关键技术 图2 2 显示了一棵a s t ，用于说明我么前面给出的实例。注意，i f 语句现在有 一个空的e l s e 分支，这个i f 所进行的谓词检查现在就是一个与“0 清晰的对比关 系( c 语言提倡这种行为) ，而且数组的访问统一表示为二进制操作。 根据系统的需要，a s t 可包含一个比源语言数量更为有限的结构。例如，对 方法的调用可能会转换为对函数的调用，或者f 0 r 和d o 循环可能转换为w h i l e 循环。 以这种方式对程序进行重大简化称作降级。紧密相关的语言一比如c 和c + + 语言， 可被降级为同一种a s t 格式，不过，这种降级也带来了歪曲程序员意图的风险。 句法上相似的语言一比如c + + 和j a v a ，可以共享许多相同的a s t 节点类型，但毫 无疑问会有一些特殊类型的节点仅用于各自的语言中。 2 2 控制流图分析 不含9 0 t 0 的程序具有可约流图，很多程序设计方法学鼓励程序具有可约流图。 对多种程序的研究显示，事实上人们编写的所有程序都具有可约流图【2 8 】。该观察 结果同程序优化有关，因为在可约流图上我们可以找到执行速度非常快的优化算 法。本节我们将讨论一些流图的概念。 2 2 1 深度优先搜索 一种很有用的流图节点排序方法，称为深度优先排序【2 9 1 。深度优先排序可以 用来检测流图中的循环，还有助于提高数据流算法的速度。深度优先排序从初始 节点开始，然后搜索整个图，并尽可能快地访问离初始节点远的节点( 深度优先) 。 搜索的路线形成一棵树。 对图2 3 中流图的深度优先搜索如图2 4 所示。实线边形成一棵树，虚线边表 示流图的其他边。对流图的深度优先搜索相当于对树的前序遍历 l 3 4 - 6 7 8 1 0 ，然后返回8 ，再到9 。再一次返回8 ，回退到7 ， 6 ，4 ， 然后到5 。再从5 退回到4 ，再返回到3 和1 。从1 到2 ，再从2 返回l ，这样我们 就对整个树进行了前序遍历。 节点的深度优先顺序和前序遍历中各节点最后一次被访问的顺序相反。遍历 树时访问节点的完整序列是：1 ，3 ，4 ，6 ，7 ，8 ，l o ，8 ，9 ，8 ，7 ，6 ，4 ，5 ，4 ， 3 ，1 ，2 ，1 。在该列表中，标注出每个数字的最后一次出现，可以得到：1 ， 3 ， 4 ，6 ，7 ，8 ，地，8 ，2 ，墨，2 ，4 ，主，垒，三，1 ，2 ，土。深度优先顺序是标注 的序列的相反顺序。在此，这个序列恰好是l ，2 ，1 0 。也就是说，一开始节 9 电子科技大学硕士学位论文 一 一_ 一 点是按深度优先顺序编号的。 图2 3 结构化流图 图2 - 4 深度优先表不 通过构造并遍历一棵以初始一节点为根的树，并设法让树中的路径尽可能长， 我们可以给出一个计算流图深度优先顺序的算法。这样的树称为深度优先生成树 ( d f s t ) 。下面就是用来从图2 3 构造图2 4 的算法。 算法：深度优先生成树和深度优先排序。 输入：流图g 1 0 第二章静态代码分析中的关键技术 输出：g 的d f s t t 和g 的节点的深度优先顺序。 方法：使用递归过程s e r a r c h ( n ) ，该算法将g 的所有节点初始化为“未访问， 然后调用s e a r c h ( n o ) ，其中n o 是初始节点。 当我们调用s e a r c h ( n ) 时，我们首先将n 标记为“已访问 ，以免将n 添加到树 中两次。用变量i 记录g 的节点数，并递减到l ，搜索时将深度优先编号d 向 n 】给 节点n 。边t 的集合形成g 的深度优先生成树，它们被称为树边。 深度优先遍历算法： s e a r c h ( n ) b e g i i l 将n 标记为“已访问”； f o r n 的每个后继s i f s 标记为“未访问” 将边n s 添加到t ；s e 眦h ( s ) ： d 血【n 】= i ； i = i 一1 ： e n d t = 空集： f 0 r g 的每个节点 将n 标记为“未访问”： i - g 的节点数； s e a r c h ( n o ) ； 2 2 2 边的构造 当我们构造流图的d f s t 时，流图的边可以分为以下3 类： 1 树中有从一节点m 到m 的祖先( 可能到m 自身) 的边。我们称这些边为 后退边7 4 和9 1 就是图2 4 中的后退边。有趣且有用的是，如果流图是可约的， 则后退边正好是流图中的回边，与s e a r c h ( ) 算法中步骤2 访问后继的顺序无关。对 于任意的流图，每个回边都是后退边，尽管如果这个图是不可约的，将会存在一 些不是回边的后退边。 2 树中有从节点m 到m 的后代的边，称为前进边。d f s t 中所有的边都是前进 边。图3 5 中没有其他的前进边，但是如果4 8 是一条边，它将属于这类边。 3 在d f s t 中m 和n 互相不是祖先，我们称边m 为交叉边。图3 5 中，边2 3 和5 7 就是这样的边。交叉边具有一个重要特性：如果我们画d f s t 时，节点的儿 电子科技大学硕士学位论文 子是从左到右按照它们加人树的顺序画出的，那么所有的交叉边都是从右到左进 行遍历的。 应该注意的是，m n 是一条后退边当且仅当d 伍 m = d 如 n 。在d f s t 中，如 果m 是n 的后代。那么s e a r c h ( m ) 将在s e a r c h ( n ) 之前终止，所以d 伍 m = d m n 。 相反。如果d 血 m = d 向 n ，那么，s e 鲫c h ( m ) 将在s e a r c h ( m ) 之前终止，或者m = n 。 但是如果存在边m 一 n ，或者在d f s t 中n 是m 的后继这个事实使得n 成为m 的后 代，s e a r c h ( n ) 一定在s e a r c h ( m ) 之前开始。因此s e 盯c l l ( m ) 活跃的时间是s e a r c h ( n ) 活 跃的时间的子区间，因此在d f s t 中，n 是m 的祖先。 2 2 3 流图的深度 流图有一个重要的参数称为深度。给定一个图的深度优先生成树【3 0 1 ，深度是 无环路径上后退边的最大数目。 在图2 4 中，深度是3 ，因为路径1 0 7 4 3 带有3 条回退边，而且没有无 环路径带有4 条或者更多的回退边。碰巧的时，这里“最深的”路径上只有回退 边，通常最深路径可能同时带有后退边、前进边和交叉边。 我们可以证明深度永远不会大于流图中循环嵌套的深度【3 1 】。如果流图是可约 的，我们在定义深度的时候可以用同边代替后退边，因为在d 窍t 中，后退边正好 就是回边。深度的概念和实际选择的d f s t 无关【3 引。 2 3 本地分析和全局分析 2 3 1 本地分析方法 与分支和循环相关的这些问题推动着静态分析工具向着一种降低精确度而进 行更为可靠的分析的方向发展。下面来分析一下当前研究的较为流行的分析方法， 分别是：抽象解释【3 3 】、谓词转换器【3 4 和模型检查【3 5 】。 抽象解释是一种通用技术，有2 位c o u s o t ( 即c o u s o t p 和c o u s o t r ) 提出， 这种方法首先将程序中与感兴趣的属性无关的方面抽取出去，而后使用选中的程 序抽象执行一种解释。由循环所带来的问题可通过执行一种流敏感【3 6 】的分析来加 以解决，这种分析没有考虑所执行语句的顺序。从程序员的角度来看，这可能看 起来是一种相当极端的方法；语句在程序中呈现的顺序是非常重要的。不过，流 敏感的