Algorithmics-Graphs-Combinatorics
- Domaine
- Algorithmics-Graphs-Combinatorics
- Domain - extra
- Nash Equlibria-Networks-Security
- Année
- 2011
- Starting
- October 2011
- État
- Open
- Sujet
- Application of game algorithms in the study of network security problems
- Thesis advisor
- MANOUSSAKIS Yannis
- Co-advisors
- Co-encadrement possible avec Lin Chen, équipe réseaux du LRI
- Laboratory
- Collaborations
- Collaboration étroite avec Lin Chen équipe réseaux du LRI,
Mais également, possible collaboration avec:
- Fun Chung, University of California, San Diego,
- D. Barth PRISM Université de Versailles,
- J. Cohen, PRISM, Université de Versailles. - Abstract
- La croissance exponentielle des réseaux de télécommunications et internet, nécessite une étude systématique des aspects sécurité à fin de modéliser les comportements des attaquants et dériver les mécanismes de défense efficaces. S’inscrivant dans ce contexte, ce projet vise à développer un cadre générique en utilisant les algorithmes des jeux pour aborder des problèmes de sécurité. Plus spécifiquement, ces travaux consistent à 1) établir les modèles des jeux adaptés pour les problèmes de sécurité ; 2) développer des algorithmes pour résoudre les jeux et dériver la stratégie optimale pour le défenseur.
- Context
- The utilization of game theory to study the network security problems has attracted considerable research and has led to valuable insight on the attackers’ behaviour and the optimal strategy for the network defenders and the references therein. A security game on a network is usually modeled by a graph.
However, most of them are focused on the characterization of the Nash equilibrium (NE) of the formulated security game and the defenders’ strategy at the NE, few of them performs a systematic study on the complexity (in terms of time and space) of how to solve the game and reach the NE from an algorithmic perspective. The proposed work aims at filling this gap by establishing necessary theoretical foundations under the game algorithmic framework. As another novelty of the thesis, we would like to emphasize the multi-disciplinary nature of the addressed topic at the nexus of network security, graph theory, game theory, security, economics, distributed systems and algorithm designs.
- Objectives
- The objective is to establish appropriate theoretical models of security attacks and defenses for emerging networks as Internet and wireless networks under a game algorithmic framework and to design efficient defense strategies for the defender based on the theoretical results. More specifically, we expect to develop algorithms with polynomial complexity to reach the (NE). In case where the problem is NP-complete, we aim at establishing approximation or non-approximability results with distributed heuristic polynomial algorithms.
- Work program
- As an initial plan, the work will consist of the following main steps, which are also the main milestones of establishing the pertinent game algorithmic foundation on the network security problems.
• Step 1: Study the network security problems (literature study on the network security) and the relevant graph models. Formulate the network security games using appropriate abstraction.
• Step 2: Establish the existence, uniqueness if the case, of the NE of the formulated security game. Develop algorithms with polynomial complexity to reach the NE. In case where the problem is NP-complete, derive the relevant approximation or non-approximability results with distributed heuristic polynomial algorithms.
• Step 3: Based on the analytical results, design efficient protocols and security solutions implementing the developed algorithms proposed in previous step.
- Extra information
- Prerequisite
- Algorithms, Game theory about Nash equilibria, networks,
- Détails
Sujet-NashEqulibria-Networks-Security.pdf- Expected funding
- Institutional funding
- Status of funding
- Expected
- Candidates
- Jean-Alexandre Anglès d'Auriac, étudiant en M2R à l'Université de Grenoble. Le candidat réalise actuellement son stage de M2 sur ce même sujet sous ma direction. Un papier est en cours de rédaction.
- Utilisateur
- Créé
- Dimanche 19 juin 2011 17:40:14 CEST
- dernière modif.
- Dimanche 19 juin 2011 17:58:37 CEST
Connexion
Ecole Doctorale Informatique Paris-Sud
Directrice
Nicole Bidoit
Assistante
Stéphanie Druetta
Conseiller aux thèses
Dominique Gouyou-Beauchamps
ED 427 - Université Paris-Sud
UFR Sciences Orsay
Bat 650 - aile nord - 417
Tel : 01 69 15 63 19
Fax : 01 69 15 63 87
courriel: ed-info à lri.fr