组合测试:原理与方法

组合测试能够在保证错误检出率的前提下采用较少的测试用例测试系统.但是,组合测试用例集的构造问题的复杂度是NP完全的.组合测试方法的有效性和复杂性吸引了组合数学领域和软件工程领域的学者们对其进行深入的研究.总结了近年来在组合测试方面的研究进展,主要内容包括:组合测试准则的研究、组合测试生成问题与其他NP完全问题的联系、组合测试用例的数学构造方法、采用计算机搜索的组合测试生成方法以及基于组合测试的错误定位技术.     

组合测试中用例集的选择策略

组合测试用例众多,软件测试人员都希望用最少的测试用例集达到最好的测试覆盖。研究了组合测试的常规算法,比较了配对测试法和正交表测试法的特点,并借助于PICT测试工具重点研究了2因子模型的配对组合测试,在此基础上,总结出在组合测试中测试用例集的选择策略,进而达到满意的测试覆盖。     

和声搜索算法在组合测试用例生成中的应用

一个复杂的软件系统通常受很多因素影响,它们之间的交互造成系统行为的复杂化和各种故障,要完全地测试这些交互组合,不切实际。组合测试技术考虑因素的不同交互对系统产生的不同影响,以最小的测试用例提高测试质量。本文提出一种根据和声搜索算法产生组合测试用例的方法,解决多维组合覆盖和可变强度组合覆盖的关键问题,并通过实验验证该方法的有效性。     

覆盖表生成的粒子群算法:参数优化和自适应算法

组合测试是一种能有效检测由参数间相互作用所引发错误的软件测试方法,覆盖表的生成是该研究领域的一个重要问题.目前,很多方法已被应用于覆盖表生成,基于演化搜索的粒子群算法尽管能得到较优的解,但其性能容易受到配置参数的影响.本文首先使用试验设计的方法,对不同覆盖表生成的算法参数进行优化,系统分析了参数对算法性能的影响.同时,考虑到对不同的覆盖表,最优的算法参数往往不同,因此进一步提出了一种适用于覆盖表生成的自适应粒子群算法.实验结果表明,在一定的参数取值范围内粒子群算法都能获得较好的结果,且不存在一组对任意覆盖表都能有最优性能的算法参数.通过参数调优,能使粒子群算法获得比已有结果规模更小的覆盖表,同时,与经过参数调优后的算法相比,自适应粒子群算法在大部分情况下有更好的性能.     

A Formal Logic Approach to Constrained Combinatorial Testing

Combinatorial testing is as an effective testing technique to reveal failures in a given system, based on input combinations coverage and combinatorial optimization. Combinatorial testing of strength t (t ≥ 2) requires that each t-wise tuple of values of the different system input parameters is covered by at least one test case. Combinatorial test suite generation algorithms aim at producing a test suite covering all the required tuples in a small (possibly minimal) number of test cases, in order to reduce the cost of testing. The most used combinatorial technique is the pairwise testing (t = 2) which requires coverage of all pairs of input values. Constrained combinatorial testing takes also into account constraints over the system parameters, for instance forbidden tuples of inputs, modeling invalid or not realizable input values combinations. In this paper a new approach to combinatorial testing, tightly integrated with formal logic, is presented. In this approach, test predicates are used to formalize combinatorial testing as a logical problem, and an external formal logic tool is applied to solve it. Constraints over the input domain are expressed as logical predicates too, and effectively handled by the same tool. Moreover, inclusion or exclusion of select tuples is supported, allowing the user to customize the test suite layout. The proposed approach is supported by a prototype tool implementation and results of experimental assessment are also presented.     

Achievement of minimized combinatorial test suite for configuration-aware software functional testing using the Cuckoo Search algorithm

ContextSoftware has become an innovative solution nowadays for many applications and methods in science and engineering. Ensuring the quality and correctness of software is challenging because each program has different configurations and input domains. To ensure the quality of software, all possible configurations and input combinations need to be evaluated against their expected outputs. However, this exhaustive test is impractical because of time and resource constraints due to the large domain of input and configurations. Thus, different sampling techniques have been used to sample these input domains and configurations.ObjectiveCombinatorial testing can be used to effectively detect faults in software-under-test. This technique uses combinatorial optimization concepts to systematically minimize the number of test cases by considering the combinations of inputs. This paper proposes a new strategy to generate combinatorial test suite by using Cuckoo Search concepts.MethodCuckoo Search is used in the design and implementation of a strategy to construct optimized combinatorial sets. The strategy consists of different algorithms for construction. These algorithms are combined to serve the Cuckoo Search.ResultsThe efficiency and performance of the new technique were proven through different experiment sets. The effectiveness of the strategy is assessed by applying the generated test suites on a real-world case study for the purpose of functional testing.ConclusionResults show that the generated test suites can detect faults effectively. In addition, the strategy also opens a new direction for the application of Cuckoo Search in the context of software engineering.     

组合测试技术在防汛辅助决策支持系统中的应用

组合测试是一种重要的软件测试方法,能够有效地检测软件系统中各种因素间的组合可能促发的故障。防汛辅助决策支持系统需要输入多个查询条件实现相关信息的查询,影响系统正常工作的因素众多,可使用组合测试技术检测防汛辅助决策支持系统中各种参数及其相互作用对系统各种功能的影响。选择水雨情信息模块,重点探讨对水雨情信息模块建立组合测试建模,以及使用高级组合测试系统(ACTS)对该模块进行组合测试用例集的生成,再用测试用例集对系统进行测试。测试结果表明,两两组合测试仅需要执行35个测试用例,而全覆盖测试需要执行140个测试用例。     

覆盖表生成的遗传算法配置参数优化

覆盖表生成是组合测试的关键问题,很多数学方法、贪心算法以及演化搜索方法等被应用于生成各种覆盖表.针对演化搜索方法的性能受到方法本身配置参数影响很大这一实际问题,文中以二维覆盖表生成为实例,系统地对典型的演化搜索方法——遗传算法的种群规模、进化代数、交叉概率、变异概率以及遗传算法的变种算法等因素进行探索,设计了pair-wise法、Base choice法和爬山法3条实验路线探索遗传算法的这些配置参数及其相互作用对算法生成二维覆盖表效果的影响,并回答两个问题:对于特定二维覆盖表生成问题,是否存在遗传算法的最优参数配置;对于一般的二维覆盖表生成问题,是否存在通用的遗传算法最优参数配置.     

一种基于组合测试的软件故障调试方法

在研究了组合测试基本模型的基础上，提出了一种基于组合测试的故障原因诊断方法．该方法基于组合测试的结果，补充一些附加测试用例进行重新测试，并对其结果作进一步分析和验证，从而迅速将故障原因锁定在很小的范围内，这样可为软件的调试和测试工作提供更方便、更有价值的线索和参考．     

覆盖矩阵在参数组合配对测试中的应用

在实际测试中,用穷尽法测试全部测试案例会造成测试集爆炸、效率低下及资源浪费,正交矩阵虽能生成较优测试集,但其应用范围极为受限。该文提出一种覆盖矩阵构造方法解决上述问题,该矩阵以正交矩阵及其派生矩阵为基础构造,可以减少测试案例集,扩大其应用范围,提高测试效率。用.net工具实现该算法,证明其能够有效、快速地找到一个较优测试集。     

覆盖表生成的可配置贪心算法优化

覆盖表生成是组合测试研究的关键问题之一,其中,贪心算法因为速度快、生成的覆盖表规模小而得到人们的青睐.人们提出了很多基于不同策略的贪心算法,其中,多数算法可以归结到一个统一的算法框架,即形成一个可配置贪心算法,从该框架又可以衍生出很多新的算法.如何科学地配置优化受多个因素影响的算法框架、有效生成覆盖表是一个新的挑战.针对具有6个决策点的贪心算法框架,设计了3条不同的实验路线,系统地探索各个决策点以及它们之间相互作用对生成覆盖表规模的不同影响,寻找最佳配置,从而可以有效地生成规模更小的覆盖表,为覆盖表生成的贪心算法的设计和优化提供理论和实践基础.     

利用蚁群算法生成覆盖表:探索与挖掘

覆盖表生成问题是组合测试的重要研究内容之一,目前已有许多数学方法、贪心算法、搜索算法用于求解这一问题.蚁群算法作为一种能够有效求解组合优化问题的演化搜索算法,已被应用到求解覆盖表生成问题中.已有的研究工作表明:蚁群算法适于求解一般覆盖表、变力度覆盖表生成以及覆盖表排序等问题,但算法结果与其他覆盖表生成方法相比并不具有优势.为了进一步探索与挖掘蚁群算法生成覆盖表的潜力,进行了如下4个层次的改进工作:(1)算法变种集成;(2)算法参数配置优化;(3)演化对象结构调整及演化策略改进;(4)利用并行计算优化算法时间开销.实验结果表明:通过以上4个层次的改进,蚁群算法生成覆盖表的性能有了显著提升.     

覆盖表生成的禁忌搜索算法

组合测试可以有效检测待测系统中由参数间交互作用而引发的故障.在其30多年的发展过程中,覆盖表生成一直是关键问题之一,相关研究文献已达200多篇.作为一种有效的覆盖表生成算法,已有的禁忌搜索算法在所生成的覆盖表规模上具备一定的优势,但其解的质量和运算速度仍有提升空间;同时,这些算法实际应用能力较差,既不支持约束处理,也无法生成可变力度覆盖表.针对以上问题,提出了一种禁忌搜索算法.该算法从3个方面对已有的算法进行了改进：1）算法参数配置调优分pair-wise和爬山两阶段进行,确保使用较少配置条数最大程度击中最优配置,进一步提高算法生成覆盖表的规模;2）进行算法并行化,加速算法生成覆盖表的速度;3）增加约束处理和变力度处理,使算法可适应多种测试场景.实验结果表明,该算法在固定力度、变力度、带约束等多种类型覆盖表的规模上都具有一定优势,同时,并行化使算法平均加速2.6倍左右.     

Measuring and specifying combinatorial coverage of test input configurations

