一种基于遗传算法的多缺陷定位方法-王赞.pdf

《一种基于遗传算法的多缺陷定位方法-王赞.pdf》由会员分享，可在线阅读，更多相关《一种基于遗传算法的多缺陷定位方法-王赞.pdf（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、软件学报ISSN 10009825。CODEN RUXUEWJournal ofSoftware，2016，27(4)：879900【doi：10133280cnkijos004970】中国科学院软件研究所版权所有一种基于遗传算法的多缺陷定位方法王赞1，樊向宇1，邹雨果1,3，陈翔21(天津大学软件学院软件工程系，天津300072)2(南通大学计算机科学与技术学院，江苏南通226019)3(厦门航空有限公司信息部，福建厦门 361006)通信作者：樊向宇，Email：fxytjueducnEmail：josiscasaccnhttp：wwwjosorgcnTel：+861062562563摘要

2、： 基于程序频谱的缺陷定位方法可以有效地辅助开发人员定位软件内部缺陷，但大部分已有自动化方法在解决多缺陷定位问题时表现不佳，部分效果尚-q-的方法因复杂度较高或需要开发人员较多交互而仍需进一步改善为改善上述问题，提出一种基于遗传算法的多缺陷定位方法GAMFal，具体来说：首先基于搜索的软件工程思想对多缺陷定位问题进行建模。构建了候选缺陷分布的染色体编码方式，并基于扩展的Ochiai系数计算个体的适应度值；随后使用遗传算法在解空间中搜索具有最高适应度值的候选缺陷分布，在终止条件被满足后返回最优解种群；最后根据这个种群对程序实体进行排序这样开发人员可以依次对程序实体进行检查并最终确定多个缺陷的具体

3、位置实证研究以Siemens套件中的7个程序和Linux的3个程序(gzip、grep和sed)作为评测对象，并扩展传统的定位方法评测标准EXAM至EXAMF和EXAML。通过与其他经典的缺陷定位方法(Tarantula、Improved Tarantula及Ochiai)进行对比，并通过Friedman检测和最小显著性差异测试可得，提出的GAMFal方法在整体定位效率方面优于传统方法，且需要更少的人工交互除此之外，GAMFal的执行时间也在可接受的范围之内关键词： 缺陷定位；多缺陷；基于搜索的软件工程；遗传算-法r；EXAM评价标准中图法分类号：TP3ll中文引用格式：王赞，樊向宇，邹雨果，

4、陈翔一种基于遗传算法的多缺陷定位方法软件学报，2016,27(4)：879-900http：llwwwjOSorgcn1000-98254970htm英文引用格式：Wang Z，Fan XY，Zou YG，Chert xGenetic algorithm based multiple faults localization techniqueRuan JianXue BaoJournal ofSoftware，2016，27(4)：879-900(in Chinese)http：llwwwjosorgcn，l0-9825，4970himGenetic Algorithm Based Multi

5、ple Faults Localization TechniqueWANG Zanl，FAN XiangYul，ZOU YuGu01，一，CHEN Xian92(Department ofSoftware Engineering，School ofComputer SoRware，Tianjin University，Tianjin 300072，China)2(School ofComputer Science and Technology，Nantong University，Nantong 226019，China)3(Department ofInformation，Xiamen Ai

6、rlines，Xiamen 361006，China)Abstract： SpectrumBased fault localization techniques are attractive for their effectiveness，and prewous works have demonstrated thatthey can assist programmers tO locate faults automaticallyHowever,most of them can only work better when there is single bug thanmultiple bu

7、gsOther approaches，although partially successful on multiple faults problem，are complex and need more human interventionTo beaer address these problems，this paper proposes a new spectrum-based fault localization technique based on genetic algorithm，called GAMFal，which Can locate multiple bugs effect

8、ively、ith less human interventionFirst，the multiple bugslocalization isconverted into a search based model and a candidate expression for multiple bugslocation is encoded aS all individual binary stringThen，基金项目：国家自然科学基金(61202030，61373012，61202006)Foundation item：National Natural Science Foundation

