劉思琪，張亞東，楊武東，童 音，饒 暢

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

1 引 言

列車運行控制系統(tǒng)保證列車安全、高效的運行，是現(xiàn)代鐵路信號系統(tǒng)中的關(guān)鍵設(shè)備[1].列控系統(tǒng)有許多基于軟件的安全相關(guān)功能，軟件缺陷可能導致安全功能失效，造成嚴重的行車事故.因此，為提高列控系統(tǒng)的安全性和可靠性，鐵路信號系統(tǒng)安全關(guān)鍵軟件的測試尤為重要[2].

基于模型的軟件測試方法(Model-based Software Testing)采用模型描述軟件需求，以測試覆蓋準則為依據(jù)，應(yīng)用圖論等算法生成測試用例，并對待測系統(tǒng)進行測試，測試效率與自動化程度高[3]，在鐵路信號安全關(guān)鍵軟件測試中得到了廣泛的研究和應(yīng)用.軟件測試中常用的模型有確定性有限狀態(tài)機(Deterministic Finite State Machine，DFSM)和UML狀態(tài)圖等模型.對于軟件測試方法中的不同模型，已有不少的測試理論與測試用例生成方法被提出.文獻[4-6]提出了基于模型生成測試路徑方法，但實際應(yīng)用時仍需從測試路徑自動生成可執(zhí)行測試用例.文獻[7]中基于模型測試用例自動生成方法，對于不同待測系統(tǒng)仍需一定的人工參與才能自動生成測試輸入.文獻[8]精確闡述了適用于不同場景下基于規(guī)格說明的邏輯覆蓋測試準則，應(yīng)用準則生成的測試用例常是抽象的，實例化后得到實際測試輸入.文獻[9]采用輸入域建模提取有限狀態(tài)機測試場景的測試輸入，但面對更復雜的有限狀態(tài)機遷移邏輯時，無法直接得到可執(zhí)行測試用例.列控系統(tǒng)安全關(guān)鍵軟件功能邏輯復雜、輸入空間龐大，基于模型的測試用例生成的結(jié)果主要為抽象的測試路徑，為自動生成直接用于列控系統(tǒng)安全關(guān)鍵軟件的測試執(zhí)行，仍需要可執(zhí)行的測試用例的生成方法.

本文選用DFSM描述系統(tǒng)行為，結(jié)合邏輯覆蓋與輸入空間劃分方法，對模型的測試路徑上各狀態(tài)間遷移條件生成滿足邏輯覆蓋準則的測試用例，并采用輸入空間劃分選取抽象的測試用例的實際測試輸入，自動生成待測系統(tǒng)可執(zhí)行的測試用例.最后，以CTCS-2級車載設(shè)備手動等級轉(zhuǎn)換的安全功能為例，展示該方法自動生成測試用例的過程.

2 基于DFSM模型的測試方法

DFSM能夠描述軟件在生命周期中的控制行為，表現(xiàn)為軟件所經(jīng)歷的狀態(tài)序列及引起狀態(tài)遷移的事件或條件，具有表現(xiàn)直觀、易于理解的優(yōu)點，在基于模型的測試方法中得到了廣泛應(yīng)用.DFSM由狀態(tài)與狀態(tài)間遷移構(gòu)成，狀態(tài)描述了當前等待遷移執(zhí)行的系統(tǒng)狀況，遷移是在條件滿足或事件發(fā)生時使DFSM從一個狀態(tài)轉(zhuǎn)至另一狀態(tài)的動作，通常代表單個或多個變量的值的變化[8].DFSM可用一個五元組(∑,S,s0,δ,F)表示[10]，其中，

·∑ 表示有限的、非空的輸入字符集；

·S表示有限的、非空的狀態(tài)集；

·s0∈S表示一個初始狀態(tài)；

·δ:S×∑→S表示狀態(tài)遷移函數(shù)；

·F?S表示終止狀態(tài)集合.

基于DFSM的軟件測試用例自動生成方法主要分為DFSM生成測試路徑、測試路徑實例化為測試用例兩個階段組成[10].第一階段為根據(jù)軟件結(jié)構(gòu)、規(guī)格說明等建立軟件功能邏輯的DFSM模型，并生成滿足圖覆蓋等準則的測試路徑，測試路徑即抽象測試用例，記錄了圖覆蓋準則下從s0狀態(tài)到f∈F狀態(tài)的所有遷移{(s0,si),…,(sj,sk),…,(sn,f)}.第二階段為實例化測試路徑為可執(zhí)行的測試用例.

3 測試用例生成基礎(chǔ)

3.1 邏輯覆蓋

邏輯覆蓋準則通過分析謂詞與子句邏輯關(guān)系，產(chǎn)生覆蓋某些子句、謂詞的邏輯取值的測試用例[11]，常應(yīng)用在基于模型的測試.DFSM的狀態(tài)遷移函數(shù)上通常定義使得遷移發(fā)生的特定變量的取值和引發(fā)遷移發(fā)生的變量值變化的觸發(fā)事件[8], 常表現(xiàn)為遷移條件邏輯表達式，在實際中可通過分析待測系統(tǒng)規(guī)格說明得到.由于邏輯覆蓋沒有標準的術(shù)語與符號，應(yīng)用邏輯覆蓋時通常將邏輯表達式形式化為謂詞[8].謂詞，是計算結(jié)果為布爾值的子句或者復合謂詞，其結(jié)構(gòu)由邏輯運算符(非)、∧(與)、∨(或)、→(蘊含)、⊕(異或)和?(等價)等構(gòu)成[8]，其中子句是不含任何邏輯運算符的謂詞[8]，有布爾變量和關(guān)系表達式兩種常見形式[12]，復合謂詞則是由若干個子句或其補和二元布爾運算符{∧,∨}構(gòu)成[13].子句形式之一的關(guān)系表達式是形如EopF的表達式，其中E和F均為由算數(shù)表達式，關(guān)系運算符op∈{≤,≥,<,>,=,≠}[13].僅由布爾變量、布爾運算符和括號構(gòu)成的謂詞稱為布爾表達式[13]，通過抽象語法樹提取布爾變量及關(guān)系表達式為葉節(jié)點，布爾運算符{,∧,∨}為內(nèi)部節(jié)點，得到其樹形結(jié)構(gòu)，用于自動化生成測試用例.在DFSM模型中，狀態(tài)遷移條件表現(xiàn)為邏輯表達式，并已形式化為謂詞，其中{,∧,∨}是軟件功能的DFSM模型常用的3種邏輯運算，本文針對這3種邏輯運算符的DFSM模型應(yīng)用邏輯覆蓋準則生成測試用例.常見的邏輯覆蓋準則有謂詞覆蓋、子句覆蓋和組合覆蓋三種[8].

1)謂詞覆蓋(PC)：對于謂詞集的每個謂詞，測試需求是謂詞取得真值，謂詞取得假值.

2)子句覆蓋(CC)：對于謂詞的每個子句，測試需求是子句取得真值，子句取得假值.

3)組合覆蓋(CoC)：對于謂詞集的每個謂詞，測試需求是謂詞中子句的所有邏輯值組合.

當謂詞中有n個獨立的子句，共有2n種可能的邏輯值組合.以(a=b)∧C為例，該謂詞包含2個獨立子句，有4種可能的邏輯值組合，以T代表True，F(xiàn)代表False，結(jié)果如表1.其中，滿足謂詞覆蓋的測試集有T1,2={1,2}、T1,3={1,3}、T1,4={1,4}，滿足子句覆蓋的有T1,4={1,4}、T2,3={2,3}，滿足組合覆蓋的有T1,2,3,4={1,2,3,4}.

表1 謂詞(a=b)∧C邏輯值組合與覆蓋結(jié)果表Table 1 Truth table of (a=b)∧C and results of coverage criteria

3.2 輸入空間劃分

輸入空間劃分的過程稱為輸入域建模，它根據(jù)待測系統(tǒng)的接口變量定義了輸入域，如圖1中輸入域D，再從規(guī)格說明中提取出用以劃分輸入域的特性C，將輸入域D劃分為包含同等作用值的、兩兩分離的b1、b2和b3三個塊，并從塊中選出有代表性的取值(如圖1中黑點)進行測試[8].

圖1 輸入域D劃分示意圖Fig.1 Partition of input domain D

輸入域建模的方法分為基于接口的方法和基于功能的方法.基于接口的方法是單獨處理每個被測函數(shù)的變量xi，識別的特性僅限于一個單獨的變量，易于對xi進行劃分塊取值.基于功能的方法的輸入域模型包含了一些功能語義或者專業(yè)知識，其特性通過分析被測系統(tǒng)的一個行為或功能來開發(fā)，產(chǎn)生的測試用例比基于接口的方法可能更接近測試目標，但識別特性經(jīng)常不能夠匹配待測系統(tǒng)接口的變量，難以生成可執(zhí)行用例[8].軟件需求規(guī)格描述了軟件的各項需求，各項功能的具體含義等內(nèi)容，對基于規(guī)格說明的DFSM模型進行輸入域建模時，被測函數(shù)是狀態(tài)間的遷移條件，函數(shù)變量是遷移條件中的變量.遷移條件包含了待測系統(tǒng)的功能語義，從遷移條件開發(fā)出的特性既能從功能上劃分輸入域，又能與遷移條件中的變量匹配，提供了基于功能的方法識別特性后自動化選取變量取值的可能.

3.3 邏輯覆蓋與輸入空間劃分結(jié)合方法

根據(jù)邏輯覆蓋準則，DFSM的遷移條件生成的邏輯測試集是子句的邏輯值組合，常是抽象的測試用例.為使其與接口變量匹配，采用輸入空間劃分自動生成滿足邏輯值組合的接口變量測試輸入，并組成可執(zhí)行的測試用例.生成測試用例的過程見圖2，從測試路徑生成測試用例可分為以下3步：

圖2 測試用例生成過程圖Fig.2 Process of test cases generation

1)生成邏輯測試集.識別遷移條件的邏輯表達式結(jié)構(gòu)，生成滿足特定覆蓋準則的邏輯測試集.

2)生成變量取值集.通過變量定義與遷移條件提取特性，采用基于功能的輸入域建模方法對待測系統(tǒng)建模，并計算出接口變量取值集.

3)生成測試用例.結(jié)合邏輯測試集與變量取值集，得出與邏輯測試集中各測試項子句邏輯值匹配的接口變量測試輸入.若對應(yīng)一次測試的變量輸入組合有多種，則采用全排列方法，生成所有可能組合的可執(zhí)行測試輸入，最終與其他測試項的測試輸入組合成滿足特定邏輯覆蓋的測試用例.

4 基于輸入域和邏輯覆蓋的測試用例生成

4.1 生成邏輯測試集

基于DFSM模型的測試路徑是一組遷移序列，其中各遷移條件的邏輯表達式，通常被形式化為謂詞形式.邏輯覆蓋準則中的謂詞覆蓋準則的測試需求是每個謂詞集合中的謂詞需取得真值和假值[8].下面以該準則為例說明測試用例生成過程.表1中謂詞(a=b)∧C，T1,2={((a=b)=true,C=true),((a=b)=true,C=false)} 這兩項的測試集滿足了謂詞覆蓋準則.在實際中，為實現(xiàn)自動生成滿足邏輯覆蓋準則的邏輯值組合，首先需要構(gòu)建邏輯表達式的抽象語法樹.為降低構(gòu)建語法樹的難度，選用布爾變量分別替換謂詞中關(guān)系表達式，轉(zhuǎn)換其為布爾表達式，再通過識別布爾運算符構(gòu)建語法樹.謂詞(a=b)∧C，由關(guān)系表達式(a=b)和布爾變量C這2個子句組成，將其中(a=b)用布爾變量D替換，謂詞將轉(zhuǎn)換為布爾表達式D∧C，再構(gòu)建其語法樹并生成真值表，再從中取出滿足謂詞覆蓋準則的邏輯值組合構(gòu)成了邏輯測試集(logical tests).生成邏輯測試集的算法1如下：

