skip to main content
10.1145/2342356.2342434acmconferencesArticle/Chapter ViewAbstractPublication PagescommConference Proceedingsconference-collections
research-article
Free access

Private and verifiable interdomain routing decisions

Published: 13 August 2012 Publication History

Abstract

Existing secure interdomain routing protocols can verify validity properties about individual routes, such as whether they correspond to a real network path. It is often useful to verify more complex properties relating to the route decision procedure - for example, whether the chosen route was the best one available, or whether it was consistent with the network's peering agreements. However, this is difficult to do without knowing a network's routing policy and full routing state, which are not normally disclosed. In this paper, we show how a network can allow its peers to verify a number of nontrivial properties of its interdomain routing decisions without revealing any additional information. If all the properties hold, the peers learn nothing beyond what the interdomain routing protocol already reveals; if a property does not hold, at least one peer can detect this and prove the violation. We present SPIDeR, a practical system that applies this approach to the Border Gateway Protocol, and we report results from an experimental evaluation to demonstrate that SPIDeR has a reasonable overhead.

Supplementary Material

JPG File (sigcomm-ix-01-privateandverifiableinterdomainroutingdecisions.jpg)
MP4 File (sigcomm-ix-01-privateandverifiableinterdomainroutingdecisions.mp4)

References

[1]
AS relationships dataset from CAIDA. http://www.caida.org/data/active/as-relationships/.
[2]
O. Bonaventure and B. Quoitin. Common utilizations of the BGP community attribute. Internet draft, 2003.
[3]
E. Chen and T. Bates. An application of the BGP community attribute in multi-home routing. RFC 1998, Aug 1996.
[4]
X. Dimitropoulos, D. Krioukov, M. Fomenkov, B. Huffaker, Y. Hyun, kc claffy, and G. Riley. AS Relationships: Inference and Validation. ACM SIGCOMM CCR, (1):29--40, Jan 2007.
[5]
B. Donnet and O. Bonaventure. On BGP communities. ACM CCR, 38(2):55--59, April 2008.
[6]
P. Faratin, D. Clark, P. Gilmore, S. Bauer, A. Berger, and W. Lehr. Complexity of Internet interconnections: Technology, incentives and implications for policy. In Proc. 35th Annual Telecomm. Policy Research Conf. (TPRC), Sept. 2007.
[7]
N. Feamster, Z. M. Mao, and J. Rexford. BorderGuard: Detecting cold potatoes from peers. In Proc. IMC, Oct. 2004.
[8]
L. Gao. On inferring autonomous system relationships in the Internet. IEEE/ACM ToN, 9:733--745, Dec. 2001.
[9]
L. Gao and J. Rexford. Stable Internet routing without global coordination. IEEE/ACM ToN, 9(6):681--692, Dec. 2001.
[10]
M. Garofalakis, J. Hellerstein, and P. Maniatis. Proof sketches: Verifiable in-network aggregation. In Proc. ICDE, Apr. 2007.
[11]
S. Goldberg, S. Halevi, A. Jaggard, V. Ramachandran, and R. Wright. Rationality and traffic attraction: Incentives for honestly announcing paths in BGP. In Proc. ACM SIGCOMM, Aug. 2008.
[12]
S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1):186--208, 1989.
[13]
A. J. T. Gurney, A. Haeberlen, W. Zhou, M. Sherr, and B. T. Loo. Having your cake and eating it too: Routing security with privacy protections. In Proc. HotNets, Nov. 2011.
[14]
A. Haeberlen, I. Avramopoulos, J. Rexford, and P. Druschel. NetReview: Detecting when interdomain routing goes wrong. In Proc. NSDI, Apr 2009.
[15]
IETF Working Group on Secure Inter-domain Routing. http://tools.ietf.org/wg/sidr.
[16]
A. J. Kalafut, C. A. Shue, and M. Gupta. Malicious hubs: detecting abnormally malicious autonomous systems. In Proc. INFOCOM, Mar. 2010.
[17]
S. Kent, C. Lynn, and K. Seo. Secure border gateway protocol (S-BGP). IEEE JSAC, 18(4):582--592, 2000.
[18]
W. Kumari and S. Kotikalapudi. Recommendation for not using AS\_SET and AS\_CONFED\_SET in BGP. RFC 6472.
[19]
H. V. Madhyastha, E. Katz-Bassett, T. Anderson, A. Krishnamurthy, and A. Venkataramani. iPlane Nano: path prediction for peer-to-peer applications. In Proc. NSDI, Apr. 2009.
[20]
R. Mahajan, M. Rodrig, D. Wetherall, and J. Zahorjan. Sustaining cooperation in multi-hop wireless networks. In Proc. NSDI, May 2005.
[21]
R. Mahajan, D. Wetherall, and T. Anderson. Understanding BGP misconfiguration. In Proc.\ ACM SIGCOMM, Sep 2002.
[22]
R. Merkle. Protocols for public key cryptosystems. In Proc. Symposium on Security and Privacy, Apr. 1980.
[23]
S. Micali, M. Rabin, and J. Kilian. Zero-knowledge sets. In Proc. FOCS, Oct. 2003.
[24]
W. Mühlbauer, A. Feldmann, O. Maennel, M. Roughan, and S. Uhlig. Building an AS-topology model that captures route diversity. In Proc. ACM SIGCOMM, Sept. 2006.
[25]
S. Nagaraja, V. Jalaparti, M. Caesar, and N. Borisov. P3CA: Private anomaly detection across ISP networks. In Proc. Privacy Enhancing Technologies Symposium (PETS), July 2011.
[26]
J. Nagle. Congestion control in IP/TCP internetworks. RFC 896, Jan 1984.
[27]
O. Nordstroem and C. Dovrolis. Beware of BGP attacks. ACM CCR, 34(2):1--8, Apr. 2004.
[28]
W. B. Norton. A study of 28 peering policies. Technical report, DrPeering International.
[29]
One Step Consulting, Inc. BGP community guides. http://onesc.net/communities, 2012.
[30]
N. Patrick, T. Scholl, A. Shaikh, and R. Steenbergen. Peering Dragnet: anti-social behavior amongst peers, and what you can do about it. NANOG 38, 2006.
[31]
M. O. Rabin, R. A. Servedio, and C. Thorpe. Highly efficient secrecy-preserving proofs of correctness of computations and applications. In Proc. LICS, July 2007.
[32]
Y. Rekhter, T. Li, and S. Hares. A border gateway protocol 4 (BGP-4). RFC 4271, Jan 2006.
[33]
M. Roughan, W. Willinger, O. Maennel, D. Perouli, and R. Bush. 10 lessons from 10 years of measuring and modelling the Internet's Autonomous Systems. IEEE JSAC, 29(9):1810--1821, 2011.
[34]
R. Sherwood, A. Bender, and N. Spring. DisCarte: a disjunctive Internet cartographer. In Proc. SIGCOMM, Aug. 2008.
[35]
P. Smith, R. Evans, and M. Hughes. Recommendations on route aggregation. Technical Report RIPE-399, RIPE Routing Working Group, Dec. 2006.
[36]
P. Traina and R. Chandrasekeran. BGP communities attribute. RFC 1997, Aug 1996.
[37]
P. C. van Oorschot, T. Wan, and E. Kranakis. On interdomain routing security and pretty secure BGP (psBGP). ACM TISSEC, 10(3), 2007.
[38]
C. Villamizar, R. Chandra, and R. Govindan. BGP route flap damping. RFC 2439, Nov 1998.
[39]
F. Wang and L. Gao. On inferring and characterizing Internet routing policies. In Proc. IMC, Oct. 2003.
[40]
R. White. Securing BGP through Secure Origin BGP. The Internet Protocol Journal, 6(3):15--22, 2006.
[41]
E. L. Wong, P. Balasubramanian, L. Alvisi, M. G. Gouda, and V. Shmatikov. Truth in advertising: lightweight verification of route integrity. In Proc. PODC, Aug. 2007.
[42]
J. Wu, Z. M. Mao, J. Rexford, and J. Wang. Finding a needle in a haystack: Pinpointing significant BGP routing changes in an IP network. In Proc. NSDI, May 2005.
[43]
M. Zhao, W. Zhou, A. J. T. Gurney, A. Haeberlen, M. Sherr, and B. T. Loo. Private and verifiable interdomain routing decisions. Technical Report MS-CIS-12--10, U. Penn, 2012.

Cited By

View all
  • (2021)Building In-the-Cloud Network Functions: Security and Privacy ChallengesProceedings of the IEEE10.1109/JPROC.2021.3127277109:12(1888-1919)Online publication date: Dec-2021
  • (2021)TRAQR: Trust aware End-to-End QoS routing in multi-domain SDN using BlockchainJournal of Network and Computer Applications10.1016/j.jnca.2021.103055182(103055)Online publication date: May-2021
  • (2020)Subgame Perfect Equilibria of Sequential Matching GamesACM Transactions on Economics and Computation10.1145/33737177:4(1-30)Online publication date: 30-Jan-2020
  • Show More Cited By

Index Terms

  1. Private and verifiable interdomain routing decisions

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SIGCOMM '12: Proceedings of the ACM SIGCOMM 2012 conference on Applications, technologies, architectures, and protocols for computer communication
    August 2012
    474 pages
    ISBN:9781450314190
    DOI:10.1145/2342356
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 13 August 2012

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. accountability
    2. fault detection
    3. privacy
    4. routing
    5. security

    Qualifiers

    • Research-article

    Conference

    SIGCOMM '12
    Sponsor:
    SIGCOMM '12: ACM SIGCOMM 2012 Conference
    August 13 - 17, 2012
    Helsinki, Finland

    Acceptance Rates

    Overall Acceptance Rate 462 of 3,389 submissions, 14%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)68
    • Downloads (Last 6 weeks)11
    Reflects downloads up to 20 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2021)Building In-the-Cloud Network Functions: Security and Privacy ChallengesProceedings of the IEEE10.1109/JPROC.2021.3127277109:12(1888-1919)Online publication date: Dec-2021
    • (2021)TRAQR: Trust aware End-to-End QoS routing in multi-domain SDN using BlockchainJournal of Network and Computer Applications10.1016/j.jnca.2021.103055182(103055)Online publication date: May-2021
    • (2020)Subgame Perfect Equilibria of Sequential Matching GamesACM Transactions on Economics and Computation10.1145/33737177:4(1-30)Online publication date: 30-Jan-2020
    • (2020)Pricing Multi-Unit MarketsACM Transactions on Economics and Computation10.1145/33737157:4(1-29)Online publication date: 30-Jan-2020
    • (2017)Incentivizing Verifiable Privacy-Protection Mechanisms for Offline Crowdsensing ApplicationsSensors10.3390/s1709202417:9(2024)Online publication date: 4-Sep-2017
    • (2017)PrIXP: Preserving the privacy of routing policies at Internet eXchange Points2017 IFIP/IEEE Symposium on Integrated Network and Service Management (IM)10.23919/INM.2017.7987309(435-441)Online publication date: May-2017
    • (2017)SIXPACKProceedings of the 13th International Conference on emerging Networking EXperiments and Technologies10.1145/3143361.3143362(120-133)Online publication date: 28-Nov-2017
    • (2017)STYXProceedings of the 2017 Symposium on Cloud Computing10.1145/3127479.3127482(201-213)Online publication date: 24-Sep-2017
    • (2016)“I Can’t Get No Satisfaction”: Helping Autonomous Systems Identify Their Unsatisfied Interdomain InterestsIEEE Transactions on Network and Service Management10.1109/TNSM.2016.252500313:1(43-57)Online publication date: Mar-2016
    • (2016)Private and verifiable interdomain routing decisionsIEEE/ACM Transactions on Networking10.1109/TNET.2015.240923324:2(1011-1024)Online publication date: 1-Apr-2016
    • Show More Cited By

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media