基于擴(kuò)展有限狀態(tài)機(jī)的SCA符合性測(cè)試方法研究

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

1.中南大學(xué) 計(jì)算機(jī)學(xué)院，長(zhǎng)沙410083

2.國(guó)防科技大學(xué) 電子科學(xué)學(xué)院，長(zhǎng)沙410073

3.中南大學(xué) 自動(dòng)化學(xué)院，長(zhǎng)沙410083

軟件無(wú)線電（Software Definition Radio，SDR）[1-2]的基本思想是以一個(gè)通用的硬件平臺(tái)為依托，通過(guò)軟件編程來(lái)實(shí)現(xiàn)電臺(tái)所需的各種功能，因此具有很強(qiáng)的靈活性和開放性。軟件無(wú)線電系統(tǒng)運(yùn)行在各種不同的硬件平臺(tái)上，使用的軟件產(chǎn)品可能存在差異，不同系統(tǒng)之間難以實(shí)現(xiàn)信息交互。為了解決這個(gè)問(wèn)題，聯(lián)合戰(zhàn)術(shù)網(wǎng)絡(luò)中心發(fā)布了軟件通信體系結(jié)構(gòu)（Software Communication Architecture，SCA）[3-4]標(biāo)準(zhǔn)。SCA標(biāo)準(zhǔn)提供了應(yīng)用程序接口要求及組件定義和聚合要求，通過(guò)定義設(shè)備組件對(duì)底層的硬件進(jìn)行屏蔽，實(shí)現(xiàn)上層的軟件應(yīng)用和底層硬件相互分離，使得軟件應(yīng)用能夠控制不同的硬件設(shè)備，提高軟件應(yīng)用的通用性[5]。

SCA標(biāo)準(zhǔn)是組件功能需求的總集，組件產(chǎn)品的符合性測(cè)試應(yīng)根據(jù)其功能定位，從需求集中選取相應(yīng)的子集，根據(jù)子集對(duì)具體組件進(jìn)行測(cè)試[6]，其目的是驗(yàn)證實(shí)際的組件是否滿足SCA標(biāo)準(zhǔn)中的組件定義，保證系統(tǒng)能夠?qū)@些應(yīng)用進(jìn)行統(tǒng)一的管理，實(shí)現(xiàn)軟件應(yīng)用的通用性和跨平臺(tái)性[7-9]。

在SCA符合性測(cè)試方面，聯(lián)合戰(zhàn)術(shù)網(wǎng)絡(luò)中心開發(fā)了R-Check SCA測(cè)試工具，它是現(xiàn)階段主流的SCA項(xiàng)目測(cè)試工具，采用的是靜態(tài)測(cè)試的方法進(jìn)行符合性測(cè)試，能夠?qū)++/C源代碼進(jìn)行解析，尋找系統(tǒng)中存在的錯(cuò)誤，但使用該工具要求測(cè)試人員具有較高的編程水平，并且測(cè)試結(jié)果存在一定的波動(dòng)性[10]。Botella等人提出了基于模型的SCA符合性測(cè)試用例生成方法，構(gòu)建了一個(gè)測(cè)試生成系統(tǒng)，根據(jù)組件的UML（Unified Modeling Language）和OCL（Object Constraint Language）模型，預(yù)測(cè)待測(cè)系統(tǒng)的預(yù)期行為，對(duì)測(cè)試用例進(jìn)行集成[11]。Springer等人在R-Check SCA的基礎(chǔ)上提出了基于模型的SCA開發(fā)工具M(jìn)BDEs（Model-Based Development Environments）。MBDEs將模型的概念擴(kuò)展到開發(fā)階段，允許開發(fā)人員使用模型構(gòu)造系統(tǒng)[12]。與之相似的還有NordiaSoft公司開發(fā)的SCA開發(fā)軟件組，皆采用基于模型開發(fā)的概念，從開發(fā)端去解決標(biāo)準(zhǔn)符合性的問(wèn)題。

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

