面向類集成測試序列確定的強化學習方法

張曉天，王雅文，2*，謝志慶，金大海，宮云戰(zhàn)

（1.網(wǎng)絡與交換技術(shù)國家重點實驗室，北京 100876；2.廣西密碼學與信息安全重點實驗室，廣西桂林 541004；3.北京郵電大學計算機學院（國家示范性軟件學院）， 北京 100876）

0 引言

軟件測試作為提高和保證軟件質(zhì)量的重要手段，目的是全面檢測并修復軟件中的缺陷，提升軟件質(zhì)量，增強用戶體驗［1］。如今，面向?qū)ο蟮木幊棠Ｊ揭褟V泛應用于實際軟件開發(fā)中，由于面向?qū)ο蟪绦蜷g錯綜復雜的調(diào)用關(guān)系，基于程序結(jié)構(gòu)的集成測試方法不再適用。例如，ATM 軟件系統(tǒng)由21 個類組成，假設首先集成類Bank，其依賴于類Status、Atm 和Money，不可避免地要設計測試樁模擬它們的調(diào)用結(jié)果，以保證Bank 類被正常測試。據(jù)文獻［2］統(tǒng)計，設計一個簡單的測試樁平均需要0.79 Person-hours。對于編寫復雜測試樁，過程繁瑣且容易出錯，這大大降低了測試人員的工作效率。因此，在集成測試之前，如何確定類集成的順序，使該測試序列的測試代價盡可能最小成了集成測試領(lǐng)域的研究熱點。這類問題被稱為類集成測試順序確定（CITO）問題［2］。如何設計并確定集成測試序列策略及度量測試成本是CITO 問題的研究目標，同樣適用于軟件模塊之間的集成測試。

CITO 問題是一個NP-完全問題［3］，很難得到準確的測試序列。傳統(tǒng)方案包括基于圖論方法和基于啟發(fā)式方法。圖論方法通過靜態(tài)分析提取并抽象有向的調(diào)用關(guān)系圖，利用環(huán)路破除算法使其成為無環(huán)圖，再對其進行逆向拓撲排序，最終得到測試序列，主要包括基于對象關(guān)系圖（ORD）［4］、基于動態(tài)依賴關(guān)系的拓展對象關(guān)系圖（EORD）［5］、基于耦合度量的加權(quán)對象關(guān)系圖（WORD）［6］和基于控制依賴的傳遞關(guān)系（TR）模型［7］。啟發(fā)式方法首先初始化一個代表類集成測試序列的種群，在一定約束條件下通過一系列選擇、交叉和變異操作生成測試序列，主要包括基于遺傳算法［8］、基于粒子群算法［9］、基于超啟發(fā)式算法［10］、基于帕累托蟻群克隆算法［11］、禁忌搜索多目標優(yōu)化算法［12］等。

強化學習（RL）作為機器學習的一個重要分支，通過交互目標導向的學習方式可以解決集成測試中的序貫決策問題［13-14］。智能體通過權(quán)衡探索與利用能夠提出更優(yōu)的解決方案，且效率要優(yōu)于啟發(fā)式算法。然而，現(xiàn)有的強化學習方法［15-16］存在計算成本高且優(yōu)化目標單一的問題，主要體現(xiàn)在以下兩個方面：

1）樸素的強化學習建模方式。基于節(jié)點的環(huán)境狀態(tài)表示，狀態(tài)空間是樹型的，空間復雜度達到O(nn)，狀態(tài)空間的存儲開銷大，對硬件要求高。另外，這種表示方法不利于狀態(tài)的搜索和更新，由于每一個狀態(tài)通過數(shù)值編碼唯一確定，狀態(tài)轉(zhuǎn)移需要通過數(shù)值計算的方式完成，計算開銷大。同時，基于節(jié)點的表示在系統(tǒng)集成狀態(tài)的表示上是冗余的。

2）測試風險的滯后性。大型軟件系統(tǒng)具有小世界特性和無標度特性［17］，即大部分節(jié)點只有少數(shù)連結(jié)，而少數(shù)節(jié)點則擁有大量的連結(jié)，其作用更為重要。如果將被測系統(tǒng)的關(guān)鍵節(jié)點放在靠后的位置測試，則會導致錯誤不能被及時發(fā)現(xiàn)，在實際測試中會存在不可估計的風險。

