On the application of combination strategies to testing finite state machines.

Abstract

This work presents a novel application of combination strategies to the testing of software modeled by finite state machines. Given a set of system parameters and possible values for those parameters, combination strategies have traditionally been used to develop reasonably sized test sets consisting of combinations of parameters values. A finite state machine however consists of sequences in addition to discrete combinations of parameters values. By applying combination strategies to the sequences themselves, we address the problem of software errors caused by conditions built up by the history of the previous states. We show here that combination strategies derived from group and field theory, specifically Galois fields leading to the development of orthogonal Latin squares, in addition to combinatorial methods, provide strong tools for testing finite state machines. The results of an empirical experiment comparing the different strategies in testing a finite state machine in safety-critical code showed excellent efficacy in finding software errors in actual practice. Software faults were introduced into the previously tested and debugged code by a third party. Two of the combination strategies taken together not only found all of the introduced faults but revealed some software faults that had been previously overlooked.