基于決策樹等價的CBTC 列控車載TSM 監(jiān)控曲線測試案例約簡方法

張 芳，李開成，羅正偉，魏國棟，呂繼東

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 組合測試案例套件約簡方法

2.1 組合測試

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

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

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

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

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

2.2 決策樹等價

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

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

文獻［18］給出了5 種決策樹等價關系的定義.本文中，引入結(jié)構等價和誤分類等價來約簡測試套件.注意，結(jié)構等價關系是誤分類等價關系的一個子集.

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

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

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

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

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

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

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

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

2）誤分類等價.誤分類率（Misclassification Rate，MR）是誤分類等價關系的基礎，所以在引入誤分類等價之前定義MR.

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

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

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

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

2.3 測試套件約簡算法

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

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

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

3 組合測試案例套件約簡實驗

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

圖4 組合測試案例套件約簡流程Fig.4 Combinatorial test suite reduction process

3.1 組合測試案例套件生成

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

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

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

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

MCR 值越大，對應測試套件的故障檢測能力越強.初始組合測試案例套件相關的數(shù)據(jù)如表3 所示.

表2 測試案例Tab.2 Test cases

表3 初始組合測試案例套件的相關信息Tab.3 Information about the initial combinatorial test suite

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

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

3.3 組合測試案例套件約簡

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

3.4 約簡實驗結(jié)果分析與比較

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

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

式中：TS 是初始測試套件；RTS 是約簡后測試套件.

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

圖5 關于約簡率的實驗結(jié)果Fig.5 Experimental results on reduction rate

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

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

式中：VSTS指的是TS 里包含t值模式；TS 是初始測試套件；RTS 是約簡后測試套件.

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

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

3）故障檢測能力.在實驗中，約簡后的測試套件被用來測試已植入變異體的SUT.為了更直觀地衡量約簡前后測試套件故障檢測能力的變化，計算各種約簡類型對應的MCR 值，見表4.

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

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

4 結(jié)論

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

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

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

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