基于強化學習選擇策略的路徑覆蓋測試數(shù)據(jù)生成算法

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

關鍵詞：測試數(shù)據(jù)生成； 路徑覆蓋； 強化學習； 選擇策略

中圖分類號：TP311 文獻標志碼：A

文章編號：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 引言

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

面向覆蓋的測試數(shù)據(jù)生成方法通過覆蓋待測軟件的需要滿足測試要求，是經(jīng)典的測試數(shù)據(jù)生成方法。路徑覆蓋作為面向覆蓋的最基本充分性準則之一，其要求選取足夠多的測試數(shù)據(jù)，使待測程序的每條可達路徑都至少執(zhí)行一次?？梢詫栴}描述為：對于給定程序的目標路徑，需要在程序的輸入空間里尋找或生成能夠覆蓋目標路徑的測試數(shù)據(jù)［4］。

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

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

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

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

1 相關知識及定義

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

1.1 控制流圖

在待測程序中，控制流圖是一個表示程序執(zhí)行流程的有向圖G=〈V，W，s，e〉，也對應著強化學習中智能體的整體學習環(huán)境。如圖1所示，其中節(jié)點表示程序的基本塊，邊表示基本塊之間的跳轉(zhuǎn)關系。記V={V1，V2，…，Vn}為有向圖的節(jié)點集，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ù)目計算

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

1.3 狀態(tài)空間

對于狀態(tài)空間X={x0，…，xi，…}，其中每一個狀態(tài)點xi都是對待測程序的一條可執(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 動作空間

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

1.5 獎勵函數(shù)

獎勵函數(shù)R與測試數(shù)據(jù)所要達成的目標相關。對面向路徑覆蓋的測試數(shù)據(jù)來說，獎勵函數(shù)影響著智能體的決策。因此需要對智能體的不同動作賦予不同的獎勵值，在每一輪更新的數(shù)據(jù)中，若這些數(shù)據(jù)中能夠執(zhí)行之前未通過的新路徑，那么給智能體一個正向獎勵，否則沒有獎勵。具體如式（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）獲得獎勵R=1。

2 基于強化學習的測試數(shù)據(jù)生成方法

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

2.1 建立基于強化學習的測試數(shù)據(jù)生成模型

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

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

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

2.2 基于強化學習的測試數(shù)據(jù)生成模型實現(xiàn)

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

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

Qi+1=（1－α）Qi+α（iRi+γ×max Q（x，a））（2）

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

2.3 算法偽代碼分析

算法1 強化學習選擇策略

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

輸出：一組能夠覆蓋所有路徑的測試數(shù)據(jù)及各測試數(shù)據(jù)對應的路徑。

1 function R（olddata，newdata）

2 if newdata have new iR path（s）

3 return iR //返回獎勵值

4 end if

5 return 0

6 end function

7 main RLSA（X，P）

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

9 t0→p0 //由數(shù)據(jù)生成對應路徑

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

11for i=0 to N do

12 if XiX then

13 T=ti，jδ //變異、擾動生成下一代數(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 //選擇獎勵最大的數(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

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

2.4 時間復雜度分析

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

3 實驗分析

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

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

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

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

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

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

3.2 實驗結果與分析

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

從表3中可以看出，在基準程序1中，RA的隨機選擇導致其運行時間最長，改進后的PSO算法憑借其較快的收斂速度使其運行時間相對較少，而RLSA運行時間少于其他所有算法，這是因為RLSA通過貪心策略進行選擇，提高算法計算速度的同時，一定程度上和其他算法相比減少了選擇范圍；在迭代次數(shù)方面，在這兩個基準程序中，RLSA算法也都遠少于其他的優(yōu)化算法以及隨機方法，這是因為強化學習策略有較強的適應性，能夠快速適應問題及環(huán)境找到最優(yōu)解；在覆蓋率方面，在基準程序1中，RLSA策略以及改進后的PSO、TOGA算法都能夠成功找到覆蓋所有可執(zhí)行路徑的測試數(shù)據(jù)，并且在一定程度上優(yōu)于GA、GPSGA以及隨機方法。這是因為它們在全局搜索方面都進行了相應的優(yōu)化，都能夠跳出局部最優(yōu)。與此同時，RLSA策略在兩個基準程序上都可以使用較少的運行時間來覆蓋待測程序的可執(zhí)行路徑，且都具有較好的覆蓋率。這是因為RLSA策略是通過將待測程序的可執(zhí)行路徑作為狀態(tài)空間中的元素，這樣能夠更快地通過獎勵函數(shù)的引導提高路徑的覆蓋率。圖4表示算法在各程序中隨時間變化的覆蓋率。圖4（a）為程序1的運行時間與覆蓋率變化關系，其中RLSA策略可以最早達到100%覆蓋；圖（b）為程序2的運行時間與覆蓋率變化關系，其中RLSA策略同樣可以最早達到100%覆蓋，RLSA策略相對于其余策略可以達到100%覆蓋，并且運行時間最短、效率更高。

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

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

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

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

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

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

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

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

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

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

綜上，通過已得到的實驗結果以及相關分析，逐一回答了之前的問題：

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

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

對于問題3：與其他探索策略相比，基于貪心的探索策略在本文方法中具有更好的性能。

4 結束語

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

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

參考文獻：

［1］喬夢晴， 李琳， 王頡， 等. 基于遺傳規(guī)劃和集成學習的惡意軟件檢測［J］. 計算機應用研究， 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)絡的安卓虛擬化程序檢測方法［J］. 計算機應用研究， 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］單錦輝， 姜瑛， 孫萍， 等. 軟件測試研究進展［J］. 北京大學學報： 自然科學版， 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］丁蕊， 董紅斌， 張巖， 等. 基于關鍵點路徑的快速測試用例自動生成方法［J］. 軟件學報， 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］錢忠勝， 祝潔， 朱懿敏. 結合關鍵點概率與路徑相似度的多路徑覆蓋策略［J］.軟件學報，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］曹靜. 基于強化學習的Web API功能測試用例生成研究［D］. 上海：東華大學， 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］王立歆. 基于分層強化學習的自動化軟件測試技術研究［D］. 沈陽：遼寧大學， 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］張汝波， 顧國昌， 劉照德， 等. 強化學習理論， 算法及應用［J］. 控制理論與應用， 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］程孟飛， 丁蕊. 基于佳點集遺傳算法的多路徑覆蓋測試用例生成［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.）