Синтез тестов для проверки взаимодействия дискретных управляющих систем методами теории автоматов тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Спицына, Наталия Владимировна

• Спицына, Наталия Владимировна
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Спицына, Наталия Владимировна

ВВЕДЕНИЕ.

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

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

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

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

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

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

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ХЛ2.

4.2. Синтез тестов для композиции А1 0®Л2.

4.2.1. Полный проверяющий тест при использовании мутационного автомата

4.2.2. Модель неисправности при тестировании композиции А \ 0®А2.

4.2.3. Алгоритм построения полного проверяющего теста.

4.2.4. Построение тестов для компонент сети на основе решения автоматных уравнений.

4.3. Синтез тестов для удаленной компоненты.

4.3.1. Построение тестов для композиций А1 А2 (Л1 0*2-<42).

4.3.2. Исследование отношения неразделимости.

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

5. ТЕСТИРОВАНИЕ ПРОГРАММНЫХ РЕАЛИЗАЦИЙ ПРОТОКОЛОВ В ЛАБОРАТОРНОМ ПРАКТИКУМЕ.

5.1. Краткое описание предлагаемых лабораторных работ.

5.2. Ошибки, типичные при реализации любого протокола прикладного уровня.

5.3. Возможные ошибки при реализации конкретного протокола прикладного уровня.

5.3.1. Возможные ошибки при реализации протокола РОРЗ.

5.3.2. Возможные ошибки при реализации протокола SMTP.

5.3.3. Возможные ошибки при реализации протокола TFTP.

5.3.4. Возможные ошибки при реализации протокола TIME.

5.3.5. Возможные ошибки при реализации протокола HTTP.

5.4. Автоматизация тестирования студенческих реализаций протоколов

5.4.1. Постановка задачи автоматизации тестирования.

5.4.2. Архитектура тестера.

5.4.3. Пример тестирования РОРЗ-сервера.

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

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

Общая характеристика Актуальность проблемы. Под дискретной системой в работе понимается система, поведение которой описывается последовательностями действий в некотором алфавите. Поведение управляющих дискретных систем описывается при помощи формальных языков, а также таких моделей, как полуавтоматы (источники), сети Петри, автоматы и т. д. [1-11]. Примерами взаимодействующих дискретных систем являются интегральные схемы [5], аппаратные и программные реализации сетевых протоколов [8, 11], мультиагентные системы [13]. При этом системы могут быть соединены между собой различными способами, и режимы их совместного функционирования также могут быть различными. Совместная работа дискретных систем проверяется путем подачи на вход системы проверяющих тестов - последовательностей входных воздействий, и наблюдения выходных реакций системы с последующим их анализом [1, 3, 6]. Моделью дискретной системы, относительно которой достаточно хорошо развиты методы построения проверяющих тестов, является модель с конечным числом переходов, которая в русскоязычной литературе называется конечным автоматом. Тестирование дискретных управляющих систем автоматными методами активно развивалось в работах Г. Бокмана, М.П. Василевского, И.С. Грунского, Н.В. Евтушенко, А. Кавалли, М. Кима, В.В. Кулямина, Д. Ли, Б.Д. Лукьянова, А.Ю. Матросовой, А.Ф. Петренко, М. Янакакиса и других авторов.

Взаимодействующие дискретные управляющие системы могут быть соединены между собой различными способами, и режимы их совместного функционирования также могут быть разными. Методы построения тестов существенно зависят от режима взаимодействия дискретных систем. Известных формальных операций композиции автоматов [2, 40-42], вообще говоря, недостаточно для описания реальных систем, например, для описания поведения дискретных систем при кратном стимулировании, когда входные сигналы могут поступать на компоненты композиции как одновременно, так и поочередно [36]. Поэтому актуальной остается задача обобщения известных операций композиции для более сложных случаев.

