基于状态子集编码的快速DFA构造算法-论文.pdf

《基于状态子集编码的快速DFA构造算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第44卷第1期中国斜孽教求大誊辱取Vo1．44，No．12014年1月JOURNALOFUNlVERSITYOFSCIENCEANDTECHN0L0GYOFCHlNAJan．2014文章编号：0253—2778(2014)01—0001—11基于状态子集编码的快速DFA构造算法彭坤杨(巾国科学技术大学计算机科学与技术学院，安徽合肥230027)摘要：网络深度包检测等网络应用广泛采用正则表达式匹配技术检测网络中的传输内容，正则表达式用非确定性有限自动机(NFA)或者确定性有限自动机(DFA)实现．

2、网络应用对匹配速度要求很高，相比NFA，DFA具有确定性的匹配速度，但所有基于DFA的方法需要预先从NFA构造一个与之等价的DFA，于是DFA的构造成为系统瓶颈之一．为此通过深入探索自动机内在运行特性——NFA状态间活跃关系和NFA中导致DFA空间膨胀的因素，设计了一种NFA状态子集的编码方法和查询方法，显著减少了DFA构造过程中状态子集的查询代价．基于入侵检测与防护系统Snort中的真实规则集的实验表明，与传统的子集构造算法相比，该方法减少了88．33～93．57的DFA构造时间．关键词：NF

3、A；DFA；正则表达式匹配；深度包检测中图分类号：TP393文献标识码：Adoi：10．3969／j．issn．0253—2778．2014．01．001引用格式：PengKunyang．AfastDFAconstructionalgorithmbysubsetencoding[J]．JournalofUniversityofScienceandTechnologyofChina，2014，44(1)：1-11．彭坤杨．基于状态子集编码的快速DFA构造算法EJ2．中国科学技术大学学报，2014，

4、44(1)：1—11AfastDFAconstructionalgorithmbysubsetencodingPENGKunyang(SchoolofComputerScienceandTechnology，UniversityofScienceandTechnologyofChina，He{et230027，China)Abstract：Regularexpressionmatchingisthefoundationofmanynetworkfunctionssuchasdeeppacketi

5、nspection，whichiSperformedusingeithernondeterministicfiniteautomaton(NFA)ordeterministicfiniteautomation(DFA)．Tomeettherequirementofhigh-speedregularexpressionmatching，DFAhasbeentheprevalentchoiceforitsdeterministicnatureandmatchingefficiency．However

6、，alltheseDFA_basedapproachesneedtoconstructaDFAfromanNFAasanintermediatestep，thustheDFAconstructionprocesscanbeoneofbottlenecksforthesystem．ByexploringtheinherentpropertiesoffiniteautomatonwhethertheNFAstatessimultaneouslyactiveandhowtheself-loopingN

7、FAstatesleadtoexplosionofDFAstatespaceastatesubsetencodingandsearchingschemewasdesigned，andanewDFAconstructionalgorithmwasproposed．ThroughexperimentsbasedonreallifepatternsetsfromtheSnortintrusiondetectionsystem，thenewDFAconstructionalgorithmwasdemon

8、stratedtoreducetherunningtimeby88．33～93．57comparedwiththatofthestandardsubsetconstructionalgorithm．Keywords：NFA；DFA；regularexpressionmatching；deeppacketinspection收稿日期：2013—03—26；修回日期：20130423基金项目：中国科学技术大学博士研究生学术新人项目资助．作者简介：彭坤杨，男，1986年生，博士生．研究方向：网络与系统