（计算机科学与技术专业论文）内存泄漏静态检测模型的设计与实现.pdf

北京邮电大学硕士研究生学位论文摘要 内存泄漏静态检测模型的设计与实现 摘要 c 程序中内存泄漏的检测是c 程序软件测试的重点和难点之一。 由于c 程序具有灵活高效的优点，从c 语言的诞生到现在，都作为 一种主流程序设计语言_ 直被广泛使用。c 语言使得用户能够直接控 制程序内存资源的使用，这对于实现运行程序的高性能或提高计算机 资源的利用率是至关重要的。但正是因为c 语言中灵活的内存管理 机制，使c 程序很容易产生内存泄漏等内存方面的程序错误。内存 泄漏故障在c 中是非常危险的，通常难以观察到的，但随着故障的 积累，程序的整体性能会下降，严重时会导致死机或异常退出。因此 内存泄漏的检测至关重要! 本文首先研究了内存泄漏检测技术的发展情况以及内存泄漏的 特征和产生原因，并分析了国内外常见的内存泄漏检测方法，包括静 态检测法、动态检测法等，并对比他们的优缺点。之后本文实现了静 态检测工具d t s c ，实现了对程序的语法分析，词法分析，生成符号 表和控制流图，并在此之上实现了对程序中各个变量的区间分析，使 得分析的准确性大大提高。之后实现了拓展性强的缺陷模式状态机， 搭建了一个针对故障的强有力的静态检测平台。然后通过研究c 语 言中内存泄漏故障产生的错误代码，总结出产生内存泄漏代码的模 式。根据这些的模式设计并实现d t s c 的内存泄漏模型，并用该模型 对c 程序进行检测。最后，本文将检测结果与国外静态检测工具的 检测结果进行比较，分析d t s c 和内存泄漏模型的优点和不足，并完 善内存泄漏模型，提出d t s c 改进方案。 关键词：内存泄漏；静态测试；区间分析；缺陷模式；状态机 硼h ed e s i g na n di m p l e m e n 咖0 n o fs 1 = 舰cm e m o r yi 甩a k d e t e c t i o nm o d e l i ti st h em o s td i f f i c u l ti s s u et od e t e c tm e m o r ye r r o r si ns o f t w a r eo fc 舡t h ec l a n g u a g eh a st h ea d v a n t a g eo ff l e x i b i l i t ya n de f f i c i e n c y , f r o mi t s b o r nu n t i ln o w , i ti st h em a i np r o g r a m m i n gl a n g u a g ew h i c hh a sb e e n w i d e l yu s e d cl a n g u a g ea l l o w su s e r st oc o n t r o lt h eu s eo fm e m o r y r e s o u r c e sd i r e c t l y , w h i c hi sv e r yi m p o r t a n tf o rh i g h p e r f o r m a n c eo rh i g n u t i l i z a t i o no fc o m p u t e rr e s o u r c e s b u tt h ef l e x i b l em e m o r ym a n a g e m e n t m a yl e a dt om e m o r yl e a k sa n do t h e rm e m o r ye r r o r s i ncp r o g r a m s m e m o r yl e a ki sv e r yd a n g e r i ti sd i f f i c u l tt ob eo b s e r v e d h o w e v e r ，w i t h t h ea c c u m u l a t i o no ff a i l u r e s ，t h e a n df i n a l l yi tw i l ll e a dt os e r i o u s m e m o r yl e a kd e t e c t i o ni sc r u c i a l ! p r o g r a m sp e r f o r m a n c ew i l lb el o w e r , c r a s ho ru n e x p e c t e d l yq u i t t h e r e f o r e f i r s to fa l l ，t h i s p a p e rr e s e a r c h e so nt h em e m o r yl e a kd e t e c t i o n t e c h n o l o g y , a n da n a l y z e st h em e t h o d so fm e m o r yl e a kd e t e c t i o n ， i n c l u d i n gs t m i ct e s t i n g ，d y n a m i ct e s t i n g ，a n dc o m p a r et h e i ra d v a n t a g e s a n dd i s a d v a n t a g e s t h e nt h ea u t h o rb u i l tt h es t a t i ct e s t i n gt o o l sd t s c ， r e a l i z e di t s s y n t a xa n a l y s i s ，l e x i c a la n a l y s i s ，s y m b o lt a b l ea n dc o n t r o l f l o wg r a p h ，b a s eo nt h e s e ，t h ea u t h o ra d d e dt h ei n t e r v a la n a l y s i so fe a c h v a r i a b l et oi m p r o v et h ea c c u r a c yo ft h ea n a l y s i s a f t e rt h a tt h ea u t h o r b u i l tu pas t a t i ct e s t i n gp l a t f o r mo nb a s i so fs t a t em a c h i n ew i t hs t z o n g e x p a n s i o n a n dt h e nb ys t u d y i n ga n ds u m m a r i z i n gt h ecl a n g u g ec o d e s w h i c hw i l lg e n e r a t em e m o r yl e a kf a u l t ，d e s i g na n di m p l e m e n tm e m o r y i i i 北京邮电大学硕士研究生学位论文 a b s t r a c t l e a km o d ef o rd t s c ，a n du s ei tt ot e s tcp r o g r a m s f i n a l l y , t h i sp a p e r c o m p a r e st h e t e s tr e s u l t sw i t hf o r e i g ns t a t i ct e s t i n gt o o l s ，a n a l y z et h e s t r e n g t h s a n dw e a k n e s s e so fd t s cm e m o r yl e a km o d e l ，a n dg i v e s s u g g e s t i o n st oi m p r o v ed t s cp l a t f o r ma n dm e m o r y l e a km o d e k e yw o r d s ：m e m o r yl e a k ；s t a t i ct e s t i n g ；i n t e r v a la n a l y s i s ；d e f e c t m o d e ；s t a t em a c h i n e 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处， 本人签名： 拯孕 本人承担一切相关责任。 日期：碓。! 圣一 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释： 本人 导师鬻啉 围 一 一 范 一二b 密叁 保 、b 肝孓抖 娇盈娟 北京邮电大学硕士研究生学位论文 第一章绪论 1 1 内存泄漏与静态测试 第一章绪论 一般常说的内存泄漏是指堆内存的泄漏。堆内存是指程序从堆中动态分配 的，大小任意的( 内存块的大小可以在程序运行期才决定) ，使用完后必须显式释 放的内存【。应用程序一般使用m a l l o c ，r e a l l o c 等函数从堆中分配一块内存，使 用完后，应用程序必须负责相应地调用f r e e 来释放该内存块，否则，这块内存在 当前进程生命周期内就不能被回收以再次使用了，就说这块内存泄漏了。 内存泄漏故障在c 中是非常危险的，通常会使程序执行速度变慢，最终使程 序因内存耗尽而崩溃。对于内存较小，而且地址空间是固定的旧机器而言，这种 问题更为严重。随着虚拟存储技术的出现，有些人会产生浪费一点内存无所谓的 观点，这是非常错误的，因为耗尽虚拟内存空间，意味着己经在实际内存中产生 泄漏。内存泄漏故障一般是难以观察到的，但随着故障的积累，程序的整体性能 会下降，严重时会导致死机或异常退出。因此内存泄漏的检测至关重要! 目前检测内存泄漏故障主要有两种方法：动态方法【2 卅和静态方法 6 , 7 1 。两者的 区别在于是否需要执行程序。需要执行程序的测试方法称为动态方法，不需要执 行程序的为静态方法。动态方法的主要缺点是只能依靠运行特定的测试用例来检 测故障，因而不能检测所有故障，只能检测测试用例覆盖到的故障。此外，动态 测试工具的执行开销也相当高，有时是不可接受的。静态方法不需要执行程序， 而是对源代码进行分析，从而找出潜在的故障。有数据表明，对软件进行静态分 析可以揭示出大部分软件缺陷。该方法没有执行开销，但要做大量的分析工作。 静态测试是软件开发中十分有效的质量控制方式之一。 静态测试的主要对象是源程序，源程序中含有大量设计信息，逻辑信息，同 时也含有程序异常的信息，对内存泄漏故障有针对性的检测，使得软件测试的目 的更加明确。通过扫描源程序，可以从中提取方法调用关系、各模块间数据交互 关系等设计信息，检测程序的结构、控制流和数据流，从逻辑的角度对程序进行 分析，发现潜在的内存泄漏i p ( i n s p e c tp o i n t ) 点。这种方法能更全面的检测出程 序中存在的内存泄漏的故障。因此静态测试，特别是针对故障的静态测试是检测 内存泄漏必不可少的一种检测方式。 北京邮电大学硕士研究生学位论文第一章绪论 1 2 课题来源及背景 本课题来源于国家8 6 3 计划重点项目“面向缺陷软件测试系统 d e f e c tt e s t i n g s y s t e m 简称d t s 。而本文中提到的d t s c 是d t s 的重要组成部分之一，主要是针 对c 程序的面向缺陷的软件测试系统。只要根据系统的要求提供描述某类故障 ( 如能存泄漏) 查找的x m l 文件，和对应的故障检测的c l a s s 文件，d t s c 就可以 检n c 语言中出现的该类故障。内存泄漏是d t s c 检测的各种故障之一，本文中 的内存泄漏的检测就是通过设计和实现内存泄漏的x m l 文件和j a v a 文件来完成 的。 由于c 程序具有灵活高效的优点，从c 语言的诞生到现在，不论是在桌面应用 程序，还是操作系统、服务器系统，嵌入式系统等各类软件系统的开发中，c 语 言作为一种主流程序设计语言一直被广泛使用。c 语言使得用户能够直接控制程 序内存资源的使用，这对于实现运行程序的高性能或提高计算机资源的利用率是 至关重要的，同时它给编程人员带来了更大的灵活性与自由度。但正是因为c 程 序中灵活的内存管理机制，使c 程序很容易产生内存破坏和内存泄漏等内存方面 的程序错误。 内存泄漏是一种常见的内存管理错误，它是由于在程序中动态分配内存后没 有及时释放而造成的。内存泄漏对于短时间运行的程序而言，它的影响可忽略不 计，然而对于诸如服务器或守护进程这类长时间运行的应用程序，它所带来的影 响不可轻视。当应厝程序在执行过程中需要越来越多的内存，系统就会按照一定 的策略将一些内存块交换出去，这样频繁地页面交换势必使得系统的性能也会随 之下降，一旦系统耗尽所有可用的虚拟地址空间，应用程序就会因为缺页错误而 被系统终止。这在很多应用方面所造成的损失是不可估量的。因此，人们迫切需 要一套支持c 语言程序的测试工具，特别要求工具能对内存泄漏的检测提供直接 支持，并希望检测结果能更准确更全面，同时希望检测的代价能尽量的小。由此 可见本课题的研究正是针对软件行业中的这一实际需求开展的。 研究和开发易用且能够准确全面的检测c 程序内存泄漏缺陷的测试工具，可 以大幅提高这类系统的质量，帮助开发者发现和减少软件中潜在的缺陷和错误， 降低软件成本，减少维护代价，并且还可以避免由于软件失效而带来的财产损失。 可以预见，本课题的研究将会具有广阔的市场应用前景，并且产生显著的经济效 益和社会效益。 2 北京邮电大学硕士研究生学位论文第一章绪论 1 3 工作重点 本文的工作旨在研究并实现用静态测试工具来自动检测c 程序中内存泄漏缺 陷的技术。主要通过实现针对故障的静态检测工具d t s c ，并通过对内存泄漏模 式的分析，设计并实现它的静态检测模型，对c 程序进行检测，并将检测的结果 与国外的检测工具的检测结果进行对比，分析d t s c 工具和内存检测模型的优点 和不足。 内存泄漏分析的研究重点包括：内存泄漏原因的分析，内存泄漏模式的总结， 内存泄漏模型的设计，以及静态检测工具d t s c 的实现。力求充分检测出c 程序 中内存泄漏缺陷的同时，减少误报。 本文的研究工作具体如下： 一、研究内存泄漏检测技术的发展情况以及内存泄漏的特征和产生原因，广 泛收集和了解国内外在内存错误检测领域内的最新研究成果及其技术，并对此进 行分析总结。 二、研究c 语言中内存泄漏故障产生的错误代码，总结出内存泄漏产生的模 式。 三、研究国内外静态测试领域的最新成果与技术，以及国内外现有的静态检 测工具，并对其进行总结和分析。 四、与实验室小组成员共同实现静态检测工具d t s c ，主要实现部分包括符 号表缺陷模式状态及缺陷分析单元等。 五根据内存泄漏产生的模式设计并实现内存泄漏模型，并用该模型对c 程 序进行检测。 六、将检测结果与国外静态检测工具的检测结果进行比较，分析d t s c 和内 存泄漏模型的优点和不足，并完善内存泄漏模型，提出d t s c 改进方案。 1 4 论文安排 本文的内容安排如下： 第一章绪论，阐述本课题的研究意义，指明本文研究的工作重点。 第二章内存泄漏，介绍内存泄漏的相关概念，分析了内存泄漏产生的原因， 并阐明了它的危害和内存检测的重要性。 第三章静态测试，介绍了静态测试的相关概念，即其与动态测试的不同及优 劣，同时还分析了国内外各种静态测试工具。 第四章静态检测工具d t s c 的设计与实现，介绍c 语言静态检测工具d t s c 的 3 北京邮电大学硕士研究生学位论文第一章绪论 体系结构，以及d t s c 的创新点和优势，同时详细的阐述了d t s c 各模块的设计 与实现。 第五章d t s c 中内存泄漏模型的设计与实现，总结了内存泄漏的各种模式， 详细阐述基于这些模式实现c 程序内存泄漏模型的方案设计与实现，描述其别名 分析技术的实现方法。 第六章d t s c 的内存泄漏模型的检测，根据内存泄漏各种模式设计测试用例， 对模型进行测试，并分析测试结果，同时用它对实际工程项目进行检测，并将结 果与国外知名静态检测工具k 8 进行比较，分析优劣。 最后，对于目前的研究工作予以总结，并提出需要进一步改进完善的部分， 分析今后的研究发展方向。 4 北京邮电大学硕士研究生学位论文第二章内存泄漏 2 1 内存泄漏的概念 第二章内存泄漏 内存泄漏( m e m o r y l e a k s ) 是指程序中己动态分配的堆内存由于某种原因程序 未释放或无法释放，造成系统内存的浪费，导致程序运行速度减慢甚至系统崩溃 等严重后果l 引。 通常内存泄漏分为两类：物理泄漏和逻辑泄漏【9 l 。物理泄漏是指应用程序动 态分配的内存以后，用于指向该内存的指针释放或用于其它用途，导致程序无法 再次访问和释放这块内存空间；逻辑泄漏是指应用程序在动态分配内存并使用完 之后一直都不释放该内存块，但程序仍然可以访问到这块内存空间。 内存泄漏缺陷具有隐蔽性、积累性的特征，比其他内存非法访问错误更难检 测。因为内存泄漏的产生原因是内存块未被释放，属于遗漏型缺陷而不是过错型 缺吲1 0 l 。此外，内存泄漏通常不会直接产生可观察的错误症状，而是逐渐积累， 降低系统整体性能，极端的情况下可能使系统崩溃。 2 2 内存泄漏产生的原因 程序的内存空间一般分为四个逻辑区域，即代码区、全局数据区、栈区和堆 区。当程序执行的时候，其可执行文件作为二进制机器指令被调人内存顺序存放， 以实现所谓的自动执行。栈区主要是函数调用的活动区域，为函数分配局部动态 变量等，函数调用结束后系统会自动收回内存。全局数据区存放的是静态和全局 变量，随着程序的消亡而自动收收回内存。堆区主要是程序运行过程中，给程序 动态分配内存的区域，其中的内存大小任意的( 内存块的大小可以在程序运行时 决定) ，由程序员自己需要时用m a l l o c ，r e a l l o c ，等函数从堆中申请，使用完后也必 须用程序代码显式调用f r e e 释放的内存，否则，这块内存就不能被再次使用。一 般我们常说的内存泄漏是指堆内存的泄漏。 从动态内存管理的角度来看，可以将一个c 程序分为两部分，一部分是完成 实际工作的工作例程，另一部分是动态内存的管理系统。在程序运行中，管理系 统掌握着一些可供申请的动态内存，即自由空间。工作例程中申请了一些动态内 5 北京邮电大学硕士研究生学位论文第二章内存泄漏 存块，通过全局数据区、栈区和寄存器中的命名指针变量索引它们，这些内存块 形成程序的工作空间。自由空间和工作空间均属于动态内存的组成部分。 在程序执行过程中，工作空间和自由空间之间存在着两个相反的内存块迁移 方向：1 、自由空间迁移至工作空间：工作例程通过m a l l o c 等分配操作将内存块 取到工作空间。2 、工作空间迁移至自由空间：通过f r e e 等释放操作将内存块送回 自由空间。 这就是c 语言的动态内存管理模型，如图2 1 所示： - 一一一一 !工作例程! 图2 - 1c 动态内存管理模型 正常情况下，程序员通过细心安排程序里的分配和释放操作，保证程序运行 过程中，流入工作空间的每个内存块或者仍然在工作空间里，或者己经被送回自 由空间。如果不能保证这点，动态空间中出现了己分配的内存块没有释放却失去 了访问路径的情况，工作例程就再也无法访问它们了。这些失去了访问路径的已 分配内存块就是被泄漏的内存。如图2 1 中在没有f r e e 标号为4 和7 的内存前，直接 f r e e 了标号为1 的内存，则标号为1 的内存会回到自由空间中，而造成了标号为4 和7 的内存的泄漏。存泄漏的产生如图2 2 所示： 6 北京邮电大学硕士研究生学位论文第二章内存泄漏 ：一一一一王祚芴矿一一一： 图2 - 2 内存泄漏示意图 由此可见，产生内存泄漏般需要满足两个条件：1 、动态内存块已经被分 配，即内存块不在自由空间内；2 、已分配的内存块失去索引，无法再访问，即 内存块不在工作空间内。 逻辑内存泄漏是一种特殊的内存泄漏情况，即动态内存块被全局指针索引， 但该内存块在程序结束运行前一直存在于工作空间，没有被释放，而且可以通过 全局指针访问该内存块，因此它不是真正的内存泄漏，本课题为将这种分配了动 态内存但未及时释放的情况归属于内存泄漏。 2 3 内存泄漏产生方式的分类 以产生的方式来分类，内存泄漏可以分为四类： 1 ) 常发性内存泄漏。发生内存泄漏的代码会被多次执行到，每次被执行的时 候都会导致一块内存泄漏。 2 ) 偶发性内存泄漏。发生内存泄漏的代码只有在某些特定环境或操作过程下 才会发生。常发性和偶发性是相对的。对于特定的环境，偶发性的也许就变成了 常发性的。所以测试环境和测试方法对检测内存泄漏至关重要。 3 ) 一次性内存泄漏。发生内存泄漏的代码只会被执行一次，或者由于算法上 的缺陷，导致总会有一块仅且一块内存发生泄漏。举例说明如下： 7 北京邮电大学硕士研究生学位论文第二章内存泄漏 c h a r 木n a m e = n u l l ； v o i ds e t n a m e 0 i f ( n a m e ) f r e e ( n a m e ) ； n a m e = ( c h a r 水) m a l l o c ( s i z e o f ( c h a r ) 幸l o o ) ； ， 如果程序在结束的时候没有释放n a m e 指向的字符串，那么，即使多次调用 s e t n a m e ( ) ，总会有一块内存，而且仅有一块内存发生泄漏。 4 ) 隐式内存泄漏。程序在运行过程中不停的分配内存，但是直到结束的时候 才释放内存。严格的说这里并没有发生内存泄漏，因为最终程序释放了所有申请 的内存。但是对于一个服务器程序，需要运行几天，几周甚至几个月，不及时释 放内存也可能导致最终耗尽系统的所有内存。所以，我们称这类内存泄漏为隐式 内存泄漏，也就是前面提到的逻辑泄漏。 从用户使用程序的角度来看，内存泄漏本身不会产生什么危害，作为一般的 用户，根本感觉不到内存泄漏的存在。真正有危害的是内存泄漏的堆积，这会最 终耗尽系统所有的内存。 2 4 内存泄漏检测的重要意义 内存泄漏是程序中动态内存分配方面的缺陷，即动态分配的存储空间在程序 不再使用时仍然没有释放。随着分配空间地增加，这种缺陷会使程序执行速度变 慢，最终使程序因内存耗尽而崩溃。对于内存受限系统( 如嵌入式系统) ，或程序 执行时间较长的系统( 如服务器系统) 而言，这种问题更为严重。例女1 1 9 9 2 年9 月 英国伦敦救护服务系统的崩溃就是由于系统中存在内存泄漏，在程序连续运行三 星期后而引发的危险事故【1 1 1 。然而，随着计算机内存容量的不断增大和虚拟内存 技术的发展，有人会产生浪费一点内存无所谓的观点，这种观点是非常错误的。 因为耗尽虚拟内存空间，意味着己经在实际内存中产生泄漏。内存泄漏缺陷虽然 是难以观察到的，但随着泄漏内存的累积，系统的整体性能下降，严重时将会导 致计算机系统无法工作。 通过实验1 1 2 j 分析并验证内存泄漏缺陷在软件中是普遍存在的，而对于使用c 8 北京邮电大学硕士研究生学位论文第二章内存泄漏 语言的程序员来说，内存泄漏缺陷就如同程序中埋藏的定时炸弹，严重威胁着软 件系统的稳定性。因此，通过检测软件的内存泄漏缺陷，揭示软件产品中隐藏的 内存错误，能够提高软件的性能和可靠性，保证软件产品的质量，让程序员对软 件系统高效正确的运行充满信心。 2 5 国内外研究现状 随着人们对软件质量的重视，检测并去除软件中的内存错误己经成为不可缺 少的软件测试过程之。国内外软件专家研究出各类检测内存错误的技术，软件 市场中也涌现出许多内存错误测试工具，其中应用广泛的内存测试工具主要有： 美国康博软件公司出品的c o m p u w a r en u m e g a 自动化白盒测试工具 b o u n d s c h e c k e r l l 3 1 。 通过对被测应用程序的测试，b o u n d s c h e c k e r 提供清晰的、详细的程序错误 分析，自动查明静态的堆栈错误及内存资源泄漏，并能够迅速的定位出错的源 代码，即使在没有源代码的情况下也可检查第三方组件的错误。b o u n d s c h e c k e 错误检测范围主要包括：指针和泄漏错误；内存错误；a p i 和o u ! 错误。 b o u n d s c h e c k e r 支持的语言和主机平台：c c + + ，o b j e c tp a s c a l ( d e l p h i ) ；w 。 i n d o w sn t ，w i n d o w s 9 5 9 8 2 0 0 0 。 美国i b m ra t i o n a l 公司( 原p u r e a t r i a 公司，现已被i b m 公司收购) 出品的一套完 整的运行时分析工具i b mr a t i o n a lp u r i f yp l u s 1 4 j 。 p u r i f yp l u s 将内存错误和泄漏检测、应用程序性能描述、代码覆盖分析等功 能组合在一个单一、完整的工具包中。这些功能帮助开发人员在其软件发布伊始 就能确保软件具有最佳的可靠性和性能。其p u r i f y n - - j 检测的内存错误主要有： 内存泄漏、未初始化的局部变量、未申请的内存、使用已释放的内存、数组越界、 内存丢失、文件描述问题、栈溢出等缺陷。 p u r i f y 支持的语言和主机平台：c c + + ，j a v a ；w i n d o w sn t 4 0s p6 a ，w i n d o w s 2 0 0 0p r o f e s s i o n a l ，w i n d o w sx pp r o f e s s i o n a l ，s u ns o l a r i s2 6 、7 、8 、9 ，h p i i x1 0 2 ， 1 1 x x ，i b ma i x4 3 和5 uv 5 1 v 5 2 ) ，r e dh a tl i n u x 7 0 ，7 2 ，7 3 ，8 0 ，s u s e l i n u x 7 2 、7 3 、8 1 u n i x 和l i n u x 平台下开源的内存错误检测工具： d m a l l o c l l 5 1 ，m p r o f 1 6 1 ，v a l g r i n d 1 7 1 ，m a l l o c d e b u g 1 8 1 ，d e b u g l i b 1 9 】等，内存错 误检测工具采用不同的技术基本实现内存泄漏错误的检测。 l i n t 2 0 l 是一个用静态方法检测内存泄漏的工具，它利用类型分析方法，这类 工具需要手工对访存操作进行注释以辅助内存分析。文献【6 ，7 】给出了能够自 动进行内存类型推断的类型分析方法减少了对指针注释的数量，但是仍然 9 北京邮电大学硕士研究生学位论文 第二章内存泄漏 需要手工添加一定数量的类型注释。另外，由于类型分析方法中没有利用控 制流信息，使得基于类型的方法所得到结果的精度有一定局限。 此外，除了各种专用的内存测试工具，内存垃圾收集技术也可以用来检测内 存洲漏。 1 0 北京邮电大学硕士研究生学位论文第三章静态测试 3 1 静态测试的概念 第三章静态测试 软件测试有静态测试和动态测试之分。静态测试的基本特征是在对软件进行 分析、检查时，不执行被测程序，它是软件开发中十分有效的质量控制方式之一。 有数据表明，对软件进行静态测试可以揭示出大部分软件缺陷。 3 2 静态测试与动态测试的比较 静态测试在程序执行前检查程序错误，所以不影响程序执行效率。而动态测 试法在程序执行时检查错误，通常需要占用额外的系统资源，对程序运行速度有 所影响。一次动态测试仅覆盖程序的一条执行路径，需要辅以测试覆盖率的分析 才能提高测试的有效性和充分性。但这也检测不出程序中每条执行路径上的错 误。解决上述问题恰恰是静态软件测试方法所擅长的。静态测试不需要设计大量 的测试用例，执行效率高，能够较全面的覆盖系统代码，不需要测试覆盖率的分 析的辅助。 但静态测试也存在局限性。静态测试难以正确分析需要动态执行才能确定的 程序信息，如数组、链表等动态数据结构的分析，所以有时产生错误的警告信息 或无法检测出某些程序缺陷。同时静态测试由于不实际执行被测程序所以在找到 一个潜在的错误后还需要人工确认是否是真正的错误。现有的静态测试方法主要 存在漏报和误报过多的情况，给人工确认带来很大的困难，因此静态测试的准确 性至关重要。 3 3 静态检测技术 最简单的静态检测技术是使用与u n i x 平台下的g r e p 类似的工具，搜索源代码 中可能存在的一些不安全的库函数的调用。 i t s 4 ，栅和f l a w f i n d e r 是目前发展比较成熟的源码扫描工具，其基本原理 是对源程序进行词法分析，得至l j t o k e n 序列，然后与其维护的漏洞数据库中的信 北京邮电大学硕士研究生学位论文第三章静态测试 息比较，发现可能的缺陷，给出提示。这类检测技术实现简单，算法效率高，能 够较全面的覆盖系统代码，但是由于没有考虑到语法和语义层次的信息，所以这 些检测工具能够检测出系统的大量漏洞，但很多是误报。而且产生的结果集很大， 人工审计仍然很困难。 f l a w f i n d e r l 2 1 】是2 0 0 1 年发布的基于p v t h o n 语言开发的用来辅助进行安全审查 c c + + 程序的工具。它内嵌了一些常见的类似于i t s 4 的程序漏洞数据库，比如 缓冲区溢出、内存泄漏、格式化串漏洞等，并且扫描速度快，是程序静态检查中 极有竞争力的工具。f l a w f i n d e r 是遵循g p l 2 协议开发的，运行于u n i x 平台。 f l a w f i n d e r 源程序公开，是一款比较好的在程序发布前找出其潜在漏洞的工具。 r a t s ( t h er o u g ha u d i t i n gt o o lf o rs e c u r i t y ) 2 2 】也是一个影响比较大的源代码 扫描工具，目前正处于比较活跃的开发过程中，可以检查使用c 、c + + 、p e r l 、p h p 和p y t h o n 等语言编写的源程序。r a t s 可以输出x m 嘴式的错误信息，因此在使 用r a t s 之前，还需要安装x m l 处理工具e x p a t 。在r a t s 的运行过程中，用户可 以通过配置来改变其输出的错误信息级别，缺省是中级。可选的漏洞知识库和一 致的输出函数可以接受用户的自定义输入，因此更方便用户使用自己的专门数据 来发现特定的错误。目前r a t s 中已知的缺点包括它所使用的贪婪匹配算法，使 用这种算法，使得过滤错误的命中变得比较困难。 i t s 4 ( t h es o f t w a r es t u p i ds o u r c es c a n n e r ) 1 2 3 】是基于l i n u x 和u n i x 的扫描工具， 可以扫描c 和c + + 语言所编写的程序，用于发现一些最普遍的安全性相关的漏洞。 由于许多i t s 4 的开发人员转向开发r a t s 和f l a w f i n d e r ，因此它的开发趋于平和。 但某些吸引人的特点在r a t s 或者f l a w f m d e r 中得到了发展，例如行忽略技术、跟 踪用户输入以及可选的漏洞知识库等。i t s 4 可与u n i x 下的编辑工具e m a c s 结合 起来运行，在程序员编码的过程中同步完成检查，可以随时的提示程序员。这也 是i t s 4 与其它源码扫描工具相比所独有的一个特点。 l i n t 是f 扫a n d yl e s t e r 发布的一个开源工具，能够检查可能的空指针、在释放 内存之后使用了该指针、赋值次序问题以及拼写错误等。一个c c + + 编译器通常 假设程序是正确的，而l i n t 恰恰相反，因此，它优于编译器执行的一般性检查。 l i n t 还可以贯穿多个文件来执行它的错误检查和代码分析。目前有两个流行的 l i n t - k 具：p c 1 i n t 和s p l i n t ( 原l c l i n t ) 。p c l i n t 是一种静态代码检测工具，它可以 检查出那些虽然完全合乎语法要求，但很可能存在潜在的、不易发现的错误； p c 1 i n t 可以在检查当前文件的同时检查所有与之相关的文件，从而从整个项目的 角度来检测问题；p c 1 i n t 支持几乎所有流行的编辑环境和编译器，l l 女n b o r l a n d c + + 、g c c 、v c 、v c n e t 、s o u r c ei n s i g h t 等等，支持1 6 3 2 6 4 的平台环境；p c 1 i n t 支持s c o t tm e y e s 的名著( e f f e c t i v ec + + m o r ee f f e c t i v ec + + ) 中说描述的各种提高 北京邮电大学硕士研究生学位论文 第三章静态测试 效率和防止错误的方法。s p l i n t 是在n t 工具的基础上改造而成的，专门针对程序 的安全问题。它要求手工加入注释，然后根据这些注释进行语法分析，利用了语 法树刚。 k l o c w o r kk 8 ( 简称k 8 ) 【2 5 1 是o c w o r k 公司出品，k l o c w o r k 位于麻省伯灵顿， 此公司是程序静态分析解决方案的领导者，主要致力于帮助用户提高开发效率， 降低开发成本，提高软件安全性和软件质量。k l o c w o r k8 缺陷分析有以下几个特 点：分析的缺陷类型全面、准确；分析能力强、适应性强，能够分析上千万行代 码；能够自动提取源程序构建信息；使用知识库技术进行缺陷检测。k l o c w o r k8 除了静态检测功能外还有软件结构分析、质量趋势分析、定制开发策略等功能， 十分强大。 l o g i s c o p e 是法 t e l e l o g i c 公司推出的专用于软件质量保证和软件测试的产 品。其主要功能是对软件做质量分析和测试以保证软件的质量，并可做认证、反 向工程和维护，特别是针对要求高可靠性和高安全性的软件项目和工程。 l o g i s c o p e 是一组嵌入软件测试工具集。l o g i s c o p e 产品主要有3 个功能：1 l o g i s c o p er u l e c h e c k e r 语法规则分析功能：根据工程中定义的编程规则自动检_ 查软件代码错误，可直接定位错误，其包含大量标准规则。另外这个工具的亮点 就是高度可扩展性，用户可以定制创建规则，并自动生成测试报告。2 l o g i s c o p e a u d i t 静态分析功能：定位错误模块，可评估软件质量及复杂程度；提供代码的 直观描述，自动生成软件文档。3 l o g i s c o p et e s t c h e c k e r 测试覆盖分析：显示没 有测试的代码路径，基于源码结构分析。直接反馈测试效率和测试进度，协助进 行衰退测试。支持不同的实时操作系统、支持多线程。自动生成定制报告和文档_ 按照工作方式不同，上述的检测工具大致可分为三类：( 1 ) 基于词法分析的检 测方法；( 2 ) 注释驱动的约束分析和检测方法；( 3 ) 对源码抽象、建模，然后分析求 解的检测方法。 第一类工具出现的时间较长，且发展较成熟，其优点是：漏洞特征以数据的 形式独立于分析程序存在，可以灵活扩展。另外，词法分析可以保证较好的执行 效率。但它的缺点非常明显：以数据形式存在的特征库并不能对漏洞进行充分、 完整的描述，从而造成漏洞信息收集的不完整，也限制了与之配合的相关算法仅 能进行词法分析，因此影响了检测能力。 第二类检测工具虽然引入了语法分析，却是基于程序验证系统的思想和方法 进行的。这要求操作人员对检测目标非常熟悉，甚至需人工编写程序规范和注释， 因此检测的自动化程度较低。 第三类检测工具倾向于将源码的特征进行抽象、建模，将漏洞检测问题转化 为约束分析和求解的问题。它们一般基于已有的程序分析工具来实现，其优点是： 1 3 北京邮电大学硕士研究生学位论文第三章静态测试 功能非常强大，能够生成抽象语法树、函数调用关系图、控制流图甚至指针指向 关系图等语法、语义信息。使用工具提供的编程接口，可以直接基于这些信息进 行分析，从而减小了设计上的复杂度。但它们的缺点是对已有分析工具的依赖性， 其开发过程也缺少灵活性。 静态检测主要是通过对源代码扫描来判断是否存在内存泄漏的故障，其优点 是在软件发布之前就修正所发现的弱点，并且不会造成程序执行的负担。国内也 有许多学者和研究机构进行了这方面的研究，如参考文献1 2 6 - 2 8 1 。 1 4 北京邮电大学硕士研究生学位论文第四章静态检测工具i y i s c 的设计与实现 第四章静态检测工具d t s c 的设计与实现 4 1d t s c 的介绍 d t s c 系统是面向缺陷软件测试系统一d t s 的重要组成部分之一。主要用 于针对c 程序的面向缺陷测试，其主要组成部分包括：抽象语法树生成；控制流 图生成；符号表生成；区间运算；缺陷模式状态机计算；数据库访问；缺陷分析。 其主要对外连接关系包括：用户配置要分析的缺陷模式及其相关描述文件，相关 描述文件包括模式定义x m l 文件和模式动作c l a s s 文件；用户指定要分析的目 标源代码；d t s c 将发现的缺陷检查点填写入数据库以方便界面程序进一步的显 示和分析。 d t s c 的功能是根据给定的要分析的缺陷模式及其相关描述文件，对目标c 代码进行自动分析，查找目标c 代码中潜在的符合缺陷模式描述的检查点，并将 检查点信息入库。 本项目为8 6 3 课题的一个子课题。 4 1 1d t s c 的框架 d t s c 软件可以分成用户界面，处理模块，输入模块，缺陷报表4 个部分。图 4 _ l 为d t s c 的体系结构图： 1 5 北京邮电人学硕研究生学位论文第叫章静态捡t 且d t s c 的设计与宴现 处理 模块 输入 模块 图4 - 1d t s c 软件c s c l 软件单元组成 ( 1 ) 输入模块 软件缺陷、规则描述文件( s d d l ) ：该文件采用y a u l 技术描述了要检测的 缺陷模式或者规则的状态机模型。 配置文件：对系统进行配置，如定义要检测的缺陷模式或者规则。 程序源代码：是被测试程序的代码。 ( 2 ) 统一测试框架 词法分析语法分析：用丁源代码的词法和语法分析 抽象语法树生成器：根据c 源代码生成c 抽象语法树 控制流图生成器：根据抽象语法树生成每个函数的控制流图 符号表生成器：根据抽象语法树生成作用域和作用域下的标志符符号表 区间运算：根据抽蒙语法树、控制流图和符号表对程序的各种变量进行区 间运算，跟踪变量在程序中各位置的可能取值范田 缺陷模式分析引擎：根据缺陷模式配置及相应的模式定义和模式动作文件， 北京邮电大学硕士研究生学位论文第四章静态检测工具d t s c 的设计与实现 结合控制流图、抽象语法树、符号表和区间运算等进行状态机计算并报告 检查点。 ( 3 ) 用户界面：是用户使用的界面。该界面简单、直观、易学。 ( 4 ) 缺陷报表：测试结果报表。 d t s c 软件c s c i 的执行控制流程如图4 2 所示： |l 图4 - 2d t s c 流程图 1 7 北京邮电大学硕士研究生学位论文第四章静态检测工具d t s c 的设计与实现 4 2d t s c 的特点与优势 软件缺陷测试系统( d t s c ) 是一套面向故障的测试工具，它采用全新的软 件测试理念，具有和以往各种测试方法不同的特点。该方法的核心概念是故障 模式，所谓软件的故障模式就是总结那些经常出现、并具有一定模式的故障。 经过大量的源码分析和总结，给出一些极具代表性的错误模式，测试过程就是 针对这些故障模式进行有目的性的自动化或者半自动化测试，应用d t s c 可大 大提高了软件测试效率和软件质量。d t s c 有如下特点和先进性： 面向故障：d t s c 是面向故障的静态检测工具，针对各种故障总结故障模式， 设计故障模型。故障模型反映了故障发生的规律，基于故障模型的自动测 试方法通过静态分析源程序、依据故障模型来识别故障，因此基于故障模 型的自动测试方法不需要运行程序；与传统测试方法相比，它具有易于全 面覆盖代码、易于定位故障的优点，检错能力依赖于故障模型和自动测试 方法的有效性! 增加了区间运算，大大提高准确率，降低了误报和漏报。 功能强大：d t s c 采用全新的软件测试理念，直接对软件的故障、漏洞：缺 陷和违反规则实施测试。目前d t s c 系统对故障、漏洞和缺陷已经定义了 1 5 0 多种模式，违反规则的模式近2 0 0 多种。内存泄漏故障就是其中的一种 故障。 自动化程度高：d t s c 自动扫描c 源代码，产生可疑缺陷点i p 。结果相对 较为客观，测试结果可复现 缺陷检测效率高：理论上看，对所定义的缺陷模式实施测试时，