Содержание к диссертации
Введение
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. Модель «черногоящика»
1.4.2. Мутационный автомат и его использование для описания модели неисправности 33
1.5. Постановка задачи синтеза тестов 35
1.6. Методы синтеза проверяющих тестов для конечных автоматов относительно модели
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. Достаточные условия полноты относительно модели неисправности <5=,Qm(X,Y)> 102
4.2.2. Метод построения полного проверяющего теста относительно модели неисправности <5,=,Пт(Х,У)> 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
Литература
- Конечные автоматы
- Генератор псевдослучайных автоматов
- Достаточные условия полноты теста
- Построение полного проверяющего теста относительно эквивалентности
Введение к работе
Актуальность проблемы. Конечные автоматы широко используются в качестве математической модели при синтезе тестов для контроля правильности функционирования систем логического управления [1-6], в частности, при тестировании телекоммуникационных протоколов [7-11], а в последнее время и при тестировании программного обеспечения [12 и др.]. Математической моделью процесса контроля является эксперимент с автоматом [2], т.е. процесс приложения тестовых последовательностей к проверяемой системе, поведение которой описано автоматом, наблюдении соответствующих реакций и вывода заключения на основе этих наблюдений о пригодности или непригодности тестируемой системы к дальнейшему использованию. При использовании автоматного подхода обычно предполагается, что множество проверяемых автоматов описывает поведение систем со всеми возможными неисправностями, и если множество входных воздействий (проверяющий тест) может обнаружить каждую систему, не пригодную к использованию, то такое множество входных воздействий называется полным проверяющим тестом (относительно заданного множества неисправностей). Несмотря на большое количество публикаций по синтезу проверяющих тестов для автоматов [13-24 и др.], задача далека от того, чтобы считаться решенной. По-прежнему неизвестны необходимые и достаточные условия полноты проверяющих тестов относительно различных моделей, что не позволяет строить оптимальные тесты. Полные тесты, построенные относительно известных моделей, в частности, относительно модели «черного ящика», т.е. для случая, когда известна только верхняя оценка числа состояний в проверяемой системе [13, 18, 19], обладают высокой полнотой, но их размерность ограничивает практическое применение. Более того, в большинстве случаев тесты, доставляемые известными методами, обладают
большой избыточностью. В связи с этим продолжается поиск новых моделей неисправности, отражающих ошибки в реальных системах, и допускающих построение тестов достаточно высокого качества. Одной из таких моделей является модель «серого ящика», когда полный проверяющий тест строится относительно множества всех подавтоматов специального мутационного автомата [7, 23, 24]. Модель мутационного автомата при синтезе проверяющих тестов активно используется при тестировании, в том числе, программного обеспечения [12 и др.]. Таким образом, задача синтеза проверяющих тестов для контроля функционирования систем логического управления методами теории автоматов является актуальной.
Цель работы. Теоретическое и экспериментальное исследование методов построения полных проверяющих тестов для конечных автоматов относительно моделей «черного ящика» и «серого ящика» без перебора автоматов из области неисправности и разработка на основе проведенных исследований новых методов, доставляющих проверяющие тесты по длине близкие к оптимальным.
Методы исследования. Для решения поставленных задач применяется аппарат теории автоматов, математической логики, а также компьютерные эксперименты для экспериментального исследования различных методов построения тестов и оценки эффективности предложенных методов.
Достоверность полученных результатов. Все научные положения и выводы, содержащиеся в работе, основаны на утверждениях, доказанных с использованием аппарата дискретной математики, в частности, с использованием аппарата теории автоматов.
Научная новизна. Научная новизна работы состоит в следующем,
1. Проведен экспериментальный анализ методов синтеза проверяющих тестов без перечисления проверяемых автоматов относительно модели
«черного ящика», т.е. относительно модели неисправности <5,=,ДИ(.АГ,У)> на одном и том же множестве автоматов, сгенерированных псевдослучайным способом, а также на автоматах, описывающих телекоммуникационные протоколы, с целью сравнения длин тестов, доставляемых различными методами. Экспериментально показано, что 1) тесты, построенные без перебора автоматов из множества 3>M(X,Y), являются избыточными относительно теста, построенного посредством перебора проверяемых автоматов; 2) UIO- и DS-методы доставляют тесты с наименьшей избыточностью, но эти методы не всегда применимы; 3) из рассмотренных методов, применимых к любому связному приведенному автомату, самые короткие тесты доставляют Wp- и Ж/-методы. Согласно проведенным экспериментам, соотношения между длинами тестов, построенных различными методами, для случайно сгенерированных автоматов и для автоматов, описывающих протоколы, сохраняются.
2. Установлены новые достаточные условия полноты проверяющих тестов для детерминированных автоматов относительно модели неисправности
Разработанный Я-метод адаптирован для случая, когда эталонный автомат является недетерминированным для проверки отношений редукции и эквивалентности.
Предложен новый метод синтеза проверяющего теста относительно мутационного автомата, который для определенных классов мутационных автоматов доставляет более короткие проверяющие тесты, чем известные методы. Экспериментально показано, что в большинстве случаев, когда число пар «текущее_состояние, входной__символ», для которых в мутационном автомате существует более одного перехода, не превышает 20%, длина теста полиномиально зависит от числа состояний мутационного автомата.
Практическая ценность. На основе проведенных исследований создан пакет прикладных программ для синтеза полных проверяющих тестов для конечных автоматов. Разработанные методы и программы были опробованы при тестировании телекоммуникационных протоколов и могут быть использованы в современных комплексах диагностики и тестирования дискретных управляющих систем.
Реализация полученных результатов. Исследования, результаты которых изложены в диссертации, проводились в рамках следующих проектов.
Научная Программа МО РФ «Научные исследования высшей школы в области производственных технологий» (2000 г.)
Проект МО РФ Е00-2.0-33 «Исследование отношений редукции и эквивалентности между недетерминированными автоматами» (2001-2002 гг.)
Грант Роснауки по мероприятию 1.11 «Развитие системы стажировок молодых ученых и преподавателей в крупных научно-образовательных центрах (включая зарубежные) и участие в
конференциях, симпозиумах, семинарах, школах (в том числе за рубежом)» федеральной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 гг. по приоритетному направлению «Развитие инфраструктуры» (XVII очередь) (2005 г.)
Грант Роснауки по мероприятию 1.9 «Проведение молодыми учеными научных исследований по приоритетным направлениям науки, высоких технологий и образования» федерельной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 гг. по приоритетному направлению «Развитие инфраструктуры» (XXII очередь) (2005 г.)
Грант Роснауки по мероприятию 1.9 «Проведение молодыми учеными научных исследований по приоритетным направлениям науки, высоких технологий и образования» федеральной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 гг. по приоритетному направлению «Развитие инфраструктуры» (IV очередь -Молодые ученые) (2006 г.)
Документы, подтверждающие участие автора в работах по грантам и программам, можно найти в приложении 3 к настоящей диссертации.
Апробация работы. Научные результаты, составившие основу данной работы, обсуждались на заседаниях объединенного семинара кафедры информационных технологий в исследовании дискретных структур радиофизического факультета ТГУ, кафедры защиты информации и криптографии и кафедры программирования факультета прикладной математики и кибернетики ТГУ. Кроме того, они докладывались на конференциях, в том числе международных, в гг. Томске, Туапсе,
Новосибирске, Иркутске, Кобленце, Тайпее. Результаты работы опубликованы в [65-77].
Структура и объем диссертации. Диссертация состоит из введения, 5 глав, заключения и списка используемой литературы. Объем диссертации составляет 151 страницу текста, набранного в редакторе MS Word 2000 (шрифт - Times New Roman, размер шрифта - 14 pt, межстрочный интервал - 1.5 строки), в том числе: титульный лист - 1 стр., оглавление - 4 стр., основной текст, включающий 17 рисунков и 3 таблицы, - 124 стр., библиография из 77 наименований - 8 стр., приложение - 13 стр.
Основное содержание работы
Первая глава диссертации содержит необходимые понятия и определения теории автоматов, формальную постановку задачи синтеза проверяющих тестов методами теории конечных автоматов и обзор основных методов в области построения полных проверяющих тестов для конечных автоматов.
Конечный автомат широко используется в качестве математической модели для описания поведения управляющих систем. Модель конечного автомата традиционно используется в технической диагностике [1,2, 13,21, 27, 28,], а в последнее время с успехом применяется в области тестирования телекоммуникационных протоколов [7-11, 14-17 и др.] и программного обеспечения [12 и др.].
В параграфе 1.1 вводятся основные понятия, определения и обозначения. Поскольку с формальной точки зрения процесс тестирования проверяемой системы имеет своей целью проверку некоторого отношения между эталонным автоматом и автоматом, описывающим поведение тестируемой системы, параграф 1.2 содержит известные отношения конформности (соответствия) между автоматами, характеризующие степень «похожести» или «сходства» двух автоматов в том или ином смысле. В
работе рассматриваются отношения конформности как между детерминированными автоматами, так и между недетерминированными автоматами [7,32,37-42]. В параграфе 1.3 вводятся понятия модели неисправности в терминах конечных автоматов [43] и полного проверяющего теста. Проблема выбора модели неисправности более подробно обсуждается в параграфе 1.4. В параграфе 1.5 формулируется задача синтеза полных проверяющих тестов относительно различных моделей неисправностей. Обзор известных результатов, относящихся к теме диссертации, приведен в параграфах 1.6-1.8. Большинство известных работ по построению проверяющих тестов посвящено синтезу тестов относительно модели «черного ящика», т.е. относительно модели неисправности, в которой эталонный автомат является детерминированным, а область неисправности состоит из всех детерминированных автоматов с количеством состояний, не превышающим заданного целого числа [2, 13-21]. В параграфе 1.7 рассматриваются методы построения полных проверяющих тестов для случая, когда эталонная и проверяемая системы могут иметь недетерминированное поведение, т.е. их поведение описывается недетерминированными автоматами [31-36,44,45]. В публикациях по построению тестов относительно мутационного автомата [6,23,26] рассматривается задача построения теста для случая, когда неисправности не увеличивают число состояний в проверяемой системе. Для случая, когда мутационный автомат может иметь больше состояний, чем эталонный автомат, метод синтеза проверяющего теста предложен в работе [25]. В параграфе 1.9 приводятся известные теоретические оценки длин тестов для модели «черного ящика».
Несмотря на большое количество публикаций в области построения тестов для конечных автоматов, тесты с гарантированной полнотой, доставляемые известными методами, обладают большой избыточностью. В
связи с этим актуальной является задача исследования необходимых и достаточных условий полноты проверяющих тестов для конечных автоматов относительно различных моделей неисправностей.
Вторая глава диссертации посвящена экспериментальному сравнению проверяющих тестов, построенных различными методами, относительно модели
В параграфе 2.1 исследуются свойства генератора случайных автоматов: определяются параметры автоматов, которые влияют на длину теста. На основании проведенных исследований делается вывод о том, что реализованный генератор доставляет автоматы с достаточно «хорошими параметрами», в том смысле, что последовательности в множестве достижимости и различающие последовательности в генерируемых эталонных автоматах оказываются достаточно короткими. Параграф 2.2 посвящен оценке избыточности тестов, построенных без перебора автоматов множества 3m(XtY). Экспериментально показано, что даже для небольших автоматов такие тесты являются избыточными относительно
теста, построенного посредством перебора проверяемых автоматов. Согласно проведенным экспериментам, структура теста при случайном переборе автоматов из области неисправности аналогична структуре тестов, доставляемых методами без перебора проверяемых автоматов. В параграфе 2.3 проводится экспериментальное исследование W-, DS-, Wp~, UIO-, UIOv-, #57-методов построения тестов на одном и том же множестве случайно сгенерированных автоматов. Раздел 2.3.1 посвящен сравнению длин тестов, доставляемых различными методами. Экспериментально показано, что тесты, доставляемые Wp- и ЖТ-методами обладают наименьшей избыточностью. В разделе 2.3.2 проводится сравнение средней длины построенных тестов с теоретическими оценками и отмечается, что для случайно сгенерированных автоматов построенные тесты оказываются существенно короче теоретических оценок. В разделе 2.3.3 проводится исследование зависимости длины проверяющего теста от числа выходных символов автомата. Экспериментально показано, что с приближением числа выходных символов к числу состояний эталонного автомата, #57-, C/70V-, ДУ-методы доставляют тесты практически одной и той же длины. Также показано, что применимость 2?5-метода зависит от отношения число выходных_символов/число_состояний в эталонном автомате. Раздел 2.3.4 посвящен вопросам полноты тестов, доставляемых t/70-методом. Экспериментально показано, что WO-метод в большинстве случаев доставляет неполные тесты. В параграфе 2.4 известные методы построения тестов применяются к реальным протоколам, а именно к протоколу Simple Connection (SCP) [46] и к протоколу V.76 [47, 48] (автомат, описывающий работу протокола Simple Connection, приведен в приложении 2). Отмечается, что полученные результаты не противоречат экспериментам со случайно сгенерированными автоматами в том смысле, что соотношение между длинами тестов, построенных различными методами для случайно
сгенерированных автоматов и для автоматов, описывающих протоколы, сохраняется.
Третья глава диссертации посвящена исследованию достаточных условий полноты проверяющего теста относительно модели
длине доставляемого теста. В параграфе 3.4 предложенный Я-метод адаптируется для случая, когда эталонный автомат является частичным.
В четвертой главе рассматривается задача построения полного проверяющего теста относительно моделей < 5,<, Зт (X, У)> и <5, = ,С1т(Х, )> для недетерминированного автомата S. В основе предлагаемых методов лежит общий подход, предложенный в третьей главе, когда различающие последовательности строятся в процессе построения теста. В параграфе 4.1 вводятся основные понятия и определения для недетерминированных автоматов. В параграфе 4.2 рассматривается модель
В ряде случаев задача тестирования сводится к определению принадлежности проверяемого детерминированного автомата множеству детерминированных редукций эталонного недетерминированного автомата [31]. В параграфе 4.3 рассматривается модель неисправности <5,<,Зт{Х,У)>, где 5 - недетерминированный эталонный автомат, 3М(Х,У) - множество всех полностью определенных детерминированных автоматов с числом состояний не более ти, а в качестве отношения конформности используется отношение редукции. В разделе 4.3 Л напоминается понятие г-различимости [32] между состояниями
недетерминированного автомата, которое отличается от понятия различимости состояний. В разделе 4.3.2 устанавливаются достаточные условия полноты теста для недетерминированного эталонного автомата с попарно /--различимыми состояниями, на основе которых в разделе 4.3.4 предлагается метод построения полного проверяющего теста относительно модели
Пятая глава посвящена задаче синтеза проверяющих тестов относительно модели
В параграфе 5.1 вводятся основные понятия и определения, ставится задача построения теста по мутационному автомату. В параграфе 5.2 предлагается новый метод синтеза полного проверяющего теста относительно модели
теста используется информация о детерминированных переходах в мутационном автомате, что в ряде случаев позволяет построить основу проверяющего теста, которая не обязательно будет включать все входные последовательности длины т-п+1, т.е. будет короче, чем множество VXtt'n+lt построенное для модели «черного ящика». В параграфе 5.3 эффективность предложенного метода оценивается посредством компьютерных экспериментов. Экспериментально показано, что если в мутационном автомате количество пар «текущее_состояние, входной_символ», которым соответствует не единственная пара «следующее_состояние, выходной_символ», не превышает 20% от всех пар «состояние, входной_символ», то для случайно сгенерированных автоматов длина теста, доставляемого предложенным методом, пропорциональна числу состояний в мутационном автомате.
В заключении подводится итог результатам, полученным в диссертации, и формулируются основные положения, выносимые на защиту.
Конечные автоматы
Рассмотрим дискретную систему, которая может находиться в конечном множестве внутренних состояний. Под воздействием входного сигнала система переходит в следующее внутреннее состояние, зависящее от текущего внутреннего состояния, и на выходе системы появляется соответствующий выходной сигнал. Такая система, в частности, «перерабатывает» последовательности в одном (входном) алфавите в последовательности в другом (выходном) алфавите. Если число состояний, число входных и выходных символов конечно, то в качестве математической модели такой системы можно использовать конечный автомат, при помощи которого, например, удобно представлять поведение систем, преобразующих последовательности дискретных входных сигналов в последовательности выходных сигналов.
Формально под конечным автоматом или просто автоматом в данной работе понимается инициальный, возможно, недетерминированный автомат, т.е. пятерка S={S,X,Y,hs,s\) [2], где S - конечное непустое множество состояний с выделенным начальным состоянием S\, X и Y -конечные входной и выходной алфавиты соответственно, a IISQSXXXSXY -отношение переходов. Отношение hs состоит из четверок «текущее состояние, входной символ, следующее состояние, выходной символ», называемых переходами, причем для каждой пары (s,x)eSxX существует хотя бы одна пара (s ,у) еSx Y, такая что (s,x,s ,y)ehs.
В случае, когда поведение системы описывается инициальным автоматом, неявно предполагается, что система обладает сигналом сброса, который не описан как входной символ. Иными словами, существует специальный возвратный входной сигнал г, который переводит систему из любого состояния в начальное состояние. В данной работе мы рассматриваем только такие системы и соответственно рассматриваем только инициальные автоматы.
Если для любой тройки (s,x,y) eSxXx Y в автомате существует не более одного перехода из состояния s под действием входного символа х с выходным символом у, то говорят, что автомат называется наблюдаемым. Автомат называется детерминированным, если для каждой пары (s, x)eSxX существует не более одной пары (s\y)eSxY такой, что (s,x, s ,y)ehs. Если для всякого состояния sєS и всякого входного символа хеХ, существует пара (s ,y)eSxY такая, что (s, х, s , y)ehs, то автомат называется полиостью определенным; в противном случае -частично определенным (или частичным). В полностью определенном автомате из любого состояния существует хотя бы один переход под действием любого входного символа, в то время как в частичном автомате такого перехода может не быть. Для простоты представления результатов в тексте диссертации, за исключением параграфа 3.4, мы рассматриваем только полностью определенные автоматы.
В детерминированном полностью определенном автомате вместо отношения поведения обычно используют две функции: Ss1. SxX- S и As. SxX- Y. Функции &и определяются соотношением: Ss(s,x)=s и Xs(s,x)=y тогда и только тогда, когда (stx,s y)ehs. Функция называется функцией переходов автомата, функция Xs функцией выходов. Обозначим через У множество всех последовательностей конечной длины из элементов множества X, включая пустую последовательность є (длины 0, по определению). Кроме того, через Xя мы обозначаем множество всех последовательностей из длина которых равна т, и для любого подмножества UQX через PrefiJJ) обозначается множество всех начальных отрезков последовательностей из U. Множество U называется префикс замкнутым, если Pref(U)=U.
Под действием любой входной последовательности a-Хі...ХкєХ в состоянии s в автомате 5 реализуется последовательность переходов s-s\-(xify\) s2-...- sk-{xk/yk) sk+i, где для всех /=1,...,, (shx,si+i,yi)ehs или Si+\=5s(Si, Хг) wyi=Xs{sh ХІ) Б детерминированном автомате. Говорят, что последовательность а переводит автомат из состояния s в состояние Sifi. При этом состояние s называется начальным состоянием перехода, а состояние Sk+i - конечным состоянием. Последовательность у\...уісєУ называется реакцией автомата 5 на входную последовательность a -X\..,Xk в состоянии 5. В общем случае в недетерминированном автомате для входной последовательности может существовать больше одной реакции. Множество всех реакций автомата в состоянии s на входную последовательность а далее обозначается outs(s,a). Если 5 -детерминированный автомат (5,Х,У, 5І-,Л5,$І), то иногда вместо outs(s,a) будем писать As(s, а). Множество всех входо-выходных последовательностей автомата 5 в состоянии s, получаемых при последовательных переходах из состояния s, называется его языком в состоянии s и обозначается Xs{s). Язык s(s{) автомата в начальном состоянии s\ называется языком автомата 5 и обозначается Xs.
Генератор псевдослучайных автоматов
Автомат в программной реализации задается списком переходов table, каждый элемент которого есть четверка текущее_состояние, входной__символ, следующее_состояние, выходной_символ . При задании автомата задается число к входных символов, число у выходных символов и число п состояний, с заранее определенным начальным состоянием init_state.
Автоматы при проведении экспериментов генерируются следующим образом. Для каждой пары «текущее_состояние/входной_символ» случайным образом выбираются состояние, в которое переходит автомат под воздействием данного входного символа, и выходной символ автомата. При выборе состояния с помощью функции randQ языка C++ случайным образом генерируется число в диапазоне от 0 до и-1. Аналогичным образом для заданной пары исходное состояние/входной символ определяется и выходной символ автомата: случайным образом генерируется число в диапазоне от 0 до числа .у-1. В программе осуществляется проверка, чтобы все заданные выходные символы были реализованы в генерируемом автомате.
Поскольку исследуемые нами методы тестирования применимы только к связным и приведенным автоматам, в программе выполняется проверка каждого сгенерированного автомата на связность и приведенность. Если сгенерированный автомат не удовлетворяет нашим требованиям, то для такого автомата тесты не строятся, и генерируется новый автомат. Как показали эксперименты, генерация 50 различных связных и приведенных автоматов с заданными параметрами осуществляется достаточно быстро. Например, чтобы сгенерировать 50 автоматов с небольшим числом переходов от 40 до 500 требуется меньше секунды. При генерации автоматов с большим числом переходов от 500 до 1000 требуется от одной до пяти секунд.
Оценим основные свойства генерируемых автоматов, которые могут влиять на длину построенного теста.
Согласно утверждению 2 главы 1, любой проверяющий тест относительно области 3m{X,Y) строится в два этапа: на первом шаге устанавливается отображение между состояниями проверяемого и эталонного автоматов (так называемая идентификация состояний) или устанавливается, что такого соответствия не существует; в последнем случае проверяемый автомат не эквивалентен эталонному. На втором шаге проверяется соответствие между переходами автоматов. Таким образом, нужно 1) попасть в каждое состояние эталонного автомата и идентифицировать данное состояние, 2) пройти по каждому переходу и проверить финальное состояние каждого перехода. Чтобы попасть в каждое состояние эталонного автомата строится множество достижимости, т.е. множество последовательностей, переводящих связный автомат из начального состояния во все состояния. Для идентификации состояний в зависимости от метода строится некоторое множество различающих последовательностей. Таким образом, на длину теста влияют как длина последовательностей множества достижимости, так и длина различающих последовательностей. Очевидно, что характеристики данных множеств определяются параметрами генерируемых автоматов.
Длина этих последовательностей существенно зависит от следующих параметров:
1)от числа состояний, достижимых из одного состояния по всем входным символам (множество достижимости);
2) от числа различных выходных символов, соответствующих входному символу (различающие последовательности).
Мы провели серию экспериментов, чтобы выяснить 1) как распределяются выходные символы в автомате для входного символа; 2) как распределяются следующие состояния в автомате для текущего состояния. С этой целью для заданных параметров автомата nlkly (число_состояний/число_входных_символов/число_выходных_символов) псевдослучайным образом генерировалось 50 автоматов. Для каждого автомата определялся 1) входной символ, которому соответствует максимальное число выходных символов автомата; 2) состояние автомата, из которого автомат переходит в максимальное число новых состояний под действием всех входных символов.
Достаточные условия полноты теста
В данной главе рассматривается задача построения полного проверяющего теста относительно модели «черного ящика», т.е. относительно модели неисправности S, ,3m(X,Y) . Ранее в параграфе 1.6 был рассмотрен ряд известных методов построения тестов относительно данной модели. Предлагаемый нами метод имеет в своей основе ту же структуру, что и другие методы синтеза проверяющих тестов без перебора автоматов из области неисправности для модели «черного ящика» (параграф 1.6). Основным отличием предлагаемого метода является тот факт, что идентификаторы состояний эталонного автомата не строятся заранее, а определяются в процессе синтеза теста с учетом уже построенной части теста. В результате может оказаться, что некоторые последовательности множества VPref[X" nH) можно продлить более короткими последовательностями, которые совместно с уже построенной частью теста образуют идентификатор соответствующего состояния, а некоторые из последовательностей вообще не требуют продления.
В параграфе 3,1 формулируются достаточные условия полноты проверяющего теста относительно модели S,=,3m(X Y) i т.е. в предположении, что число состояний проверяемого автомата не больше числа т.
В параграфе 3.2 предлагается метод построения полного проверяющего теста относительно модели «черного ящика», в котором различающие последовательности, проверяющие переходы в проверяемом автомате, строятся в процессе построения теста. В разделе 3.2.1 обсуждается порядок выбора последовательностей из множества VPref(X" "+l) для добавления к ним соответствующих различающих последовательностей, чтобы полученное множество было полным проверяющим тестом. В разделе 3.2. предлагается Я-метод построения полного проверяющего теста относительно модели «черного ящика» на основе теоремы 3.1 и результатов раздела 3.2.1. В параграфе 3.3 приводятся экспериментальные результаты по оценке длин тестов, построенных предложенным методом И Ж/-МЄТОДОМ, который, как показано в главе 2, доставляет наиболее короткие проверяющие тесты. Экспериментально показано, что для случайно сгенерированных автоматов Я-тесты оказываются почти в два раза короче, чем тесты, построенные Я5Т-методом. В параграфе 3.4 Я-метод адаптируется для случая, когда эталонный автомат является частичным.
Достаточные условия полноты теста
В данном разделе мы формулируем достаточные условия полноты проверяющего теста относительно модели 5,=,Зт(Х,У) , в которой эталонный автомат является связным, приведенным и детерминированным, т.е. любые два состояния различимы между собой некоторой входной последовательностью и все состояния автомата достижимы из начального состояния.
Теорема 3.1. Пусть TS - множество входных последовательностей эталонного автомата 5=(5Д,У, %Д5,Яі), содержащее подмножество VXm n+l, где V - множество достижимости автомата S. Множество TS является полным проверяющим тестом относительно модели S,=,3 m(X,Y) , если выполняются следующие условия:
I. Для любых двух (различных) состояний автомата 5, достижимых по последовательностям а и J3 из V, множество TS содержит последовательности ее и pa?, где о есть последовательность, различающая состояния Ss(slta) и Ss{svfT).
2.Для любой последовательности ap, aeV, \р\=т-п+\, и каждого непустого начального отрезка / последовательности Д который переводит автомат 5 из состояния Ss{s{,а) в состояние s, множество TS содержит последовательности ар\со и уа , где /є V, 5S(SX,Y) S, И СО есть последовательность, различающая состояния ddjs{iap\) и Sds f).
3. Для любой последовательности ар, ае V, \Д-т-п+1, и любых двух непустых начальных отрезков Д и / последовательности р таких, что Ss(sl9api)#Ss(sitap2)9 множество TS содержит последовательности ар\СО и ар2б), где со- последовательность, различающая состояния Ss(s]taP\) и Ss(svap2).
Доказательство (от противного). Рассмотрим множество TS входных последовательностей и предположим, что существует проверяемый автомат t=(I,X,Y,Si,Z/,i]) с т состояниями, который различим с эталонным автоматом 5, и, тем не менее, реакции автоматов /и 5на каждую входную последовательность множества TS совпадают. Обозначим через Р множество состояний, в которые может перейти проверяемый автомат / из начального состояния под действием входных последовательностей из множества V, и пусть v есть кратчайшая последовательность из некоторого состояния Зі{і\,щ) множества Р, которая различает состояния Ssis aj) и /(/, a/), ay є V. По определению, множество TS содержит последовательность (Xjp, где /?есть начальный отрезок длины т-п+\ последовательности к Рассмотрим множество і?, которое есть объединение последовательностей множества достижимости и множества а,-/? всех непустых начальных отрезков /? последовательности Д Число таких последовательностей соответственно равно л+(т-л+1)=/м+1. Поскольку / имеет не более т состояний, в этом множестве существуют две последовательности, которые переводят проверяемый автомат / из начального состояния в одно и то же состояние /. Пусть Л={аь...,а„,...,ат+1},гдедля/=и+1,...,т+1 at=ajfiк Si(ii,ai)=5/(iifar). Относительно і и г возможны три различных случая: 1) i n, г п\ 2) i n r;3)i n,r n.
Построение полного проверяющего теста относительно эквивалентности
Пусть S=(S,X,Y,hs,s\) - полностью определенный наблюдаемый недетерминированный автомат. Пусть a - входная последовательность автомата, и /?- реакция автомата 5 на последовательность а в состоянии s. Обозначим через s-after-a (y-after-o//3) множество состояний, в которые автомат 5 может перейти из состояния s под действием входной (входо-выходной) последовательности a {alp). Множество таких состояний для случая, когда s есть начальное состояние автомата 5, будем обозначать 5-after-or (S-dXttr-al(3). Заметим, что в наблюдаемом автомате множество состояний s-after-afp состоит ровно из одного состояния для любого состояния s и любой входо-выходной последовательности alp в состоянии s. Состояние s автомата 5 детерминировано достижгаю (д-достижимо) из начального состояния по входной последовательности а=Х\,..Хк, если под действием а в автомате S реализуется последовательность переходов s\ (x\fyi)- S2--»- Sk-(xkfyk)-+sf гДе для всех /=i,„.,fc, переход из состояния Si под действием входного символа xi детерминированный, т.е. S;-after-Xi={si+\}. Понятие д-достижимости может быть определено сложнее [44], в этом случае длина последовательностей в множестве д-достижимости будет экспоненциально зависеть от числа состояний эталонного автомата.
Любой автомат имеет, по крайней мере, одно д-достижимое состояние, а именно начальное состояние.
Множество последовательностей, по которым достижимы все д-достижимые состояния автомата, называется множеством д-достижимости автомата. Заметим, что в отличие от детерминированных автоматов, число последовательностей в множестве достижимости, построенном для недетерминированного автомата, может оказаться меньше, чем число состояний эталонного автомата. Причиной является тот факт, что эталонный автомат в ответ на входную последовательность, повторно подаваемую в начальном состоянии, может переходить в различные состояния с различными выходными последовательностями.
Построение полного проверяющего теста относительно эквивалентности
В данном параграфе мы полагаем, что эталонное поведение и поведение проверяемой системы описаны полностью определенными наблюдаемыми недетерминированными автоматами, и предлагаем метод построения полного проверяющего теста относительно модели неисправности S,=,Qm(X,Y) . При построении тестов относительно модели 5,=, Qm (X, Y) предполагается, что все возможные реакции недетерминированного проверяемого автомата на данную входную (тестовую) последовательность можно пронаблюдать в процессе многократной подачи этой последовательности.
Достаточные условия полноты относительно модели неисправности 5,Slfim(X,Y)
Пусть 5=(S,X,F,/z5,Si) - недетерминированный наблюдаемый эталонный автомат с п состояниями и входным алфавитом X, и проверяемый автомат имеет не более т состояний, т п, т.е. проверяемый автомат /eQm(X,Y).
Следующая теорема устанавливает достаточные условия, согласно которым различающие последовательности можно выбирать на основе уже построенной части проверяющего теста.
Теорема 4.1. Пусть TS - множество входных последовательностей эталонного недетерминированного наблюдаемого автомата S=(S,X,Y,hs,S\), содержащее подмножество QXm n+i, где Q - множество достижимости автомата 5! Множество TS является полным проверяющим тестом относительно модели 5,=, С1т {Х Y) , если выполняются следующие условия:
1. Для любых двух последовательностей а и /3 из Q, для любых двух (различных) состояний saeS-a.uev-a и s eS-after-Д множество TS содержит последовательности асо и р, где т есть последовательность, различающая состояния sa и sp.
2. Для любой последовательности afi, aeQ, \fi\=m-rt+l, любого состояния sae5-after-a и каждого непустого начального отрезка Д последовательности Д который переводит автомат S из состояния saeS after- а в состояние san є 5-after- afi\, множество TS содержит последовательности ар\0) и усо, где yeQ, sуе5-after- иsyfisap , и гуесть последовательность, различающая состояния sr и saa .
3. Для любой последовательности ар, aeQ, }J3\=m-n+\, любого состояния sae 5-after-a и любых двух непустых начальных отрезков Д и Д последовательности Д для любых двух состояний san , saa таких, что sapx sap2 и s є5-аіїег-аД, sap є5-after-a/?2, множество Г5содержит последовательности ар\б) и a/JjO), где со - последовательность, различающая состояния saa и saa .
