EIN PLAN GEGEN SPAM

August 2002

(Dieser Artikel beschreibt die Spam-Filtertechniken, die in dem spamfesten webbasierten Mailreader verwendet werden, den wir gebaut haben, um Arc zu testen. Ein verbesserter Algorithmus wird in Bessere Bayes'sche Filterung beschrieben.)

Ich denke, es ist möglich, Spam zu stoppen, und dass inhaltsbasierte Filter der richtige Weg dafür sind. Die Achillesferse der Spammer ist ihre Nachricht. Sie können jede andere Barriere, die Sie einrichten, umgehen. Das haben sie bisher zumindest getan. Aber sie müssen ihre Nachricht, was auch immer sie ist, überbringen. Wenn wir Software schreiben können, die ihre Nachrichten erkennt, gibt es keine Möglichkeit, dass sie das umgehen können.

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

Ich denke, wir werden das Problem mit ziemlich einfachen Algorithmen lösen können. Tatsächlich habe ich festgestellt, dass man heutigen Spam akzeptabel gut filtern kann mit nichts weiter als einer Bayes'schen Kombination der Spam-Wahrscheinlichkeiten einzelner Wörter. Mit einem leicht angepassten (wie unten beschrieben) Bayes'schen Filter, verpassen wir jetzt weniger als 5 von 1000 Spams, mit 0 falsch-positiven Ergebnissen.

Der statistische Ansatz ist normalerweise nicht der erste, den Leute versuchen, wenn sie Spam-Filter schreiben. Der erste Instinkt der meisten Hacker ist es, Software zu schreiben, die einzelne Eigenschaften von Spam erkennt. Man schaut sich Spams an und denkt, die Dreistigkeit dieser Typen, mir Mail zu schicken, die mit "Lieber Freund" beginnt oder eine Betreffzeile hat, die komplett in Großbuchstaben geschrieben ist und mit acht Ausrufezeichen endet. Ich kann das Zeug mit etwa einer Zeile Code herausfiltern.

Und so macht man es, und am Anfang funktioniert es. Ein paar einfache Regeln werden einen großen Teil Ihres eingehenden Spams ausfiltern. Allein das Suchen nach dem Wort "Klick" wird 79,7% der E-Mails in meinem Spam-Korpus erwischen, mit nur 1,2% falsch-positiven Ergebnissen.

Ich habe etwa sechs Monate damit verbracht, Software zu schreiben, die nach einzelnen Spam-Merkmalen suchte, bevor ich den statistischen Ansatz ausprobierte. Was ich feststellte, war, dass die Erkennung dieser letzten paar Prozent der Spams sehr schwierig wurde, und dass ich, je strenger ich die Filter machte, umso mehr falsch-positive Ergebnisse bekam.

Falsch-positive Ergebnisse sind unschuldige E-Mails, die fälschlicherweise als Spam identifiziert werden. Für die meisten Benutzer ist es um eine Größenordnung schlimmer, legitime E-Mails zu verpassen als Spam zu erhalten, daher ist ein Filter, der falsch-positive Ergebnisse liefert, wie ein Akne-Heilmittel, das das Risiko des Todes für den Patienten birgt.

Je mehr Spam ein Benutzer erhält, desto weniger wahrscheinlich ist es, dass er eine unschuldige Mail in seinem Spam-Ordner bemerkt. Und seltsamerweise werden falsch-positive Ergebnisse umso gefährlicher, je besser Ihre Spam- Filter werden, denn wenn die Filter wirklich gut sind, werden Benutzer eher alles ignorieren, was sie erwischen.

Ich weiß nicht, warum ich es so lange vermieden habe, den statistischen Ansatz auszuprobieren. Ich denke, es lag daran, dass ich süchtig danach wurde, selbst Spam-Merkmale zu identifizieren, als würde ich eine Art von Wettbewerbsspiel mit den Spammern spielen. (Nicht-Hacker erkennen das nicht oft, aber die meisten Hacker sind sehr wettbewerbsorientiert.) Als ich dann die statistische Analyse ausprobierte, stellte ich sofort fest, dass sie viel klüger war, als ich es gewesen war. Sie entdeckte natürlich, dass Begriffe wie "virtumundo" und "Teenager" gute Indikatoren für Spam waren. Aber sie entdeckte auch, dass "pro" und "FL" und "ff0000" gute Indikatoren für Spam sind. Tatsächlich ist "ff0000" (HTML für leuchtend rot) ein ebenso guter Indikator für Spam wie jeder pornografische Begriff.

Hier ist eine Skizze, wie ich die statistische Filterung durchführe. Ich beginne mit einem Korpus von Spam und einem von Nicht-Spam-Mail. Im Moment hat jeder etwa 4000 Nachrichten darin. Ich scanne den gesamten Text, einschließlich Header und eingebettetem HTML und Javascript, jeder Nachricht in jedem Korpus. Derzeit betrachte ich alphanumerische Zeichen, Bindestriche, Apostrophe und Dollarzeichen als Teil von Token, und alles andere als Token-Trennzeichen. (Hier gibt es wahrscheinlich Raum für Verbesserungen.) Ich ignoriere Token, die nur aus Ziffern bestehen, und ich ignoriere auch HTML-Kommentare, ohne sie überhaupt als Token-Trennzeichen zu betrachten.

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

Als Nächstes erstelle ich eine dritte Hash-Tabelle, die diesmal jedes Token auf die Wahrscheinlichkeit abbildet, dass eine E-Mail, die es enthält, ein 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 sind die Hash-Tabellen, die ich im ersten Schritt erstellt habe, und ngood und nbad sind die Anzahl der Nicht-Spam- und Spam-Nachrichten.

Ich habe dies als Code erklärt, um ein paar wichtige Details aufzuzeigen. Ich möchte die Wahrscheinlichkeiten leicht verzerren, um falsch-positive Ergebnisse zu vermeiden, und durch Ausprobieren habe ich festgestellt, dass eine gute Möglichkeit dafür ist, alle Zahlen in good zu verdoppeln. Dies hilft, zwischen Wörtern zu unterscheiden, die gelegentlich in legitimer E-Mail vorkommen, und Wörtern, die fast nie vorkommen. Ich betrachte nur Wörter, die insgesamt mehr als fünf Mal vorkommen (eigentlich, wegen der Verdopplung, dreimal in Nicht-Spam-Mail zu vorkommen, wäre genug). Und dann stellt sich die Frage, welche Wahrscheinlichkeit man Wörtern zuordnen soll, die in einem Korpus vorkommen, aber nicht im anderen. Auch durch Ausprobieren habe ich mich für .01 und .99 entschieden. Hier könnte es Raum für Feinabstimmung geben, aber mit zunehmendem Korpus wird diese Feinabstimmung automatisch erfolgen.

Die besonders aufmerksamen Leser werden feststellen, dass ich zwar jeden Korpus als einen einzigen langen Textstrom betrachte, um die Häufigkeit des Vorkommens zu zählen, aber die Anzahl der E-Mails in jedem, anstatt ihre kombinierte Länge, als Divisor bei der Berechnung der Spam-Wahrscheinlichkeiten verwende. Dies fügt eine weitere leichte Verzerrung hinzu, um gegen falsch-positive Ergebnisse zu schützen.

Wenn neue Mail eintrifft, wird sie in Token gescannt, und die fünfzehn interessantesten Token, 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 ein Spam ist. Wenn probs eine Liste der fünfzehn Einzelwahrscheinlichkeiten ist, berechnet man die kombinierte Wahrscheinlichkeit wie folgt:

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

Eine Frage, die sich in der Praxis stellt, ist, welche Wahrscheinlichkeit man einem Wort zuordnen soll, das man noch nie gesehen hat, d.h. einem, das nicht in der Hash-Tabelle der Wort- Wahrscheinlichkeiten vorkommt. Ich habe festgestellt, wieder durch Ausprobieren, dass .4 eine gute Zahl ist, die man verwenden kann. Wenn man ein Wort noch nie zuvor gesehen hat, ist es wahrscheinlich ziemlich harmlos; Spam-Wörter sind in der Regel allzu vertraut.

Es gibt Beispiele für die Anwendung dieses Algorithmus auf tatsächliche E-Mails in einem Anhang am Ende.

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

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 irgendwie demoralisierend. Norbert Wiener sagte, wenn man mit Sklaven konkurriert, wird man selbst zum Sklaven, und es gibt etwas ähnlich Erniedrigendes daran, mit Spammern zu konkurrieren. 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 im Kopf von Spammern verbringen.

Aber der eigentliche Vorteil des Bayes'schen Ansatzes ist natürlich, dass man weiß, was man misst. Merkmals-erkennende Filter wie SpamAssassin weisen einer E-Mail einen Spam-"Score" zu. Der Bayes'sche 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 noch schlimmer, der Entwickler des Filters auch nicht. Wie viele Punkte sollte eine E-Mail erhalten, wenn sie das Wort "Sex" enthält? Eine Wahrscheinlichkeit kann natürlich falsch sein, aber es gibt wenig Zweifel darüber, was sie bedeutet oder wie Beweise kombiniert werden sollten, um sie zu berechnen. Basierend auf meinem Korpus weist "Sex" auf eine .97 Wahrscheinlichkeit hin, dass die enthaltende E-Mail ein Spam ist, während "sexy" eine .99 Wahrscheinlichkeit anzeigt. Und die Bayes'sche Regel, ebenso eindeutig, besagt, dass eine E-Mail, die beide Wörter enthält, in Abwesenheit anderer Beweise eine 99,97%ige Wahrscheinlichkeit hätte, ein Spam zu sein.

Da es Wahrscheinlichkeiten misst, berücksichtigt der Bayes'sche Ansatz alle Beweise in der E-Mail, sowohl gute als auch schlechte. Wörter, die unverhältnismäßig selten selten in Spam vorkommen (wie "obwohl" oder "heute Abend" oder "anscheinend") tragen genauso dazu bei, die Wahrscheinlichkeit zu verringern, wie schlechte Wörter wie "abbestellen" und "opt-in" dazu beitragen, sie zu erhöhen. Daher wird eine ansonsten unschuldige E-Mail, die zufällig das Wort "Sex" enthält, nicht als Spam gekennzeichnet.

Idealerweise sollten die Wahrscheinlichkeiten natürlich individuell für jeden Benutzer berechnet werden. Ich bekomme viele E-Mails, die das Wort "Lisp" enthalten, und (bisher) keinen Spam, der das tut. Daher ist ein Wort wie dieses effektiv eine Art Passwort, um mir Mail zu schicken. In meiner früheren Spam-Filter-Software konnte der Benutzer eine Liste solcher Wörter einrichten, und Mail, die diese enthielt, würde automatisch an den Filtern vorbeigehen. Auf meine Liste habe ich Wörter wie "Lisp" und auch meine Postleitzahl gesetzt, so dass (ansonsten ziemlich spammig klingende) Quittungen von Online-Bestellungen durchkommen würden. Ich dachte, ich wäre sehr clever, aber ich stellte fest, dass der Bayes'sche Filter dasselbe für mich tat, und außerdem eine Menge 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 falsch-positiven Ergebnissen durchlassen, spreche ich davon, meine Mail basierend auf einem Korpus meiner Mail zu filtern. Aber diese Zahlen sind nicht irreführend, denn das ist der Ansatz, den ich befürworte: Filtern Sie die Mail jedes Benutzers basierend auf dem Spam und Nicht-Spam, den er erhält. Im Wesentlichen sollte jeder Benutzer zwei Lösch-Buttons haben, normales 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.

Man könnte Benutzer mit einem Seed-Filter starten, aber letztendlich sollte jeder Benutzer seine eigenen Wahrscheinlichkeiten pro Wort haben, die auf der tatsächlichen Mail basieren, die er erhält. Dies (a) macht die Filter effektiver, (b) lässt jeden Benutzer seine eigene präzise Definition von Spam festlegen, und (c) macht es vielleicht am besten von allem für Spammer schwierig, Mails so zu optimieren, dass sie an den Filtern vorbeikommen. Wenn ein großer Teil des Gehirns des Filters in den einzelnen Datenbanken liegt, dann garantiert die bloße Optimierung von Spams, um an den Seed- Filtern vorbeizukommen, nichts darüber, wie gut sie an den unterschiedlichen und viel besser trainierten Filtern der einzelnen Benutzer vorbeikommen.

Inhaltsbasierte Spam-Filterung wird oft mit einer Whitelist kombiniert, einer Liste von Absendern, deren Mail ohne Filterung akzeptiert werden kann. Eine einfache Möglichkeit, eine solche Whitelist zu erstellen, ist, eine Liste aller Adressen zu führen, an die der Benutzer jemals Mail geschickt hat. Wenn ein Mailreader einen Löschen-als-Spam-Button hat, dann könnte man auch die Absenderadresse jeder E-Mail hinzufügen, die der Benutzer als normalen Müll gelöscht hat.

Ich bin ein Verfechter von Whitelists, aber eher als eine Möglichkeit, Rechenleistung zu sparen, als als eine Möglichkeit, die Filterung zu verbessern. Früher dachte ich, dass Whitelists die Filterung einfacher machen würden, weil man nur E-Mails von Leuten filtern müsste, von denen man noch nie etwas gehört hat, und jemand, der Ihnen zum ersten Mal Mail schickt, ist durch Konvention eingeschränkt in dem, was er Ihnen sagen kann. Jemand, den Sie bereits kennen, könnte Ihnen eine E-Mail schicken, in der er über Sex spricht, aber jemand, der Ihnen zum ersten Mal Mail schickt, würde das wahrscheinlich nicht tun. Das Problem ist, dass Leute mehr als eine E-Mail-Adresse haben können, daher garantiert eine neue Absenderadresse nicht, dass der Absender Ihnen zum ersten Mal schreibt. Es ist nicht ungewöhnlich, dass ein alter Freund (besonders wenn er ein Hacker ist) Ihnen plötzlich eine E-Mail mit einer neuen Absenderadresse schickt, daher kann man sich keine falsch-positiven Ergebnisse leisten, indem man Mail von unbekannten Adressen besonders streng filtert.

In gewisser Weise verkörpern meine Filter jedoch selbst eine Art Whitelist (und Blacklist), da sie auf ganzen Nachrichten basieren, einschließlich der Header. Daher "kennen" sie in diesem Sinne die E-Mail-Adressen von vertrauenswürdigen Absendern und sogar die Wege, auf denen Mail von ihnen zu mir gelangt. Und sie wissen dasselbe über Spam, einschließlich der Servernamen, Mailer-Versionen und Protokolle.

Wenn ich glauben würde, dass ich die aktuellen Spam-Filterraten halten könnte, würde ich dieses Problem für gelöst halten. Aber es bedeutet nicht viel, den größten Teil des heutigen Spams herausfiltern 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 Insektenart zu erzeugen.

Ich bin zuversichtlicher in Bezug auf Bayes'sche Filter, weil sie sich mit dem Spam entwickeln. Wenn Spammer also anfangen, "c0ck" anstelle von "cock" zu verwenden, um einfache Spam- Filter zu umgehen, die auf einzelnen Wörtern basieren, bemerken Bayes'sche Filter das automatisch. Tatsächlich ist "c0ck" ein viel verdammter Beweis als "cock", und Bayes'sche 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 überlisten? Zum Beispiel denke ich, dass die Spammer, wenn die checksummbasierte Spam-Filterung zu einem ernsthaften Hindernis wird, einfach auf Mad-Lib-Techniken zum Generieren von Nachrichtentexten umsteigen werden.

Um Bayes'sche Filter zu besiegen, würde es für Spammer nicht ausreichen, ihre E-Mails einzigartig zu machen oder die Verwendung einzelner unzulässiger Wörter zu unterlassen. Sie müssten ihre Mails von Ihrer normalen Post ununterscheidbar machen. Und das würde sie meiner Meinung nach stark einschränken. Spam besteht hauptsächlich aus Verkaufsangeboten, daher werden Spams unweigerlich einen anderen Charakter haben, es sei denn, Ihre normale Post besteht ausschließlich aus Verkaufsangeboten. Und die Spammer müssten natürlich auch ihre gesamte Infrastruktur ändern (und immer wieder ändern), denn sonst würden die Header für die Bayes'schen Filter genauso schlecht aussehen wie immer, egal was sie mit dem Nachrichtentext machten. 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 vermute, dass es noch schwieriger wäre, als die Nachricht unschuldig aussehen zu lassen.

Angenommen, 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 so viel Verkaufsgespräch, wie die inhaltsbasierte Filterung dem Spammer noch Raum zum Gestalten lässt. (Tatsächlich wird es sogar schwer sein, das an den Filtern vorbeizuschleusen, denn wenn alles andere in der E-Mail neutral ist, hängt die Spam-Wahrscheinlichkeit von der URL ab, und es wird einige Mühe kosten, diese neutral aussehen zu lassen.)

Spammer reichen von Unternehmen, die sogenannte Opt-in-Listen betreiben und nicht einmal versuchen, ihre Identität zu verschleiern, bis hin zu Leuten, die Mailserver kapern, um Spam zu versenden, der für Pornoseiten wirbt. Wenn wir die Filterung nutzen, um ihre Möglichkeiten auf Mails wie die oben beschriebene zu reduzieren, sollte das die Spammer am "legitimen" Ende des Spektrums ziemlich aus dem Geschäft bringen; sie fühlen sich durch verschiedene staatliche Gesetze verpflichtet, einen Standardtext darüber aufzunehmen, warum ihr Spam kein Spam ist und wie man sein "Abonnement" kündigen kann, und diese Art von Text ist leicht zu erkennen.

(Früher dachte ich, es sei naiv zu glauben, dass strengere Gesetze den Spam reduzieren würden. Jetzt denke ich, dass strengere Gesetze zwar die Menge an Spam, die Spammer versenden, nicht unbedingt reduzieren, aber Filter sicherlich dabei helfen können, die Menge an Spam zu reduzieren, die Empfänger tatsächlich sehen.)

Entlang des gesamten Spektrums werden Sie, wenn Sie die Verkaufsgespräche einschränken, die Spammer führen können, unweigerlich dazu neigen, sie aus dem Geschäft zu bringen. Das Wort Geschäft ist ein wichtiges Wort, an das man sich erinnern sollte. Die Spammer sind Geschäftsleute. Sie versenden Spam, weil es funktioniert. Es funktioniert, weil die Antwortrate zwar abgrundtief niedrig ist (höchstens 15 pro Million, gegenüber 3000 pro Million bei einem Katalogversand), die Kosten für sie aber praktisch nichts betragen. Die Kosten für die Empfänger sind enorm, 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.

Das Versenden von Spam kostet den Spammer jedoch etwas. [2] Je niedriger wir also die Antwortrate bekommen können - sei es durch Filterung oder durch die Verwendung von Filtern, um Spammer zu zwingen, ihre Werbeaussagen zu verwässern - desto weniger Unternehmen werden es für sich lohnenswert finden, Spam zu versenden.

Der Grund, warum die Spammer die Art von Verkaufsgesprächen verwenden, die sie verwenden, ist, die Antwortraten zu erhöhen. Das ist möglicherweise noch widerlicher, als in den Kopf eines Spammers zu gelangen, aber lassen Sie uns einen kurzen Blick in den Kopf von jemandem werfen, der auf einen Spam antwortet. Diese Person ist entweder erstaunlich leichtgläubig oder befindet sich in tiefer 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 klingen würden. Und "Ich dachte, du solltest dir das Folgende ansehen" wird bei den Spam-Empfängern einfach nicht annähernd so viel Anziehungskraft haben wie die Art von Dingen, die Spammer jetzt sagen. Ergebnis: Wenn es keine aufregenden Verkaufsgespräche enthalten kann, wird Spam als Marketinginstrument weniger effektiv, und weniger Unternehmen wollen es verwenden.

Das ist der große Gewinn am Ende. Ich habe angefangen, Spam-Filtersoftware zu schreiben, weil ich mir das Zeug nicht mehr ansehen wollte. Aber wenn wir gut genug darin werden, Spam herauszufiltern, wird es nicht mehr funktionieren, und die Spammer werden tatsächlich aufhören, es zu versenden.

Von allen Ansätzen zur Bekämpfung von Spam, von Software bis hin zu Gesetzen, glaube ich, dass die Bayes'sche Filterung die 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 neigen, die Filterung zu erleichtern. Und selbst innerhalb der Welt der inhaltsbasierten Filterung 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 zu optimieren, dass sie durch sie gelangen.

Anhang: Beispiele für die Filterung

Hier ist ein Beispiel für einen Spam, der während des Schreibens dieses Artikels bei mir eingetroffen ist. 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 Nachrichtentext, was typisch für Spam ist. Ebenfalls typisch für Spam ist, dass jedes dieser Wörter in meiner Datenbank eine Spam-Wahrscheinlichkeit von 0,99 hat. Tatsächlich gibt es mehr als fünfzehn Wörter mit Wahrscheinlichkeiten von 0,99, und dies sind nur die ersten fünfzehn, die angezeigt werden.

Leider macht das diese E-Mail zu einem langweiligen Beispiel für die Anwendung der Bayes'schen Regel. Um eine interessante Vielfalt an Wahrscheinlichkeiten zu sehen, müssen wir uns dies tatsächlich ziemlich untypischen Spam ansehen.

Die fünfzehn interessantesten Wörter in diesem Spam, zusammen 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 der Beweis eine Mischung aus gutem und schlechtem. Ein Wort wie "kürzester" ist fast so viel Beweis für Unschuld, wie ein Wort wie "Madam" oder "Promotion" für Schuld ist. Aber trotzdem ist der Fall für Schuld stärker. Wenn Sie diese Zahlen gemäß der Bayes'schen Regel kombinieren, ergibt sich eine Wahrscheinlichkeit von 0,9027.

"Madam" stammt offensichtlich aus Spams, die mit "Sehr geehrte Damen und Herren" beginnen. Sie sind nicht sehr häufig, aber das Wort "Madam" kommt nie in meiner legitimen E-Mail vor, und es geht um das Verhältnis.

"Republik" erzielt eine hohe Punktzahl, weil es oft in nigerianischen Betrugsmails auftaucht und auch ein- 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 dazu beiträgt, diesen Spam zu identifizieren. Aber ich habe festgestellt, dass es bei der Untersuchung von Spam-Wahrscheinlichkeiten viele dieser Zufälle gibt, und sie haben eine unheimliche Tendenz, die Dinge eher in die richtige als in die falsche Richtung zu schieben. In diesem Fall ist es kein Zufall, dass das Wort "Republik" in nigerianischen Betrugsmails und diesem Spam vorkommt. Es gibt eine ganze Klasse von dubiosen Geschäftsangeboten, die weniger entwickelte Länder betreffen, und diese wiederum haben eher Namen, die explizit angeben (weil sie es nicht sind), dass sie Republiken sind. [3]

Auf der anderen Seite ist "eingeben" ein echter Fehltritt. Es kommt hauptsächlich in Abmeldehinweisen vor, wird hier aber auf völlig unschuldige Weise verwendet. Glücklicherweise ist der statistische Ansatz ziemlich robust und kann eine ganze Reihe von Fehlern tolerieren, bevor die Ergebnisse verfälscht werden.

Zum Vergleich, hier ist ein Beispiel für diesen seltenen Vogel, einen Spam, der durch die Filter gelangt. Warum? Weil es zufällig mit Wörtern gefüllt 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

Es gibt ein paar gute Nachrichten hier. Erstens würde diese Mail wahrscheinlich nicht durch die Filter von jemandem gelangen, der sich nicht zufällig auf Programmiersprachen spezialisiert hat und einen guten Freund namens Morris hat. Für den durchschnittlichen Benutzer wären alle Top-5-Wörter hier neutral und würden nicht zur Spam-Wahrscheinlichkeit beitragen.

Zweitens denke ich, dass die Filterung anhand von Wortpaaren (siehe unten) diese Mail durchaus erwischen könnte: "kostengünstig", "Einrichtungsgebühr", "Geld zurück" - ziemlich belastende Dinge. Und natürlich, wenn sie mich (oder ein Netzwerk, zu dem ich gehöre) weiterhin mit Spam bombardieren würden, würde "Hostex" selbst als Spam-Begriff erkannt werden.

Schließlich, hier ist eine unschuldige 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 Wörter hier deuten darauf hin, dass die Mail unschuldig ist. Es gibt zwei schlecht riechende Wörter, "Farbe" (Spammer lieben farbige Schriftarten) und "Kalifornien" (das in Erfahrungsberichten und auch in Menüs in Formularen vorkommt), aber sie reichen nicht aus, um offensichtlich unschuldige Wörter wie "Fortsetzung" und "Beispiel" zu überwiegen.

Es ist interessant, dass "beschreiben" als so durch und durch unschuldig eingestuft wird. Es ist in keinem einzigen meiner 4000 Spams vorgekommen. Die Daten erweisen sich als voller solcher Überraschungen. Eines der Dinge, die man lernt, wenn man Spam-Texte analysiert, ist, wie eng ein Teilbereich der Sprache Spammer nutzen. Diese Tatsache, zusammen mit dem ebenso charakteristischen Wortschatz der E-Mails jedes einzelnen Benutzers, macht die Bayes'sche Filterung zu einer guten Wahl.

Anhang: Weitere Ideen

Eine Idee, die ich noch nicht ausprobiert habe, ist die Filterung anhand von Wortpaaren oder sogar Tripeln, anstatt anhand einzelner Wörter. Dies sollte eine viel schärfere Schätzung der Wahrscheinlichkeit liefern. Zum Beispiel hat das Wort "Angebote" in meiner aktuellen Datenbank eine Wahrscheinlichkeit von 0,96. Wenn Sie die Wahrscheinlichkeiten auf Wortpaare beziehen würden, würden Sie feststellen, dass "Sonderangebote" und "wertvolle Angebote" Wahrscheinlichkeiten von 0,99 haben und "Angebotsansätze" (wie in "Dieser Ansatz bietet") eine Wahrscheinlichkeit von 0,1 oder weniger haben.

Der Grund, warum ich das nicht getan habe, ist, dass die Filterung anhand einzelner Wörter bereits so gut funktioniert. Aber es bedeutet, dass es Raum gibt, die Filter zu verschärfen, wenn Spam schwieriger zu erkennen wird. (Kurioserweise wäre ein Filter, der auf Wortpaaren basiert, im Effekt ein Markov-Ketten-Textgenerator, der rückwärts läuft.)

Spezifische Spam-Merkmale (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 man sie als virtuelle Wörter behandelt. Ich werde das wahrscheinlich in zukünftigen Versionen tun, zumindest für eine Handvoll der eklatantesten Spam-Indikatoren. Feature-erkennende Spam-Filter liegen in vielen Details richtig; was ihnen fehlt, ist eine allgemeine Disziplin für die Kombination von Beweisen.

Die Erkennung von Nicht-Spam-Merkmalen kann wichtiger sein als die Erkennung von Spam-Merkmalen. Falsch-Positive sind so besorgniserregend, dass sie außergewöhnliche Maßnahmen erfordern. Ich werde wahrscheinlich in zukünftigen Versionen eine zweite Ebene von Tests hinzufügen, die speziell darauf ausgelegt ist, falsch-Positive zu vermeiden. Wenn eine Mail diese zweite Ebene von Filtern auslöst, wird sie akzeptiert, auch wenn ihre Spam-Wahrscheinlichkeit über dem Schwellenwert liegt.

Ich erwarte nicht, dass diese zweite Ebene der Filterung Bayes'sch sein wird. Sie wird unweigerlich nicht nur ad hoc sein, sondern auch auf Vermutungen beruhen, da die Anzahl der falsch-Positiven nicht dazu neigen wird, groß genug zu sein, um Muster zu erkennen. (Es ist sowieso genauso gut, wenn ein Backup-System nicht auf der gleichen Technologie wie das primäre System basiert.)

Eine weitere Sache, die ich in Zukunft versuchen könnte, ist, bestimmte Teile der E-Mail besonders zu beachten. Zum Beispiel enthält etwa 95 % des aktuellen Spams die URL einer Website, die sie Ihnen besuchen lassen möchten. (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.) Die URL ist in solchen Fällen praktisch allein schon ausreichend, um zu bestimmen, ob die E-Mail Spam ist.

Domainnamen unterscheiden sich vom restlichen Text in einer (nicht-deutschen) E-Mail dadurch, dass sie oft aus mehreren Wörtern bestehen, die aneinandergehängt sind. Obwohl rechnerisch aufwendig im allgemeinen Fall, könnte es sich lohnen, sie zu zerlegen. Wenn ein Filter den Token "xxxporn" noch nie zuvor gesehen hat, wird er eine individuelle Spam-Wahrscheinlichkeit von 0,4 haben, während "xxx" und "porn" einzeln Wahrscheinlichkeiten (in meinem Korpus) von 0,9889 bzw. 0,99 haben und eine kombinierte Wahrscheinlichkeit von 0,9998.

Ich erwarte, dass die Zerlegung von Domainnamen immer wichtiger wird, da Spammer allmählich gezwungen werden, incriminierende Wörter im Text ihrer Nachrichten nicht mehr zu verwenden. (Eine URL mit einer IP-Adresse ist natürlich ein extrem incriminierendes Zeichen, außer in der Mail einiger Systemadministratoren.)

Es könnte eine gute Idee sein, eine gemeinschaftlich gepflegte Liste von URLs zu haben, die von Spammern beworben werden. Wir bräuchten eine Vertrauensmetrik vom Typ, der von Raph Levien untersucht wurde, um böswillige oder inkompetente Einreichungen zu verhindern, aber wenn wir so etwas hätten, würde es jede Filtersoftware verbessern. Es wäre auch eine bequeme Grundlage für Boykotte.

Eine andere Möglichkeit, dubiose URLs zu testen, wäre, einen Crawler zu schicken, um sich die Website anzusehen, bevor der Benutzer die E-Mail anschaut, die sie erwähnt. Man könnte einen Bayes'schen Filter verwenden, um die Website genauso zu bewerten wie eine E-Mail, und alles, was auf der Website gefunden wird, könnte in die Berechnung der Wahrscheinlichkeit einbezogen werden, dass die E-Mail Spam ist. Eine URL, die zu einer Weiterleitung führt, wäre natürlich besonders verdächtig.

Ein gemeinsames Projekt, von dem ich denke, dass es wirklich eine gute Idee wäre, wäre die Sammlung eines riesigen Spam-Korpus. Ein großes, sauberes Korpus ist der Schlüssel, um Bayes'sche Filter gut funktionieren zu lassen. Bayes'sche Filter könnten das Korpus tatsächlich als Eingabe verwenden. Aber ein solches Korpus wäre auch für andere Arten von Filtern nützlich, da es zum Testen verwendet werden könnte.

Die Erstellung eines solchen Korpus stellt einige technische Probleme dar. Wir bräuchten natürlich Vertrauensmetriken, um böswillige oder inkompetente Einreichungen zu verhindern. Wir bräuchten auch Möglichkeiten, persönliche Informationen (nicht nur Empfängeradressen und CCs, sondern auch z. B. die Argumente für Abmelde-URLs, die oft die Empfängeradresse kodieren) aus den Mails im Korpus zu löschen. Wenn jemand dieses Projekt übernehmen möchte, wäre es 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. Das müssen wir tun, wenn wir ein zentrales Spam-Korpus erstellen wollen oder sogar Spam-Filterraten sinnvoll vergleichen wollen.

Zunächst einmal ist Spam keine unaufgeforderte kommerzielle E-Mail. Wenn jemand in meiner Nachbarschaft hörte, dass ich nach einem alten Raleigh Dreigangrad in gutem Zustand suche, und mir eine E-Mail schickte, in der er mir anbot, mir einen zu verkaufen, würde ich mich freuen, und doch wäre diese E-Mail sowohl kommerziell als auch unaufgefordert. Das bestimmende Merkmal von Spam (in der Tat sein raison d'etre) ist nicht, dass er unaufgefordert ist, sondern dass er automatisiert ist.

Es ist auch nur zufällig, dass Spam in der Regel kommerziell ist. Wenn jemand anfangen würde, Massen-E-Mails zu versenden, um eine politische Sache zu unterstützen, wäre das zum Beispiel genauso viel Spam wie E-Mails, die für eine Porno-Website werben.

Ich schlage vor, dass wir Spam als unaufgeforderte automatisierte E-Mail definieren. Diese Definition umfasst somit einige E-Mails, die viele rechtliche Definitionen von Spam nicht abdecken. Rechtliche Definitionen von Spam, die vermutlich von Lobbyisten beeinflusst werden, neigen dazu, E-Mails auszuschließen, die von Unternehmen versendet werden, die eine "bestehende Beziehung" zum Empfänger haben. Aber etwas von einem Unternehmen zu kaufen, bedeutet zum Beispiel nicht, dass Sie unaufgeforderte E-Mails von ihnen angefordert haben. Wenn ich etwas in einem Online-Shop bestelle und sie mir dann einen Strom von Spam schicken, ist es immer noch Spam.

Unternehmen, die Spam versenden, geben Ihnen oft die Möglichkeit, sich "abzumelden" oder Sie bitten, auf ihre Website zu gehen und Ihre "Kontoeinstellungen" zu ändern, wenn Sie keinen Spam mehr erhalten möchten. Das reicht nicht aus, um zu verhindern, dass die Mail Spam ist. Sich nicht abzumelden ist nicht dasselbe wie sich anzumelden. Wenn der Empfänger nicht explizit ein deutlich gekennzeichnetes Kästchen (dessen Standardwert nein war) angekreuzt hat, in dem er um den Erhalt der E-Mail gebeten hat, dann ist es Spam.

In einigen Geschäftsbeziehungen fordern Sie implizit bestimmte Arten von E-Mails an. Wenn Sie online bestellen, fordern Sie meiner Meinung nach implizit eine Quittung und eine Benachrichtigung, wenn die Bestellung versandt wird. Es macht mir nichts aus, wenn Verisign mir eine E-Mail schickt, in der mich gewarnt wird, dass ein Domainname bald abläuft (zumindest, wenn sie der tatsächliche Registrar dafür sind). Aber wenn Verisign mir eine E-Mail schickt, in der mir ein KOSTENLOSER Leitfaden zum Aufbau meiner E-Commerce-Website angeboten wird, ist das Spam.

Hinweise:

[1] Die Beispiele in diesem Artikel sind aus Gründen der besseren Zugänglichkeit in Common Lisp übersetzt. 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 liegt der niedrigste Preis bei etwa 200 Dollar für den Versand von einer Million Spams. Das ist sehr günstig, 1/50 Cent pro Spam. Aber das Herausfiltern von 95 % des Spams würde beispielsweise die Kosten der Spammer erhöhen, um ein bestimmtes Publikum zu erreichen, um den Faktor 20. Nur wenige können Margen haben, die groß genug sind, um das zu absorbieren.

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

Danke an Sarah Harlin für das Lesen der Entwürfe; Daniel Giffin (der auch den Produktions-Arc-Interpreter schreibt) für mehrere gute Ideen zur Filterung 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 Essay und 14 weitere in [

Hacker & Maler

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

Mehr Infos: