Bessere Bayessche Filterung | undefined

Januar 2003

(Dieser Artikel wurde als Vortrag auf der Spam Conference 2003 gehalten. Er beschreibt die Arbeit, die ich zur Verbesserung der Leistung des Algorithmus geleistet habe, der in A Plan for Spam beschrieben wird, und was ich in Zukunft tun werde.)

Die erste Entdeckung, die ich hier präsentieren möchte, ist ein Algorithmus zur verzögerten Auswertung von Forschungsarbeiten. Schreiben Sie einfach, was Sie wollen, und zitieren Sie keine früheren Arbeiten, und empörte Leser werden Ihnen Referenzen zu allen Arbeiten 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, einem etablierten Feld, aber die ersten Arbeiten über Bayessche Spam-Filterung per se scheinen zwei Vorträge auf derselben Konferenz im Jahr 1998 gewesen zu sein, einer von Pantel und Lin [2] und ein weiterer von einer Gruppe des Microsoft Research [3].

Als ich von dieser Arbeit hörte, war ich etwas überrascht. Wenn Leute schon vor vier Jahren Bayessche Filterung betrieben, warum hat es nicht jeder benutzt? Als ich die Arbeiten las, fand ich heraus, warum. Pantel und Lin's 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 alarmierend, wenn zwei Personen, die dasselbe Experiment durchführen, stark abweichende Ergebnisse erzielen. Es ist hier besonders alarmierend, weil diese beiden Zahlenreihen zu entgegengesetzten 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% Fehlalarmen, dass die Filterung keine akzeptable Lösung ist, während 99,5% mit weniger als 0,03% Fehlalarmen bedeutet, dass sie es ist.

Warum also erhielten wir so unterschiedliche Zahlen? Ich habe nicht versucht, die Ergebnisse von Pantel und Lin zu reproduzieren, aber aus der Lektüre des Papiers sehe ich fünf Dinge, die den Unterschied wahrscheinlich erklären.

Eines ist einfach, dass sie ihren Filter mit sehr wenigen Daten trainiert haben: 160 Spam- und 466 Nicht-Spam-Mails. Die Leistung des Filters sollte bei so kleinen Datensätzen immer noch steigen. Ihre Zahlen sind also möglicherweise keine genaue Messung der Leistung ihres Algorithmus, geschweige denn der Bayesschen Spam-Filterung im Allgemeinen.

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

Drittens haben Pantel und Lin die Tokens gestemmt, was bedeutet, dass sie z.B. sowohl "mailing" als auch "mailed" auf die Wurzel "mail" reduziert haben. Sie mochten das Gefühl gehabt haben, dass sie dazu durch die geringe Größe ihres Korpus gezwungen waren, aber wenn ja, ist dies eine Art vorzeitige Optimierung.

Viertens haben sie die Wahrscheinlichkeiten anders berechnet. Sie benutzten alle Tokens, während ich nur die 15 wichtigsten benutze. Wenn Sie alle Tokens verwenden, werden Sie längere Spams verpassen, die Art, bei der jemand seine Lebensgeschichte bis zu dem Punkt erzählt, an dem er durch ein Multi-Level-Marketing-Schema reich geworden ist. Und ein solcher Algorithmus wäre für Spammer leicht zu fälschen: Fügen Sie einfach einen großen Block zufälligen Text hinzu, um die Spam-Begriffe auszugleichen.

Schließlich haben sie nicht gegen Fehlalarme voreingenommen. Ich denke, jeder Spam-Filteralgorithmus sollte über einen praktischen Regler verfügen, den Sie drehen können, um die Fehlalarmrate auf Kosten der Filterrate zu verringern. Ich tue dies, indem ich die Vorkommen von Tokens im Nicht-Spam-Korpus doppelt zähle.

Ich glaube nicht, dass es eine gute Idee ist, Spam-Filterung als ein reines Textklassifizierungsproblem zu behandeln. Sie können Textklassifizierungstechniken verwenden, aber Lösungen können und sollten die Tatsache widerspiegeln, dass der Text E-Mail ist und Spam im Besonderen. E-Mail ist nicht nur Text; sie hat Struktur. Spam-Filterung ist nicht nur Klassifizierung, da Fehlalarme so viel schlimmer sind als Fehlschläge, dass Sie sie als eine andere Art von Fehler behandeln sollten. Und die Fehlerquelle ist nicht nur zufällige Variation, sondern ein lebender menschlicher Spammer, der aktiv daran arbeitet, 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 gerade erwähnten Designprinzip. Es ist ein reiner Textklassifikator, aber ein so erstaunlich effektiver, dass er Spam fast perfekt filtert, ohne überhaupt zu wissen, was er tut.

Als ich verstand, wie CRM114 funktionierte, schien es unvermeidlich, dass ich schließlich von der Filterung basierend auf einzelnen Wörtern zu einem solchen Ansatz übergehen würde. Aber zuerst, dachte ich, werde ich sehen, wie weit ich mit einzelnen Wörtern komme. Und die Antwort ist überraschend weit.

Meistens habe ich an intelligenterer Tokenisierung gearbeitet. Bei aktuellem Spam konnte ich Filterraten erzielen, die sich CRM114 nähern. Diese Techniken sind größtenteils orthogonal zu denen von Bill; eine optimale Lösung könnte beide integrieren.

"A Plan for Spam" verwendet eine sehr einfache Definition eines Tokens. Buchstaben, Ziffern, Bindestriche, Apostrophe und Dollarzeichen sind Bestandteile, und alles andere ist ein Token-Trenner. Ich habe auch die 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 vorkommen. Das ermöglicht es mir, IP-Adressen und Preise intakt zu erhalten.
Eine Preisspanne wie $20-25 ergibt zwei Tokens, $20 und $25.
Tokens, die in den Zeilen To, From, Subject und Return-Path oder in URLs vorkommen, werden entsprechend markiert. Z.B. wird "foo" in der Subject-Zeile zu "Subject*foo". (Der Stern könnte jedes Zeichen sein, das Sie nicht als Bestandteil zulassen.)

Solche Maßnahmen erhöhen das Vokabular des Filters, was ihn diskriminierender macht. Zum Beispiel hat im aktuellen Filter "free" in der Subject-Zeile eine Spam-Wahrscheinlichkeit von 98%, während dasselbe Token im Body nur eine Spam-Wahrscheinlichkeit von 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 Tokens die gleiche Wahrscheinlichkeit von 0,7602 gehabt. Dieser Filter erkannte etwa 23.000 Tokens. Der aktuelle erkennt etwa 187.000.

Der Nachteil eines größeren Universums von Tokens ist, dass die Wahrscheinlichkeit von Fehlschlägen größer ist. Das Verteilen Ihres Korpus auf mehr Tokens hat denselben Effekt wie die Verkleinerung. Wenn Sie z.B. Ausrufezeichen als Bestandteile betrachten, könnten Sie am Ende 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, was ich Degeneration nenne. Wenn Sie keine exakte Übereinstimmung für ein Token finden können, behandeln Sie es so, als wäre es eine weniger spezifische Version. Ich betrachte abschließende Ausrufezeichen, Großbuchstaben und das Vorkommen in einem der fünf markierten Kontexte als eine spezifischere Token-Erstellung. Wenn ich zum Beispiel keine Wahrscheinlichkeit für "Subjectfree!" finde, suche ich nach Wahrscheinlichkeiten für "Subjectfree", "free!" und "free" und nehme, welche auch immer am weitesten von 0,5 entfernt ist.

Hier sind die Alternativen [7], die berücksichtigt 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, stellen Sie sicher, dass Sie Versionen mit Anfangsbuchstaben sowie alle Großbuchstaben und alle Kleinbuchstaben berücksichtigen. Spams haben tendenziell mehr Sätze im Imperativ, und darin ist das erste Wort ein Verb. Daher haben Verben mit Anfangsbuchstaben höhere Spam-Wahrscheinlichkeiten als sie in Kleinbuchstaben hätten. In meinem Filter hat die Spam-Wahrscheinlichkeit von "Act" 98% und für "act" nur 62%.

Wenn Sie das Vokabular Ihres Filters erhöhen, können Sie am Ende dasselbe Wort mehrmals zählen, gemäß Ihrer alten Definition von "dasselbe". Logisch gesehen sind es keine gleichen Tokens mehr. Aber wenn Sie das immer noch stört, lassen Sie mich aus Erfahrung hinzufügen, dass die Wörter, die Sie mehrmals zu zählen scheinen, genau die sind, die Sie wollen würden.

Eine weitere Auswirkung eines größeren Vokabulars ist, dass Sie beim Betrachten einer eingehenden E-Mail mehr interessante Tokens finden, d.h. solche mit Wahrscheinlichkeiten weit weg von 0,5. Ich benutze die 15 wichtigsten, um zu entscheiden, ob eine E-Mail Spam ist. Aber Sie können auf ein Problem stoßen, wenn Sie eine feste Zahl wie diese verwenden. Wenn Sie viele maximal interessante Tokens finden, kann das Ergebnis durch den zufälligen Faktor bestimmt werden, der die Reihenfolge gleich interessanter Tokens bestimmt. Eine Möglichkeit, damit umzugehen, ist, einige als interessanter als andere zu behandeln.

Zum Beispiel kommt das Token "dalco" dreimal in meinem Spam-Korpus vor und nie in meinem legitimen Korpus. Das Token "Url*optmails" (was "optmails" innerhalb einer URL bedeutet) kommt 1223 Mal vor. Und doch, als ich früher Wahrscheinlichkeiten für Tokens berechnete, hätten beide die gleiche Spam-Wahrscheinlichkeit, den Schwellenwert von 0,99.

Das fühlt sich nicht richtig an. Es gibt theoretische Argumente dafür, diesen beiden Tokens erheblich unterschiedliche Wahrscheinlichkeiten zu geben (Pantel und Lin tun dies), aber das habe ich noch nicht versucht. Es scheint zumindest, dass, wenn wir mehr als 15 Tokens finden, die nur in einem oder dem anderen Korpus vorkommen, wir denjenigen Priorität einräumen sollten, die häufig vorkommen. Daher gibt es jetzt zwei Schwellenwerte. Für Tokens, die nur im Spam-Korpus gefunden werden, beträgt die Wahrscheinlichkeit 0,9999, wenn sie mehr als 10 Mal vorkommen, und 0,9998 sonst. Dito am anderen Ende der Skala für Tokens, die nur im legitimen Korpus gefunden werden.

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

Eine weitere Möglichkeit wäre, nicht nur 15 Tokens zu berücksichtigen, sondern alle Tokens über einem bestimmten Interessensschwellenwert. Steven Hauser tut dies in seinem statistischen Spam-Filter [8]. Wenn Sie einen Schwellenwert verwenden, setzen Sie ihn sehr hoch, oder Spammer könnten Sie fälschen, indem sie Nachrichten mit mehr unschuldigen Wörtern überladen.

Schließlich, was soll man mit HTML machen? Ich habe das gesamte Spektrum der Optionen ausprobiert, vom Ignorieren bis zum vollständigen Parsen. HTML zu ignorieren ist eine schlechte Idee, da es voller nützlicher Spam-Anzeichen ist. Aber wenn Sie es vollständig parsen, könnte Ihr Filter zu einem bloßen HTML-Erkenner degenerieren. Der effektivste Ansatz scheint der Mittelweg zu sein, einige Tokens 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, da sie URLs enthalten.

Ich könnte wahrscheinlich intelligenter mit HTML umgehen, aber ich glaube nicht, dass es sich lohnt, viel Zeit darauf zu verwenden. Spams voller HTML sind leicht zu filtern. Die intelligenteren Spammer vermeiden es bereits. Die Leistung in Zukunft sollte also nicht stark davon abhängen, wie Sie mit HTML umgehen.

Leistung

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

Zwei der vier verpassten Spams kamen durch, weil sie zufällig Wörter verwendeten, 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 nur anhand des Inhalts zu filtern, da die Header unauffällig sind und sie vorsichtig mit den verwendeten Wörtern umgehen. Selbst dann kann ich sie normalerweise fangen. Dieser hier schlüpfte mit einer Wahrscheinlichkeit von 0,88, knapp unter dem Schwellenwert von 0,9, durch.

Natürlich würde die Betrachtung von Mehrwortsequenzen ihn leicht fangen. "Unten ist das Ergebnis Ihres Feedback-Formulars" ist ein sofortiger Hinweis.

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

Wenn die Spammer bei den Headern vorsichtig sind und eine frische URL verwenden, gibt es in Spam der Zukunft nichts für Filter zu bemerken. Wir können natürlich kontern, indem wir einen Crawler schicken, um die Seite anzusehen. Aber das ist vielleicht nicht notwendig. Die Antwortrate für Spam der Zukunft muss niedrig sein, sonst würde es jeder tun. Wenn sie niedrig genug ist, wird es für Spammer nicht rentabel sein, ihn zu senden, und wir müssen nicht zu hart daran arbeiten, ihn zu filtern.

Nun zu den wirklich schockierenden Nachrichten: Während desselben Monats erhielt ich drei Fehlalarme.

Auf eine gewisse 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, entpuppen sich als E-Mails, die stark nach Spam klingen, und dies sind tendenziell die, die man am wenigsten vermissen möchte [9].

Zwei der Fehlalarme waren Newsletter von Unternehmen, bei denen ich Dinge gekauft hatte. Ich hatte nie darum gebeten, sie zu erhalten, also waren sie wohl Spams, aber ich zähle sie als Fehlalarme, weil ich sie vorher nicht als Spams gelöscht hatte. Der Grund, warum die Filter sie erfassten, war, dass beide Unternehmen im Januar zu kommerziellen E-Mail-Versendern wechselten, anstatt die E-Mails von ihren eigenen Servern zu versenden, und sowohl die Header als auch die Bodies viel spammiger wurden.

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

Es ist schwer zu sagen, wie die allgemeine Fehlalarmrate ist, weil wir statistisch gesehen im Rauschen sind. Jeder, der an Filtern gearbeitet hat (zumindest effektive Filter), wird sich dieses Problems bewusst sein. Bei einigen E-Mails ist es schwer zu sagen, ob sie Spam sind oder nicht, und das sind die, die man sich ansieht, wenn man die Filter wirklich engmaschig macht. Zum Beispiel hat der Filter bisher zwei E-Mails abgefangen, die wegen eines Tippfehlers an meine Adresse gesendet wurden, und eine, die an mich gesendet wurde, weil man glaubte, ich sei jemand anderes. Arguably sind dies weder mein Spam noch meine Nicht-Spam-Mails.

Ein weiterer Fehlalarm kam von einem Vizepräsidenten von Virtumundo. Ich schrieb ihnen, indem ich mich als Kunde ausgab, und da die Antwort über die Mailserver von Virtumundo zurückkam, hatte sie die kompromittierendsten Header, die man sich vorstellen kann. Arguably ist dies auch kein echter Fehlalarm, sondern eine Art Heisenberg'sche Unschärfe: Ich habe ihn nur bekommen, weil ich über Spam-Filterung schrieb.

Abgesehen davon hatte ich bisher insgesamt fünf Fehlalarme bei etwa 7740 legitimen E-Mails, eine Rate von 0,06%. Die anderen beiden waren eine Benachrichtigung, dass etwas, das ich gekauft hatte, nachbestellt wurde, und eine Party-Erinnerung von Evite.

Ich glaube nicht, dass diese Zahl vertrauenswürdig ist, teilweise weil die Stichprobe so klein ist, und teilweise, weil ich glaube, dass ich den Filter so reparieren kann, dass er einige davon nicht erfasst.

Fehlalarme sind für mich eine andere Art von Fehler als Fehlschläge. Die Filterrate ist ein Maß für die Leistung. Fehlalarme betrachte ich eher als Bugs. Ich gehe die Verbesserung der Filterrate als Optimierung an und die Verringerung von Fehlalarmen als Debugging.

Diese fünf Fehlalarme sind also meine Bug-Liste. Zum Beispiel wurde die E-Mail aus Ägypten abgefangen, 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 die E-Mail, die komplett in Großbuchstaben geschrieben ist, eigentlich konzeptionell ein Merkmal, nicht eines für jedes Wort. Ich muss die Groß-/Kleinschreibung auf eine ausgefeiltere Weise handhaben.

Was also von diesen 0,06% halten? Nicht viel, denke ich. Man könnte sie als Obergrenze betrachten, wobei die kleine Stichprobengröße zu berücksichtigen ist. Aber in diesem Stadium ist es eher ein Maß für die Bugs in meiner Implementierung als eine intrinsische Fehlalarmrate der Bayesschen Filterung.

Zukunft

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

Zum Beispiel arbeiten Spammer jetzt aggressiv daran, Filter zu umgehen, und eines der Dinge, die sie tun, ist, Wörter zu zerlegen und falsch zu schreiben, um zu verhindern, dass Filter sie erkennen. Aber die Arbeit daran hat keine Priorität für mich, weil ich diese Spams immer noch problemlos fangen kann [10].

Es gibt zwei Arten von Spams, mit denen ich derzeit Probleme 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-Seite anzusehen. Diese kommen durch, weil sie die einzige Art von Verkaufsgespräch sind, die Sie führen können, ohne Verkaufsgespräche zu führen. Sie verwenden das gleiche Vokabular wie normale E-Mails.

Die andere Art von Spams, die ich nur schwer filtern kann, sind die von Unternehmen z.B. aus Bulgarien, die Vertrags-Programmierdienstleistungen anbieten. Diese kommen durch, weil ich auch ein Programmierer bin und die Spams voller der gleichen Wörter sind wie meine echten E-Mails.

Ich werde mich wahrscheinlich zuerst auf die Art der persönlichen Anzeigen konzentrieren. Ich denke, wenn ich genauer hinschaue, werde ich statistische Unterschiede zwischen diesen und meinen echten E-Mails finden können. Der Schreibstil ist sicherlich anders, obwohl es Mehrwortfilterung erfordern könnte, um das zu erfassen. Außerdem bemerke ich, dass sie die URL wiederholen, und jemand, der eine URL in eine legitime E-Mail einfügt, würde das nicht tun [11].

Die Outsourcing-Typen werden schwer zu fangen sein. Selbst wenn Sie einen Crawler zur Website schicken, würden Sie keine eindeutige statistische Waffe finden. Vielleicht ist die einzige Antwort eine zentrale Liste von Domains, die in Spams beworben werden [12]. Aber es kann nicht viele dieser Art von E-Mails geben. Wenn die einzigen verbleibenden Spams unerbetene Angebote von Vertrags-Programmierdienstleistungen aus Bulgarien wären, könnten wir uns wahrscheinlich alle damit beschäftigen, etwas anderes zu tun.

Werden statistische Filter uns tatsächlich so weit bringen? Ich weiß es nicht. Im Moment ist Spam für mich persönlich kein Problem. Aber Spammer haben noch keine ernsthaften Anstrengungen unternommen, statistische Filter zu fälschen. Was wird passieren, wenn sie es tun?

Ich bin nicht optimistisch, was Filter auf Netzwerkebene angeht [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 E-Mails durch Spamassassin laufen lässt und Ihnen mitteilt, ob sie herausgefiltert werden.

Netzwerk-Level-Filter werden nicht völlig nutzlos sein. Sie reichen möglicherweise aus, um den gesamten "Opt-in"-Spam zu eliminieren, d.h. Spam von Unternehmen wie Virtumundo und Equalamail, die behaupten, dass sie tatsächlich Opt-in-Listen führen. Sie können diese nur anhand der Header filtern, unabhängig davon, was sie im Body sagen. Aber jeder, der bereit ist, Header zu fälschen oder Open Relays zu verwenden, einschließlich der meisten Pornospammer, sollte in der Lage sein, eine Nachricht durch Netzwerk-Level-Filter zu bekommen, wenn er will. (Aber keineswegs die Nachricht, die sie senden möchten, was etwas ist.)

Die Art von Filtern, über die ich optimistisch bin, sind solche, die Wahrscheinlichkeiten basierend auf den E-Mails jedes einzelnen Benutzers berechnen. Diese können viel effektiver sein, nicht nur bei der Vermeidung von Fehlalarmen, sondern auch beim Filtern: Zum Beispiel ist das Finden der E-Mail-Adresse des Empfängers, die Base64-kodiert in einer Nachricht vorkommt, ein sehr guter Spam-Indikator.

Aber der wirkliche Vorteil von individuellen Filtern ist, dass sie alle unterschiedlich sein werden. Wenn die Filter aller Personen unterschiedliche Wahrscheinlichkeiten haben, wird dies die Optimierungsschleife der Spammer, was Programmierer ihren Edit-Compile-Test-Zyklus nennen würden, erschreckend langsam machen. Anstatt nur einen Spam zu optimieren, bis er durch eine Kopie eines Filters läuft, den sie auf ihrem Desktop haben, müssen sie für jede Optimierung eine Test-E-Mail durchführen. Es wäre, als würde man in einer Sprache ohne interaktives Toplevel programmieren, und das wünsche ich niemandem.

Anmerkungen

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

Die Wahrscheinlichkeiten in diesem Algorithmus werden mit einem degenerierten Fall 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 Bayessche" bezeichnet.

Die zweite Annahme traf ich, weil das Verhältnis von Spam zu Nicht-Spam in meiner eingehenden E-Mail von Tag zu Tag (tatsächlich von Stunde zu Stunde) so stark schwankte, dass das gesamte A-priori-Verhältnis als Prädiktor wertlos erschien. Wenn Sie davon ausgehen, dass P(Spam) und P(Nicht-Spam) beide 0,5 sind, heben sie sich auf und Sie können sie aus der Formel entfernen.

Wenn Sie Bayessche Filterung in einer Situation durchführen würden, in der das Verhältnis von Spam zu Nicht-Spam durchweg sehr hoch oder (besonders) sehr niedrig ist, könnten Sie die Filterleistung wahrscheinlich verbessern, indem Sie A-priori-Wahrscheinlichkeiten einbeziehen. Um dies richtig zu tun, müssten Sie Verhältnisse nach Tageszeit verfolgen, da sowohl Spam als auch legitime E-Mail-Volumen deutliche 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 dieser Zeit hatte ich null Fehlalarme bei etwa 4.000 legitimen E-Mails. Wenn die nächste legitime E-Mail ein Fehlalarm wäre, würde dies 0,03% ergeben. Diese Fehlalarmraten sind unzuverlässig, wie ich später erkläre. Ich zitiere hier eine Zahl nur, um zu betonen, dass, was auch immer die Fehlalarmrate ist, sie kleiner als 1,16% ist.

[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 vertretbar, Schwellenwerte proportional zur Größe der Korpora zu verwenden. Da ich jetzt etwa 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 "Subjectfoo", wenn es zu "foo" degeneriert, dass Sie die Statistiken für Vorkommen von "foo" im Body oder in Header-Zeilen außer denen, die ich markiere, erhalten. Was ich tun sollte, ist, Statistiken für "foo" insgesamt sowie für spezifische Versionen zu verfolgen und von "Subjectfoo" nicht zu "foo", sondern zu "Anywhere*foo" zu degenerieren. Dito für Groß-/Kleinschreibung: Ich sollte von Großbuchstaben zu beliebiger Groß-/Kleinschreibung, nicht zu Kleinbuchstaben, degenerieren.

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

Sie könnten auch von Wörtern zu ihren Stämmen degenerieren, aber das würde die Filterraten wahrscheinlich nur am Anfang verbessern, wenn Sie kleine Korpora haben.

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

[9] Fehlalarme sind nicht alle gleich, und wir sollten uns dessen bewusst sein, wenn wir Techniken zum Stoppen von Spam vergleichen. Während viele der von Filtern verursachten Fehlalarme Near-Spams sein werden, die Sie nicht vermissen möchten, werden Fehlalarme, die beispielsweise durch Blacklists verursacht werden, einfach E-Mails von Personen sein, die den falschen ISP gewählt haben. In beiden Fällen fangen Sie E-Mails ab, die nahe an Spam sind, aber für Blacklists ist die Nähe physisch und für Filter textuell.

[10] Wenn Spammer gut genug darin werden, Tokens zu verschleiern, damit dies ein Problem darstellt, 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 auszuwählen. Und natürlich wäre das Finden von Wörtern auf diese Weise, die im ursprünglichen Text nicht sichtbar waren, selbst ein Beweis für Spam.

Das Auswählen der Wörter wird nicht trivial sein. Es erfordert mehr als nur die Rekonstruktion von Wortgrenzen; Spammer fügen Buchstaben hinzu (xHot nPorn cSite'') und lassen sie weg (P#rn''). Die Forschung im Bereich Sehen könnte hier nützlich sein, da die menschliche Sicht die Grenze ist, der solche Tricks nahe kommen werden.

[11] Im Allgemeinen sind Spams repetitiver als normale E-Mails. Sie wollen die Botschaft eindringlich vermitteln. Ich lasse derzeit keine Duplikate in den Top-15-Tokens zu, da dies zu einem Fehlalarm führen könnte, wenn der Absender zufällig ein schlechtes Wort mehrmals verwendet. (In meinem aktuellen Filter hat "dick" eine Spam-Wahrscheinlichkeit von 0,9999, ist aber auch ein Name.) Es scheint, dass wir Duplikation zumindest bemerken sollten, also werde ich versuchen, bis zu zwei von jedem Token zuzulassen, wie Brian Burton es in SpamProbe tut.

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

[13] Es wird manchmal argumentiert, dass wir auf Netzwerkebene filtern sollten, weil es effizienter ist. Was die Leute normalerweise meinen, wenn sie das sagen: Wir filtern derzeit auf Netzwerkebene und wollen nicht bei Null anfangen. Aber man kann das Problem nicht diktieren, um die Lösung anzupassen.

Historisch gesehen waren Argumente knapper Ressourcen die Verlierer in Debatten über Software-Design. Leute benutzen 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 nochmals an Dan für die meiste Infrastruktur, auf der dieser Filter läuft.

Verwandt: