饒 暢，郭 進(jìn)，張亞?wèn)|，查 志

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

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

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

組合測(cè)試?yán)碚撫槍?duì)該類(lèi)問(wèn)題，能在保證檢錯(cuò)率的前提下，用較少測(cè)試用例高效完成測(cè)試工作[9]。文獻(xiàn)[10]提出一種基于回溯的城軌車(chē)載ATP的組合測(cè)試生成方法，測(cè)試效果顯著，但該方法效率較低，且不支持參數(shù)約束。通常，組合測(cè)試大都基于覆蓋數(shù)組進(jìn)行[11]，其中生成精簡(jiǎn)有效的覆蓋數(shù)組是一個(gè)重要的研究方向。最優(yōu)覆蓋數(shù)組代表組合測(cè)試中，目前已知最精簡(jiǎn)的覆蓋數(shù)組，其覆蓋極為緊湊。采用最優(yōu)覆蓋數(shù)組完成組合測(cè)試，能夠在最大程度上控制測(cè)試成本。Torres等[12]采用模擬退火算法找到了若干目前已知最優(yōu)的覆蓋數(shù)組，為基于最優(yōu)覆蓋數(shù)組進(jìn)行測(cè)試提供了可行性。然而，車(chē)載ATP輸入復(fù)雜，存在諸多輸入約束，限制了最優(yōu)覆蓋數(shù)組在車(chē)載ATP測(cè)試中的直接應(yīng)用。

針對(duì)該問(wèn)題，本文提出了一種間接利用最優(yōu)覆蓋數(shù)組的優(yōu)勢(shì)，精簡(jiǎn)生成車(chē)載ATP組合測(cè)試用例集的方法。首先，提出了參數(shù)映射算法，通過(guò)將車(chē)載ATP輸入?yún)?shù)映射到最優(yōu)覆蓋數(shù)組的不同列，重構(gòu)最優(yōu)覆蓋數(shù)組，以提高對(duì)其的利用程度；其次，提出了覆蓋數(shù)組擴(kuò)展算法，擴(kuò)展重構(gòu)后的數(shù)組，使之滿(mǎn)足約束條件且達(dá)到規(guī)定的組合強(qiáng)度；最后，基于以上算法進(jìn)行了CTCS-2級(jí)列控車(chē)載ATP測(cè)試用例生成，并根據(jù)結(jié)果分析了本方法的可行性和有效性。

1 CTCS-2級(jí)列控車(chē)載ATP簡(jiǎn)介

1.1 車(chē)載ATP及其測(cè)試環(huán)境

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

由于CTCS-2級(jí)列控系統(tǒng)構(gòu)成設(shè)備眾多，功能結(jié)構(gòu)復(fù)雜，因此針對(duì)列控系統(tǒng)設(shè)備的測(cè)試通常被劃分在不同的階段進(jìn)行。對(duì)于車(chē)載ATP，其測(cè)試過(guò)程包括實(shí)驗(yàn)室仿真測(cè)試、互聯(lián)互通測(cè)試和現(xiàn)場(chǎng)聯(lián)調(diào)聯(lián)試等不同階段[14]。本文主要關(guān)注實(shí)驗(yàn)室仿真測(cè)試階段，圍繞車(chē)載ATP的各項(xiàng)功能仿真測(cè)試展開(kāi)研究，所構(gòu)建的測(cè)試環(huán)境見(jiàn)圖1。

圖1 CTCS-2級(jí)車(chē)載ATP實(shí)驗(yàn)室仿真測(cè)試環(huán)境

該測(cè)試環(huán)境包含仿真信息生成平臺(tái)、接口仿真平臺(tái)和被測(cè)車(chē)載ATP(含DMI)三部分。其中：仿真信息生成平臺(tái)用于在測(cè)試過(guò)程中生成車(chē)載ATP運(yùn)行所需的人工操作、車(chē)輛運(yùn)動(dòng)和地面設(shè)備等各種環(huán)境仿真信息；接口仿真平臺(tái)用于將環(huán)境仿真信息實(shí)例化為滿(mǎn)足車(chē)載ATP接口規(guī)格的各種信號(hào)和數(shù)據(jù)，例如軌道電路信號(hào)、應(yīng)答器報(bào)文和速度傳感器信號(hào)等，同時(shí)，接收來(lái)自車(chē)載ATP的輸出控制信息，并反饋給仿真信息生成平臺(tái)。

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

測(cè)試用例在測(cè)試環(huán)境中被實(shí)例化為自動(dòng)觸發(fā)執(zhí)行和人工操作執(zhí)行兩部分。仿真信息生成平臺(tái)根據(jù)這兩部分的具體信息，并結(jié)合車(chē)載ATP輸出，生成各種仿真信息，通過(guò)接口仿真平臺(tái)作用于車(chē)載ATP，實(shí)現(xiàn)動(dòng)態(tài)仿真測(cè)試。

1.2 車(chē)載ATP接口輸入?yún)?shù)

接口輸入?yún)?shù)表示仿真測(cè)試時(shí)，針對(duì)車(chē)載ATP的工作模式可人工操作輸入。由于車(chē)載ATP處于不同工作模式時(shí)，其輸入不盡相同，為便于表述，本文以車(chē)載ATP處于完全監(jiān)控模式(FS模式)為例進(jìn)行分析，其余的工作模式與之類(lèi)似。根據(jù)車(chē)載ATP技術(shù)規(guī)范[15]及相關(guān)的功能規(guī)格，抽象出車(chē)載ATP接口輸入?yún)?shù)，見(jiàn)表1。

表1 車(chē)載ATP在FS模式下的相關(guān)輸入?yún)?shù)

鑒于技術(shù)規(guī)格和測(cè)試環(huán)境等限制，上述參數(shù)取值存在約束關(guān)系，不可忽略，否則將造成測(cè)試用例無(wú)效、測(cè)試不可行。根據(jù)車(chē)載ATP功能規(guī)格，總結(jié)出相關(guān)約束條件如下。

約束1仿真測(cè)試時(shí)駕駛臺(tái)應(yīng)當(dāng)處于激活狀態(tài)：p11=1。

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

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

約束4實(shí)施緊急制動(dòng)時(shí)，也需實(shí)施最大常用制動(dòng)：p6=1→p5=1。

約束5不能同時(shí)向調(diào)車(chē)和目視行車(chē)模式轉(zhuǎn)換：(p8=1∧p9=1)。

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

2 研究基礎(chǔ)

2.1 相關(guān)定義

假設(shè)被測(cè)對(duì)象有n個(gè)輸入?yún)?shù)，每個(gè)參數(shù)均有有限非空的值域，對(duì)于給定的組合覆蓋強(qiáng)度t(t≤n)，組合測(cè)試的相關(guān)定義如下。

定義1k值模式：從n個(gè)參數(shù)中任取k個(gè)，每個(gè)參數(shù)在其取值范圍內(nèi)取某個(gè)值構(gòu)成的k元組，稱(chēng)為一個(gè)k值模式。

定義2組合測(cè)試用例：對(duì)于n個(gè)輸入?yún)?shù)，每個(gè)參數(shù)在其取值范圍內(nèi)取某個(gè)值構(gòu)成的n元組，稱(chēng)為一條組合測(cè)試用例。

一條組合測(cè)試用例即為一個(gè)n值模式，一條測(cè)試需求即為一個(gè)t值模式。約束條件描述組合測(cè)試用例在參數(shù)取值方面必須滿(mǎn)足限制關(guān)系。

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

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

定義4禁止元組：為滿(mǎn)足約束條件，禁止在測(cè)試用例中出現(xiàn)的k值模式，稱(chēng)為禁止元組。

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

定義5覆蓋：對(duì)于組合測(cè)試用例τ和t值模式σ，若輸入?yún)?shù)在τ和σ中具有相同的取值，那么稱(chēng)τ覆蓋σ。

由組合測(cè)試用例構(gòu)成的集合，稱(chēng)為一個(gè)組合測(cè)試用例集，簡(jiǎn)稱(chēng)為測(cè)試用例集。

定義6t路組合覆蓋：給定測(cè)試用例集T，對(duì)于被測(cè)對(duì)象任意t個(gè)輸入?yún)?shù)對(duì)應(yīng)的任一t值模式σ，若T中都至少存在一條測(cè)試用例覆蓋σ，那么稱(chēng)T滿(mǎn)足t路組合覆蓋。

滿(mǎn)足t路組合覆蓋的測(cè)試用例集可采用覆蓋數(shù)組CA(Covering Array)表示。

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

CA具有如下性質(zhì)：

(1)第i列對(duì)應(yīng)的參數(shù)取值構(gòu)成的集合大小為v。

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

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

具有最小行數(shù)的覆蓋數(shù)組即最優(yōu)覆蓋數(shù)組，記為CAN(t,n,v)，簡(jiǎn)寫(xiě)為CAN。

2.2 基于最優(yōu)覆蓋數(shù)組的組合測(cè)試

設(shè)被測(cè)對(duì)象的輸入?yún)?shù)為p1，p2，…，pn，每個(gè)輸入?yún)?shù)具有大小為v的值域，對(duì)于組合覆蓋強(qiáng)度t，基于最優(yōu)覆蓋數(shù)組CAN進(jìn)行組合測(cè)試。通常的做法是，首先找到一個(gè)覆蓋強(qiáng)度為t、列數(shù)為n且每列具有v個(gè)不同取值的最優(yōu)覆蓋數(shù)組CAN(t,n,v)，然后按照下標(biāo)對(duì)應(yīng)關(guān)系，將參數(shù)pi映射到CAN的第i列(i=1，2，…，n)，通過(guò)參數(shù)映射，將CAN的每一行構(gòu)造為一條測(cè)試用例。

車(chē)載ATP的接口輸入?yún)?shù)具有相同大小的值域，因此可基于最優(yōu)覆蓋數(shù)組CAN進(jìn)行測(cè)試。然而車(chē)載ATP的測(cè)試輸入中存在大量約束條件，采用現(xiàn)有方法，有可能造成輸入?yún)?shù)在映射到CAN的過(guò)程中，某些行出現(xiàn)禁止元組，導(dǎo)致這些行不滿(mǎn)足約束條件，無(wú)法用于實(shí)際測(cè)試，最終只能被移除。若CAN中需要移除的行越多，那么對(duì)于CAN的利用程度將會(huì)越低，需要額外補(bǔ)充的測(cè)試用例將會(huì)越多，在這種情況下，控制車(chē)載ATP的測(cè)試成本將會(huì)變得越困難。

3 車(chē)載ATP組合測(cè)試用例生成方法

本文針對(duì)現(xiàn)有方法面臨的問(wèn)題，提出了一種基于最優(yōu)覆蓋數(shù)組的帶約束組合測(cè)試用例集生成方法，其主要流程見(jiàn)圖2。

圖2 車(chē)載ATP組合測(cè)試用例生成流程

該方法包括兩步：①基于參數(shù)映射算法的最優(yōu)覆蓋數(shù)組重構(gòu)；②考慮約束的覆蓋數(shù)組擴(kuò)展。最優(yōu)覆蓋數(shù)組重構(gòu)，即基于參數(shù)映射算法，采用貪婪映射策略，將車(chē)載ATP輸入?yún)?shù)映射到最優(yōu)覆蓋數(shù)組CAN的不同列中，最大程度上保留滿(mǎn)足約束條件的行，移除最少量不滿(mǎn)足約束條件的行。覆蓋數(shù)組的擴(kuò)展，即采用覆蓋數(shù)組擴(kuò)展算法，在考慮約束的前提下，擴(kuò)展前一步得到的子數(shù)組，得到滿(mǎn)足約束和覆蓋強(qiáng)度的測(cè)試用例集。

3.1 最優(yōu)覆蓋數(shù)組重構(gòu)

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

進(jìn)行列交換操作，可看作將輸入?yún)?shù)按照一定關(guān)系映射到CAN的不同列。因此，重構(gòu)CAN的關(guān)鍵在于找到一個(gè)最優(yōu)的映射關(guān)系，使得映射后CAN的無(wú)效行數(shù)量最少。通過(guò)遍歷所有可能的映射方式，在理論上可找到一個(gè)最優(yōu)的映射關(guān)系，但在實(shí)際情況中，往往不具備可行性。例如對(duì)于車(chē)載ATP，其參數(shù)的映射方式達(dá)到了13!=13×12×…×2×1=6 227 020 800種，完全遍歷不具備時(shí)間可行性。

鑒于此，本文提出了一種貪婪算法，來(lái)快速計(jì)算近似最優(yōu)的列映射關(guān)系。該算法每次選擇一個(gè)未映射的參數(shù)，按照貪婪方式將該參數(shù)映射到CAN的某一列，算法循環(huán)執(zhí)行直至所有參數(shù)均被映射。為便于說(shuō)明流程，提出如下定義。

定義8敏感元組：禁止元組f的部分參數(shù)已經(jīng)被映射，但另一部分參數(shù)還未被映射，將f在已被映射的參數(shù)上的投影稱(chēng)為敏感元組。

例如，對(duì)于上述禁止元組(p3.1，p4.1)，若參數(shù)p3已經(jīng)映射，但p4還未映射，那么稱(chēng)1-值模式(p3.1)為一個(gè)敏感元組。

定義9無(wú)效行：對(duì)于CAN的某一行r，若r中已經(jīng)被參數(shù)所映射的那部分，包含禁止元組，那么稱(chēng)r為無(wú)效行。

定義10敏感行：對(duì)于CAN的某一行r，若r中已經(jīng)被參數(shù)所映射的那部分，不含禁止元組但包含敏感元組，那么稱(chēng)r為敏感行。

敏感行在映射過(guò)程中可能會(huì)轉(zhuǎn)變?yōu)闊o(wú)效行，造成更多行被移除。對(duì)此，本算法在映射參數(shù)時(shí)，根據(jù)無(wú)效行、禁止元組和敏感行對(duì)重構(gòu)CAN的影響，按照優(yōu)先考慮無(wú)效行最少，其次考慮禁止元組數(shù)量最多，最后考慮敏感行最少的原則完成參數(shù)映射，保持無(wú)效行數(shù)量最少。算法框架如下。

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

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

開(kāi)始

令SCA←CAN

令Q←?

for (inti=1 ton) 執(zhí)行

if (pi?F) 執(zhí)行

Q←Q∪{pi}; //Step1

else

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

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

end if

end for

for (每個(gè)參數(shù)p∈Q) 執(zhí)行

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

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

end for

for (每行r∈SCA)

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

從SCA中移除r; //Step4

end if

end for

returnSCA;

結(jié)束

該算法主要包括以下4個(gè)步驟：

Step1參數(shù)約束性檢查。逐一檢查輸入?yún)?shù)是否出現(xiàn)在集合F相關(guān)的禁止元組中，若不出現(xiàn)，則將該參數(shù)加入非約束參數(shù)集Q，否則執(zhí)行下一步。

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

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

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

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

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

循環(huán)執(zhí)行Step1和Step2直至所有約束參數(shù)完成映射，然后執(zhí)行下一步。

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

Step4根據(jù)約束條件，移除SCA中的無(wú)效行。

3.2 覆蓋數(shù)組擴(kuò)展

重構(gòu)最優(yōu)覆蓋數(shù)組并移除無(wú)效行，有可能造成無(wú)效行中某些合法有效t值模式丟失覆蓋。設(shè)這些t值模式構(gòu)成的集合為Π。為使得最終生成的車(chē)載ATP組合測(cè)試用例集既能滿(mǎn)足約束條件，又能實(shí)現(xiàn)對(duì)Π的全覆蓋，需要額外生成測(cè)試用例，擴(kuò)展重構(gòu)之后的數(shù)組。

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

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

算法輸出：滿(mǎn)足約束和覆蓋強(qiáng)度的SCA。

開(kāi)始

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

令T←?;

while (Π!=?) 執(zhí)行

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

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

初始化候選測(cè)試用例τ←σ; //Step1

基于貪婪策略擴(kuò)展τ; //Step2

T←T∪{τ};

end for

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

將τb加入SCA; //Step4

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

end while

returnSCA;

結(jié)束

