国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

基于強(qiáng)化學(xué)習(xí)選擇策略的路徑覆蓋測(cè)試數(shù)據(jù)生成算法

2024-08-15 00:00劉超丁蕊朱雨寒

摘 要:面向路徑覆蓋的測(cè)試是軟件測(cè)試的重要方法之一。如何快速生成高質(zhì)量測(cè)試數(shù)據(jù)使其滿足路徑覆蓋要求,一直是研究熱點(diǎn)問題。為解決現(xiàn)有智能優(yōu)化方法運(yùn)行時(shí)間長、探索過程不穩(wěn)定以及生成測(cè)試用例冗余的問題,提出一種基于強(qiáng)化學(xué)習(xí)思想的選擇策略,用于以路徑覆蓋為準(zhǔn)則的測(cè)試數(shù)據(jù)生成中。通過將可執(zhí)行路徑定義為智能體狀態(tài),算法每一輪迭代更新后的數(shù)據(jù)選擇定義為智能體動(dòng)作,并將獎(jiǎng)勵(lì)函數(shù)與狀態(tài)變化關(guān)聯(lián),在狀態(tài)更新過程中使用貪心策略來引導(dǎo)輸入數(shù)據(jù)不斷向未獲取狀態(tài)變異更新,以此不斷選擇能夠覆蓋新可執(zhí)行路徑的數(shù)據(jù),從而實(shí)現(xiàn)對(duì)待測(cè)程序所有執(zhí)行路徑覆蓋的目標(biāo)。實(shí)驗(yàn)結(jié)果表明,與其他算法相比,所提策略的運(yùn)行時(shí)間和迭代次數(shù)明顯降低,同時(shí)覆蓋率快速提高。結(jié)合理論分析可以得出結(jié)論:所提策略在實(shí)際運(yùn)用中能夠有效實(shí)現(xiàn)路徑覆蓋并提高測(cè)試數(shù)據(jù)生成效率。

關(guān)鍵詞:測(cè)試數(shù)據(jù)生成; 路徑覆蓋; 強(qiáng)化學(xué)習(xí); 選擇策略

中圖分類號(hào):TP311 文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001-3695(2024)08-031-2467-07

doi:10.19734/j.issn.1001-3695.2023.11.0592

Algorithm for path coverage test data generation based onreinforcement learning selection strategy

Liu Chaoa, Ding Ruib, Zhu Yuhana

(a.School of Mathematics & Science, b.School of Computing & Information Technology,Mudanjiang Normal University, Mudanjiang Heilongjiang 157000, China)

Abstract:Path-coverage oriented testing is a crucial method in software testing, and the rapid generation of high-quality test data to satisfy path coverage requirements has been a persistent research challenge. To address issues such as long running times, unstable exploration processes, and the generation of redundant test cases in existing intelligent optimization methods, this paper proposed a selection strategy based on the reinforcement learning paradigm applied to test data generation with path coverage as the criterion. By defining executable paths as the state of the intelligent agent, it defined the data selection after each iteration update as the agent’s action. It associated the reward function with state changes, and employed a greedy strategy during the state update process to guide input data towards continuous variations in unexplored states. This iterative selection process aimed to continuously choose data that covered new executable paths, thereby achieving the goal of covering all execution paths of the target program. Experimental results demonstrate that compared to other algorithms, the proposed strategy significantly reduces running times and iteration counts while achieving notable improvements in coverage. Theoretical ana-lysis supports the conclusion that the proposed strategy effectively realizes path coverage and enhances the efficiency of test data generation in practical applications.

Key words:test data generation; path coverage; reinforcement learning; selection strategy

0 引言

軟件測(cè)試是保障軟件質(zhì)量的重要方法。其對(duì)軟件進(jìn)行大量的測(cè)試,用來發(fā)現(xiàn)軟件中可能存在的缺陷和錯(cuò)誤[1]。當(dāng)下對(duì)軟件行業(yè)的統(tǒng)計(jì)結(jié)果顯示,關(guān)乎軟件測(cè)試的花費(fèi)成本很高,往往能占整個(gè)項(xiàng)目開發(fā)的一半[2]。而軟件測(cè)試的核心在于生成有效的測(cè)試數(shù)據(jù),用來滿足規(guī)定的測(cè)試充分性準(zhǔn)則。因此,如何高效地生成測(cè)試數(shù)據(jù),就具有重要的現(xiàn)實(shí)意義和經(jīng)濟(jì)價(jià)值[3]。

面向覆蓋的測(cè)試數(shù)據(jù)生成方法通過覆蓋待測(cè)軟件的需要滿足測(cè)試要求,是經(jīng)典的測(cè)試數(shù)據(jù)生成方法。路徑覆蓋作為面向覆蓋的最基本充分性準(zhǔn)則之一,其要求選取足夠多的測(cè)試數(shù)據(jù),使待測(cè)程序的每條可達(dá)路徑都至少執(zhí)行一次。可以將問題描述為:對(duì)于給定程序的目標(biāo)路徑,需要在程序的輸入空間里尋找或生成能夠覆蓋目標(biāo)路徑的測(cè)試數(shù)據(jù)[4]。

對(duì)于測(cè)試數(shù)據(jù)生成,傳統(tǒng)優(yōu)化算法方面,Goschen等人[5]利用遺傳規(guī)劃方法來進(jìn)行自動(dòng)化軟件測(cè)試,動(dòng)態(tài)地生成輸入值來探索給定軟件的輸入域,從而實(shí)現(xiàn)更好的路徑覆蓋。Sun等人[6]將分布式代理引導(dǎo)進(jìn)化優(yōu)化與測(cè)試用例生成相結(jié)合,以提高程序中路徑覆蓋測(cè)試的測(cè)試用例生成效率。Zhang等人[7]提出覆蓋引導(dǎo)的模糊測(cè)試生成測(cè)試數(shù)據(jù),以此來檢測(cè)軟件運(yùn)行中的缺陷和故障。Potluri等人[8]提出了一種混合群智能方法,將粒子群、蜜蜂群和螢火蟲、布谷鳥算法結(jié)合,以優(yōu)化測(cè)試覆蓋率,從而高效地生成測(cè)試數(shù)據(jù)。Damia等人[9]提出基于群的遺傳算法,采用全新的適應(yīng)度函數(shù)來更新種群,實(shí)現(xiàn)測(cè)試數(shù)據(jù)的生成。丁蕊等人[10]提出關(guān)鍵點(diǎn)路徑表示法來計(jì)算理論路徑的數(shù)目,從覆蓋難易程度上對(duì)路徑進(jìn)行分類,并使用遺傳算法來生成難覆蓋路徑的測(cè)試數(shù)據(jù)。錢忠勝等人[11]提出一種結(jié)合關(guān)鍵點(diǎn)與路徑相似度的多種群多覆蓋策略,來提高測(cè)試數(shù)據(jù)生成效率。Kumar等人[12]針對(duì)測(cè)試數(shù)據(jù)自動(dòng)生成問題,提出了一種蟻群優(yōu)化負(fù)選擇算法,對(duì)生成的數(shù)據(jù)進(jìn)行細(xì)化,以此來提高測(cè)試數(shù)據(jù)質(zhì)量。雖然傳統(tǒng)的優(yōu)化算法能夠有效地生成測(cè)試數(shù)據(jù),但是其受搜索能力以及更新速度等因素限制,容易陷入過早收斂,并且由于其缺乏并行性,在大規(guī)模路徑覆蓋或者復(fù)雜程序的測(cè)試數(shù)據(jù)生成問題中,存在計(jì)算時(shí)間過長、生成測(cè)試數(shù)據(jù)效率不高的問題。

