Методы и средства оптимизации автоматных моделей поиска информационных структур в потоке данных для реализации на реконфигурируемых вычислительных системах тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Ильченко, Дмитрий Николаевич

• Ильченко, Дмитрий Николаевич
• кандидат наук
• 2014

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

СОДЕРЖАНИЕ

стр.

ВВЕДЕНИЕ

1. АНАЛИЗ МЕТОДОВ И СРЕДСТВ МОНИТОРИНГА СОВРЕМЕННЫХ КОМПЬЮТЕРНЫХ СИСТЕМ

1.1. Классические алгоритмы поиска шаблонов

1.2. Классификация цифровых автоматов

1.3. Реконфигурируемые вычислительные системы

1.4. Принципы структурной организации вычислений при поиске информационных структур в потоке данных на РВС

1.5. Выводы

2. МЕТОДЫ ОПТИМИЗАЦИИ АВТОМАТНЫХ МОДЕЛЕЙ ПОИСКА ИНФОРМАЦИОННЫХ СТРУКТУР

2.1. Векторизация состояний автоматной модели поиска информационных структур с масками

2.2. Комплексная оптимизация автоматной модели поиска информационных структур с масками

2.3. Инициализация состояний и векторизация изоморфных подграфов

2.4. Выводы

3. ПРОГРАММНЫЕ СРЕДСТВА СИНТЕЗА АВТОМАТНЫХ МОДЕЛЕЙ ПОИСКА ИНФОРМАЦИОННЫХ СТРУКТУР В ПОТОКЕ ДАННЫХ ДЛЯ РЕАЛИЗАЦИИ НА РВС

3.1. Общая структура и алгоритмы работы транслятора

3.2. Общая структура и алгоритмы работы синтезатора

3.3. Графическая оболочка

3.4. Реализация автоматных моделей поиска в виде схемотехнических примитивов на РВС с помощью синтезатора Fire ¡Constructor

3.5. Выводы

4. РЕШЕНИЕ ЗАДАЧ ПОИСКА ИНФОРМАЦИОННЫХ СТРУКТУР

НАРВС

4.1. Задача поиска ключевых слов

4.2. Задача поиска битовых последовательностей

4.3. Задача сигнатурного анализа данных

4.4. Выводы 154 ЗАКЛЮЧЕНИЕ 156 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 158 ПРИЛОЖЕНИЕ 1 168 ПРИЛОЖЕНИЕ 2

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

ВВЕДЕНИЕ

Актуальность темы. В конце XX века произошел резкий скачок в развитии компьютерных технологий, что привело к массовому использованию компьютерных сетей. Сегодня сетевые технологии обеспечивают скорость передачи информации до десятков гигабит в секунду. Для анализа передаваемой информации и состояния сети используются различные средства мониторинга. В общем случае их можно разделить на две группы: средства анализа работоспособности сетей и средства защиты от вредоносного воздействия [1]. К средствам защиты относятся системы обнаружения вторжений, системы предотвращения вторжений и сетевые экраны [2-5]. Их основными функциями являются: защита от несанкционированного проникновения, защита от вредоносного программного обеспечения, контроль активности пользователей сети и др.

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

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

Наиболее эффективным в данном случае является использование специализированных вычислителей [6,7] на основе заказных специализированных интегральных схем (ASIC) [8], поскольку такие микросхемы изготавливаются производителями аппаратного обеспечения «под заказ» для выполнения конкретной задачи и имеют максимально высокую производительность. Однако такие микросхемы дороги в

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

Более целесообразным является использование реконфигурируемых вычислительных систем (РВС) [9,10] на базе программируемых логических интегральных схем (ПЛИС) [11]. За счет адаптации архитектуры вычислителя под структуру решаемой задачи такие системы позволяют получить высокую реальную производительность при решении сильносвязных задач. Если в кластерных системах [12,13] задача представляет собой набор процедур, которые последовательно выполняются на разных процессорах, то в РВС все вычислительные устройства аппаратно объединены для реализации информационного графа решаемой задачи. Это позволяет на одной аппаратной платформе решать задачи различных предметных областей с высокой производительностью.

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

Для повышения функциональных возможностей и гибкости поиска при формировании информационных структур могут применяться маски. Их использование усложняет логическую структуру автоматных моделей, что приводит к необходимости их минимизации. Традиционные алгоритмы оптимизации направлены на минимизацию числа внутренних состояний автоматов с целью сокращения элементов памяти на их реализацию [15,16,17]. При реализации цифровых автоматов на ПЛИС в качестве элементов памяти используются триггеры [18], а условия переходов и выходные функции реализуются с помощью логических таблиц истинности. Важной особенностью архитектуры последних семейств ПЛИС является наличие на одну логическую таблицу истинности двух элементов памяти (триггеров), поэтому актуальна минимизация автоматной модели, направленная не на снижение количества триггеров, а на сокращение логических элементов.

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

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

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

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

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

Для достижения указанной цели решены следующие задачи:

1) проведен анализ классических алгоритмов поиска, традиционных методов минимизации и синтеза цифровых автоматов для реализации на РВС;

2) разработаны принципы структурной организации вычислений для обеспечения поиска информационных структур в потоке данных в реальном масштабе времени;

3) разработаны методы оптимизации автоматных моделей поиска информационных структур, направленные на повышение удельной производительности путем сокращения аппаратных ресурсов РВС, используемых для их реализации;

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

5) выполнен синтез вычислительных структур поиска на РВС и проведен анализ эффективности разработанных методов оптимизации автоматных моделей.

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

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

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

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

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

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

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

Практическая значимость. На основании предложенных методов создано программное обеспечение для генерации и оптимизации автоматных моделей поиска информационных структур в потоке данных в режиме реального времени на РВС. Разработанное программное обеспечение сокращает время оптимизации и отладки автоматных моделей поиска. Разработанные методы позволяют минимизировать до 90% аппаратного ресурса в среднем до 30%.

Использование результатов работы. Материалы диссертации использовались при выполнении ряда НИОКР, среди которых можно выделить следующие:

- «Исследование и разработка программного обеспечения и испытания экспериментального образца унифицированного базового модуля многопроцессорной системы со структурной реализацией параллельной обработки информации», итоговый отчет о НИР, № гос. per. 01.2.00613841, Таганрог, НИИ МВС ТРТУ, шифр «ССПВ-Т2», 2006 г.;

- «Разработка эскизной конструкторской документации на макет базового модуля модульно-наращиваемой мультипроцессорной системы (МНМС) на основе реконфигурируемой элементной базы и программных средств поддержки масштабируемых программ для решения задач обработки информации и управления в реальном времени на различных конфигурациях МНМС, в том числе при деградации вычислительного ресурса», отчет о НИР, № гос. per. 01.2.00611470, инв. № 02.2.00606581, Таганрог, НИИ МВС ТРТУ, шифр «Триада», 2006 г.;

- «Разработка и исследование параллельных и конвейерных реализаций задач различных предметных областей на гетерогенных МВС», итоговый отчет о НИР, № гос. per. 01.2007 02728, инв. № 0220.0800098, Таганрог, НИИ МВС ЮФУ, шифр «Карнавал», 2007 г.;

- «Создание семейства высокопроизводительных многопроцессорных вычислительных систем с динамически перестраиваемой архитектурой на основе реконфигурируемой элементной базы и их математического обеспечения для решения вычислительно трудоемких задач», итоговый отчет об ОКР, № гос. per. 01.2.007 05707, Таганрог, НИИ МВС ЮФУ, шифр «Большая Медведица», 2007 г.;

- «Разработка методов и инструментальных систем для анализа эффективности работы параллельных программ и суперкомпьютеров. Этап 1. Выбор направления исследований. Теоретические исследования

поставленных перед НИР задач», отчет о НИР, № гос. per. И110519102540, Таганрог, НИИ МВС ЮФУ, шифр «Рамка», 2011 г.;

- «Разработка теоретических основ построения сверхвысокопроизводительных реконфигурируемых вычислительных систем», отчет о НИР, № гос. per. 01201153442, Таганрог, НИИ МВС ЮФУ, шифр «Маска», 2012 г.;

- «Разработка и исследование принципов построения программных средств для высокопроизводительных реконфигурируемых вычислительных комплексов», отчет о НИР, № гос. per. 01201153442, инв. № 02201254407, Таганрог, НИИ МВС ЮФУ, шифр «Маска-2», 2013 г.

Апробация работы. Основные результаты, представленные в диссертации, докладывались и обсуждались на всероссийских и международных научно-технических конференциях: VII, VIII, IX, X ежегодных научных конференциях студентов и аспирантов базовых кафедр ЮНЦ РАН, Ростов-на-Дону; международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы (МВУС-2009)», с. Дивноморское, Геленджик, 2009 г.; 2-й Всероссийской научно-технической конференции «Суперкомпьютерные технологии (СКТ-2012)», с. Дивноморское, Геленджик, 2012 г.; 6-й Всероссийской мультиконференции по проблемам управления МКПУ-2013, с. Дивноморское, Геленджик, 2013 г.; международной научно-практической конференции «Интеграция науки и практики, вопросы модернизации, проблемы совершенствования в экономике, проектном менеджменте, образовании, юриспруденции, языкознании, культурологии, экологии, зоологии, химии, биологии, медицине, психологии, политологии, филологии, философии, социологии, информатике, технике, математике, физике», Санкт-Петербург, 27-28 февраля 2014 г.; всероссийском совещании по проблемам управления (ВСПУ-2014), Москва, 2014 г.

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

1. Ильченко, Д.Н. Применение операции векторизации состояний для синтеза цифровых автоматов [Электронный ресурс] / Д.Н. Ильченко // «Инженерный вестник Дона», 2013, №4 - Режим доступа: http://www.ivdon.ru/magazine/archive/n4y2013/2028 (доступ свободный) -Загл. с экрана. - Яз. рус. ISSN 2073-8633 (ведущий рецензируемый журнал, входит в перечень ВАК);

2. Ильченко, Д.Н. Комплексная минимизация цифровых автоматов при решении задачи поиска шаблонов [Текст] / И.И. Левин, Д.Н. Ильченко // Вестник компьютерных и информационных технологий. - М.: Машиностроение, 2014. - №5. - С. 3-7 (ведущий рецензируемый журнал, входит в перечень ВАК);

3. Ильченко, Д.Н. Преобразования структуры автоматов поиска шаблонов с масками [Текст] / Д.Н. Ильченко // Известия ЮФУ. Технические науки. - Таганрог: Изд-во ТТИ ЮФУ, 2014. - №6(155), С. 108-116 (ведущий рецензируемый журнал, входит в перечень ВАК);

4. Ильченко, Д.Н. Организация доступа к вычислительным устройствам в реконфигурируемых вычислительных системах с высокой степенью распараллеливания [Текст] / Д.Н. Ильченко, Ю.И. Доронченко, М.К. Раскладкин // Материалы Международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы» (МВУС-2009). - Таганрог: Изд-во ТТИ ЮФУ, 2009.- Т.1. - С.43-45;

5. Ильченко, Д.Н. Сигнатурный анализ множества каналов Ethernet с помощью алгоритма Ахо-Корасик с использованием реконфигурируемых вычислителей [Текст] / Д.Н. Ильченко // Труды молодых ученых ЮФУ и ЮНЦ РАН «Высокопроизводительные вычислительные системы». -Таганрог: Изд-во ТТИ ЮФУ, 2011. - С.60-63.;

6. Ильченко, Д.Н. Устройство поиска битовых последовательностей в потоке данных, передаваемых по сети Ethernet [Текст] / Д.Н. Ильченко //

Труды молодых ученых ЮФУ и ЮНЦ РАН «Высокопроизводительные вычислительные системы» Выпуск 2. - Таганрог: Изд-во ЮФУ, 2012. - С.12-15;

7. Ильченко, Д.Н. Реализация алгоритма Ахо-Корасика для поиска сигнатур в потоке данных в сети Ethernet с использованием реконфигурируемых вычислительных систем [Текст] / Д.Н. Ильченко // Тезисы докладов Седьмой ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН 11-25 апреля 2011 года. - Ростов-на-Дону: Изд-во ЮНЦ РАН, 2011. - С. 121-122;

8. Ильченко, Д.Н. Устройство для лексемного анализа данных в сети Ethernet в режиме реального времени [Текст] / Д.Н. Ильченко // Тезисы докладов Восьмой ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН 11-25 апреля 2012 года. -Ростов-на-Дону: Изд-во ЮНЦ РАН, 2012. - С. 125-126;

9. Ильченко, Д.Н. Реализация поиска ключевых слов в текстовых файлах, передаваемых по сети Ethernet [Текст] / Д.Н. Ильченко // Материалы Второй Всероссийской научно-технической конференции СКТ-2012. -Таганрог: Изд-во ТТИ ЮФУ, 2012. - С.118-120;

10. Ильченко, Д.Н. Поиск символьных структур в сети Ethernet [Текст] / Д.Н. Ильченко // Сборник трудов Девятой ежегодной научной конференции студентов и аспирантов базовых кафедр, 15-20 апреля 2013 г., г. Ростов-на-Дону. - Ростов н/Д: Изд-во ЮНЦ РАН, 2013. С. 106-107;

11. Ильченко, Д.Н. Доступ к реконфигурируемым вычислительным системам через ethernet-канал [Текст] / Д.Н. Ильченко // Труды 6-й Всероссийской мультиконференции по проблемам управления МКПУ-2013, 30 сентября-5 октября 2013 г., с. Дивноморское, Геленджик, Россия. — Т. 4. — Ростов-на-Дону: Изд-во ЮФУ, 2013. - С. 153-156;

12. Ильченко, Д.Н. Минимизация логической структуры цифрового автомата для поиска шаблонов [Текст] / Д.Н. Ильченко, А.К. Мельников // Сборник научных статей по итогам международной заочной научно-

практической конференции "Интеграция науки и практики, вопросы модернизации, проблемы совершенствования в экономике, проектном менеджменте, образовании, юриспруденции, языкознании, культурологии, экологии, зоологии, химии, биологии, медицине, психологии, политологии, филологии, философии, социологии, информатике, технике, математике, физике", Санкт-Петербург, 27-28.02.2014. - СПб: Изд-во «КультИнформПресс», 2014. - С. 75-77. ISBN: 978-5-8392-0447-8. (РИНЦ);

13. Ильченко, Д.Н. Методы оптимизации автоматных моделей поиска шаблонов [Текст] / Д.Н. Ильченко, А.К. Мельников // Труды XII Всероссийского совещания по проблемам управления (ВСПУ-2014). - М.: Изд-во ИПУ им. В.А. Трапезникова РАН, 2014. - С.8697 - 8701;

14. Ильченко, Д.Н. Оптимизация цифровых автоматов поиска шаблонов [Текст] / Д.Н. Ильченко // Труды Десятой юбилейной ежегодной научной конференции студентов и аспирантов базовых кафедр, 15-20 апреля 2014 г., г. Ростов-на-Дону. - Ростов н/Д: Изд-во ЮНЦ РАН, 2014. - С. 63-64. ISBN 978-5-4358-0085-2;

15. Ильченко, Д.Н. Оптимизация синтеза цифровых автоматов для поиска шаблонов с масками [Текст] / Д.Н. Ильченко, А.К. Мельников // Труды Ш-ей международной заочной научно-практической конференции "Академическая наука - проблемы и достижения", Москва, 20-21.02 2014. М., 2014. - С. 149-150. ISBN: 978-1496060730.

По результатам исследований также получено 2 свидетельства о государственной регистрации программ для ЭВМ:

1. Ильченко, Д.Н. Программа синтеза и оптимизации цифровых автоматов для мониторинга компьютерных сетей / Ильченко Д.Н., Гудков В.А., Бовкун A.B. // Свидетельство об официальной регистрации программы для ЭВМ № 2014617297, РФ. Зарегистр. в Реестре программ для ЭВМ 16.07.2014 г. Правообладатель: федеральное государственное автономное образовательное учреждение высшего профессионального образования «Южный федеральный университет»;

2. Ильченко, Д.Н. Генератор файлов топологических ограничений для вычислительных структур и интерфейсов на ПЛИС / Ильченко Д.Н., Дордопуло А.И., Доронченко Ю.И. // Свидетельство об официальной регистрации программы для ЭВМ № 2013619581, РФ. Зарегистр. в Реестре программ для ЭВМ 10.10.2013 г. Правообладатель: федеральное государственное автономное образовательное учреждение высшего профессионального образования «Южный федеральный университет».

Положения, выдвигаемые на защиту:

1) применение разработанных методов (метод векторизации вершин состояний, метод векторизации вершин графа, метод векторизации изоморфных подграфов) позволяет сократить аппаратные затраты на реализацию автоматных моделей поиска информационных структур в потоке данных на РВС, что повышает удельную производительность;

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

Результаты, выносимые на защиту:

1) метод векторизации вершин состояний цифрового автомата, позволяющий сократить аппаратный ресурс РВС при реализации автоматных моделей поиска, что обеспечивается минимизацией структуры графа автомата путем замены упорядоченного множества вершин состояний вершиной-массивом;

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

3) метод инициализации состояний, позволяющий применять разработанные методы оптимизации структуры автоматной модели при ее реализации на РВС, что обеспечивается введением в структуру автоматной

модели поиска дополнительного устройства для хранения информации о текущем объекте поиска;

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

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

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

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

задач необходимы новые методы и средства для создания автоматных моделей поиска на РВС.

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

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

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

Синтезатор осуществляет отображение оптимизированной автоматной модели или объектной схемы в виде схемотехнических примитивов для дальнейшей передачи файла описания в синтезатор схемотехнических решений Fire ¡Constructor.

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

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

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

Представлена структура интерфейса взаимодействия между Ethernet-каналом и вычислительными ПЛИС.

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

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ источников

1. Норткарт С., Новак Д. Обнаружение нарушений безопасности в сетях, 3-е изд.: Пер. с англ. - М.: Издательский дом «Вильяме», 2003. - 448 с.

2. Аграновский A.B., Хади P.A. Системы обнаружения компьютерных угроз [электронный ресурс]. - Режим доступа: http://www.nestor.minsk.by/sr/2008/05/sr80513 .html.

3. Галицкий A.B., Рябко С.Д., Шаньгин В.Ф. Защита информации в сети - анализ технологий и синтез решений. - М.: ДМК Пресс, 2004.- 616 с.

4. Каляев И.А., Левин И.И., Кухаренко А.П., Капустян С.Г. Информационно-телекоммуникационные и компьютерные технологии, устройства и системы: состояние и перспективы развития в Южном федеральном университете / Под. ред. И.А. Каляева, Кухаренко А.П.:. -Ростов-на-Дону: Изд-во ЮФУ, 2010. - 520 с.

5. Корниенко А.А, Слюсаренко И.М. Системы и методы обнаружения вторжений: современное состояние и направления совершенствования [электронный ресурс]. - Режим доступа: http://citforum.rU/security/internet/ids_overview/#5.

6. Жан М. Рабаи, Ананта Чандракасан, Боривож Николич Цифровые интегральные схемы. Методология проектирования - 2-е изд. - М.: Вильяме, 2007.-912 с.

7. Зиатдинов С.И., Осипов Л.А. Проектирование специализированных вычислителей цифровой обработки сигналов: Учебное пособие / СПбГУАП. СПб, 2002. - 75 с.

8. ASIC basics tutorial [электронный ресурс]. - Режим доступа: http://www.radio-electronics.com/info/data/semicond/asic/asic.php.

9. Каляев A.B. Многопроцессорные системы с перестраиваемой архитектурой: концепции развития и применения [Текст] / A.B. Каляев, И.И. Левин // Наука - производству, 1999. - № 11. - С. 11-19.

10. Каляев A.B. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений [Текст]: монография / A.B. Каляев, И.И. Левин; под ред. A.B. Каляева. - М.: Янус-К, 2003. - 380 с.

11. Программируемая пользователем вентильная матрица [электронный ресурс]. - Режим доступа: http://ru.wikipedia.org/wiki/FPGA.

12. Гергель В.П. Технологии построения и использования кластерных систем / Интернет университет информационных технологий intuit.ru -[электронный ресурс]. - Режим доступа: http://www.intuit.ru/department/supercomputing/tbucs/

13. Воеводин, Вл.В. «Вычислительное дело и кластерные системы» [Текст]: монография / Вл.В. Воеводин, С.А. Жуматий. - М.: Изд-во МГУ, 2007.- 150 с.

14. Поликарпова Н.И., Шалыто A.A. Автоматное программирование -СПб.: СПбГПУ, 2008. - 227с.

15. Кудрявцев В.Б., Алешин C.B., Подколзин A.C. Введение в теорию автоматов - М.: Наука, 1985. - 320с.

16. Белоусов А.И., Ткачев С.Б. Дискретная математика [Текст]. - М.: Издательство МГТУ им. Н.Э. Баумана, 2001. - 744 с.

17. Лазарев В. Г., Пийль Е. И. Синтез управляющих автоматов. — 3-е изд., перераб. и доп. М.: Энергоатомиздат, 1989. - 328 с.

18. Матюшин О.Т. Архитектура и функционирование ПЛИС: Учебное пособие. - М.: Издательство МЭИ, 2003. - 23с.

19. Каляев И. А., Левин И.И. Семейство многопроцессорных вычислительных систем с динамически перестраиваемой архитектурой / Труды международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2008)» (Санкт-Петербург, 28 января - 1 февраля 2008 г.). - Челябинск: Изд. ЮУрГУ, 2008. - 118-124 с.

20. Каляев И.А., Левин И.И., Семерников Е.А., Шмойлов В.И. Реконфигурируемые мультиконвейерные вычислительные структуры. -Ростов н/Д: Изд-во ЮНЦ РАН, 2008. - 320 с.

21. Brute Force algorithm [электронный ресурс]. - Режим доступа: httpV/www-igm.univ-mlv.fiy-lecroq/string/nodeS.html.

22. Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология / Пер. с англ. И.В. Романовского. — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с.

23. Альсведе Р., Вегенер И. Задачи поиска. - М.: Мир, 1982. - 368 с.

24. Kurtz, St. Fundamental Algorithms For A Declarative Pattern Matching System [Текст]. - Bielefeld:. University Bielefeld, 1995. - 238 c.

25. Вирт, H. Алгоритмы и структуры данных [Текст].- М:. Мир, 1989. -

360 с.

26. Boyer-Moore algorithm [электронный ресурс]. - Режим доступа: http://www-igm.univ-mlv.fr/~lecroq/string/nodel4.html.

27. Шень А. Программирование: теоремы и задачи [Текст]. - М.: Московский центр непрерывного математического образования, 1995.

28. Apostolico A., Galil Z. Pattern Matching Algorithms - New York: Oxford University Press; 1997. - 377 p.

29. Обзор алгоритмов поиска максимальной подматрицы [электронный ресурс]. - Режим доступа: http://software.intel.com/ru-ru/articles/max_subarray_problem.

30. Кормен, Т. Алгоритмы: построение и анализ [Текст]/ Т. Кормен, Ч. Лейзерсон, Р. Ривест - М.: МЦНМО, 2002. М.: МЦНМО, 2002.

31. Alfred V. Aho and Margaret J. Corasick Efficient String Matching: An Aid to Bibliographic Search [Электронный ресурс]. - Режим доступа: http://www.ece.ncsu.edu/asic/ece792A/2009/ECE792A/Readings_files/p333-aho.pdf (доступ свободный) - Загл. с экрана. - Яз. англ.

32. Ахо, Альфред Структура данных и алгоритмы [Текст]. - М.: Издательский дом «Вильяме», 2000. - 384 с.

33. Лобанов В.И. Азбука разработчика цифровых устройств [Текст]. -М.: Горячая линия - Телеком, 2001. - 192 с.

34. Хопкрофт Д., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений: пер. с англ. 2-е изд. М.: Вильяме, 2002. -528 с.

35. Гилл, Арт. Введение в теорию конечных автоматов [Текст]. - М., 1966.-272 с.

36. Савельев А. Я. Прикладная теория цифровых автоматов. - М.: Высшая школа, 1987. -272с.

