Детектирование массовых рассылок на Яндекс.Почте

Подробно о методах фильтрации мы рассказали в статье «Принципы и технические методы работы с незапрашиваемой корреспонденцией». Ниже мы расскажем о применении методов фильтрации в повседневной борьбе со спамов на Почте Яндекса.

О почтовой службе Яндекс.Почта

На Почте Яндекса письма проходят три уровня фильтрации.

На первом этапе отбрасывается явный спам — сообщения, приходящие от неадминистрируемых (взломанных, открытых) почтовых серверов, либо пойманные в спамовые ловушки.

Затем каждое письмо проверяется антивирусной программой DrWeb. При этом зараженные письма, не содержащие ничего, кроме самого вируса, отбрасываются, а зараженные письма с текстом помечаются «осторожно, вирус».

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

На странице mail.yandex.ru/monitoring/ публикуются ежедневные данные, по которым можно следить за ходом борьбы со спамом на Яндекс.Почте.

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

На Яндекс.Почте реализован (благодаря наличию специальной папки «Рассылки») оба вида обратной связи, как по ошибкам первого рода (Кнопка «ФУ! ЭТО СПАМ»), так и по ошибками второго рода: ссылка «Это не рассылка» в папке Рассылки.

Зачем детектировать повторы?

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

Что такое контрольная сумма? fnv, md5, crc

Контрольная сумма (или «сигнатура») — это уникальное число, поставленное в соответствие некоторому тексту и/или функция его вычисления. Функция вычисления контрольных сумм может преследовать несколько целей: например «невзламываемость» (минимизируется вероятность того, что по значению контрольной суммы можно подобрать исходный текст) или «неповторяемость» (минимизируется вероятность того, что два разных текста могут иметь одну контрольную сумму). Существует обширная литература по алгоритмам вычисления контрольных сумм, я упомяну здесь самые известные: fnv, md5, crc. Обычно более-менее все равно, какой из них выбрать, но в любом случае при выборе алгоритма его положительной стороной можно считать хорошее быстродействие.

Нечеткие дубликаты. Постановка задачи

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

Опыт современных поисковых систем

Задача, схожая с этой, но на гораздо больших масштабах данных, уже встречалась в нашей компании, когда нам приходилось решать проблему «почти дубликатов» в веб-поиске [Ilyinsky2002]. И хотя тот алгоритм (представленный на всемирной конференции по интернет-вычислениям WWW2002 на Гавайях) не годился в использовании напрямую, однако общий круг идей и методов нам был хорошо знаком.

Шинглы

Наиболее известным способом обработки почти-дубликатов в веб-поиске, изящно представленным Андреем Бродером в 1997 году, является метод «шинглов». Очевидно, чтобы повысить вероятность того , чтобы в результате небольших изменения текста контрольная сумма не изменилась, можно попытаться выбрать из текста несколько подстрок. Шингл (от английского shingle — чешуйка, черепичка) это и есть подстрока текста, по которой происходит вычислений контрольной суммы.

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

Встык

Если запоминать контрольные суммы для строчек фиксированной длины, идущих встык, то вставка и удаление одного символа (особенно в начале текста) разрушит их все, как их ни выбирай. Это — безусловно, самый неудачный вариант.

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

Когда заведомо известно, что документ изменяется, пусть и сильно, но в малом количестве мест, этот тип сигнатур успешно применяют. Например: передача HTML-файлов или синхронизация репозитория исходных текстов программ и т.п.

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

Внахлест

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

Выборка. Какие шинглы запоминать?

Классический алгоритм Бродера предлагает отбирать либо фиксированное количество минимальных по значению шинглов, либо все шинглы, значение которых делятся на какое-нибудь небольшое число (10-30). В первом случае мы получаем фиксированную по размеру выборку (что иногда удобно) и приличный по размеру набор шинглов даже для относительно коротких документов, но нельзя будет судить о вложенности документов. Во втором случае число шинглов пропорционально размеру документа, то есть оно переменное, зато можно по набору шинглов оценивать такие интересные вещи, как вложение документов друг в друга или процент их пересечения. Наконец, последний самый «модный» алгоритм формирует фиксированную выборку, размер которой определяется заданным числом (например, 85 для веб-документов) разных независимых случайных функций, для каждой из которых запоминается ровно один шингл, минимальный по значению контрольной суммы. Этот подход комбинирует преимущества двух предыдущих.

Короткие документы. Что можно сделать?

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

Супершингл

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

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

Замена супершингла: лексические сигнатуры

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

Если локальные сигнатуры рассматривают документ изолированно от коллекции и пытаются извлечь несколько характерных слов, основываясь только на их статистике в самом документе — TF (характерный пример: взять 5 самых частотных слов в документе длиннее пяти букв и упорядочить их по убыванию частоты), то глобальные либо пытаются при анализе документа учитывать информацию о глобальной статистике слова — IDF, либо, вообще выбирают опорные слова, опираясь исключительно на уже существующий инвертированный индекс (см. метод Яндекса). Для работы глобальных методов необходимо как-то считать глобальную статистику слов, что в интенсивной антиспамовой системе вполне возможно, например в рамках байесовского подхода.

Антидетекторы. Борьба борьбы с борьбой

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

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

1. Генерация невидимого (или очень слабо видимого) текста средствами HTML-форматирования.

   В этом случае, детектирование рассылок по контрольным суммам может быть полностью разрушено. Однако, чтобы добиться такого эффекта, спам-системам придется интенсивно пользоваться разными приемами HTML. Существует целый букет эвристик, связанных с оформлением письма, надежно детектирующий эту технику. Это и отсутствие plain-text части и масса специфичных тегов HTML или нестандартные стилей CSS (например visibility: hidden). В любом случае здесь речь идет не столько о расчете сигнатуры, сколько о хорошем детекторе особенностей html-формата.

2. Генерация видимого «мусора», то есть случайных буквенных цепочек, добавляемых в заголовки и текст письма.

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

3. Вставка пробелов в текст в случайных местах внутри слов и удаление их между словами. Против такого приема может помочь подсчет шинглов с гранулярностью в один символ с предварительно удаленными пробелами (все слова текста склеить в одну цепочку из букв, фиксированным окошком вычислить шинглы). Кроме того, доля «несловарных» слов с таким антидетектором тоже будет аномально высока.

4. Вставка значащих слов в текст в случайных позициях. Этот вид антидетектора редок, так как затрудняет понимание текста письма. Генерировать же бесконечное количество синтаксически связанных перефразирований спамеры еще не научились. В любом случае с таким антидетектором остается надеяться на снижение эффективности спама и соответственно существенное повышение цены вхождения в этот рынок.

Низкий порог срабатывания

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

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

Заключение

Детектор массовых рассылок внедрен в Яндексе в ноябре 2002 года. Мы продолжаем его совершенствовать и считаем, что это относительно простой в реализации, но эффективный механизм, предназначенный как для облегчения ежедневной работы пользователей с почтой, так и для использования его в составе более сложной антиспам-фильтрации.

Не существует рассылок, на которые нет жалоб пользователя. Не существует спама, который люди не просят реабилитировать. Границу часто провести невозможно. Следовательно, даже после открытия пользователю понятного интерфейса по обучению системы («ЭТО ПИСЬМО = СПАМ»,»ЭТО ПИСЬМО — НЕ СПАМ») и налаживанию сбора всей информации, следующим шагом должна быть максимальная индивидуализация антиспамовой системы.

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