基于爬蟲的智能爬行算法研究

侯美靜 崔艷鵬 胡建偉

(西安電子科技大學(xué)網(wǎng)絡(luò)與信息安全學(xué)院 陜西 西安 710000)

0 引 言

基于Web系統(tǒng)的多層體系結(jié)構(gòu)以及與其他不同類型的子系統(tǒng)之間的復(fù)雜交互，增加了可以被攻擊者利用的安全漏洞的數(shù)量。正如開放式Web應(yīng)用程序安全項目OWASP(Open Web Application Security Project)[1]所強調(diào)的那樣，攻擊者可能會沿著基礎(chǔ)結(jié)構(gòu)跟蹤各種路徑，以發(fā)現(xiàn)可能會導(dǎo)致嚴(yán)重后果的安全漏洞。我們就需要對Web應(yīng)用執(zhí)行例行巡檢，采取必要的行動降低安全風(fēng)險。軟件開發(fā)人員通常使用Web應(yīng)用巡檢系統(tǒng)來自動檢查其基于Web應(yīng)用程序的安全性，并對許多不同的Web應(yīng)用程序進行大規(guī)模安全分析[2-3]。

在Web應(yīng)用巡檢系統(tǒng)里，爬蟲是按照一定的爬行策略，做站內(nèi)的URL爬取，從而獲得目標(biāo)網(wǎng)站下所有的可視或不可視的URL信息。巡檢系統(tǒng)對于所有的URL進行安全審計，但是對于同源網(wǎng)站來說，存在大量結(jié)構(gòu)相似的URL和網(wǎng)頁，對于此類URL和網(wǎng)頁，重復(fù)地審計不會發(fā)現(xiàn)新的漏洞?，F(xiàn)在的爬蟲技術(shù)多采用URL相似性去重，雷佳偉[4]通過研究Scrapy爬蟲框架，分析頁面爬取及解析的過程，并研究了URL相似性去重，但是這種方法會將大量的非相似的網(wǎng)頁去重，失誤率過高。賀建英[5]針對搜索引擎提出了一種基于Rabin指紋算法進行URL去重、網(wǎng)頁內(nèi)容相似和相同去重，將網(wǎng)頁文檔進行定長分塊，然后用Rabin指紋算法計算每個網(wǎng)頁塊的指紋，通過比對兩個網(wǎng)頁分塊指紋的重復(fù)率來判定網(wǎng)頁是否相似，這種方法只適用于網(wǎng)頁結(jié)構(gòu)絕對類似，網(wǎng)頁內(nèi)容相同的的情況。而其他人[6-7]關(guān)注更多的是爬蟲的覆蓋率，只是進行URL去重，并沒有考慮網(wǎng)頁相似的問題，而對參數(shù)進行模糊測試的方法查找漏洞。開發(fā)人員盡量避免在URL里顯示明顯的參數(shù)，所以已有的技術(shù)不能滿足Web應(yīng)用巡檢系統(tǒng)的需求。

針對以上文獻中的不足，本文針對智能巡檢系統(tǒng)提出了一種基于URL去重和以網(wǎng)頁相似度為基礎(chǔ)的聚合式層次聚類的智能爬行算法，能有效地去除重復(fù)的URL和大量結(jié)構(gòu)相似的網(wǎng)頁，最大程度縮小巡檢系統(tǒng)的測試目標(biāo)，提高檢測效率。

1 智能爬行策略

隨著Web應(yīng)用的發(fā)展，爬蟲技術(shù)也在改進。從早期的通用爬蟲到現(xiàn)在的主題爬蟲[8]、深度爬蟲[9]等等，滿足了不同用戶的不同需求。

通用爬蟲的爬取過程比較簡單，一般是從初始的URL開始爬取網(wǎng)頁，將獲得的URL放入待爬取的列表里，等初始頁面爬完，再從待爬取列表里取出新的URL開始爬取，依次循環(huán)，直到待爬取列表為空或者滿足設(shè)置的停止條件。這種方法簡單，比較常用，但是這類爬蟲只是針對URL進行單一爬取，不能滿足用戶額外的需求。

深度爬蟲相對于通用爬蟲來說比較復(fù)雜，對于獲得的頁面不光提取URL，還會進行解析，對URL進行去重，提高了爬行效率避免陷入死循環(huán)。

