Уточнение недетерминированного эталонного автомата при условном тестировании
В статье рассматривается синтез проверяющих тестов с гарантированной полнотой для недетерминированных автоматов. В качестве отношения конформности (соответствия) рассматривается отношение редукции, т. е. для каждой входной последовательности множество выходных последовательностей «хорошего» проверяемого автомата должно содержаться в множестве выходных последовательностей эталонного автомата. Мы рассматриваем условный эксперимент с проверяемым автоматом т.е. предполагаем, что перед подачей следующего тестового набора на проверяемый автомат, мы анализируем выходные последовательности этого автомата на предыдущие тестовые последовательности. Чтобы сократить длину проверяющего теста, в данной работе мы предлагаем «уточнять» эталонный автомат, удаляя из него вход-выходные последовательности, которых нет в проверяемом автомате, правильно отреагировавшем на некоторые тестовые последовательности. В результате эталонный автомат становится «более детерминированным», и может оказаться, что требуемая полнота тестирования для такого более детерминированного эталонного автомата будет достигнута ранее, чем для исходного эталона. Достоинства предлагаемого подхода иллюстрируются на простом примере.
Keywords
Finite State Machine (FSM) ,
adaptive testing ,
fault model ,
complete test suite w.r.t. the fault model ,
Конечный автомат ,
условное тестирование ,
модель неисправности ,
полный проверяющий тест ,
эксперименты с автоматами Authors
| ПЕТРЕНКО Александра | Исследовательский центра по информатике | |
| ЕВТУШЕНКО Нина Владимировна | Томский государственный университет | |
Всего: 2
References
Zhang F. and Cheung T. Optimal transfer trees and distinguishing trees for testing observable nondeterministic finite-state machines // IEEE Trans. Software Engineering. 2003. V. 29(1). P. 1 - 14.
Tripathy P. and Naik K. Generation of adaptive test cases from nondeterministic finite state models. Protocol test systems // Proc. of the IFIP TC6/WG6.1 Fifth International Workshop on Protocol Test Systems. 1992. P. 309 - 320.
Tretmans J. Test generation with inputs, outputs and quiescence // Proc. of TAGAS'96. 1996. P. 127 - 146.
Petrenko A. and Yevtushenko N. Conformance tests as checking experiments for partial nondeterministic FSM // Proc. of the 5th International Workshop on Formal Approaches to Testing of Software (Fates 2005). 2005. LNCS volume 3997. P. 118 - 133.
Petrenko A., Yevtushenko N., and Bochmann G.v. Testing deterministic implementations from their nondeterministic specifications // Proc. of the IFIP TC6/WG6.1 Ninth International Workshop on Protocol Test Systems. 1996. P. 125 - 140.
Petrenko A., Yevtushenko N., Lebedev A., and Das A. Nondeterministic state machines in protocol conformance testing // Proc. of the IFIP TC6/WG6.1 Sixth International Workshop on Protocol Test Systems. 1993. P. 363 - 378.
Nachmanson L., Veanes M., Schulte W., et al. Optimal strategies for testing nondeterministic systems // Proc. of ISSTA. 2004. Software Engineering Notes ACM. V. 29. P. 55 - 64.
Miller R., Chen D., Lee D., Hao R. Coping with nondeterminism in network protocol testing. testing of communicating systems // Proc. of the IFIP TC6/WG6.1 19th International Conference on Protocol Test Systems. 2005. LNCS volume 3502. P. 129 - 145.
Luo G., Petrenko A., and Bochmann G.v. Selecting test sequences for partially specified non-deterministic finite state machines // Proc. of the IFIP TC6/WG6.1 Seventh International Workshop on Protocol Test Systems. 1994. P. 95 - 118.
Luo G.L., Bochmann G.v., and Petrenko A. Test selection based on communicating nondeterministic finite-state machines using a generalized Wp-method // IEEE Trans. Software Engineering. 1994. V. 20(2). P. 149 - 161.
Kufareva I., Yevtushenko N., and Petrenko A. Design of tests for nondeterministic machines with respect to reduction // Automatic Control and Computer Sciences. 1998. No. 3. P. 1 - 6.
Kloosterman H. Test Derivation from Non-Deterministic Finite State Machines // Proc. of the IFIP TC6/WG6.1 Fifth International Workshop on Protocol Test Systems. 1992. P. 297 - 308.
Hwang I., Kim T., Hong S., and Lee J. Test selection for a nondeterministic FSM // Computer Communications. 2001. V. 24/12 (7). P.1213 - 1223.
Hierons R.M. and Ural H. Concerning the ordering of adaptive test sequences // Proc. of the 23rd IFIP International Conference on Formal Techniques for Networked and Distributed Systems (FORTE 2003). 2003. LNCS volume 2767. P. 289 - 302.
Hierons R.M. Using candidates to test a deterministic implementation against a nondeterministic finite state machine // The Computer J. 2003. V. 46 (3). P. 307 - 318.
Hierons R.M. Testing from a non-deterministic finite state machine using adaptive state counting // IEEE Trans. Computers. 2004. V. 53 (10). P. 1330 - 1342.
Dorofeeva M., Petrenko A., Vetrova M., and Yevtushenko N. Adaptive test generation from a nondeterministic FSM // Radioelektronika i Informatika. 2004. No. 3. P. 91 - 95.
Hierons R.M. Adaptive testing of a deterministic implementation against a nondeterministic finite state machine // The Computer J. 1998. V. 41(5). P. 349 - 355.
Alur R., Courcoubetis C., and Yannakakis M. Distinguishing tests for nondeterministic and probabilistic machines // Proc. of the 27th ACM Symp. on Theory of Comp. 1995. P. 363 -372.
AboElFotoh H., Abou-Rabia O., and Ural H. A test generation algorithm for protocols modeled as non-deterministic FSMs // The Software Eng. J. 1993. V. 8(4). P. 184 - 188.
Yevtushenko N., Lebedev A., and Petrenko A. On checking experiments with nondeterministic automata // Automatic Control and Computer Sciences. 1991. V. 6. P. 81 - 85.
