導航：安全管理網>> 安全論文>> 交通安全論文>>正文

鐵路信號安全協議一致性測試序列生成研究

文檔作者：楊世玉1 徐中偉1 喻鋼1 張盛1 文檔來源： 1同濟大學 2．上海大學		點擊數：	更新時間： 2021年07月12日
下載地址：點擊這里	文件大小： 310.67 KB 共4頁	文檔格式： PDF	下載點數： 1 點（VIP免費）

全屏查看

內容預覽 [文件共4頁]

本文件共4頁，如需編輯使用，請下載。

注：預覽效果可能會出現部分文字亂碼（如口口口）、內容顯示不全等問題，下載是正常的。

	文件大小：310.67 KB 共4頁文件格式：PDF 下載點數：1 點（VIP會員免費）

下一篇：鐵路客運服務系統信息安全測試方法研究

上一篇：安全氣囊氣體發生劑燃速測試方法研究

文本預覽

僅提取頁面文字內容，供快速閱讀使用。

Compu招r Engineering andApplications計算機工程與應用2010，46(34) 59
@研發、設計、測試@
鐵路信號安全協議一致性測試序列生成研究
楊世玉1，徐中偉1，喻鋼1一，張盛1
YANG Shi．yul，XU Zhong．weP,YU Gan91．2,ZHANG Shen91
1同濟大學電子與信息工程學院，上海201804
2．上海大學悉尼工商學院，上海201800
1．College of Electronic and Information Engineering，Tongji University，Shanghai 201804，China
2．College of Sydney Business，Shanghai University，Stmghai 201800，China
E-mail：ysytomorrow@163．com．
YANG Shi-yu。XU Zhong-wel。YU Gang，et a1．Conformance test sequence generation for railway signal safety protoc01．
Computer Engineering and AppHcafions，2010．46(34)：59·61．
Abstract：Railway signal safety protocol—I alsure$the safe operation of high-speed rmlway．And generation of test sequence
is the key of conformance test．Aiming at the real—time requirements of RSSP—I，this paper proposes an FSM model with
time constraints。and generates every state’S unique input／output sequence at the basis of this model．At last，the algorithm
based On converging edge is used to generate conforltmnce test sequence for RSSP—I．which is more efficient than other algorithms．
Key words：Finite State Machine(FSM)；Unique Input／Output(UIO)sequence；Railway Signal Safety Protocol(RSSP·I)；time
constraints；converging edge
摘要：鐵路信號安全協議(RssP．I)是實現高速鐵路安全運行的保障，協議一致性測試的核心是生成完備有效的測試序列。針
對鐵路信號安全協議的實時性要求。提出了帶時間約束的FSM(Finite State Machine)模型，并在此模型基礎上生成狀態的UIO
(Unique Input／Output sequences)序列，最后采用基于收斂邊的算法生成了較其他算法更短的一致性測試序列，從而提高了測試效率。
關鍵詞：有限狀態機；唯一輸入輸出序列；CA路信號安全協議；時間約束；收斂邊
DOI：10．3778／j．issn．1002．8331．2010．34．018 文章編號：1002—8331(2010)34—0059．03 文獻標識碼：A 中圖分類號：TN915．852
l 引言
隨著武廣客運專線、京津客運專線的正式運營，我國已經
步入高速鐵路飛速發展階段。列車運行控制系統是保障高速
鐵路運行安全的關鍵設備之一，其一旦失效，將可能引發重大
的財產損失或人員傷亡，是典型的安全苛求系統。我國目前
高速鐵路使用的CTCS．3(中國列車運行控制系統3級)功能復
雜，系統內部、系統與外部環境之間存在大量復雜的數據交
互，這些數據的交互直接影響到列車運行安全“l。因此采用鐵
路信號安全協議(RSSP．I)是保障信息安全實時傳遞的有效技
術方法，而一致性測試是協議測試的關鍵。協議一致性測試
是驗證協議實現是否符合協議規范、滿足需求的有效方法n1。
一致性測試的工作主要集中在測試組織和測試集的生成
兩個方面。測試組織即測試方法的研究和測試系統的建立；
測試集的生成主要通過協議的形式化描述，從理論和方法上
研究并生成高質量的測試集。一致性測試集包含一組測試序
列，是一致性測試的核心和主線。在測試序列生成方面，理論
上比較成熟的測試序列生成算法主要是基于有限狀態機的，
有T方法、D方法、UIO方法和w方法。相對而言，UIO序列的
長度最短．所以通常采用UIO(Unique Input／Output sequences)
序列作為狀態的區分序列I”。目前一致性測試研究都是針對
功能的，研究重點在于如何生成長度短、檢錯能力強的測試序
列，而在CTCS-3安全苛求系統中，協議一致性測試除了面向
功能需求，更要針對安全性需求及實時性需求進行測試。因
此，針對RSSP．I協議一致性測試需求。建立了帶時間約束的
FSM模型，并利用基于收斂邊的算法，生成了RSSP．I協議的
一致性測試序列。
2基于FSM模瓔的一致性測試序列生成算法
2．1有限狀態機
有限狀態機在一致性測試中主要用于協議建模和測試序
基金項目：國家自然科學基金(the National Natural Science Foundation of China under Grant No．6067400)；鐵道部科技研究開發計劃基金資助
項目(the Ministry of Railway Technology Research and Development Foundation of China under Errant No．2007X003)。
作者簡介：楊世毛(1985．)。女，碩士研究生，主研領域為安全軟件測試評估；徐中偉(1964-)，男，教授。博士生導師．主研領域為安全軟件測試評
估；喻鋼(1977．)，男，講師，博士研究生．主研領域為安全軟件測試評估；張盛(1985·)，男，碩士研究生，主研領域為安全軟件測試評估。
收穡日期：2010-05．27修回日期：2010．07．26
萬方數據
60 2010，46(34) Compu把r Engineering andApplications計算機工程與應用
列自動生成兩個方面。有限狀態機可表示為M=假1,0，d，靠so)，
其中14J：
(1)s是非空的有限狀態集；
(2)，是有限輸入集；
(3)D是有限輸出集；
(4)J是狀態轉移函數s×，一S；
(5)y是輸出函數：S×，-0；
(6)so是初始狀態。
M可以用有向圖G--(V，￡)來表示。其中頂點集合肛{v。，
V2，?，¨}為FSM的狀態集合S，有向邊集合E一--(vt，vj；IdO．)，表
示從一個狀態v,N另一個狀態v，的變遷，厶和D_分別為輸入輸
出事件。圖I所示為一個FSM的有向圖。
圖1 FSM的有向圖
2．2一致性測試序列生成算法
協議的一致性測試要覆蓋FSM有向圖中的每個狀態和
變遷。一般算法生成一致性測試序列的過程如下91：首先計算
出各個狀態的UIO序列，然后用復位信息Reset將被測的有向
圖置于初始狀態&amp;amp;，再將其轉換到狀態S；對有向圖施加輸入
信號f．校驗輸出0與協議規范是否一致；最后用UIO序列驗證
尾狀態。由此得到的測試序列為P(&amp;amp;，S)@，(S，S)@們D(S)。
其中@是連接符，P(品，S)為引導序列。對每個狀態的所有輸
入都執行上述過程就可以得到最終的測試序列。
使用上述方法生成的測試序列較長，測試效率低下。因
此，采用了基于收斂邊的算法：設e。、e2為相同的砌序列，若e，、
e2收斂到相同的尾狀態，那么稱e，、e2為收斂邊嗍。
對于沒有收斂邊的FSM模型來說，模型中的任一狀態sj，
如果只有一個變遷(S，S；fl／o。)取決于iJo。，那么由UIO的定義
可知，f。／o。啪(S)必定是S的UIO序列。對狀態＆來說，如果
只有一個變遷(S，&amp;amp;；咖：)是取決于如，那么i#o：啪(&amp;amp;)為
狀態S的UIO序列。所以，fl／o。iJo：∽D(＆)是S的UIO序列。
以此類推，f，／o，i2／o：?UIO(剛為狀態S的UIO序列。
基于收斂邊的算法將FSM模型分為有收斂邊和沒有收
斂邊兩種情況r1：對于一個沒有收斂邊的FSM模型G，將模型
添加若干條邊構造成一個對稱圖G·，由初始狀態氐開始，生
成G·的歐拉遍歷EP。由于G沒有收斂邊，則有向圖G中的每
個狀態(S，&amp;amp;，?，曼)的UIO序列都可以用f。／D。f2／02"··明D(墨)
表示。最后的測試序列為EP@UIO(島)，@為連接符；如果一
個FSM模型中有收斂邊，如對狀態S，＆，?，＆輸入相同f／D后
都收斂到狀態S，那么i／oUlO(Sj)不是＆，島，?，S的UIO序
列。此時，需要把收斂邊單獨提取出來進行處理。具體的算
法流程如圖2。
3 RSSP—I協議一致性測試序列的生成
3．1鐵路信號安全協議
在高速鐵路列車控制系統中，鐵路倍號安全協議
圖2基于收斂邊算法的沈程圖
(RSSP．I)是用于車站列車控制中心與軌旁電子單元之間傳輸
信息的。在RSSP．I協議中，發送方(B)是會話發起者，接收方
(A)不能主動向發送方發送數據。B周期性地向A發送安全
數據。A必須實時檢查來自B的報文的時序，一旦不同步，就
觸發時序校正機制。A向B發送時序校正請求幀(SSE)，B收
到SSE后將時序信息放入時序校正應答幀(SSR)中，發送給
A，A收到SSR經過校驗提取出時序信息后，開始處理B發送
的安全數據。若當前時序已同步，就只需B單方向實時發送
安全數據幀即可，A不必做應答。
在握手過程中，B仍可繼續傳輸安全數據。這樣就保證
了網絡中消息序列傳輸的連續性。鐵路信號安全協議的數據
交互如圖3所示嗍。
f～能夠處理來自B 1不能夠處理來自B
L的安全數據■ 的安全數據
圖3安全數據交瓦
3．2帶時問約束的FSM模型
高速鐵路列車控制系統對實時性要求非常高。在系統
中。通信雙方都沒有未收到數據的最大容忍時間，如果超過這
個時間還未收到對方發來的數據，則進行重發或判定通信中
斷。超時數據即使合法也應丟棄，因為超時的數據不僅沒用
有時還會對整個系統的安全帶來危害嘲。
通常處理超時的做法是在通信雙方設定定時器。對發送
萬方數據
楊世玉，徐中偉，喻鋼，等：鐵路信號安全協議一致性測試序列生成研究2010，46(34) 61
方來說，發送消息的同時啟動定時器，在規定時間內收到接收
方發來的反饋消息則認為通信正常，繼續發送下一條消息。
如果發送方在規定時間內沒有收到對方的反饋消息，則認為
通信發生了故障。對接收方來說，每次收到發送方的數據就
給出一條反饋消息，并重新啟動定時器，如果在規定時間內還
沒收到發送方的數據，則判定為通信中斷。
在建立RSSP．I協議的FSM模型時，應把超時考慮進去，
構建帶時間約束的FSM模型。即利用定時器實現超時處理，
將超時作為模型的輸入，根據協議的相應動作輸出即可實現
重發和結束通信的功能。
RSSP．I協議是從接收方的角度來設計的，所以本文就以
接收方為測試對象。在RSSP．I協議中，采用定時器對超時的
數據進行處理。超時處理的做法是，在接收方設置兩個定時
器，NoDam和Wa“SSR。
NoDam是接收方未收到發送方數據的最大容忍時間，一
旦超過這個時間，接收方判定通信中斷。
WaitSSR為接收方發送SSE后等待SSR回復的最大容忍
時間，超過此時間，重新發送時序校驗請求幀。RSSP—I協議的
有限狀態機模型如圖4所示。
圖4 RSSP．1協議的FSM模型
協議具有4個狀態(島，S，島，島)，其中：
&amp;amp;表示空閑，無連接狀態；
&amp;amp;表示等待SSR回復狀態，即接收方發送了SSE，等待發
送方回復SSR以便進行時序同步；
．受表示接收安全數據狀態，接收方與發送方已建立同步，
接收方接收發送方數據交給應用層處理；
島表示通信中斷狀態，通信過程中由于接收方在設定的
時間限制內未收到來自發送方的數據，接收方判為通信中斷，
斷開連接。
協議的輸入輸出包括：
DATA為安全數據；SSE為接收方的時序校正請求；SSR
為發送方的時序校正應答；Timeout 為等待接收WaitSR SSR
超時；Timeout 為接收安全數據超時； 為刪_NoData DISCONN
除鏈路命令。
輸入集合為而(D／蛆'A)，i2(SSR)，6(D)，h(Timeout WaitSSR)，
is(Timeout NoDam)，i。(DISCONN)；輸出集合為o。(SSE)，D2(D)。
3．3 RSSP．I協議一致性測試序列的生成
根據圖4所示的FSM模型G，首先找出收斂邊，可以看出
只有兩條收斂邊：
ce,={Sl，島；is／02}，ce2={S2，焉；舶2}
對每條收斂邊的起始狀態，求出其u10序列：L玎D(蜀)=∥D2。
叩D(&amp;amp;)=i#ol。
在圖4中，將以&amp;amp;和&amp;amp;作為尾狀態的所有變遷找出，計算
其子序列e(S，sj。S,；i／o)={i／o，u／o(sj)}如下：
et---(S0，S，＆；iI／01)=“／ol，i#02}
薩(So，&amp;amp;，＆；∥0I)={跏l，彬D2}
白=(&amp;amp;，S，&amp;amp;；ido，)={跏l，iJ02}
鱸(&amp;amp;，S，&amp;amp;；i3／01)={i40I，i#02}
e產(蜀，島，SI；∥02)={∥D2，i；o-}
薩(&amp;amp;，島。S；i,／o：)={f，／02，U01}
構造圖G，-(礦，E’)，V’即為G的頂點，而E，是將G中相關
的變遷{j，／o，，Uo。，iJo，，i#o，，8／0：，i,／o：}用上面的子序列替代，
其余邊保持不變。得到的G如圖5所示。
圖5基于收斂邊算法的G倒
在任意狀態．孓和．霉間添加若干來自圖G的邊，使得G變成
對稱圖G·，即對于每個狀態，其入度與出度相等，如圖6所示。
圈6基于收斂邊算法的G·圖
構造圖6的歐拉路徑：
ri／null，e1，e4。e6，e5，自，i40l。f5／D2，iJ02，如，is／o：，f如
代入測試子序列可得到：
ri／null，i,／oI'∥仍，厶／bI'∥詵，f1／也，i3／ol，iJ02，UoI，idol，i2／02，
i；ol，∥D2，id02，Uol，iJ02，is／02，枷2
可以看出，本文是以&amp;amp;作為末狀態，而啪(S0)=f。／o。。由
前面的推理可知，在整個歐拉路徑中。每一個狀態都可以用
it／o，i#o：?∽D(&amp;amp;)來驗證，所以得到的測試序列不僅對每個變
遷進行了測試，還對每個尾狀態進行了驗證。
最終，得到RSSP．I協議的一致性測試序列：
r／／null，f1／bl，∥a2，i；oI，糾b2，j，／況，U01，i2／02，i,／ol，idoI，i#02，
i#01，id02，id02，i#ol，i#02，id02，劃白2，i,／ol
測試序列長度為19。
3．4測試序列分析
傳統算法需要對每個尾狀態進行狀態驗證，而基于收斂
邊的算法根據收斂邊的性質，利用最后一個狀態的UIO序列
進行所有狀態的驗證。因此產生的測試序列較短。
(下轉9l頁)
萬方數據
俞惠芳，王彩芬，王之倉，等：自認證廣義指定驗證者簽密方案
假沒還有其他用戶能夠從密文中恢復出消息明文m。簽
密持有者在指定簽密算法中給出礦=e(Q，，P，+P。∥，攻擊者
由R=kP求出k，進而偽造礦以便恢復消息明文是不可行的，
因為這相當于破解ECDL難題。另外，如果攻擊者能求出
y=e(sr，固=P((～+s)Qr，㈣=e(P，p)abk，這就相當于已知
R=kP，Q，=aP，(rv+力P=cP，計算出了dP，P)樅，這和BDH
困難問題相矛盾，所以攻擊者通過掰=皿(noc恢復出消息明
文研是不可能的，即假設不成立。所以除了簽密者、簽密持有
者和指定驗證者外．其他任何第三方均無法知道消息明文。
4．3指定簽密驗證的指定性
從等式m=％O")ec(其中y=e(Sv，P))中可以看出，要確
保能夠正確恢復出消息明文m，需要用到指定驗證者的私鑰
品。只有擁有合法私鑰品的指定驗證者才能正確恢復出消
息明文m。在正確恢復出m的基礎上，指定驗證者才能通過
判斷等式cr2=P(Q。，巳)7rq‘”·∞r即P(Q』，P。6)’q‘朋’峨·～是否成
立來驗證簽密(0"I，％)。而任何與本文方案無關的第三方試圖
利用已有信息甑，％)求出m是不可能的，因為這相當于破解
BDH困難問題和單向散列函數求逆問題。
4．4不可偽造性
任何內部攻擊者和外部攻擊者都不可能偽造一個來自簽
密者和簽密持有者的簽密組。
一個外部攻擊者試圖假冒簽密者偽造消息m的簽密組
倆，f，q)和(R，C，O"I，0"2)。由于外部攻擊者不知道(，，s．，七)，
因而無法構造合法的能夠通過簽密持有者和指定驗證者驗證
的簽密。所以任何外部攻擊者在不知道(f，s。，七)情況下，要
偽造出有效合法的密文是不可行的。
假沒內部攻擊者為指定驗證者，指定驗證者向第三方稱
(R 7，C，吼，#23為合法的簽密組，其中(R’，嗎，)為指定驗證者偽
造的數據。為了使得偽造數據通過驗證，指定驗證者必須確
定k，但是k是一個隨機整數而且只有簽密持有者知道，即使
指定驗證者知道R，想通過尺=艫計算出k也是不可行的，因
為求解ECDL問題是困難的。因此，指定驗證者是不可能偽
造出合法的簽密。
5結語
在橢圓曲線離散對數問題和雙線性Diffie—Hellman問題
的難解性下，首次構造了一個自認證廣義指定驗證者簽密方
案。新方案不存在證書管理問題和密鑰托管l’ⅡJ題，允許簽密
的持有者指定簽密給指定的驗證者，只有指定的驗證者能夠
從指定簽密中正確恢復出消息，而且安全性強、計算和通信成
本低、效率高，更適合于在實際中應用。
參考文獻：
【1】Stemfeld R，Bull L，Wang H，et a1．Universal designated-verifier
signatures[C]／／LNCS 2894：Proceedings of Advances in Cryptol—
ogy-Asiacrypt’03，Taipei，Taiwai，November 30·December 4，
2003．Berlin：Springer-Verlag。2003：522·542．
【2】Zhang Fan·guo。Susilo W，Mu Yi，et a1．Identity-based universal
designated verifier signature[C]／／LNCS 3823：Proceedings of
EDC Workshops’05，Nagasaki，Japan，December 6-9，2005．Berlin：
Springer-Verlag，2005：825·834．
【3】Shao Zu-hua．Self-certified signature scheme from pairings[J]．
The Journal of Systems and Software．2007(80)：388·395．
【4】Wang Gui-lin．Universal forgery 011 a group signature scheme
using seif-certi 6 ed pubfic keys[J]．Information Processing Letters．
2004(89)：227。231．
【5】Tseng Y，Jan J，Chien H．Digital signature with message l哈eOV·
ery using self-certified public keys and its variants[J]．Applied
Mathematics and Computation，2003(136)：203-214．
[6】6俞惠芳，王彩芬．一個高效的自認證簽密方案【J】．計算機工程。
2009，35(18)．
(Ja接6l頁)
對于RSSP．I協議的FSM模型，一般算法得到的測試序列
長度為30，基于收斂邊算法得到的測試序列長度為19，而產
生測試序列的時間并沒有增加。基于收斂邊的算法與一般算
法都對FSM模型中所有變遷進行了遍歷，并且都以UIO序列
為特征序列來驗證每次變遷的末狀態，所以兩種算法生成的
測試序列錯誤覆蓋率相似。并且，基于收斂邊算法得到的測
試序列中還包含了對超時的處理。
4結束語
隨著我國高速鐵路的迅速發展，用于保證運輸安全的鐵
路安全通信協議越來越重要，它的實現能否滿足系統交互的
實時性、安全性至關重要。因此實現完備的鐵路安全通信協
議一致性測試不僅要關注如何生成更短的測試序列，更應該
關注安全性、實時性方面的測試。本文在生成鐵路信號安全
協議一致性測試序列時，不僅考慮到了測試序列的效率問題，
更兼顧了安全通信協議對實時性的要求。
參考文獻：
【1】1張曙光．CTCS-3級列控系統總體技術方案【M】．北京．中國鐵道出版
社．2008．
【2】ISO／IEC 9646·2．Information Processing Systems．Open system interconnecfion，
OSI conformance testing methodology and flamework，
Part 2：Abstract test suite SlⅪCification[S]．1994．
【3】Derderian K，Hierons R M，Harmun M，et ai．Automated unique
input output sequence generation for conformance testing of
FSMs[J]．Computer Journal。2006，49(3)：331-344．
【4】葛猛。趙保華．BGP-4協議一致性測試序列生成【J】．計算機工程與
應用，2005，41(22)：108．1lO．
【5】魏仰蘇，孟兆航，舒挺．通信協議一致性測試序列自動生成算法研
究【J】．計算機工程與設計，2007(10)：2312-2315．
【6】6 Aho A V，Dahbura A T，Lee D，et a1．An optimization technique
for protocol conformance test generation based 011 UIO se—
quence and rural Chinese postman tom[J]．IEEE Transactions
Oil Communications．1991。39(11)．
【7】Xie Lei。Wei Jiao-long。Zhu Guang—xi．An improved FSM-basod
method for BGP protocol[J]．IEEE，2008(6)：557·561．
【8】北京全路通信信號研究設計院．鐵路信號安全協議-I(報批
稿)【s1．2009—08．
【9】9滕竹．基于EFSM的CBTC通信協議一致性測試的研究【D】．北京：
北京交通大學，2008．

網友評論 more

交通安全論文最新內容

04-23