Максим Чистолинов / Николай Близнюк, 3 курс, mod-sem

На этом форуме публикуются и уточняются постановки задач студентам, а также отслеживается ход их выполнения

Модератор: staff

Закрыто
Бычков Иван
Аспирант
Сообщения: 179
Зарегистрирован: 23 сен 2008 01:19 pm

Максим Чистолинов / Николай Близнюк, 3 курс, mod-sem

Сообщение Бычков Иван »

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

Актуальность
В конце 80-х - начале 90-х было достаточно много статей на тему использования расширений регулярных выражений (РРВ) для спецификации и распознавания поведения РВС, в том числе - в целях отладки. Хотелось бы разобраться во что все это выросло. В перспективе - выбрать/доработать средства-фавориты и сделать на их основе распознаватель для трасс разрабатываемого в ЛВК стенда.
Исходная посылка: РРВ достаточно мощный и относительно легко реализуемый механизм, который возможно сделать удобным для практического использования.

Цель курсовой работы на 3-ем курсе
Составить обзор и ретроспективу средств спецификации поведения РВС на основе РРВ. В практическом плане - восстановить работоспособность модуля анализа РВ Олега Козлова retools и апробировать на нем 1-2 расширения РРВ.

План работы
План на осенний семестр
1. Изучить статьи по использованию РРВ в целях спецификации поведения ВС и РВС. Составить перечень встречающихся в литературе расширений РРВ, определить их области приложения.
2. Совместно с научным руководителем выбрать критерии сравнения средств на основе РРВ.
3. Составить обзор по п. 1-2.
В практической части:
4. Восстановить работоспособность библиотеки работы с РВ O.Козлова retools.
5. Реализовать в retools алгоритмы построения НКА:
* алгоритм отмеченного выражения;
* алгоритм на основе анализа множеств позиций;
[возможно]
6. Реализовать метод интерпретации НКА (regex driven pattern matching).
7. Перенести в retools метод построения РВ по КА на основе алгоритма элиминации вершин (реализован в курсовой М.Лахтурова).

План на весенний семестр
1. Изучить архитектуру различных библиотек и инструментов работы с РРВ. Разобраться, в какой степени можно повторно использовать имеющиеся реализации разбора РРВ для собственного анализатора трасс обменов в стенде.
2. Спроектировать поддержку РРВ для операций параллельной композиции, позиционной проверки и обратных ссылок.
3. Написать текст курсовой работы.
[возможно]
4. Составить обзор библиотек и инструментов, используемых для анализа и распознавания РРВ.
В практической части:
5. Реализовать в retools ограниченную поддержку операций параллельной композиции, обратных ссылок и позиционных проверок.
[возможно - в порядке эксперимента]
6. Перевести retools на использование библиотеки Boost Graph.

Ожидаемые результаты
1. Обзор методов спецификации поведения вычислительных систем на основе РРВ, критерии сравнения, выводы.
2. Восстановленная и дополненная библиотека работы с РPВ retools.
3. Текст курсовой работы с обзором, подробным описанием и обоснованием архитектуры библиотеки.
[возможно]
4. Обзор библиотек и инструментов, используемых для анализа и распознавания РРВ - в составе курсовой работы.
Николай Близнюк
Выпускник
Сообщения: 1
Зарегистрирован: 07 окт 2008 12:28 pm

Сообщение Николай Близнюк »

Тема работы

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

Актуальность


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

Цель работы


Составить обзор и показать ретроспективу средств спецификации поведения РВС на основе РРВ. В практическом плане - восстановить работоспособность модуля анализа РВ Олега Козлова retools и апробировать на нем 1-2 расширения РРВ.

Проделанная работа


Изучены статьи по использованию РРВ в целях спецификации поведения ВС [1-12]. Составлена сравнительная таблица этих статей (источников). Сформулированы критерии сравнения средств на основе РРВ и на их основе составлена таблица сравнения некоторых средств. Написан Обзор методов спецификации поведения вычислительных систем на основе РРВ. В обзор включены описания 6 средств спецификации поведения ВС, рассматриваются особенности каждого средства, расширения РВ используемые в каждом конкретном средстве. Кратко приведен синтаксис для каждого средства, для большинства средств - в формализованном виде.
В практической части выполнена доработка библиотеки работы с РВ O.Козлова retools. Была восстановлена работа этой библиотеки (исправлены некорректно работающие алгоритмы), проведен рефакторинг кода. Были внесены изменения в грамматику (для программы Bison) и в логику разбора РВ для построения синтаксического дерева. Были также добавлены различные варианты алгоритмов построения недетерминированного конечного автомата (НКА) по синтаксическому дереву РВ, на основе анализа множеств позиций FIRSTPOS, LASTPOS, FOLLOWPOS. Исправлены ошибки, допущенные Козловым в реализации построения детерминированного конечного автомата (ДКА) по алгоритму Ахо-Ульмана.

Дальнейшая деятельность


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

Список изученной литературы

1. F. Baiardi N. De Francesco, S. Stefanini, G. Vaglini Development of a debugger for a concurrent language // IEEE Trans.on Soft. Eng. – 1986.- Vol.SE-12, N.4.- P.547-553
2. Bates P., Wileden J. High-level debugging of distributed Systems: The Behavioral Approach // J. Systems and Software.- 1983.- Vol.3, N.4-P.255-264
3. Bates P. Distributed debugging tools for heterogeneous distributed system // ACM Sigplan Noties.- 1988, N.8. – P.107-111
4. Bernd Bruegge, Peter Hibbard Generalized path expressions: a high level debugging mechanism //J. Systems and Software. 1983 Vol.3, N.4. P.265-276
5. Wileden,Riddle,Sayler,Segal,Stavely Behavior specification in software design system //J. Systems and Software. 1983. Vol.3. P.123-135
6. N. De Francesco , D. Latella, G. Vaglini An interactive debugger for a concurrent language // Int. Conf. Software Engeneering, 8-th, Procs. 1985. P.320-325
7. Бочков С.О. Автоматизация отладки программ на основе операционного описания их поведения 1991
8. Garg Modeling of distributed systems by concurrent regular expressions // Proc. 2nd International Conference on Formal Description Techniques for Distributed Systems and Communication Protocols, Vancouber, Dec 1989
9. Garg, Raghunath Concurrent regular expressions and their relationship in Petri Nets // Computer Science Devision, 1988
10. Козлов О. Дипломная работа Язык описания шаблонов поиска по трассам событий 2007
11. Smith T. A debugger for message-based processes // Software-Pract. and Exper. 1985 Vol.15, N.11 P.1086-1173
12. Riddle The modeling and analysis of supervisory systems // ACM SIGPLAN Notices 1972, v.8 n.9, p.133-136
Закрыто