面向MBFL的测试用例约减策略

基于变异的错误定位(MBFL)是最近提出的一种自动化程序错误定位技术, 错误定位精度高, 但伴随着庞大的执行开销, 严重制约了其在工业领域的应用. 研究人员主要从减少变异体数量、减少测试用例数量和优化变异体的执行过程三个方面优化MBFL的执行效率. 前两种方法被广泛研究并取得很好的定位效果, 但对MBFL测试用例方面的研究较少, 且存在错误定位精度损失的问题. 为解决该问题, 本文提出了一种基于信息熵的测试用例约减方法(IETCR). IETCR首先计算出测试用例的信息熵, 然后根据信息熵对测试用例进行排序, 最后选择少量有价值的测试用例执行变异体. 在SIR中 6个程序100个版本上的实验结果表明, IETCR能够约减56.3%~88.6%的MBFL执行开销, 而且几乎保持与原始MBFL相同的错误定位精度.     

面向语句的MBFL变异体约减策略

在软件调试过程中如何高效、精确地定位程序中的错误代码是软件开发人员普遍关注的问题。MBFL是一种基于变异分析的错误定位技术,它在获得较高错误定位精度的同时会生成大量变异体,并在变异体上执行测试用例集,开销庞大。为了减少MBFL的变异执行开销,提出面向语句的变异体约减策略,通过分析测试用例的执行信息, 按一定比例 对每条由失败测试用例覆盖的语句生成的变异体集合进行约减。实验结果表明,在7个程序包的112个错误版本上,应用面向语句的变异体约减策略的MBFL,在保持较高错误定位精度的同时,能够有效减少73.51%~79.98%的变异执行开销。     

基于SOM神经网络的二阶变异体约简方法

二阶变异测试通过向源程序中人工注入两个缺陷来模拟程序实际的复杂缺陷,在软件测试中具有重要意义.但由一阶变异体组合形成二阶变异体后数量会急剧增长,极大地增加了程序的执行开销.为了减少二阶变异体数量,降低程序的执行开销,提出一种基于SOM神经网络的二阶变异体约简方法.该方法首先采用较为全面的二阶变异体错误组合策略,对一阶变异体组合形成二阶变异体;然后,根据二阶变异体执行过程中的中间值相似性,进行基于SOM神经网络的变异体聚类.使用经典的基准程序和开源程序进行了方法的验证,实验结果表明,一方面,使用错误覆盖更为全面的组合策略能够充分模拟程序的复杂缺陷,聚类约简后,二阶变异体的个数在极大减少的同时,二阶变异充分度和一阶变异充分度更加接近,但是因为执行的二阶变异体数目明显降低,从而使得运行聚类后的二阶变异体时间开销明显比执行全部二阶变异体降低;另一方面,实验过程发现了有利于增加测试组件的隐藏二阶变异体.     

基于程序变异的程序谱错误定位方法

针对基于程序谱错误定位方法完全依赖于测试用例的语句覆盖信息导致错误定位效率低下的问题,提出了一种基于变异测试技术的程序谱错误定位方法。在原有语句怀疑度计算方法的基础上,增加了程序变异后执行结果与原程序执行结果不同的测试用例变化情况的分析。此外,为解决程序变异后产生的变异体数量巨大而导致执行代价过大的问题,提出了根据变异位置约简变异体的策略。实验结果表明,与几种基于程序谱的程序错误定位方法相比,该方法的错误定位代价最低,能有效提高错误定位的效率。     

基于程序变异分析的软件错误定位

基于覆盖的错误定位(CBFL)方法通过获取成功和失败测试用例的覆盖信息和执行结果对程序中的错误进行定位,但该方法未考虑偶然性成功测试用例的影响,降低了错误定位的准确率。为此,提出一种新的软件错误定位方法,通过分析程序变异减少偶然性成功测试用例的影响,改进怀疑度计算公式,并加入对变异影响的计算。实验结果表明,与传统CBFL方法相比,该方法能够有效提高错误定位的准确率。     

等价变异体的弱变异分析方法

变异测试通过执行变异体评价给定测试用例集的质量。然而,一定比例的等价变异体,不仅增加变异测试成本,也影响测试用例评价结果的准确性。鉴于此,提出基于弱变异分析的方法,以有效检测等价变异体。所提方法将变异前后语句组合为条件语句,以反映杀死变异体的必要性条件,并构造变异分支;将所有变异分支集成到原程序中;通过分析变异分支的可满足性,判定等价变异体。将所提方法用于6个程序的实验,结果表明,所提方法能够有效检测等价变异体。     

一种基于UML状态图的规约变异测试方法

规约变异测试从软件功能的角度,对规约进行分析,从而揭示规约中存在的问题。本文提出一种基于UML状态图的变异测试方法,针对每种变异算子,分析其是否会引入冲突,进而有效避免不合理的变异操作;分析了每种变异算子产生等价变异体的条件,能够在生成变异体的同时检测并移除等价变异体,进而减少其对测试过程的影响;给出了杀掉每种变异体所需满足的条件,可在此基础上产生杀掉特定变异体所需的测试用例,从而提高测试用例集的质量。在此基础上,根据变异算子的实际功能,整合了功能相同的算子,减少了变异算子的数量,从而进一步降低了变异测试的开销。实验结果表明,本方法能够较好地提高测试用例的质量,进而提升测试的效率。     

基于高阶变异的多错误定位实证研究

错误定位是软件调试中最昂贵的活动之一.基于变异的错误定位(MBFL)技术假定被大多数失败测试用例杀死的变异体能够很好地定位错误的位置.之前的研究表明MBFL在单错误定位上有很好的定位效果,但关于MBFL在多错误定位上的表现没有被深入研究过.近年来,高阶变异体被提出用于构造难以被杀死的复杂错误,但高阶变异体是否能提升MBFL的错误定位精度是未知的.本文中,我们研究了一阶变异体和高阶变异体在多错误定位场景下的表现.进一步,我们依据不同的变异位置将高阶变异体划分成3类:准确高阶变异体、部分准确高阶变异体和不准确高阶变异体.探索哪类变异体在错误定位上更有效.基于5个程序上的实证研究,我们发现在多错误定位场景下,高阶变异体比一阶变异体有更好的定位效果.更进一步,我们发现不同种类的高阶变异体的影响是不容忽视的.具体而言,准确高阶变异体比不准确高阶变异体有更高的贡献.因此研究人员应提出更有效的方法生成这类变异体用于未来的MBFL研究.     

运用变异测试的并行程序测试用例最小化算法

在并行程序测试中,测试输入和线程交互时序是影响并行错误检测的两个关键因素。以缩减并行错误检测的输入空间为目标,给出一种基于变异测试的测试用例最小化算法。首先对并行程序进行研究,选取与并行错误密切相关的9个变异算子,并以此为基础为待测程序生成多种变异体;采用JPF作为线程调度工具来执行测试用例,根据变异评分与平均时间成本对测试用例进行排序,在优化后的测试用例集中选取检测能力不重复的测试用例,从而得到面向并行错误检测的最小测试用例集。实验结果证明,该方法能有效减小测试用例集的规模,并大幅缩短运行时间,从而提高了并行程序的测试效率。     

基于模型检测技术的变异测试用例生成方法

为了进行基于模型的软件测试变异分析,文中提出了一种基于模型检测的变异测试用例生成方法。基于模型检测工具UPPAAL的形式化分析与测试框架,首先用符合规范的时间自动机模型描述被测系统;然后基于时间自动机模型的基本结构和语法,对系统模型进行一组变异操作,并模拟实现时可能出现的一些错误;对变异后的模型分别使用UPPAAL Yggdrasil工具,生成一组能覆盖变异区域的测试用例;在系统变异模型上执行生成的测试用例,根据测试执行结果(是否能“杀死”变异体)筛选出一组有效的测试用例。通过实例验证,所提方案生成的测试用例是有效的,且测试用例集变异分数优于现有的基于状态机复制的变异测试用例自动生成方法和基于模型中变换覆盖的变异测试用例生成方法。     

An empirical study on the use of mutant traces for diagnosis of faults in deployed systems

Debugging deployed systems is an arduous and time consuming task. It is often difficult to generate traces from deployed systems due to the disturbance and overhead that trace collection may cause on a system in operation. Many organizations also do not keep historical traces of failures. On the other hand earlier techniques focusing on fault diagnosis in deployed systems require a collection of passing–failing traces, in-house reproduction of faults or a historical collection of failed traces. In this paper, we investigate an alternative solution. We investigate how artificial faults, generated using software mutation in test environment, can be used to diagnose actual faults in deployed software systems. The use of traces of artificial faults can provide relief when it is not feasible to collect different kinds of traces from deployed systems. Using artificial and actual faults we also investigate the similarity of function call traces of different faults in functions. To achieve our goal, we use decision trees to build a model of traces generated from mutants and test it on faulty traces generated from actual programs. The application of our approach to various real world programs shows that mutants can indeed be used to diagnose faulty functions in the original code with approximately 60–100% accuracy on reviewing 10% or less of the code; whereas, contemporary techniques using pass–fail traces show poor results in the context of software maintenance. Our results also show that different faults in closely related functions occur with similar function call traces. The use of mutation in fault diagnosis shows promising results but the experiments also show the challenges related to using mutants.     

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.     

基于模板匹配的BPEL程序故障修复及优化技术

BPEL (business process execution language)是一种可执行的Web服务组合语言. 与传统程序相比, BPEL程序在编程模型、执行方式等方面存在较大差异. 这些新特点使得如何定位并修改测试阶段发现的BPEL程序故障成为挑战, 面向传统软件的故障修复技术难以直接应用于BPEL程序. 从变异分析角度出发, 提出一种基于模板匹配的BPEL程序故障修复方法BPELRepair. 为了克服基于变异分析的故障修复技术计算开销高的缺点, 从补丁生成、测试用例选择以及终止条件3个角度提出多种优化策略. 开发一个BPEL故障修复支持工具, 提高故障修复的自动化程度与效率. 采用经验研究的方式, 评估所提故障修复技术及优化策略的有效性. 实验结果表明, 所提故障修复方法能够成功修复约53%的BPEL程序故障; 所提优化策略能够显著降低搜索匹配、补丁程序验证、测试用例执行与故障修复等方面的开销.     

ContextAug: model-domain failing test augmentation with contextual information

In the process of software development, the ability to localize faults is crucial for improving the efficiency of debugging. Generally speaking, detecting and repairing errant behavior at an early stage of the development cycle considerably reduces costs and development time. Researchers have tried to utilize various methods to locate the faulty codes. However, failing test cases usually account for a small portion of the test suite, which inevitably leads to the class-imbalance phenomenon and hampers the effectiveness of fault localization. Accordingly, in this work, we propose a new fault localization approach named ContextAug. After obtaining dynamic execution through test cases, ContextAug traces these executions to build an information model; subsequently, it constructs a failure context with propagation dependencies to intersect with new model-domain failing test samples synthesized by the minimum variability of the minority feature space. In contrast to traditional test generation directly from the input domain, ContextAug seeks a new perspective to synthesize failing test samples from the model domain, which is much easier to augment test suites. Through conducting empirical research on real large-sized programs with 13 state-of-the-art fault localization approaches, ContextAug could significantly improve fault localization effectiveness with up to 54.53%. Thus, ContextAug is verified as able to improve fault localization effectiveness.     

Combining mutation and fault localization for automated program debugging

This paper proposes a strategy for automatically fixing faults in a program by combining the ideas of mutation and fault localization. Statements ranked in order of their likelihood of containing faults are mutated in the same order to produce potential fixes for the faulty program. The proposed strategy is evaluated using 8 mutant operators against 19 programs each with multiple faulty versions. Our results indicate that 20.70% of the faults are fixed using selected mutant operators, suggesting that the strategy holds merit for automatically fixing faults. The impact of fault localization on efficiency of the overall fault-fixing process is investigated by experimenting with two different techniques, Tarantula and Ochiai, the latter of which has been reported to be better at fault localization than Tarantula, and also proves to be better in the context of fault-fixing using our proposed strategy. Further experiments are also presented to evaluate stopping criteria with respect to the mutant examination process and reveal that a significant fraction of the (fixable) faults can be fixed by examining a small percentage of the program code. We also report on the relative fault-fixing capabilities of mutant operators used and present discussions on future work.     

一种基于变异分析的BPEL程序故障定位技术

不同于传统C,C++或Java程序,BPEL(Business Process Execution Language)程序由一组活动及其之间的交互组成,同时引入了并发、序列化、XML表示等新特征,这些新特点使得定位BPEL程序的故障具有一定的挑战性.针对现有故障定位技术在有效性方面的不足,提出一种基于变异分析的BPEL...     

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

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

Diversity maximization speedup for localizing faults in single-fault and multi-fault programs

Fault localization is useful for reducing debugging effort. Such techniques require test cases with oracles, which can determine whether a program behaves correctly for every test input. Although most fault localization techniques can localize faults relatively accurately even with a small number of test cases, choosing the right test cases and creating oracles for them are not easy. Test oracle creation is expensive because it can take much manual labeling effort (i.e., effort needed to decide whether the test cases pass or fail). Given a number of test cases to be executed, it is challenging to minimize the number of test cases requiring manual labeling and in the meantime achieve good fault localization accuracy. To address this challenge, this paper presents a novel test case selection strategy based on Diversity Maximization Speedup (Dms). Dms orders a set of unlabeled test cases in a way that maximizes the effectiveness of a fault localization technique. Developers are only expected to label a much smaller number of test cases along this ordering to achieve good fault localization results. We evaluate the performance of Dms on 2 different types of programs, single-fault and multi-fault programs. Our experiments with 411 faults from the Software-artifact Infrastructure Repository show (1) that Dms can help existing fault localization techniques to achieve comparable accuracy with on average 67 and 6 % fewer labeled test cases than previously best test case prioritization techniques for single-fault and multi-fault programs, and (2) that given a labeling budget (i.e., a fixed number of labeled test cases), Dms can help existing fault localization techniques reduce their debugging cost (in terms of the amount of code needed to be inspected to locate faults). We conduct hypothesis test and show that the saving of the debugging cost we achieve for the real C programs are statistically significant.     

State dependency probabilistic model for fault localization

ContextFault localization is an important and expensive activity in software debugging. Previous studies indicated that statistically-based fault-localization techniques are effective in prioritizing the possible faulty statements with relatively low computational complexity, but prior works on statistical analysis have not fully investigated the behavior state information of each program element.ObjectiveThe objective of this paper is to propose an effective fault-localization approach based on the analysis of state dependence information between program elements.MethodIn this paper, state dependency is proposed to describe the control flow dependence between statements with particular states. A state dependency probabilistic model uses path profiles to analyze the state dependency information. Then, a fault-localization approach is proposed to locate faults by differentiating the state dependencies in passed and failed test cases.ResultsWe evaluated the fault-localization effectiveness of our approach based on the experiments on Siemens programs and four UNIX programs. Furthermore, we compared our approach with current state-of-art fault-localization methods such as SOBER, Tarantula, and CP. The experimental results show that, our approach can locate more faults than the other methods in every range on Siemens programs, and the overall efficiency of our approach in the range of 10–30% of analyzed source code is higher than the other methods on UNIX programs.ConclusionOur studies show that our approach consistently outperforms the other evaluated techniques in terms of effectiveness in fault localization on Siemens programs. Moreover, our approach is highly effective in fault localization even when very few test cases are available.