提出一种适用于大规模互联网流量的实时广告流量检测系统，系统以目前最为流行的Adblock规则列表作为基本规则库，将HashTable快速匹配算法和Aho-Corasick快速匹配算法相结合，对广告流量进行快速实时匹配.此外，为了适应大规模流式数据的需求，将匹配算法部署在并行流式工作框架Spark Streaming之上.模型系统分别在实验室和运营商真实网络环境下的超大规模数据集进行了测试，结果表明，检测系统具有较高的准确率和计算效率.
A real-time internet advertisement traffic recognition system applied to massive network dataset was proposed. The model adopts the currently most popular Adblock filter rules as the basic filter rules, and combines the HashTable fast matching algorithm as well as the Aho-Corasick fast matching algorithm to recognize the advertisement traffic in a fast and real-time way. To meet the need of the massive streaming data, the algorithms are deployed on Spark Streaming, a parallel streaming framework for solving streaming data. The model is respectively experimented with both factual data from our lab and the real massive datasets from the network operators. Experiments show that the system can achieve high precision and high calculation performance.
互联网广告流量在整个互联网流量中占据了十分重要的地位. 目前国内外的研究也十分重视互联网广告业务分析，Fan[1]等采用联合过滤的方法对社交网络的广告进行分析. 刘[2]使用多类别特征的方法对腾讯搜搜广告进行了分析. 但对于网络运营商而言，要想实现对互联网广告流量的分析需要面对以下两大技术挑战：
1) 互联网广告多种多样，包括文字广告、图形广告、视频广告等，增加了广告流量识别的难度；
2) 由于计算能力的限制，之前的广告流量分析大多基于广告服务器或者用户客户端的数据[1]. 面对运营商网络的大规模数据，急需可扩展的并行流式算法.
提出了一种快速规则匹配算法，并将该算法系统部署在真实的网络环境中，验证其性能. 近几年来快速匹配算法广泛应用到各个领域，包括互联网流量分析、异常检测、模式发现等. 例如Bremler-Barr等[3]提出一种ACCH(Aho-Corasick-based algorithm for compressed HTTP)框架，将Aho-Corasick算法应用HTTP流量分析. Becchi等[4]对ACCH框架进行了进步扩展，在参数选择上进行了改进. Garofalakis等[5]则是通过应用正则表达式来对序列模式进行模式挖掘. 但以上研究中的方法都没有实现并行化，不能很好地适应网络运营商的高速网络环境. 提出快速规则匹配算法并行化，并采用目前比较流量的并行流式框架Spark Streaming进行实现，实验结果表明，该系统可以从大规模互联网络流量中快速、实时地识别出广告流量.
1 Adblock Plus 介绍Adblock Plus(ABP)是目前最为流行的开源广告过滤浏览器附加组件. ABP可以支持大部分的主流浏览器，包括Firefox、Chrome、Explorer、Opera等. ABP的工作原理非常简单，它将网页内容的源地址和规则列表进行比较，如果某个内容的源地址中包含了规则表中的字符串，Adblock将阻止浏览器发送源地址的HTTP请求. 为了保证Adblock规则表的全面准确，Adblock规则表由数量庞大的社区用户共同维护，并由专门的作者定期进行矫正更新. Adblock规则表的规则数量已经超过的4万条，并且还在根据互联网的变化而不断的更新和增加.
Adblock规则表大体上可以分为两类，一类是规则中包含通配符. 另一类是规则中不包含任何通配符，只包含一个字符串，如表 1所示. 本研究的广告监测系统就是以Adblock的规则表为基础，将Adblock规则表作为基础规则库，应用于真实网络的大规模流量监控系统中，实现Adblock规则表的快速准确匹配，达到广告过滤的目的.
|
表 1 Adblock规则表实例 |
图 1展示了快速大规模广告流量检测系统的运行架构. 该系统主要包括3个功能模块：1)流量镜像系统(TMS，traffic monitor system)：TMS是作者实验室自主研发的高性能流量镜像监测系统[6]. 系统采用深度包监测(DPI，deep packet inspection)技术，可以实现10 GB带宽的实时网络流量镜像. TMS设备被部署到运营商GPRS服务支持节点(SGSN，serving GPRS support node)和网关GPRS支持节点(GGSN，gateway GPRS support node,)间的Gn接口上. GGSN作为运营商与互联网的网关，为运营商的用户提供互联网接入服务. 因此通过镜像SGSN和GGSN间的Gn接口流量可以捕获所有用户的上网数据. 2)Kafka：Kafka是一个开源的分布式消息系统. Kafka负责将TMS镜像的数据流式的输入到并行计算平台中. 3)并行计算平台：使用Apache Spark框架搭建的并行计算平台，主要负责对大规模流式数据的处理. 平台将输入的网络流量数据与规则表进行快速匹配，检测和过滤出广告流量. 同时平台中的Driver节点负责每天定时查询和更新Adblock规则表.
|
图 1 快速大规模广告流量检测系统架构 |
为了实现对运营商网络中的大规模流式数据的实时匹配，检测系统针对单机版的Adblock附加组件进行了2个方面的改进：1) 对于Adblock中的两种不同规则，采用不同的算法进行快速匹配；2) 将匹配算法应用于并行流式计算系统. 下面将在2.1和2.2节分别介绍采用的2个快速算法，2.3介绍算法的并行实现.
2.1 HashTable快速匹配算法假设Adblock规则表中有m个规则，需要检测的URL请求的字符串长度为n，最为简单的匹配算法就是遍历m个规则，将请求与m个规则分别作一对一的比较，算法的时间复杂度为O(mn). 这种算法实现虽然简单但效率低，运行时间长，显然不能满足运营商网络大规模数据的应用场景.
优化算法的基本思路是对于Adblock规则表中上万的规则，不去遍历整个规则表，而是首先缩小URL请求可能匹配规则的范围，形成一个缩小的规则集，然后将此URL请求匹配这个缩小了的规则集. 为此设计了一个基于HashTable的快速匹配算法来对Adblock规则表中含有通配符的规矩进行匹配. 算法实现方法如下.
1) 对于规则表中的每个包含通配符的规则，首先以通配符为分割符，将规则进行分割.
2) 从分割后的字符串中提取一个固定长度为k的字符串作为该规则的关键字keyword，keyword尽量保证在整个规则集中唯一. 将keyword和该keyword对应的规则存入HashTable中，keyword作为HashTable的键值key，规则作为HashTable的value值. 通过多次实验发现固定长度k取8时可以达到最优的匹配效果. 表 1中规则存入HashTable的keyword值如表 2 的keyword列所示.
|
|
表 2 对应keyword |
3) 对于URL请求，同样以k为固定长度，从中提取多个keyword. 如表 2第2行所示.
4) 将步骤3)中提取的多个keyword，作为哈希键值key，来匹配HashTable中的规则. 如果哈希键值在HashTable中存在，则将URL与该键值对应value值进行匹配.
从表 2中可以看出URL请求“jpseek.com/tuiguang”提取的多个keyword中，粗体字的/tuiguan关键字作为哈希键值，可以在HashTable中查找到，有一个对应的规则，因此只需要将URL请求与规则“/tuiguang/*_banner”进行匹配. 该算法的计算效率只与规则的数量m有关，算法的时间复杂度为O(m).
2.2 Aho-Corasick快速匹配算法Aho-Corasick算法是一个广泛使用的字符串匹配算法[7-8]. Aho-Corasick算法将字符匹配的判断过程转化为有限状态机的状态转移问题，其算法的复杂度只与URL请求的字符串长度n有关，时间复杂度为O(n). Aho-Corasick算法效率要高于HashTable匹配算法，但是Aho-Corasick算法的有限状态机不能很好地表示通配符，因此系统使用Aho-Corasick算法来快速匹配不包含通配符的规则，算法的实现方法如下.
1) 创建树形有限状态机：首先，建立一个确定性的树形有限状态机来描述规则表. 例如对于多个规则tag、stay、go、gov，建立的树形有限状态机如图 2所示. 图中的每1个节点表示了1次的状态转移，所有规则状态转移的创建均以根节点(状态节点0)开始. 深色节点表示一个完整的规则匹配. 如果规则中的字符状态转移在树中已存在，则沿树中已有边向下转移. 如果字符状态转移在已有树中不存在，则新建一个状态转移节点. 如在图 2中构建gov状态转移时，因为go已在树中存在，所以首先沿0、8、9节点构建，当发现v不在树中时，新增加了一个v的状态转移节点10.
2) 为节点添加失败指针：为避免匹配过程中的回溯，为每个节点添加可能的失败指针，如图 2中的虚线所示. 通过失败指针当一个模式匹配失败时，算法不会马上回溯到字符串的首字母重新匹配，而是根据失败节点的位置沿着失败指针重新选择一个开始节点继续匹配. 失败指针的添加遵循如下规则：如果图中存在相同的转移节点，并且如果其中一个节点向上遍历到根节点0节点得到的字符串为另一个点向上遍历到0点节点得到的字符串的子串. 那么这两个点就存在一个失败指针. 指针的方向指向包含子串的节点. 如图中的3和8节点间的虚线，虚线方向从3节点指向8节点.
|
图 2 树形有限状态机 |
3) 字符串匹配过程：树形有限状态机建立好以后，将要匹配的字符串作为输入，从状态0开始进行状态转移，首先沿着图中实线进行状态转移，当转移到某个节点发生匹配失败时，查看该节点是否有失败指针，如果存在失败指针则沿着失败指针继续匹配，直到没有任何状态可以转移，算法结束. 在整个状态转移过程中如果经过了深色节点说明发生了规则匹配. 例如需要对“stago”进行规则匹配时，整个状态转移过程经历了节点0，4，5，6，2，3，8，9. 其中节点3，9为深色节点，则可以得到规则“stago”与规则“tag”和“go”匹配. 而在实际应用中只要有一次规则匹配发生，就说明该URL请求为广告请求. 因此为了提高系统的性能，当算法转移到一个深色节点时，就使算法退出而不进行后续的状态转移.
2.3 并行流式算法实现为了实现大规模流式数据的实时处理，系统使用Spark Streaming框架来处理输入的流式网络流量数据. Spark Streaming是构建在Spark集群基础框架之上的实时计算应用框架. Spark Streaming在处理大规模流式数据上有如下优点：
1) Spark Streaming在任务执行上使用有向无环图(DAG，directed acyclic graph)，在DAG中后续任务会依赖前序任务的执行. 一旦后续任务失败，系统会回溯到前序任务来恢复任务. 这就保证了Spark Streaming具有很高的容错性.
2) Spark Streaming将流式计算分解成多个Spark作业，并且可以将计算放入内存中以提高计算效率，因此Spark Streaming可以实现近似实时计算.
3) Spark Streaming是基于Spark计算平台的应用框架，因此Spark Streaming可以使用Spark中丰富的操作函数来表达复杂的计算过程.
基于以上优点，系统在并行计算平台中使用Spark Streaming来接受Kafka发来的流式网络流量数据. Kafka将流数据以并行的方式分发到Spark Streaming的各个Worker节点. Spark Streaming在每一个Worker节点上启动一个Receiver对象，负责监听Kafka发来的数据. Worker节点利用2.1和2.2节所述的快速匹配算法，将收到的数据与本机的规则表进行匹配. 此外，在Driver节点上启动一个定时任务，负责定时查询Adblock网站最新的规则表. 如果规则表发生了变化，Driver节点更新规则表，并使用Spark的broadcast方法将更新后的规则表分发给各个Worker节点.
3 系统评估系统首先利用实验室的小规模数据，测试系统算法的准确性和可扩展性. 随后，利用运营商真实网络环境下的大规模流量数据进行测试，以验证系统在大规模流式数据环境下的可行性.
3.1 实验室环境实验首先邀请30位志愿者来生成标准测试集. 30位志愿者分别对各大主流网站进行随机访问，网站类型包括门户网站、社交网站、娱乐网站等. 30位志愿者在自己本机浏览器上安装Adblock Plus附件组件来对广告进行屏蔽，并将屏蔽请求的结果记录、导出. 导出的结果作为实验评判正确性的标准集合. 同时在实验室的网络出口路由器架设广告流量检测系统，对30位志愿者的互联网访问记录进行镜像、检测. 30位志愿者进行了3 d的测试，将检测的结果和标准集进行对比验证. 对比结果如表 3所示. 从表中可以看出提出的方法可以实现很高的广告识别准确率. 这里需要指出的是，Adblock中有一类特殊的过滤规则就是根据网页内容源码进行规则过滤，这类广告由于不需要发送单独的URL请求，因此不在统计的范围内.
|
|
表 3 检测正确率 |
实验还使用不同文件大小的数据进行实验，比较该算法与字符串硬匹配方法以及HashTable匹配方法的性能优劣. 比较结果如表 4所示.
|
|
表 4 方法性能对比 |
从表中可以看出提出的方法在拥有少量记录的小文件数据集下，性能表现不如HashTable匹配算法高效. 这是因为提出的方法在匹配之前需要首先
初始化一个有限状态机，有限状态机的创建过程需要一定的运算时间. 当处理大文件时，提出的方法则明显优于HashTable匹配方法. 处理2 908 MB文件时，相比于HashTable匹配方法，提出的算法性能提升了41.5%.
同时为了验证系统算法的可扩展性，实验分别使用1、2、3、4、5、6台计算节点，每台计算节点使用1个内核进行测试，来计算算法的加速比J. 加速比定义为J=T0/Ts，其中T0表示一个计算节点的运行时间，Ts表示s个节点的运行时间. 试验结果如图 3所示. 由图 3可以看出，随着节点数的增加，加速比也不断的增加，但加速比并不完全符合线性增加，这是由于随着节点数量的增加，节点的启动时间以及节点间通信开销也不断加大，对算法的加速比造成了一定的影响.
|
图 3 算法加速比 |
在运营商真实网络环境下，实验使用了一个持续时长为2 h的数据集，整个数据集的大小为34.5 GB. 实验中Kafka以5 min为时间间隔发送流式数据，并行计算平台由12台服务器组成，每台服务器有8个内核. 系统的执行效率如图 4所示. 从图 4中可以看出，算法具有稳定的计算效率，平均处理5 min流量数据仅仅需要12.5 s.
|
图 4 不同文件大小算法运行效率 |
同时实验还对不同时间、不同请求到达率的数据进行了测试. 实验从1 d中4个时间段(00:00:00、06:00:00、12:00:00、18:00:00)中各取了2个5 min请求数据进行实验. 系统的执行效率如图 5所示.
|
图 5 不同到达率文件算法运行效率 |
从图 5中可以看出，对于不同的请求到达率，算法同样具有稳定的计算效率.
4 结束语为了满足运营商网络环境下处理大规模流式数据的需求，提出了一种由HashTable快速匹配算法和Aho-Corasick快速匹配算法相结合的广告流量识别方法，并将算法部署在Spark Streaming上，以实现对大规模流式数据的处理. 通过在实验室环境和真实运营商网络环境的测试，验证了该系统的准确性和执行效率. 下一步研究的工作有：1)根据已有的广告流量寻找用户的广告点击流量，从而计算各个广告的转化率. 2)扩展运营商业务，增加网络版广告屏蔽服务.
| [1] | Fan T K, Chang C H. Learning to predict Ad clicks based on boosted collaborative filtering[C]//Social Computing (SocialCom), 2010 IEEE Second International Conference on Minneapolis.[S.l.]: IEEE, 2010: 209-216. |
| [2] | 刘唐. 基于多类别特征的在线广告点击率预测研究[D]. 北京: 北京邮电大学, 2013. |
| [3] | Bremler-Barr A, Koral Y. Accelerating multi-pattern matching on compressed HTTP traffic[J]. IEEE/ACM Transactions on Networking (TON) , 2012, 20 (3) :970–983. doi:10.1109/TNET.2011.2172456 |
| [4] | Becchi M, Bremler-Barr A, Hay D, et al. Accelerating regular expression matching over compressed HTTP[C]//Computer Communications (INFOCOM), 2015 IEEE Conference on Hong Kong.[S.l.]: IEEE, 2015: 540-548. |
| [5] | Garofalakis M N, Rastogi R, Shim K. SPIRIT: sequential pattern mining with regular expression constraints[C]//VLDB. 1999: 7-10. |
| [6] | Liu Jun, Liu Feng, Ansari N. Monitoring and analyzing big traffic data of a large-scale cellular network with Hadoop[J]. IEEE Network , 2014, 28 (4) :32–39. doi:10.1109/MNET.2014.6863129 |
| [7] | Dori S, Landau G M. Construction of Aho Corasick automaton in linear time for integer alphabets[J]. Information Processing Letters , 2006, 98 (2) :66–72. doi:10.1016/j.ipl.2005.11.019 |
| [8] | Pao D, Lin Wei, Liu Bin. A memory-efficient pipelined implementation of the aho-corasick string-matching algorithm[J]. ACM Transactions on Architecture and Code Optimization (TACO) , 2010, 7 (2) :10. |