Helmholtz Center for Information Security
CISPA – Helmholtz-Zentrum für InformationssicherheitNot a member yet
3406 research outputs found
Sort by
Graph Unlearning
Get PDFThe right to be forgotten states that a data subject has the right to erase their data from an entity storing it. In the context of machine learning (ML), it requires the ML model provider to remove the data subject's data from the training set used to build the ML model, a process known as machine unlearning. While straightforward and legitimate, retraining the ML model from scratch upon receiving unlearning requests incurs a high computational overhead when the training set is large. To address this issue, a number of approximate algorithms have been proposed in the domain of image and text data, among which SISA (Sharded, Isolated, Sliced, and Aggregated) is the state-of-the-art solution. It randomly partitions the training set into multiple shards and trains a constituent model for each shard. However, directly applying SISA to the graph data can severely damage the graph structural information, and thereby the resulting ML model utility.
In this paper, we propose GraphEraser, a novel machine unlearning framework tailored to graph data. Its contributions include two novel graph partition algorithms and a learning-based aggregation method. We conduct extensive experiments on five real-world graph datasets to illustrate the unlearning efficiency and model utility of GraphEraser. We observe that GraphEraser achieves 2.06 (small dataset) to 35.94 (large dataset) unlearning time improvement compared to retraining from scratch. On the other hand, GraphEraser achieves up to higher F1 score than that of random partitioning. In addition, our proposed learning-based aggregation method achieves up to higher F1 score than that of the majority vote aggregation
On Xing Tian and the Perseverance of Anti-China Sentiment Online
Get PDFSinophobia, anti-Chinese sentiment, has existed on the Web for a long time. The outbreak of COVID-19 and the extended quarantine has further amplified it. However, we lack a quantitative understanding of the cause of Sinophobia as well as how it evolves over time. In this paper, we conduct a largescale longitudinal measurement of Sinophobia, between 2016 and 2021, on two mainstream and fringe Web communities. By analyzing 8B posts from Reddit and 206M posts from 4chan’s /pol/, we investigate the origins, evolution, and content of Sinophobia. We find that, anti-Chinese content may be evoked by political events not directly related to China, e.g., the U.S. withdrawal from the Paris Agreement. And during the COVID-19 pandemic, daily usage of Sinophobic slurs has significantly increased even with the hate-speech ban policy. We also show that the semantic meaning of the words “China” and “Chinese” are shifting towards Sinophobic slurs with the rise of COVID-19 and remain the same in the pandemic period. We further use topic modeling to show the topics of Sinophobic discussion are pretty diverse and broad. We find that both Web communities share some common
Sinophobic topics like ethnics, economics and commerce, weapons and military, foreign relations, etc. However, compared to 4chan’s /pol/, more daily life-related topics including food, game, and stock are found in Reddit. Our finding also reveals that the topics related to COVID-19 and blaming the Chinese government are more prevalent in the pandemic period. To the best of our knowledge, this paper is the longest quantitative measurement of Sinophobia
Distributed edge coloring in time polylogarithmic in Δ
Get PDFWe provide new deterministic algorithms for the edge coloring problem, which is one of the classic and highly studied distributed local symmetry breaking problems. As our main result, we show that a (2Δ-1)-edge coloring can be computed in time poly(log Δ) + O(log* n) in the LOCAL model. This improves a result of Balliu, Kuhn, and Olivetti [PODC '20], who gave an algorithm with a quasi-polylogarithmic dependency on Δ. We further show that in the CONGEST model, an (8+epsilon)Δ-edge coloring can be computed in poly(log Δ) + O(log* n) rounds. The best previous O(Δ)-edge coloring algorithm that can be implemented in the CONGEST model is by Barenboim and Elkin [PODC '11] and it allows to compute a 2^{O(1/epsilon)}Δ-edge coloring in time O(Δ^epsilon + log* n) for any epsilon in (0,1]
Efficiently Factorizing Boolean Matrices using Proximal Gradient Descent
Get PDFAddressing the interpretability problem of NMF on Boolean data, Boolean Matrix Factorization (BMF) uses Boolean algebra to decompose the input into low-rank Boolean factor matrices. These matrices are highly interpretable and very useful in practice, but they come at the high computational cost of solving an NP-hard combinatorial optimization problem. To reduce the computational burden, we propose to relax BMF continuously using a novel elastic-binary regularizer, from which we derive a proximal gradient algorithm. Through an extensive set of experiments, we demonstrate that our method works well in practice: On synthetic data, we show that it converges quickly, recovers the ground truth precisely, and estimates the simulated rank exactly. On real-world data, we improve upon the state of the art in recall, loss, and runtime, and a case study from the medical domain confirms that our results are easily interpretable and semantically meaningful
Where to Recruit for Security Development Studies: Comparing Six Software Developer Samples
Get PDFStudying developers is an important aspect of usable security and privacy research. In particular, studying security development challenges such as the usability of security APIs, the secure use of information sources during development or the effectiveness of IDE security plugins raised interest in recent years. However, recruiting skilled participants with software development experience is particularly challenging, and it is often not clear what security researchers can expect from certain participant samples, which can make research results hard to compare and interpret. Hence, in this work, we study for the first time opportunities and challenges of different platforms to recruit participants with software development experience for security development studies. First, we identify popular recruitment platforms in 59 papers. Then, we conduct a comparative online study with 706 participants based on self-reported software development experience across six recruitment platforms. Using an online questionnaire, we investigate participants’ programming and security experiences, skills and knowledge. We find that participants across all samples report rich general software development and security experience, skills, and knowledge. Based on our results, we recommend developer recruitment from Upwork for practical coding studies and Amazon MTurk along with a pre-screening survey to reduce additional noise for larger studies. Both of these, along with Freelancer, are also recommended for security studies. We conclude the paper by discussing the impact of our results on future security development studies
How Not to Handle Keys: Timing Attacks on FIDO Authenticator Privacy
Get PDFThis paper presents a timing attack on the FIDO2 (Fast IDentity Online) authentication protocol that allows attackers to link user accounts stored in vulnerable authenticators, a serious privacy concern. FIDO2 is a new standard specified by the FIDO industry alliance for secure token online authentication. It complements the W3C WebAuthn specification by providing means to use a USB token or other authenticator as a second factor during the authentication process. From a cryptographic perspective, the protocol is a simple challenge-response where the elliptic curve digital signature algorithm is used to sign challenges. To protect the privacy of the user the token uses unique key pairs per service. To accommodate for small memory, tokens use various techniques that make use of a special parameter called a key handle sent by the service to the token. One of the most popular techniques used by leading token manufacturers (e.g. Yubico), termed key wrapping, stores the encrypted secret key in the server’s database and provides it to the token via the key handle parameter. We identify and analyse a vulnerability in the way the processing of key handles is implemented that allows attackers to remotely link user accounts on multiple services. We show that for vulnerable authenticators there is a difference between the time it takes to process a key handle for a different service but correct authenticator, and for a different authenticator but correct service. This difference can be used to perform a timing attack allowing an adversary to link the same authenticator across different services. Two of the eight hardware authenticators we tested were vulnerable despite FIDO level 1 certification, indicating a not insignificant problem. This vulnerability cannot be easily mitigated on authenticators because, for security reasons, they usually do not allow firmware updates. In addition, we show that due to the way existing browsers implement the WebAuthn standard, the attack can be executed remotely. However, we discuss countermeasures that can be implemented by browser providers to mitigate the remote form of the attac
Efficient Adaptively-Secure Byzantine Agreement for Long Messages
Get PDFWe investigate the communication complexity of Byzantine agreement
protocols for long messages against an adaptive adversary. In this setting, prior -party protocols
either achieved a communication complexity of
O(nl\cdot\poly(\kappa)) or O(nl +
n^2 \cdot \poly(\kappa)) for -bit long messages and security parameter . We improve the
state of the art by presenting protocols with communication complexity
O(nl + n \cdot \poly(\kappa)) in both the synchronous and
asynchronous communication models. The synchronous protocol tolerates
corruptions and assumes a VRF setup,
while the asynchronous protocol tolerates corruptions under further cryptographic assumptions. Our
protocols are very simple and combine subcommittee election with the
recent approach of Nayak et al. (DISC `20). Surprisingly, the analysis
of our protocols is \emph{all but simple} and involves an interesting
new application of Mc Diarmid's inequality to obtain {\em almost optimal} corruption thresholds
State Machine Replication under Changing Network Conditions
Get PDFProtocols for state machine replication (SMR) are typically designed for synchronous or asynchronous networks, with a lower corrup- tion threshold in the latter case. Recent network-agnostic protocols are secure when run in either a synchronous or an asynchronous network. We propose two new constructions of network-agnostic SMR protocols that improve on existing protocols in terms of either the adversarial model or communication complexity:
1. an adaptively secure protocol with optimal corruption thresholds and quadratic amortized communication complexity per transaction;
2. a statically secure protocol with near-optimal corruption thresholds
and linear amortized communication complexity per transaction.
We further explore SMR protocols run in a network that may change between synchronous and asynchronous arbitrarily often; parties can be uncorrupted (as in the proactive model), and the protocol should remain secure as long as the appropriate corruption thresholds are maintained. We show that purely asynchronous proactive secret sharing is impossible without some form of synchronization between the parties, ruling out a natural approach to proactively secure network-agnostic SMR protocols. Motivated by this negative result, we consider a model where the ad- versary is limited in the total number of parties it can corrupt over the duration of the protocol and show, in this setting, that our SMR proto- cols remain secure even under arbitrarily changing network conditions
Specification decomposition for reactive synthesis
No full textReactive synthesis is the task of automatically deriving a correct implementation from a specification. It is a promising technique for the development of verified programs and hardware. Despite recent ad- advances in terms of algorithms and tools, however, re-active synthesis is still not practical when the specified systems reach a certain bound in size and complexity. In this paper, we present a sound and complete modular synthesis algorithm that automatically decomposes the specification into smaller subspecifications. For them, independent synthesis tasks are performed, significantly reducing the complexity of the individual tasks. Our decomposition algorithm guarantees that the subspecifications are independent in the sense that completely separate synthesis tasks can be performed for them. Moreover, the composition of the resulting implementations is guaranteed to satisfy the original specification. Our algorithm is a preprocessing technique that can be applied to a wide range of synthesis tools. We evaluate our approach with state-of-the-art synthesis tools on established benchmarks: the runtime decreases significantly when synthesizing implementations modularly