9、ofChina(61202030，61373012，61202006)收稿时间：2015-08-31；修改时间：20151015；采用时间：2015-11-20；jOS在线出版时间：20160113CNKI网络优先出版：2016-0l14 13：16：12http：wwwenkinetkcmsdetail112560TP201601141316009html万方数据Journal of Software软件学报V0127，No4，April 2016the new approach extends the Ochiai coefficient to calculate the suspicio

10、usness value used by genetic algorithm as a fitness function tosearch for a best populmion composed by optimal fault location candidates with highest suspiciousness value，and conveys the ranking listof candidates to a checking order of program entitiesAccording to this order，programmers finally exam

11、ine program entities to locatefaultsAn empirical study on Siemens suites and three Linux programs(gzip，grep and sed)is conducted to compare GAMFal with otherspectrum-based approachesThe Friedman test and Least Significance Difference method are then carried out to investigate the statisticalsignific

12、ance、of any differences observed in the experimentsThe result suggests that the proposed method outperforms other relatedtechniques in some respects and is feasible with respect to running timeKey words：fault localization；multiple faults；search-based software engineering；genetic algorithm；EXAM软件缺陷定位

13、(software fault localization)技术是在执行测试用例集后发现有部分测试用例执行失败时，确定缺陷所在具体位置的一种分析方法在传统的软件开发过程中，通常是由开发人员手工调试、找到缺陷并进行修复但这种传统的缺陷定位方法成本较高【l】为了提高调试效率，把开发人员从枯燥的手工调试中解放出来，研究人员提出了大量的自动化缺陷定位方法用以辅助开发人员快速准确地定位缺陷已有的自动化缺陷定位方法可以简单地分为两类：静态定位方法和动态定位方法其中静态定位方法【2】在程序运行前通过分析代码结构来定位缺陷，而动态定位方法【3-5】则通过分析测试用例的执行轨迹和运行结果来定位缺陷在动态定位方法中

14、，基于程序频谱的缺陷定位(program spectrum based fault localization，简称SFL)技术表现出很好的定位效果15J它们通过计算出每个程序实体(可设置为语句、语句块或函数等)内含有缺陷的可能性，然后生成缺陷分析报告并以此来辅助开发人员进行调试，直至找到真正缺陷位置并完成修复SFL是当前软件缺陷定位问题的研究热点，也是本文研究的问题程序频谱是执行测试用例时收集到的程序执行信息，包括测试用例的程序实体覆盖信息和执行结果在大量SFL方法中，Tarantula【3】、Jaccard【6】、OchiaitTl和oo隅】等方法取得了较好的效果它们使用统计学方法计算出程序

15、实体的可疑值，并依次排序但这类方法在定位单缺陷时的效果要优于定位多缺陷时的效果141然而在实际软件开发过程中，被测程序内部含有的缺陷数难以预先获知，并且在绝大多数情况下都多于1个目前研究人员对多缺陷定位问题进行了初步研究Jones等人【4】基于测试用例执行结果将被测程序划分为几个不同部分，随后指派不同的开发人员分别去定位相关部分内的缺陷这种方法需要多个开发人员来检查代码，因此需要较高的人力成本Abreu等人提出BARlNEL方法【9】，这种方法使用贝叶斯模型排序代表多缺陷的候选集BARINEL方法在单缺陷定位和多缺陷定位中都具有较好的性能，但是它需要开发人员在检查代码的过程中保持实时交互，以确

16、保可以依此不断修正候选集排序Steimann和Bertschler10】尝试使用概率分布来估计内部缺陷数然而，缺陷的概率分布难以预知，并且很难进行估计和验证MUSE方法】不断地对程序语句执行变异操作，试图得到所有测试用例都能通过的新版本来定位到缺陷该方法的效果很好，但是需要耗费大量时间，难以在实际中使用本文提出一种基于遗传算法的多缺陷定位方法框架GAMFal首先以基于搜索的软件工程思想对多缺陷问题进行建模，将多缺陷定位问题转化为一类搜索问题；然后以二进制染色体形式表达潜在的多缺陷候选分布，同时，基于覆盖的频谱信息及“通过失败”的执行结果拓展Ochiai方法以构建适应值函数，并以此为依据采用遗传

17、算法搜索解空间，搜索出的最优解可显性地表示多个缺陷的可能位置这样，该方法便能在较少人工参与的情况下有效地进行多缺陷定位本文的主要贡献总结如下：(1)提出基于遗传算法的多缺陷定位方法GAMFal具体来说，将多缺陷定位问题建模为一类搜索问题，拓展传统的Ochiai系数，使其能够适应于多缺陷定位问题；随后以此为适应度值函数，基于遗传算法寻找最优候选集，并在此基础上对程序实体进行可疑值排序(2)基于现有缺陷定位方法评价标准匠物朋的两个扩展标准匠识朋f和匠搬则分别表示找到第1个缺陷和找到最后一个缺陷需要检查的程序实体占总程序实体的百分比)，实验对比本文方法和其他3种方法(Tarantula、Improv

18、ed Tarantula和Ochiai)的性能，证明本文方法在多缺陷定位时具有一定的优势本文第1节介绍研究背景，并通过一个简单实例，引出研究动机第2节描述我们提出的方法框架GAMFal第3节为实证研究，描述实验设计、采用的评测数据集、GAMFal方法在Siemens套件的7个程序和Linux的3个程序上的缺陷定位效果及与其他3种缺陷定位方法的比较实验，并讨论实验结果以及有效性影响因素第4万方数据王赞等：一种基于遗传算法的多缺陷定位方法节总结全文并指出值得关注的下一步研究工作l研究背景和相关工作88111基于频谱的软件缺陷定位本节首先对SFL问题进行描述，随后给出一个具体实例进行说明定义1(测试

19、用例集)T=tl,t：，tm)表示被测程序的配套测试用例集，其中，f表示该测试用例集的第f个测试用例定义2(待测程序实体集)E=ea,e2，表示被测程序内包含的程序实体集，其中，er表示第f个程序实体程序实体粒度可设置为语句、语句块或函数等定义3(覆盖矩阵)仁(瞄)用来表示T和E之间的覆盖关系M是一个mxn的矩阵，其中第i行表示第i个测试用例的程序实体覆盖情况，第J列表示第J个程序实体被不同测试用例覆盖的情况每一个代表第i个测试用例对第，个程序实体的覆盖情况，当M=1时，表示测试用例f覆盖程序实体当尬=0时，表示测试用例i未覆盖程序实体，定义4(失败测试用例覆盖矩阵)磊=(M，)是覆盖矩阵M的

