Graphs are a ubiquitous form of structured data, with applications in many privacy-sensitive domains, such as social and healthcare. As for other modalities, modern graph synthesizers enable the creation of realistic synthetic samples, facilitating privacy-preserving data sharing while maintaining high utility. Unfortunately, unlike such other modalities, there is no relevant work on evaluating the privacy risk associated with synthetic graphs. The fact that graphs, unlike, e.g., tables, naturally capture relationships between individuals means that existing approaches are not easily transferable. To allow quantifying these privacy risks, we introduce SyntheGrAnon, a framework for evaluating synthetic graph anonymity. SyntheGrAnon primarily targets the singling out, linkability, and inference risks outlined in the EU GDPR at the node and community levels, while also including edge-level attacks as an extension of the node-level setting. We design attacks tailored to synthetic graphs and, in addition, extend the existing methodology by leveraging multiple synthetic samples for our black-box attacks. In our evaluation, spanning datasets from social and financial domains and five generative graph models, including three modern diffusion-based options, we find that our attacks are mostly effective, achieving risks close to the maximum of 1 in some cases. However, they struggle with large-scale, attribute-scarce graphs.

In many places, a surge of micro-mobility sharing systems, as for instance e-scooters, can be observed. Shared micro-mobility is a cost-efficient and flexible alternative to owning vehicles and, furthermore, leads to reduced traffic and air pollution. However, sharing information about vehicles impacts the privacy of the individuals using such vehicles as changes in vehicle state are linked to an individual’s mobility pattern. Malicious exploitation of knowledge on mobility patterns of individuals may assist in criminal activities such as stalking or burglary. Thus, it is very important that micro-mobility sharing platforms do not leak sensitive data about the mobility patterns of their users, resulting in a tradeoff between sharing and privacy.To characterize the privacy leakage in one specific instance of shared micro-mobility, we conducted a large-scale, long-term data collection from scooters run by the e-scooter company Tier in the European university town Kaiserslautern. Indeed, the data reveals several privacy issues: For instance, we were able to reconstruct work and school schedules of various individuals. Furthermore, we could infer interests and hobbies by visits to, e.g., sports facilities. Our initial discovery of such leakages was aided by the fact that the specific e-scooter company does not comply with existing privacy standards, in particular the use of dynamic IDs. Yet, an a-posteriori analysis of our data shows that even with dynamic IDs, we are able to re-construct 80% of the trips, which still constitutes a substantial privacy leakage.

The convergence of 6G and WiFi technologies promises unprecedented online connectivity, enabling immersive experiences such as the Metaverse, with a particular emphasis on VR gaming. Despite these advancements, they bring to light considerable privacy concerns, especially the ability of adversaries to deduce personal information from encrypted gaming network traffic. Focusing on VR headsets and Nintendo Switch consoles, this study explores the privacy implications within such network environments. By simulating the typical network conditions of online multiplayer games, we expose potential privacy breaches by adversaries from both WiFi and WAN, including mobile service providers. Classical machine learning algorithms can successfully classify games and gaming consoles with an accuracy exceeding 90%, further dissecting the network traffic to unveil distinct signatures and assess privacy risks.

The Lightning Network, a payment channel network with a market cap of over 192M USD, is designed to resolve Bitcoin's scalability issues through fast off-chain transactions. There are multiple Lightning Network client implementations, all of which conform to the same textual specifications known as BOLTs. Several vulnerabilities have been manually discovered, but to-date there have been few works systematically analyzing the security of the Lightning Network.

Federated learning (FL) enables clients to collabo-ratively learn models without revealing their local data. However, the shared model updates still reveal information about the data set, as indicated by a number of attacks on privacy. While privacy in the context of single data use is well-studied, users may provide the same data for multiple tasks. Hence, we focus on the case when data is re-used in the presence of multiple colluding servers, either the same or the different training tasks. We develop Collusive Gradient Inversion (CGI), an attack that combines multiple gradients computed on the same data to reconstruct the original data. The theoretical bound on how privacy leakage increases with the number of re-use is analyzed for the same task reconstruction. We then show that Nash bargaining games are effective in determining aggregation weights while integrating contributions from different tasks. We experimentally validate the increased quality of the reconstructed image in comparison to single-server reconstruction, both with and without defense mechanisms. Our code for reproducing is available at: https://github.com/GillHuang-Xtler/CGI.

Attacks on Federated Learning (FL) can severely reduce the quality of the generated models and limit the usefulness of this emerging learning paradigm that enables on-premise decentralized learning. However, existing untargeted attacks are not practical for many scenarios as they assume that i) the attacker knows every update of benign clients, or ii) the attacker has a large dataset to locally train updates imitating benign parties. In this paper, we propose a data-free untargeted attack (DFA) that synthesizes malicious data to craft adversarial models without eavesdropping on the transmission of benign clients at all or requiring a large quantity of task-specific training data. We design two variants of DFA, namely DFA-R and DFA-G, which differ in how they trade off stealthiness and effectiveness. Specifically, DFA-R iteratively optimizes a malicious data layer to minimize the prediction confidence of all outputs of the global model, whereas DFA-G interactively trains a malicious data generator network by steering the output of the global model toward a particular class. Experimental results on Fashion-MNIST, Cifar-10, and SVHN show that DFA, despite requiring fewer assumptions than existing attacks, achieves similar or even higher attack success rate than state-of-the-art untargeted attacks against various state-of-the-art defense mechanisms. Concretely, they can evade all considered defense mechanisms in at least 50% of the cases for CIFAR-10 and often reduce the accuracy by more than a factor of 2. Consequently, we design REFD, a defense specifically crafted to protect against data-free attacks. REFD leverages a reference dataset to detect updates that are biased or have a low confidence. It greatly improves upon existing defenses by filtering out the malicious updates and achieves high global model accuracy.

Federated Learning is highly susceptible to backdoor and targeted attacks as participants can manipulate their data and models locally without any oversight on whether they follow the correct process. There are a number of server-side defenses that mitigate the attacks by modifying or rejecting local updates submitted by clients. However, we find that bursty adversarial patterns with a high variance in the number of malicious clients can circumvent the existing defenses. We propose a client-self defense, LeadFL, that is combined with existing server-side defenses to thwart backdoor and targeted attacks. The core idea of LeadFL is a novel regularization term in local model training such that the Hessian matrix of local gradients is nullified. We provide the convergence analysis of LeadFL and its robustness guarantee in terms of certified radius. Our empirical evaluation shows that LeadFL is able to mitigate bursty adversarial patterns for both iid and non-iid data distributions. It frequently reduces the backdoor accuracy from more than 75% for state-of-the-art defenses to less than 10% while its impact on the main task accuracy is always less than for other client-side defenses.

In PCNs, nodes that forward payments between a source and a receiver are paid a small fee if the payment is successful. The fee is a compensation for temporarily committing funds to the payment. However, payments may fail due to insufficient funds or attacks, often after considerable delays of up to several days, leaving a node without compensation. Furthermore, attackers can intentionally cause failed payments, e.g., to infer private information (like channel balances), without any cost in fees. In this paper, we first use extensive form games to formally characterize the conditions that lead to rational intermediaries refusing (or agreeing) to forward payments. An intermediary’s decision to forward or not depends on the probability of failure, which they approximate based on past experience. We then propose and analyze an alternative fee model that allows the sender to determine and pay a fraction of the fee to intermediaries in a non-refundable manner. A rational sender chooses the fraction such that the intermediaries’ utility for forwarding the payment exceeds their utility for not forwarding. Our simulation study, based on real-world Lightning snapshots, confirms that our novel mechanism can increase the probability of successful payments by 12% and decrease routing fees for senders by about 6% if all nodes behave rationally. Furthermore, previously cost-free probing attacks now require that the attacker pays 1500 satoshis for every 1 million satoshis inferred.

Abstract Federated learning (FL) enables collaborative learning between parties, called clients, without sharing the original and potentially sensitive data. To ensure fast convergence in the presence of such heterogeneous clients, it is imperative to timely select clients who can effectively contribute to learning. A realistic but overlooked case of heterogeneous clients are Mavericks, who monopolize the possession of certain data types, e.g., children hospitals possess most of the data on pediatric cardiology. In this paper, we address the importance and tackle the challenges of Mavericks by exploring two types of client selection strategies. First, we show theoretically and through simulations that the common contribution-based approach, Shapley Value, underestimates the contribution of Mavericks and is hence not effective as a measure to select clients. Then, we propose FedEMD, an adaptive strategy with competitive overhead based on the Wasserstein distance, supported by a proven convergence bound. As FedEMD adapts the selection probability such that Mavericks are preferably selected when the model benefits from improvement on rare classes, it consistently ensures the fast convergence in the presence of different types of Mavericks. Compared to existing strategies, including Shapley Value-based ones, FedEMD improves the convergence speed of neural network classifiers with FedAvg aggregation by 26.9% and its performance is consistent across various levels of heterogeneity.

Payment channel networks (PCNs) enhance the scalability of block-chains by allowing parties to conduct transactions off-chain, i.e, without broadcasting every transaction to all blockchain participants. To conduct transactions, a sender and a receiver can either establish a direct payment channel with a funding blockchain transaction or leverage existing channels in a multi-hop payment. The security of PCNs usually relies on the synchrony of the underlying blockchain, i.e., evidence of misbehavior needs to be published on the blockchain within a time limit. Alternative payment channel proposals that do not require blockchain synchrony rely on quorum certificates and use a committee to register the transactions of a channel. However, these proposals do not support multi-hop payments, a limitation we aim to overcome.

Lightning, the prevailing solution to Bitcoin’s scalability issue, uses onion routing to hide senders and recipients of payments. Yet, the path between the sender and the recipient along which payments are routed is selected such that it is short, cost efficient, and fast. The low degree of randomness in the path selection entails that anonymity sets are small. However, quantifying the anonymity provided by Lightning is challenging due to the existence of multiple implementations that differ with regard to the path selection algorithm and exist in parallel within the network. In this paper, we propose a general method allowing a local internal attacker to determine sender and recipient anonymity sets. Based on an in-depth code review of three Lightning implementations, we analyze how an adversary can predict the sender and the recipient of a multi-hop transaction. Our simulations indicate that only one adversarial node on a payment path uniquely identifies at least one of sender and recipient for around 70% of the transactions observed by the adversary. Moreover, multiple colluding attackers can almost always identify sender and receiver uniquely.

Greedy embeddings on rooted spanning trees are the most promising solution to provide sufficiently scalable routing in dynamic networks with restricted topologies, for instance friend-to-friend overlays such as the Dark Freenet and payment channel networks such as Lightning. Yet, they are not deployed in practice, as electing a root and configuring addresses remains an unsolved problem in adverse environments. Indeed, faulty or malicious nodes might provide incorrect coordinates, prevent the network from stabilizing by simulating dynamics, or not start the assignment of coordinates in their subtree at all. All of the above attacks may result in an inability to route. To mitigate the above attacks, we design a novel embedding algorithm with an adapted distance metric that only relies on interconnections between benign subtrees for successful delivery. In other words, even if roots of (sub-)trees are malicious or faulty, the remaining nodes still receive coordinates and can communicate with nodes in their tree branch as well as other branches reachable via the neighborhood of their benign ancestors. Extensive simulations demonstrate that we thus facilitate efficient routing even when seemingly decisive parts of the network are under adversarial control.

Nodes in route-restricted overlays have an immutable set of neighbors, explicitly specified by their users. Popular examples include payment networks such as the Lightning network as well as social overlays such as the Dark Freenet. Routing algorithms are central to such overlays as they enable communication between nodes that are not directly connected. Recent results show that algorithms based on spanning trees are the most promising provably efficient choice. However, all suggested solutions fail to address how distributed spanning tree algorithms can deal with active denial of service attacks by malicious nodes. In this work, we design a novel self-stabilizing spanning tree construction algorithm that utilizes cryptographic signatures and prove that it reduces the set of nodes affected by active attacks. Our simulations substantiate this theoretical result with concrete values based on real-world data sets. In particular, our results indicate that our algorithm reduces the number of affected nodes by up to 74% compared to state-of-the-art attack-resistant spanning tree constructions.

Online streaming is a popular service for data-intensive applications such as video streaming. P2P-based streaming solutions are advocated to help reduce costs for both providers and users. Yet, involving users over data dissemination entails security risks including a variety of denial-of-service attacks. While extensive research exists on mitigating varied attack types, their effectiveness is limited if the attacker can infer information about the topology such as the identity of nodes that have direct connections to the source. The attacker can then leverage the gained insights to place malicious participants in prominent positions. By dropping chunks that should be forwarded, the malicious peers degrade the performance in a stealthy way that does not raise suspicion. We first demonstrate the feasibility of conducting such attacks. Accordingly, we propose a detection mechanism that identifies the attack and removes potential malicious peers from their disruptive positions. We ascertain, theoretically and through simulations, that malicious peers cannot misuse the detection mechanism to gain influence. Our simulation-based study indicates that the proposed detection mechanism is able to detect malicious peers with up to 80-90% accuracy while inducing a small overhead of approximately 8%.

