Tutoriel #3 : Traitement de flux de données à grande échelle

Ce tutoriel d'une durée d'une heure et demi environ propose de faire un tour d'horizon des algorithmes existant pour le traitement de grandes masses de données à la volée.

Large-Scale Data Stream Analysis: This one-hour-and-a-half tutorial aims to survey some existing algorithms that process huge amount of data inline, efficiently in term of space and time complexity.

[ENGLISH DESCRIPTION BELOW]
[slides en anglais, talk en français (ou en anglais si non francophone intéressé)]

Intervenant

Programme

L’intérêt d’estimer des métriques ou d’identifier des motifs spécifique entre différents flux de données est important dans les applications traitant des masses de données. De nombreux domaines sont concernés par ce type d’analyse, incluant l’apprentissage, la fouille de donnée, les bases de données, la collecte d’information, ou la surveillance réseau. Dans toutes ces applications, il est nécessaire de traiter rapidement et précisément un nombre considérable de données. Par exemple, dans la gestion d’un réseau IP, l’analyse des flux d’entrée permet de détecter rapidement la présence d’anomalie ou de tentative d’intrusion quand des changements de motifs de communication apparaissent.

Le problème d’extraire de l’information pertinente dans un flux de donnée est similaire au problème d’identifier des motifs qui ne sont pas conformes au comportement attendu. Cette thématique a été un champs de recherche très productif ces derniers décénies. Par exemple, en fonction des spécificités du domaine et du type d'aberration considérée, différentes méthodes ont été conçues, telles que celles de classification, de groupement, du plus proche voisin, statistique, spectral et de théorie de l’information. Un petit état de l’art sur ces techniques, leurs avantages et inconvénients est proposé dans ce tutoriel. Cette approche consiste à traiter toutes les données du flux à la volée, et de ne conserver localement que des résumés, ou synopses, dans lesquels seule l'information essentielle à propos des données est conservée. Cette approche dérive des statistiques sur les flux de données traités, avec des probabilité d'erreurs bornées, sans présupposer aucune contrainte sur l'ordre dans lequel les données sont reçues sur les noeuds (i.e., l'ordre des données peut être manipulé par un adversaire omnipotent). La plupart des recherches existantes utilisant cette approche se sont concentrées sur le calcul de fonctions ou de mesures statistiques avec une erreur $\varepsilon$, utilisant une quantité mémoire de l'ordre de poly(1/epsilon, log n) où n représente la taille du domaine des données entrantes.

Première partie : Modèle de flux de données

Objectif, cas d'utilisation et formalisation du modèle de flux de données.

Deuxième partie : Quelques algorithmes simples

Présentations d'algorithmes classiques, permettant de calculer des fonctions simples sur les flux (entropie, extraction de données fréquentes, estimation du nombre de données distinctes, …)

Troisième partie : Détection d'intrusion par des métriques de similarités (Algorithme AnKLe)

Concernant la sécurisation, nous voudrions être capable de détecter des attaques par surveillance passive des messages transitant sur chaque nœud. S'il est possible de détecter une divergence entre un flux attendu et le flux observé réellement, il serait possible de lancer une alerte. La recherche d'optimalité en terme de capacité de mémoire peut rendre la détection de ces attaques particulièrement complexe. C'est l'objectif de l'algorithme AnKLe.

Quatrième partie : Tolérance aux attaques malveillantes (Echantillonnage uniforme)

Nous considérons dans cette partie le problème d'obtenir un échantillonnage uniforme dans un système large-échelle, en présence d'un adversaire surpuissant. Nous proposons et analysons deux algorithmes de traitement à la volée. La version omnisciente est totalement résistante aux attaques lancées par un adversaire malveillant, tandis que la version "à l'aveugle" est capable de réduire significativement l'impact d'une attaque en utilisant qu'une très faible quantité mémoire.

Large-Scale Data Stream Analysis

Program

The interest of estimating metrics or identify specific patterns between several data streams is important in data intensive applications. Many different domains are concerned by such analyses including machine learning, data mining, databases, information retrieval, and network monitoring. In all these applications, it is necessary to quickly and precisely process a huge amount of data. For instance, in IP network management, the analysis of input streams allows to rapidly detect the presence of anomalies or intrusions when changes in the communication patterns occur.
The problem of extracting pertinent information in a data stream is similar to the problem of identifying patterns that do not conform to the expected behavior, which has been an active area of research for many decades. For instance, depending on the specificities of the domain considered and the type of outliers considered, different methods have been designed, namely classification-based, clustering-based, nearest neighbor based, statistical, spectral, and information theory. We aim to propose a comprehensive survey of these techniques, their advantages and their drawbacks in this tutorial. A common feature of these techniques is their space complexity and their computational cost, as they rely on small space approximation algorithms for analyzing their data.

First part : The data stream model

Aim, use case and formalism of the data stream model.

Second part : Background algorithms

Introduction of classical algorithms that compute some basic function on a data stream (entropy, determining frequent items, estimation of the number of distinct items, …)

Third part : Similarity metric (AnKLe algorithm)

Concerning the safety of the federation of plugs, we want to be able to detect attacks by monitoring streams of messages on each node. If we are able to detect a divergence between an expected stream and the current stream, then we can throw alerts. Search of optimality in term of memory space makes attacks detection challenging in this context. This is the aim of AnKLe algorithm.

Fourth part : Byzantine faut tolerance (Uniform sampling case)

We consider the problem of achieving uniform node sampling in large scale systems in presence of a strong adversary. We have proposed and analyzed two online algorithms. The omniscient one is fully resilient to any attacks launched by a strong adversary, while the knowledge-free one is capable of drastically decreasing the impact of adversarial attacks by using very small memory space.