Abstract
通訊協定是用來指揮協調各電腦之間通訊連接的規定，要確保各通訊協定 的成品是否符合其該有之規格的測試學問，稱之為通訊協定之一致性測試 。事實上，各通訊協定的成品可看做是一個黑盒子，我們將各測試序列輸 入至黑盒子中，觀查其輸出，若輸出符合其規格該有之輸出，則這一個通 訊協定的成品是正確的，反之則此通訊協定的成品是有錯誤的。目前已有 多種通訊協定之一致性測試的理論被提出來，這些理論多基於通訊協定之 規格可以由有限狀態機來描述的假設所發展。然而實際上因有限狀態機先 天上的限制其對所有的通訊協定並非全然適用，延伸有限狀態機之模式於 是被提出以彌補其不足。所謂延伸有限狀態機顧名思義即是有限狀態機之 延伸，它比有限狀態機模式多了對變數的操作及述語的判斷，由於在延伸 有限狀態機中狀態之改變不只是受輸入所影響，變數的內容也同時須要考 量，因此原先在有限狀態機模式所發展的理論便無法直接套用於延伸有限 狀態機模式上，而且也使問題的難度昇高了。在通訊協定之一致性測試中 ，產生轉態旅程以便對每一個通訊協定的轉態過程能測試至少一遍之方式 是一種常用的測試方法。過去工業界為了從通訊協定之延伸有限狀態機模 式產生轉態旅程，採用了兩種策略，其分別是直接將延伸有限狀態機視為 有限狀態機及將延伸有限狀態機以自動方式展開成有限狀態機，最後再以 有限狀態機的理論求得轉態旅程。但是兩者皆有其缺陷，前者難以自動化 多以半自動收場而後者則因展開後的有限狀態機大而無當降低了其所產生 出的測試序列之效率。在本論文中，我們首先證明了要從延伸有限狀態機 獲取最短長度的轉態旅程是一個 NP-hard 的問題，接著提出一個具導向 的隨機漫游之演算法則來獲得延伸有限狀態機之轉態旅程。從我們對 ISO Class 4 Transport Protocol 所進行的實驗中，其數據顯示了我們 的演算法則所產生的測試序列之長度為過去從由延伸有限狀態機展得的有 限狀態機所得之測試序列長度的五分之二。