Generating Reduced Tests for FSMs using a Search-Based Testing Approach

Ideally, in FSM-based testing, a test suite should have as few input symbols and sequences as possible, speeding up its execution, and being able to reveal as many faulty implementations as possible in a given fault domain. Unfortunately, in general, it is an NP-hard problem. Several test generation methods have been proposed to generate a test suite with full fault detection capability. However, they usually generate large test suites with many sequences. In this paper, we propose a search-based software testing method aiming to generate test suites that represent a good trade-off between its cost and its fault coverage. A new encoding, called Node-depth-outdegree Encoding (NDOE) and its mutation and initialization operators are proposed. Also, a new fitness function is presented. The proposed fitness is composed of three objectives: minimize the test suite length, minimize the number of test sequences, and maximize the fault coverage, which analysis is based on mutation score. The experimental results show that the proposed method is able to generate lower cost test suites, with high mutation score, than literature test generation methods.