原课件;共83页。以下是文字提取,未经逐句纠错;图中文字、截图代码、公式对象及动画关系可能无法完整提取。阅读主题笔记后,可按页码回原文件查看。
第 1 页#
计算机安全 @ 入侵检测系统 |
备注区文字#
大家好。本节课我们介绍对称密钥加密算法。
|
第 2 页#
内容提要 入侵检测系统概念 入侵检测系统误报率与贝叶斯定理 入侵检测系统实例 Snort 入侵检测系统检测算法 模式匹配算法 多模式匹配算法 现代方法 2 |
第 3 页#
入侵检测系统 入侵(Intrusion)定义为未经授权的计算机使用者以及不正当使用(misuse)计算机的合法用户(内部威胁),危害或试图危害资源的完整性、保密性、可用性的行为 入侵检测(Intrusion Detection,ID)通过监测计算机系统的某些信息,加以分析,检测入侵行为,并作出反应 入侵检测系统(Intrusion Detection System,IDS)是实现入侵检测功能的硬件与软件。入侵检测基于一个观察,即:许多入侵行为与正常行为有显著的不同,因而是可以检测的 预防 Prevent 检测 Detect 恢复 Restore 反应 Response Protect |
备注区文字#
入侵属于对计算机系统的不正当使用。
|
第 4 页#
入侵检测系统结构 事件产生器(Event generater, E-box)收集入侵检测事件,并提供给IDS其他部件处理。事件可以是网络活动也可是系统调用序列等系统信息。 事件分析器(Analysis engine, A-box)对输入的事件进行分析并检测入侵。 事件数据库(Event database, D-box)存储和管理E-boxes 和 A-boxes 产生大量数据,用于IDS的训练和证据保存。 事件响应器(Response unit, C-box)对入侵做出响应,包括向管理员发出警告,切断入侵连接,根除入侵者留下的后门以及数据恢复等。 、 |
第 5 页#
入侵检测系统分类 检测方法 误用检测(misuse detection) 异常检测(anomaly detection) 混合检测 数据源 来自主机,系统调用序列,存储系统的活动记录,系统日志等 来自网络,网络包 |
第 6 页#
入侵检测系统检测方法 误用检测 也称为基于特征的检测, 建立已知攻击的知识库 判别当前行为是否符合已知的攻击模式 机制:状态模型、专家系统、正则表达式匹配 异常检测 也称为基于行为的检测 建立用户的正常使用模式知识库 标识出不符合正常模式的行为 机制:统计、机器学习方法 |
第 7 页#
入侵检测系统的评价 处理高速网络流量的能力 自身抗攻击的能力 误报率和漏报率 协同事件的能力 检测新攻击的能力 |
第 8 页#
误报率-混淆矩阵 正常 攻击、 不可判定 攻击 报告攻击 正常 报告正常 误报率:误报的数量占所有正常事件的比例 |
第 9 页#
一个思想实验 一个精确的异常检测系统。检测的准确率为99%。 恶意事件的出现率为1/10000。 问题:当系统报告一个攻击时(A),正确的概率(是攻击事件T)是多少? 估算:检测的准确率大于多少时,当系统报告一个攻击时(A),正确的概率接近50%。 2026/11/3 9 |
第 10 页#
Bayes定律 P(B|A)=P(A|B)P(B)/P(A) P(A):事件A的概率 条件概率 P(A|B):在给定事件B发生时发生事件A的概率 P(A|B)=|A∩B|/|B| 2026/11/3 10 A B A∩B |
第 11 页#
计算P(T|A) 攻击的概率 P(T)=1/10000 事件被报警的概率P(A)未知 P(A|T)=99%, P(A)=P(A|T)P(T)+P(A|!T)P(!T) =0.99*0.0001+0.01*0.9999=0.10098 根据Bayesian定理 P(T|A)= P(A|T)P(T)/P(A)=0.00098 2026/11/3 11 |
第 12 页#
IDS误报率 现实中,攻击行为占比很少。导致正确率很高的检测器可能有较高的误报率。 例如设检测器检测正确率为99%,攻击占全部事件的1%,则: 报警的准确度为1% 99%为误报 IDS的核心问题:降低误报率! |
第 13 页#
网络入侵检测系统Snort 著名开源NIDS,采用误用检测,包含:网络包的解析器、检测引擎、日志和报警子系统 利用libpcap库作为捕获数据包的工具 特点 设计原则:简单、灵活、高性能 协议分析和模式匹配、正则表达式匹配 特征描述语言:可描述攻击行为 插件子系统:实现系统功能扩展 |
第 14 页#
网络数据包解析 按照网络协议栈的分层解析包 按照协议层次依次处理各层包头 每一层协议栈都对应一个处理函数 从链路层,到传输层,直到应用层 支持链路层和TCP/IP协议 以太网、令牌网、FDDI |
第 15 页#
Snort的规则 pcre alert tcp any any -> 192.168.1.0/24 111 (content:"|00 01 86 a5|"; msg: "mountd access";) 规则头 规则选项 Snort的规则: 针对已经发现的攻击,编写规则 响应方式(alert),协议(tcp),以及IP地址和端口号, content域指定了在包数据中搜索的内容模式 |
第 16 页#
规则选项 content 和 pcre content: 用于匹配固定字符串,适合匹配简单的特征。 pcre: 用于匹配复杂的模式,支持正则表达式,适合匹配灵活多变的攻击 payload。 结合使用: 将 content 和 pcre 结合使用,可以提高检测的准确性。例如,使用 content 匹配关键字,使用 pcre 匹配变量部分。 其他选项 nocase: 忽略大小写。 depth: 指定搜索的最大深度。 offset: 指定搜索的起始位置。 distance: 指定多个匹配内容之间的距离。 fast_pattern: 使用快速模式匹配。 http_uri: 匹配 HTTP URI 部分。 session: 记录指定会话的应用层信息。 规则与性能 先处理匹配几率低的规则选项(如内容匹配),排除后续操作 16 |
第 17 页#
Snort规则实例 alert tcp $EXTERNAL_NET any -> $HOME_NET any (msg:"SHELLCODE x86 NOOP"; flow:to_server,established; content:"|90 90 90 90 90 90 90 90|"; content:"|90 90 90 90 90 90 90 90|"; content:"|90 90 90 90|"; pcre:"/\\x90{10,}/"; metadata:service http; classtype:shellcode-detect; sid:1390; rev:10;) alert tcp $EXTERNAL_NET any -> $HTTP_SERVERS $HTTP_PORTS (msg:"WEB-MISC SQL injection attempt"; flow:to_server,established; content:"union"; nocase; http_client_body; content:"select"; nocase; http_client_body; pcre:"/union(\s)+select/i"; content:"from"; nocase; http_client_body; content:"where"; nocase; http_client_body; metadata:service http; classtype:web-application-attack; sid:1000001; rev:1;) 17 |
第 18 页#
Snort规则数据结构 在Snort的检测引擎中规则被解析为决策树结构 |
第 19 页#
2026/11/3 19 针对IDS的拒绝服务类攻击 超载攻击 当网络流量超过IDS的处理能力时,IDS的处理能力将急剧下降甚至完全瘫痪。攻击者通过某些手段使网络流量达到饱和,迫使IDS大量丢包。这种攻击还可针对目标IDS系统采用的检测算法进行算法攻击。 资源耗尽攻击 通过发送大量残缺TCP数据段以及IP分片耗尽IDS的存储资源,使IDS不能正常工作。 |
第 20 页#
加密流量处理 SSL/TLS解密(中间人方式) 元数据分析(Metadata Analysis) 分析HTTPS流量的元数据(例如,SNI、流量模式、连接频率等) 基于行为的异常检测(Anomaly-Based Detection) 对正常流量模式建模,来识别与正常行为偏差较大的活动 恶意软件、数据泄露 EDR(Endpoint Detection and Response,端点检测和响应) EDR部署在客户端设备上,可以直接查看未加密的流量和活动 20 |
第 21 页#
2026/11/3 21 IDS性能问题 在高速网络上工作 10Gbps以太网、G比特光纤网 … DPI处理能力显著下降,发生丢包、漏报 更复杂的攻击模式集合 模式数量巨大, Snort的模式数量接近10,000 攻击模式的描述手段:从字符串到正则表达式 空间占用和处理速度的两难问题 算法复杂攻击 使DPI算法进入最坏情况,造成拒绝服务。 目前除了通过修改算法还没有其他有效的方法。 |
第 22 页#
2026/11/3 22 IDS性能问题 DPI = 深度网络数据包检测 网络入侵检测系统(NIDS)、防火墙系统的核心功能 DPI深入到数据包的载荷处理 高层协议分析、攻击特征码匹配 协议分析。协议分析可以显著地缩小检测模式范围,从而减少内容检查,提高了入侵检测的效率。 内容检查。这是目前大多数网络入侵检测系统最重要的检测手段,内容模式取自攻击数据包的字符串特征。一般在协议分析之后对包内容进行特征串匹配,但相反的顺序可能提高检测效率 内容检查占全部处理时间的1/3 |
第 23 页#
2026/11/3 23 DPI vs 正则表达式匹配 DPI的中心问题:高效多正则表达式匹配 识别多表达式的DFA 高速度,对输入扫描一次 状态大爆炸 两个DFA的合并,状态数可能为二者之积 88个snort规则占用15G的内存空间 多个有限状态机 空间很小 速度差,需硬件支持 |
第 24 页#
提高IDS的性能 提高单机检测性能 采用高效检测算法 多模式匹配/多正则表达式匹配 采用高性能硬件 FPGA、GPU、多核处理器 多机并行 网络流量的分割 处理任务的分割 |
第 25 页#
IDS中使用的数据结构&算法 (组合)模式匹配算法 单模式匹配 kmp bm Sunday… 多模式匹配 AC WM… 正则表达式处理、非精确模式匹配 数据结构:AC自动机(TRIE)、后缀树、后缀自动机、后缀数组、紧凑数据结构 应用领域 病毒扫描、入侵检测、搜索引擎、大数据处理 |
第 26 页#
模式匹配算法 模式匹配算法 Brute Force算法 Knuth-Morris-Pratt (KMP) 算法 Aho-Corasick多模式匹配算法 Boyer-Moore算法 现代技术 后缀树与后缀自动机 基于因子识别的算法 Bit并行算法与非标准模式匹配 Snort IDS中的匹配算法应用 |
第 27 页#
Notions 字母表 ∑={1,2,…,σ} String t = t[1]t[2] ・・・t[n] on ∑ ε:空串 Substring(factor) 子串、因子 t[i.. j] = t[i] t[i + 1] ・・・t[j] Suffix: t[i.. n] 或 t[i..] 后缀 Prefix: t[1.. j] 或 t[.. j] 前缀 Concatenation: uv |
第 28 页#
蛮力算法Brute Force 模式P 长度为m 文本T 长度为n P在T的位置x处 出现: T = bacbabababacbb P = ababa x=4 ababa x=6 找到P在T中的出现的最直接的方法: 在T的所有位置上检查P的出现 运行时间: 最坏情况 O(nm) |
第 29 页#
Brute Force 对一个位置的匹配中已经获得了对于文本的”知识” 例如: P能出现在x+1, x+2么? |
第 30 页#
Brute Force 对一个位置的匹配中已经获得了对于文本的”知识” 例如: P能出现在x+1, x+2, x+3么? |
第 31 页#
观察 假设 P 在T[x…] 处匹配了 k 个字符 P[0..k-1] == T[x..x+k-1], 对于 0<r<k, 如果 T[x+r…x+k-1] 不是 P的前缀, 则 P 不能出现在 x + r 处 |
第 32 页#
略过位置 当 T[x..] 匹配了P的k个字符, P[0..k-1] == T[x..x+k-1] 我们可在最左 x+r 处重新匹配 如果T[x+r..x+k-1] 是P的前缀 略过了 r 个位置 |
第 33 页#
在此例中: 下一个匹配开始于x+3处 |
第 34 页#
在此例中: 下一个匹配开始于x+3处 |
第 35 页#
算 可略过的位置数 已匹配的前缀P[0..k-1], P[0..k-1]的后缀中最长的前缀为P[r..k-1] 则略过位置数为r K=3, r=3 K=5, r=3 |
第 36 页#
模式匹配自动机 字母表 ∑ 状态 i 代表前缀p[1,i]。 边 前向边,如果sa是P的前缀,则有边(s, a, sa), 记为 follow(s, a)=sa 后向边,如果sa不是P的前缀,则有边(s, a, s’), s’是sa后缀中最长的前缀 初始状态0,终止状态|s| p=ababba 的部分模式匹配自动机,只有前向边 |
第 37 页#
模式匹配自动机 p=ababba 的(full)模式匹配自动机 goto(i,a):串 p[1,i]a 后缀中最长的前缀 |
第 38 页#
fail函数 fail(s, i) 前缀 p[1, i] 的后缀中最长的前缀 引入状态⊥ (对应长度为-1的串) follow(⊥, 任意字符)=p0 fail(p0)= p-1=⊥ |
第 39 页#
通过fail计算goto函数 goto(4,a)=3 |
第 40 页#
通过fail计算goto函数 goto(5,b)=0 问题:自己动手计算goto(4,c) |
第 41 页#
Morris-Pratt (MP)算法 没有Kunth优化的算法 |
第 42 页#
MP算法 O(m+n) 第一个线性算法! MP算法对应的有限状态自动机. 模式p, |p|=m 状态集合:模式前缀集合, p为终止状态 follow Function, follow(s, a) 如果sa是s的前缀,则follow(s, a)=sa 否则follow(s, a)未定义 failure Function,后缀链接 fail(s):s的后缀(不包含s)中最长P的前缀 引入状态⊥ (对应长度为-1的串) follow(⊥, 任意字符)=p0 fail(p0)= p-1=⊥ |
第 43 页#
MP算法 goto(s,a) { while(follow(s,a)==未定义) s=fail(s); return follow(s,a); } Match(T) { s= p0; for( i=1 to |T|){ if( s 是终止状态 ) return 匹配!; else s=goto(s,T[i]); } } |
第 44 页#
fail函数的构造 fail(s)的定义: s的后缀(不包含s)中最长P的前缀 分层 递归 fail(p0) = ⊥ fail(pi) =? 看fail(pi-1)有没有字母为P[i]的边 如果有,则fail(pi) 是 此边指向的状态 如果没有,则沿着失败链向后找… 直到找到P[i]边,这条边指向的状态就是fail(pi) Compute_fail() { s = fail(p0) = ⊥; for( i =1 to |P| ){ s = goto(s, P[i]) ; fail(pi) = s ; } } 第i次循环中 s=fail(pi-1) |
第 45 页#
时间复杂(分摊分析) 对文本扫描一遍,无回头扫描 O(n) 调用了多少次fail函数? 从自动机看 向左的移动距离 >= 向左移动的距离=调用fail的次数 向右的移动距离= 对文本扫描的距离=n 调用fail的次数=O(n) fail构造复杂度 向左的移动距离>= 向左移动的距离=调用fail的次数 向右的移动距离= 对模式扫描的距离=m O(m) O(m+n) |
第 46 页#
Knuth-Morris-Pratt (KMP) 算法 KMP算法与MP算法的区别 |
第 47 页#
多模式匹配问题 在文本 T 中找到模式集合中模式的出现 模式集合: P Aho and Corasick,1975 基于有限状态自动机 AC自动机 |
第 48 页#
Aho-Corasick多模式匹配算法 AC自动机算法是MP算法的多模式扩展 AC自动机包括 Follow Function failure Function AC自动机goto函数的实现是用二者的结合 |
第 49 页#
Aho Corasick 自动机 follow function: a trie of the patterns failure function: 对于每个前缀, 其后缀中最长的模式前缀对应的trie节点 MP算法的fail函数的多模式推广 output function: 报告每个前缀的后缀中匹配的模式 |
第 50 页#
Trie 字符串集合的Trie结构是一颗树,对应于AC自动机的follow函数 模式的每个前缀对应一个状态 s和sa是模式的前缀,则有边(s,a,sa) 前缀压缩(合并) |
第 51 页#
Aho Corasick 自动机–trie h i he ir is her iri iris P = {her, iris, he, is} 模式的trie对应着AC自动机的 follow 函数 每个模式前缀对应一个状态 trie的边上的字母是边目标状态的最后一个字母 |
第 52 页#
AC自动机 - failure link h i he ir is her iri iris P = {her, iris, he, is} 缺省失败链接指向根 s的失败链接指向s的后缀中最长的模式前缀 从状态s起始的失败链接最终到达根,构成了s的失败链 |
第 53 页#
Aho Corasick 自动机- output h i he ir is her iri iris P = {her, iris, he, is} 如果当前状态的失败链中有状态有模式标志,则要加入匹配标志 对应着模式的状态加上模式标志位 匹配中若当前状态有匹配标志,则需要沿着失败链报告所有模式的匹配 |
第 54 页#
follow函数的实现方法 跳转表 O(1), O(|P||Σ|log|P|) 数组+二分查找 O(log|Σ|), O(|P|log|P|) 平衡二叉树O(log|Σ|), O(|P|log|P|) 紧凑数据结构O(1), O(|P|(|Σ|+log|P|)) 集合数据结构 |
第 55 页#
Aho Corasick – 分析 AC自动机构造算法时间复杂为 O(|P|) |P|模式集合中模式的长度之和 模式匹配搜索时间复杂 O(n + occ) occ为模式出现次数 ... 在固定字母表上! 对于整数字母表, Σ=O(nc), 用平衡树等结构 |
备注区文字#
text length + appearances O(m+k) Branching method determines the complexity of the query: However we can do better than this, like s.t. that are now built in linear time! Indeed our algorithm does better. |
第 56 页#
AC算法的模式匹配搜索时间复杂度中为何包含occ? 思考问题 |
第 57 页#
状态转换函数 引入状态⊥,状态转换简化为: goto(s,a) { while(follow(s,a)==未定义) s=fail(s); return follow(s,a); } 搜索时间复杂 O(n + occ) |
第 58 页#
failure链接的构造 按照节点的深度分层 按层由浅到深递增填写fail链接 时间复杂O(|P|) |
第 59 页#
模式匹配自动机 模式匹配自动机 取消失败函数 失败链接 边 (s, a, goto(s,a) ) 全部字母都对应跳转边 比AC自动机需要更多的空间 |
第 60 页#
思考 AC算法是MP算法的多模式扩展,如何将KMP扩展为多模式? |
第 61 页#
小结 蛮力算法 KMP模式匹配算法 AC自动机多模式匹配算法 重点和难点 失败链接 均摊分析 Knuth优化 61 |
第 62 页#
作业 编程实现蛮力算法,KMP算法。比较二者性能。输入包括随机串,模式重复串。考察二者在不同输入的性能差异。 编程实现AC自动机算法,包括AC自动机的构造、匹配算法实现。优化follow函数的实现。分析fail函数的特征,优化fail函数实现。 要求: 给出程序设计描述,结构描述。 给出程序测试,包括正确性测试和性能测试。设计测试实例,展示测试结果。 62 |
第 63 页#
Boyer-Moore (BM) algorithm 对模式 P 中的字符从右向左匹配:后缀识别 可不用扫描全部输入字符,平均匹配时间c·n, 常量 c <1 (随机或真实文本), 但最坏情况是O(n·m). 可以将BM算法的最坏情况改进到O(n),记录文本后缀中最长的模式后缀。 |
第 64 页#
Good-suffix shift
|
第 65 页#
Good Suffix位移 输入字符在模式x的位置z处失配 当前输入的后缀匹配了从z+1开始的x后缀u 情况1:找到u在z+1之前的最后一次出现位置z’,且x[z’]≠x[z]。重启匹配过程。新匹配窗口的结束向右移动 z - z’ 个字符。 情况2:u在z+1之前没有出现,此时确定u的后缀中最长x的前缀,窗口向右移动。 |
第 66 页#
Bad-character shift
|
第 67 页#
Bad-character shift 模式中不包含b |
第 68 页#
扩展的Bad-character shift 如果失配字母是x的最后一个字母 b Bad-character shift 为 0 优化后位移由b的倒数第2次出现决定 一个优化:b 在当前失配位置之前的最后一次出现,窗口位移由这个位置决定 保证了bad-character shift总会向右移动匹配窗口 |
第 69 页#
BM实例 7 6 54 3 2 10 模式x = GCAGAGAG 计算bad char: 输入字符b失配,b在反向第一次出现的反偏移 计算Good suffix:窗口右移长度 bmGS[i]:第i+1后缀匹配,但i处字母失配时,窗口向右移位的距离 特殊情况 bmGS有m个元素 bmGS[-1]=全匹配移位 相当于左结束符不匹配 x的最后一个字母G bmGS[G] = G的第二次出现 G作为失配输入,则x的匹配数>1,若使用原始Bc定义,导致窗口像左移 |
第 70 页#
计算Good suffix表 X代表失配 ???????????X? GCAGAGAG ????????XG? GCAGAGAG ??????XAG? GCAGAGAG 匹配窗口右移 ?????????X??? GCAGAGAG ????????XG??? GCAGAGAG ??????XAG??? GCAGAGAG |
第 71 页#
BM匹配实例
|
第 72 页#
KMP算法与BM算法的比较 KMP算法的实际性能不好,一般实际中不用 BM速度快,但最快的BM类算法不是完整BM算法而是简化的版本 复杂的算法反而比简单的算法实际性能差 |
第 73 页#
思考题 设计能够识别串s所有子串的数据结构与算法 输入p,能够在O(|p|)时间内判定p是否是s的子串 尽力压缩空间,试试能否达到O(|s|) word 设p=ababb,给出此数据结构实例 |
第 74 页#
Bit并行算法 非确定性自动机NFA 模式匹配NFA MP自动机的非确定化 形状极简单:线性,而非树、图 模式匹配NFA的使用 初始状态永远活跃 活动状态集合=当前输入中的后缀中匹配的所有前缀的集合 状态转换 活跃状态集合的转换 |
第 75 页#
NFA与DFA NFA需要并行机制的支持 适合硬件实现 空间占用小 DFA只需串行操作 适用于基于存储的系统 空间占用大 |
第 76 页#
模式匹配NFA的比特并行实现 比特并行 CPU对机器字的多个bit的处理是并行的 常见机器字长 32、64、128、256 算术运算 逻辑运算 假定模式长度小于机器字长! 模式匹配NFA状态与机器字的bit对应 保留顺序 Bit取值 1:对应状态活跃 0:对应状态未激活 |
第 77 页#
Shift-And 算法 模式p, |p|=m,输入t, |t|=n 状态向量D = dm…d1. p的每个前缀对应一个bit, di = 1 代表前缀 i 匹配 (匹配了已处理的输入的一个后缀) di = 0 代表前缀 i 未匹配 表 B:每个字母对应一个bit向量 B[a]=所有a在p中出现的位置置1,否则置0 状态转换 D ← ((D<<1) | 0m-11) & B [t[i+1]] |
第 78 页#
Shift-And 算法 Shift-And (p , t) 1. Preprocessing 2. For c ∊ Σ Do B[c] ← 0m 3. For j ∊ 1 ... m Do B[p[j]] ← B[p[j]] | 0m-j 10j-1 4. Searching 5. D ← 0m 6. For pos from 1 to n Do 7. D ← ((D << 1) | 0m-1 1) & B[t[pos]] 8. If D & 10m-1 ≠ 0m then report an occurrence at pos - m + 1 9. End of for |
第 79 页#
Shift-Or 算法 Shift-Or算法 观察:移位后,移入的bit是0 用0代表匹配,则无需 & 0m-11 状态向量D = dm…d1 di = 0 代表前缀 i 匹配 (匹配了已处理的输入的一个后缀) di = 1 代表前缀 i 未匹配 表 B:每个字母对应一个bit向量 B[a]=所有a在p中出现的位置置0,否则置1 状态转换 D ← (D<<1) | B [t[i+1]] 79 |
第 80 页#
Example Shift-Or 字符串是小端顺序比特向量是大端顺序 |
第 81 页#
通配符匹配 比特并行算法可实现带通配符的模式匹配 通配符 * 匹配任意字符 表 B:每个字母对应一个bit向量 B[a] = 所有 a 在 p 中出现的位置置1,否则置0 若 pi 为通配符,则所有 B 元素的第 I 位置置1 比特并行算法可实现字符集合匹配 |
第 82 页#
AC自动机对应的NFA 用bit对应自动机状态 状态转换 Shift-And不再适用 查表法 同时活跃状态在一条后缀链上 思考题: 如何通过word运算枚举每个活跃状态? |
第 83 页#
总结 比特并行模式匹配算法模拟了模式匹配NFA 模式长度不超过机器字长时性能较高 重点 AC多模式匹配 BM算法 bit并行算法 83 |