BESSERES BAYESISCHES FILTERN

Januar 2003

(Dieser Artikel wurde als Vortrag auf der Spam-Konferenz 2003 gehalten. Er beschreibt die Arbeit, die ich geleistet habe, um die Leistung des in A Plan for Spam beschriebenen Algorithmus zu verbessern, und was ich in Zukunft zu tun plane.)

Die erste Entdeckung, die ich hier präsentieren möchte, ist ein Algorithmus für die faule Auswertung von Forschungsarbeiten. Schreiben Sie einfach, was Sie wollen, und zitieren Sie keine früheren Arbeiten, und empörte Leser werden Ihnen Verweise auf alle Papiere schicken, die Sie hätten zitieren sollen. Ich habe diesen Algorithmus entdeckt, nachdem ``A Plan for Spam'' [1] auf Slashdot war.

Spam-Filterung ist eine Teilmenge der Textklassifizierung, die ein etabliertes Gebiet ist, aber die ersten Arbeiten über Bayessche Spam-Filterung an sich scheinen zwei gewesen zu sein, die auf derselben Konferenz 1998 vorgestellt wurden, eine von Pantel und Lin [2], und eine andere von einer Gruppe aus Microsoft Research [3].

Als ich von dieser Arbeit hörte, war ich etwas überrascht. Wenn die Leute vor vier Jahren schon auf Bayessche Filterung gekommen waren, warum benutzte sie dann nicht jeder? Als ich die Papiere las, fand ich heraus, warum. Pantel und Lins Filter war der effektivere der beiden, aber er fing nur 92% des Spams ab, mit 1,16% Fehlalarmen.

Als ich versuchte, einen Bayesschen Spam-Filter zu schreiben, fing er 99,5% des Spams mit weniger als 0,03% Fehlalarmen ab [4]. Es ist immer beunruhigend, wenn zwei Leute dasselbe Experiment durchführen und völlig unterschiedliche Ergebnisse erzielen. Hier ist es besonders beunruhigend, weil diese beiden Zahlenreihen zu entgegengesetzten Schlussfolgerungen führen könnten. Verschiedene Nutzer haben unterschiedliche Anforderungen, aber ich denke, für viele Menschen bedeutet eine Filterrate von 92% mit 1,16% Fehlalarmen, dass die Filterung keine akzeptable Lösung ist, während 99,5% mit weniger als 0,03% Fehlalarmen bedeuten, dass sie es ist.

Warum also haben wir so unterschiedliche Zahlen bekommen? Ich habe nicht versucht, Pantel und Lins Ergebnisse zu reproduzieren, aber aus dem Lesen des Papiers sehe ich fünf Dinge, die die Unterschiede wahrscheinlich erklären.

Eines ist einfach, dass sie ihren Filter mit sehr wenigen Daten trainierten: 160 Spam- und 466 Nicht-Spam-Mails. Die Filterleistung sollte bei so kleinen Datensätzen immer noch steigen. Daher sind ihre Zahlen möglicherweise nicht einmal eine genaue Messung der Leistung ihres Algorithmus, geschweige denn des Bayesschen Spam-Filterns im Allgemeinen.

Aber ich denke, der wichtigste Unterschied ist wahrscheinlich dass sie die Nachrichtenköpfe ignorierten. Für jeden, der an Spam-Filtern gearbeitet hat, wird dies eine perverse Entscheidung erscheinen. Und doch habe ich in den ersten Filtern, die ich zu schreiben versuchte, die Köpfe auch ignoriert. Warum? Weil ich das Problem sauber halten wollte. Ich wusste damals nicht viel über Mail-Köpfe und sie erschienen mir voller zufälliger Dinge. Hier gibt es eine Lektion für Filterschreiber: Ignorieren Sie keine Daten. Man sollte meinen, diese Lektion wäre zu offensichtlich, um erwähnt zu werden, aber ich musste sie mehrmals lernen.

Drittens haben Pantel und Lin die Token gestempelt, d.h. sie haben z.B. sowohl mailing'' als auch mailed'' auf die Wurzel ``mail'' reduziert. Sie haben vielleicht das Gefühl gehabt, dass sie dazu gezwungen waren aufgrund der geringen Größe ihres Korpus, aber wenn dem so ist, ist dies eine Art vorzeitige Optimierung.

Viertens haben sie die Wahrscheinlichkeiten anders berechnet. Sie verwendeten alle Token, während ich nur die 15 wichtigsten verwende. Wenn man alle Token verwendet, wird man dazu neigen, längere Spams zu verpassen, also den Typ, bei dem jemand Ihnen seine Lebensgeschichte bis zu dem Punkt erzählt, an dem er durch ein Mehrstufenmarketing-Schema reich geworden ist. Und ein solcher Algorithmus wäre für Spammer leicht zu täuschen: Fügen Sie einfach einen großen Zufallstext-Block hinzu, um die Spam-Begriffe auszugleichen.

Schließlich haben sie nicht gegen Fehlalarme gewichtet. Ich denke, jeder Spam-Filteralgorithmus sollte einen praktischen Regler haben, mit dem man die Fehlalarmrate auf Kosten der Filterrate senken kann. Ich tue dies, indem ich die Häufigkeiten der Token im Nicht-Spam-Korpus doppelt zähle.

Ich denke nicht, dass es eine gute Idee ist, die Spam-Filterung als ein reines Textklassifizierungsproblem zu behandeln. Man kann Textklassifizierungstechniken verwenden, aber Lösungen können und sollten die Tatsache widerspiegeln, dass der Text E-Mail ist und insbesondere Spam. E-Mail ist nicht nur Text; sie hat eine Struktur. Spam-Filterung ist nicht nur Klassifizierung, weil Fehlalarme so viel schlimmer sind als Fehleinschätzungen, dass man sie als eine andere Art von Fehler behandeln sollte. Und die Fehlerquelle ist nicht nur zufällige Variation, sondern ein aktiv arbeitender menschlicher Spammer, der versucht, Ihren Filter zu besiegen.

Tokens

Ein weiteres Projekt, von dem ich nach dem Slashdot-Artikel gehört habe, war Bill Yerazunis' CRM114 [5]. Dies ist das Gegenbeispiel zu dem Entwurfsprinzip, das ich gerade erwähnt habe. Es ist ein reiner Textklassifizierer, aber ein so erstaunlich effektiver, dass er Spam fast perfekt filtert, ohne einmal zu wissen, dass das sein Ziel ist.

Sobald ich verstanden hatte, wie CRM114 funktioniert, schien es unvermeidlich, dass ich irgendwann von der Filterung auf der Basis einzelner Wörter zu einem Ansatz wie diesem wechseln müsste. Aber zuerst, dachte ich, werde ich sehen, wie weit ich mit einzelnen Wörtern komme. Und die Antwort ist, überraschenderweise sehr weit.

Hauptsächlich habe ich an einer klügeren Tokenisierung gearbeitet. Bei aktuellen Spam-Nachrichten konnte ich Filterraten erreichen, die an CRM114 heranreichen. Diese Techniken sind meist orthogonal zu Bills; eine optimale Lösung könnte beide einbeziehen.

``A Plan for Spam'' verwendet eine sehr einfache Definition eines Tokens. Buchstaben, Ziffern, Bindestriche, Apostrophe, und Dollarzeichen sind Bestandteile, und alles andere ist ein Tokentrennzeichen. Ich habe auch Groß-/Kleinschreibung ignoriert.

Jetzt habe ich eine kompliziertere Definition eines Tokens:

Die Groß-/Kleinschreibung wird beibehalten.

Ausrufezeichen sind Bestandteile.

Punkte und Kommas sind Bestandteile, wenn sie zwischen zwei Ziffern auftreten. Das ermöglicht mir, IP-Adressen und Preise intakt zu halten.

Ein Preisbereich wie $20-25 ergibt zwei Token, $20 und $25.

Token, die innerhalb der To-, From-, Subject- und Return-Path-Zeilen oder innerhalb von URLs auftreten, werden entsprechend gekennzeichnet. Z.B. wird foo'' in der Betreffzeile zu Subject*foo''. (Der Stern könnte ein beliebiges Zeichen sein, das Sie als Bestandteil nicht zulassen.)

Solche Maßnahmen erhöhen den Wortschatz des Filters, was ihn diskriminierender macht. Zum Beispiel hat im aktuellen Filter das Wort ``free'' in der Betreffzeile eine Spam-Wahrscheinlichkeit von 98%, während dasselbe Token im Textkörper nur eine Spam-Wahrscheinlichkeit von 65% hat.

Hier sind einige der aktuellen Wahrscheinlichkeiten [6]:

ThemaKOSTENLOS 0,9999 kostenlos!! 0,9999 Zukostenlos 0,9998 Themakostenlos 0,9782 kostenlos! 0,9199 Kostenlos 0,9198 Urlkostenlos 0,9091 KOSTENLOS 0,8747 Von*kostenlos 0,7636 kostenlos 0,6546

Im Plan für den Spam-Filter hätten all diese Token die gleiche Wahrscheinlichkeit von .7602 gehabt. Dieser Filter erkannte etwa 23.000 Token. Der aktuelle erkennt etwa 187.000.

Der Nachteil eines größeren Universums von Token ist, dass es mehr Fehlschläge gibt. Wenn man seinen Korpus auf mehr Token verteilt, hat das den gleichen Effekt wie ihn zu verkleinern. Wenn man Ausrufezeichen als Bestandteile betrachtet, könnte man zum Beispiel keine Spam-Wahrscheinlichkeit für "kostenlos" mit sieben Ausrufezeichen haben, obwohl man weiß, dass "kostenlos" mit nur zwei Ausrufezeichen eine Wahrscheinlichkeit von 99,99% hat.

Eine Lösung dafür ist, was ich "Degeneration" nenne. Wenn man keine exakte Übereinstimmung für ein Token findet, behandelt man es, als wäre es eine weniger spezifische Version. Ich betrachte Endausrufezeichen, Großbuchstaben und das Vorkommen in einem der fünf markierten Kontexte als Faktoren, die ein Token spezifischer machen. Zum Beispiel, wenn ich keine Wahrscheinlichkeit für "Themakostenlos!" finde, suche ich nach Wahrscheinlichkeiten für "Themakostenlos", "kostenlos!" und "kostenlos" und nehme die, die am weitesten von .5 entfernt ist.

Hier sind die Alternativen [7], die der Filter in Betracht zieht, wenn er "KOSTENLOS!!!" im Betreff sieht und keine Wahrscheinlichkeit dafür hat.

ThemaKostenlos!!! Themakostenlos!!! ThemaKOSTENLOS! ThemaKostenlos! Themakostenlos! ThemaKOSTENLOS ThemaKostenlos Themakostenlos KOSTENLOS!!! Kostenlos!!! kostenlos!!! KOSTENLOS! Kostenlos! kostenlos! KOSTENLOS Kostenlos kostenlos

Wenn man das tut, sollte man auch Versionen mit Großbuchstaben am Anfang sowie in Groß- und Kleinschreibung berücksichtigen. Spam-Nachrichten haben tendenziell mehr Sätze im Imperativ, und dort hat das erste Wort eine höhere Spam-Wahrscheinlichkeit als in Kleinschreibung. In meinem Filter hat "Handeln" eine Spam-Wahrscheinlichkeit von 98% und "handeln" nur 62%.

Wenn man den Wortschatz des Filters erweitert, kann es vorkommen, dass man dasselbe Wort mehrmals zählt, gemäß der alten Definition von "gleich". Logisch gesehen sind sie nicht mehr dasselbe Token. Aber wenn das immer noch stört, lass mich aus Erfahrung hinzufügen, dass die Wörter, die man mehrmals zu zählen scheint, genau die sind, die man haben möchte.

Ein weiterer Effekt eines größeren Wortschatzes ist, dass man bei eingehenden E-Mails mehr interessante Token findet, also solche mit Wahrscheinlichkeiten weit weg von .5. Ich verwende die 15 interessantesten, um zu entscheiden, ob eine E-Mail Spam ist. Aber man kann ein Problem bekommen, wenn man eine feste Anzahl verwendet. Wenn man viele maximal interessante Token findet, kann das Ergebnis davon abhängen, welcher zufällige Faktor die Reihenfolge der gleich interessanten Token bestimmt. Eine Möglichkeit, damit umzugehen, ist, einige als interessanter als andere zu behandeln.

Zum Beispiel kommt das Token "dalco" in meinem Spam-Korpus 3 Mal vor und nie in meinem legitimen Korpus. Das Token "Url*optmails" (bedeutet "optmails" innerhalb einer URL) kommt 1223 Mal vor. Und doch hätten beide, wie ich früher Wahrscheinlichkeiten für Token berechnet habe, dieselbe Spam-Wahrscheinlichkeit von .99.

Das fühlt sich nicht richtig an. Es gibt theoretische Argumente dafür, diesen beiden Token deutlich unterschiedliche Wahrscheinlichkeiten zu geben (Pantel und Lin tun das), aber ich habe das noch nicht ausprobiert. Es scheint zumindest, dass wenn wir mehr als 15 Token finden, die nur in einem Korpus vorkommen, wir den Priorität geben sollten, die öfter vorkommen. Also gibt es jetzt zwei Schwellenwerte. Für Token, die nur im Spam-Korpus vorkommen, ist die Wahrscheinlichkeit .9999, wenn sie mehr als 10 Mal vorkommen, und .9998 sonst. Entsprechend am anderen Ende der Skala für Token, die nur im legitimen Korpus gefunden werden.

