Framework for accessing privacy accuracy trade-off in FL

3.0 Framework / Design:

As explicitly stated in the goals section we will not conduct any privacy attacks rather will build a defence mechanism against privacy attacks and its effect on the model accuracy. We have chosen ‘Differential Privacy (DP)’ as a defence mechanism against privacy attacks.

3.0.1 Why did we choose differential privacy (DP)?

• Some of the initial approaches used a variety of approaches like suppression, aggregation, and transformation to anonymize the data to remove identifying information from the data source. These cryptographic ciphers can obfuscate the original source, but a dedicated attacker would be able to infer or extrapolate more information.
• Others like removal of certain columns or attributes or aggregation of certain row attributes or mixing the row attributes from multiple rows so that no single row has its original values, but the overall distribution of values is unchanged. These do not guarantee privacy as release of any data has a potential for a re-identification attack or information gain.
• DP has shifted focus from ‘how to anonymize data’ to ‘How can we measure the loss of privacy when the data is released? ’ or ‘How much privacy loss am I willing to create in order to answer the question? ’ DP defines a limit or bounds on the amount of privacy loss one can have while releasing information. Compared to other methods, it focuses on the process rather than the results.

3.0.2 The basic of DP

DP incorporates random noise into the mix so that everything an adversary receives becomes noisy and imprecise and so it is much more difficult to breach privacy.

Let two datasets 𝐷1 and 𝐷2 with one row difference between them and 𝐷1 and 𝐷2 be called adjacent dataset (this is called example-level DP). One uses an algorithm (𝑀) to release the query which can be ensured satisfying the following definition:

𝑃[𝑀(𝐷1) ∈𝑆] ≤exp(𝜀) ×𝑃[𝑀(𝐷2) ∈𝑆]

The probability 𝑃 that an attacker can determine based on the response 𝑀(𝐷1) or 𝑀(𝐷2) from the expected database, 𝑆 , if they are interacting with the first or second database is limited by a small value exp(𝜀). The value exp(𝜀) represents the amount of information gained by a dedicated adversary investigating the algorithm in a worst-case scenario. The goal of 𝑀 is to keep the accuracy as high as possible but to still provide as much privacy as possible by setting an upper bound giving individual privacy using 𝜀.

3.0.3 Privacy Loss:

The attacker will try to guess whether the database is either 𝐷1 and 𝐷2 depends on the information gather from 𝑀(𝐷1)=𝑂 where 𝑂 is the actual response the attacker sees. We would like to quantify how much information an attacker can gain and want to keep it in a probabilistic range. From Bayes theorem, 𝑃(𝐷=𝐷1|𝑀(𝐷1)=𝑂) lies within a range which is a function of exp(𝜀).

By varying 𝜀 a best-case and worst-case scenario can be drawn which will shed light on how much more a certain attack with a given prior information can get from a query which uses DP. It is often recommended to choose a small 𝜀, close to 1 or even less than 1.

Implementing those boundaries can be done by adding calibrated noise adding to the query which will guarantee information leakage within the range.

3.0.4 Noise 𝜺 term

𝜖 can be drawn either from Laplace distribution or Gaussian distribution.

The difference between these two distributions is the peak of Laplace distribution is sharper than Gaussian meaning a greater number of samples around zero is more than Gaussian. But it is obvious that the variance of residual is minimized if Gaussian prior is assumed.

The previous DP equation has considered Laplace distribution. Gaussian distribution allows a relaxation of the probability bounds by adding a small delta to the original definition.

𝑃[𝑀(𝐷1) ∈𝑆] ≤exp(𝜀) ×𝑃[𝑀(𝐷2) ∈𝑆]+ 𝛿

Where 𝛿 = margin of error means that ,𝛿 allows an implementation to, essentially, release all information about a small number of rows with no noise added, it that fits within the delta.

A good choice of delta is somewhere between 1/n, n = number of rows and cryptographically small (2−30≈9 × 10−10). A smaller delta values adds more guarantees.

A Gaussian mechanism is ( 𝜀,𝛿) differentially private if it follows the criteria and 𝜀<1.

𝐹(𝑥)=𝑓(𝑥)+𝑁( 𝜎2) where 𝜎2= 2𝑠2 log( 1.25𝛿)𝜀2⁄

𝑁( 𝜎2) samples a Gaussian distribution centred at 0 with variance 𝜎2 and 𝑠 is sensitivity.

3.0.5 Other terminologies

• Sensitivity: Measures the maximum change in the query result based on the change in the underlying dataset.
• Privacy budget: With each new query, additional information about the sensitive data is released. To ensure a meaningful privacy guarantee, data curators can enforce a maximum privacy loss. The maximum privacy loss is called the privacy budget. If the number of queries exceeds the threshold, then the privacy guarantee becomes too weak the curator stops answering queries.
• Privacy accounting: Each query as a privacy expense which incurs an incremental privacy loss. The strategy of using budgets, expenses and losses is fittingly known as privacy accounting.

