Transcript The Frog-Boiling Attack: Limitations of Secure Network Coordinate

The Frog-Boiling Attack: Limitations of Secure
Network Coordinate Systems
Adil Ahmad
Outlines
•
•
•
•
•
•
•
•
•
•
What is a Network Coordinate System
Possible uses of a network coordinate system
What is a frog-boiling attack
The challenge
Network Coordinate systems
Performance Metrics
Counter-measures
Targeted attack and attack variants
Potential Solutions
Conclusion
What is a Network Coordinate System?
• A network coordinate system is used in the
assigning of virtual nodes in given network
(Chan-Tin, et al (2011)
• The coordinates are noted to allow for the
efficient estimation of the latency that exist
between any two pair of nodes within a given
network
Possible uses of a network coordinate
system
• There are several possible uses of network coordinate
systems. Some of which include:
• Choosing of peers to download from in a given file sharing
network as noted by Ng and Zhang (2001)
• Choosing of peers for DHT routing (Dabek et al. ,2004).
• Finding the closest node in a given content-distribution
network as noted by Vuze (2010).
• State reduction in routers (Gummadi et al., 2004).
• Detection of Sybil attackers (Douceur,2002).
• Performing of leader election as noted by (Cowling et al.,
2009) and
• Matchmaking in online gaming (Agarwal and Lorch ,2009)
What is a frog-boiling attack?
• The "frog-boiling" attack is named after a theory that a frog placed in cold
water will not jump out of the water as the temperature is slowly raised.
Eventually, the frog will be boiled to death without noticing the
temperature change, because it is so gradual. In theory, the same general
rule can be applied to the network coordinate system. If a change is
gradual enough so as to go undetected by the failsafes in place to catch
attacks and malfunctions, the entire system can be attacked, taken over, or
badly damaged because the change was so slow so as not to be noticed
until it is too late. Chan-Tin, et al (2011) noticed that this could be done on
all network coordinate systems with three different types of attacks. Even
with other filters in place to prevent the danger, nothing could be done to
stop the slow, gradual attacks
The challenge
• The main challenge in the process of
designing a secure network coordinate system
is the design of a system that is based on the
act of rejecting all the “bad” inputs that do
not show signs of conformity.
•
Network Coordinate systems
• There are several network coordinate systems in the
market. They include the following;
• Vivaldi.: This is a decentralized network coordinate system
that is used in the provision of fact convergence as well as
resilience to a dynamic (ever changing) network
conditions like a P2P Network or a churn (Dabek et al.
,2004).
• Pyxida.: This system implements a coordinate system in a
virtual space. It is employed commercially as well as in
academia in the tracking of the coordinated of PlanetLab
nodes(Pyxida ,2009, Bavier et al. 2004) as well as in
BitTorrent and Vuze. It is however designed to operate on a
P2P network via the implementation of the Vivaldi
algorithm.
Performance Metrics
• The performance metrics used in the evaluation of the boiling frog attack
includes the following;
• Error- The median relative error is evaluated as follows;
• Where RTTactual is the actual RTT value between two nodes and the
RTTestimated is the RTT that is obtained by taking the difference in the
coordinates of the two nodes.
• RRL. -Relative Rank Loss:
• False positive rate
• Intercluster/intracluster ratio
Counter-measures
• There are several countermeasure schemes that can be deployed without
much success against frog-boiling attacks. They include the following;
• Mahalanobis Distance- uses a statistical method to determine the
acceptability of a coordinate
• Kalman Filter.- also uses uses a statistical method to determine the
acceptability of a coordinate
• Veracity- uses a distributed reputation system to determine the
acceptability of a coordinate
• Rvivaldi-This is a reputation system that assigns weighted trust to peers
and utilizes the trust metric to accept coordinate updates from these
peers
Targeted attack and attack variants
•
•
•
•
•
•
How the targeted attack works ;
The attacker makes an attempt to move some victim nodes to certain arbitrary network coordinates.
These nodes are flagged by the three secure mechanisms as anomalous ,outliers or misbehaving and thus
avoid accepting their updates.
Moving a victim node to an arbitrary location with a single update would typically
require a force of sufficient magnitude to trigger an outlier filter.
In order to avoid this, the victim node will be moved to a target location in small steps. The rest of the
network will still accept updates from that victim node if the move is small.
Thus, the rest of the network will also be pulled to that location by the victim node. However, since the
victim nodes consist of a small portion of the network (less than 5%), the rest of the network will get
pulled back together, further from the victim nodes at every update. See diagram below.
Potential Solutions
• outfit the coordinate system with something that will detect
anomalies
• instead of let the system is only looking for changes in coordinates
that fall outside the accepted margin for error, nodes in the
networks should have to trust at least some of their peers at some
time, by accepting updates on coordinates. The updates have to be
similar to other updates, but they do not have to be exact. They
must only fall within certain parameters
• The absence of any requirements made ​it very easy to make small
changes over time such as the frog-boiling attack, to discover, to
take a serious problem. By that time, had infiltrated all that has
been specifically designed to attack the network is already done
and caused damage that are not easy to repair. So the system must
be in the process of update and development to address attacks
such as the frog-boiling attack, and is considered in order to identify
security measures that will not be vulnerable to these types of
problems.
Conclusion
• A stable and decentralized network coordinate
system could potentially provide a number of
beneficial service for various Internet
applications. Early systems however, provide
no protection against malicious participants.
This is because even a single adversary can
cause the entire coordinate system to fail. It is
noted that one apparent solution to such a
dilemma is to include an anomaly detection
mechanism to the coordinate system.
Contd.
• The protection against more complicated adversaries is
marked with difficulty.
• Network conditions on the Internet are very dynamic and
the network coordinates and errors change over time. Due
to this, it becomes a challenge for a node to know whether
a reported coordinate as well as RTT is valid or faked.
Therefore, a secure network coordinate system will have to
provide certain mechanisms for verifying a node’s reported
coordinates as well as RTTs. The success of the frog-boiling
attack therefore effectively demonstrates that the outlier
or anomaly detection system not a secure mechanism to
provide this kind of service
References
•
•
•
•
•
•
•
•
•
•
•
•
•
AGARWAL, S. AND LORCH, J. R. 2009. Matchmaking for online games and other latency-sensitive P2P systems. In
Proceedings of the ACM SIGCOMM Conference on Data Communication (SIGCOMM’09). ACM, New York, NY, 315–
326.
BAVIER, A., BOWMAN, M., CHUN, B., CULLER, D., KARLIN, S., MUIR, S., PETERSON, L., ROSCOE, T.,
SPALINK, T., AND WAWRZONIAK, M. (2004.) Operating system support for planetary-scale network
services. In Proceedings of the 1st Symposium on Networked Systems Design and Implementation
(NSDI’04). USENIX Association, Berkeley, CA, 19–19.
Chan-Tin, E. Heorhiadi, V., Hopper, N. and Kim, Y. (2011)"The frog-boiling attack: Limitations of secure network
coordinate systems." ACM Trans. Inf. Syst. Secur. Vol 14, no. 3, Art. 27, Nov. 2011.
COWLING, J., PORTS, D., LISKOV, B., POPA, R. A., AND GAIKWAD, A. 2009. Census: Location-aware
membership management for large-scale distributed systems. In Proceedings of the USENIX Annual Technical
Conference
DABEK, F., LI, J., SIT, E., ROBERTSON, J.,KAASHOEK, M. F., AND MORRIS, R. (2004). Designing a DHT forlow latency
and high throughput. In Proceedings of the 1st Symposium on Networked Systems Design and Implementation
(NSDI). 85–98.
DOUCEUR, J. R. 2002. The sybil attack. In Revised Papers from the 1st International Workshop on Peer-to- Peer
Systems (IPTPS’01). Springer-Verlag, 251–260.
GUMMADI, R., GOVINDAN, R., KOTHARI, N., KARP, B., KIM, Y. J., AND SHENKER, S. (2004). Reduced state routing in
the internet. In Proceedings of the ACM Workshop on Hot Topics in Networks.
NG, T. S. E. AND ZHANG, H. (2004). A network positioning system for the internet. In Proceedings of the USENIX
Annual Technical Conference (ATEC’04). USENIX Association, Berkeley, CA, 11.