在測(cè)試數(shù)據(jù)生成問題中,執(zhí)行路徑受到輸入數(shù)據(jù)、內(nèi)部結(jié)構(gòu)變化等因素影響,構(gòu)成了一個(gè)動(dòng)態(tài)的環(huán)境。同時(shí),路徑覆蓋問題中需要探索全局最優(yōu)解,測(cè)試數(shù)據(jù)的生成要考慮長期目標(biāo),而不是局部最優(yōu)解,這些都需要在高維度的決策空間中進(jìn)行搜索。強(qiáng)化學(xué)習(xí)[24]作為利用智能體與環(huán)境的交互進(jìn)行學(xué)習(xí)以達(dá)成回報(bào)最大化或?qū)崿F(xiàn)特定目標(biāo)的方法,在面向復(fù)雜程序的測(cè)試時(shí),以動(dòng)態(tài)環(huán)境為基礎(chǔ),通過獎(jiǎng)勵(lì)函數(shù),在動(dòng)態(tài)環(huán)境中展現(xiàn)出比其他智能優(yōu)化算法更好的環(huán)境適應(yīng)性和靈活性。同時(shí),強(qiáng)化學(xué)習(xí)具有一個(gè)長期的獎(jiǎng)勵(lì)導(dǎo)向功能,能夠高效地處理高維度的決策問題,與其他智能優(yōu)化算法相比,能夠更好地探索全局最優(yōu)解,不易陷入局部最優(yōu)。

在強(qiáng)化學(xué)習(xí)方面,曹靜[13]提出一種基于強(qiáng)化學(xué)習(xí)的智能化測(cè)試用例生成方法,通過強(qiáng)化學(xué)習(xí)模型建立測(cè)試智能體Xbot,將測(cè)試用例生成問題轉(zhuǎn)換為多步?jīng)Q策優(yōu)化問題,以此來快速生成測(cè)試用例。Spieker等人[14]使用一種基于強(qiáng)化學(xué)習(xí)的方法Retecs,其根據(jù)數(shù)據(jù)持續(xù)時(shí)間、上次執(zhí)行時(shí)間和失敗歷史來選擇測(cè)試用例,提供了一種更輕量級(jí)的學(xué)習(xí)方法,證明了強(qiáng)化學(xué)習(xí)能夠在持續(xù)集成和回歸測(cè)試中進(jìn)行有效的自動(dòng)化自適應(yīng)測(cè)試用例選擇。Esnaashari等人[15]提出一種模因算法,將強(qiáng)化學(xué)習(xí)作為遺傳算法中的一種局部搜索方法,以此來提高測(cè)試數(shù)據(jù)生成速度。Reddy等人[16]提出一種基于表格策略的強(qiáng)化學(xué)習(xí)方法RLCheck,將隨機(jī)選擇問題形式化成多樣化引導(dǎo)問題,通過RLCheck方法生成有效的測(cè)試數(shù)據(jù)。Cˇegiň等人[17]提出一種基于強(qiáng)化學(xué)習(xí)的測(cè)試數(shù)據(jù)生成方法,通過獎(jiǎng)賞函數(shù)對(duì)每一組測(cè)試數(shù)據(jù)形成的覆蓋率提供一個(gè)獎(jiǎng)勵(lì),同時(shí)將測(cè)試函數(shù)主體添加到強(qiáng)化學(xué)習(xí)算法中,根據(jù)被測(cè)函數(shù)的復(fù)雜度推斷個(gè)體嘗試次數(shù),再利用神經(jīng)網(wǎng)絡(luò)對(duì)獎(jiǎng)勵(lì)進(jìn)行訓(xùn)練,以此達(dá)到路徑的完全覆蓋或滿足給定的嘗試次數(shù)。Kim等人[18]使用強(qiáng)化學(xué)習(xí)取代元啟發(fā)式算法,將被測(cè)軟件重構(gòu)為強(qiáng)化學(xué)習(xí)環(huán)境,構(gòu)建了GunPowder框架,利用深度神經(jīng)網(wǎng)絡(luò)訓(xùn)練一個(gè)雙深度Q-Networks智能體,通過實(shí)驗(yàn)驗(yàn)證了其在分支路徑覆蓋上的可行性。Harries等人[19]提出一種用于功能軟件測(cè)試的強(qiáng)化學(xué)習(xí)(RL)框架DRIVE,并提出Batch-RL方法進(jìn)行Q學(xué)習(xí),用圖神經(jīng)網(wǎng)絡(luò)對(duì)狀態(tài)-動(dòng)作值函數(shù)進(jìn)行建模,證明此框架可以用自動(dòng)化的方式觸發(fā)所需的軟件功能,能夠高效地測(cè)試具有大范圍測(cè)試目標(biāo)的軟件。Tsai等人[20]提出了DeepRNG框架,其主要通過在框架里增加深度強(qiáng)化學(xué)習(xí)代理來提高軟件的測(cè)試數(shù)據(jù)生成效率。王立歆[21]提出了一種基于分層強(qiáng)化學(xué)習(xí)的混合測(cè)試算法LCCT,采用馬爾可夫決策過程作為上層控制,模糊測(cè)試方法作為決策補(bǔ)充來測(cè)試數(shù)據(jù)。Pan等人[22]提出了一種基于強(qiáng)化學(xué)習(xí)方法的Q-Testing,使用一種好奇心驅(qū)動(dòng)的策略來探索被測(cè)程序,該策略利用已訪問過的部分狀態(tài)來引導(dǎo)測(cè)試轉(zhuǎn)向不熟悉的程序區(qū)域。Pan等人[23]提出一種將可測(cè)性分析與強(qiáng)化學(xué)習(xí)相結(jié)合的方法,利用強(qiáng)化學(xué)習(xí)方法來大大縮減測(cè)試數(shù)據(jù)生成的時(shí)間,并提高代碼覆蓋率。綜上,強(qiáng)化學(xué)習(xí)算法通過將數(shù)據(jù)生成過程轉(zhuǎn)換成與環(huán)境的交互學(xué)習(xí)過程,能夠避免算法陷入過早收斂。同時(shí),智能體通過自主探索解空間,充分利用計(jì)算資源,能夠提高測(cè)試數(shù)據(jù)生成的效率。但現(xiàn)有的強(qiáng)化學(xué)習(xí)算法在面對(duì)路徑覆蓋的測(cè)試數(shù)據(jù)生成研究中仍面臨一些挑戰(zhàn),如探索過程不穩(wěn)定、測(cè)試用例贅余等問題。

為了應(yīng)對(duì)上述挑戰(zhàn),本文研究基于強(qiáng)化學(xué)習(xí)算法的路徑覆蓋測(cè)試數(shù)據(jù)生成方法,提出強(qiáng)化學(xué)習(xí)選擇算法(reinforcement learning selection algorithm,RLSA),將強(qiáng)化學(xué)習(xí)思想融入面向路徑覆蓋的測(cè)試數(shù)據(jù)生成中。在測(cè)試數(shù)據(jù)生成問題中,首先以待測(cè)程序的動(dòng)態(tài)環(huán)境為基礎(chǔ),定義智能體的狀態(tài)及動(dòng)作,將待測(cè)程序的可執(zhí)行路徑定義為狀態(tài),將每一輪更新的數(shù)據(jù)選擇定義為動(dòng)作,通過這種定義方式,極大地減少了無效數(shù)據(jù)的產(chǎn)生,降低了生成冗余測(cè)試數(shù)據(jù)的可能性;然后,將貪心策略與Q學(xué)習(xí)方法相結(jié)合,設(shè)計(jì)基于環(huán)境反饋Q值學(xué)習(xí)的貪心選擇策略,用確定性的動(dòng)作選擇來提高智能體學(xué)習(xí)的穩(wěn)定性和效率,以此避免隨機(jī)性探索時(shí)可能造成的探索過程不穩(wěn)定問題,實(shí)現(xiàn)測(cè)試數(shù)據(jù)生成的全局性;最后,利用獎(jiǎng)勵(lì)函數(shù)引導(dǎo)智能體在高維度的決策空間選擇最優(yōu)決策,使得智能體能夠快速地生成覆蓋所有可執(zhí)行路徑的數(shù)據(jù),以此來提高算法的效率。

1 相關(guān)知識(shí)及定義

強(qiáng)化學(xué)習(xí)[24]是利用智能體與周圍環(huán)境的感知來獲取最大獎(jiǎng)勵(lì)值,并基于此來尋找最優(yōu)化策略的方法過程。本文將強(qiáng)化學(xué)習(xí)的尋優(yōu)過程應(yīng)用到程序結(jié)構(gòu)上,先將程序結(jié)構(gòu)抽象成控制流圖,再利用智能體對(duì)環(huán)境的感知交互來作出決策,最后根據(jù)決策方法不斷迭代,從而實(shí)現(xiàn)目標(biāo)。對(duì)應(yīng)于軟件測(cè)試數(shù)據(jù)生成問題,下面定義在強(qiáng)化學(xué)習(xí)中智能體學(xué)習(xí)時(shí)涉及的相關(guān)概念及條件。

1.1 控制流圖

在待測(cè)程序中,控制流圖是一個(gè)表示程序執(zhí)行流程的有向圖G=〈V,W,s,e〉,也對(duì)應(yīng)著強(qiáng)化學(xué)習(xí)中智能體的整體學(xué)習(xí)環(huán)境。如圖1所示,其中節(jié)點(diǎn)表示程序的基本塊,邊表示基本塊之間的跳轉(zhuǎn)關(guān)系。記V={V1,V2,…,Vn}為有向圖的節(jié)點(diǎn)集,W={W1,W2,…,Wn}為有向圖的邊集,有Wjk=〈Vj,Vk〉,s和e分別為程序輸入的入口和出口。以圖1為例,有V={s,1,2,3,4,5,6,7,e},Ws1=〈s,1〉。

1.2 執(zhí)行路徑及其數(shù)目計(jì)算

執(zhí)行路徑是程序入口節(jié)點(diǎn)開始到出口節(jié)點(diǎn)的一條路徑,其通過節(jié)點(diǎn)的序列進(jìn)行表示,如圖1中“〈s,1,3,7,e〉”就是一條由節(jié)點(diǎn)序列組成的執(zhí)行路徑。對(duì)于可執(zhí)行路徑的數(shù)量,利用節(jié)點(diǎn)、兄弟節(jié)點(diǎn)以及分支節(jié)點(diǎn)數(shù)目計(jì)算,以圖1為例,其計(jì)算方式如下所示:路徑數(shù)目=兄弟節(jié)點(diǎn)+節(jié)點(diǎn)×[分支節(jié)點(diǎn)×(分支子節(jié)點(diǎn)+分支子節(jié)點(diǎn))+兄弟節(jié)點(diǎn)],M=②+③×[④×(⑤+⑥)+⑦],將所有節(jié)點(diǎn)代入數(shù)值1,得路徑數(shù)目為4。

1.3 狀態(tài)空間

對(duì)于狀態(tài)空間X={x0,…,xi,…},其中每一個(gè)狀態(tài)點(diǎn)xi都是對(duì)待測(cè)程序的一條可執(zhí)行路徑的描述,狀態(tài)空間為所有可執(zhí)行路徑的集合。以圖1為例,其狀態(tài)空間為X={〈s,1,2,e〉,〈s,1,3,4,5,e〉,〈s,1,3,4,6,e〉,〈s,1,3,7,e〉}。

1.4 動(dòng)作空間

對(duì)于動(dòng)作空間A={a0,a1,a2,…,ai,…},每一個(gè)動(dòng)作ai都是對(duì)新一輪更新后的數(shù)據(jù)進(jìn)行選擇行為的刻畫。以圖1程序?yàn)槔?,初始輸入的?shù)據(jù)為t,新一輪對(duì)輸入數(shù)據(jù)t進(jìn)行更新操作后產(chǎn)生的數(shù)據(jù)為t1,t2,t3,…,動(dòng)作a0=〈t,t1〉,a1=〈t1,t2〉。例如圖1中,若輸入數(shù)據(jù)為(a,b,c),進(jìn)行更新后產(chǎn)生的數(shù)據(jù)為(a1,b1,c1),(a2,b2,c2),動(dòng)作a0=〈(a,b,c),(a1,b1,c1)〉,a1=〈(a,b,c),(a2,b2,c2)〉。

1.5 獎(jiǎng)勵(lì)函數(shù)

獎(jiǎng)勵(lì)函數(shù)R與測(cè)試數(shù)據(jù)所要達(dá)成的目標(biāo)相關(guān)。對(duì)面向路徑覆蓋的測(cè)試數(shù)據(jù)來說,獎(jiǎng)勵(lì)函數(shù)影響著智能體的決策。因此需要對(duì)智能體的不同動(dòng)作賦予不同的獎(jiǎng)勵(lì)值,在每一輪更新的數(shù)據(jù)中,若這些數(shù)據(jù)中能夠執(zhí)行之前未通過的新路徑,那么給智能體一個(gè)正向獎(jiǎng)勵(lì),否則沒有獎(jiǎng)勵(lì)。具體如式(1)表示。

R=iR if data have new iR path(s)

R=0else(1)

以圖1為例,若初始數(shù)據(jù)集(a,b,c)更新后的數(shù)據(jù)為(a1,b1,c1),相較初始數(shù)據(jù)集多執(zhí)行了一條新路徑,則更新后的數(shù)據(jù)(a1,b1,c1)獲得獎(jiǎng)勵(lì)R=1。

2 基于強(qiáng)化學(xué)習(xí)的測(cè)試數(shù)據(jù)生成方法

本文研究利用強(qiáng)化學(xué)習(xí)思想提高測(cè)試數(shù)據(jù)生成效率的方法,從而快速實(shí)現(xiàn)待測(cè)程序的路徑覆蓋目標(biāo)。在強(qiáng)化學(xué)習(xí)中,智能體是在與環(huán)境的交互中獲得信息的,在基于強(qiáng)化學(xué)習(xí)的路徑覆蓋測(cè)試數(shù)據(jù)生成中,智能體需要使用策略來進(jìn)行狀態(tài)-動(dòng)作的選擇,從而生成覆蓋路徑的測(cè)試數(shù)據(jù)。為此,提出了一種學(xué)習(xí)策略來進(jìn)行智能體的模型訓(xùn)練,利用確定性的狀態(tài)-動(dòng)作選擇來加速智能體的學(xué)習(xí)過程,同時(shí)簡化計(jì)算過程。

2.1 建立基于強(qiáng)化學(xué)習(xí)的測(cè)試數(shù)據(jù)生成模型

在本文提出的基于強(qiáng)化學(xué)習(xí)的測(cè)試數(shù)據(jù)生成模型中,首先對(duì)初始數(shù)據(jù)集中覆蓋的路徑進(jìn)行覆蓋率計(jì)算。若滿足覆蓋率要求,初始數(shù)據(jù)集即為滿足要求的測(cè)試數(shù)據(jù);若不滿足覆蓋要求,則利用強(qiáng)化學(xué)習(xí)方法更新數(shù)據(jù),生成新的初始數(shù)據(jù)集。循環(huán)迭代,直到滿足覆蓋率要求輸出數(shù)據(jù)。其具體的模型運(yùn)行過程如圖2所示。

本文目標(biāo)是生成覆蓋所有路徑的數(shù)據(jù),即生成的測(cè)試數(shù)據(jù)能覆蓋待測(cè)程序的所有可執(zhí)行路徑。本文策略將貪心算法與Q學(xué)習(xí)算法相結(jié)合,用貪心選擇替換原本探索過程中的概率選擇。通過貪心算法,使得強(qiáng)化學(xué)習(xí)智能體更傾向于選擇當(dāng)前Q值最高的動(dòng)作,通過累積的Q值來引導(dǎo)智能體決策,促使算法能夠更快地收斂,并得到一組優(yōu)質(zhì)的測(cè)試數(shù)據(jù)。同時(shí),貪心算法和Q學(xué)習(xí)的結(jié)合能夠減少很多在概率探索過程中的不必要嘗試,更有針對(duì)性地選擇未覆蓋的可執(zhí)行路徑,使得生成的測(cè)試數(shù)據(jù)更有可能覆蓋未被探索的可執(zhí)行路徑,從而提高測(cè)試數(shù)據(jù)的質(zhì)量,提高算法的運(yùn)行效率,讓智能體能夠快速選擇出優(yōu)質(zhì)數(shù)據(jù),實(shí)現(xiàn)待測(cè)程序可執(zhí)行路徑的全覆蓋。

具體實(shí)現(xiàn)思路如下:首先,通過控制流圖,得到所有可執(zhí)行路徑的數(shù)目,同時(shí)將每一條可執(zhí)行路徑都定義為智能體的一種狀態(tài);然后,根據(jù)隨機(jī)方法生成初始輸入數(shù)據(jù),利用智能體轉(zhuǎn)換獲得初始狀態(tài)集合,當(dāng)這個(gè)初始狀態(tài)集合為狀態(tài)空間X的真子集時(shí),說明有可執(zhí)行路徑未被覆蓋,通過變異、隨機(jī)擾動(dòng)等方式更新初始輸入數(shù)據(jù),并生成多組更新后的數(shù)據(jù),以此來增加未覆蓋的可執(zhí)行路徑選擇概率;接著進(jìn)行更新數(shù)據(jù)的獎(jiǎng)勵(lì)函數(shù)值設(shè)定,在這些新生成的數(shù)據(jù)中,若有數(shù)據(jù)發(fā)現(xiàn)了初始數(shù)據(jù)集未覆蓋的執(zhí)行路徑,則智能體對(duì)這組數(shù)據(jù)選擇賦予正向獎(jiǎng)勵(lì)值,反之無獎(jiǎng)勵(lì)值;最終,智能體將獎(jiǎng)勵(lì)值最大的數(shù)據(jù)替換為新的初始數(shù)據(jù)集,繼續(xù)迭代,直到智能體的狀態(tài)覆蓋整個(gè)狀態(tài)空間,即覆蓋了待測(cè)程序的所有可執(zhí)行路徑。其更新以及動(dòng)作選擇的模型如圖3所示。

2.2 基于強(qiáng)化學(xué)習(xí)的測(cè)試數(shù)據(jù)生成模型實(shí)現(xiàn)

強(qiáng)化學(xué)習(xí)選擇策略的具體行為如下。在整個(gè)策略的具體行為上,首先通過分析待測(cè)程序控制流圖結(jié)構(gòu),計(jì)算出待測(cè)程序所有的可執(zhí)行路徑集合P以及對(duì)應(yīng)的完整狀態(tài)空間X。隨機(jī)生成初始數(shù)據(jù)集t0后,通過智能體轉(zhuǎn)換環(huán)境信息,獲得初始數(shù)據(jù)集t0當(dāng)前覆蓋的可執(zhí)行路徑p0,并得到初始狀態(tài)空間X0、初始動(dòng)作空間A0,并設(shè)置初始Q0值為0。接下來,對(duì)X0與X進(jìn)行比較。若X0X,則說明初始數(shù)據(jù)集t0未能完全覆蓋待測(cè)程序執(zhí)行路徑;若X0=X,則說明初始數(shù)據(jù)集t0已經(jīng)完全覆蓋待測(cè)程序執(zhí)行路徑,此時(shí)t0即為符合條件的測(cè)試用例。

下面說明在更新過程中,強(qiáng)化學(xué)習(xí)選擇策略的具體實(shí)現(xiàn):當(dāng)初始數(shù)據(jù)集未能完全覆蓋待測(cè)程序可執(zhí)行路徑時(shí),強(qiáng)化學(xué)習(xí)選擇策略將Q學(xué)習(xí)與貪心方法相結(jié)合來指導(dǎo)智能體進(jìn)一步探索學(xué)習(xí),通過對(duì)數(shù)據(jù)集ti中各重復(fù)覆蓋可執(zhí)行路徑的數(shù)據(jù)ti,j進(jìn)行m次變異、擾動(dòng)操作δ,使得智能體向下探索生成新數(shù)據(jù)集為ti,jδ={ti,j1,ti,j2,…,ti,jm},由智能體動(dòng)作空間A的定義,此時(shí)智能體的動(dòng)作集為{ai,jk=〈ti,j,ti,jδ〉|k=1,2,…,m},同時(shí)動(dòng)作空間更新為Ai+1=Ai∪{ai,jk}。再根據(jù)上述獎(jiǎng)勵(lì)函數(shù)R的定義,給予新數(shù)據(jù)集中不同數(shù)據(jù)對(duì)應(yīng)的獎(jiǎng)勵(lì)值iR,通過貪心策略選擇新數(shù)據(jù)集ti,jδ中具有最大獎(jiǎng)勵(lì)值的數(shù)據(jù)ti,jk,即有R(ti,j,ti,jk)=max R(ti,j,ti,jδ),同時(shí)更新狀態(tài)空間Xi+1以及數(shù)據(jù)集ti+1,并生成對(duì)應(yīng)的執(zhí)行路徑pi+1。在更新好數(shù)據(jù)集及狀態(tài)空間后,再通過強(qiáng)化學(xué)習(xí)選擇策略來更新Q值,使其不斷地引導(dǎo)智能體決策,更新公式如下:

Qi+1=(1-α)Qi+α(iRi+γ×max Q(x,a))(2)

其中:Qi+1為新數(shù)據(jù)集ti+1的Q值;α為智能體學(xué)習(xí)效率;Qi為當(dāng)前數(shù)據(jù)的Q值;iRi為所做動(dòng)作的獎(jiǎng)勵(lì);γ為折扣因子;max Q(x,a)為新狀態(tài)下能獲取的最大動(dòng)作獎(jiǎng)勵(lì)。最后將更新后的數(shù)據(jù)ti+1作為新的數(shù)據(jù)集,重復(fù)上述過程,不斷向下進(jìn)行探索迭代,直到生成覆蓋所有執(zhí)行路徑的數(shù)據(jù)并輸出結(jié)果。

2.3 算法偽代碼分析

算法1 強(qiáng)化學(xué)習(xí)選擇策略

輸入:隨機(jī)生成的被測(cè)程序的一組測(cè)試數(shù)據(jù)。

輸出:一組能夠覆蓋所有路徑的測(cè)試數(shù)據(jù)及各測(cè)試數(shù)據(jù)對(duì)應(yīng)的路徑。

1 function R(olddata,newdata)

2 if newdata have new iR path(s)

3 return iR //返回獎(jiǎng)勵(lì)值

4 end if

5 return 0

6 end function

7 main RLSA(X,P)

8 t0=random(data),t0,j∈t0 //數(shù)據(jù)域中隨機(jī)生成數(shù)據(jù)集

9 t0→p0 //由數(shù)據(jù)生成對(duì)應(yīng)路徑

10X0=Xt0,A0=At0,Q0=0

11for i=0 to N do

12 if XiX then

13 T=ti,jδ //變異、擾動(dòng)生成下一代數(shù)據(jù)集

14 ai,jk=〈ti,j,T〉

15 Ai+1=Ai∪{ai,jk}

16 iRi=max R(ti,T)

17 ai,jk→ti,jk∈T|iRi //選擇獎(jiǎng)勵(lì)最大的數(shù)據(jù)

18 (ai,jk,ti,jk)→xi,jk

19 Xi+1=Xi∪{xi,jk} //更新狀態(tài)空間

20 ti+1=(ti\{ti,j})∪{ti,jk}

21 ti+1→pi+1

22 Qi+1=(1-α)Qi+α(iRi+γ×max Q(x,a))

23 end if

24 return datas=models(ti+1)

25 return paths=models(pi+1)

26?; if Xi==X then

27 break

28 end if

29 end for

在上述代碼中,首先定義算法的獎(jiǎng)勵(lì)函數(shù)(第1行),通過判斷新數(shù)據(jù)是否涵蓋新的可執(zhí)行路徑,以此來賦予不同的獎(jiǎng)勵(lì)值(第2~5行)。接下來,指定算法策略(第7行),隨機(jī)生成初始數(shù)據(jù)集(第8行),由初始數(shù)據(jù)得到已覆蓋的路徑情況(第9行)、初始狀態(tài)空間、動(dòng)作空間以及Q值(第10行)。然后執(zhí)行本文算法的循環(huán)更新過程(第12~29行)。通過比較初始數(shù)據(jù)集狀態(tài)空間與整個(gè)待測(cè)程序狀態(tài)空間的包含關(guān)系來判定是否生成新數(shù)據(jù),若此時(shí)初始狀態(tài)集合為待測(cè)程序狀態(tài)空間集合真子集(第12行),則通過變異、擾動(dòng)等方式對(duì)重復(fù)覆蓋路徑的數(shù)據(jù)進(jìn)行更新(第13行),然后更新動(dòng)作集(第14行)以及動(dòng)作空間(第15行),再通過最大獎(jiǎng)勵(lì)值(第16行)進(jìn)行動(dòng)作選擇更新數(shù)據(jù)(第17行),以及更新數(shù)據(jù)對(duì)應(yīng)的狀態(tài)集(第18行)和狀態(tài)空間(第19行),之后更新數(shù)據(jù)集(第20行)、對(duì)應(yīng)的路徑(第21行)以及Q值(第22行)。最后,重復(fù)迭代上述過程,直到更新后數(shù)據(jù)集的狀態(tài)空間等于待測(cè)程序狀態(tài)空間或滿足迭代終止條件,輸出此時(shí)的測(cè)試數(shù)據(jù)(第24行)以及其對(duì)應(yīng)的可執(zhí)行路徑(第25行)。

2.4 時(shí)間復(fù)雜度分析

本文算法每次更新Q值表時(shí)需要進(jìn)行的計(jì)算量與狀態(tài)數(shù)目及動(dòng)作數(shù)目相關(guān)。具體來說,對(duì)于一個(gè)有n條可執(zhí)行路徑的程序,其狀態(tài)數(shù)為n,記每一次動(dòng)作選擇的數(shù)目為m,其中m不超過算法設(shè)定的最大變異數(shù)。在每次更新Q值表時(shí),需要計(jì)算所有狀態(tài)下可能的動(dòng)作獎(jiǎng)勵(lì),每個(gè)動(dòng)作的獎(jiǎng)勵(lì)需要進(jìn)行m次計(jì)算。又由于每次訓(xùn)練都需要進(jìn)行狀態(tài)的更新,所以總的計(jì)算量為O(N(nm)),其中N表示迭代次數(shù)。

3 實(shí)驗(yàn)分析

為驗(yàn)證本文方法在路徑覆蓋率方面的性能和可靠性,選擇隨機(jī)方法(RA)、傳統(tǒng)優(yōu)化算法中的遺傳算法(GA)、改進(jìn)的粒子群算法(PSO)[25]、TOGA算法[26]、GPSGA算法[27]和(RLSA),以及在不同的探索率下的強(qiáng)化學(xué)習(xí)Q-learning算法在兩個(gè)基準(zhǔn)程序以及兩個(gè)工業(yè)程序上進(jìn)行實(shí)驗(yàn)對(duì)比,以檢驗(yàn)本文算法是否具有更高的測(cè)試數(shù)據(jù)生成效率。本文所對(duì)比的幾種算法進(jìn)行測(cè)試數(shù)據(jù)生成時(shí),在全局搜索以及在處理復(fù)雜結(jié)構(gòu)方面都有較好的表現(xiàn),具有較好的尋優(yōu)能力。所有的程序在Python 3.8軟件環(huán)境下運(yùn)行,Windows 10操作系統(tǒng),機(jī)器主頻是2.80 GHz,內(nèi)存為16 GB。通過對(duì)比實(shí)驗(yàn)旨在回答下面幾個(gè)問題:

問題1 本文方法的數(shù)據(jù)生成效率是否優(yōu)于一些現(xiàn)有的優(yōu)化方法?

問題2 本文方法在覆蓋率方面是否優(yōu)于一些現(xiàn)有的優(yōu)化方法?

問題3 貪心探索策略在本文方法中是否優(yōu)于其他探索策略?

3.1 測(cè)試程序以及參數(shù)

