基于ＣＦＳＭ的一致性測試序列生成方法

摘要：本文采用通信有限狀態機模型描述通信協議，基于通信有限狀態機模型提出了協議一致性測試的測試序列生成方法，解決了構件化協議的測試序列生成的問題。本文實現了測試序列的生成算法，通過實例說明了采用測試序列生成算法生成了比傳統算法更少的測試序列。同時本算法還可以用于多層協議測試。

關鍵詞：有限狀態機；通信有限狀態機；一致性測試

中圖分類號：TP301文獻標識碼：A文章編號：1009-3044(2008)25-1589-03

Test Sequence Generation Method For Protocol Conformance Test Based CFSM

LI Xi-he1， HU Zong2

(1. College of Network Education， Northwest Normal University， Lanzhou 730070， China; 2. College of Education， Ningbo University， Ningbo 315211， China)

Abstract: This paper proposes test sequence generation method for protocol conformance test based Communication Finite State Machine (CFSM). The algorithm solved test sequence generation problem of component-based protocol. This paper implements the test sequence generation algorithm， and an example shows the use of test sequence generation algorithm generated the short number of test sequence. In addition， the algorithm also can be used for multi-protocol testing.

Key words: Finite State Machine (FSM); Communication Finite State Machine (CFSM); Protocol Conformance Test

1 引言

協議一致性測試是測試被測協議實現（IUT）與協議規范是否一致。目前對協議的形式化描述較多的是采用有限狀態機（FSM）模型和擴展有限狀態機（EFSM）模型，相關內容見[1，4]。構件化協議就是將某個協議分解成具有相對獨立功能的完整交互規則的協議構件，通過協議構件的組合實現原來協議的功能。采用構件化的思想分析協議規范后的協議就由多個構件有限狀態機和有限狀態機之間的交互數據或者信號組成，成為了一個通信有限狀態機（CFSM）。

本文中就是基于通信有限狀態機模型研究構件化協議的測試序列生成問題，提出了構件化協議一致性測試的測試序列自動生成算法，解決了在多狀態機下協議一致性測試的問題。在生成構件化協議一致性測試的測試序列自動生成算法的基礎上，通過一個實例說明了本文的方法可以解決對實際中較為復雜的協議的一致性測試問題。

2 基于通信有限狀態機一致性測試的相關研究

2.1 通信有限狀態機定義

定義1 通信有限狀態機模型

一個通信有限狀態機(Communicating Finite State Machine:CFSM)N是由狀態機集合M和通信通道集合C組成N=(M，C)，其中：

M = {M1，M2，…，Mn}是有限個數的有限狀態機集合；

C = {Cij ∶ j≤n且i≠j}是有限個數的通道集合；

定義2 內部事件

通信有限狀態機中一些在FSM之間交換的輸入和輸出數據或者信號，本文FSM變遷中可以接收內部交互信號的輸入事件或者可以發送內部交互信號的輸出事件，稱為內部事件。

定義3 外部事件

通信有限狀態機中，FSM的變遷中可以接收協議外部PDU或者ASP的輸入事件或者可以發送協議外部PDU或者ASP的輸出事件，稱為外部事件。

2.2 相關研究

許多系統可以被抽象為CFSM，CFSM中的FSM并發執行而且FSM之間通過輸入隊列來通信。CFSM表示了規范的控制結構，可以用狀態圖或者SDL語言來描述。

在[2-3]中討論了變遷和狀態的測試問題，其中提出了一種CFSM下的狀態驗證序列。

3 基于通信有限狀態機的一致性測試序列生成方法

基于CFSM的一致性測試序列生成的一種簡單的測試方法就是將各個狀態機組合成為一個狀態機，就可以用已有的算法生成測試序列。但是這樣做會使狀態機急劇增大，構件的數目較多時會造成狀態爆炸。本文采用的的算法是直接通過CFSM模型中生成測試序列。

3.1 測試序列自動生成算法

在通信有限狀態機中生成測試序列的問題有：由于將多個有限狀態機組合成為乘積狀態機會引起狀態爆炸問題；其次由于在測試時，內部變遷無法被一個測試者觸發和觀察到。本文提出了一種基于通信有限狀態機的測試序列生成方法，可以解決或者簡化在測試通信有限狀態機中存在的問題。

以下提出了采用變遷游歷法生成的測試序列算法。為了檢測錯誤，遍歷的基本要求每一個變遷至少一次。

基于通信有限狀態機實現測試序列生成算法的步驟：

1) 從FSM中的初始狀態出發，采用深度優先遍歷算法遍歷通信有限狀態機的狀態變遷圖。遍歷變遷的條件是：

(a) 對于變遷中的輸入事件為協議外部交互信息的情況直接遍歷；

(b) 對于變遷中的輸入事件為協議內部交互信息的情況需要通信有限狀態機中其它變遷的輸出事件來觸發；

2) 在深度優先遍歷的過程中在以下約束條件裁減分支：

(a) 當一條路徑上出現重復變遷時（包含環路），這條路徑結束；

