kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Computational complexity of traffic hijacking under BGP and S-BGP
Roma Tre University, Italy.ORCID iD: 0000-0002-9675-9729
2012 (English)In: Automata, Languages, and Programming: 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II, Springer, 2012, Vol. 7392, no PART 2, p. 476-487Conference paper, Published paper (Refereed)
Abstract [en]

Harmful Internet hijacking incidents put in evidence how fragile the Border Gateway Protocol (BGP) is, which is used to exchange routing information between Autonomous Systems (ASes). As proved by recent research contributions, even S-BGP, the secure variant of BGP that is being deployed, is not fully able to blunt traffic attraction attacks. Given a traffic flow between two ASes, we study how difficult it is for a malicious AS to devise a strategy for hijacking or intercepting that flow. We show that this problem marks a sharp difference between BGP and S-BGP. Namely, while it is solvable, under reasonable assumptions, in polynomial time for the type of attacks that are usually performed in BGP, it is NP-hard for S-BGP. Our study has several by-products. E. g., we solve a problem left open in the literature, stating when performing a hijacking in S-BGP is equivalent to performing an interception.

Place, publisher, year, edition, pages
Springer, 2012. Vol. 7392, no PART 2, p. 476-487
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 7392
National Category
Communication Systems Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-222335DOI: 10.1007/978-3-642-31585-5_43ISI: 000342761300043Scopus ID: 2-s2.0-84872101229ISBN: 978-3-642-31585-5 (print)OAI: oai:DiVA.org:kth-222335DiVA, id: diva2:1180757
Conference
39th International Colloquium on Automata, Languages, and Programming, ICALP 2012, Warwick, United Kingdom, 9 July 2012 through 13 July 2012
Note

QC 20180207

Available from: 2018-02-06 Created: 2018-02-06 Last updated: 2024-03-15Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Chiesa, Marco

Search in DiVA

By author/editor
Chiesa, Marco
Communication SystemsComputer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 96 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf