Passive fault detection for FSM and EFSM models

Abstract

Passive fault detection is a fundamental part of passive testing which determines whether a system under test (SUT) is faulty by observing the input/output behaviors of the SUT without interfering with its normal operations. This thesis focuses on passive fault detection for SUTs whose specifications are given in finite state machine (FSM) and extended finite state machine (EFSM) models, and proposes a new approach to FSM and EFSM-based passive fault detection. Compared with previous approaches for FSM-based passive fault detection based on the approach in [Lee97], this proposed approach for FSM-based passive fault detection has better performance with respect to computational complexity and provides more information about possible starting state and possible trace during the passive fault detection without the need for additional post-processing. We analyzed the worst case time complexity of the algorithms and gave results of experiments to estimate the average case time complexity of these algorithms. This proposed approach for EFSM-based passive fault detection is derived from the proposed approach for FSM-based passive fault detection. It also provides information about possible starting state and possible trace at the end of passive fault detection; and utilizes a Hybrid method which combines the use of both Interval Refinement and Simplex methods for performance improvement during passive fault detection. Through experiments, we show that, compared with using only the Interval Refinement method or only the Simplex method, the Hybrid method guarantees the correctness of results with a reasonable time cost.