Mutation Testing

Il n'est plus à prouver l'utilité des tests unitaires. Ils sont essentiels dans la conception d'une application de qualité. Mais, savons-nous quantifier leur pertinence, leur qualité ?

Un indicateur de couverture du code par les tests à 100%, ne signifie pas du code 100% testé. Cet indicateur ne détermine que  grossièrement le pourcentage de code exécuté lors du passage des tests unitaires, pas plus.

Voici une technique qui vous permettra d’accorder plus de confiance à vos tests.

Le processus de cette technique se déroule en deux grandes étapes : la génération de mutants, puis le carnage de ceux-ci. WTF ?

Génération de mutant

Cette étape consiste à générer des classes mutantes à partir de vos classes métiers sources. Que vous faut-il ?

Premièrement, le code métier sur lequel vous souhaitez évaluer la pertinence de vos tests.

Deuxièmement, un "pool" de mutations possibles. Une mutation étant une modification du code source, comme par exemple, l'action de remplacer un opérateur par un autre. Voici quelques exemples :

• + ► -
• * ► /
• >= ► ==
• true ► false.
• la suppression d'une instruction
• etc.

La génération à proprement parler consiste à parcourir toutes les instructions de votre code métier et pour chacune déterminer si des mutations sont applicables. Si oui, chaque mutation donnera naissance à un nouveau mutant. Dans l'exemple suivant, pour le code métier et le pool de mutations donné, le processus générera deux classes mutantes.

On notera que ce processus peut être gourmand en ressources. Lorsque le code à muter contient de nombreuses instructions et que le "pool" de mutations est conséquent, le nombre de mutants générés croit très rapidement.

Le processus de génération de mutant est maintenant terminé, ces mutants sont stockés en attendant la prochaine étape. Le carnage !

Le carnage des mutants !

Carnage, c'est simplement le terme qui me parait le plus approprié pour qualifier la deuxième étape de cette technique.

Dans la première partie, on a généré un grand nombre de mutants, mais les mutants c'est dangereux, on n'en veut pas ! Le but du "jeu" sera donc d'en éliminer le plus possible.

De quelle arme disposons-nous ? Des tests unitaires bien sûr ! Mode d'emploi :

