（计算机科学与技术专业论文）cbftcc+bug+finding+tool的设计与实现.pdf

c b f t ( c + + cb u gf i n d i n gt 0 0 1 ) 的设计与实现摘要随着软件系统的普及，软件测试成为保证软件质量、提高软件可靠性的重要手段。而软件测试的工作量很大，用人工测试几乎难以胜任，在规模迅速扩大的软件系统中，实现高准确度，高效率的测试遇到的困难越来越大。因此在测试过程中引入自动化的思想逐步发展和成熟起来。在软件测试技术中，程序静态分析技术近年来成为自动化测试技术中的一个研究热点，大量的软件测试工具被研制出来从而可以自动地静态检测软件中的故障，并且在对一些大型商业软件和开源软件的测试中发现了大量的以前测试没有发现的软件故障和安全隐患。但其缺陷也随之暴露出来，如误报问题和漏报问题没有得到很好地解决等等。在基于静态分析的自动化测试方法中，寻找针对性强，工具自动化程度高，测试效率高和漏报率低的自动化测试方法，成为一个亟待解决的问题。通过对基于缺陷模式的软件测试方法的研究，在8 6 3 课题支持下所开发的针对c c + + 语言的c b f t i 具，可以对软件的缺陷自动进行测试并记录，极大地提高软件的测试效率和软件质量，应用c b f t 可大大提高软件的测试效率和软件质量，使软件在开发整体上具有时间的竞争优势。本文系统研究了针对c 抖，c 语言的缺陷模式，提出了缺陷模式的定义和分类，并对其中的漏洞模式进行了详细的总结和定义。同时，本文在调研国内外自动化静态分析工具的基础上，深入研究开源工具j a v a c c ，借鉴其设计思想，结合访问者模式独立设计并实现了自动化测试工具c b f t 的统一测试框架部分，完成了抽象语法树、控制流图和符号表的生成，此测试框架可以对c + + ，c 语言进行自动化测试，相比于以往检测方法，降低了测试误报率和漏报率，对于软件测试具有重要的意义。关键词：软件测试；静态分析；缺陷模式；抽象语法树；控制流图；符号表；t h ed e s i g na n di m p l e m e n l = a n o no f c b f ta b s t r a c tw i t ht h ep r e v a l e n ta n dp o p u l a r i t yo fs o f t w a r es y s t e m s ，s o f t w a r et e s ti so b v i o u s l yb e c o m i n gac o m m o na n ds i g n i f i c a n tm e t h o dt oa s s u r et h eq u a l i t yo fs o f t w a r ea n de n h a n c ei t sr e l i a b i l i t y i ft e s ti so n l yd e p e n d e n to nh u m a nb e i n g sw i t hm a n u a lc h e c k i n g ，s u c ha p p r o a c hc a n n o ta f f o r dh e a v yw o r k l o a da n dl a r g es c a l et e s t i n g a c h i e v i n gh i g ha c c u r a c ya n dh i g he f f i c i e n c ya st h eo b j e c t i v eo ft e s ti nt h er a p i d l ye x p a n d i n gs c a l es o f t w a r es y s t e m si se n c o u n t e r i n gd i f f i c u l t i e s ；t h e r e f o r et h ei d e ao fa u t o m a t i ct e s ti si n t r o d u c e da n dr a p i d l yd e v e l o p e di nt h ec o u r s eo fs o f t w a r et e s t i n g i ns o f t w a r et e s tt e c h n o l o g y , p r o g r a ms t a t i ca n a l y s i st e c h n i q u eh a sb e c o m ear e s e a r c hh o t s p o ti nr e s e n ty e a r s a l t h o u g hl a r g en u m b e r so ft e s tt o o l sh a v eb e e nd e v e l o p e dw h i c hc o u l da u t o m a t i c a l l yd e t e c ts o f t w a r ef a i l u r e s ，t h e r ea l s oe x i s t e dm a n ys h o r t c o m i n g si nt h e s et e s tt o o l s ，s u c ha sh i g hr a t eo ff a i l u r er e p o r ta n dm i s s i n gr e p o r t t h e r e f o r e ，i ti sa nu r g e n ta n ds i g n i f i c a n ti s s u et of i n dm e t h o d sw h i c hc o u l dd e t e c ts o f t w a r ef a i l u r ew i t hh i g hd e g r e eo fa u t o m a t i o na sw e l la sw i t hl o wm i s s i n ga n df d l u r er e p o r tr a t e s i nt h i sp a p e r c b f ri si n t r o d u c e da n dd e v e l o p e du n d e rt h es u p p o r to f8 6 3p r o j e c t , w h i c hs a t i s f i e ss u c ha i m sb a s e do nd e f e c tp a t t e r n s n i st o o lc o u l dd e f e c t ss o f t w a r ef a i l u r ea u t o m a t i c a l l y , g r e a t l yi m p r o v i n gt h eq u a l i t ya n de f f i c i e n c yo f s o f t w a r et e s t i n g s p e c i f i c a l l y , a u t h o r i n v e s t i g a t e ss t a t i ca n a l y s i st o o l sa th o m ea n da b r o a de x t e n s i v e l y , s t u d i e st h eo p e ns o u r c et o o lj a v a c ci n d e p t ha n dd r a w so ni t se l e g a n td e s i g n ，c o m b i n e dw i t hd e s i g np a t t e r n “v i s i t o r ”p a t t e r n ，t oi m p l e m e n tt h ef o u n d a t i o no fu n i f i e dt e s tf r a m e w o r ko fc b f t t h ef o u n d a t i o nf r a m e w o r kc o n s i s t so ft h r e ep a r t s ：c o n s t r u c t i o no fa b s t r a c ts y n t a xt r e e ，c o n s t r u c t i o no fc o n t r o lf l o wg r a p ha n ds y m b o lt a b l eg e n e r a t i o n 1 h eu n i f i e dt e s tf r a m e w o r kc a nt e s tc ，c + + l a n g u a g eb a s e ds o f t w a r ea u t o m a t i c a l l y c o m p a r e dw i t ho t h e rm e t h o d s ，t h ed e f e c tp a t t e r nb a s e da p p r o a c hr e d u c i n gt h ef a l s ea n dm i s s i n gr e p o r tr a t ei so fg r e a ts i g n i f i c a n c e vk e yw o r d s ：s o f t w a r et e s t ，s t a t i ca n a l y s i s ，a b s t r a c ts y n t a xt r e e ；c o n t r o lf l o wg r a p h ，s y m b o lt a b l e ，f a u l tp a t t e r n独创性( 或创新性) 声明本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人签名：本人承担一切相关责任。日期：靼红丝。2 之j关于论文使用授权的说明学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定)保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论文注释：本学位本人签名：导师签名：适用本授权书。量塑：丑啤逻卫二日期：北京邮电大学硕士学位论文第一章绪论1 1 研究背景和意义第一章绪论随着计算机的普及，软件系统已经深入到人们生活工作的各个方面，可靠性显得越来越重要，对软件进行测试是保证软件质量很重要的一环，同时软件系统的规模也在持续扩大，需求日益复杂，对软件质量的要求也越来越高，该问题已成为制约计算机发展的主要因素之一。但现实中软件系统的质量和稳定性却不尽如人意，因而采用有效的软件测试是保证软件质量、提高软件可靠性的重要手段。软件测试可以看作是对错误空间的搜索，即要在数以百万计甚至更多的输入及其状态组合中，尽可能寻找更多的错误的状态及其组合。软件测试【1 】【2 j 是软件生命周期中的重要环节，是保证软件质量的重要手段。而测试的工作量很大，在一般的开发过程中会占到工作总量的4 0 以上，在一些要求比较严格的软件开发中，还会高于这一比例。软件规模的扩大更加重了测试工作，如手工测试的速度太慢、效率太低等等，同时测试过程具有很多操作重复、非智力创造性的、要求细致注意力的工作。对于一个合格而完备的软件测试系统而言，如果要确保每一个目标组合都被测试，那么测试必须是系统的；因为最终要定位错误，所以测试必须是集中的；因为测试需要使用大量的测试用例和大量的重复性测试，用纯人工测试几乎难以胜任，因此测试又需要是自动的。在这样的背景下，在测试过程中引入自动化的思想逐步发展和成熟起来。随着软件测试技术的不断成熟，程序静态分析技术成为自动化测试技术中的一个研究热点，大量的软件测试工具被研制出来用以自动地检测软件中的故障，并且在对一些大型商业软件和开源软件的测试中发现了大量的以前测试没有发现的软件故障和安全隐患，但其缺陷也随之暴露出来，如误报问题和漏报问题没有得到很好地解决等等。在多种静态分析方法之中，基于缺陷模式的软件测试方法具有针对性强，工具自动化程度高，测试效率高和漏报率低等特点。目前国际上基于缺陷的软件测试工具大约有几十个，商业化的软件大约有十余个，他们存在的主要问题是：价格昂贵，一般需要百万人民币；故障误报率高：一般在7 0 - - 8 0 ；故障的漏报率高：各个工具检测效果的不一致。而国内基于缺陷的软件测试工具尚未问世，因此，本文研究依托的8 6 3 课题所开发的c b f t 系统是国内第一套基于软件缺陷的测试工具，采用目前国际主流的软件测试技术，诠释了软件领域一种全新的软件北京邮电大学硕士学位论文第一章绪论测试理念。它弥补了当前国内外众多软件测试工具的不足，填补了国内在软件缺陷测试领域的空白。本文研究内容属于该课题的一个部分，针对c c + + 语言对缺陷模式进行了详细的总结和定义，基于缺陷模式设计并实现自动化软件测试工具c b f t ( c + + cb u gf i n d i n gt o o l s ) 的统一测试框架，该框架作为其他处理模块的基础，提供基本的抽象语法树生成，控制流图生成，符号表生成，配合其他处理模块能够对基于c + + 或c 语言的软件进行自动化检测，查找目标代码中潜在的符合缺陷模式描述的i p ( 检查点) ，并将球信息入库，解决目前软件测试的低效率、误报率漏报率高、测试效果不佳等方面的问题，对软件自动化测试具有重要的意义。1 2 主要研究工作本人在硕士研究生期间，参加了国家8 6 3 项目“软件的故障模型与面向故障的软件测试系统( 课题编号：2 0 0 6 a a 0 1 2 1 8 4 ) ，主要负责缺陷模式的总结定义和自动化测试系统c b f t 统一框架的设计与开发：国家发改委项目“c n g i 通用业务平台 ，主要负责翻译器模块的设计和业务脚本的研究。具体来说，作者在攻读硕士学位期间的主要研究工作包括以下两个方面：第一，软件的故障模型与面向故障的软件测试系统：1 研究了软件测试技术，包括静态分析的各种方法。2 研究基于缺陷模式的测试技术，并对c + + 和c 语言的漏洞缺陷模式进行总结定义。3 研究并参与开发自动化测试工具c b f t 的统一测试框架，包括抽象语法树，控制流图和符号表的生成。第二，c n g i 通用业务平台：1 研究了下一代网络的网络框架，和3 g 标准t d 。s c d m a 和移动w i m a x 。2 研究c p l 语言，r f c 2 8 2 4 ，并对其进行语言机制和附加功能的扩展。3 研究业务生成方法，基于脚本的业务生成方法设计新的业务脚本，包括短信发送邮件，短信接受邮件，短信定位等。4 研究并参与开发c n g i 通用业务平台的翻译器和业务构件。限于论文篇幅和文章的一致性，在上述研究中，本文只给出了作者对于自动化测试工具c b 兀方面的研究成果，而不涉及c n g i 通用业务平台的研究和开发。2北京邮电大学硕士学位论文第一章绪论1 3 论文组织和结构本文主要研究内容是基于缺陷模式的自动化测试相关问题，包括基于缺陷模式的静态分析方法综述，c + + 、c 语言的缺陷模式总结定义，并在此基础上设计和实现了自动化测试工具c b f t 的统一测试框架，包括抽象语法树，控制流图和符号表的研究与实现。论文共分为六章，论文主要结构概述如下：第一章绪论本章主要介绍了本论文的研究背景，研究工作和论文结构。第二章静态测试相关技术综述本章首先对软件测试进行了概述，从定义入手，尽管目前软件测试定义不一，但总体目标都是以提高软件的质量为根本目的，明确了软件测试的重要意义。然后，根据不同分类条件对软件测试方法进行了分类概述，并详细阐明静态分析方法在软件测试中的地位和主要研究方法，并介绍了目前国内外静态测试技术的研究现状。第三章基于缺陷模式的软件测试方法本章介绍了基于缺陷模式的软件测试方法的概念和优势，并针对c + + c 语言中涉及到的缺陷模型进行了总结归纳，包括缺陷故障模型的概念介绍，对故障模式，漏洞模式，疑问模式和规则模式这四种缺陷模式的定义，之后针对其中的漏洞模式的具体分类，一般形式和例证等分别给予详细的说明。第四章c b f i 系统综述本章主要介绍了c b y i 系统的核心优势，总体框架和测试流程，并对系统中采用的编译器生成工具j a v a c c 进行了详细的介绍，为下一章介绍抽象语法树的生成做好准备。第五章c b f t 统一测试框架的设计与实现本章主要介绍了c b f t 系统统一测试框架的部分设计与实现，包括统一测试流程，抽象语法树，控制流图和符号表的生成，每个部分都介绍了相应的生成流程算法，实现的数据结构和打印图示，统一测试框架的设计与实现为整个c b f t3北京邮电大学硕士学位论文第一章绪论系统后期的进一步测试分析和优势技术的应用打好了基础。第六章结束语本章简要归纳了本论文所研究内容的创新点，提出了基于缺陷模型的软件测试技术的下一步研究方向。4北京邮电大学硕士学位论文件测试技术综述错误i 未找到引用源软第二章软件测试技术综述软件测试的方法根据是否要实际运行被测软件而言，可以分为动态测试和静态测试。静态测试是软件测试中技术中的一个重要分支，作为动态测试的补充，在程序运行前尽可能多的发现其中隐含的错误，提高程序的可靠性和健壮性。本章主要阐述软件测试相关技术，简要介绍软件测试的概念并阐明软件测试意义，然后对软件测试不同分类方法进行具体说明，第三节将具体介绍静态测试技术，着重针对目前静态分析技术分类方法以及国内外对静态测试技术的研究成果。2 1 软件测试概述软件测试是对软件需求分析、设计规格说明和编码的终审，是软件质量保证的关键步骤。但对于什么是软件测试，一直未达成共识，根据侧重点不同，主要有三种描述：定义1 ：1 9 8 3 年i e e e ( 国际电子电气工程师协会) 提出的软件工程标准术语中给软件测试下的定义是：“使用人工或自动手段来运行或测定某个系统的过程，其目的在于检验它是否满足规定的需求或是弄清预期结果与实际结果之间的差别 。该定义包含了两方面的含义：1 是否满足规定的需求。2 是否有差别。如果有差别，说明设计或实现中存在故障，自然不满足规定的需求。因此，这一定义非常明确地提出了软件测试以检验软件是否满足需求为目标。定义2 ：软件测试是根据软件开发各阶段的规格说明和程序的内部结构而精心设计一批测试用例，并利用这些测试用例去执行程序，以发现软件故障的过程。该定义强调寻找故障是测试的目的。定义3 ：软件测试是一种软件质量保证活动，其动机是通过一些经济有效的方法，发现软件中存在的缺陷，从而保证软件质量。上述三种观点实际上是从不同角度理解软件测试，但不论从哪种观点出发，都可以认为软件测试是在一个可控的环境中分析或执行程序的过程，其根本目的是以尽可能少的时间和人力发现并改正软件中潜在的各种故障及缺陷，提高软件的质量。所以软件测试对于软件系统的质量保证具有非常重要的意义，主要体现在以下几个方面：1 减少软件的缺陷数目或者降低软件的缺陷密度。通过测试可以发现软件中存在的缺陷，通过完全地修改这些缺陷，可以减少软件中缺陷的总数目或者降低其缺陷密度。2 提高软件的可靠性。软件的缺陷数目是影响软件5北京邮电大学硕士学位论文件测试技术综述错误l 未找到引用源软可靠性的主要因素，通过测试减少软件的缺陷数目可以达到提高软件可靠性的目的。3 评估软件的性能指标。通过软件测试，根据所发现的缺陷数目和发现缺陷的时间，可以评估软件的可靠性等指标，即使软件测试没有发现缺陷，也同样可以达到这个目的。4 增加用户对软件的信心。软件通过了何种测试对用户来说是非常重要的，严格的软件测试可以大大增强用户对该软件的信心。正是由于软件测试的重要意义，软件测试技术逐渐成为一门独立的学科，尤其在最近十几年来，软件测试技术得到了快速发展，表现在：1 出现了众多新的软件测试方法。面向模型的软件测试技术、面向对象的软件测试技术、g u i 测试技术、软件可靠性测试技术、软件测试性分析技术等，都是近些年来发展起来的新的软件测试技术。2 出现了众多的软件测试工具。包括白盒测试工具、黑盒测试工具、面向模型的测试工具、功能测试工具、性能测试工具、g u i 测试工具、可靠性测试工具、测试性分析工具等，测试管理工具等。3 软件测试工具的自动化程度更高。软件测试是一个知识密集与劳动密集相结合的产业，先进的软件测试工具不仅能更多的发现软件错误，也能大大提高劳动生产率。4 软件模型的研究取得了重大突破，面向模型的软件测试工具应运而生。模型研究的是否成熟是该学科测试技术发展是否成熟的重要标志。进入2 0 0 0 年以来，经过对大量软件的深入研究，提出了c + + 、j a v a 的模型，相应的面向软件模型的测试系统也应运而生。软件测试技术的快速发展，极大的促进了软件测试产业的发展；蓟瑚5 底，全国有各种测试中心( 企业) 、评测中心已经超过t 3 0 0 家j 其中9 0 以上的中心都是近5 年建立的，每年这些企业可对数万个软件进行评测。随着我国从政府到企业对软件测试的认识不断加强，在今后几年内，软件测试服务将会有一个快速的发展。2 2 软件测试方法软件测试是一项复杂的系统工程，从不同的角度考虑可以有不同的划分方法，对测试进行分类是为了更好的明确测试的过程，了解测试究竟要完成哪些工作，尽量做到全面测试。目前主要的软件测试分类方法主要有以下三种，按照测试阶段划分，按照测试方法划分，按照是否运行被测软件划分：( 一)按阶段划分：按照软件开发完成后不同的阶段对测试方法可以划分为单元测试，集成测试，系统测试和验收测试。分别详细说明如下：单元测试是对软件中的基本组成单位进行测试，其目的是检验软件基本组成6北京邮电大学硕士学位论文件测试技术综述错误l 未找到引用源软单位的正确性。在公司的质量控制体系中，单元测试由产品组在软件提交测试部前完成。集成测试是在软件系统集成过程中所进行的测试，其主要目的是检查软件单位之间接口是否正确。系统测试：系统测试是对已经集成好的软件系统进行彻底的测试，以验证软件系统的正确性和性能等满足其规约所指定的要求。系统测试应该按照测试计划进行，其输入、输出和其它动态运行行为应该与软件规约进行对比，同时测试软件的强壮性和易用性。如果软件规约( 即软件的设计说明书、软件需求说明书等文档) 不完备，系统测试更多的是依赖测试人员的工作经验和判断，这样的测试是不充分的。验收测试是软件在投入使用之前的最后测试。是购买者对软件的试用过程。在公司实际工作中，通常是采用请客户试用或发布b e t a 版软件来实现。回归测试即软件维护阶段，其目的是对验收测试结果进行验证和修改。( 二)按测试方法划分：软件测试方法一般分为两种：白盒测试与黑盒测试。其中，白盒测试又称为结构测试，着重于程序的内部结构及算法，通常不关心功能与性能指标。黑盒测试又被称为功能测试、数据驱动测试或基于规格说明的测试，实际上是站在最终用户的立场上，检验输入输出信息及系统性能指标是否符合规格说明书中有关功能需求及性能需求的规定。白盒测试也称结构测试或逻辑驱动测试，是指基于一个应用代码的内部逻辑知识，即基于覆盖全部代码、分支、路径、条件的测试，它是知道产品内部工作过程，可通过测试来检测产品内部动作是否按照规格说明书的规定正常进行，按照程序内部的结构测试程序，检验程序中的每条通路是否都有能按预定要求正确工作，而不顾它的功能，白盒测试的主要方法有逻辑驱动、基路测试等，主要用于软件验证。黑盒测试是指不基于内部设计和代码的任何知识，而基于需求和功能性的测试，黑盒测试也称功能测试或数据驱动测试，它是在已知产品所应具有的功能，通过测试来检测每个功能是否都能正常使用，在测试时，把程序看作一个不能打开的黑盆子，在完全不考虑程序内部结构和内部特性的情况下，测试者在程序接口进行测试，它只检查程序功能是否按照需求规格说明书的规定正常使用，程序是否能适当地接收输入数锯而产生正确的输出信息，并且保持外部信息( 如数据库或文件) 的完整性。黑盒测试方法主要有等价类划分、边值分析、因果图、错误推测等，主要用于软件确认测试。( 三)按是否要实际运行被测软件：1 动态测试动态测试直接执行被测程序以提供测试活动，通过运行软件来检验软件的动7北京邮电大学硕上学位论文件测试技术综述错误l 未找到引用源软态行为和运行结果的正确性。动态测试工具具有功能确认、接口测试、覆盖率分析等功能。2 静态测试静态测试工具是在不执行程序的情况下，分析软件的特性。不编译运行程序，而是通过对程序源代码进行分析以发现其中的错误。静态分析主要集中在需求文档、设计文档以及程序结构上，可以进行类型分析、接口分析、输入输出规格说明分析等。常用的静态分析工具有：m c c a b e a s s o c i a t e s 公司开发的m c c a b ev i s u a lq u a l i t yt o o l s e t 分析工具；v i e w l o g 公司开发的l o g i s c o p e 分析工具；在软件测试文献中，有许多将动态测试与静态测试相比较的工作。这里引用有典型意义的b a s i l 和s c l b y 的实验数据【3 1 ，比较静态测试和动态测试的揭错能力该实验使用的静态测试方法是y o u r d e n 结构化走通法，使用的动态测试方法是功能测试方法和结构测试方法( 基于语句覆盖测试) 。实验结果如表2 1 ：表2 - 1 动态静态测试对比阶段1阶段2揭错评判标准测试方法平均值标准差平均值标准差静态测试4 1 01 9 33 0 02 2 0揭错个数功能测试4 4 51 7 03 7 71 8 3结构性测试3 2 81 6 73 0 81 8 9静态测试1 9 01 8 30 5 60 4 6揭错效率功能测试1 3 8o 9 01 2 2。0 9 1结构性测试1 4 0、0 8 71 1 80 8 4从上述表格静态动态测试对比中可以看到，动态测试与静态测试在发现错误的个数上相差无几，而在测试效率上动态测试低于静态测试。然而，在揭错能力稳定性的评判标准下，静态测试的标准差要高于动态测试，这意味着静态测试的稳定性、可靠性低于动态测试。因此，就目前技术来讲这两种方法各有优缺点，一个完成的成熟的测试过程应该是两者结合的。因为静态测试分析的目标不是证明程序完全正确，也不是要替代动态测试而存在，而是作为动态测试的补充，在程序运行前尽可能多的发现其中隐含的错误，提高程序的可靠性和健壮性，在一定程度上可以减少动态测试中发现的问题，降低测试成本和人力消耗。事实上，很多相当成熟的系统还包含错误，仅凭测试人员进行动态测试很难找出这些错误，而通过静态测试则已经发现了现存系统中的很多错误【4 】【5 】。因此，本论文主要对静态测试方法进行研究，并在下一节中详细介绍静态测试。8北京邮电大学硕士学位论文件测试技术综述错误l 未找到引用源软2 3 静态测试技术2 3 1 静态分析方法静态测试技术【6 l 是一种不通过执行程序而进行测试的技术，也就是说在不运行软件系统的情况下对软件系统进行静态的分析，以此来发现软件产品的缺陷的方法。静态测试包括代码检查、静态结构分析、代码质量度量等。静态测试使用静态分析技术，直接分析程序的源代码，通过词法分析、语法分析和静态语义分析，检测程序中潜在的安全漏洞。目前静态测试分析的方法主要有以下四种：1 符号执行符号执行的基本思想是，用抽象的符号表示程序中变量的值，来模拟程序的执行【7 】。该方法很好地克服了在静态测试时不能确定程序中变量的值的问题，常常在对路径敏感的程序分析中使用。优点在于它可以精确的静态模拟程序的执行，由于它跟踪了变量的所有可能取值，因此能够发现程序中细微的错误。但是在处理大程序时，程序执行的可能的路径数目随着程序尺寸的增大而呈指数级增长，在这种情况下就需要对路径进行选择，选取一定数量的路径进行分析。2 类型推导类型推导指的是由机器自动地推导出程序中变量和函数的类型。它在函数式程序设计语言中有着广泛的应用。其基本思想是程序中的数据可以依照一定的规则划分为不同的集合如果把每一个集合作为一种类型，就可以利用类型理论中的一些算法进行分析。例如可以将程序看作一个图，各结点通过加有控制流和数据流信息的边相连。图中的每个结点包含了计算出的变量的值若将结点依据一定的规则分组，每一组就是一个类型，由此就可以对程序中指针变量的别名等问题进行考察。上述类型推导适用于控制流无关的分析，具有很好的可扩展性，能够处理大规模的程序。但是它不能解决所有的问题。对于和程序控制流紧密相关的特性则需要引入子类型的概念，来描述类型问的包含关系。3 模型检测模型检测的基本思想是对于有限状态的系统构造状态机或者有向图等抽象模型，再对模型进行遍历以验证系统的某一性质，其难点在于如何避免状态空间爆炸。为此人们提出了多种方法，其中符号化模型检测方法是将抽象模型中的状态转换为逻辑公式，然后判定公式的可满足性。还可将模型转化成自动机，同时将需要检查的公式转换为一个等价的自动机，再将此自动机取补。这两个自动机的积就构成了一个新的自动机，则判定模型是否具有某一属性的问题就转换成检9北京邮电大学硕士学位论文件测试技术综述错误l 未找到引用源软查这个新自动机能接受的语言是否为空。4 基于规则的检查采用基于规则进行分析的系统的结构是：首先由一个规则处理器处理规则，将其转换为分析器能够接受的内部表示，然后再将其应用于程序的分析。在面向不同应用的程序中，常常隐含着各种不同的编程规则，例如要求在使用某一共享变量时最受“使用前先加锁，使用后解锁 的规则，所以我们提出了基于规则对多线程程序进行分析的方法。采用基于规则进行分析的系统的结构是：首先由一个规则处理器处理规则，将其转换为分析器能够接受的内部表示，然后再将其应用于程序的分析。此算法的具体实现为：读入源程序后首先获取词法和语法规则，定义抽象语法树的结构，编写相应的语法规则，进行词法和语法分析。在分析抽象语法树后得到一些辅助分析信息如：控制流图、定义使用链、相关函数的位置、相关变量的位置等。然后针对各种模式错误的分析算法，分析错误的模式，给出合适的错误模式的描述，给出分析结果。具体过程参见图2 1 。图2 - i 基于规则的检查算法流程图以上介绍的是在程序静态分析工具的构建中常用的四种静态分析方法，对于其具体优缺点分析可参见表2 2 。1 0北京邮电大学硕士学位论文件测试技术综述错误l 未找到引用源软表2 - 2 静态分析方法优缺点对比分析方法优点缺点符号执行可以精确的静态模拟程序的在处理大程序时，程序执行的可执行能的路径数目随着程序尺寸的增大而呈指数级增长，造成指数级时间和空间复杂度，这种精确分析很难扩展到大程序分析类型推导具有很好的可扩展性，能适用只适用于控制流无关的分析。于大规模的程序模型检测可以分析各类属性，更善于发分析成本昂贵，很难适用到大规现系统的复杂行为模的实际应用基于规则能够依据不同的规则对不同受到规则描述机制的局限，只能的检查的系统进行分析，发现大规模分析特定类型的错误程序中的潜在错误其中基于规则检查这种方法，可以依据不同的规则对不同的系统进行分析，相比于其它静态分析技术，具有更好的适用性和扩展性，所以本文基于规则检查这种技术研究了基于缺陷模式的软件测试方法。将在后面的章节中详细阐述。2 3 2 静态测试技术研究现状近年来软件测试技术得到快速的发展，大量的软件测试工具被研制出来从而可以自动地检测软件中的故障，并且在对一些大型商业软件和开源软件的测试中发现了大量的以前测试没有发现的软件故障和安全隐患。例如，s d v 在对w i n d o w s 操作系统1 2 6 个使用多年的驱动程序测试中发现了6 5 个故障，包括1 2个严重故斟5 j ；e x p l o d e 在一些常用的文件存储系统系统发现了大量的严重故斟8 j ；m c 在l i n u x 、o p e n b s d 和x o ke x o k e r n e l 软件中发现了近5 0 0 个故障【9 】以及1 0 0 多个安全漏洞【1 0 j 。f i n d b u g s 在e c l i p s e 、j 2 s e 和j b o s s 等开源软件中发现上百的故斟1 1 j 。但是有一些基本的问题依然没有得到很好地解决。1 误报问题。误报问题是基于模型的软件测试技术的一个共性问题。通常基于模型的软件测试技术都属于静态分析技术，由于某些故障的确定需要动态的执行信息，因此对于基于静态分析的工具来说，误报问题是不可避免的。故障的最后确认一般需要人工进行，因此如果口集合过大，测试的代价就可能无法忍受，所以要尽量缩减待确认的i p 集合。为此，有人提出，将动态测试与静态测试有机结合来解决误报问题【1 引。2 漏报问题。漏报问题主要由模型定义和模型检测算法引起。目前对于软件模北京邮电大学硕士学位论文件测试技术综述错误l 未找到引用源软式没有一个规范的、统一的和形式化的定义。不同的故障查找工具都给出自己所能检测的模型的定义，但是这些定义很多都是一些自然语言的描述，有的甚至只是给出一个简单的例子进行说明f 1 2 】【1 3 】f 1 4 】：同时，针对具体的软件模型，不同的检测工具一般设计自己的检测算法，从检测的效率和实现的复杂性上考虑，不同的算法给出不同的假设以降低计算复杂性，这导致对于相同的模型，用不同的工具进行检测得到的故障结果集合很大不同。文献【1 3 j 使用一些常用的j a v a 程序故障自动分析工具对e c l i p s e 、j d k 和j b o s s 等开源软件进行测试，发现不同的工具得到的检测结果集差别较大。使用我们开发的工具t g s o f m 和r e a s o n i n g 公司的工具对4 个软件项目约3 2 万行源代码关于内存泄漏和空指针引用故障进行测试，发现的故障集合也有所不同。3 模型机理。由于编程过程中，程序员具有较强的个体性，因此软件模型是多种多样的。通常软件中的故障主要来源于程序员，如错误的理解造成的、二义性造成的、疏忽造成的和遗漏造成的。国内有不少高校和研究所从事软件测试和形式验证及相关理论方面的研究工作，包括南京大学、国防科技大学、上海交通大学、华东师范大学0 同济大学、东南大学、北京航空航天大学以及中科院软件所等。但是，尚未见国产的基于模型的软件测试技术的商业化测试工具，目前国内测试中心使用的相关测试工具基本上都是从国外购置。因此，该课题研究了基于缺陷模式的软件测试方法，来降低误报率和漏报率，对于软件测试静态分析工具的研究与开发具有重要的意义。2 4 本章小结本章首先对软件测试进行了概述，从定义入手，尽管目前软件测试定义不一，但总体目标都是以提高软件的质量为根本目的，明确了软件测试的重要意义。然后，根据不同分类条件对软件测试方法进行了分类概述，并详细阐明静态分析方法在软件测试中的地位和主要研究方法，并介绍了目前国内外静态测试技术的研究现状。1 2北京邮电大学硕士学位论文的软件测试方法错误l 未找到引用源基于缺陷模式第三章基于缺陷模式的软件测试方法基于缺陷模式的软件测试方法是上一章中基于规则的检查这种静态分析方法的一种具体实现，它具有针对性强，识别率高，定位准确等特点。本章主要对该方法的概念和优势进行介绍，同时针对c + + ，c 语言进行了详细的缺陷模式总结和分类，并对其中的漏洞模式进行了详细的介绍和举例说明。本章总结的缺陷模式也为自动化测试工具c b f t 的设计和开发打下良好的理论基础。3 1 基于缺陷模式的软件测试方法概述由于软件的复杂性和软件缺陷的复杂性，传统的软件测试方法逐步显现出以下缺陷：自动化程度低，发现缺陷能力低，测试评估比较困难，小概率故障等检测效率很低，测试需要耗费大量的资源，需要很专业的测试人才等等。而基于软件缺陷模式的测试方法自2 0 0 0 年诞生以来，展现出强大的生命力和良好的测试效果，获得越来越多的关注与重视。虽然有很多科学家在软件的缺陷模式方面做了大量的工作，但收效甚微。这在很大程度上影响了软件测试技术的发展与进步。进入二十一世纪以来，随着社会对软件测试技术的需求越来越大，软件的质量越来越受到重视，软件的测试理论也得到快速发展，其中之一就是软件测试缺陷模式的研究取得了重要进展。2 0 0 0 年以来，基于缺陷模式的软件测试首先从美国发展起来，目前以此为基础开发的软件测试工具如k l o c k w o r k , i q a 等已经投入商业运营。其商业模式包括软件测试工具的销售和软件测试服务，目前，已经取得了很大的成功。与其他测试技术相比，基于缺陷模式的软件测试技术具有如下特点：1 针对性强：如果说某种模式的缺陷是经常发生的，并且在被测软件中是存在的，则面向缺陷的测试可以检测出此类缺陷。而不会像白盒测试和黑盒测试那样的不确定性。2 识别率高：基于缺陷模式的软件测试技术往往能发现其他测试技术难以发现的故障，如内存泄漏缺陷，空指针引用缺陷。3 故障检测效率以及自动化程度高。使用基于此方法自主开发的c b f t 系统，对a p a c h et o m c a tv 6 0 1 4 约3 0 万行源代码进行空指针引用缺陷测试，所耗时间只需几分钟。4 缺陷定位准确：对测试所发现的缺陷能够准确定位。1 3北京邮电大学硕士学位论文的软件测试方法错误l 未找到引用源基于缺陷模式5 易学、易使用：对一般的r i 专业专科以上的毕业生，该测试方法一般经过数天的培训即可掌握其使用方法。一种测试理论是否成熟的重要标志是测试对象是否有比较好的缺陷模式，因此在此技术中，缺陷模式的完备性成为非常重要的衡量标准。一般来说，缺陷模式必须满足下列几个条件：1 该模式下的缺陷是符合实际的。也就是说，该模式下所定义的缺陷在实际工程中是大量存在的。2 基于该模式的缺陷数目是可以容忍的。一般来讲，缺陷个数跟系统的规模成线性关系。3 该模式下的缺陷是可以测试的。存在一个算法，该算法是可以检测这些缺陷的。基于以上三种条件，本课题对缺陷模式进行了详尽的总结定义。3 2 缺陷模式概述缺陷模式是和语言本身相关的，由于c + + 语言的缺陷模式覆盖了c 语言，所以本节以c + + 语言为背景来描述其缺陷模式。这些缺陷模式是从大量工程实践中总结出来的，有很强的工程背景。根据大量的调研和总结，将软件的缺陷模式按照危害级别分为四个层次，即故障模式、漏洞模式、缺陷模式和规则模式。1 故障模式：此类缺陷是故障，一经产生，会导致系统出错。存储器泄露模式_ 资源泄漏模式指针使用错误模式一数组越界模式非法计算模式使用未初始化变量模式_ 死循环结构模式_ 死锁模式2 漏洞模式：此类缺陷会给系统留下安全隐患，使系统容易受攻击。一缓冲区溢出模式被感染的数据模式竞争条件模式风险操作模式3 缺陷模式：此类缺陷是不应该发生的，它未必会造成系统的错误，但可能会隐含某些故障，或者是由初级软件工程师不理解造成的。性能缺陷模式一疑问代码模式4 规则模式：软件开发总要遵循一定的规则，某个团队也有一些开发规则，1 4北京邮电大学硕士学位论文的软件测试方法错误l 未找到引用源基于缺陷模式违反这些规则也是不允许的。代码规则一复杂性规则控制流规则命名规则_ 可移植性规则_ 资源规则本文主要研究第二类缺陷模式中的漏洞模式，具体内容将在下一小节进行详细的介绍。3 3 漏洞模式该类模型为他人攻击软件提供可能。而一旦软件被攻击成功，系统就可能发生瘫痪，所造成的危害可能更大，因此，此类漏洞应当尽量避免，如：缓冲区溢出漏洞模型、被感染数据漏洞模型、竞争条件漏洞模型以及风险操作模型等。3 3 1 缓冲区溢出漏洞模型当程序要在一个缓冲区内存储比该缓冲区的大小还要多的数据时，即会产生缓冲区溢出漏洞。在缓冲区溢出的漏洞中，所要存储多余的信息，能够存储在缓一冲区的邻接区域内，从而破坏了原来存储在该区域的有效信息。虽然缓冲区溢出漏洞在一般的程序错误中也可能发生，但表现更多的是安全问题。在缓冲区溢出的攻击中，多余的信息可能包含诸如破坏用户文件，改变数据和泄露用户有用的信息等这样一些程序代码。在利用缓冲区溢出攻击时，这些额外的数据可能包含一些恶意代码，它可能会破坏用户文件，改写数据，或者窃取用户的隐私之所以能够利用缓冲区溢出进行攻击，是因为很多c c + + 的程序语言结构不能自动的进行范围检查，并且许多程序员对这个问题也没有给予足够的重视。缓冲区溢出主要有两种类型：大小和格式。前者主要是由于一个函数在拷贝数据的时候没有去检查缓冲区是否足够大。最主要的就是函数s t r c p y 0 和s t r c a t 0 ，这些函数都是将一组数据从一个源地址拷贝到目的地址( 也就是缓冲区) 。后者主要是由于函数在使用格式字符串将数据存储到缓冲区中，如果这个格式中允许太多的数据时，就会造成溢出。举例：s t a t i cv o i da d d p l u g i n s f r o m p a t h ( c o n s tt c h a r 奉p p h g i n s p a t h ，p l u g i 【n l o c a t i o n m a p r p l u g i n s ) 北京邮电大学硕士学位论文的软件测试方法错误l 未找到引用源基于缺陷模式t c h a ra r p l u g i n s p a t h m a x _ p a t h ；a r p l u g i n s p a t h 0 】= 0 ；i f ( ：r t l _ u s t r _ i n d e x o f s t r ( p p l u g i n s p a t h ，l ”p r o g r a m f d e s ”) = = 0 )c o n s tc h a r 掌p = ：g e t e n v ( ”p r o g r a m f i l e s ”) ；i f o u s t r i n ga s t r ( o u s t r i n g ：c r e a t e f r o m a s c i i ( p ) ) ；：l s t r c p y ( a r p l u g i n s p a t h ，a s t r g e t s t r 0 ) ；p p l u g i n s p a t h + = 1 4 ；在这个例子中，a r p l u g i n s p a t h 的值是m a x _ p a