论文部分内容阅读
正则表达式匹配是计算机研究领域的一个经典问题，是众多网络安全系统中的关键技术之一。随着互联网的的普及和发展，海量信息的处理和新的应用需求对正则表达式匹配技术提出了新的挑战。本文对面向深度包检测的正则表达式匹配技术进行了研究。正则表达式匹配技术主要有基于NFA的匹配技术、基于DFA的匹配技术、基于NFA和DFA的混合匹配技术、位并行匹配技术和过滤匹配技术。目前的应用系统主要使用基于NFA的匹配技术，但由于该技术匹配速度较慢，不能满足日益增长的应用需求，因此人们把目光集中在匹配速度更快的基于DFA的匹配技术上。DFA具有O(1)的状态转移时间，却带来了存储空间急剧膨胀的缺陷，目前的解决方法主要是对DFA进行压缩，以达到用较少存储空间获取更快匹配速度的目的。本研究主要内容及结果如下：
⑴自动机分割和状态偏移量压缩算法：以“分而治之”为基本思想，把自动机分割为Trie结构和回边结构，然后分别对其进行压缩。在Trie结构中，通过把形状相同的状态转化为等价状态进行压缩；在回边结构中，通过提取每列最频繁的元素构造出大量可合并状态进行压缩。实验结果表明，在随机数据和真实数据上，该算法取得了很好的压缩效果。
⑵簇分割自动机压缩算法：算法基于实验统计特征：每个状态的绝大部分转移边都会集中指向某几个簇。根据这一特征，本文作者把DFA的存储矩阵分成三个部分，分别对每个部分进行压缩。实验结果表明，在随机数据和真实数据上，簇分割算法都表现出比较好的压缩效果。
⑶正则表达式匹配技术的实验及测试平台：构建了一个正则表达式→DFA的实验平台以及一个测试数据生成平台。通过实验平台，可以方便地从正则表达式构建出DFA；通过测试平台生成的数据，可以方便地测试匹配结果的正确性。