在深度爬蟲的基礎(chǔ)上，本文提出了一種智能爬蟲策略。智能爬蟲的爬取過程是：以一個初始URL為起點爬取相關(guān)的所有網(wǎng)頁，然后利用智能爬行算法爬取網(wǎng)站，最后得到無重復(fù)的URL，且URL對應(yīng)的網(wǎng)頁結(jié)構(gòu)都是不相似的。本文所提出的智能爬行算法，首先對URL去重丟棄重復(fù)的URL。下一步利用頁面相似度公式依次計算兩個URL對應(yīng)頁面的相似度值，具體是將頁面解析成DOM樹，根據(jù)節(jié)點的位置、DOM樹的深度以及深度相同的節(jié)點數(shù)量，將權(quán)重分配給每個節(jié)點，再根據(jù)給定的公式計算網(wǎng)頁的相似度。最后以相似度為基礎(chǔ)，使用聚合式層次聚類思想將具有相似結(jié)構(gòu)的網(wǎng)頁聚為一組，只選取代表URL進行后續(xù)測試。

本文提出的智能爬行算法的計算過程分三個階段，如圖1所示。第一階段需要對URL去重；第二階段對網(wǎng)頁解析并計算網(wǎng)頁相似度；第三階段將相似度滿足設(shè)定閾值的網(wǎng)頁進行聚類，并從每一類中選取一個URL作為代表進行后續(xù)檢測。整個計算過程稱為智能爬行算法。

圖1 智能爬行算法圖

2 智能爬行算法

2.1 URL去重

URL又稱統(tǒng)一資源定位符，是對互聯(lián)網(wǎng)上資源的位置和訪問方法的一種簡潔的表示，是互聯(lián)網(wǎng)上標(biāo)準(zhǔn)資源的地址[10]。它可以理解為是互聯(lián)網(wǎng)上資源的索引，通過它爬蟲就可以找到新的資源，獲取新的URL。但是并非所有的URL都是可用的，對于重復(fù)的、相似的、存在包含關(guān)系的URL要進行過濾，可以減少重復(fù)爬取的時間，提高智能巡檢系統(tǒng)的整體效率。

URL的完整格式(其中帶[]的為可選項)如圖2所示。圖3為URL分片對應(yīng)圖。

圖3 URL分片對應(yīng)圖

圖2 URL格式圖

URL重復(fù)：兩個URL的協(xié)議、主機名、端口、路徑、參數(shù)名和參數(shù)值完全一樣。

URL相似：兩個URL的協(xié)議、主機名、端口、路徑、參數(shù)名和參數(shù)個數(shù)都相同。

URL包含：兩個URL記為A和B，協(xié)議、主機名、端口、路徑都相同。若A的參數(shù)個數(shù)大于或等于B，且B的參數(shù)名列表與A的參數(shù)名列表存在包含關(guān)系。

在HTML中，URL主要會在下列常見的標(biāo)簽中產(chǎn)生，可以通過其相關(guān)的屬性值來獲取，如表1所示。

表1 存在URL的常見標(biāo)簽及屬性

爬蟲在爬取網(wǎng)頁的過程中，總會出現(xiàn)很多重復(fù)的URL。重復(fù)的爬取不會發(fā)現(xiàn)新的URL鏈接，只會浪費計算資源和延長爬行時間甚至使爬行陷入死循環(huán)。因此，需要過濾這類URL，減少重復(fù)爬取。智能爬行算法的第一階段就是基于Rabin指紋算法[4]對URL去重?；静襟E如下：

(1) 輸入一個URL值作為參數(shù)。

(2) 構(gòu)造一個初始值為0，長度為n的列表L用于存放指紋映射。再構(gòu)造一個空列表U，用于存放爬取過的URL。

(3) 對該URL爬取出的所有url進行循環(huán)，循環(huán)包括：計算每個url的指紋值，將指紋值r映射到列表L中。判斷列表中L[r]的值是否為0，若為0，則將L[r]置為1，并將此url存放入列表U中。若值為1，則舍棄。

2.2 頁面相似度

對于同源網(wǎng)頁，大量的網(wǎng)頁結(jié)構(gòu)是相似的，只是少量內(nèi)容不同。在進行漏洞巡檢時，會對每一個URL進行滲透測試，這樣會做大量的無用工作，浪費時間。也有人通過比對URL的相似度，去除相似的URL，但是這種方式誤差太大，可用性不強。本文提出的智能爬行算法通過比對網(wǎng)頁結(jié)構(gòu)的相似度，當(dāng)相似度達到設(shè)定閾值后，才判定為相似，這種方法對于網(wǎng)頁去重更精確，更具可行性。

智能爬行算法的第二階段就是計算網(wǎng)頁的相似度。這里采用一種基于平均分配權(quán)重的網(wǎng)頁結(jié)構(gòu)相似度測量方法。首先對網(wǎng)頁構(gòu)造DOM樹[11]結(jié)構(gòu)并預(yù)處理，將DOM樹下的標(biāo)簽作為樹的節(jié)點，對于文本內(nèi)容則統(tǒng)一用text表示，只比較兩個頁面的結(jié)構(gòu)相似度。再將權(quán)重平均分配給節(jié)點，具體步驟如下：

① 令整個DOM樹的權(quán)重為1，對于深度為1的根節(jié)點，權(quán)重為1；對于深度為2的根的子節(jié)點，若數(shù)量為n，則每個子節(jié)點的權(quán)重為1/n。

② 將深度為2的節(jié)點的權(quán)重平均分給它的子節(jié)點。

③ 迭代分配，直到樹的葉子節(jié)點。

④ 對于葉子節(jié)點a和b，如果a等于b，那么a和b的相似度就是它們所分配的權(quán)重，若不等于，那么相似度為0。對于非葉子節(jié)點a和b，如果a等于b，那么a和b的相似度就是它們的子節(jié)點的權(quán)重總和，若不等于，那么相似度為0。

⑤ 兩棵DOM樹的相似度就是它們根節(jié)點的相似度。

具體的計算過程，以兩個簡單的HTML頁面為例，兩個HTML頁面的源代碼如圖4所示。

圖4 兩個HTML頁面源碼圖

首先構(gòu)建兩個頁面對應(yīng)的DOM樹，DOM樹的節(jié)點就是HTML頁面的標(biāo)簽，文本內(nèi)容統(tǒng)一用text表示，如圖5所示。

圖5 兩個HTML頁面的DOM樹圖

整個DOM樹的權(quán)重設(shè)為1，從根節(jié)點HTML開始依次平均下發(fā)到葉子節(jié)點，整棵樹的權(quán)重分配如圖6所示。

圖6 兩棵DOM樹的權(quán)重分配圖

根節(jié)點的權(quán)重為1，根節(jié)點下有兩個子節(jié)點，平均分配，每個子節(jié)點的權(quán)重為1/2。依次循環(huán)，直到整棵樹分配完畢，可以看出，所有葉子節(jié)點的權(quán)重相加等于1，所以，我們通過比較同一深度葉子節(jié)點的相似度，得到父節(jié)點的權(quán)重，即：所有相同的子節(jié)點的權(quán)重總和。但是如果父節(jié)點不相同的話，權(quán)重則為0。如DOM樹1中，a標(biāo)簽是img標(biāo)簽的父節(jié)點；DOM樹2中center標(biāo)簽是img標(biāo)簽的父節(jié)點，雖然兩個葉子節(jié)點一樣，但是父節(jié)點是不一樣的，所以a標(biāo)簽和center標(biāo)簽的相似度為0。

計算過程可以描述為：

similar(D1,D2)=similar(D1X11,D2X11)

similar(D1Xnm,D2Xnm)=

式中：D是DOM樹，X11,X21,X22,…,Xnm是樹的節(jié)點，n是樹的深度，根節(jié)點的深度是1，X11代表根節(jié)點，m是節(jié)點的序列號，Xnm代表深度為n的第m個節(jié)點，DiXnm代表第i個樹的Xnm節(jié)點，Num(n)代表深度為n的節(jié)點的數(shù)量。

2.3 聚 類

智能爬行算法的第三階段就是以網(wǎng)頁相似度為基礎(chǔ)，利用聚合式層次聚類思想，將結(jié)構(gòu)相似的網(wǎng)頁聚為一組，取出一個作為代表URL。

因為聚類的集群數(shù)量不確定，聚類的密度也高，只確定相似性的閾值大小，所以該算法對類似于K-means等需要在開始就確定集群數(shù)量的算法不太適用；對于基于密度的方法同樣需要在開始時設(shè)置兩個參數(shù)(半徑和最小數(shù)量)，但我們無法準(zhǔn)確地對兩個參數(shù)進行設(shè)置；基于網(wǎng)格的方法通常適用于多維數(shù)據(jù)；基于模型的方法則需要根據(jù)數(shù)據(jù)集的特征構(gòu)建模型。綜合以上問題，本文選擇基于層次的聚類思想實現(xiàn)網(wǎng)頁聚類。層次聚類有兩種思想[12]，一種是所有的文檔為一個類，之后去做切分，每次可能就會多一個類，叫做分割式聚類；另一種是聚合式聚類，開始每個數(shù)據(jù)都單獨成一類，之后根據(jù)相似度去比對閾值，然后聚類。

利用聚合式層次聚類的思想，以上面的網(wǎng)頁相似度為基礎(chǔ)，將相似度大于閾值的網(wǎng)頁所對應(yīng)的URL放在一個子集中；通過一系列的計算得到若干個子集；再從每個子集中取出一個作為代表URL。

算法步驟如下：

第一步：聚類的對象是去重后的URL列表，設(shè)定一個初始相似度閾值T1。

第二步：在列表中隨機選擇一個URL作為初始點，并計算初始點與列表中其他URL的相似度。

