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

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

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

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

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.     

The AETG system: an approach to testing based on combinatorialdesign

This paper describes a new approach to testing that uses combinatorial designs to generate tests that cover the pairwise, triple, or n-way combinations of a system's test parameters. These are the parameters that determine the system's test scenarios. Examples are system configuration parameters, user inputs and other external events. We implemented this new method in the AETG system. The AETG system uses new combinatorial algorithms to generate test sets that cover all valid n-way parameter combinations. The size of an AETG test set grows logarithmically in the number of test parameters. This allows testers to define test models with dozens of parameters. The AETG system is used in a variety of applications for unit, system, and interoperability testing. It has generated both high-level test plans and detailed test cases. In several applications, it greatly reduced the cost of test plan development     

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

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

Covering arrays avoiding forbidden edges

Covering arrays (CAs) can be used to detect the existence of faulty pairwise interactions between parameters or components in a software system. The generalization considered here applies to the situation in which some input combinations are invalid, a requirement quite common in software testing. In this paper, we study covering arrays avoiding forbidden edges (CAFEs), where certain pairwise interactions are forbidden while all others must be covered, and we aim to minimize the number of tests. We establish a theoretical framework for this problem, by providing connections to the edge clique covering problem, lower and upper bounds, complexity results and a recursive construction. We also give an algorithm for the case of binary alphabets.     

Mixed optimization combinatorial method for constructing covering arrays

Covering arrays are used for generating tests for interfaces with a large number of parameters. In this paper, a new method is described for constructing homogeneous and heterogeneous covering arrays that is based on a combination of combinatorial and optimization methods. In a wide class of particular cases, the method speeds up the construction of arrays several times (depending on a particular case) compared with well-known, widely used optimization methods. In most cases, the sizes of the arrays obtained are approximately the same as those of the arrays constructed by other optimization methods; in a number of particular cases, one could obtain arrays that are smaller by 5–15%. The application range of the new method is analyzed.     

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.     

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

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

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

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

A survey of methods for constructing covering arrays

The paper presents a survey of methods for constructing covering arrays used in generation of tests for interfaces with a great number of parameters. The application domain of these methods and algorithms used in them are analyzed. Specific characteristics of the methods, including time complexity and estimates of the required memory, are presented. Various—direct, recursive, optimization, genetic, and backtracking—algorithms used for constructing covering arrays are presented. Heuristics are presented that allow one to reduce arrays without loss of completeness, and application domains of these heuristics are outlined.     

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

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

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.     

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

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

Slicing communicating automata specifications: polynomial algorithms for model reduction

In the industry, communicating automata specifications are mainly used in fields where the reliability requirements are high, as this formalism allow the use of powerful validation tools. Still, on large scale industrial specifications, formal methods suffer from the combinatorial explosion phenomenon. In our contribution, we suggest to try to bypass this phenomenon, in applying slicing techniques preliminarily to the targeted complex analysis. This analysis can thus be performed a posteriori on a reduced (or sliced) specification, which is potentially less exposed to combinatorial explosion. The slicing method is based on dependence relations, defined on the specification under analysis, and is mainly founded on the literature on compiler construction and program slicing. A theoretical framework is described, for static analyses of communicating automata specifications. This includes formal definitions for the aforementioned dependence relations, and for a slice of a specification with respect to a slicing criterion. Efficient algorithms are also described in detail, for calculating dependence relations and specification slices. Each of these algorithms has been shown to be polynomial, and sound and complete with respect to its respective definition. These algorithms have also been implemented in a slicing tool, named Carver, that has shown to be operational in specification debugging and understanding. The experimental results obtained in model reduction with this tool are promising, notably in the area of formal validation and verification methods, e.g.model checking, test case generation.     

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.     

Non-specification-based approaches to logic testing for software

Testing is a crucial part of the development of software systems. In this paper, we consider testing of an implementation that is intended to satisfy a Boolean formula. In the literature, specification-based testing has been suggested for this purpose. Typically, such methods first hypothesize a fault class and then generate tests. However, there is almost no research that justifies fault classes proposed previously. Moreover, specifications amenable to automatic test generation are not always available to testers in practice. Based on these observations, we examine the applicability of non-specification-based approaches, which need no specification in the form of a Boolean formula to create tests. We compare a specification-based approach to three non-specification-based approaches, namely, random testing, antirandom testing, and combinatorial testing. The results of an experiment show that combinatorial testing is often comparative to specification-based testing and is superior to both random testing and antirandom testing.     

Analysis of testable PLA designs

A framework is presented for evaluating methods of testing programmable logic arrays (PLAs), and the attributes of 25 test design methodologies are tabulated. PLA testing problems are first examined, and several test-generation algorithms are briefly described. Techniques for designing testable designs are examined, namely, special coding, parity checking, signature analysis, divide and conquer, and fully testable PLAs. The attributes that make a good testable design are then discussed. They fall into four categories: (1) testability characteristics; (2) effect on original design; (3) requirements of the application environment; and (4) design costs, i.e. how difficult it is to implement the technique     

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.