Содержание к диссертации
Введение
Глава 1. Алгоритмы фильтрации почтовых сообщений 8
1.1 Электронная почта и нежелательные рассылки 8
1.2 Характеристики спама 9
1.3 Классификация спам-сообщений 10
1.4 Спам без вложений 11
1.5 Спам со вложением 13
1.6 Анализ уязвимости различных учетных записей электронной почты. 19
1.7 Массовые методы рассылки 22
1.8 Ущерб, наносимый спамом 23
1.9 Контрмеры 27
1.10 Вывод., 31
Глава 2. Смешанный алгоритм фильтрации основанный на методе опорных векторов и нейронной сети 32
2.1 Метод опорных векторов 32
2.3 Обработка обучающего множества 41
2.4 Алгоритм таксономии FOREL 42
2.5 Результаты обработки обучающего набора 46
2.6 Вывод 51
Глава 3. Спам-фильтр на основе двухслойного персептрона 52
3.1 Формальные нейроны и персептрон на их основе 52
3.2 Формирование двухслойного персептрона 58
3.3 Результаты тестирования 62
3.4 Вывод 65
Глава 4. Спам-фильтр на основе персептрона Розенблатта и саморганизующихся карт Кохонена 66
4.1 Персептрон Розенблата 66
4.2 Самоорганизующиеся карты Кохонена 70
4.3 Результаты тестирования 75
4.4 Сравнительное тестирование 78
4.5 Вывод 82
Заключение 83
Основные публикации по теме диссертации 85
Библиографический список 87
- Классификация спам-сообщений
- Обработка обучающего множества
- Формирование двухслойного персептрона
- Самоорганизующиеся карты Кохонена
Введение к работе
Актуальность работы.
Одним из направлений исследований в области защиты информации является разработка методов и алгоритмов фильтрации потока электронной почты. В последнее время электронная почта стала одним из наиболее распространенных средств связи, управления и бизнеса. Она является достаточно совершенной в техническом отношении и недорогой альтернативой привычным средствам связи.
Вместе с развитием электронной почты увеличивается и количество угроз ее нормальному функционированию. Наиболее серьезной и важной проблемой стал так называемый спам, то есть нежелательные массовые рассылки сообщений, в основном рекламного характера. По сообщениям экспертов «Лаборатории Касперского», в 2010 году доля спама превысила 83% общего количества пересылаемых писем.
На сегодняшний день разработан ряд технологий построения фильтров -сервисов для отсеивания нежелательной корреспонденции. Все технологии можно разделить на настраиваемые вручную и интеллектуальные. Настраиваемые вручную фильтры основываются на списках доступа и настраиваются непосредственно пользователем, который выбирает либо нежелательные адреса, при политике пропуска по «черному списку», либо разрешенные адреса, при политике пропуска по «белому списку». Однако ручные способы фильтрации нежелательных сообщений малоэффективны и требуют постоянного обновления списков доступа, создавая дополнительную нагрузку на пользователя.
Фильтры, построенные с использованием технологий искусственного интеллекта, требуют обучения только на начальном этапе, дообучаясь в дальнейшем самостоятельно, существенно снижая нагрузку на пользователя. Самым распространенным на сегодняшний день является фильтр, основанный на наивном байесовском подходе, в котором предполагается, что различные термы сообщения независимы друг от друга. Максимальный результат, достигнутый байесовскими фильтрами на сегодняшний день составляет порядка 95% отфильтрованного спама. Для повышения эффективности байесовского фильтра необходимо учитывать семантические связи между термами, что требует привлечения методов семантического анализа и существенно повышает нагрузку на систему и увеличивает время работы самого фильтра, при незначительном повышении эффективности фильтрации.
Другим подходом, получающим в последнее время все большее распространение, является использование нейросетей. Преимущество нейросетевого подхода перед наивным байесовским состоит в том, что не делается никаких предварительных предположений о характере нежелательных
сообщений, а семантические связи учитываются автоматически. Наибольшее количество разработок связано с построением фильтра на основе многослойного персептрона. Однако такой подход встречается с рядом трудностей, связанных с выбором пороговых значений, которые задаются произвольно в некотором интервале. Эффективность фильтра существенно зависит от выбора порогового значения. При этом пороговое значение требует постоянной подстройки под изменяющийся характер нежелательных сообщений. Также малоисследованным остается вопрос использования других нейросетей, хорошо зарекомендовавших себя в задачах распознавания образов, частным случаем которых является фильтрация спама.
Таким образом, развитие нейросетевого подхода применительно к фильтрации нежелательных сообщений является актуальной задачей.
Целью диссертационной работы является повышение эффективности фильтрации нежелательных сообщений в потоке электронной почты с использованием интеллектуальных систем.
Для достижения поставленной цели были решены следующие задачи:
1. Разработка смешанного алгоритма фильтрации на основе совмещения
метода опорных векторов и нейросетевого подхода.
-
Реализация и апробация смешанного спам-фильтра на основе двухслойного персептрона.
-
Реализация и апробация смешанного спам-фильтра на основе персептрона Розенблатта.
-
Реализация и апробация смешанного спам-фильтра на основе самоорганизующихся карт Кохонена.
Методы исследования. В диссертационной работе использованы методы построения нейронных сетей, алгоритмы кластеризации и методы системного анализа.
Научная новизна результатов исследования.
1. Впервые совместно использованы метод опорных векторов и нейросети
для построения спам-фильтра.
-
Впервые для фильтрации писем использованы совместно алгоритм таксономии и двухслойный персептрон.
-
Впервые для фильтрации писем использованы совместно алгоритм таксономии и персептрон Розенблатта.
-
Впервые для фильтрации писем использованы совместно алгоритм таксономии и самоорганизующиеся карты Кохонена.
Достоверность результатов работы. Научные результаты диссертационной работы получены с использованием методов хорошо зарекомендовавших себя для построения спам-фильтров. Проведено сравнение
результатов работы предлагаемого алгоритма с существующими программными решениями проблемы массовых рассылок.
Практическая значимость работы заключается в возможности разработки прикладных систем индивидуальной защиты от нежелательной корреспонденции для персональных компьютеров.
Основные положения, выносимые на защиту.
1. Алгоритм фильтрации спам-сообщений на основе совместного
использования алгоритма и нейросетевого подхода.
-
Система фильтрации спам-сообщений на основе алгоритма таксономии FOREL и двухслойного персептрона.
-
Система фильтрации спам-сообщений на основе алгоритма таксономии FOREL и персептрона Розенблатта.
-
Система фильтрации спам-сообщений на основе алгоритма таксономии FOREL и самоорганизующихся карт Кохонена.
Апробация работы. Основные положения диссертационной работы представлялись и обсуждались на следующих конференциях: «Актуальные проблемы безопасности информационных технологий». (Красноярск, 2009, 2010), «Информационные технологии и автоматизация управления» (Омск, 2009,2010), а так же внедрена в деятельность трех организаций.
Публикации. Результаты диссертационной работы были представлены в 9 публикациях: в 6 научных статьях, в том числе 3 статьи в журналах из списка периодических изданий, рекомендованных ВАК.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка и изложена на 96 страницах машинописного текста. Библиографический список литературы состоит из 100 наименований.
Классификация спам-сообщений
Из всего спама, что был получен, более 50% попадает под категорию спама со вложением. Этот вид спама содержит комбинацию изображений, текста и URL или гиперссылку на веб-сайт. В основном вложенные файлы это изображения (как правило, формата GIF, реже JPG) и исполняемые файлы (ЕХЕ). Размер спам-сообщений данной категории колеблется от 5 кб до 45 кб. Спам с исполняемыми файлами во вложении часто содержит вирусы или червей [69]. Спам со вложением можно разделить на четыре основные категории. Первая категория - спам-письма, содержащие файлы с изображениями (GIF) и текст, вторая - спам-письма, содержащие изображение, текст и URL, третья категория - письма, содержащие только изображения с гиперссылкой и четвертая категория спама со вложением -письма, содержащие червей, вирусы, троянские программы. Размер таких сообщений колеблется от 13 кб до 45 кб. В таблице 2 показано распределение спама с вложением в течение 7 дней.
Рисунок 4 показывает количество спама с файлами изображениями во вложении и текстом, с файлами изображениями во вложении и гиперссылками или URL, с файлами изображениями во вложении, текстом и URL, а так же количество спама других категорий, поступившего за неделю. Под спамом других категорий подразумеваются ложные срабатывания и массовые рассылки, на которые пользователь самостоятельно когда-то подписался. Оси X - день, оси Y - количество поступившего спама. Спама, содержащего файл изображения и текст, поступило от 17 до 2005, в среднем - 943 за день. Спам-сообщений, содержащих изображения и гиперссылки или URL, - от 0 до 545, в среднем - 137. Спама, содержащего файл изображения, текст и URL, колеблется от 81 до 911, в среднем - 290 в день. Спама других категорий - колеблется от 33 до 1093, в среднем - 303. Наибольшее количество поступившего спама, это сообщения, содержащие файл изображения и текстом. Каждое спам-сообщение рассылалось на разные почтовые адреса с уникальных IP. В основном, спам приходил от поддельных IP -адресов с поддельными учетными записями электронной почты при помощи реле [59,76]. Сообщения новостного характера и реклама телекоммуникационных услуг, бытовой техники также многими пользователями считаются спамом. От подобного вида спам-сообщений легко отписаться, и они незначительны в общем проценте спама.
Спам, содержащий текст, изображения, URL. Текст не связан с темой сообщения. Изображение содержит URL, который непосредственно связан с темой. Размер подобных писем колеблется от 10 кб до 30 кб. Значительная часть спама этого вида связана с фишинг атаками.
Спам, содержащий изображение и текст. Изображение содержит текст и URL какой-либо темы. Этот вид спама, как правило, не содержит активных ссылок. Содержание изображения имеет отношение к теме. Текст сообщения выбирается случайным образом и не связан с темой. Размер текстового сообщения варьируется. Изменяя содержание текста и его размер, спамеры пытаются обойти фильтры. В этой категории большинство спама связано с медициной и финансами. Исследование показало, что в этой категории более чем 50% спама связано с финансами. Размер, цвет, содержание изображений одинаковы для определенного периода времени.
Спам, содержащий изображения и URL или гиперссылки. Так как URL или гиперссылка находится внутри изображения, спам легко обходит контент фильтры.
Четвертая категория спама содержит ЕХЕ-файлы. Спам с ЕХЕ-файлами в качестве вложения в основном содержит вирусы, червей, trojan-программы и так далее. Размер сообщений в диапазоне от 35 кб до 140 кб. Цель таких сообщений - распространение вирусов, а также попытка установить почте бомбы для DDoS атак на сервер и сеть. При запуске файла из вложения он создает новые файлы в системных папках, изменяет файл реестра, ссылаясь на сайт злоумышленника для загрузки больших программ. Инфицированные машины собирают адреса электронной почты из адресной книги и автоматически рассылают письма на другие в этом же домене [69].
DDoS-атаки через спам-сообщения являются одним из новейших видов атак DDoS. Атакующий проникает в сеть через небольшую программу, прикрепленную к спам-сообщению. После запуска прикрепленного файла ресурсы почтового сервера полностью расходуются из-за массы писем от других машин в домене, что приводит к отказу от предоставления услуг. Спам содержит небольшого размера ЕХЕ файл (например, update.exe). Размер сообщений - от 35 кб до 180 кб. Названия червей, используемых в такого рода DDoS-атаках: WORM_start.Bt, WORM_STPvAT.BG, WOPvM_STRAT.BR, TROJ_PDROPPER.Q. Однако выполнив свою работу, эти черви запускают файлы serv.exe, serv.dll, serv.s, serv.wax, El.dll, rasaw32t.dll и так далее [85]. Массовые почтовые и сетевые черви причиняют косвенный ущерб, они используют всю пропускную способность сети и её ресурсов, в результате чего медленно доставляется почта и далее происходит отказ в обслуживании. Работа сервера замедляется из-за огромного количества просьб со стороны клиентов.
Распределение спама с вирусами, червями и trojan-программами пришедшего в течение семи недель и первых семи дней. Недели Сообщения с вирусами,червями и trojan-программами Дни Сообщения с вирусами,червями и trojan-программами Рисунок 5 показывает количество спама, содержащего вирусы, червей и trojan-программы, пришедшего в течение семи недель. Оси X - недели, ось Y - количество спама. Спама этого вида было получено от 1245 до 2847 в среднем -1957 за неделю. Кроме того, был проведен анализ этого спама в течение недели. Рисунок 6 показывает количество спама с вирусами, червями и trojan-программами, который поступил в течение семи дней. Такого спама поступило от 253 до 496 в среднем - 407. Оси X - день, Y -количество спама. Не существует никакой связи между спамом с вирусами и легитимной почтой.
Обработка обучающего множества
Метод опорных векторов (SMV) на сегодняшний день считается одним из самых перспективных алгоритмов искусственного интеллекта при решении задач кластеризации [58,64]. Рассмотрим основные положения данного подхода необходимые в дальнейшем.
Основная идея метода опорных векторов состоит в поиске N-гиперплоскости, осуществляющей деление пространства на два подпространства, каждое из которых содержит точки только из одного кластера. Построение производится в пространстве признаков элементов, каждый из которых играет роль координаты. Каждому элементу кластеризуемого множества сопоставляется точка в пространстве признаков. При необходимости выделения нескольких кластеров строится множество гиперплоскостей. Классификация элементов производится по принадлежности одному из подпространств.
Как показано в работе [58] метод SVM может быть реализован с помощью двухслойного персептрона с сигмовидной функцией отклика. Не смотря на то, что SMV близок классическому двухслойному персептрону он обладает дополнительными возможностями при обучении нейронных сетей с полиномиальными и радиальными базисными функциями [74]. Как легко понять, метод опорных векторов осуществляет обучение с учителем [74,98].
Определим ряд понятий, используемых в методе опорных векторов. Предикат переменной будем называть атрибутом, а трансформатор атрибута, который используется для определения гиперплоскости функцией. Задача выбора наиболее подходящего представления принято называть выбором функции. Набор функций, которые описаны в одном случае (то есть, ряд значений предиктора), называется вектором. Таким образом, цель SVM в том, чтобы найти оптимальную гиперплоскость, отделяющую кластеры вектора таким образом, что случаи с одной категорией целевой переменной находятся на одной стороне плоскости и случаи с другой категорией находятся на другой. Вектора, проходящие возле гиперплоскости, называются опорными векторами. На рисунке ниже представлен обзор процесса SVM.
Прежде чем перейти к рассмотрению N-мерных гиперплоскостей, нужно рассмотреть простой двумерный пример. Предположим, необходимо выполнять классификацию, и наши данные определяются переменной с двумя координатами. Также предположим, что есть два предиката с непрерывными значениями. Если мы наносим данные (точки) с использованием значения одного предсказателя по оси X, а другого - по оси Y, в конечном итоге мы получим изображение, показанное на рисунке 12. Одна категория данных, которые необходимо классифицировать представлена прямоугольниками, а другая категория представлена овалами.
В этом идеализированном примере с одной категорией в левом нижнем углу рисунка и другой - в правом верхнем углу, данные полностью разделены. SVM необходимо найти одномерную гиперплоскость (т.е. линию), которая разделит данные на две категории. Существует бесконечное число возможных линий, которые можно провести. Вопрос в том, какая линия лучше, и как определить оптимальную.
Пунктирные линии отмечают расстояние между разделяющей линией и ближайшими точками. Расстояние между пунктирными линиями называется маржа. Точки (вектора), которые ограничивают ширину маржи, называются опорными векторами [72] (support vectors). Рисунок 12 иллюстрирует это.
SVM находит линию (или, в общем, гиперплоскости), которая ориентирована так, что разница между опорными векторами была максимальной. На рисунке выше (рис. 12), линия в правой его части превосходит линию в левой панели.
Как видно из примера задача классификации методом опорных векторов легко решается в двумерном пространстве. Однако классификация точек по двум признакам встречается очень редко. В большинстве случаев приходится иметь дело с пространствами большой размерности. Другим случаем, требующим развития SMV является невозможность разделения данных гиперплоскости по причине их относительного положения. Еще одной разновидностью «трудных» задач является мультиклассификация, то есть возможность отнесения каждой точки более чем к одному кластеру [22,65,100]. Как легко понять, размерность разделяющей гиперплоскости на единицу меньше размерности пространства признаков.
Для определения принадлежности точки одному из кластеров строится разрешающая функция, называемая классификатором. Рассмотрим построение классификатора в простейшем случае разделения множества точек на два класса гиперплоскостью.
Пусть есть обучающая выборка (х\,...,у{),...,(хт,...7ут), JC;eRn, ,е{-1,1}. Классификатор F строится в виде функции F(x)=sign«w,x)+b) [91], где (,) -скалярное произведение, w - нормальный вектор к разделяющей гиперплоскости, b - вспомогательный параметр. Точки, для которых значение классификатора F(x) = 1 попадают в один класс, а объекты со значением классификатора F(x) = -1 - в другой класс. Функция-классификатор выбирается в таком виде исходя из того, что любая гиперплоскость определяется уравнением w,x)+b=0 для некоторых w и Ь.
Формирование двухслойного персептрона
Персептрон, состоящий из одного слоя, характеризуется матрицей синаптических связей W (от S- к А-элементам). Каждый из элементов W;J матрицы отвечает за связи между і-м S-элементом и j-м А-элементом. Персептроном описывается функцией [43]: y/J=\ j О,5 л 0, І где w,j — веса персептрона, в — порог, х\ — значения входных сигналов.
При заданных значениях и у- и в, нейрон имеет определенное выходное значение для любого вектора входов. Множество векторов входа, для которых у=1, разделяется гиперплоскостью с векторами, при которых у=0, эта гиперплоскость, в свою очередь, описывается следующим равенством: 2 л-0у=о
Обучение сети состоит в изменении весов связей всех нейронов [81,84]. Пусть есть пары векторов {ха, уа), а = 1,...,р, называемые обучающей выборкой. Будем называть нейронную сеть обученной на данной обучающей выборке, если при подаче на входы сети каждого вектора ха на выходах всякий раз получается соответствующий вектор уа. Алгоритм обучения включает четыре этапа: Этап 0. Инициализация весов нейронов (t=0). Все начальные значения весов Wjj выбираются случайным образом; Этап 1. На вход сети подается образ ха, на выходе получается У фУ \ Этап 2. Производится вычисление вектора ошибки 8" - \уа - уа J, которая получается на выходе. Изменение весовых коэффициентов в области малых ошибок пропорционально ошибке на выходе и равно нулю, если 8" = 0. Этап 3. Модифицируются веса нейронов: W(t + At) = W(t)+rpca (Sa ), 0 г} 1- скорость обучения. Этап 4. -Для всех пар обучающей выборки повторяются этапы 1-3. Обучение заканчивается в одном из двух случаев: 1) вектор весов не меняется; 2) общая ошибка сети становится достаточно малой. Рассмотрим данный алгоритм подробнее. Пусть на вход подается вектор х и известен правильный ответ х , который должен выдать персептрон. Если выходной сигнал у(х)=х , то никаких действий предпринимать не надо. В противном случае (у(х)Фх% произошла ошибка и возникает необходимость обучить персептрон корректно решать данный пример. Существует два типа ошибок. 1. Ошибки первого типа: у(х)=0, а х =1. Для того, чтобы сеть давала правильный ответ, необходимо увеличить сумму в правой части функции у/. Увеличивая веса w t можно добиться этого. Но очевидно, что нет необходимости их увеличивать при переменных Xj=0. Следовательно, необходимо увеличить Wjj при переменных Xj=l. Таким образом, можно сформулировать правило, если у(х)=0, а х =1, следовательно, необходимо увеличить веса связей между одновременно активными нейронами.
2. Ошибка второго типа: у(х)=1, а х =0. Для того чтобы, сеть давала правильный ответ, необходимо уменьшить сумму в правой части функции у/. Следовательно, необходимо уменьшить веса щ при переменных, равных 1 (как и в случае ошибки первого типа Wy при Xj=0, очевидно, их менять не нужно). В результате получаем правило, что если y(x)=l, a x =0, следовательно, необходимо уменьшать веса связей между одновременно активными нейронами.
Таким образом, процедура заключается в последовательном переборе всех примеров из обучающего множества с применением правил обучения к ошибочно решенных примеров. Обучение считается завершенным, когда сеть для любого примера из обучающего множества выдает правильный ответ. Неясными остаются два момента. 1. Насколько нужно увеличивать (уменьшать) веса связей при применении правил обучения? 2. Конечна ли процедура обучения? Ответ на него содержится в теореме о сходимости персептрона и теореме о его «зацикливании».
Теорема о сходимости персептрона [44]. Если существует вектор параметров w, при котором персептрон правильно решает все примеры обучающей выборки, то при обучении персептрона по вышеописанному алгоритму решение будет найдено за конечное число шагов.
Теорема о «зацикливании» персептрона [44]. Если не существует вектора параметров w, при котором персептрон правильно решает все примеры обучающей выборки, то при обучении персептрона по данному правилу через конечное число шагов вектор весов начнет повторяться.
Таким образом, теоремы гласят, что, запустив процедуру обучения персептрона, через некоторое конечное время мы либо получим обучившийся персептрон, либо ответ, что данный персептрон обучиться не может.
Самоорганизующиеся карты Кохонена
Как видно из графиков, количество отфильтрованного спама значительно колеблется в первые 12 дней эксперимента, это позволяет сказать, что происходит процесс дообучения. Таким образом, если учитывать в определении эффективности работы фильтра только период с 4 октября по 17 октября, получим следующие результаты: Фильтра на основе двухслойного персептрона - 89,07% отфильтрованного спама; Фильтра на основе персептрона Розенблатта - 91,79% отфильтрованного спама; Фильтра на основе карт Кохонена - 88,50% отфильтрованного спама.
По результатам проведенного тестирования предлагаемого алгоритма фильтрации потока входящих сообщений можно говорить о том, что в ходе эксперимента были получены результаты, подтверждающие целесообразность его использования. Кроме того, как было написано ранее, мы видим, что на небольших текстах (электронное сообщение, как правило, небольшого размера), весьма эффективным будет использование простейших типов нейронных сетей (однослойный персептрон Резенблатта, двухслойный персептрон), то есть, нет необходимости строить многослойную сеть (например, на основе карт Кохонена).
Исходя из результатов этой главы, можно сделать следующие выводы: 1. В разработанной системе фильтрации на основе совмещения метода опорных векторов и нейро сетевого подхода возможно использование персептрона Розенблатта и нейронной сети на основе карт Кохонена. 2. Система фильтрации спам-сообщений на основе персептрона Розенблатта приводит к ошибкам первого рода в пределах 0%. 3. Система фильтрации спам-сообщений на основе персептрона Розенблатта приводит к ошибкам второго рода в пределах 1.48%. 4. Система фильтрации спам-сообщений на основе карт Кохонена приводит к ошибкам первого рода в пределах 0%. 5. Система фильтрации спам-сообщений на основе карт Кохонена приводит к ошибкам второго рода в пределах 1.11%. 6. Полученная система на основе персептрона Розенблатта и карт Кохонена обладает высокой скоростью обучения и достигает результатов сравнимых с широко распространенными коммерческими системами через 5 дней.
1. Разработан смешанный спам-фильтр на основе совмещения метода опорных векторов и нейросетевого подхода. В методе опорных векторов применен алгоритм таксономии FOREL. Такой подход позволяет одновременно существенно уменьшить как размерность пространства опорных векторов, так и количество входных синапсов нейронной сети. В результате заметно уменьшается время работы фильтра. Основным преимуществом предлагаемого алгоритма фильтрации является его скорость работы, в среднем на обработку одного входящего сообщения затрачивается 1,58 секунды, при сохранении приемлемого уровня ложных срабатываний и качества фильтрации. 2. Реализован смешанный спам-фильтр на основе двухслойного персептрона. Апробация на специально созданной коллекции показала эффективность 80,33%. Испытания на реальном почтовом ящике показали среднюю эффективность 89,07%. Следует также отметить рост эффективности фильтра с течением времени вследствие дообучения.
3. Реализован смешанный спам-фильтр на основе персептрона Розенблатта. Апробация на специально созданной коллекции показала эффективность 80,82%). Испытания на реальном почтовом ящике показали среднюю эффективность 91,79%. Следует также отметить рост эффективности фильтра с течением времени вследствие дообучения.
4. Реализован смешанный спам-фильтр на основе самоорганизующихся карт Кохонена. Апробация на специально созданной коллекции показала эффективность 78,25%. Испытания на реальном почтовом ящике показали среднюю эффективность 88,50%. Следует также отметить рост эффективности фильтра с течением времени вследствие дообучения.
