Améliorer les algorithmes de test : approches mathématiques dans les tests de logiciels

Les nouvelles méthodologies de conception de tests n’apparaissent pas toujours simultanément. Une partie importante des pratiques de test modernes a évolué grâce à un travail théorique et expérimental méticuleux d’adaptation de modèles mathématiques. Bien qu’il ne soit pas nécessaire d’être mathématicien pour être un bon testeur, comprendre les fondements théoriques des méthodes de test peut être bénéfique.

Maximiser la couverture et minimiser le nombre de cas de test

La logique mathématique peut être appliquée pour optimiser la couverture du code d'un système. Considérons un exemple simple avec une instruction « if » contenant deux branches et une longue formule logique dans la condition :

 if ( (& a2) & (!(a2 || a4) ) || a3 ) { # action 1 } else { # action 2 }

Pour couvrir les deux branches, il est nécessaire de comprendre la structure de la formule. On pourrait se demander : que peut-on faire ? Vous pouvez toujours tester ce morceau de code (formule logique) de manière exhaustive, ce qui donne 16 tests. Cependant, c’est beaucoup et des efforts devraient être faits pour réduire le nombre de tests. Le nombre de tests peut être réduit en utilisant la méthode Modified Condition/Decision Coverage (MC/DC) (donnant 11 à 12 tests). Si la couverture des succursales est suffisante pour tester les risques, seuls deux tests sont nécessaires, mais on ne sait pas lesquels.

Pour résoudre ce problème, l'algèbre booléenne peut être appliquée à la formule logique :

 if( (& a2) & (! (a2 || a4) ) || a3 ) = = ( (& a2) & ( (!a2 || !a4) ) || a3 ) = = ( a1 & a2 & !a2 & !a4 || a3 ) = = 0 || a3 = a3

Après transformation de la formule originale, il devient évident qu’une seule variable a3 influence réellement la valeur de vérité. Du coup, l’obtention de cas de tests devient plus simple (l’un avec et l’autre avec a3 == false ). De plus, il devient évident que le code n'est pas optimisé, car il est étrange d'avoir une expression logique complexe dépendant d'une seule variable. Malheureusement, de telles situations sont assez courantes dans la réalité et l’exemple fourni est relativement simple.

En conclusion:

• 2 tests si des tests exhaustifs sont utilisés

• 2 tests avec la méthode MC/DC

• 2 tests si la couverture des succursales est appliquée

  
  

En général, les expressions logiques peuvent être simplifiées (minimisées) à l’aide de l’algèbre, de méthodes mathématiques et d’algorithmes. Il existe au moins trois méthodes similaires. Les transformations directes utilisant l'algèbre booléenne, comme expliqué ci-dessus, fonctionnent toujours. Des méthodes de minimisation d'expression qui prennent en compte les caractéristiques d'un domaine spécifique en s'appuyant non seulement sur les mathématiques et la logique, mais également sur les particularités du domaine, peuvent être trouvées et appliquées.

Optimisation des tests par paires

La méthode de test par paires implique de générer des ensembles de tests de telle manière qu'au lieu de tester toutes les combinaisons possibles de paramètres d'entrée via des tests exhaustifs (qui peuvent prendre du temps et des ressources), les ensembles de tests sont conçus de manière à ce que chaque valeur de paramètre se combine avec chaque valeur. valeur des autres paramètres testés au moins une fois. Cela réduit considérablement le nombre de cas de test.

Il s’agit d’une méthode bien établie et souvent utilisée. Malheureusement, cette méthode ne fonctionne pas toujours à mesure que les systèmes deviennent plus complexes. La question se pose : les tests par paires sont-ils suffisants pour tester en profondeur un système complexe avec de nombreux paramètres d’entrée ? Cette question a intrigué de nombreux professionnels et chercheurs en tests, notamment le National Institute of Standards and Technology (NIST) aux États-Unis.

• Pairwise finds 65-97% of errors
• 3-way finds 89-99% of errors
• 4-way finds 96-100% of errors
• 5-way finds 96-100% of errors
• 6-way finds 100% of errors

Selon des études, les tests par paires détectent des erreurs dans 65 à 97 % des cas. Si nous commençons à combiner non pas des paires de paramètres mais des triples ou quadruples, c'est-à-dire en utilisant des tests k-way, nous obtenons un plus grand nombre de tests mais détectons également plus d'erreurs.

Par exemple, supposons qu'un système ait deux paramètres avec trois valeurs chacun et trois paramètres avec deux valeurs chacun :

• Pairwise: 10 tests with 14% coverage
• 3-way: 18 tests with 25% coverage
• 4-way: 36 tests with 50% coverage
• 5-way: 72 tests with 100% coverage

Vous pouvez choisir un niveau satisfaisant de couverture de tests et un nombre acceptable de cas de test.

La base du principe par paire est constituée de tableaux orthogonaux contenant des n-uplets (paires, triples, quadruples, ...) de valeurs un nombre égal de fois.

La base habituelle pour les tests par paires et k-way est OA(N, V^k, t) , où :

• N est le nombre de lignes

• k est le nombre de colonnes

• V est le nombre de valeurs différentes dans une colonne

• t est la force (t=2 pour deux à deux)

  
  

En OA, chaque ensemble de t colonnes inclut tous les t tuples un nombre égal de fois.

Au lieu de matrices orthogonales, il est préférable d’utiliser des matrices de couverture. Ces matrices diffèrent des matrices orthogonales dans la mesure où chaque ensemble de valeurs apparaît au moins une fois, et non « un nombre égal de fois ». Dans ce cas, il y a un peu moins de tests. Des cas de test incorrects peuvent survenir avec les matrices de couverture, mais dans l'ensemble, le processus de test est beaucoup plus rapide. Ainsi, le processus de test est considérablement simplifié.

CA(N, V^k, t), où :

• N est le nombre de lignes
• k est le nombre de colonnes
• V est le nombre de valeurs différentes dans une colonne
• t est la force (t=2 pour deux à deux)

En CA, chaque ensemble de t colonnes comprend tous les t tuples au moins une fois. L'utilisation de matrices de couverture permet de passer des tests par paires aux tests k-way sans augmenter significativement le nombre de tests.

États du système et tests des états changeants du système

Habituellement (presque toujours), un système a plus de deux états : « fonctionne » et « ne fonctionne pas ». Considérons une partie des États qui ont une commande de stock. Un ordre d’achat ou de vente d’actions doit passer par une série d’états pour que la transaction soit finalisée. Tout d'abord, l'ordre est créé, puis confirmé par l'échange, suivi de nombreuses petites transactions d'achat et enfin, la quantité d'actions requise est achetée ou vendue. Tous les états d’un ordre boursier sont reflétés dans les systèmes commerciaux, et toutes les transitions et tous les états doivent bien entendu être testés.

Presque toujours, soit tous les états, soit toutes les transitions sont testés, mais le plus souvent, les deux sont vérifiés. Une couverture complète est réalisable, mais elle prendra beaucoup de temps, sera coûteuse et nécessitera beaucoup de ressources.

Graphiques et automates finis

Considérons le problème du voyageur de commerce (commi voyager) et l'algorithme de De Bruijn. Il suffit de comprendre que l'algorithme permet d'obtenir un ensemble optimal ou suffisamment optimal de chemins courts pouvant être parcourus dans un graphe pour le parcourir complètement (à proprement parler, tout autre algorithme accomplissant quelque chose de similaire peut être utilisé, ou on peut inventer un algorithme personnalisé).

• Tout d’abord, prenez les états initiaux du système et construisez un nouveau graphe où les sommets correspondent aux transitions du graphe d’origine.
• Ensuite, couvrez les sommets du nouveau graphe, c'est-à-dire les transitions de l'ancien.
• Certains chemins sont évidents et s'avèrent assez courts (ce qui est très pratique pour tester les états et les transitions du système).
• Continuez à construire d’autres chemins. Du coup, ils risquent de devenir trop longs (et ce n’est pas bon).

Considérons l'exemple suivant pour analyser la situation :

Il y a trois testeurs. Le premier effectuera le premier test, le deuxième le deuxième test, le troisième le troisième test. Les deux premiers termineront les deux premiers tests assez rapidement car les chemins sont courts (en comparaison avec le troisième, car les deux premiers chemins sont courts), mais le dernier prendra beaucoup de temps (car le troisième chemin est très long).

Si l'algorithme de Bruijn est appliqué, la troisième séquence peut être « découpée » en plusieurs séquences plus courtes et l'exécution de tous les tests peut être parallélisée efficacement.

Nous pouvons nous retrouver avec plus de tests, mais dans le cas d'une exécution parallèle, les tests se termineront beaucoup plus rapidement car les tests sont plus courts.

De plus, avec plus de tests, il y a plus de flexibilité dans leur exécution. Tous les tests peuvent être exécutés simultanément, ou les tests inintéressants et moins importants peuvent être supprimés. Des priorités plus élevées peuvent être attribuées aux tests qui passent par les états les plus importants du système. Il existe de nombreuses façons d’exploiter les résultats de l’algorithme.

De plus, l'algorithme n'utilise pas d'éléments spécifiques au domaine ; il fonctionne avec des états et des transitions absolument abstraits du système.

Dans cette technique, tout dépend de la manière dont l’algorithme est utilisé. Dans le cas le plus extrême, les testeurs peuvent ne rien savoir de la logique derrière les transitions entre les états. Dans une telle situation, la longue chaîne de transitions d'état sera « coupée » par l'algorithme en plusieurs courtes. Certaines de ces chaînes peuvent s’avérer dénuées de sens. Par conséquent, le caractère raisonnable des chaînes obtenues et celles qui sont importantes et significatives pour les tests doivent être évaluées. Cela n'a pas de sens et n'a pas d'importance, mais les voies possibles pour changer les états du système peuvent permettre de comprendre quelle partie du système doit être modifiée, et il sera évident quelle partie exactement.

Les principales conclusions peuvent être considérées comme suit :

• Les algorithmes de minimisation des expressions logiques offrent une couverture de test maximale avec un minimum d'effort. Il n'est pas toujours nécessaire d'utiliser des algorithmes de minimisation - c'est parfois une perte de temps ; il existe des approches universelles.
• Une couverture complète des tests pourrait être obtenue avec un petit ensemble de cas de test courts, faciles à paralléliser, automatiser, flexibles et indépendants.
• L'analyse des statistiques d'utilisation des applications en conditions réelles permet d'optimiser et d'adapter les techniques de conception de tests existantes et d'atteindre la couverture de tests nécessaire, garantissant la qualité des applications.
• La modification des tests par paires permet des tests plus approfondis avec une plus grande couverture de test que les algorithmes standard et avec presque les mêmes ressources.
• Certains algorithmes peuvent être efficaces dans les cas où les techniques standard de conception de tests sont moins efficaces.
• Les échecs des techniques de conception de tests combinatoires présentent certains défis.
• Les algorithmes obtenus peuvent être facilement adaptés à différents systèmes et ne nécessitent pas de connaissances particulières dans le domaine.

Quant aux inconvénients mineurs, il convient de noter :

• Certains algorithmes ne sont pas efficaces et pertinents dans tous les cas ; dans de nombreuses situations, les techniques de conception de tests standard sont tout aussi efficaces, voire parfois même plus.
• L'application d'algorithmes nécessite certaines connaissances mathématiques et parfois plus de temps pour leur application, ce qui peut également devenir un facteur vital dans de nombreuses situations.