Содержание к диссертации
Введение
ГЛАВА 1. Концепции построения обучаемой серверной системы фильтрации почты 20
1.1 выбор базового метода классификации 20
1.1.1 Фильтрация почты, как задача классификации 20
1.1.2 Модели представления объектов для задачи классификации 21
1.1.2.1 Выделение признаков объектов 22
1.1.2.2 Определение весовых коэффициентов признаков 23
1.1.3 Методы классификации 24
1.1.3.1 Naive Bayes 25
1.1.3.2 Memory-Based (к ближайших соседей) 26
1.1.3.3 Линейный дискриминант Фишера 26
1.1.3.4 Нейронные сети 29
1.1.3.5 Метод опорных векторов 30
1.1.4 Оценка методов классификации 34
1.1.5 Выбор базового метода классификации 35
1.2 Выбор архитектуры системного решения 36
1.2.1 Архитектура серверных систем фильтрации спама 36
1.2.2 Архитектура персонатзированной обучаемой системы фильтрации почты серверного уровня 38
1.2.2.1 Функциональные стадии обучаемой системы классификации 38
1.2.2.2 Особенности архитектуры 39
1.3 Выводы и результаты 42
ГЛАВА 2. Модификация и организация использования метода опорных векторов 43
2.1 Модель представления данных 43
2.1.1 Выбор модели представления данных 43
2.1.2 Сокращение размерности пространства признаков 44
2.1.3 Экспериментальное обоснование метода сокращения пространства признаков 50
2.1.4 Выбор меры сходства (потенциальной функции) 52
2.2 Сокращение примеров тренировочного набора 53
2.2.1 Предлагаемое решение 54
2.2.2 Кластеризация тренировочного набора 55
2.2.3 Экспериментальная проверка 56
2.3 Борьба с шумом в тренировочном наборе 58
2.3.1 Постановка проблемы 58
2.3.2 Решение 59
2.3.3 Определение функции принадлежности 60
2.3.4 Эксперимент 61
2.4 Выводы и результаты 62
ГЛАВА 3. Программная реализация 64
3.1 Архитектура системы 64
3.2 Пользовательский интерфейс 72
3.2.1 Функциональные особенности 73
3.2.1.1 І Іастройки обучения 73
3.2.1.2 Настройки классификации 74
3.2.1.3 Обучение и дообучение 74
3.2.1.4 «Черные»/«белые» списки адресов отправителей 75
3.2.1.5 Статистика обучения 76
3.3 Программная реализация 76
3.3.1 Концепция интеграции системы фшьтрации с почтовыми системами 77
3.3.2 Примеры интеграции с почтовыми системами 78
3.3.2.1 Интеграция с Sendmail и Exim 78
3.3.2.2 Интеграция с CommuniGate Pro 79
3.3.2.3 Интеграция с Microsoft Exchange 200012003 79
3.3.3 Программные модули, статистика 81
3.3.4 Апробация экспериментальной системы 81
3.4 Выводы и результаты 82
ГЛАВА 4. Сравнительные эксперименты 83
4.1 Метрики оценки качества фильтрации 83
4.2 Наборы данных 85
4.2.1 LingSpam Corpus 85
4.2.2 Spamassassin Corpus 85
4.3 Сравнительные тесты 85
4.3.1 Сравнение Naive Bayes (SpamAssassin) 85
4.3.1.1 Тестовые наборы 86
4.3.1.2 Результаты тестирования 86
4.3.1.3 Выводы 90
4.3.2 Сравнение Naive Bayes (Лаборатория Касперского) 91
4.3.2.1 Тестовые наборы данных 91
4.3.2.2 Сценарий эксперимента 92
4.3.2.3 Результаты сравнения 92
4.3.2.4 Выводы 95
4.3.3 Сравнение с Kaspersky Anti-Spam 96
4.3.3.1 Организация входящего потока писем 96
4.3.3.2 Характеристики и настройки фильтров 97
4.3.3.3 Характеристики наборов для первоначального обучения 98
4.3.3.4 Характеристики настройки фильтров 98
4.3.3.5 Контролируемые параметры 99
4.3.3.6 Контроль и сбор результатов, дообучение 99
4.3.3.7 Результаты эксперимента 100
4.4 Оценка производительности 101
4.4.1 Оценка производительности ачгоритма классификации 101
4.4.2 Оценка производительности жсперимеитаїьной системы фильтрации почты 102
Заключение 103
Литература
- Модели представления объектов для задачи классификации
- Экспериментальное обоснование метода сокращения пространства признаков
- «Черные»/«белые» списки адресов отправителей
- Сравнение Naive Bayes (Лаборатория Касперского)
Введение к работе
Быстрый рост популярности электронных средств коммуникации, в том числе электронной почты, а также низкая стоимость их использования приводит к увеличивающемуся потоку несанкционированных массовых рассылок. По различным оценкам в настоящее время от 40 до 90% всех электронных сообщений в интернет являются спамом[26,67].
Несанкционированные рассылки наносят очевидный ущерб - это реальные материальные потери компаний и пользователей сети. Например, убытки только крупных ІТ-компаний в США 2003 году от спама оценивается в $20.5 миллиарда[55]. Излишняя нагрузка на сети и оборудование, потраченное время на сортировку и удаление писем, потраченные деньги на оплату трафика - это неполный перечень проблем, которые приносит спам. Часто спам используется в качестве канала для распространения вирусов.
Следовательно, является практически значимым исследование, разработка и создание новых алгоритмов, методов, средств и систем, обеспечивающих защиту пользователей от несанкционированных массовых рассылок электронной почты и минимизирующих приносимый такими рассылками ущерб.
В настоящее время разработаны различные средства, методы и подходы для борьбы со спамом. Их можно разделить на две категории:
предотвращение распространения спама;
предотвращение получения спама, или фильтрация.
Первая категория - это различные административные и технические методы, направление на предотвращение рассылки спама. Сюда относятся такие решения как:
законодательные меры по ограничению рассылки спама;
новые протоколы электронной почты, использующие аутентификацию отправителя;
блокирование почтовых серверов, пользователи которых рассылают спам.
Использование этих методов пока не дает значительных результатов. Наибольшую активность по законодательному ограничению распространения спама проявляют США, тем не менее, это не мешает тому, что с территории этой страны рассылается наибольшее количество спама в мире [46]. Одна из причин этого - большой уровень проникновения широкополосного доступа к интернет в США.
Предотвращение получения Предотвращение
спама (фильтрация) рассылки спама
Традиционные методы: "Обучаемые" методы: Законодательные
Моделышассификации модель классификации ограничения,
готовится экспертом строится с помощью новые «почтовые»
математических методов протоколы
Рисунок 1 Классификация средств, методов и подходов для борьбы со спамом.
Существуют разработки, предлагающие решить проблему несанкционированных массовых рассылок с помощью использования нового почтового протокола. Усилия по созданию таких протоколов прилагались различными группами и консорциумами. Наиболее известные из них - это Sender ID, Sender Policy Framework (SPF), DomainKeys [23, 48, 66]. Использование такого протокола - это значительные дополнительные расходы. Основная проблема заключатся во внедрении нового протокола.
Существует ряд подходов, предлагающих сделать рассылку спама экономически невыгодной. Одним из таких является предложение сделать отправку каждого электронного сообщения платным. Плата за одно сообщение должна быть крайне незначительной. В этом случае для обычного пользователя это будет незаметным. Для тех, кто занимается рассылкой спама, чтобы достигнуть заметного результата, необходимо разослать одновременно сотни тысяч и миллионы сообщений. В этом случае стоимость такой рассылки становится значительной, что делает ее экономически невыгодной.
Вторая категория средств борьбы с несанкционированными массовыми рассылками - это методы, направленные на предотвращение получения спама пользователями, так называемые методы фильтрации спама.
Задачу фильтрации спама, можно рассматривать как задачу классификации [14] -определение принадлежности объекта к одному из заранее выделенных классов на основании анализа совокупности признаков, характеризующих данный объект. Объекты - это электронные письма. Классы - это две категории писем - спам и легальная почта. Определим модель классификации - как данные, на основании которых выносится решение, к какому классу принадлежит объект. Можно выделить две основные группы методов, используемых при решении задачи фильтрации спама:
традиционные методы - это те методы, для которых модель классификации, или другими словами те данные, на основании которых классифицируются письма, определяется экспертом.
обучаемые методы - это те методы, для которых модель классификации строится с помощью методов интеллектуального анализа данных (Data Mining).
Таким образом, для фильтрации электронной почты можно примерять широкий спектр методов, используемых для решения задачи классификации. Учитывая специфику предметной области, основную сложность представляет выбор базового метода классификации и его адаптация к условиям применения в задаче фильтрации спама.
Для оценки качественных характеристик методов классификации будут применяться такие критерии как уровень обнаружения и уровень ложно-положительных ошибок. Уровень обнаружения - это отношение количества правильно распознанных писем со спамом к общему количеству писем со спамом в тестовом наборе. Этот критерий характеризует, насколько точно алгоритм обнаруживает несанкционированные письма. Уровень ложно-положительных ошибок - это отношение количества легальных писем, ошибочно распознанных алгоритмом как спам к общему количеству легальных писем в тестовом наборе. Этот критерий характеризует, насколько редко алгоритм ошибается, классифицируя легальные письма как спам.
Рассмотрим более подробно традиционные методы фильтрации электронной почты и определим их достоинства и недостатки. Современные традиционные методы основываются на следующих категориях информации, подготовленной экспертами:
информация, которая характеризует свойства содержимого писем со спамом: различные правила, шаблоны, ключевые слова которые используются для анализа письма;
списки IP адресов серверов, с которых осуществляется рассылка спама. Хранилище данных, подготовленных экспертами, называется базой знаний. Отдельно стоит сказать о такой информации, как списки доверия и недоверия
адресов отправителей почты. Сейчас это не столько средство фильтрации спама, сколько средство отбора легальной почты. Так как распространители спама используют фиктивные адреса отправителя, фактически для пользователя имеет смысл только создание «белого» списка. Т.е. списка адресов отправителей, письма от которых гарантированно не являются спамом. Это средство не может выступать в качестве
полноценного фильтра почты, но может значительно уменьшить количество ложных срабатываний, будучи частью системы фильтрации почты, использующей некоторые другие методы классификации.
Большинство существующих коммерческих и распространенных систем фильтрации спама строятся на использовании традиционных методов. Наиболее распространенные из них это анализ содержимого писем на соответствие вручную заданных эвристических правил и шаблонов, использование сигнатур писем со спамом для детектирования повторов и использование черных списков ІР-адресов машин, с которых отправляется спам.
Одним из первых [22] средств предотвращения массовых рассылок, активно применяемых в настоящее время, являются системы, использующие «черные» списки ІР-адресов отправителей спама - DNSBL (DNS-based Black-hole List), RBL (Real-time Black-hole List) [44, 50].
Устроены они следующим образом. Имеется список ІР-адресов потенциальных или замеченных распространителей спама, доступ к которому осуществляется в реальном времени по протоколу DNS. Почтовый сервер, использующий такой сервис, во время приема сообщения отсылает запрос, присутствует ли IP-адрес отправителя письма в черном списке и на основании ответа принимает или отвергает письмо. Существует большое количество подобных сервисов, отличающихся в основном условиями занесения и исключения из списков.
Достоинство такого метода - обнаружение спама в самом начале приема сообщения. Недостатки заключаются в том, политика добавления и исключения адресов не всегда прозрачна. Часто благодаря этому или по ошибке в список попадают целые подсети, принадлежащие провайдерам^], что приводит к тому, что почта из таких подсетей перестает приниматься вовсе, в том числе и от легальных пользователей.
Для таких систем фактически невозможно оценить уровень ложно-положительных ошибок (легальная почта, ошибочно классифицированная как спам) на реальных потоках писем. Оценка сервисов с помощью архивов почты не совсем корректна, так как список ІР-адресов постоянно меняется и актуален на данный момент времени, а письма тестируются при этом «старые». Тем не менее, проводившиеся эксперименты показывают[12] невысокую эффективность таких методов (40-60%) при достаточно высоком уровне ложно положительных ошибок (2,3-4,1%).
Следующим распространенным методом предотвращения спама является метод обнаружения повторов, основанный на свойстве массовости писем в рассылке и их схожести. Такие методы подразумевают, что рассылка продолжается долгое количество времени, поэтому если обнаружить ее в самом начале, то после этого времени конкретно эту рассылку можно было бы блокировать. Для собора информации о такой рассылке используются следующие методы:
голосование пользователей (Razor / Pyzor) [54, 56];
анализ всей почты, проходящей через почтовую систему (DCC) [58];
прием почты в «ловушки» спама и последующий анализ (коммерческие системы: Symantec Brightmail Anti-Spam) [72].
Вне зависимости от способа обнаружения рассылки идея метода такова, что для письма создается сигнатура (контрольная сумма), которая затем доставляется к системе фильтрации почты и используется для фильтрации писем.
Для методов на основе обнаружения повторов характерны две существенные проблемы[13]. Во-первых, это «персонализация» спама - каждое письмо в рассылке имеет незначительные отличия, за счет чего затрудняется построение устойчивых сигнатур. Для решения этой проблемы используются различные устойчивые сигнатуры, например, реализованный в системе Яндекс.Почта метод шинглов[9, 10]. Вторая проблема - это обнаружение легальных рассылок.
Еще один распространенный метод, применяемый в системах фильтрации почты, использует для обнаружения спама эвристические правила и шаблоны. Основывается на анализе сообщения и поиске в нем специфических признаков, характеризующих письмо как спам. Это могут быть как формальные признаки, типичные для писем со спамом, такие как, например, отсутствие отправителя или получателя письма. Так и семантические, проверяющие наличие в письме определенных фраз, словосочетаний, оборотов, приемов маскировки с помощью языка разметки документов и так далее.
В современной системе, основанной на таких методах, содержится тысячи и десятки тысяч правил и шаблонов. Весовые коэффициенты для них определяются, например, с помощью генетических алгоритмов на тестовой выборке, либо вручную. Обычно письмо со спамом содержит сразу несколько таких признаков и итоговое решение
о принадлежности письма к спаму определяется совокупностью их весовых коэффициентов.
Базы знаний для таких систем создаются и поддерживаются вручную. Эффективность системы, основанной на таких методах, ключевым образом зависит от регулярности обновлений экспертной базы знаний и ее качества. Очевидно, что большинство семантических правил зависят от естественного языка, таким образом, система может быть ориентированна только на какой-либо локальный рынок и плохо работать в мультиязыковой среде.
Рассмотрим достоинства и недостатки традиционных методов. Все методы основываются на той концепции, что данные, на основании которых производится анализ, готовятся в большинстве случаев сторонними поставщиками и являются одинаковыми для всех пользователей.
Традиционные методы, как правило, не персонифицированы, т.е. не учитывают особенности переписки конкретного пользователя. Декларируется, что понятие спама является одинаковым для всех пользователей, что в корне неверно. То, что для одного пользователя является спамом, вполне может быть важной содержательной информацией для другого. Отсутствие персопализации понижает уровень обнаружения и влечет рост количества ложных срабатываний.
При использовании традиционных методов возникает прямая зависимость от поставщиков обновлений баз знаний, на основании которых осуществляется фильтрация. Необходимо постоянно поддерживать базы знаний в актуальном состоянии. От регулярности обновлений напрямую зависит качество работы такой системы. Система привязана и зависима от оперативности конкретного сервиса - провайдера обновлений.
3. Актуальным для традиционных методов является вопрос безопасности.
Принципиальный момент в том, что решение о том, что есть спам, а что есть легальная
почта, принимается третьей стороной. Это порождает несколько проблем безопасности.
Третья сторона управляет тем, какую почту получает пользователь. Кроме того, от
провайдера зависит и качество фильтрации почты. Для многих организаций такой подход
к безопасности является недопустимым.
4. Большинство систем, основанных на традиционных методах - национальные.
Правила и шаблоны зависят от естественного языка, для которого они созданы.
Сигнатуры создаются провайдерами обновлений для определенного рынка.
Таким образом, традиционные методы обладают следующими недостатками:
необходимость регулярных обновлений базы знаний (для поддержания ее актуального состояния);
зависимость от поставщиков обновлений;
низкий уровень безопасности (благодаря зависимости от сторонних поставщиков);
«неперсонифицированная» модель классификации (не учитывает индивидуальные особенности переписки пользователя);
зависимость от естественного языка переписки;
относительно невысокий уровень обнаружения (как минимум, благодаря общей модели классификации).
Активно развивающимся в настоящее время направлением фильтрации электронной почты является разработка и использование обучаемых, или так называемых интеллектуальных методов, использующих алгоритмы интеллектуального анализа данных (Data Mining). Такие алгоритмы разделяют объекты на несколько категорий, используя для классификации модель, построенную заранее на базе прецедентной информации [14, 65].
Таким образом, для того чтобы такая система фильтрации спама работала, первоначально ее необходимо обучить на множестве писем, для которых заранее известна их принадлежность к спаму или к нормальной переписке. Пользователь заранее подготавливает набор писем, который он вручную классифицирует как спам либо как легальную почту. Затем с помощью математических методов производится анализ этого набора и строится модель, которая в дальнейшем используется для классификации новой почты. Модель строится на анализе выделенных характеристик письма. В качестве таких характеристик могут служить, например, слова (лексемы), входящие во все письма. Далее, в результате такого анализа метод выделяет характерные для данного класса писем признаки.
(Х|,у|=спам)
(Хі.Уі)
(х,?)
. / Алгоритм \,_лу v 'классификации
{хі.Уі} - тренировочный набор
Хі = {легальные письма, примеры спама}
Уі = {спам, легальные}
і = 1..п
Модель
Рисунок 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.
Рисунок 3 Система фильтрации MailShell. (с) MailShell Inc.
Фильтр содержит несколько компонентов, осуществляющих фильтрацию следующим принципам. Использование устойчивых шаблонов писем со спамом. Использование метода обнаружения повторов с поддержкой голосования пользователями. Использование черных списков (IP-адресов и e-mail адресов) распространителей спама. Использование шаблонов и сигнатур для анализа содержимого писем и специфичных признаков спам-рассылок. В данном решении также применяется баесовский статистический анализ для построения нечетких сигнатур писем со спамом, анализа содержимого писем (Рисунок 3).
Для серверных систем, основанных на данном решении, персонализация отсутствует.
SpamAssassin
SpamAssassin, наиболее популярный фильтр спама с открытыми исходными текстами[18]. Применяется как отдельно, так и в составе большого числа, в том числе коммерческих продуктов.
Фильтр использует несколько разнообразных методик обнаружения, перечисленных выше. Основной блок фильтра использует наборы эвристических правил для анализа текста и заголовков письма. Регулярная поддержка базы знаний правил отсутствует.
Также имеются расширения, использующие дополнительно такие техники как черные списки IP-адресов отправителей спама (RBL), распределенные системы обнаружения рассылок с помощью голосования пользователей.
На момент начала данной работы SpamAssassin поддерживал обучаемый алгоритм классификации на основе метода Байеса (Na'ive-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-ми научных публикациях.
Диссертационная работа состоит из введения, четырех глав, заключения и библиографии. Далее излагается краткое содержание работы.
Во введении рассматривается постановка проблемы, ставятся цели работы, обосновываются актуальность, новизна и практическая значимость их решения.
В первой главе задача фильтрации электронной почты рассматривается с точки зрения классической задачи классификации. Приводится обзор методов классификации на основе алгоритмов машинного обучения и методики их оценки. Рассматриваются методы
представления объектов для задачи классификации, связанные с ними проблемы и подходы к их решению. Далее анализируются проблемы, возникающие при использовании методов классификации на основе алгоритмов машинного обучения для задачи классификации электронной почты, и выдвигаются предположения об их эффективном решении. В конце главы анализируется общая архитектура серверной системы классификации, формулируются концепции организации серверных систем фильтрации спама, использующих обучаемые методы классификации.
Во второй главе предлагается новый подход к решению задачи фильтрации электронной почты на уровне почтового сервера, основанный на использовании персонифицированной модели классификации. Рассматривается модифицированный обучаемый алгоритм на основе метода опорных векторов. В данной главе также исследуются вопросы увеличения качества и скорости обучения и классификации для предложенного обучаемого алгоритма.
В третьей главе приводится детальное описание архитектуры предлагаемой системы фильтрации электронной почты, а также ее программная реализация. Описываются возможные конфигурации и схемы интеграции представленной системы фильтрации электронной почты с известными и наиболее распространенными почтовыми серверами.
Четвертая глава посвящена экспериментальной верификации разработанной системы фильтрации спама серверного уровня. Здесь рассматриваются применяемые методики тестирования алгоритмов классификации и систем фильтрации электронной почты. Приводится описание и результаты сравнительных экспериментов предлагаемой системы с наиболее распространенными коммерческими и свободно распространяемыми системами фильтрации электронной почты.
В заключении приводится описание полученных результатов.
Модели представления объектов для задачи классификации
Набор признаков, характеризующих объект, в полной мере определяется типом и сущностью объекта. Например, если, как в нашем в случае, объект представляет собой электронное письмо, признаки можно разделить на текстовые и нетекстовые. Нетекстовые признаки определяются эмпирически на основании экспертных оценок[77]. Их количество невелико и фиксировано. В частности, возможные нетекстовые признаки это: - наличие, тип, размер прикрепленных файлов; - кодировка, использование форматирования; - различная информация из заголовка письма (об отправителе, получателях письма, почтовых серверах); - статистические данные о текстовой части письма (размер, среднее количество слов, знаки препинания, использование регистра).
Текстовую часть письма можно рассматривать как обычный текстовый документ. Существует несколько различных по сложности методов выделения признаков текстовых документов. Наиболее распространенный подход в качестве признаков документа предлагает использовать все слова, входящие в документ. Обычно используются некоторые меры по уменьшению размерности пространства таким образом выделенных признаков, которые будут далее рассмотрены в этой главе в соответствующем пункте.
Применяются также более сложные модели выделения признаков текстовых документов. Такие модели учитывают взаимное расположение слов в документе, используют многословные характеристики. Существуют различные методики формирования многословных характеристик. В качестве примера можно привести выделение всех пар или всех троек слов, стоящих в тексте рядом. Несомненно, такие модели предоставляют больше информации о структуре и составе документа, нежели модель «bag of words», в которой теряются семантические связи между словами. Но в то же время значительно возрастает пространство признаков и соответственно растут расходы на их хранение и обработку. Различные эксперименты показывают, что использование более сложных моделей вьщеления признаков текстовых документов не приводят к значительному повышению эффективности модели [25].
Методы определения весовых коэффициентов признаков основываются на двух
очевидных утверждениях: во-первых, чем чаще признак встречается в объекте, тем он более значимый (релевантный) для той категории, которой принадлежит объект, и во-вторых чем чаще признак встречается во всех объектах набора, тем меньше информации он несет об отличии различных объектов набора. Наиболее простая бинарная модель определения весовых коэффициентов: Wy = 1, если соответствующий признак присутствует в данном объекте и Wy = О в противном случае. Большинство же моделей используют более сложные методы, учитывающие «вес» признаков в объекте.
Рассмотрим несколько подходов определения веса признаков на примере объектов - текстовых документов. Как было рассмотрено ранее, одним из возможных определений набора признаков для текстовых документов является набор всех слов, входящих во все документы обучающего набора. Наиболее распространенный метод определения веса слова основан на статистических характеристиках его появления в тексте документа и всех документах обучающего набора: - Wy = fу - количество вхождений слова в документ. Недостаток этого метода определения веса - признаки более длинных документов будут получать больший вес. W, »= /» = Л dj - частота вхождения слова в документ. Где d. - количество слов в документе. Здесь, наоборот, признаки слов тех документов, в которые входит большое количество признаков, будут получать меньший вес. - Wy = 1 + \og(tfy ). По сравнению с предыдущей, эта формула более устойчива к переоценке документов, где данное слово встречается слишком часто. - wij У x idJij Jij 18 , где N - общее количество документов в наборе, \Пі ) nt - количество документов в наборе, в которые хотя бы раз входит данное слово.
В отличие от предыдущих, этот метод определения веса учитывает также частоту появления слова во всей коллекции документов. Wij=tfCij tfxidfij дЛ -i2 . Этот метод, в отличие от предыдущих, \nkJ Л/-log учитывает различную длину документов, используя нормализацию.
Существуют различные модификации представленных методов, хотя, скорее всего наиболее распространенным является последний из рассмотренных. Веса, вычисленные по любому из данных методов, монотонно возрастают с ростом числа вхождений соответствующего признака в документ.
Как правило, выполняют нормировку весовых коэффициентов так, чтобы О W- 1 . Таким образом любой объект dj Є І . Достаточно часто используется например такая норма: W- = v W;1 ZlliW Оценке и сравнению алгоритмов классификации, в том числе и для задачи классификации текстовых документов, посвящен ряд публикаций [14, 25, 65, 79]. Задача фильтрации электронной почты на серверном уровне накладывает определенные ограничения на алгоритмы классификации. Здесь будет рассмотрено несколько алгоритмов, которые либо применяются в настоящее время для решения этой задачи, либо имеют наибольшие шансы быть применимым.
Экспериментальное обоснование метода сокращения пространства признаков
Была проведена серия экспериментов, в которых использовались представленные методы с различными параметрами. В качестве тренировочного и тестового набора документов использовался общедоступный архив электронных писем, предлагаемый разработчиками фильтра почты SpamAssassin[18]. Весь набор писем был разбит на несколько частей, каждая из которых последовательно использовалась в качестве тестовой, а все оставшиеся - в качестве обучающих. Затем результаты экспериментов для каждой из частей объединялись. К обучающему набору применялись исследуемые методы уменьшения пространства признаков с различными параметрами, затем для каждого эксперимента использовался один и тот же алгоритм классификации -модифицированный метод опорных векторов. Для сравнения результатов различных экспериментов применялась стандартная процедура оценки алгоритмов, имеющих ошибки первого и второго рода с использованием ROC-кривых.
На Рисунок 13 самый верхний график - результат работы метода опорных векторов на всем наборе признаков, без удаления. Его можно рассматривать как эталонный. Два других графика представляют два метода сокращения признаков, для которых была выбрана одинаковая граница количества отобранных признаков.
Самый нижний график - выбор признаков с помощью метода оценки информационной значимости. Как видно, результаты классификации значительно ухудшились. Второй график - результат предлагаемого решения. Как видно, результаты классификации отличаются незначительно от результатов с использованием всего пространства признаков. Таким образом, удалось сократить пространство признаков на два порядка, практически не ухудшив качество классификации.
Основная проблема при разработке статистических методов классификации -большая размерность пространства признаков. Существующие методы сокращения количества признаков плохо подходят для задачи классификации электронной почты. Методы выбора оптимальных признаков недостаточно точны при значительном сокращении количества признаков, а методы репараметризации обладают слишком высокой вычислительной сложностью и при размерности пространства признаков в несколько тысяч элементов практически неприменимы. Для решения этой проблемы был предложен комбинированный подход, суть которого заключается в суперпозиции двух методов. Сначала набор признаков сокращается одним из методов выбора пространства признаков. Затем к существенно уменьшенному набору применяется алгоритм репараметризации. Такой подход позволил сократить пространство признаков на два порядка при этом практически не ухудшив точность классификации.
В качестве алгоритма классификации в системе фильтрации почты используется модифицированный метод опорных векторов, в общем виде рассмотренный в главе 1. Данный метод с помощью потенциальной функции К отображает объекты исходного множества X в векторное пространство характеристик Н существенно большей размерности. Отображение (р . X — Н в явном виде не используется, а потенциальная функция определяет скалярное произведение в пространстве Н: К(х, у) = \ р[х), (р\у))и.
В пространстве характеристик строится гиперплоскость таким образом, чтобы граница между объектами различных категорий была максимальна, а ошибки классификации минимальны.
Потенциальная функция или kernel-функция или ядро - это мера схожести объектов в пространстве характеристик. Фактически, она вычисляет скалярное произведение в некотором пространстве характеристик Н, отличном от исходного пространства X, в котором определены объекты. Вычислительный трюк, благодаря которому метод опорных векторов показывает столь впечатляющие результаты, заключается в том, что вместо вычисления отображения (р в явном виде скалярное произведение подменяется kernel-функцией К(х,у) = ( р\Х),(р[у))и , которая неявно и осуществляет отображение.
«Черные»/«белые» списки адресов отправителей
Пользователь имеет возможность сформировать свой персональный «черный»/«белый» список e-mail адресов отправителей почты. В реальности, практическую пользу имеет только «белый» список адресов. Письма от отправителей, которые присутствуют в этом списке, считаются легальными вне зависимости от результата классификации, и соответственно всегда попадают в папку Inbox. Эта функция позволяет, например, исключить возможность ложно-положительных ошибок для писем наиболее важных адресатов.
Управление списками адресов осуществляется с помощью web-интерфейса. Имеется возможность добавлять и удалять одиночные адреса, текстовые файлы со списками адресов, а также адресные книги в формате Windows Address Book (wab).
Существует такая проблема, что классификация с использованием «черных»/«белых» списков может влиять на корректность тренировочного набора. Например, пользователь может включить в «белый» список адрес какой-либо коммерческой рассылки, письма которой очень похожи по содержанию на рекламные объявления и в нормальной ситуации были бы отнесены к спаму. Таким образом, такие письма будут находиться в папке Inbox вместе с легальной почтой и затем будут использоваться в качестве примеров легальной почты при обучении. Так как такие письма по содержанию относятся скорее к спаму, это будет отрицательно влиять на качество построенной модели и, следовательно, на качество классификации новой почты.
Для корректного построения модели классификации в системе фильтрации создана опция, с помощью которой пользователь может влиять на стратегию формирования тренировочного набора. При классификации каждого письма в его заголовок помимо оценки, проставленной фильтром, добавляется признак, находится ли автор письма в одном из списков пользователя. Во время обучения те письма, которые были классифицированы с помощью «черных»/«белых» списков, исключаются из тренировочного набора.
В системе хранится и доступна для просмотра история всех обучений и дообучений пользователя и их характеристики, такие как количество писем в тренировочном наборе, временные характеристики обучения, значения пользовательских параметров, используемых при обучении. Также во время обучения отображается текущий статус операции и динамика процесса.
В настоящее время серверная система фильтрации электронной почты интегрирована и опробована со следующими почтовыми серверами: Sendmail 8.12, Exim 4.34, CommuniGate Pro 4.2, Microsoft Exchange 2000.
Для функционирования системы дополнительно используются следующее программное обеспечение: СУБД mySQL 3.23, Web-сервер Apache 2.0.
Предлагаемая концепция архитектуры системы фильтрации почты, в основе которой лежит мультиагентный подход, обеспечивает решение двух задач. Во-первых, это достижение высокой степени параллелизма и масштабирования, и, во-вторых, гибкость при интеграции с различными почтовыми серверами при классификации и источниками данных при обучении. Для того, чтобы минимизировать изменения во всей системе фильтрации, специфичные для конкретного почтового сервера интерфейсы, используемые при классификации и специфичные интерфейсы источника данных вынесены в два соответствующих агента: классифицирующий и обучающий.
Обучающий агент может быть реализован для различных хранилищ писем, например, на основе протокола ІМАР на централизованном сервере или как персональный агент, использующий для обучения письма из персональных папок пользователя, откачанных по РОРЗ и хранящихся на рабочей станции пользователя. В экспериментальной системе для решения этой задачи был использован и реализован подход, при котором обучающий агент загружает письма пользователя автоматически из соответствующей папки на почтовом сервере про протоколу ШАР. Такой подход применим только для пользователей, которые для чтения почты пользуются протоколом ІМАР либо web-интерфейсом. Это является некоторым ограничением, но только для обучающего агента такого типа.
При интеграции с новым почтовым сервером все изменения будут инкапсулированы внутри классифицирующего агента. Он служит интерфейсом между системой фильтрации почты и почтовым сервером, так как специфика механизма передачи писем для классификации и дальнейшие действия в зависимости от результатов классификации учитываются только на уровне классифицирующего агента. Практически любой почтовый сервер имеет какой-либо определенный интерфейс для обеспечения проверки писем сторонним фильтром. Это интерфейс в том числе можно использовать и для фильтрации спама.
Сравнение Naive Bayes (Лаборатория Касперского)
Для Kaspersky Anti-Spam все настройки были сохранены такими, какие они стоят по умолчанию. Был выбран предустановленный общий профиль Spam Detection Standard (no RBL & DNS check). Выбранные персональные профили: root: No Filtering и Marking Spam - Subject.
Списки e-mail адресов, ір-адресов, dns blacklists - пусты. Пользовательские примеры писем со спамом отсутствуют. Добавлен один пользователь (получатель) -учетная запись KAS. Конфигурация системы: Pentium IV 2800 MHz, RAM 512 Mb, HDD 120 Gb Linux RedHat 9
Для ISD первоначальное обучение проводилось для всех шести почтовых учетных записей. Размеры наборов писем для первоначального обучения - в соответствии с таблицей. Для трех из шести учетных записей проводилось дообучение раз в сутки. Конфигурация системы: Pentium IV 2800 MHz, RAM 512 Mb, HDD 120 Gb Linux RedHat Для оценки качества классификации почтовых сообщений для каждой учетной записи собирались следующие характеристики: - количество легальных писем, ошибочно распознанных как спам (False Positive); - количество писем, содержащих спам, ошибочно распознанных как легальные письма (False Negative).
Дополнительно для Intelligent Spam Detector собирались следующие параметры: - время первоначального обучения; - время дообучения; - размер словаря в базе данных, общего для всех почтовых учетных записей; - размер построенных моделей, используемых при классификации.
Для почтовой учетной записи KAS настроено чтение почты по протоколу ШАР на одной из рабочих станций. Раз в сутки проводился ручной визуальный контроль легальных писем, затем автоматизировано собиралась информация о количестве неклассифицированных писем со спамом.
Для почтовых учетных записей ISDE 1, ISDE 2,1SDE 3, ISDE 1+, ISDE 2+, ISDE 3+ настроено чтение почты по протоколу ІМАР на одной из рабочих станций. ISD раскладывает письма в соответствии с результатами классификации и установленным пользователем значением границы Message Rate в папки Inbox и Spam. Пользователь может контролировать качество работы фильтра используя для чтения почты протокол ІМАР.
Раз в сутки проводился ручной визуальный контроль писем в папках Inbox и Spam.
Далее, если это было необходимо, те письма, которые были ошибочно классифицированы, перемещались в соответствующие папки. Для трех учетных записей ISDE 1+, ISDE 2+, ISDE 3+, поводилось дообучение.
Для трех других учетных записей, ISDE 1, ISDE 2, ISDE 3, дообучение не проводилось на протяжении всего эксперимента.
Для ISD собирались дополнительные параметры, не относящиеся к качеству классификации. Они характеризуют временные и затраты и на процесс обучения и дообучения системы, а также затраты по памяти.
Алгоритм фильтра почтовых сообщений ISD по результатам классификации приписывает письму некоторую числовую характеристику, отражающую его степень принадлежности к тому или иному классу (спам или легальное сообщение). Использование этого параметра позволяет регулировать то, каким письмам при классификации отдается предпочтение.
В ходе эксперимента для каждой из почтовых учетных записей было выбрано два различных оптимальных порога. Один из них минимизирует коэффициент ложных положительных ошибок, при этом ухудшается коэффициент обнаружения. Другой оптимальный порог максимизирует коэффициент обнаружения, ухудшая коэффициент ложных положительных ошибок. Обобщенные результаты приведены в Таблица 19.
Для оценки производительности предложенных решений была проведена серия экспериментов. Стояла задача получить данные о производительности, во-первых, для алгоритма классификации в отдельности и, во-вторых, для всей экспериментальной системы фильтрации почты в комплексе и в реальном окружении.
Оценка производительности алгоритма классификации проводилась на эталонном тестовом наборе писем SpamAssassin по той же методологии, что и большинство рассмотренных выше тестов, оценивающих качество классификации. То есть набор был разбит на несколько частей, затем было проведено несколько перекрестных экспериментов, в каждом из которых один набор выступал в качестве тестирующего, а остальные - обучающих. Результаты отдельных экспериментов были объединены и усреднены.
Тест на производительность осуществлялся с использованием следующего оборудования: Pentium IV 2800 MHz, RAM 512 Mb, 1 IDE HDD 120 Gb. Операционная система: RedHat Linux 9.0. Всего в тестовый набор содержит порядка 3000 писем, его общий размер около 14 мегабайт, средний размер одного письма около 4,7 килобайт.
