一種高速URL過濾算法的研究與應用

黃誠

（四川大學計算機學院，成都　610065)

一種高速URL過濾算法的研究與應用

黃誠

（四川大學計算機學院，成都610065)

0　引言

當前，大量涉黃涉暴網站盛行，同時每天有成千上萬的網頁更新、上線，傳統的防火墻對于URL的過濾功能基于給定的規則庫，并由管理人員去進行人工管理。因此，對于當前有害URL的過濾工作，當前傳統防火墻顯得能力不足。而且，當前的URL過濾算法設計相對簡單，對于大量用戶訪問網站時，過濾效率明顯不足。通過使用網絡爬蟲去爬取網頁并對爬取得網頁內容進行文本分析，從而建立黑、白名單，使得黑白名單的規模快速擴大，自動化的擴容黑白名單，減輕管理員的工作壓力也使得過濾系統能夠過濾更多的URL。

當黑白名單的容量過大時，簡單的使用HashMap結構用于URL過濾，將無法滿足系統對于實時性的要求。因此，設計出結合 Bloom Filter算法的改進HashMap結構，用于提高URL的過濾效率。由于URL地址在整個網絡空間中是唯一的，根據這一特性，可以將其轉化為另外一種表現方式。同時，一般情況下，存儲URL長度會大于16字節，使用MD5對URL計算摘要值之后URL將轉化為16字節長度的字符，可以明顯的減少存儲URL時所占用的內存，既節省空間，也能夠提高URL的匹配效率，從而提高整個系統性能。

1　系統架構

本文中的URL過濾系統分為四個獨立模塊，分別為網絡爬蟲模塊、文件緩沖區、敏感詞過濾模塊和URL過濾模塊，模塊間關系如下圖所示：

圖1　

工作步驟如下：

網絡爬蟲模塊：使用網絡爬蟲，從互聯網上面去爬取網頁，并將爬取回來的網頁存放在文件緩沖區中，作為敏感詞過濾模塊的輸入。

文件緩沖區模塊：是在系統磁盤上開辟一塊大的空白區域，用來存放網絡爬蟲爬取的網頁內容，解決網絡爬蟲爬取網頁速度過快與敏感詞過濾模塊處理速度不一致的問題。

敏感詞過濾模塊：將文件緩沖區中存放的網頁進行敏感詞過濾，結合給定的敏感詞庫判定相關聯的URL是否非法，如果為非法則將結果添加到URL過濾模塊的黑名單中，否則，將結果加入到URL過濾模塊的白名單。

URL過濾模塊：將黑白名單中的所有結果作為輸入，使用MD5算法逐條對URL計算摘要值，將摘要值添加到改進的HashMap結構中，用于URL過濾。

2　URL過濾模型

當局域網中用戶在瀏覽器中輸入URL地址完畢，并向外發送請求之后，部署在網關設備將URL內容捕獲，并將URL值傳遞給URL過濾模塊，開始URL過濾過程，匹配流程如圖2所示：

圖2　

URL過濾模塊獲取到輸入之后，首先計算出MD5摘要值，將計算出的摘要值進行布隆過濾，如果匹配失敗，表示該URL還未加入到黑白名單中，直接將該URL放入網絡爬蟲優先處理隊列；否則，進行黑名單過濾。

為了提高訪問效率，將摘要值進行黑名單過濾（非法網址數量遠遠效率合法網址數量），如果不在黑名單中，則允許用戶訪問該網址。

再將該URL進行白名單過濾，如果出現在白名單中，此次過濾過程結束。否則，將該URL反饋給網絡爬蟲模塊，優先對該URL進行爬取，爬取完畢之后迅速進行敏感詞過濾，并將結果添加到URL過濾模塊的黑白名單中。

3　主要工作

