基于遗传算法的函数级别软件错误定位

针对软件开发过程中的错误定位问题,提出一种以函数调用路径和遗传算法为基础的软件错误定位方法FGAFL。将软件测试中的错误定位问题转化为组合优化问题,结合函数调用路径对错误定位的影响构建适应度函数。通过遗传算法在候选种群中迭代搜索具有较高可疑度的候选错误分布,得到最优解。根据最优解对程序中的函数按可疑度进行排序,依次检查函数并定位错误的具体位置。实验表明,FGAFL方法可以有效降低运算量并缩减代码审查的范围,提高错误定位的精度和效率。     

一种基于频谱信息并结合碰集和遗传算法的缺陷定位方法

在软件研制过程中,缺陷定位是一个重要的研究课题。但是,实际软件中的缺陷数量无法被预先判定,且已有的单缺陷定位方法不易使用,已有的多缺陷定位方法存在定位效率不高的问题。基于此,文中对多缺陷定位方法GAMFL进行了研究和改进,提出了基于频谱信息并结合碰集和遗传算法的缺陷定位方法GAHIT。该方法定义了定位基本块,并用其替代语句进行缺陷定位,缩小了搜索范围;在初始种群的构造过程中,提出了采用求解失败用例执行路径碰集的方法,优化了初始种群的生成,并给出了新的适应度函数的计算方法,提高了算法的整体执行效率;最后针对遗传算法的结果,给出了缺陷检查策略,提高了在最优种群中查找缺陷的准确性。实验结果表明,所提方法能够有效处理缺陷数量未知情况下的定位问题,在单缺陷和多缺陷程序中都有较好的定位效果。     

基于影响分析的回归测试优先级错误定位方法

基于程序行为特征的错误定位方法由于只孤立地看待每个程序实体,使其错误定位的效率受到影响,而回归测试错误定位又由于需要执行全部测试用例将大大增加开发和测试成本。针对以上问题,提出一种基于影响分析的回归测试优先级错误定位方法,该方法将联合依赖图、基于程序行为特征的错误定位方法和回归测试优先级进行有机结合。实验结果表明,与Ochiai,Tarantula,PPDG,CP和Naish等经典方法相比,该方法可更加有效地定位软件错误。     

基于蚁群遗传算法的高校排课系统

传统的手工排课的方法在效率和合理度上存在较大的缺陷.而利用单纯的遗传算法和蚁群算法则存在着计算时间过长和易导致早熟收敛等缺点.为了解决问题,将蚁群算法与遗传算法相结合,结果发现使用蚁群遗传算法,可以有效地减少搜索空间,使种群在遗传过程按规则分区,在区间中喷洒信息素,染色适应度与种群区间交互,形成正反馈系统,驱动整个算法得到排课较优解.测试结果表明.蚁群遗传算法较大提高了高校排课系统中的效率和合理度.     

基于多精英协同进化遗传算法的云资源调度

传统的遗传算法(GA)在解决云资源调度问题时会随着问题规模的增大而出现早熟收敛、搜索效率低下、寻优能力差等现象.为了克服这些缺陷,提出一种基于多精英协同进化的遗传算法(MECGA).该算法通过多精英保留技术将适应度值大的个体选入精英子种群,通过与普通子种群进行协同交叉操作,可引导整个种群向最优解的方向移动;通过定义个体评价策略,将差异度高的个体也选入到精英子种群,这些个体又能够保证种群的多样性,使种群更容易跳出局部最优解.实验结果表明,ME C GA相较其他GA具有求解效率高、收敛速度快和寻优能力强等特点.     

基于程序频谱的动态缺陷定位方法研究

基于程序频谱的动态缺陷定位是软件自动化调试研究中的一个热点问题,通过搜集测试用例的程序频谱和执行结果,基于特定模型以定位缺陷语句在被测程序内的可能位置.对近些年来国内外学者在该研究领域取得的成果进行系统总结:首先,给出预备知识和基本假设;随后,提出缺陷定位研究框架并识别出框架内一系列可影响缺陷定位效果的内在影响因素,包括程序频谱构造方式、测试套件构成和维护、内在缺陷数量、测试用例预言设置、用户反馈和缺陷修复开销等;接着,对实证研究中采用的评测指标和评测程序进行总结和分析;然后,对缺陷定位方法在一些特定测试领域中的应用进行总结;最后,对该领域未来值得关注的研究方向进行了展望.     

基于概率模型检测的软件缺陷定位方法

