EIN PLAN GEGEN SPAM

August 2002

(Dieser Artikel beschreibt die Spam-Filtertechniken, die wir in dem spamfreien webbasierten Mail-Reader verwendet haben, den wir entwickelt haben, um Arc zu testen. Ein verbessertes Algorithmus wird in Besseres Bayesisches Filtern beschrieben.)

Ich denke, es ist möglich, Spam zu stoppen, und dass inhaltsbasierte Filter der Weg dazu sind. Die Achillesferse der Spammer ist ihre Nachricht. Sie können jede andere Barriere, die Sie aufstellen, umgehen. Bisher haben sie das zumindest getan. Aber sie müssen ihre Nachricht übermitteln, was auch immer sie ist. Wenn wir Software schreiben können, die ihre Nachrichten erkennt, gibt es keinen Weg, wie sie das umgehen können.

Für den Empfänger ist Spam leicht erkennbar. Wenn Sie jemanden engagieren würden, um Ihre Post zu lesen und den Spam zu entsorgen, hätte er damit wenig Schwierigkeiten. Wie viel müssen wir tun, abgesehen von KI, um diesen Prozess zu automatisieren?

Ich denke, wir werden in der Lage sein, das Problem mit ziemlich einfachen Algorithmen zu lösen. Tatsächlich habe ich festgestellt, dass man den heutigen Spam akzeptabel gut filtern kann, indem man nichts weiter als eine bayesianische Kombination der Spam-Wahrscheinlichkeiten einzelner Wörter verwendet. Mit einem leicht angepassten (wie unten beschriebenen) bayesianischen Filter verpassen wir jetzt weniger als 5 von 1000 Spams, mit 0 falschen Positiven.

Der statistische Ansatz ist normalerweise nicht der erste, den die Leute versuchen, wenn sie Spam-Filter schreiben. Der erste Instinkt der meisten Hacker ist, Software zu schreiben, die individuelle Eigenschaften von Spam erkennt. Man schaut sich Spams an und denkt, wie dreist diese Leute sind, mir eine Mail zu schicken, die mit "Lieber Freund" beginnt oder eine Betreffzeile hat, die ganz in Großbuchstaben geschrieben ist und mit acht Ausrufezeichen endet. Ich kann diesen Kram mit etwa einer Zeile Code herausfiltern.

Und so tun Sie das, und am Anfang funktioniert es. Ein paar einfache Regeln werden einen großen Teil Ihres eingehenden Spams herausfiltern. Allein nach dem Wort "klicken" zu suchen, wird 79,7 % der E-Mails in meinem Spam-Korpus erfassen, mit nur 1,2 % falschen Positiven.

Ich habe etwa sechs Monate damit verbracht, Software zu schreiben, die nach individuellen Spam-Eigenschaften sucht, bevor ich den statistischen Ansatz ausprobierte. Was ich fand, war, dass es sehr schwierig wurde, die letzten paar Prozent Spams zu erkennen, und dass ich, je strenger ich die Filter machte, mehr falsche Positive bekam.

Falsche Positive sind harmlose E-Mails, die fälschlicherweise als Spam identifiziert werden. Für die meisten Benutzer ist es um ein Vielfaches schlimmer, legitime E-Mails zu verpassen, als Spam zu erhalten, sodass ein Filter, der falsche Positive liefert, wie eine Aknebehandlung ist, die ein Risiko für den Tod des Patienten birgt.

Je mehr Spam ein Benutzer erhält, desto unwahrscheinlicher wird es, dass er eine harmlose Mail in seinem Spam-Ordner bemerkt. Und seltsamerweise werden falsche Positive umso gefährlicher, je besser Ihre Spam-Filter werden, denn wenn die Filter wirklich gut sind, werden die Benutzer eher alles ignorieren, was sie erfassen.

Ich weiß nicht, warum ich so lange vermieden habe, den statistischen Ansatz auszuprobieren. Ich denke, es lag daran, dass ich süchtig danach wurde, Spam-Eigenschaften selbst zu identifizieren, als ob ich ein wettbewerbsorientiertes Spiel mit den Spammern spielen würde. (Nicht-Hacker erkennen das oft nicht, aber die meisten Hacker sind sehr wettbewerbsorientiert.) Als ich dann die statistische Analyse ausprobierte, stellte ich sofort fest, dass sie viel cleverer war als ich. Sie entdeckte natürlich, dass Begriffe wie "virtumundo" und "teens" gute Indikatoren für Spam waren. Aber sie entdeckte auch, dass "per" und "FL" und "ff0000" gute Indikatoren für Spam sind. Tatsächlich stellt sich heraus, dass "ff0000" (html für leuchtendes Rot) ein ebenso guter Indikator für Spam ist wie jeder pornografische Begriff.

Hier ist eine Skizze, wie ich statistisches Filtern mache. Ich beginne mit einem Korpus von Spam und einem von Nicht-Spam-Mails. Im Moment hat jeder etwa 4000 Nachrichten. Ich scanne den gesamten Text, einschließlich Header und eingebettetem HTML und JavaScript, jeder Nachricht in jedem Korpus. Ich betrachte derzeit alphanumerische Zeichen, Bindestriche, Apostrophe und Dollarzeichen als Teil von Tokens und alles andere als Token-Trenner. (Hier gibt es wahrscheinlich Raum für Verbesserungen.) Ich ignoriere Tokens, die nur aus Ziffern bestehen, und ich ignoriere auch HTML-Kommentare, ohne sie sogar als Token-Trenner zu betrachten.

Ich zähle die Anzahl der Vorkommen jedes Tokens (ohne Berücksichtigung der Groß- und Kleinschreibung, derzeit) in jedem Korpus. In diesem Stadium habe ich zwei große Hashtabellen, eine für jeden Korpus, die Tokens den Anzahl der Vorkommen zuordnet.

Als nächstes erstelle ich eine dritte Hashtabelle, die diesmal jedes Token der Wahrscheinlichkeit zuordnet, dass eine E-Mail, die es enthält, Spam ist, die ich wie folgt berechne [1]:


(let ((g (* 2 (or (gethash word good) 0))) (b (or (gethash word bad) 0))) (unless (< (+ g b) 5) (max .01 (min .99 (float (/ (min 1 (/ b nbad)) (+
(min 1 (/ g ngood)) (min 1 (/ b nbad)))))))))

wobei word das Token ist, dessen Wahrscheinlichkeit wir berechnen, good und bad die Hashtabellen sind, die ich im ersten Schritt erstellt habe, und ngood und nbad die Anzahl der Nicht-Spam- und Spam-Nachrichten sind.

Ich habe dies als Code erklärt, um ein paar wichtige Details zu zeigen. Ich möchte die Wahrscheinlichkeiten leicht verzerren, um falsche Positive zu vermeiden, und durch Versuch und Irrtum habe ich festgestellt, dass es eine gute Möglichkeit ist, alle Zahlen in good zu verdoppeln. Dies hilft, zwischen Wörtern zu unterscheiden, die gelegentlich in legitimen E-Mails vorkommen, und Wörtern, die fast nie vorkommen. Ich betrachte nur Wörter, die mehr als fünfmal insgesamt vorkommen (tatsächlich wäre es aufgrund der Verdopplung ausreichend, wenn sie dreimal in Nicht-Spam-Mails vorkommen). Und dann gibt es die Frage, welche Wahrscheinlichkeit Wörtern zuzuweisen ist, die in einem Korpus, aber nicht im anderen vorkommen. Wiederum habe ich durch Versuch und Irrtum .01 und .99 gewählt. Hier könnte es Raum für Feinabstimmung geben, aber während der Korpus wächst, wird eine solche Feinabstimmung ohnehin automatisch geschehen.

Die besonders aufmerksamen Leser werden bemerken, dass ich, während ich jeden Korpus als einen einzigen langen Textstrom für die Zählung der Vorkommen betrachte, die Anzahl der E-Mails in jedem als Divisor zur Berechnung der Spam-Wahrscheinlichkeiten verwende, anstatt ihre kombinierte Länge. Dies fügt eine weitere leichte Verzerrung hinzu, um gegen falsche Positive zu schützen.

Wenn neue Mails ankommen, werden sie in Tokens gescannt, und die interessantesten fünfzehn Tokens, wobei interessant gemessen wird, wie weit ihre Spam-Wahrscheinlichkeit von einem neutralen .5 entfernt ist, werden verwendet, um die Wahrscheinlichkeit zu berechnen, dass die Mail Spam ist. Wenn probs eine Liste der fünfzehn individuellen Wahrscheinlichkeiten ist, berechnen Sie die kombinierte Wahrscheinlichkeit wie folgt:

(let ((prod (apply #'* probs))) (/ prod (+ prod (apply #'* (mapcar #'(lambda (x) (- 1 x)) probs)))))

Eine Frage, die in der Praxis aufkommt, ist, welche Wahrscheinlichkeit einem Wort zuzuweisen ist, das Sie noch nie gesehen haben, d.h. einem, das nicht in der Hashtabelle der Wortwahrscheinlichkeiten vorkommt. Ich habe festgestellt, dass .4 eine gute Zahl ist, die man verwenden kann. Wenn Sie ein Wort noch nie gesehen haben, ist es wahrscheinlich ziemlich harmlos; Spam-Wörter sind allzu vertraut.

Es gibt Beispiele für diesen Algorithmus, die in einem Anhang am Ende angewendet werden.

Ich behandle Mails als Spam, wenn der obige Algorithmus ihnen eine Wahrscheinlichkeit von mehr als .9 zuweist, Spam zu sein. Aber in der Praxis würde es nicht viel ausmachen, wo ich diese Schwelle setze, da nur wenige Wahrscheinlichkeiten in der Mitte des Bereichs enden.

Ein großer Vorteil des statistischen Ansatzes ist, dass Sie nicht so viele Spams lesen müssen. In den letzten sechs Monaten habe ich buchstäblich Tausende von Spams gelesen, und es ist wirklich ein bisschen demoralisiert. Norbert Wiener sagte, wenn Sie mit Sklaven konkurrieren, werden Sie ein Sklave, und es gibt etwas ähnlich Erniedrigendes daran, mit Spammern zu konkurrieren. Um individuelle Spam-Eigenschaften zu erkennen, müssen Sie versuchen, in den Kopf des Spammers zu gelangen, und ehrlich gesagt möchte ich so wenig Zeit wie möglich in den Köpfen von Spammern verbringen.

Aber der wirkliche Vorteil des bayesianischen Ansatzes ist natürlich, dass Sie wissen, was Sie messen. Merkmals-erkennende Filter wie SpamAssassin weisen einer E-Mail einen Spam-"Score" zu. Der bayesianische Ansatz weist eine tatsächliche Wahrscheinlichkeit zu. Das Problem mit einem "Score" ist, dass niemand weiß, was er bedeutet. Der Benutzer weiß nicht, was es bedeutet, aber noch schlimmer, der Entwickler des Filters weiß es auch nicht. Wie viele Punkte sollte eine E-Mail für das Wort "sex" erhalten? Eine Wahrscheinlichkeit kann natürlich falsch sein, aber es gibt wenig Mehrdeutigkeit darüber, was sie bedeutet oder wie Beweise kombiniert werden sollten, um sie zu berechnen. Basierend auf meinem Korpus zeigt "sex" eine Wahrscheinlichkeit von .97 an, dass die enthaltene E-Mail Spam ist, während "sexy" eine Wahrscheinlichkeit von .99 anzeigt. Und Bayes' Regel, die ebenso eindeutig ist, besagt, dass eine E-Mail, die beide Wörter enthält, in der (unwahrscheinlichen) Abwesenheit anderer Beweise eine 99,97 %ige Chance hat, Spam zu sein.

Da es Wahrscheinlichkeiten misst, berücksichtigt der bayesianische Ansatz alle Beweise in der E-Mail, sowohl gute als auch schlechte. Wörter, die überproportional selten in Spam vorkommen (wie "obwohl" oder "heute Abend" oder "offensichtlich"), tragen ebenso viel zur Verringerung der Wahrscheinlichkeit bei wie schlechte Wörter wie "abmelden" und "eintragen" zur Erhöhung. Daher wird eine ansonsten harmlose E-Mail, die zufällig das Wort "sex" enthält, nicht als Spam markiert.

Idealerweise sollten die Wahrscheinlichkeiten natürlich individuell für jeden Benutzer berechnet werden. Ich erhalte viele E-Mails, die das Wort "Lisp" enthalten, und (bisher) keinen Spam, der das tut. Ein solches Wort ist also effektiv eine Art Passwort, um mir Mails zu senden. In meiner früheren Spam-Filter-Software konnte der Benutzer eine Liste solcher Wörter einrichten, und Mails, die sie enthielten, würden automatisch die Filter passieren. Auf meiner Liste habe ich Wörter wie "Lisp" und auch meine Postleitzahl gesetzt, damit (ansonsten ziemlich spammy klingende) Quittungen von Online-Bestellungen durchkommen. Ich dachte, ich wäre sehr clever, aber ich stellte fest, dass der bayesianische Filter dasselbe für mich tat und zudem viele Wörter entdeckte, an die ich nicht gedacht hatte.

Als ich zu Beginn sagte, dass unsere Filter weniger als 5 Spams pro 1000 mit 0 falschen Positiven durchlassen, spreche ich von der Filterung meiner Mails basierend auf einem Korpus meiner Mails. Aber diese Zahlen sind nicht irreführend, denn das ist der Ansatz, den ich befürworte: die Mails jedes Benutzers basierend auf dem Spam- und Nicht-Spam-Mail, die er erhält, zu filtern. Im Wesentlichen sollte jeder Benutzer zwei Löschtasten haben, gewöhnliches Löschen und Löschen als Spam. Alles, was als Spam gelöscht wird, geht in den Spam-Korpus, und alles andere geht in den Nicht-Spam-Korpus.

Sie könnten Benutzer mit einem Seed-Filter starten, aber letztendlich sollte jeder Benutzer seine eigenen pro-Wort-Wahrscheinlichkeiten basierend auf der tatsächlichen Mail, die er erhält, haben. Dies (a) macht die Filter effektiver, (b) lässt jeden Benutzer seine eigene präzise Definition von Spam festlegen, und (c) vielleicht am besten von allem, macht es Spammern schwer, Mails so abzustimmen, dass sie die Filter passieren. Wenn ein großer Teil des Gehirns des Filters in den individuellen Datenbanken ist, dann wird das bloße Abstimmen von Spams, um durch die Seed-Filter zu gelangen, nichts garantieren, wie gut sie durch die variierenden und viel besser trainierten Filter einzelner Benutzer gelangen.

Inhaltsbasiertes Spam-Filtering wird oft mit einer Whitelist kombiniert, einer Liste von Absendern, deren Mails ohne Filterung akzeptiert werden können. Eine einfache Möglichkeit, eine solche Whitelist zu erstellen, besteht darin, eine Liste jeder Adresse zu führen, an die der Benutzer jemals eine Mail gesendet hat. Wenn ein Mail-Reader eine Löschen-als-Spam-Taste hat, könnten Sie auch die Absenderadresse jeder E-Mail hinzufügen, die der Benutzer als gewöhnlichen Müll gelöscht hat.

Ich bin ein Befürworter von Whitelists, aber mehr als eine Möglichkeit, Berechnungen zu sparen, als eine Möglichkeit, das Filtern zu verbessern. Früher dachte ich, dass Whitelists das Filtern erleichtern würden, weil Sie nur E-Mails von Personen filtern müssten, von denen Sie noch nie gehört haben, und jemand, der Ihnen zum ersten Mal eine Mail sendet, ist durch Konvention in dem, was er Ihnen sagen kann, eingeschränkt. Jemand, den Sie bereits kennen, könnte Ihnen eine E-Mail über Sex senden, aber jemand, der Ihnen zum ersten Mal eine Mail sendet, würde das wahrscheinlich nicht tun. Das Problem ist, dass Menschen mehr als eine E-Mail-Adresse haben können, sodass eine neue Absenderadresse nicht garantiert, dass der Absender Ihnen zum ersten Mal schreibt. Es ist nicht ungewöhnlich, dass ein alter Freund (insbesondere wenn er ein Hacker ist) Ihnen plötzlich eine E-Mail mit einer neuen Absenderadresse sendet, sodass Sie das Risiko falscher Positiver nicht eingehen können, indem Sie Mails von unbekannten Adressen besonders streng filtern.

In gewissem Sinne verkörpern meine Filter jedoch selbst eine Art Whitelist (und Blacklist), da sie auf gesamten Nachrichten basieren, einschließlich der Header. Insofern "wissen" sie die E-Mail-Adressen vertrauenswürdiger Absender und sogar die Routen, auf denen Mails von ihnen zu mir gelangen. Und sie wissen dasselbe über Spam, einschließlich der Servernamen, Mailer-Versionen und Protokolle.

Wenn ich dachte, dass ich die aktuellen Spam-Filterraten aufrechterhalten könnte, würde ich dieses Problem als gelöst betrachten. Aber es bedeutet nicht viel, die meisten heutigen Spams filtern zu können, denn Spam entwickelt sich weiter. Tatsächlich waren die meisten Antispam-Techniken bisher wie Pestizide, die nichts weiter tun, als eine neue, resistente Variante von Schädlingen zu schaffen.

Ich bin optimistischer in Bezug auf bayesianische Filter, weil sie sich mit dem Spam weiterentwickeln. Wenn Spammer also anfangen, "c0ck" anstelle von "cock" zu verwenden, um einfache Spam-Filter, die auf einzelnen Wörtern basieren, zu umgehen, bemerken bayesianische Filter das automatisch. Tatsächlich ist "c0ck" weitaus belastender als "cock", und bayesianische Filter wissen genau, wie viel mehr.

Dennoch muss jeder, der einen Plan zur Spam-Filterung vorschlägt, die Frage beantworten können: Wenn die Spammer genau wüssten, was Sie tun, wie gut könnten sie an Ihnen vorbeikommen? Zum Beispiel denke ich, dass, wenn die auf Checksummen basierende Spam-Filterung ein ernsthaftes Hindernis wird, die Spammer einfach auf Mad-Lib-Techniken umschalten werden, um Nachrichteninhalte zu generieren.

Um bayesianische Filter zu überlisten, wäre es nicht genug für Spammer, ihre E-Mails einzigartig zu machen oder die Verwendung einzelner unanständiger Wörter einzustellen. Sie müssten ihre Mails von Ihrer gewöhnlichen Mail ununterscheidbar machen. Und das, denke ich, würde sie erheblich einschränken. Spam sind hauptsächlich Verkaufsangebote, also es sei denn, Ihre reguläre Mail sind alles Verkaufsangebote, werden Spams unvermeidlich einen anderen Charakter haben. Und die Spammer müssten natürlich auch ihre gesamte Infrastruktur ändern (und weiterhin ändern), denn andernfalls würden die Header für die bayesianischen Filter so schlecht aussehen wie eh und je, egal was sie mit dem Nachrichteninhalt tun. Ich weiß nicht genug über die Infrastruktur, die Spammer verwenden, um zu wissen, wie schwer es wäre, die Header unschuldig aussehen zu lassen, aber ich schätze, dass es sogar schwieriger wäre, als die Nachricht unschuldig aussehen zu lassen.

Vorausgesetzt, sie könnten das Problem der Header lösen, wird der Spam der Zukunft wahrscheinlich so aussehen:

Hey there. Thought you should check out the following: http://www.27meg.com/foo

Denn das ist ungefähr so viel Verkaufsangebot, wie die inhaltsbasierte Filterung dem Spammer Raum lässt. (Tatsächlich wird es sogar schwer sein, dies an den Filtern vorbeizubekommen, denn wenn alles andere in der E-Mail neutral ist, wird die Spam-Wahrscheinlichkeit von der URL abhängen, und es wird einige Mühe kosten, diese neutral aussehen zu lassen.)

Spammer reichen von Unternehmen, die sogenannte Opt-in-Listen führen und nicht einmal versuchen, ihre Identität zu verbergen, bis hin zu Typen, die Mail-Server kapern, um Spams zu versenden, die Pornoseiten bewerben. Wenn wir das Filtern nutzen, um ihre Optionen auf Mails wie die oben genannte zu reduzieren, sollte das die Spammer am "legitimen" Ende des Spektrums aus dem Geschäft drängen; sie fühlen sich durch verschiedene staatliche Gesetze verpflichtet, Standardtexte darüber einzufügen, warum ihr Spam kein Spam ist, und wie man sein "Abonnement" kündigt, und solche Texte sind leicht zu erkennen.

(Ich dachte früher, es sei naiv zu glauben, dass strengere Gesetze Spam verringern würden. Jetzt denke ich, dass, während strengere Gesetze die Menge an Spam, die Spammer versenden, nicht verringern mögen, sie sicherlich den Filtern helfen können, die Menge an Spam zu verringern, die die Empfänger tatsächlich sehen.)

Über das gesamte Spektrum hinweg, wenn Sie die Verkaufsangebote, die Spammer machen können, einschränken, werden Sie sie unvermeidlich aus dem Geschäft drängen. Dieses Wort Geschäft ist wichtig zu merken. Die Spammer sind Geschäftsleute. Sie senden Spam, weil es funktioniert. Es funktioniert, weil die Rücklaufquote abscheulich niedrig ist (im besten Fall 15 pro Million, im Vergleich zu 3000 pro Million für einen Katalogversand), die Kosten für sie jedoch praktisch nichts betragen. Die Kosten sind enorm für die Empfänger, etwa 5 Mannwochen für jede Million Empfänger, die eine Sekunde damit verbringen, den Spam zu löschen, aber der Spammer muss das nicht bezahlen.

Spam zu senden kostet den Spammer jedoch etwas, [2]. Je niedriger wir die Rücklaufquote bekommen können – sei es durch Filtern oder durch die Verwendung von Filtern, um Spammer zu zwingen, ihre Angebote zu verdünnen – desto weniger Unternehmen werden es als lohnenswert erachten, Spam zu senden.

Der Grund, warum die Spammer die Arten von Verkaufsangeboten verwenden, die sie tun, ist, um die Rücklaufquoten zu erhöhen. Dies ist möglicherweise sogar noch widerlicher, als in den Kopf eines Spammers zu schauen, aber lassen Sie uns einen kurzen Blick in den Kopf von jemandem werfen, der auf einen Spam antwortet. Diese Person ist entweder erstaunlich glaubensselig oder tief in der Verleugnung über ihre sexuellen Interessen. In beiden Fällen, so abstoßend oder idiotisch der Spam uns auch erscheinen mag, ist er für sie aufregend. Die Spammer würden diese Dinge nicht sagen, wenn sie nicht aufregend klängen. Und "dachte, du solltest dir Folgendes ansehen" wird bei dem Spam-Empfänger nicht annähernd so viel Anziehungskraft haben wie die Arten von Dingen, die Spammer jetzt sagen. Ergebnis: Wenn es keine aufregenden Verkaufsangebote enthalten kann, wird Spam als Marketinginstrument weniger effektiv, und weniger Unternehmen wollen es nutzen.

Das ist am Ende der große Gewinn. Ich begann, Spam-Filter-Software zu schreiben, weil ich mir die Sachen nicht mehr ansehen wollte. Aber wenn wir gut genug darin werden, Spam herauszufiltern, wird es aufhören zu funktionieren, und die Spammer werden tatsächlich aufhören, ihn zu senden.

Von allen Ansätzen zur Bekämpfung von Spam, von Software bis zu Gesetzen, glaube ich, dass bayesianisches Filtern das effektivste sein wird. Aber ich denke auch, dass je mehr verschiedene Arten von Antispam-Bemühungen wir unternehmen, desto besser, denn jede Maßnahme, die Spammer einschränkt, wird dazu tendieren, das Filtern zu erleichtern. Und selbst innerhalb der Welt des inhaltsbasierten Filterns denke ich, dass es eine gute Sache sein wird, wenn viele verschiedene Arten von Software gleichzeitig verwendet werden. Je mehr verschiedene Filter es gibt, desto schwieriger wird es für Spammer, Spams so abzustimmen, dass sie durch sie hindurchkommen.

Anhang: Beispiele für Filterung

Hier ist ein Beispiel für einen Spam, der ankam, während ich diesen Artikel schrieb. Die fünfzehn interessantesten Wörter in diesem Spam sind:

qvp0045 indira mx-05 intimail $7500 freeyankeedom cdo bluefoxmedia jpg unsecured platinum 3d0 qves 7c5 7c266675

Die Wörter sind eine Mischung aus Dingen aus den Headern und aus dem Nachrichteninhalt, was typisch für Spam ist. Auch typisch für Spam ist, dass jedes dieser Wörter in meiner Datenbank eine Spam-Wahrscheinlichkeit von .99 hat. Tatsächlich gibt es mehr als fünfzehn Wörter mit Wahrscheinlichkeiten von .99, und dies sind nur die ersten fünfzehn, die gesehen wurden.

Leider macht dies diese E-Mail zu einem langweiligen Beispiel für die Verwendung von Bayes' Regel. Um eine interessante Vielfalt von Wahrscheinlichkeiten zu sehen, müssen wir uns dieses tatsächlich ziemlich atypische Spam ansehen.

Die fünfzehn interessantesten Wörter in diesem Spam, mit ihren Wahrscheinlichkeiten, sind:


madam 0.99 promotion 0.99 republic 0.99 shortest 0.047225013 mandatory 0.047225013 standardization 0.07347802 sorry 0.08221981 supported 0.09019077
people's 0.09019077 enter 0.9075001 quality 0.8921298 organization 0.12454646 investment 0.8568143 very 0.14758544 valuable 0.82347786

Diesmal ist die Evidenz eine Mischung aus guten und schlechten. Ein Wort wie "shortest" ist fast ebenso viel Beweis für Unschuld wie ein Wort wie "madam" oder "promotion" für Schuld. Aber dennoch ist der Fall für Schuld stärker. Wenn Sie diese Zahlen gemäß Bayes' Regel kombinieren, beträgt die resultierende Wahrscheinlichkeit .9027.

"Madam" stammt offensichtlich von Spams, die mit "Sehr geehrter Herr oder Frau" beginnen. Sie sind nicht sehr häufig, aber das Wort "madam" kommt nie in meinen legitimen E-Mails vor, und es geht alles um das Verhältnis.

"Republic" hat einen hohen Wert, weil es oft in nigerianischen Betrugs-E-Mails auftaucht und auch einmal oder zweimal in Spams vorkommt, die sich auf Korea und Südafrika beziehen. Man könnte sagen, dass es ein Zufall ist, dass es so hilft, diesen Spam zu identifizieren. Aber ich habe festgestellt, dass es bei der Untersuchung von Spam-Wahrscheinlichkeiten viele solcher Zufälle gibt, und sie haben eine unheimliche Tendenz, die Dinge in die richtige Richtung zu drücken, anstatt in die falsche. In diesem Fall ist es kein reiner Zufall, dass das Wort "Republic" in nigerianischen Betrugs-E-Mails und diesem Spam vorkommt. Es gibt eine ganze Klasse von zweifelhaften Geschäftsvorschlägen, die weniger entwickelte Länder betreffen, und diese haben wiederum eher Namen, die ausdrücklich (weil sie es nicht sind) angeben, dass sie Republiken sind.[3]

Andererseits ist "enter" ein echtes Missverständnis. Es kommt hauptsächlich in Abmeldeanweisungen vor, wird hier aber auf völlig harmlose Weise verwendet. Glücklicherweise ist der statistische Ansatz ziemlich robust und kann eine ganze Menge Fehlschläge tolerieren, bevor die Ergebnisse durcheinander geraten.

Zum Vergleich finden Sie hier ein Beispiel für diesen seltenen Vogel, einen Spam, der die Filter passiert. Warum? Weil er rein zufällig mit Wörtern geladen ist, die in meiner tatsächlichen E-Mail vorkommen:


perl 0.01 python 0.01 tcl 0.01 scripting 0.01 morris 0.01 graham 0.01491078 guarantee 0.9762507 cgi 0.9734398 paul 0.027040077 quite 0.030676773 pop3
0.042199217 various 0.06080265 prices 0.9359873 managed 0.06451222 difficult 0.071706355

Hier gibt es ein paar gute Nachrichten. Erstens würde diese Mail wahrscheinlich nicht die Filter einer Person passieren, die nicht zufällig auf Programmiersprachen spezialisiert ist und einen guten Freund namens Morris hat. Für den durchschnittlichen Benutzer wären alle fünf Wörter hier neutral und würden nicht zur Spam-Wahrscheinlichkeit beitragen.

Zweitens denke ich, dass das Filtern basierend auf Wortpaaren (siehe unten) dieses hier gut erfassen könnte: "kosteneffektiv", "Einrichtungsgebühr", "Geld zurück" – ziemlich belastende Sachen. Und natürlich, wenn sie mich weiterhin spammen (oder ein Netzwerk, dem ich angehöre), würde "Hostex" selbst als Spam-Begriff erkannt werden.

Schließlich finden Sie hier eine harmlose E-Mail. Ihre fünfzehn interessantesten Wörter sind wie folgt:


continuation 0.01 describe 0.01 continuations 0.01 example 0.033600237 programming 0.05214485 i'm 0.055427782 examples 0.07972858 color 0.9189189
localhost 0.09883721 hi 0.116539136 california 0.84421706 same 0.15981844 spot 0.1654587 us-ascii 0.16804294 what 0.19212411

Die meisten der hier vorkommenden Wörter deuten darauf hin, dass die Mail harmlos ist. Es gibt zwei schlecht riechende Wörter, "color" (Spammer lieben farbige Schriftarten) und "California" (das in Testimonials und auch in Menüs in Formularen vorkommt), aber sie sind nicht genug, um offensichtlich harmlose Wörter wie "continuation" und "example" zu überwiegen.

Es ist interessant, dass "describe" so gründlich unschuldig bewertet wird. Es ist in keiner meiner 4000 Spams vorgekommen. Die Daten sind voller solcher Überraschungen. Eine der Dinge, die Sie lernen, wenn Sie Spam-Texte analysieren, ist, wie eng der Wortschatz ist, in dem Spammer operieren. Es ist diese Tatsache, zusammen mit dem ebenso charakteristischen Wortschatz der E-Mails eines einzelnen Benutzers, die bayesianisches Filtern zu einer guten Wette macht.

Anhang: Weitere Ideen

Eine Idee, die ich noch nicht ausprobiert habe, ist, basierend auf Wortpaaren oder sogar Tripeln zu filtern, anstatt auf einzelnen Wörtern. Dies sollte eine viel schärfere Schätzung der Wahrscheinlichkeit liefern. Zum Beispiel hat das Wort "offers" in meiner aktuellen Datenbank eine Wahrscheinlichkeit von .96. Wenn Sie die Wahrscheinlichkeiten auf Wortpaare basieren, würden Sie mit "special offers" und "valuable offers" Wahrscheinlichkeiten von .99 und sagen wir, "approach offers" (wie in "dieser Ansatz bietet") eine Wahrscheinlichkeit von .1 oder weniger erhalten.

Der Grund, warum ich das nicht getan habe, ist, dass das Filtern basierend auf einzelnen Wörtern bereits so gut funktioniert. Aber es bedeutet, dass es Raum gibt, die Filter zu verschärfen, wenn Spam schwieriger zu erkennen wird. (Seltsamerweise wäre ein Filter, der auf Wortpaaren basiert, in der Tat ein Markov-Ketten-Textgenerator, der rückwärts läuft.)

Spezifische Spam-Eigenschaften (z.B. die Empfängeradresse nicht im Feld "An:" zu sehen) haben natürlich einen Wert bei der Erkennung von Spam. Sie können in diesem Algorithmus berücksichtigt werden, indem sie als virtuelle Wörter behandelt werden. Ich werde dies wahrscheinlich in zukünftigen Versionen tun, zumindest für eine Handvoll der eklatantesten Spam-Indikatoren. Merkmals-erkennende Spam-Filter liegen in vielen Details richtig; was ihnen fehlt, ist eine übergreifende Disziplin zur Kombination von Beweisen.

Die Erkennung von Nicht-Spam-Eigenschaften könnte wichtiger sein als die Erkennung von Spam-Eigenschaften. Falsche Positive sind ein solches Problem, dass sie außergewöhnliche Maßnahmen erfordern. Ich werde wahrscheinlich in zukünftigen Versionen eine zweite Testebene hinzufügen, die speziell darauf ausgelegt ist, falsche Positive zu vermeiden. Wenn eine Mail diese zweite Filterebene auslöst, wird sie akzeptiert, selbst wenn ihre Spam-Wahrscheinlichkeit über der Schwelle liegt.

Ich erwarte nicht, dass diese zweite Filterebene bayesianisch ist. Sie wird unvermeidlich nicht nur ad hoc, sondern auch auf Vermutungen basieren, da die Anzahl der falschen Positiven nicht groß genug sein wird, um Muster zu erkennen. (Es ist ohnehin gut, wenn ein Backup-System nicht auf derselben Technologie wie das primäre System basiert.)

Eine weitere Sache, die ich in Zukunft ausprobieren könnte, ist, bestimmten Teilen der E-Mail besondere Aufmerksamkeit zu schenken. Zum Beispiel enthält etwa 95 % des aktuellen Spams die URL einer Seite, die sie möchten, dass Sie besuchen. (Die verbleibenden 5 % möchten, dass Sie eine Telefonnummer anrufen, per E-Mail oder an eine US-Mail-Adresse antworten oder in einigen Fällen eine bestimmte Aktie kaufen.) Die URL ist in solchen Fällen praktisch allein ausreichend, um zu bestimmen, ob die E-Mail Spam ist.

Domainnamen unterscheiden sich von dem Rest des Textes in einer (nicht-deutschen) E-Mail darin, dass sie oft aus mehreren Wörtern bestehen, die zusammengefügt sind. Obwohl es im allgemeinen Fall rechenintensiv ist, könnte es sich lohnen, sie zu zerlegen. Wenn ein Filter das Token "xxxporn" noch nie gesehen hat, hat es eine individuelle Spam-Wahrscheinlichkeit von .4, während "xxx" und "porn" einzeln Wahrscheinlichkeiten (in meinem Korpus) von .9889 und .99 haben und eine kombinierte Wahrscheinlichkeit von .9998.

Ich erwarte, dass das Zerlegen von Domainnamen wichtiger wird, da Spammer allmählich gezwungen werden, belastende Wörter im Text ihrer Nachrichten zu vermeiden. (Eine URL mit einer IP-Adresse ist natürlich ein äußerst belastendes Zeichen, es sei denn, es handelt sich um die Mail eines Sysadmins.)

Es könnte eine gute Idee sein, eine kooperativ geführte Liste von URLs zu haben, die von Spammern beworben werden. Wir bräuchten eine Vertrauensmetrik, wie sie von Raph Levien untersucht wurde, um böswillige oder inkompetente Einreichungen zu verhindern, aber wenn wir so etwas hätten, würde es jeder Filtersoftware einen Schub geben. Es wäre auch eine bequeme Grundlage für Boykotte.

Eine weitere Möglichkeit, zweifelhafte URLs zu testen, wäre, einen Crawler loszuschicken, um die Seite zu betrachten, bevor der Benutzer die E-Mail, die sie erwähnt, ansieht. Sie könnten einen bayesianischen Filter verwenden, um die Seite zu bewerten, genau wie Sie es mit einer E-Mail tun würden, und alles, was auf der Seite gefunden wurde, könnte in die Berechnung der Wahrscheinlichkeit einfließen, dass die E-Mail Spam ist. Eine URL, die zu einer Weiterleitung führte, wäre natürlich besonders verdächtig.

Ein kooperatives Projekt, von dem ich denke, dass es wirklich eine gute Idee wäre, wäre, einen riesigen Korpus von Spam anzusammeln. Ein großer, sauberer Korpus ist der Schlüssel, um bayesianisches Filtern gut funktionieren zu lassen. Bayesianische Filter könnten den Korpus tatsächlich als Eingabe verwenden. Aber ein solcher Korpus wäre auch für andere Arten von Filtern nützlich, da er verwendet werden könnte, um sie zu testen.

Die Erstellung eines solchen Korpus wirft einige technische Probleme auf. Wir bräuchten Vertrauensmetriken, um böswillige oder inkompetente Einreichungen zu verhindern, natürlich. Wir bräuchten auch Möglichkeiten, persönliche Informationen (nicht nur Adressen und Cc, sondern auch z.B. die Argumente für Abmelde-URLs, die oft die Adresse kodieren) aus Mails im Korpus zu löschen. Wenn jemand dieses Projekt übernehmen möchte, wäre es eine gute Sache für die Welt.

Anhang: Spam definieren

Ich denke, es gibt einen groben Konsens darüber, was Spam ist, aber es wäre nützlich, eine explizite Definition zu haben. Wir müssen dies tun, wenn wir einen zentralen Korpus von Spam etablieren oder sogar die Spam-Filterraten sinnvoll vergleichen wollen.

Um zu beginnen, Spam ist nicht unerwünschte kommerzielle E-Mail. Wenn jemand in meiner Nachbarschaft gehört hat, dass ich nach einem alten Raleigh-Dreigangrad in gutem Zustand suche und mir eine E-Mail schickt, in der er mir anbietet, mir eines zu verkaufen, wäre ich begeistert, und doch wäre diese E-Mail sowohl kommerziell als auch unerwünscht. Das definierende Merkmal von Spam (tatsächlich seine raison d'être) ist nicht, dass es unerwünscht ist, sondern dass es automatisiert ist.

Es ist auch nur zufällig, dass Spam normalerweise kommerziell ist. Wenn jemand damit beginnen würde, Massene-Mails zu senden, um eine politische Sache zu unterstützen, wäre das beispielsweise ebenso Spam wie E-Mails, die eine Pornoseite bewerben.

Ich schlage vor, Spam als unerwünschte automatisierte E-Mail zu definieren. Diese Definition umfasst somit einige E-Mails, die viele gesetzliche Definitionen von Spam nicht berücksichtigen. Gesetzliche Definitionen von Spam, die vermutlich von Lobbyisten beeinflusst sind, neigen dazu, Mails auszuschließen, die von Unternehmen gesendet werden, die eine "bestehende Beziehung" zum Empfänger haben. Aber etwas von einem Unternehmen zu kaufen, impliziert beispielsweise nicht, dass Sie fortlaufende E-Mails von ihnen angefordert haben. Wenn ich etwas von einem Online-Shop bestelle und sie mir dann einen Strom von Spam senden, ist es immer noch Spam.

Unternehmen, die Spam senden, geben Ihnen oft die Möglichkeit, sich "abzumelden" oder bitten Sie, auf ihre Seite zu gehen und Ihre "Kontoeinstellungen" zu ändern, wenn Sie aufhören möchten, Spam zu erhalten. Das reicht nicht aus, um die Mail davon abzuhalten, Spam zu sein. Nicht abzumelden ist nicht dasselbe wie sich anzumelden. Es sei denn, der Empfänger hat ausdrücklich ein deutlich gekennzeichnetes Kästchen angekreuzt (dessen Standard nein war), in dem er um den Erhalt der E-Mail bittet, dann ist es Spam.

In einigen Geschäftsbeziehungen fordern Sie bestimmte Arten von Mails implizit an. Wenn Sie online bestellen, denke ich, fordern Sie implizit eine Quittung und eine Benachrichtigung an, wenn die Bestellung versendet wird. Ich habe nichts dagegen, wenn Verisign mir eine Mail sendet, in der gewarnt wird, dass ein Domainname kurz vor dem Ablauf steht (zumindest, wenn sie der tatsächliche Registrar dafür sind). Aber wenn Verisign mir eine E-Mail sendet, in der sie einen KOSTENLOSEN Leitfaden zum Aufbau meiner E-Commerce-Website anbieten, ist das Spam.

Hinweise:

[1] Die Beispiele in diesem Artikel sind in Common Lisp übersetzt, um, glauben Sie es oder nicht, die Zugänglichkeit zu erhöhen. Die hier beschriebene Anwendung ist eine, die wir geschrieben haben, um einen neuen Lisp-Dialekt namens Arc zu testen, der noch nicht veröffentlicht ist.

[2] Derzeit scheint die niedrigste Rate etwa 200 US-Dollar zu betragen, um eine Million Spams zu senden. Das ist sehr billig, 1/50 Cent pro Spam. Aber das Herausfiltern von 95 % Spam würde beispielsweise die Kosten für die Spammer, ein bestimmtes Publikum zu erreichen, um den Faktor 20 erhöhen. Nur wenige können Margen haben, die groß genug sind, um das zu absorbieren.

[3] Als Faustregel gilt: Je mehr Qualifikatoren es vor dem Namen eines Landes gibt, desto korrupt sind die Herrscher. Ein Land namens Die Sozialistische Volksdemokratische Republik von X ist wahrscheinlich der letzte Ort auf der Welt, an dem Sie leben möchten.

Danke an Sarah Harlin für das Lesen von Entwürfen; Daniel Giffin (der auch den Produktions-Arc-Interpreter schreibt) für mehrere gute Ideen zum Filtern und für die Erstellung unserer Mail-Infrastruktur; Robert Morris, Trevor Blackwell und Erann Gat für viele Diskussionen über Spam; Raph Levien für Ratschläge zu Vertrauensmetriken; und Chip Coldwell und Sam Steingold für Ratschläge zu Statistiken.

Sie finden diesen Aufsatz und 14 weitere in [

Hackers & Painters

](http://www.amazon.com/gp/product/0596006624) .