IPOG/IPOG‐D: efficient test generation for multi‐way combinatorial testing

This paper presents two strategies for multi‐way testing (i.e. t‐way testing with t>2). The first strategy generalizes an existing strategy, called in‐parameter‐order, from pairwise testing to multi‐way testing. This strategy requires all multi‐way combinations to be explicitly enumerated. When the number of multi‐way combinations is large, however, explicit enumeration can be prohibitive in terms of both the space for storing these combinations and the time needed to enumerate them. To alleviate this problem, the second strategy combines the first strategy with a recursive construction procedure to reduce the number of multi‐way combinations that have to be enumerated. Both strategies are deterministic, i.e. they always produce the same test set for the same system configuration. This paper reports a multi‐way testing tool called FireEye, and provides an analytic and experimental evaluation of the two strategies. Copyright © 2007 John Wiley & Sons, Ltd.     

The density algorithm for pairwise interaction testing

There are many published algorithms for generating interaction test suites for software testing, exemplified by AETG, IPO, TCG, TConfig, simulated annealing and other heuristic search, and combinatorial design techniques. Among these, greedy one‐test‐at‐a‐time methods (such as AETG and TCG) have proven to be a reasonable compromise between the needs for small test suites, fast test‐suite generation, and flexibility to accommodate a variety of testing scenarios. However, such methods suffer from the lack of a worst‐case logarithmic guarantee on test suite size, while methods that provide such a guarantee at present are less efficient or flexible, or do not produce test suites that are competitive in size for practical testing scenarios. In this paper, a new algorithm establishes that efficient, greedy, one‐test‐at‐a‐time methods can indeed produce a logarithmic worst‐case guarantee on the test suite size. In addition, this can be done while still producing test suites that are of competitive size, and in a time that is comparable to the published methods. It is deterministic, guaranteeing reproducibility. It generates only one candidate test at a time, permits users to ‘seed’ the test suite with specified tests, and allows users to specify constraints of combinations that should be avoided. Further, statistical analysis examines the impact of five variables used to tune this density algorithm for execution time and test suite size: weighting of density for factors, scaling of density, tie‐breaking, use of multiple candidates, and multiple repetitions using randomization. Copyright © 2007 John Wiley & Sons, Ltd.     

An approach for experimentally evaluating effectiveness and efficiency of coverage criteria for software testing

Experimental work in software testing has generally focused on evaluating the effectiveness and effort requirements of various coverage criteria. The important issue of testing efficiency has not been sufficiently addressed. In this paper, we describe an approach for comparing the effectiveness and efficiency of test coverage criteria using mutation analysis. For each coverage criterion under study, we generate multiple coverage-adequate minimal test suites for a test-program from a test-pool, which are then executed on a set of systematically generated program mutants to obtain the fault data. We demonstrate the applicability of the proposed approach by describing the results of an experiment comparing the three code-based testing criteria, namely, block coverage, branch coverage, and predicate coverage. Our results suggest that there is a trade-off between effectiveness and efficiency of a coverage criterion. Specifically, the predicate coverage criterion was found to be most effective but least efficient whereas the block coverage criterion was most efficient but least effective. We observed high variability in the performance of block test suites whereas branch and predicate test suites were relatively consistent. Overall results suggest that the branch coverage criterion performs consistently with good efficiency and effectiveness, and it appears to be the most viable option for code-based control flow testing.     

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.     

A combinatorial testing strategy for concurrent programs

One approach to testing concurrent programs is called reachability testing, which derives test sequences automatically and on‐the‐fly, without constructing a static model. Existing reachability testing algorithms are exhaustive in that they are intended to exercise all possible synchronization sequences of a concurrent program with a given input. In this paper, we present a new testing strategy, called t‐way reachability testing, that adopts the dynamic framework of reachability testing but selectively exercises a subset of synchronization sequences. The selection of the synchronization sequences is based on a combinatorial testing strategy called t‐way testing. We present an algorithm that implements t‐way reachability testing, and report the results of several case studies that were conducted to evaluate its effectiveness. The results indicate that t‐way reachability testing can substantially reduce the number of synchronization sequences exercised during reachability testing while still effectively detecting faults. Copyright © 2007 John Wiley & Sons, Ltd.     

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.     

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.     

An empirical evaluation of several test‐a‐few strategies for testing particular conditions

Existing specification‐based testing techniques often generate comprehensive test suites to cover diverse combinations of test‐relevant aspects. Such a test suite can be prohibitively expensive to execute exhaustively because of its large size. A pragmatic strategy often adopted in practice, called test‐once strategy, is to identify certain particular conditions from the specification and to test each such condition once only. This strategy is implicitly based on the uniformity assumption that the implementation will process a particular condition uniformly, regardless of other parameters or inputs. As the decision of adopting the test‐once strategy is often based on the specification, whether the uniformity assumption actually holds in the implementation needs to be critically assessed, or else the risk of inadequate testing could be non‐negligible. As viable alternatives to reduce such a risk, a family of test‐a‐few strategies for the testing of particular conditions is proposed in this paper. Two rounds of experiments that evaluate the effectiveness of the test‐a‐few strategies as compared with the test‐once strategy are further reported. Our experiments do the following: (1) provide clear evidence that the uniformity assumption often, but not always, holds and that the assumption usually fails to hold when the implementation is faulty; (2) demonstrate that all our proposed test‐a‐few strategies are statistically more reliable than the test‐once strategy in revealing faulty programs; (3) show that random sampling is already substantially more effective than the test‐once strategy; and (4) indicate that, compared with other test‐a‐few strategies under study, choice coverage seems to achieve a better trade‐off between test effort and effectiveness. Copyright © 2011 John Wiley & Sons, Ltd.     

Analysing the effectiveness of rule-coverage as a reduction criterion for test suites of grammar-based software

The term grammar-based software describes software whose input can be specified by a context-free grammar. This grammar may occur explicitly in the software, in the form of an input specification to a parser generator, or implicitly, in the form of a hand-written parser. Grammar-based software includes not only programming language compilers, but also tools for program analysis, reverse engineering, software metrics and documentation generation. Hence, ensuring their completeness and correctness is a vital prerequisite for their use. In this paper we propose a strategy for the construction of test suites for grammar based software, and illustrate this strategy using the ISO C^+ + grammar. We use the concept of grammar-rule coverage as a pivot for the reduction of an implementation-based test suite, and demonstrate a significant decrease in the size of this suite. The effectiveness of this reduced test suite is compared to the original test suite with respect to code coverage and more importantly, fault detection. This work greatly expands upon previous work in this area and utilises large scale mutation testing to compare the effectiveness of grammar-rule coverage to that of statement coverage as a reduction criterion for test suites of grammar-based software. This work finds that when grammar rule coverage is used as the sole criterion for reducing test suites of grammar based software, the fault detection capability of that reduced test suite is greatly diminished when compared to other coverage criteria such as statement coverage.

Pairwise testing for software product lines: comparison of two approaches

Software Product Lines (SPL) are difficult to validate due to combinatorics induced by variability, which in turn leads to combinatorial explosion of the number of derivable products. Exhaustive testing in such a large products space is hardly feasible. Hence, one possible option is to test SPLs by generating test configurations that cover all possible t feature interactions (t-wise). It dramatically reduces the number of test products while ensuring reasonable SPL coverage. In this paper, we report our experience on applying t-wise techniques for SPL with two independent toolsets developed by the authors. One focuses on generality and splits the generation problem according to strategies. The other emphasizes providing efficient generation. To evaluate the respective merits of the approaches, measures such as the number of generated test configurations and the similarity between them are provided. By applying these measures, we were able to derive useful insights for pairwise and t-wise testing of product lines.     

Grammar‐based test generation with YouGen

Grammars are traditionally used to recognize or parse sentences in a language, but they can also be used to generate sentences. In grammar‐based test generation (GBTG), context‐free grammars are used to generate sentences that are interpreted as test cases. A generator reads a grammar G and generates L(G), the language accepted by the grammar. Often L(G) is so large that it is not practical to execute all of the generated cases. Therefore, GBTG tools support ‘tags’: extra‐grammatical annotations which restrict the generation. Since its introduction in the early 1970s, GBTG has become well established: proven on industrial projects and widely published in academic venues. Despite the demonstrated effectiveness, the tool support is uneven; some tools target specific domains, e.g. compiler testing, while others are proprietary. The tools can be difficult to use and the precise meaning of the tags are sometimes unclear. As a result, while many testing practitioners and researchers are aware of GBTG, few have detailed knowledge or experience. We present YouGen, a new GBTG tool supporting many of the tags provided by previous tools. In addition, YouGen incorporates covering‐array tags, which support a generalized form of pairwise testing. These tags add considerable power to GBTG tools and have been available only in limited form in previous GBTG tools. We provide semantics for the YouGen tags using parse trees and a new construct, generation trees. We illustrate YouGen with both simple examples and a number of industrial case studies. Copyright © 2010 John Wiley & Sons, Ltd.     

A dynamic stochastic model for automatic grammar‐based test generation

Grammar‐based test generation provides a systematic approach to producing test cases from a given context‐free grammar. Unfortunately, naive grammar‐based test generation is problematic because of the fact that exhaustive random test case production is often explosive, and grammar‐based test generation with explicit annotation controls often causes unbalanced testing coverage. In this paper, we present an automatic grammar‐based test generation approach, which takes a symbolic grammar as input, requires zero control input from users, and produces well‐distributed test cases. Our approach utilizes a novel dynamic stochastic model where each variable is associated with a tuple of probability distributions, which are dynamically adjusted along the derivation. We further present a coverage tree illustrating the distribution of generated test cases and their detailed derivations. More importantly, the coverage tree supports various implicit derivation control mechanisms. We implemented this approach in a Java‐based system, named Gena. Each test case generated by Gena automatically comes with a set of structural features, which can play an important and effective role on automated failure causes localization. Experimental results demonstrate the effectiveness of our approach, the well‐balanced distribution of generated test cases over grammatical structures, and a case study on grammar‐based failure causes localization. Copyright © 2014 John Wiley & Sons, Ltd.     

Cause reduction: delta debugging,even without bugs

What is a test case for? Sometimes, to expose a fault. Tests can also exercise code, use memory or time, or produce desired output. Given a desired effect, a test case can be seen as a cause, and its components divided into essential (required for effect) and accidental. Delta debugging is used for removing accidents from failing test cases, producing smaller test cases that are easier to understand. This paper extends delta debugging by simplifying test cases with respect to arbitrary effects, a generalization called cause reduction. Suites produced by cause reduction provide effective quick tests for real‐world programs. For Mozilla's JavaScript engine, the reduced suite is possibly more effective for finding faults. The effectiveness of reduction‐based suites persists through changes to the software, improving coverage by over 500 branches for versions up to 4 months later. Cause reduction has other applications, including improving seeded symbolic execution, where using reduced tests can often double the number of additional branches explored. Copyright © 2015 John Wiley & Sons, Ltd.     

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

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

An approach and tool for measurement of state variable based data-flow test coverage for aspect-oriented programs

ContextData-flow testing approaches have been used for procedural and object-oriented programs, and shown to be effective in detecting faults. However, few such approaches have been evaluated for aspect-oriented programs. In such programs, data-flow interactions can occur between base classes and aspects, which can affect the behavior of both. Faults resulting from such interactions are hard to detect unless the interactions are specifically targeted during testing.ObjectiveThis paper presents an approach and tool implementation for measuring data-flow coverage based on state variables defined in base classes or aspects in AspectJ programs. The paper also reports on an empirical study that compares the cost and effectiveness of data-flow test criteria that are based on state variables with two control-flow criteria.MethodEffectiveness of the criteria was evaluated for various fault types. Cost-effectiveness of test suites that cover all state variable definition-use associations (DUAs) was evaluated for three coverage levels: 100%, 90%, and 80%.ResultsThe effort needed to obtain a test case that achieves data-flow coverage is higher than the effort needed to obtain a test case that covers a block or a branch in an advised class. Covering certain data flow associations requires more effort than for other types of data flow associations. The data-flow test criteria based on state variables of a base-class are in general more effective than control-flow criteria.ConclusionsOverall, it is cost-effective to obtain test suites at the 90% coverage level of data-flow criteria.     

Can fault‐exposure‐potential estimates improve the fault detection abilities of test suites?

Code‐coverage‐based test data adequacy criteria typically treat all coverable code elements (such as statements, basic blocks or outcomes of decisions) as equal. In practice, however, the probability that a test case can expose a fault in a code element varies: some faults are more easily revealed than others. Thus, several researchers have suggested that if one could estimate the probability that a fault in a code element will cause a failure, one could use this estimate to determine the number of executions of a code element that are required to achieve a certain level of confidence in that element's correctness. This estimate, in turn, could be used to improve the fault‐detection effectiveness of test suites and help testers distribute testing resources more effectively. This conjecture is intriguing; however, like many such conjectures it has never been directly examined empirically. If empirical evidence were to support this conjecture, it would motivate further research into methodologies for obtaining fault‐exposure‐potential estimates and incorporating them into test data adequacy criteria. This paper reports the results of experiments conducted to investigate the effects of incorporating an estimate of fault‐exposure probability into the statement coverage test data adequacy criterion. The results of these experiments, however, ran contrary to the conjectures of previous researchers. Although incorporation of the estimates did produce statistically significant increases in the fault‐detection effectiveness of test suites, these increases were quite small, suggesting that the approach might not be able to produce the gains hoped for and might not be worth the cost of its employment. Copyright © 2002 John Wiley & Sons, Ltd.     

