Frères Peyronnet

Veille technologique & Référencement web

Mardi

12

octobre 2010

0

COMMENTAIRES

Marche aléatoire et détection de spam…

Ecrit par , Publié dans Théorie

Un article heureux est un article partagé !Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedIn

Aujourd’hui je vais vous parler d’un résultat que nous avons obtenu récemment. Nous ? je parle ici de mon chanceux thésard (mais oui, chanceux) Thomas Largillier et moi même. Je vous vois venir, vous pensez que je suis un peu vaniteux de la croire chanceux car il a un super directeur de thèse, mais vous vous méprenez, il est chanceux car il soutient très prochainement ;)

Bref, je vais vous parler de l’article suivant :
Using patterns in the behavior of the random surfer to detect Webspam beneficiaries.

Thomas Largillier and Sylvain Peyronnet.

Auparavant, on s’était intéressé au déclassement du spam sans le détecter, ici au contraire on veut explicitement détecter des structures de linking élaborées pour booster le pagerank (c’est-à-dire des fermes de liens évoluées). Pour les amis SEO qui me lisent et qui avaient assisté à mon exposé au premier seocampus, j’avais dit que c’était une tâche impossible à réaliser, mais il s’avère que c’est impossible de façon exacte, mais faisable de manière statistique et probabiliste.

La méthode que je présente ici a donc pour but d’identifier des structures malicieuses au sein des pages web. L’intuition est la suivante : pour booster le pagerank d’un page donnée, les spammers vont créer une architecture dont le but est d’être la plus discrète possible, c’est-à-dire de faire circuler le pagerank autour de la cible pour le ramener le plus vite possible sur cette même cible. Si l’on considère la définition du pagerank comme la probabilité qu’à un moment donné un surfeur aléatoire soit sur une page, alors il semble qu’en utilisant des marches aléatoires et en estimant la probabilité d’être sur une page particulière à tout moment, on devrait pouvoir trouver les structures crées par les spammeurs.

A l’origine notre idée était de créer un vecteur qui donnait les statistiques d’apparition de chaque page au cours d’une marche aléatoire (par exemple, si la page p_{1} apparait 2 fois dans une marche de longueur 10, alors la composante du vecteur qui correspond vaut 2/10. Ensuite, le vecteur crée était comparé à des vecteurs représentant des fermes de liens connues, et si il y avait correspondance, alors cela signifiait que l’on avait trouvé un objet louche (=du spam). Mais il s’avère qu’au final cela ne permet pas de détecter le spam. Nous avons donc fait deux modifications :

  1. Au lieu de calculer des statistiques sur l’apparition des pages, nous calculons des statistiques sur l’apparition de motifs de plusieurs pages (2 pages sont suffisantes pour commencer à obtenir un pouvoir de détection significatif). Dans le cas de ce motif de taille 2, on regarde donc combien de fois on passe d’une page X à une page Y.
  2. Mais surtout, on va fusionner les pages par rapport à la distance à la page d’origine de la marche aléatoire. Cela va avoir un effet majeur : cela rend la méthode robuste au changement dans la ferme de liens (sinon, pour casser la détection il suffisait de modifier la structure en dupliquant des pages choisies au hasard).

Voici maintenant une description en textes et images.

ETAPE 1

On prend le graphe du web que l’on considère (ici un petit web avec seulement 10 pages, mais on ferait pareil avec plus), voici à quoi cela ressemble :

Fig1

ETAPE 2

Au voisinage de la page qui va nous servir de point de départ (typiquement une page que l’on soupçonne d’avoir un trop bon linking pour être honnête), on va changer le graphe en remplaçant les noms de page par les distances à la page d’origine. Pour le graphe de l’exemple, cela donne le résultat suivant :

Fig2

ETAPE 3

On calcule le vecteur de fréquence pour chaque motif de taille 2 sur une marche aléatoire de taille fixe (par exemple 17 ici). Qu’est ce que cela veut dire ? Que je vais faire les 2 étapes suivantes.
D’abord, je vais suivre les liens de manière aléatoire (comme le surfeur du même nom) et marquer dans un tableau les distances que je croise, par exemple 0 puis 1 puis 2 puis 3 puis 3 puis … (en l’absence de lien sortant, je vais en arrière). Imaginons donc que je fasse une marche aléatoire de taille 17, j’obtiens par exemple :

0 1 2 3 3 2 1 1 0 1 2 3 3 1 0 1 2

L’étape suivante est de calculer le fameux vecteur de statistiques sur la marche aléatoire. On va construire un tableau dont chaque colonne correspond à un motif de taille 2 dans la marche aléatoire (sur les distance, donc ’01’, ’12’, etc.) et on va calculer la fréquence d’apparition de chaque motif. Pour l’exemple on obtient :

00 01 02 03 10 11 12 13 20 21 22 23 30 31 32 33
0 3/16 0 0 1/8 1/16 3/16 0 0 1/16 0 1/8 0 1/16 1/16 1/8

ETAPE 4

On compare le vecteur obtenu (que l’on appelle vecteur ustat) à ceux obtenu en faisant la même manip sur des fermes de liens connus, du type de ce que j’ai dessiné en dessous :

Pat1

Pat2

Si les vecteurs sont proches (je ne m’étendrais pas sur la manière ce calculer la distance), c’est à dire pas forcément égaux mais presque, alors cela signifie que les structures sont proches (pas forcément les mêmes, mais quasiment). Si je m’intéressais à des fermes de liens, cela veut donc dire que j’ai trouvé des structures proches des fermes de liens, c’est-à-dire le produit du travail de méchant spammeurs !

Dans l’article, des résultats numériques montrent que cette méthode fonctionne bien comme il faut sur l’un des datasets fourni par Yahoo!, ce qui est une bonne chose pour nous.

RESUME

Voici un schéma qui résume la méthodologie que nous suivons :

method

Et voilà, comme d’habitude vous pouvez « lacher tes coms »…

Un article heureux est un article partagé !Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedIn