Сложность распознавания принадлежности слова регулярному языку в системах обнаружения вторжений тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Александров, Дмитрий Евгеньевич

• Александров, Дмитрий Евгеньевич
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Александров, Дмитрий Евгеньевич

Оглавление

Введение

1 Постановка задачи

2 Модификации конечных автоматов

2.1 Регулярные языки и выражения

2.2 Простейшие конечные автоматы

2.2.1 Недетерминированный конечный автомат

2.2.2 Детерминированный конечный автомат . •

2.2.3 Детерминированный конечный мультиавтомат

2.3 Конечные автоматы с модифицированными переходами

2.3.1 Алгоритм Ахо-Корасик

2.3.2 Детерминированный конечный автомат с задержкой

2.3.3 Двойной автомат

2.3.4 Расширенный детерминированный конечный автомат

2.4 Выводы

3 Модификация двух выражений

3.1 Алгоритм объединения выражений

3.2 Оценка числа состояний

3.2.1 Вспомогательные утверждения

3.2.2 Доказательство теоремы 1

3.3 Применение алгоритма

4 Модификация произвольного числа выражений

4.1 Оценка числа состояний

4.1.1 Вспомогательные утверждения

4.1.2 Доказательство теоремы 2

4.1.3 Доказательство теоремы 3

4.1.4 Доказательство теоремы 4

4.2 Применение алгоритма

5 Оценка роста языка при модификации выражений

5.1 Способ оценки

5.1.1 Вспомогательные утверждения

5.1.2 Доказательство теоремы 5

5.2 Применение алгоритма

Заключение

Список литературы

Приложение 1

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

Введение

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

С развитием технологий передачи данных одним из актуальных направлений информационной безопасности стали исследование и фильтрация сетевого трафика для противодействия реализации угроз деструктивных воздействий на ресурсы информационных систем в открытых компьтер-ных сетях. Согласно ежегодному отчету корпорации Cisco [1], только в 2013 году число обнаруженных сетевых вторжений, то есть несанкционированных воздействий на ресурсы информационной системы с использованием протоколов межсетевого взаимодействия, увеличилось на 14% ио сравнению с предыдущим годом и превысило в среднем 50000 вторжений в день. На настоящее время существует большое число различных сетевых систем обнаружения вторжений (ССОВ), однако наибольшее распространение получили системы, базы сигнатур которых представляют собой наборы регулярных выражений, а вердикт о вредоносности трафика выносится на основании соответствия фильтруемых данных хотя бы одному из регулярных выражений базы. К описанному типу относятся такие известные системы как Snort [2]. Отметим, что по результатам исследований, проведенных компанией Gartner в 2013 году [3], компания Sourcefire, разрабатывающая систему Snort, была признана лидером в области ССОВ. К числу других систем подобного назначения можно отнести также и Вго [4], L7-filter [5] и

аппаратные продукты фирмы Cisco [6]. Последняя фирма является лиде, ром в области ССОВ по версии компании Gartner в 2014 году [7].

Традиционно для проверки принадлежности слова регулярному языку, задаваемому набором регулярных выражений, используются детерминированные конечные автоматы (ДКА) [8; 9]. Данный метод характеризуется крайне низкой сложностью вычисления. Однако с ростом числа распознаваемых выражений увеличивается пространственная сложность — число состояний распознающего ДКА, и, соответственно, необходимый для программной реализации алгоритма объем памяти. В случае, когда число состояний автомата экспоненциально зависит от количества регулярных выражений, говорят о так называемом "экспоненциальном взрыве". Среди различных видов выражений, приводящих к экспоненциальному взрыву, можно выделить класс выражений вида .*Ri.*R2.*, где Ri и R2 — регулярные выражения, а подвыражения .* задают регулярные языки, совпадающие со множеством всех слов Е*, где S — алфавит, над которым заданы выражения. Отметим, что выражения такого вида часто встречаются на практике в системах обеспечения информационной безопасности. Например, база сигнатур сетевой системы обнаружения вторжений Snort [10] содержит 36 таких выражений. При этом детерминированный конечный автомат, распознающий регулярный язык, задаваемый только 11 из 36 выражений, содержит более 1.5 млн. состояний. Отмеченная выше сложность существенно ограничивает возможности ССОВ. В связи с этим нахождение способа нивелирования эффекта экспоненциального взрыва является важной практической задачей.