第三步：若網(wǎng)頁之間的相似度大于閾值T1，則將兩個網(wǎng)頁劃分到一個子集中，并將此網(wǎng)頁的URL在列表中置為0；若距離小于閾值T1，則繼續(xù)從列表中取值，直到此網(wǎng)頁和剩余非0網(wǎng)頁比較結(jié)束。

第四步：重復(fù)第二步和第三步，直到列表為空。

第五步：取代表URL。

3 測 試

3.1 實驗環(huán)境

智能爬行策略實驗是在kali虛擬機、內(nèi)存2 GB的硬件環(huán)境下進行的，使用Python語言實現(xiàn)。

3.2 實驗內(nèi)容

利用現(xiàn)有技術(shù)的深度爬蟲和本文的智能爬蟲分別對網(wǎng)站進行爬取。

3.3 爬取結(jié)果分析

分別對三個網(wǎng)站進行了測試，爬取結(jié)果如表2所示。

表2 深度爬蟲和智能爬蟲對比結(jié)果

用深度爬蟲對http://www.freebuf.com網(wǎng)站進行爬取，結(jié)果可達14萬個，而智能爬蟲的爬取結(jié)果只有2 367個，聚類效果明顯，可大量節(jié)省Web應(yīng)用巡檢系統(tǒng)的審計時間。其他網(wǎng)站類似，對https://www.douban.com網(wǎng)站，深度爬蟲爬取結(jié)果為138 655個，而智能爬蟲的爬取結(jié)果為3 856。對于https://www.shiyanlou.com網(wǎng)站，深度爬蟲的爬取結(jié)果為1 764，智能爬蟲的爬取結(jié)果為122。

對于http://www.freebuf.com網(wǎng)站的深度爬蟲爬取結(jié)果進行分析，如表3所示。

表3 http://www.freebuf.com網(wǎng)站深度爬蟲爬取結(jié)果分析

對于https://www.douban.com網(wǎng)站的深度爬蟲爬取結(jié)果進行分析，如表4所示。

表4 https://www.douban.com網(wǎng)站深度爬蟲爬取結(jié)果分析

由表3、表4可知類似的URL有很多，它們對應(yīng)的網(wǎng)頁大多是結(jié)構(gòu)相似的。而智能爬蟲可以有效地將這些結(jié)構(gòu)相似的網(wǎng)頁進行聚類，減少后續(xù)巡檢系統(tǒng)的測試工作。

為了更清晰地展示兩種爬蟲爬取的結(jié)果，我們展示部分爬取結(jié)果，圖7是深度爬蟲的部分爬取結(jié)果圖。圖8是智能爬蟲的部分結(jié)果圖。

圖7 深度爬蟲部分爬取結(jié)果圖

圖8 智能爬蟲部分爬取結(jié)果圖

表5是智能爬行算法在聚類過程中比對的相似度值和聚類過程。

表5 智能爬行算法聚類過程分析

從表中可以看出，智能爬行算法在聚類過程中，先隨機選擇一個URL(表中為URL1)，與剩余的其他URL進行相似度比對，若相似度大于閾值(閾值=0.8)則聚為一組，表中URL1、URL2、URL3、URL7、URL8聚為一組。剩余的URL4、URL5、URL6再重復(fù)上面的步驟，直到所有URL都完成分組，表中URL4、URL5、URL6聚為一組。智能爬行算法最后會在每組中取一個代表URL，圖8就是爬行的結(jié)果。

從圖7和圖8的對比可以看出，深度爬蟲會將所有的網(wǎng)頁爬取出來，存在很多結(jié)構(gòu)相似的網(wǎng)頁。而智能爬蟲可以有效地將結(jié)構(gòu)相似的網(wǎng)頁聚為一類，只取代表URL進行后續(xù)檢測，極大地提高了巡檢系統(tǒng)的效率。

4 結(jié) 語

本文提出了一種智能爬行算法，在爬行過程中采用基于Rabin指紋算法對URL去重，檢索速度快，效率高，且避免爬蟲在爬行過程中浪費不必要的時間，甚至陷入死循環(huán)；在計算網(wǎng)頁相似度前對網(wǎng)頁進行預(yù)處理，構(gòu)建DOM樹，并統(tǒng)一用text表示文本，只保留網(wǎng)頁標(biāo)簽，簡化了網(wǎng)頁，并通過平均分配權(quán)重的方法計算網(wǎng)頁結(jié)構(gòu)相似度，使網(wǎng)頁相似度計算更高效；采用聚合式層次聚類算法將相似性網(wǎng)頁聚為一組，提高了巡檢系統(tǒng)的效率。本文解決了網(wǎng)頁結(jié)構(gòu)大量相似的問題，提高了安全巡檢的效率，而且本方法思路簡單、易于實現(xiàn)、通用性強，對結(jié)構(gòu)相似的網(wǎng)頁識別率高，提高了爬蟲的精確度。