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

在審

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

本發明公布了一種基于搜索域縮減的軟件測試用例進化生成方法，目的是動態確定輸入變量與變異體的相關性，移除不相關輸入變量相當于縮減搜索域，并采用遺傳算法高效生成變異測試用例；該方法，首先建立變異測試用例生成優化模型，設計適應值函數，再基于適應值變化動態確定變異體與輸入變量的相關性；然后，改進變異測試用例生成優化模型，決策變量為相關輸入變量，建立基于相關輸入變量的變異測試用例生成優化模型；最后，針對新模型，在相關輸入變量形成的搜索域內，采用遺傳算法高效生成測試用例。

技術領域

本發明涉及計算機軟件測試領域，具體是一種基于搜索域縮減的軟件測試用例進化生成方法。

背景技術

軟件測試是保障軟件質量一個重要的手段。軟件測試的代價比較大，主要來自于設計好的測試用例和檢查它們的輸出的人工成本。因此，很多技術被設計提高軟件測試的效率。變異測試已經被證明是軟件測試的一種強有力的技術。變異測試包括通過引入簡單的語法變化和創建可能的錯誤版本(稱為變異體)來修改程序。某一測試用例執行原程序和變異體后，考察輸出或狀態是否變化。一個變異體被一個測試用例殺死，使變異體和原程序產生不同的輸出，那么測試用例被認為是有效的，說明它能夠發現程序的缺陷。然而找到殺死數量龐大的變異體，測試成本很高，很多工具被開發，用于自動生成變異體。但又存在一些問題，比如每個變異體都是重復執行，針對至少一個或者很多的測試用例。許多研究試圖減少沒有意義的變異體，或者提高殺死變異體的效率。

Papadakis等人在2011年《Software Quality Journal》第19期發表的文章“Automatically performing weak mutation with the aid of symbolic execution,concolic testing and search-based testing”一文提出一種新的軟件測試方法。他們基于弱變異測試準則，將殺死變異體問題轉化為變異條件語句真分支的覆蓋問題。為此，對于變異前后的語句s和s'，基于弱變異測試的必要條件，構建變異條件語句“if s！＝s'”，其真分支為一個標志語句，簡稱變異分支；然后，把這些變異分支插入到原程序的變異前的語句s前面，這樣便形成了新的被測程序。那么，能夠覆蓋新程序變異分支的測試用例，一定能夠基于弱變異測試準則，殺死該變異分支對應的變異體。這樣做的好處是，能夠利用已有的傳統結構測試的測試用例生成方法，生成變異測試用例。

研究發現，如果能夠縮減搜索域，在尋找殺死變異體測試用例時，將大大提高測試的效率。如果能夠移除與變異體無關的輸入變量，采用遺傳算法生成測試用例時，進化個體只需要在相關輸入變量所形成的域內搜索，將大大提高找到測試用例的速度。然而，尋找變異體與輸入變量之間的相關性很難。考慮到，基于搜索的進化算法，已經廣泛的應用于變異測試中，尤其是用于高效生成殺死變異體的測試用例。

發明內容

為了解決現有技術中軟件測試生成測試用例效率低下的問題，本發明提供了一種基于搜索域縮減的軟件測試用例進化生成方法，通過動態分析適應值變化與輸入變量相關性，快速得到變異體與輸入變量的相關性，然后選擇相關輸入變量作為決策變量，相當于縮減了搜索域，采用遺傳算法高效生成變異測試用例。

本發明采用的技術方案：一種基于搜索域縮減的軟件測試用例進化生成方法，設被測程序為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：構建傳統變異測試用例生成的優化模型；