本文使用的測(cè)試程序基本信息以及相關(guān)的實(shí)驗(yàn)參數(shù)如表1和2所示。其中:triangle classification和password strength程序都是傳統(tǒng)軟件測(cè)試中常用的基準(zhǔn)程序,其程序邏輯簡單,可以適應(yīng)多種不同的測(cè)試環(huán)境,以滿足不同條件下的測(cè)試;text sentiment和decision-making support都是在現(xiàn)實(shí)生活中被廣泛應(yīng)用的工業(yè)程序,具有一定的現(xiàn)實(shí)場(chǎng)景,能夠證明所提的測(cè)試策略在實(shí)際應(yīng)用中的性能和可靠性。

3.2 實(shí)驗(yàn)結(jié)果與分析

為了降低單次實(shí)驗(yàn)造成的結(jié)果誤差,將6種算法在測(cè)試程序上運(yùn)行20次,取其平均值作為對(duì)比數(shù)據(jù)。表3為6種算法在兩個(gè)基準(zhǔn)測(cè)試程序中的運(yùn)行時(shí)間、迭代次數(shù)以及多次運(yùn)行后平均覆蓋率的結(jié)果比較。

從表3中可以看出,在基準(zhǔn)程序1中,RA的隨機(jī)選擇導(dǎo)致其運(yùn)行時(shí)間最長,改進(jìn)后的PSO算法憑借其較快的收斂速度使其運(yùn)行時(shí)間相對(duì)較少,而RLSA運(yùn)行時(shí)間少于其他所有算法,這是因?yàn)镽LSA通過貪心策略進(jìn)行選擇,提高算法計(jì)算速度的同時(shí),一定程度上和其他算法相比減少了選擇范圍;在迭代次數(shù)方面,在這兩個(gè)基準(zhǔn)程序中,RLSA算法也都遠(yuǎn)少于其他的優(yōu)化算法以及隨機(jī)方法,這是因?yàn)閺?qiáng)化學(xué)習(xí)策略有較強(qiáng)的適應(yīng)性,能夠快速適應(yīng)問題及環(huán)境找到最優(yōu)解;在覆蓋率方面,在基準(zhǔn)程序1中,RLSA策略以及改進(jìn)后的PSO、TOGA算法都能夠成功找到覆蓋所有可執(zhí)行路徑的測(cè)試數(shù)據(jù),并且在一定程度上優(yōu)于GA、GPSGA以及隨機(jī)方法。這是因?yàn)樗鼈冊(cè)谌炙阉鞣矫娑歼M(jìn)行了相應(yīng)的優(yōu)化,都能夠跳出局部最優(yōu)。與此同時(shí),RLSA策略在兩個(gè)基準(zhǔn)程序上都可以使用較少的運(yùn)行時(shí)間來覆蓋待測(cè)程序的可執(zhí)行路徑,且都具有較好的覆蓋率。這是因?yàn)镽LSA策略是通過將待測(cè)程序的可執(zhí)行路徑作為狀態(tài)空間中的元素,這樣能夠更快地通過獎(jiǎng)勵(lì)函數(shù)的引導(dǎo)提高路徑的覆蓋率。圖4表示算法在各程序中隨時(shí)間變化的覆蓋率。圖4(a)為程序1的運(yùn)行時(shí)間與覆蓋率變化關(guān)系,其中RLSA策略可以最早達(dá)到100%覆蓋;圖(b)為程序2的運(yùn)行時(shí)間與覆蓋率變化關(guān)系,其中RLSA策略同樣可以最早達(dá)到100%覆蓋,RLSA策略相對(duì)于其余策略可以達(dá)到100%覆蓋,并且運(yùn)行時(shí)間最短、效率更高。

表4為6種算法在兩個(gè)工業(yè)測(cè)試程序中的運(yùn)行時(shí)間、迭代次數(shù)以及多次運(yùn)行后平均覆蓋率的結(jié)果比較。

從表4中可以看出,在text sentiment(程序3)程序的實(shí)驗(yàn)中,RLSA策略在運(yùn)行時(shí)間上優(yōu)于RA、GA和PSO算法,進(jìn)一步說明強(qiáng)化學(xué)習(xí)選擇策略在智能程序上的適用性;在迭代次數(shù)方面,RLSA也有著較好的性能,說明在數(shù)據(jù)生成方面強(qiáng)化學(xué)習(xí)選擇策略也有較好的收斂速度;在覆蓋率方面,RLSA能夠成功找到覆蓋所有可執(zhí)行路徑的測(cè)試數(shù)據(jù),高于TOGA以及PSO算法。在decision-making support程序(程序4)實(shí)驗(yàn)中,在運(yùn)行時(shí)間方面,RLSA遠(yuǎn)低于RA、TOGA以及GPSGA,這是因?yàn)镽LSA在面對(duì)復(fù)雜結(jié)構(gòu)時(shí),能夠高效地在高維度決策空間中選擇最優(yōu)策略;迭代次數(shù)方面,RLSA依然具有優(yōu)勢(shì);在覆蓋率方面,RLSA覆蓋率為100%,TOGA和GPSGA也有較高的覆蓋率,而其他算法覆蓋率則較低,這是因?yàn)樵诿鎸?duì)復(fù)雜的程序時(shí),其他算法在高維度空間決策方面能力較差,而TOGA策略使用反向?qū)W習(xí)提高未覆蓋路徑的搜索效率,GPSAG通過保留佳點(diǎn)集中的優(yōu)秀個(gè)體來提高搜索精度,RLSA策略利用獎(jiǎng)勵(lì)函數(shù)不斷引導(dǎo)智能體自主學(xué)習(xí)探索未知狀態(tài),增加智能體在復(fù)雜程序中的探索范圍和搜索效率,以此來實(shí)現(xiàn)更好的路徑覆蓋。因此,對(duì)于工業(yè)程序,RLSA算法在覆蓋率方面仍然保持著較好的性能。圖4(c)為程序3的運(yùn)行時(shí)間與覆蓋率變化關(guān)系,其中只有RLSA策略達(dá)到100%覆蓋;圖(d)為程序4的運(yùn)行時(shí)間與覆蓋率變化關(guān)系,同樣只有RLSA策略可以達(dá)到100%覆蓋,其余算法都未達(dá)到100%的覆蓋,說明RLSA策略在覆蓋率方面顯著優(yōu)于其他方法。

本文所提策略中使用貪心策略,相比于強(qiáng)化學(xué)習(xí)方法中原本的概率選擇方法,生成的測(cè)試數(shù)據(jù)能夠更好地覆蓋此前未覆蓋的可執(zhí)行路徑,較好地提高測(cè)試數(shù)據(jù)的生成效率。表5為強(qiáng)化學(xué)習(xí)選擇策略和其他使用不同探索率的強(qiáng)化學(xué)習(xí)Q-learning算法在運(yùn)行4種待測(cè)程序后的運(yùn)行時(shí)間比較。

從表5中可以看出,對(duì)于面向路徑覆蓋的測(cè)試數(shù)據(jù)生成問題,強(qiáng)化學(xué)習(xí)算法探索率ε和被測(cè)程序的運(yùn)行時(shí)間呈正相關(guān)。而本文貪心策略能夠?qū)崿F(xiàn)最高的探索率,使得強(qiáng)化學(xué)習(xí)選擇策略能夠?qū)崿F(xiàn)最短的運(yùn)行時(shí)間。這是由于可執(zhí)行路徑的確定,在RLSA中,將可執(zhí)行路徑作為動(dòng)作的選擇,每一次動(dòng)作更新都是對(duì)未被覆蓋路徑的選擇,每一次智能體向前探索時(shí),都會(huì)優(yōu)先選擇未被探索的可執(zhí)行路徑,以此來極大地縮短運(yùn)行時(shí)間,而概率選擇方法缺少搜索精度,效率會(huì)明顯低于貪心策略。圖5是在不同探索率下的強(qiáng)化學(xué)習(xí)Q-learning算法和本文算法在待測(cè)程序上的運(yùn)行時(shí)間比較。

3.3 算法穩(wěn)定性分析

通過分析RLSA對(duì)以上效率、覆蓋率、迭代次數(shù)影響的實(shí)驗(yàn),得出RLSA算法在性能方面有較好的優(yōu)勢(shì)。為進(jìn)一步分析RLSA策略的穩(wěn)定性,將RLSA與TOGA、GPSGA等算法進(jìn)行穩(wěn)定性對(duì)比。由于RLSA的最大迭代次數(shù)為50,所以僅選擇上述實(shí)驗(yàn)分析中迭代次數(shù)少于50次的算法進(jìn)行穩(wěn)定性對(duì)比。

下面重點(diǎn)分析RLSA、GPSGA、TOGA算法的穩(wěn)定性。對(duì)各算法種群迭代次數(shù)進(jìn)行統(tǒng)計(jì)分析,選取基準(zhǔn)測(cè)試程序和工業(yè)測(cè)試程序分別對(duì)比被測(cè)程序在各算法上種群迭代次數(shù),為避免結(jié)果的隨機(jī)性,使用各算法在被測(cè)程序上執(zhí)行5 000次的迭代次數(shù)數(shù)值來分析算法穩(wěn)定性。迭代次數(shù)統(tǒng)計(jì)結(jié)果使用帶有正態(tài)曲線的箱線圖進(jìn)行展示,箱線圖用來表現(xiàn)一組種群迭代次數(shù)數(shù)據(jù)的離散程度,正態(tài)曲線可以展示數(shù)據(jù)的分布情況。箱線圖由上至下依次表示異常值、上限、上四分位數(shù)(Q3)、中位數(shù)、下四分位數(shù)(Q1)、下限。采用上四分位數(shù)和下四分位數(shù)之差(IOR=Q3-Q4)表示統(tǒng)計(jì)數(shù)據(jù)的穩(wěn)定性,即箱線圖中箱子的高度,箱子高度越高說明數(shù)據(jù)離散程度越大,反之離散程度越小。

如圖6所示,RLSA與GPSA、TOGA算法對(duì)應(yīng)箱線圖的中位數(shù)值明顯低于其余算法的中位數(shù)值。在程序2中,RLSA策略的中位數(shù)值略低于TOGA和GPSGA,是因?yàn)閺?qiáng)化學(xué)習(xí)思想需要有強(qiáng)化和學(xué)習(xí)的過程,所以RLSA策略會(huì)存在少量的迭代學(xué)習(xí)過程,而在測(cè)試程序1、3、4中,RLSA策略優(yōu)勢(shì)明顯,均小于其余算法。從4個(gè)被測(cè)程序整體看,RLSA策略的迭代次數(shù)均保持在10代左右。

從箱線圖中的IQR值來看,RLSA策略在4個(gè)測(cè)試程序中的IQR值均小于其余算法的IQR值,這說明RLSA策略的穩(wěn)定性優(yōu)于GPSGA和TOGA。

對(duì)比箱線圖中的上四分位線,4個(gè)被測(cè)程序中,除被測(cè)程序2以外,RLSA策略均明顯低于其余算法,其中被測(cè)程序4的優(yōu)勢(shì)不明顯,其余被測(cè)程序中,RLSA策略均明顯優(yōu)于其余算法。從正態(tài)曲線看出,RLSA的數(shù)據(jù)分布離散程度最小,異常值較少,數(shù)據(jù)分布情況相比于其余算法較密集??傮w來說,RLSA策略比傳統(tǒng)算法和GPSGA、TOGA算法優(yōu)勢(shì)明顯,RLSA的覆蓋率、效率、穩(wěn)定程度均高于其余算法。

綜上,通過已得到的實(shí)驗(yàn)結(jié)果以及相關(guān)分析,逐一回答了之前的問題:

對(duì)于問題1:基于強(qiáng)化學(xué)習(xí)選擇算法的測(cè)試數(shù)據(jù)生成方法能夠更好地提高測(cè)試數(shù)據(jù)生成效率,因其通過合理的狀態(tài)定義以及高效的選擇策略,使得本文方法的測(cè)試數(shù)據(jù)生成效率優(yōu)于傳統(tǒng)的優(yōu)化算法。

對(duì)于問題2:與傳統(tǒng)的優(yōu)化方法相比,基于強(qiáng)化學(xué)習(xí)選擇算法的測(cè)試數(shù)據(jù)生成方法提高了路徑覆蓋率,并具有更好的穩(wěn)定性。

對(duì)于問題3:與其他探索策略相比,基于貪心的探索策略在本文方法中具有更好的性能。

4 結(jié)束語

本文提出了一種基于強(qiáng)化學(xué)習(xí)的測(cè)試數(shù)據(jù)生成方法RLSA,通過貪心策略的強(qiáng)化學(xué)習(xí)方法來實(shí)現(xiàn)高效率的測(cè)試數(shù)據(jù)生成。同時(shí),提出一種新的狀態(tài)表示方式,并設(shè)計(jì)新的動(dòng)作選擇方式為強(qiáng)化學(xué)習(xí)策略提供指導(dǎo),避免了使用強(qiáng)化學(xué)習(xí)方法生成測(cè)試數(shù)據(jù)時(shí)造成的大量贅余,提高了生成的測(cè)試數(shù)據(jù)的質(zhì)量。實(shí)驗(yàn)表明,RLSA在迭代次數(shù)、運(yùn)行時(shí)間以及路徑覆蓋率上優(yōu)于現(xiàn)有的一些方法。

未來,將通過優(yōu)化數(shù)據(jù)更新方式來進(jìn)一步改善狀態(tài)空間遍歷情況,以期能夠進(jìn)一步減少智能體訓(xùn)練時(shí)間。同時(shí),對(duì)于貪心策略在一些程序中可能產(chǎn)生的測(cè)試數(shù)據(jù)生成效率不高的問題,將繼續(xù)優(yōu)化智能體在探索和利用方面的性能,以此增強(qiáng)算法的普適性,進(jìn)一步提高測(cè)試數(shù)據(jù)生的成效率。

參考文獻(xiàn):

[1]喬夢(mèng)晴, 李琳, 王頡, 等. 基于遺傳規(guī)劃和集成學(xué)習(xí)的惡意軟件檢測(cè)[J]. 計(jì)算機(jī)應(yīng)用研究, 2023, 40(3): 898-904. (Qiao Mengqing, Li Lin, Wang Jie, et al. Malware detection based on genetic programming and ensemble learning[J]. Application Research of Computers, 2023, 40(3): 898-904.)

[2]張威楠, 孟昭逸, 熊焰, 等. 基于異質(zhì)信息網(wǎng)絡(luò)的安卓虛擬化程序檢測(cè)方法[J]. 計(jì)算機(jī)應(yīng)用研究, 2023, 40(6): 1764-1770. (Zhang Weinan, Meng Zhaoyi, Xiong Yan, et al. Detection method of Android virtualization program based on heterogeneous information network[J]. Application Research of Computers, 2023, 40(6): 1764-1770.)

[3]Anand S, Burke E K, Chen T Y, et al. An orchestrated survey of methodologies for automated software test case generation[J]. Journal of Systems & Software, 2013, 86(8): 1978-2001.

[4]單錦輝, 姜瑛, 孫萍, 等. 軟件測(cè)試研究進(jìn)展[J]. 北京大學(xué)學(xué)報(bào): 自然科學(xué)版, 2005, 41(1): 134-145. (Shan Jinhui, Jiang Ying, Sun Ping, et al. Research advances in software testing[J]. Journal of Peking University: Natural Science Edition, 2005, 41(1): 134-145.)

[5]Goschen J, Bosman A S, Gruner S, et al. Genetic Micro-programs for automated software testing with large path coverage[C]//Proc of IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE Press, 2022: 1-8.

[6]Sun Baicai, Gong Dunwei, Yao Xiangjuan, et al. Integrating DSGEO into test case generation for path coverage of MPI programs[J]. Information and Software Technology, 2023, 153: 107068.

[7]Zhang Wenxi, Sakamoto K, Washizaki H, et al. Improving fuzzing coverage with execution path length selection[C]//Proc of IEEE International Symposium on Software Reliability Engineering Workshops. Piscataway, NJ: IEEE Press, 2022: 132-133.

[8]Potluri S, Ravindra J, Mohammad G B, et al. Optimized test cove-rage with hybrid particle swarm bee colony and firefly cuckoo search algorithms in model based software testing[C]//Proc of the 1st International Conference on Artificial Intelligence Trends and Pattern Recognition. Piscataway, NJ: IEEE Press,2022: 1-9.

[9]Damia A, Esnaashari M, Parvizimosaed M. Automatic test data ge-neration based on the prime path coverage criterion: a grouping-based GA approach[EB/OL]. (2023-04-12). https://doi.org/10.21203/rs.3.rs-2796131/v1.

[10]丁蕊, 董紅斌, 張巖, 等. 基于關(guān)鍵點(diǎn)路徑的快速測(cè)試用例自動(dòng)生成方法[J]. 軟件學(xué)報(bào), 2016, 27(4): 814-827. (Ding Rui, Dong Hongbin, Zhang Yan, et al. Rapid test case generation method based on critical path[J]. Journal of Software, 2016, 27(4): 814-827.)

[11]錢忠勝, 祝潔, 朱懿敏. 結(jié)合關(guān)鍵點(diǎn)概率與路徑相似度的多路徑覆蓋策略[J].軟件學(xué)報(bào),2022, 33(2): 434-454.(Qian Zhong-sheng, Zhu Jie, Zhu Yimin. Multi-path coverage strategy combining key point probability and path similarity[J]. Journal of Software, 2022, 33(2): 434-454.)

[12]Kumar G, Chopra V. Automatic test data generation for basis path testing[J]. Indian Journal of Science and Technology, 2022, 15(41): 2151-2161.

[13]曹靜. 基于強(qiáng)化學(xué)習(xí)的Web API功能測(cè)試用例生成研究[D]. 上海:東華大學(xué), 2021. (Cao Jing. Research on Web API functional test case generation based on reinforcement learning[D]. Shanghai: Donghua University, 2021.)

[14]Spieker H, Gotlieb A, Marijan D, et al. Reinforcement learning for automatic test case prioritization and selection in continuous integration[C]//Proc of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis. New York:ACM Press, 2017: 12-22.

[15]Esnaashari M, Damia A H. Automation of software test data generation using genetic algorithm and reinforcement learning[J]. Expert Systems with Applications, 2021, 183: 115446.

[16]Reddy S, Lemieux C, Padhye R, et al. Quickly generating diverse valid test inputs with reinforcement learning[C]//Proc of the 42nd ACM/IEEE International Conference on Software Engineering. Pisca-taway, NJ: IEEE Press, 2020: 1410-1421.

[17]Cˇegiň J, Rástocˇny K. Test data generation for MC/DC criterion using reinforcement learning[C]//Proc of IEEE International Conference on Software Testing, Verification and Validation Workshops. Pisca-taway, NJ: IEEE Press, 2020: 354-357.

[18]Kim J, Kwon M, Yoo S, et al. Generating test input with deep reinforcement learning[C]//Proc of the 11th International Workshop on Search-Based Software Testing. Piscataway, NJ: IEEE Press, 2018: 51-58.

[19]Harries L, Clarke R S, Chapman T, et al. Drift: deep reinforcement learning for functional software testing[EB/OL]. (2020-07-16). https://arxiv.org/abs/2007.08220.

[20]Tsai C Y, Taylor G W. DeepRNG: towards deep reinforcement learning-assisted generative testing of software[EB/OL]. (2022-01-29). https://arxiv.org/abs/2201.12602.

[21]王立歆. 基于分層強(qiáng)化學(xué)習(xí)的自動(dòng)化軟件測(cè)試技術(shù)研究[D]. 沈陽:遼寧大學(xué), 2022. (Wang Lixin. Research on automated software testing technology based on hierarchical reinforcement learning[D].Shenyang: Liaoning University, 2022.)

[22]Pan Minxue, Huang An, Wang Guoxin, et al. Reinforcement lear-ning based curiosity-driven testing of Android applications[C]//Proc of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis. New York:ACM Press, 2020: 153-164.

[23]Pan Zhixin, Mishra P. Automated test generation for hardware trojan detection using reinforcement learning[C]//Proc of the 26th Asia and South Pacific Design Automation Conference. Piscataway, NJ: IEEE Press, 2021: 408-413.

[24]張汝波, 顧國昌, 劉照德, 等. 強(qiáng)化學(xué)習(xí)理論, 算法及應(yīng)用[J]. 控制理論與應(yīng)用, 2000, 17(5): 637-642. (Zhang Rubo, Gu Guochang, Liu Zhaode, et al. Reinforcement learning: theory, algorithms, and applications[J]. Control Theory & Applications, 2000, 17(5): 637-642.)

[25]Jaiswal U, Prajapati A. Optimized test case generation for basis path testing using improved fitness function with PSO[C]//Proc of the 13th International Conference on Contemporary Computing. New York:ACM Press, 2021: 475-483.

[26]Cheng Mengfei, Ding Rui, Huo Tingting, et al. A hyper-heuristic algorithm for test data generation[C]//Proc of the 6th International Conference on Big Data Research. New York:ACM Press, 2022: 26-31.

[27]程孟飛, 丁蕊. 基于佳點(diǎn)集遺傳算法的多路徑覆蓋測(cè)試用例生成[J]. 計(jì)算機(jī)與數(shù)字工程, 2022, 50(9): 1940-1944. (Cheng Mengfei, Ding Rui. Multi-path coverage test case generation based on optimal point set genetic algorithm[J]. Computer and Digital Engineering, 2022, 50(9): 1940-1944.)