Programmiertechnik/Bayesscher Kommentarspam-Filter

Aus SELFHTML-Wiki
Wechseln zu: Navigation, Suche

Konzepte von Spamfiltern

Nach den E-Mails haben in letzter Zeit auch die Weblogs mit ihrer Kommentarfunktion die Aufmerksamkeit der Spammer auf sich gezogen – sehr zum Leidwesen der Blogger. Diese müssen sich nämlich regelmäßig um die Entsorgung des angestauten Mülls kümmern. Die Motive sind die gleichen wie bei den E-Mails: Man kann mit wenig Aufwand tausende Kommentare absetzen und damit zehntausende Nutzer bewerben.

Gegenmaßnahmen müssen her, Antispam-Plugins für Weblogs sprießen wie Pilse aus dem Bierfass, hier sollen einige Konzepte und ihre Vor- und Nachteile dargestellt werden.

CAPTCHAs, die kleinen Bilder mit verzerrten Buchstaben, die die Benutzer abtippen sollen, um die Erlaubnis zum Kommentieren zu erhalten sind vielleicht die häufigste Anti-Spam-Maßnahme. Nichtsdestotrotz hindert sie Sehbehinderte an der Teilnahme, nervt die erwünschten Benutzer und es gibt seitens der Spammer bereits diverse Gegenmaßnahmen.

Eine entschärfte Version der CAPTCHA sind kleine Fragen oder Rechenaufgaben, die von Menschen problemlos, von Computern aber nur sehr schwierig allgemein gelöst werden können. Woher soll der Spambot auch wissen, der wievielte Monat der Januar ist? Wahre Programmierer geben hier vielleicht 0 an, aber das ist ein anderes Problem und soll ein anderes Mal gelöst werden.

Manchmal werden den Eingabefeldern zufällige Namen gegeben und dann überprüft, ob die E-Mail-Adresse ein @ enthält oder ob das Feld für die Website eine gültige URL enthält. Dabei gibt man aber den Komfort des automatischen Vorausfüllens durch den Browser auf; diese Methode wird also die Stammleser verschrecken.

Eine weitere Möglichkeit ist das Einfügen von Eingabefeldern, die mit CSS wieder ausgeblendet werden und daher von Benutzern nicht bemerkt werden. Viele Spam-Bots füllen einfach alle gefundenen Eingabefelder aus und fallen damit durch diesen Turing-Test. Leider gibt schon wieder Bots, die CSS interpretieren. Die dafürt notwendige CSS-Engine können sich die Spammer schließlich ganz bequem bei freien Browsern abkupfern.

Spammer entwickeln also immer wieder Methoden und Software, um die technischen Hürden der Anti-Spam-Fraktion zu umgehen, woraufhin sich letztere wieder neue Gegenmaßnahmen ausdenken muss. Was liegt also näher, als das Beobachten, Analysieren und Gegensteuern der neusten Spam-Angriffe einem trainierbaren Filter zu überlassen? Bei E-Mails haben Filter auf Basis des Bayestheorems bereits ihre Schlagkraft bewiesen, warum nicht also auch bei Weblogkommentaren?

Der Witz an den Bayes'schen Filtern ist, dass sie Entscheidungen aufgrund von Statistiken über Eigenschaften der Kommentare treffen. So ist es durchaus üblich, dass das Feld für die Website eine URL enthält, die mit HTTP beginnt oder leer ist. Der Kommentartext selbst enthält aber oft keine oder nur wenige URLs. Spammer versuchen häufig viele URLs gleichzeitig zu bewerben und zeichnen diese auch noch mittels HTML aus. Damit liefern sich direkt selbst ans Messer, die Zeichenketten "href=http", "[URL=http", "href='http", "org/sex'>sex</a>" sind in nach meinen Statistiken praktisch eindeutige Indizien für einen Spam-Kommentar.

Um nun den Spam trotzdem eintragen zu können, müssten die Spammer sowohl typische Spam-Wörter vermeiden als auch typische Wörter aus erwünschten Kommentaren verwenden. Da Kommentarspam im Moment fast nur aus URLs besteht müssten sie also ständig die URLs bzw. die Domains wechseln. Ersteres bringt nichts, wenn der Filter URLs zerlegt und Domain und Pfad getrennt behandelt. Letzteres würde zwar kurzfristig helfen wäre aber langfristig viel zu teuer und aufwändig. Um den Filter trotzdem zu täuschen könnten Spammer die Website spidern und herauszufinden, welche Wörter am häufigsten in Kommentaren verwendet werden. Diese Vorgehensweise würde aber unverhältnismäßig viel Rechenleistung und Speicherplatz verbraten und den Spam-Durchsatz in den Keller bringen.

Deutschsprachige Blogs haben den Vorteil, dass die allermeisten erwünschten Kommentare auf Deutsch sind, im Gegensatz zu den englischen Spam-Kommentaren. Das ergibt einen fast vollkommen anderen Wortschatz als den des Spams und erleichtert das Filtern sehr. Andererseits hat man den Nachteil dass erwünschte englische Kommentare für den Filter eventuell zu sehr nach Spam aussehen. Ganz so schlimm, wie es sich anhört ist es aber doch nicht: In meinen Tests mit meinen E-Mails bekam ich jedenfalls nur deutsche falsch positive, keine englischen falsch negativen Einstufungen.

Bayestheorem

Das Bayestheorem, auch Satz von Bayes genannt bietet die Formel für die Berechnung der Wahrscheinlichkeit eines Ereignisses A – in diesem Fall dass ein Kommentar von einem Spammer stammt – unter der Voraussetzung, dass vorher ein Ereignis B stattgefunden hat

Mathematische Formulierung des Bayestheorems

Lies: "Die Wahrscheinlichkeit, dass ein Ereignis A eintritt, wenn vorher ein Ereignis B eingetreten ist ist das Produkt der Wahrscheinlichkeit, dass B eintritt, wenn vorher A eingetreten ist und der Wahrscheinlichkeit, dass A auftritt geteilt durch die Wahrscheinlichkeit, dass B auftritt."

Dieser Satz ist die Umkehrung der bedingten Wahrscheinlichkeit: Man schließt von der Wahrscheinlichkeit, dass Spam-Kommentar ein bestimmtes Wort enthält auf die Wahrscheinlichkeit, dass ein Kommentar der dieses Wort enthält Spam ist.

Sei NC die Anzahl der Kommentare in der Kategorie C und NC,i die Anzahl der Kommentare in der Kategorie C, die das Wort wi enthalten. Dann ist die Wahrscheinlichkeit, dass ein zufällig gewählter Text aus der Kategorie C das Wort wi enthält

P(C, i) = N_C,i / N_C

Die Wahrscheinlichkeit, dass ein Kommentar die Wörter w1,w2,...,wn enthält, berechnet man unter der naiven Annahme, dass das Auftreten eines bestimmten Wortes unabhängig von dem Auftreten aller anderen Wörter ist. Somit gilt:

pwwwn

Lies: Die Wahrscheinlichkeit, dass ein Kommentar der Kategorie C die Wörter w1, w2 ... wi enthält, ist gleich das Produkt aller Einzelwahrscheinlichkeiten.

Jetzt wird für beide Kategorien die Umkehrung der bedingten Wahrscheinlichkeit berechnet:

Screenshot Screenshot

Zuletzt wird die Spam- mit der Ham-Wahrscheinlichkeit verglichen, indem der Quotient gebildet wird. Man erhält einen Vergleichswert V. Wenn dieser größer als eins ist, hat man es wahrscheinlich mit einem Spam-Kommentar, wenn er kleiner ist mit einem Ham-Kommentar zu tun. Ein Vergleichswert von eins lässt keine Aussage zu.

Probleme bei der Implementierung

Mit der Formel kann man sofort anfangen, Vergleichswerte berechnen zu lassen. Man wird aber unter Umständen unzuverlässige Ergebnisse bekommen, weil das Produkt vieler Wahrscheinlichkeiten betragsmäßig zu klein ist, als dass man es als 64Bit Gleitkommazahl dargestellen könnte. Eine Möglichkeit wäre nun die Speicherung in Zeichenketten von 5KB Länge, aber da der resultierende Vergleichswert nur auf drei oder vier Stellen genau bekannt sein muss suchen wir einen eleganteren Weg.

Hier helfen uns die Logarithmengesetze. Diese besagen unter anderem, dass der Logarithmus des Quotienten zweier Zahlen der Differenz der Logarithmen beider Zahlen entspricht. Analog gilt das für den Logarithmus eines Produktes, der der Summe der Logarithmen der Faktoren entspricht:

L-Gesetz


L-Gesetz

Diese beiden Regeln machen wir uns jetzt zunutze um die Formeln Computer-gerecht umzuformen:

Zuerst wenden wir auf beide Seiten den natürlichen Logarithmus an. Der ist zwar nur für positive Zahlen definiert, aber andere treten ja nicht auf.

Die Brüche werden mit Hilfe der Logarithmengesetze umgeformt.

Der natürliche Logarithmus des Vergleichswertes ist größer als null, wenn der Kommentar laut Statistiken Spam ist und kleiner als null, wenn nicht. Ein Wert von null lässt keine Aussage zu; man sollte allerdings in solchen Fällen nach dem Spruch "In dubio pro reo" verfahren in den Kommentar als Ham behandeln, um falsch positive Einstufungen zu vermeiden.

Beispiel-Implementierung

Nachdem wir jetzt eine Formel haben, mit deren Hilfe wir den Vergleichswert innerhalb von Bruchteilen von Sekunden ermitteln können ohne kilobyteweise Speicher für extreme Rechengenauigkeit verschwenden zu müssen können wir uns an eine Implementierung wagen.

Zuerst müssen wir man den Text in Zeichenketten, sogenannte "Token" zerlegen um in einem DBMS zu jedem Token zu speichern, in wie vielen Spam- und in wie vielen Ham-Kommentaren es vorkommt. Gute Erfahrungen habe ich damit gemacht, Leerzeichen, Tabulatoren, Zeilenumbrüche, Punkte, Doppelpunkte, Kommata und Semikolons als Trenner zu betrachten und alles andere als Teil eines Tokens. Es scheint verlockend, alle Texte in Kleinschreibung umzuwandeln um Speicherplatz zu sparen und die Trainingsphase zu verkürzen. Ich habe allerdings die Erfahrung gemacht, dass man das besser lassen sollte, es verdoppelt die Zahl der falsch sortierten Kommentare fast.

Beispiel Bedeutung 
 create table filter_categories (
 category varchar(20) primary key,
 words integer unsigned default 0,
 texts integer unsigned default 0,
);
insert into filter_categories (category)
 values ("ham"),("spam");

+----------+--------+-------+
| category | words  | texts |
+----------+--------+-------+
| ham      | 0      |  0    |
| spam     | 0      |  0    |
+----------+--------+-------+
 Diese Tabelle enthält zu jeder Kategorie die Information, wie viele Wörter in den Texten enthalten sind und wie viele Texte sie enthält. Jedes Wort wird pro Text nur einmal gezählt, um die Überschwemmung mit massenhaft zufälligen Wörtern zu entschärfen, wie sie E-Mail-Spam vorkommt.

Wenn man schlechte Trefferquoten erhält kann man versuchen, anstelle der Anzahl Kommentare die Anzahl Wörter in der Berechnung zu verwenden, das hilft unter Umständen wenn durchschnittliche Spam-Kommentare sehr viel länger oder kürzer als durchschnittliche Ham-Kommentare sind. 

create table filter_words (
 word varbinary(50) primary key,
 spam integer unsigned default 0,
 ham integer unsigned default 0,
);

+--------------+------+------+
| word         | spam | ham  |
+--------------+------+------+
| <a           |  981 |    1 |
| [url=http    |  641 |    0 |
| TramadolDog  |  591 |    0 |
| TamBov       |  591 |    0 |
| href=http    |  591 |    0 |
| |            |  591 |    0 |
| ist          |    0 |  391 |
| so           |    0 |  381 |
| es           |    0 |  371 |
| den          |    0 |  351 |
| ja           |    0 |  331 |
| noch         |    0 |  291 |
| an           |    0 |  271 |
| Mannheim     |    0 |  271 |
| für          |    0 |  261 |
| bei          |    0 |  261 |
+--------------+------+------+
 Hier werden Statistiken über die Spam- und Ham-Kommentare geführt. In jeder Reihe steht ein Wort und in wie vielen Spam- und Ham-Kommentaren es vorkommt.

Wenn ein neuer Kommentar eingetragen wird und den Vergleichswert berechnet werden soll muss man den Text zunächst in Wörter zerlegen und dann alle doppelten Wörter entfernen. Nimmt man aus der Tabelle die Spam-Werte der Wörter, die in dem Text vorkommen und berechnet die Summe der Logarithmen. Die gleiche Rechnung führt man für die Ham-Werte durch und zieht das Ergebnis von der ersten Summe ab. Da der Logarithmus von null nicht definiert ist muss man vorher auf diesen Wert abfragen und ihn gegebenenfalls von der Berechnung der Summe ausnehmen. Zu dem Ergebnis dieser Rechnung addiert man dann die Anzahl Wörter im vorliegenden Text minus 1 mal die Differenz der natürlichen Logarithmen der Anzahl Ham-Kommentare und Spam-Kommentare.

Screenshot

Damit hat man den Vergleichswert.

Wenn man den Filter mit Trainingsdaten füttern will muss man ebenfalls den Text in Wörter zerlegen und die doppelten entfernen und dann den Ham- oder Spam-Wert in der Wörtertabelle für jedes gefundene Wort um eins inkrementieren. Außerdem muss man den Wert "words" in der Kategorien-Tabelle um die Anzahl unterschiedlicher Wörter und den Wert "texts" um eins erhöhen.

Fertige Software

Damit können Sie jetzt natürlich sofort anfangen einen eigenen Spamfilter zu bauen. Wem das zu umständlich ist, kann auch meinen Spamfilter verwenden. Dieser steht unter der LGPL, das heißt Sie dürfen ihn in eigener Software verwenden, wenn sie den Quellcode des Spamfilters mitliefern, unabhängig von der Lizenz ihrer eigenen Software. Wenn Sie den Spamfilter verändern müssen Sie ihn unter GPL oder LGPL zur Verfügung stellen. Alles weitere klärt der mitgelieferte Original-Text der LGPL.

Aber nun zur Anwendung der Software:

Zuerst lädt man das ZIP-Datei mit den benötigten Klassen herunter und entpackt es. Man erhält die Dateien functions.php, mysql.class.php, dbwrapper.class.php und v_spam_filter.class.php, die man in der genannten Reihenfolge in den eigenen Quelltext einbindet. Dann erstellt man eine Instanz der Klasse v_spam_filter und übergibt der Methode opendb den Hostnamen des Rechners, auf dem der MySQL-Server läuft, den Benutzernamen, das Passwort, den Namen der Datenbank und das Präfix, das für Tabellennamen verwendet werden soll. Der letzte Parameter gibt an, ob die benötigten Tabellen schon existieren (false) oder erst angelegt werden müssen (true).

Beispiel 
require_once('functions.php');
require_once('mysql_connector.class.php');
require_once('v_spam_filter_mysql_storage.class.php');
require_once('v_spam_filter.class.php');

$t = new v_spam_filter();
$t->opendb('localhost', 'benutzer', 'passwort', 'datenbank', 'test', true);

Jetzt kann man Spam mit $t->add_text('spam', $text) und Ham mit $t->add_text('ham', $text) eintragen, $text darf dabei eine Zeichenkette oder ein assoziatives Array nach folgendem Schema sein: 

array(
 'name' => 'Name, Vorname',
 'text' => 'Kommentar-Beitrag'
 ... (beliebige weitere Feld-Wert-Kombinationen, die der Benutzer eingegeben hat)
)

Wie die Schlüssel heißen ist irrelevant. Es ist aber zu empfehlen Abkürzungen mit einem Buchstaben zu verwenden, um Redundanz in der Datenbank zu vermeiden und die Performance nicht unnötig zu verschlechtern.

Es kann immer mal passieren, dass man einen Text in die falsche Kategorie einsortiert. Dagegen gibt es die Methode remove_text, die die gleichen Parameter wie add_text erwartet und einen fehlerhaft eingetragenen Text wieder aus den Statistiken herausrechnet.

Sobald man ein paar dutzend Ham- und Spam-Kommentare eingetragen hat wird es sinnvoll, ihn Vergleichswerte für neue Texte berechnen zu lassen. Dazu übergibt man der Methode get_rank($text) als einzigen Parameter den zu untersuchenden Text, der wieder als Zeichenkette oder Array vorliegen darf und bekommt den Vergleichswert als Gleitkommazahl. Um falsch positiv sortierte Kommentare zu vermeiden sollte man Kommentare erst ab einem Vergleichswert größer null wirklich als Spam behandeln lassen.

Download


Weblinks

Abgerufen von „http://wiki.selfhtml.org/index.php?title=Programmiertechnik/Bayesscher_Kommentarspam-Filter&oldid=98085“