автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Система защиты от массовых несанкционированных рассылок электронной почты на основе методов Data Mining

Московский государственный университет им. М.В. Ломоносова

На правах рукописи

Розинкин Андрей Николаевич

СИСТЕМА ЗАЩИТЫ ОТ МАССОВЫХ НЕСАНКЦИОНИРОВАННЫХ РАССЫЛОК ЭЛЕКТРОННОЙ ПОЧТЫ НА ОСНОВЕ МЕТОДОВ DATA MINING

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Ж^ЬЙЫЙ

■¿^¿¿МПЛЯР

Москве 2006

Работа выполнена на кафедре автоматизации систем вычислительных комплексов факультета вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова.

Научный руководитель:

доктор физико-математических наук, профессор Машечкин Игорь Валерьевич.

Официальные оппоненты:

член-корр. РАН,

доктор физико-математических наук Воеводин Владимир Валентинович;

кандидат физико-математических наук, доцент

Гайсарян Сергей Суренович.

Ведущая организация: Межведомственный суперкомпьютерный

центр РАН

Защита диссертации состоится " 14 " апреля 2006 г. в 11:00 часов на заседании диссертационного совета Д 501.001.44 в Московском государственном университете им. М.В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ. Автореферат разослан " 10 " марта 2006 г

Ученый секретарь , диссертационного совета профессор / у/у// л НЛ. Трифонов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

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

Задачу фильтрации спама, можно рассматривать как задачу классификации - определение принадлежности электронных писем к одному из заранее выделенных классов на основании анализа совокупности их признаков. Классы - это две категории писем - спам и легальная почта. Определим модель классификации - как данные, на основании которых выносится решение, к какому классу принадлежит письмо. Можно выделить две основные группы методов, используемых при решении задачи фильтрации спама:

- традиционные методы - это те методы, для которых модель классификации, или другими словами те данные, на основании которых классифицируются письма, определяется экспертом.

- обучаемые методы - это те методы, для которых модель классификации строится с помощью методов интеллектуального анализа данных (Data Mining).

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

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

РОС. НАЦИОНАЛЬНА 1

БИБЛИОТЕКА СПе О»

направлением исследования является совмещение этих двух подходов и развитие серверных персонифицированных систем фильтрации почты, использующих обучаемые алгоритмы классификации на основе методов интеллектуального анализа данных (Data Mining). Это утверждение строится на следующих фактах:

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

- персональная модель фильтрации более предпочтительна, нежели общая модель по причине большей точности и меньшего количества ошибок;

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

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

Цель работы

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

• предложить высокоэффективный и точный алгоритм классификации почты на основе методов интеллектуального анализа данных (Data Mining), который позволил бы использование персональной модели фильтрации;

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

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

Научная новизна

В работе предложен новый подход к решению задачи персональной фильтрации электронной почты на уровне почтового сервера с использованием методов классификации на основе алгоритмов интеллектуального анализа данных (Data Mining).

Разработан и реализован комплекс алгоритмов для решения задачи классификации почты на уровне почтового сервера.

Разработано системное решение, обеспечивающее

персонализированную фильтрацию электронной почты на уровне почтового сервера на основе алгоритмов интеллектуального анализа данных.

Практическая ценность

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

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

-ft к

î

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

Сравнительный анализ экспериментальной системы с распространенной коммерческой системой фильтрации электронной почты, основанной на использовании традиционных методов фильтрации, на реальных потоках писем показал превосходство разработанной системы.

Предложенный в работе подход и комплекс алгоритмов был реализован в виде экспериментальной системы фильтрации электронной почты. Экспериментальная система была интегрирована с несколькими распространенными серверами электронной почты.

Методы исследования

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

Апробация работы и публикации

По теме диссертации опубликовано 8 печатных работ. Результаты диссертации докладывались на объединенном научно-исследовательском семинаре кафедр АСВК, Алгоритмических языков и Системного программирования ВМиК МГУ под руководством проф. Шура-Бура М.Р., научно-исследовательском семинаре под руководством чл.корр. РАН Вл.В .Воеводина (НИВЦ МГУ), на семинарах факультета ВМиК и следующих научных конференциях:

• 7th International Conference on Enterprise Information Systems, Miami, USA,

2005;

• Всероссийская научно-техническая конференция «Методы и средства

обработки данных», Москва, Россия, 2005;

• Научная конференция «Тихоновские Чтения», Москва, МГУ, 2004;

• Научная конференция «Ломоносовские Чтения», Москва, МГУ, 2004;

• Научная конференция «Тихоновские Чтения», Москва, МГУ, 2005;

Работа поддерживается грантом РФФИ 05-01-00744а.

Структура и объем работы

Диссертация состоит из введения, четырех глав, заключения и библиографии. Объем диссертации 110 страниц. Библиография включает 81 наименование.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

- время обучения (время построения модели);

- время классификации нового письма;

- точность классификации;

- размер модели;

- скорость дообучения модели;

- предрасположенность алгоритма к избыточному обучению (overfitting). В результате сравнительного анализа в качестве наиболее перспективного

для использования в серверной системе фильтрации был выбран базовый алгоритм на основе метода опорных векторов (Support Vector Machines, SVM).

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

Формулируются концепции организации серверной системы фильтрации спама, использующей обучаемые методы классификации и определяются следующие основные требования, предъявляемые к ее архитектуре:

- возможность применения ресурсоемкого алгоритма классификации

- на основе алгоритмов машинного обучения;

- необходимый уровень производительности системы фильтрации почты, сравнимый с традиционными системами фильтрации;

- возможность масштабирования системы;

- независимость от платформы реализации, переносимость;

- возможность интеграции с различными почтовыми серверами;

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

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

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

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

- выбор модели представления данных;

- выбор меры сходства (потенциальной функции);

- сокращение тренировочного набора;

- повышение устойчивости метода опорных векторов к ошибкам в тренировочном наборе.

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

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

Для представления писем был выбран модифицированный вариант векторной модели. В терминах этой модели набор писем представляется в виде матрицы: = , в которой а{/ это весовой коэффициент ¡-ого признака, входящего в письмо к. Размерность этой матрицы определяется количеством писем в наборе и количеством выбранных признаков письма.

Было использовано два типа признаков, характеризующих электронные письма: текстовые признаки и признаки, не связанные с текстовым содержимым. Текстовые признаки - это все текстовые лексемы, входящие в письмо. Соответствующим элементом вектора представления письма является нормированная частота вхождения данной лексемы в письмо. Нетекстовые признаки - это статистические характеристики для письма, такие как, например средняя длина слова, а также тип, размер прикрепленных файлов.

Для определения весовых коэффициентов признаков была проведена серия экспериментов по сравнению различных подходов, в результате которых была выбрана следующая формула для вычисления весовых коэффициентов:

где ау - это весовой коэффициент 1-ого признака, входящего в письмо /у - частота встречаемости ьго признака в письме т - количество признаков в данном письме.

Далее в пункте 2.1.2 данного раздела рассматривается проблема сокращения пространства признаков. Помимо применения для предварительного сокращения признаков эмпирических правил, таких как:

- исключение наиболее частоупотребимых слов (на основании заранее определенного словаря);

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

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

- методы выбора признаков из существующего набора признаков;

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

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

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

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

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

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

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

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

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

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

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

Для того чтобы уменьшить влияние «выбросов» при построении гиперплоскости была предложена нечеткая модификация метода опорных

»

векторов (Fuzzy Support Vector Machines, FSVM). Для этого предлагается ввести дополнительную нечеткую характеристику для объектов обучающего набора, которая характеризовала бы степень «типичности» данного объекта для данного класса. В такой модели разные объекты тренировочного набора имеют разный вес, или важность и «выбросы» должны получить меньший вес, чем более типичные для данного класса объекты.

Предположим, что имеется тренировочный набор

D = {{x,y):x&Rn ,у&{-\\\}}, определена kernel-функция

K{xt,Xj)= (fp(xt\(р{х})), которая неявно задает отображение <р:Х Н из

исходного пространства X в пространство признаков Я. Идея метода опорных векторов - отыскать гиперплоскость (w,b), которая разделяет объекты двух классов в пространстве признаков Я так, чтобы граница между объектами разных классов была максимальна. Это приводит к следующей задаче »

оптимизации:

1 N

min<D(>v) = ~(w,w)+

2 (=i

при условии y,([w,xl)+b)'Z. 1-4,, ££0,Vje[l,...,JV]

Для нечеткой модификации метода опорных векторов тренировочный набор принимает вид ¿i:X [0,1], где Цу{х) -

функция принадлежности объекта х классу у или мера типичности. Му(х) тем меньшее значение принимает, чем менее типичен объект х для класса

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

Таким образом, штраф зависит от «важности» объекта тренировочного набора. Штраф за неверно классифицированный объект тем меньше, чем он

менее типичен для того класса, к которому он отнесен.

Для решения задачи определения функции принадлежности для тренировочного набора был применен нечеткий метод поиска исключений, использующий потенциальные функции, который является расширением метода Support Vector Clustering (SVC). Данный метод с помощью потенциальной функции К отображает объекты исходного множества X в векторное пространство характеристик Я существенно большей размерности. Отображение <р: X -> Н в явном виде не используется, а потенциальная функция определяет скалярное произведение в пространстве Я: К(х, у) = (<р(х), р(у))и. В пространстве характеристик строится гиперсфера, отделяющая компактное множество образов основной части объектов от остальных образов объектов, которые определяются как исключения. В оригинальном методе SVC решающая функция является бинарной.

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

Была проведена практическая апробация рассмотренного модифицированного алгоритма, продемонстрировавшая что, модифицированный метод опорных векторов показывает лучшую

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

В третьей главе рассмотрена архитектура реализованной системы фильтрации почты. Представлено описание пользовательского интерфейса и его основных функций. Рассмотрены детали интеграции системы с различными ■ почтовыми серверами.

Классифицирующий агент

\ I /

Коммуникационный агент

/ \

Индивиуальные

модели пользователей

Агент-процессор

Обучающий агент

801. РВ Общие структуры данных

Архитектура экспериментальной серверной системы

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

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

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

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

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

Общие структуры данных, словарь лексем, персональные настройки пользователей хранятся в базе данных.

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

Для экспериментальной системы классификации почты было разработано три типа различных классифицирующих агентов для следующих почтовых серверов: Microsoft Exchange 2000/2003, Communigate Pro, Sendmail, Exim (а также любой почтовый сервер, поддерживающий работу с агентом локальной доставки Procmail).

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

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

Для оценки используются два общедоступных набора писем. Первый -это широко известный набор LingSpam, который используется многими исследователями и разработчиками методов фильтрации спама. Второй набор -SpamAssassin public corpus, общедоступный набор реальных писем с известными характеристиками, предлагаемый разработчиками фильтра почты SpamAssassin для тестирования.

Во второй части главы представлены результаты сравнения экспериментальной системы фильтрации почты с распространенными алгоритмами и системами фильтрации электронной почты.

Результаты сравнительного анализа алгоритмов позволяют утверждать, что на эталонных тестовых наборах данных экспериментальный алгоритм показал лучшие результаты (как по уровню обнаружения, так и по уровню ложно-положительных ошибок) по сравнению с наиболее распространенным в существующих системах фильтрации обучаемым методом классификации Naïve-Bayes. Для сравнения использовались две реализации метода Naïve-Bayes: одна из них из распространенной некоммерческой системы фильтрации почты SpamAssassin и другая - экспериментальный алгоритм фильтрации на основе метода Naïve-Bayes, разработанного в Kaspersky Labs.

Далее в главе представлена комплексная оценка разработанной экспериментальной серверной персонализированной системы фильтрации почты на примере сравнения ее с наиболее известной и распространенной коммерческой серверной системой фильтрации почты Kaspersky Anti-Spam Enterprise Edition, использующей традиционные эвристические методы, в реальных условиях эксплуатации.

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

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

В заключении формулируются основные результаты работы.

Основные результаты

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

2. Разработан комплекс алгоритмов, основанный на развитии методов интеллектуального анализа данных (Data Mining), предназначенный для решения задачи классификации электронной почты на уровне почтового сервера.

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

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

Публикации автора по теме диссертации

1. Mashechkin, I., Petrovskiy, M., Rozinkin, A., Gerasimov, S. Enterprise Antispam Solution Based on Machine Learning Approach II Proceedings of 7th International Conference on Enterprise Information Systems, USA, Miami, 2005, Vol. 2, pp. 188-193

2. Герасимов C.B., Машечкин И.В., Петровский М.И., Розинкин А.Н. Мультиагентная архитектура для Machine Learning систем фильтрации спама масштаба предприятия И Тематический сборник факультета ВМиК МГУ «Программные системы и инструменты» №5, Изд. отдел ВМиК МГУ, Москва, 2005, сс. 113-123

3. Герасимов C.B., Машечкин И.В., Петровский М.И., Розинкин А.Н. Система предотвращения массовых рассылок на основе алгоритмов машинного обучения II Журнал Проблемы теории и практики управления. Программные продукты и системы, №3, МНИИПУ, Главная редакция

15

международного журнала и НИИ «Центрпрограммсистем», Тверь, 2005, сс. 10-15

4. Розинкин А.Н. Разработка и оптимизация модели представления электронных писем в обучаемых системах классификации электронной почты И МГУ им. Ломоносова, ф-т ВМиК, Москва, 2005. Деп. в ВИНИТИ 08.09.2005 № 1215-В2005

5. Розинкин А.Н. Разработка методов формирования оптимального тренировочного набора для системы классификации электронной почты на основе алгоритма опорных векторов II МГУ им. Ломоносова, ф-т ВМиК, Москва, 2005. Деп. в ВИНИТИ 08.09.2005 № 1216-В2005

6. Розинкин А.Н. Методы повышения эффективности алгоритма опорных векторов для задачи классификации электронной почты II Труды второй Всероссийской научной конференции «Методы и средства обработки данных», МГУ им. Ломоносова, Москва, 2005, сс. 182-187

7. Розинкин А.Н. Модели представления электронных писем в обучаемых системах классификации электронной почты II Тематический сборник факультета ВМиК МГУ «Программные системы и инструменты» №6, Изд. отдел ВМиК МГУ, Москва, 2005, сс. 80-87

8. Розинкин А.Н. Оптимизация тренировочного набора для системы классификации электронной почты на основе алгоритма опорных векторов II Тематический сборник факультета ВМиК МГУ «Программные системы и инструменты» №6, Изд. отдел ВМиК МГУ, Москва, 2005, сс. 88-94

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 03.03.2006 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 110 экз. Заказ 128. Тел. 939-3890. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

A££6¿

»-5803

ВВЕДЕНИЕ.

ГЛАВА 1. КОНЦЕПЦИИ ПОСТРОЕНИЯ ОБУЧАЕМОЙ СЕРВЕРНОЙ СИСТЕМЫ ФИЛЬТРАЦИИ ПОЧТЫ.

1.1 Выбор базового метода классификации.

1.1.1 Фильтрация почты, как задача классификации.

1.1.2 Модели представления объектов для задачи классификации.

1.1.2.1 Выделение признаков объектов.

1.1.2.2 Определение весовых коэффициентов признаков.

1.1.3 Методы классификации.

1.1.3.1 Naive Bayes.

1.1.3.2 Memory-Based (к ближайших соседей).

1.1.3.3 Линейный дискриминант Фишера.

1.1.3.4 Нейронные сети.

1.1.3.5 Метод опорных векторов.

1.1.4 Оценка методов классификации.

1.1.5 Выбор базового метода классификации.

1.2 Выбор архитектуры системного решения.

1.2.1 Архитектура серверных систем фильтрации спама.

1.2.2 Архитектура персонализированной обучаемой системы фильтрации почты серверного уровня

1.2.2.1 Функциональные стадии обучаемой системы классификации.

1.2.2.2 Особенности архитектуры.

1.3 выводы и результаты.

ГЛАВА 2. МОДИФИКАЦИЯ И ОРГАНИЗАЦИЯ ИСПОЛЬЗОВАНИЯ МЕТОДА ОПОРНЫХ ВЕКТОРОВ.

2.1 Модель представления данных.

2.1.1 Выбор модели представления данных.

2.1.2 Сокращение размерности пространства признаков.

2.1.3 Экспериментальное обоснование метода сокращения пространства признаков.

2.1.4 Выбор меры сходства (потенциальной функции).

2.2 Сокращение примеров тренировочного набора.

2.2.1 Предлагаемое решение.

2.2.2 Кластеризация тренировочного набора.

2.2.3 Экспериментальная проверка.

2.3 Борьба с шумом в тренировочном наборе.

2.3.1 Постановка проблемы.

2.3.2 Peutenue.

2.3.3 Определение функции принадлежности.

2.3.4 Эксперимент.

2.4 Выводы и результаты.

ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ.

3.1 Архитектура системы.

3.2 Пользовательский интерфейс.

3.2.1 Функциональные особенности.

3.2.1.1 Настройки обучения.

3.2.1.2 Настройки классификации.

3.2.1.3 Обучение и дообучение.

3.2.1.4 «Черные»/«белые» списки адресов отправителей.

3.2.1.5 Статистика обучения.

3.3 Программная реализация.

3.3.1 Концепция интеграции системы фильтрации с почтовыми системами.

3.3.2 Примеры интеграции с почтовыми системами.

3.3.2.1 Интеграция с Sendmail и Exim.

3.3.2.2 Интеграция с CommuniGate Pro.

3.3.2.3 Интеграция с Microsoft Exchange 2000 / 2003.

3.3.3 Программные модули, статистика.

3.3.4 Апробация экспериментальной системы.

3.4 выводы и результаты.

ГЛАВА 4. СРАВНИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ.

4.1 метрики оценки качества фильтрации.

4.2 Наборы данных.

4.2.1 LingSpam Corpus.

4.2.2 SpamAssassin Corpus.

4.3 Сравнительные тесты. а 4.3.1 Сравнение Naive Bayes (SpamAssassin).

4.3.1.1 Тестовые наборы.

4.3.1.2 Результаты тестирования.

4.3.1.3 Выводы.

Щ 4.3.2 Сравнение Naive Bayes (Лаборатория Касперского).

4.3.2.1 Тестовые наборы данных.

4.3.2.2 Сценарий эксперимента.

4.3.2.3 Результаты сравнения.

4.3.2.4 Выводы.

4.3.3 Сравнение с Kaspersky Anti-Spam.

4.3.3.1 Организация входящего потока писем.

4.3.3.2 Характеристики и настройки фильтров.

4.3.3.3 Характеристики наборов для первоначального обучения.

4.3.3.4 Характеристики настройки фильтров.

4.3.3.5 Контролируемые параметры.

4.3.3.6 Контроль и сбор результатов, дообучение.

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

4.4 Оценка производительности.

4.4.1 Оценка производительности алгоритма классификации.

4.4.2 Оценка производительности экспериментальной системы фильтрации почты.

Быстрый рост популярности электронных средств коммуникации, в том числе электронной почты, а также низкая стоимость их использования приводит к увеличивающемуся потоку несанкционированных массовых рассылок. По различным оценкам в настоящее время от 40 до 90% всех электронных сообщений в интернет являются спамом[26, 67].

Несанкционированные рассылки наносят очевидный ущерб - это реальные материальные потери компаний и пользователей сети. Например, убытки только крупных IT-компапий в США 2003 году от спама оценивается в $20.5 миллиарда[55]. Излишняя нагрузка на сети и оборудование, потраченное время на сортировку и удаление писем, потраченные деньги на оплату трафика - это неполный перечень проблем, которые приносит спам. Часто спам используется в качестве канала для распространения вирусов.

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

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

- предотвращение распространения спама;

- предотвращение получения спама, или фильтрация.

Первая категория - это различные административные и технические методы, направление на предотвращение рассылки спама. Сюда относятся такие решения как:

- законодательные меры по ограничению рассылки спама;

- новые протоколы электронной почты, использующие аутентификацию отправителя;

- блокирование почтовых серверов, пользователи которых рассылают спам.

Использование этих методов пока не дает значительных результатов. Наибольшую активность по законодательному ограничению распространения спама проявляют США, тем не менее, это не мешает тому, что с территории этой страны рассылается наибольшее количество спама в мире [46]. Одна из причин этого - большой уровень проникновения широкополосного доступа к интернет в США.

Предотвращение получения спама (фильтрация)

Предотвращение рассылки спама

Традиционные методы: Модель классификации готовится экспертом

Обучаемые" методы: Законодательные модель классификации ограничения, строится с помощью новые «почтовые» математических методов протоколы

Рисунок 1 Классификация средств, методов и подходов для борьбы со спамом.

Существуют разработки, предлагающие решить проблему несанкционированных массовых рассылок с помощью использования нового почтового протокола. Усилия по созданию таких протоколов прилагались различными группами и консорциумами. Наиболее известные из них - это Sender ID, Sender Policy Framework (SPF), DomainKeys [23, 48, 66]. Использование такого протокола - это значительные дополнительные расходы. Основная проблема заключатся во внедрении нового протокола.

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

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

Задачу фильтрации спама, можно рассматривать как задачу классификации [14] -определение принадлежности объекта к одному из заранее выделенных классов на основании анализа совокупности признаков, характеризующих данный объект. Объекты - это электронные письма. Классы - это две категории писем - спам и легальная почта. Определим модель классификации - как данные, на основании которых выносится решение, к какому классу принадлежит объект. Можно выделить две основные группы методов, используемых при решении задачи фильтрации спама:

- традиционные методы - это те методы, для которых модель классификации, или другими словами те данные, на основании которых классифицируются письма, определяется экспертом.

- обучаемые методы - это те методы, для которых модель классификации строится с помощью методов интеллектуального анализа данных (Data Mining).

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

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

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

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

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

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

Одним из первых [22] средств предотвращения массовых рассылок, активно применяемых в настоящее время, являются системы, использующие «черные» списки IP-адресов отправителей спама - DNSBL (DNS-based Black-hole List), RBL (Real-time Black-hole List) [44, 50].

Устроены они следующим образом. Имеется список IP-адресов потенциальных или замеченных распространителей спама, доступ к которому осуществляется в реальном времени по протоколу DNS. Почтовый сервер, использующий такой сервис, во время приема сообщения отсылает запрос, присутствует ли IP-адрес отправителя письма в черном списке и на основании ответа принимает или отвергает письмо. Существует большое количество подобных сервисов, отличающихся в основном условиями занесения и исключения из списков.

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

Для таких систем фактически невозможно оценить уровень ложно-положительных ошибок (легальная почта, ошибочно классифицированная как спам) на реальных потоках писем. Оценка сервисов с помощью архивов почты не совсем корректна, так как список IP-адресов постоянно меняется и актуален на данный момент времени, а письма тестируются при этом «старые». Тем не менее, проводившиеся эксперименты показывают[12] невысокую эффективность таких методов (40-60%) при достаточно высоком уровне ложно положительных ошибок (2,3-4,1%).

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

- голосование пользователей (Razor / Pyzor) [54, 56];

- анализ всей почты, проходящей через почтовую систему (DCC) [58];

- прием почты в «ловушки» спама и последующий анализ (коммерческие системы:

Symantec Brightmail Anti-Spam) [72].

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

Для методов на основе обнаружения повторов характерны две существенные проблемы[13]. Во-первых, это «персонализация» спама-каждое письмо в рассылке имеет незначительные отличия, за счет чего затрудняется построение устойчивых сигнатур. Для решения этой проблемы используются различные устойчивые сигнатуры, например, реализованный в системе Яндекс.Почта метод шинглов[9, 10]. Вторая проблема - это обнаружение легальных рассылок.

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

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

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

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

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

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

3. Актуальным для традиционных методов является вопрос безопасности. Принципиальный момент в том, что решение о том, что есть спам, а что есть легальная почта, принимается третьей стороной. Это порождает несколько проблем безопасности. Третья сторона управляет тем, какую почту получает пользователь. Кроме того, от провайдера зависит и качество фильтрации почты. Для многих организаций такой подход к безопасности является недопустимым.

4. Большинство систем, основанных на традиционных методах - национальные. Правила и шаблоны зависят от естественного языка, для которого опи созданы. Сигнатуры создаются провайдерами обновлений для определенного рынка.

Таким образом, традиционные методы обладают следующими недостатками:

- необходимость регулярных обновлений базы знаний (для поддержания ее актуального состояния);

- зависимость от поставщиков обновлений;

- низкий уровень безопасности (благодаря зависимости от сторонних поставщиков);

- «неперсонифицированная» модель классификации (не учитывает индивидуальные особенности переписки пользователя);

- зависимость от естественного языка переписки;

- относительно невысокий уровень обнаружения (как минимум, благодаря общей модели классификации).

Активно развивающимся в настоящее время направлением фильтрации электронной почты является разработка и использование обучаемых, или так называемых интеллектуальных методов, использующих алгоритмы интеллектуального анализа данных (Data Mining). Такие алгоритмы разделяют объекты на несколько категорий, используя для классификации модель, построенную заранее на базе прецедентной информации[14, 65].

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

Xi.Yi) х^спам)

Алгоритм классификации

Xi,yi} - тренировочный набор X| = {легальные письма, примеры спама} yi = {спам, легальные} i = 1.n ill

Модель

Рисунок 2 Обучаемая система классификации почты

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

Основное достоинство таких методов - возможность строить персональную модель классификации почты, т.е. пользователь сам может определять, что для него является легальной почтой, а что спамом. Благодаря этому такие методы имеют более высокий уровень обнаружения спама. Наибольшее распространение из интеллектуальных методов в настоящее время получил метод Байеса. [31, 60]. Он реализован и успешно применяется в некоторых системах обнаружения спама[17, 53, 68, 69].

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

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

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

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

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

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

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

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

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

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

- по области действия: на серверные и клиентские;

- по аудитории: на персональные и общие;

- по используемым принципам классификации: на традиционные и обучаемые.

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

Обучаемые Традиционные

Персональные Наиболее перспективный и интересный класс систем фильтрации. Не распространены

Общие Распространены незначительно Наиболее распространенный класс серверных фильтров почты.

Таблица 1 Системы фильтрации электронной почты серверного уровня.

Обучаемые Традиционные

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

Общие Не распространены Достаточно распространенный класс фильтров

Таблица 2 Системы фильтрации электронной почты уровня почтового клиента пользователя.

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

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

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

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

Kaspersky Anti-Spam

Наиболее известная и распространенная в настоящее время коммерческая система фильтрации почты серверного уровня, основанная на традиционных методах фильтрации[36]. В основе данной системы лежит технология «Спамтест»[2], основанная полностью на традиционных методах фильтрации, в том числе RBL, база нечетких сигнатур писем со спамом, база эвристических правил. Базы знаний поддерживаются и регулярно обновляются (до 3 раз в час) вручную круглосуточно функционирующей лабораторией экспертов. Поддерживаются также обработка прикрепленных файлов, обнаружение повторов (массовости рассылки). Система имеет общую модель классификации для всех пользователей, персонализация отсутствует.

Заявляемая производительность системы Kaspersky Anti-Spam ISP Edition - до 2 млн. сообщений в сутки на сервере, имеющем следующую конфигурацию: Intel Pentium 4, 2.4 ГГц, 1 ГБ RAM, 2 IDE HDD (Western Digital, 40 ГБ, 8 МБ кэш). Операционная система: RedHat Linux 7.3 [2, 36].

MailShell

MailShell - крупнейшее коммерческое решение для фильтрации спама, предлагаемое как в OEM исполнении так и в виде конечного продукта [43]. Используется, в частности, в почтовом сервере CommuniGate Pro.

ID Modules and Databases

10 Modules, used to compute | overall spam probability.

ID Databases, used to compute | overall spam probability. Щ

Mailshell SpamLabs

Rules, including pattern matches, 1 statistical heuristic functions, J computer algorithms, etc.

Databases, including locally I cached databases oi white lists, ' blacklist's, fingerprints, etc.

Рисунок 3 Система фильтрации MailShell. (с) MailShell Inc.

Фильтр содержит несколько компонентов, осуществляющих фильтрацию следующим принципам. Использование устойчивых шаблонов писем со спамом. Использование метода обнаружения повторов с поддержкой голосования пользователями. Использование черных списков (IP-адресов и e-mail адресов) распространителей спама. Использование шаблонов и сигнатур для анализа содержимого писем и специфичных признаков спам-рассылок. В данном решении также применяется баесовский статистический анализ для построения нечетких сигнатур писем со спамом, анализа содержимого писем (Рисунок 3).

Для серверных систем, основанных на данном решении, персонализация отсутствует.

SpamAssassin

SpamAssassin, наиболее популярный фильтр спама с открытыми исходными текстами[18]. Применяется как отдельно, так и в составе большого числа, в том числе коммерческих продуктов.

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

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

На момент начала данной работы SpamAssassin поддерживал обучаемый алгоритм классификации на основе метода Байеса (Nai've-Bayes)[31, 60] общей для всех пользователей системы. В соответствующей главе работы приводятся результаты сравнения данного алгоритма с разработанным экспериментальным алгоритмом.

Следует отметить что в последнее время ведущие мировые производители средств фильтрации спама начали внедрение концепции персонализированной фильтрации на основе обучаемых методов в свои серверные решения. В частности, в фильтре SpamAssassin со второй половины 2004 года заявлено использование персональных моделей для классификатора на основе метода Байеса.

Фильтрация спама на публичных почтовых сервисах

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

В частности, компанией Яндекс для детектирования массовых рассылок в публичном почтовом сервисе Яндекс.Почта используется свой собственный продукт «Спамооборона»[11]. Этот продукт также распространяется как серверное решение фильтрации почты для сторонних почтовых серверов. Система использует традиционные методы обнаружения, среди которых данные собственного RBL, наборы эвристик и оригинальная технология детектирования массовых повторов на основе вычисления устойчивых сигнатур специального вида - шинглов. База знаний системы регулярно обновляется и поддерживается специальной службой. Заявляется также, что система учитывает персональную информацию о пользователе для минимизации ложно-положительных ошибок, но более подробная информация по этому вопросу отсутствует[10, 43].

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

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

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

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

- персональная модель фильтрации более предпочтительна, нежели общая модель по причине большей точности и меньшего количества ошибок;

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

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

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

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

Результаты данной диссертационной работы докладывались автором на следующих конференциях и научных семинарах:

- Ломоносовские чтения, Москва, апрель 2004;

- Доклад на научно-исследовательском семинаре под руководством чл.корр. РАН

Вл.В. Воеводина (НИВЦ МГУ), май 2004;

- Тихоновские чтения, Москва, ноябрь 2004;

- 7th International Conference on Enterprise Information Systems, USA, Miami, май

2005;

- Доклад на научно-исследовательском семинаре под руководством проф. М.Р.

Шура-Бура, июнь 2005;

- Всероссийская научно-техническая конференция «Методы и средства обработки данных», Москва, Россия, октябрь 2005;

- Тихоновские чтения, Москва, октябрь 2005.

Основные результаты работы изложены в 8-ми научных публикациях.

Диссертационная работа состоит из введения, четырех глав, заключения и библиографии. Далее излагается краткое содержание работы.

Основные результаты диссертации:

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

2. Разработан комплекс алгоритмов, основанный на развитии методов интеллектуального анализа данных (Data Mining), предназначенный для решения задачи классификации электронной почты на уровне почтового сервера.

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

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

Заключение

1. Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин, Москва, Наука, 1970

2. Ашманов и Партнёры. Технология «Спамтест». Описание технологии. http://www.spamtest.ru/techno1ogy-e.htrnl.

3. Бари Н.К. Тригонометрические ряды. М.: Гос. издательство физико-математической литературы, 1961

4. Пашко Д. Еще раз про RBL'u. Ашманов и Партнёры, июнь, 2005, http://www.spamtest.ru/document.html?context=15932&pubid-19256

5. Петровский М.И. Исследование и разработка алгоритмов поиска исключений в системах интеллектуального аначиза данных, МГУ им. Ломоносова, Москва, 2003

6. Розинкин А.Н. Разработка и оптимизация модели представления электронных писем в обучаемых системах классификации электронной почты. МГУ им. Ломоносова, ф-т ВМиК Москва, 2005. Деп. в ВИНИТИ 08.09.2005 № 1215-В2005

7. Розинкин А.Н. Разработка методов формирования оптимального тренировочного набора для системы классификации электронной почты на основе алгоритма опорных векторов. МГУ им. Ломоносова, ф-т ВМиК Москва, 2005. Деп. в ВИНИТИ 08.09.2005 № 1216-В2005

8. И. Сегалович. Некоторые автоматические методы детектирования спама, доступные большим почтовым системам. Яндекс, декабрь 2004, http://company.yandex.ru/articles/antispam.xml

9. И. Сегалович, Д. Тейблюм, А. Дилевский. Пршщипы и технические методы работы с незапрашиваемой корреспонденцией. Яндекс, сентябрь 2003, http://company.yandex.ru/articles/spamooborona.html

10. Спамооборона. Описание технологии. Яндекс, 2005-2006, http://so.yandex.ni/technique.xml

11. Тутубалнн Алексей. RBL: вред или польза? Ашманов и Партнёры, сентябрь, 2003, http://www.spamtest.ni/document.html?context=15932&pubid=22

12. Алексей Тутубалнн. Распределенные методы обнаружения спама. Ашманов и Партнёры, февраль, 2004, http://www.spamtest.ru/document.html?context=15932&pubid=41

13. Aas К. and Eikvil L. Text categorisation: A survey. Technical report, Norwegian Computing Center, June 1999

14. Almeida, M. В., Braga, A. P., Braga, J. P.: SVM-KM: speeding SVMs learning with a priori cluster selection and k-means. In: Proceedings of the 6th Brazilian Symposium on Neural Networks (2000) 162-167

15. Apache Software Foundation. The Apache SpamAssassin Project http://spamassassin.apache.org

16. Apache Software Foundation. The Apache SpamAssassin Public Corpus http://spamassassin.apache.org/publiccorpus/

17. Ben-Hur, Asa, Horn, David, Siegelmann, Hava Т., and Vapnik, Vladimir. Support vector clustering. Journal of Machine Learning Research, 2:125-137, 2001

18. Bishop, Christopher M. Neural Networks for Pattern Recognition, Oxford University Press, 1995

19. Bradley, A.P., The use of the area under the roc curve in the evaluation of machine learning algorithms. Pattern Recognition, 30(7), 1145-- 1159, (1997).

20. DNSBL, DNS-based Blackhole List. Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/wiki/DNSBL

21. DomainKeys Identified Mail, http://antispam.yahoo.com/domainkevs

22. Drucker, H., Wu, D. and Vapnik, V. Support Vector Machines for Spam Categorization, IEEE Trans, on Neural Networks, vol 10, number 5, pp. 1048-1054, 1999

23. Email Systems, Email Systems Ltd. http://www.emailsystems.com

24. Fanner, J. (2004)SpamPal -Mail Classification Program http://www.spampal.org

25. Forman, G. An extensive empirical study of feature selection metrics for text classification. Journal of Machine Learning Research, 3, pp. 1289-1305, 2003

26. Golub, G.H. and van Loan, C.F. Matrix Computations. North Oxford Academic, Oxford, UK, 1983

27. Goutte, C., Gaussier, E. A Probabilistic Interpretation of Precision, Recall and F-score, with Implication for Evaluation, ECIR'05, 2005

28. Graham, P. A Plan For Spam, 2002 http://www.paulgraham.com/spam.html

29. Gurney K., An Introduction to Neural Networks, UCL Press, 1997

30. Haung H.-P., Liu Y.-H. Fuzzy support vector machines for pattern recognition and data mining, International Journal of Fuzzy Systems, Vol.4, No.3, September 2002, pp.826835

31. Huang, S. Y., Lee, Y. J.: Reduced support vector machines: a statistical theory. Technical report, Institute of Statistical Science, Academia Sinica, Taiwan. http://www.stat.sinica.edu.tw/syhuang/ (2004)

32. Joachims, T. Text Categorization with Support Vector Machines: Learning with Many Relevant Features. Proceedings of {ECML}-98, 10th European Conference on Machine Learning, Springer Verlag, Heidelberg, DE, 137-142,1998

33. Kaspersky Labs, Kaspersky Anti-Spam Enterprise Edition http://www.kaspersky.com/antispamenterprise http://www.kaspersky.ru/smb?chapter=145592822

34. Koggalage, R., Halgamuge, S. Reducing the Number of Training Samples for Fast Support Vector Machine Classification. Neural Information Processing, Vol. 2, No. 3, March 2004, pp.57-65

35. Lee S., Paik E., Lee Y., Time Series Data Pattern Classification using Fuzzy Membership Functions and Support Vector Machines. KOSPI 200: Korea Composite Stock Price Index, IPSJSIG Notes Intelligence and Compex Systems, No.133-021,2003

36. Lee, Y. J., Mangasarian, O. L.: RSVM: Reduced support vector machines. In Proceedings of the First SIAM International Conference on Data Mining (2001)

37. Leopold, E., & Kindermann, J. Text categorization with support vector machines: How to represent texts in input space. Machine Learning, 46, pp. 423-444, 2002

38. Lin C.-F., Sheng-De, Fuzzy Support Vector Machines. IEEE Transaction on Neural Networks, Vol.12, No.2., March 2002.

39. Lin C.-F., Sheng-De, Using Fuzzy Support Vector Machines to Learn Small Training Sets: Its Application to PCA-based Face Recognition, Proceedings of FIP'2003, Taiwan, 2003

40. MailShell Inc., MailShell Anti-Spam Technology, 2005, http://www.mailshell.com/mail/client/oem2.html/step/howitworks

41. MAPS Mail Abuse Prevention System, LLC http://www.mailabuse.com

42. Mashechkin, I., Petrovskiy, M. and Rozinkin, A. Enterprise Anti-spam Solution Based on Machine Learning Approach II Proceedings of 7th International Conference on Enterprise Information Systems, USA, Miami, 2005, Vol. 2, pp.188-193.

43. MessageLabs Intelligence, A Spammer In The Works, http://www.messagelabs.com

44. Microsoft Corp., Microsoft Exchange Server 2003, SDK Documentation, Anti-Spam Infrastructure. MSDN Library, 2006 http://msdn.microsoft.com/library/defau1t.asp7urWlibrarv/enus/e2k3/e2k3/ast anti spam infrastructure.asp

45. Microsoft Corp. Sender ID technology http://www.microsoft.com/senderid

46. Mladenic, D. Feature subset selection in text learning. ECML'98, pp.95-100, 1998

47. ORDB.org Open Relay Database http://www.ordb.org

48. Petrovskiy, M. A Fuzzy Kernel-Based Method for Real-Time Network Intrusion Detection, Innovative Internet Community Systems, Third International Workshop, IICS 2003, pp. 189-200, Leipzig, Germany, 2003

49. Petrovskiy, M. An Approach to Membership Model Identification for Fuzzy Support Vector Machines. Proceedings of International Conference on Recent Advances in Soft Computing, United Kingdom, Nottingham, 2004, pp. 45-50

50. POPFile Automatic Email Classification http://popfile.sourceforge.net

51. Pyzor Project, http://pyzor.sourceforge.net/, 2005

52. The Radicati Group, Inc. The Messaging Technology Report, 2003 http ://www. radicati .com

53. Razor Project, http://razor.sourceforge.net/. 2005

54. Reuters. Reuters-21578 text categorization test collection, Distribution 1.0. Reuters. http://www.daviddlewis.com/resources/testcollections/reuters21578.

55. Rhyolite Software, Distributed Checksum Clearinghouse (DCC) Project, http://www.rhvolite.com/anti-spam/dcc/. 2005

56. Rogati, M., & Yang, Y. High-performing feature selection for text classification. CIKM'02, pp. 659-661, 2002

57. Sahami, M., Dumais, S., Heckerman, D., and Horvitz, E. A Bayesian approach to filtering junk email. AAAI Workshop on Learning for Text Categorization, Madison, Wisconsin. AAAI Technical Report WS-98-05, 1998

58. Salton, G. & McGill, J. An introduction to modern information retrieval. New York: McGraw-Hill, 1983

59. Scholkopf, B. and Smola, A., J. Learning with kernels: Support Vector Machines, Regularization, Optimization and Beyond. The MIT Press Cambridge, Massachusetss, 2000

60. Scott С. Deerwester, Susan Т. Dumais, Thomas K. Landauer, George W. Fumas and Richard A. Harshman, Indexing by Latent Semantic Analysis. Journal of the American Society of Information Science, Vol. 41, No. 6, pp. 391-407,1990

61. Sebastiani, F. Machine Learning in Automated Text Categorization, ACM Computing Surveys, Vol. 34, No. 1, March 2002, pp. 1-47, 2002

62. Sender Policy Framework http://www.openspf.org/

63. Spam Filter Software Review, eCatapult, Inc. http://www.spamfilterreview.com

64. Spam Inspector, GIANT Company Software, Inc. http://www.spaminspector.com

65. SpamPal Mail Classification Program http://www.spampal.org

66. Stenberg, D. libcURL the multiprotocol file transfer library, http://curl.haxx.se/libcurl/

67. Stalker Software Inc. CommuniGate Pro Core Server, http://www.stalker.com/content/groupware.htm

68. Symantec, Symantec Brightmail Anti-Spam, http://www.symantec.com/, 2005

69. Thorsten, J. A Statistical Learning Model of Text Classification with Support Vector Machines. In Proceedings of SIGIR-01, New Orleans, US, 2001. ACM Press, NY, 2001

70. University of Washington, IMAP Information Center, C-client library, http://www.washington.edu/imap/

71. Vapnik, V., N. The nature of statistical learning theory. Springer-Verlag New York, Inc., New York, NY, 1995

72. Vapnik, V., N. Statistical learning theory, Wiley, New York, 1998

73. O. de Vel, Anderson, A., Comey, M. & Mohay, GM, Mining email content for author identification forensics. SIGMOD Record, 30(4), pp. 55-64,2001

74. Yang, Y. An Evaluation of Statistical Approaches to Text Categorization. Information Retrieval, 1, 1/2,69-90, 1999

75. Yang Y. and Pedersen, J. O. A comparative study of feature selection in text categorization, Proceedings of the Fourteenth International Conference on Machine Learning, Morgan Kaufman Publishers, pp.412-420, 1997

76. Yang Y. and Pedersen, J. O. Feature selection in statistical learning of text categorization. In Proc. of the 14th International Conference of Machine Learning ICML97, pp.412-420, 1997