國(guó)內(nèi)外目前對(duì)于SCA符合性測(cè)試的研究還處于起步階段，主要是采取靜態(tài)分析的方法進(jìn)行測(cè)試，其效果具有波動(dòng)性，其次是缺乏自動(dòng)化的測(cè)試方法，測(cè)試過(guò)程需要人工參與，對(duì)于規(guī)模龐大的通信系統(tǒng)，很容易造成錯(cuò)撿或者漏檢。針對(duì)目前存在的問(wèn)題，結(jié)合EFSM原理，以及已存在的EFSM方面的研究，根據(jù)SCA符合性測(cè)試的情況進(jìn)行改進(jìn)，提出一種基于EFSM的SCA符合性測(cè)試模型，該模型能夠?qū)Σ煌枨鬁y(cè)試之間的依賴關(guān)系進(jìn)行有效的分析，并基于該模型提出測(cè)試序列的自動(dòng)化構(gòu)建方法，為實(shí)現(xiàn)符合性測(cè)試自動(dòng)化提供支撐。

1 基于EFSM的SCA符合性測(cè)試模型

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

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

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

其中，source(t)和target(t)分別表示遷移t的源狀態(tài)和目標(biāo)狀態(tài)；condition(t)為t遷移觸發(fā)的前置條件，當(dāng)前置條件不滿足時(shí)，遷移不能進(jìn)行觸發(fā)；event(t)、action(t)分別表示t觸發(fā)的事件和執(zhí)行的操作。event(t)、condition(t)和action(t)共同組成了t的標(biāo)簽，其表達(dá)式為event[condition]/action。

SCA標(biāo)準(zhǔn)是由大量的組件功能需求構(gòu)成的，每個(gè)需求都有對(duì)應(yīng)的測(cè)試用例，分析各需求測(cè)試的前置條件，以及執(zhí)行該測(cè)試對(duì)組件的影響，將其轉(zhuǎn)換成標(biāo)簽為event[condition]/action的遷移和執(zhí)行測(cè)試抵達(dá)的末狀態(tài)。任意組件的符合性測(cè)試是根據(jù)其功能定位和具體要求，從SCA標(biāo)準(zhǔn)中選擇相應(yīng)的子集進(jìn)行測(cè)試。測(cè)試時(shí)，用戶根據(jù)組件功能需求進(jìn)行輸入，系統(tǒng)從需求全集中抽取需求子集，根據(jù)下述規(guī)則進(jìn)行連接：

規(guī)則1若任意需求測(cè)試A的前置條件condition依賴于另一需求測(cè)試B的執(zhí)行動(dòng)作action，則需求測(cè)試A為需求測(cè)試B的后繼。

規(guī)則2若任意數(shù)量需求測(cè)試的前置條件condition相同，并且這些需求測(cè)試的執(zhí)行動(dòng)作并不會(huì)使得該條件不成立，則這些需求測(cè)試為雙向互通的；任意需求測(cè)試的執(zhí)行動(dòng)作使得該條件不成立，則其他需求測(cè)試對(duì)其為單向測(cè)試。

圖1 為根據(jù)現(xiàn)階段SCA符合性測(cè)試較為常用的基本組件部分需求集所構(gòu)造的EFSM模型。表1是圖1各個(gè)狀態(tài)之間的遷移的描述，表中Num為模型中的遷移編號(hào)，source和target分別表示遷移的起始狀態(tài)和末狀態(tài)，condition為遷移觸發(fā)的條件，action為執(zhí)行遷移后系統(tǒng)變量產(chǎn)生的改變，Req表示遷移對(duì)應(yīng)的需求測(cè)試在SCA標(biāo)準(zhǔn)中的需求編號(hào)。

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

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

