基于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