EIN PLAN GEGEN SPAM

August 2002

(Dieser Artikel beschreibt die Spamfiltertechniken, die in dem spamsicheren webbasierten Mail-Reader verwendet werden, den wir zum Testen von Arc entwickelt haben. Ein verbesserter Algorithmus wird in „Bessere Bayes-Filterung “ beschrieben.)

Ich glaube, dass es möglich ist, Spam zu stoppen, und dass inhaltsbasierte Filter der Weg dorthin sind. Die Achillesferse der Spammer ist ihre Botschaft. Sie können jede andere Barriere umgehen, die man aufstellt. Zumindest haben sie das bisher geschafft. Aber sie müssen ihre Botschaft übermitteln, was auch immer sie ist. Wenn wir Software schreiben können, die ihre Botschaften erkennt, kommen sie nicht mehr daran vorbei.

Für den Empfänger ist Spam leicht zu erkennen. Wenn Sie jemanden damit beauftragen würden, Ihre E-Mails zu lesen und den Spam zu löschen, hätte er damit keine Probleme. Wie viel müssen wir – abgesehen von KI – tun, um diesen Prozess zu automatisieren?

Ich denke, wir werden das Problem mit relativ einfachen Algorithmen lösen können. Tatsächlich habe ich herausgefunden, dass man heutigen Spam ganz gut filtern kann, indem man lediglich die Spamwahrscheinlichkeiten einzelner Wörter mit einer Bayes-Kombination kombiniert. Mit einem leicht angepassten (wie unten beschrieben) Bayes-Filter entgehen uns jetzt weniger als 5 von 1000 Spams und es gibt 0 Fehlalarme.

Der statistische Ansatz ist normalerweise nicht der erste, den Leute ausprobieren, wenn sie Spamfilter schreiben. Der erste Instinkt der meisten Hacker ist, Software zu schreiben, die die individuellen Eigenschaften von Spam erkennt. Man sieht sich Spams an und denkt sich: Was für eine Frechheit diese Typen, mir eine Mail zu schicken, die mit „Lieber Freund“ beginnt oder deren Betreffzeile komplett in Großbuchstaben geschrieben ist und mit acht Ausrufezeichen endet. Ich kann das Zeug mit etwa einer Zeile Code herausfiltern.

Und das tun Sie, und am Anfang funktioniert es. Mit ein paar einfachen Regeln können Sie Ihren eingehenden Spam erheblich eindämmen. Wenn Sie nur nach dem Wort „Klick“ suchen, werden 79,7 % der E-Mails in meinem Spam-Korpus abgefangen, wobei nur 1,2 % falsch-positive Ergebnisse vorliegen.

Ich habe etwa sechs Monate damit verbracht, Software zu schreiben, die nach einzelnen Spam-Merkmalen sucht, bevor ich den statistischen Ansatz ausprobierte. Dabei stellte ich fest, dass es sehr schwierig wurde, die letzten paar Prozent Spam zu erkennen, und dass ich mehr Fehlalarme bekam, je strenger ich die Filter einstellte.

Falsche Positivmeldungen sind harmlose E-Mails, die fälschlicherweise als Spam identifiziert werden. Für die meisten Benutzer ist es viel schlimmer, legitime E-Mails zu übersehen, als Spam zu erhalten. Ein Filter, der falsche Positivmeldungen liefert, ist also wie ein Aknemittel, das für den Patienten tödlich sein kann.

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

Ich weiß nicht, warum ich den statistischen Ansatz so lange vermieden habe. Ich glaube, es lag daran, dass ich süchtig danach geworden bin, selbst Spam-Merkmale zu identifizieren, als würde ich eine Art Wettkampfspiel mit den Spammern spielen. (Nichthacker erkennen das oft nicht, aber die meisten Hacker sind sehr wettbewerbsorientiert.) Als ich die statistische Analyse ausprobierte, stellte ich sofort fest, dass sie viel schlauer war als ich. Sie stellte natürlich fest, dass Begriffe wie „virtumundo“ und „teens“ gute Indikatoren für Spam waren. Aber sie stellte auch fest, dass „per“ und „FL“ und „ff0000“ gute Indikatoren für Spam sind. Tatsächlich erwies sich „ff0000“ (html für leuchtendes Rot) als ein ebenso guter Indikator für Spam wie jeder pornografische Begriff.

Hier ist eine Skizze, wie ich statistische Filterung durchführe. Ich beginne mit einem Korpus für Spam und einem für Nicht-Spam-Mails. Im Moment enthält jeder Korpus 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 Token und alles andere als Token-Trennzeichen. (Hier besteht wahrscheinlich noch Verbesserungsbedarf.) Ich ignoriere Token, die nur aus Ziffern bestehen, und ich ignoriere auch HTML-Kommentare und betrachte sie nicht einmal als Token-Trennzeichen.

Ich zähle, wie oft jedes Token (derzeit ohne Berücksichtigung der Groß- und Kleinschreibung) in jedem Korpus vorkommt. An diesem Punkt habe ich zwei große Hash-Tabellen, eine für jedes Korpus, die Token der Anzahl der Vorkommen zuordnen.

Als nächstes erstelle ich eine dritte Hash-Tabelle und ordne diesmal jedem Token die Wahrscheinlichkeit zu, dass es sich bei der E-Mail, die es enthält, um Spam handelt. Diese Wahrscheinlichkeit berechne ich wie folgt [1]:

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

Dabei ist „word“ das Token, dessen Wahrscheinlichkeit wir berechnen, „good“ und „bad“ sind die Hash-Tabellen, die ich im ersten Schritt erstellt habe, und „ngood“ und „nbad“ sind die Anzahl der Nicht-Spam- bzw. Spam-Nachrichten.

Ich habe dies als Code erklärt, um ein paar wichtige Details zu zeigen. Ich möchte die Wahrscheinlichkeiten leicht verzerren, um falsche Positivwerte zu vermeiden, und durch Ausprobieren habe ich herausgefunden, dass eine gute Möglichkeit, dies zu tun, darin besteht, 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 berücksichtige nur Wörter, die insgesamt mehr als fünfmal vorkommen (tatsächlich würde aufgrund der Verdoppelung ein dreimaliges Vorkommen in Nicht-Spam-Mails ausreichen). Und dann ist da noch die Frage, welche Wahrscheinlichkeit Wörtern zugewiesen werden soll, die in einem Korpus vorkommen, aber nicht in dem anderen. Wieder durch Ausprobieren habe ich 0,01 und 0,99 gewählt. Hier besteht möglicherweise Spielraum für Feinabstimmungen, aber wenn das Korpus wächst, erfolgt eine solche Feinabstimmung ohnehin automatisch.

Besonders aufmerksame Personen werden bemerken, dass ich zwar jedes Korpus als einen einzigen langen Textstrom betrachte, um die Vorkommen zu zählen, aber als Divisor für die Berechnung der Spamwahrscheinlichkeit die Anzahl der E-Mails in jedem Korpus und nicht ihre Gesamtlänge verwende. Dies führt zu einer weiteren leichten Verzerrung zum Schutz vor Fehlalarmen.

Wenn neue E-Mails eintreffen, werden sie in Tokens gescannt und die interessantesten fünfzehn Tokens (wobei die Interessantheit daran gemessen wird, wie weit ihre Spamwahrscheinlichkeit von einem neutralen Wert von 0,5 abweicht) werden verwendet, um die Wahrscheinlichkeit zu berechnen, dass es sich bei der E-Mail um Spam handelt. Wenn probs eine Liste der fünfzehn Einzelwahrscheinlichkeiten ist, berechnen Sie die kombinierte Wahrscheinlichkeit folgendermaßen:

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

In der Praxis stellt sich die Frage, welche Wahrscheinlichkeit man einem Wort zuordnen soll, das man noch nie gesehen hat, also einem Wort, das in der Hash-Tabelle der Wortwahrscheinlichkeiten nicht vorkommt. Ich habe, wiederum durch Ausprobieren, herausgefunden, dass 0,4 ein guter Wert ist. Wenn man ein Wort noch nie gesehen hat, ist es wahrscheinlich ziemlich harmlos; Spam-Wörter sind einem in der Regel nur allzu vertraut.

Im Anhang am Ende finden Sie Beispiele für die Anwendung dieses Algorithmus auf echte E-Mails.

Ich behandle E-Mails als Spam, wenn der obige Algorithmus eine Wahrscheinlichkeit von mehr als 0,9 dafür festlegt, dass es sich um Spam handelt. In der Praxis würde es jedoch keine große Rolle spielen, wo ich diesen Schwellenwert ansetze, da nur wenige Wahrscheinlichkeiten im mittleren Bereich liegen.

Ein großer Vorteil des statistischen Ansatzes ist, dass man nicht so viele Spams lesen muss. In den letzten sechs Monaten habe ich buchstäblich Tausende von Spams gelesen, und das ist wirklich ziemlich demoralisierend. Norbert Wiener sagte, wer mit Sklaven konkurriert, wird selbst zum Sklaven, und der Wettbewerb mit Spammern hat etwas ähnlich Erniedrigendes. Um einzelne Spam-Merkmale zu erkennen, muss man 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.

Der eigentliche Vorteil des Bayes-Ansatzes ist natürlich, dass Sie wissen, was Sie messen. Filter mit Merkmalserkennung wie SpamAssassin weisen E-Mails einen Spam-„Score“ zu. Der Bayes-Ansatz weist eine tatsächliche Wahrscheinlichkeit zu. Das Problem mit einem „Score“ ist, dass niemand weiß, was er bedeutet. Der Benutzer weiß nicht, was er bedeutet, aber schlimmer noch, der Entwickler des Filters weiß es auch nicht. Wie viele Punkte sollte eine E-Mail bekommen, wenn sie das Wort „Sex“ enthält? Eine Wahrscheinlichkeit kann natürlich falsch sein, aber es gibt wenig Zweideutigkeit darüber, was sie bedeutet oder wie Beweise kombiniert werden sollten, um sie zu berechnen. Basierend auf meinem Korpus gibt „Sex“ eine Wahrscheinlichkeit von 0,97 an, dass die enthaltene E-Mail Spam ist, während „sexy“ eine Wahrscheinlichkeit von 0,99 anzeigt. Und die Bayes-Regel, ebenso eindeutig, besagt, dass eine E-Mail, die beide Wörter enthält, in der (unwahrscheinlichen) Abwesenheit jeglicher anderer Beweise eine 99,97-prozentige Chance hat, Spam zu sein.

Da der Bayes-Ansatz Wahrscheinlichkeiten misst, berücksichtigt er alle Beweise in der E-Mail, sowohl gute als auch schlechte. Wörter, die in Spam unverhältnismäßig selten vorkommen (wie „obwohl“ oder „heute Abend“ oder „anscheinend“), tragen ebenso viel zur Verringerung der Wahrscheinlichkeit bei wie schlechte Wörter wie „abbestellen“ und „Opt-in“ zu ihrer Erhöhung beitragen. Eine ansonsten harmlose E-Mail, die zufällig das Wort „Sex“ enthält, wird also nicht als Spam markiert.

Idealerweise sollten die Wahrscheinlichkeiten natürlich für jeden Benutzer individuell berechnet werden. Ich bekomme viele E-Mails mit dem Wort „Lisp“ und (bisher) keinen Spam mit diesem Wort. Ein solches Wort ist also praktisch eine Art Passwort zum Senden von E-Mails an mich. In meiner früheren Spamfiltersoftware konnte der Benutzer eine Liste mit solchen Wörtern erstellen, und E-Mails mit diesen Wörtern kamen automatisch durch die Filter. Auf meine Liste setzte ich Wörter wie „Lisp“ und auch meine Postleitzahl, damit (ansonsten eher nach Spam klingende) Quittungen von Online-Bestellungen durchkamen. Ich dachte, ich wäre sehr schlau, aber ich stellte fest, dass der Bayes-Filter dasselbe für mich tat und außerdem viele Wörter entdeckte, an die ich nicht gedacht hatte.

Als ich zu Beginn sagte, dass unsere Filter weniger als 5 Spams pro 1000 durchlassen und 0 Fehlalarme haben, meinte ich damit, dass ich meine E-Mails auf Grundlage eines Korpus meiner E-Mails filtere. Aber diese Zahlen sind nicht irreführend, denn das ist der Ansatz, den ich befürworte: Filtern Sie die E-Mails jedes Benutzers auf Grundlage der Spam- und Nichtspam-Mails, die er erhält. Im Wesentlichen sollte jeder Benutzer zwei Löschtasten haben: normales Löschen und Löschen als Spam. Alles, was als Spam gelöscht wird, wandert in den Spamkorpus, und alles andere wandert in den Nichtspamkorpus.

Sie könnten Benutzer mit einem Seed-Filter beginnen, aber letztendlich sollte jeder Benutzer seine eigenen Wahrscheinlichkeiten pro Wort haben, basierend auf der tatsächlichen E-Mail, die er erhält. Dies (a) macht die Filter effektiver, (b) lässt jeden Benutzer seine eigene genaue Definition von Spam festlegen und (c) macht es Spammern – vielleicht am besten – schwerer, E-Mails so zu optimieren, dass sie durch die Filter kommen. Wenn ein Großteil der Funktionsweise des Filters in den einzelnen Datenbanken steckt, dann ist die bloße Optimierung von Spams, damit sie durch die Seed-Filter kommen, keine Garantie dafür, wie gut sie durch die unterschiedlichen und viel besser trainierten Filter der einzelnen Benutzer kommen.

Inhaltsbasierte Spamfilterung wird oft mit einer Whitelist kombiniert, einer Liste von Absendern, deren E-Mails ohne Filterung akzeptiert werden. Eine einfache Möglichkeit, eine solche Whitelist zu erstellen, besteht darin, eine Liste aller Adressen zu führen, an die der Benutzer jemals E-Mails gesendet hat. Wenn ein E-Mail-Reader über eine Schaltfläche zum Löschen als Spam verfügt, können Sie auch die Absenderadresse aller E-Mails hinzufügen, die der Benutzer als normalen Papierkorb gelöscht hat.

Ich bin ein Befürworter von Whitelists, aber eher als Möglichkeit, Rechenleistung zu sparen, als als Möglichkeit, die Filterung zu verbessern. Früher dachte ich, dass Whitelists die Filterung einfacher machen würden, weil man dann nur E-Mails von Leuten filtern müsste, von denen man noch nie etwas gehört hat, und jemand, der einem zum ersten Mal eine E-Mail schickt, durch Konventionen in dem eingeschränkt ist, was er einem sagen darf. Jemand, den man bereits kennt, schickt einem vielleicht eine E-Mail, in der es um Sex geht, aber jemand, der einem zum ersten Mal eine E-Mail schickt, würde das wahrscheinlich nicht tun. Das Problem ist, dass Leute mehr als eine E-Mail-Adresse haben können, also ist eine neue Absenderadresse keine Garantie dafür, dass der Absender einem zum ersten Mal schreibt. Es ist nicht ungewöhnlich, dass ein alter Freund (besonders wenn er ein Hacker ist) einem plötzlich eine E-Mail mit einer neuen Absenderadresse schickt, also kann man keine Fehlalarme riskieren, indem man E-Mails von unbekannten Adressen besonders streng filtert.

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

Wenn ich glauben würde, dass ich die aktuelle Spamfilterrate aufrechterhalten könnte, würde ich dieses Problem als gelöst betrachten. Aber es bedeutet nicht viel, dass man den Großteil des heutigen Spams herausfiltern kann, denn Spam entwickelt sich weiter. Tatsächlich waren die meisten Antispam-Techniken bisher wie Pestizide, die nichts anderes bewirken, als einen neuen, resistenten Erregerstamm zu schaffen.

Ich bin optimistischer, was Bayesianische Filter angeht, denn sie entwickeln sich mit dem Spam weiter. Wenn Spammer also anfangen, „c0ck“ statt „cock“ zu verwenden, um einfältigen Spamfiltern, die auf einzelnen Wörtern basieren, zu entgehen, bemerken Bayesianische Filter das automatisch. Tatsächlich ist „c0ck“ ein weitaus belastenderer Beweis 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 Sie dann überwinden? Ich denke zum Beispiel, wenn die auf Prüfsummen basierende Spam-Filterung zu einem ernsthaften Hindernis wird, werden die Spammer einfach auf Mad-lib-Techniken zur Generierung von Nachrichtentexten umsteigen.

Um Bayesianische Filter zu überwinden, müssten Spammer ihre E-Mails nicht nur einzigartig machen oder einzelne anstößige Wörter vermeiden. Sie müssten ihre E-Mails so gestalten, dass sie von Ihren normalen E-Mails nicht zu unterscheiden sind. Und ich denke, das würde sie stark einschränken. Spam besteht hauptsächlich aus Verkaufsgesprächen. Wenn Ihre normalen E-Mails nicht nur aus Verkaufsgesprächen bestehen, werden Spams also zwangsläufig einen anderen Charakter haben. Und natürlich müssten die Spammer auch ihre gesamte Infrastruktur ändern (und ständig ändern), denn sonst würden die Header für die Bayesianischen Filter genauso schlecht aussehen wie immer, egal, was sie mit dem Nachrichtentext machen. Ich weiß nicht genug über die Infrastruktur, die Spammer verwenden, um zu wissen, wie schwierig es wäre, die Header harmlos aussehen zu lassen, aber ich schätze, es wäre sogar noch schwieriger, als die Nachricht harmlos aussehen zu lassen.

Vorausgesetzt, sie könnten das Problem der Header lösen, würde der Spam der Zukunft wahrscheinlich ungefähr so aussehen:

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

denn das ist ungefähr das Einzige, was Spammern durch inhaltsbasierte Filterung an Verkaufsargumenten übrig bleibt. (Tatsächlich wird es schwierig sein, dies überhaupt durch die Filter zu bekommen, denn wenn alles andere in der E-Mail neutral ist, hängt die Spamwahrscheinlichkeit von der URL ab und es wird einige Mühe kosten, diese neutral aussehen zu lassen.)

Zu den Spammern gehören Unternehmen, die sogenannte Opt-in-Listen betreiben und nicht einmal versuchen, ihre Identität zu verbergen, sowie Typen, die Mailserver kapern, um Spams zu verschicken, die für Pornoseiten werben. Wenn wir Filter verwenden, um ihre Optionen auf Mails wie die oben genannte zu reduzieren, sollte das die Spammer am „legitimen“ Ende des Spektrums ziemlich aus dem Geschäft drängen; sie fühlen sich durch verschiedene staatliche Gesetze verpflichtet, Standardtexte darüber zu verfassen, warum ihr Spam kein Spam ist und wie man sein „Abonnement“ kündigt, und solche Texte sind leicht zu erkennen.

(Früher hielt ich es für naiv zu glauben, dass strengere Gesetze die Spam-Menge verringern würden. Heute bin ich der Meinung, dass strengere Gesetze zwar nicht die Menge an Spam verringern, die Spammer versenden, aber sie können den Filtern sicherlich dabei helfen, die Menge an Spam zu verringern, die die Empfänger tatsächlich sehen.)

Wenn Sie die Verkaufsargumente der Spammer einschränken, werden Sie sie zwangsläufig aus dem Geschäft drängen. Das Wort Geschäft ist wichtig und sollte man sich merken. Spammer sind Geschäftsleute. Sie versenden Spam, weil es funktioniert. Es funktioniert, weil die Antwortrate zwar abscheulich niedrig ist (bestenfalls 15 pro Million, im Vergleich zu 3000 pro Million bei einem Katalogversand), die Kosten für sie jedoch praktisch nichts betragen. Für die Empfänger sind die Kosten enorm, etwa 5 Mannwochen pro Million Empfänger, die eine Sekunde damit verbringen, den Spam zu löschen, aber das muss der Spammer nicht bezahlen.

Allerdings kostet das Versenden von Spam den Spammer etwas. [2] Je niedriger also die Antwortrate ist – sei es durch Filterung oder indem wir die Spammer mit Filtern zwingen, ihre Angebote zu verwässern –, desto weniger Unternehmen werden es für sich lohnen, Spam zu versenden.

Der Grund, warum Spammer diese Art von Verkaufsmaschen verwenden, ist, die Antwortrate zu erhöhen. Das ist möglicherweise noch abstoßender, als in den Kopf eines Spammers zu schauen, aber werfen wir doch einmal einen kurzen Blick in den Kopf einer Person, die auf Spam reagiert . Diese Person ist entweder erstaunlich leichtgläubig oder leugnet ihre sexuellen Interessen zutiefst. In beiden Fällen ist der Spam, so abstoßend oder idiotisch er uns auch erscheinen mag, für sie ist er aufregend. Die Spammer würden diese Dinge nicht sagen, wenn sie nicht aufregend klingen würden. Und „Ich dachte, Sie sollten sich Folgendes ansehen“ wird beim Spam-Empfänger einfach nicht annähernd so viel Anklang finden wie die Art von Dingen, die Spammer heute sagen. Ergebnis: Wenn Spam keine aufregenden Verkaufsmaschen enthalten kann, wird es als Marketinginstrument weniger effektiv und weniger Unternehmen wollen es verwenden.

Das ist letztlich der große Gewinn. Ich habe angefangen, Spamfiltersoftware zu schreiben, weil ich mir das Zeug nicht mehr ansehen wollte. Aber wenn wir Spam gut genug herausfiltern können, wird es nicht mehr funktionieren und die Spammer werden tatsächlich aufhören, Spam zu versenden.

Von allen Ansätzen zur Spambekämpfung, von Software bis zu Gesetzen, halte ich die Bayessche Filterung für die effektivste. Ich denke aber auch, dass es besser ist, je mehr verschiedene Arten von Antispam-Maßnahmen wir ergreifen, denn jede Maßnahme, die Spammer einschränkt, erleichtert tendenziell das Filtern. Und selbst in der Welt der inhaltsbasierten Filterung halte ich es für gut, wenn viele verschiedene Arten von Software gleichzeitig verwendet werden. Je mehr verschiedene Filter es gibt, desto schwieriger wird es für Spammer, Spams so zu optimieren, dass sie durchkommen.

Anhang: Beispiele für Filterung

Hier ist ein Beispiel für Spam, der eintraf, 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 Inhalten aus den Kopfzeilen und dem Nachrichtentext, was typisch für Spam ist. Ebenfalls typisch für Spam ist, dass jedes dieser Wörter in meiner Datenbank eine Spamwahrscheinlichkeit von 0,99 hat. Tatsächlich gibt es mehr als fünfzehn Wörter mit einer Wahrscheinlichkeit von 0,99, und dies sind nur die ersten fünfzehn, die gesehen wurden.

Leider ist diese E-Mail dadurch ein langweiliges Beispiel für die Anwendung des Bayes-Prinzips. Um eine interessante Vielfalt an Wahrscheinlichkeiten zu sehen, müssen wir uns diesen eigentlich recht untypischen 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 sind die Beweise eine Mischung aus Gut und Böse. Ein Wort wie „kürzeste“ ist fast so sehr ein Beweis für Unschuld wie ein Wort wie „Frau“ oder „Beförderung“ ein Beweis für Schuld. Aber die Argumente für Schuld sind noch stärker. Wenn Sie diese Zahlen gemäß der Bayes-Regel kombinieren, ergibt sich eine Wahrscheinlichkeit von 0,9027.

„Madam“ stammt offensichtlich aus Spams, die mit „Sehr geehrte Damen und Herren“ beginnen. Diese kommen nicht sehr häufig vor, aber in meinen legitimen E-Mails kommt das Wort „Madam“ nie vor, und es kommt nur auf das Verhältnis an.

