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

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

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

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

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

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

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

1.1 基本概念

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

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

定義2Web客戶端擴(kuò)展有限狀態(tài)機(jī)模型。用來表征Web應(yīng)用客戶端行為的擴(kuò)展有限狀態(tài)機(jī)模型，其狀態(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ā)生改變的過程，用一個(gè)五元組〈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)對(duì)應(yīng)可驅(qū)動(dòng)客戶端代碼執(zhí)行，改變當(dāng)前網(wǎng)頁的DOM結(jié)構(gòu)的事件，包含事件的類型(Etype)、事件綁定的DOM元素、該DOM元素的定位方式(DL)及事件上的輸入?yún)?shù)(CIN)和參數(shù)的定位方式(CDL)等信息；Cond(t)對(duì)應(yīng)事件處理函數(shù)中涉及的謂詞條件；Action(t)對(duì)應(yīng)事件處理函數(shù)的參數(shù)變化及服務(wù)器端返回的消息。

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

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

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

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

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

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

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

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

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

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

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

1) 個(gè)體表示。

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

2) 個(gè)體覆蓋敏感路徑的評(píng)價(jià)指標(biāo)。

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

fit=approach_level+branch_distance

(1)

f=Normalized(fit)

(2)

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

3)評(píng)估矩陣M。

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

p1p2p3…pk

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

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

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

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

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

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

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

//隨機(jī)生成初始種群

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

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

cover_flag=setFlag(M,P)

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

if cover_flag=True then

//pop覆蓋所有敏感路徑源點(diǎn)，局部搜索

if | Listuncover_path|=0 then return TS=pop

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

else

for eachpin Listuncover_pathdo{

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

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

pop=Update_Individual(pop, Ind)

until | Listuncover_path|=0 return TS=pop

else

//pop未覆蓋所有敏感路徑源點(diǎn)，全局搜索

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

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

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

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

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

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

2) 遷移聚類。

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

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

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

S(Ti,Tj)=

(4)

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

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

3) 測試腳本自動(dòng)生成方法。

測試腳本自動(dòng)生成的映射規(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í)(一類遷移腳本封裝在一個(gè)函數(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個(gè)遷移的輸入?yún)?shù)個(gè)數(shù)CIN不同時(shí)，這2個(gè)遷移對(duì)應(yīng)的Selenium原子操作個(gè)數(shù)也不同，S(Ti,Tj)=0；反之，通過特征字符串的最長公共字串來計(jì)算2個(gè)遷移之間的相似度。當(dāng)2個(gè)遷移的特征字符串沒有公共子串時(shí)，二者相似程度為0；當(dāng)2個(gè)遷移的特征字符串完全一樣時(shí)，二者的相似程度為1。根據(jù)相似度公式構(gòu)建遷移之間的相似矩陣S，用于譜聚類算法，可得到聚類結(jié)果。

3) 測試腳本自動(dòng)生成方法

測試腳本自動(dòng)生成的映射規(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 實(shí)驗(yàn)及結(jié)果分析

為評(píng)估所提方法的有效性，本文通過以下3個(gè)問題進(jìn)行實(shí)驗(yàn)研究。

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

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

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

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

表2 實(shí)驗(yàn)程序Table 2 Web applications of under test

表3 實(shí)驗(yàn)程序的模型及敏感路徑信息Table 3 Information for client-side EFSM model

2.1 測試腳本自動(dòng)構(gòu)建可行性驗(yàn)證

遷移聚類的準(zhǔn)確程度直接影響得到生成的測試腳本是否有效，而遷移聚類的核心是遷移之間的相似度性度量。為回答RQ1，本實(shí)驗(yàn)以手工統(tǒng)計(jì)結(jié)果為基準(zhǔn)，比較不同相似度的譜聚類精確度Acluster。Acluster為能正確分類的遷移數(shù)量(#CCTrans)除以遷移總數(shù)。本文與使用較為廣泛的編輯距離進(jìn)行對(duì)比實(shí)驗(yàn)，聚類精度結(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ù)器端敏感路徑的擴(kuò)展有限狀態(tài)機(jī)測試用例生成的有效性驗(yàn)證

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

實(shí)驗(yàn)結(jié)果如表5所示，在3個(gè)被測程序中，GA+HC方法的全局搜索代數(shù)分別為334、361、28，大于另外2種使用MyGA的組合方法，說明MyGA能比GA更快地搜索到能覆蓋所有敏感路徑源點(diǎn)的個(gè)體集合。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

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

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

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

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

由此可見，對(duì)于3個(gè)被測程序，本文方法在總搜索代數(shù)，執(zhí)行個(gè)體數(shù)量及時(shí)間開銷上優(yōu)于于其他兩種方法。此外，測試用例生成的結(jié)果表明本文方法可以生成滿足要求的測試用例，這意味著從客戶端行為模型擴(kuò)展有限狀態(tài)機(jī)上生成的抽象測試用例可以轉(zhuǎn)換為測試腳本并執(zhí)行，進(jìn)一步驗(yàn)證了本文所提出的測試腳本自動(dòng)生成方法是可行和有效的。

3 結(jié)論

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

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

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