• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Синтез и анализ моделей процессов

Приоритетные направления развития: инженерные науки
2017

Цель работы:

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

Используемые методы:

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

Эмпирическая база исследования:

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

Результаты работы:

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

Доказана алгоритмическая неразрешимость выполнимости формул логики FL-LTL на конечных автоматах-преобразователях, работающих над вполне коммутативными полугруппами и абелевыми группами.

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

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

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

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

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

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

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

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

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

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

Разработан и реализован метод извлечения моделей процессов, представленных на высокоуровневом языке BPMN (Business Process Model and Notation). Этот метод позволяет строить иерархические модели процессов, а также выявлять дополнительные перспективы моделирования, такие как данные и ресурсы.

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

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

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

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

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

Степень внедрения, рекомендации по внедрению или итоги внедрения результатов НИР

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

Публикации по проекту:


Sergey A. Shershakov, Anna A. Kalenkova, Irina A. Lomazova. Transition Systems Reduction: Balancing Between Precision and Simplicity, in: Lecture Notes in Computer Science Vol. 10470: Transactions on Petri Nets and Other Models of Concurrency XII. Berlin, Heidelberg : Springer, 2017. doi P. 119-139. doi
Lomazova I. A., Popova-Zeugmann L., Bartels A. Controlling boundedness for live Petri nets, in: International Conference on Control, Decision and Information Technologies, CoDIT 2017, Barcelona, Spain, April 5-7, 2017. IEEE, 2017. P. 0236-0241. doi
Мицюк А. А., Ломазова И. А., ван дер Аалст В. Использование журналов событий для локальной корректировки моделей процессов // Моделирование и анализ информационных систем. 2017. Т. 24. № 4. С. 459-480. doi
Kalenkova A. A., van der Aalst W., Lomazova I. A., Rubin V. Process Mining Using BPMN: Relating Event Logs and Process Models // Software and Systems Modeling. 2017. Vol. 16. No. 4. P. 1019-1048. doi
Begicheva A.K., Lomazova I.A. Discovering High-Level Process Models from Event Logs // Моделирование и анализ информационных систем. 2017. Vol. 24. No. 2. P. 125-140. doi
Захаров В. А., Жайлауова Ш. Р. О задаче минимизации последовательных программ // Моделирование и анализ информационных систем. 2017. Т. 24. № 4. С. 415-433. doi
R.A. Nesterov, I.A. Lomazova. Using Interface Patterns for Compositional Discovery of Distributed System Models // Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 4. P. 21-38. doi
Mitsyuk A. A., Shugurov I., Kalenkova A. A., van der Aalst W. Generating Event Logs for High-Level Process Models // Simulation Modelling Practice and Theory. 2017. Vol. 74. P. 1-16. doi
Lomazova I. A. Resource Equivalences in Petri Nets, in: Application and Theory of Petri Nets and Concurrency. 38th International Conference, PETRI NETS 2017, Zaragoza, Spain, June 25–30, 2017, Proceedings / Ed. by W. van der Aalst, E. Best. Vol. 10258: Lecture Notes in Computer Science. Switzerland : Springer, 2017. doi P. 19-34. doi
Dworzanski L. W., Михайлов В. Е. Tool for Behavioral Analysis of Well-Structured Transition Systems // Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 4. P. 175-190. doi
Konchagin A., Kalenkova A. A. On the efficient application of Aho-Corasick algorithm in process mining, in: Analysis of Images, Social Networks and Texts. 6th International Conference, 2017, Lecture Notes in Computer Science, Revised Selected Papers / Ed. by W. M. van der Aalst, D. I. Ignatov, M. Khachay, S. Kuznetsov, V. Lempitsky, I. A. Lomazova, A. Napoli, A. Panchenko, P. M. Pardalos, A. V. Savchenko, S. Wasserman. Vol. 10716. Cham : Springer, 2018. doi P. 371-377. doi
K. Davydova, S. Shershakov. Mining Hybrid UML Models from Event Logs of SOA Systems // Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 4. P. 155-174. doi
Mitsyuk A. A., Lomazova I. A., van der Aalst W. Using Event Logs for Local Correction of Process Models / Пер. с рус. // Automatic Control and Computer Sciences. 2017. Vol. 51. No. 7. P. 709-723. doi
Mitsyuk A. A., Lomazova I. A., Ivan S. Shugurov, Wil M.P. van der Aalst. Process Model Repair by Detecting Unfitting Fragments, in: Supplementary Proceedings of the 6th International Conference on Analysis of Images, Social Networks and Texts (AIST-SUP 2017), Moscow, Russia, July 27-29, 2017 / Ed. by W. van der Aalst, M. Y. Khachay, S. Kuznetsov, V. Lempitsky, I. A. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, P. M. Pardalos, A. V. Savchencko, S. Wasserman, D. I. Ignatov. Vol. 1975. Aachen : CEUR-WS.org, 2017. Ch. 32. P. 301-313.