«

»

From Genetic to Bacteriological Algorithms for Mutation-Based Testing

by Benoit Baudry, Franck Fleurey, Jean-Marc Jézéquel, Le Traon Yves
Abstract:
The level of confidence in a software component is often linked to the quality of its test cases. This quality can in turn be evaluated with mutation analysis: faults are injected into the software component (making mutants out of it) to check the proportion of mutants detected (“killed”) by the test cases. But while the generation of basic test cases set is easy, improving its quality may require prohibitive effort. This paper focuses on the issue of automating the test optimization. The application of genetic algorithms looks like an interesting way to solve it. The optimization problem is modeled as follows: a test case can be considered as a predator while a mutant program is analogous to a prey. The aim of the selection process is to generate test cases able to kill as many mutants as possible, starting from an initial set of predators, which is the test cases set provided by the programmer. To overcome disappointing experimentation results, on .Net components and unit Eiffel classes, a slight variation on this idea is studied, no longer at the “animal” level (lions killing zebras) but at the bacteriological level. The bacteriological level indeed better reflects the test case optimization issue: it mainly differs from the genetic one by the introduction of a memorization function and the suppression of the cross over operator. The purpose of the paper is to explain how the genetic algorithms have been adapted to fit with the issue of test optimization. The resulting algorithm differs so much from genetic algorithms that it has been given another name: bacteriological algorithm.
Reference:
From Genetic to Bacteriological Algorithms for Mutation-Based Testing (Benoit Baudry, Franck Fleurey, Jean-Marc Jézéquel, Le Traon Yves), In Software, Testing, Verification & Reliability journal (STVR), volume 15, 2005.
Bibtex Entry:
@article{Baudry05a,
	Abstract = {The level of confidence in a software component is often linked to
	the quality of its test cases. This quality can in turn be evaluated
	with mutation analysis: faults are injected into the software component
	(making mutants out of it) to check the proportion of mutants detected
	("killed") by the test cases. But while the generation of basic test
	cases set is easy, improving its quality may require prohibitive
	effort. This paper focuses on the issue of automating the test optimization.
	The application of genetic algorithms looks like an interesting way
	to solve it. The optimization problem is modeled as follows: a test
	case can be considered as a predator while a mutant program is analogous
	to a prey. The aim of the selection process is to generate test cases
	able to kill as many mutants as possible, starting from an initial
	set of predators, which is the test cases set provided by the programmer.
	To overcome disappointing experimentation results, on .Net components
	and unit Eiffel classes, a slight variation on this idea is studied,
	no longer at the "animal" level (lions killing zebras) but at the
	bacteriological level. The bacteriological level indeed better reflects
	the test case optimization issue: it mainly differs from the genetic
	one by the introduction of a memorization function and the suppression
	of the cross over operator. The purpose of the paper is to explain
	how the genetic algorithms have been adapted to fit with the issue
	of test optimization. The resulting algorithm differs so much from
	genetic algorithms that it has been given another name: bacteriological
	algorithm.},
	keywords = {test, OOP, search-based, selected},
	Author = {Baudry, Benoit and Fleurey, Franck and J{'e}z{'e}quel, Jean-Marc and {Le~Traon} Yves},
	Journal = {Software, Testing, Verification & Reliability journal {(STVR)}},
	Month = jun,
	Number = {2},
	Pages = {73-96},
	Title = {From Genetic to Bacteriological Algorithms for Mutation-Based Testing},
	url = {http://www.irisa.fr/triskell/publis/2005/Baudry05a.pdf},
	Volume = {15},
	x-abbrv = {STVR},
	X-Editorial-Board = {yes},
	X-International-Audience = {yes},
	X-Language = {EN},
	Year = {2005},
	Bdsk-Url-1 = {http://www.irisa.fr/triskell/publis/2005/Baudry05a.pdf}}