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

• Коломеец, Антон Владимирович
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Коломеец, Антон Владимирович

Введение.

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

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

1.2. Расширенные автоматы.

1.3. Построение эквивалентного конечного автомата.

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

1.4.1 Модели неисправности и тесты для конечных автоматов.

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

1.5. Обзор методов по синтезу тестов для расширенных автоматов.

1.6. Выводы по главе 1.

2. Модели неисправности на основе мутационного расширенного автомата.

2.1. Модель неисправности на основе мутационного расширенного автомата.

2.2. Ошибки в расширенном автомате.

2.2.1 Выходные неисправности.

2.2.2. Ошибки переходов.

2.2.3. Предикатные ошибки.

2.2.4. Ошибки присвоения.

2.3. Тестирование на основе мутационного автомата.

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

3. Синтез тестов для расширенного автомата на основе срезов.

3.1. Построение среза расширенного автомата с сохранением достижимости состояний.

3.2. Построение РБМ-среза расширенного автомата.

3.3. Построение различающего автомата для двух контекстно-свободных расширенных автоматов.

3.4. Алгоритм построения проверяющего теста для проверки ошибок переходов/выходов на выделенных переходах расширенного автомата.

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

3.6. Построение проверяющего теста на основе эквивалентного конечного автомата с ограничением на число состояний.

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

4. Соответствие между ошибками в программных реализациях и ошибками в расширенных автоматах.

4.1. Соответствие между программными ошибками и ошибками в расширенном автомате.

4.1.1. Тесты, построенные по расширенному автомату для проверки ошибок переходов.

4.1.2. Тесты, построенные по расширенному автомату для проверки ошибок выходов.

4.1.3. Тесты, построенные по расширенному автомату для проверки предикатных ошибок.

4.1.4. Тесты, построенные по расширенному автомату для проверки ошибок присвоения.

4.1.5. Более сложные ошибки.

4.2. Генерация программных реализаций на основе модели расширенного автомата.

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

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

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

Актуальность проблемы. Построение качественных проверяющих тестов для дискретных управляющих систем является актуальной технической задачей. Для построения проверяющего теста, с гарантированной полнотой необходимо иметь, в первую очередь, адекватную математическую модель протокола и ошибки (неисправности). Классические хорошо изученные модели, такие как конечный автомат [1], полуавтомат, входо-выходной полуавтомат [2] имеют слишком большое число состояний (и переходов), что затрудняет их использование для решения практических задач. Кроме того, эти модели описывают не все аспекты поведения протокола, в частности, не описывают ситуации, когда область определения некоторого параметра (например, временной переменной) бесконечна. Поэтому в настоящее время активно исследуется вопрос о построении тестов с гарантированной полнотой на основе более компактных моделей, таких как расширенный автомат [3], временной автомат. Модель расширенного автомата достаточно часто используется при описании технических систем, в частности, расширенный автомат достаточно просто построить по описанию технической системы в языке SDL [4] или If или UML [5]. Однако практически все известные методы синтеза тестов для расширенных и временных автоматов доставляют проверяющие тесты, полнота которых остается неизвестной. Синтез проверяющих тестов с гарантированной полнотой требует дополнительных исследований, которые в данной работе проводятся для модели расширенного автомата. Таким образом, разработка методов синтеза проверяющих тестов с гарантированной полнотой для расширенных автоматов является актуальной задачей.

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

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

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

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

2. Предложено понятие среза расширенного автомата. Предложены три среза расширенного автомата и алгоритм построения проверяющего теста с гарантированной полнотой на их основе.

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

Основные положения, выносимые на защиту.

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

2. Метод построения конечно- автоматного среза, расширенного автомата,,который имеет не больше состояний, чем исходный расширенный' автомат, и алгоритм построения по такому срезу проверяющего теста- с гарантированной полнотой.

3. Установленное- соответствие между программными ошибками некоторых классов' и ошибками, в расширенном автомате, эффективность использования которого при тестировании- программных реализаций, построенных на основе соответствующего расширенного автомата, подтверждается проведенными компьютерными экспериментами.

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

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

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

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

1. 6™ рамочная программа TAROT «Мобильность молодых ученых», 2003-2007 гг.

2. НИР «Разработка математических и программных средств обеспечения надежного и безопасного доступа к электронным ресурсам коллективного, пользования» (в рамках инновационного проекта ТГУ), 20062007 гг.

3. НИР «Проведение прикладных и проблемно-ориентированных поисковых исследований в области информационно-телекоммуникационных систем с участием научных организаций Франции (шифр заявки «2009-04-1.4-00-02-003»)», госконтракт №02.514.12.4002 от 09.06.2009.

Апробация работы. Все теоретические и практические результаты, составившие основу диссертационной работы, по мере их получения обсуждались на семинаре кафедры информационных технологий в исследовании дискретных структур радиофизического факультета ТГУ. Кроме того,1 результаты работы докладывались на научных конференциях: всероссийской конференции с международным участием «Новые информационные технологии в исследовании дискретных структур» (Томск, 2003 и 2008 гг., Иркутск, 2004 г., Шушенское, 2006 г.), международной научной студенческой конференции^ «Студент и научно - технический прогресс» (Новосибирск, 2004 и 2006 гг.), на международной конференции по тестированию программного обеспечения, ICST'2008, (Лиллехаммер, Норвегия, 2008 г.)

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

1. Коломеец A.B., Прокопенко С.А. Метод синтеза диагностических тестов для расширенных конечных автоматов // Вестник ТГУ. Приложение. -2003.-№6. -С. 174-177.

2. Коломеец A.B. Метод синтеза проверяющих тестов для расширенных конечных автоматов // Студент и научно - технический прогресс. Информационные технологии : материалы XLII международной научной студенческой конференции. - Новосибирск. - 2004. - С. 174-176.

3. Громов М.Л., Коломеец A.B., Евтушенко Н.В. Синтез диагностических тестов для автоматных сетей // Вестник ТГУ. Приложение. - 2004. - № 9 (I). - С. 204-209.

4. Коломеец A.B. Экспериментальное исследование диагностических тестов для локализации одиночных выходных ошибок и ошибок переходов в расширенных автоматах // Наука. Технологии. Инновации : материалы всероссийской научной конференции молодых ученых в 7 ч. Новосибирск : Изд-во НГТУ, 2006. - Ч. 1. - С. 238-240.

5. Коломеец A.B., Шабалдин A.B., Спицына Н.В. Автоматизация тестирования реализаций протоколов прикладного уровня в лабораторном практикуме // Современные средства и системы автоматизации : материалы IV научно-практической конференции. - Томск : Изд-во. ТУ СУР, 2003. - С. 222-225.

6. Коломеец A.B., Прокопенко С.А. Соответствие между ошибками в программных реализациях протоколов и расширенных автоматах // Вестник ТГУ. Приложение. - 2005. - № 14. - С. 154-157.

7. Коломеец A.B., Прокопенко С.А. Метод синтеза проверяющих тестов для расширенных автоматов без построения эквивалентного конечного автомата // Вестник ТГУ. Приложение. - 2006. - № 18. - С.62-66.

8. Михайлов Ю.В., Коломеец A.B. Автоматизация внесения ошибок в программные реализации протоколов на основе модели расширенного автомата // Наука. Технологии. Инновация : материалы всероссийской научной конференции молодых ученых в 7 ч. - Новосибирск : Изд-во НГТУ, 2006.-Ч. 1.- С. 49-51.

9: El-Fakih К., Kolomeez A., Prokopenko S., Yevtushenko N. Extended' Finite State Machine Based Test Derivation Driving» By User Defined Faults // International Conference ICST'20087 IEEE. - 2008. - P. 308-317.

10. Михайлов Ю.В., Коломеец A.B. Проверка переходов, в расширенном автомате на основе срезов // Вестник ТГУ. Управление, вычислительная техника и информатика. - 2008. - № 3 (4). - С. 140-118.

11. Громов МЛ1, Евтушенко Н.В., Коломеец. A.B. К синтезу условных тестов для недетерминированных автоматов; Программирование. - 2008. - № 6. - С. 1-111

121 Жигулин М.В., Коломеец А.В. Оценка полноты проверки при пассивном тестировании на основе автоматной модели // Известия ТПУ. - 2009. - Т. 314, № 5. - С. 225-2281

Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения и списка используемой литературы. Диссертация содержит 11 рисунков и 3 таблицы. Объем диссертации составляет 108 страницы, в том числе: титульный лист - одна страница, оглавление - две страницы, основной текст - 96 страниц, библиография из 88 наименований - 11 страниц, приложение - 2 Г страница.

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

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

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

Заключение

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

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

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

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

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

5. Установленно соответствие между программными ошибками некоторых классов и ошибками в расширенном автомате; проведенные компьютерные эксперименты показали, что такие программные ошибки могут быть обнаружены тестами, построенными на основе соответствующего расширенного автомата. Экспериментально показано, что тесты, построенные на основе расширенного автомата, обнаруживают 72 и более процентов ошибок в программных реализациях в зависимости от класса ошибки.

Отметим также, что результаты главы 3 можно расширить в различных направлениях. Например, в алгоритме 3.2 можно не выполнять Шаг 3 для увеличения возможностей при различении состояний. Однако в этом случае алгоритм построения проверяющего теста должен быть адаптирован к случаю, когда контекстно-свободный расширенный автомат имеет не только входные, но и выходные параметры.

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

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

1. Евтушенко, Н.В. Недетерминированные автоматы: анализ и синтез. 4.1.

2. Отношения и операции: Учебное пособие / Н.В. Евтушенко, А.Ф. Петренко, М.В. Ветрова // Томск: Томский государственный университет.- 2006.- 142 с.

3. Lynch, N. Hybrid I/O Automata / N. Lynch, R. Segala, F. Vaandrager, H. B.

4. Weinberg. // Hybrid Systems III. Eds. R. Alur et al. Lecture Notes in Computer Science 1066. Springer-Verlag. Berlin, Germany.- 1996.- Pp. 496-510.

5. El-Fakih, K. Fault diagnosis in extended finite state machines / K. El-Fakih, S.

6. Prokopenko, N. Yevtushenko, G. Bochmann, // In Proc. of the IFIP 15th International Conference on Testing of Communicating Systems (TestCom2003), France, Published as Lecture Notes in Computer Science 2644.- 2003.- Pp. 197-210.

7. Verilog. ObjectGEODE Simulator, Reference manual, 1997.

8. Horrocks, I. Constructing the user interface with statecharts / I. Horrocks //

9. Addison Wesley Longman Limited, Edinburg Gate, Harlow, Essex CM20 2JE, England and Associated Companies throughout the World.- 1999.- 272 p.

10. Ural, H. Test sequence selection based on static data flow analysis / H.Ural //

11. Computer communications, vol. 10, N 5.- 1987.- Pp. 234 242.

12. Chen, W.-H. Executable test sequences for the protocol data flow property / W.

13. H. Chen // Int. Conference on Formal Techniques for Networked and Distributed Systems (FORTE).- 2001.- Pp. 285-299.

14. Huang, C.-M. An executable protocol test sequence generation method for EFSM-specified protocols / Chung-Ming Huang, Yuan-Chuen Lin, Ming-Yule Yang // Intern Workshop on Ptotocol Test Systems, IWPTS'95.- 1995, Pp. 29-44.

15. Chen, W.-H. Test sequence generation from the protocol data portion based onthe selecting Chinese Postman algorithm / W.-H. Chen // Information Processing Letters, vol. 65.- 1998.- Pp. 261-268.

16. Chen, W.-H. Executable test sequence for the protocol control and data portions / W.-H. Chen // Proc. of IEEE Intern. Conf. on Communications, vol.1.- 2000.-Pp. 505-510.

17. Chen, W.-H. Automatic functional test generation using extended finite state machine model / W.-H. Chen // Proc. IEEE Design Automation Conference.-1993.-Pp. 86-91.

18. Ural, H. Test generation based on control and data dependencies within system specification in SDL / H.Ural, K.Saleh, and A.Williams // Computer Communications, vol. 23.- 2000.- Pp. 609-627.

