Test derivation based on tree FSMs and tree automata
https://doi.org/10.15514/ISPRAS-2014-26(6)-6
Abstract
In this paper, an approach for testing software implementations of telecommunication protocols based on tree finite state machines (FSM) is proposed. The first step is the extraction of the specification Extended FSM from an informal protocol description. The next step is to derive a corresponding EFSM l-equivalent that is a tree FSM. Based on the set of considered faults corresponding sequences of the l-equivalent are included into a test suite. The proposed approach is illustrated by protocol TCP (Windows).
References
1. A. Gill, Introduction to the Theory of Finite-state Machines. M. Science. 1966, 272 p.
2. A.V. Kolomeets, Algoritmy sinteza proveryayushchikh testov dlya upravlyayushchikh sistem na osnove rasshirennykh avtomatov: dis. ... kand. tekhn. nauk. Tomskii gosudrastvennyi universitet, [PhD dissertation, Tomsk state university] 2010, 129 s.
3. T. S. Chow. Testing software design modelled by finite state machines. IEEE Transactions on Software Engineering. 1978, pp. 178-187.
4. M.P. Vasilevskii. O raspoznovanii neispravnostei avtomatov. [On the recognition of failure] Kibernetika, [Cybernetic] 9(4). 1973, pp. 93-108.
5. R. Dorofeeva, K. El-Fakih, S. Maag, A.R. Cavalli, N. Yevtushenko. Experimental evaluation of FSM-based testing methods. In Proc. of the IEEE International Conference on Software Engineering and Formal Methods (SEFM05). 2005, pp. 23-32.
6. K. El-Fakih, S. Prokopenko, N. Yevtushenko, G. Bochmann. Fault Diagnosis in Extended Finite State Machines. Lecture Notes in Computer Science, V. 2644. 2003, pp. 197-210.
7. A.V. Kolomeets, S.A. Prokopenko. Metod sinteza diagnosticheskikh testov dlya rasshirennykh konechnykh avtomatov. [Extended finite state machine based test derivation strategies] Vestnik TGU. Prilozhenie #6. [Vestnik of the Tomsk State University, part #6] 2003, pp. 174-177.
8. K. El-Fakih, A. Kolomeez, S. Prokopenko, N. Yevtushenko. Extended Finite State Machine Based Test Derivation Driving By User Defined Faults. International Conference ICST. 2008, pp. 308-317.
9. H. Ural. Test sequence selection based on static data flow analysis. Computer communications, V. 10, № 5. 1987, pp. 234 – 242.
10. H. Chen. Test sequence generation from the protocol data portion based on the selecting Chinese Postman algorithm. Information Processing Letters, V. 65. 1998, pp. 261-268
11. A. Cavalli, D. Lee, C. Rinderknecht, F. Zaidi. Hit-or-Jump: An algorithm for embedded testing with applications to IN services. FORTE XII and PSTV XIX, China,1999, pp. 41-58.
12. N. Kushik, M. Forostyanova, S. Prokopenko, N. Yevtushenko. Studying the optimal height of the EFSM equivalent for testing telecommunication protocols. Proc. of the Second Intl. Conf. on Advances In Computing, Communication and Information Technology – CCIT. 2014, pp. 159-163.
13. I. Burdonov, A.S. Kosachev, V.V. Kuljamin. Neizbytochye algoritmy obxoda orientirovannyx grafov. Determinirovannyj sluchaj.[Irredundant algorithms for traversing oriented graphs. deterministic case], Trudy ISP RАN [The Proceedings of ISP RAS], 2003, pp. 59-69.
14. K. Hant. TCP/IP Network Administration. Cumbo. 2008, 816 p.
15. The application package. The certificate of state registration of the computer program №2014661807 "Programma sinteza testov konechno-avtomatnymi metodami" [The program of synthesis tests based on finite state machine], Tomsk State University
16. A. J. Offutt, R. H. Untch. Mutation 2000: Uniting the Orthogonal. In Proceedings of the 1st Workshop on Mutation Analysis (MUTATION’00). Mutation Testing for the New Century. California, 2001, pp. 34–44.
Review
For citations:
Forostyanova M. Test derivation based on tree FSMs and tree automata. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2014;26(6):67-76. (In Russ.) https://doi.org/10.15514/ISPRAS-2014-26(6)-6
Email this article 