基于有限狀態(tài)機的協(xié)議測試方法

黃恩博　黃耿生

摘要：該文首先介紹了有限狀態(tài)機的一般理論并描述了兩種確定型有限狀態(tài)機模型，之后將有限狀態(tài)機模型引入通信系統(tǒng)中，并以GTP協(xié)議為例介紹了通信協(xié)議報文在GPRS網(wǎng)絡(luò)中流轉(zhuǎn)的過程及測試方法。

關(guān)鍵詞：有限狀態(tài)機；協(xié)議測試；通信系統(tǒng)

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2013）09-2161-05

在通信系統(tǒng)建模中，使用著各種類型的有限狀態(tài)機，每個有限狀態(tài)機都有一個狀態(tài)集合（包括初始狀態(tài)）和一個輸入集合表，還有一個轉(zhuǎn)化函數(shù)，它對每個由狀態(tài)和輸入條件構(gòu)成的序列，指定了下一個狀態(tài)。有限狀態(tài)機作為經(jīng)常使用的一個抽象機器模型，被廣泛的使用在通信網(wǎng)絡(luò)中，是一個進(jìn)行系統(tǒng)建模的有力工具。

本文從有限狀態(tài)機的一般理論出發(fā)，以GTP協(xié)議為例介紹和描述了有限狀態(tài)機模型及基于它的協(xié)議測試方法。

1 確定型有限狀態(tài)機

確定型的有限狀態(tài)機是指針對一個可能的輸入，只有一個狀態(tài)的遷移，非確定的有限狀態(tài)機是對每一個可能的輸入可以有多個狀態(tài)遷移，接收到輸入時候從中多個狀態(tài)轉(zhuǎn)移中非確定的選擇一個。

下面介紹它的兩種模型。

1.1 帶輸出的有限狀態(tài)機模型

一個有限狀態(tài)機的形式化定義是這樣：一個確定的有限狀態(tài)機M：

S是一個有限的狀態(tài)集合；

I是一個有限的輸入字母表；

O是一個有限的輸出字母表O；

一個狀態(tài)轉(zhuǎn)移函數(shù)f為每個狀態(tài)和輸入對指派一個新的狀態(tài)；

一個輸出函數(shù)g為每個狀態(tài)和輸入對指派一個輸出，還有一個初始狀態(tài)s0。

下面以一個狀態(tài)圖來進(jìn)行說明：

有限狀態(tài)機是抽象出來的一個數(shù)學(xué)模型，與現(xiàn)實世界比較，通過很多理想的假設(shè)來簡化系統(tǒng)設(shè)計的復(fù)雜程度。比如，假設(shè)系統(tǒng)的幾個狀態(tài)是可以窮舉的，即可以認(rèn)為在行為上是固定的。當(dāng)系統(tǒng)從一個狀態(tài)通過條件變化遷移到另外一個狀態(tài)，遷移是很迅速并且一次有效的。

為了建模的需要，人們開發(fā)了各種不同類型的有限狀態(tài)機模型，主要應(yīng)用的模型有Mealy狀態(tài)機和Moore狀態(tài)機。在Mealy狀態(tài)機模型中，對一個轉(zhuǎn)移都附加有輸出動作，Moore 狀態(tài)機對每一個狀態(tài)都有附加輸出動作。

1.2 不帶輸出的有限狀態(tài)機

不帶輸出的有限狀態(tài)機是用來作為識別語言而設(shè)計的。這些機器不產(chǎn)生輸出，但是有終止?fàn)顟B(tài)。

一個有限狀態(tài)機的形式化定義是這樣：一個確定的有限狀態(tài)機M：

S 是一個有限的狀態(tài)集合；

I 是一個有限的輸入字母表；

f是一個狀態(tài)轉(zhuǎn)移函數(shù)，為每個狀態(tài)的輸入對指派下一個狀態(tài)；

s0 是一個初始裝態(tài)；

F是一個由終結(jié)狀態(tài)構(gòu)成的S的子集。

不帶輸出的有限狀態(tài)機可以用一個狀態(tài)圖來表示，在狀態(tài)圖中，終結(jié)狀態(tài)用雙圈表示。

前面討論的有限狀態(tài)機都是確定型的，因為對于每對狀態(tài)和輸入值，轉(zhuǎn)移函數(shù)只給出唯一的下一個狀態(tài)。而非確定有限狀態(tài)機模型，它對每隊輸入和狀態(tài)，有多個可能的下一個狀態(tài)。

一個狀態(tài)集合S，一個輸入字母表I，一個轉(zhuǎn)移函數(shù)f為每個狀態(tài)和輸入對指定下一個狀態(tài)集合，一個初始狀態(tài)s0，和一個由終結(jié)狀態(tài)構(gòu)成的S的子集F。

非確定型狀態(tài)機和確定型狀態(tài)機的唯一區(qū)別就是他們的轉(zhuǎn)移函數(shù)不同，確定型有限狀態(tài)機的輸入只有一個狀態(tài)的轉(zhuǎn)移，非確定型狀態(tài)機可以有多個狀態(tài)轉(zhuǎn)移。非確定型狀態(tài)機可以轉(zhuǎn)化成確定型狀態(tài)機。

2 通信系統(tǒng)中的有限狀態(tài)機

在GPRS網(wǎng)絡(luò)中，同一個公眾陸地移動網(wǎng)（Public Land Mobile-communication Network，以下簡稱PLMN）中的GPRS支持節(jié)點（GPRS Support Nodes，以下簡稱GSN）節(jié)點，比如GGSN節(jié)點和SGSN節(jié)點，都采用GTP協(xié)議進(jìn)行數(shù)據(jù)傳輸，并采用GTP協(xié)議進(jìn)行隧道管理。所謂隧道管理就是承載在GTP協(xié)議上的PDP（Packet Date Protocol）報文的激活、更新、分離等一系列的過程。PDP的管理也是GTP-C和GTP-U的一個重要功能。在GTP隧道管理中，系統(tǒng)之間的狀態(tài)主要是在PDP上下文的創(chuàng)建、更新、刪除等狀態(tài)之間進(jìn)行轉(zhuǎn)移的。

在圖3中，PDP上下文有ACTIVE，CREATE，UPDATE，DELETE，IDLE等五個狀態(tài)，每個狀態(tài)之間的遷移需要一定的條件。從IDLE狀態(tài)不能直接遷移到DELETE，中間必須經(jīng)過一個CREATE狀態(tài)的轉(zhuǎn)移，從CREATE狀態(tài)也不能直接遷移到UPDATE狀態(tài)，因為PDP報文的UPDATE動作是在PDP的傳輸隧道建立之后才能發(fā)送，而建立PDP 隧道是需要進(jìn)行ACTIVE動作，同樣的道理，從IDLE狀態(tài)也不能直接遷移到UPDATE狀態(tài)。

當(dāng)測試系統(tǒng)開啟之后，由于沒有加載測試用例，系統(tǒng)處于IDLE狀態(tài)，即空閑狀態(tài)，此時沒有測試用例通過TTCN-3系統(tǒng)來完成，如果在IDLE狀態(tài)之后執(zhí)行TTCN-3中的初始化動作，即創(chuàng)建主測試成分（Main Testing Component，以下簡稱MTC）、并行測試成分（Parallel Test Component，以下簡稱PTC）、測試端口、配置參數(shù)、連接測試系統(tǒng)和通信端口、連接各個測試端口和測試端口，那么此時系統(tǒng)狀態(tài)則轉(zhuǎn)移到CREATE，此時表明PDP報文初始化已經(jīng)完成但是現(xiàn)在還沒有被真正執(zhí)行，條件RE_START/stInitCreate是指初始化發(fā)送序列的條件。

當(dāng)系統(tǒng)處于CREATE狀態(tài)時候，經(jīng)過一個激活的操作過程，可以到達(dá)ACTIVE狀態(tài)。由ACTIVE狀態(tài)可以遷移到UPDATE狀態(tài)，也可以由UPDATE狀態(tài)遷移到ACTIVE狀態(tài)。由ACTIVE狀態(tài)也可以直接遷移到DELETE狀態(tài)，這個代表系統(tǒng)激活了PDP報文，成功創(chuàng)建了PDP隧道，但是沒有發(fā)送數(shù)據(jù)量，然后直接刪除PDP隧道，直接退出測試系統(tǒng)。

下面分別將各個狀態(tài)時候的系統(tǒng)狀態(tài)進(jìn)行描述一下。

2.1 CREATE狀態(tài)

一個PDP的CREATE的過程是由IDLE過程遷移而來，CREATE的過程主要是創(chuàng)建并初始化通信端口，并把通信端口和測試系統(tǒng)通過MAP映射進(jìn)行連接，或者是端口之間通過CONNECT操作連接。初始化的過程也包括一些常用協(xié)議的初始化操作，由于被測試系統(tǒng)是GGSN，GGSN的周邊的接口有Gx，Gy，Gz，所以在CREATE的過程中，針對不同的測試端口需要進(jìn)行不同的初始化操作，比如數(shù)據(jù)報文發(fā)送在Gx接口，與之相對應(yīng)的是Gx接口上的DIAMETER協(xié)議，那么需要進(jìn)行Gx接口的初始化并初始化DIAMETER協(xié)議的TTCN-3模板，在Gy接口上進(jìn)行測試，需要初始化的是Gy接口，并初始化GTP協(xié)議的TTCN-3模板，等。

由于在整個PDP上下文的傳輸過程中，傳輸分為GTP-C信令面和GTP-U用戶面，所以在初始化操作里需要同時對GTP-C和GTP-U的TTCN-3模板進(jìn)行初始化。

總體而言，一個CREATE過程中需要進(jìn)行的主要的狀態(tài)轉(zhuǎn)移過程如下：

Step 1.初始化MTC，主要是運行在MTC上的一些通信端口參數(shù)；

Step 2.初始化Gi接口，因為Gi接口是GTP協(xié)議主要的通信接口，承載SGSN和GGSN之間的控制信令和用戶信令的數(shù)據(jù)傳輸，所以第一個應(yīng)該初始化并且探測Gi接口時候已經(jīng)初始化成功，如果沒有，則可以遷移到DELETE狀態(tài)，表示初始化失敗，清除原先操作。

Step 3.初始化DHCP（Dynamic Host Configuration Protocol）服務(wù)，進(jìn)行動態(tài)域名配置，主要是把MS請求的APN名字轉(zhuǎn)化成IP地址，并作動態(tài)分配；如果DHCP初始化成功，則遷移到step 4.否則，遷移到DELETE狀態(tài)，表示初始化失敗，清除原先操作。

Step 4.初始化RADIUS（Remote Authentication Dial In User Service）服務(wù)，如果RADIUS初始化成功，則遷移到step5，否則，遷移到DELETE狀態(tài)，表示初始化失敗，清除原先操作。

Step 5. 初始化Gz接口上CGF，并打開計費端口，否則遷移到step3，重新開始。

當(dāng)以上步驟都完成后，PDP的運行環(huán)境由INIT遷移到ACTIVE狀態(tài)，表示各種環(huán)境已經(jīng)配置，可以發(fā)送GTP報文進(jìn)行通信。

2.2 ACTIVE狀態(tài)

如圖4所示：

當(dāng)PDP報文經(jīng)過CREATE過程后，PDP的狀態(tài)遷移到ACTIVE狀態(tài)，ACTIVE表明現(xiàn)在已經(jīng)初始化了PDP的運行環(huán)境并創(chuàng)建了PDP，現(xiàn)在PDP處于激活狀態(tài)，可以通過通信端口發(fā)送數(shù)據(jù)報文。

由ACTIVE狀態(tài)可以遷移到UPDATE狀態(tài)，表明GTP-C協(xié)議在信令面成功創(chuàng)建PDP隧道之后，當(dāng)PDP 上下文請求的Qos需要更改、GTP 信道發(fā)生變化、GTP的傳輸?shù)陌姹居蓈0改變?yōu)関1時，由GSN中的節(jié)點SGSN發(fā)送更新PDP請求，此時如果GGSN反饋的是請求接受的消息，則測試行為成功遷移到UPDATE狀態(tài)。

一個ACTIVE狀態(tài)遷移到DELETE狀態(tài)的原因有兩點：一是因為一次成功的測試已經(jīng)完成，PDP報文的GPT-C和GTP-U報文已經(jīng)發(fā)送并且成功創(chuàng)建了測試環(huán)境，測試?yán)Ｍ瓿珊笙到y(tǒng)退出；二是因為經(jīng)過ACTIVE過程PDP傳輸隧道成功創(chuàng)建之后，SGSN發(fā)送Delete PDP Context Request請求并被GGSN成功接受并反饋Delete PDP Context Response之后，系統(tǒng)狀態(tài)遷移到DELETE。