37. Захаров Н.Г., Рогов В.Н. Синтез цифровых автоматов: Учебное пособие. - Ульяновск: УлГТУ, 2003. - 135 с.

38. Триханов A.B. Теория автоматов: Учебное пособие Томский политехнический университет, 1999.

39. Глушков В.М. Синтез цифровых автоматов - М.: Физматгиз; 1962. -

476 с.

40. Евреинов, Э. В. Цифровые автоматы с настраиваемой структурой [Текст] : однород. среды / Э. В. Евреинов, И. В. Прангишвили. - М. : Энергия, 1974. - 240 с. : ил. - Библиогр.: с. 233-238. - 0.79 р. РУБ 6П2.15В24.

41. Каляев A.B. Многопроцессорные системы с программируемой архитектурой. - М.: Радио и связь, 1984. - 240с.

42. Шалыто A.A., Туккель Н.И. От тьюрингова программирования к автоматному [электронный ресурс]. - Режим доступа: http://is.iiTno.ru/download/turing.pdf (Дата обращения: 24.06.2014).

43. Марченков С.С. Конечные автоматы. - М.: Физмалит, 2008. - 56с.

44. Смирнов А.Д. Архитектура вычислительных систем: Учебное пособие для вузов. - М.: Наука, 1990. - 320 с.

45. ПЛИС [электронный ресурс]. - Режим доступа: https://m.wildpedia.org/wiki/roniC

46. Xilinx [электронный ресурс].- Режим доступа: http://www.xilinx.com

47. Altera [электронный ресурс]. - Режим доступа: http://www.altera.com

48. Acronix Semiconductor Corp. [электронный ресурс]. - Режим доступа: http://www.achronix.com.

49. Actel Microsemi [электронный ресурс]. - Режим доступа: http://www.actel.com

50. Virtex-6 FPGA Configurable Logic Block User Guide [электронный ресурс]. - Режим доступа: www.xilinx.com/support/documentation/user_guides/ug364.pdf

51. Долинский М. «Горячие темы» EDA-индустрии // Компоненты и технологии. 2004. - №8.

52. Вычужанин В. Состояние рынка и расширение сферы применения ПЛИС // Компоненты и технологии. 2004. - №5.

53. Тарасов И. Обзор архитектуры ПЛИС семейства Virtex-5 // Компоненты и технологии. 2006. - №9.

54. Cray Supercomputer Company [электронный ресурс]. - Режим доступа: http://www.cray.com/Home.aspx

55. Silicon Graphics [электронный ресурс]. - Режим доступа: http://www.sgi.com/

56. Черняк Л.А. НРС - конец мелового периода. [Текст] / «Открытые системы», № 03, 2010.

57. ФГУП "НИИ "Квант" [электронный ресурс]. - Режим доступа: http://www.rdi-kvant.ru

58. Nallatech [электронный ресурс]. - Режим доступа: http://www.nallatech.com

59. SciEngines massively parallel computing [электронный ресурс]. -Режим доступа: http://www.sciengines.com

60. Dini Group [электронный ресурс]. - Режим доступа: http://www.dinigroup.com

61. Alpha Data [электронный ресурс]. - Режим доступа: http://www.alpha-data.com

62. ООО НПО «Роста» [электронный ресурс]. - Режим доступа: http://www.rosta.ru

.63. НИИ МВС ЮФУ [электронный ресурс]. - Режим доступа: http://www.mvs.sfedu.ru

64. «Модульно-наращиваемая многопроцессорная вычислительная система с программируемой архитектурой на основе реконфигурируемой элементной базы», Итоговый отчет об ОКР, № гос. per. 0122.0510630, инв. № 0220.0601017,Таганрог, НИИ МВС ТРТУ, шифр «Медведь», 2006 г.

65. «Создание семейства высокопроизводительных многопроцессорных вычислительных систем с динамически перестраиваемой архитектурой на основе реконфигурируемой элементной базы и их математического обеспечения для решения вычислительно трудоемких задач», Итоговый отчет об ОКР, № гос. per. 01.2.007 05707, инв. № 0220.0900079, Таганрог, НИИ МВС ЮФУ, шифр «Большая Медведица», 2007 г.

66. «Разработка теоретических основ построения сверхвысокопроизводительных реконфигурируемых вычислительных систем», Отчет о НИР, № гос. per. 01201153442, Таганрог, НИИ МВС ЮФУ, шифр «Маска», 2012 г.

67. Научно-исследовательский центр супер-ЭВМ и нейрокомпьютеров [электронный ресурс]. - Режим доступа: http://superevm.ru

68. Левин, И.И. Многопроцессорная система с программированием архитектуры на нескольких уровнях [Текст] / И.И. Левин // Труды Первой Всероссийской научной конференции «Методы и средства обработки информации». - Москва: Издательский отдел ф-та вычислительной математики и кибернетики МГУ им. М.В. Ломоносова, 2003. - С. 111-118.

69. Левин И.И. Структурно-процедурное программирование. Тезисы докладов Международной научной конференции "Искусственный интеллект 2000", п. Кацивели, 2000. - С. 148-150.

70. Каляев A.B., Левин И.И. Структурно-процедурная организация параллельных вычислений. // Труды межд. конф. "Параллельные вычисления и задачи управления (РАСО'2001)". - М: ИПУ РАН им. В.А.Трапезникова, 2001.-Т.5.-С.112-119.

71. Биргкоф Г., Барти Т. Современная прикладная алгебра. - М.: Мир, 1976.-400с.

72. Царев Ф.Н., Шалыто A.A. О построении автоматов с минимальным числом состояний для задачи об «Умном муравье» [электронный ресурс] -URL: http://is.ifmo.ru/download/ant_ga_min_number_of_state.pdf (Дата обращения 24. 06. 2014).

73. Мельников Б.Ф., Мельникова A.A. Многоаспектная минимизация недетерминированных конечных автоматов (Часть I. Вспомогательные факты и алгоритмы) // Изв. вузов. Поволжский регион. Физико-математические науки. 2011. № 4. С. 59 - 69.

74. Мельников Б.Ф., Сайфуллина М.Р. О некоторых алгоритмах эквивалентного преобразования недетерминированных конечных автоматов // Изв. вузов. Математика. 2009. № 4. С. 67 - 71.

75. Ильченко, Д.И. Применение операции векторизации состояний для синтеза цифровых автоматов [Электронный ресурс] / Д.Н. Ильченко // «Инженерный вестник Дона», 2013, №4 - Режим доступа: http://www.ivdon.ru/magazine/archive/n4y2013/2028 (доступ свободный) -Загл. с экрана. - Яз. рус. ISSN 2073-8633.

76. Ильченко, Д.Н. Комплексная минимизация цифровых автоматов при решении задачи поиска шаблонов [Текст] / И.И. Левин, Д.Н. Ильченко // Вестник компьютерных и информационных технологий. — М.: Машиностроение, 2014. - №5. - С. 3-7.

77. Ильченко, Д.Н. Минимизация логической структуры цифрового автомата для поиска шаблонов [Текст] / Д.Н. Ильченко, А.К. Мельников // Сборник научных статей по итогам международной заочной научно-практической конференции "Интеграция науки и практики, вопросы модернизации, проблемы совершенствования в экономике, проектном менеджменте, образовании, юриспруденции, языкознании, культурологии, экологии, зоологии, химии, биологии, медицине, психологии, политологии, филологии, философии, социологии, информатике, технике, математике,

физике", Санкт-Петербург, 27-28.02.2014. - СПб: Изд-во «КультИнформПресс», 2014. - С. 75-77. ISBN: 978-5-8392-0447-8.

78. Ильченко, Д.Н. Оптимизация синтеза цифровых автоматов для поиска шаблонов с масками [Текст] / Д.Н. Ильченко, А.К. Мельников // Труды Ш-ей международной заочной научно-практической конференции "Академическая наука - проблемы и достижения", Москва, 20-21.02 2014. М., 2014. - С. 149-150. ISBN: 978-1496060730.

79. Годяев А.И. Теоретические основы анализа и логического проектирования дискретных устройств: учебное пособие. - Хабаровск: Изд-во ДВГУПС, 2007. - 128с.

80. Ильченко, Д.Н. Методы оптимизации автоматных моделей поиска шаблонов [Текст] / Д.Н. Ильченко, А.К. Мельников // Труды XII Всероссийского совещания по проблемам управления (ВСПУ-2014). - М.: Изд-во ИПУ им. В.А. Трапезникова РАН, 2014.

81. Ильченко, Д.Н. Оптимизация цифровых автоматов поиска шаблонов [Текст] / Д.Н. Ильченко // Труды Десятой юбилейной ежегодной научной конференции студентов и аспирантов базовых кафедр, 15-20 апреля 2014 г., г. Ростов-на-Дону. - Ростов н/Д: Изд-во ЮНЦ РАН, 2014. - С. 63-64. ISBN 978-5-4358-0085-2.

82. Ильченко, Д.Н. Преобразования структуры автоматов поиска шаблонов с масками [Текст] / Д.Н. Ильченко // Известия ЮФУ. Технические науки. - Таганрог: Изд-во ТТИ ЮФУ, 2014. - №6 (155), С.108-116.

83. Ильченко, Д.Н. Программа синтеза и оптимизации цифровых автоматов для мониторинга компьютерных сетей / Ильченко Д.Н., Гудков В.А., Бовкун A.B. // Свидетельство об официальной регистрации программы для ЭВМ № 2014617297, РФ. Зарегистр. в Реестре программ для ЭВМ 16.07.2014 г. Правообладатель: федеральное государственное автономное образовательное учреждение высшего профессионального образования «Южный федеральный университет».