19. Bozga, M. Using static analysis to improve automatic test derivation / M. Bozga, J.C1. Fernandez, L. Ghirvu // Software Tools and Technologie Transfer 4(2).- 2003.- Pp. 142-152.

20. Faro, A. Sequence Generation from EFSMs for Protocol Testing / A. Faro and A. Petrenko // COMNET'90.- 1990.- Pp. 17-26.

21. Wang, C.J. Generating test cases for EFSM with given fault models / C.J.Wang, M.T.Liu // Proc. IEEE INFOCOM, 1993, Pp. 774 781.

22. Cavalli, A. Hit-or-Jump: An< algorithm for embedded testing with applications to IN services / A. Cavalli, D. Lee,C. Rinderknecht, F. Zaidi // FORTE XII and PSTV XIX, China.- 1999.- Pp. 41-58.

23. El-Fakih, K. Extended Finite State Machine Based Test Derivation Driving By User Defined Faults / K. El-Fakih, A. Kolomeez, S. Prokopenko, N. Yevtushenko // International Conference ICST'2008.- 2008.- Pp. 308-317.

24. Bozga, M. Symbolic Verification for Communication Protocols / M. Bozga // PhD thesis, VERIMAG/IMAG.- 1999.- p. 137.

25. Korel, B. Slicing of state-based-models / B. Korel, I. Singh, L. Tahat, B. Vaysburg // Int. Conference on Software Maintenance.- 2003.- Pp. 34-43.

26. Weiser, M. Program slicing / M. Weiser // IEEE Trans, on Software Engineering, 10(4).- 1982.- Pp. 352-357.

27. Михайлов, Ю. В. Проверка переходов в расширенном автомате на основе срезов / Ю. В. Михайлов, А.В.Коломеец // Вестник ТГУ. Управление, вычислительная техника и информатика. 2008. - №3(4). - С. 110-118.

28. El-Fakih, К. Fault Diagnosis in Extended Finite State Machines / K. El-Fakih, S. Prokopenko, N. Yevtushenko, G. Bochmann // Lecture Notes in Computer Science, vol. 2644.- 2003,- Pp. 197-210.

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

30. Petrenko, A. Test suite generation for a FSM with a given type of implementation errors / A. Petrenko and N. Yevtushenko // In Proc. of the 12th Int. Workshop Protocol Specification, Testing and Verification.- 1992.- Pp. 229 243.

31. Bochmann, G. Protocol testing: review of methods and relevance for software testing / G. v. Bochmann, A. Petrenko // ISSTA, Seattle.- 1994.- Pp. 109-123.

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

33. Starke, P. Abstract Automata / P. Starke. // Amsterdam: North-Holland Publishing Company.- 1972.- 419 p.

34. Koufareva, I. Test generation driven by user-defined fault models / I. Koufareva, A. Petrenko, N. Yevtushenko // In Proc. of IFIP TC6 12th International Workshop on Testing of Communicating Systems, Hungary.-1999.- Pp. 215-223.

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

36. Chow, Т. S. Test design modeled by finite-state machines / T.S. Chow // IEEE Transactions on Software Engineering, 4(3).- 1978.- Pp. 178-187.

37. Fujiwara, S. Test selection based on finite state models / S. Fujiwara, G.v. Bochmann, F. Khendek, M. Amalou, A. Ghedamsi // IEEE Transactions on Software Engineering. 17(6).- 1991.- Pp. 591-603.

38. Gonenc, G. A method for the design of fault detection experiments / G. Gonenc // IEEE Trans. Computers, C-19(6).- 1970.- Pp. 551-558.

39. Hsieh, E. P. Checking experiments for sequential machines / E. P. Hsieh // IEEE Trans, on Computers, 20(10).- 1971.- Pp. 1152-1166.

40. Koufareva, I. A novel modification of W-method / I. Koufareva, R. Dorofeeva // Joint Bulletin of the Novosibirsk computing center and A.P. Ershov instituteof informatics systems. Series: Computing science, 18.- 2002.- Pp. 69-81.i

41. Lai, R. A survey of communication protocol testing / R. Lai // Journal of Systems and Software.- 2002.- Pp. 21-46.

