СТАТИЧЕСКОЕ ТЕСТИРОВАНИЕ ДИНАМИЧЕСКИХ СТРУКТУР ДАННЫХ

АННОТАЦИЯ 3
ВВЕДЕНИЕ 7
Постановка задачи 8
1 Методы статического тестирования 9
1.1 Инструменты статического тестирования 10
1.2 Анализ операций над связями в динамических структурах 11
1.3 Результаты экспериментов 13
2 Структура для моделирования операций со связями 15
2.1 Правила построения графа G и моделирования операций 16
3 Обнаружение операций, приводящих к обрыву связей 19
3.1 Классификация обнаруживаемых ошибок 19
3.2 Алгоритм моделирования операций над связями 20
3.3 Алгоритм обнаружения обрыва связей 27
4 Описание ПО 29
4.1 Архитектура статического анализатора списочных структур 29
4.2 Модуль построения графа G 30
4.3 Интерфейс и отображение номеров строк 33
5 Эксперименты. Анализ результатов 36
ЗАКЛЮЧЕНИЕ 39
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
Купить

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

Купить