Принципы и технические методы работы с незапрашиваемой корреспонденцией. Часть 2

Часть 2. Методы борьбы со спамом

Можно встретить разные описания (по сути классификации) средств борьбы со спамом. Поскольку программа это всегда «Алгоритм + Структура Данных», то и классификацию программ правильно основывать на видах используемых данных и используемых алгоритмах. Что мы и попытаемся проделать ниже.

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

Задача спам-фильтрации

Задача, которую решает детектор спама: разделить входящий поток сообщений на спам и нормальную почту, Spam и Ham в английском жаргоне.

Исходные данные

Данные, которые используются для анализа — это все признаки пришедшего письма. Их можно разделить на четыре пространства, вычисление решений в которых можно производить независимо:

• IP-адрес сервера отправителя
• оформление и стиль писем, заголовки, форматирование, характерные обороты
• статистика слов в письмах
• контрольные суммы («сигнатуры») текстов писем

Естественно, что пространство признаков по каждому набору данных ограничивают только «интересными» признаками.

Конкретный антиспамовый модуль может использовать все эти пространства признаков или только 1-2 из них. Недостатки и преимущества каждого из пространств признаков мы обсудим ниже. Пока же обратим внимание на необходимое присутствие еще двух составляющих «задачи машинного обучения», классическим примером каковой является детектор спама, а именно: обучающей выборки и обратной связи.

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

Ошибки первого и второго рода

Чтобы любое машинное обучение работало, ему необходимо сообщать об ошибках. Ошибки бывают двух видов. Ошибка первого рода: пропуск спама, то есть пропуск спамового письма. Иными словами — недостаточная полнота метода. Ошибка второго рода — ложные срабатывания, когда не спам ошибочно относят к спаму. Иными словами — точность метода. Естественно, приоритет при настройке алгоритма отдается минимизации числа ложных срабатываний. Обычное требование для спам-детектора — уложиться в несколько промилле. Считается, что лучше дать пользователю прочитать несколько спамовых писем, чем скрыть от него настоящее письмо.

Интегральный показатель качества

Процент детектированного спама есть мера полноты, процент ложных срабатываний — мера неточности. Несложно предложить интегральную оценку качества, назовем ее качеством фильтрации. Очевидно, что при точности близкой к 100%, качество будет примерно равно полноте. Именно полноту фильтрации часто и называют, когда озвучивают те или иные цифры, подразумевая, что точность практически абсолютна. Надо при этом понимать, что острота восприятия ошибки второго рода зависит от характера поступающих в почтовый ящик писем и индивидуальных предпочтений пользователя: люди, обсуждающие в почте многомиллионные сделки, реагируют на ошибки второго рода гораздо более болезненно, чем сервис поддержки пользователей и, тем более, читатели рассылки анекдотов.

Ложные срабатывания. Разные подходы

Довольно большое значение имеет то, что происходит при ошибках второго рода — от этого зависит величина ущерба, наносимого этими ошибками, и, следовательно, требования к их количеству. Возможны следующие реакции фильтра на обнаруженный спам:
-1-письмо отвергается почтовым сервером; при этом, если оно на самом деле было «законным» письмом, отправитель получит сообщение об этом;
-2-письмо помещается в специальную папку; пользователь имеет шанс заглянуть в эту папку и увидеть там ошибочно отфильтрованное письмо;
-3-письмо «удаляется», как будто его и не было; никто ни о чем не знает.
Сценарий (3) — самый опасный; к счастью, администраторы почтовых серверов его почти никогда не используют. Однако из популярных текстов, о которых мы будем говорить ниже, зачастую создается впечатление, что используется именно он.
Сценарий (2) с одной стороны имеет тенденцию вырождаться в (3), если качество фильтра хорошее. С другой стороны, регулярный просмотр пользователем папки со спамом снижает пользу фильтрации, хотя это и делается существенно реже, поверхностным просмотром и т.д. В таком сценарии, однако, ущерб от ошибок второго рода минимален, а обратная связь максимальна.
Сценарий (1) — традиционный вариант для «классической» фильтрации по IP адресам. В отличие от (2), он не вырождается в (3), однако его, к сожалению, достаточно сложно реализовать на сервере, если в фильтре используется содержимое письма.

Промежуточная зона — «полуспам»

Очень важная, часто недопонимаемая проблема состоит в том, что спам и не-спам пересекаются в очень большой степени. Рассылки, от которых трудно отписаться, но на которые вы тем не менее (кажется?) подписывались. Подписки, возникающие при регистрации без вашего ведома. Многочисленные квитанции глупых антиспамерских и антивирусных программ. Автоответчики. Рассылки, совершаемые спамерами при помощи веб-форм из публичных, совершенно неспамерских веб-сервисов, тем не менее слабо защищенных от вторжения. Например, открытки или приглашения вступить в то или иное веб-сообщество — по тексту такого письма даже автор не может понять, спам это или нет. Вся такая корреспонденция может быть смело отнесена к «полуспаму».

Объем этой зоны очень и очень значительный.
Перед началом очередного этапа работ по антиспамовой фильтрации Яндекс провел исследование. Был проведен ручной анализ достаточно репрезентативной выборки из 5151 писем, пришедших на 300 адресов. Так вот, ситуации, когда проверяющий посторонний человек, используя для принятия решения все мощь своего естественного интеллекта, отнес письмо к такой «промежуточной зоне» составляли до 40 процентов! При этом формулировка правила для такого отнесения были достаточно осторожной.

… «Полуспамовое» письмо — это письмо от известного проверяющему реально работающего магазина или онлайн-сервиса, в котором пользователь скорее всего регистрировался. …

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

Второй вывод таков. Старайтесь не верить заявлениям создателям неперсонализированных антиспамовых продуктов, уверяющих что качество их фильтрации 95 или 98 процентов. В неперсонализированной антиспам-системе, которой известны предпочтения только усредненного пользователя, этот показатель, по-видимому, теоретически недостижим.

Обратная связь

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

Реализация обратной связи

В интерфейсе большинства современных публичных веб-почт (Hotmail, Yandex, Yahoo, Oddpost) есть специальная папка, служащая для накопления «полуспама» и не очень достоверно определяемого спама, а также кнопка для «реабилитации», сообщающая системе о ложном срабатывании.

В настольных почтовых клиентах, созданных в последнее время, тоже обязательно присутствует обратная связь как первого, так и второго рода. Обычно в виде кнопки «это спам» / «это не спам».

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

Технические приемы на уровне протокола

Особняком от методов, анализирующих только данные пришедшего письма, стоят некоторые довольны популярные в последнее время приемы, задающие особый способ взаимодействия почтовых программ.
1.Незнакомым отправителям посылается письмо типа «Извините, мы с Вами не переписывались, подтвердите пожалуйста что Вы не спамер». По приходу подтверждения программа добавляет адрес отправителя в список разрешенных. Есть и довольно известные реализации этой довольно старой идеи: TMDA и WinAntiSPAM.
2.Довольно свежая идея — graylisting («серые» списки). Суть ее состоит в том, что на некоторые письма сервер отвечает не «OK» или «rejected», как обычно, а «временная ошибка». Это само по себе работает (пока) очень хорошо, потому что «хорошие» почтовые сервера через некоторое время повторяют попытку доставить письмо (они обязаны это делать), а рассыльщики спама (пока) этого не делают. Причем можно надеяться, что если спамеры будут пытаться повторять попытки доставки, как нормальные сервера, то за это время они успеют попасть в списки запрещенных. Время повторного соединения обычно полчаса, и это, в общем, некритично, тем более что оно относится только к первой корреспонденции между двумя незнакомыми сторонами, так как ранее проверенные адреса не проверяются, а запросы на проверку кэшируются и вновь не посылаются.
3.Проверка корректности адреса отправителя (envelope-from). Проверку существования домена в большинство серверов вставили очень давно, однако до сих пор она иногда срабатывает. Сейчас многие стали вставлять проверку адреса целиком. Хотя это довольно дорого — для этого надо связываться с сервером, на котором расположен адрес, и осмысленный ответ при этом не гарантирован, однако, по крайней мере пока, это тоже неплохо работает.

Алгоритмы

Как видно из приведенной таблицы, потоки данных сильно отличаются для разных типа признаков. Рассмотрим их по отдельности

Проверка IP. DNS-зона. Имя списка запрещенных как интегральный признак

Простейшая в реализации, и безусловно именно поэтому самая популярная — фильтрация по пространству IP адресов. Для каждого письма проверить надо 1 (редко больше) IP адрес, делается это сейчас при помощи специальной DNS-зоны для каждого из списков запрещенных. Поиск в DNS, в сущности — простая хеш-функция. Часть из списков разрешено скачивать и для эффективности такие зоны легко создать на локальном DNS-сервере. Что еще характерно для данного пространства признаков?
Во-первых, отлично отработанная обратная связь.
Во-вторых, это самое нестабильное и текучее пространство признаков, для которого характерно постоянное исчезновение и добавление адресов. Следовательно, считать индивидуальный весовой коэффициент для каждого IP довольно дорого и не очень эффективно: данных слишком мало, а адреса все время меняются.

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

Байесовская фильтрация по словам

Очень простым, интуитивно понятным методом «машинного обучения с учителем» (то есть при наличии Spam&Ham выборки) является наивная байесовская классификация. «Наивной» она называется потому что исходит из предположения о взаимной независимости признаков, и, как ни странно, этого часто оказывается вполне достаточно. Использование формулы Байеса для фильтрации спама предложено совсем недавно, примерно год назад (http://www.paulgraham.com/spam.html).

Автор, Paul Graham, предназначал его для персональной фильтрации. Для работы требуется, чтобы у классифицируемого объекта было достаточно признаков. Этому требованию идеально удовлетворяют все слова (или токены) писем данного пользователя, исключая разве что очень редко встречающихся и совсем короткие. Вторым требованием является постоянное переобучение и пополнение коллекции Spam+Ham. Все такие условия идеально работают в локальных почтовых клиентах, поддерживающих этот алгоритм.

К сожалению, использовать метод Байеса напрямую в условиях массовой почтовой службы затруднительно, в основном по причине большого разнообразия словарного состава клиентских ящиков. Так, из-за того, что в обучающей выборке наверняка будет очень много порно-спама, все письма, например, врача-гинеколога могут быть отнесены к спаму. Не смогут здесь помочь и другие методы классификации текстов по словам, более традиционные для науки информационного поиска (например метод Роккио или метод опорных векторов). Однако как-то использовать вероятность отнесения письма к среднестатистическому спаму (или иную меру текстуальной схожести), полученную анализом словарного состава, по-видимому, можно и в массовых сервисах.

Генетические алгоритмы и ручное выставление весов

В результате больших усилий многих людей было выявлено огромное количество различных эвристик, связанных с особенностями заголовков спамерских писем, их оформления, характерных стилистических оборотов, типичных фраз. Суммарное количество подобных признаков у известного фильтра SpamAssassin, например, приближается к тысяче. К сожалению, несмотря на то, что практически каждое спамовое письмо содержит хотя бы несколько таких признаков, над пространством таких признаков невозможно построить устойчивый Байесовский автомат. Причин здесь две: слишком мало число признаков, типично встретившихся в одном письме, и отсутствует балансировка, то есть нет достаточного количества надежных и многочисленных признаков не-спама.

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

Часто практикуется и ручное выставление весов для каждого признака, ведь количество их обозримо и опытные администраторы в состоянии контролировать и постоянно корректировать спам-фильтрацию для почты своей компании.

Детектирование повторов и признак массовости

Если антиспамовая система имеет дело с большим потоком писем, она может и должна пытаться детектировать повторы писем. Во-первых так можно вылавливать письма, уже известные (помеченные ранее) как спам. Во-вторых, массовость письма сама по себе является неотъемлемым признаком спама. Из утверждения что письмо есть спам, неизбежно следует, что оно массовое. Таким образом, признак массовости есть необходимое, хотя и не достаточное условие спама.

Строго говоря, одиночные нежелательные письма тоже можно считать спамом, но бороться с ними имеет смысл одиночными же методами, поэтому для данной статьи можно смело принять такое допущение.

Интересной темой является практическая реализация выявления массовой корреспонденции. Попытки наладить распределенные системы обмена контрольными суммами писем, предпринимаемые в рамках таких проектов, как DCC (несколько контрольных сумм по тексту и заголовкам письма) или Бритва Вайпула (одна «нечеткая» контрольная сумма) в настоящий момент упираются в общие ограничения P2P-технологий по производительности. Дело в том, что для того, чтобы обеспечить статистику повторов в реальном времени, участники системы вынуждены поддерживать режим постоянного обмена этой информацией. В момент спамовой атаки скорость реакции таких систем становится неприемлемо низкой. Видимо, об эффективном применении детектирования повторов можно пока говорить только в системах с очень большим потоком писем, у крупных провайдеров или на публичных почтовых серверах, например веб-почты.

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

Интегрирующие системы

Ни один отдельно взятый набор признаков не в состоянии обеспечить максимальное качество фильтрации. Очевидно, преимущество здесь окажется у систем, интегрирующих решения по всем пространствам признаков. Пионером здесь является СпамАссасин, который позволяет применить как генетический алгоритм, так и ручное взвешивание поверх не только собственного или «настроенного» набора флагов, но и с учетом байесовского текстового подобия, и с учетом взаимодействия с DCC-модулем детектирования рассылок.
Отдельным вопросом является то, какой алгоритм должен работать в точке окончательного принятия решения.

Точки применения фильтра

Кроме различия в исходных данных, алгоритмах и видах обратной связи, антиспамовые средства надо различать по месту их применения. Таких мест можно выделить два: почтовый сервер и клиентский компьютер.

Фильтрация на сервере: царство IP-метода

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

Фильтрация на клиенте: царство Байеса

У клиента совершенно другая картина. Здесь малый поток данных, неизвестная производительность компьютера, отсутствие постоянной связи с Интернетом — то есть невозможно или слишком дорого постоянно «закачивать» массивы контрольных суммы писем или IP черных дыр. Зато очень точно можно отличить чужие письма, они всегда не похожи на ваши просто по тексту; «вкусы» одного пользователя выяснить легко. По всем этим причинам клиентские антиспамовые программы представляют из себя царство Байеса.

Принципы и технические методы работы с незапрашиваемой корреспонденцией. Часть 3