Exercices corrigés de NSI : processus, réseaux et sécurisation

a) Un processus est un programme EN COURS D'EXÉCUTION, accompagné de tout ce qui décrit son exécution : son code, ses données, sa pile, ses fichiers ouverts et la valeur de ses registres. L'état PRÊT signifie qu'il pourrait s'exécuter mais qu'aucun coeur ne lui est attribué. L'état ÉLU signifie qu'un coeur exécute effectivement ses instructions. L'état BLOQUÉ signifie qu'il attend un événement extérieur, lecture disque, saisie clavier, arrivée de données réseau, et qu'il ne pourrait donc rien faire même si un coeur était libre. Les transitions : l'ÉLECTION est décidée par l'ordonnanceur ; la PRÉEMPTION est provoquée par l'ordonnanceur, en général sur expiration d'un quantum de temps signalé par une interruption d'horloge ; le passage à BLOQUÉ est provoqué par le processus lui-même, lors d'un appel système bloquant ; le RÉVEIL est provoqué par l'arrivée de l'événement attendu, signalée au système par une interruption du périphérique.

b) Parce que la fin de l'attente ne dit rien sur la disponibilité d'un coeur. Le processus redevient CAPABLE de s'exécuter, ce qui est exactement la définition de l'état prêt ; mais un autre processus occupe peut-être le coeur, et c'est à l'ordonnanceur, et à lui seul, de décider qui l'obtient. Autoriser un passage direct de bloqué à élu reviendrait à laisser un périphérique décider de l'attribution du processeur, donc à permettre à n'importe quel matériel de préempter le système. La séparation entre « je peux avancer » et « on me laisse avancer » est le coeur du modèle.

c) Au plus 4 processus peuvent être élus simultanément, un par coeur. Les autres sont soit prêts, soit bloqués : si 30 attendent des entrées-sorties, il y en a $180 - 4 - 30 = 146$ dans l'état prêt. L'utilisateur a l'impression que tous avancent grâce au PARTAGE DE TEMPS : l'ordonnanceur préempte chaque processus au bout de quelques millisecondes et donne la main au suivant. Comme la perception humaine ne distingue pas deux événements séparés de moins d'une trentaine de millisecondes, un processus qui reçoit le processeur vingt fois par seconde paraît continu, alors qu'il est en réalité arrêté 95 pour cent du temps.

d) Un processus possède son propre espace mémoire, isolé de celui des autres. Un fil d'exécution est un flot d'instructions à l'intérieur d'un processus. Deux fils du même processus PARTAGENT l'espace mémoire, donc les variables globales, le tas et les fichiers ouverts ; ils ne partagent PAS leur pile d'appels ni leurs registres, chacun ayant les siens. C'est ce partage de la mémoire qui rend la communication entre fils immédiate et qui rend indispensable la protection des sections critiques : deux processus ne peuvent pas s'écraser mutuellement une variable, deux fils le peuvent à chaque instant.

e) Sur un cycle de $5 + 40 = 45$ millisecondes, il passe $5 / 45 \approx 11{,}1$ pour cent de son temps élu et $40 / 45 \approx 88{,}9$ pour cent bloqué, la part passée à l'état prêt étant négligeable si la machine n'est pas chargée. C'est un processus dit lié aux entrées-sorties. L'ordonnanceur devrait le PRIVILÉGIER, c'est-à-dire lui donner le processeur en priorité dès son réveil : il ne le gardera que 5 millisecondes, puis se rebloquera en libérant le coeur pour les autres. Le faire attendre serait doublement coûteux, puisqu'on retarderait sa prochaine lecture disque, laissant le périphérique inoccupé, alors que le lancer coûte presque rien. C'est le principe des ordonnanceurs à priorité dynamique, qui augmentent la priorité d'un processus à chacun de ses blocages.

a) Le diagramme donne, dans l'ordre : A de 0 à 2, B de 2 à 4, C de 4 à 6, A de 6 à 8, B de 8 à 9, C de 9 à 11, A de 11 à 12. Le processus B s'achève à l'instant 9, C à l'instant 11 et A à l'instant 12. Cohérence : la somme des durées de calcul vaut $5 + 3 + 4 = 12$, et le processeur n'est jamais inoccupé, donc le dernier processus doit bien s'achever à l'instant 12.

b) Temps de séjour : A vaut $12 - 0 = 12$, B vaut 9, C vaut 11 ; moyenne $(12 + 9 + 11) / 3 = 32 / 3 \approx 10{,}67$. Temps d'attente : A vaut $12 - 5 = 7$, B vaut $9 - 3 = 6$, C vaut $11 - 4 = 7$ ; moyenne $(7 + 6 + 7) / 3 = 20 / 3 \approx 6{,}67$. On vérifie la relation : la moyenne des attentes vaut bien la moyenne des séjours moins la moyenne des temps de calcul, soit $10{,}67 - 4 = 6{,}67$.

c) En premier arrivé premier servi, A s'exécute de 0 à 5, B de 5 à 8, C de 8 à 12. Temps de séjour : 5, 8 et 12, de moyenne $25 / 3 \approx 8{,}33$. Temps d'attente : $5 - 5 = 0$, $8 - 3 = 5$, $12 - 4 = 8$, de moyenne $13 / 3 \approx 4{,}33$. Cette politique est meilleure que le tourniquet sur ces données, parce qu'elle ne fragmente aucune exécution.

d) Par temps de calcul croissant, l'ordre est B, C, A : B de 0 à 3, C de 3 à 7, A de 7 à 12. Temps de séjour : 3, 7 et 12, de moyenne $22 / 3 \approx 7{,}33$. Temps d'attente : 0, 3 et 7, de moyenne $10 / 3 \approx 3{,}33$. Comparaison des trois politiques sur le temps d'attente moyen : tourniquet $6{,}67$, premier arrivé $4{,}33$, plus court d'abord $3{,}33$. Le plus court d'abord gagne, et l'on démontre qu'il minimise effectivement le temps d'attente moyen quand toutes les tâches sont présentes au départ.

e) Deux raisons. La première est qu'il exige de CONNAÎTRE À L'AVANCE la durée de calcul de chaque processus, information dont le système ne dispose jamais : un programme ne sait pas lui-même combien de temps il va tourner. La seconde est la FAMINE : un long processus peut être indéfiniment repoussé par l'arrivée continue de processus courts, et ne jamais s'achever. Le tourniquet, lui, garantit qu'aucun processus n'attend plus que le nombre de concurrents multiplié par le quantum, ce qui est exactement ce qu'on veut d'un système interactif. On accepte donc une moyenne moins bonne en échange d'une garantie sur le PIRE cas, arbitrage qui revient constamment en informatique.

a) On attend $2 \times 1\ 000\ 000 = 2\ 000\ 000$. La valeur obtenue est presque toujours inférieure parce que l'incrémentation n'est pas une opération INDIVISIBLE : elle se décompose en plusieurs opérations machine, et l'ordonnanceur peut préempter un fil entre deux d'entre elles. Les deux fils peuvent alors lire la même valeur, l'incrémenter chacun de son côté et écrire le même résultat : deux incrémentations ont eu lieu, une seule est visible.

b) Les trois opérations sont : LIRE la valeur de compteur en mémoire vers un registre ; AJOUTER 1 dans le registre ; ÉCRIRE le registre en mémoire. Entrelacement fautif, en partant de compteur valant 100 : le fil 1 lit 100 ; le fil 2 lit 100 ; le fil 1 calcule 101 ; le fil 2 calcule 101 ; le fil 1 écrit 101 ; le fil 2 écrit 101. Deux incrémentations ont été demandées, compteur vaut 101 au lieu de 102 : une est perdue. C'est exactement la mise à jour perdue du chapitre des bases de données, au niveau d'une variable au lieu d'une ligne.

c) Une section critique est une portion de code qui accède à une ressource partagée et qui ne doit être exécutée que par un seul fil à la fois. Les trois propriétés à garantir sont : l'EXCLUSION MUTUELLE, deux fils ne peuvent jamais être simultanément dans la section critique ; l'ABSENCE D'INTERBLOCAGE, si des fils veulent entrer, l'un d'eux finit par entrer ; et l'ABSENCE DE FAMINE, tout fil qui demande à entrer finit par entrer en un temps fini. Les deux dernières sont distinctes et souvent confondues : un système peut progresser globalement tout en laissant un fil précis attendre indéfiniment.

d) On crée un verrou avant les fils, par exemple verrou = Lock(). Dans la fonction, la boucle devient : pour chaque tour, prendre le verrou, exécuter compteur = compteur + 1, relâcher le verrou. En Python on écrit cela avec un bloc with verrou autour de la seule ligne d'incrémentation. Le verrou doit être pris juste AVANT la première des trois opérations machine et relâché juste APRÈS la troisième : c'est ce qui rend l'ensemble indivisible du point de vue des autres fils. Le prendre plus tôt ne nuit pas à la correction mais réduit le parallélisme ; le relâcher plus tôt détruit la garantie.

e) Le résultat est correct : le compte final vaut bien 2 000 000, puisque chaque fil exécute son million d'incrémentations sans interruption. Mais l'intérêt des deux fils disparaît complètement : le second attend que le premier ait terminé l'intégralité de sa boucle avant de commencer, si bien que l'exécution est strictement séquentielle et même un peu plus lente que le programme à un seul fil, à cause du coût de gestion des fils et du verrou. C'est l'arbitrage central de la programmation concurrente : plus la section critique est LARGE, plus le programme est simple à prouver correct et moins il est parallèle. On cherche donc la section critique la plus étroite qui reste correcte, et non la plus commode à écrire.

a) La flèche de R1 vers P1 dit que la ressource R1 est attribuée au processus P1. La flèche de P1 vers R2 dit que P1 attend la ressource R2. La flèche de R2 vers P2 dit que R2 est attribuée à P2. La flèche de P2 vers R1 dit que P2 attend R1. Aucun ne peut avancer parce que chacun attend une ressource que l'autre détient et ne libérera qu'après avoir obtenu celle que le premier détient : l'attente est CIRCULAIRE, donc éternelle.

b) Les quatre conditions. EXCLUSION MUTUELLE : une ressource ne peut être détenue que par un processus à la fois ; vérifiée ici, R1 et R2 ont chacune un seul détenteur. DÉTENTION ET ATTENTE : un processus qui détient une ressource peut en demander une autre sans libérer la première ; vérifiée, P1 garde R1 tout en demandant R2. ABSENCE DE PRÉEMPTION : on ne peut pas retirer de force une ressource à son détenteur ; vérifiée, personne n'arrache R1 à P1. ATTENTE CIRCULAIRE : il existe un cycle dans le graphe ; vérifiée, P1 vers R2 vers P2 vers R1 vers P1. Les quatre étant réunies, l'interblocage est effectif. Elles sont NÉCESSAIRES, ce qui signifie qu'en briser une seule suffit à rendre l'interblocage impossible.

c) On détecte un interblocage en cherchant un CYCLE dans le graphe d'attente. Un parcours en profondeur suffit : on lance le parcours depuis chaque sommet non visité, et l'on conclut au cycle dès qu'une arête ramène sur un sommet présent dans la pile de récursion courante. Le coût est linéaire en la taille du graphe, soit de l'ordre de $p + r$ sommets et d'au plus $p \times r$ arêtes, donc $O(p \times r)$ dans le pire cas. C'est peu, ce qui permet de lancer la détection périodiquement plutôt qu'à chaque demande.

d) PRÉVENTION : imposer que toutes les ressources soient demandées en une seule fois au début, ce qui brise la condition de détention et attente. Coût faible à l'exécution, mais inconvénient sérieux, car un processus doit réserver au départ tout ce dont il pourrait avoir besoin, donc il monopolise des ressources qu'il n'utilisera peut-être jamais. ÉVITEMENT : n'accorder une ressource que si l'état résultant reste sûr, c'est-à-dire s'il existe un ordre d'exécution qui permet à tous de terminer. Coût important, puisqu'il faut simuler cet ordre à chaque demande, et inconvénient majeur, car il faut connaître à l'avance le besoin maximal de chaque processus. GUÉRISON : détecter les cycles périodiquement et annuler une transaction ou tuer un processus victime. Coût très faible en régime normal, inconvénient évident, le travail de la victime est perdu et doit être rejoué.

e) Supposons que chaque processus demande ses ressources dans l'ordre croissant des indices. Un cycle d'attente exigerait une suite de processus $P_{1}, P_{2}, \dots, P_{k}$ revenant sur $P_{1}$, où chaque $P_{i}$ détient une ressource d'indice $a_{i}$ et en attend une d'indice $b_{i}$ strictement supérieur. En parcourant le cycle, les indices ne feraient donc que croître, et l'on reviendrait au point de départ avec un indice strictement plus grand que lui-même, ce qui est impossible. La condition d'attente circulaire est donc brisée. Cette règle est difficile à faire respecter dans un vrai programme parce qu'elle est GLOBALE : elle porte sur l'ordre des prises de verrous à travers tout le code, y compris dans des bibliothèques dont on ne lit pas les sources, et une seule fonction qui prend deux verrous dans le mauvais ordre suffit à rouvrir la porte. Elle ne se vérifie pas localement, ce qui est exactement ce qui rend les défauts de concurrence si coûteux à trouver.

a) Depuis A. Vers D : le lien direct coûte 1, c'est le plus court, chemin A-D. Vers B : le lien direct coûte 2, chemin A-B. Vers C : par B le coût vaut $2 + 3 = 5$, par D et E il vaut $1 + 4 + 2 = 7$ ; le plus court est donc 5, chemin A-B-C. Vers E : par D il vaut $1 + 4 = 5$, par B directement $2 + 5 = 7$, par B et C $2 + 3 + 2 = 7$ ; le plus court est 5, chemin A-D-E. Les distances sont donc B 2, C 5, D 1, E 5.

b) Table de routage de A. Vers B : prochaine étape B, coût 2. Vers C : prochaine étape B, coût 5. Vers D : prochaine étape D, coût 1. Vers E : prochaine étape D, coût 5. Le point essentiel est qu'une table ne contient JAMAIS le chemin complet, seulement la PROCHAINE étape : chaque routeur ne décide que du saut suivant, et c'est la cohérence de toutes les tables qui fait émerger le chemin complet.

c) En nombre de sauts : D à 1 saut, B à 1 saut, C à 2 sauts par A-B-C, E à 2 sauts par A-D-E ou par A-B-E. La destination E change de chemin possible : A-B-E coûte 2 sauts alors qu'il coûtait 7 en métrique pondérée, et le protocole pourrait donc l'emprunter, ce qui serait un choix médiocre puisque ce lien est le plus lent du réseau. Le protocole qui raisonne en nombre de sauts est RIP, un protocole à VECTEUR DE DISTANCE : chaque routeur annonce à ses voisins la distance qu'il connaît vers chaque destination, sans jamais leur décrire la topologie.

d) Sans le lien A-D. En métrique pondérée : vers B toujours 2 par B ; vers C toujours 5 par B ; vers E, il reste A-B-E à 7 et A-B-C-E à $2 + 3 + 2 = 7$, donc 7 par B ; vers D, il faut passer par B, C puis E, soit $2 + 3 + 2 + 4 = 11$, ou par B et E, soit $2 + 5 + 4 = 11$, donc 11 par B. En nombre de sauts : B à 1, C à 2, E à 2, D à 3 par A-B-E-D. La métrique pondérée est la plus affectée : le coût vers D passe de 1 à 11, soit un facteur 11, alors qu'en nombre de sauts il passe seulement de 1 à 3. Cela illustre bien que les deux métriques ne mesurent pas la même chose, et que le nombre de sauts sous-estime gravement le coût réel d'un détour par des liens lents.

e) Il applique sa ROUTE PAR DÉFAUT, c'est-à-dire l'entrée qui dit « pour tout le reste, envoyer par là ». S'il n'en a pas, il jette le paquet et renvoie à l'émetteur un message d'erreur de réseau inaccessible. La route par défaut permet à un routeur de ne connaître que son voisinage et de déléguer tout le reste à un routeur mieux informé. Une machine domestique n'a donc besoin que de trois lignes : son propre réseau local, la boucle locale, et la route par défaut vers la passerelle. Un routeur de coeur, lui, n'a personne à qui déléguer : il doit connaître effectivement toutes les destinations d'Internet, soit près d'un million de préfixes, et c'est pour cela qu'il coûte cent mille fois plus cher.

a) Dans un protocole à VECTEUR DE DISTANCE, chaque routeur annonce à ses SEULS VOISINS immédiats sa table de distances, c'est-à-dire, pour chaque destination connue, le coût auquel il sait l'atteindre. Il le fait périodiquement, typiquement toutes les trente secondes, et à chaque changement. Il ne dit jamais par où il passe, ni ce que le réseau contient. Dans un protocole à ÉTAT DE LIENS, chaque routeur annonce à TOUS les routeurs du domaine, par inondation, la seule chose qu'il connaisse de première main : la liste de ses liens directs et leur coût. Il le fait à chaque changement, et de façon périodique très espacée pour rafraîchir. Chacun reconstitue alors la carte complète du réseau.

b) Il emploie l'algorithme de DIJKSTRA, qui calcule les plus courts chemins depuis un sommet source dans un graphe à poids positifs. Il a besoin pour cela de la TOPOLOGIE COMPLÈTE, c'est-à-dire de la liste de tous les routeurs et de tous les liens avec leurs coûts, ce que l'inondation des états de liens lui a précisément fourni. C'est le même algorithme que celui d'un calculateur d'itinéraire routier, et la garantie qui le fonde est la même : traiter les sommets par distance croissante rend chaque distance définitive au moment où on la sort de la file.

c) Prenons trois routeurs en ligne, X, Y et Z, où seul X est relié au réseau de destination, à distance 1 de Y et 2 de Z. Le lien de X vers la destination tombe. X passe sa distance à l'infini, mais avant qu'il n'ait annoncé quoi que ce soit, Y lui annonce qu'il sait l'atteindre à distance 2. X en conclut qu'il peut passer par Y, à distance 3. Il l'annonce, Y se corrige à 4, Z à 5, et ainsi de suite : la distance monte de un à chaque échange, indéfiniment, alors que la destination est simplement injoignable. Le défaut vient de ce que Y ne sait pas que sa route de distance 2 passait justement par X : un vecteur de distance ne transporte pas le chemin. RIP l'arrête en décrétant que 16 vaut l'INFINI, ce qui limite le comptage à quelques échanges mais interdit du même coup tout réseau de plus de 15 sauts de diamètre.

d) Sur le réseau de l'exercice 5, un routeur à vecteur de distance annonce une entrée par destination, soit 4 entrées, à ses voisins ; A en a 2, donc il envoie 8 entrées par période. Un routeur à état de liens annonce ses liens directs, soit 2 pour A, mais à TOUS les routeurs, donc $2 \times 4 = 8$ entrées également. Les deux se valent à cette échelle. Sur 500 routeurs et 1 200 liens, un routeur à vecteur de distance annonce 499 entrées à chacun de ses voisins, soit environ $499 \times 4{,}8 \approx 2\ 395$ entrées par période, en prenant un degré moyen de $2 \times 1\ 200 / 500 = 4{,}8$. Un routeur à état de liens annonce ses $4{,}8$ liens à 499 routeurs, soit $2\ 395$ entrées, mais SEULEMENT quand quelque chose change, alors que le vecteur de distance recommence toutes les trente secondes. En régime stable, l'état de liens ne consomme presque rien, et c'est ce qui décide.

e) Argument TECHNIQUE : à l'intérieur d'un réseau, on veut une convergence rapide et des chemins optimaux selon une métrique fine, débit ou latence ; l'état de liens le donne, et le comptage à l'infini y est impossible puisque chacun voit la carte entière. Argument POLITIQUE : entre opérateurs, personne ne veut publier la topologie interne de son réseau, ni se voir imposer un chemin par le calcul d'un concurrent. Un protocole à vecteur de chemin annonce des CHEMINS, listes d'opérateurs traversés, ce qui permet à chacun d'appliquer ses propres règles commerciales, de refuser de transiter pour untel, de préférer un client à un pair, et de détecter les boucles en voyant son propre nom dans le chemin annoncé. Le routage entre opérateurs n'est donc pas un problème de plus court chemin, c'est un problème de contrat.

a) Le chiffrement SYMÉTRIQUE utilise la même clé pour chiffrer et déchiffrer ; les deux correspondants doivent donc la partager à l'avance. Le chiffrement ASYMÉTRIQUE utilise une paire de clés, l'une publique et l'autre privée : ce qui est chiffré avec l'une ne se déchiffre qu'avec l'autre. En symétrique, chaque paire de personnes a besoin de sa propre clé, soit $n(n-1)/2$ clés ; pour $n = 1\ 000$, cela fait $1\ 000 \times 999 / 2 = 499\ 500$ clés, chacune à transmettre de façon sûre. En asymétrique, chacun possède une paire, soit $2n = 2\ 000$ clés, dont seules les 1 000 privées sont secrètes et n'ont jamais à circuler. C'est ce rapport, de 499 500 contre 1 000, qui explique que le problème de la distribution des clés ait attendu l'asymétrique pour être résolu.

b) Une clé de 128 bits offre $2^{128} \approx 3{,}40 \times 10^{38}$ possibilités. En moyenne, une recherche exhaustive en essaie la moitié, soit $1{,}70 \times 10^{38}$. À $10^{12}$ essais par seconde, cela demande $1{,}70 \times 10^{26}$ secondes, soit $1{,}70 \times 10^{26} / (3{,}156 \times 10^{7}) \approx 5{,}4 \times 10^{18}$ années, c'est-à-dire environ cinq milliards de milliards d'années, soit près de quatre cents millions de fois l'âge de l'univers. Conclusion : une clé symétrique de 128 bits n'est pas attaquable par force brute, et elle ne le sera pas. Toute compromission réelle vient donc d'ailleurs, mot de passe faible, clé volée, défaut d'implémentation, jamais de la recherche exhaustive.

c) Ils emploient un chiffrement HYBRIDE. L'échange se déroule ainsi : le client obtient la clé publique du serveur ; il tire au hasard une clé symétrique de session ; il chiffre cette clé de session avec la clé publique du serveur et la lui envoie ; le serveur la déchiffre avec sa clé privée ; à partir de là, toute la conversation est chiffrée symétriquement avec cette clé de session, rapide. L'asymétrique n'a donc servi qu'à transporter quelques dizaines d'octets, une seule fois. On obtient à la fois la commodité de l'asymétrique, aucun secret partagé au préalable, et la vitesse du symétrique.

d) Pour que seul Bob puisse lire, Alice chiffre avec la clé PUBLIQUE DE BOB : seule la clé privée de Bob permet de déchiffrer, et lui seul la possède. Pour prouver que le message vient d'elle, Alice chiffre avec sa PROPRE CLÉ PRIVÉE : n'importe qui peut déchiffrer avec la clé publique d'Alice, ce qui ne protège rien, mais le seul fait que le déchiffrement produise un texte cohérent prouve que l'auteur détenait la clé privée d'Alice. Ce ne sont pas les mêmes clés parce que les deux objectifs sont opposés : la confidentialité restreint la LECTURE au seul détenteur d'un secret, l'authentification restreint l'ÉCRITURE au seul détenteur d'un secret. Confondre les deux est l'erreur la plus fréquente sur ce chapitre.

e) Trois propriétés. Elle doit être DÉTERMINISTE et rapide : le même message donne toujours la même empreinte. Elle doit être à SENS UNIQUE : il doit être impraticable de retrouver un message à partir de son empreinte. Elle doit résister aux COLLISIONS : il doit être impraticable de trouver deux messages différents ayant la même empreinte, et modifier un seul bit du message doit changer l'empreinte de façon imprévisible. Dans une signature, l'empreinte sert à ne chiffrer que 256 bits au lieu du message entier : Alice calcule l'empreinte du message et chiffre cette empreinte avec sa clé privée. Le destinataire recalcule l'empreinte du message reçu, déchiffre la signature avec la clé publique d'Alice, et compare. La signature est donc rapide quelle que soit la taille du message, et elle garantit à la fois l'origine et l'INTÉGRITÉ, puisque toute modification du message changerait l'empreinte.

1) FAUX. La fin de l'attente rend le processus CAPABLE de s'exécuter, ce qui le place dans l'état prêt ; l'attribution d'un coeur est une décision de l'ordonnanceur, prise séparément. Énoncé correct : un processus réveillé passe de bloqué à prêt, puis à élu si et seulement si l'ordonnanceur l'élit.

2) FAUX, pour deux raisons. Il exige de connaître à l'avance la durée de calcul de chaque processus, information dont le système ne dispose jamais. Et il provoque la famine des longs processus si des courts arrivent continuellement. Énoncé correct : les systèmes généralistes emploient un tourniquet avec priorités dynamiques, qui garantit une borne sur le PIRE cas plutôt qu'une meilleure moyenne.

3) FAUX. L'incrémentation est une seule instruction du langage mais trois opérations machine, lire, ajouter, écrire, entre lesquelles l'ordonnanceur peut préempter. Deux fils peuvent alors lire la même valeur et écrire le même résultat, perdant une incrémentation. Énoncé correct : toute lecture-modification-écriture d'une variable partagée est une section critique et doit être protégée par un verrou.

4) FAUX. Une table de routage associe à chaque destination la PROCHAINE ÉTAPE et un coût, jamais l'itinéraire complet. Chaque routeur ne décide que du saut suivant. Énoncé correct : le chemin complet n'existe nulle part ; il émerge de la cohérence des tables de tous les routeurs traversés, ce qui est précisément ce qui rend le réseau capable de se reconfigurer après une panne.

5) FAUX, c'est même le contraire. La clé publique correspondante étant connue de tous, n'importe qui peut déchiffrer : le message n'est absolument pas confidentiel. Ce que l'opération prouve, c'est l'ORIGINE, puisque seul le détenteur de la clé privée pouvait la produire. Énoncé correct : on chiffre avec la clé PUBLIQUE DU DESTINATAIRE pour la confidentialité, et avec SA PROPRE CLÉ PRIVÉE pour la signature.

a) L'intercepteur se place entre Alice et Bob. Quand Alice demande la clé publique de Bob, il lui renvoie la SIENNE ; quand Bob demande celle d'Alice, il lui renvoie également la sienne. Alice chiffre alors pour l'intercepteur en croyant chiffrer pour Bob ; celui-ci déchiffre, lit, éventuellement modifie, rechiffre avec la vraie clé de Bob et transmet. Le chiffrement ne protège rien parce qu'il fonctionne parfaitement : chaque message est bien illisible pour un tiers passif. Le problème n'est pas la confidentialité mais l'AUTHENTIFICATION de la clé : le chiffrement garantit que seul le détenteur de la clé privée lit le message, il ne dit rien sur l'identité de ce détenteur.

b) Un certificat est une déclaration signée qui associe une clé publique à une identité. Il contient au minimum : le nom du domaine ou de l'organisation concernée ; la clé publique correspondante ; les dates de début et de fin de validité ; l'identité de l'autorité qui l'a émis ; les usages autorisés ; et la SIGNATURE de cette autorité, calculée sur tout le reste. Il est signé par une autorité de certification, c'est-à-dire un tiers dont la clé publique est déjà connue de celui qui vérifie.

c) Le navigateur reçoit le certificat du site, signé par une autorité intermédiaire. Il vérifie cette signature avec la clé publique de l'intermédiaire, qu'il trouve dans le certificat de celui-ci, lui-même signé par une autorité racine. Il vérifie alors cette seconde signature avec la clé publique de la racine. La chaîne s'arrête là, parce que le certificat racine est AUTO-SIGNÉ et qu'il est présent dans le magasin de confiance installé avec le système ou le navigateur. Elle doit s'arrêter quelque part, faute de quoi la vérification serait infinie : à un moment, il faut faire confiance à une clé pour une raison qui n'est pas cryptographique, ici parce qu'elle a été livrée avec le système. Toute la sécurité repose donc, en dernier ressort, sur l'intégrité de ce magasin.

d) « Certificat expiré » signifie que la date du jour dépasse la fin de validité inscrite dans le certificat. C'est le plus souvent une négligence administrative : personne n'a renouvelé. Le risque réel est modéré, mais il est réel, car un certificat expiré ne peut plus être révoqué utilement et l'on ne sait plus si la clé a été compromise depuis. « Certificat non valide pour ce domaine » signifie que le nom inscrit dans le certificat ne correspond pas au site visité. C'est BEAUCOUP plus inquiétant : c'est exactement la signature de l'attaque de la question a, quelqu'un présentant un certificat authentique mais qui n'est pas celui du site demandé. Le premier message signale un défaut d'entretien, le second une usurpation possible.

e) Ce que le cadenas GARANTIT : que la communication est chiffrée entre le navigateur et le serveur, donc illisible pour un observateur du réseau ; que les données n'ont pas été modifiées en transit, grâce aux empreintes ; et que le serveur possède bien la clé privée correspondant à un certificat valide pour ce nom de domaine. Ce qu'il NE GARANTIT PAS : que le site est honnête, un site frauduleux pouvant parfaitement obtenir un certificat gratuit pour son propre domaine ; que le nom de domaine est celui qu'on croit, une adresse imitant une marque à un caractère près étant parfaitement chiffrable ; et que les données sont en sécurité UNE FOIS ARRIVÉES, le chiffrement protégeant le transport et non le stockage. Le cadenas dit « vous parlez bien à ce domaine, sans écoute possible » ; il ne dit rien de ce que ce domaine mérite.

a) Le bloc 10.1.0.0/16 offre $2^{16} = 65\ 536$ adresses, largement de quoi tailler des /24 de 254 machines chacun. Proposition : salle 1 en 10.1.1.0/24, salle 2 en 10.1.2.0/24, salle 3 en 10.1.3.0/24, salle 4 en 10.1.4.0/24, administration en 10.1.10.0/24, sans-fil des élèves en 10.1.20.0/24. Chaque salle n'ayant que 30 postes, un /24 est surdimensionné, mais la lisibilité vaut mieux que l'économie : personne ne manque d'adresses privées, et un plan d'adressage que l'on retient de tête évite bien plus d'incidents qu'il n'en coûte. On réserve les blocs 10.1.5.0/24 à 10.1.9.0/24 pour de futures salles.

b) Première raison, la CONFIDENTIALITÉ : les postes d'administration manipulent des données personnelles d'élèves, notes, absences, dossiers ; un appareil personnel compromis sur le sans-fil ne doit pas pouvoir seulement les atteindre. Seconde raison, la MAÎTRISE : le sans-fil accueille des appareils non administrés, dont on ne connaît ni l'état ni les logiciels, et dont on doit supposer qu'au moins un est infecté à tout instant. Techniquement, la séparation est appliquée par des réseaux locaux virtuels, qui isolent le trafic au niveau des commutateurs, complétés par des règles de filtrage sur le routeur qui interdisent le trafic du sous-réseau sans-fil vers celui de l'administration. Le filtrage est indispensable : sans lui, les deux sous-réseaux resteraient joignables l'un depuis l'autre par le routeur.

c) Trente postes téléchargent chacun 4 Gio, soit $30 \times 4 = 120$ Gio au total, c'est-à-dire $120 \times 1\ 073\ 741\ 824 \approx 1{,}2885 \times 10^{11}$ octets, donc $1{,}0308 \times 10^{12}$ bits. À 1 Gbit/s, cela demande $1\ 030{,}8$ secondes, soit environ 17 minutes et 11 secondes, pendant lesquelles le lien du serveur est saturé et plus rien d'autre ne passe. Propositions : distribuer l'image en DIFFUSION, une seule copie envoyée simultanément à tous les postes, ce qui ramène la durée à celle d'un seul poste, soit 34 secondes ; ou bien pré-installer l'image et ne transmettre que les différences ; ou encore programmer l'opération la nuit. La diffusion est de loin la meilleure, parce qu'elle attaque la cause, à savoir l'envoi trente fois du même contenu.

d) La demande vaut $600 \times 300 = 180\ 000$ kbit/s, soit 180 Mbit/s, contre 500 Mbit/s disponibles. La liaison suffit donc en moyenne, avec un taux d'occupation de $180 / 500 = 36$ pour cent. Mais la moyenne n'est pas la bonne grandeur : si un dixième des appareils lance une vidéo à 5 Mbit/s, cela ajoute $60 \times 5 = 300$ Mbit/s, portant le total à 480 Mbit/s, soit 96 pour cent, et la liaison sature. Sans action, la saturation ne se traduit pas par un refus mais par une DÉGRADATION générale : les temps de réponse s'allongent pour tout le monde, y compris pour l'administration. Deux mesures : mettre en place une QUALITÉ DE SERVICE qui réserve une part garantie du débit aux usages pédagogiques et administratifs et relègue le reste ; et poser un CACHE local pour les contenus les plus demandés, mises à jour de systèmes en tête, ce qui supprime le trafic externe correspondant.

e) La politique minimale. Un, RÉSEAU : segmenter en réseaux virtuels séparés, interdire par filtrage tout trafic du sans-fil élèves vers l'administration et le serveur de fichiers, et n'ouvrir depuis Internet que les services réellement nécessaires. Deux, COMPTES : un compte nominatif par personne, jamais de compte partagé, mot de passe long plutôt que compliqué, deuxième facteur pour les comptes d'administration, et retrait immédiat des accès au départ d'un agent. Trois, DROITS : appliquer le moindre privilège, un enseignant ne devant pas pouvoir lire les dossiers d'une autre classe ni un élève écrire ailleurs que dans son espace. Quatre, SAUVEGARDE : trois copies, sur deux supports, dont une hors site et hors ligne, avec un test de RESTAURATION effectué au moins une fois par trimestre, car une sauvegarde jamais restaurée n'est pas une sauvegarde. Cinq, MISES À JOUR : appliquer les correctifs de sécurité sur les serveurs et les postes selon un calendrier écrit, ce qui ferme la très grande majorité des voies d'entrée réellement utilisées.

a) Un système sur puce intègre typiquement : les coeurs du PROCESSEUR, le processeur GRAPHIQUE, la MÉMOIRE vive, un processeur de signal pour l'image ou le son, le MODEM de communication, et les contrôleurs d'entrées-sorties, stockage, capteurs, écran. Deux avantages : la consommation d'énergie baisse fortement, parce que les signaux ne quittent plus la puce et que chaque bloc peut être éteint séparément ; et l'encombrement et le coût de fabrication diminuent, un seul composant remplaçant une carte entière.

b) De 1971 à 2021, il s'écoule 50 ans, soit 25 doublements. La loi prévoit $2\ 300 \times 2^{25} = 2\ 300 \times 33\ 554\ 432 \approx 7{,}7 \times 10^{10}$ transistors, soit environ 77 milliards. Les plus grosses puces grand public de cette époque comptent effectivement plusieurs dizaines de milliards de transistors : la prévision a tenu l'ordre de grandeur pendant un demi-siècle, ce qui est exceptionnel pour une loi empirique.

c) Consommation totale du téléphone : $1{,}5 + 1 = 2{,}5$ W, d'où une autonomie de $\frac{15}{2{,}5} = 6$ heures. Pour le poste de bureau : $65 + 200 = 265$ W, d'où $\frac{15}{265} \approx 0{,}057$ heure, soit environ $3{,}4$ minutes. Le rapport de puissance, un facteur 100 environ, est la raison d'être du système sur puce : la contrainte d'un appareil mobile n'est pas la puissance de calcul, c'est l'énergie par calcul.

d) Sur la carte mère : $\frac{0{,}05}{2 \times 10^{8}} = 2{,}5 \times 10^{-10}$ s, soit $0{,}25$ ns. Dans la puce : $\frac{0{,}005}{2 \times 10^{8}} = 2{,}5 \times 10^{-11}$ s, soit $0{,}025$ ns. La période d'une horloge de 3 GHz vaut $\frac{1}{3 \times 10^{9}} \approx 0{,}333$ ns : le trajet sur la carte mère consomme à lui seul 75 pour cent d'un cycle d'horloge, contre $7{,}5$ pour cent dans la puce. À ces fréquences, la distance devient une limite physique, et rapprocher les composants est la seule façon de la repousser.

e) La mémoire et le stockage étant gravés ou soudés avec le processeur, on ne peut plus les AGRANDIR après l'achat : il faut choisir la configuration une fois pour toutes. Et une panne d'un seul bloc rend toute la puce inutilisable, ce qui rend la RÉPARATION impossible autrement que par remplacement de la carte entière. On peut ajouter la chaleur concentrée sur une petite surface, qui limite la puissance soutenue.

a) La racine est systemd, de PID 1, créé par le noyau au démarrage. Il a pour enfants sshd et firefox. sshd a pour enfant bash, qui a deux enfants, python3 et less. firefox a deux enfants, ses deux onglets. La hauteur vaut 3, atteinte par le chemin systemd, sshd, bash, python3. Chaque processus, sauf le premier, a été créé par un autre : c'est pourquoi les processus forment un ARBRE, dont on retrouve la structure dans la paire PID, PPID.

b) R regroupe les états ÉLU et PRÊT : le processus peut avancer, qu'il ait déjà un coeur ou qu'il en attende un. S correspond à l'état BLOQUÉ : le processus attend un événement, frappe au clavier, paquet réseau, fin d'une lecture. Un seul processus est dans l'état R parce que les autres n'ont rien à calculer à cet instant : un shell attend une commande, un lecteur de fichier attend une touche, un navigateur attend un clic. Avoir quatre coeurs ne crée pas de travail ; la plupart des processus d'une machine passent l'essentiel de leur vie endormis.

c) kill envoie un signal de terminaison au processus 1450, et bash se termine. Ses enfants, s'ils ne sont pas terminés avec lui, deviennent ORPHELINS : sur la plupart des systèmes, ils sont alors rattachés au processus de PID 1, qui devient leur nouveau parent et recueillera leur code de retour. L'arbre se réorganise donc sans jamais se couper en morceaux.

d) $98{,}7 + 0{,}1 + 2{,}3 + 5{,}1 + 0{,}8 = 107{,}0$ pour cent, les autres lignes valant 0. La capacité totale vaut 400 pour cent, quatre coeurs à 100 chacun : la machine est utilisée à $\frac{107}{400} \approx 26{,}8$ pour cent. Un total supérieur à 100 n'est pas une erreur, c'est la signature d'une machine à plusieurs coeurs.

e) Un programme écrit de façon séquentielle ne comporte qu'un seul fil d'exécution : il ne peut occuper qu'un coeur à la fois, quel que soit le nombre de coeurs disponibles. Pour en profiter, il faudrait le découper en tâches indépendantes exécutées par plusieurs fils ou processus, avec les précautions de l'exercice 3. Pour le suspendre, on lui envoie le signal d'arrêt temporaire, par kill -STOP 1502, ou par la combinaison de touches Ctrl et Z dans le terminal qui l'a lancé ; il passe alors dans un état stoppé sans perdre sa mémoire, et kill -CONT 1502 le fait repartir exactement où il en était.

a) Bit à bit : 01101000 $\oplus$ 10110011 = 11011011. En décimal : $128 + 64 + 16 + 8 + 2 + 1 = 219$. On vérifie avec les valeurs de départ, 104 et 179 : le ou exclusif n'est pas une addition, et $104 + 179 = 283$ ne tiendrait même pas dans un octet.

b) Le ou exclusif est associatif, et $k \oplus k = 0$ pour tout $k$, puisque chaque bit est comparé à lui-même. Donc $(m \oplus k) \oplus k = m \oplus (k \oplus k) = m \oplus 0 = m$. Le DÉCHIFFREMENT est donc exactement la même opération que le chiffrement, avec la même clé : c'est ce qui en fait un chiffrement symétrique, et ce qui le rend si simple à réaliser en circuit.

c) $79 \oplus 42 = 101$, $85 \oplus 42 = 127$ et $73 \oplus 42 = 99$ : le message chiffré est [101, 127, 99]. Une clé qui répète le même octet chiffre toujours la même lettre en le même octet : les répétitions du message restent visibles, et une analyse des fréquences, la lettre la plus fréquente d'un texte français étant e, suffit à casser le chiffrement sur un texte assez long. Ce n'est rien d'autre qu'un chiffre de substitution déguisé.

d) Puisque $c_{1} = m_{1} \oplus k$, on a $k = c_{1} \oplus m_{1}$ : $94 \oplus 79 = 17$, $157 \oplus 85 = 200$ et $76 \oplus 73 = 5$, donc la clé vaut [17, 200, 5]. Le second message vaut $c_{2} \oplus k$ : $95 \oplus 17 = 78$, $135 \oplus 200 = 79$, $75 \oplus 5 = 78$, soit N, O, N : le second message est NON. Même sans connaître $m_{1}$, l'espion obtient $c_{1} \oplus c_{2} = m_{1} \oplus m_{2}$ = [1, 26, 7], où la clé a DISPARU : réutiliser une clé livre une relation directe entre les deux messages clairs.

e) Trois conditions, établies par Shannon : la clé est parfaitement ALÉATOIRE ; elle est au moins aussi LONGUE que le message ; elle n'est utilisée qu'UNE SEULE FOIS. Pour un fichier de 1 Gio, il faut une clé de 1 Gio, qu'il faut avoir transmise au destinataire de façon sûre à l'avance : le problème du transport du message est seulement déplacé vers celui de la clé. En pratique, on utilise des chiffrements symétriques à clé courte, 128 ou 256 bits, qui fabriquent à partir de cette clé une suite pseudo-aléatoire, et l'on échange la clé courte par un protocole comme celui de l'exercice suivant.

a) $5^{6} = 15\ 625$ et $15\ 625 = 23 \times 679 + 8$, donc $A = 8$.

b) On réduit au fur et à mesure : $5^{2} = 25 \equiv 2$, donc $5^{4} \equiv 4$, $5^{8} \equiv 16$. Puis $5^{15} = 5^{8} \times 5^{4} \times 5^{2} \times 5 \equiv 16 \times 4 \times 2 \times 5 = 640$, et $640 = 23 \times 27 + 19$. Donc $B = 19$. Réduire à chaque étape évite de manipuler $5^{15}$, qui dépasse trente milliards : c'est le même principe que l'exponentiation rapide.

c) Alice : $19^{6} \bmod 23$. $19 \equiv -4$, donc $19^{2} \equiv 16$, $19^{4} \equiv 256 \equiv 3$, et $19^{6} \equiv 3 \times 16 = 48 \equiv 2$. Bob : $8^{15} \bmod 23$. $8^{2} = 64 \equiv 18$, $8^{4} \equiv 324 \equiv 2$, $8^{8} \equiv 4$, et $8^{15} = 8^{8} \times 8^{4} \times 8^{2} \times 8 \equiv 4 \times 2 \times 18 \times 8 = 1\ 152 \equiv 2$. Les deux trouvent 2. C'est nécessaire : $B^{a} = (g^{b})^{a} = g^{ab}$ et $A^{b} = (g^{a})^{b} = g^{ab}$, et le calcul modulo $p$ respecte les produits. Le secret commun vaut $g^{ab} \bmod p$ ; il n'a jamais circulé.

d) Ève doit retrouver $a$ à partir de $5^{a} \bmod 23 = 8$, c'est le problème du LOGARITHME DISCRET. Ici, les exposants utiles vont de 1 à 22, soit au plus 22 essais : elle trouve $a = 6$ immédiatement. Pour un $p$ de 2 048 bits, il y aurait de l'ordre de $2^{2\ 048}$ exposants, et l'on ne connaît aucun algorithme qui résolve ce problème en un temps raisonnable : même à un milliard de milliards d'essais par seconde, l'essai exhaustif dépasserait de très loin l'âge de l'univers. La sécurité repose sur cette asymétrie : calculer $g^{a} \bmod p$ est rapide, retrouver $a$ ne l'est pas.

e) C'est l'attaque de l'INTERCEPTEUR de l'exercice 9. Ève intercepte $A$ et envoie à Bob sa propre valeur $g^{e} \bmod p$ ; elle intercepte $B$ et envoie à Alice cette même valeur. Alice partage alors un secret avec Ève en croyant le partager avec Bob, et Bob de même : Ève détient DEUX clés, déchiffre chaque message, le lit, et le rechiffre pour l'autre. Le protocole garantit la confidentialité face à une écoute passive, mais rien sur l'identité du correspondant. Ce qui déjoue l'attaque, c'est l'AUTHENTIFICATION des valeurs échangées, par exemple leur signature par une clé certifiée : c'est exactement ce que fait une connexion sécurisée sur le Web.

a) Exemplaires détenus : $5 + 2 + 2 = 9$, donc $12 - 9 = 3$ disponibles. Besoins restants, maximum moins détenu : P1 a besoin de $10 - 5 = 5$, P2 de $4 - 2 = 2$ et P3 de $9 - 2 = 7$.

b) Avec 3 disponibles, seul P2, qui a besoin de 2, peut aller au bout : il obtient ses 2 exemplaires, termine et rend les 4 qu'il détenait, d'où $3 - 2 + 4 = 5$ disponibles. P1, qui a besoin de 5, peut alors terminer et rend ses 10 : $5 - 5 + 10 = 10$ disponibles. P3, qui a besoin de 7, termine à son tour, et l'on retrouve les 12 exemplaires. L'ordre P2, P1, P3 convient : l'état est sûr.

c) Si on l'accorde, P3 détient 3 exemplaires, il en reste 2 disponibles, et les besoins deviennent 5, 2 et 6. P2 peut terminer : $2 - 2 + 4 = 4$ disponibles. Mais P1 a besoin de 5 et P3 de 6, tous deux supérieurs à 4 : aucun ordre ne permet de continuer, l'état obtenu n'est PAS sûr. La demande doit être refusée pour l'instant : P3 attendra, par exemple la fin de P2, et sa demande sera réexaminée.

d) Un état non sûr signifie seulement qu'il EXISTE une suite de demandes, conforme aux maximums déclarés, qui mènerait à un interblocage ; mais les processus n'iront peut-être jamais jusqu'à leur maximum, et tout pourrait bien se passer. L'algorithme refuse d'y entrer parce qu'il ne connaît pas l'avenir : tant que l'état est sûr, il peut GARANTIR que tous les processus termineront, quoi qu'ils demandent ; au-delà, il ne peut plus rien garantir. C'est la famille de l'évitement de l'exercice 4, prudente par construction.

e) D'abord, il exige que chaque processus déclare À L'AVANCE son besoin maximal pour chaque ressource, ce qu'un programme généraliste est incapable de faire. Ensuite, il faut refaire le test de sûreté à chaque demande, en comparant les besoins de tous les processus pour toutes les ressources, ce qui devient coûteux avec des centaines de processus et de ressources, et les refus prudents immobilisent des ressources qui auraient pu servir. Les systèmes généralistes préfèrent donc laisser les interblocages se produire, rarement, et les traiter par détection ou par redémarrage.