王 碩，張亞東，郭 進(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)級列控系統(tǒng)核心的地面設(shè)備之一，主要完成軌道電路編碼、區(qū)間信號機(jī)點燈控制、區(qū)間方向控制等安全苛求功能.其功能邏輯的失效將危及行車安全，造成嚴(yán)重的事故.為了保證TCC功能的安全性，在投入使用前必須進(jìn)行一系列嚴(yán)格的測試.近年來，隨著自動化測試的興起，我國主要TCC廠家陸續(xù)研發(fā)了自動化測試平臺，但自動生成測試用例的問題仍未得到有效解決，成為TCC自動化測試的瓶頸.

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

1)基于測試需求和測試計劃建立測試模型；

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

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

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

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

1 模型與測試路徑

1.1 DFSM-T模型定義

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

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

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

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

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

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

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

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

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

表1 抽象測試場景的數(shù)據(jù)塊

1.3 測試路徑搜索

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

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

輸入：DFSM-T模型.

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

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

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

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

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

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

2 測試用例生成

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

2.1 時間約束的邊界值分析

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

表2 時間約束的離散取值

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

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

2.2 控制條件覆蓋與算法

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

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

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

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

輸入：n個測試條件C.

輸出：n個測試條件的取值組集合G.

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

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

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

2.3 算法的應(yīng)用

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

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

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

表3 測試用例舉例

3 實例分析

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

3.1 正改方場景的DFSM-T模型

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

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

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

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

3.2 正改方場景的測試路徑

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

3.3 正改方場景的測試用例

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

表6 路徑10的測試用例

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

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

3.4 方法有效性分析

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

4 結(jié)論

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

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

3) 控制條件覆蓋準(zhǔn)則能測試選定條件對功能相對獨立的影響，能覆蓋影響功能場景的每個條件.

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

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