中国公安部第一研究所，北京

收稿日期：2020年9月1日；录用日期：2020年9月11日；发布日期：2020年9月18日

摘要

多模式匹配算法是许多网络安全应用中的一种关键核心技术，被应用于检测网络内容中的有害信息。在当前网络中，HTTP压缩技术被广泛应用于网页内容压缩，以提升网络的传输速度。对于压缩HTTP流量的检测，传统方法一般是先对其进行解压，然后利用多模式匹配算法对解压后的内容进行检测过滤。这种传统的方法效率不高，且未能充分利用压缩数据的特性。本文提出了一种针对压缩的HTTP流量的基于跳跃的多模式匹配算法SMCH，SMCH可直接在压缩的HTTP流量上执行多模式匹配操作，而无需额外的解压操作。SMCH可以显著提高针对压缩HTTP流量的匹配速度。实验结果显示，SMCH可直接跳过91.9%的字符，而无需进行字符串匹配操作，其匹配性能比原始的匹配算法相比，提高了将近441%。此外，SMCH算法也更简单，比其它压缩HTTP流量匹配算法具有更高的跳变率和加速比。同时，SMCH具有良好的可扩展性，可以简便地与不同的字符串匹配算法结合使用。在本文中，我们在SMCH上实现了Wu-Manber算法。

关键词

多模式匹配，压缩的HTTP，GZIP，压缩匹配，网络安全

Skipping-Based Multi-Patterns Matching Algorithm for Compressed HTTP Traffic

Yuan Tian, Zhiqi Jiang

First Research Institute of the Ministry of Public Security of PRC, Beijing

Received: Sep. 1^st, 2020; accepted: Sep. 11^th, 2020; published: Sep. 18^th, 2020

ABSTRACT

Multi-patterns matching algorithm is a core technique of many network security applications, which is used to detect malicious information of HTTP contents. In the current Internet, HTTP compression technology has been widely used in web content compression to increase transmission speed. For the compressed HTTP traffic, the traditional approach needs to decompress it firstly, and then applies multi-patterns matching algorithm in the decompressed HTTP traffic. This traditional approach is not efficient enough and does not take full advantage of the characteristics of compressed data. In this paper, we propose a novel Skipping-based Multi-patterns Matching Algorithm for Compressed HTTP traffic (SMCH), which can directly perform the multi-patterns matching task on the compressed HTTP traffic without additional decompression. SMCH can significantly accelerate the matching speed of compressed HTTP traffic. Experimental results show that SMCH can skip at most 91.6% of the characters without executing matching, and gain performance boosts most 441% as compared to the original multi-patterns matching algorithm. Besides, SMCH is simpler and has higher skip ratio and accelerate ratio than the other compressed matching algorithms for compressed HTTP traffic. Meanwhile, SMCH has good scalability. Different multi-patterns algorithms can be simply implemented for SMCH. In this paper, we implement Wu-Manber algorithm based on SMCH.

Keywords:Multi-Patterns Matching, Compressed HTTP, GZIP, Compressed Matching, Network Security

Copyright © 2020 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

模式串匹配技术是入侵检测系统与网络应用防火墙等网络安全应用的关键技术之一，但是随着信息时代的发展，模式匹配技术面临新的问题：数据量急剧增加，网络流复杂多变，匹配的实时性不能满足等。如图1所示，展示了自2010年以来中国国际出口带宽。所以面对复杂多变的网络数据，模式匹配技术的性能需要进一步提升。

为了不断提升网络带宽，除了提高硬件传输能力以外，压缩数据传输逐渐被重视起来。HTTP压缩是指将Web文本数据在服务器压缩后发送给浏览器的传输方式。目前，Yahoo!、Google、YouTube、Baidu、腾讯等知名网站都使用HTTP压缩传输的传输方式。在2017年，根据Alexa网站 [1] 的前1000万网址的流量统计，有71.4%的网站使用了HTTP压缩传输，目前仍然呈现上升趋势 [2]。

在网页内容中存在着大量相同的标签信息以及声明信息等(如HTML、CSS、JavaScript等)，所以HTTP网页能被有效压缩。根据统计测试，压缩之后的HTTP页面可节省将近70%的存储空间。在HTTP 1.1协议中选用的压缩算法包括GZIP、DEFLATE等，其中根据‎ [2] 可以看出，GZIP压缩算法是HTTP压缩的常用算法，占到了98.9%左右。