Ich werde die Token-Wahrscheinlichkeiten später möglicherweise deutlich skalieren, aber diese winzige Menge an Skalierung stellt zumindest sicher, dass die Token richtig sortiert werden.

Eine weitere Möglichkeit wäre, nicht nur 15 Token, sondern alle Token über einem bestimmten Schwellenwert der Interessantheit zu berücksichtigen. Steven Hauser macht das in seinem statistischen Spam-Filter [8]. Wenn man einen Schwellenwert verwendet, sollte man ihn sehr hoch setzen, sonst könnten Spammer Sie austricksen, indem sie Nachrichten mit mehr harmlosen Wörtern füllen.

Schließlich, was sollte man mit HTML machen? Ich habe das ganze Spektrum an Optionen ausprobiert, vom Ignorieren bis zum vollständigen Parsen. HTML zu ignorieren ist eine schlechte Idee, weil es voller nützlicher Spam-Anzeichen ist. Aber wenn man es alles parsed, könnte der Filter zu einem reinen HTML-Erkenner degenerieren. Der effektivste Ansatz scheint der Mittelweg zu sein, einige Token zu beachten, aber nicht andere. Ich schaue mir a-, img- und font-Tags an und ignoriere den Rest. Links und Bilder sollte man sicher betrachten, da sie URLs enthalten.

Ich könnte wahrscheinlich schlauer mit HTML umgehen, aber ich denke nicht, dass es sich lohnt, viel Zeit damit zu verbringen. Spam-Nachrichten voller HTML sind einfach zu filtern. Die klügeren Spammer vermeiden es schon. Daher sollte die Leistung in der Zukunft nicht stark davon abhängen, wie man mit HTML umgeht.

Leistung

Zwischen dem 10. Dezember 2002 und dem 10. Januar 2003 erhielt ich etwa 1750 Spam-Nachrichten. Davon kamen 4 durch. Das ist eine Filterrate von etwa 99,75%.

Zwei der vier Spam-Nachrichten, die ich verpasst habe, kamen durch, weil sie zufällig Wörter verwendeten, die in meiner legitimen E-Mail-Korrespondenz oft vorkommen.

Der dritte war einer jener, die ein unsicheres CGI-Skript ausnutzen, um E-Mails an Dritte zu senden. Sie sind schwer zu filtern, basierend nur auf dem Inhalt, weil die Header unschuldig sind und sie vorsichtig mit den verwendeten Wörtern umgehen. Trotzdem kann ich sie normalerweise erwischen. Dieser ist mit einer Wahrscheinlichkeit von .88 durchgerutscht, knapp unter dem Schwellenwert von .9.

Natürlich würde das leicht auffallen, wenn man Sequenzen von mehreren Token betrachtet. "Nachfolgend das Ergebnis Ihres Feedback-Formulars" ist ein sofortiger Verräter.

Der vierte Spam war das, was ich einen Spam-der-Zukunft nenne, denn das ist es, was ich erwarte, dass Spam sich entwickeln wird: ein völlig neutraler Text gefolgt von einer URL. In diesem Fall kam er von jemandem, der sagte, dass er seine Homepage endlich fertig gestellt habe und ob ich sie mir ansehen würde. (Die Seite war natürlich eine Werbung für eine Pornosite.)

Wenn die Spammer vorsichtig mit den Überschriften umgehen und eine frische URL verwenden, gibt es in Spam-der-Zukunft nichts, das Filter auffallen lassen würde. Natürlich können wir gegensteuern, indem wir einen Crawler die Seite ansehen lassen. Aber das könnte nicht notwendig sein. Die Antwortrate für Spam-der-Zukunft muss niedrig sein, sonst würden es alle machen. Wenn sie niedrig genug ist, lohnt es sich für Spammer nicht, sie zu senden, und wir müssen nicht zu hart an der Filterung arbeiten.

Jetzt zur wirklich schockierenden Nachricht: In diesem einen Monat hatte ich drei Fehlalarme.

In gewisser Weise ist es eine Erleichterung, einige Fehlalarme zu bekommen. Als ich "A Plan for Spam" schrieb, hatte ich keine gehabt, und ich wusste nicht, wie sie sein würden. Jetzt, da ich ein paar hatte, bin ich erleichtert, festzustellen, dass sie nicht so schlimm sind, wie ich befürchtet hatte. Fehlalarme, die von statistischen Filtern erzeugt werden, erweisen sich als E-Mails, die sehr nach Spam klingen, und diese sind in der Regel diejenigen, die man am wenigsten vermissen würde [9].

Zwei der Fehlalarme waren Newsletter von Unternehmen, bei denen ich etwas gekauft hatte. Ich hatte sie nicht abonniert, also könnte man sie als Spam bezeichnen, aber ich zähle sie als Fehlalarme, weil ich sie vorher nicht als Spam gelöscht hatte. Der Grund, warum die Filter sie erwischt haben, war, dass beide Unternehmen im Januar auf kommerzielle E-Mail-Versender umgestiegen sind, anstatt die E-Mails von ihren eigenen Servern aus zu senden, und sowohl die Kopfzeilen als auch die Texte viel "spammiger" wurden.

Der dritte Fehlalarm war jedoch ein schlechter. Er kam von jemandem in Ägypten und war in Großbuchstaben geschrieben. Dies war eine direkte Folge der Groß-/Kleinschreibung; der "Plan for Spam"-Filter hätte ihn nicht erwischt.

Es ist schwer zu sagen, was die allgemeine Fehlalarmquote ist, da wir statistisch gesehen im Rauschen sind. Jeder, der an Filtern gearbeitet hat (zumindest an effektiven Filtern), kennt dieses Problem. Bei manchen E-Mails ist es schwer zu sagen, ob es sich um Spam handelt oder nicht, und das sind die, auf die man schaut, wenn man die Filter wirklich eng einstellt. Zum Beispiel hat der Filter bisher zwei E-Mails erwischt, die aufgrund eines Tippfehlers an meine Adresse gesendet wurden, und eine, die in dem Glauben an mich gesendet wurde, dass ich jemand anderes sei. Streng genommen sind das weder mein Spam noch meine Nicht-Spam-Post.

Ein weiterer Fehlalarm kam von einem Vizepräsidenten von Virtumundo. Ich schrieb ihnen als vermeintlicher Kunde, und da die Antwort über die Mailserver von Virtumundo kam, hatte sie die verdächtigsten Kopfzeilen überhaupt. Streng genommen ist das auch kein echter Fehlalarm, sondern eine Art Heisenberg'sche Unschärferelation: Ich habe ihn nur bekommen, weil ich über Spam-Filterung schrieb.

Ohne diese Fälle hatte ich insgesamt fünf Fehlalarme, von etwa 7740 legitimen E-Mails, also eine Rate von 0,06 %. Die anderen beiden waren eine Benachrichtigung, dass etwas, das ich gekauft hatte, nachbestellt wurde, und eine Partyerinnerung von Evite.

Ich denke nicht, dass diese Zahl verlässlich ist, zum einen wegen der geringen Stichprobengröße und zum anderen, weil ich glaube, dass ich den Filter so anpassen kann, dass er einige dieser Fälle nicht mehr erwischt.

Fehlalarme scheinen mir eine andere Art von Fehler zu sein als Fehleinschätzungen. Die Filterrate ist ein Leistungsmaß. Fehlalarme betrachte ich eher als Bugs. Ich gehe die Verbesserung der Filterrate als Optimierung an und die Verringerung der Fehlalarme als Fehlerbeseitigung.

Diese fünf Fehlalarme sind also meine Fehlerliste. Zum Beispiel wurde die E-Mail aus Ägypten erwischt, weil der Großbuchstabentext sie für den Filter wie einen nigerianischen Spam aussehen ließ. Das ist wirklich eine Art Bug. Wie bei HTML ist der Umstand, dass die E-Mail komplett in Großbuchstaben geschrieben ist, eigentlich nur ein einziges Merkmal, nicht eines für jedes Wort. Ich muss den Umgang mit Groß-/Kleinschreibung sophistizierter gestalten.

Was also ist mit dieser 0,06 % zu machen? Nicht viel, denke ich. Man könnte sie als Obergrenze behandeln, wobei die kleine Stichprobengröße zu berücksichtigen ist. Aber in diesem Stadium ist sie eher ein Maß für die Bugs in meiner Implementierung als für eine inhärente Fehlalarmquote der Bayes'schen Filterung.

Zukunft

