面向Web服務器端敏感路徑的客戶端擴展有限狀態機測試生成

趙瑞蓮， 郭小紅， 王微微， 尚穎

(北京化工大學 信息科學與技術學院, 北京 100029)

隨著互聯網普及與快速發展，Web應用已成為人們生活中不可或缺的一部分。但Web應用極易受到攻擊。因此，對Web應用進行有效的安全測試極為重要。

目前，關于Web應用安全測試的研究主要針對客戶端模型或服務器端代碼，多以模型自身的狀態、遷移覆蓋為目標，探討其測試用例自動生成[1-2]。繆淮扣等[3]設計了一個基于模型的Web應用程序測試系統，以FSM作為被測Web應用程序的形式化測試模型；Schur等[4]從商業Web應用程序中挖掘用戶行為模型，并通過分析用戶行為模式建立模型，然后利用模型進行回歸測試用例生成；趙瑞蓮等[5]提出了基于用戶軌跡的Web客戶端擴展有限狀態機建模方法，通過對Web應用客戶端源代碼進行插裝，在用戶動態執行Web應用過程中獲取用戶的行為軌跡，利用用戶行為軌跡建立Web應用的擴展有限狀態機模型。Alshahwan等[6]將搜索算法應用于Web應用程序測試中, 隨后更多的研究者嘗試采用包括遺傳算法、禁忌搜索算法、模擬退火算法等在內的啟發式搜索算法來解決擴展有限狀態機測試數據生成問題[7-9]。Jan等[10]針對XML注入漏洞，利用遺傳算法實現測試用例的自動生成，該方法受限于已有的惡意輸入。研究者針對PHP Web應用程序的XSS漏洞，給出了以遺傳算法為主的測試用例生成方法[11-13]。通常一種算法只能在某一方面表現出較好的性能。混合搜索Memetic算法[14-15]則能通過將多種搜索算法有機結合起來，實現算法性能的進一步提高。

為此，本文將Web應用客戶端擴展有限狀態機模型的測試用例生成與服務器端的敏感路徑覆蓋結合起來，以服務器端安全脆弱點敏感路徑覆蓋為目標，利用Memetic演化算法將全局搜索的高效性和局部搜索的精準性相結合，實現客戶端擴展有限狀態機模型的測試用例自動生成，為Web應用軟件安全測試提供一種新的、有效的解決途徑。

基于擴展有限狀態機模型生成的抽象測試用例不能在Web應用中直接執行，需轉為驅動Web應用執行的測試腳本。若對每一個抽象測試用例編寫測試腳本或借助工具錄制測試腳本，將增加測試成本，降低測試效率。因此，測試腳本的自動生成是本文研究的另一個關鍵問題。Selenium是一個具有豐富應用程序編程接口的Web測試工具，可以在瀏覽器上模擬用戶操作。本文利用Selenium生成測試腳本，即通過分析提取擴展有限狀態機模型遷移的特征，根據特征信息對遷移進行聚類，再依據Selenium語法規范及映射規則，將聚類結果轉為可執行的測試腳本，形成遷移腳本庫，為抽象測試用例的可執行化提供服務。

1 面向Web服務器端敏感路徑的客戶端擴展有限狀態機測試生成方法

1.1 基本概念

面向Web服務器端敏感路徑的客戶端擴展有限狀態機測試生成涉及的基本概念定義如下：

定義1Web服務器端敏感路徑。假設程序P的一條語句執行序列為，若語句s1可接收外部輸入數據，語句sn為關鍵操作語句，如：訪問數據庫語句、輸出語句等，且語句s2到sn-1都不是安全驗證與過濾機制語句，則稱語句序列為程序P的一條敏感路徑，s1稱為源點(source)，sn為脆弱敏感點(sink)。

定義2Web客戶端擴展有限狀態機模型。用來表征Web應用客戶端行為的擴展有限狀態機模型，其狀態和遷移含義如下：

狀態s定義為Web應用軟件網頁的URL地址及其當前的DOM結構。

遷移t定義為Web應用軟件網頁地址或DOM結構發生改變的過程，用一個五元組〈Src(t)，Tgt(t)，Event(t)，Cond(t)，Action(t)〉表示，表示遷移t在狀態Src(t)下，若事件Event(t) 觸發，且遷移條件Cond(t) 滿足，則引發操作Action(t)，并將狀態轉換到Tgt(t)狀態。其中，Event(t)對應可驅動客戶端代碼執行，改變當前網頁的DOM結構的事件，包含事件的類型(Etype)、事件綁定的DOM元素、該DOM元素的定位方式(DL)及事件上的輸入參數(CIN)和參數的定位方式(CDL)等信息；Cond(t)對應事件處理函數中涉及的謂詞條件；Action(t)對應事件處理函數的參數變化及服務器端返回的消息。

定義3Selenium原子操作。原子操作指不可再分的最小Selenium語法規范，可用三元組表示，其中Cmd表示一個GUI操作命令，如點擊；Target是Cmd的操作對象；若Cmd未輸入類命令，Value用來表示接收的用戶輸入數據，若是非輸入類命令，則Value為空。

一個遷移表示用戶對Web應用的一次交互，由一個或由幾個操作組成。如一個交互可能是用戶的1次登錄操作，該交互包括輸入用戶名、密碼和點擊登錄按鈕3個子操作。若只觸發輸入操作而不觸發點擊操作，則不會引發Web應用的響應，該交互不能作為一個遷移，只有能引發Web應用響應的交互，才能作為遷移。因此，遷移可由多個Selenium原子操作組成。例如，遷移t(user, pwd)為用戶的1次登錄操作，由輸入用戶名、輸入密碼和點擊登錄3個Selenium原子操作組成，即、、。

1.2 面向Web服務器端敏感路徑的客戶端擴展有限狀態機測試生成

面向Web服務器端敏感路徑的客戶端擴展有限狀態機測試生成，是從客戶端和服務器端2個方面著手，進行Web應用安全測試用例自動生成的研究，其整體框架如圖1所示，主要包含2部分:1)基于服務器端敏感路徑的擴展有限狀態機測試用例集Memetic演化生成，2)基于Selenium的測試腳本自動構建。擴展有限狀態機測試用例集Memetic演化生成是本文的核心。針對構建的Web應用客戶端擴展有限狀態機模型，以服務器端敏感路徑覆蓋為目標，利用Memetic演化算法，實現Web應用客戶端擴展有限狀態機測試用例集的自動生成。針對擴展有限狀態機模型測試用例不可直接執行問題，本文通過提取擴展有限狀態機模型中遷移信息特征，進行聚類，根據聚類結果為每一類遷移構建測試腳本，形成遷移腳本庫，為抽象測試用例轉化為可執行的測試腳本提供支持。

圖1 面向Web服務器端敏感路徑的客戶端擴展有限狀態機測試用例生成方法框架Fig.1 The overview of server-side sensitive path coverage-oriented client-side EFSM test case generation

1.2.1 基于服務器端敏感路徑的EFSM測試用例集Memetic演化生成

由Web客戶端發出請求，服務器端響應處理的特性可知，Web服務器端的一條敏感路徑對應客戶端的一次請求操作，而客戶端擴展有限狀態機模型上的一個遷移表示客戶端的一次請求操作。因此，Web服務器上的一條敏感路徑對應客戶端擴展有限狀態機模型的一個遷移。所以，若要覆蓋服務器端的某條敏感路徑，則需要覆蓋該敏感路徑對應的遷移。此外，外部輸入數據通常是通過POST、GET等請求方法與事件一起提交Web服務器處理，敏感路徑源點是接收外部輸入數據的語句，由此該遷移事件對應于該敏感路徑源點，覆蓋該遷移即可覆蓋了該敏感路徑源點。基于Web客戶端構建的擴展有限狀態機模型，其遷移上謂詞條件只涉及客戶端觸發事件的謂詞條件，沒有包含服務器端敏感路徑上的謂詞條件。所以，擴展有限狀態機遷移序列覆蓋敏感路徑對應的遷移，只能保證該序列覆蓋敏感路徑的源點，不一定能完全覆蓋該敏感路徑。因此，在覆蓋敏感路徑的源點后，需要調整遷移序列上的測試輸入，使其能夠覆蓋敏感路徑。

綜上，為覆蓋服務器端的敏感路徑，在生成Web客戶端擴展有限狀態機測試用例時，可通過全局搜索大幅地調整遷移序列，使之能覆蓋對應敏感路徑源點的遷移，然后通過局部搜索調整遷移序列上的測試輸入，生成能覆蓋敏感路徑的測試用例。此過程中，本文將敏感路徑的實時覆蓋信息作為搜索的啟發信息，來指導擴展有限狀態機模型測試用例的自動生成。因此，本文將遺傳算法(genetic algorithm,GA)和模擬退火算法(simulated annealing algorithm,SAA)有機結合，利用GA實現全局搜索生成覆蓋敏感路徑源點的測試用例，以SA作為局部搜索，對GA生成的測試用例進行校正。2種搜索算法結合使用，直到生成覆蓋敏感路徑集的測試用例集。演化流程如圖2所示。在擴展有限狀態機模型上，隨機生成若干條遷移序列及其測試輸入，構造初始種群。因從擴展有限狀態機模型生成的測試用例是抽象的，所以需對每一個個體生成相應的測試腳本，通過執行測試腳本實現抽象測試用例的執行。

圖2 EFSM測試用例集Memetic演化流程Fig.2 The process of Memetic evolution

同時，服務器端的插樁程序記錄各條敏感路徑的覆蓋情況，通過提取覆蓋信息可計算個體對各條敏感路徑的覆蓋程度f，并構造種群對敏感路徑集的評估矩陣M，獲取種群對所有敏感路徑源點的覆蓋情況。若所有敏感路徑的源點都被覆蓋，則敏感路徑源點的覆蓋標志cover_flag為True，否則為False。

在迭代過程中，當種群未能覆蓋所有敏感路徑的源點時，應用GA實現全局搜索，即根據適應度值選擇個體進行交叉變異操作以產生新個體。遺傳操作產生的所有新個體與當前種群一起參與種群的更新。在更新過程中，若某個個體覆蓋新的敏感路徑或新的敏感路徑的源點，則該個體被添加到測試用例集中。同時，該個體所覆蓋的敏感路徑從敏感路徑集中剔除，后續演化生成只針對未被覆蓋的敏感路徑。重復上述過程，直到覆蓋所有敏感路徑的源點或達到最大迭代次數。

此時，可能會出現以下3種情況：1)測試用例集不僅覆蓋到所有敏感路徑的源點，而且完全覆蓋了敏感路徑集，則測試用例集生成結束；2) 測試用例集僅能覆蓋敏感路徑的源點而未能完全覆蓋敏感路徑，啟動SA進行局部搜索；3) 達到最大迭代次數但仍有敏感路徑未被覆蓋，重新啟動基于GA的測試生成過程。

在SA局部搜索階段，對每一條未被完全覆蓋的敏感路徑，從GA生成的測試用例集中選出所有對該敏感路徑覆蓋程度f在(0,1]之間的個體(f越小，個體對路徑的覆蓋程度越高)，并按f值從小到大排序構成候選集。然后對f最小的候選個體利用SA搜索生成覆蓋該敏感路徑的測試數據。若達到終止溫度，仍沒有找到符合要求的數據，則依次對下一候選個體進行局部搜索，直到該敏感路徑被完全覆蓋或所有候選個體都不能生成測試輸入使其完全覆蓋該敏感路徑，則考慮下一條未被完全覆蓋的敏感路徑。若演化搜索達到最大迭代次數仍未能完全覆蓋所有敏感路徑，則SA搜索結束。

1) 個體表示。

基于Web客戶端EFSM模型產生的測試用例包括遷移序列及序列上的測試數據。本文個體是一個測試用例，因此，也由2個部分組成，都采用字符編碼。

2) 個體覆蓋敏感路徑的評價指標。

根據個體執行對敏感路徑的覆蓋信息，采用通用的approach_level和branch_distance來計算當前個體對敏感路徑的覆蓋程度fit。fit值越小，說明當前個體對敏感路徑的覆蓋程度越高。當fit=0時，說明敏感路徑完全被覆蓋。

fit=approach_level+branch_distance

(1)

f=Normalized(fit)

(2)

式中：approach_level用來衡量當前個體執行路徑與目標路徑之間的距離；branch_distance用來衡量當前個體執行路徑與目標路徑不同時，第1個不同分支處謂詞條件從假變為真的距離。本文根據變量類型的不同采用不同的計算方法，即對于謂詞E1opE2(op是關系運算符)，若E1、E2是數值型變量，分支距離為distance(a,b)=|a-b|；若E1、E2是字符串型變量，分支距離為2個字符串間的編輯距離。式(2)對fit進行歸一化處理，使fit在[0,1]范圍內。

3)評估矩陣M。

矩陣M記錄各個個體對所有敏感路徑的覆蓋程度值f。搜索初始默認敏感路徑都未被覆蓋，其f置為2。當個體到達某一條敏感路徑的源點時，計算該個體對該敏感路徑的覆蓋程度，并修改M中該路徑的f值。從M的行可以得到某一個體對所有敏感路徑的覆蓋情況，從M的列可以得到所有個體對某一條敏感路徑的覆蓋情況。

p1p2p3…pk

4) 全局搜索適應度函數。

Memetic演化搜索的目標是生成能覆蓋所有敏感路徑的個體集合，全局搜索的目標是生成能覆蓋所有敏感路徑源點的個體集合，演化搜索的目標包含全局搜索的目標。因此，可將個體完全覆蓋的敏感路徑數作為全局適應度值來指導整個種群的進化。個體覆蓋的敏感路徑數越多，越難再進化出覆蓋其他敏感路徑的個體，且極有可能在進化過程中失去原本具有的優良基因片段。因此，本文優先挑選覆蓋敏感路徑數量少的遷移序列參與進化操作。對于那些覆蓋敏感路徑數的個體則加入最終測試集，同時，被覆蓋的敏感路徑從目標路徑集中剔除。f=0表示個體能完全覆蓋某敏感路徑，Count(f=0)是此個體完全覆蓋的敏感路徑的數量。若Count(f=0)為0，則表明該個體未完全覆蓋任何敏感路徑，f值越小，說明該個體越逼近某敏感路徑。因此，全局適應度值Fglobal設置為：

Fglobal越少，個體覆蓋的敏感路徑數越少或越逼近敏感路徑，此個體越好。

5)局部搜索適應度函數。

局部搜索的目標是尋找能完全覆蓋敏感路徑的測試數據，因此采用式(2)的f值進行個體評估，即局部搜索的適應度函數flocal為f。

測試用例集Memetic演化生成算法輸入為Web客戶端擴展有限狀態機模型，敏感路徑集P(p1,p2,…,pk)；輸出為覆蓋服務器端敏感路徑的測試用例集TS，描述為：

pop=Generate-Initial-Population(EFSM，N)

//隨機生成初始種群

while iteration<=max and | Listuncover_path|!=0

M=Executor(pop)//執行個體，得到覆蓋矩陣M

cover_flag=setFlag(M,P)

//標記敏感路徑源點是否全部覆蓋

if cover_flag=True then

//pop覆蓋所有敏感路徑源點，局部搜索

if | Listuncover_path|=0 then return TS=pop

//覆蓋了所有敏感路徑，返回生成結果

else

