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.

Prendre de bonnes décisions dans des environnements multiagents est une tâche difficile dans la mesure où la présence de plusieurs décideurs implique des conflits d'intérêts, un manque de coordination, et une multiplicité de décisions possibles. Si de plus, les décideurs interagissent successivement à travers le temps, ils doivent non seulement décider ce qu'il faut faire actuellement, mais aussi comment leurs décisions actuelles peuvent affecter le comportement des autres dans le futur. La théorie des jeux est un outil mathématique qui vise à modéliser ce type d'interactions via des jeux stratégiques à plusieurs joueurs. Des lors, les problèmes de décision multiagent sont souvent étudiés en utilisant la théorie des jeux. Dans ce contexte, et si on se restreint aux jeux dynamiques, les problèmes de décision multiagent complexes peuvent être approchés de façon algorithmique. La contribution de cette thèse est triple. Premièrement, elle contribue à un cadre algorithmique pour la planification distribuée dans les jeux dynamiques non-coopératifs. La multiplicité des plans possibles est à l'origine de graves complications pour toute approche de planification. Nous proposons une nouvelle approche basée sur la notion d'apprentissage dans les jeux répétés. Une telle approche permet de surmonter lesdites complications par le biais de la communication entre les joueurs. Nous proposons ensuite un algorithme d'apprentissage pour les jeux répétés en ``self-play''. Notre algorithme permet aux joueurs de converger, dans les jeux répétés initialement inconnus, vers un comportement conjoint optimal dans un certain sens bien défini, et ce, sans aucune communication entre les joueurs. Finalement, nous proposons une famille d'algorithmes de résolution approximative des jeux dynamiques et d'extraction des stratégies des joueurs. Dans ce contexte, nous proposons tout d'abord une méthode pour calculer un sous-ensemble non vide des équilibres approximatifs parfaits en sous-jeu dans les jeux répétés. Nous montrons ensuite comment nous pouvons étendre cette méthode pour approximer tous les équilibres parfaits en sous-jeu dans les jeux répétés, et aussi résoudre des jeux dynamiques plus complexes. / Making good decisions in multiagent environments is a hard problem in the sense that the presence of several decision makers implies conflicts of interests, a lack of coordination, and a multiplicity of possible decisions. If, then, the same decision makers interact continuously through time, they have to decide not only what to do in the present, but also how their present decisions may affect the behavior of the others in the future. Game theory is a mathematical tool that aims to model such interactions as strategic games of multiple players. Therefore, multiagent decision problems are often studied using game theory. In this context, and being restricted to dynamic games, complex multiagent decision problems can be algorithmically approached. The contribution of this thesis is three-fold. First, this thesis contributes an algorithmic framework for distributed planning in non-cooperative dynamic games. The multiplicity of possible plans is a matter of serious complications for any planning approach. We propose a novel approach based on the concept of learning in repeated games. Our approach permits overcoming the aforementioned complications by means of communication between players. We then propose a learning algorithm for repeated game self-play. Our algorithm allows players to converge, in an initially unknown repeated game, to a joint behavior optimal in a certain, well-defined sense, without communication between players. Finally, we propose a family of algorithms for approximately solving dynamic games, and for extracting equilibrium strategy profiles. In this context, we first propose a method to compute a nonempty subset of approximate subgame-perfect equilibria in repeated games. We then demonstrate how to extend this method for approximating all subgame-perfect equilibria in repeated games, and also for solving more complex dynamic games.

No description available.

