HashTrie：一种空间高效的多模式串匹配算法-论文

1、 第 期 张 萍等 ： ：一种 空 间高效 的多 模式 串匹 配算 法 结构 ，将 空 间复杂 度 （ ） ；搜索阶段 （ 算法 ）的最坏时间复杂度为 上 ，利用双 数 组结 构表 示 （ ） 。 证 明 降为 （ ， 与字符集 大小口 无关。 根 据定 理 的分 析可 知 ， 本 文提 出 的 算法 的空 间 ）空 间复杂 度 ： 算法 包括 个 基本 的 数 据 结构 ：位 向量 、位 向量 和校 验散 列表 复 杂度 （ ） ， 进一步降 低了 空间 复 杂度， 明 显 优 于 和 算法 。 表 算法和 、 复杂度对 比 其 中 和 的大 小 均为 日， 用于 存储 所有 待校 验 的模

2、式串信息， 其存储空间大小为 （ ，所以 （ × （ ） （ ） 根 据算 法 中对 参 数 日 的选 择 ： ， 位 向量 、 位 向量 和校 验 散列表 总 的存储 空 间 空 间 以便 于在 位 向量 ，上 进行 操 作 ，其所 占 在预处理 时间方面 ， 算法 的预 处理 时间 复杂度也是最低 的。 和 算法 的预处理 时间与 为 （ 。此外， 算法还需要额外的辅助 模 式 串规模 和字符集大小 口 相关 ，而 仅 用的存储空间为 （ 。 综上， 算法 的空间复杂度为 （ 。 预 处理 时间复 杂度 ：在预 处 理阶段 ，需要 计 与模式串规模线性相关，与字符集大小 口 无关

3、。 在 搜索 时 间方面 ， 算法 的最 坏 时间 复 杂 度 与 最长 模 式 串的长 度 。 线 性相 关 ， 高于 算 法和 算法 。但 是 ，下一 节 中的实 验结 果表 明， 算法的平均识别长度 （ 算法 中变量 ，的平 均值 ）通 常 是 比较 小 的 ，远 远小 于最 长模 式 串长 度 。 因此 ，在 随机情 况下 ， 算法 的平 均搜 索时 间复杂 度 可 以认 为 是 （ ） 。 算所有模式 串的每个前缀的散列值，并在位向量 中将相 应 的 比特 置 。对于模 式 串集 合 ，总 的前 缀 数 为 。 通 过递 归 散列 函数计 算每 个模 式 串前 缀 的散列值仅需要 （

4、 的时间， 因此， 构造位向量 的时间为 （ 。同 样地， 构造位向量和校验散 实验 评 估 本 节从 存储 空 间、匹配速 度 和预 处理 时 间 个 方 面 ，将 自动 机 的指针 实现 方式 （ ） 、表 实 现方式 （ ） 、双 数组 实 现 方式 （ ）和本 文 提 出的 算法 进行 对 比。此 外 ，在 随机 数据 集 上对 算法 的平 均 识别长 度进 行统 计 ， 考 察模 式 串长 度 和平 均识 别长度 的关系 ，从实验 结 果 上对 算 法在 搜素 阶段 的平 均 时 间复杂 度 列表 的时间为 （ 。 此外， 还需要在位向量 上 构造 操作 所 需 的辅 助数 据 结构

5、 ，其 时 间复 杂度为 （ 日 ） （ ） 。 因 此， 算法 预处理 阶段的时间复杂度为 （ ） 。 ）搜 索 时 间复杂 度 ：在搜 索阶 段 ， 对 于每 个 文 本 位置 ，需要 从 当前 位置 开 始搜 索可 能 出现 的模 式串， 搜索的 最大 深度为 ， 。 搜索时， 每处理一个文本字符（ 计算散列值） 的时间为 （ 。 因此 ， 算 法在 搜索 阶段 的最 坏 时 间复杂 度 进 行 实验性 分析 。 实验 的软硬 件 环 境 如 下 。 ： （ ） （ ） ；内存 ： ； 硬盘： ；操 作系 统 ： ；编译 环 境 ： （ ） 。 为 （ ） 。 表 是 算法 同经 典 的

