陳亞龍，江國華

(南京航空航天大學計算機科學與技術學院，江蘇南京 210016)

在Web工程中，基于Web系統(tǒng)的測試、確認和驗收是一項重要的工作。首先，Internet是一個無集中控制、并且在不斷發(fā)展的系統(tǒng)，它由大量的局部自治系統(tǒng)組成，并具有多方面的異構性以及系統(tǒng)狀態(tài)的不確定性。其次，由于Web應用的多層體系架構，客戶端、硬件和服務器之間相互聯(lián)系，導致故障源難以排查。另外，由于瀏覽器可能引起的兼容問題，服務器、數(shù)據庫負載能力對系統(tǒng)性能的影響，并發(fā)用戶對系統(tǒng)交互行為的干擾等，使得Web系統(tǒng)的測試變得異常困難。因此，研究Web應用測試技術具有現(xiàn)實意義。Web測試主要涉及:功能測試、性能測試、瀏覽器兼容性測試、可用性測試、回歸測試等。

目前，國內外對Web應用的測試研究已經取得一些研究成果。在模型構造方面，有D.C.Kung等人提出的面向對象的Web應用測試模型;Filippo Ricca等人提出了采用 UML模型方法描述 Web應用;A.A.Andraws等人在前人的基礎上提出了分層聚集FSM。在工具方面，有記錄/回放工具，自動化測試框架等工具，但這些工具都具有明顯的缺點［1－2］。

基于FSM對Web應用建模，論文提出一種改進的最小測試成本遷移覆蓋準則，并在此覆蓋準則之上，提出并實現(xiàn)了一種有效的測試用例生成算法——模擬退火遺傳算法。

1 軟件測試及Web測試技術

1.1 Web應用程序的結構

Web應用具有分布、并發(fā)、異構以及平臺無關性等特點。目前Web應用通常采用3層體系結構，如圖1所示，客戶端瀏覽器負責用戶界面解析、顯示以及接受用戶的輸入信息。Web服務器進行通信和交互。Web服務器是主要的事務計算和處理單元，屬于商業(yè)邏輯層，根據不同用戶的請求做出對應的處理。數(shù)據庫服務器是數(shù)據服務層，以一定的邏輯規(guī)則存放著與應用程序相關的數(shù)據，并進行數(shù)據增、刪、改、查、維護等工作。

圖1 Web應用結構

1.2 主流的4種提取用例方法

按照Web測試用例生成方法所采用的技術，把Web測試用例的生成方法歸結為4類:(1)記錄/回放法，基于Capture/Replay技術產生測試用例。(2)源代碼分析法，分析服務器端的源代碼，產生測試用例。(3)User session法，基于用戶會話產生測試用例。(4)Html分析法，分析客戶端Html代碼，建立模型，從模型產生測試用例。其中，記錄/回放法需要耗費大量的人力來產生測試用例;源代碼分析法通用性不強，需要處理不同的Web編程語言;User session法需要有訪問數(shù)據積累，在應用投入使用之前，無法用該方法測試，并且很難調試沒有使用過的功能;Html分析法與平臺實現(xiàn)技術無關，并且能方便地在客戶端完成測試，所以采用Html分析法提取模型。

2 基于FSM的Web應用模型的研究

2.1 FSM 模型

有限自動機(FSM)簡稱自動機，它表示有限個狀態(tài)以及在這些狀態(tài)之間的轉移和動作等行為的數(shù)學模型。它提供一種方便的建模方法，并且它可以很好地避免與實現(xiàn)相關聯(lián)的問題。利用自動機的思想，結合Web應用的特點，建立出有效的Web應用模型。它主要包括:一個有限狀態(tài)集合，用于描述系統(tǒng)中的不同狀態(tài);一個輸入集合，用于表征系統(tǒng)所接受的不同輸入信息;一個狀態(tài)轉移規(guī)則集合，用于表述系統(tǒng)在接受不同輸入的情況下，從一個狀態(tài)轉移到另一個狀態(tài)的規(guī)則。

2.2 具有Web特性的FSM

FSM定義為

其中，Q表示狀態(tài)集合:Web應用所有的狀態(tài);∈表示輸入符號集合:從一個頁面狀態(tài)轉移到下一個頁面狀態(tài)需要接受的輸入的集合;δ表示轉移函數(shù):每一條遷移就是一個轉移，變遷的類型分為兩種:(1)鏈接類型。(2)表單提交類型;q表示初始狀態(tài)集合:Web應用的入口頁面，等入度為0的結點;F表示接受狀態(tài)集合:無法繼續(xù)擴展的頁面以及核心頁面。

2.3 提出改進的Html法

2.3.1 Html解析結合源代碼分析

(1)Html分析。利用Html分析法，從Html提取出鏈接、表單等元素信息。

(2)源代碼分析。如果在Web應用里存在重定向頁面，而重定向頁面對于用戶并不可知，所以為了建模的準確性，除了分析Html，還需要分析源代碼，跳過重定向頁面。保證自動機狀態(tài)變遷與用戶實際操作狀態(tài)變遷相一致。

2.3.2 自動填充表單

如果一個遷移的起始狀態(tài)需要提交表單至目標狀態(tài)，那么就需要對起始狀態(tài)中表單進行自動填充。對于表單里的每一種類型元素，系統(tǒng)自動生成輸入值，模擬提交這些數(shù)據，如果能正常提交到目標狀態(tài)，保存當前的提交數(shù)據。否則，根據Web應用響應重新生成數(shù)據。在嘗試一定次數(shù)仍無法達到滿意輸入值后，則該表單需要人工填寫數(shù)據。

2.3.3 解析

Html法解析可以分為兩種:廣度優(yōu)先算法，深度優(yōu)先算法。兩者在效率，以及結果上均沒有顯著影響，文中采用廣度優(yōu)先算法。2.3.3.1 基本數(shù)據結構

(1)link結點。包含鏈接的名稱以及跳轉頁面。(2)form元素。form表單中的元素信息，包括名稱，類型，值。(3)form結點。包含form的跳轉頁面，傳輸類型，以及form元素信息。(4)urls鏈表。解析的所有url地址，并且url地址都標識是否解析過。(5)鄰接表。鄰接表的頭結點為FSM的狀態(tài)標識，表結點為link結點和form結點。

2.3.3.2 Html法解析流程

Html法解析流程圖，如圖2所示。

圖2 Html分析法解析流程

2.3.3.3 鄰接表的建立

(1)將當前解析頁面的頁面標識作為鄰接表中的頭結點。

(2)將1中解析出的link，form裝箱成結構體，作為表結點鏈接在頭結點之后。

3 Web應用的覆蓋準則

3.1 常見的3種覆蓋準則

(1)狀態(tài)覆蓋。測試用例集TS使FSM中的每一個狀態(tài)至少被訪問一次。FSM中的每個狀態(tài)是可達的，因而每一個狀態(tài)被訪問一次很容易。(2)遷移覆蓋。測試用例集TS使FSM中的每一個遷移至少被激活一次。(3)遷移對覆蓋。測試用例集TS使FSM中的每一對相鄰遷移t1和t2的交互至少測試一次。遷移對覆蓋檢查的是狀態(tài)之間的接口。

3.2 最小測試成本遷移覆蓋準則

劉攀等人［3］在提出的優(yōu)化遷移覆蓋算法基礎之上繼續(xù)改進提出了最小測試成本遷移覆蓋準則。符號說明:ran表示值域操作符號，#表示集合長度操作符號。

3.2.1 最小測試成本遷移覆蓋

定義 給定 M的一個遷移覆蓋 Aid，若?TSi，TSj∈Aid，都有 ran TSi∩ran TSj= ?，且?TS∈Aid都滿足#(ran TS)=#TS，即集合ran TS的大小等于序列TS的長度，則稱Aid為M的獨立遷移覆蓋。

定義 對于M的一個遷移覆蓋Ap，滿足下面兩個條件:

1)Ap是M的一個獨立遷移覆蓋。2)對于M的任意一個獨立遷移覆蓋Aid，都有#Ap≤#Aid。

3.2.2 優(yōu)化遷移覆蓋算法

1)將M中所有自遷移序列加入到輸出集合SS中，并從遷移集合T中刪除所有自遷移。

2)從遷移集合T中取一個單遷移t，令序列TS=＜t＞及T=T ，若使得TS～＜ti＞為有效連接操作，則TS=TS～＜ti＞及T=T i，直到T中不存在這樣的ti;

