CTCS-2級列控車載ATP組合測試用例集生成方法

饒 暢，郭 進，張亞東，查 志

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

CTCS-2級列控系統(Chinese Train Control System, Level-2)基于軌道電路和點式應答器傳輸列車行車許可信息，采用目標-距離速度防護模式監控列車運行，是保證列車安全、高效運行的重要系統之一[1]。CTCS-2級列控系統由地面設備和車載設備組成，其中車載ATP(Automatic Train Protection)設備承擔著監控列車速度、防止列車越過行車許可終點等安全功能，為SIL-4級(Safety Integrity Level-4)安全關鍵設備，若發生失效，輕則影響行車效率，重則導致嚴重的行車事故，其安全性要求非常高。

嚴格的測試能夠有效保證車載ATP的功能安全，其中核心問題之一是如何生成精簡有效的測試用例。現有針對列控系統(包括車載ATP)的測試用例生成方法，如文獻[2-6]等，普遍從功能模型和場景模型等角度入手開展研究。然而，車載設備的各種輸入接口對設備安全性也會產生重要影響[7]，不同輸入接口之間的交互組合往往會引發設備相關的軟件故障[8]，嚴重影響行車安全。因此，對車載ATP輸入接口進行組合測試具有重要意義。但在實際測試中，車載ATP接口輸入情況復雜，如果采用窮舉組合交互測試，往往不可行，而采用人工經驗進行組合交互測試，其效率低且測試效果有限。

組合測試理論針對該類問題，能在保證檢錯率的前提下，用較少測試用例高效完成測試工作[9]。文獻[10]提出一種基于回溯的城軌車載ATP的組合測試生成方法，測試效果顯著，但該方法效率較低，且不支持參數約束。通常，組合測試大都基于覆蓋數組進行[11]，其中生成精簡有效的覆蓋數組是一個重要的研究方向。最優覆蓋數組代表組合測試中，目前已知最精簡的覆蓋數組，其覆蓋極為緊湊。采用最優覆蓋數組完成組合測試，能夠在最大程度上控制測試成本。Torres等[12]采用模擬退火算法找到了若干目前已知最優的覆蓋數組，為基于最優覆蓋數組進行測試提供了可行性。然而，車載ATP輸入復雜，存在諸多輸入約束，限制了最優覆蓋數組在車載ATP測試中的直接應用。

針對該問題，本文提出了一種間接利用最優覆蓋數組的優勢，精簡生成車載ATP組合測試用例集的方法。首先，提出了參數映射算法，通過將車載ATP輸入參數映射到最優覆蓋數組的不同列，重構最優覆蓋數組，以提高對其的利用程度；其次，提出了覆蓋數組擴展算法，擴展重構后的數組，使之滿足約束條件且達到規定的組合強度；最后，基于以上算法進行了CTCS-2級列控車載ATP測試用例生成，并根據結果分析了本方法的可行性和有效性。

1 CTCS-2級列控車載ATP簡介

1.1 車載ATP及其測試環境

CTCS-2級列控車載ATP設備主要包含車載安全計算機、應答器傳輸模塊、安全輸入/輸出接口、軌道電路信息讀取器、測速測距單元和人機界面(DMI)等部分。其主要功能為界面顯示、列車速度測量、列車定位、靜態曲線比較、動態曲線計算以及行車許可和速度監控等。根據地面提供的軌道電路信息、線路靜態參數、臨時限速信息等，并結合動車組相關數據，生成目標-距離模式曲線，監控列車運行，保證列車的運行安全[13]。在實際運行中，車載ATP主要的運行場景有追蹤運行、等級切換和模式轉換等。車載ATP具有多種工作模式，用于支持不同的運行場景，包括待機模式(SB)、完全監控模式(FS)、調車模式(SH)及目視行車模式(OS)等。

由于CTCS-2級列控系統構成設備眾多，功能結構復雜，因此針對列控系統設備的測試通常被劃分在不同的階段進行。對于車載ATP，其測試過程包括實驗室仿真測試、互聯互通測試和現場聯調聯試等不同階段[14]。本文主要關注實驗室仿真測試階段，圍繞車載ATP的各項功能仿真測試展開研究，所構建的測試環境見圖1。

圖1 CTCS-2級車載ATP實驗室仿真測試環境

該測試環境包含仿真信息生成平臺、接口仿真平臺和被測車載ATP(含DMI)三部分。其中：仿真信息生成平臺用于在測試過程中生成車載ATP運行所需的人工操作、車輛運動和地面設備等各種環境仿真信息；接口仿真平臺用于將環境仿真信息實例化為滿足車載ATP接口規格的各種信號和數據，例如軌道電路信號、應答器報文和速度傳感器信號等，同時，接收來自車載ATP的輸出控制信息，并反饋給仿真信息生成平臺。

仿真信息生成平臺由列車操縱臺、車輛模擬器、地面模擬器及測試控制器等部分構成。其中：列車操縱臺提供與實際列車一致的操作對象供人工操作，如前進/后退手柄、牽引/制動手柄以及緊急制動按鈕等，同時還提供表示車載ATP狀態的指示燈用于觀測；車輛模擬器根據列車操縱臺的人工操作和車載ATP設備的控制輸出，實時計算列車當前的運動狀態(速度、位置等)，模擬列車走行；地面模擬器根據測試控制器的控制輸出，產生列車在走行過程中觸發的各類地面信息，例如軌道電路編碼信息、應答器信息等；測試控制器根據系統仿真狀態，適時控制觸發預先存儲的測試用例，并實時接收和展示車載ATP的工作狀態，供人工觀測記錄。

測試用例在測試環境中被實例化為自動觸發執行和人工操作執行兩部分。仿真信息生成平臺根據這兩部分的具體信息，并結合車載ATP輸出，生成各種仿真信息，通過接口仿真平臺作用于車載ATP，實現動態仿真測試。

1.2 車載ATP接口輸入參數

接口輸入參數表示仿真測試時，針對車載ATP的工作模式可人工操作輸入。由于車載ATP處于不同工作模式時，其輸入不盡相同，為便于表述，本文以車載ATP處于完全監控模式(FS模式)為例進行分析，其余的工作模式與之類似。根據車載ATP技術規范[15]及相關的功能規格，抽象出車載ATP接口輸入參數，見表1。

表1 車載ATP在FS模式下的相關輸入參數

鑒于技術規格和測試環境等限制，上述參數取值存在約束關系，不可忽略，否則將造成測試用例無效、測試不可行。根據車載ATP功能規格，總結出相關約束條件如下。

約束1仿真測試時駕駛臺應當處于激活狀態：p11=1。

約束2方向手柄不能處于既前進又后退的狀態：(p1=1∧p2=1)。

約束3牽引/制動手柄不能處于既牽引又制動的狀態：(p3=1∧p4=1)。

約束4實施緊急制動時，也需實施最大常用制動：p6=1→p5=1。

約束5不能同時向調車和目視行車模式轉換：(p8=1∧p9=1)。

約束6完全監控模式下不能進行CTCS 0/2的等級切換：(p12=1)。

2 研究基礎

2.1 相關定義

假設被測對象有n個輸入參數，每個參數均有有限非空的值域，對于給定的組合覆蓋強度t(t≤n)，組合測試的相關定義如下。

定義1k值模式：從n個參數中任取k個，每個參數在其取值范圍內取某個值構成的k元組，稱為一個k值模式。

定義2組合測試用例：對于n個輸入參數，每個參數在其取值范圍內取某個值構成的n元組，稱為一條組合測試用例。

一條組合測試用例即為一個n值模式，一條測試需求即為一個t值模式。約束條件描述組合測試用例在參數取值方面必須滿足限制關系。

定義3約束：一條約束為一個映射，將測試用例τ映射為布爾值true或false。

約束條件決定了測試用例的合法性，在組合測試實際應用中，約束條件可采用禁止元組(forbidden tuple)表示。

定義4禁止元組：為滿足約束條件，禁止在測試用例中出現的k值模式，稱為禁止元組。

例如要滿足上述車載ATP的測試約束條件3，那么需要避免在測試用例中出現禁止元組(p3.1，p4.1)。除有特別說明外，后文提及的“組合測試用例”均默認為滿足約束的組合測試用例。

定義5覆蓋：對于組合測試用例τ和t值模式σ，若輸入參數在τ和σ中具有相同的取值，那么稱τ覆蓋σ。

由組合測試用例構成的集合，稱為一個組合測試用例集，簡稱為測試用例集。

定義6t路組合覆蓋：給定測試用例集T，對于被測對象任意t個輸入參數對應的任一t值模式σ，若T中都至少存在一條測試用例覆蓋σ，那么稱T滿足t路組合覆蓋。

滿足t路組合覆蓋的測試用例集可采用覆蓋數組CA(Covering Array)表示。

定義7覆蓋數組：覆蓋數組CA(M;t,n,v)是一個M行n列的二維數組，每行可表示一條測試用例，M為覆蓋數組包含的測試用例總數，t為覆蓋強度，n為參數個數，v為參數取值個數。

CA具有如下性質：

(1)第i列對應的參數取值構成的集合大小為v。

(2)任意的M×t子數組包含了在相應值域上所有的t值模式。

(3)將CA的任意兩列互換，CA仍然滿足t路組合覆蓋。

具有最小行數的覆蓋數組即最優覆蓋數組，記為CAN(t,n,v)，簡寫為CAN。

2.2 基于最優覆蓋數組的組合測試

設被測對象的輸入參數為p1，p2，…，pn，每個輸入參數具有大小為v的值域，對于組合覆蓋強度t，基于最優覆蓋數組CAN進行組合測試。通常的做法是，首先找到一個覆蓋強度為t、列數為n且每列具有v個不同取值的最優覆蓋數組CAN(t,n,v)，然后按照下標對應關系，將參數pi映射到CAN的第i列(i=1，2，…，n)，通過參數映射，將CAN的每一行構造為一條測試用例。

車載ATP的接口輸入參數具有相同大小的值域，因此可基于最優覆蓋數組CAN進行測試。然而車載ATP的測試輸入中存在大量約束條件，采用現有方法，有可能造成輸入參數在映射到CAN的過程中，某些行出現禁止元組，導致這些行不滿足約束條件，無法用于實際測試，最終只能被移除。若CAN中需要移除的行越多，那么對于CAN的利用程度將會越低，需要額外補充的測試用例將會越多，在這種情況下，控制車載ATP的測試成本將會變得越困難。

3 車載ATP組合測試用例生成方法

本文針對現有方法面臨的問題，提出了一種基于最優覆蓋數組的帶約束組合測試用例集生成方法，其主要流程見圖2。

圖2 車載ATP組合測試用例生成流程

該方法包括兩步：①基于參數映射算法的最優覆蓋數組重構；②考慮約束的覆蓋數組擴展。最優覆蓋數組重構，即基于參數映射算法，采用貪婪映射策略，將車載ATP輸入參數映射到最優覆蓋數組CAN的不同列中，最大程度上保留滿足約束條件的行，移除最少量不滿足約束條件的行。覆蓋數組的擴展，即采用覆蓋數組擴展算法，在考慮約束的前提下，擴展前一步得到的子數組，得到滿足約束和覆蓋強度的測試用例集。

3.1 最優覆蓋數組重構

根據覆蓋數組的基本定義可知，對覆蓋數組進行列交換操作，將會改變數組相應位置上元素的取值，但并不會造成組合覆蓋丟失。對此，本文利用覆蓋數組的這一特性，針對車載ATP約束條件，通過交換CAN的列，對每行元素的取值進行重構，力求在最大程度上削減映射過程中出現的無效行數量，從而更好地利用CAN。

進行列交換操作，可看作將輸入參數按照一定關系映射到CAN的不同列。因此，重構CAN的關鍵在于找到一個最優的映射關系，使得映射后CAN的無效行數量最少。通過遍歷所有可能的映射方式，在理論上可找到一個最優的映射關系，但在實際情況中，往往不具備可行性。例如對于車載ATP，其參數的映射方式達到了13!=13×12×…×2×1=6 227 020 800種，完全遍歷不具備時間可行性。

鑒于此，本文提出了一種貪婪算法，來快速計算近似最優的列映射關系。該算法每次選擇一個未映射的參數，按照貪婪方式將該參數映射到CAN的某一列，算法循環執行直至所有參數均被映射。為便于說明流程，提出如下定義。

定義8敏感元組：禁止元組f的部分參數已經被映射，但另一部分參數還未被映射，將f在已被映射的參數上的投影稱為敏感元組。

例如，對于上述禁止元組(p3.1，p4.1)，若參數p3已經映射，但p4還未映射，那么稱1-值模式(p3.1)為一個敏感元組。

定義9無效行：對于CAN的某一行r，若r中已經被參數所映射的那部分，包含禁止元組，那么稱r為無效行。

定義10敏感行：對于CAN的某一行r，若r中已經被參數所映射的那部分，不含禁止元組但包含敏感元組，那么稱r為敏感行。

敏感行在映射過程中可能會轉變為無效行，造成更多行被移除。對此，本算法在映射參數時，根據無效行、禁止元組和敏感行對重構CAN的影響，按照優先考慮無效行最少，其次考慮禁止元組數量最多，最后考慮敏感行最少的原則完成參數映射，保持無效行數量最少。算法框架如下。

算法輸入：參數集P={p1,p2,…,pn}，CAN(t,k,v)，禁止元組集F。

算法輸出：CAN的子數組SCA，其中每一列均有參數映射。

開始

令SCA←CAN

令Q←?

for (inti=1 ton) 執行

if (pi?F) 執行

Q←Q∪{pi}; //Step1

else

令C←{c|c為SCA中未被參數映射的列};

基于字典序比較策略，完成映射pi→cmin，其中cmin∈C; //Step2

end if

end for

for (每個參數p∈Q) 執行

令C←{c|c為SCA中未被參數映射的列};

從C中取出一列，完成映射p→c; //Step3

end for

for (每行r∈SCA)

if (r包含禁止元組f∈F)

從SCA中移除r; //Step4

end if

end for

returnSCA;

結束

該算法主要包括以下4個步驟：

Step1參數約束性檢查。逐一檢查輸入參數是否出現在集合F相關的禁止元組中，若不出現，則將該參數加入非約束參數集Q，否則執行下一步。

Step2映射約束參數。基于字典序比較策略，將約束參數pi映射到SCA的某一列cmin。設參數pi映射到SCA的某一列，產生的無效行數量為n1，無效行包含的禁止元組數量為n2，敏感行數量為n3，則該步驟根據字典序[n1，n2，n3]比較，完成映射pi→cmin，即

(1)若SCA中僅存在一列c1，使得pi→c1產生的n1最少，則cmin=c1。

(2)若SCA中存在多個列，pi映射到其中任一列產生的n1均相同且最少，在這種情況下，檢查pi映射到其中任一列產生的n2數量。若僅存在一列c2，使得pi→c2產生的n1和n2都最少，則cmin=c2。

(3)若SCA中存在多個列，且映射pi到其中任一列產生的n1和n2均相同且都最少，在這種情況下，檢查pi映射任一列時產生的n3數量。若其中僅存在一列c3，使得pi→c3產生的n1，n2，n3都最少，那么cmin=c3。

(4)若SCA中存在多個列，且映射pi到其中任一列產生的n1，n2，n3均相同且都是最少的，則從這些列中任取一列作為cmin。

循環執行Step1和Step2直至所有約束參數完成映射，然后執行下一步。

Step3映射非約束參數。由于映射非約束參數不會增加無效行，因此，算法直接取出Q中參數，依次映射到CAN還未被映射的列中，完成所有參數的映射。

Step4根據約束條件，移除SCA中的無效行。

3.2 覆蓋數組擴展

重構最優覆蓋數組并移除無效行，有可能造成無效行中某些合法有效t值模式丟失覆蓋。設這些t值模式構成的集合為Π。為使得最終生成的車載ATP組合測試用例集既能滿足約束條件，又能實現對Π的全覆蓋，需要額外生成測試用例，擴展重構之后的數組。

本文提出一種基于one-test-at-a-time架構的組擴展算法，以每次構造若干候選測試用例、并選擇最佳候選測試用例的方式擴展數組，通過循環執行，直至對Π實現全覆蓋。設Π中t值模式對應的參數組合為Σ1，Σ2，…，Σm，Π(Σi)代表Π中屬于參數組合Σi的t值模式構成的集合，i={1，2，…，m}。算法的基本框架如下。

算法輸入：參數集P={p1,p2,…,pn}，覆蓋強度t，集合Π，子數組SCA，禁止元組集F。

算法輸出：滿足約束和覆蓋強度的SCA。

開始

令Σ←{Σ1,Σ2,…,Σm};

