王 碩，張亞?wèn)|，郭 進(jìn)，李 耀，蘭 浩

(1.西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都 611756；2.電子科技大學(xué) 光電科學(xué)與工程學(xué)院，成都 611731)

列控中心(Train Control Centre, TCC)是高速鐵路CTCS-2(Chinese Train Control System Level 2)和CTCS-3(Chinese Train Control System Level 3)級(jí)列控系統(tǒng)核心的地面設(shè)備之一，主要完成軌道電路編碼、區(qū)間信號(hào)機(jī)點(diǎn)燈控制、區(qū)間方向控制等安全苛求功能.其功能邏輯的失效將危及行車(chē)安全，造成嚴(yán)重的事故.為了保證TCC功能的安全性，在投入使用前必須進(jìn)行一系列嚴(yán)格的測(cè)試.近年來(lái)，隨著自動(dòng)化測(cè)試的興起，我國(guó)主要TCC廠家陸續(xù)研發(fā)了自動(dòng)化測(cè)試平臺(tái)，但自動(dòng)生成測(cè)試用例的問(wèn)題仍未得到有效解決，成為T(mén)CC自動(dòng)化測(cè)試的瓶頸.

基于模型的測(cè)試(Model Based Testing，MBT)通過(guò)建立被測(cè)系統(tǒng)或所處環(huán)境的模型設(shè)計(jì)或執(zhí)行測(cè)試用例，實(shí)現(xiàn)軟件或系統(tǒng)的測(cè)試[1].MBT生成測(cè)試用例的一般流程為：

1)基于測(cè)試需求和測(cè)試計(jì)劃建立測(cè)試模型；

2)利用模型生成抽象測(cè)試用例，形成抽象測(cè)試集；

3)將抽象測(cè)試集中的抽象測(cè)試用例轉(zhuǎn)化為可執(zhí)行測(cè)試用例，形成可執(zhí)行測(cè)試集[1].近年來(lái)，MBT方法被引入到列控系統(tǒng)設(shè)備測(cè)試中，文獻(xiàn)[2-3]利用有色Petri網(wǎng)分別對(duì)車(chē)地通信和車(chē)載模式轉(zhuǎn)換場(chǎng)景生成測(cè)試用例.文獻(xiàn)[4-7]利用UPPAAL建立相應(yīng)的時(shí)間自動(dòng)機(jī)模型，結(jié)合CoVer工具自動(dòng)生成測(cè)試用例集.文獻(xiàn)[8]利用輸入等價(jià)類(lèi)劃分測(cè)試?yán)碚摻⒂邢逘顟B(tài)機(jī)，通過(guò)W-method生成測(cè)試用例集.文獻(xiàn)[2-8]所生的測(cè)試集為抽象測(cè)試集，實(shí)際應(yīng)用時(shí)仍需將其實(shí)例化為可執(zhí)行測(cè)試集.文獻(xiàn)[9]提出了一種輸入空間劃分和邏輯覆蓋相結(jié)合的抽象測(cè)試用例實(shí)例化方法.

以上研究在測(cè)試用例生成方面做了大量工作，但均未考慮接口通信時(shí)機(jī)的問(wèn)題，無(wú)法滿(mǎn)足TCC自動(dòng)化測(cè)試的需求.因?yàn)樵谧詣?dòng)化測(cè)試中，為了實(shí)現(xiàn)測(cè)試連續(xù)自動(dòng)的執(zhí)行，測(cè)試用例不僅需要提供通信的數(shù)據(jù)內(nèi)容，還需提供通信的時(shí)機(jī).此外，對(duì)于TCC中帶有時(shí)間約束的功能場(chǎng)景，通信時(shí)機(jī)也是對(duì)時(shí)間特性的測(cè)試.

基于此，本文作者提出帶有輸入輸出時(shí)間的確定性有限狀態(tài)機(jī)(Deterministic Finite State Machine with Input and Output Time，DFSM-T)來(lái)實(shí)現(xiàn)通信時(shí)機(jī)的表達(dá)，并對(duì)其搜索測(cè)試路徑.再利用邊界值分析及控制條件覆蓋測(cè)試生成算法(Test Generation Algorithm of Control Condition Coverage，CGA)生成帶有通信時(shí)機(jī)的測(cè)試用例，形成可執(zhí)行測(cè)試集，以滿(mǎn)足TCC自動(dòng)化測(cè)試的需求.

1 模型與測(cè)試路徑

