Ein Plan gegen Spam | undefined | Paul Grahams Essays

Möchten Sie Dinge bauen? Probieren Sie Hacker News.

August 2002

(Dieser Artikel beschreibt die Spam-Filtertechniken, die in unserem webbasierten Mailreader, der für die Ausübung vonArc entwickelt wurde, verwendet werden. Ein verbesserter Algorithmus wird in Better Bayesian Filtering beschrieben.)

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

Für den Empfänger ist Spam leicht erkennbar. Wenn Sie jemanden beauftragen würden, Ihre E-Mails zu lesen und den Spam auszusortieren, hätte diese Person wenig Schwierigkeiten 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 den aktuellen Spam mit nichts anderem als einer bayesianischen Kombination der Spam-Wahrscheinlichkeiten einzelner Wörter akzeptabel gut filtern kann. Mit einem leicht angepassten (wie unten beschrieben) bayesianischen Filter verpassen wir jetzt weniger als 5 von 1000 Spams, mit 0 Fehlalarmen.

Der statistische Ansatz ist normalerweise nicht das Erste, was Leute versuchen, wenn sie Spamfilter 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: Was für eine Frechheit, dass diese Typen versuchen, mir E-Mails zu schicken, die mit „Sehr geehrter Freund“ beginnen oder eine Betreffzeile haben, die komplett in Großbuchstaben geschrieben ist und in acht Ausrufezeichen endet. Ich kann diesen Kram mit etwa einer Zeile Code herausfiltern.

Und das tun Sie, und am Anfang funktioniert es. Ein paar einfache Regeln werden einen großen Teil Ihres eingehenden Spams aussortieren. Allein die Suche nach dem Wort „klicken“ erfasst 79,7 % der E-Mails in meinem Spam-Korpus, mit nur 1,2 % Fehlalarmen.

Ich habe etwa sechs Monate damit verbracht, Software zu schreiben, die einzelne Spam-Merkmale erkannte, bevor ich den statistischen Ansatz ausprobierte. Was ich feststellte, war, dass die Erkennung der letzten paar Prozent Spams sehr schwierig wurde und dass ich, je strenger ich die Filter machte, mehr Fehlalarme bekam.

Fehlalarme sind unschuldige E-Mails, die fälschlicherweise als Spam identifiziert werden. Für die meisten Benutzer ist das Verpassen legitimer E-Mails um eine Größenordnung schlimmer als der Empfang von Spam, daher ist ein Filter, der Fehlalarme liefert, wie ein Akne-Heilmittel, das ein Todesrisiko für den Patienten birgt.

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

Ich weiß nicht, warum ich den statistischen Ansatz so lange vermieden habe. Ich glaube, es lag daran, dass ich süchtig danach wurde, Spam-Merkmale selbst zu identifizieren, als ob ich eine Art Wettkampfspiel mit den Spammern spielen würde. (Nicht-Hacker erkennen das nicht oft, aber die meisten Hacker sind sehr wettbewerbsorientiert.) Als ich dann statistische Analysen durchführte, stellte ich sofort fest, dass sie viel cleverer war als ich. Sie entdeckte natürlich, dass Begriffe wie „virtumundo“ und „teens“ gute Indikatoren für Spam sind. Aber sie entdeckte auch, dass „per“ und „FL“ und „ff0000“ gute Indikatoren für Spam sind. Tatsächlich erweist sich „ff0000“ (HTML für leuchtend rot) als ebenso guter Indikator für Spam wie jeder pornografische Begriff.

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

Ich zähle, wie oft jedes Token (Groß-/Kleinschreibung wird ignoriert) in jedem Korpus vorkommt. In diesem Stadium erhalte ich zwei große Hash-Tabellen, eine für jeden Korpus, die Tokens auf die Anzahl der Vorkommen abbilden.

Als Nächstes erstelle ich eine dritte Hash-Tabelle, die jedes Token auf die Wahrscheinlichkeit abbildet, dass eine E-Mail, die es 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 das 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- und Spam-Nachrichten sind.

