用优化的正则表达式引擎进行快速网络流分类

摘要

自从互联网诞生以来，网络流分类就成了众多网络相关任务中的一种，也逐渐成了人们集中研究的对象。网络流的分类与识别是网络流量工程、入侵监测与防御、包过滤、网络设计与规划等网络行为的前提和基础，因此准确高效地识别网络流对于分析网络发展趋势和检测网络异常行为都有着很重要的现实意义。
　　本文主要研究快速网络流分类优化技术，包括面向网络流的正则表达式匹配技术和基于云计算平台的大数据网络流分类技术。对于正则表达式匹配技术，目前应用的系统是基于NFA(Non-deterministic Finite Automata)的匹配技术和基于DFA(Deterministic Finite Automata)的匹配技术。NFA技术匹配速度较慢，因此人们把目光投向了匹配速度更快的DFA技术，DFA具有O(1)的快速状态转移时间，却带来了空间爆炸的缺陷，需要对DFA进行空间压缩优化。另一方面，随着现在网络通信量急剧增长，俨然进入了大数据领域，单机下已经不堪重负，无法有效的完成流量分类任务，需要针对大数据流量的分类方案。
　　具体来说，本文的研究工作及方法主要集中在以下两个方面:
　　(1)使用优化的DFA空间压缩技术和状态匹配速度提高技术进行快速网络流分类。通过调研DFA空间爆炸的本质因素，研究出合适的空间压缩算法和数据结构对状态和转移边进行压缩。由于在对DFA进行空间压缩后，其状态转移查询可能没有直接访问传统DFA的状态转移二维表快速，即经过空间压缩后匹配速度可能会有所降低。为此，我们从提高匹配成功的速度和匹配失败的速度两方面来进一步提速，并与传统的DFA匹配效率进行对比。
　　(2)研究基于Hadoop云计算平台的大数据网络流分类技术。运用HadoopStreaming技术将单机下的网络流分类系统部署到Hadoop平台下，解决Hadoop平台本身不支持二进制网络流输入格式的问题，并通过Hadoop平台调优技术优化各参数，使其更好的应用到云平台上，从而能够充分运用云平台的并行技术实现快速网络流分类。
　　经过实验论证，我们提出的DFA优化技术能达到平均99％的压缩效率且压缩后的匹配效率是原DFA的3～5倍。另外随着流量数据的增多，在Hadoop平台下进行分类的优势越来越明显，远超过单机下的分类效率。本文提出的这两种技术给大数据网络流的快速分类和实时分类带来了借鉴意义，有一定的应用价值。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．2 研究现状

1．3 研究内容

1．4 论文结构

第2章 网络流分类和Hadoop相关技术

2．1 网络数据流

2．2 网络流分类技术

2．2．1 基于端口的分类方法

2．2．2 基于载荷特征的分类方法

2．2．3 基于流统计特征的分类方法

2．2．4 基于主机行为特征的分类方法

2．2．5 基于图的技术

2．3 正则表达式匹配技术

2．3．1 正则表达式

2．3．2 非确定型有限自动机匹配技术

2．3．3 确定型有限自动机匹配技术

2．3．4 NFA与DFA的比较

2．4 Hadoop云平台技术研究

2．4．1 云计算思想

2．4．2 Hadoop云平台的优势

2．4．3 Hadoop的工作机制

2．4．4 Hadoop平台的参数调优

2．4．5 Hadoop Streaming技术

2．5 本章小结

第3章 优化的DFA正则表达式匹配引擎

3．1 选择DFA引擎的原因

3．2 DFA引擎的不足

3．3 优化的DFA空间压缩技术

3．3．1 DBDFA的基本思想

3．3．2 问题形式化描述

3．3．3 DBDFA构造思路

3．3．4 一个例子

3．3．5 DBDFA算法描述

3．3．6 DBDFA匹配过程

3．4 改善的DFA状态匹配技术

3．4．1 快速匹配失败机制

3．4．2 优化的缓存技术

3．5 实验验证及结果

3．5．1 实验环境

3．5．2 DBDFA的压缩效率

3．5．3 DBDFA的匹配效率

3．6 本章小结

第4章 基于Hadoop云平台的网络流分类系统

4．1 Hadoop下的网络流分类技术难题

4．2 支持二进制流输入格式的MapReduce模型

4．3 基于Hadoop的网络流分类模块

4．4 实验验证及结果

4．4．1 实验环境

4．4．2 匹配效率对比

4．5 本章小结

第5章 总结与展望

5．1 本文工作总结

5．2 未来工作展望

参考文献

附录

致谢

在读期间发表的学术论文与取得的其他研究成果