Синтез тестов для проверки взаимодействия дискретных управляющих систем методами теории автоматов
Диссертация
Реализация полученных результатов. Исследования, результаты которых изложены в диссертации, проводились в рамках работ по программе «Университеты России» (2002;2003 г.), НИР «Алгебра конечных автоматов и полуавтоматов: отношения, операции, решение уравнений», а также в рамках международного проекта по исследованию и обучению методам тестирования TAROT (Training and Research on Testing, с 2004 г… Читать ещё >
Список литературы
- Мур Э. Ф. Умозрительные эксперименты с последовательными машинами // Автоматы. -М.: Изд-во иностр. лит., 1956. С. 179−210.
- Глушков В. М. Синтез цифровых автоматов. М: Физматгиз, 1962. — 476 с.
- Гилл А. Введение в теорию конечных автоматов. М: Наука, 1966. — 272 с.
- Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы (поведение и синтез). М.: Наука, 1970. — 400 с.
- Агибалов Г. П., ОрановА. М. Лекции по теории конечных автоматов. — Томск: Изд-во Томского госуниверситета, 1984. 184 с.
- Богомолов А. М., Грунский И. С., Сперанский Д. В. Контроль и преобразования дискретных автоматов. Киев: Наук, думка, 1975. — 176 с.
- Матросова А. Ю. Алгоритмические методы синтеза тестов. Томск: Изд-во Томского госуниверситета, 1990. — 207 с.
- Грунский И. С., Петренко А. Ф. Построение проверяющих экспериментов с автоматами, описывающими протоколы // Автоматика и Вычислительная техника. 1988. — № 4. — С. 7−14.
- Бурдонов И. Б., Косачев А. С., Кулямин В. В. Использование конечных автоматов для тестирования программ // Программирование. 2000. — № 2. — С. 1228.
- Hartmanis J., Stearns R. Algebraic Structure Theory of Sequential Machines. — Printice-Hall, New-York, 1966. 210 p.
- Карпов Ю. Г. Теория автоматов. СПб.: Питер, 2003. — 208 с.
- Лукьянов Б. Д. О различающих и контрольных экспериментах с недетерминированными автоматами // Кибернетика и системный анализ. 1995. — № 5. — С. 69−76.
- A. Haddadi. Communication and Cooperation in Agent Systems: A Pragmatic Theory // Lecture Notes in Computer Science, 1056, Springer-Verlag, 1996.
- Wonham W. M. Supervision of DES // www.control.utoronto.ca/des, 1999. 324 P
- 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.
- Yannakakis M., Lee D. Testing finite state machines // AT&T Bell Labs, internal memorandum, 1990.
- 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.
- 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.
- 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.
- 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.
- Gerard J. Holzmann. Design and validation of computer protocols // Prentice-Hall, Englewood Cliffs, 1991.
- J. Farrell. IP Fragmentation Attacks on Checkpoint Firewalls // http://www.sans.org/rr/firewall/fragattacks.php, 2001.
- Василевский M. П. О распознавании неисправности автоматов // Кибернетика. 1973. — № 4. — С. 98−108.
- Т. S. Chow. Test design modeled by finite-state machines I I IEEE Trans. SE, vol. 4, no. 3, 1978.-P. 178−187.
- 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.
- 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.
- N. Yevtushenko, A. Petrenko. Test derivation method for an arbitrary deterministic automaton // Automatic Control and Computer Sciences, Allerton Press Inc., USA, no. 5,1990.
- 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.
- КуфареваИ. Б., Дорофеева M. Ю. Минимизация проверяющих тестов для конечных автоматов. //ВестникТГУ. Приложение. 2002. № 1 (II). С. 357−362.
- 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.
- B. Yang, H. Ural. Protocol conformance test generation using multiple UIO sequences with overlapping // Computer Communication Review, No. 4, 1990. P. 118−125.
- 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.
- 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.
- Куфарева И. Б. Применение недетерминированных автоматов в задачах синтеза проверяющих тестов для систем логического управления: Диссертация на соискания ученой степени канд. технических наук. — Томск, 2000. — 176 с.
- 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.
- P. Starke. Abstract automata, North-Holland / American Elsevier, 1972. 419 p.
- Rose M. Post Office Protocol Version 3. RFC 1460, June 1993. // http://www.faqs.org/rfcs/rfcl460.html.
- Евтушенко H. В., Куфарева И. Б. Отношения между недетерминированными автоматами. Томск: Изд-во Института оптики атмосферы СО РАН, 2001. -26 с.
- Т. Kim, Т. Villa, R. Brayton, A. Sangiovanni-Vincentelli. Synthesis of FSMs: -functional optimization. Kluwer Academic Publishers, 1997.
- H. Евтушенко, Т. Вилла, А. Петренко, Р. Брайтон, А. Санджованни- ' Винцентелли. Решение уравнений в логическом синтезе // Препринт, Томск: Изд-во «Спектр», 1999. 27 с.
- Yevtushenko N., Villa Т., Brayton R., Petrenko A., Sangiovani-Vincentelli A. Solution of synchronous language equations for logic synthesis // Вестник ТГУ. Приложение. 2002. № 1(11). С. 132−137.
- 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.
- H. Qin, P. Lewis. Factorisation of Finite State Machines under strong and observational equivalences // Formal Aspects of Computing, 3:284−307, Jul.-Sept. 1991.
- A. Petrenko, N. Yevtushenko. Solving asuynchronous equations. // Formal desrip-tion techniques/Protocol specification, testing and verification. Kluwer Academic Publishers, 1998.-P. 125−140.
- 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.
- N. Yevtushenko, T. Villa, R. Brayton, A. Petrenko, A. Sangiovanni-Vincentelli. Sequential Synthesis by Language Equation Solving // Technical report, 2003.
- S. Hassoun, T. Villa. Optimization of synchronous circuits. // In R. Brayton, S. Hassoun, andT. Sasao, editors, Logic Synthesis and Verification, 2001. P. 225−253.
- С. H. West. An automated technique of communication protocols validation // IEEE Trans. Comm., 26 (1978) 1271−1275.
- D. Brand and P. Zafiropulo. On communicating finite state machines // J. ACM 30(2), (1983) 323−342.
- G. v. Bochmann, C. A. Sunshine. Formal methods in communication protocol design // IEEE Trans, on Comm., Vol 28, 1980. P. 624−631.
- 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.
- S. Naito, M. Tsunoyama. Fault detection for sequential machines by transition tours // Proceedings of Fault Tolerant Comp, Syst., 1981. P.23 8−243.
- 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.
- Евтушенко H. В., Петренко А. Ф., Тренькаев В. H. Метод тестирования автоматных сетей, основанный на тестируемом поведении компоненты // Автоматика и вычислительная техника. 1996. — № 2. — С. 48−59.
- К. 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.
- 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.
- Hopcroft J. E., UlmanJ. D. Introduction to automata theory, Languages and Computation // Addison-Wesley Publishing Company, 1979.
- Буфалов С. А. Исследование живых и безопасных решений параллельных уравнений и неравенств на множестве полуавтоматов и автоматов: Диссертация на соискание ученой степени кандидата тех. наук, 2002.
- 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.
- Евтушенко H. В., Тренькаев В. H. Методы синтеза тестов для цифровых автоматов: Учебно-методическое пособие. Томск: Изд-во ТГУ, 1997. — 34 с.
- Тренькаев В. Н. Разработка методов синтеза проверяющих тестов для сетей из конечных автоматов: Диссертация на соискание ученой степени кандидата тех. наук, 2000. 188 с.
- К. El-Fakih, N. Yevtushenko and G. Bochmann. Protocol re-testing methods // Proc. of the IFIP 14th International Conference on Testing of Communicating Systems, 2002.
- 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.
- Дорофеева М. Ю., ЕвтушенкоН. В. Усовершенствование метода синтеза проверяющих тестов по мутационному автомату // Вестник ТГУ. Приложение. Серия «Математика. Кибернетика. Информатика». 2003. № 6. С. 164—169.
- Евтушенко Н. В., СпицынаН. В. Синтез полуавтоматов посредством решения логических уравнений // Материалы международной конференции, посвященной памяти профессора A.M. Богомолова. Саратов, 2002. — С.26.
- Спицына Н. В., Евтушенко Н. В., Петренко А. Ф. Решение уравнений в алгебре полуавтоматов для операции обобщенной композиции // Вестник ТГУ. Приложение. 2002. № 1(11). С. 265−270.
- СпицынаН. В., ШабалдинА. В. Интернет-программирование. Лабораторные работы. Часть 1: Методическое пособие. — Томск: Издательство ТГУ, 2002. 50 с.
- СпицынаН. В. Этапы тестирования на взаимодействие // Материалы Международной конференции «Современные проблемы физики и высокие технологии». Томск: Издательство НТЛ, 2003. — С. 500−502.
- Спицына Н. В., Тренькаев В. Н. К синтезу тестов для композиции конечных автоматов // Вестник ТГУ. Приложение. Серия «Математика. Кибернетика. Информатика». 2003. № 6. С. 183−187.
- 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.
- К. 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.