for eachpin Listuncover_pathdo{

Ind=Local-SA-Search(pop，M，p)

//調整個體數據以完全覆蓋敏感路徑

pop=Update_Individual(pop, Ind)

until | Listuncover_path|=0 return TS=pop

else

//pop未覆蓋所有敏感路徑源點，全局搜索

Fglobal=Global_fitness_Evaluation(pop，M)

Listuncover_path=getUncoverPath(M,P(p1,p2,…,pk))

while size(NewInds)

Indi,Indj=Select-Operator (pop,Fglobal)

Indi,Indj=Crossover-Operator(pc,Indi,Indj)

Indi,Indj=Mutation-Operator(pm,Indi,Indj)

NewInds←Indi，Indj

end while

for eachIjin NewInds do

if (isfeasible(Ij)) then NewIndfeasible←Ij

M=M∪Executor(NewIndfeasible)

pop=Elite_Update (NewIndfeasible, pop,Fglobal)

iteration++

end while

1.2.2 基于Selenium的測試腳本自動構建

一個遷移的測試腳本不僅應能模擬客戶端的用戶操作，還應能處理服務器端的反饋信息，如提示、確認彈框等。這些操作都反映在遷移的Event(t)和Action(t)信息中，直接影響到測試腳本需要哪些Selenium指令。因此，本文根據Event(t)和Action(t)信息粗粒度的將遷移劃分為4類，如表1所示。例如，若Event(t)上有輸入變量，則在生成測試腳本時，需要生成輸入類Selenium指令；若Action(t)有彈窗的提示信息，則在生成測試腳本時，需要生成處理彈窗的Selenium指令。

表1 遷移的粗粒度分類Table 1 Coarse-grained classification of transition

另一方面，一個遷移代表的交互操作可由多個Selenium原子操作組成，基于Selenium原子操作可以生成完整的Selenium指令。因此，測試腳本構建可先通過分析提取擴展有限狀態機模型上所有遷移的特征；然后根據遷移特征聚類，結合粗粒度，確定映射規則，為每一類遷移構建對應的測試腳本，形成遷移腳本庫。

1) 遷移特征分析及提取。

對于2個遷移，當它們的事件類型、事件綁定的DOM元素的定位方式、事件上的輸入參數個數、參數的定位方式及引發的后續操作響應這5方面的信息一致時，這2個遷移具有相同的操作行為，可共用同一個遷移測試腳本。因此，選取以上信息作為遷移特征。

2) 遷移聚類。

聚類可以將操作行為相似的遷移分為一類，可以共用一段測試腳本，因此，不需要為每個遷移都寫一段測試腳本。遷移特征量化后的數據樣本是稀疏、離散的。與傳統聚類算法相比，譜聚類算法能在任意數據樣本空間上進行聚類并收斂于全局最優解，聚類效率高。因此，本文采用譜聚類算法進行遷移聚類。

相似度計算是聚類的關鍵。若將全部特征看成字符串采用常規的距離公式(如編輯距離)進行計算，則極有可能因模糊特征本身的意義而導致分類的準確程度降低。例如按照的格式，3個遷移Ti，Tj和Tk的特征信息分別為Ti=，Tj=，Tk=。若采用編輯距離計算，則遷移Ti、Tj和Tk兩兩之間的編輯距離值均為1，導致聚類時3個需要不同測試腳本的遷移會被分為同一類。

為此，本文設計如下公式來計算遷移特征間的相似程度S(Ti,Tj)：

S(Ti,Tj)=

(4)

式中:S(Ti)表示遷移Ti的特征，是由表示Etype、DL、Action、CDL特征信息構成的字符串，TL是S(Ti)與S(Tj)的字符串總長，LCS表示2個字符串的最長公共子串的長度。

當2個遷移的輸入參數個數CIN不同時，這2個遷移對應的Selenium原子操作個數也不同，S(Ti,Tj)=0；反之，通過特征字符串的最長公共字串來計算2個遷移之間的相似度。當2個遷移的特征字符串沒有公共子串時，二者相似程度為0；當2個遷移的特征字符串完全一樣時，二者的相似程度為1。根據相似度公式構建遷移之間的相似矩陣S，用于譜聚類算法，可得到聚類結果。

