基于狀態空間剪枝的軟件測試數據擴增算法

張 昇，劉春寶

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

1 引言

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

但是以往軟件測試數據擴增算法非常局限，如吳詩輝等，研究基于神經網絡的仿真優化算法[9]，在軟件測試數據擴增過程中，由于該算法訓練過于復雜，導致軟件測試數據擴增效果不佳；劉靜等，基于分布式壓縮感知的聯合檢測與跟蹤算法[10]，在軟件測試數據擴增中，由于該算法在計算時間長導致后期軟件測試數據，因此本文研究基于狀態空間剪枝的軟件測試數據擴增算法。

2 基于狀態空間剪枝的軟件測試數據擴增算法

2.1 SCPN模型實例實施并發無關行為段的分類

軟件系統采用著色Petri網(Colored Petri Net，CPN)實施控制流模型明確及初始標識。面對分段行為的CPN(Segmentation Behavior of CPN，SCPN)，SCPN模型是測試序列生成方法的模型基礎，是對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]∈∑；初始化函數(Initialization function)用I描述，定義位置原始數據；1個非空顏色集(Color set)用Σ描述，主要作用是CPN定義數據類型；防衛表函數(Guard function)用G描述，用于表示每個變遷方位表達式；顏色集函數(Color function)用C描述，主要作用是定義位置內的數據類型；弧表達函數(Arc expression function)用E描述，用于表示弧表達式。

變遷集合T包括：

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

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

圖1 SCPN模型實例

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

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

圖2 并發無關行為段的分類

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

2.2 狀態空間剪枝的軟件測試序列生成算法

通過狀態節點的剪枝算法，處理并發無關行為段分類后待測行為段的狀態集。輸入系統模型、待測或相關行為段的匹配初、末狀態集，判斷無關行為段類型，依據類型不同，分別實施特定狀態節點剪枝操作，縮減狀態空間的規模，得到末狀態集、匹配初。

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

圖3 測試序列生成算法

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

2.3 數據序列擴增算法

依據上小節獲取的軟件該測試序列，采用自適應粒子群優化算法，實現軟件測試數據擴增。

2.3.1 初始種群選擇

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

在新版本程序P′輸入用t1，t2，…，tm表示2.1小節獲取的測試序列數據集，生成的執行路徑用p′(t1)，p′(t2)，…，p′(tm)描述。程序P′的路徑p′i和p′j穿越的節點序列分別用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)

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

(2)

2.3.2 自適應粒子群算法

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

(3)

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

通過調整慣性權重，優化粒子群算法，粒子聚集度φ計算，用式(4)描述

φ=|fg-f′avg|

(4)

其內：種群粒子的平均適應值用favg描述；采用種群內適應值大于favg粒子適應值再次平均計算出f′avg；種群的全局最優解用f描述。

自適應調整方法包括

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

(5)

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

(6)

其內：最大進化代數、當前進化代數分別用T、t描述。

3)當f(xi)

(7)

其內，常數用d描述。

(8)

2.3.3 用自適應粒子群優化算法流程

基于粒子群優化算法的數據集擴增算法具體流程如下：

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

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

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

step 3：測試序列數據的適應值按照適應度函數調整全局最優pgd、個體最優值pid，并通過式(5)～式(7)設置慣性權重。

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

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

step 6：輸出覆蓋P′的測試序列數據集。

3 仿真研究

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

表1 測試程序信息

3.1 軟件測試數據擴增效率分析

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

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

3.2 算法性能分析

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

圖4 目標路徑覆蓋率

通過圖4數據表明：本文算法比神經網絡算法、分布式壓縮感知算法相比，在覆蓋目標路徑方面具有較大的優勢，

本文算法在進化代數400時，目標路徑覆蓋率達到1.0，并在后期的目標路徑覆蓋率保持平穩，而神經網絡算法、分布式壓縮感知算法目標路徑覆蓋率低，后期的目標路徑覆蓋率有波動。

4 結論

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