摘要
随着Internet环境的不断复杂以及数量的不断增加,要求防火墙、VPN、PKI、入侵检测等技术更加的快速、高效。模式匹配能有效支持网络内容安全并提高网络设备的性能,是高速网络的关键技术之一。
本文介绍了模式匹配的研究背景、发展和研究现状,探讨了防火墙、入侵检测等网络内容安全的关键技术,分析研究了经典模式匹配算法。针对已有模式匹配算法存在的不足,提出了一种基于字频的模式匹配算法——BCFM算法。该算法首先建立一个字符使用频率表,根据使用频率表找出模式串中使用频率最低和次低的字符,并记录它们的相对位置。当模式匹配时,首先查找出文本中使用频率最低的字符,然后直接将其相应位置上的字符与使用频率次低的字符进行匹配,迅速完成匹配过程。BCFM算法对字符定位较准确,从而提高了模式匹配的效率。
本文还对防火墙和入侵检测技术进行了分析和研究。最后,通过实验对BCFM和BM算法的性能进行了测试和比较。实验结果表明,BCFM算法具有较好的时间效率,并且在模式串较短、文本较长时作用发挥的更加明显。
The more rapid and efficient of technology such as firewall, VPN, PKI and intrusion detection is required by the increasing complexity of Internet environment and the increasing number of Internet. Pattern matching which is able to effectively support network content security and improve the performance of network equipments is one of the most important high-speed network.
In this thesis, the research background, development and current research status of pattern matching are written first, followed by the related technology of content security as well as firewall and intrusion detection. After that, typical pattern matching algorithms are described and analyzed. To improve the shortage of pattern matching algorithms, a pattern matching algorithm based on word frequency, which is named BCFM, is proposed here. This algorithm establishes a character frequency table firstly, then finds the lowest frequency character and the second lowest frequency character according to this table, and records their relative position. When the pattern matches, it will be find out the lowest frequency characters in the text firstly, then the character on the relative position with the second lowest frequency character to match directly. The matching process is completed quickly. BCFM algorithm is more accurate for character positioning than other algorithms, so it increases the efficiency of pattern matching.
Firewall and intrusion detection is also investigated here. Finally, an experiment is completed to test and compare the performance of BM and BCFM. The results indicate that BCFM is provided with preferable efficiency on time. It is more efficiency when pattern is shorter and text is longer.
引文
[1]Fisky M, Varghese G. An analysis of fast string matching applied to content-based forwarding and intrusion detection:[UCSD Technical Report CS2001-0670(updated version)][J],2002.
[2]Charras C, lecroq T. Exact string marching algorithm [J]. http://www-igm.univ-mlv.fr/-lecroq/string,1997,1.
[3]Knuth DE, Morris JH, Pratt VR. Fast pattern matching in strings[J]. SIAM Journal on Computing, 1977,6(1):323-350.
[4]RS Boyer, JS Moore. A fast string searching algorithm[J]. Communication of the ACM, 1977,20(10):762-772.
[5]Daniel M Sunday. A very fast substring searching algorithm[J]. Communication of the ACM, 1990,33(8):132-142.
[6]Horspool R N. Practical fast searching in strings[J]. Software-Practice and Experience, 1980,10(6):501-506.
[7]Daniel M S. Very Fast Substring Search Algorithm[J]. Communications of the ACM.1990,33(8):132-142.
[8]Aho AV, Corasick MJ. Efficient string marching: an add to biological graphyic search[J]. Communication of the ACM. 1975, 18(6): 333-340.
[9]Sun Wu, Udi Manber. Agrep-A fast approximate pattern-matching tool[C]. Usenix Winter Technical Conference,1992:153-162.
[10]Tuck N, Sherwood T, Calder B, etal. Deterministic memory-efficient string marching algorithms for intrusion detection[C].Proceedings of the IEEE Infocom Conference,2004.
[11]Fan J J, Su K Y. An efficient algorithm for marching multiple patterns[C], IEEE Transactions on knowledge and data engineering, 1993,5(2): 339-351.
[12]王永成,沈洲,许一震.改进的多模式匹配算法[J],计算机研究与发展, 2002,39(1):55-60.
[13]张鑫,谭建龙,程学旗.一种改进的Wu-Manber多关键字匹配算法[J],计算机应用, 2003,23(7):29-31.
[14]黎连业,张维,向东明.防火墙及应用技术[M],清华大学出版社,2004,7.
[15]张翠肖,王峰.利用VPN技术构建企业内部网[J],计算机应用研究,2001,5.
[16]Andrew Nash,张玉清译.公钥基础设施(PKI):实现和管理电子安全[M],清华大学出版社, 2002,12.
[17]B. Mukherjee, L. T. Heberlein, and K. N. Levitt. Network Intrusion Detection IEEE Network[C],1994,8(3):26-41.
[18]谢希仁.计算机网络教程[M],人民邮电出版社,2002,5.
[19]李涛.安全网络概论[M],电子工业出版社,2008.
[20]翟钰,武舒凡,胡建斌.防火墙包过滤技术发展研究[J],计算机应用研究,2004(9):144-146.
[21]刘更楼,丁常福,蒋建国.基于状态检测的防火墙系统研究[J],航空计算机技术, 2004(1):122-125.
[22]M. Smith, R. Hunt. Network Security Using NAT and NAPT[C], IEEE International Conference on network, 2002,8:355-360.
[23]张明武,刘劲葵. HTTP代理服务系统的实现与分析[J],计算机工程,2001(3):145-147.
[24]R. Venkateswaran. Virtual Private Networks[C],Potentials IEEE, Volume 20, Issue 1, 1999,3:11-15.
[25]James P Anderson. Computer Security Threat Monitoring and Surveillance[J], 1980,4.
[26]Dorothy E Denning. An Intrusion Detection Model[C], IEEE Transaction on Software Engineering, 1987,13(2):222-232.
[27]ISS公司的PSDR动态安全模型, http://www.bj.is-one.net/inside/aqfu_linian_p2dr.php.
[28]刘远生.计算机网络安全[M],清华大学出版社, 2006,5.
[29]张然,钱德沛,张文杰,刘轶,栾钟治.入侵检测技术研究综述[J],小型微型计算机系统, 2003,7:24-36.
[30]杜强. SPSS统计分析从入门到精通[M],人民邮电出版社,2009.
[31]陈德礼,程羽.基于神经网络和规则的专家系统的应用研究[J],计算机工程与科学,2004,26(6):70-72.
[32]Kennedy J, Eberhart R. Particle Swarm Optimization, Proc[C], IEEE Int. Conf on Neural Network, 1995:1942-1948.
[33]TSENG C S, CHEN B S, UANG H J. Fuzzy tracking control design for nonlinear dynamic systems via T-S fuzzy model[C], IEEE Trans on Fuzzy Systems, 2001,9(3):381-392.
[34]Quinlan J R. Induction of decision trees[J], Machine Learning, 1986,1(1):81-106.
[35]Dasgupta, Forrest. An anomaly detection algorithm inspired by the immune system[J],Artifical Immune Systems and Their Applications,1999:262-277.
[36]盛思源,战守义,石耀斌.基于数据挖掘的入侵检测系统[J],计算机工程, 2003,29(1):156-157,217.
[37]Lee W,Stolfo S,Mok K. A Data Mining Framework for Adaptive Intrusion Detection[C],Proceedings of the 1999 IEEE Symposium on Security and Privacy, 1999:120-132.
[38]侯方明,李大兴.一种新的机遇协议树的入侵检测系统的设计[J],计算机应用研究,2005.
[39]张乃孝.算法与数据结构——C语言描述(第二版)[M], 2006,6.
[40]纪祥敏,连一峰,许晓利,贾文臣.入侵检测的技术与发展[J],计算机仿真, 2004,11:66-78.
[41]R. Bayer. Symetric binary B-trees: Data structure and maintenance algorithms[J], Acta Information,1972:34-52.
[42]Caswell B, Beale J. Snort2.0 Intrusion Detection[M],国防工业出版社,2004:21-46.