• Vérifiez que tous vos tests sont au vert sur le code métier non-muté
• Prenez vos mutants un par un
• Positionnez les devant le mur des fusillés (ou dans votre classpath, mais c'est beaucoup moins classe...)
• Tirez une salve de tests unitaires
• Faites le bilan

Bilan / analyse

Pour un mutant donné, il y a deux résultats possibles, soit les tests sont toujours au vert, soit au moins l'un d'eux est passé au rouge.

Habituellement on souhaite que nos tests soient au vert, mais dans ce contexte, on veut du rouge. Rouge sang qui attestera de la mort de notre mutant.

En effet si, au minimum, un des tests est en échec cela prouve qu'ils sont capables de détecter les modifications du code métier source. En revanche, si tous les tests sont toujours au vert, le mutant survit, il est donc invisible aux yeux de nos tests.

Un mutant qui survit est potentiellement un test manquant !

Limitations

Le principe est simple, mais l'analyse complète peut s'avérer fastidieuse. En effet comme évoqué dans la première partie, votre nombre de mutants est rapidement conséquent.

Prenons un exemple, j'ai généré lors de la première phase 8000 mutants. Lors du carnage, 95% d'entre eux ont été tués (paix à leur âme). Il reste tout de même 400 mutants. Faire une analyse manuelle pour chacun d'entre eux est coûteux. Et la faute n'est peut être pas à la charge de nos tests unitaires. En effet, comme dans toutes batailles, il existe des ennemis plus coriaces, plus fourbes. Ici, ils se nomment "mutant équivalent".

Un mutant équivalent est un mutant qui modifiera la syntaxe du code source, mais pas sa sémantique. De ce fait, il sera impossible de créer un test unitaire capable de le détecter.

Code source :

int index = 0;
while(...) {
    ...;
    index++;
    if (index == 10) break;
}

Une mutation de "==" vers ">=" produira le mutant équivalent suivant :

int index = 0;
while(...) {
    ...;
    index++;
    if (index >= 10) break;
}

Dans cet exemple on voit clairement que la condition de sortie de la boucle reste le même.

Quel outil ?

Cette technique n'est pas nouvelle, elle a été imaginée en 1971 par Richard Lipton. Son expansion a été restreinte par la lourdeur du processus, mais l'augmentation de la puissance de nos machines permet dorénavant de rendre le "mutation testing" plus accessible.

Ok, le concept est intéressant, mais comment l'appliquer à mon projet ?

Malheureusement les outils disponibles dans le monde java sont loin d'être industrialisés.

Le pionner MµJava n'est pas basé sur JUnit car antécédent à celui-ci, son remplaçant MµClipse ne supporte que JUnit 3 et n'est plus maintenu. Jester quant à lui nécessite une configuration laborieuse et n'est plus maintenu.

L'outil le plus abouti que j'ai pu trouver est Javalanche. C'est d'ailleurs ainsi qu'il est décrit. Il reprend et combine tous les atouts des précédents outils c.à.d. :

Selective mutation:

Un petit nombre de mutations bien sélectionnées suffit à avoir des résultats précis sans générer trop de bruit.

Mutant schemata:

Pour éviter un nombre trop important de version de classe. Les mutants schemata, le programme conserve de multiples mutations chacune gardée par un "runtime flag".  Ref. [3]

Coverage data:

Tous les tests ne passent pas sur chaque mutant. Pour éviter d'exécuter des tests non pertinents pour une mutation, des données de couvertures sont collectées. Ne sont alors exécutés que les tests qui concernent la mutation.

Manipulate bytecode :

La génération des mutants s'effectue directement au niveau du bytecode pour éviter les recompilations, consommatrices de temps.

Parallel execution :

Il est possible de paralléliser le processus.

Automation :

Javalanche, contrairement aux autres outils ne nécessite que très peu de configuration. Il suffit de configurer la suite de tests à exécuter et la base du package des classes à muter.

Pour attester leurs dires les créateurs de Javalanche ont réalisé le benchmark suivant :

Dans la vraie vie

Javalanche parait éprouvé. J'ai donc tenté de le soumettre aux contraintes d'un projet réel. Les résultats que j'ai obtenus sont positifs malgré quelques difficultés de mise en œuvre. Après une durée de prise en main non négligeable et la résolution de quelques conflits de classpath avec mon projet, voici mes conclusions :

• pour 10 classes et un total de 1000 LOC, le processus prend 1 minute
• possibilité d'effectuer le processus avec des tests aussi bien d'intégrations qu'unitaires
• intégration avec des frameworks comme Spring et Hibernate possible
• intégration avec des frameworks de mock (EasyMock) possible, mais avec des restrictions. En effet, il m'a été impossible d'exécuter le processus en une seule fois sur la classe A et la classe B si, les tests de la classe B utilisent un mock de A. Sans avoir creusé plus, il me semble qu'à  force de "proxyifier" les classes, l'outil est "perdu" dans le classpath ( A, A muté, A mocké, etc...)

Mais le plus important est que cela a permis de révéler certains cas non-testés et critiques.

Conclusion

Cette technique est un pas de plus vers la perfection.

Mais avant de la mettre en œuvre,  il vous faut déjà être dans une démarche qualité assez poussée. Les tests doivent déjà être au cœur de votre processus de développement, sans quoi les résultats obtenus représenteront une trop grosse charge d'analyse. Si vous faites parti de ceux pour qui l'indicateur de couverture à atteint ses limites, méditez donc cette citation du Dr. Robert Geist :

If the software contains a fault, there will usually be a set of mutants that can only be killed by a test case that also detects that fault.

Malheureusement, les outils actuels, même Javalanche, ne me semblent pas assez industrialisés. A quand un plugin Maven qui nous permettrait de suivre le taux de mutants tués à chaque build ?

Wanna play ?

Vous voulez voir comment cela fonctionne ? Voici un petit POC (Proof Of Concept) en images qui décrit la manière dont on peut compléter ses tests unitaires via cette méthode.

Pour commencer, prenons une classe couverte à 100% par nos tests :

La méthode initialise une Map et y ajoute une entrée pour chaque clef passée en paramètre en lui affectant la valeur 0.

Apres une première passe, Javalanche nous donne ce rapport :

Dans la section de gauche, on observera que cette simple classe génère déjà 8 mutants, mais surtout qu'il y a 3 survivants. Dans la partie de droite, on remarquera que c'est au niveau de la ligne 18 que le bât blesse.

Que l'on incrémente ou décrémente la constante, les tests continuent de passer. Allons voir :

Et les tests associés à cette méthode :

package com.octo.sample.mutationTesting;

public class MyClassUTest {

	@Test
	public void initMapToValueForKeys_WithNull_ShouldReturnAnEmptyMap() {
		// setup
		MyClass myCLass = new MyClass();

		// action
		Map myMap = myCLass.initMapToValueForKeys(null);

		// assert
		assertNotNull(myMap);
		assertEquals(0, myMap.size());
	}

	@Test
	public void initMapToValueForKeys_WithGoodParams_ShouldReturnAMapOfTheRigthSize() {
		// setup
		MyClass myCLass = new MyClass();
		Integer[] myKeys =new Integer[] {35, 84,8000};

		// action
		Map myMap = myCLass.initMapToValueForKeys(myKeys);

		// assert
		assertNotNull(myMap);
		assertEquals(3, myMap.size());
	}
}

En effet, on vérifie la taille de la Map retournée, mais pas la valeur d'initialisation. On ajoute donc un test :

@Test
public void initMapToValueForKeys_WithGoodParams_ShouldReturnAMapWithGoodValues() {
	// setup
	MyClass myCLass = new MyClass();
	Integer[] myKeys =new Integer[] {35, 84,8000};

	// action
	Map myMap = myCLass.initMapToValueForKeys(myKeys);

	// assert
	assertNotNull(myMap);
	assertEquals(3, myMap.size());
	assertEquals(new Integer(0), myMap.get(myKeys[0]));
	assertEquals(new Integer(0), myMap.get(myKeys[1]));
	assertEquals(new Integer(0), myMap.get(myKeys[2]));
}

On relance Javalanche :

Good job !

Vous souhaitez essayer ? Pour mettre en place ce POC, suivez les étapes suivantes : - installez maven et Ant - récupérez et de-zippez Javalanche - de-zippez et compilez (maven install) le POC - éditez le fichier Javalanche.xml à la racine du projet pour modifier la première propriété et la faire pointer vers le répertoire où vous avez extrait Javalanche

Il ne vous reste plus qu'a lancer Javalanche en executant la commande suivante à la racine du projet :

ant -f javalanche.xml -Djavalanche.maxmemory=1024m mutationTest

Références

[1] - Javalanche: Efficient Mutation Testing for Java

[2] - Should Software Testers Use Mutation Analysis to Augment a Test Set?

[3] - Mutation Analysis Using Mutant Schemata