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

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

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

I

Петровский Михаил Игоревич

ИССЛЕДОВАНИЕ И РАЗРАБОТКА АЛГОРИТМОВ ПОИСКА ИСКЛЮЧЕНИЙ В СИСТЕМАХ ИНТЕЛЛЕКТУАЛЬНОГО АНАЛИЗА

ДАННЫХ

I

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

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

I

I

I

Москва - 2003

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

Научный руководитель: доктор физико-математических наук,

профессор Машечкин Игорь Валерьевич.

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

профессор Крюков Виктор Алексеевич;

кандидат физико-математических наук, кандидат технических наук, доцент Рыжов Александр Павлович.

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

систем РАН

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

С диссертацией можно ознакомиться в библиотеке факультета ВМиК

МГУ.

Автореферат разослан "_" сентября 2003 г.

Ученый секретарь / диссертационного совета

профессор / } Н.П. Трифонов

(Л м-& г**!

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

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

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

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

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

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

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

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

Цель работы

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

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

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

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

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

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

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

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

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

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

Предложенный в работе метод был реализован в виде экспериментальной компоненты анализа данных, поддерживающей промышленный стандарт OLEDB for Data Mining. Это позволяет встраивать компоненту в пользовательские приложения, используя стандартные библиотеки доступа к данным, поддерживающие стандарт OLEDB. На базе этой компоненты была реализована экспериментальная система обнаружения сетевых атак.

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

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

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

По теме диссертации опубликовано 7 печатных работ [1-7]. Результаты диссертации докладывались на объединенном научно-исследовательском семинаре кафедр АСВК, Алгоритмических языков и Системного программирования ВМиК МГУ под руководством проф. Шура-Бура М.Р., а также на семинарах факультетов ВМиК и МехМат МГУ и следующих научных конференциях:

• Международная конференция «Интеллектуальная обработка информации» (Украина, Алушта, 2002).

• Пятый международный симпозиум «Интеллектуальные системы» (Россия, Калуга, 2002).

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

• International Conference on Intelligent Data Engineering and Automated Learning (China, Hong Kong, 2003).

• Atlantic Web Intelligence Conference (Spain, Madrid, 2003).

• International Workshop Innovative Internet Community Systems (Germany, Leipzig, 2003).

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

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

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

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

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

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

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

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

исключения. Он основан на вычислении расстояния между объектами в базе данных и использует следующее определение исключения [Е.Кпогг & R. Ng, 1997]: «Объект о считается исключением, если как минимум р-ая часть всех объектов в базе данных находятся на расстоянии большем D от данного объекта о». В рамках данного подхода рассматриваются глобальные метрические алгоритмы, ищущие в базе данных объекты, удовлетворяющие данному определению, а также локальные метрические алгоритмы, основанные на вычислении степени исключительности LOF (local outlier factor).

Методы, не использующие ни вероятностную ни геометрическую интерпретацию понятия исключения, объединены в третью группу. Они называются методы анализа отклонений и рассматриваются в разделе 1.3. Практически каждый метод из этой группы использует собственное формальное определение исключения. В частности, рассмотрены методы поиска исключений на основе нейронных сетей (SOM и репликаторные нейросети), методы последовательного поиска исключений (Sequential Exception Mining) [R. Agrawal, A. Arning, P. Raghavan, 1996], методы на основе кластеризации.

Следует заметить, что попытки ввести универсальное определение исключения, объединяющее разные подходы, предпринимались рядом авторов (например, [Е. Knorr, R. Ng & V.Tucakov, 2000]), но на настоящий момент не увенчались успехом.

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

• мотивированное интуитивно понятное определение исключения;

• вычислительная эффективность алгоритма поиска исключений;

• возможность работы с разнородными структурированными данными;

• минимальное использование в алгоритме параметров, устанавливаемых априори.

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

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

Определение 2.1. Пусть задано U = {Аг,..., Ар}- универсальное множество

атрибутов. Деревом схемы Т, заданным на множестве атрибутов U, будем

5

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

• Att(n)- множество атомарных атрибутов, связанных с узлом п\

• Num(n) с Att(ri) - множество числовых атрибутов в узле л;

• Discr(n) с. Att(n) - множество номинальных атрибутов в узле п;

• Кеу{п) с Att(n) - множество атрибутов, образующих первичный ключ в узле п, Att{ri) = Num{n) и Discr(n) u Key(n) ;

• Root(T) - корневой узел T.

Определение 2.2. Реляционная схема с вложенными отношениями NR(T), заданная на множестве атрибутов U деревом Т, определяется рекурсивно:

• если Г пусто, то NR(T) тоже пусто;

• если в Г только один узел и и V = Att(n), то NR(T) = V ;

• если V = Att(Root(T)) и Tl,...,Ts - табличные атрибуты (поддеревья первого уровня в Т), то AK(r) = ru{(AK(7i)*),...,(A«(rj*)};

Определение 2.3. Домен Dom(NR(T)) схемы NR(T) определяется рекурсивно:

• если Т пусто, то Dom{NR{T)) тоже пуст;

• если в Т только один узел п и V = Att(n), где V - }, то Dom(NR(T)) = Dom(V) = Dom(Al ) х ...xDom(Am ) ;

• если V = Att(Root(T)) и TU...,TS - табличные атрибуты (поддеревья первого уровня в Т), то

Dom{Tx,..., Ts ) = P(Dom(NR(Tx ))) x...xP(Dom(NR(Ts ))), где P(.) есть множество всех подмножеств, за исключением пустого множества. В результате: Dom(NR(T)) = Dom(V) х Dom(Tx,..., Ts ). Определение 2.4. Вложенным реляционным отношением г*, определенным схемой NR(T), является конечное множество картежей г е Dom{NR(T)). Таким образом, г* с P(Dom(NR(T))).

В разделе 2.2 ставится задача определения меры сходства для разнородных структурированных данных, структура которых задана реляционной схемой с вложенными отношениями NR(T). Мера сходства определяется в классе потенциальных функций [М.А. Айзерман, Э.М. Браверман, Л.И. Розоноэр, 1970]. Предлагается метод определения меры сходства для вложенных реляционных отношений, в котором используется .R-свертка [Haussier, 1999] потенциальных функций, заданных для атомарных атрибутов вложенного реляционного отношения.

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

Утверждение 2.1. Пусть дано конечное множество объектов, структура которых определена реляционной схемой с вложенными отношениями МЯ(Т). Универсальное множество атрибутов [/= {А1,..., Ар}, на

котором определена схема N11(7'), содержит числовые и номинальные

атрибуты. Тогда потенциальная функция

К: £>от(Ж(Г))х£>от(ЛЖ(Г)) 9*5

может быть определена рекурсивно:

К(х,у,Ж(Т))

х П

Т,е{Ти...Т3] кеОот(Кеу(Яоо1(Т,))) где Тг,...,Т$ - табличные атрибуты (поддеревья первого уровня в Т); К-Ыит(п) " потенциальная функция для числовых атрибутов в узле п; КП13СГ(п) - потенциальная функция для номинальных атрибутов в узле п; х, с Р(Оот(ЫЯ(Т())) - множество значений 1-го табличного атрибута для х; х1 (к) е Оот(ЫЯ(Т,)) - к-ый картеж из х(, соответствующий значению первичного ключа к из Вот(Кеу(Яоо1(Т1))).

Используя данный результат предлагается мера сходства, являющаяся Л-сверткой радиально-базисных потенциальных функций, определенных независимо для каждого из числовых и номинальных атомарных атрибутов реляционной схемы с вложенными отношениями. Утверждение 2.2. В условиях утверждения 2.1 семейство потенциальных функций К(д): Вот(Ы11(Т)) х Бот(ЫК(Т)) —»может быть определено как Я-свертка радиально-базисных (КВР) потенциальных функций по рекурсивной формуле:

JeDlscr(Root(T))лxJ#yJ

х гк^-**2'"? п 2»,(*Ш*),ЛИ( Г,))

|е№ии(Ж>о<(Г)) Т,(={Т1,..Т5)кеРот(Кеу(Коо1(Т1)))

где Я — (Я\,—,Яр)- параметры КВР потенциальных функций, определенных для атомарных атрибутов из II; х, - значение ¡-го атомарного (числового или номинального) атрибута картежа х; сг,- -оценка дисперсии {-го числового атомарного атрибута; р(.) — оценка маргинальной вероятности распределения номинального атомарного атрибута.

В разделе 2.3 Рассматриваются свойства предложенной меры сходства, семантика параметров и вычислительная сложность, обсуждается случай зависимых атрибутов и приводится пример применения предложенной меры сходства для поиска исключений в реляционных данных с помощью метрического метода DB(p,D) [Е. Knorr & R.Ng, 1997].

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

В третьей главе формулируется новый нечеткий метод поиска исключений, использующий потенциальные функции, и применимый для анализа больших объемов данных. В начале раздела 3.1 обсуждается вопрос применения потенциальных функций в методах поиска исключений, внимание акцентируется на методах, использующих гипотезу о компактности (111) [М.А. Айзерман, Э.М. Браверман, Л.И. Розоноэр, 1970]. В частности, рассматриваются методы опорных векторов Single-Class Support Vector Machine (Single-Class SVM) и Support Vector Clustering (SVC) [B. Scholkopf et al., 2000]. Данные методы, с помощью потенциальной функции if, отображают объекты исходного множествах в векторное пространство характеристик Н, возможно бесконечномерное. При этом явный вид отображения <р:Х Я не используется, а потенциальная функция определяет скалярное произведение в пространстве Н: К(х, у) = (tp(x), <р{у)) н ■ В пространстве характеристик

строятся гиперсфера (SVC) или гиперплоскость (Single-Class SVM), отделяющая компактное множество образов «основной части» объектов от остальных образов объектов, которые определяются как исключения. Размер этой «основной части», т.е. число ожидаемых исключений в X, контролируется специальным параметром. Эти методы доказали свою эффективность для большого числа прикладных задач, но они имеют ряд недостатков с точки зрения применение в системах ИАД. Эти недостатки связаны с тем что, решающая функция в Single-Class SVM и SVC является бинарной и существенно зависит от параметров, задаваемых априори. Для подбора значений этих параметров используются эвристические переборные методы, требующие многократного применения методов Single-Class SVM или SVC [A. Ben-Hur et al., 2001].

Для преодоления этих недостатков, в настоящей работе предлагается метод поиска исключений, который вместо гиперсферы ищет нечеткий кластер, такой что, образы «основной части» объектов в пространстве

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

Рассмотрим задачу нечеткой кластеризации в пространстве характеристик Я для случая одного кластера. Дано конечное множество объектов {*,•}!<,■<# с: X, причем на X х X задана потенциальная функция

К:ХхХ -»5R*, определяющая отображение <р:Х-*Н. Степень принадлежности и,- образов <р(х,) общему нечеткому кластеру в пространстве характеристик может быть определена из решения следующей задачи:

min J{U,a)

J(U,a) = !(«,■)">(*,)- afH +1/2(1 -и,)"

i=i i=i

(1)

где а е Я есть центр нечеткого кластера в пространстве характеристик, т > 1 и г} > о - параметры. (1) может рассматриваться как сформулированный в пространстве характеристик Я аналог целевой функции метода нечеткой кластеризации PCM [J.M.Keller & R. Krishnapuram, 1993]. Главным отличием является то, что центр кластера а принадлежит не исходному пространству X, а, вообще говоря, неизвестному векторному пространству характеристик, возможно бесконечной размерности.

Утверждение 3.1. Задача (1) может быть сведена к следующей задаче безусловной оптимизации:

J{U, а) =1 («,•)" i-1

min J(U,a)

Z afljKtj + К;, - ajKu \J>j j у

(2)

1=1

где Кu =K(xhXi). Утверждение 3.2. Необходимыми условиями минимума (2) являются:

. \ l/(m-l)

и,- =

1 +

2>,ayKz, +Кп -2SajK„

\\>-J J

n 1=1

Следствие 1. и, е [0,1].

\

/

Следствие 2. Поскольку

есть квадрат

^'j j у

расстояния в пространстве характеристик H от центра кластера а до образа <p(xt), то очевидна семантика параметра т]. Этот параметр определяет квадрат расстояния, на котором образ <р(х,- ) имеет степень принадлежность нечеткому кластеру равную 0.5. Таким образом, параметр т] играет роль радиуса нечеткого кластера.

Рассмотрев задачу нечеткой кластеризации в пространстве характеристик, сформулируем определение исключения для предлагаемого метода. Идея метода состоит в поиске в пространстве характеристик нечеткого кластера, включающего все образы объектов, таким образом, что степень принадлежности «основной части» выше 0.5. Размер этой «основной части» контролируется с помощью параметра т] -радиуса нечеткого кластера. Величина т) либо задается непосредственно, либо, определяется через число предполагаемых исключений к. Определим целевую функцию:

