More Web Proxy on the site http://driver.im/

Article

Detecting BGP configuration faults with static analysis

Authors:

Hari BalakrishnanAuthors Info & Claims

NSDI'05: Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation - Volume 2

Pages 43 - 56

Published: 02 May 2005 Publication History

Publisher Site Get Access

Abstract

The Internet is composed of many independent autonomous systems (ASes) that exchange reachability information to destinations using the Border Gateway Protocol (BGP). Network operators in each AS configure BGP routers to control the routes that are learned, selected, and announced to other routers. Faults in BGP configuration can cause forwarding loops, packet loss, and unintended paths between hosts, each of which constitutes a failure of the Internet routing infrastructure.

This paper describes the design and implementation of rcc, the router configuration checker, a tool that finds faults in BGP configurations using static analysis. rcc detects faults by checking constraints that are based on a high-level correctness specification. rcc detects two broad classes of faults: route validity faults, where routers may learn routes that do not correspond to usable paths, and path visibility faults, where routers may fail to learn routes for paths that exist in the network. rcc enables network operators to test and debug configurations before deploying them in an operational network, improving on the status quo where most faults are detected only during operation. rcc has been downloaded by more than sixty-five network operators to date, some of whom have shared their configurations with us. We analyze network-wide configurations from 17 different ASes to detect a wide variety of faults and use these findings to motivate improvements to the Internet routing infrastructure.

References

[1]

{1} BASU, A., ET AL. Route oscillations in IBGP with route reflection. In Proc. ACM SIGCOMM (Pittsburgh, PA, Aug. 2002).]]

Digital Library

[2]

{2} BATES, T., CHANDRA, R., AND CHEN, E. BGP Route Reflection - An Alternative to Full Mesh IBGP. Internet Engineering Task Force, Apr. 2000. RFC 2796.]]

Digital Library

[3]

{3} BEIJNUM, I. V. BGP. O'Reilly and Associates, Sept. 2002.]]

Digital Library

[4]

{4} BHARGAVAN, K., OBRADOVIC, D., AND GUNTER, C. A. Formal verification of standards for distance vector routing protocols. Journal of the ACM 49, 4 (July 2002), 538-576.]]

Digital Library

[5]

{5} CAESAR, M., FEAMSTER, N., REXFORD, J., SHAIKH, A., AND VAN DER MERWE, K. Design and Implementation of a Routing Control Platform. In Proc. 2nd Symposium on Networked Systems Design and Implementation (Boston, MA, May 2005).]]

Digital Library

[6]

{6} CALDWELL, D., GILBERT, A., GOTTLIEB, J., GREENBERG, A., HJALMTYSSON, G., AND REXCORD, J. The cutting EDGE of IP router configuration. In Proc. 2nd ACM Workshop on Hot Topics in Networks (Hotnets-II) (Cambridge, MA, Nov. 2003).]]

[7]

{7} Team Cymru bogon route server project. http://www.cymru.com/BGP/bogon-rs.html.]]

[8]

{8} DUBE, R. A comparison of scaling techniques for BGP. ACM Computer Communications Review 29, 3 (July 1999), 44-46.]]

Digital Library

[9]

{9} FEAMSTER, N. Practical verification techniques for wide-area routing. In Proc. 2nd ACM Workshop on Hot Topics in Networks (Hotnets-II) (Cambridge, MA, Nov. 2003).]]

[10]

{10} FEAMSTER, N., AND BALAKRISHNAN, H. Towards a logic for wide-area Internet routing. In ACM SIGCOMM Workshop on Future Directions in Network Architecture (Karlsruhe, Germany, Aug. 2003).]]

Digital Library

[11]

{11} FEAMSTER, N., JOHARI, R., AND BALAKRISHNAN, H. Stable policy routing with provider independence. Tech. Rep. MIT-LCS-TR-981, Massachusetts Institute of Technology, Feb. 2005.]]

[12]

{12} FEAMSTER, N., JUNG, J., AND BALAKRISHNAN, H. An empirical study of "bogon" route advertisements. ACM Computer Communications Review (Nov. 2004).]]

Digital Library

[13]

{13} FEAMSTER, N., MAO, Z. M., AND REXFORD, J. BorderGuard: Detecting cold potatoes from peers. In Proc. ACM SIGCOMM Internet Measurement Conference (Taormina, Sicily, Italy, Oct. 2004).]]

Digital Library

[14]

{14} FEAMSTER, N., WINICK, J., AND REXFORD, J. A model of BGP routing for network engineering. In Proc. ACM SIGMETRICS (New York, NY, June 2004).]]

Digital Library

[15]

{15} FELDMANN, A., AND REXFORD, J. IP network configuration for intradomain traffic engineering. IEEE Network (Sept. 2001).]]

[16]

{16} GAO, L. On inferring automonous system relationships in the Internet. IEEE/ACM Transactions on Networking 9, 6 (Dec. 2001), 733-745.]]

Digital Library

[17]

{17} GAO, L., GRIFFIN, T. G., AND REXFORD, J. Inherently safe backup routing with BGP. In Proc. IEEE INFOCOM (Anchorage, AK, Apr. 2001).]]

[18]

{18} GODEFROID, P. Model Checking for Programming Languages using VeriSoft. In Proc. ACM Symposium on Principles of Programming Languages (1997).]]

Digital Library

[19]

{19} GRIFFIN, T., AND WILFONG, G. An analysis of BGP convergence properties. In Proc. ACM SIGCOMM (Cambridge, MA, Sept. 1999).]]

Digital Library

[20]

{20} GRIFFIN, T., AND WILFONG, G. On the correctness of IBGP configuration. In Proc. ACM SIGCOMM (Pittsburgh, PA, Aug. 2002).]]

Digital Library

[21]

{21} GRIFFIN, T. G., SHEPHERD, F. B., AND WILFONG, G. The stable paths problem and interdomain routing. IEEE/ACM Transactions on Networking 10, 1 (2002), 232-243.]]

Digital Library

[22]

{22} HAJEK, J. Automatically verified data transfer protocols. In Proc. ICCC (1978), pp. 749-756.]]

[23]

{23} LABOVITZ, C., AHUJA, A., BOSE, A., AND JAHANIAN, F. Delayed Internet Routing Convergence. IEEE/ACM Transactions on Networking 9, 3 (June 2001), 293-306.]]

Digital Library

[24]

{24} MAHAJAN, R., WETHERALL, D., AND ANDERSON, T. Understanding BGP misconfiguration. In Proc. ACM SIGCOMM (Pittsburgh, PA, Aug. 2002), pp. 3-17.]]

Digital Library

[25]

{25} MUSUVATHI, M., AND ENGLER, D. Some lessons from using static analysis and software model checking for bug finding. In Workshop on Software Model Checking (Boulder, CO, July 2003).]]

[26]

{26} MUSUVATHI, M., AND ENGLER, D. A framework for model checking network protocols. In Proc. First Symposium on Networked Systems Design and Implementation (NSDI) (San Francisco, CA, Mar. 2004).]]

Digital Library

[27]

{27} The North American Network Operators' Group mailing list archive. http://www.cctec.com/maillists/nanog/.]]

[28]

{28} NORTON, W. Internet service providers and peering. http://www.equinix.com/press/whtppr.htm.]]

[29]

{29} Opnet NetDoctor. http: //opnet.com/products/modules/netdoctor.htm.]]

[30]

{30} Really Awesome New Cisco ConfIg Differ (RANCID). http://www.shrubbery.net/rancid/, 2004.]]

[31]

{31} REKHTER, Y., AND LI, T. A Border Gateway Protocol 4 (BGP-4). Internet Engineering Task Force, Mar. 1995. RFC 1771.]]

Digital Library

[32]

{32} Router Glitch Cuts Net Access. http://news.com.com/2100-1033-279235.html, Apr. 1997.]]

[33]

{33} SPRING, N., MAHAJAN, R., AND ANDERSON, T. Quantifying the causes of path inflation. In Proc. ACM SIGCOMM (Karlsruhe, Germany, Aug. 2003).]]

Digital Library

[34]

{34} BGP config donation. http://www.cs.washington.edu/research/ networking/policy-inference/donation.html.]]

[35]

{35} VARADHAN, K., GOVINDAN, R., AND ESTRIN, D. Persistent route oscillations in inter-domain routing. Computer Networks 32, 1 (2000), 1-16.]]

Cited By

Das SKim DAbbott JCamp LFarzan RLópez CCardoso Llach DQuercia DMustafa MNiu SWong-Villacrés M(2024)User-Centered Phishing Detection through Personalized Edge ComputingCompanion Publication of the 2024 Conference on Computer-Supported Cooperative Work and Social Computing10.1145/3678884.3681864(283-287)Online publication date: 11-Nov-2024
https://dl.acm.org/doi/10.1145/3678884.3681864
Wang DZhang PGember-Jacobson ASekar VYu MSeneviratne AVeitch D(2024)Expresso: Comprehensively Reasoning About External Routes Using Symbolic SimulationProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672220(197-212)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672220
Tang ABeckett RBenaloh SJayaraman KPatil TMillstein TVarghese GSchulzrinne HKohler EMaltz DMisra V(2023)Lightyear: Using Modularity to Scale BGP Control Plane VerificationProceedings of the ACM SIGCOMM 2023 Conference10.1145/3603269.3604842(94-107)Online publication date: 10-Sep-2023
https://dl.acm.org/doi/10.1145/3603269.3604842
Show More Cited By

Index Terms

Detecting BGP configuration faults with static analysis

Recommendations

BGP skeleton: an alternative to iBGP route reflection
INFOCOM'10: Proceedings of the 29th conference on Information communications

The Internet is a composition of ASes (Autonomous Systems), BGP (Border Gateway Protocol) is the routing protocol that is responsible of exchanging routes between these ASes. It operates in two modes: External BGP (eBGP) and Internal BGP (iBGP). EBGP ...
Neighbor-specific BGP: more flexible routing policies while improving global stability
SIGMETRICS '09

The Border Gateway Protocol (BGP) offers network administrators considerable flexibility in controlling how traffic flows through their networks. However, the interaction between routing policies in different Autonomous Systems (ASes) can lead to ...
Multiple route selector BGP (MRS-BGP)
ICWET '10: Proceedings of the International Conference and Workshop on Emerging Trends in Technology

To maximize the utilization of network resources it is necessary to have good approach for Routing Policy. The protocol currently used for Interdomain Routing is Border Gateway Protocol (BGP). BGP permits each router to use single best route for each ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

NSDI'05: Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation - Volume 2

May 2005

356 pages

Sponsors

Publisher

USENIX Association

United States

Publication History

Published: 02 May 2005

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

136
Total Citations
View Citations
699
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)2

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Das SKim DAbbott JCamp LFarzan RLópez CCardoso Llach DQuercia DMustafa MNiu SWong-Villacrés M(2024)User-Centered Phishing Detection through Personalized Edge ComputingCompanion Publication of the 2024 Conference on Computer-Supported Cooperative Work and Social Computing10.1145/3678884.3681864(283-287)Online publication date: 11-Nov-2024
https://dl.acm.org/doi/10.1145/3678884.3681864
Wang DZhang PGember-Jacobson ASekar VYu MSeneviratne AVeitch D(2024)Expresso: Comprehensively Reasoning About External Routes Using Symbolic SimulationProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672220(197-212)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672220
Tang ABeckett RBenaloh SJayaraman KPatil TMillstein TVarghese GSchulzrinne HKohler EMaltz DMisra V(2023)Lightyear: Using Modularity to Scale BGP Control Plane VerificationProceedings of the ACM SIGCOMM 2023 Conference10.1145/3603269.3604842(94-107)Online publication date: 10-Sep-2023
https://dl.acm.org/doi/10.1145/3603269.3604842
Alberdingk Thijm TBeckett RGupta AWalker D(2023)Modular Control Plane Verification via Temporal InvariantsProceedings of the ACM on Programming Languages10.1145/35912227:PLDI(50-75)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591222
Tang AKakarla SBeckett RZhai EBrown MMillstein TTamir YVarghese GKuipers FCaesar M(2021)CampionProceedings of the 2021 ACM SIGCOMM 2021 Conference10.1145/3452296.3472925(748-761)Online publication date: 9-Aug-2021
https://dl.acm.org/doi/10.1145/3452296.3472925
Xiang CHuang HYoo AZhou YPasupathy SGavrilovska AZadok E(2020)PracExtractorProceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference10.5555/3489146.3489164(265-280)Online publication date: 15-Jul-2020
https://dl.acm.org/doi/10.5555/3489146.3489164
Hu YHuang GHuang PLu SHowell J(2020)Automated reasoning and detection of specious configuration in large systems with symbolic executionProceedings of the 14th USENIX Conference on Operating Systems Design and Implementation10.5555/3488766.3488807(719-734)Online publication date: 4-Nov-2020
https://dl.acm.org/doi/10.5555/3488766.3488807
Kakarla STang ABeckett RJayaraman KMillstein TTamir YVarghese GBhagwan RPorter G(2020)Finding network misconfigurations by automatic template inferenceProceedings of the 17th Usenix Conference on Networked Systems Design and Implementation10.5555/3388242.3388313(999-1014)Online publication date: 25-Feb-2020
https://dl.acm.org/doi/10.5555/3388242.3388313
Zhang PLiu XYang HKang NGu ZLi HBhagwan RPorter G(2020)APKeepProceedings of the 17th Usenix Conference on Networked Systems Design and Implementation10.5555/3388242.3388259(241-256)Online publication date: 25-Feb-2020
https://dl.acm.org/doi/10.5555/3388242.3388259
Bahnasy MLi FXiao SCheng X(2020)DeepBGPProceedings of the Workshop on Network Meets AI & ML10.1145/3405671.3405816(48-55)Online publication date: 10-Aug-2020
https://dl.acm.org/doi/10.1145/3405671.3405816
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents