ОБНАРУЖЕНИЕ УТЕЧКИ ПАМЯТИ В СПИСОЧНЫХ СТРУКТУРАХ МЕТОДОМ СТАТИЧЕСКОГО АНАЛИЗА

Реферат
ВВЕДЕНИЕ 6
1 Статический анализ 8
Библиотека libclang 9
2 Динамические структуры 11
2.1 Основные разновидности динамических структур списочного типа 11
2.1.1 Односвязный список 11
2.1.2 Двусвязный список 12
2.1.3 Список произвольной вложенности 12
2.2 Связность элементов динамической памяти 13
3 Утечки ресурсов 14
Операции, приводящие к утечкам ресурсов 14
4 Символьное выполнение 18
4.1 Модель кучи 18
4.2 Модель программы 20
4.3 Множество путей выполнения программы 21
5 Анализ инструментов статического анализа 23
Утилита Predator 23
6 Алгоритм поиска утечек памяти 29
7 Статический анализатор 37
7.1 Модули и компоненты программы 37
7.1.1 Классы внутреннего представления программы 37
7.1.1.1 Переменная 37
7.1.1.2 Объект памяти 38
7.1.1.3 Адрес 39
7.1.1.4 Тип 40
7.1.1.5 Пользовательский тип 40
7.1.1.6 Функция 41
7.1.2 Модули поиска утечки памяти 42
7.1.2.1 Перевод программы во внутренний формат 42
7.1.2.2 Формирование всех возможных путей выполнения программы 43
7.1.2.3 Символьное выполнение 44
7.2 Проверка связности элементов 47
7.3 Ограничения в работе программы 51
8 Представление результатов работы 52
ЗАКЛЮЧЕНИЕ 55
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ 56
ПРИЛОЖЕНИЕ А 57
Листинг А1 57
Листинг А2 59
ПРИЛОЖЕНИЕ Б 65
Листинг Б1 65
Листинг Б2 65
ПРИЛОЖЕНИЕ В 67
Архитектура приложения 67
Купить

Разработка программного обеспечения - это длительный, трудоемкий процесс, который, как правило, разбивается на этапы. Чем сложнее разрабатываемый продукт, тем более детальное проектирование требуется провести, прежде чем приступить к конструированию программы. Как следствие, с увеличением сложности проекта, увеличивается объем информации, с которой разработчику приходится работать одновременно. Это неизбежно приводит к увеличению количества ошибок, допускаемых в процессе написания кода. Наилучшим средством обнаружения ошибок в больших проектах принято считать обзор кода, проводимый другими программистами, т.к. программисты гораздо легче замечают ошибки в чужом коде. Однако, у этого подхода есть существенный недостаток - это его цена. Во-первых, - это отрывает от работы сразу несколько человек. Во-вторых, такой подход отнимает большое количество времени у разработчиков, поскольку возникает необходимость делать регулярные перерывы на отдых. Если же пытаться делать обзоры больших фрагментов кода, то внимание быстро притупляется и польза от такого подхода сходит на нет. Компромиссным решением являются инструменты статического анализа кода. Эти инструменты обращают внимание программиста на определенные участки кода. Разумеется, программа не может заменить полноценного обзора кода, выполняемого коллективом программистов. Однако соотношение польза/цена делает использование статического анализа весьма полезной практикой, применяемой многими компаниями.
Статические анализаторы способны обнаруживать достаточно широкий спектр ошибок. К ним относятся, например, выход за границу массива, ошибка в имени переменной, последствия невнимательного copy-paste и т.д. Среди всех прочих ошибок, статические анализаторы способны обнаруживать утечки памяти. Ошибки, связанные с памятью трудно обнаружимы и могут находиться в местах, которым не уделяется достаточно, для их обнаружения, времени при тестировании. В данном случае, статический анализатор может существенно облегчить процесс поиска таких ошибок.
Причина возникновения в программах утечек памяти кроется в неправильной работе с динамической памятью, с перезаписью объектов программы через которые осуществляется доступ к элементам динамической памяти или не внимательность при реализации части программы, выполняющей освобождение объектов динамической памяти. С динамической памятью тесно связаны рекурсивно определенные структуры. Особенность этих структур заключается в том, что они внутри себя содержат ссылки на структуры такого же типа. Как правило, элементы таких структур размещаются в динамической памяти, а доступ к ним осуществляется по адресу ячейки памяти, в которую они были размещены. Одними из типов таких структур являются списочные структуры. Работа с такими структурами предполагает большое количество операторов осуществляющих работу с динамической памятью.
В настоящее время, обнаружению утечек памяти посвящено множество работ[1][2], в том числе предлагающих решение на основе методов статического анализа[3]. Одним из таких методов является метод символьного выполнения программы. Ключевая идея этого метода заключается в моделировании динамической памяти (или другими словами кучи) на основе информации полученной в результате статического анализа исходного кода программы. Данный подход используется в предлагаемом в данной работе решении.
Данная работа посвящена обнаружению утечек памяти в программах на языке C+ + использующих списочные структуры методом статического анализа.
Цель и задачи работы: разработка статического анализатора исходного кода обнаруживающего утечки памяти в программах использующих динамические структуры списочного типа. В ходе выполнения работы были поставлены и решены следующие задачи:
1. Выделить основные свойства динамических структур списочного типа;
2. Исследовать метод статического анализа для поиска утечек памяти;
3. Проанализировать существующие инструменты статического анализа, которые могут обнаруживать утечки памяти;
4. Определить набор операций, которые приводят к утечкам памяти в программах использующих динамические структуры списочного типа;
5. Построить модели анализируемой программы и динамической памяти;
6. Разработать алгоритм обнаружения утечек памяти, в программах использующих динамические структуры списочного типа;
7. Разработать программный инструментарий, выполняющий статический анализ исходного кода программы и указывающий на участки кода содержащие операторы, приводящие к утечкам памяти.
Купить