BESSERE BAYES'SCHE FILTERUNG

January 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 vorhabe.)

Die erste Entdeckung, die ich hier vorstellen möchte, ist ein Algorithmus für die träge Auswertung von Forschungsarbeiten. Schreiben Sie einfach was Sie wollen und zitieren Sie keine vorherige Arbeit, und empörte Leser werden Ihnen Referenzen zu all den Arbeiten schicken, die Sie hätten zitieren sollen. Ich entdeckte diesen Algorithmus nachdem ``A Plan for Spam'' [1] auf Slashdot war.

Spam-Filterung ist eine Teilmenge der Textklassifizierung, die ein etabliertes Feld ist, aber die ersten Arbeiten über Bayes'sche Spam-Filterung scheinen zwei auf der gleichen Konferenz im Jahr 1998 gewesen zu sein, eine von Pantel und Lin [2], und eine weitere von einer Gruppe von Microsoft Research [3].

Als ich von dieser Arbeit hörte, war ich etwas überrascht. Wenn die Leute vor vier Jahren auf Bayes'sche Filterung gestoßen wären, warum benutzte dann nicht jeder sie? Als ich die Arbeiten las, fand ich heraus, warum. Pantels und Lins Filter war der effektivere der beiden, aber er fing nur 92% des Spams ab, mit 1,16% falsch-positiven Ergebnissen.

Als ich versuchte, einen Bayes'schen Spam-Filter zu schreiben, fing er 99,5% des Spams ab mit weniger als 0,03% falsch-positiven Ergebnissen [4]. Es ist immer alarmierend, wenn zwei Personen das gleiche Experiment durchführen und stark abweichende Ergebnisse erhalten. Besonders alarmierend ist es hier, weil diese beiden Zahlenreihen zu gegensätzlichen Schlussfolgerungen führen könnten. Verschiedene Benutzer haben unterschiedliche Anforderungen, aber ich denke für viele Menschen bedeutet eine Filterrate von 92% mit 1,16% falsch-positiven Ergebnissen dass Filtern keine akzeptable Lösung ist, während 99,5% mit weniger als 0,03% falsch-positiven Ergebnissen bedeutet, dass es das ist.

Warum haben wir also so unterschiedliche Zahlen erhalten? Ich habe nicht versucht, die Ergebnisse von Pantel und Lin zu reproduzieren, aber aus dem Lesen des Artikels sehe ich fünf Dinge, die wahrscheinlich für den Unterschied verantwortlich sind.

Eines ist einfach, dass sie ihren Filter mit sehr wenigen Daten trainiert haben: 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 ein genaues Mass für die Leistung ihres Algorithmus, geschweige denn für Bayes'sche Spam-Filterung im Allgemeinen.

Aber ich denke, der wichtigste Unterschied ist wahrscheinlich, dass sie Nachrichtenköpfe ignoriert haben. Für jeden, der an Spam-Filtern gearbeitet hat, wird dies eine perverse Entscheidung erscheinen. Und doch habe ich in den allerersten 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 schienen mir voll von zufälligem Zeug zu sein. Hier gibt es eine Lektion für Filter- Autoren: Ignorieren Sie keine Daten. Man könnte meinen, diese Lektion wäre zu offensichtlich, um sie zu erwähnen, aber ich musste sie mehrmals lernen.

Drittens haben Pantel und Lin die Token gestutzt, d.h. sie haben z.B. sowohl mailing'' als auch mailed'' auf die Wurzel ``mail'' reduziert. Sie mögen sich gezwungen gefühlt haben, dies aufgrund der geringen Grösse ihres Korpus zu tun, aber wenn ja, ist dies eine Art von vorzeitiger Optimierung.

Viertens haben sie Wahrscheinlichkeiten anders berechnet. Sie haben alle Token verwendet, während ich nur die 15 wichtigsten verwende. Wenn Sie alle Token verwenden, werden Sie dazu neigen, längere Spams zu verpassen, die Art, bei der Ihnen jemand seine Lebensgeschichte bis zu dem Punkt erzählt, an dem er durch ein Multilevel- Marketing-Schema reich geworden ist. Und ein solcher Algorithmus wäre für Spammer leicht zu fälschen: Fügen Sie einfach einen grossen Klumpen von zufälligem Text hinzu, um die Spam-Begriffe auszugleichen.

Schliesslich haben sie keine Verzerrung gegen falsch-positive Ergebnisse vorgenommen. Ich denke, jeder Spam-Filter-Algorithmus sollte einen praktischen Knopf haben, den man drehen kann, um die falsch-positive Rate auf Kosten der Filterrate zu verringern. Ich tue dies, indem ich die Vorkommen von Token im Nicht-Spam-Korpus doppelt zähle.

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

Token

Ein weiteres Projekt, von dem ich hörte nach dem Slashdot-Artikel, war Bill Yerazunis' CRM114 [5]. Dies ist das Gegenbeispiel zu dem Designprinzip, das ich gerade erwähnt habe. Es ist ein reiner Textklassifikator, aber ein so erstaunlich effektiver, dass er es schafft, Spam fast perfekt zu filtern, ohne überhaupt zu wissen, dass es das tut.

Als ich verstand, wie CRM114 funktionierte, schien es unvermeidlich, dass ich irgendwann von der Filterung auf der Basis einzelner Wörter zu einem Ansatz wie diesem übergehen müsste. Aber zuerst dachte ich, ich werde sehen, wie weit ich mit einzelnen Wörtern kommen kann. Und die Antwort ist, überraschend weit.

Meistens habe ich an einer intelligenteren Tokenisierung gearbeitet. Auf aktuellem Spam konnte ich Filterraten erreichen, die sich CRM114 nähern. Diese Techniken sind meist orthogonal zu Bills; eine optimale Lösung könnte beides beinhalten.

``A Plan for Spam'' verwendet eine sehr einfache Definition eines Tokens. Buchstaben, Ziffern, Bindestriche, Apostrophe, und Dollarzeichen sind konstituierende Zeichen, und alles andere ist ein Token-Trennzeichen. Ich habe auch die Gross- und Kleinschreibung ignoriert.

Jetzt habe ich eine kompliziertere Definition eines Tokens:

Die Gross- und Kleinschreibung wird beibehalten.

Ausrufezeichen sind konstituierende Zeichen.

Punkte und Kommas sind Bestandteile, wenn sie zwischen zwei Ziffern vorkommen. So kann ich IP-Adressen und Preise intakt erhalten.

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 vorkommen, werden entsprechend gekennzeichnet. Z.B. foo'' in der Subject-Zeile wird zu Subject*foo''. (Das Sternchen könnte beliebiges Zeichen sein, das Sie nicht als Bestandteil zulassen.)

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

Hier sind einige der aktuellen Wahrscheinlichkeiten [6]:

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

Im Plan for Spam-Filter hätten all diese Token die gleiche Wahrscheinlichkeit, 0,7602. Dieser Filter erkannte etwa 23.000 Token. Der aktuelle erkennt etwa 187.000.

Der Nachteil eines grösseren Universums von Token ist, dass es mehr Möglichkeiten für Fehler gibt. Die Verteilung Ihres Korpus auf mehr Token hat den gleichen Effekt wie eine Verkleinerung. Wenn Sie Ausrufezeichen als Bestandteile betrachten, könnten Sie zum Beispiel keine Spam-Wahrscheinlichkeit für free mit sieben Ausrufezeichen haben, obwohl Sie wissen, dass free mit nur zwei Ausrufezeichen eine Wahrscheinlichkeit von 99,99% hat.

Eine Lösung dafür ist das, was ich Degeneration nenne. Wenn Sie keine exakte Übereinstimmung für ein Token finden, behandeln Sie es so, als wäre es eine weniger spezifische Version. Ich betrachte terminale Ausrufezeichen, Grossbuchstaben und das Vorkommen in einem der fünf markierten Kontexte als eine Verfeinerung eines Tokens. Wenn ich zum Beispiel keine Wahrscheinlichkeit für Subject*free!'' finde, suche ich nach Wahrscheinlichkeiten für Subject*free'', free!'' und free'' und nehme diejenige, die am weitesten von 0,5 entfernt ist.

Hier sind die Alternativen [7], die in Betracht gezogen werden, wenn der Filter ``FREE!!!'' in der Subject-Zeile sieht und keine Wahrscheinlichkeit dafür hat.

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

Wenn Sie dies tun, sollten Sie unbedingt Versionen mit anfänglichen Grossbuchstaben sowie alle Grossbuchstaben und alle Kleinbuchstaben berücksichtigen. Spams haben tendenziell mehr Sätze im Imperativ, und in diesen ist das erste Wort ein Verb. Daher haben Verben mit anfänglichen Grossbuchstaben höhere Spam-Wahrscheinlichkeiten als sie in allen Kleinbuchstaben hätten. In meinem Filter beträgt die Spam-Wahrscheinlichkeit von Act'' 98% und für act'' nur 62%.

Wenn Sie den Wortschatz Ihres Filters erweitern, können Sie am Ende das gleiche Wort mehrmals zählen, gemäss Ihrer alten Definition von ``gleich''. Logischerweise sind sie nicht mehr das gleiche Token. Aber wenn Sie das immer noch stört, lassen Sie mich aus Erfahrung hinzufügen, dass die Wörter, die Sie scheinbar mehrmals zählen, genau die sind, die Sie haben wollen.

Ein weiterer Effekt eines grösseren Wortschatzes ist, dass, wenn Sie sich eine eingehende Mail ansehen, Sie mehr interessante Token finden, d.h. solche mit Wahrscheinlichkeiten, die weit von 0,5 entfernt sind. Ich verwende die 15 interessantesten, um zu entscheiden, ob eine Mail Spam ist. Aber Sie können auf ein Problem stossen, wenn Sie eine feste Zahl wie diese verwenden. Wenn Sie viele maximal interessante Token finden, kann das Ergebnis am Ende von dem zufälligen Faktor abhängen, der die Reihenfolge gleich interessanter Token bestimmt. Eine Möglichkeit, damit umzugehen, ist, einige als interessanter als andere zu behandeln.

Zum Beispiel kommt das Token dalco'' 3 Mal in meinem Spam-Korpus vor und nie in meinem legitimen Korpus. Das Token Url*optmails'' (d.h. ``optmails'' innerhalb einer URL) kommt 1223 Mal vor. Und doch hätten beide, wie ich früher Wahrscheinlichkeiten für Token berechnete, die gleiche Spam-Wahrscheinlichkeit, den Schwellenwert von 0,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 dies), aber ich habe das noch nicht ausprobiert. Es scheint zumindest so, dass, wenn wir mehr als 15 Token finden, die nur in dem einen oder anderen Korpus vorkommen, wir denjenigen Priorität einräumen sollten, die häufig vorkommen. Daher gibt es jetzt zwei Schwellenwerte. Für Token, die nur im Spam-Korpus vorkommen, beträgt die Wahrscheinlichkeit 0,9999, wenn sie mehr als 10 Mal vorkommen, und 0,9998 andernfalls. Das Gleiche gilt am anderen Ende der Skala für Token, die nur im legitimen Korpus gefunden werden.

Ich werde die Token-Wahrscheinlichkeiten später möglicherweise erheblich skalieren, aber diese winzige Skalierung stellt zumindest sicher, dass die Token in der richtigen Reihenfolge sortiert werden.

Eine weitere Möglichkeit wäre, nicht nur 15 Token zu betrachten, sondern alle Token über einem bestimmten Schwellenwert der Interessantheit. Steven Hauser tut dies in seinem statistischen Spam-Filter [8]. Wenn Sie einen Schwellenwert verwenden, machen Sie ihn sehr hoch, oder Spammer könnten Sie täuschen, indem sie Nachrichten mit mehr harmlosen Wörtern füllen.

Schliesslich, was sollte man mit HTML tun? Ich habe das gesamte Spektrum an Optionen ausprobiert, von der Ignorierung bis hin zum vollständigen Parsen. HTML zu ignorieren ist eine schlechte Idee, weil es voller nützlicher Spam-Signale ist. Aber wenn Sie es vollständig parsen, könnte Ihr Filter zu einem blossen HTML- Erkenner degenerieren. Der effektivste Ansatz scheint der Mittelweg zu sein, einige Token zu bemerken, aber nicht andere. Ich schaue mir a-, img- und font-Tags an und ignoriere den Rest. Links und Bilder sollten Sie sich auf jeden Fall ansehen, weil sie URLs enthalten.

Ich könnte wahrscheinlich intelligenter mit HTML umgehen, aber ich denke nicht, dass es sich lohnt, viel Zeit in dieses Thema zu investieren. Spams voller HTML sind leicht zu filtern. Die intelligenteren Spammer vermeiden es bereits. Daher sollte die Leistung in Zukunft nicht mehr stark davon abhängen, wie Sie mit HTML umgehen.

Leistung

Zwischen dem 10. Dezember 2002 und dem 10. Januar 2003 habe ich etwa 1750 Spams erhalten. Davon sind 4 durchgekommen. Das ist eine Filterrate von etwa 99,75%.

Zwei der vier Spams, die ich verpasst habe, sind durchgekommen, weil sie zufällig Wörter verwendet haben, die in meiner legitimen E-Mail häufig vorkommen.

Der dritte war einer von denen, 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 Kopfzeilen unschuldig sind und sie sorgfältig auf die Wörter achten, die sie verwenden. Trotzdem kann ich sie normalerweise erwischen. Dieser hier ist mit einer Wahrscheinlichkeit von 0,88 knapp unter dem Schwellenwert von 0,9 durchgeschlüpft.

Natürlich würde das Betrachten mehrerer Token-Sequenzen ihn leicht erwischen. ``Below is the result of your feedback form'' ist ein sofortiges Indiz.

Der vierte Spam war das, was ich einen Spam-der-Zukunft nenne, weil ich erwarte, dass Spam sich zu diesem entwickeln wird: etwas völlig neutrales Text gefolgt von einer URL. In diesem Fall war es von jemandem, der sagte, er habe seine Homepage endlich fertiggestellt und ob ich sie mir ansehen wolle. (Die Seite war natürlich eine Werbung für eine Pornoseite.)

Wenn die Spammer auf die Kopfzeilen achten und eine frische URL verwenden, gibt es im Spam-der-Zukunft nichts für Filter zu bemerken. Wir können natürlich dagegenhalten, indem wir einen Crawler schicken, um uns die Seite anzusehen. Aber das könnte nicht notwendig sein. Die Antwortquote für Spam-der-Zukunft muss niedrig sein, sonst würde jeder das tun. Wenn sie niedrig genug ist, wird es sich nicht lohnen für Spammer, ihn zu versenden, und wir müssen uns nicht zu sehr mit der Filterung befassen.

Nun zu den wirklich schockierenden Neuigkeiten: In der gleichen einmonatigen Periode habe ich drei falsch-positive Ergebnisse erhalten.

In gewisser Weise ist es eine Erleichterung, einige falsch-positive Ergebnisse zu erhalten. Als ich ``A Plan for Spam'' schrieb, hatte ich keine, und ich wusste nicht, wie sie sein würden. Jetzt, wo ich ein paar hatte, bin ich erleichtert, dass sie nicht so schlimm sind, wie ich befürchtet hatte. Falsch-positive Ergebnisse, die von statistischen Filtern erzeugt werden, erweisen sich als Mails, die sehr nach Spam klingen, und diese sind tendenziell diejenigen, die Sie am wenigsten vermissen würden [9].

Zwei der falsch-positiven Ergebnisse waren Newsletter von Unternehmen, bei denen ich Dinge gekauft habe. Ich habe nie darum gebeten, sie zu erhalten, daher waren sie wohl Spam, aber ich zähle sie als falsch-positive Ergebnisse, weil ich sie vorher nicht als Spam gelöscht hatte. Der Grund war, dass beide Unternehmen im Januar zu kommerziellen E-Mail-Versendern wechselten anstatt die Mails von ihren eigenen Servern zu senden, und sowohl die Kopfzeilen als auch die Textkörper wurden viel spammiger.

Der dritte falsch-positive war jedoch ein schlechter. Er war von jemandem in Ägypten und in allen Grossbuchstaben geschrieben. Dies war ein direktes Ergebnis der gross- und kleinschreibungsempfindlichen Token; der Plan for Spam-Filter hätte ihn nicht erwischt.

Es ist schwer zu sagen, wie hoch die Gesamtzahl der falsch-positiven Ergebnisse ist, weil wir statistisch gesehen im Rauschen sind. Jeder, der an Filtern gearbeitet hat (zumindest an effektiven Filtern), wird dieses Problem kennen. Bei einigen E-Mails ist es schwer zu sagen, ob sie Spam sind oder nicht, und diese sind die, die Sie sich ansehen, wenn Sie Filter wirklich eng einstellen. Zum Beispiel hat der Filter bisher zwei E-Mails erwischt, die an meine Adresse geschickt wurden, weil ein Tippfehler vorlag, und eine, die an mich geschickt wurde, weil man glaubte, ich sei jemand anderes. Man könnte argumentieren, dass dies weder mein Spam noch meine Nicht-Spam-Mail ist.

Ein weiterer falsch-positiver war von einem Vizepräsidenten von Virtumundo. Ich schrieb ihnen, als wäre ich ein Kunde, und da die Antwort über Virtumundos Mail-Server zurückkam, hatte sie die incriminierendsten Kopfzeilen, die man sich vorstellen kann. Man könnte argumentieren, dass dies auch kein echter falsch-positiver ist, sondern eine Art von Heisenberg'scher Unschärferelation: Ich habe ihn nur bekommen, weil ich über Spam- Filterung schrieb.

Ohne diese zu zählen, hatte ich bisher insgesamt fünf falsch-positive Ergebnisse aus etwa 7740 legitimen E-Mails, eine Rate von 0,06%. Die anderen beiden waren eine Mitteilung, dass etwas, das ich gekauft hatte, nachbestellt wurde, und eine Party-Erinnerung von Evite.

Ich glaube nicht, dass diese Zahl vertrauenswürdig ist, zum Teil weil die Stichprobe so klein ist, und zum Teil, weil ich glaube, dass ich den Filter so reparieren kann, dass er einige dieser Fälle nicht mehr erwischt.

Falsch-positive Ergebnisse scheinen mir eine andere Art von Fehler zu sein als falsch-negative Ergebnisse. Die Filterrate ist ein Mass für die Leistung. Falsch- positive Ergebnisse betrachte ich eher als Fehler. Ich gehe die Verbesserung der Filterrate als Optimierung an und die Verringerung der falsch- positiven Ergebnisse als Debugging.

Diese fünf falsch-positiven Ergebnisse sind also meine Fehlerliste. Zum Beispiel wurde die Mail aus Ägypten erwischt, weil der Text in Grossbuchstaben dem Filter wie ein nigerianischer Spam vorkam. Das ist wirklich eine Art von Fehler. Wie bei HTML ist die E-Mail in Grossbuchstaben wirklich konzeptionell ein Merkmal, nicht eines für jedes Wort. Ich muss die Gross- und Kleinschreibung auf eine ausgefeiltere Weise behandeln.

Was soll man also aus diesen 0,06% machen? Nicht viel, denke ich. Man könnte sie als obere Grenze betrachten, wobei man die geringe Stichprobengrösse im Auge behält. Aber in diesem Stadium ist es eher ein Mass für die Fehler in meiner Implementierung als für eine intrinsische falsch-positive Rate der Bayes'schen Filterung.

Zukunft

Was kommt als Nächstes? Filtern ist ein Optimierungsproblem, und der Schlüssel zur Optimierung ist das Profiling. Versuchen Sie nicht, zu erraten, wo Ihr Code langsam ist, weil Sie falsch raten werden. Sehen Sie sich an, wo Ihr Code langsam ist, und beheben Sie das. Im Bereich der Filterung bedeutet dies: Sehen 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 Spammer jetzt aggressiv daran, Filter zu umgehen, und eines der Dinge, die sie tun, ist, Wörter aufzuteilen und falsch zu buchstabieren, um zu verhindern, dass Filter sie erkennen. Aber daran zu arbeiten ist nicht meine oberste Priorität, weil ich immer noch keine Probleme habe, diese Spams zu erwischen [10].

Es gibt zwei Arten von Spams, mit denen ich derzeit Probleme habe. Die 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- Seite zu sehen. Diese kommen durch, weil sie die einzige Art von Werbebotschaft sind, die man machen kann, ohne Werbesprache zu verwenden. Sie verwenden den gleichen Wortschatz wie normale E-Mails.

Die andere Art von Spams, die ich schwer filtern kann, sind diejenigen von Unternehmen in z.B. Bulgarien, die Vertrags-Programmierungs- Dienstleistungen anbieten. Diese kommen durch, weil ich auch Programmierer bin, und die Spams sind voll von den gleichen Wörtern wie meine echten Mails.

Ich werde mich wahrscheinlich zuerst auf die Art der persönlichen Anzeigen konzentrieren. Ich denke, wenn ich genauer hinschaue, werde ich in der Lage sein, statistische Unterschiede zwischen diesen und meinen echten Mails zu finden. Der Schreibstil ist sicherlich anders, obwohl es möglicherweise eine mehrwörtige Filterung braucht, um das zu erwischen. Ausserdem stelle ich fest, dass sie dazu neigen, die URL zu wiederholen, und jemand, der eine URL in eine legitime Mail einfügt, würde das nicht tun [11].

Die Art der Auslagerung wird schwer zu erwischen sein. Selbst wenn Sie einen Crawler auf die Seite schicken würden, würden Sie keine rauchende statistische Waffe finden. Vielleicht ist die einzige Antwort eine zentrale Liste von Domains, die in Spams beworben werden [12]. Aber es kann nicht so viele von dieser Art von Mail geben. Wenn die einzigen Spams, die übrig blieben, unaufgeforderte Angebote für Vertrags-Programmierungs- Dienstleistungen aus Bulgarien wären, könnten wir alle wahrscheinlich zu etwas anderem übergehen.

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

Ich bin nicht optimistisch, was Filter betrifft, die auf Netzwerkebene funktionieren [13]. Wenn es ein statisches Hindernis gibt, das es wert ist, überwunden zu werden, sind Spammer ziemlich effizient darin, es zu überwinden. Es gibt bereits ein Unternehmen namens Assurance Systems, das Ihre Mail durch Spamassassin laufen lässt und Ihnen sagt, ob sie herausgefiltert wird.

