發(fā)布時(shí)間：2021-06-13 03:13

　　擴(kuò)展有限狀態(tài)機(jī)（EFSM）相比于有限狀態(tài)機(jī)（FSM）能夠更加精確地刻畫系統(tǒng)的動(dòng)態(tài)行為,因而廣泛作為各種控制流與數(shù)據(jù)流系統(tǒng)的測試模型。在EFSM模型的測試中,使用搜索的方法獲得觸發(fā)目標(biāo)測試路徑的測試數(shù)據(jù)是近年來的一個(gè)研究熱點(diǎn)。為進(jìn)一步提高搜索效率,在遺傳算法（GA）的基礎(chǔ)上提出一種自動(dòng)分離測試路徑中無關(guān)輸入變量的方法,該方法通過分析模型中變量與遷移間的關(guān)系,判定不影響子路徑中謂詞條件的無關(guān)輸入變量,進(jìn)而從個(gè)體中將其分離以實(shí)現(xiàn)搜索空間的自動(dòng)縮減,提升測試數(shù)據(jù)生成效率。對幾種具有不同復(fù)雜度的基準(zhǔn)EFSM模型進(jìn)行實(shí)驗(yàn)后的結(jié)果表明,該方法生成有效測試數(shù)據(jù)的成功率均達(dá)到98. 2%以上,且與未分離輸入變量的遺傳算法相比,所需平均迭代次數(shù)減少44. 7%～85. 9%,平均運(yùn)行時(shí)間減少24. 1%～85. 5%。 

【文章來源】：北京航空航天大學(xué)學(xué)報(bào). 2019,45(05)北大核心EICSCD

【文章頁數(shù)】：11 頁

【部分圖文】：

ATM的擴(kuò)展有限狀態(tài)機(jī)模型Fig．1ExtendedfinitestatemachinemodelofATM將不同的測試數(shù)據(jù)代入到LTP中所實(shí)際經(jīng)過的關(guān)系可以劃分為變量與賦值語句及謂詞條件中

北京航空航天大學(xué)學(xué)報(bào)2019年圖2EFSM中的一條測試路徑Fig．2AtestpathinEFSM圖3不同變量間的關(guān)系圖Fig．3ＲelationshipdiagramamongdifferentvariablesQ=1110111000100011根據(jù)矩陣Q及算法3可以得出:變量{a，b，c，d}的取值會(huì)對遷移t3的謂詞條件能否滿足造成影響，而遷移t4的謂詞條件僅受變量d的影響，由于{a，b，c，d}均為輸入變量，因此對于LTP的子路徑L'TP=t4來講，變量{a，b，c}屬于無關(guān)輸入變量，可以分離，其起始分離遷移為t3，而變量d對應(yīng)的起始分離遷移為t4，說明其在整個(gè)測試路徑中不能分離。3無關(guān)輸入變量的自動(dòng)分離方法3．1自動(dòng)分離方法及測試數(shù)據(jù)生成過程基于無關(guān)輸入變量分離與遺傳算法的EFSM測試數(shù)據(jù)生成過程如圖4所示。圖4EFSM測試數(shù)據(jù)生成的實(shí)現(xiàn)過程Fig．4ImplementationprocessofEFSMtestdatageneration設(shè)待測EFSM模型M包含的輸入變量為Iv={x1，x2，…，xn}，變量的取值空間為D，選取M中的一條目標(biāo)測試路徑LTP=［t0，t1，…，tm－1］，設(shè)遺傳算法產(chǎn)生的初始種群包含k個(gè)個(gè)體，不同個(gè)體對應(yīng)的測試數(shù)據(jù)分別為X1，X2，…，Xk，不同個(gè)體以其對應(yīng)測試數(shù)據(jù)作為輸入，在動(dòng)態(tài)執(zhí)行EFSM模型時(shí)，所能實(shí)際經(jīng)過的路徑分別為LTP1，LTP2，…，LTPk，以LTP表示相應(yīng)路徑的路徑長度(路徑所包含遷移的個(gè)數(shù))，由1．2節(jié)可知，實(shí)際經(jīng)過的路徑長度越長，該個(gè)體的適應(yīng)度值越好。無關(guān)輸入變量的分離方法為:在每一次迭代中，

(t1)+2，…，xj(t2)}，…，{xj(tm－1)+1，xj(tm－1)+2，…，xj(tm)}，且0＜j(t1)＜j(t2)＜…＜j(tm)＜n，則此時(shí)搜索空間將分別變?yōu)镈t1?∏ni=j(t1)+1DiDt2?∏ni=j(t2)+1Di?Dtm?∏ni=j(tm)+1Di(5)設(shè)該測試路徑目標(biāo)解的空間為Dr，則D，Dt1，Dt2，…，Dtm及Dr的關(guān)系可以用圖5表示。由圖5可知，隨著分離變量的增多，搜索空間逐漸減小，在更小的搜索空間內(nèi)進(jìn)行搜索，將顯著提高遺傳算法的搜索效率［16］。圖5不同搜索空間之間的關(guān)系Fig．5Ｒelationshipbetweendifferentsearchspaces4實(shí)驗(yàn)為了驗(yàn)證采用本文方法對遺傳算法搜索效率的影響，將采用全空間搜索(GlobalSpaceSearch，GSS)的傳統(tǒng)遺傳算法［3］與本文無關(guān)輸入變量分離(IrrelevantInputVariablesSeparation，IIVS)的遺傳算法進(jìn)行對比，2種方法均采用二進(jìn)制編碼、輪盤賭選擇、使用單點(diǎn)交叉及單點(diǎn)變異，算法的一些其他參數(shù)為:交叉概率0．75，變異概率0．1，初始種群規(guī)模25，最大迭代次數(shù)50000代。此外，為進(jìn)一步驗(yàn)證IIVS方法的優(yōu)勢，本文還對使用IIVS方法的隨機(jī)算法(ＲandomAlgorithm，ＲA)與全空間搜索的隨機(jī)算法［17］進(jìn)行了比較，與遺傳算法中無關(guān)輸入變量的分離方法類似，IIVS-ＲA也是在每次迭代中判斷實(shí)際經(jīng)過的路徑是否包含可分離輸入變量的起始分離遷移，若包含則在以后的搜索過程中固定該變量的取值，以此達(dá)?

【參考文獻(xiàn)】：
期刊論文
[1]基于EFSM不定型切片測試用例自動(dòng)生成的研究[J]. 蘇寧,郭俊霞,李征,趙瑞蓮.  計(jì)算機(jī)研究與發(fā)展. 2017(03)
[2]基于路徑自動(dòng)分割的測試數(shù)據(jù)生成方法[J]. 廖偉志.  電子學(xué)報(bào). 2016(09)
[3]基于程序變異的Simulink模型測試方法[J]. 周藝斌,殷永峰,李驍?shù)?王明威.  北京航空航天大學(xué)學(xué)報(bào). 2015(03)
[4]回歸測試數(shù)據(jù)進(jìn)化生成[J]. 鞏敦衛(wèi),任麗娜.  計(jì)算機(jī)學(xué)報(bào). 2014(03)
[5]基于搜索空間自動(dòng)縮減的路徑覆蓋測試數(shù)據(jù)進(jìn)化生成[J]. 張巖,鞏敦衛(wèi).  電子學(xué)報(bào). 2012(05)
[6]基于擴(kuò)展有限狀態(tài)機(jī)測試中測試輸入數(shù)據(jù)自動(dòng)選取的研究[J]. 張涌,錢樂秋,王淵峰.  計(jì)算機(jī)學(xué)報(bào). 2003(10)



本文編號(hào)：3226874