本文以降低測試樁復雜度并提升重要節(jié)點測試優(yōu)先級為優(yōu)化目標，提出一種具有重要值加權(quán)獎勵的基于測試順序的強化學習方法。首先，改進環(huán)境狀態(tài)的建模方式，提高轉(zhuǎn)移樣本的可學習性，并將狀態(tài)空間的復雜度從O(nn)降為O(2n)；然后，設計一種符合優(yōu)化目標的獎勵函數(shù)，將修正的節(jié)點重要值和測試樁復雜度融入獎勵值的計算，并提出相應的評估指標；最后，將掩碼序列作為深度強化學習模型的輸入，使得智能體從初態(tài)到終態(tài)的過程中不斷通過獎勵優(yōu)化狀態(tài)到動作策略的映射，最終生成滿足優(yōu)化目標的最優(yōu)測試序列。

1 基礎知識

定義1在ORD 中，類被抽象為節(jié)點，類間依賴關(guān)系被抽象為有向邊。假設系統(tǒng)規(guī)模為n，表示組成該系統(tǒng)的類數(shù)量。ORD 由節(jié)點集合V={Vi,i=1,2,…,n}和邊集合E={eij,Vi,Vj?V}組成。

定義2在UML 類圖中6 種常見的靜態(tài)依賴關(guān)系可歸結(jié)為關(guān)聯(lián)關(guān)系（包括依賴和關(guān)聯(lián)關(guān)系，記作As）、聚合關(guān)系（包括聚合和組合關(guān)系，記作Ag）和繼承關(guān)系（包括泛化和實現(xiàn)關(guān)系，記作In）。將靜態(tài)依賴關(guān)系的集合作為邊集E=EAs∪EAg∪EIn。

定義3由于面向?qū)ο缶幊痰亩鄳B(tài)性，因此程序運行時會產(chǎn)生一種動態(tài)依賴關(guān)系［18］，記作Dy。拓展的邊集Eexd=E∪EDy。

圖1 展示了由8 個類組成的實例test 系統(tǒng)的EORD，共計包含8 個節(jié)點、11 條邊，包括兩個強相關(guān)關(guān)系。由于VF 與VE 具有繼承關(guān)系，且VG 與VE 之間存在關(guān)聯(lián)關(guān)系，在程序運行時VG 與VF 之間會產(chǎn)生動態(tài)依賴關(guān)系。

定義4αt表示t時刻的測試序列，由t-1 時刻測試序列和當前時刻被測節(jié)點組成，初始的測試序列為空集，如式（1）所示。當t=n時，測試序列確定，記為α。

定義5為了順利執(zhí)行測試，需要編寫代碼片段模擬返回值。測試樁復雜度（SCplx）用于衡量測試樁的代價，是屬性復雜度Aplx(i,j)和方法復雜度Mplx(i,j)的加權(quán)平方和［6］，如式（2）所示：

其中：節(jié)點i和節(jié)點j之間具有調(diào)用關(guān)系；SCplx(i,j)代表節(jié)點i依賴于節(jié)點j的測試樁復雜度；屬性復雜度Aplx(i,j)是節(jié)點i調(diào)用節(jié)點j的成員變量、方法參數(shù)類型與方法的返回值數(shù)目之和；方法復雜度Mplx(i,j)是節(jié)點i調(diào)用節(jié)點j中方法的數(shù)目；wM和wA是方法和屬性復雜度的權(quán)重，且wM+wA=1。屬性和方法復雜度的縮放，如式（3）和式（4）所示：

定義6節(jié)點重要值表示節(jié)點期望被優(yōu)先測試的程度，使用W表示，為影響力和復雜度的平均值，如式（5）所示：

其中：I和C分別代表影響力和復雜度。

由于扇入扇出耦合度量是類間耦合度量的基礎［19］，影響力通常與節(jié)點的入度值相關(guān)，復雜度通常與節(jié)點的出度值相關(guān)。根據(jù)HITS 算法［20］，首先通過C&K 度量［21］中特征數(shù)量和類間依賴程度完成初始化，如式（6）所示；之后，令影響力為權(quán)威值，復雜度為樞紐值，不斷迭代至收斂，迭代計算過程如式（7）和式（8）所示。

其中：F和D分別代表特征數(shù)量和類間依賴程度；wF和wD是指標權(quán)重，權(quán)重通過信息熵確定，所以針對不同被測系統(tǒng)，該值是不同的；i→j代表節(jié)點i與節(jié)點j之間具有依賴關(guān)系。

2 問題描述

在面向?qū)ο蟪绦驎r，對象之間通過消息傳遞機制相互聯(lián)系，消息經(jīng)過傳遞會形成一條方法調(diào)用鏈。由于多條調(diào)用鏈相互交錯，類間的調(diào)用關(guān)系變得錯綜復雜，對象關(guān)系圖呈現(xiàn)網(wǎng)絡結(jié)構(gòu)。在實際應用中，幾乎所有面向?qū)ο蟮南到y(tǒng)都包含環(huán)路［22］，85%的系統(tǒng)包含超過10 個類的強連通組件（SCCs）。對于含有環(huán)路的對象關(guān)系圖，在打破環(huán)路的過程中，不可避免地需要編寫測試樁，測試樁的復雜程度影響集成測試代價。另外，由于軟件系統(tǒng)具有復雜網(wǎng)絡特性，如果將被測系統(tǒng)的關(guān)鍵節(jié)點滯后測試，則會使錯誤不能被及時發(fā)現(xiàn)，在實際測試中存在難以預估的風險。本文將面向?qū)ο蟪绦虻募蓽y試問題建模為在滿足一定約束條件下的測試序列優(yōu)化問題。度量指標為整體測試樁復雜度（OCplx）和半序列重要值（SHO）。

定義7節(jié)點i、j分別是α中的節(jié)點，節(jié)點i依賴于節(jié)點j且節(jié)點j并未被集成，即節(jié)點j在α中的位置在節(jié)點i之后［23］。所有節(jié)點的測試樁復雜度之和為測試序列α的OCplx(α)，如式（9）所示。CITO 的優(yōu)化目標為min(OCplx(α))，最優(yōu)解為α*。

鑒于軟件系統(tǒng)的復雜網(wǎng)絡特性，期望重要節(jié)點可以優(yōu)先被測試，并定義半序列重要值指標以衡量重要節(jié)點的優(yōu)先級是否被提升。

定義8通過計算測試序列α前半部分節(jié)點的重要值之和，度量測試序列的重要值，以評估關(guān)鍵節(jié)點的優(yōu)先級是否被提升，半序列重要值如式（10）所示：

3 具有重要值加權(quán)獎勵的基于測試順序的強化學習方法

3.1 方法概述

以整體測試樁復雜度盡可能低且重要節(jié)點優(yōu)先被測試為優(yōu)化目標，提出一種具有重要值加權(quán)獎勵的基于測試順序的強化學習方法（TOIR）確定集成類測試序列。TOIR 基于異步優(yōu)勢行動者評論家（A3C）算法［24］，具有多個線程私有的網(wǎng)絡和一個共享的主網(wǎng)絡，并且具有相同的網(wǎng)絡結(jié)構(gòu)。每一套網(wǎng)絡都由基于策略梯度更新策略的行動者和基于值函數(shù)評估狀態(tài)值的評論家組成。圖2 展示了TOIR 與環(huán)境交互的過程。TOIR 在每一個時間步t中，將測試序列αt編碼成st。將st作為行動者網(wǎng)絡的輸入，輸出所有待測節(jié)點被選擇的概率（已集成的節(jié)點執(zhí)行概率重置為0）。根據(jù)執(zhí)行概率，TOIR 選擇動作at并執(zhí)行。環(huán)境會反饋給智能體獎勵rt和新的測試序列αt+1編碼成st+1。評論家使用神經(jīng)網(wǎng)絡近似狀態(tài)st、st+1的評估值，并計算tderror=rt+γV(st+1)-V(st)，以更新行動者網(wǎng)絡參數(shù)θπ。另外，根據(jù)tderror計算均方誤差更新評論家網(wǎng)絡參數(shù)θv。

圖2 TOIR 系統(tǒng)架構(gòu)Fig.2 TOIR system architecture

TOIR 通過在有限的時間內(nèi)在環(huán)境中探索，學習到一種可靠的從狀態(tài)到動作映射的策略π(s,a)，即根據(jù)系統(tǒng)當前的集成狀態(tài)，選擇最有利于控制測試成本和風險的類進行集成。在智能體從初態(tài)到終態(tài)的過程中，測試序列α可以表示為動作的歷史執(zhí)行路徑δα，屬于全部類全排列。智能體通過不斷優(yōu)化策略，最終確定最優(yōu)的測試序列α*。

3.2 CITO 問題的建模過程

強化學習是一種從狀態(tài)映射到動作的學習，目標是使智能體在與環(huán)境的交互過程中獲得最大的累積獎勵。馬爾可夫決策過程（MDP）可以用來建模強化學習問題［25］，通常將MDP 定義為四元組，如式（11）所示：

其中：S為有限的狀態(tài)集合；A為有限的動作集合；P為狀態(tài)轉(zhuǎn)移的概率；R為獎勵函數(shù)。當智能體處于某一狀態(tài)si時，依據(jù)當前狀態(tài)選擇動作ai，并以某種概率pi轉(zhuǎn)移到下一狀態(tài)si+1。當環(huán)境狀態(tài)轉(zhuǎn)移之后，獎勵函數(shù)可以記為r(si+1|si,ai)。假設歷史動作總共有n個動作，MDP 流程如圖3 所示。針對集成測試序列的確定問題，需要尋求一組最優(yōu)序列，本節(jié)將具體定義馬爾可夫決策過程中的各個元素。

圖3 MDP 流程Fig.3 Procedure of MDP

3.2.1 環(huán)境狀態(tài)

狀態(tài)st是對t時刻環(huán)境的描述。在CITO 問題中，使用測試序列αt作為狀態(tài)st的基礎，如式（12）所示。具體而言，采用0-1 編碼的掩碼序列表示測試序列αt的集成狀態(tài)，即長度為系統(tǒng)規(guī)模的0-1 序列，其中，0代表該節(jié)點未被集成，1 代表該節(jié)點已被集成。初態(tài)為長度為n的全0 序列，終態(tài)為長度為n的全1 序列。

假設系統(tǒng)中包含3 個類A、B、C，存在2 個測試序列，即α1=[A，C，B]和α2=[C，B，A]。若使用基于節(jié)點的建模方式，兩種測試序列的路徑分別為=[0，1，6，20]和=[0，3，11，34]，狀態(tài)空間如圖4 所示。相反地，若使用基于序列的建模方式，得到的路徑分別為=[000，001，101，111]和=[000，100，110，111]，狀態(tài)空間如圖5 所示。

圖4 基于節(jié)點的狀態(tài)空間Fig.4 Node-based state space

圖5 基于序列的狀態(tài)空間Fig.5 Order-based state space

基于節(jié)點的狀態(tài)表示方法主要存在以下3 個方面的局限性：

2）狀態(tài)之間強關(guān)聯(lián)性。當智能體處于環(huán)境狀態(tài)6 和10 時，分別對應的測試序列為[A,C]和[C,A]。此時，系統(tǒng)僅剩類B未集成，而智能體需要根據(jù)狀態(tài)6 和10 完成下一個待集成類的選擇。狀態(tài)6 和10 分別代表一種有序的排列，當前的決策受t=[0,1,…,t-1]時刻決策的影響，這不利于智能體的學習。相反地，基于序列的表示方法只區(qū)分是否加入測試序列，忽略了節(jié)點在測試序列中的位置，使得智能體的動作選擇僅依賴當前時刻智能體所處狀態(tài)，而與之前的序列無關(guān)，滿足馬爾可夫性，即其未來狀態(tài)僅依賴于當前狀態(tài)，與歷史狀態(tài)無關(guān)。

3）抽象的環(huán)境狀態(tài)描述?；诠?jié)點的表示方法使用編號表示環(huán)境狀態(tài)，需要通過計算才能確定唯一的測試序列，而基于序列的表示方法能夠直觀地了解系統(tǒng)當前的集成狀態(tài)。

3.2.2 智能體行為

at是t時刻智能體的行為。在CITO 問題中，使用獨熱編碼表示智能體的行為。在每一個狀態(tài)下的可選動作是未被集成的節(jié)點，即狀態(tài)中標記為0 的節(jié)點。動作空間是離散的，其維度是系統(tǒng)規(guī)模。假設系統(tǒng)包含3 個節(jié)點，動作空間為3 維，可以使用001、010、100 表示。

3.2.3 狀態(tài)轉(zhuǎn)移

狀態(tài)轉(zhuǎn)移表示為狀態(tài)與動作的邏輯運算，如式（13）所示。假設智能體在初始狀態(tài)s0=000，若選擇節(jié)點010 集成，那么狀態(tài)轉(zhuǎn)移到s1=010，如此反復，直至終態(tài)s3=111。

3.2.4 獎勵函數(shù)

獎勵是環(huán)境給予智能體的反饋，作為智能體在狀態(tài)st下執(zhí)行動作at的即時獎勵。為了適應CITO問題的優(yōu)化目標，在獎勵函數(shù)中融入節(jié)點重要值和測試樁復雜度，如式（14）所示：

其中：常數(shù)μ和η能夠避免節(jié)點重要值或測試代價為0；modify(Wat)計算修正的節(jié)點重要值，包括歸一化和tanh 拉伸操作，如式（15）所示；cost(st,at)表示狀態(tài)st下集成節(jié)點at所需的測試代價，如式（16）所示；Tat→i的值與依賴關(guān)系的類型相關(guān)。為了減少破除強相關(guān)關(guān)系（In 和Ag）［26］，令其測試代價乘以一個大于1 的系數(shù)，使得智能體獲得的獎勵盡可能小。

