一種基于關聯規則的Web應用統計測試方法

王玉奇,高建華

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

0 概述

隨著互聯網技術及其應用的快速發展,保證Web應用的可靠性日益重要,Web統計測試可以有效確保Web應用的質量,其基于用戶的使用場景和頻率進行優先測試,將統計方法學的理論應用到軟件測試中。研究人員針對Web統計測試做了大量研究。文獻[1]提出Web統計測試與馬爾科夫模型構建方法,通過分析Web訪問日志與錯誤日志,使用馬爾科夫模型對Web應用進行測試和可靠性評估。文獻[2]闡述了馬爾科夫模型應用于Web統計測試以及構建Web使用模型過程中的可行性,通過從Web服務器日志中統計網頁的使用頻率進行測試,將馬爾科夫模型作為統計測試、性能評估與可靠性分析的基礎。文獻[3]提出了一種基于UML的馬爾科夫模型構建方法,并將馬爾科夫模型分為測試用例級與場景級兩類,通過馬爾科夫模型生成軟件測試用例。文獻[4]提出改進的Apriori算法以挖掘Web訪問序列,以此預測用戶的下一個頁面請求以及改進Web站點的拓撲結構。文獻[5]提出應用關聯規則對Web用戶進行區域劃分的方法,其對Web的用戶行為進行分析并實現頁面推薦。

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

1 Web日志與關聯規則

本文首先獲取服務器日志,通過使用哈希表與自定義結構note存儲并描述用戶的行為記錄,利用關聯規則對用戶會話Session進行挖掘,以得到用戶會話中的頻繁訪問頁面,從而構建Web統計測試的馬爾科夫模型。基于關聯規則的Web統計測試方法框架如圖1所示。

圖1 基于關聯規則的Web統計測試方法框架

1.1 Web服務器日志

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

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

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

1)C-IP:訪問者IP。

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

3)Date:訪問日期。

4)Time:訪問時間。

5)Referrer:引用鏈接。

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

7)SC-Bytes:服務器向客戶端發送的字節數。

8)Time-Taken:服務器接收請求到發送響應內容間的時間間隔。

1.2 自定義數據結構note

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

定義1數據結構note=為一個三元組,可以描述用戶的一次行為,其中,各元素含義如下:

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

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

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

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

圖2 用戶行為分離示意圖

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

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

輸入訪問日志

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

步驟1讀取一條日志,通過note結構表示該條日志。將IP地址中每個字符的ASCII碼相加并進行模運算,將運算結果作為哈希表的索引值。

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

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

步驟4重復執行步驟1～步驟3,直到日志記錄遍歷結束。

1.3 關聯規則

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

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

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

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

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

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

6)非頻繁項集:項集的出現頻率小于最小支持度。

設候選項集I={A,B,C,D}是含有4個不同項的集合,數據庫D是針對I的事務集合,共包含6個事務,如表2所示。考慮A與B的關聯規則(頻繁-2項集),事務1、2、3、4、6包含A,事務1、2、6同時包含A與B,則支持度support(A)=5/6,support(A∪B)=3/6。若給定最小支持度為0.5,則認為A與B存在關聯。

表2 關聯規則數據庫Table 2 Database of association rules

1.4 基于興趣度的會話挖掘

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

輸出L2/*頁面的頻繁2-項集*/

步驟1生成頁面的頻繁1-項集L1

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

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

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

4)重復執行步驟2)、步驟3),直到CurrentURL指向URLn結束,得到頁面的頻繁1-項集L1。

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

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

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

4)重復執行步驟2)、步驟3),直到CurrentEdge指向會話中的最后一個Edge結束,得到頁面的頻繁2-項集L2。

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

2 基于關聯規則的Web統計測試方法

2.1 Web統計測試

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

1)基于軟件真實使用場景和相關的頻率構建統計測試模型。

2)根據統計測試模型生成測試用例并篩選和執行測試。

3)分析測試結果,進行可靠性評估與預測。

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

2.2 馬爾科夫模型主要元素

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

3)轉移概率:指軟件從一個狀態空間轉移到其他狀態空間的概率。從某一狀態空間到其他狀態空間的轉移概率之和為1。

2.3 馬爾科夫模型構建

圖3 用戶會話集合示意圖

圖4 用戶會話分離示意圖

圖5 馬爾科夫有向圖

圖6 馬爾科夫模型

2.4 測試用例生成

算法3Routlette-Wheel-Selection算法

輸出Statev/*跳轉到的頁面鏈接*/

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/*一組測試用例中的測試用例個數*/

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

輸出cases

1.assigncases←an object of List

/*測試用例的結果*/

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用來記錄當前頁面*/

6.assign u←Outside/*馬爾科夫模型入口點*/

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的測試用例。首先,從入口點開始調用算法3生成下一頁面鏈接,然后循環M次生成一個長度為M的測試用例case =<(Edge1),(Edge2),…>,最后將上述過程循環N次生成N條測試用例cases=<(case1),(case2),…>。

3 實驗結果與分析

3.1 實驗環境

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

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

Q1:在Web統計測試中,通過關聯規則挖掘用戶會話中頻繁訪問的Edge與用戶會話中所有的Edge相比,是否能夠更準確地評估Web應用的可靠性。

Q2:模擬訪問產生的Web日志與真實環境下的Web日志的可靠性度量值MTBF是否相似。

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

3.2 結果分析

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

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

表4 MTBF與R統計結果Table 4 Statistical results of MTBF and R

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

表5 馬爾科夫模型的部分狀態轉移弧及其概率分布情況

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

Referrer(Inside)URL轉移概率/% 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 測試用例執行結果Table 6 Test case execution results

針對Q1,本文實驗分析關聯規則挖掘前后的鏈接跳轉數據,結果表明,與用戶會話中所有Edge相比,在Web統計測試中通過關聯規則挖掘用戶會話中頻繁訪問的Edge,可以更準確地評估Web應用的可靠性。針對Q2,本文實驗利用生成的測試用例對Web應用進行測試,結果表明,測試用例產生的Web日志與真實環境下的Web日志在評估Web應用可靠性時,度量值MTBF相近,即驗證了本文方法的有效性。

4 結束語

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