Optimization For Test Case Prioritization

Search-based techniques have been widely used in test case optimization area, which includes three main aspects:test case prioritization, test case selection and test suite minimization. Test case prioritization aims to find the best execution order of test case set. Compared with the other two, test case prioritization will not omit important test cases, which makes it has high flexibility and adaptability, so that it gains more and more focus. Test case prioritization is an NP-hard problem, which is usually solved with genetic algorithm. The industry requirements amend the improvement on effectiveness and efficiency of the algorithm:on the aspect of effectiveness, no researchers have adapted genetic algorithm according to the characteristics of test case prioritization, where there is much room to improve; on the aspect of efficiency, the time genetic algorithm consuming is too much to make it possible for the industrial usage of test case prioritization. This article aims to solve the two problems above and proposed two optimization strategies from algorithm optimization and engineering optimization.In the optimization of algorithm, the execution of previous test cases will suppress the attribution of the following test cases to test targets, which is similar with epistatic genes in biology. After analyzing on test case prioritization, this article proposed an epistatic model for this problem, where Epistatic Test Case Segment is defined. Based on the definition, this paper proposed an epistatic genetic algorithm, which consist of two epistasis-based crossover operators. In empirical studies, the proposed epistatic genetic algorithm outperformed a genetic which evolved an advanced crossover operator on efficiency and effectiveness.In the optimization of engineering, this paper proposed a parallel framework based on GPU, an advanced parallel platform. This platform focuses on the research of parallel to crossover operator and fitness function, which ends up with three different parallel strategies. The empirical studies prove that, the proposed parallel framework gains much improvement on efficiency. And for V8, an industry program with 60 thousand source lines of code, the speedup rate of the parallel framework achieves to 30 times. Based on the code, an open source tool is developed and is available online.The two proposed optimization strategies for test case prioritization in this paper is compatible, which make up the optimization frame for test case prioritization. This optimization framework attributes to the industry usage of test case prioritization.