黃誠(chéng)

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

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

黃誠(chéng)

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

0　引言

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

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

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

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

圖1　

工作步驟如下：

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

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

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

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

2　URL過(guò)濾模型

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

圖2　

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

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

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

3　主要工作

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

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

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

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

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

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

圖3　

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

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

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

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

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

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

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

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

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

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

本文通過(guò)使用設(shè)計(jì)了一種局域網(wǎng)內(nèi)URL過(guò)濾系統(tǒng)，主要的工作在于對(duì)于URL過(guò)濾效率的改進(jìn)，因?yàn)楹诎酌麊蔚闹荒芨采w極少數(shù)的網(wǎng)頁(yè)，使用Bloom Filter對(duì)于URL進(jìn)行第一次過(guò)濾時(shí)，可以將不在黑白名單中的網(wǎng)頁(yè)立刻加入優(yōu)先處理隊(duì)列，從而減少了無(wú)效的黑白名單匹配。利用位圖法改進(jìn)的hash表在URL的匹配過(guò)程中能夠做到一定程度的隨機(jī)訪問(wèn)，與鏈表從頭到尾的匹配方式相比，減少了在黑白名單中的比較次數(shù)。該方法相對(duì)于Bloom Filter，杜絕了誤判的可能。和傳統(tǒng)的hash表進(jìn)行URL過(guò)濾相比，減少了無(wú)效匹配的次數(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]李曉明.兩種對(duì)URL效果很好的散列函數(shù)[J].軟件學(xué)報(bào),2004（2）,179-185

[4]劉燕兵.一種面向大規(guī)模URL過(guò)濾的多模式串匹配算法[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

黃誠(chéng)（1987-），男，湖南常德人，碩士研究生，研究方向?yàn)樾畔踩?/p>

2015-12-21

2016-01-10

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

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