鐵路信號(hào)安全協(xié)議互操作性測(cè)試序列生成研究

王 瑞，梁 艷

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

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

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

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

1 互操作性測(cè)試的形式化模型

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

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

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

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

（4）Lout=(U1, U2, …Uk)是輸出符號(hào)向量的集合，其中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)，輸入符號(hào)，輸出符號(hào)的集合。

互操作性測(cè)試把參與測(cè)試的兩個(gè)或者多個(gè)實(shí)現(xiàn)作為整體考慮，采用組合的有限狀態(tài)機(jī)對(duì)被測(cè)協(xié)議從整體上進(jìn)行形式化描述，本文中研究的是1:1的互操作性測(cè)試，用II表示2個(gè)有限狀態(tài)機(jī)的組合：MA和MB?？梢赃@樣定義，組合的有限狀態(tài)機(jī)II是一個(gè)五元組(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)表示輸入符號(hào)的集合，即，LII,in=(Lin,A,EULin,B,E) 。

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

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

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

2 互操作性測(cè)試序列的生成算法

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

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

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

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

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

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

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

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

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

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

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

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

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

在對(duì)RSSP-I協(xié)議進(jìn)行互操作性測(cè)試的研究中，采用前面的互操作性測(cè)試套生成算法，圖5以一個(gè)RSSP-I協(xié)議中的交互實(shí)例來(lái)說(shuō)明互操作性測(cè)試套的生成過(guò)程。

最開(kāi)始，發(fā)送方和接收方都處于初始狀態(tài)，即：States ={（IDLE, IDLE）}。圖6介紹了圖1中的算法生成互操作性測(cè)試?yán)倪^(guò)程。

于是，就生成了第（1）條測(cè)試?yán)?，用同樣的方法可以生成下?1條互操作性測(cè)試?yán)?/p>

圖4 RSSP-I接收方模型

圖5 一個(gè)消息交互的例子

圖6 測(cè)試?yán)?）生成的具體過(guò)程

（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?？梢陨山M合的有限狀態(tài)機(jī)如圖7所示。在組合的有限狀態(tài)機(jī)模型基礎(chǔ)上進(jìn)行對(duì)稱擴(kuò)展，得到歐拉圖如圖8所示。

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

圖8 RSSP-I組合的有限狀態(tài)機(jī)的對(duì)稱擴(kuò)展

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

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

5 結(jié)束語(yǔ)

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

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

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

[3]李 華，葉新銘.協(xié)議互操作性測(cè)試綜述[J].內(nèi)蒙古大學(xué)學(xué)報(bào)，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+的互操作性測(cè)試研究[D].包頭：內(nèi)蒙古大學(xué)，2007.

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

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