EIN PLAN FÜR SPAM
OriginalAugust 2002
(Dieser Artikel beschreibt die Spam-Filterungstechniken, die in dem spamgeschützten webbasierten Mailreader verwendet wurden, den wir gebaut haben, um Arc zu testen. Ein verbesserter Algorithmus wird in Better Bayesian Filtering 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 aufbauen, umgehen. Zumindest bisher. Aber sie müssen ihre Nachricht, was auch immer sie ist, zustellen. 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 zu erkennen. Wenn Sie jemanden einstellen würden, um Ihre Post zu lesen und den Spam zu entsorgen, hätte er dabei nur wenig Schwierigkeiten. 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 herausgefunden, dass man den heutigen Spam durchaus akzeptabel filtern kann, indem man nichts weiter als eine Bayes'sche Kombination der Spam-Wahrscheinlichkeiten einzelner Wörter verwendet. Mit einem leicht angepassten (wie unten beschrieben) Bayes'schen Filter verpassen wir jetzt weniger als 5 von 1000 Spams, ohne falsch-positive Ergebnisse.
Der statistische Ansatz ist normalerweise nicht der erste, den Leute ausprobieren, wenn sie Spam-Filter schreiben. Die erste Intuition der meisten Hacker ist es, Software zu schreiben, die einzelne Eigenschaften von Spam erkennt. Man schaut sich Spams an und denkt: "Die Frechheit dieser Kerle, mir E-Mails zu schicken, die mit 'Lieber Freund' beginnen oder eine Betreffzeile haben, die komplett in Großbuchstaben geschrieben ist und mit acht Ausrufezeichen endet. Das kann ich mit etwa einer Zeile Code herausfiltern."
Und so tut man es auch, und am Anfang funktioniert es. Ein paar einfache Regeln werden einen großen Teil Ihres eingehenden Spams abfangen. Allein das Suchen nach dem Wort "klicken" wird 79,7% der E-Mails in meinem Spam-Korpus abfangen, mit nur 1,2% falsch-positiven Ergebnissen.
Ich habe etwa sechs Monate damit verbracht, Software zu schreiben, die nach einzelnen Spam-Merkmalen sucht, bevor ich den statistischen Ansatz ausprobiert habe. Was ich festgestellt habe, war, dass das Erkennen der letzten paar Prozent der Spams sehr schwierig wurde und dass ich bei strengeren Filtern mehr falsch-positive Ergebnisse bekam.
Falsch-positive Ergebnisse sind harmlose E-Mails, die fälschlicherweise als Spam identifiziert werden. Für die meisten Nutzer ist es eine Größenordnung schlimmer, echte E-Mails zu verpassen, als Spam zu empfangen, daher ist ein Filter, der falsch-positive Ergebnisse liefert, wie ein Akne-Heilmittel, das ein Todesrisiko für den Patienten birgt.
Je mehr Spam ein Nutzer bekommt, desto unwahrscheinlicher ist es, dass er eine harmlose E-Mail in seinem Spam-Ordner übersieht. Und seltsamerweise werden falsch-positive Ergebnisse umso gefährlicher, je besser Ihre Spam-Filter werden, denn wenn die Filter wirklich gut sind, werden Nutzer eher dazu neigen, alles zu ignorieren, was sie abfangen.
Ich weiß nicht, warum ich den statistischen Ansatz so lange gemieden habe. Ich denke, es lag daran, dass ich süchtig danach wurde, selbst Spam-Merkmale zu identifizieren, als würde ich eine Art Wettbewerb mit den Spammern austragen. (Nicht-Hacker wissen oft nicht, dass die meisten Hacker sehr wettbewerbsorientiert sind.) Als ich dann die statistische Analyse ausprobiert habe, habe ich sofort festgestellt, dass sie viel cleverer war, als ich es war. Sie hat natürlich erkannt, dass Begriffe wie "virtumundo" und "teens" gute Indikatoren für Spam sind. Aber sie hat auch erkannt, dass "per" und "FL" und "ff0000" gute Spam-Indikatoren sind. Tatsächlich erweist sich "ff0000" (HTML für leuchtendes Rot) als genauso guter Spam-Indikator 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-E-Mails. Derzeit hat jedes etwa 4000 Nachrichten. Ich scanne den gesamten Text, einschließlich Kopfzeilen 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 Tokentrennzeichen. (Es gibt hier wahrscheinlich Raum für Verbesserungen.) Ich ignoriere Token, die nur aus Ziffern bestehen, und ich ignoriere auch HTML-Kommentare, ohne sie sogar als Tokentrennzeichen zu betrachten.
Ich zähle, wie oft jeder Token (ohne Berücksichtigung der Groß-/Kleinschreibung) in jedem Korpus vorkommt. In diesem Stadium ende ich mit zwei großen Hash-Tabellen, einer für jedes Korpus, die Token auf Häufigkeiten abbilden.
Als Nächstes erstelle ich eine dritte Hash-Tabelle, die diesmal jeden Token auf die Wahrscheinlichkeit abbildet, dass eine E-Mail, die ihn enthält, Spam ist, was 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 der Token ist, dessen Wahrscheinlichkeit wir berechnen, good und bad die Hash-Tabellen sind, die ich im ersten Schritt erstellt habe, und ngood und nbad die Anzahl der Nicht-Spam- bzw. Spam-Nachrichten sind.
Ich habe das als Code erklärt, um ein paar wichtige Details zu zeigen. Ich möchte die Wahrscheinlichkeiten leicht zugunsten von falsch-positiven Ergebnissen verzerren, und durch Versuch und Irrtum habe ich herausgefunden, 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 dies fast nie tun. Ich berücksichtige nur Wörter, die insgesamt mehr als fünfmal vorkommen (tatsächlich würden aufgrund der Verdopplung drei Vorkommen in Nicht-Spam-E-Mails ausreichen). Und dann gibt es noch die Frage, welche Wahrscheinlichkeit man Wörtern zuweisen soll, die in einem Korpus, aber nicht im anderen vorkommen. Wieder durch Versuch und Irrtum habe ich .01 und .99 gewählt. Es gibt hier vielleicht Raum für Feinabstimmung, aber mit wachsendem Korpus wird sich das sowieso automatisch ergeben.
Die besonders aufmerksamen Leser werden bemerken, dass ich zwar jedes Korpus für die Zwecke der Häufigkeitszählung als einen einzigen langen Textfluss betrachte, aber die Anzahl der E-Mails in jedem als Divisor für die Berechnung der Spam-Wahrscheinlichkeiten verwende. Dies fügt eine weitere leichte Verzerrung hinzu, um falsch-positive Ergebnisse zu vermeiden.
Wenn neue Post eintrifft, wird sie in Token zerlegt, und die 15 interessantesten Token, wobei interessant durch den Abstand ihrer Spam-Wahrscheinlichkeit von einem neutralen .5 gemessen wird, werden verwendet, um die Wahrscheinlichkeit zu berechnen, dass die Post Spam ist. Wenn probs eine Liste der 15 individuellen Wahrscheinlichkeiten ist, berechnet man die kombinierte Wahrscheinlichkeit so:
(let ((prod (apply #'* probs))) (/ prod (+ prod (apply #'* (mapcar #'(lambda (x) (- 1 x)) probs)))))
Eine Frage, die in der Praxis auftaucht, ist, welche Wahrscheinlichkeit man einem Wort zuweisen soll, das man noch nie gesehen hat, d.h. das nicht in der Hashtabelle der Wortwahrscheinlichkeiten vorkommt. Ich habe durch Versuch und Irrtum herausgefunden, 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 tendieren dazu, nur allzu vertraut zu sein.
Es gibt Beispiele dafür, wie dieser Algorithmus auf tatsächliche E-Mails in einem Anhang am Ende angewendet wird.
Ich behandle E-Mails als Spam, wenn der oben genannte 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 landen.
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 es ist wirklich ein bisschen demoralisierend. Norbert Wiener sagte, wenn man mit Sklaven konkurriert, wird man selbst zum Sklaven, und es gibt etwas ähnlich Erniedrigendendes daran, mit Spammern zu konkurrieren. Um einzelne Spam-Merkmale zu erkennen, muss man versuchen, in den Kopf des Spammers zu kommen, und ehrlich gesagt möchte ich so wenig Zeit wie möglich in den Köpfen von Spammern verbringen.
Der eigentliche Vorteil des Bayes'schen Ansatzes ist natürlich, dass man weiß, was man misst. Merkmalserkennende Filter wie SpamAssassin weisen E-Mails 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 ist, dass auch der Entwickler des Filters es nicht weiß. Wie viele Punkte sollte eine E-Mail dafür bekommen, dass das Wort "Sex" darin vorkommt? 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 deutet das Wort "Sex" auf eine Wahrscheinlichkeit von .97 hin, dass die enthaltene E-Mail ein Spam ist, während "Sexy" eine Wahrscheinlichkeit von .99 anzeigt. Und Bayes' Regel, ebenso eindeutig, besagt, dass eine E-Mail, die beide Wörter enthält, in Abwesenheit jeglicher anderer Beweise eine Wahrscheinlichkeit von 99,97 %, ein Spam zu sein.
Da er Wahrscheinlichkeiten misst, berücksichtigt der Bayes'sche Ansatz alle Beweise in der E-Mail, sowohl gute als auch schlechte. Wörter, die in Spam überproportional selten vorkommen (wie "obwohl" oder "heute Abend" oder "anscheinend"), tragen ebenso viel dazu bei, die Wahrscheinlichkeit zu verringern, wie schlechte Wörter wie "abmelden" und "opt-in" dazu beitragen, sie zu erhöhen. Daher wird eine ansonsten harmlose 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 erhalte viel E-Mail, die das Wort "Lisp" enthält, und (bisher) keinen Spam, der es tut. Ein Wort wie dieses ist also effektiv eine Art Passwort, um mir E-Mail zu senden. In meiner früheren Spam-Filterungssoftware konnte der Benutzer eine Liste solcher Wörter einrichten, und E-Mails, die sie enthielten, würden automatisch an den Filtern vorbei kommen. Auf meine Liste habe ich Wörter wie "Lisp" und auch meine Postleitzahl gesetzt, damit (ansonsten eher spamverdächtig klingende) Quittungen von Online-Bestellungen durchkommen würden. Ich dachte, ich sei sehr clever, aber ich fand, dass der Bayes'sche Filter dasselbe für mich tat und darüber hinaus eine Menge Wörter entdeckte, an die ich nicht gedacht hatte.
Wenn ich zu Beginn sagte, dass unsere Filter weniger als 5 Spams pro 1000 durchlassen, bei 0 Fehlalarmen, dann spreche ich davon, meine E-Mails basierend auf einem Korpus meiner E-Mails zu filtern. Aber diese Zahlen sind nicht irreführend, denn das ist der Ansatz, den ich befürworte: Filtern Sie die E-Mails jedes Benutzers basierend auf den Spam- und Nicht-Spam-E-Mails, die er erhält. Im Grunde sollte jeder Benutzer zwei Lösch-Buttons haben, einen normalen Lösch-Button und einen Lösch-als-Spam-Button. Alles, was als Spam gelöscht wird, kommt in den Spam-Korpus, und alles andere kommt in den Nicht-Spam-Korpus.
Man könnte die Benutzer mit einem Seed-Filter starten, aber letztendlich sollte jeder Benutzer seine eigenen wortspezifischen Wahrscheinlichkeiten basierend auf den tatsächlichen E-Mails haben, 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) vielleicht am wichtigsten, es erschwert es Spammern, E-Mails so zu optimieren, dass sie durch die Filter kommen. Wenn ein Großteil des "Gehirns" des Filters in den individuellen Datenbanken liegt, dann garantiert das bloße Abstimmen von Spams darauf, durch die Seed-Filter zu kommen, noch lange nicht, wie gut sie durch die individuell viel besser trainierten Filter der einzelnen Benutzer kommen werden.
Inhaltsbasierte Spam-Filterung wird oft mit einer Whitelist, einer Liste von Absendern, deren E-Mails ohne Filterung akzeptiert werden können, kombiniert. Eine einfache Möglichkeit, eine solche Whitelist aufzubauen, ist, eine Liste aller Adressen zu führen, an die der Benutzer jemals E-Mails gesendet hat. Wenn ein E-Mail-Programm einen Lösch-als-Spam-Button hat, könnte man auch die Absenderadresse jeder E-Mail hinzufügen, die der Benutzer als normalen Müll gelöscht hat.
Ich bin ein Befürworter von Whitelists, aber mehr als Mittel zur Einsparung von Rechenleistung denn als Mittel zur Verbesserung der Filterung. Früher dachte ich, dass Whitelists das Filtern erleichtern würden, weil man dann nur E-Mails von Leuten filtern müsste, von denen man noch nie gehört hatte, und jemand, der einem zum ersten Mal schreibt, ist durch Konventionen in dem, was er einem sagen kann, eingeschränkt. Jemand, den man schon kennt, könnte einem eine E-Mail über Sex schicken, aber jemand, der einem zum ersten Mal schreibt, würde das wahrscheinlich nicht tun. Das Problem ist, dass Leute mehr als eine E-Mail-Adresse haben können, so dass eine neue Absenderadresse nicht garantiert, dass der Absender einem zum ersten Mal schreibt. Es ist nicht ungewöhnlich, dass ein alter Freund (vor allem wenn er ein Hacker ist) einem plötzlich mit einer neuen Absenderadresse eine E-Mail schickt, so dass man sich keine Fehlalarme leisten kann, indem man E-Mails von unbekannten Adressen besonders streng filtert.
In gewissem Sinne verkörpern meine Filter selbst eine Art Whitelist (und Blacklist), da sie auf vollständigen Nachrichten, einschließlich der Kopfzeilen, basieren. Insofern "kennen" sie also die E-Mail-Adressen vertrauenswürdiger Absender und sogar die Routen, über die E-Mails von ihnen zu mir gelangen. Und sie kennen dasselbe über Spam, einschließlich der Servernamen, Mailer-Versionen und Protokolle.
Wenn ich glaubte, dass ich die derzeitigen Raten der Spam-Filterung aufrechterhalten könnte, würde ich dieses Problem für gelöst halten. Aber es bedeutet nicht viel, die meisten 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 Plage von Schädlingen zu schaffen.
Ich bin optimistischer in Bezug auf Bayes'sche Filter, denn sie entwickeln sich mit dem Spam weiter. Wenn Spammer also beginnen, "c0ck" anstelle von "cock" zu verwenden, um einfältige Spam-Filter auf der Basis einzelner Wörter zu umgehen, bemerken Bayes'sche Filter das automatisch. Tatsächlich ist "c0ck" weitaus belastenderes Beweismaterial als "cock", und Bayes'sche Filter wissen genau, wie viel mehr.
Trotzdem muss jeder, der einen Plan für die Spam-Filterung vorschlägt, in der Lage sein, die Frage zu beantworten: Wenn die Spammer genau wüssten, was Sie tun, wie gut könnten sie dann an Ihnen vorbeikommen? Zum Beispiel denke ich, dass wenn die Prüfsummen-basierte Spam-Filterung zu einem ernsthaften Hindernis wird, die Spammer einfach zu Mad-Lib-Techniken für die Generierung von Nachrichtentexten wechseln werden.
Um Bayessche Filter zu besiegen, würde es für die Spammer nicht ausreichen, ihre E-Mails eindeutig zu machen oder einzelne anstößige Wörter nicht mehr zu verwenden. Sie müssten ihre Mails ununterscheidbar von Ihrer normalen Post machen. Und das würde sie meiner Meinung nach stark einschränken. Spam besteht hauptsächlich aus Verkaufspitches, also werden Spams, solange Ihre reguläre Post nicht nur aus Verkaufspitches besteht, unweigerlich einen anderen Charakter haben. Und die Spammer müssten natürlich auch ihre gesamte Infrastruktur ändern (und ständig ändern), denn ansonsten würden die Kopfzeilen für die Bayesschen Filter genauso schlecht aussehen wie bisher, egal was sie am Nachrichtentext tun. Ich weiß nicht genug über die Infrastruktur, die Spammer verwenden, um zu wissen, wie schwierig es wäre, die Kopfzeilen unschuldig aussehen zu lassen, aber meine Vermutung ist, dass es sogar noch schwieriger wäre als das Nachrichtenformat unschuldig aussehen zu lassen.
Unter der Annahme, dass sie das Problem der Kopfzeilen lösen könnten, wird der Spam der Zukunft wahrscheinlich so aussehen:
Hey da. Dachte, du solltest dir das mal ansehen: http://www.27meg.com/foo
denn das ist etwa so viel Verkaufspitch, wie inhaltsbasierte Filterung den Spammern noch erlauben wird. (In der Tat wird es selbst schwierig sein, das an den Filtern vorbeizubringen, denn wenn der Rest der E-Mail neutral ist, wird die Spam-Wahrscheinlichkeit an der URL hängen, und es wird einige Mühe kosten, diese neutral aussehen zu lassen.)
Spammer reichen von Unternehmen, die sogenannte Opt-in-Listen betreiben und ihre Identitäten nicht einmal zu verbergen versuchen, bis hin zu Leuten, die E-Mail-Server kapern, um Spams zu verschicken, die Pornowebsites bewerben. Wenn wir mit Filtern ihre Optionen auf Mails wie die oben genannte reduzieren, dürfte das die Spammer am "legitimen" Ende des Spektrums praktisch aus dem Geschäft werfen; sie fühlen sich durch verschiedene Gesetze in den Bundesstaaten verpflichtet, Standardtexte darüber aufzunehmen, warum ihr Spam kein Spam ist und wie man sein "Abonnement" kündigt, und dieser Typ von Text ist leicht zu erkennen.
(Ich dachte früher, es sei naiv zu glauben, dass strengere Gesetze den Spam verringern würden. Jetzt denke ich, dass, auch wenn strengere Gesetze die Menge an Spam, die Spammer senden, vielleicht nicht verringern, sie den Filtern sicher helfen können, die Menge an Spam zu verringern, die die Empfänger tatsächlich sehen.)
Über das gesamte Spektrum hinweg, wenn Sie die Verkaufspitches einschränken, die Spammer machen können, werden Sie sie unweigerlich aus dem Geschäft drängen. Dieses Wort Geschäft ist ein wichtiges, das man im Hinterkopf behalten sollte. Die Spammer sind Geschäftsleute. Sie senden Spam, weil es funktioniert. Es funktioniert, weil, obwohl die Antwortrate erbärmlich niedrig ist (maximal 15 von einer Million, verglichen mit 3000 von einer Million für einen Katalogversand), die Kosten für sie praktisch nichts sind. Die Kosten sind enorm für die Empfänger, etwa 5 Mannwochen für jede Million Empfänger, die eine Sekunde zum Löschen des Spams aufwenden, aber der Spammer muss das nicht bezahlen.
Das Senden von Spam kostet den Spammer jedoch etwas. [2] Je niedriger wir also die Antwortrate halten können - sei es durch Filterung oder indem wir die Spammer zwingen, ihre Pitches zu verwässern -, desto weniger Unternehmen werden es für lohnenswert halten, Spam zu versenden.
Der Grund, warum die Spammer die Arten von Verkaufspitches verwenden, die sie tun, ist, um die Antwortquoten zu erhöhen. Das ist möglicherweise sogar noch widerlicher als sich in den Kopf eines Spammers zu versetzen, aber lassen Sie uns einen kurzen Blick in den Kopf eines Menschen werfen, der auf einen Spam antwortet. Diese Person ist entweder erstaunlich leichtgläubig oder tief in Verleugnung über ihre sexuellen Interessen. In beiden Fällen, so abstoßend oder idiotisch der Spam für uns 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 das mal ansehen" wird bei dem Spam-Empfänger bei weitem nicht so viel Anziehungskraft haben wie die Dinge, die Spammer jetzt sagen. Ergebnis: Wenn er keine aufregenden Verkaufspitches enthalten kann, wird Spam als Marketinginstrument weniger effektiv, und weniger Unternehmen wollen es einsetzen.
Das ist der große Gewinn am Ende. Ich habe angefangen, Spam-Filterungssoftware zu schreiben, weil ich die Sache nicht mehr sehen wollte. Aber wenn wir gut genug im Filtern von Spam werden, wird es nicht mehr funktionieren, und die Spammer werden tatsächlich aufhören, es zu senden.
Von allen Ansätzen im Kampf gegen Spam, von Software bis hin zu Gesetzen, glaube ich, dass die Bayessche Filterung die einzeln effektivste sein wird. Aber ich denke auch, dass es umso besser ist, je mehr verschiedene Arten von Antispam-Bemühungen wir unternehmen, denn jede Maßnahme, die Spammer einschränkt, wird dazu tendieren, das Filtern zu erleichtern. Und selbst innerhalb der Welt der inhaltsbasierten Filterung denke ich, dass es gut sein wird, wenn gleichzeitig viele verschiedene Arten von Software verwendet werden. Je mehr verschiedene Filter es gibt, desto schwerer wird es für Spammer, Spams darauf abzustimmen, um durchzukommen.
Anhang: Beispiele für Filterung
Hier ist ein Beispiel für einen Spam, der mir während des Schreibens dieses Artikels zugestellt wurde. 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 Kopfzeilen und aus dem Nachrichtentext, was für Spam typisch 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 aufgetaucht sind.
Leider macht das dieses E-Mail-Beispiel für die Verwendung von Bayes' Regel langweilig. Um eine interessante Vielfalt an Wahrscheinlichkeiten zu sehen, müssen wir uns diesen tatsächlich ziemlich 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 ist der Beweis eine Mischung aus Gutem und Schlechtem. Ein Wort wie "kürzeste" ist fast genauso viel Beweis für Unschuld wie ein Wort wie "Madam" oder "Beförderung" für Schuld. Aber dennoch ist der Fall für Schuld stärker. Wenn Sie diese Zahlen nach Bayes' Regel kombinieren, beträgt die resultierende Wahrscheinlichkeit .9027.
"Madam" stammt offensichtlich aus Spam-Nachrichten, die mit "Sehr geehrte Damen und Herren" beginnen. Sie sind nicht sehr häufig, aber das Wort "Madam" kommt in meiner legitimen E-Mail nie vor, und es geht alles um das Verhältnis.
"Republik" erzielt eine hohe Punktzahl, da es oft in nigerianischen Betrugs-E-Mails auftaucht und auch ein- oder zweimal in Spam-Nachrichten 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 solcher Zufälle gibt, und sie haben eine unheimliche Tendenz, die Dinge in die richtige Richtung zu treiben, anstatt in die falsche. In diesem Fall ist es kein reiner Zufall, dass das Wort "Republik" in nigerianischen Betrugs-E-Mails und in diesem Spam auftaucht. Es gibt eine ganze Klasse zweifelhafter Geschäftsvorschläge, die sich auf weniger entwickelte Länder beziehen, und diese sind wiederum eher dazu geneigt, explizit (weil sie es nicht sind) zu benennen, dass sie Republiken sind.[3]
Andererseits ist "enter" ein echter Fehlgriff. Es kommt hauptsächlich in Abmelde-Anweisungen vor, wird hier aber auf völlig harmlose Weise verwendet. Glücklicherweise ist der statistische Ansatz ziemlich robust und kann eine ganze Reihe von Fehlgriffen tolerieren, bevor die Ergebnisse anfangen, aus dem Ruder zu laufen.
Zum Vergleich [1] ist hier ein Beispiel für diesen seltenen Vogel, einen Spam, der die Filter durchdringt. Warum? Weil er durch reinen Zufall mit Wörtern gespickt 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 hier ein paar gute Nachrichten. Erstens würde diese Mail bei jemandem, der sich nicht zufällig auf Programmiersprachen spezialisiert und einen guten Freund namens Morris hat, wahrscheinlich nicht durch die Filter kommen. Für den Durchschnittsnutzer wären alle fünf wichtigsten Wörter hier neutral und würden nicht zur Spam-Wahrscheinlichkeit beitragen.
Zweitens denke ich, dass das Filtern auf der Grundlage von Wortpaaren (siehe unten) diesen Fall durchaus erwischen könnte: "kostengünstig", "Einrichtungsgebühr", "Geld-zurück" - ziemlich belastendes Material. Und natürlich würde "Hostex" selbst, wenn sie mich weiter mit Spam belästigen würden (oder ein Netzwerk, dem ich angehöre), als Spam-Begriff erkannt werden.
Schließlich [2] ist 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 Wörter hier deuten darauf hin, dass es sich um eine harmlose Mail handelt. Es gibt zwei übel riechende Wörter, "Farbe" (Spammer lieben bunte Schriften) und "Kalifornien" (das in Testimonials und auch in Menüs in Formularen vorkommt), aber sie reichen nicht aus, um die offensichtlich harmlosen Wörter wie "Fortsetzung" und "Beispiel" aufzuwiegen.
Es ist interessant, dass "beschreiben" als so durchweg harmlos eingestuft wird. Es ist in keiner einzigen meiner 4000 Spam-Nachrichten vorgekommen. Die Daten erweisen sich als voller solcher Überraschungen. Eines der Dinge, die man lernt, wenn man Spam-Texte analysiert, ist, wie eng der Bereich ist, in dem sich Spammer bewegen. Es ist diese Tatsache zusammen mit dem ebenso charakteristischen Wortschatz der E-Mails eines jeden Einzelnen, die Bayessche Filterung zu einem guten Wett machen.
Anhang: Weitere Ideen
Eine Idee, die ich noch nicht ausprobiert habe, ist es, nach Wortpaaren oder sogar -tripeln statt nach einzelnen Wörtern zu filtern. Dies sollte zu einer viel schärferen Schätzung der Wahrscheinlichkeit führen. Zum Beispiel hätte in meiner derzeitigen Datenbank das Wort "Angebote" eine Wahrscheinlichkeit von .96. Wenn Sie die Wahrscheinlichkeiten auf der Grundlage von Wortpaaren berechnen würden, würden Sie am Ende bei "Sonderangebote" und "wertvolle Angebote" Wahrscheinlichkeiten von .99 und bei "Ansatz Angebote" (wie in "dieser Ansatz bietet") eine Wahrscheinlichkeit von .1 oder weniger landen.
Der Grund, warum ich das noch nicht gemacht habe, ist, dass das Filtern auf der Grundlage einzelner Wörter bereits so gut funktioniert. Es bedeutet aber, dass es Spielraum gibt, die Filter zu verschärfen, wenn Spam schwerer zu erkennen wird. (Interessanterweise wäre ein Filter auf der Grundlage von Wortpaaren in der Tat ein Markov-Ketten-Textgenerator, der rückwärts läuft.)
Spezifische Spam-Merkmale (z.B. das Fehlen der Empfängeradresse im to:-Feld) haben natürlich auch 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 dies wahrscheinlich in zukünftigen Versionen tun, zumindest für eine Handvoll der offensichtlichsten Spam-Indikatoren.
Die Erkennung von Nicht-Spam-Merkmalen könnte wichtiger sein als die Erkennung von Spam-Merkmalen. Falsch-positive Ergebnisse sind so besorgniserregend, dass sie außergewöhnliche Maßnahmen erfordern. Ich werde in zukünftigen Versionen wahrscheinlich eine zweite Ebene der Überprüfung hinzufügen, die speziell darauf ausgerichtet ist, Falsch-positive zu vermeiden. Wenn eine Mail diese zweite Ebene der Filter auslöst, wird sie akzeptiert, auch wenn ihre Spam-Wahrscheinlichkeit über dem Schwellenwert liegt.
Ich erwarte nicht, dass diese zweite Ebene der Filterung bayesianisch sein wird. Sie wird unvermeidlich nicht nur ad hoc, sondern auch auf Vermutungen basieren, da die Zahl der Falsch-positiven nicht groß genug sein wird, um Muster zu erkennen. (Es ist sowieso gut, wenn ein Backup-System nicht auf der gleichen Technologie wie das Primärsystem basiert.)
Eine weitere Sache, die ich in Zukunft ausprobieren könnte, ist es, besondere Aufmerksamkeit auf bestimmte Teile der E-Mail zu richten. Etwa 95% des derzeitigen Spams enthält die URL einer Website, die man besuchen soll. (Die restlichen 5% wollen, dass man eine Telefonnummer anruft, per E-Mail antwortet oder in einigen Fällen eine bestimmte Aktie kauft.) Die URL ist in solchen Fällen praktisch allein schon ausreichend, um zu bestimmen, ob die E-Mail Spam ist.
Domainnamen unterscheiden sich vom Rest des Texts in einer (nicht-deutschen) E-Mail dadurch, dass sie oft aus mehreren zusammengesetzten Wörtern bestehen. Obwohl dies im Allgemeinen rechenintensiv ist, könnte es sich lohnen, sie zu zerlegen. Wenn ein Filter den Token "xxxporn" noch nie 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 das Zerlegen von Domainnamen wichtiger wird, da Spammer nach und nach gezwungen werden, keine belastenden Wörter mehr im Text ihrer Nachrichten zu verwenden. (Eine URL mit einer IP-Adresse ist natürlich ein extrem belastendes Zeichen, außer in der Mail einiger Systemadministratoren.)
Es wäre eine gute Idee, eine kooperativ gepflegte Liste von URLs zu haben, die von Spammern beworben werden. Wir bräuchten eine Vertrauensmetrik der Art, wie sie von Raph Levien untersucht wurde, um böswillige oder inkompetente Einsendungen zu verhindern, aber wenn wir so etwas hätten, würde es jeder Filtersoftware einen Schub geben. Es wäre auch eine praktische Grundlage für Boykotte.
Eine andere Möglichkeit, zweifelhafte URLs zu testen, wäre, einen Crawler auszusenden, um die Website anzusehen, bevor der Benutzer die E-Mail mit dem Verweis darauf liest. Sie könnten 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 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 kooperatives Projekt, das meiner Meinung nach wirklich eine gute Idee wäre, wäre es, einen riesigen Korpus von Spam anzulegen. Ein großer, sauberer Korpus ist der Schlüssel dafür, dass Bayes'sche Filterung gut funktioniert. Bayes'sche 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 zum Testen verwendet werden könnte.
Die Erstellung eines solchen Korpus wirft einige technische Probleme auf. Wir bräuchten natürlich Vertrauensmetriken, um böswillige oder inkompetente Einsendungen zu verhindern. Wir bräuchten auch Möglichkeiten, persönliche Informationen (nicht nur Empfänger-Adressen und Cc's, sondern auch z.B. die Argumente in URLs zum Abbestellen, die oft die Empfänger-Adresse codieren) aus den Mails im Korpus zu löschen. Wenn sich jemand dazu bereit erklärt, dieses Projekt in Angriff zu nehmen, 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 werden dies tun müssen, wenn wir einen zentralen Korpus von Spam aufbauen oder sogar die Spam-Filterraten sinnvoll vergleichen wollen.
Zunächst einmal ist Spam keine unaufgeforderte kommerzielle E-Mail. Wenn jemand in meiner Nachbarschaft gehört hätte, dass ich auf der Suche nach einem guten gebrauchten Raleigh-Dreigangfahrrad bin, und mir eine E-Mail geschickt hätte, um mir eines anzubieten, wäre ich begeistert, und doch wäre diese E-Mail sowohl kommerziell als auch unaufgefordert. Das entscheidende Merkmal von Spam (in der Tat sein raison d'etre) ist nicht, dass sie unaufgefordert ist, sondern dass sie automatisiert ist.
Es ist auch nur ein Nebenaspekt, dass Spam normalerweise kommerziell ist. Wenn jemand damit beginnen würde, Massen-E-Mails zur Unterstützung einer politischen Sache zu versenden, wäre das genauso Spam wie E-Mails, die eine Pornoseite bewerben.
Ich schlage vor, Spam als unaufgeforderte automatisierte E-Mail zu definieren. Diese Definition umfasst also einige E-Mails, die viele rechtliche Definitionen von Spam nicht einschließen. Rechtliche Definitionen von Spam, die vermutlich von Lobbyisten beeinflusst sind, tendieren dazu, E-Mails von Unternehmen auszuschließen, die eine "bestehende Beziehung" zum Empfänger haben. Aber der Kauf eines Produkts bei einem Unternehmen impliziert nicht, dass Sie fortlaufende 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 auf ihrer Website Ihre "Kontoeinstellungen" zu ändern, wenn Sie keine E-Mails mehr erhalten möchten. Dies reicht nicht aus, um die E-Mails als Nicht-Spam zu stoppen. Nicht abzumelden ist nicht dasselbe wie anzumelden. Solange der Empfänger nicht ausdrücklich ein klar gekennzeichnetes Kästchen (dessen Standardeinstellung "nein" war) angekreuzt hat, in dem er um den Erhalt der E-Mail bittet, handelt es sich um Spam.
In manchen Geschäftsbeziehungen fordern Sie implizit bestimmte Arten von E-Mails an. Wenn Sie online bestellen, denke ich, dass Sie implizit eine Quittung und eine Benachrichtigung über den Versand der Bestellung anfordern. Ich habe nichts dagegen, wenn Verisign mir E-Mails schickt, in denen sie mich warnen, dass ein Domainname bald abläuft (zumindest wenn sie der tatsächliche Registrar dafür sind). Aber wenn Verisign mir E-Mails schickt, in denen sie mir einen KOSTENLOSEN Leitfaden zum Aufbau meiner E-Commerce-Website anbieten, ist das Spam.
Anmerkungen:
[1] Die Beispiele in diesem Artikel sind in Common Lisp übersetzt, und zwar, glauben Sie es oder nicht, für eine größere Zugänglichkeit. 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 für das Versenden einer Million Spam-Nachrichten zu betragen. Das ist sehr billig, 1/50 Cent pro Spam. Aber wenn man 95% des Spams herausfiltert, würde sich die Kosten der Spammer, eine bestimmte Zielgruppe zu erreichen, um den Faktor 20 erhöhen. Nur wenige können Gewinnspannen haben, die groß genug sind, um das zu verkraften.
[3] Als Daumenregel gilt: Je mehr Qualifizierer es vor dem Namen eines Landes gibt, desto korrupter sind die Herrscher. Ein Land, das sich Sozialistische Demokratische Volksrepublik von X nennt, ist wahrscheinlich der letzte Ort auf der Welt, an dem man leben möchte.
Danke an Sarah Harlin für das Lesen von Entwürfen dieses Artikels; 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 zur Statistik.
Sie finden diesen Aufsatz und 14 weitere in Hackers & Painters.
Weitere Informationen: