In the test case generation process of combinatorial testing, particle swarm optimization (PSO) is widely concerned for its simple implementation and fast convergence rate;however, it often falls into local optimum du...
详细信息
In the test case generation process of combinatorial testing, particle swarm optimization (PSO) is widely concerned for its simple implementation and fast convergence rate;however, it often falls into local optimum due to premature convergence. To attack this problem, a novel adaptive value measurement strategy is adopted by weighing the relationship between current test cases and historical test cases. The test case with the minimum average hamming distance is selected as the optimal test case, and the inertial weight linear differential decrease strategy is developed to ensure better inertial weight in different search stages, further to improve the capability of generating smaller coveringarrays. In addition, we integrate the simulated annealing strategy into the improved PSO to improve the ability of particles jumping out of the local optimum, and an innovative approach for generating a better coveringarray is proposed. Experiments on 16 classical random strength coveringarrays suggest that our approach outperforms six other techniques in terms of effectiveness.
Software behavior depends on many factors. Combinatorial testing (CT) aims to generate small sets of test cases to uncover defects caused by those factors and their interactions. covering array generation, a discrete ...
详细信息
Software behavior depends on many factors. Combinatorial testing (CT) aims to generate small sets of test cases to uncover defects caused by those factors and their interactions. covering array generation, a discrete optimization problem, is the most popular research area in the field of CT. Particle swarm optimization (PSO), an evolutionary search-based heuristic technique, has succeeded in generating coveringarrays that are competitive in size. However, current PSO methods for covering array generation simply round the particle's position to an integer to handle the discrete search space. Moreover, no guidelines are available to effectively set PSOs parameters for this problem. In this paper, we extend the set-based PSO, an existing discrete PSO (DPSO) method, to covering array generation. Two auxiliary strategies (particle reinitialization and additional evaluation of gbest) are proposed to improve performance, and thus a novel DPSO for covering array generation is developed. Guidelines for parameter settings both for conventional PSO (CPSO) and for DPSO are developed systematically here. Discrete extensions of four existing PSO variants are developed, in order to further investigate the effectiveness of DPSO for covering array generation. Experiments show that CPSO can produce better results using the guidelines for parameter settings, and that DPSO can generate smaller coveringarrays than CPSO and other existing evolutionary algorithms. DPSO is a promising improvement on PSO for covering array generation.
Providing a reusable methodology for the evaluation of covering array generation utilities and apply it to a corpus of such tools, obtaining an overview of supported features and constraints, performance, output size,...
详细信息
Providing a reusable methodology for the evaluation of covering array generation utilities and apply it to a corpus of such tools, obtaining an overview of supported features and constraints, performance, output size, file formats, and practical considerations that may ease or hinder *** of supported capabilities, input and output formats, and constraints, followed by an experimental evaluation of eight covering array generation tools, two of which were provided in updated versions, against a corpus of 295 publicly available benchmark models in six categories, producing arrays of strength two to ***, particularly constraint support, vary widely amongst competitors. Metaheuristic algorithms, commonly focused on postoptimization, tend to produce small arrays at the cost of performance. Approaches based on the In-Parameter-Order paradigm offer a good balance between speed and output size that may prove conducive to real-world *** choice of a covering array generation utility should be based on specific requirements related to the use case. Nevertheless, our evaluation identifies some candidates - CAgen, ACTS, and APPTS - which lead the field in terms of overall score. Others, such as PICT, offer unique features;however, a lack of standardization may lead to vendor lock-in.
Context: covering array generation (CAG) is the core task of Combinatorial interaction testing (CIT), which is widely used to discover interaction faults in real-world systems. Considering the universality, constraine...
详细信息
Context: covering array generation (CAG) is the core task of Combinatorial interaction testing (CIT), which is widely used to discover interaction faults in real-world systems. Considering the universality, constrained covering array generation (CCAG) is more in line with the characteristics of applications, and has attracted a lot of researches in the past few years. Objective: In CIT, a coveringarray (CA) with smaller size means lower cost of testing, particularly for the systems where the execution of a test suite is time consuming. As constraints between parameters are ubiquitous in real systems, this work is dedicated to more efficient algorithms for CCAG. Specifically, we aim to develop a heuristic search algorithm for CCAG, which allows generating CAs with smaller size in a limited time when compared with existing algorithms. Method: We propose a weighting local search algorithm named WCA, which makes use of weights associated with the tuples and dynamically adjusts them during the search, helping the algorithm to avoid search stagnation. As far as we know, this is the first weighting local search for solving CCAG. Results: We apply WCA to a wide range of benchmarks, including real-world ones and synthetic ones. The results show that WCA achieves a significant improvement over three state-of-the-art competitors in 2-way and 3-way CCAG, in terms of both effectiveness and efficiency. The importance of weighting is also reflected by the experimental comparison between WCA and its alternative algorithm without the weighting mechanism. Conclusion: WCA is an effective heuristic algorithm for CCAG to obtain smaller CAs efficiently, and the weighting mechanism plays a crucial role.
Combinatorial interaction testing (CIT) is a popular approach to detecting faults in highly configurable software systems. The core task of CIT is to generate a small test suite called a t-way coveringarray (CA), whe...
详细信息
ISBN:
(纸本)9781450355728
Combinatorial interaction testing (CIT) is a popular approach to detecting faults in highly configurable software systems. The core task of CIT is to generate a small test suite called a t-way coveringarray (CA), where t is the covering strength. Many meta-heuristic algorithms have been proposed to solve the constrained coveringarray generating (CCAG) problem. A major drawback of existing algorithms is that they usually need considerable time to obtain a good-quality solution, which hinders the wider applications of such algorithms. We observe that the high time consumption of existing meta-heuristic algorithms for CCAG is mainly due to the procedure of score computation. In this work, we propose a much more efficient method for score computation. The score computation method is applied to a state-of-the-art algorithm TCA, showing significant improvements. The new score computation method opens a way to utilize algorithmic ideas relying on scores which were not affordable previously. We integrate a gradient descent search step to further improve the algorithm, leading to a new algorithm called FastCA. Experiments on a broad range of real-world benchmarks and synthetic benchmarks show that, FastCA significantly outperforms state-of-the-art algorithms for CCAG algorithms, in terms of both the size of obtained coveringarray and the run time.
Context To improve the quality and correctness of a software product it is necessary to test different aspects of the software system. Among different approaches for software testing, combinatorial testing along with ...
详细信息
Context To improve the quality and correctness of a software product it is necessary to test different aspects of the software system. Among different approaches for software testing, combinatorial testing along with coveringarray is a proper testing method. The most challenging problem in combinatorial testing strategies like t-way, is the combinatorial explosion which considers all combinations of input parameters. Many evolutionary and meta heuristic strategies have been proposed to address and mitigate this problem. Objective: Genetic Algorithm (GA) is an evolutionary search-based technique that has been used in t-way interaction testing by different approaches. Although useful, all of these approaches can produce test suite with small interaction strengths (i.e. t <= 6). Additionally, most of them suffer from expensive computations. Even though there are other strategies which use different meta-heuristic algorithms to solve these problems, in this paper, we propose an efficient uniform and variable t-way minimal test suite generation approach to address these problems using GA, called Genetic Strategy (GS). Method: By changing the bit structure and accessing test cases quickly, GS improves performance of the fitness function. These adjustments and reduction of the complexities of GA in the proposed GS decreases the test suite size and increases the speed of test suite generation up to t = 20. Results: To evaluate the efficiency and performance of the proposed GS, various experiments are performed on different set of benchmarks. Experimental results show that not only GS supports higher interaction strengths in comparison with the existing GA-based strategies, but also its supported interaction strength is higher than most of other AI-based and computational-based strategies. Conclusion: Furthermore, experimental results show that GS can compete against the existing (both AI-based and computational-based) strategies in terms of efficiency and performance in mo
暂无评论