[發明專利]一種基于搜索域縮減的軟件測試用例進化生成方法

在審

• 申請號: 202110051667.4
• 申請日: 2021-01-14
• 公開（公告）號: CN112732582A
• 公開（公告）日: 2021-04-30
• 發明（設計）人: 黨向盈;鞏敦衛;姚香娟;鮑蓉;姜代紅;阮少偉;厲丹;陳磊;李子龍;包季楠;袁偲朕
• 申請（專利權）人: 徐州工程學院
• 主分類號: G06F11/36
• 分類號: G06F11/36;G06N3/12
• 代理公司: 徐州市三聯專利事務所 32220
• 代理人: 陳帥

1.一種基于搜索域縮減的軟件測試用例進化生成方法，設被測程序為G，對其包含的語句實施變異，得到變異體集合為M＝{M₁,M₂,…,M_n}，n是變異體的個數；將這些變異體轉化的變異分支插入到G中，得到新的被測程序G'；設程序的輸入向量為X＝(x₁,x₂,…,x_m)，m是程序輸入變量的個數；輸入域D(X)是每個輸入變量域的叉乘,即D(X)＝D(x₁)×D(x₂)×…×D(x_m)；其特征在于，該方法包括以下步驟：

S1：動態確定變異體與輸入變量之間的相關性；

S1.1：構建傳統變異測試用例生成的優化模型；

S1.2：基于適應值確定變異體與輸入變量之間的相關性；

S2：構建基于相關輸入變量的變異測試用例生成優化模型；

S3：基于遺傳算法生成變異測試用例。

2.根據權利要求1所述的一種基于搜索域縮減的軟件測試用例進化生成方法，其特征在于：步驟S1.1中構建傳統變異測試用例生成的優化模型的方法為：

記f_i(X)為目標函數，反映程序的輸入向量X基于弱變異測試準則，是否殺死變異體M_i，當M_i被殺死，f_i(X)＝0，否則，f_i(X)＝1；M_i被殺死當且僅當f_i(X)取最小值0；因此生成殺死M_i測試用例問題可以轉化為求解f_i(X)最小值問題，記為：

min f_i(X)

f_i(X)只取0和1兩個值，很難指導種群的進化；為給種群進化提供更多的信息，在模型中增加一個約束函數g_i(X)；

X覆蓋M_i的前提是，必須可達原語句s，因此定義X是否覆蓋s為約束函數g_i(X)；覆蓋s的分支距離，設為dist_i(X)；那么，dist_i(X)＝0時當且僅當X能夠覆蓋s，分支距離的值可以任意大，將其進行歸一化處理；令

由上式可知，0≤g_i(X)1，且g_i(X)＝0當且僅當dist_i(X)＝0，即，如果X能夠覆蓋s，那么，g_i(X)取值為0；

那么，殺死M_i的測試用例生成問題的數學模型為：

min(f_i(X))

采用基于遺傳算法求解上式最優解時，程序的輸入向量為遺傳算法的決策變量，記為X＝(x₁,x₂,…,x_m)，那么，適應值函數定義為，

fit_i(X)＝f_i(X)×(g_i(X)+d)

其中，d是一個很小的常數，它的作用確保括號中的值大于0；由上式可知，進化個體性能越好，fit_i(X)越小；當fit_i(X)＝0時，種群找到了最優解X。