Mutualisation des Anomalies confidentielle

pour la détection de comportements malveillants

 

AxIS	KDD
Inria	LGI2P
Sophia Antipolis	Nîmes

 

           

 

1. Objet et durée du projet 2

2. Equipes Concernées. 7

3. Descriptif scientifique. 15

3.1 La détection d’anomalies. 22

3.2 Approche envisagée. 28

           

1. Objet et durée du projet

 

La détection de comportements malveillants se base actuellement sur deux types d’approches.

Le premier type consiste à énumérer toutes les attaques/intrusions connues et ensuite à filtrer les comportements entrants en supprimant ceux qui correspondent à une de ces attaques. Il s’agit des approches par mauvais usages (misuse). Ces approches sont celles qui se commercialisent actuellement via les IDS (Intrusion Detection Systems). Leur principal défaut vient de leur incapacité à détecter une attaque qui ne fait pas partie de la liste prédéfinie. En d’autres termes, ces approches n’offrent aucune une résistance aux nouvelles attaques.

Le deuxième type d’approches repose sur la détection d’anomalies (ou comportements atypiques). Avec une première phase d’apprentissage (généralement de la fouille de données), ce type de méthode établit une base de connaissances sur les comportements « normaux ». Dès qu’un comportement s’écarte trop de ceux enregistrés dans cette base, il est considéré comme anormal ou atypique. Bien entendu, tous les comportements atypiques ne sont pas malveillants. Si un comportement atypique est, à tort, considéré comme une attaque et lève le déclenchement d’une alarme, alors on dit qu’il s’agit d’un faux positif (ce qui correspond d’ailleurs à une fausse alarme…). La difficulté de mise en œuvre de ces approches est bien entendu liée à l’ensemble d’apprentissage qui doit être suffisamment exhaustif pour être capable de déterminer quels sont les comportements normaux. Ainsi l’application de ces méthodes dans un contexte réel est difficile car le nombre d’alarmes générées est trop important. Ce domaine est donc un sujet très étudié à l’heure actuelle. L’objectif principal des travaux menés est la réduction du nombre de faux positifs dans la détection d’anomalies tout en garantissant la détection de toutes les vraies attaques (y compris les nouvelles). Ceci permettrait de dépasser la technologie des approches par misuse.

Cette maîtrise du nombre de faux positifs est l’objectif du projet MUTAN. Pour cela, nous envisageons de faire collaborer les systèmes à surveiller avec l’idée qu’une majorité de comportements malveillants est partagée par les différents systèmes. Dans la description scientifique, nous détaillerons cette idée et nous présenterons le principal verrou technologique soulevé par notre proposition.

 

La durée du projet MUTAN est de 1 an.

2. Equipes Concernées

EPI AxIS – INRIA Sophia Antipolis – Méditerrannée

 

L’EPI AxIS est basée sur une approche multi-disciplinaire pour l’analyse, la conception et  l’amélioration des systèmes d’information. Les techniques développées font appel à des compétences en intelligence artificielle, fouille de données ou encore génie logiciel. Ces compétences complémentaires sont nécessaires pour atteindre nos objectifs principaux: 1) développer des méthodes et outils pour aider à la fois à l’analyse d’un SI et à celle de son utilisation 2) aider à la validation, la maintenance et l’amélioration de SIs. Actuellement nous travaillons sur les SIs basés sur le Web et les NTIC.

Dans le cadre de cette action Color, nous souhaitons utiliser nos compétences en fouille de données afin de répondre à un des prérequis de nos objectifs scientifiques : la détection d’anomalies.

 

Participants :

• Florent Masseglia (CR1 Inria). Thèmes de recherche : Découverte de motifs, Détection d’anomalies, Fouille des usages du Web.
• Céline Fiot (Post-doc Inria AxIS). Thèmes de recherche : Extraction de motifs séquentiels, Fouille de données floue, Valeurs manquantes.

 

Equipe KDD – LGI2P – Nîmes

 

Les travaux menés par le projet KDD (Knowledge Discovery for Decision making) concernent l’extraction et la visualisation de connaissances à partir de grandes bases de données. Parmi les différentes techniques d’extraction, nous nous sommes intéressés ces dernières années à la détection de motifs séquentiels afin de rechercher des comportements typiques. Ces techniques ont été utilisées dans différents domaines d’application tels que le Web Usage Mining, le Text Mining. Afin de prendre en compte ces applications, nous avons également étendu les approches traditionnelles pour pouvoir gérer de nouveaux types de contraintes (données réparties, données disponibles en temps réel, données inattendues, …). Dans le cadre de cette action Color, nous souhaitons collaborer avec le projet AxIS afin d’exploiter nos travaux en fouille de données préservant la vie privée (privacy preserving data mining / fouille de données confidentielle) dans le cadre de la détection d’anomalies.

 

Participants :

• Pascal Poncelet (Professeur). Thèmes de recherche : Extraction de motifs séquentiels, Détection de fraudes, Text Mining, Data Stream, Préservation de la vie privée
• Gérard Dray (Enseignant Chercheur). Thèmes de recherche : Clustering, Flou, Détection de fraudes, Text Mining.
• François Trousset (Ingénieur de Recherche). Thèmes de recherche : Préservation de la vie privée et Extraction collaborative

3. Descriptif scientifique

 

Optimiser le taux de détection des méthodes de détection d’intrusions basées sur les anomalies consiste principalement à améliorer deux indicateurs :

-         Les faux positifs. Il s’agit des fausses alarmes. Leur nombre doit être le plus faible possible.

-         Les faux négatifs. Il s’agit de véritables attaques/intrusions qui n’ont pas été détectées. Leur nombre doit être le plus faible possible.

 

Notre objectif est d’optimiser ces indicateurs et d’appliquer nos propositions à la détection d’intrusions sur des sites Web. L’idée principale de notre projet se base sur plusieurs observations :

1.      Les systèmes d’information reposent sur un nombre limité d’architectures possibles. Par exemple pour un site Web, il peut s’agir principalement de Apache ou Microsoft IIS (les deux principales architectures de serveurs Web). Pour schématiser on peut également dire que pour une base de données, ce sera IBM DB ou Oracle et pour un système d’exploitation ce sera Linux, Windows ou Mac OS…

2.      Les attaques/intrusions qui fonctionnent sur un système d’information sont en majorité reproduites sur d’autres systèmes avec la même architecture. Par exemple, sur un serveur Web Microsoft, quand une faille est trouvée, elle est diffusée, améliorée et reproduite. Ainsi, les attaques qui fonctionnent se propagent et sont réutilisées d’un site à l’autre.

3.      Avant qu’une attaque soit détectée, comprise et validée dans les bases de signatures des IDS commerciaux, il s’écoule assez de temps pour que de nombreux sites en soient victimes.

 

Dans la section 3.1 nous présentons un tour d’horizon des méthodes existantes pour la détection d’anomalies et dans la section 3.2 nous proposons notre approche pour minimiser les faux négatifs en se basant sur les observations précédentes.

 

3.1 La détection d’anomalies

La détection d’anomalies est un thème de recherche qui fait appel à la fouille de données pour aider à sécuriser un système d’information. Pour préciser la description faite en section 1, nous pouvons dire que la détection d’anomalies se décline en plusieurs approches.

 

Les méthodes à base de classifieur.

Il s’agit d’apprendre (training) les comportements normaux et anormaux (qui sont donc étiquetés) et construire des modèles pour les deux types de comportements. Ensuite en phase de détection, les nouveaux comportements sont comparés aux modèles existants pour décider s’il s’agit d’un comportement normal ou anormal (Münz et al., 2007 ; Fawcett et al., 1997 ; Gomez et al., 2001).

 

Les méthodes de détection des comportements atypiques (outliers).

Il s’agit de construire des modèles correspondant à tous les usages normaux passés (généralement avec des techniques de regroupement ou clustering). Ensuite, les nouveaux comportements sont comparés à ces modèles et ceux qui s’en éloignent trop (outliers) sont considérés comme atypiques (Friedman et al., 2007 ; Last et al., 2001). Dans (Joshi et al., 2001) les auteurs proposent également de détecter les classes de comportements les plus rares, ce qui peut s’approcher de la notion d’outlier.

 

Les méthodes basées sur un critère expert.

Il s’agit d’extraire des motifs dans les comportements qui correspondent à un critère spécifié par l’expert. Par exemple les motifs qui ont une fréquence élevée sur une période très courte sont typiques des attaques DDoS. Une attaque DDoS correspond à la synchronisation de plusieurs machines qui envoient ensemble des messages lourds à un serveur de mails afin de le faire saturer et l’empêcher de fonctionner normalement. Ces attaques génèrent donc un motif fréquent (titre et taille du message) sur une période courte (la durée de l’attaque).

L’EPI AxIS a récemment proposé l’algorithme DeiCo (Saleh et al., 2008) qui permet de découvrir les motifs qui ont un support élevé de manière très localisée (rapprochée dans le temps) et donc d’extraire des comportements correspondant à ce type de critère expert.

 

Verrou technologique : diminuer le nombre de faux positifs.

Toutes ces méthodes (à base de fouille de données) partagent le même inconvénient : elles génèrent un grand nombre de fausses alarmes. Il est, en effet, très difficile de trouver les bons critères pour dessiner la frontière entre les comportements atypiques et les comportements malveillants. Notre proposition dans ce sens est détaillée en section 3.2.

 

3.2 Approche envisagée

 

Notre approche se base sur les observations mentionnées en début de section (partage des architectures entre systèmes d’information et reproduction des attaques d’un système à l’autre). Quand un trop grand nombre de comportements suspects est généré pour un système A, alors ces comportements ne sont pas exploitables pour générer des alarmes, même si une véritable attaque fait partie de ces comportements suspects. En revanche, quand un comportement suspect est partagé par deux systèmes A et B, alors notre heuristique se base sur les points suivants :

1. Il est très peu probable que ce comportement soit une navigation atypique « normale » du site A et du site B à la fois. Par exemple un comportement atypique mais « normal » sur le site Web du centre Inria de Sophia ne peut pas se retrouver sur le site Web du LGI2P (les structures des sites sont différentes, les noms des rubriques également, etc.).
2. Il est très probable que ce comportement soit malveillant. Par exemple une recherche de faille de sécurité dans le fichier  « win32.exe » sera la même sur les deux sites Web. Si un tel comportement atypique est partagé par les deux sites alors il s’agit très certainement d’une attaque.

 

En d’autres termes, puisque les attaques se propagent d’un système à l’autre :

-         On doit les retrouver dans les anomalies détectées sur les deux systèmes.

-         Seules les attaques doivent se retrouver dans les anomalies détectées sur les deux systèmes. En se basant sur ces anomalies communes on ne génère probablement aucune fausse alarme et donc on répond au verrou des faux positifs.

 

Notre objectif est donc de mutualiser les anomalies découvertes par plusieurs sites qui collaborent pour se protéger. Cependant, cette solution au verrou technologique des faux positifs et soulève un autre : la confidentialité des données.

 

Verrou technologique : le partage confidentiel des anomalies

Pour que plusieurs systèmes d’informations partagent leurs connaissances (leurs comportements atypiques) il faut leur garantir que les données seront échangées avec un niveau élevé de confidentialité. Partager des informations sans en divulguer le contenu est un sujet récent de la fouille de données, connu sous le nom de privacy preserving data mining.

 

Récemment, de nombreux travaux se sont intéressés à la définition d’algorithmes de fouille de données préservant la vie privée (e.g. (Pinkas, 2002; Clifton et al., 2003)). Ainsi, des approches adaptées à la classification (Du et al., 2004), à la recherche de règles d’association (Evfimievski et al., 2004) et au clustering (Jagannathan et al., 2005) permettent d’extraire de la connaissance tout en respectant la contrainte de la vie privée. Par exemple, (Lindell et al., 2002) proposent une nouvelle approche de classification utilisant un protocole de transfert sécurisé, inspiré des SMC (Secure Multi-Party Computation), entre les différentes bases de données. (Vaidya et al., 2002) considèrent une architecture sécurisée composée de deux parties effectuant les opérations avec les différentes bases afin de rechercher les règles d’association. Enfin, une nouvelle architecture garante de la sécurité et particulièrement adaptée aux problèmes de fouille de données a été proposée dans (Kantarcioglu et al., 2002).

 

