基于擴展有限狀態機的SCA符合性測試方法研究

伍旭東，唐 麒，張 偉，張 健，魏急波，王一軍

1.中南大學 計算機學院，長沙410083

2.國防科技大學 電子科學學院，長沙410073

3.中南大學 自動化學院，長沙410083

軟件無線電（Software Definition Radio，SDR）[1-2]的基本思想是以一個通用的硬件平臺為依托，通過軟件編程來實現電臺所需的各種功能，因此具有很強的靈活性和開放性。軟件無線電系統運行在各種不同的硬件平臺上，使用的軟件產品可能存在差異，不同系統之間難以實現信息交互。為了解決這個問題，聯合戰術網絡中心發布了軟件通信體系結構（Software Communication Architecture，SCA）[3-4]標準。SCA標準提供了應用程序接口要求及組件定義和聚合要求，通過定義設備組件對底層的硬件進行屏蔽，實現上層的軟件應用和底層硬件相互分離，使得軟件應用能夠控制不同的硬件設備，提高軟件應用的通用性[5]。

SCA標準是組件功能需求的總集，組件產品的符合性測試應根據其功能定位，從需求集中選取相應的子集，根據子集對具體組件進行測試[6]，其目的是驗證實際的組件是否滿足SCA標準中的組件定義，保證系統能夠對這些應用進行統一的管理，實現軟件應用的通用性和跨平臺性[7-9]。

在SCA符合性測試方面，聯合戰術網絡中心開發了R-Check SCA測試工具，它是現階段主流的SCA項目測試工具，采用的是靜態測試的方法進行符合性測試，能夠對C++/C源代碼進行解析，尋找系統中存在的錯誤，但使用該工具要求測試人員具有較高的編程水平，并且測試結果存在一定的波動性[10]。Botella等人提出了基于模型的SCA符合性測試用例生成方法，構建了一個測試生成系統，根據組件的UML（Unified Modeling Language）和OCL（Object Constraint Language）模型，預測待測系統的預期行為，對測試用例進行集成[11]。Springer等人在R-Check SCA的基礎上提出了基于模型的SCA開發工具MBDEs（Model-Based Development Environments）。MBDEs將模型的概念擴展到開發階段，允許開發人員使用模型構造系統[12]。與之相似的還有NordiaSoft公司開發的SCA開發軟件組，皆采用基于模型開發的概念，從開發端去解決標準符合性的問題。

擴展有限狀態機（Extended Finite State Machine，EFSM）模型是一種常用軟件測試模型，被廣泛應用于通信協議、軟件嵌入式系統等測試建模。Ilie等人提出了關于EFSM的縮減算法，能夠有效地減小模型的規模[13]。在此基礎上，Kelly等人提出了不定向切片技術，能夠針對特定問題對模型進行裁剪[14]。Ramalingom等人基于EFSM模型，提出采用控制分析技術生成測試序列，能夠很好地保證測試的覆蓋度。張涌等人針對測試冗余問題，提出了R-Wp方法，減少模型中不可行遷移，從而提高測試序列生成的效率[15]。

國內外目前對于SCA符合性測試的研究還處于起步階段，主要是采取靜態分析的方法進行測試，其效果具有波動性，其次是缺乏自動化的測試方法，測試過程需要人工參與，對于規模龐大的通信系統，很容易造成錯撿或者漏檢。針對目前存在的問題，結合EFSM原理，以及已存在的EFSM方面的研究，根據SCA符合性測試的情況進行改進，提出一種基于EFSM的SCA符合性測試模型，該模型能夠對不同需求測試之間的依賴關系進行有效的分析，并基于該模型提出測試序列的自動化構建方法，為實現符合性測試自動化提供支撐。

1 基于EFSM的SCA符合性測試模型

基于EFSM的SCA符合性測試模型由一個六元組組成，表示為：

其中，S={s0,s1,…,sn}為狀態集，是測試過程存在的所有狀態的集合；s0表示測試的初始狀態，s0∈S；V為測試過程中所需要用到的變量的集合，在SCA符合性測試中存在的變量有載荷數、組件連接數等，變量可作為測試是否可執行的判斷指標；I和O表示測試系統的輸入和輸出集合；T為測試系統中狀態之間的遷移集合[12-13]。

T中的每個元素t又由一個五元組組成，表示為：

其中，source(t)和target(t)分別表示遷移t的源狀態和目標狀態；condition(t)為t遷移觸發的前置條件，當前置條件不滿足時，遷移不能進行觸發；event(t)、action(t)分別表示t觸發的事件和執行的操作。event(t)、condition(t)和action(t)共同組成了t的標簽，其表達式為event[condition]/action。

SCA標準是由大量的組件功能需求構成的，每個需求都有對應的測試用例，分析各需求測試的前置條件，以及執行該測試對組件的影響，將其轉換成標簽為event[condition]/action的遷移和執行測試抵達的末狀態。任意組件的符合性測試是根據其功能定位和具體要求，從SCA標準中選擇相應的子集進行測試。測試時，用戶根據組件功能需求進行輸入，系統從需求全集中抽取需求子集，根據下述規則進行連接：

規則1若任意需求測試A的前置條件condition依賴于另一需求測試B的執行動作action，則需求測試A為需求測試B的后繼。

規則2若任意數量需求測試的前置條件condition相同，并且這些需求測試的執行動作并不會使得該條件不成立，則這些需求測試為雙向互通的；任意需求測試的執行動作使得該條件不成立，則其他需求測試對其為單向測試。

圖1 為根據現階段SCA符合性測試較為常用的基本組件部分需求集所構造的EFSM模型。表1是圖1各個狀態之間的遷移的描述，表中Num為模型中的遷移編號，source和target分別表示遷移的起始狀態和末狀態，condition為遷移觸發的條件，action為執行遷移后系統變量產生的改變，Req表示遷移對應的需求測試在SCA標準中的需求編號。

表1 模型遷移描述Table 1 Transition description of model

圖1 基于EFSM的SCA符合性測試模型Fig.1 SCA compliance testing model based on EFSM

符合性測試過程中，需求的測試會對組件的狀態造成改變，在模型中使用變量來表示當前組件的狀態。該模型中存在3個變量，分別是initialized、started和connected，而遷移表示某項需求測試，如SCA7的描述是連接使用端口操作，應根據輸入的端口連接參數建立與對應組件的連接，在模型中由t7表示；SCA10的描述是斷開連接端口操作，應根據輸入的端口斷開連接參數斷開與對應組件的連接，在模型中由t8表示。遷移均有標簽event[condition]/action，其標簽可能為空，模型根據當前的變量值對遷移標簽上的condition進行判斷，選取當前符合條件的測試，在執行測試后對變量進行實時的改變，從而保證了構成測試序列的可行性。

2 測試序列自動生成

該測試序列生成方法的總體流程如圖2所示。首先輸入需要進行測試的需求集，根據該需求集構造測試模型，測試系統將對模型進行反復遍歷，隨機生成測試路徑，直到已生成的測試序列集滿足覆蓋要求并到達設置的最小規模。此時生成的測試序列集存在很強的隨機性，集合中可能存在冗余，影響測試效率，因此采用基于集合的貪心算法對測試序列集進行挑選，減少測試序列集中的冗余，提高測試效率，并返回最終的結果。

圖2 測試序列生成流程Fig.2 Test sequence generation process

需求集總是包含多個需求，并且需要對這些需求進行反復的測試。這些需求測試之間存在相互影響，因此在實際的測試過程中為保證測試的覆蓋度，要對組件進行反復的初始化、釋放。如圖1中，構成任一由組件初始狀態S0最終抵達組件釋放狀態released的遷移集稱為一條測試序列：

式（3）為測試序列表達公式，一條測試序列由測試模型中多個遷移構成。式（4）中wpathi是測試序列pathi的執行時間，為構成該序列的所有測試時間的和；wpathij表示具體測試所需的測試時間。系統通過不斷地生成測試序列，加入到測試序列集中，構造初始測試序列集S：

式（6）中reqs表示需要進行測試的需求集，即生成的測試序列集應保證能夠覆蓋到所有的需求測試，保證測試的可靠性。由于構造初始測試序列集的測試序列是隨機生成的，可能會存在冗余或者測試效率較低的測試序列個體，這將造成測試時間的增加。在保證測試覆蓋度的基礎上，為提高測試效率，減少測試用時，采用一種基于集合覆蓋的貪心算法[16]對測試序列進行選取。該算法的核心思想是構建每次從初始集合中選擇n個集合，這n個包含的未被覆蓋的元素個數最多，反復迭代，直到完全覆蓋。將其與符合性測試的需求相結合并進行改進，為保證每次選擇的收益最大化，需要設置一個適應度函數，評估測試序列的優劣，該適應度函數如下。

式（7）中，Wi為測試序列的適應度，wpathi是測試序列的執行時間，reqi為該序列覆蓋到的測試需求集，C為當前已被覆蓋的測試需求集。以測試序列個體能為測試集合增加的覆蓋需求數量和造成的時間開銷來評估測試序列的優劣，因為選擇目標是測試用時最短，故將適應度函數取反。每次從初始序列集中選擇n條序列，這n條個體的總適應度為：

每次選取的n條序列應使得式（8）中的W最大，將這n條序列加入到新集合中，直到產生的新集合能夠對需求集實現全覆蓋。算法如下：

算法第1~5行中，Reps表示需要覆蓋的需求集，P表示當前已生成的可覆蓋需求集的測試序列集，n為算法的選擇參數，S為當前挑選出的測試序列集合，C為當前集合所包含的需求集。

3 實驗分析

實驗將需求集輸入到根據此測試序列生成方法搭建的系統中，根據需求集構造測試模型，使用經改進的貪心算法生成測試序列。為保證該方法的通用性，采用三個不同需求數量的基礎需求集，分別為1#、2#、3#需求集。1#需求集為SCA符合性測試中基本組件的較為常用的部分基礎功能需求集，該需求集包含9個功能需求，主要用于保證組件擁有初始化、配置屬性、查詢屬性、連接等基礎功能的測試；2#需求集為完備的基本組件功能測試需求集，該需求集在1#需求集的基礎上增加了錯誤處理、日志輸出、生產事件等功能的測試，總共包含33個需求測試；3#需求集為可管理應用組件的組件功能需求集，可管理應用組件是基本組件的擴展組件，因此該需求集需要包含2#需求集，并增加訪問文件系統、組件注冊等功能測試，總共包含39個需求測試。各需求集如表2所示。

表2 需求集Table 2 Set of requirements

表2 中Num表示需求集的編號，Reqs表示對應需求集包含的測試需求在SCA標準中的需求編號，Count表示該需求集包含的需求總數量。

為了說明該測試方法的工作原理，給出實驗的具體過程，以1#需求集為例進行分析。需要輸入的數據如表3所示，Req表示需求的具體編號，Test Time表示對應的需求測試所需要的平均時間。根據SCA標準的要求，部分需求要求進行重復多次的測試，因此需要對測試的執行次數進行設置，即Repeat Times。

表3 輸入需求集Table 3 Set of requirements for input

將這些數據輸入到測試系統中，測試系統根據前文所述的規則1以及規則2構造對應的EFSM模型。根據該需求集所構造的測試模型如圖1所示。測試系統不斷地生成由S0到released的測試序列，構造測試序列集，直到滿足測試覆蓋要求和各需求的重復次數要求或者達到指定最小規模，如表4所示。將貪心算法中的參數設置為2，使用該算法對表4所顯示的測試序列集進行挑選，最終結果如表5所示。

表4 初始測試序列集Table 4 Initial set of test sequences

表5 最終測試序列集Table 5 Final set of test sequences

表4 和表5中，Path為由系統生成的測試序列的編號，Transition表示測試序列的遷移組成，Req表示該測試路徑所覆蓋到的需求編號，需求編號后的括號內的數字表示需求測試重復的次數，如7（2）表示需求SCA7的測試在測試序列中重復進行了2次，Time為測試路徑的總用時。對比表5和表4可以看出，由該方法生成的測試序列集共包含4條測試序列，能夠滿足需求測試的覆蓋要求和重復測試要求，采用該測試序列集進行測試所需的測試時間為91.1 s。

再將2#和3#需求集分別輸入到測試系統中，具體步驟相同，得到最終的實驗結果如表6所示。

表6 實驗結果Table 6 Experimental results

實驗結果表明生成的測試序列集均能對測試需求集進行完整的覆蓋。但采用該方法解決實際的問題時，最終生成的測試序列集的測試用時可能受到兩個因素的影響，一是設定的最小初始測試序列規模，二是貪心算法參數。為進一步分析這兩個因素對于最終結果的影響，采用2#需求集進行實驗。將2#需求集輸入到測試序列生成系統中，系統根據需求集構造測試模型，在保證測試覆蓋度的基礎上對初始的測試序列集規模進行限定。系統首先生成相應大小的測試序列集，然后進行選擇，最后返回最終的測試序列集。實驗結果如圖3所示。

圖3 初始測試序列集規模和測試用時的關系Fig.3 Relationship between size of initial test sequence set and test time

圖3 中橫坐標為系統生成的初始測試序列集規模，縱坐標為初始測試序列集經挑選后產生的最終測試序列集的執行時間。結果表明，隨著初始測試序列集的規模增大，生成的測試序列集的執行時間變短，最終收斂于一個較優值。為保證結果的優越性，應設置合適的初始測試序列集規模。

將初始測試序列集規模設置為250，分別設置貪心算法的參數為1至5，最終生成的測試序列集的執行時間如圖4所示。

圖4 貪心算法參數和測試用時的關系Fig.4 Relationship between size of greedy algorithm parameters and test time

實驗表明參數設置越大，經該方法生成的測試序列集效果越好。參數設置為1時，其效果等同于傳統貪心算法，當參數設置為2時，提升最為顯著，參數繼續增大時，最終結果提升比較微弱，但算法的時間復雜度上升較快。在解決實際問題時，應根據具體的測試需求進行參數設置。

4 結束語

隨著軟件無線電技術的不斷發展，越來越多的廠家都投入到軟件無線電產品的生產中，符合性測試是這些產品可移植性、可配置性及互操作性的重要保障。任一組件產品的符合性測試都是由SCA標準中多個需求的測試構成的，各需求測試之間存在相互影響，如何構造合理的測試序列，保證符合性測試的可行性，針對該問題提出了一種基于EFSM的SCA符合性測試模型以及測試序列自動生成方法。在模型中以遷移表示需求測試，測試會對組件狀態進行實時的改變，通過對組件的當前狀態進行判斷來選取后續可行的需求測試，保證測試序列的可行性。為保證測試的覆蓋度，并且提高測試效率，通過隨機生成可行測試序列的方式保證需求的全覆蓋，采用改進的貪心算法對測試序列集進行挑選，降低測試用時。實驗證明，該方法能夠很好地保證測試的覆蓋度，有效地減少測試的總用時，彌補了目前國內對SCA符合性測試研究的空缺，為后續的測試自動化提供了有效的支撐。

該方法目前階段主要是針對單個組件的符合性測試生成有效的測試序列，保證測試的可行性，提高測試效率。下一階段的工作將致力于多組件的交互測試，在多個組件存在相互影響的情況下，如何組織測試，保證測試的可行性。