史增樹，李 耀，郭 進，張亞東

當前我國已成為世界上高鐵運營里程最長、運輸密度最高、運營場景最復(fù)雜的國家。信號系統(tǒng)是保障高鐵安全、高效運行的核心，是典型的安全關(guān)鍵系統(tǒng)。如何高效生成覆蓋全部測試需求的測試案例是高鐵信號系統(tǒng)的重要研究內(nèi)容［1-2］。

目前，對于高鐵信號系統(tǒng)在測試案例生成方面的研究主要基于模型的測試理論，包含抽象測試案例生成和抽象測試案例實例化為具體測試案例等。如針對列控系統(tǒng)測試，文獻［3-5］ 研究基于UML模型的測試案例生成方法；文獻［6］結(jié)合混合通信順序進程和時間自動機模型，研究測試案例自動生成問題；文獻［7-8］將時間自動機理論和變異測試技術(shù)相結(jié)合，提出列控系統(tǒng)安全功能測試案例生成技術(shù)；針對車載設(shè)備邏輯復(fù)雜的特點，文獻［9-10］提出基于SCADE 模型的測試案例生成方法；文獻［11-12］基于UPPAAL Cover 工具，研究基于自動機模型的測試案例生成技術(shù)；文獻［13］提出基于Colored Petri Net 模型的測試案例生成方法。以上研究重點關(guān)注抽象測試案例的全面性和重復(fù)度。

在抽象測試案例實例化為具體測試案例方面，文獻［14］針對列控系統(tǒng)抽象測試案例實例化的問題，基于確定性有限狀態(tài)機模型，提出輸入空間劃分和邏輯覆蓋相結(jié)合的抽象測試案例自動實例化方法；文獻［15］以CTCS-3級列控系統(tǒng)等級轉(zhuǎn)換場景為例，研究基于時間自動機模型的抽象測試案例生成方法，進一步提出基于排列組合的具體測試案例生成流程；文獻［16］從組合測試的角度，基于有限狀態(tài)機模型研究信號系統(tǒng)具體測試案例的實例化方法。

高鐵信號系統(tǒng)抽象測試案例實例化時，測試項可能包括多個實例化取值，導(dǎo)致具體測試案例的數(shù)量龐大。如何將抽象測試案例實例化為高效的具體測試案例是高鐵信號系統(tǒng)測試中的重要問題，目前的研究尚未深入地對該問題展開探討。為此，本文基于有限狀態(tài)機建模方法，引入并改進引力搜索算法，對信號系統(tǒng)抽象測試案例實例化為具體測試案例的過程進行研究，在保證具體測試案例全面性的同時，降低測試案例的數(shù)量，對降低高鐵信號系統(tǒng)測試成本具有一定的意義。

1 高鐵信號系統(tǒng)測試案例生成過程

高鐵信號系統(tǒng)測試案例生成過程見圖1?；谀Ｐ偷臏y試是高鐵信號系統(tǒng)測試的重要研究方向，主要包括系統(tǒng)需求分析、測試模型建立、抽象測試案例生成、抽象測試案例實例化、測試執(zhí)行和測試結(jié)果分析6 個階段。首先，基于信號系統(tǒng)的需求規(guī)格等文件對系統(tǒng)功能進行抽象，建立系統(tǒng)的測試模型；其次，依據(jù)測試模型，選取測試覆蓋準則，自動生成抽象測試案例；然后結(jié)合行業(yè)知識，將抽象測試案例實例化為可執(zhí)行的具體測試案例；最后，將具體測試案例加載到測試環(huán)境中執(zhí)行測試，觀察、分析測試結(jié)果。

圖1 高鐵信號系統(tǒng)測試案例生成過程

在將抽象測試案例實例化為具體測試案例的過程中，抽象測試案例可能包括多個實例化取值，如抽象測試案例“開放允許信號”，實例化的具體測試案例可能為L 碼、LU 碼等。在生成具體測試案例時，需要覆蓋每個實例化取值。在如圖2 所示的有限狀態(tài)機（Finite State Machine，F(xiàn)SM）［17-18］測試模型中，s0為初始狀態(tài)，sf為終止狀態(tài)，g1~g5為轉(zhuǎn)移；g1~g4有1個實例化取值，g5有2個實例化取值。模型存在3條抽象測試案例p1、p2、p3：

圖2 FSM模型

為覆蓋g5的2 個實例化取值，生成具體測試案例時，可以分配p2中g(shù)5取值z5，p3中g(shù)5取值z6，即模型通過3 條具體測試案例T1、T2、T3，覆蓋抽象測試案例和所有的實例化取值：

通常，鐵路信號系統(tǒng)抽象測試案例的實例化取值較多。文獻［16］對ZPW-2000軌道電路接收器進行了研究，其抽象測試案例“電壓無效”包括20個實例化取值，“頻率無效”包括24個實例化取值。信號系統(tǒng)測試需要覆蓋所有的抽象測試案例和全部的實例化值；同時，為節(jié)省測試資源，應(yīng)當使測試成本（消耗的資源、時間等）盡量較低，具體要求如下。

1）覆蓋所有抽象測試案例，即每個抽象測試案例至少需要測試1次。

2）覆蓋所有的實例化值，即每一個實例化取值至少被一條具體測試案例覆蓋。

3）總體測試成本較低。信號系統(tǒng)測試繁瑣復(fù)雜，將實例化值合理分配到抽象測試案例，能夠有效降低具體測試案例的數(shù)量，減少系統(tǒng)的測試成本。

綜上，高鐵信號系統(tǒng)抽象測試案例的實例化過程存在一個典型的優(yōu)化問題：如何在保證100%覆蓋抽象測試案例和實例化取值的前提下，總體測試成本控制較低，即：

式中：n為測試模型轉(zhuǎn)移的數(shù)量；C(gi)為轉(zhuǎn)移gi的測試成本；E(gi)為轉(zhuǎn)移gi實例化取值的數(shù)量；K(gi) 為轉(zhuǎn)移gi實際的執(zhí)行次數(shù)。

2 基于引力搜索算法的測試案例生成方法

結(jié)合FSM提出基于引力搜索算法的高鐵信號系統(tǒng)測試案例生成方法［19］，見圖3，具體步驟如下。

圖3 基于改進引力搜索算法的測試案例生成方法

Step 1采用FSM描述高鐵信號系統(tǒng)的測試需求，建立FSM測試模型。

Step 2利用FSM測試案例生成算法自動生成高鐵信號系統(tǒng)的抽象測試案例。

Step 3根據(jù)測試需求，提取FSM模型中各個轉(zhuǎn)移的實例化取值，計算抽象測試案例的測試成本。

Step 4克服算法早熟的缺點，綜合高鐵信號系統(tǒng)抽象測試案例、實例化取值和測試成本3 個因素進行搜索，生成具體化的測試案例。

2.1 引力搜索算法

2009 年，Esmat Rashedi 等學(xué)者結(jié)合萬有引力定律，提出了一種新型的群體智能優(yōu)化算法——引力搜索算法（Gravitational Search Algorithm，GSA）。研究發(fā)現(xiàn)，該算法具有較強的全局搜索能力，在標準測試函數(shù)優(yōu)化試驗中，尋優(yōu)精度和收斂速度都明顯優(yōu)于粒子群優(yōu)化算法（PSO）和遺傳算法（GA）［20］。

引力搜索算法首先在解空間和速度空間分別對位置和速度進行初始化，然后評價各個個體的目標函數(shù)值，確定每個個體的質(zhì)量和受到的引力，計算加速度，更新速度和位置。

2.1.1計算質(zhì)量

對N個個體，個體i的質(zhì)量Mi( )

t定義為式中：fiti(t)為第t次迭代個體i的適應(yīng)度函數(shù)值；best(t)和worst(t)為在第t次迭代時，所有個體中最優(yōu)的適應(yīng)度函數(shù)值和最差的適應(yīng)度函數(shù)值。

2.1.2計算引力

在第d維上，個體j對個體i的引力定義為

式中：G(t) 為在第t次迭代時的萬有引力常數(shù)；Rij(t)為個體i和j之間的歐氏距離，i，j∈{1，2，…，N}，且i≠j，d=1，2，…；ε為防止分母為零的常數(shù)；分別為個體i、j在第d維的位置分量。

式中：G0和a為常數(shù)，T為最大迭代次數(shù)。

在第d維上，個體i所受的合力為

