Automated EFSM-based Test Case Generation With Scatter Search

Software testing is an important phase of the software development life cycle. It is an important way to guarantee software quality and reliability. A challenging task of software testing entails test case generation, whose cost can be reduced by means of the use of techniques for automating this task. A typical approach used for automated test case generation is to create a model of the software and employ the model to generate test cases. Finite State Machine (FSM) and Extended Finite State Machine (EFSM) are among the popular models for representing system specifications. An EFSM model is an enhanced model based on FSM. It essentially comprises states, variables and transitions among states. And it can represent many complex systems containing both control and data parts, whereas an EFM only can model the control part of a system. However, automated test data generation from an EFSM model is still a challenging task due to two main problems:the path feasibility and path test data generation.In recent years, some meta-heuristic search algorithms have been gradually applied to automatic generation of test cases, such as genetic algorithm, simulated annealing and tabu search algorithm etc. Scatter search is one of meta-heuristic search techniques based on a population of solutions, called Reference Set, for the purpose of new trial solution generation. Scatter search has been compared with genetic algorithm in some problem, and it has been shown to have high quality in fewer evaluations than genetic algorithm. In addition, scatter search is more similar to a template search algorithm, which is basically composed of five methods. Each method can be customized or optimized based on the problem to be solved, so scatter search has high flexibility and scalability.In this paper, we introduce scatter search to generate test cases for given transition paths of an EFSM model. Each solution explored by scatter search is encoded as sequence of input variable values of the EFSM model. A novel feature of our method is using an executable EFSM model to provide run-time feedback to guide the search process. The executable model receives a transition path and the initial input variable values as inputs, and returns the coverage information of the given transition path as the expected outputs. Furthermore, the expected outputs associated with test data are also collected to construct the test oracle automatically. Finally, test data and test oracles are combined into complete test cases. Scatter search is compared with genetic algorithm and random algorithm. The experimental results show that our approach has much better effectiveness and efficiency.