(b) 當兩個分枝相同，則可以裁減掉其中路徑較短的一個分枝；

3) 在1)和2)生成變遷樹的基礎上生成測試子序列；

4) 生成狀態的驗證序列，

(a) 如果驗證序列已經存在于包含某個狀態的路徑中，驗證序列不需要添加；

(b) 否則為其它狀態添加一個驗證序列；

5) 合并測試子序列，刪除一個變遷包含的內部事件，生成完整的測試序列。

算法的思路是采用分枝限界的方法，在進行深度遍歷的同時，用兩個裁剪條件來裁剪分枝。在遍歷的時候分兩種情況：對于變遷中的輸入事件為協議外部交互信息的情況直接遍歷；對于變遷中的輸入事件為協議內部交互信息的情況需要通信有限狀態機中其它變遷的輸出事件來觸發，因為當某一個狀態機中變遷的輸入事件觸發內部交互信號時，只有通過其他狀態機變遷的輸出事件才能觸發相應的內部交互信號。根據變遷的生成樹生成測試子序列，然后為各狀態機中的狀態生成驗證序列，本文采用的驗證序列是UIO序列。在生成的子序列當中合并可能包含的內部事件。當測試子序列生成之后，就可以組合成為完整的測試序列。

3.2 算法分析

設狀態機的數目為n，第i個狀態機的變遷數量為mi，狀態機的平均數量為m生成樹的平均路徑長度為deep生成樹的葉結點數量為nleaf算法的時間復雜度為O(n*m*deep*hleaf*nleaf)本算法中采用了分枝裁剪算法，所以生成樹的葉結點數目不會太多，并且算法可以在多項式時間復雜度內完成。

4 實例

本文提出的算法已經成功用C語言實現，并且完成了相關協議的一致性測試。以下舉一個例子來說明算法的執行過程，實例中的協議由兩個狀態機構成，分別為FSM1和FSM2，如圖1和圖2。

■

圖1 FSM1 圖2 FSM2

對圖中的符號作一個說明：為了方便起見，大寫字母M，N標記的輸入或者輸出表示協議和外部交互的ASP或者PDU，比如c1-t1:M1/M2中，c1-t1表示了狀態機c1中的第一個變遷t1，而M1，M2都表示和外部交互的ASP或者PDU。而小寫字母a開始的輸入或者輸出表示了狀態機之間的交互信號，比如c1-t4:a3/o1中的a3表示了一個狀態機之間的交互信號。

驗證序列采用UIO序列，生成狀態機中所有狀態的驗證序列，如表1。

表1 驗證序列

■

在生成樹中查找是否有些驗證序列已經存在于包含某個狀態的路徑中，查找的結果發現所有的驗證序列都已經存在于包含相應狀態的路徑中，所以不需要添加UIO序列。

經過以上步驟，得到了相應的測試子序列，在這個實例中生成了三個測試子序列，如表2所示。在得到三個子序列之后，對每一個子序列中的輸入輸出作調整，得到了調整以后的測試子序列。

表2 測試子序列

■

所以最終的測試序列為：M1/M2， M4/M7， M3/N1， N2/a3， N5/M5， N4/M6， M1/M2， M4/M7， M3/N1， N3/-， M1/M2， M4/M7， M3/N1， N2/-， N4/M6

測試序列的長度為15。

以實例中的CFSM為例，本文給出了乘積狀態機下的測試序列和本文的測試序列生成算法之間的狀態數量、變遷數量和測試序列長度的比較，見表3：

表3 測試序列比較

■

比較結果顯示了本文提出的測試序列生成方法在保持通信有限狀態機中狀態數目不增加的情況下產生了較短的測試序列。

5 結論

本文為了解決構件化協議的測試序列生成問題提出了基于CFSM的一致性測試序列生成算法，用C語言實現了該算法，并分析了算法的時間復雜度。通過一個實例來說明算法的執行過程，分析了測試序列，并且和乘機狀態機中的測試序列進行比較，說明了本文提出的測試序列生成方法可以生成較短的測試序列。

本文提出的基于CFSM的一致性測試序列生成算法解決了在多狀態機下協議一致性測試的問題，適用于可以進行構件化分析的協議，而且可以應用于對多層協議的測試。

參考文獻：

[1] C. Bourhfir， El M. Aboulhamid， R. Dssouli， N. Rico. A test case generation approach for conformance testing of SDL systems[J]. Computer Communications， 2001，24(3-4):319-333.

[2] R.M.Hierons， Testing from semi-independent communicating finite state machines with a slow environment[J]， IEE Proceedings on Software Engineering， 1997，(144):291-295.

[3] R.M.Hierons， Checking States and Transitions of a set of Communicating Finite State Machines[J]， Microprocessors and Microsystems， 2001，31(24):443-452.

[4] G.M. Lundy， C. Basaran. Automated generation of protocol test sequences from formal specifications[C]， Network Protocols 1994 International Conference， 1994，9:25-28，72-79.