Некоторые автоматические методы детектирования спама, доступные большим почтовым системам

Введение

В современных антиспамовых системах, установленных на крупных почтовых серверах и использующих широкий набор признаков спама и разнообразные техники по их выявлению [1, 2], центральным вопросом является вопрос создания автоматических механизмов фильтрации, способных работать с актуальным почтовым потоком.

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

Другой подход, подход постоянного ручного анализа и мониторинга всего почтового потока, в котором существуют «ночные лингвисты, которые вынуждены постоянно подстраиваться под спамеров» [3], а сигнатуры спама составляются вручную, представляется нам не менее дорогостоящим.

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

Данная работа в популярной форме описывает несколько таких механизмов, уже использующихся или проходящих тестирование в Яндексе (http://mail.yandex.ru, http://so.yandex.ru), дает представление о текущем состоянии алгоритмов в этой области, выводит некоторые аналитические оценки эффективности их применения. В конце работы приведен сравнительный анализ работы нескольких антиспамовых систем, в том числе систем Яндекса, в которых применяются описываемые в статье методы.

Устойчивые сигнатуры

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

Небольшими изменениями назовем такие изменения, которые не нарушают основного содержания письма.

Опишем вкратце несколько современных методов расчета таких сигнатур. Как отмечалось в [1], можно выделить ‘синтаксические’ (то есть оперирующие с цепочками слов) и ‘лексические’ (то есть оперирующие со словарем) методы расчета сигнатур.

Современные ‘синтаксические’ методы, основанные на шинглах [4, 5], используют идею вычисления контрольных сумм для всех подцепочек текста (‘шинглов’) и последующего построения случайной выборки из полученного набора.

Рисунок 1. «Шинглы» первых строк известного русского стихотворения

Нетрудно показать [5], что по шинглам можно с высокой вероятностью судить о сходстве текстов, их вложенности, плагиате и т.д. Однако для практических задач, в том числе для обнаружения массовых рассылок, требуется слишком большое количество шинглов, что предъявляет непреодолимо высокие требования к ресурсам для проведения процедуры кластеризации. Эти ограничения преодолеваются при помощи техники супершинглирования (DSC-SS), состоящей в расчете небольшого количества (1-6) контрольных сумм (‘супершинглов’) над подмножествами полного массива шинглов для данного текста. Так в работе [6] были предложены следующие параметры: 84 шингла, 6 супершинглов над 14 шинглами каждый; тексты считаются гипотетически совпавшими при совпадении хотя бы двух супершинглов из 6.

Класс методов, основанных на лексиконе, также развивался в последнее время. В частности, к методу опорных слов [7] (Ильинский, 2002) и его аналогу, методу I-Match [8] (Chowhudri, 2002), смысл которых состоит в тщательном выборе глобального лексикона (на основе статистики слов в коллекции) и в проецировании словаря текста на выбранный лексикон, добавились новые особенности. Во-первых, подвергаются ревизии процедуры выбора лексикона [10] (по некоторым причинам я не могу описать здесь алгоритм выбора лексикона в методе Ильинского), во-вторых, также как и в случае с супершинглированием, полная сигнатура заменяется небольшим количеством (до 10) сигнатур [9], построенных на случайных подмножествах исходного лексикона (т.н. метод Lexicon Randomization). Пример применения лексических сигнатур к задаче обнаружения спама приведен здесь [10].

И в синтаксических, и в лексических методах наблюдается тенденция, направленная на повышение полноты обнаружения слабоизмененных документов, на основе рандомизированных подмножеств из исходных ‘более полных’ сигнатур.

Оценка полноты детектирования по сигнатурам¹

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

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

Мы считаем письмо ‘детектированным’ (опознаем как ‘массовое’ или ‘спам’) если размер кластера, в который оно попало, больше или равно порога k. Оценим полноту (‘recall’) нашего метода, то есть долю ‘детектированных’ писем в рассылке:

 , где s — общее число ‘детектированных’ (‘спам’) писем

Примем вероятность ‘склеивания’ (попадания в один кластер) любых двух писем из рассылки равной p. Очевидно, соблюдается соотношение:

 , где в числителе число всех ‘склеенных’ пар, а в знаменателе число всех возможных пар писем из данной рассылки. Проведя элементарные преобразования выражения для p:

Отсюда:

Представим сумму квадратов размеров всех кластеров в виде сумм квадратов размеров ‘больших’ (больше или равно порога) и ‘маленьких’ кластеров:  и попытаемся оценить ее сверху.

Сумму квадратов размеров ‘больших’ кластеров заменим квадратом общего числа детектированных писем (квадратом суммы):

 (1)

Для ‘маленьких’ кластеров имеем . Суммируя по i, получаем:

  (2)

Отсюда:

Разделим на N², введем переменную для относительного порога  и перенесем влево неизвестные:

Пренебрегая , так как N>>1, получаем

  (3)

Упростим еще дальше. В ситуации большого потока писем, а также разумно выбранного (то есть малого) порогового размера кластера, N>>k, то есть можно считать c близким к нулю.

Таким образом, полнота детектирования рассылок для данного метода не меньше корня из вероятности ‘склеивания’ данным методом произвольной пары писем из одной рассылки:

  (4)

Это выражение служит формальным подтверждением вывода, сделанного в [1], о высокой эффективности сигнатурного метода на Яндекс.Почте в 2002-2003 гг.

Из формулы (4) следует, что даже при относительно невысокой вероятности склеивания, например, 0.1, в ‘большие’ кластеры попадает не меньше 33% писем массовой рассылки.

¹ Автор благодарит С. Ильинского за помощь в выводе формулы>>

Применение сигнатур

Если антиспамовая система в состоянии детектировать письмо как массовое, а кроме того, в состоянии опознать в нем конкретную рассылку, то информация про данную рассылку может накапливаться по всем письмам данной рассылки. Следовательно, у системы появляется возможность использовать детектор массовости в построении различных антиспамовых эвристик. Перечислим некоторые примеры таких эвристик:

1. Идентичные письма, посланные (с точностью до пересылок через trusted zone) с одного и того же (или малого количества) IP, содержащие при этом характерные признаки ‘честных’ почтовых рассылок (например, SPF запись, явно разрешающая отправку писем с конкретного адреса, специфические заголовки и др.), как правило, являются ‘честной’ почтовой рассылкой
2. И, наоборот, идентичные письма, приходящие со слишком большого количества адресов (с точностью до пересылок через trusted zone), особенно при условии дополнительных признаков (содержание письма, жалобы, ловушки, ‘плохой’ SPF), могут быть с высокой вероятностью отнесены к спаму.
3. IP-адреса, высокий процент трафика с которых (с точностью до пересылок через trusted zone) задействован в массовой рассылке, идентифицированной как спам (см. п.2), могут заноситься в специальную подозрительную зону. Письма из этой зоны могут трактоваться особо тщательным образом.

Списки разрешенных

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

1. Письма от типичных адресатов пользователя (при условии минимальной верификации корректности адреса отправителя: например, SPF или подсеть домена, указанного во from) могут трактоваться как НЕ-СПАМ. Сам список адресатов составляет основу автоматически построенного индивидуального списка разрешенных
2. В той же или меньшей степени это утверждение относится к адресатам адресатов
3. Домены (и их IP-адреса) в которые направляется большой поток исходящей корреспонденции крупной почтовой системы, при некоторых дополнительных условиях могут вноситься в ‘trusted zone’

Анализ эффективности

Принципы эксперимента

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

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

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

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

Описание эксперимента и участвующих систем

В течение двух месяцев, с 19 февраля по 16 апреля 2004 года, почтовый сервер владельца ящика принимал корреспонденцию на два адреса, существующие с 1997 и 2000-го года, соответственно. Он был настроен на пересылку входящей корреспонденции по 5-ти адресам: 4 адреса были размешены на публичных сервисах, доступных на тот момент в Рунете, и позволявших использование в качестве фильтра, 5 й адрес был контрольным адресом, на котором была отключена фильтрация.

• [M] antispamcompare@mail.ru — настройки: УДАЛЯТЬ СПАМ. ПЕРЕСЫЛАТЬ НА ‘контрольный ящик’
• [Y] antispamcmp@yandex.ru — настройки: УДАЛЯТЬ СПАМ. ПЕРЕСЫЛАТЬ НА ‘контрольный ящик’
• [T] antispamcompare@spamtest.ru — настройки: ПОМЕЧАТЬ В ЗАГОЛОВКЕ. ПЕРЕСЫЛАТЬ НА ‘контрольный ящик’
• [O] antispamcmp@so.yandex.ru — настройки: ПОМЕЧАТЬ В ЗАГОЛОВКЕ. ПЕРЕСЫЛАТЬ НА ‘контрольный ящик’
• ‘контрольный ящик’

При помощи модуля языка фильтрации SIEVE [11] письма, поступающие из названных пяти мест в ‘контрольный ящик’, раскладывались по пяти фолдерам². Заметим, что разница между настройками сервисов M,Y и T,O была вызвана тем, что первые два сервиса не позволяют одновременно и пропускать спам и помечать его в заголовках. Тем не менее, предполагая, что входной поток для всех сервисов одинаков, этим различием для наших целей можно пренебречь, ведь недостающие характеристики можно получить, используя данные других сервисов или ‘контрольного ящика’. Заметим, что один из входящих почтовых ящиков представляет собой популярное женское имя на популярном сервере, поэтому в числе писем, полученных на него, было некоторое количество ошибочно отправленных сообщений.

1. Всего за это время поступило 1222 письма.
2. Из них 17 персональных писем, предназначенных владельцу ящика. Все 17 были пропущены всеми 4-мя системами.
3. Еще 16 писем пришли от незнакомых владельцу ящика людей и не были предназначены владельцу ящика. 13 от некой Ирины из Санкт-Петербурга и 3 письма от некой Алии. Первый автор (Ирина) активно рассылал по большому количеству адресов (более 2-х десятков) различные бородатые истории, анекдоты и картинки. Владелец ящика идентифицировал все эти письма как нежелательные. Система T пропустила все 13 писем от Ирины, система M пропустила 12, O — 8 и Y — 5. Все 3 письма Алии, также безадресные и ‘бессмысленные’, были пропущены всеми системами.
   В нижеследующих таблицах и графиках все безадресные письма считаются спамом.
4. 9 писем представляли собой автоматически посланные сообщения: рассылки и уведомления. Мы могли бы выделить для таких сообщений отдельный класс, если бы все исследуемые системы одинаково их трактовали. К сожалению, это не так: в системах O и Y такие сообщения относятся к обобщенному классу Спам+Рассылки, в системе T эти сообщения получали признак FormalMessage. При этом она сама не афишировала данную возможность и не демонстрировала высокой точности в их детектировании. Только 7 из 9 сообщений данного класса носили признак FormalMessage, при этом к тому же классу были отнесены 6 явно безадресных, хотя и автоматических писем. В нижеследующих таблицах и графиках все такие письма считаются спамом.

Опишем чуть подробнее класс автоматических писем. Из 9 ‘автоматических’ писем 5 писем были отправлены от незнакомых владельцу сервисов и людей (2 — чьи-то попытки регистрации с неправильным обратным адресом, 2 открытки и 1 уведомление о посланной открытке), то есть, фактически, представляли собой автоматический или полуавтоматический способ знакомства. 4 ‘корректных’ ‘автоматических’ письма из 9 пришли от offline-сервисов (‘Росинтер Почетный Гость’ и ‘Citibank Alerting Service’), электронный адрес получателя был взят из рукописной анкеты и не был ими проверен; согласия получать рекламные электронные письма владелец ящика никогда не выражал. В соответствующих рукописных анкетах нет предупреждения о том, что заполнение поля e-mail автоматически означает получение рекламных писем от вышеназванных компаний.

² Автор статьи готов предоставить полученную коллекцию в размеченном виде>>

Результаты эксперимента

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

Очевидно, что относительно небольшая по объему ‘серая зона’, условия интерпретации которой подробно описаны выше, слабо влияет на данные показатели.

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

Рисунок 2. Абсолютное, осредненное по неделе, число спамовых писем, пропущенных системами в день

Несмотря на то, что абсолютное число пропусков спама сильнее зависит от интенсивности и характеристик потока, наблюдается достаточно устойчивая картина относительной эффективности систем.

Чтобы подчеркнуть стабильность работы разных алгоритмов, приведем график относительного пропуска спама, приняв объем пропусков наименее эффективной системы [M] за единицу.

Рисунок 3. Осредненное по неделе число спамовых писем, пропущенных системами в день, нормированное к системе [M]

Можно видеть, что эффективность систем [O] и [Y] в начале наблюдаемого периода была очень близка. Затем, к примерно 20-му дню эксперимента, эффективность [O] постепенно упала, а затем, буквально за 5 следующих дней, опять достигла уровня [Y]. Можно сделать вывод (подтверждаемый свидетельствами разработчиков), что системой [O] ‘плотно не занимались’, а примерно в 20-й день эксперимента, заимствовали техники и опыт из системы [Y], что привело к скачкообразному повышению эффективности.

Второе наблюдение состоит в том, что хотя системы [T] и [M] стартовали с одинаковой эффективностью, эффективность системы [T] последовательно нарастала и к концу периода приблизилась к эффективности системы [Y].

Заключение

В заключении хочется подчеркнуть следующее.

1. Полностью автоматические метрики в крупных антиспамовых системах не только имеют право на существование, но и достаточно эффективны, особенно в сочетаниях с другими факторами.
2. Антиспамовые системы демонстрируют относительно стабильную эффективность, однако требуют постоянного ‘ухода’ и присмотра
3. Существует возможность (хотя и не дешевая) достаточно точного внешнего мониторинга их эффективности, хорошо согласующегося с эффективностью реально использующихся в них алгоритмов и техник

Литература

1. Принципы и технические методы работы с незапрашиваемой корреспонденцией // И. Сегалович, Д. Тейблюм, А. Дилевский // Яндекс // http://company.yandex.ru/articles/spamooborona.html
2. Технология Спамтест. Описание технологии // Ашманов и Партнеры // http://www.spamtest.ru/products.html?chapter=9149
3. Яндекс: решение различных проблем безопасности // Дискуссия к статье // http://hostinfo.ru/htmltree/internet/vip/yandex/security
4. Finding similar files in a large file system // U. Manber // USENIX Conference 1994 // http://citeseer.ist.psu.edu/manber94finding.html
5. On the resemblance and containment of documents // A. Broder // digital Systems Research Center // http://ftp.digital.com/pub/Digital/SRC/publications/broder/positano-final-wpnums.pdf
6. A large-scale study of the evolution of web pages // D. Fetterly, M. Manasse, M. Najork, J. Wiener // WWW Conference 2003 // http://www2003.org/cdrom/papers/refereed/p097/P97%20sources/p97-fetterly.html
7. An efficient method to detect duplicates of Web documents with the use of inverted index // S. Ilyinsky, M. Kuzmin, A. Melkov, I. Segalovich // WWW Conference 2002 // http://www2002.org/CDROM/poster/187/
8. Collection statistics for fast duplicate document detection // A. Chowdhury, O. Frieder, D. Grossman, M. McCabe // ACM Transactions on Information Systems (TOIS), Vol. 20, Issue 2 (April 2002) // http://portal.acm.org/citation.cfm?id=506311
9. Improved Robustness of Signature-Based Near-Replica Detection via Lexicon Randomization // A. Kołcz, A. Chowdhury, J. Alspector // KDD 2004 // http://ir.iit.edu/~abdur/publications/470-kolcz.pdf
10. The Impact of Feature Selection on Signature-Driven Spam Detection // A. Kołcz, A. Chowdhury, J. Alspector // CEAS 2004, The First Conference on Email and Anti-Spam // http://www.ceas.cc/papers-2004/147.pdf
11. Sieve. A Mail Filtering Language // http://www.cyrusoft.com/sieve