6、 算法 【 、基 于 双数 组 结构 实现 的 算法 （ 简 称 ） 的空 间 和 时间复 杂度 比较 。 在存 储 空 间方面 ， 算 法 的空 间 开销主 要 用 于存 储状 态 转移 的二维矩 阵，因此其 空 间复杂 度 与 字 符集 大小 盯成 正 比 。 算法 在 算 法 的基 础 测试 数据 集包 括两 部分 ：开源 系统 中提取 的真 实数 据集 和随 机生 成 的数据 集 。其 中真 实数据 集 包 括 入 侵 检 测 数 据 集 、 规 则 集 【 、 规则集 、 数据 集（ 。所采 用数 据集 简 要 介绍如 下 。 夕 通 信 学 报 第 卷 ） 入侵 检测 数据 集 ：

7、来 自 公 开 的网 络入 侵检 测数据 集 （ ） ，用作 匹配 和 规则 集 的待扫描 文本 。 ） 规 则集 ：从开源 入侵 检测 系统 中 提取 的 条规 则 （ ） ，作 为待 匹配 的模 式 串集合 。其 中最 长模式 串长 度 为 ，最 短模 式 串长度 为 。 的匹配 速度 为上 述算 法 的 。 在 随机 数据 上 ， 算法 显著 快于 和 算 法 ，与 的匹配速度 相 当 。 的 匹配速 度分 别为 、 和 的 倍 、 倍和 倍 。 此 外 ，本文 还在 随机 数据 集上 测试 了算法 的匹 配 速度 与模 式 串个数和 长度 的关 系 。实验 结果 如 图 和 图 所 示

8、 。 ） 规则集 ： 从 开源 反病 毒系统 中抽取 的 条规 则 （ ） ，作 为待 匹配 的模式 串集合 。其 中最 长模 式 串长 度 为 ，最 短 模 式 串长度 为 。 ） 数据集 ：从 网络流量 中采集 的约 万 （ ）条 规则作为待扫描文本 ，从 中抽 取了 万条 规则作 为待匹配的模式 串集合 。 其 中最长模式 串长度 为 ，最短模式 串长度 为 。 ）随机 数据 集 ：随机 生 成 模式 串集 合 和 待 扫 描 文 本 。模 式 串 和文 本 中 的字 符 服 从 等 概 率独 立 同分 布 ，生 成 每 个 字 符 的概 率 为 。模 式 串个 一 里 ） ， 髓 数由

9、 变化到 ， 长度为 ， 待扫描文本大 小为 。 表 是 与 、 、等算 法在 上 述数据 集 上 的实验 结果 。 存储 空 间 模式串个数 图 在随 机数据 集 上（ 固定 ， ， ） ， 、 、 、 算法的匹配速度与模式串个数的关系 在存 储 空间方 面 ，从表 中的实 验结 果可 以看 出 ， 算 法是所 有测 试算 法 中 占用 空 间最少 的。以 规则集为例 ， 算法 比指针方 式 实现 的 算法 节 省 了 的存 储空 间 ， 比表 结 构方 式实 现 的 算 法 节省 了 的存储 空 间， 比双 数组 结构方 式实 现 的 算 法 节 省了 的存 储 空间 。 算 法 的 内存

10、 空 间 占用依 赖 于模式 串的个数 、长 度 以及字符集大小等因素。算法所采用的数据结构 直 接 决定 了其所 占用 的 内存 空 间大小相较 于 、 、， 算法 在 内存空 间 占用上 要远 远 低于其 他 种算 法 ，是 一种 空 间高效 的多模 式 串 匹 配算法 。 模 式 阜长厦 图 在随机 数据 集上 （ 固定 ） ， 、 、 、 算 法 的匹配 速度 与模 式 串长 度 的关系 在 图 中，固定模 式 串长度 ，模式 串个数 从 增 加 到 ，考 察算 法 匹配速 度 随着 模式 串个 数变 化 的关系 。从 图 中可 以看 出，随着 匹配 速度 在 随机 数据集 上 ， 算

11、法 的匹配速 度约 为 、 和 的一 半左 右 。 具 体地 ， 在 规 则 集 上 ， 的 匹 配 速 度 为 上 述 算 法 的 ；在 规 则集上 ， 的 匹配 速 度 为上述 算法 的 ；在 规则 集上 ， 模式 串个数的增加，种算法的匹配速度均有所下 降。模式 串个 数在 万 至 万 之 间 ， 算 法 的匹配速 度 高于其 他 种算 法 。随着 模式 串数 量 的 增加 ， 算法 的匹配 速度 高 于 和 ， 第 期 张萍等： ：一种空间高效的多模式串匹配算法 是 和 的 倍。 在 万至 万之间， 算法 低 于 算 法 。 的平 均 识别 长 度 为 算 法 在 搜索 阶段 的平 均

12、扫 描深 度 ，即扫描 过程 中在 每一 个文 本位 置跳 出 循环 所 需扫描 的字 符 串长度 （ 算 法 中变 量 ， 的平 均值 ） 。实验 在 随机 数 据 集上 进 行 ， 固定 模式 串个 数 ，命 中率为 ，模 式 串长度 从 变 化到 。实验 结果 如 图 所示。 在 图 中，固定模式 串个数 ，模式 串 长度 从 变 化 到 。从 图 中可 以看 出 ， 算法 的匹配速度是经典算法 的 倍左右，相 比于 和 算法， 与 更适合于 较长模式 串的匹配 问题 。随着模 式串长度变化 ， 算法 本 身 的匹配速 度变 化 相对平 稳 。 预处 理 时 间 在 实时入侵检测 系统中

13、 ， 具有较短预 处理时 间的 串匹配算法 更能满足检测规 则生效 的时效性要 求 。因 此 ，预 处理 时 间是衡量算法 好坏的一个重要 指标 。 萤 酿 从表 中的实验结果可知， 算法在所 有数据集上的预处理时间均是最短的。 比 经典 的 算 法 节约 的预 处理 时 间 ，比表 方 式 实现的 算法节省了 的预处理时间，比双 数组结构实现 的 算法节省了 的预处理时 间 。因此 ， 算 法更 能满 足实 时入 侵检 测系 统对 规 则生 效 的时效 性要 求 。 平 均 识别 长度 最坏 情况 下 ， 算 法 的搜 索 时间 复杂度 与最长模式串长度 ， 成正比， 但是在平均情况下， 的

14、 搜 索 效 率 是 比 较 高 的 。 为 了 评 估 在 平 均情 况下 的搜 索效 率 ，定 义 表 模式串长度 图 算法在 随 机数据 集 上 的平均 识别 长度 从 图 可 以看 出 ，随着 模式 串长 度从 变 化到 ， 算 法 的平 均识 别长 度均 小于 ，远 远 小 于 最 坏 情 况 下 的识 别 长 度 （ 即最 长 模 式 串长 度 蛐） 。因此 ，在随机情况下 ， 算法的平均 算 法与 、 、 实验结果对 比 ， 通 信 学 报 第 卷 搜索时间复杂度可 以认为是 （ ） ，与 、 和 等算 法相 当 。 【 】 ， ： ， ， （ ） ： 【 】 ， ， ， （ ）

15、 ： 结 束 语 本 文 提 出 了一 种 基 于 前 缀 搜 索 的多 模 式 串匹 配算 法 ，与经 典 的多模式 串匹配算 法 、 和 算法 相 比， 大 大减 少 了存储 】 ， 】 ， ， 】 】 空 间消耗 ，存储 空间仅 与模式 串规 模线 性关 系 ，与 字符集大小 无关。在真实数据集和随机数据集上 的测 试 结 果表 明， 算 法 比 节 约 高达 的内存空 间 ，匹配速 度约 为 算 法 的一半 至 倍 。此外 ， 算法 在所有 数据 集上 的预 处理 时 间均是 最短 的，比 、 和 等 算法 节省 了约 的预处 理 时间 。 更适合 模式 ， 】 ， 【 ： 【 】 何

16、慧敏， 刘燕兵， 谭 建龙 ， 等 一 种 基 于 子 串 识 别 的 多 模 式 串 匹 配 】 算法 】 计 算机 应用 与软件 ， ， （ ） ： ， ， ， 串集合规模较大、 模式串长度较短的多模式串实时 匹配 问题 。下一步将研究在 上对 算 法进 行优 化 的策略 以提 高其 匹配速度 。 参考 文献 ： 】 ： ， ， （ ） ： ， 【 （ ） ， 【 ， ： ： ： ： ； ， 】 、 ： ， ， （ ） ： 作者简介： 张萍 （ ），女 ，河南唐河人，中 国科 学院博士 生，主要研究方 向为网络与 信息安全 、内容过滤等 。 【 】 ， ， ， （ ） ： 】 ， ， ， （ ） ： 【 】 ， 【 】 ： ， ， ） ： 【 】 ， ， ， 【 】 （ ） 】 【 】 乙 ， 髓 ， ： ：