Search-based Test Case Prioritization Technology Optimization Research

Regression test is a crucial process to guarantee the software quality,but regression testing is a time-consuming process that may seriously affect the software development when you need to modify the software at a high frequency.Test case prioritization(TCP)is one of the important optimization technologies in regression testing.Compared with Test Case Selection(TCS)and Test Suite Minimization(TSM),TCP has higher possible to find the hidden faults than TCS and TSM.In TCP,the global best test case execution sequence set should be found for testing,so search-based technique has been used in this area,since the search space is all the possibility permutation,which is an NP-complete problem.Meanwhile,with the improvement of the industrial requirement in improving quality and efficiency in software testing,multi-objective optimization has been invited to TCP process.The main research question in this thesis is optimizing search-based techniques for both single-objective and multi-objective algorithm in TCP.So the main contributions and research results of the work can be summarized as follows:1.CPU+GPU-based algorithm optimization in TCP.With the increasing of software scale and test case scale,there are some new challenges have been put forward for TCP and optimization algorithms.In this thesis,a novel CPU+GPU TCP framework has been presented based on the potential parallelism of meta-heuristic algorithm.With the assistance of Graphics Processing Unit(GPU)to optimize algorithms with parallelization,TCP algorithms can achieve similar efficiency as multi-core servers but with rather lower cost.In this paper,CPU+GPU-based framework has been used to accelerate algorithm for Multi-objective TCP problem.(1)Fitness function parallelization strategy has been illustrated as it is the most time-consuming operation in evolution process,and a novel approach has been used to parallel accelerating this operation.(2)For crossover operation,both fine-grained and coarse-grained parallel crossover have been compared in experiments,and the best crossover has been summarized for TCP algorithms.(3)Because of the difference of memory address in CPU and GPU,different parallelization frameworks have been discussed for different scale of subjects under test.For the three research questions above,experiments have been designed for comparing different parallel structures and the best parallel structure has been found for TCP algorithms.2.Epistatsis-based algorithm optimization research.Genetic algorithm based evolution computation algorithms are all based on the Darwinian evolution theory and genetic theory,but nowadays the related evolution algorithms are all seldom optimized based on those theory.Epistasis theory reflects the correlation between genes in evolution process.In TCP,Epistatic Test case Segment(ETS)that based on epistasis theory can be used to express the dependency between genes and to guide to optimize meta-heuristic algorithms in the evolution process.(1)Based on the guide of ETS,single-point crossover and order crossover have been improved for meta-heuristic algorithm.And individual generation results showed that the changing of original individuals should be in an appropriate range for the better effectiveness.(2)Compared with the state-of-the-art crossover operation,it has been proved that the improvement of ETS-based crossover can achieve better results for both single-objective and multi-objective TCP.3.Self-adapting-based search algorithm for TCP researchIn Multi-objective TCP(MoTCP)area,a wide variety of search algorithms and strategies has been proposed to optimize test case sequences.And different algorithms or strategies have different implementation cost,and each algorithm or strategy usually performs with high effectiveness and efficiency in one specific situation.To address this problem for the different test scenarios,an algorithm using hyper-heuristic strategy is proposed to adjust algorithms for search-based TCP dynamically.(1)In this paper,based on the research on the different type of Multi-objective optimization algorithm,low-level hyper-heuristic algorithm has been structured for dynamic algorithm selection.(2)A novel evaluation function has been proposed for evaluating different multi-objective algorithm based on the feedback results for subjects under test.(3)Construct the hyper-heuristic based algorithm dynamic selection framework for MoTCP.At last,experiments showed that for different subjects our framework that can always achieve rather better results.Based on the research on above,TCP has been optimized in three aspects.In the hardware level,advanced heterogeneous parallel computing has been used to improve the efficiency of the search technology in TCP for the industrial applications.In the theoretical aspects,epistasis theory has been used to improve the effectiveness of operations in meta-heuristic algorithm for TCP.Finally,a hyper-heuristic search algorithm framework has been constructed for TCP algorithm selection problem,which can significantly improve the effectiveness and efficiency of TCP process.