Spectral test generation for Boolean expressions

Abstract

This paper presents a novel method for testing Boolean expressions. It is based on spectral, aka Fourier analysis of Boolean functions which is exploited to generate test inputs. The approach has three important contributions: (i) It generates a relatively small test suite with a high capability of fault detection, (ii) The test suite is prioritized such that expected fault detection time is shorter, (iii) It is entirely mathematical relying on a simple and straightforward formula. The proposed method is formulated and evaluations are performed on both synthetic and real expressions. It is also compared with two common test generation criteria, MC/DC and Minimal MUMCUT. Evaluations show that the test suite generated by the spectral approach is relatively small while expressing the capability of a better and quicker fault detection. The approach presented in this paper provides a useful insight into how spectral/Fourier analysis of Boolean functions can be exploited in software testing.