Ich habe dies als Code erklärt, um ein paar wichtige Details zu zeigen. Ich möchte die Wahrscheinlichkeiten leicht verzerren, um Fehlalarme zu vermeiden, und durch Versuch und Irrtum habe ich festgestellt, dass eine gute Methode 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 wegen der Verdoppelung dreimaliges Vorkommen in Nicht-Spam-Mails ausreichen). Und dann gibt es die Frage, welche Wahrscheinlichkeit man Wörtern zuweisen soll, die in einem Korpus vorkommen, aber nicht im anderen. Wieder durch Versuch und Irrtum habe ich .01 und .99 gewählt. Hier gibt es vielleicht Raum für Anpassungen, aber wenn der Korpus wächst, werden solche Anpassungen ohnehin automatisch erfolgen.

Die besonders Aufmerksamen werden bemerken, dass ich, während ich jeden Korpus als einen einzigen langen Textstrom zum Zählen von Vorkommen betrachte, die Anzahl der E-Mails in jedem, anstatt ihre kombinierte Länge, als Nenner bei der Berechnung der Spam-Wahrscheinlichkeiten verwende. Dies fügt eine weitere leichte Verzerrung hinzu, um Fehlalarme zu vermeiden.

Wenn neue E-Mails eintreffen, werden sie in Tokens gescannt, und die fünfzehn interessantesten Tokens, wobei interessant gemessen wird, wie weit ihre Spam-Wahrscheinlichkeit von einem neutralen .5 abweicht, werden verwendet, um die Wahrscheinlichkeit zu berechnen, dass die E-Mail Spam ist. Wenn probs eine Liste der fünfzehn einzelnen Wahrscheinlichkeiten ist, berechnen Sie die kombinierte Wahrscheinlichkeit wie folgt: (let ((prod (apply #'* probs))) (/ prod (+ prod (apply #'* (mapcar #'(lambda (x) (- 1 x)) probs))))) Eine Frage, die in der Praxis auftritt, ist, welche Wahrscheinlichkeit man einem Wort zuweisen soll, das man noch nie gesehen hat, d. h. einem, das nicht in der Hash-Tabelle der Wortwahrscheinlichkeiten vorkommt. Ich habe, wieder durch Versuch und Irrtum, festgestellt, dass .4 eine gute Zahl dafür ist. Wenn Sie ein Wort noch nie zuvor gesehen haben, ist es wahrscheinlich ziemlich unschuldig; Spam-Wörter sind oft nur allzu vertraut.

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

Ich behandle E-Mails als Spam, wenn der obige Algorithmus ihnen eine Wahrscheinlichkeit von mehr als 0,9 gibt, dass es sich um Spam handelt. Aber in der Praxis würde es nicht viel ausmachen, wo ich diesen Schwellenwert 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 das ist wirklich 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 bayesianischen Ansatzes ist natürlich, dass man weiß, was man misst. Merkmalserkennende Filter wie SpamAssassin weisen E-Mails eine Spam-"Punktzahl" zu. Der bayesianische Ansatz weist eine tatsächliche Wahrscheinlichkeit zu. Das Problem mit einer "Punktzahl" ist, dass niemand weiß, was sie bedeutet. Der Benutzer weiß nicht, was sie bedeutet, aber schlimmer noch, auch der Entwickler des Filters nicht. Wie viele Punkte sollte eine E-Mail für das Wort „sex“ bekommen? Eine Wahrscheinlichkeit kann natürlich falsch sein, aber es gibt wenig Mehrdeutigkeit darüber, was sie bedeutet oder wie Beweise kombiniert werden sollten, um sie zu berechnen. Basierend auf meinem Korpus zeigt „sex“ eine Wahrscheinlichkeit von 0,97 an, dass die enthaltende E-Mail Spam ist, während „sexy“ eine Wahrscheinlichkeit von 0,99 anzeigt. Und die Bayes'sche Regel, ebenso eindeutig, besagt, dass eine E-Mail, die beide Wörter enthält, in der (unwahrscheinlichen) Abwesenheit anderer Beweise eine 99,97%ige Chance hat, Spam zu sein.

Da der bayesianische Ansatz Wahrscheinlichkeiten misst, berücksichtigt er alle Beweise in der E-Mail, sowohl gute als auch schlechte. Wörter, die in Spam selten vorkommen (wie „though“ oder „tonight“ oder „apparently“), tragen genauso zur Verringerung der Wahrscheinlichkeit bei wie schlechte Wörter wie „unsubscribe“ und „opt-in“ zu ihrer Erhöhung. Eine ansonsten unschuldige E-Mail, die zufällig das Wort „sex“ enthält, wird also nicht als Spam markiert.

Idealerweise sollten die Wahrscheinlichkeiten natürlich individuell für jeden Benutzer berechnet werden. Ich erhalte viele E-Mails, die das Wort „Lisp“ enthalten, und (bisher) keinen Spam, der es tut. Ein Wort wie dieses ist also effektiv eine Art Passwort, um mir E-Mails zu schicken. In meiner früheren Spam-Filter-Software konnte der Benutzer eine Liste solcher Wörter einrichten, und E-Mails, die sie enthielten, würden automatisch die Filter passieren. Auf meiner Liste stehen Wörter wie „Lisp“ und auch meine Postleitzahl, damit (sonst eher spamverdächtig klingende) Quittungen von Online-Bestellungen durchgehen. Ich dachte, ich wäre sehr schlau, aber ich stellte fest, dass der bayesianische Filter dasselbe für mich tat und darüber hinaus viele Wörter entdeckte, an die ich nicht gedacht hatte.

Als ich am Anfang sagte, dass unsere Filter weniger als 5 Spams pro 1000 mit 0 Fehlalarmen durchlassen, spreche ich vom Filtern meiner E-Mails basierend auf einem Korpus meiner E-Mails. 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 dem Spam und Nicht-Spam, den er erhält. Im Wesentlichen sollte jeder Benutzer zwei Löschschaltflächen haben: „normal löschen“ und „als Spam löschen“. 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 beginnen, aber letztendlich sollte jeder Benutzer seine eigenen Pro-Wort-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 genaue Definition von Spam festlegen und (c) macht es vielleicht am besten, Spammer daran zu hindern, E-Mails so abzustimmen, dass sie die Filter passieren. Wenn ein Großteil des Gehirns des Filters in den individuellen Datenbanken steckt, dann garantiert die bloße Abstimmung von Spams, um die Seed-Filter zu passieren, nichts darüber, wie gut sie die variierenden und viel besser trainierten Filter einzelner Benutzer passieren werden.

Inhaltsbasierte Spam-Filterung wird oft mit einer Whitelist kombiniert, einer Liste von Absendern, deren E-Mails ohne Filterung akzeptiert werden können. 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 Mailreader eine Schaltfläche „als Spam löschen“ hat, könnten Sie 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 eine Möglichkeit, Rechenleistung zu sparen, als eine Möglichkeit, die Filterung zu verbessern. Ich dachte früher, dass Whitelists die Filterung erleichtern würden, da man nur E-Mails von Leuten filtern müsste, von denen man noch nie gehört hatte, und jemand, der Ihnen zum ersten Mal eine E-Mail schickt, ist durch Konventionen in dem, was er Ihnen sagen kann, eingeschränkt. Jemand, den Sie bereits kennen, könnte Ihnen eine E-Mail über Sex schicken, aber jemand, der Ihnen zum ersten Mal eine E-Mail schickt, würde dies wahrscheinlich nicht tun. Das Problem ist, dass Leute mehr als eine E-Mail-Adresse haben können, sodass eine neue Absenderadresse nicht garantiert, dass der Absender Sie zum ersten Mal kontaktiert. 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, sodass Sie keine Fehlalarme riskieren können, indem Sie E-Mails von unbekannten Adressen besonders streng filtern.

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

Wenn ich dachte, dass ich die aktuellen Spam-Filterraten aufrechterhalten könnte, würde ich dieses Problem als gelöst betrachten. Aber es bedeutet nicht viel, die meisten aktuellen Spams herausfiltern zu können, weil sich Spam weiterentwickelt. Tatsächlich waren die meisten bisherigen Antispam-Techniken wie Pestizide, die nichts weiter tun, als eine neue, resistente Keimart zu schaffen.

Ich bin hoffnungsvoller bei bayesianischen Filtern, weil sie sich mit dem Spam weiterentwickeln. Wenn Spammer also beginnen, „c0ck“ anstelle von „cock“ zu verwenden, um einfältige Spamfilter zu umgehen, die auf einzelnen Wörtern basieren, bemerken bayesianische Filter dies automatisch. Tatsächlich ist „c0ck“ ein weitaus stärkerer Beweis als „cock“, und bayesianische Filter wissen genau, wie viel stärker.

Dennoch muss jeder, der einen Plan für die 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 glaube zum Beispiel, dass, wenn checksum-basierte Spam-Filterung zu einem ernsthaften Hindernis wird, die Spammer einfach zu Mad-Lib-Techniken zur Generierung von Nachrichtentexten wechseln werden.

Um bayesianische Filter zu schlagen, würde es nicht ausreichen, wenn Spammer ihre E-Mails einzigartig machen oder aufhören, einzelne unanständige Wörter zu verwenden. Sie müssten ihre E-Mails von Ihren normalen E-Mails ununterscheidbar machen. Und das, denke ich, würde sie stark einschränken. Spam sind meist Verkaufsangebote, also wenn Ihre regulären E-Mails keine Verkaufsangebote sind, werden Spams zwangsläufig einen anderen Charakter haben. Und die Spammer müssten natürlich auch ihre gesamte Infrastruktur ändern (und weiter ändern), denn sonst würden die Header für die bayesianischen Filter genauso schlecht aussehen wie immer, egal was sie am Nachrichtentext tun. Ich weiß nicht genug über die Infrastruktur, die Spammer verwenden, um zu wissen, wie schwer es wäre, die Header unauffällig aussehen zu lassen, aber ich vermute, dass es noch schwieriger wäre, als den Nachrichtentext unauffällig aussehen zu lassen.

Unter der Annahme, dass sie das Problem der Header lösen könnten, wird der Spam der Zukunft wahrscheinlich so aussehen: Hallo. Ich dachte, Sie sollten sich Folgendes ansehen: http://www.27meg.com/foo, denn das ist ungefähr so viel Verkaufsgespräch, wie der inhaltsbasierte Filter dem Spammer Raum lässt. (Tatsächlich wird es sogar schwierig sein, dies durch Filter zu bekommen, denn wenn alles andere in der E-Mail neutral ist, hängt die Spam-Wahrscheinlichkeit vom URL ab, und es wird einige Anstrengungen erfordern, diese neutral aussehen zu lassen.)

Spammer reichen von Unternehmen, die sogenannte Opt-in-Listen führen und ihre Identitäten nicht einmal verbergen, bis hin zu Typen, die Mailserver kapern, um Spam für Porno-Seiten zu versenden. Wenn wir Filter verwenden, um ihre Optionen auf E-Mails wie die obige zu reduzieren, sollten wir die Spammer am „legitimen“ Ende des Spektrums ziemlich aus dem Geschäft drängen; sie fühlen sich durch verschiedene Landesgesetze verpflichtet, Boilerplate darüber aufzunehmen, warum ihr Spam kein Spam ist und wie man sein „Abonnement“ kündigt, und diese Art von Text ist leicht zu erkennen.

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

Entlang des gesamten Spektrums, wenn Sie die Verkaufsangebote, die Spammer machen können, einschränken, werden Sie sie zwangsläufig aus dem Geschäft drängen. Das Wort Geschäft ist wichtig zu merken. Die Spammer sind Geschäftsleute. Sie senden Spam, weil es funktioniert. Es funktioniert, weil, obwohl die Antwortrate abscheulich niedrig ist (im besten Fall 15 pro Million, gegenüber 3000 pro Million für eine Katalogwerbung), die Kosten für sie praktisch nichts betragen. Die Kosten sind für die Empfänger 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 senken können – sei es durch Filterung oder durch die Verwendung von Filtern, um Spammer zu zwingen, ihre Angebote zu verwässern – desto weniger Unternehmen werden es für lohnenswert halten, Spam zu versenden.

Der Grund, warum Spammer die Art von Verkaufsangeboten verwenden, die sie verwenden, ist die Erhöhung der Antwortraten. Dies ist möglicherweise noch widerlicher, als in den Kopf eines Spammers zu gelangen, aber werfen wir einen kurzen Blick in den Kopf von jemandem, der auf einen Spam antwortet. Diese Person ist entweder erstaunlich glaubwürdig oder tief in der Verleugnung ihrer sexuellen Interessen. In beiden Fällen ist abstoßend oder idiotisch, wie der Spam uns erscheint, für sie 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 bei dem Spam-Empfänger nicht annähernd so viel Anziehungskraft haben wie die Dinge, die Spammer jetzt sagen. Ergebnis: Wenn er keine aufregenden Verkaufsangebote enthalten kann, wird Spam als Marketinginstrument weniger effektiv, und weniger Unternehmen wollen ihn nutzen.

Das ist letztendlich der große Gewinn. Ich begann, Spam-Filtersoftware zu schreiben, weil ich den Kram nicht mehr sehen wollte. Aber wenn wir gut genug im Filtern von Spam werden, wird er aufhören zu funktionieren, und die Spammer werden tatsächlich aufhören, ihn zu senden.

Von allen Ansätzen zur Bekämpfung von Spam, von Software bis hin zu Gesetzen, glaube ich, dass die bayesianische Filterung die 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 die Filterung tendenziell erleichtern. Und selbst innerhalb der inhaltsbasierten Filterung denke ich, dass es gut wäre, wenn viele verschiedene Arten von Software gleichzeitig verwendet würden. Je mehr verschiedene Filter es gibt, desto schwieriger wird es für Spammer, Spams so abzustimmen, dass sie sie passieren.

Anhang: Beispiele für die Filterung

Hier ist ein Beispiel für einen Spam, der während des Schreibens dieses Artikels eingegangen 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 gesehen wurden.

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

Die fünfzehn interessantesten Wörter in diesem Spam mit ihren Wahrscheinlichkeiten sind: madam 0.99 promotion 0.99 republic 0.99 shortest 0.047225013 mandatory 0.047225013 standardization 0.07347802 sorry 0.08221981 supported 0.09019077 people's 0.09019077 enter 0.9075001 quality 0.8921298 organization 0.12454646 investment 0.8568143 very 0.14758544 valuable 0.82347786 Diesmal ist die Evidenz eine Mischung aus gut und schlecht. Ein Wort wie „shortest“ ist fast genauso viel Beweis für Unschuld wie ein Wort wie „madam“ oder „promotion“ für Schuld. Aber immer noch ist der Fall für Schuld stärker. Wenn man diese Zahlen nach der Bayes'schen Regel kombiniert, beträgt die resultierende Wahrscheinlichkeit 0,9027.

„Madam“ stammt offensichtlich aus Spams, die mit „Sehr geehrte Damen und Herren“ beginnen. Sie sind nicht sehr verbreitet, aber das Wort „madam“ kommt in meinen legitimen E-Mails nie vor, und es geht nur um das Verhältnis.

„Republic“ erzielt hohe Werte, da es oft in nigerianischen Betrugs-E-Mails vorkommt 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 hilft, diesen Spam zu identifizieren. Aber ich habe bei der Untersuchung von Spam-Wahrscheinlichkeiten festgestellt, dass es viele dieser Zufälle gibt, und sie haben eine unheimliche Tendenz, die Dinge in die richtige Richtung zu lenken, anstatt in die falsche. In diesem Fall ist es keine völlige Zufälligkeit, dass das Wort „Republic“ in nigerianischen Betrugs-E-Mails und diesem Spam vorkommt. Es gibt eine ganze Klasse zweifelhafter Geschäftsvorschläge, die weniger entwickelte Länder betreffen, und diese wiederum haben eher Namen, die explizit (weil sie es nicht sind) angeben, dass sie Republiken sind.[3]

Auf der anderen Seite ist „enter“ ein echter Fehlgriff. Es kommt meistens in Abmeldehinweisen vor, wird hier aber auf völlig unschuldige Weise verwendet. Glücklicherweise ist der statistische Ansatz ziemlich robust und kann viele Fehlgriffe tolerieren, bevor die Ergebnisse verfälscht werden.

Zum Vergleich, hier ist ein Beispiel für diesen seltenen Vogel, einen Spam, der die Filter passiert. Warum? Weil er zufällig mit Wörtern vollgestopft ist, die in meinen tatsächlichen E-Mails 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 E-Mail wahrscheinlich nicht die Filter von jemandem passieren, der sich nicht zufällig auf Programmiersprachen spezialisiert hat und einen guten Freund namens Morris hat. Für den Durchschnittsnutzer wären alle fünf Top-Wörter hier neutral und würden nicht zur Spam-Wahrscheinlichkeit beitragen.

Zweitens denke ich, dass die Filterung basierend auf Wortpaaren (siehe unten) diese hier gut erfassen könnte: „cost effective“, „setup fee“, „money back“ – ziemlich belastende Sachen. Und natürlich, wenn sie mich (oder ein Netzwerk, dem ich angehörte) weiterhin spammen 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 E-Mail unschuldig ist. Es gibt zwei verdächtig klingende Wörter, „color“ (Spammer lieben farbige Schriftarten) und „California“ (das in Testimonials und auch in Formularen vorkommt), aber sie reichen nicht aus, um offensichtlich unschuldige Wörter wie „continuation“ und „example“ aufzuwiegen.

Es ist interessant, dass „describe“ als so durch und durch unschuldig eingestuft wird. Es ist in keiner meiner 4000 Spams vorgekommen. Die Daten sind voller solcher Überraschungen. Eines der Dinge, die man lernt, wenn man Spam-Texte analysiert, ist, wie eng die Sprache, in der Spammer operieren, ein Subset ist. Es ist diese Tatsache, zusammen mit dem ebenso charakteristischen Vokabular der E-Mails eines jeden Benutzers, die die bayesianische Filterung zu einer guten Wahl macht.

Anhang: Weitere Ideen

Eine Idee, die ich noch nicht ausprobiert habe, ist die Filterung basierend auf Wortpaaren oder sogar Tripeln anstelle von einzelnen Wörtern. Dies sollte eine viel schärfere Schätzung der Wahrscheinlichkeit ergeben. Zum Beispiel hat in meiner aktuellen Datenbank das Wort „offers“ eine Wahrscheinlichkeit von 0,96. Wenn Sie die Wahrscheinlichkeiten auf Wortpaaren basieren würden, würden Sie „special offers“ und „valuable offers“ mit Wahrscheinlichkeiten von 0,99 und „approach offers“ (wie in „this approach offers“) mit einer Wahrscheinlichkeit von 0,1 oder weniger erhalten.

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 schwerer zu erkennen wird. (Seltsamerweise wäre ein Filter, der auf Wortpaaren basiert, im Wesentlichen ein Markov-Ketten-Textgenerator, der rückwärts läuft.)

Spezifische Spam-Merkmale (z. B. das Nichtvorhandensein der Adresse des Empfängers im To:-Feld) haben natürlich einen Wert bei der Erkennung von Spam. Sie können in diesem Algorithmus berücksichtigt werden, indem sie als virtuelle Wörter behandelt werden. Ich werde dies wahrscheinlich in zukünftigen Versionen tun, zumindest für eine Handvoll der gravierendsten Spam-Indikatoren. Merkmalserkennende Spam-Filter liegen in vielen Details richtig; was ihnen fehlt, ist eine allgemeine Disziplin zur Kombination von Beweisen.

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

Ich erwarte nicht, dass diese zweite Filterebene bayesianisch sein wird. Sie wird zwangsläufig nicht nur ad hoc sein, sondern auf Vermutungen basieren, da die Anzahl der Fehlalarme nicht groß genug sein wird, um Muster zu erkennen. (Es ist sowieso gut, wenn ein Backup-System nicht auf derselben 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 berücksichtigen. Zum Beispiel enthalten etwa 95 % des aktuellen Spams die URL einer Website, die sie besuchen 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 genug, um allein zu bestimmen, ob die E-Mail Spam ist.

Domainnamen unterscheiden sich von den übrigen Texten in einer (nicht-deutschen) E-Mail dadurch, dass sie oft aus mehreren zusammengesetzten Wörtern bestehen. Obwohl dies im allgemeinen Fall 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 Spam-Wahrscheinlichkeit von 0,4, während „xxx“ und „porn“ einzeln Wahrscheinlichkeiten (in meinem Korpus) von 0,9889 bzw. 0,99 und eine kombinierte Wahrscheinlichkeit von 0,9998 haben.

Ich erwarte, dass die Zerlegung von Domainnamen wichtiger wird, da Spammer gezwungen sind, belastende Wörter im Text ihrer Nachrichten zu verwenden. (Eine URL mit einer IP-Adresse ist natürlich ein extrem belastendes Zeichen, außer in der E-Mail einiger Sysadmins.)

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 der von Raph Levien untersuchten Art, um böswillige oder inkompetente Einreichungen zu verhindern, aber wenn wir so etwas hätten, würde es jede Filtersoftware stärken. 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 zu überprüfen, bevor der Benutzer die erwähnte E-Mail ansieht. Sie könnten einen bayesianischen Filter verwenden, um die Website genauso zu bewerten wie eine E-Mail, und alles, was auf der Website gefunden wurde, könnte in die Berechnung der Spam-Wahrscheinlichkeit der E-Mail einbezogen werden. 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, ist die Ansammlung eines riesigen Spam-Korpus. Ein großer, sauberer Korpus ist der Schlüssel, um die bayesianische Filterung gut funktionieren zu lassen. Bayesianische Filter könnten den Korpus tatsächlich als Eingabe verwenden. Aber ein solcher Korpus wäre auch für andere Filterarten nützlich, da er zu deren Testen verwendet werden könnte.

Die Erstellung eines solchen Korpus birgt einige technische Probleme. 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 To-Adressen und Ccs, sondern auch z. B. die Argumente von Abmelde-URLs, die oft die To-Adresse kodieren) aus den E-Mails im Korpus zu löschen. Wenn jemand dieses Projekt übernehmen möchte, wäre es gut für die Welt.

Anhang: Spam definieren

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

Zunächst einmal ist Spam keine unerbetene kommerzielle E-Mail. Wenn jemand in meiner Nachbarschaft gehört hätte, dass ich nach einem alten Raleigh Dreigangrad in gutem Zustand suche, und mir eine E-Mail geschickt hätte, um es mir zu verkaufen, wäre ich begeistert, und doch wäre diese E-Mail sowohl kommerziell als auch unerbeten. Das definierende Merkmal von Spam (tatsächlich sein raison d'être) ist nicht, dass es unerbeten ist, sondern dass es automatisiert ist.

Es ist auch nur zufällig, dass Spam normalerweise kommerziell ist. Wenn jemand massenhaft E-Mails zur Unterstützung einer politischen Sache versenden würde, wäre dies genauso Spam wie E-Mails, die für eine Porno-Website werben.

Ich schlage vor, Spam als unerbetene automatisierte E-Mail zu definieren. Diese Definition schließt somit einige E-Mails ein, die viele rechtliche Definitionen von Spam nicht einschließen. Rechtliche Definitionen von Spam, die vermutlich von Lobbyisten beeinflusst werden, schließen E-Mails von Unternehmen aus, die eine „bestehende Beziehung“ zum Empfänger haben. Aber etwas von einem Unternehmen zu kaufen, impliziert nicht, dass Sie fortlaufende E-Mails von ihnen angefordert haben. Wenn ich etwas bei einem Online-Shop bestelle und sie mir dann eine Flut von Spam schicken, ist das immer noch Spam.

Unternehmen, die Spam versenden, bieten Ihnen oft 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. Das reicht nicht aus, um die E-Mail als Spam zu kennzeichnen. Nicht abzumelden ist nicht dasselbe wie sich anzumelden. Sofern der Empfänger nicht ausdrücklich ein klar gekennzeichnetes Kästchen angekreuzt hat (dessen Standardeinstellung „nein“ war), um die E-Mail zu erhalten, dann ist es Spam.

In einigen Geschäftsbeziehungen fordern Sie bestimmte Arten von E-Mails implizit an. Wenn Sie online bestellen, denke ich, dass Sie implizit eine Quittung und eine Benachrichtigung über den Versand der Bestellung anfordern. Es macht mir nichts aus, wenn Verisign mir eine E-Mail schickt, die mich warnt, dass ein Domainname bald abläuft (zumindest, wenn sie der tatsächliche Registrar dafür sind). Aber wenn Verisign mir eine E-Mail schickt, die einen KOSTENLOSEN Leitfaden zum Aufbau meiner E-Commerce-Website anbietet, ist das Spam.

Anmerkungen:

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

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

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

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

Sie finden diesen Aufsatz und 14 weitere in Hackers & Painters.

Mehr Infos: