基于子图同构的XFA压缩算法设计

《基于子图同构的XFA压缩算法设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代号10532学号S11102055分类号TP393密级硕士学位论文基于子图同构的XFA压缩算法设计学位申请人姓名刘哲培养单位信息科学与工程学院导师姓名及职称林亚平教授学科专业计算机科学与技术研究方向信息安全论文提交日期2016年3月学校代号：10532学号：S11102055密级：湖南大学学术硕士学位论文基于子图同构的XFA压缩算法设计学位申请人姓名：刘哲导师姓名及职称：林亚平教授培养单位：信息科学与工程学院专业名称：计算机科学与技术论文提交日期：2016年3月论文答辩日期：2016年4月17日答辩委员

2、会主席：秦拯教授DesignofXFACompressionAlgorithmsbasedonSubgraphIsomorphismbyLIUZheB.E.(HunanUniversity)2011AthesissubmittedinpartialsatisfactionoftherequirementsforthedegreeofMasterofEngineeringinComputeScienceintheGraduateSchoolofHunanUniversitySupervisorProfessor

3、LINYapingMarch,2016湖南大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：哲日期：年孓月￣曰学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或

4、机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于１、保密□，在年解密后适用本授权书。２、不保密Ｍ“”（请在以上相应方框内打Ｖ）＞，作者签名曰期：／：文年ｙ月曰１省￣导师签名：：日期年日Ｉ基于子图同构的的XFA压缩算法的设计与应用摘要网络入侵检测与防御（NetworkIntrusionDetection/Preven

5、tion，NIDP）是信息安全领域一个重要的技术手段。NIDP的基本原理是预先制定一定的安全策略，并将安全策略与其检测到的内容进行匹配，如果检测到安全策略不允许的内容，则拦截或作其他处理。而深度包检测（DeepPacketInspection，DPI）是实现NIDP的重要技术。由于正则表达式灵活、高效的特点，其常用于网络安全的DPI。传统的正则表达式匹配算法实现方式主要基于非确定有限自动机(NFA,NondeterministicFiniteAutomaton)和确定有限自动机(DFA,Determinist

6、icFiniteAutomaton)。上述两种实现方式在匹配效率和存储空间优化上很难兼得。NFA所需存储空间很小但是匹配速度很慢；DFA由于匹配速度很快使得DFA方法成为了实现正则表达式匹配的普遍选择，但DFA的高匹配速度是以可呈指数膨胀的状态空间为代价的。最近研究者们提出了扩展有限自动机（ExtendedFiniteAutomata，XFA），XFA的主要思想是在某些状态后附加一些额外的指令，对DFA实现压缩。附加的指令有寄存器置位复位、计数器累加复位等操作。针对一些包含通配符“.*”的数据具有很大的优化作

7、用。本文在分析传统正则表达式匹配算法NFA和DFA无法满足高性能需求的原因的基础上，试图进一步优化XFA。根据对于实际正则表达式数据集的研究，通过其生成的XFA当中会包含很多相似的结构。本文尝试利用子图同构的原理，提出将XFA进行分块处理后,对其进行合理的编码，从而进一步存储压缩存储空间，提升吞吐量。文中以星形结构为例，使用通过开源正则表达式工具regex转换得到的数据，进行了三态内容可寻址存储器（TernaryContentAddressableMemory，TCAM）的仿真实验。实验结果表明，本方法对于一

8、些数据集可以将存储空间压缩至26.8%，而相同存储量的吞吐量则提高到2.6倍。关键词：正则表达式匹配；TCAM；扩展有限自动机；子图同构II学术硕士学位论文AbstractNetworkIntrusionDetectionandPrevention(NIDP)isanimportanttechnicalmeansinthefieldofinformationsecurity.Thebasicprin