Ismaïl Berrada
email: berrada@labri.fr

Patrick Félix
email: felix@labri.fr

TGSE : Un Outil Générique pour le Test *

Keywords: Systèmes communicants, Modélisation, Test de protocoles Communicating systems, Modeling, Protocol testing

L'automatisation de la génération des tests devient une nécessité devant l'accroissement de la complexité des protocoles à tester. La simulation graphique de l'exécution d'un cas de test vient compléter l'étape de génération par une étape d'analyse des séquences générées. Dans cet article, nous proposons un modèle générique permettant de traiter différents types et architectures de test : le test de conformité, le d'interopérabilité, de composants, et le test dans le contexte. Ce modèle appelé 'systèmes communicants' (CS), supportant des contraintes temporelles et les données, est basé sur la définition d'une topologie de communication régissant les synchronisations possibles entre différentes entités communicantes. Nous montrons le caractère générique des CSs pour la spécification et la génération de test pour le test actif et passif. Ce modèle est mis en oeuvre dans l'outil TGSE (émulation, simulation et génération de test).

ABSTRACT. This paper follows two main lines of research. The first line is related to the study of models for the description of systems. For this line, we introduce the model of Communicating Systems (CS), which defines a set of common resources, a set of entities, and a topology of communication. The second line concerns testing methodologies adapted to protocol testing. For this line, we give a formal definition of a generic algorithm of generation (GAG). We demonstrate that the CS model with a GAG supports various 1) test architectures, 2) test types: conformance, interoperability, embedded, component testing..., and 3) test approaches: passive and active testing. The paper presents also the main characteristics of the TGSE tool (Test Generation, Simulation, and Emulation). TGSE is composed of a test case generator based on the CS model and implementing a GAG, a graphic simulator of the execution of a sequence generated by TGSE and a real-time emulator of communicating specifications. In its current version, TGSE supports the passive and active testing of one or several components with data and temporal constraints.

Introduction

Le test est une étape importante dans le cycle de développement de tout système (logiciel, protocole de communication ou matériel). Cette étape consiste à soumettre le système considéré à toute une série d'épreuves (expériences) pour voir si son comportement est bien celui attendu.

Le contexte actuel du test offre une multitude de types de test : test de conformité, dans le cas d'une seule entité, test d'interopérabilité, dans le cas de plusieurs entités communicantes, test dans le contexte, dans le cas d'une entité communicante dans un environnement. A cette multitude de types, s'ajoute une grande diversité dans les modèles de base considérés : les systèmes de transitions étiquetés (LTS) [BRI 88], les systèmes de transitions à entrée/sortie (IOLTS) [TRE 96,FER 97] De notre point de vue, cette diversité dans les types, les modèles et les approches traduit la spécificité des besoins. En effet, les différents types de test sont une conséquence de la composition des systèmes à tester et des architectures de test : la conformité considère seulement une entité tandis que l'interopérabilité et le test dans le contexte considèrent plusieurs entités communicantes interagissant selon une architecture de test donnée. La multitude des modèles de base se justifie par des besoins différents de spécification : les systèmes considérés qui ont des comportements événementiels, peuvent manipuler des données et être soumises à des contraintes temporelles. Que l'on soit dans le cadre du test actif où la dérivation d'un test se fait à partir de la spécification, ou bien dans le cadre du test passif où l'absence d'observabilité et de contrôlabilité ne permet qu'une validation des traces de l'implémentation, nous sommes confrontés au même problème. Il s'agit d'un problème d'accessibilité d'un état ou d'une transition au sein d'un graphe.

Motivations. Dans cet article, nous traitons le test des protocoles de communication temps-réel dans l'optique d'une approche permettant d'appréhender les différents types de test au sein d'un même outil. La première motivation est la modélisation des communications et le partage des données entre différentes entités d'un système. Les algèbres de processus se présentent alors comme un bon modèle, très expressive. Cependant, l'utilisation des algèbres de processus présente une difficulté de définition d'algorithmes applicables dans un outil de génération de test. Nous introduisons alors le modèle générique des systèmes communicants inspiré de [MAD 04]. Ce modèle définit un ensemble d'entités (composantes) communicantes, des ressources communes (données et paramètres partagés) aux différentes composantes et une topologie de communication qui explicite les différentes synchronisations possibles dans un état global du système.

La deuxième motivation de cet article est réduire l'écart qui existe entre les différents types de test. Notre but est de montrer qu'il est possible d'appliquer la même stratégie de génération pour différents types de test. Nous définirons alors un algorithme générique de génération. Nous montrerons que le modèle des systèmes communicants muni d'un algorithme générique de génération supporte les différents types, approches et architectures de test.

Finalement, en présentant l'outil TGSE (Émulation, Simulation et Génération de Test), basé sur le modèle des systèmes communicants, nous montrons la faisabilité de notre approche. Nous présenterons les différentes techniques de génération implémentées dans TGSE.

Dans la suite de cet article, nous introduisons dans la section 2 le modèle des systèmes communicants et l'algorithme générique de génération dans le section 3. Puis, dans la section 4, nous montrons le caractère générique de ce modèle. Ensuite nous donnons dans la section 5 quelques éléments sur la mise en oeuvre de ce modèle au sein de l'outil TGSE. La section 6 est consacrée à une étude de cas sur le protocole CSMA/CD. La dernière section sera réservée à la conclusion et aux perspectives.

Modèle des Systèmes Communicants

Le comportement d'un protocole de communication peut être décrit par un modèle formel comme les systèmes communicants. Un système communicant (CS) définit un ensemble de ressources communes, un ensemble d'entités et une topologie de communication. Les entités représentent des processus. Elles sont modélisées par des automates temporisés étendus à entrée/sortie (ETIOAs). La topologie de communication décrit les différentes synchronisations possibles entre les entités du CS. Les ressources communes représentent les différentes données partagées par les entités du CS. Par la suite, IR dénotera l'ensemble des réels et IR + dénotera l'ensemble des réels positifs.

Automate temporisé étendu à entrée/sortie

Horloges et Contraintes.

Une horloge est une variable qui mémorise le passage du temps. Elle peut être réinitialisée et inspectée à tout moment pour calculer le temps écoulé depuis la dernière réinitialisassion. Dans le modèle d'Alur-Dill [ALU 94], les horloges évoluent à la même vitesse, elles sont évaluées dans IR + et la seule réinitialisassion permise est de la forme x := 0. Pour un ensemble C d'horloges, un ensemble P de paramètres et un ensemble V de variables, l'ensemble des contraintes d'horloge Φ(C, P, V ) est défini par la grammaire suivante :

φ := φ 1 |φ 2 | φ 1 ∧ φ 2 , φ 1 := x ≤ f (P, V ), φ 2 := f (P, V ) ≤ x avec x une horloge de C et f (P, V ) une expression linéaire de P et V .
Définition 1 (ETIOA) Un automate temporisé étendu à entrée/sortie (ETIOA) est un 10-uplet M = (S, L, C, P, V, V 0 , P red, Ass, s 0 , T ) avec :

-S est un ensemble fini des états.

-

s 0 est l'état initial. -L est un alphabet fini d'actions, L = L i ∪ L o ∪ I.
-C est un ensemble fini d'horloges incluant une horloge globale h.

-P est un ensemble fini de paramètres. -V est un ensemble fini de variables.

-V 0 est un ensemble de valeurs initiales pour les variables de V .

-P red = Φ(C, P, V ) ∪ P [P, V ], P [P, V ] est un ensemble d'inégalités linéaires sur V et P .

- -S = {s 0 , s 1 , s 2 , s 3 } et s 0 l'état initial. -L = {!a, ?b, !c, ?d}, C = {x, y}, P = {β, λ}, V = {v1} et V 0 = {β}.

Ass = {x := 0 | x ∈ C} ∪ {v := f (P, V ) | v ∈ V }
-P red = {y ≥ λ, x ≤ 1, v1 ≤ 4}.

-Ass = {x := 0, y := 0, v1 := v1 + 1}.

-La transition t de source s 2 et de destination s 3 est : t = (s 2 , !c, {x ≤ 1}, {v1 := v1 + 1}, s 3 ).

REMARQUE. -

Pour un ETIOA M = (S, L, C, P, V, V 0 , P red, Ass, s 0 , T ), -Lorsque P = ∅ et V = ∅, on retrouve alors la définition usuelle d'un automate temporisé (TIOA) et M sera noté simplement (S, L, C, s 0 , T ).

-Lorsque C = ∅, P = ∅ et V = ∅, on retrouve alors la définition usuelle d'un automate (IOA) et M sera noté simplement M = (S, L, s 0 , T ).

Topologies de communication et Systèmes Communicants

Une

éléments et ∀ - → v ∈ L tr , - → v = (a g , a 1 , ..., a n ) avec a g ∈ G et ∀i ∈ [1, n], a i ∈ I i ∪ {idle}.
Un vecteur -→ v = (a g , a 1 , ..., a n ) de L tr décrit l'action a i que le processus i, i ∈

[1, n], doit effectuer. La synchronisation des différentes actions donne lieu à l'action globale a g . Lorsque un vecteur -→ v = (a g , idle, ..., a i , ..., idle) définit une seule action, le processus i exécute seul l'action a i et change d'état. Pour une topologie T op = (G, I, T r), lorsque le nombre d'états du traducteur T r est égale à 1, T op est appelée topologie statique et dans ce cas les éléments de L tr sont appelés des vecteurs de synchronisation.

Une topologie offre la possibilité de modéliser des communications entre un, deux ou plusieurs processus : unicast, multiscast et broadcast. Elle peut être utilisée, dans certains cas, comme une sorte de contrôleur sur les actions permises par les différents processus dans une configuration donnée du système global.

Définition 4 (Système Communicant) Un système communicant CS est un 5-uplet (SP, SV, SV 0 , (M i ) 1≤i≤n , T op) avec :

-SP est un ensemble de paramètres partagés.

-SV est un ensemble de variables partagées.

-SV 0 est un ensemble de valeurs initiales pour les variables de SV .

-

T op = (G, {I i } 1≤i≤n , T r) est une topologie. -M i = (S i , L i , C i , P i , V i , V 0i , P red i , Ass i , s 0i , → i ) est un ETIOA tel que : ∀i ∈ [1, n], I i ⊆ L i .
Un système communicant (CS) définit un ensemble de ressources communes, un ensemble d'entités et une topologie de communication. Les entités représentent des processus. Elles sont modélisées par des ETIOAs. La topologie de communication décrit les différentes synchronisations possibles entre les entités du CS. Nous avons supposé dans la définition des entités que ∀i ∈ [1, n], I i ⊆ L i . Ceci permet d'avoir des topologies partielles qui ne définissent que les synchronisations permises (dans la section suivante, nous donnerons des exemples de telles topologies). Les ressources communes représentent les différentes données partagées du CS. Nous nous restreignons à des données de types variables et paramètres. Les paramètres (resp. les variables) peuvent être lus (resp. lues et modifiées) par les entités du CS1 . C'est une communication à mémoire partagée. Ceci ne restreint pas le modèle vu que la communication par messages peut être modélisée par des paramètres et des variables partagées. La sémantique d'un CS est définie en terme d'un ETIOA. Pour simplifier, nous supposons que les noms des différents paramètres et variables des différentes entités du système sont différents et différents de ceux du CS.

Définition 5 (Sémantique) La sémantique d'un système communicant

S = (SP, SV, SV 0 , (M i ) 1≤i≤n , T op), avec M i = (S i , L i , C i , P i , V i , V 0i , P red i , Ass i , s 0i , → i ) et T op = (G
, I, (S tr , L tr , s 0tr , → tr )), est définie par un ETIOA ζ(S) = (S, L, C, P, V, V 0 , P red, Ass, s 0 , →), tel que :

-S = {s = (s tr , s 1 , ..., s n ) | s tr ∈ S tr , ∀i ∈ [1, n], s i ∈ S i } -s 0 = (s otr , s 01 , ..., s 0n ). -L = G, C = C 1 ∪ ... ∪ C n , P = SP ∪ P 1 ∪ ... ∪ P n . -V = V P ∪ V 1 ∪ ... ∪ V n , V 0 = V P 0 ∪ V 01 ∪ ... ∪ V 0n . -P red = P red 1 ∪ ... ∪ P red n , Ass = Ass 1 ∪ ... ∪ Ass n . -→ = δ {(s tr , s 1 , ..., s n ) a,pred,ass -------→ (s tr , s 1 , ..., s n ) | ∃ - → v = (a, a 1 , ..., a n ) ∈ L tr , s tr - → v -→ tr s tr , ∀i ∈ [1, n], (((a i = idle) ∧ (s i = s i )) ((a i = idle) ∧ (s i ai,predi,assi --------→ i s i ))), pred = pred 1 ∧ ... ∧ pred n , ass = ass 1 ∧ ... ∧

CS : Un Modèle Générique pour le Test

Un modèle de spécification d'un protocole de communication doit permettre la possibilité de modéliser le comportement propre du protocole et son comportement vis-à-vis de son environnement. Le but de cette section est de montrer le caractère générique des CSs pour la spécification et la génération de test.

Pour deux ensembles L 1 et L 2 , notons par L 1 \L 2 l'ensemble des éléments propres de

L 1 : L 1 \L 2 = {a | a ∈ L 1 ∧ a ∈ L 2 }.
Dans le reste de cette section, nous considérons deux spécifications communicantes S A et S B , partageant les paramètres SP et les variables SV , SV 0 étant les valeurs initiales des variables. Nous modélisons S A (resp. S B ) par l'ETIOA A = (S A , L A , C A , P A , V A , V 0 , P red A , Ass A , s 0 , T A ) (resp. B = (S B , L B , C B , P B , V B , V 0 , P red B , Ass B , s 0 , T B )). L AB (resp. L BA ) dénotera l'ensemble des événements de L A (resp. L B ) qui synchronisent avec un événement de L B (resp. L A ). Par exemple, si L A = {?begin, ?end, !busy} et

L B = {!end, ?busy, !CD} alors L AB = {?end, !busy} et L BA = {!end, ?busy}.
Pour simplifier, nous supposons que pour tout a ∈ L AB il existe un unique b ∈ L BA qui synchronise avec a.

CS comme Modèle de Spécification

Le but de cette partie est de montrer comment décrire une spécification dans le modèle CS.

Considérons la spécification S composée des spécifications S A et S B . Une modélisation en CS de S est la suivante : CS 1 =< SP, SV, SV 0 , < A, B >, T opS >, avec T opS l'automate de la Figure 2 Ainsi, nous avons décrit une spécification à deux composantes en CS en tenant compte de l'observabilité des actions du système. La même approche s'applique à une spécification à plusieurs composantes.

CS comme Modèle pour la Génération de Test

Pour le test des protocoles, deux approches majeures ont été utilisées : le test actif et le test passif. Dans le test actif, la dérivation se fait à partir de la spécification. Cette dérivation peut ne concerner qu'une partie de la spécification dans le but de limiter l'explosion combinatoire des états, comme c'est le cas pour la technique de

Test passif.

Supposons que la trace modélisée par l'ETIOA P T race de la Figure 3 (a) est une trace d'une implémentation de la spécification S A . Cette trace exprime que l'implémentation a effectuée l'action a ∈ L A à l'instant 3, puis l'action b ∈ L B à l'instant 5 telle que la valeur de la variable partagée v ∈ SV vaut 4. Vérifier la validité de cette trace consiste à modéliser un CS CS 3 =< SP, SV, SV 0 , < A, P T race >, P T op >, avec P T race l'ETIOA de la Figure 3 (a) et P T op l'automate de la Figure 3 (b).

La topologie P T op est partielle et ne définit que les synchronisations sur les événements de P T race. Nous avons étiqueté l'état après l'action b de P T race par ACCEP T . Ceci a pour but de rendre CS 3 un CSUT et de pouvoir appliquer gga. Dès lors, gga permet de décider si P T race est une trace valide de A : si gga retourne un ensemble vide (P AT H(CS 3 ) = ∅) alors P T race n'est pas valide, sinon c'est une trace valide. REMARQUE. -1) D'une façon générale, la construction de P T op dépend fortement de P T race, elle ne doit définir que les synchronisations sur les événements de P T race et dans le même ordre.

2) La trace P T race est considéré comme une entité de CS 3 sans aucune distinction par rapport aux autres entités. Ceci permet d'étendre la forme des traces que le test passif considère à des traces sous forme d'ETIOAs définissant des états ACCEP T . 3) L'exemple du test passif de la spécification S A est un test à une composante, mais l'approche reste la même dans le cas du test passif à plusieurs composantes. La difficulté, dans ce cas, est de réordonner des différentes traces des composantes pour en construire une trace globale. Nous pensons que les techniques d'estampillage, et

Test actif.

Pour un CSUT S, les chemins générés par l'algorithme gga peuvent être utilisés pour dériver des cas de test qui couvrent par exemple tous les états de S. Ceci revient à définir tous les états de S comme des états acceptables. Nous nous intéressons alors qu'à la technique de dérivation orientée objectif de test.

Définition 9 Un objectif de test (OT) est un ETIOA (S, L, C, P, V, V 0 , P red, Ass, s 0 , →) ayant deux ensembles d'états ACCEP T et REJECT caractérisant les comportements désirables à tester.

Un OT définit une partie de la spécification à tester. Nous modélisons un OT par un ETIOA équipé de deux ensembles d'états ACCEP T et REJECT . T P 1 de la Figure 4 (a) est un exemple d'OT pour la spécification S A . T P 1 teste que l'implémentation peut effectuer l'action a puis l'action b entre [2, Sig] selon l'horloge globale h (Sig ∈ SP est un paramètre partagé de S A ). La boucle étoile sur les deux premiers états de T P 1 est pour dénoter tout l'alphabet L A des événements de S A . Nous assumons ici que a, b, c ∈ L A .

Test à une composante. On s'intéresse au test actif de la spécification S A avec OT T P 1. Une modélisation possible de ce test en CS est CS 4 =< SP, SV, SV 0 , < A, T P 1 >, T P op1 >, avec T P op1 la topologie de la Figure 4 (b). Les vecteurs < L A \{a, b}, L A \{a, b}, idle > est pour dénoter un évolution séparée de la spécification sur des événements autres que a et b. Une application directe de l'algorithme gga permet alors de trouver les comportements vérifiant l'OT T P 1.

Signalons qu'à partir de ce même OT T P 1, on peut avoir plusieurs modélisations en CS, mettant en jeu des topologies différentes. En effet, ceci est possible dans la défi-nition de la topologie qui procure plus d'expressivité sur le comportement attendu par OT. Un exemple typique de l'expressivité de la topologie est le suivant : étant donné que les chemins générés par gga pour CS 4 sont de taille (nombre de transitions) arbitraire, nous désirons générer que les chemins de taille inférieure à n. Ce souhait ne peut pas être formulé par un OT qui ne permet pas de compter les occurrences des événements. Considérons maintenant le CS CS 5 =< SP, SV, SV 0 , < A, T P 1 > , T P op1 >, avec T P op1 la topologie de la Figure 4 (c). L'étiquette étoile dans T P op1 dénote les vecteurs < a, a, a >, < b, b, b >, et < L A \{a, b}, L A \{a, b}, idle > (une transition étoile est l'ensemble de transitions sur ces vecteurs de synchronisation). Appliquer gga à CS 5 générera des chemins vérifiant T P 1 et de taille inférieure à n vu qu'on dépasse pas n états dans T P op1 . Pour conclure la partie test à une composante, prenons l'OT T P 2 de la Figure 5 (a).

T P 2 teste les mêmes fonctionnalités que T P 1 mais interdit l'apparition de c dans les deux premiers états. L'étiquette other dans T P 2 dénote les événements L A \{c}. La définition des états REJECT est en effet une manière d'interdire la synchronisation sur un ensemble d'événements. Cette interdiction peut être formulée au niveau de la topologie au lieu de l'objectif de test. Dans ce cas, on peut utiliser T P 1 au lieu de T P 2. En effet, le test actif de S A et l'OT T P 2 peut être modélisé par le CS CS 6 =< SP, SV, SV 0 , < A, T P 1 >, T P op2 >, avec T P op2 la topologie de la Figure 5 (b). Dans T P op2, lorsque la synchronisation sur c se produit, le système communicant évolue dans un état bloquant et donc lors de l'application de gga à CS 6 , gga est obligé de dépiler cette synchronisation. Finalement, l'algorithme gga appliqué à CS 6 donne les chemins vérifiant T P 2.

Test à plusieurs composantes

On s'intéresse au test actif de la spécification S composée des deux spécifications Dès lors, l'application de gga permet de générer les chemins qui vérifient T P 1.

Finalement, dans le cas du test actif orienté OT d'une spécification définissant des composantes symétriques, à l'exemple de la spécification TCP et la spécification de CSMA/CD à plusieurs émetteurs, l'OT peut contenir des événements (a j ) qui ne sont pas des événements de synchronisations entre composantes mais apparaissent dans plusieurs composantes. Pour spécifier qu'un événement de OT correspond à une composante spécifique i, deux solutions sont envisageables sans utiliser le modèle CS : 1) dupliquer les ETIOAs où les événements (a j ) apparaissent puis indexer les différents événements par l'indice de chaque composante ou 2) indexer les événements (a j ) par l'indice de la composante i (a j (i)) et définir un algorithme de génération tenant compte des indices des événements dans OT. Dans le modèle CS, ce problème ne se pose pas vu que cette correspondance peut être formulée dans les vecteurs de la topologie. Ceci évite d'indexer et de dupliquer des composantes.

Ainsi, nous avons montré que notre modèle CS est un modèle générique dans le sens qu'il permet la modélisation des différents types de communications et l'incorporation de l'architecture du test dans la description et un modèle unificateur des différents types de test, offrant plus d'expressivité pour tester les protocoles de communications.

TGSE : Un Outil de Générique de Génération

Dans cette section, nous décrivons l'implémentation des CSs dans l'outil TGSE (Test génération, simulation and emulation) développé au LaBRI. Si lors du parcours, un état ACCEP T est rencontré, la recherche se termine par un appel à l'API writeT race() qui décore le chemin obtenu par les différents verdicts. La sortie est en XML suivant une DTD Calife.

Signalons finalement qu'en cas ou aucun état ACCEP T n'est rencontré, l'algorithme df s est relancé automatiquement pour une nouvelle tentative (le lancement est paramétrable). De plus, il est possible de générer un cas de test minimal en nombre de transitions pour un nombre de tentatives donné.

Application : CSMA/CD

Le protocole CSMA/CD (Figure 7) se compose d'un bus (médium de communication) et d'un ou plusieurs émetteurs (stations émettrices). Nous ne modélisons pas ici les récepteurs. Lorsque deux ou plusieurs émetteurs envoient simultanément des données sur le bus, ce dernier détecte les collisions des trames et envoie le message CD en diffusion aux émetteurs ; ces derniers devront re-émettre plus tard. Par la suite, Sender dénotera l'ETIOA représentant la spécification de l'émetteur (Figure 7 Malgré que le protocole CSMA/CD est de taille réduite, l'utilisation de plusieurs émetteurs augmente sa complexité. Les resultats obtenus sont très encouragants et des améliorations sont en cours.

Discussion

Dans cet article, nous avons traité le test des protocoles de communication tempsréel et à données. Le but était de réduire l'écart qui sépare les différents types et approches du test. Dans cet optique, nous avons présenté le modèle générique des systèmes communicants (CS) pouvant traiter différents types et modèles de test et dont la sémantique est définie en terme d'automate temporisé étendue à entrée/sortie (ETIOA). Ce modèle définit un ensemble d'entités (composantes) communicantes (modélisées par des ETIOAs), des ressources communes (données et paramètres partagées) aux différentes composantes et une topologie de communication qui explicite les différentes synchronisations possibles dans un état globale du système. L'introduction de la topologie dans la spécification offre des mécanismes de modélisation, de synchronisation et de génération plus adaptés au test des protocoles.

Ce modèle a été mis en oeuvre dans l'outil TGSE (Émulation, Simulation et Génération de Test). La version actuelle de TGSE peut être utilisée pour le test actif orienté objectif de test (à une ou plusieurs composantes) et le test passif, mais ne supporte qu'un CS à topologie statique et dont l' ETIOA sémantique est événementiellement déterministe. Notre travail actuel s'oriente à enlever ces restrictions en étendant la topologie dans TGSE et investiguer les techniques de détérminisation à la volée dans le cas temporel à l'exemple de la technique présentée dans [TRI 04]. Une intention particulière est portée sur la définition et l'incorporation dans TGSE du silence des états à l'exemple de [TRI 04, BRI 04].

Remerciements.

Nous tenons à remercier les membres de l'action spécifique AS 32 menée par Ana Cavalli pour leur remarques constructives. Nous remercions également les élèves de l'ENSEIRB Dimitri Kandassa, Jamel Semeh, David Dogoh et Carine Beduz pour leur participations dans la réalisation de TGSE.

  ou temporisés (TLTS) [BRI 04], les machines à états finies (FSM) [SEO 03], ou étendues (EFSM)[HIG 99], les automates à entrée/sortie temporisés (TIOA)[SPR 01]... Deux approches majeures sont alors utilisées pour tester : le test actif [CAR 00, CLA 97, DSS 98, HIG 99, KOU 00, SPR 01, BER 04, LAR 03, TRI 04, DSS 03, KOU 03], la dérivation se fait à partir d'une spécification (exprimée sous la forme d'une ou plusieurs entités communicantes) et le test passif [CAV 04] qui vérifie la validité d'une trace d'exécution d'une implémentation (la trace est une exécution valide).

Figure 1 .

 1 Figure 1. Exemple d'un ETIOA.

