串匹配算法及其网络内容分析中的应用.pdf

串匹配算法段荩在膀络内容分析中的应用：摘要 摘要 Internet是全球信息共享的基础设施，是一种开放和面向所有用户的技术。一方面要 保证信息方便、快捷的共享，另一方面要防止垃圾的传播。网络内容分析是一种管理信 息传播的重要手段。网络内容分析是网络信息安全核心理论与关键技术，对解决国民经 济发展和国防建设具有重大意义。研究网络内容分析所涉及的新理论、新体系结构、新 方法和新技术将是未来几年研究的重要挑战。 ～方面是人们生活越来越多地依靠网络，许多政府业务越来越多地使用网络，面另 一方面却是Internet上信息的鱼龙混杂，黑客、病毒、网络攻击等日益盛行。保护网络 空问的洁净，保护网络空间中的“国土”，已成为未来国家发展的重要问题，也是摆在 人们面前的一个巨大挑战。 从闪电般流逝的网络数据中查找到我们感兴趣的信息，无疑是一项非常富有挑战性 的工作。本文的工作是从研究面向宽带互联网的网络信息安全问题出发，对高速网络内 容分析所涉及的科学理论和关键技术进行了有益探索。本文从算法和框架两个层次来讨 论快速信息分析技术，有以下几点创新之处： 1．1．1串匹配算法IntMatch 从面向计算机指令层面来优化匹配算法，设计了一种新的串匹配算法。新设计的 IntMatch是一种简洁串匹配算法。它使用的数值计算代替字符比较的思想很容易推广到 其它领域，具有～定的理论价值。ImMatch算法可以在高速网络内容分析、大规模模式 IntMatch算法是一种跳跃型的算法，设计的主要思路是充分利用硬件整数操作的效率， 使用数值运算代替字节比较。 1．1．2关键词表达式匹配算法 for keywordsexpression，predicateMgofithm 经典的关键词表达式(queryexpressiont rule)是有哪些信誉好的足球投注网站引擎(webretrieve)和数据库等使用的查询语言。但是在网络内容分析系 统中，如果单纯使用关键词作为查询条件，会存在很多误报情况。所以网络内容分析系 统-般采用表达式作为查询条件。我们提出了一种新关键词表达式匹配算法。这种算法 改进了经典计数算法(predicatealgorithm)中不适合网络内容分析环境的数据 counting 结构，对比计数算法需要平方级的算法复杂度，新算法可以在线性复杂度完成内容扫描 阶段的关键词表达式匹配工作。关键词表达式匹配算法还可以广泛地应用于基于调用序 i 串匹配算法及其在数据流监管系统中的应用 列的入侵检测系统中。 1．1．3面向网络内容分析的文本表示方法 本文一种新的基于n-gram字的文本表示方法同时实现了一个文本分类系统。这个系 统自动提取网络内容分析所需要的关键词，进行网络内容的感情色彩判断和内容分类。 基于n．gram字的文本分类方法比基于单纯串匹配算法的文本分类方法正确率更高，而 且性能基本保持不变。与词、短语等向量空间的文本表示方法相比较，在正确率损失不 超过1％的前提下，大幅度地提高文本分类的速度。 1．1．4扁平结构的网络内容分析框架 扁平结构是高性能协议栈的一种实现方式。使用扁平结构，我们设计了--jfeo高速骨 干网络内容分析系统。系统针对大量数据连接的特定领域，采用了把应用层协议解析和 部分文档格式分析统一在一个层次处理的方式，可以在两次数据扫描中，完成应用协议 解析、文档格式分析和规则匹配工作。相对于先进行协议分析，再进行文档格式分析， 最后进行规则匹配的一般处理流程，这种新的框架，节省了多次数据复制和数据扫描的 时间，从而提高了网络内容分析系统的性能。同时，这种把各种应用层协议解析和各种 编码转换工作统一处理的方式，可以方便地增加新的应用协议和统一优化应用协议解析 的性能。我们实现的原型系统表明了这种把关键词扫描、协议分析、编码等融合在一起 的模型是可行的。 从更广泛的角度来说，网络内容分析技术是数据流管理的一个应用。数据流管理是 处理相对固定不变的大量查询和源源不断的流动数据的技术。我们一直有一个想法，就