Deriving adaptive distinguishing sequences for Finite State Machines

Abstract

FSM (Finite State Machines) are widely used for deriving tests with guaranteed fault coverage for control systems. Distinguishing sequences (DS) are used in FSM based testing for state identification and can significantly reduce the size of a returned complete test suite. In some cases, length of distinguishing sequence can be exponential with respect to the size of the FSM specification. Moreover, DS can be even longer for non-deterministic FSMs, which are used for the specification optionality description when deriving tests for real systems. Unfortunately, DS not always exist for deterministic and non-deterministic FSMs. Adaptive DS (or corresponding distinguishing test cases (DTC)) are known to exist more often and be much shorter than the preset ones that makes adaptive DS attractive for test derivation. In this paper, we investigate the properties of adaptive DS and propose an approach for optimizing the procedure for the adaptive DS derivation. For this purpose, we propose to limit the height of a DTC and correspondingly to reduce the size of a distinguishing FSM that is used for the DTC derivation in the original procedure. The efficiency of a proposed optimized procedure is evaluated by computer experiments for randomly generated FSMs up to 100 states. We also present the experimental results on checking the percentage of randomly generated FSMs when a DTC exists.