Was kommt als Nächstes? Filterung ist ein Optimierungsproblem, und der Schlüssel zur Optimierung ist das Profiling. Versuchen Sie nicht, zu raten, wo Ihr Code langsam ist, denn Sie werden falsch liegen. Schauen Sie sich an, wo Ihr Code langsam ist, und beheben Sie das. In der Filterung übersetzt sich das zu: Schauen Sie sich die Spams an, die Sie verpassen, und finden Sie heraus, was Sie hätten tun können, um sie zu erwischen.

Zum Beispiel arbeiten die Spammer jetzt aggressiv daran, Filter zu umgehen, und eine der Dinge, die sie tun, ist, Wörter aufzubrechen und falsch zu schreiben, um zu verhindern, dass Filter sie erkennen. Aber daran zu arbeiten, ist nicht meine oberste Priorität, denn ich habe immer noch keine Schwierigkeiten, diese Spams zu erwischen [10].

Es gibt zwei Arten von Spams, mit denen ich derzeit Schwierigkeiten habe. Eine ist die Art, die vorgibt, eine E-Mail von einer Frau zu sein, die Sie einlädt, mit ihr zu chatten oder ihr Profil auf einer Dating-Site anzusehen. Diese kommen durch, weil es der einzige Verkaufsversuch ist, den man machen kann, ohne Verkaufssprache zu verwenden. Sie verwenden den gleichen Wortschatz wie normale E-Mails.

Die andere Art von Spams, die ich nur schwer filtern kann, sind die von Unternehmen in z.B. Bulgarien, die Vertragsprogrammierleistungen anbieten. Diese kommen durch, weil ich selbst Programmierer bin und die Spams voller der gleichen Wörter sind wie meine echte Post.

Ich werde mich wahrscheinlich zuerst auf den Typ der Kontaktanzeigen konzentrieren. Ich denke, wenn ich genauer hinschaue, werde ich statistische Unterschiede zwischen diesen und meiner echten Post finden können. Der Schreibstil ist sicher anders, auch wenn es möglicherweise eine Mehrwort-Filterung braucht, um das zu erfassen. Außerdem fällt mir auf, dass sie dazu neigen, die URL zu wiederholen, was jemand, der eine legitime Mail sendet, nicht tun würde [11].

Die Outsourcing-Typen werden schwer zu fangen sein. Selbst wenn man einen Crawler zur Website schicken würde, fände man keine statistisch belastbare "rauchende Waffe". Vielleicht ist die einzige Antwort eine zentrale Liste der in Spams beworbenen Domains [12]. Aber es kann nicht so viele dieser Art von Mail geben. Wenn die einzigen Spams, die übrig blieben, unaufgeforderte Angebote für Vertragsprogrammierleistungen aus Bulgarien wären, könnten wir uns wahrscheinlich alle anderen Dingen widmen.

Wird die statistische Filterung uns tatsächlich an diesen Punkt bringen? Ich weiß es nicht. Für mich persönlich ist Spam im Moment kein Problem. Aber die Spammer haben noch keinen ernsthaften Versuch unternommen, statistische Filter zu täuschen. Was wird passieren, wenn sie es tun?

Ich bin nicht optimistisch in Bezug auf Filter, die auf Netzwerkebene funktionieren [[13]]. Wenn es ein statisches Hindernis gibt, das es zu überwinden gilt, sind Spammer ziemlich effizient darin, es zu umgehen. Es gibt bereits ein Unternehmen namens Assurance Systems, das Ihre E-Mail durch Spamassassin laufen lässt und Ihnen mitteilt, ob sie herausgefiltert wird.

Netzwerk-basierte Filter werden nicht völlig nutzlos sein. Sie könnten ausreichen, um die gesamte "Opt-in"-Spam zu töten, d.h. Spam von Unternehmen wie Virtumundo und Equalamail, die behaupten, dass sie wirklich Opt-in-Listen betreiben. Sie können diese allein anhand der Kopfzeilen filtern, unabhängig davon, was im Textkörper steht. Aber jeder, der bereit ist, Kopfzeilen zu fälschen oder offene Weiterleitungen zu verwenden, darunter vermutlich die meisten Porno-Spammer, sollte in der Lage sein, einige Nachrichten an Netzwerk-basierten Filtern vorbeizubringen. (Allerdings nicht die Nachricht, die sie gerne senden würden, was immerhin etwas ist.)

Die Art von Filtern, auf die ich optimistisch bin, sind solche, die Wahrscheinlichkeiten basierend auf der individuellen E-Mail-Kommunikation jedes einzelnen Nutzers berechnen. Diese können viel effektiver sein, nicht nur bei der Vermeidung von Fehlalarmen, sondern auch beim Filtern: Zum Beispiel ist das Auffinden der E-Mail-Adresse des Empfängers, base-64 codiert, an irgendeiner Stelle in einer Nachricht ein sehr guter Spam-Indikator.

Aber der eigentliche Vorteil individueller Filter ist, dass sie alle unterschiedlich sein werden. Wenn die Filter aller Nutzer unterschiedliche Wahrscheinlichkeiten haben, wird das den Optimierungskreislauf der Spammer, was Programmierer als "Edit-Compile-Test-Zyklus" bezeichnen würden, entsetzlich langsam machen. Anstatt einfach nur einen Spam-Eintrag so lange zu verändern, bis er durch eine Kopie des Filters auf ihrem Desktop kommt, müssen sie für jede Änderung einen Testversand durchführen. Es wäre, als würden sie in einer Sprache ohne interaktive Oberfläche programmieren, und das möchte ich niemandem zumuten.

Anmerkungen

[1] Paul Graham. ``A Plan for Spam.'' August 2002. http://paulgraham.com/spam.html.

Die Wahrscheinlichkeiten in diesem Algorithmus werden unter Verwendung eines entarteten Falls der Bayes'schen Regel berechnet. Es gibt zwei vereinfachende Annahmen: dass die Wahrscheinlichkeiten der Merkmale (d.h. Wörter) unabhängig sind und dass wir nichts über die Vorwahrscheinlichkeit einer E-Mail als Spam wissen.

Die erste Annahme ist in der Textklassifizierung weit verbreitet. Algorithmen, die sie verwenden, werden als "naive Bayes" bezeichnet.

Die zweite Annahme habe ich getroffen, weil das Verhältnis von Spam zu Nicht-Spam in meinem eingehenden E-Mail-Verkehr von Tag zu Tag (ja, sogar von Stunde zu Stunde) so stark schwankte, dass das allgemeine Vorwahrscheinlichkeitsverhältnis als Prädiktor unbrauchbar erschien. Wenn man annimmt, dass P(Spam) und P(Nicht-Spam) beide 0,5 betragen, heben sie sich auf und können aus der Formel entfernt werden.

Wenn man Bayessche Filterung in einer Situation durchführt, in der das Verhältnis von Spam zu Nicht-Spam durchgängig sehr hoch oder (insbesondere) sehr niedrig ist, könnte man die Filterleistung wahrscheinlich durch Einbeziehung der Vorwahrscheinlichkeiten verbessern. Um dies richtig zu machen, müsste man die Verhältnisse nach Tageszeit verfolgen, da sowohl das Spam- als auch das legitime E-Mail-Aufkommen deutliche Tagesgänge aufweisen.

[2] Patrick Pantel und Dekang Lin. ``SpamCop-- A Spam Classification & Organization Program.'' Proceedings of AAAI-98 Workshop on Learning for Text Categorization.

[3] Mehran Sahami, Susan Dumais, David Heckerman und Eric Horvitz. ``A Bayesian Approach to Filtering Junk E-Mail.'' Proceedings of AAAI-98 Workshop on Learning for Text Categorization.

[4] Zum Zeitpunkt, als ich dies schrieb, hatte ich null Fehlalarme bei etwa 4.000 legitimen E-Mails. Wenn die nächste legitime E-Mail ein Fehlalarm wäre, würde das 0,03% ergeben. Diese Fehlalarmraten sind unzuverlässig, wie ich später erläutere. Ich nenne hier eine Zahl nur, um zu betonen, dass die Fehlalarmrate, was auch immer sie ist, unter 1,16% liegt.

[5] Bill Yerazunis. ``Sparse Binary Polynomial Hash Message Filtering and The CRM114 Discriminator.'' Proceedings of 2003 Spam Conference.

[6] In "A Plan for Spam" verwendete ich Schwellenwerte von 0,99 und 0,01. Es scheint gerechtfertigt, Schwellenwerte proportional zur Größe der Korpora zu verwenden. Da ich jetzt in der Größenordnung von 10.000 von jeder Art von E-Mail habe, verwende ich 0,9999 und 0,0001.

[7] Hier gibt es einen Fehler, den ich wahrscheinlich beheben sollte. Derzeit bedeutet, wenn "Subjectfoo" zu einfach nur "foo" entartet, dass Sie die Statistiken für das Vorkommen von "foo" im Textkörper oder in anderen Kopfzeilen als den von mir gekennzeichneten erhalten. Was ich stattdessen tun sollte, ist, die Statistiken für "foo" insgesamt sowie für spezifische Versionen zu verfolgen und von "Subjectfoo" nicht auf "foo", sondern auf "Anywhere*foo" zu entarten. Gleiches gilt für Groß-/Kleinschreibung: Ich sollte von Großschreibung auf Beliebige Schreibung, nicht auf Kleinschreibung entarten.

Es wäre wahrscheinlich ein Gewinn, dies auch mit Preisen zu tun, z.B. um von "$129,99" auf "$--9,99", "$--.99" und "$--" zu entarten.

Man könnte auch von Wörtern auf ihre Wortstämme entarten, aber das würde die Filterraten wahrscheinlich nur in der Anfangsphase verbessern, wenn man kleine Korpora hat.

[8] Steven Hauser. "Statistical Spam Filter Works for Me." http://www.sofbot.com.

[9] Fehlalarme sind nicht alle gleich, und wir sollten dies berücksichtigen, wenn wir Techniken zum Stoppen von Spam vergleichen. Während viele der Fehlalarme, die durch Filter verursacht werden, Beinahe-Spam sind, den man nicht vermissen würde, werden Fehlalarme, die durch Sperrlisten verursacht werden, einfach nur E-Mails von Leuten sein, die den falschen ISP gewählt haben. In beiden Fällen fangen Sie E-Mails ab, die Beinahe-Spam sind, aber bei Sperrlisten ist die Nähe physisch und bei Filtern textuell.

[10] Wenn Spammer gut genug darin werden, Token zu verschleiern, um dies zu einem Problem zu machen, können wir einfach Leerzeichen, Punkte, Kommas usw. entfernen und ein Wörterbuch verwenden, um die Wörter aus der resultierenden Sequenz herauszuholen. Und natürlich wäre das Auffinden von Wörtern auf diese Weise, die im ursprünglichen Text nicht sichtbar waren, an sich schon ein Indiz für Spam.

Das Herausfiltern der Wörter wird nicht trivial sein. Es erfordert mehr als nur das Wiederherstellen von Wortgrenzen; Spammer fügen sowohl Buchstaben hinzu ("xHot nPorn cSite") als auch lassen welche weg ("P#rn"). Forschung zur menschlichen Wahrnehmung könnte hier hilfreich sein, da die menschliche Sicht die Grenze dessen ist, was solche Tricks erreichen werden.

[11] Im Allgemeinen sind Spam-Nachrichten repetitiver als reguläre E-Mails. Sie wollen diese Botschaft nachdrücklich vermitteln. Derzeit erlaube ich keine Duplikate in den 15 wichtigsten Tokens, da es einen Fehlalarm geben könnte, wenn der Absender zufällig ein bestimmtes Wort mehrmals verwendet. (In meinem aktuellen Filter hat "dick" eine Spam-Wahrscheinlichkeit von 0,9999, aber es ist auch ein Name.) Es scheint, wir sollten zumindest Duplizierung bemerken, also werde ich versuchen, bis zu zwei von jedem Token zuzulassen, wie Brian Burton es in SpamProbe tut.

[12] Dies ist, was Ansätze wie der von Brightmail in Zukunft werden, wenn Spammer dazu gezwungen werden, Mad-Lib-Techniken zu verwenden, um den Rest der Nachricht zu generieren.

[13] Manchmal wird argumentiert, dass wir an der Filterung auf Netzwerkebene arbeiten sollten, da sie effizienter ist. Was die Leute damit normalerweise meinen, ist: Wir filtern derzeit auf Netzwerkebene und wollen nicht von vorne anfangen. Aber man kann das Problem nicht so definieren, dass es zur Lösung passt.

Historisch gesehen waren Argumente über knappe Ressourcen die Verliererseite in Debatten über Softwaredesign. Leute verwenden sie nur, um Entscheidungen (insbesondere Untätigkeit) zu rechtfertigen, die aus anderen Gründen getroffen wurden.

Danke an Sarah Harlin, Trevor Blackwell und Dan Giffin für das Lesen von Entwürfen dieses Papiers und an Dan erneut für den Großteil der Infrastruktur, auf der dieser Filter läuft.

Verwandt:

SubjectFREE 0.9999 free!! 0.9999 Tofree 0.9998 Subjectfree 0.9782 free! 0.9199 Free 0.9198 Urlfree 0.9091 FREE 0.8747 From*free 0.7636 free 0.6546

SubjectFree!!! Subjectfree!!! SubjectFREE! SubjectFree! Subjectfree! SubjectFREE SubjectFree Subjectfree FREE!!! Free!!! free!!! FREE! Free! free! FREE Free free