通訊協定的符合性測試與錯誤診斷

Abstract

為了連結異值性電腦系統，網路通訊協定已變得愈來愈複雜，每個廠商的 通訊產品為了正常運作，也應該被完整的測試來驗證它是否與相關通訊協 定規格完全符合，這正是所謂的符合性測試（conformance testing）； 而錯誤診斷（fault diagnosis）則更進一步的指出來待測產品的實作錯 誤位置。為了有效率的執行符合性測試與錯誤診斷，這篇論文主要在解決 三個相關議題：分別是狀態驗證（state verification）的最小化、同質 性（homogeneous）有限狀態機（Finite State Machine,FSM）的最小化 、與遠地測試器的同步問題（synchronization problem）。首先，由於 待測物一班被視為「黑箱」，亦即擁有許多不可見的內部狀態，所謂的狀 態驗證，也就是要推導出一組輸入/輸出序列（Input/Output sequence） 來測試待測物（Implementation Under Test, IUT）是否正處於某特定狀 態，雖然「唯一輸入/輸出序列（Unique Input/Output sequence）」被 公認為狀態驗證領域中一個非常有效率的方法，但不幸的是，並非每一個 通訊協定的內部狀態都有對應的唯一輸入/輸出序列，針對那些沒有唯一 輸入/輸出序列的內部狀態，則使用另一個測試序列--及狀態簽章（ signature）來替代。本論文的第一個研究成果即是提出一個產生最小化 狀態簽章的有效率方法。其次， 通訊協定規格通常被正規化描述成有限 狀態機，針對那些有單一狀態轉移錯誤（transfer error）的實作系統， 為了明確指出它的錯誤位置，所有可能的錯誤實作方法所對應的一整組有 限狀態機都必須先作最小化後再進行彼此間的交叉驗證。如果直接運用單 一有限狀態機最小化方法逐個將所有的有限狀態機最小化，這樣的方法由 於沒有善用整組有限狀態機彼此間的同質性（Homogeneity），而變得沒 有效率。所以本論文的第二個研究成果即是提出一個兩階段的最小化方法 來有效率的將一整組有限狀態機同時做最小化。由實驗結果顯示，針對許 多被實際使用中的通訊協定而言，此方法將最小化的複雜度明顯降低。最 後，當我們將由通訊協定規格所推導出來的測試序列（testing sequence ）實際拿到由兩個以上相隔遙遠的測試器（remote tester）所構成的測 試環境-亦即所謂的多單元測試架構（multi-party configuration）中使 用時，可能會產生測試器同步問題。此問題產生的原因是由於測試器分散 各地，雖然測試序列已經規範測試程序，但由於某個測試器並不知道待測 物是否已先送出訊息到另一個遠地測試器，因此無法判斷正確的時間來送 出下一個訊息。所以本論文的第三個研究成果即是提出一個解決測試器同 步問題的機制（synchronization paradigm），來巧妙的融合「自發性同 步序列（self-synchronizable sequence）」與「外在同步動作（ external synchronization operation）」兩種技術。為了顯現它的優越 性，本論文套用此機制來產生兩種同步測試序列：亦即同步前置序列（ synchronizable preamble）與同步狀態區隔序列（synchronizable distinguishing sequence），而這兩種測試序列透過精巧的配合使用， 已經被證明可以測試通訊協定的每一個內部狀態轉換是否正確。 Evolution of communication networks has led toward increasingly complexprotocols to interconnect heterogeneous system.In order to functionproperly,individual vendor's implementation should be tested to verifythat it conforms to the relevant protocol specification,i.e.,conformancetesting. Moreover, fault diagnosis further identifies the location of the implementation faults. For efficientlyu executing the conformance testing and fault diagnosis, this thesis aims at solving three related problems: minimum-length state verification, homogeneous Finite State Machines(FSMs) minimization, and distanced testers synchronization,respectively.First, since an Implementation Under Test(IUT) is typically regarded as black box, state verification is then related to the problem of derivingan input/ output sequence which can be used to determine if the IUT iscurrently in a particular state. Although the approach of the UniqueInput/Output (UIO) sequence has been utilized as an efficient techniquefor state verification, some states in a protocol, however, may possessno UIO sequences. A substitute method of the input/output sequence, called a signature, for a state without a UIO sequence is thus employed. The first goal of the thesis is to propose an efficient algorithm of constructing the minimum-length signature. Second, to identify potentialfaulty implementations caused by a transfer error in the protocolspecification, cross verification over the corresponding FSMs is performedafter all potential faulty FSMs have been minimized. Existing minimizationalgorithms become inefficient due to the lack of taking advantage of the homogeneity of these potential faulty FSMs. The second goal of the thesis is to propose a two-phase algoritm for the efficient and simultaneous minimization of a set of homogeneous faulty FSMs. Experimental resultsshow that the algorithm renders the minimization complexity greatly reduced for most relistic protocol FSMs. Finally, conformance testing may lead tothe synchronization problem should predetermined test sequences be appliedto multiple distanced testers, namely under the multi- party configuration.The third goal of the thesis is to propose a novel synchroniation paradigmwhich seamlessly unifies two synchronization techniques, theself-synchronizable wequence and the external synchronization operation.To demonstrate the viability of the proposed paradigm, the thesis also presents the generations of two synchronizable sequences, namely thesynchronizable preamble and the synchronizable distinguishing sequence,which have previously been used for the testing of the correctness of a protocol's transition.