The Incremental Maintenance of Transition Tour

• Autorzy: Németh G. A. , Pap Z.

Identyfikatory

DOI

10.3233/FI-2014-972

• Języki publikacji: EN

Abstrakty

EN

While evolutionary developmentmethodologies have become increasingly prevalent, incremental testing methods are lagging behind. Most traditional test generation algorithms – including the Transition Tour method – rebuild test sequences from scratch even if minimal changes to the system have been made. In the current paper we propose two incremental algorithms to update a Transition Tour test sequence after changes in a deterministic finite state machine model. Our solution uses existing information – the Eulerian graph of a previous version of the system and an Euler tour in it – to update the test cases of the system in response to modification. The first algorithm keeps an Eulerian graph up to date, while the second algorithm maintains an Euler tour in the augmented graph. Analytical and practical analyses show that our algorithms are very efficient in the case of changing specifications. We also demonstrate our methods through an example.

Słowa kluczowe

EN

finite state machine; test generation algorithms; incremental algorithm; incremental test generation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 129, nr 3
• Strony: 279--300
• Opis fizyczny: Bibliogr. 34 poz., rys., wykr.

Twórcy

autor

Németh G. A.

• High Speed Networks Laboratory Department of Telecommunications and Media Informatics Budapest University of Technology and Economics Magyar tudósok körútja 2, Budapest, H-1117, Hungary

autor

Pap Z.

• High Speed Networks Laboratory Department of Telecommunications and Media Informatics Budapest University of Technology and Economics Magyar tudósok körútja 2, Budapest, H-1117, Hungary

Bibliografia

• [1] Ammann, P., Offutt, J.: Introduction to Software Testing, 1 edition, Cambridge University Press, New York, NY, USA, 2008.
• [2] Binder, R. V.: Testing object-oriented systems: models, patterns, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2000.
• [3] Bochmann, G. v., Das, A., Dssouli, R., Dubuc, M., Ghedamsi, A., Luo, G.: Fault Models in Testing, Proceedings of the IFIP TC6/WG6.1 Fourth International Workshop on Protocol Test Systems IV, North-Holland Publishing Co., Amsterdam, The Netherlands, The Netherlands, 1992.
• [4] Broy, M., Jonsson, B., Katoen, J.-P., Leucker, M., (Eds.), A. P.: Model-Based Testing of Reactive Systems, Springer, 2005.
• [5] Chow, T.: Testing software design modeled by finite-state machines, IEEE Transactions on Software Engineering, 4(3), May 1978, 178–187.
• [6] Dorofeeva, R., El-Fakih, K., Maag, S., Cavalli, A. R., Yevtushenko, N.: FSM-based conformance testing methods: A survey annotated with experimental evaluation, Information and Software Technology, 52(12),2010, 1286–1297.
• [7] Dove, R.: Response Ability - The Language, Structure and Culture of the Agile Enterprise, John Wiley and Sons, 2001.
• [8] Edmonds, J., Johnson, E. L.: Matching, Euler tours and the Chinese postman, Mathematical Programming,5(1), 1973, 88–124.
• [9] Eiselt, H. A., Gendreau, M., Laporte, G.: Arc routing problems, part I: The Chinese postman problem,Operations Research, 43(2), 1995, 231–242.
• [10] El-Fakih, K., Yevtushenko, N., von Bochmann, G.: FSM-Based Incremental Conformance Testing Methods, IEEE Transactions on Software Engineering, 30(7), 2004, 425–436.
• [11] Friedman, A. D., Menon, P. R.: Fault Detection in Digital Circuits, Prentice-Hall, 1971.
• [12] Gibbons, A.: Algorithmic graph theory, Cambridge University Press, 1985.
• [13] Highsmith, J. A.: Adaptive Software Development: A Collaborative Approach to Managing Complex Systems, Dorset House Publishing Co., Inc., New York, NY, USA, 2000.
• [14] Holzmann, G. J.: Design and Validation of Protocols, Prentice-Hall, 1990.
• [15] ITU-T: Recommendation Z.100: Specification and Description Language, 2000.
• [16] Jääskeläinen, A.: Filtering test models to support incremental testing, Proceedings of the 5th internationalacademic and industrial conference on Testing - practice and research techniques, TAIC PART’10, Springer-Verlag, Berlin, Heidelberg, 2010.
• [17] Kwan, M.: Graphic programming using odd or even points, Chinese Math, (1), 1962, 273–277.
• [18] Lee, D., Yannakakis,M.: Principles and Methods of Testing Finite State Machines – A Survey, Proceedings of the IEEE, 84(8), 1996, 1090–1123.
• [19] LEMON: A C++ library for efficient modeling and optimization in networks, Technical report, Avaliable: http://lemon.cs.elte.hu.
• [20] Lin, Y., Zhao, Y.: A new algorithm for the directed chinese postman problem, Computers & operations research, 15(6), 1988, 577–584.
• [21] Naito, S., Tsunoyama, M.: Fault detection for sequential machines by transition-tours, Proceedings of the11th IEEE Fault-Tolerant Computing Conference (FTCS 1981), IEEE Computer Society Press, 1981.
• [22] Orloff, S.: A Fundamental Problem in Vehicle Routing, Networks, 4, 1974, 35–64.
• [23] Pap, Z., Subramaniam, M., Kovács, G., Németh, G. A.: A Bounded Incremental Test Generation Algorithm for Finite State Machines, 19th IFIP Testing of Communicating Systems (TestCom/FATES), Tallinn, Estonia,2007.
• [24] Petrenko, A., Yevtushenko, N., Lebedev, A., Das, A.: Nondeterministic State Machines in Protocol Conformance Testing, Proceedings of the IFIP TC6/WG6.1 Sixth International Workshop on Protocol Test systems VI, 1994.
• [25] Simão, A., Petrenko, A.: Fault Coverage-Driven Incremental Test Generation, Comput. J., 53, November2010, 1508–1522.
• [26] Simao, A., Petrenko, A., Maldonado, J.: Comparing finite state machine test coverage criteria, Software, IET,3(2), april 2009, 91–105.
• [27] Smith, P., Reinertsen, D.: Developing Products in Half the Time: New Rules, New Tools, John Wiley and Sons, 1998.
• [28] Subramaniam, M., Pap, Z.: Analyzing the Impact of Protocol Changes on Tests, Proceedings of the IFIP International Conference on Testing Communicating Systems, Test Com, 2006.
• [29] Takahashi, J., Kakuda, Y., Ohba, M.: Extended-model Based Testing by Using Directed Chinese Postman Problem, Journal of Reliability Engineering Association of Japan, 25(3), 2003, 267–278.
• [30] Tarjan, R.: Depth-first search and linear graph algorithms, SIAM Journal of Computing, 1(2), jun 1972,146–160.
• [31] TC97/SC21, I.: Estelle – A Formal Description Technique Based on an Extended State Transition Model. International Standard 9074, 1988.
• [32] Thimbleby, H.: The directed chinese postman problem, Software Practice and Experience, 33, 2003, 1081–1096.
• [33] Utting, M., Legeard, B.: Practical Model-Based Testing: A Tools Approach, Morgan Kaufmann PublishersInc., San Francisco, CA, USA, 2007.
• [34] Yannakakis, M., Lee, D.: Testing finite state machines: fault detection, Selected papers of the 23rd annual ACM symposium on Theory of computing, 1995.