软件缺陷的存在导致软件无法满足用户的需求,如何高效高质量地定位缺陷是消除软件缺陷的关键.基于模型的缺陷定位技术是当前的研究热点,可以用于检测软件系统故障找到软件失效的原因.现有基于模型的缺陷定位技术中,未考虑非相邻节点间传递依赖和测试用例对可疑度的影响,导致缺陷定位精度和效率低.提出了基于概率模型检测的软件缺陷定位方法(probabilistic model checking method for software fault location,PMC-SFL),首先提出一种程序概率模型用于提高模型的推理能力;然后设计了基于执行路径构建程序概率模型的学习算法;最后设计了基于概率模型检测的软件缺陷定位算法,用于缺陷定位分析.通过在公共数据集Siemens上进行实验和分析,表明了PMC-SFL方法与五种现有的缺陷定位方法RankCP、BNPDG、Tarantula、SOBER和CT相比,具有更高的软件缺陷定位精度和效率.     

基于信息检索的软件缺陷定位方法综述

基于信息检索的软件缺陷定位方法是当前软件缺陷定位领域中的一个研究热点.该方法主要分析缺陷报告文本和程序模块代码,通过计算缺陷报告和程序模块间的相似度,选取与缺陷报告相似度最高的若干程序模块,将其推荐给开发人员.本文对近些年国内外研究人员在该综述主题上取得的成果进行了系统的梳理和总结.首先,给出研究框架并阐述影响方法性能的三个重要因素：数据源、检索模型和场景应用;其次,依次对这三个影响因素的已有研究成果进行总结;然后,总结基于信息检索的软件缺陷定位研究中常用的性能评测指标和评测数据集;最后总结全文并对未来值得关注的研究方向进行展望.     

面向旅行商问题的一种改进遗传算法

针对传统遗传算法解决组合优化领域的典型难题--旅行商问题时存在的缺陷与不足,对传统遗传算法加以改进.引入了种群熵和基因座多样性来测度种群的多样性,并利用求得的测度值修改了个体的适应度,达到了预期目的.还提出启发式交叉箅子、二分局部搜索、自适应遗传参数,使该算法在提高搜索效率与解质量方面取得了综合平衡.在算法的仿真和测试中,改进后的算法明显优于传统的遗传算法.这表明,该算法具有良好的可行性和实用性.     

基于条件概率模型的缺陷定位方法

缺陷定位是软件调试的重要阶段,依赖程序频谱信息实现软件缺陷定位,是当前比较行之有效的方法.基于频谱缺陷定位方法应用的前提是,程序频谱和执行结果之间存在的潜在关联.通过经验性分析两者之间的内在关联,借助于统计学的条件概率思想,构建了用以量化分析两者关系强弱的P模型,并基于此提出了基于条件概率的缺陷定位方法.以Siemens套件中的7个程序、Space程序和3个Unix工具程序为基准评测对象,与已有的15种经典缺陷定位方法进行了对比实验.实证研究结果表明,该方法总体上具有更好的缺陷定位效果.     

一种基于层次切片谱的软件错误定位技术

传统的软件错误定位技术通常利用测试覆盖信息计算程序语句发生错误的可疑度进行软件错误定位,但是这种定位技术没有充分考虑程序本身固有的依赖信息,缺乏语句筛选,从而使错误定位的精度受限.提出了一种基于层次切片谱的错误定位技术,以提高面向对象程序中的错误定位效率.这种技术首先分析程序不同粒度层次元素(包、类、方法以及语句)之间的依赖信息,对可能发生错误的元素进行筛选,缩小错误查找范围;在此基础上,建立了层次切片谱模型,并定义了一种可疑度度量方法;最后根据该可疑度结果从大到小的顺序进行错误定位.通过实验验证了基于层次切片谱的错误定位技术的有效性,且比基于程序谱的Tarantula 技术、Union 技术、Intersection 技术效率更高.     

HSFal: Effective fault localization using hybrid spectrum of full slices and execution slices

Most of the existing fault localization approaches use execution coverage of test cases to isolate the suspicious codes that likely contain faults. Program slicing can extract the dependencies of program entities with respect to a specific criterion. Therefore this technique is expected to have a beneficial effect on fault localization. In this paper, we propose a novel approach using a hybrid spectrum of full slices and execution slices to improve the effectiveness of fault localization. In particular, our approach firstly computes full slices of failed test cases and execution slices of passed test cases respectively. Secondly it constructs the hybrid spectrum by intersecting full slices and execution slices. Finally it computes the suspiciousness of each statement in the hybrid slice spectrum and generates a fault location report with descending suspiciousness of each statement. We also implement our proposed approach in our prototype tool HSFal by Java programming language. To verify the effectiveness of our approach, we performed an empirical study by the prototype on several widely used open source programs. Our approach is compared with eight representative coverage-based and slice-based fault localization approaches. Final experimental results show that our proposed approach is more effective in fault localization than other compared approaches, and can reduce almost 2.98–31.79% of the average cost of examined code significantly.     

Evaluating the usage of fault localization in automated program repair: an empirical study

Fault localization techniques are originally proposed to assist in manual debugging by generally producing a rank list of suspicious locations.With the increasing popularity of automated program repair,the fault localization techniques have been introduced to effectively reduce the search space of automated program repair.Unlike developers who mainly focus on the rank information,current automated program repair has two strategies to use the fault localization information:suspiciousness-first algorithm(SFA)based on the suspiciousness accuracy and rank-first algorithm(RFA)relying on the rank accuracy.However,despite the fact that the two different usages are widely adopted by current automated program repair and may result in different repair results,little is known about the impacts of the two strategies on automated program repair.In this paper we empirically compare the performance of SFA and RFA in the context of automated program repair.Specifically,we implement the two strategies and six well-studied fault localization techniques into four state-of-the-art automated program repair tools,and then use these tools to perform repair experiments on 60 real-world bugs from Defects4J.Our study presents a number of interesting findings:RFA outperforms SFA in 70.02%of cases when measured by the number of candidate patches generated before a valid patch is found(NCP),while SFA performs better in parallel repair and patch diversity;the performance of SFA can be improved by increasing the suspiciousness accuracy of fault localization techniques;finally,we use SimFix that deploys SFA to successfully repair four extra Defects4J bugs which cannot be repaired by SimFix originally using RFA.These observations provide a new perspective for future research on the usage and improvement of fault localization in automated program repair.     

Effective software fault localization using predicted execution results

Software has become ubiquitous in our daily lives, and with its increasing functionality and complexity comes a frequently tedious and prolonged debugging process. Of the three activities in program debugging (failure detection, fault localization, and bug fixing), the focus of this paper is on the first, failure detection, under the condition that there is no test oracle that can be used to automatically determine the success or failure of all the executions. More precisely, the outputs for many executions have to be verified manually, or the expected outputs are not even available. We want to determine whether there is a solution to help programmers predict the execution results. How good are these predicted results when they are used to help programmers find the locations of bugs? A framework is proposed to reduce the effort on output verification using a strategy based on the Hamming distance or K-Means clustering to predict results of test executions. Such data and the statement coverage of each test case are used to compute the suspiciousness of each statement according to a fault localization technique and produce a ranking for examination to locate bugs. Case studies using 22 programs and seven fault localization techniques were conducted to evaluate the fault localization effectiveness of the proposed framework on 1203 faulty versions, some of which have a single bug and others with multiple bugs. A discussion on factors that may affect the accuracy of execution result prediction and the resulting fault localization effectiveness is also presented. Our data suggests that, in general, with respect to fault localization techniques using execution results verified against the expected outputs, those using predicted execution results can be even more effective than (by examining a smaller number of statements to locate the first faulty statement) or as good as the former (the verified).     

BPELDebugger: An effective BPEL-specific fault localization framework

ContextBusiness Process Execution Language (BPEL) is a widely recognized executable service composition language, which is significantly different from typical programming languages in both syntax and semantics, and especially shorter in program scale. How to effectively locate faults in BPEL programs is an open and challenging problem.ObjectiveIn this paper, we propose a fault localization framework for BPEL programs.MethodBased on BPEL program characteristics, we propose two fault localization guidelines to locate the integration and interaction faults in BPEL programs. Our framework formulates the BPEL fault localization problem using the popular fault localization problem settings, and synthesizes BPEL-specific fault localization techniques by reuse of existing fault localization formulas. We use two realistic BPEL programs and three existing fault localization formulas to evaluate the feasibility and effectiveness of the proposed fault localization framework and guidelines.ResultExperiment results show that faults can be located with the fewest code examining efforts. That is, the fault-relevant basic block is assigned the highest suspiciousness score by our fault localization method. The experiment results also show that with the use of the proposed fault localization guidelines, the code examining efforts to locate faults are extraordinarily reduced.ConclusionWe conclude that the proposed framework is feasible in synthesizing effective fault localization techniques, and our fault localization guidelines are very effective to enhance existing fault localization techniques in locating faults in BPEL programs.     

一种基于信息量的缺陷定位方法

缺陷定位是软件调试过程中的重要环节,它通过利用程序信息和测试信息来定位软件中的错误.借助于事件信息量,提出一种基于事件信息量的缺陷定位方法——SIQ(suspiciousness based on information quantity).SIQ方法根据测试信息中不同事件的类型及其发生的概率,结合语句的执行信息,动态计算和调整缺陷定位的结果.通过大量的实验分析和对比,SIQ方法在多个数据集上表现出了很好的稳定性,与几种现有的缺陷定位方法相比,SIQ方法的缺陷定位效果也更加准确.     

A family of code coverage-based heuristics for effective fault localization

Locating faults in a program can be very time-consuming and arduous, and therefore, there is an increased demand for automated techniques that can assist in the fault localization process. In this paper a code coverage-based method with a family of heuristics is proposed in order to prioritize suspicious code according to its likelihood of containing program bugs. Highly suspicious code (i.e., code that is more likely to contain a bug) should be examined before code that is relatively less suspicious; and in this manner programmers can identify and repair faulty code more efficiently and effectively. We also address two important issues: first, how can each additional failed test case aid in locating program faults; and second, how can each additional successful test case help in locating program faults. We propose that with respect to a piece of code, the contribution of the first failed test case that executes it in computing its likelihood of containing a bug is larger than or equal to that of the second failed test case that executes it, which in turn is larger than or equal to that of the third failed test case that executes it, and so on. This principle is also applied to the contribution provided by successful test cases that execute the piece of code. A tool, χDebug, was implemented to automate the computation of the suspiciousness of the code and the subsequent prioritization of suspicious code for locating program faults. To validate our method case studies were performed on six sets of programs: Siemens suite, Unix suite, space, grep, gzip, and make. Data collected from the studies are supportive of the above claim and also suggest Heuristics III(a), (b) and (c) of our method can effectively reduce the effort spent on fault localization.     

失效上下文统计分析的软件故障定位方法

针对程序切片方法不提供语句的可疑程度描述,而覆盖分析方法不能充分分析程序元素间的相互影响等问题,提出上下文统计分析的软件故障定位方法。首先,将源程序转换为抽象语法树和程序依赖图;接下来,插桩程序,收集运行时信息;然后,根据失效点,执行按需的反向动态切片,确定失效产生的上下文;最后,对于反向动态切片中的节点,统计计算可疑度,输出带可疑度排序的动态程序切片。该方法不但描述了失效产生的上下文,还计算上下文中各个语句的可疑度。实验结果表明,所提方法与单一的覆盖分析方法相比,平均Expense降低了1.3%,与单一的切片方法相比,平均Expense降低了5.6%,所提方法可以有效辅助开发人员定位与修正软件缺陷。     

Hierarchy-Debug: a scalable statistical technique for fault localization

Considering the fact that faults may be revealed as undesired mutual effect of program predicates on each other, a new approach for localizing latent bugs, namely Hierarchy-Debug, is presented in this paper. To analyze the vertical effect of predicates on each other and on program termination status, the predicates are fitted into a logistic lasso model. To support scalability, a hierarchical clustering algorithm is applied to cluster the predicates according to their presence in different executions. Considering each cluster as a pseudo-predicate, a distinct lasso model is built for intermediate levels of the hierarchy. Then, we apply a majority voting technique to score the predicates according to their lasso coefficients at different levels of the hierarchy. The predicates with relatively higher scores are ranked as fault relevant predicates. To provide the context of failure, faulty sub-paths are identified as sequences of fault relevant predicates. The grouping effect of Hierarchy-Debug helps programmers to detect multiple bugs. Four case studies have been designed to evaluate the proposed approach on three well-known test suites, Space, Siemens, and Bash. The evaluations show that Hierarchy-Debug produces more precise results compared with prior fault localization techniques on the subject programs.     

基于路径分析和信息熵的错误定位方法

软件错误定位是一项耗时又费力的工作,因此如何提高软件错误定位的自动化程度一直以来都是软件工程领域研究的热点.现有的基于频谱的错误定位方法很少利用程序的上下文信息,而程序的上下文信息对错误定位至关重要.针对此问题,本文提出了一种基于路径分析和信息熵的错误定位方法FLPI.该方法在基于频谱信息技术的基础上,通过对所有执行路径中的数据依赖关系进行分析来引入执行上下文信息,同时利用信息熵理论将测试事件信息引入到可疑语句的怀疑度计算公式中,以提高错误定位的精度和效率.为了评价该方法的有效性,基于一组基准程序和开源程序进行实验验证.实验结果表明,本文所提方法FLPI能够有效地提高错误定位的精度和效率.