面向Web服務(wù)器端敏感路徑的客戶端擴展有限狀態(tài)機測試生成

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

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

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

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

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

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

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

1.1 基本概念

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

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

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

狀態(tài)s定義為Web應(yīng)用軟件網(wǎng)頁的URL地址及其當(dāng)前的DOM結(jié)構(gòu)。

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

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

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

1.2 面向Web服務(wù)器端敏感路徑的客戶端擴展有限狀態(tài)機測試生成

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

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

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

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

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

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

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

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

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

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

1) 個體表示。

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

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

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

fit=approach_level+branch_distance

(1)

f=Normalized(fit)

(2)

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

3)評估矩陣M。

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

p1p2p3…pk

4) 全局搜索適應(yīng)度函數(shù)。

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

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

5)局部搜索適應(yīng)度函數(shù)。

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

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

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

//隨機生成初始種群

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

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

cover_flag=setFlag(M,P)

//標(biāo)記敏感路徑源點是否全部覆蓋

if cover_flag=True then

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

if | Listuncover_path|=0 then return TS=pop

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

else

for eachpin Listuncover_pathdo{

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

//調(diào)整個體數(shù)據(jù)以完全覆蓋敏感路徑

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的測試腳本自動構(gòu)建

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

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

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

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

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

2) 遷移聚類。

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

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

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

S(Ti,Tj)=

(4)

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

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

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

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

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

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;

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

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

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

2 實驗及結(jié)果分析

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

RQ1:遷移測試腳本庫構(gòu)建方法是否可行？

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

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

本文以開源Web應(yīng)用SchoolMate、Webchess和FAQforge作為實驗對象，相關(guān)信息見表2、表3。

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

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

2.1 測試腳本自動構(gòu)建可行性驗證

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

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

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

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

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

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

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

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

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

由圖3可以看出，3種測試生成方法經(jīng)過反復(fù)迭代最終都可以覆蓋Web應(yīng)用中的所有敏感路徑。隨著搜索代數(shù)的增加，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個被測程序，本文方法在總搜索代數(shù)，執(zhí)行個體數(shù)量及時間開銷上優(yōu)于于其他兩種方法。此外，測試用例生成的結(jié)果表明本文方法可以生成滿足要求的測試用例，這意味著從客戶端行為模型擴展有限狀態(tài)機上生成的抽象測試用例可以轉(zhuǎn)換為測試腳本并執(zhí)行，進一步驗證了本文所提出的測試腳本自動生成方法是可行和有效的。

3 結(jié)論

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

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

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