Deriving adaptive checking sequence for nondeterministic Finite State Machines

The derivation of checking sequences for Finite State Machines (FSMs) has a long history. There are many papers devoted to deriving a checking sequence that can distinguish a complete deterministic specification FSM from any non-equivalent FSM with the same number of states. To the best of our knowledge, for nondeterministic FSMs, the topic appeared only recently; the authors started with preset checking sequences for FSMs where the initial state is still known but the reset is very expensive. In this paper, a technique is proposed for deriving an adaptive checking sequence for a complete nondeterministic finite state machine with respect to the reduction relation. The main contribution of the paper is the use of a (adaptive) distinguishing test case instead of a separating sequence. Such a test case is usually shorter that a separating sequence (when it exists) and can exist when there is no separating sequence. We also discuss the possibilities of using adaptive transfer sequences instead of deterministic transfer sequences that also allows to extend the set of FSMs for which the strategy can be used and reduce the length of a checking sequence. The application of a proposed strategy to partial possibly nondeterministic FSMs is briefly discussed.

nondeterministic Finite State Machines (FSM), reduction relation, fault model, test derivation, adaptive checking sequences

1. Kohavi Z. Switching and Finite Automata Theory, McGraw-Hill, New York, 1978.

2. Chow T.S.. “Testing software Design Modelled by Finite State Machines”, In IEEE Trans. Software Eng. Vol. 4 (3), 1978, pp. 178-187.

3. Dorofeeva R., El-Fakih K., Maag S., Cavalli A., Yevtushenko N. “FSM-based conformance testing methods: A survey annotated with experimental evaluation”, In Information & Software Technology, Vol. 52 (12), 2010, pp. 1286-1297.

4. Hennie F.C. “Fault-Detecting Experiments for Sequential Circuits”, In Proc. Fifth Ann. Symp. Switching Circuit Theory and Logical Design, 1964, pp. 95-110.

5. Petrenko A., Simão A., Yevtushenko N. “Generating Checking Sequences for Nondeterministic Finite State Machines”, In Proceedings of the ICST, 2012, pp. 310-319.

6. Zhigulin M., Kolomeez A., Kushik N., Shabaldin A... “EFSM based testing a software implementation of IRC protocol”, In Izvestia Tomskogo polytechnicheskogo instituta [Bulletin of the Tomsk Polytechnic University], 318 (5), 2011, pp. 81-84 (in Russian).

7. Petrenko A., Simão A.. “Generalizing the DS-Methods for Testing Non-Deterministic FSMs”, In Comput. J. 58(7), 2015, pp. 1656-1672.

8. Ermakov A.. “Deriving checking sequences for nondeterministic FSMs”, In Proceedings of the Institute for System Programming of RAS, Vol. 26, 2014, pp. 111-124 (in Russian).

9. Alur R., Courcoubetis C., Yannakakis M.. “Distinguishing tests for nondeterministic and probabilistic machines”, In Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, 1995, pp. 363-372.

10. Kushik N., El-Fakih K., Yevtushenko N. ”Adaptive Homing and Distinguishing Experiments for Nondeterministic Finite State Machines”, In Lecture Notes in Computer Science, Vol. 8254, 2013, pp. 33-48.

11. Petrenko A., Yevtushenko N.. “Conformance Tests as Checking Experiments for Partial Nondeterministic FSM”, In Lecture Notes in Computer Science, Vol. 3997, 2005, pp. 118-133.

12. Petrenko A., Yevtushenko N.. “Adaptive Testing of Deterministic Implementations Specified by Nondeterministic FSMs”, In Lecture Notes in Computer Science, Vol. 7019, 2011, pp. 162-178.

13. Kushik N.. Methods for deriving homing and distinguishing experiments for nondeterministic FSMs. PhD thesis, Tomsk State University, 2013 (in Russian).

14. Shabaldina N., El-Fakih K., Yevtushenko N. “Testing Nondeterministic Finite State Machines with Respect to the Separability Relation”, In Proceedings of Intern. Conf. on Testing Systems and Software (ICTSS/FATYES), 2007, pp. 305-318.

15. Vetrova M. FSM based methods for compensator design and testing. PhD thesis, Tomsk State University, 2004 (in Russian).

16. Yevtushenko N., Kushik N. Decreasing the length of Adaptive Distinguishing Experiments for Nondeterministic Merging-free Finite State Machines / // Proceedings of IEEE East-West Design & Test Symposium, pp.338 – 341.

17. Güniçen C., Inan K., Türker U.C., Yenigün H. “The relation between preset distinguishing sequences and synchronizing sequences”, In Formal Aspects of Computing, Vol. 26 (6), 2014, pp. 1153–1167.

18. Kushik N., Yevtushenko N., Yenigun H. “Reducing the complexity of checking the existence and derivation of adaptive synchronizing experiments for nondeterministic FSMs”, In Proceedings of International Workshop on Domain Specific Model-based Approaches to Verification and Validation (AMARETTO’2016), 2016, pp. 83-90.