建構通訊協定測試資料組之二階段演算法

Abstract

通訊協定測試是根據所建構的測試個案來驗證產品與協定描述之間的一致 性。各種以延伸的有限狀態機為描述模型的測試個案建構方法已被提出。 然而這些方法不但需要龐大的時間複雜度，而且沒有決定出測試個案中變 數的測試資料值。此篇論文對於以延伸的有限狀態機來描述的通訊協定， 提出一個建構完整測試資料組的二階段演算法。所謂的一套測試資料組是 一個測試個案加上其相對應的測試資料值。在演算法的第一階段，會根據 建構的一個非循環樹來有效地產生測試個案。這個非循環樹解決了無限迴 圈的問題，並且包含延伸的有限狀態機中的每個變數其所有的定義－使用 路徑。演算法的第二階段則利用公理語意和回溯的方法來選取適當的測試 資料值。於是完整的測試資料組就可以自動而有效率地被建構出來。 Protocol testing deals with the verification of the external behavior of an implementation against its protocol specification based on constructed test cases. Various methods of test case construction based on Exteded Finite State Machine( EFSM) models have been proposed. These methods, however, not only incur high time complexity but also are lacking in the determination of the test data for the variables in test cases. This thesis proposes a two-phase algorithm for the construction of a complete set of test suites for a protocol specified by an EFSM model. Each test suite is a test case with corresponding test data augmented. The first phase of the algorithm efficiently generates all test cases based on a constructed acyclic tree. The acyclic tree resolves the infinite loop problem and contains all du-paths of each variable in a given EFSM. The second phase then performs test data selection by means of axiomatic semantics and backtracking approaches. Consequenctly, test suite can be automatically and efficiently constructed.