【作者】 王雅文；

【导师】 陈俊亮；

【作者基本信息】 北京邮电大学 ， 通信与信息系统， 2009， 博士

【摘要】 随着信息技术的发展,软件的规模不断扩大,如何保证和提高软件质量成为软件界最为关心的问题之一。由于软件危机的频频出现,使得软件测试的地位得到了前所未有的提高。基于缺陷模式的软件测试是近些年发展起来的一种程序源代码静态分析技术,主要用于自动或者半自动的软件缺陷检测及预防,此类缺陷检测工具由于效率高和使用简单等特点在高可信软件测试中得到了广泛应用。所谓的缺陷模式,是指程序中经常发生的错误或缺陷所呈现出的特定规律。缺陷模式通常由具有领域程序设计经验的人或者测试人员总结出来。基于缺陷模式的软件测试作为传统软件测试的一种有力补充技术,其主要的优势在于：1)针对性强,不会有像白盒测试和黑盒测试那样的不确定性；2)可以检测出一些“小概率”的缺陷,例如存储器泄漏缺陷、空指针引用缺陷等。本文在国家“863”计划“软件的故障模型与面向故障的软件测试系统”及“863”重点项目“支持软件可信性分析和评估的生产线”的支持下,以缺陷模式检测中所涉及到的若干静态分析技术为研究核心,着重讨论了缺陷模式的分类及缺陷检测模型、程序变量值范围分析方法以及基于数据流的路径敏感检测方法。论文的主要工作包括以下内容：(1)本文以缺陷产生后果的严重性高低为评判标准,从程序的源代码形式着眼,将软件的缺陷模式分为四大类：故障模式、安全漏洞模式、疑问代码模式及规则模式。提出了一种缺陷模式检测的统一模型,其中提高精度和自动测试是其中的核心部分。该测试模型中,缺陷模式数据库与缺陷模式检测相分离,缺陷模式统一描述,具有可定制和可配置的优点；各缺陷模式状态机独立存在,可以并行高效分析多种缺陷模式。(2)本文基于抽象解释理论框架,扩展了经典的区间抽象,提出了一种扩展区间的方法来表示变量的值范围信息。针对不同的变量类型,首次提出了数值型变量的区间集表示和基本运算方法,定义了布尔型区间代数和引用型区间代数；定义了条件表达式中区间消减运算和逻辑运算；首次提出了变量取值的可能集和必然集及其在不同表达式中的计算方法。在此基础之上,提出了一个统一的过程内和过程间值范围分析算法,使用函数摘要来计算过程调用对程序上下文状态的影响。该算法可以直接检测出程序中的大部分矛盾语句节点及不可达路径；基于此的缺陷检测工具在实际测试中能较好地减少误报,提高检测效率。(3)本文提出了一种基于数据流的路径敏感检测方法来检测软件中的缺陷模式,该方法以扩展区间表示的值范围作为属性状态条件,通过在控制流汇合节点上对相同属性状态的属性状态条件进行合并来降低计算复杂度,其时间复杂度为多项式级。通过对大型Java、C/C++开源项目的测试结果分析,表明该方法的误报率比较低。基于上述关键技术的实现,本文最后介绍了实用化的软件缺陷检测工具DTS,说明了系统接口设计和系统主要功能,通过与常见缺陷检测工具的实验对比,DTS有较好的测试结果。更多还原

【Abstract】 With the development of information technology, the scale of software extends continuously, and how to guarantee and raise software quality becomes the main point in the software field. The frequent software crises enhance the position of software testing unprecedentedly.Software testing based on defect pattern is a new kind of source code static analysis technology, and it is mainly used in automatic and semi-automatic defect testing and precaution. For their high performance and easy use, such tools are widely applied in highly dependable software fields. The defect pattern is defined as often occurrences of program errors or defects, and defect patterns are usually summarized by experienced program designers and testers. As the beneficial supplement of traditional software testing, the main advantages of this technology are:(1) unlike the uncertainty of white box and black box testing, it is very pertinent to program defects; (2) it can detect defects that happen in lower probability such as memory leak and null pointer dereference.Supported by the National High-tech Research and Development Program ("863" Program) "Software fault models and the fault oriented software testing system" and "The product line supporting software dependability analysis and evaluation", this paper focuses on several static analysis technologies involved in defect pattern checking. It mainly discusses the classification of defect patterns and the general detecting model, variable range analysis methods and path sensitive analysis method based on data flow analysis. The main contributions are as follows:(1) Based on the graveness which defects may result in, software defects are divided into four classes:fault patterns, security vulnerability patterns, suspicious code patterns and program rule patterns. A general defect pattern checking model is proposed, in which accuracy enhancement and automatic testing are the kernel parts. In this model, defect pattern database and defect detecting are separate, and defect patterns are described unifiedly, so they can be customized and configured flexibly. Defect pattern state machines are independent, so the model can check many defect patterns concurrently.(2) Based on abstract interpretation theory, this paper extends classical interval abstraction, and extended intervals are used to describe variable range. The concept of numeric interval-set is proposed for the first time, and fundamental operations on interval-sets are defined. Boolean interval algebra and Reference interval algebra are also proposed. For range analysis in conditional expressions, split operation and logic operation are defined. Furthermore, to improve computing efficiency, the possible-value-set and necessary-value-set are put forward to compute variable range in conditional expressions.Then, a general algorithm for intra-procedural and inter-procedural range analysis is given. The algorithm can detect a great number of paradoxical statement nodes and infeasible paths in program, and defect detecting tool based on it can improve testing efficiency.(3) A new path sensitive analysis method is given, in which the property state condition is described by extended interval. It emerges property state conditions of the same property state at join points in CFG to depress computing complexity, and it runs in polynomial time and space. Experiments show that this method has lower false positive rate.Based on the above contributions, a practical software defect detecting tool-DTS (Defect Testing System) is introduced, and its interface design and system functions are given. Compared with several popular defect testing tools, DTS has satisfied testing results.更多还原