Visible to the public Biblio

Filters: Keyword is sybil attacks  [Clear All Filters]
2019-02-18
Zhang, X., Xie, H., Lui, J. C. S..  2018.  Sybil Detection in Social-Activity Networks: Modeling, Algorithms and Evaluations. 2018 IEEE 26th International Conference on Network Protocols (ICNP). :44–54.

Detecting fake accounts (sybils) in online social networks (OSNs) is vital to protect OSN operators and their users from various malicious activities. Typical graph-based sybil detection (a mainstream methodology) assumes that sybils can make friends with only a limited (or small) number of honest users. However, recent evidences showed that this assumption does not hold in real-world OSNs, leading to low detection accuracy. To address this challenge, we explore users' activities to assist sybil detection. The intuition is that honest users are much more selective in choosing who to interact with than to befriend with. We first develop the social and activity network (SAN), a two-layer hyper-graph that unifies users' friendships and their activities, to fully utilize users' activities. We also propose a more practical sybil attack model, where sybils can launch both friendship attacks and activity attacks. We then design Sybil SAN to detect sybils via coupling three random walk-based algorithms on the SAN, and prove the convergence of Sybil SAN. We develop an efficient iterative algorithm to compute the detection metric for Sybil SAN, and derive the number of rounds needed to guarantee the convergence. We use "matrix perturbation theory" to bound the detection error when sybils launch many friendship attacks and activity attacks. Extensive experiments on both synthetic and real-world datasets show that Sybil SAN is highly robust against sybil attacks, and can detect sybils accurately under practical scenarios, where current state-of-art sybil defenses have low accuracy.

