Université de Rennes 1 Detection and localization of link-level network anomalies using end-to-end path monitoring Détection et localisation des anomalies réseau au niveau des liens en utilisant de la surveillance des chemins de bout-en-bout Monitorage des réseauxdétection des anomalieslocalisation des anomaliesmonitorage des chemins de bout-en-bout Network monitoringanomaly detectionanomaly localizationend-toend path monitoringlink-level network anomalies Réseaux d'ordinateurs Mesures de sécurité Internet L'objectif de cette thèse est de trouver des techniques de détection et de localisation des anomalies au niveau des liens qui soient à faible coût, précises et rapides. La plupart des techniques de détection et de localisation des anomalies au niveau des liens qui existent dans la littérature calculent les solutions, c-à-d l'ensemble des chemins à monitorer et les emplacements des dispositifs de monitorage, en deux étapes. La première étape sélectionne un ensemble minimal d'emplacements des dispositifs de monitorage qui permet de détecter/localiser toutes les anomalies possibles. La deuxième étape sélectionne un ensemble minimal de chemins de monitorage entre les emplacements sélectionnés de telle sorte que tous les liens du réseau soient couverts/distinguables paire par paire. Toutefois, ces techniques ignorent l'interaction entre les objectifs d'optimisation contradictoires des deux étapes, ce qui entraîne une utilisation sous-optimale des ressources du réseau et des mesures de monitorage biaisées. L'un des objectifs de cette thèse est d'évaluer et de réduire cette interaction. A cette fin, nous proposons des techniques de détection et de localisation d'anomalies au niveau des liens qui sélectionnent les emplacements des moniteurs et les chemins qui doivent être monitorés conjointement en une seule étape. Par ailleurs, nous démontrons que la condition établie pour la localisation des anomalies est suffisante mais pas nécessaire. Une condition nécessaire et suffisante qui minimise le coût de localisation considérablement est établie. Il est démontré que les deux problèmes sont NP-durs. Des algorithmes heuristiques scalables et efficaces sont alors proposés. The aim of this thesis is to come up with cost-efficient, accurate and fast schemes for link-level network anomaly detection and localization. It has been established that for detecting all potential link-level anomalies, a set of paths that cover all links of the network must be monitored, whereas for localizing all potential link-level anomalies, a set of paths that can distinguish between all links of the network pairwise must be monitored. Either end-node of each path monitored must be equipped with a monitoring device. Most existing link-level anomaly detection and localization schemes are two-step. The first step selects a minimal set of monitor locations that can detect/localize any link-level anomaly. The second step selects a minimal set of monitoring paths between the selected monitor locations such that all links of the network are covered/distinguishable pairwise. However, such stepwise schemes do not consider the interplay between the conflicting optimization objectives of the two steps, which results in suboptimal consumption of the network resources and biased monitoring measurements. One of the objectives of this thesis is to evaluate and reduce this interplay. To this end, one-step anomaly detection and localization schemes that select monitor locations and paths that are to be monitored jointly are proposed. Furthermore, we demonstrate that the already established condition for anomaly localization is sufficient but not necessary. A necessary and sufficient condition that minimizes the localization cost drastically is established. The problems are demonstrated to be NP-Hard. Scalable and near-optimal heuristic algorithms are proposed. Electronic Thesis or DissertationText application/pdf1 : 3402 Kohttp://ecm.univ-rennes1.fr/nuxeo/site/esupversions/8656a5c6-f26d-4e7c-81ea-15335fd057a6 Salhi Emna 1984-11-10 TN 167786725 10030698 emna.salhi@gmail.com 2013REN1S021 http://www.theses.fr/2013REN1S021 2013-02-13 Informatique Université de Rennes 1thesis.degree.grantor_1 02778715X Doctorat non ouiCousinBernardintervenant_1078661803LahoudSamerintervenant_2108881091 Mathématiques, informatique, signal, électronique et télécommunicationsecoleDoctorale_1 139007164 IRISA partenaireRecherche_1 026386909 Universite européenne de BretagnepartenaireRecherche_2 139075119 ddc:004 CousinBernardLahoudSamerUniversité de Rennes 1Sciences et technologie, médecine, pharmacie, odontologie, droit, économie, gestion, philosophieMathématiques, informatique, signal, électronique et télécommunicationsÉcole doctorale Mathématiques, informatique, signal, électronique et télécommunications (Rennes) IRISA Universite européenne de Bretagne ASCII PDF 3483286