嵌入式軟件路徑覆蓋測試用例生成仿真

陳金萍,趙成喜

(大連海洋大學應用技術(shù)學院,遼寧 大連 116300)

1 引言

現(xiàn)階段,嵌入式系統(tǒng)飛速發(fā)展,已涉及國防、醫(yī)療、商業(yè)等多個行業(yè)。例如常用的移動終端、機頂盒等均為嵌入式技術(shù)的產(chǎn)物。隨著該系統(tǒng)的深入應用,軟件規(guī)模與復雜程度也不斷增加。軟件設計過程中,難以做到十全十美,一方面,由于開發(fā)人員疏忽或技術(shù)問題,導致軟件達不到理想要求;再加上嵌入式系統(tǒng)自身空間有限,還附加上高可靠性等要求,加大了軟件缺陷檢測的難度,使其成為系統(tǒng)中的定時炸彈,對系統(tǒng)安全帶來嚴重威脅。例如,因軟件故障造成火箭發(fā)射失敗,歐洲不得不推遲航天計劃;由于機票系統(tǒng)出現(xiàn)軟件程序錯誤,美國造成百萬美元經(jīng)濟損失。因此,對軟件進行測試、及時修正缺陷,保證系統(tǒng)運行穩(wěn)定十分必要。

惠子青[1]等人構(gòu)建了動態(tài)加權(quán)神經(jīng)網(wǎng)絡模型測試軟件。綜合分析軟件多樣性特征,使用神經(jīng)網(wǎng)絡建立加權(quán)組合模型;根據(jù)故障發(fā)生過程進行軟件缺陷預測。除此之外,還有學者通過建立高階Markov模型生成軟件測試用例。針對馬爾科夫模型測試用例生成不穩(wěn)定的缺陷,進行改進,利用快速輪盤賭的二分查找方法生成測試用例。

上述兩種測試方案是在目標機上進行的,因軟件運行過程中具有不可視性,測試人員不能實時掌握代碼覆蓋情況,隨機性較強。此外,測試用例生成會占用系統(tǒng)CPU利用率,對系統(tǒng)運行造成負擔。為此,本文提出嵌入式軟件路徑覆蓋測試用例生成算法。路徑覆蓋表示設置多個測試用例,將程序中全部可行路徑都覆蓋。該方法是評估軟件性能的重要手段,但是程序中若出現(xiàn)多個循環(huán),路徑數(shù)據(jù)會大幅度增加。因此,本文首先對軟件中污點數(shù)據(jù)進行檢測,避免覆蓋不可行路徑,再引入遺傳算法使路徑覆蓋得到簡化,經(jīng)過遺傳變異操作輸出最終測試用例。

2 污點數(shù)據(jù)檢測

分析待測試軟件的過程中,要著重注意程序中的數(shù)據(jù)計算和傳遞,解決任意節(jié)點中可能存在的污點數(shù)據(jù)[2,3]。這些數(shù)據(jù)有可能是惡意添加或是隨機生成的,如果不刪除,會生成太多無用路徑,影響測試效率。

1)軟件數(shù)據(jù)分類

內(nèi)部數(shù)據(jù):是軟件自身存在的,與軟件結(jié)構(gòu)有關,在軟件測試過程中,通常不將這些數(shù)據(jù)當作惡意數(shù)據(jù)。即便這些數(shù)據(jù)存在一定缺陷,通過修復后,不會對測試造成影響。

外部數(shù)據(jù):此種數(shù)據(jù)一般會改變軟件執(zhí)行路徑,存在很強的不穩(wěn)定性,對這些數(shù)據(jù)分析具有一定難度,污點數(shù)據(jù)通常會存在其中。

2)污點數(shù)據(jù)確定

污點數(shù)據(jù)具有威脅的原因是它能以信息流的方式進行傳播,當軟件定義某變量a為污點數(shù)據(jù)時,存在a中的信息,經(jīng)過賦值等操作將數(shù)值傳遞給變量b,此種情況就是信息流傳播[4],是導致程序崩潰的主要原因。污點數(shù)據(jù)傳播示意圖如圖1所示。

圖1 污點數(shù)據(jù)傳播示意圖

由于數(shù)據(jù)來源不同,污點數(shù)據(jù)被分為下述兩種:

網(wǎng)絡數(shù)據(jù):因網(wǎng)絡結(jié)構(gòu)復雜,某些惡意攻擊者通過發(fā)送不良數(shù)據(jù)對主機進行攻擊[5],導致污點數(shù)據(jù)生成;

I/O數(shù)據(jù):此種數(shù)據(jù)包含鍵盤數(shù)據(jù)輸入以及文件讀取生成的數(shù)據(jù)。

信息流傳播過程中,具體傳播方式可通過下述公式描述

(1)

公式中,b和c代表污點數(shù)據(jù),經(jīng)過傳播a和d也變?yōu)槲埸c數(shù)據(jù)。

3)流向分析

分析污點數(shù)據(jù)流向即可找出不可行的覆蓋路徑,進而加快模型求解速度。具體分析過程如下:

第一步:設置兩個變量,包括污點數(shù)據(jù)和可信數(shù)據(jù);

第二步:將污點數(shù)據(jù)通過文件取讀方式傳遞給a,此時a變?yōu)槲埸c數(shù)據(jù);

步驟三:如果傳遞數(shù)據(jù)為可信,則返回值同樣可信;

步驟四:若使用污點數(shù)據(jù),則危險函數(shù)[6]被調(diào)用,此時污點數(shù)據(jù)會控制函數(shù)的具體執(zhí)行情況。

通過以上分析,將可能存在污點數(shù)據(jù)的路徑篩選出來,作為不可行路徑,減少路徑冗余。

3 基于路徑覆蓋的軟件測試用例生成

要想高效生成測試用例,需要對目標路徑分組,使所有個體均被有效使用。路徑相似度的高低能夠反映出測試數(shù)據(jù)的利用效率,所以結(jié)合路徑相似度完成路徑分組,將具有高度相似性的歸為同一組。完成分組后,可將任意一組用例生成問題轉(zhuǎn)換為初始問題的子問題,再通過遺傳算法求解,獲取子種群最優(yōu)解。在進化期間,當已知某路徑的測試數(shù)據(jù),儲存此信息與路徑的同時刪除被覆蓋路徑,這樣會降低CPU利用率[7]。

3.1 分組策略

假設Pi與Pj代表兩個目標路徑,其中i,j=1,2,…,n,且Pi的節(jié)點表示為ni1,ni2,…,nirj,Pj的節(jié)點則是nj1,nj2,…,njrj。將nj1當作起點進行對比,直至找出首個Pi與Pj不一致的節(jié)點njk,此時Pi與Pj存在的相同節(jié)點數(shù)量是same(Pi,Pj)=k-1。反之,若Pi與Pj全部節(jié)點均相同,則同類節(jié)點數(shù)量描述為same(Pi,Pj)=ri=rj。Pi與Pj存在的相似度s(Pi,Pj)表達式為

(2)

由此可知,s(Pi,Pj)∈[0,1],該值越大,同類節(jié)點數(shù)量越多。假設閾值設置為s0∈(0,1),從眾多目標路徑中選取一條路徑Pi,獲取該路徑與其它路徑之間的相似度,如果高于或等于s0,則將符合該要求的路徑放在一組,記作{g1};再從路徑集合中去除{g1},針對剩余路徑,通過上述方式獲得{g2}。反復以上操作,直至全部路徑均被劃分在某組中。

3.2 路徑覆蓋測試用例生成數(shù)據(jù)模型構(gòu)建

因{gi}中隨機兩個路徑的相似度不能低于s0,因此,?需符合s(Pi1,P(?))≥s0,則第i個優(yōu)化子問題表示為

(3)

因此可以得出,在第i個優(yōu)化問題中包括的目標函數(shù)數(shù)量少于整體優(yōu)化問題,計算起來更為方便。此外,由于相同子問題的目標路徑相似度較高,所以可通過一個子種群完成優(yōu)化,縮小可行域,使搜索范圍變小,提高測試效率。

根據(jù)上述分析結(jié)果,可將路徑覆蓋測試用例生成問題變換為多個具有較少目標的子問題,構(gòu)建的數(shù)據(jù)模型如下

