Фильтрация спама по Байесу

Наверное, каждый пользователь, активно пользующийся электронной почтой и "живущий" в интернете несколько лет, сталкивается с проблемой нежелательных массовых рассылок (спама). Особенно если его адрес широко известен, или опубликован на каком-нибудь сайте или доске объявлений...

Поначалу спам не вызывает особых проблем, а лишь лёгкую досаду. Однако с увеличением количества подобных писем даже элементарная операция сортировки почты на "нужное" и "мусор" начинает занимать непозволительно много времени, не говоря уже о том, что весь мусор приходится, к тому же, скачивать из интернета.

В ответ на возникающий в такой ситуации вопрос: "Что делать?", — в интернете можно найти довольно большое количество всевозможных фильтров, защищающих почтовый ящик от мусора. Принципы их работы самые разные. Простейшие содержат некоторую базу "запрещённых" и "разрешённых" слов или фраз, при наличии которых входящее письмо может либо беспрепятственно попасть в ящик, либо же быть безжалостно удалённым ещё на "входе". К одному из вариантов подобной фильтрации относится, в частности, фильтрация по публичным smtp-серверам, которые используют спамеры для своих рассылок. Другой метод блокировки — отправлять в ответ на каждое письмо запрос на подтверждение, в расчёте на то, что хороший человек на него непременно ответит, а спаммеры — проигнорируют.

Недостатки обоих перечисленных методов очевидны: в первом случае используется база слов, которую тоже кто-то должен составлять. Из-за этого по иронии судьбы смысл работы фильтра меняется на противоположный: вместо того, чтобы избавиться от чтения спама, вам как раз приходится читать и анализировать его, пытаясь выявить очередные примечательные слова, которыми можно пополнить базу данных фильтра. Но даже в этом случае, спамеру достаточно в очередной раз написать в письме вместо "корова" -> "карова", чтобы его письмо снова беспрепятственно оказалось в вашем ящике.

Второй случай, с запросом на подтверждение, опять же, неудобен обычным отправителям, которым приходится фактически отправлять вам два письма — "информационное" и "утвердительное". К тому же слабым местом подобного метода является допущение, что спамер ни в коем случае не будет подтверждать намерение попасть к вам в ящик, а также то, что обратный адрес спамерского письма всегда фиктивен. Оба утверждения, как показывает практика, весьма неоднозначны. Обратный адрес может быть не выдуманным, а случайно или специально совпасть с адресом существующего человека. Тогда он, скорее всего, ради любопытства ответит на пришедшее непонятно откуда письмо-подверждение — и тем самым письмо спамера будет доставлено до адресата, а сам он, за своё любопытство, может даже попасть в чей-нибудь "чёрный список", сам того не подозревая. Вероятность такого невольного ответа довольно велика: если пользователь, чей адрес подставлен вместо обратного, активно пользуется почтой, он может просто автоматически подтвердить доставку, не разбираясь, что это за письмо. Если же пользователь неопытен, то он просто нажмёт "ответить", ради любопытства... Опять же, далеко не все почтовые сервера корректно рапортуют о недоставленной почте. Корректно - в смысле, что исходное письмо прилагается в виде вложения, а текст отчёта содержит только техническую информацию о нём. Бывает, что сервер просто отсылает письмо назад в неизменном виде - а это значит, что если это было письмо-запрос на подтверждение, то программа-фильтр вполне может принять его именно за корректное подтверждение доставки. Наконец, если игра будет стоит свеч, то вполне может появится программе массовой рассылки, которая будет отправлять подобные подтверждения, — и метод "свой-чужой" потеряет свои плюсы.

Практически всё множество существующих на данный момент антиспамерских фильтров базируются на этих двух перечисленных принципах. Отличаются же они, как правило, "мощностью" спамерской базы, а также регулярностью и степенью её обновления.

