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

• Автор: Александров, Дмитрий Евгеньевич
• Шифр специальности: 05.13.17, 05.13.19
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Москва
• Количество страниц: 114 с. : ил.

Оглавление
Введение

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 Доказательство теоремы
3.3 Применение алгоритма
4 Модификация произвольного числа выражений
4.1 Оценка числа состояний

4.1.1 Вспомогательные утверждения
4.1.2 Доказательство теоремы
4.1.3 Доказательство теоремы
4.1.4 Доказательство теоремы
4.2 Применение алгоритма
5 Оценка роста языка при модификации выражений
5.1 Способ оценки
5.1.1 Вспомогательные утверждения
5.1.2 Доказательство теоремы
5.2 Применение алгоритма
Заключение
Список литературы
Приложение

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

Пусть имеется п регулярных выражений длины I вида ”.*й1.*й'”, где Д и И[ — различные строки. Тогда количество состояний соответствующего ДКА имеет порядок 0(п12п) [14; 20]. Рассмотрим простейший пример: реализация регулярных выражений ”.*аЬ.*сс1” и ”На рисунке 2.8 изображены ДКА приведенного вида для отдельных выражений ”.*аЬ.*с<1”
Рис. 2.8. Детерминированные автоматы для регулярных выражений ”.*аЬ.*ссГ и ”.*е:
и ”.*е:£и ДКА для объединения этих выражений, у которого все состояния, кроме (2,9) и (4, 7), попарно отличимы. Как видно из схемы ДКА. состояния, соответствующие подвыражениям в середине первого и второго выражений, независимы с состояниями автоматов, реализующих второе и первое выражения соответственно, что и приводит к росту состояний с оценкой 0(п12п) при переходе от НКА к ДКА.
Для устранения экспоненциальной составляющей 2п в расширенном детерминированном конечном автомате [14], а равно и в конечном автомате с счетчиками [15] (так как данные два автомата схожи по принципу работы, далее рассматривается только расширенный автомат), для каждого подвыражения вида исходного выражения ”й.*й'” в памяти хранится один бит, равный единице, если проверенная (обработанная) часть строки соответствует регулярному выражению ”й.*”. Для манипуляций с данными битами к некоторым переходам конечного автомата приписываются инструкции типа “установить бит в 1” и “установить бит в 0”, выполняемые во время перехода. Такое дополнение приводит к тому, что, например, число