$\mathcal k$-branching uio sequences for partially specified observable non-deterministic fsms
Khaled El‐Fakih, Robert M. Hierons, Uraz Cengiz Türker · IEEE Transactions on Software Engineering · 2020
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 ofUIOsto 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${\mathcal K}$-UIOs:UIOsthat lead to at most${\mathcal K}$output sequences from states of$M$. We show that checking${\mathcal K}$-UIOexistence 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${\mathcal K}$-UIOsand the results of experiments on randomly generated and real FSM specifications. The proposed algorithm was able to constructUIOsin cases where the existingUIOgeneration algorithm could not and was able to constructUIOsfrom FSMs with 38K states and 400K transitions.