（计算机应用技术专业论文）clang上的cc过程间分析.pdf

摘要 摘要 程序静态分析不编译运行程序，而是对程序源代码进行分析以发现其中的错 误。静态分析的目标不是证明程序完全正确，而是在程序运行前尽可能多地发现 其中隐含的错误，提高程序的可靠性和健壮性。 现有的c c + + 程序的过程内分析已经发展得较为完善，而大部分c c + + 程序 安全漏洞却存在于过程之间的交互作用中，仅仅使用过程内分析技术无法检测这 些漏洞，需要深入研究过程间静态分析的理论和技术。 在传统的过程问分析技术和经典过程间漏洞发掘技术的基础上，针对函数调 用拓扑序列的生成和函数本地分析路径的生成等问题提出了符合c l a n g 架构的 实现算法。对于函数调用序列，采用递归向下的分析方法，保证每个函数即使被 多次调用，函数体本身也只需分析一遍；对于本地分析路径，采用根据本地控制 流图生成实际分析路径的方法，减少了路径分析的时间。 基于l l v m 编译架构以及c l a n g 编译器设计并实现了一个过程问分析工具 的原型s i m p l e l p a 。s i m p l e i p a 通过递归算法创建控制节点，然后对每个函数进 行本地分析，对于某些特殊语句则使用特定的处理算法，在本地分析结束后，采 用模型生成算法产生函数摘要。 实例分析表明，s i m p l e l p a 能够有效地发现过程间的安全漏洞。 关键字：程序静态分析过程间分析漏洞发掘c l a n g a b s t r a e t a b s t r a c t s t a t i ca n a l y s i sd o e sn o tr u nt h ep r o g r a m s ，b u ta n a l y z et h es o u r c ec o d ei no r d e rt o f i n db u g s t h eg o a lo fs t a t i ca n a l y s i si s n tt op r o v et h ec o r r e c t n e s so ft h ep r o g r a m ，t o f i n dv u l n e r a b i l i t i e sa sm a n ya sp o s s i b l eb e f o r er u n n i n gt h ep r o g r a m ，a n dt h e ni m p r o v e t h er e l i a b i l i t ya n dr o b u s t n e s s n o w a d a y s ，t h ei n t r a - p r o c e d u r a la n a l y s i so fc 圮+ + p r o g r a mh a sb e e nd e v e l o p e d v e r yw e l l m o s to ft h ev u l n e r a b i l i t i e sa r ed u et ot h ei n t e r a c t i o n sa m o n gp r o c e d u r a l s ， w h e r e f o r ew en e e dt oi n t e n s i v es t u d yt h e o r i e sa n dt e c h n i q u e so fi n t e r - p r o c e d u r a l a n a l y s i s o nt h eb a s i so ft r a d i t i o n a l i n t e r - p r o c e d u r a la n a l y s i sa n di n t e r - p r o c e d u r a l v u l n e r a b i l i t yd e t e c t i o n ，s o m ee f f e c t i v ea l g o r i t h m sa r ep u tf o r w a r df o rt h eg e n e r a t i o n o ft h ef u n c t i o nc a l l s e q u e n c ea n dl o c a lp a t h s t h e s ea l g o r i t h m sa r es u i tt ot h e f r a m e w o r ko fac o m p i l e r c l a n g i nt h eg e n e r a t i o no ft h ef u n c t i o nc a l ls e q u e n c e ，t h e r e c u r s i v ed o w n w a r da n a l y s i si su s e d ，w h i c he n s u r e st h a tn om a t t e rh o wm a n yt i m e s t h ef u n c t i o n a r ec a l l e d ，t h ef u n c t i o nb o d yw i l lb ea n a l y z e do n l yo n c e i nt h e g e n e r a t i o no fl o c a lp a t h s ，c o n t r o lf l o wg r a p hi n t r o d u c e df o rr e d u c i n gt h ec o s to fp a t h a n a l y s i s b a s e do nl o wl e v e lv i r t u a lm a c h i n ea n dt h e c o m p i l e rc l a n g , a n i n t e r - p r o c e d u r a la n a l y s i sp r o t o t y p es y s t e m s i m p l e l p ai sd e s i g n e da n di m p l e m e n t e d s i m p l e i p au s et h er e c u r s i v ea l g o r i t h mt oc r e a t et h ec o n t r o ln o d e s ，t oa n a l y z ee v e r y f u n c t i o n a n dt h e nu s et h em o d e lg e n e r a t i o na l g o r i t h mt og e n e r a t ef u n c t i o ns u m m a r y t h ee x p e r i m e n tr e s u l t ss h o w t h a t ，s i m p l e l p ac a ne f f e c t i v e l y d e t e c tt h e i n t e r - p r o c e d u r a lv u l n e r a b i l i t i e s k e yw o r d s ：s t a t i ca n a l y s i s ，i p a ，v u l n e r a b i l i t i e sd e t e c t i o n ，c l a n g i i 图目录 图目录 图2 1软件开发周期中的安全实践6 图3 1 静态分析流程1 2 图3 2p r e f i x 流程框架图1 9 图3 3p r e 做本地分析算法2 0 图4 1c l a n g 库组织形式2 6 图4 2c l a n g 驱动器工作流程2 7 图4 3c l a n g 静态分析流程3 0 图5 1 s i m p l e i p a 在c l a n g 驱动配置文件内的添加代码3 3 图5 2 “c l a n g h e l p ”输出截图3 3 图5 3 “c l a n g s i m p e l p a ”输出截图3 4 图5 4 s i m p l e l p a 在c l a n g c c 驱动配置文件中添加的代码3 4 图5 5 a c t i o n s i m p l e l p a 测试代码3 5 图5 6s i m p l e l p a 成功驱动截图3 5 图5 7d e a d s t o r e c 源代码3 7 图5 8d e a d s t o r e c 的控带0 流图输出3 8 图5 9 基于控制流图的路径生成算法3 9 图5 1 0 生成模型信息的来源4 0 图5 1 1s i m p l e l p a 主体算法流程4 4 图5 1 2i p a m a n a g e r 构造函数及核心实现4 6 图5 1 3p a t h a n a l y s i s 函数实现4 6 图5 1 4 返回语句的特殊处理4 7 图5 1 5函数调用语句的特殊处理4 8 图5 1 6 p a t h a n a l y s i s 中的模型生成代码4 8 图5 1 7t e s t c 的源代码4 9 图5 1 8 对t e s t c 进行s i m p l e i p a 的结果截图5 0 图5 1 9d e r e f 函数的控制流图5 0 图5 2 0m a i n 函数的控制流图5 l 图5 2 1d e r e f 函数的模型5 l v i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名： 签字日期：尘扯 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存，汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 晒公开口保密( 年) 作者签名：导师签名： 签字日期：上半阻 签字日期： 第1 章引言 1 1研究背景 第1 章引言 随着计算机应用的不断发展，软件已渗透到国民经济和国防建设的各个领 域，在信息社会中发挥着至关重要的作用。一方面，软件为人们提供了新的生活 和工作方式，软件成为信息基础设施；另一方面，软件不仅在逐步地代替传统硬 件和物理设备，而且在系统中承担了集成的作用。然而，软件的生产现状以及质 量都不能令人满意【l 】。所以程序的正确性、安全性等性质一直受到人们的关注， 如何在软件的开发和运行中保证软件具有这些性质也成为软件理论和技术的重 要研究方向。 程序静态分析作为在程序运行前发现软件漏洞的主要手段之一，对于保证程 序质量，提高软件生产率有重要的意义。如今，程序静态分析的研究是软件工程 研究的一个热点，也已经有一些产品面世。但是由于程序设计语言的复杂性，现 有的静态分析技术很难达到非常理想的效果( 既具有高效率，又能找到尽可能多 的错误) 。静态分析需要更加有效的算法，同时在程序模型的构造、路径选择等 方面，需要有更好的策吲引。 近年来，国内外研究者采用将动态测试和静态分析有机结合的方法，从而将 分析的路径限制在一定的范围。这种方法的尝试获得一定的成果，例如文献【3 】 中的e x e ( e x e c u t i o ng e n e r a t e de x e c u t i o n s ) 漏洞自动发掘工具和文献【4 】中的程 序验证工具。它们采用符号执行的方法来自动地生成测试例和测试输入。 c l a n g ( l l v m 的c 语言族编译器) 作为新一代编译器，提供了许多为静态 分析使用的库函数和数据结构。利用c l a n g 的特性解决静态分析算法与编译器耦 合的问题，这是本文选择c l a n g 作为实验平台的依据。 在c c + + 的静态分析工具中，过程间分析是发掘现代软件漏洞的最有效技术 之一副。有一些静态分析工具如p r e f i x 5 1 ，给出了基于模型仿真的过程间分析解 决方案。但是过程间分析的开销很大，如何有效地进行过程间分析能否以及如 何采用和动态测试有机结合的技术，这些都是过程间分析面临的难点。 在此背景下，对静态分析技术进行研究，采用过程间分析技术完善c l a n g 上 已有的静态分析工具，进行过程间漏洞发掘方案研究。 第1 章引言 1 1 1静态分析的发展 静态分析技术又称为静态测试技术，区别于传统的动态软件测试。 传统的基于用例的软件测试都需要将测试用例输入到执行程序中，然后再判 断结果的正确性。由于需要编译运行程序，所以在进行测试开发时需要书写额外 的驱动程序，这样的做法增加了程序员的负担【2 。 另一方面，对于自从二十世纪六十年代开始就进行研究的程序验证技术，已 经涌现了各种理论和方法。但是由于程序验证要求通过推理或者穷举的手段来判 定程序的行为是否符合规约，而程序设计语言的复杂性又使得程序的复杂性随着 程序的规模呈指数级增长，因此程序验证目前只用于证明一些关键的核心模块的 正确性而没有得到更广泛的应用1 2 j 。 动态测试通过考察尽可能多的测试用例来保证程序的质量。程序验证则希望 通过逻辑推理和计算判定程序是否正确。这两种手段，一种通过穷举所有可能来 验证程序的正确性，而另一种则通过高度的抽象考察程序的正确性。由于程序设 计语言及软件的复杂性，这两种方法都不能很好地解决实际中普遍存在的问题 2 0 l o 为了解决这个问题，在上个世纪七十年代，c l a r k e 等人提出了静态分析的方 法【2 l 】。目前，程序静态分析的研究是软件工程研究的一个热点，也已经有很多 产品面世。静态分析是介于动态测试和程序验证之间的一种方法：与动态测试相 比，它不运行程序，而是静态地分析源代码，对程序的某些属性进行考察；与程 序验证相比，静态分析不要求程序完全正确，而是尽可能地发现程序中的错误。 b a s i l i 和s e l b y 的实验结剁2 2 】表明，静态分析在错误发现率上可以达到动态 测试的水平，而在测试效率上动态测试会远远低于静态分析。但这并不表明可以 用静态分析取代动态测试，因为动态测试的稳定性和可靠性还是高于静态分析。 所以可以得出结论，静态分析作为动态测试的补充手段，能够在程序运行前发现 隐含的错误，提高程序的可靠性和健壮性。 目前提出的各种静态分析技术试图在精确性和可扩展性之间做出平衡。采用 类型推导和抽象解释的方法，分析结果不够精确；采用定理证明的方法，由于算 法复杂性的限制，很难处理实际应用中的大规模程序；将符号执行和约束求解结 合在一起，路径的选择会存在性能问题【2 】。 由于c 忿+ + 语言天生的不安全性和广泛使用，c c 针的静态分析显得尤为重 要。随着静态分析技术的发展，在现有的c c + + 静态分析工具中，过程内分析已 经发展得较为完善。而大部分缺陷却存在于过程之间的交互中，所以过程间分析 成为静态分析中的热点。 2 第1 章引言 1 1 2编译器与静态分析 编译器技术一直是程序分析技术的基础，编译器中原本用于优化的控制流分 析、数据流分析等技术都成为程序分析中的利器。 但是，静态分析中的程序分析和编译器实现以及软件逆向工程中的程序分析 有所不同。编译器实现中需要的程序分析以优化为e l 的，着重于具体数据的别名、 依赖关系等底层信息的分析；逆向软件工程则以分析软件的体系结构为目的，在 函数的抽象层次上进行分析；静态测试巾的程序分析介于两者之间，他既需要考 虑编译器实现的底层细节，又需要对程序的总体有一定的认识。 然而在现有的静态分析工具中，存在程序分析技术和程序分析算法与编译器 内部框架耦合的问题：一方面，各种程序分析算法在不同编译器内部重复设计和 实现：另一方面，编译器框架缺少同时支持静态分析和动态分析的能力。 要解决这个问题，需要找到一个合适的编译器框架，在这个框架内可以实现 静态分析与编译器内部的分离。本文为解决这一问题做了一些尝试。 1 1 3c ia n g 编译器的发展 c l a n g 诞生于2 0 0 6 年6 月，作为新一代“l l v mn a t i v e 的c 语言家族编译 器，被苹果公司在l l v m 中用来替代原来的g c c 编译器。 c l a n g 采用先进的开源开发模式，并继承了l l v m 的模块化结构。对于c l a n g ， 开发者希望能够支持这几个特殊的需求：静态分析、漏洞发掘、重构、交叉引用、 增量编译。如果需要在c l a n g 上构建一个c 或者o b j e c t i v ec 的工具，可以遍历 语法树或者控制流图，也可以使用内建的数据流分析。 到现在为止，c l a n g 已经基本上实现了对c 、o b j e c t i v ec 的支持。c 和o b j e c t i v e c 的语法分析：大部分完成，缺少v l a 的细节，已经可以顺利地分析巨大量的 代码；c 和o b j e c t i v ec 的代码生成：可以用l l v m 的代码生成编译大部分c 程 序，计划在2 0 0 9 年完成对c 和o b j e c t i v ec 的支持；c + + 的语法解析：已经可以 分析名字空间、类以及内联函数，缺少大量的内容，但正在进行之中。 可以从c l a n g 的官方网站h t t p ：c l a n g 1 l v m o r g 获得c l a n g 的基本信息、内部 特性、设计思想，但是并没有详细的设计文档可供参考。如果需要对c l a n g 进行 系统的研究，可以通过s v n 从官方服务器获得l l v m 和c l a n g 的源代码( c l a n g 中使用了l l v m 实现的库) 。编译得到c l a n g 之后，可以通过运行和调试来进一 步研究c l a n g 的设计。 3 第1 章引言 1 2本文研究内容和贡献 作者在攻读硕士研究生学位期间，参与导师蒋凡教授组织的一系列“t t c n 3 测试平台”研发活动，并先后从事其中的耶r c n 3 和a s n 1 编译器开发工作。 在三年时间中，对编译器整个流程( 词法分析、语法分析、静态语义检查、代码 生成) 的开发过程，以及编译器的内部实现( 符号表设计、语法树设计等) 有了 深刻的理解。从实践中获得不少经验，同时在实践中通过“需求分析 一“概要 设计 一“详细设计 一“代码编写 一“软件测试 一“b u g 修复 一“版本 发行 等一系列的软件开发过程。 本文的主要工作与贡献有： 1 本文在深入研究过程间分析技术的基础上，并结合对国内为已有的静 态分析工具的调研工作，总结出过程间漏洞分析的基本算法。 2 对开源编译器c l a n g 的架构进行了分析，给出了c l a n g 驱动模块和静 态分析模块的设计方案。 3 提出了在c l a n g 上实现过程间分析工具的方案，方案中采用的函数分 析顺序策略、路径分析策略、模型生成策略，一方面使得过程间分析 在c l a n g 的架构下可以正常进行，另一方面保证了过程间分析工具在 性能上的要求。 4 按照上述的过程问分析方案，实现了一个原型系统s i m p l e i p a ，验证 了方案的可行性和有效性。 1 3本文章节组织 本文大致分为4 章： 第一章，阐述了论文的研究背景和主要内容，并对论文结构做简要介绍。 第二章，介绍了常见的软件安全漏洞，并给出了一种针对静态分析的漏洞分 类方式。 第三章，概括介绍了静态分析技术的用途和技术内幕，其中重点探讨了过程 间分析技术和过程间漏洞发掘，并对p r e f i x 静态分析工具进行调研。 第四章，调研l l v m 编译架构以及c l a n g 编译器的背景，对c l a n g 的系统设 计以及c l a n g 静态分析器的架构进行细致的分析。 第五章，s i m p l e i p a 原型系统的设计和实现，从s i m p l e l p a 的设计需求开始， 给出了s i m p l e l p a 原型系统的总体框架，重点介绍了从控制节点创建到模型生成 等过程间分析实现的相关算法。 4 第l 章引言 第六章，总结全文，展望下一步的工作。 1 4术语与缩写 本节对文中用到的静态的基本术语和缩写加以介绍，方便后续。文字内容中 尽可能使用术语的中文翻译，表格和图中则一般使用缩写或英文方式。 i p a i n t e r - p r o c e d u r a la n a l y s i s ，过程间分析 姗 l o wl e v e lv i r t u a lm a c h i n e ，低层次虚拟机 c l a n gl l l i m 的c 语言族编译器 a s t 抽象语法树 s i m p l e i p a基于c l a n g 架构实现的过程间分析工具原型 c f g 控制流图 5 第2 章软件安全漏洞 第2 章软件安全漏洞 图2 1 是软件开发周期中的一些安全实践，将这些实践应用到软件工程中对 应的环节，能极大的提高软件的安全性【6 l 。 图2 1 软件开发周期中的安全实践 本文关注的是源代码层次的软件安全漏洞。代码层次的软件安全漏洞是非常 普遍和常见的，几乎一半的软件安全漏洞都是在代码层次上引入软件系统的【7 1 。 本章首先对软件安全漏洞进行概述，并针对代码级别的安全漏洞进行分类总结。 2 1软件安全漏洞概述 如今对于安全漏洞有多种不同的形式，但它们的本质基本是一致的。 r f c 2 8 2 8 e 8 】中如是说，安全漏洞是计算机系统在硬件、软件、协议的具体实现或 系统安全策略上存在的缺陷和不足。漏洞一旦被发现，可以被恶意攻击者用来突 破系统的安全策略，从而在未授权的情况下访问资源和数据或破坏系统，从而导 致危害计算机系统安全。 由于漏洞具有逻辑性、持久变化性、和环境密切相关等特点，为了达到漏洞 描述的完整性，在对漏洞进行研究时，除了要掌握漏洞本身的特征属性，还要了 解与漏洞密切相关的其他对象的特点。漏洞的基本属性包括：漏洞类型、造成的 后果、严重程度、利用需求、环境特征等。与漏洞相关的对象包括：存在漏洞的 软件、操作系统、相应的补丁程序和修补漏洞的方法等。 2 2软件安全漏洞分类 对软件安全漏洞从不同角度和层次进行分类，有助于更好的把握漏洞的共 性，从而更好地进行漏洞的分析和检测。恰当地定义软件安全漏洞分类机制，能 够帮助研究人员和实际人员更好的理解问题本身，并设计开发出自动化或半自动 6 作 一 一 l缱上贼一山声 析 一果一 试 |一l一一一一。沙 嗣怔糟 一 斤 _ l擎一竺l哗匝 始i 一 啊1|囊卜 点乒 ，j 析 计一 查 1一；一一，一。沙 风 一架一 外 ，j 1 0 山卤i 甲 第2 章软件安全漏洞 化的工具。 过去的几十年里，研究人员已经提出了各种各样的漏洞分类方法。在文献 2 3 】 中，b i s h o p 对已有的漏洞分类方法进行了深入的分析，并且得出的一个重要结论： 不存在最好的漏洞分类方法，不同的分类目的就会有不同的最优分类方法 2 4 j 。 非赢利调研机构m i t r e 和美国系统网络安全协会( s a n si n s t i t u t e ) 曾对通过 安全专家对常见的软件编程错误进行筛选，公布了二十五种软件漏洞：输入验证 漏洞、不正确的编码或转义输出、维持s q l 查询结构( s q l 注入) 错误、维持网 页结构( 跨站点脚本) 错误、维持操作系统命令结果( 操作系统命令注入) 错误、明 文传送敏感信息、跨站点请求伪造、资源竞争( r a c ec o n d i t i o n ) 、错误信息泄露、 限定缓冲区内操作失败、外部控制重要状态数据、外部控制文件名或路径、不可 信搜索路径、控制代码生成错误( 代码注入) 、下载未经完整性检查的代码、错误 的资源关闭或发布、不正确的初始化、错误计算、可渗透防护、使用被破解的加 密算法、硬编码密码、对核心资源的错误权限分配、随机值的错误利用、滥用特 权操作、客户端执行服务器端安全。 针对上述二十五种常见的软件安全漏洞，进行了如下的归纳分类。在下面这 些漏洞的检测中，静态分析技术十分有效且应用广泛。 2 2 1输入验证 输入验证的内容包括三部分内容： 验证所有的输入 验证各种来源的输入 建立可信边界 输入验证的常见方法有黑名单法、白名单法和间接选择法，其中间接选择法 的安全性高于白名单法，而白名单法高于黑名单法。然而仅仅具有这些方法是不 够的，在不同软件安全级别的要求下，需要根据不同的验证策略( 例如默认执行 正确输入验证、限制数值输入等) 选择相应的方法对输入进行验证。 元字符攻击问题是输入验证问题中最重要的一类( 元字符是指输入语言中具 有特定含义的字符或者字符串) ，常见的元字符攻击问题包括s q l 注入、路径操 纵、日志欺骗等。 2 2 2 缓冲区溢出 近二十年来，缓冲区溢出无疑是软件安全中最严重的问题。直到2 0 0 5 年， 在c e r t c c 的报告中缓冲区溢出漏洞占有的比重是最大的，1 9 9 9 年占到5 0 以 7 第2 章软件安全漏洞 上，2 0 0 2 年占到5 7 之多。闻名于世的蠕虫冲击波、震荡波等就是利用缓冲区 溢出来达到攻击目的的【9 】。 当应用程序将数据写入到所分配的内存区以外时，就会发生缓冲区溢出。存 在缓冲区溢出漏洞的应用程序往往会给攻击者提供很大的控制权。 缓冲区分配策略一般分为静态缓冲区分配和动态缓冲区分配。无论采用哪种 缓冲区分配策略，跟踪缓冲区大小都是程序分析时必需的工作。但是在c c + + 中，除了简单地返回字符串长度以及已分配堆栈的变量以外，没有多少手段来跟 踪缓冲区大小。 按照安全级别的高低，进一步对容易造成缓冲区溢出漏洞的字符串操作进行 分类： 天生危险的函数：许多c 字符串函数很容易被错误使用，应该完全避免 使用这些函数，例如g e t s o i 蚕i 数、s c a n f o 函数、s t r c p y o i 累i 数等。 有界字符串操作：引入有边界限制的函数后，可以在程序中消除一些天 生危险函数造成的简单缓冲区溢出漏洞，但这些函数也不是最佳选择方 案，例如s t r n c p y o 函数、s t r n c a t o 函数。 更完善的字符串类和类库：一些可以在字符串处理程序中消除绝大部分 缓冲区溢出漏洞的字符串类库，例如s t d ：s t r i n g 、s a f e s t r 。 2 2 3 缓冲区溢出伴随的问题 不是每一次缓冲区溢出都是由字符串操作错误引起的，所以明智地采用安全 性更好的字符串操作函数也不能预防每一次缓冲区溢出。 2 2 3 1 整数 当一个整数值大于或小于其范围时，就会产生整数溢出错误。整数溢出错误， 常常就是攻击者致使缓冲区溢出的起点。许多情况下，缓冲区溢出都与数字有关， 因为内存分配量、字符串操作长度都是用数字表示的，数字还常用于计算变质内 存的偏移量。 常见的整数溢出错误类型： 回绕错误：当一个整数值大于或小于其数据类型所规定的范围时，就会 发生回绕错误。 截断和符号位扩展：当数据从一个位数较多的整数类型转换为一个位数 较少的数据类型时，就会发生数据截断错误。 8 第2 章软件安全漏洞 有符号数和无符号数之间的转换：有符号和无符号数据类型都有相同的 位数，但是两种类型所表达的数值仅有部分重叠。 对于整数溢出问题，检测和防止整数溢出的方法包括限制用户的数字输入、 重视编译器警告、确定导致溢出的运算符的前提和后置条件。 2 2 3 2 运行时保护 保护缓冲区溢出的最好方法是，使用类型安全、内存安全的编程语言来编写 程序。 对于动态缓冲区溢出进行保护，可以采用诸如编译时工具、虚拟执行环境、 更健壮的系统类库等方法改变程序的二进制表示或运行环境。但是这些流行的保 护类型也不能防止大量典型的入侵，只是增加了攻击者进行攻击的难度。 2 2 4错误与异常 一般情况下，程序员没有完全考虑错误条件和异常情况，而是更多地考虑那 些期望的情况，这种忽略使得攻击者可以遵循一条自然的错误和异常发生路径来 实现攻击。 下面是几类常见的错误与异常问题。 利用返回代码处理错误：容易忽略错误，将错误处理代码和错误信息链 接在一起，使得程序不好理解。 管理异常：异常机制使错误处理更容易正确执行。如果要忽略一个已检 测的异常，需要编制专门的代码才能忽略。 防止资源泄漏：未能释放资源可能会导致严重的性能问题，当程序遇到 一个错误或者意外条件时，资源泄漏很容易发生。想要解决这种问题， 需要建立资源管理体系。 日志记录与调试：良好的日志记录和调试策略可以使得识别、处理错误 并从错误巾恢复正常变得更加容易；拙劣的日志记录和不安全的调试代 码可能会使应用程序更容易遭受攻击。所以必须确保日志存储在远程用 户不能访问的地方，同时确保从产品系统中清除调试代码、“后门”访 问代码和特意隐藏的“复活节彩蛋 。 9 第3 章静态分析及过程问分析技术 第3 章静态分析及过程间分析技术 程序静态分析是在程序运行前发现软件漏洞的主要手段之一。本章首先概括 介绍了静态分析的技术路线和常用的方法与理论，给出了一些静态分析工具的调 研结果分析。接着重点探讨了过程问分析技术和过程间漏洞发掘技术。最后对 p r e f i x 静态分析工具的设计思路进行详细的分析。 3 1静态分析技术 3 1 1静态分析概述 术语静态分析( s t a t i ca n a l y s i s ) 是指在不执行的情况下对代码进行评估的过 程。静态分析非常强大，这是因为它允许对多种可能性进行快速考量。一个静态 分析工具能够探查大量“如果将会”的假定情况，而不必为所有这些假 定进行计算，进而执行这些代列6 1 。 静态分析技术非常适合于识别安全问题： 静态分析工具彻底而一致地进行检查，而不管程序员的检查角度和代码 的复杂程度。 通过对代码本身的检查，静态分析工具往往能指出安全问题的根源，而 不仅仅是指出某种症状。 静态分析能够在开发早期发现错误，甚至，在程序首次运行之前就可以 发现。及早发现错误，不仅仅减少了修补错误所付出的费用，而且这种 快速反馈周期可有助于。 当安全研究人员发现一种新攻击时，静态分析工具可以很容易地对大量 代码进行重新检查，从而将了解这种新的攻击能不能针对这些代码而成 功实施。 对于静态分析技术，最普遍的不满意见是：这些工具产生太多的无用信息， 尤其是产生太多误报( 当程序中实际不存在问题时，却报告了问题) 。但是从安 全的角度来看，漏报( 程序中存在问题。而安全分析工具却没有报告这个问题) 的问题更为严重。误报的代价是对报告结果的审查浪费时间，但漏报的代价就远 1 0 第3 章静态分析及过程间分析技术 远不止这些。 3 1 2静态分析用途 静态分析的用途比大多数人所了解的要更为广泛，下面对这些用途进行一个 简单的分类： 类型检查：最为广泛的静态分析的应用形式，也是大多数程序员熟悉的 形式。类型检查将消除全部类别的编程错误。不过，类型检查捕获错误 的能力有局限性，而且也有漏报和误报的问题。 风格检查：比起类型检查程序，风格检查程序强制执行的规则更加挑剔， 也更加注重表面的东西。纯粹的风格检查程序强制执行的规则和空格、 命名、注释、程序结构等这类东西相关。随着时间的推进，某写编译器 已经实现了可选的风格检查功能。 程序理解：帮助用户搞懂代码库中的大量代码。集成开发环境一般至少 都包含有某些程序理解功能。高水平的程序理解工具将努力帮助程序员 洞察程序运转之道。 程序验证及属性检查：程序验证工具接受一份完整描述程序的规格说明 和一份代码，而后尝试证明该代码忠实实现了这份规格说明。而属性检 查根据只描述部分程序行为的部分规格声明对程序进行检查。 b u g 查找：指出程序以程序员设想之外的方式运转的一些地方。高级的 b u g 查找工具可以通过代码本身推断出需求而扩展其内建的模式。 安全审查：现代安全分析工具往往更像是一种属性检查程序和b u g 查找 程序的混合体。但是，安全工具一般不能像b u g 查找工具通过允许漏报 来减少误报，而是应该倾向于另一个极端：即使该工具并不能证实某些 代码表现出的可被探测并利用的漏洞，也应告警并指出这些代码应该进 行人工审查。 o 1 3静态分析技术路线 本节介绍静态分析工具内部的工作流程，包括数据结构、分析技术、规则以 及报告结果的方式等，了解这些技术路线对于创建自己的静态分析工具有重要的 第3 章静态分析及过程问分析技术 帮助。 图3 1 所示的流程图说明了所有针对安全的静态分析工具的工作方式。 图3 1 静态分析漉程 3 1 3 1 建模 静态分析工具需要做的第一件事情，就是将要分析的代码转换为一种程序模 型，即一组代表此代码的数据结构。通常情况下，静态分析工具都会借用大量来 自编译器领域的技术来完成建模的过程。 在编译器和静态分析过程中，会共用下面这几种重要的技术： 词法分析：将代码转换为一系列的记号，并沿途丢掉程序文本中那些不 重要的部分比如空白或者注释。 语法解析：使用一种与上下文环境无关的语法来匹配上述的记号流，然 后生成一颗解析树。 抽象语法：准确说这是一种数据结构，称作抽象语法树。它提供了一种 适合于后期进行分析的标准化的程序版本。 语义分析：在编译器领域，包括符号分析和类型检查。对于面向对象语 言，类型信息是至关重要的，所以高级静态分析工具不得不像编译器那 样完成相关的工作。 跟踪控制流：当函数执行时，需要探究其可能采取的执行路径，所以多 数工具会在抽象语法树或者中间表示之上生成一个控制流图。 跟踪数据流：数据流分析通常包括遍历某个函数的控制流图，其中将函 数变换为静态单一赋值形式，对数据流分析有益。 污染传播；使用数据流来判断攻击者能够控制的值。 指针别名歧义：了解哪些指针可能会指向同一个内存地址。 为需要分析的程序选择一种合适的表示法( 建模) ，从而可以在精确度和伸 缩性之间做出较好的折中。 1 2 第3 章静态分析及过程间分析技术 3 1 3 2分析算法 任何高级分析策略都至少由2 个主要部分构成：一个用来分析单个函数的过 程内分析组件，另一个用于分析函数间交互行为的过程问分析组件。 断言检查：许多安全属性都可以作为断言进行陈述，对于要保护的程序 来说，这些断言必须是真的。通过将检查工具与要检查的事情分离开来， 分析工具可以迅速适应对新类型问题的查找，或者可以防止将不是问题 的内容当作问题来报告。 过程内分析：分析单个函数的策略，又称为本地分析。它推动着静态分 析工具向着一种降低精确度而进行更为可靠的分析的方向发展。当前较 为流行的分析方法包括抽象解释、谓词转换、模型检查等。 过程间分析：分析函数间交互行为的策略，又称为全局分析。具体的过 程间分析技术将在3 2 节进行详细研究。 针对不同的漏洞，需要选择能够发现目标缺陷的算法。使用高级静态分析算 法的动机是为了提高上下文环境敏感度判断特定代码在何种环境和何种条 件下运行。更好的上下文环境敏感度能够更好地评估目标代码带来的危险。 3 1 3 3 规则 优秀的静态分析工具是规则驱动的。规则告诉分析引擎如何对环境以及库文 件和系统调用的影响进行建模。规则还定义了静态分析工具将据此检查的安全属 性，甚至程序文本中未明确包含的程序行为。 优秀的静态分析工具会尽可能在程序外部实现其检查所需的规则，这样用户 可以方便地添加新的规则来建立新的库文件或者环境的模型，从而检查新的安全 属性。 常见的规则文件格式包括批注、专用的规则文件、程序查询语言等形式。由 于很多安全问题都可以表示为污染传播问题，所以用于污染传播的规则是一种经 典的规则描述。它包括源规则、接收器规则、传递规则、净化规则、入口点规则 等几种类型。 3 1 3 4 报告结果 分析器的结果应该能够使用户对结果的正确性和重要性做出判断，而且能够 采取适当的纠正行动。 作为理想的输出，分析工具的结果必须完成以下三部分工作： 结果的分组和分类：如果能以一种灵活的方式对问题进行分组和分类， 第3 章静态分析及过程问分析技术 那么可以消除大量非预期的结果，而无须逐一对每个问题进行审查。 消除非预期的结果：所有的高级静态分析工具都提供了用来抑制结果的 机制，这样在后续运行的分析中，前面报告过的问题将不会再进行报告。 解释结果的意义：优秀的b u g 报告应该包括问题的描述、影响范围、重 要性、重现方法，即静态分析工具必须解释他所识别出来的问题的风险， 并说明在某种漏洞利用方面的潜在影响。 3 1 4 静态分析方法与理论 在静态分析工具的构建中，经常采用符号执行、定理证明、类型推导、抽象 解释等具体的方法和理论。这些方法和理论并不完全独立。一个静态分析工具常 常需要使用多种方法以取得最佳效果。 3 1 4 1符号执行 符号执行的基本思想是，用抽象的符号表示程序中变量的值来模拟程序的执 行。该方法很好地克服了在静态测试时不能确定程序中变量的值的问题，符号执 行常常在对路径敏感的程序分析中使用【10 1 。 用符号执行加约束求解进行程序分析的基本思想是：用h o a r e 逻辑将程序进 行抽象表示，在程序的符号执行过程中由前置条件出发，结合程序中的约束条件 推导出新的约束条件，最终得到程序的后置条件。如果存在一组输入使运行程序 的结果和规约不符，那么在程序规约正确的前提下，程序中必定包含错误。 符号执行和约束求解方法的优点在于它可以精确地静态模拟程序的执行。由 于它跟踪了变量的所有可能取值，因此能够发现程序中细微的逻辑错误。但是在 处理大程序时，程序执行的可能的路径数目随着程序尺寸的增大而星指数级增 长。在这种情况下就需要对路径进行选择，选取一定数量的路径进行分析。 3 1 4 2定理证明 自动定理证明是基于语义的程序分析特别是程序验证中常用到的技术。但是 采用消解原理的定理证明器一般并不适合于程序分析，因为它不太方便处理整数 域、有理数域上的运算。在这种情况下，人们常用各种判定过程来判别公式是否 为定理。为了能够对包含数学运算以及函数的更复杂的合取式进行推导，n e l s o n 和o p p e n 川提出了所谓的协同判定过程，该方法能处理的公式中可以有抽象函数 符号以及带大于号、小于号的不等式。 1 4 第3 章静态分析及过程间分析技术 3 1 4 3 类型推导 类型推导指的是由机器自动地推导出程序中变量和函数的类型，它在函数式 程序设计语言中有着广泛的应用。其基本思想是，程序中的数据可以依照一定的 规则划分为不同的集合；如果把每一个集合作为一种类型，就可以利用类型理论 中的一些算法进行分析。 类型推导适用于控制流无关的分析，具有很好的可扩展性，能够处理大规模 的程序。但是它不能解决所有的问题，对于和程序控制流紧密相关的特性则需要 引入予类型的概念，来描述类型间的包含关系。 3 1 4 4 基于规则的检查 在面向不同应用的程序中，常常隐含着各种不同的编程规则。采用基于规则 进行分析的系统的结构是：首先由一个规则处理器处理规则，将其转换为分析器 能够接受的内部表示，然后再将其应用于程序的分析。基于规则的分析方法的优 点是能够依据不同的规则对不同的系统进行分析，发现大规模程序中的潜在错 误。缺点是由于受到规则描述机制的局限，只能分析特定类型的错误。 3 1 4 5 模型检测 模型检测是一种验证有限状态的并发系统的方法，基本思想是对于有限状态 的系统构造状态机或者有向图等抽象模型，再对模型进行遍历以验证系统的某一 性质。模型检测的难点在于如何避免状态空间爆炸。 模型检测在硬件检测和协议验证方面已经有了很好的应用。然而对于软件检 测，由于软件本身具有的高复杂度，该方法只能针对程序中的某一方面特性构造 抽象的模型进行检测。 3 1 5 静态分析工具 本节介绍当前在程序静态分析方面的一些研究工具。 3 1 5 1p r e f i x p r e f i x 使用符号执行及约束求解方法对c c + + 程序进行静态分析测试。 p r e f i x 的工作流程是：首先分析源代码，将其转换成抽象的语法树，然后对过 程依照调用关系进行拓扑排序，再为每个过程生成相应的抽象模型，最后静态模 拟执行路径并用约束求解的方法对约束集合进行检测。用p r e f i x 对a p a c h e 、 m o z i l l a 等程序进行检查，发现了其中存在的数百个错误和安全隐患。 第3 章静态分析及过程间分析技术 3 1 5 2m e t a i m e t a l 是基于规则的程序静态分析检测工具f 馕。m e t a l 将程序的规则以状态 机的形式进行描述，然后对程序依照规则进行分析。m e t a l 对l i n u x 内核、f l a s h 等程序进行了检查，发现了其中隐含的不少错误。 3 1 5 3e s p e s p 也是一种基于规则的系统1 3 1 。它使用了多种策略，包括保守别名分析、 数据流分析以及路径敏感的符号执行。e s p 被用于检查g e e 中使用的cs t r e a m 库 的某些性质的正确性。e s p 着重于过程间程序分析，而m e t a l 侧重于过程内的程序 分析。