Test Sequence Generation Based on Chain Unique Input-Output Sequence in FSM Conformance Testing
Authors: 
Weiwei Lin, Hongwei ZengAuthors Info & Claims
Pages 87 - 92
Abstract
This paper introduces a test method based on chain unique input/output (CUIO) sequence in finite state machine (FSM) conformance testing. For FSMs with UIO for each state, the test sequence based on CUIO can identify all the states and verify all the transitions. For FSMs without UIO for some states, the test sequence based on CUIO can identify as many states and verify as many transitions as possible. Meanwhile, W method is introduced to deal with the unidentified states and the unverified transitions. For FSMs without UIO for each state, the method completely degenerates to W method. It is proved by experiment that the average and maximum reduction rate are 45.5% and 63.2% comparing with UIO method. Moreover, the method is always feasible even when UIO method fails.
References
[1]
Liu P., Li Y., and Li Z. 2019. Some thoughts on model-based test optimization. In Proceedings of 19th International Conference on Software Quality, Reliability and Security Companion. IEEE, Sofia, Bulgaria, 268-274. https://doi.org/10.1109/QRS-C.2019.00058.
[2]
Lu G. Z. and Miao H. K. 2016. Optimized test cases generation for EFSM model combining abstraction refinement and satisfiability. CJC 39, 11 (February 2016), 2236-2252. https://doi.org/10.11897/SP.J.1016.2016.02236.
[3]
Porto R. Faimison, Endo T. Andre, and Simao A. 2013. Generation of checking sequences using identification sets. In Proceedings of International Conference on Formal Engineering Methods. IEEE, Berlin, Heidelberg, 115-130. https://doi.org/10.1007/978-3-642-41202-8_9.
[4]
Hoda K. and Yvan L. 2017. On FSM-based testing: An empirical study: complete round-trip versus transition trees. In Proceedings of 28th International Symposium on Software Reliability Engineering. IEEE, Toulouse, France, 305-315. https://doi.org/ 10.1109/ISSRE.2017.34.
[5]
Gaudel M. 2017. Formal methods for software testing. In Proceedings of International Symposium on Theoretical Aspects of Software Engineering. IEEE, Sophia Antipolis, France, 1-3. https://doi.org/10.1109/TASE.2017.8285622.
[6]
Lin W. W. and Zeng H. W. 2015. A chain algorithm for conformance testing based on UIO sequences. In Proceedings of 16th International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing. IEEE, Takamatsu, Japan, 1-6. https://doi.org/ 10.1109/SNPD.2015.7176270.
[7]
Ahmad I., Ali M. Faridah, and Shoba Das A. 2006. Synthesis of finite state machines for improved state verification. Comput. Electr. Eng. 32, 5 (September 2006), 349–363. https://doi.org/10.1016/j.compeleceng.2005.12.002.
[8]
Zhang X. C., Yang M. H., Zhang J., Shi H. L., and Zhang W. 2012. A study on the extended unique input/output sequence. Inf. Sci. 203 (October 2012), 44-58. https://doi.org/10.1016/j.ins.2012.03.007.
[9]
R. M. Hierons, M. R. Mousavi, M. K. Thomsen and U. C. Trker, “Hardness of deriving invertible sequences from finite state machines,” in Proc. SOFSEM, Limerick, Ireland, 2017, pp. 147–160.
[10]
K. El-Fakih, R. M. Hierons and U. C. Turker, “ -branching UIO sequences for partially specified observable non-deterministic FSMs,” IEEE Trans. Softw. Eng., pp. 1-1, Apr. 2019.
[11]
L. Duan and J. Chen, “Reducing test sequence length using invertible sequences,” in Proc. ICFEM. Berlin, Heidelberg, 2007, pp. 171-190.
[12]
F. Zhang and R. L. Probert, “Minimizing the Lengths of Test Sequences with Overlapping,” in Proc. I2MTC, Ottawa, Ont., Canada, 2006, pp. 2355-2359.
[13]
L. Xie, J. L. Wei and G. X. Zhu, “Protocol conformance testing method based on improved FSM,” JCM, vol. 32, no. 6, pp. 172-176, Jun. 2011.
[14]
M. C. Yalcin and H. Yenigun, “Using distinguishing and UIO sequences together in a checking sequence,” in Proc. TestCom. Berlin, Heidelberg, 2006, pp. 259-273.
[15]
T. S. Chow, “Testing software design modeled by finite-state machines,” IEEE Trans. Softw. Eng., vol. SE-4, no. 3, pp. 178-187, May. 1978.
[16]
S. R. Liang, “Fuzzy test algorithm of ZigBee protocol based on FSM,” M.S. thesis, COC., BUPT., Beijing, China, 2014.
[17]
D. S. Sun, “GUI modeling and test method research based on IOLTS,” M.S. thesis, Dept. Shanghai Univ., Shanghai, China, 2015.
[18]
J. D. Lee, J. I. Jung, J. H. Lee, J. G. Hwang, J. H. Hwang and S. U. Kim, “Verification and conformance test generation of communication protocol for railway signaling systems,” Comput. Stand. Interfaces, 2007, 29(2): 143-151.
[19]
J. F. Cutigi, A. Simao, S. R. S. Souza, “Reducing FSM-based test suites with guaranteed fault coverage,” Comput. J., 2016, 59(8): 1129-1143.
[20]
B, Sarikaya, G. V. Bochmann, “Synchronization and specification issues in protocol testing,” IEEE Trans. Commun., 1984, 32(4): 389-395.
[21]
Z. B. Wang, H. Zhou, B. H. Zhao, “Path overlapped method for protocol conformance test generation,” Comput. Sys. Applications, 2011, 20(7): 47-52.
[22]
R. E. Miller, S. Paul, “On the generation of minimal-length conformance tests for communication protocols,” IEEE-ACM Trans. Netw., 1993, 1(1): 116-129.
[23]
K. Sabnani, A. Dahbura, “A new technique for generating protocol test,” ACM SIGCOMM Comp. Commun. Rev., 1985, 15(4): 36-43.
Recommendations
Automated Unique Input Output Sequence Generation for Conformance Testing of FSMs
This paper describes a method for automatically generating unique input output (UIO) sequences for FSM conformance testing. UIOs are used in conformance testing to verify the end state of a transition sequence. UIO sequence generation is represented as ...
A FSM-based Test Sequence Generation Method for RPL Conformance Testing
GREENCOM-ITHINGS-CPSCOM '13: Proceedings of the 2013 IEEE International Conference on Green Computing and Communications and IEEE Internet of Things and IEEE Cyber, Physical and Social ComputingThis paper contributes to the conformance testing of RPL. Through analyzing the protocol, a model based on the Finite State Machine(FSM) is proposed to describe the RPL. Combined with the existing methods, an algorithm is applied to generate the test ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2021
366 pages
ISBN:9781450390675
DOI:10.1145/3494885
Copyright © 2021 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 20 December 2021
Check for updates
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
CSSE 2021
CSSE 2021: 2021 4th International Conference on Computer Science and Software Engineering
October 22 - 24, 2021
Singapore, Singapore
Acceptance Rates
Overall Acceptance Rate 33 of 74 submissions, 45%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 28Total Downloads
- Downloads (Last 12 months)6
- Downloads (Last 6 weeks)0
Reflects downloads up to 16 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format