Filtrage bayésien du 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 :

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

où :

• ${\displaystyle P(S|M)}$ est la probabilité que le message soit un spam, sachant que le mot « Replica » y figure ;
• ${\displaystyle P(S)}$ est la probabilité dans l'absolu qu'un message quelconque soit un spam ;
• ${\displaystyle P(M|S)}$ est la probabilité que « Replica » apparaisse dans des messages de spam ;
• ${\displaystyle P(H)}$ est la probabilité dans l'absolu qu'un message quelconque ne soit pas un spam (c'est-à-dire du « ham ») ;
• ${\displaystyle 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)

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

${\displaystyle 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 % :

${\displaystyle 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 :

${\displaystyle 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 ${\displaystyle 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, ${\displaystyle 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.

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 :

${\displaystyle 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ù :

• ${\displaystyle p}$ est la probabilité que le message suspect soit du spam ;
• ${\displaystyle p_{1}}$ est la probabilité ${\displaystyle P(M_{1}|S)}$ que ce soit du spam, sachant qu'il contient un premier mot (par exemple « Replica ») ;
• ${\displaystyle p_{2}}$ est la probabilité ${\displaystyle P(M_{1}|S)}$ que ce soit du spam, sachant qu'il contient un deuxième mot (par exemple « watches ») ;
• etc.
• ${\displaystyle p_{N}}$ est la probabilité ${\displaystyle P(M_{N}|S)}$ que ce soit du spam, sachant qu'il contient un ${\displaystyle 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 ${\displaystyle p}$ est habituellement comparé à un seuil donné pour décider si le message est un spam ou non. Si ${\displaystyle 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.

Souvent, ${\displaystyle 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 :

${\displaystyle {\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é :

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

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

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

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

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

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 :

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

où :

• ${\displaystyle P'(S|M)}$ est la probabilité corrigée que le message soit du spam, sachant qu'il contient un mot donné ;
• ${\displaystyle s}$ est la force que nous donnons aux informations sur le spam ambiant ;
• ${\displaystyle P(S)}$ est la probabilité qu'un message entrant soit du spam ;
• ${\displaystyle n}$ est le nombre d'occurrences de ce mot pendant la phase d'apprentissage ;
• ${\displaystyle 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.

${\displaystyle P(S)}$ peut à nouveau être pris égal à ${\displaystyle 0,5}$, pour éviter d'obtenir un filtre trop soupçonneux. ${\displaystyle 3}$ est une bonne valeur pour ${\displaystyle 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ù ${\displaystyle n}$ est nul (et où la spamicité n'est pas définie), et donne dans ce cas ${\displaystyle P(S)}$.

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 ${\displaystyle |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.

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 ${\displaystyle 2\cdot N}$ degrés de liberté, on peut utiliser la formule :

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

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

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

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 ».

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].

• Inférence bayésienne
• Filtrage collaboratif
• Anti-spam

• (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