3) 測試腳本自動生成方法。

測試腳本自動生成的映射規則包含2部分：第1層是粗粒度的，根據遷移的T.CIN和T.Action信息確定要調用的Selenium指令；第2層是細粒度的，將遷移的特征信息T.Etype、T.DL、T.CIN、T.CDL映射到Selenium原子操作命令語句的相關部分，通過字符串拼接的方式與Selenium的部分命令語句構成完整的Selenium命令，從而構成遷移測試腳本。測試腳本還需要引用一些Selenium模塊信息才能執行，也需將這部分信息寫入遷移測試腳本庫中。

測試腳本生成算法：輸入為遷移類別CResult，模板信息Template，每一類遷移的特征信息；輸出為：遷移測試腳本庫TransitionScriptLib；其中：Cstr,ACstr為不完整的selenium命令；DEstr為函數名標識(一類遷移腳本封裝在一個函數中)。描述如下：

TransitionScriptLib=?; ScriptContent=?;

Cstr=“a=driver.find_element_by”;

ACstr=“driver.switch_to_alert().accept()”;

DEstr=”def TFunction%s(driver，object)”;

for eachT∈CResultdo

TestScriptLib ←DEstr;

if T.Pnum=0 and T.Action ? AlertMessage//類別1

ScriptContent=Function C1();

if T.Pnum=0 and T.Action ? AlertMessage//類別2

ScriptContent=Function C2();

if T.Pnum!=0 and T.Action ? AlertMessage//類別3

ScriptContent=Function C3();

if T.Pnum!=0 and T.Action ? AlertMessage//類別4

ScriptContent=Function C4();

TransitionScriptLib ←Template， ScriptContent;

return TransitionScriptLib;

Function C1()

StrA=Cstr+T.DL;

StrB=“a.”+T.Etype;

ScriptContent ← StrA，StrB;

return ScriptContent

Function C2()

text=Function C1();

ScriptContent←text，ACstr;

Function C3()

for each i ∈T.CIN do

StrA=Cstr+T.DL(i);.send_keys(di));

StrB=Cstr+T.DL;

StrC=“a.”+T.Etype;

end for

ScriptContent ← StrA，StrB，StrC;

return ScriptContent

Function C4()

text=Function C3();

ScriptContent ←text，ACstr;

當2個遷移的輸入參數個數CIN不同時，這2個遷移對應的Selenium原子操作個數也不同，S(Ti,Tj)=0；反之，通過特征字符串的最長公共字串來計算2個遷移之間的相似度。當2個遷移的特征字符串沒有公共子串時，二者相似程度為0；當2個遷移的特征字符串完全一樣時，二者的相似程度為1。根據相似度公式構建遷移之間的相似矩陣S，用于譜聚類算法，可得到聚類結果。

3) 測試腳本自動生成方法

測試腳本自動生成的映射規則包含2部分：第1層是粗粒度的，根據遷移的T.CIN和T.Action信息確定要調用的Selenium指令；第2層是細粒度的，將遷移的特征信息T.Etype、T.DL、T.CIN、T.CDL映射到Selenium原子操作命令語句的相關部分，通過字符串拼接的方式與Selenium的部分命令語句構成完整的Selenium命令，從而構成遷移測試腳本。測試腳本還需要引用一些Selenium模塊信息才能執行，也需將這部分信息寫入遷移測試腳本庫中。測試腳本生成算法如算法2所示。

2 實驗及結果分析

為評估所提方法的有效性，本文通過以下3個問題進行實驗研究。

RQ1:遷移測試腳本庫構建方法是否可行？

RQ2:本文方法在Web應用程序的測試用例生成中的效果如何？

RQ3:本文方法與其他方法相比測試生成的效率如何？

本文以開源Web應用SchoolMate、Webchess和FAQforge作為實驗對象，相關信息見表2、表3。

