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

Les résultats pour les algorithmes QLearning et SARSA sont représentés par les graphiques suivants :

• QLearning pour un épisode de 1000 étapes. Le gain maximal est de 3000 car les rewards sont fixés à 3 pour un crawl réussi :

Le barplot, qui est plus explicite :

Nous pouvons ainsi voir que l'algorithme parvient à progresser et à se stabiliser aux alentours de 60% de crawls réussis (en ne comptant les sites non crawlés durant l'épisode.

• Sarsa dans les même configurations que précédemment :

Le barplot :

Les résultats sont similaires à précédemment, à l’exception que dans le cas de l'algorithme SARSA, nous commençons les premiers épisodes avec un reward très négatif. Cela peut s'expliquer par le fait que SARSA soit un algorithme on-policy et suivra ainsi une même policy tout le long de l’exécution tandis que le QLearning, étant off-policy, privilégieras l'exploration.

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 élevé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 élémentaires é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.

Semaine 7

L'objectif pour cette semaine était de finaliser le modèle précédent et de le tester, pour ensuite mettre en place le test en conditions réelles. J'ai pu finaliser le modèle, qui montre des des résultats assez mitigés une nouvelle fois. Nous pensons cependant que les raisons des résultats mitigés restent en grande partie dû au fait que nous sommes dans une modélisation, qui reste assez lointaine des conditions réelles. Nous pensons également qu'en modifiant un peu le dernier modèle, nous pouvons tester en conditions réelles. Les états sont légèrement modifiés pour contenir des informations plus détaillés sur les sites web :

• Le site vérifie-t-il le taux de chargement de documents ?
• Le site utilise-t-il le fingerprinting ?
• Le site vérifie-t-il la taille de l'écran ?
• Nombre de visites du site ? (Du coté du bot, plus c'est elevé, plus on privilégie le changement)
• Le site bloque-t-il les bots ?
• Le site verifie-t-il les plugins ?
• Le site analyse le pattern de la souris/clavier ?
• Le site vérifie les IPs/UAs ?
• Nombre de fois que notre IP à été utilisée
• Nombre de fois que notre UA à été utilisée

Du coté d'un épisode, un changement est a noter : un épisode est considéré comme toutes les visites de liens d'un même domaine, jusqu'à la fin de ceux-ci, ou le blocage.

Les actions ne changent pas. Nous ajoutons simplement l'action d'ajouter/supprimer un plugin.

Je suis ainsi en train d'écrire le programme de test. Le langage de choix est le Javascript sous NodeJS, en raison du fait que le crawler utilisera Chrome Headless et Puppeteer, et ce dernier ne dispose que d'une API en javascript. Il est ainsi plus raisonnable d'éviter de jongler entre les langages. Ne connaissant pas ce langage, je suis actuellement en train de parcourir la documentation du langage ainsi que la documentation de l'API.

Semaine 8

Cette semaine à été consacrée à l'écriture du code permettant de tester notre modèle en temps réel. Comme annoncé lors de la précédente semaine, le langage utilisé sera le Javascript sous NodeJS. La raison du choix de Javascript porte sur le fait que toutes les librairies permettant de réaliser des crawlers sont écrites en Javascript (à l'éxception de certaines d'entre eux). Ne connaissant absolument pas le langage et ses particularités, j'ai dû prendre quelques jours afin de me documenter et apprendre sur le langage au fur et à mesure que j'écrivais le programme principal. J'ai ainsi pu découvrir l'asynchronisme de Javascript, en utilisant la syntaxe ES6 (async/await), disponible depuis Node v7.0, et en évitant le plus possible les callbacks. L'asynchronisme est un atout dont nous pouvons profiter pour notre programme afin de pouvoir réduire le temps d’exécution, et notamment le temps d’exécution de la phase de pré-processing. Le gain en rapidité est fortement marqué par rapport au langage Python.

Le programme est organisé en modules et prend avantage des nombreux librairies déjà disponibles par commande npm. J'ai tenté de faire en sorte que le programme soit le plus modulaire possible, en divisant toutes les tâches dans différents modules réutilisables. La librairie Winston me permet de gérer les logs d'éxecution, tandis que j'utilise Chaï et Mocha pour les tests unitaires.

Description du fonctionnement du programme

• Phase de pré-processing :

La phase de préprocessing me permet de générer les différents attributs de chaque site web à crawler, ainsi qu'a générer les différents liens que notre bot visitera. Dans le premier cas, durant le temps de mettre en place le script, je dispose déjà d'une base de donnée de plus de 10000 sites web dont les attributs sont déterminés, et qui m'a été fournie par Antoine. Cette liste est stockée dans un document mongodb. J'ai ainsi mis en place un module me permettant de récupérer les différents éléments de la collection. Je dispose également d'un fichier csv fourni encore une fois par Antoine, déterminant si le site web utilise le fingerprinting, ou bloque les bots. La génération des liens se fait simplement en générant le sitemap du site web et en choisissant un nombre limité de liens. La phase de pré-processing permet ainsi de combiner les trois opérations précédentes, à savoir, la lecture de la BDD, la lecture et l'interpretation du fichier csv, et la génération du site map, en un objet javascript contenant les attributs suivants pour chaque site web :

   { 'hostname': {
                  urls: ['url1', 'url2'],
                  hostname: 'hostname',
                  fingerprinting : boolean,
                  screen_size: boolean,
                  block_bots: boolean,
                  mouse_pattern: boolean,
                  plugins: boolean,
                  ua_proxy: boolean,
                  visits: integer,
                  uas: [{'ua1':integer}, {'ua2': integer}],
                  ips: [{'ip1':integer}, {'ip2': integer}] 
                  },
    'hostname2':....
   }

Nous obtenons ainsi un objet JSON contenant plusieurs objets JSON dont les attributs sont représentés par des booléens. True pour un attribut vérifié, false pour le contraire. Le choix des objets JSON est important car il nous sera plus facile à sérialiser dans le cas où nous souhaiterons interrompre le programme et repartir du même endroit.

Nous générons également les états, qui ont été définis la semaine précédentes et qui seront surement modifiés encore une fois par la suite pour disposer de plus d'attributs. Actuellement, nous nous retrouvons avec 31800 états, ce qui est acceptable et laisse de la marge pour l'ajout d'autres états.

• Épisode :

Une étape fait partie d'un épisode. Le nombre d'épisodes sera défini à l'avance. Pour le moment, nous définissons un épisode comme le crawl d'un site web et de l'ensemble de ses urls. L'épisode se termine soit pas le bloquage du bot, soit par la visite de toutes les urls disponibles.

Le diagramme d'exécution pour un épisode est le suivant :

L'écriture du programme est encore en cours. Les actions n'ont pas encore été codés et la sérialisation n'a toujours pas été abordée. Le but de la semaine qui vient est ainsi de clore ces derniers points.

Documents Rendus

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