臺灣博碩士論文加值系統

通訊協定一致性測試在今日的通訊領域中扮演把關的角色。一個實作完成的通訊協定需通過通訊協定一致性測
試來確保此實作與原始的規格是否相符。我們通常將通訊協定以有限狀態機(Finite State Machine)的形式來表示。當我們在進行通訊協定一致性測試時，整個測試架構是以黑盒子的形式來進行，所以只能藉由輸入訊息至通訊協定實作中，觀察通訊協定實作輸出的訊息來判斷其一致性。在進行測試時，此實作所需要的輸入訊息需要依事先規定的順序依次到達測試實作。由於輸入訊息的傳輸資料埠通常有兩個以上，因此輸入訊息至資料埠就會有同步問題的產生。解決同步問題的方法有兩種，一為拉額外的線路，另一為利用同步測試序列。在過去已經有許多人針對同步測試序列的問題進行討論，並且提出了解決的方法。在本論文中，首先介紹同步問題在通訊協定一致性測試中的發展歷史。由歷史的回顧來瞭解我們的動機：提出一個可產生更廣義並且能包timeout指令的可同步測試序列的方法。為了達到此目標，首先，我們提出了專埠可同步測試序列的定義，並且提出了一個產生專埠可同步測試序列的方法來解決測試上的同步問題。此方法主要是先將原來的通訊協定規格的有限狀態機轉換成多路通訊( multiplex )的有限狀態機，在此新的有限狀態機下的每一條路線都是可同步的狀態。接下來再利用原有的測試序列產生方法來產生同步測試序列。藉由我們的方法，可以產生包含timeout的同步測試序列。

Protocol conformance testing is used to test if the implementation conform to specification. We commonly use the finite state machine (FSM) model to specify protocols. Due to the black box testing feature and the test architecture, a synchronization problem among inputs may occur. In this thesis, we discuss the synchronizable problem of protocol conformance testing and propose a port-specified synchronizable test sequence definition which can include timeout command. We use an O(mn) algorithm to transfer a digraph of a FSM into a multiplex digraph. Every transfer sequence in the multiplex digraph is synchronizable. Then you can apply different test sequence generation methods on the multiplex digraph .

Contents
Abstract
Chpater 1 Introduction
1.1 Protocol conformance Testing
1.2 Synchronization Problem in Conformance Testing
Chapter 2 Preliminaries
2-1 Notation
2-2 Test Architectures
2-3 Test Sequences
Chpater 3 The Synchronization Problem
3-1 Previous Work on Synchronizable Test Sequences of an FSM
3-2 How the Conformance Testing Encounters the Synchronization Problem
Chapter 4 Overcoming the synchronizable Problem
4-1 Generating the port-specified synchronizable test sequence from the duplex Digraph
4-2 Application of the multiplex digraph
Chpater 5 Conclusion and Future Work
Bibliography

[Aho 91] A. V. Aho, A. T. Dahubra, D. Lee and M. U. Uyar, "An optimization technique for protocol conformance test generation based on UIO sequences and rural Chinese postman tours," IEEE Transaction on Communications, Vol. 39, No. 11, pp. 1604-1615, 1991.
[Andrews 91] G. Andrews, Concurrent Programming: Principles and Practice, Benjamin Commings Pub. Co.,Inc., Redwood, CA, 1991
[Berkhout 90] S.R. Berkhout, M.F.Witteman, Application of multi-party conformance test methods to the GSM mobile network system, in : Proceeding of IFIP, 3rd Int. Workshop on Protocol Test Systems, McLean, VA,October 1990
[Bochmann 78] G.v. Bochmann, "Finite state description of communication protocols," Computer Networks, Vol.2, 1978, 362-372
[Bochmann 80] G.v. Bochmann, "A general transition model for protocols and communication services," IEEE Transaction. on Communications, Vol. Com-28, April 1980, 643-650
[Boyd 91] S. Boyd and H. Ural, "The synchronization problem in protocol testing and its complexity" Information Processing Letters, Vol. 40, Nov. 1991, 131-136
[Chanson 90] S.T.Chanson, S.T. Vuong,H.Dany, The ferry clip approach to multi-party testing, in : Proceeding. IFIP, 3rd Int. Workshop on Protocol Test Systems, McLean, VA,October 1990
[Chen 90] W.H. Chen, C.S.LU, L.Chen, and J.T. Tang, "Synchronizable protocol test generation via the duplex technique" Proceeding. IEEE INFOCOM '90, 561-563
[Chen 95] W.H. Chen and H. Ural, " Synchronizable test sequences based on multiple UIO sequences," IEEE/ACM Transaction Network, Vol.3, No. 2, April 1995 152-7
[Chow 78] T. S. Chow, "Testing software design modeled by finite-state machines," IEEE Transaction on Software Engineer, Vol. SE-4, No. 3, pp. 178-187, 1978.
[Fujiwara 91] S. Fujiwara, G. v. Bochmann, F. Khendek, M. Amalou and A. Ghedamsi, "Test selection based on finite state models," IEEE Transaction on Software Engineer, Vol. 17, No. 6, pp. 591-603, 1991.
[Goenenc 70] G. Goenenc, "A method for the design of fault detection experiments," IEEE Trans. on Computer, Vol. C-19, pp. 551-558, 1970
[Guyot 95] S. Guyot and H. Ural , " Synchronizable checking sequences based on UIO sequences," Proceeding Protocol Test Systems VIII, 1995
[Knightson] Keith G. Knightson, OSI Protocol Conformance Testing ,McGraw-Hill,Inc. pp206
[Lin 98] Rong S.Lin and Maria C. Yuang, "Synchronization Paradigm for Protocol Testing under Multi-Party Configuration," to appear on Computers & Mathematics with Applications.
[Luo 93] G.Luo,R. Dssouli, G.von Bochmann, P. Venkataram, A. Ghedamsi, Generating synchronizable test sequences based on finite state machine with distributed ports, in : Proceeding. Int. IFIP Workshop on Protocol Test Systems, 1993.
[Naito 81] S. Naito and M. Tsunoyama, "Fault detection for sequential machines by transitions tours," Proceeding. of IEEE Fault Tolerant Computer. Symposium., 1981, 238-243
[Sabnani 88] K. K. Sabnani and A. T. Dahbura, "A protocol test generation procedure," Computer Networks and ISDN Systems, Vol. 15, No. 4, pp. 285-297, 1988.
[Sarikaya 84] B. Sarikaya and G. v. Bochmann, " Synchronizable and specification issues in protocol testing" IEEE Transaction. on Communications, Vol. 32, No.4 Apr. 1984, 389-395
[Sarikaya 93] B. Sarikaya, Principles of Protocol Engineering and Conformance Testing, Ellis Horwood Limited, 1993
[Tarnay 91] K. Tarnay, Protocol Specification and Testing, Plenum Press, 1991
[Tai 98] K. C. Tai, and Y. C. Young, "Synchronizable Test Sequences of Finite State Machines", Computer Networks and ISDN Systems, vol. 30, issue 12, 1998
[Turner 93] K J., Turner, ed., Using Formal Description Techniques: An Introduction to Estelle, Lotos, and SDL, Wiley, 1993
[Ural 93] H. Ural and Z. Wang, " Synchronizable test sequence generation using UIO sequences, " Computer Communications, Vol. 16, No.10, Oct. 1993 653-661
[Uyar 87] M.U.Uyar,A.T. Dahbura, Optimal test sequence generation for protocols: the Chinese postman algorithm applied to Q.931, Proceeding .IEEE GLOBALCOM,1987.
[Vuong 89] S. T. Vuong, W. Y. L. Chan and M. R. Ito, "The UIOv-method for protocol test sequence generation," Proceeding. of 2nd Workshop on Protocol Test Systems, IFIP, 1989.
[Wu 98] Wen-Jer Wu, Wen-Huei Chen, Chuan Yi Tang, " Synchronizable test sequence for multi-party protocol conformance testing," Computer communications 21, 1998, 1177-1183