表2 實驗程序Table 2 Web applications of under test

表3 實驗程序的模型及敏感路徑信息Table 3 Information for client-side EFSM model

2.1 測試腳本自動構建可行性驗證

遷移聚類的準確程度直接影響得到生成的測試腳本是否有效，而遷移聚類的核心是遷移之間的相似度性度量。為回答RQ1，本實驗以手工統計結果為基準，比較不同相似度的譜聚類精確度Acluster。Acluster為能正確分類的遷移數量(#CCTrans)除以遷移總數。本文與使用較為廣泛的編輯距離進行對比實驗，聚類精度結果如表4所示。

表4 基于不同相似度公式的聚類精度結果Table 4 Cluster accuracy for two similarity formulas

結果表明，采用本文相似度(SF-our)的譜聚類結果與基準結果相同，并且明顯優于采用編輯距離(SF-edit)的譜聚類結果。

2.2 面向Web服務器端敏感路徑的擴展有限狀態機測試用例生成的有效性驗證

為回答RQ2和RQ3，本文方法(MyGA+MySA)與其他2種組合方法，即本文的遺傳算法與爬山算法(MyGA+HC)，傳統遺傳算法與爬山算法(GA+HC)進行對比實驗。與本文所提GA相比，在以路徑作為覆蓋目標的優化問題上，傳統GA將目標敏感路徑與執行路徑之間的距離作為個體的適應值，并且不包含本文提到的更新策略。

實驗結果如表5所示，在3個被測程序中，GA+HC方法的全局搜索代數分別為334、361、28，大于另外2種使用MyGA的組合方法，說明MyGA能比GA更快地搜索到能覆蓋所有敏感路徑源點的個體集合。MyGA+MySA與MyGA+HC在SchoolMate和Webchess中全局搜索代數比較接近，分別為51、53和63、65，但在局部搜索上， MySA優于HC，說明MySA能比HC更快地搜索到完全覆蓋敏感路徑所需的測試數據。

表5 測試用例生成的搜索代數比較Table 5 Iterations comparison of test case generation

時間開銷由搜索個體和執行個體2部分時間組成。由表6可以看出，本文方法在需要執行的個體數量和時間開銷上顯著少于其他2種方法，并且個體執行時間對總時間的占比均為95%以上，說明實際搜索個體的時間很少。

表6 測試用例生成的時間開銷情況Table 6 The time cost of test case generation

由圖3可以看出，3種測試生成方法經過反復迭代最終都可以覆蓋Web應用中的所有敏感路徑。隨著搜索代數的增加，3種方法生成的個體集合對敏感路徑集的覆蓋率逐漸提高，其中MyGA+MySA和MyGA+HC上升較快，而本文方法(MyGA+MySA)能較早地覆蓋所有敏感路徑。

圖3 3種測試生成方法在3個被測程序搜索過程中對敏感路徑的覆蓋情況Fig.3 Coverage of sensitive paths by the three test generation methods during three search processes

由此可見，對于3個被測程序，本文方法在總搜索代數，執行個體數量及時間開銷上優于于其他兩種方法。此外，測試用例生成的結果表明本文方法可以生成滿足要求的測試用例，這意味著從客戶端行為模型擴展有限狀態機上生成的抽象測試用例可以轉換為測試腳本并執行，進一步驗證了本文所提出的測試腳本自動生成方法是可行和有效的。

3 結論

1)基于Selenium的測試腳本自動構建方法，能有效解決由模型生成的抽象測試用例不可直接執行問題。

2)Memetic進化搜索能從Web應用客戶端EFSM生成測試用例覆蓋服務器端敏感路徑；并且在搜索過程中，以敏感路徑的覆蓋信息作為啟發信息設計的全局和局部適應度函數能夠加速演化過程，在總搜索代數，執行個體數量及時間開銷上優于其他2種方法。

針對測試用例自動生成，在后續的工作中將考慮根據更多的過濾機制來生成多樣化的惡意數據，增加測試用例的故障檢測效果。