Статистические (вероятностные) методы фильтрации спама
Неэффективность традиционных фильтров
Существует множество традиционных способов защиты от спама — черные списки IP-адресов отправителей (RBL), черные списки Email-адресов отправителей, черные списки слов, поиск типичных спам-сигнатур (названий используемых программ массовой рассылки, особенностей форматирования html и т.д.) в заголовках и телах сообщений. Все они с тем или иным успехом используются в большинстве спам-фильтров, и эти спам-фильтры уже работают на большинстве крупных почтовых серверов, причем не первый год. Однако проблема спама остается актуальной и даже продолжает обостряться. Следовательно спамеры научились эффективно обходить такую защиту.Самое неприятное, что обойти такие фильтры и на самом деле не сложно. Спамеры ставят себе самые популярные спам-фильтры и могут перед рассылкой пропустить своё письмо через фильтры и проверить, как они срабатывают, и на что они срабатывают. После этого достаточно немного изменить заголовки письма и текст, и письмо готово к "просачиванию" через большинство фильтров, проверяющих содержание писем. На пути такого письма остается небольшая преграда в лице RBL. Для её обхода спамер может применить те же средства — не пользоваться теми IP, которые занесены в RBL (спамерская программа может проверять это также, как и антиспамерская
. К счастью для спамеров и к несчастью для нас в интернете слишком много слабозащищенных компьютеров, которые могут использоваться для передачи спама. Современные вирусы помогают спамерам устанавливать открытые прокси на чужих компьютерах и предоставляют спамерам потенциально сотни тысяч компьютеров для их черного дела. IP этих новых источников спама не могут блокироваться в RBL немедленно: во-первых, кто-то должен сообщить RBL-сервису этот новый IP, потом RBL-сервис проверяет, действительно ли он "имеет право" включить этот IP в свой черный список в соответствии со своей политикой (что он блокирует — OpenRelays (ORDB), OpenProxy, DUL, RFC-ignorant, и т.д.) — время уходит, и за это время спам уже разослан, и спамер может сменить используемые IP (чужие серверы), как перчатки. Страдают от таких черных списков не столько спамеры, сколько владельцы блокируемых IP. Поэтому почтовый сервер, если он блокирует прием почты по RBL, должен в сообщениях об отказе приема почты точно указывать причину блокировки и способ её снятия (обычно указывается URL соответствующего RBL-сайта) — тогда отправитель сможет устранить злоупотребления его компьютером и исключить свой IP из RBL.
Что делать
Как справедливо заметил Paul Graham в своей статье
A Plan for Spam, "ахиллесова пята спамеров — их сообщения. Они могут преодолеть любой барьер, какой вы установите... Но они должны доставить своё сообщение, каким бы оно ни было." Т.е. спамеры могут идти на любые уловки с IP-адресами и подгонкой текста сообщений, но продать-то свою виагру, американский английский, виллу на Канарах и "мужа на час" они вам все-таки должны! Если посланное ими сообщение будет из-за вынужденного применения эзопова языка не понято читателями, то толку от такой рассылки не будет. "Читать между строк" покупатель не будет. Значит они все-таки должны написать в письме нечто понятное, призывающее нас к какому-то действию. Вот за это мы их и ухватим. Научим спам фильтр понимать (ну, почти сообщения. На помощь "искусственному интеллекту" приходит статистическое обучение.
Теорема Байеса наконец пригодилась
Большая Советская Энциклопедия говорит о Теореме Байеса (Б.т.): "Б. т. долгое время рассматривали как основу для статистических выводов из результатов наблюдений. Однако в применениях, как правило, отсутствуют достаточно обоснованные данные об априорных вероятностях гипотез. В силу этого Б. т. потеряла своё значение." Paul Graham дал этой теореме новую жизнь, да такую, которая английскому математику в 18м веке и не снилась: он предложил использовать теорему Байеса для автоматического вычисления вероятности того, что сообщение является спамом.
Для вычисления вероятности спама используются частотные словари, созданные в процессе обучения фильтра. Берется архив старых вручную отсортированных сообщений (почти все ведут свои почтовые архивы, в которых спам либо в папке "удаленные", либо в отдельной папке "спам") и "скармливается" программе обучения. Она вычисляет частотные словари для каждого типа (папки) сообщений — сколько раз какое слово встречалось в письмах этой папки. Когда словари заполнены, вычисление вероятности принадлежности конкретного нового письма к тому или иному типу производится по формуле Байеса для каждого слова этого нового письма. Суммированием и нормализацией вероятностей слов получают вероятности для всего письма. Как правило, вероятность принадлежности к одному из типов намного (на порядки) выше, чем к другим. Вот в эту папку сообщение и отправляется. Это кажется удивительным, но практически сразу после начального обучения фильтра точность определения спама этим методом достигает недостижимой для традиционных фильтров величины — 97-99% и продолжает уверенно двигаться к 100% по мере дальнейшего дообучения. Это обучение состоит в обработке случаев неправильной классификации — фильтру указывается, к какому типу следует впредь относить эти письма, и он добавляет слова из этих писем в соответствующие частотные словари. Обратите внимание — пользователю фильтра не приходится вручную анализировать письмо и пополнять на основе анализа списки правил фильтрации, как это делается в традиционных фильтрах. Достаточно одного щелчка мыши — и статистический "портрет" письма меняется полностью автоматически. Эта способность байесового фильтра к обучению впечатляет: если бы у вас был человек-помощник, который классифицировал вашу почту, то он бы обучался тем же способом ("впредь считай такие письма спамом"), и врядли с лучшим качеством работы. "Искусственный интеллект" оказался на высоте.
Проблема ложных срабатываний
Ложные срабатывания — беда любых спам-фильтров. Причем главная! Различают два вида ложных срабатываний: false positive — неверное зачисление письма в спам, т.е. собственно ложное срабатывание, и false negative — неверное причисление письма к не-спаму, т.е. "ложное не срабатывание". В случае байесового фильтра "ложное не срабатывание" — не проблема — один раз указать фильтру, что это спам, и больше вы подобных писем не увидите. А вот false positive практически сводит на нет эффект борьбы со спамом: приходится просматривать папку "спам" в поисках возможно ошибочно попавших туда важных писем. Далее можно дообучить спам-фильтр — "это не спам" — и в будущем ложных срабатываний станет меньше. Но сам факт того, что ложные срабатывания хотя бы теоретически могут иметь место, заставляет заглядывать в папку спам.Есть ли метод, позволяющий надежно исключить ложные срабатывания — настолько надежно, чтобы вам не приходилось просматривать список спам-писем, так же как сейчас вы не просматриваете список присланных вам вирусов? Есть! Кстати, у антивирусов тоже, хоть и не часто, бывают ложные срабатывания, и этот метод в равной степени поможет исключить и их.
Суть метода исключения ложных срабатываний лежит на поверхности. Более того, его "поддержка" изначально предусмотрена в протоколе SMTP! Проблема только в том, что далеко не все почтовые серверы способны его реализовать — просто в силу своих архитектурных ограничений. И в том, что агенты передачи почты (MTA, т.е. программы, передающие почту между SMTP-серверами) способны иногда запутать дело расплывчатой диагностикой. В чем состоит метод: почтовый сервер сразу после приема письма, еще до отключения MTA-отправителя, должен классифицировать письмо — спам/вирус/нормальное — и в случае спама или вируса сразу же в ответ на команду DATA (посылающую тело письма) ответить не кодом "250 ок, письмо принято для доставки", а кодами 4хх (временная ошибка) или 5хх (фатальная ошибка). Например, "550 ваше письмо классифицировано как СПАМ, оно не будет доставлено! Если это ошибка, то посетите URL такой-то для проталкивания вашего письма." Раз вирусы и спам и в самом деле фактически не доставляются получателям из-за остановки их фильтрами, то можно сказать, что такое поведение почтового сервера является его ОБЯЗАННОСТЬЮ — он обязан сказать во время почтовой сессии, что не будет доставлять принятое письмо. MTA отправителя, получив код 5хх, САМ вернет письмо отправителю — и процитирует в возвращенном письме это сообщение сервера "5хх это спам", и отправитель, таким образом, будет иметь возможность активно влиять на судьбу своего письма — посетит указанный URL и "подтолкнет" письмо получателю. И фильтр в результате обучится не считать это спамом впредь. Таким образом получателю уже не придется просматривать папку "спам" для поиска ложных срабатываний — ложное срабатывание "разрулит" сам отправитель!
Обратите внимание, принимающий сервер не высылает отправителю спам-письма никаких писем-извещений — это способно только увеличить количество бесполезных писем в сети, т.к. вирусы и спамеры подделывают обратный адрес. Он всего лишь говорит отправляющей программе "я не буду доставлять это письмо". А вернет письмо "хозяину" сама отправляющая программа. Причем ЕСЛИ ОТПРАВИТЕЛЬ НЕ СПАМЕР! Если письмо отправляла спамерская программа массовой рассылки, то она не возвращает писем при получении отрицательных ответов принимающей стороны. Т.е. непричастные к этому спаму люди, даже если их адрес используется спамером как фиктивный обратный адрес спама, никаких извещений о чужом спаме не получат.
Таким образом, байесовый фильтр, интегрированный с почтовым сервером, способен отфильтровывать 99% процентов спама и гарантировать отсутствие ложных срабатываний. Т.е. спам, как и вирусы, теперь можно оставлять на сервере "на всякий случай", а почтовым клиентом качать только отфильтрованную почту. Если вы получаете 200 нормальных писем в день, то среди них будет не больше 2-3 спам-писем, которые вы будете отправлять на дообучение спам-фильтру одним движением мышки. Мечта осуществилась!
Спамеры, конечно, начнут изучать статистику , но у них никогда не будет частотных словарей вашего фильтра.
Прежде чем перейти к описанию существующих статистических фильтров и способов их интеграции с почтовыми серверами для исключения ложных срабатываний, должен рассказать об оставшейся капле дёгтя в этой бочке мёда. Только эта капля и не позволяет назвать этот фильтр идеальным решением. Это случай почты от "неспамерских роботов". Т.е. почты от списков рассылки, на которые вы подписаны, почты с уведомлениями с сайтов, с которыми вы работаете (форумов, например) и т.п. авто-сообщений. Ложные срабатывания в обработке такой почты не могут быть исправлены отправителем, т.к. отправитель не обрабатывает такие отказы. В результате приходится держать на контроле первые письма от нового робота в тот момент, когда вы ожидаете их прихода — это делается легко, если почтовый сервер предоставляет список email'ов остановленных спам-писем. Если ожидаемое извещение не пришло, то придется разбираться с этим ложным срабатыванием вручную — и не забыть дообучить фильтр не считать это впредь спамом. Можно, конечно, и заблаговременно поставить нужного отправителя в белый список: некоторые сервисы рассылок (например, subscribe.ru) позволяют задать уникальный адрес отправителя для вашей подписки, чтобы исключить возможность его подделки спамерами. Но лучше именно "честно" обучать фильтр, не давая ему подсказов в виде черно-белых списков. Потраченное на обучение фильтра время с лихвой окупится повышением качества его словарей и экономией времени в будущем.
Применение на практике
Байесовые статистические фильтры были самым модным направлением развития антиспам-фильтров за год, прошедший со времени публикации революционной статьиA Plan for Spam (с августа 2002). Одного перечисления этих инструментов хватило бы на целую статью. Поэтому ограничусь ссылкой на отдельную страницу сайта со списком — BayesianSpamFilteringSoftware, и перейду сразу к тому фильтру, который выжил на моём сервере в результате естественного отбора и показал замечательную эффективность в процессе многомесячной эксплуатации как на стороне почтовых клиентов, так и на сервере (последние полгода — на сервере). Это POPfile — OpenSource (GPL) программа, вы можете использовать её совершенно свободно. Есть версии для Windows и для других ОС, версии для встраивания в Outlook, версии для работы в качестве Pop3proxy, SmtpProxy, NntpProxy или просто в виде "сервера классификации текстов" для использования любыми внешними программами — интеграция через поддерживаемый всеми языками программирования интерфейс XMLRPC.
В идеале фильтр нужно ставить на SMTP-сервере так, чтобы классификация письма выполнялась сразу по получении его в SMTP-команде DATA. Во всех популярных почтовых серверах есть средства подключения внешних фильтров содержания — Content Filter API (см. SendmailMilter, PostfixContentFilter, EximContentFilter). В нашем Eserv/3 вирусные и спам-фильтры подключаются через список правил smtpOnMessageEnd. Если на той же машине работает веб-сервер, то можно реализовать описанную выше возможность исправления ложных срабатываний отправителем: почтовый сервер должен откладывать отвергнутый спам в специальный каталог, доступный скрипту переклассификации на веб-сервере и сообщать MTA, отправившему спам, URL на своем сервере, где можно протолкнуть письмо получателю. Для Eserv/3 есть готовый plugin, интегрирующий PopFile в таком режиме (в Eserv/3 входит и веб-сервер). Как это работает на практике — вы можете проверить, отправив тестовое письмо со спамерским содержимым на мой адрес ac@eserv.ru
Для MS Exchange тоже есть скрипт (VB) подключения PopFile через XMLRPC — Tom Voss написал его по моей "наводке". Для других почтовых серверов готовых plugin'ов для PopFile я не встречал, но наверняка они появятся после выхода PopFile 0.20 или 0.21 — как раз сейчас разработчики PopFile дорабатывают средства интеграции. XMLRPC-API-интерфейс сейчас еще не входит в "официальную" версию PopFile — мы используем версию с CVS-сервера, находящуюся в разработке. Полный комплект необходимых файлов для запуска PopFile в серверном режиме можно скачать и на нашем сайте на странице PopFile.
Обработка "ложных не срабатываний" (false negatives, неотфильтровавшийся спам) PopFile в Eserv/3 делается в IMAP-сервере: когда пользователь (читатель) перемещает сообщение в папку с именем "spam", IMAP-сервер запускает на сервере дообучение PopFile — "впредь считать такое спамом" (тоже через XMLRPC-интерфейс PopFile).
Использование PopFile в качестве Pop3Proxy для работы с почтовыми клиентами — т.е. на машинах пользователей, а не на сервере — хорошо описано в статье
http://notes.rusc.ru/notes/27
Будущее
PopFile настолько эффективен, что позволяет отказаться от других методов фильтрации спама (вы убедитесь в этом, когда попробуете), однако и этот метод постоянно совершенствуется. Последний "писк моды" — новый статистический метод, использующий "Хи-квадрат распределение". Впервые он был использован в спам-фильтре SpamBayes, но недавно реализован и в PopFile. В SpamBayes хи-квадрат стал основным методом, хотя раньше, как следует из названия программы, основным был байесов метод. В PopFile хи-квадрат используется пока только как дополнительный тест для добавления в фильтр уровня "неуверенности". Теорема Байеса дает однозначную характеристику письма, основываясь на имеющихся частотных словарях — всегда можно точно вычислить, какая вероятность больше, и к какому типу сейчас следует отнести письмо. Ситуация "невозможно классифицировать" была искусственно введена в PopFile установкой минимально приемлемой вероятности для вынесения решения. Хи-квадрат вероятности позволяют математически выявить степень неуверенности фильтра в однозначном решении. Это позволяет уменьшить к-во ложных срабатываний, не уменьшая при этом процент верных срабатываний. В этом режиме некоторая часть писем, которая по Байесу попала бы в спам вместе с гарантированно спамерскими письмами, попадает в папку "не уверен", т.е. "требует ручной проверки и классификации".Просачиваются через PopFile сейчас только сообщения в виде картинок, без текста. И то лишь редкие из них — ведь сам html-код, несущий картинку (и URL рекламируемого сайта в этом коде), и заголовок письма (с IP-адресами, подставными Email'ами и Subject) — все является простым текстом, и этого обычно хватает PopFile для правильной классификации. Бывает достаточно ОДНОГО слова с большим статистическим спам-весом для вынесения решения. Кроме того, PopFile пытается заглядывать и внутрь картинок — не OCR'ит их, конечно, а просто "не понимает", что это картинка, и ищет текст в двоичном файле — и словесный портрет картинки тоже попадает в частотные словари. Может это и не предусмотренная специально возможность, но это тоже срабатывает против спама.
Вообще теорему Байеса можно использовать для авто-классификации любых текстов по любым категориям — любому их количеству, а не только спам/не_спам/не_уверен. Я, например, свою почту классифицирую с помощью PopFile по 8-ми категориям. PopFile — единственный фильтр, который дает возможность использования более 3х категорий, и поэтому может иметь более широкое применение, чем тривиальная фильтрация спама. Например, для классификации текстов поисковой машиной. Статистическую классификацию можно с успехом применять и для классификации изображений — если считать цвет точки "словом". И видимо для автоклассификации вообще чего угодно, вероятности чего в принципе можно посчитать (вспомните цитату из БСЭ про вероятности гипотез, например). Статистическая классификация несомненно станет одним из основных методов классификации контента в интернете.
--
AndreyCherezov /05.09.2003 14:19/
См. также Статьи
AndreyCherezov /16.12.2003 04:07/
SpamTest.ru опубликовал эту нашу статью в рассылкеAndreyCherezov /17.12.2003 12:14/
... и на сайтах spamtest.ru и kasperskylabs.ru AndreyCherezov /10.10.2007 01:56/ Ссылка изменилась: http://www.kaspersky.ru/news?id=144772578#article2AndreyCherezov /03.03.2004 15:37/
Google использует Байесовы фильтры в своём поисковике, т.е. подтвердились слова моей статьи о возможности использования байесовой классификации в поисковой машине.AndreyCherezov /10.03.2004 09:01/
В сегодняшней рассылке spamtest приводятся цитаты обсуждения спамерами этой моей статьи (без ссылки на источник цитаты) и признания спамерами байесового фильтра как самого эффективного. Со своей стороны отмечу, что рекомендуемый там способ борьбы с фильтрами — рассылка спамерами сообщений с не-спам содержимым наряду со спамом (для порчи словарей фильтров) — мало эффективен, т.к. переклассификации ложных срабатываний проходят проверку антиспам-админом и "анекдоты" в спам-словари не попадут.AndreyCherezov /07.09.2005 21:32/ См. SpamProtexxPlugin — серверная версия отечественного спам-фильтра SpamProtexx для Eserv/3. Используется "в бою" с марта 2005 г, рекомендуется всем.
AndreyCherezov /15.09.2006 14:22/
http://www.ceas.cc/2006/15.pdf , http://www.ceas.cc/2006/presentations/bayes.pdf — байесы бывают разные
