黃誠

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都　610065)

一種高速URL過濾算法的研究與應(yīng)用

黃誠

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065)

0　引言

當(dāng)前，大量涉黃涉暴網(wǎng)站盛行，同時每天有成千上萬的網(wǎng)頁更新、上線，傳統(tǒng)的防火墻對于URL的過濾功能基于給定的規(guī)則庫，并由管理人員去進(jìn)行人工管理。因此，對于當(dāng)前有害URL的過濾工作，當(dāng)前傳統(tǒng)防火墻顯得能力不足。而且，當(dāng)前的URL過濾算法設(shè)計(jì)相對簡單，對于大量用戶訪問網(wǎng)站時，過濾效率明顯不足。通過使用網(wǎng)絡(luò)爬蟲去爬取網(wǎng)頁并對爬取得網(wǎng)頁內(nèi)容進(jìn)行文本分析，從而建立黑、白名單，使得黑白名單的規(guī)?？焖贁U(kuò)大，自動化的擴(kuò)容黑白名單，減輕管理員的工作壓力也使得過濾系統(tǒng)能夠過濾更多的URL。

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

1　系統(tǒng)架構(gòu)

本文中的URL過濾系統(tǒng)分為四個獨(dú)立模塊，分別為網(wǎng)絡(luò)爬蟲模塊、文件緩沖區(qū)、敏感詞過濾模塊和URL過濾模塊，模塊間關(guān)系如下圖所示：

圖1　

工作步驟如下：

網(wǎng)絡(luò)爬蟲模塊：使用網(wǎng)絡(luò)爬蟲，從互聯(lián)網(wǎng)上面去爬取網(wǎng)頁，并將爬取回來的網(wǎng)頁存放在文件緩沖區(qū)中，作為敏感詞過濾模塊的輸入。

文件緩沖區(qū)模塊：是在系統(tǒng)磁盤上開辟一塊大的空白區(qū)域，用來存放網(wǎng)絡(luò)爬蟲爬取的網(wǎng)頁內(nèi)容，解決網(wǎng)絡(luò)爬蟲爬取網(wǎng)頁速度過快與敏感詞過濾模塊處理速度不一致的問題。

敏感詞過濾模塊：將文件緩沖區(qū)中存放的網(wǎng)頁進(jìn)行敏感詞過濾，結(jié)合給定的敏感詞庫判定相關(guān)聯(lián)的URL是否非法，如果為非法則將結(jié)果添加到URL過濾模塊的黑名單中，否則，將結(jié)果加入到URL過濾模塊的白名單。

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

2　URL過濾模型

當(dāng)局域網(wǎng)中用戶在瀏覽器中輸入U(xiǎn)RL地址完畢，并向外發(fā)送請求之后，部署在網(wǎng)關(guān)設(shè)備將URL內(nèi)容捕獲，并將URL值傳遞給URL過濾模塊，開始URL過濾過程，匹配流程如圖2所示：

圖2　

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

為了提高訪問效率，將摘要值進(jìn)行黑名單過濾（非法網(wǎng)址數(shù)量遠(yuǎn)遠(yuǎn)效率合法網(wǎng)址數(shù)量），如果不在黑名單中，則允許用戶訪問該網(wǎng)址。

再將該URL進(jìn)行白名單過濾，如果出現(xiàn)在白名單中，此次過濾過程結(jié)束。否則，將該URL反饋給網(wǎng)絡(luò)爬蟲模塊，優(yōu)先對該URL進(jìn)行爬取，爬取完畢之后迅速進(jìn)行敏感詞過濾，并將結(jié)果添加到URL過濾模塊的黑白名單中。

3　主要工作

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

f是關(guān)于m，n，t的函數(shù)，表示為：

我們對用戶訪問互聯(lián)網(wǎng)采取“第一次允許策略”[2]，即當(dāng)用戶訪問的URL不在黑白名單中時，我們首先是讓用戶繼續(xù)訪問網(wǎng)頁，同時將該URL進(jìn)行優(yōu)先處理，當(dāng)任何用戶第二次輸入該URL訪問網(wǎng)頁時，則可對此URL進(jìn)行黑白名單過濾。

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

