Sécurité dans les systèmes temps réel

Chapitre 2

Pré-requis

2.1 Systèmes temps réel

2.1.1 Introduction

Nous apporterons dans cette section quelques définitions largement inspirées de [7] et notations qui pourront servir à la compréhension de la suite de ce mémoire.

Un système temps réel est constitué d'un ensemble de tâches et chacune d'elles doit effectuer une quantité de calculs. Les résultats produits par ces différentes tâches doivent être d'une certaine qualité mais aussi être fournis avant un instant donné, que nous appellerons l'échéance de cette tâche.

Ces systèmes sont utilisés principalement dans des applications critiques qui ne peuvent pas se permettre de fournir un résultat erroné ou incomplet au moment de l'échéance, comme pour le contrôle d'une centrale nucléaire, le contrôle aérien, ...

2.1.2 Les travaux

Toute tâche n^o i (que nous noterons Ti) prise dans un ensemble de n tâches (i ? [1, n]) composant le système, partage la quantité de calculs qu'elle doit effectuer en un certain nombre de travaux. Ces travaux obtiennent le processeur à intervalle régulier (périodique) ou non. Chaque travail (aussi appelé instance

ou job en anglais) obtient le processeur à un instant donné et peut s'exécuter sur une certaine durée.

Définition Travail: Un travail _ôij, soit le j^e travail de la tâche Ti sera caractérisé par le tuple (a, e, d). Un instant d'arrivée _aij, un temps d'exécution _eij et une échéance _dij. Le travail _ôij devra donc recevoir _eij unités d'exécution sur l'intervalle [aij, dij)

Il existe différentes classes de niveaux de contraintes temporelles, on parle d'échéances strictes (hard), fermes (firm) ou souples (soft) [1].

- Un système temps réel est dit à échéances strictes (hard deadlines) lorsqu' on ne peut rater aucune échéance, les conséquences en seraient catastrophiques;

- Pour les échéances fermes (firm deadlines), les conséquences sont moins sévères, mais la valeur de l'exécution d'un travail après son échéance est nulle et donc d'aucune utilité.

- Un travail possédant une échéance souple (soft deadline) peut terminer son exécution après son échéance, son exécution après l'échéance a toujours une certaine valeur, bien que celle-ci décroisse avec le temps suivant l'échéance.

2.1.3 Les tâches

Classiquement dans un système temps réel, les calculs (l'exécution de ces travaux) sont récurrents, les tâches peuvent être périodiques ou sporadiques. Nous nous focaliserons dans ce mémoire sur les systèmes à tâches périodiques.

Définition Tâche périodique : Une tâche périodique Ti est caractérisée par le tuple (Ai, Pi, Di, Ci)

- Ai est la date d'arrivée du premier travail de la tâche Ti, ce qui ne signifie pas que celui-ci s'exécutera à cette date.

- Pi est la période, c.-à-d. la durée qui sépare deux arrivées successives de travaux. Le deuxième travail d'une tâche Ti ne pourra donc pas s'exécuter avant l'instant Ai + Pi.

- Di est l'échéance de la tâche Ti, qui dénote la limite supérieure de temps entre l'arrivée d'un travail et la fin de son exécution.

- Ci est le temps d'exécution de chaque travail de la tâche Ti, nous parlons aussi de WCETi (Worst Case Execution Time) pour dénoter la limite supérieure du temps d'exécution de chaque travail de la tâche Ti.

Mi, Oi : Dans la partie sur le « Reward-based Scheduling », ces notations dénotent respectivement la partie obligatoire (Mandatory) et optionnelle (Optional) d'une tâche Ti. Les notations mi et oi, dénotent respectivement la limite supérieure du temps d'exécution de la partie obligatoire Mi et la limite supérieure sur le temps d'exécution de la partie optionnelle Oi. Nous y reviendrons par la suite.

Chaque tâche génère un travail à chaque instant Ai+k.Pi avec une échéance à l'instant Ai + k. Pi + Di pour tout entier k ~ 0.

Les tâches sporadiques sont similaires aux tâches périodiques à l'exception faite que Pi correspond à la durée minimum qui sépare deux arrivées de travaux delatâche Ti.

Mais il existe également des tâches non récurrentes dites apériodiques, elles sont utilisées en général pour traiter des alarmes et des états d'exception, l'instant de réveil n'est pas connu au départ et il n'y a donc pas de période.

Chaque tâche a une certaine proportion d'exécution par rapport à sa période, nous parlerons d'utilisation que l'on définit mathématiquement comme : U(Ti) = Ci/Pi. L'utilisation d'un système S est la somme des utilisations des tâches qu'il contient, autrement dit : U(S) = >ITi?S U(Ti).

Dans la partie sur le « Reward-based Scheduling », nous parlerons d'utilisation par les parties obligatoires d'un système composé de n tâches. Nous noterons ce facteur d'utilisation U_m que nous définissons par U_m = >In i=1mi/Pi, c.-à-d. le rapport sur le temps d'exécution des parties obligatoires par rapport au temps total disponible. U quand à lui, désignera le facteur d'utilisation total (parties obligatoires et optionnelles confondues).

2.1.4 Le système

Il existe plusieurs expressions qualifiant un système constitué de n tâches, on parle de systèmes:

- à échéance contrainte : signifie que l'échéance de toute tâche du système
ne peut pas être supérieure à la période de celle-ci (Di Pi Vi E [1, n]).

- à échéance sur requête : signifie que l'échéance de toute tâche du système coïncide avec la période de celle-ci (Di = Pi Vi E [1, n], chaque travail d'une tâche doit se terminer avant l'arrivée du travail suivant de cette même tâche. C'est donc un cas particulier de système à échéance contrainte.

- à échéance arbitraire : aucune contrainte n'est imposée entre l'échéance et la période.

- à départ simultané : l'instant d'arrivée du premier travail de chaque tâche coïncide avec les autres, on peut donc poser Ai = 0 Vi E [1, n] sans nuire à la généralité.

Nous nous intéresserons plus particulièrement dans nos analyses aux systèmes à échéance sur requête et à départ simultané.

Le processeur

Il existe deux types d'environnement possibles pour un même système de tâches:

- monoprocesseur;

- multiprocesseur.

Un environnement multiprocesseur constitué de k processeurs peut exécuter k unités de temps d'exécution simultanément contrairement à un environnement monoprocesseur qui est limité à une exécution à la fois. Nous resterons dans le cadre de ce mémoire sur des environnements monoprocesseur.

Définition oisif: Nous reprenons la traduction de la terminologie anglaise : « idle » (inoccupé) en parlant du processeur ou d'instants pour dire de ceux-ci qu'ils sont inutilisés, autrement dit qu'il n'y a pas de travail en cours d'exécution.

Nous parlerons également d'unités de temps oisives, pour désigner les moments où le processeur n'exécute aucun travail.

2.1.5 L'ordonnancement

L'ordonnancement est le mécanisme permettant de choisir la tâche qui va être exécutée par le processeur à un instant donné. L'algorithme qui va effectuer ce choix est appelé l'ordonnanceur (le scheduler).

Il existe deux manières d'appeler cet ordonnanceur:

- appels à intervalle régulier (par exemple à chaque unité de temps);

- appels basés sur des évènements comme l'arrivée, la fin d'exécution ou l'échéance d'un travail.

Nous expliquerons par la suite pourquoi nous avons préféré utiliser une méthode basée sur des évènements dans nos simulations.

A chaque fois qu'il est appelé, l'ordonnanceur va choisir le travail qui doit être exécuté au moment de l'appel si celui-ci existe bien entendu, car il est probable qu'aucun travail ne soit disponible à cet instant, le processeur restera alors oisif. Un ordonnancement dit « préemptif » signifie qu'une tâche peut être interrompue par une autre plus prioritaire. Si le processus choisi, c.-à-d. le programme en cours d'exécution, est différent de celui exécuté actuellement, l'ordonnanceur effectue alors un changement de contexte qui consiste en une sauvegarde des données de la tâche actuelle et une restauration des données de la nouvelle tâche si cela est nécessaire, on appelle ce changement de contexte une «préemption » et nous dirons du travail interrompu qu'il est «préempté».

Dans un ordonnanceur temps réel, si le système arrive à ordonnancer toutes ses tâches en respectant leurs échéances, nous dirons de celui-ci qu'il est ordonnançable.

L'ordonnanceur va donc devoir assigner des priorités aux différentes tâches ou aux travaux de ces tâches. Il existe donc deux types d'assignations des priorités :

1. priorité fixe : également appelé assignation à priorité statique, chaque tâche reçoit une priorité par rapport aux autres à l'initialisation du système et chaque travail lancé hérite de la priorité de sa tâche;

2. priorité dynamique : la priorité est donnée aux travaux des tâches, non plus aux tâches. La priorité peut passer à un travail d'une autre tâche pendant l'exécution du système, selon la règle d'assignation utilisée, qui peut se baser par exemple sur le temps restant avant la prochaine échéance ou le temps d'exécution déjà écoulé pour ce travail.

Définition faisable - ordonnançable[18] : On dit d'un ordonnancement qu'il est faisable si chaque tâche se termine avant son échéance dans cet ordonnancement. Un système est ordonnançable s'il existe un ordonnancement faisable pour ce système.

Définition optimalité : Une règle d'assignation de priorité R désigne la façon dont la priorité de sélectionner un travail par rapport à un autre est définie. On dit que R est optimale si, lorsqu'un système est faisable, il est ordonnançable étant donné la règle R.

Pour tester l'ordonnançabilité d'un système en posant l'hypothèse que celui- ci est constitué de n tâches à échéance contrainte et à départ simultané, il suffit de tester celui-ci jusqu'à l'instant P que nous appellerons l'hyper-période et qui est égale au plus petit commun multiple des périodes des différentes tâches composant le système.

P=ppcm{P1,P2,...,P_n}

En effet, à cet instant et sous ces hypothèses, nous nous retrouvons dans la même position qu'à l'instant initial : toutes les tâches envoient un nouveau travai l.

« Earliest Deadline First »

Nous allons présenter maintenant la règle d'assignation que nous utiliserons dans notre étude, EDF ( Earliest Deadline First », plus proche échéance d'abord). EDF est une règle d'assignation à priorité dynamique. Lorsqu'un évènement survient : comme la fin de l'exécution d'un travail ou l'arrivée d'un nouveau travail dans le système, l'ordonnanceur va sélectionner parmi tous les travaux prêts à être exécutés celui dont l'échéance est la plus proche. Ce travail sera alors exécuté sur le processeur. Autrement dit, plus le travail doit être exécuté rapidement, plus il aura de chance d'être exécuté.

Cette règle d'assignation est optimale, car EDF trouve toujours un ordonnancement faisable s'il en existe un. Pour un système S à échéance sur requête, EDF à une borne supérieure de 100% sur l'utilisation, cela signifie que si U(S) = 1 alors il est garanti qu' EDF trouvera un ordonnancement faisable contrairement à une règle d'assignation à priorité fixe comme RM ( Rate Monotonic ») qui donne une priorité plus élevée aux tâches ayant les périodes les plus courtes. La borne sur l'utilisation pour laquelle il est garanti de trouver un ordonnancement faisable n'est que de ln 2 ~ = 69,3%. Cette borne peut-être augmentée à 83% et 78% si nous nous limitons respectivement à 2 ou 3 tâches, d'après la démonstration développée dans [13], mais reste toutefois inférieure àEDF.

Donnons maintenant un exemple de système afin d'illustrer le principe du fonctionnement d'EDF.

Prenons un système à échéance sur requête composé de 2 tâches T1(P1 = D1 = 5, C1 = 3) et T2(P2 = D2 = 3, C2 = 1), voici comment EDF va ordonnancer les différents travaux de ces tâches dont le schéma de l'ordonnancement est représenté sur la figure 2.1.

T1,2

T1,2

T1 ,3

1 4

56

7 9

10 13

T1

o o o

T1,1

		T2,3		T2,4
T2,2						T2,5

o o o o o

0 1 45 67 9 10 13 14

T2,1

T2

FIG. 2.1 - Exemple d'ordonnancement de 2 tâches avec la règle d'assignation EDF

Les deux tâches sont à départ simultané et envoient chacune leur premier travail à l'instant 0 (autrement dit O1 = O2 = 0). EDF sélectionne le travail i-2,1 pour être exécuté car l'échéance d2,1 < d1,1. A l'instant 1, _i-1,1 se termine et EDF doit choisir à nouveau un travail, il ne reste que _i-1,1 qui continue son exécution à l'instant 3 lors de l'arrivée d'un nouveau travail de T2 car son échéance est plus proche. Nous remarquons, qu'à l'instant 6, _i-1,2 est préempté lors de l'arrivée de i-2,3 car celui-ci possède une échéance d2,3 < d1,2.

Nous stoppons notre exemple à l'hyperpériode P = 15 = ppcm(5, 3) car à cet instant nous nous retrouvons exactement dans la même situation qu'à l'instant 0 et l'ordonnancement peut recommencer de la même manière indéfiniment.

Lorsque les échéances sont égales, le choix entre les deux travaux se fait arbitrairement en donnant priorité au travail en cours d'exécution, comme à l'instant 12 dans notre exemple où _i-1,3 poursuit son exécution.

2.2 Cryptologie

2.2.1 Introduction

La cryptologie est la science du secret, elle se divise en deux branches :

La cryptographie : qui étudie les différentes possibilités de cacher, protéger ou contrôler l'authenticité d'une information;

La cryptanalyse : qui étudie les moyens de retrouver cette information à partir du texte chiffré (de l'information cachée) sans connaitre les clés ayant servi à protéger celle-ci, c'est en quelque sorte l'analyse des méthodes cryptographiques.

La cryptographie doit garantir certains principes qualifiant la bonne sécurité d'un système:

1. Confidentialité : grâce à un chiffrement pour que les données soient illisibles par une personne tierce et ainsi garantir que l'information est restée secrète de bout en bout.

2. Authentification : afin que personne ne puisse se faire passer pour la source de l'information, que la provenance des données soit garantie.

3. Intégrité : pour que les données ne puissent pas être modifiées sans qu'on ne s'en rende compte.

2.2.2 Confidentialité

La confidentialité est historiquement le premier but des études en cryptographie : rendre secrètes des informations.

Cela se réalise par un chiffrement mathématique des données qui utilise comme paramètre une clé. Le chiffrement consiste à appliquer une suite d'opérations sur un texte clair, pour obtenir un texte chiffré, aussi appelé cryptogramme, ne pouvant être déchiffré que par l'entité qui possède la clé adéquate.

Il existe deux catégories de chiffrements:

Le chiffrement symétrique également appelé le chiffrement à clé secrète:

Le principe est de chiffrer le texte clair avec une clé et de le déchiffrer avec la même clé ou une clé dérivée de celle-ci. La clé n'est connue que par les deux entités s'échangeant des informations.

Le chiffrement asymétrique également appelé le chiffrement à clé publique: Les clés utilisées pour le chiffrement et le déchiffrement sont différentes et ne peuvent être déduites l'une de l'autre par un observateur extérieur sans la connaissance des informations nécessaires. Une des clés peut être connue de tous tandis que l'autre doit rester secrète. Le but étant que tout le monde puisse à l'aide d'une clé publique chiffrer des données que seule l'entité possédant la clé secrète puisse déchiffrer. La vision d'un ensemble de textes chiffrés ne doit apporter aucune information sur le texte clair, c'est ce qu'on appelle la notion de sécurité sémantique (propre au chiffrement asymétrique).

Dans le cadre de la sécurité dans les systèmes temps réel qui doivent respecter des contraintes de temps, nous nous intéresserons plus particulièrement au chiffrement symétrique qu'il est préférable d'utiliser car le chiffrement asymétrique a été montré comme plus complexe au niveau du temps de calcul [16].

2.2.3 Intégrité et authentification

Le réseau reliant les entités n'étant pas toujours sûr, il est important de contrôler la provenance des informations et de s'assurer qu'elles n'ont pas été modifiées en chemin, ce sont respectivement les principes d'authentification et d'intégrité des données.

Afin de garantir ces deux principes, on utilise des codes d'authentification de message (MAC : Message Authentication Code). Un MAC est un code envoyé avec le message, il est aussi appelé hachage ou empreinte du message. Le hachage correspond au message et permet de garantir la validité de celui-ci. Il est obtenu à partir d'un algorithme MAC qui prend deux paramètres en entrée: le message dont on désire garantir l'intégrité et une clé secrète connue des deux entités s'échangeant ce message.

La probabilité que des données différentes possèdent le même hachage est très faible, c'est ce qu'on appelle une « collision ». La probabilité de trouver une collision et que le message possédant le même hachage soit compréhensible par le récepteur est quasi nulle. Une modification même très légère des données provoque un changement radical au niveau du hachage obtenu. Si une modification a lieu entre la source et la destination, le hachage ne correspondra plus aux données et celles-ci seront rejetées par le récepteur.

Le fait d'utiliser une clé secrète partagée entre les deux entités en plus de la fonction de hachage garantit l'authenticité des données étant donné qu'un attaquant ne connaissant pas la clé ne peut envoyer des informations accompagnées d'un hachage correct de celles-ci.

Différentes méthodes existent pour créer une empreinte du message:

- une fonction de hachage utilisant une clé en paramètre en plus du message (ex : HMAC);

- un chiffrement par blocs (comme les méthodes CBC-MAC).