周燕彬

（湖南財經(jīng)工業(yè)職業(yè)技術(shù)學(xué)院 湖南省衡陽市 421001）

從互聯(lián)網(wǎng)剛開始出現(xiàn)，一直到現(xiàn)在，都是以飛速蓬勃的姿態(tài)在發(fā)展著。無論是電腦，還是手機(jī)等電子設(shè)備，都離不開軟件的支持，它已應(yīng)用到社會發(fā)展、人類生活、城市建設(shè)等各個領(lǐng)域。由于軟件應(yīng)用廣泛，軟件的質(zhì)量也必須要得到保證。

總體上講，軟件測試是一個需要不斷重復(fù)的工作，在條件不成熟時，軟件測試大多數(shù)還是依靠人工，人工設(shè)計測試用例，然后手動執(zhí)行這些測試用例，這樣就會導(dǎo)致耗費大量的人力和物力，而且人并不能時時刻刻都高度集中精神，所以稍有疏忽就容易出現(xiàn)不必要的錯誤，沒法保證百分之百的正確率。一旦軟件的規(guī)模不在手工的承受范圍之內(nèi)，它所需要的開銷也變得異常昂貴，也是沒辦法被接受的。因此，自動化軟件測試被提出并成為一種傾向。其中，測試用例的自動生成是一個非常重要的部分，一個典型的測試用例生成方法是先創(chuàng)建一個軟件的測試模型，然后基于這個模型來自動生成測試用例[1]。而經(jīng)常用到的模型有有限狀態(tài)機(jī)（FSM）和擴(kuò)展有限狀態(tài)機(jī)（EFSM），相對于有限狀態(tài)機(jī)，后者增加了遷移、謂詞條件和遷移被觸發(fā)后的操作，因而更能準(zhǔn)確地描述軟件系統(tǒng)的動態(tài)行為。

盡管在基于EFSM 模型的測試用例生成上前人已經(jīng)做了很多研究工作，但是實現(xiàn)有效的測試還存在一些挑戰(zhàn)。由于一些不可行路徑的轉(zhuǎn)換之間的相關(guān)性，以及檢測不可行路徑的問題一般是不可判定的[1]，因此，基于FSM 的測試生成方法不能直接用于基于EFSM 的測試。

1 EFSM模型

EFSM（Enhanced Finite State Machine），即擴(kuò)展有限狀態(tài)機(jī)。是在有限狀態(tài)機(jī)（FSM）的基礎(chǔ)上添加了上下文變量、謂詞和操作，而有限狀態(tài)機(jī)本質(zhì)上是一個傳感器，它是由狀態(tài)、輸入、輸出組成的有限集合，其中輸出和狀態(tài)遷移、輸入相關(guān)。一個EFSM 是由許多狀態(tài)和狀態(tài)之間的轉(zhuǎn)換共同構(gòu)成的。

EFSM 模型可用一個六元組（S，S0，V，I，O，T）來表示，其中：

（1）S 是邏輯狀態(tài)集；

（2）S0∈S，是初始狀態(tài)；

（3）V 是內(nèi)部變量和環(huán)境變量有限集；

（4）I 是輸入操作有限集；

（5）O 是輸出操作有限集；

（6）T 是有限狀態(tài)遷移集。

在EFSM 中，當(dāng)機(jī)器的一個轉(zhuǎn)換被采用時，就會發(fā)生狀態(tài)轉(zhuǎn)換。如果初始狀態(tài)為source，且接收到輸入input 并滿足保護(hù)guard，則T 中每個遷移元素t 又可以表示為一個五元組＜source(t),input(t),guard(t),operation(t)，end(t)＞，簡化為＜ss,i,g,op,se＞，其中：

（1）source(t)是遷移t 的初始狀態(tài)；

（2）input(t)∈I 為遷移t 上的激勵事件，由若干個輸入變量組成或者為空；

（3）guard(t)是稱為保護(hù)的邏輯表達(dá)式，有的也稱作守衛(wèi)；

（4）operation(t)∈O 是遷移t 引起的操作，是由諸如輸出語句和賦值語句之類的簡單語句組成的順序操作；

（5）end(t)是其結(jié)束狀態(tài)。

當(dāng)EFSM 處于某個遷移t 的初始狀態(tài)source(t),接收到輸入input(t)且遷移的保護(hù)條件guard(t)為true 時，就會執(zhí)行該遷移的operation(t)操作，并將狀態(tài)由初始狀態(tài)source(t)轉(zhuǎn)換到結(jié)束狀態(tài)end(t)。

在過去幾年中，基于EFSM 的測試用例生成有比較大的發(fā)展，這促使我對近年來自動化測試的現(xiàn)狀以及基于EFSM 的測試用例生成技術(shù)進(jìn)行了系統(tǒng)的調(diào)查。

到目前為止，各種搜索算法已經(jīng)成功運(yùn)用在EFSM 模型的測試用例自動生成上，文獻(xiàn)[2]提出了利用禁忌搜索算法來對EFSM 模型生成測試數(shù)據(jù)，文中分析了測試數(shù)據(jù)的生成時間與路徑之間的不同影響因素的相關(guān)性，從而得到影響生成效率的主要因素，作者還通過與遺傳算法進(jìn)行對比，驗證了該算法的可行性。

文獻(xiàn)[3]提出了將模擬退火算法的思想應(yīng)用于EFSM 模型的測試用例生成中，分別對算法中的參數(shù)選取不同的值，來分析不同的參數(shù)設(shè)置對測試數(shù)據(jù)生成效率的影響，并對傳統(tǒng)的模擬退火算法進(jìn)行了改進(jìn)，進(jìn)一步提高了測試數(shù)據(jù)的生成效率。

2 遺傳算法和模擬退火算法的優(yōu)缺點

優(yōu)化算法在自動化測試方面已經(jīng)被證明是有效的[4]，把優(yōu)化搜索的原理運(yùn)用到測試數(shù)據(jù)的生成中，就是把測試數(shù)據(jù)的生成問題轉(zhuǎn)化為搜索和優(yōu)化問題。

2.1 遺傳算法

遺傳算法實際上是一個優(yōu)化搜索問題，首先從一個種群開始，按照適者生存和優(yōu)勝劣汰的法則來尋找存活下來的個體，在不斷的進(jìn)化中，通過存活下來的優(yōu)秀個體的繁衍，會產(chǎn)生出越來越好的一個種群。在每一代，通過判斷適應(yīng)度的好壞，從而挑選一部分優(yōu)秀個體復(fù)制到下一代，即選擇操作，另外還能對基因進(jìn)行交叉以及變異操作，從而產(chǎn)生新種群。這個過程就像自然界中的進(jìn)化過程一樣，新得到的子代種群會比父代更適應(yīng)環(huán)境，而整個進(jìn)化過程中得到的最優(yōu)個體就是問題的最終解。

遺傳算法使用適應(yīng)度值來進(jìn)行評價，而且根據(jù)適應(yīng)度值來進(jìn)行一定的隨機(jī)搜索，不一定能保證找到最優(yōu)解，另外該算法在收斂于最優(yōu)解的速度上可能會比較慢。

2.2 模擬退火算法

模擬退火算法是用固體退火的方式來模擬組合優(yōu)化問題，其原理簡要概括為：首先給固體升溫，至溫度夠高，則內(nèi)能越大，其內(nèi)部的粒子則會進(jìn)行快速的無規(guī)則運(yùn)動，給固體降溫時，則內(nèi)能減小，粒子的運(yùn)動速度降低，慢慢排列有序，最終固體處于常溫時，則此時內(nèi)能最小，粒子最穩(wěn)定。用內(nèi)能E 模擬為目標(biāo)函數(shù)值f，用溫度T 模擬成控制參數(shù)t，用來解決組合優(yōu)化問題。

模擬退火算法雖然具有跳出局部最優(yōu)解的能力，能夠以隨機(jī)搜索的方式從概率的意義上找出目標(biāo)函數(shù)f 的全局最小點。但是，由于該算法對整個搜索空間的狀況不了解，不能立即使搜索過程進(jìn)入到最有希望的搜索區(qū)域，因此它的運(yùn)算效率并不高，另外該算法對參數(shù)（如初始溫度）的依賴性較強(qiáng)，且進(jìn)化速度慢。

同樣作為元啟發(fā)式搜索算法，粒子群算法在尋找最優(yōu)解方面存在一定的優(yōu)勢，因此嘗試基于粒子群算法生成EFSM 模型的測試用例。

表1 ：公式1、2 中各個參數(shù)及其含義

表2：生成的可執(zhí)行路徑

表3：ATM 模型上生成的部分測試數(shù)據(jù)

3 基于粒子群算法的EFSM模型的測試用例自動生成

3.1 粒子群算法的原理

粒子群算法（Particle Swarm Optimization，以下稱PSO），是受到鳥類捕食的行為特征啟發(fā)而得到的，有一群鳥在空中覓食，它們不知道食物在哪，但是它們知道自己距離食物有多遠(yuǎn)，它們只能慢慢去尋找，那么食物就是整個問題的最優(yōu)解，而每一只去捕食的鳥就是在空間中進(jìn)行搜索的一個個粒子。

在PSO 中，將需要被優(yōu)化的問題的解看成是一個個粒子，每一個粒子都具有以下屬性：位置X，速度V，它本身經(jīng)歷的最好的位置pbest，它在全局中所經(jīng)歷的最好位置gbest 和它本身的適應(yīng)度值。每個粒子都包含著一個適應(yīng)度值，它的作用是表示粒子的優(yōu)劣程度，若適應(yīng)度值越小，則表明粒子的位置更優(yōu)，若適應(yīng)度值越大，則表明粒子的位置更差。

以下公式1,2 表示的是當(dāng)找到最優(yōu)值pbest 和gbest 時，粒子更新自己速度和位置的依據(jù)。

公式中各個參數(shù)代表的含義如表1。

最初的粒子群算法是沒有w 慣性權(quán)重這個參數(shù)的，即w=1，后來經(jīng)過改進(jìn)，加入了慣性權(quán)重，可以取不同的值，成為標(biāo)準(zhǔn)的粒子群算法。從之前的經(jīng)驗來看，如果慣性權(quán)重偏大，算法的全局搜索效果更好，而慣性權(quán)重偏小，則更有利于局部搜索。

公式中使用學(xué)習(xí)因子是為了提高算法的局部求精能力。

3.2 基于粒子群算法的EFSM測試數(shù)據(jù)生成實現(xiàn)流程

對于一個已經(jīng)存在的EFSM 模型，根據(jù)生成的可行測試序列，將其作為指定的輸入，通過粒子群算法，找到滿足各個前置條件的變量的值，從而生成測試用例。下面主要介紹算法的具體實現(xiàn)流程：

（1）隨機(jī)生成一組初始粒子群（包含多個粒子），即初始解來作為當(dāng)前的解。而該初始解是根據(jù)EFSM 模型中存在的一條可執(zhí)行遷移路徑的event 中的輸入變量來生成的。

（2）根據(jù)給出的適應(yīng)度函數(shù)計算出每個粒子的適應(yīng)度值，由此來評價它滿足路徑的執(zhí)行要求與否，如若滿足，則輸出結(jié)果，說明測試用例生成成功，結(jié)束算法。

（3）如果不滿足，則根據(jù)公式1 和公式2 更新粒子的位置和速度，并增加迭代次數(shù)。

（4）對新得到的粒子群重新進(jìn)行適應(yīng)度的評估。

（5）直到滿足執(zhí)行條件或者達(dá)到最大迭代次數(shù)。

3.3 基于粒子群算法的EFSM測試用例生成關(guān)鍵元素設(shè)計

3.3.1 群體規(guī)模

表4：三種算法生成測試用例迭代次數(shù)對比（單位：次）

表5：三種算法生成測試用例迭代時間對比（單位：秒）

不同的粒子群規(guī)模大小不同，而不同的粒子群規(guī)模對于最后的結(jié)果也可能產(chǎn)生不同影響，在設(shè)計可行性證明實驗時，取種群規(guī)模N=100。

3.3.2 最大迭代次數(shù)

最大迭代次數(shù)即粒子群進(jìn)行更新的最大代數(shù)，若是超過了這個數(shù)值還沒有得到最優(yōu)解，則表示實驗失敗。一般來說，都會在最大迭代次數(shù)以內(nèi)產(chǎn)生一個最優(yōu)解。這里設(shè)置Tmax=1000。

3.3.3 最大速度

即粒子在這個空間內(nèi)運(yùn)動時的最大速度Vmax。

3.3.4 權(quán)重因子

包括慣性因子w 和學(xué)習(xí)因子c1,c2。一般選取經(jīng)驗值，w=0.7，c1=c2=2。

3.3.5 適應(yīng)度函數(shù)構(gòu)造

構(gòu)造適應(yīng)度函數(shù)的方法一般有兩種，一是層接近度法，二是分支距離法，本文則采用第二種方法來構(gòu)造適應(yīng)度函數(shù)。對于粒子群優(yōu)化算法，構(gòu)建適應(yīng)度函數(shù)能夠讓其發(fā)揮出它的優(yōu)化能力，從而去解決測試用例生成的問題，本文采用分支距離法來構(gòu)造適應(yīng)度函數(shù)。

3.4 實驗過程及結(jié)果分析

為了驗證本文中的測試序列自動生成方法是否有效，將該方法應(yīng)用于ATM 模型（一個典型的EFSM 模型）的測試序列的自動生成中，為了生成測試序列，也就是可行遷移路徑，而且要使最終得到的測試用例可以滿足全狀態(tài)-遷移覆蓋標(biāo)準(zhǔn)，本文將ATM 模型中的所有遷移當(dāng)做目標(biāo)遷移，來尋找從初始前已出發(fā)，到達(dá)目標(biāo)遷移的較短可行遷移路徑的集合，生成的可執(zhí)行路徑的結(jié)果如表2。

從表2可以看出，ATM 模型最終得到了30 個較短測試序列，覆蓋了EFSM 模型中的所有遷移。如表3所示。

進(jìn)行實驗時，選取ATM 模型，選取路徑長度[4-50]范圍內(nèi)的若干條路徑，為每條路徑各取5 條不同的可執(zhí)行路徑，每條路徑分別應(yīng)用三種算法10 次，表4和表5分別表示用三種算法生成正確的測試數(shù)據(jù)所需要的迭代次數(shù)和平均迭代時間，這里僅僅列出了一部分?jǐn)?shù)據(jù)。通過比較三種算法生成測試用例的平均迭代時間和迭代次數(shù)來判斷粒子群算法是否更高效。

從表4和表5的數(shù)據(jù)可以看出，粒子群算法在測試數(shù)據(jù)生成的迭代次數(shù)少于遺傳算法和模擬退火算法，而且時間上大大減少，提高了生成效率。

4 結(jié)論

本文提出了基于粒子群優(yōu)化算法的EFSM 模型測試用例自動生成的設(shè)計思路，介紹了粒子群算法的原理、生成測試用例的具體的算法流程、參數(shù)設(shè)置等。通過實驗，比較了遺傳算法，模擬退火算法，粒子群優(yōu)化算法在ATM 模型上生成測試用例的平均迭代時間，可以看出粒子群優(yōu)化算法在ATM 模型的測試用例生成上的效率比遺傳算法和模擬退火算法要高。