BESSERES BAYES'SCHES 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 vorhabe.)

Die erste Entdeckung, die ich hier präsentieren möchte, ist ein Algorithmus für die verzögerte Auswertung von Forschungspapieren. Schreiben Sie einfach, was Sie wollen, und zitieren Sie keine vorherige Arbeit, und empörte Leser werden Ihnen Verweise auf alle Papiere senden, die Sie hätten zitieren sollen. Ich entdeckte diesen Algorithmus, nachdem „A Plan for Spam“ [1] auf Slashdot veröffentlicht wurde.

Spam-Filterung ist ein Teilbereich der Textklassifikation, die ein gut etabliertes Feld ist, aber die ersten Papiere über Bayes'sche Spam-Filterung scheinen zwei zu sein, die auf derselben Konferenz 1998 gehalten wurden, eines von Pantel und Lin [2] und ein anderes von einer Gruppe von Microsoft Research [3].

Als ich von dieser Arbeit hörte, war ich etwas überrascht. Wenn die Leute vor vier Jahren schon auf Bayes'sches Filtern gesetzt hatten, warum hat es dann nicht jeder verwendet? Als ich die Papiere las, fand ich heraus, warum. Der Filter von Pantel und Lin war der effektivere der beiden, aber er erfasste nur 92 % des Spams, mit 1,16 % falsch positiven Ergebnissen.

Als ich versuchte, einen Bayes'schen Spam-Filter zu schreiben, erfasste er 99,5 % des Spams mit weniger als 0,03 % falsch positiven Ergebnissen [4]. Es ist immer alarmierend, wenn zwei Personen, die dasselbe Experiment durchführen, stark unterschiedliche Ergebnisse erzielen. Es ist besonders alarmierend, weil diese beiden Zahlen möglicherweise gegensätzliche Schlussfolgerungen liefern. Verschiedene Benutzer haben unterschiedliche Anforderungen, aber ich denke, für viele Menschen bedeutet eine Filterrate von 92 % mit 1,16 % falsch positiven Ergebnissen, dass die Filterung keine akzeptable Lösung ist, während 99,5 % mit weniger als 0,03 % falsch positiven Ergebnissen bedeutet, dass sie es ist.

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

Eines ist einfach, dass sie ihren Filter mit sehr wenig Daten trainiert haben: 160 Spam- und 466 Nicht-Spam-E-Mails. Die Filterleistung sollte bei so kleinen Datensätzen immer noch steigen. Ihre Zahlen sind möglicherweise nicht einmal ein genaues Maß für die Leistung ihres Algorithmus, geschweige denn für die Bayes'sche Spam-Filterung im Allgemeinen.

Aber ich denke, der wichtigste Unterschied ist wahrscheinlich, dass sie die Nachrichtenheader ignoriert haben. Für jeden, der an Spam-Filtern gearbeitet hat, wird dies wie eine perverse Entscheidung erscheinen. Und doch habe ich in den allerersten Filtern, die ich zu schreiben versuchte, die Header ebenfalls ignoriert. Warum? Weil ich das Problem ordentlich halten wollte. Ich wusste damals nicht viel über E-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 könnte denken, diese Lektion wäre zu offensichtlich, um sie zu erwähnen, aber ich musste sie mehrere Male lernen.

Drittens haben Pantel und Lin die Tokens gestemmt, was bedeutet, dass sie z. B. sowohl „mailing“ als auch „mailed“ auf die Wurzel „mail“ reduzierten. Sie fühlten sich möglicherweise gezwungen, dies aufgrund der kleinen Größe ihres Korpus zu tun, aber wenn dem so ist, ist dies eine Art vorzeitige Optimierung.

Viertens haben sie die Wahrscheinlichkeiten anders berechnet. Sie verwendeten alle Tokens, während ich nur die 15 bedeutendsten verwende. Wenn Sie alle Tokens verwenden, werden Sie dazu neigen, längere Spams zu übersehen, bei denen jemand Ihnen seine Lebensgeschichte bis zu dem Punkt erzählt, an dem er durch ein Multilevel-Marketing-Schema reich wurde. Und ein solcher Algorithmus wäre für Spammer leicht zu fälschen: Fügen Sie einfach einen großen Block zufälligen Textes hinzu, um die Spam-Begriffe auszugleichen.

Schließlich haben sie nicht gegen falsch positive Ergebnisse voreingenommen. Ich denke, jeder Spam-Filter-Algorithmus sollte einen praktischen Regler haben, den Sie drehen können, um die Rate falsch positiver Ergebnisse auf Kosten der Filterrate zu verringern. Ich mache dies, indem ich die Vorkommen von Tokens im Nicht-Spam-Korpus doppelt zähle.

Ich denke nicht, dass es eine gute Idee ist, die Spam-Filterung als ein einfaches Textklassifikationsproblem zu behandeln. Sie können Techniken der Textklassifikation 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 Klassifikation, weil falsch positive Ergebnisse so viel schlimmer sind als falsch negative, dass Sie sie als eine andere Art von Fehler behandeln sollten. Und die Fehlerquelle ist nicht nur zufällige Variation, sondern ein lebendiger menschlicher Spammer, der aktiv daran arbeitet, Ihren Filter zu überlisten.

Tokens

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

Sobald ich verstand, wie CRM114 funktionierte, schien es unvermeidlich, dass ich schließlich von der Filterung basierend auf einzelnen Wörtern 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, überraschend weit.

In erster Linie habe ich an einer intelligenteren Tokenisierung gearbeitet. Bei aktuellem Spam konnte ich Filterraten erreichen, die CRM114 nahekommen. Diese Techniken sind größtenteils orthogonal zu Bills; 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 ignorierte auch die Groß- und Kleinschreibung.

Jetzt habe ich eine kompliziertere Definition eines Tokens:

Die Groß- und Kleinschreibung bleibt erhalten.

Ausrufezeichen sind Bestandteile.

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

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

Tokens, die innerhalb der Zeilen To, From, Subject und Return-Path oder innerhalb von URLs auftreten, werden entsprechend markiert. Z. B. wird „foo“ in der Betreffzeile zu „Subject*foo“. (Das Sternchen könnte jedes Zeichen sein, das Sie nicht als Bestandteil zulassen.)

Solche Maßnahmen erhöhen den Wortschatz des Filters, was ihn diskriminierender macht. Zum Beispiel hat „free“ in der Betreffzeile eine Spam-Wahrscheinlichkeit von 98 %, während dasselbe Token im Text 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 für 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 Chance auf Fehlschläge steigt. Wenn Sie Ihr Korpus über mehr Tokens verteilen, hat das denselben Effekt, als würde es kleiner werden. Wenn Sie Ausrufezeichen beispielsweise 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 das, was ich Degeneration nenne. Wenn Sie kein genaues Match für ein Token finden können, behandeln Sie es so, als wäre es eine weniger spezifische Version. Ich betrachte terminale Ausrufezeichen, Großbuchstaben und das Auftreten in einem der fünf markierten Kontexte als ein Token spezifischer. Wenn ich beispielsweise keine Wahrscheinlichkeit für „Subjectfree!“ finde, suche ich nach Wahrscheinlichkeiten für „Subjectfree“, „free!“ und „free“ und nehme die, die am weitesten von 0,5 entfernt ist.

Hier sind die Alternativen [7], die in Betracht gezogen werden, wenn der Filter „FREE!!!“ in der Betreffzeile 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ß- und Kleinbuchstaben berücksichtigen. Spams neigen dazu, mehr Sätze im Imperativ zu haben, und in diesen 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 das Spam-Wahrscheinlichkeit von „Act“ 98 % und für „act“ nur 62 %.

Wenn Sie den Wortschatz Ihres Filters erhöhen, können Sie am Ende dasselbe Wort mehrfach zählen, je nach Ihrer alten Definition von „gleich“. Logisch gesehen sind sie nicht mehr dasselbe Token. Aber wenn Sie sich darüber immer noch Gedanken machen, lassen Sie mich aus Erfahrung hinzufügen, dass die Wörter, die Sie anscheinend mehrfach zählen, genau die sind, die Sie zählen möchten.

Ein weiterer Effekt eines größeren Wortschatzes ist, dass Sie beim Betrachten einer eingehenden E-Mail mehr interessante Tokens finden, was bedeutet, dass diese Wahrscheinlichkeiten weit von 0,5 entfernt sind. Ich verwende die 15 interessantesten, um zu entscheiden, ob eine E-Mail Spam ist. Aber Sie können auf ein Problem stoßen, wenn Sie eine feste Anzahl wie diese verwenden. Wenn Sie viele maximal interessante Tokens finden, kann das Ergebnis von dem zufälligen Faktor abhängen, der die Reihenfolge gleich interessanter Tokens bestimmt. Eine Möglichkeit, damit umzugehen, besteht darin, 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“ (was „optmails“ innerhalb einer URL bedeutet) kommt 1223 Mal vor. Und doch, als ich 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 ich habe das noch nicht versucht. Es scheint zumindest, dass wir, wenn wir mehr als 15 Tokens finden, die nur in einem Korpus oder dem anderen vorkommen, denjenigen, die häufig vorkommen, Priorität einräumen sollten. Jetzt gibt es also zwei Schwellenwerte. Für Tokens, die nur im Spam-Korpus vorkommen, beträgt die Wahrscheinlichkeit 0,9999, wenn sie mehr als 10 Mal vorkommen, und 0,9998 andernfalls. Gleiches gilt am anderen Ende der Skala für Tokens, die nur im legitimen Korpus gefunden werden.

Ich könnte später die Token-Wahrscheinlichkeiten erheblich skalieren, aber diese kleine Menge an Skalierung stellt zumindest sicher, dass die Tokens in der richtigen Reihenfolge sortiert werden.

Eine weitere Möglichkeit wäre, nicht nur 15 Tokens zu betrachten, sondern alle Tokens ü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 überlisten, indem sie Nachrichten mit harmloseren Wörtern füllen.

Was sollte man schließlich über HTML tun? Ich habe das gesamte Spektrum von Optionen ausprobiert, von der Ignorierung bis zur vollständigen Analyse. HTML zu ignorieren ist eine schlechte Idee, weil es voller nützlicher Spam-Zeichen ist. Aber wenn Sie alles analysieren, 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 auf jeden Fall betrachten, da sie URLs enthalten.

Ich könnte wahrscheinlich intelligenter mit HTML umgehen, aber ich denke nicht, dass es sich lohnt, viel Zeit dafür aufzuwenden. Spams, die voller HTML sind, sind leicht zu filtern. Die intelligenteren Spammer vermeiden es bereits. Daher sollte die Leistung in Zukunft 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 Spams, die ich verpasst habe, kamen durch, weil sie zufällig Wörter verwendeten, die häufig in meinen legitimen E-Mails vorkommen.

Der dritte war einer von denen, die ein unsicheres CGI-Skript ausnutzen, um E-Mails an Dritte zu senden. Sie sind schwer nur aufgrund des Inhalts zu filtern, weil die Header unschuldig sind und sie darauf achten, welche Wörter sie verwenden. Trotzdem kann ich sie normalerweise fangen. Dieser hier schlüpfte mit einer Wahrscheinlichkeit von 0,88 durch, knapp unter dem Schwellenwert von 0,9.

Natürlich würde das Betrachten mehrerer Token-Sequenzen es leicht erfassen. „Unten finden Sie das Ergebnis Ihres Feedback-Formulars“ ist ein sofortiger Hinweis.

Der vierte Spam war das, was ich als Spam der Zukunft bezeichne, denn das ist es, was ich erwarte, dass Spam sich entwickelt: 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 Werbung für eine Pornoseite.)

Wenn die Spammer vorsichtig mit den Headern umgehen und eine frische URL verwenden, gibt es im Spam der Zukunft nichts, was Filter bemerken könnten. Wir können natürlich dagegensteuern, indem wir einen Crawler schicken, um die Seite zu betrachten. Aber das könnte nicht notwendig sein. Die Rücklaufquote für Spam der Zukunft muss niedrig sein, sonst würde es jeder tun. Wenn sie niedrig genug ist, wird es sich nicht lohnen, dass Spammer sie senden, und wir müssen nicht zu hart daran arbeiten, sie zu filtern.

Jetzt zu den wirklich schockierenden Nachrichten: In diesem einen Monat erhielt ich drei falsch positive Ergebnisse.

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 festzustellen, dass sie nicht so schlimm sind, wie ich befürchtet hatte. Falsch positive Ergebnisse, die von statistischen Filtern erzeugt werden, sind E-Mails, die Spam sehr ähnlich sind, und diese sind tendenziell die, die Sie am wenigsten stören würden, wenn Sie sie übersehen [9].

Zwei der falsch positiven Ergebnisse waren Newsletter von Unternehmen, bei denen ich Dinge gekauft habe. Ich habe nie darum gebeten, sie zu erhalten, also könnte man argumentieren, dass sie Spam waren, aber ich zähle sie als falsch positive Ergebnisse, weil ich sie vorher nicht als Spam gelöscht hatte. Der Grund, warum die Filter sie erfasst haben, war, dass beide Unternehmen im Januar auf kommerzielle E-Mail-Absender umgestiegen sind, anstatt die E-Mails von ihren eigenen Servern zu senden, und sowohl die Header als auch die Inhalte viel spamiger wurden.

Das dritte falsch positive Ergebnis war ein schlechtes. Es war von jemandem aus Ägypten und in Großbuchstaben geschrieben. Dies war eine direkte Folge der Sensitivität der Tokens; der Plan für Spam-Filter hätte es nicht erfasst.

Es ist schwer zu sagen, wie hoch die allgemeine Rate falsch positiver Ergebnisse ist, weil wir statistisch im Rauschen sind. Jeder, der an Filtern gearbeitet hat (zumindest an effektiven Filtern), 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 Sie sich ansehen, wenn Sie die Filter wirklich eng einstellen. Zum Beispiel hat der Filter bisher zwei E-Mails erfasst, die an meine Adresse aufgrund eines Tippfehlers gesendet wurden, und eine, die mir in dem Glauben gesendet wurde, ich sei jemand anderes. Man könnte argumentieren, dass dies weder mein Spam noch meine Nicht-Spam-Mail ist.

Ein weiteres falsch positives Ergebnis kam von einem Vizepräsidenten bei Virtumundo. Ich schrieb ihnen und tat so, als wäre ich ein Kunde, und da die Antwort über die Mail-Server von Virtumundo zurückkam, hatte sie die belastendsten Header, die man sich vorstellen kann. Man könnte argumentieren, dass dies auch kein echtes falsch positives Ergebnis ist, sondern eine Art Heisenbergsche Unschärfe: Ich habe es nur bekommen, weil ich über Spam-Filterung schrieb.

Wenn man diese nicht zählt, 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, zurückbestellt wurde, und eine Partyerinnerung von Evite.

Ich denke nicht, dass diese Zahl vertrauenswürdig ist, partly weil die Stichprobe so klein ist, und partly weil ich denke, dass ich den Filter so anpassen kann, dass er einige dieser Ergebnisse nicht erfasst.

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

Diese fünf falsch positiven Ergebnisse sind also meine Bug-Liste. Zum Beispiel wurde die E-Mail aus Ägypten erfasst, weil der Text in Großbuchstaben dem Filter wie ein nigerianischer Spam erschien. Das ist wirklich eine Art Bug. Wie bei HTML ist die gesamte E-Mail in Großbuchstaben wirklich konzeptionell ein Merkmal, nicht eines für jedes Wort. Ich muss die Groß- und Kleinschreibung auf eine ausgeklügeltere Weise behandeln.

Was also von dieser 0,06 % zu halten? Nicht viel, denke ich. Man könnte es als obere Grenze betrachten, wobei man die kleine Stichprobengröße im Hinterkopf behält. Aber in diesem Stadium ist es mehr ein Maß für die Bugs in meiner Implementierung als eine intrinsische Rate falsch positiver Ergebnisse der Bayes'schen Filterung.

Zukunft

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

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 daran zu arbeiten, ist nicht meine erste Priorität, denn ich habe immer noch keine Probleme, diese Spams zu erfassen [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-Website anzusehen. Diese kommen durch, weil sie die eine Art von Verkaufsangebot sind, die Sie machen können, ohne Verkaufsjargon zu verwenden. Sie verwenden denselben Wortschatz wie gewöhnliche E-Mails.

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

Ich werde wahrscheinlich zuerst auf die Art von persönlichen Anzeigen fokussieren. 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 möglicherweise mehrwortige Filterung erfordert, um das zu erfassen. Außerdem fällt mir auf, dass sie dazu neigen, die URL zu wiederholen, und jemand, der eine URL in einer legitimen E-Mail einfügt, würde das nicht tun [11].

Die Outsourcing-Art wird schwer zu fangen sein. Selbst wenn Sie einen Crawler zur Website schicken, 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 dieser Art von E-Mails geben. Wenn die einzigen verbleibenden Spams unaufgeforderte Angebote für Vertragsprogrammierungsdienste aus Bulgarien wären, könnten wir alle wahrscheinlich zu etwas anderem übergehen.

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

Ich bin nicht optimistisch in Bezug auf Filter, die auf Netzwerkebene arbeiten [13]. Wenn es ein statisches Hindernis gibt, das es wert ist, überwunden zu werden, sind Spammer ziemlich effizient darin, es zu umgehen. Es gibt bereits ein Unternehmen namens Assurance Systems, das Ihre E-Mails durch Spamassassin laufen lässt und Ihnen sagt, ob sie herausgefiltert werden.

Filter auf Netzwerkebene werden nicht völlig nutzlos sein. Sie könnten ausreichen, um allen „Opt-in“-Spam zu beseitigen, was Spam von Unternehmen wie Virtumundo und Equalamail bedeutet, die behaupten, dass sie wirklich Opt-in-Listen führen. Sie können diese nur basierend auf den Headern filtern, egal was sie im Text sagen. Aber jeder, der bereit ist, Header zu fälschen oder offene Relays zu verwenden, vermutlich einschließlich der meisten Pornospammer, sollte in der Lage sein, eine Nachricht an Netzwerkfilter vorbeizuschicken, wenn er will. (Allerdings nicht die Nachricht, die sie gerne senden würden, was etwas ist.)

Die Art von Filtern, bei denen ich optimistisch bin, sind solche, die Wahrscheinlichkeiten basierend auf den E-Mails jedes einzelnen Benutzers berechnen. Diese können viel effektiver sein, nicht nur um falsch positive Ergebnisse zu vermeiden, sondern auch beim Filtern: Zum Beispiel ist es ein sehr guter Spam-Indikator, die E-Mail-Adresse des Empfängers irgendwo in einer Nachricht base-64-codiert zu finden.

Aber der wirkliche Vorteil individueller Filter ist, dass sie alle unterschiedlich sein werden. Wenn die Filter aller unterschiedlich hohe Wahrscheinlichkeiten haben, wird dies den Optimierungszyklus der Spammer, was Programmierer als ihren Edit-Compile-Test-Zyklus bezeichnen würden, erschreckend langsam machen. Anstatt einfach einen Spam zu optimieren, bis er durch eine Kopie eines Filters, den sie auf ihrem Desktop haben, durchkommt, müssen sie für jede Anpassung einen Testversand durchführen. Es wäre, als würde man in einer Sprache ohne interaktives Top-Level programmieren, und ich würde das niemandem wünschen.

Hinweise

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

Die Wahrscheinlichkeiten in diesem Algorithmus werden unter Verwendung eines degenerierten Falls von Bayes' 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 vorherige Wahrscheinlichkeit wissen, dass eine E-Mail Spam ist.

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

Die zweite Annahme habe ich gemacht, weil das Verhältnis von Spam zu Nicht-Spam in meinen eingehenden E-Mails von Tag zu Tag (tatsächlich von Stunde zu Stunde) so stark schwankte, dass das gesamte vorherige Verhältnis als Prädiktor wertlos erschien. Wenn Sie annehmen, dass P(spam) und P(nonspam) beide 0,5 sind, heben sie sich auf und Sie können sie aus der Formel entfernen.

Wenn Sie Bayes'sche Filterung in einer Situation durchführen, in der das Verhältnis von Spam zu Nicht-Spam konstant sehr hoch oder (insbesondere) sehr niedrig ist, könnten Sie die Filterleistung wahrscheinlich verbessern, indem Sie vorherige Wahrscheinlichkeiten einbeziehen. Um dies richtig zu machen, müssten Sie die Verhältnisse nach Tageszeit verfolgen, da sowohl Spam- als auch legitime E-Mail-Volumina unterschiedliche tägliche Muster aufweisen.

[2] Patrick Pantel und Dekang Lin. „SpamCop—Ein Spam-Klassifikations- und Organisationsprogramm.“ Proceedings of AAAI-98 Workshop on Learning for Text Categorization.

[3] Mehran Sahami, Susan Dumais, David Heckerman und Eric Horvitz. „Ein Bayes'scher Ansatz zur Filterung von Junk-E-Mails.“ Proceedings of AAAI-98 Workshop on Learning for Text Categorization.

[4] Zu diesem Zeitpunkt hatte ich null falsch positive Ergebnisse aus etwa 4000 legitimen E-Mails. Wenn die nächste legitime E-Mail ein falsch positives Ergebnis war, würde uns das 0,03 % geben. Diese Raten falsch positiver Ergebnisse sind unzuverlässig, wie ich später erkläre. Ich zitiere hier eine Zahl nur, um zu betonen, dass die Rate falsch positiver Ergebnisse, egal wie hoch sie ist, 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“ verwendete ich Schwellenwerte von 0,99 und 0,01. Es scheint gerechtfertigt zu sein, 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, wenn „Subjectfoo“ zu „foo“ degeneriert, bedeutet das, dass Sie die Statistiken für Vorkommen von „foo“ im Text oder in den Headerzeilen erhalten, die ich nicht markiere. Was ich tun sollte, ist, die Statistiken für „foo“ insgesamt sowie für spezifische Versionen zu verfolgen und von „Subjectfoo“ nicht zu „foo“, sondern zu „Anywhere*foo“ zu degenerieren. Gleiches gilt für die Groß- und Kleinschreibung: Ich sollte von Großbuchstaben zu beliebigen Buchstaben degenerieren, nicht zu Kleinbuchstaben.

Es wäre wahrscheinlich auch vorteilhaft, dies 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 das würde wahrscheinlich nur die Filterraten zu Beginn 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 dies bei der Vergleich von Techniken zur Bekämpfung von Spam berücksichtigen. Während viele der falsch positiven Ergebnisse, die durch Filter verursacht werden, nahe Spam sind, die Sie nicht stören würden, sind falsch positive Ergebnisse, die durch Blacklists verursacht werden, beispielsweise einfach E-Mails von Personen, die den falschen ISP gewählt haben. In beiden Fällen fangen Sie E-Mails, die nahe Spam sind, aber bei Blacklists ist die Nähe physisch, und bei Filtern ist sie textuell.

[10] Wenn Spammer gut genug darin werden, Tokens zu verschleiern, um dies zu einem Problem zu machen, 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 Finden von Wörtern auf diese Weise, die im ursprünglichen Text nicht sichtbar waren, an sich ein Beweis für Spam.

Das Herausfiltern der Wörter wird nicht trivial sein. Es wird mehr erfordern, als nur die Wortgrenzen wiederherzustellen; Spammer fügen sowohl Buchstaben hinzu („xHot nPorn cSite“) als auch Buchstaben weg („P#rn“). Die Forschung zur visuellen Wahrnehmung könnte hier nützlich sein, da die menschliche Wahrnehmung die Grenze ist, die solche Tricks erreichen werden.

[11] Im Allgemeinen sind Spams repetitiver als reguläre E-Mails. Sie wollen diese Nachricht eindringlich vermitteln. Ich erlaube derzeit keine Duplikate in den 15 wichtigsten Tokens, weil Sie ein falsch positives Ergebnis erhalten könnten, wenn der Absender zufällig ein schlechtes Wort mehrfach verwendet. (In meinem aktuellen Filter hat „dick“ eine Spam-Wahrscheinlichkeit von 0,9999, aber es ist auch ein Name.) Es scheint, dass wir zumindest Duplikate bemerken sollten, also könnte ich versuchen, bis zu zwei von jedem Token zuzulassen, wie Brian Burton es in SpamProbe tut.

[12] Dies ist das, was Ansätze wie Brightmail tun werden, wenn Spammer gezwungen werden, verrückte 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 normalerweise meinen, wenn sie das sagen, ist: Wir filtern derzeit auf Netzwerkebene, und wir wollen nicht von vorne anfangen. Aber Sie können das Problem nicht diktieren, um Ihre Lösung zu passen.

Historisch gesehen waren Argumente über knappe Ressourcen die unterlegene Seite in Debatten über Softwaredesign. Die Leute neigen nur dazu, sie 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 Papiers und an Dan erneut 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