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

在審

• 申請(qǐng)?zhí)枺?/td>: 202010906633.4
• 申請(qǐng)日: 2020-09-01
• 公開（公告）號(hào): CN111984542A
• 公開（公告）日: 2020-11-24
• 發(fā)明（設(shè)計(jì)）人: 勾善義
• 申請(qǐng)（專利權(quán)）人: 勾善義
• 主分類號(hào): G06F11/36
• 分類號(hào): G06F11/36
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于貪婪算法和搜索算法的混合算法的組合測(cè)試用例生成算法，其主要步驟如下：

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

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

步驟3)、當(dāng)覆蓋標(biāo)準(zhǔn)達(dá)到K后，貪婪算法遇到瓶頸，選擇搜索算法代替，如圖3，以期達(dá)到更優(yōu)的效果。

進(jìn)一步的，所述步驟1)的具體步驟如下：

步驟1.0)、首先是構(gòu)建數(shù)組，構(gòu)建覆蓋數(shù)組的總體目標(biāo)是創(chuàng)建一個(gè)二維數(shù)組，其中所有與指定輸入關(guān)聯(lián)的t元組都會(huì)被覆蓋。

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

進(jìn)一步的，所述步驟2)的具體步驟如下：

步驟2.1)、通過使用貪婪算法，將每個(gè)因子與某個(gè)級(jí)別的值綁定在一起，可以為該集合一次建立一行。一旦所有t元組都被覆蓋，覆蓋數(shù)組就完成了。本發(fā)明可以動(dòng)態(tài)設(shè)置參數(shù)K，當(dāng)覆蓋率達(dá)到K時(shí)，將貪婪算法轉(zhuǎn)換為搜索算法，避免陷入局部最優(yōu)。

步驟2.2)、手動(dòng)選擇第一個(gè)測(cè)試用例T，或者自動(dòng)選擇T，T的選擇會(huì)影響后續(xù)測(cè)試用例的生成。

步驟2.3)、根據(jù)步驟2.2)選中的測(cè)試用例T，選擇測(cè)試用例T’，選擇標(biāo)準(zhǔn)是轉(zhuǎn)換成本最低，如果同時(shí)存在多個(gè)T’，則選擇其中一個(gè)。在此階段，覆蓋率逐漸上升。

進(jìn)一步的，所述步驟3)的具體步驟如下：

步驟3.1)、用戶可以根據(jù)自己的實(shí)際需求，設(shè)置一個(gè)覆蓋標(biāo)準(zhǔn)值K。如果標(biāo)準(zhǔn)值K設(shè)置得過高，則有可能在貪婪算法陷入局部最優(yōu)時(shí)仍未達(dá)到K，會(huì)影響性能。

步驟3.2)、當(dāng)覆蓋率到達(dá)K時(shí)，本發(fā)明將選擇搜索算法繼續(xù)生成測(cè)試用例。

步驟3.4)、假定S為SUT應(yīng)涵蓋的所有未覆蓋2值組合的集合，Tg為生成的測(cè)試用例的集合。對(duì)于每個(gè)測(cè)試候選t，t(2-way)表示t覆蓋的S中的所有2-way值組合。則有：

Fitness(t)＝|t(2-way)∩S|

其中Fitness用來衡量每個(gè)候選者的質(zhì)量。以此來選擇候選者。因?yàn)檫@是搜索算法的一般方法，因此對(duì)于其他強(qiáng)度的組合也適用。

步驟3.5)、當(dāng)步驟3.4)中S為空時(shí)，CA完全覆蓋，流程結(jié)束。