基于KMP算法的網頁敏感信息審查系統

米 淳 李 翔 付為民 梅 彬

（中國人民公安大學 網絡安全保衛學院，北京 102623）

1 研究背景

1.1 選題目的及意義

隨著網絡突飛猛進的發展，網絡媒體已發展為繼報紙、廣播、電視之后的“第四媒體”，08年初中國網民數量更是超過了美國成為世界第一。如此驚人的發展速度使得網絡已經成為信息的主要載體，每天都會有大量良莠不齊的信息產生于網絡并廣泛傳播，網絡也成為一些不法分子用來實施犯罪行為或者傳播違法信息的重要工具。在此背景下，公安部門對于網絡信息的掌握顯得尤為重要。隨著公安部門“實施科技強警戰略、建立公安情報信息系統”的目標提出，公安網絡信息分析系統的建設需求空前迫切。本文在分析公安部門對網絡信息分析系統需求和相關技術的基礎上，結合公安部門已有的“公安情報信息綜合平臺”探討研究了網頁信息分析系統的設計與實現。

1.2 本課題的研究方向及創新點

1.2.1 本文的研究方向：本文以互聯網信息過濾與定位系統的設計和實現為目標，深入分析了一個高效的互聯網敏感信息審查系統的系統架構和基本工作流程等方面的問題。本文的主要工作如下：（1）結合國內外有關搜索與模式匹配的技術，設計了互聯網信息審查系統的整體架構；（2）介紹并分析了系統中三個重要的系統子模塊：信息收集模塊，信息預處理模塊和關鍵詞發現模塊的設計實現；（3）通過實驗證明了該設計中系統架構的可行性及高效性。

1.2.2 本論文的創新點：（1）采用KMP快速匹配算法對網頁內容進行定位，效率相對于其他一般模式匹配算法大幅提高；（2）運用爬蟲思想及算法從網絡獲取信息源，較人工查找方式實現了工作自動化及高效化。

2 系統的設計與實現

2.1 設計目標與思路

根據《計算機信息網絡國際聯網安全保護管理辦法》中的第五條規定：任何單位和個人不得利用國際聯網制作、復制、查閱和傳播下列信息：煽動抗拒、破壞憲法和法律、行政法規實施的；煽動顛覆國家政權，推翻社會主義制度的；煽動分裂國家、破壞國家統一的；煽動民族仇恨、民族歧視，破壞民族團結的；捏造或者歪曲事實，散布謠言，擾亂社會秩序的；宣揚封建迷信、淫穢、色情、賭博、暴力、兇殺、恐怖，教唆犯罪的；公然侮辱他人或者捏造事實誹謗他人的；損害國家機關信譽的；其他違反憲法和法律、行政法規的。

因此，開發敏感信息過濾系統旨在實現網絡安全監察人員在虛擬復雜的網絡世界中及時有效地發現有關情報信息與違法犯罪信息，為打擊網絡違法犯罪及時提供有力的依據和線索，推動監控網絡違法犯罪的信息化與自動化。

該敏感信息過濾系統主要實現以下功能。

（1）多級網頁鏈接獲取

一個網站一般包含了多級目錄，即擁有多個超鏈接，呈樹形結構。而本系統中網頁鏈接獲取子系統針對該結構，采用“網絡爬蟲”。“網絡爬蟲”是一個自動提取網頁的程序，是搜索引擎的重要組成。本系統中，網頁鏈接獲取子系統，根據一定的網頁分析算法過濾并保留指定類型的鏈接，并將其放入等待抓取的URL隊列。然后，它將根據廣度優先的搜索策略，從隊列中的上級站點頁面逐級往該站點的下級頁面抓取網頁URL，并可根據用戶的需求重復上述過程，直到達到系統中設定的某一條件時停止。

（2）網頁內容分析

1）網頁編碼格式分析

在當今網頁設計中，包含中文的編碼格式主要有四種，其分別是：GB2312、BIG5、GBK以及UTF-8格式。其中GB2312是簡體中文編碼，其一個漢字占用2字節，是大陸的主要編碼方式。但當網頁中包含繁體中文、日文、韓文等等時，這些內容可能無法被正確編碼；

很多國內網頁指定的編碼都是GB2312的，它是對ASCII的一種擴展，而ASCII—GB2312—GBK之間是向下兼容的，但Unicode中的 UTF-8與 ASCII、GB2312、GBK之間并不兼容，如果用UTF-8處理其他格式或者其他格式處理UTF-8的中文字符均會出現亂碼。因此，對頁面關鍵字分析之前需要對網頁編碼格式進行檢測與轉換。

在UTF-8格式的頁面中，一般包含如下標記：

其中HTTP-EQUIV類似于HTTP的頭部協議,它回應給瀏覽器一些有用的信息,以幫助正確和精確地顯示網頁內容。該標記即在發送文檔前通知瀏覽器該網頁采用UTF-8格式的編碼，提前進行編碼以實現正常的瀏覽。該網頁內容分析子系統通過分析如上標記中的編碼格式，并提前通過WideCharToMultiByt（）函數進行轉換，以達到關鍵詞準確搜索的目的。

2）基于KMP算法的敏感信息關鍵詞分析

關鍵詞的搜索操作，即字符串的模式匹配，是各種串處理系統中最重要的操作之一。其定位函數為Index（S,T,pos），其中S為目標串，T為模式串，pos表示第N個字符開始匹配。KMP算法是一種改進的字符串匹配算法，其關鍵是根據給定的模式串定義一個next函數，next函數包含了模式串局部匹配的信息。此算法可以在O（m+n）的時間數量級上完成串的模式匹配操作，其改進在于：每當一趟匹配過程中出現的字符比較不相等時，不需要回溯i指針，而是利用已經得到的“部分匹配”的結果將模式串向右“滑動”盡可能遠的一段距離后，繼續進行比較，極大的縮短的對復雜網頁的搜索時間。KMP算法的匹配過程如下：

2.2 基于KMP算法的敏感信息過濾系統軟件的實現

軟件在VC++6.0集成開發環境中編寫實現。其主要由用戶界面進程以及負責下載與分析的工作者線程組成。其包含了以下子系統：

（1）網頁獲取子系統：其對指定URL的緩存文件進行讀取分析，由于一般的HTML網頁中，標簽的href屬性用于指定超鏈接目標的 URL，因此，獲取中的引號中內容即可獲得URL地址。

（2）網頁格式轉換子系統：其首先判斷網頁編碼格式，即讀入網頁源代碼的1個字節，檢測如下內容：“”如果存在，則進行編碼格式轉換，即將UTF-8轉換至Unicode，再由Unicode轉換至ANSI。其實現關鍵代碼如下：

（3）基于KMP算法的網頁內容搜索子系統：該系統首先對用戶輸入的關鍵詞進行分析或拆分操作，獲取NEXT[J]列表。隨后根據NEXT[J]列表對網頁內容進行關鍵詞的模式匹配操作。其實現的關鍵代碼如下：

3 總結

本文在充分考慮基層網監民警業務需求的基礎上，針對網頁敏感信息隱藏難以發現的問題，開發了一種基于KMP模式匹配算法的網頁敏感信息檢索及URL提取應用軟件。使用本軟件能夠高速地對網頁敏感信息進行精確或者模糊檢索，使民警在進行網絡監察時，面對海量網頁信息是不再 “束手無策”，對敏感信息“一覽無余”。

[1]孫鑫.VC++深入詳解[M].北京：電子工業出版社，2012

[2]吳偉民，嚴蔚敏[M].北京：清華大學出版社，2009

[3]《計算機信息網絡國際聯網安全保護管理辦法》，1997年12月