基于指针映射集的动态内存故障测试方法研究样本.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。基于指针映射集的动态内存故障测试方法研究张威1),2), 宫云战2), 卢庆龄1), 万琳1)1) (装甲兵工程学院信息工程系 北京 100072)2) (北京邮电大学网络与交换技术国家重点实验室 北京 100876)摘 要 动态内存故障在使用指针的程序中是普遍存在的,采用动态测试方法进行测试难以准确定位故障源.而现有的静态分析方法主要存在漏报和误报过多的情况.针对这些问题,提出了指针映射代数系统的概念,全面地反映了指针与内存之间的映射关系.并给出了面向不同故障的指针映射集的构造规则,以此为基础建立了动态内存故障模型.经过指针映射集和故障模型,能够自动检测内存释放异常、 内存泄露和空指针引用等动态内存故障,提高了测试效率.在分析过程中,还综合应用了控制流图和路径条件,提高了测试结果的精度.实验结果表明,该方法能够有效检测动态内存故障,而且由于规则定义较为全面,漏报和误报率也较低.关键词 软件测试;静态分析;指针映射集;内存泄漏;空指针引用中图分类号 TP302.8Research on Dynamic Memory Faults Testing Method based on Pointer Mapping SetsZHANG Wei1),2), GONG Yun-Zhan2), LU Qing-Ling1), WAN Lin1)1)(Department of Information Engineering, Academy of Armored Force Engineering, Beijing 100072)2) (State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876)Abstract: Dynamic memory faults are ubiquitous in the program with pointers. It is difficult to locate faults sources adopting dynamic testing method. Static analysis methods nowadays often miss some faults and produce too many false alarms. Considering of these problems, this paper puts forward the notion of pointer mapping algebra system that reflects the mapping relationship of pointer and memory completely, and gives the construction rules of pointer mapping sets for different faults class, and then establishes dynamic memory faults model. Through pointer mapping sets and fault model, it can detect bad deallocation, memory leak and null pointer dereference faults automatically and increase the testing efficiency. In the process of analyzing, it adopts synthetically control flow chart and path condition in order to increase the precision of testing results. Results of experimentation show that this method can detect dynamic memory faults effectively. Since rule definition is general, the probability of missing faults and producing false alarms is lower.Keywords: software testing; static analysis; pointer mapping sets; memory leak; null pointer dereference1 引言随着信息技术的发展,软件的规模不断扩大,如何保证和提高软件质量成为软件界最为关心的问题之一.软件测试作为保证软件质量的关键技术之一,能够有效地发现软件中的故障.根据Boehm的统计,在软件开发总成本中,用在测试上的开销要占30到501.对于某些关系人的生命安全的关键软件,其测试费用甚至高达所有其它软件工程阶段费用总和的三到五倍.因此,提高软件测试的有效性和测试效率,降低软件开发成本已成为软件工程师迫切需要解决的任务之一.软件测试方法能够分为两大类,即动态方法和静态方法1.动态方法的主要缺点是只能依靠特定的测试用例来检测故障,因而不能检测所有故障,只能检测测试用例覆盖到的故障.另外,动态测试工具的执行开销也相当高,有时是不可接受的.静态方法不运行被测程序,而是分析程序源代码,并从中找出程序故障.但这并不意味着不利用计算机作为分析工具,它和人工测试有着本质的区别.静态分析算法不需要任何运行时的开销,但需要做大量的分析工作.许多重要的编程语言都经过指针操作来支持动态内存管理,以提高语言的表示能力,但拥有指针的编程语言也会引起大量的动态内存故障.经过对30余万行C+语言源代码中的动态内存故障进行分析能够看出,每千行源代码(KLOC)故障数为0.921,其中内存释放异常0.015,内存泄漏0.355,空指针引用0.551,这说明动态内存故障在程序中是普遍存在的,研究针对这些故障的测试方法具有非常重要的意义.检测动态内存故障是非常困难的,也难以准确识别出程序中的故障源2.静态检测动态内存故障需要进行指针分析,一些研究人员已经对基于堆操作的指针分析进行了研究3,4,5,其基本思路就是开发特定的算法来检测特定的内存问题(如内存释放异常、 内存泄漏和空指针引用等),这些算法不需要执行程序,也不需要借助程序注释和程序文档.这些方法的不足之处主要在于控制流模型不够精确,导致漏报和误报过多的情况发生.P. Fradet等人6提出了一种类Hoare逻辑来检测C程序中无效指针引用故障.这种分析方法基于别名和连接关系分析,能够处理循环数据结构,但循环不变量需要由用户提供,这种工作量有时是无法忍受的.R. Ghiya等人7提出的方法综合考虑了指针分析、 指向分析和连接关系分析.指向堆栈的指针采用基于存储的指向分析模型,堆指针采用堆分析、 连接关系分析和形状分析.这些方法的主要缺点是没有考虑控制流信息. Bernhard Scholz和J.Zhu等人8,9提出了一种采用符号运算的方法来进行指针分析.符号运算是一种很有效的数据流和控制流分析工具,它能判断出一个给定程序在运行时的特性而无须执行该程序.但这种方法涉及的代数系统过于抽象,而且不易区分内存分配、 释放和指针变量赋值等操作.上述研究工作所要解决的问题和本文所要解决的问题有某些相似性,但本文提出的指针映射代数系统将内存分配、 释放和指针变量赋值等操作进行了细化,更全面地反映了指针与内存之间的映射关系.另外,提出了面向故障的指针映射集的概念,给出了面向不同故障的指针映射集的构造规则,以此为基础建立了动态内存故障模型.经过指针映射集和故障模型,能够检测内存释放异常、 内存泄露和空指针引用等动态内存故障,提高了测试效率.在分析过程中,还综合应用了控制流图和路径条件,提高了测试结果的精度.本文第2节介绍了基本概念和指针状态及其变化.第3节介绍了指针映射集,包括指针映射代数系统和面向故障的指针映射集.第4节建立了故障模型.第5节给出了测试算法.第6节经过实例分析了测试过程,并给出了测试结果.第7节总结全文.2 指针状态分析2.1 基本概念动态内存故障有很多种类,本文论述与动态分配内存相关的几类故障的静态分析方法,包括内存释放异常(Bad Deallocation,记作FBD)、 内存泄露(Memory Leak,记作FML)和空指针引用(Null Pointer Dereference,记作FNPD),这几类故障都与指针变量相关(以下将指针变量简称为指针).下面给出这几类故障的形式化定义.定义1 与动态内存故障相关的谓词定义如下: Malloc(p):为指针p动态分配堆地址单元; Static(p):使指针p指向静态变量; Null(p):使指针p指向特殊地址单元 Free(p):释放指针p所指向的存储单元; Status(p):取指针p的当前状态; Access(p):访问指针p; Invalid(p): 指针p的生存期结束;Point(p,h):指针p指向堆地址空间h;Belong(x,y):x属于y.定义2 令S表示静态变量的集合,V表示指针的集合,pV, xS,在程序中的Si点,如果Free(p),且p当前指向x或,则称在Si点存在FBD故障.记作Free(p)(Point(p,x)Point(p, )FBD定义3 令H表示所有堆地址的集合,Ht表示已经分配的堆地址的集合,HtH,pV, 执行程序中Si点的语句之后,如果hHt,且p(Point(p,h),则称在Si点存在FML故障.记作h(Belong(h,Ht)p(Belong(p,V) Point(p, h)FML.定义4 令pV,在程序中的Si点,如果Access(p),且p当前指向,则称在Si点存在FNPD故障.记作Access(p)Point(p, )FNPD. 2.2 指针的状态及其变化指针在其存在的过程中,由于各条与指针相关的语句的作用,使得它们的状态不断发生变化.一般一个指针能够划分为三种基本状态:空状态(记为Suncert):指针未指向任何有效的地址单元.指针声明和释放之后都变为Suncert状态;堆栈状态(记为Sstack):指针指向静态变量;堆状态(记为Sheap):指针指向堆地址.这三种基本状态反映了指针在生存期内的动态特性,但还不能揭示所有的动态内存故障.为此引入了反映指针产生和消亡的两种状态:声明状态(记为Sdecl):标识指针的产生;失效状态(记为Sinvalid):指针生存期结束.指针状态及其变化如图1所示.图中实线箭头表示正常的状态变化过程,虚线箭头表示可能产生动态内存故障的状态变化过程.下面着重讨论可能产生故障的变化过程.变化 指针p由Sdecl状态变为Suncert状态.如果执行Free(p)操作,就会导致内存释放异常故障,形式化描述如下:p, (Status(p)= Sdecl)Free(p)FBD变化 指针p由Suncert状态变为Suncert状态.如果执行Free(p)操作,就会导致内存释放异常故障,形式化描述如下:p, (Status(p)=Suncert)Free(p)Free(p) FBD变化 指针p由Sstack状态变为Suncert状态.如果执行Free(p)操作,就会导致内存释放异常故障,形式化描述如下:p, (Status(p)=Sstack)Free(p)FBD变化 指针p由Sheap状态变为Sinvalid状态.为指针p分配了堆地址空间,但没有执行释放操作指针p即失效,导致内存泄露故障,形式化描述如下:p, (Status(p)= Sheap)Invalid (p)FML变化 指针p由Sheap状态变为Suncert状态.如果执行Null(p)操作,而且此时没有其它指针q指向p所指的堆地址空间h, 就会导致内存泄漏故障,形式化描述如下:p,(Status(p)=Sheap)Null(p)(q (Point(q, h)FML变化 指针p由Sheap状态变为Sheap状态.即再次为同一个指针p分配堆地址空间, 如果此时没有其它指针q指向p原来所指的堆地址空间h, 就会导致内存泄露故障,形式化描述如下:p, (Status(p)=Sheap)Malloc(p)(q (Point(q, h)FML图1 指针P的状态及其变化Free(p)Free(p)Static(p)Free(p)Malloc(p)Static(p)Malloc(p)Malloc(p)Static(p)SuncertSstackSheapSdeclSinvalidStatic(p)Null(p)Malloc(p)Invalid(p)Invalid(p)Invalid(p)Invalid(p)变化 指针p由Sheap状态变为Sstack状态.即指针p已经指向了堆地址空间h,又令其指向静态变量, 如果此时没有其它指针q指向h, 就会导致内存泄露故障,形式化描述如下:p,(Status(p)=Sheap)Static(p)(q (Point(q, h)FML上述变化可能产生内存释放异常和内存泄漏故障,除此之外,如果访问处于Sdecl和Suncert状态的指针,会产生空指针引用故障,形式化描述如下:p,(Status(p)=Sdecl)(Status(p)=Suncert)Access (p)FNPD3 指针映射集3.1 指针映射代数系统定义5 令S表示静态变量的集合,V表示指针的集合,H表示所有堆地址的集合,则广义指针映射集定义为:(V)(HS)=|x(V)y(HS),记作.定义6 广义指针映射集及定义在该集合上的运算、 和称为指针映射代数系统,记作.其中运算定义如下:动态分配运算,=,其中xV,y(HS), zH,且x;:赋值运算,=,其中x1V, x2V,y1(HS),y2(HS),且x1;:释放运算,=,其中xV,yH,且x.从定义5、 定义6能够看出: 指针只能指向静态变量、 堆地址单元或特殊地址单元;运算指调用内存分配函数的操作,C+程序设计语言提供的内存分配函数有new、 strdup、 malloc、 calloc、 realloc等.该运算实际上是将分配操作和赋值操作组合在一起,因为单纯的分配操作没有任何意义.例如,p=malloc(sizeof(int)可描述为,z即为动态分配的堆地址单元,运算结果为;运算即指针的赋值操作,改变指针所指向的内容;运算是单目运算符,运算的结果是回收堆地址单元,并使指针指向特殊地址单元.性质1 指针映射代数系统是封闭的.性质2 指针映射代数系统是不可交换的.3.2 面向故障的指针映射集定义7 动态反映程序中指针映射关系的集合称为面向故障的指针映射集,记作T,T.面向故障的指针映射集T是广义指针映射集的子集,是分析程序语句的过程中动态生成的,它反映了程序中的指针与内存地址之间的映射关系.本文经过面向故障的指针映射集T来分析动态内存故障.定义8 对面向故障的指针映射集T进行操作的函数定义如下:Add():添加元素到集合T.其中pV, h(i)H,由于检测动态内存故障只需知道分配了一个存储单元即可,而不必考虑该单元的具体地址,因此i的作用只在于区分不同的堆地址单元,可设置为一个递增变量.Change(,):将变为.其中p1V,h(i)H,h(j)H.Delete():从集合T中删除元素.其中pV, h(i)H.Get(p):从集合T中取p所指向的堆地址.其中pV.如不存在则返回.JudgeNull(p):判断p是否指向,如果指向,返回True,否则返回False.为了更全面地找出动态内存故障,需要分别建立面向故障的指针映射集,内存释放异常和内存泄漏故障共用一个指针映射集TBM,空指针引用故障单独使用一个指针映射集TNPD,两者的主要区别是对动态分配函数的处理,前者在没有判断的情况下,假定分配成功;而后者在没有判断的情况下,假定分配不成功.下一节将详细介绍TBM和TNPD的构造规则并给出故障模型.4 故障模型4.1 内存释放异常和内存泄漏故障模型指针映射集TBM按以下规则构造:规则M1 初始值为;规则M2 令pV,h(i)H,h(j)H,如果Malloc(p), 使p指向h(i),且(Belong(,TBM),则Add();规则M3 令pV,h(i)H,h(j)H,如果Malloc(p),使p指向h(i),且(Belong(,TBM),则Change(, ),Add();规则M4 令pV,h(i)H,如果Free(p), 使p不再指向h(i),且(Belong(,TBM),则Delete();规则M5 令pV,xS,h(i)H,如果p=&x, 使p指向x ,则 如果 (Belong(,TBM),且 (Belong(,TBM),则Change(,);如果 (Belong(,TBM),且 (Belong(,TBM),则Delete();规则M6 令pV,qV,h(i)H,h(j)H,如果p=q, 使p从指向h(i),变为指向h(j),则 h(j)=Get(q); 如果 (Belong(,TBM),且(Belong(,TBM),则Change(,);如果 (Belong(,TBM),且 (Belong(,TBM),则Delete();如果 (Belong(,TBM),且h(j),则Add().规则M7 如果JudgeNull(p)为True,且 (Belong(,TBM),则Delete();规则M8 令pV,h(i)H,如果Invalid(p), 使p不再指向h(i),且(Belong(,TBM),则Change(,);根据以上规则,可得内存释放异常故障模型:在程序中的Si点,当前指针映射集为TBM(Si),pV,h(i)H,如果Free(p),且 (Belong(,TBM(Si),则在Si点存在FBD.记作Free(p)(Belong(,TBM(Si) FBD (1)根据TBM构造规则,(Belong(, TBM(Si),说明指针p没有指向堆地址空间,即 Point(p,x)或Point(p,),其中xS,根据定义2可知存在FBD故障.内存泄漏故障模型:在程序中Si点,当前指针映射集为TBM(Si),如果(Belong(,TBM(Si), h(i)H,则在Si点存在FML.记作(Belong(,TBM(Si)FML (2)根据TBM构造规则,(Belong(,TBM(Si),则一定有动态分配操作,且没有释放操作,左变元为,说明没有指针指向堆地址单元h(i),根据定义3可知存在FML故障.4.2 空指针引用故障模型指针映射集TNPD按以下规则构造:规则N1 初始值为;规则N2 令pV,xS,如果JudgeNull(p)为False,且(Belong(,TNPD),则Add();规则N3 令pV,xS,如果JudgeNull(p)为True,且(Belong(,TNPD),则Delete();规则N4 令pV,xS,如果Free(p),且(Belong(,TNPD),则Delete();规则N5 令pV,xS,如果p=&x,且(Belong(,TNPD),则Add();规则N6 令pV,qV,xS,如果p=q,(Belong(,TNPD),且(Belong (,TNPD),则Add();规则N7 令pV,xS,如果Invalid(p),且(Belong(,TNPD),则Delete();根据以上规则,可得空指针引用故障模型:在程序中Si点,当前指针映射集为TNPD(Si),如果Access(p),且(Belong(,TNPD(Si),则在Si点存在FNPD故障.记作Access(p)(Belong(,TNPD(Si) FNPD (3)根据TNPD构造规则,TNPD只在确保非空的情况下才添加元素,因此(Belong(,TNPD(Si),说明Point(p,),根据定义4可知存在FNPD故障.本节讨论了面向故障的指针映射集的构造规则,据此建立了内存释放异常、 内存泄漏和空指针引用故障模型,模型的建立是进一步检测工作的基础.5 测试算法测试算法的操作步骤如下:预编译.由于源程序中存在宏定义、 文件包含和条件编译等预处理命令,因此在进行词法分析前必须进行预处理,将宏进行展开,这样有利于变量的查找;词法分析.将预编译阶段产生的中间代码进行分解,形成各种符号表,为语法分析作准备.符号表的结构主要有:标识符表、 类型表、 关键字表、 常数表、 运算符表和分界符表;L1图2 程序控制流图L3L2S0S1S2S3S5S6S10S7S11S13S8S12语法分析.这一步主要是将输入字符串识别为单词符号流,并按照标准的C+语法规则,对源程序作进一步分析,区分出变量定义、 赋值语句、 函数等等.语法分析的结果是生成语法树,并提供对外的接口.另外,经过语法树能够生成程序的控制流图和变量的定义使用链,为下一步的故障查找作准备;取控制流图中的一条路径;按顺序取路径中的一个结点,如果是与指针相关的操作,则按M规则和N规则修改面向故障的指针映射集TBM和TNPD;按公式(1)、 (2)和(3)分别检测是否存在FBD、 FML和FNPD故障;返回直到所有结点检测完毕;返回直到所有路径检测完毕.6 实例与实验结果分析6.1 实例分析下面经过一个实际程序来分析一下测试过程,程序代码如下:s1 p=malloc(sizeof(int);s2 q= malloc(sizeof(int);s3 if (q= =NULL)s4 return; s5 if (x= =1)s6 p=&x;s7 free(p);s8 free(q);s9 return; s10 y=*p;s11 free(p);s12 free(q);程序控制流图如图2所示.该程序有3条路径L1、 和L3,在各条路径中,指针映射集TBM和TNPD的变化情况如表1所示.表1 TBM和TNPD 变化情况及检测结果路径语句TBM规则TNPD规则结果L1s1M1s2, M1s3M7N1s4M8N7TBM中出现左变元为的元素,因此产生FML故障L2s1M1s2, M1s3, M7N2s5, s6, M5,N5TBM中出现左变元为的元素,因此产生FML故障s7, M4N4释放p,且TBM中不存在左变元为p的元素,因此产生FBD故障s8M4N4s9M8N7L3s1M1s2, M1s3, M7N2s5, s10, 访问p,且TNPD中不存在左变元为p的元素,因此产生FNPD故障s11M4N4s12M4N4s13M8N7从指针映射集TBM和TNPD的变化能够看出,在路径L1的结点s4处,TBM中存在一个元素的左变元为,因此产生一个FML故障.在路径L2的结点s6处,TBM中存在一个元素的左变元为,因此产生一个FML故障;结点s7处释放指针p,但TBM中不存在左变元为p的元素,因此产生一个FBD故障.在路径L3的结点s10处,访问指针p,但TNPD中不存在左变元为p的元素,因此产生FNPD故障.6.2 实验结果及分析采用本文所述的方法,对国内外不同领域的7个项目进行了实验测试,测试结果如表2所示,其中前4个项目为国外项目,后3个项目为国内项目,由于有些项目头文件不全,因此统计中剔除了头文件不全的源文件.这里IP(Inspection points)表示自动发现的故障点,故障表示经人工确认后的故障点,用故障率和准确率来表示测试的效果,其定义如下: 其中故障率即千行源代码( KLOC) 的故障数,准确率即故障在IP中所占比重,它也能够反映出误报的情况,误报率=(1-准确率).表2 实验测试结果项目编号源代码行数FBDFMLFNPDIP总数故障总数15045502137515255863114411185634279901026115364852703765642013551173304163620611859046221076870616224929合计3266855116180835301故障率0.0150.3550.5510.921测试代码的总行数有32万余行,从中找出301个动态内存故障,平均每千行源代码0.921个故障.这些数据具有一定的统计意义,说明这些故障在项目中是普遍存在的,开发针对这些故障的专用测试工具具有很高的实用价值.对于4个国外项目,我们与Reasoning公司的测试结果进行了对比,如表3所示.表3 测试结果比较项目编号本文所述方法Reasoning工具IP总数故障总数准确率IP总数故障总数准确率1751520%10798.4%21185647.5%1105348.2%31153631.3%1642917.9%442013532.1%3596618.4%合计72824233.2%74015721.2%表3中Reasoning工具的测试数据引自该公司测试结果数据库.从中能够看出,采用本文所述的方法,从20余万行源代码中找出728个IP,经人工确认,其中有242个故障,准确率为33.2%,而Reasoning工具找出740个IP,其中有157个故障,准确率为21.2%.这说明本文所述方法在测试动态内存故障方面还是比较有效的.7 结束语本文提出了一种新的动态内存故障测试方法,该方法基于指针映射关系分析.经过构造面向故障的指针映射集,建立了动态内存故障模型,并按照故障模型,给出了测试算法,该算法能够自动检测内存释放异常、 内存泄露和空指针引用等动态内存故障,提高了测试效率.在分析过程中,还综合应用了控制流图和路径条件,提高了测试结果的精度.但由于程序语法的复杂性, 采用静态分析方法难以覆盖所有的语法现象, 因而还存在误报和漏报的情况.下一步的研究目标是根据程序中的各种语法现象,扩展指针映射集的构造规则,以减少误报和漏报,使之具有更强的适应性.参 考 文 献1 Zheng Ren-Jie. Computer Software testing technology. Beijing: Tsinghua university press,1992. (郑人杰.计算机软件测试技术.北京:清华大学出版社,1992)2 R.Hastings and B. Joyce. Purify: Fast detection of memory leaks and access errors/Proceedings of the Winter USENIX Technical Conference, Monterey, California, USA, 1999:125-136.3 A. Gotsman, J. Berdine, and B. Cook. Interprocedural shape analysis with separated heap abstractions/Proceedings of the 13th International Static Analysis Symposium (SAS06), Seoul, Korea, :241-260.4 W.Landi and B. G. Ryder. Safe approximate algorithm for interprocedural pointer aliasing. ACM SIGPLAN Notices,1992, 27(7):235-248.5 R. P. Wilson and M. S. Lam. Efficient context-sensitive pointer analysis for C program/Proceedings of the ACM SIGPLAN95 Conference on Programming Language Design and Implementation(PLDI), La Jolla, California,USA, 1995:18-21.6 P. Fradet, R. Caugne, and D. L. Metayer. Static detection of pointer errors: An axiomatisation and a checking algorithm/Programming Languages and Systems-ESOP96, 6th European Symposium on Programming, Linkoping, Sweden, 1996:22-24.7 R. Ghiya and L. Hendren. Putting pointer analysis to work/ Proceedings of the 25th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. San Diego, CA, 1998:121-133.8 Bernhard Scholz, Johann Blieberger and Thomas Fahringer, Symbolic pointer analysis for detecting memory leaks/ Proceedings of the ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation. Boston, Massachusetts,USA, :104-1139 J. Zhu and S. Calman. Symbolic pointer analysis revisited/Proc