Методы определения входных данных, обеспечивающих эффективное тестирование программ

• Автор: Яковлев, Юрий Александрович
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Санкт-Петербург
• Количество страниц: 265 с. : ил.

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

1.1. Определение и цели тестирования.

1.2. Программа и ее структурная модельуправляющий граф

1.3. Покрытие и критерии тестирования

1.3.1. Критерии структурного тестирования

1.3.1.1. Критерии потока управления.

1.3.1.2. Критерии потока данных.

1.3.1.3. Мутационные критерии.

1.3.1.4. Отношение включения
1.4. Взаимосвязь степени структурного покрытия и надежности программы
1.5. Задача генерации входных тестовых данных
1.6. Структурные методы
1.6.2. Статические методы
1.6.2.1. Метод символьного выполнения.
1.6.2.2. Метод тестирования на основе ограничений.
1.6.2.3. Метод динамического сокращения областей значений.
1.6.3. Динамические методы.
1.6.3.1. Метод случайного тестирования
1.6.3.2. Методы поиска тестовых данных на основе локального и глобального поиска.
1.6.3.2.1. Метод МиллераСпунера
1.6.3.2.2. Метод Б. Корела метод вариации переменной
1.6.3.2.3. Цельориентированный подход на основе локального поиска
1.6.3.2.4. Цепочечный подход
1.6.3.2.5. Моделирование отжига.
1.6.3.2.6. Генетические алгоритмы.
1.6.3.3. Метод последовательной релаксации
1.7. Постановка задачи
1.8. Выводы.
ГЛАВА 2. УСОВЕРШЕНСТВОВАНИЕ МЕТОДОВ ГЕНЕРАЦИИ ВХОДНЫХ
ДАННЫХ.
2.1. Характеристики методов генерации тестовых данных
2.1.4. Количественные характеристики.
2.1.5. Качественные характеристики.
2.4. Выводы
ГЛАВА 3. ВСПОМОГАТЕЛЬНЫЕ АЛГОРИТМЫ ДЛЯ ГЕНЕРАЦИИ ТЕСТОВЫХ ДАННЫХ
3.1. Обзор вспомогательных алгоритмов для генерации тестовых данных
3.2. Построение управляющего графа из исходного текста программы.
3.3. Алгоритм формирования набора путей, обеспечивающих покрытие по заданному критерию
3.4. Алгоритм инструментации программы
2.2. Улучшение качественных характеристик.
2.2.6. Обработка строк в методах генерации, разработанных для работы с числовыми данными
2.2.6.1. Определение длины строки
2.2.6.2. Сравнение двух строк
2.2.6.3. Конкатенация двух строк.
2.2.6.4. Извлечение подстроки
2.2.6.5. Свойства операций над строками
2.2.6.6. Общий алгоритм адаптации метода для работы со строковыми данными
. .6.7. Адаптация метода последовательной релаксации для работы со строковыми данными.
2.2.7. Генерация входных тестовых данных процедурных типов
2.3. Улучшение количественных характеристик.
.1.1. Адаптация метода релаксации для обработки дуговых функций кусочнолинейного вида.
3.5. Алгоритм построения линейного варианта программы
3.6. Выводы
ГЛАВА 4. ПРОГРАММНАЯ СИСТЕМА ГЕНЕРАЦИИ ТЕСТОВЫХ ДАННЫХ
4.1. Обзор существующих систем генерации тестовых данных.
4.2. Общая структура разработанной программной системы.
4.3. Модуль синтаксического анализа
4.4. Модуль построения управляющего графа
4.5. Модули визуализации.
4.6. Модуль построения набора требуемых путей
4.7. Модули инструментации и построения линейных вариантов программы
4.8. Модули компиляции, выполнения тестируемых программ и сф
вспомогательные модули 1
4.9. Модуль алгоритмов нахождения тестовых данных.
4 Модуль верификации
4 Результаты применения программной системы.
4 Выводы
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Критерий аіі-р-шез/зоте-с-шез: критерий выполняется, если Р включает в себя все пути от каждого определения переменной до ее р-иБе-использования. Если определению переменной не соответствует ни одного р-изе-использования, то Р должен включает в себя путь до некоторого с-иБе-использования этой переменной. Критерий аіі-сіи-раїй выполняется, если Р включает в себя все пути-от. Одним из подходов к тестированию является мутационный подход, при котором на основе тестируемой программы путем добавления одиночных ошибок создаются ее неправильные варианты - «мутанты»[]. В таком случае решается задача нахождения таких входных данных, на которых результат работы мутантов отличался бы от результата работы исходной программы. Таким образом, приведенные ниже слабомутационные критерии предназначены для обнаружения неправильного использования арифметических операций и имен переменных и требуют построения такого набора тестов, который позволил бы выявить все такие неточности. Критерий слабой мутации арифметических операций. Для данного критерия программы-мутанты получаются из исходной программы заменой одного из арифметических операторов другим. Критерий слабой мутации имен переменных. Для данного критерия программы-мутанты получаются из исходной программы заменой вхождения одной переменной на другую с тем же типом и областью действия. Пусть С| и С2 - некоторые критерии тестирования. Критерий С1 включает в себя критерий С2, если для всех программ и тестовых наборов выполнение С1 подразумевает выполнение С2. Упорядочив критерии тестирования в соответствии с отношением включения, можно построить иерархию критериев, наглядно представляющую относительную "силу" и "слабость" критериев в смысле строгости требований к покрытию элементов программы. Данная иерархия представлена на Рис. Рис. Чем больше степень покрытия программы, тем выше вероятность обнаружения существующих ошибок и тем больше надежность программы, о которой свидетельствует отсутствие ошибок. При этом применение различных тестовых критериев направлено на выявление ошибок соответствующего типа. В общем случае задача генерации тестовых данных состоит в нахождении такого множества наборов входных данных, что при выполении программы на них был бы удовлетворен заданный критерий тестирования. В случае структурного подхода критерий задает элементы структуры, которбые необходимо покрыть (пройти). Тогда в значительной части случаев задача может быть сведена к нахождению входных данных, на которых будет пройден заданный путь или выполнен заданный оператор. Существующие на настоящий момент методы решения данной задачи можно представить в виде схемы на Рис. Путь-ориентир. Корел ! Цепочечный 1 1 ) генетич. Рис. Существует несколько принципов классификации автоматизированных методов нахождения входных данных при структурном тестировании. В зависимости от того, используется ли реальное исполнение тестируемой программы, выделяют динамические и статические методы. В зависимости от того, является ли задачей метода прохождение программы по заданному пути или выполнение заданного оператора, выделяют путь-ориснтированные и цель-ориентированные методы. Ниже более подробно описаны методы в соответствии с приведенной классификацией. Статические методы нахождения тестовых данных основаны на анализе внутренней структуры тестируемой программы и не требуют ее выполнения. Они используют символьное исполнение, то есть процесс обхода заданного пути , в управляющем графе и построения символьного представления значений внутренних переменных как выражений, содержащих только входные переменные. К статическим методам относятся собственно символьное исполнение [,,], метод ограничений и метод динамического уменьшения областей значений. В результате символьного исполнения на основании выражений, определяющих условия перехода по заданным дугам управляющего графа для ветвлений, строится система ограничений по отношению к входным переменным. На входных переменных, удовлетворяющих этой системе, и будет пройден заданный путь. Если система неразрешима, то путь является нереализуемым.