| 新颖的正则NFA引擎构造方法 |
| |
| 引用本文： | 敬茂华,杨义先,汪 韬,辛 阳. 新颖的正则NFA引擎构造方法[J]. 通信学报, 2014, 35(10): 12-106. DOI: 10.3969/j.issn.1000-436x.2014.10.012 |
| |
| 作者姓名： | 敬茂华 杨义先 汪 韬 辛 阳 |
| |
| 作者单位： | 1.东北大学秦皇岛分校 计算机与通信工程学院，河北 秦皇岛 066004；2.东北大学 信息科学与工程学院，辽宁 沈阳 110819；3. 云安全技术北京市工程实验室，北京 100082；4. 北京邮电大学 信息安全中心，北京 100876 |
| |
| 基金项目： | 国家自然科学基金资助项目（61100021，61121061，61202447）；河北省自然科学基金资助项目 (F2012501014)；河北省教育厅自然科学指导基金资助项目(Z2010215) |
| |
| 摘 要： | 提出了一种新颖的正则NFA引擎构造方法——PFA构造法。PFA构造法包括3个主要算法：预处理算法、解析树编码算法和基于编码树的NFA构造算法。采用PFA构造法能够构造出只含有一个开始状态和一个终止状态的规模更小的NFA，称其为NFAp。NFAp的规模与正则表达式组的长度线性相关，较Thompson自动机、后跟自动机、位置自动机以及部分派生自动机的规模都要小，是Thompson NFA的1/3，比已经接近最优的后跟自动机构造法所获得的NFA还要小。
|
| 关 键 词： | 深度分组检测；模式匹配；正则表达式；有穷自动机；构造算法 |
Novel NFA engine construction method of regular expressions |
| |
| Mao-hua JING,Yi-xian YANG,Tao WANG,Yang XIN. Novel NFA engine construction method of regular expressions[J]. Journal on Communications, 2014, 35(10): 12-106. DOI: 10.3969/j.issn.1000-436x.2014.10.012 |
| |
| Authors: | Mao-hua JING Yi-xian YANG Tao WANG Yang XIN |
| |
| Affiliation: | 1. School of Computer and Communication Engineering,Northeastern University at Qinhuangdao,Qinhuangdao 066004,China;2. College of Information Science and Engineering,Northeastern University,Shenyang 110819,China;3. Beijing Engineering Lab for Cloud Security,Beijing 100082,China;4. Information Security Center,Beijing University of Posts and Telecommunications,Beijing 100876,China |
| |
| Abstract: | A novel method for constructing smaller non-deterministic finite automata (NFA) engine from given regular expressions named PFA was proposed.There are three main algorithms in PFA,the pretreatment algorithm,the coding parser tree algorithm and the NFA construction algorithm based on the coded binary tree.The smaller NFA named NFAp with only one start state and one final state can be obtained by using PFA construction method.NFAphave linear size in terms of the size of given regular expressions.It is the smallest NFA comparing with current methods like Thompson NFA,follow automata,position automata and partial derivatives automata.The size of NFApis one third of Thompson’s and it is smaller than the size of follow automata whose size has nearly closed to optimal. |
| |
| Keywords: | deep packet inspection pattern matching regular expression finite automata construction algorithm |
|
| 点击此处可从《通信学报》浏览原始摘要信息 |
|
点击此处可从《通信学报》下载全文 |
