Nejčastěji používaná technika proti spamu jsou filtry pracující statisticky, jenž jsou založeny na metodě vypracované anglickým matematikem Tomasem Bayesem. Uvádíme přehled filtrů, které můžete použít na ochranu před spamem na poštovním serveru.

Existuje několik obecně používaných metod, jak se zbavit nevyžádané pošty. Jedny z nejmodernějších jsou bayovské filtry (dále jen BF). Představujeme linuxové bay filtry a porovnáváme je při oddělování spamu od hamu (nespamu).

Bayesovské filtry

BF jsou obecně využívané k ochraně před spamem s přihlédnutím k faktu, že jsou lehce implementovatelné, velmi účinné a nevyžadují vysoké technické znalosti. Provoz BF je založen na metodě strojového učení (machine learning algorithms). Před použitím filtru je ho třeba naučit, co považujeme za spam. Aby to bylo možné, musíme připravit seznam pošty, kterou považujeme za spam, a takové, které jsou ham. Velká výhoda filtrů založených na strojovém učení je ta, že nemají založenou definici spamu a můžeme tudíž definovat spam podle vlastních potřeb. Filtry se učí to, co uživatel označí jako spam na základě doručené pošty během učení.

BF analyzuje mail a rozděluje ho na tokeny. Následně vybírá určité tokeny z mailu a zapisuje je do databáze společně s informací, zda byly uvedeny ve spamu nebo hamu (a jak často). Když naučený filtr dostane k analýze (klasifikaci) nový mail, rozdělí ho na tokeny a provede kontrolu v databázi, jak často se daný token vyskytuje ve spamu a hamu. Na tomto základě se rozhoduje, zda je mail spam nebo ham.

Úspěšnost BF záleží mimo jiné na tom, jak jsou konstruované tokeny a kolik jich je v databázi. Příklady vlivu elementů na konstrukci tokenů:

1. Velikost písma: „free“ a „FREE“ - je to stejný nebo jiný token?
2. Doplňkové znaky: „free“ a „free!!!“ - je to stejný nebo jiný token?
3. Tečky: „sex.com“ - jsou to dva tokeny („sex“ a „com“) nebo jeden?
4. Umístění tokenů: „free“ - je v adrese odesílatele, subjektu a těle mailu; je to různý token

I když existuje mnoho jiných metod strojového učení, žádná z nich nebyla využita k analýze mailů jako techniky Thomase Bayese.

Tabulka 1. Testované filtry

Filtr	Jazyk	Testovaná verze	Domovská stránka	Licence	Poznámka
Annoyance Filter	C++	1.0b	WWW	Public Domain	Filtr rozpozná kodování znaků, dokáže přečist text zakodovaný v PDF
AntiSpam Mail Filter	C++	1.2	WWW	GPL	filtr spolupracuje s Eximem, muže být využitý s jakýmkoliv MTA
Bayespam	Perl	0.9.2	WWW	GPL	Spolupracuje s qmailem, může být využit s jakýmkoliv MTA
Bayesian Mail Filter	C	0.9.4	WWW	GPL	Dokáže podrobně využívat databázi
Bogofilter	C	0.16.4	WWW	GPL	Umožňuje analyzovat poštu ve formatu MIME multipart
CRM114	C	20040102-1.0 -SanityCheck	WWW	GPL	Jazyk pro statistickou analýzu textu
dbacl	C	1.6	WWW	GPL	Umožňuje rozdělení na více než dvě kategorie
DSPAM	C	2.8.3	WWW	GPL	Vyprojektovaný s myšlenkou změny velkého množstvi dat, nabízí pokročilé vytváření tokenů
ifile	C	1.3.3	WWW	GPL	Umožňuje rozdělení na vice než dvě kategorie, pravděpodobně první utilita pro filtrovaní pošty založena na bayes analýze
Quick Spam Filter	C	0.9.25	WWW	GPL	Rychlost, snadná instalace a snadné použití s Procmailem
SpamAssassin	Perl	2.63	WWW	Artistic Licence	Nástroj k heuristicke analýze, která využívá bayesovskou analýzu jako jeden prvek ovlivňující hodnocení mailu
SpamBayes	Python	1.0a7	WWW	PSF (Python Software Foundation)	Filtr využívá novodobé bayes techniky
SpamOracle	OCaml (Objective Caml)	1.4	WWW	GPL	Filtr je projektovaný pro spolupráci s Procmailem
SpamProbe	C++	0.9g2	WWW	QPL (Q Public License)	Ignoruje HTML, aby minimalizoval false positives

Provedené testy

Pro porovnání BF bylo provedeno kolem 600 testů, majících za cíl ohodnotit jejich funkčnost učení pomocí příkladového spamu a hamu převzatého ze sítě, vlastního spamu a hamu a vlastního spamu a hamu převzatého ze sítě. Zkoumán byl také pracovní čas filtru a využití databáze.

Všechny testované filtry umožňovaly označení klasifikovaných mailů. Značka informovala, zda je to spam nebo ham, v hlavičce je zapsána filtrem speciální hodnota. Pravidla pro označování jsou závislá na nastavení autora filtru, administrátora nebo uživatele. Pozdější uživatelova činnost (např. třídění) může být doplněna o jeden ze dvou parametrů: dvoustavová značka (spam nebo ham) nebo hodnotou od 0 do 100 nebo od 0 do 1. Ve většině filtrů platí pravidlo, že čím je hodnota vyšší, tím je vyšší pravděpodobnost, že je to spam (v CRM114 obráceně).

Test 1: Archiv SpamAssassin

První skupina testů se prováděla na veřejně dostupném archivu spamu a hamu připraveného tvůrcem SpamAssassinu (Public Corpus - http://spamassassin.org/publiccorpus). Na internetu je mnohem obtížnější najít učebnicové sbírky hamu než spamu.

K testu byly využity sbírky z 28. února 2003 (novější nebyly přístupné): easy_ham, hard_ham, easy_ham2, spam a spam_2. Archiv obsahuje 4150 mailů, které budou hamem a 1897 spamem. Hamy byly rozděleny do deseti skupin po 415 mailech a spam na deset skupin po 189 nebo 190 emailech. Následně bylo provedeno 10 testovacích cyklů u každého ze čtrnácti nástrojů. Filtr byl učen devíti skupinami hamu a spamu, testovala se klasifikace na zbylé desáté skupině. Výsledek testu je průměr z deseti cyklů.

Během klasifikace se filtr nedoučoval. Některé filtry se automaticky učí na základě předchozí klasifikace, ale nebyly ručně opravovány chyby. Klasifikace byla hodnocena šesti parametry používanými ve statistice a literatuře související se spamem.

Výsledky testů klasifikace (spam nebo ham) jsou uvedeny v tabulce 2. Vysoký precision a velmi vysoký recall nabízí SpamProbe a SpamAssassin. Velký precision získáte použitím Bogofiltru a Annoyance Filtru, ale recall je nižší. Nejvyšší precision nabízí SpamOracle, současně má i nejnižší recall. Pokud se naše hodnocení bude opírat o počet chyb, vítězem je SpamProbe.

Výsledky klasifikace na obrázku 1 a 2 ukazují false positiv rate a miss rate v závislosti na hraniční hodnotě. Obrázek 2 je část obrázku 1, zvětšení false positiv na 3% a false negatives na 4%. Interpretace výsledků je jednoduchá. Pokud se linie reprezentující výsledky dvou filtrů neprotínají, lepší výsledek získal filtr, jehož linie je umístěna více dole a vlevo. Pokud se linie kříží, hodnocení záleží na tom, jakou jsme nastavili přípustnou velikost false positives a negatives.

Při nastavení hodnot false negatives musí být nižší než 4% a false positiv musí být nižší než 1,5% - nejlepší výsledky pak vykazoval SpamProbe. Pokud za přípustnou hranici false positiv definujeme 1,75%, nejlepší je SpamAssassin. Ostatní filtry dosáhly horšího hodnocení než SpamProbe nebo SpamAssassin. Jako nejhorší se ukázal dbacl.

Tabulka 2. Vysledky testu opirajici se o archiv SpamAssassinu.

Filtr	Precision	Recall	False positiv	False negatives	Spravne zarazene maily
Annoyance Filter	99,8%	89,0%	3	209	5835
AntiSpam Mail Filter	93,3%	98,2%	133	35	5879
Bayespam	94,0%	95,9%	117	77	5853
Bayesian Mail Filter	99,3%	95,9%	13	78	5956
Bogofilter	99,7%	90,3%	5	184	5858
CRM114	97,4%	96,9%	50	58	5939
dbacl	32,8%	98,8%	3841	22	2184
DSPAM	99,3%	96,0%	13	76	5958
ifile	96,6%	93,2%	63	129	5855
Quick Spam Filter	99,1%	91,6%	16	160	5871
SpamAssassin	99,7%	96,1%	6	74	5967
SpamBayes	99,6%	95,6%	7	83	5957
SpamOracle	100,0%	83,7%	0	309	5738
SpamProbe	99,7%	96,6%	6	65	5976

Test 2: Příchozí pošta z prosince 2003

Jako materiál pro provedení testů privátní pošty byly využity maily obdržené v prosinci 2003 na adresu publikovanou mnoho let na diskuzních skupinách a WWW stránkách. Archiv obsahoval 146 mailů hamů a 3557 spamů. Ve skupině spamů jsou také viry a odpovědi antivirových programů obdržené z důvodu falešné adresy odesílatele.

Byla využita identická metoda jako u prvního testu. Výsledky jsou uvedeny v tabulce 3 a na obrázku 3 a 4. Nejlepší výsledky dosáhl QuickSpamFilter a Bogofilter (žádné false negatives a vysoký recall), také Annoyance Filter a Bayes Mail Filter (zachytily více spamů, ale objevily se i false positives). Nejvíce chyb udělal SpamProbe.

Nejlepší výsledky procentuálního hodnocení získal Bogofilter (zachytil více než 98% spamu a neudělal ani jeden false positives), Annoyance Filter (který zachytil více spamů než Bogofilter, ale povedl se mu i false positives). Jako poslední je dbacl.

Tabulka 3. Vysledky testu.

Filtr	Precision	Recall	False positiv	False negatives	Spravne zarazene maily
Annoyance Filter	99,9%	99,0%	2	34	3667
AntiSpam Mail Filter	98,3%	99,9%	62	2	3639
Bayespam	99,1%	94,7%	29	189	3485
Bayesian Mail Filter	99,8%	99,3%	8	25	3670
Bogofilter	100,0%	95,2%	0	169	3534
CRM114	99,2%	99,5%	27	19	3657
dbacl	99,3%	37,5%	9	2224	1470
DSPAM	100,0%	51,6%	0	1723	1980
ifile	99,9%	97,5%	2	90	3611
Quick Spam Filter	100,0%	95,8%	0	149	3554
SpamAssassin	100,0%	49,4%	0	1799	1904
SpamBayes	99,9%	94,7%	1	189	3513
SpamOracle	99,9%	88,6%	2	406	3295
SpamProbe	99,7%	99,7%	10	9	3684

Test 3: Vlastní spam a cizí spam

Jestliže chceme poprvé využít BF, existuje malá pravděpodobnost, že jsme shromáždili vlastní archiv spamu. Máme-li větší či menší archiv důležitých mailů, zřídkakdy sbíráme doručené spamy. V takové situaci je nejlepším východiskem využít cizího archivu spamu - např. od přátel nebo z internetu. Obrovský archiv spamu najdete na adrese http://spamarchive.org.

Mnoho specialistů na BF odsuzuje využívání cizích archivů spamů. Vychází to z faktu, že každý uživatel dostává jiné spamy a použije jiná kritéria hodnocení, zda je mail spam nebo ne. Využití cizích spamů pro učení filtru může navíc způsobit velký výskyt chyb. Test 3 sloužil pro ilustraci, jak jsou velké rozdíly při využívání vlastního a cizího spamu.

Jako ham bylo využito privátní pošty 116 mailů. Za spam posloužily dva různé zdroje: 345 mailů doručených na osobní účet a 400 mailů ze spam archivu (archiv 305.r2.gz). Maily jsou rozděleny stejně jako v předchozích testech na test skupin. Tentokrát byly vytvořeny dvě testované sestavy: deset částí pro vlastní ham a vlastní spam, deset částí pro vlastní ham a cizí spam (v druhé sestavě byl využit pro hodnocení vlastní spam).

Výsledky jsou uvedeny v tabulce 4. Výsledky (jak při využití vlastního, tak i cizího spamu) nebyly tak dobré jako v předchozích testech, což je pravděpodobně způsobeno tím, že k učení bylo použito menšího počtu mailů než předtím. Jsou to ale výsledky mnohem realističtější - málo uživatelů uchovává ohromné archivy pošty. Zajímavé je, že precision byl vyšší během učení za pomocí cizího spamu. To mohlo být způsobeno tím, že archiv cizího spamu byl vetší než archiv vlastního spamu. Recall je nižší u většiny filtrů, pokud při učení využíváme cizí spam.

Výsledky jsou na obrázcích 5 a 6. Obrázek 5 ukazuje výsledky učení filtrů za použití vlastního spamu, kdežto obrázek 6 spamu ze Spam Archive a vlastního spamu pro klasifikaci. Výsledky při využití vlastního spamu byly lepší, ale rozdíly nebyly drastické. Můžeme tedy říci, že využití cizího spamu pro učení je přípustné.

Tabulka 4. Využití jak vlastního, tak i cizího spamu.

Filtr	Uceni vlastnim spamem		Uceni cizim spamem
	precision	Recall	precision	Recall
Annoyance Filter	98,3%	86,1%	99,5%	54,5%
AntiSpam Mail Filter	89,2%	95,7%	90,9%	89,9%
bayeSpam	92,2%	92,2%	93,6%	84,9%
bayesian Mail Filter	96,1%	93,9%	100,0%	55,1%
bogofilter	99,6%	78,6%	100,0%	33,9%
CRM114	95,4%	99,1%	98,7%	71,0%
dbacl	100,0%	2,9%	100,0%	2,3%
DSpAM	98,9%	79,7%	99,2%	70,4%
ifile	96,6%	83,5%	99,1%	65,8%
Quick Spam Filter	98,8%	70,4%	98,5%	56,5%
SpamAssassin	98,5%	58,0%	98,5%	58,0%
Spambayes	99,4%	91,5%	99,5%	61,7%
SpamOracle	98,8%	75,1%	98,3%	67,0%
Spamprobe	98,2%	94,8%	99,5%	55,1%

Test 4: Správnost

Vážným aspektem praktického využití BF je jejich správnost. Ani nejdokonalejší filtr se nedá použít v praxi, pokud vyžaduje velkou kapacitu nebo analyzuje maily příliš dlouho. Veličiny, které hodnotíme jako správnost filtru, jsou: čas potřebný k učení a klasifikaci (současně s maximálním využitím procesoru), maximální využití paměti a diskový prostor odebraný pro databázi. Test byl proveden učením filtru archivem 3000 mailů a následující klasifikací jiných 3000 mailů. Výsledky jsou zobrazeny v tabulce 5.

Tabulka 5. Správnost filtru

Filtr	Uceni			Klasifikace
	Cas (s)	Cas procesoru (%)	Pamet (KB)	Cas (s)	Cas procesoru(%)	Pamet (KB)	Disk (KB)
Annoyance Filter	86	99	5776	293	99	2196	372
AntiSpam Mail Filter	146	58	514048	1569	99	48196	1676
bayespam	67	79	14088	717	99	8780	500
Bayesian Mail Filter	144	12	1604	44	82	1524	2632
Bogofilter	501	8	2932	23	92	1364	3580
CRM114	24	77	20884	632	68	25560	24616
dbacl	425	99	5228	40	99	4028	3344
DSPAM	1615	5	2620	3808	3	4044	53744
ifile	206	98	1644	54	99	1476	120
Quick Spam Filter	244	96	1480	64	95	2076	3108
SpamAssassin	200	95	17676	3581	80	25944	7792
SpamAssassin (spamd)	200	95	17676	571	bd.	3188	7792
SpamBayes	144	90	8604	487	98	6628	2156
SpamOracle	45	75	6452	22	98	1188	468
SpamProbe	121	83	7608	89	86	2460	16492

Největším „žroutem“ se ukázal AntiSpam Mail Filter. Více než půl gigabajtu RAM je příliš mnoho na praktické využití filtru. Jiné programy nepotřebovaly více než 20 MB. SpamOracle a Bogofilter se klasifikují jako nejrychlejší, využívající nejméně paměti a střední velikost diskového prostoru. Jsou nejlépe využitelné na serverech obsluhujících velké množství uživatelů.

Hodnocení

Je těžké jednoznačně označit vítěze našich testů, protože se potřeby uživatelů mohou lišit. Pokud chcete samostatně zjistit, který filtr se hodí na jakou činnost, doporučujeme využít našeho CD (/_materials/spam-bayes/). Abyste získali výsledky dle vlastních potřeb, stačí měnit parametry označené modře a zadávat různé výsledky relativní váhy.

Nejvyšší hodnocení u nás má veličina precision v testu 2. Nižší váhu má test založený na cizím spamu a nejnižší test založený na archivu SpamAssassin. Precision jsme uznali za třikrát důležitější než recall. Při takovém složení dosáhli nejlepších výsledků: Spam Bayes, Bayesian Mail Filter a Bogofilter.

Nezávisle na tom, který filtr vyberete, pamatujte na to, že jeho efektivnost bude větší než prezentovaná v testech, pokud budeme neustále učit filtr spamem a hamem a především opravovat chyby v klasifikaci (učit filtr za pomocí chybně klasifikovaných mailů). Také je třeba po určité době smazat databázi a znova učit filtr a využívat přitom nový archiv spamu a hamu. Profil spamu a hamu se v čase mění, příliš velká databáze tokenů způsobuje, že se filtr stává méně spolehlivý, i když využívá stále větší objemy dat z databáze.