（计算机科学与技术专业论文）基于扩展状态机的软件缺陷检测技术的研究与实现.pdf

独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：翻蛐同期：砷j 1 ) 。l 莎 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以 公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇 编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论文注 释：本学位 本人签 导师签 适用本授权书。 ：加州、钐 一 h 北京邮电人学硕l ：学位论文 摘要 基于扩展状态机的软件缺陷检测技术的研究与实现 摘要 伴随着信息技术的蓬勃发展以及软件危机的频频出现，软件测试的重 要性显而易见。作为软件测试领域的一个重要方面静态测试以其不用 运行程序而是只通过分析源代码查找错误的优点占据了重要的地位。基于 缺陷模式的软件静态分析技术是近年来发展起来的一种程序源代码静态测 试技术，其主要优势在于对缺陷的针对性强，而且可以检测出如空指针引 用等“小概率 缺陷。 基于缺陷模式的软件静态分析技术的核心便是如何描述和定义缺陷模 式以及如何设计高效统一的缺陷检测框架。针对上述问题，本文提出了使 用扩展的缺陷模式状态机进行缺陷检测的方法。论文的主要工作包括以下 几个方面。首先是缺陷模式状态机的研究与实现，主要深入研究了状态机 的基本结构组成、描述规则以及状态机的转换条件，并介绍了在应用缺陷 模式状态机进行缺陷检测时的一些相关研究，如路径敏感、不可达路径、 函数摘要等的分析，旨在提高检测的效率和精度。然后，重点介绍了如何 应用该统一的缺陷模式状态机框架进行具体的缺陷检测，给出了一些具体 缺陷模式的定义和描述，并重点设计了针对这些缺陷模式的检测算法。 基于缺陷模式的缺陷检测系统d t s c p p 应用本文的研究成果针对一些 具体的缺陷模式进行了检测，实验结果表明该系统具有较好的检测效果， 本文的研究成果为基于缺陷模式的静态分析技术的研究提供了有益的方法 和手段。 关键字：软件测试静态分析缺陷检测缺陷模式状态机函数摘要误报率 北京邮电人学顾： ：学位论文 摘要 北京邮电火学硕士学位论文 a b s t r a c t r e s e a r c ha n di m p l e m e n t a t l 0 no f s o f l w a red e f e ( 了rd e t e c t l 0 nt e c h n o l o g y b a s e d0 ne x t e n d e ds t p 江em a c h i n e a b s t r a c t w i t ht h ev i g o r o u sd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g ya n dt h ef r e q u e n te m e r g e n c eo f t h es o f t w a r ec r i s e s ，t h ei m p o r t a n c eo fs o f t w a r et e s t i n gi so b v i o u s a st h ei m p o r t a n ta s p e c to f t h ef i e l do fs e f t w a r et e s t i n g - s t a t i ct e s t i n gm e t h o do c c u p ya l li m p o r t a n tp o s i t i o nb e c a u s ei tc a n n o tr u nt h ep r o g r a mb u to n l yt h r o u g ht h ea n a l y s i so nt h es o u r c ec o d e s o f t w a r et e s t i n gb a s e d o nd e f e c tp a t t e r ni san e wk i n do fs o u r c ec o d es t a t i c a n a l y s i st e c h n o l o g y , i th a st w o a d v a n t a g e s o n ei st h a ti ti sv e r yp e r t i n e n tt op r o g r a md e f e c t s ；t h eo t h e ri st h a ti tc a nd e t e c t d e f e c t sw h i c hh a p p e ni nl o w e rp r o b a b i l i t ys u c ha sn u l lp o i n t e rd e r e f e r e n c e s o f t w a r es t a t i ca n a l y s i st e c h n o l o g yb a s e do nd e f e c tp a t t e r nm a i n l yi n c l u d e st w op a r t s o n ei sh o wt od e f i n et h ed e f e c tp a t e r n ，a n dt h eo t h e ri sh o wt od e s i g nau n i f i e da n de f f i c i e n t d e t e c t i o nf r a m w o r k a i ma tt h ep r o b l e ma b o v e ，am e t h o dt h a tu s e se x t e n d e dd e f e c tp a t t e m s t a t em a c h i n et od e t e c td e f e c t si sg i v e n t h em a i nc o n t r i b u t i o n sa r ea sf o l l o w s f i r s t l y , w e r e s e a r c ha n di m p l e m e n tt h ed e f e c tp a t t e r ns t a t em a c h i n e ，m a i n l yi n c l u d e st h eb a s i cs t r u c t u r e ， d e s c r i p t i o nr u l e sa n dt r a n s i t i o nc o n d i t i o no fs t a t em a c h i n e a tt h es a m et i m e ，i tg i v e ss o m e r e l e v a n tr e s e a r c ha b o u tp a t hs e n s i t i v e ，i n f e a s i b l ep a t ha n dp r o c e d u r a la b s t r a c tw h i c hc a n e n h a n c et h er e s u l to fs t a t i cd e t e c t i o n t h e n ，s o m ec o n c r e t ed e f e c tp a t t e r n sa r eg i v e na n dw e d e s i g nt h ed e t e c t i o na l g o r i t h mo nt h e s ep a t t e r n s ，m a i n l yf o c u so nh o wt oa p p l yt h eu n i f i e d d e f e c tp a t t e r ns t a t em a c h i n et op r a c t i c a la p p l i c a t i o n s t h ed e f e c td e t e c t i o ns y s t e md t s c p pb a s e do nd e f e c tp a t t e r nu s e so u rr e s e a r c hf o rs o m e d e f e c t sd e t e c t i o n ，a n dt h ee x p e r i m e n ts h o w st h a tt h i ss y s t e mh a ss a t i s f i e dt e s t i n gr e s u l t ，a n d o u rr e s e a r c hp r o v i d e su s e f u lm e t h o d sa n da p p r o a c h e sf o rt h es t a t i ca n a l y s i st e c h n o l o g yb a s e d o nd e f e c tp a t t e r n k e yw o r d s ：s o f t w a r et e s t i n g , s t a t i ca n a l y s i s ，d e f e c td e t e c t i n g , p r o c e d u r a la b s t r a c t ，d e f e c t p a t t e r ns t a t em a c h i n e ，f a l s ep o s i t i v e i i i 北京邮i 乜人学硕l ：学位论文 a b s t r a c t i v 3 1 系统简介1 l 3 2 系统总体设计1 1 3 2 1 系统总体构成。1 1 3 2 2 系统执行流程1 2 3 3 系统模块介绍1 3 3 3 1 抽象语法树1 3 3 3 2 基于控制流图的区间运算。1 4 3 3 3 函数调用1 6 3 3 4 基于函数摘要的全局分析1 6 3 3 5 缺陷模式状态机。1 7 第4 章扩展的缺陷模式状态机1 8 4 1 缺陷模式状态机基本结构1 8 4 2 缺陷模式状态机转换条件2 3 4 2 1 x p a t h 条件2 3 4 2 2 变量区间条件2 4 4 2 3 变量作用域条件2 5 4 3 缺陷模式描述。2 5 4 4 缺陷模式分析2 8 v 北京邮f 乜人学硕二i ：学位论文 目录 4 4 1 路径敏感。2 9 4 4 2 不可达路径分析2 9 4 4 3 函数摘要的使用。3 1 4 5 附录：f s m x s d 状态机描述模板3 2 第5 章缺陷模式检测。3 5 5 1 通用结构和算法3 5 5 2 内存泄漏3 6 5 2 1 内存泄漏具体模式分类。3 6 5 2 2 内存泄漏设计策略4 0 5 2 3 内存泄漏检测状态机。4 0 5 3 空指针引用4 2 5 3 1 空指针引用具体模式分类4 3 5 3 2 空指针引用设计策略4 7 5 3 3 空指针引用检测状态机4 7 5 4 非法计算4 9 5 4 1 非法计算具体模式分类4 9 5 4 2 非法计算设计策略5 0 5 4 3 非法计算检测状态机。5 0 5 5 实验数据5 l 第6 章结论5 3 6 1 研究工作总结5 3 6 2 展望5 3 参考文献5 5 致谢5 7 作者攻读学位期间发表的学术论文目录5 8 v l 北京邮电人学硕七学位论文第1 章绪论 1 1 研究背景 第1 章绪论 伴随信息技术的蓬勃发展，计算机处理速度的飞速提高，以及内存和外存容量的 快速增加，软件的地位越来越重要，软件的功能也越来越强大，软件的规模和复杂性 也日益庞大和增加，开发人员在开发过程中由于没有完全理解软件需求或个人局限性 等因素，导致软件的质量保证变得至关重要。由于软件危机的频繁出现，随着软件工 程技术的发展，软件测试的地位也越来越重要，近年来备受关注。根据b o e h m 的统 计，在软件开发总成本中，用在测试上的开销要占3 0 至1 j5 0 1 1 1 。对于某些关系人类 生命安全的关键软件，其测试费用甚至高达所有其他软件工程阶段费用总和的三到五 倍。因此，软件测试是软件生命周期中非常复杂的工作，对于提高软件的正确性和可 靠性有着重要的意义，而提高软件测试的有效性和测试效率，降低软件开发成本已成 为迫切需要解决的任务。 软件测试的目的是为了发现软件中的错误1 2 j ，软件的错误存在于软件生存期的各个 阶段，不同阶段的错误性质不同，亦对应着不同的测试方法，但基本上从是否要实际 运行被测软件来分，可分为动态测试和静态测试。动态测试只存在于软件生存期的编 码阶段之后，通过运行软件来检验软件的动态行为和运行结果的正确性。而静态测试 则相反，其基本特征是在对软件进行分析、检查和测试时不实际运行被测试的程序， 因而在软件开发过程的早期阶段，静态测试的作用尤为重要。就目前技术来讲这两种 方法各有优缺点，因此一个完成的成熟的测试过程应该是两者结合的，才会使错误检 测的效果更好。 随着传统的软件测试技术的不断发展，近年来人们提出了许多新的软件测试方 法，如面向缺陷的软件测试、面向对象的软件测试、软件可靠性测试等【2 1 。本文所研究 的基于缺陷模式的软件静态分析技术就是面向缺陷软件测试的理论基础，其基本方法 是不用运行实际软件，而是通过对源代码的分析找出其中已定义的故障模式。近几 年，静态分析技术也逐渐受到操作系统、信息安全等领域学者的高度重视。 1 2 研究内容 基于以上的研究背景，本文的研究工作主要围绕着基于源代码和缺陷模式的静态 分析技术，旨在通过对可编译通过的源代码进行词法分析、语法分析、抽象语法树生 成、符号表生成、区间运算、控制流图生成、跨函数分析、函数摘要生成、缺陷模式 状态机设计等模块1 3 硼，最后生成输入源代码中存在的潜在缺陷模式，该缺陷模式是预 北京0 瑕电人学硕j 二学位论文第1 章绪论 先定义的，并且具有可扩充性和可定制性。本文所研究的内容主要包括以下几个方 面： ( 1 ) 软件缺陷模式的描述和定义 面向故障的软件测试不是传统意义上的针对整个软件系统，而是针对具体缺陷 的，包括两个重要的方面：一是缺陷模式，二是基于该模式的检测方法。其中软件的 缺陷模式是该检测技术的重点之一，是影响该技术发展的主要因素。缺陷模式需要大 量的实际经验以及大量的资料参考进行归类总结，不同缺陷的具体形态也会干差万 别，因此如何用一个统一的方法进行缺陷模式的描述是亟待解决的问题。有了对缺陷 模式的描述和定义的统一的方法，有利于不断引入新的缺陷模式，提高该检测技术的 检测能力。 ( 2 ) 软件缺陷模式的检测框架 对于已经定义的缺陷模式集合，如何从源代码中将具体的缺陷模式检测出来? 针 对常用的编程语言，如何设计一个统一的通用的检测过程模型，使之具有可扩展性， 对于不同的缺陷模式只需要架设在这个统一的过程模型上设计不同的检测算法即可。 在已经实现了的检测算法必须的基本模块如词法和语法分析、抽象语法树、符号表等 的基础上，提出了一种定义和描述具体缺陷模式的扩展的有限状态自动机，即缺陷模 式状态机。状态机是对程序语义的一种常用和易于理解的抽象表示，对于描述具体的 缺陷模式和按照该模式进行缺陷分析具有实际意义。 ( 3 ) 软件缺陷模式的检测 对缺陷模式进行了描述和定义后，如何应用统一的通用的检测模型进行具体缺陷 模式的检测算法的设计是基于缺陷模式的软件静态分析技术的最后一步，是该检测技 术的关键所在。因此本文针对一些具体的缺陷模式如内存泄漏、空指针引用以及非法 计算给出了检测算法的设计。同时，在检测过程中如何保证检测效率和提高检测精度 也是我们需要重点考虑的问题，这需要我们在上述提到的统一的检测框架上引入相关 方法的研究，如对路径敏感、不可达路径和函数摘要的分析，着重提高针对具体缺陷 模式的检测效果。 1 3 论文内容和结构 本文首先对软件测试的基本概念以及测试方法进行了介绍，重点介绍了静态分析 技术的原理和意义，并对基于缺陷模式的软件测试中的若干关键技术进行了研究。论 文共包括6 章，本章是第一章，作为全文的绪论，说明论文的研究背景和研究内容， 第6 章是结束语，总结全文，并给出本文研究工作的不足之处以及前景展望，其他4 章的内容如下： 2 北京邮电大学硕十学位论文第1 章绪论 ( 1 ) 软件测试( 第2 章内容) 本章全面的介绍了软件测试的基本概念，包括软件测试的定义、软件测试的过程 和方法、软件测试工具以及软件测试的意义，并对软件静态分析技术的原理和技术方 法进行了综述，本章是后续章节所介绍的研究内容的理论基础。 ( 2 ) d t s c p p 系统介绍( 第3 章内容) 本章简要地概括了基于缺陷模式的缺陷检测系统d t s c p p 。d t s c p p 主要是针对 c + + 源程序进行缺陷分析，主要组成部分包括：抽象语法树、控制流图、符号表、函 数调用关系、区间运算、函数摘要、缺陷模式状态机计算、数据库访问、缺陷分析等 主要模块。 ( 3 ) 扩展的缺陷模式状态机( 第4 章内容) 本章主要介绍了定义和检测具体缺陷模式的统一框架：缺陷模式状态机计算单 元。d t s c p p 采用扩展了的状态机对故障模式进行无二义性地统一描述，在对源程序进 行分析的时候，在控制流上按照设计统一的缺陷模式状态机的状态转换条件进行状态 转换的计算从而完成对具体缺陷模式的检测。 ( 4 ) 缺陷模式检测( 5 章内容) 本章在基于上述章节的理论以及分析的基础上，介绍了在软件中普遍存在的几种 具有代表性的缺陷模式，给出具体的检测算法以及检测流程，并给出实验结果，表明 基于扩展的缺陷模式状态机的缺陷检测方法有着实际可行的意义。 3 北京邮电人学硕i ：学位论文 第2 章软件测试 2 1 软件测试概念及意义 第2 章软件测试 软件测试就是在软件投入运行之前，对软件需求分析、设计规格说明和编码的最 终复审，是软件质量保证的关键步骤，贯穿于软件定义与开发的整个期间【1 1 。m y e r s 认 为：“程序测试是为了发现错误而执行程序的过程”，该定义明确给出了软件测试就是 为了发现软件中的错误。1 9 8 3 年i e e e 给出的定义是：“使用人工或自动手段来运行或 测定某个系统的过程，其目的在于检验它是否满足规定的需求或是弄清楚预期结果与 实际结果之间的差别”。应该说该定义是比较全面的。上述两个定义都是以检验软件是 否存在错误为目的，也可以说是一种正确性测试。除此之外，软件测试还应包括可靠 性测试、健壮性测试、性能测试、效率测试等。 软件测试在软件生存期中横跨两个阶段：通常在编写出每一个模块之后就对它做 必要的测试( 称为单元测试) 。编码与单元测试属于软件生存期中的同一个阶段。在结 束这个阶段之后，对软件系统还要进行各种综合测试，这是软件生存期的另一个独立 的阶段，即测试阶段1 5 l 。 软件测试是在一个可控的环境中分析或执行程序的过程，其根本目的是以尽可能 少的时问和人力发现并改正软件中潜在的各种故障及缺陷，提高软件的质量。测试者 希望通过软件测试来提高软件的质量或可靠性。这就意味着要发现并改正程序中的错 误。所以，进行测试时不应该为了显示程序是好的，而应该从“软件中含有故障 这 个假定出发去测试程序，从中发现尽可能多的软件故障。因此，“一个好的测试用例在 于发现至今尚未被发现的故障 ，“一个成功的测试是发现了至今未被发现的故障的测 试”。 软件测试在软件生存期中占有非常突出的重要位置，其重要意义在于： ( 1 ) 减少软件的缺陷数目或者降低软件的缺陷密度：通过测试可以发现软件中存 在的缺陷，通过完全的修改这些缺陷，可以减少软件中缺陷的总数目或者降低其缺陷 密度。 ( 2 ) 提高软件的可靠性：软件的缺陷数目是影响软件可靠性的主要因素，通过测 试减少软件的缺陷数目可以达到提高软件可靠性的目的。 ( 3 ) 评估软件的性能指标：通过软件测试，根据所发现的缺陷数目和发现缺陷的 时间，可以评估软件的可靠性等指标。即使软件测试没有发现缺陷，也同样可以达到 这个目的。 4 北京邮电大学硕上学位论文 第2 章软件测试 ( 4 ) 增加用户对软件的信心。软件通过了何种测试对用户来说是非常重要的，严 格的软件测试可以加大用户对该软件的信心。 2 2 软件测试方法 软件的错误存在于软件生存期的各个阶段，不同阶段的错误性质是不同的，不同 的错误对应了不同的测试方法。本节所述的各种测试方法就是根据上述问题而发展起 来的。有些方法是通用的，例如静态分析技术，在软件生存期各个阶段的错误检测中 都可以使用，而有些方法只是某个阶段才能使用，例如，动态测试技术，只有当程序 出来以后才能进行动态测试。不同的测试方法对各个阶段错误检测的效率也是不同 的，有些时候，在同一阶段，当各种方法组合使用时，错误检测的效果会更好。 ( 1 ) 静态分析方法 静态分析方法1 6 l 的基本特征是在对软件进行分析、检查和测试时，不实际运行被测 试的程序。在软件开发过程中的早期阶段，代码尚未产生，无法进行动态测试，因此 静态分析的作用尤为重要。而且因为静态分析主要是面向文档和源程序，不用实际执 行去分析，因此，静态分析要比动态测试成本低，容易实现而且不依赖于程序特定的 运行环境。静态分析的范围和内容很多。大体可分为基于文档的测试和基于代码的测 试。本文所研究的内容属于基于源代码的静态分析范畴。 ( 2 ) 动态测试方法 动态测试，就是通过运行软件来检验软件的动态行为和运行结果的正确性。因 此，动态测试只存在于软件生存期的编码阶段之后。动态测试包括两个基本要素：一 是被测程序，二是用于运行软件的数据，称为测试数据，程序一次运行所需要的测试 数据称为测试用例，所以测试数据是测试用例的集合。 动态测试发展近三十年来，由于有其比较强的错误检测能力，受到人们的普遍重 视，产生了许多测试方法。按照产生测试数据以及判断测试充分性的方法，可以分为 结构性测试、排错性测试、分域测试和功能测试；按照产生测试数据所根据的信息来 源，可以分为以程序为基础的测试、以需求和功能的规约为基础的测试、程序和需求 相结合的测试，以及以界面为基础的测试。 ( 3 ) 其它测试方法 传统的测试方法还包括黑盒测试和白盒测试方法。黑盒测试又称功能测试、数据 驱动测试或基于规格说明的测试，测试者只需知道程序的输入和输出之间的关系即 可。白盒测试又称结构测试、逻辑驱动测试或基于程序的测试，测试者需要知道被测 程序的内部构造并对其做到一定程度的覆盖。近1 0 年来，许多新的软件测试技术也应 5 北京邮i 乜大学硕十学位论文 第2 章软件测试 运而生，主要有面向故障的软件测试方法、面向对象的软件测试方法、软件可靠性测 试与排错性测试以及软件测试性分析技术等等。 2 3 软件测试工具 根据软件测试种类的不同以及测试方法的多样，对应了不同的软件测试工具，图 2 1 给出了具有代表性的软件测试工具，并图示了这些测试工具和软件生存期中测试活 动的关系。 图2 - 1 软件测试工具分类 下面将对具体的软件测试工具给予详细的介绍。 ( 1 ) 白盒测试工具 白盒测试工具是基于源代码的，需要测试者理解代码实现的功能以及代码的结构 并做到逻辑上的全覆盖。根据测试工具原理的不同，可分为静态分析工具和动态测试 工具。 静态分析工具 静态分析工具不需要编译、连接并运行源代码，而是直接对源代码进行分析。静 态分析工具一般是对代码进行语法扫描，找出不符合编码规范的地方，根据某种质量 模式评价代码的质量，生成系统的调用关系图等。静态分析工具的代表有t e l e l o g i c 公 司的l o g i s c o p e l 7 l 软件、p r 公司的p r q a 软件、m a c a b e 公司的m a c a b e 等。 动态测试工具 动态测试工具一般采用“插桩 的方式，向代码生成的可执行文件中插入一些监 测代码，用来统计程序运行时的数据。与静态分析工具最大的不同就是动态测试工具 6 北京邮电人学硕f ：学位论文 第2 章软件测试 要求被测系统实际运行。动念测试工具的代表有c o m p u w a r e 公司的d e v p a r t n e r 软件、 r a t i o n a l 公司的p u r i f y 系列1 8 1 、n u m e g a 中的b o u n c e c h e c k e r 等 ( 2 ) 黑盒测试工具 黑盒测试工具适用于黑盒测试的场合，黑盒测试工具包括功能测试工具和系统测 试工具。黑盒测试工具的一般原理是利用脚本的录制和回放，模拟用户的操作，然后 将被测系统的输出记录下来同预先给定的标准结果比较。黑盒测试工具可以大大减轻 黑盒测试的工作量，在迭代开发的过程中，能够很好地进行回归测试。 黑盒测试工具的代表有i b mr a t i o n a l 的t e a m t e s t 、r o b o t ，c o m p u w a r e 公司的 q a c e n t e r 、m i 公司的w i n r u n n e r 等工具，另外，专用于系统测试的工具包括有m i 公 司的l o a d r u n n e 9 、i b mr a t i o n a l 的q u a n t i f y 、r a d v i e w 公司的w e b l o a d 、m i c r o s o f t 公司的w e b s t r e s s 等工具。 ( 3 ) 测试管理工具 测试管理工具用于对测试进行管理。一般而言，测试管理工具对测试计划、测试 用例、测试实施进行管理。而且测试管理工具还包括对缺陷的跟踪管理。测试管理工 具的代表有m i 公司的t e s t d i r e c t o r l l 0 1 、r a t i o n a l 公司的t e s t m a n a g e r 、c o m p u r e w a r e 公 司的q a d i r e c t o r 和t r a c k r e c o r d 等软件。 ( 4 ) 专用测试工具 专用测试工具是用于某一专门应用领域或某些特殊用途的测试工具，针对w e b 应 用的有w o r k b e n c h 、w e b a p p l i c a t i o ns t r e s s t o o l ( w a s ) 、m i 公司的a s t r a 系列；数据 库测试工具t e s t b y t e s i l l 】以及嵌入式测试工具t e s tr e a l t i m e 、c o d e t e s t 等。 ( 5 ) 测试辅助工具 这类工具跟测试过程相关，帮助测试人员更有效地进行测试。如s m a r t d r a w 用于 绘制u c m l ，进行负载压力测试需求分析，有助于测试前的准备工作；s d e m o 将测试 过程中的操作录制成可执行文件文件，并回放出来，可以避免一些偶尔才出现的错 误。 2 4 基于缺陷模式的静态源码分析技术 所有基于缺陷模式的静态源码分析技术【1 2 1 4 】的共同点是都不用实际运行被测程 序，而是通过对源代码的词法、语法和静态语义的分析，对源代码进行适当的建模， 并设计一个检测框架以及检测算法，根据已经定义好的缺陷模式进行状态计算，最终 报告给用户源代码中存在的缺陷。 基于缺陷模式的缺陷检测技术是以软件静态分析为理论基础。因此下述部分详细 7 目前，静态分析主要有以下几种检测方法【1 5 l ： ( 1 ) 模型检测：模型检测是一种验证有限状态的并发系统的方法，基本思想是对 于有限状态的系统构造状态机或者有向图等抽象模型，再对模型进行遍历以验证系统 的某一性质【瑚。 ( 2 ) 符号执行：符号执行测试是一种静态的白盒测试技术。符号执行是一种符号 化定义数据，并为程序每条路径给出符号表达式，对特定路径输入符号，经处理输出 8 北京邮电大学顾j j 学位论文第2 章软件测试 符号，从而判断程序行为是否错误，达到分析错误目的。 ( 3 ) 类型推断：程序语言的类型系统，包括一套定义类型的机制，一套有关类型 等价、类型相容和类型推理的规则。类型推断是一个处理过程，其目的是保证每个操 作都是针对一组数目正确，类型合适的对象进行，以保证操作的有效性。 ( 4 ) 数据流分析：数据流分析【1 7 】是一项编译时使用的技术，它能从程序代码中收 集程序的语义信息并通过代数的方法在编译时确定变量的定义和使用。数据流分析被 用于解决编译优化、程序验证、调试、测试、并行、向量化和串行编程环境等问题。 数据流分析是通过对变量构造定义一引用对来实现的。 ( 5 ) 约束分析：约束分析方法将程序分析过程分为约束产生和约束求解两个阶 段，前者利用约束产生规则建立变量类型或分析状态之间的约束系统，后者对这些约 束系统进行求解。 2 4 3 静态分析的不足 静态分析最终要依靠人工来确认。因此，故障发现的多少完全依赖于测试的组织 和测试者的水平。从目前静态分析的效果来看尚存在如下的一些问题【列。 ( 1 ) 认识不足。特别是决策者的认识不足。但这种情况正在改变。 ( 2 ) 测试的问题太多，不知从何处下手。解决这个问题的办法是可以对静态测试 的范围和内容进行分门别类的测试，效果可能会更好。 ( 3 ) 自动化或半自动化的测试工具是必须的。 ( 4 ) 开发的软件缺少静态分析所必须的文档。 静态分析另外一方面的缺点是性能不足。静态检测的精确度同运行时间和空间消 耗成j 下比，因此，提高检测质量的同时会增加运行成本。 衡量静态分析技术有2 个重要的指标： ( 1 ) 漏报率( f a l s en e g a t i v er a t e ) ：指软件中实际存在的但是未检测出来的缺陷数占 软件中存在的所有缺陷的百分比。 ( 2 ) 误报率( f a l s ep o s i t i v er a t e ) ：指运用检测技术检测出来的但是并非软件中实际 存在的缺陷占软件中存在的所有缺陷的百分比。 降低其中之的同时往往会造成另外一个指标的增高。因此需要在软件的漏报率 和误报率之间达到一个平衡点，使系统既能满足用户的需求报告出尽可能多的正确的 缺陷，同时又不至于有太多的误报而使检测结果集过于庞大导致用户不能容忍。 9 北京邮f 乜大学硕+ 上学位论文 第2 章软件测试 2 4 4 缺陷模式 软件的缺陷模式【1 3 l 一直是基于源代码的静态分析工具的重要内容，是制约软件测 试技术发展的主要因素。考虑程序是软件的具体表现，所以为了便于测试，其定义的 缺陷模式必须落实到实际的程序上。基于此定义的缺陷模式必须满足下列几个条件： ( 1 ) 缺陷必须是和实际是对应的。也就是说，实际软件中存在大量这种缺陷，而且所 提出的缺陷模式能覆盖大多数实际存在的缺陷。( 2 ) 缺陷必须能引起错误。一旦该缺 陷被执行且产生的变异能传播到程序中的某个输出，则程序的结果必然是错误的，或 者说程序的行为是错误的。( 3 ) 缺陷的个数是可以容忍的。缺陷的个数一般和程序的 规模是线性关系，个数太多，难以实现，以至无法实用。 只要缺陷模式的定义符合实际、可测试而且精确，就可以根据这些定义的缺陷模 式来设计各种算法对它们进行检测。根据缺陷对软件影响的严重程度，本文所研究的 内容将软件的缺陷模式分成四大类1 1 8 】：故障模式、安全漏洞模式、疑问代码模式及规 则模式，其中每个大类对应若干缺陷子类，每个子类针对特定的缺陷。 ( 1 ) 故障模式 故障一经产生会导致系统崩溃，该类模式是引起错误的常见缺陷模式，应该尽量 避免。主要包括内存泄漏模式、资源泄漏模式、空指针使用错误模式、数组越界模 式、非法计算模式、使用未初始化变量模式、死循环结构模式和死锁模式等。 ( 2 ) 安全漏洞模式 软件的安全漏洞会给系统留下安全隐患，导致系统被攻击。该类模式为他人攻击 软件提供可能，一旦软件被攻击成功，系统就可能发生瘫痪，所造成的危害可能更 大，因此，此类缺陷应当尽量避免。安全漏洞模式主要包括未验证的输入模式、滥用 a p i ( a p p l i c a t i o np r o g r a m m i n gi n t e r f a c e ) 模式、安全功能部件模式、竞争条件模式、 不合理的异常处理模式、缓冲区溢出模式、代码质量模式和封装不当模式等。 ( 3 ) 疑问代码模式 疑问代码是指执行效率比较低及让人费解的代码，此类模式不会产生故障或安全 隐患，但在软件动态运行时效率比较低下，因此建议采用更高效的代码来完成同样的 功能。主要包括低性能模式、死码模式和不良习惯模式等。 ( 4 ) 规则模式 软件开发的过程中往往要遵循一定的编码规则，此类缺陷是指不符合规则的代 码。编码规则主要包括命名规则、复杂性规则、控制流规则、可移植性规则和资源规 则等。 1 0 北京邮电大学硕十学位论文 第3 章d t s c p p 系统介绍 3 1 系统简介 第3 章d t s c p p 系统介绍 d t s c p p ( d e f e c tt e s t i n gs y s t e mf o rc p l u sp l u sl a n g u a g e ) t 3 - 4 1 1 1 8 1 系统全名是基于缺 陷模式的缺陷检测系统，它是d t s 的重要组成部分，是北京邮电大学网络与交换技术 国家重点实验室自主研发的新型软件测试工具，主要是针对c + + 源程序的面向缺陷分 析检测。其主要组成部分包括：抽象语法树生成；控制流图生成；符号表生成：函数 调用关系生成；区间运算；全局分析；函数摘要生成；缺陷模式状态机计算；数据库 访问；缺陷分析等。其主要对外连接关系包括：用户配置要分析的缺陷模式及其相关 描述文件，相关描述文件包括模式定义和描述文件以及模式动作文件；用户指定要分 析的目标源代码；d t s c p p 将发现的缺陷检查点填写入数据库以方便界面程序进一步的 显示和分析。 系统的功能是根据给定的要分析的缺陷模式及其相关描述文件，对目标c + + 代码 进行自动分析，查找目标c + + 代码中潜在的符合缺陷模式描述的检查点，并将检查点 信息写入数据库报告给用户。 3 2 系统总体设计 3 2 1 系统总体构成 d t s c p p 系统的总体设计框架主要分为抽象语法树生成、控制流图生成、符号表生 成、区间运算、函数调用关系生成、全局分析、函数摘要生成、缺陷模式状态机计 算、缺陷分析等模块，具体的组成以及依赖关系如图3 - 1 所示。 北京邮电人学硕i ：学位论文 第3 章d t s c p p 系统介绍 ( ， ，一、 卜， 用户 缺陷分析 ，盯7 ，7 誓 ，| 7 i 一、 f ，之，。，。：7 ，二7 7 7 7 。+ 上、! | ( f ：7 ，7 、，、? ：i 乒! ，、 ，尹，卫、j 一， ：l f ， 7 ，i 。， 、 ，3 乒f 一一 、 ，：7 、f ， 、 一。：磊0 、 麦函 函孟曩成 du和喇_i主i、j，、lj：二3iii7)、函芡：酽生成 ，一、1 、 i1 1 二，7 | 一。：渺- ， ( 17 一一。 、 控；赢量扑、 i ，, 广麓裹三 控制流图生成 j1。二i 二：。 3 2 2 系统执行流程 图3 一id t s c p p 软件单元组成 d t s c p p 对输入源代码进行分析，经过上述提到的各种模块的基本变换和计算，最 终输出代码中的缺陷给用户，其基本的执行流程如图3 2 所示。 1 2 北京g i l + ) u , 人学硕1 ：学位论文 第3 章o t s c p p 系统介绍 f 。_ _ 。_ 。_ _ 。一_ 1 。_ _ 。_ _ - 。_ - 。_ 输入的待分析的源程序 词法和语法分析 上 抽象语法树生成 控制流图生成 0 全局类型信息牛成 函数调用图和依赖关系生成 j 区倒运算 缺陷模式描述文件 函数摘要生成 i， 缺陷模式状态机计算 il 缺陷报告数据库访问 3 3 系统模块介绍 3 3 1 抽象语法树 图3 2 系统执行流程图 程序的语法树是一种树的数据结构，该数据结构准确地说明按照语法怎样看待程 序的各个部分，语法树可以通过语法分析过程得到。完全符合文法规格要求的分析树 对于进一步处理并不是最适合的，实际中，经常会根据需要对语法树做适当的简化和 修改，这种修改后的形式，称为抽象语法树( a s t , a b s t r a c ts y n t a xt r e e ) 0 9 l 。 图3 3 是对应表达式b * b 4 * a * c 的分析树，表达式所用的文法与j a v a 语言相似： e x p r e s s i o n _ e x p r e s s i o n 4 - t e r mle x p r e s s i o n 一t e r mit e r m t e r m _ t e r mq f a c t o rlt e r m f a c t o rlf a c t o r f a c t o r _ i d e n t i f i e ric o n t a n ti ( e x p r e s s i o n ) 1 3 系统介绍 流图中 数为基 系控制 算f 2 l 】将 计算单 下面给出了一个简单的程序片段，该程序片段生成的带区间运算信息的控制流图 如图3 5 所示。 l ：v o i dt e s t o 2 ：i n tv a r = l ； 3 ： v a r + + ； 4 ： v a 卜； 5 ： ) 1 4 北京邮电人学硕：l ：学位论文 第3 章d t s c p p 系统介绍 图3 - 5 基于控制流图的区间运算实例 区间运算的目的是对程序中出现的变量和表达式的取值范围进行估计，为进一步 的程序分析提供精确的信息支持。区间运算是在对控制流图进行遍历的同时利用访问 者模式进行计算，近似模拟每一个变量在程序执行过程中的取值范围，不同的数据类 型有不同的区间定义。缺陷模式状态机计算单元状态计算过程中将利用变量的区间信 息。 1 5 北京邮电人学硕十学位论文 第3 章d t s c p p 系统介绍 3 3 3 函数调用 函数调用在源代码中是普遍存在的，许多信息都会通过参数或者返回值在函数间 进行传递，得到这些信息的前提是正确分析出函数调用关系，因此生成函数调用图【2 2 l 会提高分析的精确性。 图3 7 函数调用图实例 针对上述图3 6 程序实例，其函数调用图如图3 7 所示。由实例可分析，将函数 g e t p o i n t e r 0 的返回值应用到u s e p o i n t e r 2 0 中，分析到这里的时候必须要用到u s e p o i n t e r 0 的信息，即在分析u s e p o i n t e r 2 0 之前必须尽可能的对u s e p o i n t e r 0 进行了分析。可见，在 分析函数处理的次序关系的时候就需要用到函数调用关系。本文所研究的函数调用关 系是全局的，即包