www.eserv.ru // StatisticalSpamFiltering

oldwiki /2007-10-10 05:56/ (v1)
Продукты и услуги Скачать Документация Купить Поддержка Форумы Партнёрам Статьи О компании
News
15.05.2012
Eserv504
15.05.2012
ActiveSync
01.04.2012
Eproxy508
25.03.2012
Eserv503
26.02.2012
Eserv502
08.02.2012
UMI.CMS
22.12.2011
Eserv431
20.12.2011
Eproxy507
15.11.2011
Eproxy506
19.09.2011
Eproxy505
08.09.2011
Eserv430
07.09.2011
Lightning
19.07.2011
PoweredBy
16.07.2011
IPv6
08.07.2011
Eproxy5beta1
17.06.2011
IPv6DNS
13.06.2011
IPv6Mail
21.03.2011
Eserv428
22.10.2010
Eserv426
22.10.2010
SSL
22.04.2010
Eserv423
20.04.2010
Eserv4WhatsNew
19.04.2010
EservLDAP
19.04.2010
EservDHCP
19.04.2010
EservRubricator
08.04.2010
EservDNS
08.04.2010
NSСI
08.04.2010
WPAD
27.03.2010
Eserv422
27.03.2010
Eserv4Docs
26.03.2010
Eserv4FAQ
21.03.2010
EservIrc
05.03.2010
Eserv421
05.03.2010
HttpProxy
02.03.2010
EservVideo
02.12.2009
Eserv4Wiki
02.12.2009
Eserv4acWEB
02.12.2009
PopPull
22.11.2009
PigMailPigProxy2/WhatsNew
22.11.2009
PigMail/WhatsNew
23.09.2009
FossilEservHowTo
22.09.2009
SourceCodeManagement
22.09.2009
FossilScm
16.09.2009
SendEmail
08.09.2009
RoundCube
07.05.2009
GitScm
07.05.2009
GitEservHowTo
06.05.2009
SunBird

Статистические (вероятностные) методы фильтрации спама

TOC

Неэффективность традиционных фильтров

Существует множество традиционных способов защиты от спама — черные списки 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, и перейду сразу к тому фильтру, который выжил на моём сервере в результате естественного отбора и показал замечательную эффективность в процессе многомесячной эксплуатации как на стороне почтовых клиентов, так и на сервере (последние полгода — на сервере). Это POPfileOpenSource (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#article2
AndreyCherezov /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 — байесы бывают разные

Работает на Eserv/7.0.beta1/Linux/arm64 (Dec 25 2023)