BESSERE BAYES-FILTERUNG

Januar 2003

(Dieser Artikel wurde als Vortrag auf der Spam-Konferenz 2003 gehalten. Er beschreibt meine Arbeit zur Verbesserung der Leistung des in „Ein Plan gegen Spam“ beschriebenen Algorithmus und was ich in Zukunft vorhabe.)

Die erste Entdeckung, die ich hier vorstellen möchte, ist ein Algorithmus zur nachlässigen Bewertung von Forschungsarbeiten. Schreiben Sie einfach, was Sie wollen, und zitieren Sie keine früheren Arbeiten. Dann werden Ihnen empörte Leser Referenzen zu allen Arbeiten schicken, die Sie hätten zitieren sollen. Ich entdeckte diesen Algorithmus, nachdem „A Plan for Spam“ [1] auf Slashdot erschien.

Spam-Filterung ist ein Teilbereich der Textklassifizierung, einem gut etablierten Gebiet. Die ersten Arbeiten über Bayesianische Spam-Filterung an sich scheinen jedoch auf derselben Konferenz im Jahr 1998 erschienen zu sein, eine von Pantel und Lin [2] und eine andere von einer Gruppe von Microsoft Research [3].

Als ich von dieser Arbeit hörte, war ich etwas überrascht. Wenn die Leute schon vor vier Jahren auf Bayesianische Filter gestoßen waren, warum haben sie dann nicht alle verwendet? Als ich die Artikel las, fand ich heraus, warum. Der Filter von Pantel und Lin war der effektivere der beiden, aber er fing nur 92 % des Spams ab, und es gab 1,16 % Falschmeldungen.

Als ich versuchte, einen Bayes’schen Spamfilter zu schreiben, fing dieser 99,5% des Spams ab und hatte weniger als 0,03% Falschmeldungen [4]. Es ist immer beunruhigend, wenn zwei Leute, die das gleiche Experiment durchführen, zu sehr unterschiedlichen Ergebnissen kommen. In diesem Fall ist es besonders beunruhigend, weil diese beiden Zahlenreihen zu entgegengesetzten Schlussfolgerungen führen können. Unterschiedliche Benutzer haben unterschiedliche Anforderungen, aber ich denke, für viele Leute bedeutet eine Filterrate von 92% mit 1,16% Falschmeldungen, dass Filtern keine akzeptable Lösung ist, während 99,5% mit weniger als 0,03% Falschmeldungen bedeuten, dass es eine akzeptable Lösung ist.

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

Einer ist einfach, dass sie ihren Filter mit sehr wenigen Daten trainiert haben: 160 Spam-Mails 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 Maß für die Leistung ihres Algorithmus, geschweige denn für Bayesian Spam-Filter im Allgemeinen.

Aber ich denke, der wichtigste Unterschied ist wahrscheinlich, dass sie die Nachrichtenkopfzeilen ignoriert haben. Für jeden, der schon einmal an Spamfiltern gearbeitet hat, wird dies eine perverse Entscheidung sein. Und doch habe ich bei den allerersten Filtern, die ich zu schreiben versuchte, auch die Kopfzeilen ignoriert. Warum? Weil ich das Problem übersichtlich halten wollte. Ich wusste damals nicht viel über E-Mail-Kopfzeilen und sie schienen mir voller zufälliger Dinge zu sein. Für Filterautoren gibt es hier eine Lektion: Ignorieren Sie keine Daten. Man könnte meinen, diese Lektion sei zu offensichtlich, um sie zu erwähnen, aber ich musste sie mehrmals lernen.

Drittens haben Pantel und Lin die Token gestielt, d. h. sie haben z. B. sowohl mailing'' and „mailed“ auf die Wurzel „mail“ reduziert. Möglicherweise haben sie sich durch die geringe Größe ihres Korpus dazu gezwungen gefühlt, aber wenn das so ist, ist das eine Art vorzeitige Optimierung.

Viertens berechneten sie die Wahrscheinlichkeiten anders. Sie verwendeten alle Token, während ich nur die 15 wichtigsten verwende. Wenn Sie alle Token verwenden, werden Sie längere Spams eher übersehen, beispielsweise solche, in denen Ihnen jemand seine Lebensgeschichte erzählt, bis er durch ein Multi-Level-Marketing-System reich wurde. Und ein solcher Algorithmus wäre für Spammer leicht zu fälschen: Sie müssen nur einen großen Block zufälligen Textes hinzufügen, um die Spam-Begriffe auszugleichen.

Und schließlich haben sie keine Voreingenommenheit gegenüber falschen Positivmeldungen gezeigt. Ich denke, jeder Spamfilteralgorithmus sollte einen praktischen Knopf haben, mit dem man die Rate falscher Positivmeldungen auf Kosten der Filterrate senken kann. Ich mache das, indem ich die Vorkommen von Tokens im Nichtspamkorpus doppelt zähle.

Ich halte es nicht für eine gute Idee, Spamfilterung als reines Textklassifizierungsproblem zu behandeln. Sie können Textklassifizierungstechniken verwenden, aber Lösungen können und sollten die Tatsache berücksichtigen, dass es sich bei dem Text um E-Mail und insbesondere um Spam handelt. E-Mail ist nicht nur Text; sie hat Struktur. Spamfilterung ist nicht nur Klassifizierung, denn falsch positive Ergebnisse sind so viel schlimmer als falsch negative, dass Sie sie als eine andere Art von Fehler behandeln sollten. Und die Fehlerquelle sind nicht nur zufällige Variationen, sondern ein echter menschlicher Spammer, der aktiv daran arbeitet, Ihren Filter zu überwinden.

Token

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 handelt sich um einen reinen Textklassifizierer, der jedoch so erstaunlich effektiv ist, dass er Spam nahezu perfekt filtert, ohne dass die Benutzer dies überhaupt merken.

Nachdem ich verstanden hatte, wie CRM114 funktionierte, schien es unvermeidlich, dass ich irgendwann von der Filterung auf Basis einzelner Wörter zu einem Ansatz wie diesem wechseln musste. 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 einer intelligenteren Tokenisierung gearbeitet. Bei aktuellem Spam konnte ich Filterraten erreichen, die denen von CRM114 nahe kommen. Diese Techniken sind größtenteils orthogonal zu denen von Bill; eine optimale Lösung könnte beides beinhalten.

„Ein Plan gegen Spam“ verwendet eine sehr einfache Definition eines Tokens. Buchstaben, Ziffern, Bindestriche, Apostrophe und Dollarzeichen sind Bestandteile, und alles andere ist ein Token-Trennzeichen. Ich habe auch die Groß- und Kleinschreibung ignoriert.

Jetzt habe ich eine kompliziertere Definition eines Tokens:

Gehäuse ist erhalten.

Ausrufezeichen sind Bestandteilszeichen.

Punkte und Kommas sind Bestandteile, wenn sie zwischen zwei Ziffern stehen. So erhalte ich IP-Adressen und Preise unverändert.

Bei einem Preisbereich von beispielsweise 20–25 $ erhält man zwei Token: 20 $ und 25 $.

Token, die in den Zeilen „An“, „Von“, „Betreff“ und „Rücksendepfad“ oder innerhalb von URLs vorkommen, werden entsprechend markiert. Beispielsweise foo'' in the Subject line becomes Betreff*foo“. (Das Sternchen kann jedes beliebige Zeichen sein, das Sie als Bestandteil nicht zulassen.)

Solche Maßnahmen erweitern das Vokabular des Filters und machen ihn dadurch differenzierter. Im aktuellen Filter beispielsweise hat „kostenlos“ in der Betreffzeile eine Spamwahrscheinlichkeit von 98 %, während das gleiche Token im Text nur eine Spamwahrscheinlichkeit von 65 % hat.

Hier sind einige der aktuellen Wahrscheinlichkeiten [6]:

Betreff KOSTENLOS 0,9999 frei!! 0,9999 Bis frei 0,9998 Betreff frei 0,9782 frei! 0,9199 Frei 0,9198 URL frei 0,9091 KOSTENLOS 0,8747 Von*frei 0,7636 frei 0,6546

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

Der Nachteil eines größeren Tokenuniversums besteht darin, dass die Wahrscheinlichkeit von Fehlschlägen größer ist. Das Verteilen Ihres Korpus auf mehr Token hat denselben Effekt wie das Verkleinern. Wenn Sie beispielsweise Ausrufezeichen als Bestandteile betrachten, kann es passieren, dass Sie bei sieben Ausrufezeichen für „kostenlos“ keine Spamwahrscheinlichkeit haben, obwohl Sie wissen, dass „kostenlos“ bei nur zwei Ausrufezeichen eine Wahrscheinlichkeit von 99,99 % hat.

Eine Lösung hierfür ist das, was ich Degeneration nenne. Wenn Sie keine genaue Entsprechung für ein Token finden, behandeln Sie es, als wäre es eine weniger spezifische Version. Ausrufezeichen am Ende, Großbuchstaben und das Auftreten in einem der fünf markierten Kontexte betrachte ich als etwas, das ein Token spezifischer macht. Wenn ich beispielsweise keine Wahrscheinlichkeit für Subject*free!'', I look for probabilities for Subjekt*frei!“, free!'', and „frei!“ und nehme diejenige, die am weitesten von 0,5 entfernt ist.

Hier sind die Alternativen [7], die berücksichtigt werden, wenn der Filter ``KOSTENLOS!!!'' in der Betreffzeile sieht und keine Wahrscheinlichkeit dafür hat.

Betreff kostenlos!!! Betreff kostenlos!!! Betreff KOSTENLOS! Betreff kostenlos! Betreff kostenlos! Betreff KOSTENLOS Betreff kostenlos Betreff kostenlos KOSTENLOS!!! Kostenlos!!! kostenlos!!! KOSTENLOS! Kostenlos! kostenlos! KOSTENLOS Kostenlos kostenlos

Wenn Sie dies tun, achten Sie darauf, dass Sie sowohl Versionen mit Großbuchstaben als auch Versionen mit Kleinbuchstaben berücksichtigen. Spams enthalten tendenziell mehr Sätze im Imperativ, und bei diesen ist das erste Wort ein Verb. Daher ist die Spamwahrscheinlichkeit bei Verben mit Großbuchstaben höher als bei Verben mit Kleinbuchstaben. In meinem Filter Act'' is 98% and for „act“ nur 62 %.

Wenn Sie den Wortschatz Ihres Filters erweitern, kann es passieren, dass Sie dasselbe Wort mehrfach zählen, gemäß Ihrer alten Definition von „gleich“. Logischerweise sind sie nicht mehr dasselbe Token. Aber wenn Sie das immer noch stört, lassen Sie mich aus Erfahrung hinzufügen, dass die Wörter, die Sie scheinbar mehrfach zählen, in der Regel genau die sind, die Sie zählen möchten.

Ein weiterer Effekt eines größeren Vokabulars ist, dass Sie beim Betrachten einer eingehenden E-Mail interessantere Token finden, also solche mit Wahrscheinlichkeiten weit von 0,5. Ich verwende die 15 interessantesten, um zu entscheiden, ob es sich bei einer E-Mail um Spam handelt. Aber Sie können auf ein Problem stoßen, wenn Sie eine feste Zahl wie diese verwenden. Wenn Sie viele maximal interessante Token finden, kann das Ergebnis letztendlich von dem Zufallsfaktor bestimmt werden, der die Reihenfolge der gleichermaßen interessanten Token bestimmt. Eine Möglichkeit, damit umzugehen, besteht darin, einige als interessanter zu behandeln als andere.

Beispielsweise dalco'' occurs 3 times in my spam corpus and never in my legitimate corpus. The token Url*optmails“ (was „optmails“ innerhalb einer URL bedeutet) kommt 1223 Mal vor. Und dennoch hätten beide, so wie ich die Wahrscheinlichkeiten für Token berechnet habe, dieselbe Spam-Wahrscheinlichkeit, nämlich den Grenzwert von 0,99.

Das fühlt sich nicht richtig an. Es gibt theoretische Argumente dafür, diesen beiden Tokens deutlich unterschiedliche Wahrscheinlichkeiten zuzuweisen (Pantel und Lin tun das), aber das habe ich noch nicht ausprobiert. Es scheint zumindest so, dass wir, wenn wir mehr als 15 Tokens finden, die nur in dem einen oder anderen Korpus vorkommen, denjenigen Priorität einräumen sollten, die häufig vorkommen. Es gibt also jetzt 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, wenn sie nicht häufiger vorkommen. Das Gleiche gilt am anderen Ende der Skala für Tokens, die nur im legitimen Korpus vorkommen.

Ich werde die Token-Wahrscheinlichkeiten später vielleicht erheblich skalieren, aber diese geringe Skalierung stellt zumindest sicher, dass die Token richtig sortiert werden.

Eine andere Möglichkeit wäre, nicht nur 15 Token zu berücksichtigen, sondern alle Token, die einen bestimmten Schwellenwert an Interessantheit überschreiten. Steven Hauser tut dies in seinem statistischen Spamfilter [8]. Wenn Sie einen Schwellenwert verwenden, legen Sie ihn sehr hoch an, sonst könnten Spammer Sie täuschen, indem sie Nachrichten mit noch harmloseren Wörtern füllen.

Und was sollte man schließlich mit HTML machen? Ich habe alle möglichen Optionen ausprobiert, vom Ignorieren bis zum kompletten Parsen. HTML zu ignorieren ist keine gute Idee, weil es voller nützlicher Spam-Zeichen ist. Aber wenn Sie alles parsen, könnte Ihr Filter zu einem bloßen HTML-Erkenner verkommen. Der effektivste Ansatz scheint der Mittelweg zu sein, bei dem einige Tokens erkannt werden, andere jedoch nicht. Ich sehe mir die Tags a, img und font an und ignoriere den Rest. Links und Bilder sollten Sie sich auf jeden Fall ansehen, weil sie URLs enthalten.

Ich könnte wahrscheinlich klüger mit HTML umgehen, aber ich glaube nicht, dass es sich lohnt, viel Zeit darauf zu verwenden. Spams voller HTML lassen sich leicht filtern. Die klügeren Spammer vermeiden sie bereits. Die Leistung sollte in Zukunft also nicht mehr so sehr 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 entspricht einer Filterrate von etwa 99,75 %.

Zwei der vier Spam-Mails, die ich übersehen habe, sind durchgekommen, weil sie zufällig Wörter enthielten, 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 nur schwer anhand des Inhalts zu filtern, da die Header harmlos sind und sie auf die verwendeten Wörter achten. Trotzdem kann ich sie normalerweise erwischen. Dieser hier ist mit einer Wahrscheinlichkeit von 0,88 knapp unter dem Grenzwert von 0,9 durchgekommen.

Natürlich lässt sich dies leicht erkennen, wenn man sich mehrere Token-Sequenzen ansieht. „Nachfolgend sehen Sie das Ergebnis Ihres Feedback-Formulars“ ist ein sofortiges Indiz.

Den vierten Spam nenne ich Spam der Zukunft, denn so wird sich Spam meiner Meinung nach entwickeln: ein völlig neutraler Text, gefolgt von einer URL. In diesem Fall kam er von jemandem, der sagte, er hätte endlich seine Homepage fertiggestellt und würde mich bitten, sie mir mal anzusehen. (Die Seite war natürlich eine Anzeige für eine Pornoseite.)

Wenn die Spammer bei den Headern vorsichtig sind und eine neue URL verwenden, gibt es im Spam der Zukunft nichts, was die Filter bemerken könnten. Wir können natürlich dagegen vorgehen, indem wir einen Crawler losschicken, der sich die Seite ansieht. Aber das ist vielleicht gar nicht nötig. Die Antwortrate für Spam der Zukunft muss niedrig sein, sonst würde es jeder tun. Wenn sie niedrig genug ist, lohnt es sich für Spammer nicht , ihn zu versenden, und wir müssen uns nicht allzu viel Mühe mit der Filterung geben.

Und jetzt die wirklich schockierende Nachricht: Im selben Monat erhielt ich drei falsche Positivergebnisse.

In gewisser Weise ist es eine Erleichterung, ein paar falsche Positivmeldungen zu erhalten. Als ich „A Plan for Spam“ schrieb, hatte ich noch keine und wusste auch nicht, wie sie aussehen würden. Nachdem ich nun ein paar davon erhalten habe, bin ich erleichtert, dass sie nicht so schlimm sind, wie ich befürchtet hatte. Falschmeldungen, die von statistischen Filtern ausgegeben werden, entpuppen sich als Mails, die sehr nach Spam klingen, und das sind in der Regel die, die man am wenigsten stört, wenn man sie übersieht [9].

Zwei der Fehlalarme waren Newsletter von Unternehmen, bei denen ich Dinge gekauft habe. Ich hatte nie darum gebeten, sie zu erhalten, also waren sie wohl Spam, aber ich zähle sie zu den Fehlalarmen, weil ich sie vorher nicht als Spam gelöscht hatte. Der Grund, warum die Filter sie abgefangen haben, war, dass beide Unternehmen im Januar auf kommerzielle E-Mail-Absender umgestiegen waren, anstatt die Mails von ihren eigenen Servern zu versenden, und sowohl die Header als auch die Nachrichtentexte viel spammiger wurden.

Der dritte Fehlalarm war allerdings schlimm. Er kam von jemandem aus Ägypten und war komplett in Großbuchstaben geschrieben. Das war eine direkte Folge der Groß- und Kleinschreibung der Token; der Spamfilter von Plan for Spam hätte ihn nicht erkannt.

Es ist schwer zu sagen, wie hoch die Gesamtrate falscher Positivmeldungen ist, da wir statistisch gesehen mitten im Rauschen stecken. Jeder, der schon einmal mit Filtern gearbeitet hat (zumindest mit effektiven Filtern), kennt dieses Problem. Bei manchen E-Mails ist es schwer zu sagen, ob es sich um Spam handelt oder nicht, und diese E-Mails werden Ihnen letztendlich angezeigt, wenn Sie die Filter wirklich streng einstellen. Bisher hat der Filter beispielsweise zwei E-Mails abgefangen, die aufgrund eines Tippfehlers an meine Adresse gesendet wurden, und eine, die in dem Glauben an mich gesendet wurde, ich sei jemand anderes. Man könnte argumentieren, dass dies weder mein Spam noch meine Nicht-Spam-Mails sind.

Ein weiterer falscher Positivbefund kam von einem Vizepräsidenten bei Virtumundo. Ich schrieb ihnen als Kunde und da die Antwort über die Mailserver von Virtumundo zurückkam, hatte sie die belastendsten Header, die man sich vorstellen kann. Man könnte argumentieren, dass dies auch kein echter falscher Positivbefund ist, sondern eine Art Heisenbergscher Unschärfeeffekt: Ich habe ihn nur erhalten, weil ich über Spamfilterung geschrieben habe.

Abgesehen davon hatte ich bisher insgesamt fünf Fehlalarme bei etwa 7740 legitimen E-Mails, eine Quote von 0,06 %. Die anderen beiden waren eine Benachrichtigung, dass etwas, das ich gekauft hatte, nachbestellt werden musste, 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 einstellen kann, dass er einige davon nicht erfasst.

Falschpositive scheinen mir eine andere Art von Fehler zu sein als falschnegative. Die Filterrate ist ein Maß für die Leistung. Falschpositive betrachte ich eher als Fehler. Die Verbesserung der Filterrate betrachte ich als Optimierung und die Verringerung falschpositiver Ergebnisse als Debugging.

Diese fünf Fehlalarme sind also meine Fehlerliste. Die E-Mail aus Ägypten wurde beispielsweise erkannt, weil sie aufgrund des großgeschriebenen Textes für den Filter wie nigerianischer Spam aussah. Das ist wirklich ein Fehler. Wie bei HTML ist die Großschreibung der E-Mail konzeptionell ein Merkmal, nicht eines für jedes Wort. Ich muss die Groß- und Kleinschreibung auf eine ausgefeiltere Weise handhaben.

Was also ist mit diesen 0,06 % zu tun? Nicht viel, denke ich. Man könnte es als Obergrenze betrachten, wenn man die kleine Stichprobengröße bedenkt. Aber in diesem Stadium ist es eher ein Maß für die Fehler in meiner Implementierung als eine inhärente Falsch-Positiv-Rate der Bayes-Filterung.

Zukunft

Was kommt als Nächstes? Filtern 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. Sehen Sie sich an, wo Ihr Code langsam ist, und beheben Sie das. Beim Filtern bedeutet dies: Sehen Sie sich die Spams an, die Sie übersehen, und finden Sie heraus, was Sie hätten tun können, um sie abzufangen.

Spammer beispielsweise versuchen mittlerweile aggressiv, Filter zu umgehen. Sie zerlegen Wörter und schreiben sie falsch, damit sie von den Filtern nicht mehr erkannt werden. Daran zu arbeiten hat für mich allerdings nicht die höchste Priorität, da ich diese Spams immer noch problemlos abfangen kann [10].

Es gibt zwei Arten von Spam, 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-Site 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 Spam, die ich nur schwer filtern kann, sind die von Unternehmen aus Bulgarien, die beispielsweise Programmierdienste auf Vertragsbasis anbieten. Diese kommen durch, weil ich auch Programmierer bin und die Spams voller derselben Wörter sind wie meine echten Mails.

Ich werde mich wahrscheinlich zuerst auf die Art der persönlichen Anzeige konzentrieren. Ich denke, wenn ich genauer hinschaue, kann ich statistische Unterschiede zwischen diesen und meiner echten E-Mail feststellen. Der Schreibstil ist sicherlich anders, aber um das zu erkennen, ist möglicherweise eine Filterung nach mehreren Wörtern erforderlich. Außerdem fällt mir auf, dass sie dazu neigen, die URL zu 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 fassen sein. Selbst wenn man einen Crawler auf die Site schickt, findet man keine stichhaltigen statistischen Beweise. Vielleicht ist die einzige Lösung eine zentrale Liste der in Spams beworbenen Domains [12]. Aber von dieser Art von Mails kann es nicht so viele geben. Wenn die einzigen Spams, die übrig blieben, unaufgeforderte Angebote für Vertragsprogrammierdienste aus Bulgarien wären, könnten wir uns wahrscheinlich alle anderen Dingen zuwenden.

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

Ich bin nicht optimistisch, was Filter angeht, 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 eine Firma namens Assurance Systems, die Ihre E-Mails durch Spamassassin laufen lässt und Ihnen sagt, ob sie herausgefiltert werden.

Filter auf Netzwerkebene sind nicht völlig nutzlos. Sie reichen möglicherweise aus, um allen „Opt-in“-Spam zu töten, also Spam von Unternehmen wie Virtumundo und Equalamail, die behaupten, dass sie tatsächlich Opt-in-Listen betreiben. Sie können diese nur anhand der Header filtern, unabhängig davon, was im Text steht. Aber jeder, der bereit ist, Header zu fälschen oder offene Relays zu verwenden, vermutlich einschließlich der meisten Porno-Spammer, sollte in der Lage sein, einige Nachrichten an den Filtern auf Netzwerkebene vorbeizubekommen, wenn er das möchte. (Allerdings auf keinen Fall die Nachricht, die sie senden möchten, was immerhin schon mal was ist.)

Ich bin optimistisch, was Filter angeht, die Wahrscheinlichkeiten auf Grundlage der E-Mails jedes einzelnen Benutzers berechnen. Diese können viel effektiver sein, nicht nur bei der Vermeidung falscher Positivmeldungen, sondern auch beim Filtern: Wenn beispielsweise die E-Mail-Adresse des Empfängers irgendwo in einer Nachricht Base-64-kodiert ist, ist das ein sehr guter Spam-Indikator.

Der wirkliche Vorteil individueller Filter besteht jedoch darin, dass sie alle unterschiedlich sind. Wenn jeder Filter unterschiedliche Wahrscheinlichkeiten hat, wird die Optimierungsschleife der Spammer, die Programmierer als Editier-Kompilier-Test-Zyklus bezeichnen würden, erschreckend langsam. Anstatt einfach eine Spam-Mail so lange zu optimieren, bis sie durch eine Kopie eines Filters auf ihrem Desktop kommt, müssen sie für jede Optimierung eine Testmail versenden. Das wäre wie das Programmieren in einer Sprache ohne interaktive Toplevel, und das würde ich niemandem wünschen.

Hinweise

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

Die Wahrscheinlichkeiten in diesem Algorithmus werden mithilfe eines degenerierten Falls des Bayes-Prinzips berechnet. Dabei gibt es zwei vereinfachende Annahmen: dass die Wahrscheinlichkeiten von Merkmalen (also Wörtern) unabhängig sind und dass wir nichts über die Vorwahrscheinlichkeit wissen, dass es sich bei einer E-Mail um Spam handelt.

Die erste Annahme ist bei der Textklassifizierung weit verbreitet. Algorithmen, die sie verwenden, werden als „naive Bayesianer“ bezeichnet.

Die zweite Annahme habe ich getroffen, weil der Spam-Anteil in meinen eingehenden E-Mails von Tag zu Tag (tatsächlich von Stunde zu Stunde) so stark schwankte, dass das vorherige Gesamtverhältnis als Prädiktor wertlos erschien. Wenn Sie davon ausgehen, dass P(Spam) und P(Nichtspam) beide 0,5 betragen, heben sie sich gegenseitig auf und Sie können sie aus der Formel entfernen.

Wenn Sie Bayesian-Filter in einer Situation anwenden, in der das Verhältnis von Spam zu Nicht-Spam konstant sehr hoch oder (vor allem) sehr niedrig ist, könnten Sie die Filterleistung wahrscheinlich verbessern, indem Sie Vorwahrscheinlichkeiten einbeziehen. Um dies richtig zu machen, müssten Sie die Verhältnisse nach Tageszeit verfolgen, da das Spam- und das legitime E-Mail-Volumen jeweils unterschiedliche tägliche Muster aufweisen.

[2] Patrick Pantel und Dekang Lin. „SpamCop – Ein Programm zur Klassifizierung und Organisation von Spam.“ Proceedings des AAAI-98-Workshops zum Thema Lernen zur Textkategorisierung.

[3] Mehran Sahami, Susan Dumais, David Heckerman und Eric Horvitz. „Ein Bayesianischer Ansatz zum Filtern von Junk-E-Mails.“ Proceedings des AAAI-98-Workshops zum Lernen für die Textkategorisierung.

[4] Zu diesem Zeitpunkt hatte ich bei etwa 4.000 legitimen E-Mails null False Positives. Wenn die nächste legitime E-Mail ein False Positive wäre, käme man auf 0,03 %. Diese False-Positive-Raten sind nicht vertrauenswürdig, wie ich später erkläre. Ich nenne hier nur eine Zahl, um zu betonen, dass die False-Positive-Rate, wie hoch sie auch sein mag, weniger als 1,16 % beträgt.

[5] Bill Yerazunis. „Sparse Binary Polynomial Hash Message Filtering und der CRM114-Diskriminator.“ Proceedings der Spam-Konferenz 2003.

[6] In „A Plan for Spam“ habe ich Schwellenwerte von 0,99 und 0,01 verwendet. Es erscheint gerechtfertigt, Schwellenwerte zu verwenden, die proportional zur Größe der Korpora sind. Da ich jetzt ungefähr 10.000 E-Mails jeder Art habe, verwende ich 0,9999 und 0,0001.

[7] Hier gibt es einen Fehler, den ich wahrscheinlich beheben sollte. Wenn derzeit Subject*foo'' degenerates to just , bedeutet das, dass Sie die Statistiken für Vorkommen von foo'' in the body or header lines other than those I mark. What I should do is keep track of statistics for und von Subject*foo'' not to „foo''“, sondern zu „Anywhere*foo''“ zu degenerieren. Das Gleiche gilt für die Groß- und Kleinschreibung: Ich sollte von Großbuchstaben zu beliebigen Groß- und Kleinschreibung degenerieren, nicht zu Kleinbuchstaben.

Wahrscheinlich wäre es ein Gewinn, dies auch mit den Preisen zu tun, z. B. von $129.99'' to --9,99 $, $--.99'', and -- $ herabzustufen.

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

[8] Steven Hauser. „Statistischer Spamfilter funktioniert bei mir.“ http://www.sofbot.com.

[9] Falsche Positivmeldungen sind nicht alle gleich, und das sollten wir im Hinterkopf behalten, wenn wir Techniken zum Stoppen von Spam vergleichen. Während viele der durch Filter verursachten Falschmeldungen Beinahe-Spam sind, den man gerne übersehen würde, sind beispielsweise durch Blacklists verursachte Falschmeldungen einfach nur Mails von Leuten, die den falschen ISP gewählt haben. In beiden Fällen fangen Sie Mails ab, die Beinahe-Spam sind, aber bei Blacklists ist die Nähe physisch und bei Filtern textuell.

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

Das Herausfinden der Wörter wird nicht trivial sein. Es wird mehr erfordern, als nur Wortgrenzen zu rekonstruieren; Spammer fügen sowohl Buchstaben hinzu ( xHot nPorn cSite'') and omit ( P#rn''). Die Untersuchung des Sehvermögens könnte hier hilfreich sein, da das menschliche Sehvermögen die Grenze darstellt, an die solche Tricks stoßen.

[11] Im Allgemeinen sind Spams repetitiver als normale E-Mails. Sie wollen die Botschaft einhämmern. Ich erlaube derzeit keine Duplikate in den Top 15 Tokens, da man ein falsches Positiv erhalten könnte, wenn der Absender zufällig ein Schimpfwort mehrfach verwendet. (In meinem aktuellen Filter hat „dick“ eine Spamwahrscheinlichkeit von 0,9999, aber es ist auch ein Name.) Es scheint uns jedoch, dass wir Duplikate zumindest bemerken sollten, also werde ich vielleicht versuchen, bis zu zwei von jedem Token zuzulassen, wie es Brian Burton in SpamProbe tut.

[12] Zu diesem Szenario werden Ansätze wie der von Brightmail verkommen, wenn Spammer erst einmal dazu gezwungen werden, Mad-Lib-Techniken zu verwenden, um alles andere in der Nachricht zu generieren.

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

In der Vergangenheit waren Argumente über knappe Ressourcen bei Debatten über Softwaredesign immer die Verlierer. Man neigt dazu, sie nur zu verwenden, um Entscheidungen (insbesondere Untätigkeit) zu rechtfertigen, die aus anderen Gründen getroffen wurden.

Unser Dank geht an Sarah Harlin, Trevor Blackwell und Dan Giffin für das Lesen der Entwürfe dieses Dokuments und nochmals an Dan für den Großteil der Infrastruktur, auf der dieser Filter läuft.

Verwandt:

Betreff KOSTENLOS 0,9999 frei!! 0,9999 Bis frei 0,9998 Betreff frei 0,9782 frei! 0,9199 Frei 0,9198 URL frei 0,9091 KOSTENLOS 0,8747 Von*frei 0,7636 frei 0,6546