3.0.6 DP-SGD (Differentially Private Stochastic Gradient Descent)

• The difficulty in applying DP is determining what the sensitivity of a given training tensor is. Hence DP-SGD uses the gradient itself as a measurement of a single person’s contribution. This comes with the assumption that each person is seen only once.
• It mainly consists of two steps: gradient clipping and adding noise for DP.
• Gradient clipping: At each step of SGD, we compute the gradient for a loss function for a random subset of examples. Due to presence of unbounded gradient in SGD, one must clamp the amount that any one same can contribute to control the amount of privacy leakage from the unbounded gradients. One uses 𝐿2 norm for clipping purposes.
• Adding noise: Once the per-sample gradient is clipped and scaled, combine those gradients back to the batch update and add noise, appropriately scaled on the bounded gradients, to protect privacy.
• Privacy accounting: ‘accountant’ procedure that computes the privacy cost at each access to the training data and accumulates this cost as the training progress.
• Privacy Loss: DP-SGD gives better, tighter bound on privacy loss by tracking detailed information (higher moments) of the privacy loss. For MNIST dataset with epoch 1000 with Gaussian variance 𝜎=4,𝛿= 10−5 , one can has 𝜀≈1.26 using DP-SGD method compared to 𝜀≈9.34 using strong composition theorem.

3.0.7 DP in FL settings: DP-FedAvg:

Next question: How DP-SGD can be implemented in federated settings?

• User-level DP: When users can contribute multiple examples to the training dataset, an example-level DP (depends on a single training example) is not necessarily strong enough to ensure the users’ data is not memorized. User-level DP which requires that the output distribution of models does not change even if we add/remove all the training examples from any one user (or all the examples from any one device in our application). As FL summarizes all a user’s training data as a single model update, federated algorithms are well-suited to offering user-level DP guarantees.
• Amplification-via-sampling: Means amplifying the privacy guarantee by leveraging the randomness in the sampling training examples.
• Flow-chart of DP-FedAvg: o Using random-sized batches where one selects users independently with probability q, rather than always selecting a fixed number of users.
  • Enforcing clipping of per-user updates so that the total update has bounded 𝐿2 norm.
  • Using different estimators for the average update to control sensitivity.
  • Adding Gaussian noise 𝑁(0,𝜎2) to the final average update where 𝜎=𝑧.𝑆 where 𝑧 is a parameter and 𝑆 is the sensitivity of the query. Varying 𝑧 and 𝛿>0, the accountant gives an 𝜀 for which this mechanism satisfies ( 𝜀,𝛿) differentially private.
• Note: DP-FedAvg has been deployed in practice by Google in 2020 to mobile device and this algorithm has been implemented assuming a dataset with a sufficiently large number of users and claimed to be easily met by even small internet-scale dataset.

4.0 Experimental design

• The FL architecture design is strictly server-client based. No hierarchical structure has been considered.
• Baseline: We will distribute the chosen dataset (MNIST) into 5 to 7 different clients and there are no malicious clients or server directly conducting privacy attacks. We will get the overall accuracy of the model.
• Privacy implementing scenario 1:
  • Implement DP-FedAvg where the server is adding noise on the aggregated parameters to incorporate privacy and varying different parameters (𝑧,𝑆,𝛿) to estimate how much privacy (𝜀) we can guarantee. Also keeping track of privacy accounting in the overall training time and its relationship with accuracy. In each iteration, either we can get local parameter updates from all the clients or a selected few to see how privacy-accuracy trade-off.

• Privacy implementing scenario 2:
  • There are different ways to add noise for DP purposes. In the above-described method, noise has been added at the server side. Users should have flexibility to set up the training such that each client independently adds a small amount of noise to the clipped update.
  • To be precise, if we let 𝑚 be the number of clients sampled each round and 𝜎 be the scale of the total Gaussian noise that needs to be added to the sum of the model updates, we can use simple maths to show that this is equivalent to each client adding noise with scale 𝜎/√𝑚.
  • We will get clients flexibility to add noise and access the privacy/accuracy trade-off in that architecture.
• Security–privacy-accuracy scenario 3:
  • During security defence mitigation, we have considered other aggregation methods apart from FedAvg, such as FedMedian and FedTrimmedAvg and some of them with proper hyperparameter settings perform better than FedAvg.
  • We can let the clients add noises in their local updates and see how the other aggregation methods behave in order of privacy-accuracy tradeoff scenario either in presence of security attacks or not.