„Republik“ schneidet gut ab, weil es häufig in nigerianischen Betrugsmails auftaucht und auch ein- oder zweimal in Spams mit Bezug auf Korea und Südafrika vorkommt. Man könnte sagen, es sei ein Zufall, dass es auf diese Weise dabei hilft, diesen Spam zu identifizieren. Aber ich habe bei der Untersuchung der Spamwahrscheinlichkeiten festgestellt, dass es viele solcher Zufälle gibt und sie die unheimliche Tendenz haben, die Dinge in die richtige statt in die falsche Richtung zu lenken. In diesem Fall ist es kein reiner Zufall, dass das Wort „Republik“ in nigerianischen Betrugsmails und diesem Spam vorkommt. Es gibt eine ganze Klasse zweifelhafter Geschäftsvorschläge mit Bezug auf weniger entwickelte Länder, und diese wiederum haben eher Namen, die explizit angeben (weil sie es nicht sind), dass es sich um Republiken handelt.[3]

Andererseits ist „Enter“ ein echter Fehlschlag. Es kommt meistens in Abmeldeanweisungen vor, wird hier aber auf völlig harmlose Weise verwendet. Glücklicherweise ist der statistische Ansatz ziemlich robust und kann ziemlich viele Fehlschläge tolerieren, bevor die Ergebnisse verfälscht werden.

Zum Vergleich hier ein Beispiel für diesen seltenen Vogel, nämlich Spam, der durch die Filter kommt. Warum? Weil er durch puren Zufall mit Wörtern vollgestopft ist, die in meiner eigentlichen 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 Neuigkeiten. Erstens würde diese E-Mail wahrscheinlich nicht durch die Filter von jemandem kommen, der nicht zufällig auf Programmiersprachen spezialisiert ist und einen guten Freund namens Morris hat. Für den durchschnittlichen Benutzer wären alle fünf Top-Wörter hier neutral und würden nicht zur Spam-Wahrscheinlichkeit beitragen.

Zweitens denke ich, dass Filterung basierend auf Wortpaaren (siehe unten) diesen Begriff durchaus aufdecken könnte: „kostengünstig“, „Einrichtungsgebühr“, „Geld zurück“ – ziemlich belastendes Zeug. Und natürlich würde „Hostex“ selbst als Spambegriff erkannt werden, wenn sie mich (oder ein Netzwerk, dem ich angehöre) weiterhin mit Spam belästigen würden.

Zum Schluss noch eine harmlose E-Mail. Die fünfzehn interessantesten Wörter sind:

 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 Wörter hier deuten darauf hin, dass es sich um eine harmlose E-Mail handelt. Es gibt zwei übelriechende Wörter, „Farbe“ (Spammer lieben farbige Schriftarten) und „Kalifornien“ (das in Testimonials und auch in Menüs in Formularen vorkommt), aber sie reichen nicht aus, um offensichtlich harmlose Wörter wie „Fortsetzung“ und „Beispiel“ aufzuwiegen.

Es ist interessant, dass „describe“ als so vollkommen harmlos gilt. Es ist in keiner einzigen meiner 4000 Spam-Mails vorgekommen. Die Daten sind voller solcher Überraschungen. Eines der Dinge, die man lernt, wenn man Spam-Texte analysiert, ist, wie eng die Teilmenge der Sprache ist, in der Spammer agieren. Diese Tatsache, zusammen mit dem ebenso charakteristischen Vokabular der E-Mails jedes einzelnen Benutzers, macht die Bayes-Filterung zu einer guten Wahl.

Anhang: Weitere Ideen

Eine Idee, die ich noch nicht ausprobiert habe, ist, nach Wortpaaren oder sogar Wortdreifachen statt nach einzelnen Wörtern zu filtern. Dies sollte eine viel genauere Schätzung der Wahrscheinlichkeit ergeben. In meiner aktuellen Datenbank hat das Wort „Angebote“ beispielsweise eine Wahrscheinlichkeit von 0,96. Wenn Sie die Wahrscheinlichkeiten auf Wortpaaren basieren würden, hätten „Sonderangebote“ und „wertvolle Angebote“ Wahrscheinlichkeiten von 0,99 und beispielsweise „Annäherungsangebote“ (wie in „diese Annäherungsangebote“) eine Wahrscheinlichkeit von 0,1 oder weniger.

Der Grund, warum ich das nicht getan habe, ist, dass das Filtern auf Basis einzelner Wörter bereits so gut funktioniert. Es bedeutet aber, dass es Spielraum gibt, die Filter zu verschärfen, wenn Spam schwieriger zu erkennen wird. (Merkwürdigerweise wäre ein Filter auf Basis von Wortpaaren tatsächlich ein umgekehrt laufender Markow-Verkettungs-Textgenerator.)

Bestimmte Spam-Merkmale (z. B. das Nicht-Erkennen der Empfängeradresse im An:-Feld) sind natürlich für die Spam-Erkennung von Nutzen. 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 schwerwiegendsten Spam-Indikatoren. Spamfilter mit Merkmalserkennung haben in vielen Details recht; was ihnen fehlt, ist eine allgemeine Disziplin zum Kombinieren von Beweisen.

Das Erkennen von Nicht-Spam-Merkmalen ist möglicherweise wichtiger als das Erkennen von Spam-Merkmalen. Falschmeldungen sind so besorgniserregend, dass sie außergewöhnliche Maßnahmen erfordern. Ich werde in zukünftigen Versionen wahrscheinlich eine zweite Testebene hinzufügen, die speziell darauf ausgelegt ist, Falschmeldungen zu vermeiden. Wenn eine E-Mail diese zweite Filterebene auslöst, wird sie akzeptiert, auch wenn ihre Spamwahrscheinlichkeit über dem Schwellenwert liegt.

Ich erwarte nicht, dass diese zweite Filterebene Bayesianisch ist. Sie wird zwangsläufig nicht nur ad hoc sein, sondern auf Vermutungen beruhen, da die Anzahl der Fehlalarme tendenziell nicht groß genug ist, um Muster zu erkennen. (Es ist sowieso genauso gut, wenn ein Backup-System nicht auf derselben Technologie basiert wie das primäre System.)

Eine weitere Sache, die ich in Zukunft vielleicht versuchen werde, ist, besonderen Teilen der E-Mail besondere Aufmerksamkeit zu schenken. Beispielsweise enthalten etwa 95 % der aktuellen Spam-Mails die URL einer Site, die Sie besuchen sollen. (Die restlichen 5 % möchten, dass Sie eine Telefonnummer anrufen, per E-Mail oder an eine US-Postadresse antworten oder in einigen Fällen eine bestimmte Aktie kaufen.) In solchen Fällen reicht die URL praktisch aus, um festzustellen, ob es sich bei der E-Mail um Spam handelt.

Domänennamen unterscheiden sich vom Rest des Textes einer (nicht deutschen) E-Mail dadurch, dass sie oft aus mehreren aneinandergefügten Wörtern bestehen. Obwohl dies im Allgemeinen rechenintensiv ist, könnte es sich lohnen, sie zu zerlegen. Wenn ein Filter das Token „xxxporn“ noch nie zuvor gesehen hat, hat es eine individuelle Spamwahrscheinlichkeit von 0,4, während „xxx“ und „porn“ einzeln (in meinem Korpus) Wahrscheinlichkeiten von 0,9889 bzw. 0,99 und eine kombinierte Wahrscheinlichkeit von 0,9998 haben.

Ich gehe davon aus, dass die Aufschlüsselung von Domänennamen wichtiger wird, da Spammer nach und nach gezwungen sind, keine belastenden Wörter mehr in ihren Nachrichtentexten zu verwenden. (Eine URL mit einer IP-Adresse ist natürlich ein äußerst belastendes Zeichen, außer in den E-Mails einiger Systemadministratoren.)

Es wäre vielleicht eine gute Idee, eine gemeinsam gepflegte Liste der von Spammern beworbenen URLs zu führen. Wir bräuchten eine Vertrauensmetrik der Art, wie sie Raph Levien untersucht hat, um böswillige oder inkompetente Einsendungen zu verhindern, aber wenn wir so etwas hätten, würde das jede Filtersoftware verbessern. Es wäre auch eine praktische Grundlage für Boykotte.

Eine andere Möglichkeit, zweifelhafte URLs zu testen, besteht darin, einen Crawler loszuschicken, der sich die Site ansieht, bevor der Benutzer die E-Mail liest, in der sie erwähnt wird. Sie könnten einen Bayes-Filter verwenden, um die Site wie eine E-Mail zu bewerten, und alles, was auf der Site gefunden wird, könnte in die Berechnung der Wahrscheinlichkeit einbezogen werden, dass es sich bei der E-Mail um Spam handelt. Eine URL, die zu einer Weiterleitung führt, wäre natürlich besonders verdächtig.

Ein Gemeinschaftsprojekt, das meiner Meinung nach wirklich eine gute Idee wäre, wäre die Ansammlung eines riesigen Korpus an Spam. Ein großer, sauberer Korpus ist der Schlüssel für eine gute Funktionsweise des Bayes-Filters. Bayes-Filter könnten den Korpus tatsächlich als Eingabe verwenden. Ein solcher Korpus wäre aber auch für andere Filterarten nützlich, da man ihn zu deren Tests verwenden könnte.

Die Erstellung eines solchen Korpus wirft einige technische Probleme auf. Wir bräuchten natürlich Vertrauensmaße, um böswillige oder inkompetente Einsendungen zu verhindern. Wir bräuchten auch Möglichkeiten, persönliche Informationen (nicht nur Absender- und CC-Adressen, sondern z. B. auch die Argumente für Abmelde-URLs, die oft die Absenderadresse verschlüsseln) aus E-Mails im Korpus zu löschen. Wenn sich jemand dieses Projekt vornehmen möchte, wäre das eine gute Sache für die Welt.

Anhang: Definition von Spam

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 das tun, wenn wir ein zentrales Korpus für Spam erstellen oder auch nur die Spamfilterraten sinnvoll vergleichen wollen.

Zunächst einmal ist Spam keine unerwünschte kommerzielle E-Mail. Wenn jemand in meiner Nachbarschaft erfahren würde, dass ich nach einem alten Raleigh-Dreigangrad in gutem Zustand suche, und mir eine E-Mail mit dem Angebot schicken würde, mir eines zu verkaufen, wäre ich hocherfreut, und dennoch wäre diese E-Mail sowohl kommerziell als auch unaufgefordert. Das entscheidende Merkmal von Spam (eigentlich seine Existenzberechtigung ) ist nicht, dass er unaufgefordert ist, sondern dass er automatisiert erfolgt.

Dass Spam in der Regel kommerzieller Natur ist, ist nur nebensächlich. Wenn jemand beispielsweise Massen-E-Mails zur Unterstützung eines politischen Anliegens versenden würde, wäre das genauso Spam wie eine E-Mail, die für eine Pornoseite wirbt.

Ich schlage vor, Spam als unerwünschte automatisierte E-Mails zu definieren. Diese Definition umfasst also einige E-Mails, die in vielen gesetzlichen Definitionen von Spam nicht enthalten sind. Gesetzliche Definitionen von Spam, die vermutlich von Lobbyisten beeinflusst sind, schließen in der Regel E-Mails aus, die von Unternehmen gesendet werden, die eine „bestehende Beziehung“ zum Empfänger haben. Aber wenn Sie beispielsweise etwas von einem Unternehmen kaufen, bedeutet das nicht, dass Sie fortlaufend E-Mails von diesem Unternehmen angefordert haben. Wenn ich etwas in einem Online-Shop bestelle und sie mir dann eine Flut von Spam schicken, ist das immer noch Spam.

Unternehmen, die Spam versenden, bieten Ihnen häufig die Möglichkeit, sich abzumelden, oder bitten Sie, auf ihre Website zu gehen und Ihre „Kontoeinstellungen“ zu ändern, wenn Sie keinen Spam mehr erhalten möchten. Dies reicht jedoch nicht aus, um zu verhindern, dass die E-Mail Spam ist. Sich nicht abzumelden ist nicht dasselbe wie sich anzumelden. Sofern der Empfänger nicht ausdrücklich ein klar gekennzeichnetes Kästchen (das standardmäßig „Nein“ lautete) angekreuzt hat, um den Erhalt der E-Mail anzufordern, handelt es sich um Spam.

In manchen Geschäftsbeziehungen fordern Sie implizit bestimmte Arten von E-Mails an. Wenn Sie online bestellen, fordern Sie meiner Meinung nach implizit eine Empfangsbestätigung und eine Benachrichtigung an, wenn die Bestellung versandt wird. Es stört mich nicht, wenn Verisign mir eine E-Mail mit der Warnung schickt, dass ein Domänenname bald abläuft (zumindest, wenn sie der eigentliche Registrar dafür sind). Aber wenn Verisign mir eine E-Mail mit einem KOSTENLOSEN Leitfaden zum Erstellen meiner E-Commerce-Website schickt, ist das Spam.

Hinweise:

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

[2] Derzeit liegt der niedrigste Tarif bei etwa 200 Dollar für den Versand von einer Million Spam-Mails. Das ist sehr günstig, 1/50 Cent pro Spam. Aber wenn man beispielsweise 95 Prozent des Spams herausfiltert, steigen die Kosten für die Spammer, um ein bestimmtes Publikum zu erreichen, um den Faktor 20. Nur wenige können über ausreichende Margen verfügen, um das aufzufangen.

[3] Als Faustregel gilt: Je mehr Zusätze vor dem Namen eines Landes stehen, desto korrupter sind die Herrscher. Ein Land namens Sozialistische Demokratische Volksrepublik X ist wahrscheinlich der letzte Ort auf der Welt, an dem man leben möchte.

Wir danken Sarah Harlin für das Lesen der Entwürfe, Daniel Giffin (der auch den Arc-Produktionsinterpreter schreibt) für mehrere gute Ideen zum Filtern und für die Erstellung unserer E-Mail-Infrastruktur, Robert Morris, Trevor Blackwell und Erann Gat für zahlreiche Diskussionen zum Thema Spam, Raph Levien für Ratschläge zu Vertrauensmetriken und Chip Coldwell und Sam Steingold für Ratschläge zu Statistiken.

Diesen Essay und 14 weitere finden Sie in [

Hacker & Maler

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

Weitere Informationen: