Методы генерации тестовых сценариев на основе структурированных UCM-моделей проектируемой системы Воинов Никита Владимирович Специальность – Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей Научный руководитель: к.т.н., проф. кафедры ИУС, ФТК Котляров Всеволод Павлович САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

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

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

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

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

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

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

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

10/25 Взаимодополняемость формальных нотаций ПреимуществаНедостатки UCM близость к исходным требованиям модель понятна для контроля и согласования с заказчиком высокоуровневое описание архитектуры и поведения системы отсутствие инструментальных средств проверки корректности модели и генерации тестовых сценариев Базовые протоколы доказательство свойств модели и проверка корректности автоматическое создание символических тестовых сценариев определение областей допустимых значений большая трудоемкость формализации и сложность согласования с заказчиком Недостатки одной нотации устраняются использованием другой. Эффективно совместное использование нотаций

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

26/25 Сравнение инструментов тестирования на основе моделей. Покрытие элементов графа поведения модели Название Катего- рия Состоя- ния модели Заданное подмн-во переходов Все пе- реходы* Парал. переходы Пользователь- ские сценарии AGEDISбесплатн /- GOTCHA- TCBeans коммерч. +/- -- Mbtбесплатн /- MOTESбесплатн ParTeGбесплатн Qtronicкоммерч Spec Explorerкоммерч Test Designerкоммерч TestOptimalкоммерч UniTESKкоммерч VRS/TATкоммерч поддерживается +/- поддерживается частично - не поддерживается

27/25 Покрытие значений переменных и отслеживание требований НазваниеКатегория Покрытие конкретных значений Покрытие диапазона значений Покрытие пригранич. значений Отслежи- вание требований AGEDIS бесплатн GOTCHA- TCBeans коммерч mbt бесплатн MOTES бесплатн ParTeG бесплатн Qtronic коммерч Spec Explorer коммерч Test Designer коммерч TestOptimal коммерч UniTESK коммерч VRS/TATкоммерч поддерживается - не поддерживается

28/25 Поддерживаемая функциональность Название Формаль- ная нотация Созда- ние модели Верифи кация модели Структу рир-е модели Генера- ция тестов Исполне- ние тестов Язык целевой платформы AGEDIS UML С/C++, Java GOTCHA- TCBeans FSM С/C++, Java mbt FSM/EFSM любой MOTES EFSM любой ParTeG UML Java Qtronic UML любой Spec Explorer FSM любой Test Designer UML любой TestOptimal FSM любой UniTESK FSM С, C#, Java VRS/TAT MSC любой + поддерживается - не поддерживается

29/25 Создание среды тестирования Название Тестовый адаптер Тестовый оракул Тестовое окружение Online тестирование Offline тестирование AGEDIS +/- --+ GOTCHA- TCBeans +/- -++ mbt +/- - - MOTES -+/---- ParTeG Qtronic -+/---- Spec Explorer +/- --+ Test Designer TestOptimal +/- --- UniTESK VRS/TAT поддерживается +/- поддерживается частично - не поддерживается

30/25 Результаты сравнения инструментов тестирования на основе моделей Название Произво- дитель Кол-во удов- летворяемых критериев VRS/TATMotorola17 UniTESKИСП РАН15 Spec ExplorerMicrosoft12 Test DesignerSmartesting11 QtronicConformiq Inc10,5 TestOptimal 9 mbtopen source8 AGEDISIBM6,5 GOTCHA- TCBeans IBM6,5 MOTESElvior LLC6,5 ParTeGopen source5 В инструментах не применяются высокоуровневые формальные нотации Инструментарий VRS/TAT функционально наиболее полон Технология VRS/TAT имеет ряд ограничений VRS/TAT – базовый инструментарий для реализации цели. Но требуется устранение некоторых ограничений

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

32/25 Результаты применения разработанных методов Проект12 Оценка сокращения трудоемкост и (%) 34 Оценка сокращения трудоемкост и (%) 56 Оценка сокращени я набора трасс (%) C_ROUTER1,85, CDMA2,25, MPM2,16, S_HMI2, – Трудоемкость тестирования на основе моделей при использовании технологии VRS/TAT после интеграции разработанных методов (человеко-недель); 2 – Трудоемкость ручной разработки тестов без использования моделей (человеко-недель); 3 – Трудоемкость создания формальной UCM-модели и генерации модели базовых протоколов с помощью разработанного метода (человеко-дней); 4 – Трудоемкость создания формальной модели базовых протоколов вручную (человеко-дней); 5 – Кол-во трасс, покрывающих требования; 6 – Оптимизированный набор трасс

33/25 Сравнение формальных нотаций КритерииUCMUMLSDLMSC Описание архитектуры системы +++- Высокоуровневое описание поведения ++++ Прозрачность и доступность описания +--- Бесплатная инструментальная поддержка +---

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

35/25 Список публикаций по теме диссертации 1. Воинов Н.В., Котляров В.П. Верификация и автоматизация тестирования UML-проектов // Научно-технические ведомости СПбГПУ. 3 (80). СПб.: Изд-во Политехнического ун-та. – – C (издание из перечня ВАК) 2. Воинов Н.В., Котляров В.П. Применение метода эвристик для создания оптимального набора тестовых сценариев // Научно-технические ведомости СПбГПУ. 4 (103). СПб.: Изд-во Политехнического ун-та. – – C (издание из перечня ВАК) 3. Воинов Н.В., Веселов А.О., Котляров В.П. Автоматизация тестирования UML проектов // Вычислительные, измерительные и управляющие системы. Сборник научных трудов. СПб.: Изд-во Политехнического ун-та. – – С Воинов Н.В., Котляров В.П. Методика автоматизации тестирования проектов, специфицированных средствами UML // Технологии Microsoft в теории и практике программирования. Материалы межвузовского конкурса- конференции студентов, аспирантов и молодых ученых Северо-Запада марта 2009 г. СПб.: Изд-во Политехнического ун-та. – – С Воинов Н.В., Котляров В.П. Применение метода оптимизации обхода пространства поведения формальной модели для генерации тестовых сценариев // Технологии Microsoft в теории и практике программирования. Материалы межвузовского конкурса-конференции студентов, аспирантов и молодых ученых Северо-Запада марта 2010 г. СПб.: Изд-во Политехнического ун-та. – – С Воинов Н.В., Веселов А.О., Котляров В.П. Технология генерации тестовых наборов из UML спецификаций // Технологии Microsoft в теории и практике программирования. Материалы межвузовского конкурса-конференции студентов, аспирантов и молодых ученых Северо-Запада марта 2008 г. СПб.: Изд-во Политехнического ун-та. – – С Здробилко С.Н., Воинов Н.В. Автоматизированная формализация функциональных требований XMPP сервера // XXXVIII Неделя науки СПбГПУ. Материалы межвузовской научно-технической конференции ноября 2009 г. СПб.: Изд-во Политехнического ун-та. – – С. ???. 8. Синицкий Г.Ю.., Воинов Н.В. Применение UCM нотации для автоматизации тестирования программного продукта // XXXIX Неделя науки СПбГПУ. Материалы межвузовской научно-технической конференции декабря 2010 г. СПб.: Изд-во Политехнического ун-та. – – С 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, P

36/25 Сводка о разработанном подходе Решаемая проблема Повышение прозрачности и доступности для заказчика процесса тестирования на основе моделей с целью сокращения трудозатрат Конкурирующие альтернативы Формальные нотации UML, SDL, MSC Инновационные отличия (1) Применение двух формальных моделей: в высокоуровневой нотации UCM и в нотации базовых протоколов; (2) 6 методов усовершенствования технологии VRS/TAT Барьеры для внедрения Отсутствие опыта работы с нотацией UCM у исполнителей проектов и заказчиков Открывающиеся перспективы Эффективное взаимодействие с заказчиком на фазе дизайна архитектуры системы для согласования, контроля и раннего обнаружения и исправления ошибок в спецификациях

37/25 Направления будущих работ Сокращение количества генерируемых вспомогательных базовых протоколов, сохраняющих поток управления между элементами Responsibilities Упрощение ввода метаданных Проверка корректности введенных метаданных Разработка более гибких алгоритмов сокращения тестовых сценариев, покрывающих все требования Применение разработанных методов в новых проектах