Incremental and Heuristic Approaches for Deriving Adaptive Distinguishing Test Cases for Non-deterministic Finite-State Machines
Khaled El‐Fakih, Nina Vladimirovna Yevtushenko, Ayat Saleh · The Computer Journal · 2018
An incremental approach is proposed for deriving an adaptive Distinguishing Test Case (DTC) for a subset of states of an observable non-deterministic Finite-State Machine (FSM). The approach considers the states of the subset incrementally while checking the existence of a DTC. Experiments were conducted to assess and compare various versions of the incremental approach with respect to a non-incremental counterpart. In addition, two implementations of an efficient heuristic approach for the considered problem are proposed. The implementations are based on a special traversal of a successor tree up to certain height using some established construction rules. Experiments were conducted to assess the execution time and quality of obtained solutions for large FSMs. Moreover, we determine how often a DTC exists while varying the number of states, outputs and non-determinism of a given FSM. A complete summary of the obtained results is included.