论文部分内容阅读
软件代码中的缺陷是导致软件故障和漏洞问题的主要原因。基于缺陷的软件测试技术可以分为动态检测技术和静态检测技术。静态检测技术不运行被测程序,通过应用各种静态分析技术来发现程序中的缺陷。从可计算性理论的角度来看,静态缺陷检测是一个不可判定问题。提高精度是静态缺陷检测的核心问题,提高精度包括两个方面:减少误报和减少漏报。大量的误报会使人对分析工具失去信心,而漏报会造成程序具有较高质量的假象。本文在国家“863”计划“软件的故障模型与面向故障的软件测试系统”、“软件的安全性缺陷模型及基于安全性缺陷的测试技术”及“863”重点项目“支持软件可信性分析和评估的生产线”的支持下,以提高静态缺陷检测精度为核心研究内容,着重从抽象域设计、路径敏感和上下文敏感角度讨论了提高缺陷检测精度的方法,论文的主要工作包括以下内容:(1)如何更好地近似表示和计算程序变量的取值信息是提高静态分析精度的关键。本文基于抽象解释理论提出一种考虑变量相关性的变量取值抽象表示和计算方法。首先,为了能精确表示两个分离区间的并,将经典的单区间抽象域扩展为区间集抽象域;其次,为了处理由赋值引入的变量关联关系,引入符号表达式抽象域,符号表达式抽象域是对变量关系的抽象。将符号表达式抽象与单区间抽象或区间集抽象结合可以进一步精化后者的抽象结果;最后,给出一个统一的程序中变量抽象取值计算算法,该算法并不依赖于具体的抽象域。(2)基于有限状态机的缺陷检测可以化为一个传统的数据流问题。数据流问题典型的解有三个:理想解(IDEAL)、全路径聚合解(Meet Over all Paths, MOP)和最大/小不动点解(Maximal/Minimal Fixed Point, MFP)。传统求MFP解的迭代算法是一种流敏感但路径不敏感的方法。本文在传统数据流迭代算法的基础上,提出一种多项式复杂度的路径敏感缺陷检测算法,该方法采用变量的抽象取值来表示缺陷状态条件,通过缺陷状态条件中的变量抽象取值为空来判断不可达路径,并在所有控制流汇合节点上合并相同缺陷状态的状态条件从而避免完整路径的组合爆炸问题,实际测试结果表明该方法能够减少误报。(3)对于基于有限状态机的缺陷检测来说,过程间分析有其特点:当遇到一个函数调用时,它关心的是该函数的执行是否会引起当前缺陷状态机实例的状态发生变化,不同缺陷检测关心的信息各不相同。针对这一特点,本文提出一种基于函数摘要的过程间缺陷检测方法:首先,定义了面向缺陷检测的函数摘要,其内容包括前置约束信息集合、后置副作用信息集合和状态特征信息集合,函数摘要可以看作是以函数为单位对程序实际语义的抽象。函数摘要的生成过程伴随过程内分析进行,其中前置约束信息生成是一个逆向可能数据流问题,后置副作用信息生成和状态特征信息生成是两个正向可能数据流问题。其次,为实现上下文敏感分析,引入了摘要条件的概念,摘要条件采用变量的抽象取值表示,代表在函数调用点处应用相应摘要信息时需满足的上下文条件。最后,给出一个基于函数摘要的过程间缺陷检测迭代算法,实验表明该方法能降低误报和漏报。综上所述,本文针对提高缺陷检测精度的几个关键性问题进行了探索,取得了一定的理论研究成果。上述关键技术已应用于软件缺陷检测工具DTS,初步应用结果表明上述关键技术也具有良好的工业应用价值。