АННОТАЦИЯ 4
ОГЛАВЛЕНИЕ 6
ВВЕДЕНИЕ 7
1 Динамические списочные структуры данных 9
1.1 Однонаправленный линейный список 9
1.2 Двунаправленный линейный список 10
2 Утечки памяти 11
3 Методы статического анализа 17
4 Анализ работы существующих статических анализаторов 18
4.1 Описание статических анализаторов 18
4.2 Пример анализа программы PVS-studio 20
4.3 Выводы анализа утилит 22
5 Предложенный метод статического анализа 24
5.1 Вспомогательный граф, описывающий поведение кучи 24
5.2 Три линейных множества, используемые при анализе вспомогательного графа 26
6 Алгоритм поиска утечек памяти 28
6.1 Алгоритм формирования множеств и вывода 31
6.2 Примеры работы алгоритма на односвязных списках 32
6.3 Примеры работы алгоритма на двухсвязных списках 37
6.4 Итог анализа вспомогательных методов списочных структур 42
7 Алгоритм статического анализа списочных структур. Практическая реализация 43
8 Результаты алгоритма 46
ЗАКЛЮЧЕНИЕ 50
СПИСОК ЛИТЕРАТУРЫ 51
ПРИЛОЖЕНИЕ A 52
Файл test.cpp 52
Файл test1.cpp 53
Файл test2.cpp 54
ПРИЛОЖЕНИЕ Б 55
Файл main.cpp 55
Файл main1.cpp 56
Разработка программного обеспечения подразумевает работу над большим объемом данных, написание кода, который в свою очередь должен решать задачи, связанные с обработкой потенциальных уязвимостей. Как следствие, с увеличением сложности проекта, увеличивается объема обрабатываемой информации, с которой разработчику необходимо работать. Это неизбежно приводит к увеличению количества ошибок в проекте или вероятности их появления.
Для того чтобы значительно сократить количество ошибок в проекте, программисту необходимо провести кропотливую работу над их обнаружением. Но у данного вида анализа есть существенные недостатки:
Человеческий фактор: всегда существует вероятность, что человек, который проводит анализ, может допустить ошибку или пропустить определенный участок кода по тем или иным причинам;
Большое количество времени, затраченное на поиск уязвимостей.
Но, так или иначе, на сегодняшний день лучшим вариантом, осуществляющим анализ кода и оценку уровня качества разрабатываемого программного обеспечения, остается человек. Так как программист может найти такого рода уязвимости, которые та или иная программа не смогла обнаружить.
Также многие виды ошибок находятся благодаря assert, где это в свою очередь конструкция, позволяющая проверять предположения о значениях произвольных данных в произвольном месте программы, также с предупреждениями со стороны, интегрированной средой разработки, сборкой проекта разными компиляторами под разные операционные системы. Но даже при использовании всех этих мер ошибки часто остаются незамеченными. Компромиссным решением является использование вспомогательных инструментов статического анализа кода.
Начнем с того, что статический анализ кода - это инструмент для выявления ошибок и потенциальных уязвимостей в исходном коде программы. Статические анализаторы способны обнаруживать достаточно широкий спектр ошибок:
Неверный синтаксис, разыменование нулевого указателя, выход за границу массива, некорректные операции сдвига и т.п.;
Потенциальные уязвимости (Common Weakness Enumeration).
Среди прочих ошибок, статический анализатор может обнаруживать утечки памяти.
Утечка ресурсов может возникать при неправильной работе с динамическими структурами данных - забыли освободить память, неправильно перезаписали объект структуры и т. п.
Динамические структуры это в первую очередь тот объём данных, который занимает определенное место в памяти и не является фиксированным. Динамические структуры характеризуются тем, что память выделяется в процессе программы (размерность структуры может изменяться), количество элементов или объектов в структурах не фиксированное и вполне возможно изменение связей между элементами структур.
И нарушение работы с динамическими структурами ведёт к нарушению работы с памятью.
В работе предлагается метод статического анализа для обнаружения утечек ресурсов в динамических списочных структурах, в частности односвязных и двухсвязных списках.
В методе предлагается моделирование кучи с помощью трех множеств: память, рабочая среда и результат. На основании исходного кода программы строится графовая структура, позволяющая отследить состояние связей в процессе моделирования работы программы и по ее завершению. После того, как анализ динамической структуры завершится, и найдутся вершины во вспомогательном графе, которые не имеют связей, следующим этапом можно будет отследить историю изменений состояния вершин в модели работы динамической памяти. Благодаря данному анализу результатом будут строки, где были совершены утечки.
По материалам исследования был сделан доклад на конференции:
IX Международная молодежная научная конференция
«Математическое и программное обеспечение информационных, технических и экономических систем». Томск, 26-28 мая 2022 г.
