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

張 昇，劉春寶

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

1 引言

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

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

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

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

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

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

變遷集合T包括：

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

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

圖1 SCPN模型實例

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

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

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

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

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

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

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

圖3 測試序列生成算法

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

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

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

2.3.1 初始種群選擇

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

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

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

(1)

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

(2)

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

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

(3)

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

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

φ=|fg-f′avg|

(4)

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

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

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

(5)

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

(6)

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

3)當f(xi)

(7)

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

(8)

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

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

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

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

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

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

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

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

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

3 仿真研究

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

表1 測試程序信息

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

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

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

3.2 算法性能分析

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

圖4 目標路徑覆蓋率

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

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

4 結(jié)論

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