research-article

Free access

Alibi Routing

Authors:

Cristian Lumezanu,

Bobby BhattacharjeeAuthors Info & Claims

SIGCOMM '15: Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication

Pages 611 - 624

https://doi.org/10.1145/2785956.2787509

Published: 17 August 2015 Publication History

Abstract

There are several mechanisms by which users can gain insight into where their packets have gone, but no mechanisms allow users undeniable proof that their packets did not traverse certain parts of the world while on their way to or from another host. This paper introduces the problem of finding "proofs of avoidance": evidence that the paths taken by a packet and its response avoided a user-specified set of "forbidden" geographic regions. Proving that something did not happen is often intractable, but we demonstrate a low-overhead proof structure built around the idea of what we call "alibis": relays with particular timing constraints that, when upheld, would make it impossible to traverse both the relay and the forbidden regions.

We present Alibi Routing, a peer-to-peer overlay routing system for finding alibis securely and efficiently. One of the primary distinguishing characteristics of Alibi Routing is that it does not require knowledge of--or modifications to--the Internet's routing hardware or policies. Rather, Alibi Routing is able to derive its proofs of avoidance from user-provided GPS coordinates and speed of light propagation delays. Using a PlanetLab deployment and larger-scale simulations, we evaluate Alibi Routing to demonstrate that many source-destination pairs can avoid countries of their choosing with little latency inflation. We also identify when Alibi Routing does not work: it has difficulty avoiding regions that users are very close to (or, of course, inside of).

Supplementary Material

WEBM File (p611-levin.webm)

Download
160.44 MB

References

[1]

S. Agarwal and J. R. Lorch. Matchmaking for online games and other latency-sensitive P2P systems. In ACM SIGCOMM, 2009.

Digital Library

[2]

D. G. Andersen, H. Balakrishnan, N. Feamster, T. Koponen, D. Moon, and S. Shenker. Accountable Internet Protocol (AIP). In ACM SIGCOMM, 2008.

Digital Library

[3]

D. G. Andersen, H. Balakrishnan, M. F. Kaashoek, and R. Morris. Resilient overlay networks. In ACM Symposium on Operating Systems Principles (SOSP), 2001.

Digital Library

[4]

Anonymous. The collateral damage of Internet censorship by DNS injection. ACM SIGCOMM Computer Communication Review (CCR), 42(3):21--27, 2012.

Digital Library

[5]

Anonymous. Towards a comprehensive picture of the Great Firewall's DNS censorship. USENIX Workshop on Free and Open Communications on the Internet (FOCI), 2014.

[6]

ARRL. The ARRL Handbook for Radio Communications. The ARRL, 89th edition, 2012.

[7]

S. Aryan, H. Aryan, and J. A. Halderman. Internet censorship in Iran: A first look. In USENIX Workshop on Free and Open Communications on the Internet (FOCI), 2013.

[8]

I. Clarke, O. Sandberg, B. Wiley, and T. W. Hong. Freenet: A distributed anonymous information storage and retrieval system. In Designing Privacy Enhancing Technologies: Workshop on Design Issues in Anonymity and Unobservability, pages 46--66, July 2000.

Digital Library

[9]

B. Cohen. Incentives build robustness in BitTorrent. In Workshop on Economics of Peer-to-Peer Systems (P2PEcon), 2003.

[10]

R. Dingledine, N. Mathewson, and P. Syverson. Tor: The second-generation onion router. In USENIX Security, 2004.

Digital Library

[11]

N. Feamster, M. Balazinska, G. Harfst, H. Balakrishnan, and D. Karger. Infranet: Circumventing censorship and surveillance. In USENIX Security, 2002.

Digital Library

[12]

R. Feynman, R. Leighton, and M. Sands. The Feynman Lectures on Physics Vol. 1. (Chapter 26). Addison-Wesley, 1963.

[13]

Global Administrative Areas (GADM) Database. http://www.gadm.org.

[14]

P. B. Godfrey, I. Ganichev, S. Shenker, and I. Stoica. Pathlet Routing. In ACM SIGCOMM, 2009.

Digital Library

[15]

K. Gummadi, H. Madhyastha, S. D. Gribble, H. M. Levy, and D. J. Wetherall. Improving the reliability of Internet paths with one-hop source routing. In Symposium on Operating Systems Design and Implementation (OSDI), 2004.

Digital Library

[16]

A. Haeberlen, P. Kuznetsov, and P. Druschel. PeerReview: Practical accountability for distributed systems. In ACM Symposium on Operating Systems Principles (SOSP), 2007.

Digital Library

[17]

A. Houmansadr, G. T. K. Nguyen, M. Caesar, and N. Borisov. Cirripede: Circumvention infrastructure using router redirection with plausible deniability. In ACM Conference on Computer and Communications Security (CCS), 2011.

Digital Library

[18]

J. Karlin, D. Ellard, A. W. Jackson, C. E. Jones, G. Lauer, D. P. Mankins, and W. T. Strayer. Decoy routing: Toward unblockable Internet communication. In USENIX Workshop on Free and Open Communications on the Internet (FOCI), 2011.

[19]

J. Karlin, S. Forrest, and J. Rexford. Nation-state routing: Censorship, wiretapping, and BGP. http://arxiv.org/pdf/0903.3218.pdf, Mar. 2009.

[20]

B. Karp and H. T. Kung. GPSR: greedy perimeter stateless routing for wireless networks. In ACM Conference on Mobile Computing and Networking (MobiCom), 2000.

Digital Library

[21]

E. Katz-Bassett, C. Scott, D. R. Choffnes, Ítalo Cunha, V. Valancius, N. Feamster, H. V. Madhyastha, T. Anderson, and A. Krishnamurthy. LIFEGUARD: Practical repair of persistent route failures. In ACM SIGCOMM, 2012.

Digital Library

[22]

T. H.-J. Kim, C. Basescu, L. Jia, S. B. Lee, Y.-C. Hu, and A. Perrig. Lightweight Source Authentication and Path Validation. In ACM SIGCOMM, 2014.

Digital Library

[23]

E. Kline and P. Reiher. Securing data through avoidance routing. In New Security Paradigms Workshop (NSPW), 2009.

Digital Library

[24]

D. Levin, A. Bender, C. Lumezanu, N. Spring, and B. Bhattacharjee. Boycotting and extorting nodes in an internetwork. In Joint Workshop on the Economics of Networked Systems and Incentive-Based Computing (NetEcon+IBC), 2007.

[25]

C. Lumezanu, R. Baden, D. Levin, B. Bhattacharjee, and N. Spring. Symbiotic relationships in Internet routing overlays. In USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2009.

Digital Library

[26]

MaxMind, Inc. http://dev.maxmind.com/geoip/legacy/geolite/.

[27]

S. J. Murdoch and P. Zieli\'nski. Sampled traffic analysis by Internet-exchange-level adversaries. In Workshop on Privacy Enhancing Technologies (PET), 2007.

Digital Library

[28]

J. Naous, M. Walfish, A. Nicolosi, M. Miller, and A. Seehra. Verifying and enforcing network paths with ICING. In ACM Conference on emerging Networking EXperiments and Technologies (CoNEXT), 2011.

Digital Library

[29]

J. A. Obar and A. Clement. Internet surveillance and boomerang routing: A call for Canadian network sovereignty. Online:\\ http://ssrn.com/abstract=2311792, 2013.

[30]

V. Paxson. End-to-End Routing Behavior in the Internet. In ACM SIGCOMM, 1996.

Digital Library

[31]

J. Postel. Internet Protocol. IETF RFC-791, Sept. 1981.

[32]

J. Preethi and R. Sumathi. An energy efficient on-demand routing by avoiding voids in wireless sensor network. In Internation Conference on Information Systems Design and Intelligent Applications (INDIA), 2012.

[33]

C. Reis, S. D. Gribble, T. Kohno, and N. C. Weaver. Detecting in-flight page changes with web tripwires. In USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2008.

Digital Library

[34]

Reporters Without Borders. Enemies of the internet 2013, report. http://surveillance.rsf.org/en/wp-content/uploads/sites/2/2013/03/enemies-of-the-internet_2013.pdf, Mar. 2013.

[35]

E. Rosen, A. Viswanathan, and R. Callon. Multiprotocol label switching. IETF RFC-3031, Jan. 2001.

Digital Library

[36]

S. Savage, T. Anderson, A. Aggarwal, D. Becker, N. Cardwell, A. Collins, E. Hoffman, J. Snell, A. Vahdat, G. Voelker, and J. Zahorjan. Detour: Informed Internet routing and transport. IEEE Micro, 19(1):50--59, 1999.

Digital Library

[37]

M. Schuchard, J. Geddes, C. Thompson, and N. Hopper. Routing around decoys. In ACM Conference on Computer and Communications Security (CCS), 2012.

Digital Library

[38]

J. Seibert, S. Becker, C. Nita-Rotaru, and R. State. Securing virtual coordinates by enforcing physical laws. In International Conference on Distributed Computing Systems (ICDCS), 2012.

Digital Library

[39]

R. Sherwood, B. Bhattacharjee, and R. Braud. Misbehaving TCP receivers can cause Internet-wide congestion collapse. In ACM Conference on Computer and Communications Security (CCS), 2005.

Digital Library

[40]

R. Sherwood, B. Bhattacharjee, and A. Srinivasan. $\mathcalP$5: A protocol for scalable anonymous communication. Journal of Computer Security, 13(6):839--876, 2005.

Digital Library

[41]

A. Singh, M. Castro, P. Druschel, and A. Rowstron. Defending against eclipse attacks on overlay networks. In Proc. of ACM SIGOPS European Workshop, 2004.

Digital Library

[42]

G. Varghese. Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices. Morgan Kaufmann, 2004.

Digital Library

[43]

G. Wang and T. E. Ng. Distributed algorithms for stable and secure network coordinates. In ACM Internet Measurement Conference (IMC), 2008.

Digital Library

[44]

B. Wong, A. Slivkins, and E. G. Sirer. Meridian: A lightweight network location service without virtual coordinates. In ACM SIGCOMM, 2005.

Digital Library

[45]

Y. Wu, M. Zhao, A. Haeberlen, W. Zhou, and B. T. Loo. Diagnosing Missing Events in Distributed Systems with Negative Provenance. In ACM SIGCOMM, 2014.

Digital Library

[46]

E. Wustrow, S. Wolchok, I. Goldberg, and J. A. Halderman. Telex: Anticensorship in the network infrastructure. In IFIP International Information Security and Privacy Conference (SEC), 2011.

Digital Library

[47]

X. Yang, D. Clark, and A. W. Berger. NIRA: A New Inter-Domain Routing Architecture. IEEE/ACM Transactions on Networking (ToN), 15(4):775--788, 2007.

Digital Library

[48]

X. Yang and D. Wetherall. Source Selectable Path Diversity via Routing Deflections. In ACM SIGCOMM, 2006.

Digital Library

[49]

X. Zhang, H.-C. Hsaio, G. Hasker, H. Chan, A. Perrig, and D. G. Andersen. SCION: Scalability, Control and Isolation On Next-Generation Networks. In IEEE Symposium on Security and Privacy, 2011.

Digital Library

[50]

M. Zhao, W. Zhou, A. J. T. Gurney, A. Haeberlen, M. Sherr, and B. T. Loo. Private and verifiable interdomain routing decisions. In ACM SIGCOMM, 2012.

Digital Library

Cited By

Patterson DTomlinson B(2024)Xylem: An Energy-efficient, Globally Redistributive, Financial Infrastructure Using Proof-by-LocationDistributed Ledger Technologies: Research and Practice10.1145/36536803:3(1-27)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1145/3653680
Chao DXu DGao FZhang CZhang WZhu L(2024)A Systematic Survey on Security in Anonymity Networks: Vulnerabilities, Attacks, Defenses, and FormalizationIEEE Communications Surveys & Tutorials10.1109/COMST.2024.335000626:3(1775-1829)Online publication date: Nov-2025
https://doi.org/10.1109/COMST.2024.3350006
Davidson AFrei MGartner MHaddadi HPerrig ANieto JWinter PWirz F(2022)Tango or square dance?Proceedings of the 21st ACM Workshop on Hot Topics in Networks10.1145/3563766.3564111(205-212)Online publication date: 14-Nov-2022
https://dl.acm.org/doi/10.1145/3563766.3564111
Show More Cited By

Index Terms

Alibi Routing
1. Hardware
  1. Communication hardware, interfaces and storage
2. Networks
  1. Network protocols

Recommendations

Alibi Routing
SIGCOMM'15

There are several mechanisms by which users can gain insight into where their packets have gone, but no mechanisms allow users undeniable proof that their packets did not traverse certain parts of the world while on their way to or from another host. ...
Large Scaling Unstructured Peer-to-Peer Networks with Heterogeneity-Aware Topology and Routing

Peer-to-peer (P2P) file sharing systems such as Gnutella have been widely acknowledged as the fastest-growing Internet applications ever. The P2P model has many potential advantages, including high flexibility and serverless management. However, these ...
On investigating overlay service topologies

Recently, a moderate amount of work has been reported on the use of overlay networks to support value-added network services, such as multicasting, Quality-of-Service (QoS), security, etc. To design an overlay network, the first step is to choose an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGCOMM '15: Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication

August 2015

684 pages

ISBN:9781450335423

DOI:10.1145/2785956

General Chairs:
Steve Uhlig
Queen Mary University of London, UK
,
Olaf Maennel
Tallinn U. of Technology in Estonia, Estonia
,
Program Chairs:
Brad Karp
University College London, UK
,
Jitendra Padhye
Microsoft, USA

