IMA5 2018/2019 P42

Présentation générale

Description

Les empreintes de navigateur sont un moyen pour traquer les utilisateurs sans leur consentement, et sans laisser de traces, mais peuvent être également utilisés pour détecter des bots ou pour lutter contre la fraude. Les empreintes sont directement produits par les navigateurs et sont distribués par ces derniers sans autorisation préalable. Des contre-mesures contre le traçage d'empreintes de navigateur existent, notamment pour contourner les contrôles de sécurité contre les bots ou les fraudeurs. Il est ainsi question d'appliquer les avancées récentes de l'apprentissage automatique afin d’augmenter l’efficacité du fingerprinting ainsi que de détecter des cas d'incohérence ou de fraude. La collecte de données et la validation se fera à travers le site web http://amiunique.org .

Objectifs

L'objectif du projet est de mettre en place un algorithme utilisant les techniques du Reinforcement Learning (RL), afin de permettre à des bots informatiques, basés sur Pupetteer et Chrome Headless, ou d'autres technologies, de passer outre les défenses des sites web actuels. Il est ainsi question de permettre à notre bot, a travers un apprentissage basé sur des actions suivis de récompenses, d'apprendre par lui-même les actions nécessaires afin de s'éviter la détection.

Préparation du projet

Choix techniques : matériel et logiciel

Il n'y a aucun matériel particulier à utiliser dans le cadre de ce projet. Il serait néanmoins utile d'avoir accès à un ordinateur disposant d'une puissance calcul conséquente. Les langages de programmation utilisés seront les suivants :

• Javascript pour la mise en place du bot
• Python pour la mise en place des algorithmes de RL

Enfin, nous travaillerons tout au long de notre documentation dans l'environnement OpenAI (Python), qui propose de nombreuses ressources adaptés au Reinforcement Learning.

Liste des tâches à effectuer

Dans le cadre du projet, il est nécessaire de développer des connaissances avancés dans le domaine du Reinforcement Learning, qui constitue une branche à part du Machine Learning. Il est également nécessaire de développer une connaissance de l'état de l'art en terme de défense contre les bots informatiques. Enfin, dans l'objectif de répondre aux buts du projet, nous appliquerons nos connaissances en Reinforcement Learning, en choisissant et adaptant l'algorithme le plus approprié à notre problème. Il est également nécessaire de mettre en place en environnement d'entraînement factice afin de permettre à notre bot de procéder à son apprentissage, sans risquer un bannissement de l'adresse IP depuis laquelle le bot agit.

Calendrier prévisionnel

Nous tenterons dans un premier temps, idéalement dans le premier mois, de se documenter dans les domaines suivants :

• La théorie du Reinforcement Learning et l'implémentation des algorithmes
• L'état de l'art en terme de détection des bots
• L'état de l'art en terme d'implémentation de bots informatiques

Durant les mois suivants (Mi-Octobre 2018 - Décembre 2018), les objectifs seront :

• Mise en place de l'environnement d'expérimentation des bots implémentés
• Mise en place des algorithmes à utiliser
• Amélioration des algorithmes mise en place.

Enfin, les derniers mois seront consacrés aux tests et aux comparaisons entre différentes techniques utilisés.

Réalisation du Projet

Semaine 1

La première semaine à permis de mettre au clair les objectifs du projet et de définir le moyen de procéder afin d'atteindre notre but, à savoir : l'utilisation d'algorithmes de Reinforcement Learning afin de rendre notre bot indétectable.

Ainsi, j'ai pu me pencher en grande majorité sur l'état de l'art actuel en terme de détection de bots informatique. En extrayant les informations récupérés pour chaque sessions, plusieurs règles peuvent être déterminés et mènent à une détection plus ou moins probable du bot :

• [BLOG OR BOT](http://cs229.stanford.edu/proj2017/final-reports/5240610.pdf) Détection de bots informatique basés sur les mouvements de la souris et des touches utilisées. Cette solution produit un taux de 99.7% de TPR (True positive Rate) et seulement 0.2% de FPR (False Positive Rate).

• La durée de la session : une session est définie du moment qu'un agent accède au site internet (détecté par son IP, ou son empreinte) jusqu'à l'inactivité (?) de celui-ci.

• Le nombre de requêtes réalisés : un utilisateur normal tend à réaliser un nombre de requête significativement inférieur au nombre de requêtes réalisés par un bot.

• Le pourcentage de requêtes HTML : à définir

• Le nombre de requêtes sans la présence du header http referer : le header http referer contient l'adresse de la page précédente visité, menant à la page actuelle (par la présence d'un lien). Cet en-tête n'est pas défini dans le cas ou la resource précédente est représentée par une URI de type data ou si un différent de protocoles de sécurité existe entre les pages(de HTTPS à HTTP). Un pourcentage important de bots tendent à ne pas définir cet en-tête, ou a ne pas le définir correctement. A noter que les humains peuvent également désactiver cet en-tête.

