Alibi Routing

Session 11: Security, Privacy and Censorship - Paper 1

Authors: Dave Levin (University of Maryland), Youndo Lee (University of Maryland), Luke Valenta (University of Pennsylvania), Zhihao Li (University of Maryland), Victoria Lai (University of Maryland), Cristian Lumezanu (NEC Labs), Neil Spring (University of Maryland), Bobby Bhattacharjee (University of Maryland)
Paper:
http://conferences.sigcomm.org/sigcomm/2015/pdf/papers/p611.pdf
Public Review:
http://conferences.sigcomm.org/sigcomm/2015/pdf/reviews/371pr.pdf

Intro:
Users have no control over routing path and lack the insights into undeniable proof of where their packets travelled. This is problematic because the packets might go thorough censoring country, causing collateral damage. Existing approaches like HTTPS and Anonymity can help hide information, but they are still somehow subject to censorship. The authors propose to avoid these geographic regions in the first place and provide proofs of the avoidance, which is called “provable avoidance routing”.

System:
The problem is considered to be intractable because you are trying to prove something did not happen without enumerating everything that could have? the paper uses a very simple logic: if event A happens reduces to event X doesn’t happen, then conjectured with A actually happens, we have the proof that X doesn’t happen. Here A makes an “alibi”.  To put the routing into this logic, X is traversing a forbidden area and A is traversing a relay node. The key idea is to choose a relay that is far away from a forbidden node that the difference between the two traversing is significant.

Using these two mutually exclusive events, the author then presents “alibi routing”, a peer-to-peer overlay routing system.  The algorithm works in following steps:
1. users choose forbidden regions
    These regions are user-specified and arbitrary sets of polygons(defined over lat/lon)
2. users compute target regions (where alibis might be)
    Exclude locations where alibis cannot exit
    Segment the world into grid
    Include a grid point if the shortest latency(min RTT) to reach a destination via the alibis node alone is largely smaller than via the alibis node+any node in the forbidden area.
3. Alibi Routing recursively searches for peers within the target regions

Evaluation/Result:
The authors evaluate their work by both simulation(20k nodes) and an implementation deployed on PlanetLab which has 425 nodes.
The result turns out that
- Most source-destination pairs can provably avoid.
- Failure typically  arises when target region is too small or non-existent
- Failure is likely when source or destination are very close to the forbidden region
little latency overhead
- and more results in the paper

The conclusion is that provable avoidance is possible safely and efficiently. Alibi routing finds potential alibis successfully and at low cost.

The data and code are publicly available at alibi.cs.umd.edu


Q: Given that distance variability , it must cause equivalently false positives? Is that good?
A: This is what that delta parameter will affect, the idea is that you can specify smaller argument, so in that way hopefully that target region is still less than the minimum requirement to succeed. This is the tradeoff of success versus performance.

Q: The motivation is about censorship, but there are lots of people inside the forbidden area. But there’s very small percentage of traffic from Europe across China. Is that fair?
A: We didn’t evaluate the overhead and we aren’t sure how that could be fair. But even as centric as the US data is, still the majority of the time it still succeeds.

Q: What if attackers increases the delay?
A: Don’t know for sure. But the attackers cannot trick us by decreasing the delay.