（计算机科学与技术专业论文）td类漏洞及死锁检测系统的设计与实现.pdf

一 独创性( 或创新性) 声明 木人声明所呈交的论文是木人白：导帅指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特1 1 ) j l 以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也1 i 包含为获得北京邮电人学或其他 教育机构的学位或证书而使用过的材料。与我一蚓工作的 划志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论义与资料若有1 i 实之处，本人承担一切相关责任。 本人签名： 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识广：权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅：学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围， 本人虢当牡 导师签名： 适用本授权书。 日期： 塑丝：! ：墨 日期：墨竺! ! ：塑 污染数据和死锁安全漏洞检测方法的设计与实现 摘要 网络应用已渗透到社会的各行各业，网民对网络安全的要求也日 渐提高，网络安全逐渐成为了各界日益关注的焦点。网络应用的本质 是软件，因此软件的安全问题是网络安全的核心。如何在软件发布前 检测并排除软件中所存在的安全漏洞、提高软件的稳定性、降低软件 的风险已经成为了一个新的研究课题。 一 一 针对上述问题，本文就软件安全问题中两类典型的安全漏洞 污染数据和死锁的检测方法进行了深入的研究，并详细描述了污染数 据类安全漏洞检测系统与死锁检测系统的设计与实现。 本文具体的研究工作主要包括以下几个方面。首先对污染数据和 死锁的检测方法进行深入调研，并总结了现有方法的优缺点。就污染 数据检测方法而言，现有的检测方法因为不具有路径敏感的性质，因 此存在较多的误报。就死锁的检测方法而言，当前的静态分析技术皆 不能对死锁检测这一问题进行直接求解。其次，本文在现有的检测方 法的基础上进行了改进，一方面，设计并实现了路径敏感且上下文敏 感的污染数据检测系统，另一方面，提出了一种新的死锁检测框架， 该框架将死锁检测这一复杂问题分解成为四个子问题，进而通过现有 的静态分析技术可达分析、别名分析、并发分析、以及g a t e l o c k 分析对这四个子问题独立求解。最后，以s o u r c e f o r g e 网站上下载排 。 名最前的七个开源软件作为污染数据检测系统的测试集，将本方法的 检测结果与另一款静态分析软件k l o c w o r k 的检测结果进行了比较。 通过比较结果可知，本文所提出的污染数据类安全漏洞的检测方法在 误报率与漏报率这两项评估指标上都优于k l o c w o r k 。 本文的研究成果对死锁检测问题提供了一个新的研究思路，具有 一定的理论意义和应用价值，为污染数据类安全漏洞的检测，提供了 有益的方法和手段j 关键词污染数据死锁静态分析数据流分析别名分析 k l o c w o r k 北京邮i 【i 人学顾 ：学位论义a b s t t a c t r e s e a r c ha n di m p l e m e n t a t i o no ft h e d e t e c t i o nme t h o df o rt a i n t edd a t aa n d d e a d l o c k a bs t r a c t w i t hw i d e s p r e a du s eo fw e b a p p l i c a t i o n s t h ep r o b l e mo fn e t w o r k i n g s e c u r i t yh a sb e e n a t t a c h e db i gi m p o r t a n c eb yt h ep u b l i c ，a n d i th a s b e c o m ean e wr e s e a r c hf i e l do nh o wt od e t e c ts e c u r i t yv u l n e r a b i l i t i e s i n v o l v e di ns o f t w a r e a n dh o wt or e d u c et h er i s ko fs o f t w a r e t a i n t e dd a t a ( t d ) a n dd e a d l o c ka r et w ot y p i c a lt y p e so fs e c u r i t y v u l n e r a b i l i t i e s t oa d d r e s st h e s ep r o b l e m s ，t h i st h e s i sd o e ss o m er e s e a r c h o nt h e m ，a n dd e s c r i b e st h ed e s i g na n di m p l e m e n t a t i o no ft h ed e t e c t i o no f t da n dd e a d l o c ki nd e t a il t h em a i nc o n t e n ta n dc o n t r i b u t i o no ft h i sp a p e ra r el i s tb e l o w f i r s t l y , t h i s t h e s i ss u m m a r i z e st h ea d v a n t a g e sa n dd i s a d v a n t a g e so f e x i s t i n ga p p r o a c h e so nd e t e c t i o no f t da n dd e a d l o c k t h ee x i s t i n gs t a t i c d e t e c t i o nm e t h o d so nt 】da r em a i n l yp a t h i n s e n s i t i v e s oi tm a yc a u s ea l a r g ea m o u n to ff a l s ep o s i t i v e s w h i l e c u r r e n td e t e c t i o no fd e a d l o c k c o u l dn o td i r e c t l ys o l v et h i sc o m p l e xp r o b l e me f f e c t i v e l y s e c o n d l y , t h i s t h e s i sr e f i n e st h ee x i s t i n gm e t h o d s ad e t e c t i o ns y s t e mf o rt d w h i c hi s p a t h - s e n s i t i v ea n dc o n t e x t s e n s i t i v e ，i sd e s i g n e da n di m p l e m e n t e d ，a n da n e wf r a m e w o r ko fd e a d l o c k sd e t e c t i o ni s d e s i g n e d a sw e l l t h i s f r a m e w o r kd i v i d e st h ec o m p l e xp r o b l e mo fd e a d l o c kd e t e c t i o ni n t of o u r s u b p r o b l e m s ，w h i c hc a nb ed i r e c t l ys o l v e db ye x i s t i n gs t a t i ca n a l y s i s t e c h n o l o g i e s ，i n c l u d i n gr e a c h a b l ea n a l y s i s ，a l i a sa n a l y s i s ，p a r a l l e la n a l y s i s a n dg a t e l o c ka n a l y s i s f i n a l l y , t h i st h e s i sc o m p a r e st h et e s t i n gr e s u l t sw i t h a n o t h e rs t a t i c a n a l y s i st 0 0 1 k l o c w o r k a c c o r d i n gt ot h ee x p e r i m e n t r e s u l t s ，w ef o u n dt h a to u ra l g o r i t h mc o u l dr e d u c et h en u m b e ro ff a l s e p o s i t i v e sa n df a l s en e g a t i v e sm o r ee f f e c t i v e l yt h a nk l o c w o r k i nc o n c l u s i o n ，t h ea c h i e v e m e n to fo u rr e s e a r c hr e s u l t se n r i c h e st h e a p p r o a c h e so nh o wt od e t e c td e a d l o c k ，a n dh a sac e r t a i nt h e o r e t i c a la n d p r a c t i c a l i m p o r t a n c e i na d d i t i o n ，t h i st h e s i s p r o v i d e s a j l e f f e c t i v e a p p r o a c hf o rt dd e t e c t i o n k e yw o r d s t a i n t e dd a t a d e a d l o c k s t a t i ca n a l y s i s d a t a f l o w a n a l y s i s a l i a sa n a l y s i s k l o c w o r k + 2 3t d 类安全漏洞静态检测方法的研究现状1 0 2 3 1 污染传播分析算法1 0 2 3 2 基于污染传播分析算法的t d 类安全漏洞检测方法1 2 2 4 死锁静态检测方法的研究现状1 3 2 4 1 基于类型系统的死锁静态检测方法1 4 2 4 2 基于数据流分析的死锁静态检测方法1 4 第三章t d 类安全漏洞检测系统的设计与实现1 5 3 1t d 类安全漏洞概述1 5 3 1 1t d 类安全漏洞例子及分析1 5 3 1 2t d 类安全漏洞建模。16 3 2t d 类安全漏洞检测系统的概要设计1 6 3 2 1 总体流程图! ：1 6 3 2 2 总体架构图二? ! ? 1 8 3 3t d 类安全漏洞检测系统的详细设计，一j ：1 9 3 3 1 规则的语法1 9 3 3 2 函数语义特征牛成模块2 2 3 3 3 安全漏洞状态机分析模块2 6 3 3 4t d 类安全漏洞定义模块3 1 、学坝 学位论爻 目录 死锁检测系统的设计与实现3 7 死锁概述3 7 4 1 1 死锁例子及分析3 7 4 1 2 死锁建模：3 8 死锁检测系统的概要设计3 9 4 2 1 总体流程图3 9 4 2 2 总体架构图4 1 死锁检测系统的详细设计4 2 4 3 1 并发特征分析模块详细设计4 2 4 3 2 可达集分析模块详细设计4 6 4 3 3 别名集分析模块详细设计4 8 4 3 4 并发集分析模块详细设计5 2 4 3 56 a t e l o c k 集分析模块详细设计5 6 t d 类安全漏洞检测系统的实验数据及分析6 1 实验环境6 1 实验结果比较6 1 5 3 漏报率6 2 5 4 误报率6 3 5 5 结果分析6 4 第六章总结与展望6 5 6 1 工作总结6 5 6 2 下一步研究工作6 5 参考文献6 7 附录缩略语一7 0 致谢7 1 作暂攻读学位期间发表的学术论文目录7 2 北京邮l u 人学坝l 学位论义 第章绪论 1 1 背景 第一章绪论 网络应用已渗透到社会的各行各业，网民对网络安全的要求也日渐提高，网 络安全逐渐成为了各界日益关注的焦点。网络应用的本质属性是软件，因此软件 的安全问题是网络安全的核心。 m c g r a w 将软件安全漏洞划分为“7 种有害的领域”i lj ，其中排在第一位的 是“输入验证和表示法”。“输入验证和表示法”类型的安全漏洞是由元字符、替 代编码、以及数字表示法等所引发，可能会产生包括跨站点执行脚本、s q l 注 入、路径操纵以及许多其它的安全漏洞隐患。o w a s p ( 开放式w 曲应用程序安全 项目) 组织2 0 0 7 年公布的1 0 大w e b 应用程序安全漏洞中，排在第一的是跨站点 脚本( x s s ) ，排在第二的是数据注入攻击，包括s q l 注入、命令注入等1 2 j 。造 成这两种安全漏洞的主要原因也是没有对输入数据进行合适的验证。 “输入验证和表示法”类型的安全漏洞又称污染数据( t a i n t e dd a t a ，下文简 称t d ) 类安全漏洞。t d 类安全漏洞的检测方法大都基于污染传播算法l j j 。所谓 污染传播是指使用数据流来判断攻击者能控制的值，它需要知道信息在程序的什 么地方进入，并且怎样在程序中传送。当前所存在的t d 类安全漏洞方法要么规 则不完备，要么不具备路径敏感性或者上下文敏感性，因此存在较多的误报和漏 报。所谓误报是指软件不存在某个缺陷，但分析工具报告该软件可能存在此缺陷。 所谓漏报是指分析工具没有报告出软件中存在的安全漏洞。 此外，在现代软件开发中，并发程序以其计算资源利用率高、计算速度快等 优点得到了广泛的应用。然而，由于并发行为的复杂性以及不确定性，使得并发 程序的开发、测试与维护相对闲难，其中最为典型的并发安全问题就是死锁。而 且，随着多核处理器的广泛使用，并发程序中的死锁问题必将成为业界关注的焦 点。例如，在s u n 公司的缺陷数据库中，大约有3 ( 6 5 0 0 1 9 8 0 0 0 ) 的缺陷与死 锁相关。死锁通常可以分为资源死锁和通信死锁两类【4 j ，本文年要关注资源死锁， 即两个或两个以上的线程在并发执行时因各自需要请求的资源被它们中的其他 线程占有而相互阻塞，从而产牛了这些线程都无法继续运行下去的状态p j 。 目前，死锁的检测方法大致可以分为两类：动态检测方法与静态检测方法。 由于并发行为的不确定性，因此动态检测方法存在较多的漏报。此外，对于大多 数库函数而言，由于这些代码不能直接执行，因此动态检测方法对于库函数的死 锁检测不具有可行性。与之相对应的是静态检测方法，即在不运行软件前提下进 行死锁检测。死锁的静态检测。厅法由于具螯漏报少、适i h i f 玎广等优点而受到研究 路径分析算法，虽然具有了路径敏感的特性，但会出现路径组合爆炸的问题。本 文所提出的路径敏感的数据流分析算法，既汲取了路径敏感的优点，又避免了路 径组合爆炸这一缺点。 。 ( 2 ) 提出并设计了一种新的死锁检测框架。先前的死锁检测方法，不论是 基于数据流分析的死锁检测方法，还是基于类型系统的死锁检测方法，都是对死 锁检测这一问题进行直接求解，但是由于该问题的复杂性，当前所存在的静态分 析技术都不能对其进行直接有效的求解。本文所提出的框架将死锁检测问题分解 一成为四个子问题，并且这四个子问题可以通过当前所存在的静态分析技术来求 解。 。 i 3 论文结构 本文的组织结构如下： 第一章：选题背景剃研究内容。本章介绍了t d 类安全漏洲j 死锁对软f t ：安 2 北京邮i u 人学坝i 学位论义 第一章绪论 全所构成的威胁，并简要闸述了当前这曲类安全漏洞检测方法所存有：的不足，最 后总结了作者的研究内容。 第章：相关研究。本章首先对软件分析技术进行了概要介绍，进而对静态 分析技术进行了展开论述，尤其是数据流分析和别名分析，然后简要介绍了静态 检测方法的基本组成，最后就t d 类安全漏洞的静态检测方法与死锁的静态检测 方法的研究现状进行了较为详细的阐述。 第三章：t d 类安全漏洞检测系统的设计与实现。本章首先给出t d 类安全 漏洞的例子，进而引出对t d 类安全漏洞的定义，最后详细阐述t d 类安全漏洞 检测系统的概要设计与详细设计。t d 类安全漏洞检测系统由四个部分构成：规 则定义模块、自定义函数语义特征分析模块、安全漏洞状态机计算模块以及t d 类安全漏洞定义模决，其中所涉及的核心技术为基于函数摘要的全局分析以及路 径敏感的数据流分析。 一 第四章：死锁检测系统的设计与实现。本章具体描述死锁检测系统的概要设 计与详细设计。死锁检测系统由四个部分构成：并发特征分析模块、可达集分析 模块、别名集模块、并发集模块以及g a t e l o c k 分析模块，其中所涉及的核心技术 为别名分析。 。 第五章：实验数据及分析。本章以s o u r c e f o r g e 网站上下载排名最前的7 个 开源软件作为测试集，分别就误报率与漏报率这两项指标与另一款静态分析软件 k 8 进行了测试结果比较。 第六章：总结与展望。本章概括了本文的丰要内容，评价了t d 类安全漏洞 检测系统以及死锁检测系统的优点和不足，并给出了下一步研究工作的重点。 义 第。一章绪论 4 1 9 , 9 ；邮i u 人学坝i j 学位论义 筇二章棚哭删宄 2 1 软件分析技术概述 第二章相关研究 弟一旱个日大研九 分析技术很早就被用于数学、逻辑等方面的研究，并且逐渐被更多的学科所 采用。软件作为一门新型的学科，在研究过程中引用分析技术是十分自然的。虽 然，软件分析技术的能力是有限的，尤其是对于自动分析而言，许多问题是不可 判定的，其中最典型的例子是图灵停机不可判定问题1 7 j ，但是，对于软件领域而 言，该技术仍十分有用：高级语言的翻译过程需要分析技术，验证程序是否符合 需求规约需要分析技术，判断程序是否存在安全漏洞更是需要分析技术，等等。 文蒯8 】将软件分析定义为“对软件进行人工或者自动分析，以验证、确认或 发现软件性质( 或者规约、约束) 的过程或活动。之所以强调“性质”，是因为 分析的结果通常表示为软件是否符合或者具有某种性质( 或者规约、约束) ，而 一这种性质不是软件本身自明的。 软件分析通常是软件牛命周期活动( 例如：开发、维护、复用等) 的一部分， 因此软件分析的对象多种多样。文献1 9 1 1 分别对软件分析的一个子集进行了深入 的介绍，比如，对源代码的分析、形式化分析方法、以及以模型为中心的程序分 一析。文_ 献l8 j 在上述工作的基础上，对软件分析所涉及的书要方法进行了总结和分 类。根据分析过程“是否需要运行软件 为准则，软件分析技术被分成静态分析 技术和动态分析技术两大类，如图2 1 所示。 图2 i 静态分析与动态分析的基本过程 s 静态分析是指在不运行软件前提下进行的分析过程。静态分析的对象一般是 程序的源代码、目标码、或者设计模型。 文献8 将十要的静态分析划分为四类：基本分析、基于形式化方法的分析、 指向分析以及其它辅助分析，如图2 2 所示。 基本分析 蒡主豸募嫠 指向分析其他辅助分析 图2 2 主要的静态分析技术 ，2 2 1 基本分析技术 - - 基本分析是大多数编译器都包含的分析过程，例如语法分析、类型分析、控 制流分析以及数据流分析。语法分析是根据语法规则牛成语法树的过程。类型分 析的年要目的是进行类型检查，以检测程序中是否存在类型错误。控制流分析的 目标是牛成程序的控制流图。数据流分析是基本分析的核心，其作用是试图确定 在某个程序点关于各变量的使用或者取值情况。 冈为数据流分析是本文t d 类安全漏洞检测方法的的核心技术，所以本：1 了将 6 北京邮i 【! 人学颂i j 学位论文 第章卡f 1 关t t ) l 究 详细介绍数据流分析的研究现状。 基本的数据流分析技术由g a r yk i l d a l l 提出，该技术是一种用于收集在不同 程序点信息的技术。一个程序的控制流图被用来确定对变量的一次赋值可能传播 到程序中的哪些部分。这些信息通常被编译器用来优化程序。数据流分析的一个 典型的例子就是可到达定义的计算。进行数据流分析的最简单的一种形式就是对 控制流图的某个节点建立数据流方程，然后通过迭代计算，反复求解，直到到达 不动点1 12 1 。 数据流分析试图获得程序中每一点的特定信息。通常，在基本块( b a s i cb l o c k s ) 的界限内就可以获得这些信息，因为很容易计算基本块中的信息。在前向流分析 ( f o r w a r df l o wa n a l y s i s ) 中，一个基本块的结束状态是该基本块起始状态的一个函 数。函数由基本块内的语句的语义信息组成，一个基本块的开始状态是它的前驱 的结束状态的函数，于是就产牛了l 系列的数据流方程。对于每一个基本块b ， 其数据流方程如下： d “气= t r a n s ( 魄) m h 2 j o m p e p d ，( o u t p ) 在这里，t r a n s 6 是基本块b 的转移函数。它作用于入口状态i ，并产生 出口状态o u t b 。连接运算符j o i n 口p r e d 。将基本块b 的前驱节点的出口状态联合 起来，产牛入口状态魄。如图2 3 所示。 图2 3 数据流方程的解释图 最常用的用于求解数据流方程的方法是使用迭代算法。它由每个块的近似入 口状态信息出发。然后应用转移函数基于这些入口状态信息计算出口状态信息。 然后，使用连接运算符更新入口状态信息。最后两步将一直进行下去直至到达不 动点：即此时入口状态信息和出口状态信息都不冉改变。 一个基本的求解数据流方程的算法是循环迭代算法： 7 北京l i i 【；i u 人学f 晚i 学位论义 笫一章相关川究 声，e a c hn nd oi n n 】：= 巾； c h a n g e ：= t r u e ； w h i l ec h a n g ed ob e g i n c h a n g e = f a l s e ； 如re a c hr l n d o b e g i n 。 i fn = e n t r y t h e n m n 】- s t a r t ； e l s e 埘刀】：= u p 。p r e d ( 。) o u t p ； ：o l d o u t - o u t n ； o u t n 】= g e n n u ( i n n - k i l l n ) ； i fo u t n 】o l d o u tt h e nc h a n g e - t r u e e n d e n d 传统的数据流分析本质上是流分析，但传统的数据流分析是典型的路径不敏 感的。所谓路径敏感的分析计算了依赖于分支条件的谓蒯的不同的信息。比如， 如果一个分支条件是x 0 ，那么在条件不满足的分支，分析会假设x 0 确实成立。 为了减少静态分析所引入的误报，就数据流分析而言，传统的数据流分析存 在如下两个问题：1 ) 不可达路径判断不准确，造成不精确；2 ) 在控制流汇合节 点将不同分支的数据流信息“过早”地进行聚合，造成不精确。其中前者代表 i d e a l 和m o p ( m e e to v e ra l lp a t h s ) 的差距，后者代表m f p ( m a x i m a lf i x e dp o i n t ) 和m o p 的差距。不同学者提出了许多尝试提高数据流分析精度的方法，其中尝 试改进m f p 和m o p 的差距的包括：b o d i k 和a n i k 提出一种值重命名方案，通 过在数据流分析过程中综合值名称空间来提高数据路分析的精度，这实际上是针 对那些转换函数不满足分配率的数据流分析，试图通过m f p 分析得到m o p 信 息【8 】；a m m o n s 和l a r u s 提出一种从控制流图中分离出一个有限路径集合进行数 据流分析的方法，通过该方法来提高数据流分析的精度，本质上是通过减少分析 路径数求m o p 解以提高精度1 1 3 l ；t h a k u r 和g o v i n d a r a j a n 首先分析哪些控制流汇 合节点会降低数据流分析精度，然后通过重构这些节点处的控制流图，最后在重 构的控制流图上进行分析以此来提高精度，本质上也是试图通过m f p 分析得到 m o p 信息1 1 4 j ；- 尝试改进i d e a l 和m o p 差距的包括：h o l l e ya n dr o s e n 提出一种通过增加 一个有限的谓词集合来提高数据流分析精度的方法，将控制流上的每条边与该谓 诃集合上的一个关系相关联，如果某条路径的关系合成得到空集，则被认为是不 可达的l l s l ；b o d i k 等人提出一种低代价的基于检测静态边关联的- 畲找不可达路径 8 北京邮i 【i 人学坝 j 学位论义 第审相关埘究 万法，用于提高定义使用分析的精度1 1 6 l ；t u 和p a d u a 通过在s s a ；i ：合节点上增 加控制谓词，提出一个广泛性的s s a 方法米提高数据流分析精度1 1 7j ：d a s 等人 在模型检查的属性状态上增加程序执行符号状态信息，通过跟踪属性状态和程序 执行符号状态间的关联关系，并将其用于排除不可达路径来提高数据流分析的精 度【1 8 1 ；f i s c h e r 等人通过在数据流分析半格中元素上增加谓词信息来提高数据流 分析精度，实际上这些谓词将程序路径集合进行了划分，从另一个角度也可以认 为是记录了不同的路径信息，该信息可用于不可达路径判断。谓倒的选取基于一 种反例导向的抽象精化技术( c o u n t e r e x a m p l eg u i d e da b s t r a c tr e f i n e m e n t ) 1 9 1 。 为了尽可能的降低误报率和漏报率，本文提出了路径敏感的数据流分析方 法，通过引入可能状态集，避免了路径组合爆炸问题。在上述方法中，d a s i 懈j 方 法和本论文提出的方法相似，但是本文引入了抽象解释思想，采用变量的抽象取 值来表示属性状态条件，不可达路径就体现为属性状态条件中任意变量抽象取值 范围为空，属性状态条件相关计算更加简单和灵活。 。2 2 2 基于形式化的分析技术 基于形式化方法的分析是指在分析过程中引入形式化方法，以提高分析的准 确度，获取程序更多的性质。其中代表性的技术有模型检查、定理证明、约束求 解、抽象解释等。模型检查是通过状态迁移系统来描述系统的行为，用模态时 序逻辑公式表示系统的性质，最后通过“状态迁移系统是否是该逻辑公式的一个 模型”来判定“系统是否具有所期望的性质”。定理证明将验证问题转换为数学 上的定理证明问题来判断待分析程序是否满足指定属性1 9 l 。使用定理证明的软件 分析工具有e s c t 2 0 1 。抽象解释是指使用抽象对象域上的计算逼近程序对象域的 计算，使得程序抽象执行的结果能够反映出程序真实运行的部分信息，代表性工 具有p r o v e r i f t 引1 。 2 2 3 指向分析技术 指向分析多与指针和引用相关，通常与应用程序的某个特定性质密切相关。 这类分析一般是以基本分析( 尤其是数据流分析) 为框架，为了提高分析精度而 提出的技术。代表性技术有别名分析、指针分析、逃逸分析等。别名分析书要用 于确定程序中不同的内存引用是否指向内存的相同区域。指针分析则试图确定一 个指针到底指向哪些对象或者存储位置。逃逸分析的书要目的是计算变量的可达 边界。逃逸分析用于查找一些变量，它们只存在于为它们分配内存的方法或者线 程的牛命周期内。 9 术，而函数摘要、克隆分析技术则属于全局分析技术。 2 3t d 类安全漏洞静态检测方法的研究现状 分 间 析 技 t d 类型的安全漏洞是指，在未对外部输入数据进行验证的前提下，对该数 据进行安全敏感的使用所弓l 发的安全漏洞。所谓外部输入数据不仅仅指用户输 入，还包括：命令行参数、配置文件、从数据库检索的数据、环境变量、网络服 务、注册表值、系统性能参数、临时文件，等。安全敏感的使用是指可能会引发 系统安全的操作( 比如：执行系统命令，修改注册表等) 。t d 类的安全漏洞包括 s q l 注入、路径操纵、命令行注入、日志欺骗等。 与其他类型安全漏洞的检测类似，t d 类安全漏洞的分析算法由本地分析组 件和全局分析组件构成。 2 3 1 污染传播分析算法 。 。 - 污染传播分析算法是用来识别许多输入验证缺陷和表示缺陷的关键。污染传 播分析算法( t a i n t e dp r o p a g a t i o n ) 是指用数据流来判断攻击者能控制的值。例如， 如果一个程序包含一个可能被利用的缓冲区溢出漏洞，那么它总是会包含一条从 输入函数到有漏洞操作的数据流路径。污染传播分析算法的结构如图2 5 所示。 1 0 北京邮i 乜人学坝i 学位论义第一章午h 关埘究 图2 5 基于污染传播的静态分析算法 基于污染传播的静态分析算法首先需要定义规则，而规! j ! j 包括安全属性以及 程序行为。 安全属性规定了一系列有序的事件，要求在程序中不能发牛这些事件。如果 静态分析工具在程序中发现了违反该安全属性的情况则报告一个反例。例如：“内 存应该只释放一次”这一安全属性，可以该属性表示为一个有限状态自动机。如 图2 - 6 所示。 ， 一 f r e e ( x ( 其他操作) ( 其他操作) 图2 - 6 安全属性一一“内存应该只释放一次”的有限状态自动机 程序行为是对程序语义的抽象。例如：函数g e t p a r a m e t e r s o 返回值是污染 数据，可以抽象表示为： 就污染传播规则而言，可以划分为如下5 类【3 】： 入口规则：启动安全属性检查的规则，通常对应函数的入口点。该规则触发 一次时序安全属性检查，创建一个安全属性状态机实例，并将其初始化为s t a r t 状态。 污染源规则：定义受污染的数据进入系统的程序位置，例如 h t t p s e r v l e t r e q u e s t 的g e t p a r a m e t e r 方法。污染源规则将安全属性状态机实例的状 态从s t a r t 状态转换为t a i n t e d 状态。 污染传递规则：定义污染的数据在程序中传递和扩散。污染传递规则使当前 污染数据集合中元素增加。例如：以被污染的字符串对象作为参数调用s t r i n g 类 的t r i m 方法，那么污染会传递到t r i m 方法的返回值。 净化规则：定义污染的数据有：程序中进行了合适的检查验证后被净化。净化 规则通常表示验证条件或验证函数的调用。净化规则将一个污染埘象从污染数据 1 】 图2 7 函数调用图图2 - 8b d d 例子( x l & x 2 ) 该检测方法采用了b d d ( b i n a r yd e c i s i o nd i a g r a m ) 来描述上下文信息。 b d d l 2 3 1 是一种用于表示布尔函数的数据结构。例如：图2 8 表示的布尔函数为 x l & x 2 。通过对函数的_ 进制编码，函数调用的上下文调用信息能够表示成布尔 函数，如此便可以通过数据结构b d d 来描述上下文信息。值得注意的是，对变 量进行不同的排序，会优化b d d 的存储空间，如图2 - 9 所示。图2 - 9 所表示的 布尔函数是x i & x 2 + x 3 & x 4 ，当变量的排序不同时；b d d 所占用的存储空问也 不同。但是，找出最优的变量序列也是一个n p 问题。 北京i f f j l 【i 人学坝i 学位论义第章千 1 芙训究 x i x 2 x 3 x 4x l x 3 x 2 x 4 图2 9 不同的变量序列对b d d 存储空间的影响 该检测系统采用了d a t a l o g 语言来查询软件源代码中的安全漏洞。d a t a l o g 是一种逻辑语言，属于p r o l o g 的一个子集。d a t a l o g 可以根据已有的关系，推导 出新的关系。假设已知关系f a t h e r 为 ， ，那么可以通 过定义新的规则导出关系 g r a n d f a t h e r 。其推导规则为 g r a n d f a t h e r ：= f a t h e r x ，伊& f a t h e r 。这样g r a n d f a t h e r 的结果 为x = l i m p p a 。因此可以将安全漏洞定义成规则，通过d a t a l o g 来查询满足该规则 的元组，即满足该规则的安全漏洞。但是，该方法存在两个问题。第一，该方法 是路径不敏感的；第二，需要构造一个d a t a l o g 解析器。 由上可知，该检测方法存在如下三点不足： l 、基于克隆技术的上下文敏感分析不能应用于实际程序；2 、路径不敏感： 3 、复杂。 文献2 4 所提供的基于函数摘要的上下文敏感分析1 2 4 j 的核心思想是：首先根 据实际需求，抽象出该函数的特征信息；而后，根据函数调用图的逆拓扑序列进 行分析。该方法的缺点是针对不同的需求，需要抽象出不同的特征信息。该方法 的优点是工程实现简单，并且适用于大型的应用程序。 2 4 死锁静态检测方法的研究现状 死锁是指两个或两个以上的线程在并发执行时因各自需要请求的资源被它 们中的其他线程占有而相互阻塞，从而产牛了这些线程都无法继续运行下去的状 态。死锁的静态检测方法可以分为两大类：基于类型系统的静态检测方法【2 5 2 6 1 、 以及基于数据流分析的静态检测方法1 2 7 2 8 2 9 3 0 3 1 3 2 3 3 1 。 1 4 北京邮i u 人学帧l j 学位论义锦t 章t d 炎霞伞漏洲榆删系统的设i f 4j 实岘 第三章t d 类安全漏洞检测系统的设计与实现 本章首先给出t d 类安全漏洞的例子，进而弓l 出对t d 类安全漏洞的定义， 最后详细阐述t d 类安全漏洞检测系统的概要设计与详细设计。t d 类安全漏洞 检测系统由四个部分构成：规则定义模块、自定义函数语义特征分析模块、安全 漏洞状态机计算模块以及t d 类安全漏洞定义模块，其中所涉及的核心技术为基 于函数摘要的全局分析以及路径敏感的数据流分析。 3 1t d 类安全漏洞概述 本节首先列举_ 种非常具有代表性的t d 类安全漏洞s q l 注入，并对 s q l 注入漏洞进行具体的描述与分析。而后，通过该例子推导出t d 类安全漏洞 的定义，最后采用扩展的有限状态自动机对t d 类安全漏洞建模。 3 1 1i d 类安全漏洞例子及分析 s q l 注入( s q li n j e c t i o n ) 是一种非常具有代表性的t d 类安全漏洞。本小 节将详细定义及描述s q l 注入安全漏洞，并对其产牛原因进行分析。 s q l 注入是指恶意用户通过在输入数据中插入能影响s q l 命令语义的元字 符的一种攻击方式。用户的输入在未经验证的前提下，即被用在s q l 语句中将 会造成严重的后果，包括暴露数据库数据给攻击耆，或者恶意数据被存储到数据 库中甚至可以执行任何命令。如例3 1 所示： l s t r i n ga c c o u n t n u m b e r = r e q g e t p a r a m e t e r ( ”a c c o u n t n u m b e r ”) ； 2 s t r i n gq u e r y = ”s e l e c t 宰f r o mu s e r d a t aw h e r eu s e r i d = + a c c o u n t n u m b e r + ”： 3s t a t e m e n ts t a t e m e n t = c o n ，c r e a t e s t a t e m e n t ( ) ； 4r e s u l t s e tr e s u l t s = s t a t e m e n t e x e c u t e q u e r y ( q u e r y ) ； 上述程序通过调用方法g e t p a r a m e t e r 从程序外部获得一个用户输入的帐号字 符串，并用使用该字符串构造一条s q l 查询语句进行数据库查询。 这段代码包含了一个s q l 注入漏洞，因为从外部输入的字符串在作为s q l 查询的一部分前并没有经过合适的检查。例如，恶意用户如果输入字符串o r 1 = 1 ：一，在o r a c l e 数据库s q l 语法中，代表注释符号，因此该输入经过程序 的字符串连接处理后，最终的s q l 查询条件将成为u s e r i d = ”o r1 = 1 。这使攻击 者绕过户帐号检查获得i j i 了问所有用户数据库记录的权限。防范s q l 注入的方法 就是在使川外部输入数据之前进行合适的检查，过滤其中涉及s q l 语法的元字 图3 - 1 输入验证安全属性状态机 上述描述的具体含义如下：首先对不信任的输入数据做污染标记，并对当前 的污染数据集合进行监控；状态机的初始状态为s t a r t 状态，当程序接收了外部 不信任输入信息后则激活t a i n t 条件进入t i a n t e d 状态，并开始维护一个当前污染 数据集合；在t i a n t e d 状态下，如果对污染数据集合中所有的数据都进了合适的 检查则进入u n t a i n t e d 状态；如果将污染数据集合中任一元素用做高安全性的方 法参数则进入终结状态e r r o r ，报告一个安全漏洞问题。状态机转换过程中涉及 的污染数据集合通过数据流分析进行维护。 3 2 丁d 类安全漏洞检测系统的概要设计 本节首先详细描述了t d 类安全漏洞检测系统的总体流程，并对该流程的卓 要步骤以及所涉及的核心技术进行了简要的介绍，而后，给出了t d 类安全漏洞 检测系统的总体架构。 3 2 1 总体流程图 本文采用了模型检查的思想1 3 4 1 ，选择程序控制流图作为代表系统行为的模型 1 6 北京l l i 人学坝f 学位论义 第三章t d 炎友伞漏洲柃洲系统的设计j 实现 m ，需要检套的属性p 即为前述输入验证属性状态机。那么漏涧玲找的过程即为 检查控制流图上所有的可达路径上属性p 是否满足。 圈王国国圉 安伞属 安全属性状态 性建模 自动机 的构建 国国固回固 图3 2t d 类安全漏洞检测系统的总体流程 。t d 类安全漏洞的检测算法与2 3 节所介绍的基于污染分析的分析算法基本 相同。该算法包含三个阶段： 阶段1 ，规则的定义。该阶段的半要任务是描述安全属性以及定义预定义函 数的语义规则。安全属性规定了一系列有序的事件，要求在程序中不能发牛这些 事件。预定义函数是指标准库函数或者第三方所提供的函数包中的函数。 阶段2 ，自定义函数语义的特征牛成。该阶段的丰要任务是根据预定义函数 的语义特征牛成自定义函数的语义特征。与污染传播的规则相对应，自定义函数 的语义特征分为四类：污染源特征、汇点特征、污染传播特征以及污染净化特征。 阶段3 ，本地分析。该阶段的年要任务是在控制流图上，对安全属性状态自 动机进行数据流迭代计算，以判断是否满足安全属性的要求( 即是否存在安全漏 洞) 。 就阶段1 而言，为了提高系统的可扩展性，降低系统的漏报率，本文定义了 规则描述语法( 安全属性描述语法与预定义函数语义描述语法) ，并且设计和实 现了规则的解析模块，与规则的定义模块解耦合。 就阶段2 而言，为了降低系统的漏报率，本文采用了全局分析算