Mutation testing from Finite State Machines

Abstract

A finite state machine (FSM) is a mathematical model of computation defined by a finite list of states, inputs and outputs, in which outputs are not only determined by the last input but also by the current state, and so by past inputs. A mutant of a finite state machine is another finite state machine obtained by mutating the first machine. This mutation can consist in changing response of the machine to an input, be it the output or the state to which the machine transitions, or in adding a new state and its corresponding transitions. A test is a sequence of inputs with its corresponding outputs. The main goal of this project is to develop a system that generates mutations of an FSM and applies a series of tests to evaluate their effectiveness at distinguishing the original FSM from its mutants.

Una máquina de estados finita (FSM) es un modelo matemático de computación definido por una lista finita de estados, datos de entrada y datos de salida, en el cual los datos de salida no están determinados unívocamente por el último dato de entrada recibido sino también por el estado actual y, por ello, por los datos de entrada previos. Un mutante de una máquina de estados finita es otra máquina de estados finita obtenida mutando la primera. La mutación puede consistir en alterar la respuesta a un dato de entrada, tanto modificando el estado al que la máquina se desplaza como el dato de salida que genera, o en crear un nuevo estado y sus transiciones correspondientes. Un test es una secuencia de datos de entrada con sus correspondientes datos de salida. El objetivo principal de este proyecto es desarrollar un sistema que genere mutantes de una FSM y les aplique una serie de tests para evaluar su efectividad a la hora de distinguir la FSM original de sus mutantes.