现有的多模式匹配算法过滤压缩数据是比较困难的。针对HTTP压缩数据，不做处理和拒绝接受都会带来安全隐患或者性能损耗。目前网络安全应用基本采用“解压 + 扫描”的方式对压缩数据进行扫描过滤，当收到一个HTTP数据包之后，首先将其解压得到明文内容，然后利用模式串匹配算法对解压后的明文进行扫描过滤。这种方式的处理性能不够高效，且存在着一定的安全风险：

1) 处理性能不够高效：这种方式将扫描过滤的过程分解成了数据解压和数据扫描两个彼此独立的阶段，而忽视了压缩数据本身的特性，从而降低了扫描过滤的实时性；

2) 存在着“解压炸弹”的风险：攻击者可故意构造恶意数据来攻击网络安全应用，比如构造10 GB内容全为数字1的明文数据，但是压缩之后大小仅为1 MB，甚至更小。当处理这种类型的HTTP压缩数据时，解压过程中将会占用大量的内存空间和CPU运算，出现“解压炸弹”的风险。

图1. 自2010年以来中国国际出口带宽

压缩匹配是解决这一问题的有效途径，压缩匹配是指针对压缩数据进行模式匹配时，通过不解压或者局部解压的方式，对压缩数据进行模式串匹配。压缩匹配算法通过利用压缩匹配的特点提高对压缩数据的匹配效率。如图2是针对HTTP压缩流量整体过滤流程，首先获取HTTP报文，根据HTTP头部的Content-Encoding字段判断是否使用GZIP或者Deflate编码；如果否，使用正常系统过滤，否则将数据进行哈夫曼解码，获取LZ77数据，最后对LZ77数据进行过滤，产生过滤结果。

图2. HTTP压缩流量过滤流程

通过对压缩HTTP数据的特点进行分析，本文提出了一种针对压缩HTTP数据的基于跳跃的多模式串匹配算法SMCH。SMCH算法不依赖于任何具体的多模式匹配算法，而可以基于SMCH实现不同的支持压缩匹配的多模式匹配算法。在本文中，我们在SMCH上实现的是Wu-Manber算法。实验结果显示，SMCH可直接跳过91.9%的字符而无需进行字符串匹配操作，其匹配性能比原始的匹配算法相比提高了将近441%。

2. 背景和相关工作

2.1. GZIP压缩

GZIP，全称是GNU zip，是一种文件压缩程序，作者是Jean-loup Gailly和Mark Adler，于1992年公开发表‎ [3]。GZIP是对DELATE的封装，包括两个部分：LZ77压缩 [4] 和哈夫曼编码压缩 [5]。由于其中LZ77是其主要部分，而且LZ77部分是对原始数据进行编码，而哈夫曼编码部分是二次编码，所以本文主要根据LZ77的特性对多模式匹配算法进行改进，从而提高匹配速度。

LZ77算法是一种无损压缩算法，该算法需要维持一个固定大小的窗口(大小一般为32 KB)。如果字符串在其前面的窗口内重复出现，则使用指针(length, distance)来记录此重复数据，其中length表示重复数据的长度，distance表示重复数据的位置，从而达到压缩数据的目的。例如，字符串“abcdabc”，使用LZ77压缩后为“abcd(3,4)”，其中(3,4)表示在此位置有一个长度为3的字符串，该字符串的初始位置为向前4个单位。

表1. LZ77数据详细信息

如上所示，LZ77压缩数据格式中包含两种类型的数据：一种是普通的ASCII字符，另一种则是指针(length, distance)，后者表示在当前位置存在重复子串。我们抓取了采用LZ77压缩的Yahoo网页数据，并对压缩的网页数据进行了统计分析，结果如表1所示。压缩的Yahoo网页数据中93.75%的内容是指针，且指针的平均长度为19.4，这也表明指针部分的数据中有很大部分可以前面重复数据的匹配信息而直接跳过这部分数据而无需执行串匹配操作，从而改善匹配的效率。

图3. LZ77数据中重复子串的长度分布

如图3所示，LZ77压缩数据中存在着大量的重复子串，如果预先记录下重复子串的匹配信息，就可以利用前面获得的重复子串的匹配信息来确定当前子串的匹配动作，用重复子串的匹配结果作为当前字符的匹配结果，从而跳过部分字符而无需逐字符的执行串匹配操作。HTTP数据中存在大量的重复的标签数据使得其有很高的压缩率，这也说明针对压缩的HTTP数量，传统的“解压 + 匹配”不是一种高效的处理方式，而是压缩匹配算法是一种更加高效的方法。

2.2. 多模式匹配算法

本模板可直接用于论文及其文字的编排，有的页边距、行距、字体都严格符合规定，请勿修改！尤其是页边距，由于期刊在后期制作过程中需要在页眉、页脚添加各种信息，所以所有论文务必确保现有的页边距不被修改，页面空白不被占用。

目前有许多经典的多模式串匹配算法，如KMP算法 [6]、AC算法 [7]、Karp Rabin (KR)算法 [8] [9] 以及Wu-Manber (WM)算法‎ [10]。但是本文所提的SMCH算法不依赖于具体的匹配算法，且无需原始匹配算法的基础匹配结构。本文选择了将WM算法和SMCH结合使用，并以此为例对SMCH进行介绍，因此首先我们先对WM算法进行简要的介绍。

WM可以看作是单模式串匹配算法BM [11] 在多模式串上的扩展。WM采用了字符块技术，增大了主串和模式串不匹配的可能性，从而增加了直接跳跃的机会。同时使用散列表选择模式串集合中的一个子集与当前文本进行完全匹配，其主要包括三个表，分别是SHIFT表、HSAH表以及PREFIX表。SHIFT表是所有模式串的字符块以及字符块可转移长度的表格，用于在扫描文本串的时候，根据读入的目标文本决定可以转移的字符数，如果相应的转移值为0，则说明可能匹配成功。PREFIX表用于存储尾块字符散列值相同的模式串的首块字符散列值，如果转移值为0，那么就需要详细地将匹配文本和模式串比较。PREFIX表是为了通过字符块精准的定位模式串的位置，提高比较的效率。HASH表用来存储尾块字符散列值相同的模式串，待便于精准匹配。

2.3. 压缩匹配算法

压缩匹配算法指的是可以直接在压缩数据上执行字符串匹配的一类匹配算法，可大致分为哈夫曼压缩匹配算法、SDCH压缩匹配算法、LZW压缩匹配算法以及LZ77压缩匹配算法等。

哈夫曼编码被广泛使用，但是针对哈夫曼编码的压缩匹配算法主要是针对单模式串的。文献 [12] 总结了哈夫曼编码压缩算法并提出了一种直接在哈夫曼编码上执行匹配的压缩匹配算法。谷歌公司于2008年提出了一种新的针对HTTP网页的字典类压缩技术SDCH，文献 [13] 提出了一种针对SDCH压缩技术的压缩匹配算法，该算法主要是基于AC算法，假设模式串为{E, BE, BD, BCD, BCAA, CDBCAB}，搜索文本为“ABDDBEAAAACDBCABABCAACBCDBADBC”经过SDCH压缩后的文本。算法主要思想为通过不同的压缩数据完成自动机状态的转化，实现跳跃，进而加速，实验结果显示该算法能够跳跃99%的字符，获得56%的性能提升。LZW压缩算法主要用于GIF、TIFF以及PDF等文件的压缩，目前针对LZW压缩数据的压缩匹配算法主要集中在单模式串匹配，相关工作见文献 [14] [15]，由于和本文工作关系不大，本文不作详细介绍。

文献 [16] 首次提出了一种针对压缩HTTP流量的压缩匹配算法ACCH，该算法结合LZ77压缩数据的特点，对AC算法进行改进，从而实现了直接在压缩的LZ77数据上的匹配。ACCH主要基于匹配状态Status和自动机深度Depth来实现字符跳跃，文中实验结果显示ACCH能够跳跃75%的字符，且性能较原始的AC算法提高了70%左右。文献‎ [17] 以Wu-Manber算法为基础，提出了一个针对LZ77压缩数据的模式串匹配算法SPC。SPC算法能够跳跃最多87.5%的字符，相较于原始Wu-Manber算法，匹配性能提升了113%，并且相较于ACCH算法，也能够达到52%的性能提升。同时，在额外的空间消耗方面，SPC算法也同样优于ACCH算法。随后文献 [18] [19] 分别提出了各自的改进策略，主要针对AC算法和WM算法进行改进，在一定程度上提升模式串匹配算法在LZ77压缩数据上的匹配速度。

LZ77压缩匹配算法是用于匹配过滤GZIP压缩格式的HTTP数据的一种有效的方法。但是目前已有的研究工作都是针对某个特定匹配算法进行专门的设计优化，通用性不够。一方面，这些针对性的优化改进算法一般都可以跳跃较多的字符，也能较好的提升算法的匹配性能；但是另一方面，在实际应用中，网络安全应用中一般都集成了多种不同的匹配算法以应对日益复杂的网络内容，不同的匹配算法适用于不同的业务和场景，对多种不同的匹配算法进行优化改进以支持压缩匹配会有较大的难度。针对该问题，本文提出了一种灵活的压缩匹配结构SMCH，其可以灵活的和不同的具体的匹配算法结合使用。

3. 针对HTTP压缩流量的基于跳跃的多模式匹配算法

SMCH的核心是本文中定义的匹配状态mState，匹配状态被设计成压缩匹配算法和原始匹配算法之间的桥梁。匹配状态的值由原始匹配算法在匹配阶段计算得到，然后压缩匹配算法根据匹配状态以确定当前字符是否可以被跳过而无需进行字符串匹配操作。

3.1. 匹配状态的定义

除了一些众所周知的英文缩写，如IP、CPU、FDA，所有的英文缩写在文中第一次出现时都应该给出其全称。文章标题中尽量避免使用生僻的英文缩写。

压缩匹配算法的主要思想是利用压缩数据的性质，记录匹配状态，并利用重复的状态跳跃一定的字符，从而加速过滤。我们可以注意到，压缩匹配算法的重点在于匹配状态。在ACCH算法中，CDepth作为匹配状态，从而根据CDepth和AC自动机中的状态作为一个比较，判断是否可以跳跃。在SPC算法中，Partial Match作为匹配状态，从而判断是否可以跳跃。匹配状态是压缩匹配算法的重点，压缩匹配算法需要根据匹配状态和搜索的状态进行跳跃。

图4. 压缩匹配原理示意

如图4所示是压缩匹配算法的原理示意图，状态窗口负责记录匹配状态，字符窗口负责缓存字符，以便指针(length, distance)能够索引的正确的子串位置。在遇到指针类型的数据时，我们不仅能够获取原来的子串，同时根据状态窗口可以获取子串对应的匹配状态。通过记录匹配状态和搜索算法的状态判断是否可以重复利用记录的匹配状态完成跳跃。跳跃可能是一段，也可能是一个字符。

在本算法中，将匹配状态表示为mState，其主要包含两方面的信息：符号和数值。符号表示匹配结果，如果符号为正，那么表示该位置有一个模式串匹配成功；如果符号为负，那么表示该位置在一定长度内不可能匹配成功。数值表示安全距离，即只有大于mState的数值时，才是安全的。同时数值在符号为正时，表示匹配成功的模式串长度。当符号为负时，表示在该数值长度内不可能有一个模式串匹配成功。如果数值为0，则表示该位置没有任何匹配状态。

图5. 匹配状态mState举例

mState代表匹配结果，也代表匹配过程。符号表示匹配结果，而数值表示匹配过程。mState应该在字符串的匹配过程中产生，并不会影响匹配过程。如图5所示，图中模式串是“avb”。左侧文本是“avbnmgdad”，右侧文本为“avcnmgdad”。当使用模式串“avb”搜索目标文本“avbnmgdad”时，可以在文本的位置1处匹配成功，那么根据mState的定义，在第一个位置的字符“a”处的mState为“+3”。因为此时匹配成功，所以符号为正。为数值为匹成功的模式串长度，为3。所以mState为“+3”。当目标文本改为“avcnmgdad”时，模式串在第一个位置开始匹配时，在位置3的字符‘c’处匹配不成功，而前两个字符“ad”匹配成功。根据mState的定义，如果匹配不成功，那么符号应该为负，所以mState的符号为负。数值表示安全长度，即大于长度后不可能匹配成功，那么根据图中所示，当大于3个字符时，匹配就不可能成功，所以数值为3。因此，右侧的搜索产生的mState为“−3”。

从上面例子可以看出，搜索过程一定有两种可能，一个是匹配成功，一个匹配不成功。当匹配成功时，那么mState为正，且数值为匹配成功的模式串长度。当匹配不成功时，mState可能为负，且数值为最大匹配长度加一，即最小的安全长度。值得注意的是，匹配成功一定可以返回mState，而匹配不成功时，并不一定返回mState，主要原因是安全长度的定义。不同的多模式匹配算法有不同的搜索过程，最重要的是保持mState的数值必须是安全的，而匹配不成功导致的最大匹配长度加一并不一定是安全的。

在SMCH中，跳跃和搜索是分离的。搜索过程是执行字符串匹配并返回当前位置的匹配状态信息，跳跃过程则是根据对数据进行逐个扫描并根据匹配状态进行跳跃。

3.2. 匹配状态的计算

前文已介绍过当前的压缩匹配算法都是对原始匹配算法进行特定的改进优化，但是本文所提的SMCH不依赖于原始的匹配算法，具有良好的可扩展性，使用是只需原始匹配算法返回匹配状态即可。此外，SMCH在获得匹配状态的时候并不需要改变原始匹配算法的基础数据结构，这也使得SMCH具备良好的灵活性。

我们在算法1中定义Search()接口作为为模式的搜索过程，它需满足两个条件：搜索字符串的能力和返回正确的mState的能力。不同模式匹配算法之间的搜索过程不同，因此重要的是找到搜索与mState之间的联系，并将匹配状态转换为mState。

在本节中，我们仅以WM算法的一种实现为例。根据WM算法和mState的定义，有两个主要计算mState的地方：在shift表中的转移和在hash表中的查询。在shift表中，设max_pat_len是模式的最大长度，min_pat_len是模式的最小长度。算法的输入是字符串，其长度是max_pat_len，从该字符串的某个位置i开始，输出mState或mState数组。在第4行，如果shift_value = 0，则第5~14行处理hash表中的查询，该查询定位hash表并将模式与目标字符串一一比较。在第8行，如果文本与模式匹配，则返回模式的长度。否则，最大匹配长度记录在第10~11行。max_tmp是字符串和当前模式之间的最大匹配长度，max记录的是最大的max_tmp。在第14行，如果max+1大于或等于min_pat_len，则返回−max−1，否则返回−min_pat_len。第16行是转移过程，将mState设置为[−min_pat_len,−(min_pat_len-shift_value+1)]。这意味着如果一个shift_value值不为0，则有shift_value个mStates是有效的。

shift和hash之间有一些区别。在hash中成功匹配时，匹配的模式长度与mState有关。若有许多可匹配的模式，则返回可匹配模式的最小长度，因为它足够作为安全长度。当哈希失败时，存在一个与某模式可匹配的最大长度(如max)，这意味着从最大长度开始的下一个字符没有成功匹配。所以max + 1是安全长度。另外，max + 1应该大于或等于min_pat_len，因为需要将min_pat_len长的字符串作为哈希表的索引。但是在shift中，min_pat_len与mState显然无关。从当前位置i到i+shift_value-1的位置是有效的mState，其值是从−min_pat_len到−(min_pat_len-shift_value+1)。例如，如果shift_value为3，min_pat_len为4，则从当前位置i到i+2的mStates为[−4, −3, −2]。因为所有的转移字符都是安全的，不可能有匹配。

从hash表中获得的mState仅在此位置有效，而从shift表中获得的mState表可能会影响之后shift_value的位置。主要原因是哈希值的位置不能影响下一个位置，所以不能确定下一个位置的mState。shift表是转移表，因此它会对移位的字符产生影响。

SMCH算法需要一个模式算法来提供mState，它并不会改变原有模式匹配算法的数据结构，因此模式匹配算法的空间复杂度没有改变。SMCH算法主要基于两个固定长度的窗口(GZIP中为32 KB)，一个是字符的缓存，另一个是mState的缓存。不需要额外的空间。

