基于分支覆盖的回归测试路径选择

回归测试是迭代式软件开发的重要环节,测试数据生成是回归测试的前提.传统的回归测试方法,从已有的测试数据中选择部分测试数据,并生成一些新的测试数据,以验证程序的正确性.但是,该方法容易生成冗余的测试数据,从而降低了回归测试的效率.研究了回归测试的分支覆盖问题,通过利用已有测试数据的路径覆盖信息,并选择一定个数的路径,以覆盖所有的目标分支.首先,以若干路径形成的集合作为决策变量,以路径最少、覆盖的分支最多以及包含的未覆盖路径最少为目标,建立路径选择问题的3目标优化模型;然后,采用遗传算法求解上述模型时,设计了基于目标重要性的个体评价策略;最后,基于已有的测试数据与选择的路径之间的覆盖关系,确定需要生成的测试数据.将所提方法应用于6个基准工业程序测试中,并与其他方法比较.实验结果表明,采用该方法选择的路径,能够覆盖更多的分支,需要生成的测试数据更少,回归测试消耗的时间更短.     

回归测试数据进化生成

采用遗传算法生成回归测试数据近年来得到普遍关注,该方法高效生成测试数据的前提是合理利用已有的测试数据形成初始进化种群,并设计有针对性的遗传操作.但是,到目前为止,相关的研究成果尚不多见.文中研究采用遗传算法生成回归测试数据以覆盖目标路径时,已有测试数据的利用问题,提出一种新的回归测试数据进化生成方法.该方法根据已有测试数据穿越的路径与目标路径的相似度,选择合适的测试数据,作为初始进化种群的部分个体.进一步,根据已有测试数据穿越的路径与目标路径不相同子路径的节点对应的输入分量,确定对进化个体实施遗传操作的位置.理论分析表明,所提方法可以有效提高测试数据生成效率.将所提方法应用于典型基准和工业程序的测试,并与已有方法比较,实验结果证实了所提方法的优越性.     

基于天牛须搜索的软件测试数据扩增方法

为使原测试用例集满足软件演化后新版本程序的测试需求,提出一种基于天牛须搜索算法的软件测试数据扩增方法。静态分析新旧版本程序,获取调用图和程序执行信息并得到所需测试的目标方法集,通过计算目标方法包含错误的影响度获得有序目标方法集。根据原测试用例集的覆盖信息选取部分测试用例作为初始的进化种群,基于分支距离和分支嵌套深度设计适应度函数,采用改进的天牛须搜索算法对有序目标方法集实现测试数据扩增。实验结果表明,与基于遗传算法和粒子群优化算法的测试数据扩增方法相比,该方法的测试数据扩增效率约平均提升49.91%和24.76%,且有效降低了回归测试成本。     

ALL-Uses覆盖引导的回归测试用例生成方法

基于扩展有限状态机(EFSM)的回归测试过程需要根据依赖关系变化对软件所做修改的影响域进行分析。为了针对软件某一功能进行修复,通常需要对多处代码进行同步修改,已有依赖分析方法在这种情况下暴露模型中触发条件和行为语句错误的效率不高。提出以ALL-Uses覆盖准则引导回归测试的方法,引入依赖关系变化因素的概念,修改待覆盖子路径的产生规则,对已有测试用例集中能有效覆盖子路径的用例进行选择、排序。针对已有测试用例无法覆盖的子路径,利用AOE活动图中求关键路径的方法将其补充为一条完整的迁移执行序列。选取三个软件进行实验,结果表明,本文方法可以在减小测试用例集规模的前提下有效提升ALL-Uses和植入错误的覆盖率,提高回归测试效率。     

基于搜索的分层回归测试数据集扩增方法

针对在回归测试中原有的测试数据集往往难以满足新版本软件的测试需求问题,提出一种基于搜索的分层回归测试数据生成方法。方法主要包含覆盖目标方法集获取模块和测试数据生成模块。首先对新版本程序进行抽象分析,提取出方法调用图,利用方法调用轨迹和已有测试数据建立方法覆盖信息,获取目标方法集,并通过计算贝叶斯条件概率对目标方法集进行优先选择;利用Hadamard矩阵设计正交种群,同时结合已有测试数据集进行种群初始化,采用文化基因算法对目标集中方法生成测试数据。该方法针对4个基准程序与随机法和遗传算法以及基于粒子群算法测试数据生成方法相比,测试数据的生成效率平均提高了95.2%、78.2%和50.5%,测试数据检错能力平均提高了47.9%、33.6%和18.2%,实验结果表明,该方法更适合回归测试数据的生成。     

基于分支函数线性逼近的测试数据自动生成算法

软件测试是保证软件可靠性的一个重要手段.面向路径测试是软件测试中一种重要方法.提出了一种分支函数线性逼近的测试数据自动生成算法.结合赵瑞莲给出的谓词切片算法和程序DUC表达方式以及本文提出的算法,给出了一个基于程序执行的路径测试及测试数据自动生成新算法.由于算法采用DUC表达式,不仅可以从源端判断子路径是否可行,而且有效地降低了不可行路径对算法性能的影响.另外,与现有文献中单纯利用分支函数极小化方法的算法相比,新算法由于有机结合了分支函数线性逼近和极小化方法的长处,因此减少了测试用例的数量,提高了测试效率.     

基于二叉树搜索空间缩减的测试数据生成

为了减小适应度函数计算量, 提高测试数据自动生成效率, 提出一种基于二叉树表示的搜索空间数据缩减方法。利用二叉树编码, 记录全空间中的覆盖路径和路径长度; 将目标路径和测试路径长度进行对比, 去除路径长度相差较大的路径; 利用遗传算法生成测试数据并同已有两种方法进行比较。实验结果表明, 在保证软件测试数据正确生成的情况下, 该方法在进化代数和运行时间上有明显优势, 生成测试数据效率高。     

一种基于约束的变异测试数据生成方法

作为衡量测试用例集完备性的测试策略,变异测试是一种"面向缺陷"的单元测试技术,主要用来生成完备的测试用例集.其中面向路径测试数据生成技术通过约束系统构造和求解过程实现用例集生成,是一种高效的测试用例生成技术.但目前大部分面向路径测试用例生成技术只考虑了程序语句间的控制依赖,即通过对控制流图的分析来构建约束系统,而忽略了语句间的数据依赖对约束系统的影响.充分考虑两种依赖关系,针对域削减的测试数据生成技术进行了改进,提出了一种考虑数据依赖的域削减方法.实验表明,这种方法在变异测试数据生成的成功率和执行效率上都有较大程度的提高.     

用于回归测试数据验算的筛选方法

通过利用覆盖数据技术和回归测试集选择技术,提出一种用于回归测试数据验算的筛选方法,该方法通过深度优先遍历程序的相关记录来筛选测试用例,能有效地提高回归测试的准确性,减少回归测试的测试时间和省略无需测试的测试用例,以达到降低回归测试的成本的目的.对顺序、循环和分支3类程序设计了相关的实验,比较了该算法在这3类程序上的使用效果.     

活动图模型驱动的Web应用程序测试方法

提出了一种活动图(AD)模型驱动的Web应用程序测试方法,从活动图中生成满足往返路径覆盖准则的测试序列,基于测试输入语法生成驱动测试序列执行的测试数据,将测试数据整合到测试序列中生成测试用例,运行测试用例进行测试并生成测试结果的报告。实现了一个原型工具以支持活动图模型驱动的Web应用程序测试方法,设计并完成了一个实验,验证了该方法的可行性与有效性。     

Directed test suite augmentation: an empirical investigation