Большинство публикаций по тестированию взаимодействующих конечных автоматов посвящено синтезу тестов для проверки функционирования некоторых видов автоматных композиций, особенно для бинарной параллельной или синхронной композиции [15, 17-20, 22, 63]. Авторы предполагают, что взаимодействующие автоматы согласованы, т. е. предполагается соответствие внешних алфавитов взаимодействующих систем, отсутствие несовместимостей при задании их параметров, отсутствие осцилляций при совместной работе и т. п. [15]. Однако, такое предположение не соответствует действительности, т. к. проверка на тупики и осцилляции на этапе валидации [21], т. е. на этапе проверки корректности спецификации, например, таких дискретных управляющих систем, как протоколы, не всегда гарантирует, что при взаимодействии реализаций этих систем от разных производителей осцилляций не возникнет. Поэтому в последнее время появились работы [16], в которых предлагаются методы синтеза тестов только для проверки, могут ли системы функционировать совместно. Тестьг для двух этапов строятся независимо друг от друга, т. к. неизвестна связь между этими тестами. В известных нам работах тесты для проверки совместимости систем строятся эвристически без математической модели [15-20]. Таким образом, актуальной является задача разработки технологии тестирования взаимодействующих автоматов, включающей в себя тестирование на возможность совместного функционирования, для более сложных режимов совместного функционирования, в частности для режима кратного стимулирования.

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

Для достижения поставленной цели решаются следующие задачи.

1. Обобщение известных операций композиции для описания взаимодействия дискретных систем в режиме кратного стимулирования, и исследование свойств такой композиции.

2. Разработка модели неисправности и метода синтеза полных проверяющих тестов для проверки дискретных систем на совместимость (отсутствие осцилля-ций при взаимодействии).

3. Исследование применимости известных методов построения проверяющих тестов для проверки взаимодействующих дискретных систем на соответствие спецификации при кратном стимулировании, и разработка новых методов для случаев, когда известные методы не применимы.

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

Йаучная новизна работы состоит в следующем: 1) Введена обобщенная операция композиции дискретных систем, которая позволяет формально описать взаимодействие дискретных систем, в том числе в режиме кратного стимулирования. На основе введенной формулы предложена формула для нахождения максимально допустимого поведения неизвестной компоненты дискретной системы, если известен язык композиции и известны языки остальных компонент. Показано, что с применением предложенной формулы может быть построена бинарная композиция автоматов при кратном стимулировании, а также параллельная и синхронная композиции автоматов для произвольного количества компонент и структуры композиции. Введенная формула для нахождения максимально допустимого поведения адаптирована для нахождения максимально допустимого поведения компоненты автоматной композиции.

2) Введена модель неисправности и предложен метод построения полных проверяющих тестов для проверки дискретных управляющих систем на совместимость (отсутствие осцилляций при взаимодействии).

3) Предложены алгоритмы построения полных проверяющих тестов для проверки автоматной композиции с кратным стимулированием на соответствие спецификации при различных условиях доступа к каналам композиции.

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

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

Реализация полученных результатов. Исследования, результаты которых изложены в диссертации, проводились в рамках работ по программе «Университеты России» (2002-2003 г.), НИР «Алгебра конечных автоматов и полуавтоматов: отношения, операции, решение уравнений», а также в рамках международного проекта по исследованию и обучению методам тестирования TAROT (Training and Research on Testing, с 2004 г.) и по программе МОН РФ «Развитие научного потенциала высшей школы» (2005 г.), НИР «Разработка методологии тестирования совместного функционирования телекоммуникационных протоколов на основе теории автоматов». Кроме того, результаты исследований по тестированию сетевых протоколов нашли применение при выполнении НИР «Лабораторные работы по курсу «Интернет-программирование» при поддержке

ИДО ТГУ в рамках программы информатизации ТГУ. Разработанная система автоматизированного тестирования студенческих реализаций протоколов прикладного уровня внедрена в учебный процесс на радиофизическом факультете ТГУ.

Документы, подтверждающие участие автора в работе по грантам, можно найти в приложении к настоящей диссертации.

