[Formula Omitted]-Branching UIO Sequences for Partially Specified Observable Non-Deterministic FSMs

• Published in: IEEE transactions on software engineering 2021-01, Vol.47 (5), p.1029
• Main Authors: El-Fakih, Khaled, Hierons, Robert M, Uraz Cengiz Turker
• Format: Article
• Language: English
• Subjects: Algorithms; Finite state machines; Input output
• ISSN: 0098-5589; 1939-3520
• DOI: 10.1109/TSE.2019.2911076

In black-box testing, test sequences may be constructed from systems modelled as deterministic finite-state machines (DFSMs) or, more generally, observable non-deterministic finite state machines (ONFSMs). Test sequences usually contain state identification sequences, with unique input output sequences ( UIOs ) often being used with DFSMs. This paper extends the notion of UIOs to ONFSMs. One challenge is that, as a result of non-determinism, the application of an input sequence can lead to exponentially many expected output sequences. To address this scalability problem, we introduce [Formula Omitted]- UIOs : UIOs that lead to at most [Formula Omitted] output sequences from states of [Formula Omitted]. We show that checking [Formula Omitted]- UIO existence is PSPACE-Complete if the problem is suitably bounded; otherwise it is in EXPSPACE and PSPACE-Hard. We provide a massively parallel algorithm for constructing [Formula Omitted]- UIOs and the results of experiments on randomly generated and real FSM specifications. The proposed algorithm was able to construct UIOs in cases where the existing UIO generation algorithm could not and was able to construct UIOs from FSMs with 38K states and 400K transitions.