Diagnosis of stochastic discrete event systems based on N-gram models with wildcard characters

In this paper, a new approach to the diagnosis of stochastic discrete event system is presented. We are developing a method, called sequence profiling, based on N-gram models. The information necessary for sequence profiling is only event logs from the target system. From event logs in the normal situation, N-gram models are constructed through a simple statistical analysis. Based on the N-gram model, the diagnoser estimates what kind of faults has occurred in the system, or may conclude that no faults occurs. When the target system is a distributed system consisting of several subsystems, event sequences from subsystems may be interleaved and the method cannot separate the event sequence from local event sequences by subsystems. To improve this situation, we introduce the wildcard characters in the short sequences used in the N-grams. This contributes to removing the effect by subsystems which may not be related to faults. Effectiveness of the proposed approach is demonstrated by application to fault diagnosis of a multi-processor system.