Micah Sherr Matt Blaze Boon Thau Loo
University of Pennsylvania
This paper describes Veracity, a practical fully-decentralized service for securing network coordinate systems. In Veracity, all advertised coordinates and subsequent coordinate updates must be independently verified by a small set of nodes via a voting scheme. Unlike existing approaches, Veracity does not require any a priori secrets or trusted parties, and does not depend on outlier analysis of coordinates based on a fixed set of neighbors. We have implemented Veracity by modifying an open-source network coordinate system, and have demonstrated within a simulated network environment and deployment on PlanetLab that Veracity mitigates attacks for moderate sizes of malicious nodes (up to 30% of the network), even when coalitions of attackers coordinate their attacks. We further show that Veracity resists high levels of churn and incurs only a modest communication overhead.
Decentralized network coordinate systems such as Vivaldi , PIC , ICS , Big-bang simulation , and NPS  have been proposed as a means of efficiently estimating network distances without having to explicitly contact the end-hosts involved. Distributed algorithms map nodes to -dimensional coordinates such that the distance between two nodes' coordinates corresponds to a network distance (e.g., latency) between the pair. For a network with nodes, coordinate systems linearize the information necessary to compute pairwise network distances, allowing nodes to estimate distances using embedded coordinates.
Coordinate systems support a wide range of network services, including proximity-based routing , neighbor selection in overlays , network-aware overlays , and replica placement in content-distribution networks [8,37]. Several large-scale coordinate systems are currently deployed on the Internet. For example, the Vuze client (formally called Azureus) for BitTorrent uses coordinate systems for efficient distributed hash table (DHT) traversal  and locality-based neighbor selection , and currently operates on more than one million nodes .
Unfortunately, the distributed nature of coordinate systems make them particularly vulnerable to insider manipulation. To illustrate, recent studies  on Vivaldi have shown that when 30% of nodes lie about their coordinates, Vivaldi's accuracy decreases by a factor of five. When attackers collude, even 5% malicious nodes have a sizable impact on the system's accuracy.
In addition to causing significantly decreased accuracy and performance, corrupted coordinate systems may serve as stepping stones for attacks against the applications that rely on them. Attackers who control the coordinate system may advertise attractive (but false) coordinates for nodes under their control, increasing the likelihood that such hosts will be selected for routes, neighbors, or replicas. Such compromises enable myriad attacks against the overlying services. For example, malicious nodes may misdirect intercepted messages sent via overlay routing, return false data when serving as a replica in a content distribution network, or partition the keyspace in a distributed hash table.
This paper presents Veracity , a fully decentralized service for securing network coordinate systems. Veracity provides a practical deployment path while providing equivalent (or greater) security than previously proposed coordinate security systems. Unlike prior proposals, Veracity does not require either pre-selected trusted nodes , the triangle inequality test , or outlier detection based on a fixed neighbor set , allowing Veracity to be practically deployed and react more rapidly to changes in network conditions. Veracity is also agnostic to the type of decentralized coordinate system being deployed, and can be employed as a protection service over existing decentralized coordinate systems [7,6,19,22].
At a high-level, Veracity utilizes a two-step verification process. The first step involves a majority vote-based scheme in which a published coordinate has to be independently verified by a deterministically assigned set of verification nodes before it is used by peers. An adversary who attempts to disrupt the network by publishing inconsistent coordinates will fail this verification step, and consequently its coordinates will be ignored. As an additional measure, a second verification step utilizes a set of randomly chosen peers to independently compute the estimation error due to a new coordinate, and reject the coordinate if the error is above a threshold. This second protection mechanism detects attacks in which malicious nodes delay responses to measurement probes. The combination of the two techniques ensures that Veracity can tolerate a high fraction of malicious nodes that concurrently report false coordinates and delay latency measurements.
In this paper, we focus our implementation and evaluation on Vivaldi since it is widely used  and has been the focus of recent work [15,40] on securing coordinate systems. We demonstrate via execution in a simulated network environment using realistic network traces [38,17] and a deployment on PlanetLab that Veracity mitigates attacks for moderate sizes of malicious nodes (up to 30% of the network), even when coalitions of attackers coordinate their attacks. We further show that Veracity is resistant to high levels of churn and incurs only a modest communication overhead.
Vivaldi uses a fully distributed spring relaxation algorithm, requiring no fixed network infrastructure and no distinguished nodes. The system envisions a spring between each pair of nodes, with the resting position of the spring equaling the network latency between the pair. At any point in time, the distance between the nodes in the coordinate space determines the current length of the spring connecting the nodes.
Nodes adjust their coordinates after collecting published coordinate and latency measurements from a randomly chosen neighbor. Consider a node that wishes to update its coordinate . It picks a randomly chosen neighbor , retrieves its coordinate and performs a round-trip measurement from itself to . The squared error function, (where is the distance between their coordinates) denotes the estimation error between the coordinates of and . Using Vivaldi's spring relaxation algorithm, reflects the potential energy of the spring connecting the two nodes. Vivaldi attempts to minimize the potential energies over all springs. In each timestep of the algorithm, nodes allow themselves to be pulled or pushed by a connected spring. The system converges when the squared error function (i.e., the potential energies) is minimized below a threshold.
Prior studies [16,15] have demonstrated that coordinate systems are susceptible to three classes of attacks: disorder attacks in which malicious insiders attempt to decrease the accuracy of the system by advertising false coordinates and delaying RTT responses, and isolation and repulsion attacks in which the attacker respectively attempts to isolate or repulse a subset of targeted nodes. Veracity's general approach defends against malicious nodes that falsify their coordinates or induce/report artificially inflated latencies. Hence, the techniques described in this paper can mitigate all three attacks.
We adopt the constrained-collusion Byzantine model proposed by Castro et al.  in which malicious nodes can insert, delete, or delay messages. Given a network of size , and some fraction () of malicious attackers, there exist independent coalitions of size , where .
To assess the accuracy of a virtual coordinate, we measure the median error ratio of a node , defined as the median over the error ratios
To gauge the accuracy of the system as a whole, we define the system error ratio as the median over all peers' median error ratios. The system error ratio enables us to quantitatively compare the performance and security of Veracity and Vivaldi. To show lower performance bounds, we also consider the 90th percentile error ratio - i.e., the 90th percentile of nodes' median error ratios.
We first provide an overview of Veracity's security mechanisms. We base our description on Vivaldi's coordinate update model. While other decentralized coordinate systems [6,19,22] differ in their implementations, the update models are conceptually similar to Vivaldi's, and hence, Veracity's techniques are applicable to these systems as well.
To update its coordinate, a participating node (the investigator) periodically obtains the coordinate of a selected peer (the publisher) and measures the RTT between the two nodes. In most implementations, the publisher is typically a pre-assigned neighbor node of the investigator. In Veracity, we relax the requirement that a publisher has to be a fixed neighbor of the investigator and instead use a distributed directory service (Section 4.2) to enable investigators to scalably select random publishers on demand.
The basic update model of Vivaldi leads to two possible avenues of attacks: first, if the publisher is dishonest, it may report inaccurate coordinates. Second, the publisher may delay the RTT probe response to increase the error of the investigator's updated coordinate. To defend against such attacks, Veracity protects the underlying coordinate system through a two-step verification process in which groups of nodes independently verify the correctness of another node's coordinates. We outline these two processes below, with additional details presented in Section 4.
An important benefit of Veracity is that it makes no distinction between intentionally falsified coordinates and those that are inaccurate due to limitations of the coordinate embedding process. In either case, Veracity prevents the use of inaccurate coordinates.
This section presents details of Veracity's two-step verification protocol. We first focus on various mechanisms necessary to realize publisher coordinate verification that prevents investigators from considering inaccurate coordinates. We then motivate and describe the candidate coordinate verification that protects against malicious RTT probe delays by the publisher.
VSet construction utilizes a hash function to increase the difficulty of stacking VSets with collaborating malicious nodes. Attackers who control large coalitions of peers may be able to populate a majority of a particular malicious node's VSet (for example, by strategically choosing IP addresses within its assigned range), but such VSet stacking requires at a minimum peers per VSet. In practice, many more malicious peers are required since the attacker does not have complete discretion over the IP addresses of its coalition members. Moreover, as nodes join and leave the network, VSet members change (since the nodes whose GUIDs are closest to also change), significantly impairing the ability to persistently stack VSets.
Veracity utilizes a distributed directory service to resolve VSet members and route messages based on node GUIDs. The directory service implements a single API function, deliver(), which delivers the message to the peer whose GUID is closest to according to a keyspace distance metric. Veracity is compatible with any distributed directory service that supports the deliver function. We explore the implementation of distributed directory services in Section 5.
As shown in Figure 1(a), when a publisher updates its coordinate, it transmits an update tuple to members of its VSet using the deliver function provided by the directory service. The update tuple contains the following values: is the publisher's GUID, is a logical timestamp incremented whenever the publisher updates his coordinate, is the new coordinate, and is the publisher's network address. Upon receiving the update tuple, each VSet member measures the RTT between itself and (Figure 1(b)), and computes the error ratio
To update its coordinate, the investigator queries a random node (via a deliver message to a random GUID ) in the network (i.e., the publisher). As depicted in Figure 1(c), the publisher replies with a claim tuple . The investigator immediately discards the publisher's coordinates if the publisher's IP address is not , , or it deems (VSet size) insufficiently large to offer enough supporting evidence for the coordinate.
Otherwise, the investigator transmits the evidence query to each member of the publisher's VSet, constructed on demand given according to Eq. 2 (Figure 1(d)). If a VSet member stores an evidence tuple containing both and (logical timestamp), it returns that tuple to the investigator (Figure 1(e)). The investigator then checks that the GUID, network address, and coordinates in the publisher's claim tuple matches those in the evidence tuple. If there is a discrepancy, the evidence tuple is ignored.
After querying all members of the publisher's VSet, the investigator counts the number of non-discarded evidence tuples for which , where is the investigator's chosen ratio cutoff parameter. Intuitively, this parameter gauges the investigator's tolerance of coordinate errors: a large permits fast convergence times when all nodes are honest, but risks increased likelihood of accepting false coordinates. If the count of passing evidence tuples meets or exceeds the investigator's evidence cutoff parameter, , the coordinate is considered verified. Otherwise, the publisher's coordinate is discarded.
To determine an appropriate value for the ratio cutoff parameter , we examined Vivaldi's system error ratio when run against the Meridian , King , and Scalable Sensing Service (S)  datasets, as well as a pairwise latency experiment that we executed on PlanetLab  (PL). Simulations and the PlanetLab experiment used Bamboo , a DHT with a Vivaldi implementation and a simulation mode that takes as input a matrix of pairwise latencies. Due to scalability limitations, the simulator used the first 500 nodes from the Meridian and King datasets. Simulation results were averaged over 10 runs. Table 1 provides the properties of the four datasets as well as Vivaldi's achieved system error ratio.
An appropriate value for should be sufficiently large to accommodate baseline errors. For example, in our Veracity implementation (see Section 6.1), we use a ratio cutoff parameter of , well above the system error ratio for all datasets.
In the absence of network churn, the VSet membership of a publisher remains unchanged. With network churn, some of the VSet members may be modified as the keyspace of the directory service is reassigned. New VSet members may not have stored any evidence tuples, but as long as (evidence cutoff parameter) VSet members successfully verify the coordinate, the coordinate can be used. In our experiments, we note that even when is for a VSet size of , Veracity can tolerate moderate to high degrees of churn while ensuring convergence in the coordinate system.
The publisher coordinate verification scheme described in Section 4.3 provides the investigator with evidence that a publisher's coordinate is accurate. This does not prevent a malicious publisher from deliberately delaying an investigator's RTT probe, thereby causing the investigator to update its own coordinate erroneously. (Recall that to update its coordinate, the investigator must measure the RTT between itself and the publisher after having obtained the publisher's coordinate.)
Once an investigator has validated the publisher's coordinate, the candidate coordinate verification scheme compares coordinate estimation errors among the investigator and a random subset of nodes (the RSet ) using the investigator's current coordinate () and a new candidate coordinate () calculated using the publisher's verified coordinate and the measured RTT.
The investigator queries for the coordinates of RSet members by addressing deliver messages to random GUIDs (Figures 2(a) and 2(b)). As with (VSet size), a larger (RSet size) increases confidence in the candidate coordinate at the expense of additional communication. In our experimentation, we found that setting provides reasonable security without incurring significant bandwidth overhead. The investigator () measures the RTT between itself and each RSet member (Figure 2(c)) and computes the average error ratio
Veracity utilizes DHTs to implement its distributed directory service, which supports the deliver messaging functionality described in Section 4.1. While one can adopt a centralized or semi-centralized directory service, a fully-decentralized solution ensures scalability, allowing Veracity's security mechanisms to be deployable at Internet scale. DHTs are ideal because they scale gracefully with network size, requiring messages to resolve a GUID [34,26,25].
While DHTs ensure scalability, they are vulnerable to insider manipulation  due to their distributed nature. Malicious nodes can conduct Sybil attacks to increase their influence by registering multiple identities in the network , eclipse attacks in which they falsify routing update messages to corrupt honest nodes' routing tables , and routing attacks in which they inject spurious responses to messages that cross their paths . Fortunately, well-studied techniques exist that defend DHTs against such attacks [11,10,4,14,5,1]. We describe defenses that are compatible with Veracity's design below.
Sybil attack countermeasures that are compatible with a decentralized architecture include distributed registration in which registration nodes, computed using iterative hashing of a new node's IP address, vote on whether the new node can join the system based on the number of similar requests it has received from the same IP address . Alternatively, Danezis et al. propose using bootstrap graphs that capture the relationships between joining nodes and the nodes through which they join to construct trust profiles . Finally, Borisov suggests the use of cryptographic puzzles (e.g., finding a string in which the last bits of a cryptographic hash are zero) to increase the cost of joining the network .
There are also several security techniques that mitigate eclipse and routing attacks. The S-Chord system proposed by Fiat et al. organizes the network into swarms based on GUIDs . Lookups are relayed between swarms and are forwarded only if the lookup was sent from a majority of the members of the previous swarm. S-Chord is resilient to attacks in which the adversary controls nodes, where , is the minimum number of nodes in the network at any time, is a tunable parameter, and the number of honest nodes is less than or equal to . Castro et al. propose the use of redundant routing in which queries are sent via diverse paths , reaching the intended recipient if all nodes on at least one path are honest. Sanchez et al. improve the redundant routing technique in their Cyclone system , showing that 85% of requests were correctly delivered when attackers controlled 30% of a 1024 node network and nodes sent messages using 8 redundant paths.
The impact of utilizing the above secure routing techniques is minimal. All of the above approaches operate below the Veracity protocol and do not affect Veracity's operation. Approaches that rely on redundant messaging incur a linear increase in bandwidth overhead, since all deliver messages must be reliably communicated. As we show in Section 6.5.1, Veracity's communication costs (measured using uncompressed messages) are within the tolerances of even dial-up Internet users. A small linear increase in bandwidth can likely be compensated for by using less expensive message formats (our implementation currently uses Java serialization libraries) and data compression.
We argue that the above DHT security techniques are sufficient to provide the reliability required of Veracity's deliver messaging functionality. Furthermore, unforeseen attacks that manage to circumvent such mechanisms have the effect of artificially increasing the fraction of malicious nodes in the network (since a greater fraction of messages will be misdirected towards misbehaving nodes), and such attacks can be compensated for by increasing (the number of VSet members that must support a publisher's claimed coordinate for it to be accepted) and (the RSet size).
Finally, to our best knowledge, Veracity is one of the first attempts at directly addressing the problem of secure distributed directory services and secure neighbor selection in the context of coordinate systems. Existing proposals for securing network coordinate systems either rely on a priori trusted nodes [15,28] or utilize decentralized architectures while ignoring the mechanisms used to locate peers [6,40], implicitly assuming in the latter case that the underlying coordinate system provides some distributed techniques to securely populate neighbor sets. Unfortunately, such an assumption does not hold as none of the existing systems (Vivaldi , PIC , ICS , the Big-bang simulation , nor NPS ) describe mechanisms for ensuring that neighbor selection cannot be influenced by misbehaving nodes. Veracity utilizes the distributed directory service for both neighbor location and VSet resolution, but other coordinate systems that rely on a directory service solely to determine neighbor sets risk significant vulnerability if the neighbor sets are easily populated by malicious nodes.
In this section, we evaluate Veracity's ability to mitigate various forms of attacks in the presence of network churn. We have implemented Veracity by modifying the Vivaldi implementation that is packaged with Bamboo , an open-source DHT that is resilient to high levels of node churn  and functions either in simulation mode or over an actual network.
Veracity uses Vivaldi as the underlying coordinate system with a 5-dimensional coordinate plane (the recommended configuration in the Bamboo source code ). Each node attempted to update its coordinate every 10 seconds. The size of VSets and RSets were both fixed at 7 ( ). We used a ratio cutoff parameter of and an evidence cutoff parameter of 4. That is, at least 4 of the 7 VSet members had to report error ratios less than for a coordinate to be verified. The maximum tolerable increase in error () for the candidate coordinate verification was set to .
Our experiments are carried out using Bamboo's simulation mode as well as on PlanetLab. In the simulation mode, we instantiated 500 nodes with pairwise latencies from the Meridian and King datasets. Due to space constraints, simulation results are shown only for the Meridian dataset. Similar conclusions were drawn from the King dataset and are available in the technical report version of this paper . To distribute the burden of bootstrapping peers, a node joins the simulated network every second until all 500 nodes are present. Nodes join via an already joined peer selected uniformly at random.
In our PlanetLab experiments, the 100 participating nodes joined within 3 minutes of the first node. The selected PlanetLab nodes were chosen in a manner to maximize geographic diversity. The simulation and PlanetLab experiments share a common code base, with the exception of the simulator's virtualized network layer.
In Sections 6.2 through 6.4, we present our results in simulation mode in the absence and presence of attackers, followed by an evaluation on PlanetLab in Section 6.5. We focus our evaluation on comparing Vivaldi (with no protection scheme) and Veracity based on the accuracy of the coordinate system, convergence time, ability to handle churn, and communication overhead.
Before evaluating the effectiveness of Veracity at mitigating various attacks, we first provide a performance comparison between Veracity and Vivaldi in the absence of any attackers within the simulation environment.
The polling frequency - the rate at which nodes attempt to update their coordinate - is directly proportional to the system's convergence time. Higher polling frequencies enable faster convergence time at the expense of bandwidth. Although the values of the x-axis can be increased or decreased by adjusting the polling frequency, the shape of the curves remain fixed. Repeating our experiments with smaller and larger polling frequencies produced similar results.
Figure 5 shows the system error ratio for Vivaldi and Veracity for various inter-event periods. Note that the level of churn is inversely proportional to the inter-event period. To illustrate near-worstcase performance, the figure also plots the 90th percentile error ratio.
Both Vivaldi and Veracity are able to tolerate high levels of churn. The ``breaking'' point of both systems occur when the inter-event period is less than five seconds, reflecting a rate at which approximately a quarter of the network is replaced every 10 minutes. Churn affects Veracity since the joining and leaving of nodes may cause the members of a VSet to more rapidly change, reducing the investigator's ability to verify a coordinate. Even at this high churn rate, Veracity's system error ratio () is only slightly worse than its error ratio () when there is no churn. It is worth emphasizing that such high churn (i.e., 25% of the network is replaced every 10 minutes) is unlikely for real-world deployments. The near 0-slope in Figure 5 for inter-event periods greater than 10 seconds shows that neither Vivaldi nor Veracity are significantly affected by more realistic churn rates.
To emulate realistic network conditions, all simulations experience moderate churn at a median rate of one churn event (a node leaving, immediately followed by a new node joining) every 120 seconds. This churn rate replaces 10% of the nodes during the lifetime of our experiments (100 minutes).
Malicious attackers significantly reduce Vivaldi's accuracy, resulting in a 387% increase in the system error ratio (relative to Vivaldi when no attack takes place) even when just 10% of nodes are malicious. When 30% of nodes are malicious, the system error ratio increases dramatically by 1013%. In contrast, Veracity easily mitigates such attacks since the coordinate discrepancies are discernible in evidence tuples, causing inconsistently advertised coordinates to be immediately discarded by investigators. At low rates of attack (10%), the system error ratio increases by only 6% (representing a negligible system-wide median latency error of ). When 30% of the network is malicious, Veracity limits the increase in system error ratio to 32% (), an 88% improvement over Vivaldi under the same attack.
Malicious nodes may conduct a more intelligent attack by randomly delaying probes while reporting consistent but erroneous coordinates. That is, each malicious node randomly generates a coordinate and reports the identical (and false) coordinate whenever probed. Such a strategy eliminates coordinate inconsistencies among VSet members. Compared to the previously described attack, this strategy results in lower estimation errors for Vivaldi but does slightly better against Veracity. Here, the increase in Vivaldi's system error ratio is 163% for 10% malicious nodes and 368% for 30% malicious. Veracity successfully defends against heavy network infiltrations, yielding an increase in the system error ratio of just 39% when 30% of the network is malicious. Veracity reaches its tipping point when 40% of nodes are malicious, incurring an increase of 118%. We note that this increase is still far below the 497% increase experienced by Vivaldi.
Figure 7 shows Veracity's performance (measured by the cumulative distribution of median error ratios) when the malicious nodes cooperate. For comparison, the Figure also plots the CDFs for equally sized uncoordinated attacks against Veracity and Vivaldi. Since Vivaldi does not collaborate with peers to asses the truthfulness of advertised coordinates, there is no equivalent ``coordinated'' attack against Vivaldi.
For all tested attack strengths, the coordinated attacks did not induce significantly more error than uncoordinated attacks. The resultant system error ratios differed little: when attackers control 30% of the network, the system error ratios are 0.202 and 0.201 for the uncoordinated and coordinated attacks, respectively (for comparison, Vivaldi's system error ratio is 0.679).
The previous sections show that Veracity's two protections schemes - publisher coordinate verification and candidate coordinate verification - effectively mitigate attacks when the adversary controls a large fraction of the network. In this section, we investigate whether it is sufficient to apply only one of the two techniques to achieve similar security.
Figure 8 shows the cumulative distribution of median error ratios when nodes utilize only publisher coordinate verification (``VSet-only'') or candidate coordinate verification (``RSet-only''). We model the attack scenario from Section 6.3.2 in which 20% of the nodes are malicious and cooperating. For comparison, we also show the CDF when both strategies are utilized (``Veracity''). The VSet-only technique achieves nearly the same system error ratio as Veracity (0.19 and 0.17, respectively). However, using only publisher coordinate verification results in a very long tail of median error ratios. In particular, the 90th percentile error ratio is 0.29 for Veracity and 4.42 for VSet-only. Hence, publisher coordinate verification protects the accuracy of most nodes, but permits a significant degradation in accuracy for a minority of peers.
By itself, candidate coordinate verification results in a higher system error ratio (0.42) than VSet-only or Veracity. Additionally, RSet-only has a longer tail than Veracity, resulting in a 90th percentile error ratio of 1.05 during the attack.
By combining both techniques, Veracity better protects the underlying coordinate system, achieving error ratios that nearly mirror those produced by Vivaldi in the absence of attack (see Figures 6 and 7).
Overall we observe that Veracity is effective at mitigating the effects of disorder attacks. Even under heavy attack (40% malicious nodes), disorder attacks result in a relative system error of 1.54, far below Vivaldi's relative median error of 13.9.
Veracity's effectiveness matches or exceeds that of the prior proposals discussed in Section 7. In contrast to existing coordinate protection systems, Veracity does not require pre-selected trusted nodes, triangle inequality testing, nor outlier detection based on a fixed neighbor set, and is therefore better suited for practical deployment.
While Veracity is intended primarily to defend against disorder attacks, our next experiment demonstrates the effectiveness of Veracity for protecting against repulsion and isolation attacks. We carry out a combined repulsion and isolation attack as follows: malicious nodes are partitioned into three coalitions, each of which attempts to repulse and isolate a single victim node. Attackers attempt to repulse the targeted node towards an extremely negative coordinate (i.e., having in all five dimensions) by using the following heuristic: if the victim is closer than the attacker to the negative coordinate, the attacker behaves honestly. Otherwise, the attacker reports his accurate coordinate but delays the victim investigator's RTT probe response by 1000ms, causing the victim to migrate his coordinate (provided it passes candidate coordinate verification) towards the negative coordinate.
Figure 9 shows the median of the three victim nodes' median error ratios achieved during the combined repulsion and isolation attack. In contrast to previous experiments, we do not use the system error ratio (the median over all peers' median error ratios), as repulsion and isolation attacks target specific victims and need not cause a significant degradation in coordinate accuracy for the remaining peers.
Veracity consistently offers lower median error ratios than Vivaldi. While Veracity does not completely mitigate the effects of repulsion and isolation attacks, our results suggest that the vote-based verification scheme is amenable to defending against such attacks.
In our last experiment, we validate our simulation results by deploying Veracity on the PlanetLab testbed.
Veracity incurs a communication overhead since publishers' coordinates must be verified by VSets and investigators' candidate coordinates must be assessed by RSets. Since Veracity uses a DHT as its directory service, it leverages the scalability of DHTs: each verification step requires , where and denotes the VSet and RSet sizes respectively.
Based on the PlanetLab measurements, we performed logarithmic regression analysis to extrapolate the per-node bandwidth requirements of Veracity as the number of nodes increases: KBps () for Vivaldi and KBps () for Veracity. Figure 11 shows the extrapolated bandwidth utilization of Vivaldi and Veracity for large networks. For a large network consisting of 100,000 nodes, Veracity's expected per-node bandwidth requirement is a modest 35KBps, making it accessible to typical broadband users.
PIC detects dishonest nodes by observing that falsified coordinates or delayed measurements likely induce triangle inequality violations (TIVs) . To verify peers' coordinates and measurements, honest nodes use distances to trusted landmarks to detect TIVs. Using a generated transit-stub topology of 2000 nodes, PIC is able to tolerate attacks when up to 20% of the network was controlled by colluding adversaries . However, more recent work has indicated that TIVs can potentially be common and persistent , reducing the practicality of PIC's protection scheme on real-world networks.
Kaafar et al. propose the use of trusted surveyor nodes to detect malicious behavior . Surveyor nodes position themselves in the coordinate space using only other trusted surveyors. Nodes profile surveyors to model honest behavior, detecting falsified coordinates and measurements as behavior that differs from their constructed model. Kaafar et al. conclude that their approach is effective when 30% or less of the network is controlled by malicious and cooperating nodes . Their technique requires 8% of the nodes to be a priori trusted surveyors  - a nontrivial fraction when the network consists of 100,000 or more nodes.
The RVivaldi system proposed by Saucez et al. protect coordinate systems using surveyors as well as centralized Reputation Computation Agents (RCAs), the latter of which assigns reputations (trust profiles) to coordinates [28,27]. Their technique is evaluated only against non-cooperating adversaries, and tolerates up to 20% malicious nodes .
Like Veracity, the system proposed by Zage and Nita-Rotaru is fully distributed and designed for potentially wide-scale deployments . Their approach relies on outlier detection, reducing the influence of nodes whose coordinates are too distant (spatial locality) or whose values change too rapidly in short periods of time (temporal locality). Their technique successfully mitigates attacks when 30% or fewer of the nodes are under an attacker's control . However, the temporal locality heuristic requires that each node maintains an immutable neighborset, a list of neighbors that a node uses to update its coordinates. Wide-scale deployments involving hundreds of thousands of nodes are likely to be dynamic with nodes frequently joining and leaving the system. The high rate of churn will lessen the opportunities for temporal analysis as nodes leave the system (since less history is available), and cause errors in such analysis for newly joined nodes for which frequent changes in coordinates are expected. In contrast, Veracity does not discriminate against spatial or temporal outliers, and as described in Section 6.2.3, tolerates high levels of churn.
This paper extends our original position paper  that outlines our initial design of Veracity. This paper additionally proposes a second verification step geared towards ensuring the correctness of coordinate updates in the presence of malicious delays in latency measurements. This paper further presents a full-fledged implementation that is experimented within a network simulation environment and on PlanetLab.
This paper proposes Veracity , a fully distributed service for securing network coordinates. We have demonstrated through extensive network simulations on real pairwise latency datasets as well as PlanetLab experiments that Veracity effectively mitigates various forms of attack. For instance, Veracity reduces Vivaldi's system error ratio by 88% when 30% of the network misbehaves by advertising inconsistent coordinates and adding artificial delay to RTT measurements. Veracity performs well even against cooperating attackers, reducing Vivaldi's system error ratio by 70% when 30% of the network is corrupt and coordinates its attacks.
We argue that Veracity provides a more practical path to deployment while providing equivalent (or greater) security than previously proposed coordinate security systems. Unlike PIC, Veracity does not associate triangle-inequality violations (TIVs) with malicious behavior , and as indicated by our simulation and PlanetLab results, does not impose additional inaccuracies in the coordinate system when TIVs do exist. Veracity is fully decentralized, requiring no a priori shared secrets or trusted nodes. In comparison to techniques that require specialized trusted nodes [28,27,15], Veracity is well-suited for applications for which centralized trust models are incompatible (e.g., anonymity networks ), and in general, removes central points of trust that may serve as focal points of attack. Veracity's use of distributed directory services enables graceful scalability, and hence the system can easily be applied to wide-scale virtual coordinate system deployments.
Our most immediate future work entails the use of secure network coordinate systems to permit applications to intelligently form routes that meet specific latency and bandwidth requirements. We are also investigating anonymity services  that may leverage Veracity to produce high-performance anonymous paths. Finally, we expect to release an open-source implementation of Veracity in the near future.
The authors are grateful to our shepherd, Kenneth Yocum, for his insightful comments and advice. We also thank the anonymous reviewers for their many helpful suggestions. This work is partially supported by NSF Grants CNS-0831376, CNS-0524047, CNS-0627579, and NeTS-0721845.
This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)
Copyright © 1993, 1994, 1995, 1996,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -split 0 -show_section_numbers -local_icons -no_navigation veracity.tex
The translation was initiated by Micah Sherr on 2009-04-22