由ACTIVE過程到GTPU_REBUILD狀態(tài)并不是一個狀態(tài)過程的遷移，在圖中出現(xiàn)的原因是表明在PDP 隧道創(chuàng)建成功之后，對于同一個手機基站MS（Mobile Station）而言，在一個PDP隧道里面可以進(jìn)行多次的GTP-U報文的傳輸，只要用稱作為TEID的字段和NSAPI字段進(jìn)行標(biāo)識即可，這個也符合在GPRS網(wǎng)絡(luò)中的電路交換原理，GTP協(xié)議把信令面和用戶面進(jìn)行了分離，即分離成GTP-C和GTP-U，一次信令面表明的是隧道建立，傳輸，釋放等控制，但是在隧道中傳輸中采用用戶面的GTP-U報文，做到了一次創(chuàng)建，多次使用。

2.3 UPDATE狀態(tài)

UPDATE狀態(tài)是由ACTIVE狀態(tài)轉(zhuǎn)移過來，ACTIVE狀態(tài)是進(jìn)入UPDATE狀態(tài)的唯一前趨狀態(tài)，PDP報文只有在成功發(fā)送了ACTVIE激活流程之后才能進(jìn)行更新操作，DELETE是UPDATE狀態(tài)的唯一后趨狀態(tài)，表明在經(jīng)過UPDATE狀態(tài)之后，系統(tǒng)運行測試用例結(jié)束，通過DELETE狀態(tài)清除原先的配置操作，歸還請求的處理機請求并釋放資源。

UPDATE的過程主要是由SGSN發(fā)送Update PDP Context Request 并且GGSN發(fā)送Update PDP Context Response響應(yīng)消息，表明MS請求的PDP更新請求得到GGSN的同意，然后可以進(jìn)行數(shù)據(jù)量的傳輸，在傳輸數(shù)據(jù)信息的過程中，采用的是GTP-U協(xié)議。

2.3 DELETE狀態(tài)

進(jìn)入DELETE的狀態(tài)主要是做系統(tǒng)清理工作，比如關(guān)閉在通信過程中的測試端口，關(guān)閉SACC（Service Aware Charging and Control），關(guān)閉DHCP通信連接，關(guān)閉RADIUS的通信連接，等等。其主要過程可以用圖6狀態(tài)圖來表示。

3 結(jié)束語

本文介紹了有限狀態(tài)機的基本概念和相關(guān)理論，主要分析了有限狀態(tài)機中的確定性有限狀態(tài)機，結(jié)合實例說明了確定性有限狀態(tài)機的兩種理論模型，即帶輸出的有限狀態(tài)機模型和不帶輸出的有限狀態(tài)機模型，并根據(jù)有限狀態(tài)機的狀態(tài)遷移圖來講述了在一個GTP報文從INIT狀態(tài)，經(jīng)過ACTIVE、UPDATE、DELETE狀態(tài)，最后退出到IDLE狀態(tài)的各個過程以及在各個狀態(tài)轉(zhuǎn)換中進(jìn)行測試的方法。

參考文獻(xiàn)：

[1] Myers G J.The art of software of testing[M].New Jersey：John Wiley and Sons，2004.

[2] Hopcroft J E，Motwani R，Ullman J D.Introduction to Automata Theory， Languages and Computation[M].2nd ed.Addison-Wesley，2001.

[3] Hoare C A R.Communicating Sequential Processes[J].Communications of the ACM，1978，21（8）.

[4] Kwang Ting Cheng，Krishnakumar A S.Automatic functional test generation using the extended finite state machine model[C]. New York， NY， USA：DAC'93 Proceedings of the 30th international Design Automation Conference ACM，1993： 86-91.

[5] ETSI ES 201 873-1 v2.2.1.Methods for Testing and Specification （MTS）；The Testing and Test Control Notation version 3；Part1：TTCN-3 Core Language，27-28[S].2003.

[6] Newkirk J W，Vorontsov A A.Test-Driven，Developmentment in Microsoft .NET[M].Microsoft Press，2004.

[7] Astels D.Test-Driven Developmentment：A practical Guide[M]. Prentice Hall，2003.