20、一部分，只包含失败测试用例的覆盖信息定义5(通过测试用例覆盖矩阵)朋声(釉是覆盖矩阵M的另一部分，只包含通过测试用例的覆盖信息定义6(执行结果向量)R=r。,r2，代表测试用例集中的测试用例的测试结果，n表示第i个测试用例的执行结果，lf埘当r尸O时，表示第i个测试用例执行通过当n=1时，表示第i个测试用例执行失败定义7(程序实体统计量)程序频谱构造方式仅需简单统计测试用例的程序实体覆盖信息当程序实体为语句、语句块或函数时，基于各个测试用例的程序频谱和执行结果，可由程序实体统计量表示程序实体统计量定义为口，(P)=心=P A，；=qP，qo，1|；口l，o(口)和al,l(o分别表示“覆盖程序

21、实体P”的通过测试用例数和失败测试用例数，ao,o(P)和ao,i(P)分别表示“未覆盖程序实体矿的通过测试用例数和失败测试用例数Tarantula可疑度系数【3ISr和Ochiai可疑度系数【71品的计算公式依次定义如下：鱼!f尘ST(班_糟等型r (1)ql(P)+a01(P) alo(D+aoo(e)S P)：1 鱼!堡! (2)o(7 (口l。(P)+口o。(e)(q。(D+q。(D) 。Jones等人3】还提出引入了置信度的改进Tarantula方法，用来辅助Tarantula方法排序，其定义如下： She)-趴小叫羔，揣(3)下面通过图l所示的函数findSecond来说明这类方法

22、的工作方式，并对比GAMFal方法与已有方法的差异，讨论GAMFal方法的可行性findSecond函数的输入是4个整数，输出是这些整数中的第二大整数在图l给出的版本中，第14行和第17行程序都有错误，即在第14行中代码temp=b应为temp=min，在第17行中代码temp=b应为temp=c目前已有的可疑度值计算公式一般基于陈翔等人总结的8个假设【12】，该文是对虞凯等人工作的进一步完善【13】，其中一个假设是程序实体的怀疑度值与该程序实体被失败测试用例覆盖的次数成正比如果程序中只有一个缺陷，那么这个假设是可以被接受的，但是如果程序中含有两个或两个以上的缺陷，则存在如下问题：(1)被失败

23、测试用例覆盖最多的一般不是这两个缺陷所在的代码行，而是这些失败测试用例共同覆盖的那部分程序实体，这样得到的怀疑度值排序结果显然是不够准确的；(2)单缺陷定位方法会在很大程度上忽略缺陷间的干扰以及相互作用情况【14】万方数据882 Journal矽Software软件学报V0127，No4，April 2016函数findSecond1 intfindSecon以int a，int b，int c，int曲2 int max，min，temp；3 if(口max)11 temp=max；12 max=c；13 else if(ctemp)20 return吐21 else if(dmax)22

24、return max：23 1 else f24 return temp；25 126 Fig1 FunetionfindSecond with multiple faults图1含有多个缺陷的函数findSecond根据图1的被测程序及表1中测试用例的覆盖情况和执行结果可以看出，现有的3种方法中只有Tarantula可以快速找到第1个缺陷在3种方法计算出的可疑值中，排名第2的程序实体都是失败测试用例共同经过的第24行，但第24行并没有缺陷同时，没有缺陷的第4行、第5行也因被较多的失败测试用例覆盖而排名较为靠前而运用本文提出的GAMFal方法搜索出的3个最优解分别为(13)、(14，17)组合

25、以及(15，17)组合，根据这3个最优解可首先定位到第17行包含的缺陷，然后至多在第4次就可以定位到第14行包含的缺陷：如果采取一次定位多缺陷方法，则至多在第3次就可以同时得到两个缺陷的位置，这将有效提高多缺陷定位的准确性，也在一定程度上减少了人工参与基于上述观察我们认为，GAMFal方法在保证单缺陷定位效果的基础上，能够有效地解决多缺陷定位问题，因此更加符合实际开发中对缺陷定位的需求Table 1 Coverage matrix and sorted result of functionfindsecond表1 函数findSecond的缺陷覆盖矩阵及排序结果万方数据王赞等：一种基于遗传算法

26、的多缺陷定位方法 88312基于搜索的软件工程和遗传算法Harman和Jones在2001年首次提出基于搜索的软件工程(search based software engineering，简称SBSE)概念该领域尝试采用元启发式搜索技术，以合理的计算开销求解一类可转化为组合优化问题的软件工程问题15】2012年Harman等人总结了该领域10多年来的发展并提出新的趋势、技术和应用【l 61李征等人也在“20132014年度中国计算机科学年度报告”中对“基于搜索的软件工程”进行了全面的综述【17】随着计算能力的增强。越来越多的启发式搜索方法被应用到软件工程中来，为软件工程问题的求解提供了一个新的

27、思路经过10几年的发展，基于搜索的软件工程研究取得了显著的成绩，已成为软件工程研究领域内的一个活跃方向，且在软件测试领域有很好的应用，经统计，有超过50的论文关注的是软件测试与挑错方向【17】基于搜索的软件工程广泛应用于软件测试领域，成功地解决了功能测试【18】、执行时间测试【l 91、集成测试【20】、压力测试【2l】、变异测试【22】、组合测试f23】、回归测试【24】等各种测试的问题其中，测试数据的生成应用最为广泛，McMinn25】和Ali26】等人曾对基于搜索的测试数据生成技术进行了总结基于搜索的软件工程在软件缺陷定位和缺陷自动修复领域也有很多应用研究者根据缺陷自动修复中的量变和质变

28、现象，利用面向自动修复的缺陷定位，提高了定位的准确度27,28研究者还通过构造面向缺陷定位的轻量级近似动态后向切片算法，提出程序逻辑与统计相结合的软件缺陷定位方法SSFL，提高了定位准确度29,301软件缺陷定位研究是当前软件工程研究领域中的一个活跃分支，本文将多缺陷定位问题建模为组合优化问题，并尝试用遗传算法这一主流的元启发式搜索技术进行求解接下来我们对遗传算法的相关知识进行简介遗传算法是一种模拟自然选择进化过程(即适者生存)的搜索算法【311，其使用选择算子、交叉算子以及变异算子等对原始种群进行进化和筛选，经过数轮迭代得到可能的最优解遗传算法最初由美国密歇根大学Holland教授于1975

29、年提出【3矾，解决了优化模型中的两个重要问题：优化的方向和新的更优解生成方法下面依次给出遗传算法的相关定义p1。定义8(染色体编码)染色体编码是把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法在遗传算法中，Holland建议采取二进制串的编码方式定义9(适应度值函数)适应度值用于评价个体的优劣程度，一般来说，适应度值越大，则个体越好；反之，适应度越小，则个体越差针对具体问题可以选择与问题相适宜的适应度值函数，作为个体评价的标准定义10(遗传操作算子)遗传算法的操作算子包括选择、交叉和变异3种基本形式，构成了遗传算法高效搜索能力的基础，是模拟自然选择和遗传过程中发生的繁殖、

30、杂交和突变现象的主要载体【311选择操作体现适者生存的原理，通过适应度值选择优质个体而抛弃劣质个体；交叉操作通过交换个体之间的遗传信息从而产生新的个体；变异算子通过对部分基因位信息的突变而得到尚未被开发的遗传信息，以防止个体在形成最优解过程中过早收敛遗传算法的流程大致描述为：首先初始化一个指定规模的种群，种群中每个染色体随机生成；然后，算法将根据每个个体的适应度值采取选择、交叉、变异等算子对种群进行演化迭代，直至满足特定终止条件(终止条件通常为达到指定迭代次数或最优适应度值变化低于某个阈值)，并返回迄今为止已找到的最优解算法的关键是染色体的编码方式、适应度值函数的设定以及选择、交叉、变异等遗传

31、操作算子的设定13缺陷定位其他研究成果SFL方法是一种动态的缺陷定位技术，它利用大量测试用例的执行结果和程序的覆盖信息，通过统计学的方法得到代码可疑值的排序研究者们提出很多不同的统计学公式【3-7】来计算代码的可疑值排序，这些公式在不同的评测程序上各有优劣，研究者们在此基础上不断进行优化研究有研究人员利用谓词将程序划分成块，通过统计谓词在成功测试用例和失败测试用例中的执行情况来进行缺陷定位Liblit等人【33】提出CBI方法来寻找与程序缺陷最相关的谓词，通过谓词在成功测试用例和失败测试用例执行过程中的取值信息计算谓词的可疑值随后，Liu等人【34】提出了SOBER方法，该方法通过搜集谓词的执

32、万方数据884 Journal of Software软件学报V0127，No4，April 2016行次数，比较谓词执行结果在成功测试用例和失败测试用例上的分布情况计算谓词的可疑值并且实验结果表明，SOBER方法要优于Liblit方法郑征等人提出一种基于谓词执行序列的缺陷定位方法【351，通过搜集更多的谓词执行信息能够进一步优化缺陷定位的效果随后，他们又对此方法进行补充，提出一种自适应的缺陷定位方法【3 61，该方法能够动态地选择每个谓词需要搜集的信息强度近年来，不断有新的方法被引入该研究领域，尤其是机器学习和基于搜索的方法3 71Yoo提出一种通过遗传算法自动生成SBFL公式的方法，并可得

33、到与人工设计公式相近的定位效果【3引谢晓园等人使用基于搜索的方法从30个不同怀疑率计算公式中，发现了4个最优的公式【391玄跻峰等人使用机器学习的方法将多个排序指标结合使用，根据不同的程序选择最优公式【401研究者还从测试用例维护和程序分析角度进一步提高缺陷定位效果，充分考虑测试用例及程序本身的特性对缺陷定位结果的影响，并以此优化缺陷定位效果郝丹等人从测试用例出发，通过消除相似测试用例【41】和有害测试用例【42l来优化测试用例集，从而优化缺陷定位的结果贺韬等人使用变异分析来降低偶然因素的影响，并以此提高缺陷定位的效果【431Masri通过分析程序中的信息流来辅助缺陷定位，在分析过程中考虑程序

34、间的依赖关系【4 41张震宇等人加入布尔表达式求值中的短路现象处理来提高缺陷定位效果45,46此外，概率图模型【4H9】和程序切片技术【50,51也被引入到程序缺陷定位技术多缺陷定位问题是缺陷定位技术实际应用必须要解决的问题Jones等人通过分析提出缺陷定位效果与缺陷数量成反比关系，缺陷数量越多，缺陷定位方法得到的效果越差【31而DiGiuseppe等人通过大量实验发现，缺陷数量对缺陷定位效果的影响可以忽略不计，他们同时也对缺陷间的干扰现象进行了深入研究，并将失败测试用例聚类，使得同一类中的测试用例只与一个缺陷相关【l舢Abreu等人提出一种基于贝叶斯的多缺陷定位方法，它能预测程序实体中包含缺

35、陷的概率【521文万志等人提出一种基于切片技术的多缺陷定位方法，该方法通过程序切片降低了不同缺陷之间的相互影响【5312 GAMFal方法框架我们提出的GAMFal方法包括两个阶段：基于遗传算法进行最优多缺陷候选分布种群的搜索阶段和根据最优种群进行多缺陷定位阶段其中遗传算法搜索最优种群阶段的任务是对问题进行建模并通过遗传算法搜索出最优种群，这一阶段需要重点研究染色体编码方式和适应度值函数的设定、初始种群的生成方式、遗传算子的设计及执行终止条件的定义等，最终生成最优解种群；多缺陷定位阶段的任务是将第1阶段所得最优种群中的候选解映射到程序实体的真实位置，从而辅助开发人员完成多缺陷的定位21基本思想

36、和整体流程传统的SFL算法主要是基于每个程序实体被通过或失败测试用例数的覆盖情况来计算出其含有缺陷的可疑值GAMFal算法的思想则是先假设某些程序实体有错，然后根据测试用例集的运行结果来评价这些假设并通过遗传算法进行迭代进化，最终得到最优种群，并以此为依据进行多缺陷定位GAMFal方法首先构建一个长度为程序实体(代码行、代码块)总数的二进制向量，该向量表示可能的缺陷位置分布，其中，1表示该位置所对应的程序实体有错，0表示该位置所对应的程序实体无错；这种情况下所有可能的解有2”个，我们可以依据所有测试用例对每一个解进行评价，缺陷定位的目标就是去寻找最优解，以得到最可能的缺陷位置这便将传统的软件缺

37、陷定位问题转化为一类搜索问题，可用常见的搜索方法来求解，但在求解之前需要解决如下3个问题(1)如何评价一个候选解和最优解(真实多缺陷位置)的接近程度，即适应度值函数的设置问题(2)在给定适应度值函数的情况下如何搜索以得到最优解(3)如何根据最优解再去映射返回得到缺陷程序实体最可能的位置对于第1个问题，本文基于程序频谱信息和运行结果对Ochiai方法进行拓展以适应多缺陷情况，同时考虑到表1例子中存在的问题，对由通过测试用例经过的可能缺陷位置进行惩罚，我们提出了MultiOchiai系数，并以此作为候选缺陷分布的评价函数对于第2个问题，由于整体解空间的大小为2”，当程序实体数玎较大时，解空间规模将

38、较为庞大，借助穷举法找到最优解的方案并不可行，因此我们需要采用更好的搜索算法来求解遗传算万方数据王赞等：一种基于遗传算法的多缺陷定位方法 885法是一种模拟生物进化的启发式搜索算法，它能得到一系列的最优候选解，而其他的启发式搜索算法，如爬山算法、模拟退火算法等容易收敛于一个局部最优解，因为本问题中可能存在多个最优解，所以我们选择遗传算法进行搜索对于第3个问题，考虑到遗传算法是一种基于种群迭代的算法，在算法达到终止条件时将会得到一个最优种群。考虑到算法的稳定性，本文将针对得到的最优解种群确定多缺陷最终可能的位置GAMFal算法的核心是MultiOchiai可疑度系数计算公式和遗传操作算子的选择，

39、图2给出了整个算法的流程图，算法共分为两个阶段，第1阶段首先使用贪心算法对多缺陷分布的种群进行初始化；然后执行选择、交叉和变异算子，生成新的个体并添加到种群中，同时以MultiOchiai可疑度系数作为适应度值对个体进行评价并进化得到新种群；如果终止条件被满足，则将得到最终的最优多缺陷分布种群然后进入第2阶段，依据最优种群中的多缺陷分布得到对应的程序实体的可疑度排序，算法结束最终的l匝一爹_叫缺陷分布lI组金扯薤l陌瞻裔砑目酃厂筛选圈I实体排序1篙J真实位置I”窗鲕t圈通 L一厂萧Fig2 Flow chart of GAMFal algorithm图2 GAMFal算法的流程图22遗传算法搜

40、索最优种群阶段本节主要介绍GAMFal方法的第1阶段计算过程，首先介绍对候选缺陷分布的编码方式，然后给出具体的适应度值函数，最后描述遗传操作算子并介绍搜索的整体流程具体如下221染色体编码方式GAMFal算法将候选缺陷分布【54】表示为一个二进制向量：C=Cl，C2，c3，q (4)其中，一为被测程序中可执行的程序实体数量，c，表示被测程序中的第，个程序实体是否有错，如果c，=1，则在该候选缺陷分布中，第，个程序实体被认为是存在缺陷的；如果c=0，则在该候选缺陷分布中，第，个程序实体被认为没有缺陷例如一个候选缺陷分布C毛0，0，1，0，0，0，0，0，1，O，表示被测程序共有9条可执行的程序实

41、体，其中第3个和第8个程序实体被认为是有缺陷的，其余的则被认为是没有缺陷的222适应度值函数Tarantula和Ochiai等可疑度系数计算公式通过计算测试用例的频谱信息和执行结果得到可疑度系数，进而得出每一个程序实体的可疑度值然后根据程序实体的可疑度值从大Nd,进行排序，可以得到可疑度排名列表，开发人员便可以根据该列表依次检查程序，从而发现缺陷在程序中的具体位置Tarantula及Ochiai等可疑度系数计算公式所度量的是每一条语句的可疑度值，此类方法在单缺陷的情况下表现出了很好的效果但在实际的软件调试过程中，被测程序往往含有多个缺陷Tarantula和Ochiai所得出的可疑度排名列表在存

42、在多缺陷的情况下能够作为参考，但是因为并没有根据多缺陷情况进行优化，因此会存在潜在的问题pJ文献【3】提出的MultiOchiai可疑度系数计算公式便是针对这一问题在Ochiai可疑度系数计算公式上所作的改进当程序中存在多个缺陷时，与单缺陷程序的假设f12】会有较大的差别，因此本文的方法基于如下假设假设1一个缺陷分布的可疑度与该分布能解释的失败用例数成正比万方数据886 Journal of Software软件学报V0127，No4，ArIril 2016假设2一个缺陷分布的可疑度与该分布能解释的通过用例数成反比假设3在设定的可疑度公式中，假设1所占的比重要更大一些MultiOchiai可疑

43、度系数计算公式度量候选缺陷分布的可疑度值对于一个候选缺陷分布C其可疑度值(即该候选缺陷分布为真实缺陷分布的概率)可由如下公式计算出来MultiOchiai(C)：1 丝2 i (5)I耳x(c)+P(c)I其中，吠c)为候选缺陷分布C解释失败测试用例的能力，其定义为妒(c)=M嘶胯矧珏f五l嘲。eJ (6)公式(6)中的函数爿O)被称为示性函数，定义为A(工)=：，iiff(zx：。0) (7)公式(5)中的P(C)定义为P(c)=鸩嘶J闼昂Il。，Jlq坞) (8)公式(6)和公式(8)中的为定义3中覆盖矩阵的元素，l昂I为失败测试用例的数量与假设1对应，公式(5)和公式(6)qb的烈C)表

44、达了候选缺陷分布C解释”失败测试用例的能力；即如果一个失败测试用例运行了一个或者多个在c中被假定为有错的语句，则该失败测试用例能够被C解释反之，如果该失败测试用例运行到的语句在C中都被认为是无错的，则该失败测试用例不能被C解释如公式(6)所示，砍。的值为候选缺陷分布C能够解释的失败测试用例的数量；砍C)的值加l，当且仅当C能够解释一个失败的测试用例公式(8)中的I昂I是通过测试用例的数量尸(o是一个惩罚函数，与假设2相对应，如果一个候选缺陷分布c所假设为有错的程序实体被通过的测试用例执行到，则P(C)的值加1需要说明的是，如果C能解释一个失败的测试用例，则烈。的值加1；而P(c)中并未引入示性

45、函数，则只要c中有错的语句被通过的测试用例执行一次，则P(o的值为1这样做的目的是让候选缺陷分布C中被认为有错的语句数量保持在一个比较低的水平，这与实际调试时程序的缺陷数量一致如果一个候选缺陷分布C中被认为有错的语句数量较多，则其P(C)值会更大，从而降低了该候选缺陷分布的可疑度值反之，如果不进行惩罚，则可能出现极端情况，即包含缺陷实体数量最多的候选分布的MultiOchiai可疑度值最高，这样的结论将推出所有程序实体都是有缺陷的，显然无法有效地辅助开发人员定位缺陷因此，GAMFal方法使用惩罚函数以降低那些过多估计缺陷数量候选分布的适应度值，这样既可以进一步优化GAMFal算法的执行结果，又

46、能在一定程度上提高算法的执行效率在GAMFal方法中，对于一个给定的缺陷分布，其MultiOchiai可疑度值越高，则表示该分布解释失败测试用例的能力越强，解释正确测试用例的能力越弱223遗传操作算子及最优种群搜索过程如上节所述，MultiOchiai可疑度系数计算公式可计算出每一个候选缺陷分布的可疑度值本节所述方法就是对候选缺陷分布进行搜索，找出其中可疑度值较大的种群，最终得到程序实体的可疑度排名列表由于候选解的空间较大且无法用解析的方法求解该问题，本文将采用遗传算法来对该问题进行求解遗传算法由可行候选解集的一个初始种群开始，种群由经过基因编码的一定数目个体组成，而每个个体是染色体带有一定特

47、征的实体通常采用简化的编码方法，即二进制编码对原始问题中的表现型进行编码，使之成为基因型的个体初始种群产生后，按照适者生存和优胜劣汰的原理，逐代地演化以产生新的个体，并保留更好的个体进入下一代在每一代中，根据个体的适应度值来选择个体，进行交叉和变异，从而产生新的个体这一过程迭代进行，直到达到终止条件，终止条件一般为预设的迭代次数，或者是种群中的个体的适应度达到一个预设的值等等最终代种群中的最优个体经过解码，作为问题的近似最优解在GAMFal算法中，使用长度为irl的二进制向量C来表示一个候选缺陷分布，n为被测程序的可执行语句数量二进制向量c即可作为遗传算法中的一个个体而MultiOchiai可

48、疑度系数计算公式即作为遗传算法中的万方数据王赞等：一种基于遗传算法的多缺陷定位方法 887适应度函数，即MultiOchiai值可作为在遗传算法中度量候选缺陷分布c的标准GAMFal方法中使用遗传算法搜索高可疑度值候选缺陷分布，表2是GAMFal算法的伪代码Table 2 Pseudo code of GAMFal algorithm表2 GAMFal算法伪代码算法GAMFal覆盖矩阵M结果向量R；近似最优解种群Ppop,-AG(M,R，)CandidatePool-popf+一ORepeati*-i+lG。lec。ed一-select(pop,s。00p)，GGAP)Ccmssovere一-crossover(C selected-PaCmd囝for all CCc删redif sum(oThresholdmmutatet(C，Pml)12 else1 3 mutate2(C，P。2)i4 endif15 cm吡口0Cmtale女JC16 endfor1 7