符合性測(cè)試過(guò)程中，需求的測(cè)試會(huì)對(duì)組件的狀態(tài)造成改變，在模型中使用變量來(lái)表示當(dāng)前組件的狀態(tài)。該模型中存在3個(gè)變量，分別是initialized、started和connected，而遷移表示某項(xiàng)需求測(cè)試，如SCA7的描述是連接使用端口操作，應(yīng)根據(jù)輸入的端口連接參數(shù)建立與對(duì)應(yīng)組件的連接，在模型中由t7表示；SCA10的描述是斷開連接端口操作，應(yīng)根據(jù)輸入的端口斷開連接參數(shù)斷開與對(duì)應(yīng)組件的連接，在模型中由t8表示。遷移均有標(biāo)簽event[condition]/action，其標(biāo)簽可能為空，模型根據(jù)當(dāng)前的變量值對(duì)遷移標(biāo)簽上的condition進(jìn)行判斷，選取當(dāng)前符合條件的測(cè)試，在執(zhí)行測(cè)試后對(duì)變量進(jìn)行實(shí)時(shí)的改變，從而保證了構(gòu)成測(cè)試序列的可行性。

2 測(cè)試序列自動(dòng)生成

該測(cè)試序列生成方法的總體流程如圖2所示。首先輸入需要進(jìn)行測(cè)試的需求集，根據(jù)該需求集構(gòu)造測(cè)試模型，測(cè)試系統(tǒng)將對(duì)模型進(jìn)行反復(fù)遍歷，隨機(jī)生成測(cè)試路徑，直到已生成的測(cè)試序列集滿足覆蓋要求并到達(dá)設(shè)置的最小規(guī)模。此時(shí)生成的測(cè)試序列集存在很強(qiáng)的隨機(jī)性，集合中可能存在冗余，影響測(cè)試效率，因此采用基于集合的貪心算法對(duì)測(cè)試序列集進(jìn)行挑選，減少測(cè)試序列集中的冗余，提高測(cè)試效率，并返回最終的結(jié)果。

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

需求集總是包含多個(gè)需求，并且需要對(duì)這些需求進(jìn)行反復(fù)的測(cè)試。這些需求測(cè)試之間存在相互影響，因此在實(shí)際的測(cè)試過(guò)程中為保證測(cè)試的覆蓋度，要對(duì)組件進(jìn)行反復(fù)的初始化、釋放。如圖1中，構(gòu)成任一由組件初始狀態(tài)S0最終抵達(dá)組件釋放狀態(tài)released的遷移集稱為一條測(cè)試序列：

式（3）為測(cè)試序列表達(dá)公式，一條測(cè)試序列由測(cè)試模型中多個(gè)遷移構(gòu)成。式（4）中wpathi是測(cè)試序列pathi的執(zhí)行時(shí)間，為構(gòu)成該序列的所有測(cè)試時(shí)間的和；wpathij表示具體測(cè)試所需的測(cè)試時(shí)間。系統(tǒng)通過(guò)不斷地生成測(cè)試序列，加入到測(cè)試序列集中，構(gòu)造初始測(cè)試序列集S：

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

式（7）中，Wi為測(cè)試序列的適應(yīng)度，wpathi是測(cè)試序列的執(zhí)行時(shí)間，reqi為該序列覆蓋到的測(cè)試需求集，C為當(dāng)前已被覆蓋的測(cè)試需求集。以測(cè)試序列個(gè)體能為測(cè)試集合增加的覆蓋需求數(shù)量和造成的時(shí)間開銷來(lái)評(píng)估測(cè)試序列的優(yōu)劣，因?yàn)檫x擇目標(biāo)是測(cè)試用時(shí)最短，故將適應(yīng)度函數(shù)取反。每次從初始序列集中選擇n條序列，這n條個(gè)體的總適應(yīng)度為：

每次選取的n條序列應(yīng)使得式（8）中的W最大，將這n條序列加入到新集合中，直到產(chǎn)生的新集合能夠?qū)π枨蠹瘜?shí)現(xiàn)全覆蓋。算法如下：

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

3 實(shí)驗(yàn)分析

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

表2 需求集Table 2 Set of requirements

表2 中Num表示需求集的編號(hào)，Reqs表示對(duì)應(yīng)需求集包含的測(cè)試需求在SCA標(biāo)準(zhǔn)中的需求編號(hào)，Count表示該需求集包含的需求總數(shù)量。

為了說(shuō)明該測(cè)試方法的工作原理，給出實(shí)驗(yàn)的具體過(guò)程，以1#需求集為例進(jìn)行分析。需要輸入的數(shù)據(jù)如表3所示，Req表示需求的具體編號(hào)，Test Time表示對(duì)應(yīng)的需求測(cè)試所需要的平均時(shí)間。根據(jù)SCA標(biāo)準(zhǔn)的要求，部分需求要求進(jìn)行重復(fù)多次的測(cè)試，因此需要對(duì)測(cè)試的執(zhí)行次數(shù)進(jìn)行設(shè)置，即Repeat Times。

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

將這些數(shù)據(jù)輸入到測(cè)試系統(tǒng)中，測(cè)試系統(tǒng)根據(jù)前文所述的規(guī)則1以及規(guī)則2構(gòu)造對(duì)應(yīng)的EFSM模型。根據(jù)該需求集所構(gòu)造的測(cè)試模型如圖1所示。測(cè)試系統(tǒng)不斷地生成由S0到released的測(cè)試序列，構(gòu)造測(cè)試序列集，直到滿足測(cè)試覆蓋要求和各需求的重復(fù)次數(shù)要求或者達(dá)到指定最小規(guī)模，如表4所示。將貪心算法中的參數(shù)設(shè)置為2，使用該算法對(duì)表4所顯示的測(cè)試序列集進(jìn)行挑選，最終結(jié)果如表5所示。

表4 初始測(cè)試序列集Table 4 Initial set of test sequences

表5 最終測(cè)試序列集Table 5 Final set of test sequences

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

再將2#和3#需求集分別輸入到測(cè)試系統(tǒng)中，具體步驟相同，得到最終的實(shí)驗(yàn)結(jié)果如表6所示。

表6 實(shí)驗(yàn)結(jié)果Table 6 Experimental results

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

圖3 初始測(cè)試序列集規(guī)模和測(cè)試用時(shí)的關(guān)系Fig.3 Relationship between size of initial test sequence set and test time

圖3 中橫坐標(biāo)為系統(tǒng)生成的初始測(cè)試序列集規(guī)模，縱坐標(biāo)為初始測(cè)試序列集經(jīng)挑選后產(chǎn)生的最終測(cè)試序列集的執(zhí)行時(shí)間。結(jié)果表明，隨著初始測(cè)試序列集的規(guī)模增大，生成的測(cè)試序列集的執(zhí)行時(shí)間變短，最終收斂于一個(gè)較優(yōu)值。為保證結(jié)果的優(yōu)越性，應(yīng)設(shè)置合適的初始測(cè)試序列集規(guī)模。

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

圖4 貪心算法參數(shù)和測(cè)試用時(shí)的關(guān)系Fig.4 Relationship between size of greedy algorithm parameters and test time

實(shí)驗(yàn)表明參數(shù)設(shè)置越大，經(jīng)該方法生成的測(cè)試序列集效果越好。參數(shù)設(shè)置為1時(shí)，其效果等同于傳統(tǒng)貪心算法，當(dāng)參數(shù)設(shè)置為2時(shí)，提升最為顯著，參數(shù)繼續(xù)增大時(shí)，最終結(jié)果提升比較微弱，但算法的時(shí)間復(fù)雜度上升較快。在解決實(shí)際問(wèn)題時(shí)，應(yīng)根據(jù)具體的測(cè)試需求進(jìn)行參數(shù)設(shè)置。

4 結(jié)束語(yǔ)

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

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