This paper is available on arxiv under CC BY-NC-SA 4.0 DEED license. Authors: (1) Shanshan Han & Qifan Zhang, UCI; (2) Wenxuan Wu, Texas A&M University; (3) Baturalp Buyukates, Yuhang Yao & Weizhao Jin, USC; (4) Salman Avestimehr, USC & FedML. Table of Links Abstract and Introduction Problem Setting The Proposed Two-Stages Anomaly Detection Verifiable Anomaly Detection using ZKP Evaluations Related Works Conclusion & References 2 PROBLEM SETTING In this section we present our threat model along with some preliminaries that we leverage in the proposed anomaly detection mechanism. 2.1 ADVERSARY MODEL We consider an FL system where some subset of the clients might be malicious, while most of the clients (i.e., more than 50%) are honest. The clients would like to collaboratively train a model, however, malicious clients may conduct attacks to achieve some adversarial goals, including: i) planting a backdoor to misclassify a specific set of samples while minimally impacting the overall performance of the global model, i.e., backdoor attacks (Bagdasaryan et al., 2020b; Wang et al., 2020); ii) altering the local models to prevent the global model from converging, i.e., Byzantine attacks (Chen et al., 2017; Fang et al., 2020); and iii) randomly submitting contrived models without actual training, i.e., free riders (Wang, 2022). Clients are aware that the FL server may take some defensive measures for their submissions to mitigate potential attacks, and they want to verify the integrity of these defensive measures, to ensure correct operation at the server. 2.2 PRELIMINARIES Krum (Blanchard et al., 2017) is a well-known distance-based anomaly detection method in distributed learning that accepts local models that deviate less from the majority based on their pairwise distances. Given that there are f byzantine clients (i.e., malicious clients) among L clients in the FL system, where the server receives L local models as w1, w2, . . . , wL in each training round, Krum selects one of these models, i.e., the one that is the most likely to be benign, as the global model. An optimization of Krum is m-Krum (Blanchard et al., 2017) that selects m local models, instead of one, with the m smallest scores, to compute an average model when aggregating local models. Algorithms for Krum and m-Krum is shown in Algorithm 1. Krum. The three sigma rule is an empirical rule stating that almost all of the population lies within three standard deviations of the mean in normal distributions. Specifically, in normal distributions N (µ, σ), the percentage of values within one, two, and three standard deviations of the mean are 68%, 95%, and 99.7%, respectively. This rule can be widely applied in real-world applications, since normal distributions are consistent with real-world data distributions (Lyon, 2014), and according to the central limit theorem (Rosenblatt, 1956), when aggregating independent random variables, even if the variables are generated by various distributions, the aggregation tends towards a normal distribution. Further, when the data are not normally distributed, we can transform the distribution to a normal distribution (Aoki, 1950; Osborne, 2010; Sakia, 1992; Weisberg, 2001). The three sigma rule has been used in anomaly detection (Han et al., 2019) since data outside two or three standard deviations of the mean take a very limited proportion; see Figure 2. Three Sigma Rule. Zero-Knowledge Proofs (ZKPs)(Goldwasser et al., 1989) is a proof system that allow a prover to convince a verifier that a function on prover’s secret input (witness) is correctly computed. ZKPs ensures three properties: correctness, soundness, and zero-knowledge. Correctness means that if the prover is honest, then the proof they produce should check out (integrity property). Soundness ensures that a cheating prover will not convince verifier with overwhelming probability. Zero-knowledge guarantees that prover’s winess will be not learned by the verifier (privacy). Due to these properties, ZKP has been widely used in machine learning and blockchain applications (Lee et al., 2020; Feng et al., 2021; Liu et al., 2021; Sasson et al., 2014). Zero-knowledge proofs.

Augmentastic || Augmented Reality

Zero-Knowledge-Proof-Based Anomaly Detection: Problem Setting

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

A Comprehensive Look at Solar Radiation Predictions through Bayesian Hierarchical Models

The Noonification: Anomaly Detection with Privileged Information—Part 1 (12/13/2023)

The Noonification: Craig Wright is Satoshi Nakamoto (12/24/2023)

3 Types of Anomalies in Anomaly Detection

A Zero-Knowledge Anomaly Detection Approach for Robust Federated Learning

A Comprehensive Look at Solar Radiation Predictions through Bayesian Hierarchical Models

The Noonification: Anomaly Detection with Privileged Information—Part 1 (12/13/2023)

The Noonification: Craig Wright is Satoshi Nakamoto (12/24/2023)

3 Types of Anomalies in Anomaly Detection

A Zero-Knowledge Anomaly Detection Approach for Robust Federated Learning

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps