Статический анализ играет важную роль в задаче поиска ошибок в коде. Однако многие из методов статического анализа основаны на сопоставлении участков кода с некоторым шаблоном: если участок кода соответствует шаблону, считается, что он содержит ошибку. Такой подход может приводить как к пропуску существующих ошибок, так и выдаче ложных предупреждений. Алгоритмы статического анализа, которые выделяют ошибки на основе различных свойств программы, например, контекстов вызова и потока управления, позволяют обнаруживать больше истинных ошибок и сообщать меньше ложных предупреждений.
Многие виды статического анализа могут быть сформулированы как задача контекстно-свободной (КС) достижимости. Один из примеров — анализ псевдонимов (анализ указателей). Он позволяет обнаруживать использование освобождённой памяти, взаимные блокировки и обращение к выделенной памяти через тип с несоответствующим размером. Ещё один пример — Points-to анализ, учитывающий поля, особенностью которого являются большие грамматики, используемые для анализа.
Существует множество алгоритмов, решающих задачу КС- достижимости. Среди них можно выделить алгоритмы, основанные на операциях линейной алгебры, так как такие операции хорошо поддаются распараллеливанию. В исследовании Никиты Мишина и др. был произведён сравнительный анализ времени работы нескольких реализаций матричного алгоритма Рустама Азимова, основанных на различных специализированных матричных библиотеках. Однако графы, на которых проводилось исследование, значительно меньше получаемых по исходному коду для статического анализа.
В данной работе предлагается изучить различные алгоритмы КС- достижимости в графах и сравнить их производительность на больших графах, полученных по реальным программам.
1. Постановка задачи
Целью данной работы является экспериментальное исследование алгоритмов КС-достижимости в задаче статического анализа кода.
Для достижения цели были поставлены следующие задачи.
1. Рассмотреть возможность применения алгоритмов, основанных на операциях линейной алгебры, для Points-to анализа, учитывающего поля, и предложить модификацию алгоритма, подходящую для этого анализа.
2. Оптимизировать реализации алгоритмов, основанных на операциях линейной алгебры.
3. Провести замеры производительности алгоритмов, основанных на операциях линейной алгебры, на графах, полученных по реальным программам, сравнить их с другими алгоритмами КС- достижимости.
В ходе работы были достигнуты следующие результаты.
• Предложена модификация тензорного алгоритма для Points-to анализа, учитывающего поля, показавшая наилучшее время работы на небольших графах среди алгоритмов, основанных на операциях линейной алгебры. Однако эксперименты показали, что из-за большого потребления памяти алгоритм практически неприменим для данного вида анализа.
• Оптимизирована реализация матричного алгоритма из библиотеки CFPQ_PyAlgo, эффективность оптимизации экспериментально проверена.
• Проведены замеры производительности реализаций алгоритмов КС-достижимости, которые показали, что алгоритмы, основанные на операциях линейной алгебры, достаточно эффективны для анализа псевдонимов, но из-за больших размеров грамматики малоэффективны для Points-to анализа, учитывающего поля.
Так как реализации алгоритма, основанного на произведении Кро- некера, и его вариации плохо применимы для Points-to анализа, учитывающего поля, в силу очень большого объёма потребляемой памяти под пересечение графа и рекурсивного автомата, в дальнейшем можно рассмотреть следующие шаги по оптимизации матричного алгоритма для применения его к данному типу анализа.
• Разработка инкрементальной версии матричного алгоритма, в которой полученные на предыдущих итерациях данные не будут пересчитываться в дальнейшем, что позволит сократить затрачиваемое на умножение матриц время.
• Специализация матричного алгоритма для данного анализа, не требующего перевода грамматики в ОНФХ и вычисления достижимости для нетерминала FlowsTo непосредственно, что позволит значительно сократить количество перемножений матриц.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
