Conformance testing

In this chapter we tackle the problem of conformance testing between finite state machines. The problem can be briefly described as follows. Given a finite state machine M_S which acts as specification and for which we know its transition diagram, and another finite state machine M_I which is the alleged implementation and for which we can only observe its behavior, we want to test whether M_I correctly implements or conforms M_S. Although FSM notation is simple, conformance testing for FSMs is very useful in practice. FSMs have been widely used to directly specify many types of systems, including protocols, embedded control systems and digital circuits. Moreover, many formal notations are very similar to finite state machines, or use FSMs to specify some parts of the systems. Such notations include StateCharts, SDL for communication protocols, UML state diagrams and ASM for software, and StateFlow and SCR for reactive systems. Note that many control or reactive systems are described by an infinite set of states and infinite transitions. However, it is often possible to extract for such systems a system part or a particular system behavior or interaction with the environment, which can be modeled by a finite state machine. In many case this can be done through an abstraction process that allows the designer to ignore some details and focus on the finite part of the system interaction with the environment. This finite part of the specification can be used to derive tests and to test the whole system. To apply these tests to the complete system, we have to assume that we know the input and output finite vocabulary, and that the system produces a response to an input signal within a known, finite amount of time. A state of the system can be defined as a stable condition in which it has produced the expected output and is waiting for a new input. A transition is defined as the consumption of an input, the generation of an output, and the possible move to a new state. In this chapter we consider only deterministic systems, i.e. that produce the outputs and move to the next state in a deterministic way.