Learning Finite State Machine Specifications from Test Cases

Up-to-date software systems are often modular and need to be changeable. While modularity is believed to reduce software production costs, it also leads to increased difficulty in testing, as the future uses of a module are getting more varied and therefore harder to guess. Also, reused modules are often represented as black boxes, whose interior structure is hidden from the system. In consequence, on reusing a module, the testing focuses on integration testing and monitoring the interfaces of the module. <br> In order to monitor a system, a model of the system is needed to compare the observed traces to. However, with the advent of agile development methods and decreasing time to market, formal models of a system are seldom available. While formal modeling has not been widely adopted in industry, the importance of testing has increased, in part thanks to the same agile development methods that obsolete explicit modeling. An example is the test first paradigm of eXtreme Programming, which requires that the tests for any software have to be written before the software itself. Therefore, test cases are available even for systems without a formal model. <br> In consequence, we propose to generate a system model suitable for monitoring from a test suite for the system. The approach is based on automata learning. Angluin&#180;s learning algorithm is used to generate an appropriate model, while state-merging methods are applied to represent the test cases in a format that can be processed by the learning algorithm. <br> Both Angluin&#180;s algorithm and state-merging are tailored to the characteristics of testing. For Angluin&#180;s algorithm, this comprises a mapping of the query mechanisms onto a test suite. The state-merging is used to construct a generic representation of arbitrary test suites by exploiting the properties of a given test specification language for a better coverage. The approach is implemented in a prototypical tool and validated by a case study.