Dans les deux dernières décennies, le logiciel libre a pris un essor considérable. Des distributions qui au début comptaient une centaine de paquets, en ont maintenant des dizaines de milliers, tous de provenance très différente. Ceci engendre des problèmes pour la gestion de qualité. Les outils et procédures ne sont plus adaptés à la taille et la complexité des distributions d'aujourd'hui. Dans cette thèse, nous commençons par présenter une modélisation mathématique des points communs entre les différents types de distribution (Debian et RPM); notamment le concept des paquets et des relations qui existent entre eux: les dépendances et les conflits. Cette modélisation est en partie formalisé avec l'assistant de preuves Coq. Cette modélisation sera ensuite utilisée pour proposer des relations 'sémantiques', qui sont plus adaptés que les relations existantes pour repérer et corriger des erreurs dans les distributions. Nous présentons aussi des algorithmes pour calculer ces relations d'une façon efficace, et nous utiliserons Coq pour prouver formellement les théorèmes les plus importantes utilisées par ces algorithmes. Finalement, nous avons validé les algorithmes sur des distributions existantes. Nous présenterons une analyse de la structure des distributions qui est le résultat de cette validation, ainsi qu'une discussion de la phénomène du "petit monde" en rapport avec les distributions.

<p>This report evaluates whether an interpreted high-level garbage collected language has enough information about its memory behaviour to make better cache decisions than modern general CPU hardware.</p><p>With a generational garbage collector, depending on promotion algorithm and generation size, around 90% of all objects never leave the first generation. This report is based on the hypothesis that, because of the low promotion rate, accesses to higher generations are sufficiently rare not to benefit from caching.</p><p>To test this hypothesis, we built an operating system with a Scheme interpreter in kernel mode, where the interpreter controls the cache. Generic x86 PC hardware was used, since it allows fine-grained control of cache decisions.</p><p>Measurements of execution time in this interpreter show that disabling the cache for generations higher than the first does not give any performance gain, but rather a performance loss of up to 50%.</p><p>We conclude that this interpreter design is not an improvement, but cannot conclude that the hypothesis is false in general. We suggest building a better CPU simulator to gather more data from which to make better caching decisions, moving internal interpreter data structures into the garbage collected heap and modifying the hardware to allow control in the currently rigid dimension of where data is cached---for example separate control of instruction and data caches and separate data caches for different areas of memory.</p>

