📄Работа №142478
Тема: Экспериментальное исследование алгоритмов контекстно-свободной достижимости применительно к задачам статического анализа кода
Тип работы
Дипломные работы, ВКР
Предмет
программирование
Объем:
32 листов
Год:
2023
Просмотров:
149
4800
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 4
1. Постановка задачи 5
2. Обзор 6
2.1. Терминология 6
2.2. Анализ псевдонимов 8
2.3. Points-to анализ, учитывающий поля 10
2.4. Алгоритмы КС-достижимости, основанные на операциях
линейной алгебры 11
2.4.1. Матричный алгоритм 11
2.4.2. Тензорный алгоритм 12
2.4.3. Инкрементальная версия тензорного алгоритма . 13
2.5. Исследуемые реализации 15
3. Адаптация тензорного алгоритма для Points-to анализа,
учитывающего поля 16
3.1. Применение модификации для анализа псевдонимов ... 18
3.2. Особенности реализации 19
4. Оптимизация реализации матричного алгоритма 22
5. Эксперименты 23
5.1. Тестовый стенд 23
5.2. Тестовые данные 23
5.3. Замеры времени работы и потреблетния памяти 23
5.4. Оптимизация реализации матричного алгоритма 25
5.5. Сравнение алгоритмов КС-достижимости 26
Заключение 30
Список литературы 31
1. Постановка задачи 5
2. Обзор 6
2.1. Терминология 6
2.2. Анализ псевдонимов 8
2.3. Points-to анализ, учитывающий поля 10
2.4. Алгоритмы КС-достижимости, основанные на операциях
линейной алгебры 11
2.4.1. Матричный алгоритм 11
2.4.2. Тензорный алгоритм 12
2.4.3. Инкрементальная версия тензорного алгоритма . 13
2.5. Исследуемые реализации 15
3. Адаптация тензорного алгоритма для Points-to анализа,
учитывающего поля 16
3.1. Применение модификации для анализа псевдонимов ... 18
3.2. Особенности реализации 19
4. Оптимизация реализации матричного алгоритма 22
5. Эксперименты 23
5.1. Тестовый стенд 23
5.2. Тестовые данные 23
5.3. Замеры времени работы и потреблетния памяти 23
5.4. Оптимизация реализации матричного алгоритма 25
5.5. Сравнение алгоритмов КС-достижимости 26
Заключение 30
Список литературы 31
📖 Введение
Статический анализ играет важную роль в задаче поиска ошибок в коде. Однако многие из методов статического анализа основаны на сопоставлении участков кода с некоторым шаблоном: если участок кода соответствует шаблону, считается, что он содержит ошибку. Такой подход может приводить как к пропуску существующих ошибок, так и выдаче ложных предупреждений. Алгоритмы статического анализа, которые выделяют ошибки на основе различных свойств программы, например, контекстов вызова и потока управления, позволяют обнаруживать больше истинных ошибок и сообщать меньше ложных предупреждений.
Многие виды статического анализа могут быть сформулированы как задача контекстно-свободной (КС) достижимости. Один из примеров — анализ псевдонимов (анализ указателей). Он позволяет обнаруживать использование освобождённой памяти, взаимные блокировки и обращение к выделенной памяти через тип с несоответствующим размером. Ещё один пример — Points-to анализ, учитывающий поля, особенностью которого являются большие грамматики, используемые для анализа.
Существует множество алгоритмов, решающих задачу КС- достижимости. Среди них можно выделить алгоритмы, основанные на операциях линейной алгебры, так как такие операции хорошо поддаются распараллеливанию. В исследовании Никиты Мишина и др. был произведён сравнительный анализ времени работы нескольких реализаций матричного алгоритма Рустама Азимова, основанных на различных специализированных матричных библиотеках. Однако графы, на которых проводилось исследование, значительно меньше получаемых по исходному коду для статического анализа.
В данной работе предлагается изучить различные алгоритмы КС- достижимости в графах и сравнить их производительность на больших графах, полученных по реальным программам.
1. Постановка задачи
Целью данной работы является экспериментальное исследование алгоритмов КС-достижимости в задаче статического анализа кода.
Для достижения цели были поставлены следующие задачи.
1. Рассмотреть возможность применения алгоритмов, основанных на операциях линейной алгебры, для Points-to анализа, учитывающего поля, и предложить модификацию алгоритма, подходящую для этого анализа.
2. Оптимизировать реализации алгоритмов, основанных на операциях линейной алгебры.
3. Провести замеры производительности алгоритмов, основанных на операциях линейной алгебры, на графах, полученных по реальным программам, сравнить их с другими алгоритмами КС- достижимости.
Многие виды статического анализа могут быть сформулированы как задача контекстно-свободной (КС) достижимости. Один из примеров — анализ псевдонимов (анализ указателей). Он позволяет обнаруживать использование освобождённой памяти, взаимные блокировки и обращение к выделенной памяти через тип с несоответствующим размером. Ещё один пример — Points-to анализ, учитывающий поля, особенностью которого являются большие грамматики, используемые для анализа.
Существует множество алгоритмов, решающих задачу КС- достижимости. Среди них можно выделить алгоритмы, основанные на операциях линейной алгебры, так как такие операции хорошо поддаются распараллеливанию. В исследовании Никиты Мишина и др. был произведён сравнительный анализ времени работы нескольких реализаций матричного алгоритма Рустама Азимова, основанных на различных специализированных матричных библиотеках. Однако графы, на которых проводилось исследование, значительно меньше получаемых по исходному коду для статического анализа.
В данной работе предлагается изучить различные алгоритмы КС- достижимости в графах и сравнить их производительность на больших графах, полученных по реальным программам.
1. Постановка задачи
Целью данной работы является экспериментальное исследование алгоритмов КС-достижимости в задаче статического анализа кода.
Для достижения цели были поставлены следующие задачи.
1. Рассмотреть возможность применения алгоритмов, основанных на операциях линейной алгебры, для Points-to анализа, учитывающего поля, и предложить модификацию алгоритма, подходящую для этого анализа.
2. Оптимизировать реализации алгоритмов, основанных на операциях линейной алгебры.
3. Провести замеры производительности алгоритмов, основанных на операциях линейной алгебры, на графах, полученных по реальным программам, сравнить их с другими алгоритмами КС- достижимости.
✅ Заключение
В ходе работы были достигнуты следующие результаты.
• Предложена модификация тензорного алгоритма для Points-to анализа, учитывающего поля, показавшая наилучшее время работы на небольших графах среди алгоритмов, основанных на операциях линейной алгебры. Однако эксперименты показали, что из-за большого потребления памяти алгоритм практически неприменим для данного вида анализа.
• Оптимизирована реализация матричного алгоритма из библиотеки CFPQ_PyAlgo, эффективность оптимизации экспериментально проверена.
• Проведены замеры производительности реализаций алгоритмов КС-достижимости, которые показали, что алгоритмы, основанные на операциях линейной алгебры, достаточно эффективны для анализа псевдонимов, но из-за больших размеров грамматики малоэффективны для Points-to анализа, учитывающего поля.
Так как реализации алгоритма, основанного на произведении Кро- некера, и его вариации плохо применимы для Points-to анализа, учитывающего поля, в силу очень большого объёма потребляемой памяти под пересечение графа и рекурсивного автомата, в дальнейшем можно рассмотреть следующие шаги по оптимизации матричного алгоритма для применения его к данному типу анализа.
• Разработка инкрементальной версии матричного алгоритма, в которой полученные на предыдущих итерациях данные не будут пересчитываться в дальнейшем, что позволит сократить затрачиваемое на умножение матриц время.
• Специализация матричного алгоритма для данного анализа, не требующего перевода грамматики в ОНФХ и вычисления достижимости для нетерминала FlowsTo непосредственно, что позволит значительно сократить количество перемножений матриц.
• Предложена модификация тензорного алгоритма для Points-to анализа, учитывающего поля, показавшая наилучшее время работы на небольших графах среди алгоритмов, основанных на операциях линейной алгебры. Однако эксперименты показали, что из-за большого потребления памяти алгоритм практически неприменим для данного вида анализа.
• Оптимизирована реализация матричного алгоритма из библиотеки CFPQ_PyAlgo, эффективность оптимизации экспериментально проверена.
• Проведены замеры производительности реализаций алгоритмов КС-достижимости, которые показали, что алгоритмы, основанные на операциях линейной алгебры, достаточно эффективны для анализа псевдонимов, но из-за больших размеров грамматики малоэффективны для Points-to анализа, учитывающего поля.
Так как реализации алгоритма, основанного на произведении Кро- некера, и его вариации плохо применимы для Points-to анализа, учитывающего поля, в силу очень большого объёма потребляемой памяти под пересечение графа и рекурсивного автомата, в дальнейшем можно рассмотреть следующие шаги по оптимизации матричного алгоритма для применения его к данному типу анализа.
• Разработка инкрементальной версии матричного алгоритма, в которой полученные на предыдущих итерациях данные не будут пересчитываться в дальнейшем, что позволит сократить затрачиваемое на умножение матриц время.
• Специализация матричного алгоритма для данного анализа, не требующего перевода грамматики в ОНФХ и вычисления достижимости для нетерминала FlowsTo непосредственно, что позволит значительно сократить количество перемножений матриц.
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.