Soutenance mémoire
Rôle d’un système d’exploitation
Un ordinateur est constitué de nombreux composants matériels : microprocesseur, mémoire, et divers périphériques. Et au niveau de l’utilisateur, des dizaines de logiciels permettent d’effectuer toutes sortes de calculs et de communications. Le système d’exploitation permet de faire l’interface entre ces deux échelles. Au cours de l’histoire des systèmes informatiques, la manière de les programmer a beaucoup évolué. Au départ, les programmeurs avaient accès au matériel dans son intégralité : toute la mémoire pouvait être accédée, toutes les instructions pouvaient être utilisées. Néanmoins cela était un peu restrictif, puisque cela ne permet qu’à une personne d’interagir avec le système. Dans la seconde moitié des années 1960, sont apparus les premiers systèmes « à temps partagé », permettant à plusieurs utilisateurs de travailler en même temps. Permettre l’exécution de plusieurs programmes en même temps est une idée importante, mais elle n’est pas sans difficultés techniques : en effet les ressources de la machine doivent être aussi partagées entre les utilisateurs et les programmes. Par exemple, plusieurs programmes vont utiliser le processeur les uns à la suite des autres ; et chaque programme aura à sa disposition une partie de la mémoire principale, ou du disque dur. Si plusieurs programmes s’exécutent de manière concurrente sur le même matériel, il faut s’assurer que l’un ne puisse pas écrire dans la mémoire de l’autre, et aussi que les deux n’utilisent pas la carte réseau en même temps. Ce sont des rôles du système d’exploitation. Ainsi, au lieu d’accéder directement au matériel via des instructions de bas niveau, les programmes communiquent avec le noyau, qui centralise donc les appels au matériel, et abstrait certaines opérations. Par exemple, comparons ce qui se passe concrètement lors de la copie de données depuis un cédérom ou une clef USB.
• Dans le cas du cédérom, il faut interroger le bus SATA, interroger le lecteur sur la présence d’un disque dans le lecteur, activer le moteur, calculer le numéro de trame des données sur le disque, demander la lecture, puis déclencher une copie de la mémoire.
• Avec une clef, il faut interroger le bus USB, rechercher le bon numéro de périphérique, le bon numéro de canal dans celui-ci, lui appliquer une commande de lecture au bon numéro de bloc, puis copier la mémoire.
Ces deux opérations, bien qu’elles aient la même intention (copier de la mémoire depuis un périphérique amovible), ne sont pas effectuées en extension de la même manière. C’est pourquoi le système d’exploitation fournit les notions de fichier, lecteur, etc : le programmeur n’a plus qu’à utiliser des commandes de haut niveau (« monter un lecteur », « ouvrir un fichier », « lire dans un fichier ») et, selon le type de lecteur, le système d’exploitation effectuera les actions appropriées. En résumé, un système d’exploitation est l’intermédiaire entre le logiciel et le matériel, et en particulier est responsable de la gestion de la mémoire, des périphériques et des processus. Les détails d’implantation ne sont pas présentés à l’utilisateur ; à la place, il manipule des abstractions, comme la notion de fichier. Pour une explication détaillée du concept de système d’exploitation ainsi que des cas d’étude, on pourra se référer à [Tan07].
Séparation entre espace noyau et espace utilisateur
Puisque le noyau est garant d’une utilisation sûre du matériel, il ne doit pas pouvoir être manipulé directement par l’utilisateur ou les programmes exécutés. Ainsi, il est nécessaire de mettre en place des protections entre les espaces noyau et utilisateur. Au niveau matériel, on utilise la notion de niveaux de privilèges pour déterminer s’il est possible d’exécuter une instruction. D’une part, le processeur contient un niveau de privilège intrinsèque. D’autre part, chaque zone mémoire contenant du code ou des données possède également un niveau de privilège minimum nécessaire. L’exécution d’une instruction est alors possible si et seulement si le niveau de privilège du processeur est supérieur à celui de l’instruction et des opérandes mémoires qui y sont présentes . Par exemple, supposons qu’un programme utilisateur contienne l’instruction « déplacer le contenu du registre EAX vers l’adresse mémoire a », où a fait partie de l’espace mémoire de l’utilisateur. Alors aucune erreur de protection mémoire n’est déclenchée. Ainsi, pour une instruction manipulant des données en mémoire, les accès possibles sont décrits dans le tableau suivant. En cas d’impossibilité, une erreur se produit et l’exécution s’arrête. Par exemple, l’avant-dernière ligne indique que, si un programme tente de lire une variable du noyau, celui-ci sera arrêté par une exception.
En plus de cette vérification, certains types d’instructions sont explicitement réservés au mode le plus privilégié : par exemple les lectures ou écritures sur des ports matériels, ou celles qui permettent de définir les niveaux de privilèges des différentes zones mémoire. Comme les programmes utilisateur ne peuvent pas accéder à ces instructions de bas niveau, ils sont très limités dans ce qu’ils peuvent faire. En utilisant seulement les seules instructions non privilégiées, on peut uniquement réaliser des calculs, sans réaliser d’opérations visibles depuis l’extérieur du programme. Pour utiliser le matériel ou accéder à des abstractions de haut niveau (comme créer un nouveau processus), ils doivent donc passer par l’intermédiaire du noyau. La communication entre le noyau et les programmes utilisateur est constituée du mécanisme des appels système.
Lors d’un appel système, une fonction du noyau est invoquée (en mode noyau) avec des paramètres provenant de l’utilisateur. Il faut donc être particulièrement précautionneux dans le traitement de ces données. Par exemple, considérons un appel système de lecture depuis un disque : on passe au noyau les arguments (d,o,n,a) où d est le nom du disque, o (pour offset) l’adresse sur le disque où commencer la lecture, n le nombre d’octets à lire et a l’adresse en mémoire où commencer à stocker les résultats. Dans le cas d’utilisation prévu, le noyau va copier la mémoire lue dans a. Le processeur est en mode noyau, en train d’exécuter une instruction du noyau manipulant des données utilisateur. D’après le tableau de la page 3, aucune erreur ne se produit. Mais même si ce cas ne produit pas d’erreur à l’exécution, il est tout de même codé de manière incorrecte. En effet, si on passe à l’appel système une adresse a faisant partie de l’espace noyau, que se passe-t-il ? L’exécution est presque identique : au moment de la copie on est en mode noyau, en train d’exécuter une instruction du noyau manipulant des données noyau. Encore une fois il n’y a pas d’erreur à l’exécution. On peut donc écrire n’importe où en mémoire. De même, une fonction d’écriture sur un disque (et lisant en mémoire) permettrait de lire de la mémoire du noyau. À partir de ces primitives, on peut accéder aux autres processus exécutés, ou détourner l’exécution vers du code arbitraire. L’isolation est totalement brisée à cause de ces appels système. La cause de ceci est qu’on a accédé à la mémoire en testant les privilèges du noyau au lieu de tester les privilèges de celui qui a fait la requête (l’utilisateur). Ce problème est connu sous le nom de confused deputy problem [Har88]. Pour implanter un appel système, il est donc nécessaire d’interdire le déréférencement direct des pointeurs dont la valeur peut être contrôlée par l’utilisateur. Dans le cas du passage par adresse d’un argument, il aurait fallu vérifier à l’exécution que celui-ci a bien les mêmes privilèges que l’appelant. Il est facile d’oublier d’ajouter cette vérification, puisque le cas « normal » fonctionne. Avec ce genre d’exemple on voit comment les bugs peuvent arriver si fréquemment et pourquoi il est aussi capital de les détecter avant l’exécution.
Systèmes de types
La plupart des langages de programmation incorporent la notion de type, dont un des buts est d’empêcher de manipuler des données incompatibles entre elles. En mémoire, les seules données qu’un ordinateur manipule sont des nombres. Selon les opérations effectuées, ils seront interprétés comme des entiers, des adresses mémoire ou des caractères. Pourtant il est clair que certaines opérations n’ont pas de sens : par exemple, multiplier un nombre par une adresse ou déréférencer le résultat d’une division sont des comportements qu’on voudrait pouvoir empêcher. En un mot, le but du typage est de classifier les objets et de restreindre les opérations possibles selon la classe d’un objet : en somme, « ne pas ajouter des pommes et des oranges ». Le modèle qui permet cette classification est appelé système de types et est en général constitué d’un ensemble de règles de typage, comme « un entier plus un entier égale un entier ».
Typage dynamique Dans ce cas, chaque valeur manipulée par le programme est décorée d’une étiquette définissant comment interpréter la valeur en question. Les règles de typage sont alors réalisées à l’exécution. Par exemple, l’opérateur « + » vérifie que ses deux opérandes ont une étiquette « entier », et construit alors une valeur obtenue en faisant l’addition des deux valeurs, avec une étiquette « entier ». C’est ce qui se passe par exemple dans le langage Python [☞4].
Typage statique Dans ce cas on fait les vérifications à la compilation. Pour vérifier ceci, on donne à chaque fonction un contrat comme « si deux entiers sont passés, et que la fonction renvoie une valeur, alors cette valeur sera un entier ». Cet ensemble de contrats peut être vérifié statiquement par le compilateur, à l’aide d’un système de types statique. Par exemple, on peut dire que l’opérateur « + » a pour type (INT, INT) → INT. Cela veut dire que, si on lui passe deux entiers (INT, INT), alors la valeur obtenue est également un entier. A contrario, si autre chose qu’un entier est passé à cet opérateur, le programme ne compile pas.
Typage fort ou faible Indépendamment du moment où est faite cette analyse, on peut avoir plus ou moins de garanties sur les programmes sans erreurs de typage. En poussant à l’extrême, les systèmes de types forts garantissent que les valeurs ont toujours le type attendu. Avec du typage statique, cela permet d’éliminer totalement les tests de typage à l’exécution. Mais souvent ce n’est pas le cas, car il peut y avoir des constructions au sein du langage qui permettent de contourner le système de types, comme un opérateur de transtypage. On parle alors de typage faible.
Polymorphisme Parfois, il est trop restrictif de donner un unique type à une fonction. Si on considère une fonction ajoutant un élément à une liste, ou une autre triant un tableau en place, leur type doit-il faire intervenir le type des éléments manipulés ? En première approximation, on peut imaginer fournir une version du code par type de données à manipuler. C’est la solution retenue par le langage C, ou par les premières versions du langage Pascal, ce qui rendait très difficile l’écriture de bibliothèques [Ker81]. On parle alors de monomorphisme. Une autre manière de procéder est d’autoriser plusieurs fonctions à avoir le même nom, mais avec des types d’arguments différents. Par exemple, on peut définir séparément l’addition entre deux entiers, entre deux flottants, ou entre un entier et un flottant. Selon les informations connues à la compilation, la bonne version sera choisie. C’est ainsi que fonctionnent les opérateurs en C++. On parle de polymorphisme ad hoc, ou de surcharge. Une autre technique est de déterminer la fonction appelée non pas par le type de ses arguments, mais par l’objet sur lequel on l’appelle. Cela permet d’associer le comportement aux données. On parle alors de polymorphisme objet. Dans ce cas, celui-ci repose sur le soustypage : si A1 et A2 sont des sous-types de B, on peut utiliser des valeurs de type A1 ou A2 là où une valeur de type B est attendue. Dans ce cas, la fonction correspondante sera appelée. La dernière possibilité est le polymorphisme paramétrique, qui consiste à utiliser le même code quel que soit le type des arguments. Dans ce cas, on utilise une seule fonction pour traiter une liste d’entiers ou une liste de flottants, par exemple. Au lieu d’associer à chaque fonction un type, dans certains cas on lui associe un type paramétré, instanciable en un type concret. Dans le cas des fonctions de traitement de liste, l’idée est que lorsqu’on ne touche pas aux éléments, alors le traitement est valable quel que soit leur type. Cette technique a été décrite en premier dans [Mil78]. Pour un tour d’horizon de différents systèmes de types statiques, avec en particulier du polymorphisme, on pourra se référer à [Pie02].
Langages
Le système Unix, développé à partir de 1969, a tout d’abord été développé en assembleur sur un mini-ordinateur PDP-7, puis a été porté sur d’autres architectures matérielles. Pour aider ce portage, il a été nécessaire de créer un « assembleur portable », le langage C [KR88, ISO99]. Son but est de fournir des abstractions au dessus du langage d’assemblage. Les structures de contrôle (if, while, for) permettent d’utiliser la programmation structurée, c’està-dire en limitant l’utilisation de l’instruction goto. Les types de données sont également abstraits de la machine : ainsi, int désigne un entier machine, indépendamment de sa taille concrète. Son système de types, bien que statique (il peut y avoir des erreurs de typage à la compilation), est assez rudimentaire : toutes les formes de transtypage sont acceptées, certaines conversions sont insérées automatiquement par le compilateur, et la plupart des abstractions fournies par le langage sont perméables. Le noyau Linux est écrit dans un dialecte du langage C. Le noyau du système Mac OS X d’Apple est également un dérivé d’Unix, et est donc aussi écrit dans ce langage.
|
Table des matières
1 Introduction
1.1 Rôle d’un système d’exploitation
1.2 Séparation entre espace noyau et espace utilisateur
1.3 Systèmes de types
1.4 Langages
1.5 L’analyse statique dans l’industrie aéronautique
1.6 De l’avionique à l’informatique d’entreprise
1.7 Objectifs et contributions de la thèse
1.8 Plan de la thèse
2 Systèmes d’exploitation
2.1 Architecture physique
2.2 Tâches et niveaux de privilèges
2.3 Appels système
2.4 Le Confused Deputy Problem
3 Analyses statiques existantes
3.1 Taxonomie
3.2 Méthodes syntaxiques
3.3 Analyse de valeurs et interprétation abstraite
3.4 Typage
3.5 Langages sûrs
3.6 Logique de Hoare
3.7 Assistants de preuve
4 Syntaxe et sémantique d’évaluation
4.1 Notations
4.2 Syntaxe
4.3 Mémoire et valeurs
4.4 Interprète
4.5 Opérations sur les valeurs
4.6 Opérations sur les états mémoire
4.7 Accesseurs
4.8 Contextes d’évaluation
4.9 Valeurs gauches
4.10 Expressions
4.11 Instructions
4.12 Erreurs
4.13 Phrases et exécution d’un programme
4.14 Exemple
5 Typage
5.1 Environnements et notations
5.2 Expressions
5.3 Instructions
5.4 Fonctions
5.5 Phrases
5.6 Sûreté du typage
5.7 Typage des valeurs
5.8 Propriétés du typage
5.9 Progrès et préservation
6 Extensions de typage
6.1 Exemple préliminaire : les entiers utilisés comme bitmasks
6.1.1 Modifications
6.1.2 Exemple : ! x & y
6.2 Analyse de provenance de pointeurs
6.2.1 Extensions noyau pour SAFESPEAK
6.2.2 Extensions sémantiques
6.2.3 Insuffisance des types simples
6.2.4 Extensions du système de types
6.2.5 Sûreté du typage
Conclusion
Télécharger le rapport complet