Depuis quelques années, l' introduction de l' informatique dans l'imprimerie a renouvelé les techniques et les concepts de cette dernière. L'évolution s'est opérée suivant deux axes principaux : -développement de logiciels afin de faciliter la transmission, l'édition et l'archivage des textes destinés à être photocomposés. - développement de matériels pour améliorer les performances et les caractéristiques des machines de photocomposition. En ce qui concerne ce dernier axe, l 'amélioration des performances, en particulier la vitesse de composition, a été acquise au prix d'une diminution de la qualité typographique des caractères. Cette thèse propose une méthode permettant de remédier à cet inconvénient sans perdre sur les performances déjà obtenues. La difficulté du problème est liée aux paramètres suivants : - la finesse de définition d'un caractère dépend de la quantité d'information sur celui-ci. - la rapidité de composition dépend du nombre de données à traiter. De ce fait, elle varie en sens inverse de la finesse de définition. La solution adoptée est issue d'un compromis entre une compression d'informations (jeux de caractères digitaux pour la photocomposeuse) obtenue par des considérations linguistiques et numériques, et une rapidité de décodage obtenue par une architecture multiprocesseurs appropriée. Le problème est traité dans sa totalité, à savoir la définition des formes (encodage) et leur génération (décodage). Il en résulte de nombreuses applications intermédiaires ou dérivées : - création de jeux de caractères pour les photocomposeuses existantes. - création automatique de jeux de caractères dégradés pour l'impression des épreuves - stockage de courbes régulières sous forme condensée. -utilisation en dessin animé (coloriage par ordinateur de l'intérieur de contours complexes).

Miss Rate Curves (MRCs) for main memory have been proposed as a representation of memory utilization for use in a range of optimizations in the area of memory man- agement. Various techniques exist for their creation; however, all real-world methods of MRC generation must make trade-offs between overhead and accuracy. Proposals for new hardware techniques exist, but have yet to be implemented in actual hardware. We pro- pose the use of the Intel PEBS (Precise Event-Based Sampling) performance monitoring capability for the task of MRC generation on existing commodity hardware. We use PEBS to generate MRCs and compare them against MRCs generated through instrumentation, finding the PEBS MRCs to be good, but imperfect approximations, while keeping average PEBS overheads below 5%. We were unable to show that PEBS is better or worse than existing techniques, but believe we have succeeded in showing the promise of the use of general purpose performance monitoring hardware for this task and in motivating future research and development in this area.

Miss Rate Curves (MRCs) for main memory have been proposed as a representation of memory utilization for use in a range of optimizations in the area of memory man- agement. Various techniques exist for their creation; however, all real-world methods of MRC generation must make trade-offs between overhead and accuracy. Proposals for new hardware techniques exist, but have yet to be implemented in actual hardware. We pro- pose the use of the Intel PEBS (Precise Event-Based Sampling) performance monitoring capability for the task of MRC generation on existing commodity hardware. We use PEBS to generate MRCs and compare them against MRCs generated through instrumentation, finding the PEBS MRCs to be good, but imperfect approximations, while keeping average PEBS overheads below 5%. We were unable to show that PEBS is better or worse than existing techniques, but believe we have succeeded in showing the promise of the use of general purpose performance monitoring hardware for this task and in motivating future research and development in this area.

Cette thèse présente le système d'exploitation MutekH, capable de s'exécuter nativement sur une plateforme matérielle multiprocesseur, où les processeurs peuvent être de complexité différente et disposer de spécificités ou de jeux d'instructions différents. Les travaux présentés ici s'insèrent dans un contexte où les systèmes multi-core et les processeurs spécialisés permettent tous deux de réduire la consommation énergétique et d'optimiser les performances dans les systèmes embarqués et dans les systèmes sur puce. Les autres solutions logicielles existantes permettant l'exécution d'applications sur des plateformes multiprocesseurs hétérogènes ne permettent pas, à ce jour, la communication par mémoire partagée, telle qu'on l'envisage habituellement pour les systèmes multiprocesseurs homogènes. Cette solution est la seule qui permet la réutilisation du code source d'applications parallèles existantes pour leur exécution directe par des processeurs différents. La solution proposée est mise en oeuvre en deux phases: grâce au développement d'un noyau dont l'abstraction rend transparente l'hétérogénéité des processeurs, puis à la réalisation d'un outil spécifique d'édition des liens, capable d'harmoniser le code et les données des fichiers exécutables chargés en mémoire partagée. Les résultats obtenus montrent que MutekH permet l'exécution d'applications préexistantes utilisant des services standards, tels que les Threads POSIX, sur des plateformes multiprocesseurs hétérogènes sans dégradation des performances par rapport aux autres systèmes d'exploitation opérant sur des plateformes multiprocesseurs classiques.

Au cours des dernières années, de nombreux systèmes distribués ont évolué pour faire face à la convergence de leur domaine et des réseaux informatiques. À titre d'exemple, la téléphonie sur Internet a révolutionné le domaine des télécommunications par l'introduction de nombreux nouveaux services basés sur des services Web et bases de données. Les systèmes distribués qui fournissent des services avancés doivent être efficaces pour être en mesure de traiter un grand nombre d'utilisateurs et doivent être robustes pour faire face à diverses attaques ciblant le service lui-même ou la plate-forme sous-jacente. Cependant, le développement de systèmes distribués efficace et robuste exige une connaissance approfondie des protocoles utilisés et une certaine maîtrise de la programmation réseau et système bas niveau, ce qui peut être un défi pour de nombreux développeurs. Néanmoins, le processus de développement des systèmes distribués demeure rudimentaire et requiert un haut niveau d'expertise bas niveau. Dans cette thèse, nous montrons que les langages métiers (DSL) peuvent réduire avec succès le niveau d'expertise nécessaire pour construire des systèmes distribués efficace et robuste, ce qui rend la programmation de service à portée de développeurs moyens. Nous présentons trois contributions dans ce domaine. Notre première contribution vise la création de services de téléphonie basés sur le protocole SIP. Nous avons défini une machine virtuelle spécifique au domaine SIP et un DSL nommé SPL, offrant au programmeur des notations de haut niveau et des abstractions dédiées pour le développement de services de téléphonie. La robustesse de SPL a été un facteur clé dans l'accélération du déploiement de service. Une variété de services ont été écrits en SPL, ce qui démontre l'utilité et la facilité de programmation du langage. Notre deuxième contribution est Zébu, une approche basée sur les DSL pour le développement des couches de traitement protocolaires des applications réseau. Nous avons démontré, à travers diverses expériences, que cette approche est une alternative fiable pour le développement manuel des couches de traitement protocolaires. Le code généré par Zébu a de bonnes performances et a une empreinte mémoire nettement inférieur à des solutions existantes codées manuellement, tout en garantissant les propriétés de robustesse et de performance. La troisième contribution de cette thèse est z2z, une approche générative à la construction de passerelles qui permet la communication entre des appareils qui utilisent des protocoles incompatibles. Z2z inclus un compilateur qui vérifie des propriétés de correction et un support d'exécution qui masque les détails bas niveau au développeur de la passerelle. Nous avons utilisé z2z pour générer automatiquement des passerelles entre différents protocoles incompatibles. Les passerelles générées fonctionnent avec une faible empreinte mémoire et pratiquement sans aucun surcoût à l'exécution.

La dernière génération de cartes à puce permet le téléchargement d'applications après leur mise en circulation. Outre les problèmes que cela implique, cette capacité d'extension applicative reste encore aujourd'hui bridée par un espace de stockage adressable restreint. La thèse défendue dans ce mémoire est qu'il est possible d'exécuter efficacement des applications stockées dans la mémoire non-adressable des cartes à puce, disponible en plus grande quantité, et ce, malgré ses temps de latences très longs, donc peu favorables a priori à l'exécution de code. Notre travail consiste d'abord à étudier les forces et faiblesse de la principale réponse proposée par l'état de l'art qu'est un cache. Cependant, dans notre contexte, il ne peut être implémenté qu'en logiciel, avec alors une latence supplémentaire. De plus, ce cache doit respecter les contraintes mémoires des cartes à puce et doit donc avoir une empreinte mémoire faible. Nous montrons comment et pourquoi ces deux contraintes réduisent fortement les performances d'un cache, qui devient alors une réponse insuffisante pour la résolution de notre challenge. Nous appliquons notre démonstration aux caches de code natif, puis de code et méta-données Java et JavaCard2. Forts de ces constats, nous proposons puis validons une solution reposant sur une pré-interprétation de code, dont le but est à la fois de détecter précocement les données manquantes en cache pour les charger à l'avance et en parallèle, mais aussi grouper des accès au cache et réduire ainsi l'impact de son temps de latence logiciel, démontré comme son principal coût. Le tout produit alors une solution efficace, passant l'échelle des cartes à puce.

Malicious attacks on computer systems attempt to obtain and maintain illicit control over the victim system. To obtain unauthorized access, they often exploit vulnerabilities in the victim system, and to maintain illicit control, they apply various hiding techniques to remain stealthy. In this dissertation, we discuss and present solutions for two classes of security problems: TOCTTOU (time-of-check-to-time-of-use) and K-Queue. TOCTTOU is a vulnerability that can be exploited to obtain unauthorized root access, and K-Queue is a hiding technique that can be used to maintain stealthy control of the victim kernel. The first security problem is TOCTTOU, a race condition in Unix-style file systems in which an attacker exploits a small timing gap between a file system call that checks a condition and a use kernel call that depends on the condition. Our contributions on TOCTTOU include: (1) A model that enumerates the complete set of potential TOCTTOU vulnerabilities; (2) A set of tools that detect TOCTTOU vulnerabilities in Linux applications such as vi, gedit, and rpm; (3) A theoretical as well as an experimental evaluation of security risks that shows that TOCTTOU vulnerabilities can no longer be considered "low risk" given the wide-scale deployment of multiprocessors; (4) An event-driven protection mechanism and its implementation that defend Linux applications against TOCTTOU attacks at low performance overhead. The second security problem addressed in this dissertation is kernel queue or K-Queue, which can be used by the attacker to achieve continual malicious function execution without persistently changing either kernel code or data, which prevents state-of-the-art kernel integrity monitors such as CFI and SBCFI from detecting them. Based on our successful defense against a concrete instance of K-Queue-driven attacks that use the soft timer mechanism, we design and implement a solution to the general class of K-Queue-driven attacks, including (1) a unified static analysis framework and toolset that can generate specifications of legitimate K-Queue requests and the checker code in an automated way; (2) a runtime reference monitor that validates K-Queue invariants and guards such invariants against tampering; and (3) a comprehensive experimental evaluation of our static analysis framework and K-Queue Checkers.

Virtualization environments have become basic building blocks in consolidated data centers and cloud computing infrastructures. By running multiple virtual machines (VMs) in a shared physical machine, virtualization achieves high utilization of hardware resources and provides strong isolation between virtual machines. This dissertation discusses the implementation and the evaluation of an approach, called kernel service outsourcing, which improves the performance and the reliability of guest systems in the virtualized, multi-kernel environments. Kernel service outsourcing allows applications to exploit OS services from an external kernel existing in the shared system, not limiting application OS service requests to the local kernel. Because external kernels may provide more efficient services than the local kernel does, kernel service outsourcing provides new opportunities with applications in the guest OS for better performance. In addition, we apply the kernel service outsourcing technique to implement natural diversity, improving the reliability of the virtualized systems. We present two major benefits of kernel service outsourcing. First, we show that I/O service outsourcing can significantly improve the I/O performance of guest OSes by up to several times. In some important cases, the performance of network applications in the guest OS using network outsourcing was comparable to that of native OS (Linux). We also apply kernel service outsourcing between Windows and Linux, and show that kernel service outsourcing is viable even with two heterogeneous OS kernels. In addition, we study further performance optimization techniques that can be achieved in the external kernel when certain OS services are outsourced to the external kernel. The second benefit of kernel service outsourcing is to improve system reliability through natural diversity created by the combination of different kinds of the OS kernel implementations. Because OS services can be outsourced to different versions or even heterogeneous types of OS kernel for equivalent functions, malicious attacks that aim to exploit certain vulnerabilities in specific versions of OS kernels would not succeed in the outsourced kernels. Our case studies with Windows and Linux show that kernel service outsourcing was able to prevent the malicious attacks designed to exploit implementation-dependent vulnerabilities in the OSes from becoming successful in the outsourced systems.