域间路由安全监测系统的研究与实现
|
摘要
国家的经济建设和社会发展对全球Internet的依赖性越来越强。基于BGP协议构造的域间路由系统是Internet的基础设施,目前仍面临多种恶意攻击的威胁且易受人为错误的影响。近年来,对Internet域间路由安全的研究受到极大关注,已成为Internet领域中的一个研究热点。
由于S-BGP等安全协议机制的部署存在重重障碍,要基于现有网络设备确保域间路由系统的健康,域间路由监测是非常实际和真正能够发挥效用的技术途径,它具有可扩展性好、方便部署以及不需对现有协议修改等特点。本文针对现有域间路由监测系统的不足,提出了一种域间路由安全监测系统ISP-View的层次模型,研究该模型下的若干关键技术,设计并实现了该监测系统。
建立了监测系统的关系数据库模型,给出了网络知识库、Internet模型库、Internet域间路由信息与异常库、本地BGP路由信与异常库的详细设计。着重研究了路由表的压缩存储:对单个路由表内部,通过关系拆分对数据库模型进行规范化处理,去除了关系内部的数据冗余;对多个路由表之间的压缩提出了一种基于时间戳的增量式无损压缩算法,新增的时间戳字段方便了多路由表的联合分析和检测。
系统实现了对路由表的高效检测。通过对BGP路由表的语法和语义分析,将BGP路由表中的异常检测规则分为战略性规则、一般规则和特殊规则,设计并实现了基于异常检测规则的检测引擎,对路由信息库进行单视图异常检测、多视图异常检测和本地应用策略检查,构造路由信息异常库。
改进了现有的基于力学模型的拓扑展示计算模型,提出了基于磁场-弹簧的力学模型实现网络拓扑图的动态展示。将算法应用于ISP-View中,可以展示不同粒度下的网络拓扑结构,动态显示路由系统的安全状态,实现对域间路由的异常行为的安全监测。将模拟退火算法用于ISP-View中大规模拓扑的离线静态拓扑展示。
最后,给出了域间路由监测系统的详细设计,实现了一个Internet域间路由监测系统原型——ISP-View,并给出了系统ISP-View的一些应用实例。
National economy and society development become more dependent on the global Internet. Inter-domain routing system based on BGP is the key routing infrastructure of the Internet. Currently it is prone to imprudence errors and is menaced by many aggressive attacks. In recent years, the researches about security of inter-domain routing of the Internet have attracted great attentions, and are being hot research points.
Since the deployment of the secure protocol mechanisms, such as S-BGP, is confronted with many obstacles, monitoring is an effective and practical method to ensure the healthy inter-domain routing system based on the current network devices, for it is extensible and can be deployed conveniently, as well as it doesn’t have to modify the current protocol. In this paper, we propose a hierarchical monitoring model ISP-View for inter-domain routing system, which can detect anomalous routes and avoid the deficiencies of other monitoring systems. Some key technologies about this model are also researched, and the system is designed and implemented. First, we establish the relational database model of the monitoring system and present the detailed design of database, which includes database of the network knowledge, database of the Internet model, database of the Internet BGP routing information and anomaly routing, database of the local BGP routing information and anormoulas routing. We mainly focus on the compression of the route tables: for compression of a single route table, we perform the data base normalization by partitioning the relations; for multiple route tables, we propose a delta lossless compression algorithm which is based on time stamp which facilitates the joint analysis and detection among different route tables.
Anomaly detection of high performance is implemented in our system. We apply the syntactic and semantic analysis in BGP routing tables, and classify anomaly detection rules into strategic rules, general rules and special rules. Then we design and implement of the anomaly detection engine based on these rules. By the single-view checking, multi-view checking and local application strategy checking, we establish the routing anomaly database.
For visualization of detection results, we improve the topological display model, and propose a spring-field model of the dynamic displaying of the network topology map. By applying our algorithm into ISP-View, The network topologies can be displayed in different levels so as to show the routing system safety dynamically and monitor the abnormal behavior of the Inter-domain Routing system. Simulated annealing algorithm is applied to static topology offline display in our system.
Finally, we present the detailed design of the inter-domain routing monitoring system. A prototype of the Internet BGP routing monitoring is implemented and some application examples are presented in the end of this paper.
由于S-BGP等安全协议机制的部署存在重重障碍,要基于现有网络设备确保域间路由系统的健康,域间路由监测是非常实际和真正能够发挥效用的技术途径,它具有可扩展性好、方便部署以及不需对现有协议修改等特点。本文针对现有域间路由监测系统的不足,提出了一种域间路由安全监测系统ISP-View的层次模型,研究该模型下的若干关键技术,设计并实现了该监测系统。
建立了监测系统的关系数据库模型,给出了网络知识库、Internet模型库、Internet域间路由信息与异常库、本地BGP路由信与异常库的详细设计。着重研究了路由表的压缩存储:对单个路由表内部,通过关系拆分对数据库模型进行规范化处理,去除了关系内部的数据冗余;对多个路由表之间的压缩提出了一种基于时间戳的增量式无损压缩算法,新增的时间戳字段方便了多路由表的联合分析和检测。
系统实现了对路由表的高效检测。通过对BGP路由表的语法和语义分析,将BGP路由表中的异常检测规则分为战略性规则、一般规则和特殊规则,设计并实现了基于异常检测规则的检测引擎,对路由信息库进行单视图异常检测、多视图异常检测和本地应用策略检查,构造路由信息异常库。
改进了现有的基于力学模型的拓扑展示计算模型,提出了基于磁场-弹簧的力学模型实现网络拓扑图的动态展示。将算法应用于ISP-View中,可以展示不同粒度下的网络拓扑结构,动态显示路由系统的安全状态,实现对域间路由的异常行为的安全监测。将模拟退火算法用于ISP-View中大规模拓扑的离线静态拓扑展示。
最后,给出了域间路由监测系统的详细设计,实现了一个Internet域间路由监测系统原型——ISP-View,并给出了系统ISP-View的一些应用实例。
National economy and society development become more dependent on the global Internet. Inter-domain routing system based on BGP is the key routing infrastructure of the Internet. Currently it is prone to imprudence errors and is menaced by many aggressive attacks. In recent years, the researches about security of inter-domain routing of the Internet have attracted great attentions, and are being hot research points.
Since the deployment of the secure protocol mechanisms, such as S-BGP, is confronted with many obstacles, monitoring is an effective and practical method to ensure the healthy inter-domain routing system based on the current network devices, for it is extensible and can be deployed conveniently, as well as it doesn’t have to modify the current protocol. In this paper, we propose a hierarchical monitoring model ISP-View for inter-domain routing system, which can detect anomalous routes and avoid the deficiencies of other monitoring systems. Some key technologies about this model are also researched, and the system is designed and implemented. First, we establish the relational database model of the monitoring system and present the detailed design of database, which includes database of the network knowledge, database of the Internet model, database of the Internet BGP routing information and anomaly routing, database of the local BGP routing information and anormoulas routing. We mainly focus on the compression of the route tables: for compression of a single route table, we perform the data base normalization by partitioning the relations; for multiple route tables, we propose a delta lossless compression algorithm which is based on time stamp which facilitates the joint analysis and detection among different route tables.
Anomaly detection of high performance is implemented in our system. We apply the syntactic and semantic analysis in BGP routing tables, and classify anomaly detection rules into strategic rules, general rules and special rules. Then we design and implement of the anomaly detection engine based on these rules. By the single-view checking, multi-view checking and local application strategy checking, we establish the routing anomaly database.
For visualization of detection results, we improve the topological display model, and propose a spring-field model of the dynamic displaying of the network topology map. By applying our algorithm into ISP-View, The network topologies can be displayed in different levels so as to show the routing system safety dynamically and monitor the abnormal behavior of the Inter-domain Routing system. Simulated annealing algorithm is applied to static topology offline display in our system.
Finally, we present the detailed design of the inter-domain routing monitoring system. A prototype of the Internet BGP routing monitoring is implemented and some application examples are presented in the end of this paper.
引文
[1] Y. Rekhter and T. Li.A Border Gateway Protocol.RFC 1771 (BGP version 4).1995
[2] B. Halabi, Internet Routing Architectures. Cisco Press, second edition. 2001
[3] Barry Raveendran Greene.BGPv4 Security Risk Assessment. http://www.cisco.com/public/cons/isp/essentials/.June 11, 2002
[4] R. Bush T, Griffin Z, Morley Mao. Route Flap Damping: Harmful? NANOG 25.October 2002
[5] J. Cowie, A. Ogielski, B. Premore, Y. Yuan.Global Routing Instabilities during Code Red II and Nimda Worm Propagation. http://www.renesys.com /projects/bgp_instability
[6] Greene B R, and Smith P.BGP risk assessment[EB/OL]. http://www.nanog.org/mtg-0206/ppt/BGP-Risk-Assesment-v.5.pdf.
[7] http://bgp.potaroo.net/as1221/bgp-active.html
[8] URL ftp://ftp-eng.cisco.com/sobgp/index.htm
[9] Meeting Notes from S-BGP Oregon Workshop. http://www.net-tech.bbn.com/sbgp/021030.OregonWorkshopNotes.html, October 2002.
[10] V. Gill, et al.The BGP TTL Security Hack (BTSH) draft-gill-btsh-01.txt.December 2002
[11] Ng James, Extensions to BGP to Support Secure Origin BGP (soBGP) draft-ng-sobgp-bgp-extensions- 01.txt. November 2002
[12] Kruegel C, Mutz D, Robertson S, et al.Topology-based detection of anomalous BGP messages[A] . In 6th Symposium on Recent Advances in Intrusion Detection(RAID)[C]. USA. 17-35.September 2003
[13] Renesys Corp. Real Time Monitoring of Global Internet Routing[EB/OL]. http://www.renesys.com/services.html
[14] http://bgpview.6test.edu.cn/bgp-view/index.shtml
[15] http://www.routeviews.org/
[16] L. Colitti, G. Di Battista, F. Mariani, M. Patrignani and M. Pizzonia, Visualizing Interdomain Routing with BGPlay.in Journal of Graph Algorithms and Applications, Special Issue on the 2003 Symposium on Graph Drawing, GD '03. Vol. 9, no. 1, p. 117-148.2005
[17] M. Lad, L. Zhang, D. Massey.Link-Rank: A Graphical Tool for Capturing BGP Routing Dynamics. in IEEE/IFIP NOMS, Seoul, Korea.April 2004
[18] Ge Z, Figueiredo D, Jaiwal S, and et al. On the hierarchical structure of the logical Internet graph [A] . Proceedings of SPIE ITCOM[C], USA. August 2001
[19] Subramanian L, Agarwal S, Rexford J, et al. Characterizing the Internet hierarchy frommultiple vantage points [A]. Proceedings of IEEE Infocom[C], 594-604, New York, USA. 2002
[20] Zhu P D, Liu X. An Efficient Algorithm to Infer the Internet Hierarchy [A]. Advances on Computer Architecture, ACA’04[C]. Jinan, 358-361. August 2004
[21] L. Gao. On inferring autonomous system relationships in the Internet[J]. IEEE/ACM Transactions on Networking, vol. 9, no. 6. 733–745. Dec, 2000
[22] Battista G, Patrignani M, and Pizzonia M. Computing the types of the relationships between autonomous systems [A]. Proceedings of IEEE Infocom[C],California, USA. 2003
[23] 朱培栋, 蔡开裕, 刘欣等. 基于多视图的域间路由异常检测方法. 国家发明专利. 申请号: 200410046857.3
[24] Kruegel C, Mutz D, Robertson S, et al. Topology-based detection of anomalous BGP messages[A]. In 6th Symposium on Recent Advances in Intrusion Detection (RAID) [C], 17-35.USA. September 2003
[25] 朱培栋, 刘欣. 一个推断Internet互连层次结构的有效算法. 《高技术通讯(A)》, 14(A), 358-361. 2004 年 8 月
[26] C. Alaettinoglu. Scalable router configuration for the Internet. In Proc. IEEE IC3N. October 1996
[27] Norton, W.B. (2000), Internet service providers and peering, Available on request from: http://www.equinix,com/press/whtppr.htm
[28] 刘欣. 域间路由安全监测. 国防科技大学计算机学院硕士学位论文. 2004 年
[29] D.A. Huffman. A Method for the Construction of Minimum-Redundancy Codes. In Proc. of IRE, pp. 1098-1101. 1952
[30] Glen G, Langdon Jr. An introduction to arithmetic coding. IBM J. Res. Develop, 28(2):135--149. March 1984
[31] Ziv J, Lempel A. A Universal Algorithm for Sequential Data Compression. IEEE Transactions on Information Theory, Vol. 23, No. 3, pp. 337-343
[32] O’Connell SJ, Winterbottom N. Performing joins without decompression in a compressed database system. ACM SIGMOD Record, 32(1):55-67. 2003
[33] Berchtold S. Independent quantization: An index compression technique for high dimensional data space. In: Proc. of the 16th Int’l Conf. on Data Engineering, New Orleans: IEEE Computer Science Society Press, 577-588. 2000
[34] NG WK, Ravishhankar CV. Relational database compression using augmented vector quantization. Int’l Conf. on Data Engineering, New Orleans: IEEE Computer Science Society Press, 540-549.1995
[35] 骆吉洲, 李建中. 一种有效的关系数据库压缩方法. 软件学报. Vol.16, No.2. 2005
[36] Poess M, Potapov D. Data compression in oracle. In: Freytag JC, Lockemann PC, eds. Proc. of the 29th Int’l Conf. on Very Large Data Bases, Mumbai: Morgan Kaufmann Publishers, Inc, 937-947. 2003
[37] T. Suel, N. Memon. Algorithms for delta compression and remote file synchronization, In Khalid Sayood, editor, Lossless Compression Handbook, Academic Press, to appear. 2002
[38] Zan Ouyang, Nasir Memon, Torsten Suel. Dimitre Trendafilov. Cluster-Based Delta Compression of a Collection of Files. CIS Department. Polytechnic University. Brooklyn, NY 11201
[39] K. Butler, T. Farley, P. McDaniel, and J. Rexford. A Survey of. BGP Security. Technical Report TD-5UGJ33, ATT Labs - Research, Florham Park, NJ. February 2004, (Revised April 2005)
[40] TMJ Fruchtermann, EM Reingold. Graph drawing by force-directed placement. Software-Practice and Experience, Vol. 21, No. 11, pp. 1129-1164. 1991
[41] P. Eades. A heuristic for graph drawing. Congressus Nutnerantiunt, 42, 149–160. 1984
[42] Sugiyama K, Misue, K. Graph drawing by magnetic spring model. Journal of Visual Languages and Computing, Vol.6, No.3, pages 217---231. 1995
[43] R. Davidson, D. Harel. Drawing graphs nicely using simulated annealing. ACM Transactions on Graphics, 15(4):301--331. 1996
[44] Andre MS Barreto, Helio JC Barbosa. Graph Layout Using a Genetic Algorithm. Laboratorio Nacional de Computa??ao Cient? fica, CP 95113 CEP: 25651-070
[2] B. Halabi, Internet Routing Architectures. Cisco Press, second edition. 2001
[3] Barry Raveendran Greene.BGPv4 Security Risk Assessment. http://www.cisco.com/public/cons/isp/essentials/.June 11, 2002
[4] R. Bush T, Griffin Z, Morley Mao. Route Flap Damping: Harmful? NANOG 25.October 2002
[5] J. Cowie, A. Ogielski, B. Premore, Y. Yuan.Global Routing Instabilities during Code Red II and Nimda Worm Propagation. http://www.renesys.com /projects/bgp_instability
[6] Greene B R, and Smith P.BGP risk assessment[EB/OL]. http://www.nanog.org/mtg-0206/ppt/BGP-Risk-Assesment-v.5.pdf.
[7] http://bgp.potaroo.net/as1221/bgp-active.html
[8] URL ftp://ftp-eng.cisco.com/sobgp/index.htm
[9] Meeting Notes from S-BGP Oregon Workshop. http://www.net-tech.bbn.com/sbgp/021030.OregonWorkshopNotes.html, October 2002.
[10] V. Gill, et al.The BGP TTL Security Hack (BTSH) draft-gill-btsh-01.txt.December 2002
[11] Ng James, Extensions to BGP to Support Secure Origin BGP (soBGP) draft-ng-sobgp-bgp-extensions- 01.txt. November 2002
[12] Kruegel C, Mutz D, Robertson S, et al.Topology-based detection of anomalous BGP messages[A] . In 6th Symposium on Recent Advances in Intrusion Detection(RAID)[C]. USA. 17-35.September 2003
[13] Renesys Corp. Real Time Monitoring of Global Internet Routing[EB/OL]. http://www.renesys.com/services.html
[14] http://bgpview.6test.edu.cn/bgp-view/index.shtml
[15] http://www.routeviews.org/
[16] L. Colitti, G. Di Battista, F. Mariani, M. Patrignani and M. Pizzonia, Visualizing Interdomain Routing with BGPlay.in Journal of Graph Algorithms and Applications, Special Issue on the 2003 Symposium on Graph Drawing, GD '03. Vol. 9, no. 1, p. 117-148.2005
[17] M. Lad, L. Zhang, D. Massey.Link-Rank: A Graphical Tool for Capturing BGP Routing Dynamics. in IEEE/IFIP NOMS, Seoul, Korea.April 2004
[18] Ge Z, Figueiredo D, Jaiwal S, and et al. On the hierarchical structure of the logical Internet graph [A] . Proceedings of SPIE ITCOM[C], USA. August 2001
[19] Subramanian L, Agarwal S, Rexford J, et al. Characterizing the Internet hierarchy frommultiple vantage points [A]. Proceedings of IEEE Infocom[C], 594-604, New York, USA. 2002
[20] Zhu P D, Liu X. An Efficient Algorithm to Infer the Internet Hierarchy [A]. Advances on Computer Architecture, ACA’04[C]. Jinan, 358-361. August 2004
[21] L. Gao. On inferring autonomous system relationships in the Internet[J]. IEEE/ACM Transactions on Networking, vol. 9, no. 6. 733–745. Dec, 2000
[22] Battista G, Patrignani M, and Pizzonia M. Computing the types of the relationships between autonomous systems [A]. Proceedings of IEEE Infocom[C],California, USA. 2003
[23] 朱培栋, 蔡开裕, 刘欣等. 基于多视图的域间路由异常检测方法. 国家发明专利. 申请号: 200410046857.3
[24] Kruegel C, Mutz D, Robertson S, et al. Topology-based detection of anomalous BGP messages[A]. In 6th Symposium on Recent Advances in Intrusion Detection (RAID) [C], 17-35.USA. September 2003
[25] 朱培栋, 刘欣. 一个推断Internet互连层次结构的有效算法. 《高技术通讯(A)》, 14(A), 358-361. 2004 年 8 月
[26] C. Alaettinoglu. Scalable router configuration for the Internet. In Proc. IEEE IC3N. October 1996
[27] Norton, W.B. (2000), Internet service providers and peering, Available on request from: http://www.equinix,com/press/whtppr.htm
[28] 刘欣. 域间路由安全监测. 国防科技大学计算机学院硕士学位论文. 2004 年
[29] D.A. Huffman. A Method for the Construction of Minimum-Redundancy Codes. In Proc. of IRE, pp. 1098-1101. 1952
[30] Glen G, Langdon Jr. An introduction to arithmetic coding. IBM J. Res. Develop, 28(2):135--149. March 1984
[31] Ziv J, Lempel A. A Universal Algorithm for Sequential Data Compression. IEEE Transactions on Information Theory, Vol. 23, No. 3, pp. 337-343
[32] O’Connell SJ, Winterbottom N. Performing joins without decompression in a compressed database system. ACM SIGMOD Record, 32(1):55-67. 2003
[33] Berchtold S. Independent quantization: An index compression technique for high dimensional data space. In: Proc. of the 16th Int’l Conf. on Data Engineering, New Orleans: IEEE Computer Science Society Press, 577-588. 2000
[34] NG WK, Ravishhankar CV. Relational database compression using augmented vector quantization. Int’l Conf. on Data Engineering, New Orleans: IEEE Computer Science Society Press, 540-549.1995
[35] 骆吉洲, 李建中. 一种有效的关系数据库压缩方法. 软件学报. Vol.16, No.2. 2005
[36] Poess M, Potapov D. Data compression in oracle. In: Freytag JC, Lockemann PC, eds. Proc. of the 29th Int’l Conf. on Very Large Data Bases, Mumbai: Morgan Kaufmann Publishers, Inc, 937-947. 2003
[37] T. Suel, N. Memon. Algorithms for delta compression and remote file synchronization, In Khalid Sayood, editor, Lossless Compression Handbook, Academic Press, to appear. 2002
[38] Zan Ouyang, Nasir Memon, Torsten Suel. Dimitre Trendafilov. Cluster-Based Delta Compression of a Collection of Files. CIS Department. Polytechnic University. Brooklyn, NY 11201
[39] K. Butler, T. Farley, P. McDaniel, and J. Rexford. A Survey of. BGP Security. Technical Report TD-5UGJ33, ATT Labs - Research, Florham Park, NJ. February 2004, (Revised April 2005)
[40] TMJ Fruchtermann, EM Reingold. Graph drawing by force-directed placement. Software-Practice and Experience, Vol. 21, No. 11, pp. 1129-1164. 1991
[41] P. Eades. A heuristic for graph drawing. Congressus Nutnerantiunt, 42, 149–160. 1984
[42] Sugiyama K, Misue, K. Graph drawing by magnetic spring model. Journal of Visual Languages and Computing, Vol.6, No.3, pages 217---231. 1995
[43] R. Davidson, D. Harel. Drawing graphs nicely using simulated annealing. ACM Transactions on Graphics, 15(4):301--331. 1996
[44] Andre MS Barreto, Helio JC Barbosa. Graph Layout Using a Genetic Algorithm. Laboratorio Nacional de Computa??ao Cient? fica, CP 95113 CEP: 25651-070