ACM SIGCOMM Computer Communication Review Volume 45, Issue 4
SIGCOMM'15
October 2015
659 pages
ISSN:0146-4833
DOI:10.1145/2829988
Editors:
Konstantina Papagiannaki
Telefonica Research, Barcelona, Spain
,
Katerina Argyraki
EPFL, Switzerland
,
Hitesh Ballani
Microsoft Research Cambridge, UK
,
Fabián Bustamante
Northwestern University, USA
,
Joseph Camp
SMU, USA
,
Augustin Chaintreau
Columbia University, USA
,
Phillipa Gill
Stony Brook University, USA
,
Marco Mellia
Politecnico di Torino, Italy
,
Bhaskaran Raman
IIT Bombay, India
,
Joel Sommers
Colgate University, USA
,
Aline Carneiro Viana
INRIA, France
Issue’s Table of Contents

Copyright © 2015 ACM.

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 the author(s) 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

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 August 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF
ONR

Conference

SIGCOMM '15

Sponsor:

SIGCOMM

SIGCOMM '15: ACM SIGCOMM 2015 Conference

August 17 - 21, 2015

London, United Kingdom

Acceptance Rates

SIGCOMM '15 Paper Acceptance Rate 40 of 242 submissions, 17%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
912
Total Downloads

Downloads (Last 12 months)92
Downloads (Last 6 weeks)21

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Patterson DTomlinson B(2024)Xylem: An Energy-efficient, Globally Redistributive, Financial Infrastructure Using Proof-by-LocationDistributed Ledger Technologies: Research and Practice10.1145/36536803:3(1-27)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1145/3653680
Chao DXu DGao FZhang CZhang WZhu L(2024)A Systematic Survey on Security in Anonymity Networks: Vulnerabilities, Attacks, Defenses, and FormalizationIEEE Communications Surveys & Tutorials10.1109/COMST.2024.335000626:3(1775-1829)Online publication date: Nov-2025
https://doi.org/10.1109/COMST.2024.3350006
Davidson AFrei MGartner MHaddadi HPerrig ANieto JWinter PWirz F(2022)Tango or square dance?Proceedings of the 21st ACM Workshop on Hot Topics in Networks10.1145/3563766.3564111(205-212)Online publication date: 14-Nov-2022
https://dl.acm.org/doi/10.1145/3563766.3564111
Zhang GCao JXu MLi Q(2022)Less is More: Mitigating Tor Traffic Correlation with Distance-Aware Path Selection2022 IEEE 24th Int Conf on High Performance Computing & Communications; 8th Int Conf on Data Science & Systems; 20th Int Conf on Smart City; 8th Int Conf on Dependability in Sensor, Cloud & Big Data Systems & Application (HPCC/DSS/SmartCity/DependSys)10.1109/HPCC-DSS-SmartCity-DependSys57074.2022.00099(538-545)Online publication date: Dec-2022
https://doi.org/10.1109/HPCC-DSS-SmartCity-DependSys57074.2022.00099
Bu KLaird AYang YCheng LLuo JLi YRen K(2020)Unveiling the Mystery of Internet Packet ForwardingACM Computing Surveys10.1145/340979653:5(1-34)Online publication date: 28-Sep-2020
https://dl.acm.org/doi/10.1145/3409796
Sengupta BLi YBu KDeng R(2020)Privacy-preserving Network Path ValidationACM Transactions on Internet Technology10.1145/337204620:1(1-27)Online publication date: 7-Feb-2020
https://dl.acm.org/doi/10.1145/3372046
Ryan MChowdhury MJiang FDoss R(2020)Avoiding Geographic Regions in Tor2020 IEEE 19th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)10.1109/TrustCom50675.2020.00109(802-809)Online publication date: Dec-2020
https://doi.org/10.1109/TrustCom50675.2020.00109
Yang FXu KLi QLu RWu BZhang TZhao YShen M(2020)I Know If the Journey Changes: Flexible Source and Path Validation2020 IEEE/ACM 28th International Symposium on Quality of Service (IWQoS)10.1109/IWQoS49365.2020.9213001(1-6)Online publication date: Jun-2020
https://doi.org/10.1109/IWQoS49365.2020.9213001
Bock KHughey GQiang XLevin DCavallaro LKinder JWang XKatz J(2019)GenevaProceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security10.1145/3319535.3363189(2199-2214)Online publication date: 6-Nov-2019
https://dl.acm.org/doi/10.1145/3319535.3363189
Davoli GEsposito FCerroni W(2019)A Network Management Protocol for Sonification of Software-Defined Infrastructures2019 IEEE Conference on Network Function Virtualization and Software Defined Networks (NFV-SDN)10.1109/NFV-SDN47374.2019.9039998(1-7)Online publication date: Nov-2019
https://doi.org/10.1109/NFV-SDN47374.2019.9039998
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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

Media

Figures

Other

Tables

View Table of Contents