一種基于關(guān)聯(lián)規(guī)則的Web應(yīng)用統(tǒng)計測試方法

王玉奇,高建華

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

0 概述

隨著互聯(lián)網(wǎng)技術(shù)及其應(yīng)用的快速發(fā)展,保證Web應(yīng)用的可靠性日益重要,Web統(tǒng)計測試可以有效確保Web應(yīng)用的質(zhì)量,其基于用戶的使用場景和頻率進(jìn)行優(yōu)先測試,將統(tǒng)計方法學(xué)的理論應(yīng)用到軟件測試中。研究人員針對Web統(tǒng)計測試做了大量研究。文獻(xiàn)[1]提出Web統(tǒng)計測試與馬爾科夫模型構(gòu)建方法,通過分析Web訪問日志與錯誤日志,使用馬爾科夫模型對Web應(yīng)用進(jìn)行測試和可靠性評估。文獻(xiàn)[2]闡述了馬爾科夫模型應(yīng)用于Web統(tǒng)計測試以及構(gòu)建Web使用模型過程中的可行性,通過從Web服務(wù)器日志中統(tǒng)計網(wǎng)頁的使用頻率進(jìn)行測試,將馬爾科夫模型作為統(tǒng)計測試、性能評估與可靠性分析的基礎(chǔ)。文獻(xiàn)[3]提出了一種基于UML的馬爾科夫模型構(gòu)建方法,并將馬爾科夫模型分為測試用例級與場景級兩類,通過馬爾科夫模型生成軟件測試用例。文獻(xiàn)[4]提出改進(jìn)的Apriori算法以挖掘Web訪問序列,以此預(yù)測用戶的下一個頁面請求以及改進(jìn)Web站點(diǎn)的拓?fù)浣Y(jié)構(gòu)。文獻(xiàn)[5]提出應(yīng)用關(guān)聯(lián)規(guī)則對Web用戶進(jìn)行區(qū)域劃分的方法,其對Web的用戶行為進(jìn)行分析并實(shí)現(xiàn)頁面推薦。

傳統(tǒng)Web統(tǒng)計測試方法通常根據(jù)日志記錄中的用戶行為信息構(gòu)建馬爾科夫模型,對用戶行為的量化不夠明確,測試重點(diǎn)不突出,且生成的測試用例無法較好地模擬用戶行為。本文提出一種基于關(guān)聯(lián)規(guī)則的Web應(yīng)用統(tǒng)計測試方法。使用哈希表與自定義數(shù)據(jù)結(jié)構(gòu)note從Web日志中提取用戶行為記錄。通過將2個連續(xù)頁面之間的訪問時間差再減去Time-Taken字段值得到用戶頁面的瀏覽時間,并將其作為頁面興趣度的屬性之一。通過關(guān)聯(lián)規(guī)則挖掘得到會話中的頻繁訪問頁面,以此構(gòu)建馬爾科夫模型,從而衡量Web應(yīng)用的可靠性。在此基礎(chǔ)上,采用輪盤賭算法生成測試用例,兼顧馬爾科夫模型中轉(zhuǎn)移概率的大小與選擇的隨機(jī)性。通過執(zhí)行本文測試用例產(chǎn)生的Web日志與真實(shí)環(huán)境下的Web日志,以評估Web應(yīng)用的可靠性。

1 Web日志與關(guān)聯(lián)規(guī)則

本文首先獲取服務(wù)器日志,通過使用哈希表與自定義結(jié)構(gòu)note存儲并描述用戶的行為記錄,利用關(guān)聯(lián)規(guī)則對用戶會話Session進(jìn)行挖掘,以得到用戶會話中的頻繁訪問頁面,從而構(gòu)建Web統(tǒng)計測試的馬爾科夫模型?；陉P(guān)聯(lián)規(guī)則的Web統(tǒng)計測試方法框架如圖1所示。

圖1 基于關(guān)聯(lián)規(guī)則的Web統(tǒng)計測試方法框架

1.1 Web服務(wù)器日志

Web服務(wù)器端完整保留了用戶在使用Web應(yīng)用時的操作,并通過日志的形式進(jìn)行保存[6]。Web日志包括訪問日志(Access Log)、錯誤日志(Error Log)、代理日志(Agent Log)、引用日志(Referrer Log)以及事件日志(Event Log)。目前常用的Web服務(wù)器有MS IIS、Apache、Nginx等,每種服務(wù)器的日志格式不同,可以通過分析Web日志來探究用戶的瀏覽行為以及測試Web應(yīng)用的可靠性。Apache是目前最常用的服務(wù)器之一,也是本文的研究對象,其采用可自定義的ASCII格式,可以包含各種不同的字段,字段之間以空格分開。表1所示為訪問日志的格式。

表1 訪問日志的格式Table 1 Format of access log

本文使用Apache服務(wù)器的訪問日志,主要選用其中的以下8個字段:

1)C-IP:訪問者IP。

2)CS(User-Agent):訪問者的瀏覽器以及操作系統(tǒng)。

3)Date:訪問日期。

4)Time:訪問時間。

5)Referrer:引用鏈接。

6)URL:訪問者訪問的頁面鏈接。

7)SC-Bytes:服務(wù)器向客戶端發(fā)送的字節(jié)數(shù)。

8)Time-Taken:服務(wù)器接收請求到發(fā)送響應(yīng)內(nèi)容間的時間間隔。

1.2 自定義數(shù)據(jù)結(jié)構(gòu)note

在從訪問日志與引用日志中分離用戶行為記錄時,考慮到每讀取一條日志記錄,會獲得一個C-IP與CS(User-Agent),在用戶列表(user list)中查找與該IP地址和CS(User-Agent)對應(yīng)的位置,然后將該條日志所記載的網(wǎng)頁加入到頁面列表(page list)中,當(dāng)網(wǎng)站日志記錄很大時,用戶列表會非常龐大,查詢和對比效率較低。因此,本文使用哈希表,同時自定義一種數(shù)據(jù)結(jié)構(gòu)note,以提高查詢和對比效率并詳細(xì)記錄用戶的每一次行為。

定義1數(shù)據(jù)結(jié)構(gòu)note=為一個三元組,可以描述用戶的一次行為,其中,各元素含義如下:

1)U表示用戶編號,本文定義U=< C-IP ,CS(User-Agent)>,即由訪問日志中的IP地址與用戶代理共同確定一個唯一用戶。

2)Edge表示用戶的一次頁面跳轉(zhuǎn),本文定義Edge=為一個二元組。其中,Referrer(type)取自引用日志中的Referrer,即用戶在訪問當(dāng)前鏈接前訪問的URL鏈接,type∈{′Inside′,′Outside′},Inside表示該引用鏈接屬于Web站點(diǎn)內(nèi),Outside表示該引用鏈接屬于Web站點(diǎn)外。

3)Interest為用戶對該頁面的興趣度,興趣度可以通過對頁面的瀏覽時間和服務(wù)器發(fā)送的字節(jié)數(shù)來綜合考慮。服務(wù)器發(fā)送的字節(jié)數(shù)取自訪問日志中的SC-Bytes字段,在一般情況下,將會話中2個連續(xù)訪問頁面之間的時間差定義為瀏覽持續(xù)時間,并作為用戶興趣度的描述屬性[7]。但是,持續(xù)時間還與網(wǎng)絡(luò)的傳輸速度有直接關(guān)系,即持續(xù)時間不能準(zhǔn)確表示用戶的興趣度,誤差較大。因此,本文綜合考慮訪問日志中的Time-Taken字段,將2個連續(xù)訪問頁面之間的時間差再減去Time-Taken值,以作為用戶訪問該頁面的瀏覽時間Spend-Time,并用來描述用戶的興趣度。本文采用文獻(xiàn)[8]中定義的用戶對頁面i的興趣度:

從Web訪問日志中分離用戶行為記錄的過程如圖2所示,當(dāng)讀取一條日志時,會得到一個用戶的IP地址,將IP地址中每個字符的ASCII碼相加并進(jìn)行模運(yùn)算,將運(yùn)算結(jié)果作為哈希表的索引值,在索引值下找到相應(yīng)的用戶列表。用note結(jié)構(gòu)表示該日志,通過note中的U字段查找用戶列表中的用戶,并將該note加入到此用戶的note list中。

圖2 用戶行為分離示意圖

從Web訪問日志中分離用戶行為記錄的過程如算法1所示。

算法1Web訪問日志中用戶行為記錄分離算法

輸入訪問日志

輸出存儲用戶行為記錄的哈希表

步驟1讀取一條日志,通過note結(jié)構(gòu)表示該條日志。將IP地址中每個字符的ASCII碼相加并進(jìn)行模運(yùn)算,將運(yùn)算結(jié)果作為哈希表的索引值。

步驟2根據(jù)索引值找到相應(yīng)的用戶列表(user list)。

步驟3在user list中比較該note中的U字段,如果user list中已經(jīng)存在該note中的U字段,則將該note加入到note list中;否則,將該U字段加入到user list中。

步驟4重復(fù)執(zhí)行步驟1～步驟3,直到日志記錄遍歷結(jié)束。

1.3 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則源自數(shù)據(jù)挖掘方法,該方法可以從大量數(shù)據(jù)集中有效發(fā)現(xiàn)有意義的規(guī)則。如X→Y,其中,X?I,Y?I,I={i1,i2,…,im}是m個不同項(xiàng)的集合。規(guī)則意味著包含項(xiàng)集X的數(shù)據(jù)庫D中的事務(wù)記錄往往包含項(xiàng)集Y[9-11]。相關(guān)定義如下:

1)項(xiàng)集(itemset):為一些項(xiàng)的集合,項(xiàng)集中的項(xiàng)數(shù)稱為項(xiàng)集的長度,包含k個項(xiàng)的項(xiàng)集稱為k-項(xiàng)集。

2)支持?jǐn)?shù)(φ):對于X?I,φ為D中包含X的事務(wù)個數(shù)。

3)支持度(support):對于X?I,若D中包含X的事務(wù)個數(shù)為s,D中事務(wù)總數(shù)為n,則support(X)=s/n。

4)閾值:為最小支持度。

5)頻繁項(xiàng)集:項(xiàng)集的出現(xiàn)頻率大于等于最小支持度,頻繁k-項(xiàng)集的集合通常記作Lk,頻繁2-項(xiàng)集記作L2。

6)非頻繁項(xiàng)集:項(xiàng)集的出現(xiàn)頻率小于最小支持度。

設(shè)候選項(xiàng)集I={A,B,C,D}是含有4個不同項(xiàng)的集合,數(shù)據(jù)庫D是針對I的事務(wù)集合,共包含6個事務(wù),如表2所示?？紤]A與B的關(guān)聯(lián)規(guī)則(頻繁-2項(xiàng)集),事務(wù)1、2、3、4、6包含A,事務(wù)1、2、6同時包含A與B,則支持度support(A)=5/6,support(A∪B)=3/6。若給定最小支持度為0.5,則認(rèn)為A與B存在關(guān)聯(lián)。

表2 關(guān)聯(lián)規(guī)則數(shù)據(jù)庫Table 2 Database of association rules

1.4 基于興趣度的會話挖掘

算法2基于興趣度的Apriori算法

輸出L2/*頁面的頻繁2-項(xiàng)集*/

步驟1生成頁面的頻繁1-項(xiàng)集L1

1)定義集合P={URL1,URL2,…,URLn}為候選項(xiàng)集C1,一個用戶的一條會話作為事務(wù)數(shù)據(jù)庫中的一個事務(wù),定義集合L1為頁面的頻繁1-項(xiàng)集,令CurrentURL指向URL1。

2)遍歷事務(wù)數(shù)據(jù)庫中所有會話的Edge,如果CurrentURL=Edge.URL,則支持度CurrentURL.count=CurrentURL.count+φi;如果等式不成立,則繼續(xù)比較會話中的下一個URL,直到所有用戶的會話集合遍歷結(jié)束。

3)如果CurrentURL.count>min_support,則將CurrentURL添加到L1中,令CurrentURL指向URL2。

4)重復(fù)執(zhí)行步驟2)、步驟3),直到CurrentURL指向URLn結(jié)束,得到頁面的頻繁1-項(xiàng)集L1。

步驟2生成頁面的頻繁2-項(xiàng)集L2,得到用戶會話的頻繁訪問頁面序列。

1)將頻繁1-項(xiàng)集L1中的項(xiàng)兩兩結(jié)合,生成候選項(xiàng)集C2={},URLi∈L1,URLj∈L1。定義集合L2為頁面的頻繁2-項(xiàng)集,令CurrentEdge指向。

3)如果CurrentEdge.count>min_support,則將CurrentEdge添加到L2中,令CurrentEdge指向會話中的下一個Edge。

4)重復(fù)執(zhí)行步驟2)、步驟3),直到CurrentEdge指向會話中的最后一個Edge結(jié)束,得到頁面的頻繁2-項(xiàng)集L2。

在所有用戶的會話集合中,如果note.Edge不屬于L2,則將該用戶行為記錄note從用戶的會話集合中去掉,最終得到用戶會話中的頻繁訪問頁面。

2 基于關(guān)聯(lián)規(guī)則的Web統(tǒng)計測試方法

2.1 Web統(tǒng)計測試

統(tǒng)計測試將統(tǒng)計學(xué)方法應(yīng)用到軟件測試中,其產(chǎn)生軟件所有可能使用的子集,并以該子集所表現(xiàn)的性能作為依據(jù)來評估軟件整體使用性能[16]。Web統(tǒng)計測試通過選用頻繁使用的樣本歷史數(shù)據(jù)和故障信息來推斷軟件的可靠性,統(tǒng)計測試一般分為以下3個步驟:

1)基于軟件真實(shí)使用場景和相關(guān)的頻率構(gòu)建統(tǒng)計測試模型。

2)根據(jù)統(tǒng)計測試模型生成測試用例并篩選和執(zhí)行測試。

3)分析測試結(jié)果,進(jìn)行可靠性評估與預(yù)測。

一般測試方法無法以較小的代價對Web應(yīng)用進(jìn)行大規(guī)模和覆蓋性測試,而Web統(tǒng)計測試根據(jù)用戶對軟件的使用方式,對頻繁使用的操作進(jìn)行更多地測試[17]。軟件使用可以看作一個隨機(jī)的過程,本文用馬爾科夫模型來描述軟件的使用方式,即任何下一狀態(tài)發(fā)生的事件只和當(dāng)前狀態(tài)有關(guān),和歷史狀態(tài)無關(guān)。

2.2 馬爾科夫模型主要元素

在本文中,Web統(tǒng)計測試在建模過程中選擇馬爾科夫模型,該模型是滿足如下假設(shè)的一種過程:t+1時刻系統(tǒng)狀態(tài)的概率分布只與t時刻的狀態(tài)有關(guān),與t時刻以前的狀態(tài)無關(guān)[18]。馬爾科夫模型通過馬爾科夫鏈描述軟件使用過程,其不僅能描述在使用過程中軟件的狀態(tài),也能通過狀態(tài)轉(zhuǎn)移概率模擬用戶的行為習(xí)慣[19]。馬爾科夫模型的3個主要元素為狀態(tài)空間、狀態(tài)轉(zhuǎn)移弧和狀態(tài)轉(zhuǎn)移概率。三者定義分別如下:

3)轉(zhuǎn)移概率:指軟件從一個狀態(tài)空間轉(zhuǎn)移到其他狀態(tài)空間的概率。從某一狀態(tài)空間到其他狀態(tài)空間的轉(zhuǎn)移概率之和為1。

2.3 馬爾科夫模型構(gòu)建

圖3 用戶會話集合示意圖

圖4 用戶會話分離示意圖

圖5 馬爾科夫有向圖

圖6 馬爾科夫模型

2.4 測試用例生成

算法3Routlette-Wheel-Selection算法

輸出Statev/*跳轉(zhuǎn)到的頁面鏈接*/

1.assign P_total =0/* P_total為輪盤過程中的概率和*/

2.assign number ←a random float number from 0 to 1

4.assign P_total = P_total+P(Edge) /*將有向邊Edge的概率加到P_total中*/

5.if P_total>number then

6.assign v=the URL of the Edge

7.break;

8.end if

9.end for

算法4測試用例生成算法

輸入Markov model

N/*一組測試用例中的測試用例個數(shù)*/

M/*一個測試用例的最大長度*/

輸出cases

1.assigncases←an object of List

/*測試用例的結(jié)果*/

2.assigncase←an object of List

3.for all i∈1 to N do

4.assign Edge←an object of List

5.assign u←an object of State

/*u用來記錄當(dāng)前頁面*/

6.assign u←Outside/*馬爾科夫模型入口點(diǎn)*/

7.for all j∈1 to M do

8.Add u to Edge.Referrer

10.Add Edge to case

11.assign u←Edge.URL

12.end for

13.Add case to cases

14.Clear(case)

15.end for

算法4用于生成一組測試用例,其中,包含N條最大長度為M的測試用例。首先,從入口點(diǎn)開始調(diào)用算法3生成下一頁面鏈接,然后循環(huán)M次生成一個長度為M的測試用例case =<(Edge1),(Edge2),…>,最后將上述過程循環(huán)N次生成N條測試用例cases=<(case1),(case2),…>。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證基于關(guān)聯(lián)規(guī)則的Web統(tǒng)計測試方法的有效性,本文以一個校園門戶網(wǎng)站(http://www.shnu.edu.cn)作為測試背景,該網(wǎng)站發(fā)布學(xué)校各部門新聞以及各學(xué)院相關(guān)信息,提供學(xué)校概況、機(jī)構(gòu)設(shè)置、師資隊(duì)伍、人才培養(yǎng)、學(xué)術(shù)研究、海外交流和招生就業(yè)等導(dǎo)航。本文實(shí)驗(yàn)平臺搭載在Apache服務(wù)器上,使用Apache服務(wù)器記錄連續(xù)10個工作日的Web訪問日志與Web錯誤日志并進(jìn)行分析。

Web應(yīng)用的可靠性評估采用Nelson模型[21],可靠性評估的一個重要指標(biāo)為平均無故障時間(MTBF),設(shè)鏈接跳轉(zhuǎn)(Edge)次數(shù)為n,錯誤數(shù)為f,則MTBF=n/f,Web應(yīng)用可靠性估計值R=1-f/n,即可靠性與MTBF為正比關(guān)系。本文實(shí)驗(yàn)主要解決以下2個問題:

Q1:在Web統(tǒng)計測試中,通過關(guān)聯(lián)規(guī)則挖掘用戶會話中頻繁訪問的Edge與用戶會話中所有的Edge相比,是否能夠更準(zhǔn)確地評估Web應(yīng)用的可靠性。

Q2:模擬訪問產(chǎn)生的Web日志與真實(shí)環(huán)境下的Web日志的可靠性度量值MTBF是否相似。

由于Apache服務(wù)器記錄日志時將網(wǎng)頁中的文件引用也作為一次記錄,故用戶的一次請求會包含多條記錄,如后綴為jpg、png、gif等圖像文件的引用,doc、TXT、PDF等文本文件的引用等,因此,本次實(shí)驗(yàn)去除多余的日志訪問記錄。

3.2 結(jié)果分析

表3 原始Edge與頻繁訪問Edge的可靠性測量結(jié)果Table 3 Reliability measurement results of original Edge and frequently accessed Edge

由于該網(wǎng)站為校園門戶網(wǎng)站,通過分析發(fā)現(xiàn),鏈接跳轉(zhuǎn)發(fā)生次數(shù)最多的是各學(xué)院以及各單位的官網(wǎng)及其子鏈接,其中,11月份臨近研究生考試,研究生官網(wǎng)“http://yjsc.shnu.edu.cn”及其各子鏈接跳轉(zhuǎn)最頻繁。通過統(tǒng)計得到,10 d中的鏈接跳轉(zhuǎn)總次數(shù)為366 807,錯誤數(shù)為51 415,MTBF值為7.13,平臺可靠性評估值為85.98%。而關(guān)聯(lián)規(guī)則挖掘后頻繁訪問的鏈接跳轉(zhuǎn)總次數(shù)為52 048,錯誤數(shù)為773,MTBF值為67.30,平臺可靠性評估值為98.51%,如表4所示。因此,該網(wǎng)站存在的大量不頻繁訪問鏈接對Web應(yīng)用的可靠性評估產(chǎn)生了較大的影響,在評估門戶網(wǎng)站的可靠性時,需針對用戶頻繁訪問的跳轉(zhuǎn)鏈接進(jìn)行測試。

表4 MTBF與R統(tǒng)計結(jié)果Table 4 Statistical results of MTBF and R

通過關(guān)聯(lián)規(guī)則挖掘共得到399組頻繁訪問鏈接,將其作為馬爾科夫模型中的狀態(tài)轉(zhuǎn)移弧,其中,部分狀態(tài)轉(zhuǎn)移弧的轉(zhuǎn)移概率如表5所示,本文采用2.3節(jié)馬爾科夫模型以及2.4節(jié)輪盤賭算法生成3組測試用例,3組測試用例都包含150條最大長度為10的訪問序列,通過執(zhí)行測試用例對Web站點(diǎn)進(jìn)行模擬訪問,分析模擬訪問后的訪問日志與錯誤日志,結(jié)果如表6所示。3組測試用例得到的3組MTBF值分別為67.68、69.75、66.36,與真實(shí)情況下的MTBF值(67.80)相似,平臺可靠性評估值分別為98.52%、98.56%、98.49%。測試用例產(chǎn)生的Web日志與真實(shí)環(huán)境下的Web日志在評估Web應(yīng)用可靠性時,可靠性度量值MTBF相似。

表5 馬爾科夫模型的部分狀態(tài)轉(zhuǎn)移弧及其概率分布情況

Table 5 Some state transition arcs of Markov model and the probability distribution

Referrer(Inside)URL轉(zhuǎn)移概率/% http://www.shnu.edu.cn/26/list.htmhttp://cwc.shnu.edu.cn31.16http://jwc.shnu.edu.cn27.19http://hr.shnu.edu.cn15.37http://yjsc.shnu.edu.cn14.34http://xgb.shnu.edu.cn6.53http://shkch.shnu.edu.cn5.41http://yjsc.shnu.edu.cn/17206/list.htm17.98http://yjsc.shnu.edu.cn/17192/list.htm16.42http://yjsc.shnu.edu.cnhttp://yjsc.shnu.edu.cn/17205/list.htm15.50http://yjsc.shnu.edu.cn/17204/list.htm13.51http://yjsc.shnu.edu.cn/6d/89/c17243a 683401/page.htm12.84http://yjsc.shnu.edu.cn/38/82/c17243a 669826/page.htm9.98http://yjsc.shnu.edu.cn/38/0f/c17243a 669711/page.htm8.52http://yjsc.shnu.edu.cn/17243/list.htm5.25

表6 測試用例執(zhí)行結(jié)果Table 6 Test case execution results

針對Q1,本文實(shí)驗(yàn)分析關(guān)聯(lián)規(guī)則挖掘前后的鏈接跳轉(zhuǎn)數(shù)據(jù),結(jié)果表明,與用戶會話中所有Edge相比,在Web統(tǒng)計測試中通過關(guān)聯(lián)規(guī)則挖掘用戶會話中頻繁訪問的Edge,可以更準(zhǔn)確地評估Web應(yīng)用的可靠性。針對Q2,本文實(shí)驗(yàn)利用生成的測試用例對Web應(yīng)用進(jìn)行測試,結(jié)果表明,測試用例產(chǎn)生的Web日志與真實(shí)環(huán)境下的Web日志在評估Web應(yīng)用可靠性時,度量值MTBF相近,即驗(yàn)證了本文方法的有效性。

4 結(jié)束語

本文提出一種基于關(guān)聯(lián)規(guī)則的Web應(yīng)用統(tǒng)計測試方法,該方法從服務(wù)器日志中提取用戶訪問信息,采用關(guān)聯(lián)規(guī)則以及自定義結(jié)構(gòu)note挖掘用戶的頻繁訪問序列,通過構(gòu)建馬爾科夫模型并采用輪盤賭算法生成測試用例。實(shí)驗(yàn)結(jié)果表明,該方法可以更準(zhǔn)確地評估Web應(yīng)用的可靠性。本文實(shí)驗(yàn)環(huán)境相對穩(wěn)定,選用的研究對象為校園門戶網(wǎng)站,網(wǎng)站功能較單一,下一步將選擇不同復(fù)雜度的Web應(yīng)用系統(tǒng)(如商業(yè)化網(wǎng)站)對本文方法進(jìn)行測試,同時優(yōu)化關(guān)聯(lián)規(guī)則,以提高Web測試和可靠性評估的準(zhǔn)確性與效率。