中科院计算所智能安全课件.pptx

《中科院计算所智能安全课件.pptx》由会员分享，可在线阅读，更多相关《中科院计算所智能安全课件.pptx（31页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Reading Notes 中科院计算所智能安全 2006年11月28日Algorithms to Accelerate Multiple Regular Expressions Matching For Deep Packet Inspection提纲l文章内容介绍新的正则表达式表示方法 -Delayed Input DFA（）基于 的硬件体系结构 -多嵌入式内存基于硬件体系结构的负载平衡算法l作者及其实验室介绍l一些个人想法文章主要内容l使用技术算法 -文中给出的 自动机表示方式 -负载平衡算法硬件 -ASIC技术 -多个有限容量的嵌入式内存实现结果 表达式规模 千规模的正则表达式千规模的

2、正则表达式 扫描匹配速度 OC-192（10Gbps）Delayed Input DFA 背景 l正则表达式匹配需求 深层次内容检测（NIDS/NIPS）第7层网关和防火墙 基于内容流量管理l现有系统 Snort Bro 3Coms TippingPpint Cisco Systeml现有技术缺陷 典型的正则表达式集合规模为：百级别 字符集为256（ASCII）,平均出边为50多（？）tens of thousands of states Hundreds of megabytes Table compression techniques are not effectiveDelayed In

3、put DFA 主要思路1l算法思路增加一条Default边-Default边有方向-每个结点最多只能有一条Default边-所有Default边不构成回路用时间换空间-对于输入字符，某结点没有对应出边时，则根据Default边到达下一结点。-循环往复，直至找到对应出边或到达没有Default边的结点。lDefault边构造方式如果结点u和v在某输入字符均到达点w，则可以增加一条u-v(or v-u)的default边。Delayed Input DFA 主要思路2举例说明Delayed Input DFA 主要思路3生成Default边算法 构建一个无向带权图权重为两个结点中相同字符对应出边

4、指向同一结点的边数减1 问题转化成：最大权生成树问题。问题转化成：最大权生成树问题。Delayed Input DFA 主要思路4l主要问题 生成的最大权生成树其Default Path不是最短的。Default Path最短为1（图1所示），生成树则为2（下图所示）。限长最大权生成树问题是NP-Hard问题问题。Delayed Input DFA 主要思路5l解决思路采用Kruskal生成树算法思想启发式的获得相对较好的生成树在最大权和最短树高之间做平衡得到的可能会是个森林（多棵树）l具体方法初始阶段：每个结点都是一棵树权重从 255-1 递减判断选择边边u，v被选中条件 -u和v不属于同一

5、棵树 -加入该边不会使树直径超过预定值Delayed Input DFA 实验部分1测试集Delayed Input DFA 实验部分2实验结果根据试验结果，将表达式分组将会进一步减少空间 92MB for 9 partitions of the Cisco ruls 1+GB without clever rule partitioning 文中没有给出如何分组文中没有给出如何分组硬件体系结构lRegex System Architecture FPGA来作为存储部件：Xilinx Virtex-4 -几百个18Kbit的内存块组成几兆的内存单元 -使用多个内存单元300MHz的时钟频率 负

6、载平衡l内存单元数目不能使用太多内存单元数目跟时钟频率成反比需要分配有限的资源l问题描述 m个内存模块，p个并发扫描器 建立模型 -p个小球放在m个箱子里的问题 -其中每个箱子只允许最多放1个球 lRandomized Mapping m个球随机放平均内存利用率：65%Randomized Mapping性能测试MIT DARPA Intrusion Detection Data Sets插入1%的匹配数据正则表达式测试集（文中没说明）最好情况最好情况比较差比较差Deterministic and Robust Mapping l主要目标 同时执行的自动机应当位于不同的内存模块中 -避免内存冲

7、突 -可以通过使内存数目大于自动机个数来解决可以通过使内存数目大于自动机个数来解决 default path中的状态结点应当位于不同的内存模块中 -避免default path中所有状态位于一个内存模块中 -需要通过一定算法来解决的目标需要通过一定算法来解决的目标问题形式化问题可以形式化成形式化成graph coloring problem 颜色代表内存模块，default path代表图 问题转化成：将图中的结点涂颜色，使得每条从叶子到根结点的路问题转化成：将图中的结点涂颜色，使得每条从叶子到根结点的路 径都涂上不同的颜色径都涂上不同的颜色 max-min algorithm-介绍 具体算法

8、 使用三个堆：树堆、层次堆、颜色堆 每次选树堆中结点对多的一棵树 对数构建层次堆（层数：每层的节点数）-选择颜色堆中颜色使用数目的最多的颜色-分给层次堆中最少层的所有该层结点-更新颜色堆中该分配颜色的使用数目-直至所有层均分配颜色直至所有树均分配到颜色即：每次选择树堆中最大的树，在该树中选层次堆中结点最少的一即：每次选择树堆中最大的树，在该树中选层次堆中结点最少的一 层，配颜色堆中最多使用的颜色层，配颜色堆中最多使用的颜色 max-min algorithm-示例l缺陷 导致颜色不均匀（下图所示）Adaptive coloring algorithm l主要思路max-min算法没有考虑当结点

