Selection of tests for finite state machines

Abstract

It is unaffordable to apply all the possible tests to an implementation in order to assess its correctness. Therefore, it is necessary to select relatively small subsets of tests that an detect as many faults as possible. In this paper we propose different approaches to select the best subset of tests from the original one: all the possible subsets up to a given number of inputs, an intelligent greedy algorithm and several genetic algorithms. In order to de ide how good a test suite is, we apply it to a set of mutants that correspond to small variations of the specification of the system to be developed. The goal is that our algorithms generate test suites that kill as many mutants as possible. We compare the proposed approaches and discuss the obtained results. The whole framework has been fully implemented and the tool is freely available.

Habitualmente no se pueden aplicar todas las posibles pruebas (tests) a una implementación para comprobar su corrección. Por ello, es necesario seleccionar subconjuntos de pruebas relativamente pequeños que permitan detectar el mayor número de errores posible. En este trabajo proponemos diferentes enfoques para seleccionar dichos conjuntos de pruebas. Para determinar la calidad de un conjunto de pruebas, este se aplicará a un grupo de mutantes. Un mutante corresponde a una variación de la especificación del sistema bajo prueba que induce un error en la misma. El objetivo de nuestro trabajo es que los algoritmos propuestos generen conjuntos de pruebas que maten el mayor número de mutantes posible. Comparamos los enfoques propuestos entre los que se consideran todos los posibles subconjuntos dada una cota en las entradas (inputs), un algoritmo devorador inteligente y distintos algoritmos genéticos. Finalmente, discutimos los resultados obtenidos en los experimentos realizados para determinar su efectividad. Todas las propuestas han sido implementadas y la herramienta desarrollada es totalmente libre y accesible.