Hlavní navigace

Jak funguje bayesovský antispamový filtr? (1.)

Michal Kára

V poslední době získaly mezi antispamovými nástroji silnou pozici tzv. bayesovské filtry. Většina uživatelů tuší, že klasifikují e-mail na základě toho, jaká slova se v něm vyskytují. A že se tato slova naučí tím, že jim uživatel spamy označuje. Toto je však jen obecná představa jejich fungování.

Ve skutečnosti bayesovský filtr funguje na velmi jednoduchém principu. U každého slova, které zná, si pamatuje pravděpodobnost, že e-mail, ve kterém se slovo vyskytuje, je spam. Jak se taková pravděpodobnost spočítá?

Předpokládejme, že máme dvě složky s e-maily. V jedné jsou spamy, ve druhé ne-spamy (hamy). Filtr si obě složky projde a z e-mailů vyextrahuje slova. U každého slova spočte pravděpodobnost, že e-mail s ním je spam (pspam), a to jako podíl „počet spamů, kde se slovo vyskytuje“ ku „počet všech e-mailů, kde se slovo vyskytuje“.

Dále je dobré si uvědomit, že pravděpodobnost, že e-mail je ham (pham), je dána jako „počet hamů, kde se slovo vyskytuje“ ku „počtu všech e-mailů, kde se slovo vyskytuje“. Nebo také jednodušeji jako 1-pspam.

Co uděláme při příjmu e-mailu: Stejným postupem, jaký jsme použili v předchozím kroku, z něj vyextrahujeme slova a pro každé slovo dohledáme jeho pravděpodobnost, že e-mail s ním je spam (pspam). Nyní už je to jen statistika. Podle té zjistíme pravděpodobnost, že e-mail je spam, vynásobením pravděpodobností jednotlivých slov. A totéž pro pravděpodobnost, že je mail ham. Pak obě dvě pravděpodobnosti porovnáme. Pokud je pravděpodobnější, že mail je spam, označíme jej jako spam. Jestliže je pravděpodobnější, že je ham, označíme jej jako ham.

Toto je samozřejmě hodně zjednodušený algoritmus, a jako takový by v praxi nefungoval příliš dobře. Proto se používá algoritmus poněkud upravený. Největší změnou je fakt, že se nepočítají váhy všech slov v dopise, ale jen cca dvaceti až třiceti nejzajímavějších (nejextrémnějších). Tedy takových, jejichž pspam je blízké nule nebo jedničce. Dále se pravděpodobnost jednoho slova počítá jen jednou, i kdyby se v e-mailu vyskytovalo vícekrát. Jaký to má efekt, ukáži dále.

Pokud bychom pravděpodobnosti násobili, vznikla by poměrně malá čísla. Proto se v praxi používá geometrický průměr – vynásobit a poté odmocnit tolikátou odmocninou, kolik členů jsme násobili. Tak se nám výsledek rozprostře po rozsahu od nuly do jedné rovnoměrněji.

Velmi důležitou věcí je rovněž neposuzovat pouze tělo e-mailu, ale také jeho hlavičky. V nich se totiž velmi často skrývá mnoho užitečných informací. Tak lze jednoduše do celého algoritmu zahrnout i servery, přes které e-maily chodí, User-Agenty, jména uživatelů, kteří vám píší, atp.

Nyní ale nastává otázka, jakým způsobem z hlaviček extrahovat slova. Je možné to dělat „naivně“ – stejně jako u těla. Ale lepší je rozlišovat, kde se slovo vyskytuje – poskytne nám to přesnější a citlivější algoritmus. Například slovo „free“ v těle dává, podle databáze antispamu na Centrum.cz, pravděpodobnost 50,4 procenta, že e-mail je spam. To je takřka přesně nerozhodně – takové slovo nám příliš nepomůže. Ale v předmětu zprávy dá slovo „free“ pravděpodobnost 79,6 procenta, že je e-mail spam. A to už je poměrně hodně.

Nicméně nemusí zůstat jen u toho. Jako „slova“ můžeme brát i URL v mailu obsažená. A nebo dokonce různé abnormality – e-mail pouze v HTML, neexistence reverzních záznamů protějšího serveru – prostě věci, které testuje spamassassin. Na rozdíl od něj má ale bayesovský filtr podstatně smysluplnější systém hodnocení, a hlavně fungující zpětnou vazbu.

Ta je jeho silnou zbraní. Počítá se většinou v okamžiku odstranění e-mailu z poštovního programu (MUA). Bylo by samozřejmě možné e-mail přidat do správné složky (podle toho, zda byl označen jako spam, nebo ham) a pak přepočítat pravděpodobnosti podle algoritmu uvedeného výše. Ale to by bylo s narůstajícím počtem e-mailů poněkud náročné na čas a diskový prostor.

Proto se používá vzorec stanovený Thomasem Bayesem, který nám dovoluje „upravit pravděpodobnost jevu ve světle nových důkazů“ (viz Wikipedia). Z mazaného e-mailu se opět vyextrahují všechna slova. Jejich pravděpodobnost v databázi se pak upraví podle toho, zda byl e-mail označen jako spam, nebo jako ham. Právě díky tomuto způsobu zajištění zpětné vazby je zde popisovaný filtr označován jako bayesovský.

V praxi se bayesovské filtry vyznačují velmi vysokou účinností. Není problém mít filtr s účinností kolem 99 procent a chybovostí (false positive rate) pod 0,1 procenta. Této účinnosti je dosaženo právě onou adaptabilitou. Filtr se postupně adaptuje na charakteristiku pošty svého uživatele. Stejně tak se adaptuje i na nové obsahy spamů a postupy využívané spamery.

Spameři se samozřejmě snaží bayesovské filtry obcházet. Ale z toho, že jsou stále účinné, je vidět, že se jim to příliš nedaří. Prvním pokusem bylo používat modifikované tvary slov – například „m0ney“. To však bayesovským filtrům spíše pomáhá. Slovo „money“ se vyskytuje poměrně často i v hamech. Ale „m0ney“ se tam vyskytne opravdu zřídkakdy. Dalším „opatřením“ spammerů je rozdělování slov. Výsledek je podobný, neboť se do slovníku rychle dostanou fragmenty rozdělených slov.

Stejně tak přidávání „normálního“ textu (zprávy atp.) ke spamu není příliš efektivní. Slova v něm budou mít hodnocení kolem 0.5 a nejspíš tedy, díky braní v úvahu pouze „zajímavých“ slov, do konečného hodnocení vůbec nezasáhnou. Spammeři by se museli trefit do slov, která se často vyskytují ve vaší nespamové poště. Jelikož je ale databáze individuální pro každého příjemce spamu, a spammeři ji neznají, je to nemožný úkol. Pokud je takovýto „normální“ text navíc (v HTML) extra malým písmem, bíle na bílém pozadí atp., spammeři jen usnadňují identifikaci spamů, protože toto jsou prvky, které se v hamech skoro nevyskytují.

Jedinou metodou, která má alespoň minimální účinnost, je kombinace „normálního“ textu s tím, že spam je celý v obrázku a je odkazem jinam. Ale i tam se dobře napsaný bayesovský filtr může chytit na URL a na fakt, že e-mail má v sobě obrázek a ten je odkazem jinam. Rovněž v takovýchto případech hodně pomáhají hlavičky. Spam se z nich dá poznat podle přítomnosti/nep­řítomnosti různých položek, podle serverů, přes které e-mail šel, podle odesílatele, a především podle předmětu, do kterého se obrázek dát nedá a který přitom musí zaujmout.

O bayesovských filtrech by se toho dalo napsat ještě mnohé; tento článek byl pouze lehkým úvodem do problematiky. Pokud by to někoho zajímalo, mohu napsat jeho další pokračování.

Anketa

Kolik spamu denně Vám bayesovské filtry pustí?

Našli jste v článku chybu?

2. 3. 2005 12:18

Michal Kára (neregistrovaný)
Jo je, tuhle moznost jsem zapomel dodat. Mozna je to lepsi (logictejsi), ale mne to prislo jako prilis velky anglicismus.

P.S.: ad P.S.: Ano ;-)

DigiZone.cz: Sat novinky: Je tu Sky Sport News HD

Sat novinky: Je tu Sky Sport News HD

Měšec.cz: Jak levně odeslat balík přímo z domu?

Jak levně odeslat balík přímo z domu?

DigiZone.cz: Zdeněk Gerlický: nový ředitel nangu.tv

Zdeněk Gerlický: nový ředitel nangu.tv

Vitalia.cz: Nejlepší obranou při nachlazení je útok

Nejlepší obranou při nachlazení je útok

Vitalia.cz: Mondelez stahuje rizikovou čokoládu Milka

Mondelez stahuje rizikovou čokoládu Milka

120na80.cz: Stoná vaše dítě často? Upravte mu jídelníček

Stoná vaše dítě často? Upravte mu jídelníček

Podnikatel.cz: Chaos u EET pokračuje. Jsou tu další návrhy

Chaos u EET pokračuje. Jsou tu další návrhy

Měšec.cz: Vklad na cizí účet je draze zpoplatněn (přehled)

Vklad na cizí účet je draze zpoplatněn (přehled)

Root.cz: Telegram spustil anonymní blog Telegraph

Telegram spustil anonymní blog Telegraph

Podnikatel.cz: Alza.cz má StreetShop. Mall.cz více výdejních míst

Alza.cz má StreetShop. Mall.cz více výdejních míst

Root.cz: Nová třída SD karet A1 s vysokým výkonem

Nová třída SD karet A1 s vysokým výkonem

Podnikatel.cz: Udávání kvůli EET začalo

Udávání kvůli EET začalo

Podnikatel.cz: Vládu obejde, kvůli EET rovnou do sněmovny

Vládu obejde, kvůli EET rovnou do sněmovny

Podnikatel.cz: Daňové úlevy s EET nestačí. Budou zdražovat

Daňové úlevy s EET nestačí. Budou zdražovat

120na80.cz: Co všechno ovlivňuje ženskou plodnost?

Co všechno ovlivňuje ženskou plodnost?

Root.cz: Mirai má nový cíl 5 milionů routerů

Mirai má nový cíl 5 milionů routerů

Vitalia.cz: To nejhorší při horečce u dětí: Febrilní křeče

To nejhorší při horečce u dětí: Febrilní křeče

120na80.cz: 5 nejčastějších mýtů o kondomech

5 nejčastějších mýtů o kondomech

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Podnikatel.cz: Chtějte údaje k dani z nemovitostí do mailu

Chtějte údaje k dani z nemovitostí do mailu