A key issue in testing is how many tests are needed for a required level of coverage or fault detection. Estimates are often based on error rates in initial testing, or on code coverage. For example, tests may be run until a desired level of statement or branch coverage is achieved. Combinatorial methods present an opportunity for a different approach to estimating required test set size, using characteristics of the test set. This paper describes methods for estimating the coverage of, and ability to detect, t-way interaction faults of a test set based on a covering array. We also develop a connection between (static) combinatorial coverage and (dynamic) code coverage, such that if a specific condition is satisfied, 100 % branch coverage is assured. Using these results, we propose practical recommendations for using combinatorial coverage in specifying test requirements, and for improving estimates of the fault detection capacity of a test set.     

组合测试用例生成技术

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

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

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

Using simulated annealing for computing cost-aware covering arrays

The configuration spaces of software systems are often too large to test exhaustively. Combinatorial interaction testing approaches, such as covering arrays, systematically sample the configuration space and test only the selected configurations. In an attempt to reduce the cost of testing, standard t-way covering arrays aim to cover all t-way combinations of option settings in a minimum number of configurations. By doing so, they simply assume that every configuration costs the same. When the cost varies from one configuration to another, however, minimizing the number of configurations is not necessarily the same as minimizing the cost. To overcome this issue, we have recently introduced cost-aware covering arrays. In a nutshell, a t-way cost-aware covering array is a standard t-way covering array that “minimizes” a given cost function modeling the actual cost of testing. In this work we develop a simulated annealing-based approach to compute cost-aware covering arrays, which takes as input a configuration space model enhanced with a cost function and computes a cost-aware covering array by using two alternating neighboring state generation strategies together with a fitness function expressed as a weighted sum of two objectives: covering all required t-way option setting combinations and minimizing the cost function. To the best of our knowledge, the proposed approach is the first approach that computes cost-aware covering arrays for general, non-additive linear cost functions with multiplicative interaction effects. We evaluate the approach both by conducting controlled experiments, in which we systematically vary the input models to study the sensitivity of the approach to various factors and by conducting experiments using real cost functions for real software systems. We also compare cost-aware covering arrays to standard covering arrays constructed by well-known algorithms and study how fast the construction costs are compensated by the cost reductions provided. Our empirical results suggest that the proposed approach is more effective and efficient than the existing approaches.     

Search‐based software test data generation: a survey

The use of metaheuristic search techniques for the automatic generation of test data has been a burgeoning interest for many researchers in recent years. Previous attempts to automate the test generation process have been limited, having been constrained by the size and complexity of software, and the basic fact that, in general, test data generation is an undecidable problem. Metaheuristic search techniques offer much promise in regard to these problems. Metaheuristic search techniques are high‐level frameworks, which utilize heuristics to seek solutions for combinatorial problems at a reasonable computational cost. To date, metaheuristic search techniques have been applied to automate test data generation for structural and functional testing; the testing of grey‐box properties, for example safety constraints; and also non‐functional properties, such as worst‐case execution time. This paper surveys some of the work undertaken in this field, discussing possible new future directions of research for each of its different individual areas. Copyright © 2004 John Wiley & Sons, Ltd.     

Design of test inputs and their sequences in multi-function system testing

This discussion paper addresses combinatorial models in system testing from the perspective of system usage (utilization) and corresponding examination of system functions and their groups. Thus the following aspects of multi-function system testing are under study: analysis of system requirements and revelation of atomic system functions and their relationships, analysis of system function groups (clusters), design of the most important test inputs and sequences of the test inputs. The basic combinatorial problem is: composition of the best (the most important) test input(s) for each group of atomic system functions. Additional combinatorial problems are the following: (a) design of test input sequence for a trail (chain) of function clusters, (b) design of collection of test input sequences as covering of function cluster digraph, (c) structural fusion of unit test results. Numerical and real world examples illustrate the proposed approach. Mark Sh. Levin received the M.S. degree in Radioengineering from Moscow Techn. Univ. for Communication and Informatics (1970), the M.S. degree in Mathematics from ‘Lomonosov’ Moscow State Univ. (1975), the Ph.D. degree in Systems Analysis and Combinatorial Optimization from Inst. for System Analysis of Russian Acad. of Sci. (1982). His research interests include systems engineering, decision making, combinatorial optimization, and applications. Currently Dr. Levin is with Inst. for Inform. Transmission Problems of Russian Acad. of Sci. (Moscow) as a Senior Research Scientist. He is a member of ACM, IEEE, SIAM, Int. Soc. on MCDM, Int. Soc. of Appl. Intel., and OR Society of Israel. Mark Last received his Ph.D. degree in Industrial Engineering from Tel Aviv Univ. (2000). Dr. Last is a faculty member at Dept. of Information Systems Engineering of Ben-Gurion Univ. (Israel) and affiliated as a visiting faculty at National Inst. for Systems Test and Productivity (Univ. of South Florida, USA). His research interests include information systems, knowledge discovery and data mining, fuzzy sets and fuzzy logic, and software testing. He is a member of IEEE Computer Society and ACM.     

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

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