基于AC-BM算法的移動互聯網審計平臺性能提升方法

慕悅 王健

摘 要：近年移動互聯網絡以燎原之勢迅速發展，用戶群數量上漲和激增的網絡流量不僅僅成為舉世矚目的成就，也對現有的網絡環境提出了更高的要求。基于當下的移動網絡環境，文章以移動互聯網審計系統為實驗平臺，使用深度包檢測等數據包分析技術對網絡流通數據進行識別、審計、分析，并通過該技術對移動互聯網中的流量數據進行合理監測、管控有害信息傳播。另外，文章使用AC-BM算法對審計平臺的識別算法進行優化，快速有效地分析處理數據，以解決用戶使用高峰時段訪問量驟增，導致的系統性能驟降甚至丟包、分析不全面等問題。

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

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

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

本文旨在快速、有效地分析、識別和管理移動互聯網數據。使用AC-BM算法對應用識別過程進行效率的提升，解決現有的應用審計系統在大數據流環境下的審計效率低下問題。

1 背景

1.1 移動互聯網應用市場

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

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

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

1.2 移動互聯網應用市場

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

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

2 關鍵技術

2.1 數據獲取及特征提取

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

2.2 應用業務識別

2.2.1 DPI技術

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

2.2.2 多模式匹配技術

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

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

3 優化方案

3.1 AC-BM算法

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

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

3.2 構造有限自動機

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

3.2.1 匹配過程

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

3.2.2 應用識別模塊優化方案

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

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

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

4 結論

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

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

[參考文獻]

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

[2]沈亮.數據挖掘在移動通信網絡優化中的應用[D].上海：上海交通大學，2009.

[3]何山.網絡審計平臺面臨大流量、多業務挑戰運營商需個性化安全方案[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]簡光垚.基于啟發式識別的深層數據包檢測P2P流的研究與實現[D].廣州：暨南大學，2008.

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

[8]呂錦揚.DPI技術在移動數據網絡分析的應用[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