基于UML狀態圖的列控中心軟件測試路徑生成方法

王秀玄

（西南交通大學 信息科學與技術學院， 成都 611756）

基于UML狀態圖的列控中心軟件測試路徑生成方法

王秀玄

（西南交通大學 信息科學與技術學院， 成都 611756）

針對列控中心測試，介紹了基于UML狀態圖的列控中心測試路徑生成方法。根據列控中心需求規范建立UML狀態圖模型；采用改進的深度優先搜索算法（DFS）自動搜索有向圖得到從初始節點到終止節點的所有路徑集合，利用貪心算法構造超串合并測試需求；利用路徑集合擴展測試需求集合，最終實現測試路徑自動生成；以列控中心改變區間運行方向功能為例，給出測試路徑生成方法實現。

測試路徑；UML狀態圖；列控中心；深度優先搜索；超串

列控系統是保證列車安全運行、提高列車運行效率和行車密度的關鍵設備，而列控中心（TCC）是列控系統地面設備的重要組成部分，在CTCS-2級列控系統中，根據線路限速、進路信息、區段占用等信息，產生行車許可，在保證行車安全中起著重要作用。列控中心軟件是典型的安全關鍵軟件（Safety Critical Software），軟件的正確性和安全性直接關系到行車安全，軟件測試已成為保證列控中心質量的一項重要任務。列控中心輸入輸出復雜，信息交互頻繁，對安全性和實時性要求嚴格。然而，目前對于列控中心軟件的測試主要由專家或工程師根據工作經驗設計測試案例，采用手工測試的方式分析軟件在各種場景下的響應行為，測試工作繁重[1]，并且易出現漏編漏測，無法保證測試的完備性。

基于UML模型的軟件測試技術采用UML模型對系統需求建模，由模型生成測試用例，可以降低測試工作量，并且模型具有直觀性。本文根據列控中心需求規范建立UML狀態圖模型，將狀態圖轉化為有向圖，利用超串思想組合測試需求子路徑，通過改進深度優先搜索算法遍歷有向圖得到遍歷路徑，并用來擴展組合后的測試需求子路徑，得到完整測試路徑。以列控中心改變區間運行方向為例，驗證了該方法的可行性。

1 基于UML狀態圖的測試需求

測試主要包括基于代碼的測試和基于規格說明的測試，其中，基于規格說明的測試主要關注軟件規格說明所描述的系統功能，對系統功能描述進行驗證和確認[2]。基于UML模型的測試屬于基于規格說明測試。根據期望輸出與實際輸出的一致性，分析系統的每個功能是否符合系統需求。

1.1 UML狀態圖

UML模型圖包括用例圖、狀態圖、順序圖、活動圖、協作圖等多種圖。其中，狀態圖能夠描述一個特定對象的所有可能的狀態和觸發狀態轉移的條件，以及對象的動作行為，通常表現為一個對象所經歷的狀態序列，也包含引起狀態轉移的事件，以及狀態轉移伴隨的動作，它可以對一個對象的生命周期建模[3]。狀態圖能夠清晰地展示列控中心軟件的邏輯、結構及功能，便于后期的軟件分析與測試。

1.2 基于UML的覆蓋準則

UML狀態圖包含諸多元素，覆蓋準則應從不同程度上覆蓋這些元素。不同覆蓋準則會確定不同的測試需求。UML狀態圖主要涉及的測試覆蓋準則有：狀態覆蓋準則、狀態變遷覆蓋準則、狀態變遷對覆蓋準則、全序列覆蓋準則等。

（1）狀態覆蓋準則：要求測試用例必須覆蓋所有的狀態。

（2）狀態變遷覆蓋準則：要求測試用例必須滿足規格說明中每個前置條件。

（3）狀態變遷對覆蓋準則：要求測試用例必須覆蓋每個相鄰的變遷對。

（4）全序列覆蓋準則：要求測試必須覆蓋所有可以進入狀態的組合序列[2]。

第1種覆蓋強度最弱，只覆蓋狀態。第2種包含狀態覆蓋。第3種主要檢查狀態之間的接口。第4種執行所有可能執行的路徑，但對于包含回路的狀態圖，全序列覆蓋則是無限的，實際測試中往往只考慮循環次數為0、1和2的情況。從圖的角度來劃分，也將覆蓋準則劃分為節點覆蓋、邊覆蓋、邊對覆蓋、主路徑覆蓋等。

對于UML狀態圖，選擇不同覆蓋準則會得到不同的測試需求，最終會得到不同的測試路徑。分別讀取圖中的狀態、遷移、遷移對和狀態序列，得到與覆蓋準則相應的測試需求。

2 基于UML狀態圖的測試路徑生成方法

本文主要研究基于UML狀態圖生成列控中心軟件測試路徑，主要包括以下步驟：（1）基于列控中心需求規范恰當建立UML狀態圖模型；（2）提取UML狀態圖狀態、轉移、區域等信息，根據信息將UML狀態圖模型轉化為有向圖；（3）根據有向圖各種覆蓋準則生成相應測試需求；（4）結合有向圖和測試需求生成測試路徑。

2.1 UML狀態圖模型轉化為有向圖

狀態圖轉化為有向圖是測試的常用方法。根據需求規范，建立UML狀態圖模型并獲取與模型相對應的XML文件，提取模型的節點、轉移條件、警戒條件以及約束等信息。圖1所示為簡單狀態圖的狀態信息提取映射流程。

圖1 簡單狀態圖映射流程

利用狀態圖模型提取的元素信息生成有向圖，將狀態圖中狀態映射為有向圖中節點，將狀態轉移映射為邊。生成有向圖的步驟為：

（1）創建狀態映射哈希表，鍵是狀態，值是整數；狀態逆映射哈希表，鍵是整數，值是狀態；創建狀態轉移表；實現狀態圖的哈希表存儲。

（2）創建節點映射哈希表，鍵是整數，值是節點；節點逆映射哈希表，鍵是節點，值是整數；創建邊映射表；實現哈希表信息到有向圖的構建。

2.2 改進深度優先搜索（DFS）遍歷圖

深度優先搜索是一種回溯搜索算法，本文采用改進的深度優先搜索算法得出遍歷初始節點到終止節點的路徑集合。

深度優先搜索算法基本思想是任選圖形G的一個頂點v作為起點，訪問v，然后訪問該頂點鄰接的未被訪問的一個頂點v’，再從v’出發，繼續添加邊到這條路上。當某頂點所有鄰接頂點都已訪問過，則回到已訪問頂點序列中最后擁有未被訪問鄰接點的頂點w。再從w出發，繼續盡可能多地添加邊得到以w開始的未訪問過的頂點序列。當所有已訪問頂點的相鄰頂點都已被訪問時，結束搜索[4]。

通用的深度優先搜索算法是要遍歷圖的所有節點，在搜索過程中，得到的子路徑不會有確定的起點和終點。而本文模型有明確的初始節點和終止節點，且任意狀態都是從初始狀態可達的，因此，從初始節點到終止節點必然存在路徑集能夠遍歷所有節點。本文將深度優先算法（DFS）加以改進，搜索出從初始節點到終止節點遍歷圖中所有節點的路徑集合P。具體算法流程如圖2如示。

圖2 改進深度優先搜索算法遍歷圖

（1）將初始節點入棧，標為入棧狀態；

（2）查看棧頂節點是否有未訪問且未入棧的可達鄰接節點，若有，將該節點入棧，標為入棧狀態；若無，該棧頂節點出棧，標為未入棧狀態；

（3）若棧頂節點為終止節點，則整個棧為一條路徑，輸出整個棧，加入路徑集合P；

（4）棧頂節點出棧；

（5）重復（2）～（4），直到棧為空。

2.3 貪心算法合并測試需求為超串

將覆蓋準則確定的測試需求采用超串的思想加以處理，可以減少測試花費成本。設S1和S2是兩個字符串，本文用＜S1，S2＞來表示S1的后綴和S2的前綴之間重疊的最長字符序列，用S1,2表示S1和S2公共超串。貪心算法是用來構造最短公共超串的重要方法。貪心算法就是指逐步加入重疊覆蓋程度最大的兩個字符串Si和Sj，將其合并成Si,j，直到所有子字符串連接成一個超串[5]，如：

計算重疊字符序列和超串為：

則P1,P2,P3最短公共超串為：

同理，將測試需求集合（TR）中每條測試需求看做一個子串，利用貪心算法盡可能多地連接子串，求得連接子串最多的公共超串，得到連接后的測試需求集合TRS。

2.4 測試路徑生成

由生成超串后的測試需求集合（TRS）和覆蓋所有節點的路徑集合P得到最終測試路徑集合TP。取TRS中第i個子路徑tri（tri∈TRS），查找包含子串tri首節點的路徑Pm（Pm∈P）和包含tri尾節點的路徑Pn（Pn∈P），用路徑Pm中從初始節點到tri首節點的部分擴展tri，用路徑Pn中從tri尾節點到終止節點的部分擴展tri,得到一條完整測試路徑。假設：

若Vi=Vmi，Vj=Vnj；

得到完整的測試路徑為：

將TRS中所有子路徑擴展完畢，刪除冗余路徑，得到最終測試路徑集合。具體算法流程如圖3所示。

圖3 測試路徑生成流程

3 改變區間運行方向功能測試路徑生成

根據列控中心技術規范，以改變區間運行方向功能為例，建立UML狀態圖模型并且提取與模型相對應的XML文件，通過對文件的解析提取模型信息，實現從模型到測試路徑的生成過程。

3.1 列控中心改變區間運行方向功能

改變區間運行方向功能主要涉及正常改變運行方向和輔助改變運行方向，以及改變區間運行方向時異常情況處理。

（1）正常改變區間運行方向時，原接車站TCC收到本站CBI發車請求和鎖閉信息后，檢查條件滿足，則向對方站發送請求改變運行方向信息；對方站條件滿足且驅動相應方向繼電器動作到位，向原接車站發送允許改變運行方向信息；原接車站收到允許改變運行方向命令，驅動相應方向繼電器動作到位，向CBI發送允許發車信息，CBI控制出站信號機開放，改變運行方向成功。

（2）區間軌道電路故障占用則辦理輔助改變運行方向。兩站值班員確認軌道電路故障且區間空閑，由原接車站值班員按下相應按鈕， CBI向TCC發送發車輔助辦理請求，確認條件滿足，向原發車站TCC發送輔助改變運行方向請求；原發車站值班員按下相關按鈕， TCC接到輔助改變運行方向請求和輔助接車命令，檢查條件滿足，驅動方向繼電器動作到位，向對方站發允許輔助改變運行方向信息；原接車站收到信息后，驅動方向繼電器動作到位，輔助改變運行方向完成[6]。

3.2 改變區間運行方向功能狀態圖模型

利用Eclipse平臺的UML建模工具Papyrus建立改變區間運行方向功能模型，如圖4所示。

圖4 改變運行方向狀態圖模型

主要過程如下：

（1）列控中心啟動后，進行方向初始化，若本站方向繼電器為接車狀態或鄰站為發車狀態，則初始化為接車方向（RS）；若6 s未接收到鄰站方向信息或本站方向繼電器處于未知狀態，也初始化為接車方向（RS）；當本站方向繼電器為發車狀態且鄰站為接車狀態，則初始化為發車方向（DS）。

（2）接車狀態時，若收到本站CBI發車請求和發車鎖閉信息，且站間空閑、本站無接發車進路、對方站無發車進路等條件滿足，則轉到正常接車轉換準備狀態（RN）；若不滿足則仍處于RS狀態。

（3）若在RN狀態時，收到對方站允許改變運行方向命令，則轉換到正常接車轉換狀態（RNC），若未收到允許命令則轉回RS狀態。

（4）對于RNC狀態，若相應方向繼電器轉換到位則進入發車狀態（DS），若13 s無法確認方向繼電器轉換到位則仍轉為接車狀態（RS）。

（5）對發車狀態（DS），若收到對方站正常改變運行方向請求，且檢查站間空閑、未辦理發車進路，則進入正常改變發車轉換狀態（DNC）。

（6）對DNC狀態，若13 s內確認方向繼電器轉換到位，則進入接車狀態（RS）；否則，仍轉為發車狀態（DS）。

對于區間軌道電路故障占用而不能正常改變運行方向時，辦理輔助改變運行方向，過程相似。

3.3 改變區間運行方向模型測試路徑生成

基于以上算法進行程序實現，以狀態變遷覆蓋準則為例，得到如下6條測試路徑。

Method of software test paths generation for train control center based on UML state chart diagram

WANG Xiuxuan
( School of Information Science and Technology,Southwest Jiaotong University,Chengdu 611756,China)

Aiming at testing train control center (TCC),this article introduced the method of test paths generation for TCC based on UML state chart diagram.The UML state chart diagram model was established on the requirement specifcation of TCC.An improved Depth First Search (DFS) Algorithm was used to automatically search the directed graph,and get all paths from the initial node to the end node.The Greedy Algorithm was used to construct the test requirement of super string merging,and the path set was used to extend test requirements set.Finally,the automatic generation of test path was implemented.Taking changing running direction in sections of TCC for example,the implementation of test path generation method was given.

test paths;UML state chart diagram;train control center (TCC);depth frst search;super string

U284.48：TP39

A

1005-8451（2016）08-0009-05

2016-01-12

王秀玄，在讀碩士研究生 。