基于贡献度的两两组合测试用例生成算法

为在两两组合测试中获得近似最小的测试用例集,提出一种基于贡献度的两两组合测试用例自动生成算法。生成满足覆盖要求的有序配对集,根据有序配对集生成初始用例集,对初始用例集进行简约,获得测试用例集。实验结果表明,该算法生成的测试用例数目较少,算法效率较高。     

参数配对及n-way组合覆盖算法研究

组合测试是软件测试数据生成研究的一个重要领域,其中参数配对组合测试的应用最为广泛.对常用的参数配对组合覆盖方法进行了综述分析.目前主流的配对覆盖算法AETG和IPO所存在的主要问题是在确定水平取值时,具有盲目性和随机性,从而难以控制测试用例的规模.为此提出了改进的AETG算法和IPO算法,改进算法通过对参数进行预处理以及综合考虑各因素的水平组合等手段,对测试用例的规模进行控制,采用更加完备的方法尽早确定水平取值.为验证新算法的有效性,进行了仿真实验和实际测试,结果表明,改进算法所生成的测试用例数量要少于原算法,测试用例约减效果更为明显;测试用例数与配对数之间、测试用例数与因素水平数之间存在着某些规律性的联系,分析得出了一系列相关的结论.在配对覆盖的基础上,提出了遗传算法与AETG算法相结合的n-way组合覆盖算法,证明了其时间复杂性较已有算法得到了改善.     

组合测试用例生成技术

组合测试是一种科学有效的软件测试方法,该方法旨在使用较少的测试用例有效地检测软件系统中各个因素以及它们之间的相互作用对系统产生的影响,实践证明其具有较高的错误检测能力。当前组合测试研究的热点之一是组合测试用例生成问题,即如何针对具体待测软件,在满足给定组合覆盖要求的前提下,生成规模尽可能小的测试用例集,以便在保证错误检测能力的前提下尽可能降低测试成本。从N维组合覆盖和变力度组合覆盖等两类不同的组合覆盖标准出发,简要介绍了迄今为止人们在组合测试用例生成领域所取得的研究成果,对现有的组合用例生成方法进行了分类和总结。此外,还对优先级、组合约束、错误定位等条件和应用场景下的组合测试用例生成技术进行了介绍。最后,分析了现有成果中存在的问题,并对该领域未来的研究方向进行了分析和讨论。     

基于输入输出关系的局部组合测试技术

主要针对软件测试中黑盒测试时测试用例集过大,以及测试效率低的问题,提出了一种有用有效的测试用例集生成设计方法.该方法根据待测系统参数的输入输出关系,对输入参数进行分组生成输入参数的组合关系集,再仅对组合关系集中每组输入变量生成两两组合覆盖测试用例集合,然后进行水平拼接生成最终的用于待测系统测试的测试用例集合.实验结果表明,该方法不仅能有效地减少了测试用例数目,而且还能够保持了原来测试检错能力,从而提高测试效率.     

具有约束条件的组合测试用例集的构建方法

针对如何为存在约束条件的软件系统生成尽可能小的组合测试用例集问题,提出了基于组合测试算法的约束组合测试法.该方法是对待测系统中的约束条件进行处理,将约柬条件先转化为合取范式再转化为布尔表达式的形式.利用布尔可满足性求解器进行求解,找出满足约束条件的约束组合测试用例.最后运用AETG-SAT算法得到较优的组合测试用例集,并通过实验表明了AETG-SAT算法的优越性.     

基本路径测试用例设计算法

McCabe提出的基本路径测试法(McCABE T J. A complexity measure. IEEE Transactions on Software Engineering, 1976, SE-2(4): 308-320)是动态白盒测试技术中严谨而有效的方法,但存在测试用例设计效率较低的问题,影响了该方法在工程项目中的广泛应用。为了解决这一问题,从被测程序的基本结构出发,提出一种基于组合的基本路径测试用例设计方法。创建一种基于Z路径覆盖的基本单元图,构建由基本单元图组合形成控制流图的组合规则,以此为基础提出了基本路径组合算法,该算法只需一次扫描程序得到程序基本结构的路径集,将这些路径进行组合即可生成被测程序的基本路径集。该方法比McCabe所提出的方法构造过程简洁,能有效提高基本路径测试用例设计的效率。     

基于符号零压缩二叉决策图的组合测试用例生成方法

组合测试是系统测试中一种非常有效的方法,能够在保证错误检出率的前提下采用较少的测试用例来测试系统。但是,组合测试用例集构造问题的复杂度是NP完全的。给出了一种基于符号零压缩二叉决策图(Zero-suppressed Binary Decision Diagram,ZBDD)的组合测试用例生成方法。该方法首先利用ZBDD的结构特性,对测试系统进行紧凑的符号表示。然后利用ZBDD的隐式操作,结合贪心算法的思想,不断地覆盖更多的组合并缩小未覆盖组合集合,生成2～4维覆盖强度的较小测试用例集。实验证明,所提方法不仅可行而且节点开销小。     

