Методы борьбы с почтовым спамом

Размещено на http://www.allbest.ru/

Методы борьбы с почтовым спамом

Рожков Г.Г.

ANNOTATION

The article is devoted to the questions of effective struggle against a post spam. The review of the most popular and demanded mathematical algorithm of spam detection is described. Results of the analysis and testing of the software constructed on the basis of considered algorithms are resulted.

Рожков Геннадий Геннадьевич

Студент факультета электроники и приборостроения

Орловский государственный технический университет, г. Орел

ВВЕДЕНИЕ

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

Так что же подпадает под определение «спам»? На сегодняшний день в РФ определения, данного в рамках федеральных закона или подзаконного акта, нет. Есть лишь техническое (обиходное) определение данного понятия. По мнению Евгения Альтовского - координатора рабочей группы Проекта «АнтиСпам» Российского комитета Программы ЮНЕСКО «Информация для всех» - спамом следует объявить сообщения, которые обладают четырьмя признаками:

1. рассылаются массово;

2. являются незапрошенными, то есть рассылаются по каналам e-mail, ICQ, IRC и другим подобным, где пользователь не может исключить получение сообщений, не ограничивая себя существенно, при этом рассылаются без явного или неявного согласия получателя либо после явного выражения им несогласия;

3. содержат рекламу (в том смысле, как она определена в законе «О рекламе», то есть, в широком смысле);

4. являются анонимными, то есть не содержат идентификации рекламораспространителя либо содержат неверные данные о рекламораспространителе.

1.АЛГОРИТМЫ БОРЬБЫ СО СПАМОМ

Алгоритм Teiresias

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

Задан массив строк в алфавите A. Будем считать шаблоном (в терминах алгоритма Teiresias) последовательность следующего вида: A(A|.)*A. То есть шаблоном является строка, начинающаяся и кончающаяся символами из алфавита A, между которыми находится любая комбинация символов алфавита A и специального символа «.» (точка). Шаблон является регулярным выражением, в котором специальный символ «.» соответствует любому символу алфавита A. Тем самым шаблон P определяет язык G(P). К примеру, если задан шаблон BC.D.E, то его язык будет содержать, в частности, следующие строки: BCCDCE, BCEDCE, BCBDBEБ и т.п.

Для шаблона P каждая его подстрока, также являющаяся шаблоном, называется внутренним шаблоном шаблона P. Шаблон P называется (L,W)-шаблоном, если каждый его внутренний шаблон длины W или более содержит как минимум L символов алфавита A. Понятно, что если шаблон P является (L,W)-шаблоном, то он также является и (L,W+1)-шаблоном.

Строка символов алфавита A называется подпадающей под шаблон P, если содержит в себе подстроку из языка G(P). Если задан набор строк S={s₁,s₂,...,s_n}, то для шаблона P можно определить следующее множество смещений:

L_S(P)={(i,j)| строка s_i содержит в себе строку языка G(P), начиная со смещения j}.

Шаблон Pґ называется более характерным, чем P, если он может быть получен из P путем замещения одного или более специальных символов «.» на символы алфавита A или через дописывания справа или/и слева строк, состоящих из специальных символов и символов алфавита A. Очевидно, что |L_S(Pґ)| ? |L_S(P)|. Шаблон P называется максимальным для множества S, если не существует более характерного шаблона Pґ, такого что |L_S(Pґ)| = |L_S(P)|.

Алгоритм Teiresias позволяет по множеству строк S={s₁,s₂,...,s_n} в алфавите A и параметрам L, W, K найти все максимальные (L,W)-шаблоны, под которые подпадают как минимум в K различных строк множества S. [1, 2]

Алгоритм Chung-Kwei

Алгоритм Chung-Kwei основан на применении алгоритма Teiresias для поиска шаблонов в электронных сообщениях и разработан для спам-фильтра компании IBM SpamGuru. Алгоритм является целиком эвристическим, то есть не имеющим под собой точного обоснования.

Письма представляются в виде строк в алфавите ASCII. Авторы предполагают разделение писем на две части: техническая информация (заголовки) и тело письма, после чего предлагается использовать алгоритм раздельно для обеих частей. Тем не менее в его описании [3] авторы используют только тело письма без технической информации.

Алгоритм выполняется в два этапа - построение базы шаблонов (обучение) и применение шаблонов для классификации письма.

Для построения базы шаблонов (словаря спама) используется исходный набор спама, для которого применяется алгоритм Teiresias с некоторыми заданными (L,W) и K=2. Понятно, что полученные шаблоны являются характеристиками документов и могут лежать в основе любого иного метода автоматической классификации, например, Байесовского классификатора.

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

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

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

Каждое вхождение шаблона в письмо также соответствует вхождениям этого же шаблона в некоторые письма исходного набора. Для каждого такого вхождения по таблице соответствий символов начисляются очки в счетчики. Например, обрабатываемое письмо содержит подстроку ABCD, соответствующую найденному шаблону, и вхождение в базу содержит подстроку AbCD. Тогда каждому из четырех счетчиков, соответствующих символам этой строки в обрабатываемом письме, добавятся очки для пар символов (A,A), (B,b), (C,C) и (D,D) соответственно. Таблица соответствий символов заполняется изначально, исходя из прагматических соображений о степени «похожести» символов.

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

Найденные спамерские письма могут автоматически добавляться в базу и использоваться для обучения алгоритма на лету.

Результаты классификации спама, указанные авторами в [3], есть 96% распознавания спама и 0,06% ложных срабатываний.

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

Таким образом, использование непосредственно описанного выше алгоритма Chung-Kwei на почтовых клиентах сильно затруднено.

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

2.Формальное определение Байесовского классификатора

Постановка задачи классификации документов.

Задача классификации документов состоит в том, чтобы найти приближенное отображение Kґ=DxC>{T,F} отображения K, такого, что K(d, c)=T тогда и только тогда, когда документ d соответствует категории c и K(d,c)=F в обратном случае.

Полученная аппроксимация K' называется классификатором. В случае если категории статистически независимы друг от друга (то есть Kґ(d_j,cґ) не зависит от Kґ(d_j,cґґ) для любых cґcґґ), то можно без потери общности предположить, что множество категорий состоит только из двух непересекающихся категорий, к одной из которых обязательно принадлежит каждый из документов: . Это связано с тем, что случай с большим количеством категорий {c₁,...c_n} можно представить как n задач вида:

.

Таким образом, задача классификации приводится к виду поиска приближенного отображения Kґ=DxC>{T,F}.

Кроме того, вводится множество характеристик T, которые могут быть сопоставлены с документами. Тогда документ d представляется вектором коэффициентов (w₁,...,w_|T|), 0 ? w_i ? 1. Коэффициенты w_i, грубо говоря, определяют «вклад» характеристики t_i в семантику документа d.

В любом методе автоматической классификации сначала определяются характеристики документов и способ вычисления весов.

3.Наивный Байесовский классификатор

Байесовский классификатор основан на использовании знаменитой теоремы Байеса, и первые упоминания о нем можно встретить еще в 1960-м году [6]. За уже более чем 40-летнюю историю НБК использовался для решения самых разнообразных задач: от классификации текстов в новостных агентствах до первичной диагностики заболеваний в медицинских учреждениях.

При постановке задачи для НБК в качестве характеристик обычно выбирается наличие или отсутствие каких либо слов в документе, то есть за множество характеристик T принимается множество всех слов в обрабатываемых документах. Таким образом, вес характеристики w_i=1 в том случае, если слово t_i было найдено, и w_i=0 в обратном случае. В случае с фильтрами, которые используются для классификации спама [8], учитывается еще и область, в которой встретилось слово: заголовки, тема письма (subject), тело письма. То есть слово спам, встретившееся в теме письма, есть иной термин, чем слово спам в теле письма.

Кроме того, делается очень важное допущение: предполагается, что все характеристики документов, полученные таким образом (слова), статистически независимы; именно из-за этого допущения в названии классификатора присутствует слово «наивный». Это сильно упрощает применение теоремы Байеса для построения классификатора.

НБК, обычно используемый в спам-фильтрах (предложенный Полом Грэмом [6, 7]) имеет вид:

p₁·p₂ ... p_|d|/(p₁·p₂ ... p_|d|+(1-p₁)·(1-p₂ ... (1-p_|d|))>W,

где p_i=P(w_i=1|c), W - заданный пользователем порог. При этом используются вероятности только тех характеристик, которые встретились в документе. Такой НБК отличается от классической формулы [4, 5] тем, что в нем не используются вероятности самих категорий (или, точнее, эти категории приняты за равновероятные). Такое решение обосновывается авторами [10] тем, что принятие решения о конкретном письме не должно быть связано с количеством спама в почтовом ящике, а должно вычисляться исключительно по содержимому самого письма.

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

p_i=b_i/(g_i+b_j) ,

где b_i - количество «плохих» документов, содержащих характеристику t_i; g_i - количество «хороших» документов, содержащих характеристику t_i.

В реальных фильтрах, основанных на НБК, могут использоваться иные способы вычисления оценок вероятностей, учитывающие специальные случаи редких характеристик (встречающихся в малом количестве документов). К примеру, Гари Робинсон рекомендует заменить оценку p_i на f_i [10]:

f_i=(s·x+n_i·p_i)/(s+n_i),

где s и x - экспериментально подобранные параметры (рекомендуется 1 и 0.5), а n - количество документов с характеристикой t_i.

Метод Фишера

Начиная с публикации статьи Гари Робинсона [10], в некоторых фильтрах (например, SpamAssassin) вместо НБК стал использоваться метод совмещения вероятностей, предложенный Р. Фишером в 1950 году.

Применительно к классификации документов Робинсон сформулировал этот метод следующим образом: допустим, что документ имеет n характеристик, для каждой из которых уже рассчитана вероятность p_i. Тогда, согласно Фишеру, если эти вероятности не распределены равномерно, то значение будет подчиняться закону распределения ч²(2n).

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

Для определения спама Робинсон предложил рассчитать подобным образом не только вероятность спамности документа (H), но и вероятность того, что письмо не является спамом (S), и использовать показатель I, рассчитываемый по формуле: I=(1+H-S)/2.

Если показатель I достаточно близок к 0, то письмо считается не спамом; если I достаточно близок к 1, письмо считается спамом. В противном случае письмо считается спорным. Таким образом, в работе [10] вводится классификация не по двум категориям, а по трем.

4.ПРОГРАММНЫЕ РЕШЕНИЯ

Trend Micro Spam Prevention Solution

Компания Trend Micro была основана в 1988 году в Калифорнии Стивом Ченгом. С самого начала деятельности основным фокусом компании стала антивирусная безопасность. Компания заслужила высокую репутацию как производитель современного антивирусного программного обеспечения, а также средств фильтрации информационного наполнения и соответствующих сервисов. Инновации компании, как правило, опережают свое время и задают новые направления в защите информации.

Решение компании Trend Micro для защиты от спама - Trend Micro Spam Prevention Solution (SPS) [11] - появилось на рынке в марте 2003 года и основано на лицензированном ядре компании Postini. Данное решение представляет собой защиту от вредоносной почты на уровне интернет-шлюза. SPS работает в тесном взаимодействии с решениями компании для защиты от вирусов и фильтрации контента, что позволяет создать единую структуру защиты электронной почты для организации любого масштаба.

Spam Prevention Solution использует ряд методов для проверки почты и позволяет рассчитать вероятность того, что конкретное сообщение является спамом, исходя из совокупности целого ряда его характеристик. Trend Micro Spam Prevention Solution рассчитан на обработку и анализ 40-90 и более сообщений в секунду, что позволяет удовлетворить потребности организаций с большим трафиком при минимальных необходимых инвестициях в оборудование. Функции переключения при сбоях и блокировании машин-ретрансляторов помогают обеспечить надежность и доступность продукта. SPS функционирует в режиме «прозрачного» прокси-сервера, обрабатывая сообщения во внутренней памяти для обеспечения производительности и масштабируемости, необходимых в сетях больших предприятий. Многоплатформенная поддержка, включающая Windows, Linux и Solaris, позволяет легко встроить продукт в существующую корпоративную инфраструктуру, не требуя дополнительных инвестиций.

BayesIt! 0.6.0

Данный фильтр является плагином к известному почтовому клиенту The Bat! и с третьей версии включен в стандартную поставку. Судя по описанию и генерируемым отчетам, он целиком основан на работах Пола Грэма [7 ,8], то есть учитывает расположение слов (тело письма или заголовок) и техническую информацию; имеет ограничение на количество слов, выбираемых из документа для анализа. Результаты тестирования данного фильтра приведены в Таблице 1.

Таблица 1 - Результаты тестирования фильтра BayesIt! 0.6.0

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

- количество ложных срабатываний;

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

В почтовом ящике info количество спамерских писем было уменьшено до 800, чтобы его удалось обработать. После обучения фильтр допустил 10% ложных срабатываний и распознал 51% спама.

PopFile 0.21.2

Фильтр спама, работающий как pop3-прокси между любым почтовым клиентом и провайдером (в качестве почтового клиента был выбран MS Outlook Express), в отличие от остальных фильтров, поддерживает классификацию более чем по одной категории (спам или не спам), основываясь на использовании нескольких двоичных классификаторов для каждой из категорий. Дает возможность пользователю заводить свои собственные категории. Тем не менее, во время тестирования использовался только как бинарный классификатор.

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

Даже при двух категориях (спам и не спам) PopFile имеет третью - Unclassified. При вычислениях считалось, что все содержимое этой категории было отнесено к нормальной почте. Результаты тестирования фильтра приведены в Таблице 2.

Таблица 2 - Результаты тестирования фильтра PopFile 0.21.2

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

Почтовый ящик info не проверялся из-за неудобства пользовательского интерфейса.

ВЫВОДЫ

Рассмотренные в данной статье алгоритмы являются лишь малой частью во всем многообразии средств борьбы с нежелательной корреспонденцией. Следует отметить, что эффективного решения в области борьбы с почтовым спамом на сегодняшний день не существует: «война» спамеров и сил, им противодействующих, идет с переменным успехом - обе стороны постоянно варьируют методы и тактику ведения борьбы. Однако приведенные примеры программных реализаций алгоритмов Байеса и Chung-Kwei позволяют сделать краткосрочный прогноз развития в этом противостоянии. Если программное обеспечение основанное на положениях Байесовского метода, является нашей реальностью и на данный момент несмотря на постоянное усовершенствование не дает должных результатов из-за большого числа ложных срабатываний, которое не может составлять более 0.001 процента от общего количества почты, то средства анализа корреспонденции, основанные на алгоритме Chung-Kwei, с учетом возможной многоплатформенной поддержки могут стать серьезным прорывом в данной области.

ЛИТЕРАТУРА

алгоритм спам teiresias chung kwei

1. I. Rigoutsos, A. Floratos. Combinatorial pattern discovery in biological sequences: the TEIRESIAS algorithm. Bioinformatics, Vol .14, no. 1, 1998.

2. A. Floratos, I. Rigoutsos. Research report: On the time complexity of the TEIRESIAS algorithm. IBM Research division, RC21161(94582)21APR98, 1998.

3. I. Rigoutsos, T. Huynh. Chung-Kwei: a pattern-discovery-based system for the automatic identification of unsolicted e-mail messages (SPAM).

4. David D. Lewis. Naive (Bayes) at forty: the independence assumption in information retrieval, 2000.

5. Fabrizio Sebastiani. Machine learning in automated text categorization, ACM Computing Surveys, Vol. 34, No. 1, 2002.

6. M.E. Maron, J.L. Kuhns. On relevance, probabilistic indexing and information retrieval. Journal of the ACM, July 1960.

7. Paul Graham, A plan for spam, http://paulgraham.com/spam.html.

8. Paul Graham, Better Bayesian filtering, http://paulgraham.com/better.html.

9. В. С. Пугачев. Теория вероятностей и математическая статистика. М.: Физматлит, 2002.

10. Gary Robinson, A statistical approach to the spam problem, 2003, http://www.linuxjournal.com/article.php?sid=6467.

11. http://www.spamtest.ru/document.html?context=15932&pubid=19208

Размещено на Allbest.ru