Zage Rotaru

On the Accuracy of Virtual Coordinate Systems in Adversarial Networks
-------------------------------------

Virtual coordinate systems: Node maps itself to virtual coordinates based on network distance estimates from "reference nodes".
Allow Internet hosts to determine latency to arbitrary hosts w/out active monitoring all hosts.  Designed assuming everyone altruistic.
Paper presents vulnerability to attacks and mitigation techniques.

Two sorts:
landmark-based (special servers) (centralized--more robust to attacks if we can have a number of pre-trusted landmarks)
decentralized (any node can act as reference node -- good approach: identify set of close and set of far nodes, randomly choose a subset of them as ref. nodes)

Examples of virtual coordinate systems: 
	- Multicast trees
	- "Closest" replica in p2p

Previous work:
Triangle inequality to detect malicious tampering.  Insufficient because real networks often violate triangle inequality...

Types of attacks:

Coordinate inflation - Delaying response to raise RTT or reporting high error.  Both result in node thinking it is further from a set of virtual coords than it is.
Deflation - Prevent node from performing corrections by reporting false coordinates.
Oscillation - Causing nodes to continually change their positions (prevent stabilization)

Note that displacing one node affects all nodes using the victim as a reference node as well.


Mitigation techniques:
- Should not add to communication overhead
- Centers on outlier detection

Spatial (node at coordinates inconsistent with neighbors) and Temporal outlier detection (inconsistencies over time)

Spatial - Forces reported distance to be consistent with others in ref set

Temporal - Forces report to be consistent with previous reports

Issue: Spatial, claim only have limited amount of time to coordinate with other attackers

Must do outlier detection each time it receives new coordinates

Compute centroids for both metrics.

Drop outliers, compute only based on reports within centroid.


Calculate error_attack / error_noattack = error_rel.  > 1, degradation of accuracy, < 1, increase in accuracy


Vivaldi
-------
Half nodes selected are closest based on network latency, half selected at random. 2dim coordinate space.

oscillation attack = cool.


AMP results cause them to conclude that works well when malicious coalition is less than 1/3 total num of reference set.  (Why not scale reference set size with system size?)



Can we use this to minimize Sybil/Eclipse attacks?