Filtrage bayésien du spam

Le filtrage bayésien du spam (en référence au théorème de Bayes) est une technique statistique de détection de pourriels s'appuyant sur la classification naïve bayésienne.

Les filtres bayésiens fonctionnent en établissant une corrélation entre la présence de certains éléments (en général des mots, parfois d'autres choses) dans un message et le fait qu'ils apparaissent en général dans des messages indésirables (spam) ou dans des messages légitimes (ham) pour calculer la probabilité que ce message soit un spam.

Le filtrage bayésien du spam est une technique puissante pour traiter le courrier électronique indésirable. Elle s'adapte aux habitudes de courrier des uns et des autres et produit un taux de faux positifs suffisamment bas pour être acceptable.

Historique

Le premier programme de filtrage du courrier électronique utilisant Bayes était le programme iFile de Jason Rennie, publié en 1996. Ce programme était utilisé pour classer le courrier en dossiers^[1]^, ^[2]. La première publication académique sur le filtrage bayésien du spam a été faite par Sahami et al. en 1998^[3]. En 2002, les principes du filtrage bayésien ont été portés à la connaissance d'un plus grand public dans un article de Paul Graham^[4].

Des variantes de la technique de base ont été implémentées dans plusieurs travaux de recherche et produits logiciels. De nombreux agents de courriers électronique modernes mettent en œuvre des filtres bayésiens antispam. Les utilisateurs peuvent également installer des logiciels tiers spécialisés dans ce travail. Il est également possible de déployer ce type de filtre sur les serveurs à l'aide de logiciels spécialisés comme DSPAM (en), SpamAssassin, SpamBayes (en), Altospam, Bogofilter, OutClock, Spamihilator ou encore ASSP (en), et cette fonctionnalité est parfois intégrée au serveur de courrier lui-même.

Procédé

Certains mots ont des probabilités d'apparaître dans un spam et dans un courrier légitime. Par exemple, la plupart des gens rencontreront fréquemment le mot « Viagra » dans leurs spams, mais ils le rencontreront rarement dans leurs courriers légitimes. Le filtre ne connaît pas à l'avance ces probabilités, c'est pourquoi il lui faut un temps d'apprentissage pour les évaluer. L'apprentissage est à la charge de l'utilisateur, qui doit indiquer manuellement si un message est un spam ou non. Pour chaque mot de chaque message « appris », le filtre ajustera les probabilités de rencontrer ce mot dans un spam ou un courrier légitime et les stockera dans sa base de données. Par exemple, les filtres bayésiens ont de fortes chances d'avoir une forte probabilité de spam pour le mot « Viagra », mais une très faible probabilité pour les mots rencontrés dans les courriers légitimes, comme les noms des amis et des parents de l'utilisateur.

Après l'apprentissage, les probabilités des mots (également appelées fonctions de vraisemblance) sont utilisées pour calculer la probabilité qu'un message (l'ensemble de ces mots) soit un spam. Chaque mot du message, ou du moins chaque mot « intéressant » du message, contribue à la probabilité que le message soit un spam. Cette contribution est calculée en utilisant le théorème de Bayes. Une fois que le calcul pour le message en entier est terminé, on compare sa probabilité d'être un spam à une valeur arbitraire (95 % par exemple) pour marquer ou non le message comme spam.

Comme dans n'importe quelle autre technique de filtrage du spam, les messages marqués comme spam peuvent être automatiquement déplacés dans un dossier « détritus », ou même supprimés sur le champ. Certains logiciels mettent en place des mécanismes de quarantaine qui définissent un intervalle de temps pendant lequel l'utilisateur a la possibilité de réexaminer la décision du logiciel.

L'apprentissage initial peut souvent être affiné si jamais de mauvaises décisions du logiciel sont identifiées (faux positifs ou faux négatifs). Cela permet au logiciel de s'adapter à la nature évolutive du spam.

Certains filtres anti-spam combinent les résultats du filtrage bayésien du spam à d'autres méthodes heuristiques (règles prédéfinies concernant le contenu du message, examen de l'enveloppe du message, etc.), ce qui conduit à un filtrage encore plus précis, parfois aux dépens de l'adaptivité.

Fondements mathématiques

Les filtres antispams bayésiens reposent sur le théorème de Bayes. Le théorème de Bayes est utilisé à plusieurs reprises dans le contexte du spam :

une première fois, pour calculer la probabilité que le message soit un spam, sachant qu'un mot donné apparaît dans ce message ;
une deuxième fois, pour calculer la probabilité que le message soit un spam, en considérant tous ses mots, ou un sous-ensemble significatif de ses mots ;
parfois une troisième fois, pour traiter les mots rares.

Calculer la probabilité qu'un message contenant un mot donné soit un spam

Supposons que le message suspect contienne le mot « Replica ». En 2009, la plupart des gens habitués à recevoir du courrier électronique savent qu'il est probable que ce message soit un spam, plus précisément une tentative de vendre des contrefaçons de marques de montres célèbres. Le logiciel de détection de spam ignore néanmoins de tels faits, tout ce qu'il sait faire est calculer des probabilités.

La formule que le logiciel utilise pour déterminer cette probabilité est dérivée du théorème de Bayes. Il s'agit, dans sa forme la plus générale, de :

P(S|M)={\frac {P(M|S)\cdot P(S)}{P(M|S)\cdot P(S)+P(M|H)\cdot P(H)}}

où :

$P(S|M)$ est la probabilité que le message soit un spam, sachant que le mot « Replica » y figure ;
$P(S)$ est la probabilité dans l'absolu qu'un message quelconque soit un spam ;
$P(M|S)$ est la probabilité que « Replica » apparaisse dans des messages de spam ;
$P(H)$ est la probabilité dans l'absolu qu'un message quelconque ne soit pas un spam (c'est-à-dire du « ham ») ;
$P(M|H)$ est la probabilité que « Replica » apparaisse dans des messages de ham.

(Démonstration : Théorème de Bayes#Autres écritures du théorème de Bayes)

La spamicité

Les statistiques récentes montrent que la probabilité actuelle qu'un message quelconque soit un spam sont au moins de 80 %^[5] :

P(S)=0,8;P(H)=0,2

La plupart des logiciels bayésiens de détection du spam considèrent qu'il n'y a pas de raison a priori^[6] qu'un message reçu soit du spam plutôt que du ham, et considèrent les deux cas comme ayant des probabilités identiques de 50 % :

P(S)=0,5;P(H)=0,5

Les filtres qui font cette hypothèse sont dits « non biaisés », ce qui signifie qu'ils n'ont pas de préjugés sur le courrier reçu. Cette hypothèse permet de simplifier la formule générale en :

P(S|M)={\frac {P(M|S)}{P(M|S)+P(M|H)}}

Cette quantité est appelée spamicité du mot « Replica » et peut être calculée. Le nombre $P(M|S)$ qui apparaît dans cette formule est approché par la fréquence des messages contenant « Replica » parmi les messages identifiés comme du spam pendant la phase d'apprentissage. De manière semblable, $P(M|H)$ est approché par la fréquence des messages contenant « Replica » parmi les messages identifiés comme du ham durant la phase d'apprentissage. Pour que ces approximations soient réalistes, l'ensemble de messages « appris » doit être suffisamment grand et représentatif^[7]. De plus, il est recommandé que le jeu de messages utilisé pour l'apprentissage se conforme à l'hypothèse de 50 % sur la répartition entre pourriel et messages innocents, c'est-à-dire que le corpus de spam et le corpus de ham soient environ de la même taille^[8].

Bien entendu, déterminer si un message est un spam ou non en se fondant uniquement sur la présence du mot « Replica » peut conduire à l'erreur, c'est pourquoi le logiciel antispam essaye de considérer plusieurs mots et de combiner leurs spamicités pour déterminer la probabilité d'ensemble d'être un spam.

Combiner les probabilités individuelles

Le logiciel de filtrage bayésien du spam fait l'hypothèse naïve que les mots présents dans le message sont des évènements indépendants. Cela est faux dans les langages naturels comme le français, où la probabilité de trouver un adjectif, par exemple, est influencée par la probabilité d'avoir un nom. Quoi qu'il en soit, avec cette hypothèse, on peut déduire une autre formule du théorème de Bayes :

p={\frac {p_{1}p_{2}\cdots p_{N}}{p_{1}p_{2}\cdots p_{N}+(1-p_{1})(1-p_{2})\cdots (1-p_{N})}}

où :

$p$ est la probabilité que le message suspect soit du spam ;
$p_{1}$ est la probabilité $P(M_{1}|S)$ que ce soit du spam, sachant qu'il contient un premier mot (par exemple « Replica ») ;
$p_{2}$ est la probabilité $P(M_{1}|S)$ que ce soit du spam, sachant qu'il contient un deuxième mot (par exemple « watches ») ;
etc.
$p_{N}$ est la probabilité $P(M_{N}|S)$ que ce soit du spam, sachant qu'il contient un $N$ ième mot (par exemple « home »).

(Démonstration : Combining probabilities sur le site MathPages^[9])

De telles hypothèses font du logiciel de filtrage bayésien un processus de classification naïve bayésienne.

Le résultat $p$ est habituellement comparé à un seuil donné pour décider si le message est un spam ou non. Si $p$ est en dessous de ce seuil, le message est considéré comme un probablement légitime. Sinon, il est considéré comme probablement illégitime.

Autre expression de la formule permettant de combiner les probabilités individuelles

Souvent, $p$ n'est pas calculé directement en utilisant la formule précédente, car elle a tendance à produire des soupassements arithmétiques (arithmetic underflows) une fois implémentée dans un programme informatique. À sa place, on peut utiliser les logarithmes en réécrivant la formule originale ainsi :

{\frac {1}{p}}-1={\frac {(1-p_{1})(1-p_{2})\dots (1-p_{n})}{p_{1}p_{2}\dots p_{n}}}

En prenant le logarithme des deux côtés de l'égalité :

\ln \left({\frac {1}{p}}-1\right)=\sum _{i=1}^{N}\left[\ln(1-p_{i})-\ln p_{i}\right]

Posons $\eta =\sum _{i=1}^{N}\left[\ln(1-p_{i})-\ln p_{i}\right]$ . Alors,

{\frac {1}{p}}-1=e^{\eta }

Ce qui donne l'expression alternative de la formule permettant de calculer la probabilité combinée :

p={\frac {1}{1+e^{\eta }}}

Traiter les mots rares

Dans le cas où le mot « Replica » n'a jamais été rencontré durant la phase d'apprentissage, le numérateur et le dénominateur sont tous les deux nuls, aussi bien dans la formule générale de calcul de la probabilité qu'un message contenant ce mot soit un spam que dans la formule de calcul de la spamicité de ce mot. Le logiciel de filtrage du courrier peut décider de rejeter de tels mots pour lesquels on ne dispose pas d'informations.

De façon plus générale, les mots qui n'ont été rencontrés qu'un petit nombre de fois pendant la phase d'apprentissage posent problème, car ce serait une erreur de faire confiance aveuglément à l'information qu'ils apportent. Une solution simple est de mettre ces mots aussi de côté.

En appliquant à nouveau le théorème de Bayes, et en supposant que le classement entre spams et courrier légitime est une variable aléatoire obéissant à la loi bêta, d'autres logiciels décident d'utiliser une probabilité corrigée :

P'(S|M)={\frac {s\cdot P(S)+n\cdot P(S|M)}{s+n}}

où :

$P'(S|M)$ est la probabilité corrigée que le message soit du spam, sachant qu'il contient un mot donné ;
$s$ est la force que nous donnons aux informations sur le spam ambiant ;
$P(S)$ est la probabilité qu'un message entrant soit du spam ;
$n$ est le nombre d'occurrences de ce mot pendant la phase d'apprentissage ;
$P(S|M)$ est la spamicité du mot.

(Démonstration : dans l'article A statistical approach to the spam problem^[6])

La probabilité corrigée est utilisée à la place de la spamicité dans la formule combinant les probabilités de chaque mot.

$P(S)$ peut à nouveau être pris égal à $0,5$ , pour éviter d'obtenir un filtre trop soupçonneux. $3$ est une bonne valeur pour $s$ , ce qui veut dire qu'il faut plus de trois messages pour avoir plus confiance dans la valeur de la spamicité que dans les informations sur le spam ambiant.

Cette formule peut être étendue au cas où $n$ est nul (et où la spamicité n'est pas définie), et donne dans ce cas $P(S)$ .

Autres heuristiques

Les mots « neutres » comme « le », « la », « un » (en français) ou leurs équivalents dans d'autres langues sont habituellement ignorés.

De façon plus générale, la plupart des logiciels de filtrage bayésiens ignorent purement et simplement tout mot dont la spamicité est proche de 0,5, car ils ne contribuent pas à une bonne décision. Les mots pris en considération sont ceux dont la spamicité est proche de 0,0 (signes distinctifs de messages légitimes) ou proche de 1,0 (signes distinctifs de messages illégitimes). Une méthode peut consister à ne conserver que les dix mots pour lesquels la valeur absolue $|0,5-pI|$ est la plus grande.

Certains logiciels prennent en considération le fait qu'un mot donné apparaît plusieurs fois dans le message examiné^[10], d'autres ne le font pas.

Certains logiciels utilisent des motifs (groupes de mots) au lieu de mots isolés dans la langue naturelle^[11]. Par exemple, pour une fenêtre contextuelle de quatre mots, ils calculent la spamicité de « Viagra est bon pour », au lieu de calculer les spamicité de « Viagra », « est », « bon » et « pour ». Cette méthode donne plus de sensibilité au contexte et élimine mieux le bruit bayésien, mais demande une plus grande base de données.

Méthodes mixtes

Il y a d'autres manières de combiner les probabilités individuelles pour les différents mots que l'approche « naïve ». Ces méthodes divergent de la méthode naïve sur les hypothèses qui sont faites au sujet des données en entrée. Ces hypothèses différentes donnent des formules radicalement différentes pour combiner les probabilités individuelles.

Par exemple, si l'on suppose que les probabilités individuelles suivent une loi du χ² avec $2\cdot N$ degrés de liberté, on peut utiliser la formule :

p=C^{-1}(-2\ln(p_{1}p_{2}\cdots p_{N}),2N)

où $C^{-1}$ est l'inverse de la fonction χ².

Les probabilités individuelles peuvent être combinées aussi avec les techniques de discrimination markovienne.

Discussion

Avantages

Un des principaux avantages du filtre bayésien est qu'il s'adapte à son utilisateur.

Le spam qu'un utilisateur reçoit est souvent lié à son activité sur Internet. Par exemple, alors qu'il surfait sur le web, il peut avoir été inscrit à son insu sur une liste de diffusion (présentée comme une « lettre commerciale ») qu'il considérera comme du spam. La plupart du temps, l'ensemble des messages envoyés sur cette liste contiennent des mots communs, comme le nom de la liste et l'adresse de courrier électronique de son émetteur. Le filtre bayésien détectera ces points communs et leur attribuera une probabilité élevée.

De la même façon, les courriers légitimes reçus par plusieurs utilisateurs tendent à être différents. Par exemple, en milieu professionnel, le nom de la société où l'on travaille ainsi que les noms des clients et fournisseurs seront souvent mentionnés. Le filtre attribuera une probabilité basse aux courriers contenant ces noms.

Les probabilités peuvent évoluer au fil du temps, au moyen de l'apprentissage continu, à chaque fois que le filtre classe mal un message. Il en résulte qu'un filtre bayésien est souvent plus précis que des règles prédéfinies.

Les filtres bayésiens évitent particulièrement bien les faux positifs, c'est-à-dire de classer les messages légitimes comme des spams. Par exemple, si le courriel contient le mot « Nigeria », qui apparaît souvent dans les spams de type arnaque nigériane, un jeu de règles prédéfinies le rejettera d'office. Un filtre bayésien marquerait le mot « Nigeria » comme caractéristique de spam, mais prendrait aussi en compte d'autres mots importants, comme le nom du conjoint ou les noms d'amis, qui sont habituellement des signes de courriers légitimes et prendront le pas sur la présence du mot « Nigeria ».

Inconvénients

L'empoisonnement bayésien (bayesian poisoning) est une technique utilisée par les spameurs pour tenter de dégrader l'efficacité des filtres antispams bayésiens. Elle consiste à placer dans le courrier une grande quantité de texte anodin (provenant de site d'actualités ou de la littérature par exemple), ou bien de salade textuelle (des séquences aléatoires de mots qui semblent cohérentes mais qui ne veulent rien dire), pour noyer le texte indésirable et tromper le filtre.

Les spammeurs peuvent également transformer les mots qui n'apparaissent d'habitude en grande majorité que dans le spam. Ainsi, « Viagra » sera transformé par exemple en « Viaagra » ou en « V!agra ». La lecture reste toujours possible par le destinataire mais chacun de ces mots transformés ne se rencontrera que plus rarement, ce qui pénalise l'apprentissage par le filtre bayésien. En pratique, cette technique marche assez mal, car les mots dérivés finissent eux-mêmes par être reconnus par le filtre^[4].

Une autre technique utilisée par les spammeurs pour essayer de tromper le filtre bayésien est de remplacer le texte par des images. L'ensemble du texte, ou une partie de celui-ci, est remplacé par une image où ce même texte est « dessiné ». Le filtre de spam est d'ordinaire incapable d'analyser cette image qui contient les mots sensibles comme « Viagra ». Néanmoins, bon nombre d'utilisateurs désactivent l'affichage des images pour des raisons de sécurité, ce qui fait que les polluposteurs atteignent moins leurs cibles. De plus, la taille d'une image est supérieure à celle du texte équivalent, et les polluposteurs ont besoin de plus de bande passante pour envoyer des messages contenant des images. Certains filtres tendent à décider qu'un message est du spam quand il a trop de contenu graphique. Enfin, une solution qui est probablement plus efficace a été proposée par Google et est utilisée par le système de courrier électronique Gmail : traiter toute image de taille moyenne ou grande par reconnaissance optique de caractères pour analyser le texte qu'elle contient ^[12].

Notes et références

↑ (en) Jason Rennie, « ifile » [text], 1996 (consulté le 23 avril 2020)
↑ (en) Jason D. M. Rennie, « ifile: An Application of Machine Learning to E-Mail Filtering » [PDF], Boston, MA USA, KDD-2000 Text Mining Workshop, 2000 (consulté le 23 avril 2020)
↑ (en) M. Sahami, S. Dumais, D. Heckerman, E. Horvitz, A Bayesian Approach to Filtering Junk E-Mail, AAAI'98 Workshop on Learning for Text Categorization, 1998.
↑ ^{a et b} (en) Paul Graham, « A Plan for Spam » [html], 2002 (consulté le 23 avril 2020).
↑ (en) Dylan Mors et Dermot Harnett, « State of Spam, a monthly report, report #33 » [PDF], 2009 (version du 23 mars 2019 sur Internet Archive).
↑ ^{a et b} (en) Gary Robinson, « A statistical approach to the spam problem », Linux Journal,‎ 1^er mars 2003 (lire en ligne, consulté le 23 avril 2020).
↑ (en) Trevor Stone, « Parametrization of Naïve Bayes for Spam Filtering », automne 2003
↑ (en) Process Software, Introduction to Bayesian Filtering
↑ (en) « Combining probabilities » sur le site MathPages.
↑ (en) Brian Burton, « SpamProbe - Bayesian Spam Filtering Tweaks », 2003.
↑ (en) Jonathan A. Zdziarski, « Bayesian Noise Reduction: Contextual Symmetry Logic Utilizing Pattern Consistency Analysis »^{(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)}, 2004.
↑ (en) « Gmail uses Google's innovative technology to keep spam out of your inbox »

Voir aussi

Articles connexes

Liens externes

(en) Guide des filtres bayésiens de spam : 1^re partie, 2^de partie.
(en) Explication détaillée des formules de Paul Graham par Tim Peters
(en) Le blog de Gary Robinson sur le spam
Fondement mathématiques de l'apprentissage Statistique

[1] (en) Jason Rennie, « ifile » [text], 1996 (consulté le 23 avril 2020)

[2] (en) Jason D. M. Rennie, « ifile: An Application of Machine Learning to E-Mail Filtering » [PDF], Boston, MA USA, KDD-2000 Text Mining Workshop, 2000 (consulté le 23 avril 2020)

[3] (en) M. Sahami, S. Dumais, D. Heckerman, E. Horvitz, A Bayesian Approach to Filtering Junk E-Mail, AAAI'98 Workshop on Learning for Text Categorization, 1998.

[graham-4] {a et b} (en) Paul Graham, « A Plan for Spam » [html], 2002 (consulté le 23 avril 2020).

[5] (en) Dylan Mors et Dermot Harnett, « State of Spam, a monthly report, report #33 » [PDF], 2009 (version du 23 mars 2019 sur Internet Archive).

[robinson-6] {a et b} (en) Gary Robinson, « A statistical approach to the spam problem », Linux Journal,‎ 1^er mars 2003 (lire en ligne, consulté le 23 avril 2020).

[7] (en) Trevor Stone, « Parametrization of Naïve Bayes for Spam Filtering », automne 2003

[8] (en) Process Software, Introduction to Bayesian Filtering

[9] (en) « Combining probabilities » sur le site MathPages.

[10] (en) Brian Burton, « SpamProbe - Bayesian Spam Filtering Tweaks », 2003.

[11] (en) Jonathan A. Zdziarski, « Bayesian Noise Reduction: Contextual Symmetry Logic Utilizing Pattern Consistency Analysis »^{(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)}, 2004.

[12] (en) « Gmail uses Google's innovative technology to keep spam out of your inbox »

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]