Yuan, Y., Huo, L., Wang, Z., Hogrefe, D..  2018.  Secure APIT Localization Scheme Against Sybil Attacks in Distributed Wireless Sensor Networks. IEEE Access. 6:27629–27636.
For location-aware applications in wireless sensor networks (WSNs), it is important to ensure that sensor nodes can get correct locations in a hostile WSNs. Sybil attacks, which are vital threats in WSNs, especially in the distributed WSNs. They can forge one or multiple identities to decrease the localization accuracy, or sometimes to collapse the whole localization systems. In this paper, a novel lightweight sybilfree (SF)-APIT algorithm is presented to solve the problem of sybil attacks in APIT localization scheme, which is a popular range-free method and performs at individual node in a purely distributed fashion. The proposed SF-APIT scheme requires minimal overhead for wireless devices and works well based on the received signal strength. Simulations demonstrate that SF-APIT is an effective scheme in detecting and defending against sybil attacks with a high detection rate in distributed wireless localization schemes.
Shamieh, F., Alharbi, R..  2018.  Novel Sybil Defense Scheme for Peer–to–peer Applications. 2018 21st Saudi Computer Society National Computer Conference (NCC). :1–8.
The importance of peer-to-peer (P2P) network overlays produced enormous interest in the research community due to their robustness, scalability, and increase of data availability. P2P networks are overlays of logically connected hosts and other nodes including servers. P2P networks allow users to share their files without the need for any centralized servers. Since P2P networks are largely constructed of end-hosts, they are susceptible to abuse and malicious activity, such as sybil attacks. Impostors perform sybil attacks by assigning nodes multiple addresses, as opposed to a single address, with the goal of degrading network quality. Sybil nodes will spread malicious data and provide bogus responses to requests. To prevent sybil attacks from occurring, a novel defense mechanism is proposed. In the proposed scheme, the DHT key-space is divided and treated in a similar manner to radio frequency allocation incensing. An overlay of trusted nodes is used to detect and handle sybil nodes with the aid of source-destination pairs reporting on each other. The simulation results show that the proposed scheme detects sybil nodes in large sized networks with thousands of interactions.
Iwendi, C., Uddin, M., Ansere, J. A., Nkurunziza, P., Anajemba, J. H., Bashir, A. K..  2018.  On Detection of Sybil Attack in Large-Scale VANETs Using Spider-Monkey Technique. IEEE Access. 6:47258–47267.
Sybil security threat in vehicular ad hoc networks (VANETs) has attracted much attention in recent times. The attacker introduces malicious nodes with multiple identities. As the roadside unit fails to synchronize its clock with legitimate vehicles, unintended vehicles are identified, and therefore erroneous messages will be sent to them. This paper proposes a novel biologically inspired spider-monkey time synchronization technique for large-scale VANETs to boost packet delivery time synchronization at minimized energy consumption. The proposed technique is based on the metaheuristic stimulated framework approach by the natural spider-monkey behavior. An artificial spider-monkey technique is used to examine the Sybil attacking strategies on VANETs to predict the number of vehicular collisions in a densely deployed challenge zone. Furthermore, this paper proposes the pseudocode algorithm randomly distributed for energy-efficient time synchronization in two-way packet delivery scenarios to evaluate the clock offset and the propagation delay in transmitting the packet beacon message to destination vehicles correctly. The performances of the proposed technique are compared with existing protocols. It performs better over long transmission distances for the detection of Sybil in dynamic VANETs' system in terms of measurement precision, intrusion detection rate, and energy efficiency.
Wang, G., Wang, B., Wang, T., Nika, A., Zheng, H., Zhao, B. Y..  2018.  Ghost Riders: Sybil Attacks on Crowdsourced Mobile Mapping Services. IEEE/ACM Transactions on Networking. 26:1123–1136.
Real-time crowdsourced maps, such as Waze provide timely updates on traffic, congestion, accidents, and points of interest. In this paper, we demonstrate how lack of strong location authentication allows creation of software-based Sybil devices that expose crowdsourced map systems to a variety of security and privacy attacks. Our experiments show that a single Sybil device with limited resources can cause havoc on Waze, reporting false congestion and accidents and automatically rerouting user traffic. More importantly, we describe techniques to generate Sybil devices at scale, creating armies of virtual vehicles capable of remotely tracking precise movements for large user populations while avoiding detection. To defend against Sybil devices, we propose a new approach based on co-location edges, authenticated records that attest to the one-time physical co-location of a pair of devices. Over time, co-location edges combine to form large proximity graphs that attest to physical interactions between devices, allowing scalable detection of virtual vehicles. We demonstrate the efficacy of this approach using large-scale simulations, and how they can be used to dramatically reduce the impact of the attacks. We have informed Waze/Google team of our research findings. Currently, we are in active collaboration with Waze team to improve the security and privacy of their system.
Singh, S., Saini, H. S..  2018.  Security approaches for data aggregation in Wireless Sensor Networks against Sybil Attack. 2018 Second International Conference on Inventive Communication and Computational Technologies (ICICCT). :190–193.
A wireless sensor network consists of many important elements like Sensors, Bass station and User. A Sensor can measure many non electrical quantities like pressure, temperature, sound, etc and transmit this information to the base station by using internal transreceiver. A security of this transmitted data is very important as the data may contain important information. As wireless sensor network have many application in the military and civil domains so security of wireless sensor network become a critical concern. A Sybil attack is one of critical attack which can affect the routing protocols, fair resourse allocation, data aggregation and misbehavior detection parameters of network. A number of detection techniques to detect Sybil nodes have already designed to overcome the Sybil attack. Out of all the techniques few techniques which can improve the true detection rate and reduce false detection rate are discussed in this paper.
Afsharinejad, Armita, Hurley, Neil.  2018.  Performance Analysis of a Privacy Constrained kNN Recommendation Using Data Sketches. Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining. :10–18.
This paper evaluates two algorithms, BLIP and JLT, for creating differentially private data sketches of user profiles, in terms of their ability to protect a kNN collaborative filtering algorithm from an inference attack by third-parties. The transformed user profiles are employed in a user-based top-N collaborative filtering system. For the first time, a theoretical analysis of the BLIP is carried out, to derive expressions that relate its parameters to its performance. This allows the two techniques to be fairly compared. The impact of deploying these approaches on the utility of the system—its ability to make good recommendations, and on its privacy level—the ability of third-parties to make inferences about the underlying user preferences, is examined. An active inference attack is evaluated, that consists of the injection of a number of tailored sybil profiles into the system database. User profile data of targeted users is then inferred from the recommendations made to the sybils. Although the differentially private sketches are designed to allow the transformed user profiles to be published without compromising privacy, the attack we examine does not use such information and depends only on some pre-existing knowledge of some user preferences as well as the neighbourhood size of the kNN algorithm. Our analysis therefore assesses in practical terms a relatively weak privacy attack, which is extremely simple to apply in systems that allow low-cost generation of sybils. We find that, for a given differential privacy level, the BLIP injects less noise into the system, but for a given level of noise, the JLT offers a more compact representation.
Gupta, Diksha, Saia, Jared, Young, Maxwell.  2018.  Proof of Work Without All the Work. Proceedings of the 19th International Conference on Distributed Computing and Networking. :6:1–6:10.
Proof-of-work (PoW) is an algorithmic tool used to secure networks by imposing a computational cost on participating devices. Unfortunately, traditional PoW schemes require that correct devices perform computational work perpetually, even when the system is not under attack. We address this issue by designing a general PoW protocol that ensures two properties. First, the network stays secure. In particular, the fraction of identities in the system that are controlled by an attacker is always less than 1/2. Second, our protocol's computational cost is commensurate with the cost of an attacker. That is, the total computational cost of correct devices is a linear function of the attacker's computational cost plus the number of correct devices that have joined the system. Consequently, if the network is attacked, we ensure security, with cost that grows linearly with the attacker's cost; and, in the absence of attack, our computational cost is small. We prove similar guarantees for bandwidth cost. Our results hold in a dynamic, decentralized system where participants join and depart over time, and where the total computational power of the attacker is up to a constant fraction of the total computational power of correct devices. We show how to leverage our results to address important security problems in distributed computing including: Sybil attacks, Byzantine Consensus, and Committee Election.
Hernandez, Nestor, Rahman, Mizanur, Recabarren, Ruben, Carbunar, Bogdan.  2018.  Fraud De-Anonymization for Fun and Profit. Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. :115–130.
The persistence of search rank fraud in online, peer-opinion systems, made possible by crowdsourcing sites and specialized fraud workers, shows that the current approach of detecting and filtering fraud is inefficient. We introduce a fraud de-anonymization approach to disincentivize search rank fraud: attribute user accounts flagged by fraud detection algorithms in online peer-opinion systems, to the human workers in crowdsourcing sites, who control them. We model fraud de-anonymization as a maximum likelihood estimation problem, and introduce UODA, an unconstrained optimization solution. We develop a graph based deep learning approach to predict ownership of account pairs by the same fraudster and use it to build discriminative fraud de-anonymization (DDA) and pseudonymous fraudster discovery algorithms (PFD). To address the lack of ground truth fraud data and its pernicious impacts on online systems that employ fraud detection, we propose the first cheating-resistant fraud de-anonymization validation protocol, that transforms human fraud workers into ground truth, performance evaluation oracles. In a user study with 16 human fraud workers, UODA achieved a precision of 91%. On ground truth data that we collected starting from other 23 fraud workers, our co-ownership predictor significantly outperformed a state-of-the-art competitor, and enabled DDA and PFD to discover tens of new fraud workers, and attribute thousands of suspicious user accounts to existing and newly discovered fraudsters.
Sengupta, Jayasree, Ruj, Sushmita, Das Bit, Sipra.  2018.  An Efficient and Secure Directed Diffusion in Industrial Wireless Sensor Networks. Proceedings of the 1st International Workshop on Future Industrial Communication Networks. :41–46.
Industrial Wireless Sensor Networks (IWSNs) are an extension of the Internet of Things paradigm that integrates smart sensors in industrial processes. However, the unattended open environment makes IWSNs vulnerable to malicious attacks, such as node compromise in addition to eavesdropping. The compromised nodes can again launch notorious attacks such as the sinkhole or sybil attack which may degrade the network performance. In this paper, we propose a lightweight, Secure Directed Diffusion (SDD) protocol. The algorithm for the proposed protocol uses bilinear pairing to derive a location-based key (LK) by binding the ID and geographic location of a node, thereby ensuring neighborhood authentication. Thus, authenticated nodes can prevent eavesdropping, node compromise including sinkhole and sybil attacks while ensuring confidentiality, authenticity, integrity with reduced latency. Finally, through security analysis, we prove that basic security is maintained and above-mentioned attacks are also prevented. We also compute storage, computation and communication overheads which show that SDD performs at least 2.6 times better in terms of storage overhead and at least 1.3 times better in terms of communication overhead over the other state-of-the-art competing schemes for attack preventions in WSN domain.
2019-01-21
Khalil, M., Azer, M. A..  2018.  Sybil attack prevention through identity symmetric scheme in vehicular ad-hoc networks. 2018 Wireless Days (WD). :184–186.
Vehicular Ad-hoc Networks (VANETs) are a subset of Mobile Ad-hoc Networks (MANETs). They are deployed to introduce the ability of inter-communication among vehicles in order to guarantee safety and provide services for people while driving. VANETs are exposed to many types of attacks like denial of service, spoofing, ID disclosure and Sybil attacks. In this paper, a novel lightweight approach for preventing Sybil attack in VANETs is proposed. The presented protocol scheme uses symmetric key encryption and authentication between Road Side Units (RSUs) and vehicles on the road so that no malicious vehicle could gain more than one identity inside the network. This protocol does not need managers for Road Side Units (RSUs) or Certification Authority (CA) and uses minimum amount of messages exchanged with RSU making the scheme efficient and effective.
2018-05-02
Gu, P., Khatoun, R., Begriche, Y., Serhrouchni, A..  2017.  k-Nearest Neighbours classification based Sybil attack detection in Vehicular networks. 2017 Third International Conference on Mobile and Secure Services (MobiSecServ). :1–6.

