République Algérienne Démocratique et Populaire

Ministère de l’Enseignement Supérieur et de la Recherche Scientifique

Université Mentouri de Constantine

Faculté des Science de l’Ingénieur

Département d’Informatique

Année :

N° d’ordre :

Série :

THESE

Pour l’obtention du diplôme de Docteur en 3éme cycle LMD

Option : Systèmes distribués

Test formel des systèmes temps réel : Approche de

transformation de graphes

Hiba HACHICHI

Soutenue le 17/03/ 2013 devant le jury composé de :

Pr Allaoua CHAOUI Président U.Mentouri. Constantine

Pr Djamel-Eddine SAIDOUNI Rapporteur U.Mentouri. Constantine

Pr Mohamed Taher KIMOUR Examinateur U.Badji Mokhtar.Annaba

Dr Abdelkrim AMIRAT Examinateur U.Souk-Ahras

Dr Salah MERNIZ Examinateur U.Mentouri. Constantine

Thèse préparée au laboratoire MISC, Université Mentouri de Constantine

Remerciement

J'adresse toute ma reconnaissance au Pr Djamel Eddine SAIDOUNI quia dirigé ce travail. Je le remercie pour sa disponibilité, son soutien et sa com-préhension durant toutes ces années de thèse.

Je tiens à remercier Mme Kitouni Ilham et Melle Kenza Bouarroudj pourleur coopération ainsi que leur esprit d'équipe.

Je remercie également les honorables membres de jury qui ont acceptéd'évaluer ce travail.

Je n'oublie pas de remercier particulièrement mes parents pour leur aide,leur soutien aussi bien matériel que moral ainsi que mes chéres s÷ures etmon petit frère.

je suis très reconnaissante envers mon mari pour sa compréhension, sonsoutien ainsi que les conseils qu'il m'a donnés.

J'adresse également mes remerciements à mes amies et mes collègues quim'ont soutenu durant ces années.

Résumé

Les méthodes formelles sont de plus en plus utilisées pour répondre auxexigences des systèmes critiques. Elles orent plusieurs approches : l'approchecomportementale, l'approche logique et l'approche test. Nous nous intéres-sons à l'approche test. D'abord, nous proposons une approche automatiséepour la déterminisation des DATA de grandes tailles. Nous proposons aussiune approche pour la génération d'un automate des régions agrégé à partird'un DATA*, le but de cette transformation est de fournir une abstractionnie d'un modèle DATA* de grande taille. Finalement, nous proposons uneapproche pour tester les systèmes temporisés. En eet, nous transformonsun DATA* en GRA dans le but de générer un testeur canonique ainsi quedes cas de test.Ces approches sont basées sur la transformation de graphes àl'aide de l'outil de modélisation AToM3.

Mots clé : Approche formelle de test, Transformation de graphes, DATA*,DATA, Automate des régions, AToM3.

Abstract

Formal methods are increasingly used to meet the requirements of cri-tical systems. They oer several approaches : behavioral approach, logicalapproach and testing approach. We are interested in testing approach. First,we propose an automated approach to determinize DATA structure with ahigh number of states. We propose also an approach for translating DATA*structure to aggregate region automaton. The purpose of this transformationis to provide a nite abstraction of DATA* with a high number of states.Finally, we propose an approach for testing timed systems. Indeed, we trans-form a DATA* into GRA in order to generate a canonical tester and testcases. These approaches are based on graph transformation using the mode-ling tool AToM3.

Keywords : Formal testing, Graph transformation, DATA*, DATA, Regionautomata, AToM3.

ملخص

و ةالسلوكيالطريقة ك :العديد من الطرق نھا توفرأذ ا ،لتلبية متطلبات النظم الحيوية منھجيةتزايد استخدام الطرق الي ا ليآنھجا نقترح حيث ختباريةبالطريقة ا, نھتم ي اطار ھذه ا,طروحةف .ةيا,ختبار الطريقة يضاأو ةالمنطقي الطريقة " un automate des régions agrégé " الى " *DATA" حويللت نقترح نھجا كما ،"DATA" النموذجلتحديد

نقوم حيث .يةنظم التوقيتال,ختبار ا، نقترح نھجفي ا,خير ." *DATA" تجريد منتھي للنموذج تقديم هوالغرض من ." Cas de test "كذلك و" testeur canonique" الحصول علىبھدف " GRA" الى "*DATA" بتحويل

. AToM 3 باستخدام أداة النمذجة بيانيالتعتمد ھذه المناھج على التحويل

.AToM 3, بيان المناطق, DATA*, DATA, بيانيالالتحويل , ا,ختبار المنھجي : الكلمات المفتاحية

Table des matières

I Problématique 1

1 Introduction Générale 21.1 Problématique . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Organisation du document . . . . . . . . . . . . . . . . . . . . 4

II Le test des systèmes : état de l'art 5

2 Validation des systèmes par le test 62.1 Caractéristiques du test . . . . . . . . . . . . . . . . . . . . . 6

2.1.1 Le pouvoir du test . . . . . . . . . . . . . . . . . . . . 62.1.2 Le coût du test . . . . . . . . . . . . . . . . . . . . . . 62.1.3 Catégories du test . . . . . . . . . . . . . . . . . . . . . 72.1.4 Les outils du test . . . . . . . . . . . . . . . . . . . . . 72.1.5 Les modes d'exécution du test . . . . . . . . . . . . . . 82.1.6 Types du test . . . . . . . . . . . . . . . . . . . . . . . 8

3 Test de conformité 113.1 La norme ISO/9646 relative au test de conformité . . . . . . . 12

3.1.1 La conformité . . . . . . . . . . . . . . . . . . . . . . . 123.1.2 Etapes du test de conformité . . . . . . . . . . . . . . . 133.1.3 Architecture du test à la norme ISO/9646 . . . . . . . 15

3.2 Les niveaux du test de conformité . . . . . . . . . . . . . . . 153.2.1 Tests d'interconnexion de base . . . . . . . . . . . . . 15

V

3.2.2 Tests de capacité . . . . . . . . . . . . . . . . . . . . . 153.2.3 Tests de comportement . . . . . . . . . . . . . . . . . . 163.2.4 Tests pour résoudre la question de conformité . . . . . 16

4 Méthodes de test 174.1 Le test de conformité des systèmes non temporisés . . . . . . 17

4.1.1 Méthodes fondées sur les automates . . . . . . . . . . . 174.1.2 Méthodes basées sur les LTS et les MLTS . . . . . . . 19

4.2 Le test de conformité des systèmes temporisés . . . . . . . . . 20

III Transformation de modèles : état de l'art 23

5 Transformation des modèles à l'aide de la transformation degraphes 245.1 Architecture dirigée par les modèles (MDA) . . . . . . . . . . 25

5.1.1 Modèle, Langage de modélisation et Méta-modèle . . . 255.1.2 Transformation de Modèles . . . . . . . . . . . . . . . 27

5.2 Transformation de graphes . . . . . . . . . . . . . . . . . . . . 315.2.1 Notion de graphe . . . . . . . . . . . . . . . . . . . . . 315.2.2 Grammaire de graphe . . . . . . . . . . . . . . . . . . 325.2.3 Outils de transformation de graphes . . . . . . . . . . . 34

IV Modélisations des systèmes 37

6 Modèles formels 386.1 Système de transitions étiquetées (LTS) . . . . . . . . . . . . 38

6.1.1 Notations standards des LTS . . . . . . . . . . . . . . . 396.2 Systèmes de transitions étiquetées maximales (MLTS) . . . . . 406.3 Le modéle des DATA "Durational Action Timed Automata" . 42

6.3.1 Formalisation du modèle des DATA . . . . . . . . . . . 436.4 Modèle des DATA* . . . . . . . . . . . . . . . . . . . . . . . . 44

6.4.1 Intuition . . . . . . . . . . . . . . . . . . . . . . . . . . 446.4.2 Expression de l'urgence . . . . . . . . . . . . . . . . . . 476.4.3 Formalisation . . . . . . . . . . . . . . . . . . . . . . . 48

V Contributions 50

7 Application de l'approche de transformation de graphes pourla déterminisation des DATA 51

VI

7.1 L'opération de déterminisation d'un DATA . . . . . . . . . . 517.1.1 Conditions générales sur la pratique du Modèle . . . . 527.1.2 Élimination des actions internes . . . . . . . . . . . . 52

7.2 Génération d'un DATA respectant la syntaxe d'AToM3 . . . . 537.3 Transformation d'un DATA à un DATA déterministe . . . . . 53

7.3.1 Méta-modèle d'un DATA . . . . . . . . . . . . . . . . . 547.3.2 Outil de modélisation d'un DATA . . . . . . . . . . . . 557.3.3 Grammaire de graphe proposée . . . . . . . . . . . . . 55

7.4 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

8 Transformation des DATA* sous format dotty en des auto-mates de régions agrégés 618.1 Automates des régions . . . . . . . . . . . . . . . . . . . . . . 62

8.1.1 Régions d'horloges . . . . . . . . . . . . . . . . . . . . 628.1.2 Dénition 8.1 . . . . . . . . . . . . . . . . . . . . . . . 628.1.3 Automate des régions . . . . . . . . . . . . . . . . . . 62

8.2 Automate des régions agrégé . . . . . . . . . . . . . . . . . . . 648.3 Génération d'un DATA* respectant la syntaxe d'AToM3 . . . 658.4 Transformation d'un DATA* à un automate des régions agrégé 66

8.4.1 Méta-modèle d'un DATA* . . . . . . . . . . . . . . . . 668.4.2 Méta-modèle d'un automate des régions agrégé . . . . 678.4.3 Outil de modélisation du DATA* et de l'automate des

régions Agrégé . . . . . . . . . . . . . . . . . . . . . . 688.4.4 La grammaire de graphe proposée . . . . . . . . . . . . 69

8.5 Cas d'étude . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

9 Application de l'approche de transformation de graphes pourle test des systèmes temporisés 739.1 Graphe de Refus Agrégé(GRA) . . . . . . . . . . . . . . . . . 73

9.1.1 Formalisation . . . . . . . . . . . . . . . . . . . . . . . 749.2 Génération d'un Graphe de Refus Agrégé(GRA) . . . . . . . . 759.3 Testeur canonique . . . . . . . . . . . . . . . . . . . . . . . . . 769.4 Transformation d'un DATA* à un Graphe de Refus Agrégé et

à un testeur canonique . . . . . . . . . . . . . . . . . . . . . . 769.4.1 Méta-modèle d'un Graphe de Refus Agrégé et d'un tes-

teur canonique . . . . . . . . . . . . . . . . . . . . . . 779.4.2 Outil de modélisation du Graphe de Refus Agrégé . . 789.4.3 La grammaire de graphe proposée . . . . . . . . . . . . 79

9.5 Cas d'étude . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

VII

Table des gures

3.1 Méthode de test . . . . . . . . . . . . . . . . . . . . . . . . . . 15

4.1 Spécication LTS (gauche) et un cas de test (droite) . . . . . . 194.2 GR et GRM associés aux machines M1 et M2 . . . . . . . . 21

5.1 Relation entre système, modèle et méta-modèle . . . . . . . . 265.2 Les quatre niveaux d'abstraction pour MDA . . . . . . . . . . 275.3 Concepts de base de la transformation de modèles . . . . . . . 285.4 Exemple d'un graphe G . . . . . . . . . . . . . . . . . . . . . 325.5 Graphe orienté étiqueté avec des entiers . . . . . . . . . . . . . 325.6 Graphe non orienté étiqueté avec des lettres . . . . . . . . . . 335.7 Présentation de l'outil AToM3 . . . . . . . . . . . . . . . . . 35

6.1 Système de transitions étiquetées maximales . . . . . . . . . . 416.2 Exemple d'un DATA . . . . . . . . . . . . . . . . . . . . . . . 436.3 DATA du comportement de S . . . . . . . . . . . . . . . . . . 456.4 DATA* du comportement de S . . . . . . . . . . . . . . . . . 466.5 Expression de l'urgence par un DATA* . . . . . . . . . . . . . 47

7.1 Représentation textuelle d'un DATA . . . . . . . . . . . . . . 537.2 Représentation d'un DATA sous l'environnement AToM3 . . 547.3 Étape de génération d'un DATA . . . . . . . . . . . . . . . . 547.4 Méta-modèle du DATA . . . . . . . . . . . . . . . . . . . . . 557.5 Outil de modélisation des automates DATA . . . . . . . . . . 567.6 Achage d'un message d'erreur . . . . . . . . . . . . . . . . . 567.7 Elimination de τ − cycle . . . . . . . . . . . . . . . . . . . . . 57

VIII

7.8 Élimination de τ − transition . . . . . . . . . . . . . . . . . . 577.9 Élimination des états inaccessibles . . . . . . . . . . . . . . . . 587.10 Enregistrement du DATA déterministe . . . . . . . . . . . . . 587.11 Le chier DATA . . . . . . . . . . . . . . . . . . . . . . . . . . 597.12 Le modèle DATA graphique . . . . . . . . . . . . . . . . . . . 597.13 Le modèle DATA déterministe . . . . . . . . . . . . . . . . . . 607.14 Le modèle DATA textuel déterministe . . . . . . . . . . . . . . 60

8.1 Régions d'horloges . . . . . . . . . . . . . . . . . . . . . . . . 638.2 DATA* A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 638.3 Automate des régions associé à A . . . . . . . . . . . . . . . . 648.4 Automate des régions agrégé associé à A . . . . . . . . . . . . 658.5 Représentation dotty d'un DATA* A . . . . . . . . . . . . . . 658.6 Étape de transformation (dotty-python) du DATA* A . . . . . 668.7 Représentation du DATA* A sous l'environnement AToM3 . . 668.8 Méta-modèle du DATA* . . . . . . . . . . . . . . . . . . . . . 678.9 Méta-modèle d'A.R. Agrégé . . . . . . . . . . . . . . . . . . . 688.10 Outil de modélisation des DATA* et A.R. Agrégé . . . . . . . 688.11 Génération de l'état initial d'un A.R. Agrégé (règle 1) . . . . 698.12 Génération des états d'un A.R. Agrégé et son enregistrement

(règles 2 et 3) . . . . . . . . . . . . . . . . . . . . . . . . . . . 698.13 Élimination des liens génériques (règles 4 et 5) . . . . . . . . 698.14 Suppression du modèle DATA* (règles 6,7,8 et 9) . . . . . . . 708.15 DATA* SRB présenté en dotty . . . . . . . . . . . . . . . . . 718.16 DATA* SRB présenté sous AToM3 . . . . . . . . . . . . . . . 718.17 A.R.Agrégé . . . . . . . . . . . . . . . . . . . . . . . . . . . . 728.18 Fichier texte correspondant à l'A.R.Agrégé . . . . . . . . . . 72

9.1 DATA*M représentant une machine à café . . . . . . . . . . 759.2 GRAM′ associé àM . . . . . . . . . . . . . . . . . . . . . . 759.3 Testeur canoniqueM” associé àM′ . . . . . . . . . . . . . . 779.4 Cas de test associé àM” . . . . . . . . . . . . . . . . . . . . . 779.5 Méta-modèle d'un GRA/testeur canonique . . . . . . . . . . 789.6 Outil de modélisation du GRA et du testeur canonique . . . . 799.7 Calcul de l'ensemble des refus associé à l'état initial du DATA*

(règle 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 799.8 Déterminisation et calcul des refus dans le cas d'un système

non-deterministe(règles 2) . . . . . . . . . . . . . . . . . . . . 809.9 Calcul des refus associés au reste du DATA* (règles 3 et 4) . 809.10 Génèration de la 1iere localité du GRA (règle 5) . . . . . . . 809.11 Génération du reste du GRA(règles 6 et 7) . . . . . . . . . . 81

IX

9.12 Génération des localités du GRA dans le cas d'un systèmenon-deterministe (règles 8 et 9) . . . . . . . . . . . . . . . . . 81

9.13 Génèration de la localité nale du GRA (règle 10) . . . . . . 819.14 Elimination des liens génériques entre DATA* et GRA (règles

11, 12 et 13) . . . . . . . . . . . . . . . . . . . . . . . . . . . 829.15 Elimination de la représentation graphique du DATA*(règles

14, 15 et 16) . . . . . . . . . . . . . . . . . . . . . . . . . . . 829.16 Génération de la première localité du testeur canonique(règle

17) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 829.17 Génération des localités du testeur canonique dans le cas d'un

système non-deterministe(règle 18) . . . . . . . . . . . . . . . 839.18 Génération du reste des localités du testeur canonique(règle

19) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 839.19 Génération de la localité nale du testeur canonique(règle 20) 839.20 Elimination des refus et la génération des cas de test(règles

21, 22 et 23) . . . . . . . . . . . . . . . . . . . . . . . . . . . 839.21 GRA SRB associé au DATA* SBR (8.16) . . . . . . . . . . . 849.22 testeur canonique SBR . . . . . . . . . . . . . . . . . . . . . . 859.23 Exemple d'un cas de test . . . . . . . . . . . . . . . . . . . . 85

X

Première partie

Problématique

1

Chapitre

1

Introduction Générale

Sommaire1.1 Problématique . . . . . . . . . . . . . . . . . . . . . 3

1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Organisation du document . . . . . . . . . . . . . . 4

De nos jours, les systèmes informatiques que ce soit simples ou complexessont de plus en plus utilisés au niveau de diérents domaines tel que la méde-cine, l'avionique, le domaine militaire...lesquels sont considérés comme étantdes domaines critiques et par conséquent le moindre échec ou défaillancerencontré durant la phase d'exploitation de ceux-ci peut engendrer des dé-gâts humains ou matériels considérables. Pour cette raison que ces systèmesdoivent être conçus de sorte à atteindre la qualité zero-erreur. Ces derniers,doivent être vériés d'une manière able et performante avant leur mise en÷uvre.

Il existe diérents moyens de vérication et de validation pour ces systèmes.En informatique, les méthodes formelles sont des techniques qui permettentun raisonnement rigoureux, à l'aide d'une sémantique et de modèle formel, surdes systèmes informatique ou même du matériel électronique an de prouverleur validité par rapport à un certain ensemble de propriétés bien dénies.Parconséquent le test des systèmes marque toujours un intérêt particulier parmiles domaines de recherche en informatique. Son objectif est de vérier qu'unproduit réalisé répond aux exigences dénies. Il existe plusieurs catégories detest pour vérier qu'une implémentation sera capable de fonctionner "cor-rectement" dans une situation réelle (opérationnelle). Parmi ces tests, lestests dits fonctionnels qui s'intéressent aux fonctionnalités d'un ou plusieurssystèmes sans prendre en compte leur structure interne. Les systèmes testéssont dits des "boîtes noires" dont le comportement n'est connu que par lesinteractions à travers leurs interfaces avec l'environnement. Parmi ces dié-rents types de tests fonctionnels, on peut distinguer :Le test de conformité, le

2

test d'interopérabilité, le test de robustesse et le test de performances.Dansce travail nous sommes intéressés au test de conformité.

1.1 Problématique

Les systèmes réactifs temps-réel intègrent de plus en plus de contraintes tem-porelles ; devant être respectées pour assurer l'intégrité de fonctionnementdu système. De ce fait,les modélisations ont pris en compte les contraintestemporelles inhérentes au système. Il est donc important de s'intéresser auxapproches permettant de dériver des séquences de test de conformité à partirde ce type de spécications temporisées.La diculté particulière de la prise en compte des contraintes temporellestient à ce que la représentation du temps continu conduit à des domaines devaleurs innis. En eet, les automates manipulant du temps dense ne peuventpas être analysés de manière énumérative.Pour résoudre ce problème,nous proposons dans ce travail une méthode detest automatisée qui s'appuie sur une discrétisation de l'espace d'états grâceau graphe de régions agrégé. L'automatisation de cette méthode est baséesur la transformation de graphes.La transformation de graphes facilite la modélisation des modèles qui sontdécrits comme des graphes, les transformations entre modèles sont eectuéespar réécriture des graphes et peuvent être décrites aussi comme des graphessous forme de grammaire de graphes. Chaque transformation prend des mo-dèles en entrée et produit des modèles en sortie.

1.2 Contributions

Dans ce travail nous utilisons les deux modèles DATA et DATA* [Belala et Saidouni, 2005][Belala, 2010] pour la modélisation des systèmes. Ces modèles suscitent deplus en plus d'intérêt particulièrement pour leur utilisation dans la valida-tion des systèmes. Ce sont des modèles temporisés qui observent dans leursémantique les durées des actions . Ces modèles reposent sur la sémantiquede maximalité [Courtiat et Saïdouni, 1995], [Saidouni, 1996] qui prône le vraiparallélisme, de ce point de vu ils se prêtent bien à la modélisation des sys-tèmes temps réel, concurrents et distribués.Nos contributions sont basées sur la transformation de graphes et réalisées àl'aide de l'outil AToM3 , elles peuvent se résumer en :• Transformer un DATA en un DATA déterministe.

3

• Transformer le modèle des DATA* de grandes tailles en des automates desrégions agrégés.• Proposer une approche pour la génération de test pour les systèmes temps-réel,elle consiste à transformer un DATA* à un Graphes de Refus Agrégé età un testeur canonique ainsi que la génération des cas de test.

1.3 Organisation du document

Le document est organisé comme suit :La première partie se consacre à l'introduction générale. La seconde partiede ce document se compose de trois chapitre, le chapitre 2 se concentre auxdiérentes notions sur le test, il présente les diérents types de test ainsique leur pouvoir de validation des systèmes. Le chapitre 3 présente la normestandard pour le test de conformité ainsi que les nouvelles recommandationspour la formalisation et l'automatisation du processus de génération de test.Dans chapitre 4 nous donnons un aperçu de méthodes formelles utilisablespour le test de conformité de systèmes réactifs.La deuxième partie sera dédiée à la transformation de modèles à l'aide detransformation de graphes. Nous donnerons un rappel sur l'architecture di-rigée par les modèles ou MDA (" Model Driven Architecture") qui est unedémarche de réalisation de logiciel, proposée et soutenue par l'OMG. MDAest une variante particulière de l'ingénierie dirigée par les modèles. Puis latransformation de graphes comme outil de transformation de modèles seraprésentée.Dans la troisième partie, nous rappelons les concepts de base relatifs auxquelques modèles utilisés dans le cadre de la modélisation des systèmes non-temporisés et ceux temporisés.La quatrième partie présente nos contributions. Nous achevons en n notredocument par une conclusion générale et des perspectives de recherches sug-gérées par ce travail.

4

Deuxième partie

Le test des systèmes : état de l'art

5

Chapitre

2 Validation des sys-

tèmes par le test

Sommaire2.1 Caractéristiques du test . . . . . . . . . . . . . . . . 6

Le test fait partie intégrante du développement du matériel ; il ne s'intéressequ'au produit nal, c'est-à-dire au comportement de l'exécutable correspon-dant. Cette activité a pour objectif d'exécuter le système, dans l'intentionde détecter une erreur [Myers, 1980]. Son exécution consiste à appliquer ausystème sous test un ensemble d'entrées et à observer les sorties an de dé-terminer si elles correspondent au cahier des charges.

2.1 Caractéristiques du test

2.1.1 Le pouvoir du test

L'objectif de la phase de test est de vérier que l'implémentation satisfait lesexigences spéciées par le cahier des charges, avant la mise en ÷uvre naledu système. Il faut cependant noter que le test ne permet pas de prouverl'absence d'erreurs ; il met seulement en évidence des dysfonctionnementséventuels [Prigent, 2003].

2.1.2 Le coût du test

Il est communément admis que le test couvre près de 50% du coût total dudéveloppement d'un système. La construction des séquences de test, à partirdu cahier des charges, est une phase laborieuse qui peut être source d'erreurs.De plus, les séquences de test écrites sont produites à partir de la liste desexigences du système. Ainsi, rien ne garantit l'absence de redondance ou lacomplétude de la suite de tests, c'est-à-dire l'absence d'un test nécessaire àla validation.

6

2.1.3 Catégories du test

Le choix du test correspond au type de validation que l'on souhaite eectuer.Ainsi, une diérence est faite entre test fonctionnel et test structurel.

Le test structurel ou test boîte blanche

Vise à analyser la structure interne du système. Celle-ci étant connue et c'esten fonction d'elle que s'eectue la sélection des cas de test. L'une des mé-thodes possibles est d'exécuter tous les chemins possibles du code. Le critèrede sélection exhaustif consiste à passer dans toutes les branches d'exécutiondu programme, ce qui est impossible à atteindre. Il dénit les éléments ducode parcourus par le test : on parle alors de "couverture". Cela permet,entre autres, de détecter des morceaux de programmes qui, présents dans lecode source, ne sont jamais réellement exécutés. Il s'agit de code mort quidoit être supprimé avant mise en service du logiciel.

Le test fonctionnel ou test boîte noire

A pour objectif d'analyser les comportements externes du système. Sa struc-ture interne n'est pas connue. L'objectif est de déterminer si le produit déve-loppé correspond aux fonctionnalités prévues. Il s'agit de soumettre l'implé-mentation sous test à des entrées et d'observer les sorties an de déterminerla validité des comportements. Les tests fonctionnels sont dénis à partir dela spécication. Il est donc nécessaire que celle-ci soit précise et ne renfermepas d'erreur.

Le test boîte grise

Est une forme hybride de test où les tests de types boîte blanche et boîtenoire sont utilisés de manière complémentaire. On applique des stratégies deboîtes noires en ayant connaissance de la structure du programme. Ce typed'approche est intéressant dans le cas des structures modulaires.

2.1.4 Les outils du test

Il existe des outils permettant d'automatiser la phase d'exécution des tests.Par exemple, Rational system test (anciennement ATTOL system test) per-met une exécution automatique des séquences de test sur une implémentation[Rational, 2003]. D'autres outils opèrent diéremment, ils permettent de sau-vegarder les séquences de test exécutées par un intervenant humain et rejouerces séquences de test sur le système.

7

2.1.5 Les modes d'exécution du test

Dans le cadre du test, on distingue généralement deux modes d'exécution :

Le test actif

Dans lequel le testeur stimule (contrôle) l'implémentation et observe ses ré-actions. En fonction de celles-ci, il décide du prochain stimulus à émettre.

Le test passif

Consiste à examiner le comportement (messages d'entrée/sortie) d'une im-plémentation sans pour autant imposer les entrées, ainsi le testeur passifn'aura pas à dénir une interface d'entrée sur l'IUT (Implementation UnderTest), il se contentera dans un premier lieu de récupérer une trace d'exé-cution. Une fois cette trace obtenue, on détermine si elle est conforme à laspécication. Si c'est le cas, on ne peut rien armer à propos de la validité del'implémentation, en eet une autre trace non observée pourrait révéler deserreurs. Sinon, on sait que l'implémentation n'est pas conforme. L'analyse decette trace permet au testeur d'émettre un verdict soit à l'issue du test, soitpendant le test si une faute se produit.

2.1.6 Types du test

Il existe plusieurs types de test adaptés aux comportements erronés que l'onsouhaite détecter sur l'implémentation. Dans [Belinfante et al., ]une classi-cation a été proposée, en fonction de l'aspect du système à tester. De ce fait,nous pouvons nous poser les questions suivantes : Le système se comporte-t-il de manière fonctionnelle, comme cela est prévupar sa spécication ?

Le système a-t-il les performances requises ? Comment le système se comporte-t-il si son environnement lui fournit desdonnées non prévues ?

Le système peut-il traiter un grand nombre d'entrées ? Pendant quelle durée est-il possible de faire conance au système ? Quelle est la disponibilité du système ?A partir de cette distinction sur la connaissance du système pour le testeur,plusieurs types de tests permettent de vérier des propriétés diérentes etpeuvent être classiés suivant leur appartenance aux types suivants : Test de conformité. Test d'une politique de sécurité. Test de performance.

8

Test d'interopérabilité/test d'inter-fonctionnement. Test de robustesse.

Le test de conformité

Vise à déterminer si l'implémentation est conforme à sa spécication en vé-riant que le comportement observable d'une implémentation correspond àcelui prévu par sa spécication, ce qui le rattache à la classe des tests fonc-tionnels ayant pour but de vérier que le système implémente correctementles fonctionnalités prévues par la spécication. C'est le type de tests dénidans ISO/9646.

Le test d'une politique de sécurité

Il vise le respect d'une politique de sécurité, c'est un test de conformitéd'une mise en ÷uvre (déployée sur l'ensemble des machines en réseau) d'unespécication de la sécurité. Il s'agit d'un test fonctionnel à posteriori aprèsdéploiement d'un ensemble d'éléments logiciels et matériels. C'est un testde conformité particulier pour des réseaux qui a fait l'objet de nombreusesétudes depuis la mise en place des interconnexions de machines au sein d'ar-chitectures ouvertes, en particulier dans le cadre des architectures de typeISO et Internet. Celui-ci s'appuie sur des notions essentielles pour une dé-marche formelle qui a permit de développer des outils d'analyse automatiquedes logiciels déployés pour la sécurité. Les étapes suivantes sont à respecterdans le cas du test d'une politique de sécurité : Une modélisation formelle de la politique de sécurité ou une formalisationde la relation de conformité entre le système à tester et la spécicationqu'il doit respecter.

Une dénition de l'architecture du test, en référence à l'architecture dusystème, qui exprime les capacités d'interaction (observation et contrôle)entre le système de test et le système à tester.

Dans le cas du test de politique de sécurité, certains événements observables(interaction entre deux machines distantes, variables d'environnement misesà jour par le système d'exploitation, etc.) ne peuvent pas toujours être connuspar le testeur pendant l'exécution du test. Ces événements, stockés au fur età mesure dans un journal de bord, ne sont alors disponibles qu'a posteriori.Le contrôle eectué par le testeur n'est donc que partiel. Un certain nombrede décisions doivent être prises arbitrairement, sans connaître complètementl'état du système sous test. De même, le verdict de test ne pourra être émisqu'après analyse de la séquence d'exécution, en fonction de l'état atteint dansl'arbre de test. Contrairement aux principes du test actif. C'est pour quoi,

9

dans le cadre du test de la politique de sécurité, les deux modes d'exécutionsdes tests restent envisageables [Darmaillacq et al., 2004].

Le test de performance

Est une spécialisation du test de conformité qui teste les aspects temporelsd'une spécication comportementale. Il est alors indiqué dans le cas d'uneformalisation d'utiliser un modèle capable de prendre en compte l'aspecttemporel permettant de spécier des propriétés temporelles [Kitouni, 2008].

Le test d'interopérabilité/test d'inter-fonctionnement

Ce type de tests est une autre spécialisation du test de conformité qui testeles aspects d'interopérabilité ou d'inter-fonctionnement de ces systèmes. Ce-pendant il faut dissocier ces deux types de spécications : le test d'inter-opérabilité vise à vérier si deux ou plusieurs composants d'un système ré-parti peuvent communiquer entre eux ; le test d'inter-fonctionnement néces-site d'une part l'interopérabilité et d'autre part le test du comportementdynamique des systèmes répartis [Kitouni, 2008].

Le test de robustesse

Il consiste à s'assurer que le système réagit correctement en milieu hostile,dans des situations non prévues au niveau de la spécication. En eet, dansce genre de milieux, le système va être soumis à toutes sortes d'aléas qu'il estmalheureusement impossible de prédire, mais qu'il faut malgré tout anticiper[Rollet, 2004].

10

Chapitre

3

Test de conformité

Sommaire3.1 La norme ISO/9646 relative au test de conformité 12

3.2 Les niveaux du test de conformité . . . . . . . . . 15

Le test de conformité a été développé pour la validation des protocoles decommunication, il permet de vérier qu'une implémentation satisfait les com-portements prévus par sa spécication. Le test de conformité s'intéresse uni-quement aux comportements observables de l'implémentation. Cette dernièreest considérée comme une boîte noire dont on ne connaît pas le fonctionne-ment interne. En pratique, le test de conformité consiste à faire interagirl'implémentation sous test (IUT pour Implementation Under Test) avec sonenvironnement. Cet environnement, qui est constitué par un ou plusieursprocessus ou utilisateurs, est simulé par un ou un ensemble de testeurs. Cestesteurs exécutent des tests élémentaires appelés cas de test qui consistent enune suite d'interactions. Cette suite d'interactions contrôle l'IUT par des sti-muli (des envois de messages, des appels de fonctions, de méthodes, etc...) etobserve ses réactions (messages reçus, résultats d'appels, etc....). Les compor-tements de l'IUT sont contrôlés et observés à travers des interfaces (appeléesPCOs pour "Points of Control and Observation" dans le monde télécoms).Généralement, chaque cas de test a pour objectif le test d'une fonctionnalitéprécise, décrite dans ce qu'on appelle un objectif de test. An de garantirque des tests de conformité d'une même implémentation, eectués par deséquipes diérentes, fournissent les mêmes résultats, il est important de dé-nir clairement les notions de conformité, de séquences de test et de verdict.Ces éléments doivent être dénis et standardisés. C'est dans cet objectif quel'ISO, en accord avec l'ITU (l'Union Internationale de Télécommunication),a développé un standard pour le test de conformité des systèmes ouverts.Le standard, désigné sous le sigle ISO/9646, produit un cadre méthodolo-gique de description et d'exécution des suites de test permettant d'établir laconformité d'un composant. C'est pourquoi les techniques de génération au-tomatique de tests, basées sur une spécication formelle du système, sont un

11

apport majeur pour les développements industriels. Dans ce chapitre, nousprésentons le concept de test de conformité et la norme qui le standardise,l'ISO/9646.

3.1 La norme ISO/9646 relative au test de confor-

mité

La norme, ISO "Conformance Testing Methodology and framework", dé-nit un cadre méthodologique de test de conformité des systèmes. Selonl'ISO/9646, il est possible de distinguer trois phases dans le processus de testde conformité. Une première phase correspond à la dérivation des séquencesabstraites de test. Ensuite, ces séquences abstraites sont transformées en sé-quences de test exécutables : c'est l'étape d'implémentation des tests. Enn,l'exécution des séquences de test sur l'IUT et l'analyse du résultat, per-mettent d'obtenir le verdict sur la conformité. Les résultats de l'exécutionsont documentés par le PCTR (Protocol Conformance Test Report). Tret-mans propose dans [Tretmans, 2001]une synthèse des concepts dénis parcette norme. Nous en donnons ici les grands axes. La norme ISO/9646 a étédénie pour des protocoles spéciés en langage naturel. En fait au départ,elle a été développée pour les protocoles ISO, mais elle est utilisée pour testertous les types de protocoles (ISDN, GSM). On la retrouve bien entendu dansle domaine des systèmes à objets répartis et plus particulièrement dans lagestion de réseaux ISO [Kaboré, 1995] [Baer, 1993]. Cette norme comprendquatre parties : la partie 1 est une introduction qui traite des concepts généraux ; la partie 2 décrit le processus de spécication des suites de tests ; la partie 3 dénit la notation TTCN (Tree and Tabular Combined Nota-tion) ;

la partie 4 traite de la réalisation du test.

3.1.1 La conformité

La première étape consiste à dénir précisément la relation de conformitéentre la spécication et l'implémentation. Les contraintes de conformité sontexplicitement indiquées dans la norme du protocole. Elles indiquent ce qu'uneimplémentation conforme doit faire et ce qu'elle ne doit pas faire. Toutes lesoptions qui ont été réalisées dans une implémentation donnée sont listéesdans les PICSs (Protocol Implementation Conformance Statement). Des res-trictions dans la sélection sont données par l'intermédiaire de deux types de

12

contraintes : les contraintes statiques de conformité et les contraintes dy-namiques de conformité. Les contraintes statiques dénissent les capacitésminimales qu'une implémentation doit avoir (les combinaisons possibles desoptions) ; Les contraintes dynamiques (la plus grande et la plus importantepart de la norme) dénissent le comportement observable de l'implémentationlors de la communication avec son environnement : l'ordre des événements, lecodage des informations dans les PDU (Protocol Data Unit) et les relationsentre les PDU. Le test de conformité a alors pour fonction de s'assurer quel'implémentation satisfait les exigences dynamiques et statiques de confor-mité spéciées par le PICS [Prigent, 2003].

3.1.2 Etapes du test de conformité

[Prigent, 2003][Kitouni, 2008]

Dérivation des séquences de test

La première étape du processus de test de conformité est de générer lesséquences de test abstraites à partir de la spécication du protocole. Lesséquences de test sont construites à partir des exigences de conformité dyna-miques. Dans un premier temps, les objectifs de test sont dérivés à partir detoutes les exigences de conformité. Un objectif de test correspond à une des-cription détaillée de ce qui doit être testé pour la vérication d'une exigenceparticulière de conformité.Deux niveaux de cas de test :

1. Cas de test générique qui est une séquence de test contenant des opé-rations nécessaire a la vérication de l'objectif de test.

2. Cas de test abstrait qui ne tient pas compte de l'environnement ni de laméthode de test choisie. La norme ISO/ 9646 recommande par chaqueobjectif de test la construction d'un cas de test générique, à partir duquel un cas de test abstrait est généré.

Implémentation des séquences de test

La seconde étape est l'implémentation des séquences de test permettant derendre exécutable la séquence de test pour une IUT spécique.

1. Sélection des tests : la première étape est une sélection des tests parmil'ensemble des séquences de test abstraites obtenues. Cette sélectionconcerne les tests correspondant à des comportements qui n'ont pas étéimplémentés pour l'IUT que nous souhaitons tester. Les tests pertinentssont sélectionnés en fonction des PICS.

13

2. Implémentation des tests : pour construire les séquences de test exécu-tables, il est indispensable de tenir compte des particularités de l'IUTet de son environnement. Le PIXIT (Protocol Implementation eXtraInformation for Testing) contient les informations nécessaires. Les testsimplémentés sont les tests obtenus après la phase de sélection des testsauxquels on a ajouté les informations contenues dans le PIXIT.

3. Format des séquences de test : ISO9646 recommande l'utilisation dulangage TTCN (Tree and Tabular Combined Notation) pour la notationdes séquences de test. Une suite de tests de ce format est composéede quatre parties : un résumé, une zone de déclaration, une partiecontraintes et une partie dynamique. Un cas de test est un arbre danslequel chaque branche décrit une séquence d'interaction entre le testeuret l'IUT.

Exécution des tests

L'exécution des tests applique les séquences de test implémentées pour uneIUT particulière an d'établir le verdict de conformité. La première étapeest une vérication de la conformité statique. Les PICS sont observés pourdéterminer s'ils répondent aux exigences de conformité du standard. La se-conde étape de l'exécution est d'appliquer les séquences de test exécutablessur l'implémentation. Chaque séquence de test exécutée produit un verdict.Ce verdict peut être :

Pass : le test a été exécuté avec succès et la propriété exprimée par l'objectifde test est vériée.

Fail : le test a permis de conclure que l'implémentation n'était pas conformeà la spécication.

Inconclusive : l'exécution de la séquence de test ne permet pas d'établirla non conformité, mais la propriété correspondante à l'objectif de testn'est pas respectée par l'implémentation.

Les résultats de l'exécution de tous les tests statiques ou dynamiques sontcombinés pour établir le verdict nal de conformité. Un verdict Pass estobtenu seulement dans le cas ou aucun des tests individuels eectués n'aproduit de résultat Fail. Les résultats individuels de chaque test et le verdictnal sont rapportés dans un document : le PCTR (Protocol ConformanceTest Report). La gure (3.1) illustre cette technique.

14

Figure 3.1 Méthode de test

3.1.3 Architecture du test à la norme ISO/9646

Les points où le testeur contrôle l'implémentation s'appellent des PCOs(Points of Control and Observation). L'implémentation sous test (IUT) estobservable uniquement par l'intermédiaire de ces PCOs. Selon la normeISO9646, il existe deux types d'architecture de test :

L'architecture locale : Le testeur et l'IUT sont exécutés sur une mêmemachine. Ce type de campagne de test est appliqué, par exemple, autest de logiciel.

L'architecture globale : pour un système distribué, réparti et distant. Pource type d'architecture, il est nécessaire de quantier les délais et de lesprendre en compte lors de la création des tests.

3.2 Les niveaux du test de conformité

La norme ISO/9646 décrit les diérents niveaux de test suivants [Khorchef, 2006] :

3.2.1 Tests d'interconnexion de base

Ils permettent de vérier les caractéristiques principales du protocole (lesinterconnexions de base), en particulier la capacité à ouvrir des connexions,transmettre des données et fermer des connexions.

3.2.2 Tests de capacité

ils permettent de vérier si toutes les possibilités statiques (externes et ob-servables) de l'exécution sont valides par rapport aux contraintes statique de

15

la conformité (options, classe de protocole, etc).

3.2.3 Tests de comportement

ils consistent à vérier la conformité pendant l'exécution par rapport auxconditions d'exécution dynamiques dénies dans la norme de protocole.

3.2.4 Tests pour résoudre la question de conformité

ils regroupent des tests spéciaux visant des objectifs au-delà des objectifsvisés par le test de comportement (par exemple, les exceptions).

Conclusion

Depuis plus d'une trentaine d'années, la génération automatique de testsest perçue comme l'une des applications les plus rentables des techniques despécications formelles. Vu l'importance en terme de temps et de coût desphases de test, les chercheurs et praticiens du test ont cherché depuis plu-sieurs années à automatiser cette phase. Ainsi, de nombreuses méthodes degénération automatique de test de conformité ont vu le jour. Malheureuse-ment, peu d'entre elles sont utilisées en pratique et les tests sont encore écritsà la main à partir de spécications informelles. Cette situation est particuliè-rement vraie dans le contexte des systèmes temporisés qui forment le cadrede travail de cette thèse.

16

Chapitre

4

Méthodes de test

Sommaire4.1 Le test de conformité des systèmes non tempo-

risés . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4.2 Le test de conformité des systèmes temporisés . . 20

L'objectif de ce chapitre est de donner un aperçu de méthodes formellesutilisables pour le test de conformité de systèmes réactifs.

4.1 Le test de conformité des systèmes non tem-

porisés

4.1.1 Méthodes fondées sur les automates

La première classe de méthodes est basée sur une spécication représentée àbase de Machines de Mealy. Le principe du test pour ce type de modèle est dedéterminer si les machines I et S, représentant respectivement l'implémenta-tion et la spécication, sont équivalentes. Plusieurs algorithmes permettentde détecter si deux machines sont équivalentes. Nous présentons ici les tech-niques suivantes :Tour de transitions [Naito et Tsunoyama, 1981], séquencede distinction :DS Method [Kohavi, 1978], séquence de caractérisation : Wmethod [Chow, 1978] et enn séquence unique d'entrée/sorties : UIO method[Lee et Yannakakis, 1996].

Tour de transition

Un tour de transition TT est une séquence de transitions permettant depasser par chaque transition au moins une fois. Un tour minimal peut êtreobtenu par le chemin d'Euler. La méthode TT permet de détecter toutes lesfautes de sorties mais peut ignorer certaines fautes de transfert car aucunevérication n'est eectuée pour contrôler l'état d'arrivée. L'application de

17

cette technique exige la forte connexité, la complétude et le déterminisme dela machine à état nis (FSM) de la spécication [Khorchef, 2006].

Méthode de séquence de distinction :DS Method

Une séquence de distinction DS Method est une suite d'entrées provoquantune suite de sorties diérentes pour chaque état de la FSM auquel elle est ap-pliquée. Tout état est donc identiable grâce à cette séquence. La constructiondes séquences de test consiste en la concaténation de trois parties permet-tant respectivement de synchroniser la FSM à tester, de tester les transitionset d'identier les états. Une séquence de synchronisation SS est une suited'entrées provoquant le transfert dans un état de synchronisation quel quesoit le point d'application de cette séquence. Un reset est une séquence desynchronisation dans l'état initial. La méthode DS est applicable à des FSMdéterministes, fortement connexes et pour lesquels il existe une DS et une SS[Khorchef, 2006].

Séquence de caractérisation : W method

Un ensemble de caractérisation W est un ensemble de séquences d'entréespermettant d'identier chaque état dans la spécication. Une séquence d'en-trées W distingue deux états si, appliquée respectivement à chacun des états,elle produit des sorties diérentes. Cette méthode consiste à accéder aux dif-férents états à l'aide d'un ensemble P de préambules couvrant les transitionsde la spécication et à tenter de les distinguer les uns des autres par unensemble W de séquence d'entrées. Le point fort de cette méthode est sa ca-pacité de détecter les fautes de transfert et de sortie. Toutefois, il se peut qu'iln'existe pas de séquence de distinction pour chaque état [Khorchef, 2006].

Séquence unique d'entrée/sorties : UIO method

une UIO (unique input output) est une séquence d'entrée et de sortie décri-vant le comportement de la spécication de façon unique. Par conséquent,chaque état est identiable grâce à cette séquence d'entrées et de sorties.Si un état q n'a pas d'UIO, alors, on utilise une signature qui est un en-semble de séquences d'entrées-sorties minimales ayant pour origine l'état qet elles sont capables de distinguer cet état des autres états de la FSM. Cesséquences sont concaténées avec les séquences de transfert an de ramener laFSM à l'état q après chaque séquence. Cette méthode détecte les fautes desortie et de transfert. En revanche, elle est applicable qu'à des FSM détermi-nistes, complètement spéciées, minimales, fortement connexes et possédantune séquence UIO pour chaque état [Khorchef, 2006].

18

4.1.2 Méthodes basées sur les LTS et les MLTS

Avec le modèle des LTS, les approches sont assez similaires que pour les FSM.Toutefois, des relations de conformité diérentes sont utilisées. On peut citerla bissimulation, ou les preordres (failure equivalence and preorder, testingequivalence and preorder, refusal preorder, etc...). Tretmans [Tretmans, 1996][Tretmans, 1997] [Tretmans, 2001] généralise ces relations en introduisant lanotion d'observateur : un LTS p est équivalent à un LTS q si n'importe quelobservateur peut faire exactement les mêmes observations avec p qu'avec q.Il (re)dénit ainsi diérentes relations sur des LTS(relations testing preorder,conf, refusal preorder),ou des IOLTS(une extension des LTS qui distingue lesactions d'entrée des actions de sortie).les relations étudiées sont les suivantes :relations input-output testing, ioconf, input-output refusal, ioco, ioconf.Tretmans dénit un cas de test aussi comme un IOLTS, et donne un algo-rithme (récursif) pour le générer. le principe est de tester à chaque fois toutesles entrées possibles, et de prévoir le résultat pour chaque réponse éventuelledu système ( pass ou fail). En suite, selon le choix de la relation, une machinesera considérée comme conforme ou non [Rollet, 2004]. La gure (4.1) montreun exemple de spécication et de cas de test correspondant.

Figure 4.1 Spécication LTS (gauche) et un cas de test (droite)

Les théories proposées dans [Hennessy, 1985], [Brinksma et al., 1987], [Brinksma, 1988],[Drira, 1992] ont permit la dénition d'un modèle entièrement abstrait appeléGraphe de Refus permettant une représentation des systèmes communicant

19

se basant sur une sémantique proche de la sémantique de refus "failure se-mantics" de CSP [Hoare, 1985] et un formalisme similaire au "failure tree" de[Brinksma, 1988] mais permet de décrire les comportements récursifs et sup-porte des dénitions opérationnelles des relation de conformité [Drira, 1992].L'approche des graphes de refus s'inscrit dans les méthodes formelles pourle test de conformité des systèmes non temporisés. Elle consiste en la créa-tion d'un testeur capable de détecter si l'implémentation viole la relation deconformité et cela par l'exécution en parallèle de l'implémentation sous testet du testeur. Le testeur dans ce cas est fabriqué à partir d'une spécicationsous forme de système de transitions en utilisant un graphe de refus, ce der-nier est un système de transitions déterministe où les n÷uds sont augmentéspar les actions interdites. Intuitivement un graphe de refus est un systèmede transitions étiquetées déterministe tel que à chaque état est associé unensemble de refus incluant les ensembles d'actions sur lesquelles le systèmepeut se bloquer. Dans [Drira, 1992] le modèle des graphes de refus est étudiéainsi que toutes les propriétés le concernant sont prouvées. A titre d'exemple,reconsidérons l'exemple des distributeurs de café M1 et M2 dont les spéci-cations respectives sont données par les expressions de comportement BasicLOTOS suivantes : M1 = p; c; c; stop et M2 = p; (c; stop|||c; stop). Les deuxmachines M1 et M2 admettent le même système de transitions étiquetées(LTS) et par voie de conséquence elles admettent le même graphe de refus, re-présentés respectivement par les gures (4.2).(a) et (4.2).(b). Ceci a motivé laproposition du modèle des Graphes de Refus Mixtes (GRM)[Saidouni, 1996][Chaoui et al., 2010] incluant à la fois les blocages classiques, qualiés depermanents, et les blocages temporaires. Il est évident que cette notion deblocage temporaire introduite est intrinsèquement liée à la non atomicitétemporelle des actions. Cette remarque a conduit à l'adoption de la séman-tique de maximalité qui permet d'échapper à l'hypothèse d'atomicité desactions, le modèle utilisé est celui des MLTS (systèmes de transitions étique-tées maximales)[Courtiat et Saïdouni, 1995], [Saidouni, 1996].

4.2 Le test de conformité des systèmes tempo-

risés

Depuis 1994, certaines études portent sur la construction de séquences detest pour les systèmes temps-réel. Ces approches sont basées sur une modéli-sation temporisée du système à tester. La diculté particulière de la prise encompte des contraintes temporelles tient à ce que la représentation du tempscontinu conduit à des domaines de valeurs innis. En eet, les automates

20

Figure 4.2 GR et GRM associés aux machines M1 et M2

manipulant du temps dense ne peuvent pas être analysés de manière énumé-rative. Une discrétisation de l'espace d'états permet de résoudre le problème.Certaines approches [Laurençot et al., 2000], [Dssouli et al., 1997], [Salva et al., 2001]utilisent le graphe de régions. Le problème de ces approches est que lacomplexité de construction du graphe de régions est exponentielle par rap-port au nombre d'horloges du système. Une autre méthode présentée dans[Nielsen, 2000] utilise des techniques de Model-Checking par résolution decontraintes. Ce type de méthode n'est pas limité par le nombre d'horloges.Les techniques présentées par [Laurençot et al., 2000], [Dssouli et al., 1997],[Salva et al., 2001] utilisent le produit synchrone entre un objectif de test etune spécication. Cette sélection permet de réduire les comportements à par-courir sur le système. [Nielsen, 2000] propose une technique de constructiondes séquences de test basée sur une extension temporisée de la théorie dutest fondée sur les systèmes de transitions.l'approche proposée dans [Prigent, 2003] est basée sur l'utilisation de la sé-lection des tests par objectif de test, elle permet de limiter les compor-tements explorés au cours de la génération. Contrairement aux méthodesutilisant le graphe de régions [Laurençot et al., 2000], [Dssouli et al., 1997],[Salva et al., 2001],dans cette approche, la génération des contraintes tempo-relles et des traces par une analyse d'accessibilité symbolique permet de ne

21

pas être limité par le nombre d'horloges dans le système.[Krichen et Tripakis, 2004] se base sur la relation de conformité tioco quiétend ioco au cas temporisé. Deux types de tests sont considérés : des testsanalogiques qui permettent de mesurer le temps précisément, et des testsnumériques qui mesurent le temps par une horloge périodique, moins précisque les premiers, mais implémentables en pratique.

Conclusion

Ce chapitre nous a permis de voir un état de l'art sur les diérentes ap-proches pour la génération des tests de conformité pour les systèmes nontemporisés et les systèmes temporisés. Ces approches peuvent présenter cer-taines limitations. En eet, l'utilisation reste limitée par des problèmes telsque l'explosion combinatoire, un nombre trop grand de séquences de testsgénérées et des délais sur les séquences de test trop petits.Une génération de test doit permettre de produire des séquences de test dequalité. En eet, les tests générés doivent être en nombre ni et raisonnablesur des intervalles de temps en adéquation avec les ordres de grandeur de laspécication.

22

Troisième partie

Transformation de modèles : état

de l'art

23

Chapitre

5

Transformation des

modèles à l'aide de

la transformation de

graphes

Sommaire5.1 Architecture dirigée par les modèles (MDA) . . . 25

5.2 Transformation de graphes . . . . . . . . . . . . . . 31

L'Ingénierie Dirigée par les Modèles (IDM, ou MDE : Model Driven Enginee-ring) est utilisée principalement dans le domaine des logiciels, elle a permisplusieurs améliorations signicatives dans le processus de développement desystèmes complexes en se concentrant sur des préoccupations plus abstraitesautour des modèles utilisés sur la programmation classique (le code). L'IDMore un cadre méthodologique et technologique qui permet d'unier dié-rentes façons de faire dans un processus homogène. Il est ainsi possible d'uti-liser la technologie la mieux adaptée à chacune des étapes du développementdu logiciel, tout en ayant un processus global de développement qui soit uniédans un paradigme unique.L'IDM permet cette unication grâce à l'utilisation importante des modèles(qui peuvent être exprimés dans des formalismes diérents) et des transfor-mations automatiques entre les modèles. les transformations permettent depasser d'un espace technique à un autre ainsi, elles permettent de choisirl'espace technique et le formalisme le plus adapté à chaque activité.Dans ce chapitre nous commençons par une présentation des concepts de basepour la transformation de modèles (dans le cadre général). Par la suite, nousexposerons quelques types de ces transformations, ainsi que leur classication.Nous focaliserons par ranement sur la transformation de graphes commeétant un type spécique de la transformation de modèles.

24

5.1 Architecture dirigée par les modèles (MDA)

L'architecture dirigée par les modèles ou Model Driven Architecture est unedémarche de réalisation de logiciel, proposée et soutenue par l'OMG 1. L'idéede base de cette approche est de dénir des modèles métiers indépendantsde l'informatisation (Computation Independent Model, CIM), on transformeces CIM pour obtenir des modèles totalement indépendants des plates-formestechniques (Platform Independent Model, PIM), par la suite, on rane cesPIM pour prendre en considération les problèmes liés à la technologie retenueet on obtient des modèles spécique à la plate-forme cible (Platform SpecicModel, PSM).

5.1.1 Modèle, Langage de modélisation et Méta-modèle

Un modèle est une abstraction de la réalité, il met l'accent sur certains aspectsdu système et ignore d'autres (c'est une représentation simpliée). Son butest de permettre une étude plus simple dans un contexte maîtrisé autre quele contexte réel. Au niveau du MDA les modèles manipulés sont de naturesdiverses : modèles d'objets métiers, de processus, de service, de plate-forme,de transformation et de tests. On peut distinguer trois classes de modèles :

Le modèle CIM : le CIM (Computational Independent Model) correspondau modèle des besoins au niveau métier. Il permet de recenser les dif-férents besoins du clients indépendamment de toute implémentation.

Le modèle PIM : le PIM (Platform Independent Model) correspond aumodèle de spécication de la partie métier d'une application. Cettespécication doit être conforme à une analyse informatique cherchantà répondre aux besoins métiers indépendamment de la technologie demise en ÷uvre.

Le modèle PSM : le PSM (Platform Specic Model) correspond au mo-dèle de conception et d'implémentation d'une application par rapportà une plateforme spécique.

La notion de modèle dans l'IDM fait explicitement référence à la notion deformalisme ou de langage de modélisation bien déni. Un langage de mo-délisation est déni par une syntaxe abstraite, une syntaxe concrète et unesémantique. La syntaxe abstraite dénit les concepts de base du langage.La syntaxe concrète dénit le type de notation qui sera utilisé pour chaqueconcept abstrait qui peut être graphique, textuelle ou mixte. Enn, la séman-tique dénit comment les concepts du langage doivent être interprétés par les

1. OMG : Object Modeling Group

25

concepteurs mais surtout par les machines. En eet, pour qu'un modèle soitproductif, il doit pouvoir être manipulé par une machine. Le langage danslequel ce modèle est exprimé doit donc être clairement déni. De manièrenaturelle, la dénition d'un langage de modélisation a pris la forme d'un mo-dèle, appelé Méta-modèle [Kerkouche, 2011].Un méta-modèle est un modèle qui dénit le langage d'expression d'un mo-dèle. Autrement dit, le méta-modèle représente (modélise) les entités d'unlangage, leurs relations ainsi que leurs contraintes, c'est-à-dire une spécica-tion de la syntaxe du langage. Le Méta-modèle à son tour est exprimé dansun langage de méta-modélisation spécié par le Méta-Méta-modèle. Le lan-gage utilisé au niveau du méta-méta-modèle doit être susamment puissantpour spécier sa propre syntaxe abstraite et ce niveau d'abstraction demeurelargement susant (méta-circulaire). Chaque élément du modèle est une ins-tance d'un élément du méta-modèle [Kerkouche, 2011].Un modèle est dit conforme à un méta-modèle et constitue une représentationd'un système existant ou imaginaire. La relation entre un méta-méta-modèleet un méta-modèle est analogue à la relation entre un méta-modèle et unmodèle. Cette relation est illustrée dans la gure(5.1) [Kerkouche, 2011].

Figure 5.1 Relation entre système, modèle et méta-modèle

OMG [Group, 2004] a déni une architecture à quatre niveaux d'abstrac-tion, comme carde général pour l'intégration des méta-modèles, en se basantsur MOF 2 comme le montre la gure (5.2 [Group, 2004]). Dans cette ar-chitecture, les modèles de deux niveaux adjacents sont liés par une relationd'instanciation [Bahri, 2011] :

2. MOF :Méta Object Facility, permet la dénition des éléments essentiels, la syntaxe

et la structure des méta-modèles

26

Figure 5.2 Les quatre niveaux d'abstraction pour MDA

Le niveau M0 : Niveau des instances des modèles. Il dénit des informa-tions pour la modélisation des objets du monde réel.

Le niveau M1 : Ce niveau représente toutes les instances d'un méta-modèle.Les modèles du niveau M1 doivent être exprimés dans un langage déniau niveau M2. UML est un exemple de modèles du niveau M1.

Le niveau M2 : Ce niveau représente toutes les instances d'un méta-méta-modèle. Il est composé de langages de spécications de modèles d'infor-mation. Le méta-modèle UML qui est décrit dans le standard UML etqui dénit la structure interne des modèles UML, appartient au niveauM2.

Le niveau M3 : Ce niveau dénit un langage unique pour la spécicationdes méta-modèles. Le MOF élément réexif du niveau M3, dénit lastructure de tous les méta-modèles du niveau M2.

5.1.2 Transformation de Modèles

La transformation de modèles est une opération qui consiste à générer unou plusieurs modèles cibles conformément à leur méta-modèle à partir d'unou de plusieurs modèles sources conformément à leur méta-modèle(gure 5.3[Czarnecki et Helsen, 2006]).Il existe dans la littérature trois types de transformations [Kerkouche, 2011] :

Les transformations verticales : la source et la cible d'une transforma-tion verticale sont dénies à diérents niveaux d'abstraction. Une trans-formation qui baisse le niveau d'abstraction est appelée un ranement.

27

Figure 5.3 Concepts de base de la transformation de modèles

Une transformation qui élève le niveau d'abstraction est appelée uneabstraction.

Les transformations horizontales : Une transformation horizontale mo-die la représentation source tout en conservant le même niveau d'abs-traction. La modication peut être l'ajout, la modication, la suppres-sion ou la restructuration d'informations.

Les transformations obliques : Une transformation oblique combine unetransformation horizontale et une verticale. Ce type de transformationest notamment utilisé par les compilateurs, qui eectuent des optimi-sations du code source avant de générer le code exécutable.

Classication des approches de transformation de modèles

Les approches de transformation de modèle ont été classées selon plusieursaxes. Chaque axe mène à une classication particulière. La classication desapproches de transformation proposée par Czarnecki et Helsen [Czarnecki et Helsen, 2003]se base sur les techniques de transformation utilisées dans les approches etles facettes qui les caractérisent. Selon cette classication on peut distinguerdeux types de transformation de modèles : les transformations de type modèlevers code et les transformations de type modèle vers modèles. Généralement,le premier type de transformation peut être vu comme un cas particulierdu deuxième type, nous avons seulement besoin de fournir un méta-modèlepour le langage de programmation cible. Cependant, pour des raisons pra-tiques de réutilisation de la technologie des compilateurs existants, souvent,le code est simplement généré en tant que texte, qui est ensuite introduitdans un compilateur. Pour cette raison, nous distinguons entre la transfor-mation de type modèle vers code et la transformation de type modèle versmodèle [Hamrouche, 2010].

Transformations de type Modèle vers code : Dans cette catégorie, on

28

distingue entre les approches basées sur le principe du visiteur (Visitor-based approach) et celles basées sur le principe des patrons (Template-based approach) [Hamrouche, 2010].

1. Approche basée sur le visiteur (Visitor-based) : approche de basepour la génération de code, elle consiste à fournir un mécanismede visiteur pour traverser la représentation interne d'un modèle etcréer le code. On peut citer comme exemple le framework Jamdaqui fournit un ensemble de classes pour représenter les modèlesUML, une API pour manipuler les modèles, et un mécanisme devisiteur pour générer le code.

2. Approche basée sur les templates (Template-based) : Actuelle-ment, la majorité des outils MDA disponibles supportent cetteapproche. La structure d'un template ressemble au code à géné-rer, dans un template il n'y a pas de séparation syntaxique entrele LHS et le RHS. le LHS utilise une logique exécutable pour ac-céder au modèle source, le RHS combine des patrons non typéset une logique exécutable (la logique : code ou requêtes déclara-tives). Parmi les outils basés sur ce principe, on peut citer : JET,Codagen Architect , ArcStyler, AndroMDA, OptimalJ et XDE(les deux derniers outils fournissent aussi la transformation mo-dèle vers modèle).

Transformations de type modèle vers modèle : Les transformations detype modèle vers modèle consistent à transformer un modèle source enun modèle cible, ces modèles peuvent être des instances de diérentsméta-modèles. Elles orent des transformations plus modulaires et fa-ciles à maintenir. Dans les cas où on trouve un grand espace d'abs-traction entre PIMs et PSMs, il est plus facile de générer des modèlesintermédiaires qu'aller directement vers le PSM cible. Les modèles in-termédiaires peuvent être utiles pour l'optimisation ou bien pour desns de déboguage. De plus, les transformations de type modèle versmodèle sont utiles pour le calcul des diérentes vues du système etleurs synchronisation.

1. Structure d'une transformation [Bahri, 2011] : Une transformationde modèle est un modèle en soit même. Elle se dénit par unensemble d'éléments à savoir : des règles de transformation ainsique leurs organisation et ordonnancement, une traçabilité et uneorientation. La combinaison de ses éléments permet de décrirela transformation. Toutefois, ces règles de transformation doiventêtre d'abord spécier an de pouvoir exprimer les correspondancesentres les concepts des Méta-modèles source et cible.

29

Règles de transformation : une règle de transformation est unedescription de la manière dont une ou plusieurs constructionsdans le langage du modèle source peuvent être transforméesen une ou plusieurs constructions dans le langage du mo-dèle cible [Kadima, 2005]. En plus, toute règle de transfor-mation possède une logique de forme déclarative ou impéra-tive pour exprimer des contraintes ou des calculs sur les mo-dèles sources et cibles de la transformation. Techniquement,une règle de transformation se compose de deux parties : unepartie gauche appelée LHS (Left Hand Side) qui accède aumodèle source, et une partie droite appelée RHS (Right HandSide) qui accède au modèle cible. l'exécution d'une règle detransformation orientée de gauche à droite, permet de rem-placer les constructions du modèle source conformes au LHSde la règle avec les RHS de la même règle pour la constructiondu modèle cible. Cette technique nécessite une organisationet un ordonnancement des règles ainsi que leurs orientation.Le mécanisme de traçabilité permet en plus de renforcer latechnique par archivage des corrélations qui existent entre leséléments des modèles de la transformation.

Spécication des règles de transformation : les règles de trans-formation expriment la correspondance entre les concepts duméta-modèle source et les concepts du méta-modèle cible. Lerôle de la spécication est la description de telles relationsindépendamment de toute exécution. MDA prévoit l'automa-tisation complète de cette phase. Actuellement, il n'existe pasde standard permettant d'exprimer les règles de transforma-tion. Les travaux actuels de l'OMG sur le standard MOF/-QVT (Query Views Transformation) semble être prometteurs.Dans notre travail, nous avons opté pour l'outilAToM3 [atom3, 2010].

Approches pour la dénition de la transformation : la trans-formation Modèle à Modèle se base sur une structure variée.Par conséquent, plusieurs approches tentent de dénir ce typede transformation. Dans la littérature, on distingue générale-ment cinq approches : les approches par manipulation directe ; les approches relationnelles ; les approches basées sur la transformation de graphes ; les approches basées sur la structure ; les approches hybrides.

30

5.2 Transformation de graphes

Les graphes et les diagrammes sont un moyen pratique, intuitif et directpour la modélisation des systèmes complexes. Citons comme exemples, lesdiagrammes UML, les réseaux de Petri ou encore les automates. Si les graphesservent à visualiser les structures complexes des modèles d'une manière simpleet intuitive, les transformations de graphes peuvent être exploitées pour spé-cier comment ces modèles peuvent évoluer. Les transformations de graphes[Rozenberg, 1999] ont évolué dans la répercussion à l'imperfection dans l'ex-pressivité des approches de réécriture classique comme les grammaires deChomsky et la réécriture de termes pour s'y prendre avec les structures non li-néaires. Une transformation de graphe [Karsai et Agrawal, 2004] [Andries et al., 1999][Rozenberg, 1999] consiste en l'application d'une règle à un graphe et ité-rer ce processus. Chaque application de règle transforme un graphe par leremplacement d'une de ses parties par un autre graphe. Autrement dit, latransformation de graphe est le processus de choisir une règle d'un ensembleindiqué, appliquer cette règle à un graphe et réitérer le processus jusqu'à cequ'aucune règle ne puisse être appliquée. La transformation de graphe estspéciée sous forme d'un modèle de grammaires de graphes. Ces dernièressont une généralisation des grammaires de Chomsky pour les graphes. Ellessont composées de règles. Une règle est constituée de deux parties, le LeftHand Side (LHS) et le Right Hand Side (RHS). Le LHS est la partie gauchede la règle, destinée à être mise en concordance avec les parties du graphe(appelé host graph) où on veut appliquer la règle. La partie droite de larègle, Le RHS, décrit la modication qui sera eectuée sur le host graph,elle substitue dans le host graph la partie identiée par la partie gauche dela règle [Rozenberg, 1999]. Il existe plusieurs formalismes pour représenterles règles de transformations. Dans ce manuscrit, nous utilisons des règlesqui sont exprimées visuellement. Avant d'aborder les grammaires de graphes,nous allons rappeler quelques concepts de base relatifs aux graphes.

5.2.1 Notion de graphe

On appelle graphe G = 〈V,E〉 la donnée d'un ensemble V dont les élémentssont appelés sommets et d'une partie E dont les éléments sont appelés arêtes :(v, v

′) ∈ E avec v, v

′ ∈ V [Chartrand et Zhang, 2009].La gure (5.4) montre l'exemple d'un graphe G avec un ensemble de sommetsV = a, b, c, d, e, f, g et un ensemble d'arêtes E = ab, ad, ae, bc, cc, df, ef,cf, fg. Dans cet exemple, on a |V | = 7 et |E| = 9, où |V | et |E| désignentrespectivement le cardinal de V et le cardinal de E.Il existe deux types de graphes : les graphes non orientés et les graphes

31

Figure 5.4 Exemple d'un graphe G

orientés.

Graphe orienté

Un graphe orienté est un graphe G = 〈V,E〉 où : V : ensemble ni d'éléments appelés sommets ou n÷uds. E : ensemble ni de paires ordonnées de sommets appelés arcs. A ⊆ X ×X = (s, t)|s, t ∈ V

Figure 5.5 Graphe orienté étiqueté avec des entiers

Graphe non orienté

Un graphe non orienté G = 〈V,E〉 où : V : ensemble ni d'éléments appelés sommets ou n÷uds. E : ensemble ni de paires de sommets appelés arêtes. A ⊆ X ×X = (s, t)|s, t ∈ V

5.2.2 Grammaire de graphe

Une grammaire de Graphe [Andries et al., 1999] est généralement dénie parun triplet : GG = (P, S, T ) où : P : ensemble de règles. S : un graphe initial. T : ensemble de symboles

32

Figure 5.6 Graphe non orienté étiqueté avec des lettres

Une grammaire de graphes distingue les graphes non terminaux, qui sont lesrésultats intermédiaires sur lesquels les règles sont appliquées et les graphesterminaux dont on ne peut plus appliquer de règles. Ces derniers sont dansle langage engendré par la grammaire de graphe. Pour vérier si un grapheG est dans les langages engendrés par une grammaire de graphe, il doit êtreanalysé. Le processus d'analyse va déterminer une séquence de règles dérivantG [Kerkouche, 2011].

Le principe de règles

Une règle de transformation de graphe est dénie par :r = (L,R,K, glue, emb, cond), elle consiste en : Deux graphes, L graphe de coté gauche et R graphe de coté droit. Un sous graphe K de L. Une occurrence glue de K dans R qui relie le sous graphe avec le graphede coté droit.

Une relation d'enfoncement emb qui relie les sommets du graphe de cotégauche et ceux du graphe du coté droit.

Un ensemble cond qui spécie les conditions d'application de la règle.

Application des règles

L'application d'une règle r = (L,R,K, glue, emb, cond) à un graphe G pro-duit un graphe résultant H. Le graphe H peut être obtenu depuis le graphed'origine G en passant par les cinq étapes suivantes :

1. Choisir une occurrence du graphe de coté gauche L dans G.

2. Vérier les conditions d'application d'après cond.

3. Retirer l'occurrence de L(jusqu'à K) de G ainsi que les arcs pendillé,c'est-à-dire tout les arcs qui ont perdu leurs sources et/ou leurs desti-nations. Ce qui fourni le graphe de contexte D de L qui a laissé uneoccurrence de K.

33

4. Coller le graphe de contexte D et le graphe de coté droit R suivantl'occurrence de K dans D et dans R. C'est la construction de l'unionde disjonction de D et R et, pour chaque point dans K,identier lepoint correspondant dans D avec le point correspondant dans R.

5. Enfoncer le graphe de coté droit dans le graphe de contexte de L suivantla relation d'enfoncement emb. Pour chaque arcs retiré incident avec unsommet v dans D et avec un sommet v′ dans l'occurrence de L dansG et pour chaque sommet v” dans R, un nouvel arc est établi (avec lamême étiquette) incident avec l'image de v et le sommet v” à conditionque (v′, v”) appartient à emb.

L'application de r à un graphe G pour produire un graphe H est appelée unedérivation directe depuis G vers H à travers r, elle est dénotée par G→ H.En donnant les notions de règle et de dérivation directe comme étant lesconcepts élémentaires de la transformation de graphe, ont peut dénir lessystèmes de transformation de graphe et la notion de langages engendrés.

Système de transformation de graphe

Un système de transformation de graphe est déni comme un système de ré-écriture de graphes qui applique les règles de la grammaire de graphes sur songraphe initial jusqu'à ce que aucune règle ne soit applicable [Rozenberg, 1999].

Langage engendré

Supposons que nous avons un ensemble donné P de règles et un graphe G0 ,une séquence de transformations de graphe successive :G0 → G1 → ...→ Gn

est une dérivation à partir de G0 vers Gn par les règles de P (à conditionque toutes les règles utilisées appartiennent à P ). G0 est le graphe initialet Gn est le graphe dérivé de la séquence de transformation. L'ensemble desgraphes dérivés à partir d'un graphe initial S en appliquant les règles de Pqui sont étiquetées par les symboles de T , est dit langage engendré par P , Set T et on écrit L(P, S, T ) [ElMansouri, 2009].

5.2.3 Outils de transformation de graphes

Plusieurs outils de transformation de graphes existent actuellement, parmilesquels : AGG [AGG, 2010],AToM3 [atom3, 2010], VIATRA [VIATRA, 2010],etc. Dans le cadre de cette thèse, nous avons opté pour AToM3 à cause desa simplicité et sa disponibilité.

34

Présentation de l'outil AToM3

AToM3 [atom3, 2010] A Tool for Multi-formalism and Meta-Modeling est un outil visuel pour la modélisation et la méta-modelisation multi-formalismes. Comme il a été implémenté en Python [Python, 2010], il peutêtre exécuté, sans aucun changement, sur toutes les plateformes où un in-terpréteur de Python est disponible (Linux, Windows et MacOS). Les deuxtâches principales d' AToM3 sont la méta-modelisation et la transformationde modèles. Pour la méta-modélisation, AToM3 supporte la modélisationvisuelle en utilisant le formalisme Entité-Relation (ER) ou le formalisme dediagrammes de classes d'UML. Ceci signie que pour méta-modéliser de nou-veaux formalismes on peut utiliser le modèle ER ou le modèle des diagrammesde classes. Dans le cadre de cette thèse nous avons choisi d'utiliser le modèledes diagrammes de classes. Les modèles dans AToM3 ont une représentationgraphique et une construction basée sur des règles issues d'une spécicationd'un formalisme déterminé. Dans AToM3 , la description graphique est at-tribuée aux modèles ainsi qu'au formalismes. AToM3 permet de générer desoutils de manipulation graphique des modèles décrits selon des formalismespéciés dans des méta-spécication. Par la suite, la transformation de mo-dèles s'eectue en utilisant des grammaires de graphes (gure 5.7).

Figure 5.7 Présentation de l'outil AToM3

35

Conclusion

Dans ce chapitre, nous avons présenté le concept de transformation de mo-dèles et plus précisément la transformation de graphes, une discipline im-portante dans la démarche MDA. Dans ce contexte, nous avons présenté lesdiérentes approches, méthodes et outils existants dans la littérature. Lesconcepts présentés dans ce chapitre constituent un background nécessairepour la compréhension de nos contributions dans le cadre de cette thèse.

36

Quatrième partie

Modélisations des systèmes

37

Chapitre

6

Modèles formels

Sommaire6.1 Système de transitions étiquetées (LTS) . . . . . 38

6.2 Systèmes de transitions étiquetées maximales (MLTS) 40

6.3 Le modéle des DATA "Durational Action TimedAutomata" . . . . . . . . . . . . . . . . . . . . . . . 42

6.4 Modèle des DATA* . . . . . . . . . . . . . . . . . . 44

La modélisation mathématique des systèmes informatiques est devenue deplus en plus une nécessité méthodologique, notamment pour le développe-ment et la validation des systèmes complexes. Au l des années, un bonnombre de modèles ont été introduits pour décrire les composants électro-niques ou les systèmes informatiques. Rappelons que pour qu'un système soitparfaitement utilisable, il doit être validé sur la base de fondements mathé-matiques, et par conséquent sur une sémantique correcte. Le choix du modèledépend du type du système à modéliser et des conditions de son évolution,ainsi il doit être ouvert pour accepter de nouvelles contraintes de modélisa-tion. C'est ce modèle qui servira à écrire la spécication du système. Pourplus de clarté, nous avons divisé ces modèles selon des grandes catégories.Une diérence cruciale entre diérents modèles, c'est la prise en compte desaspects temporels. Cette notion est arrivée bien plus tard, mais a toute sonimportance dans les systèmes soumis à des contraints de temps. Dans cechapitre, nous rappelons les concepts de base relatifs aux quelques modèlesutilisés dans le cadre de la modélisation des systèmes non-temporisés et ceuxtemporisés.

6.1 Système de transitions étiquetées (LTS)

LTS :Labelled Transition System [Arnold, 1992][Arnold, 1994] [Brinksma et Tretmans, 2000]est un quadruplet (Q, q0,Σ,→) tel que :• Q est un ensemble dénombrable d'états,

38

• q0 ∈ Q est l'état initial,• Σ est un alphabet dénombrable d'actions,• →⊆ Q×Σ∪τ×Q est un ensemble de transitions. Un élément (s, a, s′)de→ sera simplement noté s

a→ s′ .Un alphabet Σ est un ensemble ni d'actions. Une action d'un LTS peutprendre plusieurs formes : une entrée, une sortie, un appel de méthode, etc.Les états sont souvent une abstraction d'états du système (habituellement,il est impossible de représenter tous les états du système). Les actions deΣ sont dites actions observables .Une transition peut être étiquetée soit parune action observable, ou par une action interne τ (inobservable, ou encoresilencieuse).Une séquence ou un chemin est une suite nie d'actions que l'on notesimplement par juxtaposition :σ = a1a2....an , ai ∈ Σ . L 'ensemble desséquences nies et non vides de Σ est noté Σ+. La séquence vide est noté ε .Σ∗ dénote l'ensemble des séquences de Σ , c'est à dire l'ensemble Σ+ ∪ ε.De plus τ désigne une action qui n'appartient pas à Σ, l'ensemble Σ ∪ τest noté Στ .La longueur d'une séquence σ , notée |σ|, est le nombre d'actions qui lacomposent. σi dénote la ième action de σ (l'indice i est compris entre 1 et|σ|).Le produit de concaténation de deux séquences σ1 = a1a2....an et σ2 =b1b2....bm est la séquence σ = a1a2............anb1b2.......bm.Bien entendu, ε.σ = σ.ε = σ et |σ1, σ2| = |σ1|+ |σ2|.Une exécution sur un système de transitions est alors une séquence d'ac-tions (ai)i∈[1,n] .

6.1.1 Notations standards des LTS

Soient S = (Q, q0,Σ,→) un LTS, a,µ(i) ∈ Σ ∪ τ , α(i) ∈ Σ une actionobservable, σ ∈ Σ∗ une séquence d'actions observables et q, q′ ∈ Q deuxétats. Les notations standards des LTS sont rappelées ci-dessous :

- qa→ ∆

= ∃q′ |q a→ q′.- q

µ1...µn→ q′ ∆= ∃q0....qn|q = q0

µ1→ q1µ2→ ...

µn→ qn = q′.Le comportement observable de S est décrit par la relation ⇒:

- qε⇒ q′ ∆

= q = q′ ou q τ...τ→ q′.- q

α⇒ q′ ∆= ∃q1, q2|q

ε⇒ q1α→ q2

ε⇒ q′

- qα1...αn⇒ q′ ∆

= ∃q0...qn|q = q0α1⇒ q1

α2⇒ ...αn⇒ qn = q′.

- qσ⇒ ∆

= ∃q′|q σ⇒ q′.

39

- q after σ∆=q′ ∈ Q|q σ⇒ q′

, l'ensemble des états atteignables à

partir de q par σ. Par extension, Q after σ∆= q0 after σ.

- Traces (q)∆=

σ ∈ Σ∗|q σ⇒

, l'ensemble des séquences observables

tirables à partir de q. Par convention les traces d'un LTS sont ceux de son

état initial : Traces(Q)∆= Traces(q0) .

6.2 Systèmes de transitions étiquetées maximales

(MLTS)

Les modèles de spécications existant reposent sur une hypothèse primor-diale qui suppose l'atomicité structurelle et temporelle des actions. Un desmodèles pionnier dans la levée de cette hypothèse est celui introduit dans[Saidouni, 1996] Ce modèle considère que toute action dure dans le temps.Dans la pratique de la modélisation et du test il est non réaliste de maintenirl'hypothèse de l'atomicité des actions.Nous allons présenté le modèle qui n'est qu'une variante des systèmes detransitions étiquetées, déni sur un ensemble d'événement qui concrétise ledébut de l'exécution des actions avec les deux fonctions sur les congurationsainsi obtenues, permettant de suivre l'évolution des actions en cours d'exé-cution. Cette nouvelle approche permet de modéliser le vrai parallélismeainsi que l'autoconcurrence. Un système de transitions étiquetées maximales[Saidouni, 1996] n'est autre qu'un graphe d'état bi-étiqueté, tel qu' une tran-sition est étiquetée par un nom d'action. Un état est étiqueté par l'ensembledes noms d'événements identiant les actions qui sont potentiellement encours d'exécution au niveau de cet état là. Ces actions sont dites maximales.Les noms des événements sont choisis à partir d'un ensemble dénombrablenotéM.

Dénition 6.1 : L'ensemble des atomes de support Act est Atm = 2Mfn ×Act×M. 2Mfn étant l'ensemble des parties nies de l'ensemble dénom-brable des noms des événements M. Cet ensemble est parcouru par...x, y, z.M,N , ... dénotent des sous ensembles nis de M. Un atome(M,a, x) sera noté Max .

Dénition 6.2 : SoitM un ensemble dénombrable de noms d'événements,un système de transitions étiquetées maximales de support M est unquintuplés (Ω, λ, µ, ξ, ψ) avec :Ω = 〈S, T, α, β, s0〉 un système de transitions tel que :• S est un ensemble non vide d'états du système, cet ensemble peutêtre ni.

40

• T est un ensemble de transitions indiquant le changement d'état quepeut réaliser le système, cet ensemble peut être ni ou inni.• α et β sont deux applications de T dans S tel que pour toute transitiont on a : α(t) est l'origine de la transition et β(t) sa déstination.• s0 est l'état initial du système de transitions Ω.• (Ω, λ) est un système de transitions étiquetées par la fonction λ surun alphabet A appelé support de (Ω, λ). (λ : T → A).• ψ : S → 2Mfn est une fonction qui associe à chaque état l'ensemble nides noms des événements maximaux présents à son niveau.• µ : T → 2Mfn est une fonction qui associe à chaque transition l'en-semble ni des noms des événements correspondant aux actions quiont commencé leur exécution et dont la terminaison sensibilise cettetransition.• ξ : T → M est une fonction qui associe à chaque transition le nomde l'événement qui identie son occurrence.tel que ψ(s0) = ∅ et pour toute transition t, µ(t) ⊆ ψ(α(t)), ξ(t) /∈ψ(α(t))− µ(t) et ψ(β(t)) = (ψ(α(t))− µ(t)) ∪ ξ(t).

Notation Soit Stem = (Ω, λ, µ, ξ, ψ) un système de transitions étiquetéesmaximales tel que Ω = 〈S, T, α, β, s0〉, t ∈ T étant une transition telleque α(t) = s, β(t) = s′, λ(t) = a, µ(t) = E et ξ(t) = x. La transitiont sera notée aussi s Eax−→ s′.

Soit l'expression de comportement Basic LOTOS E ≡ a; stop|||a; stop. La -gure (6.1).(a) donne le système de transitions étiquetées obtenu par la séman-tique d'entrelacement. Ce système de transition est exactement le même quecelui de l'expression de comportement F ≡ a; a; stop représentant l'exécutionséquentielle de deux actions a. L'application de la sémantique de maximalitégénère le système de transitions de la gure (6.1).(b) dans le quel l'ensemblex, y exprime le fait que deux exécutions de l'action a peuvent avoir lieuen parallèle dans l'état nal.

Figure 6.1 Système de transitions étiquetées maximales

41

6.3 Le modéle des DATA "Durational Action

Timed Automata"

Les modèles non temporisé supposent la non-atomicité des actions (tempo-relle et structurelle) que se soit ceux basés sur l'algèbre de processus ou issuedes systèmes de transitions étiquetées, la sémantique sous jacente est celle del'entrelacement. Intuitivement elle suppose l'atomicité des actions et réduitl'exécution des actions parallèles à leur exécution entrelacer dans le temps.Cette hypothèse peut rendre invalides certaines spécications et même letest exécuter sur la base de cette modélisation, de même les modèles tem-porisés qui formellement traitent trois types d'actions (i) les actions obser-vables, (ii) les actions internes, (iii) et le passage de temps matérialisé par unedurée[Belmokadem, 2006][Brinksma et Briones, 2005][Bérard et al., 1998], ilsse résignent à exécuter des actions instantanées. La durée des actions n'a ja-mais été prise en compte explicitement.Dans ce contexte le modèle des DATA pour (Durational Action Timed Auto-mata model) [Belala et Saidouni, 2005] résulte de la combinaison des modèlesde transition temporisés et de la sémantique de maximalité[Courtiat et Saïdouni, 1995][Saidouni, 1996].Le modèle des DATA considère que chaque action dure dans le temps, cettequantité est capturée par la condition de durée sur un état destination, d'unetransition étiquetée par cette action, toutes les transitions oertes sont pos-sibles alors que toutes celles qui dépendent de la terminaison de l'action encours sont inhibées jusqu'à ce que la condition d'exécution attribuée à cestransitions soit vériée.Les actions qui doivent s'exécuter en parallèle sont au contraire lancer sansêtre concernée par les conditions de durées. Dans ce cas la condition de duréeore explicitement l'information sur l'évolution du système. La condition dedurée d'une action a décore chaque état atteint par l'exécution de l'actiona. Alors que toute transition est gardée par une condition d'exécution, c'estune conjonction sur des conditions de durée, elles concernent une transitiondont le passage est conditionné par la terminaison d'un ensemble d'actions(dépendance causale dans le sens d'événements maximaux).Ce modèle est aux frontières des modèles temporisés est ceux non temporiséscar les contraintes temporelles qu'il manipule expriment la réalité physiquede tout système sans pour autant traiter les contraintes temps réel de celuici.Pour illustrer le modèle des DATA, nous considérons l'exemple suivant (gure6.2) :Ce DATA est composé de trois états et deux actions a de durée 2 unités de

42

Figure 6.2 Exemple d'un DATA

temps et b de 10 unités de temps. A partir de l'état initial S0, l'exécution del'action a entraîne une initialisation de l'horloge x qui lui est associée. x >= 2est une condition de durée concernant a, elle est enregistrée dans l'état S1 etqui signie que a est en cours d'exécution, de même pour la condition y >= 10relative à l'action b. La transition S1 S2 est franchissable ssi la condition surla transition est vériée, celle-ci est dite condition d'exécution et elle signieque b ne peut être exécuter que si l'action a est achevée.

6.3.1 Formalisation du modèle des DATA

Dénition 6.3 : Soit H, parcouru par x, y... un ensemble d'horloges devaleurs non negatives dans (un domaine temporel T, tel que Q+ ou R+).l'ensemble Φt (H) de contraintes temporelles γ sur H est déni par lasyntaxe γ ::= x ∼ t, où x est une horloge dans H, ∼∈ =, <,>,≤,≥et t ∈ T. Fx est utilisé pour représenter une contrainte de la formex ∼ t. soit l'ensemble Fx1 , Fx2 , . . . , Fxn de contraintes temporelles ,∧Fx1 , Fx2 , . . . , Fxn évoque une contrainte de la forme

∧i=1,n Fxi .

Une valuation ou interprétation v sur H est une fonction qui associe àtoute horloge x ∈ H une valeur dans T. Une valuation v sur H satisfaitune contrainte temporelle γ sur H ssi γ est vériée lors de la valuation deshorloges par v. pour I ⊆ H, [I 7→ 0] v désigne la valuation sur H qui aectela valeur 0 à toute horloge x ∈ I, est vérie toutes les contraintes sur lesautres horloges de H. l'ensemble de toutes le valuations de H est noté Ξ (H).la relation de satisfaction |= sur les contraintes temporelles est dénie surl'ensemble des valuations sur H par : v |= x ∼ t ⇐⇒ v(x) ∼ t tel quev ∈ Ξ (H).On note 2Tfn l'ensemble ni des sous ensembles de T .

Dénition 6.4 : Un DATA -Durational Action Timed Automaton- A estun tuple (S, LS, s0,H, T ) tel que :• S est un ensemble ni d'états,• LS : S → 2

Φt(H)fn est une fonction qui correspond à chaque état s

l'ensemble F des conditions de durées des actions potentiellement enexécution dans l'état s .

43

• s0 ∈ S est l'état initial,• H est un ensemble ni d'horloges.• T ⊆ S × ∧2

Φt(H)fn × Act×H× S est l'ensemble des transitions. Une

transition (s, γ, a, x, s′) représente le passage de l'état s à l'état s′, enlançant l'exécution d'une action a et en initialisant x à zero. γ estla contrainte temporelle qui conditionne le passage de la transition.(s, γ, a, x, s′) est aussi notée s

γ,a,x−→ s′. L'ensemble de transition T par-couru par τ0, τ1, ...étant donnée une transition τi = (s, γ, a, x, s′), α(τi)(resp. β(τi)) représente l'état initial de τi (resp. l'état nal de τi). (i.e.α(τi) = s et β(τi) = s′). L'étiquette de la transition τi est λ(τi) = a.L'horloge associée à la transition τi est donnée par la fonction ξ(τi) = x

Dénition 6.5 : La sémantique d'un DATA A = (S, LS, s0,H, T ) est dé-nie par un système de transition inni SA sur Act ∪ T, Un état de SA( ou conguration) est un couple 〈s, v〉 tel que s est un état de A etv une valuation sur H. une conguration 〈s0, v0〉 est dite initiale ssi s0

est l'état initial de A et ∀x ∈ H, v0 (x) = 0. Deux types de transitionsentre deux congurations de SA sont possibles, est qui correspondentrespectivement au passage du temps ; la règle (RA rule) , une transitionde A ; la régle (RD rule).

(RA) d∈R+

〈s,v〉 d−→〈s,v+d〉(RD) (s,γ,a,x,s′)∈T v|=γ

〈s,v〉 a−→〈s′,[x7→0]v〉

6.4 Modèle des DATA*

Le modèle des DATA a été introduit dans le but d'exprimer la non-atomicitétemporelle et structurelle des actions. En général, les systèmes à tempscontraint ne peuvent être complètement spéciés si l'on considère pas desnotions comme l'urgence, les délais, les contraintes, etc. Pour prendre encompte ces nouveaux concepts, nous avons besoin de passer vers les DATA*que nous introduisons dans cette section [Belala, 2010].

6.4.1 Intuition

Considérons le système S représenté par le DATA de la gure (6.3) :A partir de l'état s3 de la gure (6.3).(b), l'action d ne peut commencerson exécution que si a et b ont terminé leurs exécutions, d'où la contraintex ≥ 10 ∧ y ≥ 12 correspondante à la transition d. Cette contrainte estune contrainte sur les durées des actions a et b. Une fois la contrainte x ≥10 ∧ y ≥ 12 satisfaite, l'action d peut s'exécuter à n'importe quel moment

44

Figure 6.3 DATA du comportement de S

dans l'intervalle ouvert de sensibilisation x ∈ [10,+∞[ , y ∈ [12,+∞[ quenous appelons domaine de sensibilisation.Le type de contraintes que nous voulons exprimer est celui impliquant desrestrictions sur le domaine de sensibilisation. Dans un contexte de tempscontraint, ces restrictions peuvent ne pas être dues uniquement aux durées desactions antérieures, formant ainsi des domaines ouverts comme pour x ≥ 10∧y ≥ 12, mais peuvent borner le domaine de sensibilisation indépendammentdes durées des autres actions en retardant par exemple une action d'unecertaine quantité de temps ou en limitant le temps pendant lequel une actionest oerte à son environnement (restriction temporelle).Ainsi, supposons que l'action a ne peut commencer son exécution que dansles trois premières unités de temps, c'est-à-dire dans le domaine [0, 3]. Uneaction peut éventuellement commencer son exécution si la valeur d'une cer-taine horloge appartient à son domaine de sensibilisation. L'action a ne peutcommencer son exécution que si une horloge particulière n'a pas encore at-teint la valeur 3. Cette horloge est initialisé au moment de la sensibilisationdu système S (c'est-à-dire à l'instant 0). Etant donné que l'action a n'attendla n d'aucune autre action, cette horloge est désignée c∅. Conséquemment, latransition a dans le DATA* résultant sera étiquetée par la contrainte c∅ ≤ 3(c'est-à-dire c∅ ∈ [0, 3]). Cette contrainte, appelée garde, devra être satis-faite pour que l'action a puisse s'exécuter. Si en plus, l'action a est retardéed'un laps de temps égal à 1 , la garde sur la transition a sera 1 ≤ c∅ ≤ 4(c'est-à-dire c∅ ∈ [0 + 1, 3 + 1]).Le même raisonnement s'applique sur les autres actions. En admettant que les

45

actions a et b du système S sont oertes à l'environnement dans les quantitésde temps respectives 3 et 4 depuis leurs sensibilisation, et que l'action d estretardée dans le sous-système S1 de 5 et dans S2 de 4 unités de temps, lecomportement global de S est représenté par le DATA* de la gure(6.4) :

Figure 6.4 DATA* du comportement de S

A partir de l'état s3, les deux sous-systèmes S1 et S2 peuvent se synchronisersur l'action d à condition que les actions a et b ont terminé leurs exécutions.Le début de l'action d est conditionné d'une part par la contrainte sur lesdurées de a et b : x ≥ 10 ∧ y ≥ 12, et d'autre part par la restriction tem-porelle du domaine de sensibilisation de l'action d de 5 et 4 unités de tempsrespectivement suivant la provenance de d (de S1 ou S2). L'action d prove-nant de S1 attend la terminaison de a (qui a comme horloge x), c'est-à-dire,elle attend que x atteint la valeur 10. Une fois cette valeur atteinte, le délaid'expiration de l'ore de l'action d de S1 commence, et termine après 5 unitésde temps, c'est-à-dire après que x atteint la valeur 15. Donc, le domaine desensibilisation de cette action est x ∈ [10, 15]. La même chose pour l'autreaction d ayant comme domaine de sensibilisation y ∈ [12, 16]. 1

1. x ∈ [min,max], min ≤ x ≤ max, x ≥ min ∧ x ≤ max, ou encore x ≥ min, x ≤ maxsignient la même chose. Cette observation a pour but d'assurer que les fonctions sur les

domaines, qui seront dénies par la suite, peuvent être appliquées à toutes les formes

précédentes de domaines, même si elles seront explicitement dénies en utilisant une seule

forme.

46

6.4.2 Expression de l'urgence

Nous avons constaté que le nouveau modèle des DATA* est capable d'ex-primer les contraintes temporelles dues aux restrictions sur un domaine desensibilisation d'une action. Observons à présent l'expression d'actions ur-gentes dans le modèle des DATA*. Une action urgente doit s'exécuter dèsqu'elle est sensibilisée, tout en stoppant la progression du temps.Notons qu'il faut distinguer entre actions urgentes et actions dont le domainede sensibilisation est formé d'un seul instant dans le temps. Considéronsl'exemple d'une action a ayant une durée de 7 et ayant comme domaine desensibilisation x ∈ [3, 3]. Cette action ne peut s'exécuter que si l'horloge xatteint la valeur 3 ; au-delà de ce domaine (par exemple dans le cas d'unrefus de l'environnement), l'action a ne peut plus s'exécuter. Si par contrea est une action urgente ayant toujours comme domaine de sensibilisationx ∈ [3, 3], une fois x est égale à 3, le temps s'arrête de progresser jusqu'à ceque l'action a commence à s'exécuter. Donc, le domaine d'urgence de a estx ∈ [3, 3].En considérant l'hypothèse de la monotonie du temps, au moment de la sa-tisfaction de la condition correspondante au domaine d'urgence d'une action,cette dernière doit être tirée immédiatement.Dans cet exemple, le domaine x ∈ [3, 3] désigne à la fois le domaine desensibilisation et le domaine d'urgence sauf que sa sémantique dière dansles deux contextes. Cette observation nous ramène à introduire le domained'urgence au niveau des transitions des DATA*. Ainsi, toutes les transitionsseront étiquetées en plus de la contrainte de sensibilisation G (pour guard, ougarde) par la contrainte d'urgence D (pour deadline, ou échéance). Dans lecas du comportement du système S représenté par la gure (6.4), toutes lestransitions seront étiquetées par D = false, à cause de l'absence d'actionsurgentes. La contrainte d'urgenceD peut être occultée sans aucune ambiguïtédans le cas où D = false.

Figure 6.5 Expression de l'urgence par un DATA*

47

Le comportement de l'exemple précédent dans lequel l'action a est urgenteest illustré par la gure (6.5). L'horloge c∅ est utilisée à la place de x dansle cas où a est la première action que le système peut exécuter, ce qui esteectivement le cas dans notre exemple. En fait, l'horloge x sera associée àl'action a, la contrainte sur la durée de a placée sur l'état s1 est écrite ainsien fonction de x.

6.4.3 Formalisation

Dénition 6.6

Un DATA* A est un quintuplet (S, LS, s0,H, TD) tel que :• S est un ensemble ni d'états,• LS : S → 2

Φt(H)fn est une fonction qui fait correspondre à chaque état s

l'ensemble F des conditions de terminaison des actions potentiellement enexécution dans s.• s0 ∈ S est l'état initial,• H est un ensemble ni d'horloges.• TD ⊆ S × 2

Φt(H)fn × 2

Φt(H)fn × Act × H × S est l'ensemble des transitions.

Une transition (s,G,D, a, x, s′) représente le passage de l'état s à l'états′, en lançant l'exécution de l'action a et en réinitialisant l'horloge x. Gest la contrainte correspondante, qui doit être satisfaite pour tirer cettetransition. D est l'échéance correspondante qui exige, au moment de sasatisfaction, que l'action a doit être tirée. (s,G,D, a, x, s′) peut être écrit

sG,D,a,x−→ s′.

Dénition 6.7

La sémantique d'un DATA* A = (S, LS, s0,H, TD) est dénie en lui associantun système inni de transitions SA sur l'alphabet Act ∪ R+. Un état de SA(ou conguration) est un couple 〈s, v〉 tel que s est un état de A et v est unevaluation sur H. Une conguration 〈s0, v0〉 est initiale si s0 est l'état initial deA et ∀x ∈ H, v (x) = 0. Deux types de transitions entre les congurations deSA sont possibles, et qui correspondent respectivement au passage de temps(règles RA1* et RA2*) et au tirage d'une transition de A (règle RD*).

(RA1*)d ∈ R+ ∀d′ ≤ d, v + d′ 2 D

〈s, v〉 d−→ 〈s, v + d〉(RA2*)

ε ∈ R+ v + ε D et ε ≤ η

〈s, v〉 ε−→ 〈s, v + ε〉

(RD*)(s,G,D, a, x, s′) ∈ TD v |= G

〈s, v〉 a−→ 〈s′, [x 7→ 0] v〉

48

Où η est la plus petite quantité réelle de temps dans laquelle aucune actionne se produit.

Conclusion

Nous avons présenté dans ce chapitre un état de l'art concernant quelquesmodèles utilisés pour spécier les systèmes logiciels ou matériels. Dans lecadre de cette thèse,nous nous interessons aux deux modèles basés sur lamaximalité appelés respectivement DATA et DATA* (pour Durational Ac-tion Timed Automata(*)). Le premier modèle est destiné principalement à latache de spécication de systèmes, temps-réel ou non, où nous nous intéres-sons beaucoup plus aux durées d'actions. Le deuxième étant une extensiondes DATA mais cette fois-ci en donnant la possibilité à un concepteur depouvoir spécier aussi bien les durées explicites d'actions que les contraintestemporelles et les contraintes d'urgence agissant sur le comportement du sys-tème temps-réel à analyser. Ces deux modèles se présentent aussi comme unealternative intéressante aux modèles existants du point de vu implémentabi-lité et robustesse.

49

Cinquième partie

Contributions

50

Chapitre

7

Application de l'ap-

proche de transforma-

tion de graphes pour

la déterminisation des

DATA

Sommaire7.1 L'opération de déterminisation d'un DATA . . . 51

7.2 Génération d'un DATA respectant la syntaxe d'AToM3 53

7.3 Transformation d'un DATA à un DATA déter-ministe . . . . . . . . . . . . . . . . . . . . . . . . . . 53

7.4 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . 58

Dans ce chapitre, nous présentons notre première contribution qui consisteà transformer un DATA en un DATA déterministe [Saidouni et al., 2010a][Saidouni et al., 2010b] en se basant sur l'algorithme de détermisation pro-posé dans [Kitouni, 2008]. A cette n nous utilisons l'approche de transfor-mation de graphes. En premier lieu, nous proposons un programme pythonqui transforme un DATA écrit sous la forme d'un chier texte respectantune syntaxe bien dénie vers un DATA écrit sous la forme d'un chier py-thon respectant la syntaxe d'un chier AToM3,Le choix de la représentationtextuelle permet l'interfaçage de notre outil avec d'autres environnementsgénérant des DATA. Ce qui permet la considération de systèmes de grandestailles. la deuxième étape consiste à proposer un méta-modèle associé auxDATA et une grammaire de graphes pour l'exécution de la transformation àl'aide de l'outil de modélisation AToM3. Le DATA déterministe obtenu seraenregistré sous forme d'un chier texte.

7.1 L'opération de déterminisation d'un DATA

A cette section nous rappelons la méthode de déterminisation particuliè-rement l'élimination des actions internes, qui représente une étape consi-dérable dans le domaine de génération automatique du test de conformité

51

[Kitouni, 2008].L'opération de déterminisation d'un DATA A signie le calcul d'un DATAdéterministe ayant les mêmes traces temporisées que A en deux étapes :

1. L'élimination des actions internes (τ − actions) et2. L'élimination du non déterminisme causé par les actions observables.

Dans notre travail,nous nous intéressons au premier point.

7.1.1 Conditions générales sur la pratique du Modèle

1. Les actions internes sont urgentes.

2. Toute spécication de système doit être gardée : i.e. à partir de l'étatinitial du système les transitions possibles sont toutes observables. For-mellement :∀τi ∈ T tel que α (τi) = s0 alors λ (τi) 6= τ

7.1.2 Élimination des actions internes

L'idée principale pour l'élimination des actions internes, consiste en le calculde l'eet temporel de la séquence de transitions internes qui se termine parune action observable ensuite d'aecter cet eet à la condition d'exécutionde celle ci.

Fonction de translation en avant (Forward Translation)

Intuitivement la fonction de translation en avant traite toutes les paires detransitions contiguës tel que la première soit une τ − transition en troisétapes : (1) Le traitement de l'état de sortie de la τ − transition. (2) Letraitement de la condition d'exécution de la transition suivante si elle dépendde la terminaison de τ , et cela en translatant la durée de l'action interne, ainsique sa condition d'exécution. (3) L'élimination eective de la τ − transition.Ce schéma est détaillé comme suit :

1. Traitement de l'état de sortie de la τ − transition : cela est réalisé lorsde la substitution de la condition de durée de l'action τ dans l'état des-tination par la contrainte temporelle qui conditionne la τ − transitionaugmentée de la durée de τ .

2. Toutes les transitions qui suivent directement la τ−transition (formantavec elle une paire de transitions contiguës) : Le traitement consiste àremplacer la condition de durée de l'action τ dans la condition d'exécu-tion de la transition suivante, si elle existe, par la contrainte temporelle

52

qui conditionne la τ − transition augmentée de la durée de τ . Sinon letraitement s'eectue sur la branche débutant par la deuxième transitionde la paire avec tous ses successeurs en respectant le même scénario.Le processus s'arrête, soit par la détection d'une dépendance soit parla détection d'une transition sans successeur (atteignant un état nal).

3. Enn, élimination de la τ − transition.4. Refaire l'opération jusqu'à élimination de toutes les τ − transitions du

DATA.

7.2 Génération d'un DATA respectant la syn-

taxe d'AToM 3

Les gures (7.1) et (7.2) représentent un exemple de la représentation tex-tuelle et graphique d'un DATA. La gure (7.3) représente un chier pythond'un DATA. La transcription d'une représentation textuelle en une représen-tation graphique se fait à travers le programme python(PGM −DATAfichText−DATAfichAtom3.py)

Figure 7.1 Représentation textuelle d'un DATA

7.3 Transformation d'un DATA à un DATA dé-

terministe

Dans cette section, nous proposons une approche de transformation de DATAen DATA déterministe. Nous proposons un méta-modèle associé au DATA

53

Figure 7.2 Représentation d'un DATA sous l'environnement AToM3

Figure 7.3 Étape de génération d'un DATA

et une grammaire de graphes pour l'exécution de la transformation à l'aidede l'outil de modélisation AToM3.

7.3.1 Méta-modèle d'un DATA

Notre méta-modèle est un diagramme de classes composé des classes sui-vantes (gure 7.4) :

La classe DATAState : cette classe représente les états du DATA, chaqueétat possède deux attributs qui sont son nom (name), et les conditionsde durées (conDuree). Elle est reliée à la classe DATAInitState parun lien d'héritage et à DATATransition.

L'association DATATransition : Elle représente les transitions du DATA,chaque transition est identiée par une action, une horloge et une condi-tion d'exécution (condExecution).

La classe DATAInitState : Cette classe représente l'état initial du DATA.Elle hérite les attributs de la classe DATAState.

Chacune de ces classes a une apparence graphique distincte.

54

Figure 7.4 Méta-modèle du DATA

7.3.2 Outil de modélisation d'un DATA

Le méta-modèle ainsi déni est représenté dans AToM3 (gure 7.4), va nouspermettre la génération d'automates temporisés avec durées d'actions DATAen cliquant sur le bouton GEN. La gure(7.5) représente le graphe d'unautomate DATA modélisant un système.

7.3.3 Grammaire de graphe proposée

La grammaire proposée qui permet de générer des DATA déterministes estcomposée de dix règles reparties en quatre catégories.

Les règles 1 et 2 : [propriétés 1 et 2](Figure 7.6) assure que le système dé-bute son exécution par une action observable. Si la première action n'estpas observable (action interne τ), le système ache un message d'er-reur. (L'action interne est représentée dans l'environnement AToM3

par T ).

Les règles 3 et 4 : [propriétés 3 et 4] (Figure 7.7) permettent l'éliminationde τ − cycle (boucle de τ − transitions)Regle3 : calcule le cumul de la durée d'une séquence τ − transitionsc'est-à-dire génère une contrainte temporelle condition de durée quiest la somme de toutes les durées des τ − transitions.

55

Figure 7.5 Outil de modélisation des automates DATA

Figure 7.6 Achage d'un message d'erreur

Regle4 : génère une contrainte temporelle condition de durée quiest la somme de toutes les durées des τ − transitions (règle 3) muni dunombre d'itérations représenté par W ; et le remplacement de cettecontrainte temporelle dans la condition d'exécution de la transitionsuivante si elle est conditionnée par τ − cycle.

Les règles 5, 6 et 7 : [propriétés 5,6 et 7](Figure 7.8) permettent l'élimi-nation de τ − transitions(succession de τ − transitions)Regle5 : permet l'élimination de τ − transitions en cas d'une branche.

56

Figure 7.7 Elimination de τ − cycle

Regle6 : permet l'élimination deτ − transitions ayant un successeur.Regle7 : permet l'élimination de τ − transitions sans successeur.

Au niveau des règles 5, 6 et 7, il y aura l'élimination d'une τ−transition,le fusionnement de l'état qui précède la τ − transition et celui qui lasuccède dans un nouveau état et le remplacement de la condition dedurée de l'action τ au niveau de cet état par la contrainte temporellequi conditionne la τ − transition augmentée de la durée de τ .Les règles 5 et 6 eectuent le même processus au niveau de la condi-tion d'exécution des transitions successeurs (descendants) de la τ −transition si celles-ci dépendent de l'action τ , autrement dit : la condi-tion de durée de l'action τ fait partie de la condition d'exécution de cestransitions.

Figure 7.8 Élimination de τ − transition

57

La règle 8 : [propriété 8](Figure 7.9) permet l'élimination des états inac-cessibles.

Figure 7.9 Élimination des états inaccessibles

Les règles 9 et 10 : [propriété 9 et 10](Figure 7.10) ) permettent la récu-pération du DATA déterministe résultant.

Figure 7.10 Enregistrement du DATA déterministe

7.4 Exemple

Nous proposons cet exemple pour illustrer notre approche. Le mapping entrele chier DATA (gure7.11) et son modèle DATA correspondant (gure 7.12)est réalisé par un programme python. Après l'exécution de la grammaire, nousobtenons un DATA déterministe (gure 7.13). Le résultat sera enregistré dansun chier texte (gure 7.14).

Conclusion

Dans ce chapitre, nous avons présenté notre première approche : la détermi-nisation des automates temporisés avec durées d'actions DATA par la trans-formation de graphes et l'utilisation de l'environnement AToM3. Dans un

58

Figure 7.11 Le chier DATA

Figure 7.12 Le modèle DATA graphique

premier temps, nous avons élaboré un programme en langage python quitranscrit un automate DATA présenté sous format texte (un chier texte)en un automate DATA sous format python, dans un chier python respec-tant la syntaxe d'AToM3. Par la suite, nous avons proposé une démarche

59

Figure 7.13 Le modèle DATA déterministe

Figure 7.14 Le modèle DATA textuel déterministe

automatisée basée sur la technique de transformation de modèles, en uti-lisant la grammaire de graphes, pour transformer un DATA en un DATAdéterministe, en puisant du concept de la méta-modélisation et l'algorithmede déterminisation proposé dans [Kitouni, 2008]. Le principal objectif étaitd'élaborer un outil able et maniable sous l'environnement d'AToM3 pourgénérer des DATA déterministes à partir des DATA de grandes tailles et enconsidérant les spécicités de la majorité des systèmes.

60

Chapitre

8

Transformation des

DATA* sous format

dotty en des automates

de régions agrégés

Dans la pratique, les algorithmes de vérication et de validation en géné-ral sont plus durs à implémenter du fait de la considération des aspectsquantitatives du temps réel ; ils reposent sur l'utilisation des graphes des ré-gions pour résoudre un nombre considérable de problèmes. Rappelons quel'exécution d'un automate temporisé est innie, l'idée des graphes des ré-gions consiste en le partitionnement de cet espace d'états en régions nis.Ensuite,la construction eective du graphe qui imite le fonctionnement del'automate initial.Ce travail se base sur notre approche d'agrégation [Kitouni et al., 2012a][Kitouni et al., 2012d] qui consiste à agréger les localités d'un graphe desrégions en utilisant une Bi-relation de regroupement qui peut exister entreeux. Cette relation est une équivalence qui permet de regrouper les régionsd'une même classe ce qui permet de réduire le nombre de localités du grapheet de faciliter son implémentation .Dans un premier temps nous proposons un programme python qui trans-forme un DATA* présenté dans un chier dotty en un chier format py-thon accepté par l'outil AToM3, en suite, nous présentons notre outil, quitransforme le modèle des DATA* de grandes tailles en des automates desrégions agrégés par l'approche de transformation de graphes. Par ailleursnous proposons deux méta-modèles, le premier pour le modèle des DATA* etle deuxième pour les automates des régions agrégés ainsi qu'une grammairepour la génération d'un automate des régions agrégé à partir d'un DATA*. Leprogramme python proposé permet l'interfaçage de notre outil avec d'autresenvironnement générant des DATA* de grandes tailles [Hachichi et al., 2011][Hachichi et al., 2012c] [Hachichi et al., 2012d].

61

8.1 Automates des régions

Nous reprenons dans cette section la dénition classique ainsi que la forma-lisation des automates des régions [Alur et Dill, 1994] [Bouyer, 2002].

8.1.1 Régions d'horloges

Une région est un ensemble de valuations d'horloges, tel que à partir dedeux valuations d'une même région, les mêmes transitions d'un DATA* sonttirables.

8.1.2 Dénition 8.1

Soit A un DATA*, l'ensemble des régions standards de A est l'ensemble desclasses de la relation d'équivalence ≡ dénie sur les valuations d'horlogescomme suit : v ≡ v′ , si ∀(x, y) ∈ H

1. v(x) > Mx ⇔ v′(x) > Mx

2. v(x) 6 Mx ⇒ ((bv(x)c = bv′(x)c) et (frac(v(x)) = 0⇔ frac(v(x′)) =0))

3. (v(x) 6Mx et v(y) 6My ⇒ (frac(v(x)) 6 frac(v(y))⇔ frac(v′(x)) 6frac(v′(y)))

OùMx (respMy) est la constante maximale apparaissant dans les contraintestemporelles sur x (resp y) du modèle DATA* et pour tout réel d positif,bdc représente la partie entière de d, alors que frac(d) représente sa partiefractionnaire. On notera R l'ensemble de régions.La gure (8.1) montre les 38 régions dans le cas d'un ensemble H constituéde deux horloges x et y où Mx = 3 et My = 1. Les successeurs temporels d'une région d'horloge sont les régions que l'onpeut atteindre à partir de cette région lorsque le temps évolue (découperselon les diagonales gure (8.1)). Notons que succ(r) est l'ensemble dessuccesseurs d'une région r.

Deux valuations d'une même région doivent satisfaire les mêmes contraintes.

8.1.3 Automate des régions

L'automate des régions imite le fonctionnement atemporel de l'automate tem-porisé avec durées d'actions, il est déni comme suit :

62

Figure 8.1 Régions d'horloges

Dénition 8.2

Soit A :(ACT, S, s0,H, TD, LS) un DATA*, l'automate des régions R(A) cor-respondant à A est un automate ni déni comme suit : L'ensemble des localités de R(A) sont de la forme (s, r) où s ∈ S et r estune région d'horloge.

La localité initiale : (s0, s0). L'ensemble des transitions TR :

TR =

t′/t′ = (s, r) a−→ (s′, r′)

∃ s g,a,h−→ s′ ∈ TD et ∃r” ∈ succ(r)telque r v g et r = r” [h← 0]

Nous présentons un exemple de l'automate des régions associé à un DATA*A dans les gures (8.2) et (8.3).

Figure 8.2 DATA* A

63

Figure 8.3 Automate des régions associé à A

8.2 Automate des régions agrégé

Notre opération d'agrégation sur les localités d'un automate des régionsconsiste à substituer les localités regroupables par une localité ayant le mêmenom d'état et une région qui regroupe plusieurs régions successeurs. Les lo-calités sont dites regroupables si et seulement si elles possèdent les mêmestransitions images avant et images arrière. L'opération d'agrégation a permisde révéler des aspects de symétrie des régions d'horloges lors de la création dugraphe des régions associé au DATA*. En eet du fait de la dépendance cau-sale des actions suite à la considération des durées des actions, les gardes destransitions ont une forme particulière ainsi que la remise à zéro de l'horlogerelative à chaque début d'exécution d'une action ; de ces deux caractéristiqueson peut déduire la forme de toutes les régions et ses successeurs temporelsvériant la garde et la remise à zéro d'une transition donnée. Le regroupe-ment des localités (s, ri) réputées regroupables, consiste en la création d'unenouvelle localité (s, R) tel que R est la sommation sur les régions ri des lo-calités à regrouper. Cette nouvelle région n'est autre que la garde g avec laremise à zéro associée, de la transition initiale.

Remarque :

La sommation des régions d'horloges est une opération dénie sur l'ensembledes régions comme suit :

R = ⊕(r1, r2 . . . , rk) = ⊕k(rk)

⊕(r) = r si k = 1⊕k(rk) = r1 ∪ r2 ∪ ...... ∪ rk si k > 1

Dans le modèle des DATA*, on peut générer un automate des régions agrégé àpartir de la spécication par transformation. Les règles de la transformation

64

sont basées sur la translation des gardes et des remises à zéro vers l'étatcible de la transition, c.à.d. pour toute transition t = (s, g, a, x, s′) ∈ TDdu DATA* A, lui faire correspondre une transition tr = ((s, ri), a, (s

′, g ∧x = 0) ∈ TR à partir de l'état initial (s0, r0) tel que s0 l'état initial de Aet r0 = (∀x ∈ H, x = 0) par induction sur toutes les transitions de A.Plus de détails se trouvent dans nos articles suivants : [Kitouni et al., 2012a][Kitouni et al., 2012b] [Kitouni et al., 2012d].Exemple, la gure (8.4) présente l'automate des régions agrégé associé auDATA* A de la gure (8.2)

Figure 8.4 Automate des régions agrégé associé à A

8.3 Génération d'un DATA* respectant la syn-

taxe d'AToM3

La gure (8.5) présente un exemple d'un système en DATA* sous l'éditeurgraphique dotty [Dotty, 2011], le chier dotty correspondant est transforméen chier python (gure 8.6).b en utilisant l'application(applicationDATAetfichdottyf ichATOM3) (gure 8.6).a, elle-même implé-mentée dans le langage python. La représentation graphique sous AToM3 duchier python résultat est montrée dans la gure (8.7).

Figure 8.5 Représentation dotty d'un DATA* A

65

Figure 8.6 Étape de transformation (dotty-python) du DATA* A

Figure 8.7 Représentation du DATA* A sous l'environnement AToM3

8.4 Transformation d'un DATA* à un automate

des régions agrégé

Dans cette section nous proposons deux méta-modèles, le premier pour lemodèle des DATA* et le deuxième pour les automates des régions agrégésainsi qu'une grammaire pour la génération d'un automate des régions agrégéà partir d'un DATA*.

8.4.1 Méta-modèle d'un DATA*

Notre méta-modèle est un diagramme de classes composé des classes sui-vantes (gure 8.8) :

La classe DATAet : Cette classe représente les états du DATA*, chaqueétat possède deux attributs qui sont le nom (nom), et les conditionsde durées (CD). Elle est reliée à la classe DATAetInit par un liend'héritage et à TransitionD.

L'association TransitionD : Représente les transitions du DATA*, chaque

66

transition est identiée par une action, une horloge, une garde et uneéchéance.

La classe DATAetInit : Cette classe représente l'état initial du DATA*,elle hérite des attributs de la classe DATAet.

Figure 8.8 Méta-modèle du DATA*

8.4.2 Méta-modèle d'un automate des régions agrégé

Notre méta-modèle est un diagramme de classes composé des classes sui-vantes (gure 8.9) :

La classe ARstate : Cette classe représente les localités de l'automate desrégions agrégé (A.R. Agrégé), chaque localité possède deux attributsqui sont le nom (nom), et une région d'horloge (RegionHorloge), elle estreliée à la classe ARStateInit par un lien d'héritage et à ARtransition.

L'association ARtransition : Représente les transitions de l'automate desrégions agrégé, chaque transition est identiée par une action.

La classe ARStateInit : Cette classe représente la localité initiale de l'au-tomate des régions agrégé, elle hérite les attributs de la classe ARstate.

Lors de la modélisation dans AToM3, chacune de ces classes a une apparencegraphique distincte.

67

Figure 8.9 Méta-modèle d'A.R. Agrégé

8.4.3 Outil de modélisation du DATA* et de l'automatedes régions Agrégé

Les deux méta-modèles ainsi dénis sont représentés dans AToM3 ((gure8.8), (gure 8.9)) et vont nous permettre la génération d'un outil pour lamodélisation des exemples en DATA* ainsi que l'automate des régions Agrégé(gure 8.10).

Figure 8.10 Outil de modélisation des DATA* et A.R. Agrégé

68

8.4.4 La grammaire de graphe proposée

La grammaire proposée permet de générer des automates des régions agrégés,elle est composée de neuf règles.

La 1 ère règle : [propriété 1](Figure 8.11) permet de générer la 1ère régionassocié à l'état initial du DATA* où toutes les horloges sont remises àzéro.

Figure 8.11 Génération de l'état initial d'un A.R. Agrégé (règle 1)

Les règles 2 et 3 : [propriétés 2 et 3](Figure 8.12) génèrent le reste de l'au-tomate des régions agrégé ainsi que l'enregistrement de l' A.R.Agrégédans un chier texte.

Figure 8.12 Génération des états d'un A.R. Agrégé et son enregistrement(règles 2 et 3)

Les règles 4 et 5 : [propriétés 4 et 5](Figure 8.13) permettent l'éliminationdes liens génériques entre le graphe du modèle source et le graphe dumodèle cible.

Figure 8.13 Élimination des liens génériques (règles 4 et 5)

Les règles 6, 7,8 et 9 : [propriétés 6,7,8 et 9](Figure 8.14) permettent lasuppression de la représentation graphique du modèle DATA*.

69

Figure 8.14 Suppression du modèle DATA* (règles 6,7,8 et 9)

8.5 Cas d'étude

Pour illustrer l'approche proposée nous utilisons un système de réservationde billet SRB, le principe de ce système est comme suit : pour acheter unbillet, nous passons généralement par deux fenêtres. La première est de typeR (Réservation), elle permet la réservation d'une place dans un vol et l'éta-blissement du billet d'avion. La seconde fenêtre est de type C (Comptoird'argent) pour le règlement et le retrait du billet par le client. Cette agencea une salle d'attente, trois fenêtres de type R et deux de types C. A l'arrivée,le client passe à la salle d'attente, lorsque une fenêtre de type R est libre, ilpeut se présenter à la fenêtre et faire une réservation. Une fois l'opérationest terminée, il attend jusqu'à ce qu'une fenêtre C devient libre pour payeret prendre le billet. La gure (8.15) représente le DATA* associé au systèmede réservation de billets SRB en format dotty, pour deux clients. Le mappingentre ce chier dotty (gure 8.15) et son DATA* correspondant en AToM3

(gure 8.16) est réalisé par un programme python. Après l'exécution de lagrammaire, nous obtenons un automate des régions agrégé (gure 8.17). Lerésultat sera enregistré dans un chier texte (gure 8.18).

70

Figure 8.15 DATA* SRB présenté en dotty

Figure 8.16 DATA* SRB présenté sous AToM3

Conclusion

Dans ce chapitre, nous avons proposé une approche pour la génération d'unautomate des régions agrégé à partir d'un DATA* par la transformation degraphes et l'utilisation de l'environnement AToM3. Le but de cette transfor-

71

Figure 8.17 A.R.Agrégé

Figure 8.18 Fichier texte correspondant à l'A.R.Agrégé

mation est de fournir une abstraction nie d'un modèle DATA* de grandetaille ainsi que l'utilisation de ce résultat pour proposer un modèle de test.Dans un premier temps, nous avons élaboré un programme en langage py-thon qui transcrit un automate DATA* présenté sous format dotty en unautomate DATA* sous format python, respectant la syntaxe d' AToM3. Parla suite, nous avons proposé une démarche automatisée pour transformer unDATA* en un automate des régions agrégé.

72

Chapitre

9

Application de l'ap-

proche de transforma-

tion de graphes pour le

test des systèmes tem-

porisés

Dans ce chapitre, nous nous intéressons au test formel des systèmes tempsréel en utilisant la transformation de graphe.Dans le cadre de la génération de tests des systémes temporisés, la dicultémajeure est que le temps continu sur les transitions induit un espace d'étatsinni. Pour obtenir une suite nie de tests, nous proposons une approchebasée sur les graphes de régions agrégés (chapitre 8) an de discrétiser l'espaced'état.Dans un premier temps nous transformons un DATA* de grandes tailles enun Graphe de Refus Agrégé (GRA), ce dernier n'est qu'un automate desrégions agrégé (section 8.2) décoré par un ensemble d'actions refusées. leGRA est basé sur le principe de refus utilisé dans le modèle des Graphesde Refus Mixtes (GRM)[Saidouni, 1996] [Chaoui et al., 2010]. Ensuite, noustransformons ce GRA à un testeur canonique an de générer des cas de test.Par ailleurs nous proposons deux méta-modèles, le premier pour le modèle desDATA* (déjà présenté dans la section 8.4.1) et le deuxième pour GRA/testeurcanonique ainsi qu'une grammaire pour la génération d'un GRA, d'un testeurcanonique ainsi des cas de test à partir d'un DATA*. Pour générer des DATA*de grandes tailles, nous utilisons le même programme python présenté dansla section 8.3 [Hachichi et al., 2012b][Hachichi et al., 2012a].

9.1 Graphe de Refus Agrégé(GRA)

Le Graphe de Refus Agrégé(GRA) est généré à partir du DATA*. Il dé-core chaque localité de l'automate des régions agrégé par un ensemble derefus. Un GRA est doté de deux types de refus : les refus temporaires etceux permanents en associant à chaque action refusée des deux types, lescontraintes temporelles assurant leurs validités. Un GRA est doté aussi par

73

des actions interdites (forbidden actions). Elles représentent les actions inter-dites à partir d'un état. Cependant, les refus permanents sont induits par lenon-déterminisme inhérent dans le système après l'application de l'opérationde déterminisation. Les refus temporaires sont induits par le fait que les ac-tions peuvent durer dans le temps. Un refus temporaire sur une action dansun état donné signie que ce refus va disparaître après un laps de temps.

9.1.1 Formalisation

Dénition 9.1

Soit A :(S, s0,H, TD, LS) un DATA*, le Graphe de Refus Agrégé (GRA) de Aest une structure de graphe Bi-étiqueté déterministe : LR = (L, l0, TR, RefGRA)où :• L est un ensemble ni de localités, l0 = (s0, r0) ∈ L est appelé localitéinitiale.• l'ensemble des transitions TR :

TR =

t′/t′ = (s, r) a−→ (s′, r′)

∃ s g,a,h−→ s′ ∈ TD et ∃r” ∈ succ(r)telque r v g et r = r” [h← 0]

• RefGRA : L −→ P (P (V ∪≈V )) est une application qui dénit pour toute

localité l ∈ L, l'ensemble des parties d'actions pouvant être refusées telque :∼v =

∼a(g) : a ∈ ACT and g la garde qui doit être satisfaite pour executer a

et≈v =

≈a(g) : a ∈ ACT and g la garde qui doit être satisfaite pour executer a

La sémantique de P (P (V ∪

≈V )) est comme suit :

∼v =

∼a(g) ∈ RefGRA(l) : signie que l'action a peut être refusée en perma-

nence au niveau de la localié l. Ce refus est possible, mais pas certain. Cettecertitude aura lieu après la satisfaction de garde g.≈v =

≈a(g) ∈ RefGRA(l) : signie que l'action a est temporairement refusée au

niveau de la localié l. Ce cas de blocage se présente lorsque au moins uneaction de durée non nulle qui a causé a n'a pas encore terminé son exécution.

La determinisation du GRA est faite selon le principe detaillé dans [Kitouni et al., 2012c]Nous présentons dans les gures (9.1) et (9.2) un exemple du GRAM′ associéau DATA*M représentant une machine à café.

74

Figure 9.1 DATA*M représentant une machine à café

Figure 9.2 GRAM′ associé àM

9.2 Génération d'un Graphe de Refus Agrégé(GRA)

La génération d'un GRA se fait en 5 étapes :En entrée : Spécication DATA* Determinisation du DATA* Calcul des refus permanents. Calcul des refus temporaires. Décoration de chaque état par l'ensemble des refus (actions interdites, refuspermanent, refus temporaire).

Calcul de l'automate de région agrégé.En sortie : Graphe de Refus Agrégé

75

9.3 Testeur canonique

Un testeur canonique est capable de détecter toute implémentation nonconforme à sa spécication.Une implémentation I est dite conforme à sa spécication S si elle refuse lamême action après la même trace temporisée que sa spécication. Cela veutdire I et S ont les mêmes traces temporisées et les mêmes refus.Notre testeur canonique est composé de trois verdicts ( pass, inconclusive, fail). pass :veut dire que le test a été exécuté avec succès. Il décore les localitésaccessibles.

inconclusive :se produit par le non-determinisme présent dans le système,il est capturé dans les refus permanents.

fail :se produit dans deux cas :• Si les actions sont interdites.• Si une action est oerte malgré que sa garde n'est pas vériée.Ce type de verdict permet de conclure que l'implémentation n'est pasconforme à la spécication.

Ce testeur canonique génère les cas de test à partir du graphe de refus agrégé.toutes les traces du testeur canonique sont considérées comme des cas detest. Une trace temporisée concrète est calculée en choisissant une valeurdiscrète(un point)au niveau des régions.Le testeur canonique M” associé au GRA M′ est présenté dans la gure(9.3). La gure (9.4)présente un exemple d'un cas de test généré à partir dutesteur canoniqueM” avec un verdict pass.

9.4 Transformation d'un DATA* à un Graphe

de Refus Agrégé et à un testeur canonique

Dans cette section nous proposons un seul méta-modèle pour le Graphes deRefus Agrégé et pour le testeur canonique ainsi qu'une grammaire pour lagénération d'un Graphes de Refus Agrégé et du testeur canonique plus les casde test à partir d'un DATA*. Le méta-modèle d'un DATA* est déjà présentédans la section 8.4.1.Pour générer des DATA* de grandes tailles, nous utilisons le même pro-gramme python présenté dans la section 8.3.

76

Figure 9.3 Testeur canoniqueM” associé àM′

Figure 9.4 Cas de test associé àM”

9.4.1 Méta-modèle d'un Graphe de Refus Agrégé et d'untesteur canonique

Notre méta-modèle est un diagramme de classes composé des classes sui-vantes (gure 9.5) :

77

La classe TRRG-Canonical-state : Cette classe représente les localitésdu GRA et du testeur canonique, chaque localité possède trois attri-buts qui sont le nom (name), une région d'horloge (clock-region) etl'ensemble des refus (refusal).

L'association TRRG-Canonical-transition : Représente les transitionsdu GRA et du testeur canonique , chaque transition est identiée parune action.

La classe TRRG-Canonical-StateInit : Cette classe représente la loca-lité initiale du GRA et du testeur canonique, elle hérite les attributs dela classe TRRG− Canonical − state.

La classe TRRG-Canonical-StateFin : Cette classe représente la loca-lité nale du GRA et du testeur canonique, elle hérite les attributs dela classe TRRG− Canonical − state.

Lors de la modélisation dans AToM3, chacune de ces classes a une apparencegraphique distincte.

Figure 9.5 Méta-modèle d'un GRA/testeur canonique

9.4.2 Outil de modélisation du Graphe de Refus Agrégé

Le méta-modèle ainsi déni(gure 9.6) nous permet la génération d'un outilpour la modélisation des exemples en GRA.

78

Figure 9.6 Outil de modélisation du GRA et du testeur canonique

9.4.3 La grammaire de graphe proposée

La grammaire proposée permet de générer des GRA, des testeurs canoniqueset des cas de test, elle est composée de 23 règles, reparties en deux catégorie.La première catégorie contient les 16 premières règles ; ces règles permettentde construire le GRA.

La 1 ère règle : [propriété 1](Figure 9.7)calcule l'ensemble des refus asso-cié à l'état initial du DATA*.

Figure 9.7 Calcul de l'ensemble des refus associé à l'état initial du DATA*(règle 1)

La règle 2 : [propriété 2](Figure 9.8)permet la déterminisation et le calculdes refus dans le cas d'un système non-deterministe.

79

Figure 9.8 Déterminisation et calcul des refus dans le cas d'un systèmenon-deterministe(règles 2)

Les règles 3 et 4 : [propriétés 3 et 4](Figure 9.9)permettent de calculer lesrefus associés au reste du DATA*.

Figure 9.9 Calcul des refus associés au reste du DATA* (règles 3 et 4)

La règle 5 : [propriété 5](Figure 9.10) génère la 1iere localité du GRA as-socié à l'état initial du DATA* où toutes les horloges sont remises àzero.

Figure 9.10 Génèration de la 1iere localité du GRA (règle 5)

Les règles 6 et 7 : [propriétés 6 et 7](Figure 9.11)permettent de générer lereste du GRA.

Les règles 8 et 9 : [propriétés 8 et 9](Figure 9.12)permettent de générerles localités du GRA dans le cas d'un système non-deterministe.

80

Figure 9.11 Génération du reste du GRA(règles 6 et 7)

Figure 9.12 Génération des localités du GRA dans le cas d'un systèmenon-deterministe (règles 8 et 9)

La règle 10 : [propriété 10](Figure 9.13)génère la localité nale du GRA.

Figure 9.13 Génèration de la localité nale du GRA (règle 10)

Les règles 11, 12 et 13 : [propriétés 11, 12 et 13](Figure 9.14)permettentd'éliminer les liens génériques entre DATA* et GRA.

Les règles 14, 15 et 16 : [propriétés 14, 15 et 16](Figure 9.15)éliminent lareprésentation graphique du DATA*.La deuxième catégorie contient les règles du 17ieme jusqu'au 23ieme ;ces règles permettent la construction du testeur canonique et la géné-ration des cas de test.

La règle 17 : [propriété 17](Figure 9.16)génère la première localité du tes-teur canonique à partir de la première localité du GRA.

81

Figure 9.14 Elimination des liens génériques entre DATA* et GRA (règles11, 12 et 13)

Figure 9.15 Elimination de la représentation graphique du DATA*(règles14, 15 et 16)

Figure 9.16 Génération de la première localité du testeur canonique(règle17)

La règle 18 : [propriété 18](Figure 9.17)génère les localités du testeur ca-nonique dans le cas d'un système non-deterministe.

La règle 19 : [propriété 19](Figure 9.18)génère le reste des localités du tes-teur canonique.

La règle 20 : [propriété 20](Figure 9.19)génère la localité nale du testeurcanonique.

Les règles 21, 22 et 23 : [propriétés 21, 22 et 23](Figure 9.20)éliminentles refus des localités et génère les cas de test.

82

Figure 9.17 Génération des localités du testeur canonique dans le casd'un système non-deterministe(règle 18)

Figure 9.18 Génération du reste des localités du testeur canonique(règle19)

Figure 9.19 Génération de la localité nale du testeur canonique(règle20)

Figure 9.20 Elimination des refus et la génération des cas de test(règles21, 22 et 23)

83

9.5 Cas d'étude

cette section est une continuité de la section 8.5. Nous avons appliqué notreoutil sur le DATA* SRB (gure 8.16),et nous avons obtenu automatiquementle GRA SRB (gure 9.21) ainsi que le testeur canonique SBR (gure 9.22).La gure (gure 9.23) représente un cas de test généré à partir du testeurcanonique SBR.

Figure 9.21 GRA SRB associé au DATA* SBR (8.16)

Conclusion

Dans ce chapitre, nous avons proposé une approche pour tester les systèmestemporisés en se basant sur la transformation de graphes. En eet, nous avonstransformé un DATA* en GRA et nous avons généré un testeur canoniqueainsi que des cas de test.

84

Figure 9.22 testeur canonique SBR

Figure 9.23 Exemple d'un cas de test

85

Conclusion et Perspec-

tives

Conclusion

Les travaux présentés dans ce document se situent dans le cadre du test dessystèmes temps-réel en utilisant la transformation de graphes et l'environne-ment AToM3.D'abord, nous avons proposé une approche pour la déterminisation des auto-mates temporisés avec durées d'actions DATA de grandes tailles. Nous avonsélaboré un programme en langage python qui transcrit un automate DATAprésenté sous format texte (un chier texte) en un automate DATA sousformat python, dans un chier python respectant la syntaxe d'AToM3. Parla suite, nous avons proposé une démarche automatisée pour transformerun DATA en un DATA déterministe, en puisant du concept de la méta-modélisation.Dans notre deuxième contribution, nous avons proposé une approche pour lagénération d'un automate des régions agrégé à partir d'un DATA*, le but decette transformation est de fournir une abstraction nie d'un modèle DATA*de grande taille. Nous avons élaboré un programme en langage python quitranscrit un automate DATA* présenté sous format dotty en un automateDATA* sous format python, respectant la syntaxe d'AToM3. Cette dernièreopération nous permet l'interfaçage avec d'autres outils existants.Notre dernière contribution consiste a proposé une approche pour tester lessystèmes temporisés. En eet, nous avons transformé un DATA* en GRA etnous avons généré un testeur canonique ainsi que des cas de test.

86

Perspectives

Plusieurs perspectives de recherches et de réalisation se dessinent à l'issue deces travaux. En premier lieu nous proposons l'emploie des objectifs de testcomme mécanisme de sélection des cas de test an de diminuer leur nombre.D'autre part nous proposons l'application de ce résultat sur les protocoles decommunication.

87

Bibliographie

[AGG, 2010] AGG (2010). http ://tfs.cs.tu-berlin.de/agg/.

[Alur et Dill, 1994] Alur, R. et Dill, D. L. (1994). A theory of timedautomata. Theoretical Computer Science, 126(2):183235.

[Andries et al., 1999] Andries, M., Engels, G., Habel, A., Hoffmann,B., Kreowski, H. J., Kuske, S., Pump, D., Schürr, A. et Taent-zer, G. (1999). Graph transformation for specication and programming.Science of Computer programming, 34(1):154.

[Arnold, 1992] Arnold, A. (1992). Systèmes de transitions nis et séman-tique des processus communicants. Masson,Paris.

[Arnold, 1994] Arnold, A. (1994). Hypertransition systems. STACS'94,LNCS, Springer-Verlag, 775:327338.

[atom3, 2010] atom3 (2010). http ://-moncs.cs.mcgill.ca/msdl/research/projects/atom3.html.

[Baer, 1993] Baer, B. (1993). A conformance testing approach for managedobjects. In 4th IFIP/IEEE International Workshop on Distributed SystemOperations and Management. Long Branch, New Jersey.

[Bahri, 2011] Bahri, M. R. (2011). Une approche intégrée Mobile-UML/Réseaux de Petri pour l'Analyse des systèmes distribués à based'agents mobiles. Thèse de doctorat, Université de Mentouri, Constan-tine.

[Belala, 2010] Belala, N. (2010). Modèles de Temps et leur Intérêt à laVérication Formelle des Systèmes Temps-Réel. Thèse de doctorat, Uni-versité Mentouri, 25000 Constantine.

88

[Belala et Saidouni, 2005] Belala, N. et Saidouni, D. E. (2005). Non-atomicity in timed models. The International Arab Conference on Infor-mation Technology (ACIT).

[Belinfante et al., ] Belinfante, A., Feenstra, J., de Vries, R. G.,Tretmans, J., Goga, N., Feijs, L., Mauw, S. et Heerink, L. For-mal test automation : A simple experiment. In 12th Int.Workshop onTesting of Communicating Systems.

[Belmokadem, 2006] Belmokadem, H. (2006). Vérication Des PropriétésTemporisées Des Automates Programmables Industriels. Thèse de docto-rat, L'école normale supérieure de Cachan.

[Bouyer, 2002] Bouyer, P. (2002). Modèles et Algorithmes pour la Véri-cation des Systèmes Temporisés. Thèse de doctorat, Laboratoire de Spé-cication et Vérication, Cachan, France.

[Bérard et al., 1998] Bérard, B., Diekert, V., Gastin, P. et Petit, A.(1998). Characterization of the expressive power of silent transitions intimed automata. Fundamenta Informatica, 36(2-3):145182.

[Brinksma, 1988] Brinksma, E. (1988). A theory for the derivation of test.Protocol Specication, Testing and Verication, pages 6374.

[Brinksma et Briones, 2005] Brinksma, E. et Briones, L. B. (2005). Testgeneration framework for quiescent real-time systems. FATES, 3395:6478.

[Brinksma et al., 1987] Brinksma, E., Scollo, G. et Steenbergen, C.(1987). Lotos specications, their implementations and their tests. thesixth international workshop on protocol specication, testing and verica-tion, pages 349360.

[Brinksma et Tretmans, 2000] Brinksma, E. et Tretmans, J. (2000). Tes-ting transition systems. the proceeding of Modelling and Verication ofParallel Processes, 2067:187195.

[Chaoui et al., 2010] Chaoui, A., Saidouni, D. E., Bouarioua, M., Be-krar, S. et Kerkouche, E. (2010). An automatic transformation ofmaximality-based labeled transitions models to mixed refusal graphs usinggraph grammars. MISC 2010 : International Symposium on Modelling andImplementation of Complex Systems.

[Chartrand et Zhang, 2009] Chartrand, G. et Zhang, P. (2009). Chro-matic Graph Theory, page 27.

[Chow, 1978] Chow, T. (1978). Testing software design modeled by nitestate machins. IEEE transactions on Software Engeeniering, pages 178187.

89

[Courtiat et Saïdouni, 1995] Courtiat, J. P. et Saïdouni, D. E. (1995).Relating maximality-based semantics to action renement in process al-gebras. 7th Int Conf on Formal Description Techniques (FORTE?94),pages 293308.

[Czarnecki et Helsen, 2003] Czarnecki, K. et Helsen, S. (2003). Classi-cation of model transformation approaches. OOPSLA'03 Workshop onGenerative Techniques in the Context of Model- Driven Architecture.

[Czarnecki et Helsen, 2006] Czarnecki, K. et Helsen, S. (2006). Feature-based survey of model transformation approaches. IBM SYSTEMS JOUR-NAL, 45(03).

[Darmaillacq et al., 2004] Darmaillacq, V., Fernandez, J. C.,Groz, R.,Mounier, L. et Richier, J. L. (2004). Eléments de modélisation pourle test de politiques de sécurité. Ce travail a été soutenu par le projetProtestat de l'ACI Sécurité et le projet IMAG- Modeste.

[Dotty, 2011] Dotty (2011). Graphviz home page.http ://www.graphviz.org/.

[Drira, 1992] Drira, K. (1992). Transformation et Composition DesGraphes de Refus : Analyse de la Testabilité. Thèse de doctorat, Uni-versité Paul Sabatier de Toulouse.

[Dssouli et al., 1997] Dssouli, R., Elqortobi, A. et Ennouaary, A.(1997). Génération des tests temporisés. Colloque Francophone sur l'ingé-nierie des Protocoles de communication CFIP'97.

[ElMansouri, 2009] ElMansouri, R. (2009). Modélisation et Véricationdes processus métiers dans les entreprises virtuelles : Une approche ba-sée sur la transformation de graphes. Thèse de doctorat, Université deMentouri, Constantine.

[Group, 2004] Group, O. M. (2004). Model driven architecture (mda). URLhttp ://www.omg.org/mda.

[Hachichi et al., 2012a] Hachichi, H.,Kitouni, I., Bouaroudj, K. et Sai-douni, D. E. (2012a). A graph transformation approach for testing timedsystems. The 18th International Conference on Information and SoftwareTechnologies (ICIST 2012), Kaunas, Lithuania, published as a volume ofSpringer-Verlag CCIS 319, pages 123137.

[Hachichi et al., 2012b] Hachichi, H.,Kitouni, I., Bouaroudj, K. et Sai-douni, D. E. (2012b). A graphical tool for testing timed systems based onmeta-modeling and graph grammars. The International Journal of Com-puter Science Issues - IJCSI, 9(4).

90

[Hachichi et al., 2011] Hachichi, H., Kitouni, I. et Saidouni, D. E.(2011). A graph grammar approach for calculation of aggregate regionsautomata. The International Arab Conference on Information Technology(ACIT'2011). Naif Arab University for Security Science (NAUSS) Riyadh,Saudi Arabia.

[Hachichi et al., 2012c] Hachichi, H., Kitouni, I. et Saidouni, D. E.(2012c). Transforming data* with dotty format to aggregate region au-tomaton. International Journal of Computer Applications, 37(10):3542.

[Hachichi et al., 2012d] Hachichi, H., Kitouni, I. et Saidouni, D. E.(2012d). Utilisation de la transformation de graphes pour le calcul desautomates des régions agrégés. The Sixth IEEE International Conferenceon Sciences of Electronic, Technologies of Information and Telecommuni-cations (SETIT 2012). Sousse, Tunisia.

[Hamrouche, 2010] Hamrouche, H. (2010). Une approche de transforma-tion des diagrammes d'activité d'uml vers csp basée sur la transformationde graphes. Mémoire de D.E.A., Ecole Doctorale en Informatique de l'Est.

[Hennessy, 1985] Hennessy, M. (1985). Acceptance trees. ACM Journal,32(4):896928.

[Hoare, 1985] Hoare, C. A. R. (1985). Communicating sequential processes.Prentice-Hall.

[Kaboré, 1995] Kaboré, P. (1995). Une Approche de Test de ConformitéDes Systèmes D'administration de Réseaux. Thèse de doctorat, UniversitéHenri Poincaré, Nancy I, Centre de Recherche en Informatique de Nancy(CRIN).

[Kadima, 2005] Kadima, H. (2005). Mda, une conception orientée objetguide par les modèles. DUNOD.

[Karsai et Agrawal, 2004] Karsai, G. etAgrawal, A. (2004). Graph trans-formations in omg's model-driven architecture. Lecture Notes in ComputerScience, Springer Berlin, Heidelberg, 3062:243259.

[Kerkouche, 2011] Kerkouche, E. (2011). Modélisation Multi-Paradigme :Une Approche Basée sur la Transformation de Graphes. Thèse de doctorat,Université de Mentouri, Constantine.

[Khorchef, 2006] Khorchef, F. S. (2006). Un Cadre Formel pour le Test deRobustesse des Protocoles de Communication. Thèse de doctorat. Thèseprésentée à l'université Bordeaux I.

[Kitouni, 2008] Kitouni, I. (2008). Déterminisation des automates tem-porisés avec durées d'actions pour le test formel. Mémoire de D.E.A.,Université de Mentouri, 25000 Constantine.

91

[Kitouni et al., 2012a] Kitouni, I., Hachichi, H., Bouaroudj, K. et Sai-douni, D. E. (2012a). Reducing timed automata : A new approach. Inter-national Journal of Information Sciences and Techniques (IJIST), 2(4):1527.

[Kitouni et al., 2012b] Kitouni, I., Hachichi, H., Bouarroudj, K. etSaidouni, D. E. (2012b). Durational actions timed automata : Determi-nization and expressiveness. International Journal of Applied InformationSystems, 4(2):111.

[Kitouni et al., 2012c] Kitouni, I.,Hachichi, H.,Bouarroudj, K. et Sai-douni, D. E. (2012c). Timed refusals graph for non-deterministic timedsystems. International Journal of Computer Science and Telecommunica-tions IJCST, 3(9).

[Kitouni et al., 2012d] Kitouni, I., Hachichi, H. et Saidouni, D. E.(2012d). A simple approach for reducing timed automata. The 2ndIEEE International Conference on Information Technology and e-Services(ICITeS 2012), Sousse, Tunisia.

[Kohavi, 1978] Kohavi, Z. (1978). Switching and nite automata theory.New York.

[Krichen et Tripakis, 2004] Krichen, M. et Tripakis, S. (2004). Black-box conformance testing for real-time systems. 11th International SPINWorkshop, Barcelona, Spain.

[Laurençot et al., 2000] Laurençot, P., Mesnard, E. et Toussaint, J.(2000). Mise en ÷uvre de tests temporisés. RTS'99.

[Lee et Yannakakis, 1996] Lee, D. et Yannakakis, M. (1996). Principlesand methods of testing nite state machines - a survey. volume 84, pages10901123. Proceedings of The IEEE.

[Myers, 1980] Myers, G. J. (1980). Review of "the art of software testing". Wiley-Interscience, 11(4, Summer 1980):23 23.

[Naito et Tsunoyama, 1981] Naito, S. et Tsunoyama, M. (1981). Faultdetection for sequential machines by transition tours. IEEE Fault TolerantComput Conference.

[Nielsen, 2000] Nielsen, B. (2000). Specication and test of real-time sys-tems. Thèse de doctorat, Aalborg University.

[Prigent, 2003] Prigent, A. (12 décembre 2003). Le Test Des SystémesTemps-Réel Paramétrés : Application à la Conception D'architecturesAvioniques. Thèse de doctorat, délivré conjointement par l'école Centralede Nantes et l'université de Nantes.

92

[Python, 2010] Python (2010). Python home page.htpp ://www.python.org.

[Rational, 2003] Rational (2003). http://Www.Rational.Com/Products/Tstudio/Prodinfo.Jsp.

[Rollet, 2004] Rollet, A. (2004). Test de robustesse des systèmes temps-réel. Thèse de doctorat. Laboratoire CRESTIC, Université de Reims -Champagne Ardenne.

[Rozenberg, 1999] Rozenberg, G. (1999). Handbook of graph grammarsand computing by graph transformation. World Scientic, 1.

[Saidouni, 1996] Saidouni, D. E. (1996). Sémantique de Maximalité : Ap-plication au Ranement d'actions en LOTOS. Thèse de doctorat, LAAS-CNRS, 7 av. du Colonel Roche, 31077 Toulouse Cedex France.

[Saidouni et al., 2010a] Saidouni, D. E., Kitouni, I. et Hachichi, H.(2010a). Application de l'approche de transformation de graphes pourla déterminisation des automates temporisés avec durées d'actions. 7èmeSéminaire National en Informatique BISKRA (SNIB'2010), pages 229236.

[Saidouni et al., 2010b] Saidouni, D. E., Kitouni, I. et Hachichi, H.(2010b). A graph grammar approach for durational action timed auto-mata determinization. The International Arab Conference on InformationTechnology (ACIT'2010).University of Garyounis, Benghazi,Libya.

[Salva et al., 2001] Salva, S., Petitjean, E. et Fouchal, H. (2001). Asimple approach to testing timed systems. FATES'01, Formal Approachesto Testing of Software.

[Tretmans, 1996] Tretmans, J. (1996). Test generation with inputs, out-puts, and repetitive quiescence. Software Concepts and Tools, pages 103120.

[Tretmans, 1997] Tretmans, J. (1997). Repetitive quiescence in implemen-taion and testing. Formale Beschreibungstechniken fur verteilte Systeme,(315):2337.

[Tretmans, 2001] Tretmans, J. (2001). An overview of osi conformancetesting. Rapport technique, Formal Methods Tools group University ofTwente.

[VIATRA, 2010] VIATRA (2010). Visual automated transfor-mations for formal verication and validation of uml mo-dels. URL :http ://dev.eclipse.org/viewcvs/indextech.cgi/gmt-home/subprojects/VIATRA2/index.html.

93

IX