42. Lee, D. Principles and methods of testing finite state machines-a survey / D. Lee, M. Yannakakis //Proceedings of the IEEE, 84(8).- 1996.- Pp. 1090-1123.

43. Yao, M. Fault coverage analysis in respect to an FSM specification / M. Yao, A. Petrenko, G. Bochmann // INFOCOM'94.- 1994.- Pp. 768-775.

44. Yvtushenko, N. V. Synthesis of test experiments in some classes of automata / N. V. Yvtushenko, A. F. Petrenko // Automatic Control and Computer Sciences.- 1990.- v.24, N.4.- Pp. 50-55.

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

46. Ural, H. On minimizing the lengths of checking experiments / H.Ural, X.Wu, F. Zhang // IEEE Trans, on Computers, 46(1).- 1997.- Pp. 93-99.

47. Спицына, H. Интернет программирование. Часть 1 / H. Спицына, А. Шабалдин // ТГУ, Томск.- 2002.- 30 с.

48. Petrenko, A. Fault models for testing in context / A. Petrenko, N. Yevtushenko,102

49. Sidhu, D. P. Formal methods for protocol testing: a detailed study / D. P. Sidhu and T. K. Leung // IEEE Trans, on Software Engineering, 1989.- 15(4).-Pp. 413-426.

50. Kwast, E. Automatic test generation for protocol data aspects / E.Kwast // Proc. of IFIP Intern. Symp. On Protocol Specification, Testing, and Verification.-1992.-Pp. 211-226.

51. Chanson, S.T: A unified approach to protocol test sequence generation / S.T.Chanson, J.Zhu//Proc. of INFOCOM.- 1993.- Pp. 106-114.

52. Dssouli, R. Test development for communication protocols: towards automation / R. Dssouli, K. Saleh, E. Aboulhamid, A. En-Nouaary, C. Bourfir // Computer Networks, vol. 31.- 1999.- Pp. 1835 1872.

53. ITU-T, Recommendation Z.lOO-Specification and Description Language (SDL), Geneva.- 1994.- Pp. 246.

54. Boroday, S. Techniques for Abstracting SDL Specifications / S. Boroday, R. Groz, A. Petrenko, Y.-M. Quemener // Proc. of the 3rd SAM (SDL and MSC) Workshop. LNCS, vol. 2599.- 2003,- Pp. 141-157.

55. ISO/IEC, Information processing systems, Estelle-A formal description technique based on extended state transition model, ISO 9074.- 1997.

56. Chun, W. Test case generation for protocols specified in ESTELLE / W. Chun, P. Amer // FORTE'90.- 1990.-Pp. 191-206.

57. Favreau, J.-P. Automatic generation of test scenario skeletons from protocolspecifications written in ESTELLE / J.-P. Favreau, R. J. Linn // Int. Workshop Protocol Specification, Testing and Verification (PSTV).- 1986.- Pp. 191-202.

58. Harel, D. The STATEMATE semantics of statecharts / D. Harel, A. Naamad // ACM Trans. Software Engineering and Methodolody.- 1996.- 5(4).-Pp. 293-333.

59. OMG, Unified Modelling Language, version 1.4, OMG Standard, Nov. 2002.

60. Bensalem, S. Property preserving Simulations / S. Bensalem, A. Bouajjani, C. Loiseaux, J. Sifakis // In 4th International Conference on Computer Aided Verification, volume 663 of Lecture Notes in Computer Science, SpringerVerlag:- 1992.-Pp. 11-44.

61. Lee, D. Passive testing and applications to network management / D. Lee, A.N: Netravali, K.K. Sabnani, B. Sugla, A. John // Proc. of ICNP.- 1997.-Pp. 98-114.

62. Жигулин, M.B. Оценка полноты проверки при пассивном тестировании на основе автоматной модели / М.В. Жигулин, А.В. Коломеец // Известия ТПУ, Т. 314. -№ 5.- 2009.- С. 225-228.

63. Cavalli, A. New approaches for passive testing using an Extended Finite State Machine specification / A. Cavalli, C. Gervy, S. Prokopenko // Journal of Information and Software Technology.-2003.- Pp. 837-852.

64. Коломеец, А. В. Метод синтеза диагностических тестов для расширенных конечных автоматов / А. В. Коломеец, С. А. Прокопенко // Вестник ТГУ. Приложение. 2003. - №6. - С. 174-177.

65. Громов, М. JI. Синтез диагностических тестов для автоматных сетей / М. JI. Громов, A.B. Коломеец, Н.В. Евтушенко // Вестник ТГУ. Приложение.- 2004. №9(1). с. 204-209.

66. Коломеец, A.B. Соответствие между ошибками в программных реализациях протоколов и расширенных автоматах / A.B. Коломеец, С.А. Прокопенко // Вестник ТГУ. Приложение. 2005. - №14. - С. 154 - 157.

67. El-Fakih, К. Extended Finite State Machine Based Test Derivation Driving By User Defined Faults / K. El-Fakih, A. Kolomeez, S. Prokopenko, N. Yevtushenko // International Conference ICST'2008. 2008. - Pp. 308-317.

68. Громов, M. JI. К синтезу условных тестов для недетерминированных автоматов / М. JL Громов, Н.В. Евтушенко, A.B. Коломеец // Программирование. 2008. - №6. - С. 1-11.

69. Куфарева, И. Б. Применение недетерминированных автоматов в задачах синтеза проверяющих тестов для систем логического управления: диссертация на соискание степени к-та. тех. наук: 05.13.01.- Томск: ТГУ,1052000.- 176 с.

70. Hierons, R. M. Mutation testing from probabilistic and stochastic finite state machines / R. M. Hierons, M. G. Merayo // Journal of Systems and Software. 82(11).- 2009.- Pp. 1804-1818.

71. Jia, Y. An analysis and survey of the development of mutation testing / Y. Jia, M. Harman // Crest Center, King's College, Londin. Technical Report TR-09-06.- 2006.-Pp. 1-31.

72. Громов, M.JI. К синтезу тестов по мутационному автомату / М.Л.Громов,

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

74. Пархоменко, П.П. Основы технической диагностики / П.П. Пархоменко,

75. B.В. Карибский, Е.С. Согомонян, В.Ф. Халчев // М.: Энергия.- 1976.476 с.

76. Коломеец, А.В. Соответствие между ошибками в программных реализациях протоколов и расширенных автоматах / А.В. Коломеец, С.А. Прокопенко // Вестник ТГУ. Приложение. 2005, №14, С. 154 - 157.

77. Massacci, F. Logical Cryptoanalisys as a SAT Problem: the Encoding of the Data Encryption Standart / F. Massacci, L. Marraro // Dipartimento di Imformatica e Sistemistica. Universita di Roma «La Sapienza».- 1999.- Pp. 165 - 203.

78. Lantao, Z. Validation SAT solvers using an independent resolution-based checker: partical impementations and other applications / Z. Lantao, M. Sharad // Proceedings of Design, Automation and Test in Europe(DATE2003).- 2003.-Pp. 116-122.

79. Солодовников, А. С. Системы линейных неравенств / A.C. Солодовников //M.: Наука.- 1977.- 112 с.

80. Petrenko, A. Testing from Partial Deterministic FSM Specifications / A. Petrenko, N. Yevtushenko // IEEE Trans. Computers 54(9).- 2005.- Pp. 11541165.

81. Дорофеева, М. Ю. Исследование и разработка конечно-автоматных методов синтеза проверяющих тестов для управляющих систем: дис. . канд. техн. наук / М. Ю. Дорофеева; Томский гос. ун-т. Томск, 2007. -150 с.

82. Михайлов, Ю. В. Проверка переходов в расширенном автомате на основе срезов / Ю. В. Михайлов, А.В. Коломеец // Вестник ТГУ. Управление, вычислительная техника и информатика.-2008.- №3(4).- С. 110-118.

83. Жигулин, М.В. Оценка полноты проверки при пассивном тестировании на основе автоматной модели / М. В. Жигулин, А. В. Коломеец // Известия ТПУ.- 2009.- Т. 314.- № 5.- С. 225-228.