Heuristics for deriving distinguishing experiments of nondeterministic finite state machines

Derivation of input sequences for distinguishing states of a finite state machine (FSM) specification is well studied in the context of FSM-based functional testing. We present three heuristics for the derivation of distinguishing sequences for nondeterministic FSM specifications. The first is based on a cost function that guides the derivation process and the second is a genetic algorithm that evolves a population of individuals of possible solutions (or input sequences) using a fitness function and a crossover operator specifically tailored for the considered problem. The third heuristic is a mutation based algorithm that considers a randomly generated input sequence as a candidate solution, and if the candidate is not a distinguishing sequence, then the algorithm tries to find a solution by appropriately mutating the considered candidate. Experiments are conducted to assess the performance of the considered algorithms with respect to execution time, virtual memory consumption, and quality (length) of obtained sequences. Experiments are conducted using randomly generated machines with a various number of states, inputs, outputs, and degrees of non-determinism. Further, we assess the impact of varying the number of states, inputs, outputs, and degree of non-determinism.