Рожков Геннадий Геннадьевич
Студент факультета электроники и приборостроения
Орловский государственный технический университет, г. Орел
ВВЕДЕНИЕ
Спам, безусловно, проблема неоднозначная. Кто-то склонен ее вовсе не замечать, кто-то - преувеличивать до размеров вселенского зла. Одни собственноручно выискивают деловые письма среди зачастую более многочисленных нежелательных писем, другие пытаются выстроить вокруг своего почтового ящика непреодолимый барьер. Встречаются даже люди готовые отдать решение проблемы полностью на откуп провайдеру, даже не задумываясь, что это фактически означало бы введение цензуры (пусть и в рамках отдельно взятой подсети).
Так что же подпадает под определение «спам»? На сегодняшний день в РФ определения, данного в рамках федеральных закона или подзаконного акта, нет. Есть лишь техническое (обиходное) определение данного понятия. По мнению Евгения Альтовского - координатора рабочей группы Проекта «АнтиСпам» Российского комитета Программы ЮНЕСКО «Информация для всех» - спамом следует объявить сообщения, которые обладают четырьмя признаками:
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={s1,s2,...,sn}, то для шаблона P можно определить следующее множество смещений:
LS(P)={(i,j)| строка si содержит в себе строку языка G(P), начиная со смещения j}.
Шаблон Pґ называется более характерным, чем P, если он может быть получен из P путем замещения одного или более специальных символов «.» на символы алфавита A или через дописывания справа или/и слева строк, состоящих из специальных символов и символов алфавита A. Очевидно, что |LS(Pґ)| ? |LS(P)|. Шаблон P называется максимальным для множества S, если не существует более характерного шаблона Pґ, такого что |LS(Pґ)| = |LS(P)|.
Алгоритм Teiresias позволяет по множеству строк S={s1,s2,...,sn} в алфавите 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ґ(dj,cґ) не зависит от Kґ(dj,cґґ) для любых cґcґґ), то можно без потери общности предположить, что множество категорий состоит только из двух непересекающихся категорий, к одной из которых обязательно принадлежит каждый из документов: . Это связано с тем, что случай с большим количеством категорий {c1,...cn} можно представить как n задач вида:
.
Таким образом, задача классификации приводится к виду поиска приближенного отображения Kґ=DxC>{T,F}.
Кроме того, вводится множество характеристик T, которые могут быть сопоставлены с документами. Тогда документ d представляется вектором коэффициентов (w1,...,w|T|), 0 ? wi ? 1. Коэффициенты wi, грубо говоря, определяют «вклад» характеристики ti в семантику документа d.
В любом методе автоматической классификации сначала определяются характеристики документов и способ вычисления весов.
3.Наивный Байесовский классификатор
Байесовский классификатор основан на использовании знаменитой теоремы Байеса, и первые упоминания о нем можно встретить еще в 1960-м году [6]. За уже более чем 40-летнюю историю НБК использовался для решения самых разнообразных задач: от классификации текстов в новостных агентствах до первичной диагностики заболеваний в медицинских учреждениях.
При постановке задачи для НБК в качестве характеристик обычно выбирается наличие или отсутствие каких либо слов в документе, то есть за множество характеристик T принимается множество всех слов в обрабатываемых документах. Таким образом, вес характеристики wi=1 в том случае, если слово ti было найдено, и wi=0 в обратном случае. В случае с фильтрами, которые используются для классификации спама [8], учитывается еще и область, в которой встретилось слово: заголовки, тема письма (subject), тело письма. То есть слово спам, встретившееся в теме письма, есть иной термин, чем слово спам в теле письма.
Кроме того, делается очень важное допущение: предполагается, что все характеристики документов, полученные таким образом (слова), статистически независимы; именно из-за этого допущения в названии классификатора присутствует слово «наивный». Это сильно упрощает применение теоремы Байеса для построения классификатора.
НБК, обычно используемый в спам-фильтрах (предложенный Полом Грэмом [6, 7]) имеет вид:
p1·p2 ... p|d|/(p1·p2 ... p|d|+(1-p1)·(1-p2 ... (1-p|d|))>W,
где pi=P(wi=1|c), W - заданный пользователем порог. При этом используются вероятности только тех характеристик, которые встретились в документе. Такой НБК отличается от классической формулы [4, 5] тем, что в нем не используются вероятности самих категорий (или, точнее, эти категории приняты за равновероятные). Такое решение обосновывается авторами [10] тем, что принятие решения о конкретном письме не должно быть связано с количеством спама в почтовом ящике, а должно вычисляться исключительно по содержимому самого письма.
Для вычисления вероятностей pi используется так называемый процесс обучения, во время которого анализируются заранее классифицированные документы. Тогда вероятности можно рассчитать, к примеру, следующим образом:
pi=bi/(gi+bj) ,
где bi - количество «плохих» документов, содержащих характеристику ti; gi - количество «хороших» документов, содержащих характеристику ti.
В реальных фильтрах, основанных на НБК, могут использоваться иные способы вычисления оценок вероятностей, учитывающие специальные случаи редких характеристик (встречающихся в малом количестве документов). К примеру, Гари Робинсон рекомендует заменить оценку pi на fi [10]:
fi=(s·x+ni·pi)/(s+ni),
где s и x - экспериментально подобранные параметры (рекомендуется 1 и 0.5), а n - количество документов с характеристикой ti.
Метод Фишера
Начиная с публикации статьи Гари Робинсона [10], в некоторых фильтрах (например, SpamAssassin) вместо НБК стал использоваться метод совмещения вероятностей, предложенный Р. Фишером в 1950 году.
Применительно к классификации документов Робинсон сформулировал этот метод следующим образом: допустим, что документ имеет n характеристик, для каждой из которых уже рассчитана вероятность pi. Тогда, согласно Фишеру, если эти вероятности не распределены равномерно, то значение будет подчиняться закону распределения ч2(2n).
Таким образом, становится возможным найти вероятность того, что для некоторых иных значений pi соответствующее число будет больше, чем рассчитанное для данного документа. Если эта вероятность достаточно мала, то документ следует отнести к рассматриваемой категории.