SpamStamp,
een antwoord op de noodkreet van Jos?

over een programma van Jan-Jaap van der Geer

Een paar maandjes terug hoorde ik op mijn werk over een methode om spam te bestrijden. 'De' beste methode was gebaseerd op een formule van een Engelse dominee ergens in zeventienhonderd-huppeldepup. Dat wekte mijn interesse, want wat heeft een 18e eeuwse priester nou te maken met spam? Dus deed ik wat onderzoek op het internet. En verdraaid, er was een Thomas Bayes die in 1763 een artikel schreef over hoe je de kans moest uitrekenen over een bepaalde situatie als je al wat informatie hebt. Bijvoorbeeld als je weet dat zoveel % van de auto's op de weg rood zijn, en zoveel % van de auto's rijden te hard. En als we nou weten dat er meer rode auto's zijn die te hard rijden dan andere kleuren, dan kunnen we meer zeggen over de kans dat een auto rood is als we al weten dat 'ie te hard rijdt.

Deze methode toegepast op spam werkt erg goed, zeggen ze. Affijn, binnen enkele seconden na achterhaald te hebben hoe deze methode ongeveer werkt, had ik besloten er een projectje van te maken. Eigenlijk heb ik helemaal geen groot spam probleem, maar het was gewoon interessant!

SpamStamp is inmiddels door een aantal generaties heen en de werking is hier en daar flink aangepast. Vooral de eerste versies hadden erg knullige methoden om uit te vinden of een bericht spam is. Maar tegenwoordig werkt het heel aardig. Ik heb me behoorlijk nauw gehouden aan een verhaal van ene Paul Graham, deze heeft een website over spam op http://www.paulgraham.com/spam.html en dat is een prachtige leidraad geweest voor SpamStamp.

Hoe werkt het?
Welnu, ieder woord in een bericht wordt omgerekend naar een getal - de methode daarvoor doet eigenlijk niet zo terzake. Dit getal representeert een positie in twee tabellen. De ene tabel is de tabel voor de frequentie waarmee woorden die in spam zijn voorgekomen, terwijl de andere een dergelijke tabel is met de frequentie van woorden die in niet-spam, ook wel 'ham' genoemd, zijn voorgekomen.

Welnu, zodra SpamStamp een bericht moet beoordelen, wordt ieder woord dus bekeken, en er wordt een kans uitgerekend dat het woord een spam-woord is. Dat gaat als volgt: De waarden voor dat woord wordt in beide tabellen opgezocht. We nemen als voorbeeld het woord 'feet' (Engels omdat nou eenmaal de meeste spam in het Engels is). Het lijkt een behoorlijk neutraal woord. Het woord blijkt 49 keer in ham voorgekomen te zijn en 32 keer in spam. Hieruit kunnen we echter nog geen conclusies verbinden. Immers, we weten helemaal niet hoeveel spam en hoeveel ham er in de tabel zit. Dus, we rekenen de kans uit dat een woord dat in spam voorkomt het woord 'feet' is. En datzelfde doen we voor ham. Dan hebben we het totaal aantal woorden in de ham en de spam nodig. We krijgen:

de kans dat een woord in spam het woord 'feet' is (spamkans): 32 / 412044 = 0,0000777
de kans dat een woord in ham het woord 'feet' is (hamkans): 49 / 2376041 = 0,0000206

Deze twee getallen kunnen we vervolgens met elkaar vergelijken, en aan de hand daarvan de kans uitrekenen dat een bericht met het woord 'feet' erin een spam bericht is:

kans dat het bericht spam is: spamkans / (spamkans + hamkans) = 0,790

oftewel, 79% kans dat een bericht waar het woord 'feet' in voorkomt, een spam bericht is!

Een van de doelstellingen van Paul Graham was dat zo min mogelijk berichten als spam herkend mogen worden terwijl het in werkelijkheid geen spam is (een zgn. vals-positief). Het tegenovergestelde, een spam bericht als ham herkennen (een vals-negatief) is niet zo gevaarlijk. De eerste versies van SpamStamp volgden deze redenering niet, maar uiteindelijk heb ik ingezien dat dat inderdaad een heel belangrijke eigenschap is van de detectie van Spam.

Een van de methodes om vals-positieven tegen te gaan is een correctie van de bovengenoemde formule. In SpamStamp verdubbel ik de hamkans, zodat de formules geen 0,790 geven, maar:

kans dat het bericht spam is: spamkans / (spamkans + 2 x hamkans) = 0,653

oftewel 65,3%. De conclusie dat een merkwaardig woord als 'feet' overigens blijkbaar veel in spam voorkomt is niet helemaal juist. Ik was zelf ook wat verbaasd en toen ik het na ging kijken bleek dat er een vrij vaak terugkomend bericht is geweest waar dat woord in voorkwam. Aangezien 'feet' nauwelijks in ham voorkomt, heeft het enigszins een spam-eigenschap gekregen. Dit is meteen ook een sterk voordeel van deze methode: Hij past zich automatisch aan aan de spam die je zelf binnenkrijgt. Zo is er een hoop spam die begint met 'hi janjaap' of iets dergelijks. Vanwege het feit dat ik een email adres heb dat janjaap@dsv.nl luidt. En dus wordt 'janjaap' eruit gepikt en gebruikt als voornaam. Maar ik heet Jan-Jaap en niemand noemt me janjaap. Het gevolg is dat zelfs een behoorlijk specifiek woord als 'janjaap' een hoog spamgehalte heeft: 96,34% kans dat een mail dat dat woord bevat een spam-bericht is!

Deze statistische methode past zich ook aan aan de spammers. Viagra werd al gauw v1agr@ of iets dergelijks. Geen probleem, want v1agr@ is statistisch gezien veel unieker dan viagra. Viagra zou wellicht nog in echte mail voor kunnen komen, maar als het als v1agr@ gespeld wordt, dan kun je er véél zekerder van zijn dat het spam is. De spammer in z'n eigen kuil gevallen!

Deze kansberekening voor een enkel woord kunnen we nu herhalen voor alle woorden in een bericht. Paul Graham heeft besloten, en ik heb dat slaafs gevolgd, om alleen de 15 meest interessante woorden eruit te plukken. De meest interessante zijn natuurlijk die waarden die het meeste op spam danwel op ham wijzen. En dat zijn dus de waarden die het verst van 50% af liggen.

Deze 15 kansen worden gecombineerd via de methode die daarvoor in de kansberekening gebruikelijk is:

           ab
gecombineerde kans op a en b: ----------------------
ab + (1 - a) (1 - b)
Het resultaat is nagenoeg altijd een kans die ofwel dicht bij 0 (geen spam) ofwel dicht bij 1 (spam) ligt. SpamStamp trekt de conclusie dat een bericht spam is als deze waarde groter is dan 0,9. Dit relatief hoge getal is wederom een zekerheid tegen vals-posititieven.

De implementatie
Alles leuk en wel. Nu kun je besluiten of een bericht spam is of niet aan de hand van wat statistieken. Leuk. Maar wat doe je er dan mee? Gooi je het bericht weg? Dat geeft moeilijkheden bij het bijwerken van de statistieken. En dat zou ook betekenen dat ik - als auteur - verantwoordelijk ben voor het weggooien van berichten die door SpamStamp als spam bestempeld zijn. Wil ik dat wel? Eigenlijk niet.

In plaats daarvan heb ik besloten wat simpele header-regels toe te voegen aan het bericht. Deze regels geven aan of het bericht spam is of niet. Vervolgens is het aan de gebruiker om wat met die headerregels te doen. Het meest voor de hand liggende is natuurlijk de spam apart te zetten. Op die manier kun je spam bekijken voordat je het weggooit. Je kunt de statistieken er mee bijwerken.

Dus SpamStamp is een programma geworden wat actief wordt op het moment dat de mail is opgehaald. Op dat moment wordt de opgehaalde mail door SpamStamp bekeken en beoordeeld. De resultaten van de beoordeling wordt teruggezet in de mailfile(s) en vervolgens gaat alles weer als voorheen, dus de mail wordt uitgepakt en in de berichtendatabase opgeslagen. Eventuele filters zorgen hier voor de acties die speciaal zijn voor spam. Maar dit gaat allemaal via de bestaande mail-software. SpamStamp heeft hier eigenlijk niets meer mee te maken.

Het frontend van SpamStamp verschijnt bij het dubbelklikken van SpamStamp als een icon op de iconbar. Dit frontend heeft een aantal taken, zoals het kunnen aanpassen van de configuratie en het kunnen bekijken van de statistieken over hoe SpamStamp werkt. Maar de belangrijkste functie is het kunnen corrigeren van fouten die SpamStamp gemaakt heeft. Indien een bericht als ham bestempeld terwijl het spam is, kun je dit bericht naar het SpamStamp frontend slepen. Als je dit doet, komt het volgende scherm tevoorschijn:

In dit geval laat het zien dat het bericht wat naar het SpamStamp frontend is gesleept herkend is als zijnde spam. Indien dit bericht eerder als ham was herkend, dan kun je SpamStamp vertellen dat het spam is door op de knop 'this is spam' te drukken. Door dat te doen wordt de statistische informatie van het bericht toegevoegd aan de spam-kennis van SpamStamp.

Vaak zal SpamStamp echter zelf al goed kiezen. In dat geval zou het leerproces sneller gaan indien SpamStamp zelf aanneemt dat wat het zelf kiest goed is, en vervolgens de statistieken aan de hand daarvan aanpast. Hier is een instelling voor, en die heet 'Learn automatically'. Als je dat kiest, worden alle berichten die via SpamStamp bestempeld worden als spam of ham tegelijkertijd toegevoegd aan de statistische kennis van SpamStamp. Maar zo af en toe zal SpamStamp nog steeds fouten maken. Omdat SpamStamp automatisch leert, is het nu veel belangrijker geworden dat SpamStamp ook gecorrigeerd wordt. Gebeurt dit niet, dan zijn er woorden die eigenlijk in de ene tabel thuishoren, maar die in de andere terechtgekomen zijn, en die niet gecorrigeerd zijn. Als 'learn automatically' uitstaat, is het niet zo kritisch dat foutief bestempelde mail gecorrigeerd wordt, alhoewel het natuurlijk altijd de kennis van SpamStamp ten goede komt.

Indien 'learn automatically' aanstaat, moet de statistische correctie dus eerst uit de ene tabel weggehaald worden, om vervolgens toegevoegd te worden aan de andere. Om dit te bewerkstelligen, moet het keuzevak 'This is a correction' aangevinkt worden. Indien 'learn automatically' uitstaat, worden de statistische gegevens niet automatisch aan de kennis van SpamStamp toegevoegd, en zodoende hoeft die ook niet eerst uit de bestaande gegevens weggetrokken te worden. In dit geval is 'This is a correction' dan ook niet nodig. SpamStamp kiest overigens de goede standaardwaarden afhankelijk van de configuratie.

De optie 'update statistics' bepaalt of de toegevoegde kennis als fout gedetecteerde berichten gezien moeten worden. Als SpamStamp slechts getraind wordt in het verschil tussen ham en spam is het niet nodig deze berichten als fout-bestempeld te zien, en wordt het aantal fout gedetecteerde berichten dan ook niet aangepast. Indien 'update statistics' wel aanstaat, wordt het bericht wel als fout-bestempeld gezien en wordt het aantal gemaakte fouten aangepast.

