臺灣博碩士論文加值系統

隨著網路、無線通訊各項技術的蓬勃發展，各式各樣架構其上的服務應運而生。不同的服務需要不同的通訊協定來配合，通訊協定制訂了參與通訊的各方所需遵循的規範。而為了因應傳輸媒介的不同、傳輸資料的多樣性、反應時間、資料的安全性…等方面不同的條件，新的、更複雜的通訊協定不斷地在制訂當中。
在工業界開發新的通訊產品，實作一個新的通訊協定時。由於對新的通訊協定的不熟悉，只經由通訊協定的標準規格書，往往無法得到完整、正確的認知。此時必須以逆向工程的方式，對市面上已經開發成熟的產品進行一些測試。經由測試的結果，逐步釐清各個細部，推導出正確的標準規格。而缺乏一套有系統的方法，使得這項工作往往需要反覆多次，並耗費許多的時間。
在這篇論文的研究中，我們提出一套系統化進行逆向工程的方法，並製作自動化的工具，透過實驗來驗證其可行性。

Fast development in networking and wireless communication result in a large amount of services provided via them. Each service needs to cooperate with a communication protocol which is defined as a set of rules that each part involved in the communication environment must abide. Communication pro-tocols are more complicated nowadays to satisfy different requirement in bandwidth, response time, data format, security…etc.
When a new communication protocol is implemented, the most critical problem is it is very hard to get a full understanding only from the specification of the communication protocol. To solve this, a reverse engineering way is invoked. We perform testing on a validated product. The testing report is used to clarify the uncertain parts of the specification. This process is usually repeated and time consuming.
In this thesis, we propose a systematic way to do reverse engineering for communication protocols. We also developed automatic tools to experiment our theory.

Contents
Abstract
1. Introduction
1.1 Communication protocols
1.2 The reverse engineering problem for communication protocols
2. Preliminaries
2.1 The problem model of reverse engineering
2.2 Notations
3. Approach
3.1 The reverse engineering approach
3.2 Phase 1: Obtaining I/O relations
3.3 Phase 2: Generating candidates
3.4 Phase 3: Discrimination between candidates
3.4.1 Gill''s algorithm
3.4.2 Reducing the number of candidates
4. Results and Improvements
4.1 Experiment results
4.2 Improvements
4.2.1 Candidate conformance testing result feedback technique
4.2.2 Off-line simulation technique
5. Conclusions
Reference

[Chow 78]T. S. Chow, "Testing design modeled by finite-state-machines", IEEE Trans. Software Eng. Vol.4, pp. 178-186, Mar. 1978.
[Gill 62]A. Gill. "Introduction to the theory of Finite-State Machines", McGraw-Hill Book Company, 1962.
[Gone 70]G. Gonenc, "A method for the design of fault-detection experiments", IEEE Trans. Comput., vol. C-19, pp.551-558. June 1970
[Ghed 93]A. Ghedamsi, G.v.Bochmann, and R.Dssouli. "Multiple Fault Diagnostics for Finite State Machines".,Proc. Of IEEE INFOCOM, 2:6d.4.1-6d.4.10, 1993.
[Kohavi 78]Z. Kohavi, "Switching and Finite Automata Theory", McGraw-Hill, New York, N.Y., 1978.
[Log 90]L. Logrippo, R. L. Probert and H. Ural "Protocol Specification, Testing, And Verification", North-Holland, 1990
[Nai 81]Naito S., Tsunoyama M. "Fault Detection for Sequential Machines by Transition Tours", IEEE , pp. 128-143, 1981
[Richard 94]Richard J. Linn, M. Umit Uyar, "Conformance Testing Methodologies and Architectures for OSI Protocols", IEEE Computer Society Press, 1994.
[Sab 88]K.K. Sabnani et al., " A protocol Testing Procedures", Computer Networks and ISDN Systems, Vol. 15, No.4, pp.285-297, 1988
[Tarnay 91]K. Tarnay, "Protocol Specification and Testing", Plenum Press, 1991