NETSEC

Internet Routing Forensics, funded by NSF

While the Internet continues to thrive, the behavior of abnormal routing events are not well understood, nor are their symptoms and how they can be detected. Although numerous studies have created systems for detecting intrusions and anomalies by investigating traffic at the Internet data plane, no similar systems have been created for routing at the control plane. This leaves a wide range of critical basic and applied research questions unanswered, particularly for routing based on the Border Gateway Protocol (BGP) -- the de facto inter-domain routing protocol on the Internet.

This research -- Internet Routing Forensics (IRF) -- aims to provide a systematic means for understanding and detecting networking anomalies from the Internet control plane by investigating a huge amount of routing data. As its first step, IRF focuses on abnormal BGP events, such as Internet worms or large-scale electricity outages that may affect the normal operation of BGP. With detection speed, accuracy and usability as the major goals, this research will build a reliable but flexible framework that can systematically process large archives of BGP data, observe and learn the patterns and effects of abnormal BGP events as well as those of normal behavior, discover rules of abnormal BGP events, and apply these rules to detect the occurrence of these events -- even if they are yet unknown.

While IRF research lies primarily in the area of networking, it is inter-disciplinary. Besides leveraging modeling techniques, mathematical methods and statistical analysis, this research will in particular leverage data mining techniques to explore the huge data space from the global and local levels, devise a novel rule processor to optimize rules produced from the data mining process, and adopt supervised machine learning and other techniques to more accurately identify abnormal routing events within a given context. We collaborate with both the Data Integration and Data Mining Lab and Advanced Network Technology Center on this topic.

Documents:

• Jun Li, Dejing Dou, Zhen Wu, Shiwoong Kim, and Vikash Agarwal, "An Internet routing forensics framework for discovering rules of abnormal BGP events," ACM SIGCOMM Computer Communication Review, vol. 35, no. 5, pp. 55-66, October 2005.
• Jun Li, Michael Guidero, Zhen Wu, Eric Purpus, and Toby Ehrenkranz, "BGP routing dynamics revisited," ACM SIGCOMM Computer Communication Review, vol. 37, no. 2, pp. 7-16, April 2007.
• Dejing Dou, Jun Li, Han Qin, Shiwoong Kim, and Sheng Zhong, "Understanding and utilizing the hierarchy of abnormal BGP events," in SIAM International Conference on Data Mining, Minneapolis, Minnesota, April 2007, pp. 457-462 (short paper), acceptance rate 24.8% (36 full papers and 39 short papers are accepted, 302 submissions).
• Dejing Dou, Jun Li, Han Qin, Yibo Wang, and Sheng Zhong, "Mining and sharing the hierarchy of abnormal BGP events," IEEE Transactions on Know ledge and Data Engineering, In submission.
• Jun Li, Dejing Dou, Shiwoong Kim, Han Qin, and Yibo Wang, "On knowledge-based classification of abnormal BGP events," in International Conference on Information Systems Security, December 2007, 19 pages. Under review.

Documents:

• Jun Li, Randy Bush, Zhuoqing Mao, Timothy Griffin, Matthew Roughan, Daniel Stutzbach, and Eric Purpus, "Watching data streams toward a multi-homed sink under routing changes introduced by a BGP beacon," in Passive and Active Measurement Conference, Adelaide, Australia, March 2006, acceptance rate 25.6% (21/82).
• Matthew Roughan, Jun Li, Randy Bush, Zhuoqing Mao, and Timothy Griffin, "Is BGP update storm a sign of trouble: Observing the Internet control and data planes during Internet worms," in Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS), Calgary, Canada, July 2006, vol. 38, pp. 535-542.

Also, we have studied the behavior of BGP during large-scale power outages, as reflected in this document:

• Jun Li, Zhen Wu, and Eric Purpus, "Toward understanding the behavior of BGP during large-scale power outages," in IEEE GLOBECOM, San Francisco, CA, November 2006, 5 pages.
• Zhen Wu, Eric S. Purpus, and Jun Li, "BGP behavior analysis during the August 2003 blackout," in The 9th IFIP/IEEE International Symposium on Integrated Network Management, Nice, France, May 2005, 4 pages (short paper).