[發明專利]一種基于貪婪算法和搜索算法的混合算法的組合測試用例生成算法

在審

• 申請號: 202010906633.4
• 申請日: 2020-09-01
• 公開（公告）號: CN111984542A
• 公開（公告）日: 2020-11-24
• 發明（設計）人: 勾善義
• 申請（專利權）人: 勾善義
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明公開了一種基于混合的組合測試用例生成算法，包括以下步驟：1)生成滿足要求的覆蓋數組，后續的操作以覆蓋這個數組為判別標準。2)在覆蓋率較低的情況下，根據貪婪算法特性，使用貪婪算法來生成測試用例。3)在覆蓋率達到比例K后，貪婪算法遇到瓶頸，選擇搜索算法替代，以期達到更優的效果。本發明的基于混合算法的組合測試用例生成算法，即保證了貪婪算法生成測試用例前期的高效，又能避免后期陷入局部最優的情況，為從業人員在做測試用例生成方向的工作時，提供一個可以思考的角度。

技術領域

本發明提出了一種基于混合算法的組合測試用例生成算法，屬于軟件測試中組合測試的領域。利用混合技術，根據覆蓋率指標對生成技術及時切換，以更高效地生成測試用例。本發明有效地彌補了單一生成算法的缺陷，在高維的情況下更能體現其優勢。

背景技術

軟件測試是軟件開發生命周期中不可或缺的一個重要環節。如果要保證一個軟件系統的質量，需要對它進行詳盡的測試。然而，在現實生活中，一個軟件系統的參數可能有很多，這會導致完全測試的測試用例數量達到成千上萬個，因此組合測試用例生成算法應運而生。

貪婪算法試圖在每次迭代中找到當前的最佳選擇，以達到滿意的解決方法。在確定給定測試集的優先集時，確定一個測試用例作為源測試用例，然后迭代選擇后續的測試用例。但是貪婪算法很容易陷入局部最優解。

搜索算法：許多搜索技術已經開發并成功應用于許多領域，包括基于搜索的軟件工程(SBSE)領域。作為組合測試的關鍵問題，覆蓋數組的生成已經得到了廣泛的研究，并且已經應用了許多搜索技術，這些技術可以稱為基于搜索的組合測試(SBCT)。SBCT是SBSE中基于搜索的軟件測試(SBST)的一個分支。

本文提出基于貪婪算法和搜索算法的混合算法，用來生成組合測試用例，并給出測試用例生成工具。

發明內容

發明目的：為了解決傳統的貪婪算法在生成測試用例時會陷入局部最優的情況，本文提出了一種基于貪婪算法和搜索算法的測試用例生成算法，通過設置覆蓋率要求，在未達到設置的覆蓋率之前采用貪婪算法，當達到覆蓋率要求后，采用搜索算法生成測試用例。

技術方案：為了實現上述目的，本發明采用的技術方案為：

基于貪婪算法和搜索算法的測試用例生成算法，包括以下步驟：

步驟1)、生成滿足要求的覆蓋數組。

步驟2)、首先選擇貪婪算法，如圖2，根據貪婪算法特性逐步覆蓋數組。

步驟3)、當覆蓋標準達到K后，貪婪算法遇到瓶頸，選擇搜索算法代替，如圖3，以期達到更優的效果。

進一步的，所述步驟1)的具體步驟如下：

步驟1.0)、首先是構建數組，構建覆蓋數組的總體目標是創建一個二維數組，其中所有與指定輸入關聯的t元組都會被覆蓋。

步驟1.1)、組合測試使用覆蓋表CA作為測試用例集，CA是一個大小為M×k維的矩陣。本發明中，測試用例條數，即覆蓋表的大小標記為N；覆蓋強度標記為t；待測系統參數個數為其中，取值個數為v_i的參數有k_i(1≤i≤m，m≤k)個，v_i(1≤i≤k)表示第i個參數取值集合，|v_i|表示第i個參數取值個數。則CA表有如下表示：

進一步的，所述步驟2)的具體步驟如下：

步驟2.1)、通過使用貪婪算法，將每個因子與某個級別的值綁定在一起，可以為該集合一次建立一行。一旦所有t元組都被覆蓋，覆蓋數組就完成了。本發明可以動態設置參數K，當覆蓋率達到K時，將貪婪算法轉換為搜索算法，避免陷入局部最優。