论文部分内容阅读
Test case generation is an integral aspect of any effective software debugging process.Manual test case generation is error-prone and expensive.Therefore automatic test case generation has been widely used to improve efficiency and effectiveness of software test.Various methods have been proposed for automatic test case generation.However,automatic generation of test cases with higher coverage is still one of the challenges faced by structural testing of software.To address this problem,this paper proposed two new methods which use Monte Carlo Tree Search（MCTS）and Parallel Monte Carlo Tree Search（PMCTS）for test case generation.Our methods can maximize branch coverage of derived test cases within the available test resources.The main work of this paper is summarized as follows:（1）A MCTS method（M-TCG）is proposed to formulate test case generation problem as a tree exploration problem and then utilizes MCTS for heuristically searching the optimal test cases.Tree policy is explored in constructing simulated test case generation tree.To evaluate the effectiveness and efficiency of MCTS method,comparative experiments were conducted based on 17 projects with 66 non trivial Java classes from SF110 corpus and other benchmarks.Experiment results indicate that the proposed MCTS method improved average branch coverage by 2.1% compared with Dyna MOSA which is a state-of-the-art evolutionary technique.Our method also decreased memory consumption by 4% compared with the existing adaptive a Dyna MOSA approach.（2）We proposed PMCTS method（PM-TCG）which extends M-TCG method for automatic test case generation.Since computational cost for constructing the search tree in rollouts of MCTS is expensive,PMCTS method can further improve its effectiveness by formulating the test case generation problem as a parallel tree exploration problem and then uses PMCTS for heuristically searching the optimal test cases.Experiments were conducted on the subject programs used in the MCTS method.Experimental results show that our new method can improve 5.1% average branch coverage and decrease 4% memory consumption compared with Dyna MOSA and a Dyna MOSA,Hence,PMCTS method improved MCTS method by 3%average branch coverage with no decrease in the statistical significant memory usage.（3）A prototype system was designed and implemented.Based on the implementation of above algorithms,an experiment prototype system for automatic test case generation is developed and the effectiveness of the proposed methods is verified by evaluation experiments.The system automatically executes the input program and outputs test cases by specified method.