PRINCIPLES AND METHODS OF TESTING FINITE-STATE MACHINES - A SURVEY

With advanced computer technology, systems are getting larger to fulfi ll more complicated tasks: however they are also becoming less reliabl e. Consequently, testing is an indispensable part of system design and implementation; yet it has proved to be a formidable task for complex systems. This motivates the study of resting finite state machines to ensure the correct functioning of systems and to discover aspects of their behavior. A finite state machine contains a finite number of sta tes and produces outputs on state transitions after receiving inputs. Finite state machines are widely used to model systems in diverse area s, including sequential circuits, certain types of programs, and more recently, communication protocols. In a testing problem we have a mach ine about which we lack some information; we would like to deduce this information by providing a sequence of inputs to the machine and obse rving the outputs produced. Because of its practical importance and th eoretical interest the problem of testing finite state machines has be en studied in different areas and at various times. The earliest publi shed literature on this topic dates back to the 1950's. Activities in the 1960's and early 1970's were motivated mainly by automata theory a nd sequential circuit resting. The area seemed to have mostly died dow n until a few years ago when the resting problem was resurrected and i s now being studied anew due to its applications to conformance testin g of communication protocols. While some old problems which had been o pen for decades were resolved recently, new concepts and more intrigui ng problems from new applications emerge. We review the fundamental pr oblems in testing finite stare machines and techniques for solving the se problems, tracing progress in the area from its inception to the pr esent and the state of the art. In addition, we discuss extensions of finite stare machines and some other topics related to testing.