王秀玄

（西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院， 成都 611756）

基于UML狀態(tài)圖的列控中心軟件測(cè)試路徑生成方法

王秀玄

（西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院， 成都 611756）

針對(duì)列控中心測(cè)試，介紹了基于UML狀態(tài)圖的列控中心測(cè)試路徑生成方法。根據(jù)列控中心需求規(guī)范建立UML狀態(tài)圖模型；采用改進(jìn)的深度優(yōu)先搜索算法（DFS）自動(dòng)搜索有向圖得到從初始節(jié)點(diǎn)到終止節(jié)點(diǎn)的所有路徑集合，利用貪心算法構(gòu)造超串合并測(cè)試需求；利用路徑集合擴(kuò)展測(cè)試需求集合，最終實(shí)現(xiàn)測(cè)試路徑自動(dòng)生成；以列控中心改變區(qū)間運(yùn)行方向功能為例，給出測(cè)試路徑生成方法實(shí)現(xiàn)。

測(cè)試路徑；UML狀態(tài)圖；列控中心；深度優(yōu)先搜索；超串

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

基于UML模型的軟件測(cè)試技術(shù)采用UML模型對(duì)系統(tǒng)需求建模，由模型生成測(cè)試用例，可以降低測(cè)試工作量，并且模型具有直觀性。本文根據(jù)列控中心需求規(guī)范建立UML狀態(tài)圖模型，將狀態(tài)圖轉(zhuǎn)化為有向圖，利用超串思想組合測(cè)試需求子路徑，通過(guò)改進(jìn)深度優(yōu)先搜索算法遍歷有向圖得到遍歷路徑，并用來(lái)擴(kuò)展組合后的測(cè)試需求子路徑，得到完整測(cè)試路徑。以列控中心改變區(qū)間運(yùn)行方向?yàn)槔?，?yàn)證了該方法的可行性。

1 基于UML狀態(tài)圖的測(cè)試需求

測(cè)試主要包括基于代碼的測(cè)試和基于規(guī)格說(shuō)明的測(cè)試，其中，基于規(guī)格說(shuō)明的測(cè)試主要關(guān)注軟件規(guī)格說(shuō)明所描述的系統(tǒng)功能，對(duì)系統(tǒng)功能描述進(jìn)行驗(yàn)證和確認(rèn)[2]。基于UML模型的測(cè)試屬于基于規(guī)格說(shuō)明測(cè)試。根據(jù)期望輸出與實(shí)際輸出的一致性，分析系統(tǒng)的每個(gè)功能是否符合系統(tǒng)需求。

1.1 UML狀態(tài)圖

UML模型圖包括用例圖、狀態(tài)圖、順序圖、活動(dòng)圖、協(xié)作圖等多種圖。其中，狀態(tài)圖能夠描述一個(gè)特定對(duì)象的所有可能的狀態(tài)和觸發(fā)狀態(tài)轉(zhuǎn)移的條件，以及對(duì)象的動(dòng)作行為，通常表現(xiàn)為一個(gè)對(duì)象所經(jīng)歷的狀態(tài)序列，也包含引起狀態(tài)轉(zhuǎn)移的事件，以及狀態(tài)轉(zhuǎn)移伴隨的動(dòng)作，它可以對(duì)一個(gè)對(duì)象的生命周期建模[3]。狀態(tài)圖能夠清晰地展示列控中心軟件的邏輯、結(jié)構(gòu)及功能，便于后期的軟件分析與測(cè)試。

1.2 基于UML的覆蓋準(zhǔn)則

UML狀態(tài)圖包含諸多元素，覆蓋準(zhǔn)則應(yīng)從不同程度上覆蓋這些元素。不同覆蓋準(zhǔn)則會(huì)確定不同的測(cè)試需求。UML狀態(tài)圖主要涉及的測(cè)試覆蓋準(zhǔn)則有：狀態(tài)覆蓋準(zhǔn)則、狀態(tài)變遷覆蓋準(zhǔn)則、狀態(tài)變遷對(duì)覆蓋準(zhǔn)則、全序列覆蓋準(zhǔn)則等。

（1）狀態(tài)覆蓋準(zhǔn)則：要求測(cè)試用例必須覆蓋所有的狀態(tài)。

（2）狀態(tài)變遷覆蓋準(zhǔn)則：要求測(cè)試用例必須滿足規(guī)格說(shuō)明中每個(gè)前置條件。

（3）狀態(tài)變遷對(duì)覆蓋準(zhǔn)則：要求測(cè)試用例必須覆蓋每個(gè)相鄰的變遷對(duì)。

（4）全序列覆蓋準(zhǔn)則：要求測(cè)試必須覆蓋所有可以進(jìn)入狀態(tài)的組合序列[2]。

第1種覆蓋強(qiáng)度最弱，只覆蓋狀態(tài)。第2種包含狀態(tài)覆蓋。第3種主要檢查狀態(tài)之間的接口。第4種執(zhí)行所有可能執(zhí)行的路徑，但對(duì)于包含回路的狀態(tài)圖，全序列覆蓋則是無(wú)限的，實(shí)際測(cè)試中往往只考慮循環(huán)次數(shù)為0、1和2的情況。從圖的角度來(lái)劃分，也將覆蓋準(zhǔn)則劃分為節(jié)點(diǎn)覆蓋、邊覆蓋、邊對(duì)覆蓋、主路徑覆蓋等。

對(duì)于UML狀態(tài)圖，選擇不同覆蓋準(zhǔn)則會(huì)得到不同的測(cè)試需求，最終會(huì)得到不同的測(cè)試路徑。分別讀取圖中的狀態(tài)、遷移、遷移對(duì)和狀態(tài)序列，得到與覆蓋準(zhǔn)則相應(yīng)的測(cè)試需求。

2 基于UML狀態(tài)圖的測(cè)試路徑生成方法

本文主要研究基于UML狀態(tài)圖生成列控中心軟件測(cè)試路徑，主要包括以下步驟：（1）基于列控中心需求規(guī)范恰當(dāng)建立UML狀態(tài)圖模型；（2）提取UML狀態(tài)圖狀態(tài)、轉(zhuǎn)移、區(qū)域等信息，根據(jù)信息將UML狀態(tài)圖模型轉(zhuǎn)化為有向圖；（3）根據(jù)有向圖各種覆蓋準(zhǔn)則生成相應(yīng)測(cè)試需求；（4）結(jié)合有向圖和測(cè)試需求生成測(cè)試路徑。

2.1 UML狀態(tài)圖模型轉(zhuǎn)化為有向圖

狀態(tài)圖轉(zhuǎn)化為有向圖是測(cè)試的常用方法。根據(jù)需求規(guī)范，建立UML狀態(tài)圖模型并獲取與模型相對(duì)應(yīng)的XML文件，提取模型的節(jié)點(diǎn)、轉(zhuǎn)移條件、警戒條件以及約束等信息。圖1所示為簡(jiǎn)單狀態(tài)圖的狀態(tài)信息提取映射流程。

圖1 簡(jiǎn)單狀態(tài)圖映射流程

利用狀態(tài)圖模型提取的元素信息生成有向圖，將狀態(tài)圖中狀態(tài)映射為有向圖中節(jié)點(diǎn)，將狀態(tài)轉(zhuǎn)移映射為邊。生成有向圖的步驟為：

（1）創(chuàng)建狀態(tài)映射哈希表，鍵是狀態(tài)，值是整數(shù)；狀態(tài)逆映射哈希表，鍵是整數(shù)，值是狀態(tài)；創(chuàng)建狀態(tài)轉(zhuǎn)移表；實(shí)現(xiàn)狀態(tài)圖的哈希表存儲(chǔ)。

（2）創(chuàng)建節(jié)點(diǎn)映射哈希表，鍵是整數(shù)，值是節(jié)點(diǎn)；節(jié)點(diǎn)逆映射哈希表，鍵是節(jié)點(diǎn)，值是整數(shù)；創(chuàng)建邊映射表；實(shí)現(xiàn)哈希表信息到有向圖的構(gòu)建。

2.2 改進(jìn)深度優(yōu)先搜索（DFS）遍歷圖

深度優(yōu)先搜索是一種回溯搜索算法，本文采用改進(jìn)的深度優(yōu)先搜索算法得出遍歷初始節(jié)點(diǎn)到終止節(jié)點(diǎn)的路徑集合。

深度優(yōu)先搜索算法基本思想是任選圖形G的一個(gè)頂點(diǎn)v作為起點(diǎn)，訪問(wèn)v，然后訪問(wèn)該頂點(diǎn)鄰接的未被訪問(wèn)的一個(gè)頂點(diǎn)v’，再?gòu)膙’出發(fā)，繼續(xù)添加邊到這條路上。當(dāng)某頂點(diǎn)所有鄰接頂點(diǎn)都已訪問(wèn)過(guò)，則回到已訪問(wèn)頂點(diǎn)序列中最后擁有未被訪問(wèn)鄰接點(diǎn)的頂點(diǎn)w。再?gòu)膚出發(fā)，繼續(xù)盡可能多地添加邊得到以w開始的未訪問(wèn)過(guò)的頂點(diǎn)序列。當(dāng)所有已訪問(wèn)頂點(diǎn)的相鄰頂點(diǎn)都已被訪問(wèn)時(shí)，結(jié)束搜索[4]。

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

圖2 改進(jìn)深度優(yōu)先搜索算法遍歷圖

（1）將初始節(jié)點(diǎn)入棧，標(biāo)為入棧狀態(tài)；

（2）查看棧頂節(jié)點(diǎn)是否有未訪問(wèn)且未入棧的可達(dá)鄰接節(jié)點(diǎn)，若有，將該節(jié)點(diǎn)入棧，標(biāo)為入棧狀態(tài)；若無(wú)，該棧頂節(jié)點(diǎn)出棧，標(biāo)為未入棧狀態(tài)；

（3）若棧頂節(jié)點(diǎn)為終止節(jié)點(diǎn)，則整個(gè)棧為一條路徑，輸出整個(gè)棧，加入路徑集合P；

（4）棧頂節(jié)點(diǎn)出棧；

（5）重復(fù)（2）～（4），直到棧為空。

2.3 貪心算法合并測(cè)試需求為超串

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

計(jì)算重疊字符序列和超串為：

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

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

2.4 測(cè)試路徑生成

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

若Vi=Vmi，Vj=Vnj；

得到完整的測(cè)試路徑為：

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

圖3 測(cè)試路徑生成流程

3 改變區(qū)間運(yùn)行方向功能測(cè)試路徑生成

根據(jù)列控中心技術(shù)規(guī)范，以改變區(qū)間運(yùn)行方向功能為例，建立UML狀態(tài)圖模型并且提取與模型相對(duì)應(yīng)的XML文件，通過(guò)對(duì)文件的解析提取模型信息，實(shí)現(xiàn)從模型到測(cè)試路徑的生成過(guò)程。

3.1 列控中心改變區(qū)間運(yùn)行方向功能

改變區(qū)間運(yùn)行方向功能主要涉及正常改變運(yùn)行方向和輔助改變運(yùn)行方向，以及改變區(qū)間運(yùn)行方向時(shí)異常情況處理。

（1）正常改變區(qū)間運(yùn)行方向時(shí)，原接車站TCC收到本站CBI發(fā)車請(qǐng)求和鎖閉信息后，檢查條件滿足，則向?qū)Ψ秸景l(fā)送請(qǐng)求改變運(yùn)行方向信息；對(duì)方站條件滿足且驅(qū)動(dòng)相應(yīng)方向繼電器動(dòng)作到位，向原接車站發(fā)送允許改變運(yùn)行方向信息；原接車站收到允許改變運(yùn)行方向命令，驅(qū)動(dòng)相應(yīng)方向繼電器動(dòng)作到位，向CBI發(fā)送允許發(fā)車信息，CBI控制出站信號(hào)機(jī)開放，改變運(yùn)行方向成功。

（2）區(qū)間軌道電路故障占用則辦理輔助改變運(yùn)行方向。兩站值班員確認(rèn)軌道電路故障且區(qū)間空閑，由原接車站值班員按下相應(yīng)按鈕， CBI向TCC發(fā)送發(fā)車輔助辦理請(qǐng)求，確認(rèn)條件滿足，向原發(fā)車站TCC發(fā)送輔助改變運(yùn)行方向請(qǐng)求；原發(fā)車站值班員按下相關(guān)按鈕， TCC接到輔助改變運(yùn)行方向請(qǐng)求和輔助接車命令，檢查條件滿足，驅(qū)動(dòng)方向繼電器動(dòng)作到位，向?qū)Ψ秸景l(fā)允許輔助改變運(yùn)行方向信息；原接車站收到信息后，驅(qū)動(dòng)方向繼電器動(dòng)作到位，輔助改變運(yùn)行方向完成[6]。

3.2 改變區(qū)間運(yùn)行方向功能狀態(tài)圖模型

利用Eclipse平臺(tái)的UML建模工具Papyrus建立改變區(qū)間運(yùn)行方向功能模型，如圖4所示。

圖4 改變運(yùn)行方向狀態(tài)圖模型

主要過(guò)程如下：

（1）列控中心啟動(dòng)后，進(jìn)行方向初始化，若本站方向繼電器為接車狀態(tài)或鄰站為發(fā)車狀態(tài)，則初始化為接車方向（RS）；若6 s未接收到鄰站方向信息或本站方向繼電器處于未知狀態(tài)，也初始化為接車方向（RS）；當(dāng)本站方向繼電器為發(fā)車狀態(tài)且鄰站為接車狀態(tài)，則初始化為發(fā)車方向（DS）。

（2）接車狀態(tài)時(shí)，若收到本站CBI發(fā)車請(qǐng)求和發(fā)車鎖閉信息，且站間空閑、本站無(wú)接發(fā)車進(jìn)路、對(duì)方站無(wú)發(fā)車進(jìn)路等條件滿足，則轉(zhuǎn)到正常接車轉(zhuǎn)換準(zhǔn)備狀態(tài)（RN）；若不滿足則仍處于RS狀態(tài)。

（3）若在RN狀態(tài)時(shí)，收到對(duì)方站允許改變運(yùn)行方向命令，則轉(zhuǎn)換到正常接車轉(zhuǎn)換狀態(tài)（RNC），若未收到允許命令則轉(zhuǎn)回RS狀態(tài)。

（4）對(duì)于RNC狀態(tài)，若相應(yīng)方向繼電器轉(zhuǎn)換到位則進(jìn)入發(fā)車狀態(tài)（DS），若13 s無(wú)法確認(rèn)方向繼電器轉(zhuǎn)換到位則仍轉(zhuǎn)為接車狀態(tài)（RS）。

（5）對(duì)發(fā)車狀態(tài)（DS），若收到對(duì)方站正常改變運(yùn)行方向請(qǐng)求，且檢查站間空閑、未辦理發(fā)車進(jìn)路，則進(jìn)入正常改變發(fā)車轉(zhuǎn)換狀態(tài)（DNC）。

（6）對(duì)DNC狀態(tài)，若13 s內(nèi)確認(rèn)方向繼電器轉(zhuǎn)換到位，則進(jìn)入接車狀態(tài)（RS）；否則，仍轉(zhuǎn)為發(fā)車狀態(tài)（DS）。

對(duì)于區(qū)間軌道電路故障占用而不能正常改變運(yùn)行方向時(shí)，辦理輔助改變運(yùn)行方向，過(guò)程相似。

3.3 改變區(qū)間運(yùn)行方向模型測(cè)試路徑生成

基于以上算法進(jìn)行程序?qū)崿F(xiàn)，以狀態(tài)變遷覆蓋準(zhǔn)則為例，得到如下6條測(cè)試路徑。

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

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