An official website of the United States government
A common tool to defend against Sybil attacks is proof-of-work, whereby computational puzzles are used to limit the number of Sybil participants. Unfortunately, current Sybil defenses require significant computational effort to offset an attack. In particular, good participants must spend computationally at a rate that is proportional to the spending rate of an attacker. In this paper, we present the first Sybil defense algorithm which is asymmetric in the sense that good participants spend at a rate that is asymptotically less than an attacker. In particular, if T is the rate of the attacker's spending, and J is the rate of joining good participants, then our algorithm spends at a rate of O( sqrt{TJ} + J ). We provide empirical evidence that our algorithm can be significantly more efficient than previous defenses under various attack scenarios. Additionally, we prove a lower bound showing that our algorithm's spending rate is asymptotically optimal among a large family of algorithms.
more »
« less
Exploiting Temporal Dynamics in Sybil Defenses
Sybil attacks present a significant threat to many Internet systems and applications, in which a single adversary inserts multiple colluding identities in the system to compromise its security and privacy. Recent work has advocated the use of social-network-based trust relationships to defend against Sybil attacks. However, most of the prior security analyses of such systems examine only the case of social networks at a single instant in time. In practice, social network connections change over time, and attackers can also cause limited changes to the networks. In this work, we focus on the temporal dynamics of a variety of social-network-based Sybil defenses. We describe and examine the effect of novel attacks based on: (a) the attacker's ability to modify Sybil-controlled parts of the social-network graph, (b) his ability to change the connections that his Sybil identities maintain to honest users, and (c) taking advantage of the regular dynamics of connections forming and breaking in the honest part of the social network. We find that against some defenses meant to be fully distributed, such as SybilLimit and Persea, the attacker can make dramatic gains over time and greatly undermine the security guarantees of the system. Even against centrally controlled Sybil defenses, the attacker can eventually evade detection (e.g. against SybilInfer and SybilRank) or create denial-of-service conditions (e.g. against Ostra and SumUp). After analysis and simulation of these attacks using both synthetic and real-world social network topologies, we describe possible defense strategies and the trade-offs that should be explored. It is clear from our findings that temporal dynamics need to be accounted for in Sybil defense or else the attacker will be able to undermine the system in unexpected and possibly dangerous ways.
more »
« less
- Award ID(s):
- 1423163
- PAR ID:
- 10018815
- Date Published:
- Journal Name:
- Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security
- Page Range / eLocation ID:
- 805 to 816
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Schedule randomization is one of the recently introduced security defenses against schedule-based attacks, i.e., attacks whose success depends on a particular ordering between the execution window of an attacker and a victim task within the system. It falls into the category of information hiding (as opposed to deterministic isolation-based defenses) and is designed to reduce the attacker's ability to infer the future schedule. This paper aims to investigate the limitations and vulnerabilities of schedule randomization-based defenses in real-time systems. We first provide definitions, categorization, and examples of schedule-based attacks, and then discuss the challenges of employing schedule randomization in real-time systems. Further, we provide a preliminary security test to determine whether a certain timing relation between the attacker and victim tasks will never happen in systems scheduled by a fixed-priority scheduling algorithm. Finally, we compare fixed-priority scheduling against schedule-randomization techniques in terms of the success rate of various schedule-based attacks for both synthetic and real-world applications. Our results show that, in many cases, schedule randomization either has no security benefits or can even increase the success rate of the attacker depending on the priority relation between the attacker and victim tasks.more » « less
-
Most of the cybersecurity research focus on either presenting a specific vulnerability %or hacking technique, or proposing a specific defense algorithm to defend against a well-defined attack scheme. Although such cybersecurity research is important, few have paid attention to the dynamic interactions between attackers and defenders, where both sides are intelligent and will dynamically change their attack or defense strategies in order to gain the upper hand over their opponents. This 'cyberwar' phenomenon exists among most cybersecurity incidents in the real world, which warrants special research and analysis. In this paper, we propose a dynamic game theoretic framework (i.e., hyper defense) to analyze the interactions between the attacker and the defender as a non-cooperative security game. The key idea is to model attackers/defenders to have multiple levels of attack/defense strategies that are different in terms of effectiveness, strategy costs, and attack gains/damages. Each player adjusts his strategy based on the strategy's cost, potential attack gain/damage, and effectiveness in anticipating of the opponent's strategy. We study the achievable Nash equilibrium for the attacker-defender security game where the players employ an efficient strategy according to the obtained equilibrium. Furthermore, we present case studies of three different types of network attacks and put forth how our hyper defense system can successfully model them. Simulation results show that the proposed game theoretical system achieves a better performance compared to two other fixed-strategy defense systems.more » « less
-
The increasing penetration of cyber systems into smart grids has resulted in these grids being more vulnerable to cyber physical attacks. The central challenge of higher order cyber-physical contingency analysis is the exponential blow-up of the attack surface due to a large number of attack vectors. This gives rise to computational challenges in devising efficient attack mitigation strategies. However, a system operator can leverage private information about the underlying network to maintain a strategic advantage over an adversary equipped with superior computational capability and situational awareness. In this work, we examine the following scenario: A malicious entity intrudes the cyber-layer of a power network and trips the transmission lines. The objective of the system operator is to deploy security measures in the cyber-layer to minimize the impact of such attacks. Due to budget constraints, the attacker and the system operator have limits on the maximum number of transmission lines they can attack or defend. We model this adversarial interaction as a resource-constrained attacker-defender game. The computational intractability of solving large security games is well known. However, we exploit the approximately modular behavior of an impact metric known as the disturbance value to arrive at a linear-time algorithm for computing an optimal defense strategy. We validate the efficacy of the proposed strategy against attackers of various capabilities and provide an algorithm for a real-time implementation.more » « less
-
Crowdsensing leverages the rapid growth of sensor-embedded smartphones and human mobility for pervasive information collection. To incentivize smartphone users to participate in crowdsensing, many auction-based incentive mechanisms have been proposed for both offline and online scenarios. It has been demonstrated that the Sybil attack may undermine these mechanisms. In a Sybil attack, a user illegitimately pretends multiple identities to gain benefits. Sybil-proof incentive mechanisms have been proposed for the offline scenario. However, the problem of designing Sybil-proof online incentive mechanisms for crowdsensing is still open. Compared to the offline scenario, the online scenario provides users one more dimension of flexibility, i.e., active time, to conduct Sybil attacks, which makes this problem more challenging. In this paper, we design Sybil-proof online incentive mechanisms to deter the Sybil attack for crowdsensing. Depending on users’ flexibility on performing their tasks, we investigate both single-minded and multi-minded cases and propose SOS and SOM, respectively. SOS achieves computational efficiency, individual rationality, truthfulness, and Sybil-proofness. SOM achieves individual rationality, truthfulness, and Sybil-proofness. Through extensive simulations, we evaluate the performance of SOS and SOM.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1145/2810103.2813693