Ook hier is een bepaalde logica aanwezig in de standaardwaarde van dit veld. Indien één enkel bericht naar SpamStamp wordt gesleept, wordt aangenomen dat het een fout-bestempeld bericht is. Is het echter een bericht in het rmail of ANT formaat, zodat het meerdere berichten kan bevatten, dan wordt aangenomen dat het géén fout-bestempelde berichten zijn en worden de statistieken standaard niet aangepast.

Bij het leren en corrigeren van SpamStamp raad ik aan om een aantal regels in acht te nemen:

Gebruik altijd berichten met alle headers erbij, niet alleen de tekst.

Dit geldt zéér zeker als 'learn automatically' aanstaat, want als een bericht dan gecorrigeerd moet worden, moet dat voor het gehele bericht inclusief de headers gelden, en niet voor slechts de tekst. SpamStamp haalt ook interessante informatie uit de headers. Bij welke provider het bericht vandaan komt, dat soort dingen. Dit kan -via diezelfde statistische methode- ook prima tot de detectie van spam danwel ham leiden.

Zorg voor een representatief aanbod van berichten om SpamStamp mee op te leiden.

De beste methode is 'learn automatically', maar als je niet voor die methode kiest, zorg dan voor een redelijke diversiteit in de berichten te brengen waarmee SpamStamp wordt opgeleid. Indien alleen de fout gegane berichten worden gecorrigeerd zullen dit in de praktijk voornamelijk spam berichten zijn. Dat betekent dat de woordenschat van spam groter wordt en er dus meer woorden als 'spam-woorden' worden gezien. Dit kan op de langere duur veroorzaken dat ham voor spam wordt aangezien.

Als een bericht naar het SpamStamp frontend wordt gesleept om het te corrigeren, wordt ook de huidige spamscore aangegeven. (Die spamscore is een momentopname, en zal bij wijziging van de statistieken meewijzigen). Na correctie zou je nog een keer kunnen kijken of de spamscore aangepast is. Niet altijd is er verschil te zien. Dit wil niet zeggen dat er niets is gebeurd, maar wellicht dat de wijzigingen in de statistieken dermate klein zijn dat het geen effect had op de totale score. In deze situatie kan het aantrekkelijk klinken de operatie nog een keer uit te voeren. Dat raad ik echter niet aan, omdat het ongewenste bijeffecten kan hebben. Stel je hebt een spam met de tekst 'als je geen viagra bij ons koopt, ben je een oen!'. Op het moment dat dit bericht meerdere keren aan SpamStamp wordt geleerd als zijnde spam, krijgen alle woorden in dat bericht dus een hogere spamscore dan anders het geval geweest zou zijn. Een onschuldig woord als 'oen', wat nou ook weer niet zo vaak voor komt, krijgt hierbij dus een negatieve spam-betekenis. Statistisch gezien is dit onjuist en het kan tot verkeerde conclusies van SpamStamp leiden. Dus zelfs als SpamStamp na de 'opleiding' de 'les' niet begrepen heeft, weersta de verleiding om de boel te forceren!

Op het moment van schrijven staat versie 0.12 ter download op mijn website. Deze versie heeft eigenlijk een te kleine tabel voor spam en ham. Hierdoor is het effect van SpamStamp niet goed genoeg. Ik heb zelf echter een versie 0.13 die hier wat aan doet. Deze versie zal ik binnenkort op mijn website zetten. Het nadeel van deze versie is echter dat hij meer dan 2MB nodig heeft bij het controleren van berichten, omdat de beide tabellen zo groot geworden zijn. Hierin hoop ik in de komende versie (0.14?) iets aan te doen.

0.13 heeft bij mij op dit moment heel aardige statistieken:

Dus is dit het antwoord op de noodkreet? Nee, want de spam wordt nog steeds verstuurd door de spammers, en de spam moet nog steeds gedownload worden, en de spam moet nog steeds verwerkt worden enzovoort enzovoort. Maar toch, het maakt het toch weer wat makkelijker, zeker voor diegenen die een veel groter spamprobleem hebben dan ik.

Groetjes,
Jan-Jaap