Содержание к диссертации
СОДЕРЖАНИЕ 2
ВВЕДЕНИЕ 5
ГЛАВА 1. ОБЗОР МЕТОДОВ АВТОМАТИЧЕСКОЙ ГЕНЕРАЦИИ
ВХОДНЫХ ДАННЫХ ДЛЯ СТРУКТУРНОГО ТЕСТИРОВАНИЯ ПРОГРАММ
11
-
Определение и цели тестирования 11
-
Программа и ее структурная модель - управляющий граф 14
-
Покрытие и критерии тестирования 15
1.3.1. Критерии структурного тестирования 16
-
Критерии потока управления 16
-
Критерии потока данных 18
-
Мутационные критерии .19
-
Отношение включения 20
-
Взаимосвязь степени структурного покрытия и надежности программы21
-
Задача генерации входных тестовых данных 22
-
Структурные методы 24
1.6.2. Статические методы 24
-
Метод символьного выполнения 24
-
Метод тестирования на основе ограничений 26
-
Метод динамического сокращения областей значений 30
1.6.3. Динамические методы 32
-
Метод случайного тестирования 32
-
Методы поиска тестовых данных на основе локального и глобального поиска 33
-
Метод Миллера-Спунера 34
-
Метод Б. Корела (метод вариации переменной) 36
-
Цель-ориентированный подход на основе локального поиска 41
-
Цепочечный подход 43
-
Моделирование отжига 46
-
Генетические алгоритмы 47
1.6.3.3. Метод последовательной релаксации 50
-
Постановка задачи 57
-
Выводы 57
ГЛАВА 2. УСОВЕРШЕНСТВОВАНИЕ МЕТОДОВ ГЕНЕРАЦИИ ВХОДНЫХ
ДАННЫХ 59
2.1. Характеристики методов генерации тестовых данных 59
-
Количественные характеристики 59
-
Качественные характеристики 63
2.2. Улучшение качественных характеристик 66
2.2.6. Обработка строк в методах генерации, разработанных для работы с
числовыми данными 66
-
Определение длины строки 68
-
Сравнение двух строк 70
-
Конкатенация двух строк 74
-
Извлечение подстроки 75
-
Свойства операций над строками ...78
-
Общий алгоритм адаптации метода для работы со строковыми данными
. 2.2.6.7. Адаптация метода последовательной релаксации для работы со
строковыми данными ...80
2.2.7. Генерация входных тестовых данных процедурных типов 86
2.3. Улучшение количественных характеристик 89
.1.1. Адаптация метода релаксации для обработки дуговых функций кусочно-
линейного вида 89
2.4. Выводы 91
ГЛАВА 3. ВСПОМОГАТЕЛЬНЫЕ АЛГОРИТМЫ ДЛЯ ГЕНЕРАЦИИ
ТЕСТОВЫХ ДАННЫХ 92
-
Обзор вспомогательных алгоритмов для генерации тестовых данных....92
-
Построение управляющего графа из исходного текста программы 93
-
Алгоритм формирования набора путей, обеспечивающих покрытие по заданному критерию 101
-
Алгоритм инструментации программы 108
-
Алгоритм построения «линейного» варианта программы 113
-
Выводы 114
ГЛАВА 4. ПРОГРАММНАЯ СИСТЕМА ГЕНЕРАЦИИ ТЕСТОВЫХ ДАННЫХ
116
-
Обзор существующих систем генерации тестовых данных 116
-
Общая структура разработанной программной системы 117
-
Модуль синтаксического анализа 121
-
Модуль построения управляющего графа 125
-
Модули визуализации 126
-
Модуль построения набора требуемых путей 127
-
Модули инструментации и построения линейных вариантов программы 130
-
Модули компиляции, выполнения тестируемых программ и ..+. вспомогательные модули.... '. ;...;. 1ДЗ
-
Модуль алгоритмов нахождения тестовых данных 134
-
Модуль верификации 135
-
Результаты применения программной системы 136
-
Выводы 139
ЗАКЛЮЧЕНИ Е 140
ЛИТЕРАТУРА 141
ПРИЛОЖЕНИЯ 148
Введение к работе
В настоящее время вопросы качества программного обеспечения приобретают особую важность. Неотъемлемой частью процесса обеспечения качества является тестирование. По существующим оценкам [69], затраты на тестирование программ составляют до 50% всего бюджета программного продукта. Таким образом, тестирование — очень трудоемкий и дорогостоящий процесс. Актуальность проблемы
Автоматизация тестирования является весьма актуальной проблемой. В то время как такие составляющие процесса тестирования, как автоматизированное контролируемое выполнение программы, оценка и запись отчетов о результатах поддерживаются существующими программными системами, задача автоматизации получения входных тестовых данных зачастую остается нерешенной[49].
Решение этой задачи осложнено по следующим причинам: трудоемкость или невозможность создания формальной спецификации, позволяющей автоматизировать как создание тестов при функциональном тестировании, так и проверку правильности результатов работы программы на созданных входных наборах; ограничения существующих методов получения тестов для структурного тестирования модулей - относящиеся к обрабатываемым типам данных, управляющим структурам, методологии программирования (структурная или объектно-ориентированная).
Следует отметить, что актуальной задачей в настоящее время является не только генерация тестовых данных при промышленной разработке коммерческих программных продуктов, которая в значительной степени акцентируется на функциональном тестировании, но и генерация тестовых данных при проверке учебных программ, создаваемых на том или ином этапе обучения программированию. . Автоматизация такой проверки особенно важна, если обучение проводится дистанционно (например, на основе сети Интернет). В этом случае число тестируемых программ превышает объем, доступный для ручной проверки за приемлемое время.
Для класса учебных программ сложность решения вышеупомянутой задачи может быть уменьшена за счет следующего: в качестве формальной спецификации может выступать эталонная правильная программа, созданная в соответствии с учебным заданием экспертом в области программирования (например, преподавателем). Данная программа может служить полной и адекватной моделью, обеспечивающей правильный результат для любых входных данных; сложность учебных программ и их интерфейса искусственно ограничена требованиями задания, что позволяет эффективно применить методы автоматизированной генерации тестовых данных. В частности, рассматриваются только процедурные, а не объектно-ориентированные программы.
Наличие функциональной спецификации в виде эталонной программы позволяет найти тестовые входные данные структурно-ориентированными методами на основе тестируемой программы и объединить полученные наборы с тестовыми данными, полученными теми же методами на основе эталонной программы. Таким образом реализуется сочетание функционального и структурного подходов при применении только структурных методов генерации тестов.
Следовательно, основной задачей в контексте проверки учебных программ является исследование и усовершенствование существующих методов генерации тестовых данных для структурного тестирования путем расширения присущих им рамок ограничений.
Цель работы
Основной целью данной работы является усовершенствование методов нахождения входных данных для тестирования программ, а именно улучшение их количественных и качественных характеристик. Для достижения этой цели были решены следующие задачи: проведен сравнительный анализ существующих методов нахождения входных данных; разработаны вспомогательные алгоритмы, обеспечивающие функционирование методов расширен набор типов данных, поддерживаемых существующими методами; улучшены характеристики метода релаксации для случаев целевых функций сложного вида.
Методы исследования
Для достижения поставленных в работе целей использовались методы теоретического и эмпирического исследования.
Научная новизна
В диссертации получены следующие результаты, характеризующиеся научной новизной.
Разработан метод обработки строковых данных при генерации входных тестовых данных.
Разработан метод обработки данных процедурного типа при генерации входных тестовых данных.
Предложена адаптация метода релаксации для обработки дуговых функций сложного (кусочно-линейного) вида.
Разработаны вспомогательные алгоритмы для генерации тестовых данных: построения управляющего графа из исходного текста, формирования набора требуемых путей, инструментации программы
Практическая ценность
Включение строкового и процедурного типов данных в состав поддерживаемых методами генерации приводит к расширению множества 'v программ, для которых задача нахождения тестовых данных может быть эффективно решена. В результате степень автоматизации решения вышеупомянутой задачи существенно повышается, что не может не давать экономического эффекта.
Внедрение результатов
Результаты работы внедрены в СПбГУИТМО в учебном процессе, а также в проекте "Интернет-школа программирования". ..
Апробация работы
Основные положения диссертационной работы и результаты исследований, включенные в диссертацию, докладывались на различных конференциях СПбГУИТМО, всероссийской научно-методической конференции «Телематика 2005», а также на четырех различных всероссийских конференциях. Доклад на конференции «Микроэлектроника и информатика-2005» (МИЭТ, Зеленоград) был отмечен дипломом за третье место в конкурсе работ аспирантов.
9 Публикации
Яковлев Ю.А. Критерии полноты тестирования программ// Вестник конференции молодых ученых СПбГУИТМО. Сборник научных трудов. -СПб: СПбГИТМО (ТУ), 2004. -том 1. - с. 150-154
Яковлев Ю.А. Среда исследования методов генерации входных данных для структурного тестирования программного обеспечения // Вестник II межвузовской конференции молодых ученых. Сборник научных трудов /Под ред. В.Л. Ткалич. - СПб: СПбГУИТМО(ТУ), 2005. - том 1. - с. 60-64
Яковлев Ю.А. Реализация генетического алгоритма для поиска входных данных при структурном тестировании программ. //Материалы международной научно-технической конференции "Наука и образование-2005"- Мурманск, 2005. - с. 12-15
Яковлев Ю.А. Генерация входных тестовых данных символьного типа. //Микроэлектроника и информатика-2005. 12-я всероссийская межвузовская научно-техническая конференция студентов и аспирантов. Тезисы докладов. -Москва, 2005.-С.299
5. Яковлев Ю.А., Павловская Т.А. Графическая интерпретация динамических методов генерации входных данных для тестирования программ. //Информационные технологии в науке, проектировании и производстве.
Материалы 14-й всероссийской научно-технической конференции.-
Нижний Новгород, 2005. - с. 25-28
6. Яковлев Ю.А., Павловская Т.А. Адаптация метода генерации входных данных для тестирования программ с параметрами процедурного типа //Информационные технологии в профессиональной деятельности и научной работе. Сборник материалов региональной научно-практической конференции. - Йошкар-Ола, 2005. - с. 144-146.
7. Яковлев Ю.А., Павловская Т.А. Адаптация алгоритмов генерации входных данных для структурного тестирования объектно-ориентированных программ //Техника и технология, № 2, 2005. - с. 86-88
8. Яковлев Ю.А., Павловская Т.А. Динамические методы генерации входных данных для тестирования учебных программ // Сборник XII Всероссийской научно-методической конференции Телематика 2005 / Под ред. Сергеева А.О. — СПб: СПбГУ ИТМО (ТУ), 2005 г. - т.2. - с. 514-515
Структура и объем работы
Диссертационная работа состоит из четырех глав, введения, заключения, списка литературы, включающего 72 наименования, и приложения. Общий объем работы 265 страниц. Диссертация содержит 24 рисунка и 21 таблицу.
