Les noyaux de systèmes d'exploitation manipulent des données fournies par les programmes utilisateur via les appels système. Si elles sont manipulées sans prendre une attention particulière, une faille de sécurité connue sous le nom de Confused Deputy Problem peut amener à des fuites de données confidentielles ou l'élévation de privilèges d'un attaquant. Le but de cette thèse est d'utiliser des techniques de typage statique afin de détecter les manipulations dangereuses de pointeurs contrôlés par l'espace utilisateur. La plupart des systèmes d'exploitation sont écrits dans le langage C. On commence par en isoler un sous-langage sûr nommé Safespeak. Sa sémantique opérationnelle et un premier système de types sont décrits, et les propriétés classiques de sûreté du typage sont établies. La manipulation des états mémoire est formalisée sous la forme de lentilles bidirectionnelles, qui permettent d'encoder les mises à jour partielles des états et variables. Un première analyse sur ce langage est décrite, permettant de distinguer les entiers utilisés comme bitmasks, qui sont une source de bugs dans les programmes C. / Operating system kernels need to manipulate data that comes from user programs through system calls. If it is done in an incautious manner, a security vulnerability known as the Confused Deputy Problem can lead to information disclosure or privilege escalation. The goal of this thesis is to use static typing to detect the dangerous uses of pointers that are controlled by userspace. Most operating systems are written in the C language. We start by isolating Safespeak, a safe subset of it. Its operational semantics as well as a type system are described, and the classic properties of type safety are established. Memory states are manipulated using bidirectional lenses, which can encode partial updates to states and variables. A first analysis is described, that identifies integers used as bitmasks, which are a common source of bugs in C programs. Then, we add to Safespeak the notion of pointers coming from userspace. This breaks type safety, but it is possible to get it back by assigning a different type to the pointers that are controlled by userspace. This distinction forces their dereferencing to be done in a controlled fashion. This technique makes it possible to detect two bugs in the Linux kernel: the first one is in a video driver for an AMD video card, and the second one in the ptrace system call for the Blackfin architecture.

À mesure que le nombre d’objets capables de communiquer croît, le besoin de sécuriser leurs interactions également. La conception des protocoles cryptographiques nécessaires pour cela est une tâche notoirement complexe et fréquemment sujette aux erreurs humaines. La vérification formelle de protocoles entend offrir des méthodes automatiques et exactes pour s’assurer de leur sécurité. Nous nous intéressons en particulier aux méthodes de vérification automatique des propriétés d’équivalence pour de tels protocoles dans le modèle symbolique et pour un nombre non borné de sessions. Les propriétés d’équivalences ont naturellement employées pour s’assurer, par exemple, de l’anonymat du vote électronique ou de la non-traçabilité des passeports électroniques. Parce que la vérification de propriétés d’équivalence est un problème complexe, nous proposons dans un premier temps deux méthodes pour en simplifier la vérification : tout d’abord une méthode pour supprimer l’utilisation des nonces dans un protocole tout en préservant la correction de la vérification automatique; puis nous démontrons un résultat de typage qui permet de restreindre l’espace de recherche d’attaques sans pour autant affecter le pouvoir de l’attaquant. Dans un second temps nous exposons trois classes de protocoles pour lesquelles la vérification de l’équivalence dans le modèle symbolique est décidable. Ces classes bénéficient des méthodes de simplification présentées plus tôt et permettent d’étudier automatiquement des protocoles taggués, avec ou sans nonces, ou encore des protocoles ping-pong. / As the number of devices able to communicate grows, so does the need to secure their interactions. The design of cryptographic protocols is a difficult task and prone to human errors. Formal verification of such protocols offers a way to automatically and exactly prove their security. In particular, we focus on automated verification methods to prove the equivalence of cryptographic protocols for a un-bounded number of sessions. This kind of property naturally arises when dealing with the anonymity of electronic votingor the untracability of electronic passports. Because the verification of equivalence properties is a complex issue, we first propose two methods to simplify it: first we design a transformation on protocols to delete any nonce while maintaining the soundness of equivalence checking; then we prove a typing result which decreases the search space for attacks without affecting the power of the attacker. Finally, we describe three classes of protocols for which equivalence is decidable in the symbolic model. These classes benefit from the simplification results stated earlier and enable us to automatically analyze tagged protocols with or without nonces, as well as ping-pong protocols.

