CAJ | 학술논문

串匹配技术是入侵检测系统中的关键技术，随着特征数量的增加，现有的自动机类匹配算法都会面对内存占用过大的问题．当特征超过一定数目后，自动机可能根本无法构造．文中提出了一种针对超大规模特征匹配（SLSPM）环境的匹配算法SLSPM．SLSPM算法借助一个块式匹配自动机和若干个普通自动机完成匹配工作，而且能够支持至少上万规模的特征集．与普通匹配自动机先读入状态再判断读入符号的方式不同，SLSPM首先使用散列函数判断当前文本块是否可以被过滤掉．如果文本块无法被过滤且为合法文本块时，再检查当前状态是否是一个能够识别当前文本块的状态．仅在当前状态吻合的情况下再读入下一个文本块进行后续匹配．理论证明显示SLSPM算法具有近似O（n）的复杂度．由于SLSPM算法未能保存全部的跳转信息，其匹配速度相对于高级Aho-Corasick算法未有大幅提升．算法的优势在于，该算法在软件环境下能够维持与AC算法相同的匹配性能，而且能够将特征加载规模至少提升至上万以适应超大规模特征集匹配环境．
천필배기술시입침검측계통중적관건기술，수착특정수량적증가，현유적자동궤류필배산법도회면대내존점용과대적문제．당특정초과일정수목후，자동궤가능근본무법구조．문중제출료일충침대초대규모특정필배（SLSPM）배경적필배산법SLSPM．SLSPM산법차조일개괴식필배자동궤화약간개보통자동궤완성필배공작，이차능구지지지소상만규모적특정집．여보통필배자동궤선독입상태재판단독입부호적방식불동，SLSPM수선사용산렬함수판단당전문본괴시부가이피과려도．여과문본괴무법피과려차위합법문본괴시，재검사당전상태시부시일개능구식별당전문본괴적상태．부재당전상태문합적정황하재독입하일개문본괴진행후속필배．이론증명현시SLSPM산법구유근사O（n）적복잡도．유우SLSPM산법미능보존전부적도전신식，기필배속도상대우고급Aho-Corasick산법미유대폭제승．산법적우세재우，해산법재연건배경하능구유지여AC산법상동적필배성능，이차능구장특정가재규모지소제승지상만이괄응초대규모특정집필배배경．
The current string matching algorithms nearly can not afford the burden of large memorydemand when the patters amount increases dramatically.Matching automaton can not be estab-lished at all when the amount of patterns is at least tens of thousands.We present a solution tothe problem of super large scale patterns matching (SLSPM).In our design,a matching trie isdivided into one block matching trie and many general character matching tries if possible.Duringa block matching procedure our block matching automaton (trie)does not read the current statefirst.Instead,the automaton first reads the current text block symbol and decides whether it willbe matched or not by a hash function.Then,the automaton looks for the current state in thestates set in which all the states recognize the same current text block symbol.After the currentstate is found the automaton continues to read the next text block symbol.The theoretical analysisshows that under the worst case the proposed algorithm takes O(n)time approximately,where n is the length of the text.The experiment results show that our design matches only a little fasterthan the advanced Aho-Corasick because in the advanced Aho-Corasick the entire possible transitioninformation has been stored.The advantage of SLSPMis that under software environmentSLSPMis not slower than AC during the matching procedure,and also at least tens of thousands patterns can be loaded into the hybrid automatons of SLSPMso that it can be used well for superlarge scale patters matching environment.