Een Plan voor Spam | undefined | Essays van Paul Graham

Wil je dingen bouwen? Probeer Hacker News.

Augustus 2002

(Dit artikel beschrijft de spamfiltertechnieken die gebruikt worden in de spamvrije webgebaseerde mailreader die we hebben gebouwd om Arc te oefenen. Een verbeterd algoritme wordt beschreven in Betere Bayesiaanse Filtering.)

Ik denk dat het mogelijk is om spam te stoppen, en dat op inhoud gebaseerde filters de manier zijn om dat te doen. De achilleshiel van spammers is hun bericht. Ze kunnen elke andere barrière die je opwerpt omzeilen. Dat hebben ze tot nu toe gedaan, tenminste. Maar ze moeten hun bericht afleveren, wat het ook is. Als we software kunnen schrijven die hun berichten herkent, is er geen manier waarop ze dat kunnen omzeilen.

Voor de ontvanger is spam gemakkelijk herkenbaar. Als je iemand zou inhuren om je mail te lezen en de spam te verwijderen, zou die er weinig moeite mee hebben. Hoeveel moeten we doen, afgezien van AI, om dit proces te automatiseren?

Ik denk dat we het probleem met vrij eenvoudige algoritmen kunnen oplossen. Sterker nog, ik heb ontdekt dat je de huidige spam acceptabel goed kunt filteren met niets meer dan een Bayesiaanse combinatie van de spamkansen van individuele woorden. Met een licht aangepaste (zoals hieronder beschreven) Bayesiaanse filter missen we nu minder dan 5 van de 1000 spams, met 0 valse positieven.

De statistische aanpak is meestal niet het eerste wat mensen proberen als ze spamfilters schrijven. De eerste ingeving van de meeste hackers is om software te proberen te schrijven die individuele eigenschappen van spam herkent. Je kijkt naar spams en denkt, de lef van deze jongens om me mail te sturen die begint met "Beste Vriend" of een onderwerp heeft dat helemaal in hoofdletters is en eindigt met acht uitroeptekens. Ik kan dat spul filteren met ongeveer één regel code.

En dus doe je dat, en in het begin werkt het. Een paar eenvoudige regels zullen een flinke hap uit je inkomende spam nemen. Alleen al het zoeken naar het woord "klik" zal 79,7% van de e-mails in mijn spamcorpus vangen, met slechts 1,2% valse positieven.

Ik heb ongeveer zes maanden software geschreven die zocht naar individuele spamkenmerken voordat ik de statistische aanpak probeerde. Wat ik ontdekte was dat het herkennen van dat laatste paar procent spams erg moeilijk werd, en dat naarmate ik de filters strenger maakte, ik meer valse positieven kreeg.

Valse positieven zijn onschuldige e-mails die per abuis als spam worden geïdentificeerd. Voor de meeste gebruikers is het missen van legitieme e-mail een orde van grootte erger dan het ontvangen van spam, dus een filter dat valse positieven oplevert, is als een acne-kuur die een risico op de dood voor de patiënt met zich meebrengt.

Hoe meer spam een gebruiker krijgt, hoe kleiner de kans dat hij één onschuldig mailtje in zijn spammap opmerkt. En vreemd genoeg, hoe beter je spamfilters worden, hoe gevaarlijker valse positieven worden, want als de filters echt goed zijn, zullen gebruikers alles wat ze vangen eerder negeren.

Ik weet niet waarom ik de statistische aanpak zo lang heb vermeden. Ik denk dat het kwam doordat ik verslaafd raakte aan het zelf identificeren van spamkenmerken, alsof ik een soort competitief spel speelde met de spammers. (Niet-hackers realiseren zich dit niet vaak, maar de meeste hackers zijn erg competitief.) Toen ik statistische analyse probeerde, ontdekte ik onmiddellijk dat het veel slimmer was dan ik. Het ontdekte, natuurlijk, dat termen als "virtumundo" en "tieners" goede indicatoren van spam waren. Maar het ontdekte ook dat "per" en "FL" en "ff0000" goede indicatoren van spam waren. Sterker nog, "ff0000" (html voor felrood) blijkt een net zo goede indicator van spam te zijn als elke pornografische term.

Hier is een schets van hoe ik statistische filtering doe. Ik begin met één corpus van spam en één van niet-spam mail. Op dit moment heeft elk ongeveer 4000 berichten. Ik scan de volledige tekst, inclusief headers en ingebedde html en javascript, van elk bericht in elk corpus. Ik beschouw momenteel alfanumerieke tekens, streepjes, apostroffen en dollartekens als onderdeel van tokens, en al het andere als een tokenseparator. (Hier is waarschijnlijk ruimte voor verbetering.) Ik negeer tokens die volledig uit cijfers bestaan, en ik negeer ook html-commentaren, en beschouw ze niet eens als tokenseparators.