Test suite augmentation techniques are used in regression testing to identify code elements in a modified program that are not adequately tested and to generate test cases to cover those elements. A defining feature of test suite augmentation techniques is the potential for reusing existing regression test suites. Our preliminary work suggests that several factors influence the efficiency and effectiveness of augmentation techniques that perform such reuse. These include the order in which target code elements are considered while generating test cases, the manner in which existing regression test cases and newly generated test cases are used, and the algorithm used to generate test cases. In this work, we present the results of two empirical studies examining these factors, considering two test case generation algorithms (concolic and genetic). The results of our studies show that the primary factor affecting augmentation using these approaches is the test case generation algorithm utilized; this affects both cost and effectiveness. The manner in which existing and newly generated test cases are utilized also has a substantial effect on efficiency and in some cases a substantial effect on effectiveness. The order in which target code elements are considered turns out to have relatively few effects when using concolic test case generation but in some cases influences the efficiency of genetic test case generation. The results of our first study, on four relatively small programs using a large number of test suites, are supported by our second study of a much larger program available in multiple versions. Together, the studies reveal a potential opportunity for creating a more cost‐effective hybrid augmentation approach leveraging both concolic and genetic test case generation techniques, while appropriately utilizing our understanding of the factors that affect them. Copyright © 2014 John Wiley & Sons, Ltd.     

Automatically performing weak mutation with the aid of symbolic execution,concolic testing and search-based testing

Automating software testing activities can increase the quality and drastically decrease the cost of software development. Toward this direction, various automated test data generation tools have been developed. The majority of existing tools aim at structural testing, while a quite limited number aim at a higher level of testing thoroughness such as mutation. In this paper, an attempt toward automating the generation of mutation-based test cases by utilizing existing automated tools is proposed. This is achieved by reducing the killing mutants’ problem into a covering branches one. To this extent, this paper is motivated by the use of state of the art techniques and tools suitable for covering program branches when performing mutation. Tools and techniques such as symbolic execution, concolic execution, and evolutionary testing can be easily adopted toward automating the test input generation activity for the weak mutation testing criterion by simply utilizing a special form of the mutant schemata technique. The propositions made in this paper integrate three automated tools in order to illustrate and examine the method’s feasibility and effectiveness. The obtained results, based on a set of Java program units, indicate the applicability and effectiveness of the suggested technique. The results advocate that the proposed approach is able to guide existing automating tools in producing test cases according to the weak mutation testing criterion. Additionally, experimental results with the proposed mutation testing regime show that weak mutation is able to speedup the mutant execution time by at least 4.79 times when compared with strong mutation.     

Heuristics-based infeasible path detection for dynamic test data generation

Automated test data generation plays an important part in reducing the cost and increasing the reliability of software testing. However, a challenging problem in path-oriented test data generation is the existence of infeasible program paths, where considerable effort may be wasted in trying to generate input data to traverse the paths. In this paper, we propose a heuristics-based approach to infeasible path detection for dynamic test data generation. Our approach is based on the observation that many infeasible program paths exhibit some common properties. Through realizing these properties in execution traces collected during the test data generation process, infeasible paths can be detected early with high accuracy. Our experiments show that the proposed approach efficiently detects most of the infeasible paths with an average precision of 96.02% and a recall of 100% of all the cases.     

GA-based multiple paths test data generator

Developers have learned over time that software testing costs a considerable amount of a software project budget. Hence, software quality managers have been looking for solutions to reduce testing costs and time. Considering path coverage as the test adequacy criterion, we propose using genetic algorithms (GA) for automating the generation of test data for white-box testing. There are evidences that GA has been already successful in generating test data. However, existing GA-based test data generators suffer from some problems. This paper presents our approach to overcome one of these problems; that is the inefficiency in covering multiple target paths. We have designed a GA-based test data generator that is, in one run, able to synthesize multiple test data to cover multiple target paths. Moreover, we have implemented a set of variations of the generator. Experimental results show that our test data generator is more efficient and more effective than others.     

C/C++程序静态内存泄漏警报自动确认方法

内存泄漏是C/C++程序的一种常见的、难以发现的缺陷,一直困扰着软件开发者,尤其是针对长时间运行的程序或者系统软件,内存泄漏的后果十分严重.针对内存泄漏的检测,目前主要有静态分析和动态测试两种方法.动态测试实际运行程序,具有较大开销,同时依赖测试用例的质量;静态分析技术及自动化工具已经被学术界和工业界广泛运用于内存泄漏缺陷检测中,然而由于静态分析采取了保守的策略,其结果往往包含数量巨大的误报,需要通过进一步人工确认来甄别误报,但人工确认静态分析的结果耗时且容易出错,严重限制了静态分析技术的实用性.本文提出了一种基于混合执行测试的静态内存泄漏警报的自动化确认方法.首先,针对静态分析报告的目标程序中内存泄漏的静态警报,对目标程序进行控制流分析,并计算警报的可达性,形成制导信息;其次,基于警报制导信息对目标程序进行混合执行测试;最后,在混合执行测试过程中,监控追踪内存对象的状态,判定内存泄漏是否发生,对静态警报进行动态确认并分类.实验结果表明该方法可以对静态内存泄漏警报进行有效的分类,显著降低了人工确认的工作量.实验详情参见：http://ssthappy.github.io/memleak/.     

A multiple-population genetic algorithm for branch coverage test data generation

The software testing phase in the software development process is considered a time-consuming process. In order to reduce the overall development cost, automatic test data generation techniques based on genetic algorithms have been widely applied. This research explores a new approach for using genetic algorithms as test data generators to execute all the branches in a program. In the literature, existing approaches for test data generation using genetic algorithms are mainly focused on maintaining a single-population of candidate tests, where the computation of the fitness function for a particular target branch is based on the closeness of the input execution path to the control dependency condition of that branch. The new approach utilizes acyclic predicate paths of the program’s control flow graph containing the target branch as goals of separate search processes using distinct island populations. The advantages of the suggested approach is its ability to explore a greater variety of execution paths, and in certain conditions, increasing the search effectiveness. When applied to a collection of programs with a moderate number of branches, it has been shown experimentally that the proposed multiple-population algorithm outperforms the single-population algorithm significantly in terms of the number of executions, execution time, time improvement, and search effectiveness.     

Dynamic stopping criteria for search-based test data generation for path testing

ContextEvolutionary algorithms have proved to be successful for generating test data for path coverage testing. However in this approach, the set of target paths to be covered may include some that are infeasible. It is impossible to find test data to cover those paths. Rather than searching indefinitely, or until a fixed limit of generations is reached, it would be desirable to stop searching as soon it seems likely that feasible paths have been covered and all remaining un-covered target paths are infeasible.ObjectiveThe objective is to develop criteria to halt the evolutionary test data generation process as soon as it seems not worth continuing, without compromising testing confidence level.MethodDrawing on software reliability growth models as an analogy, this paper proposes and evaluates a method for determining when it is no longer worthwhile to continue searching for test data to cover un-covered target paths. We outline the method, its key parameters, and how it can be used as the basis for different decision rules for early termination of a search. Twenty-one test programs from the SBSE path testing literature are used to evaluate the method.ResultsCompared to searching for a standard number of generations, an average of 30–75% of total computation was avoided in test programs with infeasible paths, and no feasible paths were missed due to early termination. The extra computation in programs with no infeasible paths was negligible.ConclusionsThe method is effective and efficient. It avoids the need to specify a limit on the number of generations for searching. It can help to overcome problems caused by infeasible paths in search-based test data generation for path testing.     

Generating test data for both paths coverage and faults detection using genetic algorithms: multi-path case

Generating test data that can expose the faults of the program is an important issue in software testing. Although previous methods of covering path can generate test data to traverse target path, the test data generated by these methods are difficult in detecting some low-probabilistic faults that lie on the covered paths. We present a method of generating test data for covering multiple paths to detect faults in this study. First, we transform the problem of covering multiple paths and detecting faults into a multi-objective optimization problem with constraint, and construct a mathematical model for it. Then, we give a strategy of solving the model based on a weighted genetic algorithm. Finally, we apply our method to several real-world programs, and compare it with several methods. The experimental results confirm that the proposed method can more efficiently generate test data that not only traverse the target paths but also detect faults lying in them than other methods.