面向列控系統(tǒng)的多目標測試序列集生成方法

趙曉宇

(中國鐵道科學研究院集團有限公司通信信號研究所，北京 100081)

引言

作為典型的安全苛求系統(tǒng)，列控系統(tǒng)融合多種先進技術(shù)，用于保證列車運行安全、提高列車運行效率。系統(tǒng)的任何故障都可能會導致不可估量的災難性后果，為了保證軟硬件功能的完整性和正確性，在投入運營之前必須執(zhí)行嚴格的系統(tǒng)功能測試?，F(xiàn)有的測試技術(shù)需要測試人員手動編制測試序列，同時很少根據(jù)某種標準對測試序列進行排序，耗時耗力，而且不同廠家的測試手段不同，自動化程度也有不同。趙顯瓊等[1]提出基于CPN[2]的測試案例和測試序列生成方法；鄭偉等[3]提出基于全路徑覆蓋優(yōu)化算法和序列優(yōu)選算法的測試生成方法，而后又提出改進蟻群算法和老鼠迷宮算法[4]；趙曉宇等[5]提出車載設備模式轉(zhuǎn)換測試序列生成方法；但這些均未涉及測試序列的排序問題。

為了盡早發(fā)現(xiàn)系統(tǒng)缺陷，并及時反饋給研發(fā)人員，測試人員希望通過多個優(yōu)化原則對測試序列進行排序，執(zhí)行優(yōu)先級較高的測試序列。針對持續(xù)集成測試問題，何柳柳等[6]改進了強化學習的獎勵函數(shù)設計和獎勵策略。面向測試用例優(yōu)先排序問題，張娜等[7]在引入3個優(yōu)先級影響因子的基礎上，提出在線調(diào)整策略。多目標測試序列優(yōu)化排序問題可以轉(zhuǎn)化為多目標組合優(yōu)化問題，一般通過啟發(fā)式搜索算法尋求最優(yōu)解集，如粒子群算法、蟻群算法(ACO)和非支配排序遺傳算法等。針對高維多目標優(yōu)化問題，朱占磊等[8]提出線性權(quán)重最優(yōu)支配關(guān)系和高維多目標進化優(yōu)化算法。石宇楠等[9]提出多目標協(xié)同進化算法，通過剔除“老年”個體避免算法陷入局部最優(yōu)。邊毅等[10]通過CPU+GPU的并行策略改進適應度評估函數(shù)。陳云飛等[11]提出粒子群算法，并研究不同參數(shù)的性能影響。相比其他算法而言，ACO具有較優(yōu)的魯棒性和并行計算機制。肖箐等[12]討論ACO在多目標優(yōu)化問題中的應用。顧慧聰?shù)萚13]提出基于ACO的多目標測試用例預優(yōu)化方法。江君莉等[14]采用直接學習機制避免算法陷入局部最優(yōu)。邢行等[15]定義基于上位基因段的信息素更新策略。張娜等[16]提出一種動態(tài)簡約的在線指導蟻群信息更新的多目標測試用例優(yōu)先級排序方法，避免了蟻群算法的收斂速度緩慢等問題?；诖耍菊撐脑跐M足測試案例全覆蓋的前提下，提出了一種多目標測試序列集生成方法，如圖1所示，使得測試人員能夠及早發(fā)現(xiàn)功能缺陷，提高測試效率。

圖1 總體框架

1 相關(guān)定義

定義1假設蟻群為K:{1，…，AntNum}，測試案例覆蓋表為tabuc:{tabuck|k∈K}，測試序列覆蓋表為tabus:{tabusk|k∈K}，則測試序列集生成模型PM通過13元素進行描述，即PM={R，C，N，S，Δ(R，C)，Δ(N，C)，Δ(C，S)，Δ(C，tubuc)，Irx，Icy，Isl，Lcy，Lsl}

(1)R:{r1，…，rX}為系統(tǒng)需求集；C:{c1，…，cY}為測試案例集；N:{n1，…，nZ}為模型的狀態(tài)空間的路徑節(jié)點集，S:{s1，…，sL}為DFS算法和模型場景邏輯關(guān)系生成的測試序列池。

(2)測試需求覆蓋矩陣Δ(R，C)，表示C到R的覆蓋關(guān)系，矩陣元素為

(1)

(3)路徑節(jié)點覆蓋矩陣Δ(N，C)，表示C到N的覆蓋關(guān)系，矩陣元素為

(2)

(4)測試案例覆蓋矩陣Δ(C，S)，表示S到C的覆蓋關(guān)系，矩陣元素為

(3)

(5)測試案例遍歷矩陣Δ(C，tubuc)，表示tabuc到C的覆蓋關(guān)系，矩陣元素為

(4)

(6)測試需求重要度Irx，根據(jù)測試需求的使用情況和復雜程度將Irx分為必用、常用、很少用和幾乎不用，取值為1，0.7，0.4和0.1，引發(fā)的缺陷等級分別為致命、嚴重、一般和較輕。

(7)測試案例重要度Icy，表示測試案例覆蓋的全部測試需求重要度的總和，由公式(1)可得

(5)

(8)測試序列重要度Isl，表示測試序列覆蓋的全部測試案例重要度的總和，由公式(3)和公式(5)可得

(6)

(9)測試案例路徑長度Lcy，表示測試案例覆蓋的全部路徑節(jié)點的總個數(shù)，由公式(2)可得

(7)

(10)測試序列路徑長度Lsl，表示測試序列覆蓋的測試案例路徑長度的總和，由公式(3)和公式(7)可得

(8)

(9)

2 多目標測試序列集生成方法

2.1 模型的構(gòu)建及驗證

根據(jù)TB/T 3530—2018《CTCS-3 級列車運行控制系統(tǒng)系統(tǒng)需求規(guī)范》(以下簡稱“《規(guī)范》”)[17]和CPN Tools的建模要求，提出以下建模規(guī)則，并采用CPN Tools的ASK-CTL擴展邏輯語言和非標準狀態(tài)空間查詢法對列控系統(tǒng)模型進行分析與驗證。

(1)采用分層建模規(guī)則構(gòu)建列控系統(tǒng)模型，頂層模型考慮場景間和場景與接口間的交互關(guān)系，中層模型考慮場景的主要功能，底層模型考慮詳細功能。

(2)建模流程需嚴格遵守顏色定義、變量和庫所等的命名規(guī)則，用于輔助算法實現(xiàn)。

(3)采用ML語言處理全部數(shù)據(jù)，用于提供算法的輸入數(shù)據(jù)和輸出數(shù)據(jù)。

(4)關(guān)于數(shù)據(jù)內(nèi)容的判斷行為，均在模型的守衛(wèi)函數(shù)中體現(xiàn)。

(5)鑒于列控系統(tǒng)功能復雜性，考慮構(gòu)建多個模型，用于子系統(tǒng)功能的分析與測試。

2.2 基于IDFS的測試案例集生成算法

為了處理模型的循環(huán)(自)回路，在滿足路徑全覆蓋和節(jié)點全覆蓋的基礎上，測試案例集生成算法的描述如下。

步驟1：確定模型狀態(tài)空間和底層模型集合{M1，…MI}，初始化i=1。

步驟2：針對底層模型Mi，獲取鄰接矩陣A、開始路徑節(jié)點ns和結(jié)束路徑節(jié)點ne。

步驟3：根據(jù)IDFS算法生成ns至ne的簡單路徑集(不包括循環(huán)(自)回路)，并識別ns和ne間的全部循環(huán)(自)回路。刪除Mi的全部循環(huán)(自)回路，獲取鄰接矩陣A1；針對每個循環(huán)(自)回路頂點，通過Dijkstra算法搜索最短前置路徑(ns至回路頂點)和最短后置路徑(回路頂點至ne)。針對每條循環(huán)(自)回路，補充最短前置路徑和最短后置路徑，生成包含循環(huán)(自)回路的路徑集，和簡單路徑集共同組成Mi的測試案例集Ci。

步驟4：更新i=i+1，如果i≤I，返回步驟2，否則輸出測試案例集C:{C1，…，CI}。

2.3 基于IMMAC的多目標測試序列集生成算法

針對包含冗余測試案例的測試序列池，測試人員往往考慮順序測試，很少根據(jù)案例全覆蓋和多優(yōu)化目標對測試序列池進行測試序列的挑選與排序?；诖?，將測試序列關(guān)注覆蓋率、測試序列重要度、測試序列路徑長度作為啟發(fā)式函數(shù)，共同作用于蟻群遍歷策略，蟻群根據(jù)轉(zhuǎn)移概率對測試序列池內(nèi)的測試序列進行遍歷，直至遍歷完測試序列池或者滿足測試案例全覆蓋，而后可得構(gòu)造解集，采用快速非支配排序法判斷構(gòu)造解的優(yōu)劣性，通過更新全局最優(yōu)解集得到最優(yōu)測試序列集。

2.3.1 多目標測試序列集生成問題

多目標測試序列集生成問題描述為求解滿足測試案例全覆蓋的部分測試序列的順序排列。本文提出3個優(yōu)化目標，即測試序列重要度、測試序列路徑長度和平均測試案例覆蓋率。

(1)平均測試案例覆蓋率。相同覆蓋準則的條件下，測試序列的平均測試案例覆蓋率越高，測試序列的檢錯力越強。

(2)測試序列重要度。實際上，經(jīng)常使用的設備功能需求僅占40%左右[18]，優(yōu)先執(zhí)行重要度等級較高的測試序列，能夠盡早檢測設備功能缺陷，提高測試效率。

(3)測試序列路徑長度。測試序列包含的測試路徑越長，測試步驟越多，越具有檢錯潛力。

2.3.2 算法的關(guān)鍵步驟

(1)構(gòu)造解過程

假設信息素釋置于測試序列上，構(gòu)造解的求解過程即蟻群選擇測試序列的過程。蟻群根據(jù)轉(zhuǎn)移概率確定下個遍歷的測試序列，直至遍歷完測試序列池或者滿足測試案例全覆蓋。

①蟻群初始放置規(guī)則。針對測試序列池S:{s1，…，sL}中的全部測試序列，分別對測試序列重要度和測試序列路徑長度進行排序，將各序列的前L/2個測試序列存入初始測試序列集Sinit，刪除重復序列。約定蟻群初始置于Sinit中的測試序列上，提高算法收斂速度。

(10)

③啟發(fā)式函數(shù)。tabuc覆蓋測試序列中測試案例的數(shù)量越少，此測試序列對tabuc的貢獻越大。順序遍歷對tabuc、測試序列重要度和測試序列路徑長度貢獻最大的測試序列，能夠生成數(shù)量最少的測試序列集，即將測試序列重要度、測試序列路徑長度和測試序列關(guān)注覆蓋率作為啟發(fā)式函數(shù)，由公式(6)、公式(8)和式(9)可得

(11)

(2)更新信息素

信息素更新策略是為了增加較優(yōu)解上的信息素濃度，同時降低較劣解上的信息素濃度，從而起到正反饋的作用，引導螞蟻朝更好的方向進行搜索。

①局部信息素。螞蟻遍歷測試序列后，更新此測試序列上的信息素。局部信息素更新規(guī)則如下式所示，ω為局部信息素揮發(fā)系數(shù)。

τi(t+n)=(1-ω)τi(t)+ωτi(0)

τi(0)=τmax

(12)

②全局信息素。蟻群完成迭代后，更新全局最優(yōu)解集中的測試序列上的信息素。全局信息素更新策略如下

τi(t+n)=(1-ρ)τi(t)+Δτi(t)

(13)

式中，ρ為全局信息素揮發(fā)系數(shù)；Fmin=(F1+F2+F3)min為全局最優(yōu)解集中的最小適應度值。

③信息素閾值。信息素閾值如下

(14)

式中，Nc為迭代次數(shù)，avg=Nc/2，Pbest=0.5。

(3)評價解過程

蟻群完成迭代后，根據(jù)適應度函數(shù)判斷構(gòu)造解集的優(yōu)劣性。本文根據(jù)優(yōu)化目標設計適應度函數(shù)，如下式所示，F(xiàn)1鼓勵對平均測試案例覆蓋率貢獻大的測試序列排在構(gòu)造解的前面，F(xiàn)2和F3分別鼓勵具有更高重要度和更長路徑的測試序列排在測試序列集前面

(15)

式中，M1為構(gòu)造解包含的測試序列數(shù)量；Y為測試案例數(shù)量；SSy為覆蓋測試案例cy的首個測試序列在測試序列集中的位置；h為測試序列sh在測試序列集中的位置；Ish為sh的測試序列重要度；Lsh為sh的測試序列路徑長度；C1和C2用于限制適應度函數(shù)的值域，此處取C1=10，C2=5。

(4)非支配排序

通過快速非支配排序法判斷構(gòu)造解的優(yōu)劣性，具體步驟描述如下，dii為種群P中支配個體ii的個體數(shù)量，Dii為P中被ii所支配的個體集合。

步驟1：初始化dii，Dii(?ii∈P)，即令dii=0，Dii=φ。

步驟2：對于jj∈P，如果ii支配jj，則將jj存入Dii，否則dii=dii+1。

步驟3：如果dii=0，將ii加入構(gòu)造解集。

步驟4：輸出最優(yōu)構(gòu)造解集。

3 實驗及結(jié)果分析

3.1 實驗設計

根據(jù)《規(guī)范》和CPN建模規(guī)則，對CTCS-3級列控系統(tǒng)的注冊與啟動、RBC移交和注銷場景進行建模。頂層模型如圖2所示，包括5個底層模型，即StartProcedure、Train Start-up、Single-RBC HandingOver、Double-RBC HandingOver和EndofMission。狀態(tài)流運行至Train Start-up模型后，如果ATP與RBC未建立通信，則轉(zhuǎn)至EndofMission模型；如果ATP與RBC已建立通信，當雙電臺工作時，轉(zhuǎn)至Double-RBC HandingOver模型，否則轉(zhuǎn)移至Single-RBC HandingOver模型。此處僅給出Double-RBC HandingOver模型，如圖3所示。

圖2 頂層模型

圖3 Double-RBC HandingOver模型

運行CPN Tools的狀態(tài)空間查詢功能，得到模型的狀態(tài)空間，如圖4所示。采用測試案例集生成算法生成40個測試案例，得到底層模型及測試案例對應表，如表1所示。通過圖4得到測試案例路徑長度，根據(jù)測試需求重要度的等級劃分得到測試案例重要度，如表2所示。參考文獻[19-20]，將測試需求重要度劃分為必用、常用、很少用和幾乎不用，對應數(shù)值分別為1，0.7，0.4和0.1。以測試案例c1為例，包含的測試需求有ATP啟機、ATP轉(zhuǎn)入SB模式、版本信息錯誤引起ATP和RBC通信未成功，根據(jù)需求使用情況和復雜程度設計重要度數(shù)值分別為1，1和0.4，可得測試案例c1的重要度為2.4。本文采用基于IMMAC的多目標測試序列集生成算法生成最優(yōu)測試序列集，最終通過CPN Tools工具內(nèi)嵌的XML文件保存功能得到最優(yōu)測試序列集的XML文件，用于平臺測試。

圖4 狀態(tài)空間

表1 底層模型及測試案例對應

表2 測試案例信息

3.2 算法對比實驗

根據(jù)DFS算法和場景邏輯關(guān)系生成包含152個測試序列的測試序列池，通過本文算法對測試序列池內(nèi)的測試序列進行選擇性地排序，生成最優(yōu)測試序列集，如表3所示，本文算法和DFS算法的對比結(jié)果如表4所示。

表3 測試序列集

表4 不同算法的對比結(jié)果

由表3和表4可知：(1)在滿足測試案例全覆蓋的準則上，基于本文算法生成的測試序列數(shù)量遠小于DFS算法(即測試序列池的測試序列數(shù)量)，測試序列重復度降低86%；(2)本文算法滿足測試人員優(yōu)先執(zhí)行等極度較高的測試序列，能夠及早發(fā)現(xiàn)設備問題，及時反饋給相關(guān)研發(fā)人員，提高并行效率。

4 結(jié)語

本文針對多目標測試序列集生成問題，提出一種多目標測試序列集生成方法。該方法根據(jù)建模規(guī)則構(gòu)建列控系統(tǒng)模型，并通過測試案例集生成算法生成滿足路徑全覆蓋和節(jié)點全覆蓋的測試案例集；而后引入3個優(yōu)化目標，即測試序列重要度、測試序列路徑長度和平均測試案例覆蓋率，在滿足測試案例全覆蓋的提前下，提出基于IMMAC的多目標測試序列集優(yōu)化生成算法，改進了序列遍歷策略、信息素更新策略和構(gòu)造解評價機制等。最后通過實例可知，該方法在滿足相應覆蓋準則的前提下，具有較高的測試生成效率，為列控系統(tǒng)自動化測試技術(shù)的發(fā)展提供理論參考。