In Vehicular networks, privacy, especially the vehicles' location privacy is highly concerned. Several pseudonymous based privacy protection mechanisms have been established and standardized in the past few years by IEEE and ETSI. However, vehicular networks are still vulnerable to Sybil attack. In this paper, a Sybil attack detection method based on k-Nearest Neighbours (kNN) classification algorithm is proposed. In this method, vehicles are classified based on the similarity in their driving patterns. Furthermore, the kNN methods' high runtime complexity issue is also optimized. The simulation results show that our detection method can reach a high detection rate while keeping error rate low.

Gu, P., Khatoun, R., Begriche, Y., Serhrouchni, A..  2017.  Support Vector Machine (SVM) Based Sybil Attack Detection in Vehicular Networks. 2017 IEEE Wireless Communications and Networking Conference (WCNC). :1–6.

Vehicular networks have been drawing special atten- tion in recent years, due to its importance in enhancing driving experience and improving road safety in future smart city. In past few years, several security services, based on cryptography, PKI and pseudonymous, have been standardized by IEEE and ETSI. However, vehicular networks are still vulnerable to various attacks, especially Sybil attack. In this paper, a Support Vector Machine (SVM) based Sybil attack detection method is proposed. We present three SVM kernel functions based classifiers to distinguish the malicious nodes from benign ones via evaluating the variance in their Driving Pattern Matrices (DPMs). The effectiveness of our proposed solution is evaluated through extensive simulations based on SUMO simulator and MATLAB. The results show that the proposed detection method can achieve a high detection rate with low error rate even under a dynamic traffic environment.

Yao, Y., Xiao, B., Wu, G., Liu, X., Yu, Z., Zhang, K., Zhou, X..  2017.  Voiceprint: A Novel Sybil Attack Detection Method Based on RSSI for VANETs. 2017 47th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). :591–602.

Vehicular Ad Hoc Networks (VANETs) enable vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) communications that bring many benefits and conveniences to improve the road safety and drive comfort in future transportation systems. Sybil attack is considered one of the most risky threats in VANETs since a Sybil attacker can generate multiple fake identities with false messages to severely impair the normal functions of safety-related applications. In this paper, we propose a novel Sybil attack detection method based on Received Signal Strength Indicator (RSSI), Voiceprint, to conduct a widely applicable, lightweight and full-distributed detection for VANETs. To avoid the inaccurate position estimation according to predefined radio propagation models in previous RSSI-based detection methods, Voiceprint adopts the RSSI time series as the vehicular speech and compares the similarity among all received time series. Voiceprint does not rely on any predefined radio propagation model, and conducts independent detection without the support of the centralized infrastructure. It has more accurate detection rate in different dynamic environments. Extensive simulations and real-world experiments demonstrate that the proposed Voiceprint is an effective method considering the cost, complexity and performance.

Zhang, P., Zhang, X., Sun, X., Liu, J. K., Yu, J., Jiang, Z. L..  2017.  Anonymous Anti-Sybil Attack Protocol for Mobile Healthcare Networks Analytics. 2017 IEEE Trustcom/BigDataSE/ICESS. :668–674.

Mobile Healthcare Networks (MHN) continuouslycollect the patients' health data sensed by wearable devices, andanalyze the collected data pre-processed by servers combinedwith medical histories, such that disease diagnosis and treatmentare improved, and the heavy burden on the existing healthservices is released. However, the network is vulnerable to Sybilattacks, which would degrade network performance, disruptproceedings, manipulate data or cheat others maliciously. What'smore, the user is reluctant to leak identity privacy, so the identityprivacy preserving makes Sybil defenses more difficult. One ofthe best choices is mutually authenticating each other with noidentity information involved. Thus, we propose a fine-grainedauthentication scheme based on Attribute-Based Signature (ABS)using lattice assumption, where a signer is authorized by an at-tribute set instead of single identity string. This ABS scheme usesFiat-Shamir framework and supports flexible threshold signaturepredicates. Moreover, to anonymously guarantee integrity andavailability of health data in MHN, we design an anonymousanti-Sybil attack protocol based on our ABS scheme, so thatSybil attacks are prevented. As there is no linkability betweenidentities and services, the users' identity privacy is protected. Finally, we have analyzed the security and simulated the runningtime for our proposed ABS scheme.

Garip, M. T., Kim, P. H., Reiher, P., Gerla, M..  2017.  INTERLOC: An interference-aware RSSI-based localization and sybil attack detection mechanism for vehicular ad hoc networks. 2017 14th IEEE Annual Consumer Communications Networking Conference (CCNC). :1–6.

Vehicular ad hoc networks (VANETs) are designed to provide traffic safety by exploiting the inter-vehicular communications. Vehicles build awareness of traffic in their surroundings using information broadcast by other vehicles, such as speed, location and heading, to proactively avoid collisions. The effectiveness of these VANET traffic safety applications is particularly dependent on the accuracy of the location information advertised by each vehicle. Therefore, traffic safety can be compromised when Sybil attackers maliciously advertise false locations or other inaccurate GPS readings are sent. The most effective way to detect a Sybil attack or correct the noise in the GPS readings is localizing vehicles based on the physical features of their transmission signals. The current localization techniques either are designed for networks where the nodes are immobile or suffer from inaccuracy in high-interference environments. In this paper, we present a RSSI-based localization technique that uses mobile nodes for localizing another mobile node and adjusts itself based on the heterogeneous interference levels in the environment. We show via simulation that our localization mechanism is more accurate than the other mechanisms and more resistant to environments with high interference and mobility.

Rajan, A., Jithish, J., Sankaran, S..  2017.  Sybil attack in IOT: Modelling and defenses. 2017 International Conference on Advances in Computing, Communications and Informatics (ICACCI). :2323–2327.

Internet of Things (IoT) is an emerging paradigm in information technology (IT) that integrates advancements in sensing, computing and communication to offer enhanced services in everyday life. IoTs are vulnerable to sybil attacks wherein an adversary fabricates fictitious identities or steals the identities of legitimate nodes. In this paper, we model sybil attacks in IoT and evaluate its impact on performance. We also develop a defense mechanism based on behavioural profiling of nodes. We develop an enhanced AODV (EAODV) protocol by using the behaviour approach to obtain the optimal routes. In EAODV, the routes are selected based on the trust value and hop count. Sybil nodes are identified and discarded based on the feedback from neighbouring nodes. Evaluation of our protocol in ns-2 simulator demonstrates the effectiveness of our approach in identifying and detecting sybil nodes in IoT network.

Chothia, Tom, Ordean, Mihai, de Ruiter, Joeri, Thomas, Richard J..  2017.  An Attack Against Message Authentication in the ERTMS Train to Trackside Communication Protocols. Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security. :743–756.
This paper presents the results of a cryptographic analysis of the protocols used by the European Rail Traffic Management System (ERTMS). A stack of three protocols secures the communication between trains and trackside equipment; encrypted radio communication is provided by the GSM-R protocol, on top of this the EuroRadio protocol provides authentication for a train control application-level protocol. We present an attack which exploits weaknesses in all three protocols: GSM-R has the same well known weaknesses as the GSM protocol, and we present a new collision attack against the EuroRadio protocol. Combined with design weaknesses in the application-level protocol, these vulnerabilities allow an attacker, who observes a MAC collision, to forge train control messages. We demonstrate this attack with a proof of concept using train control messages we have generated ourselves. Currently, ERTMS is only used to send small amounts of data for short sessions, therefore this attack does not present an immediate danger. However, if EuroRadio was to be used to transfer larger amounts of data trains would become vulnerable to this attack. Additionally, we calculate that, under reasonable assumptions, an attacker who could monitor all backend control centres in a country the size of the UK for 45 days would have a 1% chance of being able to take control of a train.
Allodi, Luca, Etalle, Sandro.  2017.  Towards Realistic Threat Modeling: Attack Commodification, Irrelevant Vulnerabilities, and Unrealistic Assumptions. Proceedings of the 2017 Workshop on Automated Decision Making for Active Cyber Defense. :23–26.
Current threat models typically consider all possible ways an attacker can penetrate a system and assign probabilities to each path according to some metric (e.g. time-to-compromise). In this paper we discuss how this view hinders the realness of both technical (e.g. attack graphs) and strategic (e.g. game theory) approaches of current threat modeling, and propose to steer away by looking more carefully at attack characteristics and attacker environment. We use a toy threat model for ICS attacks to show how a realistic view of attack instances can emerge from a simple analysis of attack phases and attacker limitations.
Dang, Hung, Huang, Yue, Chang, Ee-Chien.  2017.  Evading Classifiers by Morphing in the Dark. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. :119–133.
Learning-based systems have been shown to be vulnerable to evasion through adversarial data manipulation. These attacks have been studied under assumptions that the adversary has certain knowledge of either the target model internals, its training dataset or at least classification scores it assigns to input samples. In this paper, we investigate a much more constrained and realistic attack scenario wherein the target classifier is minimally exposed to the adversary, revealing only its final classification decision (e.g., reject or accept an input sample). Moreover, the adversary can only manipulate malicious samples using a blackbox morpher. That is, the adversary has to evade the targeted classifier by morphing malicious samples "in the dark". We present a scoring mechanism that can assign a real-value score which reflects evasion progress to each sample based on the limited information available. Leveraging on such scoring mechanism, we propose an evasion method – EvadeHC? and evaluate it against two PDF malware detectors, namely PDFRate and Hidost. The experimental evaluation demonstrates that the proposed evasion attacks are effective, attaining 100% evasion rate on the evaluation dataset. Interestingly, EvadeHC outperforms the known classifier evasion techniques that operate based on classification scores output by the classifiers. Although our evaluations are conducted on PDF malware classifiers, the proposed approaches are domain agnostic and are of wider application to other learning-based systems.
Petsios, Theofilos, Zhao, Jason, Keromytis, Angelos D., Jana, Suman.  2017.  SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. :2155–2168.
Algorithmic complexity vulnerabilities occur when the worst-case time/space complexity of an application is significantly higher than the respective average case for particular user-controlled inputs. When such conditions are met, an attacker can launch Denial-of-Service attacks against a vulnerable application by providing inputs that trigger the worst-case behavior. Such attacks have been known to have serious effects on production systems, take down entire websites, or lead to bypasses of Web Application Firewalls. Unfortunately, existing detection mechanisms for algorithmic complexity vulnerabilities are domain-specific and often require significant manual effort. In this paper, we design, implement, and evaluate SlowFuzz, a domain-independent framework for automatically finding algorithmic complexity vulnerabilities. SlowFuzz automatically finds inputs that trigger worst-case algorithmic behavior in the tested binary. SlowFuzz uses resource-usage-guided evolutionary search techniques to automatically find inputs that maximize computational resource utilization for a given application. We demonstrate that SlowFuzz successfully generates inputs that match the theoretical worst-case performance for several well-known algorithms. SlowFuzz was also able to generate a large number of inputs that trigger different algorithmic complexity vulnerabilities in real-world applications, including various zip parsers used in antivirus software, regular expression libraries used in Web Application Firewalls, as well as hash table implementations used in Web applications. In particular, SlowFuzz generated inputs that achieve 300-times slowdown in the decompression routine of the bzip utility, discovered regular expressions that exhibit matching times exponential in the input size, and also managed to automatically produce inputs that trigger a high number of collisions in PHP's default hashtable implementation.
Friebe, Sebastian, Florian, Martin.  2017.  DPS-Discuss: Demonstrating Decentralized, Pseudonymous, Sybil-resistant Communication. Proceedings of the SIGCOMM Posters and Demos. :74–75.
A current trend on the Internet is the increasing surveillance of its users. A few big service providers have divided most of the user-facing Internet between them, observing and recording the activities of their users to increase profits. Additionally, government agencies have been found to practice mass surveillance. With regard to this it becomes even more important to provide online services that protect the privacy of their users and avoid censorship by single, powerful entities. To reach these goals, a trusted third party should be avoided. A prototype service which fulfills these goals is DPS-Discuss, a decentralized, pseudonymous online discussion application. It uses the libraries BitNym and Peer-Tor-Peer for pseudonym management and anonymous communication.
Pass, Rafael, Shi, Elaine.  2017.  FruitChains: A Fair Blockchain. Proceedings of the ACM Symposium on Principles of Distributed Computing. :315–324.
Nakamoto's famous blockchain protocol enables achieving consensus in a so-called permissionless setting—anyone can join (or leave) the protocol execution, and the protocol instructions do not depend on the identities of the players. His ingenious protocol prevents "sybil attacks" (where an adversary spawns any number of new players) by relying on computational puzzles (a.k.a. "moderately hard functions") introduced by Dwork and Naor (Crypto'92). Recent work by Garay et al (EuroCrypt'15) and Pass et al (manuscript, 2016) demonstrate that this protocol provably achieves consistency and liveness assuming a) honest players control a majority of the computational power in the network, b) the puzzle-hardness is appropriately set as a function of the maximum network delay and the total computational power of the network, and c) the computational puzzle is modeled as a random oracle. Assuming honest participation, however, is a strong assumption, especially in a setting where honest players are expected to perform a lot of work (to solve the computational puzzles). In Nakamoto's Bitcoin application of the blockchain protocol, players are incentivized to solve these puzzles by receiving rewards for every "block" (of transactions) they contribute to the blockchain. An elegant work by Eyal and Sirer (FinancialCrypt'14), strengthening and formalizing an earlier attack discussed on the Bitcoin forum, demonstrates that a coalition controlling even a minority fraction of the computational power in the network can gain (close to) 2 times its "fair share" of the rewards (and transaction fees) by deviating from the protocol instructions. In contrast, in a fair protocol, one would expect that players controlling a φ fraction of the computational resources to reap a φ fraction of the rewards. We present a new blockchain protocol—the FruitChain protocol—which satisfies the same consistency and liveness properties as Nakamoto's protocol (assuming an honest majority of the computing power), and additionally is δ-approximately fair: with overwhelming probability, any honest set of players controlling a φ fraction of computational power is guaranteed to get at least a fraction (1-δ)φ of the blocks (and thus rewards) in any Ω(κ/δ) length segment of the chain (where κ is the security parameter). Consequently, if this blockchain protocol is used as the ledger underlying a cryptocurrency system, where rewards and transaction fees are evenly distributed among the miners of blocks in a length κ segment of the chain, no coalition controlling less than a majority of the computing power can gain more than a factor (1+3δ) by deviating from the protocol (i.e., honest participation is an n/2-coalition-safe 3δ-Nash equilibrium). Finally, the FruitChain protocol enables decreasing the variance of mining rewards and as such significantly lessens (or even obliterates) the need for mining pools.
2017-05-17
Saab, Farah, Kayssi, Ayman, Elhajj, Imad, Chehab, Ali.  2016.  Solving Sybil Attacks Using Evolutionary Game Theory. Proceedings of the 31st Annual ACM Symposium on Applied Computing. :2195–2201.

Recommender systems have become quite popular recently. However, such systems are vulnerable to several types of attacks that target user ratings. One such attack is the Sybil attack where an entity masquerades as several identities with the intention of diverting user ratings. In this work, we propose evolutionary game theory as a possible solution to the Sybil attack in recommender systems. After modeling the attack, we use replicator dynamics to solve for evolutionary stable strategies. Our results show that under certain conditions that are easily achievable by a system administrator, the probability of an attack strategy drops to zero implying degraded fitness for Sybil nodes that eventually die out.

Schoenebeck, Grant, Snook, Aaron, Yu, Fang-Yi.  2016.  Sybil Detection Using Latent Network Structure. Proceedings of the 2016 ACM Conference on Economics and Computation. :739–756.

Sybil attacks, in which an adversary creates a large number of identities, present a formidable problem for the robustness of recommendation systems. One promising method of sybil detection is to use data from social network ties to implicitly infer trust. Previous work along this dimension typically a) assumes that it is difficult/costly for an adversary to create edges to honest nodes in the network; and b) limits the amount of damage done per such edge, using conductance-based methods. However, these methods fail to detect a simple class of sybil attacks which have been identified in online systems. Indeed, conductance-based methods seem inherently unable to do so, as they are based on the assumption that creating many edges to honest nodes is difficult, which seems to fail in real-world settings. We create a sybil defense system that accounts for the adversary's ability to launch such attacks yet provably withstands them by: Notassuminganyrestrictiononthenumberofedgesanadversarycanform,butinsteadmakingamuch weaker assumption that creating edges from sybils to most honest nodes is difficult, yet allowing that the remaining nodes can be freely connected to. Relaxing the goal from classifying all nodes as honest or sybil to the goal of classifying the "core" nodes of the network as honest; and classifying no sybil nodes as honest. Exploiting a new, for sybil detection, social network property, namely, that nodes can be embedded in low-dimensional spaces.