Search()的实现多种多样，但原理相同。在实践中我们还根据KR算法和AC算法实现了接口，同样可达到良好的应用效果。本文不多叙述其他模式算法的实现。

3.3. 匹配状态在压缩匹配算法中的应用

根据mState的定义，跳转的条件是剩余重复子串的长度大于或等于mState的绝对值。在本节中，我们将详细介绍如何使用mState进行跳转。

图6. SMCH算法中的跳转过程

首先我们举例说明如何使用mState，如图6所示。指针(4, 521)指向重复子串sbca，在重复子串中与s对应位置的mState为3。可以看出，从s开始的重复子串的剩余长度为4，大于安全长度3，说明sbc段是安全的。换句话说，在sbc中有一个匹配项，之前由mState记录过。因此，我们不需要搜索字符串sbc，可以跳过它。可以看到b字符的mState为−2，根据mState的定义，表示第二个字符不能匹配成功，只有1个部分匹配成功。但是b之后的重复子串的剩余长度是3 (bca的长度是3)，因此我们可以安全地得出结论：bca字符串不会成功匹配，那么同样可以不搜索而直接跳转。但是，c不能跳过，因为0表示这里没有状态，a也不能跳过，因为a的剩余长度(为1)小于mState的绝对值(为4)。

算法3显示了SMCH中的扫描和跳转的过程。window是字符的缓冲窗口，w是字符索引，sw是搜索索引，w和sw同步但不在同一位置，sw在w之后，mState_window是mState的缓冲窗口，我们支持w和sw可以从0到window长度的自动循环。由于模式匹配算法需要一定长度的子串进行搜索，因此算法的第2~4行需要根据window中的LZ77数据初始化一个长度为max_pat_len字符串。此时，索引w位于max_pat_len位置，搜索索引sw位于0位置。模式搜索全部在sw。第5~24行是算法3的主体，它循环处理LZ77数据。第6~11行是处理ASCII字符的情况，在第10行更新缓存的索引。开始时，位于w位置的mState窗口没有得到匹配的状态，所以在第8行设置mState_window_w为0。第9行是搜索部分，它从搜索索引sw开始，而不是w。第11~23行是处理指针(length, distance)的过程。第13行根据指针(length, distance)更新window。第14~22行是跳过的关键，通过扫描复制字符串，如果在w位置处的已知指针长度大于等于mState的绝对值，则可以确定该位置的mState值可以重复使用指针指向相应位置处的mState值，否则设置为0。该算法在第10行和第22行有sw和w对来更新操作。第8行和第15~19行是在位置w处mState的过滤过程，只有通过该位置，sw到达时，mState才有效。

在算法3中第9行和第20行，Skip()函数用于搜索一个字符段，它根据mState的值确定是否需要模式搜索。Skip()的过程如算法4所示。如果mState大于0，则则从该位置开始向后有一个匹配的子字符串。如果mState小于0，则从该位置后向没有成功匹配的子字符串。以上两种情况都可以跳过。但如果mState等于0，则无法判断匹配信息，所以直接用Search()进行搜索(见3.2节)。

根据算法3和算法4，我们可以看到mState主要由sw处的Search()函数更新，但算法3中w处的mState信息需要在第8行和15~19行进行过滤。mState只有在剩余拷贝长度l-i大于或等于mState绝对值(算法3第15行)时才有效，然后可以直接使用搜索指针来使用mState信息。

4. 试验评估

4.1. 实验设计

本文的实验规则集为Snort‎ ‎ [20]、ModSecurity [21] 和random rules，Snort和ModSecurity的特点如表2所示。目标数据集是从Yahoo！网站爬取的50 MB网页数据。实验环境是g++4.8.4，Ubuntu 14.04，2核intel e5-2620 v3 CPU，2 GB内存。

表2. 规则集的特征

SMCH算法在不改变原算法数据结构的前提下，跳过了一些字符，因此我们主要考虑跳过率和加速率。跳过率是跳过的字符数与正常文本长度的比。加速比是解压缩和匹配的总时间(decompress & match)与压缩匹配(Compressed Match)的总时间之比。前者包括GZIP数据解压为纯文本数据的时间和原始模式匹配算法在纯文本上搜索匹配的时间。后者包括GZIP数据被解压成LZ77数据的时间和SMCH算法处理LZ77数据的时间。实验输出全部归一化。

