王 瑞，梁 艷

（1.中國鐵道科學(xué)研究院 通信信號研究所， 北京 100081 2.卡斯柯信號有限公司 城交部，北京 100045）

高速鐵路列車運行控制系統(tǒng)，其系統(tǒng)內(nèi)部、系統(tǒng)與外界環(huán)境之間存在大量復(fù)雜的數(shù)據(jù)交互，這就依賴于高容量的傳輸系統(tǒng)進行數(shù)據(jù)傳輸[1]。其中，鐵路信號安全協(xié)議-I（以下簡稱RSSP-I）為鐵道部制訂的用于列控系統(tǒng)封閉網(wǎng)絡(luò)中的安全數(shù)據(jù)傳輸協(xié)議，是保證信息安全實時傳遞的有效手段，對整個系統(tǒng)安全起著重要作用[2]。

在協(xié)議實現(xiàn)投入運行之前，對其進行完整的測試可以保證協(xié)議有效安全地投入應(yīng)用。協(xié)議測試包括一致性測試、互操作性測試、性能測試和魯棒性測試，其中的互操作性測試就是檢查同一協(xié)議或者同一類協(xié)議的不同被測實現(xiàn)之間是否可以進行正確的交互，提供期望的服務(wù)，它是對一致性測試的完善和補充。

自然語言描述的協(xié)議說明可能具有二義性或者存在可選選項，一致性測試無法做到窮盡測試，故對產(chǎn)品進行互操作性測試是必要的[3]。在不同廠家的產(chǎn)品之間進行互操作性測試，可以降低系統(tǒng)集成的費用，提高設(shè)備的利用率，保證系統(tǒng)的良好運行。

1 互操作性測試的形式化模型

為了生成協(xié)議的互操作性測試序列，需要對協(xié)議說明進行形式化建模，可以用有限狀態(tài)機對協(xié)議的行為進行形式化描述。有限狀態(tài)機FSM，M是一個五元組(S, s0, Lin, Lout, Tr)[4]，其中：

（1）S=(s0, s1, …sn-1)表示狀態(tài)機M的狀態(tài)集合；

（2）s0∈S表示狀態(tài)機M的初始狀態(tài)；

（3）Lin=(v1, v2, …wm)表示輸入符號的集合；

（4）Lout=(U1, U2, …Uk)是輸出符號向量的集合，其中Ui=(uex, uin) ，uex表示外部輸出消息，uin表示內(nèi)部輸出消息；

（5）Tr U?{s－v/U→s'|s, s'∈S∧v∈L∧inU U?L}表示變遷的集合，其中s，s'，v ，U 分

out別表示起始狀態(tài)，終止?fàn)顟B(tài)，輸入符號，輸出符號的集合。

互操作性測試把參與測試的兩個或者多個實現(xiàn)作為整體考慮，采用組合的有限狀態(tài)機對被測協(xié)議從整體上進行形式化描述，本文中研究的是1:1的互操作性測試，用II表示2個有限狀態(tài)機的組合：MA和MB。可以這樣定義，組合的有限狀態(tài)機II是一個五元組(SII, sII,0, sII,in, LII,out, TrII)[4]：

（1）SII=(sII,0, sII,1, …sII,n-1)表示全局狀態(tài)的集合，sII,i=(sA, sB), sA和 sB分別表示 MA和MB的狀態(tài)。

（2）sII,0∈SII表示初始狀態(tài)，即sII,0=(sA,0,sB,0) 。

（3）LII,in=(vII,1, vII,2, …vII,m)表示輸入符號的集合，即，LII,in=(Lin,A,EULin,B,E) 。

（4）WII=(UII,1, UII,2, …UII,l)表示由一個外部輸入所產(chǎn)生的一系列輸出符號向量的集合，UII,i∈Lout,A∪Lout,B, UII,i+1是由UII,i的內(nèi)部輸出產(chǎn)生的，其中1≤i ≤l，并且最后一個向量UII,l的內(nèi)部輸出為空，或者雖然內(nèi)部輸出不為空，但也不會引起狀態(tài)的變遷。 LII,out=(WII,1, WII,2, …WII,k)是一系列輸出符號向量的集合。

（5）TrIIsII－v/U→sII'|sII, s'∈S∧IIIIIIIIIIIIII

v∈LII,in∧UU?LII,out}表示變遷的集合。

2 互操作性測試序列的生成算法

本文的互操作性測試生成算法中，主要基于單激勵原則，即被測系統(tǒng)在同一時刻只有一個外部激勵，且在系統(tǒng)處于穩(wěn)定狀態(tài)時給入，只有當(dāng)被測系統(tǒng)處理完該激勵時，外部才能輸入下一個激勵。同時，還假設(shè)要進行互操作性測試的被測實現(xiàn)已經(jīng)經(jīng)過了一致性測試[5]。

組合的有限狀態(tài)機的生成算法可以產(chǎn)生互操作性測試套，對給定輸入存在多少信息交互，或?qū)ν惠斎氪嬖诙嗌僮冞w都普遍適用。該算法中，首先要做全局變量的初始化工作：LII,in=(Lin,A,EULin,B,E)，sII,0=(sA,0, sB,0)，SII={sII,0}, TrII:={}。然后，從組合的有限狀態(tài)機的初始狀態(tài)States（初始化為sII,0）開始，通過函數(shù)choose-any()從States中任選一個狀態(tài)gs_i作為當(dāng)前狀態(tài)，對于gs_i的每一個外部輸入v，求出當(dāng)前狀態(tài)在輸入v時的下一個狀態(tài)gs_f，從而求得新的輸出LII,out和TrII。把新狀態(tài)gs_f并入SII和States中，可以得到新的狀態(tài)集SII和States。為了得到gs_i和gs_f的內(nèi)部交互序列，引入子函數(shù)interoperabilityderive (in, s, s', gs_i, v,W )，它是一個遞歸調(diào)用的函數(shù)，能夠生成一個互操作性測試例。其算法流程圖如圖1所示。

圖1 組合的有限狀態(tài)機的生成算法流程圖

3 RSSP-I協(xié)議的形式化模型建立

RSSP-I規(guī)定了鐵路信號安全設(shè)備之間進行信息交互的安全層功能結(jié)構(gòu)和協(xié)議，實現(xiàn)數(shù)據(jù)通信，適用于封閉式傳輸系統(tǒng)。該協(xié)議依照封閉式傳輸系統(tǒng)安全通信標(biāo)準 EN50159-1制定，采用從接收方角度設(shè)計的保護算法，能夠獨立檢測通信傳輸中的所有錯誤，采取相應(yīng)的故障安全防范措施。

RSSP-I協(xié)議中用了3種數(shù)據(jù)幀：RSD（實時安全數(shù)據(jù)幀），SSE（時序校正請求幀）和SSR（時序校正應(yīng)答幀），其安全數(shù)據(jù)交互示例如圖2所示。

圖2 RSSP-I安全數(shù)據(jù)交互示例

為生成RSSP-I的互操作性測試序列，需要建立該協(xié)議的發(fā)送方和接收方的有限狀態(tài)機模型。由于RSSP-I協(xié)議是基于接收方的保護算法，發(fā)送方是主動的，而接收方作為跟隨方是被動的，通信鏈路的建立和刪除過程都是由發(fā)送方?jīng)Q定的。因此，本文在建立模型時，為發(fā)送方設(shè)計比較多的外部輸入，而接收方只有內(nèi)部輸入，完全跟隨發(fā)送方。

首先，需要確定發(fā)送方和接收方的狀態(tài)機集合。發(fā)送方模型的狀態(tài)集：S1={IDLE , WaitSSE ,DelaySSR, DATA }， 其中，IDLE表示鏈路不存在或者已刪除，默認的初始狀態(tài)；W aitSSE表示等待接收方的時序校正請求SSE；DelaySSR表示本方延遲發(fā)送時序校正應(yīng)答SSR；DATA表示發(fā)送實時安全數(shù)據(jù)幀RSD；建立接收方模型的狀態(tài)集S2={IDLE, READY , WaitSSR, DATA }。

在觸發(fā)發(fā)送方模型和接收方模型的狀態(tài)轉(zhuǎn)化過程中，需要有相應(yīng)的輸入/輸出事件。其中外部輸入包括：Setup1正常啟動發(fā)送方；Setup2啟動發(fā)送方異常（不能及時發(fā)送SSR）；Conn鏈路連接正常；Disconn斷開鏈路、SSRTim eout發(fā)送SSR超時；RSDDelay發(fā)送RSD延遲等。外部輸出包括：Start狀態(tài)機啟動；C losed鏈路斷開，回到初始狀態(tài)；D isp lay被測設(shè)備將一些發(fā)送接收數(shù)據(jù)，狀態(tài)的變化等顯示出來，方便測試者查看。內(nèi)部的輸出包括：i_RSD發(fā)送RSD；i_SSE發(fā)送SSE；i_SSR發(fā)送SSR；i_RSDe發(fā)送錯誤的RSD；i_RSDd發(fā)送延遲的RSD；i_tim eout（i_timeout1，i_timeout2）分別表示超時時間t（t1，t2）、nu ll（輸出為空）；同時一個狀態(tài)機的內(nèi)部輸出事件是另外一個狀態(tài)機的內(nèi)部輸入事件，用來觸發(fā)相應(yīng)的變遷。

本文建立的發(fā)送方模型、接收方模型如圖3和圖4所示。

圖3 RSSP-I發(fā)送方模型

4 RSSP-I協(xié)議的互操作性測試序列生成

在對RSSP-I協(xié)議進行互操作性測試的研究中，采用前面的互操作性測試套生成算法，圖5以一個RSSP-I協(xié)議中的交互實例來說明互操作性測試套的生成過程。

最開始，發(fā)送方和接收方都處于初始狀態(tài)，即：States ={（IDLE, IDLE）}。圖6介紹了圖1中的算法生成互操作性測試例的過程。

于是，就生成了第（1）條測試例，用同樣的方法可以生成下面11條互操作性測試例：

圖4 RSSP-I接收方模型

圖5 一個消息交互的例子

圖6 測試例（1）生成的具體過程

（1）（IDLE,IDLE）—Setup1/(Start, i_RSD),(Display, i_SSE),(Display, i_SSR),(Display, null) →（DATA,DATA）；

（2）(DATA,DATA)—RSDError/(Display, i_RSDe),(Display, i_SSE),(Display, i_SSR),(Display,null) →（DATA,DATA）；

（3）(DATA,DATA)—RSDDelay/(Display, i_RSDd),(Display, i_SSE),(Display, i_SSR),(Display,null) →（DATA,DATA）；

（4）(DA TA,DA TA)—Conn/(D isp lay,i_RSD),(Display, null) →（DATA,DATA）；

（5）(DATA,DATA)—D isconn/（C losed,i_timeout），（Closed, null） →（IDLE,IDLE）；

（6）(IDLE,IDLE)—Setup2/(Start, i_RSD),(Display, i_SSE),(Display, i_timeout1),(Disp lay, null)→（DelaySSR, WaitSSR）；

（7）（DelaySSR, WaitSSR）—Disconn/(Closed,i_timeout2),(Closed, null) →（IDLE,IDLE）；

（8）（DelaySSR, WaitSSR）—SSRNormal/(Display, i_SSR),(Display, null) →（DATA,DATA）；

（9）（DelaySSR, W aitSSR）—SSRTimeout/(Display,i_timeout2),(Closed, null) →(WaitSSE,IDLE);

（10）(WaitSSE, IDLE) —Conn/(D isp lay,i_RSD),(Display, i_SSE),(Display, i_SSR),(Display,null) →(DATA,DATA);

（11）(W aitSSE, IDLE) —Disconn/(Closed,i_timeout),(Closed, null) → (IDLE,IDLE)。

變遷分別叫做 T1，T2，T3，T4，T5，T6,T7，T8，T9，T10，T11。可以生成組合的有限狀態(tài)機如圖7所示。在組合的有限狀態(tài)機模型基礎(chǔ)上進行對稱擴展，得到歐拉圖如圖8所示。

圖7 RSSP-I組合的有限狀態(tài)機模型

圖8 RSSP-I組合的有限狀態(tài)機的對稱擴展

對其進行歐拉遍歷，可以得到最佳的測試序列為：T1’→ T5 →T6→ T9→T10’→ T2’→T3’→ T4→ T5→T6→T9’→T11’→T6 →T8’ T5’→ T6’→ T7’。

該測試序列覆蓋了所有變遷，并且對每個變遷的末狀態(tài)都做了檢查，具有很高的錯誤覆蓋率，序列長度在可接受的范圍內(nèi)保證了測試的工作量不大并具有可執(zhí)行性，可以將其描述為抽象測試套，用于本協(xié)議的互操作性測試中。

5 結(jié)束語

本文介紹了互操作性測試序列的生成算法，基于該算法對RSSP-I協(xié)議進行了互操作性測試的生成研究，最后得到了其互操作性測試序列。但本文在生成測試序列時所基于的單激勵原則有一定的局限性，在下一步的研究工作中，需要采用多激勵原則生成互操作性測試序列，多激勵原則即從外界環(huán)境可以同時向兩個實現(xiàn)輸入外部消息，它更為復(fù)雜，卻更加接近實際情況。另外，在序列生成算法上也有可以改進之處[6~7]，以達到更高的錯誤覆蓋率和更短的序列長度。

[1] 楊世玉，徐中偉.鐵路信號安全協(xié)議一致性測試序列生成研究[J].計算機工程與應(yīng)用，2010，46（34）：59-61.

[2]鐵路信號安全協(xié)議-I（報批稿）[S]. 北京全路通信信號設(shè)計院，2009.

[3]李 華，葉新銘.協(xié)議互操作性測試綜述[J].內(nèi)蒙古大學(xué)學(xué)報，2008，39（5）： 590-595.

[4] Seol S，Kim M，Kang S,et al．Fully automated interoperability test suite derivation for communication protocols[J]．Computer Networks, 2003, 43(6):735-759.

[5]張 濤.邊界網(wǎng)關(guān)協(xié)議BGP4+的互操作性測試研究[D].包頭：內(nèi)蒙古大學(xué)，2007.

[6] 王之梁，吳建平，尹 霞.基于通信多端口有限狀態(tài)機的協(xié)議互操作性測試生成研究[J].計算機學(xué)報，2006，29（11）：1909-1919.

[7] 林華輝，趙保華，屈玉貴.基于有向圖的最小完全覆蓋互操作測試序列生成算法[J].中國科學(xué)技術(shù)大學(xué)學(xué)報，2006（2）：225-229.