Dans le domaine de la classification, les algorithmes d'apprentissage par compression d'échantillons sont des algorithmes qui utilisent les données d'apprentissage disponibles pour construire l'ensemble de classificateurs possibles. Si les données appartiennent seulement à un petit sous-espace de l'espace de toutes les données «possibles», ces algorithmes possédent l'intéressante capacité de ne considérer que les classificateurs qui permettent de distinguer les exemples qui appartiennent à notre domaine d'intérêt. Ceci contraste avec d'autres algorithmes qui doivent considérer l'ensemble des classificateurs avant d'examiner les données d'entraînement. La machine à vecteurs de support (le SVM) est un algorithme d'apprentissage très performant qui peut être considéré comme un algorithme d'apprentissage par compression d'échantillons. Malgré son succès, le SVM est actuellement limité par le fait que sa fonction de similarité doit être un noyau symétrique semi-défini positif. Cette limitation rend le SVM difficilement applicable au cas où on désire utiliser une mesure de similarité quelconque. / In classification, sample compression algorithms are the algorithms that make use of the available training data to construct the set of possible predictors. If the data belongs to only a small subspace of the space of all "possible" data, such algorithms have the interesting ability of considering only the predictors that distinguish examples in our areas of interest. This is in contrast with non sample compressed algorithms which have to consider the set of predictors before seeing the training data. The Support Vector Machine (SVM) is a very successful learning algorithm that can be considered as a sample-compression learning algorithm. Despite its success, the SVM is currently limited by the fact that its similarity function must be a symmetric positive semi-definite kernel. This limitation by design makes SVM hardly applicable for the cases where one would like to be able to use any similarity measure of input example. PAC-Bayesian theory has been shown to be a good starting point for designing learning algorithms. In this thesis, we propose a PAC-Bayes sample-compression approach to kernel methods that can accommodate any bounded similarity function. We show that the support vector classifier is actually a particular case of sample-compressed classifiers known as majority votes of sample-compressed classifiers. We propose two different groups of PAC-Bayesian risk bounds for majority votes of sample-compressed classifiers. The first group of proposed bounds depends on the KL divergence between the prior and the posterior over the set of sample-compressed classifiers. The second group of proposed bounds has the unusual property of having no KL divergence when the posterior is aligned with the prior in some precise way that we define later in this thesis. Finally, for each bound, we provide a new learning algorithm that consists of finding the predictor that minimizes the bound. The computation times of these algorithms are comparable with algorithms like the SVM. We also empirically show that the proposed algorithms are very competitive with the SVM.

Dans cette thèse, nous proposons un cadre unifié pour la pragmatique et la sémantique de la communication entre agents logiciels. La pragmatique traite la façon dont les agents utilisent les actes communicatifs lorsqu’ils participent aux conversations. Elle est liée à la dynamique des interactions entre agents et à la manière avec laquelle les actes individuels sont reliés pour construire des conversations complètes. La sémantique, quant à elle, est intéressée par la signification de ces actes. Elle établit la base pour une signification concise et non ambiguë des messages échangés entre les agents. Ce cadre unifié vise à résoudre trois problèmes majeurs dans le domaine de communication entre agents : 1- L’absence d’un lien entre la pragmatique et la sémantique. 2- L’inflexibilité des protocoles actuels de communication entre agents. 3- La vérification des mécanismes de communication entre agents. Les contributions principales de cette thèse sont : 1- Une approche pragmatique formelle basée sur les engagements sociaux et les arguments. 2- Un nouveau formalisme pour la communication entre agents appelé Réseau d’Engagements et d’Arguments. 3- Un modèle logique définissant la sémantique des éléments utilisés dans l’approche pragmatique. 4- Une technique de vérification de modèles basée sur une sémantique à tableaux pour vérifier une famille de protocoles flexibles de communication entre agents appelée protocoles à base de jeux de dialogue. 5- Un nouveau protocole de persuasion à base de jeux de dialogue. L'idée principale de notre approche pragmatique est que la communication entre agents est modélisée comme des actions que les agents accomplissent sur des engagements sociaux et des arguments. La dynamique de la conversation entre agents est représentée par cette notion d’actions et par l’évolution de ces engagements et arguments. Notre formalisme (Réseau d’Engagements et d’Arguments) basé sur cette approche fournit une représentation externe de la dynamique de communication entre agents. Ce formalisme peut être utilisé par les agents comme moyen pour participer à des conversations d’une manière flexible parce qu’ils peuvent raisonner sur leurs actes communicatifs en utilisant leurs systèmes d’argumentation et l’état actuel de la conversation. Notre modèle logique est une sémantique, à base d’un modèle théorique, pour l’approche pragmatique. Il définit la signification des différents actes de communication que nous utilisons dans notre approche pragmatique. Il exprime également la signification de quelques actes de discours importants dans le contexte de communication multi-agents et il capture la sémantique des arguments annulables. Ce modèle logique permet d’établir le lien entre la sémantique et la pragmatique de communication entre agents. Nous traitons le problème de vérification des protocoles à base de jeux de dialogue en utilisant une technique de vérification de modèles basée sur une sémantique à tableaux. Ces protocoles sont spécifiés sur la base de notre modèle logique. Nous montrons que notre algorithme de vérification offre une technique, non seulement pour vérifier si le protocole à base de jeux de dialogue (le modèle) satisfait une propriété donnée, mais également si ce protocole respecte la sémantique des actes communicatifs. Notre protocole de persuasion à base de jeux de dialogue est spécifié dans le contexte de notre cadre unifié en utilisant un langage logique. Il est implémenté en utilisant une programmation logique et un paradigme orienté-agent. Dans ce protocole, le processus décisionnel des agents est basé sur les systèmes d’argumentation et sur la notion de crédibilité des agents. / In this thesis, we propose a unified framework for the pragmatics and the semantics of agent communication. Pragmatics deals with the way agents use communicative acts when conversing. It is related to the dynamics of agent interactions and to the way of connecting individual acts while building complete conversations. Semantics is interested in the meaning of these acts. It lays down the foundation for a concise and unambiguous meaning of agent messages. This framework aims at solving three main problems of agent communication: 1- The absence of a link between the pragmatics and the semantics. 2- The inflexibility of current agent communication protocols. 3- The verification of agent communication mechanisms. The main contributions of this thesis are: 1- A formal pragmatic approach based on social commitments and arguments. 2- A new agent communication formalism called Commitment and Argument Network. 3- A logical model defining the semantics of the elements used in the pragmatic approach. 4- A tableau-based model checking technique for the verification of a kind of flexible protocols called dialogue game protocols. 5- A new persuasion dialogue game protocol. The main idea of our pragmatic approach is that agent communication is considered as actions that agents perform on social commitments and arguments. The dynamics of agent conversation is represented by this notion of actions and by the evolution of these commitments and arguments. Our Commitment and Argument Network formalism based on this approach provides an external representation of agent communication dynamics. We argue that this formalism helps agents to participate in conversations in a flexible way because they can reason about their communicative acts using their argumentation systems and the current state of the conversation. Our logical model is a model-theoretic semantics for the pragmatic approach. It defines the meaning of the different communicative acts that we use in our pragmatic approach. It also expresses the meaning of some important speech acts and it captures the semantics of defeasible arguments. This logical model allows us to establish the link between the semantics and the pragmatics of agent communication. We address the problem of verifying dialogue game protocols using a tableau-based model checking technique. These protocols are specified in terms of our logical model. We argue that our model checking algorithm provides a technique, not only to verify if the dialogue game protocol satisfies a given property, but also if this protocol respects the underlying semantics of the communicative acts. Our persuasion dialogue game protocol is specified in our framework using a logical language, and implemented using a logic programming and agent-oriented programming paradigm. In this protocol, the agents’ decision making process is based on the agents’ argumentation systems and the notion of agents’ trustworthiness.

La conduite collaborative est un domaine lié aux systèmes de transport intelligents, qui utilise les communications pour guider de façon autonome des véhicules coopératifs sur une autoroute automatisée. Depuis les dernières années, différentes architectures de véhicules automatisés ont été proposées, mais la plupart d’entre elles n’ont pas, ou presque pas, attaqué le problème de communication inter véhicules. À l’intérieur de ce mémoire, nous nous attaquons au problème de la conduite collaborative en utilisant un peloton de voitures conduites par des agents logiciels plus ou moins autonomes, interagissant dans un même environnement multi-agents: une autoroute automatisée. Pour ce faire, nous proposons une architecture hiérarchique d’agents conducteurs de voitures, se basant sur trois couches (couche de guidance, couche de management et couche de contrôle du trafic). Cette architecture peut être utilisée pour développer un peloton centralisé, où un agent conducteur de tête coordonne les autres avec des règles strictes, et un peloton décentralisé, où le peloton est vu comme une équipe d’agents conducteurs ayant le même niveau d’autonomie et essayant de maintenir le peloton stable. / Collaborative driving is a growing domain of Intelligent Transportation Systems (ITS) that makes use of communications to autonomously guide cooperative vehicles on an Automated Highway System (AHS). For the past decade, different architectures of automated vehicles have been proposed, but most of them did not or barely addressed the inter-vehicle communication problem. In this thesis, we address the collaborative driving problem by using a platoon of cars driven by more or less autonomous software agents interacting in a Multiagent System (MAS) environment: the automated highway. To achieve this, we propose a hierarchical driving agent architecture based on three layers (guidance layer, management layer and traffic control layer). This architecture can be used to develop centralized platoons, where the driving agent of the head vehicle coordinates other driving agents by applying strict rules, and decentralized platoons, where the platoon is considered as a team of driving agents with a similar degree of autonomy, trying to maintain a stable platoon. / Inscrit au Tableau d'honneur de la Faculté des études supérieures

Dans ce travail, nous proposons un nouveau langage dédié à la détection d'intrusions. Il s'agit d'un langage purement déclaratif, basé sur une logique temporelle linéaire passée avec prédicats du premier ordre. Après avoir effectué une revue de treize langages de détection d'intrusions existant déjà, nous donnons une liste de dix propriétés souhaitables pour un langage de détection d'intrusions. Contrairement au langage que nous proposons, aucun des langages étudiés ne présente à la fois ces dix propriétés. En plus d'être suffisamment expressif pour répondre aux besoins identifiés, il vient avec un algorithme de vérification qui s'exécute en temps linéaire avec la quantité d'information analysée et utilise une quantité bornée d'espace mémoire. Ces deux propriétés permettent de protéger le système de détection d'intrusions contre d'éventuelles attaques d'inondation. / Inscrit au Tableau d'honneur de la Faculté des études supérieures

La communication entre agents est primordiale à l’intérieur des systèmes multiagents. Les agents d’un système multi-agents doivent communiquer pour se coordonner et pour échanger de l’information. Dans ce mémoire, nous avons travaillé à l’élaboration et à l’amélioration d’un langage de communication agent nommé DIAGAL (DIAlogue- Game based Agent Language) dont la sémantique se base sur les engagements sociaux. En fait, notre approche se base sur les jeux de dialogue qui sont des structures qui permettent la négociation d’engagements sociaux par le dialogue. Les agents peuvent donc, à l’aide des jeux de dialogue, communiquer pour créer, annuler ou modifier des engagements sociaux. De plus, nous proposons le concept de réseau d’engagements pour modéliser les conversations entre agents. Les réseaux d’engagements permettent de spécifier les dialogues à l’intérieur d’un système multi-agents en analysant les liens de causalité qui existent entre les différents engagements pouvant exister dans le système. Finalement, nous avons défini différentes métriques qui permettent d’analyser les dialogues entre agents.

A wireless sensor network (WSN) consists of a large number of sensor nodes that are capable of detecting many types of information from the environment, including temperature, light, humidity, radiation and seismic vibrations. Current applications of WSNs include: physical security, air traffic control, video surveillance, environment and building monitoring. Such applications require that each sensor node knows its exact location. In this context, the received signal strength indicator (RSSI) is often used for distance measurements between the sensor nodes. This thesis presents a method for the evaluation of the RSSI properties in application to node localization in WSN. More specifically, a WSN application is implemented for collecting RSSI measurement in different conditions. The application consists of two parts: an experiment control script which runs on a computer, and an experiment mote firmware which runs on each WSN node. Statistical analysis of variance (ANOVA) was performed to determine the factors affecting the RSSI measurements. Result analysis shows that: the relation between RSSI values and distances depends on the environment; the used WSN motes are manufactured with enough precision, as the differences between the motes are insignificant; even if the RSSI measurements have significant variation, the mean RSSI values correlate with the distances; using different transmission power levels can provide additional information about the distances.

Ce mémoire propose un modèle de programmation distribuée basé sur la migration de processus pouvant communiquer à l’aide de canaux de communication. Ce travail cadre bien avec le contexte actuel où l’augmentation de la puissance de traitement passe par les processeurs multicoeurs et les systèmes distribués, qui permettent l’exécution de plusieurs processus en parallèle. L’étude de différentes algèbres de processus et langages de programmation permettant le parallélisme a tout d’abord permis de comparer leurs différentes caractéristiques. Suite à cette étude, nous présentons différents concepts né- cessaires à la mise en place de notre modèle distribué par migration de processus, dans le cadre des langages objets qui imposent certaines contraintes. Finalement, l’implé- mentation de notre modèle à l’aide des fonctionnalités de Stackless Python permet de voir comment chacun des concepts a été mis en place. Cette implémentation se présente sous la forme d’une extension qui permet la transformation de programmes existants en programmes distribués.