Autant les applications Android ont réussi à positionner Android parmi les systèmes d'exploitation les plus utilisés, autant elles ont facilité aux créateurs de maliciels de s'introduire et de compromettre ses appareils. Une longue liste de menaces causées par les applications téléchargées vise l'intégrité du système et la vie privée de ses utilisateurs. Malgré l'évolution incessante du système Android pour améliorer son mécanisme de sécurité, le niveau de sophistication des logiciels malveillants a augmenté et s'adapte continuellement avec les nouvelles mesures. L'une des principales faiblesses menaçant la sécurité de ce système est le manque abyssal d'outils et d'environnements permettant la spécification et la vérification formelle des comportements des applications avant que les dommages ne soient causés. À cet égard, les méthodes formelles semblent être le moyen le plus naturel et le plus sûr pour une spécification et une vérification rigoureuses et non ambiguës de telles applications. Notre objectif principal est de développer un cadre formel pour le renforcement de politiques de sécurité dans les applications Android. L'idée est d'établir une synergie entre le paradigme orienté aspect et les méthodes formelles. L'approche consiste à réécrire le programme de l'application en ajoutant des tests de sécurité à certains points soigneusement sélectionnés pour garantir le respect de la politique de sécurité. La version réécrite du programme préserve tous les bons comportements de la version originale qui sont conformes à la politique de sécurité et agit contre les mauvais. / As much as they have positioned Android among the most widely used operating systems, Android applications have helped malware creators to break in and infect its devices. A long list of threats caused by downloaded applications targets the integrity of the system and the privacy of its users. While the Android system is constantly evolving to improve its security mechanism, the malware's sophistication level is skyrocketing and continuously adapting with the new measures. One of the main weaknesses threatening smartphone security is the abysmal lack of tools and environments that allow formal specification and verification of application behaviors before damage is done. In this regard, formal methods seem to be the most natural and secure way for rigorous and unambiguous specification and verification of such applications. Our ultimate goal is to formally enforce security policies on Android applications. The main idea is to establish a synergy between the aspect-oriented paradigm and formal methods such as the program rewriting technique. The approach consists of rewriting the application program by adding security tests at certain carefully selected points to ensure that the security policy is respected. The rewritten version of the program preserves all the good behaviors of the original one that comply with the security policy and acts against the bad ones.

L'avènement d'Internet révolutionne l'accès à l'information, mais contribue également à l'essor de nouveaux services, notamment le commerce électronique, à l'allègement de la bureaucratie et à l'arrivée d'une multitude de e-services. Or, le développement de cette technologie de l'information s'est accompagné d'une panoplie de problématiques. Parmi celles-ci, les plus inquiétantes ont trait à la sécurité puisqu'elles mettent en péril le bon fonctionnement de ces services. Le présent mémoire approfondit ces problématiques de sécurité selon une approche formelle : les algèbres de processus. Dans un premier temps, le fruit de la recherche sur les failles de sécurité réseau de niveau deux et trois de la couche TCP/IP et d'une étude comparative de l'expressivité des principales algèbres de processus est présenté. Dans un second temps, les caractéristiques souhaitées d'une algèbre de modélisation de réseau sont mises en exergue et sont intégrées dans la syntaxe et la sémantique d'une nouvelle algèbre. Finalement, une nouvelle algèbre de processus pour la modélisation de réseau, Netcal, ainsi que les principes d'un système de détection de failles d'architecture et de configuration de réseau sont explicités.

Ce mémoire traite en premier lieu des avantages et des désavantages des différentes approches visant à assurer la sûreté et la sécurité des logiciels. En second lieu, il présente une nouvelle approche pour combiner l'analyse statique et l'analyse dynamique afin de produire une architecture de sécurité plus puissante. Les premiers chapitres du mémoire comportent une revue analytique des différentes approches statiques, dynamiques et hybrides qui peuvent être utilisées afin de sécuriser le code potentiellement malicieux. L'exposé identifie alors les avantages et les inconvénients de chaque approche ainsi que le champ des politiques de sécurité dans lesquels on peut l'appliquer. Le dernier chapitre traite de la possibilité de combiner l'analyse statique et l'analyse dynamique par une nouvelle approche hybride. Cette approche consiste à instrumenter le code seulement là où c'est nécessaire pour assurer satisfaire une politique de sécurité définie par l'usager et exprimée en un ensemble de propriétés exprimées μ-calcul modal. Cette instrumentation est guidée par une analyse statique effectuée à priori et basée sur un système de type à effets. Les effets représentent les accès aux ressources protégées du système. / The purpose of this thesis is twofold. In the first place it presents a comparative study of the advantages and drawbacks of several approaches to insure software safety and security. It then focuses more particularly on combining static analyses and dynamic monitoring in order to produce a more powerful security architecture. The first chapters of the thesis present an analytical review of the various static, dynamic and hybrid approaches that can be used to secure a potentially malicious code. The advantages and drawbacks of each approach are thereby analyzed and the field of security properties that can be enforced by using it are identified. The thesis then focuses on the possibility of combining static and dynamic analysis through a new hybrid approach. This approach consists in a code instrumentation, that only alters those parts of a program where it is necessary to do so to insure the respect of a user-defined security policy expressed in a set of modal μ-calculus properties. this instrumentation is guided by a static analysis based on a type and effect system. The effects represent the accesses made to pretested system ressources.

Ce mémoire présente une nouvelle approche pour sécuriser du code potentiellement malicieux à l'aide d'un moniteur incorporé au code. Les premiers chapitres du mémoire introduisent les notions préliminaires à la présentation de l'approche. Plus précisément, les concepts fondamentaux de la vérification de modèle et du contrôle des systèmes à événements discrets. Le dernier chapitre présente les fondements théoriques de l'approche en généralisant les résultats de Ligatti, Bauer et Walker, et montre une classe de moniteurs qui est plus puissante lorsqu'on précise son contexte d'application. Cette observation mène à l'élaboration d'une approche consistant à instrumenter un programme, dans le but de le rendre sécuritaire, à partir d'un modèle du programme et d'une propriété de sécurité représentée par un automate de Rabin.

Les problèmes logiciels sont frustrants et diminuent l’expérience utilisateur. Par exemple, la fuite de données bancaires, la publication de vidéos ou de photos compromettantes peuvent affecter gravement une vie. Comment éviter de telles situations ? Utiliser des tests est une bonne stratégie, mais certains bogues persistent. Une autre solution est d’utiliser des méthodes plus mathématiques, aussi appelées méthodes formelles. Parmi celles-ci se trouve la sémantique dénotationnelle. Elle met la sémantique extraite de vos logiciels préférés en correspondance avec des objets mathématiques. Sur ceux-ci, des propriétés peuvent être vérifiées. Par exemple, il est possible de déterminer, sous certaines conditions, si votre logiciel donnera une réponse. Pour répondre à ce besoin, il est nécessaire de s’intéresser à des théories mathématiques suffisamment riches. Parmi les candidates se trouvent le sujet de ce mémoire : la théorie des domaines. Elle offre des objets permettant de modéliser formellement les données et les instructions à l’aide de relations d’ordre. Cet écrit présente les concepts fondamentaux tout en se voulant simple à lire et didactique. Il offre aussi une base solide pour des lectures plus poussées et contient tout le matériel nécessaire à sa lecture, notamment les preuves des énoncés présentés. / Bugs in programs are definitively annoying and have a negative impact on the user experience. For example, leaks of bank data or leaks of compromising videos or photos have a serious effect on someone’s life. How can we prevent these situations from happening? We can do tests, but many bugs may persist. Another way is to use mathematics, namely formal methods. Among them, there is denotational semantics. It links the semantics of your favorite program to mathematical objects. On the latter, we can verify properties, e.g., absence of bugs. Hence, we need a rich theory in which we can express the denotational semantics of programs. Domain Theory is a good candidate and is the main subject of this master thesis. It provides mathematical objects for data and instructions based on order relations. This thesis presents fundamental concepts in a simple and pedagogical way. It is a solid basis for advanced readings as well as containing all the needed knowledge for its reading, notably proofs for all presented statements.

Ce mémoire étudie la relation entre les concepts de régionalisme et de convergence des politiques. L'hypothèse avancée est que le régionalisme constitue un moteur à la convergence des politiques entre les États membres d'un même bloc régional. Le cas étudié est l'Amérique du Nord, plus particulièrement l'intégration entre le Canada et les États-Unis de 1980 à 2005, et nous examinons les politiques liées au contrôle frontalier. Nous examinons donc les impacts qu'ont eus l'ALÉ et l'ALÉNA principalement sur les politiques canadiennes et américaines de sécurité à leur frontière commune. Nos résultats confirment partiellement notre hypothèse étant donné que plusieurs politiques similaires ont été adoptées après l'entrée en vigueur de l'ALÉNA en 1994. Toutefois, l'accélération du processus de convergence après le 11 septembre 2001 ne semble pas avoir été causée spécifiquement par le régionalisme. C'est plutôt les attentats terroristes qui expliquent le rapprochement institutionnel entre le Canada et les États-Unis jusqu'en 2005. Malgré tout, le régionalisme a joué un rôle de 2001 à 2005, mais celui-ci s'est plutôt avéré indirect.

« Thèse présentée à l'École des gradués de l'Université Laval pour l'obtention du grade de maître ès arts (M.A.) »

Durant ces dernières décennies, nous avons assisté à une automatisation massive de la société selon toutes ses sphères. Malheureusement, cette révolution technologique n’a pas eu que des bienfaits. En effet, une nouvelle génération de criminels en a profité, afin d’occasionner davantage d’activités illégales. De ce fait, afin de protéger les systèmes informatiques, il est devenu plus que primordial de définir rigoureusement des politiques de sécurité ainsi que de mettre en oeuvre des mécanismes efficaces capables de les appliquer. L’objectif majeur d’un mécanisme de sécurité consiste souvent à contrôler des logiciels, afin de les contraindre à “bien” se comporter. Cependant, la plupart des mécanismes de sécurité procèdent par des méthodes ad hoc qui sont loin d’être efficaces. En outre, ils sont peu fiables, puisqu’il n’y a aucune preuve sur leur capacité à faire respecter les politiques de sécurité. De là apparaît la nécessité de concevoir des mécanismes de sécurité alternatifs qui résolvent le problème de l’application de la sécurité d’une manière formelle, correcte et précise. Dans ce contexte, notre thèse cible principalement la caractérisation formelle de l’application effective des politiques de sécurité via des mécanismes basés sur la réécriture de programmes. On entend par application effective, le fait d’éliminer tous les “mauvais” comportements d’un programme, tout en conservant tous les “bons” comportements qu’il engendre, et ce, sans compromettre la sémantique du programme à sécuriser. Nous avons opté pour la réécriture de programmes, vu sa grande puissance par rapport aux autres mécanismes de sécurité qui sont soit laxistes soit très restrictifs. Les principaux résultats qui ont été réalisés, afin d’atteindre les objectifs ciblés par cette thèse sont les suivants : – Caractérisation formelle de l’application des propriétés de sûreté par la réécriture de programmes. Il s’agit d’appliquer les propriétés de sûreté qui constituent la classe de propriétés de sécurité la plus communément appliquée par les mécanismes de sécurité. – Caractérisation formelle de l’application de n’importe quelle propriété de sécurité par la réécriture de programmes. Cette contribution montre comment la réécriture de programmes permet l’application de politiques de sécurité qu’aucune autre classe de mécanismes de sécurité ne peut appliquer. – Caractérisation alternative de l’application de la sécurité par une approche algébrique. Cette contribution propose un formalisme algébrique afin de réduire l’écart entre la spécification et l’implantation des mécanismes de sécurité basés-réécriture. / During the last decades, we have witnessed a massive automation of the society at all levels. Unfortunately, this technological revolution came with its burden of disadvantages. Indeed, a new generation of criminals emerged and is benefitting from continuous progress of information technologies to cause more illegal activities. Thus, to protect computer systems, it has become very crucial to rigorously define security policies and provide the effective mechanisms required to enforce them. Usually, the main objective of a security mechanism is to control the executions of a software and ensure that it will never violate the enforced security policy. However, the majority of security mechanisms are based on ad hoc methods and thus, are not effective. In addition, they are unreliable, since there is no evidence on their ability to enforce security policies. Therefore, there is a need to develop novel security mechanisms that allow enforcing security policies in a formal, correct, and accurate way. In this context, our thesis targets the formal characterization of effective security policies enforcement that is based on programs rewriting. We mean by “effective” enforcement preventing all the “bad” behaviors of a program while keeping all its "good" behaviors. In addition, effective enforcement should not compromise the semantics of controlled programs. We have chosen for rewriting programs, because it has a great power compared to other security mechanisms that are either permissive or too restrictive. Themain contributions of this thesis are the following : – Formal characterization of security enforcement of safety properties through program rewriting. Safety properties represent the main class of properties usually enforced by security mechanisms. – Formal characterization of any security property using program rewriting. This contribution shows how program rewriting allows the enforcement of security policies that no other class of security mechanisms can enforce. – Algebraic approach as an alternative formal characterization of program rewriting based security enforcement. In this contribution, we investigate an algebraic formal model in order to reduce the gap between the specification and the implementation of program rewriting based security mechansisms.