式中：randj為在[0， 1]之間服從均勻分布的隨機變量；kbest為個體質(zhì)量按降序排在前k個的個體，且k的取值隨迭代次數(shù)線性減小，初值為N，終值為1。

2.1.3計算加速度

個體i在第d維的加速度方程為

2.1.4更新速度和位置

式中：u為在[0， 1]之間服從均勻分布的一個隨機變量。

2.2 基于改進引力搜索算法的測試案例生成

對于FSM 測試模型，其包含的轉(zhuǎn)移集合記為Γ={g1，g2，…，gn}，轉(zhuǎn)移實例化取值數(shù)量記為E={E(g1)，E(g2)，…，E(gn)}，抽象測試案例集記為P，p∈P的測試成本記為C（p）。對于圖2 所示的FSM 模型，Γ={g1，g2，g3，g4，g5}，E(g5)=2，P={p1，p2，p3}，假設(shè)g1，g2，g3，g4，g5的測試成本分別為10，30，50，20，20，則C(p1)=60，C(p2)=50，C(p3)=50。

抽象測試案例實例化問題可轉(zhuǎn)化為計算FSM模型抽象測試案例的執(zhí)行次數(shù)，使其在實例化時能夠全面覆蓋抽象測試案例所有的實例化取值，且測試成本較低。引力搜索算法在測試成本{C(p1)，C(p2)，…，C(pn)}的約束下，根據(jù)抽象測試案例包含的各個轉(zhuǎn)移實例化取值數(shù)量，搜索抽象測試案例的執(zhí)行次數(shù)。由于需要對抽象測試案例至少覆蓋1 次，則x(t)下轉(zhuǎn)移gi的執(zhí)行次數(shù)記為Kx(t)(gi)，則抽象測試案例實例化過程的適應(yīng)度函數(shù)fit(t)為

迭代過程中，所有個體最優(yōu)適應(yīng)度函數(shù)值best(t)和最差適應(yīng)度函數(shù)值worst(t)定義為

由于傳統(tǒng)的引力搜索算法存在局部收斂，導(dǎo)致早熟的問題［21］，因此需進行改進，引入遺傳算法中應(yīng)用較好的最優(yōu)保存策略［22-23］，并加入末位淘汰機制。即：每次算法迭代后，如果某個體優(yōu)于當前最優(yōu)個體，則保持該個體的當前位置，淘汰適應(yīng)度最差的個體，即將適應(yīng)度最差的個體重新初始化到解空間，將所有個體迭代次數(shù)重置為0。

基于改進引力搜索算法的測試案例生成流程見圖4，包括以下階段：

圖4 基于改進引力搜索算法的測試案例生成流程

Step 1隨機初始化所有個體的位置，每個個體的初始速度為零。

Step 2計算每個個體的適應(yīng)度函數(shù)值。

Step 3利用式（2）、（5）、（11）、（12）分別更新M（t）、G（t）、best（t）、worst（t）。

Step 4利用式（6）計算每個個體受到的引力。

Step 5利用式（4）、（6）、（7）計算每個個體的加速度。

Step 6利用式（8）、（9）更新每個個體的速度和位置。

Step 7根據(jù)優(yōu)化規(guī)則，更新個體位置和迭代次數(shù)。

Step 8重復(fù)步驟Step 2~Step 8，直到滿足終止條件。

Step 9輸出當前結(jié)果并終止算法。

3 案例分析

以高鐵信號系統(tǒng)中CTCS-2級向CTCS-3級轉(zhuǎn)換的功能為例，介紹測試案例生成過程。

3.1 等級轉(zhuǎn)換功能抽象測試案例生成

在CTCS-2級向CTCS-3級轉(zhuǎn)換前，需要完成的工作包括：車載電臺注冊到GSM-R 網(wǎng)絡(luò)、車載設(shè)備與RBC 建立通信會話、車載設(shè)備從RBC 獲得系統(tǒng)配置參數(shù)和行車許可等信息。如果在轉(zhuǎn)換邊界不具備CTCS-3 級控車條件，列車將繼續(xù)按CTCS-2級運行，直至CTCS-3級控車條件具備后，車載設(shè)備將自動轉(zhuǎn)入CTCS-3級工作。轉(zhuǎn)換過程中，可能出現(xiàn)的異常情況包括：呼叫RBC不成功、取消等級轉(zhuǎn)換、未同時得到等級轉(zhuǎn)換命令和MA、轉(zhuǎn)換時超過CTCS-3級允許速度、未收到等級轉(zhuǎn)換應(yīng)答器組消息。

為了在不同運行速度下對等級轉(zhuǎn)換功能的執(zhí)行情況進行測試，將轉(zhuǎn)換過程中的速度等級劃分為高速（大于250 km/h）、正常速度（100~250 km/h）和低速（小于100 km/h）3 種模式，F(xiàn)SM 測試模型及轉(zhuǎn)移的實例化取值測試見圖5。

圖5 CTCS-2級向CTCS-3級轉(zhuǎn)換FSM測試模型

圖5中，E（g2）=2，E（g20）=3，E（g21）=3，E（g17）=5，E（g18）=5，E（g16）=7，其余轉(zhuǎn)移的實例化取值數(shù)量均為1。如g17表示列車以正常速度通過執(zhí)行應(yīng)答器，正常速度（單位為km/h）的實例化取值范圍包括：（0，100），［100，150），［150，250），［250，300），［300，350］，分別取不同范圍下的速度通過執(zhí)行應(yīng)答器進行測試。

對于測試模型，采用文獻［19］提出的測試案例生成方法，生成24條抽象測試案例，見表1。以測試人員準備車載設(shè)備上電的時間為測試成本的基礎(chǔ)標準，記為S。每條抽象測試案例的測試成本由測試人員根據(jù)工程測試數(shù)據(jù)，結(jié)合測試經(jīng)驗進行確定。為描述方便，抽象測試案例僅保留FSM 測試模型中的關(guān)鍵轉(zhuǎn)移。以抽象測試案例p6為例，測試內(nèi)容為：列車以CTCS-2 級運行，檢測到GSM-R 網(wǎng)絡(luò)唯一，連接GSM-R 網(wǎng)絡(luò)和RBC 成功后，檢測到等級轉(zhuǎn)換預(yù)告應(yīng)答器，但未同時得到等級轉(zhuǎn)換命令和MA，保持CTCS-2級工作狀態(tài)進入CTCS-3 級區(qū)域后，未收到RBC發(fā)送的MA 和線路描述信息，轉(zhuǎn)為CTCS-3 級后，執(zhí)行冒進防護。

表1 抽象測試案例及測試成本

3.2 等級轉(zhuǎn)換功能具體測試案例生成

改進的引力搜索算法的個體數(shù)設(shè)定為50，G為5，迭代次數(shù)為200。在第137次迭代后，測試總成本達到最小2 005，共計28 條具體測試案例，測試案例覆蓋的實例化取值信息見表2。由于p1~p6各個轉(zhuǎn)移的實例化取值唯一，對應(yīng)的具體測試案例唯一，為節(jié)省篇幅，表2未列舉。

表2 等級轉(zhuǎn)換主要的具體測試案例

由表2可知，抽象測試案例p7、p8、p11、p12分別需要測試2次。如p7，其具體化測試案例分別為T1和T3，實例化取值分別為［150，250）和（0，100）。

為驗證改進引力搜索算法的性能優(yōu)化效果，圖6 給出了與基于傳統(tǒng)的引力搜索算法測試案例生成方法的比較曲線。在傳統(tǒng)的引力搜索算法中，個體數(shù)設(shè)定為50，G為5，迭代次數(shù)為350。第124次迭代時，測試總成本達到最小2 412；而改進的引力搜索算法獲得的測試總成本更低，克服了引力搜索算法容易出現(xiàn)早熟的問題。

圖6 測試案例生成對比

4 結(jié)論

本文提出一種高鐵信號系統(tǒng)測試案例生成方法，重點對抽象測試案例實例化為具體測試案例的關(guān)鍵問題展開了研究。從FSM 測試模型生成抽象測試案例，采用改進引力搜索算法對抽象測試案例實例化取值及測試成本進行優(yōu)化，生成覆蓋全面且測試成本較低的具體測試案例。以信號系統(tǒng)中的等級轉(zhuǎn)換功能為例進行了案例分析，結(jié)果表明該方法能夠滿足信號系統(tǒng)的測試需求。下一步，將繼續(xù)對實例化取值之間的組合問題展開研究。