中科院计算所智能安全

《中科院计算所智能安全》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ReadingNotes中科院计算所智能安全曹京2006年11月28日AlgorithmstoAccelerateMultipleRegularExpressionsMatchingForDeepPacketInspection提纲文章内容介绍新的正则表达式表示方法--DelayedInputDFA（）基于的硬件体系结构--多嵌入式内存基于硬件体系结构的负载平衡算法作者及其实验室介绍一些个人想法文章主要内容使用技术算法--文中给出的自动机表示方式--负载平衡算法硬件--ASIC技术--多个有限容量的嵌入式内存实现结果表达式规模千规模的正则表达式扫描匹配速度OC-192（10Gbps）Delay

2、edInputDFA–背景正则表达式匹配需求深层次内容检测（NIDS/NIPS）第7层网关和防火墙基于内容流量管理现有系统SnortBro3Com’sTippingPpintCiscoSystem现有技术缺陷典型的正则表达式集合规模为：百级别字符集为256（ASCII）,平均出边为50多（？？）tensofthousandsofstatesHundredsofmegabytesTablecompressiontechniquesarenoteffectiveDelayedInputDFA–主要思路1算法思路增加一条Default边--Default边有方向--每个结点最多只能有一条Def

3、ault边--所有Default边不构成回路用时间换空间--对于输入字符，某结点没有对应出边时，则根据Default边到达下一结点。--循环往复，直至找到对应出边或到达没有Default边的结点。Default边构造方式如果结点u和v在某输入字符均到达点w，则可以增加一条u->v(orv->u)的default边。DelayedInputDFA–主要思路2举例说明DelayedInputDFA–主要思路3生成Default边算法构建一个无向带权图权重为两个结点中相同字符对应出边指向同一结点的边数减1问题转化成：最大权生成树问题。DelayedInputDFA–主要思路4主要问题生成的最大权生成

4、树其DefaultPath不是最短的。DefaultPath最短为1（图1所示），生成树则为2（下图所示）。限长最大权生成树问题是NP-Hard问题。DelayedInputDFA–主要思路5解决思路采用Kruskal生成树算法思想启发式的获得相对较好的生成树在最大权和最短树高之间做平衡得到的可能会是个森林（多棵树）具体方法初始阶段：每个结点都是一棵树权重从255->1递减判断选择边边{u，v}被选中条件--u和v不属于同一棵树--加入该边不会使树直径超过预定值DelayedInputDFA–实验部分1测试集DelayedInputDFA–实验部分2实验结果根据试验结果，将表达式分组将会进一步

5、减少空间92MBfor9partitionsoftheCiscoruls1+GBwithoutcleverrulepartitioning文中没有给出如何分组硬件体系结构RegexSystemArchitectureFPGA来作为存储部件：XilinxVirtex-4--几百个18Kbit的内存块组成几兆的内存单元--使用多个内存单元300MHz的时钟频率负载平衡内存单元数目不能使用太多内存单元数目跟时钟频率成反比需要分配有限的资源问题描述m个内存模块，p个并发扫描器建立模型--p个小球放在m个箱子里的问题--其中每个箱子只允许最多放1个球RandomizedMappingm个球随机放平均内存

6、利用率：65%RandomizedMapping性能测试MITDARPAIntrusionDetectionDataSets插入1%的匹配数据正则表达式测试集（文中没说明）最好情况比较差DeterministicandRobustMapping主要目标同时执行的自动机应当位于不同的内存模块中--避免内存冲突--可以通过使内存数目大于自动机个数来解决defaultpath中的状态结点应当位于不同的内存模块中--避免defaultpath中所有状态位于一个内存模块中--需要通过一定算法来解决的目标问题形式化问题可以形式化成graphcoloringproblem颜色代表内存模块，defaultpa

7、th代表图问题转化成：将图中的结点涂颜色，使得每条从叶子到根结点的路径都涂上不同的颜色max-minalgorithm–-介绍具体算法使用三个堆：树堆、层次堆、颜色堆每次选树堆中结点对多的一棵树对数构建层次堆（层数：每层的节点数）--选择颜色堆中颜色使用数目的最多的颜色--分给层次堆中最少层的所有该层结点--更新颜色堆中该分配颜色的使用数目--直至所有层均分配颜色直至所有树均分配到颜色即：每次选择