| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
A Method Enabling Feasible Conformance Test Sequence Generation for EFSM Models
May 2004 (vol. 53 no. 5)
pp. 614-627
A formal description of an implementation under test (IUT), such as its VHDL behavior description, is required to automatically generate feasible test sequences for the IUT. Although finite-state machines (FSMs) can be used to describe the control structures of communication protocols, the data portion can only be modeled by extended finite-state machines (EFSMs). However, infeasible paths due to the conflicts among the condition and action variables of EFSMs complicate the test generation process. This paper introduces a method enabling the automatic generation of realizable test sequences from a class of EFSMs. Algorithms to detect and eliminate conflicts caused by the interdependencies among the variables of a class of EFSM models are presented. After all conflicts are eliminated from the EFSM graph, the existing FSM-based automated test generation methods can be used to generate feasible test sequences. Recently, these algorithms have been implemented as a software package called INDEEL. This methodology is applied to generate feasible tests for protocols such as ACA and MIL-STD 188-220. Current applications include IETF protocols and ASAP.
[1] I. Adler and N. Megiddo, A Simplex Algorithm Whose Average Number of Steps Is Bound between Two Quadratic Functions of the Smaller Dimension J. ACM, vol. 32, no. 4, pp. 871-895, Oct. 1985.
[2] P.J. Ashenden, The Designer's Guide to VHDL. San Francisco: Morgan Kaufmann, 1996.
[3] J. Bhasker, A VHDL Primer. Englewood Cliffs, N.J.: Prentice Hall PTR, 1995.
[4] H.V. Bertine, W.B. Elsner, P.K. Verma, and K.T. Tewani, Overview of Protocol Testing Programs, Methodologies and Standards AT&T Technical J., pp. 7-16, Jan./Feb. 1990.
[5] E. Brinksma, A Theory for the Derivation of Tests Proc. IFIP Protocol Specification and Testing Verification (PSTV), 1988.
[6] L. Brömstrup and D. Hogrefe, TESDL: Experience with Generating Test Cases from SDL Specifications SDL '89: The Language at Work, Proc. Fourth SDL Forum, pp. 267-279, 1989.
[7] S. Budkowski and P. Dembinski, An Introduction to Estelle: A Specification Language for Distributed Systems Computer Networks and ISDN Systems, vol. 14, pp. 3-23, 198.7
[8] S.T. Chanson and J. Zhu, A Unified Approach to Protocol Test Sequence Generation Proc. INFOCOM'93 Conf., vol. 1, pp. 106-114, 1993.
[9] K.T. Cheng and A.S. Krishnakumar, Automated Generation of Functional Vectors Using the Extended Finite State Machine Model ACM Trans. Design Automation, vol. 1, no. 1, pp. 57-79, Jan. 1996.
[10] L.A. Clarke, Formal Evaluation of Data Flow Path Selection Criteria IEEE Trans. Software Eng., vol. 15, no. 11, pp. 1318-1332, Nov. 1989.
[11] T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms. McGraw-Hill, 1996.
[12] P.D. Coward, Symbolic Execution Systems a Review Software Eng. J., pp. 229-239, Nov. 1988.
[13] S. Crawley, J. Inulska, and B. McClure, OPD-Based Adaptive Management of Network Resources in Heterogeneous Defence Networks Proc. IEEE Workshop Distributed Systems Operations and Management, Oct. 1998.
[14] A.Y. Duale, Feasible Test Generation by Elimination of Inconsistencies from EFSM Models of Computer and Communications Systems PhD thesis, The City Univ. of New York, 2000.
[15] A. Duale and U. Uyar, Generation of Feasible Test Sequences for EFSM Models Proc. IFIP Int'l Conf. Testing of Communicating Systems (TestCom), pp. 91-109, Sept. 2000.
[16] A. Duale and M. Uyar, Indeel: A Software System for Inconsistency Detection and Elimination Protocol Specification and Testing, Advanced Telecomm. and Information Distribution, Final Report, first ed., Univ. of Maryland Press, chapter 3, pp. 3-29 to 3-34, 2001.
[17] A.Y. Duale, M.U. Uyar, B.D. McClure, and S. Chamberlain, Conformance Testing: Towards Refining VHDL Specifications Proc. IEEE Military Comm. Conf. (MILCOM), no. 5.1.4, Oct. 1999.
[18] A. En-Nauaary, R. Dssaouli, F. Khendek, and A. Elqortobi, Timed Test Cases Generation Based on State Characterisation Technique Proc. IEEE Real-Time Systems Symp. (RTSS), pp. 220-229, Dec. 1998.
[19] M. Fecko, P. Amer, U. Uyar, and A. Duale, Test Generation in the Presence of Conflicting Timers Proc. IFIP Int'l Conf. Testing of Communicating Systems (TestCom), pp. 301-320, Sept. 2000.
[20] M.U. Uyar, J. Zheng, M.A. Fecko, S. Samtani, and P.T. Conrad, Evaluation of Architectures for Reliable Server Pooling in Wired and Wireless Environments IEEE J. Selected Areas in Comm., special issue on recent advances in service overlay networks, to appear.
[21] M. Fecko, U. Uyar, P. Amer, A. Sethi, T. Dzik, R. Menell, and M. McMahon, A Success Story of Formal Description Techniques: Estelle Specification and Test Generation for MIL-STD 188-220 FDT in Practice, Computer Comm., R. Lai, ed, vol. 23, pp. 1196-1213, July 2000.
[22] M.A. Fecko, M.U. Uyar, A.Y. Duale, and P.D. Amer, A Technique to Generate Feasible Tests for Communications Systems with Multiple Timers IEEE/ACM Trans. Networking, to appear.
[23] A. Fin and F. Fummi, VHDL Error Simulator for Functional Test Generation http://jamaica.ee.pitt.edu/Archives/Proceeding Archives/ Date/Date2000/papers2000 , 2000.
[24] T. Higashino and G. Bochmann, Automatic Analysis and Test Case Derivation for a Restricted Class of LOTOS Expressions with Data Parameters IEEE Trans. Software Eng., vol. 20, no. 1, pp. 29-42, Jan. 1994.
[25] D. Lee and M. Yannakakis, Testing Finite-State Machines: State Identification and Verification IEEE Trans. Computers, vol. 43, no. 3, pp. 306-320, Mar. 1994.
[26] X. Li, T. Higashino, M. Higuchi, and K. Taniguchi, Automatic Generation of Extended UIO Sequences for Communication Protocols in an EFSM Model Proc. Seventh Int'l Workshop Protocol Test Systems, pp. 225-240, Nov. 1997.
[27] R.J. Linn and M.U. Uyar, Conformance Testing Methodologies and Architecture for OSI Protocols. Los Alamitos, Calif.: IEEE CS Press, 1994.
[28] R. Miller and S. Paul, Generating Conformance Test Sequences for Combined Control Flow and Data Flow of Communication Protocols Proc. 12th Int'l Symp. Protocol Specification, Testing, and Verification, pp. 12-27, 1992.
[29] J.R. Moonen, J.M.T. Romijn, O. Sies, J. Springintveld, L.G.M. Feijs, R.L.C. Koymans, A Two-Level Approach to Automated Conformance Testing of VHDL Designs SEN-R9707, ISSN 1386-369X, 1997.
[30] OpenVera White Paper,http://www.open-vera.com/technicalopenvera_wp.html , 2003.
[31] A.F. Petrenko, G. v Bochmann, and M.Y. Yao, On Fault Coverage of Tests for Finite State Specifications Computer Networks and ISDN Systems, vol. 29, no. 1, 1996.
[32] S. Rapps and E. Weyuker, Selecting Software Test Data Using Data Flow Information IEEE Trans. Software Eng., vol. 11, no. 4, Apr. 1985.
[33] E.M Rudnick, R. Vietti, A. Ellis, F. Corno, P. Prinetto, and M. Sonza Reorda, Fast Sequential Circuit Test Generation Using High-Level and Gate-Level Technique Proc. DATE98: Design, Automation and Test in Europe, Feb. 1998.
[34] B. Sarikaya, G. Bochmann, and E. Cerny, A Test Design Methodology for Protocol Testing IEEE Trans. Software Eng., vol. 13, no. 5, pp. 518-531, May 1987.
[35] D. Solow, Linear Programming: An Introduction to Finite Improvement Algorithms. North-Holland, 1984.
[36] H. Ural, Formal Methods for Test Sequence Generation IEEE Trans. Comm., vol. 39, no. 4, pp. 514-523, 1992.
[37] H. Ural, A Test Derivation Method for Protocol Conformance Testing Proc. Sixth Int'l Conf. Protocol Specification, Testing, and Verification, pp. 347-358, 1989.
[38] H. Ural, Formal Methods for Test Sequence Generation IEEE Trans. Comm., vol. 39, no. 4, pp. 514-523, 1992.
[39] M.U. Uyar, Dual State Augmentation for Minimizing Conformance Test Costs Computer Networks and ISDN Systems, vol. 30, pp. 1277-1294, 1998.
Index Terms:
Conformance testing, EFSM, Estelle, FSM, test generation, VHDL.
Citation:
Ali Y. Duale, M. Ümit Uyar, "A Method Enabling Feasible Conformance Test Sequence Generation for EFSM Models," IEEE Transactions on Computers, vol. 53, no. 5, pp. 614-627, May 2004, doi:10.1109/TC.2004.1275300
