Direction de recherche : Serge FDIDA

Co-encadrement : GUILLEMIN Patrice

Algorithmes de comptage dans les trafics IP

La supervision des réseaux IP via l'analyse des statistiques remontées par les routeurs ou autres sondes requiert le traitement rapide de masses de données gigantesques, un tel traitement ayant pour but, par exemple, de détecter des événements inhabituels (sécurité des réseaux), de dégager des grandes tendances dans l'évolution du trafic (planification des réseaux), de pister une composante particulière du trafic (caractérisation de l'usage), etc. Le problème spécifique rencontré dans les réseaux est la cardinalité de l'espace des objets à traiter. Les algorithmes de comptage existant dans la littérature (déterministes ou probabilistes) ne sont pas capables de manipuler des espaces d'état si grands. De plus, il est utile de développer une vision hiérarchique de l'espace d'état, en regroupant des adresses IP selon certains critères (préfixes, adresses engendrant les plus gros volumes, etc.). Nous portons dans notre étude un grand intérêt au problème des heavy hitters hiérarchiques, qui permet d'agréger les éléments d'un flux par clusters. Le regroupement hiérarchique des données favorise en effet la détection d'attaques par déni de service visant par exemple un ensemble d'hôtes appartenant à un même sous-réseau. Nous avons également étudié le problème de comptage des cardinalités locales qui consiste à estimer le nombre de connexions distinctes en provenance d'une même source donnée. Ce type de comptage s'avère notamment utile pour la détection d'anomalies dans les trafics, permettant entre autres d'identifier des scans de ports ou des propagations de virus où un hôte malicieux lance un très grand nombre de connexions vers une large plage d'adresses de destination.

Publications 2010

• 2010
  • P. Truong : “Algorithmes de comptage dans les trafics IP”, soutenance de thèse, soutenance 12/07/2010, direction de recherche Fdida, Serge, co-encadrement : Guillemin, Patrice (2010)