资源描述：
《An Improved Algorithm to Accelerate Regular Expression Evaluation》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、AnImprovedAlgorithmtoAccelerateRegularExpressionEvaluationMichelaBecchiPatrickCrowleyWashingtonUniversityWashingtonUniversityComputerScienceandEngineeringComputerScienceandEngineeringSt.Louis,MO63130-4899St.Louis,MO63130-4899+1-314-935-4306+1-314-935-9186mbecchi@cs
2、e.wustl.edupcrowley@wustl.eduSecurityAppliances[13]andtheCitrixApplicationFirewall[14]—ABSTRACTuseregularexpressionstodescribepayloadpatterns.Inaddition,Modernnetworkintrusiondetectionsystemsneedtoperformregularapplication-levelsignatureanalysishasbeenrecentlypropo
3、sedasanexpressionmatchingatlinerateinordertodetecttheoccurrenceofaccuratemeanstodetectandtrackpeer-to-peertraffic,enablingcriticalpatternsinpacketpayloads.Whiledeterministicfinitesophisticatedpacketprioritizationmechanisms[17].automata(DFAs)allowthisoperationtobepe
4、rformedinlineartime,theymayexhibitprohibitivememoryrequirements.In[9],KumaretRegularexpressionsaremoreexpressivethansimplepatternsofal.proposeDelayedInputDFAs(D2FAs),whichprovideatrade-offstringsandthereforeabletodescribeawidervarietyofpayloadbetweenthememoryrequir
5、ementsofthecompressedDFAandthesignatures,buttheirimplementationsdemandfargreatermemorynumberofstatesvisitedforeachcharacterprocessed,whichspaceandbandwidth.Consequently,therehasbeenaconsiderablecorrespondsdirectlytothememorybandwidthrequiredtoevaluateamountofrecent
6、workonimplementingregularexpressionsforuseregularexpressions.inhigh-speednetworkingapplications,particularlywithrepresentationsbasedondeterministicfiniteautomata(DFA).Inthispaperweintroduceageneralcompressiontechniquethatresultsinatmost2Nstatetraversalswhenprocessi
7、ngastringofDFAshaveattractivepropertiesthatexplaintheattentionthey2lengthN.IncomparisontotheDFAapproach,ourtechniquehavereceived.Foremost,theyhavepredictableandacceptableachievescomparablelevelsofcompression,withlowerprovablememorybandwidthrequirements.Infact,theus
8、eofDFAsallowsoneboundsonmemorybandwidth(orgreatercompressionforagivensinglestatetransition,andonecorrespondingmemoryoperation,forbandwidthbound).
