基于狀態(tài)空間剪枝的軟件測(cè)試數(shù)據(jù)擴(kuò)增算法

張 昇，劉春寶

(吉林大學(xué)，吉林長(zhǎng)春 130041)

1 引言

為了保證軟件質(zhì)量通過(guò)軟件測(cè)試保證軟件正確性，軟件測(cè)試核心是制定優(yōu)質(zhì)測(cè)試計(jì)劃得到測(cè)試用例[1-3]。評(píng)定軟件質(zhì)量的有效方式為實(shí)施全面的軟件測(cè)試，可找出軟件內(nèi)的錯(cuò)誤，降低開發(fā)的錯(cuò)誤風(fēng)險(xiǎn)[4，5]。在軟件測(cè)試的過(guò)程中，測(cè)試者為了驗(yàn)證新版軟件中是否存在新的錯(cuò)誤[6]，需重新測(cè)試新版軟件[7]。為了實(shí)現(xiàn)對(duì)軟件原有數(shù)據(jù)擴(kuò)增需覆蓋軟件的新增與修改內(nèi)容。軟件系統(tǒng)具有的并發(fā)特性，存在大量的測(cè)試數(shù)據(jù)影響軟件模型的狀態(tài)空間及軟件的測(cè)試效率[8]，軟件測(cè)試數(shù)據(jù)擴(kuò)增算法可提高軟件測(cè)試效率。

但是以往軟件測(cè)試數(shù)據(jù)擴(kuò)增算法非常局限，如吳詩(shī)輝等，研究基于神經(jīng)網(wǎng)絡(luò)的仿真優(yōu)化算法[9]，在軟件測(cè)試數(shù)據(jù)擴(kuò)增過(guò)程中，由于該算法訓(xùn)練過(guò)于復(fù)雜，導(dǎo)致軟件測(cè)試數(shù)據(jù)擴(kuò)增效果不佳；劉靜等，基于分布式壓縮感知的聯(lián)合檢測(cè)與跟蹤算法[10]，在軟件測(cè)試數(shù)據(jù)擴(kuò)增中，由于該算法在計(jì)算時(shí)間長(zhǎng)導(dǎo)致后期軟件測(cè)試數(shù)據(jù)，因此本文研究基于狀態(tài)空間剪枝的軟件測(cè)試數(shù)據(jù)擴(kuò)增算法。

2 基于狀態(tài)空間剪枝的軟件測(cè)試數(shù)據(jù)擴(kuò)增算法

2.1 SCPN模型實(shí)例實(shí)施并發(fā)無(wú)關(guān)行為段的分類

軟件系統(tǒng)采用著色Petri網(wǎng)(Colored Petri Net，CPN)實(shí)施控制流模型明確及初始標(biāo)識(shí)。面對(duì)分段行為的CPN(Segmentation Behavior of CPN，SCPN)，SCPN模型是測(cè)試序列生成方法的模型基礎(chǔ)，是對(duì)CPN擴(kuò)展。

SCPN=(P，T，A，Σ，V，C，G，E，I)表示1個(gè)SCPN模型包括1九元組，有限的變遷(Transition)集合、位置(Place)集合分別用T、P描述；A表示有向弧(Arc)集合且A滿足條件A?P×T∪T×P；變量(Variable)集合用V描述，對(duì)任意變量v∈V，滿足Type[v]∈∑；初始化函數(shù)(Initialization function)用I描述，定義位置原始數(shù)據(jù)；1個(gè)非空顏色集(Color set)用Σ描述，主要作用是CPN定義數(shù)據(jù)類型；防衛(wèi)表函數(shù)(Guard function)用G描述，用于表示每個(gè)變遷方位表達(dá)式；顏色集函數(shù)(Color function)用C描述，主要作用是定義位置內(nèi)的數(shù)據(jù)類型；弧表達(dá)函數(shù)(Arc expression function)用E描述，用于表示弧表達(dá)式。

變遷集合T包括：

待測(cè)行為變遷集合(Tested Behavior Transition)，用TT描述，STT表示待測(cè)行為段(Segmentation of Tested Behavior Transition)包括TT內(nèi)1組連續(xù)的相關(guān)弧和變遷位置，1個(gè)待測(cè)行為段用STT{T1，T2，…，Tn}描述。其內(nèi)T1，T2，…，Tn∈STT。相關(guān)行為變遷集合(Related Behavior Transition)用TR描述，STR表示相關(guān)行為段(Segmentation of Related Behavior Transition)包括TR內(nèi)1組連續(xù)的相關(guān)弧和位置，1個(gè)相關(guān)行為段用STR{T1，T2，…，Tn}描述，其內(nèi)T1，T2，…，Tn∈STR。TU表示并發(fā)無(wú)關(guān)行為變遷集合(Unrelated Behavior Transition)；STU表示并發(fā)無(wú)關(guān)行為段(Segmentation of Unrelated Behavior Transition)包括TU內(nèi)1組連續(xù)的相關(guān)弧和變遷位置，1個(gè)并發(fā)無(wú)關(guān)行為段用STU{T1，T2，…，Tn}描述，其內(nèi)T1，T2，…，Tn∈STU。

非并發(fā)無(wú)關(guān)行為變遷集合用TN描述，STN表示非并發(fā)無(wú)關(guān)行為段(Segmentation of Non-concurrent Unrelated Behavior Transition)包括Tn中一組連續(xù)的相關(guān)弧和變遷位置定1個(gè)非并發(fā)無(wú)關(guān)行為段用STN{T1，T2，…，Tn}描述，其內(nèi)T1，T2，…，Tn∈STN。變遷集合T滿足：T=TT∪TR∪TU∪TN。SCPN模型實(shí)例，見圖1。

圖1 SCPN模型實(shí)例

圖1描述1個(gè)3路并發(fā)的SCPN模型，數(shù)據(jù)相關(guān)行為變遷用TE描述，待測(cè)行為用TC、TG描述，并發(fā)無(wú)關(guān)行為TA、TB、TD、TF、TH確定按照模型中是否與待測(cè)、相關(guān)行為具有并發(fā)關(guān)系。

SCPN模型實(shí)例的并發(fā)無(wú)關(guān)行為段的分類，用圖2描述。因?yàn)椴l(fā)無(wú)關(guān)行為段操作復(fù)雜，測(cè)試過(guò)程中，依照位置關(guān)系進(jìn)行分類處理[11，12]，依據(jù)分類結(jié)果實(shí)施不同規(guī)則的剪枝操作。在軟件測(cè)試內(nèi)的一條分支上，如果在所有待測(cè)行為段后有并發(fā)無(wú)關(guān)行為段；純無(wú)關(guān)行為段(Pure STU，PSTU)在軟件測(cè)試內(nèi)并發(fā)無(wú)關(guān)行為段占據(jù)1整條分支的行為片段；前無(wú)關(guān)行為段(Before STU，BSTU)；中無(wú)關(guān)變遷集合(Middle Transition，MT)表示MT中一個(gè)變遷元素；中無(wú)關(guān)行為段(Middle STU，MSTU)。

圖2 并發(fā)無(wú)關(guān)行為段的分類

在圖2內(nèi)，STT{TG}表示對(duì)于待測(cè)行為段，存在前無(wú)關(guān)行為段BSTU{TA，TB}、后無(wú)關(guān)行為段(AfterSTU，ASTU)，后無(wú)關(guān)行為段ASTU{TD}、PSTU{TH}。STT{TC}表示對(duì)于待測(cè)行為段，存在中無(wú)關(guān)行為段用MSTU{TF}描述、純無(wú)關(guān)行為段用PSTU{TH}描述。

2.2 狀態(tài)空間剪枝的軟件測(cè)試序列生成算法

通過(guò)狀態(tài)節(jié)點(diǎn)的剪枝算法，處理并發(fā)無(wú)關(guān)行為段分類后待測(cè)行為段的狀態(tài)集。輸入系統(tǒng)模型、待測(cè)或相關(guān)行為段的匹配初、末狀態(tài)集，判斷無(wú)關(guān)行為段類型，依據(jù)類型不同，分別實(shí)施特定狀態(tài)節(jié)點(diǎn)剪枝操作，縮減狀態(tài)空間的規(guī)模，得到末狀態(tài)集、匹配初。

采用狀態(tài)空間剪枝的測(cè)試序列生成算法獲取軟件測(cè)試數(shù)據(jù)，該算法流程，如圖3描述。

圖3 測(cè)試序列生成算法

由圖3可知：將系統(tǒng)模型及其狀態(tài)空間作為輸入數(shù)據(jù)，采用狀態(tài)節(jié)點(diǎn)投影對(duì)所有待測(cè)行為段實(shí)施操作；對(duì)無(wú)關(guān)行為段類型實(shí)施判斷，如果有中無(wú)關(guān)行為段，實(shí)施變遷弧剪枝操作；如果存在無(wú)關(guān)行為段，獲取可達(dá)子圖，變遷弧剪枝操作；若在內(nèi)側(cè)行為段，去重可達(dá)子圖，依據(jù)狀態(tài)空間，操作全序列測(cè)試。

