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

ФГБОУ ВО «Московский государственный университет имени М. В. Ломоносова»

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

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

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

05.13.17 — Теоретические основы информатики

05.13.19 — Методы и системы защиты информации, информационная

безопасность

АВТОРЕФЕРАТ

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

1 7 ДСГ 2015

Москва - 2015

005561428

Работа выполнена на кафедре Математической теории интеллектуальных систем Механико-математического факультета ФГБОУ ВО «Московского государственного университета имени М.В. Ломоносова».

Научные руководители:

Официальные оппоненты:

Ведущая организация:

Галатенко Алексей Владимирович,

кандидат физико-математических наук, ст.н.с.

Панкратьев Антон Евгеньевич,

кандидат физико-математических наук, доцент

Орлов Валентин Александрович,

доктор физико-математических наук, профессор (ФГБОУ ВПО «Московский государственный технический университет имени Н.Э. Баумана», профессор кафедры информационной безопасности) Холоденко Александр Борисович, кандидат физико-математических наук, ООО «Центр прикладной соционики»

ФГБОУ ВПО «Санкт-Петербургский государственный университет»

Защита состоится 23 сентября 2015 г. в 16 час. 45 мин. на заседании диссертационного совета Д.501.002.16 на базе ФГБОУ ВО «Московский государственный университет имени М.В. Ломоносова», по адресу: 119991, Москва, ГСП-1, Ленинские горы д. 1, ФГБОУ ВО МГУ имени М.В. Ломоносова, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в Фундаментальной библиотеке ФГБОУ ВО «Московского государственного университета имени М. В. Ломоносова» (Москва, Ломоносовский проспект, д. 27, сектор А, 8 этаж) и на сайте http://istina.msu.ru/dissertations/9611141/ .

Автореферат разослан 23 августа 2015 г.

Ученый секретарь

диссертационного совета Д.501.002.16 на базе ФГБОУ ВО МГУ, д.ф.-м.н., профессор Корнев Андрей Алексеевич

Общая характеристика работы

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

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

'Cisco 2014 Annual Security Report. URL: http://wvv.cisco.com/web/offer/gist_ty2.asset/ Cisco_2014_ASR.pdf.

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

3Magic Quadrant for Intrusion Prevention Systems / Gartner, Inc. 2013. URL: http://wvv.gartner. com/technology/reprints.do?id=l-10R69EO!tct=131231ftst=sb.

можно отнести также и Bro4, L7-filter5 и аппаратные продукты фирмы Cisco6. Последняя фирма является лидером в области ССОВ по версии компании Gartner в 2014 году7.

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

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

'Описание системы L7-filter. URL: http://17-iilter.sourceforga.net/README.

°Страница аппаратных продуктов компании Cisco. URL: http://www.cisc0.c0m/c/en/u3/ producta/security/intrusion-prevention-system-ips.

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

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

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

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

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

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

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

Aho А. V., Corasick М. J. Efficient string matching: ал 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 [и др.] // ACM SIGCOMM Computer Communication Review. 2006. т. 36, Д» 4. с. 339-350.

Третий способ реализации — обычный ДКА, но с некоторым набором вспомогательных данных, зависящим от конкретной модификации. При этом общей чертой всех модификаций является наличие "быст-ровычислимого" алгоритма изменения этого набора данных при каждом новом входном символе. Так, например, двойной конечный автомат (Dual F А)1^ состоит из ДКА и битового массива. При поступлении на вход нового символа производится обычный переход у ДКА и несколько битовых операций с массивом. После этого осуществляется еще один переход в ДКА в зависимости от значений массива и состояний ДКА. Другие варианты такого типа реализации — расширенный конечный автомат (XFÄ)li и конечный автомат с счетчиками (HFA)15, сочетающие в себе ДКА и набор счетчиков, которые тривиальным образом изменяются в зависимости от входного символа и текущего состояния и предотвращают "экспоненциальный взрыв" числа состояний конечного автомата в случае, когда PCRE-совместимые регулярные выражения16 содержат символы повтора ("*", "+" и "{,}").

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

lsLiu С., 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 [и др.] // ACM SIGCOMM Computer Communication Review. 2008. т. 38, № 4. с. 207—218.

ls 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.

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

l7Fast 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.

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

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

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

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

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

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

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

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

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

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

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

3. Выведена формула для вычисления функции роста языков, задаваемых набором выражений из некоторого подкласса класса выражений вида .*R!.*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 работах автора [1—4] в научных журналах из списка, рекомендованного ВАК РФ.

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

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

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

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

В начале главы 2 дано определение регулярных выражений и языков.

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

• М1М2 = {ûiû2 l'ai € Mi,û'2 e M2} — конкатенация множеств Mi и M2;

• М{ = {Л} U {«1... а„ I п € N; а{ G Мь Vi S ÏTïï} — звезда Клини множества М\, где Л — пустое слово.

Тогда регулярное множество (язык) определяется рекурсивно18:

• 0, {Л} и {а} — регулярные множества, где a S Е;

• если Mi и М2 — регулярные множества, то множества Mi UM2, М1М2 и М{ также являются регулярными множествами.

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

• "0", "Л" и "а" — регулярные выражения, обозначающие регулярные множества 0, {Л} и {а} соответственно, где а € Е;

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

• если и Н2 — регулярные выражения, обозначающие регулярные множества М\ и Мг, то "К1+Н2" (объединение), "й^" (конкатенация) и "Й1*" (звезда Клини) — регулярные выражения, обозначающие регулярные множества М\ и Мг, М\ и М{ соответственно.

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

В дополнение к обозначениям базовых операций над регулярными выражениями далее будут использовать следующие обозначения, которые применяются в РСЛЕ-совместимых регулярных выражениях19:

• "О^!^!... |йц)" — обозначение объединения регулярных выражений Их, Й2> • • •, Кп, которое будет использоваться вместо 'Т^+КгЧ- ■ • • +Яц";

• "." — символ, обозначающий объединение всех символов языка;

• "[а1Э2.. .ап]" — обозначение объединения символов щ, а,2 ... ап;

• "[*а1а2.. ,ап]" — обозначение объединения всех символов языка кроме символов а1, аг... ап;

• "г+" — выражение, обозначающее повтор регулярного подвыражения "г" не менее одного раза;

• "г{т, п}" — выражение, обозначающее повтор регулярного подвыражения "г" не менее т раз и не более п раз.

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

Далее в главе изложены различные модификации конечных автоматов, решающих задачу оптимизации проверки принадлежности сло-

1'Документадия регулярных выражений РСЯЕ. иЛЬ: http://wwv.pcre.org/pcre.txt.

ва регулярному языку, который задается набором регулярных выражений. Вначале даны определения недетерминированного конечного автомата и детерминированного конечного автомата, которые являются центральными объектами изучения. Показана проблема "экспоненциального взрыва" — экспоненциального роста числа состояний детерминированного конечного автомата, принимающего язык, задаваемый набором регулярных выражений, с ростом числа выражений. Описан детерминированный конечный автомат с задержкой (Z)2FЛ), являющийся усовершенствованием алгоритма Ахо-Корасик для поиска заданных слов и позволяющий сократить число хранимых переходов для детерминированного конечного автомата. Другой описанный конечный автомат, двойной автомат [ИисйРА), является гибридом ДКА и НКА и позволяет в некоторых случаях использовать преимущества обоих подходов. Последний описаннь1й автомат, расширенный конечный автомат (ХРА и НЕ А), представляет собой ДКА, который хранит часть информации о текущем состоянии в простых структурах — числовых счетчиках и битовых флагах, тем самым снижая число состояний автомата.

В начале главы 3 показано, что наборы регулярных выражений вида *, где и Е2 — регулярные выражения, подвержены проблеме "экспоненциального взрыва". Для ее решения автором предложено проводить "слияние" некоторых пар выражений — заменять некоторые пары выражений ,*Я1.*Е2.* и .*К3.*114.* на выражения ^(Л^йз).*^^).*. Такой подход приводит к сокращению числа состояний принимающего детерминированного конечного автомата. Однако из-за расширения регулярного языка, который задается набором выражений, появляются ошибки распознавания. Они обусловлены тем, что ДКА принимает не только язык на основе исходного набора выражений, но и некоторые другие слова. Далее в главе 3 для случая алфавита из не менее чем пяти символов представлены неулучшаемые оценки на число состояний конечных автоматов, которые распознают регулярные языки, задаваемые парой выражений или слиянием выражений. Кроме того доказано, что

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

Пусть И. — регулярное выражение над алфавитом Е, Ь (й) — регулярный язык, определяемый выражением Я, V (Ь (К)) — приведенный ДКА, принимающий язык Ь (К), а |У| — число состояний автомата V.

Через (К) обозначим такое наибольшее подмножество Ь(Л), что ни одно из слов из Ь (И.) не является нетривиальным префиксом для слов из I?! (II). Под нетривиальным префиксом в данном случае понимаем префикс, не совпадающий со всем словом. Если Ь (й) содержит пустую строку Л, положим (й) = {Л}.

В теореме 1 автором точно вычислены функции Шеннона числа состояний автоматов приведенного вида, распознающих исходный и модифицированный языки, а также показано, что для любого С 6 (0; 1] П О найдутся такие Из и БЦ, что отношение чис-

ла состояний автоматов, распознающих языки £,(.*(К1|Кз).*(К2|Я4).*) и Ь (.*111.*К2.*) и Ь (.*11з.*1Ц.*), будет равно С.

Теорема 1. Пусть .*Л1.*112-* и ,*11з.*114.* — такие регулярные выражения, что ¡V (1?! (.*КА))| =п> + 2,т^ 1. Тогда:

|К(1(.*Н1.*Н2.*))| =п1 + п2 + 1) |У(£(.*НЗ.*Н4.*))| = пз + П4 + 1,

\У {Ь (.*Й1.*К2.*) и Ь (.кЯз.*^.*))! ^ (П1 + п2) • ("3 + П4) + 1,

|У (I (.*(Е1|Из).*(й2|К4)-*))| < Щ ■ п3 + п2 • п4 + 1.

Причем в случае |Е| > 5 оценки, вообще говоря, неулучшаемы.

Если |Е| ^ 3, то для любого С € (0; 1] ПО) найдутся такие выражения Ль Л2, и ГЦ, что

IV (Ь (.*Л1.*Л2.*) и Ь (.*11з.*Я1.*))Г

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

Для исследования эффективности модификации регулярных выражений была выбрана база сигнатур сетевой системы обнаружения вторжений Snort20. Были взяты 36 выражений вида Ri = .^R^.^R'/.*. Затем для каждой пары выражений RA и Rj (г ф j) были построены автоматы V(L(Ri|R3)) и V(L(.*(R'i|R'j).*(R'/|Rp.*)). Частота появления N определенных значений отношения С = ^(¿(r^r))!— ' хаРактеРизУ~ ющего эффективность предложенного алгоритма, приведена на рис. 1. Видно, что применение данного алгоритма изменения выражений для различных пар выражений в большинстве случаев привело к сокращению числа состояний до 40 — 60%. При этом в одном из случаев число состояний сократилось примерно до 0.5%, а в двух случаях, где у выражений совпали подвыражения R^ или R", число состояний не изменилось. Таким образом, модификация может быть эффективна, но это существенно зависит от выбора пары выражений для изменения.

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