Апробация работы. Научные результаты [67-79], составившие основу данной работы, обсуждались на заседаниях объединенного семинара кафедры информационных технологий в исследовании дискретных структур радиофизического факультета, кафедры защиты информации и криптографии и кафедры программирования факультета прикладной математики и кибернетики ТГУ. Кроме того, они докладывались на конференциях различного уровня, в том числе международных, в гг. Саратове, Берлине, Оксфорде, Москве и Томске, что подтверждается соответствующими публикациями докладов и тезисов докладов [67, 68, 70, 71, 73, 74, 76, 77, 79].

Структура и объем диссертации. Диссертация состоит из введения, 5 глав, заключения и списка используемой литературы. Объем диссертации составляет 158 страниц текста, набранного в редакторе Microsoft Word 2000 (Шрифт -Times New Roman, размер шрифта - 14 pt, межстрочный интервал - 1,5 строки), в том числе: титульный лист - 1 стр., оглавление - 3 стр., основной текст, включающий 53 рисунка и 3 таблицы, - 141 стр., библиография из 79 наименований - 8 стр., приложение - 5 стр. Основное содержание работы

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

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

В данной главе рассматривается задача тестирования реализаций протоколов в лабораторном практикуме. Вводится классификация наиболее вероятных ошибок, которые могут быть свойственны либо реализации только данного протокола, либо реализации любого протокола прикладного уровня, предлагаются тестовые последовательности, гарантирующие обнаружение и/или локализацию таких ошибок, а также описывается подход к автоматизации процесса тестирования студенческих реализаций протокола, который был реализован при выполнении проекта «Лабораторные работы по курсу Интернет-программирование» при поддержке ИДО ТГУ в рамках программы информатизации ТГУ.

Заключение

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

Введена модель неисправности и предложен метод построения полных проверяющих тестов для проверки композиций автоматов на осцилляции. Показано, что при удаленном тестировании (отсутствии доступа к входу и выходу одной из компонент) единственным отношением конформности, проверку которого можно гарантировать, является отношение неразделимости между недетерминированными автоматами, при этом синтез полного проверяющего теста относительно неразделимости нельзя свести к синтезу теста относительно известных отношений эквивалентности и редукции. Предложен алгоритм построения полного проверяющего теста относительно неразделимости при явном перечислении проверяемых автоматов.

На защиту выносятся:

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

2. Модель неисправности для проверки композиции автоматов на отсутствие осцилляций, и метод построения полных проверяющих тестов относительно этой модели.

3. Алгоритмы синтеза полных проверяющих тестов для композиции конечных автоматов с кратным стимулированием при различных условиях доступа к каналам композиции.

4. Алгоритм синтеза полных проверяющих тестов для недетерминированных автоматов относительно неразделимости, который может быть использован при удаленном тестировании.

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

Список литературы диссертационного исследования кандидат технических наук Спицына, Наталия Владимировна, 2005 год

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

2. Глушков В. М. Синтез цифровых автоматов. М: Физматгиз,1962. - 476 с.

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

4. Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы (поведение и синтез). М.: Наука, 1970. - 400 с.

5. Агибалов Г. П., ОрановА. М. Лекции по теории конечных автоматов. — Томск: Изд-во Томского госуниверситета, 1984. 184 с.

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

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

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

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

10. Hartmanis J., Stearns R. Algebraic Structure Theory of Sequential Machines. — Printice-Hall, New-York, 1966. 210 p.

11. Карпов Ю. Г. Теория автоматов. СПб.: Питер, 2003. - 208 с.

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

13. A. Haddadi. Communication and Cooperation in Agent Systems: A Pragmatic Theory // Lecture Notes in Computer Science, 1056, Springer-Verlag, 1996.

14. Wonham W. M. Supervision of DES // www.control.utoronto.ca/des, 1999. 324 P

15. C. Viho, S. Barbin, L. Tanguy. Towards a formal framework for interoperability testing // Proceedings of the 21st Inter. Conf. FORTE 2001, Korea. P. 51-68.

16. Yannakakis M., Lee D. Testing finite state machines // AT&T Bell Labs, internal memorandum, 1990.

