基于指针映射集的动态内存故障测试方法研究样本.doc
《基于指针映射集的动态内存故障测试方法研究样本.doc》由会员分享,可在线阅读,更多相关《基于指针映射集的动态内存故障测试方法研究样本.doc(16页珍藏版)》请在咨信网上搜索。
1、资料内容仅供您学习参考,如有不当或者侵权,请联系改正或者删除。基于指针映射集的动态内存故障测试方法研究张威1),2), 宫云战2), 卢庆龄1), 万琳1)1) (装甲兵工程学院信息工程系 北京 100072)2) (北京邮电大学网络与交换技术国家重点实验室 北京 100876)摘 要 动态内存故障在使用指针的程序中是普遍存在的,采用动态测试方法进行测试难以准确定位故障源.而现有的静态分析方法主要存在漏报和误报过多的情况.针对这些问题,提出了指针映射代数系统的概念,全面地反映了指针与内存之间的映射关系.并给出了面向不同故障的指针映射集的构造规则,以此为基础建立了动态内存故障模型.经过指针映射集
2、和故障模型,能够自动检测内存释放异常、 内存泄露和空指针引用等动态内存故障,提高了测试效率.在分析过程中,还综合应用了控制流图和路径条件,提高了测试结果的精度.实验结果表明,该方法能够有效检测动态内存故障,而且由于规则定义较为全面,漏报和误报率也较低.关键词 软件测试;静态分析;指针映射集;内存泄漏;空指针引用中图分类号 TP302.8Research on Dynamic Memory Faults Testing Method based on Pointer Mapping SetsZHANG Wei1),2), GONG Yun-Zhan2), LU Qing-Ling1), WAN
3、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 p
4、ointers. 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
5、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
6、 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.
7、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的
8、统计,在软件开发总成本中,用在测试上的开销要占30到501.对于某些关系人的生命安全的关键软件,其测试费用甚至高达所有其它软件工程阶段费用总和的三到五倍.因此,提高软件测试的有效性和测试效率,降低软件开发成本已成为软件工程师迫切需要解决的任务之一.软件测试方法能够分为两大类,即动态方法和静态方法1.动态方法的主要缺点是只能依靠特定的测试用例来检测故障,因而不能检测所有故障,只能检测测试用例覆盖到的故障.另外,动态测试工具的执行开销也相当高,有时是不可接受的.静态方法不运行被测程序,而是分析程序源代码,并从中找出程序故障.但这并不意味着不利用计算机作为分析工具,它和人工测试有着本质的区别.静态分
9、析算法不需要任何运行时的开销,但需要做大量的分析工作.许多重要的编程语言都经过指针操作来支持动态内存管理,以提高语言的表示能力,但拥有指针的编程语言也会引起大量的动态内存故障.经过对30余万行C+语言源代码中的动态内存故障进行分析能够看出,每千行源代码(KLOC)故障数为0.921,其中内存释放异常0.015,内存泄漏0.355,空指针引用0.551,这说明动态内存故障在程序中是普遍存在的,研究针对这些故障的测试方法具有非常重要的意义.检测动态内存故障是非常困难的,也难以准确识别出程序中的故障源2.静态检测动态内存故障需要进行指针分析,一些研究人员已经对基于堆操作的指针分析进行了研究3,4,5
10、,其基本思路就是开发特定的算法来检测特定的内存问题(如内存释放异常、 内存泄漏和空指针引用等),这些算法不需要执行程序,也不需要借助程序注释和程序文档.这些方法的不足之处主要在于控制流模型不够精确,导致漏报和误报过多的情况发生.P. Fradet等人6提出了一种类Hoare逻辑来检测C程序中无效指针引用故障.这种分析方法基于别名和连接关系分析,能够处理循环数据结构,但循环不变量需要由用户提供,这种工作量有时是无法忍受的.R. Ghiya等人7提出的方法综合考虑了指针分析、 指向分析和连接关系分析.指向堆栈的指针采用基于存储的指向分析模型,堆指针采用堆分析、 连接关系分析和形状分析.这些方法的主
11、要缺点是没有考虑控制流信息. Bernhard Scholz和J.Zhu等人8,9提出了一种采用符号运算的方法来进行指针分析.符号运算是一种很有效的数据流和控制流分析工具,它能判断出一个给定程序在运行时的特性而无须执行该程序.但这种方法涉及的代数系统过于抽象,而且不易区分内存分配、 释放和指针变量赋值等操作.上述研究工作所要解决的问题和本文所要解决的问题有某些相似性,但本文提出的指针映射代数系统将内存分配、 释放和指针变量赋值等操作进行了细化,更全面地反映了指针与内存之间的映射关系.另外,提出了面向故障的指针映射集的概念,给出了面向不同故障的指针映射集的构造规则,以此为基础建立了动态内存故障模
12、型.经过指针映射集和故障模型,能够检测内存释放异常、 内存泄露和空指针引用等动态内存故障,提高了测试效率.在分析过程中,还综合应用了控制流图和路径条件,提高了测试结果的精度.本文第2节介绍了基本概念和指针状态及其变化.第3节介绍了指针映射集,包括指针映射代数系统和面向故障的指针映射集.第4节建立了故障模型.第5节给出了测试算法.第6节经过实例分析了测试过程,并给出了测试结果.第7节总结全文.2 指针状态分析2.1 基本概念动态内存故障有很多种类,本文论述与动态分配内存相关的几类故障的静态分析方法,包括内存释放异常(Bad Deallocation,记作FBD)、 内存泄露(Memory Lea
13、k,记作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):
14、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故障.记作A
15、ccess(p)Point(p, )FNPD. 2.2 指针的状态及其变化指针在其存在的过程中,由于各条与指针相关的语句的作用,使得它们的状态不断发生变化.一般一个指针能够划分为三种基本状态:空状态(记为Suncert):指针未指向任何有效的地址单元.指针声明和释放之后都变为Suncert状态;堆栈状态(记为Sstack):指针指向静态变量;堆状态(记为Sheap):指针指向堆地址.这三种基本状态反映了指针在生存期内的动态特性,但还不能揭示所有的动态内存故障.为此引入了反映指针产生和消亡的两种状态:声明状态(记为Sdecl):标识指针的产生;失效状态(记为Sinvalid):指针生存期结束.指
16、针状态及其变化如图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状态.如果执行F
17、ree(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变化
18、指针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)Inv
19、alid(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表示
20、静态变量的集合,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、 real
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 指针 映射 动态 内存 故障测试 方法 研究 样本
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。