陳金萍,趙成喜

(大連海洋大學(xué)應(yīng)用技術(shù)學(xué)院,遼寧 大連 116300)

1 引言

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

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

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

2 污點(diǎn)數(shù)據(jù)檢測(cè)

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

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

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

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

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

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

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

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

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

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

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

(1)

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

3)流向分析

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

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

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

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

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

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

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

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

3.1 分組策略

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

(2)

由此可知,s(Pi,Pj)∈[0,1],該值越大,同類(lèi)節(jié)點(diǎn)數(shù)量越多。假設(shè)閾值設(shè)置為s0∈(0,1),從眾多目標(biāo)路徑中選取一條路徑Pi,獲取該路徑與其它路徑之間的相似度,如果高于或等于s0,則將符合該要求的路徑放在一組,記作{g1};再?gòu)穆窂郊现腥コ齵g1},針對(duì)剩余路徑,通過(guò)上述方式獲得{g2}。反復(fù)以上操作,直至全部路徑均被劃分在某組中。

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

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

(3)

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

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

(4)

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

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

對(duì)于上述路徑覆蓋測(cè)試用例生成模型,本文利用遺傳算法對(duì)變換成I個(gè)的子問(wèn)題求解。具體過(guò)程如下。

1)確定編碼方式

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

2)適應(yīng)值構(gòu)建

已知?ij的適應(yīng)值,則子問(wèn)題中包括ni個(gè)目標(biāo)函數(shù),能夠得出ni個(gè)目標(biāo)函數(shù)在個(gè)體?ij處的函數(shù)值fi1(?ij),fi2(?ij),…,fini(?ij)。

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

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

(5)

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

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

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

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

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

(6)

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

3)終止條件確定

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

路徑覆蓋測(cè)試用例生成的整個(gè)過(guò)程為:

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

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

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

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

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

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

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

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

實(shí)驗(yàn)一:電話(huà)機(jī)系統(tǒng)

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

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

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

由圖2可知,動(dòng)態(tài)加權(quán)神經(jīng)網(wǎng)絡(luò)與高階馬爾科夫模型算法生成的用例數(shù)量多、波動(dòng)較大,表明生成過(guò)程隨機(jī),可控性較差,會(huì)生成太多無(wú)用用例。所提方法生成數(shù)量相對(duì)較少,整個(gè)測(cè)試過(guò)程表現(xiàn)得較為穩(wěn)定,可避免用例冗余。這是因?yàn)樵摲椒ㄔ谟美汕皩?duì)程序中的污點(diǎn)數(shù)據(jù)進(jìn)行分析,刪除不可覆蓋的路徑,提高測(cè)試效率。

2)充分性分析

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

(7)

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

圖3 不同算法Discriminant比較

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

實(shí)驗(yàn)二:三角形分類(lèi)程序

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

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

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

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

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

圖4 不同方法測(cè)試CPU利用情況

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

5 結(jié)論

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