$\text{skip}\text{ratio}=\frac{\text{number}\text{of}\text{skipped}\text{characters}}{\text{length}\text{of}\text{plain}\text{text}}\times 100\%$ (1)

$\text{accelerate}\text{ratio}=\frac{\text{total}\text{time}\text{of}\text{decompress}\text{\&}\text{match}}{\text{total}\text{time}\text{of}\text{compressed}\text{match}}\times 100\%$ (2)

值得一提的是，与匹配的时间相比，解压缩的时间非常少，并且GZIP数据解压为LZ77数据的时间比将GZIP数据解压为原始文本数据的时间要小一些。因此，我们在总时间里把它们放在一起讨论。

4.2. 性能评估

在本节中，我们主要讨论SMCH算法的性能。实验中使用了公共规则集(Snort和ModSecurity)。实验结果如图7所示，可以看出，SMCH算法可以大大提高原模式算法的匹配速度。与原始WM算法相比，SMCH在Snort和ModSecurity中的速度分别提高了441%和385%。

图7. 归一化时间

此外，本文还选择了两种典型算法ACCH [16] 和SPC [17] 作为对比。图8(a)显示了算法的加速性能。与原有的模式匹配算法相比，SMCH算法的性能有了很大的提高。SMCH算法在Snort和ModSecurity中的加速比分别为5.41和4.85。另外，无论是ModSecurity还是Snort，SMCH的加速比都大于ACCH和SPC，它们都小于2.00。

如图8(b)所示，SMCH算法在ModSecurity中的跳转率可以达到91.6%左右，在Snort中可以达到86.8%左右。在ModSecurity中，SMCH的跳过率略高于ACCH和SPC；在Snort中，SMCH的跳转率远远高于ACCH和SPC，SMCH的跳转条件非常简单，因此SMCH可以比ACCH和SPC跳过更多的字符。

图8. 加速率和跳转率

4.3. 算法的扩展性

在本节中，我们将探讨SMCH算法的可伸缩性。主要考虑两个因素：模式的平均长度和模式的总数。由于SMCH算法中的跳转与模式的长度有关，而WM算法在大规模模式应用场景中仍然能够保持稳定的性能。因此，我们基于这两个因素测试算法的可扩展性。实验中，以随机方式生成模式集，目标文本不变。实验结果如图9和图10所示。

图9. k = 1000时的归一化时间

在图9(a)中，模式的总数从20,000增加到100,000，并且模式的平均长度为10。在图9(b)中，模式的平均长度在5到30之间，模式的总数为20,000。可以看出，SMCH算法的速度基本稳定。同时，随机规则中SMCH的加速比也很高。显然，SMCH算法不会破坏原有的算法结构，因此SMCH算法具有很好的可扩展性。

图10(a)和图10(b)是SMCH算法的跳过率的结果。结果表明，模式总数和模式平均长度对跳过率影响不大。SMCH算法中的跳转与模式长度有关。模式长度越长，跳越的可能性越小。但如果模式很长，匹配的可能性也很小。另外，如果匹配失败，仍然可以返回mState。综上所述，跳转虽然与模式长度有关，但跳转率不受影响。

图10. k = 1000时的跳跃率

SMCH算法具有较高的跳过率、高加速比和可扩展性。因此，与原有的模式匹配算法相比，SMCH算法在不增加其他负担的情况下，可以很好地与原算法共存，甚至可以获得非常高的性能提升。

5. 总结

HTTP压缩技术已经得到了广泛的应用，因此我们应该利用压缩数据的特征，来提高匹配性能。本文提出的SMCH算法可以充分利用压缩数据的特性，提高原模式算法的性能。mState作为SMCH与模式匹配算法之间的一个纽带，使得SMCH对模式匹配算法的依赖性降低，在不改变原算法结构的情况下，可以与模式匹配算法无缝结合，从而获得SMCH的强大应用价值。

文章引用

田 源,蒋志颀. 针对HTTP压缩流量的基于跳跃的多模式匹配算法
Skipping-Based Multi-Patterns Matching Algorithm for Compressed HTTP Traffic[J]. 计算机科学与应用, 2020, 10(09): 1595-1608. https://doi.org/10.12677/CSA.2020.109168

参考文献