CADENCE's Bayes_filtering

Bayes wiecznie żywy

5 kwietnia 2004

Dotychczasowe metody walki ze spamem okazały się z punktu widzenia użytkowników systemów pocztowych nieskuteczne. Wygląda jednak na to, że rozwiązaniem problemu są algorytmy matematyczne odkryte jeszcze w dziewiętnastym wieku.

Tomasz Grabowski

Zaczyna się niewinnie: jeden, dwa listy dziennie. Wykasowanie kilku maili informujących o świetnym biznesie w Nigerii czy dużej wygranej na loterii nie sprawia większych problemów. Jednak firmy zajmujące się „promocją przez Internet” wymieniają się posiadanymi adresami i z czasem listów przybywa. Gdy do skrzynki trafia 100-200 listów dziennie, kasowanie spamu staje się przymusowym porannym rytuałem – człowiek przyzwyczai się do wszystkiego.

Nerwy puszczają zwykle któregoś pięknego poranka, gdy walcząc z powodzią niechcianej korespondencji przez nieuwagę kasujemy ten jeden ważny list, na który czekaliśmy. Zwykle dopiero wtedy uświadamiamy sobie, że spam stanowi realne zagrożenie dla biznesu: zwiększa prawdopodobieństwo przeoczenia ważnego listu, odrywa ludzi od produktywnej pracy, a ponadto zapycha łącza do Internetu i zmniejsza wydajność serwerów pocztowych.

Strach przed czarną listą

Najstarszą metodą walki ze spamem jest powiadamianie administratorów sieci, z których spam jest wysyłany. Wymaga to jednak szeregu zabiegów ze strony administratora: dodatkowych kontaktów z użytkownikami systemu pocztowego, analizy nagłówków niechcianych listów, wyszukiwania kontaktów do administratorów innych sieci, dodatkowej korespondencji z nimi. Część tych czynności można zautomatyzować pisząc odpowiednie skrypty, nadal jest to jednak zajęcie bardzo niewdzięczne i bez jakiejś formy automatyzacji na dłuższą metę wytrzymać się nie da.

Jedną z prostszych technik walki ze spamem na poziomie serwera poczty, jest korzystanie z tzw. czarnych list (black lists) – tworzone przez ochotników i wymieniane między administratorami spisy domen, w których działają źle skonfigurowane systemy pocztowe umożliwiające wysyłanie spamu. Znalezienie się domeny na takiej liście to dla jej administratora środowiskowy wstyd i zwykle powód do natychmiastowego działania. Czarne listy nie są jednak panaceum na spam.

Z listami wiąże się też realne niebezpieczeństwo, że niekiedy poszczególne adresy mogą na nie trafić przez pomyłkę lub nawet czyjeś celowe działanie. Nieostrożne korzystanie z czarnych list może więc skończyć się tym, że w pewnym momencie dostęp do sieci zostanie odcięty użytkownikom na których obsłudze nam zależy, np. klientów. Wielokrotnie przeprowadzane testy wykazują ponadto, że metoda ta pozwala wyeliminować w najlepszym razie około 50% spamu, a najczęściej dużo mniej – w granicach 15-25%. Atrakcyjne jest głównie to, że jest ona niezmiernie prosta w implementacji, dlatego można ją traktować jako pierwszy krok w walce ze spamem. Warto w tym celu skorzystać z odpowiedzialnie prowadzonej listy, np. The Spamhaus Block List.

Z reguły nieskutecznie

Stosowaną z powodzeniem techniką walki ze spamem jest filtrowanie nagłówków i treści listów na poziomie bramki pocztowej lub serwera pocztowego. Filtry dzielą się na takie, które posługują się sygnaturami (wzorcami) oraz takie, które analizują zawartość listu według pewnych ogólniejszych kryteriów (skanery oparte na regułach, zwane niekiedy heurystycznymi).

Bieżącym tworzeniem wzorców zajmują się wyspecjalizowane firmy. Przykładowo firma Brightmail utrzymuje ponad 2 miliony kont pocztowych, na które przychodzi dziennie ok. 2 miliardy spamerskich przesyłek. Dla każdego z tych listów tworzona jest sygnatura, która ląduje w bazie danych dostępnej dla klientów. Jeśli do klienta trafi list podobny do tego, który został opisany w sygnaturze, zostanie on oznaczony jako spam. Oczywiście spamerzy są tego świadomi i stosują metody, które mają za zadanie zmylenie filtrów (np. do każdego listu wstawiają jakieś losowe słowo, aby różnił się od wzorca zawartego w sygnaturze). Spam nadal płynie więc szerokim strumieniem, napędzany nieustanną kreatywnością spamerów, a twórcy oprogramowania antyspamowego ciągle wydają nowe sygnatury.

Ten wyścig wydaje się nie mieć końca – podobnie jak nie widać końca zapału ludzi do pisania wirusów. Biorąc jednak pod uwagę fakt, że skuteczność tego typu filtrów oceniania jest na około 50-70%, wygląda na to, że w tym wyścigu spamerzy są cały czas o krok z przodu. Filtry wymagają też ciągłego utrzymywania odpowiedniej infrastruktury umożliwiającej tworzenie sygnatur, w związku z czym są to rozwiązania raczej drogie – wspomniane oprogramowanie firmy Brightmail kosztuje 1500 USD rocznie za licencję dla 50 użytkowników. Mocną ich stroną jest jednak to, że nie ma w praktyce możliwości, aby list, który nie jest spamem, został przez oprogramowanie jako taki zakwalifikowany. Jest to więc bardzo istotny czynnik dla firm, których funkcjonowanie związane jest z nawiązywaniem kontaktu z nowymi klientami za pomocą poczty elektronicznej.

Filtry oparte na regułach działają na nieco innej zasadzie. Najczęściej nie przechowują żadnej bazy danych, którą trzeba by na bieżąco uaktualniać. Zamiast tego analizują treść każdego listu według pewnych kryteriów. Sprawdzają np. czy list pisany jest wielkimi literami, czy występują w nim pewne słowa kluczowe najczęściej występujące w spamie jak np. „YOU WON”, „SEX”, „VIAGRA”, do ilu osób jest adresowany, czy zawiera odnośniki do zewnętrznych stron i do jakich itp. Każda z reguł ma przypisaną odpowiednią wagę wyrażoną pewną ilością punktów. Jeśli list zbierze zadaną ilość punktów (np. zawiera „podejrzane” słowa kluczowe oraz linki do zewnętrznych stron) to jest on oznaczany jako spam. Skuteczność takich filtrów jest już całkiem zadowalająca – oscyluje w granicach 90-95% - dotyczy to jednak tylko najlepszego oprogramowania tego typu, takiego jak bardzo popularny SpamAssasin rozwijany na zasadach open source.

Nie ma niestety róży bez kolców. Okazuje się, że tego typu filtry posiadają tendencję do oznaczania jako spam listów, które trudno zaliczyć do tej kategorii. Odsetek takich źle sklasyfikowanych listów sięga około 0.5%, co w większości przypadków jest wynikiem niedopuszczalnym, skutkuje bowiem „wycinaniem” uprawnionej korespondencji. Dodatkowo z racji tego, że oprogramowanie to korzysta z konkretnych algorytmów, przed wysłaniem konkretnego listu spamerzy mogą po prostu sprawdzić, czy zdoła on prześlizgnąć się przez dostępne filtry. Szanse na oszukanie filtra są w praktyce spore.

Centralnie i w rozproszeniu

Centralne filtrowanie poczty na serwerze, który nierzadko obsługuje kilkaset lub kilka tysięcy kont pocztowych, nie może być jednak uważane za skuteczne. Łatwo bowiem wyobrazić sobie, że w zasadzie każdy użytkownik posługuje się innym „rodzajem” listów. Np. używa różnych języków, korzysta z list dyskusyjnych, wysyła wiele załączników lub w treści jego listów często znajdują się linki do innych stron – słowem nie sposób jest skonfigurować centralnego filtra poczty w sposób, który brałby pod uwagę wszystkie możliwe preferencje. Na szczęście, w wielu pakietach istnieje możliwość udostępnienia użytkownikom narzędzi do samodzielnej konfiguracji.

Wspomniany wcześniej SpamAssasin udostępnia pewne możliwości konfiguracji. Jeżeli np. w poczcie przesyłane jest wiele odnośników do witryn WWW, możemy zmniejszyć ilość punktów wagowych przyznawanych tego typu listom i tym samym zmniejszyć szansę na to, że jakiś ważny list zostanie uznany jako spam. Podobnie, jeśli np. nigdy nie używamy języka innego niż Polski, możemy zwiększyć ilość punktów, które będą otrzymywały listy zawierające słowa w innych językach. Dzięki temu skuteczność filtra zostanie w prosty sposób zwiększona. Niezależnie można też samodzielnie tworzyć nowe reguły. W pakiecie SpamAssasin robi się to przy pomocy wyrażeń regularnych.

To, że możliwość dostosowania do preferencji użytkownika jest kluczowa dla jakości filtrowania producenci zrozumieli już dawno i w tym kierunku zmierzają w zasadzie wszystkie wiodące systemy antyspamowe. Ideałem byłoby oprogramowanie, które uczyłoby się samo jakie listy użytkownik uważa za spam, a jakie za normalną pocztę. Powinno dostosowywać się do zmian zarówno w samym spamie, jak też w preferencjach użytkownika. Najlepiej byłoby także, gdyby oprogramowanie to wymagało jak najmniej konfiguracji i działań ze strony samego zainteresowanego.

Utopia? Okazuje się, że nie. Najnowsze oprogramowanie do walki ze spamem zaprzęga bowiem do pracy sieci neuronowe. Rozwiązania takie posiadają pewne zdolności uczenia się i przewidywania wyników na podstawie wcześniej zdobytych informacji. W powiązaniu z narzędziami do analizy statystycznej podejście to sprawdza się w walce ze spamem. Dochodzimy więc do kolejnego rodzaju oprogramowania antyspamowego czyli tzw. Bayesian Filtering. Nazwa pochodzi od Thomasa Bayes’a – osiemnastowiecznego twórcy koncepcji analizy statystycznej (patrz ramka).

Pomysł na wykorzystanie do filtrowania nie jest nowy – jego korzenie sięgają 1996 r., a tak naprawdę technik analizy statystycznej opracowanych przez Dopiero jednak ostatnio udało się wypracować algorytmy, które dobrze sprawdzałyby się w przypadku filtrowania spamu. Prawdziwa eksplozja tego typu oprogramowania rozpoczęła się tak naprawdę pod koniec 2003 r. Najnowsze wersje programów wykorzystujące filtrowanie oparte na koncepcji Bayes’a mają współczynnik skuteczności na poziomie 99,98%! Dodatkowo ilość „dobrej” korespondencji klasyfikowanej przez te filtry jako spam jest praktycznie zerowa. Skąd biorą się tak dobre rezultaty?

Użytkownik decyduje sam

Filtr oparty na algorytmie Bayes’a działa następująco. Dla każdego użytkownika na serwerze pocztowym lub w oprogramowaniu klienckim tworzone są dwa pliki. W jednym przechowywane są informacje dotyczące listów uznanych za spam, w drugim zaś pozostałych. Początkowo pliki te są puste, użytkownik musi bowiem „nauczyć” oprogramowanie odróżniać spam od właściwej poczty. Proces ten wygląda różnie w zależności od tego jakiego oprogramowania używamy.

W większości programów instalowanych na serwerze odbywa się w taki sposób, że po otrzymaniu listu użytkownik wysyła go z powrotem na swoje konto z adnotacją czy jest to spam, czy też normalny list (tak działa np. w darmowe oprogramowane o nazwie CRM114). Czasami też zamiast przesyłać cały list, wystarczy przesłać tylko jego sygnaturę (tak działa inny pakiet – również darmowy – o nazwie Dspam). W przypadku niektórych pakietów komercyjnych, jak np. SpamBully (cena ok. 30 USD za jedno stanowisko) wystarczy tylko jedno kliknięcie. Bez względu na metodę oznaczania spamu przez użytkownika, wszystkie te programy działają podobnie.

Najczęściej wykorzystywana przez filtry Bayes’a metoda uczenia się zwana jest Train Only Errors (TOE). Oznacza to, że programowi wskazywane są tylko te listy, przy klasyfikacji których popełnił błąd. Na początku program popełnia oczywiście dużo błędów i jego używanie może się wydawać kłopotliwe. Pojawia się więc pytanie jak szybko odczujemy korzyści płynące ze stosowanie filtrowania Bayes’a. I tu kolejne zaskoczenie. Okazuje się, że po sklasyfikowaniu kilkudziesięciu listów, program jest skuteczny już w ponad 90% swoich decyzji. Sklasyfikowanie około 100 – 150 listów pozwala osiągać skuteczność na poziomie przekraczającym 95%. Po miesiącu używania programu ponad 99% listów jest klasyfikowana poprawnie. Czy warto czekać tak długo?

Zdecydowanie tak! Kiedy już filtr nauczy się odróżniać pocztę od spamu, jego skuteczność już na zawsze pozostanie wysoka. Co więcej, ponieważ program uczy się cały czas, zmiany w sposobie tworzenia spamu jak i charakteru tworzonej i odbieranej „poprawnej” poczty są na bieżąco uwzględniane. Inaczej mówiąc, dzięki wskazówkom otrzymywanym od użytkownika program ewoluuje wraz z jego potrzebami.

Niezbyt wydajnie, ale skutecznie

Pliki, w których przechowywane są informacje pozwalające odróżniać spam od normalnej poczty zajmują zwykle od kilku do kilkudziesięciu Megabajtów. Dopóki pliki są przechowywane na komputerach klienckich problemów z wydajnością czy pojemnością dysków raczej nie ma. Przechowywanie tak dużych plików na serwerze pocztowym może już jednak spowodować konieczność dokupienia dodatkowych dysków. Jeśli chodzi o potrzebną moc procesora, to najszybsze obecnie programy pozwalają sprawdzać nadchodzącą pocztę w tempie około 120 KB/s (pomiary na serwerze z 1 procesorem Pentium III 1,4 GHz). W przypadku dużych instalacji serwerowych konieczne wydaje się zbudowanie farmy równoważącej obciążenie.

Skoro filtry Bayes’a są aż tak skuteczne, pytanie brzmi: jak trudno jest spamerom skonstruować list, który przejdzie przez nasz filtr. Z racji tego, że ten sposób obrony przed spamem jest na razie rzadko stosowany, trudno wysnuć wnioski, co do jego skuteczności w przyszłości. Jedno jest jednak pewne – fakt, że tego typu filtry są dostosowane do indywidualnych wymogów użytkowników powoduje, że skonstruowanie listu, który przeszedłby wszystkie filtry jest w zasadzie niemożliwe.

Istnieją propozycje pomagające w zwiększeniu prawdopodobieństwa, że dany list przejdzie dużą część filtrów, jednak wszystkie one wymagają utrzymywania swego rodzaju bazy danych na temat tego jakie listy należy wysyłać pod konkretne adresy. Z racji tego, że na 1 milion wysłanych listów spamowych odpowiada od 1 do 5 osób, utrzymywanie takiej bazy jest dla spamerów po prostu nieopłacalne. Poza tym trudno oczekiwać, że użytkownik, który z własnej woli korzysta z takiego oprogramowania odpowie na jakąkolwiek ofertę wysyłaną w ten sposób. Oznacza to, że ten obszar „rynku” konsumentów jest dla spamerów po prostu nieatrakcyjny.

Już teraz widać, że stosowanie tego typu filtrów odnosi skutek. Na przestrzeni ostatnich miesięcy daje się bowiem zauważyć wyraźną tendencję do zmniejszania ilości informacji zawartej w samych listach, a zamiast tego umieszczanie w nich odnośników do witryn WWW. Coraz częściej list spamowy zawiera jedno zdanie „na zachętę” i towarzyszący mu odnośnik, po kliknięciu którego otwiera się właściwa strona z reklamą. Skuteczność tego typu działań jest jednak dużo mniejsza niż zwykłego spamu. Implementacje filtrów Bayes’a istnieją dopiero od niedawna, a jednak ich skuteczność zwiększa się praktycznie z dnia na dzień, dlatego też istnieje realna szansa na to, że spam da się jednak ograniczyć.

Spam zostaje za drzwiami

Jaka przyszłość czeka oprogramowanie antyspamowe? Istniejące obecnie propozycje, takie jak wprowadzenie mikropłatności czy też wymóg przeprowadzenia przez komputer wysyłający szeregu działań matematycznych mających za zadanie zmniejszyć szybkość wysyłania spamu, wymagają zmiany lub rozwinięcia protokołu SMTP. Oznacza to, że nowe rozwiązania będą wymagały nowego oprogramowania. Szansa na to, że większość użytkowników Internetu zdecyduje się na ich zastosowanie jest niewielka.

Inne pomysły, takie jak np. filtry agresywne (filters that fight back) też raczej nie mają przed sobą świetlanej przyszłości. Ich działanie miałoby bowiem polegać na tym, że specjalne automaty nawiązywałyby połączenia z adresami WWW zawartymi w spamie, przeciążając tym samym serwery spamerów. Technika ta niesie jednak ze sobą niebezpieczeństwo wykorzystania jej do ataków typu Distributed Denial of Service.

Prawdziwą szansę na skuteczną walkę ze spamem dają więc chyba tylko filtry Bayes’a. Skoro raptem po kilku miesiącach od powstania ich wczesnych implementacji cechują się one tak wysoką skutecznością, to jakiej skuteczności będziemy mogli oczekiwać od dojrzałych produktów tego typu, które pojawią się na rynku np. za rok?

Z drugiej strony, kto to wie? Być może do tego czasu spamerzy wynajdą nowe techniki pozwalające ominąć tego typu zabezpieczenia. W informatyce bardzo często okazuje się bowiem, że z pozoru niemożliwe do złamania systemy są po jakimś czasie skutecznie oszukiwane. Czy tak będzie w przypadku filtrów Bayes’a przekonamy się prawdopodobnie w ciągu kilkunastu miesięcy. Jedno jest pewne: arsenał środków przeciwko spamerom jeszcze nigdy nie zawierał tak skutecznej broni.

***RAMKA**
Czy na pewno wysłałeś?

Niezależnie od filtrów Bayes’a interesującym sposobem ograniczania spamu jest technika zwana Challenge-Response Filtering. W skrócie polega ona na tym, że do nadawcy listu, który nigdy wcześniej do nas nie pisał, filtr wysyła zapytanie. Dopiero, kiedy nadawca udzieli na nie odpowiedzi (zazwyczaj musi po prostu odesłać list z powrotem) właściwy list jest dostarczany do naszej skrzynki odbiorczej. Ta prosta metoda zatrzymuje ponad 99,9% spamu, choć może być nieco uciążliwa zwłaszcza dla osób korzystających z poczty sporadycznie.

O ile to możliwe, technikę Challenge-Response Filtering najlepiej stosować równolegle z innymi. Najkorzystniejszym rozwiązaniem wydaje się więc zastosowanie filtru Bayes’a lub heurystycznego filtrowania treści opartego na regułach dla wstępnego segregowania poczty, a następnie wykorzystywania techniki Challenge-Response dla listów, które zostały oznaczone jako spam. Dzięki temu można mieć pewność, że nie przeoczyło się żadnej istotnej wiadomości. Wspomniane wcześniej komercyjne oprogramowanie SpamBully działa właśnie w taki sposób. Jeśli chcemy korzystać z oprogramowania open source, musimy połączyć ze sobą funkcjonalność dwóch różnych programów, np. SpamAssasin i Active Spam Killer.

Klasyfikacja wg Bayes’a

Thomas Bayes, osiemnastowieczny brytyjski kleryk opracował metodę pozwalającą, w uproszczeniu, przewidywać prawdopodobieństwo występowania zjawisk w przyszłości na podstawie obserwacji dotychczasowej częstotliwości ich występowania. Metoda Bayes’a jest stosowana m.in. do rozwiązywania problemów sortowania i klasyfikowania danych przy wykorzystywaniu uczenia maszynowego, ale także w bankowości i ubezpieczeniach, a więc wszędzie tam, gdzie występuje ryzyko. Najnowszym zastosowaniem jest klasyfikacja wiadomości e-mail pod kątem spamu.

Twierdzenie Bayes’a mówi, że dla dwóch niezależnych zdarzeń A i B prawdopodobieństwo wystąpienia B, jeśli wystąpiło A wynosi:

P(B|A) = (P(B) * P(A|B)) / P(A) = P(A i B) / P(A),

gdzie:
P(A) oznacza prawdopodobieństwo że wystąpi A
P(A|B) oznacza prawdopodobieństwo, że wystąpi A pod warunkiem że wystąpiło już B
P(A i B) oznacza prawdopodobieństwo tego, że wystąpią zarówno A jak i B

W odniesieniu do spamu za A uznajemy otrzymanie zwykłego listu, zaś za B – listu ze spamem. Powyższy wzór można by więc odczytać następująco: prawdopodobieństwo tego, że nowy list jest spamem, jest równe prawdopodobieństwu tego, że ten konkretny list jest spamem – ustalonemu na podstawie porównania z dotychczas otrzymanymi listami uznanymi za spam, pomnożonemu przez udział normalnych listów w dotychczasowej korespondencji i podzielonemu przez prawdopodobieństwo tego, że list spamem nie jest – ustalonemu na podstawie porównań z listami uznanymi za spam (jw).

W przypadku bankowości, klasyfikację Bayes’a można zastosować do oceny wiarygodności klientów. Można np. stworzyć dwie klasy decyzyjne: pierwsza, to klienci, którzy nie spłacają rat w terminie. Druga, to klienci, którzy sumiennie wywiązują się ze swoich zobowiązań. Gdy pojawi się nowy klient, można szacować prawdopodobieństwo, z jakim znajdzie się on w jednej bądź w drugiej grupie, a na podstawie obserwacji spłaty kredytu modyfikować ocenę jakości przyporządkowania do jednej z dwóch klas.

Na podobnej zasadzie działają także np. katalogi stron WWW w wyszukiwarkach internetowych. W tym przypadku tworzone są odpowiednie grupy tematyczne (np. sport, wiadomości, rozrywka) do których przypisane są odpowiednie strony. Na tej podstawie klasyfikator Bayes’a jest w stanie zdecydować, do której kategorii zaliczyć nowo dodaną stronę.

***RAMKA***
Pakiety wykorzystujące filtry Bayes’a

Komercyjne
    SpamBully ( http://www.spambully.com )
    IronMail 4.0 ( http://www.CipherTrust.com )
    Disruptor OL ( http://www.hlembke.de/prod/disruptor )
    InBoxer ( http://www.inboxer.com )
    InboxShield ( http://www.edovia.com/inboxshield )
    PreciseMail ( http://www.process.com/precisemail
Open source
    SpamAssasin ( http://www.spamassasin.org )
    CRM114 ( http://www.crm114.sourceforge.net )
    Dspam ( http://www.dspam.com )
    POPFile ( http://popfile.sourceforge.net/cgi-bin/wiki.pl )
    SpamTUNNEL ( http://uiorean.cluj.astral.ro )
    SpamProbe ( http://spamprobe.sourceforge.net )
    ifile ( http://www.nongnu.org/ifile/ )

99,98%

Tyle wynosi współczynnik skuteczności filtrów opartych na algorytmie Bayes’a i wciąż się poprawia! Dla porównania metody heurystyczne zapewniają skuteczność na poziomie ok. 90-95%, zaś filtrów opartych na wzorcach – 50-70%.

***RAMKA OPCJONALNA***

Użytkownicy systemów pocztowych mogą zrobić całkiem sporo, by ograniczyć ryzyko umieszczenia ich adresu na spamowych listach wysyłkowych. W pierwszym rzędzie wypada zalecić wykorzystywanie aliasów zamiast rzeczywistych nazw kont, zwłaszcza jeśli adres ma być udostępniony publicznie, np. na witrynie WWW. Można też doradzić unikanie podawania adresu przypadkowym osobom, choć w praktyce, np. w biznesie, jest to raczej trudne. Na pewno jednak warte rozważenia jest unikanie podawania go na listach dyskusyjnych.

Powyższe zabiegi są jednak skuteczne jedynie do momentu, w którym nie popełnimy błędu, lub ktoś z kręgu osób zaufanych wpadnie na pomysł wysłania do nas kartki internetowej z publicznego serwisu. Wniosek jest więc taki, że są to pomocnicze, dodatkowe środki, nie pozwalające na dłuższą metę pozbyć się problemu spamu.