n . n п)

Ди,= £(и,)Ч2 («) + (1 - и,Г

¡=1 i=l

где а = (ах.....aN)e91м = (м1,...,мЛ,)е[0,1]ЛГ, d}(a) есть расстояние в

пространстве характеристик от образа ç(xl) до а, такое что:

¿,2(а) =

laiajKij +Kii-2Y.ajKu hi J

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

принадлежности в зависимости от расстояния до центра кластера.

Рассматриваются две постановки задачи.

П31: параметр rj = const задается априори (эквивалентна (2)).

ГО2: параметр т] определяется адаптивно, как расстояние от центра

кластера до (N-k) образа в следствии чего к объектов имеют степень

принадлежности меньше 0.5: tj = df.k (а), d^ (а) > d}.2 (а) >... > dJ.N(а)

Определение 3.2. Степенью «типичности» произвольного объекта х из X

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

образом:

\

и(х) =

1 +

iufiurm^j) £ utmK{x,x,) „ ,

j-л <=1__2i=1 ■ k(x>x)

l/(m-l)

«i 2

m

n

rjiu;

i=i

где My есть решение (3) в постановке ТТ31 или П32.

Определение 3.3. Объект хеХ является исключением тогда и только тогда, когда его степень «типичности» и{х) меньше заданного порога а. Замечание. Используя терминологию теории нечетких множеств, множество исключений есть множество а -уровня нечеткого множества U, заданного на универсуме X функцией принадлежности и(х).

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

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

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

Вообще, задача упрощения решающего правила возникает для большинства методов, использующих потенциальные функции. Для этих методов, как и для предложенного в настоящей работе метода поиска исключений на основе потенциальных функций, искомое решение а представляется как линейная комбинация образов объектов из {x;}Hi<N, а

решающее правило представляет собой функцию от линейной комбинации

f n л

потенциальных функций f(a,x) = /

V i

Формальная постановка задачи упрощения решающего правила в общем случае выглядит следующим образом. Пусть решение есть

n

a = H ßi<P(Xi ) ■ Требуется найти сокращенное множество {zj} , и

I

коэффициенты а = (а},..., aL ), такие что:

minfla -а'\\н, а'= j)> {zjhijsL <= Wis,^.L<<N ^ЗЛЗ)

j

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

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

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

В разделе 4.1 данной главы вводятся основные понятия и описывается задача и методы выявления вторжений, а также методика верификации методов обнаружения вторжений DARPA 1998 Intrusion Détection Evaluation Program. Под вторжением в компьютерную систему понимается любая деятельность, нарушающая целостность, конфиденциальность или доступность данных. Задача системы обнаружения вторжений IDS (intrusion détection system) - по действиям пользователя или программы определять, является ли такая активность допустимой, или может быть классифицирована как вторжение. Основным источником информации являются системные журналы и протоколы. Идея применения методов ИАД в системах обнаружения атак

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

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

системный журнал Сигнал

(System Log) администратору

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

• Хранилище данных для информации, собранной сенсорами.

• ИАД модуль реализует алгоритмы анализа данных, применяемые для построения ИАД моделей с использованием информации из хранилища.

• ИАД модели - модели нормальной активности или атак. Конкретный вид модели зависит от используемых алгоритмов анализа данных.

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

Методы ИАД, применяемые в IDS делятся на две группы: методы обнаружения нарушений (misuse detection), которые строят модель атаки, а в процессе обнаружения используют ИАД методы классификации или поиска ассоциаций; и методы обнаружения аномалий (anomaly detection), которые строят модель нормальной активности, а в процессе обнаружения используют ИАД методы кластеризации и поиска исключений.

В 1998 году MIT Lincoln Lab предложила методику верификации алгоритмов обнаружения вторжений DARPA 1998 Intrusion Detection Evaluation Program (далее DARPA). В нее входит эталонный набор данных, симулирующих сетевые атаки в локальную сеть. Одна из его версий в 1999 была использована в качестве тестовой задачи на KDD (Knowledge Discovery in Databases) Cup - ежегодном соревновании ИАД алгоритмов. С этого времени эталонный набор данных KDD Сир 99 регулярно

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

В разделе 4.2 описывается экспериментальное исследование по методике DARPA предложенного метода поиска исключений для задачи обнаружения атак. Результаты проведенного экспериментального исследования сравниваются с результатами существующих ведущих методов обнаружения атак, работающих как в режиме обнаружения нарушений, так и в режиме обнаружения аномалий. Следует заметить, что в силу того, что большинство существующих методов поиска исключений в отличии от предложенного в настоящей работе не способны работать с разнородными структурированными данными большого объема, эксперимент для них проводится не строго следуя методике DARPA. Таким образом при сравнительном анализе использовалось три различные сценария эксперимента. Первый, точно следующий методике DARPA использовался для сравнительного анализа с методами выявления нарушений. Во втором сценарии использовался сокращенный тестовый набор данных для сравнительного анализа с методами поиска исключений, использующими потенциальные функции (в них использовались потенциальные функции, отличные от предложенной в настоящей работе). При сравнении рассматривалось по одному методу, представляющему каждый из подходов: метод Single-Class SVM, метод анализа отклонений на основе алгоритма быстрой кластеризации с фиксированной шириной кластера [Е. Eskin & L. Portnoy, 2001] и метрический метод поиска исключений на основе к ближайших соседей kNN [Е. Eskin et al. 2002]. Третий тип эксперимента проводился на сокращенном наборе данных, с использованием только трех основных числовых атрибутов (продолжительность соединения, число переданных и полученных байт). В сравнительном анализе для данного типа эксперимента участвовали статистический метод SmartShifter, основанный на построении эмпирической вероятностной модели данных, метод анализа отклонений на основе репликаторной нейросети и глобальный метрический метод поиска исключений.

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

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

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

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

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

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

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

3. Исследована возможность применения предложенного метода поиска исключений для прикладной задачи обнаружения сетевых атак. Проведено экспериментальное исследование свойств предложенного метода по методике DARPA Intrusion Detection Evaluation Program и сравнительный анализ с ведущими методами обнаружения сетевых атак.

4. Предложенный метод поиска исключений реализован в программной компоненте анализа данных, поддерживающей промышленный стандарт OLEDB for Data Mining. На базе данной компоненты построена экспериментальная система обнаружения сетевых атак.

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

[1] Машечкин КВ., Петровский МИ. Об одном методе классификации данных для многомерной модели // Журнал НАМ Украины «Искусственный Интеллект», 2002, №2, сс. 188-196.

[2] I.V. Mashechkin, МЛ. Petrovskiy, The Fuzzy Metrics in Classification Problem for N-dimensional Cube-based Model // Proceedings of the Fifth International Symposium «Intelligent Systems», Moscow, BMSTU, 2002, p. 369.

[3] MM. Петровский, Мера сходства для сравнения прецедентов в системах анализа данных, поддерживающих стандарт OLEDB for Data Mining // Тематический сборник «Программные системы и инструменты», Изд. отдел ВМиК МГУ, 2002, №3, сс. 33-43.

[4] Mikhail Petrovskiy. A Hybrid Method for Patterns Mining and Outliers Detection in the Web Usage Log. // Springer-Verlag, Lecture Notes in Artificial Intelligence, 2003, vol. 2663, pp. 318-328.

[5] Mikhail Petrovskiy. Convolution Kernels for Outliers Detection in Relational Data. // Springer-Verlag, Lecture Notes in Computer Science, 2003, vol. 2690, pp. 661-668.

[6] М.И. Петровский. Алгоритмы выявления исключений в системах интеллектуального анализа данных. // Журнал РАН «Программирование», 2003, №4, сс. 66-80.

[7] Mikhail Petrovskiy. Fuzzy Kernel-based Method for Real-time Network Intrusion Detection // Springer-Verlag, Lecture Notes in Computer Science, 2003, vol. 2887, 12pages, (в печати).

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

¡* i ч 4 в 1 -А

ВВЕДЕНИЕ.

1. Интеллектуальный анализ данных.

2. Задача поиска исключений.

3. Актуальность.

4. Цель работы.

5. Структура и краткое содержание работы.

ГЛАВА I. СУЩЕСТВУЮЩИЕ МЕТОДЫ ПОИСКА ИСКЛЮЧЕНИЙ.

1.1. Статистический подход.

1.1.1. Методы традиционного статистического подхода.

1.1.2. Методы робастной нечеткой кластеризации.

1.1.3. Методы обнаружение исключений, строящие вероятностную модель данных.

1.2. Метрический подход.

1.2.1. Глобальные метрические алгоритмы.

1.2.2. Локальные метрические алгоритмы.

1.3. Методы анализа отклонений

1.3.1. Алгоритмы последовательного поиска исключений.

1.3.2. Репликаторные нейронные сети.

1.3.3. Подходы на основе кластеризации.

1.4. ВЫВОДЫ.

ГЛАВА II. МЕРА СХОДСТВА ДЛЯ РАЗНОРОДНЫХ

СТРУКТУРИРОВАННЫХ ДАННЫХ.

2.1. Представление данных в системах ИАД.

2.1.1. Типы источников данных.

2.1.2. Реляционная модель с вложенными отношениями.

2.2 мера сходства для вложенных реляционных отношений.

2.2.1. Потенциальная функция как мера сходства.

2.2.2. Определение потенциальной функции для вложенных реляционных отношений.

2.3. Основные свойства предложенной меры сходства. to 2.3.1. Семантика параметров.

2.3.3. Вычислительная сложность.

2.3.3. Предположение о независимости атрибутов.

2.3.4. Пример использования предложенной меры сходства для поиска исключений в реляционных данных.

2.4. Выводы.

ГЛАВА III. НЕЧЕТКИЙ МЕТОД ПОИСКА ИСКЛЮЧЕНИЙ С ИСПОЛЬЗОВАНИЕМ ПОТЕНЦИАЛЬНЫХ ФУНКЦИЙ.

3.1. Обоснование и формулировка метода.

3.1.1. Потенциальные функции в задачах поиска исключений.

3.1.2. Идея метода, определение исключения.

3.1.3. Алгоритм поиска исключений на основе блочного покоординатного спуска.

3.1.4. Исследование сходимости.

3.2. Повышение вычислительной эффективности метода для больших объемов данных.

3.2.1. Оценка сложности алгоритма и применение методов случайной выборки.

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

3.2.3. Алгоритм упрощения решающего правила на основе алгоритма кластеризации Руспини.

3.3. Экспериментальное исследование метода на эталонных наборах данных.

3.3.1. Данные с числовыми атрибутами. Тестовый набор данных НВК.

3.3.2. Данные с бинарными и номинальными атрибутами. Тестовые наборы данных из архива UCI.

И 3.3.3 Реляционные данные. База данных Northwind.

3.5. ВЫВОДЫ.

ГЛАВА IV. АПРОБАЦИЯ НА ПРИКЛАДНОЙ ЗАДАЧЕ ОБНАРУЖЕНИЯ КОМПЬЮТЕРНЫХ АТАК.

4.1. Задача обнаружения атак.

4.1.1. Методы ИАД в системах обнаружения атак.

4.1.2. Методика верификации алгоритмов выявления сетевых атак.

4.2. Экспериментальное исследование метода для задачи выявления сетевых атак.

4.2.1. Постановка эксперимента.

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

4.2.3. Сравнительный анализ.

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

4.3.1. Реализация модуля поиска исключений, поддерживающего стандарт OLEDB for Data Mining.

4.3.2. Архитектура и функциональность экспериментальной системы обнаружения атак.

4.4.Вывод ы.:.

1. ИНТЕЛЛЕКТУАЛЬНЫЙ АНАЛИЗ ДАННЫХ

С развитием информационных технологий увеличивается количество, размеры и сложность хранилищ и баз данных. Объем хранимой информации в таких системах может достигать миллионов и даже миллиардов записей. В связи с чем возникает необходимость разработки программных средств автоматизированного анализа данных большого объема с целью извлечения из них содержательной информации. Для этих целей используются системы интеллектуального анализа данных (НАД) [6,10,14,37,56,59,66].

Согласно подходу, представленному в работах [56,59,66], интеллектуальный анализ данных (Data Mining) рассматривается как один из этапов процесса, называемого обнаружение знаний в базах данных (Knowledge Discovery in Databases). Этот термин был впервые введен в работе [59], где определялся следующим образом: «Обнаружение знаний в базах данных это нетривиальный процесс выявления скрытых, значимых, содержательных и потенциально полезных закономерностей в больших объемах данных». Найденные таким образом закономерности затем могут быть использованы экспертом или программными системами при решении задач поддержки принятия решений, информационного поиска, управлении производственными процессами и в других приложениях.

В процессе обнаружения знаний в базах данных принято выделять три взаимосвязанных этапа:

• объединение и предобработка данных;

• интеллектуальный анализ данных;

• проверка, интерпретация и визуализация результатов.

Хранилище данных

Знания» Найденные » закономерности /^Проверка, модели) f^j] интерпретация и визуализация

Интеллектуальный анализ данных (Data Mining)

Базы /""Объединение и данных рзэ предобработка LJ данных

Схема 1. Процесс выявления знаний в базах данных.

Объединение и предобработка данных. На данном этапе происходит консолидация данных из различных источников, удаление некорректных значений и вычисление агрегационных значений. Как правило, после этого этапа данные помещаются в хранилище, использующее либо реляционное представление [40], либо многомерное представление на основе п-мерного информационного куба [16,41].

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

Проверка, интерпретация и визуализация результатов. Данный этап основан на интерактивном взаимодействии с экспертом, проводящим анализ данных. Эксперт должен иметь возможность просмотреть и проверить найденные закономерности. Возможно, заново произвести анализ данных, изменив параметры применяемых алгоритмов. Кроме того, на данном этапе могут К применяться статистические методы [2] и методы теории возможностей [11] для проверки значимости найденных закономерностей и адекватности построенных моделей.

Традиционно выделяют следующие основные задачи интеллектуального анализа данных (Data Mining tasks) [37,66]: поиск ассоциативных правил; классификация; прогнозирование; кластеризация; анализ временных рядов; поиск исключений.

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

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

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

3. Исследована возможность применения предложенного метода поиска исключений для прикладной задачи обнаружения сетевых атак. Проведено экспериментальное исследование свойств предложенного метода по методике DARPA Intrusion Detection Evaluation Program и сравнительный анализ с ведущими методами обнаружения сетевых атак.

4. Предложенный метод поиска исключений реализован в программной компоненте анализа данных, поддерживающей промышленный стандарт OLEDB for Data Mining. На базе данной компоненты построена экспериментальная система обнаружения сетевых атак.

Данные результаты опубликованы в 7 печатных работах [104-110].

ЗАКЛЮЧЕНИЕ

1. Аверкин А.Н., Батыршин И.З., Блишун А.Ф., Сипов В.Б., Тарасов В.Б. Нечеткие множества в моделях управления и искусственного интеллекта // Москва, Наука, 1986, 312 с.

2. Айвазян С.А., Енюков И.С., Мешалкин Л Д. Прикладная статистика: Исследование зависимостей // Справочное издание под ред. Айвазяна С.А., Москва, Финансы и статистика, 1985, 471 с.

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

4. Алгоритмы и программы восстановления зависимостей (под ред. В.Н.Вапника) //Москва, Наука, 1983, 816 с.

5. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1980.

6. Забежайло М.И. Интеллектуальный анализ данных новое направление развития информационных технологий // НТИ. Сер. 2, 1998, № 8, сс. 6-17.

7. Классификация и кластер // Под ред. Дж. Вэн Райвин; Пер. с англ. под ред. Ю.И. Журавлева. М.: Мир, 1978.

8. Лукацкий А.В. Обнаружение атак. // 2е издание. СПб.: БХВ-Петербург, 2003., 569 с.

9. ПолякБ.Т. Введение в оптимизацию. М.: Наука, 1983, 385 с.

10. Пржиялковский В. В. Сложный анализ данных большого объема: новые перспективы компьютеризации // СУБД, № 4, 1996, сс. 71-83.

11. Пытьев Ю.П. Возможность. Основы теории и применения. // Москва, Эдиториал УРСС, 2000

12. Хьюбер П. Робастность в статистике. // Москва, Мир, 1984, 303 с.

13. Ченцов Н.Н. Оценка неизвестной плотности распределения по наблюдениям //ДАН СССР, т.147, №1, 1962.

14. Щавелёв Л. В. Способы аналитической обработки данных для поддержки принятия решений // СУБД, 1998, № 4-5.

15. Agrawal R., Arning A., Raghavan P. A Linear Method for Deviation Detection in Large Databases // Proc. of the 2nd Int'l Conference on Knowledge Discovery in Databases and Data Mining, Portland, Oregon, August, 1996, pp. 164-169.

16. Agrawal R., Gupta A., Sarawagi A., Modeling Multidimensional Databases // IBM Research Report, 1995, (published in the proceedings of ICDE'97)

17. Agrawal R., Megiddo N., Sarawagi S. Discovery-driven exploration of OLAP data cubes // Proc. of the Sixth International Conference on Extending Database Technology (EDBT), Spain, 1998, pp. 168-182.

18. Arnold A., Eskin E., Prerau M., Portnoy L., Stolfo S. A Geometric Framework for Unsupervised Anomaly Detection: Detecting Intrusions in Unlabeled Data // Kluwer, Applications of Data Mining in Computer Security, 2002, pp.272.

19. Batistakis Y.,Halkidi M., Vazirgiannis M. Clustering Validity Checking Methods: Part II // SIGMOD Record 31(3): 19-27 (2002)

20. Barnett, V. and Lewis, T. Outliers in Statistical Data // Wiley, N. Y., 1994, 365pp.

21. Baxter R., Gu L., Hawkins S., He H., Williams G. A Comparative Study of RNN for Outlier Detection in Data Mining // IEEE ICDM 2002, pp.709-712.

22. Baxter R., Gu L., Hawkins S., He H., Williams G. Outlier Detection Using Replicator Neural Networks // Proceedings of DaWaK 2002, pp. 170-180.

23. Ben-Hur A., Horn D., Siegelmann H., Vapnik V. Support Vector Clustering // Journal of Machine Learning Research, 2001, 2:125-137.

24. Bezdek, J.C. Fuzzy Mathematics for Pattern Classification // PhD Thesis, 1973, Cornell University, Ithaca, NY.

25. Bezdek, J.C. Pattern Recognition with Fuzzy Objective Function Algorithms // Plenum Press, New York, 1981.

26. Bezdek, J.C., Hathaway R.J. Some Notes on Alternating Optimization //Springer-Verlag, 2002, pp. 288-300.

27. Bezdek, J.C., Hathaway R.J., Howard R.E., Wilson C.A., and M.P. Windham. Local convergence analysis of a grouped variable version of coordinate descent // Journal of Optimization Theory and Applications, 1987, v. 54, pp.471-477.

28. Bolton, R. J., Hand D. J. Statistical Fraud Detection: A Review (with discussion). // Statistical Science, 2002, 17(3), pp. 235-255.

29. Bradley P., Fayyad U., Reina C. Scaling EM (Expectation-Maximization) Clustering to Large Databases // Microsoft Technical Report MSR-TR-98-35, February 1999.

30. Bradu D., Hawkins D. M, Kass G. V. Location of several outliers in multiple regression data using elemental sets // Technometrics, 1984, 26:197-208.

31. Breunig S., Kriegel H.-P., Ng R., Sander J. LOF: Identifying Density-Based Local Outliers // ACM SIGMOD Int. Conf. on Management of Data, 2000, pp. 93-104.

32. Breunig M. M., Kriegel H.-P., Ng R., Sander J. OPTICS-OF: Identifying Local Outliers III Proceedings Conf. on Principles of Data Mining and Knowledge Discovery, Prague, 1999, pp. 262-270.

33. В urge, P. and J. Shawe-Taylor. Frameworks for fraud detection in mobile telecommunications networks // Proceedings of the Fourth Annual Mobile and Personal Communications Seminar, University of Limerick, 1996,

34. Burges С. Simplified Support Vector Decision Rules //13th International Conference on Machine Learning, 1996, pp. 71-79.

35. Burges C., Knirsch P., Mika S., Mtiller K.-R., Ratsch G., Scholkopf В., Smola A.J. Input space versus feature space in kernel-based methods //IEEE Transactions On Neural Networks 10(5), 1000-1017(1999)

36. Chan P., Eskin E., Fan IV., Hershkop S., Lee W., Miller M., Stolfo S., Zhang, J. Real Time Data Mining-based Intrusion Detection // Proceedings of DISCEX II. (2001), 12p.

37. Chen M-S., Han J., Yu P. S. Data Mining: An Overview from Database Perspective // IEEE Transactions on Knowledge and Data Engineering, 1996, №6, pp. 866-883.

38. Cheng G., Liu, X., Wu, J. Analyzing outliers cautiously. I I IEEE Transactions on Knowledge and Data Engineering, 2002, 14(2):432-437.

39. Choi Y., Krishnapuram R. Fuzzy and robust formulation of maximum-likelihood-based Gaussian mixture decomposition //In IEEE Conference on Fuzzy Systems, pages 1899-1905, New Orleans, Sep. 1996.

40. Codd E.F. The Relational Model for Database Management: Version 2 // Addison-Wesley Pub Co, Addison-Wesley, 1990, 538pp.

41. Codd E.F. Providing OLAP (on-line analytical processing) to user-analysts: an IT mandate // Technical Report, E.F. Codd and Associates, 1993, 31pp.

42. Cohen W. W. Fast effective rule induction. //Machine Learning: the 12th International Conference, Lake Taho, CA, 1995. Morgan Kaufmann. Pp. 115123.

43. Cristianini N., Lodhi H., Shawe-Taylor J., Watkins C. Text classification using string kernels // MIT Press, 2001, Advances in Neural Information Processing Systems 13, pp. 563—569.

44. Dave R. N. Krishnapuram R. Robust clustering methods: A unified view. // IEEE Trans. Fuzzy Syst., 5(2):270-293, 1997.

45. Dave R. N. Kim J., Krishnapuram R. On robustifying the c-means algorithms 7/ In NAFIPS/ISUMA, pp. 630-635, College Park, MD, Sep. 1995.

46. Deng S., He Z, Xu X. Discovering cluster-based local outliers // Pattern Recognition Letters 2003, 24(9-10): 1641-1650.

47. Denning D.E.: An intrusion detection model // IEEE Transactions on Software Engineering, SE-13 (1987), 222-232

48. Dodd, T.J. and C.J. Harris. Identification of Nonlinear Time Series via Kernels // International Journal of Systems Science 2002 , 33(9), 737-750.

49. Dokas P., Ertoz L., Kumar V., Lazarevic A. Srivastava, J., Tan, P. Data Mining for Network Intrusion Detection // Proceedings NSF Workshop on Next Generation Data Mining, Baltimore, MD, November 2002.

50. Ertoz, L., Kumar V., Steinbach, M. Finding clusters of different sizes, shapes, and densities in noisy, high dimensional data, Technical Report, 2002, p. 12.

51. Eskin E. Anomaly Detection over Noisy Data using Learned Probability Distributions // In Proceedings of the International Conference on Machine Learning, 2000, pp. 255-262. '

52. Eskin E., Leslie C., Stafford W. The spectrum kernel: A string kernel for SVM protein classification // Proceedings of the Pacific Symposium on Biocomputing, 2002, pp. 564-575.

53. Eskin E., Portnoy L. Intrusion Detection with Unlabeled Data using Clustering I I Proceedings of ACM CSS Workshop on Data Mining Applied to Security, DMSA-2001.

54. Fayyad U., Piatetski-Shapiro G. Advances in Knowledge Discovery and Data Mining // MIT Press, 1996, 560pp.

55. Filev D. P., Yager R. R. Approximate clustering via the mountain method // SMC 1994, 24(8): 1279-1284.

56. Frigui H., Krishnapuram R. A robust clustering algorithm based on the m-estimator // In Neural, Parallel and Scientific Computations, Atlanta, Georgia, May 1995.

57. Frawley W., Piatetsky-Shapiro G. Knowledge Discovery in Databases // MIT Press, 1991, 539pp.

58. Gaede, V., Gnther, O. Multidimensional Access Methods // ACM Computing Surveys, 30(2), 1998.

59. Gammerman A., Stitson M. O., Vapnik V., Vovk V., Watkins C., Weston J. Density estimation using support vector machines // Technical report, Royal Holloway College, Report number CSD-TR-97-23, 1997,12 pp.

60. Getoor L., Freedman N., Koller D., Taskar B. Learning Probabilistic Models of Relational Structure // Journal of Machine Learning Research, 3:679-707,2002.

61. Girolami, M., He, C. Probability Density Estimation from Optimally Condensed Data Samples //Computing & Information Systems Technical Reports, 2002, 25 pp.

62. Gunn S.R. and Kandola, J.S. Structural modelling with sparse kernels // Machine Learning, 2002, 48(1): 137-163.

63. Han J. OLAP mining: An integration of OLAP with data mining // Proc. of the 7th IFIP 2.6 Working Conference on Database Semantics (DS-7), 1997, pp. 1-9.

64. Han J., Kamber M. Data Mining: Concepts and Techniques I I Morgan Kaufmann, 2000, 500pp.

65. Han J., Tung K., Wen J. Mining top-n local outliers in large databases // KDD, 2001, pp. 293-298.

66. Haussler D. Convolution Kernels on Discrete Structures // Technical Report UCSC-CRL-99-10, CS Department, University of California at Santa Cruze, 1999, 38 pp.

67. Hiirsalmi M, Abnormality detection using SOM modelling // VTT Information Technology RESEARCH REPORT TTE1-2001-16, 2001, p.54.

68. Keller, J. M., Krishnapuram, R. A Possibilistic Approach to Clustering // IEEE Trans. Fuzzy Systems. Vol. 1. № 1, 1993, pp. 98-110.

69. Knorr E., Ng R. Algorithms for Mining Distance-Based Outliers in Large Datasets // VLDB 1998, pp. 392-403.

70. Knorr E., Ng R. A Unified Notion of Outliers: Properties and Computation // Proceedings of KDD 1997, pp. 219-222.

71. Knorr E., Ng R., and Tucakov V. Distance-Based Outliers: Algorithms and Applications // VLDB Journal, 2000, 8(3-4):237~253.

72. Knorr E., Ng R, Zamar R. Robust Space Transformations for Distance-Based Operations // Proceedings of the 7th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, San Francisco, August 25-29, 2001, pp. 126-135.

73. Krishnapuram R, Nasraoui O. A robust estimator based on density and scale optimization, and its application to clustering // IEEE International Conference on Fuzzy Systems, 1996, pp. 1031-1035.

74. Krishnapuram R, Nasraoui O. Crisp interpretation of fuzzy and possibilistic clustering algorithms. // 3rd European Congress on Intelligent Techniques and Soft Computing, 1995, vol. 3, pp. 1312-1318.

75. Kumar V. Data Mining for Network Intrusion Detection // Presentation at NSF Workshop on Next Generation Data Mining, Nov 1-3, 2002.

76. Kumar S., Spafford E. An Application of Pattern Matching in Intrusion Detection // Technical Report 94-013, Department of Computer Sciences, Purdue University, March 1994, p.55

77. Lee W. A Data Mining Framework for Constructing Features and Models for Intrusion Detection Systems // PhD thesis, Computer Science Department, Columbia University, 1999.

78. Leroy A. M., Rousseeuw P. J. Robust Regression & Outlier Detection // Wiley, 1987, pp.352.

79. Levene M., Loizou G. A Fully Precise Null Extended Nested Relational Algebra // Fundamenta Informaticae, 1993, 19, pp. 303-343.

80. Marichal, J.-L. On Sugeno integral as an aggregation function I I Fuzzy Sets and Systems, 2000,114, pp. 347-365.

81. Merz C.J., Murphy P.M. UCI repository of machine learning databases, 1998. www.ics.uci.edu/mlearn/MLRepository.html

82. MIT Lincoln Lab Intrusion Detection Evaluation Program http://www.ll.mit.edu/IST/ideval

83. Moon T. The Expectation-Maximization algorithm // IEEE Signal Processing Magazine, pp. 47-60, Nov. 1996.

84. Mtiller K.-R., Scholkopf В., Smola A.J. Kernel principal component analysis // MIT Press, Cambridge, MA (1999), Advances in Kernel Methods Support Vector Learning, pp. 327-352.

85. Northcutt S., Novak J. Network Intrusion Detection. 3rd edition // Que, 2002, 512pp.

86. Northwind Traders Sample Database. Microsoft Corporation, (2003) http://office.microsoft.com/downloads/9798/Nwind.aspx

87. Ohashi Y. Fuzzy clustering and robust estimation // Presentation at the 9th meeting of SAS Users Group International, 1984.

88. OLE DB for Data Mining Specification. Version 1.0. Microsoft Corporation, 2000. http://www.microsoft.com/data/oledb/dm.html

89. Parzen E. On the estimation of a probability density function and the mode // Ann. Math. Statistics, vol. 33, pp. 1065-1076, 1962.

90. Petrovic P.B. A Fast One-Pass Algorithm for Data-Driven Fuzzy Pattern Recognition // International Journal of Fuzzy Systems, Vol. 4, No. 2, June 20026 pp. 680-689.

91. Piatt J., Scholkopf В., Smola A., Shawe-Taylor J., Williamson R. Support Vector Method for Novelty Detection // Advances in Neural Information Processing Systems 2000, 12, pp. 582-588.

92. Scholkopf В., Smola A. J. Learning with Kernels //MIT Press, Cambridge, 2002, 625 p.

93. Ramaswamy S., Rastogi R., Shim K. Efficient Algorithms for Mining Outliers from Large Data Sets // Proc. of ACM SIGMOD Intl. Conf. On Management of Data, 2000, pp 427 438.

94. Rocke D. A Perspective on Statistical Tools for Data Mining Applications // Proceedings of the Second International Conference on Practical Application of Knowledge Discovery and Data Mining, 1998, pp. 313-318.

95. Rosenblatt, M. On Some Nonparametric Estimates of a Density Function // The Annals of Mathematical Statistics, 1956, 27, pp. 832-837.

96. Ruspini, E.H. Recent developments in fuzzy clustering. // Fuzzy Set and Possibility Theory: Recent Developments. Pergamon Press, New York, 133-147 (1982)

97. Sykacek P. Outliers and Bayesian Inference // Proc. of the International ICSC/IFAC Symposium on Neural Computation, 1998, pp. 973-978.

98. Takeuchi J., Williams G., Yamanishi K. On-line unsupervised outlier detection using finite mixtures with discounting learning algorithms // Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 2000, pp. 320-324.

99. Watkins C. Dynamic alignment kernels. //MIT Press, Cambridge, Advances in Large Margin Classifiers, 2000, pp. 39-50.

100. Yianolos. Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces //Proceedings of 4th ACM-SIAM Symposium on Discrete Algorithms, 1993, pp. 311 -321.

101. Машечкин И.В., Петровский М.И. Об одном методе классификации данных для многомерной модели // Журнал НАН Украины «Искусственный Интеллект», Донецк, 2002, №2, сс. 188-196.

102. I.V. Mashechkin, M.I. Petrovskiy, The Fuzzy Metrics in Classification Problem for N-dimensional Cube-based Model // Proceedings of the Fifth International Symposium «Intelligent Systems», Moscow, BMSTU, 2002, p 369.

103. М.И. Петровский, Мера сходства для сравнения прецедентов в системах анализа данных, поддерживающих стандарт OLEDB for DM // Тематический сборник «Программные системы и инструменты», Издательский отдел ВМиК МГУ, 2002, №3, сс. 33-43.

104. М.И. Петровский. Алгоритмы выявления исключений в системах интеллектуального анализа данных. // Журнал РАН «Программирование», 2003, №4, сс. 66-80.

105. Mikhail Petrovskiy. A Hybrid Method for Patterns Mining and Outliers Detection in the Web Usage Log. // Springer-Verlag, Lecture Notes in Artificial Intelligence, 2003, vol. 2663, pp. 318-328.

106. Mikhail Petrovskiy. Convolution Kernels for Outliers Detection in Relational Data. // Springer-Verlag, Lecture Notes in Computer Science, 2003, vol. 2690, pp. 661-668.

107. Mikhail Petrovskiy. Fuzzy Kernel-based Method for Real-time Network Intrusion Detection // Springer-Verlag, Lecture Notes in Computer Science, 2003, vol. 2887, (12pages) (в печати).