面向宽带网络环境的防火墙分布式并行全搜索过滤技术
摘要
当前，网络化与信息化突破了时间和地域的限制，已成为全球化不可抗拒的世界潮流。目前互联网正与电话网、电视网、无线网、卫星网相结合，互联网在商业运作的驱动下，更加迅猛地发展。
但是同时，网络的安全形势也同时越来越严峻。而防火墙作为网络安全的重要组成部分，其性能是非常重要的。防火墙的发展经历了五个时代，目前带状态监测的防火墙是防火墙技术的主流。
在防火墙的性能上，过滤规则库的搜索和状态监测表的搜索、维护是关键。这两个方面的技术目前在国内外都研究得比较多。但是相对于网络应用的不断发展，尤其是近年来的宽带网络技术发展，还是有很大不足。在很多场合下，防火墙的性能已经成为网络带宽的瓶颈问题。
本文在带状态监测的防火墙结构基础上，首先从总体上设计了整个防火墙的结构，进而研究了过滤规则库和状态监测表的搜索、维护问题，提出了将计算几何学、图论中的数据结构和算法引入防火墙的设计的方式，将基础理论应用到实践中来。
在过滤规则库的搜索过程中，本文将规则库视为一个三维空间中有重叠的长方体集合，在规则库中搜索数据包匹配的规则，则转化为在长方体集合中搜索点所处的长方体的问题。参考了计算几何中在一个平面上多个不重叠的矩形中定位的算法，设计出初始化算法和搜索算法。
在状态监测表的搜索、维护问题上，本文采用改进后的键树作为数据结构，并且设计了改进的键树的存储方案、在其上的搜索、添加、删除结点等的算法。
除了将这些方面的数据结构与算法引入防火墙外，本文还进行了这些方法和其它一些实现方法之间的比较，综合分析了各自的优点与缺点，为将来从事设计的人员提供了一个参考。
Now a day the development of the internet has widely spread the world. It surpassed the limitation of time and distance, made the world becoming a earth-village. And under the imitation of business, the internet developed much faster than pure technology. But meanwhile the internet becomes more and more dangerous.
Firewall, as the main component of networking security, its performance is attached to more importance. The firewall has gone through 5 generations and the current main stream is firewall with state inspection. The main problem of the performance is searching of filter rules and state inspector table. There are a lot of researching done and being done in the world, but facing with the rapid progress of internet application, the performance is still unsatisfied. In many cases the firewall is still the choke point of the bandwidth.
The thesis designed the structure of a firewall in global, and then it go deep into the problem of searching and maintaining the filter rules and the state inspection table. It employed the data structure and algorithms of geometry and graph theory in the design of firewall.
In design of the filter rules, it takes the rules as a set of cuboids, and the searching process is transferred to a process of locating a point in these cuboids. With help of reference to some documents in geometry, it gave methods to solve of the problem.
When discussed about the state inspector table, it employed key-tree as the storage method, but it improved the tree. It also gave the procedure about searching, inserting and deleting nodes in the tree.
Besides the designing of data structure and algorithms, it made comparisons between its design scheme and some other schemers. It analyzed their advantages and disadvantages and made some advice for selecting the schemes.
但是同时，网络的安全形势也同时越来越严峻。而防火墙作为网络安全的重要组成部分，其性能是非常重要的。防火墙的发展经历了五个时代，目前带状态监测的防火墙是防火墙技术的主流。
在防火墙的性能上，过滤规则库的搜索和状态监测表的搜索、维护是关键。这两个方面的技术目前在国内外都研究得比较多。但是相对于网络应用的不断发展，尤其是近年来的宽带网络技术发展，还是有很大不足。在很多场合下，防火墙的性能已经成为网络带宽的瓶颈问题。
本文在带状态监测的防火墙结构基础上，首先从总体上设计了整个防火墙的结构，进而研究了过滤规则库和状态监测表的搜索、维护问题，提出了将计算几何学、图论中的数据结构和算法引入防火墙的设计的方式，将基础理论应用到实践中来。
在过滤规则库的搜索过程中，本文将规则库视为一个三维空间中有重叠的长方体集合，在规则库中搜索数据包匹配的规则，则转化为在长方体集合中搜索点所处的长方体的问题。参考了计算几何中在一个平面上多个不重叠的矩形中定位的算法，设计出初始化算法和搜索算法。
在状态监测表的搜索、维护问题上，本文采用改进后的键树作为数据结构，并且设计了改进的键树的存储方案、在其上的搜索、添加、删除结点等的算法。
除了将这些方面的数据结构与算法引入防火墙外，本文还进行了这些方法和其它一些实现方法之间的比较，综合分析了各自的优点与缺点，为将来从事设计的人员提供了一个参考。
Now a day the development of the internet has widely spread the world. It surpassed the limitation of time and distance, made the world becoming a earth-village. And under the imitation of business, the internet developed much faster than pure technology. But meanwhile the internet becomes more and more dangerous.
Firewall, as the main component of networking security, its performance is attached to more importance. The firewall has gone through 5 generations and the current main stream is firewall with state inspection. The main problem of the performance is searching of filter rules and state inspector table. There are a lot of researching done and being done in the world, but facing with the rapid progress of internet application, the performance is still unsatisfied. In many cases the firewall is still the choke point of the bandwidth.
The thesis designed the structure of a firewall in global, and then it go deep into the problem of searching and maintaining the filter rules and the state inspection table. It employed the data structure and algorithms of geometry and graph theory in the design of firewall.
In design of the filter rules, it takes the rules as a set of cuboids, and the searching process is transferred to a process of locating a point in these cuboids. With help of reference to some documents in geometry, it gave methods to solve of the problem.
When discussed about the state inspector table, it employed key-tree as the storage method, but it improved the tree. It also gave the procedure about searching, inserting and deleting nodes in the tree.
Besides the designing of data structure and algorithms, it made comparisons between its design scheme and some other schemers. It analyzed their advantages and disadvantages and made some advice for selecting the schemes.
引文
[1] 李增智. 计算机网络原理(修订本). 西安，西安交通大学出版社，1991.7.
[2] William Stallings (齐望东，薛卫娟，傅麒麟，等译). 高速网络. 北京，电子工业出版社，1999.12.
[3] 林升，王闽. 一种新型计算机网络黑客入侵防护系统. 微型电脑应用，2000，16(8)：10-12.
[4] Check Point. Check Point(tm) FireWall-1(r) Guide. 2001.6.
[5] W. Richard Stevens (范建华，胥光辉，张涛，等译). TCP/IP详解－卷1：协议. 北京，机械工业出版社，2000.4.
[6] W. Richard Stevens. TCP/IP Illustrated, Volume 1: The Protocols. America, Addison Wesley. 1994.
[7] 林仙丽，傅清祥. 矩形集上的点定位. 福州大学学报(自然科学版)，1999，27(4)：24-28.
[8] 傅清祥，王晓东. 算法与数据结构. 北京，电子工业出版社，2001.8.
[9] 严蔚敏，吴伟民. 数据结构. 北京，清华大学出版社，1992.6.
[10] 翁冠南. 基于应用网关的混合型防火墙的研究和实现：[硕士学位论文]. 哈尔滨：哈尔滨工业大学，2000.
[11] 段海新，吴建平，等. 防火墙规则的动态分配和散列表匹配算法. 北京：清华大学学报(自然科学版)，2001，41(1)，96-98，128.
[12] 陆汝钤. P/R网和进程(Ⅰ). 中国科学(A辑)，1991.9：992-999.
[13] 陆汝钤. P/R网和进程(Ⅱ). 中国科学(A辑)，1991.10：1105-1112.
[14] Preparata F P，Shamos M I. Computational geometry，an introduction[M]. New York：Springer-Verlag，1985.
[2] William Stallings (齐望东，薛卫娟，傅麒麟，等译). 高速网络. 北京，电子工业出版社，1999.12.
[3] 林升，王闽. 一种新型计算机网络黑客入侵防护系统. 微型电脑应用，2000，16(8)：10-12.
[4] Check Point. Check Point(tm) FireWall-1(r) Guide. 2001.6.
[5] W. Richard Stevens (范建华，胥光辉，张涛，等译). TCP/IP详解－卷1：协议. 北京，机械工业出版社，2000.4.
[6] W. Richard Stevens. TCP/IP Illustrated, Volume 1: The Protocols. America, Addison Wesley. 1994.
[7] 林仙丽，傅清祥. 矩形集上的点定位. 福州大学学报(自然科学版)，1999，27(4)：24-28.
[8] 傅清祥，王晓东. 算法与数据结构. 北京，电子工业出版社，2001.8.
[9] 严蔚敏，吴伟民. 数据结构. 北京，清华大学出版社，1992.6.
[10] 翁冠南. 基于应用网关的混合型防火墙的研究和实现：[硕士学位论文]. 哈尔滨：哈尔滨工业大学，2000.
[11] 段海新，吴建平，等. 防火墙规则的动态分配和散列表匹配算法. 北京：清华大学学报(自然科学版)，2001，41(1)，96-98，128.
[12] 陆汝钤. P/R网和进程(Ⅰ). 中国科学(A辑)，1991.9：992-999.
[13] 陆汝钤. P/R网和进程(Ⅱ). 中国科学(A辑)，1991.10：1105-1112.
[14] Preparata F P，Shamos M I. Computational geometry，an introduction[M]. New York：Springer-Verlag，1985.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |