Soutenance mémoire
Anomalies réseau : exemple de l’attaque par déni de service
Un système de détection d’anomalies peut faire face à de nombreux types d’attaques. Nous nous intéressons, dans un premier temps, aux attaques par déni de service. L’attaque par déni de service par engorgement de paquets SYN (SYN flooding) exploite les mécanismes utilisés par le protocole TCP. Le protocole TCP est un protocole de transport de paquets de données permettant d’obtenir une liaison de données fiable entre deux machines. Lorsque deux machines, qu’on appellera Alice et Bob dans cet exemple, veulent effectuer un échange de données à l’aide du protocole TCP, elles doivent établir une connexion. Celle-ci s’effectue en trois étapes, illustrées en figure 2.1 appelées « poignée de main en trois temps » (ou three-way handshake). Schématiquement, le processus se déroule ainsi :
1. Alice envoie un paquet de type SYN à Bob contenant (entre autres) un numéro de séquence aléatoire ;
2. Bob reçoit ce paquet, enregistre en mémoire une trace de cette connexion en la marquant comme étant « semi-ouverte » et envoie un paquet SYN-ACK d’acquittement à Alice ;
3. Alice reçoit ce paquet SYN-ACK et émet vers Bob un paquet d’acquittement ACK ; les deux hôtes ont ainsi chacun reçu un acquittement de la part de l’autre machine, la communication est établie.Une attaque de type SYN flooding a pour but d’interrompre le fonctionnement normal d’une machine, celle de Bob, dans ce cas. Une attaquante, qu’on appellera Sasha, va envoyer un grand nombre de paquets SYN contenant des numéros de séquence différents à Bob (voir figure 2.2). Bob, suivant la procédure habituelle, enregistre autant de connexions semi-ouvertes que de paquets SYN reçus et envoie les paquets SYN-ACK correspondants à Sasha qui en revanche ne renvoie pas de paquet ACK. La capacité mémoire de la machine de Bob est limitée, soit de manière physique, soit en nombre de connexions qui peuvent être ouvertes (celle-ci est fixée, et est de l’ordre du millier dans les systèmes d’exploitations récents) ; ainsi lorsque le nombre de connexions semi-ouvertes excède cette capacité, la machine de Bob ne fonctionne plus correctement et Alice ne peut plus établir de connexion avec Bob.
Test séquentiel : CUSUM
Un algorithme couramment utilisé (Wang et al., 2002; Siris et Papagalou, 2006;Soule et al., 2005; Tartakovsky et al., 2006) en détection d’anomalies réseau, en particulier pour la détection d’attaques par déni de service, est le CUSUM (CUmulated SUM, (Basseville et Nikiforov, 1993)), initialement introduit par Page (1954). CUSUM est, contrairement à la plupart des algorithmes présentés dans ce manuscrit, un algorithme séquentiel, famille d’algorithmes ayant l’avantage de détecter un changement abrupt avec un délai minimal. L’algorithme repose sur un test d’hypothèses dans lesquelles on connaît la distribution des données avant et après le changement. Notons le logarithme du rapport de vraisemblance d’une observation N(t) par st = log pθ1 (N(t))/pθ0(N(t)), où θ0 et θ1 sont les paramètres de la distribution avant et après le changement.
Description de la méthode TopRank
Lévy-Leduc et Roueff (2009) proposent une méthode pour la détection de ruptures, dans les cas particuliers où l’on veut détecter des attaques de type déni de service par SYN ou UDP flooding ou balayage de ports ou de réseaux. L’objectif, par exemple dans la tâche de détection de DoS est de pouvoir analyser les séries temporelles du nombre de paquets envoyés à tous les hôtes du réseau afin de détecter les machines victimes d’attaques. Le nombre de machines apparaissant dans les traces de données étant très élevé, une diminution de la quantité de données à analyser est nécessaire. La méthode de Lévy-Leduc et Roueff (2009) combine ainsi une étape de filtrage qui permet de diminuer la quantité de données traitées en éliminant celles non relatives à des machines possiblement attaquées – ce processus produit des séries temporelles censurées – et un test de détection de changement qui avait été initialement proposé par Gombay et Liu (2000). Ce test utilise les idées de Gehan (1965) ou Mantel (1967) qui proposent une généralisation du test de Wilcoxon (que l’on présente dans la section 4.4.1) aux données aléatoirement censurées. Soit une fenêtre de P observations. On subdivise cette fenêtre en deux sous fenêtres de taille p1 et P − p1. Le test de détection de rupture de Gombay et Liu (2000) consiste alors à calculer la statistique permettant de tester l’homogénéité des deux fenêtres pour l’ensemble des valeurs de p1, puis à en prendre la plus grande valeur. Cette plus grande valeur est alors comparée à un seuil (que l’on détermine à partir de la loi de cette statistique sous l’hypothèse nulle) afin de déterminer la présence d’une rupture dans cette fenêtre d’observations. La quantité d’intérêt est dans le cas de la détection d’attaques par SYN flooding le nombre de paquets de type SYN envoyés à chaque adresse IP i. Considérons ainsi la situation où le trafic de données est analysé dans plusieurs fenêtres d’observations successives d’une certaine durée P × ∆, où P est un entier indiquant le nombre de subdivisions de la fenêtre d’observation, et ∆ la durée de ces subdivisions dans lesquelles on compte le nombre de paquets. On veut prendre une décision concernant la présence d’attaques dirigées vers différentes adresses IP et identifier les adresses en question. On désigne ainsi par (Ni(t))1≤t≤P la série temporelle associée au nombre de paquets SYN reçus par l’adresse IP i. La difficulté du problème réside dans le grand nombre d’adresses IP et de séries temporelles à analyser, c’est le point qui justifie l’étape de filtrage du TopRank.
La méthode BTopRank
Dans la suite, la méthode DTopRank est comparée à une méthode plus simple pour laquelle l’étape d’agrégation dans le collecteur central est remplacée par une procédure de comparaisons multiples, la correction de Bonferroni des p-valeurs déterminées dans chaque sonde. Plus précisément, avec le BTopRank, une adresse IP est déclarée comme attaquée au niveau α ∈ (0, 1) si au moins une des sondes locales a calculé une p-valeur inférieure à α/K, c’est-à-dire si K(inf1≤k≤K Pvalk) <α, Pvalk étant la p-valeur calculée par la sonde Mk. La correction de Bonferroni est la méthode la plus simple pour limiter le taux de fausses alarmes lorsque l’on tente de prendre une décision à partir de tests multiples sur un ensemble de données. En effet, le risque de rejeter à tort l’hypothèse nulle augmente avec le nombre de prises de décision supplémentaires. La correction de Bonferroni consiste alors à diviser le seuil de décision α par le nombre de tests effectués, ici K. Le taux de fausse alarme est contrôlé, mais la méthode devient alors très conservative (en particulier pour K grand), ce qui diminue le taux de détection. On peut se référer par exemple à Dudoit et al. (2003) pour d’autres procédures de tests multiples.
Généralisations multivariées du test de Wald-Wolfowitz
Dans le cas unidimensionnel un test d’homogénéité à deux échantillons est le test de Wald et Wolfowitz (1940). Celui-ci consiste à trier les valeurs des observations regroupées des deux échantillons testés dans l’ordre croissant, puis à compter le nombre de « runs », le run étant une séquence d’observations provenant du même échantillon. On peut voir intuitivement que dans le cas où les deux échantillons diffèrent beaucoup dans leurs moyennes, on obtient de longues séquences et ce nombre de runs est petit, ce qui indique que l’hypothèse nulle d’égalité des distributions peut être rejetée. De par l’absence d’une relation d’ordre naturelle dans des observations multivariées, on peut comprendre qu’il est difficile d’obtenir une généralisation de ce test à des dimensions supérieures ou égales à deux. Friedman et Rafsky (1979) proposent quelques généralisations qui utilisent le concept d’arbre de recouvrement de poids minimal (minimal spanning tree, abrégé en MST). Ces méthodes commencent par construire l’arbre de recouvrement de poids minimal sur les données regroupées, c’est-à-dire le graphe complet (aucun point/nœud n’est isolé des autres) qui minimise la somme des poids assignés aux arêtes du graphe, ces poids étant fixés comme étant la distance (euclidienne ou autre) entre les deux nœuds reliés. Un premier test (« runs ») consiste à construire le MST de l’échantillon regroupé, puis à supprimer les arêtes existantes entre les nœuds provenant de groupes différents. La statistique de test est alors le nombre de sous arbres disjoints qui résultent de cet élagage (c’est aussi le nombre d’arêtes supprimées plus un). Les auteurs calculent les deux premiers moments de cette statistique et montrent sa normalité asymptotique (la distribution peut aussi être calculée de manière exacte combinatoirement pour un échantillon de petite taille).
|
Table des matières
1 Introduction
I Détection d’anomalies réseau
2 La détection de changement dans les réseaux de données
2.1 Anomalies réseau : exemple de l’attaque par déni de service
2.2 Tests statistiques de données agrégées
2.2.1 Test séquentiel : CUSUM
2.2.2 Analyse en composantes principales
2.3 Détection et identification de ruptures
2.3.1 Réduction de la dimension par agrégation aléatoire (sketches)
2.3.2 Test rétrospectif et réduction de la dimension avec filtrage par records : TopRank
3 Test de changement pour données censurées dans l’application réseau
3.1 Introduction
3.2 Description des méthodes proposées
3.2.1 Description de la méthode DTopRank
3.2.2 La méthode BTopRank
3.3 Application à un jeu de données réelles
3.3.1 Description des données
3.3.2 Évaluation des performances des méthodes
3.4 Application à un jeu de données synthétique
3.4.1 Description des données
3.4.2 Performance des méthodes
3.5 Conclusion du chapitre
3.6 Démonstration du théorème 1
II Méthodes robustes de tests d’homogénéité et de changement pour données multivariées
4 Tests d’homogénéité et de détection de changements
4.1 Test paramétrique de changement dans la moyenne
4.2 Méthodes à noyaux
4.2.1 MMD
4.2.2 Analyse discriminante de Fisher à noyaux
4.2.3 SVM à une classe
4.3 Méthodes à arbres des plus proches voisins
4.3.1 Généralisations multivariées du test de Wald-Wolfowitz
4.3.2 k plus proches voisins
4.4 Méthodes de rang
4.4.1 Test de rang de Mann-Whitney/Wilcoxon
4.4.2 Test de Kruskal-Wallis
4.4.3 Statistique de Wei et Lachin
4.5 Stratégies pour l’estimation de changements multiples
4.5.1 Méthodes « locales »
4.5.2 Sélection de modèle par pénalisation du nombre de ruptures
4.5.3 Sélection de modèle par l’utilisation de pénalités `1
5 Tests d’homogénéité
5.1 Test d’homogénéité entre deux échantillons
5.1.1 Présentation de la méthode
5.1.2 Implémentation
5.1.3 Données discrètes, manquantes ou censurées
5.2 Test d’homogénéité entre plusieurs groupes de données
5.2.1 Statistique de test
5.2.2 Cas particuliers
5.2.3 Comportement asymptotique de la statistique
5.3 Simulations numériques
5.3.1 Illustration du test d’homogénéité de deux échantillons
5.3.2 Conclusion
5.4 Démonstrations
5.4.1 Démonstration du théorème 3
5.4.2 Démonstration du théorème 4
6 Estimation et détection de ruptures
6.1 Estimation de ruptures multiples
6.1.1 Nombre de ruptures connu et programmation dynamique
6.1.2 Nombre de ruptures inconnu
6.2 Évaluation du niveau de significativité du test dans le cas de la rupture unique
6.2.1 Normalisation de la statistique de test
6.3 Simulations numériques
6.3.1 Comparaison avec les décisions marginales
6.3.2 Robustesse de la statistique à la présence de valeurs aberrantes
6.3.3 Robustesse par rapport à différents profils de changement
6.3.4 Évaluation de la méthode pour changements multiples
6.4 Démonstration du théorème 5
7 Applications
7.1 Détection d’anomalies réseau
7.2 Données économétriques
7.3 Détection de variations de nombres de copies sur micro réseaux d’ADN
Conclusion
A Segmentation de signaux issus d’un accéléromètre
A.1 Protocole expérimental
A.2 Représentations du signal
A.3 Méthodes de détection de ruptures
A.4 Résultats
Bibliographie
Publications
Télécharger le rapport complet