• Pourcentage d'images récupérés : les bots tendent à ignorer les images.

• Pourcentage de requêtes PDF : Les bots tendent à les demander en totalité tandis que les humains tendent à selectionner leur utilisation.

• Utilisation du header HEAD : Le header HEAD est *parfois* (?) utilisé par les bots afin d'obtenir moins de données du site web. Le header HEAD permet de demander au site les headers qu'il aurait renvoyé dans le cas d'une requête GET classique. Un humain tend à ne presque jamais passer par la requête HEAD.

• Pourcentage d'erreurs 4xx : Les bots tendent à disposer de ce pourcentage plus élevé, en raison du fait qu' un bot tend à tenter d'accéder à des ressources sans en connaitre le contenu.

• Demande du robots.txt : un humain ne demande pas le robots.txt

• Pourcentage de requêtes HTTP sequentielles : les humains tendent à disposer d'un pourcentage plus élevés en raison d'une demande moindre pour des ressources de type script, images, doc...

• Standard deviation of requested page's depth. <--- Pas compris, a developper

• Adresse IP : Une utilisation intensive d'une adresse IP disposant des précédents attributs est douteuse.

J'ai également pu me renseigner sur l'état de l'art en terme de technologie utilisée dans la mise en place de bots : Chrome Headless est devenue la norme afin de mettre en place des bots ayant le moins de chance de détection. Un environnement headless représente un environnement sans GUI. Chrome headless est ainsi une "variante" du navigateur chrome, sans interface utilisateur, et ainsi, plus axée pour le testing automatisé, le développement de bots destinés au web crawling, ou toute sorte d'application ou la présence d'un GUI n'est pas requise. Puppeteer est la librairie Node officielle utilisant Chrome Headless afin d'exploiter le contenu de pages web.

Enfin, je poursuis mon étude des algorithmes de Reinforcement Learning : j'ai pu voir jusqu'à présent les algorithmes utilisés en Dynamic Programming. Ces algorithmes nécessitent la connaissance préalable de toute la MDP (Markov Decision Process), à savoir, une connaissance de toutes les valeurs associée à une action prise. Un environnement proche de la réalité bénéficie très rarement de cet avantage. En général, nous cherchons à déterminer les meilleures actions en explorant plusieurs différentes paires état-actions, qui risquent de présenter un meilleur avantage sur le long terme.

Semaine 2

J'ai pu, durant cette semaine, continuer mon apprentissage du reinforcement learning, des algorithmes, formules et notions associés. J'ai ainsi passé en revu la majorité des algorithmes utilisés dans l'état de l'art, à l'exception des algorithmes introduisant des réseaux neuronaux en raison du fait que cette approche ne pourra être considérée que dans le cas de limitation avérés des approches classiques.

J'ai également pu définir le problème et établir un modèle basique en termes de reinforcement learning, à discuter au cours de la semaine 3 avec mes tuteurs :

• But : Éviter la détection du bot par les systèmes de détection présents.

• Agent : Dans notre cas, un controlleur externe est plus approprié en raison du fait que la tache du bot doit correspondre uniquement à celle prédéfinie. Nous devons également pouvoir dimensionner la solution à plusieurs bots.

• Environnement : Le bot, controllé par l'agent, et son environnement, soit, la liste des sites web à explorer ?

• Action :

   * Changement d'adresse IP
   * Varier le nombre de requêtes dans un même site web
   * Variation des mouvements de la souris et keystrokes
   * Variation de la durée de la session
   * Varier les headers HTTP
   * Varier le pourcentage d'images et de documents récupérés 
   * Varier le taux de requêtes HTTP séquentielles.
   * Varier l'user agent
   * Varier la liste des plugins
   * Une action pour éviter de cliquer sur les liens cachés ?
   * Varier le délai de navigation entre deux pages
   

• États :

   * Possibilité de définir les états par les sites web à visiter.
   * Possibilité de définir les états sur les hyperliens visités dans un même site web.
   * Etat terminal : soit le bot est bloqué, soit nous avons parcours la liste des sites web à visiter.

• Gains : (A développer)

   * +1 Dans le cas d'un site crawlé sans détection. (Le taux de non-detection sera sûrement élevé, on ne prendre donc rarement en compte les gains négatifs. Solution : discounting factor si on décide de partir sur un gain positif)
   * -1 Dans le cas de détection.
   * 0 dans le cas d'une navigation dans un même site web sans détection.

• Politique d'action :

   * Définies par notre algorithme dans le cas de l'utilisation des policy gradient methods.
   * Sinon, on cherche a minimiser la détection, donc optimiser les paramètres permettant de ne pas se faire détection.

Quels sont les possibles algorithmes suites aux conditions précédentes ?

Il est préférable de partir sur un algorithme off-policy dans le cas où nous n'utilisons pas les algorithmes de policy gradient, en raison du fait que nous désirons maximiser l'exploration et l'amélioration de différentes politiques d'actions. Il est également préférable de choisir un algorithme offline afin de mettre à jour les paramètres du modèle seulement à la fin de l'épisode.

• One-step auto-critic algorithm dans le cas ou un épisode correspond au parcours d'un site web, sinon, actor-critic algorithm with eligibility traces.

• REINFORCE with baseline.

• Q-learning car off-line.

• Semi-gradient TD(0)

Semaine 3

Cette semaine à été consacrée à la mise en place de l'environnement de test sous OpenAI Gym. OpenAI Gym est un toolkit permettant le développement et le test d'algorithmes de reinforcement learning. Il a été mis en place dans le but de standardiser les environnements de test, afin de simplifier l'implémentation des algorithmes issues de papiers de recherche. Notre modèlisation est finalement la suivante :

• Un site web est représenté par des features. Soit, la présence de fingerprinting, le fait que le site web bloque les bots ou pas, la présence d'un security provider qui peu être expliqué simplement par un serveur gérant la sécurité d'une multitude de sites web. Un site web dispose également d'un compteur de visite.

• Le security provider est représenté par un numéro, une note, qui va régir ses performances en terme de bloquage. Le security provider bloquera les bot dans un premier temps selon le nombre de fois que l'IP visite le site, ou bien le nombre de fois que l'user agent est apparu.

• Les états sont représentés par les features des sites web, un état contiendra les sites web ayant été visités entre 0 et 50 fois, dont le security provider à été visité entre 50 et 100 fois, disposant de fingerprinting et bloquant les bots.

• Les actions quant à eux correspondent à la visite d'un état particulier, au changement d'IP et au changement d'UA dans un premier temps. Nous aurons ainsi un nombre d'actions correspondant au nombre d'états + 2. Les actions seront à revoir par la suite car ce nombre limite les performances des algorithmes.

• Le bot est représenté par ses caractéristiques classiques, soit, son IP et son user agent en premier lieu. Ces caractéristiques seront améliorés par la suite pour mieux correspondre à la réalité.

L'environnement est développé en python, et disponible sur ce répo git : https://github.com/naifmeh/smartbot

Semaine 4

La semaine 4 à été consacrée à tester différents algorithmes sur la première version de l'environnement.

Nous testons notre environnement sur les algorithmes SARSA, Q-Learning et l'actor-critic (policy gradient methods). Les résultats dans le cas des deux premiers algorithmes sont prometteurs. A noter que dans cette première configuration, nous gardons le même set de sites web pour l'ensemble des épisodes. Las paramètres sont : 1000 steps par épisode, step size de 0.5 et espilon à 0.1 :

• SARSA en introduisant un faible reward négatif dans le cas de visite d'un état sans site web

• Q-learning dans la même configuration :

• Actor-Critic :

A noter également que les gains sont faibles en raison du fait que nous introduisons un gain négatif dans le cas du parcours d'un état vide de sites web.

Semaine 5

La semaine 5 à permis d'écrire de nouveaux algorithmes de RL, ainsi que de réaliser une petite présentation de l'avancement à l'INRIA, où nous avons pu discuter du modèle, des limitations de celui-ci, ainsi que des possibles améliorations. J'ai pu mettre en place les algorithmes n-step SARSA et SARSA(lambda). Le premier introduit une mise à jour des paramètres du modèle en plein épisode, ce qui permet à notre algorithme de mieux généraliser au fur et à mesure des épisodes.

En limitant le gain négatif en cas de visite d'un état vide à -0.1, en introduisant un gain de 5 en cas de crawl réussi, et en réinitialisant la liste de sites web à chaque épisode, nous obtenons de biens meilleurs résultats car l'algorithme est toujours confronté à de nouvelles situations. La configuration précédente introduisait un overfitting, les algorithmes s'adaptaient simplement à la configuration d'une mếme série de sites web. Nous remarquons que les algorithmes Q-Learning et SARSA, qui mettent à jour les paramètres du modèle uniquement à la fin de l'épisode, retournent des résultats très mitigés, tandis que l'actor critic, le n-step SARSA et le SARSA(lambda) montrent des belles performances :

• N-Step SARSA :

• SARSA(lambda) :

• Actor-Critic :

Après discussion lors de la présentation, nous avons pu mettre en avant les limitations du modèle : il est ainsi très difficile, dans le monde réel, de déterminer si un site web utilise le fingerprinting, à quel security providers plusieurs site appartiennent, et d'autres caractéristiques clés de notre modèle.

Ainsi, nous avons décidé de réaliser un second modèle utilisant comme états les configuration du bot. Chaque état correspond ainsi à une configuration précise du bot, à savoir, un user-agent, un proxy, le fait que le bot utilise ou non le header REFERER, ou le header HEAD, le taux de chargement des images et documents, qui va influer sur le temps de chargement des pages, que l'on cherche a minimiser.

Semaine 6

La semaine de pause m'a permis de mettre en place le nouveau modèle, toujours dans un environnement factice, utilisant comme états les configuration du bot. Comme annoncé, les états sont représentés par :

• L'user-agent
• Le proxy
• L'utilisation du header REFERER
• L'utilisation du header HEAD
• Le taux de chargement des images
• Le taux de chargement des documents (PDFs, etc...)

Les actions quant à eux sont les suivantes :

• Changer l'UA
• Changer le proxy
• Changer le referer
• Changer le header HEAD
• Changer de site web
• Augmenter/Diminuer le taux de chargement d'images

PHOTOS RESULTATS

A première vue, ce modèle paraissait être le plus apte à être reproduit dans un cas réel. Cependant, après test avec les différents algorithmes implémentés jusque la, les résultats en ressortant sont très mitigés : nous retrouvons un taux de réussite qui progresse jusqu'à 60% en moyenne et dans les 80% dans le meilleur des cas. Nous souhaitons un système qui soit plus fiable et ne présente pas une variance aussi importante. La raison du non fonctionnement de ce modèle est notamment le nombre très elevés d'états générés, qui est de l'ordre de 10^6, et du nombre d'actions (car je considère les combinaisons d'actions élementaires également), à 10^3. Ces modèles introduisant un nombre élevé d'état nécessitent des algorithmes de RL plus poussés: les algorithmes de Deep Reinforcement Learning (DRL) sont plus appropriés, mais nécessitent une puissance de calcul élevée. Nous implémenterons ces algorithmes lorsque notre modèle sera assez fiable.

Au vu des mauvais résultats, nous changeons une nouvelle fois de modèle et passons à un modèle plus simple, que nous améliorerons par la suite. Les états de ce modèle introduisent quelques caractéristiques de sites web facilement extraites, ainsi que deux caractéristiques du bot :

• Le fait que le site web bloque les bots
• Le fait que le site web utilise du fingerprinting
• L'intervalle de visite d'un site
• L'intervalle d'utilisation d'un UA
• L'intervalle d'utilisation d'un proxy

Les actions quant à eux sont représentés par :

• Choix d'un UA
• Choix d'un proxy
• Choix d'un site web
• Ne rien faire (maintenir la configuration)

J'ai également mis en place un crawler utilisant Puppeteer et Chrome Headless, afin de pouvoir récupèrer des informations détaillés sur certains proxies, à partir de la page : [[1]] .

L'objectif pour la semaine prochain est d'introduire notre modèle dans le cas réel et de le déployer sur les serveurs pour un test.

Documents Rendus

• Git du projet : https://github.com/naifmeh/smartbot