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

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 (p_spam), 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 (p_ham), 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-p_spam.

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 (p_spam). 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ž p_spam 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í.