Исследование и разработка конечно-автоматных методов синтеза проверяющих тестов для управляющих систем

• Автор: Дорофеева, Маргарита Юрьевна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Томск
• Количество страниц: 151 с.

СОДЕРЖАНИЕ
Введение

1. Основные понятия, постановка задачи и обзор существующих методов ее

решения

1Л Конечные автоматы

1.2. Отношения между автоматами.

1.2.1. Отношения конформности.

1.2.2. Отношения различимости.

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

1.3.1. Модель неисправности.

1.3.2. Проверяющие тесты

1.4. Выбор модели неисправности.
1.4.1. Модель черного ящика 5,,3тАг,У
1.4.2. Мутационный автомат и его использование для описания модели
неисправности
1.5. Постановка задачи синтеза тестов.
1.6. Методы синтеза проверяющих тестов для конечных автоматов
относительно модели 5,,5тАг,У.
1.6.1. Построение теста перечислением неисправностей
1.6.2. Идентификация состояний
1.6.3. Методы построения тестов.
1.7. Методы синтеза проверяющих тестов для недетерминированных автоматов.
1.8. Методы синтеза проверяющих тестов относительно мутационного
автомата.
1.9. Теоретические оценки длины проверяющего теста
1 Выводы по главе.
2. Экспериментальное сравнение методов синтеза проверяющих тестов для детерминированных автоматов
2.1. Генератор псевдослучайных автоматов.
2.1.1. Способ генерации автомата.
2.1.2. Анализ свойств генерируемых автоматов.
2.2. Экспериментальное исследование избыточности тестов, доставляемых различными методами
2.3. Экспериментальное исследование абстрактных методов синтеза тестов относительно модели черного ящика
2.3.1. Исследование зависимости длин тестов от числа состояний эталонного автомата
2.3.2. Сравнение с теоретическими оценками.
2.3.3. Исследование зависимости длины теста от числа выходных символов в автомате.
2.3.4. Полнота Iтестов
2.4. Результаты экспериментов с протоколами i i и V.
2.4.1. Сравнение длин тестов, построенных различными методами, для протокола
2.4.2. Сравнение длин тестов, построенных различными методами, для протокола V
2.5. Выводы по главе.
3. Метод синтеза проверяющих тестов для детерминированных автоматов с использованием построенной части теста Яметод.
3.1. Достаточные условия полноты теста.
3.2. Яметод построения полного проверяющего теста.
3.2.1. Стратегии перебора последовательностей
3.2.2. Алгоритм построения проверяющего теста
3.3. Экспериментальные результаты по оценке длины тестов, доставляемых Яметодом
3.4. Яметод для частичных приведенных автоматов.
3.4.1. Определения и обозначения.
3.4.2. Достаточные условия полноты теста.
3.4.3. Яметод построения полного проверяющего теста для частичного эталонного автомата
3.5. Выводы по главе.
4. Метод синтеза проверяющих тестов для недетерминированных автоматов с использованием построенной части теста адаптация Яметода
4.1. Определения и обозначения
4.2. Построение полного проверяющего теста относительно эквивалентности.
4.2.1. Достаточные условия полноты относительно модели неисправности
5,г,ОяедЮ
4.2.2. Метод построения полного проверяющего теста относительно модели
неисправности 5,,0яЛгУ.
4.3. Построение полного проверяющего теста относительно редукции
4.3.1. Понятие гразличимости.
4.3.2. Достаточные условия полноты теста
4.3.3. Метод построения полного проверяющего теста.
4.4. Основные результаты главы.
5. Метод синтеза полных проверяющих тестов по мутационному автомату
5.1. Основные понятия и определения.
5.2. Построение полного проверяющего теста относительно модели 5,,5и
5.3. Экспериментальные результаты.
5.4. Основные результаты главы
Заключение
Литература


Проведение молодыми учеными научных исследований по приоритетным направлениям науки, высоких технологий и образования федеральной целевой научнотехнической программы Исследования и разработки по приоритетным направлениям развития науки и техники на гг. Развитие инфраструктуры IV очередь Молодые ученые г. Документы, подтверждающие участие автора в работах по грантам и программам, можно найти в приложении 3 к настоящей диссертации. Апробация работы. Научные результаты, составившие основу данной работы, обсуждались на заседаниях объединенного семинара кафедры информационных технологий в исследовании дискретных структур радиофизического факультета ТГУ, кафедры защиты информации и криптографии и кафедры программирования факультета прикладной математики и кибернетики ТГУ. Кроме того, они докладывались на конференциях, в том числе международных, в гг. Новосибирске, Иркутске, Кобленце, Тайпее. Результаты работы опубликованы в . Структура и объем диссертации. Диссертация состоит из введения, 5 глав, заключения и списка используемой литературы. Объем диссертации составляет 1 страницу текста, набранного в редакторе шрифт i , размер шрифта , межстрочный интервал 1. Первая глава диссертации содержит необходимые понятия и определения теории автоматов, формальную постановку задачи синтеза проверяющих тестов методами теории конечных автоматов и обзор основных методов в области построения полных проверяющих тестов для конечных автоматов. Конечный автомат широко используется в качестве математической модели для описания поведения управляющих систем. Модель конечного автомата традиционно используется в технической диагностике 1, 2,,, , ,, а в последнее время с успехом применяется в области тестирования телекоммуникационных протоколов 7, и др. В параграфе 1. Поскольку с формальной точки зрения процесс тестирования проверяемой системы имеет своей целью проверку некоторого отношения между эталонным автоматом и автоматом, описывающим поведение тестируемой системы, параграф 1. В параграфе 1. Проблема выбора модели неисправности более подробно обсуждается в параграфе 1. В параграфе 1. Обзор известных результатов, относящихся к теме диссертации, приведен в параграфах 18. Большинство известных работ по построению проверяющих тестов посвящено синтезу тестов относительно модели черного ящика, т. В параграфе 1. В публикациях по построению тестов относительно мутационного автомата 6,, рассматривается задача построения теста для случая, когда неисправности не увеличивают число состояний в проверяемой системе. Для случая, когда мутационный автомат может иметь больше состояний, чем эталонный автомат, метод синтеза проверяющего теста предложен в работе . В параграфе 1. Несмотря на большое количество публикаций в области построения тестов для конечных автоматов, тесты с гарантированной полнотой, доставляемые известными методами, обладают большой избыточностью. Вторая глава диссертации посвящена экспериментальному сравнению проверяющих тестов, построенных различными методами, относительно модели 5,,ДИАГ,К в которой 5 детерминированный приведенный полностью определенный автомат. Согласно теоретическим оценкам, длина теста, доставляемого любым автоматным методом, экспоненциально зависит от разности тп числа состояний проверяемого и эталонного автоматов. Таким образом, представляют интерес экспериментальная оценка средней длины тестов, построенных различными методами относительно модели 5,,ДЯГ,У на одном и том же множестве примеров например, на множестве автоматов, сгенерированных псевдослучайным способом оценка избыточности соответствующих тестов а также исследование узких мест этих методов. Для проведения экспериментальных исследований был реализован генератор конечных автоматов и создан программный комплекс, в который вошли программы по построению тестов известными методами. В параграфе 2. На основании проведенных исследований делается вывод о том, что реализованный генератор доставляет автоматы с достаточно хорошими параметрами, в том смысле, что последовательности в множестве достижимости и различающие последовательности в генерируемых эталонных автоматах оказываются достаточно короткими. Параграф 2.