Balancing the load in content addressing schemes for route-restricted networks represents a challenge with a wide range of applications. Solutions based on greedy embeddings maintain minimal state information and enable efficient routing, but any such solutions currently result in either imbalanced content addressing, overloading individual nodes, or are unable to efficiently account for network dynamics. In this work, we propose a greedy embedding in combination with a content addressing scheme that provides balanced content addressing while at the same time enabling efficient stabilization in the presence of network dynamics. We point out the tradeoff between stabilization complexity and maximal permitted imbalance when deriving upper bounds on both metrics for two variants of the proposed algorithms. Furthermore, we substantiate these bounds through a simulation study based on both real-world and synthetic data.

Friend-to-friend (F2F) overlays, which restrict direct communication to mutually trusted parties, are a promising substrate for privacy-preserving communication due to their inherent membership-concealment and Sybil-resistance. Yet, existing F2F overlays suffer from a low performance, are vulnerable to denial-of-service attacks, or fail to provide anonymity. In particular, greedy embeddings allow highly efficient communication in arbitrary connectivity-restricted overlays but require communicating parties to reveal their identity. In this paper, we present a privacy-preserving routing scheme for greedy embeddings based on anonymous return addresses rather than identifying node coordinates. We show that the return addresses allow plausible deniability. Furthermore, we enhance the routing's resilience by using multiple embeddings and propose a method for efficient content addressing. Our extensive simulation study on real-world data indicates that our approach is highly efficient and effectively mitigates failures as well as powerful denial-of-service attacks.

In pull-based Peer-to-Peer video streaming systems, peers exchange buffer maps to reveal the availability of video chunks in their buffer. When collecting these buffer maps, a malicious party can infer the system's overlay structure and even identify head nodes, the direct communication partners of the stream's source. Attacking these head nodes can isolate peers from the source resulting in a disruption of the video dissemination for most peers in the system. We introduce a lightweight SWAP scheme, which allows peers to proactively change their partners, to reduce the chance of head nodes to be identified by such an inference attacker. Extensive simulation studies demonstrate that our scheme effectively undermines the attack's accuracy in identifying head nodes. So, SWAP lowers the chunk miss ratio while causing only a slight increase in signaling overhead.

The emerging trend of highly-resilient P2P botnets poses a huge security threat to our modern society. Carefully designed countermeasures as applied in sophisticated P2P botnets such as P2P Zeus impede botnet monitoring and successive takedown. These countermeasures reduce the accuracy of the monitored data, such that an exact reconstruction of the botnet's topology is hard to obtain efficiently. However, an accurate topology snapshot, revealing particularly the identities of all bots, is crucial to execute effective botnet takedown operations. With the goal of obtaining the required snapshot in an efficient manner, we provide a detailed description and analysis of the P2P Zeus neighbor list restriction mechanism. As our main contribution, we propose ZeusMilker, a mechanism for circumventing the existing anti-monitoring countermeasures of P2P Zeus. In contrast to existing approaches, our mechanism deterministically reveals the complete neighbor lists of bots and hence can efficiently provide a reliable topology snapshot of P2P Zeus. We evaluated ZeusMilker on a real-world dataset and found that it outperforms state-of-the-art techniques for botnet monitoring with regard to the number of queries needed to retrieve a bot's complete neighbor list. Furthermore, ZeusMilker is provably optimal in retrieving the complete neighbor list, requiring at most 2n queries for an n-elemental list. Moreover, we also evaluated how the performance of ZeusMilker is impacted by various protocol changes designed to undermine its provable performance bounds.

Virtual overlays generate topologies for greedy routing, like rings or hypercubes, on connectivity restricted networks. They have been proposed to achieve efficient content discovery in the Darknet mode of Freenet, for instance, which provides a private and secure communication platform for dissidents and whistle-blowers. Virtual overlays create tunnels between nodes with neighboring addresses in the topology. The routing performance hence is directly related to the length of the tunnels, which have to be set up and maintained at the cost of communication overhead in the absence of an underlying routing protocol. In this paper, we show the impossibility to efficiently maintain sufficiently short tunnels. Specifically, we prove that in a dynamic network either the maintenance or the routing eventually exceeds polylog cost in the number of participants. Our simulations additionally show that the length of the tunnels increases fast if standard maintenance protocols are applied. Thus, we show that virtual overlays can only offer efficient routing at the price of high maintenance costs.

Hybrid Peer-to-Peer streaming systems combine the advantages of an efficient push-based with a more resilient pull-based system to deliver video streams over the Internet. In this manner, hybrid systems offer low latency and an increased robustness to failures and node churn. However, current hybrid systems is vulnerable to misbehaving nodes and deliberate attacks. By taking central positions in the overlay, malicious nodes can perform extremely harmful Denial-of-Service (DoS) attacks. We propose RBCS, a novel backbone construction scheme, that is highly resilient against DoS attacks while maintaining fast content dissemination. RBCS incorporates stable peers into a manipulation-resistant multi-tree backbone overlay, which is resilient against both attacks and node churn. Additionally, RBCS securely identifies stable peers by using only local knowledge about the participation time of others. Extensive simulations indicate that RBCS outperforms the state-of-the-art in being more resilient against attacks at the price of a slightly increased overhead.

The design of secure and usable access schemes to personal data represent a major challenge of online social networks (OSNs). State of the art requires prior interaction to grant access. Sharing with users who are not subscribed or previously have not been accepted as contacts in any case is only possible via public posts, which can easily be abused by automatic harvesting for user profiling, targeted spear-phishing, or spamming. Moreover, users are restricted to the access rules defined by the provider, which may be overly restrictive, cumbersome to define, or insufficiently fine-grained. We suggest a complementary approach that can be easily deployed in addition to existing access control schemes, does not require any interaction, and includes even public, unsubscribed users. It exploits the fact that different social circles of a user share different experiences and hence encrypts arbitrary posts. Assembling only well-established cryptographic primitives, we prove that the security of our scheme is determined by the entropy of the required knowledge. We consequently analyze the efficiency of an informed dictionary attack and assess the entropy to be on par with common passwords. A fully functional implementation is used for performance evaluations, and available for download on the Web.

The widely used distributed hash table (DHT) in KAD is commonly analyzed and optimized based on partial measurements and simulation results, which are limited in scope and subject to simplification. An accurate characterization, however, is vital for a thorough understanding and effective enhancement. Analyzing and comparing complete real graphs collected from a large-scale measurement campaign as well as synthetic graphs generated by a novel simulation model, we study their degree distributions as well as resilience in face of random departure and targeted attacks. Our results show that the online KAD graph, although scale-free, is highly robust not only to random departure, but also to targeted attacks, making it suitable for distributed applications requiring a high resilience. Resilience to random departure and shape of degree distribution are well modelled by the simulations. However, due to a greatly increased ratio of stale routing information, the complete graph in the real system is much more vulnerable to targeted attacks compared to estimations based on simulative results.

Discovery of nodes and content in large-scale distributed systems is generally based on Kademlia, today. Understanding Kademlia-type systems to improve their performance is essential for maintaining a high service quality for an increased number of participants, particularly when those systems are adopted by latency-sensitive applications. This paper contributes to the understanding of Kademlia by studying the impact of diversifying neighbours' identifiers within each routing table bucket on the lookup performance. We propose a new, yet backward-compatible, neighbour selection scheme that attempts to maximize the aforementioned diversity. The scheme does not cause additional overhead except negligible computations for comparing the diversity of identifiers. We present a theoretical model for the actual impact of the new scheme on the lookup's hop count and validate it against simulations of three exemplary Kademlia-type systems. We also measure the performance gain enabled by a partial deployment for the scheme in the real KAD system. The results confirm the superiority of the systems that incorporate our scheme.

Routing in Darknets, membership concealing overlays for pseudonymous communication, like for instance Freenet, is insufficiently analyzed, barely understood, and highly inefficient. These systems at higher performance are promising privacy preserving solutions for social applications. This paper contributes a realistic analytical model and a novel routing algorithm with provable polylog expected routing length. Using the model, we additionally prove that this can not be achieved by Freenet's routing. Simulations support that our proposed algorithm achieves a better performance than Freenet for realistic network sizes.