Please use this identifier to cite or link to this item:
Title: Computational complexity of traffic hijacking under BGP and S-BGP
Authors: Chiesa, M.
Di Battista, G.
Patrignani, M.
Erlebach, Thomas
First Published: 2012
Presented at: 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012
Publisher: Springer Berlin Heidelberg
Citation: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2012, 7392 LNCS (PART 2), pp. 476-487
Abstract: 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.
DOI Link: 10.1007/978-3-642-31585-5_43
ISSN: 0302-9743
ISBN: 978-3-642-31584-8
eISSN: 1611-3349
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
Rights: Copyright © 2012, Springer Berlin Heidelberg. Deposited with reference to the publisher’s archiving policy available on the SHERPA/RoMEO website.
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
ICALP2012FinalAuthorVersion.pdfPost-review (final submitted)248.26 kBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.