9、可以涂多种颜色选择哪种颜色的情况 主要思想对每个结点赋予全部的颜色集合 当结点赋予某个颜色时，将其它颜色去除（仅余一种颜色）使用两个变量 used-每种颜色使用的次数 deproved-不能使用这种颜色的节点个数，当某一结点选定某一颜色，则其子结点均不能使用该颜色选择最长深度的节点根据其默认路径逐一将路径上的点涂颜色 -颜色选used中最小的并且deprived中最大的更新used和deproved变量。直至全部路径都涂完颜色。Adaptive coloring algorithm示例实验结果 l实验数据测试数据同随机测试l实验结果最好情况最好情况已较好已较好小结l 提出新自动机表示方法 用时

10、间来换空间平均减少95%的transition正则表达式集合分组进一步减少空间，利用并行体系结构来计算因此对于Cisco系统，只需2MB的嵌入式内存可以在300MHz的主频上处理10Gbps的吞吐率实现确定性性能监控程序使 该体系结构上在OC192的速度上处理千规模的正则表达式匹配作者及其实验室介绍1Author:Sailesh Kumar,Sarang Dharmapurikar,Fang Yu,Patrick Crowley,Jonathan Turner -除了Fang Yu之外其它都在华盛顿大学计算机科学和工程系ARL实 验室(Applied Research Laboratory)-

11、Sailesh Kumar,Sarang Dharmapurikar是学生 -Patrick Crowley,Jonathan Turner是指导老师 -Fang Yu是Berkeley计算机科学系博士生（原则上已毕业）作者及其实验室介绍2Sailesh Kumar()-ARL的博士生，印度人，-以前在Paxonet Communications公司做了三年高级ASIC设计师 研究领域主要包括around all aspects of Network processor architectures and high speed router architectures作者及其实验室介绍3Sar

12、ang Dharmapurikar()-ARL的博士生，印度人 -以前在Wipro Global R&D做过VLSI/Systems设计师主要研究领域是：algorithms and architectures for multi-gigabit networking systems。具体为：-Route lookup algorithms -Packet classification algorithms -Pattern matching algorithms for Network Intrusion Detection/Prevention Systems -High-speed TC

13、P Stream Processing 作者及其实验室介绍4Patrick Crowley()-ARL的助理教授。跟人合作写了三卷Network Processor Design目前他的研究主要是：A)designing multicore processors and memory systems B)building fast,programmable network routers with multicore processors C)building novel networks that use fast,programmable network routers作者及其实验室介绍5

14、Jonathan Turner()ARL的老大。研究领域 -design and analysis of high performance routers and switching systems,-extensible communication networks and analysis of algorithms。作者及其实验室介绍6Fang Yu()-Berkeley计算机科学系博士生（可能毕业了），本科复旦毕业的 -做过Oasis项目(Overlays and Active Services for Internetworked Storage)。研究领域是：Multi-match

15、 packet classification Deep packet pattern matching with TCAM Fast Regular Expression Matching作者及其实验室介绍7ARL实验室()建立于1988年。主要关注高性能网络和网络应用。在硬件上作了非常多的工作。一些想法国外硬件这一块很强，领先国内很多可以跟着这篇文章做些算法方面的改进硬件设计可以参考一下这篇文章的设计对原先认为难得字符串领域重新作一下研究 谢谢！1、有时候读书是一种巧妙地避开思考的方法。3月-233月-23Monday,March 6,20232、阅读一切好书如同和过去最杰出的人谈话。14:

16、08:4114:08:4114:083/6/2023 2:08:41 PM3、越是没有本领的就越加自命不凡。3月-2314:08:4114:08Mar-2306-Mar-234、越是无能的人，越喜欢挑剔别人的错儿。14:08:4114:08:4114:08Monday,March 6,20235、知人者智，自知者明。胜人者有力，自胜者强。3月-233月-2314:08:4114:08:41March 6,20236、意志坚强的人能把世界放在手中像泥块一样任意揉捏。06三月20232:08:41下午14:08:413月-237、最具挑战性的挑战莫过于提升自我。三月232:08下午3月-2314:

17、08March 6,20238、业余生活要有意义，不要越轨。2023/3/614:08:4114:08:4106 March 20239、一个人即使已登上顶峰，也仍要自强不息。2:08:41下午2:08下午14:08:413月-2310、你要做多大的事情，就该承受多大的压力。3/6/2023 2:08:41 PM14:08:4106-3月-2311、自己要先看得起自己，别人才会看得起你。3/6/2023 2:08 PM3/6/2023 2:08 PM3月-233月-2312、这一秒不放弃，下一秒就会有希望。06-Mar-2306 March 20233月-2313、无论才能知识多么卓著，如果缺乏热情，则无异纸上画饼充饥，无补于事。Monday,March 6,202306-Mar-233月-2314、我只是自己不放过自己而已，现在我不会再逼自己眷恋了。3月-2314:08:4106 March 202314:08谢谢大家谢谢大家