Как правило, антиспамерские фильтры выполняются либо как службы-демоны (daemon), работающие на почтовом сервере, либо же как служебные программы, "висящие" где-нибудь в памяти компьютера, и, естественно, забирающие на себя определённую часть его ресурсов. Если спамерская база подобных фильтров пополняется через интернет, то эта программа будет расходовать также определённую часть сетевого трафика.

Ещё одним существенным недостатком многих антиспамерских фильтров является их ориентация "на запад". Наш же, "отечественный" спам проходит подобные "заграждения" довольно легко. Спамеры ведь тоже не стоят на месте: они так же пользуются всеми подобными фильтрами, тестируя свою рассылку, чтобы максимально эффективно обмануть все заграждения. И, надо сказать, что возможностей для этого у русского спамера заметно больше, чем у иностранца. Ведь кроме упомянутой "каровы" можно написать "kopoвa", почти по-английски, заменив (в данном случае) большинство русских букв на аналогично выглядящие латинские. И такое слово с большой вероятностью пройдёт через любой фильтр...

В общем, битва назойливых спамеров и их адресатов продолжается...

The Bat! и антиспамерские фильтры

Описывать почтовую программу The Bat! я здесь не буду. Её врагов это ни в чём не убедит, а поклонники и так хорошо знают, что это за софт и как с ним работать.

Начиная с версии 1.63 этой программы (которая на момент написания этой статьи ещё не является официальной, а существует в виде beta 7), The Bat! предоставил пользователям возможность подключать и использовать антиспаммерские фильтры. Фильтр работает во время получения почты и оценивает каждое входящее письмо по шкале от 0 до 100. 0 означает, что письмо "хорошее", 100 — что это спам. Затем уже сам The Bat! может на основании этой оценки что-нибудь сделать с письмом — например, удалить спам или поместить его в специальную папку "макулатура".