4 實驗與結(jié)果分析

4.1 實驗設置及對象

設置超參數(shù)學習率為0.000 1、折扣率為0.8、訓練次數(shù)為20 000、訓練線程數(shù)為4、強相關(guān)關(guān)系的系數(shù)為5?；赑ython3.8、PyTorch 1.10.1、Windows 10操作系統(tǒng)及Intel?CoreTM7-11500U 處理器進行實驗。

選取8 個Java 系統(tǒng)作為被測對象，表1 展示了不同被測系統(tǒng)的系統(tǒng)規(guī)模、依賴數(shù)量、成圈數(shù)量、代碼行數(shù)，其中，Ant、Atm、Spm、Dns 是來自Briand 基準系統(tǒng)，Daisy、Email-spl、JaConTeBe 是SIR 網(wǎng)站上的開源程序類系統(tǒng)。所有的統(tǒng)計信息均來源于Soot 程序解析。

表1 被測對象信息Table 1 Tested object information

4.2 實驗驗證

實驗1 在集成測試序列確定問題中，驗證壓縮編碼的測試序列是否為一種合適的狀態(tài)表示。

使用編碼的測試序列表示強化學習任務中的環(huán)境狀態(tài)，使用神經(jīng)網(wǎng)絡存儲狀態(tài)的評估值。首先，設置實驗對比方法NIR，同文獻［13-14］使用節(jié)點定義強化學習任務中的狀態(tài)，保留了TOIR 的決策部分。表2 展示了使用TOIR 和NIR 在8 個被測系統(tǒng)上的測試樁復雜度。

表2 TOIR 與NIR 的性能對比Table 2 Performance comparison between TOIR and NIR

由表2 可以看出：針對中小規(guī)模系統(tǒng)，TOIR 在Ant、Atm、Daisy、Email-spl、Spm 系統(tǒng)上效果優(yōu)于NIR；針對大規(guī)模系統(tǒng)JaConTeBe，NIR 不能取得有效結(jié)果，因為NIR 中RL 任務中狀態(tài)轉(zhuǎn)移通過數(shù)值計算的方式完成，計算復雜度為O(189189)，智能體無法在狀態(tài)空間中高效探索，進而不能得到有效結(jié)果。另外，由于狀態(tài)之間的強相關(guān)性，NIR 在狀態(tài)動作的策略上受t=[0,1…,t-1]時刻決策的影響，不利于智能體的學習。在TOIR 中，狀態(tài)被定義為測試序列的編碼形式只區(qū)分是否加入測試序列，忽略節(jié)點在測試序列的位置，使得智能體的動作選擇僅依賴當前時刻智能體所處狀態(tài)，與之前的序列無關(guān)，且智能體從初態(tài)到終態(tài)的歷史動作路徑，對應系統(tǒng)的集成狀態(tài)的改變，無需額外的編碼轉(zhuǎn)換，更加直接有效，大大降低了計算成本。智能體通過學習長度為189 的0-1 序列與獨熱的節(jié)點編碼之間的映射，最終根據(jù)映射策略得到最優(yōu)解。針對Dns 系統(tǒng)，TOIR 略遜于NIR，系統(tǒng)內(nèi)部的調(diào)用關(guān)系眾多，包含依賴關(guān)系共計447 條，環(huán)路破除涉及的依賴關(guān)系復雜，當兩者的測試序列生成的策略不同時，造成前者的效果略遜于后者。

綜上所述，基于節(jié)點的表示方法搜索空間龐大且路徑要求高，導致算法很難收斂至最優(yōu)解，易于陷入局部最優(yōu)解，而本文所提的基于序列的表示方法能夠有效解決這一問題。

