计算机安全
入侵检测与匹配算法

BM、比特并行与算法比较

来源:IDS 课件第 63–83 页。

1. BM 从右向左比较#

BM(Boyer–Moore)在当前窗口中从模式末端向前比较。失配后,利用坏字符和好后缀规则移动整个窗口,通常可以跳过一些起点。

**坏字符规则:**设在模式下标 j 处遇到文本字符 c,找 c 在模式中的合适出现位置,使其对齐;若不存在,可跳过更大距离。

例:P=ABCD,当前窗口最后一位是 X。X 根本不在模式中,可以移动 4 位。若末位是 B,可把模式中的 B 对齐到它,移动 2 位。

**好后缀规则:**若末尾已经匹配了一段 u,则寻找模式中更靠左的合适 u 出现位置;没有则寻找 u 的后缀中能与模式前缀重合的部分。

两种规则给出可行移动量,标准实现结合使用,选择满足正确性的更大位移。

2. BM 的性能不能只背“最快”#

课件给出基本 BM 的最坏情况可为 O(nm),加合适改进可达到线性最坏界。许多实际文本中跳跃会很有效,但性能受文本、模式、字母表和实现影响。

“从右比较”指窗口内比较顺序,不是把整段文本从末尾扫到开头。

3. NFA 与 DFA#

DFA 在一个时刻处于一个确定状态;NFA 的模拟可维护一组同时活跃状态。NFA 不是“随机选一条路”,而是接受性按可能路径定义。

模式匹配可以把每个前缀看成状态。比特并行用一个机器字中的多个 bit 表示多个前缀是否活跃,用一次位运算并行更新。

4. Shift-And#

约定模式从左到右第 i 个字符对应从低到高第 i 位,1 表示匹配状态活跃:

B[c]:模式中等于 c 的位置置 1
D 初始为 0
每读入一个字符 c:D = ((D << 1) | 1) & B[c]
若 D & (1 << (m−1)) 非零,则有模式在当前位置结束

左移是延长旧匹配;OR 1 允许从当前字符重新开始;AND B[c] 只保留符合当前字符的状态。

手算 P=aba,T=ababa#

用三位二进制显示,最低位表示匹配了第一个字符 a:B[a]=101,B[b]=010。

当前输入 D(仅保留3位) 是否完整匹配
a 001 否
b 010 否
a 101 是,结束于第3个字符
b 010 否
a 101 是,结束于第5个字符

所以起点是 1、3(这里按 1 起始编号)。位向量可以同时记住多个长度的匹配前缀。

5. Shift-Or#

改用 0 表示活跃,掩码中对应字符位置为 0,其他为 1:

D 初始为全 1
D = (D << 1) | B[c]    # 在固定有效位宽内处理
最高模式位为 0 表示完整匹配

Shift-And/Or 的状态含义相反,初始化、掩码和判定条件必须成套使用。

当 m 不超过机器字长 w 时,单字操作模拟很高效;超出时要跨多个字处理,不能继续假定每字符仅一个普通机器字操作。

6. 通配符与多模式边界#

课件的通配符 * 表示匹配一个任意字符,可把该位置在所有字符掩码中置为可匹配;不要和某些正则/文件匹配语法中的“任意长度”混淆。

AC 的状态转移结构不是一条简单线性链,不能把 AC 节点随便编号后直接套同一个 Shift-And 左移公式。

7. 算法比较#

算法 场景 主要思想 本课复杂度要点
蛮力 单模式、简单实现 每位置重新比较 最坏 O(nm)
MP/KMP 单模式 利用前缀/后缀回退 O(n+m)
AC 多模式 Trie+fail+output 适当假设下 O(n+occ) 搜索
基本 BM 单模式 从右比较并跳跃 课件给出最坏 O(nm),有线性改进
Shift-And/Or 短模式等 位运算模拟状态集合 m≤w 时每字符常数个字操作

不要只按复杂度符号认定实际运行速度;预处理、缓存、输出量、字母表和模式分布都影响结果。

— 本篇阅读完毕 —
来源:计算机安全知识点 / 05_入侵检测与匹配算法/04_BM_比特并行与算法比较.md 下载原文
输入关键词,在三个知识库中搜索
支持正文检索 · 直接定位章节Esc 关闭