Proof of an Interdomain Policy

Authors:

Andreas Voellmy

Abstract:

Configuration of interdomain routing policies is notoriously difficult, despite their relatively simple structure. We believe that this difficulty arises in part due to the gap between a network's interdomain traffic goals and the interdomain routing policies which implement them. The gap arises because BGP policy accomplishes network goals indirectly, through interaction with the forwarding plane, and because these goals can often only be met when neighboring networks agree to implement certain policies.

We present a case study of the formal verification of a real world BGP configuration, a load-balancing multi-homed network discussed in a book on BGP configuration. We invent a formal specification from the informal description of the example and prove that the BGP policy meets this specification. The goal of this study is to make explicit and precise, the principles used in reasoning about BGP policy. We aim to show not that verification is easy, but rather that this reasoning is far from trivial and that the difficulty in configuring BGP routers may lie not in writing policy, but in understanding the effects of this policy in a complex environment. The study also illustrates some of the benefits of formal specification and verification for BGP policy, namely that such efforts help in discovering ambiguities, inconsistencies and implicit assumptions in specifications and policies.

The case study and proofs have been formalized in the Isabelle/HOL theorem prover and are available on the web.

Bibtex:

 @inproceedings{Voellmy:2009:PIP:1655062.1655071,
 author = {Voellmy, Andreas R.},
 title = {Proof of an interdomain policy: a load-balancing multi-homed network},
 booktitle = {Proceedings of the 2nd ACM workshop on Assurable and usable security configuration},
 series = {SafeConfig '09},
 year = {2009},
 isbn = {978-1-60558-778-3},
 location = {Chicago, Illinois, USA},
 pages = {37--44},
 numpages = {8},
 url = {http://doi.acm.org/10.1145/1655062.1655071},
 doi = {http://doi.acm.org/10.1145/1655062.1655071},
 acmid = {1655071},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {bgp, interdomain routing, isabelle/hol, languages, verification},
} 

Links:

safec02-voellmy.pdf