Abstract
通訊協定一致性測試在確定一個通訊協是否與它原先所依以設計的相同。 這個通訊協定的規格是用一個有限狀態機。本論文主要是探討從有限狀態 機模型中自動產生一個長度短但能有效偵測出找出錯誤產品的問題。本論 文分為四部份。第一部份介紹基本觀念及回顧前人的結果。第二部份探討 如何利用測試序列知道一個通訊協定的實做產品所停留的狀態。通訊協定 的測試工作是由分佈在兩處的兩個測試器所協力完成。第三部份探討測試 序列所引發的兩個測試器間的同步問題，及如何產生可同步的測試序列來 解決這個問題。第四部份探討了相關的問題及將來研究的方向。在第二部 份中，我們探討了兩種狀態辨識序列：輸出入序列與獨特輸出入序列。一 個有限狀態機狀甲與狀態乙的最佳輸出入序列就是一段長度最短的輸入能 夠讓這個通訊協定在停在狀態甲與停在狀態乙時產生不同的輸出。最佳輸 出入序列可以應用於確定一個通訊協定的實做產品所停留的狀態，當我們 只知道他停在兩個狀態中的一個，但並不知道是那一個。傳統的方法來找 最輸出入序列要指數的時間。我們的方法只需要O(m*m)的時間，而m 是狀 態轉移的數目。使用傳統的獨特輸出入序列在一種最常用的測試方法，叫 UIOv方法中，會產生一個很長的測試序列。我們提出一個O(m*m*i)時間的 方法來產生一種獨特的輸出入序列。我們以Q.931 這個通訊協定作例子， 發現UIOv 方法由於使用我們所產生的獨特輸出入序列而使得測試序列的 長度縮短了12.7%.在第三部份中，我們提出了緊密式可同步測試序列及外 控式可同步測試序列來解決同步問題。傳統上，這個問題是用寬鬆式可同 步測試序列來解決。我們提出的緊密式可同步測試序列可以不只做一致性 測試更可以來做偵錯式測試。我們提出的外控式測試序列不只可用於遠端 測試序統，更可用於分散式測試系統。我們分別提出低階多項式時間的演 算法來產三種可同步測試序。 The objective of protocol conformance testing is to establish if a protocol implementation con- forms to the specification. The objective of this dissertation is to study some problems of generating test sequences from the protocol specification. The protocol specification is modelled a deterministic finite state machine (FSM). The disseration consists of four parts. The first part review some backgrounds. The second part concerns with the algorithms to compute two state-distinguishing sequences: Input/output (IO) sequence and Unique Input/ Output( UIO) sequence. An optimal IO sequences for state J and state K of an FSM is a shortest sequence of inputs which cause the FSM in these two states to generate a distinct sequence of outputs. We propose an O(m*m) algorithm to compute all optimal IO sequences, improved from an earlier result of exponential time, where m is the number of transitions. Using trad- itional UIO sequences with a popular test sequence generation method (called the UIOv method) yields a long test sequence. We propose an O(m*m*i) algorithm to generate a special set of UIO sequences, where i is the distinct input numbers. Using these UIO sequences with the UIOv method yields a shorter test sequence. Exper- imentation of the Q.931 protocol shows a result of 12.7% shorter. The third part is concerned with synchronizable test sequences to be used in a remote testing system. Eariler, exponential-time algorithms are proposed to generate loosely synchronizable test sequence. We propose tightly and externally synchronizable test sequence for diagnostic testing and for used in a distributed testing systems. We propose low-order polynomial time algorithms to compute the three synchronizable test sequences. The fourth part is concerned with other related topics.