配对组合测试中参数约束问题研究

给出了配对组合测试参数约束分类方法及相关定义。重点对有2值型约束的情况进行了研究,得出有2值型约束存在时虽然所需覆盖的配对数减少,但测试集不一定减小的结论;给出有2值型约束时测试集的最小下限,并证明之。最后介绍了能够有效解决配对组合测试参数约束问题的HPC_IPO约束控制算法。     

形式概念分析在Web应用测试用例选取中的应用

为了避免基于模型的Web应用测试中存在的状态组合爆炸问题,分析了经典的每个一次和基本选择的状态组合爆炸避免方法,指出了这两种方法的不足,提出了应用形式概念分析,根据给定的测试覆盖准则,精简测试用例集,避免状态组合爆炸的方法,并改进了Sampath的测试用例选取规则.最后根据形式概念分析的原理,开发了测试用例集精简工具,提高了测试过程的自动化程度,用实例说明了方法的有效性.     

基于两两覆盖准则的遗传算法测试用例生成

软件参数的组合测试是发现参数组合问题的重要方法,但是参数组合测试面临着组合爆炸问题,成对测试可以有效降低测试成本。提出了一种基于遗传算法的成对测试生成方法,该方法用于选择当前局部优化覆盖的测试用例,在此基础上构建满足成对测试基准的测试用例套,结果表明该方法能在不降低测试覆盖精度的情况下有效降低了测试用例数量。     

A Case Study in Matching Test and Proof Coverage

This paper studies the complementarity of test and deductive proof processes for Java programs specified in JML (Java Modeling Language). The proof of a program may be long and difficult, especially when automatic provers give up. When a theorem is not automatically proved, there are two possibilities: either the theorem is correct and there are not enough pieces of information to deal with the proof, or the theorem is incorrect. In order to discriminate between those two alternatives, testing techniques can be used. Here, we present experiments around the use of the JACK tool to prove Java programs annotated with JML assertions. When JACK fails to decide proof obligations, we use a combinatorial testing tool, TOBIAS, to produce large test suites that exercise the unproved program parts. The key issue is to establish the relevance of the test suite with respect to the unproved proof obligations. Therefore, we use code coverage techniques: our approach takes advantage of the statement orientation of the JACK tool to compare the statements involved in the unproved proof obligations and the statements covered by the test suite. Finally, we ensure our confidence within the test suites, by evaluating them on mutant program killing exercises. These techniques have been put into practice and are illustrated by a simple case study.     

Pairwise testing for systems with data derived from real‐valued variable inputs

Pairwise testing is an effective combinatorial test case generation approach in which test cases are developed to execute all possible pairwise combinations of system inputs. It can help reduce the number of test cases and save testing time yet still effective in finding defects. However, it is very difficult for practitioners to effectively apply pairwise testing in the real world because of the lack of suitable techniques and guidelines. To redress this situation, this paper conducts a case study of applying pairwise testing to system data derived from real‐valued variable inputs. In order to apply pairwise testing to this case study, this paper develops a test procedure and a novel partitioning method to test derived data as a naïve application of the conventional pairwise testing that would produce a huge number of test cases. A comparative evaluation shows that the pairwise testing of the proposed approach is more effective than the random testing with a 12–20% higher fault detection ratio. Based on our experience, guidelines for applying pairwise testing in practice are also presented. Copyright © 2014 John Wiley & Sons, Ltd.     

Using combinatorial testing to build navigation graphs for dynamic web applications

Modelling a software system is often a challenging prerequisite to automatic test case generation. Modelling the navigation structure of a dynamic web application is particularly challenging because of the presence of a large number of pages that are created dynamically and the difficulty of reaching a dynamic page unless a set of appropriate input values are provided for the parameters. To address the first challenge, some form of abstraction is required to enable scalable modelling. For the second challenge, techniques are required to select appropriate input values for parameters and systematically combine them to reach new pages. This paper presents a combinatorial approach in building a navigation graph for dynamic web applications. The navigation graph can then be used to automatically generate test sequences for testing web applications. The novelty of our approach is twofold. First, we use an abstraction scheme to control the page explosion problem, where pages that are likely to have the same navigation behaviour are grouped together and are represented as a single node in the navigation graph. Second, assuming that values of individual parameters are supplied manually or generated from other techniques, we combine parameter values such that well‐defined combinatorial coverage of input parameter values is achieved. Using combinatorial coverage can significantly reduce the number of requests that have to be submitted while still achieving effective coverage of the navigation structure. We implement our combinatorial approach in a tool, Tansuo, and apply the tool on seven open‐source web applications. We evaluate the effectiveness of Tansuo's exploration process guided by t‐way coverage, for t = 1,2,3, with respect to code coverage, and find that the navigation structure exploration by Tansuo, in general, results in high code coverage (more than 80% statement coverage for most of our subject applications when dead code is removed). We compare Tansuo's effectiveness with two other navigation graph tools and find that Tansuo is more effective. Our empirical results indicate that using pairwise coverage in Tansuo results in the efficient generation of navigation graphs and effective exploration of dynamic web applications. Copyright © 2016 John Wiley & Sons, Ltd.     

