Методы генерации тестовыхсценариев на основе структурированныхUCM-моделей проектируемой системыВоинов Никита Владимирович

Проблемная область
Обеспечение качества программного обеспечения (ПО)
Предотвращение ошибок на ранних этапах проекта
Актуальность применения тестирования на основе моделей
Ограниченная вовлеченность заказчика в контроль разработки
Требуется усовершенствование технологии для контролируемого заказчиком процесса получения тестовых сценариев на проектируемую систему
Стоимость исправления
ошибок в ПО
Требования
Дизайн
Кодирование
Тестирование
Эксплуатация

Актуальность исследования
Сложность применения формальных нотаций в инженерной практике.
Фундаментальные работы по использованию моделей в спецификации, верификации и тестировании программного обеспечения:
Кларк Э.М., Грамберг О., Пелед Д. – верификация моделей программ
Ершов А.П., Лавров С.С. – математические основы технологии программирования
Липаев В.В., Петренко А.К. – подход к индустриальному тестированию и его автоматизации
Карпов Ю.Г., Смелянский Р.Л. – метод проверки на моделях
Боем Б. – экономика индустриального программного обеспечения
Майерс Г. – искусство тестирования программного обеспечения
Составляют базис теорий программирования, тестирования и формальных методов, который необходимо расширять

Контроль на этапе дизайна системы
Исходные требования
Высокоуровневое описание поведения системы
Форма представления поведения системы, понятная как заказчику, так и исполнителям проекта
Единая интерпретация требований
Модель системы в подобной нотации не может быть проверена на корректность
Необходима также модель системы в нотации,
позволяющей проводить верификацию

1. Исходные требования
2. Базовые протоколы
3. Дерево поведения
4. Поведенческие сценарии – трассы и MSC
Верифицируемая формальная модель
Применение двух формальных моделей в рамках единой технологической цепочки создания тестовых сценариев

Цели и задачи исследования
Цель – сокращение трудоемкости процесса разработки тестовых сценариев путем применения высокоуровневых UCM-моделей, контролируемых заказчиком.
Задачи:
обоснование использования UCM-нотации;
обоснованный выбор базового инструментария для реализации;
поиск наиболее трудоемких этапов процесса разработки тестовых сценариев;
разработка методов и инструментов автоматизации выделенных этапов;
интеграция разработанных методов и инструментов в процесс проверки качества разрабатываемого ПО.
Подход к реализации цели – автоматизация трудоемких этапов процесса разработки тестовых сценариев на основе UCM-модели

Нотация UCM (Use Case Maps)
UCM – последовательность событий, описывающих поведение системы
Задается набором взаимодействующих между собой диаграмм
Наглядное представление поведения системы и взаимодействий между ее компонентами
На сегодняшний день наиболее высокоуровневое описание проектируемой системы, сохраняющее при этом все сценарии ее поведения

Фрагмент UCM-модели компонента проекта CDMA
Всего в проекте порядка 9000 требований.
Характеристики компонента: 148 требований, 205 базовых протоколов, порядка
сценариев поведения.

Базовый протокол –
элементарная MSC диаграмма:
Нотация базовых протоколов
Предусловие
Постусловие
Исполнимая часть:
Действие
Сигнал
Основные функции VRS:
проверка свойств требований
проверка корректности поведения модели
доказательство выполнимости
требований в модели
и
– пред- и постусловия, P – процесс
Нотация базовых
протоколов – входной язык системы верификации VRS
x – список типизированных параметров

Взаимодополняемость формальных нотаций
Недостатки одной нотации устраняются использованием другой. Эффективно совместное использование нотаций

Уточнение цели и задач исследования
Цель – сокращение трудоемкости процесса разработки тестовых сценариев путем применения высокоуровневых UCM-моделей, контролируемых заказчиком. Сокращение трудоемкости осуществляется автоматизацией:
преобразования UCM-моделей в модели базовых протоколов;
структурирования модели базовых протоколов;
направленного поиска определенных сценариев поведения модели;
отслеживания соответствия между требованиями и элементами модели;
поиска покрытия требований полученными тестовыми сценариями.
Задачи:
разработка методов и инструментов автоматической трансляции высокоуровневой UCM-модели в формальную нотацию, используемую VRS/TAT;
разработка методов структурирования формальной модели;
разработка методов отслеживания соответствия между требованиями и элементами модели;
разработка методов и инструментальных средств построения тестовых сценариев на основе анализа формальной модели;
интеграция разработанного подхода в процесс проверки качества разрабатываемого ПО средствами VRS/TAT;
применение и проверка работоспособности предложенных методов и инструментальных средств в составе технологической цепочки VRS/TAT в крупных промышленных телекоммуникационных проектах.

Интеграция разработанных методов в технологическую цепочку VRS/TAT
Изменения в технологической цепочке

Метод 1 - автоматическое создания формальной модели базовых протоколов по нотации UCM
преобразование компонентов и элементов UCM в базовые протоколы;
использование полей метаданных для детализации поведения.
Автоматическое создание формальной модели в виде набора базовых протоколов

Метод 2 - структурирование формальной модели
Преобразование UCM модели, факторизованной элементами Stub, в
модель базовых протоколов, факторизованную расширенными протоколами, их интерпретирующими.
Покомпонентный анализ поведения модели
Расширенный протокол заменяет после-довательность базовых протоколов
Элемент Stub – механизм структурирования диаграмм
Элемент Stub интерпретиру-ется как расширенный протокол.

Уравнение А.А.Летичевского:
Сокращение времени генерации тестовых сценариев
Графическая интерпретация:
Если L - высота дерева поведения , N – кол-во базовых протоколов, на каждом шаге может примениться любой, то общее количество трасс
Экспоненциальный взрыв числа состояний!
Указание определенных элементов дерева поведения для включения в тестовый сценарий сокращает пространство поиска:
Применение эвристик:
Эвристики сокращают время на получение важных трасс
Критериальная
цепочка
– постусловие
– процесс базового протокола
– предикатный трансформер

Метод 3 – автоматическое создание эвристик
Гибкая настройка направленного поиска определенных сценариев в дереве поведения модели
1) Создание эвристик по набору MSC-диаграмм:
2) Создание эвристик по набору MSC-диаграмм и критериальным цепочкам:
3) Инкрементальный метод создания эвристик:

Метод 4 – отслеживание соответствия между требованиями и элементами модели
формулировка последовательности наблюдаемых событий в строгом порядок исполнения;
формулировка цепочек базовых протоколов;
отслеживание соответствия между событиями, характеризующими требования в терминах исходных спецификаций, доступных заказчику, и элементами модели (базовыми протоколами):
Метод реализован с помощью матрицы отслеживания:
Связь между тестовыми сценариями и требованиями; идентификация покрытых и непокрытых требований

Метод 5 – поиск покрытия требований в соответс-твии с критерием цепочек наблюдаемых событий
поиск последовательностей базовых протоколов, описывающих
требования, в сгенерированных трассах:
Определение степени покрытия требований набором тестовых сценариев

Метод 6 – сокращение тестового набора
Выявление минимального количества тестовых сценариев из всех
сгенерированных, покрывающего при этом все требования, покрытые
исходным сгенерированным набором сценариев:
Сокращение итогового числа тестовых сценариев
Разметка покрытого требования Req_1984-177
в минимальном наборе
трасс:

Применение разработанных методов
Проекты:
базовая станция системы, реализующей технологию CDMA; характеристики модуля: 148 требований, 205 базовых протоколов, порядка 1013 возможных сценариев поведения; всего в проекте порядка 9,000 требований;
C_ROUTER – компонент телекоммуникационной сети, связывающий базовые станции с администратором базовых станций; характеристики компонента:107 требований, 163 протоколов, порядка 108 возможных сценариев поведения; всего в проекте порядка 5,000 требований;
модуль MPM, решающий проблему совместимости между интерфейсами модемов и контроллера станции приемопередатчика, в рамках проекта WiMAX; характеристики модуля: 51, 283, 1010; всего в проекте порядка 12,000 требований;
S_HMI – проект электронного табло в кабине машиниста поезда метрополитена (57, 497,1012); всего в проекте порядка 240 требований

Анализ результатов применения. Общее сокращение трудоемкости
60%-ное сокращение трудоемкости по сравнению с ручным подходом к созданию тестов без использования моделей

Анализ результатов применения. Сокращение трудоемкости создания формальной модели
В среднем 45%-ное сокращение трудоемкости создания формальной модели базовых протоколов

Заключение
Впервые в рамках технологической цепочки VRS/TAT применен подход, состоящий в использовании двух формальных моделей
Выявлены преимущества UCM формализации для эффективного взаимодействия с заказчиком и сокращения трудозатрат
Разработаны, реализованы и интегрированы в технологию VRS/TAT 6 методов ее усовершенствования
Разработанные методы испытаны в 4-х крупных телекоммуникационных проектах
Получены оценки применения этих методов в промышленных проектах на основе анализа результатов применения
Достигнуто 60%-ное сокращение трудоемкости по сравнению с ручным подходом к созданию тестов

Обоснование применения двух формальных моделей: в высокоуровневой нотации UCM и в нотации базовых протоколов.
6 методов усовершенствования технологии VRS/TAT:
1) автоматическое построение модели базовых протоколов;
2) структурирование модели базовых протоколов;
3) автоматическое создание эвристик;
4) отслеживание соответствия между требованиями и элементами модели;
5) поиск покрытия требований в соответствии с критерием цепочек наблюдаемых событий;
6) сокращение набора тестовых сценариев.
Программная реализация разработанных методов (≈12,5 KLOC на языках Perl и Java).
Результаты пилотирования разработанных методов и инструментальных средств в 4-х промышленных проектах, подтвердившие их преимущества.
На защиту выносятся:

СПАСИБО ЗА ВНИМАНИЕ!

Сравнение инструментов тестирования на основе моделей. Покрытие элементов графа поведения модели
+
поддерживается
+/-
поддерживается частично
-
не поддерживается

Покрытие значений переменных и отслеживание требований
+
поддерживается
-
не поддерживается

