Исследование и разработка конечно-автоматных методов синтеза проверяющих тестов для управляющих систем
Диссертация
В данной главе предложен метод построения проверяющего теста относительно мутационного автомата в случае, когда число состояний мутационного автомата может превышать число состояний эталонного автомата. В предложенном методе используется известная информация о детерминированных переходах в мутационном автомате, за счет этого исчезает экспоненциальная зависимость длины проверяющего теста… Читать ещё >
Список литературы
- Мур Э. Ф. Умозрительные эксперименты с последовательными машинами // Автоматы. — М.: Изд-во иностр. лит., 1956. — С. 179−210.
- Гилл А. Введение в теорию конечных автоматов. М.: Наука, 1966−272с.
- Богомолов A.M., Грунский И. С., Сперанский Д. В. Контроль и преобразования дискретных автоматов. Киев: Наук. Думка, 1975. — 176с.
- Сперанский Д.В., Боголюбов A.M. Контроль и преобразование дискретных автоматов. Киев, 1975.
- Богомолов A.M., Сперанский Д. В. Аналитические методы в задачах контроля и анализа дискретных устройств. Саратов: Изд-во Сарат. ун-та, 1986.-240с.
- Грунский И.С., Козловский В. А., Пономаренко Г. Г. Представление конечных автоматов фрагментами поведения. Киев: Наук. Думка, 1990. -232с.
- Грунский И.С., Петренко А. Ф. Построение проверяющих экспериментов с автоматами, описывающими протоколы // Автоматика и вычислительная техника. 1988, № 4. — С. 7−14.
- Петренко А.Ф. Эксперименты над протокольными объектами // Автоматика и вычислительная техника. 1987, № 1. — С. 16−21.
- 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.
- G. v. Bochmann, C. A. Sunshine. Formal methods in communication protocol design // IEEE Trans, on Comm., Vol 28,1980. P. 624−631.
- 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.
- Бурдонов И. Б., Косачев А. С., Кулямин В. В. Использование конечных автоматов для тестирования программ // Программирование. -2000, № 2.-С. 12−28.
- Василевский М.П. О распознавании неисправности автоматов // Кибернетика. 1973, № 4. — С. 93−108.
- T.S. Chow. Test software design modeled by finite state machine // IEEE Transactions. 1978, SE-4, No.3. — P. 178−187.
- G. Gonenc. A method for the design of fault detection experiments // IEEE Trans. Computers. 1970, vol. C-19. No. 6. — P. 551−558.
- Sabnani K., Dahbura A. A protocol test generation procedure // Computer Networks and ISDN Systems. 1988, vol. 15, No. 4. — P. 285−297.
- 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.
- Евтушенко H.B., Петренко А. Ф. Метод построения эксперимента для произвольного детерминированного автомата // Автоматика и вычислительная техника. 1990, № 5. — С. 73−76.
- 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.
- 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.
- 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.
- D. Lee, M. Yannakakis. Testing FSMs: state identification and verification // IEEE Transactions on Computers. 1994, vol. 43, № 3. — P. 306−320.
- 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.
- 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.
- Куфарева И. Б. Применение недетерминированных автоматов в задачах синтеза проверяющих тестов в системах логического проектирования. ТГУ, Томск, диссертационная работа, 2000.
- К. 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.
- Евтушенко H.B., Петренко А. Ф., Тренькаев B.H. Метод тестирования автоматных сетей, основанный на тестируемом поведении компоненты // Автоматика и вычислительная техника. 1996, № 2. — С. 48−59.
- Евтушенко Н.В., Тренькаев В. Н. Методы синтеза проверяющих тестов для компоненты автоматной сети //Новые информационные технологии в исследовании дискретных структур. Доклады второй всероссийской конференции. Екатеринбург, 1998. — С. 219−223.
- Пархоменко П.П. Основы технической диагностики. М.: Энергия, 1976.-464 с.
- Матросова А. Ю. Алгоритмические методы синтеза тестов. Томск: Изд-во Томского госуниверситета, 1990. — 207 с.
- A. Petrenko, N. Yevtushenko, G.v. Bochmann. Testing Deterministic Implementations from Nondeterministic FSM Specifications // Proceedings of
- IP TC6 9th International Workshop on Testing Of Communicating Sytems. -Germany, 1996.-P. 125−140.
- P.H. Starke. Abstract Automata. North-Holland: American Elsevier, 1972. -419p.
- Лукьянов Б.Д. О различающих и контрольных экспериментах с недетерминированными автоматами // Кибернетика и системный анализ. -1995, № 5.-С. 69−76.
- Лукьянов Б.Д. Детерминированные реализации недетерминированных автоматов // Кибернетика и системный анализ. 1996, № 4. — С. 34−50.
- 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.
- T. Kim, T. Villa, R. Brayton, A. Sangiovanni-Vincentelli. Synthesis of FSMs: functional optimization. Kluwer Academic Publishers, 1997.
- B. Yang, H. Ural. Protocol conformance test generation using multiple UIO sequences with overlapping // Computer Communication Review. 1990, No. 4. -P. 118−125.
- 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.
- 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.
- 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.
- Gerard J. Holzmann. Design and validation of computer protocols // Prentice-Hall, Englewood Cliffs. 1991.
- 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.
- 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.
- 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.
- 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.
- ITU-T Recommendation V.76, «Generic multiplexer using V.42 LAPM-based procedures». 1996, Series V: Data communication over the telephone network.
- ITU-T Recommendation V.42, «Error-Correcting Procedures for DCEs Using Asynchronous-to Synchronous Conversion». 2002, AAP29−03/02.
- A. Petrenko, N. Yevtushenko. Testing from partial deterministic FSM specifications // IEEE Transactions on Computers. 2005, 54(9). — P. 1154−1165.
- Евтушенко H.B., Петренко А. Ф. Синтез проверяющих экспериментов в некоторых классах автоматов // Автоматика и Вычислительная техника. -1990,№ 4.-С. 59−64.
- 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.
- Hartmams J., Steams R. Algebraic structure theory of sequential machines. Prentice-Hall, New York, 1966. — 210 p.
- Евтушенко Н.В., ПетренкоА.Ф., Ветрова М. В. Недетерминированные автоматы: анализ и синтез. Часть 1. Отношения и операции. Томск: Изд-во Томского госуниверситета, 2006. — 142 с.
- Ветрова М.В. Разработка алгоритмов синтеза и тестирования конечно-автоматных компенсаторов. ТГУ, Томск, диссертационная работа, 2004. -152с.
- Спицына Н.В. Синтез тестов для проверки взаимодействия дискретных управляющих систем методами теории автоматов. ТГУ, Томск, диссертационная работа, 2005. 158с.
- RoseM. Post Office Protocol Version 3. RFC 1460, June 1993. // http://www.faqs.org/rfcs/rfcl460.html.
- 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.
- Евтушенко H.B., Петренко А. Ф. О проверяющих возможностях кратных экспериментов // Автоматика и Вычислительная техника. 1989, № 3.-С. 9−14.
- 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.
- R. Milner. A Calculus of Communicating Systems. Lecture Notes in Computer Science, vol. 92,1980.
- Куфарева И.Б., Евтушенко H.B., Петренко А. Ф. Синтез проверяющих тестов для недетерминированного автомата относительно редукции // Автоматика и вычислительная техника. 1998, № 3. — С. 10−20.
- Евтушенко Н.В., Лебедев А. В., Петренко А. Ф. О проверяющих экспериментах с недетерминированными автоматами // Автоматика и Вычислительная техника. 1991, № 6. — С. 81−85.
- R. Alur, С. Courcoubetis, М. Yannakakis. Distinguishing tests for nondeterministic and probabilistic machines // Proceedings the 27th ACM Symposium on Theory of Computing, 1995. pp. 363−372.
- Куфарева И.Б., Дорофеева М. Ю. Об оценке длины переборного теста для конечного автомата. Сборник научных трудов по материалам 7-й международной конференции «Теория и техника передачи, приема и обработки информации». Харьков, 2001. — С. 299−300.
- Куфарева И.Б., Дорофеева М. Ю. Минимизация проверяющих тестов для конечных автоматов // Вестник ТГУ. Приложение. 2002. — № 1 (2). -С. 357−362.
- 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.
- Дорофеева М.Ю., Евтушенко H.B. Усовершенствование метода синтеза проверяющих тестов по мутационному автомату // Вестник ТГУ. Приложение. 2003. -№ 6. — С. 164−168.
- М. Dorofeeva, Kh. El-Fakih, N. Yevtushenko. Incremental testing methods for implementations with more states than specifications // Вестник ТГУ. Приложение. 2004. — № 9(1). — С. 163−168.
- Дорофеева М.Ю. Экспериментальное сравнение методов синтеза проверяющих тестов для детерминированных автоматов // Вестник ТГУ. Приложение. 2005. — № 14. — С. 148−154.
- М. Dorofeeva, Kh. El-Fakih, N. Yevtushenko. An improved conformance testing method // Lecture Notes in Computer Science No. 3731. P. 204−218.
- Дорофеева М.Ю. Адаптация Н-метода для тестирования недетерминированных автоматов относительно редукции // Вестник ТГУ. Приложение. 2006. -№ 18. — С. 49−54.
- Громов М.Л., Дорофеева М. Ю., Коломеец А. В. К синтезу тестов по мутационному автомату // Вестник ТГУ. Приложение. 2006. — № 18. — С. 43−49.
- М. Dorofeeva, A. Petrenko, М. Vetrova, N. Yevtushenko. Adaptive test generation from a nondeterministic FSM // Радиоэлектроника и информатика. 2004.-№ 3.-С. 91−95.