2.3 數(shù)據(jù)序列擴(kuò)增算法

依據(jù)上小節(jié)獲取的軟件該測(cè)試序列，采用自適應(yīng)粒子群優(yōu)化算法，實(shí)現(xiàn)軟件測(cè)試數(shù)據(jù)擴(kuò)增。

2.3.1 初始種群選擇

為了降低測(cè)試序列數(shù)據(jù)生成個(gè)數(shù)，使用初始種群實(shí)施序列數(shù)據(jù)擴(kuò)增。

在新版本程序P′輸入用t1，t2，…，tm表示2.1小節(jié)獲取的測(cè)試序列數(shù)據(jù)集，生成的執(zhí)行路徑用p′(t1)，p′(t2)，…，p′(tm)描述。程序P′的路徑p′i和p′j穿越的節(jié)點(diǎn)序列分別用n′i1，n′i2，…，n′i|p′i|、n′j1，n′j2，…，n′j|p′j|描述，路徑相似度計(jì)算，用式(1)描述

S(p′i，p′j)=Nsame/|p′j|

(1)

其內(nèi)：路徑p′i相對(duì)于p′j的路徑相似度用S(p′i，p′j)描述；路徑p′i和p′j穿越的相同節(jié)點(diǎn)個(gè)數(shù)用Nsame描述，且Nsame/|p′i∪p′j|。

(2)

2.3.2 自適應(yīng)粒子群算法

自適應(yīng)粒子群算法為了實(shí)現(xiàn)粒子的位置x接近目前問(wèn)題的最優(yōu)解x*僅需研究x的直接變化，進(jìn)化公式，如式(3)所示：

(3)

慣性權(quán)重決定算法的精度與收斂速度。若慣性權(quán)重較低時(shí)，對(duì)算法局部搜索非常有利；若慣性權(quán)重較高時(shí)，對(duì)算法全局搜索非常有利。

通過(guò)調(diào)整慣性權(quán)重，優(yōu)化粒子群算法，粒子聚集度φ計(jì)算，用式(4)描述

φ=|fg-f′avg|

(4)

其內(nèi)：種群粒子的平均適應(yīng)值用favg描述；采用種群內(nèi)適應(yīng)值大于favg粒子適應(yīng)值再次平均計(jì)算出f′avg；種群的全局最優(yōu)解用f描述。

自適應(yīng)調(diào)整方法包括

1)當(dāng)f(xi)>f′avg時(shí)，表示xi逼近最優(yōu)解，慣性權(quán)重越小，慣性權(quán)重具體計(jì)算，如式(5)描述

(5)

2)當(dāng)favg≤f(xi)≤f′avg時(shí)，表示粒子的狀況很普通，慣性權(quán)重隨迭代次數(shù)的增加而增大，在求解時(shí)非線性減少，用式(6)余弦定理表示：

(6)

其內(nèi)：最大進(jìn)化代數(shù)、當(dāng)前進(jìn)化代數(shù)分別用T、t描述。

3)當(dāng)f(xi)

(7)

其內(nèi)，常數(shù)用d描述。

(8)

2.3.3 用自適應(yīng)粒子群優(yōu)化算法流程

基于粒子群優(yōu)化算法的數(shù)據(jù)集擴(kuò)增算法具體流程如下：

例如：為了輸出生成覆蓋新版本程序P′的測(cè)試序列數(shù)據(jù)采用輸入原程序P的測(cè)試序列數(shù)據(jù)集T。

step 1：相似度矩陣是通過(guò)式(2)求得，設(shè)置初始參數(shù)、初始種群。

step 2：判斷終止條件符合程度，判斷擴(kuò)增數(shù)據(jù)覆蓋P′目標(biāo)路徑最大化。如果符合，轉(zhuǎn)到step 6。

step 3：測(cè)試序列數(shù)據(jù)的適應(yīng)值按照適應(yīng)度函數(shù)調(diào)整全局最優(yōu)pgd、個(gè)體最優(yōu)值pid，并通過(guò)式(5)～式(7)設(shè)置慣性權(quán)重。

step 4：通過(guò)式(8)，為了獲取目標(biāo)路徑的不同子Pdif與穿越路徑路徑，確定輸入分量ti1，ti2，…，tin，采用Step 1選取測(cè)試序列數(shù)據(jù)作為輸入。

