張 芳，李開(kāi)成，羅正偉，魏國(guó)棟，呂繼東

（北京交通大學(xué) 電子信息工程學(xué)院，北京 100044）

Communication Based Train Control 列控系統(tǒng)作為典型的安全苛求系統(tǒng)，其任何功能故障都可能造成嚴(yán)重的事故和生命財(cái)產(chǎn)的損失［1］.車載設(shè)備的目標(biāo)速度監(jiān)控（Target Speed Monitoring，TSM）監(jiān)控曲線功能，以目標(biāo)速度、目標(biāo)距離、線路條件、列車特性為基礎(chǔ)信息，生成列車安全運(yùn)行的一次制動(dòng)模式曲線，是實(shí)現(xiàn)列車超速防護(hù)功能、確保列車安全運(yùn)行的關(guān)鍵.然而，列控車載TSM 監(jiān)控曲線功能具有參數(shù)輸入域規(guī)模大、故障模式復(fù)雜等特點(diǎn)［2］，如何進(jìn)行有效測(cè)試，保障其功能的正確性至關(guān)重要.

傳統(tǒng)的列控車載設(shè)備功能測(cè)試主要采用一致性測(cè)試方法，通過(guò)利用被測(cè)設(shè)備可觀測(cè)的輸入/輸出一致性關(guān)系進(jìn)行測(cè)試案例的生成，取得了良好的效果.文獻(xiàn)［3］在測(cè)試列控系統(tǒng)時(shí)應(yīng)用了基于模型的測(cè)試方法并對(duì)該系統(tǒng)進(jìn)行建模驗(yàn)證了其安全功能的正確性.文獻(xiàn)［4］提出了一種基于Petri 網(wǎng)（Color Petri Net CPN）的測(cè)試案例生成算法，用于在列控系統(tǒng)的移動(dòng)授權(quán)切換場(chǎng)景中自動(dòng)生成測(cè)試案例集.近年來(lái)基于模型的測(cè)試方法也應(yīng)用于國(guó)內(nèi)新型列控系統(tǒng)的測(cè)試上.文獻(xiàn)［5］提出一種基于Timed Automata with Input and Output TAIO 變異分析的新型列控系統(tǒng)功能測(cè)試框架，基于車載模型生成上萬(wàn)個(gè)變異體模型和測(cè)試案例，提高了檢錯(cuò)能力.文獻(xiàn)［6］提出了基于在線一致性方法的CBTC 系統(tǒng)車載設(shè)備安全功能測(cè)試框架，實(shí)現(xiàn)了測(cè)試案例自動(dòng)生成，且案例能夠準(zhǔn)確檢測(cè)出故障，可見(jiàn)基于模型的測(cè)試方法可適應(yīng)列控系統(tǒng)大部分運(yùn)營(yíng)場(chǎng)景.然而，上述研究中被測(cè)設(shè)備和測(cè)試環(huán)境構(gòu)建一般基于典型的列控系統(tǒng)運(yùn)營(yíng)場(chǎng)景和故障模式，在實(shí)際測(cè)試時(shí)，測(cè)試案例會(huì)隨著覆蓋運(yùn)營(yíng)場(chǎng)景和故障模式的不同組合呈指數(shù)級(jí)增長(zhǎng).

近年來(lái)，組合測(cè)試受到了國(guó)內(nèi)外的廣泛關(guān)注，與傳統(tǒng)一致性測(cè)試直接覆蓋功能不同，組合測(cè)試是一種基于接口參數(shù)的測(cè)試，通過(guò)對(duì)輸入?yún)?shù)的組合覆蓋，間接覆蓋系統(tǒng)的功能.其基本思想是：以用較少的、可以滿足組合覆蓋標(biāo)準(zhǔn)的測(cè)試案例，檢測(cè)被測(cè)系統(tǒng)（System Under Test，SUT）中由參數(shù)交互觸發(fā)的故障［7］.文獻(xiàn)［8］采用正交拉丁方生成測(cè)試案例集，對(duì)Ada 編譯器進(jìn)行了測(cè)試，這也是最早將組合測(cè)試應(yīng)用到軟件測(cè)試中的實(shí)例.文獻(xiàn)［9］利用組合測(cè)試方法對(duì)具有大量軟硬件組合的OMX/StarMAIL 產(chǎn)品進(jìn)行了實(shí)例研究，通過(guò)自主研發(fā)工具OATS 生成的正交表形式測(cè)試案例集案例數(shù)量少且能夠檢測(cè)系統(tǒng)軟件故障，提高了測(cè)試效率.隨著組合測(cè)試研究的深入，組合測(cè)試方法在兼容性測(cè)試、GUI 測(cè)試、Web 應(yīng)用測(cè)試和高度可配置的系統(tǒng)中都有了廣泛的應(yīng)用.

在列控領(lǐng)域，組合測(cè)試也逐漸成為研究熱點(diǎn)，文獻(xiàn)［10］改進(jìn)了基于網(wǎng)絡(luò)模型的組合測(cè)試案例生成算法，并將其運(yùn)用到CBTC 列控系統(tǒng)車載設(shè)備的功能測(cè)試中，滿足了實(shí)際的測(cè)試需求.在保證覆蓋率的前提下提高了CBTC 列控系統(tǒng)的測(cè)試效率.文獻(xiàn)［11］針對(duì)實(shí)際CBTC 系統(tǒng)車載設(shè)備建立了組合測(cè)試模型，并利用基于解空間樹的組合測(cè)試案例生成算法自動(dòng)生成了覆蓋多參數(shù)組合的測(cè)試案例集，實(shí)現(xiàn)了對(duì)系統(tǒng)故障的快速定位.文獻(xiàn)［12］提出了一套適用聯(lián)鎖軟件的組合測(cè)試框架并且設(shè)計(jì)了一套自動(dòng)化組合測(cè)試系統(tǒng)，極大地約簡(jiǎn)了測(cè)試案例的數(shù)量和測(cè)試的操作步驟.文獻(xiàn)［13］提出了一種基于組合測(cè)試的全自動(dòng)運(yùn)行（Fully Automatic Operation，F(xiàn)AO）系統(tǒng)自動(dòng)測(cè)試案例生成方法，并取得了良好效果.雖然組合測(cè)試已經(jīng)成功應(yīng)用到車載子系統(tǒng)測(cè)試中，但是由于在實(shí)際測(cè)試中覆蓋了沒(méi)有交互的參數(shù)組合，由此會(huì)產(chǎn)生一定數(shù)量的冗余測(cè)試案例.因此，為了進(jìn)一步提高車載設(shè)備測(cè)試的效率，需要在保證故障檢測(cè)能力的前提下，盡量約簡(jiǎn)組合測(cè)試案例套件的規(guī)模.

組合測(cè)試案例套件約簡(jiǎn)的常用方法是通過(guò)參數(shù)之間的約束來(lái)移除不滿足條件的測(cè)試案例.但由于約束識(shí)別通常是手工完成的，因此該方法存在效率低的問(wèn)題［14］.文獻(xiàn)［15］針對(duì)兩兩組合測(cè)試案例套件提出了一種基于程序不變量的約簡(jiǎn)算法，可以減少測(cè)試案例的數(shù)量.然而，為了提取程序不變量，必須預(yù)先設(shè)置一定的模板.由于模板的數(shù)量是固定的，所以目前可以檢測(cè)到的不變量的形式也是固定的，這限制了該方法的實(shí)際應(yīng)用.文獻(xiàn)［16］提出了一種基于語(yǔ)句覆蓋和變異覆蓋信息的組合測(cè)試案例套件約簡(jiǎn)方法.不過(guò)，由于獲取測(cè)試案例對(duì)應(yīng)覆蓋信息的成本較高，該方法難以應(yīng)用于復(fù)雜系統(tǒng).

本文作者提出了一種基于決策樹等價(jià)的組合測(cè)試案例套件自動(dòng)約簡(jiǎn)方法.其基本思想是每個(gè)組合測(cè)試案例套件及其系統(tǒng)相應(yīng)輸出標(biāo)簽可以在一定程度上捕獲SUT 的某些行為.首先，結(jié)合t-way 參數(shù)覆蓋的組合測(cè)試案例及其輸出構(gòu)造捕獲SUT 行為的數(shù)據(jù)集，并采用CART 算法將數(shù)據(jù)集推理出決策樹；其次，設(shè)計(jì)了改進(jìn)的組合測(cè)試案例約簡(jiǎn)算法，利用決策樹結(jié)構(gòu)等價(jià)和誤分類等價(jià)關(guān)系約簡(jiǎn)冗余的組合測(cè)試案例；最后，利用約簡(jiǎn)算法在CBTC 列控車載TSM 監(jiān)控曲線功能上進(jìn)行了實(shí)例分析，相關(guān)實(shí)驗(yàn)結(jié)果表明，該方法可以達(dá)到高達(dá)74%的約簡(jiǎn)率，同時(shí)約簡(jiǎn)前后，測(cè)試套件的低層次組合覆蓋率和故障檢測(cè)能力基本一致.