(самые последние версии The Bat! всегда доступны на ftp-сервере разработчиков: ftp://ftp.ritlabs.com/pub/the_bat/beta

Главное достоинство этой технологии в том, что фильтр в контексте The Bat! уже не является самостоятельным сервисом, живущим где-нибудь в трее или в недрах компьютера, но представляет собой подключаемую библиотеку, которая загружается только при работе с почтой, а затем автоматически выгружается, не оставляя после себя занятых ресурсов или иных неприятностей. Опять же, поскольку письмо "доставляется" фильтру непосредственно средствами The Bat!, то возможна работа со всеми видами почтовых протоколов, поддерживаемых этой программой, вплоть до "локальной доставки", когда письмо доставляется из одного ящика в другой, расположенный на этом же компьютере, без задействования в этом процессе сетевого трафика.

Итак, антиспамерские фильтры The Bat! потенциально не нуждаются в том, чтобы быть постоянно запущенными как сервис, и даже не нуждаются в использовании сети.

Осталось только найти подходящий фильтр...

Статистическая фильтрация Байеса

Суть метода статистической фильтрации состоит в применении математической теоремы Байеса ко входящим письмам. Эта теорема позволяет вычислить вероятность успешного совершения некоторого события на основании статистики совершения этого события в прошлом. Применительно к фильтрации спама: если 9 из 10 писем, содержащих пресловутое слово "корова", являются спамом, и лишь одно — "хорошим" письмом, то теорема Байеса позволяет вычислить, с какой вероятностью следующее письмо, содержащее это слово, будет являться спамом.

Метод Байеса подразумевает использование статистической оценочной базы — двух наборов ("корпусов") писем, один из которых составлен из спама, а другой — из "хороших" писем. При создании этой базы подсчитывается количество вхождений каждого отдельного слова (токена) в каждом корпусе, и на основании этого для каждого токена вычисляется оценка, или "спамность".

"Спамность" измеряется по шкале 0..1. Значение "0" означает отсутствие спама, "1" — полную уверенность в том, что это спам. Нейтральное значение — 0,5 — выражает отсутствие какой-либо определённой оценки. Токены, чья "спамность" приближается к нейтральному значению, малоинтересны для оценки письма. Наоборот, те из них, чьи значения очень сильно отличаются от 0,5, являются яркими показателями письма.

Пусть письмо содержит n токенов с оценками S1...Sn.

Тогда общая оценка письма S может быть легко вычислена по следующей формуле:

a = S1*S2*...*Sn;

b = (1-S1)*(1-S2)*...*(1-Sn);

S =a/(a+b).

Полученная оценка и будет являться значением "спамности" для некоего письма на основании существующей статистической оценочной базы.

Пауль Грэхем и Гари Робинсон

Допустим, что в оценочной базе некий токен "корова" встретился в 200 письмах спама и 100 - не-спама, а токен "бык" - в 1 письме спама и 0 не-спама. Легко сказать, что "спамность" первого токена в 2 раза превышает его не-спамность (и составляет 2/3), но как быть во втором случае? Можно сказать, что "бык" означает абсолютную спамность, но ведь он же встретился лишь единожды! Может, он вообще случайно оказался в базе...

Существует, по крайней мере, два подхода к этой проблеме. Один из них выражен в статье Пауля Грэхема "План по спаму". Второй — в статье Гари Робинсона, аналогичного содержания. Согласно первому подходу, все токены, общая частота которых меньше определённой величины (пусть, для определённости, будет 5), просто игнорируются. Согласно второму, их спамность вычисляется по формуле, которая при нулевой частоте даёт нейтральный результат (0,5 или 0,4), а при увеличении частоты асимптотически приближается к реальной оценке.

Другая проблема касается токенов, впервые встретившихся в проверяемом письме и не существовавших до этого в базе. Подход Робинсона, как было только что упомянуто, легко справляется с этой проблемой. Пауль Грэхем же предлагает для таких токенов дать оценку 0,4, из соображения, что спамеры редко придумывают новые слова, и если где-то встретилось абсолютно новое слово, то пусть оно воспринимается с лёгким сдвигом в сторону не-спамности.

Эвристический интервал

Когда вы визуально оцениваете письмо, вам необязательно читать его целиком. Обычно вы догадываетесь о том, что это спам, по нескольким ключевым признакам, срабатывающим на уровне подсознания. Точно так же, для статистической фильтрации вовсе необязательно вычислять оценку письма по всем его токенам. Достаточно выбрать лишь некоторые из них, наиболее "интересные" с точки зрения оценок. Уровень "интересности" определяется тем, насколько оценка токена отличается от нейтральной.

Эвристическим параметром для статистической фильтрации писем будет количество токенов, по которым оценивается то или иное письмо. Пауль Грэхем предлагает в качестве такого параметра число 15.

Наличие эвристического параметра позволяет существенно улучшить эффективность оценки и практически довести эффективность фильтра до 99,7%

Трюки спамеров...

В последнее время спам тоже не стоит на месте. Появились новые технологии, позволяющие спамерам с лёгкостью обманывать многие автоматические фильтры. Например, писать текст, невидимый для пользователя, но, естественно, "видимый" фильтрам и убеждающий их в том, что, мол, всё здесь в порядке. В последнее время для спамеров стало очень популярным оформлять свою рекламу в виде сравнительно небольшой картинки - в формате gif или jpeg - и посылать её как вложение. Однако с таким трюком легко справляется фильтр, который распознаёт файл-картинку не просто как вложение, но именно как картинку, причём определённого размера. Иногда это работает, но на практике обычно фактическая фильтрация производится по другим признакам - незначительным деталям заголовков писем, известным только фильтру благодаря набранной статистике.

Другой, становящийся популярным вариант - отправка текстовых писем, в которых ключевые слова разрежены при помощи пробелов. Но и это не срабатывает: поскольку нормальные письма обычно не содержат отдельно стоящие буквы (не считая коротких предлогов и союзов), то уже после нескольких подобных спамерских проделок такие буквы начинают действовать на фильтр, как красная тряпка на быка...