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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

2.4 Выводы 40

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение 110

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

• Недетерминированный конечный автомат
• Оценка числа состояний
• Доказательство теоремы 2
• Доказательство теоремы

Введение к работе

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

С развитием технологий передачи данных одним из актуальных направлений информационной безопасности стали исследование и фильтрация сетевого трафика для противодействия реализации угроз деструктивных воздействий на ресурсы информационных систем в открытых компьтерных сетях. Согласно ежегодному отчету корпорации Cisco¹, только в 2013 году число обнаруженных сетевых вторжений, то есть несанкционированных воздействий на ресурсы информационной системы с использованием протоколов межсетевого взаимодействия, увеличилось на 14% по сравнению с предыдущим годом и превысило в среднем 50000 вторжений в день. На настоящее время существует большое число различных сетевых систем обнаружения вторжений (ССОВ), однако наибольшее распространение получили системы, базы сигнатур которых представляют собой наборы регулярных выражений, а вердикт о вредоносности трафика выносится на основании соответствия фильтруемых данных хотя бы одному из регулярных выражений базы. К описанному типу относятся такие известные системы как Snort². Отметим, что по результатам исследований, проведенных компанией Gartner в 2013 году³, компания Sourcefire, разрабатывающая систему Snort, была признана лидером в области ССОВ. К числу других систем подобного назначения

¹ Cisco 2014 Annual Security Report. URL: Cisco_2014_ASR.pdf.

²Документация системы Snort. URL: .

³Magic Quadrant for Intrusion Prevention Systems / Gartner, Inc. 2013. URL: . com/technology/reprints.do?id=l-10R69E0&ct=131231&st=sb.

можно отнести также и Bro , L7-filter и аппаратные продукты фирмы Cisco⁶. Последняя фирма является лидером в области ССОВ по версии компании Gartner в 2014 году⁷.

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

⁴Документация системы Bro. URL: .

⁵Описание системы L7-filter. URL: .

^еСтраница аппаратных продуктов компании Cisco. URL: products/security/intrusion-prevention-system-ips.

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

⁸ Martin J. C. Introduction to Languages and the Theory of Computation. 4-е изд. New York: McGraw-Hill, 2011; Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. Москва «Наука», 1985.

⁹База сигнатур системы Snort. URL: .

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

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

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

¹⁰Martin J. С. Introduction to Languages and the Theory of Computation. 4-е изд. New York: McGraw-Hill, 2011; Кудрявцев В. В., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. Москва «Наука», 1985.

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

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

З

Третий способ реализации — обычный ДКА, но с некоторым набором вспомогательных данных, зависящим от конкретной модификации. При этом общей чертой всех модификаций является наличие "быст-ровычислимого" алгоритма изменения этого набора данных при каждом новом входном символе. Так, например, двойной конечный автомат (DualFА)¹³ состоит из ДКА и битового массива. При поступлении на вход нового символа производится обычный переход у ДКА и несколько битовых операций с массивом. После этого осуществляется еще один переход в ДКА в зависимости от значений массива и состояний ДКА. Другие варианты такого типа реализации — расширенный конечный автомат (XFA)^U и конечный автомат с счетчиками (HFA)¹⁵, сочетающие в себе ДКА и набор счетчиков, которые тривиальным образом изменяются в зависимости от входного символа и текущего состояния и предотвращают "экспоненциальный взрыв" числа состояний конечного автомата в случае, когда PCRE-совместимые регулярные выражения¹⁶ содержат символы повтора ("*", "+" и "{, }").

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

¹³Ыи С, Wu J. Fast Deep Packet Inspection with a Dual Finite Automata // Computers, IEEE Transactions on. 2013. т. 62, № 2. с. 310—321.

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

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

^le Документация регулярных выражений PCRE. URL: .

¹⁷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. с 93-102.

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

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

Для достижения поставленной цели в работе сформулированы и решаются следующие задачи.

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

рый задается данным набором выражений.

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

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

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

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

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

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

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

выражений на регулярных выражениях сетевой системы обнаружения вторжений Snort.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть S — конечный алфавит, Л — пустое слово из языка S , Q — конечное множество, задана функция: Qx(U{A}) - 2Q, q0 Є Q и А С Q, тогда набор V = (Q,Y,,qo,5,A) назовем недетерминированным конечным автоматом (НКА) [9] со множеством состояний Q, функцией перехода 5, инициальным (начальным) состоянием qo и множеством конечных состояний А.

Пусть задан НКА V = (Q,Y,,qo,6,A) и набор состояний S С Q. Тогда назовем Л-замыканием множества S такое множество Л (5 ), что q Є Л (S) тогда и только тогда, когда либо состояние q принадлежит множеству S, либо 3q0 Є S,qi,...,qn Є Q: Мі Є l,n,& Є 6(qi-!,A),q Є 6(qn,A). Для любого состояния q (q Є Q) и строки w (w Є S ) определим функцию 5 (q,w) как множество состояний, достигаемых из состояния q при обработке строки w с помощью автомата V. То есть, Vg Є Q: 5 (q,A) = = A({q}) и Vq Є Q,a Є S ,a є E: 5 (q,aa) = A (\JP =s (q,a) 6 (P a))- ПУСТЬ задан НКА V = (Q,Y,,qo,6,A). Тогда, согласно Теореме Клини [8; 9], множество L = {а а Є Е , 6 (qo} а) П А ф 0}, называемое множеством, пред-ставимым в автомате V, является регулярным языком, а также верно и то, что каждый регулярный язык может быть представлен НКА.

Несмотря на то, что общее количество состояний НКА имеет порядок 0(/), где / — длина соответствующего регулярного выражения (или сумма длин, если НКА реализует набор регулярных выражений), в каждый момент времени нам необходимо хранить не одно текущее состояние, а целое множество состояний. Причем в худшем случае мощность множества текущих состояний будет иметь порядок 0 (Q), где Q — множество состояний НКА, а вычислительная сложность обработки одного символа достигнет

Детерминированный конечный автомат (ДКА) [8; 9] — это набор V = = (Q T, qo 5 A). Здесь, как и в случае НКА, Q — конечное множество состояний, 5: Q х Е — Q — функция перехода, qo Є Q — начальное состояние и А С Q — множество конечных состояний. При этом функция достижимых состояний 5 (q,w) определяется как S (q,a) = 5(q,a), 5 (q, аа) = 5 (6 (q, а) , а), где q Є Q, а Є Е , а Є S. Таким образом, ДКА по сути является НКА без Л-переходов, в котором в каждый момент времени хранится только одно состояние, и, следовательно, время, требуемое на обработку одного входного символа, имеет порядок 0(1). Однако реализация ДКА может потребовать на порядок больше памяти для хранения переходов между состояниями, так как в худшем случае количество состояний имеет порядок 0(2П), где п — число состояний эквивалентного ему недетерминированного конечного автомата [8, с. 96].

В качестве примера рассмотрим ДКА, реализующий поиск по выражению ". a[ab]" (рис. 2.2а). На примере изменений состояний в случае входной последовательности ubaab" можно заметить, что состояния 1 и 2 "независимы" в соответствующем НКА, то есть наличие или отсутствие одного из них в данный момент не означает наличие или отсутствие второго. Поэтому при построении эквивалентного ДКА получаются состояния, соответству ющие различным комбинациям состояний 1 и 2 НКА.

Для построения ДКА, реализующего проверку по т регулярным выражениям, строятся т НКА (обозначим их как Vi = (Qi,Yi,qQ,5i,Ai)), каждый из которых реализует одно регулярное выражение. Далее они объединяются в один НКА V = (Qi U ... U Qm U {qo}, S, qo, 5, A\ U ... U Am), где 6(qo,a) = иГ=і ( 05а) и НЯіа) = $і(Яіа) ПРИ Я Є Qi- Полученный НКА трансформируется в ДКА [9]. В качестве примера можно рассмотреть построение ДКА, реализующего поиск по двум выражениям: ". a[ab]" и ". c. d. " (рис. 2.3).

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

В случае многоядерных систем для обеспечения высокой производительности при минимизации требуемого объема памяти используется выборочное объединение регулярных выражений [17]. То есть т заданных выражений разделяются на к групп, каждая из которых компилируется в один автомат. В силу того, что современные процессоры имеют небольшую (порядка нескольких мегабайт) внутреннюю память (кэш), скорость работы которой в несколько раз превышает скорость доступа ко внешней памяти [18], основным принципом объединения выражений по группам берется ограничение на число состояний ДКА группы — их должно быть столько, чтобы таблица переходов могла полностью вместиться в кэш.

При выделении групп используется "жадный алгоритм". Для этого вводится понятие "взаимодействия" двух регулярных выражений. Регулярные выражения R\ и / "взаимодействуют", если ДКА, реализующий поиск по {R\ +R2), имеет больше состояний, чем в сумме имеют ДКА, реализующие

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

Действительно, тогда переходы из q {) в отличные от q {) состояния не могут осуществляться по символам из Е \ Ei, а переходы из состояния q$ в состояния отличные от него не могут осуществляться по символам ИЗ S \ Е2-Поэтому переходы из q[b которые необходимо сохранить, имеют метки из множества Ei, а сохраняемые переходы из q$ — метки из Е2. По условию Si П S2 = 0, а значит объединение корректно.

Докажем утверждение (4.8) от противного. Пусть найдутся такие q Є Q \ {q } и а Є S \ Ei, что q a = 5 (q ,a) Ф q 0. В силу того, что слова из языка L (Ri) не содержат символ а и q отлично от q ,, состояние q a также отлично от финального. По предположению состояния q a и q {) различны, а так как они являются состояниями приведенного автомата, они отличимы. То есть существует различающее их непустое слово а Є Е , пе реводящее одно из этих состояний в финальное состояние (/, а другое — в некоторое нефинальное. Пусть а переводит q a в финальное состояние. Обозначим через «о слово, переводящее состояние q 0 в состояние q . Тогда, по предположению, слово аоаа должно переводить q 0 в финальное состояние q f, то есть аоаа Є L(. Ri. ) = S L(Ri)S . В силу того, что а Є S \ Si, a -L(Ri) С Е, либо слово ско, либо слово а содержит некоторое слово из L(Ri). Заметим, что слово ао не может содержать слово из L(Ri), так как в противном случае ао переводит q 0 в финальное состояние, которое отлично от q . Следовательно, а содержит слово из L (Ri), то есть принадлежит языку L(. Ri. ). Но тогда слово а переводит состояния q 0 и q a в финальное состояние q f. Противоречие. Пусть а переводит q 0 в финальное состояние, a q a — нет. Если ао — слово, переводящее q 0 в q a, то слово аоаа, по предположению, переводит q 0 в нефинальное состояние. Однако а0аа Є S (S \ S:) L (. . ) = S (S \ S:) S L () S С S L(Ri)S = = L (. Ri. ), а значит аоаа переводит состояние q {) в финальное состояние. Но тогда, так как аоа переводит q 0 в q a, состояние q a переводится словом а в финальное состояние. Противоречие. Значит утверждение (4.8) верно. Утверждение (4.9) доказывается аналогично.

Вернемся к объединению автоматов. Заменим в автомате V переходы из состояний q Є Q \ \q o, q A по символам а Є E2 на переходы в состояния 5" (qQ,a), а переходы из состояний q" Є Q" \ {q o-,q"A по символам а Є Si на переходы в состояния 5 ( о?а) соответственно.

Докаж;ем, что автомат V принимает регулярный язык L (. (RiIR2). ). Заметим, что по построению автомат V неотличим от автомата V на множестве слов (S \ S2) , так как при слиянии были сохранены все переходы автомата V по символам из S \ Х . Аналогично V неотличим от V" на множестве (S \ Si) . Возьмем произвольное слово а из регулярного языка L (. (Rj_ R2) ) Без ограничения общности можно считать, что а Є L (. Ri. ). Пусть а Є (S \ S2) L (Ri) , то есть a = a a", где а Є L (. Ri)n (S \ S2) и а" Є S . Как было замечено выше, V и V неотличимы на множестве (S \ S2) , а значит слово а переводит qo в финальное поглощающее состояние qj. Следовательно, автомат V принимает слово а = а а". Пусть теперь а Є L (Ri) \ ( \ 2) L (Ri) . Тогда слово а можно представить в виде а = а а" , где а Є Е2, а" є ( \ 2) 7 () - Если а переводит qo в финальное состояние, то а = а а" принимается автоматом V. Пусть а переводит qo в некоторое нефинальное состояние q . Заметим, что переходы по символам из 2 ведут только в состояния {qo, qf}UQ"\{q o, q i}, поэтому нефинальное состояние q Є {qo} U Q" \ {q0 ,q i}. Из построения и из утверждения (4.9) следует, что при любом а Є \ 2 переходы из состояний из {qo} U Q" \ {qo,q f} ведут в 5 ( о?а)- Поэтому любое слово из ( \ 2) S переводит состояния из Q" \ {q 0 , q l} туда же, куда и состояние qo- По доказанному выше слово а" Є ( \ 2) L (Ri) переводит состояние qo автомата V в финальное состояние, а значит а" также переводит состояние q в финальное состояние qj. Следовательно, слово а = а1 а" принимается автоматом V.

Пусть теперь слово а принимается автоматом V. Так как единственное финальное состояние является поглощающим, в слове а можно выделить префикс а минимальной длины, принимаемый автоматом V. Докажем, что о! Є L (. (RiIR2). ). В силу того, что а — минимальный префикс слова а, переводящий qo в qj, путь из состояния qo, соответствующий слову а , завершается в финальном состоянии qj, но больше не проходит через него. Но тогда по построению и из утверждений (4.8) и (4.9) следует, что последний символ а , переводящий в финальное состояние qj из нефинального, принадлежит множеству 1 U 2. Без ограничения общности можно считать, что последний символ слова о! принадлежит i. Пусть с/ Є ( \ 2) ь Тогда, так как автоматы V и V неотличимы на множестве ( \ 2) , слово Ы будет приниматься автоматом V , а значит а Є L(. Ri. ), но тогда а Є L(. Ri. ) = (. #!. ). Пусть с/ Є Д( \ 2) ь Тогда а можно представить в виде (З (3", где (З Є 2, (З" Є ( \ 2) ь Аналогично предыдущим рассуждениям слово (3 переводит состояние qo автомата V в некоторое состояние q Є {qo} U Q" \ {q o,q f}, которое переводится словом (3" туда же, куда и состояние qo- Поэтому (3" переводит qo в финальное состояние. В силу неотличимости автоматов V и V на множестве ( \ 2) , слово (3" также принимается автоматом V, то есть (З" Є L(. Ri. ). Тогда а Є E E2-L (. Ri. ) E С L(. Ri. ). Таким образом автомат У принимает язык L (. (R1R2). ).

Докажем неприводимость автомата V. Финальное состояние qj отличимо от остальных состояний как единственное финальное состояние. Из неприводимости автомата V и утверждения (4.8) следует, что исходные состояния Q \ \Q A автомата V отличимы словами из S. В силу того, что при объединении автоматов V и V" в автомат V сохранились все переходы автомата V по символам из Si, состояния {qo} Q \\Qo, Q A также попарно отличимы словами из Si. Аналогично состояния {qo}UQ"\{qQ, q A попарно отличимы словами из S . Докажем отличимость состояний из Q \ {q 0} q A и Q" \ {q o,q A. Как уже было замечено, состояния из Q" \ {q o,q A переводятся непустыми словами из (S \ S2) туда же, куда и состояние qo. То есть состояния из Q" \ {q o}q f} неотличимы от от состояния qo на множестве слов (S \ S2) \ {Л}. Поэтому слова из S С (S \ S2) , отличающие состояния из Q \ {q 0} Q A ОТ СОСТОЯНИЯ qo, также отличают их от состояний из Q" \ {q o,q A- Таким образом автомат V неприводим.

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

Для исследования эффективности применения данного метода оценки были рассмотрены 36 регулярных выражений вида R1 = . R2i_i. R2i- из базы сигнатур системы Snort [10]. Вычисление необходимых параметров, а также построение ДКА для пар выражений и модифицированных выражений осуществлялось с помощью разработанного для этих целей программного комплекса [27]. Для каждого из 72 подвыражений Rj были вычислены rrij = min отношение — имеет порядок 10 , а значит оценка расширения регулярно-го языка при "слиянии" возможна только для относительно коротких слов длины не более 1000. В остальных 33 случаях отношение — превосходит Таким образом, при оценке, например, прироста в случае слов длины до М = 10 (1МБ данных) значения выражений Є{ = М Si не превосходят 0.00357. Среди 33 таких выражений 19 выражений принадлежат классу RF. Среди 171 пары этих 19 выражений в 79 случаях минимальные длины 777,; таковы, что оценка (5.6) применима. Причем в двух случаях верхняя оценка относительного прироста числа слов не превышает 1, а в случаях не превышает 10 .

Кроме того, сравнение результатов применения предложенного метода оценки к 33 выражениям системы Snort, у которых значение — превосхо дит 2.8 10 , и точных значений относительного роста числа слов длины 2 (на рисунке 5.1 для всевозможных пар выражений системы Snort на оси абсцисс отмечены относительные выигрыши в сокращении числа состояний, а на оси ординат — реальный относительный прирост числа слов длины 2 при слиянии выражений) показало, что предложенный метод

Эффективность слияния выражений на словах длины 220 (1МиБ) дает достаточно точные оценки для более широкого класса выражений, нежели RF. Так, среди всевозможных 528 пар выражений оценка осуществима на 239 парах выражений. Из них верхние оценки 25 пар выражений лежат в промежутке от Ю-2 до 1, причем они отличаются в большую сторону от реальных значений для случая слов длины 2 не более чем в 10 раз. Значения оценок для 187 пар не превосходят 10 и отличаются от реальных значений не более чем в 100 раз в большую сторону.

Таким образом, предложенный метод оценки, имеющий низкую вычислительную сложность, на практике позволяет с высокой точностью спро 108 гнозировать относительный прирост числа слов при "слиянии" выражений не только из класса RC П RF, но и из более широкого подкласса из RC.

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

Основные результаты состоят в следующем:

Разработан и программно реализован способ автоматизированной модификации набора регулярных выражений вида . Ri. R2. , используемых в ССОВ, для сокращения автоматной сложности регулярного языка, задаваемого набором выражений.

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

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

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

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

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

Для оценки числа состояний распознающего автомата будет использоваться понятие свободного от префиксов регулярного языка. Данный класс языков впервые ввел Д. Е. Кнут в 1965 году [21]. И, хотя, по теме свобод ных от префиксов языков имеется множество работ, автором настоящей работы получены более строгие оценки на число состояний конечных автоматов, которые распознают регулярные языки, задаваемые выражениями определенного вида, чем в работе [22].

Через LP (R) обозначим такое наибольшее подмножество L (R), что ни одно из слов из L (R) не является нетривиальным префиксом для слов из LP (R). ПОД нетривиальным префиксом в данном случае понимаем префикс, не совпадающий со всем словом. В случае если L (R) содержит пустую строку Л, положим LP? (R) = {Л}.

Докажем, что множество LP (R) является регулярным языком и единственно. Из этого будет следовать, что выражение LP (R) однозначно задает свободный от префиксов язык. Лемма 1. Множество LP (R) является регулярным языком.

Доказательство. Достаточно доказать, что существует ДКА V , принимающий множество LP? (R). То гда из теоремы Клини [8] будет следовать, что LP (R) является регулярным языком.

Пусть V (L (R)) — ДКА, принимающий язык L (R), со множеством финальных состояний А. Добавим в автомат нефинальное поглощающее состояние qs и замкнем в него все состояния из А (рис. 3.3). Докажем, что

Модификация автомата полученный автомат V будет принимать LP (R). Пусть L — множество, принимаемое автоматом V. Тогда из построения следует, что LP (R) С L . Действительно, пусть слово а Є L (R) такое, что L (R) не содержит его нетривиальных префиксов. Тогда путь из начального состояния V (L(R)), соответствующий слову а, заканчивается в одном из финальных состояний, но не проходит ни через одно из них. Из построения V следует, что состояния и переходы на пути слова а остались без изменения, а значит путь в V , соответствующий а, также приведет в финальное состояние. Докажем от противного, что ни одно из слов, принимаемых V, не имеет нетривиальных префиксов из L(R). Действительно, пусть а — такое слово, принимаемое V , что а = а а", где а — минимальный префикс из L (R), а а" — непустое слово. Но так как слово а — минимальный префикс из L (R), то оно не имеет нетривиальных префиксов из L (R), а значит, по доказанному выше, V принимает Ы . Но так как все финальные состояния автомата V имеют переходы только в нефинальное поглощающее состояние, то, если V принимает Ы , то слово а а" не может быть принято, если а" непустое слово. Противоречие.

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

Для доказательства теоремы 1 потребуются следующие леммы. Лемма 3. Пусть R — произвольное регулярное выражение. Тогда ДКА V (LP (R)) имеет всего одно финальное состояние, все переходы из которого ведут в единственное нефинальное поглощающее состояние.

Доказательство. По построению из доказательства леммы 1 и единственности множества (R) (лемма 2) получаем, что автомат V (L (Lpf (R))) имеет нефинальное поглощающее состояние, причем все переходы из фи нальных состояний ведут в него. Таким образом, финальные состояния неотличимы, а значит в приведенном ДКА оно всего одно. Лемма 4. ДКА V (L (. R. )), где R — произвольное регулярное выражение, имеет одно финальное состояние, которое также является поглощающим, и не содержит нефинальных поглощающих состояний.

Доказательство. Заметим, что если слово а принимается конечным автоматом y(L(. R. )), то а/3, где /З Є S , также принимается автоматом. По этой причине любой путь из любого финального состояния проходит только через финальные состояния. Из этого следует, что финальные состояния неотличимы, то есть финальное состояние всего одно и является поглощающим.

Докажем теперь, что нефинальных поглощающих состояний нет. Дей ствительно, пусть такое состояние существует, возьмем слово а Є S , пе реводящее автомат в него, и слово /З Є L(R). Тогда слово а(3 переводит автомат y(L(. R. )) из начального состояния в нефинальное поглощаю щее. Однако а(3 принадлежит языку L (. R. ), а значит слово а(3 должно переводить рассматриваемый автомат в финальное состояние. Противоре

Пусть Vi + 1 1]. Модифицируем автомат Vi, добавив тупиковое состояние и заменив переходы замкнутого финального состояния в себя на переходы в тупиковое состояние. Очевидно, что регулярный язык V полученного автомата V[ входит в L(. R. ). Докажем, что L = IP (. R). Из построения и того факта, что I! С L(. R. ), следует, что I! свободен от префиксов и V С IP? (. R). Докажем, что V 1Э Iff (. R). Действительно, пусть а Є (.R). То гда из определения IP () следует, что для любого нетривиального разбиения a = a a": a . Iff (L(. R)). Как следствие, если рассмотреть путь, соответствующий слову а и начинающийся в начальном состоянии V\, можно заметить, что путь проходит через финальное состояние только один раз — в самом конце (иначе в L (. R. ) присутствует префикс слова из LP (. R)), и, значит, по построению V[ мы получаем, что а Є L . Таким образом, L = Iff (. R). Из минимальности V i следует, что Vi + 1 = \V{\ V2, но по предположению Vi + 1 V2I, а значит \у[\ = \V\\ + 1 = 1]. Аналогично получаем, что автоматы V{ и V изоморфны. В таком случае, если у обоих автоматов убрать нефинальные поглощающие состояния, то получим изоморфные автоматы V\ и V .

Построим автомат V с \Q \ \Q"\ состояниями, где каждому состоянию ставится в соответствие пара состояний q Є Q , q" Є Q". Для произвольного символа а Є Е зададим значение функции переходов как 5 (((/, g"), а) = (6 (q , а) , 6" (q", а)). В качестве начального состояния возьмем состояние (Q.biQo) а в качестве финальных — все состояния вида (q f,q") и {q ,q i), где (/ Є Q , q" Є Q"- Такой автомат, очевидно, будет принимать язык L (В!) U L(R//). Так как финальные состояния V и V" являются поглощающими, то по построению финальные состояния автомата V также переходят только в финальные состояния, и, следовательно, они неотличимы. Тогда в приведенном автомате V будет не больше (\Q \ — 1)- (\Q"\ 1) нефинальных состояний и одно финальное поглощающее состояние, то есть