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

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

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

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.