Incremental and Heuristic Approaches for Deriving Adaptive Distinguishing Test Cases for Non-deterministic Finite-State Machines

作     者：El-Fakih, Khaled Yevtushenko, Nina Saleh, Ayat 

作者机构：Amer Univ Sharjah Sharjah U Arab Emirates RAS Inst Syst Programming Moscow Russia 

出 版 物：《COMPUTER JOURNAL》 (计算机杂志)

年 卷 期：2019年第62卷第5期

页      面：757-768页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：AUS-FRG17-R-27 

主　　题：adaptive distinguishing experiments non-deterministic finite-state machines finite-state machine-based testing 

摘      要：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.