該算法主要包括以下4個(gè)步驟。

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

Step2擴(kuò)展候選測(cè)試用例。對(duì)于每條候選測(cè)試用例τ∈T，算法采用貪婪策略，每次從Π中選擇一個(gè)t值模式σ，使用σ為τ的參數(shù)賦值。其中，σ需同時(shí)滿(mǎn)足以下3個(gè)條件：

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

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

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

在以上3個(gè)條件中：條件(1)的取值具有一致性，指參數(shù)在σ和τ中具有相同取值，或參數(shù)在σ中有具體取值，在τ中還未被賦值；對(duì)于條件(2)的測(cè)試用例約束檢查，本算法采用了文獻(xiàn)[16]提出的最小禁止元組(Minimum Forbidden Tuple)對(duì)比法，保證τ在擴(kuò)展過(guò)程中始終滿(mǎn)足約束條件，不包含任何禁止元組和隱含元組(Implicit Tuple)；條件(3)為一個(gè)貪婪策略，目的在于快速擴(kuò)展得到精簡(jiǎn)且滿(mǎn)足要求的候選測(cè)試用例，在步驟2中將采用該策略連續(xù)擴(kuò)展τ，直至τ中所有參數(shù)均被賦值，或無(wú)法再?gòu)摩爸姓业溅覍?duì)τ賦值。

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

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

重復(fù)執(zhí)行Step1至Step4，直至Π為空。

4 車(chē)載ATP組合測(cè)試用例生成結(jié)果

本文基于Java平臺(tái)實(shí)現(xiàn)上述方法，生成了CTCS-2級(jí)列控車(chē)載ATP組合測(cè)試用例集。由于車(chē)載ATP在FS模式下，既能進(jìn)行模式轉(zhuǎn)換，又能進(jìn)行等級(jí)切換，也能維持在FS模式工作，為便于區(qū)分測(cè)試用例性質(zhì)，提高測(cè)試針對(duì)性，本文按照車(chē)載ATP模式轉(zhuǎn)換、等級(jí)切換、維持在FS模式3種基本場(chǎng)景，分別生成與輸入?yún)?shù)相關(guān)的組合測(cè)試用例集。限于文章篇幅，這里以生成模式轉(zhuǎn)換場(chǎng)景相關(guān)的組合測(cè)試用例集為例進(jìn)行詳細(xì)說(shuō)明，其余2種場(chǎng)景與之類(lèi)似，僅列出最終結(jié)果。

4.1 最優(yōu)覆蓋數(shù)組重構(gòu)

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

圖3 最優(yōu)覆蓋數(shù)組重構(gòu)

從圖3中可以看出，重構(gòu)前，采用現(xiàn)有參數(shù)映射方式將移除4行無(wú)效行(r2，r4，r5和r6)，而采用本文方法重構(gòu)后僅移除2行(r4和r5)，提高了對(duì)最優(yōu)覆蓋數(shù)組的利用。

4.2 覆蓋數(shù)組擴(kuò)展

重構(gòu)最優(yōu)覆蓋數(shù)組，共造成32個(gè)合法有效的2-值模式丟失覆蓋，限于文章篇幅，這里不再詳細(xì)列出。

圖4展示了擴(kuò)展覆蓋數(shù)組，覆蓋所有合法2-值模式后得到的覆蓋數(shù)組及完整的測(cè)試用例集。圖4中覆蓋數(shù)組的列順序已調(diào)整為參數(shù)的下標(biāo)順序，虛框內(nèi)綠色部分為對(duì)最優(yōu)覆蓋數(shù)組的利用。

圖4 車(chē)載ATP模式轉(zhuǎn)換場(chǎng)景下的組合測(cè)試用例集

圖4(b)每一行代表一條測(cè)試用例，如第2行表示在FS模式下，將車(chē)載ATP方向手柄設(shè)置為向前、牽引手柄設(shè)置為牽引，模擬列車(chē)前進(jìn)運(yùn)行；然后在運(yùn)行過(guò)程中，保持手柄狀態(tài)，并施加最大常用制動(dòng)，測(cè)試車(chē)載ATP能否控制列車(chē)停車(chē)；最后待停車(chē)后，保持手柄狀態(tài)和最大常用制動(dòng)，按壓調(diào)車(chē)鍵，測(cè)試車(chē)載ATP能否轉(zhuǎn)換為調(diào)車(chē)模式。

4.3 有效性分析

車(chē)載ATP為SIL-4級(jí)安全關(guān)鍵設(shè)備，其測(cè)試覆蓋準(zhǔn)則相對(duì)于通用軟件而言要求更加嚴(yán)格[17]。本文基于最優(yōu)覆蓋數(shù)組，還進(jìn)行了更高強(qiáng)度的測(cè)試用例生成(t=2，3，4，5)。同時(shí)，為驗(yàn)證方法的有效性，選取了以下3種方法與本文方法進(jìn)行比較：①基于現(xiàn)有的參數(shù)映射方法生成測(cè)試用例集(以下簡(jiǎn)稱(chēng)為直接擴(kuò)展法)；②基于主流工具PICT[18]生成測(cè)試用例集；③基于主流工具ACTS[19]生成測(cè)試用例集?；谥苯訑U(kuò)展法生成測(cè)試用例集，即首先采用現(xiàn)有的參數(shù)下標(biāo)映射方法，直接將參數(shù)映射到CAN并移除無(wú)效行；然后采用本文提出的擴(kuò)展算法完成子數(shù)組的擴(kuò)展，得到滿(mǎn)足約束的測(cè)試用例集?；谥髁鞴ぞ逷ICT和ACTS直接生成測(cè)試用例集，即首先根據(jù)輸入?yún)?shù)與約束條件構(gòu)造組合測(cè)試的輸入模型，然后基于輸入模型，采用工具直接生成測(cè)試用例集。圖5展示了幾種方法分別在模式轉(zhuǎn)換、等級(jí)切換和維持在FS模式3種場(chǎng)景下的測(cè)試用例集生成結(jié)果(t=2，3，4，5)。

圖5 不同場(chǎng)景和覆蓋強(qiáng)度下的測(cè)試用例生成結(jié)果

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

特別地，在t=5時(shí)，對(duì)于模式轉(zhuǎn)換場(chǎng)景，采用本文方法生成的測(cè)試用例僅為96條，而在同等條件下，采用直接擴(kuò)展法得到的結(jié)果為108條，采用PICT工具得到的結(jié)果為104條，采用ACTS工具得到的結(jié)果為103條。本文方法得到的結(jié)果相對(duì)于現(xiàn)有方法，最多可減少12條測(cè)試用例，測(cè)試用例集的規(guī)模減小幅度達(dá)到了11.11%。通過(guò)比較，驗(yàn)證了本文方法的有效性。

此外，為驗(yàn)證本文提出的參數(shù)映射算法的有效性，還比較了本文方法和直接擴(kuò)展法在測(cè)試生成過(guò)程中對(duì)CAN的利用率，見(jiàn)圖6。

圖6 2種方法對(duì)于最優(yōu)覆蓋數(shù)組的利用率

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

5 結(jié)論

(1)車(chē)載ATP是列控系統(tǒng)的核心設(shè)備之一，針對(duì)車(chē)載ATP接口輸入?yún)?shù)的組合測(cè)試在保障功能安全方面具有重要意義。

(2)最優(yōu)覆蓋數(shù)組具有行數(shù)最少、覆蓋緊湊等特點(diǎn)，基于最優(yōu)覆蓋數(shù)組完成組合測(cè)試，能有效控制測(cè)試成本。

(3)本文針對(duì)車(chē)載ATP的參數(shù)組合特點(diǎn)，提出了基于最優(yōu)覆蓋數(shù)組的車(chē)載ATP組合測(cè)試用例集生成方法。結(jié)果表明，本方法能夠提高對(duì)于最優(yōu)覆蓋數(shù)組的利用，在滿(mǎn)足約束和覆蓋準(zhǔn)則的基礎(chǔ)上，實(shí)現(xiàn)了測(cè)試用例集的精簡(jiǎn)生成，有效降低了車(chē)載ATP測(cè)試成本，提高了測(cè)試效率。