Fourier analysis-based testing of finite state machines

Abstract

Finite State Machine (FSM), as a formal modeling technique to represent both circuits and software, has been widely used in testing. FSM testing is a well-studied subject and there are several test generation methods. However, the current increase in the demand for pervasive and safety critical systems as well as the increase in software size calls for more rigorous methods that can produce more effective test suites particularly in terms of size, time spent for test generation and fault detection ratio. In this study, we propose a new test generation method based on the Fourier analysis of Boolean functions. An analysis on the effects of the various frequency components of the function output allow us to generate test suites with better performance characteristics. We compare our F-method with the two existing methods.