АННОТАЦИЯ 3
ВВЕДЕНИЕ 4
1 Постановка задачи 5
2 Обзор 6
3 Списочные структуры данных 8
3.1 Линейный односвязный список 8
3.2 Списочная структура «дерево» 9
4 Операции над списочными структурами 11
4.1 Добавление нового элемента в список 11
4.1.1 Добавление нового элемента в указанное место в списке 11
4.1.2 Добавление элемента в начало списка 13
4.1.3 Добавление элемента в конец списка 15
4.2 Удаление элемента из списка 16
4.2.1 Удаление указанного элемента из списка 16
4.2.2 Удаление первого элемента списка 19
4.2.3 Удаление последнего элемента списка 20
5 Логическая формула 2КНФ как модель ориентированного графа 22
6 Принцип и порядок формирования булевой формулы и графа для линейного
односвязного списка 24
6.1 Создание переменной-указатель и первого элемента списка 24
6.2 Операция “Добавление элемента в начало списка” 25
6.3 Операция “Добавление элемента в конец списка” 26
6.4 Операция “Добавление элемента в указанное место в списке” 27
6.5 Операция “Удаление указанного элемента из списка” 29
6.6 Операция “Удаление последнего элемента списка” 30
6.7 Операция “Удаление первого элемента списка” 31
6.8 Операция «Разделение линейного односвязного списка на два независимых списка» 32
6.9 Операция «Объединение двух независимых линейных односвязных списков» 34
6.10 Операция “Присвоение нового значения переменной-указателю Head”. Разбор и
устранение утечки памяти 36
7 Принцип и порядок формирования булевой формулы и графа для древовидной
структуры данных 38
8 Алгоритм анализа программного кода 40
8.1 Таблица соответствия 41
8.2 Архитектура анализатора 42
8.3 Результат работы алгоритма 43
ЗАКЛЮЧЕНИЕ 50
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 51
ПРИЛОЖЕНИЕ А Пример кода, представленный в json формате, передаваемый анализатору 53
ПРИЛОЖЕНИЕ Б Листинг программного кода 57
ПРИЛОЖЕНИЕ В Полная таблица соответствия 60
Тестирование и верификация программного обеспечения (далее - ПО) - это одни из важнейших этапов в рамках жизненного цикла ПО.
Верификация - это вид деятельности, направленный на контроль качества ПО и обнаружение ошибок. Она проверяет соответствие одних информационных сущностей, документов и моделей, создаваемых в ходе разработки и сопровождения ПО другим, ранее созданным или используемым в качестве исходных данных, а также соответствие этих информационных сущностей и процессов их разработки правилам, нормам стандартов и описанию требований (техническому заданию). Ошибки, допущенные на стадии верификации ПО, могут привести к ощутимым затратам в будущем.
В настоящий момент известно много различных методов верификации и тестирования, которые можно выделить в следующие группы: экспертиза, статический анализ, формальные методы, динамические методы, синтетические методы.
Остановимся подробнее на двух подходах к тестированию и верификации ПО: динамическом и статическом.
Динамический метод предполагает выявление неисправностей, ошибок на основании реальной работы ПО, или отдельных его модулей, компонентов. Следствием этого является необходимость наличия работающей программы, из -за чего отсутствует возможность использования данного подхода на ранних этапах разработки.
Статический анализ используется для обнаружения ошибок без реального запуска ПО путём проверки соответствия компонентов ПО специальным формализованным правилам и некоторым часто встречающимся шаблонам. Данный подход хорошо автоматизируется, использованием доступных инструменты [5, 6, 7. 8].
Языки программирование, такие как С и C++, дают огромные возможности по управлению памятью. Но свобода действий над динамическими структурами нередко приводит к утечкам памяти [12]. Утечки памяти - это безвозвратная потеря доступа к тому или иному участку динамической памяти и невозможность освобождения памяти из - под таких участков. Если не уделять должного внимания такие потери могут привести к аварийному закрытию программы. Так как такие ошибки являются логическим дефектом, то их обнаружение невозможно на уровне компиляции программы, они проявляются в момент работы программы. Выявления подобных дефектов программы возможно с помощью методов статического анализа.
В рамках дипломной работы разработан алгоритм статического анализа программного кода, позволяющий обнаруживать утечки памяти в динамических структурах списочного типа. Предлагаемое решение основано на формировании логической формулы 2КНФ для анализируемого участка кода и решении 2SAT-задачи. Разработаны специальные правила, позволяющие обеспечить важное свойство для 2SAT- задачи, такое как сильно-связность графа, являющегося интерпретацией списочной структуры, при этом не нарушающие операции, проводимые над списочными структурами, но позволяющие обнаружить нарушение связей.
Предложенный подход программно реализован в виде анализатора, обеспечивающего выполнение этапов алгоритма анализа. В результате, анализатор способен указать утерянные элементы динамической структуры списочного типа, а в качестве результата и выводит пользователю массив строк, указывающих на область программного кода, в котором обнаружена утечка памяти.