84. Гуленок А.А. Среда разработки масштабируемых компонентов вычислительных структур для реконфигурируемых систем. Известия ТРТУ. Специальный выпуск. Технические науки. Материалы LII научно-технической конференции профессорско-преподавательского состава, аспирантов и сотрудников ТРТУ. - Таганрог: Изд-во ТРТУ, 2006. - № 9 (64). -С. 182.

85. Гуленок А.А. Среда разработки масштабируемых макрообъектов для многопроцессорных вычислительных систем с реконфигурируемой архитектурой. Труды Всероссийской научной конференции «Научный сервис в сети ИНТЕРНЕТ: многоядерный компьютерный мир. 15 лет РФФИ». - М.: Изд-во МГУ, 2007. - С. 242-243

86. Гуленок А.А. Методы и алгоритмы отображения графов задач на реконфигурируемые вычислительные системы. Вестник компьютерных и информационных технологий. -М.: Машиностроение, 2011. - №6. - С. 3-11.

87. Мелихов А. Н. Ориентированные графы и конечные автоматы. - М.: Наука, 1971.-416 с.

88. Зотов В.Ю. Программирование встраиваемых микропроцессорных систем на основе плис фирмы Xilinx. - М.:Горячая линия - 2006. - 520 с.

89. Ильченко, Д.Н. Генератор файлов топологических ограничений для вычислительных структур и интерфейсов на ПЛИС / Ильченко Д.Н., Дордопуло А.И., Доронченко Ю.И. // Свидетельство об официальной регистрации программы для ЭВМ № 2013619581, РФ. Зарегистр. в Реестре программ для ЭВМ 10.10.2013 г. Правообладатель: федеральное государственное автономное образовательное учреждение высшего профессионального образования «Южный федеральный университет».

90. Ильченко, Д.Н. Устройство для лексемного анализа данных в сети Ethernet в режиме реального времени [Текст] / Д.Н. Ильченко // Тезисы докладов Восьмой ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН 11-25 апреля 2012 года. -Ростов-на-Дону: Изд-во ЮНЦ РАН, 2012. - С. 125-126.

91. Ильченко, Д.Н. Реализация поиска ключевых слов в текстовых файлах, передаваемых по сети Ethernet [Текст] / Д.Н. Ильченко // Материалы Второй Всероссийской научно-технической конференции СКТ-2012. — Таганрог: Изд-во ТТИ ЮФУ, 2012. - С. 118-120.

92. Ильченко, Д.Н. Устройство поиска битовых последовательностей в потоке данных, передаваемых по сети Ethernet [Текст] / Д.Н. Ильченко // Труды молодых ученых ЮФУ и ЮНЦ РАН «Высокопроизводительные вычислительные системы» Выпуск 2. - Таганрог: Изд-во ЮФУ, 2012. - С. 1215.

93. Ильченко, Д.Н. Поиск символьных структур в сети Ethernet [Текст] / Д.Н. Ильченко // Сборник трудов Девятой ежегодной научной конференции студентов и аспирантов базовых кафедр, 15-20 апреля 2013 г., г. Ростов-на-Дону. - Ростов н/Д: Изд-во ЮНЦ РАН, 2013. С. 106-107.

94. Ильченко, Д.Н. Реализация алгоритма Ахо-Корасика для поиска сигнатур в потоке данных в сети Ethernet с использованием реконфигурируемых вычислительных систем [Текст] / Д.Н. Ильченко // Тезисы докладов Седьмой ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН 11-25 апреля 2011 года. - Ростов-на-Дону: Изд-во ЮНЦ РАН, 2011. - С. 121-122.

95. Ильченко, Д.Н. Сигнатурный анализ множества каналов Ethernet с помощью алгоритма Ахо-Корасик с использованием реконфигурируемых вычислителей [Текст] / Д.Н. Ильченко // Труды молодых ученых ЮФУ и ЮНЦ РАН «Высокопроизводительные вычислительные системы». -Таганрог: Изд-во ТТИ ЮФУ, 2011. - С.60-63.

96. Ильченко, Д.Н. Доступ к реконфигурируемым вычислительным системам через Ethernet-канал [Текст] / Д.Н. Ильченко // Труды 6-й Всероссийской мультиконференции по проблемам управления МКПУ-2013, 30 сентября-5 октября 2013 г., с. Дивноморское, Геленджик, Россия. - Т. 4. -Ростов-на-Дону: Изд-во ЮФУ, 2013. - С. 153-156.

97. Ильченко, Д.Н. Организация доступа к вычислительным устройствам в реконфигурируемых вычислительных системах с высокой степенью распараллеливания [Текст] / Д.Н. Ильченко, Ю.И. Доронченко, М.К. Раскладкин // Материалы Международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы» (МВУС-2009). - Таганрог: Изд-во ТТИ ЮФУ, 2009.- Т.1. - С.43-45.

98. Таназ М. Анализ сигнатур или анализ протоколов, что лучше? [электронный ресурс]. - Режим доступа: http://www.securitylab.rU/analytics/216259.рЬр