Abstract
通訊協定是用來協調各電腦之間通訊連接的規定，而通訊協定一致測試( Protocol Conformance Testing)是測試各通訊協定之實作(Impl- ementation)是否符合原本所定的規則(Specification)的過程。事實上， 各通訊協定之實作可看成是一個黑盒子，我們將各測試序列輸入至黑盒子 中，觀察其輸出，若其輸出符合原本規則應有的輸出，則這一個通訊協定 的實作是正確的，否則，此通訊協定的實作是錯誤的。目前，有許多產生 測試序列的方法被提出，如：T-, D-, U-, Uv-, W-, Wp- 方法，但無論 這些方法所產生的測試序列能發現錯誤的能力是多麼的好，我們最終的結 果都只能知道這個通訊協定的實作是有錯的，但卻無法知道它錯在哪裡。 一九九三年A.Ghedamsi等人，提出一個診斷的方法，它包括了三個步驟： 第一，它利用T-, D-, U-, Uv-, W-, Wp-方法的任何一種方法去產生一個 測試序列的集合，將此一集合輸入通訊協定的實作，以便得知這實作是否 符合原本的規則。第二，利用第一步驟的輸出經過處理將會得到一群可能 會是通訊協定的實作的有限狀態機的集合，稱之為診斷群(diagnoses set )。一個診斷(diagnnosis)就是一個可能會是通訊協定的實作的有限 狀態機。第三步驟，額外在產生一些測試序列用來測試由第二步驟所得到 的集合與原本通訊協定的實作之間的相符性，並將不符的診斷( diagnosis)由診斷群中移去，最後將會得到與通訊協定的實作相符的有限 狀態機，由此就可以得知這實作與原本規則不同處在哪？而得知其錯誤的 地方。本篇論文就是改進Ghedamsi的第二與第三個步驟，使它處理起來速 度更快、節省更多處理的時間，並省略一些不必要的測試及中間值。改進 的第二步驟中，我們會產生與Ghedamsi相同的診斷群，但產生一些遠比 Ghedamsi少的中間值。 Consider a protocol specification S and a faulty implementa- tion I, the objective of diagnostic testing is to locate the faults of I. Recently, A. Ghedamsi et al. proposed a 3-phase method for diagnostic testing: 1) Obtain expected outputs of S and observed outputs of I by applying a set of test cases, which are generated by some conformance test case selection method, to S and I respective- ly. 2) Generate a minimal set D of diagnoses, which are the candi- dates of I, by analyzing the differences between the expected and observed outputs. 3) Identify which element of D is equivalent to I by applying some additional tests to I. Though their method can perform fault diagnostics successful- ly, but it is very time consuming. In this thesis, we propose two techniques to improve their method. First, we use "find-Possible-Fault" technique which will generate a behavior table as the constraint. By using this technique, we can reduce the analytical time in the second phase to obtain the same set of diagnoses. Second, we use "Test- all- Diagnoses" technique which use the test sequence to simulate all diagnoses. By using this technique, we reduce the number of tests applied in the third phase. Experimental results are also included.