《13计算机安全_521》由会员分享，可在线阅读，更多相关《13计算机安全_521（59页珍藏版）》请在金锄头文库上搜索。
1、2018/9/5,1,安全、网络中的数据结构&算法,病毒扫描、入侵检测、搜索引擎、字典 重要算法之一：模式匹配算法/数据结构 单模式 kmp bm Sunday 多模式 AC WM 正则表达式 Sigcom Infocom AC自动机（TRIE）、后缀树、后缀自动机、后缀数组、紧凑(succinct)数据结构,2018/9/5,2,模式匹配算法,Brute Force算法 Knuth-Morris-Pratt (KMP) 算法 AC算法Boyer-Moore算法 使用DAWG的算法 Bit并行算法,2018/9/5,3,蛮力算法Brute Force,模式P 长度为m 文本T 长度为n P在T
2、的位置x处 出现： T = bacbabababacbbP = ababa x=4ababa x=6 找到P在T中的出现的最直接的方法: 在T的所有位置上检查P的出现 运行时间: 最坏情况 O(nm),2018/9/5,4,Brute Force,对一个位置的匹配中已经获得了对于文本的”知识” 例如：,P能出现在x+1, x+2么？,2018/9/5,5,Brute Force,对一个位置的匹配中已经获得了对于文本的”知识” 例如：,P能出现在x+1, x+2, x+3么？,2018/9/5,6,观察,假设 P 在Tx 处匹配了 k 个字符 P0k-1 = Txx+k-1, 对于 0r= 向左
3、移动的次数 向右的移动次数 = 对文本扫描的次数=n O(n) Fail构造复杂度 向右的移动次数 = 向左移动的次数 向右的移动次数 = 对模式扫描的次数=m O(m) O(m+n),2018/9/5,15,课后练习,完全用数组实现前边的自动机结构。,2018/9/5,16,Aho Corasick,原始 Aho Corasick 包括 Goto Function Failure Function Combining the two KMP的多模式扩展,2018/9/5,17,多模式匹配问题,Find patterns in text P=p1, p2, . pq, in T Aho and
4、 Corasick solved it in 75 Uses a state machine,2018/9/5,18,Aho Corasick 例,P = her, iris, he, is,2018/9/5,19,Aho Corasick -例,P = her, iris, he, is,如果失配，沿着失败链接回跳,Goto函数对应着模式的trie，,2018/9/5,20,Aho Corasick -例,h,i,he,ir,is,her,iri,iris,P = her, iris, he, is,如果失配，沿着失败链接回跳,GOto函数对应着模式的trie，,发现 模式 报告,2018/
5、9/5,21,Aho Corasick,Goto function: a trie of the patterns Failure function: 对于每个前缀, 其后缀中最长的是前缀对应的状态 KMP的失败函数的多模式推广 Output function: 报告每个前缀的后缀中匹配的模式,2018/9/5,22,Aho Corasick 分析,构造算法时间复杂 O(|P|) 搜索时间复杂 O(n + occ) . 在固定字母表上! 对于整数字母表, =O(nc), 用平衡树等结构,2018/9/5,23,状态转换函数,引入状态，状态转换简化为： Update_State(s,a) whi
6、le(GoTo(s,a)=fail) s=fail(s);return GoTo(s,a); 搜索时间复杂 O(n + occ),2018/9/5,24,Failure函数的构造,按照节点的深度分层 按层递增填写Failure函数,2018/9/5,25,模式匹配自动机,模式匹配自动机 取消失败函数 失败链接 边 （s， a， Update_State(s,a) ） 全部字母都对应跳转边,2018/9/5,26,入侵检测系统结构,事件产生器（Event generater， E-box）收集入侵检测事件,并提供给IDS其他部件处理，是IDS的信息源。事件包含的范围很广泛，既可以是网络活动也可是
7、系统调用序列等系统信息。事件的质量、数量与种类对IDS性能的影响极大。 事件分析器（Analysis engine, A-box）对输入的事件进行分析并检测入侵。许多IDS的研究都集中于如何提高事件分析器的能力,包括提高对已知入侵识别的准确性以及提高发现未知入侵的几率等。 事件数据库（Event database, D-box）E-boxes 和 A-boxes 产生大量的数据，这些数据必须被妥善地存储，以备将来使用。D-box的功能就是存储和管理这些数据,用于IDS的训练和证据保存。 事件响应器（Response unit, C-box）对入侵做出响应，包括向管理员发出警告，切断入侵连接，根
8、除入侵者留下的后门以及数据恢复等。,2018/9/5,27,简单分类,检测方法 特征(signature)检测(误用(misuse)检测) 状态模型 专家系统 字符串匹配、正则表达式匹配 异常检测 统计 机器学习方法：神经网络、数据挖掘 混合检测 数据源 基于主机 基于网络,2018/9/5,28,IDS的技术,异常检测(anomaly detection) 也称为基于行为的检测 首先建立起用户的正常使用模式，即知识库 标识出不符合正常模式的行为活动误用检测(misuse detection) 也称为基于特征的检测 建立起已知攻击的知识库 判别当前行为活动是否符合已知的攻击模式,2018/9/
9、5,29,IDS的评价,入侵检测覆盖范围 误报率和漏报率 自身抗攻击的能力 处理高速网络流量的能力 协同事件的能力 检测新攻击的能力,2018/9/5,30,入侵防御系统 (Intrusion Prevention System),入侵防御 入侵检测防火墙+ 集成多各种安全防护手段 特点 类似入侵检测系统 部署方式的差别：线内(in-line)和实时(real-time) 本身可能被拒绝服务攻击，造成整个网络的拒绝服务 IDS的另一个新名字：深度包检测(DPI),2018/9/5,31,IDS和IPS部署方式的区别,2018/9/5,32,网络IDS: snort,基于模式匹配的网络IDS 源
10、码开放，跨平台(C语言编写，可移植性好) 利用libpcap作为捕获数据包的工具 特点 设计原则：性能、简单、灵活 包含三个子系统：网络包的解析器、检测引擎、日志和报警子系统 内置了一套插件子系统，作为系统扩展的手段 模式特征链规则链 命令行方式运行，也可以用作一个sniffer工具,2018/9/5,33,网络数据包解析,结合网络协议栈的结构来设计 Snort支持链路层和TCP/IP的协议定义 每一层协议栈都对应一个处理函数 按照协议层次的顺序依次调用就可以得到各个层上的数据包头 从链路层，到传输层，直到应用层 支持链路层：以太网、令牌网、FDDI,2018/9/5,34,snort的规则,
11、Snort的规则从简单到复杂，超过40个规则选项！ alert tcp any any - 192.168.1.0/24 111 (content:“|00 01 86 a5|“; msg: “mountd access“;) 规则结构： 规则头： alert tcp any any - 192.168.1.0/24 111 规则选项： (content:“|00 01 86 a5|“; msg: “mountd access“;) 针对已经发现的攻击类型，都可以编写出适当的规则来 规则与性能的关系 选项检测的先后的顺序 Content option 许多cgi攻击和缓冲区溢出攻击都需要con
12、tent option,2018/9/5,35,在Snort的检测引擎中规则被解析为决策树结构,2018/9/5,36,针对IDS的拒绝服务类攻击 超载攻击 当网络流量超过IDS的处理能力时，IDS的处理能力将急剧下降甚至完全瘫痪。攻击者通过某些手段使网络流量达到饱和，迫使IDS大量丢包。这种攻击还可针对目标IDS系统采用的检测算法进行算法攻击。 资源耗尽攻击 通过发送大量残缺TCP数据段以及IP分片耗尽IDS的存储资源，使IDS不能正常工作。,2018/9/5,37,IPS/IDS,性能问题 10Gbit以太网、G比特光纤网 在处理高速流量时，速度和存储占用无法满足应用的需要 协议分析。协议
13、分析可以显著地缩小检测模式范围，从而减少内容检查，提高了入侵检测的效率。 内容检查。这是目前大多数网络入侵检测系统最重要的检测手段，内容模式取自攻击数据包的字符串特征。一般在协议分析之后对包内容进行特征串匹配，但相反的顺序可能提高检测效率 内容检查占全部处理时间的1/3,2018/9/5,38,提高IDS的性能,多机并行 流量的分割 处理的分割 单机性能 更好的算法 多模式匹配/多正则表达式匹配 硬件 FPGA（Field Programmable Gate-Array ） GPU，SIMD 多核处理器,2018/9/5,39,模式匹配算法在snort中的使用,采用多模式匹配算法提高入侵模式检测性能； 降低IP分片重组与TCP流重组的存储占用量。2001年前：BM算法 2001年snort引入多模式匹配算法 AC算法和BM算法的混合 Snort现在支持perl的标准正则表达式 主要仍用多模式匹配算法 串行正则表达式匹配,
