Automated EFSM-Based Test Data Generation With Multi-Population Genetic Algorithm

With the development of information science and computational science, the related software industry has been becoming a booming industry. Meanwhile, more and more people pay attention to software quality and reliability. Software testing is an indispensable part in the software development life cycle. It can find the bugs and defects of software, and make sure the quality and reliability of software. However, time-consuming and complexity in the software testing is still a challenging. In order to further reduce the cost of software testing in the aspect of manpower and materials, and improve the quality and efficiency of software development, automatic software testing has been widely used in this field.Extended Finite State Machine is an extension of Finite State Machine. It not only includes the basic elements of FSM, but also adds some new characteristics like variables, precondition and some triggered operations by transition. EFSM can precisely represent many complex actions of the software system, and it is already widely used in software specification. Therefore, there is great practical value and theoretical significance in studying the method that automatically generates test data for EFSM models. With heuristic search algorithms widely used in software testing, some research achievements have been got by utilizing search algorithm to automatically generate test data for EFSM model. Multi-Population Genetic Algorithm (MPGA) is a novel parallel search algorithm. Multiple subpopulations are permitted to evolve concurrently and some individuals are allowed to migrate from one subpopulation to another, which can improve the efficiency of search.Therefore, for EFSM model, according to the paths of EFSM model a test data generation method is proposed in this paper, using MPGA to automatically generate test data. On this basis, this paper also empirically studies the impact of parameters used in MPGA on the test generation efficiency, especially size of population, migration interval, migration rate and migration policy. After that, a simple’rules of thumb’approach is applied to find an optimal parameter setting of MPGA on test data generation for EFSM models, and several experiments are conducted. The experimental results suggest that MPGA can effectively generate test data for EFSM models, and it is obviously superior to the Single-Population Genetic Algorithm (GA) in the test generation for EFSM models. The optimal parameters setting obtained by’rules of thumb’can effectively improve the efficiency of test data automatic generation for EFSM models. Furthermore, it may lay a foundation for further exploring the test data automatic generation based on MPGA.