Введение
1. Основные понятия, постановка задачи и обзор существующих методов ее решения 19
1.1. Конечные автоматы 19
1.2. Отношения между автоматами 22
1.2.1. Отношения конформности 22
1.2.2. Отношения различимости 26
1.3. Модели неисправности и проверяющие тесты 28
1.3.1. Модель неисправности 28
1.3.2. Проверяющие тесты 29
1.4. Выбор модели неисправности 30
1.4.1. Модель «черногоящика» 31
1.4.2. Мутационный автомат и его использование для описания модели неисправности 33
1.5. Постановка задачи синтеза тестов 35
1.6. Методы синтеза проверяющих тестов для конечных автоматов относительно модели 36
1.6.1. Построение теста перечислением неисправностей 37
1.6.2. Идентификация состояний 39
1.6.3. Методы построения тестов 42
1.7. Методы синтеза проверяющих тестов для недетерминированных автоматов 46
1.8. Методы синтеза проверяющих тестов относительно мутационного автомата 49
1.9. Теоретические оценки длины проверяющего теста 49
1.10. Выводы по главе 50
2. Экспериментальное сравнение методов синтеза проверяющих тестов для детерминированных автоматов 52
2.1. Генератор псевдослучайных автоматов 52
2.1.1. Способ генерации автомата 52
2.1.2. Анализ свойств генерируемых автоматов 53
2.2. Экспериментальное исследование избыточности тестов, доставляемых различными методами 56
2.3. Экспериментальное исследование абстрактных методов синтеза тестов относительно модели «черного ящика» 58
2.3.1. Исследование зависимости длин тестов от числа состояний эталонного автомата 59
2.3.2. Сравнение с теоретическими оценками 61
2.3.3. Исследование зависимости длины теста от числа выходных символов в автомате 62
2.3.4. Полнота Ш?-тестов 63
2.4. Результаты экспериментов с протоколами Simple Connection Protocol и V.76 Protocol 64
2.4.1. Сравнение длин тестов, построенных различными методами, для протокола SCP 65
2.4.2. Сравнение длин тестов, построенных различными методами, для протокола V.76 66
2.5. Выводы по главе 68
3. Метод синтеза проверяющих тестов для детерминированных автоматов с использованием построенной части теста (Я-метод) 70
3.1. Достаточные условия полноты теста 71
3.2. Я-метод построения полного проверяющего теста 80
3.2.1. Стратегии перебора последовательностей 80
3.2.2. Алгоритм построения проверяющего теста 83
3.3. Экспериментальные результаты по оценке длины тестов, доставляемых Я-методом 87
3.4. Я-метод для частичных приведенных автоматов 90
3.4.1. Определения и обозначения 91
3.4.2. Достаточные условия полноты теста 93
3.4.3. Я-метод построения полного проверяющего теста для частичного эталонного автомата 96
3.5. Выводы по главе 99
4. Метод синтеза проверяющих тестов для недетерминированных автоматов с использованием построенной части теста (адаптация Я-метода) 100
4.1. Определения и обозначения 101
4.2. Построение полного проверяющего теста относительно эквивалентности 102
4.2.1. Достаточные условия полноты относительно модели неисправности 102
4.2.2. Метод построения полного проверяющего теста относительно модели неисправности 104
4.3. Построение полного проверяющего теста относительно редукции... 106
4.3.1. Понятие г-различимости 107
4.3.2. Достаточные условия полноты теста 110
4.3.3. Метод построения полного проверяющего теста 112
4.4. Основные результаты главы ...114
5. Метод синтеза полных проверяющих тестов по мутационному автомату 115
5.1. Основные понятия и определения 116
5.2. Построение полного проверяющего теста относительно модели <5,=,Sw&( 117
5.3. Экспериментальные результаты 123
5.4. Основные результаты главы 124
Заключение 126
Литература
