Синтез тестов для проверки взаимодействия дискретных управляющих систем методами теории автоматов

• Автор: Спицына, Наталия Владимировна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Томск
• Количество страниц: 159 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

1. ОСНОВНЫЕ ПОНЯТИЯ, ПОСТАНОВКА ЗАДАЧИ И ОБЗОР ЛИТЕРАТУРЫ.

1.1. Модели дискретных систем

1.2. Представление сетевых протоколов при помощи конечных автоматов .

1.3. Особенности проверки взаимодействия дискретных систем.

1.4. Модели неисправности и проверяющие тесты

1.5. Описание задач, решаемых в работе

1.6. Обзор существующих методов

1.6.1. Известные операции композиций дискретных систем, решение языковых и автоматных уравнений

1.6.2. Обзор методов построения тестов для проверки взаимодействия дискретных систем

1.7. Выводы по главе.
2. КОМПОЗИЦИЯ ЯЗЫКОВ, ПОЛУАВТОМАТОВ И АВТОМАТОВ
2.1. Обобщенная композиция элементов, поведение которых описано формальными языками
2.1.1. Элементы и системы взаимодействующих элементов
2.1.2. Построение языка, описывающего поведение системы взаимодействующих элементов.
2.1.3. Построение языка, описывающего поведение неизвестного элемента в системе
2.2. Обобщенная композиция полуавтоматов.
2.2.1. Описание системы взаимодействующих полуавтоматов
2.2.2. Нахождение неизвестного полуавтомата в системе взаимодействующих полуавтоматов
2.3. Обсуждение ограничений на структуру и режим работы для композиции конечных автоматов
2.4. Частные случаи композиции автоматов
2.4.1. Синхронная композиция автоматов
2.4.2. Параллельная композиция автоматов
2.4.3. Бинарная композиция с кратным стимулированием
2.4.4. Некоторые свойства бинарной композиции с кратным стимулированием
2.4.5. Нахождение неизвестного автомата в системе взаимодействующих автоматов.
2.5. Выводы по главе
3. ТЕСТИРОВАНИЕ ОТНОСИТЕЛЬНО ОСЦИЛЛЯЦИЙ.
3.1. Модель неисправности для тестирования относительно осцилляций
3.2. Выбор класса неисправностей на основе частичного задания компонент композиции
3.3. Особенности тестирования относительно осцилляций.
3.4. Метод построения проверяющих тестов на отсутствие осцилляций по ф мутационному автомату.
3.4.1. Построение полного проверяющего теста на основе безусловного тестирования
3.4.2. Построение полного проверяющего теста на основе условного тестирования
3.5. Экспериментальные результаты.
3.6. Выводы по главе.
4. МОДЕЛИ НЕИСПРАВНОСТИ И СИНТЕЗ ТЕСТОВ ДЛЯ ПРОВЕРКИ ФУНКЦИОНИРОВАНИЯ ВЗАИМОДЕЙСТВУЮЩИХ АВТОМАТОВ ПРИ КРАТНОМ СТИМУЛИРОВАНИИ.
4.1. Синтез тестов для композиции А1 0ХЛ
4.2. Синтез тестов для композиции Л1 0Л
4.2.1. Полный проверяющий тест при использовании мутационного автомата
4.2.2. Модель неисправности при тестировании композиции А1 0 А2.
4.2.3. Алгоритм построения полного проверяющего теста
4.2.4. Построение тестов для компонент сети на основе решения автоматных
уравнений
4.3. Синтез тестов для удаленной компоненты.
4.3.1. Построение тестов для композиций I 0 А2 А 1 0ф2 АТ.
4.3.2. Исследование отношения неразделимости
4.4. Выводы по главе
5. ТЕСТИРОВАНИЕ ПРОГРАММНЫХ РЕАЛИЗАЦИЙ ПРОТОКОЛОВ В ЛАБОРАТОРНОМ ПРАКТИКУМЕ.
5.1. Краткое описание предлагаемых лабораторных работ.
5.2. Ошибки, типичные при реализации любого протокола прикладного уровня
5.3. Возможные ошибки при реализации конкретного протокола прикладного уровня
5.3.1. Возможные ошибки при реализации протокола 3.
5.3.2. Возможные ошибки при реализации протокола .
5.3.3. Возможные ошибки при реализации протокола .
5.3.4. Возможные ошибки при реализации протокола I.
5.3.5. Возможные ошибки при реализации протокола .
5.4. Автоматизация тестирования студенческих реализаций протоколов
5.4.1. Постановка задачи автоматизации тестирования.
5.4.2. Архитектура тестера
5.4.3. Пример тестирования РОРЗсервера.
5.5. Выводы по главе
ЗАКЛЮЧЕНИЕ.
СПИСОК ЛИТЕРАТУРЫ


При этом предполагается, что в любой проверяемой системе компоненты согласованы, т. Однако этап тестирования совместимости компонент не рассматривается. Исследования, посвященные проверке совместимости компонент системы, проводились независимо. Ниже мы кратко представляем известные в этой области результаты. Одной из основных проблем, возникающих при взаимодействии дискретных систем, являются осцилляции, т. В известных нам работах тесты для выявления осцилляций строятся эвристически без математической модели , или этот этап тестирования вообще не рассматривается , . Проверка на тупики и осцилляции на этапе валидации , т. Это связано с тем, что спецификации бывают частичными, и в реализациях неопределенные части спецификаций могут быть определены поразному. Если в проверяемой системе осцилляции отсутствуют и поведение системы описывается параллельной или синхронной композицией автоматов, то для проверки правильности работы композиции можно воспользоваться известными формальными моделями неисправности. В этих моделях, как правило, предполагается, что неисправности возможны в любой, но только в одной компоненте сети. Подобное предположение достаточно реалистично, поскольку вероятность неисправности нескольких компонент значительно меньше. Известно, что тесты, построенные для одиночных неисправностей, обнаруживают большое количество других неисправностей, в частности, такие тесты обнаруживают константные неисправности на связях между компонентами 8. Если предполагать, что неисправности возможны только в одной компоненте сети, можно говорить о тестировании компоненты сети в контексте другого автомата . Проверяющие тесты могут быть построены на основе автомата сети или на основе тестируемой компоненты сети. Автомат сети строится посредством композиции эталонной компоненты и контекста. Известно несколько подходов к построению тестов на основе автомата сети, а именно перечисление всевозможных неисправностей в компоненте, синтез тестов на основе верхней оценки числа состояний композиции методами, предложенными в , представление класса неисправностей при помощи мутационного автомата . Перечисление всех неисправностей позволяет строить безызбыточные тесты, однако обычно не применимо на практике тесты, основанные на верхней оценке числа состояний композиции, избыточны, т. При построении тестов на основе тестируемой компоненты сети, используется максимально допустимое поведение компоненты, которое может быть описано специальным недетерминированным автоматом, называемым сетевым эквивалентом , . Сетевой эквивалент обычно находится решением соответствующего автоматного уравнения. Задача трансляции внутренних тестов на внешние полюсы сеги может решаться для всех последовательностей теста одновременно на основе решения автоматных уравнений . Нам известна единственная работа , в которой проверяющие тесты для композиции автоматов при кратном стимулировании строятся на основе формальной модели неисправности, а именно для выходных неисправностей в компонентах сети. Следует также отметить, что модели неисправности, применяемые при построении тестов для синхронной и параллельной композиций, не могут быть напрямую применены для композиции с кратным стимулированием, по следующим причинам. Известно, что при кратном стимулировании результатом композиции детерминированных автоматов может быть недетерминированный автомат. Поэтому необходимы модели неисправности, в которых и спецификация, и реализация могут быть недетерминированными автоматами. Отсутствует формула, позволяющая найти максимально допустимое поведение компоненты для композиции с кратным стимулированием, в результате чего подход с использованием сетевого эквивалента не может быть применен. Известных формальных операций композиции автоматов недостаточно для описания поведения взаимодействующих систем, в частности для описания поведения композиции автоматов при кратном стимулировании. Отсутствует формальная модель неисправности и методы построения проверяющих тестов с гарантированной полнотой для проверки композиции автоматов на осцилляции.