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

侯美靜 崔艷鵬 胡建偉

(西安電子科技大學網絡與信息安全學院 陜西 西安 710000)

0 引 言

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

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

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

1 智能爬行策略

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

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

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

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

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

圖1 智能爬行算法圖

2 智能爬行算法

2.1 URL去重

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

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

圖3 URL分片對應圖

圖2 URL格式圖

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

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

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

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

表1 存在URL的常見標簽及屬性

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

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

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

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

2.2 頁面相似度

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

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

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

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

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

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

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

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

圖4 兩個HTML頁面源碼圖

首先構建兩個頁面對應的DOM樹，DOM樹的節(jié)點就是HTML頁面的標簽，文本內容統(tǒng)一用text表示，如圖5所示。

圖5 兩個HTML頁面的DOM樹圖

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

圖6 兩棵DOM樹的權重分配圖

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

2.3 聚 類

智能爬行算法的第三階段就是以網頁相似度為基礎，利用聚合式層次聚類思想，將結構相似的網頁聚為一組，取出一個作為代表URL。

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

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

算法步驟如下：

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

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

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

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

第五步：取代表URL。

3 測 試

3.1 實驗環(huán)境

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

3.2 實驗內容

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

3.3 爬取結果分析

分別對三個網站進行了測試，爬取結果如表2所示。

表2 深度爬蟲和智能爬蟲對比結果

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

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

表3 http://www.freebuf.com網站深度爬蟲爬取結果分析

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

表4 https://www.douban.com網站深度爬蟲爬取結果分析

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

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

圖7 深度爬蟲部分爬取結果圖

圖8 智能爬蟲部分爬取結果圖

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

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

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

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

4 結 語

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