面向列控系統的多目標測試序列集生成方法

趙曉宇

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

引言

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

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

圖1 總體框架

1 相關定義

定義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}為系統需求集；C:{c1，…，cY}為測試案例集；N:{n1，…，nZ}為模型的狀態空間的路徑節點集，S:{s1，…，sL}為DFS算法和模型場景邏輯關系生成的測試序列池。

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

(1)

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

(2)

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

(3)

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

(4)

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

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

(5)

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

(6)

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

(7)

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

(8)

(9)

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

2.1 模型的構建及驗證

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

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

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

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

(4)關于數據內容的判斷行為，均在模型的守衛函數中體現。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3.2 算法的關鍵步驟

(1)構造解過程

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

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

(10)

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

(11)

(2)更新信息素

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

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

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

τi(0)=τmax

(12)

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

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

(13)

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

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

(14)

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

(3)評價解過程

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

(15)

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

(4)非支配排序

通過快速非支配排序法判斷構造解的優劣性，具體步驟描述如下，dii為種群P中支配個體ii的個體數量，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加入構造解集。

步驟4：輸出最優構造解集。

3 實驗及結果分析

3.1 實驗設計

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

圖2 頂層模型

圖3 Double-RBC HandingOver模型

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

圖4 狀態空間

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

表2 測試案例信息

3.2 算法對比實驗

根據DFS算法和場景邏輯關系生成包含152個測試序列的測試序列池，通過本文算法對測試序列池內的測試序列進行選擇性地排序，生成最優測試序列集，如表3所示，本文算法和DFS算法的對比結果如表4所示。

表3 測試序列集

表4 不同算法的對比結果

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

4 結語

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