（计算机科学与技术专业论文）基于程序语义的软件故障定位技术研究.pdf

s o f t w a r ef a u l tl o c a l i z a t i o nr e s e a r c hb a s e do np r o g r a ms e m a n t i c s b y h eg u o q i n b e ( h u n a nu n i v e r s i t y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g l n c o m p u t e rs c i e n c ea n dt e c h n o l o g y i nt h e g r a d u a t es c h o o l o f h u n a n u n i v e r s i t y s u p e r v i s o r p r o f e s s o rz h a n gd a f a n g m a y , 2 0 1 1 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声 明的法律后果由本人承担。 作者签名：俑因琴 日期： 2d j l 年占月3 1 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保 存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书。 2 不保密囱。 ( 请在以上相应方框内打“”) 作者签名： f 司国琴 导师签 日期：2 0 1 1 年岁月31 日 日期：年月目 3 - o , i j 多7 硕上学位论文 摘要 随着计算机技术的发展和软件应用领域的扩大，软件系统的规模和复杂性不断 攀升，由于软件故障直接导致系统失效的比率持续增加，其可靠性越来越难以保证。 当软件失效发生后，如何自动调试和定位引发失效的软件故障是一个非常有价值的 研究课题。 基于程序频谱的故障定位技术分析程序成功运行和失败运行的动态执行特征， 将这些特征统称为程序频谱，计算出每个程序实体可能出错的概率。这种轻量级的 故障定位技术仅仅需要程序动态运行信息，由于其计算复杂度低，无需建模代价而 得到广泛研究和应用。 本文在分析各种常见程序频谱的基础上，提出了一种新的程序频谱动态方 法调用图，它能够表达程序的语义信息程序执行时方法之间的调用关系。由于 传统收集程序频谱的插桩方式引入过多额外的执行开销，本文介绍一种新的收集程 序频谱的方式，那就是采用面向方面编程技术收集程序频谱。通过在被测程序中增 加一个新的模块方面监视程序执行。由于方面可以跟踪程序执行时方法调用栈 的转换，收集的程序频谱可以记录程序执行时方法之间的调用关系。 在所收集的程序频谱的基础上，提出一种基于程序语义的故障定位技术。定义 了一种新的程序模型程序动态行为图。在行为图中，边权值表示方法调用边的 调用频率，成功行为图和失败行为图的差异指出了程序中可疑的故障点。由于成功 测试用例的和失败测试用例数量差异很大，比较边调用频率这个绝对数值是不合理 的。本文认为如果一条边在成功行为图和失败行为图中的调用概率差越大，它出错 的概率就越大。通过计算每条边在成功行为图和失败行为图中的调用概率差，得到 边的故障可疑值，最后按照故障可疑值排列方法调用边，得到故障报告。 最后设计和实现了基于程序语义的故障定位原型系统，初步的实验结果表明， 相比传统的插桩技术，采用面向方面编程技术收集程序频谱能减少数十倍以上的执 行开销。通过大量实验验证，基于程序语义的故障定位技术能够提高错误定位的效 率，减轻程序员的调试负担。 关键词：故障定位；面向方面编程；程序频谱；程序动态行为图 i i 基于程序语义的软件故障定位技术研究 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g ya n dt h e e x p a n s i o no fs o f t w a r e a p p l i c a t i o n ，t h es c a l ea n dc o m p l e x i t yo fs o f t w a r es y s t e m sr i s e sa n dt h er a t eo fs y s t e m f a i l u r ec a u s e db ys o f t w a r ef a u l t sc o n t i n u e st oi n c r e a s e ，a n ds o f t w a r er e l i a b i l i t yc a n n o tb e a s s u r e dm u c hm o r e i ti sas i g n i f i c a n ts t u d yt om a k et h ed e b u g g i n ga u t o m a t e da n dl o c a t e t h ef a u l ti nc a s eo fs o f t w a r ef a i l u r e s p e c t r a b a s e df a u l tl o c a l i z a t i o nt e c h n o l o g ya n a l y z e sp r o g r a mr u n t i m ei n f o r m a t i o n ， w h i c hi sk n o w na sp r o g r a ms p e c t r a ，f r o mp a s s i n gr u n sa n df a i l i n gr u n s ，t oc o m p u t et h e l i k e l i h o o do fe a c hp r o g r a me n t i t yb e i n gf a u l t y t h i sl i g h t w e i g h tf a u l tl o c a l i z a t i o nt a k e sa s i t so n l yi n p u tdy n a m i ci n f o r m a t i o nc o l l e c t e da tr u n - t i m e ，d u et oi t sl o wc o m p u t a t i o n a l c o m p l e x i t ya n dn om o d e l i n gc o s t ，h a sb e e nw i d e l ys t u d i e da n da p p l i e d o nt h eb a s i so fa n a l y z i n gs e v e r a lc o m m o np r o g r a ms p e c t r a ，t h et h e s i sp r o p o s e sa n o v e lp r o g r a ms p e c t r u m - d y n a m i cm e t h o dc a l lg r a p h ，w h i c hc o n v e y sp r o g r a ms e m a n t i c s i n f o r m a t i o n c a l lr e l a t i o n s h i pb e t w e e n m e t h o d sw h i l ep r o g r a me x e c u t i n g t r a d i t i o n a lw a y t oc o l l e c tp r o g r a ms p e c t r ai si n s t r u m e n t a t i o n ，b u ti ti n t r o d u c e st o om u c ho v e r h e a d t h i s t h e s i si n t r o d u c e san e ww a y , t h a ti su s i n ga s p e c t o r i e n t e dp r o g r a m m i n gt oc o l l e c tp r o g r a m s p e c t r a i tc a l lm o n i t o rp r o g r a me x e c u t i o nb ya d d i n gan e wm o d u l e a s p e c tt ot h et e s t e d p r o g r a m a sa s p e c tc a nt r a c et h et r a n s l a t i o no f m e t h o dc a l ls t a c kw h i l ep r o g r a me x e c u t i n g ， t h ep r o g r a ms p e c t r ac o l l e c t e dc a nr e c o r dc a l lh ie r a r c h yb e t w e e nm e t h o d s w i t ht h ep r o g r a ms p e c t r ac o l l e c t e d ，t h et h e s i sp r o p o s e saf a u l tl o c a l i z a t i o na p p r o a c h b a s e do np r o g r a ms e m a n t i c s w ed e f i n ean e wp r o g r a mm o d e l p r o g r a md y n a m i cb e h a v i o r g r a p h i nt h eb e h a v i o rg r a p h ，e d g ew e i g h tr e p r e s e n t sc a l lf r e q u e n c y , a n dt h ed i f f e r e n c e si n s u c c e s s f u lb e h a v i o rg r a p ha n df a i l i n gb e h a v i o rg r a p hp i n p o i n ts u s p i c i o u sf a u l tp l a c e s b e c a u s eo ft h eb i gd i f f e r e n c ei nt h en u m b e ro fp a s s i n ga n df a i l i n gt e s tc a s e s ，i ti s n t r e a s o n a b l et or e p r e s e n tb e h a v i o rg r a p hd i f f e r e n c ea sc a l lf r e q u e n c yd i f f e r e n c e s ow e a s s u m et h a tt h eg r e a t e rt h ee d g ec a l lp r o b a b i l i t yd i f f e r e n c ei nt h et w ob e h a v i o rg r a p h si s ， t h eh i g h e ri t s s u s p i c i o u s n e s si s ，c o m p u t ee d g e ss u s p i c i o u s n e s s2 l st h ec a l lp r o b a b i l i t y d i f f e r e n c ei nt h es u c c e s s f u lb e h a v i o rg r a p ha n df a i l i n gb e h a v i o rg r a p h ，a n dr a n km e t h o d c a l le d g e sa c c o r d i n gt ot h e i rs u s p i c i o u s n e s s i nt h ee n d ，w ed e s i g na n di m p l e m e n tap r o t o t y p es y s t e m ，n a m e df a u l tl o c a l i z a t i o n b a s e do np r o g r a ms e m a n t i c s e x p e r i m e n t a lr e s u l t ss h o wt h a t ，c o m p a r e dw i t ht r a d i t i o n a l i n s t r u m e n t i n gw a yt oc o l l e c tp r o g r a ms p e c t r a ，a s p e c t o r i e n t e dp r o g r a m m i n gw a yc a n r e d u c em o r et h a nt e n so ft i m e so fo v e r h e a d e m p i r i c a ls t u d i e sp r o v et h a t t h ef a u l t i i i 硕：l 学位论文 l o c a l i z a t i o nt e c h n o l o g yb a s e do np r o g r a ms e m a n t i c sc a ni m p r o v et h ea c c u r a c yo fp o i n t i n g b u g s ，a n dr e l a xp r o g r a m m e r s f r o mt h eb u r d e no f d e b u g g i n g k e yw o r d s ：f a u l tl o c a l i z a t i o n ；a s p e c t o r i e n t e dp r o g r a m m i n g ；p r o g r a ms p e c t r u m ； p r o g r a md y n a m i cb e h a v i o rg r a p h i v 目 硕j j 学位论文 3 1 引言1 7 3 2 整体框架17 3 3 程序频谱18 3 3 1 程序频谱的定义i8 3 3 2 程序频谱的分类18 3 4 选择程序频谱2 0 3 5 收集程序频谱2 1 3 5 1 插桩技术2 1 3 5 2 面向方面编程和a s p e c t j 2 l 3 5 3a o p 方式收集程序频谱2 2 3 5 4 程序频谱表现形式2 2 3 5 5 自动收集程序频谱2 3 3 6 本章小结2 3 第4 章基于程序语义的故障定位技术一2 4 4 1 引言+ 2 4 4 2 故障定位技术的提出2 4 4 2 1 几点假设2 4 4 2 2 问题描述2 5 4 3 故障定位技术总体思路2 5 4 3 1 设计思想2 5 4 3 2 故障定位流程2 6 4 4 分析程序频谱2 7 4 4 1 创建程序动态行为图2 7 4 4 2 计算故障可疑值2 8 4 5 平价2 9 4 5 1 故障报告质量2 9 4 5 2 额外的执行开销3 0 4 6 实例验证31 4 6 1 实验程序3l 4 6 2 收集程序频谱31 4 6 3 构建行为图3 2 4 6 4 计算故障可疑值3 2 4 6 5 评价3 2 4 7 本章小结3 3 第5 章原型系统设计和实验3 4 5 1 系统概述3 4 v i 基于程序语义的软件故障定位技术研究 5 2 部分模块设计实现3 5 5 2 1 程序频谱收集模块3 5 5 2 2 程序频谱分析模块3 5 5 3 实验及结果分析3 5 5 3 1 实验程序3 5 5 3 2 实验结果及分析3 6 5 4 本章小结3 7 结论3 8 参考文献4 0 致谢4 4 附录a ( 攻读学位期间所发表的学术论文目录) 4 5 v i i 图2 4 程序执行状态转换图9 图2 5 程序p l u sm u l 和p d g l0 图2 6m b s d 错误定位流程图12 图2 7 缩减后的调用图示例15 图2 8f s m b f l 流程1 5 图3 1 动态的故障定位技术流程17 图3 2 程序m u l 和控制流图1 9 图3 3 程序频谱示例2 3 图4 1 程序动态行为图示例2 6 图4 2 本文故障定位流程图2 6 图4 3 创建程序动态行为图2 7 图4 4a s p e c t 代码31 图5 1p s b f l 系统总体框架图3 4 v i i i 表1 1 各种故障定位方法比较 表3 1 各种程序频谱 表3 2 程序频谱演示 表5 1 实验程序描述 表5 2 实验结果 硕十学位论文 第1 章绪论 1 1 研究背景和意义 1 1 1 研究背景 随着社会的不断进步和信息技术的飞速发展，计算机的应用已经渗透到现代社 会生产生活的各个方面，人们对计算机系统的需求和依赖不断增加。软件是信息技 术的重要组成部分，是计算机的灵魂。近年来，软件产业取得了突飞猛进的发展， 已被成功应用到国民经济的各个领域，特别是在军事、航空航天、工业控制、交通、 金融、医疗、通讯等关键行业领域，起着举足轻重的作用。 然而，随着人们对计算机软件依赖程度的与日俱增，软件系统的规模和复杂性 不断攀升，软件存在缺陷和出现失效的可能性也在不断增加，其可靠性越来越难以 保证。据有关资料统计，软件故障占整个计算机系统故障的6 5 【l j 。 由于软件故障导致系统失效，酿成重大经济损失和人员伤亡的案例不胜枚举。 1 9 6 2 年7 月2 2 号，美国首次金星探测计划“水手l 号由于太空船本体按非预期的 方位转向导致失控，不得不自行销毁，造成了上千万美元的损失1 2 】。1 9 8 5 年6 月至 1 9 8 7 年1 月，t h e r a c 2 5 放射治疗仪在加拿大造成4 位病人死亡，2 人重伤的特大安 全事故，深层的原因是系统和软件的安全性设计方面存在严重问题p j 。1 9 9 0 年1 月 1 5 日，a t & t 公司的1 0 0 多台交换机崩溃并反复重新启动，导致6 万用户在9 个小 时中无法使用长途电话，其原因是新使用的软件在接收到某一种消息后会导致系统 崩溃，并把这种症状传染给与它相邻的系统【4 l 。1 9 9 2 年伦敦救护中心的计算机辅助 发送系统刚启动就崩溃致使这个全世界最大，每天要接待5 0 0 0 个待运病人求救的救 护服务机构瘫痪【5 】。1 9 9 4 年，英国皇家空军的支努干直升机遇难，造成2 9 个服务人 员伤亡，虽然开始时认为一个飞行员操作失误，但是事后经过详细调查表明，事故 是由于直升机的引擎控制系统中的软件故障造成【6 】。1 9 9 9 年9 月2 3 日，美国的火星 气象探测船因为没有进入预定轨道而受到大气压力和摩擦被摧毁，其原因是不同模 块使用的计算单位不同，使计算出的轨道数据出现严重错误。2 0 0 3 年8 月1 4 日发生 的北美大停电使5 0 万人受到影响，直接经济损失6 0 亿美元，其主要原因是软件缺 陷导致报警系统没有报警等等【4 】。鉴于以上这些惨痛的案例，人们对于软件质量的重 视程度越来越高，对于提高软件质量的要求也越来越迫切，如何保证软件的正确性 和可靠性成为日益紧迫的研究课题。 基于程序语义的软件故障定位技术研究 1 1 2 研究意义 除了软件复杂性的增加，日益紧张的市场压力也迫使软件开发者缩短软件开发 和测试周期，尽快将软件推向市场。但是，对于复杂的软件系统而言，详尽的测试 是相当昂贵的，测试阶段不可能检查出软件中所有的错误。因此，用户使用的软件 总会有些瑕疵。对用户而言，有些缺陷是可以容忍的。但是，某些缺陷可能导致系 统出现严重故障，甚至可能会导致极为严重的后果【_ 7 1 。 当软件失效发生后，需要找到引起软件失效的根本原因，将探索软件失效的根 源并寻求其解决方案的过程称为软件调试【8 】( s o f t w a r ed e b u g g i n g ) 。据统计，软件 调试所需的代价占整个软件开发和维护周期的5 0 到8 0 【9 1 。调试程序大概有四个 任务：( 1 ) 找出在失效过程中涉及到的语句，即被失败的测试用例执行到的语句； ( 2 ) 选择可能包含故障的可疑语句，以缩小检查范围；( 3 ) 假设可能的故障原因； ( 4 ) 改变程序变量的值，将程序转换到一个特殊的状态【l0 1 。其中第二项任务即故障 定位( f a u l tl o c a l i z a t i o n ) ，也叫错误定位，是整个调试过程中最耗时费力的任务， 约占软件调试总工作量的9 5 ，是调试过程的重中之重【l ，因而也将软件调试也叫 做故障定位或错误定位。 目前，在实际的软件开发过程中，大多数开发者采用的调试手段是：利用调试 工具进行断点设置，跟踪程序的执行，并分析程序运行时的动态信息进行错误定 位。这些人工的调试技术存在很多缺陷j 第一，在程序执行过程中从程序入口处开 始逐条分析语句，对所有出错代码的可能性都视为一致，不是按一定的优先顺序考 虑错误检查范围，需要耗费大量时间和空间。第二，要求调试人员对出错程序和编 程语言十分熟悉，才能进行断点设置和分析，并依据个人经验来设定错误查找策 略，逐步缩小分析范围，自动化程度差【l2 1 。第三，这种调试技术只利用了一次失败 执行的动态执行信息，忽略了软件测试时获取的海量测试数据。 总的来说，人工的调试技术引入了过多的人工干预和劳力成本，涉及到大量的 人力物力资源，只适用于小型程序。对于大型程序而言，由于程序状态不可计数， 人工跟踪程序状态不切实际。为了缩短软件开发和维护周期，提高软件调试和测试 阶段所获得的数据的利用效率，开发设计高效的、自动或半自动的错误定位技术是 一项非常有意义的研究。 1 2 研究现状 1 2 1 国内外研究现状 随着软件的规模越来越大，系统越来越复杂，开发和维护软件的成本就越来越 高。因此，研究自动或半自动的调试技术辅助软件开发者进行错误定位，一直是一 个非常活跃的研究领域。多年来，国内外研究者在程序调试和自动错误定位方面， 2 硕十学位论文 取得了很多的研究成果。 国外的研究情况主要有：z e l l e r 提出了d e l t a 调试【l 引，通过比较成功执行和失败 执行的程序状态差异，缩小故障的可疑变量及取值集合。w e i s e r 1 4 j 认为程序员在纠 错时，需要忽略那些对暴露缺陷无关的语句，而程序切片正是对程序做了这样的提 取，让程序员集中精力去检查那些与缺陷语句相关的代码。n e e l a mg u p t a 等人【1 5 】提 出综合d e l t a 调试和动态程序切片的方法辅助错误定位。模型检测【l6 】通过穷举搜索软 件系统所有可能的状态空间，验证这些状态是否满足期望的性质。基于模型的故障 定位技术通过静态分析技术从程序源代码中提取模型【l ，或分析程序的动态执行路 径建立程序模型【18 1 ，或结合动静态程序行为特征建立程序模型【1 9 1 以辅助故障定位。 b e nl i b l i t l 2 0 j 采用统计方法分析成功运行和失败运行，比较两类运行中谓词赋值为 t r u e 的不同概率，来检测谓词发生错误的可能性。c h a ol i u 等人1 2 l j 提出了另一种基 于统计学模型的软件故障定位方法s o b e r 。同样的是比较谓词在成功执行和失 败执行中的分布情况，计算谓词的出错概率。不同于b e nl i b l i t 单纯将谓词的两个不 同的期望值相减，s o b e r 采用了新的公式计算故障可疑值。 与本文基于程序频谱的故障定位方法( s p e c t r u m b a s e df a u l tl o c a l i z a t i o n ， s b f l ) 有关的研究工作主要是：t a r a n t u l a 【2 2 】认为，如果一条语句在失败的执行中比 在成功的执行中出现得频繁，那么这条语句出错的概率就比较大。而a m p l e 2 3 j 认 为，程序执行失败与某些特殊的类对象的方法调用序列有关。m a n o sr e n i e r i s 2 4 】通 过试验得出结论，与失败路径最相似的成功路径往往比随机选择的成功路径更有助 于错误定位，提出了“近邻模型 。 国内的研究情况起步较晚，主要是在国外的研究成果的基础上，提出了一些新 的方法和技术，也取得了一些可喜的成果。李必信【2 5 】对程序切片技术及其相关应用 做了一定的探讨。贾晓霞【2 6 】等提出了故障定位的锥状框架，以此为基础将故障定位 问题表示为一个分层细化的过程。王新平1 2 7 】【2 8 1 根据执行轨迹的特征，选择与每个语 句块相关的测试用例来计算该语句块的怀疑率。表1 1 从几个角度对已有方法进行了 分析比较。 表1 1 各种故障定位方法比较 3 基于程序语义的软件故障定位技术研究 1 2 2 目前研究中存在的问题 基于程序频谱的故障定位技术，仅需要程序运行时的动态行为信息( 而这些信 息在程序测试阶段可以大量获得) ，由于其计算复杂度低，无需建模要求等优势， 在软件工程领域得到了广泛的应用。现有的基于程序频谱的故障定位技术都涉及到 代价较高，故障报告存在一定的误差等问题，目前的研究中存在的主要问题是： ( 1 ) 动态的故障定位方法需要记录程序运行的动态信息，而传统的基于程序频 谱的故障定位技术通过对程序进行插桩获得这些信息。对程序进行插桩会引入额外 的程序执行开销，这对于一些大型程序或实时程序而言是不实际，但目前大部分研 究尚未涉及到缩减这部分代价。 ( 2 ) 虽然一次程序执行只是程序语句的一个线性序列，但分析多次程序执行信 息，就能挖掘出程序的一些内部语义特征如方法之间的调用关系等。而目前的 大部分动态的故障定位技术所收集的程序动态运行信息只简单反映了程序运行时的 顺序特征或执行次数，没有结合程序的语义信息。如a m p l e 只关注方法的调用顺序， 没有考虑到方法之间的调用关系；t a r a n t u l a 只关注每条语句在成功执行和失败执行中 的执行次数。 1 3 研究内容 在软件系统开发过程中，软件调试和故障定位是保证其可靠性的重要环节。目 前，利用调试工具进行人工跟踪的方式仍然占据主导地位，这种人工方式过分依赖 于程序员的知识和经验，不仅效率低下，浪费时间，而且不符合现代测试自动化的 要求，因此，设计自动或半自动的故障定位技术有着重要的实际意义。本文介绍了 一种新的程序动态执行信息表示形式，并在此基础上，提出了基于程序语义的故障 定位技术，设计开发了基于程序语义的故障定位原型系统。实验表明，本文提出的 故障定位技术可以减轻程序员调试程序的负担，且采用的收集程序动态执行信息的 手段能大大减少额外的程序执行开销。研究内容主要有以下几点： ( 1 ) 收集程序动态执行信息 程序频谱是对程序动态执行行为的记录，那么程序频谱应该包括哪些程序执行 特征，以及如何表示程序频谱，都是很关键的问题。 ( 2 ) 收集程序频谱的技术 对于动态的故障定位技术而言，收集程序频谱是非常关键的一步。现有的自动 调试和软件错误定位方法，大部分都需要对软件系统进行一定程度的插桩处理。然 而，对程序插桩会增加额外的程序执行开销，这对于大型程序和实时程序，是不可 容忍的。因此，利用什么技术收集程序频谱，以减少额外的执行开销，是本文的第 二个研究重点。 4 硕一i ：学位论文 ( 3 ) 分析程序频谱 在获取了大量的程序频谱之后，如何根据其中隐含的信息，求出程序中可能的 故障可疑集合，形成故障可疑报告，来辅助错误定位呢? 因此，如何处理程序频谱， 以何种策略得出故障报告，是本文最重要的研究点。 ( 4 ) 开发系统实现故障定位技术 任何一项新的技术的成熟和应用，都需要开发出相应的工具作为支撑，因此， 如何开发设计工具实现故障定位技术，是实现自动化测试技术的关键。 1 4 论文结构和章节安排 论文的整体结构和章节安排如下： 第1 章绪论 主要内容包括：简述软件调试和故障定位的研究意义；介绍目前国内外故障定 位技术的研究现状，以及目前研究中存在的问题。 第2 章软件故障定位技术研究综述 主要内容包括：介绍软件故障定位领域的一些相关术语，以及目前研究较多的 几种故障定位技术，包括d e l t a 调试、程序切片、近邻模型、模型检测、以及基于模 型的故障定位技术和基于排序的故障定位技术。 第3 章收集程序频谱 主要内容包括：收集程序频谱是故障定位技术中一个非常关键的步骤。本章首 先介绍各种程序频谱的定义和分类。结合实际应用的需要，提出了一种新的程序频 谱动态方法调用图，它能表达出程序的语义信息程序执行时的方法调用关 系。并且针对传统收集程序频谱的插桩方式引入过多额外的执行开销的问题，本章 介绍一种新的收集程序频谱的方式，那就是利用面向方面编程思想跟踪执行，收集 程序频谱。 第4 章基于程序语义的故障定位技术 主要内容包括：提出了一种基于程序语义的故障定位技术。首先介绍基于程序 语义的故障定位技术流程，接着定义了一种新的程序模型程序动态行为图，将 成功行为图和失败行为图中的差异表现为边的调用概率差，由此得到故障报告。最 后用一个简单的实例程序演示了本文所提出的故障定位技术。 第5 章原型系统设计和实验 主要内容包括：在前文提出的基础上，开发了基于程序语义的故障定位原型系 统，最后通过大量实验验证了本文技术的效率。 结论，对本文工作进行了总结，并对下一步将要开展的研究内容进行了讨论。 5 基于程序语义的软件故障定位技术研究 第2 章软件故障定位技术研究综述 2 1 软件故障 2 1 1b u g 的由来 1 9 4 5 年9 月9 日下午三点，美国海军电脑专家格蕾丝赫柏( g r a c eh o p p e r ) 正 在对第一代计算机h a r v a r dm a r k i i 的1 7 0 0 0 个继电器进行编程。那时的计算机是由许 多庞大且昂贵的真空管组成，并利用大量的电力来使真空管发光。由于计算机运行 产生光和热，引得一只飞蛾( b u g ) 钻进了一支真空管内，导致整个计算机无法工 作。技术人员试了很多办法，最后定位到第7 0 号继电器出错。赫柏观察这个出错的 继电器，发现一只飞蛾躺在中间，已经被继电器打死。她小心地用镊子将蛾子夹出 来，计算机又恢复正常。赫柏用胶条贴上飞蛾放在报告中，赫柏的事件记录本，连 同那个飞蛾，如今陈列在美国历史博物馆中，如图2 1 所示。从此以后，人们将计 算机故障戏称为虫子( b u g ) ，而把找寻错误并改正错误的工作称为( d e b u g ) 2 9 】。 ，- 图2 1 第一个软件b u g 2 1 2 软件故障存在的必然性 缺陷是物品的固有属性，世界上不存在完美无缺的东西，软件也不例外。 软件是抽象的、逻辑的、复杂的人为产品，软件生产是一种高智能、强脑力、 极具体的人类劳动。软件开发的各个阶段都包含了人们大量的创造性劳动，但是人 6 硕上学位论文 的活动和通信都不可能做到完美无缺，尤其是在开发大型软件系统的漫长过程中， 面对的问题错综复杂，人的主观意识刁 可能完全符合客观现实，因此，开发过程中 可能会引进大量的错误，产生这些错误的根源是一系列的“信息转移 。例如，在 需求分析阶段，如果系统分析员错误地理解了用户需求，则会产生由用户到系统分 析员之间的“信息转移错误：系统分析员在书写需求规格说明书时不能正确表达 自己的思维，从而产生了从系统分析员到文件的“信息转移错误，等等。此外， 在编码过程中还会不可避免地引入新的错误，例如，w i n d o w sn t 操作系统的代码大 约有3 2 0 0 万行，这使得错误更可能发生。 软件的错误个数与程序员的个人能力有关。微软的优秀程序员，每千行代码平 均有l 2 个错误；而普通程序员，每千行代码平均有3 5 个错误。黑客大i ) 币s t e v e nl e v y 曾说过：在计算机的发展史上，从未曾有过出乎意料的短暂软件调试过程，“t h e r eh a s n e v e rb e e na nu n e x p e c t e d l ys h o r ts o f t w a r ed e b u g g i n gp e r i o di nt h eh i s t o r yo fc o m p u t e r s ” 2 1 3 相关术语 软件是一系列按照特定顺序组织的计算机数据和指令的集合，它并不只是包括 可以在计算机上运行的程序，与这些程序相关的文档一般也被认为是软件的一部分。一 简单的说，软件就是程序和文档的集合体。本文即将提出的故障定位技术主要是定 位程序中的故障，因此，本文中不严格区分“软件”和“程序 两词的定义。 沿用文献 3 0 】中的定义，首先对软件故障定位技术中涉及到的一些相关术语进行 介绍。 定义2 1 故障( f a u l t ) ：指由于程序员对问题的理解或描述不正确，或由于编 码过程中的疏忽而导致的程序b u g 。在本文接下来的篇幅中，统一使用“故障一词 表示程序中的b u g 。 定义2 2 错误( e r r o r ) ：指由于程序运行时，执行t b u g 相关语句而导致程序到 达的一些异常状态。 一个程序中，可能包含多个故障，而在一次程序执行中，可能只执行到了其中 某些故障。一个故障称为被激活的，如果它导致程序到达错误。本文的研究对象主 要是单故障程序，即程序中只有一个故障。但根据人们的习惯性说法，本文不区分 故障和错误的严格定义。 定义2 。3 软件失效( f a i l u r e ) ：当程序的实际输出结果与预期结果不一致时， 就标志着软件失效。发生软件失效的根本原因是因为程序中存在故障( f a u l t ) ，在 程序的执行过程时，故障被激活( a c t i v a t i o n ) ，导致程序到达错误( e r r o r ) ，而经 过错误的不断传播( p r o p a g a t i o n ) ，使得最终的执行结果与预期结果不一致，标志着 软件失效( f a i l u r e ) 。可以说，软件失效和错误都是由故障引起的症状，这三者之间 的关系如图2 2 所示。 7 基于程序语义的软件故障定位技术研究 被激活传播根源 + 故障斗错误一失效一故障+ 图2 2 故障、错误和失效之间的关系 下面用一个实际的程序例子来演示这些术语之间复杂的关系。如图2 3 所示的一 个j a v a 方法r a t i o n a l s o r t 0 ，该方法的功能是利用冒泡排序法将1 1 个有理数从小到大排 序，这n 个有理数的分子分母分别存储在h u m 和d e n 整形参数数组中。r a t i o n a l s o r t 0 方 法的i 储句体中存在一个故障，当i 制断语句为真时，执行大括号内的语句，交换两 个有理数的分子，但却忘记了交换分母。这样排列一组有理数，程序的实际输出可 能会与预期的正确结果不同，即有可能出现失效。当d e n j 】d e n + 1 】时，执行i f x 括号内的语句，程序会可能会到达错误状态。但是，当前的错误状态可能只是暂时 的，不会直接导致失效。例如，r a t i 。n a l s 。r t ( ) 排列( 詈，三2 ，詈) ，当交换( 詈，吾) 时，程序 进入一个错误的状态，但是这个错误又会被随后的交换所取消，最终的执行结果正 确。由于此次运行的输出结果与预期结果一致，我们不认为程序中存在故障。但是， r a t i o n a l s o r t ( ) 排列g ，三 ，又会得到错误的输出结果( ；，主) ，即发生软件失效。即 使一个程序中存在故障，但并不是对所有的输入都会得到错误的输出结果。通过这 个简单的例子可以看出，故障的表象和引起失效的原因可能相隔甚远，关系扑朔迷 离，必然导致故障定位的复杂性。 v o i dr a t i o n a l s o n ( i n t 珥酞加驰h ed e n ) i n t i , j ，t e m p ； f o r ( i = n - 1 ：泠l ：i - ) f o r ( j = 0 ；j i ；j q i f ( r a t i o n a l g t ( n u m o ，d e n 石in u m d + 1 , d e n u + 1 1 ) ，唪b u g ：f o r g e tt os w a pd e n o m i n a t o r s4 7 t e m p ；n u r n j l ： n u m j 2n u m j + 1 ： n u m o 1 2t e 瑚i p 。o 图2 3j a v a 方法r a t i o n a l s o r t 0 下面介绍一些目前研究比较广泛的故障定位技术。 2 2d e l t a 调试技术 德国s a a r l a n d e s 大学的a n d r e a sz e l l e r 1 2 】【3 1 1 教授提出d e l t a 调试技术，他把一次程 序执行看做是一系列程序状态的转变( 程序状态可以理解为在程序执行某个时刻出 现的变量以及这些变量的取值) 。程序从初始状态开始执行，每执行一步，程序当 前状态就会发生改变，从当前状态转换到下一个程序状态，如此进行，最后到达了 8 硕十学位论文 一个错误的状态，标志着程序执行失败。每一个程序状态都它的前一个状态衍生而 来，但是，可能只有一小部分状态与计算下一个状态是相关的，同理，也并不是所 有程序状态都与执行失败相关，如图2 4 所示为程序执行时的状态转换图。 s t a t e ， s t a t e ? s t a t e 3 s t a t e