Combinaisons logiques

Applicabilité :: L'output est fonction d'une expression logique liant les variables d'input interprétées comme des propositions.

Modèle  de faute ::  Erreurs dans l'interprétation des conditions d'un algorithme, erreurs logiques (mauvais connecteurs logiques, inversions).

Exemple 1 : les triangles

Spécification du contsructeur d'un triangle :

Implicitement, une  expression logique définit un triangle correct (paramètres appelés a,b et c) :

• pour vérifier l'ordre des paramètres :
  • C1: <code>a <= b</code>
  •  C2: <code>b <= c</code>
• pour vérifier des propriétés de base d'un triangle :
  • C3: c < a + b
  • C4: a > 0
  • C5: b > 0
  • C6: c > 0

On a donc comme expression logique : C1 /\ C2 .. /\ C6

Construction des suites de test

Si on veut tester tous les cas, on a au pire `2^n`variants différents.  

Variant :: Une combinaison unique des variables (booléennes) d'entrée et des variables de sortie (ie. une ligne dans la table de vérité correspondant à l'expression)

1. Construire une représentation manipulable de l'expression logique:cette expression doit être la plus simple possible pour limiter lagénération de cas de test
2. Appliquer un critère de test (stratégie de test)
3. sélectionner les valeurs d'entrées permettant de réaliser le test

Représentation testable

modéle de test permettant d'appliquer une stratégie de sélection :

• table de décision : chaque colonne est une variable d'entrée ou desortie (on suppose que toutes les variables sont modélisées comme desbooléens), chaque ligne est une combinaison
• arbre : chaque noeud de l'arbre est une variable, chaque brancheest un état de cette variable, les feuilles sont les valeurs devariables de sorties correspondant
• graphe de cause-effets : les noeuds de départ sont les variablesd'entrée, les noeuds de sortie sonts les variables de sortie, lesnoeuds intermédiaires sont des opérateurs booléens
• matrices de Karnaugh
• BDD

Cas particuliers :  

• don't care : la valeur d'une variable n'a pas d'importance dans lecas considéré. Permet de simplifier une expression ou une table de décision
• can't happen : un cas est impossible (cas des valeurs de variablesliées, si plusieurs variables propositionnelles utilisent une mêmevariable d'entrée avec des valeurs différentes, appelé exclusionmutuelle sure). Attention aux faux sentiments de sécurité...
• don't know : cas non prévu par la spécification : PROBLEME

Critères de couvertures

• tous les variants explicites
• tous les variants : `2^n` dans le pire des cas, impraticable au delade quelques variables
• tous les termes true/false
• mc/dc

MC/DC

Modified Condition/Decision Coverage : critère de test classique, applicable pour expressions logiques  

• chaque valeur possible de chaque proposition de l'expression doitêtre testée au moins une fois
• chaque valeur possible de l'expression doit être testé au moinsune fois
• chaque valeur possible d'une condition produisant un résultat dedécisions différent indépendamment des autres conditions  doitêtre testée

exemple :  A \/ B

• condition coverage : (1,0), (0,1)
• decision coverage : (1,0), (0,0)
• decision/condition : (1,1), (0,0)
• MC/DC : (1,0), (0,1), (0,0)

voir http://library-dspace.larc.nasa.gov/dspace/jsp/handle/2002/12640

Principe :: Identifier pour chaque variable en entrée les conditions nécessaires pour que, toutes les autres variables étant fixées (toutes choses égales par ailleurs), la modification de la valeur de cette variable se reflète dans le résultat prévu.  

Exemple : Avionique

Exigence :: Pour savoir si un avion est au sol, on utilise l'indicateur WOW (Weight on Wheels). Cet indicateur est positionné si:  

• les interrupteurs de de roues droites et gauches sontpositionnés
• OU la vitesse est inférieure à 40 noeuds et l'indicateur AV(Airspeed Valid) est positionné

Cas de test ::

Les cas de tests sont ils valides pour le critère MC/DC et l'expression : WOW = (Roue_G & Roue_D) | ((Vit < 40 ) & AV)

Représentation Graphe: Construction d'un BDD

Représentation compacte d'une expression booléenne Construire un diagramme de décision binaire (BDD) représentant tous les états possibles d'un ensemble de variables logiquement liées (ou non). Un BDD est un graphe dirigé acyclique dont les noeuds sont des variables logiques et les arcs des valeurs logiques vrai ou faux. Les noeuds terminaux du graphe sont les valeurs true et false.  

Propriétés des (Reduced,Ordered) BDD :  

• canonicité wrt un certain ordre total des variables : tout cheminde la racine du BDD à une feuille respecte un ordre total des variables
• minimalité : chaque noeud est unique au sens où le triplet(var,low,high) est unique dans le BDD

Attention :: Tous les BDD ne sont pas égaux, trouver le BDD minimal pour une expression arbitraire est un pb NP-complet (dépend du choix d'ordonnancement des variables)

http://en.wikipedia.org/wiki/Binarydecisiondiagram

Intérêt :: réduit le problème de la sélection de cas de tests à un parcours de graphes : choisir les valeurs de variables permettant de parcourir tous les chemins du BDD !

Représentation compacte d'un arbre de décision par partage des noeuds et ordonnancement des variables.

Construit lors de la compilation des expressions logiques: forme normal if-then-elseINF) correspond au dépliage des expressions conditionnelles. Problèmes si une variable apparaît plusieurs fois dans une expression.

Lien MC/DC et BDD

Hypothèse :  Pour toute expression logique e, le nombre de cas de tests pour les critères tous les chemins du BDD et MC/DC est équivalent.

Conclusion

Critères combinatoires = cas particulier de critères de flots de contrôle généraux. Lorsqu'on construit le flot de contrôle d'une méthode, les branchement représentents des conditions logiques, La couverture des arcs implique donc  couverture des conditions logiques.  

Introduction

Modèle de fautes :: Les défauts dépendent de l'interaction d'au plus 2 (ou n) paramètres, pas de la combinaison de tous les paramètres du CUT.  

Applicabilité ::  Le comportement du CUT dépend de la combinaison d'un ensemble de paramètres à valeurs finis: drapeaux, énumérations, plages de valeurs ou partitions de domaines (cf. infra). La taille du domaine et le nombre de paramètres doivent être dans des proportions raisonnables. Le nombre réel de configuration à tester en combinant toutes les possibilités est trop important.  

Partitionnement des domaines de valeurs, parfois aeppelé test aux limites. Critère pour le choix de valeurs pertinentes.  

Modèle de fautes :: Les erreurs sont souvent dûes à une mauvaise interprétation d'opérateurs de comparaison ou de tests aux limites des domaines de valeurs. ex: < et inférieur ou égal, étoile de kleene ou étoile propre. Mauvaise détermination d'une condition limite, modification de comportement non prise en compte dans certains domaines.

Applicabilité ::  Comportement dépend d'une partition de domaine d'une ou plusieurs variables d'entrée (ou d'état), applicable aussi pour des partitions d'états d'objets : comportement fonction de classes de valeurs, changement en fonction de domaine

Basé sur existence d'une frontière de domaine, domaine peut être ouvert (ne comprenant pas la frontière) ou fermé (comprenant la frontière)

Critères

point on :: point sur la frontière

point off :: point dans un domaine ouvert et en dehors d'un domaine fermé

1 x 1 : choisit un point ON et un point OFF par condition définissant une partition de domaine, le plus proche possible l'un de l'autre

N x 1 : choisir N point ON linéairement indépendants  sur chaque frontière, N est le nombre de dimensions (variables), et 1 point OFF

Stratégies faibles vs. fortes:

• 1x1 faible: 1 point ON et un point OFF pour chaque condition
• 1x1 fort: 1 point ON et un point OFF pour chaque segmentrésultant d'une combinaison  de conditions
• Nx1 faible: N point ON et 1 point OFF pour n dimensions, par condition
• Nx1 faible: N point ON et 1 point OFF pour n dimensions, parsegment de frontiére

Exemple 1 : Triangles

Définition d'un triangle isocèle : Un triangle est isocèle si deux de ses côtés sont de mêmelongueur.

Défini trois domaine en trois dimensions borné par les frontières :

1. <code>a=b & c < a+b</code>
2. <code>b=c & a < b+c</code>
3. <code>c=a & b < c+a</code>

Attention ::  Ne tient pas compte de l'ordre des paramètres ! Si a<b<c, il y a moins de cas à traiter (lesquels ?)

Exemple 2 : contrôle de chaudière

Chaudière alimentée par une vanne et chauffée par un gaz. soupape de sécurité en cas de surpression.

Input :

• température
• pression

Output :  

• ouvrir/fermer gaz (G
• ouvrir/fermer soupape (S
• ouvrir/fermer vanne (V

Conditions :

• <code>T - 5*P < 200</code> > G, sinon ~G
• <code>P < 1</code> > V, sinon ~V
• <code>P > 3</code> => S, sinon ~S

mise en oeuvre

construction système d'équations représentant les contraintes des différents domaines.

Vérifications :

• complétude : l'ensemble des sous-domaines définis forme unepartition de l'ensemble des valeurs possibles
• consistance : l'intersection des sous-domaines est vide

Représentation facile pour domaines numériques à une ou deux variables: représente sur une droite ou un plan les contraintes et les  domaines, sélection des points visuelle.

Représentation complexe pour 3 variables et plus: vérification des critères nécessite outils mathématiques plus complexes, résolution de systèmes d'équations et inéquations (cf. simplex).  Si la spécification est trop compliquée à tester, se poser des questions sur son intérêt : il y a de fortes chances qu'elle soit mal implantée. => divide quod impera

Exemple 3: test d'un générateur aléatoire

Problème: soit la classe Random suivante:

public class Random {


   public int random() ...
}

Comment tester fonctionnellement cette classe ?  

Solution:

• extraire un échantillon des nombres produits par random()
• vérifier que la distribution des nombres tend à être uniforme,compte-tenu d'une marge d'erreur acceptable et d'exécutionsmultiples.