Définition 3 (

 3 Topologie) Une topologie de communication T op d'un ensemble de n processus est un 3-uplet (G, I, T r), avec G un ensemble fini d'actions globales, I = {I i } 1≤i≤n un ensemble fini d'ensembles d'actions et T r (traducteur) un automate T r = (S tr , L tr , s 0tr , → tr ) tel que les éléments de L tr sont des vecteurs -→ v à n + 1

  (a). T opS est une topologie statique. Le vecteur < G, L AB , L BA > est pour dénoter l'ensemble des vecteurs de la forme < g ab , a, b > tel que a ∈ L AB synchronise avec b ∈ L BA et leur synchronisation donne lieu à une action globale observable g ab . Un exemple de g ab peut être a si a est une émission et b si b est une émission (l'action visible d'une émission et une réception est une émission). De même, le vecteur < G A , L A \L AB , idle > est pour dénoter l'ensemble des vecteurs de la forme < g a , a, idle > tel que a ∈ L A \L AB . Dans le vecteur < g a , a, idle >, l'ETIOA A performe l'action a donnant lieu à une action globale observable g a . Quant à L'ETIOA B, il reste dans le même état (idle). L'ensemble G A correspond, en général, à l'ensemble L A \L AB . Finalement, T opS permet d'appliquer chaque vecteur de synchronisation (si c'est possible) dans un état global de S.Si on considère que les synchronisations des événements L AB avec les événements de L BA sont inobservables (comme c'est le cas pour l'architecture de test boîte noire) alors la modélisation de S en CS est CS 2 =< SP, SV, SV 0 , < A, B > , T opS >, avec T opS l'automate de la Figure2(b). Le vecteur < τ, a, b > de < τ, L AB , L BA >, considère que la synchronisation de a avec b donne lieu à une action interne τ . D'une façon générale, on peut modéliser la synchronisation en actions internes d'une partie des événements de synchronisations (comme c'est le cas pour une architecture de test).

Figure 3 .

 3 Figure 3. Test passif

Figure 4 .

 4 Figure 4. Test actif à une composante (1)

Figure 5 .

 5 Figure 5. Test actif à une composante (2)

SFigure 6 .

 6 Figure 6. Test actif à plusieurs composantes

Figure 7 .

 7 Figure 7. Exemples de spécifications

  est un ensemble de mises à jour sur les horloges et les variables.-T ⊆ S × L × P red × Ass × S est un ensemble de transitions.L'alphabet L d'un ETIOA est divisé en trois parties : L i l'alphabet des symboles d'entrée, L o l'alphabet des symboles de sortie et I l'alphabet des actions internes. Pour t ∈ T , t = (s, a, pred, ass, s ) est la transition de l'état s à l'état s sur l'occurrence du symbole a. pred ⊆ P red est une contrainte sur C et V et ass ⊆ Ass est l'ensemble des mises à jour sur C et V .

	Exemple 2 Un exemple d'ETIOA est donné dans la figure suivante.

  topologie de communication Top d'un ensemble de processus est un modèle de synchronisation des différents processus. Elle décrit les configurations dynamiques des processus et les synchronisations possibles dans une configuration donnée. La définition de Top est inspirée de celle d'Arnold [ARN 94, MAD 04]. Elle définit un ensemble d'actions globales, un ensemble d'ensembles d'actions et un Traducteur sous forme d'automate.

3. Méthodologie : Algorithme Générique de Génération.

  tr , s 1 , ..., s n ) de ζ(S) est conditionnée par l'existence d'une transition de T op de s tr à s tr sur un vecteur ayant comme action globale a. Ainsi, la sémantique d'un CS autorise la possibilité de synchronisation avec d'autres CSs, ce qui permet une définition hiérarchique des CSs et rend le modèle des CSs un modèle générique pour la modélisation des spécifications. La majorité des algorithmes de génération de test sont basés sur une recherche en profondeur d'un état ou d'une transition cible dans le graphe d'accessibilité. Il est alors possible de définir un algorithme générique de génération pour les différents types de test. Dans cette partie, nous montrons comment définir un tel algorithme. Un système communicant sous test (CSUT) est un système communicant S = (SP, SV, SV 0 , (M i ) 1≤i≤n , T op), tel qu'il existe au moins une entité M i , i ∈ [1, n], définissant un ou plusieurs états étiquetés par ACCEP T . Les états d'un CSUT étiquetés par ACCEP T définissent les comportements cibles à tester. Notre définition de CSUT ne considère que des états étiquetés par ACCEP T , mais il est possible de définir des transitions étiquetées par ACCEP T . Ce dernier cas n'est pas traité dans cet article, mais l'approche reste la même. Notons par CSUT l'ensemble de tous les CSUTs. Pour un S ∈ CSUT , un état s = (s tr , s 1 , ..., s n ) de ζ(S) et ρ = t 0 ...t Un algorithme gga est GGA pour CSUT , si gga appliqué à ζ(S) retourne un ensemble P AT H(S) contenant tous les chemins acceptables de ζ(S). Des exemples d'algorithmes GGA sont présentés dans [CAV 04, ZAI 99, CAL 04]. Signalons que l'algorithme Hit-or-Jump [ZAI 99] ne traite pas les aspects temporels des systèmes et considère des transitions ACCEP T au lieu des états ACCEP T .Finalement, un algorithme gga ne dépend pas d'un CSUT, il est exhaustif dans le sens que tout chemin acceptable est retourné par gga et en fin, le choix entre états ou transitions acceptables dépend du critère de couverture adopté.

	<G,LAB,LBA>		<τ ,LAB,LBA>
	<GA,LA\LAB,idle>	<GB ,idle,LB\LBA> <GA,LA\LAB ,idle>	<GB,idle,LB\LBA>
	(a) Topologie TopS	(b) Topologie TopS'
	Figure 2. Différentes topologies
	Définition 6 Définition 7 Définition 8 Un algorithme générique de génération (GGA) pour CSUT est un algo-
	rithme qui calcule, pour tout S ∈ CSUT , tous les chemins acceptables (s'ils existent)
	de ζ(S).

ass n }. La sémantique d'un CS S est définie en terme de l'ETIOA ζ(S). L'alphabet de ζ(S) est les actions globales G de T op. Un état de ζ(S) est constitué d'un état de T op et des états de (M i ) i∈[1,n] . Une transition (s tr , s 1 , ..., s n ) a,pred,ass

-------→ (s

n une suite de transitions dans ζ(S) de l'état initial : -s est dit un état acceptable de ζ(S) s'il existe i ∈ [1, n] tel que s i est un état étiqueté par ACCEP T . -ρ est dit un chemin acceptable de ζ(S), si 1) ρ est un chemin exécutable. 2) L'état destination de la transition t n est un état acceptable de ζ(S). Un état s de l'ETIOA ζ(S), sémantique de S, est un état acceptable de ζ(S) si l'un des états des entités qui le compose est un état étiqueté par ACCEP T . Un chemin ρ = t 0 ...t n dans ζ(S) de l'état initial est un chemin acceptable de ζ(S) si 1) l'état s n de la transition t n = (s n-1 , a, pred, ass, s n ) est un état acceptable de ζ(S) et 2) ρ est un chemin exécutable (faisable), c'est à dire, les différentes contraintes sur les transitions du ρ sont toutes vérifiées. L'exécutabilité d'un chemin est traité dans [CAV 04, CAL 04]. L'activité de test consiste alors à générer tous les chemins acceptables.

  génération orientée objectif de test. Ce genre de test peut considérer une ou plusieurs entités communicantes [CAR 00, CLA 97, DSS 98, HIG 99, KOU 00, MAN 95, SPR 01, BER 04, LAR 03, TRI 04]. En revanche, le test passif considère des traces d'exécution d'une implémentation, qui peuvent contenir des valeurs pour les variables et les horloges, et vérifie leur validité par rapport à la spécification. Dans les travaux relatifs au test passif [CAV 04], les auteurs considèrent une seule entité. Pour simplifier, appelons test à une composante le test d'une seule spécification (test de conformité) et test à plusieurs composantes le test de plusieurs spécifications (test d'interopérabilité, test dans le contexte, test de composants,...). Dans le reste de cette section, nous considérons que gga est un GGA. Le but de cette partie est de montrer que l'activité de test revient à modéliser un CS, en reportant les particularités

. Méthode de Génération TGSE

  TGSE [CAL 04] est un ensemble de logiciels regroupant les différentes activités du test. Il est composé d'un générateur de séquences de test basé sur le modèle CS, d'un simulateur à travers la plate-forme Calife permettant de simuler graphiquement l'exécution d'une séquence générée par TGSE et un émulateur temps réel des différentes spécifications communicantes. Le manque d'espace nous oblige à ne pas inclure les détails d'implémentation de TGSE, et le lecteur intéressé peut se référer au rapport interne [CAL 04]. Nous ne présentons ici que la génération de test dans TGSE . Le projet RNRT Calife et son successeur Averroès est un projet académique et industriel regroupant un ensemble de partenaires (France Telecom R&D, CRIL Technologie, Labri, LSV, Loria, LRI). Le but de ce projet est de définir une plate-forme générique (Open Source) permettant d'interfacer des outils de vérifications et de générations de test. Dans le cadre de ce projet, la participation du LaBRI est d'intégrer l'outil TGSE dans la plate-forme. La plate-forme Calife comporte un éditeur et un simulateur. L'éditeur fournie un interface agréable et facile à manipuler les différents types d'automates (Temoporisés, hybrides, étendus,...). Son simulateur permet de simuler graphiquement l'exécution d'un ensemble d'automates. L'entrée de TGSE est une description du CS sous une syntaxe simple permettant la définition des différentes entités du CS. Dans un soucis de réutilisation des composantes, chaque ETIOA du CS est défini dans un fichier séparé. Un fichier système décrit le chemin d'accès à chaque composante, ainsi que la topologie de communication. Dans sa version actuelle, TGSE implémente une topologie statique, mais supporte le test actif et passif à une ou plusieurs composantes. La sortie du TGSE est un fichier XML selon une DTD Calife définissant une séquence de test.TGSE peut être utilisé aussi en mode graphique à travers Calife. Dans ce cas, la saisie des spécifications est à travers l'éditeur Calife qui permet la génération automatiquement les vecteurs de synchronisation, ceci en offrant le choix d'une synchronisation par rendez-vous, broadcast, la synchronisation binaire d'Uppaal, ou par labels identiques. L'appel a TGSE se fait à travers l'interface graphique et Calife génère les fichiers d'entrée pour TGSE. TGSE produit un cas de test qui sera simulé sous Calife. Le schéma suivant représente les communications entre Calife TGSE. implémente un algorithme gga de recherche en profondeur à la volée de l'automate sémantique du CS. La recherche est paramétrée par le nombre maximal d'apparition d'une transition dans la séquence générée. Le choix des transitions, des vecteurs de synchronisations et des automates qui performent les actions est paramétré par des variables pour chaque donnée, dont les valeurs sont RANDOM, pour un choix aléatoire, et FIFO pour un respect de l'ordre d'apparition dans le définition du CS. L'algorithme gga calcule un chemin de l'état initial qui se termine sur un état ACCEP T . Durant la recherche en profondeur, plusieurs calculs sont effectués :Étape 1 : Calcul des successeurs.A partir d'un état courant s dans l'automate sémantique du CS, les vecteurs de synchronisations sont évalués d'une façon paramétrable pour calculer un état successeur s . Une API U pdateContext() est alors appelée. Étape 2 : Trace Symbolique [CAL 04] (Module contexte). L'API U pdateContext() calcule la trace symbolique des nouvelles transitions tirées. Ce module définit aussi l'API U pdateV arContext() qui permet la mise à jour du contexte lors du franchissement des transitions (les affectations des transitions). Une fois la trace symbolique est calculée, une API getSolution() est appelée. Dans le cas d'une trace paramétrée, getSolution() appelle la procédure du Module Paramètres getLpSolution() qui interagit avec l'outil de programmation linéaire lp_solve v4 pour instancier les paramètres. Dans le cas contraire, un appel à l'API getT imeExecution() du Module Horloges est effectué pour le calcul des exécutions en temps minimal et maximal [BER 04, CAL 04].

	5.1. Interface TGSE.
	Editeur Calife 5.2Étape 3 : Résolution des contraintes (Module Contraintes). Simulateur Calife TGSE

Étape 4 : Calcul d'un cas de Test (Module Trace).

Les paramètres et les variables partagées peuvent apparaître dans la définition d'une transition d'une entité.

.