Apprentissage non-supervisé appliqué à l’analyse de logs de proxy

De façon à rentrer de plein pied dans le monde du Machine Learning, nous souhaitons partager une compréhension commune des principes de l’apprentissage automatique, et expliquer au travers d’une série courte de billet ce qu’est l’apprentissage supervisé et non-supervisé avec des applications ainsi que les moyens d’évaluer un modèle en apprentissage automatique.

Ce billet est pour l’essentiel une republication sur ce blog du billet éponyme déjà publié sur le blog MSDN Big Data France .

Je vous souhaite une bonne lecture de ce billet

--Philippe

_________________________________________________________________________________________

Dans ce billet, nous allons nous intéresser à un cas particulier d’application des méthodes d’apprentissage non-supervisé, à savoir comme le titre l’indique, l’analyse de logs de proxy.

Comme les concepts évoqués ne sont pas familiers pour la plupart des personnes, nous avons préféré commencer par expliquer ces algorithmes sur un exemple d’application concret avant d’aborder la théorie dans un prochain billet. Les outils utilisés pour cette étude sont R et Excel. Pour l’outillage à proprement parler sur R, vous pouvez vous référer au billet précédent publié sur ce blog.

L’apprentissage non-supervisé, de quoi s’agit-il ?

Comme nous l’avons abordé un récent billet, on parle d’apprentissage non-supervisé lorsque les données sur lesquelles on travaille ne sont pas labélisées, c’est-à-dire qu’il n’y a pas d’indication concernant l’attribut à prédire.

Les algorithmes d’apprentissage non-supervisé sont un peu à part en apprentissage automatique (Machine Learning) dans la mesure où ils ne permettent pas de faire des prédictions comme on pourrait s’y attendre.

Ils se servent de la distribution des données d’entrées pour partitionner ces données en groupes homogènes aussi appelés classes ou clusters. Certains de ces algorithmes servent à détecter des éléments anormaux dans les données aussi appelés outliers. Enfin, d’autres permettent de faire de la réduction de dimensions comme nous le verrons plus loin.

Position du problème

Dans une entreprise x, toutes les connexions à internet sont centralisées pour des raisons de sécurité sur une même machine, appelée serveur proxy. De la même manière, les connexions venant de l’extérieur sont envoyées au proxy, qui redirige l’information à la personne concernée.

Ainsi, le proxy est capable de filtrer le contenu suspect comme les virus et les vers.

Toutefois, ce n’est un secret pour personne, le travail de filtrage effectué s’avère difficile, et il existe des failles que des personnes mal intentionnées du web peuvent exploiter.

Vu qu’il est impossible de bloquer tout le contenu suspect, il serait intéressant de détecter le plus tôt possible qu’une intrusion est en cours pour réagir : c’est là qu’intervient le Machine Learning.

L’analyse de logs relève pour le moment des experts en sécurité, mais nous allons donner ici quelques pistes sur ce que peut apporter le Machine Learning à ce domaine.

Les données d’entrée : les logs

Les logs de proxy recensent l’historique des connexions et sont stockés dans un fichier texte de préférence au format Weblog (W3C Extended Log), où chaque ligne correspond une connexion avec de nombreuses caractéristiques : date de la connexion, heure de la connexion, IP client, navigateur…

Concernant notre analyse, nous nous limitons aux caractéristiques suivantes :

Nous allons maintenant essayer d’appliquer des algorithmes de Machine Learning sur ces logs. Nous ne savons pas a priori quel log peut être considéré comme suspect, ou tout du moins cela ne fait pas l’objet d’un attribut dans l’historique. A partir des données d’entrée, il nous faut deviner ce qu’est un comportement suspect…

Choix des features

Notre but est ici de cibler les utilisateurs qui ont un comportement suspect, et donc ont des "chances" d’être infectés ou d’avoir le contexte de sécurité utilisé à leur insu.

Comme nous ne disposons pas de labels nous indiquant sur l’historique si une connexion est suspecte ou pas, nous allons donc devoir commencer par considérer qu’une machine infectée est à l’origine d’un nombre de connexions important en dehors des heures "normales" de travail.