3)若TS可與SS中的遷移序列進行有效連接操作，則對他們進行有效連接操作，否則，將單遷移序列TS加入到SS中;

4)若T不空，則轉到步驟2)。

3.2.3 最小測試成本遷移覆蓋

定義 在M中，對于任意兩條遷移序列TS1和TS2，若TS1和TS2中的遷移包含了某些共同狀態(tài)，則稱遷移序列TS1和TS2為相交序列，這些共同狀態(tài)為TS1和TS2的相交點;否則，稱TS1和TS2為不相交序列。

定義 在M中，Aid為M的獨立遷移序列覆蓋，若?TS∈Aid，TS=〈t1，…，tk〉，t1=(s1，i1，sl)和 tk=(si，ik，sj)，滿足條件 s1=sj，則稱遷移序列TS為回路。

最小測試成本遷移覆蓋算法合并準則:

準則1 若 M 中遷移序列 TS1，TS2∈ Aid，TS1和TS2相交，且滿足TS=TS1～TS2或TS=TS2～TS1為M的遷移序列，則用遷移序列 TS替代遷移序列 TS1和TS2。

準則2 假設M中遷移序列TS1，TS2∈Aid，TS1=〈t1，t2，…，ti－1，ti，…，tk〉與 TS2=〈tm，tm+1，…，tj－1，tj，…，tn〉的相交點為 si，其中，遷移 ti－1=(si－1，ii－1，si)和tj=(si，ij，sj)，且 TS2是回路，則遷移序列 TS1和 TS2合并成遷移序列 TS=〈t1，t2，…，ti－1，tj，…，tn，tm，tm+1，…，tj－1，ti，…，tk〉。

3.2.4 最小測試成本遷移覆蓋有效性

最終生成的測試序列可能不是由初始狀態(tài)到達，因此，其中這些測試序列是無效的測試片段。尋找從初始狀態(tài)至到達該片段起始點的最短路徑序列，與測試序列組合得到新的完整測試用例序列。由于新添的序列影響了覆蓋準則評價，所以最小測試成本遷移覆蓋算法的效果無法達到覆蓋準則的要求。

3.3 Web應用最小測試成本遷移覆蓋準則

3.3.1 基本概念

定義 Web應用中從一個頁面狀態(tài)跳轉到另外一個頁面狀態(tài)，完成跳轉需要的操作代價。點擊鏈接，填充表單單個元素權值設置為1。

定義 遷移 t=(si，x，c，sj)。其中，f(si，x)=sj，x∈I，c∈N，si為遷移 t的前狀態(tài)，sj為遷移 t的后狀態(tài)，x是狀態(tài)si到狀態(tài)sj的輸入，c是輸入x的操作成本。

3.3.2 Web應用最小測試成本遷移覆蓋準則

$集合的成本符號，$Ap表示集合Ap的遷移成本。對于M的一個遷移覆蓋Ap，滿足:1)Ap是M的一個獨立遷移覆蓋。2)對于M的任意一個獨立遷移覆蓋 Aid，都有$Ap≤$Aid。

4 基于模擬退火遺傳算法的用例生成

4.1 FSM的遍歷

FSM可以使用狀態(tài)圖表示，也可以用狀態(tài)轉移表表示。基于此，用例的生成就是依據提出的Web應用最小測試成本遷移覆蓋準則，對鄰接表表現(xiàn)形式的圖的遍歷。

4.2 FSM模型狀態(tài)約簡

當一個狀態(tài)的前續(xù)狀態(tài)和后繼狀態(tài)都有且僅有一個，那么這個狀態(tài)就稱為可約簡狀態(tài)?？杉s簡狀態(tài)不會對路徑造成影響，為縮小模型規(guī)模，在分析時考慮。

4.3 傳統(tǒng)方法及其缺點

對每一個完整的測試用例，都是從初始狀態(tài)到達接受狀態(tài)，傳統(tǒng)的深度優(yōu)先或廣度優(yōu)先遍歷方法并不能滿足該要求;最小測試成本遷移覆蓋算法在非啟發(fā)式搜索算法中效率較高，但它的結果也難以接近最優(yōu)解。所以提出一個新的基于遺傳算法和模擬退火算法的啟發(fā)式搜索算法用于解決FSM的遍歷問題。

定義 對于一個問題，如果它的解是一條序列，則稱問題的解為“一維解”。如果它的解是一組序列，并且路徑相互獨立，則稱問題的解為“二維解”。

維度越高，生成越復雜。每一個合法的解需要滿足覆蓋準則要求，而二維解比一維解更難滿足。解決普通NP問題時，模擬退火算法里是利用簡單的置換，互換等手段產生新解，然而，由于維度的提高，這樣的方式無法用在當前問題。所以問題需要一種新的新解產生方式。

4.4 人工智能啟發(fā)式搜索

4.4.1 遺傳算法

遺傳算法(Genetic Algorithm)是一類借鑒生物界的進化規(guī)律演化而來的隨機化搜索方法。由美國的J.Holland教授1975年首先提出，其主要特點是直接對結構對象進行操作，不存在求導和函數(shù)連續(xù)性的限定;具有內在的隱并行性和更好的全局尋優(yōu)能力;采用概率化的尋優(yōu)方法，能自動獲取和指導優(yōu)化的搜索空間，自適應地調整搜索方向，不需要確定的規(guī)則。遺傳算法的這些性質，已被廣泛地應用于組合優(yōu)化、機器學習、信號處理、自適應控制和人工生命等領域［4－6］。

4.4.2 模擬退火算法

模擬退火算法(Simulated Annealing，SA)最早由Kirkpatrick等應用于組合優(yōu)化領域，它是基于Monte－Carlo迭代求解策略的一種隨機尋優(yōu)算法，其出發(fā)點是基于物理中固體物質的退火過程與一般組合優(yōu)化問題之間的相似性。模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降，結合概率突跳特性在解空間中隨機尋找目標函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。模擬退火算法是一種通用的優(yōu)化算法，理論上算法具有概率的全局優(yōu)化性能，目前已在工程中得到了廣泛應用，諸如VLSI、生產調度、控制工程、機器學習、神經網絡、信號處理等領域。

模擬退火算法是通過賦予搜索過程一種時變且最終趨于零的概率突跳性，從而可有效避免陷入局部極小并最終趨于全局最優(yōu)的串行結構的優(yōu)化算法。

4.4.3 模擬退火遺傳算法

模擬退火進化是由參數(shù)問題t控制的，然后通過一定的操作產生新的解，根據當前解的優(yōu)劣和溫度參數(shù)t確定是否接受當前的新解。遺傳算法主要由選擇、交叉和變異等操作組成，通過種群進行進化。

模擬退火是采用單個個體進行進化，遺傳算法是采用種群進行進化。模擬退火一般新解優(yōu)于當前解才接受新解，并且還需要通過溫度參數(shù)t進行選擇，并通過變異操作產生新個體。而遺傳算法新解是通過選擇操作進行選擇個體，并通過交叉和變異產生新個體。兩者都是采用進化控制優(yōu)化的過程。

將兩者結合具有以下優(yōu)點:首先，它們基本思想都是采用進化控制優(yōu)化的過程，模擬退火采用單個個體進行優(yōu)化，在當前問題下，很適合。其次，遺傳算法在產生新個體時提供較多的手段，將交叉和變異結合到優(yōu)化過程中，可以很好地解決當前問題。

4.4.4 模擬退火遺傳算法實現(xiàn)

4.4.4.1 相關定義

定義1 入度、出度都≥2的結點為交叉點。

定義2 解狀態(tài)中一直存在，不可修改，刪除，唯一的遷移序列，為元序列。

找出初始解里的交叉點，把每個用例都在交叉點處拆分開，得到的遷移序列稱之為元序列。

4.4.4.2 模型思想

(1)初始化:初始溫度T，初始解狀態(tài)S(是算法迭代的起點)，每個T值的迭代次數(shù)L。(2)對k=1，…，L做第(3)至第6步。(3)產生新解S'。(4)計算增量Δt'=C(S')－C(S)，其中C(S)為評價函數(shù)。(5)若Δt'＜0則接受S'作為新的當前解，否則以概率 exp(－Δt'/T)接受S'作為新的當前解。(6)如果滿足終止條件則輸出當前解作為最優(yōu)解，結束程序。終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法。(7)T逐漸減少，且T－＞0，然后轉第(2)步。

4.4.4.3 新解構造

解狀態(tài):包括當前解、前段解集合、后段解集合。不同的解狀態(tài)共享元序列。

(1)拆分當前解。從FSM的狀態(tài)集合中提取出交叉點集合，從交叉點集合中隨機選取一個，拆分當前解，得到序列集合，分為前段解集合，后段解集合。

(2)序列組合。從后段解集合中隨機選取一條序列，以概率p與前段解集合的序列結合，以1－p的概率與元序列集合結合。其中p值取0.7。若此時前段解集合為空，p值取0。最終可以得到一條完整的序列。

(3)新解產生。序列組合得到的序列就是新解中的序列。在后段解集合全部組合完成:

1)若前段解集合也已經為空，則新解為組合后的序列集合，新解構造結束。2)若前段解集合不為空，且其元素不為元序列，則將剩余的前段解集合中每個元素與元序列集合結合，結合后的序列做為新解中的一條序列。

4.4.4.4 評價函數(shù)

C(S)為評價函數(shù)，C(S)=SN(S)+LN(S)+FM(S)。其中，LN(S)為統(tǒng)計S里的鏈接變遷個數(shù);FM(S)為統(tǒng)計S里的表單提交變遷個數(shù)*權值;SN(S)為統(tǒng)計S里用例的條數(shù)*權值。

5 基于FSM的Web應用功能測試實例

現(xiàn)在有一個Web應用為招聘信息發(fā)布系統(tǒng)，并且已經提取出模型。

5.1 Web應用FSM模型

模型如圖3所示，表2對圖中每個狀態(tài)進行了說明，表3對每個變遷進行說明。

圖3 應用的FSM模型

表1 狀態(tài)說明表

FSM模型的變遷說明，如表2所示。

表2 變遷說明表

5.2 用例生成

5.2.1 最小測試成本遷移覆蓋算法生成用例

按照優(yōu)化遷移覆蓋算法和最小測試成本遷移覆蓋算法，得到用例如下:

5.2.2 模擬退火遺傳算法生成用例

利用模擬退火遺傳算法可以優(yōu)化得出成本更低的用例:

5.2.3 總結

雖然該系統(tǒng)結構比較簡單，但通過模擬退火遺傳算法優(yōu)化，其測試用例成本已經明顯降低。因而，在覆蓋準則下，模擬退火遺傳算法優(yōu)化圖路徑是有效的。

6 結束語

本文完成了對Web應用建立FSM模型，實現(xiàn)了一個高效魯棒的提取算法。提出一個新的最小成本遷移覆蓋準則，在此覆蓋準則約束下，Web應用可以生成高質量的用例。提出一種混合的啟發(fā)式搜索算法，解決了在覆蓋準則約束下，從FSM模型到測試用例的高質量轉換。Web領域發(fā)展日新月異，未來工作重點主要集中在:(1)需要對Web應用中引入的特性等分析，對FSM模型需要繼續(xù)深入研究。(2)模擬退火遺傳算法中產生新解過程耗費較多計算資源，還需要繼續(xù)優(yōu)化、探索。

［1］彭樹深，顧慶，陳道蓄.Web應用測試用例生成研究［J］.計算機科學，2010，37(6):159 －163.

［2］ANNELIESE A，ANDREWS J，OFFUTT R T.Testing Web applications by modeling with fsms［J］.Software Systems and Modeling，2005，4(3):326 －345.

［3］劉攀，繆淮扣，曾紅衛(wèi)，等.確定性有限狀態(tài)機的最小測試成本遷移覆蓋準則［J］.軟件學報，2011，22(7):1457 －1474.

［4］MIAO H K，LIU P，MEI J，et al.A new approach to automated redundancy reduction for test sequences［C］.IEEE Computer Society Press，shanghai:PRDC，2009:93 －98.

［5］ZHU B，MIAO H，ZENG H，et al.Generating test case from functional requirement of Web applications［C］.Nanchang:2009 Second International Symposium on Electronic Commerce and Security，ISECS，2009:465 －468.

［6］馮雅麗.基于有限狀態(tài)機理論的Web功能自動化測試技術研究［D］.上海:華東師范大學，2009.