Bloom Filter[1]是一種二進制向量數據結構，被用來檢測一個元素是否是集合的一個成員，具有很高的時間效率和空間效率。它采用一個長度為m的向量來的表現一個大小為n的集合S，并能判斷一個元素是否的集合S中。向量m中所有位初始值為0。Bloom Filter采用t個相互獨立的hash函數h1，h2，…，ht將集合中的每個元素散列到1到m的范圍中。對于給定的元素，位置為hi（x）的比特位都置為1，其中 。判斷元素y是否屬于集合S時，只需要分別計算hi（y），如果所有向量上對應的比特位位置為1，則認為 ，否則認為 。由Bloom Filter的特點，如果y元素判定不在集合S中，則y元素一定不在集合S中。如果y元素判定在集合S中，則y元素不一定在集合S中，設Bloom Filter誤判的概率為f。

f是關于m，n，t的函數，表示為：

我們對用戶訪問互聯網采取“第一次允許策略”[2]，即當用戶訪問的URL不在黑白名單中時，我們首先是讓用戶繼續訪問網頁，同時將該URL進行優先處理，當任何用戶第二次輸入該URL訪問網頁時，則可對此URL進行黑白名單過濾。

此處引入Bloom Filter的主要有以下作用，我們用給定的黑白名單對Bloom Filter的位圖進行初始化，當進行URL過濾時，我們首先用Bloom Filter進行一次過濾，如果匹配失敗，由Bloom Filter的特點，如果y元素判定不在集合S中，則y元素一定不在集合S中，則直接將URL加入爬蟲優先處理隊列，減少無效的黑白名單匹配。如果匹配成功，則繼續URL模塊中所設定的過濾流程。

Hash表可以看成一個數組，數組的每個元素稱為“桶”（Bucket），每個Bucket使用一個鏈表來處理節點沖突，假設Hash表有m個Bucket和n個元素，那么在表中查找一個元素的平均時間的復雜度是O（m/n）。采用更大的哈希表可以獲得更好的性能。當 m＞＞n時，復雜度趨向于O（1）。另外，好的哈希函數能夠將元素更均勻地分布在各個Bucket上，從而提高Hash表的性能。

從以上的介紹中可以得知，使用Hash進行元素查找時，可以提高查找性能，同時，在同一個“桶”（Bucket）所對應的沖突鏈上進行元素查找時，假設沖突鏈長為l，則查找性能為O（l），這表示查找性能有提高的空間。

位圖法，就是用一個bit來存放某一種狀態，用0 和1來表示。一般情況下，會在系統內存中開辟一塊空間，然后初值全部置為0。設開辟的空間有n個bit位，當第k（1≤k≤n）為置為1時，表示序號為k的元素存在。

圖3　

在改進的hash[3-4]表中，以URL地址的MD5摘要值作為輸入參數，設附加在桶（Bucket）一側的位圖大小為w，數組預分配的空間大小為M，空間內可容納的摘要值個數為p，則有：M=p*16B，w≤p。

在本文所描述的系統中，所有的URL地址將轉化為MD5摘要值進行處理。設URL為MD5的輸入參數，輸出結果為R，則R的長度為128Bytes，R可由16B的內存空間進行存儲。

在改進的hash表中，在“桶”（Bucket）的一側附加了一個容量為w的位圖，為了解決沖突，使用的是一個內存空間連續的數組，用數組了取代鏈表結構。對hash表初始化時，設MD5摘要值的大小為16Bytes，數組預分配的空間大小為M，空間內可容納的摘要值個數為p，則有：M=p*16B，w≤p。

引入位圖的作用在于以下兩點：

對于將要插入到hash中的URL而言，此URL的MD5摘要值為m，第一步：我們對將要插入hash表中的url進行下面的處理，hash（m）%n=k，找出該URL將要插入第k個數組上。第二步：我們使用哈希函數，進行如下處理 ，此時如果在第k個位圖中，第i位值為0時，表示對應數組第i個元素為空，可直接將m值寫入該位置。如果第i位的值為1，表示此時產生了hash沖突，我們從i開始朝后遍歷數組，直到找到某一位數組元素為空時，將m值寫到此位置。如果一直到數組末尾仍然沒有發現為空的元素，則重新申請數組空間，空間大小為p*r，其中r為我們定義的擴充因子且r＞1，再將原來數組復制到新的數組中，復制完畢之后，釋放原來的數組空間。

對于要在該改進的hash表中過濾的指定的url是否存在時，此URL的MD5摘要值為q，第一步：我們對將要中的過濾URL進行下面的處理，hash（q）%n=z，找出該URL可能存在的第z個數組。第二步：我們使用哈希函數H，進行如下處理H（q）%w=c，如果此時，第z位圖上第c位為0，則表示匹配失敗，如果第z位圖上第c位為1，則從數組的第c位開始往后遍歷，如果和數組中的元素完全匹配，則返回匹配成功；如果遇到數組上某個元素為空、直到數組末尾任然未匹配完成，則返回匹配失敗。

4　仿真實驗和實驗分析

由于是進行仿真實驗，用程序生成了多條URL，將生成的URL緩存在內存空間中，分別用普通hash表和改進的hash表來構建黑白名單且黑白名單的大小均為10000條URL，每個hash表中的Bucket數目均為100，然后進行URL過濾，比較普通hash表和改進hash表對于的比較次數和比較時間上的區別。

通過以上的實驗結果可以看出，使用改進的hash表結構進行URL過濾，在比較次數和比較時間上比傳統hash過濾方式在比較，減少了比較次數和比較時間，提高了過濾效率。

5　仿真實驗和實驗分析

本文通過使用設計了一種局域網內URL過濾系統，主要的工作在于對于URL過濾效率的改進，因為黑白名單的只能覆蓋極少數的網頁，使用Bloom Filter對于URL進行第一次過濾時，可以將不在黑白名單中的網頁立刻加入優先處理隊列，從而減少了無效的黑白名單匹配。利用位圖法改進的hash表在URL的匹配過程中能夠做到一定程度的隨機訪問，與鏈表從頭到尾的匹配方式相比，減少了在黑白名單中的比較次數。該方法相對于Bloom Filter，杜絕了誤判的可能。和傳統的hash表進行URL過濾相比，減少了無效匹配的次數，極大地提高了匹配效率。

圖4　

圖5　

[1]劉慶.一種基于并行的Bloom Filter的高速URL查找算法[J].電子學報,2015（9）,1833-1840

[2]徐劍.面向分布式查詢認證的分層hash鏈表[J].計算機研究與發展,2012（3）,1533-1544

[3]李曉明.兩種對URL效果很好的散列函數[J].軟件學報,2004（2）,179-185

[4]劉燕兵.一種面向大規模URL過濾的多模式串匹配算法[J].計算機學報,2014（5）,1160-1168

URL filter;Web Crawler;Sensitive Word Filtering;Bloom Filter;Hash Table;MD5

Research and Application of a High Speed URL Filtering Algorithm

HUANG Cheng
（College of Computer Science，Sichuan University，Chengdu610065）

1007-1423（2016）03-0013-04

10.3969/j.issn.1007-1423.2016.03.003

黃誠（1987-），男，湖南常德人，碩士研究生，研究方向為信息安全

2015-12-21

2016-01-10

當前，傳統防火墻的URL過濾方式只是對于規則庫中的URL進行過濾，對于新增的涉黃涉暴網站無能為力，或者管理員響應遲鈍。針對當前這種現狀，提出一種局域網內URL過濾系統，基于網絡爬蟲和敏感詞過濾技術通過爬去網頁文本和對于網頁文本分析來判斷指定URL是否合法。考慮到匹配效率和本過濾系統所使用的內存空間，使用MD5 對URL計算摘要值，在此之上建立黑白名單，再結合Bloom Filter算法和改進的Hash表數據結構用以實現對URL的高速過濾。

URL過濾；網絡爬蟲；敏感詞過濾；Bloom Filter；Hash表；MD5

Recently,traditional URL filtering firewall rule base only for URL filtering,for the new added website involving violence powerless,or the administrator unresponsive.For this view of the current situation,proposes a URL filtering system within a local area network,which is based on climbing web pages for text and analyzing text to determine the lawfulness of the specified URL,considering the matching efficiency of the words and the use of memory space in this system,uses the MD5 digest value calculated on the URL,builds on top of this black and white lists,combining Bloom Filter algorithm with improved HashMap data structure to achieve high speed for URL filtering.