Filter auf Netzwerkebene werden nicht völlig nutzlos sein. Sie könnten ausreichen, um den gesamten "Opt-in"- Spam zu vernichten, d.h. Spam von Unternehmen wie Virtumundo und Equalamail, die behaupten, dass sie wirklich Opt-in-Listen betreiben. Sie können diese nur anhand der Kopfzeilen filtern, egal was sie im Textkörper sagen. Aber jeder, der bereit ist, Kopfzeilen zu fälschen oder offene Relais zu verwenden, einschliesslich der meisten Porno-Spammer, sollte in der Lage sein, einige Nachrichten an Netzwerk-Level-Filter vorbeizuschicken, wenn sie wollen. (Allerdings nicht unbedingt die Nachricht, die sie gerne senden würden, was ja etwas ist.)

Die Art von Filtern, von denen ich optimistisch bin, sind solche, die Wahrscheinlichkeiten auf der Grundlage der E-Mails jedes einzelnen Benutzers berechnen. Diese können viel effektiver sein, nicht nur bei der Vermeidung von falsch-positiven Ergebnissen, sondern auch bei der Filterung: Zum Beispiel ist das Auffinden der E-Mail-Adresse des Empfängers in Base-64-codierter Form irgendwo in einer Nachricht ein sehr guter Spam-Indikator.

Aber der eigentliche Vorteil individueller Filter ist, dass sie alle verschieden sein werden. Wenn jeder Filter unterschiedliche Wahrscheinlichkeiten hat, wird die Optimierungsschleife der Spammer, die Programmierer als ihren Edit-Compile-Test-Zyklus bezeichnen würden, erschreckend langsam. Anstatt nur einen Spam so lange zu optimieren, bis er durch eine Kopie von einem Filter kommt, den sie auf ihrem Desktop haben, müssen sie für jede Optimierung einen Testversand durchführen. Es wäre wie Programmieren in einer Sprache ohne interaktive Topebene, und ich würde das niemandem wünschen.

Hinweise

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

Wahrscheinlichkeiten in diesem Algorithmus werden unter Verwendung eines degenerierten Falls der Bayes'schen Regel berechnet. Es gibt zwei vereinfachende Annahmen: dass die Wahrscheinlichkeiten von Merkmalen (d.h. Wörtern) unabhängig sind und dass wir nichts über die a-priori-Wahrscheinlichkeit wissen, dass eine E-Mail Spam ist.

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

Die zweite Annahme habe ich getroffen, weil der Anteil von Spam in meiner eingehenden Mail von Tag zu Tag (ja, sogar von Stunde zu Stunde) so stark schwankte, dass das gesamte a-priori-Verhältnis als Prädiktor wertlos erschien. Wenn Sie annehmen, dass P(Spam) und P(Nicht-Spam) beide 0,5 betragen, heben sie sich gegenseitig auf und Sie können sie aus der Formel entfernen.

Wenn Sie Bayes'sche Filterung in einer Situation durchführen würden, in der das Verhältnis von Spam zu Nicht-Spam durchgehend sehr hoch oder (insbesondere) sehr niedrig ist, könnten Sie die Filter- leistung wahrscheinlich verbessern, indem Sie a-priori-Wahrscheinlichkeiten einbeziehen. Um dies richtig zu machen, müssten Sie die Verhältnisse nach Tageszeit verfolgen, weil Spam- und legitimes Mail-Volumen beide unterschiedliche tägliche Muster 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] Zu der Zeit hatte ich null falsch-positive Ergebnisse aus etwa 4.000 legitimen E-Mails. Wenn die nächste legitime E-Mail ein falsch-positives Ergebnis wäre, würde dies 0,03% ergeben. Diese falsch-positiven Raten sind nicht vertrauenswürdig, wie ich später erkläre. Ich zitiere hier eine Zahl, nur um zu betonen, dass die falsch-positive Rate, was auch immer sie sein mag, weniger als 1,16% beträgt.

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

[6] In ``A Plan for Spam'' habe ich Schwellenwerte von 0,99 und 0,01 verwendet. Es scheint gerechtfertigt, Schwellenwerte zu verwenden, die proportional zur Grösse der Korpora sind. Da ich jetzt etwa 10.000 von jeder Art von Mail habe, verwende ich 0,9999 und 0,0001.

[7] Hier gibt es einen Fehler, den ich wahrscheinlich beheben sollte. Derzeit, wenn Subject*foo'' zu foo'' degeneriert, bedeutet das, dass Sie die Statistiken für das Vorkommen von foo'' in dem Textkörper oder den Kopfzeilen erhalten, die ich nicht markiere. Was ich tun sollte, ist, Statistiken für foo'' insgesamt sowie für spezifische Versionen zu verfolgen und von Subject*foo'' nicht zu foo'' zu degenerieren, sondern zu ``Anywhere*foo''. Das Gleiche gilt für die Gross- und Kleinschreibung: Ich sollte von Grossbuchstaben zu beliebiger Gross- und Kleinschreibung degenerieren, nicht zu Kleinbuchstaben.

Es wäre wahrscheinlich ein Gewinn, dies auch mit Preisen zu tun, z.B. von $129.99'' zu $--9.99'', $--.99'', und $--''.

Sie könnten auch von Wörtern zu ihren Stämmen degenerieren, aber dies würde wahrscheinlich nur die Filterraten in der Anfangsphase verbessern, wenn Sie kleine Korpora hatten.

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

[9] Falsch-positive Ergebnisse sind nicht alle gleich, und wir sollten uns daran erinnern, wenn wir Techniken zum Stoppen von Spam vergleichen. Während viele der falsch-positiven Ergebnisse, die durch Filter verursacht werden, Near-Spams sind, die Sie nicht vermissen würden, werden falsch-positive Ergebnisse, die durch Blacklists verursacht werden, zum Beispiel nur Mails von Personen sein, die sich für den falschen ISP entschieden haben. In beiden Fällen fangen Sie Mail ab, die in der Nähe von Spam liegt, aber bei Blacklists ist die Nähe physisch, und bei Filtern ist sie textuell.

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

Das Herauspicken der Wörter wird nicht trivial sein. Es wird mehr erfordern als nur die Rekonstruktion von Wortgrenzen; Spammer fügen sowohl Buchstaben hinzu (xHot nPorn cSite'') als auch lassen sie weg (P#rn''). Die Sehforschung könnte hier nützlich sein, da das menschliche Sehvermögen die Grenze ist, an die sich solche Tricks annähern werden.

[11] Im Allgemeinen sind Spams repetitiver als normale E-Mails. Sie wollen diese Botschaft nach Hause hämmern. Ich erlaube derzeit keine Duplikate in den Top 15 Token, weil Sie ein falsch-positives Ergebnis erhalten könnten, wenn der Absender zufällig ein schlechtes Wort mehrmals verwendet. (In meinem aktuellen Filter hat ``dick'' eine Spam-Wahrscheinlichkeit von 0,9999, aber es ist auch ein Name.) Es scheint, dass wir Duplizierung zumindest bemerken sollten, daher werde ich vielleicht versuchen, bis zu zwei von jedem Token zuzulassen, wie Brian Burton es in SpamProbe tut.

[12] Dies ist das, wozu Ansätze wie der von Brightmail degenerieren werden, sobald Spammer dazu gezwungen werden, Mad-Lib- Techniken zu verwenden, um alles andere in der Nachricht zu generieren.

[13] Es wird manchmal argumentiert, dass wir an der Filterung auf Netzwerkebene arbeiten sollten, weil sie effizienter ist. Was die Leute meisten OMITTING_RECITATION, wenn sie das sagen, ist: Wir filtern derzeit auf Netzwerkebene, und wir wollen nicht von vorne anfangen. Aber man kann das Problem nicht so diktieren, dass es zu seiner Lösung passt.

Historisch gesehen waren Argumente der knappen Ressourcen die Verliererseite in Debatten über Softwaredesign. Die Leute neigen dazu, sie nur zu verwenden, 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 Artikels und an Dan nochmals für die meiste 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