基于NDIS中间层的Windows平台下包分类算法的研究
|
摘要
在Internet环境下广泛应用的网络安全技术,例如防火墙、入侵检测、网络监控、安全审计、虚拟专用网等,这些核心技术都是以包拦截包分类为基础的。数据包分类的正确性、准确性、快速性将直接影响安全产品的性能与效率。
目前,现有包分类算法中,一维、二维分类算法比较成熟应用广泛,而对于多维包分类算法的研究还很不成熟,存在许多急需解决的问题。比如,包分类的速度无法满足高速网络的应用需求,丢包的现象普遍存在;数据包分类的准确性有待提高,由于协议的复杂性往往导致数据包不能正常识别;随着规则库的扩大,内存空间过大无法满足低成本的要求;规则库难于更新等。
本人基于Hash函数快速查找、快速定位的思想,提出了一种基于Hash函数的五元一维包分类算法,该算法是基于包头的五元组分类的,但是由于进行了一次比较运算和一次Hash运算,从五元组降到了一维,最终存在规则库中的只有外地IP地址。因此,不但提高了查找速度,而且减小了存储空间,提高了网络数据包的分类效率。并给出该算法准确性、快速性的理论分析。
本文深入分析了Windows平台下各种数据包拦截技术,并且给出了各自的优缺点。采用NDIS中间层驱动程序实现数据包的拦截,因为NDIS中间层驱动程序工作在数据链路层与网络层之间,可以彻底的拦截所有进出主机的数据包。最后实现一个数据包分类系统,采用本人提出的基于Hash函数的五元一维包分类算法对拦截的数据包进行分类处理,实验结果与理论分析基本一致。
Under the Internet environment widespread application network security technology, such as firewalls, intrusion detection, network monitoring, security auditing, virtual private networks and so on, which are core technologies in order to intercept packets based on packet classification. Packet Classification correctness, accuracy, speed will directly affect the safety performance and efficiency.
At present, the existing packet classification algorithms, the one-dimensional, two-dimensional classification algorithms widely used in more mature, and for the multi-dimensional packet classification algorithm is still immature, there are many urgent problems. For example, the speed of packet classification can not meet the demand for high-speed network applications, packet loss widespread phenomenon; data packet classification accuracy to be improved, because of the complexity of the protocol often leads to identification of data packets can not be normal; With the expansion of the rule base, too much memory space can not meet the requirements of low-cost; difficult to update.
I based on that Hash function quick search, quick positioning of thinking, propose one based on Hash function five-dollar one-dimensional packet classification algorithm, which is based on the five-byte header classification, but as a result of a comparison operator and a Hash computing, from five down to one-dimensional, and ultimately there is only a rule-base in the IP Address field. Therefore, not only improved the seek rate, but also reduced the storage space, raised the network data package of classification efficiency. And given this algorithm accuracy, the rapid theoretical analysis.
This article has analyzed under thoroughly the Windows platform each kind of data packet interception technology, and given the advantages and disadvantages of each. The use of NDIS intermediate driver layer of the intercept data packets, because NDIS intermediate driver layer in the data link layer and network layer, which can completely block all access to the host of the packet. Finally, the realization of a packet classification system, using my Hash function based on the five-dollar one-dimensional packet classification algorithm for packet interception classification processing, experimental results are basically consistent with the theoretical analysis.
目前,现有包分类算法中,一维、二维分类算法比较成熟应用广泛,而对于多维包分类算法的研究还很不成熟,存在许多急需解决的问题。比如,包分类的速度无法满足高速网络的应用需求,丢包的现象普遍存在;数据包分类的准确性有待提高,由于协议的复杂性往往导致数据包不能正常识别;随着规则库的扩大,内存空间过大无法满足低成本的要求;规则库难于更新等。
本人基于Hash函数快速查找、快速定位的思想,提出了一种基于Hash函数的五元一维包分类算法,该算法是基于包头的五元组分类的,但是由于进行了一次比较运算和一次Hash运算,从五元组降到了一维,最终存在规则库中的只有外地IP地址。因此,不但提高了查找速度,而且减小了存储空间,提高了网络数据包的分类效率。并给出该算法准确性、快速性的理论分析。
本文深入分析了Windows平台下各种数据包拦截技术,并且给出了各自的优缺点。采用NDIS中间层驱动程序实现数据包的拦截,因为NDIS中间层驱动程序工作在数据链路层与网络层之间,可以彻底的拦截所有进出主机的数据包。最后实现一个数据包分类系统,采用本人提出的基于Hash函数的五元一维包分类算法对拦截的数据包进行分类处理,实验结果与理论分析基本一致。
Under the Internet environment widespread application network security technology, such as firewalls, intrusion detection, network monitoring, security auditing, virtual private networks and so on, which are core technologies in order to intercept packets based on packet classification. Packet Classification correctness, accuracy, speed will directly affect the safety performance and efficiency.
At present, the existing packet classification algorithms, the one-dimensional, two-dimensional classification algorithms widely used in more mature, and for the multi-dimensional packet classification algorithm is still immature, there are many urgent problems. For example, the speed of packet classification can not meet the demand for high-speed network applications, packet loss widespread phenomenon; data packet classification accuracy to be improved, because of the complexity of the protocol often leads to identification of data packets can not be normal; With the expansion of the rule base, too much memory space can not meet the requirements of low-cost; difficult to update.
I based on that Hash function quick search, quick positioning of thinking, propose one based on Hash function five-dollar one-dimensional packet classification algorithm, which is based on the five-byte header classification, but as a result of a comparison operator and a Hash computing, from five down to one-dimensional, and ultimately there is only a rule-base in the IP Address field. Therefore, not only improved the seek rate, but also reduced the storage space, raised the network data package of classification efficiency. And given this algorithm accuracy, the rapid theoretical analysis.
This article has analyzed under thoroughly the Windows platform each kind of data packet interception technology, and given the advantages and disadvantages of each. The use of NDIS intermediate driver layer of the intercept data packets, because NDIS intermediate driver layer in the data link layer and network layer, which can completely block all access to the host of the packet. Finally, the realization of a packet classification system, using my Hash function based on the five-dollar one-dimensional packet classification algorithm for packet interception classification processing, experimental results are basically consistent with the theoretical analysis.
引文
[1]CNCERT/CC2008 年上半年网络安全工作报告.[EB/OL].http://www.cert.org.cn/articles/docs/common/2008112124134.shtml.
[2]田利勤,林闯.报文分类技术的研究及其应用[J].计算机研究与发展,2003年6月,第40卷第6期:765-775.
[3]张定心.报文分类算法的研究.[硕士学位论文]解放军信息工程大学,2003年5月,4-10.
[4]段云所等译.个人防火墙[M].北京:人民邮电出版社.2002年,34-50.
[5]冯博琴等译.Windows 2000驱动程序开发大全,第一卷,设计指南[M].北京:机械工业出版社.2001年,821-838.
[6]Behrouz A.Forouzan,Sophia Chung Fegan.TCP/IP协议族[M].谢希仁译.北京:清华大学出版社.2003年,15-32.
[7]W.Richard Stevens.TCPIP协议详解卷一:协议[M].谢钧、蒋慧、吴礼发等译.北京:机械工业出版社.2000年,24-170.
[8]朱雁辉.Windows防火墙与网络封包截获技术[M].北京:电子工业出版社.2002年,119-131.
[9]王艳平,张越编著.Windows网络与通信程序设计[M].北京:人民邮电出版社.2006年,165-189.
[10]张宏怡,普杰信.基于Windows的网络数据包拦截技术[J].信息技术,2004年,28(2):12-13.
[11]王艳平.Windows程序设计[M].北京:人民邮电出版社.2005年,377-378.
[12]王旭阳,陆际光.基于Windows的多种网络数据包拦截方案的比较分析[J].微型电脑应用,2007年,23(9):53-55.
[13]郭兴阳,高峰,唐朝京.一种NDIS中间层数据包过滤方法[J].计算机工程,200.4年,30(17):102-103.
[14]Chris Cant.Windows WDM设备驱动程序开发指南[M].北京:机械工业出版社.2000年,245-247.
[15]卢泽新.核心路由器技术及实现[J].电信科学.2001年,第7期.31-35.
[16]徐恪,徐明伟,吴建平,喻中超.IP分类技术研究综述[J].小型微型计算机系统,2002年,23(7):电子学报.2001,773-779.
[17]林闯,单志广,任丰原.计算机网络的服务质量(Q0s)[M].北京:清华大学出版社.2004年,119-120.
[18]单征,赵荣彩,张铮.报文分类算法研究[J].计算机工程与应用,2005,7:149-152.
[19]张人杰.现代高速网络设备核心部件--网络处理器技术分析[J].数据通信.2002第3期.42-45.
[20]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社.2004年,214-262.
[21]Amit Prakash,Adnan Aziz,A Middle Ground between CAMs and DAGs for High-Speed Packet Classification,10th Symposium on High Performance Interconnects HOT Interconnects,August21-23,2002,Stanford,California,USA.
[22]Pankaj Gupta,Nick McKeown.Algorithms for Packet Classification.IEEE Network.March 2001.
[23] Stefan Saroiu, Krishna P. Gummadi, Richard J. Dunn, Steven D. Gribble and Henry M.Levy.An Analysis of Internet Content Delivery Systems.IEEE, August 2003.
[24] Florin Baboescu and George Varghese. Scalable Packet Classification. ACM,August 2001.
[25] Solomin, David A. Windows NT kernel architecture. Computer, 1998, 31(10):40-4.
[26] Mark E.Russinovich,David A.Solomon. Microsoft Windows Internals. Microsoft Press,2004(12):787-844.
[27] Microsoft Windows XP Driver Development Kits Document, Microsoft Corporation,2001.
[28] Richard Stevens W. TCP/IP 详解[M].北京:机械工业出版社. 2000年, 156-157.
[29] Pankaj Gupta, Nick McKeown. Algorithms for Packet Classification. IEEE Network.March 2001.
[30] Kijkanjanarat T. Fast routing lookup and packet classification for next-generation router .Ph.D. Dissertation. Polytechnic University. January 2002.
[31] Florin Baboescu, George Varghese. Scalable Packet Classification.ACMSIGCOMM'01. 2001 年,199-210.
[32] Gupta, P. McKeown,N. Packet classification on multiple fields. In :Proceedings of ACM Sigcomm'99,August 1999. 147-160.
[33] Xue hong. IP Address Lookup and Packet Classification Alogrithms:[Dissertation]. Ottawa,Ontario,Canada: Carleton University,2003,43~51.
[34] Gupta P., McKeown N., Algorithms for packet classification, IEEE Network,Volume: 15 Issue: 2, Mar 2001, 24 -32.
[35] V.Srinivasan. Fast and Efficient Internet Lookups[J]. Ph.D Thesis. Washington University,1999.
[36] T.V.Lakshman and D.Stidialis. High Speed Policy-based Packet ForwardingUsing Effcient Multi-dimensional Rang Matching. Proceeding of ACMSIGCOMM, Aug 1998,191-202.
[37] V.Srinivasan,S.Suri and G.Varghese. Packet classification using tuple space search.In: Proceedings of ACM Sigcomm99, Aug 1999. 135—146.
[38] T.Y.C.Woo. A modular approach to packet classification: algorithms and results [J].In: Gruein R ed. Proceedings of IEEE Infocom 2000.San Francisco,CA: IEEE Computer Society Press,2000:1210~1217.
[39] G. Gibson, F. Shafai, and J. Podaima. Content Addressable Memory Storage Device.United States Patent 6. 044-005. March 2000. SiberCore Technologies,Inc.
[2]田利勤,林闯.报文分类技术的研究及其应用[J].计算机研究与发展,2003年6月,第40卷第6期:765-775.
[3]张定心.报文分类算法的研究.[硕士学位论文]解放军信息工程大学,2003年5月,4-10.
[4]段云所等译.个人防火墙[M].北京:人民邮电出版社.2002年,34-50.
[5]冯博琴等译.Windows 2000驱动程序开发大全,第一卷,设计指南[M].北京:机械工业出版社.2001年,821-838.
[6]Behrouz A.Forouzan,Sophia Chung Fegan.TCP/IP协议族[M].谢希仁译.北京:清华大学出版社.2003年,15-32.
[7]W.Richard Stevens.TCPIP协议详解卷一:协议[M].谢钧、蒋慧、吴礼发等译.北京:机械工业出版社.2000年,24-170.
[8]朱雁辉.Windows防火墙与网络封包截获技术[M].北京:电子工业出版社.2002年,119-131.
[9]王艳平,张越编著.Windows网络与通信程序设计[M].北京:人民邮电出版社.2006年,165-189.
[10]张宏怡,普杰信.基于Windows的网络数据包拦截技术[J].信息技术,2004年,28(2):12-13.
[11]王艳平.Windows程序设计[M].北京:人民邮电出版社.2005年,377-378.
[12]王旭阳,陆际光.基于Windows的多种网络数据包拦截方案的比较分析[J].微型电脑应用,2007年,23(9):53-55.
[13]郭兴阳,高峰,唐朝京.一种NDIS中间层数据包过滤方法[J].计算机工程,200.4年,30(17):102-103.
[14]Chris Cant.Windows WDM设备驱动程序开发指南[M].北京:机械工业出版社.2000年,245-247.
[15]卢泽新.核心路由器技术及实现[J].电信科学.2001年,第7期.31-35.
[16]徐恪,徐明伟,吴建平,喻中超.IP分类技术研究综述[J].小型微型计算机系统,2002年,23(7):电子学报.2001,773-779.
[17]林闯,单志广,任丰原.计算机网络的服务质量(Q0s)[M].北京:清华大学出版社.2004年,119-120.
[18]单征,赵荣彩,张铮.报文分类算法研究[J].计算机工程与应用,2005,7:149-152.
[19]张人杰.现代高速网络设备核心部件--网络处理器技术分析[J].数据通信.2002第3期.42-45.
[20]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社.2004年,214-262.
[21]Amit Prakash,Adnan Aziz,A Middle Ground between CAMs and DAGs for High-Speed Packet Classification,10th Symposium on High Performance Interconnects HOT Interconnects,August21-23,2002,Stanford,California,USA.
[22]Pankaj Gupta,Nick McKeown.Algorithms for Packet Classification.IEEE Network.March 2001.
[23] Stefan Saroiu, Krishna P. Gummadi, Richard J. Dunn, Steven D. Gribble and Henry M.Levy.An Analysis of Internet Content Delivery Systems.IEEE, August 2003.
[24] Florin Baboescu and George Varghese. Scalable Packet Classification. ACM,August 2001.
[25] Solomin, David A. Windows NT kernel architecture. Computer, 1998, 31(10):40-4.
[26] Mark E.Russinovich,David A.Solomon. Microsoft Windows Internals. Microsoft Press,2004(12):787-844.
[27] Microsoft Windows XP Driver Development Kits Document, Microsoft Corporation,2001.
[28] Richard Stevens W. TCP/IP 详解[M].北京:机械工业出版社. 2000年, 156-157.
[29] Pankaj Gupta, Nick McKeown. Algorithms for Packet Classification. IEEE Network.March 2001.
[30] Kijkanjanarat T. Fast routing lookup and packet classification for next-generation router .Ph.D. Dissertation. Polytechnic University. January 2002.
[31] Florin Baboescu, George Varghese. Scalable Packet Classification.ACMSIGCOMM'01. 2001 年,199-210.
[32] Gupta, P. McKeown,N. Packet classification on multiple fields. In :Proceedings of ACM Sigcomm'99,August 1999. 147-160.
[33] Xue hong. IP Address Lookup and Packet Classification Alogrithms:[Dissertation]. Ottawa,Ontario,Canada: Carleton University,2003,43~51.
[34] Gupta P., McKeown N., Algorithms for packet classification, IEEE Network,Volume: 15 Issue: 2, Mar 2001, 24 -32.
[35] V.Srinivasan. Fast and Efficient Internet Lookups[J]. Ph.D Thesis. Washington University,1999.
[36] T.V.Lakshman and D.Stidialis. High Speed Policy-based Packet ForwardingUsing Effcient Multi-dimensional Rang Matching. Proceeding of ACMSIGCOMM, Aug 1998,191-202.
[37] V.Srinivasan,S.Suri and G.Varghese. Packet classification using tuple space search.In: Proceedings of ACM Sigcomm99, Aug 1999. 135—146.
[38] T.Y.C.Woo. A modular approach to packet classification: algorithms and results [J].In: Gruein R ed. Proceedings of IEEE Infocom 2000.San Francisco,CA: IEEE Computer Society Press,2000:1210~1217.
[39] G. Gibson, F. Shafai, and J. Podaima. Content Addressable Memory Storage Device.United States Patent 6. 044-005. March 2000. SiberCore Technologies,Inc.