算法1.generate logical tests

Input:logical expression

Output: logical tests

1.extractclausesfromlogicalexpression

2.forclauseinclausesdo

3.ifclauseis a relation expression

4.thenrenameclausewithbyname

5.endif

6.endfor

7.transformlogicalexpressiontobooleanexpression

8.generateabstractsyntaxtree

9.generatetruthtable

10.select specificlogicaltestitems and store inlogicaltests

4.2 生成變量取值集

基于功能的輸入域建模生成變量取值集時，狀態(tài)間的遷移條件邏輯表達式(logic expression)視為待測函數(shù)，遷移條件中變量為接口變量，通過從DFSM變量的定義與遷移條件中相應(yīng)子句提取劃分特性，將變量輸入域劃分為塊(blocks).劃分塊是變量可能值的集合，為了從集合自動選出變量值，采用取值策略(如有效值、無效值和邊界值等)選取，綜合后將得到子句中變量的取值集合(variable values).其中，邊界值策略認為在邊界或邊界附近是程序員進行軟件設(shè)計和開發(fā)時常出錯的地方[8]，需要進行測試.生成變量取值集的算法如算法2所示.

算法2.generate input domain values

Input: logic expression

Output: set of variable values

1.extractclausesfromlogicexpression

3. identifycharacteristicsfromclauseandvariable′sdefinition

4. createblocksforcharacteristics

5.forblockinblocks

6. selectvaluesfromblockunder strategy

7. addvaluesintovariablevalues

8.endfor

9. addvariablevaluesintosetofvariablevalues

10.end for

式中:x=(xS1,yS1,xS2,yS2,…,xSN,ySN)表示2N維的決策變量,y表示2維的目標向量;f1(x),f2(x)分別是節(jié)點安全連通度目標函數(shù)和節(jié)點網(wǎng)絡(luò)覆蓋率目標函數(shù);?i∈[1,N],?j∈[1,N],i≠j,滿足d(Si,Sj)≤Rc是節(jié)點的全連通約束,其中d(Si,Sj)表示節(jié)點Si,Sj之間的歐氏距離;為節(jié)點移動能耗約束,為節(jié)點優(yōu)化后與節(jié)點最初位置之間的距離,dth是節(jié)點允許移動的最大值。

4.3 生成測試用例

邏輯覆蓋準則考察的是邏輯運算符，生成的邏輯測試集中一次測試的邏輯值組合是謂詞中各子句的測試值，但這些測試值常常是抽象的，未匹配待測系統(tǒng)接口變量，要與輸入空間劃分的結(jié)果結(jié)合轉(zhuǎn)為實際變量的測試輸入.兩者結(jié)合算法見算法3.

算法首先對邏輯測試集中每一條測試項(logical test)中各元素(element)，應(yīng)計算出滿足當前元素邏輯值的變量取值集合(expected values).當計算出當前輸入項對應(yīng)的所有變量取值集合之后，將其視為整體，采用全排列方法或其他組合辦法，以各取值集合為單個的排列變量，集合中的值視作變量的取值，對變量進行組合，生成多種測試輸入組合.然后，對邏輯測試集中剩余測試項重復上述過程，得到各測試項的測試輸入集合(set of test input).最后，組合各測試項的測試輸入集合，得到滿足邏輯覆蓋準則的、可執(zhí)行的測試用例(test cases).

算法3.generate executable test cases

Input: logical tests, set of variable values, logic expression

Output: test cases

1.forlogicaltestinlogicaltestsdo

2.forelementinlogicaltestdo

3. get relativeclausefromlogicexpression

4. getvariablefromclause

5. getvariablevaluesfromsetofvariablevalues

6.forvariablevalueinvariablevaluesdo

7. getresultby substituting thevariablevaluetoclause

8.iftheresultmatches theelement′svalue

9.thenrecord the currentvariablevaluetoexpectedvalues

10.endif

11.endfor

12.endfor

13. combine allexpectedvaluesand store insetoftestinput

14.endfor

15.combine allsetoftestinputand generatetestcases

5 案例研究

列控系統(tǒng)領(lǐng)域的DFSM模型圖的狀態(tài)用圓圈表示，終止狀態(tài)用雙圈表示，狀態(tài)間遷移用帶箭頭的線表示.系統(tǒng)進入初始狀態(tài)后開始工作，并根據(jù)變量的變化遷移至目標狀態(tài).狀態(tài)間的遷移條件通常反應(yīng)了接口變量之間的邏輯關(guān)系，主要由關(guān)系表達式與布爾表達式組成.本節(jié)以CTCS-2車載設(shè)備等級轉(zhuǎn)換中手動切換功能為例，說明從DFSM模型生成測試用例的具體過程.

5.1 等級轉(zhuǎn)換功能有限狀態(tài)機模型

等級轉(zhuǎn)換發(fā)生在CTCS-2(簡稱C2)區(qū)段與CTCS-0(簡稱C0)區(qū)段的邊界.當C0級下車載設(shè)備不能自動切換等級時，若條件允許，司機可進行手動切換等級至C2級[14].該功能的DFSM模型如圖3所示.

圖3 CTCS-0級手動切換CTCS-2級的DFSM模型Fig.3 DFSM of CTCS-0/CTCS-2 manual level transition function

如圖3，車載設(shè)備進入Start狀態(tài)后初始化為C0等級狀態(tài)，檢測到司機手動選擇C2等級后，轉(zhuǎn)入C2手動切換狀態(tài)；若列車正在輸出制動且當前等級為C0級，則C2手動狀態(tài)轉(zhuǎn)回C0狀態(tài)；若列車未輸出制動、列車速度滿足要求、當前狀態(tài)等級為C0且司機手動選擇C2等級四個條件同時滿足，C2手動狀態(tài)將轉(zhuǎn)至C2等級狀態(tài).

從DFSM得出一條測試路徑P，遷移分別是{(Start,C0),(C0,C2-ManuSwitch),(C2-ManuSwitch,C0),(C0,C2-ManuSwitch),(C2-ManuSwitch,C2-State),(C2-State,End)}.其中(C2-ManuSwitch,C2-State)的遷移條件的子句、變量、子句含義見表2.

表2 樣例遷移條件表達式元素表Table 2 Elements in sample transition expression

5.2 測試用例生成

本小節(jié)以 C2-ManuSwitch轉(zhuǎn)C2-State的遷移條件為例，介紹生成測試用例的具體過程.

1)生成邏輯測試集.通過解析遷移條件表達式，獲得所有子句并用布爾變量替換謂詞中關(guān)系表達式，將謂詞轉(zhuǎn)為布爾表達式，建立遷移條件的抽象語法樹后求出條件表達式的所有的邏輯值組合，從中選出滿足謂詞覆蓋準則的邏輯值組合構(gòu)成了邏輯測試集.樣例遷移條件包含四個子句，其中關(guān)系表達式Speed<250.0替換為布爾變量Speed-250.0 ，遷移條件變?yōu)椴紶柋磉_式，并構(gòu)建抽象語法樹，得到子句的十六種邏輯值組合.

其中上述4個子句{LKJBrake, Speed<250.0, CurLevelCTCS0, DrvOperCTCS2}邏輯值組合為{T,T,T,T}時，表達式值為F，而四個子句邏輯值為{F,T,T,T}時，表達式值為T.由謂詞覆蓋準則定義可知，{T,T,T,T}與{F,T,T,T}這兩條測試項滿足了謂詞分別為假與真的謂詞覆蓋測試需求，因此，從由這兩項測試項組成的邏輯測試集滿足了謂詞覆蓋準則.

2)初始化變量取值集合.基于功能的輸入域建模方法通過遷移條件中功能信息提取特性，以float型變量Speed為例，在關(guān)系表達式Speed<250.0與變量Speed的定義中提取出選取"Speed大于0且小于250km/h"特性，劃分輸入空間為Speed大于0且小于250km/h、 大于等于250km/h兩個塊，并選取有效取值范圍中間值、以5為步長選取邊界的附近值和邊界值為測試值，符合了有效值、無效值、邊界值的取值策略，變量取值集合見表3，而遷移條件中LKJBrake等為布爾型變量，取值集包括其所有可能值.

表3 樣例表達式各變量取值集Table 3 Set of variables values in sample expression

3)生成測試用例.以測試項中{LKJBrake=F,Speed<250.0=T,CurLevelCTCS0=T,DrvOperCTCS2=T}為例，在子句中依次代入對應(yīng)變量值，通過計算結(jié)果并判斷其是否與子句邏輯值一致，求出變量取值集中所有滿足子句邏輯值的取值，{F, T, T, T}測試項的變量輸入子集如表4.以子句Speed<250.0為例，測試項要求該子句取值為T，因此需要求出Speed變量取值集合中小于250.0的值.

表4 樣例輸入項與變量輸入子集Table 4 Sample test input and subset of variables inputs

由于4個變量(LKJBrake, Speed, CurLevelCTCS0, DrvOperCTCS2)的取值可能組合不唯一，本次采用全排列生成4條可執(zhí)行的測試輸入，分別為：

(F,0.0,T,T)、(F,5.0,T,T)、(F,125.0,T,T)、(F,245.0,T,T).

對于謂詞覆蓋測試集中的另一條測試項{T, T, T, T}，再次進行上述過程，也可得到生成4條測試輸入，分別為：

(T,0.0,T,T)、(T,5.0,T,T)、(T,125.0,T,T)、(T,245.0,T,T).

謂詞覆蓋準則需對兩種邏輯值組合進行測試，對于上述兩項測試項有多種可能測試輸入時，為使每種輸入至少執(zhí)行一次，需要至少四個滿足謂詞覆蓋準則的可執(zhí)行測試用例，見表5.以其中可執(zhí)行測試用例{(F,0.0,T,T),(T,0.0,T,T)}為例，該用例測試了速度為0、當前等級為CTCS-0且司機手動選擇了CTCS-2時，列車輸出制動與未輸出制動兩種等級轉(zhuǎn)換的情況.路徑P中各遷移條件的測試用例見表5.

表5 路徑P各遷移條件測試用例表Table 5 Test cases for transitions in path P

由此可見，結(jié)合輸入空間的各種輸入條件所生成的測試用例覆蓋了更多的測試情況與實際的臨界條件，可測出軟件邊界情況存在的軟件缺陷，實現(xiàn)了在各種輸入場景下對鐵路相關(guān)軟件系統(tǒng)的測試，提高了軟件的可靠安全性.

6 結(jié) 論

本文針對基于DFSM的軟件測試方法中測試路徑生成測試用例的過程，結(jié)合輸入空間劃分和邏輯覆蓋準則，提出了含連續(xù)型變量的遷移條件自動生成測試用例方法.以CTCS-2級車載設(shè)備人工等級轉(zhuǎn)換的安全功能為例，對其DFSM模型測試路徑生成了多種測試情況下的測試用例，減少了軟件測試中測試用例配置的工作量與測試值選取的盲目性.本文提出的方法已經(jīng)在CTCS-2級車載設(shè)備軟件測試中得到應(yīng)用，實踐表明本方法具備良好的可操作性，能產(chǎn)生可執(zhí)行測試用例.今后，在輸入空間的劃分及如何取值和邏輯表達式特殊結(jié)構(gòu)方面將做進一步研究，提高方法的適用度.