Improvements in finite state machines

Official URL: http://risc01.sabanciuniv.edu/record=b1558939 (Table of Contents)

Finite State Machine (FSM) based testing methods have a history of over half a century, starting in 1956 with the works on machine identi cation. This was then followed by works checking the conformance of a given implementation to a given speci cation. When it is possible to identify the states of an FSM using an appropriate input sequence, it's been long known that it is possible to generate a Fault Detection Experiment with fault coverage with respect to a certain fault model in polynomial time. In this thesis, we investigate two notions of fault detection sequences; Checking Sequence (CS), Checking Experiment (CE). Since a fault detection sequence (either a CS or a CE) is constructed once but used many times, the importance of having short fault detection sequences is obvious and hence recent works in this eld aim to generate shorter fault detection sequences. In this thesis, we rst investigate a strategy and related problems to reduce the length of a CS. A CS consists several components such as Reset Sequences and State Identi - cation Sequences. All works assume that for a given FSM, a reset sequence and a state identi cation sequence are also given together with the speci cation FSM M. Using the given reset and state identi cation sequences, a CS is formed that gives full fault coverage under certain assumptions. In other words, any faulty implementation N can be identi ed by using this test sequence. In the literature, di erent methods for CS construction take di erent approaches to put these components together, with the aim of coming up with a shorter CS incorporating all of these components. One obvious way of keeping the CS short is to keep components short. As the reset sequence and the state identi cation sequence are the biggest components, having short reset and state identi cation sequences is very important as well. It was shown in 1991 that for a given FSM M, shortest reset sequence cannot be computed in polynomial time if P 6≠NP. Recently it was shown that when the FSM has particular type (\monotonic") of transition structure, constructing one of the shortest reset word is polynomial time solvable. However there has been no work on constructing one of the shortest reset word for a monotonic partially speci ed machines. In this thesis, we showed that this problem is NP-hard. On the other hand, in 1994 it was shown that one can check if M has special type of state identi cation sequence (known as an adaptive distinguishing sequence) in polynomial time. The same work also suggests a polynomial time algorithm to construct a state identi cation sequence when one exists. However, this algorithm generates a state identi cation sequence without any particular emphasis on generating a short one. There has been no work on the generation of state identi cation sequences for complete or partial machines after this work. In this thesis, we showed that construction of short state identi cation sequences is NP-complete and NP-hard to approximate. We propose methods of generating short state identi cation sequences and experimentally validate that such state identi cation sequences can reduce the length of fault detection sequences by 29:2% on the average. Another line of research, in this thesis, devoted for reducing the cost of checking experiments. A checking experiment consist of a set of input sequences each of which aim to test di erent properties of the implementation. As in the case of CSs, a large portion of these input sequences contain state identi cation sequences. There are several kinds of state identi cation sequences that are applicable in CEs. In this work, we propose a new kind of state identi cation sequence and show that construction of such sequences are PSPACE-complete. We propose a heuristic and we perform experiments on benchmark FSMs and experimentally show that the proposed notion of state identi cation sequence can reduce the cost of CEs by 65% in the extreme case. Testing distributed architectures is another interesting eld for FSM based fault detection sequence generation. The additional challenge when such distributed architectures are considered is to generate a fault detection sequence which does not pose controllability or observability problem. Although the existing methods again assume that a state identi cation sequence is given using which a fault detection sequence is constructed, there is no work on how to generate a state identi cation sequence which do not have controllability/observability problem itself. In this thesis we investigate the computational complexities to generate such state identi cation sequences and show that no polynomial time algorithm can construct a state identi cation sequence for a given distributed FSM.