Comprehensive analysis of FBD test coverage criteria using mutants

Function block diagram (FBD), a graphical modeling language for programmable logic controllers, has been widely used to implement safety critical system software such as nuclear reactor protection systems. With the growing importance of structural testing for FBD models, structural test coverage criteria for FBD models have been proposed and evaluated using mutation analysis in our previous work. We extend the previous work by comprehensively analyzing the relationships among fault detection effectiveness, test suite size, and coverage level through several research questions. We generate a large number of test suites achieving an FBD test coverage ranging from 0 to 100 %, and we also generate many artificial faults (i.e. mutants) for the FBD models. Our analysis results show that the fault detection effectiveness of the FBD coverage criteria increases with increasing coverage levels, and the coverage criteria are highly effective at detecting faults in all subject models. Furthermore, the test suites generated with the FBD coverage criteria are more effective and efficient than the randomly generated test suites. The FBD coverage criteria are strong at detecting faults in Boolean edges, while relatively weak at detecting wrong constants in FBD models. Empirical knowledge regarding our experiments provide the validity of using the FBD coverage criteria, and therefore, of FBD model-based testing.     

CONTROL LAW FOR QUADRATIC STABILIZATION OF PERTURBED FUZZY TIME‐DELAY LARGE‐SCALE SYSTEMS VIA LMI

In this paper, the perturbed continuous‐time large‐scale system with time delays is represented by an equivalent Takagi‐Sugeno type fuzzy model. First, two types of decentralized state feedback controllers are considered in this paper. Based on the Riccati‐type inequality, the Razumikhin theorem, and the delay‐dependent Lyapunov functional approach, some controller design approaches are proposed to stabilize the whole fuzzy time‐delay system asymptotically. In these design methods, both the delay‐independent and delay‐dependent stabilization criteria are derived. By Schur complement, these sufficient conditions can be easily transformed into the problem of LMI's. Moreover, the systems with all the time‐delays τ^l_ij (t) are the same for all rules (i.e., τ^l_ij (t) = τ^m_ij (t) = τ_ij for all l =m); the authors also propose a simpler and less conservative stabilizing criteria. A numerical example is given to illustrate the control design and its effectiveness.     

一种基于粒子群优化的成对组合测试算法框架

提出一种基于粒子群优化的成对组合测试用例集生成算法框架.在生成测试用例时,该框架采用粒子群优化尝试生成强组合覆盖能力的测试用例,并研究了搜索空间、适应值函数和启发式的合理设定;在构造组合测试用例集时,以上述测试用例生成算法为基础,提出两种策略:一种基于one-test-at-a-time,另一种基于类IPO.编程实现该算法框架,并通过实证研究分析了算法框架中不同设定对组合测试用例集规模的影响;最后,与现有的经典方法在组合测试用例集生成规模和算法执行时间上进行了比较.最终结果表明,该算法具有竞争力.     

Timing analysis of scenario‐based specifications using linear programming

Scenario‐based specifications (SBSs), such as UML interaction models, offer an intuitive and visual way of describing design requirements, and are playing an increasingly important role in the design of software systems. This paper presents an approach to timing analysis of SBSs expressed by UML interaction models. The approach considers more general and expressive timing constraints in UML sequence diagrams (SDs), and gives a solution to the reachability analysis, constraint conformance analysis and bounded delay analysis problems, which reduces these problems into linear programs. With the synchronous interpretation of the SD compositions, the timing analysis algorithms in the approach form a decision procedure for a class of SBSs where any loop in any path is time‐independent of the other parts in the path. These algorithms are also a semi‐decision procedure for general SBSs with both the synchronous and asynchronous composition semantics. The approach also supports bounded timing analysis of SBSs, which investigates all the paths in the bound limit one by one, and performs the timing analysis for each finite path by linear programming. A tool prototype has been developed to support this approach. Copyright © 2010 John Wiley & Sons, Ltd.