【优秀硕士博士论文】基于fcp路径切片的缺陷定位方法研究-刘丹凤-完整版-2016-1-18

分类号TP391单位代码11232密级工学硕士学位论文学位论文版权使用授权书基于FCP路径切片的缺陷定位方法研究学院计算机学院学科专业计算机应用技术学号2013020227作者刘丹凤指导教师牟永敏教授完成日期二一六年一月十八日学位论文版权使用授权书本人完全了解北京信息科技大学关于收集、保存、使用学位论文的规定，按照学校要求提交学位论文的印刷本和电子版本。学校有权保留学位论文并向中国科学技术信息研究所等国家主管部门或其指定机构送交论文的电子版和纸质版，允许论文被查阅和借阅，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。学校有权适当复制、公布论文的全部或部分内容。学校有权将本人的学位论文加入中国优秀硕士学位论文全文数据库和编入中国知识资源总库。学位论文作者签名年月日公开保密（_年_月）保密的学位论文在解密后应遵守此协议指导教师签名学位论文作者签名年月日年月日硕士学位论文原创性声明本人郑重声明所呈交的论文题目为基于FCP路径切片的缺陷定位方法研究学位论文，是本人在导师指导下，进行研究工作所取得的成果。尽我所知，除了文中特别加以标注的内容外，本学位论文的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明并表示了谢意。本学位论文原创性声明的法律责任由本人承担。作者签字年月日摘要软件在越来越多的系统中成为主要的使能部件，软件产品的可靠性事关国计民生，保证软件质量必须及时准确定位软件中隐含的缺陷。随着软件系统的规模和复杂性急剧增大，现有的软件缺陷定位技术面临着严峻的挑战。如何有效改进缺陷定位方法以快速准确定位软件中的缺陷，是软件测试领域亟待解决的问题。论文基于函数调用路径（FUNCTIONCALLINGPATH,FCP）研究缺陷定位方法。动静结合分析源程序，提取函数调用路径；基于失效原理和执行路径差异化设计路径切片算法获得缺陷怀疑序列；通过计算缺陷函数的怀疑度、分析缺陷之间关联构建缺陷拓扑图展现缺陷定位结果。软件系统的一次执行可以抽象为一条函数调用路径。一次执行可以触发多个缺陷，一个缺陷也可以被不同执行触发。成功的执行可能隐含缺陷，失败的执行必定含有缺陷。基于上述失效原理和执行路径的差异化设计切片算法，缩减缺陷定位空间为“函数调用路径路径切片函数结点”，层层递进，逐步求精，最终获得稳定的缺陷怀疑序列。缺陷传播的“涟漪效应”决定了缺陷之间并非独立存在，而是相互关联。论文从路径匹配和统计分析入手设计缺陷怀疑率函数，计算缺陷怀疑函数的怀疑度；引入数据挖掘中频繁模式树（FP树）关联规则，分析缺陷之间的关联度。基于缺陷函数的怀疑度和关联度构建缺陷拓扑图展现多缺陷关联的定位效果。最后，设计基于函数排名的评价方法，设置单缺陷定位对比实验和缺陷关联实验验证论文方法定位缺陷的可行性和有效性。实验结果表明，论文方法可有效缩减查找缺陷时的代码审查范围，提高软件缺陷定位的精度和效率，研究成果也为自动化软件测试的实现提供了新思路。关键词函数调用路径；路径切片；缺陷定位；缺陷关联；函数排名ABSTRACTSOFTWAREHASBECOMETHEMAINENABLEDCOMPONENTINMOREANDMORESYSTEM,THERELIABILITYOFSOFTWAREPRODUCTSRELATEDTOPEOPLESLIVELIHOOD,ENSURESOFTWAREQUALITYMUSTBETIMELYANDACCURATEPOSITIONINGTHEHIDDENFAULTSWITHTHERAPIDDEVELOPMENTOFTHESCALEANDCOMPLEXITYOFSOFTWARESYSTEMS,THEEXISTINGSOFTWAREFAULTSLOCALIZATIONTECHNOLOGYISFACINGSEVERECHALLENGESHOWTOEFFECTIVELYIMPROVETHEAUTOMATICFAULTSLOCATIONMETHODTOQUICKLYANDACCURATELYLOCATETHEFAULTSINTHESOFTWAREISAPROBLEMTOBESOLVEDINTHEFIELDOFSOFTWARETESTINGTHEPAPERBASEDONTHETECHNOLOGYOFFUNCTIONCALLINGPATHFCPTORESEARCHTHEAUTOMATICFAULTSLOCATIONMETHODSTATICANALYSISANDDYNAMICANALYSISOFSOURCEPROGRAMTOEXTRACTTHEFCPBASEDONTHEFAILUREPRINCIPLEANDTHEDIFFERERNCEOFEXECUTEDPATHSTODESIGNPATHSLICINGALGORITHMANDOBTAINTHEFAULTSSUSPECTEDSEQUENCEOFTHESYSTEMBYCALCULATINGTHESUSPECTRATEOFTHEFAULTSFUNCTION,ANALYZINGTHECORRELATIONBETWEENTHEFAULTS,CONSTRUCTINGTHEFAULTSCORRELATIONTOPOLOGYTOSHOWTHEFAULTSLOCATIONRESULTSTHEEXECUTIONTRACKOFSOFTWARESYSTEMCANBEABSTRACTEDASAFCPASINGLEEXECUTIONCANTRIGGERMULTIPLEFAULTS,AFAULTSCANALSOBEPERFORMEDBYDIFFERENTEXECUTIONSTHESUCCESSFULEXECUTIONSOFTHEPOTENTIALOFTHEFAULTS,WHILETHEFAILUREEXECUTIONSMUSTCONTAINFAULTSBASEDONTHEFAILUREPRINCIPLEANDTHEDIFFERENCEOFTHEEXECUTEDPATHSTODESIGNPATHSLICINGALGORITHMTHEALGORITHMGRADUALLYREDUCEDTHEFAULTSLOCATIONSPACEFROMTHEFCPTOTHEPATHSLICESTHENTOFUNCTIONNODES,LAYERSOFPROGRESSIVEANDFINALLYOBTAINEDTHESTEADYFAULTSSUSPECTEDSEQUENCETHE“RIPPLEEFFECT“OFTHEFAULTSDETERMINESTHATTHEYARENOTINDEPENDENT,BUTRELATEDTOEACHOTHERTHISPAPERCONSIDEREDTHEPATHMATCHINGANDSTATISTICALANALYSISPROBABILITYTODESIGNTHEFAULTSSUSPICIONRATEFORMULATOCALCULATETHEFAULTSUSPICIONRATE,ANDINTRODUCEDTHEASSOCIATIONRULESOFFREQUENTPATTERNTREEFPTREEFROMDATAMINETOANALYZETHECORRELATEDEGREEBETWEENTHEFAULTSBASEDONTHESUSPICIONDEGREEANDCORRELATIONDEGREEOFFAULTSTOBUILDTHEFAULTSCORRELATIONTOPOLOGICALGRAPHFORPERFORMINGTHEPOSITIONINGEFFECOFASSOCIATEDFAULTSFINALLY，THISPAPERDESIGNEDFUNCTIONBASEDRANKINGEVALUATIONMETHODANDSETTEDTHESINGLEFAULTLOCATIONCONTRASTEXPERIMENTANDTHEMULTIFAULTSRELATEDVERIFICATIONEXPERIMENTTOVERIFYTHEFEASIBILITYANDEFFECTIVENESSOFTHELOCATINGMETHODPROPOSEDBYTHISPAPEREXPERIMENTALRESULTSSHOWTHATTHEFCPPATHSLICINGMETHODPROPOSEDBYTHISPAPERCANEFFECTIVELYREDUCETHECODEREVIEWSCOPEWHENFIXEDTHEFAULTS,IMPROVETHEACCURACYANDEFFICIENCYOFTHESOFTWAREFAULTSLOCATION,ANDTHERESEARCHRESULTSALSOPROVIDESANEWTHINKINGOFTHEAUTOMATEDSOFTWARETESTINGKEYWORDSFUNCTIONCALLINGPATH,PATHSLICING,FAULTLOCATION,FAULTSCORRELATION,FUNCTIONBASEDRANKING目录第1章绪论111课题研究背景112国内外研究现状213课题来源514主要研究内容515论文组织结构6第2章相关理论与技术821函数调用路径822缺陷定位问题描述923程序切片与路径切片1024本章小结12第3章缺陷定位方法概述1331基于FCP路径切片的缺陷定位方法概述1332动静结合分析程序1433路径切片算法1434缺陷拓扑图1535本章小结16第4章算法设计与实现1741动静结合提取FCP17411静态分析17412动态分析2342路径切片算法获得FSS2543关联分析构建缺陷拓扑图30431怀疑率计算30432缺陷关联分析31433缺陷拓扑图3144本章小节34第5章实验与评测3551目标程序3552基于函数排名的评价方法3653实验与评价37531路径切片实例分析37532单缺陷定位算法比较46533缺陷关联定位验证4854本章小结50第6章总结与展望5161论文的工作与总结5162研究工作展望51致谢53参考文献53个人简历在学期间发表的学术论文及研究成果58第1章绪论11课题研究背景随着计算机技术的日益普及和不断深入，软件系统的规模和复杂性的急剧增大，软件在很多系统中已经成为了主要的使能部件。在许多安全攸关的领域如交通、航空航天、医疗设备、武器装备、金融、核能等，软件系统如果发生失效将导致非常严重的后果，保障软件系统的质量成为迫切的需求和挑战1。软件的生命周期中需求变动、技术更新、版本跌代、测试和维护能力的限制，使得由于软件缺陷引发软件失效的情况还不能完全避免。从软件本身的失效机理来看，对于一个隐含缺陷的软件产品，执行路径经过某个潜在的缺陷，激活该缺陷时，就会导致软件失效。软件失效后，如何找到引发软件失效的缺陷位置或引发失效的原因，就是软件缺陷定位问题2。据统计，软件测试约占软件开发和维护成本的50以上3，其中软件调试既对软件缺陷进行定位和修复是最耗时耗力的任务之一4。在实际环境中，软件调试人员定位程序中的缺陷是一个高度人工相关的过程。这个过程往往开始于执行一个或者一组测试用例，然后选择一个特定的失败的测试用例再执行，使用设置断点的方法逐步调试分析，直到查找到真正的程序缺陷位置。这个过程不但要求调试人员具备很强的技术水平和丰富的调试经验，而且耗时耗力没有很好的针对性。传统的软件缺陷定位很难满足和适应大型复杂软件的调试需求5，缺陷定位过程需要融入更多自动化技术，定位方法的些许改进都可能大大降低调试成本。近年来，软件自动化调试的研究成果在定位各种情况下的软件缺陷中已经表现出了良好的特性。现有的缺陷定位研究可以从不同维度进行划分从缺陷粒度上分为程序语句、基本块、分支、函数、类或包6，从研究模式上分为“ONEFAULTATONETIME”和“MANYFAULTSATONETIME”7，从定位方法上一般分为静态分析和动态执行，从技术层面分为基于程序依赖、基于概率模型和基于数据挖掘算法8。定位不同场景的软件缺陷需要具体情况而定，目前还没有一种方法可以完全揭示软件中潜在的所有缺陷，这也正促使了更多研究者对现有的缺陷定位方法进行不断优化与创新。12国内外研究现状缺陷定位一直是软件测试领域研究的重点问题，与其他软件工程领域的研究问题结合紧密，如测试过程管理、测试用例自动生成等。缺陷定位方法的研究最早可以追溯到20世纪70年代，WEISER在他的博士论文中首次提出了程序切片9可用于程序理解和软件调试。30多年来很多专家学者提出了一系列行之有效的自动化缺陷定位方法，现有研究成果依据研究技术的不同可以做如下分类（1）基于程序中的数据依赖或控制依赖。BACH等人10提出了基于概率程序依赖图的缺陷定位模型，对与缺陷相关联的程序的不确定性进行概率分析和推理，从而诊断缺陷。CHRIST等人11提出了一种基于控制流的缺陷定位方法并提出DELTA调试技术，判断缺陷定位相关的条件分支真值，生成有意义的缺陷解释来定位缺陷。ZHAO等人12提出了一种基于控制流分析的有意识执行的缺陷定位方法，使用边的怀疑度加权的覆盖信息分析缺陷定位过程。王映辉等人13提出了一种软件需求变化追踪方法，阐述软件变化跟踪的整体过程框架。邬晟峰等人14提出了准完全最大距离测试新算法的思想和构建理论，使得每一个测试码可以尽可能多地独立检测到更多不重复的故障。程序切片是一种特殊的程序依赖，PARITOSH和ZHANG等人15,16在WEISER之后进一步研究了在缺陷定位中应用切片技术，发现动态切片更适用于缺陷定位与程序理解。文万志等人17提出基于条件执行切片谱的多错误定位方法，提高了多错误定位的效率。姜淑娟等人18提出了一种基于切片谱的错误定位框架，评估不同的切片选择策略及怀疑度计算公式对错误定位效率的影响。（2）基于程序执行轨迹（或覆盖信息）的统计指标或模型。RENIERIS和REISS19对程序执行成功和执行失败的相似轨迹进行比较，基于相似程序频谱提出了最近邻查询NEARESTNEIGHBORQUERIES，NNQ方法。JONES等人20提出了使用不同颜色表征语句缺陷可疑程度的TARANTULA方法，认为语句的缺陷怀疑度与其经过此语句执行失败的次数正相关。ABREU等人21对多缺陷定位进行了研究，引入分子生物学领域的OCHIAI相关系数到缺陷怀疑率的计算中，通过实验证明在多缺陷的定位中表现良好。LIBLIT等人22从谓词角度分析，认为谓词的取值必然会影响其后隐含的程序缺陷，提出了一种互操作分离缺陷定位技术（COOPERATIONBUGISOLATION,CBI）。LIU等人23提出了基于假设检验的SOBER方法，此方法在CBI的基础上进行，关键点是对谓词在执行成功和执行失败时的取值模式进行建模。DALLMEIER等人24提出了基于方法调用序列的AMPLE技术，认为只出现在执行成功或执行失败路径中的方法调用子序列含有缺陷的可能性最大，最应该被怀疑。CUNY等人25改进了其之前提出CROSSTAB统计方法的缺陷定位方法，变为CBT（CROSSTABBASEDTCAHNIQUE）方法，该方法在时间消耗和测试组件敏感性等方面表现出了良好性。ZHANG等人26从统计方差上估计失败运行，认为只有失效运行轨迹才可能含有缺陷，提出了（FONLY）缺陷定位方法。何伟等人27提出了一种基于调用图的面向对象软件类间方法/消息路径自动生成的方法，为基于路径的缺陷定位提供了参考。惠战伟等人28提出了基于程序特征谱覆盖统计的整数溢出错误定位技术，构建整数溢出错误定位模型INTRANK，改进了现有错误定位模型。周吴杰等人29提出了基于组合测试的故障定位模型，并在此模型的基础上提出了部分覆盖表的错误交互定位方法。叶钢等人30提出了一种基于KOLMOGOROVSMIRNOV检验的缺陷定位方法，该方法在小样本和非正态分布的样本集上具有较好的适用性。陈翔等人31系统分析了基于程序频谱的动态缺陷定位（SPECTRUMBASEDDYNAMICFAULTLOCALIZATION,SFL）近年来取得的研究成果，提出SFL框架并对框架内的影响因素、评价指标和应用场景进行了总结和分析。（3）基于数据挖掘技术。DICKINSON和PODGURSKI32首次提出了对程序失效应用数据挖掘技术进行聚类分析来降低调试的代价，MAO等人33为了提高聚类的精度，将失效用例和非失效用例进行了分离、相异性度量改进。后续研究者有的通过分析程序失效与函数返回值、函数调用对等之间的关联信息进行缺陷定位34,35，有的研究者36运用频繁项集对程序元素函数、变量和数据类型等进行使用模式挖掘，再运用挖掘结果指导缺陷定位。BRUN等人37提出了基于支持向量机的缺陷定位方法，运用支持向量机和决策树对缺陷不变式进行分类。DENMAT等人38提出基于关联规则的缺陷定位方法挖掘执行轨迹，用支持度和置信度筛选与缺陷相关的语句。WANG等人39提出了基于神经网络的缺陷定位方法，使用改进的径向基（RBF）神经网络分析执行成功、失败的路径及相应的语句覆盖信息。BURGER等人40基于数据挖掘，将DELTAT调试技术和动态切片技术结合起来降低了缺陷的平均搜索区域。江建慧等人41,42基于软件不同失效过程偏差建立软件可靠性模型，在此研究基础上提出了一种对程序故障行为和失效行为的聚类有效性验证方法。在实际的软件开发过程中，由于软件的各部分之间存在依赖关系，软件中一个实体隐含缺陷，往往会影响到与之直接或间接关联的其它实体，从而导致一连串的软件失效，这种现象被称为“涟漪效应”RIPPLEEFFECT43。KATERINA和TRIVEDI44在2000年引入了缺陷关联的概念，构建MARKOV模型对存在缺陷关联的软件可靠性进行分析。在此之前，BISHOP等人45已经提出可以使用软件失效的屏蔽效应来解释为什么软件缺陷关联会导致一系列失效关联，并可以通过恰当合适的软件设计和开发技术来杜绝缺陷关联。CHEN等人46基于测试过程并非独立的思想，提出了一种MARKOV二进制过程模型，用来预测使用随机策略能够发现的软件缺陷个数。测试一般都会有结束准则，为了决定何时停止测试，SAHINOGLU47根据缺陷关联/分支覆盖关联提出了一种BAYESIAN测试停止规则。李等人48从缺陷外部表现和内部特征两个角度自动分析缺陷报告间的相关性。包晓安等人49使用马尔可夫链测试模型验证了运用缺陷之间的关联信息选择测试用例集合可以得到更好的测试结果的结论。有的研究者试图将ONEBUGATATIME的方法应用于多缺陷关联的定位问题，但效果并不满意；有的研究者50采用数据挖掘的聚类方法来提高同时定位多个缺陷的并行性，其实仍然为单缺陷定位的并行处理，没有分析缺陷间的关联，定位效果也不是太理想；有的研究者5153采用神经网络处理测试用例和缺陷之间的复杂关系，分析缺陷间的征兆相关信息，很大程度上提高了多缺陷定位的准确性，但其要求输入的完备性是要付出很大代价的。此外，对于缺陷定位比较关键的是缺陷怀疑度计算公式。JONES等人20使用TARANTULA方法的公式计算每个语句的怀疑度，认为哪个语句怀疑度值越大，就说明该语句隐含缺陷的概率越大。CHEN等人54提出了JACCARD错误定位方法，使用聚类分析中的系数分析实体的怀疑度；ABREU21用OCHIAI来定义语句的怀疑度。ARTZI等人55将TARANTULA20、JACCARD54、OCHIAI21这3种缺陷定位方法应用到WEB缺陷定位中，经过实验分析，发现这3种方法在WEB环境的缺陷定位中都表现出良好效果。NAISH56在总结了33种基于怀疑度的缺陷定位方法后，提出了两种最优化的缺陷怀疑度计算函数，分别命名为NAISH1和NAISH2。XIE等人57对NAISH提到的30个怀疑度公式的缺陷定位性能进行了理论分析和实验证明，也提出了两组最优公式，其中一组为NAISH1和NAISH2，另外一组包括三种，如下所示,1FFPPFUFFFUPUPNSOSAISHSWONGSRSELAONNOSTHERWIBARY现有的缺陷定位技术都会在一定条件下表现出良好的特性，但也不可避免存在一些问题。例如1语句级别或语句块级别的缺陷定位如TARANTULA20、JACCARD54、OCHIAI21等会产生庞大的测试数据集，不利于测试的高效进行。2通常的基于执行轨迹的定位方法假设测试用例集完备充分，足以满足缺陷定位的需要。这个假设缺乏直观的考虑和实验验证，实际中，缺陷定位需要尽可能多的测试用例执行以达到完全覆盖准则。3现有的缺陷定位方法大多是针对单个缺陷的定位，然而程序中缺陷的传播性决定了缺陷并非独立存在，分析软件缺陷关联实现多缺陷的定位，对于缺陷排除、软件质量保证具有重要的意义。论文提出基于FCP的路径切片算法定位软件缺陷，从函数粒度入手动静结合分析源程序，基于软件失效原理设计路径切片算法，引入概率统计和数据挖掘技术分析构建缺陷关联拓扑图，最终实现定位软件中的单一缺陷并展现多缺陷定位的关联效果。13课题来源课题来源于解放军某部软件测评中心的科研项目“软件测试自动化新技术方法研究”，是项目中研究缺陷定位和多缺陷关联的部分。自2008年至今，课题组在自动化测试领域做了很多研究和实践工作，突破性提出了基于函数调用路径的思想，并基于此思想拓展研究，先后实现了多个版本的自动化测试工具，研究成果获得了解放军科技进步二等奖。REGRESSIONTESTFORC10版，通过静态扫描分析源码，得到函数调用关系，并基于调用关系图设计生成测试用例58,59。REGRESSIONTESTFORC20版，主要针对C源程序中调用点与定义间的不确定问题进行研究，实现了多态唯一性和重载唯一性的确定60,61。REGRESSIONTESTFORJAVA版，利用JAVA中特有的反射技术得到继承方法树和字节码优化框架，设计最小搜索树算法，解决了JAVA多态唯一性确定问题，继而得到基本函数调用路径62。AUTOTEST10版提出动态函数调用路径提取方法，使用动态测试方法跟踪函数调用路径，并对测试用例进行分级和优化63。AUTOTEST20将基于函数调用路径的研究方法应用到软件结构的提取中，提出了更高效的函数功能提取方法，实现软件设计与实现的一致性验证64。随着研究的不断深入，课题组结合软件开发测试的实际需要，对测试方法提出了更多的要求。将基于函数调用路径的研究方法应用到软件缺陷的定位中65，成为了课题组的一个重点研究方向。14主要研究内容论文基于函数调用路径（FCP），通过动静分析源程序提取函数调用路径，设计路径切片算法获得缺陷怀疑序列，计算缺陷怀疑度、分析缺陷关联构建缺陷关联拓扑图展现缺陷定位效果。缺陷定位整体思路如图11所示，输入为源程序和测试用例集，关键算法为路径切分，逐步缩减缺陷定位问题空间为“函数调用路径路径切片函数结点”，层层递进，逐步求精，最后输出缺陷定位关联拓扑。其中P表示被测程序，TT1,T2,TN是测试用例集合，PA表示隐含缺陷的函数调用路径集合，PPA和PF1F2F3为路径切片算法，SLICES1,S2,SN为PA被路径切片算法第一次切片PPA处理后获得的缺陷怀疑路径切片，FF1,F2,F3表示SLICE被切片算法PF1F2F3处理后获得的缺陷怀疑函数结点集合，R表示对F构建缺陷拓扑PTG得到的多缺陷关联拓扑图，R即为缺陷定位的目标，最终以拓扑图的形式表现缺陷定位效果。T1T2T3T4TNF1F2F3TPFPF1F2F3INPUTSSLICETARGETLOCATIONFCPPAPPAPATHSLICESF1F2RF3P12FNP3NPN2P1NSUSF1SUSF2SUSF3SUSFNFTGPTG图11缺陷定位研究思路图主要研究内容为（1）动静结合提取函数调用路径静态分析扫描源程序，可以较全面的获得函数调用关系，然后通过路径分析生成函数调用关系图。动态执行测试用例集，根据测试用例是否执行通过分别提取执行成功的函数调用路径和执行失败的函数调用路径。其中，连接静态分析和动态分析的关键是插装技术。（2）路径切片算法获得缺陷怀疑序列基于函数调用的特点，根据软件失效机理与执行成功路径和执行失败路径的差异化，设计路径切片算法，层层缩减缺陷定位空间，获得稳定怀疑路径切片集，进而获得缺陷怀疑序列。（3）关联分析构建缺陷拓扑图设计缺陷怀疑率公式计算缺陷怀疑函数的怀疑度，引入FP树关联规则挖掘缺陷函数的关联度，基于缺陷函数的怀疑度和关联度构建缺陷拓扑图，展现多缺陷关联的定位效果。15论文组织结构论文共分6章第1章，绪论。主要介绍了课题研究背景，国内外研究现状，课题来源、主要研究内容以及论文组织结构。第2章，相关理论与技术。主要介绍了函数调用路径、缺陷定位问题、程序切片和路径切片三个方面的相关理论和技术。第3章，缺陷定位方法概述。主要介绍了基于函数调用路径切片的缺陷定位方法的概要实现。先从总体上描述系统框架，然后分别介绍动静结合分析源程序、路径切片算法和基于关联分析构建缺陷关联拓扑图的实现框架。第4章，算法设计与实现。主要介绍了动静结合提取FCP、路径切片算法获得缺陷怀疑序列和缺陷关联分析构建软件关联拓扑图三部分内容的具体算法设计和实现。第5章，实验与评测。对提出的缺陷定位方法设计实验进行验证，介绍了实验的目标程序、基于函数排名的评价方法、实验和评测结果。第6章，总结与展望。对课题研究工作进行总结，并对下一步的工作进行展望。第2章相关理论与技术21函数调用路径函数调用路径5思想是在路径覆盖测试优化和回归测试中发展起来的。路径覆盖是指使用大量的测试用例，用于覆盖程序中的每一条路径。在面向函数调用路径的思想中，可以将一个任务理解为一条函数调用路径，一个完整的系统可以理解为是由有限条函数调用路径组成。若对所有的函数调用路径均进行了充分测试并且无误的话，那么这个系统是可靠的。面向函数调用路径的软件测试方法简化了面向基本路径的软件测试问题，使得面向基本路径的测试工作量成指数级降低，将面向路径的测试由不可能变成了可能。函数调用关系是以函数为基本处理单元，基于控制流和数据流的逻辑关系得来的。函数调用关系图是一种有效反映函数调用关系的有向图，函数调用路径是函数调用关系图上的一次函数执行序列。定义1函数调用关系图（FUNCTIONCALLINGGRAPH,FCG）G是一种有向图G。其中V是节点集，RX,Y|X,YV是有向图的连接准则。弧ETE,HE连接G中相邻的两个节点TE和HE，其中TE为弧头、HE为弧尾。定义2函数调用路径（FUNCTIONCALLINGPATH,FCP）W是函数调用关系图G中的一条节点序列WIVI0,VI1,VIM。路径中的节点为函数，路径中相邻节点表示调用关系或者顺序执行关系。定义3测试用例和函数调用路径定义成一个二元关系Q给定一个程序P和P中一条函数调用路径W,T是一个测试用例,若P运行时输入T,程序运行后的路径表示为W,则关系QT,W成立。函数调用关系与函数包含关系的不同之处在于，函数包含关系只关注源代码中一个函数包含了哪些函数，而不考虑函数之间是顺序执行还是在不同的分支上分别执行31。比如一些开源工具CALLTREE，CODEVIZ，GPROF等在绘制函数调用关系图时，其所绘制的是函数包含关系图，并不包含函数之间的控制逻辑关系，如图21所示。MAINF1ENDMAINF1F2ENDVOIDMAININTS0F1/顺序调用IFS0F2/条件选择ELSEF3（A）源代码（B）包含图（C）调用图F2F3F3图21函数调用关系和函数包含关系图21中举例说明了函数包含关系和函数调用关系的区别。在图21中（A）所示程序片段中，F1、F2、F3三个函数在主函数MAIN中被调用了，在不考虑调用这些函数时的控制逻辑条件下，函数包含关系图可以表示为图21（B）所示部分；在考虑逻辑分支的情况下（由IF语句产生，使得函数F2，F3不可能同时执行），函数调用关系可以表示为图21中（C）所示的函数调用关系图。函数包含关系和函数调用关系在应用上的一点区别在于函数调用关系能够更准确的反映函数执行路径。比如在本例中，从函数包含关系图中只能看出MAIN函数包含了哪些函数，不能反映函数执行顺序，甚至可能让人误解为有三条路径；而函数调用关系图会准确的反映出程序存在路径1（MAINF1F2END）和路径2（MAINF1F3END）两条函数调用路径。22缺陷定位问题描述软件缺陷定位的主要目标是根据软件运行的内部状态或外部结果来快速准确地定位软件中存在的缺陷片断。在分析软件执行路径时，如果将分析粒度定义为“基本块”（它可以是程序模块、代码行、分支或函数，根据不同的情况而定），软件的运行过程也就是对这些基本块的调用过程。因此，在软件运行时，基本块的调用序列就构成了软件的运行序列，它准确的反映了软件实际的运行过程2。定义4对某一需要缺陷定位的程序PS1,S2,SI,SM，SI代表程序P的第I个函数。测试用例集TT1,T2,TI,TN，其中TI代表第I个测试用例。TIAI,BI,，其中AI为TI的输入，BI是P执行AI后的预期结果。测试用例TI在程序P1上的一次运行可以用函数调用路径WI来表示，WI是被TI执行了的函数序列，则有二元关系QITI，WI。TI在P上的一次运行的实际结果BIPAI,如果BIBI，则称TI在程序P上通过了，TI简称为通过的测试用例，TI的执行轨迹WI称为执行成功的函数调用路径（SUCCESSEDFUNCTIONSCALLINGPATH,SFCP）；反之，如果BI，则称TI在程序P上未通过，TI简称未通过的测试用例，TI的执行轨迹WI称为执行失败的函数调用路径（FAILEDFUNCTIONSCALLINGPATH,FFCP）。所有的测试用例执行后则有Q（T,W），测试用例集T对应一个函数调用路径集W，且T中的元素和W中的元素一一对应。定义5按照测试用例是否通过，测试用例集T被分成两个互不相交的集合TP和TF,TP是通过的测试用例集合，TF是未通过的测试用例集合。函数调用路径集W被分成两个互不相交的SFCP集合WP和FFCP集合WF。TPTI|PAIBI；TFTI|PAIBI21WPWI|TITP；WFWI|TITF22定义6缺陷怀疑路径FAULTSSUSPECTEDPATH,FSPWFSPW1,W2,WK,WN,WKF1,F2,FJ,FPJ1,2P是一条可能隐含缺陷的函数调用路径，称为缺陷怀疑路径，FJ是可能隐含缺陷的函数节点，表示调用关系或者顺序执行关系。相反，如果一条函数路径排除了隐含缺陷的可能性，则称其为稳定路径STABLEPATH,STP。定义7缺陷怀疑序列（FAULTSSUSPECTEDSEQUENCE,FSS）是一个函数节点序列，记为RR1,R2,RI,RM,RWFSP，其中RI是隐含缺陷的函数节点，（RJ，RJ1）中RJ和RJ1没有顺序关系。定义8程序中每一个函数FI都可能隐含缺陷，这种隐含缺陷的函数定义为缺陷怀疑函数（FAULTSUSPECTEDFUNCTION，FSF），其隐含缺陷的程度称为该函数的缺陷怀疑度。用区间0,1的实数表示怀疑度，这个实数叫做函数FI的怀疑率SUSFI,怀疑率越高则该函数被认为含有缺陷的可能性越大。定义9缺陷拓扑图。所有隐含缺陷的函数节点以及他们之间的关联关系构成一个缺陷拓扑图GTPV，E，S，P，其中V为节点集，E是边集，E的每个元素EI，VIVJ的方向表示VI直接或间接调用了VJ。S表示V中所有节点的缺陷怀疑度集合，对于VIV，其隐含缺陷的程度称为缺陷怀疑度，记为SUSVI，与之有直接或间接调用关系的VJ受其影响发生缺陷的概率，记为PIJ，0PIJ称作VJ相1，对VI的缺陷关联度，P就表示所有节点之间的关联度集合。论文研究的缺陷定位方法，基于函数粒度，根据执行测试用例集对应的路径信息，采用路径切片算法获得缺陷怀疑序列，计算出缺陷怀疑函数的怀疑度和缺陷怀疑函数之间的关联度，最终构建缺陷拓扑图表示缺陷定位效果。23程序切片与路径切片程序切片（PROGRAMSLICING）是一种基于控制流和数据流分析的程序分解技术，最早由MARKWEISER于1979年在他的博士论文中提出9，后来他又发表两篇文章对这种切片技术进行完善和推广。程序切片通过选择感兴趣的程序点来约简程序，把程序逐步缩减为只含有与某个特定计算相关的语句集，从而更加方便和直接的理解和分析程序。这种技术由于其他技术无法替代的作用引起了研究者的广泛关注，在软件维护、程序调试、代码理解以及逆向工程等方面都有很多研究和应用。三十多年来，研究者们对程序切片技术进行了不断扩展，经历了多个发展阶段，出现了许多切片标准及其算法和相应的实现工具，丰富和发展了程序切片的内涵，其发展历程如图22所示。基于控制流的数据流方程基于程序依赖图面向对象的程序切片程序切片变体图22程序切片技术的发展历程初期阶段，即MARKWEISE提出切片概念的阶段，主要是通过控制流图的数据流方程来计算程序切片。发展阶段，是基于程序依赖图PROGRAMDEPENDENCEGRAPH,PDG获得切片的阶段，此阶段程序切片有了很多新的概念和算法。MARKWEISE通过PDG得到过程内切片INTRAPROCEDURALSLICE，HOWITZ将PDG扩展为系统依赖图SYSTEMDEPENDENCEGRAPH,SDG得到过程间切片INTERPROCEDURALSLICE,解决了切片技术中的过程调用问题。由于以上的程序切片包含了不执行程序的思想，也是一种静态切片。之后，KOREL和LASKI考虑程序的特定执行情况，提出了动态切片的概念。面向对象阶段，在1996年MJHORRALD等人首次使用类依赖图（CLASSDEPENDENCEGRAPH,CDG）来扩展系统依赖图。随后CHRISTONSTEINDL在1999年通过对各种数据流以及控制流的计算，提出了面向对象程序切片计算的解决方法。目前是程序切片变体阶段，涌现出了不同的程序切片的变体形式，例如条件切片、规约切片、砍片、削片、层次切片等等，这些切片变体种类不同但本质是一样的，都大大促进了程序切片技术的前进和发展。论文借鉴程序切片选择感兴趣的程序点来约简程序的思想，基于FCP提升程序切片的粒度到函数级别研究软件缺陷定位方法。论文从函数调用角度提出程序切片的变体路径切片，并基于软件失效原理和执行路径的差异化设计路径切片算法，纵向切分FCP路径，逐步缩减缺陷定位问题的求解空间为“执行路径路径切片函数结点”。24本章小结本章主要介绍了与论文相关的理论和技术，包括函数调用路径、缺陷定位问题描述以及程序切片和路径切片。相关领域中都有相似的基本研究方法，各领域的方法可互相借鉴创新以便更好的研究发展。第3章缺陷定位方法概述31基于FCP路径切片的缺陷定位方法概述论文采用动静结合方法分析源程序提取FCP，根据失效原理及执行成功和执行失败的函数调用路径的差异化，设计路径切片算法获得稳定缺陷怀疑序列，通过计算缺陷怀疑度并分析缺陷关联构建缺陷拓扑图，最终以缺陷拓扑图的形式展现缺陷定位和缺陷关联的效果。源程序函数调用关系图测试用例集路径切片算法提取函数调用关系提取函数调用路径怀疑率计算缺陷怀疑序列路径分析执行成功路径关联分析动静分析执行失败路径构建缺陷拓扑缺陷拓扑图图31FCP缺陷定位方法系统框架基于FCP路径切片的缺陷定位方法系统框架如上图31所示，从图中可以看出，输入为源程序和测试用例集，输出为缺陷拓扑图。整体方案可以划分为如下步骤（1）动静结合分析源程序，加载测试用例集，提取函数调用关系和动态执行路径，根据用例执行成功和执行失败划分动态函数调用路径为执行成功路径集和执行失败路径集。（2）全局函数调用关系和动态函数调用路径经过路径分析生成函数调用关系图，作为路径切片算法的输入，层层切分失败路径，获得稳定的缺陷怀疑序列。（3）基于函数调用路径的特征，计算缺陷怀疑序列中函数结点的怀疑度。基于FP树算法，挖掘缺陷怀疑序列中缺陷怀疑函数的关联关系，构建缺陷拓扑图展现多缺陷关联效果。32动静结合分析程序论文结合动静分析技术提取源程序的函数调用关系和动态执行路径。静态分析方法可以在不运行程序的情况下较早较全面的获取一些程序信息，动态分析方法可以发现静态方法无法触发的隐含问题，插装技术是连接静态分析和动态分析的关键。探针库插装源文件预处理路径装点流静态FCP动态FCP路径分析用例执行路径提取测试用例集源程序植入图32动静结合分析源程序动静结合分析源程序的框架图如图32所示，其中静态分析主要分为三个模块预处理模块进行词法和语法分析，插装模块设计探针库植入源程序并记录插装信息，路径分析模块设计算法提取函数调用关系。动态分析基于插装后的源程序执行测试用例集，设计动态路径优化算法，在拆分函数调用路径装点流的过程中进行去重、去冗余处理，得到优化后的执行成功路径集和执行失败路径集。33路径切片算法通过动态路径优化算法得到的动态FCP路径分为执行成功的函数调用路径集SFCP和执行失败的函数调用路径集FFCP。基于失效原理，本文认为（1）执行成功的函数调用路径中可能隐含缺陷；（2）执行失败的函数调用路径一定含有缺陷；（3）执行成功路径和执行失败路径中公共的路径片段隐含缺陷的可能性最小，本文认为此路径片段不含有缺陷；（4）只在执行失败的函数调用路径中出现的路径片段，本文认为其隐含缺陷的可能性最大。那么路径切片算法就是在静态分析获得的函数调用路径基本集的大空间内，基于SFCP和FFCP的差异化对FFCP进行切分，找到最稳定的缺陷怀疑路径片段，然后拆分路径片段为缺陷怀疑序列的过程。路径切片算法的思路可以通过下图33缩减可疑空间的过程模型表示，其中S1表示FCP基本集，即为定位缺陷的最大空间；S2表示执行成功FCP集，S3S4表示执行失败路径空间；S3包含在S2内表示稳定路径集，即执行成功FCP集和执行失败路径集中公有的部分，这部分是不可能隐含缺陷的路径切片空间；S4表示稳定的缺陷怀疑路径集，即执行失败路径中含有缺陷概率最大的路径切片空间；那么，从S4中去除与S2和S3公共的空间，得到的其中部分就是最终的缺陷定位问题的有用空间。S1FCP_BASICSETS2FCP_SUCCSETS4SCP_SET（）S3STP_SET图33可疑空间缩减过程模型34缺陷拓扑图在实际的测试中，软件的失效不是相互独立的，软件中的缺陷关联普遍存在，某些实体隐含缺陷会导致其他实体也发生缺陷从而引发一系列的软件失效。论文通过计算缺陷函数的怀疑度和关联度构建软件缺陷拓扑图，表现多缺陷关联的定位效果。图34给出了构建缺陷拓扑图的过程，其中左边的RF1,F2,FI,FM表示路径切片算法获得的缺陷怀疑序列，FI表示隐含有缺陷的怀疑函数；中间SUSFI表示缺陷函数的怀疑度计算，SUPPORTFI,FI表示FI和FI之间的关联分析；右边为最终构建的缺陷拓扑图，其中F1F4表示R中的4个函数，有向边表示缺陷关联传播的方向，边的权重PIJ表示缺陷函数间的关联程度，节点的权值表示缺陷的怀疑度。例如，有向边上P21就表示F2含有缺陷时，F1含有缺陷的概率。P21P32P31P14RF1,F2,FI,FMSUSFISUPPORTFI,FJP12P23F1F2F3F4S1S4S2S3图34构建缺陷拓扑图35本章小结本章首先介绍了基于函数调用路径切片的缺陷定位方法的系统框架。然后分别介绍论文定位方法中关键技术如动静结合分析程序提取FCP、路径切片算法和构建软件缺陷拓扑图的技术框架和实现思路。第4章算法设计与实现现有的基于执行路径的缺陷方法大都基于代码级，路径的每一节点通常对应程序中的某行或某几行代码。对于大型程序，代码级别得到的路径数据量会呈爆炸式增长；并且对于复杂的测试用例的执行轨迹，语句级的路径显然不能很好的描述路径间的相似性。论文提出的基于FCP的缺陷定位方法实现了函数调用与控制逻辑的结合，通过动静结合方法获得FCP，设计路径切片算法获得最稳定缺陷怀疑序列FSS，分析缺陷关联构建缺陷拓扑图展现缺陷关联定位效果。41动静结合提取FCP411静态分析静态分析源程序获得静态FCP集，分为预处理、插装和静态路径分析三个模块。预处理模块设计基于有限状态机61的词法语法分析器产生程序信息（PROGRAMINFORMATION，PI）文件并确定适合插装的装点位置。插装模块设计插装探针库植入源程序，并记录插装信息。路径分析模块分析插装后的源代码和PI文件，得出函数模块间调用的前驱后继关系、控制流分支信息等，设计静态路径提取函数调用基本集并生成全局函数调用关系图。4111预处理为了对静态路径分析和动态测试提供信息，预处理要在词法分析和语法分析时提取PI文件，包括函数结构信息表、函数及调用关系列表和源程序的控制关键字列表等信息。词法语法分析器分为词法分析和模式匹配，其中词法分析主要是将程序分为单词，模式匹配是根据设计的模式，扫描处理源程序，提取静态分析信息，提取后的信息存储到PI文件。以下为几个重要的数据结构函数结构信息表STRUCTFUNTABCHARFUNNAME/函数名/INTFUNLENTH/记录函数名的长度/INTFUNSTAR/记录函数的起始行号/INTFUNEND/记录函数的终止行号/STRUCTDRVARREFVAR/函数引用的变量/STRUCTVARTABPARA/函数定义的形式参数/STRUCTFUNTABNEXT/链表的下一节点/STRUCTCALLTABCALL/描述调用哪个函数/STRUCTKEYWORDTABKEYWORLD/描述函数体中的关键字/函数调用关系表STRUCTCALLTABINTFUNNUM/被调用函数编号/INTFLAG/0未定义函数，1己定义函数/STRUCTVARTABFPARA/调用函数时的实参/STRUCTCALLTABNEXTCALL/链表的下一节点/控制关键字表STRUCTKEYWORDTABINTFUNNUM/关键字所在的函数编号/INTKEYWORDNUM/关键字编号/INTKEYTRUE/记录关键字真分支行号/INTKEYFALSE/记录关键字假分支行号/4112插装插装点的选择必须要以紧凑精干，收集的信息全面而无冗余为前提。论文主要针对结构化程序进行研究，程序中有三种结构顺序、循环和选择，这三种结构还可以嵌套使用。根据Z路径覆盖准则，循环结构可以认为其执行1次或0次，从而转化为选择结构。因此，设计的插装位置有以下三种情况1函数的起始点；2控制逻辑关键字；3函数的结束点。选择函数的起始点和结束点作为插装点是考虑两个因素1通过该两点可以唯一的标识一个函数；2通过该两点可以标识函数的当前状态。例如，图41所示的插装点选择，在分析动态路径时记录了函数FUNC的入口点ENTRY，但是紧跟着的不是FUNC的出口点，而是另外一个函数F1的入口点，说明该FUNC调用了函数F1，并且FUNC本身还没有结束。选择控制关键字作为插装点是为了标识出函数之间的执行顺序是基于何种函数调用关系的，循环结构只考虑循环执行一次和不执行两种情况。例如，在图41动态路径里记录了函数FUNC的入口点ENT