Study On The Efficiency Prediction Model For Efsm Test Generation Based On Genetic Programming

With the development of information society, software industry faces a huge progress opportunity, and the same time, the consequences of software errors are increasingly incalculable. As a result, test data generation techniques are paid more attention day by day. The efficiency of test data generation is seen as an important issue in automatic software testing, which can be measured by the cost of test data generation (time required for test generation, or iterations of search algorithm). Extended finite state machine (EFSM) servers as a widely used formal description approach based on states, which can describe the dynamic behavior of software system accurately. Now most researches on EFSM testing have focused on test sequence and test data generate in automation. However,the study on the efficiency of test generation is still limit.In this thesis, we try to construct a prediction model with respect to EFSMs to forecast the efficiency of test generation by using genetic programming, on the basis of the non-linear relationship between efficiency of test generation and its influence factors on the paths. Specifically, according to the feasible transition paths of EFSMs under test, the efficiency of test generation is measured by test generation cost, and regarded as a dependent variable. The influence factors on the efficiency are taken as independent variables, and genetic programming (GP) is used to build a prediction model to forecast the efficiency of test generation for EFSMs.In order to evaluate the predictive ability of our prediction model, the empirical studies are conducted on 8 EFSMs and corresponding predictive ability is analysis in detailed. The predictive abilities of created models are compared between standard genetic programming (SGP) and multi-gene genetic programming(MGGP) under two cases. One case is that the models are created by using original factors influencing the efficiency of test data generation, and the other case is that the models are built by only employing key factors after eliminating the factors with correlation with the help of principal component analysis. Moreover, the predictive abilities of the models by SGP and MGGP are compared with that of back propagation (BP). The results show that the prediction model built by GP is able to availably predict the efficiency of test generation, and the correlation between the influence factors has not effect on its prediction performance. Furthermore, the predictive ability of model by MGGP is more accurate than by SGP.