Efficient minimization of homogeneous FSMs for fault diagnosis

Abstract

On the base of the Finite State Machine (FSM) model, the fault diagnosis problem deals with the identification of a faulty implementation against its specification represented by an FSM. In particular, to efficiently identify potential faulty implementations caused by a transfer error in an FSM, cross-verification over the FSM is performed after all potential faulty FSMs have been minimized. Existing minimization algorithms become inefficient due to the lack of taking advantage of the homogeneity of these potential faulty FSMs. In this paper, we propose a two-phase algorithm for the efficient and simultaneous minimization of a set of homogeneous faulty FSMs. Disregarding the suspicious transition, the first phase of the algorithm performs minimization of these faulty FSMs via a common digraph of th FSMs. These faulty FSMs are considered minimized if the distinguishing sequences of all state-pairs can be discovered from the common digraph. Otherwise, the algorithm in the second phase performs minimization for each faulty FSM by individually restoring its corresponding unexpected transition in the reduced common digraph. To demonstrate the efficiency of the two-phase algorithm, we carried out experiments on a number of realistic protocol specifications, including the Alternation Bit Protocol (ABP), Transport Protocol Class 4 (TP4), and ISDN Basic Rate Interface (BRI) protocol. Experimental results show that the algorithm renders the minimization complexity greatly reduced for most of the realistic protocol FSMs.