L’équipe KDD du LGI2P a proposé récemment l’algorithme PRIPSEP pour l’extraction de motifs séquentiels sur plusieurs sources en préservant la confidentialité des données (Kapoor et al., 2006)

 

Dans cette proposition d’action COLOR, la difficulté consiste à extraire les comportements atypiques, ou suspects, (grâce aux techniques développées dans AxIS) et à les comparer sans qu’un site soit obligé d’en divulguer le contenu (grâce aux techniques de fouille de données confidentielle développées dans l’équipe KDD). Les résultats de ces recherches permettront de résoudre les deux verrous technologiques mentionnés dans la proposition d’action MUTAN.

 

Bibliographie :

 

Clifton C., Kantarcioglu M., Lin X., Vaidya J., Zhu M.,  Tools for privacy preserving distributed data mining , SIGKDD Explorations, vol. 4, n° 2, p. 28-34, 2003.

 

Du W., Han Y., Chen S., Privacy-preserving multivariate statistical analysis: linear regression and classification, Proc. of the Fourth SIAM Int. Conf. on Data Mining, p. 222-233, 2004.

 

Evfimievski A., Srikant R., Agrawal R., Gehrke J.,  Privacy-preserving mining of association rules , Information Systems, vol. 29, n° 4, p. 343-364, June, 2004.

 

Fawcett T.and Provost F. Adaptive Fraud Detection. In Data Mining and Knowledge Discovery, 1(3):291-316, 1997.

 

M. Friedman, M. Last, Y. Makoverb, and A. Kandel. Anomaly Detection in Web Documents Using Crisp and Fuzzy-based Cosine Clustering Methodology. Information Sciences, 177(2):467-475, 2007.

 

M. V. Joshi, R. C. Agarwal, and . Kumar. Mining Needle in a Haystack: Classifying Rare Classes Via Two-phase Rule Induction. In ACM SIGMOD 2001.

 

Jagannathan G., Wright R.,  Privacy-preserving distributed k-means clustering over arbitrarily partitioned data , Proc. of KDD 05, p. 393-399, august, 2005.

 

J. Gomez and D. Dasgupta. Evolving Fuzzy Classifiers for Intrusion Detection. In IEEE Workshop on Information Assurance, 2001.

 

V. Kapoor, P. Poncelet, F. Trousset and M. Teisseire. Privacy Preserving Sequential Pattern Mining in Distributed Databases. CIKM’06, Arlington, US, November 2006.

 

Kantarcioglu M., Vaidya J.,  An architecture for privacy-preserving mining of client information , Proc. of the Workshop on Privacy, Security, and Data Mining in conjunction with the 2002 IEEE ICDM Conf, p. 27-42, 2002.

 

M. Last and A. Kandel. Automated Detection of Outliers in Real-world Data. In International Conference on Intelligent Technologies (InTech’01), pp 292-301, 2001.

 

Lindell Y., Pinkas B.,  Privacy preserving data mining , Journal of Cryptology, vol. 15, n° 2, p. 177-206, 2002.

 

G. Münz, S. Li and G. Carle. Traffic Anomaly Detection Using k-means Clustering. In GI/ITG Workshop MMBnet’, 2007.

 

Pinkas B., Cryptographic techniques for privacy preserving data mining, SIGKDD explorations, vol. 4, n° 2, p. 12-19, 2002.

 

B. Saleh and F. Masseglia. Extraction d’Itemsets Compacts. Accepté à la conférence EGC’2008. A paraître.

 

Vaidya J., Clifton C.,  Privacy preserving association rule mining in vertically partitioned data, Proc. of KDD 02, p. 639-644, July, 2002.