中科院计算所智能安全

ReadingNotes中科院计算所智能安全曹京2006年11月28日AlgorithmstoAccelerateMultipleRegularExpressionsMatchingForDeepPacketInspection提纲文章内容介绍新的正则表达式表示方法--DelayedInputDFA（）基于的硬件体系结构--多嵌入式内存基于硬件体系结构的负载平衡算法作者及其实验室介绍一些个人想法2DFA2DFA文章主要内容使用技术算法--文中给出的自动机表示方式--负载平衡算法硬件--ASIC技术--多个有限容量的嵌入式内存实现结果表达式规模千规模的正则表达式扫描匹配速度OC-192（10Gbps）2DFADelayedInputDFA–背景正则表达式匹配需求深层次内容检测（NIDS/NIPS）第7层网关和防火墙基于内容流量管理现有系统SnortBro3Com’sTippingPpintCiscoSystem现有技术缺陷典型的正则表达式集合规模为：百级别字符集为256（ASCII）,平均出边为50多（？？）tensofthousandsofstatesHundredsofmegabytesTablecompressiontechniquesarenoteffectiveDelayedInputDFA–主要思路1算法思路增加一条Default边--Default边有方向--每个结点最多只能有一条Default边--所有Default边不构成回路用时间换空间--对于输入字符，某结点没有对应出边时，则根据Default边到达下一结点。--循环往复，直至找到对应出边或到达没有Default边的结点。Default边构造方式如果结点u和v在某输入字符均到达点w，则可以增加一条u-v(orv-u)的default边。uvwaauvwaDelayedInputDFA–主要思路2•举例说明DelayedInputDFA–主要思路3•生成Default边算法构建一个无向带权图权重为两个结点中相同字符对应出边指向同一结点的边数减1问题转化成：最大权生成树问题。DelayedInputDFA–主要思路4主要问题生成的最大权生成树其DefaultPath不是最短的。DefaultPath最短为1（图1所示），生成树则为2（下图所示）。限长最大权生成树问题是NP-Hard问题。DelayedInputDFA–主要思路5解决思路采用Kruskal生成树算法思想启发式的获得相对较好的生成树在最大权和最短树高之间做平衡得到的可能会是个森林（多棵树）具体方法初始阶段：每个结点都是一棵树权重从255-1递减判断选择边边{u，v}被选中条件--u和v不属于同一棵树--加入该边不会使树直径超过预定值DelayedInputDFA–实验部分1•测试集DelayedInputDFA–实验部分2•实验结果•根据试验结果，将表达式分组将会进一步减少空间92MBfor9partitionsoftheCiscoruls1+GBwithoutcleverrulepartitioning文中没有给出如何分组硬件体系结构RegexSystemArchitectureFPGA来作为存储部件：XilinxVirtex-4--几百个18Kbit的内存块组成几兆的内存单元--使用多个内存单元300MHz的时钟频率负载平衡内存单元数目不能使用太多内存单元数目跟时钟频率成反比需要分配有限的资源问题描述m个内存模块，p个并发扫描器建立模型--p个小球放在m个箱子里的问题--其中每个箱子只允许最多放1个球RandomizedMappingm个球随机放平均内存利用率：65%RandomizedMapping•性能测试MITDARPAIntrusionDetectionDataSets插入1%的匹配数据正则表达式测试集（文中没说明）最好情况比较差DeterministicandRobustMapping主要目标同时执行的自动机应当位于不同的内存模块中--避免内存冲突--可以通过使内存数目大于自动机个数来解决defaultpath中的状态结点应当位于不同的内存模块中--避免defaultpath中所有状态位于一个内存模块中--需要通过一定算法来解决的目标问题形式化问题可以形式化成graphcoloringproblem颜色代表内存模块，defaultpath代表图问题转化成：将图中的结点涂颜色，使得每条从叶子到根结点的路径都涂上不同的颜色max-minalgorithm–-介绍•具体算法使用三个堆：树堆、层次堆、颜色堆每次选树堆中结点对多的一棵树对数构建层次堆（层数：每层的节点数）--选择颜色堆中颜色使用数目的最多的颜色--分给层次堆中最少层的所有该层结点--更新颜色堆中该分配颜色的使用数目--直至所有层均分配颜色直至所有树均分配到颜色即：每次选择树堆中最大的树，在该树中选层次堆中结点最少的一层，配颜色堆中最多使用的颜色max-minalgorithm--示例缺陷导致颜色不均匀（下图所示）Adaptivecoloringalgorithm主要思路max-min算法没有考虑当结点可以涂多种颜色选择哪种颜色的情况主要思想对每个结点赋予全部的颜色集合当结点赋予某个颜色时，将其它颜色去除（仅余一种颜色）使用两个变量used--每种颜色使用的次数deproved--不能使用这种颜色的节点个数，当某一结点选定某一颜色，则其子结点均不能使用该颜色选择最长深度的节点根据其默认路径逐一将路径上的点涂颜色--颜色选used中最小的并且deprived中最大的更新used和deproved变量。直至全部路径都涂完颜色。Adaptivecoloringalgorithm—示例实验结果实验数据测试数据同随机测试实验结果最好情况已较好小结提出新自动机表示方法用时间来换空间平均减少95%的transition•正则表达式集合分组进一步减少空间，利用并行体系结构来计算因此对于Cisco系统，只需2MB的嵌入式内存可以在300MHz的主频上处理10Gbps的吞吐率•实现确定性性能监控程序•使该体系结构上在OC192的速度上处理千规模的正则表达式匹配作者及其实验室介绍1•Author:SaileshKumar,SarangDharmapurikar,FangYu,PatrickCrowley,JonathanTurner--除了FangYu之外其它都在华盛顿大学计算机科学和工程系ARL实验室(AppliedResearchLaboratory)--SaileshKumar,SarangDharmapurikar是学生--PatrickCrowley,JonathanTurner是指导老师--FangYu是Berkeley计算机科学系博士生（原则上已毕业）作者及其实验室介绍2•SaileshKumar(~sailesh/)--ARL的博士生，印度人，--以前在PaxonetCommunications公司做了三年高级ASIC设计师•研究领域主要包括aroundallaspectsofNetworkprocessorarchitecturesandhighspeedrouterarchitectures作者及其实验室介绍3•SarangDharmapurikar(~sarang/)--ARL的博士生，印度人--以前在WiproGlobalR&D做过VLSI/Systems设计师•主要研究领域是：algorithmsandarchitecturesformulti-gigabitnetworkingsystems。具体为：--Routelookupalgorithms--Packetclassificationalgorithms--PatternmatchingalgorithmsforNetworkIntrusionDetection/PreventionSystems--High-speedTCPStreamProcessing作者及其实验室介绍4•PatrickCrowley(~pcrowley/)--ARL的助理教授。跟人合作写了三卷NetworkProcessorDesign•目前他的研究主要是：A)designingmulticoreprocessorsandmemorysystemsB)buildingfast,programmablenetworkrouterswithmulticoreprocessorsC)buildingnovelnetworksthatusefast,programmablenetworkrouters作者及其实验室介绍5•JonathanTurner(~jst/)ARL的老大。•研究领域--designandanalysisofhighperformanceroutersandswitchingsystems,--extensiblecommunicationnetworksandanalysisofalgorithms。作者及其实验室介绍6•FangYu(~fyu/)--Berkeley计算机科学系博士生（可能毕业了），本科复旦毕业的--做过Oasis项目(OverlaysandActiveServicesforInternetworkedStorage)。•研究领域是：Multi-matchpacketclassificationDeeppacketpatternmatchingwithTCAMFastRegularExpressionMatching作者及其实验室介绍7•ARL实验室()建立于1988年。主要关注高性能网络和网络应用。在硬件上作了非常多的工作。一些想法•国外硬件这一块很强，领先国内很多•可以跟着这篇文章做些算法方面的改进•硬件设计可以参考一下这篇文章的设计•对原先认为难得字符串领域重新作一下研究谢谢！！