ARCHIV

Hakin9 - Porovnání serverových filtrů Bayes

Vyšlo nové čislo Hakin9 z kterého s laskavým svolením redakce uveřejňujeme jeden ze zajímavých članků od Sama Holdena.

12.5.2004 18:00 | Reklama | Články autora | přečteno 6868×

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.

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.

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.

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é.

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.

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.

Verze pro tisk

DISKUZE nepresnosti, nesmysly 13.5.2004 03:43 Jan Houštěk Re: nepresnosti, nesmysly 13.5.2004 08:20 Jan Houštěk Bayes 21.5.2004 17:35 Jakub Hegenbart Zobrazit označené Zobrazit vše Příspívat do diskuze mohou pouze registrovaní uživatelé.