[發(fā)明專利]一種基于改進(jìn)的灰色預(yù)測演化算法的測試用例生成方法

有效

• 申請?zhí)枺?/td>: 202110586812.9
• 申請日: 2021-05-27
• 公開（公告）號: CN113468044B
• 公開（公告）日: 2022-06-24
• 發(fā)明（設(shè)計(jì)）人: 蘇清華;蔡高成;吳海濤;楊先山;李麗萍
• 申請（專利權(quán)）人: 長江大學(xué)
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 武漢藍(lán)寶石專利代理事務(wù)所(特殊普通合伙) 42242
• 代理人: 嚴(yán)超

本發(fā)明提供一種基于改進(jìn)的灰色預(yù)測演化算法的測試用例生成方法，包括以下步驟：S1，對被測程序進(jìn)行靜態(tài)分析，得到被測程序的目標(biāo)路徑集和靜態(tài)結(jié)構(gòu)信息；S2，基于目標(biāo)路徑集和靜態(tài)結(jié)構(gòu)信息，執(zhí)行GPE?ISS算法產(chǎn)生新的測試用例集；S3，將新的測試用例集驅(qū)動被測程序運(yùn)行；S4，記錄并使用運(yùn)行結(jié)果更新路徑覆蓋信息；S5，計(jì)算測試用例的適應(yīng)度函數(shù)值，選取最有潛力的測試用例進(jìn)行下一輪的迭代；S6，重復(fù)執(zhí)行S2?S5，直到滿足算法的終止條件。本發(fā)明的方法可以用較少的測試用例來獲得了最高的路徑覆蓋率，提高面向路徑覆蓋的測試用例生成的效率，從而可以降低測試成本。

技術(shù)領(lǐng)域

本發(fā)明涉及軟件測試技術(shù)領(lǐng)域，更具體地，涉及一種基于改進(jìn)的灰色預(yù)測演化算法的測試用例生成方法。

背景技術(shù)

隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，以發(fā)現(xiàn)軟件錯誤為目的的軟件測試在軟件行業(yè)中變得越來越重要。與此同時，軟件的復(fù)雜性也在不斷增加，從而導(dǎo)致了更高的測試成本。為了降低測試成本，越來越多的行業(yè)關(guān)注自動化軟件測試(AST)。AST的主要任務(wù)是自動化生成滿足某個覆蓋準(zhǔn)則的測試用例。據(jù)許多已有的文獻(xiàn)報(bào)道，分支覆蓋、語句覆蓋和其他覆蓋問題可以轉(zhuǎn)化為路徑覆蓋問題。路徑覆蓋問題要求被測程序中的所有可能路徑至少被遍歷一次。由于被測程序的高度非線性結(jié)構(gòu)，使得自動化生成有效的面向路徑覆蓋的測試用例變得困難。如何設(shè)計(jì)一種有效的技術(shù)來解決面向路徑覆蓋的測試用例生成(ATCG-PC)問題已成為軟件工程界研究的熱點(diǎn)。

到目前為止，解決ATCG-PC的先進(jìn)技術(shù)主要包括隨機(jī)測試、符號執(zhí)行和基于搜索的測試，每種技術(shù)都有其優(yōu)缺點(diǎn)。在隨機(jī)測試中，測試用例是在被測程序的整個輸入域內(nèi)隨機(jī)抽樣生成的。隨機(jī)測試具有易于實(shí)現(xiàn)，運(yùn)行速度快等優(yōu)點(diǎn)，但一般受路徑覆蓋率低的影響。符號執(zhí)行使用符號值而不是實(shí)際數(shù)據(jù)作為測試程序的輸入，它通過求解相關(guān)約束來生成測試用例。這個優(yōu)點(diǎn)表明它可以用來檢查被測程序中的特定路徑的行為，但是在面對數(shù)組、調(diào)用、指針引用和無限循環(huán)時，它是具有挑戰(zhàn)性的。基于搜索的測試將ATCG-PC問題轉(zhuǎn)化為一個優(yōu)化問題，并用基于搜索的算法對它進(jìn)行求解。這些算法不依賴于梯度信息，可以自動檢索出有效的測試用例。正因?yàn)槿绱耍谒阉鞯乃惴ㄒ殉蔀榻鉀QATCG-PC的發(fā)展趨勢。用于求解ATCG-PC的算法可分為以下類別。

第一類是原始的基于搜索的算法，例如，爬山算法(HC)，模擬退火(SA)，禁忌搜索(TS)，交替變量法(AVM)，遺傳算法(GA)，粒子群優(yōu)化(PSO)，人工蜂群(ABC)，差分演化(DE)，蟻群優(yōu)化(ACO)，負(fù)選擇算法(NSA)，布谷鳥搜索(CS)，等等。

第二類是改進(jìn)的基于搜索的算法，例如，基于自適應(yīng)隨機(jī)測試的增廣蟻群算法(ACO-ART)，基于分散搜索策略的差分演化(DE-SS)，基于分散搜索策略的競爭群優(yōu)化器(CSO-SS)，基于關(guān)系矩陣的差分演化(RP-DE)，基于變質(zhì)關(guān)系的粒子群優(yōu)化(PSO-MR)，基于個體分享的多種群遺傳算法(MGA-IS)，基于符號執(zhí)行的遺傳算法(GA-SE)，基于反饋的遺傳算法(FD-GA)，實(shí)數(shù)編碼的遺傳算法(RCGA)，基于聚類思想的粒子群優(yōu)化算法(PSO-CT)，群活動反饋的高斯粒子群算法(SAF-GPSO)，蜂王進(jìn)化遺傳算法(QBEGA)，等等。

第三類是兩個原始的基于搜索的算法的混合，例如，CS和TS(CS-TS)，GA與HC(GA-HC)，SA和CS(SA-CS)，混合的GA和TS(HGTS)，遺傳的群優(yōu)化算法(GSO)，CS和蜂群算法(CS-BCA)，NSA和GA(NSA-GA)，CS和蝙蝠算法(CS-BA)，CS和GA(CS-GA)，飛蛾火焰優(yōu)化和螢火蟲算法(MFO-FA)，等等。

基于搜索的算法的通用性促進(jìn)了上述算法在ATCG-PC中的應(yīng)用，但大多數(shù)算法都沒有充分利用ATCG-PC的啟發(fā)式信息。當(dāng)被測試程序中存在一些字符串變量時，即被測試程序的路徑只能被一些字符串變量覆蓋時，要覆蓋這些路徑就比較困難。如果用ATCG-PC的啟發(fā)式信息去改進(jìn)原始的基于搜索的算法，則可能會提高求解ATCG-PC的效率。問題是什么樣的啟發(fā)式信息用于改進(jìn)基于搜索的算法來解決ATCG-PC是有效的。