(4)

此模型一共包括I個子問題,任意一個子問題均包括多個優(yōu)化問題。利用該模型即可將全部路徑覆蓋問題,變換成I個子問題進行求解,這樣可以降低求解難度。

3.3 基于遺傳算法的模型求解

對于上述路徑覆蓋測試用例生成模型,本文利用遺傳算法對變換成I個的子問題求解。具體過程如下。

1)確定編碼方式

通過遺傳算法對模型求解時,需對個體進行編碼[8],此處個體指程序輸入。若程序輸入是整數(shù),則利用二進制編碼,若為實數(shù),則使用實數(shù)編碼方式。

2)適應值構(gòu)建

已知?ij的適應值,則子問題中包括ni個目標函數(shù),能夠得出ni個目標函數(shù)在個體?ij處的函數(shù)值fi1(?ij),fi2(?ij),…,fini(?ij)。

若?ij可對{gi}中某條路徑覆蓋,則?ij即為需要的測試用例。即只要存在某個k,確保fik(?ij)=0,則

min{fi1(?ij),fi2(?ij),…,fini(?ij)}=fik(?ij)=0

(5)

可通過min{fi1(?ij),fi2(?ij),…,fini(?ij)}判定?ij是否符合{gi}的覆蓋需求。

另外,針對第i個問題還存在一個約束條件是s(Pi1,P(?ij))≥s0,通過懲罰函數(shù)[9]對該約束條件進行處理。針對個體?ij,若符合此條件,說明?ij為可行解,反之不可行,必須對其懲罰。s(Pi1,P(?ij))與s0之間的差距越大,表明越不能滿足約束條件,應加大懲罰力度。因此,建立懲罰函數(shù)α(s0-s(Pi1,P(?ij))),α表示某正數(shù),本文取值為0.2。

經(jīng)過上述分析,個體?ij具有的適應值公式如下

fiti(?ij)=min{fi1(?ij),fi2(?ij),…,fini(?ij)}

+αmax{max(s0-s(Pi1,P(?ij)),0)}

(6)

利用上述公式完成對?ij的評價,得出的fiti(?ij)值越小,表明?ij覆蓋某路徑的可能性越高,將其代入到下一代種群內(nèi)繼續(xù)操作。

3)終止條件確定

針對任意一個優(yōu)化問題,終止條件均包括兩種:第一種是此問題含有的目標函數(shù)數(shù)量等于零,此時優(yōu)化完成,獲取覆蓋組中全部路徑的測試用例;第二種則是算法進化到設置的代數(shù),這時即使沒有完成任務,也會停止操作。

路徑覆蓋測試用例生成的整個過程為:

步驟一:設計參數(shù)與個體編碼,確定交叉與變異概率;

步驟二:將目標路徑劃分為不同小組,對某組{gi}生成個體種群M(Pi),并將其當作輸入矢量;

步驟三:適應值獲取,計算所有個體的適應值,該值越小,與最優(yōu)解越接近,被選入下一輪的幾率越高;

步驟四:設置終止條件,如果終止轉(zhuǎn)到步驟六;

步驟五:如果不符合終止要求,在相同種群內(nèi)進行遺傳操作,主要包含交叉、變異等[10],并轉(zhuǎn)回步驟三;

步驟六:輸出最終結(jié)果,即為測試用例生成結(jié)果。

4 仿真數(shù)據(jù)分析與研究

本次仿真選取了較為典型的電話程序、三角形分類程序以及某銀行業(yè)務程序,三種系統(tǒng)軟件作為測試目標。將從用例生成數(shù)量、充分性判定、用例生成時間以及CPU利用率多個方面對所提算法性能進行仿真分析。

實驗一:電話機系統(tǒng)

1)用例生成數(shù)量分析

以電話機待機狀態(tài)作為初始測試狀態(tài),經(jīng)過各類操作直到掛機為止,停止測試。在此期間本文方法、動態(tài)加權(quán)神經(jīng)網(wǎng)絡、高階馬爾科夫模型三種算法生成的測試用例數(shù)量如圖2所示。

圖2 不同方法測試用例生成數(shù)量

由圖2可知,動態(tài)加權(quán)神經(jīng)網(wǎng)絡與高階馬爾科夫模型算法生成的用例數(shù)量多、波動較大,表明生成過程隨機,可控性較差,會生成太多無用用例。所提方法生成數(shù)量相對較少,整個測試過程表現(xiàn)得較為穩(wěn)定,可避免用例冗余。這是因為該方法在用例生成前對程序中的污點數(shù)據(jù)進行分析,刪除不可覆蓋的路徑,提高測試效率。

2)充分性分析

在軟件測試中,停止時間尤為重要,也就是對測試充分性的判定。為衡量測試是否充分,需找出一個平衡點來阻止測試過程。Discriminant值一般指2個事件似然率期望值,通過計算該值即可獲取事件之間的相似度,表示為D′(U′,T′),U′與T′分別代表軟件使用模型與測試模型。該值與零越接近,代表兩模型越逼近,如果該值低于設定閾值時,則認為測試充分,可停止,其計算公式如下

(7)

式中,x1,x2,…,xn代表測試序列。三種算法的Discriminant值計算結(jié)果如圖3所示。

圖3 不同算法Discriminant比較

分析圖3得出,在多次實驗中本文方法的Discriminant值較為平穩(wěn),且始終接近或等于0。表明測試停止時間剛好,充分性較強,能夠更好地應用在軟件測試中,避免早熟現(xiàn)象。

實驗二:三角形分類程序

對于分類程序不同的數(shù)據(jù)區(qū)間,將獲取所有可行路徑當作結(jié)束條件。實驗過程中,實時記錄每次尋找路徑的進化代數(shù),求取平均值。三種方法仿真結(jié)果如表1所示。

表1 不同方法平均迭代次數(shù)表

由表1得出,隨著輸入信息區(qū)間的擴大,對于三種行分類問題,三種算法找出目標路徑的平均進化代數(shù)也隨著增加。這是由于數(shù)據(jù)量較大,搜索難度加大導致的。但本文方法的平均進化代數(shù)小,說明該方法總是能以較快速度完成三角形分類測試。數(shù)據(jù)量越大這種優(yōu)勢越明顯。證明了基于遺傳算法路徑覆蓋的軟件測試用例生成效率高,可快速實現(xiàn)目標測試。

3)銀行業(yè)務程序

由于銀行業(yè)務系統(tǒng)在線人數(shù)較多,共包含20個分行,每個分行下還有多個網(wǎng)點,業(yè)務量大,基本上每天都會產(chǎn)生業(yè)務處理峰值。因此必須對該系統(tǒng)的軟件功能進行測試,確保每筆業(yè)務都能順利操作。針對該系統(tǒng)而言,軟件的CPU利用率最為關鍵,實驗利用上述三種方法對其CPU利用率進行測試,測試結(jié)果如圖4所示。

圖4 不同方法測試CPU利用情況

通過分析圖4可知,利用三種方法對銀行業(yè)務軟件的CPU利用率進行測試,由于測試環(huán)境相同,軟件自身CPU利用率保持不變。本文方法測試出的CPU利用率最低,這是因為該方法在測試過程中占用系統(tǒng)內(nèi)存較少,而其它兩種方法內(nèi)存占用率很高。當銀行業(yè)務出現(xiàn)峰值時,會影響系統(tǒng)正常運行,因此其它兩種方法不適合在業(yè)務辦理高峰時段進行測試,容易造成系統(tǒng)崩潰。

5 結(jié)論

軟件測試在系統(tǒng)開發(fā)過程中發(fā)揮著重要作用,通過測試可及時發(fā)現(xiàn)軟件錯誤,提高可信度?；诖?本文提出一種嵌入式軟件路徑覆蓋測試用例生成算法。通過對污點數(shù)據(jù)的檢測,排除不可行路徑,再利用遺傳算法建立路徑覆蓋的數(shù)學模型,經(jīng)過模型求解,輸出測試用例。實驗證明,該方法提高測試效率,不占用系統(tǒng)內(nèi)存,具有較強的可控性。但本文利用遺傳算法求解效果還有待提高,遺傳策略與參數(shù)設置問題還需進一步優(yōu)化。