基于運行剖面的列控系統(tǒng)測試用例生成研究

古 俐，徐中偉，梅 萌

(同濟大學 電子與信息工程學院，上海 200000)

0 引 言

近年來，中國鐵路建設進入了蓬勃發(fā)展的新時期，目前已經全面進入高鐵時代，這對于國家構建綜合交通體系，提高鐵路運輸效率起到了巨大的作用。但高鐵系統(tǒng)龐大復雜，一旦防控環(huán)節(jié)處理不當，可能對高鐵安全運行產生巨大的影響，因此，保證鐵路網(wǎng)的安全運行成為迫在眉睫的問題。而列控中心作為地面車站的控制中心，其性能決定著整個鐵路線的安全，對其功能進行有效測試，是保證其安全運行的方法[1]。

列控中心測試場景較為復雜，測試案例涵蓋的內容也相當廣泛，現(xiàn)有的測試用例的編寫運行主要靠人力手工作業(yè)，耗費了大量的時間且易出現(xiàn)錯誤，因此根據(jù)列控中心平臺測試需求，高效合理地自動構造和生成測試用例是改善測試效果，降低測試成本的有效方法。

文中重點關注列控系統(tǒng)運行剖面的構建， 并考慮將粒子群算法與構建的運行剖面相結合。通過合理構建列控系統(tǒng)的可靠性測試數(shù)據(jù)生成模型，能夠將生成測試數(shù)據(jù)所需信息通過軟件的任務、系統(tǒng)模式、環(huán)境剖面來建模實現(xiàn)，在所得到的運行剖面的基礎上，應用粒子群算法來提高自動生成測試數(shù)據(jù)的效率與質量。

1 運行剖面和測試用例生成技術簡述

1.1 運行剖面技術

運行剖面的構建是軟件可靠性測試的重點，良好的運行剖面能夠正確指導軟件的測試，幫助生成合理可靠的測試用例。運行剖面指的是對系統(tǒng)輸入值在其可能輸入范圍內出現(xiàn)概率分布的定義，它描述了軟件實際使用的情況，構建時需要充分分析被測軟件的需求、功能以及輸入輸出，從而生成可靠的運行剖面，得到可信的測試數(shù)據(jù)[2]。

運行剖面的基本概念最早出現(xiàn)在文獻[3]中，John Musa提出了構造運行剖面的基本方法以及基于運行剖面的測試數(shù)據(jù)生成方法?；镜倪\行剖面生成方法由五步構成：找出客戶剖面、建立用戶剖面、定義系統(tǒng)模式剖面、確定功能剖面、完成運行剖面。

Musa對軟件分析的原則適用于多種軟件，但需要結合實際系統(tǒng)情況進行改進。在國內，很多領域都結合并改進了運行剖面來提高軟件測試的可靠性。例如，文獻[4]提出了將復雜軟件的剖面構建過程拆分為軟件運行剖面與若干模塊運行剖面的剖面構建方法，減少了局部的復雜度；文獻[5]提出了適合于航天實時軟件使用的剖面構造方法，并在建模的基礎上結合遍歷算法實現(xiàn)了測試數(shù)據(jù)的生成；文獻[6]采用基于UML圖和定性分析的混合方法，建立了軍用軟件運行剖面元模型，為軍用軟件可靠性實例化提供了支撐。

1.2 測試用例生成技術

以往的測試用例生成主要靠人力手工完成，這對測試人員的專業(yè)水平提出了一定的要求，容易導致實際工程測試中測試用例生成的盲目性。并且根據(jù)以往統(tǒng)計，設計測試用例階段的開銷占軟件測試全部開銷近一半的比重，因此，研究測試用例生成算法，使得程序能夠高效合理地自動構建測試用例有十分重要的意義[7]。

近年來，很多學者對測試用例自動生成這一領域做了大量研究，研究表明，在多種測試用例生成算法中，啟發(fā)性算法具有良好的方向性、能夠動態(tài)反饋信息、魯棒性強等優(yōu)點。啟發(fā)性自動用例生成算法主要有四類：隨機測試、遺傳算法、蟻群算法、粒子群算法，其算法框架相似，都是先對被測程序進行結構性分析得到生成測試目標，對被測程序進行插樁進而來構造適應度函數(shù)，最后根據(jù)適應度函數(shù)選擇修正得到的測試用例，大部分研究都是在基本算法框架上進行改進，來提高生成測試用例的效率[8]。文獻[9]將迷宮算法與蟻群算法結合來優(yōu)化RBC平臺測試用例的序列集，實現(xiàn)了優(yōu)化自動生成的測試用例，縮短測試時間的目的；文獻[10]設計了遺傳算法與粒子群算法的混合優(yōu)化算法，將改進的粒子群算法作為遺傳算法的重要算子來實現(xiàn)最優(yōu)解的快速搜索；文獻[11]提出了基于正交搜索的粒子群優(yōu)化測試用例生成方法，通過利用奇異值分解，改進粒子速度項來提高覆蓋率，減少運行時間。

2 整體技術方案

文中通過分析列控系統(tǒng)的輸入特點，對操作剖面生成方法進行了改進，使得輸入數(shù)據(jù)反映實際輸入的情況，得到合理列控系統(tǒng)的運行剖面。在所得運行剖面的基礎上，結合啟發(fā)性算法來改進測試數(shù)據(jù)生成技術，提高測試用例生成效率。

2.1 運行剖面技術

運行剖面的建立是進行實時軟件可靠性測試的重點，建立運行剖面時需符合系統(tǒng)的實際使用情況。列控系統(tǒng)具有用戶單一、輸入輸出復雜、時間空間相關性的特點，基于以上的特點提出了改進的運行剖面構造流程，并根據(jù)列控系統(tǒng)分析測試需求來構建任務剖面、系統(tǒng)模式剖面以及環(huán)境剖面，最終完成運行剖面的構造[12]。

2.1.1 任務剖面構造

任務剖面是由根據(jù)列控系統(tǒng)功能總結出的具有代表性的功能特征點組成的，在獲得功能點的基礎上進行進一步的模式劃分可以得到系統(tǒng)模式剖面。獲取功能特征點前需要明確所屬功能實體，對于列控系統(tǒng)，它的功能實體分為七大類：軌道電路、區(qū)間信號機點燈、車站聯(lián)鎖、車地通信、臨時限速、鄰站列控中心、異物侵限，這七類為列控系統(tǒng)最高層功能特征，在此基礎上進一步的劃分直至功能特征點不可再分即得到最后具有代表性的功能特征點列表。列控系統(tǒng)關鍵功能特征點劃分如圖1所示，設M={mi|i=1,2,…,7}為系統(tǒng)功能狀態(tài)合集。

2.1.2 系統(tǒng)模式剖面構造

系統(tǒng)模式剖面的構造基于所得的系統(tǒng)功能狀態(tài)合集M，需要選取功能特征點進行模式劃分，劃分時需確定模式參數(shù)pi。模式參數(shù)決定了系統(tǒng)的功能狀態(tài)模式及其出現(xiàn)的概率，如臨時限速這一功能實體中包含臨時限速命令下達這一功能點[13]，其系統(tǒng)模式分為執(zhí)行失敗、執(zhí)行成功、緊急制動三種功能模式，根據(jù)功能測試要求確定系統(tǒng)模式概率取值，進而得到系統(tǒng)模式剖面Mp={(mi,pj)|i=1,2,…,7,j=1,2,…,n}，對于單一系統(tǒng)模式的功能點取pi=1。

圖1 任務剖面構造過程流程

2.1.3 環(huán)境剖面構造

環(huán)境剖面基于系統(tǒng)模式剖面Mp，由若干操作運行值E={ei|i=1,2,…,n}構成，這些運行值會影響系統(tǒng)輸出，但不影響系統(tǒng)模式的變化。在列控系統(tǒng)中，某些輸入?yún)?shù)間存在約束關系，如一個操作常基于另一個操作進行，所以在運行值間需添加參數(shù)間的約束條件。并且列控系統(tǒng)屬于實時軟件，輸入具有序列性，需對每個子剖面的功能運行值進行時序描述形成功能運行值集CombSet={X[ei(t)]|i=1,2,…,n,t∈[0,T]},X[ei(t)]為在某種功能模式下，操作運行值的變化過程[14]。

2.2 改進的粒子群算法

在運行剖面構建完成后，需要選取合適的搜索算法來生成可靠性測試數(shù)據(jù)。文中選用的測試用例搜索算法是粒子群算法，相比其他搜索算法，該算法具有較強的魯棒性和全局搜索能力，便于有效地生成測試用例。在傳統(tǒng)的粒子群算法的基礎上，根據(jù)之前所構造的列控中心運行剖面來改進算法步驟，選取合適的參數(shù)，最終達到優(yōu)化測試序列，縮短測試時間的目的。設計的粒子群測試用例生成算法流程如圖2所示，具體執(zhí)行流程如下：

2.2.1 輸入空間建模

根據(jù)已構建好的列控中心運行剖面可得到符合覆蓋強度和需求規(guī)范的功能運行值集CombSet={X[ei(t)]|i=1,2,…,n,t∈[0,T]}，即根據(jù)任務剖面獲得總結分解后的功能特征點，在獲得的功能特征點的基礎上根據(jù)系統(tǒng)模式剖面確定每個功能特征點所具有的模式參數(shù)，進而根據(jù)環(huán)境剖面獲得在每種模式下的功能運行值及相關約束條件，完成功能運行值集。最后獲得的功能運行值集在構造過程中嚴格按照上文所提出的列控中心運行剖面構造步驟，覆蓋了測試大綱要求的必需的功能點，滿足了覆蓋強度，同時預先剔除了無效的功能特征點，有效縮減了功能運行值集的大小，為之后的測試用例生成減少了計算量，并且避免因此引起的適應度值誤差。

圖2 粒子群測試用例生成算法流程

2.2.2 優(yōu)先級度量

將得到的功能運行值集作為測試用例生成的輸入條件，之后引入了優(yōu)先級度量機制，即先選擇高優(yōu)先權的測試任務來執(zhí)行。主要思想是每次劃分剖面時，根據(jù)測試大綱各部分所占條例數(shù)分配概率，最后得到每個功能運行值對應的操作序列概率，概率越大，優(yōu)先權越高[15]。優(yōu)先權的引入可以減少有價值任務的等待時間，盡量避免因測試時間不足導致重要功能無法測試到的可能，提高了生成數(shù)據(jù)的可靠性。

2.2.3 測試用例生成

步驟1：種群粒子初始化，根據(jù)優(yōu)先級度量選定要執(zhí)行的測試路徑序列，結合得到的功能運行值集確定種群規(guī)模m，即粒子群向量X={Xi|i=1,2,…,m}，粒子維數(shù)n，迭代次數(shù)t，慣性權重w，學習因子c1,c2以及粒子群的位置Xi={Xil|l=1,2,…,n}和速度Vi={Vil|l=1,2,…,n}。其中粒子群的位置通過均勻隨機分布從功能運行值集中選取，粒子自身最優(yōu)位置Pi={Pil|l=1,2,…,n}為對應的Xi。

步驟2：適應度函數(shù)設計，設計要求是使粒子所走路徑盡可能貼近目標測試路徑，通過在程序中插入適應度函數(shù)，來判斷路徑是否被覆蓋，否則進入新一輪的迭代[10]。考慮到所構造的列控系統(tǒng)的特點，在構造適應度函數(shù)時采用了分支距離法，即當選取的測試路徑序列中存在m個分支點，n個參數(shù)時，設計分支函數(shù)fk={fk(x1,x2,…,xn)|k=1,2,…,m}插入到路徑的每個分支前，fk的值取決于分支條件是否滿足，若滿足條件取值為0，否則取值定為偏離值大小。

最后得到的適應度函數(shù)如下：

通過適應度函數(shù)可得到每個粒子的適應值，進而來衡量測試用例的優(yōu)劣。

步驟3：將得到的適應度值與粒子自身最優(yōu)位置Pi、種群最優(yōu)位置Gi相比較，若適應度函數(shù)值更小代表所走路徑更貼合最優(yōu)路徑，則更新Pi、Gi。

步驟4：更新粒子的速度和位置。

速度的更新公式如下：

位置的更新公式如下：

其中，d=1,2,…,n表示粒子所處空間維數(shù)，i=1,2,…,m表示種群中某個粒子。

速度函數(shù)表明在選擇用例時，是在上一次用例選擇的基礎上結合了粒子本身經驗用例選擇和全局最優(yōu)用例，能夠很好地平衡全局和局部的搜索能力，進而得到合適的用例集。

步驟5：判斷粒子是否達到步驟1中所設置的最大迭代次數(shù)t或是找到最優(yōu)解，若滿足條件即輸出，不滿足的話跳轉到步驟2繼續(xù)迭代，直至達到結束條件，返回最優(yōu)的單個測試用例。根據(jù)得到的測試用例t更新CombSet，將其中的t剔除，跳轉到步驟1重復上述步驟，直至CombSet中所有的測試用例被覆蓋，輸出最終的測試用例集。

3 性能評估

3.1 測試數(shù)據(jù)合理性

現(xiàn)有的列控系統(tǒng)測試用例一般是由人力編寫，經過多次審核校驗，確定各部分功能點測試比例以及測試內容，進而完成最后的測試大綱。但人力編寫具有耗費時間，易出錯的缺點，通過自動化生成測試用例，能夠在滿足測試功能完整、測試數(shù)據(jù)合理的情況下，提高測試的時間效率。

文中提出的運行剖面在構造過程中的各部分取值概率參考了往年列控測試大綱中實際運行的功能條例數(shù)，使得根據(jù)剖面生成的數(shù)據(jù)從統(tǒng)計意義上更加接近于真實的使用情況。假設最終要生成的測試用例總數(shù)N=1 000，將生成的測試用例按照功能歸類，最終根據(jù)上述算法所得到的測試用例抽取情況如表1所示。

表1 操作序列的抽取結果

表1數(shù)據(jù)顯示，所抽取到的功能條例與預期抽取功能概率相差不大，抽樣比較穩(wěn)定，數(shù)據(jù)符合預期結果，各部分需要測試的功能比例分配與列控測試大綱中的比例相差不大，進而保證了生成測試數(shù)據(jù)的可靠性與合理性。

3.2 算法改進的優(yōu)越性

選取了測試大綱中軌道電路狀態(tài)更改的用例，針對上述提出的基于粒子群的運行剖面用例生成方法用Python語言在PyCharm平臺進行仿真，并將其與傳統(tǒng)的深度優(yōu)先搜索遍歷方式進行比較。選取用例的路徑總節(jié)點數(shù)為8，變量個數(shù)為3，假設輸入數(shù)據(jù)范圍為0到30，所取間隔為2，粒子群算法中的搜索空間維度n=3，學習因子c1=c2=2，慣性權重w=1.1，種群規(guī)模m=10，迭代次數(shù)分別取t=1、5、10。

仿真結果如圖3所示，其中虛線為在不同輸入數(shù)據(jù)下粒子群算法所花費時間，實線為在不同輸入數(shù)據(jù)下深度優(yōu)先搜索遍歷算法所花費時間。且在不同輸入數(shù)據(jù)下粒子群算法的分支覆蓋率均為100%。從仿真結果中可以看出，在輸入數(shù)據(jù)范圍較小時，深度優(yōu)先搜索遍歷方法的優(yōu)勢明顯，而當r值變大，深度優(yōu)先搜索遍歷方法的優(yōu)勢則逐漸減?。煌瑫r，可以看出，在滿足分支覆蓋率的前提下，盡量減少粒子群算法的迭代數(shù)可以減少用例生成時間。因此對于輸入數(shù)據(jù)范圍較大的列控系統(tǒng)而言，文中提出的基于粒子群的運行剖面用例生成方法能在滿足分支覆蓋率的前提下，有效地減少用例生成時間并進行用例約減。

圖3 運行剖面用例生成方法方針對比

4 結束語

為了提高列控軟件測試的效率，改善人力測試的不足，分析并設計了列控系統(tǒng)運行剖面的構建過程、基于粒子群算法的運行剖面用例生成方法。提出的列控系統(tǒng)運行剖面結合了列控系統(tǒng)功能特征，通過構造合理的運行剖面來生成合適比例的測試用例，滿足了測試的功能需求。在生成測試用例時，采用了粒子群算法，與構造好的剖面相結合來生成測試用例。針對上述提出的基于粒子群的運行剖面用例生成方法，選取了軌道電路狀態(tài)更改的用例來進行仿真，并將其與傳統(tǒng)的深度優(yōu)先搜索遍歷方式進行比較，證明該方法能夠根據(jù)需求生成合適功能比例的用例，減少冗余的測試用例生成，并且在滿足用例覆蓋率的前提下，減少用例的生成時間。