|
Faculté des sciences département d'inFormatique
|
|
|
|
MEMBRE DE L'ACADÉMIE UNIVERSITAIRE WALLONIE-BRUXELLES ET
DU PÔLE UNIVERSITAIRE EUROPÉEN BRUXELLES WALLONIE
|
|
Sécurité dans les systèmes
temps réel
Thomas VANDERLINDEN
Mémoire présenté sous la direction des
Professeurs Joël GOOSSENS et Olivier MARKOWITCH
en vue
de l'obtention du grade de Licencié en Informatique
Année
académique 2006-2007
1
Remerciements
Un mémoire est un travail de recherche ardu et long
mais intéressant. Malgré que ce soit un travail en solitaire, il
aurait été difficile de me passer de l'appui de nombreuses
personnes d'un point de vue académique et moral, à qui je tiens
à donner toute ma reconnaissance.
Tout d'abord, je souhaiterais remettre mes premiers
remerciements au professeur qui m'a suivi toute cette année en
organisant des réunions régulièrement, Monsieur
Joél Goossens, promoteur de ce mémoire.
Je tiens également à remercier Monsieur Olivier
Markowitch, codirecteur de ce travail, qui s'est lui aussi joint à
certaines de ces réunions, et sur qui je pouvais compter pour me fournir
des conseils dans le domaine de la cryptographie lorsque j'en avais besoin
ainsi que Monsieur Bernard Fortz pour m'avoir suggéré certaines
améliorations lors de la programmation des méthodes heuristiques
présentées dans ce mémoire et le professeur Hakan Aydin
pour avoir répondu à mes questions sur l'ordonnancement temps
réel par courrier électronique.
Je tiens à donner toute ma gratitude à mon
grand-père qui a pris la peine de relire ce travail pour apporter
quelques corrections orthographiques. Sur le plan moral, je tiens à
remercier mes parents, toute ma famille et mes amis, ils comptent
énormément pour moi, ils ne m'ont jamais abandonné durant
mes études et m'ont toujours encouragé durant
l'élaboration de ce mémoire.
Soyez tous sincèrement remerciés,
Thomas.
Table des matières
|
1
2
|
Introduction
1.1 Le problème
1.2 Organisation du mémoire
Pré-requis
|
5
5
6
7
|
|
2.1
|
Systèmes temps réel
|
7
|
|
|
2.1.1 Introduction
|
7
|
|
|
2.1.2 Lestravaux
|
7
|
|
|
2.1.3 Les tâches
|
8
|
|
|
2.1.4 Le système
|
9
|
|
|
2.1.5 L'ordonnancement
|
10
|
|
2.2
|
Cryptologie
|
13
|
|
|
2.2.1 Introduction
|
13
|
|
|
2.2.2 Confidentialité
|
14
|
|
|
2.2.3 Intégrité et authentification
|
15
|
|
3
|
Etatde l'art
|
16
|
|
3.1
|
Introduction
|
16
|
|
3.2
|
Qualité de service et longueur des clés
|
17
|
|
|
3.2.1 Introduction
|
17
|
|
|
3.2.2 Modélisation du système
|
18
|
|
|
3.2.3 L'algorithme d'ajustement de la qualité de service
|
19
|
|
|
3.2.4 Conclusion
|
22
|
|
3.3
|
Ordonnancement dynamique basé sur des niveaux de
sécurité .
|
23
|
|
|
3.3.1 Conclusion
|
25
|
|
3.4
|
Méthode SASES
|
25
|
|
|
3.4.1 Modélisation
|
26
|
|
|
3.4.2 Différents services
|
28
|
|
|
3.4.3 Calcul du bénéfice au système
|
34
|
|
|
3.4.4 L'algorithme SASES
|
35
|
|
|
3.4.5 Conclusion
|
36
|
TABLE DES MATIÈRES 3
3.5 Méthode en graphe de services 37
3.5.1 Modélisation 37
3.5.2 Recherche dans le graphe 38
3.5.3 Conclusion : Comparaison avec SASES 40
3.6 Conclusion 41
4 Récompense et sécurité
42
4.1 Introduction 42
4.2 Reward-Based Scheduling 43
4.2.1 Introduction 43
4.2.2 Une fonction de récompense 44
4.2.3 Modélisation du système 47
4.2.4 Calcul de la récompense moyenne du système
47
4.2.5 Approche Mandatory-First (parties obligatoires d'abord)
48
4.2.6 Optimalité 53
4.2.7 Optimalité avec des fonctions linéaires de
récompense 57
4.2.8 Optimalité avec des fonctions convexes de
récompense 60
4.3 Conclusion 62
5 Simulations 64
5.1 Introduction 64
5.2 Génération d'un système 65
5.2.1 Génération des périodes 65
5.2.2 Génération de l'ensemble de tâches
66
5.3 L'algorithme orienté évènement 68
5.3.1 La gestion des évènements 69
5.3.2 L'algorithme 70
5.4 Rappel du problème d'optimisation des temps optionnels
. . . 72
5.5 Notations utilisées 73
5.6 Le recuit simulé 74
5.7 La recherche tabou 77
5.8 Obtention d'une solution voisine 79
5.9 Expérimentation 81
5.9.1 Limites des algorithmes 81
5.9.2 Analyse avec des fonctions linéaires de
récompense . . 83
5.9.3 Simulation avec des fonctions convexes de récompense
83
5.10 Conclusion 87
6 Conclusion 89
A Complément à la démonstration de
H. Aydin 93
|
TABLE DES MATIÈRES
B Code source de la simulation
|
4
95
|
|
B.1
|
Système
|
95
|
|
B.1.1
|
Systeme.h
|
95
|
|
B.1.2
|
Systeme.cpp
|
97
|
|
B.2
|
|
Tâche
|
107
|
|
B.2.1
|
Tache.h
|
107
|
|
B.2.2
|
Tache.cpp
|
108
|
|
B.3
|
|
Travail
|
109
|
|
B.3.1
|
Travail.h
|
109
|
|
B.3.2
|
Travail.cpp
|
110
|
|
B.4
|
Générateur
|
111
|
|
B.4.1
|
Generateur.h
|
111
|
|
B.4.2
|
Generateur.cpp
|
111
|
|
B.5
|
|
Divers
|
113
|
|
B.5.1
|
Divers.h
|
113
|
|
B.5.2
|
Divers.cpp
|
113
|
|
B.6
|
|
Event
|
114
|
|
B.6.1
|
Event.h
|
114
|
|
B.6.2
|
Event.cpp
|
115
|
|
B.7
|
Solution
|
115
|
|
B.7.1
|
Solution.h
|
116
|
|
B.7.2
|
Solution.cpp
|
117
|
|
B.8
|
Main
|
|
122
|
|
B.8.1
|
Main.cpp
|
123
|
Chapitre 1
| 