1 CBTC 列控車載TSM 監(jiān)控曲線

CBTC 列控系統(tǒng)包括地面設(shè)備，車載設(shè)備和數(shù)據(jù)傳輸設(shè)備.CBTC 系統(tǒng)充分利用通信傳輸手段，實(shí)時(shí)或定時(shí)地進(jìn)行列車與地面設(shè)備間的雙向通信，區(qū)域控制器ZC 根據(jù)前車的位置信息、線路障礙物的狀態(tài)信息以及聯(lián)鎖設(shè)備狀況為后車計(jì)算行車許可（Movement Authority，MA），即行駛權(quán)限；車載設(shè)備根據(jù)地面?zhèn)魉偷臄?shù)據(jù)與預(yù)先儲(chǔ)存的列車數(shù)據(jù)計(jì)算出列車行駛時(shí)最大允許速度，并對(duì)列車運(yùn)行的實(shí)時(shí)速度進(jìn)行監(jiān)督和控制.系統(tǒng)的整體架構(gòu)圖如圖1 所示.

圖1 CBTC 列車運(yùn)行控制系統(tǒng)整體架構(gòu)Fig.1 Overall architecture diagram of CBTC

速度監(jiān)控曲線是列車運(yùn)行過(guò)程中所有位置的限制速度構(gòu)成的速度—距離曲線，用于監(jiān)控列車實(shí)時(shí)速度.該曲線可分為頂棚速度監(jiān)控區(qū)、目標(biāo)速度監(jiān)控區(qū)和安全距離區(qū).列車在運(yùn)行過(guò)程中一旦觸發(fā)速度監(jiān)控曲線，應(yīng)采取相應(yīng)的制動(dòng)措施，限制列車運(yùn)行速度，保證行車安全.

根據(jù)TSM 防護(hù)曲線的生成原理，通過(guò)前方目標(biāo)點(diǎn)位置及目標(biāo)速度生成動(dòng)態(tài)距離監(jiān)控曲線［11］.目標(biāo)速度監(jiān)控區(qū)內(nèi)各速度曲線的名稱和關(guān)系，如圖2所示.

圖2 目標(biāo)速度監(jiān)控曲線Fig.2 Target speed monitoring curve

圖2 中，根據(jù)安全制動(dòng)模型首先得到緊急制動(dòng)觸發(fā)曲線EBI，然后再依次算出常用制動(dòng)觸發(fā)曲線SBI、報(bào)警曲線W和允許速度曲線P.

2 組合測(cè)試案例套件約簡(jiǎn)方法

2.1 組合測(cè)試

假設(shè)SUT 參數(shù)的pi(i=1，2，…，n)，可以表示配置參數(shù)、用戶輸入等.參數(shù)或它們之間的相互作用可能會(huì)影響SUT.另外，假設(shè)參數(shù)pi有來(lái)自有限集合Vi的ai個(gè)離散取值.參數(shù)間的相互作用實(shí)際上是參數(shù)值的組合所產(chǎn)生的交互.當(dāng)這些參數(shù)的特定值一起作用時(shí)，可能會(huì)觸發(fā)軟件故障.為了更好地說(shuō)明本文的工作，下面給出組合測(cè)試相關(guān)的定義.

定 義1 值模式：對(duì) 于SUT，n元 組（-，，...)被稱為t值模式（t＞0），其中t個(gè)參數(shù)有確定的值，而其他參數(shù)可以使用它們各自的允許值（可以表示為“-”）.當(dāng)t=n時(shí)，n元組內(nèi)每個(gè)參數(shù)都有確定的值，即為SUT 的測(cè)試案例［17］.

定義2 測(cè)試套件：根據(jù)組合覆蓋準(zhǔn)則生成的測(cè)試套件是多個(gè)測(cè)試案例的集合.每個(gè)測(cè)試案例tc可以是n元組，表示為(v1，v2，...，vn)(v1∈V1，v2∈V2，...，vn∈Vn).

定義3 t-way 組合覆蓋：如果一個(gè)測(cè)試套件包含任意t個(gè) 參數(shù)值的所有組合()，其中1 ≤t≤n，即包含所有的t值模式，則可以認(rèn)為它滿足t-way 組合覆蓋.

定義4 SUT 模型：SUT 模型可以表示為一個(gè)4 元 組：ModelSUT(P，V，R，C)，其 中P是參數(shù)的集合，V是參數(shù)的取值集合，R是參數(shù)間交互關(guān)系的集合，C是不同參數(shù)值之間的約束集合.

2.2 決策樹等價(jià)

決策樹（Decision Tree，DT）可以表示為（N，E），由節(jié)點(diǎn)N和節(jié)點(diǎn)之間的邊E組成.節(jié)點(diǎn)可分為決策節(jié)點(diǎn)和葉節(jié)點(diǎn).一個(gè)決策節(jié)點(diǎn)代表一個(gè)決策（即一個(gè)關(guān)系方程）.每個(gè)葉節(jié)點(diǎn)代表一個(gè)分類，可以是一個(gè)離散的輸出值.樹的根節(jié)點(diǎn)是一個(gè)只有輸出邊的決策節(jié)點(diǎn).

定義幾個(gè)函數(shù)以便后續(xù)解釋決策樹等價(jià)關(guān)系.函數(shù)Rn：DT →N，返回決策樹的根節(jié)點(diǎn)，并將整個(gè)決策樹DT 考慮為輸入域.函數(shù)Rc：DT →D∪C，返回一個(gè)節(jié)點(diǎn)的內(nèi)容，范圍是決策集合D和分類集合C的并集.函數(shù)Rl：DT →C，返回決策樹所有葉子節(jié)點(diǎn)的內(nèi)容，即分類.決策的結(jié)果由邊的標(biāo)簽表示，通過(guò)函數(shù)Re：E→{T，F(xiàn)}訪問(wèn).

文獻(xiàn)［18］給出了5 種決策樹等價(jià)關(guān)系的定義.本文中，引入結(jié)構(gòu)等價(jià)和誤分類等價(jià)來(lái)約簡(jiǎn)測(cè)試套件.注意，結(jié)構(gòu)等價(jià)關(guān)系是誤分類等價(jià)關(guān)系的一個(gè)子集.

1）結(jié)構(gòu)等 價(jià)：兩個(gè)決策樹DT1=(N1，E1)和DT2=(N2，E2)在結(jié)構(gòu)上是等價(jià)的，當(dāng)且僅當(dāng)每一個(gè)節(jié)點(diǎn)n1∈N1有一個(gè)對(duì)應(yīng)的節(jié)點(diǎn)n2∈N2，每一個(gè)邊e1∈E1有一個(gè)對(duì)應(yīng)的邊e2∈E2，且對(duì)應(yīng)邊兩端的節(jié)點(diǎn)是一一對(duì)應(yīng)的.結(jié)構(gòu)等價(jià)可以用函數(shù)EQUAL：N×N→{True，F(xiàn)alse}表示.對(duì)于兩個(gè)決策樹DT1、DT2，節(jié) 點(diǎn)n1∈N1、n2∈N2，函 數(shù)EQUAL 輸 出True，當(dāng)且僅當(dāng)：

①Rc(n1)=Rc(n2)（即相應(yīng)節(jié)點(diǎn)的內(nèi)容必須是一致的）

②|{(n1，m1)|m1是n1的子節(jié)點(diǎn)}|=|{(n2，m2)|m2是n2的子節(jié)點(diǎn)}|（即邊的數(shù)量相當(dāng)）

③?(n1，m1)?(n2，m2)，使 得［（m1是n1的子節(jié)點(diǎn)）∧（m2是n2的子節(jié) 點(diǎn)）∧(Re(n1，m1)=Re(n2，m2))∧EQUAL(m1，m2)]成 立（即相應(yīng)的輸出邊、子決策樹必須是等價(jià)的）

否則，EQUAL 函數(shù)返回False.利用該函數(shù)，兩個(gè)決策樹的結(jié)構(gòu)等價(jià)定義如下：

定義 5 結(jié)構(gòu)等價(jià)：兩個(gè)給定的決策樹DT1，DT2是結(jié)構(gòu)等價(jià)的，當(dāng)且僅當(dāng)函數(shù)EQUAL(Rn(DT1)，Rn(DT2))返回True.

圖3 顯示了兩個(gè)在結(jié)構(gòu)上等價(jià)的決策樹.注意，兩個(gè)決策樹在相同位置的節(jié)點(diǎn)內(nèi)容和邊的標(biāo)簽是相同的.

圖3 結(jié)構(gòu)等價(jià)和誤分類等價(jià)Fig.3 Structural equivalence and misclassification equivalence

2）誤分類等價(jià).誤分類率（Misclassification Rate，MR）是誤分類等價(jià)關(guān)系的基礎(chǔ)，所以在引入誤分類等價(jià)之前定義MR.

定義6 誤分類率：決策樹（N，E）的誤分類率為誤分類樣本數(shù)與所有分類樣本數(shù)之比.即錯(cuò)誤分類的樣本集的大小MDS ?DS 與初始數(shù)據(jù)集的大小之比.

兩個(gè)決策樹DT1=(N1，E1)和DT2=(N2，E2)是誤分類等價(jià)的，當(dāng)且僅當(dāng)(N2，E2)誤分類率小于或等于的誤分類率(N1，E1)，并且相應(yīng)分類集合C包含的元素一致.

定義7 誤分類等價(jià)：當(dāng)對(duì)數(shù)據(jù)集DS 進(jìn)行分類時(shí)，決策樹DT2=(N2，E2)與參考決策樹DT1=(N1，E1)誤分類等價(jià)，當(dāng)且僅當(dāng)

假 設(shè)DS 包含兩 個(gè)樣本s1=(8，10，2) 和s2=(2，5，2)，那么圖3 誤分類等價(jià)中的兩個(gè)決策樹誤分類等價(jià)，但在結(jié)構(gòu)上不是等價(jià)的.

2.3 測(cè)試套件約簡(jiǎn)算法

所提出的測(cè)試套件約簡(jiǎn)算法在很大程度上依賴于決策樹推理和等價(jià)關(guān)系.在本文中，應(yīng)用了廣泛使用的CART 算法［19］，從數(shù)據(jù)集推理出決策樹，并且采用結(jié)構(gòu)等價(jià)和誤分類等價(jià)來(lái)判斷決策樹是否等價(jià).

該算法的約簡(jiǎn)策略是通過(guò)等價(jià)關(guān)系不斷判斷分別從初始數(shù)據(jù)集DS 和約簡(jiǎn)后數(shù)據(jù)集（Reduced Data Set，RDS）學(xué)習(xí)到的兩個(gè)決策樹模型是否等價(jià)，直到滿足設(shè)置的條件為止.如果它們相等，表示測(cè)試套件TS（對(duì)應(yīng)于DS）和約簡(jiǎn)后的測(cè)試套件（Reduced Test Suite，RTS）（對(duì)應(yīng)于RDS）具有相同的能力覆蓋系統(tǒng)的某些特征，那么RDS 繼續(xù)隨機(jī)刪除一個(gè)樣本s，否則重新添加s并隨機(jī)刪除另一個(gè)樣本.注意，開(kāi)始時(shí)RDS 和DS 是相同的.

此外，本文算法是對(duì)文獻(xiàn)［21］所提算法的改進(jìn)，特別是保證盡可能地最小化TS.為了達(dá)到更好的約簡(jiǎn)效果，算法中有兩個(gè)循環(huán).單次外層循環(huán)是一個(gè)完整的約簡(jiǎn)過(guò)程，會(huì)保持更新best RDS 以便取得盡可能小規(guī)模的測(cè)試套件.此外，在內(nèi)層循環(huán)中，設(shè)置了DDS 記錄所有可能被刪除的樣本.決策樹是通過(guò)計(jì)算熵來(lái)構(gòu)造的，反映了數(shù)據(jù)集中的某種平衡.由于在該算法中，一次最多刪除一個(gè)樣本，所以存在這樣一種可能性：為了保持平衡，一些樣本只能在其他樣本被刪除后才被刪除.因此，每當(dāng)兩個(gè)決策樹模型等價(jià)時(shí)，DDS 被更新為與RDS 一致，以盡可能地去除冗余樣本.對(duì)內(nèi)層循環(huán)的退出條件進(jìn)行改進(jìn)，將其設(shè)置為對(duì)剩余樣本遍歷判斷后均無(wú)法刪除.在該算法中，DS 是對(duì)應(yīng)于TS 初始數(shù)據(jù)集，Iterations 聲明了約簡(jiǎn)的迭代次數(shù)，F(xiàn)TS 是最終約簡(jiǎn)后的組合測(cè)試案例套件，M是TS 殺死的變異體集合.假設(shè)較約簡(jiǎn)前，初步約簡(jiǎn)后測(cè)試套件未殺死變異體個(gè)數(shù)為|Mu|，則補(bǔ)充的測(cè)試案例的個(gè)數(shù)不超過(guò)|Mu|，即可保證約簡(jiǎn)前后殺死變異體個(gè)數(shù)一致.

3 組合測(cè)試案例套件約簡(jiǎn)實(shí)驗(yàn)

CBTC 列控TSM 功能的組合套件約簡(jiǎn)過(guò)程如圖4 所示，主要分為組合測(cè)試案例套件生成、數(shù)據(jù)預(yù)處理、測(cè)試套件約簡(jiǎn)、約簡(jiǎn)實(shí)驗(yàn)結(jié)果分析與比較4部分.

圖4 組合測(cè)試案例套件約簡(jiǎn)流程Fig.4 Combinatorial test suite reduction process

3.1 組合測(cè)試案例套件生成

本部分主要對(duì)前期組合測(cè)試案例套件生成實(shí)驗(yàn)進(jìn)行補(bǔ)充說(shuō)明.本文所研究的SUT 指的是在CBTC列控車載安全計(jì)算機(jī)上運(yùn)行的核心軟件.車載設(shè)備有多種工作模式，其中CBTC-CM：受控人工駕駛（Code Train Operating Mode）具有最完整的速度監(jiān)控功能（包括TSM）.因此，前期實(shí)驗(yàn)都是在CM 模式下進(jìn)行的.

結(jié)合“城市軌道交通CBTC 信號(hào)系統(tǒng)-ATP 子系統(tǒng)規(guī)范”［20］，采用等價(jià)類劃分和邊值分析等方法，提取SUT 中涉及速度監(jiān)控功能的參數(shù)及取值，如表1 所示（為了更簡(jiǎn)潔地描述測(cè)試套件生成過(guò)程，參數(shù)值僅用符號(hào)代替）.SUT 模型中，參數(shù)R的取值為2-way、3-way、4-way，且參數(shù)C暫不被考慮.基于SUT 模型和文獻(xiàn)［21］所提出的經(jīng)典的IPOG 算法，生成初始組合測(cè)試案例套件.之后，使用TS 對(duì)SUT 進(jìn)行測(cè)試，并取得系統(tǒng)相應(yīng)的輸出結(jié)果.

表1 SUT 模型相關(guān)參數(shù)及取值Tab.1 SUT model related parameters and values

此外，為衡量測(cè)試套件的故障檢測(cè)能力，引入了變異測(cè)試并生成了3 126 個(gè)變異體.在組合測(cè)試過(guò)程中，如果變異前后SUT 的輸出不一致，可以認(rèn)為對(duì)應(yīng)的變異體被殺死，相反則是存活的.變異覆蓋率（Mutation Coverage Rate，MCR）定義為

MCR 值越大，對(duì)應(yīng)測(cè)試套件的故障檢測(cè)能力越強(qiáng).初始組合測(cè)試案例套件相關(guān)的數(shù)據(jù)如表3 所示.

表2 測(cè)試案例Tab.2 Test cases

表3 初始組合測(cè)試案例套件的相關(guān)信息Tab.3 Information about the initial combinatorial test suite

3.2 數(shù)據(jù)預(yù)處理

在前期實(shí)驗(yàn)中，收集初始組合測(cè)試案例套件在SUT 上的測(cè)試結(jié)果.結(jié)合SUT 規(guī)范和工作模式等信息，對(duì)結(jié)果進(jìn)行分析，分為：觸發(fā)緊急制動(dòng)（O1）、觸發(fā)常用制動(dòng)（O2）和無(wú)制動(dòng)觸發(fā)（O3）三類標(biāo)簽.即當(dāng)組合測(cè)試案例套件作為SUT 的輸入時(shí)，這三類標(biāo)簽可象征SUT 的輸出，形成標(biāo)簽數(shù)據(jù)集LDS.最后，結(jié)合TS 和相應(yīng)的LDS，構(gòu)建一個(gè)數(shù)據(jù)集DS，用來(lái)推理決策樹模型.

3.3 組合測(cè)試案例套件約簡(jiǎn)

在約簡(jiǎn)實(shí)驗(yàn)中，使用前文中提出的約簡(jiǎn)算法和CPU 為i5-4210U CPU、內(nèi)存為4G 的筆記本電腦作為實(shí)驗(yàn)平臺(tái).約簡(jiǎn)實(shí)驗(yàn)的可配置參數(shù)是t-way 組合覆蓋、決策樹等價(jià)關(guān)系和算法迭代Iterations.相關(guān)參數(shù)的具 體取值如下t-way 取2，3，4；Iterations 取1～5.結(jié)構(gòu)等價(jià)和錯(cuò)誤分析等價(jià).由于約簡(jiǎn)算法是隨機(jī)刪除冗余測(cè)試案例，約簡(jiǎn)結(jié)果具有不確定性，為了保證實(shí)驗(yàn)結(jié)果的可靠性，論文針對(duì)不同類型的配置進(jìn)行了100 次重復(fù)實(shí)驗(yàn).

3.4 約簡(jiǎn)實(shí)驗(yàn)結(jié)果分析與比較

在本文中，t-way-s 和t-way-m 分別代表了兩種不同的約簡(jiǎn)類型，即結(jié)構(gòu)等價(jià)和誤分類等價(jià)在最小化滿足t-way 組合覆蓋的初始測(cè)試套件中的應(yīng)用.

1）測(cè)試套件規(guī)模：組合測(cè)試案例套件的規(guī)模在縮減后發(fā)生了變化.為了衡量這種變化的程度，定義約簡(jiǎn)率（Reduction Rate，RR）為

式中：TS 是初始測(cè)試套件；RTS 是約簡(jiǎn)后測(cè)試套件.

約簡(jiǎn)實(shí)驗(yàn)得到的結(jié)果如圖5 所示.一般情況下，在相同的條件下，Iterations（迭代次數(shù)）值越大，約簡(jiǎn)算法的循環(huán)次數(shù)越多，得到的RR 越高.當(dāng)然，迭代的值并不需要很大，就可以得到一個(gè)較高的約簡(jiǎn)率.此外，初始組合測(cè)試案例套件的大?。ㄅct-way 覆蓋相關(guān)）與約簡(jiǎn)程度之間存在正相關(guān)關(guān)系.這是因?yàn)樵诖笠?guī)模測(cè)試套件中出現(xiàn)冗余測(cè)試案例的可能性更大.

圖5 關(guān)于約簡(jiǎn)率的實(shí)驗(yàn)結(jié)果Fig.5 Experimental results on reduction rate

在約簡(jiǎn)實(shí)驗(yàn)中，基于誤分類等價(jià)的約簡(jiǎn)結(jié)果往往優(yōu)于基于結(jié)構(gòu)等價(jià)的約簡(jiǎn)結(jié)果.在不考慮剪枝的情況下，基于不同等價(jià)關(guān)系得到?jīng)Q策樹模型DT2 與初始決策樹模型DT1，在輸入輸出關(guān)系上一致（TS作為輸入情況下）.然而，通過(guò)結(jié)構(gòu)等價(jià)得到的模型DT2-s 的結(jié)構(gòu)與DT1 完全一致，而通過(guò)誤分類等價(jià)得到的模型DT2-m 的結(jié)構(gòu)與DT1 并不要求相同.因此，在約簡(jiǎn)實(shí)驗(yàn)中，模型DT2-m 越容易被推理出現(xiàn)，測(cè)試案例被約簡(jiǎn)的概率越大，相應(yīng)的約簡(jiǎn)程度也越高.

2）t-way 組合覆蓋率.由于某些參數(shù)之間沒(méi)有交互作用，優(yōu)化后的組合測(cè)試案例套件可能不會(huì)有100% 的t-way 組合覆蓋率（Combination Coverage Rate，CCR）.但是，CCR 作為組合測(cè)試衡量測(cè)試套件覆蓋率的特定指標(biāo)，仍然具有一定的參考意義，其定義如下

式中：VSTS指的是TS 里包含t值模式；TS 是初始測(cè)試套件；RTS 是約簡(jiǎn)后測(cè)試套件.

約簡(jiǎn)前后CCR 的變化如圖6 所示，約簡(jiǎn)后測(cè)試套件的CCR（1-way）仍然是100%.此外，CCR（3-way）和CCR（4-way）都有很大的損失，這是由于大規(guī)模刪除冗余測(cè)試案例造成的.值得注意的是，當(dāng)約簡(jiǎn)類型為4-way-s 或4-way-m 時(shí)，對(duì)應(yīng)的CCR（2-way）基本保持在100%左右，這反映經(jīng)過(guò)約簡(jiǎn)算法得到測(cè)試套件仍然具有一定完整的低層次的組合覆蓋能力.

圖6 t-way 組合覆蓋率的變化Fig.6 Changes in t-way combination coverage rate

3）故障檢測(cè)能力.在實(shí)驗(yàn)中，約簡(jiǎn)后的測(cè)試套件被用來(lái)測(cè)試已植入變異體的SUT.為了更直觀地衡量約簡(jiǎn)前后測(cè)試套件故障檢測(cè)能力的變化，計(jì)算各種約簡(jiǎn)類型對(duì)應(yīng)的MCR 值，見(jiàn)表4.

表4 測(cè)試套件的變異覆蓋率Tab.4 Mutation coverage rate of test suite %

當(dāng)約簡(jiǎn)后測(cè)試套件的MCR 值最優(yōu)時(shí)，可以與初始組合測(cè)試案例套件TS 對(duì)應(yīng)的值一致.當(dāng)約簡(jiǎn)類型為t-way-s 時(shí)，約簡(jiǎn)后測(cè)試套件的MCR 值更高.這是由于結(jié)構(gòu)等價(jià)關(guān)系是誤分類等價(jià)關(guān)系的一個(gè)子集，前者要求更嚴(yán)格，更完整地保留了測(cè)試套件的故障檢測(cè)能力.在約簡(jiǎn)實(shí)驗(yàn)中，約簡(jiǎn)后測(cè)試套件的MCR 損失不超過(guò)3.62%，為了使MCR無(wú)損失，根據(jù)初步約簡(jiǎn)后測(cè)試套件未殺死的變異集合，獲取約簡(jiǎn)前后損失的樣本集合，進(jìn)一步獲取可完全覆蓋M的樣本集合，可保證約簡(jiǎn)前后殺死變異體個(gè)數(shù)一致，這表明本文的組合測(cè)試案例套件約簡(jiǎn)算法在一定程度上是有效的.

4 結(jié)論

1）結(jié)合以往CBTC 列控TSM 功能組合測(cè)試案例套件生成實(shí)驗(yàn)結(jié)果，經(jīng)過(guò)數(shù)據(jù)預(yù)處理，構(gòu)建了基于測(cè)試套件和系統(tǒng)相應(yīng)輸出的、可用于決策樹推理的數(shù)據(jù)集.

2）設(shè)計(jì)了改進(jìn)的組合測(cè)試案例約簡(jiǎn)算法，利用決策樹結(jié)構(gòu)等價(jià)和誤分類等價(jià)關(guān)系約簡(jiǎn)冗余的組合測(cè)試案例在CBTC 列控車載TSM 監(jiān)控曲線功能上進(jìn)行了實(shí)例分析.相關(guān)實(shí)驗(yàn)結(jié)果表明，該方法可以實(shí)現(xiàn)較大的約簡(jiǎn)率RR.

3）約簡(jiǎn)后的測(cè)試套件可以在一定程度上實(shí)現(xiàn)低層次組合覆蓋CCR，并且相應(yīng)的變異覆蓋率MCR損失很小.

在后續(xù)的研究工作中，將重點(diǎn)關(guān)注決策樹剪枝策略對(duì)該方法的影響，以及如何確保約簡(jiǎn)后組合測(cè)試案例套件故障檢測(cè)能力不受損失.