Поддерживаемая функциональность
+
поддерживается
-
не поддерживается

Создание среды тестирования
+
поддерживается
+/-
поддерживается частично
-
не поддерживается

Результаты сравнения инструментов тестирования на основе моделей
В инструментах не применяются высокоуровневые формальные нотации
Инструментарий VRS/TAT функционально наиболее полон
Технология VRS/TAT имеет ряд ограничений
VRS/TAT – базовый инструментарий для реализации цели.
Но требуется устранение некоторых ограничений

Ограничения и недостатки существующей технологии VRS/TAT
Требования
Описание
окружения
Описание
сигналов
Базовые
протоколы
VRS
Верификация
Визуальный анализ
модели в виде
графа переходов
Анализ
результатов
Верифицированная
модель
Генерация трасс с
символическими
параметрами
Подстановка конкретных
значений параметров
в трассах
Набор трасс для
автоматической
генерации тестов
TAT
Автоматическая генерация тестов
Исполнение тестов
Анализ результатов тестирования
Набор трасс с
символическими
параметрам
1
2
3
4
1 – трудоемкая ручная формализация модели базовых протоколов; модель сложна для согласования с заказчиком
2 – отсутствие структурирования модели; сложность работы с крупными проектами
3 – генерация трасс по всему дереву поведения модели; большое количество ненужных трасс и длительное время генерации
4 – не отслеживается соответствие между требованиями и элементами модели; отсутствует контроль покрытия требований

Результаты применения разработанных методов
1 – Трудоемкость тестирования на основе моделей при использовании технологии VRS/TAT
после интеграции разработанных методов (человеко-недель);
2 – Трудоемкость ручной разработки тестов без использования моделей (человеко-недель);
3 – Трудоемкость создания формальной UCM-модели и генерации модели базовых протоколов
с помощью разработанного метода (человеко-дней);
4 – Трудоемкость создания формальной модели базовых протоколов вручную (человеко-дней);
5 – Кол-во трасс, покрывающих требования;
6 – Оптимизированный набор трасс

Сравнение формальных нотаций

Пример структурирования модели

Список публикаций по теме диссертации
1. Воинов Н.В., Котляров В.П. Верификация и автоматизация тестирования UML-проектов // Научно-технические ведомости СПбГПУ. № 3 (80). СПб.: Изд-во Политехнического ун-та. – 2009. – C. 220-225. (издание из перечня ВАК)
2. Воинов Н.В., Котляров В.П. Применение метода эвристик для создания оптимального набора тестовых сценариев // Научно-технические ведомости СПбГПУ. № 4 (103). СПб.: Изд-во Политехнического ун-та. – 2010. – C. 169-174. (издание из перечня ВАК)
3. Воинов Н.В., Веселов А.О., Котляров В.П. Автоматизация тестирования UML проектов // Вычислительные, измерительные и управляющие системы. Сборник научных трудов. СПб.: Изд-во Политехнического ун-та. – 2007. – С. 57-65.
4. Воинов Н.В., Котляров В.П. Методика автоматизации тестирования проектов, специфицированных средствами UML // Технологии Microsoft в теории и практике программирования. Материалы межвузовского конкурса-конференции студентов, аспирантов и молодых ученых Северо-Запада. 17-18 марта 2009 г. СПб.: Изд-во Политехнического ун-та. – 2009. – С. 84-85.
5. Воинов Н.В., Котляров В.П. Применение метода оптимизации обхода пространства поведения формальной модели для генерации тестовых сценариев // Технологии Microsoft в теории и практике программирования. Материалы межвузовского конкурса-конференции студентов, аспирантов и молодых ученых Северо-Запада. 16-17 марта 2010 г. СПб.: Изд-во Политехнического ун-та. – 2010. – С. 139-140.
6. Воинов Н.В., Веселов А.О., Котляров В.П. Технология генерации тестовых наборов из UML спецификаций // Технологии Microsoft в теории и практике программирования. Материалы межвузовского конкурса-конференции студентов, аспирантов и молодых ученых Северо-Запада. 11-12 марта 2008 г. СПб.: Изд-во Политехнического ун-та. – 2008. – С. 22-24.
7. Здробилко С.Н., Воинов Н.В. Автоматизированная формализация функциональных требований XMPP сервера // XXXVIII Неделя науки СПбГПУ. Материалы межвузовской научно-технической конференции. 24-28 ноября 2009 г. СПб.: Изд-во Политехнического ун-та. – 2009. – С. ???.
8. Синицкий Г.Ю.., Воинов Н.В. Применение UCM нотации для автоматизации тестирования программного продукта // XXXIX Неделя науки СПбГПУ. Материалы межвузовской научно-технической конференции. 06-11 декабря 2010 г. СПб.: Изд-во Политехнического ун-та. – 2010. – С. 93-95.
9. Voinov N., Kotlyarov V. Verification and Testing Automation of UML Projects // Proceedings of the Third Spring Young Researchers’ Colloquium on Software Engineering. Vol. 3. Moscow, 2009. P. 41-45.

Сводка о разработанном подходе