Ik tel het aantal keren dat elk token (ongeacht hoofdletters, momenteel) voorkomt in elk corpus. In dit stadium eindig ik met twee grote hash-tabellen, één voor elk corpus, die tokens koppelen aan het aantal voorkomens.

Vervolgens maak ik een derde hash-tabel, die dit keer elk token koppelt aan de waarschijnlijkheid dat een e-mail die het bevat een spam is, wat ik als volgt bereken [1]: (let ((g (* 2 (or (gethash word good) 0))) (b (or (gethash word bad) 0))) (unless (< (+ g b) 5) (max .01 (min .99 (float (/ (min 1 (/ b nbad)) (+ (min 1 (/ g ngood)) (min 1 (/ b nbad))))))))) waar 'word' het token is waarvan we de waarschijnlijkheid berekenen, 'good' en 'bad' de hash-tabellen zijn die ik in de eerste stap heb gemaakt, en 'ngood' en 'nbad' respectievelijk het aantal niet-spam en spam-berichten zijn.

Ik heb dit als code uitgelegd om een paar belangrijke details te laten zien. Ik wil de waarschijnlijkheden licht bevooroordelen om valse positieven te vermijden, en door vallen en opstaan heb ik ontdekt dat een goede manier om dit te doen is om alle getallen in 'good' te verdubbelen. Dit helpt om onderscheid te maken tussen woorden die af en toe voorkomen in legitieme e-mail en woorden die bijna nooit voorkomen. Ik beschouw alleen woorden die meer dan vijf keer in totaal voorkomen (eigenlijk, vanwege het verdubbelen, zou drie keer voorkomen in niet-spam mail voldoende zijn). En dan is er nog de vraag welke waarschijnlijkheid toe te kennen aan woorden die in het ene corpus voorkomen maar niet in het andere. Opnieuw door vallen en opstaan heb ik .01 en .99 gekozen. Hier is wellicht ruimte voor afstemming, maar naarmate het corpus groeit, zal dergelijke afstemming sowieso automatisch gebeuren.

De bijzonder oplettende lezer zal opmerken dat, hoewel ik elk corpus beschouw als een enkele lange tekststroom voor het tellen van voorkomens, ik het aantal e-mails in elk, in plaats van hun gecombineerde lengte, gebruik als deler bij het berekenen van spamkansen. Dit voegt nog een lichte bias toe ter bescherming tegen valse positieven.

Wanneer nieuwe mail arriveert, wordt deze gescand in tokens, en de vijftien meest interessante tokens, waarbij interessant wordt gemeten aan de hand van hoe ver hun spamkans afwijkt van een neutrale .5, worden gebruikt om de kans te berekenen dat de mail spam is. Als 'probs' een lijst is van de vijftien individuele waarschijnlijkheden, bereken je de gecombineerde waarschijnlijkheid als volgt: (let ((prod (apply #'* probs))) (/ prod (+ prod (apply #'* (mapcar #'(lambda (x) (- 1 x)) probs))))) Een vraag die in de praktijk rijst, is welke waarschijnlijkheid toe te kennen aan een woord dat je nog nooit hebt gezien, d.w.z. een dat niet voorkomt in de hash-tabel van woordwaarschijnlijkheden. Ik heb, opnieuw door vallen en opstaan, ontdekt dat .4 een goed getal is om te gebruiken. Als je een woord nog nooit eerder hebt gezien, is het waarschijnlijk redelijk onschuldig; spamwoorden zijn meestal maar al te bekend.

Er zijn voorbeelden van de toepassing van dit algoritme op daadwerkelijke e-mails in een bijlage aan het einde.

Ik behandel mail als spam als het bovenstaande algoritme een kans van meer dan .9 op spam geeft. Maar in de praktijk zou het niet veel uitmaken waar ik deze drempel plaatste, omdat weinig waarschijnlijkheden in het midden van het bereik eindigen.

Een groot voordeel van de statistische aanpak is dat je niet zoveel spams hoeft te lezen. In de afgelopen zes maanden heb ik letterlijk duizenden spams gelezen, en het is echt demotiverend. Norbert Wiener zei dat als je met slaven concurreert, je een slaaf wordt, en er is iets soortgelijks vernederends aan concurreren met spammers. Om individuele spamkenmerken te herkennen, moet je proberen in de geest van de spammer te kruipen, en eerlijk gezegd wil ik zo min mogelijk tijd in de geest van spammers doorbrengen.

Maar het echte voordeel van de Bayesiaanse aanpak is natuurlijk dat je weet wat je meet. Kenmerk-herkennende filters zoals SpamAssassin kennen een spam-"score" toe aan e-mail. De Bayesiaanse aanpak kent een daadwerkelijke waarschijnlijkheid toe. Het probleem met een "score" is dat niemand weet wat het betekent. De gebruiker weet niet wat het betekent, maar erger nog, de ontwikkelaar van de filter ook niet. Hoeveel punten moet een e-mail krijgen voor het woord "seks" erin? Een waarschijnlijkheid kan natuurlijk verkeerd zijn, maar er is weinig ambiguïteit over wat het betekent, of hoe bewijs gecombineerd moet worden om het te berekenen. Op basis van mijn corpus geeft "seks" een kans van .97 aan dat de e-mail die het bevat een spam is, terwijl "sexy" een kans van .99 aangeeft. En de Regel van Bayes, even ondubbelzinnig, zegt dat een e-mail die beide woorden bevat, in de (onwaarschijnlijke) afwezigheid van enig ander bewijs, een kans van 99,97% heeft om een spam te zijn.

Omdat het waarschijnlijkheden meet, beschouwt de Bayesiaanse aanpak al het bewijs in de e-mail, zowel goed als slecht. Woorden die disproportioneel zeldzaam voorkomen in spam (zoals "hoewel" of "vanavond" of "blijkbaar") dragen net zoveel bij aan het verlagen van de waarschijnlijkheid als slechte woorden zoals "afmelden" en "opt-in" doen aan het verhogen ervan. Dus een verder onschuldige e-mail die toevallig het woord "seks" bevat, zal niet als spam worden gemarkeerd.

Idealiter zouden de waarschijnlijkheden natuurlijk individueel voor elke gebruiker moeten worden berekend. Ik krijg veel e-mail met het woord "Lisp", en (tot nu toe) geen spam die dat bevat. Dus een woord als dat is effectief een soort wachtwoord om mail naar mij te sturen. In mijn eerdere spamfiltersoftware kon de gebruiker een lijst met dergelijke woorden instellen en mail die ze bevatte, zou automatisch de filters passeren. Op mijn lijst heb ik woorden als "Lisp" gezet en ook mijn postcode, zodat (anders nogal spam-klinkende) ontvangstbewijzen van online bestellingen doorkwamen. Ik dacht dat ik heel slim was, maar ik ontdekte dat de Bayesiaanse filter hetzelfde voor me deed, en bovendien veel woorden ontdekte waar ik niet aan had gedacht.

Toen ik aan het begin zei dat onze filters minder dan 5 spams per 1000 doorlieten met 0 valse positieven, heb ik het over het filteren van mijn mail op basis van een corpus van mijn mail. Maar deze cijfers zijn niet misleidend, want dat is de aanpak die ik aanbeveel: filter de mail van elke gebruiker op basis van de spam en niet-spam mail die hij ontvangt. In wezen zou elke gebruiker twee verwijderknoppen moeten hebben, gewone verwijderen en verwijderen-als-spam. Alles wat als spam wordt verwijderd, gaat naar het spamcorpus, en al het andere gaat naar het niet-spam corpus.

Je zou gebruikers kunnen starten met een seed-filter, maar uiteindelijk zou elke gebruiker zijn eigen per-woord waarschijnlijkheden moeten hebben op basis van de daadwerkelijke mail die hij ontvangt. Dit (a) maakt de filters effectiever, (b) laat elke gebruiker zijn eigen precieze definitie van spam bepalen, en (c) maakt het, misschien wel het beste van alles, moeilijk voor spammers om mails af te stemmen om de filters te passeren. Als een groot deel van de hersenen van de filter in de individuele databases zit, dan garandeert het simpelweg afstemmen van spams om de seed-filters te passeren niets over hoe goed ze individuele, variërende en veel beter getrainde filters van gebruikers zullen passeren.

Op inhoud gebaseerde spamfiltering wordt vaak gecombineerd met een whitelist, een lijst van afzenders wiens mail zonder filtering kan worden geaccepteerd. Een gemakkelijke manier om zo'n whitelist te bouwen, is door een lijst bij te houden van elk adres waarnaar de gebruiker ooit mail heeft gestuurd. Als een mailreader een verwijderen-als-spam knop heeft, kun je ook het afzenderadres van elke e-mail die de gebruiker als gewoon afval heeft verwijderd, toevoegen.

Ik ben een voorstander van whitelists, maar meer als een manier om berekeningen te besparen dan als een manier om filtering te verbeteren. Ik dacht vroeger dat whitelists filtering gemakkelijker zouden maken, omdat je alleen e-mail zou hoeven te filteren van mensen waarvan je nog nooit had gehoord, en iemand die je voor het eerst mail stuurt, wordt door conventie beperkt in wat ze tegen je kunnen zeggen. Iemand die je al kent, kan je een e-mail sturen over seks, maar iemand die je voor het eerst mail stuurt, zou dat waarschijnlijk niet doen. Het probleem is dat mensen meer dan één e-mailadres kunnen hebben, dus een nieuw afzenderadres garandeert niet dat de afzender je voor het eerst mailt. Het is niet ongebruikelijk dat een oude vriend (vooral als hij een hacker is) je plotseling een e-mail stuurt met een nieuw afzenderadres, dus je kunt geen valse positieven riskeren door mail van onbekende adressen te streng te filteren.

In zekere zin belichamen mijn filters zichzelf echter wel als een soort whitelist (en blacklist) omdat ze gebaseerd zijn op volledige berichten, inclusief de headers. Dus tot op zekere hoogte "kennen" ze de e-mailadressen van vertrouwde afzenders en zelfs de routes waarlangs mail van hen naar mij komt. En ze weten hetzelfde over spam, inclusief de servernamen, mailer-versies en protocollen.

Als ik dacht dat ik de huidige spamfilteringsnelheden kon bijhouden, zou ik dit probleem als opgelost beschouwen. Maar het betekent niet veel om de meeste huidige spam te kunnen filteren, omdat spam evolueert. Inderdaad, de meeste antispamtechnieken zijn tot nu toe als pesticiden geweest die niet meer doen dan een nieuwe, resistente stam van insecten creëren.

Ik ben hoopvoller over Bayesiaanse filters, omdat ze evolueren met de spam. Dus als spammers "c0ck" in plaats van "cock" beginnen te gebruiken om simpele spamfilters gebaseerd op individuele woorden te ontwijken, merken Bayesiaanse filters dat automatisch op. Inderdaad, "c0ck" is veel damning bewijs dan "cock", en Bayesiaanse filters weten precies hoeveel meer.

Toch moet iedereen die een plan voor spamfiltering voorstelt, de vraag kunnen beantwoorden: als de spammers precies wisten wat je deed, hoe goed zouden ze dan langs je heen kunnen komen? Ik denk bijvoorbeeld dat als op checksum gebaseerde spamfiltering een serieus obstakel wordt, de spammers gewoon zullen overschakelen op mad-lib technieken voor het genereren van berichtlichamen.

Om Bayesiaanse filters te verslaan, zou het voor spammers niet genoeg zijn om hun e-mails uniek te maken of te stoppen met het gebruik van individuele ondeugende woorden. Ze zouden hun mails ononderscheidbaar moeten maken van je gewone mail. En dit, denk ik, zou hen ernstig beperken. Spam is meestal verkooppraatjes, dus tenzij je reguliere mail allemaal verkooppraatjes zijn, zullen spams onvermijdelijk een ander karakter hebben. En de spammers zouden natuurlijk ook hun hele infrastructuur moeten veranderen (en blijven veranderen), want anders zouden de headers net zo slecht lijken voor de Bayesiaanse filters als altijd, ongeacht wat ze aan het berichtlichaam deden. Ik weet niet genoeg over de infrastructuur die spammers gebruiken om te weten hoe moeilijk het zou zijn om de headers er onschuldig uit te laten zien, maar mijn gok is dat het nog moeilijker zou zijn dan het bericht er onschuldig uit te laten zien.

Ervan uitgaande dat ze het probleem van de headers konden oplossen, zal de spam van de toekomst er waarschijnlijk ongeveer zo uitzien: Hey daar. Dacht dat je het volgende moest bekijken: http://www.27meg.com/foo want dat is ongeveer zoveel verkooppraatje als op inhoud gebaseerde filtering de spammer ruimte laat om te maken. (Inderdaad, het zal zelfs moeilijk zijn om dit langs filters te krijgen, want als al het andere in de e-mail neutraal is, zal de spamkans afhangen van de url, en het zal enige moeite kosten om dat neutraal te laten lijken.)

Spammers variëren van bedrijven die zogenaamde opt-in lijsten runnen en hun identiteit niet eens proberen te verbergen, tot jongens die mailservers kapen om spam te versturen ter promotie van pornosites. Als we filtering gebruiken om hun opties te beperken tot mails zoals de bovenstaande, dan zouden de spammers aan de "legitieme" kant van het spectrum grotendeels uit het bedrijf zijn; ze voelen zich verplicht door verschillende staatswetten om boilerplate op te nemen over waarom hun spam geen spam is, en hoe je je "abonnement" kunt annuleren, en dat soort tekst is gemakkelijk te herkennen.

(Ik dacht vroeger dat het naïef was om te geloven dat strengere wetten spam zouden verminderen. Nu denk ik dat hoewel strengere wetten de hoeveelheid spam die spammers versturen misschien niet verminderen, ze filters wel kunnen helpen om de hoeveelheid spam die ontvangers daadwerkelijk zien te verminderen.)

Over het hele spectrum, als je de verkooppraatjes die spammers kunnen maken beperkt, zul je ze onvermijdelijk uit het bedrijf zetten. Dat woord bedrijf is een belangrijk woord om te onthouden. De spammers zijn zakenmensen. Ze sturen spam omdat het werkt. Het werkt omdat, hoewel de responsrate afschuwelijk laag is (hooguit 15 per miljoen, vergeleken met 3000 per miljoen voor een catalogusmailing), de kosten, voor hen, praktisch niets zijn. De kosten zijn enorm voor de ontvangers, ongeveer 5 manweken voor elke miljoen ontvangers die een seconde besteden aan het verwijderen van de spam, maar de spammer hoeft dat niet te betalen.

Het versturen van spam kost de spammer echter wel iets. [2] Dus hoe lager we de responsrate kunnen krijgen - hetzij door filtering, hetzij door filters te gebruiken om spammers te dwingen hun verkooppraatjes te verdunnen - hoe minder bedrijven het de moeite waard zullen vinden om spam te versturen.

De reden dat spammers de soorten verkooppraatjes gebruiken die ze doen, is om de responsrates te verhogen. Dit is mogelijk nog walgelijker dan in de geest van een spammer kruipen, maar laten we snel kijken in de geest van iemand die reageert op een spam. Deze persoon is ofwel verbazingwekkend goedgelovig of diep in ontkenning over hun seksuele interesses. In beide gevallen, hoe afstotelijk of idioot de spam ook aan ons lijkt, het is opwindend voor hen. De spammers zouden deze dingen niet zeggen als ze niet opwindend klonken. En "dacht dat je het volgende moest bekijken" zal lang niet zoveel aantrekkingskracht hebben op de spamontvanger als de dingen die spammers nu zeggen. Resultaat: als het geen opwindende verkooppraatjes kan bevatten, wordt spam minder effectief als marketinginstrument, en minder bedrijven willen het gebruiken.

Dat is uiteindelijk de grote winst. Ik begon met het schrijven van spamfiltersoftware omdat ik het spul niet meer wilde zien. Maar als we goed genoeg worden in het filteren van spam, zal het stoppen met werken, en zullen de spammers het daadwerkelijk stoppen met versturen.

Van alle benaderingen om spam te bestrijden, van software tot wetten, geloof ik dat Bayesiaanse filtering de meest effectieve zal zijn. Maar ik denk ook dat hoe meer verschillende soorten antispam-inspanningen we ondernemen, hoe beter, omdat elke maatregel die spammers beperkt, filtering gemakkelijker zal maken. En zelfs binnen de wereld van op inhoud gebaseerde filtering, denk ik dat het goed zal zijn als er veel verschillende soorten software tegelijkertijd worden gebruikt. Hoe meer verschillende filters er zijn, hoe moeilijker het voor spammers zal zijn om spams af te stemmen om erdoorheen te komen.

Bijlage: Voorbeelden van Filtering

Hier is een voorbeeld van een spam die arriveerde terwijl ik dit artikel aan het schrijven was. De vijftien meest interessante woorden in deze spam zijn: qvp0045 indira mx-05 intimail $7500 freeyankeedom cdo bluefoxmedia jpg unsecured platinum 3d0 qves 7c5 7c266675 De woorden zijn een mix van spullen uit de headers en uit het berichtlichaam, wat typisch is voor spam. Ook typisch voor spam is dat elk van deze woorden een spamkans heeft, in mijn database, van .99. Sterker nog, er zijn meer dan vijftien woorden met kansen van .99, en dit zijn gewoon de eerste vijftien die gezien zijn.

Helaas maakt dit de e-mail een saai voorbeeld van het gebruik van de Regel van Bayes. Om een interessante variëteit aan waarschijnlijkheden te zien, moeten we deze eigenlijk nogal atypische spam bekijken.

De vijftien meest interessante woorden in deze spam, met hun waarschijnlijkheden, zijn: madam 0.99 promotion 0.99 republic 0.99 shortest 0.047225013 mandatory 0.047225013 standardization 0.07347802 sorry 0.08221981 supported 0.09019077 people's 0.09019077 enter 0.9075001 quality 0.8921298 organization 0.12454646 investment 0.8568143 very 0.14758544 valuable 0.82347786 Dit keer is het bewijs een mix van goed en slecht. Een woord als "shortest" is bijna net zoveel bewijs voor onschuld als een woord als "madam" of "promotion" voor schuld. Maar toch is het bewijs voor schuld sterker. Als je deze getallen combineert volgens de Regel van Bayes, is de resulterende waarschijnlijkheid .9027.

"Madam" komt duidelijk van spams die beginnen met "Geachte heer of mevrouw." Ze komen niet erg vaak voor, maar het woord "madam" komt nooit voor in mijn legitieme e-mail, en het gaat allemaal om de verhouding.

"Republic" scoort hoog omdat het vaak voorkomt in Nigeriaanse scam-e-mails, en ook één of twee keer voorkomt in spams die verwijzen naar Korea en Zuid-Afrika. Je zou kunnen zeggen dat het toeval is dat het deze spam helpt identificeren. Maar ik heb bij het onderzoeken van spamkansen ontdekt dat er veel van deze toevalligheden zijn, en ze hebben een griezelige neiging om dingen in de juiste richting te duwen in plaats van de verkeerde. In dit geval is het niet geheel toevallig dat het woord "Republic" voorkomt in Nigeriaanse scam-e-mails en deze spam. Er is een hele klasse van dubieuze zakelijke voorstellen met minder ontwikkelde landen, en deze hebben op hun beurt weer vaker namen die expliciet specificeren (omdat ze dat niet zijn) dat het republieken zijn.[3]

Aan de andere kant is "enter" een echte misser. Het komt meestal voor in afmeldinstructies, maar wordt hier op een volkomen onschuldige manier gebruikt. Gelukkig is de statistische aanpak vrij robuust, en kan deze heel wat missers tolereren voordat de resultaten worden beïnvloed.

Ter vergelijking, hier is een voorbeeld van die zeldzame vogel, een spam die door de filters komt. Waarom? Omdat het door puur toeval beladen is met woorden die voorkomen in mijn daadwerkelijke e-mail: perl 0.01 python 0.01 tcl 0.01 scripting 0.01 morris 0.01 graham 0.01491078 guarantee 0.9762507 cgi 0.9734398 paul 0.027040077 quite 0.030676773 pop3 0.042199217 various 0.06080265 prices 0.9359873 managed 0.06451222 difficult 0.071706355 Er zijn een paar stukjes goed nieuws hier. Ten eerste zou deze mail waarschijnlijk niet door de filters van iemand komen die zich niet toevallig specialiseerde in programmeertalen en een goede vriend genaamd Morris had. Voor de gemiddelde gebruiker zouden alle top vijf woorden hier neutraal zijn en niet bijdragen aan de spamkans.

Ten tweede denk ik dat filtering op basis van woordparen (zie hieronder) deze wel eens zou kunnen vangen: "cost effective", "setup fee", "money back" -- behoorlijk belastende dingen. En natuurlijk, als ze me (of een netwerk waar ik deel van uitmaakte) bleven spammen, zou "Hostex" zelf worden herkend als een spamterm.

Tot slot, hier is een onschuldige e-mail. De vijftien meest interessante woorden zijn als volgt: continuation 0.01 describe 0.01 continuations 0.01 example 0.033600237 programming 0.05214485 i'm 0.055427782 examples 0.07972858 color 0.9189189 localhost 0.09883721 hi 0.116539136 california 0.84421706 same 0.15981844 spot 0.1654587 us-ascii 0.16804294 what 0.19212411 De meeste woorden hier geven aan dat de mail onschuldig is. Er zijn twee slecht ruikende woorden, "color" (spammers houden van gekleurde lettertypen) en "California" (dat voorkomt in testimonials en ook in menu's in formulieren), maar ze zijn niet genoeg om duidelijk onschuldige woorden als "continuation" en "example" te compenseren.

Het is interessant dat "describe" zo grondig onschuldig wordt beoordeeld. Het is in geen enkele van mijn 4000 spams voorgekomen. De gegevens blijken vol te zitten met dergelijke verrassingen. Een van de dingen die je leert als je spamteksten analyseert, is hoe smal een subset van de taal spammers opereert. Het is dat feit, samen met het even kenmerkende vocabulaire van de mail van elke individuele gebruiker, dat Bayesiaanse filtering een goede gok maakt.

Bijlage: Meer Ideeën

Een idee dat ik nog niet heb geprobeerd, is filteren op basis van woordparen, of zelfs woordtriples, in plaats van individuele woorden. Dit zou een veel scheremere schatting van de waarschijnlijkheid moeten opleveren. Bijvoorbeeld, in mijn huidige database heeft het woord "offers" een waarschijnlijkheid van .96. Als je de waarschijnlijkheden op woordparen zou baseren, zou je eindigen met "special offers" en "valuable offers" met waarschijnlijkheden van .99 en, zeg, "approach offers" (zoals in "this approach offers") met een waarschijnlijkheid van .1 of minder.

De reden dat ik dit niet heb gedaan, is dat filtering op basis van individuele woorden al zo goed werkt. Maar het betekent wel dat er ruimte is om de filters aan te scherpen als spam moeilijker te detecteren wordt. (Vreemd genoeg zou een filter gebaseerd op woordparen in feite een Markov-keten tekstgenerator zijn die achteruit draait.)

Specifieke spamkenmerken (bijv. het niet zien van het e-mailadres van de ontvanger in het 'aan:' veld) hebben uiteraard waarde bij het herkennen van spam. Ze kunnen in dit algoritme worden beschouwd door ze te behandelen als virtuele woorden. Ik zal dit waarschijnlijk in toekomstige versies doen, althans voor een handvol van de meest flagrante spamindicatoren. Kenmerk-herkennende spamfilters hebben veel details juist; wat ze missen, is een algehele discipline voor het combineren van bewijs.

Het herkennen van niet-spamkenmerken kan belangrijker zijn dan het herkennen van spamkenmerken. Valse positieven zijn zo'n zorg dat ze buitengewone maatregelen vereisen. Ik zal waarschijnlijk in toekomstige versies een tweede testniveau toevoegen dat speciaal is ontworpen om valse positieven te vermijden. Als een mail dit tweede filterniveau activeert, wordt deze geaccepteerd, zelfs als de spamkans boven de drempel ligt.

Ik verwacht niet dat dit tweede filterniveau Bayesiaans zal zijn. Het zal onvermijdelijk niet alleen ad hoc zijn, maar gebaseerd op gissingen, omdat het aantal valse positieven niet groot genoeg zal zijn om patronen op te merken. (Het is sowieso goed, als een back-upsysteem niet op dezelfde technologie vertrouwt als het primaire systeem.)

Een ander ding dat ik in de toekomst zou kunnen proberen, is om extra aandacht te besteden aan specifieke delen van de e-mail. Ongeveer 95% van de huidige spam bevat bijvoorbeeld de url van een site die ze willen dat je bezoekt. (De overige 5% wil dat je een telefoonnummer belt, per e-mail antwoordt of naar een Amerikaans postadres, of in een paar gevallen een bepaalde aandelenkoers koopt.) De url is in zulke gevallen praktisch genoeg om te bepalen of de e-mail spam is.

Domeinnamen verschillen van de rest van de tekst in een (niet-Duitse) e-mail in die zin dat ze vaak uit verschillende woorden bestaan die aan elkaar zijn geplakt. Hoewel computationeel duur in het algemene geval, kan het de moeite waard zijn om ze te ontleden. Als een filter het token "xxxporn" nog nooit eerder heeft gezien, heeft het een individuele spamkans van .4, terwijl "xxx" en "porn" individueel kansen hebben (in mijn corpus) van respectievelijk .9889 en .99, en een gecombineerde kans van .9998.

Ik verwacht dat het ontleden van domeinnamen belangrijker wordt naarmate spammers geleidelijk worden gedwongen om het gebruik van belastende woorden in de tekst van hun berichten te stoppen. (Een url met een ip-adres is natuurlijk een extreem belastend teken, behalve in de mail van enkele systeembeheerders.)

Het zou een goed idee kunnen zijn om een gezamenlijk onderhouden lijst van door spammers gepromote urls te hebben. We zouden een vertrouwensmetriek nodig hebben van het type dat Raph Levien bestudeert om kwaadaardige of incompetente inzendingen te voorkomen, maar als we zoiets hadden, zou het een impuls geven aan elke filtersoftware. Het zou ook een handige basis zijn voor boycots.

Een andere manier om dubieuze urls te testen, zou zijn om een crawler uit te sturen om de site te bekijken voordat de gebruiker de e-mail die ernaar verwijst bekijkt. Je zou een Bayesiaanse filter kunnen gebruiken om de site te beoordelen, net zoals je een e-mail zou doen, en wat op de site werd gevonden, zou kunnen worden opgenomen in de berekening van de waarschijnlijkheid dat de e-mail spam is. Een url die naar een doorverwijzing leidde, zou natuurlijk bijzonder verdacht zijn.

Een coöperatief project dat naar mijn mening echt een goed idee zou zijn, is het verzamelen van een gigantisch corpus van spam. Een groot, schoon corpus is de sleutel tot het goed laten werken van Bayesiaanse filtering. Bayesiaanse filters zouden het corpus zelfs als input kunnen gebruiken. Maar zo'n corpus zou ook nuttig zijn voor andere soorten filters, omdat het gebruikt zou kunnen worden om ze te testen.

Het creëren van zo'n corpus stelt enkele technische problemen. We zouden vertrouwensmetrieken nodig hebben om kwaadaardige of incompetente inzendingen te voorkomen, natuurlijk. We zouden ook manieren nodig hebben om persoonlijke informatie (niet alleen naar-adressen en cc's, maar ook bijv. de argumenten van afmeld-urls, die vaak het naar-adres coderen) uit mails in het corpus te wissen. Als iemand dit project wil aanpakken, zou het goed zijn voor de wereld.

Bijlage: Spam Definiëren

Ik denk dat er een brede consensus is over wat spam is, maar het zou nuttig zijn om een expliciete definitie te hebben. We zullen dit moeten doen als we een centrale corpus van spam willen opzetten, of zelfs om spamfilteringsnelheden zinvol te vergelijken.

Om te beginnen is spam geen ongevraagde commerciële e-mail. Als iemand in mijn buurt had gehoord dat ik op zoek was naar een oude Raleigh driewieler in goede staat, en me een e-mail stuurde om er een te verkopen, zou ik blij zijn, en toch zou deze e-mail zowel commercieel als ongevraagd zijn. Het bepalende kenmerk van spam (in feite, zijn raison d'etre) is niet dat het ongevraagd is, maar dat het geautomatiseerd is.

Het is ook slechts toevallig dat spam meestal commercieel is. Als iemand massaal e-mail zou gaan sturen ter ondersteuning van een politieke zaak, bijvoorbeeld, zou het net zoveel spam zijn als e-mail ter promotie van een pornosite.

Ik stel voor dat we spam definiëren als ongevraagde geautomatiseerde e-mail. Deze definitie omvat dus e-mail die veel juridische definities van spam niet doen. Juridische definities van spam, vermoedelijk beïnvloed door lobbyisten, hebben de neiging om mail uit te sluiten die door bedrijven wordt verzonden waarmee de ontvanger een "bestaande relatie" heeft. Maar iets kopen van een bedrijf, bijvoorbeeld, impliceert niet dat je doorlopende e-mail van hen hebt aangevraagd. Als ik iets bestel bij een online winkel, en zij sturen me vervolgens een stroom spam, is het nog steeds spam.

Bedrijven die spam versturen, geven je vaak een manier om je "af te melden", of vragen je om naar hun site te gaan en je "accountvoorkeuren" te wijzigen als je geen spam meer wilt ontvangen. Dit is niet genoeg om de mail geen spam te laten zijn. Niet afmelden is niet hetzelfde als aanmelden. Tenzij de ontvanger expliciet een duidelijk gelabeld vakje heeft aangevinkt (waarvan de standaardinstelling nee was) waarin hij vroeg om de e-mail te ontvangen, dan is het spam.

In sommige zakelijke relaties vraag je wel impliciet om bepaalde soorten mail. Wanneer je online bestelt, vraag je volgens mij impliciet om een ontvangstbewijs en een melding wanneer de bestelling wordt verzonden. Ik vind het niet erg als Verisign me mail stuurt om te waarschuwen dat een domeinnaam binnenkort verloopt (althans, als zij de daadwerkelijke registrar ervoor zijn). Maar als Verisign me e-mail stuurt met een GRATIS Gids voor het Bouwen van Mijn E-commerce Website, dan is dat spam.

Noten:

[1] De voorbeelden in dit artikel zijn vertaald naar Common Lisp voor, geloof het of niet, grotere toegankelijkheid. De hier beschreven toepassing is er een die we hebben geschreven om een nieuwe Lisp-dialect genaamd Arc te testen, die nog niet is uitgebracht.

[2] Momenteel lijkt het laagste tarief ongeveer $200 te zijn om een miljoen spams te versturen. Dat is erg goedkoop, 1/50e cent per spam. Maar het filteren van bijvoorbeeld 95% van de spam zou de kosten voor spammers om een bepaald publiek te bereiken met een factor 20 verhogen. Weinigen kunnen marges hebben die groot genoeg zijn om dat te absorberen.

[3] Als vuistregel geldt: hoe meer kwalificaties er voor de naam van een land staan, hoe corrupter de heersers. Een land genaamd De Socialistische Volksdemocratische Republiek van X is waarschijnlijk de laatste plek ter wereld waar je zou willen wonen.

Dank aan Sarah Harlin voor het lezen van concepten hiervan; Daniel Giffin (die ook de productie-Arc-interpreter schrijft) voor verschillende goede ideeën over filtering en voor het creëren van onze mailinfrastructuur; Robert Morris, Trevor Blackwell en Erann Gat voor vele discussies over spam; Raph Levien voor advies over vertrouwensmetrieken; en Chip Coldwell en Sam Steingold voor advies over statistieken.

Je vindt dit essay en 14 andere in Hackers & Painters.

Meer Info: