Исследование и разработка конечно-автоматных методов синтеза проверяющих тестов для управляющих систем тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Дорофеева, Маргарита Юрьевна

• Дорофеева, Маргарита Юрьевна
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Дорофеева, Маргарита Юрьевна

Введение.

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

1.1. Конечные автоматы.

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

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

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

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

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

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

1.4. Выбор модели неисправности.

1.4.1. Модель «черного ящика» <S,=,3M(X,Y)>.

1.4.2. Мутационный автомат и его использование для описания модели неисправности.

1.5. Постановка задачи синтеза тестов.

1.6. Методы синтеза проверяющих тестов для конечных автоматов относительно модели <S,=,-Jm(X,Y)>.

1.6.1. Построение теста перечислением неисправностей.

1.6.2. Идентификация состояний.

1.6.3. Методы построения тестов.

1.7. Методы синтеза проверяющих тестов для недетерминированных автоматов.

1.8. Методы синтеза проверяющих тестов относительно мутационного автомата.

1.9. Теоретические оценки длины проверяющего теста.

1.10. Выводы по главе.

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. Полнота UIO-тестов.

2.4. Результаты экспериментов с протоколами Simple Connection Protocol и V.76 Protocol.

2.4.1. Сравнение длин тестов, построенных различными методами, для протокола SCP.

2.4.2. Сравнение длин тестов, построенных различными методами, для протокола V.76.

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. Достаточные условия полноты относительно модели неисправности <S,=,Qm(X,Y)>.

4.2.2. Метод построения полного проверяющего теста относительно модели неисправности <5,s,Qm(X,y)>.

4.3. Построение полного проверяющего теста относительно редукции.

4.3.1. Понятие г-различимости.

4.3.2. Достаточные условия полноты теста.

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

4.4. Основные результаты главы.

5. Метод синтеза полных проверяющих тестов по мутационному автомату.

5.1. Основные понятия и определения.

5.2. Построение полного проверяющего теста относительно модели <S,=,Sub(Q)>.

5.3. Экспериментальные результаты.

5.4. Основные результаты главы.

Введение диссертации (часть автореферата) на тему «Исследование и разработка конечно-автоматных методов синтеза проверяющих тестов для управляющих систем»

Актуальность проблемы. Конечные автоматы широко используются в качестве математической модели при синтезе тестов для контроля правильности функционирования систем логического управления [1-6], в частности, при тестировании телекоммуникационных протоколов [7-11], а в последнее время и при тестировании программного обеспечения [12 и др.]. Математической моделью процесса контроля является эксперимент с автоматом [2], т.е. процесс приложения тестовых последовательностей к проверяемой системе, поведение которой описано автоматом, наблюдении соответствующих реакций и вывода заключения на основе этих наблюдений о пригодности или непригодности тестируемой системы к дальнейшему использованию. При использовании автоматного подхода обычно предполагается, что множество проверяемых автоматов описывает поведение систем со всеми возможными неисправностями, и если множество входных воздействий (проверяющий тест) может обнаружить каждую систему, не пригодную к использованию, то такое множество входных воздействий называется полным проверяющим тестом (относительно заданного множества неисправностей). Несмотря на большое количество публикаций по синтезу проверяющих тестов для автоматов [1324 и др.], задача далека от того, чтобы считаться решенной. По-прежнему неизвестны необходимые и достаточные условия полноты проверяющих тестов относительно различных моделей, что не позволяет строить оптимальные тесты. Полные тесты, построенные относительно известных моделей, в частности, относительно модели «черного ящика», т.е. для случая, когда известна только верхняя оценка числа состояний в проверяемой системе [13, 18, 19], обладают высокой полнотой, но их размерность ограничивает практическое применение. Более того, в большинстве случаев тесты, доставляемые известными методами, обладают большой избыточностью. В связи с этим продолжается поиск новых моделей неисправности, отражающих ошибки в реальных системах, и допускающих построение тестов достаточно высокого качества. Одной из таких моделей является модель «серого ящика», когда полный проверяющий тест строится относительно множества всех подавтоматов специального мутационного автомата [7, 23, 24]. Модель мутационного автомата при синтезе проверяющих тестов активно используется при тестировании, в том числе, программного обеспечения [12 и др.]. Таким образом, задача синтеза проверяющих тестов для контроля функционирования систем логического управления методами теории автоматов является актуальной.

Цель работы. Теоретическое и экспериментальное исследование методов построения полных проверяющих тестов для конечных автоматов относительно моделей «черного ящика» и «серого ящика» без перебора автоматов из области неисправности и разработка на основе проведенных исследований новых методов, доставляющих проверяющие тесты по длине близкие к оптимальным.

Методы исследования. Для решения поставленных задач применяется аппарат теории автоматов, математической логики, а также компьютерные эксперименты для экспериментального исследования различных методов построения тестов и оценки эффективности предложенных методов.

Достоверность полученных результатов. Все научные положения и выводы, содержащиеся в работе, основаны на утверждениях, доказанных с использованием аппарата дискретной математики, в частности, с использованием аппарата теории автоматов.

Научная новизна. Научная новизна работы состоит в следующем.

1. Проведен экспериментальный анализ методов синтеза проверяющих тестов без перечисления проверяемых автоматов относительно модели черного ящика», т.е. относительно модели неисправности <S,=,Sm(X,V)> на одном и том же множестве автоматов, сгенерированных псевдослучайным способом, а также на автоматах, описывающих телекоммуникационные протоколы, с целью сравнения длин тестов, доставляемых различными методами. Экспериментально показано, что 1) тесты, построенные без перебора автоматов из множества 3m{X,Y), являются избыточными относительно теста, построенного посредством перебора проверяемых автоматов; 2) UIO- и £>£-методы доставляют тесты с наименьшей избыточностью, но эти методы не всегда применимы; 3) из рассмотренных методов, применимых к любому связному приведенному автомату, самые короткие тесты доставляют Wp- и Я57-методы. Согласно проведенным экспериментам, соотношения между длинами тестов, построенных различными методами, для случайно сгенерированных автоматов и для автоматов, описывающих протоколы, сохраняются.

2. Установлены новые достаточные условия полноты проверяющих тестов для детерминированных автоматов относительно модели неисправности <S,=,3m(X,Y)>. На основе этих достаточных условий предложен метод (Я-метод) синтеза полных проверяющих тестов, который не требует перебора автоматов из области неисправности, и основан на использовании уже построенной части теста при идентификации состояний проверяемого автомата. Экспериментально показано, что в среднем для небольших автоматов длины тестов, построенных Я-методом и методом, основанным на переборе всех автоматов из множества 3m{X,Y), совпадают. Кроме того, Я-метод имеет значительное преимущество перед Я57-методом (а, следовательно, и перед другими известными абстрактными методами) по длине доставляемого теста. Показано, что Я-метод применим и для случая, когда эталонный автомат является частичным.

3. Разработанный Я-метод адаптирован для случая, когда эталонный автомат является недетерминированным для проверки отношений редукции и эквивалентности.

4. Предложен новый метод синтеза проверяющего теста относительно мутационного автомата, который для определенных классов мутационных автоматов доставляет более короткие проверяющие тесты, чем известные методы. Экспериментально показано, что в большинстве случаев, когда число пар «текущеесостояние, входнойсимвол», для которых в мутационном автомате существует более одного перехода, не превышает 20%, длина теста полиномиально зависит от числа состояний мутационного автомата.

Практическая ценность. На основе проведенных исследований создан пакет прикладных программ для синтеза полных проверяющих тестов для конечных автоматов. Разработанные методы и программы были опробованы при тестировании телекоммуникационных протоколов и могут быть использованы в современных комплексах диагностики и тестирования дискретных управляющих систем.

Реализация полученных результатов. Исследования, результаты которых изложены в диссертации, проводились в рамках следующих проектов.

1. Научная Программа МО РФ «Научные исследования высшей школы в области производственных технологий» (2000 г.)

2. Проект МО РФ Е00-2.0-33 «Исследование отношений редукции и эквивалентности между недетерминированными автоматами» (2001-2002 гг.)

3.Грант Роснауки по мероприятию 1.11 «Развитие системы стажировок молодых ученых и преподавателей в крупных научно-образовательных центрах (включая зарубежные) и участие в конференциях, симпозиумах, семинарах, школах (в том числе за рубежом)» федеральной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 гг. по приоритетному направлению «Развитие инфраструктуры» (XVII очередь) (2005 г.)

4. Грант Роснауки по мероприятию 1.9 «Проведение молодыми учеными научных исследований по приоритетным направлениям науки, высоких технологий и образования» федерельной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 гг. по приоритетному направлению «Развитие инфраструктуры» (XXII очередь) (2005 г.)

5. Грант Роснауки по мероприятию 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 стр.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Дорофеева, Маргарита Юрьевна

5.4. Основные результаты главы

В данной главе предложен метод построения проверяющего теста относительно мутационного автомата в случае, когда число состояний мутационного автомата может превышать число состояний эталонного автомата. В предложенном методе используется известная информация о детерминированных переходах в мутационном автомате, за счет этого исчезает экспоненциальная зависимость длины проверяющего теста от разности т-п, где т - число состояний мутационного автомата, а п- число состояний эталонного автомата. Экспериментально показано, что если в мутационном автомате число пар «текущеесостояние, входнойсимвол», для которых существует больее одного перехода, составляет не более 20%, то для всех случайно сгенерированных автоматов длина теста, построенного по алгоритму 5.1, пропорциональна произведению числа состояний мутационного автомата на число пар «текущеесостояние, входнойсимвол», для которых в мутационном автомате существует более одного перехода.

Заключение

В диссертации предложены методы синтеза проверяющих тестов для дискретных управляющих систем методами теории автоматов. В работе проведен теоретический и экспериментальный анализ методов построения проверяющих тестов для детерминированных и недетерминированных автоматов относительно различных моделей неисправностей, а именно относительно модели «черного ящика», когда известна только верхняя оценка числа состояний проверяемых автоматов, и относительно модели «серого ящика» (мутационного автомата). Проведен сравнительный анализ известных методов построения проверяющих тестов для детерминированных автоматов при ограниченном числе состояний проверяемого автомата. Исследована зависимость средней длины тестов, построенных с использованием различных методов, от размера эталонного автомата. Кроме того, экспериментально определено, как часто применимы методы, основанные на использовании уникальных входо-выходных последовательностей (UIO) и диагностической последовательности (DS). Эксперименты проводились на одном и том же множестве автоматов, сгенерированных псевдослучайным способом. Эксперименты, проведенные с автоматами, построенными по протоколам Simple Connection и V.76, показали, что соотношения между длинами тестов, построенных различными методами для случайно сгенерированных автоматов и для автоматов, описывающих протоколы, сохраняются. Отмечается, что проверяющий тест можно оптимизировать, т.е. существенно сократить его длину, при более удачном выборе различающих последовательностей.

В работе сформулированы новые достаточные условия полноты проверяющего теста относительно модели «черного ящика», т.е. в предположении, что число состояний проверяемого автомата не больше числа т. На основе сформулированных условий разработан метод синтеза теста для полностью определенного детерминированного автомата относительно эквивалентности. Предложенный метод основан на использовании информации об уже построенной части теста при выборе различающих последовательностей для идентификации состояний и переходов. Показано, что предложенный метод применим и для случая, когда эталонный автомат является частичным. Экспериментально показано, что, предложенный метод имеет значительное преимущество перед известными методами построения тестов относительно модели «черного ящика» по длине доставляемого теста. Это преимущество возрастает с ростом разности числа состояний проверяемого и эталонного автоматов. Экспериментально также показано, что для автоматов с небольшим числом состояний, предложенный метод доставляет тесты по длине близкие к оптимальным, т.е. избыточность тестов, построенных этим методом, минимальна по сравнению с другими известными методами. Предложенный метод адаптирован для случая, когда поведение эталонной и проверяемой систем описываются недетерминированными автоматами. В этом случае в качестве отношения конформности используется отношение эквивалентности, и проверяющий тест строится относительно модели <S,=,Q.m(X,Y)>, где Q.m(X,Y) - множество всех недетерминированных автоматов не более чем с т состояниями. Также предложенный метод адаптирован для модели <S,<,3m(X,Y)>, где 5- недетерминированный эталонный автомат, < - отношение редукции, 3m(X,Y) - множество всех детерминированных автоматов не более чем с т состояниями. Однако, хотя предложенный метод доставляет тесты, по длине близкие к оптимальным, тесты, построенные относительно модели «черного ящика» по-прежнему являются достаточно длинными. Поэтому в работе также рассматривается модель неисправности, в которой пользователь определяет наиболее типичные (часто встречающиеся) неисправности. Такая модель известна под названием модели «серого ящика» и успешно применяется в технической диагностике. В этом случае проверяющий тест строится относительно множества подавтоматов специального мутационного, в общем случае недетерминированного, автомата. В разделе предлагается метод построения проверяющих тестов для специального вида мутационного автомата, в котором имеется небольшое количество пар «текущеесостояние, входнойсимвол», которым соответствует более одной пары «следующеесостояние, выходнойсимвол», однако каждый такой переход в проверяемом автомате может быть переходом в любое состояние с любым выходным символом. Такие автоматы особенно интересны при регрессивном тестировании, когда тест генерируется только для проверки небольших модификаций в эталонной системе. В данной работе предложен метод построения тестов относительно мутационного автомата в случае, когда число состояний проверяемого автомата может превышать число состояний эталонного автомата. В предложенном методе используется известная информация о детерминированных переходах в мутационном автомате, что позволяет значительно оптимизировать проверяющий тест, т.е. сократить его длину. Экспериментально показано, что если в мутационном автомате количество пар «текущеесостояние, входнойсимвол», для которых существует больше одного перехода, составляет не более 20%, то для всех случайно сгенерированных автоматов длина теста, построенного по алгоритму 5.1, пропорциональна произведению числа состояний мутационного автомата на число пар «текущеесостояние, входнойсимвол», для которых в мутационном автомате существует более одного перехода.

На защиту выносятся следующие результаты:

1. Сформулированы новые достаточные условия полноты проверяющих тестов для детерминированных автоматов. На основе этих достаточных условий предложен новый метод (Я-метод) синтеза полных проверяющих тестов без перебора автоматов из области неисправности относительно модели «черного ящика», который основан на использовании уже построенной части теста при идентификации состояний проверяемого автомата. Экспериментально показано, что предложенный метод доставляет проверяющие тесты с меньшей избыточностью, чем другие известные методы.

2. Сформулированы новые достаточные условия полноты проверяющих тестов для недетерминированных автоматов относительно отношений эквивалентности и редукции. На основе предложенных достаточных условий Я-метод адаптирован для проверки этих отношений для случая, когда эталонный автомат является недетерминированным.

3. Предложен новый метод синтеза проверяющего теста относительно мутационного автомата, который для определенных классов мутационных автоматов доставляет более короткие проверяющие тесты, чем известные методы. Экспериментально показано, что если в мутационном автомате количество пар «текущеесостояние, входнойсимвол», для которых существует больше одного перехода, составляет не более 20%, то для всех случайно сгенерированных автоматов длина теста, построенного предложенным методом, пропорциональна произведению числа состояний мутационного автомата на число пар «текущеесостояние, входнойсимвол», для которых в мутационном автомате существует более одного перехода.

Список литературы диссертационного исследования кандидат технических наук Дорофеева, Маргарита Юрьевна, 2007 год

1. Мур Э. Ф. Умозрительные эксперименты с последовательными машинами // Автоматы. - М.: Изд-во иностр. лит., 1956. - С. 179-210.

2. Гилл А. Введение в теорию конечных автоматов. М.: Наука, 1966-272с.

3. Богомолов A.M., Грунский И.С., Сперанский Д.В. Контроль и преобразования дискретных автоматов. Киев: Наук. Думка, 1975. - 176с.

4. Сперанский Д.В., Боголюбов A.M. Контроль и преобразование дискретных автоматов. Киев, 1975.

5. Богомолов A.M., Сперанский Д.В. Аналитические методы в задачах контроля и анализа дискретных устройств. Саратов: Изд-во Сарат. ун-та, 1986.-240с.

6. Грунский И.С., Козловский В.А., Пономаренко Г.Г. Представление конечных автоматов фрагментами поведения. Киев: Наук. Думка, 1990. -232с.

7. Грунский И.С., Петренко А.Ф. Построение проверяющих экспериментов с автоматами, описывающими протоколы // Автоматика и вычислительная техника. 1988, № 4. - С. 7-14.

8. Петренко А.Ф. Эксперименты над протокольными объектами // Автоматика и вычислительная техника. 1987, № 1. - С. 16-21.

9. G.v. Bochmann, A. Petrenko. Protocol testing: review of methods and relevance for software testing. // ISSTA'94, ACM Intern. Symp. on Software Testing and Analysis, Seattle, U.S.A., 1994. P. 109-124.

10. G. v. Bochmann, C. A. Sunshine. Formal methods in communication protocol design // IEEE Trans, on Comm., Vol 28,1980. P. 624-631.

11. A. Petrenko. Checking experiments with protocol machines // Proceedings of the IFIP TC6 4th International Workshop on Protocol Test Systems, 1991, North-Holland.-P. 83-94.

12. Бурдонов И. Б., Косачев А. С., Кулямин В. В. Использование конечных автоматов для тестирования программ // Программирование. -2000, №2.-С. 12-28.

13. Василевский М.П. О распознавании неисправности автоматов // Кибернетика. 1973, № 4. - С. 93-108.

14. T.S. Chow. Test software design modeled by finite state machine // IEEE Transactions. 1978, SE-4, No.3. - P. 178-187.

15. G. Gonenc. A method for the design of fault detection experiments // IEEE Trans. Computers. 1970, vol. C-19. No. 6. - P. 551-558.

16. Sabnani K., Dahbura A. A protocol test generation procedure // Computer Networks and ISDN Systems. 1988, vol. 15, No. 4. - P. 285-297.

17. S.T. Vuong, W.W. L. Chan, and M.R. Ito. The UlOv-method for protocol test sequence generation // Proc. of the IFIP TC6 2nd IWPTS, North-Holland, 1989.-P. 161-175.

18. Евтушенко H.B., Петренко А.Ф. Метод построения эксперимента для произвольного детерминированного автомата // Автоматика и вычислительная техника. 1990, № 5. - С. 73-76.

19. Fujiwara S., Bochmann G. v., Khendek F., Amalou M., Ghedamsi A. Test selection based on finite state models // IEEE Trans. 1991, SE-17, No. 6. - P. 591-603.

20. A. Petrenko, G.v. Bochmann, R. Dssouli. Conformance relations and test derivation // Proceedings of 6th IFIP International Workshop on Protocol Test Systems, France, 1993.-P. 161-182.

21. Pomeranz, S.M. Reddy. Test Generation for Multiple State-Table Faults in Finite State Machines // IEEE Transactions on Computers. 1997, vol.48, №7. -P. 783-794.

22. D. Lee, M. Yannakakis. Testing FSMs: state identification and verification // IEEE Transactions on Computers. 1994, vol. 43, №3. - P. 306-320.

23. A. Petrenko, N. Yevtushenko. Test Suite Generation for a Given Type of Implementation Errors // Proceedings of IFIP 12th International Conference on Protocol Specification, Testing and Verification, 1992. P. 229-243.

24. I. Koufareva, A. Petrenko, N. Yevtushenko. Test Generation Driven by User-Defined Fault Models // Testing of Communicating systems: Methods and Applications. Kluwer Academic Publishers, 1999. - P. 215-223.

25. Куфарева И. Б. Применение недетерминированных автоматов в задачах синтеза проверяющих тестов в системах логического проектирования. ТГУ, Томск, диссертационная работа, 2000.

26. К. El-Fakih, N. Yevtushenko, and G. v. Bochmann. FSM-based incremental conformance testing methods // IEEE Transactions on Software Engineering. 2004, vol. 30 No.7. - P. 425-436.

27. Евтушенко H.B., Петренко А.Ф., Тренькаев B.H. Метод тестирования автоматных сетей, основанный на тестируемом поведении компоненты // Автоматика и вычислительная техника. 1996, № 2. - С. 48-59.

28. Евтушенко Н.В., Тренькаев В.Н. Методы синтеза проверяющих тестов для компоненты автоматной сети //Новые информационные технологии в исследовании дискретных структур. Доклады второй всероссийской конференции. Екатеринбург, 1998. - С. 219-223.

29. Пархоменко П.П. Основы технической диагностики. М.: Энергия, 1976.-464 с.

30. Матросова А. Ю. Алгоритмические методы синтеза тестов. Томск: Изд-во Томского госуниверситета, 1990. - 207 с.

31. A. Petrenko, N. Yevtushenko, G.v. Bochmann. Testing Deterministic Implementations from Nondeterministic FSM Specifications // Proceedings of

32. IP TC6 9th International Workshop on Testing Of Communicating Sytems. -Germany, 1996.-P. 125-140.

33. P.H. Starke. Abstract Automata. North-Holland: American Elsevier, 1972. -419p.

34. Лукьянов Б.Д. О различающих и контрольных экспериментах с недетерминированными автоматами // Кибернетика и системный анализ. -1995, №5.-С. 69-76.

35. Лукьянов Б.Д. Детерминированные реализации недетерминированных автоматов // Кибернетика и системный анализ. 1996, №4. - С. 34-50.

36. S. Boroday. Distinguishing Tests for Nondeterministic Finite State Machines // Proceedings of 11th International Workshop on Testing of Communicating Systems. Kluwer Academic Publishers, 1998. - P. 101-107.

37. T. Kim, T. Villa, R. Brayton, A. Sangiovanni-Vincentelli. Synthesis of FSMs: functional optimization. Kluwer Academic Publishers, 1997.

38. B. Yang, H. Ural. Protocol conformance test generation using multiple UIO sequences with overlapping // Computer Communication Review. 1990, No. 4. -P. 118-125.

39. Luo G., Petrenko A., Bochman G.v. Selecting test sequences for partially-specified nondeterministic state machines // Proceedings of IFIP 6th International Workshop on Protocol Test Systems, 1995. P. 95-110.

40. D.Lee, K. Sabnani, D. Kristol, S. Paul. Conformance testing of protocols specified as communicating finite state machines a guided random walk based approach // IEEE Transactions on Communications. - 1996, vol. 44, No. 5. - P. 631-640.

41. Kang D., Kang S., Kim M., Yoo S. A weighted random walk approach for conformance testing of system specified as communicating finite state machines // Proceedings of the Inter. Conf. FORTE X /PSTV XVII, 1997. P. 267-282.

42. Gerard J. Holzmann. Design and validation of computer protocols // Prentice-Hall, Englewood Cliffs. 1991.

43. A. Petrenko, N. Yevtushenko, G.v. Bochmann. Fault models for testing in context // Proceedings of IFIP 1th Joint International Conference FORTE/PSTV. -Chapmann & Hall, 1996.-P. 163-178.

44. A. Petrenko, and N. Yevtushenko. Conformance tests as checking experiments for partial nondeterministic FSM // Proceedings of the 5th International Workshop on Formal Approaches to Testing of Software, 2005.

45. R. M. Hieron, Adaptive Testing of a deterministic implementation against a non-deterministic finite state machines // The computer journal. 1998, vol.41.-P. 349-355.

46. W.-H. Chen. Executable test sequence for the protocol data flow property // Proceedings of Formal Description Techniques for Distributed Systems and Communication Protocols, and Protocol Specification, Testing, and Verification, FORTE/PSTV'01. 2001.

47. ITU-T Recommendation V.76, "Generic multiplexer using V.42 LAPM-based procedures". 1996, Series V: Data communication over the telephone network.

48. ITU-T Recommendation V.42, "Error-Correcting Procedures for DCEs Using Asynchronous-to Synchronous Conversion". 2002, AAP29-03/02.

49. A. Petrenko, N. Yevtushenko. Testing from partial deterministic FSM specifications // IEEE Transactions on Computers. 2005, 54(9). - P. 1154-1165.

50. Евтушенко H.B., Петренко А.Ф. Синтез проверяющих экспериментов в некоторых классах автоматов // Автоматика и Вычислительная техника. -1990,№4.-С. 59-64.

51. Hennie F.C. Fault detecting experiments for sequential circuits // Proceedings of the 5th Annual Symposium on Switching Circuit Theory and Logical Design. 1964. - P. 95-110.

52. Hartmams J., Steams R. Algebraic structure theory of sequential machines. Prentice-Hall, New York, 1966. - 210 p.

53. Евтушенко Н.В., ПетренкоА.Ф., Ветрова М.В. Недетерминированные автоматы: анализ и синтез. Часть 1. Отношения и операции. Томск: Изд-во Томского госуниверситета, 2006. - 142 с.

54. Ветрова М.В. Разработка алгоритмов синтеза и тестирования конечно-автоматных компенсаторов. ТГУ, Томск, диссертационная работа, 2004. -152с.

55. Спицына Н.В. Синтез тестов для проверки взаимодействия дискретных управляющих систем методами теории автоматов. ТГУ, Томск, диссертационная работа, 2005. 158с.

56. RoseM. Post Office Protocol Version 3. RFC 1460, June 1993. // http://www.faqs.org/rfcs/rfcl460.html.

57. J.A. Brzozowski, H. Jurgensen. A model for sequential machine testing and diagnosis // Journal of Electronic Testing: Theory and Applications. 1992, No. 2.-P. 219-234.

58. Евтушенко H.B., Петренко А.Ф. О проверяющих возможностях кратных экспериментов // Автоматика и Вычислительная техника. 1989, №3.-С. 9-14.

59. Luo G., Petrenko A., Bochman G.v. Selecting test sequences for partiallythspecified nondeterministic state machines // Proceedings of IFIP 6 International Workshop on Protocol Test Systems, 1995. P. 95-110.

60. R. Milner. A Calculus of Communicating Systems. Lecture Notes in Computer Science, vol. 92,1980.

61. Куфарева И.Б., Евтушенко H.B., Петренко А.Ф. Синтез проверяющих тестов для недетерминированного автомата относительно редукции // Автоматика и вычислительная техника. 1998, № 3. - С. 10-20.

62. Евтушенко Н.В., Лебедев А.В., Петренко А.Ф. О проверяющих экспериментах с недетерминированными автоматами // Автоматика и Вычислительная техника. 1991, № 6. - С. 81-85.

63. R. Alur, С. Courcoubetis, М. Yannakakis. Distinguishing tests for nondeterministic and probabilistic machines // Proceedings the 27th ACM Symposium on Theory of Computing, 1995. pp. 363-372.

64. Куфарева И.Б., Дорофеева М.Ю. Об оценке длины переборного теста для конечного автомата. Сборник научных трудов по материалам 7-й международной конференции «Теория и техника передачи, приема и обработки информации». Харьков, 2001. - С. 299-300.

65. Куфарева И.Б., Дорофеева М.Ю. Минимизация проверяющих тестов для конечных автоматов // Вестник ТГУ. Приложение. 2002. - № 1 (2). -С. 357-362.

66. I. Koufareva, М. Dorofeeva. A novel modification of W-method // Joint Bulletin of the Novosibirsk computing center and A.P. Ershov institute ofinformatics systems. Series: Computing science, issue: 18, 2002, NCC Publisher, Novosibirsk. P. 69-81.

67. Дорофеева М.Ю., Евтушенко H.B. Усовершенствование метода синтеза проверяющих тестов по мутационному автомату // Вестник ТГУ. Приложение. 2003. -№ 6. - С. 164-168.

68. М. Dorofeeva, Kh. El-Fakih, N. Yevtushenko. Incremental testing methods for implementations with more states than specifications // Вестник ТГУ. Приложение. 2004. - № 9(1). - С. 163-168.

69. Дорофеева М.Ю. Экспериментальное сравнение методов синтеза проверяющих тестов для детерминированных автоматов // Вестник ТГУ. Приложение. 2005. - №14. - С. 148-154.

70. М. Dorofeeva, Kh. El-Fakih, N. Yevtushenko. An improved conformance testing method // Lecture Notes in Computer Science No. 3731. P. 204-218.

71. Дорофеева М.Ю. Адаптация Н-метода для тестирования недетерминированных автоматов относительно редукции // Вестник ТГУ. Приложение. 2006. -№18. - С. 49-54.

72. Громов М.Л., Дорофеева М.Ю., Коломеец А.В. К синтезу тестов по мутационному автомату // Вестник ТГУ. Приложение. 2006. - №18. - С. 43-49.

73. М. Dorofeeva, A. Petrenko, М. Vetrova, N. Yevtushenko. Adaptive test generation from a nondeterministic FSM // Радиоэлектроника и информатика. 2004.-№3.-С. 91-95.