17. N. Griffeth, R. Hao, D. Lee, R. Sinha. Interoperability testing of VoIP Systems // Proceedings of the Global Telecommunications Conference, 2000, GLOBECOM'OO, IEEE, Vol.3. P. 1565-1570.

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

19. 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.

20. Cavalli A., Lee D., Rinderknecht C., Zaidi F. Hit-or-jump: an algorithm for embedded testing with application to IN services // Proceedings of the IFIP Joint Inter. Conf. FORTE/PSVT, 1999. P. 41-56.

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

22. J. Farrell. IP Fragmentation Attacks on Checkpoint Firewalls // http://www.sans.org/rr/firewall/fragattacks.php, 2001.

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

24. Т. S. Chow. Test design modeled by finite-state machines I I IEEE Trans. SE, vol. 4, no. 3, 1978.-P. 178-187.

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

26. A. Petrenko, N. Yevtushenko, A. Lebedev, and A. Das. Nondeterministic state machines in protocol conformance testing // Proc. of the IFIP 6th IWPTS, France, 1993.-P. 363-378.

27. N. Yevtushenko, A. Petrenko. Test derivation method for an arbitrary deterministic automaton // Automatic Control and Computer Sciences, Allerton Press Inc., USA, no. 5,1990.

28. F. C. Hennie. Fault detecting experiments for sequential circuits // Proc. of 5th Annual Symposium on Switching Circuit Theory and Logical Design, Princeton, 1964. — P. 95-110.

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

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

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

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

33. A. Petrenko, N. Yevtushenko, G. V. Bochmann. Testing deterministic implementations from their nondeterministic specifications // Proceedings of the IFIP Ninth International Workshop on Testing of Communication Systems, Germany, 1996. P. 125-140.

34. Куфарева И. Б. Применение недетерминированных автоматов в задачах синтеза проверяющих тестов для систем логического управления: Диссертация на соискания ученой степени канд. технических наук. — Томск, 2000. — 176 с.

35. Seol S., Kim М., Chanson S. Т. Interoperability Test Generation for Communication Protocols based on Multiple Stimuli Principle // Proceedings of the IFIP 14th Inter. Conf. TestCom2002. P. 151-169.

36. P. Starke. Abstract automata, North-Holland / American Elsevier, 1972. 419 p.

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

38. Евтушенко H. В., Куфарева И. Б. Отношения между недетерминированными автоматами. Томск: Изд-во Института оптики атмосферы СО РАН, 2001. -26 с.

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

40. H. Евтушенко, Т. Вилла, А.Петренко, Р.Брайтон, А. Санджованни- ' Винцентелли. Решение уравнений в логическом синтезе // Препринт, Томск: Изд-во «Спектр», 1999. 27 с.

41. Yevtushenko N., Villa Т., Brayton R., Petrenko A., Sangiovani-Vincentelli A. Solution of synchronous language equations for logic synthesis // Вестник ТГУ. Приложение. 2002. № 1(11). С. 132-137.

42. P. Merlin and G. Bochmann. On the construction of submodule specifications and communication protocols // ACM Transactions on Programming Language and Systems, 5(1): 1-25, January 1983.

43. H. Qin, P. Lewis. Factorisation of Finite State Machines under strong and observational equivalences // Formal Aspects of Computing, 3:284-307, Jul.-Sept. 1991.

44. A. Petrenko, N. Yevtushenko. Solving asuynchronous equations. // Formal desrip-tion techniques/Protocol specification, testing and verification. Kluwer Academic Publishers, 1998.-P. 125-140.

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

46. N. Yevtushenko, T. Villa, R. Brayton, A. Petrenko, A. Sangiovanni-Vincentelli. Sequential Synthesis by Language Equation Solving // Technical report, 2003.

47. S. Hassoun, T. Villa. Optimization of synchronous circuits. // In R. Brayton, S. Hassoun, andT. Sasao, editors, Logic Synthesis and Verification, 2001. P. 225-253.

48. С. H. West. An automated technique of communication protocols validation // IEEE Trans. Comm., 26 (1978) 1271-1275.

49. D. Brand and P. Zafiropulo. On communicating finite state machines // J. ACM 30(2), (1983) 323-342.

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

51. Cavalli A., Prokopenko S., Yevtushenko N. Fault detection power of a widely used test suite for a system of communicating FSMs // Proceedings of the IFIP 13th Inter. Conf. TestCom2000. P. 35-59.

52. S. Naito, M. Tsunoyama. Fault detection for sequential machines by transition tours // Proceedings of Fault Tolerant Comp, Syst., 1981. P.23 8-243.

53. Watanabe Y., Brayton R. K. The maximum set of permissible behaviors for FSMS network // Trans. Of IEEE / ACM Int. Conf. On Compute-aided design, 1993. -P. 316-328.

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

55. К. El-Fakih, N. Yevtushenko. Fault Propagation by Equation Solving // Proceedings of the 24th IFIP WG 6.1. Inter. Confer. Formal Techniques For Networked and Distributed Systems, FORTE 2004. P. 185-198.

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

57. Hopcroft J. E., UlmanJ. D. Introduction to automata theory, Languages and Computation // Addison-Wesley Publishing Company, 1979.

58. Буфалов С. А. Исследование живых и безопасных решений параллельных уравнений и неравенств на множестве полуавтоматов и автоматов: Диссертация на соискание ученой степени кандидата тех. наук, 2002.

59. 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-233.

60. Евтушенко H. В., Тренькаев В. H. Методы синтеза тестов для цифровых автоматов: Учебно-методическое пособие. Томск: Изд-во ТГУ, 1997. - 34 с.

61. Тренькаев В. Н. Разработка методов синтеза проверяющих тестов для сетей из конечных автоматов: Диссертация на соискание ученой степени кандидата тех. наук, 2000. 188 с.

62. К. El-Fakih, N. Yevtushenko and G. Bochmann. Protocol re-testing methods // Proc. of the IFIP 14th International Conference on Testing of Communicating Systems, 2002.

63. K. El-Fakih, N. Yevtushenko, and G. v. Bochmann. FSM-based incremental conformance testing methods // IEEE Transactions on software engineering, 2004, v.20, N7.-P. 425-436.

64. Дорофеева М. Ю., ЕвтушенкоН. В. Усовершенствование метода синтеза проверяющих тестов по мутационному автомату // Вестник ТГУ. Приложение. Серия «Математика. Кибернетика. Информатика». 2003. № 6. С. 164—169.

65. Евтушенко Н. В., СпицынаН. В. Синтез полуавтоматов посредством решения логических уравнений // Материалы международной конференции, посвященной памяти профессора A.M. Богомолова. Саратов, 2002. - С.26.

66. Спицына Н. В., Евтушенко Н. В., Петренко А. Ф. Решение уравнений в алгебре полуавтоматов для операции обобщенной композиции // Вестник ТГУ. Приложение. 2002. № 1(11). С. 265-270.

67. СпицынаН. В., ШабалдинА. В. Интернет-программирование. Лабораторные работы. Часть 1: Методическое пособие. — Томск: Издательство ТГУ, 2002. 50 с.

68. СпицынаН. В. Этапы тестирования на взаимодействие // Материалы Международной конференции «Современные проблемы физики и высокие технологии». Томск: Издательство НТЛ, 2003. - С. 500-502.

69. Спицына Н. В., Тренькаев В. Н. К синтезу тестов для композиции конечных автоматов // Вестник ТГУ. Приложение. Серия «Математика. Кибернетика. Информатика». 2003. № 6. С. 183-187.

70. N. Spitsyna, V. Trenkaev. FSM Based Interoperability Testing of Communication Protocols // Proceedings of the IEEE-Siberian Conference on Control and Communications, SIBCON-2003, P. 20-23.

71. К. El-Fakih, V. Trenkaev, N. Spitsyna, N. Yevtushenko. FSM Based Interoperability Testing Methods // In Proc. of the IFIP 16th International Conference on Testing of Communicating Systems, Oxford, U.K., 2004, Published as LNCS 2978, P. 60-75.