Security management in telecommunication systems : models, polyhedra and algorithms ; Gestion de la sécurité dans les systèmes de télécommunications : modèles, polyèdre et algorithmes

In this thesis, we propose a new risk management framework for telecommunication networks. This is based on theconcept of Risk Assessment Graphs (RAGs). These graphs contain two types of nodes: access point nodes, or startingpoints for attackers, and asset-vulnerability nodes. The latter have to be secured. An arc in the RAG represents apotential propagation of an attacker from a node to another. A positive weight, representing the propagation difficulty ofan attacker, is associated to each arc. First, we propose a quantitative risk evaluation approach based on the shortestpaths between the access points and the asset-vulnerability nodes. Then, we consider a risk treatment problem, calledProactive Countermeasure Selection Problem (PCSP). Given a propagation difficulty threshold for each pair of accesspoint and asset-vulnerability node, and a set of countermeasures that can be placed on the asset vulnerability nodes, thePCSP consists in selecting the minimum cost subset of countermeasures so that the length of each shortest path froman access point to an asset vulnerability node is greater than or equal to the propagation difficulty threshold.We show that the PCSP is NP-Complete even when the graph is reduced to an arc. Then, we give a formulation of theproblem as a bilevel programming model for which we propose two single-level reformulations: a compact formulationbased on LP-duality, and a path formulation with an exponential number of constraints, obtained by projection. Moreover,we study the path formulation from a polyhedral point of view. We introduce several classes of valid inequalities. Wediscuss when the basic and valid inequalities define facets. We also devise separation routines for these inequalities.Using this, we develop a Branch-and-Cut algorithm for the PCSP along with an extensive computational study. Thenumerical tests show the efficiency of the polyhedral results from an algorithmic point of view.Our framework applies to a wide set of real cases in the telecommunication industry. We ...