（计算机科学与技术专业论文）面向java的跨函数分析技术.pdf

l 弋 独创性( 或创新性) 声明 舢| f f 删f f | 舢f y 17 5 9 6 9 3 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意 申请学位论文与资料若有不实之处， 本人签名：叠复缝 本人承担一切相关责任。 日期：垄! 坐盥垒望一一 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅：学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 日期：筮坦生丛垒璺 日期： 丝! 垒垒! 旦垃尽 a ，i | 北京邮电大学硕仁学位论文 摘要 面向j a v a 的跨函数分析技术 摘要 本文介绍了作者在跨函数分析研究方面所做的工作，包括跨函数 分析技术的设计与实现以及对现有d t s j a v a ( d e f e c tt e s t i n gs y s t e m f o rj a v a ) 系统的改进，将跨函数分析模块与区间运算模块结合，针 对资源泄漏缺陷实现检测算法，从应用角度验证了d t s j a v a 跨函数分 析技术。 d t s j a v a 是一个以数据流分析为核心、以抽象解释和模型检查辅 助的通用的软件缺陷静态检测系统。它将软件故障抽象为缺陷模式状 态机，故障构成因素表示为状态，构成因素的时序关系表示为状态之 间的转换。缺陷模式分析的过程是沿着控制流按状态机的转换条件进 行状态计算。如果实际导致状态转换的源代码不在同一函数中而是通 过函数调用，那么称为多个函数构成的故障。已有的d t s j a v a 检测系 统关注整个系统框架的设计与实现，不具备多函数故障的检测能力。 与著名的软件测试工具k l o c w o r k 的对比发现，多函数故障在d t s j a v a 的漏报中占很大比例。 为了提高故障覆盖率，本文提出面向故障的函数摘要概念，将跨 函数分析分为收集和应用函数摘要两阶段。系统提供抽象定义，故障 检测算法实现函数摘要的提取方法和应用方法。根据用途的不同，本 文设计了三种函数摘要：前置条件p r e c o n d i t i o n 、后置条件 p o s t c o n d i t i o n 和函数特征f e a t u r e 。前置条件是避免程序故障必须 满足的限制，后置条件表示函数对调用者上下文环境的影响( 如变量 值) ，函数特征表示对故障检测状态机的影响( 如文件操作) 。 最后针对资源泄漏故障模型，本文实现一种跨函数分析检测方 法，通过实验从应用的角度证明d t s j a v a 跨函数分析模块的价值。 关键词软件测试静态分析缺陷模型跨函数分析函数摘要 。l 一 北京邮电人学硕上学位论文 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 i o no f i n t e r - p r o c e d u r a la n a l y s i sf o r j a v a i nt h i st h e s i s ，w ew i l li n t r o d u c et h er e s e a r c hw o r ko ni n t e r - p r o c e d u r a l s t a t i ca n a l y s i s ，i n c l u d i n gt h ed e s i g na n di m p l e m e n t a t i o no ft h ef r a m e w o r k , t h e i n t e g r a t i o n w i t hi n t e r v a l a r i t h m e t i c ，t h ea p p l i c a t i o no fo u r i n t e r - p r o c e d u r a lf r a m e w o r k d t s j a v a ，d e f e c tt e s t i n gs y s t e mf o rj a v a ，i sag e n e r a ls o f t w a r es t a t i c t e s t i n gs y s t e m , t a k i n gd a t af l o wa n a l y s i s ，a b s t r a c ti n t e r p r e t a t i o n ，m o d e l c h e c k i n ga st h e o r e t i c a lf o u n d a t i o n s i nd t s j a v a ，s o f t w a r ed e f e c t sa t e d e s c r i b e da sf a u l ts t a t em a c h i n e si nw h i c hs t a t e sa r ef a c t o r so fs o f t w a r e d e f e c t sa n dt r a n s i t i o n sa r et i m i n gr e l a t i o n so ft h e s ef a c t o r s t h ea n a l y s i s e n g i n eo fd e f e c tt e s t i n gc o m p u t e ss t a t et r a n s i t i o n sa c c o r d i n gt of a u l ts t a t e m a c h i n e s i ff a c t o r sa r ed i s t r i b u t e di ns e v e r a if u n c t i o n s ，w es a yt h e r ei sa i n t e r - p r o c e d u r a ld e f e c t d t s j a v af o c u so nt h ef r a m e w o r ko ft h es y s t e m a n dc a nn o tf i n di n t e r - p r o c e d u a ld e f e c t s i no r d e rt oi m p r o v ed e f e c tc o v e r a g e ，w ep r e s e n ta ni n t e r - p r o c e d u a l a n a l y s i sf r a m e w o r kb a s e do nd e f e c to r i e n t e df u n c t i o ns u m m a r y o u r i n t e r - p r o c e d u r a l f r a m e w o r kc o n t a i n se x t r a c t i o na n d a p p l i c a t i o n o f f u n c t i o ns u m m a r i e s i no u rf r a m e w o r k , w ed e s i g nt h r e ek i n do ff u n c t i o n s u m m a r y p r e c o n d i t i o ns u m m a r yi ss e to fc o n d i t i o n sw h i c hm a yl c a dt o a ne r r o r p o s t c o n d i t i o ns u m m a r yd e s c r i b e sc o n t e x tc h a n g e st ot h ec a l l e r f e a t u r e s u m m a r yr e p r e s e n t sd e f e c t - r e l a t e d o p e r a t i o n s ，s u c h a sf i l e o p e r a t i o n f i n a l l y , w ep r e s e n ta ni n t e r - p r o c e d u r a lr e s o u r c el e a kt e s t i n gm e t h o d e x p e r i m e n t ss h o wo u rm e t h o de f f e c t i v ea n ds c a l a b l e k e yw o r d ss o f t w a r e t e s t i n g s t a t i ca n a l y s i sd e f e c tm o d e l i n t e r p r o c e d u r a la n a l y s i s f u n c t i o ns u m m a r y i i 3 1 1 数据流分析12 3 1 2 模型检查14 3 1 3 抽象解释15 3 2缺陷模式状态机1 6 3 2 1 缺陷模式状态机定义16 3 2 2 路径敏感缺陷与非路径敏感故障1 7 3 2 3 变量相关检测与资源相关检测18 3 3d t s j a v a 系统结构1 8 3 3 1 设计思想2 0 3 3 2 抽象语法树2 1 3 3 3 控制流图2 2 3 3 4 区间运算2 3 3 3 5 缺陷模式分析引擎2 4 第四章跨函数分析2 8 4 1函数间的软件故障2 8 4 2 两种跨函数分析算法2 9 4 2 1 完全上下文敏感的函数间分析2 9 4 2 2 基于特征信息的跨函数分析3 1 6 2 下一步工作_ 5 1 参考文献5 2 术语缩略语5 4 1 改谢! ；! ； 作者攻读学位期间发表的学术论文目录5 6 北京g 1 9f p _ , 大学硕l 二学位论文第一章绪论 1 1 课题背景 第一章绪论 随着信息技术的发展，计算机软件在当今社会发挥越来越重要的作用。国家 安全、航天航空、金融经济、电子商务等领域都有各种各样的软件发挥着重要的 作用同时，各个行业对计算机软件的质量也提出了更高的要求。 为了满足对软件质量的要求，软件可靠性成为近些年来学术界研究的重点一 一如何用尽量低的成本保证软件的高质量。软件运行的正确与否影响到人们的正 常生活，软件的失效甚至会引发巨大的损失。软件测试是保证软件质量的重要手 段。其实软件测试是伴随着软件而产生的，有了软件，便有了软件测试。但在早 期的软件开发过程中，软件规模都很小、复杂程度低。软件测试的概念很狭窄， 经常与调试混为一谈。甚至在现在。软件测试仍然被一些人低估。在过去，不论 是软件开发者还是用户，往往关注软件的功能性，即是否完整实现客户的功能需 求，而忽略软件的可靠性、可维护性、安全性。近十年，人们才逐渐意识到软件 测试不仅仅是软件开发中的补充，而且是软件开发中必不可少的一个环节。 软件测试是一项非常困难复杂而且成本很高的工作。随着技术不断发展，软 件的复杂度越来越高软件复杂性由两方面的含义，一是软件开发的代码量越来 越大，动辄上百万行的代码；二是软件模块结构越来越复杂，没有节制的软件复 用使得软件维护越来越难，为软件可靠性埋下了安全隐患。无论是测试时间和测 试资源的耗费，软件测试都达到整个软件项目的3 0 - 5 0 p a 上i 。一位合格的软 件测试工程师需要深刻理解项目需求，参与整个项目设计，阅读大量的源代码， 并且思考项目实际运行环境中的各种可能发生的情况，采取合适的方式，设计相 应的测试用例。不论是采取哪一种测试方法，这些都是不可避免的。 目前软件测试遇到的主要问题有： 1 软件规模越来越大，需要耗费的时间和精力呈指数级增长。 2 传统的人工测试方法难以保证测试的准确性，由于人为因素难免存在明 显的漏测，使软件质量难以提高。 3 软件体系结构复杂，使测试人员无从下手，导致测试效果不佳。 4 自动化测试工具准确率不高，检测能力有一定局限性，难以应用于大型 项目复杂功能的测试，可作为人工测试的补充手段。 1 2 研究目的和意义 随着软件规模日益增长，传统人工测试方式难以满足这种日益增长的需求。 代码故障，而无法检查软件是否满足项目需求分析，这需要测试工程师编写特定 的自动测试程序，来进行大规模自动化测试。 软件故障可能由一条语句构成，也可能由分布于不同函数的多跳语句构成。 如果构成故障的代码在一个函数内，那么通过简单的数据流分析方法就可以检测 故障。如果故障出现在多个函数中，就必须使用函数间分析技术。函数间分析是 来自编译领域的技术，常用于计算函数间的指针分析、代码优化等等。 已有的d t s j a v a 检测系统关注整个系统框架的设计与实现，不具备多函数 故障的检测能力。与著名的软件测试工具k l o c w o r k 的对比发现，多函数故障在 d t s j a v a 的漏报中占很大比例。因此，对跨函数分析技术的研究能够提高d t s j a v a 系统的分析检测能力 1 3 主要内容 本文介绍了在跨函数分析研究方面所做的工作，包括跨函数分析技术的目 的、设计、实现，并对资源泄漏缺陷模式进行研究，实现资源泄漏检测算法，提 2 北京邮电人学硕二 ：学位论文第一章绪论 高软件测试的精度 首先，本文详细介绍国内外软件测试方向的研究现状，对当前测试方法和工 具进行总结，指出传统软件测试方法在测试效率和覆盖率上存在的缺陷。 然后，阐述如何将静态分析技术应用于软件测试研究，介绍本文的研究环境 面向j a v a 的缺陷监测系统d e f e c tt e s t i n gs y s t e mf o rj a v a ( d t s j a v a ) 2 ，并指 出当前静态分析技术面临的检测准确率的问题。 为了提高静态分析技术的准确率，本文提出了跨函数分析的方法，检测多个 函数构成的软件故障，并将其实现为d t s j a v a 系统的模块。针对j a v a 语言典型 的故障模型资源泄漏，提出基于跨函数分析技术的检测算法，取得了较好的 效果。 最后总结本文的研究工作，提出下一步研究的展望。 1 4 论文结构 本论文由六章构成，详细探讨了d t s j a v a 面向缺陷软件测试系统、跨函数 分析检测方法和j a v a 语言两种典型代码缺陷的检测算法。除了绪论和总结以井， 其它章节的简介如下。 第二章软件测试技术 本章将对当前软件测试的相关研究和技术发展进行介绍，包括：白盒测 试与黑盒测试、静态测试与动态测试。 第三章面向缺陷的静态分析工具 ， 本章对静态分析与软件测试的结合进行了探讨，并详细介绍面向缺陷的 软件测试系统d t s j a v a 。 第四章跨函数分析 本章提出一种跨函数分析算法，根据函数特征信息信息抽象函数功能， 避免嵌套控制流图的指数爆炸问题，提高d t s j a v a 所能检测故障的覆盖率。 第五章跨函数分析应用于资源泄漏软件故障 7 本章针对资源泄漏j a v a 语言代码缺陷，提出资源泄漏检测算法，并 且基于d t s j a v a 系统实现检测算法 3 可理解性：软件开发文档必须清晰地描述软件开发成果，易于理解。 可维护性：能够方便升级满足新的应用需求软件设计为升级做好铺垫。 可测试性t 过度复杂的软件设计可能导致软件无法测试。 其它质量特性。 概括地说，软件质量就是“软件与显式以及隐式定义的需求相一致的程度”。 具体地说，软件质量是软件符合明确叙述的功能和性能需求、文档中明确描述的 开发标准、以及所有专业开发的软件都应具有的隐含特征的程度。 软件测试是保证软件质量的重要手段，用于确定开发的软件系统的正确性， 完备性以及软件质量。软件测试能够发现错误，但无法证明软件中不存在错误， 不能保证绝对正确性。尽管在软件测试定义上存在许多不同见解，但对软件测试 的目的理解却都是一致的，即强调对软件正确性的保证。 软件测试是对系统或程序的执行以期发现其中的错误，是为了检查程序中的 错误而进行的一项复杂而艰难的工作。软件测试的经典定义是：在规定的条件下 对程序进行分析，发现程序错误，度量软件质量，并评估是否满足设计要求的过 程。i e e e 将软件测试定义为：“使用人工或自动的手段运行或测定某个软件系统 4 一 广 北京邮电大学硕+ 学位论文第二章软件测试技术 的过程，其目的在于检验它是否满足规定的需求或弄清预期结果与实际结果之间 的差别”。软件测试的目的是为了检验软件系统是否满足需求，不是一次性的仅 限于软件开发后期的活动，而是与整个开发流程融为一体。 软件测试另一个问题是软件测试的复杂性，由软件的复杂性所导致。软件中 的错误数量总是与软件设计复杂性和代码量成正比，这一性质并不是由工程师的 技术水平所决定，而是由于软件固有的复杂性所导致。当软件程序超过一定的复 杂性后，程序中的错误几乎是不可避免的对于任何一种检测软件错误的方法， 总是存在由于该方法所不能检测到的错误。因此，软件测试需要对不同的测试方 法进行研究，了解和掌握它们的优点和局限性，很多时候需要组合多种不同的方 法来提高程序错误的检测能力，这些都会增加软件测试的困难。 2 1 2 软件测试发展 软件测试是保证软件质量的重要手段。其实软件测试是伴随着软件而产生 的。在过去，不论是软件开发者还是用户，往往关注软件的功能性，即是否完整 实现客户的功能需求，而忽略软件的可靠性、可维护性、安全性近十年，人们 才逐渐意识到软件测试不仅仅是软件开发中的补充，而且是软件开发中必不可少 的一个环节。 在早期的软件开发过程中，软件规模都很小、复杂程度低，软件测试的概念 很狭窄，经常与调试混为一谈。在1 9 5 6 年以前，计算机软件技术才刚刚起步 几乎没有软件测试的概念，当时对测试的定义基本上等同于程序的调试1 5 j ，由开 发者在编写程序后进行这项工作。这是和当时的机器语言程序开发模式相对应 的。在1 9 4 9 年和1 9 5 0 年，著名的计算机科学家阿兰图灵发表了两篇论文，主 题分别是“正确性的证明”和“如何确定程序具有智能 如果我们要开发一种 具有智能的软件系统，那么我们如何证明软件系统满足我们的需求呢? 图灵定义 了一种验证智能行为的测试，这就是著名的图灵测试。1 9 5 7 年c h a r l e sb a k e r 在 一篇评论中将“调试一与“测试区分开来。他认为软件开发应该有两个目标： 一是确保程序能够正常运行；一是使程序能够j 下确地解决问题。其中“使程序运 行 属于软件调试的目的。但测试主要靠经验，没有统一的理论方法，所以软件 质量难以保证。随着计算机应用软件在数量、成本以及复杂性上不断增长，软件 测试只益得到重视。 随着软件工程研究发展，软件测试形成相对独立的理论体系作。此时，出现 两种对软件测试的理解。软件测试领域的先驱b i l lh e t z c l 定义：“软件测试是评 价软件系统、确定是否达到预期的目标而进行的一系列活动一。他的思想的核心 观点是：测试方法是试图验证软件是按照预先的设计执行的，针对所有功能点逐 个验证其正确性。软件测试把这种方法看作是的软件测试的第一类方法。 5 图2 1 软件开发v 模型 本文研究的静态分析检测技术是专门针对代码的，也就是对编码步骤的输出 结果进行检测，相当于v 模型中的单元测试步骤。在单元测试过程中，我们需要 从三个角度进行测试，即功能性、鲁棒性、高效性。功能性是指模块完成详细设 计要求的具体功能，能够对输入数据按要求进行计算。由于软件模块可能运行在 一些苛刻的环境中，可能遇到预料之中甚至预料之外的异常故障，而鲁棒性就是 要求软件能够对这些异常情况作出适当的处理，如终止运行、向运维人员报警、 处理异常继续运行，这样能够保证系统具有更高的可靠性。高效性是指系统能够 在大数据量、高负载的情况下正常地响应用户请求。 本文的研究工作侧重于代码的单元测试，下面将介绍一些单元测试常用的测 试方法。 6 一 ，、 北京邮l 乜大学硕l ：学位论文 第二章软件测试技术 2 2 1 黑盒测试与白盒测试 按照是否根据代码的具体实现设计测试方案这一标准，单元测试可分为：黑 盒测试、白盒测试。黑盒测试是一种根据详细设计对模块的功能点、输入输出限 制等要求设计测试用例，并通过执行程序验证模块是否存在故障的方法自盒测 试是一种根据模块详细设计和实现代码，按程序逻辑设计测试用例的方法除了 上述两种方法之外，还有一种称为“灰盒测试的方法 1 黑盒测试 黑盒测试嘲也称为功能测试，对软件是否满足功能需求进行验证。这种测试 方法不需要考虑程序内部逻辑流程，关注模块的功能需求和输入输出要求约束。 一般来说黑盒测试是一种针对模块结构的测试，检查代码是否按照详细设计接受 输入数据按要求产生正确的输出数据。在理想情况下，穷举所有可能的输入数据， 检验程序是否能够产生相应正确的输出数据，穷举测试固然能够保正程序1 0 0 的正确性然而，在实际情况下，不可能对任意一个程序模块都进行穷举测试， 无法枚举出所有可能情况。因此，我们一般从输入数据的测试全集中，选取具有 代表性的测试实例，每一个测试实例都能代表一类测试数据，尽可能地覆盖测试 全集。常用的黑盒测试方法有：边界值分析、等价类划分、按经验推测法。 图2 - 2 黑盒测试 2 自盒测试 白盒测试1 6 i 是根据详细设计和实现代码的具体逻辑流程，检验程序每一条执 行路径是否符合模块的功能需求。这种方法允许了解程序内部逻辑设计测试方 案，理想情况下可以检查程序的每一条执行路径，因此这种测试往往比黑盒测试 更具针对性，测试人员也可以在阅读代码过程中直接发现代码故障。 北京邮电大学硕十学位论文 第二章软件测试技术 与黑盒测试相似，如果枚举每一条可能执行的程序路径，这也是一个穷举测 试。黑盒测试根据功能需求和约束条件设计测试方案，力求穷举所有可能的输入 数据验证输出数据；白盒测试根据详细设计和实现代码设计测试用例，尽可能覆 盖每一条可能的执行路径。 f u n c t i o n ：c a l c u l a t e p a r a m s ：( i n ta ，i n tb i n to p ) r e t u r n ：i n t d e s c r i p t i o n ： i f o p = o r e t u r na + b ； i f o p 。1 ，r e t t t l aa - b ； i f o p 42 r c t u f l la 岫； i f o p = 3 ，r e t u r na b ； 陌习 f 0 麓3 豳豳豳囱 图2 - 3 白盒测试 3 灰盒测试 灰盒测试是一种介于黑盒测试和白盒测试之间的测试方法，关注输出对于输 入的正确性，同时也关注程序的内部表现，但这种关注不像白盒测试那样详细、 完整，只是通过一些表征性的现象、事件、标志来判断内部的运行状态。为了设 计测试用例灰盒测试方法允许了解内部数据结构和算法，也可以站在用户角度 进行黑盒测试。有时程序输出是正确的，但内部逻辑其实是错的，如果每次都通 过白盒测试来检测，工作效率会很低。 2 2 2 静态测试与动态测试 根据是否需要运行被测代码，软件测试可以分为静态测试和动态测试。静态 测试是指在不执行代码的情况下，对模块进行分析以发现代码故障的过程。而动 态测试则必须运行程序代码，在执行过程中发现软件故障的过程。 2 2 2 1 静态测试 在计算机领域，静态测试是一种在不执行程序的情况下对程序行为进行分析 的技术。静态测试，也称为静态分析，一般用来形容自动化工具的分析，而人工 分析则往往叫做程序理解。而动态测试则是另外一种程序分析策略，需要实际执 行程序。静态测试通过对程序源代码进行分析从而发现其中的错误，是一种高效 且低成本的测试方法。在开发过程中，被测软件的很多功能尚未实现，编译整个 模块或搭建模块运行环境需要耗费大量测试资源。静态测试能够在模块编译、执 行之前就能够发现并修正一些代码问题，虽然并不保证发现所有问题，也能够提 高测试工作的效率。静态测试工具可以提取代码的行为信息检测软件的代码故 障，具有自动化程度高、检测速度快以及代码覆盖率高等优点。 根据分析对象不同，静态测试分为源代码分析和目标代码分析。在大多数情 8 北京邮电大学硕十学位论文第二二章软件测试技术 况下，静态测试的输入是源程序代码，只有少数情况会使用目标代码。 静态源代码分析 源代码分析是针对开发者编写的代码，在未编译之前对其进行分析以求发现 代码中的故障。如k l o c w o r k 扫描j a v a 、c + + 程序源代码检测程序故障。静态源 代码分析的优点： 1 分析方法通用性高，多种不同的编程语言的语法不同，核心特征相似。 2 当发现故障时，源代码分析可以将故障定位到源代码文件中的一行或多 行代码，便于验证和修改故障。 3 可以按编码风格检查源代码，了解程序员的最基本意图。 缺点在于 1 源码分析必须依赖于预先定义的错误模式。 z 产生大量误报，所以需要人工验证。 静态目标代码分析 源代码经过编译器或解释器的处理生成目标代码。目标代码分析主要针对经 过编译器编译或解释的目标代码。如f i n d b u g s 扫描j a v a 字节码检测程序故障。 静态目标代码分析的优点： 1 检测“所见非所执行，类型的漏洞与源代码相比，目标代码更能体现出 程序如何执行。由于编译器进行优化，源代码和目标代码可能不一致。 2 不依赖于软件源代码，能够为没有源代码或私有程序检测故障。 3 可以处理内嵌汇编的情况。如c 语言的内联汇编功能。可以c 代码中可以 编写汇编代码，获取更高地执行效率。 缺点在于： 1 发现故障无法定位到源代码的具体位置。 2 丢失程序的变量信息和类型信息。 2 2 2 2 动态分析 动态分析需要编译并运行被测软件或模块，以发现故障为目的进行的测试工 作动态测试通常需要测试用例作为输入，检测软件或模块能否正确处理数据产 生符合要求的输出结果。另一种方法是在被测代码中嵌入测试代码，收集代码运 行中的信息，实时记录下软件执行的故障。 作为面向代码的测试方法，静态测试只能检测代码中存在的故障一是否存 在内存泄漏、空指针引用等故障，不能通过输入测试数据产生输出数据，所以无 法确定被测代码是否符合详细设计的功能需求，同样不能检测详细设计是否存在 逻辑错误。 9 x m l 文件的方式进行管理。由于面向j a v a 字节码，使得该工具难以移植到其它 语言，基于j a v a 字节码也使得其能够检测的缺陷模式受限。 1 0 北京邮电大学硕十学位论文第三章面向缺陷的静态分析t 具 第三章面向缺陷的静态分析工具 静态分析是编译器领域的技术，应用于编译器中的代码优化。软件测试领域 引入静态分析技术后，推动了自动化测试工具的发展。 静态分析指的是在不执行被分析程序的情况下对代码进行评估的过程。从可 计算性理论的角度来看，静态分析是一个不可判定问题。1 9 5 3 年h c n r yr i c e 提 出著名的r i c e 定理1 7 l ，r i c e 定理表明：静态分析不能完美地确定一般程序的任 何非平凡属性。这并不意味着静态分析没有价值。静态分析的不可判定性只是意 味着任何自动化静态分析系统，针对程序的非平凡属性( 如是否存在运行时错 误) ，不可能做到既是可靠的也是完备的。实际上人们可以采取如下近似：尽量 保证可靠性减少漏报( f a l s en e g a t i v e ) ，而对完备性放松限制允许误报 ( f a l s ep o s i t i v e ) 。静态分析可靠性是指如果分析结果未得到运行时错误，则程序肯 定不存在该类型运行时错误静态分析的不可判定性，也是其分析结果需要人工 确认的根源 d t s j a v a ( i ) e f e c tt e s tin gs y s t e mf o rj a v a ) 是一款通用的软件缺陷监测系 统，总结了常见的软件缺陷，将其抽象为有限状态机的形式，并且为具体故障的 检测提供了数据流分析、抽象解释、模型检查等功能结构使得测试工程师能够 集中精力研究软件缺陷，以较快地速度实现软件缺陷检测。 本章详细介绍面向缺陷的静态分析系统d t s j a v a 以及相关的静态分析技术。 3 1d t s j a v a 理论基础 。 d t s j a v a 是以数据流分析为核心，辅以抽象解释和模型检查，实现一个通用 的软件缺陷静态检测平台。其中，d t s j a v a 的检测过程是以数据流分析实现，区 间运算是以抽象解释为理论基础，故障检测的理论依据是模型检查。 图3 1i ) t s j a v a 理论依据 本节主要介绍d t s j a v a 的理论依据。 北京邮电人学硕十学位论文第三章面向缺陷的静态分析t 具 3 1 1 数据流分析 数据流分析【8 ( d a t af l o wa n a l y s i s ) 是程序分析中的传统方法，用于计算被分 析程序的每个程序点的数据流信息。这种数据流信息是一种运行时状态属性的近 似表示，包含该程序点所在基本代码块对于所有可能的输入数据所表现出的运行 时状态的属性。在数据流分析中，程序被转换为控制流图的形式。控制流节点是 对应基本代码块，基本代码块是指不存在条件分支、跳转的语句。 图3 2 数据流分析层次示例 局部数据流分析l o c a l ：在基本代码块中，所有语句都严格按顺序执行，不会 中途跳转到其它代码块。 全局数据流分析g l o b a l ：在一个函数或过程内部，基本代码块之间可以通过 控制流边进行控制传递。 函数间数据流分析i n t e r p r o c e d u r e ：通过函数调用语句，可以把不同的函数连 接起来，组成函数间控制流图。 数据流分析使用基于方程的约束求解系统，这些约束是无条件的，称为数据 流方程。进行数据流分析的最简单方法是对每个控制流节点建立数据流方程，然 后通过迭代计算反复求解，直到到达不动点。在前向流分析( f o r w a r df l o wa n a l y s i s ) 中，一个基本块的输入数据和输出数据构成一个映射，程序中的每个基本块都能 1 2 北京邮电大学硕士学位论文第三章面向缺陷的静态分析t 具 够看作以数据流信息为参数的函数，语句对数据流信息的操作构成函数的功能。 这样可以对每个基本块建立数据流方程： 对于基本块b a s i cb l o c kb ： i n p u t b 盘u 眶删( 6 ) o u t p u t p o u t p u t 厶盘b l o c k f u n c t i o n 6 ( i n p u t s ) 其中，b l o c k f u n c t i o n 6 是基本块b 对应的转移函数，以为i n p u t 6 输入参数， 计算得到输出状态o u t p u t n 1 n p u t 。是基本块b 的输入数据流信息，通过将b 的 所有前趋节点pe p r e d ( b ) 的输出数据流信息合并起来，得到l n p u t 。 求解这些方程后，基本块的输入状态l n p u t 。和输出状态o u t p u t 。可以用来获 得程序在当前基本块b 的数据流信息。每条语句的b l o c k f u n c t i o n 。函数可以被分 别用于获得在一个基本块内的某一点的信息。 前向数据流分析的函数入口控制流节点没有前趋节点，其输入状态的数据流 信息在分析开始时是默认的。如果控制流图不包含显式或隐式的循环，只需直接 求解数据流方程即可，对控制流图的节点进行拓扑排序，按照捧序后的结果依次 计算，则每个块的输入状态都可以在访问节点之前获得，因为拓扑排序保证所有 前趋节点都已经计算，所以它们的输出状态是可以获得的。如果控制流图包含循 环那么就需要进行多次迭代，直到数据流信息到达一个稳定点 3 1 1 1 流敏感 流即是数据流。流敏感分析是在计算程序中某一点的数据流信息时，必须考 虑程序执行的先后顺序，依据该点之前数据流信息计算当前点，不需要考虑数据 流信息来自哪条执行路径。数据流分析具有流敏感特性，可以计算指针信息 非流敏感是指在计算数据流信息时，语句的先后顺序不会对数据流产生影 响，也就是说每个程序点的数据流信息都是相同的。在别名分析中，非流敏感分 析也具有重要地位。 3 1 1 2 路径敏感 在静态分析中，我们会把程序源代码以函数为单位转换为控制流图的形式。 控制流图由一个四元组表示 。其中v e x s e t 表示所 有控制流节点的集合，每个控制流节点对应程序中的一段代码；e d g e s e t 表示所 有控制流边，控制流边是有向边，由一个控制流节点指向另一个控制流节点： s t a r t 表示控制流图的入口节点，一般表示函数入口；e n d 表示控制流图的统一 出口节点，如果函数有多个出口( 如r e t u r n 、t h r o w ) ，将这些出口点连接到e n d ， 使e n d 作为实际出口点的后继。 路径是描述程序执行过程的控制流节点序列。一个控制流图可能构成的路径 与程序潜在的执行过程一一对应，即程序执行的每一种情况都能够对应到一条执 北京邮电人学硕二 ：学位论文 第三章面向缺陷的静态分析r t 具 行路径。 路径敏感分析是指在数据流分析过程中，我们不仅关系程序代码执行顺序， 而且也要考虑控制流节点上的数据流信息分别来自哪一条执行路径，这样可以更 准确地进行数据分析从上述描述可以看出，路径敏感比流敏感分析能力更强， 准确率更高。非路径敏感分析则是不考虑路径问题的分析方法，大多数情况下非 路径敏感分析也就是指流敏感分析。 3 1 1 3 上下文敏感 上下文环境是指函数调用发生时，存储在进程调用栈中的函数调用返回点列 表以及当前作用域中各变量的取值信息。 上下文敏感分析：如果分析过程中遇到函数调用分析程序要将当前的上下 文环境传递到被调用函数，然后分析被调用函数，最后返回函数调用点，将分析 被调用函数所得信息更新到当前上下文环境。非上下文敏感分析不关心函数调用 发生时的上下文环境，因此可能造成误报。 函数自j 数据流分析可以是上下文敏感或者非上下文敏感。一般的完全上下文 敏感分析的运行效率低，大多数实际应用都是用有条件限制的上下文敏感分析算 法。 3 1 2 模型检查 自动验证一个软件或硬件系统的行为是否与预期的性质相符合是计算机领 域的一个根本问题。模型检查【9 i ( m o d e lc h e c k i n g ) 技术就是针对这个问题提出的 解决方案之一。自1 9 8 1 年问世以来，模型检查技术已经取得了许多突破性的进 展，逐渐成为保证计算机系统可靠性的重要手段。程序正确性的形式验证依靠数 学逻辑的推导。程序是一种复杂的、不易理解的行为，而数学逻辑能够精确地描 述这些行为。过去人们倾向于正确性的形式证明，演绎证明方法使用公理和推论 规则，使得很短的程序需要冗长的证明过程。 模型检查方法避开了正确性证明的思路，用时态逻辑来描述程序执行过程中 的属性变化。如果一个程序可以用时序逻辑来描述，那么我们可以用有限状态自 动机来实现它。模型检查是检验一个有限状态图是否一个符合时态逻辑规范的模 型。模型检查接收一个系统s 行为的状态转换模型m 和一个需要检查的属性p 作为输入。接下来尝试遍历m 中所有的路径并在每个可能到达的状态检查属性p 是否满足。模型检查中所针对的模型m 可以是一个非常高层的代表系统行为的 设计模型，也可以是程序源代码或控制流图，也可以是非常底层的代表系统行为 的实际执行机器码。模型检查中的属性p 作为一个时序属性，也可以由不同的形 式来进行表示，例如：有限状态机、正则表达式、一个逻辑断言等。 模型检查的难点在于如何避免可达状态空间爆炸，而对于基于控制流的模型 检查，所谓的可达状态空问爆炸实际上就是程序路径组合爆炸。模型m 的可达 状态空间必须是有限的或者在抽象的基础上能转化为有限的，以保证分析过程能 1 4 北京邮电大学硕：l 学位论文 第三章面向缺陷的静态分析t 具 够最终终止。 当前应用于软件的模型检测方法主要有两大类：基于程序语言转换的模型检 测和基于自建模型的模型检测。基于程序语言转换的模型检测方法是程序转换为 现有通用模型检测工具的输入语言，然而由于现有模型检测工具的输入语言和实 际程序语言的巨大差别，语言转换技术有很大的局限性，只能分析和转换短程序， 转换过程需要大量的人工修改。基于自建模型的方法直接分析程序源码形成系统 模型肼，并在m 上进行检查。常用典型的模型如：u m l 图、控制流图等。d t s j a v a 采用后一种方法，建立的程序模型即控制流图。 3 1 3 抽象解释 抽象解释( a b s t r a c ti n t e r p r e t a t i o n ) ；是静态分析的主要分析方法之一，几乎任何 静态分析方法都会涉及到一些抽象解释的范畴。抽象解释理论1 1 0 l 是c o u s o t p 和 c o t t s o t r 于1 9 7 7 年提出的。其过程是用一个抽象对象域上的计算代替具体对象 域上的计算，并使抽象计算的结果能够反映分析目标所关心的程序实际执行信 息。由于静态分析本质上是一个不可判定问题，因此抽象解释通常是程序实际语 义的近似，但它是保守的近似，即保证可靠性但不要求完备性。抽象解释所计算 的语义，称作抽象语义。例如：对于数值型变量，用变量取值区间来代替集合语 义中各变量的取值点集合。抽象解释计算过程中先将对象的实际语义映射到抽 象语义进行计算，再将抽象语义的计算结果映射到实际语义 程序代表某个数据域上的一系列计算，如果只关心程序执行的某一方面属 性，那么就可以在另外一个数据遇上执行程序中的计算，每种计算在新的数据遇 上被赋予了新的语义如1 7 1 7 宰1 5 ，如果只关心计算结果是正负号，那么就可 以定义数据域 + ? ，于是1 7 1 7 1 5 就变成了( + ) 幸( + ) ，乘号的语义就变成了“同 号为正，异号为负 对于1 7 1 7 + 1 5 变成( + ) + ( + ) ，结果是可正可负的，因为我 们感兴趣的程序执行时属性，一般都是不可判定问题，可以通过抽象解释的方法 得到近似结果 静态分析是抽象解释的一种具体化。在对程序的静态分析中，使用抽象解释 的基本方法，最为典型的就是数据流分析另外，对于编译器中使用的一些常用 的分析技术，都可以归纳为抽象解释。比如控制流分析、别名分析、类型分析、 活性分析等等 d t s j a v a 的区阗运算模块是基于抽象解释理论建模，对整型、浮点型、引用 型、布尔型、数组型变量进行建模。使用抽象解释进行静态分析的基本流程是： 1 定义一个抽象域，抽象域的值是目标属性的所有取值，并在这个域上定义 蔚蓄关系，通过添加顶元素和底元素，在域上形成一个格。 2 为程序设计语言的每个语句规定一个抽象语义。该语义是对1 中的抽象域 1 5 s t a r t 为开始状态， n o t n u l l 表示当前变量肯定不为n u ll ， n u l l o r n o t n u l l 表示当前句柄可能为n u ll ( 与n u l l 状态的状态转移重合) e r r o r 为出错状态， e n d 为终止状态。 图3 0 空指针引用故障状态转换图 图3 3 中的各条件转换含义如下表3 - 1 ： 1 6 北京邮电大学硕一i ：学位论文第三章面向缺陷的静态分析丁具 表3 - 1 空指针引用故障转换条件 序号状态转换引起状态转换的条件 s t a r t - - ) n o t n u u处于变量作用域范围内，且变量的 o 当前取值区间初始化为n o t l 讯y l l s t a r t - - ) n u u o r _ n o t n u l l 处于变量作用域范围内，且变量的 l 当前取值区闻初始化为n u l l 或 未知值 n o t n u n u l l o r n o t n u l l变量的当前取值赋值为n u l l 或 2 未知值 n o t n u l l 专e n d超出变量作用域范围 3 n u l l o r n o t n u l l -