K-Branching UIO Sequences for Partially Specified Observable Non-Deterministic FSMs

Abstract

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 K-UIOS: UIOS that lead to at most K output sequences from states of M. We show that checking K-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 K-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.