Pour cibler ces profils, nous allons donc caractériser un utilisateur par son nombre de connexions et sa quantité d’informations envoyées (upload) en dehors des heures de travail. Nous réalisons donc un prétraitement des données afin d’obtenir les informations sous la forme suivantes :

Nous allons maintenant appliquer des algorithmes de Machine Learning afin d’identifier des éléments suspects dans ces données.

Utilisation d’une méthode de clustering : k-means

Détail

Etant donné un nombre de classes prédéfini, l’algorithme des k-moyennes (k-means) prend en entrée un jeu de données non-labélisé, et affecte à chaque élément une classe. Pour chaque classe, on définit un élément comme le centre ; celui-ci sera déterminé par l’algorithme. La répartition se fait en respectant les règles suivantes :

• La distance entre les éléments d’une même classe et leur centre est minimale
• La distance entre les centres de chaque classe est maximale

Cette illustration devrait aider à visualiser ce que fait k-means.

Nous rappelons qu’une distance est une mesure de similarité entre les données.

Si on considère deux éléments x₁ et x₂, alors on peut choisir la distance d(x₁, x₂,) comme la distance dite euclidienne :

où p est le nombre de dimensions des éléments.

Application

Nous allons appliquer l’algorithme de K-means sur nos données en choisissant la distance euclidienne comme mesure de similitude. Cet algorithme va diviser les données en plusieurs classes contenant des éléments proches entre eux. En appliquant cet algorithme sur les données, on obtient pour 3 classes :

De cette manière, il est possible de cibler les éléments suspects comme étant de la classe verte.

Il est possible d’obtenir des résultats plus fins en ajoutant l’attribut navigateur à la liste des features. On obtient alors les résultats suivants pour 2 classes :

Ici, les éléments suspects sont ceux de la classe rouge.

Utilisation d’une méthode de détection d’anomalies : LOF (Local Outlier Factor)

Contrairement à l’algorithme k-means qui demande d’interpréter les données, cet algorithme renvoie une liste d’éléments anormaux ou outliers.

Pour chaque élément, l’algorithme calcule les distances entre cet élément et ses voisins. A partir de ces distances, on en déduit une mesure de la densité autour de cet élément. Plus la densité est élevée, plus il existe un grand nombre d’éléments proches autour de celui-ci. Les éléments avec la densité la plus faible sont considérés comme outliers. Pour des raisons de commodité, ce n’est pas la densité qui est renvoyée par l’algorithme mais un score appelé LOF (Local Outlier Factor) qui est affecté d’une valeur importante pour un outlier.

Dans notre cas, il est possible de sélectionner les 10 premiers outliers (ceux ayant le plus haut score LOF) :

Autre choix de features

Un comportement suspect peut aussi se repérer lors des heures de travail. Une idée qui vient à l’esprit est de représenter un utilisateur par son nombre moyen de connexion par heure. Ainsi, le profil d’un utilisateur peut être visualisé de la manière suivante :

Utilisation d’une méthode de réduction de dimensions : l’analyse en composantes principales pour la visualisation (ACP)

Chaque utilisateur est ici caractérisé par 24 composantes. Il n’est donc pas possible de visualiser la répartition de plusieurs utilisateurs dans un plan à 2 dimensions. Dans ce cas, on opte souvent pour une méthode de réduction de dimensions relevant de l’apprentissage non-supervisé : l’analyse en composantes principales ou ACP (Principal Component Analysis ou PCA en anglais).

L’ACP consiste à trouver, à partir des autres dimensions, celles qui caractérisent le mieux les données. Sans rentrer dans les détails qui dépassent le cadre voulu pour ce billet, l’ACP permet de remplacer des éléments représentés par 24 composantes par les mêmes éléments représentés par un nombre de composantes déterminé (ici 2) appelées composantes principales.

Après avoir effectué l’algorithme LOF sur les nouvelles données et en ayant projeté ces données dans l’espace des deux premières composantes principales, la visualisation donne :

Grâce à cette analyse en composantes principales, on visualise aisément les outliers, dont certains sont identifiés sur le graphe par leurs scores LOF 3331, 2375, 1851.

Nous espérons que ce billet vous aura donné quelques idées sur la façon d’aborder ce type de problématique.