Существует два основных подхода к преодолению проблемы экспоненциального взрыва. Первый подход — выбор специальной модификации конечного автомата для определения принадлежности произвольного слова регулярному языку, который задается набором регулярных выражений. Самой простой реализацией конечных автоматов, помимо ДКА, является недетерминированный конечный автомат (НКА) [8; 9]. Такой автомат имеет относительно небольшое количество состояний — порядка 0(1), где I — сумма длин реализуемых регулярных выражений, а значит и объем

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

В основе другой реализации, предложенной А. Ахо (Alfred V. Aho) и М. Корасик (Margaret J. Corasick) [И], также лежит ДКА, по изменен способ хранения переходов. В рамках этой реализации для каждого состояния автомата хранятся переходы только для некоторых символов входного алфавита и "переход в случае ошибки". Алгоритм работы такого автомата следующий: если для нового входного символа существует переход из текущего состояния, то осуществляем его как в обычном ДКА, если же переход отсутствует, то используем "переход в случае ошибки" и еще раз проверяем наличие перехода для того же входного символа (теперь уже для нового состояния). Такая техника впоследствии была расширена на регулярные выражения и получила название детерминированный конечный автомат с задержкой (D2FA) [12].

Третий способ реализации — обычный ДКА, но с некоторым набором вспомогательных данных, зависящим от конкретной модификации. При этом общей чертой всех модификаций является наличие "быстровычисли-мого" алгоритма изменения этого набора данных при каждом новом входном символе. Так, например, двойной конечный автомат (DualFA) [13] состоит из ДКА и битового массива. При поступлении на вход нового символа производится обычный переход у ДКА и несколько битовых операций с массивом. После этого осуществляется еще один переход в ДКА в зависимости от значений массива и состояний ДКА. Другие варианты такого типа реализации — расширенный конечный автомат (XFA) [14] и конечный автомат с счетчиками (HFA) [15], сочетающие в себе ДКА и набор счетчиков, которые тривиальным образом изменяются в зависимости от входного символа и текущего состояния и предотвращают "экспоненциальный взрыв" числа состояний конечного автомата в случае, когда PCRE-совместимые регулярные выражения [16] содержат символы повтора (V, "+" и "{,}").

Второй подход к решению задачи оптимизации проверки на принадлежность слова регулярному языку предполагает изменение исходного набора регулярных выражений так, чтобы сократить сложность реализации в конечных автоматах за счет расширения определяемого выражениями регулярного языка. Отметим, что этот подход более универсален, так как может быть скомбинирован с любой из реализаций первого подхода. К сожалению, данный подход слабо изучен, а методы, предлагаемые в работах по данной теме, как, например, в статье [17], подразумевают лишь "ручное" переписывание выражений, когда специалист принимает решение об изменении каждого конкретного выражения. Регулярное обновление баз сигнатур систем информационной безопасности, обусловленное появлением новых угроз, является главной причиной неэффективности, а в некоторых случаях и невозможности, использования "ручного" переписывания выражений. Поэтому в контексте информационной безопасности наибольший интерес представляют методы переписывания регулярных выражений, которые допускают автоматизацию посредством ЭВМ.

Цель исследования. Основной целью настоящей работы является исследование и совершенствование математических методов, применяемых в сетевых системах обнаружения вторжений. Тема, объект и предмет диссертационной работы соответствуют следующим пунктам паспорта специальности 05.13.17 — Теоретические основы информатики: исследование моделей и алгоритмов анализа данных; разработка основ математической теории языков и грамматик, теории конечных автоматов. Тема, объект и предмет диссертационной работы соответствуют следующим пунктам паспорта специальности 05.13.19 — Методы и системы защиты информации, информационная безопасность: методы и средства (комплексы средств) информационного противодействия угрозам нарушения информационной безопасности в открытых компьютерных сетях, включая Интернет; принципы и решения (технические, математические, организационные и др.) по созданию новых и совершенствованию существующих средств защиты информации и обеспечения информационной безопасности.

Для достижения поставленной цели в работе сформулированы и реша-

ются следующие задачи.

• Разработка метода модификации произвольного набора регулярных выражений вида .*R1.*R2.*, которые используются в сетевых системах обнаружения вторжений, для уменьшения автоматной сложности распознавания принадлежности слова регулярному языку, который задается данным набором выражений.

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

• Тестовые испытания программной реализации разработанного метода модификации выражений на сигнатурах сетевой системы обнаружения вторжений Snort.

Научная новизна. Результаты диссертации являются новыми и получены автором самостоятельно. Основные результаты диссертации состоят в следующем.

1. Разработан и программно реализован способ автоматизированной модификации набора регулярных выражении вида . ^R^.^R^*, используемых в сетевых системах обнаружения вторжений, для сокращения автоматной сложности регулярного языка, задаваемого набором выражений.

2. Предложены оценки, в том числе — неулучшаемые, автоматной сложности набора выражений вида .*Ri.*R2.* для немодифицированного и модифицированного случаев.

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

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

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

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

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

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

• семинар «Современные проблемы криптографии» под руководством ведущего научного сотрудника В.А. Носова и доцента А.Е. Панкратьева, механико-математический факультет МГУ имени М.В. Ломоносова, 2014 г.;

• семинар «Компьютерная безопасность» под руководством старшего научного сотрудника A.B. Галатенко, механико-математический факультет МГУ имени М.В. Ломоносова, 2014 г.;

• научный семинар «Проблемы современных информационно-вычислительных систем» под руководством профессора В.А. Васенина, механико-математический факультет МГУ имени М.В. Ломоносова, 2014 г.;

• научный семинар «Теория автоматов» под руководством профессора В.Б. Кудрявцева, механико-математический факультет МГУ имени М.В. Ломоносова, 2014 г.;

• Индийско-Российская конференция но алгебре, теории чисел, дискретной математике и приложениям, МГУ имени М.В. Ломоносова, 15-17 октября 2014 г.;

• семинар «Кольца, модули и матрицы» под руководством профессора A.B. Михалева и профессора В.Н. Латышева, механико-математический факультет МГУ имени М.В. Ломоносова, 2014 г.;

• семинар «Математические модели информационных технологий» под руководством профессора С.О. Кузнецова, департамент анализа данных и искусственного интеллекта и НУЛ «Интеллектуальные системы и структурный анализ» НИУ ВШЭ, 2015 г.;

• семинар «Сложность распознавания принадлежности слова регулярному языку, заданному набором регулярных выражений» под руководством В.В. Корнеева, ФГУП НИИ Квант, 2015 г.;

• XXII международная конференция студентов, аспирантов и молодых ученых «Ломоносов», МГУ имени М.В. Ломоносова, 13-17 апреля 2015 г.;

• республиканская научная конференция «Современные методы математической физики и их приложения», Национальный университет Узбекистана имени Мирзо Улугбека, 15-17 апреля 2015 г.

Публикации. Основные результаты диссертации опубликованы в 4 работах автора [23—26] в научных журналах из списка, рекомендованного ВАК РФ.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы из 27 наименований и приложения — копии свидетельства о государственной регистрации программы для ЭВМ. Общий объем диссертации составляет 114 страниц.

Краткое содержание диссертации

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

В главе 1 сформулирована задача, решение которой представлено в настоящей диссертации.

В главе 2 изложены различные модификации конечных автоматов, решающих задачу оптимизации проверки принадлежности слова регулярному языку, который задается набором регулярных выражений. Вначале даны определения недетерминированного конечного автомата и детерминированного конечного автомата, которые являются центральными объектами изучения. Показана проблема "экспоненциального взрыва" — экспоненциального роста числа состояний детерминированного конечного автомата, принимающего язык, задаваемый набором регулярных выражений, с ростом числа выражений. Описан детерминированный конечный автомат с задержкой (D2FA), являющийся усовершенствованием алгоритма Ахо-Корасик для поиска заданных слов и позволяющий сократить число хранимых переходов для детерминированного конечного автомата. Другой описанный конечный автомат, двойной автомат (DualFА), является гибридом ДКА и НКА и позволяет в некоторых случаях использовать преимущества обоих подходов. Последний описанный автомат, расширенный конечный автомат (XFA и UFA), представляет собой ДКА, который хранит часть информации о текущем состоянии в простых структурах — числовых счетчиках и битовых флагах, тем самым снижая число состояний автомата.

В начале главы 3 показано, что наборы регулярных выражений вида .*R!.*R2.*, где Ri и R2 — регулярные выражения, подвержены проблеме "экспоненциального взрыва". Для ее решения автором предложено проводить "слияние" некоторых пар выражений — заменять некоторые пары выражений .*R1.*R2.* и .*R3.*R4.* на выражения .*(Ri|R3).*(R2|R4)-*- Такой подход приводит к сокращению числа состояний принимающего детерминированного конечного автомата. Однако из-за расширения регулярного

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

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

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

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

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

Благодарности

Автор выражает глубокую благодарность своим научным руководителям — старшему научному сотруднику Алексею Владимировичу Галатенко и доценту Антону Евгеньевичу Панкратьеву за постановку задачи, обсуждение результатов и постоянное внимание к работе. Автор благодарен всем сотрудникам кафедры Математической теории интеллектуальных систем Механико-математического факультета МГУ, в особенности заведующему кафедрой профессору Валерию Борисовичу Кудрявцеву, за поддержку работы и творческую атмосферу на кафедре.

Глава 1

Постановка задачи

Пусть R — регулярное выражение над алфавитом Е, L (R) — регулярный язык, который определяется выражением R, V (L (R)) — приведенный ДКА, принимающий язык L (R), a \V\ — число состояний автомата V. Через Gi (L) обозначим функцию роста регулярного языка L, то есть — число слов длины I, содержащихся в языке L.

Традиционно для проверки принадлежности слова регулярному языку, задаваемому набором регулярных выражений, используются детерминированные конечные автоматы (ДКА). Данный подход характеризуется крайне низкой сложностью вычисления. Однако с ростом числа распознаваемых выражений увеличивается пространственная сложность — число состояний распознающего ДКА. В случае, когда число состояний автомата экспоненциально зависит от количества регулярных выражений, говорят о так называемом "экспоненциальном взрыве". Среди различных видов выражений, приводящих к экспоненциальному взрыву, можно выделить класс выражений вида .*R!.*R2.*, где Ri и R2 — регулярные выражения, а подвыражения .* задают регулярные языки, совпадающие со множеством всех слов (в том числе слова нулевой длины). Отметим, что выражения такого вида часто встречаются на практике, и, например, база сигнатур системы Snort содержит 36 таких выражений, причем детерминированный конечный автомат, распознающий регулярный язык, задаваемый только 11 из 36 выражений, содержит более 1.5 млн. состояний.

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

Выбор критерия "схожести" двух регулярных языков, вообще говоря, зависит от конкретной задачи. Однако в средствах выявления угроз нарушения информационной безопасности, как правило, наборы регулярных выражений — "базы сигнатур" — задают регулярные языки, состоящие из слов обязательных для обнаружения. Поэтому в случае систем информационной безопасности обязательным критерием "схожести" языков является вложенность исходного языка в новый, измененный регулярный язык. В силу невозможности сравнить общее число элементов регулярных языков в общем случае (регулярные языки могут быть бесконечными) предлагается сравнивать значения функций роста для различных длин слов. Пусть L — некоторый регулярный язык, a L' D L — регулярный язык, являющийся его расширением, тогда их "схожесть" па словах длины I можно

Gi (L')

оценить через относительное увеличение языка . . , если Gi (L) > О,

Gi (L)

причем в силу вложенности L в L' верно неравенство ^ ^ ^ ^ 1. Такие

Gi (L)

расширения L' языка L, что L' содержит хотя бы одно слово некоторой длины I, а язык L — нет, признаем "плохими" как языки, расширяющие множество длин принимаемых слов, и не будем рассматривать в дальней-

Gi (£')

шем. Тогда "схожесть" языков LuL Э L можно оценить через max ——7——.

- т Gi (L)

Отметим, что использование такой оценки вполне соответствует очевидному предположению, что если L" I) U — "хорошее" расширение языка L, то язык U более "схож" с языком L, чем язык Lтак как очевидно, что

Gi (L") ^ Gi (L') ^ 1

max ^ max > 1.

т Gi (L) т Gi (L)

Сформулируем центральную задачу, решаемую в данной диссертации.

Задача: Разработка метода замены набора регулярных выражений вида .*R!.*R2.*, которые используются в сетевых системах обнаружения вторжений, для уменьшения автоматной сложности распознавания принадлежности слова регулярному языку, задаваемому данным набором выражений. Оценка относительного изменения числа состояний распознающего детер-

\V{L')\ ,

минированного конечного автомата ^^ (где L — регулярный язык,

задаваемый исходным набором регулярных выражений, а V — язык, задаваемый модифицированными выражениями), которая характеризует эффективность разработанного метода. А также оценка относительного рас-

Gx (V)

ширения регулярного языка max———, которая характеризует вероят-

i>о Gi (L)

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

Глава 2

Модификации конечных автоматов

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

ста) числа состояний. В разделе 2.2.2 на простейшем примере показана данная проблема.

После рассмотрения традиционных конечных автоматов следует описание различных нестандартных автоматов, использование которых призвано смягчить проблему экспоненциального взрыва. Описан детерминированный конечный автомат с задержкой (D2FA), являющийся усовершенствованием алгоритма Ахо-Корасик для поиска заданных слов и позволяющий сократить число хранимых переходов для детерминированного конечного автомата. Другой описанный конечный автомат, двойной автомат (DualFA), является гибридом ДКА и НКА и позволяет в некоторых случаях использовать преимущества обоих подходов. Последний описанный автомат, расширенный конечный автомат (XFA и IIFА), представляет собой ДКА, который хранит часть информации о текущем состоянии в простых структурах — числовых счетчиках и битовых флагах, тем самым снижая число состояний автомата.

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

2.1 Регулярные языки и выражения

Пусть задан конечный алфавит £. Определим над подмножествами Mi и М2 множества всех слов над алфавитом Е операции конкатенации и "звезды Клини" следующим образом:

Список литературы диссертационного исследования кандидат наук Александров, Дмитрий Евгеньевич, 2015 год

Список литературы

1. Cisco 2014 Annual Security Report. — URL: http : / /www. cisco . com/ web/offer/gist_ty2_asset/Cisco_2014_ASR.pdf.

2. Документация системы Snort. — URL: http : / / www . snort . org / documents.

3. Magic Quadrant for Intrusion Prevention Systems / Gartner, Inc. — 2013. — URL: http : //www . gartner . com/technology/reprints . do? id= 1 -10R69E0&ct=131231&st=sb.

4. Документация системы Bro. — URL: http://www.bro.org/.

5. Описание системы L7-filter. — URL: http: //17-f liter. sourcef orge. net/README.

6. Страница аппаратных продуктов компании Cisco. — URL: http : / / www.cisco.com/c/en/us/products/security/intrusion-prevention-system-ips.

7. Magic Quadrant for Intrusion Prevention Systems / Gartner, Inc. — 2014. — URL: http : / /www . gartner . com/technology/reprints . do?id=l -10R69E0&ct=131231&st=sb.

8. Кудрявцев В. В., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. — Москва «Наука», 1985.

9. Martin J. С. Introduction to Languages and the Theory of Computation. — 4-е изд. - New York: McGraw-Hill, 2011.

10. База сигнатур системы Snort. — URL: http: //www. snort. org/snort-rules/.

11. Aho A. V., Corasick M. J. Efficient string matching: an aid to bibliographic search // Communications of the ACM. — 1975. — т. 18, № 6. — с. 333— 340.

12. Algorithms to accelerate multiple regular expressions matching for deep packet inspection / S. Kumar [и др.] // ACM SIGCOMM Computer Communication Review. — 2006. — т. 36, № 4. — с. 339-350.

13. Liu С., Wu J. Fast Deep Packet Inspection with a Dual Finite Automata // Computers, IEEE Transactions on. - 2013. - т. 62, № 2. - с. 310-321.

14. Deflating the big bang: fast and scalable deep packet inspection with extended finite automata / R. Smith [и др.] // ACM SIGCOMM Computer Communication Review. — 2008. — т. 38, № 4. — с. 207—218.

15. Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia / S. Kumar [и др.] // Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems. — ACM. 2007. - c. 155-164.

16. Документация регулярных выражений PCRE. — URL: http://www. pcre.org/pcre.txt.

17. Fast and memory-efficient regular expression matching for deep packet inspection / F. Yu [и др.] // Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems. — ACM. 2006. - c. 93-102.

18. Memory performance and cache coherency effects on an Intel Nehalem multiprocessor system / D. Molka [и др.] // Parallel Architectures and Compilation Techniques, 2009. PACT'09. 18th International Conference on. - IEEE. 2009. - c. 261-270.

19. Becchi M., Crowley P. An improved algorithm to accelerate regular expression evaluation // Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems. — ACM. 2007. — c. 145— 154.

20. Smith REstan С., Jha S. XFA: Faster signature matching with extended automata // Security and Privacy, 2008. SP 2008. IEEE Symposium on. — IEEE. 2008. - c. 187-201.

21. Knuth D. E. On the translation of languages from left to right // Information and control. - 1965. - т. 8, № 6. - с. 607-639.

22. Han Y.-S., Salomaa К., Wood D. State Complexity of Prefix-Free Regular Languages // DCFS. - 2006. - c. 165-176.

Работы автора то теме диссертации

23. Александров Д. Е. Эффективные методы реализации проверки содержания сетевых пакетов регулярными выражениями // Интеллектуальные системы. — 2014. — т. 18, № 1. — с. 37—60.

24. Александров Д. Е. Об уменьшении автоматной сложности за счет расширения регулярных языков // Программная инженерия. — 2014. — № 11. - с. 26-34.

25. Александров Д. Е. Об оценках автоматной сложности распознавания класса регулярных языков // Интеллектуальные системы. — 2014. — т. 18, № 4. - с. 161-190.

26. Александров Д. Е. Об оценках мощности некоторых классов регулярных языков // Дискретная математика. — 2015. — т. 27, вып. 2. — с. 3-21.

27. Александров Д. Е. Программный комплекс RE2FA // Свидетельство о государственной регистрации программы для ЭВМ №2014614857. — 2014.

ние 1

о государственной регистрации программы для ЭВМ

№ 2014614857

Программный комплекс НЕ2ЕА

Правообладатель: Александров Дмитрий Евгеньевич (К11)

Автор: Александров Дмитрий Евгеньевич (ЯП)

Заявка № 2014612653

Дата поступления 27 марта 2014 Г» Дата государственной регистрации в Реестре программ для ЭВМ /2 ЛШЯ 2014 Л

Руководитель Федеральной службы по интеллектуальной собственности

Б. П. Симонов