step 5：依據(jù)step 3獲取的參數(shù)導(dǎo)入式(3)，更新輸入變量ti1，ti2，…，tin生成新的測(cè)試序列數(shù)據(jù)后，轉(zhuǎn)到step2。

step 6：輸出覆蓋P′的測(cè)試序列數(shù)據(jù)集。

3 仿真研究

仿真測(cè)試程序?yàn)槲鏖T子工業(yè)程序集中的程序Tcas、三角形判定程序Triangle、基準(zhǔn)程序Next Day，在實(shí)驗(yàn)中，全部程序在jdkl.7.0-25環(huán)境下運(yùn)行。為驗(yàn)證本文算法的有效性，實(shí)驗(yàn)對(duì)比方法選用本文算法與文獻(xiàn)[9]基于神經(jīng)網(wǎng)絡(luò)的仿真優(yōu)化算法、文獻(xiàn)[10]基于分布式壓縮感知的聯(lián)合檢測(cè)與跟蹤算法實(shí)施軟件測(cè)試數(shù)據(jù)擴(kuò)增效率及算法性能仿真分析，基本參數(shù)設(shè)定包括慣性權(quán)重wmax=1.8、wmin=0.4，進(jìn)化最大代數(shù)T=1000，學(xué)習(xí)因子a1=a2=2。測(cè)試程序信息用表l描述。

表1 測(cè)試程序信息

3.1 軟件測(cè)試數(shù)據(jù)擴(kuò)增效率分析

采用本文算法與神經(jīng)網(wǎng)絡(luò)算法、分布式壓縮感知算法，運(yùn)行測(cè)試程序20次，生成目標(biāo)路徑測(cè)試數(shù)據(jù)，對(duì)不同指標(biāo)進(jìn)行記錄，實(shí)驗(yàn)結(jié)果用表2描述。

由表2數(shù)據(jù)可知：對(duì)比三種算法在不同基準(zhǔn)程序的擴(kuò)增效率，本文算法比神經(jīng)網(wǎng)絡(luò)算法、分布式壓縮感知算法，測(cè)試數(shù)據(jù)擴(kuò)增效率平均分別提高了約57%和82%。本文算法均差小，運(yùn)行時(shí)間最短，平均運(yùn)行時(shí)間0.51s。因此，本文算法軟件測(cè)試數(shù)據(jù)效率高。

3.2 算法性能分析

選取西門子工業(yè)程序集中的Tcas程序，三種算法在迭代過(guò)程中對(duì)目標(biāo)路徑的覆蓋率，用圖4描述。

圖4 目標(biāo)路徑覆蓋率

通過(guò)圖4數(shù)據(jù)表明：本文算法比神經(jīng)網(wǎng)絡(luò)算法、分布式壓縮感知算法相比，在覆蓋目標(biāo)路徑方面具有較大的優(yōu)勢(shì)，

本文算法在進(jìn)化代數(shù)400時(shí)，目標(biāo)路徑覆蓋率達(dá)到1.0，并在后期的目標(biāo)路徑覆蓋率保持平穩(wěn)，而神經(jīng)網(wǎng)絡(luò)算法、分布式壓縮感知算法目標(biāo)路徑覆蓋率低，后期的目標(biāo)路徑覆蓋率有波動(dòng)。

4 結(jié)論

為了提高軟件測(cè)試的效率，研究基于狀態(tài)空間剪枝的軟件測(cè)試數(shù)據(jù)擴(kuò)增算法。軟件測(cè)試時(shí)按照并發(fā)無(wú)關(guān)行為段在軟件測(cè)試內(nèi)的位置實(shí)施分類，依據(jù)分類結(jié)果實(shí)施不同規(guī)則的剪枝操作，生成測(cè)試序列，采用自適應(yīng)粒子群優(yōu)化算法實(shí)施軟件測(cè)試序列數(shù)據(jù)集擴(kuò)增。通過(guò)仿真結(jié)果表明，本文算法在生成覆蓋目標(biāo)路徑測(cè)試數(shù)據(jù)的效率高，實(shí)現(xiàn)軟件測(cè)試數(shù)據(jù)擴(kuò)增。由于本人時(shí)間與精力有限，仍有許多不足之處，以后將研究重點(diǎn)放在實(shí)際的軟件測(cè)評(píng)的過(guò)程中，采用更先進(jìn)的算法與科學(xué)技術(shù)，優(yōu)化軟件測(cè)試數(shù)據(jù)擴(kuò)增算法的實(shí)際應(yīng)用效果。