令T←?;

while (Π!=?) 執行

選擇Σmax∈Σ，使得對于?i∈{1,2,…,m}，Σi≠Σmax，都有|Π(Σi)|≤|Π(Σmax)|;

for (每一個σ∈Π(Σmax))

初始化候選測試用例τ←σ; //Step1

基于貪婪策略擴展τ; //Step2

T←T∪{τ};

end for

選擇τb∈T，使τb覆蓋Π中最多t值模式; //Step3

將τb加入SCA; //Step4

從Π中移除被τb覆蓋的t值模式;

end while

returnSCA;

結束

該算法主要包括以下4個步驟。

Step1初始化候選測試用例。在候選測試用例集T中，選擇|Π(Σi)|最大者完成候選測試用例的初始化。設被選中的參數組合為Σmax，算法將在T中總共構造|Π(Σmax)|條候選測試用例。對候選測試用例進行初始化，即對候選測試用例中，與Σmax相關的t個參數，由Π(Σmax)中一個t值模式進行賦值，對測試用例中其余的n-t個參數，暫不賦值。算法在該步驟初始化多個候選測試用例，目的在于通過嘗試更多的組合可能性，來找到覆蓋最多t值模式的最佳候選測試用例。

Step2擴展候選測試用例。對于每條候選測試用例τ∈T，算法采用貪婪策略，每次從Π中選擇一個t值模式σ，使用σ為τ的參數賦值。其中，σ需同時滿足以下3個條件：

(1)σ與τ的參數取值具有一致性。

(2)σ賦值給τ能夠滿足約束條件。

(3)σ賦值給τ能覆蓋到Π中最多t值模式。

在以上3個條件中：條件(1)的取值具有一致性，指參數在σ和τ中具有相同取值，或參數在σ中有具體取值，在τ中還未被賦值；對于條件(2)的測試用例約束檢查，本算法采用了文獻[16]提出的最小禁止元組(Minimum Forbidden Tuple)對比法，保證τ在擴展過程中始終滿足約束條件，不包含任何禁止元組和隱含元組(Implicit Tuple)；條件(3)為一個貪婪策略，目的在于快速擴展得到精簡且滿足要求的候選測試用例，在步驟2中將采用該策略連續擴展τ，直至τ中所有參數均被賦值，或無法再從Π中找到σ對τ賦值。

Step3選擇出最佳候選測試用例τb∈T，使τb相對于其他候選測試用例而言，能夠覆蓋到Π中最多t值模式。

Step4將τb作為新的一行加入SCA，并從Π中移除被τb覆蓋的t值模式。

重復執行Step1至Step4，直至Π為空。

4 車載ATP組合測試用例生成結果

本文基于Java平臺實現上述方法，生成了CTCS-2級列控車載ATP組合測試用例集。由于車載ATP在FS模式下，既能進行模式轉換，又能進行等級切換，也能維持在FS模式工作，為便于區分測試用例性質，提高測試針對性，本文按照車載ATP模式轉換、等級切換、維持在FS模式3種基本場景，分別生成與輸入參數相關的組合測試用例集。限于文章篇幅，這里以生成模式轉換場景相關的組合測試用例集為例進行詳細說明，其余2種場景與之類似，僅列出最終結果。

4.1 最優覆蓋數組重構

在模式轉換場景下，車載ATP的駕駛臺始終處于激活狀態，并且不能出現等級切換信號，此時參數p11=1，p12=0，p13=0。實際進行組合的參數為p1，p2，…，p10。圖3展示了在覆蓋強度t=2時，這些參數分別按照現有方法和按照本文方法完成映射后，最優覆蓋數組CAN(2,10,2)≤6的變化情況。其中，圖3(a)表示采用現有下標映射方式(pi→ci)構成的覆蓋數組，圖3(b)表示采用本文方法重新映射后構成的覆蓋數組，圖中灰色部分為無效行中包含的禁止元組。

圖3 最優覆蓋數組重構

從圖3中可以看出，重構前，采用現有參數映射方式將移除4行無效行(r2，r4，r5和r6)，而采用本文方法重構后僅移除2行(r4和r5)，提高了對最優覆蓋數組的利用。

4.2 覆蓋數組擴展

重構最優覆蓋數組，共造成32個合法有效的2-值模式丟失覆蓋，限于文章篇幅，這里不再詳細列出。

圖4展示了擴展覆蓋數組，覆蓋所有合法2-值模式后得到的覆蓋數組及完整的測試用例集。圖4中覆蓋數組的列順序已調整為參數的下標順序，虛框內綠色部分為對最優覆蓋數組的利用。

圖4 車載ATP模式轉換場景下的組合測試用例集

圖4(b)每一行代表一條測試用例，如第2行表示在FS模式下，將車載ATP方向手柄設置為向前、牽引手柄設置為牽引，模擬列車前進運行；然后在運行過程中，保持手柄狀態，并施加最大常用制動，測試車載ATP能否控制列車停車；最后待停車后，保持手柄狀態和最大常用制動，按壓調車鍵，測試車載ATP能否轉換為調車模式。

4.3 有效性分析

車載ATP為SIL-4級安全關鍵設備，其測試覆蓋準則相對于通用軟件而言要求更加嚴格[17]。本文基于最優覆蓋數組，還進行了更高強度的測試用例生成(t=2，3，4，5)。同時，為驗證方法的有效性，選取了以下3種方法與本文方法進行比較：①基于現有的參數映射方法生成測試用例集(以下簡稱為直接擴展法)；②基于主流工具PICT[18]生成測試用例集；③基于主流工具ACTS[19]生成測試用例集。基于直接擴展法生成測試用例集，即首先采用現有的參數下標映射方法，直接將參數映射到CAN并移除無效行；然后采用本文提出的擴展算法完成子數組的擴展，得到滿足約束的測試用例集。基于主流工具PICT和ACTS直接生成測試用例集，即首先根據輸入參數與約束條件構造組合測試的輸入模型，然后基于輸入模型，采用工具直接生成測試用例集。圖5展示了幾種方法分別在模式轉換、等級切換和維持在FS模式3種場景下的測試用例集生成結果(t=2，3，4，5)。

圖5 不同場景和覆蓋強度下的測試用例生成結果

由于車載ATP在等級切換和維持在FS模式2種場景下的有效組合參數均為8個，且具有相同的約束條件，因此同一方法2種場景中生成的測試用例數量也相同。圖5表明了在滿足約束條件和組合覆蓋強度的前提下，由本文方法產生的測試用例集普遍更加精簡。對于總共12個測試用例集，本文方法得到的結果，比直接擴展法更為精簡的達到7個，比PICT和ACTS更為精簡的達到10個。

特別地，在t=5時，對于模式轉換場景，采用本文方法生成的測試用例僅為96條，而在同等條件下，采用直接擴展法得到的結果為108條，采用PICT工具得到的結果為104條，采用ACTS工具得到的結果為103條。本文方法得到的結果相對于現有方法，最多可減少12條測試用例，測試用例集的規模減小幅度達到了11.11%。通過比較，驗證了本文方法的有效性。

此外，為驗證本文提出的參數映射算法的有效性，還比較了本文方法和直接擴展法在測試生成過程中對CAN的利用率，見圖6。

圖6 2種方法對于最優覆蓋數組的利用率

從圖6可看出，本文方法對CAN的利用率大都高于直接擴展法。尤其在t=2時，本方法對于覆蓋數組的利用率最高達到了83.33%(等級切換和維持在FS模式)。而在相同條件下，直接擴展法對于覆蓋數組的利用率僅為50%。在t=5時，本方法對CAN的利用率雖然僅為41.07%(模式轉換)，但仍然高于直接擴展法對CAN的利用率(35.71%)。通過對比分析，驗證了本文參數映射算法的有效性。

5 結論

(1)車載ATP是列控系統的核心設備之一，針對車載ATP接口輸入參數的組合測試在保障功能安全方面具有重要意義。

(2)最優覆蓋數組具有行數最少、覆蓋緊湊等特點，基于最優覆蓋數組完成組合測試，能有效控制測試成本。

(3)本文針對車載ATP的參數組合特點，提出了基于最優覆蓋數組的車載ATP組合測試用例集生成方法。結果表明，本方法能夠提高對于最優覆蓋數組的利用，在滿足約束和覆蓋準則的基礎上，實現了測試用例集的精簡生成，有效降低了車載ATP測試成本，提高了測試效率。