Темы от преподавателя

Возможные темы, если нет своих идей (обновляется):

1) Интерфейс для задания шаблонов поиска в анализе Си-программ

Pathfinder -- статический анализатор графов программ в КС-ограничениях: https://github.com/mipt-cs/pathfinder Для данного инструмента требуется разработать интерфейс пользователя, который позволит:

а) конструктивно описывать искомые шаблоны (на выходе должна быть грамматика в НФХ)

б) выводить найденные пути в сжатом виде

в) визуализировать граф исследуемой программы, подсвечивать найденные пути

г) Добавлять цепочки "переименований" переменных в межпроцедурном анализе + *points to-анализ.

е) другое*

Для мотивации можно почитать статью: https://mipt.ru/upload/medialibrary/023/02.pdf

2) Современные алгоритмы КС-достижимости

Pathfinder -- статический анализатор графов программ в КС-ограничениях: https://github.com/mipt-cs/pathfinder. Его солвер использует вариант CYK-алгоритма для поиска путей.

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

Для мотивации можно почитать статью: https://mipt.ru/upload/medialibrary/023/02.pdf

**3) Современные алгоритмы КС-достижимости: GLL. **

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

Для мотивации можно почитать статью: https://mipt.ru/upload/medialibrary/023/02.pdf

4) Статический анализатор на грамматиках с контекстами

Есть проект парсера грамматик с двухсторонними контекстами и лексера https://github.com/ilvivl/TwoSidedContextParser, преобразующего вход на Си для анализа программ как строк. Нужно:

0. проверить лексер на работоспособность, написать тесты

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

2. придумать методику и написать C++ "обвязку" для анализа программы

Для мотивации: https://arxiv.org/abs/1405.5598

*-- не обязательно