基于損失函數(shù)的單元測試用例自動化生成算法研究與實現(xiàn)

傅瑞華， 李 凡， 王俊峰

(四川大學(xué)計算機(jī)學(xué)院， 成都 610065)

1 引 言

軟件測試是軟件質(zhì)量保證的核心環(huán)節(jié)， 是軟件產(chǎn)品生命周期內(nèi)質(zhì)量保證不可缺少的有效措施.證據(jù)表明，目前完整的軟件測試過程最多可占項目開發(fā)總成本的40%[1]，而早期及時通過軟件測試可大大降低修復(fù)軟件生命周期中的缺陷的成本[2].但目前，仍有相當(dāng)多的軟件是依靠手工編寫測試用例來進(jìn)行軟件測試.這種人工方式需保證測試人員有較多經(jīng)驗和較高技術(shù)水平，且在有高質(zhì)量測試人員情況下依舊會花費較高的成本(時間、人力)，也并不能完全保證測試用例的高覆蓋率和軟件質(zhì)量.因此研究測試用例自動化生成技術(shù)成為了軟件開發(fā)行業(yè)發(fā)展的必然趨勢.

測試用例的自動構(gòu)建可視為一個優(yōu)化問題，即如何在生成最小數(shù)量的測試用例集合的標(biāo)準(zhǔn)下，盡可能覆蓋更多的目標(biāo)，并保證測試數(shù)據(jù)分布的平衡性，使得測試用例高有效.市面上目前已經(jīng)有較多的成熟工具如Logiscope、Load Runner、Web Stress[3]等，可用于軟件測試中測試用例的自動生成，但大多數(shù)仍然無法解決如何自動生成高質(zhì)量測試、如何使得測試用例全面覆蓋等自動化測試痛點問題，所以要實現(xiàn)真正意義上的自動生成測試用例，仍需投入大量研究及技術(shù)支持.

軟件測試方法可大類分為黑盒測試及白盒測試，前者注重在不清楚內(nèi)部結(jié)構(gòu)和細(xì)節(jié)的情況下驗證功能可用性；后者基于程序源碼內(nèi)部邏輯知識，并通過特定的測試覆蓋率標(biāo)準(zhǔn)如語句覆蓋率、分支覆蓋率等，來檢測編碼過程中存在的潛在錯誤[4].

根據(jù)不同的軟件測試方法，自動生成測試用例的常見算法可分為隨機(jī)測試方法、符號執(zhí)行方法、UML模型檢測法和基于元啟發(fā)式算法的測試用例自動生成方法等[5].李志博等[6]提出的優(yōu)化的固定候選集算法(Fixed Sized Candidate Set，F(xiàn)SCS)在傳統(tǒng)的隨機(jī)測試算法[7]中添加了自適應(yīng)方法，通過生成多個候選測試用例數(shù)據(jù)，計算每個候選數(shù)據(jù)與已執(zhí)行用例數(shù)據(jù)集中最近測試用例數(shù)據(jù)之間的距離，并選擇出距離最大的候選數(shù)據(jù)作為下一個執(zhí)行數(shù)據(jù)，從而使得測試用例數(shù)據(jù)盡可能均勻地在輸入空間內(nèi)分布.Xiao等[8]提出一種以程序階段特征為指導(dǎo)的新型符號技術(shù)用于測試用例的自動生成，把程序基本塊執(zhí)行次序劃分為不同的執(zhí)行階段，但此種符號執(zhí)行法易集中在局部代碼塊，導(dǎo)致其他部分的代碼無法被有效測試.Swain等[9]提出將UML行為模型轉(zhuǎn)換為圖形，通過測試場景和測試序列來自動生成測試用例的方法.Liu等[10]提出一種通過掃描帶有嵌套循環(huán)過程的源代碼來構(gòu)造程序?qū)幽Ｐ?，并將圖層模型轉(zhuǎn)換為擴(kuò)展的正則表達(dá)式，進(jìn)而獲得測試路徑的方法.但當(dāng)程序復(fù)雜度上升(特指循環(huán)嵌套)時，該方法會導(dǎo)致測試序列爆炸問題.

元啟發(fā)式測試用例自動生成算法是根據(jù)測試充分性標(biāo)準(zhǔn)自動生成最優(yōu)解測試用例集，包括粒子群優(yōu)化算法[11]、遺傳算法、模擬退火算法[12]、蟻群算法等[13]，其中遺傳算法應(yīng)用最為廣泛.Bao等[14]提出的改進(jìn)遺傳方法(Improved Adaptive Genetic Algorithm，IAGA)旨在每次迭代中根據(jù)個體相似度和適應(yīng)度值的差異，動態(tài)調(diào)整一些參數(shù)來提高早熟收斂方面的搜索性能.相比于其他算法，元啟發(fā)式算法可適用于更大規(guī)模及更高復(fù)雜度的空間，并能更敏捷地找到最優(yōu)解或近似最優(yōu)解[15].但由于算法受限于適應(yīng)度函數(shù)且依賴于初始種群，容易產(chǎn)生以下問題：算法時間復(fù)雜度過高、種群過早收斂、非全局最優(yōu)解以及局部最優(yōu)導(dǎo)致數(shù)據(jù)冗余.

為進(jìn)一步解決以上所述的元啟發(fā)式算法缺陷，并使得生成的測試用例在數(shù)量較少的情況下能夠覆蓋盡可能多的路徑，本文提出一種基于損失函數(shù)的白盒測試用例生成方法：在GA算法過程中實時判斷種群數(shù)據(jù)的分布并進(jìn)行動態(tài)調(diào)整，并根據(jù)分布情況自適應(yīng)調(diào)整交叉變異算子，同時通過改進(jìn)后的適應(yīng)度及精英策略評估函數(shù)來對種群進(jìn)行選擇，以保證每次迭代的初始輸入種群的有效性，最大程度構(gòu)建出高覆蓋低數(shù)量高有效的最優(yōu)解測試數(shù)據(jù)集.

2 相關(guān)概念

2.1 損失函數(shù)

在機(jī)器學(xué)習(xí)模型中，單個樣本的真實值與預(yù)測值的差值稱作損失，損失值越小表示模型越貼合真實場景.其中用于計算損失值的函數(shù)被稱作損失函數(shù)，其本質(zhì)是一個用于找到場景最優(yōu)解的目的函數(shù)，可被用于度量一個模型的好壞，所以損失函數(shù)是機(jī)器學(xué)習(xí)中檢驗?zāi)Ｐ徒Y(jié)構(gòu)風(fēng)險的重要組成部分.

構(gòu)建的模型能夠通過損失函數(shù)計算出的損失值，反向去傳播更新各參數(shù)，使得模型生成的預(yù)測值能夠更好地擬合真實值，從而判斷模型或者決策的好壞.當(dāng)損失值小于既定的閾值后，則可停止學(xué)習(xí)得到最優(yōu)模型.假設(shè)存在離散點(xi，yi)的集合，針對單一參數(shù)預(yù)測函數(shù)f(xi)=α1+α2xi，有平方誤差代價函數(shù)：

(1)

其中，N為總樣本數(shù)量；i表示第i個樣本.求解最優(yōu)值即為求解參數(shù)α1，α2，使得函數(shù)J值極小從而獲取最佳預(yù)測函數(shù)與最小誤差.

2.2 GA算法

遺傳算法已在多學(xué)科中被用作解決全局搜索優(yōu)化的方案，可形式化將該算法內(nèi)容用一個多元組進(jìn)行表示.

G=(C,F,O(α,β,γ),R(c,m,n),E)

(2)

表1 多元組符號含義

遺傳算法在每一次迭代中，通過適應(yīng)度函數(shù)選擇更優(yōu)的個體至下一代，再對種群進(jìn)行交叉或變異操作，從而產(chǎn)生新的種群.

使用遺傳算法實現(xiàn)測試用例的自動生成可描述為:在每輪迭代過程，遺傳算法使用當(dāng)前種群(即測試用例)來驅(qū)動被測程序的執(zhí)行，并以最大化程序路徑覆蓋率作為適應(yīng)性函數(shù)進(jìn)行計算，通過交叉變異等操作優(yōu)化有效性較低的測試用例數(shù)據(jù)，進(jìn)而產(chǎn)生下一代種群至循環(huán)結(jié)束.

2.3 動態(tài)符號化執(zhí)行

動態(tài)符號執(zhí)行在傳統(tǒng)符號執(zhí)行方法之上，讓具體值和符號執(zhí)行同時進(jìn)行[16].動態(tài)符號執(zhí)行技術(shù)在生成測試用例時使用程序變量的具體值來替換復(fù)雜表達(dá)式或數(shù)據(jù)結(jié)構(gòu)中的符號變量，通過簡化路徑條件自動生成更有效的測試用例，且具有較小的時間花銷[17].程序生成隨機(jī)數(shù)據(jù)進(jìn)行第一次執(zhí)行，并從當(dāng)前執(zhí)行路徑上的分支語句的謂詞中搜集所有符號約束，謂詞的定義如后式：P(x1,x2,…,xi)，其中xi為獨立的個體(表示不同事物或某種抽象概念)；P表示一種行為約束，刻畫出個體間的關(guān)系及性質(zhì).

之后對約束進(jìn)行修改生成新路徑的約束序列，并利用約束求解器求解出另一個可行的新輸入.通過輸入迭代產(chǎn)生變種輸入，從而觸發(fā)程序新狀態(tài)，發(fā)現(xiàn)所有可行路徑下的測試用例數(shù)據(jù).

3 算法概述

本文提出的單元測試用例自動化生成算法整體上需達(dá)成的目標(biāo)為：保證測試用例數(shù)據(jù)高覆蓋高有效，平均覆蓋率盡可能達(dá)到α(α>=95%).在測試停止標(biāo)準(zhǔn)中基于測試用例的原則下，非功能性測試用例覆蓋率達(dá)到或超過95%允許正常結(jié)束測試[18].

圖1 種群個體惡性傾斜示意圖

保證分布平衡，分散重復(fù)路徑分支下的冗余個體，使得迭代完成后各路徑之間的種群數(shù)量差值β<=5.防止收斂速度過快導(dǎo)致的早熟以及單路徑數(shù)據(jù)爆炸(如圖1)等問題缺陷.圖1中Bi為分支Li為語句，虛線框中的部分代表聚集了較多的種群個體，因此在迭代中測試重點會偏向根節(jié)點B1的右子樹路徑上，從而導(dǎo)致失衡，造成最終種群迭代的惡性結(jié)果效應(yīng).

3.1 測試用例自動生成模型框架

本文提出的單元測試用例自動化生成算法(LFGA)模型如圖2所示.整體方法中含有程序分析、GA優(yōu)化、最優(yōu)種群集合評估等主要模塊，對初始測試程序進(jìn)行插樁測試，并于中間過程引入損失函數(shù)驗證，通過及時判斷迭代各種群個體是否符合分支預(yù)期，動態(tài)根據(jù)路徑前序分支覆蓋情況調(diào)整種群在程序路徑樹的分布，執(zhí)行時無需過度依賴于初始種群，最后以適當(dāng)收斂速度及迭代次數(shù)來確定最優(yōu)數(shù)據(jù)集，增強(qiáng)此種問題場景下通用模型的整體魯棒性及種群個體耦合依賴性，并以此可推斷至較為復(fù)雜軟件的用例生成.

圖2 基于損失函數(shù)的測試用例生成模型Fig.2 Test case generation model based on loss function

3.2 程序分析

模型中程序分析采用靜態(tài)預(yù)分析方式，抽取程序片段中的關(guān)鍵信息包括分支節(jié)點、參數(shù)集合、輸入域范圍等，以Java語言為例，借助ASTParser類遍歷形成DOT類型文件數(shù)據(jù)，再利用正則從節(jié)點語句中獲取具體的輸入域范圍，具體DOT數(shù)據(jù)類型如表2所示.

表2 DOT文件數(shù)據(jù)結(jié)構(gòu)字段

生成的dot文件同時包含了各個id之間的指向信息，能夠表示各分支之間的層級關(guān)系，訪問者根據(jù)dot文件數(shù)據(jù)中的節(jié)點語句信息可得到分支集合T={t1,t2,...,tn}.給定路徑集合P={p1,p2,...,pn}，其中pi∈T，且pi代表的子集沒有重復(fù)，所有子集的并集涵蓋程序整個分支集合;若存在pm∈pn則僅保留最長路徑子集.

