Comment fonctionne un moteur de recherche ? (6ème partie : la lutte contre le spam)

Comment est captée cette valeur ? La réponse à cette question est la justification du webspam. Cette valeur va venir du nombre de visiteurs que vous aurez sur vos sites. Et ces visiteurs viennent majoritairement des moteurs de recherche (même si certains réseaux sociaux sont en tête sur des secteurs spécifiques, comme par exemple l’information au sens large). Parmi les moteurs, Google est en tête (93% de parts de marché en France en 2014) et les trois premières places du classement Google pour une requête assurent 75% des clics selon une étude menée par Synodiance en 2015. Le spam sur le web existe uniquement parce que des personnes tentent d’obtenir ces trois premières places à tout prix.

Qu’est ce que le spam sur le Web ?

Le spam sur le Web est avant tout caractérisé par la volonté de manipulation des algorithmes des moteurs de recherche. Il regroupe l’ensemble des techniques mises au points par les webmasters pour améliorer artificiellement leur classement dans les moteurs de recherche.

Il existe plusieurs types de spam sur le Web car il existe plusieurs algorithmes et plusieurs signaux utilisés par les moteurs de recherche pour faire leur classement. On peut cependant regrouper tous les types de spam dans deux familles qui correspondent aux deux grandes familles de signaux utilisés par les moteurs:

1. La manipulation du contenu des pages (ce qui inclut le code source de la page) ;
2. La manipulation des liens vers les pages web et vers l'entourage de ces pages.

Concernant la manipulation des contenus, on va pouvoir observer principalement de la duplication des termes de la requête visée par le SEO dans les “meilleures endroits” de la page. C’est ainsi qu’apparait par exemple la fameuse "triplette du bourrin" chère au coeur de Laurent Bourrelly qui a popularisé la notion (voir son article [8]). Il s’agit de mettre dans ce cas les termes de la requête dans la balise title, dans le H1 et dans l’URL de la page. Le remplissage des ancres des liens qui pointent vers une page web par la requête exacte procède aussi de la même idée.

Une autre manipulation des contenus vise directement l’algorithme de mesure de la pertinence, et au niveau des SEO, il s’agit principalement d’optimiser une métrique de type TF-IDF ou équivalente. Il y a quelques années, la qualité des textes créés était particulièrement calamiteuse, il s'agissait assez souvent de faire de la répétition de termes, ou plus “subtilement” de modifier un texte “propre” pris par exemple sur Wikipedia et à remplacer brutalement une partie des mots par les termes de la requête visée.

Traditionnellement, les chercheurs en recherche adversarial ne considèrent que deux niveaux de qualité : le spam web et les pages légitimes. Et pour définir le spam, il est souvent dit “qu'on le reconnaît lorsqu'on le voit''. Le lecteur intéressé pourra notamment lire les articles [6] et [7] sur ce sujet.

Il est important de comprendre que ce qui détermine le spam sur les textes est principalement la volonté de nuisance de son auteur. Pour déterminer si une page est du spam, il faut donc chercher à comprendre l'intention du webmaster. On s'attache en particulier à savoir s'il a sciemment cherché à contourner les algorithmes mis en place par les moteurs de recherche en vue de modifier les résultats renvoyés par ces derniers.  Il apparaît cependant que cette définition est bien faible puisqu'il existe des sites web qui sont dépourvus d'intention maligne, mais qui sont d'une indigence telle qu'aucun moteur ne pourrait vouloirmettre en avant leurs contenus. Il est donc raisonnable d'estimer qu'il faut une granularité plus fine dans l'évaluation de la qualité des sites web. C’est ce qui est maintenant fait par les moteurs qui en plus de décider si une page est du spam ou non, vont également lui attribuer un score de qualité.

Concernant le spam sur les liens (on parle généralement de spam structurel), l’objectif des spammeurs est principalement d’augmenter la popularité (c’est-à-dire le PageRank) de la page cible. On sait depuis les travaux de Zoltán Gyöngyi (voir l’article [9]) comment faire une structure de liens qui génère une optimisation parfaite du PageRank d’une page.
La plupart des webmasters savent qu’il faut obtenir de nombreux liens vers sa page web pour augmenter son PR. Pour cela, de nombreux spammeurs vont créer une ferme de liens, qui va massivement faire des liens vers une page cible. C’est typiquement ce qui arrive lorsqu’est fait du blast de commentaires de blogs (voir la figure 1).

Fig. 1 : La structure typique d’un blast.

Ce type de structure autour d’une page cible fonctionne, mais on peut faire beaucoup plus efficace en réfléchissant au comportement du surfeur aléatoire. La figure 2 présente cette structure de liens optimale.

Fig. 2 : La structure optimale.

On voit que ce qui caractérise cette structure est la notion de page de boost. Il s’agit d’une page qui va faire cycler le surfeur aléatoire et donc amplifier sa présence sur la page cible de la structure. En procédant ainsi, on peut multiplier le pagerank de cette page cible par 3.6, et c’est la meilleure amplification qu’il est possible d’obtenir.

Cette structure a ses avantages et inconvénients. L’avantage est qu’elle est facile à construire, l’inconvénient est qu’elle est difficile à indexer : il faut indexer séparément chaque page  de la ferme de liens. Cette structure est également facile à repérer pour les moteurs, elle est donc de moins en moins utilisée par les spammeurs.

De nos jours, les spammeurs vont utiliser des structures d’amplification plus subtiles, notamment sous la forme de cascade qui vont agréger du PageRank d’un ensemble de pages de très mauvaise qualité, puis le transmettre à un ensemble de meilleure qualité, puis à un ensemble, etc., jusqu’à la page cible. Ces structures rapportent moins mais sont beaucoup plus difficiles à identifier pour le moteur ce qui leur garantit une plus grande pérennité.

Comment le moteur lutte-t-il contre toutes ces manipulations ?

Il existe une multitude d’algorithmes de détection, mais en pratique, ils appartiennent tous à l’une des deux grandes familles de lutte contre le spam : les filtres et les updates.

Un update est un changement du coeur de la méthode de classement. Au chapitre des updates, on trouve par exemple la notion de PageRank thématique de Taher Haveliwala (nous en avons parlé dans un précédent article et mentionné qu’elle permettait une amélioration de la qualité de 20%), ou encore l’insertion d’un signal de type Trustrank au niveau du moteur (voir l’article [2] qui présente l’algorithme du Trustrank, qui n’est pas le même que le Trustrank de Google).

Les updates sont généralement réalisés via des algorithmes qui analysent la structure des liens plutôt que via des algorithmes travaillant sur le contenu. Mais on peut cependant dire que les derniers développements avec l’utilisation des vecteurs de contexte est du ressort des updates. Même si cet update ne lutte contre le spam que par ricochet (son premier but est d’améliorer la compréhension des requêtes).

La plupart des updates vont réaliser du déclassement du spam, c’est-à-dire qu’ils vont annuler l’impact des manipulations, sans nécessairement permettre d’identifier les spammeurs. D’une certaine manière, un update est avant tout une manière plus robuste de traiter l’information plutôt qu’un moyen de lutte contre le spam.

Les filtres sont eux beaucoup plus intuitifs : il s’agit de repérer les critères constitutifs du spam (par exemple voir que si le pourcentage d’ancres exactes dépasse 5% c’est qu’il y a eu manipulation) et ensuite de pénaliser toutes les pages qui satisfont ces critères (plus de 5% d’ancres exactes -> pénalisation directe). Les algorithmes Panda et Penguin sont des filtres.

La problématique des filtres pour le moteur de recherche est celle classique du machine learning : il faut beaucoup de données pour apprendre les critères constitutifs, et ensuite une puissance de calcul non négligeable pour traiter tout l’index du moteur. C’est Navneet Panda, ingénieur chez Google, qui a réussi le premier ce tour de force, et c’est pour cela que l’algorithme Panda porte ce nom. Google a ensuite surfé sur la vague des animaux pour nommer ses filtres (il n’y a pas de Monsieur Penguin au sein du moteur!).

Un exemple de filtre : les travaux de Ntoulas et al.

En matière de filtre sur le contenu des pages, ce sont les travaux de Ntoulas et ses coauteurs (voir l’article [3]) qui sont les premiers à avoir présenté cette notion.

Leur approche a consisté à créer un dataset de pages web (via un crawl du web et un tirage aléatoire de 18  000 pages parmi toutes celles crawlées). Ils ont ensuite demandé à des humains de noter la qualité des pages, pour déterminer celles qui sont du spam et celles qui sont de bonne qualité.

L’étape suivante est d'extraire les caractéristiques du dataset pour déterminer ce qui caractérise le spam et qui est détectable algorithmiquement. Par exemple, on apprend dans cette étude (datant de 2006) que 70% des sites en .biz sont des sites utilisant des techniques de spam tandis que c'est le cas pour moins de 5% des sites en .org.

Le cœur de leur article porte sur les critères in text qui permettent de classifier efficacement des pages web. Ils en ont déterminé de très nombreux dont par exemple :

1. Taille de la page ;
2. Nombre de séparateurs dans l'URL ;
3. Longueur du nom de domaine ;
4. Nombre de mots dans la page ;
5. Nombre de mots dans le titre ;
6. Longueur moyenne des mots ;
7. Taux de compression (rapport entre la taille de la page zippée et sa version décompressée) ;
8. Vraisemblance d’indépendance (un score proportionnel à la compatibilité des mots de la page entre eux).

Une fois ces critères mis au point, toutes les données nourrissent un algorithme de classification (dans le cas de cet article, le C4.5 de Ros Quinlan) et permettent de créer un arbre de décision. Celui-ci va permettre de décider si une page est du spam ou non. La figure 3 présente un exemple (totalement artificiel) d’arbre de décision.

Fig. 3 : Un arbre de décision.

Avec cette approche, les auteurs annoncent qu'ils identifient correctement 86.2% du spam de leur échantillon comme tel, et 98,7% du non-spam comme étant légitime. Les chiffres paraissent plutôt flatteurs pour une méthode très simple, mais il reste un taux de faux positifs encore important (1.3% c’est plusieurs milliards de pages pour un index comme celui de Google).

Un exemple d’update : modifier le crawl pour pénaliser les structures d’amplification

Pour illustrer la notion d’update structurelle, nous avons choisi de vous présenter un algorithme que nous avons nous-même créé. Cet algorithme est un update car il a vocation à être intégré au niveau du crawler d’un moteur : il agit donc avant même l’indexation des pages web. Par ailleurs, il s’inscrit en plein dans les méthodes de déclassement : nous allons minimiser l’impact de l’amplification de PageRank, sans savoir qui amplifie ce dernier.

Le principe de l'algorithme est simple : nous allons regrouper des pages qui font beaucoup de liens entre elles au sein de ce que l’on appelle un cluster. Un cluster est donc un ensemble de pages qui font beaucoup de liens entre elles, et peu de liens vers l’extérieur du cluster. Il se trouve que cette caractéristique est fondamentalement le principe d’une ferme de liens qui a pour objectif de piéger le surfeur aléatoire dans l’entourage d’une page et de l'empêcher de s’éloigner de cette même page.

Bien sûr, cet algorithme impose de savoir clusteriser les pages web, qui plus est au moment du crawl. Il existe de nombreuses méthodes de clustering efficaces. Par exemple le Markov Cluster Algorithm (MCL) et l’algorithme EBC (Edge Betweenness Clustering) sont des algorithmes efficaces. Ils ne sont cependant pas utiles dans notre contexte. Tout d’abord car ils ont besoin de l’intégralité du graphe sous-jacent à l’index pour fonctionner, et ici on veut travailler lors du crawl. Par ailleurs leur temps de calcul est proportionnel au cube du nombre de noeuds du graphe, ce qui est abusivement “trop cher” pour le graphe d’un index web de taille importante (plusieurs milliers de milliards de pages).

De plus, trouver les clusters exacts du graphe du Web est en fait inutile : ce que l’on veut faire, c’est regrouper des pages ensemble pour annuler l’effet d’obtention de PageRank par la création de structures “discutables”. Si on supprime 95% de l’effet d’une ferme de liens, on aura supprimé suffisamment d’amplification pour annuler l’intérêt de ladite ferme de liens.

Pour éviter d’utiliser des méthodes de clustering exactes mais coûteuses, on va utiliser des heuristiques. Une heuristique, c’est un algorithme qui a un temps de calcul efficace, et qui fonctionne car… il fonctionne. On va donc créer un algorithme, le tester, et si les résultats sont bons, on va l’utiliser sans se poser de questions.

L’idéal ici est une technique que l’on peut intégrer au PageRank, et au coût quasi nul. Nous avons plusieurs méthodes de regroupements des pages entre elles, et nous en présentons deux ici.

Pour chaque heuristique, on va annuler les transferts de PageRank entre les pages d’un même regroupement (cela reviendrait en fait à fusionner toutes ces pages en une seule). Ces méthodes sont locales, c’est-à-dire que pour décider si un noeud est dans un regroupement, il n’est pas utile de savoir quels sont les noeuds qui sont dans d’autres regroupements.

La première méthode regroupe les nœuds qui font partie de petits cycles dans le graphe. Plus précisément, on va choisir (arbitrairement) une longueur k et à partir de chaque nœud, on va calculer tous les chemins de longueur k qui en partent. Tous les nœuds qui font partie d’un chemin qui revient à son point d’origine sont regroupés avec ce point. L’intuition derrière ce type de regroupement est que le spammeur va forcément générer des schémas qui reviennent vers la page cible dans le but de faire cycler le surfeur aléatoire autour de cette page.

On notera que si la longueur est 2, on regroupe tous les échanges réciproques, si c’est 3 tous les échanges triangulaires, etc. La figure 4 illustre cette technique.

Fig. 4 : Regroupement des pages qui sont dans un même cycle de longueur 4.

La deuxième méthode effectue des marches aléatoires depuis une page que l’on analyse. Ces marches sont de longueur fixée. Si le nombre de marches qui finissent sur un noeud donné dépasse un seuil fixé à l’avance, alors on va regrouper la source et le point d’arrivée. Cette approche est itérative : on regroupe les noeuds en clusters, puis les clusters en clusters de clusters, etc. La figure 5 illustre cette technique.

Fig. 5 : Regroupement par marches aléatoires.

Nous avons ensuite  testé ces deux techniques sur un dataset fourni par Yahoo en 2007. Les deux techniques sont toutes les deux valides pour déclasser le spam sur ce dataset : les pages qui bénéficient d’une amplification de PageRank sont déclassées par le mécanisme de regroupement.

Cependant, seule la première technique a été validée comme pouvant passer sur d’autres datasets. Pour cela il a fallu effectuer un calcul statistique qui garantit avec grande probabilité la reproductibilité de l’expérience sur d’autres datasets (le test du chi2). La deuxième technique est plus incertaine.

Il s’agit d’un exemple illustratif de méthode de déclassement, et on peut en concevoir de très nombreux autres, basés sur des méthodes de clustering, ou sur des calculs de variation de PageRank entre pages d’un même voisinage (en théorie les PR sont distribués sur le Web selon ce que l’on appelle une loi de puissance, si ce n’est pas le cas autour d’une page, c’est qu’il y a une anomalie qui mérite au moins que le moteur regarde de plus près ce qui se passe).

Conclusion

Nous avons vu ce mois-ci pourquoi il y avait du spam sur le Web et quelles sont les grands types de spam. Nous avons aussi vu qu’il existe de nombreuses techniques de lutte, dont deux exemples sont présentés plus haut.

Il est important de noter qu’il existe un véritable combat algorithmique entre le moteur et ses adversaires que sont les spammeurs. Ce combat est un équilibre constant, qui aboutit à un statu quo : aujourd’hui, comme en 2006, la proportion de spam sur le Web est toujours proche de 20%, ce qui est loin d'être négligeable.

Références

[1] Becchetti, L., Castillo, C., Donato, D., Baeza-Yates, R., and Leonardi, S. 2008. Link analysis for Web spam detection. ACM Trans. Web 2, 1 (Feb. 2008 ), 1-42.

[2] Zoltán Gyöngyi, Hector Garcia-Molina, Jan Pedersen. Combating Web Spam with TrustRank. 30th International Conference on Very Large Data Bases (VLDB), Toronto, Ontario, Canada, 2004.

[3] Alexandros Ntoulas, Marc Najork, Mark Manasse, and Dennis Fetterly. Detecting Spam Web Pages Through Content Analysis. 15th International World Wide Web Conference (May 2006), pages 83-92.

[4] Thomas Largillier, Sylvain Peyronnet: Webspam demotion: Low complexity node aggregation methods. Neurocomputing 76(1): 105-113 (2012)

[5] Thomas Largillier, Sylvain Peyronnet: Detecting Webspam Beneficiaries Using Information Collected by the Random Surfer. IJOCI 2(2): 36-48 (2011)

[6] Fetterly, D., Manasse, M., & Najork, M. (2004, June). Spam, damn spam, and statistics: Using statistical analysis to locate spam web pages. In Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004 (pp. 1-6). ACM.
https://www.microsoft.com/en-us/research/wp-content/uploads/2004/06/webdb2004.pdf

[7] Gyongyi, Z., & Garcia-Molina, H. (2005). Web spam taxonomy. In First international workshop on adversarial information retrieval on the web (AIRWeb 2005).
http://ilpubs.stanford.edu:8090/771/1/2005-9.pdf

[8] http://www.laurentbourrelly.com/blog/874.php

[9] Gyöngyi, Z., & Garcia-Molina, H. (2005, August). Link spam alliances. In Proceedings of the 31st international conference on Very large data bases (pp. 517-528). VLDB Endowment.
http://ilpubs.stanford.edu:8090/679/1/2005-15.pdf