Реализация анализа указателей для Java на основе достижимости с контекстно-свободными ограничениями

Широкий спектр различных вариаций задачи анализа указателей может быть выражен через достижимость с контекстно-свободными ограничениями (можно, например, взглянуть на раздел 4 в работе Ильи Муравьёва Optimization of the Context-Free Language Reachability Matrix-Based Algorithm).

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

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

Требования к студенту
  • Отличное знание языков программирования Kotlin и Java.
  • Хорошие знания основ теории графов: ориентированные графы с метками на рёбрах, обходы графов, задачи поиска путей в графе.
  • Хорошие знания теории формальных языков: контекстно-свободные грамматики, выводимость в грамматиках, дерево вывода.
  • Хорошие навыки постановки экспериментов: подготовка данных и окружения, автоматизация процесса, статистическая обработка данных, анализ результатов.
Уровень

3 курс, Бакалаврская ВКР


Руководитель

Григорьев Семен Вячеславович


Консультант

Grigorev Semyon


Источник

Кафедра системного программирования СПбГУ