設置實驗對比方法Q_CITO，使用Q-learning 算法［27］作為智能體的決策部分，以驗證TOIR 中使用A3C 模型的效果。圖6 展示了TOIR 和Q_CITO 在8 個系統(tǒng)上的OCplx 與系統(tǒng)規(guī)模之間的關(guān)系（彩色效果見《計算機工程》官網(wǎng)HTML 版，下同）。由圖6 可以看出，Q_CITO 的OCplx 與系統(tǒng)規(guī)模趨勢相同，而TOIR 的OCplx 維持在一個穩(wěn)定的區(qū)間，尤其在系統(tǒng)規(guī)模較大的Dns 和JaConTeBe 系統(tǒng)中。Q_CITO 容易受到系統(tǒng)規(guī)模的影響，尤其在大規(guī)模系統(tǒng)中，適應性會變得很低，只能在中小規(guī)模的系統(tǒng)上適用。這是因為Q-learning 算法需要維護一張NS×NA的Q 表記錄狀態(tài)-動作對，盡管已經(jīng)使用基于序列的表示方法縮減狀態(tài)空間，但當系統(tǒng)規(guī)模較大或結(jié)構(gòu)復雜時（如JaConTeBe 和Spm），基于值函數(shù)的評估不準確，導致效果不佳。在TOIR 中，隨著系統(tǒng)規(guī)模的增長測試樁復雜度并不會顯著增加，這是因為基于序列的表示方法結(jié)合A3C 深度強化學習模型能夠更加有效地解決CITO 問題。A3C 模型以系統(tǒng)集成狀態(tài)的掩碼序列為模型輸入，在不同的環(huán)境狀態(tài)下，輸出每一個節(jié)點被集成的概率分布，并通過環(huán)境給予的即時獎勵更新概率分布的生成，優(yōu)化集成測試策略，最終快速有效地生成最優(yōu)的測試序列。在這一過程中，不需要計算狀態(tài)-動作的評估值，而是直接更新動作的概率分布，減弱了值函數(shù)計算的誤差，提升了模型效果。

圖6 TOIR 與Q_CITO 的對比Fig.6 Comparison of TOIR and Q_CITO

由此可以得出：使用高效的狀態(tài)編碼表示可以在顯著降低計算量的同時，使得智能體探索得到更加合理的測試序列；利用A3C 可以巧妙地避免智能體在探索最優(yōu)測試序列時狀態(tài)-動作對的存儲，在應用于大規(guī)模系統(tǒng)時依舊有效，增加了TOIR 的普適性與穩(wěn)定性。

實驗2在獎勵函數(shù)中，引入修正的節(jié)點重要值，驗證重要節(jié)點能否被優(yōu)先測試。

為了驗證在獎勵函數(shù)中融入節(jié)點重要值是否可以有效地提升重要節(jié)點在測試序列中的位置，設置獎勵函數(shù)中不包含節(jié)點重要值的TO，展示關(guān)鍵節(jié)點在測試序列中的位置，如表3 所示，其中，NO、Name分別代表類的編號和名稱，IMPO、A 分別代表重要值的原始值和修正值，#和I#分別代表TO 和TOIR 所得序列的位置。篇幅所限，僅展示Briand 基準系統(tǒng)的結(jié)果。

表3 關(guān)鍵節(jié)點在測試序列中的位置對比Table 3 Position comparison of key nodes in the test order

Ant 系統(tǒng)的關(guān)鍵類共計7 個，占28%。盡管BuildException 類的屬性復雜度和方法復雜度很低，但由于該類的屬性被12 個類訪問，且該類的方法被11 個類調(diào)用，其自身的測試風險很容易傳播到引用它的類中，因此其自身的重要值較高。對于Project等類，由于其自身的屬性復雜度和方法復雜度較高，因此應盡可能滿足測試代價低的條件，提升這些類的優(yōu)先級。較TO 關(guān)鍵類的優(yōu)先級，TOIR 最多提前了14 個位置，即RuntimeConfigurable 類整體提高了57%。

Atm 系統(tǒng)的關(guān)鍵類共計7 個，占33%。盡管Status 和Money 類的屬性復雜度和方法復雜度為0，但由于Status 類的屬性被7 個類訪問，而Money 類的屬性被10 個類訪問，且該類的方法被11 個類調(diào)用，其自身的測試風險很容易傳播到引用它的類中，TOIR 提高了兩者的測試優(yōu)先級，且不會造成任何代價。對于其他關(guān)鍵類的優(yōu)先級，TOIR 較TO 提前了1～9 個位置不等，最突出的是編號為11 的WithdrawlTransaction 類在測試序列中提前了9 個位置，較TO 整體提高了28%。

Dns 系統(tǒng)的關(guān)鍵類共計9 個，占15%。重要值排名第1 的類為Name 類，其屬性被30 個類訪問，且其方法被29 個類引用，測試代價較低且影響力較高，TOIR 將其優(yōu)先級從25 提高至9。重要值排名第2 的類為Type 類，其屬性被33 個類訪問，且其方法被8 個類調(diào)用，測試代價為0 且影響力較高，TOIR 將其優(yōu)先級從5 提升至1，不會改變該類的測試代價。對于Message 等類，測試代價極高，TOIR 提升其優(yōu)先級幅度受限，關(guān)鍵類的變化不明顯，兩者在前半序列的占比分別為44%和33%。

Spm 系統(tǒng)的關(guān)鍵類共計9個，占47%。Checkpoint類的屬性被5 個類訪問，且該類的方法被5 個類調(diào)用，有可能將風險傳播，但是其重要值不高，僅排名第9。由于Spm 系統(tǒng)包含環(huán)路較多，系統(tǒng)較為復雜，TOIR得到的關(guān)鍵類的位置較TO 相差不大，關(guān)鍵類提前或是位置不變，兩者關(guān)鍵類處于前半序列的比例分別為67%和56%，以保證不會造成因調(diào)整關(guān)鍵類的優(yōu)先級而增加測試樁復雜度。

圖7 展示了獎勵函數(shù)中使用原始值和修正值之間OCplx 和SHO 的關(guān)系，前者使用“*”標記。由圖7可以看出，在獎勵函數(shù)中使用修正的節(jié)點重要值不論在測試代價和重要節(jié)點的優(yōu)先級上都具有更好的效果。這是因為類重要值的計算與軟件系統(tǒng)的結(jié)構(gòu)密切相關(guān)。具體而言，類重要值的計算是以特征數(shù)目和耦合程度為基礎，通過復雜網(wǎng)絡算法迭代得到。若在獎勵函數(shù)中直接使用原始的類重要值，可能會降低模型的魯棒性，主要體現(xiàn)在以下兩個方面：

圖7 原始與修正節(jié)點重要值的效果對比Fig.7 Effect comparison of original and modified node importance values

1）獎勵函數(shù)針對不同系統(tǒng)中關(guān)鍵類的評價標準可能不一致。不同系統(tǒng)中節(jié)點重要值分布是不一致的。假設計算不同系統(tǒng)中關(guān)鍵類的獎勵值時，兩者得到的結(jié)果差異可能很大，使得模型對于關(guān)鍵類優(yōu)先級的評定標準差異很大，導致算法針對不同系統(tǒng)是敏感的，降低了模型的可用性和魯棒性。

2）獎勵函數(shù)的不穩(wěn)定性。系統(tǒng)中節(jié)點重要值分布的差異性導致各個節(jié)點重要值的差距可能很大或很小，不同程度上擴大或縮小即時獎勵的作用，造成模型性能不佳。相反地，通過使用修正的節(jié)點重要值能夠有效緩解同一系統(tǒng)中即時獎勵的不穩(wěn)定性，并且統(tǒng)一不同系統(tǒng)關(guān)于關(guān)鍵類的評估標準，增強模型的魯棒性。

整體而言，在8 個被測系統(tǒng)中，重要節(jié)點占全部節(jié)點的平均值為18%，引入重要值的獎勵函數(shù)可以提升重要節(jié)點在測試序列中的位置，平均提升幅度為55.38%。在獎勵函數(shù)中，引入節(jié)點重要值可以有效地提升重要節(jié)點在測試序列中的位置，并且使用修正的節(jié)點重要值能夠有效提升魯棒性。

實驗3TOIR 與其他強化學習方法的性能比較。

圖8 展示了TOIR 訓練輪次的平均獎勵（ep_r）與OCplx 和SHO 的關(guān)系。由圖8 可以看出，在獎勵函數(shù)中融入節(jié)點重要值能夠有效提升半序列重要值，同時有效降低測試樁復雜度。這是因為TOIR采用基于掩碼序列的建模方式，只區(qū)分節(jié)點是否加入測試序列，代替了有序排列的編碼，大大減少了建模的冗余度，使得智能體的動作選擇僅與當前智能體所處狀態(tài)相關(guān)，而與之前的序列無關(guān)。另外，這種建模方式使得基于深度強化學習的模型能夠有效解決CITO 問題，因為智能體僅根據(jù)0-1 序列形成狀態(tài)到動作的映射策略，并根據(jù)獎勵更新策略不斷優(yōu)化自身策略。通過在獎勵函數(shù)中融入測試樁復雜度和節(jié)點重要值的因素使得TOIR 達到優(yōu)化目標，即測試樁復雜度低且重要節(jié)點優(yōu)先被測試。綜上所述，TOIR 能夠端到端更新集成測試策略，無需其他的編碼計算過程，更加簡單直觀，有效提升了集成測試序列的性能。

圖8 評測指標與平均獎勵的示意圖Fig.8 Schematic diagram of evaluation indicators and mean rewards

圖9 展示了隨著集成測試的開展，序列與其重要值之間的關(guān)系，其中，虛線與測試序列重要值的交點表示半序列重要值，指標（OCplx 和SHO）與對數(shù)（ep_r）分別代表整體測試樁復雜度和半序列重要值與獎勵的趨勢。當測試序列的重要值在初期越高表明重要的節(jié)點越優(yōu)先被測試，說明整個測試序列結(jié)果越優(yōu)，即前半序列的斜率越大越好。由圖9 中TOIR 與BCN 的對比可以看出：在Atm、Ant、Daisy、Email-spl 系統(tǒng)上，TOIR 較BCN 的半序列重要值明顯增加；在Spm、Dns、JaConTeBe 系統(tǒng)上，TOIR 略微領(lǐng)先或是持平；在test 系統(tǒng)上，BCN 領(lǐng)先，原因是在test 系統(tǒng)中引入了新的測試樁，犧牲了測試樁復雜度提升關(guān)鍵類的優(yōu)先級。整體而言，TOIR 在50%的被測系統(tǒng)中優(yōu)化了測試序列，在37.5%的被測系統(tǒng)中無明顯提升，在12.5%的被測系統(tǒng)中出現(xiàn)了退化。此外，TOIR 在Atm、Ant、Spm、Email-spl、JaConTeBe系統(tǒng)中，前半序列的重要值斜率明顯高于后半序列，BCN 在test、Ant、Spm、JaConTeBe 系統(tǒng)中，前半序列的重要值斜率明顯高于后半序列。這說明TOIR 可以有效地提升重要節(jié)點在測試序列中的位置。綜上所述，對于半序列重要值和前半序列斜率而言，TOIR 整體優(yōu)于BCN。

圖9 測試序列重要值Fig.9 Test order importance value

選取具有代表性的基于圖論BCN［28］、基于遺傳算法（GA）［8］、基于隨機交互算法（RIA）［29］的基線方法，以驗證TOIR 的性能，如表4 所示。由表4 可以看出：RIA 在Ant 和Atm 系統(tǒng)的實驗中表現(xiàn)最優(yōu)；TO 和BCN 在Daisy 系統(tǒng)中均達到最小值；TO 和TOIR 在Spm 系統(tǒng)中均為最優(yōu)；TO 在Email-spl、Dns 和JaConTeBe 系統(tǒng)中是最優(yōu)的。由此可見：TO 在與其他方法的對比中，在75%的系統(tǒng)中獲勝，證明了其可以有效地降低整體測試樁度；TOIR 較BCN 在test、Ant、Atm、Spm 系統(tǒng)中獲勝，在Daisy、Email-spl、Dns、JaConTeBe 系統(tǒng)中稍遜于BCN。

表4 TOIR 與基線方法的性能對比Table 4 Performance comparison among TOIR and the baseline methods

另外，繪制3 種方法關(guān)于整體測試樁復雜度和半序列重要值的箱型圖，如圖10 所示。由圖10 可以看出：TOIR 較TO 雖然犧牲了一定的測試代價，但是關(guān)鍵類的優(yōu)先級得到了大幅提升；TOIR 較BCN 的半序列重要值維持在更高的水平上，整體測試樁復雜度更加緊湊，綜合性能優(yōu)于BCN。

圖10 整體測試樁復雜度和半序列重要值的箱型圖Fig.10 Box chart of OCplx and SHO

綜上所述，TOIR 能夠收斂于最佳狀態(tài)，并且性能優(yōu)于現(xiàn)有方法，可以在幾乎不增加測試樁復雜度甚至降低測試樁復雜度的前提下有效提升被測系統(tǒng)重要節(jié)點的優(yōu)先級，這在軟件測試的過程中具有重要意義。

5 結(jié)束語

現(xiàn)有面向CITO 的強化學習方法普遍存在以下問題：基于節(jié)點樹的狀態(tài)表示，冗余且狀態(tài)間的相關(guān)性較強，導致搜索效率降低，狀態(tài)空間規(guī)模大幅增加，不適用于大規(guī)模軟件系統(tǒng)；基于測試樁的評價指標單一且沒有考慮軟件系統(tǒng)具有復雜網(wǎng)絡特性，忽略了重要節(jié)點在實際測試中風險暴露的滯后性。為了解決上述問題，本文提出一種具有重要值加權(quán)獎勵的基于測試順序的強化學習方法，使用壓縮編碼的測試序列定義強化學習任務中的狀態(tài)，簡化強化學習訓練過程，并在獎勵函數(shù)的設計上融入了修正的節(jié)點重要值，提升關(guān)鍵節(jié)點的優(yōu)先級。實驗結(jié)果表明，該方法能夠有效降低測試樁復雜度，使得重要節(jié)點在測試序列中的位置平均提升55.38%，并且能夠適用于大規(guī)模軟件系統(tǒng)。下一步將根據(jù)靜態(tài)分析結(jié)果初始化深度強化學習模型參數(shù)，輔助智能體在訓練初期進行快速學習。