一种改进的两两组合测试用例生成方法

本文针对多因素二水平系统提出:将所有的测试数据表示为一棵二叉解空间树,用回溯法对二叉解空间树进行路径搜索来生成测试用例,然后使用贪心算法生成补充的测试用例,以满足两两组合覆盖标准。使用这种方法生成的测试数据集具有很高的覆盖率。     

On the use of a similarity function for test case selection in the context of model‐based testing

Test case selection in model‐based testing is discussed focusing on the use of a similarity function. Automatically generated test suites usually have redundant test cases. The reason is that test generation algorithms are usually based on structural coverage criteria that are applied exhaustively. These criteria may not be helpful to detect redundant test cases as well as the suites are usually impractical due to the huge number of test cases that can be generated. Both problems are addressed by applying a similarity function. The idea is to keep in the suite the less similar test cases according to a goal that is defined in terms of the intended size of the test suite. The strategy presented is compared with random selection by considering transition‐based and fault‐based coverage. The results show that, in most of the cases, similarity‐based selection can be more effective than random selection when applied to automatically generated test suites. Copyright © 2009 John Wiley & Sons, Ltd.     

基于解空间树的组合测试数据生成

在组合覆盖测试模型的基础上提出：将所有的可用测试数据表示为一棵解空间树,利用回溯法对解空间树进行路径搜索来生成测试数据,然后使用贪心算法补充生成测试数据,以满足两两组合覆盖标准.并且实现了基于该方法的测试数据生成工具,所生成的测试数据集与同类工具相比具有一定的特点和优势.     

A density‐based greedy algorithm for higher strength covering arrays

Algorithmic construction of software interaction test suites has focussed on pairwise coverage; less is known about the efficient construction of test suites for t‐way interactions with t≥3. This study extends an efficient density‐based algorithm for pairwise coverage to generate t‐way interaction test suites and shows that it guarantees a logarithmic upper bound on the size of the test suites as a function of the number of factors. To complement this theoretical guarantee, an implementation is outlined and some practical improvements are made. Computational comparisons with other published methods are reported. Many of the results improve upon those in the literature. However, limitations on the ability of one‐test‐at‐a‐time algorithms are also identified. Copyright © 2008 John Wiley & Sons, Ltd.     

On the order of test goals in specification-based testing

Model-based testing techniques often select test cases according to test goals such as coverage criteria or mutation adequacy. Complex criteria and large models lead to large test suites, and a test case created for one coverage item usually covers several other items as well. This can be problematic if testing is expensive and resources are limited. Therefore, test case generation can be optimized in order to avoid unnecessary test cases and minimize the test generation and execution costs. Because of this optimization the order in which test goals are selected is expected to have an impact on both the performance of the test case generation and the size of resulting test suites, although finding the optimal order is not feasible in general. In this paper we report on experiments to determine the effects of the order in which test goals are selected on performance and the size of resulting test suites, and evaluate different heuristics to select test goals such that the time required to generate test suites as well as their size are minimized. The test case generation approach used for experimentation uses model checkers, and experimentation shows that good results can be achieved with any random ordering, but some improvement is still possible with simple heuristics.     

Two case studies in grammar-based test generation

Grammar-based test generation (GBTG) has seen extensive study and practical use since the 1970s. GBTG was introduced to generate source code for testing compilers from context-free grammars specifying language syntax. More recently, GBTG has been applied to many other testing problems, including the generation of eXtensible Markup Language (XML) documents and the generation of packets for testing communications protocols. Recent research has shown how to integrate covering-array techniques such as pairwise testing into GBTG tools. While the integration offers considerable power to the tester, there are few practical demonstrations in the literature. We present two case studies showing how to use grammars and covering arrays for automated software testing. The first case study exposes HTML injection vulnerabilities in an RSS feed parser. The second case study determines the effectiveness of network firewalls when faced with TCP flag attacks. The case studies illustrate the use of covering arrays in a GBTG context, the use of visualization to understand large test logs, and the issues and tradeoffs in the design of fully automated GBTG test suites.