將所有路徑信息進(jìn)行優(yōu)化后，執(zhí)行統(tǒng)一插樁，把測試數(shù)據(jù)集映射至路徑檢測及定義域初值數(shù)據(jù)集.路徑檢測數(shù)據(jù)集合在分支損失函數(shù)驗證階段將被用于控制種群在各路徑上的分布，定義域初始隨機(jī)集合將用于種群(測試用例)初始值的生成.

3.3 初值隨機(jī)生成優(yōu)化

關(guān)于種群迭代演化的測試，前期輸入域有效性間接性確定了后期迭代時間長短及收斂速度的快慢.之前經(jīng)過對代碼片段的靜態(tài)分析并確定了類的分支行為，在DOT數(shù)據(jù)集合上進(jìn)行二次正則精簡來獲取每一個分支中可能存在的參考值以及其對應(yīng)范圍符號，包括：>、<、=、&、！等，然后以預(yù)設(shè)數(shù)量的種群個體數(shù)在變量參考范圍內(nèi)隨機(jī)生成初始種群，組成由范圍內(nèi)隨機(jī)測試用例組成的測試套件，再用于之后迭代.

由于并非所有程度控制條件中含有明確變量信息(如:無數(shù)值僅有等式約束關(guān)系)，因此考慮符號化執(zhí)行思想，把輸入變?yōu)榉栔祦淼玫阶屘囟ùa片段區(qū)域執(zhí)行的輸入組合值或關(guān)系，以圖3為例，獲取路徑分支truefalse序列的約束關(guān)系，，根據(jù)執(zhí)行樹左右子樹進(jìn)行初值的等式約束關(guān)系集取值，從而適應(yīng)于無明確參考值下的種群初值生成.改分支集合序列T中每項為ti-0和ti-1，則ti-0代表true，ti-1代表false，作為路徑集合的存儲信息.

圖3 執(zhí)行樹信息存儲示例Fig.3 Execution tree information store

獲取到各路徑下的參考值范圍或變量狀態(tài)關(guān)系后，將上述變量信息存儲至對應(yīng)分支的數(shù)據(jù)結(jié)構(gòu)中，根據(jù)取值范圍對各路徑設(shè)置相應(yīng)概率閾值，便于在分支損失函數(shù)中進(jìn)行分支碰撞檢測優(yōu)化.

3.4 分支損失函數(shù)驗證

在最優(yōu)種群集合評估模塊中，為確保數(shù)據(jù)集至少覆蓋一次決策點的每個條件的所有可能結(jié)果(即取真、取假分支)，本文提出一種通過分支損失函數(shù)實時調(diào)整后序種群分布的驗證算法，其中分支損失函數(shù)在流程中作為用于找到最優(yōu)解集合的目的函數(shù)，控制選擇及交叉變異方向，從而增強(qiáng)測試?yán)龜?shù)據(jù)之間的公平性、友好性，流程如圖4所示.

在進(jìn)行整體種群評估后開啟分支損失函數(shù)的驗證，貫穿于每代個體的選擇丟棄和后續(xù)變異的突變方向等，盡可能地去掉某分支條件下的冗余測試數(shù)據(jù)，主要損失函數(shù)的實現(xiàn)由以下兩部分構(gòu)成.

圖4 分支損失函數(shù)驗證流程Fig.4 Branch loss function verification process

第一項：用于迭代選擇過程中判斷個體累計是否符合分支覆蓋預(yù)期.由于前序步驟中進(jìn)行了正則切割及插樁等過程，程序能夠獲取存儲的分支數(shù)據(jù)結(jié)構(gòu)信息，包括分支id、分支所含變量范圍及關(guān)系、分支概率閾值等.當(dāng)進(jìn)入某分支的個體數(shù)占比超過設(shè)定的該分支概率閾值則選擇舍棄，重新隨機(jī)選取其他分支進(jìn)行參考值范圍內(nèi)的數(shù)據(jù)隨機(jī)生成以補位，再結(jié)合精英個體選擇策略下的剩余種群形成新一代種群數(shù)據(jù)的有效輸入;第二項：提供個體交叉變異的趨勢判斷.由于適應(yīng)度函數(shù)的設(shè)計易使測試數(shù)據(jù)后續(xù)匯集在已生成數(shù)據(jù)的路徑上(即概率閾值更大)，考慮在經(jīng)過選擇階段后，通過累計各路徑個體，選取數(shù)目相對較多和較少的分支種群集合進(jìn)行交叉變異.算法中的變量含義對應(yīng)關(guān)系如表3所示.

表3 算法變量含義對照表

整體算法思路過程偽代碼如算法1所示.

算法1分支損失函數(shù)驗證

1) procedure Branch Cost(，)

2) Pretreatment:T&P←dot類型數(shù)據(jù)

3) Initializa:PopList←Referencevaluerange

4) Evaluate: the primary population

5) whilei< maxGeneration do

6) Select:NewPopList←f(xi)評估

7) while in Function(CostBranch) life

circle do

8)PXover& PMutation: 自適應(yīng)改變

9) if reachedPopListend

10) end while

11) 使用JUnit計算數(shù)據(jù)覆蓋率

12) if test data optimal←cov(%) max

13) end while

14) 輸出最優(yōu)解集合

15) end procedure

3.5 自適應(yīng)算子設(shè)計

采取常規(guī)遺傳算法中的策略，交叉函數(shù)對選定的兩個父級中的基因進(jìn)行交換，變異函數(shù)實現(xiàn)采用的單點交叉.通常在覆蓋率高的測試用例數(shù)據(jù)上修改某一個參數(shù)值或用高覆蓋率測試用例中的某幾位參考數(shù)據(jù)替換前一階段新生成的測試用數(shù)據(jù)，往往能夠在適當(dāng)速度范圍內(nèi)加快收斂改善結(jié)果，有效加強(qiáng)進(jìn)化性能[19].

當(dāng)連續(xù)碰撞某分支次數(shù)累計達(dá)到設(shè)定閾值，認(rèn)為在此分支參考值范圍內(nèi)已經(jīng)設(shè)定了足夠的測試用例，為避免出現(xiàn)過度收斂導(dǎo)致分支不平衡現(xiàn)象，動態(tài)地調(diào)整交叉變異算子.根據(jù)測試數(shù)據(jù)累計分支碰撞閾值，動態(tài)改變交叉變異算子的取值.式(3)和式(4)分別表示變異和交叉算子的調(diào)整方式.

(3)

(4)

式中，fmax代表相對適應(yīng)度最大的個體；fi代表待變異個體(適應(yīng)度較小的測試用例)的相對適應(yīng)度；favg代表種群個體平均相對適應(yīng)度.在遺傳算法中Pc，Pm取值范圍一般為[0.25，0.99)及[0.001，0.1)[20]，此處公式中k1及k2、k3及k4，通過隨機(jī)函數(shù)分別取[0.25，0.99)及[0.001，0.1)區(qū)間內(nèi)的值.

相對適應(yīng)度越小的個體表示進(jìn)入其對應(yīng)分支的概率越大越容易進(jìn)入，相對較大的變異算子在此種情況下更能促進(jìn)進(jìn)入冗余分支測試數(shù)據(jù)的變異.

對于分支概率最大的情況下，fi必定大于favg，使得整體Pm增加，從而對應(yīng)個體變異的概率增加；對于進(jìn)入分支難的個體，應(yīng)使Pm變小，從而使這個個體更不容易變異順利進(jìn)入下一代.

3.6 GA優(yōu)化模塊

(1) 適應(yīng)度函數(shù)設(shè)計.根據(jù)個體分支覆蓋情況和所有種群分支覆蓋情況進(jìn)行個體的適應(yīng)度計算，每次進(jìn)行更改時需重新編譯代碼.越易覆蓋的路徑會有越多的測試數(shù)據(jù)集，適應(yīng)度函數(shù)見式(5).

(5)

其中，N代表種群待選擇個體總數(shù)；ui為路徑集合個體pi所含有的測試數(shù)據(jù)數(shù)目；umax為測試用例在pi路徑下達(dá)到理想平衡狀態(tài)下的個數(shù)，越易被覆蓋的路徑會有更多的測試數(shù)據(jù)集，對應(yīng)個體適應(yīng)度值越低，在擇優(yōu)選擇中表現(xiàn)為更劣勢個體.

(2) 精英策略設(shè)計.結(jié)合分支驗證機(jī)制之前，本文先采用輪盤賭個體選擇策略，將中間步驟得到的最優(yōu)解個體進(jìn)行保留.結(jié)合分支損失函數(shù)驗證后能在確保當(dāng)代種群中最佳成員組作為二代種群的初始有效輸入的條件下動態(tài)調(diào)整其余測試數(shù)據(jù)的平衡性，從而防止由遺傳算法過度收斂導(dǎo)致的數(shù)據(jù)極端不平衡.輪盤賭策略對優(yōu)劣個體的相對適應(yīng)度計算式如式(6).

rf(i)=f(i)/∑f(i)，i≤N

(6)

式中， ∑f(i)表示當(dāng)前適應(yīng)度的總和.個體相對適應(yīng)度rf(i)越高表示個體更優(yōu)良，將保留至分支損失函數(shù)執(zhí)行階段.

4 實驗與結(jié)果

本文實驗選擇了5種不同復(fù)雜度的被測程序來進(jìn)行所提出方法的評估，并與其他方法和工具進(jìn)行橫向?qū)Ρ葘嶒?，算法實現(xiàn)采用Intellij IDEA軟件環(huán)境，開源測試框架JUnit輔助進(jìn)行測試結(jié)果優(yōu)劣分析.實驗評估標(biāo)準(zhǔn)以回答以下兩個問題：Q1: 本文提出方法是否能夠優(yōu)化數(shù)據(jù)收斂結(jié)果，并提高總體覆蓋率？Q2: 與其他方法相比，本文提出方法是否能夠在相同規(guī)模的測試數(shù)據(jù)集合下，實現(xiàn)更高的覆蓋率結(jié)果？

4.1 實驗過程

實驗測試采用軟件測試中的經(jīng)典模型Triangle， Next Date， GCD， premium， decision[21]等作為被測程序來驗證所提出方法的可行性(如表4).

表4 測試模型信息

本文提出的方法記為LFGA，隨機(jī)算法記為RA，蟻群算法記為ACA，標(biāo)準(zhǔn)遺傳算法記為SGA，開源工具Evosuite中的改進(jìn)遺傳算法記為IGA.Evosuite[22]基于傳統(tǒng)GA算法，然后迭代地使用變異和交叉等遺傳算子來進(jìn)化.

通過使用不同的算法對上述5種待測程序模型進(jìn)行單元測試用例的自動生成，并通過Junit進(jìn)行測試用例數(shù)據(jù)的覆蓋率計算輸出及后續(xù)結(jié)果對比.實驗種群規(guī)模保持為50，最大迭代次數(shù)設(shè)上限500，自適應(yīng)遺傳操作中設(shè)置單點交叉概率上限0.9;變異概率上限0.1.實驗中使用的評估指標(biāo)是在預(yù)先確定的獨立運行次數(shù)上實現(xiàn)的平均覆蓋率.通常迭代停止機(jī)制的判斷方式為兩種:人為設(shè)定及數(shù)據(jù)收斂趨勢穩(wěn)定或陷入局部最優(yōu)解.

4.2 實驗結(jié)果

通過使用不同算法對同種程序測試模型進(jìn)行測試，生成數(shù)據(jù)的路徑覆蓋率結(jié)果數(shù)據(jù)如圖5所示，其中cov表示多次實驗累計下的覆蓋率結(jié)果均值.

表5為在每種模型經(jīng)過40輪次實驗后，程序輸出分布結(jié)果趨勢穩(wěn)定情況下的平均迭代次數(shù)(去除最優(yōu)及最壞結(jié)果以盡量降低偶然事件誤差).注:程序輸出的最優(yōu)結(jié)果不代表數(shù)據(jù)一定可用，僅可通過此數(shù)據(jù)判斷種群收斂情況.

表5 程序穩(wěn)定解下的遺傳代數(shù)

圖5 不同方法下的覆蓋率結(jié)果Fig.5 Coverage results under different methods

為了驗證被測程序的測試數(shù)據(jù)生成在改進(jìn)方法下的有效性，繪制了在本文所提出的思路下，種群數(shù)據(jù)的收斂趨勢(以Triangle為例)，如圖6所示，并以標(biāo)準(zhǔn)遺傳算法SGA下的過程中種群數(shù)據(jù)分布趨勢作為對照.圖中橫坐標(biāo)表示種群的迭代次數(shù)，縱坐標(biāo)表示為種群個數(shù)，其中每一條折線表示：一條路徑分支上的種群個數(shù)在迭代過程中的變化.

以含有4條分支路徑的Triangle程序為例，兩幅圖中從上到下的折線依次代表4條路徑上種群數(shù)量的變化.經(jīng)過20余次迭代后，在圖7的SGA算法中，每條路徑上的種群數(shù)量變化波動較大且無明顯收斂趨勢；而在圖6的LFGA算法中，每條路徑上的種群數(shù)量變化趨于平緩，且各路徑之間的分布的種群數(shù)量差值也呈現(xiàn)越來越小的趨勢.

圖6 LFGA種群收斂趨勢(以Triangle為例)Fig.6 Convergence trend of LFGA population (take Triangle as an example)

圖7 SGA種群分布圖(以Triangle為例)Fig.7 SGA population distribution trend (take Triangle as an example)

4.3 數(shù)據(jù)分析

根據(jù)實驗結(jié)果，結(jié)合第4節(jié)開篇，Q1和Q2數(shù)據(jù)分析情況如下.Q1:從表5展現(xiàn)的數(shù)據(jù)中可看出傳統(tǒng)方式生成數(shù)據(jù)雖然經(jīng)過較少的迭代總數(shù)，但測試數(shù)據(jù)可用性遠(yuǎn)遠(yuǎn)低于本文提出的方法，說明傳統(tǒng)算法使得種群數(shù)據(jù)過快收斂或陷入局部最優(yōu)中，從而通過本文中的分支損失函數(shù)驗證方式，能夠較好地讓種群數(shù)據(jù)分布得到有效的篩選，并通過圖5生成測試數(shù)據(jù)的路徑分布圖可看出，整體數(shù)據(jù)以適當(dāng)速度進(jìn)行較穩(wěn)定的收斂，最終達(dá)成最優(yōu)解較均勻覆蓋目標(biāo)路徑目標(biāo).Q2: 橫向?qū)Ρ确绞较氯绫?數(shù)據(jù)，本文方法生成數(shù)據(jù)對于幾個測試程序來講生成了較好的覆蓋率且高于SGA算法，數(shù)據(jù)可用性更高，同時Evosuite開源工具數(shù)據(jù)覆蓋率比較穩(wěn)定可作為本文方法參考目標(biāo)覆蓋率，LFGA算法中的覆蓋率與Evosuite數(shù)據(jù)覆蓋率也更為接近，說明文本所提出損失函數(shù)方法適用于測試數(shù)據(jù)的自動生成.

5 結(jié) 論

本文提出了一種基于損失函數(shù)的方法，目的是通過判斷算法過程中平衡性變化，改進(jìn)種群適應(yīng)度及精英策略評估方式，并利用分支信息優(yōu)化自適應(yīng)交叉變異算子，自動完成數(shù)據(jù)收斂過程，生成最小高覆蓋有效測試用例集.經(jīng)過大量實驗及數(shù)據(jù)表明，本文方法能夠有效收斂種群，增強(qiáng)算法全局尋優(yōu)能力，并較好解決初值依賴、收斂早熟、局部尋優(yōu)能力滯后等傳統(tǒng)缺陷，盡可能地提升搜索效率及數(shù)據(jù)有效率，將測試覆蓋度達(dá)到一個滿意的值，對快速生成滿足測試要求的數(shù)據(jù)有著重要意義.由于本文所提算法能夠通過判斷用例數(shù)據(jù)分布情況來自動完成數(shù)據(jù)收斂的過程，后續(xù)引入神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練是值得嘗試和研究的.