Automatic learning of state machines for fault detection systems in discrete event based distributed systems

Abstract: The electronic components in modern automobiles build up a distributed system with so called electronic control units connected via bus systems. As more safety- and security-relevant functions are implemented in such systems, the more important fault detection becomes. A promising approach to fault detection is to build a system model from state machines and compare its predictions with properties observed in a real system. In the automobile, potential are communication characteristics between the distributed control units. Especially, the sequence of transmitted messages can be used as the basis for supervising the communication. This thesis investigates if data gathered during system tests can be used to create state-machine system models. Such an automatically created model reflects the observed normal system behavior and can potentially be used for fault detection purposes. The task can be seen as learning a state machine from a single long message sequence. Today’s automata learning algorithms are not designed for such singlemessage- sequence input data. Especially, learning without interaction between the original system and the learning algorithm is in general a NPcomplete task. Additionally, if only positive data from the normal behaving system is available, the task is further complicated. The well-known Angluin’s L∗ state-machine learning algorithm works in general independent from the type of input data. In order for this algorithm to be applicable, certain queries have to be answered. This work proposes a statistical approach to answer such queries. The implemented adapted Angluin algorithm showed the potential of automatic model building in fault detection systems and, in particular, the possibility of learning state machines from a single positive data stream.