Hash表可以看成一個數(shù)組，數(shù)組的每個元素稱為“桶”（Bucket），每個Bucket使用一個鏈表來處理節(jié)點(diǎn)沖突，假設(shè)Hash表有m個Bucket和n個元素，那么在表中查找一個元素的平均時間的復(fù)雜度是O（m/n）。采用更大的哈希表可以獲得更好的性能。當(dāng) m＞＞n時，復(fù)雜度趨向于O（1）。另外，好的哈希函數(shù)能夠?qū)⒃馗鶆虻胤植荚诟鱾€Bucket上，從而提高Hash表的性能。

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

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

圖3　

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

在本文所描述的系統(tǒng)中，所有的URL地址將轉(zhuǎn)化為MD5摘要值進(jìn)行處理。設(shè)URL為MD5的輸入?yún)?shù)，輸出結(jié)果為R，則R的長度為128Bytes，R可由16B的內(nèi)存空間進(jìn)行存儲。

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

引入位圖的作用在于以下兩點(diǎn)：

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

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

4　仿真實(shí)驗(yàn)和實(shí)驗(yàn)分析

由于是進(jìn)行仿真實(shí)驗(yàn)，用程序生成了多條URL，將生成的URL緩存在內(nèi)存空間中，分別用普通hash表和改進(jìn)的hash表來構(gòu)建黑白名單且黑白名單的大小均為10000條URL，每個hash表中的Bucket數(shù)目均為100，然后進(jìn)行URL過濾，比較普通hash表和改進(jìn)hash表對于的比較次數(shù)和比較時間上的區(qū)別。

通過以上的實(shí)驗(yàn)結(jié)果可以看出，使用改進(jìn)的hash表結(jié)構(gòu)進(jìn)行URL過濾，在比較次數(shù)和比較時間上比傳統(tǒng)hash過濾方式在比較，減少了比較次數(shù)和比較時間，提高了過濾效率。

5　仿真實(shí)驗(yàn)和實(shí)驗(yàn)分析

本文通過使用設(shè)計(jì)了一種局域網(wǎng)內(nèi)URL過濾系統(tǒng)，主要的工作在于對于URL過濾效率的改進(jìn)，因?yàn)楹诎酌麊蔚闹荒芨采w極少數(shù)的網(wǎng)頁，使用Bloom Filter對于URL進(jìn)行第一次過濾時，可以將不在黑白名單中的網(wǎng)頁立刻加入優(yōu)先處理隊(duì)列，從而減少了無效的黑白名單匹配。利用位圖法改進(jìn)的hash表在URL的匹配過程中能夠做到一定程度的隨機(jī)訪問，與鏈表從頭到尾的匹配方式相比，減少了在黑白名單中的比較次數(shù)。該方法相對于Bloom Filter，杜絕了誤判的可能。和傳統(tǒng)的hash表進(jìn)行URL過濾相比，減少了無效匹配的次數(shù)，極大地提高了匹配效率。

圖4　

圖5　

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

[2]徐劍.面向分布式查詢認(rèn)證的分層hash鏈表[J].計(jì)算機(jī)研究與發(fā)展,2012（3）,1533-1544

[3]李曉明.兩種對URL效果很好的散列函數(shù)[J].軟件學(xué)報(bào),2004（2）,179-185

[4]劉燕兵.一種面向大規(guī)模URL過濾的多模式串匹配算法[J].計(jì)算機(jī)學(xué)報(bào),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-），男，湖南常德人，碩士研究生，研究方向?yàn)樾畔踩?/p>

2015-12-21

2016-01-10

當(dāng)前，傳統(tǒng)防火墻的URL過濾方式只是對于規(guī)則庫中的URL進(jìn)行過濾，對于新增的涉黃涉暴網(wǎng)站無能為力，或者管理員響應(yīng)遲鈍。針對當(dāng)前這種現(xiàn)狀，提出一種局域網(wǎng)內(nèi)URL過濾系統(tǒng)，基于網(wǎng)絡(luò)爬蟲和敏感詞過濾技術(shù)通過爬去網(wǎng)頁文本和對于網(wǎng)頁文本分析來判斷指定URL是否合法?？紤]到匹配效率和本過濾系統(tǒng)所使用的內(nèi)存空間，使用MD5 對URL計(jì)算摘要值，在此之上建立黑白名單，再結(jié)合Bloom Filter算法和改進(jìn)的Hash表數(shù)據(jù)結(jié)構(gòu)用以實(shí)現(xiàn)對URL的高速過濾。

URL過濾；網(wǎng)絡(luò)爬蟲；敏感詞過濾；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.