1.1 DFSM-T模型定義

為了更好的描述通信時(shí)機(jī)和通信內(nèi)容，擴(kuò)展了 確定性有限狀態(tài)機(jī)(Deterministic Finite State Machine，DFSM)的輸入輸出動(dòng)作，提出了DFSM-T模型.

定義1(DFSM-T) 一個(gè)DFSM-T是一個(gè)6元組(S,s0,I,O,δ,λ)，其中：S是有限狀態(tài)集合;s0是其中的初始狀態(tài)；I是有限輸入集合，其中每個(gè)輸入in=(a，G(x))是一個(gè)二元組，a表示輸入的內(nèi)容，G(x)表示輸入的時(shí)機(jī)，用于描述相對(duì)上一次交互的時(shí)間約束；O是有限輸出集合，其中每個(gè)輸出out=(a′，G′(x))是一個(gè)二元組，a′表示輸出的內(nèi)容，G′(x)表示輸出的時(shí)機(jī)，用于描述相對(duì)上一次交互的時(shí)間約束；δ：S×I→S是一個(gè)變遷函數(shù)；λ：S×I→O是一個(gè)輸出函數(shù).

I、O中的G(x)用于描述當(dāng)最近的一次輸入或輸出完成后，時(shí)間x應(yīng)滿(mǎn)足的時(shí)間約束.有9種表達(dá)形式，分別為xn，x≥n，x=n，x≥m&&x≤n，x>m&&x≤n，x≥m&&xm&&xm.例如in=(a，x

由于DFSM-T的輸入輸出集中在變遷上，因此對(duì)DFSM-T的覆蓋準(zhǔn)則采用DFSM中常用的變遷覆蓋準(zhǔn)則[10].變遷覆蓋準(zhǔn)則是指由變遷構(gòu)成的測(cè)試路徑集合覆蓋DFSM-T中的所有變遷至少一次.

1.2 DFSM-T模型構(gòu)建

定義2(數(shù)據(jù)塊) 數(shù)據(jù)塊DB是一個(gè)二元組(L,S)，其中L={l(c1),l(c2),…,l(cn)}，是一組有序變量的標(biāo)識(shí)，l(ci)是變量ci的唯一標(biāo)識(shí)；S={V1(L),V2(L),…,Vm(L)}是有序取值組序列，其中每個(gè)取值組Vj(L)={v(c1),v(c2),…,v(cn)}是與L中變量順序相對(duì)應(yīng)的一組變量取值.

在建模過(guò)程中，輸入輸出的內(nèi)容用DB表示.則DFSM-T模型的每個(gè)變遷表示在某個(gè)通信時(shí)機(jī)輸入某個(gè)數(shù)據(jù)塊中的一個(gè)取值組；然后在某個(gè)通信時(shí)機(jī)輸出某個(gè)數(shù)據(jù)塊中的一個(gè)取值組.

根據(jù)被測(cè)設(shè)備的通信接口協(xié)議，歸納出影響功能場(chǎng)景的數(shù)據(jù)塊，并根據(jù)經(jīng)驗(yàn)將最有利于發(fā)現(xiàn)其他條件對(duì)功能影響的取值(控制條件取值)組置于取值組序列的第1個(gè)位置.例如在測(cè)試某個(gè)選定軌道電路對(duì)其所處閉塞分區(qū)的影響時(shí)，需要將非選定軌道電路置于空閑狀態(tài)，以便于測(cè)試選定軌道電路對(duì)其所處閉塞分區(qū)的影響.

為了直觀的闡述DB和模型，對(duì)某抽象測(cè)試場(chǎng)景的DB進(jìn)行歸納如表1所示，建立的DFSM-T模型如圖1所示.其中，變遷上“/”左側(cè)表示輸入，右側(cè)表示輸出，默認(rèn)通信時(shí)機(jī)為x=T(被測(cè)設(shè)備通信周期)，null表示輸入或輸出的動(dòng)作為空.

表1 抽象測(cè)試場(chǎng)景的數(shù)據(jù)塊

1.3 測(cè)試路徑搜索

廣度優(yōu)先搜索(Breadth-First Search, BFS)和深度優(yōu)先搜索(Depth-First Search, DFS)是常用的測(cè)試路徑搜索算法[10].但由于深度優(yōu)先搜索需要不斷的回溯，以確定下一節(jié)點(diǎn)是否已被訪問(wèn).因此，本文采用廣度優(yōu)先搜索對(duì)DFSM-T模型搜索測(cè)試路徑，并使測(cè)試路徑集合滿(mǎn)足變遷覆蓋準(zhǔn)則，即覆蓋DFSM-T模型的所有變遷至少一次.但經(jīng)典BFS算法會(huì)因模型中存在自環(huán)變遷而使得某些測(cè)試路徑的冗余程度較高.例如圖1的模型利用BFS算法生成兩條測(cè)試路徑如圖2所示.因模型中存在自環(huán)變遷使得兩條測(cè)試路徑前3個(gè)變遷是相同的，導(dǎo)致兩條測(cè)試路徑冗余程度很高.

針對(duì)該問(wèn)題，提出改進(jìn)BFS算法，算法具體描述如下.

輸入：DFSM-T模型.

輸出：滿(mǎn)足變遷覆蓋準(zhǔn)則的測(cè)試路徑集合.

1)去除DFSM-T模型中所有的自環(huán)變遷，并生成自環(huán)變遷集合L；

2)利用廣度優(yōu)先搜索對(duì)去除自環(huán)變遷的DFSM-T模型搜索測(cè)試路徑，生成測(cè)試路徑集合P；

3)對(duì)于L中的每個(gè)自環(huán)變遷，在P中搜索包含自環(huán)變遷所在狀態(tài)的變遷且路徑長(zhǎng)度最短的測(cè)試路徑，將自環(huán)變遷插入到該測(cè)試路徑的相應(yīng)位置；

4)返回插入自環(huán)變遷的測(cè)試路徑集合P.

圖1模型利用改進(jìn)BFS生成的測(cè)試路徑集合包含1條測(cè)試路徑，如圖3所示，該條測(cè)試路徑覆蓋了圖1模型的所有變遷，能夠替代圖2中兩條冗余程度較高的測(cè)試路徑，減小了測(cè)試路徑集的規(guī)模.

2 測(cè)試用例生成

在測(cè)試用例生成過(guò)程中，首先把測(cè)試路徑中的時(shí)間約束離散化.然后，根據(jù)控制條件覆蓋準(zhǔn)則，利用CGA生成帶有通信時(shí)機(jī)的測(cè)試用例.

2.1 時(shí)間約束的邊界值分析

G(x)是對(duì)時(shí)間范圍的約束，利用邊界值分析，將時(shí)間約束離散化.邊界值分析的基本思想是利用輸入變量的最小值、略大于最小值的值、正常值、略小于最大值的值和最大值處的取值進(jìn)行測(cè)試[11].由于TCC具有固定的運(yùn)算周期，利用邊界值分析思想，將時(shí)間約束離散化為運(yùn)算周期的個(gè)數(shù)，提出G(x)中9種形式時(shí)間約束的離散取值，如表2所示.

表2 時(shí)間約束的離散取值

表2中M=m/T取整，N=n/T取整，m、n為時(shí)間取值且n>m.此外，下劃線標(biāo)記的取值是邊界值分析中的控制條件取值.例如對(duì)于xn，由于不存在最大周期數(shù)，因此只取最小周期數(shù)N+1和正常周期數(shù)2N+1.

圖3測(cè)試路徑中從s3到s0的變遷中存在x≤3T的時(shí)間約束，其N(xiāo)=3，離散化取值得到T，2T，3T三個(gè)取值，其中2T為控制條件取值.

2.2 控制條件覆蓋與算法

修正判定條件覆蓋(Modified Condition Decision Coverage, MC/DC)，在每個(gè)判定中的每個(gè)條件都曾獨(dú)立影響判定的結(jié)果至少一次(獨(dú)立影響的意思是在其他條件不變的情況下，改變一個(gè)條件)[12].例如，(A||B&&C)，如果B對(duì)結(jié)果獨(dú)立起作用，A必須為False、C必須為T(mén)rue，則B取True和False各一次對(duì)結(jié)果起獨(dú)立影響.MC/DC測(cè)試已被廣泛應(yīng)用于列控系統(tǒng)設(shè)備軟件的白盒測(cè)試過(guò)程中，其優(yōu)勢(shì)在于用很少的用例測(cè)試每個(gè)條件獨(dú)立對(duì)結(jié)果的影響.

在黑盒測(cè)試中，由于不能準(zhǔn)確獲取判定條件的邏輯關(guān)系，無(wú)法應(yīng)用MC/DC測(cè)試.但借鑒MC/DC測(cè)試的思想，當(dāng)測(cè)試某選定條件對(duì)功能的影響時(shí)，控制其他條件處于有利于發(fā)現(xiàn)選定條件對(duì)功能影響的狀態(tài).

定義3(控制條件覆蓋)在測(cè)試過(guò)程中，受多個(gè)條件影響的功能，每次只改變其中某一個(gè)條件的取值，而控制其他條件的取值保持不變，從而測(cè)試選定條件對(duì)功能相對(duì)獨(dú)立的影響，將這種測(cè)試覆蓋準(zhǔn)則稱(chēng)為控制條件覆蓋.

設(shè)測(cè)試條件有n個(gè)，為C={c1,c2,…，cn}，每個(gè)條件ci可在離散序列Si中取值，取值個(gè)數(shù)為mi=|Si|.其中，每個(gè)條件的控制條件取值位于Si的第1個(gè)位置.此外，每個(gè)ci具有一個(gè)標(biāo)識(shí)，用于標(biāo)記該條件的取值是否在其他情況下已被覆蓋.CGA的具體步驟描述如下.

輸入：n個(gè)測(cè)試條件C.

輸出：n個(gè)測(cè)試條件的取值組集合G.

1)將每個(gè)測(cè)試條件的控制條件取值(即Si的第1個(gè)取值)組成一個(gè)取值組，加入G；

2)對(duì)于C中的每個(gè)測(cè)試條件ci，如果該測(cè)試條件尚未被覆蓋，則對(duì)于Si中的每個(gè)非控制條件取值，與其他測(cè)試條件的控制條件取值構(gòu)成一個(gè)取值組，加入G；

3)返回n個(gè)測(cè)試條件的取值組集合G；

2.3 算法的應(yīng)用

對(duì)測(cè)試路徑中的每個(gè)變遷，輸入動(dòng)作需要轉(zhuǎn)換為具體的輸入時(shí)間和接口數(shù)據(jù)，作為被測(cè)設(shè)備的激勵(lì)；而對(duì)于輸出動(dòng)作則無(wú)需轉(zhuǎn)換，因?yàn)檩敵鰟?dòng)作用于測(cè)試結(jié)果的檢查，被測(cè)設(shè)備的輸出結(jié)果只需符合輸出動(dòng)作的時(shí)間約束和內(nèi)容即可.

將輸入動(dòng)作的內(nèi)容作為一個(gè)條件，同時(shí)輸入動(dòng)作中時(shí)間約束作為另一個(gè)條件，利用CGA生成每個(gè)變遷的輸入取值組集合.例如圖3中，變遷s3→s0生成的輸入取值組集合包含4個(gè)取值組，分別為1,0,2T，1,0,T，1,0,3T和0,1,2T.

將測(cè)試路徑中每個(gè)變遷的輸入取值組集合作為條件，再次利用CGA即可生成測(cè)試路徑的可執(zhí)行測(cè)試用例.根據(jù)圖3的測(cè)試路徑中每個(gè)變遷的輸入取值組集合，利用CGA生成4條測(cè)試用例，其中第1條測(cè)試用例的輸入部分如表3所示，另外3條測(cè)試用例僅為s3→s0的輸入取值組不同.

表3 測(cè)試用例舉例

3 實(shí)例分析

區(qū)間改變運(yùn)行方向是TCC的重要功能之一，實(shí)現(xiàn)控制本站發(fā)車(chē)口到相鄰主站對(duì)應(yīng)發(fā)車(chē)口之間的運(yùn)行方向.其中，在正常改變運(yùn)行方向過(guò)程中分為接車(chē)方向改為發(fā)車(chē)方向(簡(jiǎn)稱(chēng)正改方)和發(fā)車(chē)方向改為接車(chē)方向(簡(jiǎn)稱(chēng)反改方)兩個(gè)場(chǎng)景.下面以正改方場(chǎng)景為例，對(duì)本文方法進(jìn)行驗(yàn)證.

3.1 正改方場(chǎng)景的DFSM-T模型

根據(jù)列控中心技術(shù)條件對(duì)正改方場(chǎng)景的功能需求以及接口規(guī)范對(duì)接口數(shù)據(jù)的描述，對(duì)正改方涉及的DB進(jìn)行歸納，每個(gè)DB的具體含義及包含的取值組數(shù)量如表4所示.其中選取db9舉例展示其所包含的取值組具體內(nèi)容，如表5所示.

表4 數(shù)據(jù)塊含義

表5 數(shù)據(jù)塊內(nèi)容舉例

根據(jù)正改方場(chǎng)景的工作流程，建立DFSM-T模型如圖4所示.其中共包括5個(gè)狀態(tài)，s0～s4分別表示接車(chē)方向、等待聯(lián)鎖的方向控制命令、等待鄰主站改方、等待本站及所轄中繼站改方、發(fā)車(chē)方向狀態(tài).

3.2 正改方場(chǎng)景的測(cè)試路徑

利用改進(jìn)BFS搜索正改方DFSM-T模型，共生成10條測(cè)試路徑，測(cè)試路徑及每條路徑所表達(dá)的含義如下：路徑s0→s1→s0：所轄中繼站非空閑，改方失?。籹0→s1→s0：所轄區(qū)段非空閑，改方失??；s0→s1→s0：所轄中繼站通信中斷，改方失?。籹0→s1→s0：主站間通信中斷，改方失??；s0→s1→s0：所轄中繼站有進(jìn)路，改方失敗；s0→s1→s0：主站有進(jìn)路，改方失敗；s0→s1→s0：鄰主站非空閑，改方失??；s0→s1→s2→s0：鄰主站拒絕改方請(qǐng)求，改方失敗；s0→s1→s2→s3→s0：驅(qū)動(dòng)改方超時(shí)，改方失??；s0→s1→s2→s3→s4→s4：改方成功.

3.3 正改方場(chǎng)景的測(cè)試用例

根據(jù)測(cè)試路徑1～10，利用CGA分別生成可執(zhí)行測(cè)試用例1、21、1、1、1、1、3、7、10、3條.其中以路徑10所生成的可執(zhí)行測(cè)試用例為例進(jìn)行展示見(jiàn)表6.

表6 路徑10的測(cè)試用例

表6中，每條測(cè)試用例的一行表示一次測(cè)試輸入和測(cè)試輸出；“-”表示本次輸入輸出未涉及或是不改變的接口數(shù)據(jù)；時(shí)間表示相對(duì)上一次測(cè)試輸入或測(cè)試輸出完成后的間隔時(shí)間.表6中3條測(cè)試用例交互的接口數(shù)據(jù)是相同的，不同之處在于第4個(gè)變遷中，相關(guān)繼電器在13 s內(nèi)動(dòng)作到位的時(shí)間約束產(chǎn)生了0.5、7、13 s 三種不同的通信時(shí)機(jī).

此外，依據(jù)文獻(xiàn)[13]，本文所生成的可執(zhí)行測(cè)試集滿(mǎn)足其中對(duì)正改方場(chǎng)景的測(cè)試需求.

3.4 方法有效性分析

本文方法與現(xiàn)有方法相比，其優(yōu)勢(shì)在于所生成的測(cè)試用例不僅表達(dá)了接口通信的內(nèi)容，同時(shí)提供了接口通信的時(shí)機(jī)，這使得自動(dòng)化測(cè)試環(huán)境能夠在特定的時(shí)間交互特定的內(nèi)容，滿(mǎn)足自動(dòng)化測(cè)試的需求.同時(shí)，將通信時(shí)機(jī)作為一個(gè)測(cè)試條件，能夠?qū)Ρ粶y(cè)系統(tǒng)的時(shí)間特性進(jìn)行充分測(cè)試.

4 結(jié)論

1)為了描述接口通信的時(shí)機(jī)，提出DFSM-T模型，使得模型既能表達(dá)輸入輸出的內(nèi)容，也能表達(dá)通信的時(shí)間約束.

2) 利用邊界值分析，將通信的時(shí)間約束離散化，既能提供通信時(shí)機(jī)，同時(shí)也能對(duì)功能場(chǎng)景的時(shí)間特性進(jìn)行充分測(cè)試.

3) 控制條件覆蓋準(zhǔn)則能測(cè)試選定條件對(duì)功能相對(duì)獨(dú)立的影響，能覆蓋影響功能場(chǎng)景的每個(gè)條件.

4) 利用本文方法生成的測(cè)試用例，既能表達(dá)通信內(nèi)容也能表達(dá)通信時(shí)機(jī)，滿(mǎn)足自動(dòng)化測(cè)試的需求.

本文方法在歸納構(gòu)造DB時(shí)依賴(lài)專(zhuān)家經(jīng)驗(yàn)，且工作量相對(duì)較大，在這些方面還有待進(jìn)一步研究.