La planification devient complexe quand il s’agit de gérer des situations incertaines. Prédire de façon précise est une tâche fastidieuse pour les planificateurs humains. L’approche Simulation-Based Planning consiste à associer la planification à la simulation. Chaque plan généré est simulé afin d’être testé et évalué. Le plan le plus approprié est alors retenu. Cependant, le problème est encore plus complexe lorsque viennent s’ajouter des contraintes spatiales. Par exemple, lors d’un feu de forêt, des bulldozers doivent construire une ligne d’arrêt pour arrêter la propagation des feux. Ils doivent alors tenir compte non seulement de l’avancée des feux mais aussi des caractéristiques du terrain afin de pouvoir avancer plus facilement. Nous proposons une approche de géosimulation basée sur les agents et qui a pour but d’assister la planification dans un espace réel, à large échelle géographique et surtout à forte composante spatiale. Un feu de forêt est un problème typique nécessitant une planification dans un monde réel incertain et soumis à de fortes contraintes spatiales. Nous illustrons donc notre approche (nommée ENCASMA) sur le problème des feux de forêts. L’approche consiste à établir un parallélisme entre l’Environnement Réel ER (p.ex. une forêt incendiée) et un Environnement de Simulation ES (p.ex. une reproduction virtuelle de la forêt incendiée). Pour garantir un niveau acceptable de réalisme, les données spatiales utilisées dans l’ES doivent absolument provenir d’un SIG (Système d’information Géographique). Les planificateurs réels comme les pompiers ou les bulldozers sont simulés par des agents logiciels qui raisonnent sur l’espace modélisé par l’ES. Pour une meilleure sensibilité spatiale (pour tenir compte de toutes les contraintes du terrain), les agents logiciels sont dotés de capacités avancées telles que la perception. En utilisant une approche par géosimulation multiagent, nous pouvons générer une simulation réaliste du plan à exécuter. Les décideurs humains peuvent visualiser les conséquences probables de l’exécution de ce plan. Ils peuvent ainsi évaluer le plan et éventuellement l’ajuster avant son exécution effective (sur le terrain). Quand le plan est en cours d’exécution, et afin de garantir la cohérence des données entre l’ER et l’ES, nous gardons trace sur l’ES des positions (sur l’ER) des planificateurs réels (en utilisant les technologies du positionnement géoréférencé). Nous relançons la planification du reste du plan à partir de la position courante de planificateur réel, et ce de façon périodique. Ceci est fait dans le but d’anticiper tout problème qui pourrait survenir à cause de l’aspect dynamique de l’ER. Nous améliorons ainsi le processus classique de l’approche DCP (Distributed Continual Planning). Enfin, les agents de l’ES doivent replanifier aussitôt qu’un événement imprévu est rapporté. Étant donné que les plans générés dans le cas étudié (feux de forêts) sont essentiellement des chemins, nous proposons également une approche basée sur la géosimulation orientée agent pour résoudre des problèmes particuliers de Pathfinding (recherche de chemin). De plus, notre approche souligne les avantages qu’apporte la géosimulation orientée agent à la collaboration entre agents humains et agents logiciels. Plus précisément, elle démontre : • Comment la cognition spatiale des agents logiciels sensibles à l’espace peut être complémentaire avec la cognition spatiale des planificateurs humains. • Comment la géosimulation orientée agent peut complémenter les capacités humaines de planification lors de la résolution de problèmes complexes. Finalement, pour appliquer notre approche au cas des feux de forêts, nous avons utilisé MAGS comme plate-forme de géosimulation et Prometheus comme simulateur du feu. Les principales contributions de cette thèse sont : 1. Une architecture (ENCASMA) originale pour la conception et l’implémentation d’applications (typiquement des applications de lutte contre les désastres naturels) dans un espace géographique réel à grande échelle et dynamique. 2. Une approche basée sur les agents logiciels pour des problèmes de Pathfinding (recherche de chemin) particuliers (dans un environnement réel et à forte composante spatiale, soumis à des contraintes qualitatives). 3. Une amélioration de l’approche de planification DCP (plus particulièrement le processus de continuité) afin de remédier à certaines limites de la DCP classique. 4. Une solution pratique pour un problème réel et complexe : la lutte contre les feux de forêts. Cette nouvelle solution permet aux experts du domaine de mieux planifier d’avance les actions de lutte et aussi de surveiller l’exécution du plan en temps réel. / Planning becomes complex when addressing uncertain situations. Accurate predictions remain a hard task for human planners. The Simulation-Based Planning approach consists in associating planning and simulation. Each generated plan is simulated in order to be tested and evaluated. The most appropriate plan is kept. The problem is even more complex when considering spatial constraints. For example, when fighting a wildfire, dozers build a firebreak to stop fire propagation. They have to take into account not only the fire spread but also the terrain characteristics in order to move easily. We propose an agent-based geosimulation approach to assist such planners with planning under strong spatial constraints in a real large-scale space. Forest fire fighting is a typical problem involving planning within an uncertain real world under strong spatial constraints. We use this case to illustrate our approach (ENCASM). The approach consists in drawing a parallel between the Real Environment RE (i.e. a forest in fire) and the Simulated Environment SE (i.e. a virtual reproduction of the forest). Spatial data within the SE should absolutely come from a GIS (Geographic Information System) for more realism. Real planners such as firefighters or dozers are simulated using software agents which reason about the space of the SE. To achieve a sufficient spatial awareness (taking into account all terrain’s features), agents have advanced capabilities such as perception. Using a multiagent geosimulation approach, we can generate a realistic simulation of the plan so that human decision makers can visualize the probable consequences of its execution. They can thus evaluate the plan and adjust it before it can effectively be executed. When the plan is in progress and in order to maintain coherence between RE and SE, we keep track in the SE of the real planners’ positions in the RE (using georeferencing technologies). We periodically replan the rest of the plan starting from the current position of the real planner. This is done in order to anticipate any problem which could occur due to the dynamism of the RE. We thus enhance the process of the classical Distributed Continual Planning DCP. Finally, the agents must replan as soon as an unexpected event is reported by planners within the RE. Since plans in the studied case (forest fires) are mainly paths, we propose a new approach based on agent geosimulation to solve particular Pathfinding problems. Besides, our approach highlights the benefits of the agent-based geo-simulation to the collaboration of both humans and agents. It thus shows: • How spatial cognitions of both spatially aware agents and human planners can be complementary. • How agent-based geo-simulation can complement human planning skills when addressing complex problems. Finally, when applying our approach on firefighting, we use MAGS as a simulation platform and Prometheus as a fire simulator. The main contributions of this thesis are: 1. An original architecture (ENCASMA) for the design and the implementation of applications (typically, natural disasters applications) in real, dynamic and large-scale geographic spaces. 2. An agent-based approach for particular Pathfinding problems (within real and spatially constrained environments and under qualitative constraints). 3. An enhancement of the DCP (particularly, the continual process) approach in order to overcome some limits of the classical DCP. 4. A practical solution for a real and complex problem: wildfires fighting. This new solution aims to assist experts when planning firefighting actions and monitoring the execution of these plans.

Dans ce travail, nous définissons une nouvelle algèbre de processus basée sur CCS. Cette algèbre, qui est destinée à la sécurisation formelle de réseaux, est munie d’un opérateur de surveillance qui permet de contrôler les entrées et les sorties d’un processus, ou d’un sous-processus, à l’image d’un pare-feu dans un réseau informatique. L’algèbre permet donc de modéliser des réseaux munis de moniteurs, et également, n’importe quel système communicant devant être contrôlé par des moniteurs. Avant d’entrer dans le vif du sujet, nous débutons par une revue des approches globales en détection d’intrusions, soient l’approche comportementale et l’approche par scénarios. Nous parcourons par la suite différents langages formels destinés à la modélisation de systèmes communicants, en prêtant une attention particulière aux algèbres de processus.

Avec l’informatisation accrue de toutes les sphères d’activités de la société, nous assistons de nos jours à une explosion de la quantité de données électroniques existantes. C’est pourquoi, nous devons avoir recours à des outils automatiques qui sont à même d’analyser automatiquement les données et de ne nous fournir que l’information pertinente et résumée par rapport à ce qui est recherché. Les techniques de forage de données sont généralement utilisées à cette fin. Cependant, ces dernières nécessitent généralement un temps de calcul considérable afin d’analyser un large volume de données. Par ailleurs, si les données sont géographiquement distribuées, les regrouper sur un même site pour y créer un modèle (un classificateur par exemple) peut s’avérer très coûteux. Pour résoudre ce problème, nous proposons de construire plusieurs modèles, et plus précisément plusieurs classificateurs, soit un classificateur par site. Ensuite, les règles constituant ces classificateurs sont regroupées puis filtrées en se basant sur certaines mesures statistiques et une validation effectuée à partir de très petits échantillons provenant de chacun des sites. Le modèle résultant, appelé méta-classificateur, est, d’une part, un outil de prédiction pour toute nouvelle instance et, d’autre part, une vue abstraite de tout l’ensemble de données. Nous basons notre approche de filtrage de règles de classification sur une mesure de confiance associée à chaque règle qui est calculée statistiquement et validée en utilisant les échantillons recueillis. Nous avons considéré plusieurs techniques de validation tel qu’il sera présenté dans cette thèse. / With the pervasive use of computers in all spheres of activity in our society, we are faced nowadays with the explosion of electronic data. This is why we need automatic tools that are able to automatically analyze the data in order to provide us with relevant and summarized information with respect to some query. For this task, data mining techniques are generally used. However, these techniques require considerable computing time in order to analyze a huge volume of data. Moreover, if the data is geographically distributed, gathering it on the same site in order to create a model (a classifier for instance) could be time consuming. To solve this problem, we propose to build several models, that is one classifier by site. Then, rules constituting these classifiers are aggregated and filtered based on some statistical measures, and a validation process is carried out on samples from each site. The resulting model, called a metaclassifier is, on one hand, a prediction tool for any new (unseen) instance and, on the other hand, an abstract view of the whole data set. We base our rule filtering approach on a confidence measure associated with each rule, which is computed statistically and then validated using the data samples (one from each site). We considered several validation techniques such as will be discussed in this thesis.

Avec l'extension des cellulaires, des réseaux sans fil et des périphériques mobiles, Java est devenu incontestablement l'environnement d'exécution le plus populaire. Cela est dû à ses aspects de sécurité, portabilité, mobilité et réseaux. Dans ce contexte, la plateforme de choix est Java ME-CLDC. Aussi, vu le nombre grandissant d'applications Java destinées aux périphériques mobiles, la sécurité est devenue un enjeu crucial à considérer d'une manière primordiale. Sécuriser ce type d'applications devient plus qu'impératif, notamment lorsque celles-ci manipulent des données confidentielles telles que les informations relatives aux transactions électroniques. Plus encore, les périph ériques supportant Java se retrouvent souvent interconnectées, ce qui signifie que les applications peuvent ainsi créer des connexions réseaux et faire circuler des données critiques sur les canaux de communications. Cependant, les efforts considérables déployés afin de sécuriser Java ME-CLDC se heurtent à des contraintes de limitations strictes de l'espace mémoire disponible, au sein des périphériques en question. Dans cette optique, cette thèse étudie le problème du maintien de la sécurité sous contraintes mémoire, et cela en analysant la sécurité de la plateforme Java ME-CLDC. Plus précisément, les objectifs majeurs de notre sujet de recherche sont (1) l'évaluation et l'amélioration de la sécurité de Java ME-CLDC et (2) la modélisation du monitoring d'exécution (EM) en y introduisant des contraintes mémoire. à vrai dire, EM constitue une classe importante et omniprésente parmi tous les mécanismes de sécurité utilisés dans les plateformes Java. Les principaux résultats auxquels a abouti notre investigation sont les suivants : - Une analyse de la sécurité de Java ME-CLDC. Les deux contributions principales qu'a engendré cette analyse sont l'analyse de vulnérabilité et l'analyse des risques de cette plateforme. L'analyse de vulnérabilité a révélé la présence de certaines faiblesses dans la plateforme, elle a montré également la manière permettant d'améliorer son modèle de sécurité. Quant à l'analyse des risques, elle a fourni une estimation de la gravité des risques associés aux vulnérabilités décelées. - Une modélisation du monitoring d'exécution sous contraintes mémoire. Cette modélisation couvre aussi bien les moniteurs conventionnels que des moniteurs plus puissants. Les contributions principales qui découlent de notre modélisation sont les suivantes: Premièrement, nous avons défini une nouvelle classe d'automates, dite Bounded History Automata (BHA) ou automates à historique borné, classe d'automate qui permet de spécifier les mécanismes EM opérant sous contraintes mémoire. Deuxièmement, nous avons identifié une nouvelle taxonomie orientée mémoire des propriétés assurées par EM. Troisièmement, nous avons étudié les propriétés localement testables qui peuvent être assurées par des EMs opérant sous contraintes mémoire. Cela est fait en deux étapes: on commence par identi- fier les propriétés assurées par EMs qui sont de nature locale, ensuite on vérifie si ces dernières peuvent être spécifiées par des BHAs. / With the proliferation of mobile, wireless and internet-enabled devices (e.g., PDAs, cell phones, pagers, etc.), Java is emerging as a standard execution environment due to its security, portability, mobility and network support features. The platform of choice in this setting is Java ME-CLDC. With the large number of applications available for Javaenabled network-connected devices, security is of paramount importance. Applications can handle user-sensitive data such as phonebook data or bank account information. Moreover, Java-enabled devices support networking, which means that applications can also create network connections and send or receive data. However, the considerable efforts of securing Java ME-CLDC are constrained by strict memory limitations of the target devices. This thesis aims at investigating memory-constrained security by analyzing the security of Java ME-CLDC and characterizing enforceable security policies. More precisely, the main objectives of our research are (1) evaluating and improving the security of Java ME-CLDC and (2) characterizing memory-constrained execution monitoring; an important class of security mechanisms. The main results of our research are the following: - A security analysis of Java ME-CLDC. The two main contributions of this analysis are a vulnerability analysis and a risk analysis of the platform. The vulnerability analysis revealed the presence of vulnerabilities in the platform and showed how to improve the underlying security model. The risk analysis provided a seriousness estimation of the risks associated with the uncovered vulnerabilities. - A characterization of memory-constrained execution monitoring. This characterization covers conventional monitors as well as more powerful monitors. The contribution of this characterization is mainly threefold. First, we deffined a new automata class, called Bounded History Automata (BHA), to specify memoryconstrained EM enforcement. Second, we identiffied a new memory-directed taxonomy of EM-enforceable properties. Third, we investigated the enforcement of local properties using memory-constrained EM. This was performed by identifying BHA-enforceable local properties and explaining how to check whether an EM-enforceable policy is local or not.

Habituellement, plus le développement d’un logiciel est avancé plus il est dispen- dieux de le modifier. Par conséquent, une approche permettant de simplifier l’étape de maintenance permettrait de réduire considérablement le coût lié au développement de programmes. Le langage déclaratif de la méthodologie Lyee permet justement de simplifier la maintenance de programmes. Cependant, les programmes existants écrits dans un langage impératif doivent être traduits pour être utilisés par celle-ci. Ainsi, dans ce travail, nous proposons une fonction de conversion de programmes écrits dans un langage impératif avec des tableaux et entrées/sorties vers un langage déclaratif. Il s’agit d’une extension de langages L1 et L2 existants qui supportaient déjà les expres- sions arithmétiques et booléennes ainsi que les affectations, les boucles et les instructions conditionnelles. Le travail effectué a donc été d’ajouter les tableaux et les entrées/sorties dans ces langages et d’ajuster la fonction de traduction en conséquent. Aussi, une im- plantation d’une interface de développement permettant de spécifier des programmes dans un langage déclaratif simple à utiliser a été produite.

L’apprentissage multiagent est une direction prometteuse de la recherche récente et à venir dans le contexte des systèmes intelligents. Si le cas mono-agent a été beaucoup étudié pendant les deux dernières décennies, le cas multiagent a été peu étudié vu sa complexité. Lorsque plusieurs agents autonomes apprennent et agissent simultanément, l’environnement devient strictement imprévisible et toutes les suppositions qui sont faites dans le cas mono-agent, telles que la stationnarité et la propriété markovienne, s’avèrent souvent inapplicables dans le contexte multiagent. Dans ce travail de maîtrise nous étudions ce qui a été fait dans ce domaine de recherches jusqu’ici, et proposons une approche originale à l’apprentissage multiagent en présence d’agents adaptatifs. Nous expliquons pourquoi une telle approche donne les résultats prometteurs lorsqu’on la compare aux différentes autres approches existantes. Il convient de noter que l’un des problèmes les plus ardus des algorithmes modernes d’apprentissage multiagent réside dans leur complexité computationnelle qui est fort élevée. Ceci est dû au fait que la taille de l’espace d’états du problème multiagent est exponentiel en le nombre d’agents qui agissent dans cet environnement. Dans ce travail, nous proposons une nouvelle approche de la réduction de la complexité de l’apprentissage par renforcement multiagent. Une telle approche permet de réduire de manière significative la partie de l’espace d’états visitée par les agents pour apprendre une solution efficace. Nous évaluons ensuite nos algorithmes sur un ensemble d’essais empiriques et présentons des résultats théoriques préliminaires qui ne sont qu’une première étape pour former une base de la validité de nos approches de l’apprentissage multiagent. / Multiagent learning is a promising direction of the modern and future research in the context of intelligent systems. While the single-agent case has been well studied in the last two decades, the multiagent case has not been broadly studied due to its complex- ity. When several autonomous agents learn and act simultaneously, the environment becomes strictly unpredictable and all assumptions that are made in single-agent case, such as stationarity and the Markovian property, often do not hold in the multiagent context. In this Master’s work we study what has been done in this research field, and propose an original approach to multiagent learning in presence of adaptive agents. We explain why such an approach gives promising results by comparing it with other different existing approaches. It is important to note that one of the most challenging problems of all multiagent learning algorithms is their high computational complexity. This is due to the fact that the state space size of multiagent problem is exponential in the number of agents acting in the environment. In this work we propose a novel approach to the complexity reduction of the multiagent reinforcement learning. Such an approach permits to significantly reduce the part of the state space needed to be visited by the agents to learn an efficient solution. Then we evaluate our algorithms on a set of empirical tests and give a preliminary theoretical result, which is first step in forming the basis of validity of our approaches to multiagent learning.

L’apprentissage automatique fait parti d’une branche de l’intelligence artificielle et est utilisé dans de nombreux domaines en science. Il se divise en trois catégories principales : supervisé, non-supervisé et par renforcement. Ce mémoire de maîtrise portera uniquement sur l’apprentissage supervisé et plus précisément sur la classification de données. Un des premiers algorithmes en classification, le perceptron, fut proposé dans les années soixante. Nous proposons une variante de cet algorithme, que nous appelons le perceptron dual tronqué, qui permet l’arrêt de l’algorithme selon un nouveau critère. Nous comparerons cette nouvelle variante à d’autres variantes du perceptron. De plus, nous utiliserons le perceptron dual tronqué pour construire des classificateurs plus complexes comme les «Bayes Point Machines». / Machine Learning is a part of the artificial intelligence and is used in many fields in science. It is divided into three categories : supervised, not supervised and by reinforcement. This master’s paper will relate only the supervised learning and more precisely the classification of datas. One of the first algorithms in classification, the perceptron, was proposed in the Sixties. We propose an alternative of this algorithm, which we call the truncated dual perceptron, which allows the stop of the algorithm according to a new criterion. We will compare this new alternative with other alternatives of the perceptron. Moreover, we will use the truncated dual perceptron to build more complex classifiers like the «Bayes Point Machines».

Les problèmes de recherche sur un graphe peuvent être exprimés sous la forme d’un jeu où un ensemble de chercheurs tentent de capturer un ensemble de fugitifs. Lorsqu’un tel jeu est joué en alternance par les deux ensembles de joueurs, nous parlons alors de jeux des policiers et des voleurs (« Cops and Robbers games ») ou plus simplement de jeux policiers-voleurs. Nowakowski et Winkler [28], et indépendamment Quilliot [45], ont introduit la première version des jeux policiers-voleurs dans laquelle un seul policier tente de capturer un seul voleur, les deux se déplaçant à tour de rôle vers des sommets adjacents de leurs positions courantes. Ils ont notamment proposé une jolie caractérisation des graphes gagnants pour le policier qui est basée sur l’existence d’un démantèlement particulier des sommets du graphe ; un démantèlement consistant à retirer un à un les sommets du graphe suivant une certaine règle. Cette caractérisation par démantèlement est par ailleurs intéressante puisqu’elle donne directement un algorithme polynomial de type diminuer pour régner pour résoudre le problème du policier et du voleur. Dans ce mémoire, nous proposons une nouvelle version d’un jeu policier-voleur dans laquelle le voleur se déplace arbitrairement vite dans le graphe et dans laquelle le policier possède une zone de surveillance qui limite le voleur dans ses déplacements. Nous caractérisons les graphes gagnants pour le policier dans ce nouveau jeu en utilisant un concept de démantèlement d’un graphe, similaire à celui de Nowakowski et Winkler [28], Quilliot [45], mais adapté aux conditions de notre nouveau jeu. Nous devons notamment généraliser la définition d’un graphe classique à celle d’un graphe clandestin, qui possède un ensemble de sommets clairs et un ensemble de sommets sombres, afin d’obtenir notre caractérisation par démantèlement. Nous donnons par ailleurs un algorithme qui permet de bâtir une stratégie monotone gagnante pour le policier en nous assurant que le policier sécurise de plus en plus de sommets à chaque tour. / Graph searching problems can be expressed as a game where a group of searchers is trying to capture a group of fugitives on a graph. When players move alternately in such a game, we are then referring to games of Cops and Robbers. Nowakowski and Winkler [28], and independently Quilliot [45], introduced the very first version of cops and robbers games in which a single cop tries to capture a single robber, both players moving alternately from their current positions to neighboring vertices. They notably proposed a very nice characterization of graphs that are winning for the cop, which is based on a particular dismantling scheme of the graph’s vertices; a dismantling scheme consisting in removing one by one each vertex of the graph by following a given rule. This dismantling-like characterization is furthermore interesting since it directly yields a divide-and-conquer algorithm that is polynomial, to solve the cop and robber problem. In this master thesis, we propose a new version of cops and robbers games in which the robber is able to move arbitrarily fast in the graph and in which the cop has a watching area that limits the robber’s moving capabilities. We characterize the cop-winning graphs for this new game by using some dismantling scheme similar to the one given by Nowakowski and Winkler [28], Quilliot [45], but that better fits our new game’s conditions. To obtain this dismantling-like characterization, we particularly need to generalize the definition of a classical graph to an undergrounded graph, whose vertices are split in a set of light vertices and a set of dark vertices. We also give an algorithm that provides a monotonous cop-winning strategy by making sure the cop is securing more and more vertices at each turn.

Ce mémoire traite de la résolution de problèmes d’ordonnancement à l’aide de la programmation par contraintes. Il s’intéresse principalement aux contraintes globales et particulièrement à la contrainte cumulative. Il passe en revue les règles permettant de la filtrer et les principaux algorithmes qui les appliquent. Il explique le Edge-Finder de Vilím et son arbre cumulatif. Il propose un algorithme plus performant et plus général pour appliquer les règles découlant du raisonnement énergétique. Le mémoire traite du cas particulier où toutes les tâches sont de durée identique. Pour modéliser efficacement ce type de problèmes, on y conçoit la contrainte multi-inter-distance. L’algorithme d’ordonnancement de López-Ortiz et Quimper est adapté pour réaliser un algorithme qui applique la cohérence de bornes. La contrainte multi-inter-distance s’avère efficace à résoudre le problème de séquençage des atterrissages d’avions du banc d’essai d’Artiouchine et Baptiste. / This thesis discusses how to solve scheduling problems using constraint programming. We study global constraints and particularly the Cumulative constraint. We survey its main filtering rules and their state-of-the-art filtering algorithms. We explain the Vilím’s Edge-Finder and its cumulative tree.We introduce a more efficient and more general algorithm that enforces the filtering rules from the energetic reasoning. We study the special case where all tasks have identical processing times. To efficiently model such problems, we introduce the Multi-Inter-Distance constraint. The scheduling algorithm by López-Ortiz and Quimper is adapted to produce a filtering algorithm enforcing bounds consistency. The constraint Multi-Inter-Distance is proved efficient to solve the runway scheduling problem on the benchmark by Artiouchine and Baptiste.

Ce mémoire présente une approche d'application de politiques de sécurité qui utilise une analyse de types basée sur un système de types multi-valeurs. Cette analyse est suivie d'une instrumentation lorsque nécessaire. Le langage cible est un langage impératif. Notre approche vise à réduire les faux-positifs générés par une analyse statique, et à réduire la surcharge d'exécution en n'instrumentant que lorsque nécessaire. Les faux-positifs surviennent dans l'analyse de systèmes informatiques lorsqu'une information est manquante durant la compilation, par exemple le nom d'un fichier, et par conséquent, son niveau de sécurité. L'idée principale de notre approche est de distinguer les réponses négatives des réponses incertaines. Au lieu de rejeter les commandes potentiellement non sécuritaires, elles sont identifiées et étiquetées pour la seconde phase de l'analyse. Les réponses négatives et positives sont traitées comme cela se fait d'habitude. Ce travail est une approche hybride d'application de politique de sécurité : les points potentiellement sécuritaires du programme détectés par notre analyse par typage sont instrumentés par la suite avec des tests dynamiques. Le système de typage sur lequel se base le nôtre a été présenté par Desharnais et al. [12]. Notre approche a été acceptée pour publication [7]. Dans ce travail nous présentons les modifications apportées au précédent travail et la phase d'instrumentation qui la complète. La nouveauté de notre approche est de rajouter un niveau de sécurité aux trois du travail précédent. Nous traitons les canaux et les variables de façon spéciale. Les programmes interagissent par le biais de canaux de communication. Des niveaux de confidentialité sont associés aux canaux plutôt qu'aux variables dont le niveau de sécurité est fonction de l'information qu'elles stockent. Notre analyse est sensible au flot. / In this Master thesis, we present an approach to enforce information flow policies using a multi-valued type-based analysis followed by an instrumentation when needed. The target is a core imperative language. Our approach aims at reducing false positives generated by static analysis, and at reducing execution overhead by instrumenting only when needed. False positives arise in the analysis of real computing systems when some information is missing at compile time, for example the name of a file, and consequently, its security level. The key idea of our approach is to distinguish between negative and may responses. Instead of rejecting the possibly faulty commands, they are identified and annotated for the second step of the analysis; the positive and negative responses are treated as is usually done. This work is a hybrid security enforcement mechanism: the maybe-secure points of the program detected by our type based analysis are instrumented with dynamic tests. The basic type based analysis has been reported by Desharnais et al. [12], this work deals with the modification of the type system and the instrumentation step. It has been accepted for publication [7]. The novelty of our approach is the handling of four security types, but we also treat variables and channels in a special way. Programs interact via communication channels. Secrecy levels are associated to channels rather than to variables whose security levels change according to the information they store. Thus the analysis is flow-sensitive.