Разработка пакета прикладных программ для автоматизации построения автоматных композиций
|
РЕФЕРАТ 2
ВВЕДЕНИЕ 5
1 Основные определения и обозначения 11
2 Обзор существующих инструментов 18
2.1 ObjectGEODE 18
2.2 Estelle 20
2.3 TorX 22
3 Архитектура пакета прикладных программ 23
4 Описание программной реализации FSMs2Composition 27
4.1 Используемый инструментарий 27
4.2 Графический интерфейс 28
4.3 Внутреннее представление 29
4.4 Python-скрипт 31
4.5 Star-полуавтоматы 40
4.6 Реализованный функционал 44
4.7 Возможности расширения пакета прикладных программ 45
5 Эксперименты 51
5.1 Использование в учебном процессе 51
5.2 Примеры реальных систем 54
5.3 Эксперименты по построению композиций временных автоматов 57
ЗАКЛЮЧЕНИЕ 60
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 62
ПРИЛОЖЕНИЕ А. Инструкция по установке и эксплуатации 64
Инструкция по установке и запуску виртуальной машины 64
Управление графическим редактором и запуск тестового примера 65
ПРИЛОЖЕНИЕ Б Отчет о патентных исследованиях 69
ВВЕДЕНИЕ 5
1 Основные определения и обозначения 11
2 Обзор существующих инструментов 18
2.1 ObjectGEODE 18
2.2 Estelle 20
2.3 TorX 22
3 Архитектура пакета прикладных программ 23
4 Описание программной реализации FSMs2Composition 27
4.1 Используемый инструментарий 27
4.2 Графический интерфейс 28
4.3 Внутреннее представление 29
4.4 Python-скрипт 31
4.5 Star-полуавтоматы 40
4.6 Реализованный функционал 44
4.7 Возможности расширения пакета прикладных программ 45
5 Эксперименты 51
5.1 Использование в учебном процессе 51
5.2 Примеры реальных систем 54
5.3 Эксперименты по построению композиций временных автоматов 57
ЗАКЛЮЧЕНИЕ 60
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 62
ПРИЛОЖЕНИЕ А. Инструкция по установке и эксплуатации 64
Инструкция по установке и запуску виртуальной машины 64
Управление графическим редактором и запуск тестового примера 65
ПРИЛОЖЕНИЕ Б Отчет о патентных исследованиях 69
Актуальность работы. Поведение дискретных систем, например, телекоммуникационных протоколов, схем, веб-сервисов можно описать с помощью автоматных моделей, в частности модели конечного автомата [1]. Теория автоматов предоставляет большой набор алгоритмов и методов для работы с данными моделями. Также часто встречаются ситуации, когда несколько таких систем взаимодействуют друг с другом - несколько соединенных схем, или клиент и сервер взаимодействуют в рамках одного телекоммуникационного протокола. И в процессе этого взаимодействия возможно возникновение различных проблем - тупиков, зацикливаний. Описав совместной поведение с помощью формальной модели можно построить тест для проверки совместной работы, который покажет наличие проблем. Для описания взаимодействия нескольких автоматных моделей используется операции композиции [2].
Существующие инструменты с графическим интерфейсом не строят композиции, а только симулируют взаимодействие компонент. Существует несколько инструментов без графического интерфейса, которые могут построить композиции автоматных моделей, но каждый инструмент предназначен для построения композиции определенного режима работы или типа композируемых моделей.
Описываемый в данной работе пакет прикладных программ имеет архитектуру, которая разработана так, чтобы использовать существующие инструменты для построения композиций, но при этом инкапсулировать их в единый графический интерфейс. Благодаря такому подходу можно легко добавлять новые режимы работы и виды композируемых автоматных моделей за счёт добавления новых инструментов. Таким образом пользователю не нужно будет знать особенностей того или иного инструмента, он будет взаимодействовать только с универсальным графическим интерфейсом, в рамках которого есть возможность строить композиции разных режимов работы для разных автоматных моделей.
Целью работы является разработка унифицированного по интерфейсу пакета прикладных программ FSMs2Composition для построения композиций различной структуры для автоматных моделей и их модификаций.
Для достижения поставленной цели необходимо решить следующие задачи:
1. Изучить существующие структуры, топологии и режимы работы композиций
2. Сделать обзор существующего программного обеспечения для построения композиции
3. Разработать архитектуру пакета прикладных программ для построения композиций конечных автоматов таким образом, чтобы в дальнейшем функционал пакета можно было расширять на различные топологии и режимы работы композиции, а также использовать его для решения автоматных уравнений
4. Реализовать пакет прикладных программ для построения бинарной параллельной композиции конечных автоматов
5. Протестировать и отладить пакет прикладных программ, в том числе на реальных примерах
6. Разработать и реализовать алгоритм преобразования глобального полуавтомата композиции во временной автомат, а также провести эксперименты по построению композиции временных автоматов для определения целесообразности расширения разрабатываемого пакета для модификаций автоматных моделей
Методы исследования.
Используется аппарат дискретной математики, в частности, теория автоматов. Также в процессе реализации используются шаблоны проектирования и объектно-ориентированное программирование.
Научная новизна.
1. Разработаны алгоритмы для формирования набора команд BALM-II для построения параллельной композиции.
2. Разработан и реализован алгоритм преобразования полуавтомата во временной автомат.
Основные положения, выносимые на защиту.
1. Пакет прикладных программ FSMs2Composition, позволяющий построить параллельную композицию в автоматическом режиме.
2. Алгоритм построения временного автомата по полуавтомату.
3. Результаты экспериментов по построению композиции временных автоматов.
Достоверность результатов.
Полученные в данной работе положения и выводы опираются на известные утверждения и теоремы теории автоматов; результаты композиций, полученные с помощью пакета прикладных программ, совпадают с результатами, полученными вручную.
Практическая ценность.
Разработан и реализован пакет прикладных программ FSMs2Composition для построения автоматных композиций. Данный пакет может быть использован в научных исследованиях и в учебном процессе в рамках курса «Теория автоматов». Разработанный пакет является расширяемым, и в перспективе может быть дополнен возможностью построения других видов автоматных композиций, а также адаптирован для решения автоматных уравнений.
Апробация работы.
Основные положения и результаты были представлены на международных и всероссийских конференциях:
1. Семнадцатая международная научно-практическая конференция студентов, аспирантов и молодых ученых (МСИТ - 2020)
2. Шестнадцатая всероссийская конференция студенческих научно-исследовательских инкубаторов (СНИИ - 2019)
3. Пятнадцатая Всероссийская конференция студенческих научно-исследовательских инкубаторов (СНИИ - 2017)
4. SYRCoSE (Spring/Summer Young Researchers' Colloquium on Software Engineering) 2017
5. Четырнадцатая Всероссийская конференция студенческих научно-исследовательских инкубаторов (СНИИ - 2017)
По полученным результатам опубликовано 6 работ в изданиях, входящих в базы цитирования ВАК и РИНЦ.
1. Сотников А.П. Автоматизация построения автоматной композиции для описания клиент-серверного взаимодействия на примере протокола BOOTP / А.П. Сотников, В.С. Болтова, Н.В. Шабалдина // Молодежь и современные информационные технологии: сборник трудов XVII Международной научно-практической конференции студентов, аспирантов и молодых ученых. - Томск, 17-20 февраля 2020 г. / Томский политехнический университет. - Томск: Изд-во Томского политехнического университета, 2020. - C. 186-188.
2. Сотников А.П. Разработка интерфейса для пакета прикладных программ по автоматизированному построению автоматных композиций // Труды Шестнадцатой Всероссийской конференции студенческих научно-исследовательских инкубаторов. - Томск 13-15 мая 2019г. / - Томск: Изд- во НТЛ, 2019. - С. 197-199.
3. Сотников А.П. Применение операций левого/правого частного для очистки пользовательских данных в веб-приложениях / А.П. Сотников, Н.В. Шабалдина // Новые информационные технологии в исследовании сложных структур: Н766 материалы Двенадцатой конференции с международным участием. 4-8 июня 2018 г. - Томск: Издательский Дом Томского государственного университета, 2018. С. 84.
4. Сотников А.П. Программная реализация преобразования глобального полуавтомата во временной автомат // Труды Четырнадцатой Всероссийской конференции студенческих научно-исследовательских инкубаторов. - Томск 17-18 мая 2017г. / под ред. В.В. Демина. - Томск: Изд-во НТЛ, 2017. - С. 86-90.
5. Sotnikov A. P. Experiments On Parallel Composition of Timed Finite State Machines / A. P. Sotnikov, N. V. Shabaldina, M. L. Gromov // Труды ИСП РАН 29:3 (2017). С. 233-246.
6. Сотников А.П. Применение операций левого/правого частного для очистки пользовательских данных в веб-приложениях / А.П. Сотников, Н.В. Шабалдина // Новые информационные технологии в исследовании сложных структур: Н766 материалы Двенадцатой конференции с международным участием. 4-8 июня 2018 г. - Томск: Издательский Дом Томского государственного университета, 2018. С. 84.
Структура и объем работы.
Магистерская диссертация разделена на 5 глав.
В первой главе вводятся основные понятия и определения, которые используются в работе. В частности, вводятся понятия классического автомата, полуавтомата, временного автомата, композиции автоматов и ее типы. Также приводятся формальное описание построения полуавтомата по автомату и формальное описание построения параллельной и синхронной композиций.
Во второй главе проводится обзор существующих инструментов для построения (симулирования) композиции, имеющих графический интерфейс. Приводится их краткое описание, некоторые примеры и разбирается, почему они не подходят для достижения поставленной цели. Помимо инструментов с графическим интерфейсом приводятся инструменты, не имеющие графического интерфейса, которые тем не менее строят композиции при различных режимах работы.
В третьей главе подробно рассматривается общая архитектура пакета прикладных программ FSMs2Composition, рассказывается, почему она построена таким образом и за счёт чего может быть расширена в дальнейшем.
В четвертой главе описывается реализация пакета прикладных программ. Приводится описание используемых в разработке инструментов, интерфейса и внутреннего представления, которое используется в графическом интерфейсе. Подробно описывается реализация построения параллельной композиции с помощью BALM-II, последовательность команд, генерируемая в этом случае. Также отмечаются выявленные проблемы и то, как они были решены. Приводятся алгоритм для формирования данных о структуре композиции и алгоритмы для формирования последовательности команд BALM-II для построения параллельной композиции. Также описываются так называемые star-полуавтоматы, которые являются особенностью процесса построения параллельной композиции в целом. В конце подводится краткий итог реализованного функционала и рассматриваются дальнейшие пути для расширения пакета прикладных программ и их возможные реализации, в частности, приводится предложенный алгоритм возврата от глобального полуавтомата композиции к временному автомату, тем самым появляется возможность построения параллельной композиции временных автоматов с помощью BALM-II.
В пятой главе идёт речь о проведенных экспериментах. О внедрении пакета прикладных программ FSMs2Composition в учебный процесс, его тестировании и отладке. Также говорится об отладке на примере реальных протоколов BOOTP и TIME. Приводится описание и результаты экспериментов по построению композиций временных автоматов с использованием BALM-II; эти эксперименты выполнялись, в частности, для оценки перспектив расширения разработанного пакета прикладных программ на модель временного автомата.
Существующие инструменты с графическим интерфейсом не строят композиции, а только симулируют взаимодействие компонент. Существует несколько инструментов без графического интерфейса, которые могут построить композиции автоматных моделей, но каждый инструмент предназначен для построения композиции определенного режима работы или типа композируемых моделей.
Описываемый в данной работе пакет прикладных программ имеет архитектуру, которая разработана так, чтобы использовать существующие инструменты для построения композиций, но при этом инкапсулировать их в единый графический интерфейс. Благодаря такому подходу можно легко добавлять новые режимы работы и виды композируемых автоматных моделей за счёт добавления новых инструментов. Таким образом пользователю не нужно будет знать особенностей того или иного инструмента, он будет взаимодействовать только с универсальным графическим интерфейсом, в рамках которого есть возможность строить композиции разных режимов работы для разных автоматных моделей.
Целью работы является разработка унифицированного по интерфейсу пакета прикладных программ FSMs2Composition для построения композиций различной структуры для автоматных моделей и их модификаций.
Для достижения поставленной цели необходимо решить следующие задачи:
1. Изучить существующие структуры, топологии и режимы работы композиций
2. Сделать обзор существующего программного обеспечения для построения композиции
3. Разработать архитектуру пакета прикладных программ для построения композиций конечных автоматов таким образом, чтобы в дальнейшем функционал пакета можно было расширять на различные топологии и режимы работы композиции, а также использовать его для решения автоматных уравнений
4. Реализовать пакет прикладных программ для построения бинарной параллельной композиции конечных автоматов
5. Протестировать и отладить пакет прикладных программ, в том числе на реальных примерах
6. Разработать и реализовать алгоритм преобразования глобального полуавтомата композиции во временной автомат, а также провести эксперименты по построению композиции временных автоматов для определения целесообразности расширения разрабатываемого пакета для модификаций автоматных моделей
Методы исследования.
Используется аппарат дискретной математики, в частности, теория автоматов. Также в процессе реализации используются шаблоны проектирования и объектно-ориентированное программирование.
Научная новизна.
1. Разработаны алгоритмы для формирования набора команд BALM-II для построения параллельной композиции.
2. Разработан и реализован алгоритм преобразования полуавтомата во временной автомат.
Основные положения, выносимые на защиту.
1. Пакет прикладных программ FSMs2Composition, позволяющий построить параллельную композицию в автоматическом режиме.
2. Алгоритм построения временного автомата по полуавтомату.
3. Результаты экспериментов по построению композиции временных автоматов.
Достоверность результатов.
Полученные в данной работе положения и выводы опираются на известные утверждения и теоремы теории автоматов; результаты композиций, полученные с помощью пакета прикладных программ, совпадают с результатами, полученными вручную.
Практическая ценность.
Разработан и реализован пакет прикладных программ FSMs2Composition для построения автоматных композиций. Данный пакет может быть использован в научных исследованиях и в учебном процессе в рамках курса «Теория автоматов». Разработанный пакет является расширяемым, и в перспективе может быть дополнен возможностью построения других видов автоматных композиций, а также адаптирован для решения автоматных уравнений.
Апробация работы.
Основные положения и результаты были представлены на международных и всероссийских конференциях:
1. Семнадцатая международная научно-практическая конференция студентов, аспирантов и молодых ученых (МСИТ - 2020)
2. Шестнадцатая всероссийская конференция студенческих научно-исследовательских инкубаторов (СНИИ - 2019)
3. Пятнадцатая Всероссийская конференция студенческих научно-исследовательских инкубаторов (СНИИ - 2017)
4. SYRCoSE (Spring/Summer Young Researchers' Colloquium on Software Engineering) 2017
5. Четырнадцатая Всероссийская конференция студенческих научно-исследовательских инкубаторов (СНИИ - 2017)
По полученным результатам опубликовано 6 работ в изданиях, входящих в базы цитирования ВАК и РИНЦ.
1. Сотников А.П. Автоматизация построения автоматной композиции для описания клиент-серверного взаимодействия на примере протокола BOOTP / А.П. Сотников, В.С. Болтова, Н.В. Шабалдина // Молодежь и современные информационные технологии: сборник трудов XVII Международной научно-практической конференции студентов, аспирантов и молодых ученых. - Томск, 17-20 февраля 2020 г. / Томский политехнический университет. - Томск: Изд-во Томского политехнического университета, 2020. - C. 186-188.
2. Сотников А.П. Разработка интерфейса для пакета прикладных программ по автоматизированному построению автоматных композиций // Труды Шестнадцатой Всероссийской конференции студенческих научно-исследовательских инкубаторов. - Томск 13-15 мая 2019г. / - Томск: Изд- во НТЛ, 2019. - С. 197-199.
3. Сотников А.П. Применение операций левого/правого частного для очистки пользовательских данных в веб-приложениях / А.П. Сотников, Н.В. Шабалдина // Новые информационные технологии в исследовании сложных структур: Н766 материалы Двенадцатой конференции с международным участием. 4-8 июня 2018 г. - Томск: Издательский Дом Томского государственного университета, 2018. С. 84.
4. Сотников А.П. Программная реализация преобразования глобального полуавтомата во временной автомат // Труды Четырнадцатой Всероссийской конференции студенческих научно-исследовательских инкубаторов. - Томск 17-18 мая 2017г. / под ред. В.В. Демина. - Томск: Изд-во НТЛ, 2017. - С. 86-90.
5. Sotnikov A. P. Experiments On Parallel Composition of Timed Finite State Machines / A. P. Sotnikov, N. V. Shabaldina, M. L. Gromov // Труды ИСП РАН 29:3 (2017). С. 233-246.
6. Сотников А.П. Применение операций левого/правого частного для очистки пользовательских данных в веб-приложениях / А.П. Сотников, Н.В. Шабалдина // Новые информационные технологии в исследовании сложных структур: Н766 материалы Двенадцатой конференции с международным участием. 4-8 июня 2018 г. - Томск: Издательский Дом Томского государственного университета, 2018. С. 84.
Структура и объем работы.
Магистерская диссертация разделена на 5 глав.
В первой главе вводятся основные понятия и определения, которые используются в работе. В частности, вводятся понятия классического автомата, полуавтомата, временного автомата, композиции автоматов и ее типы. Также приводятся формальное описание построения полуавтомата по автомату и формальное описание построения параллельной и синхронной композиций.
Во второй главе проводится обзор существующих инструментов для построения (симулирования) композиции, имеющих графический интерфейс. Приводится их краткое описание, некоторые примеры и разбирается, почему они не подходят для достижения поставленной цели. Помимо инструментов с графическим интерфейсом приводятся инструменты, не имеющие графического интерфейса, которые тем не менее строят композиции при различных режимах работы.
В третьей главе подробно рассматривается общая архитектура пакета прикладных программ FSMs2Composition, рассказывается, почему она построена таким образом и за счёт чего может быть расширена в дальнейшем.
В четвертой главе описывается реализация пакета прикладных программ. Приводится описание используемых в разработке инструментов, интерфейса и внутреннего представления, которое используется в графическом интерфейсе. Подробно описывается реализация построения параллельной композиции с помощью BALM-II, последовательность команд, генерируемая в этом случае. Также отмечаются выявленные проблемы и то, как они были решены. Приводятся алгоритм для формирования данных о структуре композиции и алгоритмы для формирования последовательности команд BALM-II для построения параллельной композиции. Также описываются так называемые star-полуавтоматы, которые являются особенностью процесса построения параллельной композиции в целом. В конце подводится краткий итог реализованного функционала и рассматриваются дальнейшие пути для расширения пакета прикладных программ и их возможные реализации, в частности, приводится предложенный алгоритм возврата от глобального полуавтомата композиции к временному автомату, тем самым появляется возможность построения параллельной композиции временных автоматов с помощью BALM-II.
В пятой главе идёт речь о проведенных экспериментах. О внедрении пакета прикладных программ FSMs2Composition в учебный процесс, его тестировании и отладке. Также говорится об отладке на примере реальных протоколов BOOTP и TIME. Приводится описание и результаты экспериментов по построению композиций временных автоматов с использованием BALM-II; эти эксперименты выполнялись, в частности, для оценки перспектив расширения разработанного пакета прикладных программ на модель временного автомата.
Данная магистерская работа посвящена разработке пакета прикладных программ для автоматизации построения автоматных композиций.
Был проведен обзор существующих топологий и режимов работы композиций, а также обзор существующих инструментов для построения композиций автоматных моделей. Обзор показал, что инструменты для построения композиций существуют, но либо симулируют взаимодействие компонент, а не строят композицию, либо имеют ряд серьезных недостатков - отсутствие графического интерфейса, возможность строить композицию только определенного режима работы, сложный интерфейс и высокий порог вхождения.
Для решения этих проблем была разработана архитектура пакета прикладных программ FSMs2Composition. Главное особенностью архитектуры является возможность использования существующих инструментов для построения автоматных композиций. Пакет прикладных программ предоставляет пользователю графический интерфейс и скрывает внутренние инструменты. Т.о. пользователю не нужно изучать каждый отдельный инструмент, а графический интерфейс предоставляет интуитивно понятный способ построения композиций различных режимов работы. В то же время, есть возможность расширять список доступных режимов работы и топологий за счёт добавления новых инструментов или расширения существующих.
Далее был разработан и реализован графический интерфейс, позволяющий пользователю задать структуру композиции.
Для построения параллельной композиции классических автоматов были разработаны и реализованы алгоритмы для генерации последовательности команд для инструмента BALM-II.
Пакет прикладных программ FSMs2Composition был отлажен на ряде абстрактных и реальных примеров. В качестве реальных примеров использовались протоколы BOOTP и TIME, которые были описаны с помощью автоматов и скомпозированы. Результаты были проверены сравнением с построенной вручную композицией.
Кроме того, был разработан и реализован алгоритм преобразования глобального полуавтомата композиции во временной автомат. Также был проведен эксперимент по построению композиции временных автоматов, который показал, что с помощью BALM-II можно строить параллельную композицию временных автоматов (при определенных ограничениях на размерности автоматов), а значит, пакет прикладных программ FSMs2Composition можно расширить на случай временных автоматов.
Также пакет прикладных программ был внедрен в учебный процесс в рамках курса «Теории автоматов».
Был проведен обзор существующих топологий и режимов работы композиций, а также обзор существующих инструментов для построения композиций автоматных моделей. Обзор показал, что инструменты для построения композиций существуют, но либо симулируют взаимодействие компонент, а не строят композицию, либо имеют ряд серьезных недостатков - отсутствие графического интерфейса, возможность строить композицию только определенного режима работы, сложный интерфейс и высокий порог вхождения.
Для решения этих проблем была разработана архитектура пакета прикладных программ FSMs2Composition. Главное особенностью архитектуры является возможность использования существующих инструментов для построения автоматных композиций. Пакет прикладных программ предоставляет пользователю графический интерфейс и скрывает внутренние инструменты. Т.о. пользователю не нужно изучать каждый отдельный инструмент, а графический интерфейс предоставляет интуитивно понятный способ построения композиций различных режимов работы. В то же время, есть возможность расширять список доступных режимов работы и топологий за счёт добавления новых инструментов или расширения существующих.
Далее был разработан и реализован графический интерфейс, позволяющий пользователю задать структуру композиции.
Для построения параллельной композиции классических автоматов были разработаны и реализованы алгоритмы для генерации последовательности команд для инструмента BALM-II.
Пакет прикладных программ FSMs2Composition был отлажен на ряде абстрактных и реальных примеров. В качестве реальных примеров использовались протоколы BOOTP и TIME, которые были описаны с помощью автоматов и скомпозированы. Результаты были проверены сравнением с построенной вручную композицией.
Кроме того, был разработан и реализован алгоритм преобразования глобального полуавтомата композиции во временной автомат. Также был проведен эксперимент по построению композиции временных автоматов, который показал, что с помощью BALM-II можно строить параллельную композицию временных автоматов (при определенных ограничениях на размерности автоматов), а значит, пакет прикладных программ FSMs2Composition можно расширить на случай временных автоматов.
Также пакет прикладных программ был внедрен в учебный процесс в рамках курса «Теории автоматов».
Подобные работы
- АВТОМАТИЗАЦИЯ ПОСТРОЕНИЯ МОДЕЛЕЙ МНОГОКОМПОНЕНТНЫХ ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМ НА ОСНОВЕ ИНСТРУМЕНТА BALM-II
Дипломные работы, ВКР, физика. Язык работы: Русский. Цена: 4750 р. Год сдачи: 2019 - ИССЛЕДОВАНИЕ ПРИМЕНИМОСТИ КОМПОЗИЦИИ КОНЕЧНЫХ АВТОМАТОВ К ТЕСТИРОВАНИЮ ТЕЛЕКОММУНИКАЦИОННЫХ ПРОТОКОЛОВ
Бакалаврская работа, физика. Язык работы: Русский. Цена: 4265 р. Год сдачи: 2020 - ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ КОНЕЧНО АВТОМАТНЫХ МЕТОДОВ
ТЕСТИРОВАНИЯ В КОНТЕКСТЕ ДЛЯ ТЕЛЕКОММУНИКАЦИОННЫХ ПРОТОКОЛОВ
Магистерская диссертация, физика. Язык работы: Русский. Цена: 5570 р. Год сдачи: 2016