[發明專利]一種軟件測試用例有序生成方法

有效

• 申請號: 202110051697.5
• 申請日: 2021-01-14
• 公開（公告）號: CN112699054B
• 公開（公告）日: 2022-02-18
• 發明（設計）人: 黨向盈;阮少偉;徐瑋瑋;鮑蓉;申珅;厲丹
• 申請（專利權）人: 徐州工程學院
• 主分類號: G06F11/36
• 分類號: G06F11/36;G06N3/12
• 代理公司: 徐州市三聯專利事務所 32220
• 代理人: 陳帥

1.一種軟件測試用例有序生成方法，其特征在于包括以下步驟：

S1：排序變異體；

S2：構建測試用例生成數學模型；

S3：基于遺傳算法有序生成測試用例；

其中，所述的步驟S1中排序變異體的方法為：

設某一測試程序為G，程序的輸入為X，s為G中某一原語句，對其實施變異之后，得到變異語句s'；滿足變異測試的必要條件“s！＝s'”，其中“！＝”為不等于符號，即是滿足弱變異測試準則，那么條件語句“if s！＝s'”和它的真分支，基于弱變異測試準則稱為變異分支，它對應的變異體記為M_i；一個變異體對應一個變異分支；按照同樣的方法，得到所有變異體的集合，記為M＝{M₁,M₂,…,M_n}，n為變異體的個數；將這些變異分支插入G中對應原語句前面，形成的新被測程序，記為G'；X運行G'，如果“if s！＝s'”的真分支被執行，那么，基于弱變異準則M_i被殺死；

為了反映X殺死變異體M_i情況，定義一個隨機變量μ_i(X)，

為了計算μ_i(X)，采用數理統計的方法；首先，需要得到一個測試用例集，為此，在程序G輸入域內隨機生成R個樣本，記為X₁,X₂,...,X_R；將X_k,k＝1,2,…,R執行程序，考察在弱變異測試準則下它是否能殺死M_i，然后計算μ_i(X_k)的值；

假設變異體M_i,M_j,i,j＝1,2,...,n,i≠j是兩個不同的變異體，定義兩個隨機變量μ_i(X_k)和μ_j(X_k)，它們分別反映M_i,M_j被殺死的可能性；當M_i被殺死的情況下，M_j被殺死的情況，表示為，當μ_i(X_k)＝1時，μ_j(X_k)＝1的概率：

M_i和M_j之間的殺死相關度，記為α_i,j，由上式表示為:

由上式可知，α_i,j∈[0,1]；對于所有變異體M₁,M₂,…,M_n之間的殺死相關度，建立變異體殺死相關矩陣Λ，記為：

M₁ M₂ M_j M_n

設與M_i相關的變異體的個數記為η_i；閾值記為T；M_i對應的組記為P_i；

基于Λ，變異體排序的步驟如下：

A1：η_i＝0,i＝1,2,...,n；

A2：考察Λ中M_i,i＝1,2,...,n對應的行，M_i與每一個M_j,M_j∈M,j＝1,2,...,n,M_j≠M_i的α_i,j值，如果α_i,j≥T，η_i＝η_i+1，并將M_j放入M_i組內即P_i＝P_i∪M_j；

A3：基于η₁,η₂,…,η_n降序排列M₁,M₂,…,M_n；輸出排序后的變異體，記為M’₁,M’₂,…,M’_n；

A4：輸出排序后的變異體集合M'＝{M’₁,M’₂,…,M’_n}，M’_i對應的組為其中ρ_i為組內變異體數目；

所述的步驟S2中構建測試用例生成數據模型的方法為：

對于M’_i，設目標函數為f_i(X)，其中X為決策變量，即為程序的輸入；當X能殺死M’_i，f_i(X)＝0；否則f_i(X)＝1；因此，當且僅當f_i(X)取最小值0時，M’_i被X殺死；通過這種方式，殺死M’_i的問題轉化為求f_i(X)最小值問題，表示為：

minf_i(X)

然而，由上式可知f_i(X)的取值只有0和1兩種，為了提供更多的信息指導種群進化，需要增加一個約束函數；

在殺死M_i'之前，測試用例必須先覆蓋變異語句s′；因此，基于分支覆蓋的約束函數，表示為:

g_i(X)＝Appr(s′,X)+(1-1.001^{-dist(s′,X)})

其中Appr(s′,X)是X對于s′的層接近度，dist(s',X)為分支距離；由上式可知，當且僅當時g_i(X)＝0時，X能覆蓋s′；

根據X，f_i(X)和g_i(X)，建立殺死M_i'的數學模型為：

min f_i(X)

所述的步驟S3中基于遺傳算法有序生成測試用例的方法為：

基于強變異準則，采用遺傳算法生成測試用例；為了引導種群進化，需要計算進化個體的適應值；對于M’_i，考慮到數學模型中包括一個目標函數和一個約束函數，適應值函數fit_i(X)，表示為：

其中，是很小的正整數，它的作用確保括號里的值大于0；由上式可知，當且僅當fit_i(X)＝0時，X能殺死了M’_i；

在遺傳算法中，進化個體為X₁ X₂,…,X_Size，其中Size為子種群中進化個體的數目；算法的輸出為生成的測試用例集；終止條件有兩個，一個是殺死所有變異體的測試用例找到；另一個是種群進化到最大進化代數_g；

生成測試用例的步驟：

B1:設變量i＝1；

B2:如果或者M_i'被殺死，那么，i＝i+1；

B3:初始化種群和算法中的各種參數；設變量count＝1；

B4:X₁ X₂,…,X_Size執行M’_i；判定終止條件是否滿足，如果滿足，轉B11；

B5:判斷X₁ X₂,…,X_Size是否殺死M’_i，如果是，移除M’_i，并保存殺死它的測試用例，轉B6；否則，轉B8；

B6:X₁ X₂,…,X_Size繼續執行P’_i中其它變異體；判斷這些變異體是否都被殺死，如果是，

B7:將P_i’中被殺死的變異體，從P’_j≠P_i’,j＝1,2,…,n中移除；如果P’_j中所有變異體都被殺死，那么i＝i+1；轉B2；

B8:計算所有個體的適應值；

B9:實施選擇、交叉和變異操作；生成新進化個體，不引起混淆，仍記為X₁ X₂,…,X_Size；

B10:count＝count+1；轉B4；

B11:輸出測試用例集。