20База сигнатур системы Snort. URL: http://ww. snort. org/snort-mies/.

Рис. 1. Гистограмма эффективности алгоритма

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

Пусть задано п > 2 регулярных выражений видай1 = ,*й2.;;_1.*й2.1.*. Для оценки возможного числа состояний детерминированных конечных автоматов, распознающих обычное объединение регулярных языков

п

и Ь(й1) и объединение языка, задаваемого слиянием двух регулярных

г=1

п

выражений, с набором языков £ (.*(й1|й3).*(й2|й4).*) и и ¿(й1), введем

г=3

две следующих функции Шеннона:

5 (п, 01) = шах

5е (гг, ОТ) = шах

мим*1)

\г=1 ,

V I Ь (.^йз).*^^).*) и и Ь (й1)

г=3

где О? — набор чисел щ ^ 1, ] = 1,2п.

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

Теорема 2. Пусть 01 — набор чисел щ ^ 1, ] — 1,2п, п ^ 2. Тогда верно

неравенство:

Пусть |Е| ^ 3 и набор чисел таков, что любое число щ из него делится на Ьг = [к^щ^ п]. Тогда верно следующее неравенство:

5 (». *) > Ц П +*»>+ (Е (1е1- 1)') П (х1+тг -+1-

Пусть |Е| ^ 4 и все числа из набора не меньше 62 = ■

Тогда верно следующее неравенство:

п ,

П

¿=1 4

"21-1

ь2

+

П2{

Ь2

)

/»2-1 \ П у

"2.-1

+

П2г

V

-1+1.

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

Теорема 3. Пусть ОХ — набор чисел ^ 1, = 1,2п, п ^ 2. Тогда верно неравенство:

(п, ог) ^ (щ • П3 + п2 ■ п4) • Д (п2:-1 + Пи) + 1.

1=3

Пусть |Е| ^ 3 и набор чисел (Я таков, что любое число щ из него делится на Ь\ = ¡"1о§|Е|_1 п]. Тогда верно следующее неравенство:

с с п>\ ^ «з , п2 пА -Л (п2;_1 п2Л

п / ТТ / П2г-1

А.Н »1

Пусть |Е| ^ 4 и все числа из набора 91 не меньше Ъ2 = п].

Тогда верно следующее неравенство:

711 Пз + п2 П4

Ъ2 ь2 ь2 Ь?,

+

^2-1 \ / §(|Е|_2)У V

Пз

Ь2

" / 0(

п / п

¿^Я N

+ П4

П2г

Ъ2

+

I. ь2 \

-1 -11 + 1.

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

Теорема 4. Если |Е| ^ 3, то для любого С е (0; 1] ГКф и тг ^ 2 найдутся такие выражения К1 = .*1121_1.*К21.*, г = 1,п, что

С =

V ( Ь (.*(^|йз).*(Н2|1и).*) и и Ь (й1) __¿=з

V

иьт)

Видно, что функции Шеннона в обоих случаях имеют экспоненциальную асимптотику. Однако "слияние" двух выражений снижает максимум возможного числа состояний распознающего автомата. Так, например, в случае щ = I, г = 1,2гг, верхняя оценка на число состояний при всего лишь одном "слиянии" сокращается почти в два раза — с (21)п + 1

(20" , г,

до —---1- 1. При этом для произвольного рационального числа С из

интервала (0,1] можно подобрать такие регулярные выражения, что от-

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

Детерминированный конечный автомат, принимающий объединение языков, задаваемых только 11 из 36 выражений вида .*Ri.*R2.* из базы системы Snort, имеет свыше 1.5 млн состояний и требует около 1 Гб памяти для хранения. Поэтому для исследования эффективности алгоритма модификации из базы системы Snort были взяты только 11 этих выражений. Затем был построен автомат V ^[Ji ¿(R1)^ и для каждой пары выражений R1 и R3 (г / j) были построены автоматы V I L (.*(R'i|R'j).*(R"|R'j').*) (J L (Rk) ]. Гистограмма значений отно-

V кфг, j )

шения С =

V I L (.*(R/i|Rj).*(R'i'|R").*) U М*к)

\ кфг,] ,

п

характеризующего

Ними1)

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

Рис. 2. Гистограмма эффективности алгоритма

ма изменения выражений для различных пар выражений в большинстве случаев привело к сокращению числа состояний до 50 — 70%. При этом в одном случаев число состояний сократилось до примерно 25%. Таким образом, как и в случае набора из двух выражений, модификация может быть эффективна, но это существенно зависит от выбора пары выражений для изменения.

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

Обозначим через G; (L) = |{а б L | |а| = /}[ функцию роста языка

G\ (L)

L, а через Ci iL) обозначим отношение —;-—-, где т = min Ы.

|Е| • Gm (bV Д 1

Лемма 19. Пусть Ri и R2 — регулярные выражения. Тогда верно равенство:

G, (Iff (.*^2.*)) = |E|'~mi~m2. Gmi (L (Rt)) • Gm, (L (R2)) • где тп\ — min Ы, m2 = min lal.

абЦй,) ■ a6l(Rj)

Обозначим через RC множество регулярных выражений, имеющих вид RjCi * R2c2 * .. .Rp+i, где языки L (Ri) конечны, а L (с^ С Е.

Обозначим через RF множество таких регулярных выражений R. для которых:

1. L (R) не содержит пустых слов;

2. Va е L (R) никакое слово из L (R), кроме а, не содержит подслово а, то есть £* {а} Е* Л L (R) = {а};

3. Va, ß 6 L (R) никакой нетривиальный суффикс а не является префиксом ß, то есть {а} £* Л Е* {ß} = {а} Е* {ß}.

Gi (L)

Обозначим через Ci (L) отношение —г—-, где L — некото-

\Ц1-т-Ст(Ь)

рый язык из £*, a m = min loi.

ocSL

Пусть выражение R € RCilRF и имеет вид RjCi * R2c2 * .. -Rp+i, тогда

(p+1 oo \

П 2 Cj iL (Ri)) I •

»=1 j=mi J

/ p |£| \ ' П IVI t. ) ; где m-i = min |q|, fcj = |L(ci)|. \i=l |E| ~ kij oei(Ri)

В теореме 5 автором получена оценка относительного роста числа

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

Теорема 5. Пусть R1 = ,*R1.*R2.* и R2 = ,*R3.*R4.* — такие регулярные выражения, что подвыражения принадлежат пересечению RCП RF и mi ^ Шз, Ш2 ^ m4, где rrii — min |а|. Пусть 0 < е < 1, тогда для всех

a€b( Ri)

таких I, что тпз + тп^^ I < —, . ..--1 + 2тп*

при г £ {3,4}, верно неравенство:

Gl (L(.*(Ri|R3).*(R2|R4).*))_ 1+

Gi (L (,*Ri.*R2.*) U L (.*R3.*R4.*))

1 (Cmax (LP1 (-*Ri)) • Gmi (L(RQ)

l_e ^ |E|mi_m3 • С?тз (L (R3)) +

(^*(LP/(,*R2)) -Gm2(£(R2))\ + <.Gm4(L(R4)) j-

На практике (алфавит E содержит 256 символов) значения произвеДений • С- (L-/ (.*Ri)) близки к ■ Д ^

и, в случае выражений системы Snort, в большинстве случаев имеют порядок Ю-8 и меньше, то есть, например, при е = Ю-2 максимальная длина слов, на которых верна оценка, имеет порядок свыше 106. Верхняя же оценка относительного роста регулярного языка, предложенная в

теореме 5, для пар выражений системы Snort в более чем трети случаев (при е — Ю-2) не превышает Ю-2.

Пусть задано п регулярных выражений R1 = .*R2i_i.*R2i..*, где выражения Rj (j = 1,2п) принадлежат классу RC П RF. Для того, чтобы оценить относительный прирост числа слов длины не более М при "слиянии" для каждой пары выражений R1, достаточно вычислить значения

при ] = 1,2п и = М ■ тах • и С%ах ■ ЛГЙ) при г = 1, п. При этом значения mj, ЛГ,- и С™ах вычисляются путем простого синтаксического анализа выражений. Тогда для любой пары выражений ^ и если Ш2;-1 Зг т2{ ^ ту и е,- < 1, относительный прирост слов

длины до М при "слиянии" выражений можно оценить сверху как:

Отдельно отметим, что в случае m2i-i > m2j-i и m2i < m2j в исходном регулярном языке L (R1) U L (R3) отсутствуют слова длины m2j-i + m2i, а в языке L (.*(R2i-i|R2j-i).*(R2i|R2j)-*) они присутствуют в количестве Gmi,-, {L (R2j-i)) ■ Gmai (L (R2i)).

Для исследования эффективности применения данного метода оценки, как и в предыдущих случаях, были рассмотрены 36 регулярных выражений вида R1 = .*R2i_1.*R2i.* из базы сигнатур системы Snort.

Для работы с регулярными выражениями и конечными автоматами разработан программный комплекс RE2FA [5] со следующими функциональными возможностями.

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

• Модификация пар регулярных выражений вида ,*Ri.*R2.* в соответствии с предложенным алгоритмом.

4 ^ ^^ Qfax = Стах {1?! (.♦Rj))

(1)

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

Данный программный комплекс предназначен для запуска на ЭВМ под управлением ОС GNU/Linux. Исходный код комплекса написан на языке С и имеет объем 190КБ.

Для каждого из 72 подвыражений Rj были вычислены mj — min |а|,

a€i( Rj)

Ni = GmffRj)) и су» - C™»(L"'(.*Rj)) при j = MÏÏ, а также для каждого из 36 выражений R1 были вычислены значения Si = max (С™х • N21-1, С™1 ■ N2i). В силу того, что для оценок необходимо, чтобы £{ не превосходили 1, максимальная длина M = -J-, для

1 ' которой оценки применимы, не превосходит —. В трех случаях из 36 от-

1

ношение — имеет порядок 103, а значит оценка расширения регулярного

языка при "слиянии" возможна только для относительно коротких слов

длины не более 1000. В остальных 33 случаях отношение — превосходит

¿>1

2.8 • 108. Таким образом, при оценке, например, прироста в случае слов длины до

M = 106 (1МБ данных) значения выражений а = M ■ 5; не превосходят 0.00357. Среди 33 таких выражений 19 выражений принадлежат классу RF. Среди 171 пары этих 19 выражений в 79 случаях минимальные длины mi таковы, что оценка (1) применима. Причем в двух случаях верхняя оценка относительного прироста числа слов не превышает 1, а в 66 случаях не превышает Ю-2.

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

числа состояний, а на оси ординат — реальный относительный прирост числа слов длины 220 при слиянии выражений) показало, что предложен-

» *

«1 а? 03 0.4 0.» 0 6 0.7 0« 0» 1

Рис. 3. Эффективность слияния выражений на словах длины 220 (ШиБ)

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

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

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

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

Заключение

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

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

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

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

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

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

Автор выражает глубокую благодарность своим научным руководителям — старшему научному сотруднику Алексею Владимировичу Гала-тенко и доценту Антону Евгеньевичу Панкратьеву за постановку задачи,

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

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

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

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

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

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

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

Отпечатано в отделе оперативной печати Геологического ф-та МГУ ТиражД^£ экз. Заказ №