Test Generation from an Extended Finite State Machine as a Multiobjective Optimization Problem

Extended Finite State Machines are widely used in different phases of software development including software testing. In this Ph.D. dissertation, we argue that test generation from an Extended Finite State Machine (EFSM) can be considered as a multiobjective optimization problem. When a test engineer generates tests from an EFSM he/she typically considers several objectives. We propose a search-based approach to generate test suites from an EFSM, accounting for multiple (potentially conflicting) such objectives. We aim at maximizing coverage of the EFSM test model and maximizing feasibility of the generated test suite so that its test cases can actually execute, while minimizing similarity between these test cases since this has been shown to increase fault detection, as well as minimizing overall cost. Therefore, we have defined a multiobjective genetic algorithm that searches for optimal test suites based on four fitness functions. In doing so, we create an entire test suite at once as opposed to creating a test suite one test case one at a time, which we argue is a suboptimal test suite generation procedure. Our approach is evaluated on different case studies, showing interesting results. We also investigate different ways of improving our solution and analyze impact of those improvements.