基于AC-BM算法的移動互聯(lián)網(wǎng)審計平臺性能提升方法

慕悅 王健

摘 要：近年移動互聯(lián)網(wǎng)絡以燎原之勢迅速發(fā)展，用戶群數(shù)量上漲和激增的網(wǎng)絡流量不僅僅成為舉世矚目的成就，也對現(xiàn)有的網(wǎng)絡環(huán)境提出了更高的要求?；诋斚碌囊苿泳W(wǎng)絡環(huán)境，文章以移動互聯(lián)網(wǎng)審計系統(tǒng)為實驗平臺，使用深度包檢測等數(shù)據(jù)包分析技術對網(wǎng)絡流通數(shù)據(jù)進行識別、審計、分析，并通過該技術對移動互聯(lián)網(wǎng)中的流量數(shù)據(jù)進行合理監(jiān)測、管控有害信息傳播。另外，文章使用AC-BM算法對審計平臺的識別算法進行優(yōu)化，快速有效地分析處理數(shù)據(jù)，以解決用戶使用高峰時段訪問量驟增，導致的系統(tǒng)性能驟降甚至丟包、分析不全面等問題。

關鍵詞：流量審計；應用識別；模式匹配；AC-BM算法

近年我國通信基礎設施建設不斷升級，移動網(wǎng)絡技術迅速普及，運營商推動下移動網(wǎng)民使用3G/4G等高速流量網(wǎng)絡比例大幅增長，應用使用需求多樣化。截至2015年6月，我國手機網(wǎng)民中通過3G/4G和Wi-Fi接入過互聯(lián)網(wǎng)的比例分別占85.7%和88.9%?！吨袊ヂ?lián)網(wǎng)20年發(fā)展報告》指出中國網(wǎng)民數(shù)量已成為世界第一，由此，對網(wǎng)絡的移動性、穩(wěn)定性、高速性和安全性提出更高要求，網(wǎng)絡安全已上升為國家安全的重要內容[ 1 ]。

移動互聯(lián)網(wǎng)安全進行有效管控，首先要對現(xiàn)有網(wǎng)絡進行篩查。合理應用通訊數(shù)據(jù)，監(jiān)測、管控有害信息傳播，分析用戶行為數(shù)據(jù)[ 2 ]，對于網(wǎng)絡管理員、服務商管理員、用戶都具有重要的意義，尤其是QoS、入侵檢測、流量監(jiān)控、計費管理和用戶行為分析的前提和基礎。

本文旨在快速、有效地分析、識別和管理移動互聯(lián)網(wǎng)數(shù)據(jù)。使用AC-BM算法對應用識別過程進行效率的提升，解決現(xiàn)有的應用審計系統(tǒng)在大數(shù)據(jù)流環(huán)境下的審計效率低下問題。

1 背景

1.1 移動互聯(lián)網(wǎng)應用市場

移動運營網(wǎng)絡技術的迅速發(fā)展，用戶要求逐漸嚴格，開發(fā)平臺的普及等等原因，都為移動產(chǎn)品市場提供了一片廣闊的市場。短短幾年時間移動市場迅速崛起，各大廠商都緊緊抓住這一次發(fā)展機會，推出了眾多功能不同、面向用戶不同、業(yè)務模式不同的移動端應用。

中國互聯(lián)網(wǎng)絡信息中心《中國互聯(lián)網(wǎng)絡發(fā)展狀況統(tǒng)計報告》指出，近幾年的個人互聯(lián)網(wǎng)應用發(fā)展呈上升趨勢。表1中的統(tǒng)計數(shù)據(jù)，我國在2014-2015年期間，電子商務成為了最重要增長板塊。同時也可以看到整體的移動互聯(lián)網(wǎng)應用均有穩(wěn)步增長的發(fā)展前景。

移動互聯(lián)網(wǎng)絡中產(chǎn)生大量的流記錄，通過審計將應用信息進行識別、采集、存儲、分析，但如果面臨用戶使用高峰時間段，HTTP，P2P等消耗帶寬的應用載荷將會占用大量的網(wǎng)絡處理能力[3]?；ヂ?lián)網(wǎng)上的網(wǎng)絡設備的數(shù)量以萬計，并持續(xù)增長。在目前的高速網(wǎng)絡中，實時流量統(tǒng)計必然會遇到一些問題：（1）網(wǎng)絡統(tǒng)計信息數(shù)據(jù)十分巨大。普通的運營商骨干路由器流量以Gbps為單位，存儲能力有了額外需求。（2）數(shù)據(jù)流后期數(shù)據(jù)分析耗費大量時間。高速CPU、大容量內存來解決海量數(shù)據(jù)分析，硬件成本提高。

1.2 移動互聯(lián)網(wǎng)應用市場

傳統(tǒng)互聯(lián)網(wǎng)流量審計、識別、監(jiān)測技術已比較成熟。但專門面向移動互聯(lián)網(wǎng)的數(shù)據(jù)流量審計還在起步過程中，目前主要是借鑒于傳統(tǒng)互聯(lián)網(wǎng)審計方法，采用智能化處理和網(wǎng)絡報文采集等相關技術實現(xiàn)分析處理、訪問限制、來源審計。目前比較常用的應用識別方法有：（1）應用層協(xié)議識別技術，根據(jù)應用層協(xié)議將TCP/UDP流分類。主要分為4類：基于端口映射；基于有效載荷特征，稱為DPI（深度包檢測）技術[4]；基于流動態(tài)行為特征，稱為DFI（深度/動態(tài)流檢測）識別技術[5]；基于主機行為的識別方法。（2）啟發(fā)式的方法[6]，端口號已知的應用協(xié)議識別。（3）基于協(xié)議簽名[7]，其特征字符串是針對P2P協(xié)議。（4）基于特征串的應用層協(xié)議，將高頻字段設置為特征值。

此外，模式匹配算法的優(yōu)良與否將直接決定移動互聯(lián)網(wǎng)審計的效率。經(jīng)典的單模式匹配算法有BF算法、KMP算法、BM算法等，但多模式匹配更加是大流量環(huán)境，如AC算法、WuManber算法等。本文中使用了效率較高的多模式匹配算法，從而達到解決用戶使用高峰時段移動網(wǎng)絡訪問量驟增造成的流量激增，可能導致的系統(tǒng)性能驟降甚至丟包、分析不全面等問題。

2 關鍵技術

2.1 數(shù)據(jù)獲取及特征提取

移動網(wǎng)絡審計系統(tǒng)利用tcpdump + Wireshark來進行抓包，將審計平臺服務器和實驗移動終端（如手機）連入相同的實驗Wi-Fi網(wǎng)絡。tcpdump將局域網(wǎng)中流通的Pcap包捕獲，由Wireshark軟件解析Pcap結構，分析內容并利用LCS算法在數(shù)據(jù)流中找到最長公共子串生成特征值組作為分辨應用種類的關鍵值。圖1中可以從Host字段中提取出與應用有關的字段“.fetion.com.cn”作為特征值。

2.2 應用業(yè)務識別

2.2.1 DPI技術

DPI技術是一種基于特征碼網(wǎng)絡數(shù)據(jù)流識別方法[ 8 ]。該技術高效地將數(shù)據(jù)包分層解析并深度分析有效載荷的內容，是一種基于應用層的流量檢測和控制的技術。本文采用特征值匹配方法來識別移動互聯(lián)網(wǎng)應用，將互聯(lián)網(wǎng)中的數(shù)據(jù)流進行截取、審計、分析。字符型特征指的是使用字符串組合對應用協(xié)議進行唯一標示。特征匹配是應用業(yè)務識別的基礎，因此特征庫的完整性非常重要。只有通過對大量應用協(xié)議的特征進行提取來實現(xiàn)完備特征庫的構建，基于DPI的應用業(yè)務識別才更加精確。

2.2.2 多模式匹配技術

現(xiàn)有一組模式的集合，每個模式都是字符集合中的字符串組成。同時有一個長度為的文本串，而且中的所有字符和來自于同一個字符集合。多模式匹配在文本串中找出模式集合中的所有模式。顯然在移動互聯(lián)網(wǎng)審計系統(tǒng)中，文本串為每一條等待被解析的業(yè)務數(shù)據(jù)流，而模式集合中的所有模式就可以被視作深度包檢測中的特征庫。

1975年A V.Aho和M J.Corasick發(fā)明了AC算法[9]，1979年Comments Walter對AC算法進行了改進，結合效率較高的單模式匹配BM算法提出了新的AC-BM算法[ 1 0 ]。模式匹配算法的效率和規(guī)則庫的完整性決定了特征識別的結果。使用特征值組匹配的方法，找到數(shù)據(jù)流中的特征值字段，最終從而達到審計的目的。數(shù)據(jù)包解析后的有效載荷的特征匹配多使用了多模式匹配算法。

3 優(yōu)化方案

3.1 AC-BM算法

AC算法是一種經(jīng)典的搜索多模式串算法，由文本串輸入和模式串集合構成的有限狀態(tài)模式匹配機2個部分組成。BM算法是效率較高的單模式匹配算法，在復雜的移動網(wǎng)絡環(huán)境中將2種模式匹配算法結合使用可以使得字符串樹多模式匹配和滑動跳躍移動2種機制的優(yōu)點共同發(fā)揮，在現(xiàn)有的入侵檢測系統(tǒng)等數(shù)據(jù)流檢測系統(tǒng)中已經(jīng)得到了良好的應用。

AC-BM算法可以主要分為2個部分：預處理部分和匹配部分。預處理部分將會生成AC算法的有限狀態(tài)自動機模式樹和BM算法的壞字符、好后綴表，匹配部分將會根據(jù)上面的模式樹和2張表進行匹配。

3.2 構造有限自動機

假設模式集合為，AC算法的自動機如圖3所示。模式樹上的每一個節(jié)點都作為一個狀態(tài)，顯然有狀態(tài)，且為根節(jié)點，為匹配成功后的終點狀態(tài)。轉移函數(shù)表示當前狀態(tài)如果匹配字符將會變?yōu)闋顟B(tài)；在匹配不成功時，表示由當前狀態(tài)變?yōu)闋顟B(tài)；保存的信息為匹配最后結構。

3.2.1 匹配過程

模式串在被匹配過程中大部分情況下是失配的，BM算法中的壞字符跳轉和好前綴跳轉將大大減少字符串匹配中的重復性工作。圖4中被匹配的文本串，在A中后綴匹配成功且狀態(tài)，但是顯然說明為壞字符，失配則向左移動兩個字符。以此類推不斷向前匹配最終找到模式串并輸出。

3.2.2 應用識別模塊優(yōu)化方案

網(wǎng)絡信息審計系統(tǒng)的功能關鍵在于在網(wǎng)絡關鍵節(jié)點上監(jiān)聽所有的數(shù)據(jù)包，解析重組之后對數(shù)據(jù)包中的內容進行審查，并根據(jù)結果做出相應的響應。其中對數(shù)據(jù)包內容的審計包括對文本的內容、性質的分類，對關鍵模式的相似性匹配，匹配發(fā)生后的響應程序等步驟。其中的關鍵就是對關鍵字符串的模式相似性匹配的效率問題，也將會成為整個網(wǎng)絡信息審計系統(tǒng)的瓶頸。

原有的系統(tǒng)將捕獲的特征值組作為單模式匹配，每次查找都要遍歷所有的特征值，造成嚴重的資源浪費。本文中采取的方式是將特征值按照移動互聯(lián)網(wǎng)應用業(yè)務進行分類，并建立一個特征模式串池，將大量的應用特征值分層放入特征模式串池，減少識別過程中的空間、時間消耗（見圖5）。

被捕獲的特征值組在審計之前將會被分類，首先分類為不同的應用類型，然后根據(jù)特征值本身來源的性質再次分類，每一個類型都使用AC-BM算法進行預處理獲得各自的、、和字符跳轉表。當每一個數(shù)據(jù)包到達時，DPI技術把移動互聯(lián)網(wǎng)中的應用協(xié)議進行解析并獲得最后應用層載荷，將這些載荷或者其中特定的某個部分將作為被匹配的文本串放入分類指針當前指向的應用類別。經(jīng)過圖4右圖所示的匹配過程得到結果，如果成功則可以識別當前的移動互聯(lián)網(wǎng)應用，不成功將進入下一個審計類型。分類指針將會停留在當前應用被識別的應用類型上，當連續(xù)的數(shù)據(jù)包到達很可能是相同的應用類型。

4 結論

對移動互聯(lián)網(wǎng)審計平臺系統(tǒng)應用 AC-BM多模式匹配算法進行性能提升的驗證工作主要是對系統(tǒng)改造前后的性能進行對比。移動互聯(lián)網(wǎng)審計平臺系統(tǒng)的實驗環(huán)境為硬盤為1T的服務器環(huán)境，操作系統(tǒng)為Ubuntu12.04，利用Libpcap技術進行抓包，在這樣的環(huán)境下使用AC-BM多模式匹配算法對原有的應用識別模塊進行改造，得到如下的數(shù)據(jù)（見圖6）。

從總體的系統(tǒng)吞吐量上來看，無論是上行和下行的移動互聯(lián)網(wǎng)流量都有了較大的提高，采用AC-BM算法對審計平臺的識別算法進行優(yōu)化，處理當下的移動網(wǎng)絡環(huán)境流量激增，導致的系統(tǒng)性能驟降甚至丟包、分析不全面等問題有比較良好的效果。但同時也應對平臺識別算法繼續(xù)研究，找到能保證平臺實時性和可靠性的算法和優(yōu)化方案。由于移動網(wǎng)絡環(huán)境發(fā)展迅速、監(jiān)管方式有限，為了對移動互聯(lián)網(wǎng)中的流量數(shù)據(jù)進行合理監(jiān)測、管控有害信息傳播，對網(wǎng)絡流通數(shù)據(jù)的識別、審計、分析，后續(xù)的工作要結合數(shù)據(jù)挖掘對網(wǎng)絡流量進行差異化管理和實時控制。

[參考文獻]

[1]陳曼青，武子榮.基于4G的移動網(wǎng)絡安全問題研究[J].信息通信，2014（10）：192-193.

[2]沈亮.數(shù)據(jù)挖掘在移動通信網(wǎng)絡優(yōu)化中的應用[D].上海：上海交通大學，2009.

[3]何山.網(wǎng)絡審計平臺面臨大流量、多業(yè)務挑戰(zhàn)運營商需個性化安全方案[J].通信世界，2012（34）：32-32.

[4]Graham-Cumming J.Automatic identification of application protocols through dynamic mapping of application-port associations： US， US 6182146 B1[P].2001.

[5]Liu A X，Meiners C R，Norige E，et al.High-Speed Application Protocol Parsing and Extraction for Deep Flow Inspection[J].IEEE Journal on Selected Areas in Communications，2014（10）：1864-1880.

[6]簡光垚.基于啟發(fā)式識別的深層數(shù)據(jù)包檢測P2P流的研究與實現(xiàn)[D].廣州：暨南大學，2008.

[7]路林，羅軍勇，劉琰，等.協(xié)議簽名特征自動發(fā)現(xiàn)方法[J].信息工程大學學報，2012（5）：610-614.

[8]呂錦揚.DPI技術在移動數(shù)據(jù)網(wǎng)絡分析的應用[J].電信技術，2013（6）：72-75.

[9]Aho A V，Corasick M J.Efficient string matching： an aid to bibliographic search[J].Communications of the Acm，1975（6）：333-340.

[10]Coit C J，Staniford S，Mcalerney J. Towards Faster String Matching for Intrusion Detection or Exceeding the Speed of Snort[C]//DARPA Information Survivability Conference and Exposition.IEEE Computer Society，2001.

Mobile Internet Audit Platform Based on AC-BM Algorithm Performance Improvement Method

Mu Yue， Wang Jian*

（School of Computer and Information Technology， Beijing Jiaotong University， Beijing 100044， China）

Abstract： In recent years， mobile Internet network run amok in the rapid development of network traffic is not only the surge of number of users increases and become a remarkable achievement， also put forward higher request to the existing network environment. Based on the current mobile network environment， this paper takes the mobile Internet auditing system for the experimental platform， the use of deep packet inspection packet analysis technology such as identification， audit， analysis of network flow data， and through the technology of the mobile Internet traffic data for reasonable monitoring， control the spread of harmful information. In addition， this article USES AC -BM algorithm optimize the audit platform recognition algorithm， fast and efficient data analysis and processing， in order to solve the user use increased rush-hour traffic， cause of system performance in even the problem such as packet loss， the analysis is not comprehensive.

Key words： traffic audit； application of identification； pattern matching； AC-BM algorithm