基于netfpga的网络流量分类技术研究和实现

《基于netfpga的网络流量分类技术研究和实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

西南科技大学硕士研究生学位论文第I页基于NetFPGA的网络流量分类技术研究和实现2011邓悄硕士通信与信息系统周金治副教授 西南科技大学硕士研究生学位论文第II页ClassifiedIndex:TP393U.D.C:621.39SouthwestUniversityofScienceandTechnologyMasterDegreeThesisResearchandimplementationofnetworktrafficclassificationtechnologybasedonNetFPGAGrade:2011Candidate:DengQiaoAcademicDegreeAppliedfor:MasterSpeciality:CommunicationandInformationSystemSupervisor:ZhouJinzhiDec12,2014 西南科技大学硕士研究生学位论文第III页独创性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得西南科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。签名：日期：关于论文使用和授权的说明本人完全了解西南科技大学有关保留、使用学位论文的规定，即：学校有权保留学位论文的复印件，允许该论文被查阅和借阅；学校可以公布该论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。(保密的学位论文在解密后应遵守此规定)签名：导师签名：日期： 西南科技大学硕士研究生学位论文第IV页摘要随着互联网的发展，越来越多的新型应用应运而生，在方便人们使用时，也使得带宽资源分配不合理；同时互联网的开放性使得各种垃圾应用与病毒对网络环境造成威胁。为了解决这些问题，需要对网络进行有效的监督和管理，增强网络可控性，保障网络安全与服务质量。而网络流量分类技术作为带宽管理、信息安全、内容审计等方面的关键技术之一，可以帮助研究人员了解网络流量分布、允许网络运营商优先传输重要数据、识别计算机病毒、预防并阻止网络犯罪行为的发生。因此，网络流量分类技术已成为研究热点。本文采用斯坦福大学开发的NetFPGA平台，运用软硬结合的方式，在网卡端实现基于深度包检测的流量分类技术，以解决当前分类技术速度慢、低吞吐率的问题。根据正则表达式匹配原理，首先分析多个表达式之间相关性，设定重组膨胀率与组合状态数上限，消除冗余状态数，完成了多个表达式的重组工作；针对表达式自身结构，设定状态数增长率参数，完成了表达式结构优化工作，解决歧义匹配；分析三种扫描算法的优缺点,结合One-Pass扫描算法，实现了报文匹配方式的改进。其次分析Wireshark抓取的数据包信息与L7-fliter特征库，总结典型应用的特性并通过正则表达式进行描述，提供特征集。最后根据NetFPGA特点，在数据通道的输入仲裁模块与输出端口查询模块间插入了自定义分类架构，实现网络报文的应用层信息提取，并根据维护在SRAM中的正则表达式状态转移表，实现了应用层协议特征的匹配与标识，达到高速分类的效果。实验结果表明，改进的正则表达式算法在DFA状态总数与匹配时间消耗上都达到一个合理的范围。基于NetFPGA实现的分类技术，在吞吐率方面远远高于现有软件实现的分类技术，协议匹配精度也较高。关键词：NetFPGA正则表达式确定性有限状态机深度包检测 西南科技大学硕士研究生学位论文第V页AbstractWiththedevelopmentofinternet,moreandmorenewapplicationsemerged,whenpeopleuseconveniently,itmakesthebandwidthresourceallocationisnotreasonable;uselessapplicationandvirusposesathreattotheenvironmentofthenetwork.Inordertosolvetheseproblems,networkneedeffectivesupervisionandmanagementtoenhancethecontrollability,safetyandthequalityofservice.Asakeyofbandwidthmanagement,informationsecurity,contentaudit,thenetworktrafficclassificationcanhelpresearchersunderstandtheoccurrenceofnetworkflowdistribution,allowsthenetworkoperatorprioritytransmissionofimportantdata,identificationofvirus,preventandstopthenetworkcrime.Therefore,thenetworktrafficclassificationtechnologyhasbecomearesearchfocus.Inthispaper,weusesoftandhardcombinationwayrealizationofflowclassificationtechnologybasedondeeppacketinspectioninthenetworkcardbaseonNetFPGA，inordertosolvethecurrentclassificationtechnologyproblemwhichslowlyandlowthroughput.Accordingtotheregularexpressionmatchingprinciple,firstweanaltsisthecorrelationbetweenmultipleexpression,setofrecombinantexpansionrateandcombinedstatenumberlimit,eliminateredundantstate,recombinantexpression;accordingtotheexpressionstructure,setthenumberofstateparametersofgrowthrate,completedtheexpressionstructureoptimizationwork,resolvetheambiguitymatching;analysistheadvantagesanddisadvantagesofthreescanningalgorithm,implementedtheimprovedpacketmatchingmethodwiththeOne-Passscanalgorithm.Secondly,summarizethecharacteristicsoftypicalapplications,throughWiresharkandL7-fliterandgotthefeatureset.Finally,accordingtothecharacteristicsofNetFPGA,insertclassificationframeworkbetweentheinputarbitrationmoduleandoutputportquerymodule,implementedofapplicationlayerinformationnetworkmessageextractionandfeaturematchingbaseonthestatetransitiontableintheSRAM.ExperimentalresultsshowthenumberofDFAstatesandmatchingtotaltimeconsumedhasreachedareasonablerange.BasedonNetFPGAachieveclassificationtechniques,intermsofthroughputismuchhigherthantheexistingclassificationsoftwaretechnologies,protocolsmatchingaccuracyishigher.Keywords:NetFPGA；Regularexpression；DFA；DPI 西南科技大学硕士研究生学位论文第VI页目录目录.....................................................VI1绪论.......................................................11.1研究背景和意义.......................................................................................11.2流量分类与NetFPGA国内外研究现状...................................................21.3研究内容...................................................................................................31.4论文组织结构.............................................................................................42NetFPGA开发平台与分类技术研究.............................52.1NetFPGA硬件开发平台分析....................................................................52.1.1NetFPGA开发板研究.........................................................................52.1.2NetFPGA参考模型.............................................................................72.2网络流量分类技术.................................................................................102.2.1流量分类不同粒度与评价指标........................................................102.2.2网络流量分类主流方法...................................................................112.2.3基于正则表达式的流量分类算法....................................................132.3本章小结.................................................................................................183基于正则表达式分类算法的研究..............................193.1正则表达式的模式匹配..........................................................................193.1.1构建DFA与NFA..............................................................................203.1.2DFA状态膨胀分析...........................................................................283.2设定动态参数.........................................................................................313.2.1状态数增长率参数Ex......................................................................313.2.2重组膨胀率相关参数η与Sc...........................................................333.3削弱状态膨胀数.....................................................................................35 西南科技大学硕士研究生学位论文第VII页1.1合并互斥性......................................................................................351.2切割膨胀片段..................................................................................362.1报文匹配方式研究.................................................................................382.2测试实验.................................................................................................402.1.1匹配方式选取..................................................................................402.1.2算法整体效果评估...........................................................................412.3本章小结.................................................................................................434NetFPGA流量分类器的实现..................................442.2.1NetFPGA数据通道设计.........................................................................442.2.2网络流量分类器整体框架......................................................................453.1分类器设计指标...............................................................................453.2整体框架设计..................................................................................462.2.3输入控制模块.........................................................................................472.2.4流管理模块.............................................................................................482.2.5报文管理模块与输出控制模块..............................................................512.2.6协议识别模块.........................................................................................523.1.1协议特征提取..................................................................................523.1.2协议匹配..........................................................................................542.2.7本章小结.................................................................................................585效果评估与分析............................................593.2.1实验平台搭建.........................................................................................593.2.2吞吐率测试.............................................................................................603.2.3精确率测试.............................................................................................603.2.4本章小结.................................................................................................62 西南科技大学硕士研究生学位论文第VIII页结论.....................................................63致谢.....................................................64参考文献.....................................................65攻读学位期间发表的相关学术论文及研究成果.....................69 西南科技大学硕士研究生学位论文第1页1绪论1.1研究背景和意义互联网凭借其共享性与开放性得到迅速的发展，为网络应用提供高速增长环境的同时，也使得网络管理越来越困难。网络流量分类技术能够帮组运营商更好的分配网络带宽资源，并对网络进行监控与维护，增强网络的可控性。根据2013年中国互联网网络安全报告显示[1]，2013年我国境内被篡改网站数目为24034个，相较于2012年增长46%，其中政府部门为重点攻击对象，被篡改的网站数为2430个，约占总数的10%；查处的非法钓鱼网站多达30199个，涉及到IP地址数为4240个，其中90.2%为境外IP；监测到境内76160个网站被植入后门，其中政府网站占3.2%；监测到被木马或者僵尸程序控制的服务器数为189369个，境内被控制的服务器IP数为160228个；2013年全球互联网约有1723万主机IP感染“飞客”蠕虫，境内感染IP数超过了175万个；基础电信企业通报漏洞风险事件518起，较2012年增长超过一倍，其中通用软硬件、信息泄露、权限绕过、SQL注入、弱口令等类型较多，分别占42.1%、15.3%、12.7%、12.0%和11.2%。这些漏洞风险事件涉及的信息系统达449个，其中基础电信企业省（子）公司所属信息系统占2.1%，集团公司所属信息系统占37.2%。由此可见，我国基础网络整体防御能力较为薄弱，在面对高速发展的网络环境时，网络管理技术需要更进一步的提升，网络流量分类技术作为其关键技术之一，势必成为学术界的研究热点。把握网络中业务种类和其所占的比例情况，一方面有助带宽管理，为主流应用合理分配带宽，可以明显的提高用户体验；另一方面，安全设备厂商，可以根据具体业务类型，提供更具针对性的安全检测设备，解决与各种网络应用密切相关的安全问题。比如在建立基于网络QoS的付费制度中[2]，用户通过付费申请相应的QoS等级及签名；网络QoS的签名制为客户提供了一定的网络服务质量。由于网络流量分类在支持因特网QoS保证方面具有巨大的潜力，现有的具备服务质量保证的产品和有自动服务质量保证体系的结构上，实时的流量分类是一个核心组件[3]。在流量分类系统之上建立的入侵防御系统，能够轻松地完成对攻击流量识别与防范。入侵防御系统在对流量进行相应的处理之前，流量分类系统的预处理就识别出相应的流，这样防御系 西南科技大学硕士研究生学位论文第2页统就可以专心应付异常流量，而不需要对所有流量进行分析，提高了整体系统性能，节约了计算机资源。然而过去网络中，SMTP、FTP、HTTP等业务占据了网络流量绝大部分，传统基于端口的识别技术根据在IANA注册的正规端口来进行应用流量的识别[4]。比如，HTTP为80端口，FTP为21端口。从理论上讲，是可以通过端口的识别来进行所有现有流量的分类。然而随着P2P（PeertoPeer）、网络游戏、流媒体等新应用的出现，所占据的流量已经达到60%以上[5]，业务种类与私有协议也在不断的扩张，传统应用比例大幅下划，这样许多网络流不能通过传统的技术来进行对流量的分类。目前各种网络业务每年保持50%-300%的增长率，国际IP主干带宽每6-9个月翻一番，是摩尔定律的2-3倍。吉尔德定律中所描述的主干网增长速度比CPU的增长速度要快得多[6]。所以，带宽的增长速度远远高于CPU与内部处理性能的增长速度，只依靠纯软件的处理方式很难满足高速网络安全管理，因为软件在CPU上虽然可以乱码执行或者路径猜测等技术加快速度，但本质上也是顺序执行，报文传输的一段时间内只能执行有限的代码段，处理器、操作系统及内存的带宽都会对软件应用带来限制。综上所述，针对当前网络环境现状设计一款高效的流量分类系统是很有必要的。本文使用美国斯坦福大学开发的硬件平台—NetFPGA，设计实现了一种分类速度快、准确度高的网络流量分类系统，解决现有分类技术带来的分类瓶颈。1.1流量分类与NetFPGA国内外研究现状在国外，网络流量分类技术的应用体现在下面两点。一个是服务于网络QoS，二是针对入侵防御技术领域进行预处理。像美国的Packteer公司在2000年就推出了基于流量分类技术的网络Qos设备[7]。所采用的方法主要是基于端口的识别、基于特征码的识别以及基于BLINC的识别。现有的入侵防御领域中，很多都是基于流量的识别与应用协议分析，通过借助网络流量分类技术来提高网络不良行为的监控，规范网络行为。然而在国内关于网络流量分类的技术起步相对较晚，关于网络流量分类相关的专利在07年之后才出现，大多采用基于DPI（DeepPacketInspection）与DFI（DeepFlowInspiron），基于特征码识别和网络流量统计特征技术也在慢慢提高。 西南科技大学硕士研究生学位论文第3页流量分类技术现在主要分类为基于端口、统计特征与深度包检测三种方法。端口识别的流量分类技术在分类速度很快，原理相对简单且实现比较简易，但是在当前环境下很难保证其精度。统计特征的流量分类技术是根据对大量网络流量进行统计，掌握其特征，例如，流的到达时间，流的延时等信息。这种统计方法克服了加密报文无法通过深度包检测进行分类的缺点，并且精确性也较高，但是需要大量的训练集来完成特征收集。基于内容深度检测的流量分类方法克服了端口识别技术的缺点，保证了很高的识别度，且不需要大量的训练集，便于实现与拓展，备受学术界的关注。NetFPGA是美国斯坦福大学（StanfordUniversity）开发设计，它有4个GE级的网口，使用时插在PC机的PCI插槽内，内部拥有FPGA可编程硬件模块，可以实现用户自定义功能，为研究人员提供了一个低成本且可重构的网络平台。同时，因为NetFPGA可以很方便与它的主机通讯，所以在NetFPGA上实现软硬结合方式开发应用显得方便、快捷。它的主要使用人群包括了老师、学生和研发人员。所涉及到的项目包括了：网卡、路由器、OpenFlowSwitch、Netthread、URLExtraction等。国内在对NetFPGA平台进行研究还在初级阶段，但是NetFPGA的影响力正在加强。国防科学技术大学网络与信息安全研究所开发了一个类似的网络平台NetMagic[8]，接口更多，扩展性更强，使用更方便，功能更强大，目前这个平台正在推广中。与此同时，美国斯坦福大学也将NetFPGA进行了升级，推出了相较于1G的开发板在网络流量处理速度上就提升了10倍的NetFPGA10G[9]。1.1研究内容论文接下来介绍的内容如下:（1）通过对网络流量分类技术的研究，总结各种方法的优缺点，掌握分类技术的发展历程，以及网络流量分类技术未来的发展趋势。（2）研究应用层协议识别技术，并重点对基于正则表达式的协议识别技术进行研究。熟练掌握正则表达式的匹配原理，以及对现有的正则表达式算法进行总结，分析他们之间的性能差异。（3）归纳总结造成正则表达式状态数膨胀的原因，并通过参数的设定，严格控制多个表达式的重组与整体切片，降低确定性有限状态机DFA（DeterministicFiniteAutomaton）状态数，实现简化算法空间复杂度。在报文匹配方式上，通过实验对比单报文一次性匹配、多报文叠加匹配与多报文 西南科技大学硕士研究生学位论文第4页一次性匹配与One-Pass扫描算法结合的优缺点。最后对算法整体进行测试实验，验证其可行性。（4）针对NetFPGA开发平台，通过软硬结合的方式，在开发板上实现基于应用层识别的流量分类器，并搭建实验环境，对分类器进行测试，验证其性能表现。1.1论文组织结构第二章为NetFPGA平台及流量分类技术研究。首先对NetFPGA开发板整体进行分析，重点阐述用户数据通道（User_data_path）。然后对流量分类技术进行了系统的分析，对传统的几种分类方法进行了比较，总结他们的优缺点，并借此引出了基于正则表达式的协议层分类技术。第三章为算法实现。首先通过对正则表达式组合上限的控制与表达式本身结构的拆分，实现在状态数上的限制；接着在对匹配方法进行了研究，通过比对实验选择合适的匹配方法，最后通过与mDFA，DFA，D2FA，XFA对比，验证算法在时间复杂度与空间复杂度的优越性。第四章为基于NetFPGA的流量分类器实现。对分类框架整体设计过程进行讨论，并对各个模块的关键技术做了详细分析。第五章为实验结果展示与分析。针对分类技术的评价标准，对本文设计的分类器进行整体测试，对实验结果进行说明。最后为结束语。总结整个论文，展望NetFPGA和流量分类的前景。 西南科技大学硕士研究生学位论文第5页2NetFPGA开发平台与分类技术研究根据本文的主要研究目标，本章将对开发平台及相关技术进行研究。开发平台可以分为软件平台与硬件平台，本章只对NetFPGA开发板进行分析，并对网络流量分类技术进行系统的研究与总结。1.1NetFPGA硬件开发平台分析2.1NetFPGA开发板研究由美国斯坦福大学开发的NetFPGA是一个可重构、低成本的硬件平台。它的出现使研究人员可以反复组建多样化的网络原型和构造稳定的网络测试平台。NetFPGA硬件核心部分包括两个FPGA同步运行于125MHz时钟频率：一块Virtex-IIPro系列芯片。另外一块SpartanII系列的XC2S200-FG456C芯片。一个多端口10/100/1000Mb/s自适应的PHY芯片，在其内部集成4个千兆级电信号收发器。内存由2片字长36的SRAM和2片字长32的DRAM。工作频率分别是125MHz、200MHz。NetFPGA可以对现有网络系统进行全方位的测试与分析，而且能够组建新的网络系统，具备相当大的发展前景。网络面世至今对人类生活产生了巨大的影响，但是在网络发展方向上却没有尽头，不管是新的协议或者新的网络架构都需要一个非常合适的平台来对网络进行组建、测试，然而斯坦福大学推出的NetFPGA为解决这一个问题提供了很好平台，它内部具有FPGA（Field－ProgrammableGateArray）现场可编程门阵列的特性，实现了硬件编程，同时提供了模块化设计理念[10-12]，节省了大量的开发成本。开发板通过PCI-e接口与计算机相连，通过8个数据通道完成数据的接受与推送。图2-1[13-14]为NetFPGA结构图，其中1GEPHY即为4个千兆级网口。 西南科技大学硕士研究生学位论文第6页图2-1NetFPGA结构图Fig.2-1NetFPGAStructureNetFPGA的官方网站有许多开源项目作为初学者学习NetFPGA开发流程的案例，这里我们选择参考路由项目来完成对开发板原理的解释。我们将开发板定义为硬件转发层与用户交互界面，如图2-2所示[15-16]。图2-2逻辑框图Figure.2-2Logicalblockdiagram用户层面主要由架构管理模块和功能实现模块组成。架构管理模块主要包括：（1）NetFPGA平台的硬件开发、仿真与调试的CAD工具；（2）Monito用于管理主机Linux系统与开发板的连接工具，开发板与PC机数据的DMA传输，通过读取主机内存中寄存器与RAM地址实现开发板的配置过程。 西南科技大学硕士研究生学位论文第7页功能实现模块主要包括：（1）路由协议管理用于测试与验证开发板的路由功能，如实现OSPF[17]。（2）测试软件用于研究人员对实验结果收集与比对，如Counterdump用于读取硬件计数器然后储存到终端。(3)基于JavaGUI的用户操作界面，界面简洁、操作简单，可以根据用户自己的需求进行拓展。硬件转发层面：（1）Memory及相关电路用于外部存储与硬件功能实现，如两片DRAM和两片SRAM。4个千兆级的以太网MAC控制器用于完成所有网络数据的推送功能。PCI总线用于连接主机CPU与开发板间的数据传输。1.1NetFPGA参考模型参考模型是所有项目的扩展基础，下面我们需要对基础参考模型进行介绍，重点对User_data_path模块进行研究，分析模块之间的逻辑关系，图2-3为NetFPGA中参考模型[18]。User_data_path4个千兆级网口4个MAC控制器Input_arbiter自定义模块nf2_reg_grpOutput_port_lookupnf2_mdioOutput_queues时钟模块Reg_grpx2DMA队列nf2_dmacpcibusPCI接口用户主机驱动程序用户软件图2-3NetFPGA参考模型Figure.2-3NetFPGAReferenceModel4个mac控制器对应着4个千兆网口，负责完成外界网络数据的接收工作。数据通过网口进入User_data_path模块，经过用户处理之后推送到以太网接口，完成数据传输。对于NetFPGA来说MAC控制器是必须的，所以斯坦福大学为了减少用户开发周期，已经预先实现了MAC控制器功能，用户可以直接使用。主机通信DMA队列功能与MAC控制器类似，将待处理的 西南科技大学硕士研究生学位论文第8页数据传送到主机CPU或者接受来自主机的数据。PCI接口模块负责开发板与主机之间的联系及电源供应，该模块不需要用户额外设定，属于外围模块。整个模型的通信方式可以分为两种：一种是通过DMA传送的外来网络数据包，比如网卡向主机推送的数据；还有一种是寄存器数据传输，NetFPGA允许用户通过函数的调用完成应用程序与NetFPGA寄存器内容的交互，实时对硬件功能进行调整，设置参数等，比如路由器中路由表的设置就是通过此方法完成的。User_data_path模块对于每一个项目都是必不可少的，用户通过修改User_data_path模式来实现自己的功能。数据包在User_data_path里面的处理流程如下：MAC控制器接收到来自网络的数据包并将他们推送到缓存区，并由Input_arbiter模块负责对数据包进行输入控制，添加特定的数据包首部帧，再推送到下一个模块Output_port_lookup，该模块会根据数据包转发对数据包进行传送，并修改数据包首部帧，发送到Output_queues模块，该模块对应着8个MAC控制器，完成后续操作。图2-4为User_data_path中各个模块之间通信的4路信号，分别是64位data，8位ctrl，1位wr，一位rdy。网络数据包或者主机推送的数据包进入到NetFPGA后被放入缓存中，通过Input_arbiter模块对数据进行初始封装，自动添加NetFPGA的特定的头部帧，每一帧data数据含有64位，并在8位控制信号ctrl的协同下进行数据传输。控制信号ctrl具有两个作用：一是对数据包的第一帧和最后一帧进行识别，二是确定最后一帧数据的有效位，保证通信畅通。ctrl值为非零时，表示并行传输的data数据是第一帧与最后一帧之间的任意一个，ctrl值为零时表示同时传输的data数据是中间部分的帧。在ctrl值为非零时，且表示最后一帧数据时，它确定最后一帧数据中有效的字节数：8位ctrl有“10000000b，010000000b，…，00000001b”八种情况，分别对应data数据中有效字节数“1个字节有效，2个字节有效，…，8个字节有效”；比如当有5个有效字节存在于最后一帧的数据中时，则ctrl=00001000b。当ctrl值非零时，且表示第一帧数据时，至少有两个“1”，包含在ctrl中。这样就可以避免冲突；实际上，通常第一帧数据的ctrl都为11111111b=255。 西南科技大学硕士研究生学位论文第9页Data（63:0）模块iCtrl（7:0）wrrdy模块i+1图2-4模块间的通信信号Figure2-4Communicationsignalsbetweenmodules对于所有流进Input_arbiter模块数据通道的数据，该模块都会对其添加64位的头部，格式由图2-5给出。所添加的信息包括了目的端口、字长、源端口、字节长度信息等。数据帧的数目由16位字长指定，且这里的端口对应的是MAC控制器的缓存区。图2-5数据包格式Figure2-5PacketFormatUser_data_path模块包含的寄存器通信链路如图2-6所示。单向循环链路由Input_arbiter、Output_port_lookup和Output_queues三个子模块构成。该通信链路中，模块内部的寄存器都有唯一的地址，当一个请求信息抵达模块i时，模块i校验其地址判断是否处理该请求；假如需要处理，给出相应应答信号，并传输给下一个（i+1）模块；假如对请求不予处理，继续将该信号发送到i+1模块，i+1模块首先判断该消息中是否有应答信号；如果有，则说明i模块已经对此请求做了相应的处理，直接传递给i+2模块供后续操作；如果 西南科技大学硕士研究生学位论文第10页没有相应的应答信号，再进行之前阐述的地址判断与后续分析。用户通过软件调用驱动程序的寄存器读写函数来实现对寄存器的读写操作。RegisterbusPacketbus NetFPGA数据包数据包数据包主机主机网络接受队列发送队列网络InputArbiterOutputPortOutputQueue寄存器寄存器寄存器寄存器控制RegI/OoverPCI图2-6寄存器通信链路Figure2-6Registerscommunicationlink从前面对参考模型中User_data_path分析中我们知道，可以在其中添加自定义子模块，通过调用寄存器读写函数实现模块的读写操作，以实现特定功能。本文将在参考模型中实现对网络数据的提取与分析，达到分类的效果，所以本节主要对网络流量分类技术进行系统的总结与分析。针对不同粒度的分类及不同分类算法进行比较，详细研究他们的利弊。1.1网络流量分类技术2.1流量分类不同粒度与评价指标不同网络应用在网络中运行的环境不同，且具有自身的行为模式。同样对带宽需要也不同，运行的网络层当然也不同，就目前学术界研究现状而言，流量分类可以归结为下面三个层面[19]。（1）Packet_Level的分类级别：主要关注在网络层传输的数据包的特征，比如数据包大小、到达时间、包与包之间的时间间隔等。（2）Flow_Level分类级别：它主要分析对象为TCP流与UDP流，比如源端口、目的端口、目的IP地址、协议及源IP地址所构成的五元组。（3）Protocol_Level分类级别：主要研究对象为网络传输中的协议，虽然也是对数据包进行研究，但是侧重点在会话识别、主机行为等方面，其中也包含了IP数据包的分析。 西南科技大学硕士研究生学位论文第11页流量分类技术是通过建立分类模型对一个未知的数据对象进行分类[20]，从中体现出分类技术的精确率，衡量精确率主要通过：真正（truepositive,TP）指采集到被模型正确进行分类的样本数量，即属于类型a的样本被预测为类型a；假负（falsenegative,FN）指采集到被模型错误分类的样本数量，即类型a的样本被预测为非类型a样本；假正（falsepositive，FP）与真正相反，指将非类型a的样本预测为类型a的样本；真负（truenegative，TN）指非类型a的样本被预测为非类型a。值得说明的是，由于网络环境的复杂化，很难找到同一基准的环境来测试网络流量。对于衡量自身分类系统的参数都源于对统一特定环境、时间、采集点得到的，所以参数具有很好的参考价值，但在有些情况下不够完备。下面一节我们将对流量分类的方法进行总体的性能分析。1.1网络流量分类主流方法研究表明在网络层所能探知的数据信息是有限的，早期的流量分类模型大多都是通过一个或者数个特征来推断分析，识别通信协议，完成流量分类。比如协议字段、传输字节数、数据包个数、连接时间、持续时间、FIN个数、SYN个数等。纵观整个分类技术的过程，可以把分类方法总结为：基于端口识别的流量分类、基于流量统计特征的流量分类方法和基于内容深度检测流量分类方法。（1）在网络中主机是通过IP地址进行识别，但每个主机随时都运行多个不同的网络服务，于是主机为每一个网络服务分配一个16位(0-65535)二进制标示符，即端口号。相对于IP地址的管理规范，端口号的使用却没有那么严格，IANA(InternetAssignedNumbersAuthority)当前仅对一些知名的端口进行了管理，例如FTP协议使用的21端口，SMTP协议被分配到了25端口，HTTP服务则被分配到80端口。在一定程度上讲，这些注册的端口在流量分类技术方面提供了一些帮助。有研究显示[21]几乎70%的基于端口分类算法都是使用IANA的端口表。传统的基于端口识别的分类技术都是依据IANA注册的知名端口来进行应用类型识别，实现对网络流量的分类。当然由于网络不断的发展，传统端口分类技术已经完全不能满足要求。很多基于P2P的网络应用都使用动态分部的端口号。比如软件Naspster、Kazaa与RealVideo都能够根据当前主机情况动态地协商端口号来实现文件传输功能，但是在与主机协商过程中采用了原始的TCP连接进行。当然还有一些网络应用没有采用注册端口号，例如一些非法用户在UNIX系统下不使 西南科技大学硕士研究生学位论文第12页用80端口运行HTTP服务，而选择了其它端口。另外，有些协议还使用了数据加密技术，使得TCP和UDP的数据包头部不可见，通过正常手段无法获取端口号。事实上，有研究表明[22]采用基于端口的流量分类技术对现有网络流量进行分类，大概有30%-70%的数据包不能被正常的识别，通过注册端口来进行分类也只有30%的数据包能够识别。于是，采用传统的基于端口的流量分类技术已经不能保证其分类质量，分类技术也需要有进一步的拓展。（2）为了避免基于端口识别的流量分类带来的弊端，学者们继续对网络数据包进行研究，基于统计流量特征的网络分类方法应运而生。因为网络应用在网络各层的表现形式各有不同，包括数据包长度、数据包到达时间、数据包持续时间、发送频率、端口号等都存在很大的差异，针对网络流量这些特性，采用数据挖掘技术及机器学习方法来实现流量分类。在网络流量分类技术上采用机器学习的方法是一个比较创新的方法[23]，此方法包含两个步骤：采集大量训练数据用于建造分类模型，然后运用该模型对目标流量进行分类。基于机器学习的分类技术可分为监督型、半监督型与无监督型这三种。中国科学院的自动化研究所的王珏教授等认为，当前机器学习技术从理论上看还存在一些问题。例如：基于统计学的机器学习在满zkq20151125足独立同分布条件方面过于苛刻；且在信息与符号的映射上没有实用方法来支持；机器学习技术需要海量的数据建模，跨学科的数据需要时刻分析，没有一劳永逸的实现方案。采用机器学技术来实现流量分类并不能完全处理实际流量分类中产生的所有问题，但是基于机器学习算法的流量统计特征的分类方法正在逐步发展，能克服传统基于端口识别技术的流量分类方法的弊端，更能够在复杂的网络环境发挥其作用。（3）基于统计流量特征的分类方法实现比较困难并且普适性达不到要求；基于端口识别的流量分类技术在当前复杂的网络环境下很难达到安全标准，学者们提出了基于深度包检测DPI(DeepPacketInspection)[24]的流量分类方法。该方法及可以避免因为端口识别技术带来的不足也可以达到很好的普适性，主要针对网络数据特征字符串进行扫描匹配，然后结合IP五元组来对网络流量进行分类。DPI技术主要分为两个步骤：建立特征库，即针对当前网络上已存在的所有流量类型建立特征库用以匹配特征字符串；扫描特征字符串组，即对IP数据包应用层内容进行扫描实现匹配，比如：Gnutella在建立连接后的首个数据包含有“GNUTELLACONNECT/0.4 ”字样，服务器端回复该信息的报文中含有“GNUTELLAOK ”字样；基于P2P模型演变的协议Freenet，目 西南科技大学硕士研究生学位论文第13页标端口号一般为19114，Freenet开启时，DNS查找www.octayne.com，数据信息第55个Byte处为：03777777076F637461796e650363。了解了匹配对象特征，通过特定匹配算法检查数据包，实现网络流量分类。但是该方法只能针对没有加密的报文或者已经知晓的网络流量特性，对以加密的报文和新的网络协议效果不佳。由于基于深度包检测的流量分类方法在匹配效率上表现良好，现有很多的流量分类在识别协议上都是通过对会话报文中的特殊字段的查询来实现协议识别的。对现有大量P2P协议流的分析表明，基于数据包的高层内容识别的分类算法能够将错误匹配缩减到5%以下[25]，而采用正则表达式来实现应用层内容是当前学术界的研究热点。1.1基于正则表达式的流量分类算法基于正则表达式的流量分类技术主要在DFA原型的基础上进行自动机设计和改进。为了降低状态机存储空间，采取片上高速存储设备提高状态访存效率，提高匹配速度为主流方法。就当前而言，正则表达式的匹配算法才刚刚起步，还没有出现具体的分类标准，对现有算法进行研究，可以将现有zkq20151125的算法按照其对有限自动机定义中的五元素的改进，分为以下三个方面[26]：（1）状态转移函数压缩算法是指对五元组中的δ转移函数进行压缩；（2）状态数压缩算法是指对五元组中的当前状态集合Q进行压缩；（3）字符表压缩算法是指对五元组的∑进行压缩。总的来看，以上的三种算法之间没有直接关系，但是在实际的算法研究中可以从转移函数、状态数和输入字符表三个方面来考虑对算法的改进，实现算法空间复杂度的减小，节约存储空间资源[27]。根据对正则表达式匹配算法的研究，可以观察到在状态数之间的转移边数存在的大量的冗余，所以转换压缩算法的应用相对流行。CD2FA、D2FA、Delta-FA三种算法在DFA算法的基础上进行设计，算法的存储资源开销与匹配时间都有很大的改进[28-30]。文献[31]中指出，相同测试环境下，D2FA与DFA相比，所占存储空间降低了80%；CD2FA存储空间为D2FA的1/10；优化后的D2FA与原始D2FA相比，存储空间降低了90%，与CD2FA相比，存储空间为CD2FA的1/10到1/2之间。同样有些算法设计适用于特定的正则表达式语法[32]，为了解决Kleene闭包引起的状态数爆炸，相关学者开发了XFA算法；Counting-FA则是用于处理计数约束模式，相对而言其实现规模较小，且匹配效率方面表现相对较高。Multi-ACT[33]仅对部分DFA压缩率优于 西南科技大学硕士研究生学位论文第14页Single-ACT，因此应用规模与Single-ACT相比减小了70%，在Single-ACT的基础上实现的Multi-ACT完成了存储空间进一步压缩，相较于原算法节约了1/7到1/4的存储空间[34]，由于增加的多个ACT使得在查找过程中时间消耗增加，同一环境下运行时间会增加35%到85%[35]。下面对几个面向存储的正则表达式算法进行讨论。（1）D2FA算法根据正则表达式的定义可知，对于任意一个正则表达式，都可以经过最小化算法得到一个状态数最小的DFA[36]。正则表达式占用存储空间主要体现在状态数与状态转移边数的多少，我们可以直观的发现，状态数与转移边数的多少成正比。假如输入字符表Σ为ASCII码表，则DFA需要维持的状态数之间的转移边数为256条，可以看出，假如保存整个DFA则需要开辟大量的存储空间。根据Aho-Corasick字符匹配算法的原理实现的D2FA算法，结合了正则表达式匹配算法与Aho-Corasick匹配算法思想，在对标准的DFA算法进行了扩展，通过增加默认边来对状态转换表进行压缩。实现过程为：对DFA中两个中间状态s1和s2，当接受到相同字符集{C}之后跳转到下一个相同的状态集{S}，即d1d，其中{C}为DFA字符表Σ中的一(s,c)=(,)=iscs2iizkq20151125个子集，则可以将其中一种状态对于字符集{C}的状态转换进行删除，不失一般性，若该状态为s1，则对所有的d(,)进行删除处理，并加入一个从s1s1ci到s2的默认转移边。在D2FA匹配过程中假如当前状态为s1，接受到的输入字符为c1，则首先对状态转换表进行查找，若存在d(s1,ci)的状态跳转信息，则直接进入下一个状态；否则，引入一个默认的转移边来确定当前状态的下一跳状态，实施该转换后，字符c1并没有消耗掉，用以匹配下一个状态。构造D2FA算法分为两个步骤[37]：首先将传统的DFA生成空间压缩图，图中的每个顶点代表着各个状态，相同的状态转换数采用顶点间的边来表示；再根据压缩图采用Kruskal算法产生最大生成树，树中的每个节点都可以作为树的根，将根节点确定以后，就确定了默认转换边的下一跳方向。（2）H-FA算法H-FA[38]由一个自动机与一个历史集合构建而成。提出该算法的初衷是对Kleene闭包引起的状态数爆炸进行削减。H-FA可以通过类似于DFA五元组的形式化描述表示成一个六元组M=(Q,q0,∑,A,δ,H)，其中Q，q0，∑，A这几个元素都与标准DFA的相同，这里我们把H称为历史缓存，δ:Q×∑×H→Q×H是状态转移函数。在H-FA当中将H应用于包含Kleene闭包的状态，从而达到有限自动机 西南科技大学硕士研究生学位论文第15页的压缩效果，节约存储空间。这里我们以包含Kleene闭包的表达式合成为实例予以描述：两个正则表达式分别为RE1->.*ab[^a]*c，RE2->.*def，图2-7表示这两个表达式的NFA转换图，图2-8则为他们相应的DFA状态转化图。NFA中的状态2具有Kleene闭包，因此在历史缓存H中增加一个与之对应的标记，运用子集构造法产生标准DFA时，将在DFA中含有标记状态的子集定义为退化状态（图2-8中的4个阴影状态）。将所有的退化状态移除之后，就能达到状态数爆炸削减效果，从而得到的H-FA状态转换图如图2-9所示。[^a]*0adbc12ef4536图2-7识别*ab[^a]*c与*defNFAFigure2-7Recognition*ab[^a]*cand*defNFAzkq20151125aa a1.10.2bc2.1ad*0dae2.1.10.2.5f2.2.1d df2.20.50.6 ed d图2-8识别*ab[^a]*c与*defDFAFigure2-8Recognition*ab[^a]*cand*defDFA 西南科技大学硕士研究生学位论文第16页a a0.12.1a,|2,-2b,+20adac,|2,-2ddf,|22.2ef2.30.6de,|2d图2-9识别*ab[^a]*c与*defH-FAFigure2-9Recognition*ab[^a]*cand*defH-FA这里算法是通过在不同状态之间的转换中添加三种操作，用以消除退化状态，这三种操作为：元素H中状态S标记设置（+s），重置状态S标记（-s）与满足重置位的条件转换（|s），这三种操作都包含在转移函数δ中[39]，即δ:Q×∑×H→Q×H。（3）Single-ACT算法zkq20151125对输入字符表∑进行压缩的算法Single-ACT[40]，其主要思想是：对于DFA中的∑，在维护的状态转换表中，对于该DFA中的每个状态需要保存∑个状态转换信息，每个状态转换对应于∑中一个标识符号。可以对∑中的符号进行分类，对于∑中的符号ci和cj，如果对DFA中的每个状态s，都有d(s,ci)=d(s,cj)，那么就将ci和cj归为一类。一旦将ci和cj归为一类，那么同时保存从不同的源状态接受输入字符ci和cj到而跳转到相同的下一状态的状态转换则是冗余的，因而消除这些冗余则可节约大量存储空间。文献[41]中的算法character_class(DFAdfa=(n,δ(states,∑)),modifiessetclass)实现了由初始的输入字符表到符号类的映射过程。进行字符分类后，若新的字符表为∑'，字符表大小就由∑减小到∑'，对每个状态仅需保存∑'个状态转换。这种情况下，可以进一步对分类后的字符表进行重新编码。相应建立的由∑到∑'的映射表由于频繁访问，可通过高速缓存提高查找效率。这里以图2-10所示匹配过程为例，图a为尚未经过压缩处理的DFA，当接受第1个输入字符，当前状态为1时，则需查找在此状态转换表中维护的相应状态跳转信息，然后跳转到下一状态。图b则是采用Single-ACT算法压缩后的DFA，当接受第1个输入字符时，算法开始查找字符压缩表，根据索 西南科技大学硕士研究生学位论文第17页引值index=0进一步查找状态1的下一状态跳转信息，最后跳转到下一状态12。这种采用压缩字符表技术在减小了DFA的存储空间上表现很好。State0State1State2State32525254141415512121242828121212448882525256415415input_char=1next_state=12crt_state=1a)ACT00State0State1State2State3012122525144641224414138454142841558855index=0input_char=1next_state=12crt_state=1zkq20151125b)图2-10未压缩的DFA和Single-ACT压缩后的DFA匹配过程Figure2-10DFAmatchingprocessanduncompressedDFAcompressedSingle-ACT（4）Multi-ACTMulti-ACT在Single-ACT的基础上进行了扩展[42]，它的主要思想为：为建立一个包含m个ACT的DFA，开始将自动机的状态划分为m个子集，并且对每个子集建立一个Single-ACT。在匹配时，不仅要对当前状态机所处状态和当前的输入字符进行记录，而且还要维护m个子集中的某个ACT匹配。因此，不仅要对状态转换表中的目的状态进行编码，还要对相应的单个ACT进行编码。以图2-11所示的经Multi-ACT压缩后的DFA匹配过程为例，若当前状态为状态1，输入字符为1，当前字符表压缩表为ACT1，首先查找ACT1接受第1个输入字符的索引信息，根据索引值index=0进一步查找状态1的状态转换信息，记录目的状态12的同时，保存下一状态对应的字符压缩表 西南科技大学硕士研究生学位论文第18页ACT0。ACT0ACT1State0State1State2State3000110001200025041150012428010120418002564151322index=1next_act=1 23input_char=1next_state=1crt_act=1crt_state=1图2-11Multi-ACT压缩后的DFA匹配过程Figure2-11DFAmatchingprocessaftercompressionMulti-ACTMulti-ACT算法的关键问题在于子集划分标准。如果使用的单个ACT数量没有数量限制，在文献[43]中给出了最小化存储空间的子集划分算法character_class(StateSetStates)，该算法的时间复杂度为O(n|∑|)。而实际自动机中ACT的数量过多会使匹配效率严重降低，往往将ACT的数量限定为一个上界。将n个元素划分为m个子集存在S(m,n)种划分，1m=åS(m,n)(1)()-iCim-inmmi=0。从n个元素划分为m个子集的过程并没有一定的准则来判定某一算法是否为最优划分，实现上存在两种算法，“自底向上”的方法和“自顶向下”的方法。KONGshi-jin所提出的贪婪的启发式算法能够在O(mn|∑|3)的时间复杂度产生较小的状态转换表。基于正则表达式分类算法的发展，一直在时间复杂度与空间复杂度上寻求一个较好的平衡点，但是都没有一个让人满意的结果，下一章节将针对现有问题对算法进行改进，是匹配时间与状态数达到一个较好的平衡点。1.1本章小结本章对NetFPGA开发平台及网络流量分类技术进行了系统的介绍。NetFGPA为高速网络及下一代网络提供了研究平台，并为开发者提供较为方便的开发流程以实现特定功能；同时对将要采用的流量分类算法进行了系统分析，重点分析了基于正则表达式的分类算法，并对典型算法进行研究，总结出它们的优缺点，为下一章节的工作铺垫理论依据。 西南科技大学硕士研究生学位论文第19页3基于正则表达式分类算法的研究学术界在深度包检测方面选用匹配技术主要分为两派：以KMP、BM与QS算法为代表的单模式匹配算法，以及以DFSA、Wu_Manber和AC算法为代表的多模式匹配算法，算法本身都是基于字符串的，扫描识别方式分为前/后缀搜索与字符串搜索。由于当前网络环境的发展迅速及大量复杂的协议诞生，模式匹配算法的局限性慢慢体现出来，因而更灵活的匹配算法诞生——基于正则表达式的匹配算法。1.1正则表达式的模式匹配根据正则表达式的语法规定，它主要是由几个元素构成，包括元字符(Meta-characters)、模式修正符(Modifier)、量词(Quantifiers)和子模式(sub-patterns)等元素，通过一系列自定义模式对字符串进行识别。而对象特征模式则是由一组描述字符串特征的字符组成。正则表达式具有强大的灵活性与扩展性，它能够快速地分析大量文本信息，并在其中找到特定字符，对其实现编辑、替换或删除功能。正则表达式匹配原理是基于自动机理论生成的，当对象文本推送到匹配引擎后，且被接受状态接受时，我们则认为该对象文本与自定义的表达式实现了匹配，否则认为不能实现匹配[44]。所以在构建自动机时我们需要设定一个初始状态，根据推送的目标字符串，跳转到下一个状态，这时就要维护一个状态集来完成状态的跳转工作。这里跳转的一下状态由状态转移函数δ决定，最后需要观察是否被最终状态接受。因此在这整个过程中就我们就定义了有穷自动机(FiniteAutomate)的五元素M，他们分别为：状态开始时的初始状态、有穷状态集合、定义的转移函数、有限的输入集合及接受状态集合（包括初态与终态）。然而我们根据状态转移函数的不同，又可将它定义为确定性有穷状态机（DeterminismFiniteAutomate,DFA）与非确定性有穷状态机（Non-DeterminismFiniteAutomate,NFA）两种类型。在他们之间最大差别就是确定与非确定的差别。NFA中一个确定输入可以对应1个或者多个状态，即对应一个集合。而DFA则是一个确定的输入就有一个确定的状态。在某种程度上可以理解为NFA与DFA等价的[45]，只是他们之间存在一定的转换。 西南科技大学硕士研究生学位论文第20页1.1构建DFA与NFA（1）根据DFA的匹配过程和原理来看，我们定义了它的几个元素，分别为：①有限状态集合，我们设定为K。②有限输入字母表，设定为Σ。③设定一个从K×Σ到K的转移函数f，f(p,a)=q（q为确定值），若当前的状态为p，而推送的字符为a时，跳转的下一状态则用q表示。④定义一个属于K的初始状态，设定为S0。⑤在K中定义若干个最终接受状态，由它们组成了终态集合，我们设定为Z。它们的五元组M表达式如下所示：M=S（3-1）(K,,f,S0,Z)公式3-1定义为DFA。因此我们可以看出，一个确定的有限自动机抽象的来看就是各个状态转换矩阵的一种描述。下面我们通过扩展定义，得到f的定义域为K×Σ。f(,e)=（3-2）SSf(S,aw)=f(f(S,a),w),aÎS,wÎS（3-3）*1SA001100BC 1图3-1确定有限状态机实例Figure3-1Determinethefinitestatemachineinstance通过图3-1表示的实例，我们来对DFA进行分析。图3-1所表示的DFA只对含有偶数个0和1的字符串予以接受匹配。该DFA表示为({S，A，B，C}，{0，l}，f，S，{S})，f的定义如表3-1所示： 西南科技大学硕士研究生学位论文第21页表3-1f的定义Table3-1fdefinedFf(S,0)=Bf(S,1)=Af(A,0)=Cf(A,1)=Sf(B,0)=Sf(B,1)=Cf(C,0)=Af(C,1)=B该DFA的状态转换图如表3-2所示表3-2图3-1对应的DFA转换表Table3-2Figure3-1CorrespondingDFAconversiontable状态输入输入01SBAACSBSCCAB表3-3状态转换Table3-3StateTransition输入输入11010111101M(S,110101)=M(A,10101)M(S,11101)=M(A,1101)=M(S,0101)=M(S,101)=M(B,101)=M(A,01)=M(C,01)=M(C,1)=M(A,1)=M(B,Φ)=M(S,Φ)=S（不接受）=S（接受）比如推送的字符串为“110101”可以被该DFA所接受，推送字符串为 西南科技大学硕士研究生学位论文第22页“11101”时则不能被该DFA所接受，它们两个的状态转换过程如表3-3所示。（2）对于NFA，我们同样用一个五元组M=(K,S,,0,Z)来定义其非确fS定有限自动机。表达式中K，Σ，S0和Z的含义与DFA五元组含义相同，只有状态转移函数f的不同。因为NFA的f对应的是一个集合，不具备确定性。序列(Si，aj)在f转移映射下转换成K的子集{Skl，Sk2，…，Skm}，即f(Sia)={S,S,...S}（3-4）,jk1k2km从而在NFA中的f则维护了从K×Σ到2k的一个映射关系，对于某些Si和aj，f(Si，aj)也许是空集。f(S,e)=S（3-5）f(S,aw=ffSawaÎSwÎS（3-6）)((,),),,*f(S,a={kS,...S})S,1k2km（3-7）且定义fUm({SkSSw=fSw（3-8）1,,....},)(,)k2kmkii=1则有f(S,aw)Um=f(f(S,a),w)=f(S,)（3-9）kiwi=1所以根据公式3-9，可以看出状态转移函数f的定义域为2k×Σ*这里我们假设M={{S，A，B，C}，{a，b}，f，S，{C}}，状态之间的转换如图3-2所示，可以看出M是一个NFA。表3-4表示了通过M识别ababb的简明过程。a,babSAB aa abC 图3-2一个NFA示例图Figure3-2AnNFAexampleoffigure 西南科技大学硕士研究生学位论文第23页表3-4图3-2的状态转换表Table3-4Statetransitiontableoffigures3-2步骤当前状态待定输入后续状态集合选择状态1SababbA,CA2AbabbA,BB3BabbAA4AbbA,BB5BbC接受所以我们得出，在NFA中，下一状态的选择往往都是从若干个状态组成的集合中选取。一个NFA的识别过程其实就是一个一直探测的过程，即每次跳转都需要执行状态转移函数来确定下一跳的状态，这样就直接延长了匹配时间，降低效率。不过，对于每个NFA的M而言，总可以通过某种形式组建一个与之相同效果的DFA的M`，使得M能够接受的状态都能够通过M`来完成接受。（3）DFA与NFA最主要差别就是在状态转移函数上表现的不同映射关系，一个对应确定的状态，一个对应集合，且NFA在集合中选取对应状态又是一个探测过程。由于DFA当前状态经过判断的下一跳状态是唯一的，所以基于DFA的正则表达式匹配间复杂度较小，用O(1)表示，待匹配文本的长度与匹配时间呈线性关系。但是DFA存在状态膨胀问题：当正则表达式的实际长度为m时，最坏情况下DFA的状态个数为O(2m)。所以在构造DFA过程消耗的时间较长。通过正则表达式直接构造DFA的算法相较于先构造NFA再构造DFA过于复杂。有些算法采用预处理机制来对时间与内存开销进行控制，预处理阶段并不将正则表达式构造成一个完整的DFA，复杂的工作延迟到匹配阶段。这样在预处理阶段可以节约大量的时间与空间开销。我们采用间接构造法来完成DFA的最终生成：任何NFA都可以构造成与其效果相同的DFA，所以在算法初期先对表达式进行NFA构造，然后根据NFA状态转换来实现DFA的生成。对于基于正则表达式构造的任意的NFA，采用子集构造法完成等价DFA转换。这里我们首先需要了解闭包ε， 定义具有空转移的FA即ε转移，如图3-3所示。用五元组为M=(K,S,f,S0,Z)来定义一个具有空转移的NFA，其中K，Σ，S0和Z的含义同前，而f却是 西南科技大学硕士研究生学位论文第24页K´2k的一个映射。此时对于NFA处于状态q，接受到推送的目标字(SUe{})符为a（aÎS或a=e）将跳转到p，这里p为下一跳状态。对于图3-3定义的NFA转换图，与其对应的转移矩阵由表3-5列出。abεbABSεcCε图3-3具有空转移的实例Figure3-3Instancewithanemptytransfer表3-5状态转换表Table3-5StateTransitionTableabcεA{A}ΦΦ{B,C}BΦ{B,S}ΦΦCΦΦ{C}{S}SΦΦΦΦ我们从某一给定的状态q出发，仅经过若干条空转移所跳转到的下一状态的集合（q在此集合内），记做e-closure(q)即闭包。例如对于图3-3来说有：e-closure(A)={A,B,C,S}(3-10) e-closure=(3-11) e-closure=(3-12) e-closure=(3-13)(B){B}(C){C,S}(S){S}采用基于闭包的子集构造法构造DFA是较为常规的办法[46]。 定义具有ε动作（空转移）的NFA的五元组为M=(K,S,f,S0,Z)我们 构造的DFA的五元组则为M`=(K`,S,f`,q0,Z`)基本思路是：从定义初始状态S0出发，定义M`的初始状态q0由任意一个空转移能跳转的下一状态的集合。将K`定义为对任意输入符号a∈∑的下一跳状态所能到达的状态(包含下一状态再经过空转移所能到达的一下状态） 西南科技大学硕士研究生学位论文第25页组成的集合。所以DFA中的五元组中K`和f`的构造过程如下：K=e-(`)①令`{closure(S)}00②对于K`任一尚未标记的状态qi={S1,S,....S},SÎK。首先标记qi；ii2imik然后对于每一个a∈Σ，置=f({Si1,S,...S},a),qj=e-closure(T)；最后对于Ti2im不属于K`中的qj，标记它并将其状态添加到状态集合K`中，再将状态转移函数f(qi,a)=qj添加到DFA的五元组中。③对②重复执行，当K`中所有的状态都标记完毕，不再出现未标记状态则停止执行。构造K`完毕之后，把至少含有一个Z中的元素的qi，标记为M`中的状态。通过下面两幅图来阐述整个过程，NFA的状态转移图如图3-4所示a23εεεεab016789ε εb45图3-4一个NFA例图Figure3-4AnNFAcasediagram图3-5为经过子集构造法完成的DFA状态转换图。其中A={0，1，2，4，7}B={1，2，3，4，6，7，8}C={1，2，4，5，6，7}D={1，2，4，5，6，7，9}bCbb aaABabaD图3-5等价DFAFigure3-5EquivalentDFA 西南科技大学硕士研究生学位论文第26页（4）根据自动机的定义及正则表达式原理，每个正则表达式r，都可以通过Thompson算法构造成有限状态机FSM（FiniteStateMachine），从而使得L(M)=Lr，L为正则表达式形式化描述。构造的算法是根据自定义表达式r的表现形式，对r中包含的运算符个数n进行递归运算。以此构造的FSM均是包含了空转移边的NFA，为了方便我们需要定义一个初态和一个终态，到达终态就不再有跳转边指向其他状态。NFA的构造算法是假设r为输入字符表Σ上的一个自定义的表达式，将r中所含运算符个数定义为n。当n=0时，表示表达式无运算符，则r必然为空（Φ）、ε或者Σ中的某个字符a。因此构造相应的NFA如图3-6所示。aS0SfS0S0Sfr=Φr=εr=a图3-6没有运算符的正则表达式r的NFAFigure3-6NooperatorrofNFAregularexpression设当n=1,2，…,k-1时，表示表达式r有多个运算符构成，其相应的NFA可以线性构造，当n=k时，构造NFA时据正则表达式原理，r是以下三种方式之一构造而成，即r1|r2，rl.r2和rl*，rl、r2也为整个正则表达式r的子表达式，并假设r1与r2之间的运算符的个数均在[0-k-1]之间，故我们定义r1和r2的NFA五元组为：M=S1(K,,f,S,Sf)111011(3-14)及M=S2(K,,f,S,Sf22202)2(3-15)均已作出，并使L==，再根据上面的三种方式构造相(M1)Lr,L(M)L12r2应于r的NFA的方法即可。此外，我们定义KÇ=F，及K1与K2之间没1K2有关联性。①r=r1|r2的情况 西南科技大学硕士研究生学位论文第27页这里我们根据需要引入两个状态，即S的初始状态S0和终止状态Sf，然后根据图3-7表示的状态转移方式，将空转移（ε矢线）作为M1与M2并联线，构造出来的NFA的五元组M为M=UUSUS(3-16)(K{,1KSSf},,f,S,{Sf})20120其中状态转移函数f的定义如下：f,e)=(3-17)(0SSS{,}0102f(S,a)=ìíîf(S,a)当SÎK11f(Sa)当K,SÎ22-{S},aÎS{e}且时Uf11(3-18)-{},且SaÎS{e}时Uf22fe=,e={}(3-19)(Sf,)f(S)S1f2f对由此构造的NFA，我们有L=U=U(Mrl)L(M1)L(M)L21r2S01M1Sf1ε εS0SfεεS02Sf2M2图3-7r1|r2NFAFigure3-7r1|r2NFA②r=r1.r2的情况这里我们将以M1的初态S01与M2的终止状态作为正则表达式NFA的初态与终态，且也用空转移（ε矢线）按图3-8所示状态转换关系将M1和M2传联起来，所构造的NFA五元组M为 M=USUS(K1K,,f,S,Sf{21201})2(3-20)其中状态转移函数f的定义如下：f(S,a)1Î-ÎSUe111=f(S,a)SK{S},a{}当f且(3-21)f(Sf1,e)={S(3-22)}02 西南科技大学硕士研究生学位论文第28页2ÎÎSUe =fSaSKa22f(S,)(3-23)a(,)当且{}时对此构造的NFAM有：L()=L·L=·M(MrL1)(M)L21r2εS01M1Sf1S02M2Sf2图3-8r1.r2的NFAFigure3-8NFAofr1.r2③r=r1*的情况同样，我们这里也引入两个状态S0与S1，然后根据图3-9构造NFA状M=US态转换图构造其五元组M，即(K1{S,Sf},,f,S,{Sf})010其中，状态转移函数f的定义如下：f(S,a)f(S0e)={S,Sf}(3-24),011Î-ÎSUe111=f(S,aSKSfa(3-25))，当{},且{}时f(Sf,e)={S,S}(3-26)101f对此构造的NFAM有LM)=(L(M=L(1))**r1S0S01M1Sf1Sf2ε ε图3-9r*的NFAFigure3-9r*ofNFA 1.1DFA状态膨胀分析文献[47]中指出，任意标准正则表达式的NFA与DFA都存在某种形式化的方法构造出来。通过前面的分析，我们可以看出正则表达式的长度与NFA的实际长度存在线性相关性，NFA生成的过程中，表达式中的每一个字符(属于字符集)、操作符与元字符都与NFA的状态数相对应。但对于DFA而言，它需要一个确定的输入对应一个确定的输出，表达式结构越复杂它对应的DFA状态数越多，最坏的情况下，产生的DFA的状态数与其自身结构存在 西南科技大学硕士研究生学位论文第29页指数级膨胀关系。以图3-10说明，3个结构相同正则表达式RE1,RE2,RE3他们之间的NFA状态转换图都相同，但由于计数值的不同，所产生的DFA状态数依次为4,5,7个，且转移边数增加。其中，RE2与RE3都有计数结构。∧aa∧aaDFAaabcdS1234∧aba∧ac∧adNFAεεεabcdS2345617ε ε(a).*abcdDFASaaaabb134∧a∧aaa∧ab∧a25∧aNFAεεεab∧a∧aS2345617ε ε(b).*ab[^a]{j},j=2DFASaababaa∧ab13452∧aa∧abb∧aba2b∧ab67a1∧a ∧aNFAεεεab∧b∧bS123456εε7(c).*ab[^b]{j}j=2图3-10RE1.RE2.RE3的NFA与DFAFigure3-10NFAandDFAofRE1.RE2.RE3 西南科技大学硕士研究生学位论文第30页我们可以看出，不同类型正则表达式结构构造DFA状态数与表达式的复杂度有密切关系。可以归纳为：对于识别大字符串的正则表达式，其需要维护的DFA的状态数越多；输入目标字符串可能与正则表达式中的不同部分对应，导致歧义匹配的产生，则DFA需要维护更多的状态来区分。在实际网络环境中，各种不同的协议决定了匹配对象的复杂化，这种情况必然导致表达式长度增加与运算复杂化，这里我们总结了几点关于DFA内存膨胀问题：（1）状态数增加必然导致主机内存降低。根据统计，DFA，mDFA通过比特位移除无效边得到的每个状态需要开销32Byte内存，D2FA与CD2FA在移除无效边之后还要对添加默认边进行过滤，每个状态的内存开销为64Byte。（2）状态之间迁移边数增加也占用相应内存。状态的迁移都需要指令的控制，XFA指向下一状态的地址位需要消耗4Byte，此时还需要1Byte操作类型，对应规划编号则需要[logM/8]Byte，M代表了状态数多少。（3）目标字符串可能对应表达式不同部位，引发歧义匹配。DFA则需要利用状态数的增加来弥补匹配过程中产生的歧义匹配，因此需要的存储空间相当庞大。表3-6各类算法比对Table3-6Comparevariousalgorithms分类名称规模速率存储要求转换压缩D2FA大中中CD2FA大中小δFA大快大状态压缩XFA中中中mDFA大中小Hybrid-FA中慢中Counting-FA小快小字母表压缩Single-ACT大中中Multi-ACT中慢小结合上述分析，DFA虽然在时间复杂度上能够达到研究人员的要求，但 西南科技大学硕士研究生学位论文第31页是其空间复杂度的增加很难直接被采纳用于实际网络分析。表3-6是对现有算法的总结。传统的NFA与DFA在现有网络环境下很难再发挥其作用，不仅匹配速率达不到线速要求，且随着各种垃圾流量、病毒的蔓延，导致特征库一直更新，要求正则表达式也同步变换，传统算法在可伸缩性方面表现低下，且状态数控制方面也不让人满意。研究人员提出通过消除状态数方法来完善算法性能[48]，核心思想都在于消除迁移状态间的冗余，降低空间复杂度，主要分为对转换函数δ压缩、状态集合Q压缩、字母表Σ压缩。通过在规模、速率、存储要求方面的分析，虽然有些算法在个别方面表现都比较出色，但是综合效率不是特别理想，针对这些问题，本文基于传统DFA算法，重点削弱状态膨胀数，采用One-Pass扫描算法，优化算法在时间空间复杂度两方面的性能。1.1设定动态参数2.1状态数增长率参数Ex为了对状态数增长有一个很好的衡量标准，本文考虑到有限状态机的算法为无记忆的，对已匹配目标字符缺乏辨识度，且大量不同的结构运算符对歧义匹配造成不同量级影响，这里引入衡量状态数增长率的参数Ex，用于衡量状态数的冗余，也通过Ex大小将表达式分为不同的等级。正则表达式是基于普通元素集合，或语法修饰结构的元字符构成，根据NFA构建过程，表达式实际长度由NFA来表示更为合理。因此根据实际表达式情况，给出Ex定义为：N-NE=（3-27）DFANFAxNNFA其中：NDFA与NNFA分别为相同表达式下DFA状态数与NFA状态数，他们之间的差为构建DFA所产生的额外状态，与NNFA相除则得到状态增长率Ex。针对Ex我们对6个类型相同的正则表达式进行了计算，他们之间的区别只存在与计数值的不同，但是由此产生的DFA状态却不同。如图3-11可以看出，虽然表达式结构差不多，但是由于计数值不同，导致了状态数也不相同。 西南科技大学硕士研究生学位论文第32页400350300250200.*abcdef[Λa]j.*abcdef[Λb]j.*abcdef[Λc]j.*abcdef[Λd]j.*abcdef[Λe]j.*abcdef[Λf]j1501005001471013161922252831343740434649j图3-11相同类型表达式的DFA状态数Figure3-11DFAstatesexpressionsofthesametype针对该参数，本文通过Flex词法分析器，对表达式进行一个分类。表3-7为Snort规则集中5个类型近似相同的表达式的Ex。由表可见，第一种表达式空间复杂度与j呈指数关系增长，表达式的Ex已经溢出，无法确定其值。第二与第六种呈平方增长；第四、第五种呈线性增长，但是Ex较高，所以虽然DFA状态数与计数值呈线性增长关系，但是由于表达式本身结构也会引起Ex增加，产生多余的状态数。闭包运算对增长率的影响比较小，但是多个闭包在统一表达式时候引起的歧义匹配会让DFA状态数急速增加。所以总结可得，表达式在包含了字符集的闭包和计数的情况下，特别是大字符集的运算，会导致DFA状态数的急剧增加；只通过表达式计数值来衡量膨胀程度的大小是不完善的。所以我们需要对表达式本身结构及字符运算进行相应处理。表3-7类正则表达式Table3-7classregex结构例子Ex空间复杂度.*AB.{j}*contenttype=[∧r x3bx38]{20}>9999O(2j).*A(B[∧B]{j}|A.*(s*(x27[∧x27]{1024,}|x22[∧x22]{1>9999O(j2)[∧A]{j})024,}).*A.*B.*C*x2Fcgix2Flogurl.cgi.*User-Agentx3A[2.393N/A∧r ]*MyPost.*formdatax3Bx20name.*AB[∧B]{j}.*x28s*names*x22[∧x22]{260,}12.453O(j)∧AB+[∧A]{j}[∧x00x3Bx3D]{30}8.351O(j)∧AB+.{j}∧TESTs+[∧ ]{100}43.579O(j2) 西南科技大学硕士研究生学位论文第33页1.1重组膨胀率相关参数η与Sc对表达式进行重组是一种基于状态压缩的算法，由表达式合并产生状态机而导致的状态空间膨胀是常见的问题，例如*ab.*ed和.*ef.*gh的合并而成的DFA需要开销大量额外空间，我们采用的策略就是：将可能会引起状态空间爆炸的规则通过动态的判断，即通过设置状态阀值，对规则集进行合理的划分，达到状态的缩减。即测试每两个规则表达式合并前后的DFA状态数是否在合理范围以内，若大于预先设定的值，则不予以组合，否则合并，直到合并后的规则表达式产生的DFA状态数超过预先设置的阀值，这时重组后的表达式完成。在匹配过程中，使用穿行匹配会对匹配时间带来很大的开销，所有在匹配方式上，我们也进行了修改。本文考虑到每个规则表达式所产生的DFA状态数各有不同，且组合后可能增加也可能减少。为了解决膨胀问题，这里我们定义：多个表达式完成重构后所产生的DFA状态数大于每个表达式单独产生的DFA状态数之和称他们存在互斥性。图3-12（a）（b）（c）（d）分别为egact、egbct、eg.*ft与cd.*ab，4个表达式重组前、后的DFA状态数。前两个表达式重组后显示状态数减少了7个，说明他们之间存在相关性。但是后两个则多出了6个，说明他们之间存在互斥性。egact012345egbct012345(a)单体DFA状态数(a)SingleDFAstatesaegbt01234(b)重组DFA状态数(b)RestructuringDFAstates 西南科技大学硕士研究生学位论文第34页fegft01234acdab01234(c)单体DFA状态数(c)SingleDFAstatesfcegft1234cd4ft10100c5d10e5101010gbaab34ea(d)重组DFA状态数(d)RestructuringDFAstates图3-124个表达式重组前后状态数Figure3-124Numberofstatesaroundtheexpressionofrecombinant通过Flex对L7-filter规则集分析得出90%表达式之间存在互斥性。所以本文通过定义膨胀参数η与组合状态数上限#Sc（Combinationexpression）来衡量重组表达式的必要性。这里参数可为一个固定值也可为一个动态值，但在本文中我们选用η为静态值而#Sc为一个动态值来完成算法整体实现，即通过对参数的动态设定，检测在不同参数值的情况下算法的表现情况。动态的η为初始状态数#So（Originalexpression）与#Sc之间的函数值，实施起来比较复杂。即重组前单个正则表达式的DFA状态数与重组后新正则表达式的DFA状态数之间的函数关系。 西南科技大学硕士研究生学位论文第35页1.1削弱状态膨胀数2.1合并互斥性在通过组合规则集之前，我们需要寻找关于两两表达式之间的关系，这里我们建立一个二维数组Matrix来解释它们之间的关系，每个Matrix的值由0或者1来组成。Matrix[m][n]代表m规则与n号规则它们之间的DFA状态数存在的关系，0代表没有不存在任何关系，即不存在可组合性分析，1代表存在一定关系，即可进行可组合分析。根据上述分析，我们定义m个模式集合为{P1，P2，P3，......Pm}，每个元素的DFA状态数用Di表示，所有m个表达式合成表达式的DFA状态数为Dm，为避免重组后DFA膨胀问题，将k个表达式合并的DFA称为Rk集合，用{R1，R2，R3，.....Rk}表示，集合中每个表达式对应的DFA状态数为DRi，不能组合的表达式集合定义为Wc，用{W1，W2，.....Wc}表示。这里定义η的表达式为D+Dh=ij(3-28)Dij其中Di，Dj分别为未组合前的表达式DFA状态数，Dij为组合后的状态数。阶段一：将模式集合{P1，P2，P3，......Pm}两两分为一组，并对任意PiPj（0≦i≦j≦m）构造其DFA并推算出状态数Dij。对比组合后的状态数与之前未组合的规则表达式DFA状态数之间的关系。在此定义组合后的状态数上限为#Sc，其值为一个动态区间，且定义η的值。阶段二：根据#Sc上限及η取值进行初始集合Wc`与Rk`的构造。若Dij（0≦i≦j≦m）达到#Sc上限，或者超过η预先设定的值，则将Dij即组合后的规则表达式所产生的DFA视为无效状态，不予以重组，并添加到待处理集合Wc`中。若否，则标记并合并，并添加到集合Pk`中。此过程中存在相关性的表达式将合并其相同状态，达到了空间复杂度的释放。阶段三：进一步对初始集合Pk`中的元素进行处理，得到最终的Wc与Pk集合。依次判断Wc`中元素与Pk`中以标记元素是否具有相关性，即重复阶段一，若0≦Dij≦#Sc或参数值小于η预先设定的值，则根据阶段二步骤完成合并，若否则算法结束。如图3-13所示。 西南科技大学硕士研究生学位论文第36页随机分组η#ScNY是否超出Pk`Wc`η#ScN是否最优?YPkWc结束图3-13算法流程图Figure3-13Algorithmflow1.1切割膨胀片段虽然经过上述重组算法，集合Pk与Wc中规则表达式依然存在大量闭包[49]（*，+），计数结构（{}），集合（[]）等结构运算符，这些都是导致歧义匹配关键因素。直观认为组合后的表达式结构复杂度与结构运算符有增无减，势必引起Ex急剧上升，导致DFA状态数急速增加，影响匹配效率。这里定义片一为包含闭包、计数结构与集合等结构运算，用F1（Fragment1）表示。其余部分为片二，用F2（Fragment2）表示。表3-8为几个表达式分片实例。其中【】代表F1，其余部分为F2。显然经过切片可以明显看出，F1为结构运算符与大量字符构成，构成DFA时候引起状态数剧增的机率较大，而F2则为一般表达式不会引起状态数急增。表3-8几个表达式分片实例Table3-8slicesafewexamplesofexpressions正则表达式1【.*】x28s*names*x22【[^x22]{260,}】2【.*】cache_lastpostdate[【[^]]+】]3【^】(bGETb|bHEADb)【.*】bHTTPb4bContent-Typeb:【s*】(bvideob|baudiob) 西南科技大学硕士研究生学位论文第37页这里主要将表达式拆两片，理论上根据算法描述可以全部分解，即对F2进行再次分拆，提高时间复杂度，但是这样会导致算法复杂度的增加。本文将每个标记与未标记的表达式都分解为3个子表达式，以F2为中心节点，前面为头部后面为尾部。图3-14为分片过程描述。初始表达式 表达式F2F2F1F1F2F1F1F1切片F2F2F2F1F1F1F1F1分组头部中心尾部图3-14表达式分片过程Figure3-14Expressionfragmentationprocess阶段一：定义为一个值δ。通过公式1计算出此时增长率Ex。假如Ex>δ成立，则将表达式按照特征进行切片放入队列Queue中进行分切片处理，否则不予以切片处理。阶段二：判断Queue中元素类型。当在Queue中元素为F1时，记录在F1之前的元素为头部记为Ehead；F1之后的元素为尾部记为Etail；当然F1为中部记为Emiddle；分别计算头部、中部、尾部的状态数增长率参数Ex。如果为F2，则不予以处理。阶段三：比较当前Ex与预先δ值的大小。分别将Eh、Em、Et与δ进行比较，如果当前三个Ex中任意一个满足Ex<δ则记下切片的位置，停止计算。否则判断当前增长率Ex与三个部位的Ex的大小，记录下他们之间的最小值或者切片位置。设定的这里算法为启发式算法，对表达式中不同F2进行探索性定位，当发现头、尾两部Ex出现急剧下降时，意味着此时找到的引起歧义匹配位置最佳。一个增长率比较大的规则表达式存在片段F1的几率很大，对这样的规则表达式进行切片处理之后，表达式的Ex一般都会出现下降。该方法通过设定有效的δ值来区分F1与F2，针对增长率较大的规则表达式具有很好的效果，算法的复杂度与表达式的分片个数成正比。对大多数正则表达式算法来说主要考虑的影响因子为：表达式所产生的 西南科技大学硕士研究生学位论文第38页状态数、状态之间的迁移边数、歧义匹配以及状态存储方法等，由于他们之中状态数的数量问题尤为重要，所以本章的上几节重点是对状态数如何削减进行了详细阐述。下面将对其报文匹配方式进行研究，通过对三种报文匹配方式的分析，选择其最优方式与本文提出的算法结合使用。1.1报文匹配方式研究本文所使用的算法主要目的在于消除规则表达式在产生DFA状态数进行匹配的时候所占用的内存，且算法在实现目标匹配时候不能消耗过多的时间，这样会影响算法的整体效果。接下来我们对报文匹配方式进行研究。报文匹配方式中最简单的匹配方式就是将各个表达式放入到一个集里面，然后对报文进行串行匹配，当第n个匹配不成的情况下才能进行第n+1个匹配，这样在同等情况下，匹配时间的消耗上是一个表达式匹配的O(n)倍[50]，因此在匹配方式上需要进行优化，减少匹配时间。下面我们将对单报文匹配、多报文叠加匹配、多报文一次匹配进行分析。（1）当每一条会话流的每个报文到达时，协议匹配模型进行应用层数据提取，然后送进匹配引擎进行匹配，直到对象匹配成功，则同一流的后续报文不再匹配，匹配过程如图3-15所示。报文头1应用层信息1报文头2应用层信息2报文头3应用层信息3报文匹配数据应用层信息1应用层信息2匹配引擎匹配引擎匹配结果匹配成功无法匹配图3-15单报文匹配方式Figure3-15Singlepacketmatchingmode采用单报文匹配模式匹配对象时，在速率的匹配方向及未跨报文情况下准确性都表现出色。通过对已有报文进行匹配分析，比如HTTP、QQ、迅雷、DNS等常用报文，得出通过单报文匹配速度与匹配精确度都很高。HTTP协议采用的是三次握手方式进行连接，在用户端向服务器端发送“GET”请求报 西南科技大学硕士研究生学位论文第39页文时，服务器对其进行回应，一般都是在这条流的第5个报文段。（2）多报文叠加匹配在当协议匹配模型进行提取到应用层数据后，当当前报文未能匹配成功时，等到第二个报文来时，则将前一个没有匹配的报文与第二个报文结合进行匹配，用类似的方法依次对余下的报文进行匹配。匹配模式如图3-16所示。该匹配模型在精确度上匹配性很高，但是匹配速度上达不到要求，最坏情况下，同一条流的前面的报文从开始就一直进行反复匹配，降低了匹配速度。比如Linux系统自备的L7-fliter采用的匹配方式就是该方法，在其协议全部开启匹配时，主机CPU资源占用在90%以上[51]。报文头1应用层信息1报文头2应用层信息2报文头3应用层信息3报文匹配数据应用层信息1应用层信息1应用层信息2匹配引擎匹配引擎匹配结果无法匹配匹配成功图3-16多报文叠加匹配Figure3-16Overlaymultiplepacketsmatchingmode（3）多个报文一次性匹配方法是将到的报文存储到一定的数量之后再送入到匹配引擎进行匹配。如果匹配成功，则同一条流的后续报文则不再需要匹配，否则判断该流为无法识别的流类型。如图3-17所示。报文头1应用层信息1报文头2应用层信息2报文头3应用层信息3报文匹配数据应用层信息1应用层信息2匹配引擎匹配引擎匹配结果匹配成功图3-17多个报文一次匹配Figure3-17Multiplepacketsmatchingonetime 西南科技大学硕士研究生学位论文第40页通过对现有主流协议的分析，基于正则表达式的深度包检测技术识别引擎在原理上可以识别现有的[52]、已探知的协议，但是基于表达式的复杂性，常规的匹配引擎在资源占用与时间消耗上都不如人意，因此在在匹配引擎上需要改进。DPI匹配引擎上在现有技术上分为RepeatedScan算法与One-PassScan算法[53]。这里我们主要讨论One-Pass扫描算法。One-Pass扫描算法对每一个送入匹配引擎的报文都记录其当前匹配的状态，下一个到来的报文则根据前一个的匹配状态进行匹配。随着报文的匹配开始至结束，DFA可以在任何输入位置进行特征识别，对于未匹配成功的当前状态无需在下次匹配时进行重复匹配。采用One-Pass扫描算法即可以弥补对上面提及的单报文匹配方式在跨报文匹配方面的不足，确保了匹配速率，同时又可以缩短多报文叠加匹配所消耗的时间，One-Pass扫描过程如图3-18所示。下面我们将One-Pass扫描算法与上述三种匹配方式想结合进行测试比对，选择最优算法应用于本文。报文头1应用层信息1报文头2应用层信息2报文头3应用层信息3报文匹配数据应用层信息1应用层信息2应用层信息3匹配引擎匹配引擎匹配结果匹配1失败匹配1失败匹配2成功匹配1失败匹配2成功匹配3失败图3-18One-Pass算法示意Figure3-18One-Passalgorithmindicate1.1测试实验2.1匹配方式选取本文采用DARPA数据[54]集进行匹配方式测试大约80M的数据，包含了201219报文。实验采用主机为2G内存，AMD5000，昂达A78GT。用C语言进行编程测试其匹配性能，匹配函数采用标准的RegEx函数，匹配方法为上面三种匹配方式与One-Pass扫描算法的结合。在这里我们定义了多个报文一次性匹配的个数为8个。由图3-19与表3-8可知单个报文一次性匹配在速 西南科技大学硕士研究生学位论文第41页率与准确性上表现突出；对于一些具有首锚与尾锚的协议多报文一次匹配的精确度迅速下降，因为报文数的控制是关键，但是却十分难确定，对于复杂的网络环境不能适应。而对于多报文叠加以为需要对前一个未匹配的报文继续匹配，在时间消耗上过高，达到了28.5秒的时间。所以本文我们采取了单报文匹配与One-Pass扫描算法相结合的方式来完成匹配。下节是对算法的整体性能测试。302520151050单个报文一次多个报文叠加多个报文一次图3-19匹配时间比较Figure3-19Comparisonofmatchtime表3-8匹配准确性比较Table3-8Matchtheaccuracyofthecomparison匹配方式QQTelnetSMTPFTPHTTPVNC单报文一次21061504083453多报文叠加01061503683453多报文一次010515030834001.1算法整体效果评估本章前面几节对算法进行了整体描述，并且对匹配方法进行了比对实验，这节我们对算法进行整体的测试，评估其性能。本文实验采用70条随机提取的L7-fliter规则与147条Backdoor.rules进行算法参数分析。参数确定方面根据Sornt规则集中大约有30%的表达式Ex大于0.5,并且实验在研究了mDFA分群算法后，在0.5、0.6、0.7三个参数值之间经过数次实验，最终将参数δ与参数η分别定义为0.5与0.7，且将组合后状态数上限 西南科技大学硕士研究生学位论文第42页#S（Combinationexpression）定义为几个不同的值（下限为4000），以L7-filter规则集及Backdoor.rules作为模式集，比较他们之间产生的DFA状态数，如图3-20所示。通过实验结果，#Sc为8000时，状态数变化率为由高到低临界点，故#Sc=8000作为基于动态参数的确定性有限状态机DPDFA(DynamicParametersDFA)算法的组合状态上限。26242220L7.rulesBK.rules181614121086468101214161820#S上限（1x1000）图3-20不同参数的状态数Figure3-20Statethenumberofdifferentparameters对于算法整体效果测试上，通过Snort2Bro生成403条HTTP与规则80条FTP规则，图3-21是DPDFA与多个现有算法对FTP与HTTP规则集在空间占用率上的比对，由于HTTP规则集较大，DFA需要的空间大于2G，没有在对比图中给出，但是DFA拥有最好的匹配效果；结果表明，在资源占用方面，DFDFA比同为分组运算的mDFA算法降低了43%左右。11000100009000HTTPFTP800070006000500040003000200010000mDFAD2FACD2FAXFADPDFA图3-21算法空间复杂度Figure3-21Spacecomplexityofthealgorithm 西南科技大学硕士研究生学位论文第43页当数据达到1G的时候，DFA的匹配时间只需要7.2s，图3-22分别为DPDFA与多个现有算法对FTP与HTTP规则集进行时间复杂度实验。结果表明，DFDFA比同为分组运算的mDFA匹配时间增加50%左右；由于表达式数量与复杂度原因，D2FA默认迁移边数增加，花费在匹配上时间也高出DPDFA近130%。60HTTPFTP 50403020100mDFAD2FACD2FAXFADPDFA图3-22算法时间复杂度Figure3-22Timecomplexityofthealgorithm1.1本章小结本章所介绍的算法是本课题的核心。我们对正则表达式算法进行了系统的分析，对算法的优化及改进进行了充分介绍。算法的改进是基于在限状态机的基础上改进的，通过对正则表达式进行重组与切片产生DFA，设定动态值，有效的避免了状态数的膨胀与歧义匹配，在匹配方式上采用One-Pass扫描算法，保证了报文匹配精确度与速度。 西南科技大学硕士研究生学位论文第44页4NetFPGA流量分类器的实现通过前面几章的介绍，选用基于动态参数修改的正则表达式算法进行流量的识别能很好的保障协议匹配的精度与速度。然而根据第二章对NetFPGA的分析，我们可以在参考模型中的User_data_path中自定义流量分类模型，实现对网络数据的提取、分析与分类。所以本章将对整个自定义分类模型在NetFPGA上的实现进行详细分析。1.1NetFPGA数据通道设计在对NetFPGA开发过程中，我们发现能够在NetFPGA只通过使用C代码就能够完成相应功能的实现。在NetFPGA上提供了一个线程平台(NetThread)，包含了2个CPU，每个CPU可以控制4个线程。线程间的调用没有上下文切换开销，表4-1为NetThread与PowerPC的对比[55]。而对于在该平台进行设计，参考数据通道也有相应的变换。相较于参考数据通道中，有8条输入队列连接到输入仲裁模块，分别是4条CPURxQ与4条MACRxQ，在线程平台中唯一的变化是只有1条CPU输入队列，其余3条发送的数据将不会被线程平台接受。针对该特点我们对网络流量分类系统的逻辑框架设计如图4-1所示，将参考数据通道中OutputPortLookup模块用自定义的分类系统来替换。下面几节我们将对模块的实现进行详细的介绍。表4-1NetThread与PowerPCTable4-1NetThreadandPowerPCNetThreadPowerPC软核硬核125MHz125MHz或者250MHz8线程单线程独立的输入与输出缓存单个输入输出缓存（零拷贝）片外存储片上存储 西南科技大学硕士研究生学位论文第45页图4-1数据通道框架Figure4-1DataChannelFramework1.1网络流量分类器整体框架2.1分类器设计指标L7-filter为Linux下的一款协议识别系统，它采用基于正则表达式的协议识别技术，且它作为Netfilter／Iptables上一个开源代码软件[56]备受瞩目，其主要也是基于应用层协议识别来完成对流的分类。当对报文解封后，通过各层偏移量来剔除各层信息保留报文应用层的数据，最后以正则表达式产生NFA实现对数据的匹配，匹配的对象为应用层协议特征。但是基于正则表达式规则的匹配在资源消耗方面与时间消耗方面很难达到一个平衡点，依靠PC主机来实现这一工作，显然需要开销很多CPU资源。在网络应用不断膨胀的当下，很难保证其性能。对于任意一个分类系统都存在多个指标对其进行衡量，且各个指标之间往往存在相互制约关系，一个指标的提高通常情况下都会影响到其他指标。因此，设计分类系统需要考虑各个方面的因素，主要包括以下几个方面：（1）准确性。指分类系统是否能够在制定环境下准确的识别应用层协议的能力。良好的分类系统应该在漏报率与误报率方面有很好的控制。即前面章节提到的假正与假负（FN、FP），指采集到被模型错误分类的样本数量与指将非本类型的样本预测为本类型的样本。具备很好的准确性是流量分类系统最基本的要求，这个也是我们采用正则表达式来实现流量分类而不使用端口识别结束的原因。 西南科技大学硕士研究生学位论文第46页（2）吞吐量。指流量分类系统能够在线实时处理的链路带宽。该系统主要应用环境包括：带宽管理、IDS／IPS、入侵检测等，这就要求所设计的分类系统具备能够在高速网络上在线处理网络流量。吞吐量是分类系统的主要性能指标，重点提升系统的吞吐量来迎合时刻增长的带宽是系统设计主要方向。（3）灵活度。流量分类系统维护的难度，即写入新规则的复杂度。随着Internet与网络应用的发展，基于互联网的新业务迅速增多，新的协议类型也在不断涌现。一个好的分类系统需要适应不断变化的环境，对新规写入方面一定要做到方便、快捷。1.1整体框架设计本文在NetFPGA上设计一个整体的网络流量分类器主要包含了以下几个模块：（1）输入与输出模块：根据需要及要求对进入的流实施相应的处理。输入控制模针对非分片的报文，需要对报文的首部与报文体进行分离，推送到下一个对应模块即报文管理模块与流管理模块；针对分片报文，因为五元组信息可能存在一个独立的报文中，而报文进入的时候可能是无序状态，需要对其进行缓存，等待后序报文到达之后再进行分类。将报文包含的五元组信息送入到流管理模块，其余报文体送入到报文管理模块。（2）流管理模块：对不同的流类型进行区分，保证所有的匹配工作室基于流的。流管理模块采用FIFO存储方式，确保报文体与报头对应关系。当流管理模块对推送的报头五元组进行接收后，进行散列访问流表，表中存储了该条流的状态等信息，根据流表模块推送的信息来决定将信息推送到输出控制模块或者是协议识别模块。（3）报文管理模块：与流管理模块相同，都采用相同FIFO存储方式，该模块用于缓存送入的报文体，根据流管理模块的推送信息进行相应的处理。（4）协议匹配模块：根据匹配引擎对应用层信息进行规则匹配，识别其协议类型。并将匹配信息送入流管理模块，为流管理模块提供处理决策，并更新流表信息。通过对模块功能的分析，我们根据要求构建了相应的框架如图4-2所示。 西南科技大学硕士研究生学位论文第47页图4-2整体框架组建Figure4-2Overallframeworkestablished1.1输入控制模块本文设计流量管理模块用于对流进行初级处理。一条网络数据流经过MAC控制器流如数据输入控制模块，模块对其进行报文拆分并提取信息，分离报头与报文体数据，然后推送到流管理模块和报文体管理模块。该模块主要包括输入控制子模块、输出控制子模块和分片重组子模块，结构如图4-3所示。图4-3输入控制模块Figure4-3InputControlModule在提取缓冲区中存放的完整报文，根据报头中分片信息判断该报文是否为分片报文，如果是则推送到重组子模块，否则将报文送入到下一个模块即 西南科技大学硕士研究生学位论文第48页输出控制子模块。然后拆分报文，将报头与报文体送入到对应的FIFO，供后续处理，同时需要保证FIFO中的报头与报文对应无误。在Netthread中通过函数voidnf_pktin_init()初始化10个报文缓存，每个缓存的大小为1600Byte。1.1流管理模块流管理模块从报文体FIFO读取报头并提取五元组信息（五元组对于每一条流都是必要元素，只是在组成流的报文之间存在时间的差异；这里的五元组包括：源IP地址、源端口号、目的IP地址、目的端口号和IP层协议。）用以区分不同的流，同时维护一个流表，并根据流表信息来定义报文体的下一步输出方向。该模块包括报头处理、流表管理以及外部控制三个子模块。其结构如图4-4所示。图4-4流管理Figure4-4FlowManagement（1）管理模块主要任务包括对报文中五元组预处理任务流程与流处理超时任务。这里我们重点对五元组的处理流程进行分析：①通过计算五元组的hash值，然后根据hash值查找hash表。假如未能到对应表项，则跳转到阶段二继续执行，否则跳转到阶段三继续执行。②从链表管理中申请一个空闲ID分配给需要处理的五元组任务进程，若发现空闲ID号，则将hash值加载到hash链表中，并将流节点中的有效信息与报文挂载到相应的进程中。若在空闲链表管理中找不到空闲ID号，则表示系统所能支持的流量数量已经达到极限，导致五元组分类失败。 西南科技大学硕士研究生学位论文第49页③根据计算出的五元组的hash值查找相应的地址，从第一个hash表开始进行查找，若该表项五元组值和到已送达的五元组值相等，则返回该表项的地址。否则，依次比较并对下面表项进行查找，若能找到与之匹配对象，则跳转到阶段四；假如已到链表末尾仍不能找到匹配项，则跳转到阶段五。④向流状态管理与流超时管理机制推送更新消息，并将表项的地址值作为返回值用以匹配的流标识，且算法中止。⑤若在空闲链表管理中还有未使用的空闲ID号，则从空闲链表管理中申请一个空闲流标识，并将hash值写入hash链表中最后一个表项，并将该流的节点信息与报文进行挂载。同时向流超时管理机制与流状态管理机制推送建立消息，用以建立新的表项，且算法结束。假如空闲链表管理中已经没有空闲ID号，则表示系统所能支持的流量数量已经达到极限，导致五元组分类失败。（2）流量分类系统基于流而非基于报文，流管理模块则是协议分类识别的前提。本方案按照采集到的报文的五元组计算hash值将流构成链表，方便流的定位与查找。如图4-5所示。图4-5流链表Figure4-5Flowlist①Hash表：建立Hash表的主要目的是为了消除遍历搜索键带来的时间消耗，通过特定函数计算hash值定位表项地址用来存储指针，方便后续查找、处理。表中的指针用来指向五元组（源目的IP地址、源目地端口号、协议类型、流状态等）。②流结点：对报文的基本状态信息进行存储，包括流的五元组、协议号、流的状态、已到达报文数量、报文已成功匹配个数、超时值、上一个流 西南科技大学硕士研究生学位论文第50页指针、下一个流指针等信息，具体的含义如下：五元组：即源目IP地址、源目的端口和传输层协议号。hash表中包含一个或者多个流结点，对已保存的五元组将作为作为流的标识。流状态：这里的状态主要分为三种：无法识别的流、未进行识别的流、已识别的流。协议号：对已识别协议的流分配其协议自定义编号。已到达的报文个数：计算该条流上己到的报文数量。已匹配的报文个数：无论匹配成功与否，只要成功送入匹配引擎进行匹配的报文数量。超时值：通过数值的变化判别一条流是否因超时而引起的结束。通过设置超时范围，任务定时对该值递减1，每重新到达一个新报文，该数值则恢复初始值，继续处理。③报文：流结点上挂载的报文。当流状态转向“未进行识别”状态时，才可以进行报文的挂载，所以挂载的报文一般为一条新的流的前几个报文。其挂载流程如图4-6所示。挂载完成之后将报文推送到匹配引擎进行协议匹配。报文挂载到流结点时，已到达节点的报文数量加l，超时值也修改成初始值。Hash运算YN是否为新节点？创建新节点是否识别？识别无法识别尚未识别挂载报文修改已到报文数并送出挂载报文修改已到报文数并送出图4-6新报文处理流程Figure4-6Newmessageprocessing（3）Hash函数的计算过程是定义了一个16位数组，将源IP与目的IP的高16位与低16位执行异或，得到的值存放在16位数组中。将定义的数组内容相异或得到16位的值“a”，最后将高6位于2-7位异或，将低10位的值作为索引值。在处理Hash表冲突的方法可以分为：开放寻址法、再散列法、链地址法（拉链法）及建立一个公共溢出区。以拉链法解决冲突的做法 西南科技大学硕士研究生学位论文第51页是：将经过Hash计算之后得出的相同Hash值的关键字挂载到同一个单链表中，且以数组指针的形式存放。这里选定的散列表长度为256k，然后将散列表定义为一个由256k个头指针组成的指针数组T[0,255k]。凡是散列地址为i（0≤i≤255k）的结点，均一并插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于1，但一般均取α≤1，这里取α<1。如图4-7所示。0关键字Λ关键字Λ关键字关键字关键字Λ255K图4-7拉链法Figure4-7ZipperAct1.1报文管理模块与输出控制模块报文体管理模块将对报文体FIFO的数据进行管理和读取。针对流管理模块推送来的信息，对于不同报文进行相应的处理，将无法识别的流从FIFO中提取属于这条流的完整信息，推送到输出控制模块待下一步处理；否则，推送报文体进入匹配引擎进行协议识别。在NetThread中发送的数据包需要在输出存储器中填写报头信息与有效载荷。因为最终需要在NetFPGA硬件上发送数据，而硬件只能发送存储在存储器中输出的数据包。调用函数voidnf_pktout_init()实现初始化工作，再将流管理模块中报头信息与报文体相结合并输出，最后返回1600字节的长度空间，最后调用t_addrnf_pktout_alloc(uintsize)*发送数据包。 西南科技大学硕士研究生学位论文第52页1.1协议识别模块2.1协议特征提取根据本文设计的系统，协议识别模块采用正则表达式来实现对应用层协议特征的识别，判断其协议类型。怎样定义正则表达式，与分类效率有着密切关系。所以在确定协议的规则表达式方面，需要满足以下几点：（1）保持较低的假阳性即FP。尽量降低把非类型a的样本预测为类型a的样本的比例。（2）保持较低的假阴性即FN。降低将类型a的样本被预测为非类型a样本的比例，降低漏报率。（3）从每个流的开始阶段进行特征提取。将特征选取选在交互的开始阶段，即可以减少匹配对象的报文数量，提高匹配报文速度。（4）选择规范、简洁的规则表达式。在保持较低的FN与FP的前提下，尽量选用采取简单正则表达式，在降低资源占用率的情况下又提高了算法效率。协议特征提取我们选用wireshark来对现有协议进行提取、分析及总结。（1）对于标准的协议，如SMTP、HTTP、FTP等协议，对其进行总结归纳。这里用采集到的FTP协议来阐述：当客户端发送的消息被服务器接收时，会发现其应用层首字节包含字符串“220”，然后服务器在字符串“220”之后会发送其他字符，且必定包含了字符串“ftp”。所以服务器将使用ASCII的可打印字符添加在“220”和“ftp”之间。因此，用正则表达式来表示”ftp”协议特征为：^220[x09-x0d-~]*ftp。（2）对于某些私有协议，则需要对其在实际交互过程中，应用层包含字符的表现形式进行大量提取、分析和总结。例如腾讯的QQ协议，众所周知QQ版本一年一换，采用前人总结的协议特征来分析当下的版本，不具有说服力，所以本文通过长时间捕获其数据，分析其总体特征。最后我们发现，在使用QQ协议时，其应用层报文的前三个字节中必有一个是字符串“02”，且以字符串“03”结尾，如图4-8所示。用正则表达式对其特征进行描述为：^.?.?x2.+x03$。 西南科技大学硕士研究生学位论文第53页图4-8QQ协议应用层报文特征Figure4-8QQapplicationlayerprotocolpacketsfeature（3）在现有的相关资料中选定正则表达式。例如Linux系统专用的L7-Filter在截止统计之前存在114条协议规则。在定义的128条规则中，可以通过匹配效果将其分为5类。如表4-2所示。总结可得还有少量协议在匹配效果上表现不佳，FN与FP都相对较高。表4-2L7-Filter协议匹配效果分类Table4-2L7-Filterprotocolclassificationmatchresults匹配效果协议数量协议类型Great18DnsFtpHttpSSH......Good57BittorrentQQXunlei.....Yahoo...OK27KugooRloginSip.....Normal10RtpTftpHotline.....Poor2Freenetliveforspeed在实际的操作中，为了更好的构造表达式，我们综合运用上述三种方法。 西南科技大学硕士研究生学位论文第54页1.1协议匹配规则匹配模块的功能包括下面几个步骤。从主机读取配置文件，对表达式进行DFA编译，将状态转换表写入到NetFPGA的SRAM中。如图4-9所示。开始ReadRegExp();CompileRE();WriteRule();结束图4-9规则配置流程Figure4-9RuleConfigurationProcess（1）这里使用函数ReadRegExp()函数进行配置文件的读取。配置文件以protocol.config命名。#表示注释，用以标识协议类型，具体格式如图4-10所示。本文用DFA_Struct数据结构来存储最终生成的表达式DFA。如图4-11所示。#QQ^.?.?x02.+x03$ #ftp^220[x09-x0d-~]*ftp图4-10文件格式Figure4-10Fileformat 西南科技大学硕士研究生学位论文第55页Typedefstruct_DFA_struct{ intProNum;intDFAstateCout; MODEPro[MAX_PROTOCOL]; }DFA_struct;图4-11DFA_Struct结构Figure4-11DFA_Structformat这里用将据结构MODE用以保存协议表达式、特征字符串以及它的长度，格式如图4-12所示。Typedefstruct_MODE{ charpattern[]; charprotocol[]; intRegLength; }MODE;图4-12MODE结构Figure4-12MODEformat（2）本文用CompileRE()函数来完成表达式DFA的编译。具体流程图如图4-13所示。开始调用Init();表达式切片删除重复项获取NFA组建状态表ReadRegExp();寻找空边创建DFARE_process();合并表达式删除空转移结束图4-13构建DFA流程Figure4-13BuildingtheDFAprocess①函数Init()实现NFA与DFA状态转换表初始化。②读取表达式，检测正则表达式是否符合语法规则。 西南科技大学硕士研究生学位论文第56页③③本文设定Get_Group与Cut_Reg()函数完成表达式的组合与切片，降低最终生成的DFA状态数；使用Thompson算法构造NFA，然后使用标准子集构造法寻找空转移、删除空路径与重复状态方法构建DFA。（3）将函数将状态转换表写入到SRAM中。如图4-14所示。DFACreatTable();nf2c_ioctl();YSRAM忙？N写入SRAM结束图4-14状态表写入SRAM流程Figure4-14WriteSRAMflowstatetable本文使用staticintnf2_ioctl(structnet_device*dev,structifrep*rp,intcmd)函数完成NetFPGASRAM的读写功能。这个三个参数分别代表网络设备、地址信息与操作标示符，nf2_ioctl函数中的cmd包括SOCKETREAD与SOCKETWRITE两个选项，即读寄存器与写寄存器。当一条新报文到来时，协议匹配工作原理是根据当前的输入查找当前的状态来确定下一个状态的过程，在无法识别与识别成功的条件下终止匹配工作。具体工作过程如下：匹配的初始状态为0，开始于新报文首个字节，当每次有数据输入时，需要对当前状态左移8位，在尾部添加当前字节，从而得到下一个状态转换表的地址，并进行匹配。同时需要判断获取的状态是否为协议的尾部。如果已经识别出某个流的协议，即协议号的值在[0,0xe]区间里面，然后判断报文尾锚标志与表中的尾锚值的大小关系，来确定报文是否继续进行匹配，直到匹配失败或者已经匹配到报文的结尾。匹配的流程如图4-15所示。 西南科技大学硕士研究生学位论文第57页新报文初始状态0Y报文是否结束？NYN是否为最后最后一个字节？下一状态=[0,0x1ffff]?N无法识别下一状态=[0,0x1fff]?N无法识别YYY协议号=[0，0xe]?N协议号=[0，0xe]?N无法识别尾锚=0？N当前字节加1Y Y识别识别图4-15匹配过程Figure4-15Matchingprocess匹配的的整个过程发生在SRAM中，根据在SRAM中维护的状态转换表进行匹配。SRAM的总共有2M项，每项18位，分别为13位的状态ID、4位协议号与1位的结束符。每一项的内容在表4-3中给出。表4-3表项内容Table4-3Entriescontent名字段位意义结束符[0:0]尾锚协议号[1:4]可以识别15个协议状态ID[5:17]定义状态数为8192报文匹配引擎通过与SRAM交互数据完成识别工作，由于匹配引擎在整个框架中耗时较长，且任务繁重，这里我们开辟4个线程来实现协议的匹配工作，通过函数intnf_tid()返回当前的线程ID号来调用线程。如图4-16所 西南科技大学硕士研究生学位论文第58页示，对于没有尾锚标记的报文但又已实现匹配的报文，匹配引擎对其结果进行暂存，等待报文匹配结束之后送出匹配结果。匹配引擎SRAM匹配线程1匹配线程2报文匹配线程3……匹配线程42M*18图4-16匹配引擎示意图Figure4-16Schematicofmatchingengine1.1本章小结本章对基于NetFPGA流量分类系统模块设计进行了详细描述。在其数据通道中添加自定义的分类模块，包括：输入/输出控制模块，流管理模块、报文管理模块与协议匹配模块，并结合第三章采用的正则表达式算法，在网卡端实现对网络数据的采集、分类，避免纯软件实现带来的局限性。下一章节将对本文的设计进行比对实验，验证其可行性与优越性。 西南科技大学硕士研究生学位论文第59页5效果评估与分析1.1实验平台搭建本章将对分类系统的功能与性能进行实验验证。数据来源方面，本文选用了wireshark在网络环境进行抓包，生成标准PCAP文件后用于分类测试，包括了应用层大部分协议，数据包总量约128M。实验选用的硬件设施包括两个NetFPGA-1G开发板，4台PC主机，主机硬件为2G内存，AMD5000，昂达A78GT。PC0运行一个基于NetFPGA开发的发包器，PC1运行本文设计的流量分类系统，PC2上运行基于Libpcap开发的TCPdump，操作系统均为CentOS-5；PC3为WIN7，装载基于Winpcap开发的网络嗅探器5.5版本。测试环境的搭建如图5-1所示，不同协议所占用的比例在表5-1中给出。PC0PC1PC2PC3InternetNetFPGANetFPGA普通千兆普通千兆Wireshark图5-1实验环境Figure5-1Experimentalenvironment表5-1各类协议采集比例Table5-1Proportioncollectionofvarioustypesofagreements协议类型报文总数占用比例(%)总大小(MB)HTTP3676518.523.7QQ5482023.329.9VNC30371.92.5SMTP40782.53.2FTP39512.83.7Xunlei10183350.764.8 西南科技大学硕士研究生学位论文第60页1.1吞吐率测试测试过程为：将采集到的数据在PC0上以不同速率向PC1，PC2，PC3重复发送。实验结果如图5-2所示。NetFPGA上数据包的采集速度远远高于其他两个应用。网络嗅探器与TCPdump在发包速度大于12Mb时候，丢包率会大量增加。NetFPGA在对数据进行提取主要通过硬件实现，运用零拷贝技术，理论上可以达到千兆线速传输。1009080NetFPGAwinPcaplipPcap706050403020100510152025速度（Mbps）图5-2丢包率Figure5-2Lossrate分类器的吞吐率与前面章节提到了输入控制、输出控制及流管理模块等的代码编写有直接关系，本文采用了C语言实现，且只需要对报文的应用层进行分析、识别，报头信息不需要进行分析，实际传输速度在300Mb左右，但是也远远优于基于winpcap库开发的网络嗅探器5.5版本及libpcap库开发的网络嗅探器TCPdump。在实验过程中，我们发现NetFPGA存在少量丢包，主要原因是因为会话建立初期，硬件内部发生Hash冲突，或者因为网线原因，但是不影响分类系统的性能。1.2准确率测试测试过程为：将采集到的数据在PC0上向PC1，PC2，PC3上以10M速率下重复发送多次，主要检测考察三个分类器的TP与TN。例如，比较实际测试到HTTP协议数与Wireshark获取的HTTP协议数，实际测试不属于HTTP 西南科技大学硕士研究生学位论文第61页协议数与Wireshark获取的非HTTP协议数。测试结果如表5-2所示。由于其余两种纯软件分类器在速度大于12Mbps之后会出现大量丢包，所以表5-3只给出了本文设计的分类器在300Mbps速率下的TP与TN。表5-2三种分类软件准确率对比Table5-2ThreeclassificationaccuracycomparisonsoftwareTN(%)TP(%)协议类型NetFPGAWinLibNetFPGAWinLibHTTP97.6498.0298.0298.9798.7798.73QQ88.9988.5689.3395.3893.4792.11VNC98.1298.2397.5499.9399.3299.65SMTP98.9699.1298.8798.9897.9998.99FTP98.4597.6997.9099.2199.4299.22Xunlei99.3199.5199.4299.5499.5799.57表5-3识别准确率Table5-3Recognitionaccuracy协议类型TN(%)TP(%)HTTP97.6498.78QQ88.6193.31VNC97.8599.85SMTP98.8698.98FTP97.8599.01Xunlei99.0199.54准确率测试结果分析：1.1模式特征表达式不准确。正则表达式对匹配目标进行匹配时，需要进行大量工作提取特征字符串，它的准确性直接影响到匹配结果的精度。例如，。QQ准确度较低，造成此原因主要因为模式特征的表达式“^.?.?x02.+x03$”过于一般。1.2应用程序自身的干扰。现在的网络环境较为复杂，例如Xunlei、QQ会自动弹出广播消息，广告信息的投放，自动检测更新内容等。有这些软件 西南科技大学硕士研究生学位论文第62页集成的HTTP页面也会受到相应的干扰，造成统计数据不准确。所以，测试环境的不精确也是造成匹配精度下降的原因。图5-3为分类视图，其中对协议进行了分类，ID为1,2,4,8对应的协议类型依次是VNC,SSH,HTTP,QQ。图5-3实验结果视图Figure5-3Resultsview经过吞吐率与精确率测试实验，本文设计的基于NetFPGA的网络流量分类器在传输速率10Mbps以下的分类精度与基于纯软件实现的TCPdump和网络嗅探器基本一致。但是传输速率达到12Mbps以上时，传统纯软件开始出现大量丢包，无法对网络数据进行分类，而本文设计的分类器在300Mbps的传输速率时任然能够保持较高的分类精确率，具备一定的优越性。1.1本章小结实验分为了两个方面进行，一个是吞吐率在高速的环境下表现良好，远远超出了传统的分类软件；二是采用基于正则表达式的应用层协议特征分类确保了分类精度，保证了较高的真正与真负。 西南科技大学硕士研究生学位论文第63页结论网络流量分类技术的发展，对提高网络服务质量、监控异常网络、维护良好的网络环境起了举足轻重的作用。本课题的研究工作围绕流量分类技术发展过程中遇到的问题展开，首先对传统分类技术进行了分析，并总结出其技术特点与发展瓶颈，然后针对这些问题查阅文献，最后将研究工作聚焦到流量分类算法与分类器实现方式上，并在这两方面取得了一定研究成果。首先，分析了现有分类技术的优缺点，总结了其发展过程及所遇到的技术瓶颈，并阐述了NetFPGA平台技术，分析了其技术特点，寻找到他们之间的相关性。然后，分析了正则表达式分类算法特点并以此提出DPDFA算法。通过参数设定重组表达式及简化表达式结构，减少了匹配状态数与歧义匹配，同时将One-Pass扫描算法与单报文一次性匹配结合，提高报文匹配速度。最后通过比对实验验证了算法的可行性与优越性。其次，将通过Wireshark与L7-fliter数据库采集到的主流协议应用层文本特征信息用DPDFA算法进行编译，其状态转移表维护在NetFPGA的SRAM中，供后续分类使用。最后，根据NetThread技术特点及内置的参考路由模型架构，使用C语言在输入仲裁模块与输出端口查找模块之间自定义分类模块，在网卡端实现了对网络数据应用层信息的提取，并根据维护在SRAM中的状态转移表完成对协议的识别与分类。实验结果表明，分类器相较于传统分类技术在匹配速度与精度上都有较大幅度的提升，达到预期效果。本课题还存在大量需要继续完善的问题：在算法方面，正则表达式提供了一种灵活、高效的匹配语言。本文在对状态数膨胀方面进行了大量的研究，通过对规则表达式本身形式的控制与多个表达式重组后分片处理来降低状态数。但是在正则表达式中状态间迁移边数的控制与状态的存储方式改进也是必不可少的，这方面课题研究不多。NetFPGA方面，适用与该平台的分类算法有很多，需要进行大量的研究。怎样将NetFPGA实现的网络流量分类技术运用到骨干网络和网络安全领域也是课题后续需要研究的问题。本文在对NetFPGA进行研究以后发现，能够在此平台实现的网络应用还有很多，比如DRAM-Router、URL-Extraction、MonitoringSystem与Open-FlowSwitch等，这些都需要我们对它进行大量的研究，才能体现NetFPGA的价值。 西南科技大学硕士研究生学位论文第64页致谢我很荣幸成为了西南科技大学的研究生，我很感谢西南科技大学对我的培养，能够在图书馆找到一切需要的学术文献。实验室良好的学术氛围让我在学术上遇到困难时很好的与同学进行交流。祝实验室永创辉煌！感谢我的导师周金治老师，从我入学到现在您给我很大的帮助，提供了良好的实验环境，让我领悟到学习与生活中的很多道理。我的论文是在您的悉心指导下完成的。您渊博的专业知识，严谨的治学态度，精益求精的工作作风，诲人不倦的高尚师德，严以律己、宽以待人的崇高风范，朴实无华、平易近人的人格魅力对我影响深远。从我选题到发表论文再到现在，您对我论文的指导让我充分感受到您为我付出的心血，虽然在这个过程中我有时候想要放弃，但是您都不会责怪我，每次都用很平静的态度给我解答我遇到的问题，鼓励我。在此，谨向周老师表示崇高的敬意和衷心的感谢！祝您在科学的道路上取的更大的成绩，生活美满幸福。感谢实验室的同学们，他们陪我共同度过了美好难忘的大学生涯的最后阶段，我非常珍视和你们的友谊！祝你们前程似锦，事业有成！感谢我的父母，是他们给予了我最无私的爱，为我的成长付出了许多许多，惟愿他们健康长寿！感谢学院的领导对我学习的大力支持，是你们提供给我这样宝贵的学习经历，让我在学习过程中成长。祝愿你们工作顺利，事业腾达！最后，感谢各位评阅老师对我提出的宝贵意见，让我更全面的认识自己的不足！ 西南科技大学硕士研究生学位论文第65页参考文献[1]黄澄清,云晓青,刘欣然,等.2013年中国互联网网络安全报告[R].北京.中国互联网信息中心.2014.4[2]林闯,王元卓,任丰原.新一代网络QoS研究[J].计算机学报,2008,31(9):1525-1535.[3]黄勤,龚海清,刘金亨,等.基于改进的遗传神经网络入侵检测系统[J].重庆理工大学学报自然科学版,2010,24(2):83-86.[4]代丽.DFI流量分类技术的研究和实现[D].北京邮电大学,2011.[5]龚亮亮.基于NetFPGA的网络安全通信[D].吉林大学,2011.[6]陈曙晖.基于内容分析的高速网络协议识别技术研究[D].长沙:国防科学技术大学,2.1[7]KimH,ClaffyKC,FomenkovM,etal.InternetTrafficclassificationdemystified:myths,caveats,andthebestpractices[C].Proceedingsofthe2008ACMCoNEXTconference.ACM,2008:11.[8]Snort[OL].http//www.Snort.org,2013.2.16[9]李彬.基于NetFPGA的网络流量分类[D].电子科技大学,2011.[10]BymaS,SteffanJG,ChowP.NetThreads-10G:SoftwarepacketprocessingonNetFPGA-10Ginavirtualizednetworkingenvironmentdemonstrationabstract[C].FieldProgrammableLogicandApplications(FPL),201323rdInternationalConferenceon.IEEE,2013:1-1.[11]MinSH,KimBC,LeeJY.NetFPGA-BasedSchedulerimplementationforresourcevirtualizationoffutureinternettestbed[C].ICTConvergence(ICTC),2011InternationalConferenceon.IEEE,2011:597-602..[12]ZhangK,DingX,XiongK,etal.ReconfigurableSecurityprotectionsystembasedonNetFPGAandembeddedsoft-coretechnology[C].ComputerDesignandApplications(ICCDA),2010InternationalConferenceon.IEEE,2010,5:V5-540-V5-544.[13]AntichiG,GiordanoS,MillerDJ,etal.Enablingopen-sourcehighspeednetworkmonitoringonNetFPGA[C].NetworkOperationsandManagementSymposium(NOMS),2012IEEE.IEEE,2012:1029-1035.[14]斯坦福大学.NetFPGA官网[OL].http://www.netfpga.org,2013.2.16[15]罗力凡.基于VHDL的FPGA开发快速入门.技巧.实例[M].北京:人民邮电出版社， 西南科技大学硕士研究生学位论文第66页1.1[16]林金,杨波.基于NetFPGA的网络流量采集器[J].济南大学学报:自然科学版,2011,25(1):6-10.[17]NetFPGA使用手册[OL],北京理工大学.http://www.docin.com/p-4818769,thml.2.1[18]AntichiG,GiordanoS,MillerDJ,etal.Enablingopen-sourcehighspeednetworkmonitoringonNetFPGA[C].NetworkOperationsandManagementSymposium(NOMS),2012.IEEE,2012:1029-1035.[19]RubowE.PacketProcessingwithPowerPContheNetFPGA[J].2009.[20]熊刚,孟姣,曹自刚,等.网络流量分类研究进展与展望[J].集成技术,2012,1(1).[21]DainottiA,PescapeA,ClaffyKC.Issuesandfuturedirectionsintrafficclassification[J].Network,IEEE,2012,26(1):35-40.[22]A.Blum,P.Langley.Selectionofrelevantfeaturesandexamplesinmachinelearning.ArtificialIntelligence,97(1-2):245–271,1997.[23]ZanderS,ArmitageG.PracticalmachinelearningbasedmultimediatrafficclassificationfordistributedQoSmanagement[C].LocalComputerNetworks(LCN),2011IEEE36thConferenceon.IEEE,2011:399-406.[24]李国平,王勇,陶晓玲.基于DPI和机器学习的网络流量分类方法[J].桂林电子科技大学学报,2012,32(2):140-144.[25]LiuT,SunY,GuoL,etal.ImprovingmatchingperformanceofDPItrafficclassifier[C].Proceedingsofthe2011ACMSymposiumonAppliedComputing.ACM,2011:514-519.[26]殷珍珍.基于正则表达式的多模式匹配算法研究[D].杭州电子科技大学,2012.[27]杨毅夫,刘燕兵,刘萍,等.正则表达式的DFA压缩算法[J].通信学报,2009,30(10):36-41.[28]ValgentiVC,ChhuganiJ,SunY,etal.GPP-Grep:high-speedregularexpressionprocessingengineongeneralpurposeprocessors[M].ResearchinAttacks,Intrusions,andDefenses.SpringerBerlinHeidelberg,2012:334-353.[29]BecchiM,CrowleyP.A-dfa:Atime-andspace-efficientdfacompressionalgorithmforfastregularexpressionevaluation[J].ACMTransactionsonArchitectureandCodeOptimization(TACO),2013,10(1):4.[30]QuJ,ZhaoR,LiuP,etal.AdelayedinputDFAoptimizedalgorithmofboundingdefaultpath[C].ComputerScienceandAutomationEngineering(CSAE),2011 西南科技大学硕士研究生学位论文第67页IEEEInternationalConferenceon.IEEE,2011,4:702-705.[31]徐乾,鄂跃鹏,葛敬国,等.深度包检测中一种高效的正则表达式压缩算法[J].软件学报,2009,20(8):2214-2226.[32]金军航,张大方,黄昆.高性能正则表达式匹配算法评估[J].ComputerEngineering,2010,36(19).[33]刘鹏,姚远,邰铭,等.一种高效匹配PCRE的扩展自动机[J].计算机工程,2010,36(12):39-42[34]KongS,SmithR,EstanC.Efficientsignaturematchingwithmultiplealphabetcompressiontables[C].Proceedingsofthe4thinternationalconferenceonSecurityandprivacyincommunicationnetowrks.ACM,2008:1.[35]柳厅文,孙永,卜东波,等.正则表达式分组的1/(1-1/k)-近似算法[J].软件学报,2012,23(9):2261-2272.[36]WangK,QiY,XueY,etal.ReorganizedandCompactDFAforEfficientRegularExpressionMatching[C].Communications(ICC),2011IEEEInternationalConferenceon.IEEE,2011:1-5.[37]MeinersCR,PatelJ,NorigeE,etal.FastregularexpressionmatchingusingsmallTCAMsfornetworkintrusiondetectionandpreventionsystems[C].Proceedingsofthe19thUSENIXconferenceonSecurity.USENIXAssociation,2010:8-8.[38]KumarS,ChandrasekaranB,TurnerJ,etal.Curingregularexpressionsmatchingalgorithmsfrominsomnia,amnesia,andacalculia[C].Proceedingsofthe3rdACM/IEEESymposiumonArchitecturefornetworkingandcommunicationssystems.ACM,2007:155-164.[39]YuanY,PengL,ZhengZ,etal.AnExtendedAutomatatoEfficientlyMatchCountingConstraintsPatterns[C].E-BusinessandE-Government(ICEE),2010InternationalConferenceon.IEEE,2010:2018-2022.[40]M.Becchi,P.Crowley.AnImprovedAlgorithmtoAccelerateRegularExpressionEvaluation[A].In:ANCS2007[C].Orlando,USA,2007:145-154.[41]ShijinKong,RandySmith,CristianEstan.EfficientSignatureMatchingwithMultipleAlphabetCompressionTables[A].In:SecureComm2008.Istanbul,Turkey,2008.[42]张树壮,罗浩,方滨兴,等.一种面向网络安全检测的高性能正则表达式匹配算法[J].计算机学报,2010,33(10):1976-1986. 西南科技大学硕士研究生学位论文第68页[43]PaoD,OrNL,CheungRCC.Amemory-basedNFAregularexpressionmatchengineforsignature-basedintrusiondetection[J].ComputerCommunications,2013,36(10):1255-1267.[44]GuoD,BhuyanLN,LiuB.AnefficientparallelizedL7-filterdesignformulticoreservers[J].IEEE/ACMTransactionsonNetworking(TON),2012,20(5):1426-1439.[45]NakaharaH,SasaoT,MatsuuraM.Aregularexpressionmatchingcircuitbasedonadecomposedautomaton[M].ReconfigurableComputing:Architectures,ToolsandApplications.SpringerBerlinHeidelberg,2011:16-28.[46]LinzP.Anintroductiontoformallanguagesandautomata[M].Jones&BartlettPublishers,2011.[47]KohaviZ,JhaNK.Switchingandfiniteautomatatheory[M].CambridgeUniversityPress,2010.[48]YuX,BecchiM.ExploringdifferentautomatarepresentationsforefficientregularexpressionmatchingonGPUs[C].Proceedingsofthe18thACMSIGPLANsymposiumonPrinciplesandpracticeofparallelprogramming.ACM,2013:287-288.[49]BecchiM,CrowleyP.A-DFA:ATime-andSpace-EfficientDFACompressionAlgorithmforFastRegularExpressionEvaluation[J].ACMTransactionsonArchitectureandCodeOptimization(TACO),2013,10(1):4.[50]邓凯元,姜磊.正则表达式匹配引擎性能分析[J].计算机与现代化,2011(7):105-107.[51]林平.网络流量的离线分析[D].北京邮电大学,2010.[52]TremblayM,KelouwaniS,MelinE.Methodandsystemforidentifyinganapplicationtypeofencryptedtraffic:U.S.Patent8,539,221[P].2013-9-17.[53]王杰,石成辉.基于正则表达式的动态应用层协议识别方案[J].计算机工程与应用,2010,46(18):103-106.[54]SalmonG,GhobadiM,GanjaliY,etal.NetFPGA-basedprecisetrafficgeneration[C].Proc.ofNetFPGADevelopersWorkshop.2009,9.[55]胡婷,王勇,陶晓玲.网络流量分类方法的比较研究[J].桂林电子科技大学学报,2010,30(3):216-219.[56]SeokHongMinNetFPGA-basedschedulerimplementationforresourcevirtualizationofFutureInternettestbed[c].2011 西南科技大学硕士研究生学位论文第69页攻读学位期间发表的相关学术论文及研究成果[1]邓悄，周金治.基于NetFPGA的网络数据包重现机制的研究与实现[J].科学技术与工程.2014.14(2).205-210