R-GAP: Recursive Gradient Attack on Privacy
Authors: Junyi Zhu
Matthew B. Blaschko
Venue: ICLR 2021 Poster (2021)
Keywords: privacy leakage from gradients
federated learning
collaborative learning

Abstract: Federated learning frameworks have been regarded as a promising approach to break the dilemma between demands on privacy and the promise of learning from large collections of distributed data. Many such frameworks only ask collaborators to share their local update of a common model, i.e. gradients with respect to locally stored data, instead of exposing their raw data to other collaborators. However, recent optimization-based gradient attacks show that raw data can often be accurately recovered from gradients. It has been shown that minimizing the Euclidean distance between true gradients and those calculated from estimated data is often effective in fully recovering private data. However, there is a fundamental lack of theoretical understanding of how and when gradients can lead to unique recovery of original data. Our research fills this gap by providing a closed-form recursive procedure to recover data from gradients in deep neural networks. We name it Recursive Gradient Attack on Privacy (R-GAP). Experimental results demonstrate that R-GAP  works as well as or even better than optimization-based approaches at a fraction of the computation under certain conditions. Additionally, we propose a Rank Analysis method, which can be used to estimate the risk of gradient attacks inherent in certain network architectures, regardless of whether an optimization-based or closed-form-recursive attack is used. Experimental results demonstrate the utility of the rank analysis towards improving the network's security. Source code is available for download from https://github.com/JunyiZhu-AI/R-GAP.

Published as a conference paper at ICLR 2021
R-GAP: RECURSIVE GRADIENT ATTACK ON PRIVACY
Junyi Zhu and Matthew Blaschko
Dept. ESAT, Center for Processing Speech and Images
KU Leuven, Belgium
Hunyi.zhip matthew www.tthwwwwwsscceh..eeeeo @esat kuleuven be
ABSTRACT
Federated learning frameworks have been regarded as promising approach to break the dilemma between demands on privaey and the promise of learning from large collections of distributed data. Many such frameworks only ask collaborators to share their local update their raw data to other collaborators. However, recent optimization-aan based gradi- ent attacks show that raw data can often be accurately recovered from gradients. It has been shown that minimizing the Euclidean distance between gradients and those calculated from estimated data often effective in fully recovering private data. However, there is fundamental lack of theoretical understanding of how and when gradients can lead to unique recovery of original data. Our research fills this gap by providing a closed-form recursive procedure to recover data from gra- dients in deep neural networks. We name it Recursive Gradient Attack on Privacy (R-GAP). Experimental results demonstrate that R-GAP works as well as or even better than optimization-bn baaed approaches at fraction of the computation under certain conditions. Additionally, we propose Rank Analysis method, which can be used to estimate the risk of gradient attacks inherent in certain network ar- chitectures, regardless of whether an optimization-bu attack is used. Experimental results demonstrate the utility of the rank analysis towards improving the network's s security. Source code is available for download from hwttt:ttttstttiitt com/ Juny
common model, i.e. gradients, instead of exposing
or rerurrrsve
INTRODUCTION
Distributed and federated learning have become common strategies for training neural networks without transferring data (Jochems et al. 2016 2017 Konečný et al.) 2016 McMahan et al. (017). Instead, model updates, often the form of gradients, are exchanged between participating nodes. These are then used update each node copy of the model. This has been widely applied for privacy purposes (Rigaki & Garcia 2020 Cristofaro 2020). including with medical data (Jochems) al. 2016 2017). Recently, it has been demonstrated that this family of approaches is susceptible to attacks that can in some circumstances recover the training data from the gradient information exchanged in such federated learning approaches, calling into question their suitability for privacy preserving distributed machine learning (Phong et al.) (0018) Wang et al. 2019: Zhu et al. 2019
Zhao al. 2020; Geiping al. 2020 Wei al. 2020). To date these attack strategies have
broadly fallen into two groups: (i) an analytical attack based on the use of gradients with respect to
bias term (Phong et al., 2018). and (ii) an optimization- based attack (Zhu al. 2019) that can in some circumstances recover individual training samples in batch, but that involves a difficult non- convex optimization that doesn't 't always converge a correct solution (Geiping et al., (020), and that provides comparatively little insights into the information that is being exploited in the attack.
The development of privacy attacks is most important because they inform strategies for protecting against them. This is achieved by perturbations to the transferred gradients, and the form of the attack can give insights into the type of perturbation that can effectively protect the data (Fan et al. 2020). As such, the development of novel closed-form attacks is essential the analysis of privacy in federated learning. More broadly, the existence of model inversion attacks (He et al. 2019
Wang et al. 2019 Yang et al., 2019 Zhang et al. 2020) calls into question whether transferring

---

Published as a conference paper at ICLR 2021
fully trained model can be considered privacy preserving. As the weights of model trained by (stochastic) gradient descent are the summation of individual gradients, understanding gradient attacks can assist in the analysis of and protection against model inversion attacks in and outside of a federated learning setting.
In this work, we develop a novel third family of attacks, recursive gradient attack on privacy (R- GAP), that is based on a recursive, depth-wise algorithm for recovering training data from gradient information. Different from the analytical attack using the bias term, R-GAP utilizes much more information and is the first closed-form algorithm that works on both convolutional networks and fully connected networks with or without bias term. Compared optimization -base attacks, is not susceptible to local optima, and is orders of magnitude faster to run with a deterministic running time. Furthermore, we show that under certain conditions our recursive attack can fully recover training data in cases where optimization attacks fail. Additionally, the insights gained from the closed form of our recursive attack have lead to a refined rank analysis that predicts which network architectures enable full recovery, and which lead to provable noisy recovery due to rank- deficiency. This explains well the performance of both closed-form and optimization-bant We also demonstrate that using rank analysis are able to make small modifications to network architectures to increase the network's 's security without sacrificing its accuracy.
attacks.
1.1 RELATED WORK
The original discovery of the existence of an analytical attack based on gradients with respect to the bias term is due to |Phong et al. (2018). Fan et al. (2020) also analyzed the bias attack as system of linear equations, and proposed method of perturbing the gradients to protect against it. Their work considers convolutional and fully-connected networks as equivalent, but this ignores the aggregation of gradients in convolutional networks. Similar our work, they also perform rank analysis, but it considers fewer constraints than is included in our analysis (Section 4
Bias attacks:
Optimization attacks: The first attack that utilized an optimization approach minimize the dis- lance between gradients appears to be due to Wang et al. (2019). In this work, optimization is adopted as a submodule in their GAN-style framework. Subsequently, Zhu et al. (2019) proposed a method called deep leakage from gradients (DLG) which relies entirely on minimization of the difference of gradients (Section 2). They propose the use of L-BFGS (Liu & Nocedal 1989) to perform the optimization. /Zhao et al. (2020) further analyzed label inference in this setting, propos- ing an analytic way to reconstruct the one-hot label of multi-class classification in terms of a single input. WWi et al. (020) show that DLG is sensitive to initialization and proposed that the same class image is an optimal initialization. They proposed to use SSIM as image similarity metric, which can then be used to guide optimization by DLG. Geiping et al. (2020) point out that DLG requires second-order derivatives, L-BFGS actually requires third-order derivatives, which leads to challenging optimzation for networks with activation functions such as ReLU and LeakyReLU. They therefore propose to replace L-BFGS with Adam (Kingma & Ba 2015). Similar to the work of Wei et al. (2020). Geiping et al. (2020) propose incorporate an image prior, in this case total variation, while using PSNR as a quality measurement.
2 SIMMIIZATION-BASER GRADIENT ATTACKS ON PRIVACY (O-GAP)
Optimization-basae gradient attacks on privacy (O-GAP) take the real gradients as its ground-truth label and utilizes optimization to decrease the distance between the real gradients VW and the dummy gradients VW' generated by a pair of randomly initialized dummy data and dummy label. The objective function of O-GAP can be generally expressed as:
arg min o'
VWW - 1 arg min
Σ
VWW - -
(1)
where the summation is taken over the layers of a network of depth d, and (x', is the dummy training data and label used to generate VW'. The idea of O-GAP was proposed by Wang et al. 2019). h However, they have adopted it as a part of their GAN-style framework and did not realize that O-GAP is able preform a more accurate attack by itself. Later in the work of Zhu et al. (2019) O-GAP has been proposed as a stand alone approach, the framework has been named as Deep Leakage from Gradients (DLG).
2

---

Published as a conference paper at ICLR 2021
The approach is intuitively simple, and in practice has been shown to give surprisingly good sults (Zhu et al. 2019). However, it is sensitive to initialization and prone to fail (Zhao et al.) 2020). The choice of optimizer is therefore important, and convergence
be very slow (Geip- ing et al. 2020). Perhaps most importantly, Equation T gives little insight into what information in the gradients is being exploited recover the data. Analysis in Zhu al. (20T9) is limited to empirical insights, and fundamental open questions remain: What are sufficient conditions for arg milly', Σi ==1 I/W, l to huve unique minimizer? We address this question in Sec-
tion 4 and subsequently validate our findings empirically.
CLOSED-FORM GRADIENT ATTACKS ON PRIVACY
The first attempt closed-form GAP was proposed in research privacy- deep learning by Phong et al. (2018).
Theorem 1 (Phong et al. (2018). Assume a layer of a fully connected network with bias term, expressed as:
Wx bx+b=z.
where W. b denote the weight matrix and bias vector, and x. denote the input vector and output vector of this layer. If the loss function of the network can be expressed as:
8 e (=(((xx),))
where f indicates nested function of x including activation function and all subsequent layers, the ground-truth label. Then a can derived from gradients w.r.t. and gradients w.r.t. i.e.:
08
de
08
aW
Oz
5b
Oz.
ae
al
(3)
aw;
ab,
where j denotes the j-th row, note that in fact from each row we can compute copy of x
When this layer is the first layer of a network, possible to reconstruct the data, i.e. x, using this make of the redundancy in estimating by approach. In the case of noisy gradients, ae öf However, simply removing the bias term averaging noisy estimates: x E₁ aw, Aby disable this attack. Besides, this approach does not work on convolutional neural networks due to dimension mismatch in Equation 3 Both of these two problems have been resolved in our approach.
3.1 RECURSIVE GRADIENT ATTACK ON PRIVACY (R-GAP)
For simplicity we derive the R-GAP in terms of binary classification with a single image as input. In this setting generally describe the network and loss function
- ff (x)
# -Wddd-
W 12-2 (Wa-20 (x))
(4)
=ifa-2(X)
lo + +
(5)
where y E (-1, denotes the d-th layer, & represents all layers previous to d 2, and a denotes the activation function. Note that, although our notation omits the bias term in our approach, with an augmented matrix and augmented vector it is able to represent both of the linear map and the translation, e.g. Equation using matrix multiplication as shown in Equation 4 So our formulation also includes the approach proposed by Phong et al. (2018). Moreover, if the i-th layer is a convo- lutional layer, then W; is an extended circulant matrix representing the convolutional kernel (Golub & Van Loan 1996). and data x as well as input of each layer are represented by a flattened vector in Equation
3

---

Published as a conference paper at ICLR 2021
/
Ab
1
11
1
7
&: Lugistic loss
E: Exponential loss
&: Hinge loss
0P Figure 1: In consideration of logistic loss, exponential loss and hinge loss, 8p /a is not monotonic w.r.t. μ.. is equal to 0 at μ 0, after that either approximates 07, or equals after decreasing to = 1.
3.1.1 RECOVERING DATA FROM GRADIENTS
From Equation and Equation
5 we can derive following gradients:
di
d
y 0p
fo
(6)
Owd
Oe
de
wd
!J 3p
d'-1
fa_2
eW d-1
OE
Oe
WT
oWa22 4-2
0p
where of denotes the derivative of a, for more details of deriving the gradients refer to Appendix The first observation of these gradients that:
Oe
Ol
Ow Wa 0p" 1
Additionally, if 01, ... Id-1 are ReLU or LeakyRelu, the dot product of the gradients and weights of each layer will be the same, i.e.
de
OE OW.-1
0f Wa-1 = ow, 3p
al
Wa
W
(10)
Ow Since gradients and weights of each layer are known, we can obtain loss (Equation 5). we obtain:
By u. loss function / logistic
a8 3n 1 ea
(11)
In order to perform R-GAP, we need to derive from oj As we can see, oμ i is non-monotonic,
which means knowing 0y y does not always allow to uniquely recover μ.. However, even in the case that we cannot uniquely recover μ4, there are only two possible values consider. Figure [ illustrates ot By of logistic, exponential, and hinge losses, showing when we can uniquely recover from 08
By μ. The non-uniqueness of μ inspires us to find sort of data that can trigger exactly the same gradients as the real data, which we name twin data, denoted by &. The existence of twin data demonstrates that the objective function of DLG could have more than one global minimum, which explains at least in part why DLG is sensitive to initialization, for more information and experiments about the twin data refer to Appendix
The second observation on Equations 6 is that the gradients of each layer have repeated format:
Of
Of
Ow, kafT kg
(12)
Op
at
k4-1fd-2; k4-1 = (w. ku) C 0
(13)
OWa-1
at
T; ka-2:= ::::=WWTT (WT_kk-l 0''022
(14)
OW 4-2
4

---

Published as a conference paper at ICLR 2021
In Equation| 12 the value of can be derived from the sign of the gradients at this layer if the acti- vation function of previous layer is ReLU or Sigmoid, i... fa-1 > 0. For multi-class classification, y can always be analytically derived as proved by Zhao al. (2020). From Equations [2 we can see that gradients are actually linear constraints on the output of the previous layer, also the input of the current layer. We name these gradient constraints, which can be generally described as:
al
K, = flatten(
(15)
ow:
where i denotes i-th layer, x; denotes the input and K; is coefficient matrix containing all gradient constraints at the i-th layer.
3.1.2 IMPLEMENTATION OF R-GAP
To reconstruct the input x; from the gradients at sw; at the i-th layer, we need to determine K; or k;- The coefficient vector k; solely relies on the reconstruction of the subsequent layer. For example in Equation 13 ky-1 consists of wa, ka. 02-1 where Wa is known, and k2 and 0'21 are products of the reconstruction at the d-th layer. More specifically, KJ can be calculated by deriving y and as described in Section 3.1.1 d'-1 can be derived from the reconstructed fa-1. The condition for recovering x; under gradient constraints k; is that the rank of the coefficient matrix equals the number of entries of the input, rank(K,) [x:]- Furthermore, if this rank condition holds for i = I,.... d, we are able to reconstruct the input at each layer and do this recursively back to the input of the first layer.
The number of gradient constraints is the same as the number of weights, i.c. rows W
1....d. d. Specifically, in the case of fully connected layer we always have rank(K.) = |x,|, which implies the reconstruction over FCNs is always feasible. However in the case of a convolutional layer the matrix could possibly be rank-deficient derive Fortunately, from the view of recursive reconstruction and assuming we know the input of the subsequent layer, i.e. the output of the current layer, there new group of linear constraints which we name weight constraints:
WiX: Zy:
2 + f:
(16)
For convolution layer, the W; we use in this paper the corresponding eirculant matrix represent- ing the convolutional kernel (Golub & Van Loan| 1996). so we can express the convolution in the form of Equation [6] In order to derive z; from ft. the activation function a, should be monotonic. Commonly used activation functions satisfy this requirement. Note that for the ReLU activation function, a value in fi will remove a constraint in W, Otherwise, the number of weights con- straints is equal to the number of entries in output, i.e. (o.s(W.) |z,]; i .... d. In CNNs the number of weight constraints z is much larger than the number of gradient constraints W.| in bottom layers, and well compensate for the lack of gradient constraints in those layers. It is worth noting that, due to the transformation from a CNN to FCN using the circulant matrix, a CNN has been regarded equivalent a FCN in the parallel work of et al. (2020). However, we would like to point out that in consideration of the gradients w.r.t. the circulant matrix, what we obtain from a CNN are the aggregated gradients. Therefore, the number of valid gradient constraints in a CNN are much smaller than its corresponding FCN. Therefore, the conclusion of rank analysis derived from a FCN cannot be directly applied to a CNN.
Moreover, padding in the i-th convolutional layer increases |x:], but also involves the same number of constraints, so we omit this detail in the subsequent discussion. However, we have incorporated the corresponding constraints in our approach. Based on gradient constraints and weight constraints, we break the gradient attacks down to a recursive process of solving systems of linear equations, which we name R-GAP. The approach is detailed in Algorithm
4 RANK ANALYSIS
For optimization-base gradient attacks such as DLG, it is hard to estimate whether it will converge to a unique solution given a network's 'ss architecture other than performing an empirical test. An intuitive assumption would be that the more parameters in the model, the greater the chance of unique recovery, since there will be more terms in the objective function constraining the solution. We provide here an analytic approach, with which it is easy to estimate the feasibility of performing
5

---

Published as a conference paper at ICLR 2021
Algorithm 1: R-GAP (Notation is consistent with Equation 6 to Equation 15
Data: i: i-th layer: Wi: weights; VW;; gradients:
Result:
for 6 do /oo
it = d then
8p VW; WN
de
" - By ui k; = Vi : E:
else
Derive of and 2 from St. Note that x Si.
o. t Ki+1i Z f- X
k, = (W k(+1) 0
end
K,
kj Vw, = flatten VW.):
W
A =
b. = Vw.
K;
b; // a! MMoore-Penoose pseudoinverse
X;
end
the recursive gradient attack, which in turn is good proxy to estimate when DLG converges good solution (see Figure
Since R-GAP solves a sequence of linear equations, it is infeasible when the number of unknown
parameters is more than the number of constraints at any i-th layer, i.c. xx| W - |z: > 0. More precisely, R-GAP requires that the rank of A; which consists of W; and K; as shown in Algorithm I is equal to the number of input entries xx,l- However, A,X; constraints over X₃. Because x, is unique to Z or partly unique in terms of the ReLU activation function, any constraint over - will limit the possible value of x, On that note, suppose |x:-1 m, | n and the weight constraints the 7-11; m < rank(W;; (W,1)
does not include all effective
layer overdetermined, i.e. W = Without the loss of generality, let the first m entries of 7;-1 be linearly independent, the m + 1, ..., n entries of 2 can be expressed as linear combination the first m entries, i.e. Mz, 1.... m 2, m+1..... In other words, if the previous layers are overdetermined by weight constraints, the subsequent layer will have additional constraints, not merely its local weight constraints and gradient constraints. Since this type of additional constraint is not derived from the parameters of the layer that under reconstruction, we name them virtual constraints denoted by V. When the activation function the identity function, the virtual constraints are linear and can be readily derived. For the derivative of the activation function not being constant, the virtual constraints will become non-linear. For more details about deriving the virtual constraints, refer to Appendix C Optimization based attacks such as DLG are iterative algorithms based on gradient descent, and are able to implicitly utilize the non-linear virtual constraints. Therefore to provide a comprehensive estimate of the data vulnerability under gradient attacks, we also have to count the number of virtual constraints. It is worth noticing that virtual constraints can be passed along through the linear equation systems chain, but only in one direction that is to the subsequent layers. Next, we will informally use [V]] to denote the number of virtual constraints at the i-th layer, which can be approximated by Σi=1 marr(z, xx, i 0) max |x,] - |z,,| W 0). For more details refer to Appendix C In practice, the real number of such constraints is dependent on the data, current weights, and choice of activation function.
M
These three types of constraints, gradient, weight and virtual constraints, are effective for predicting the risk of gradient attack. To conclude, we propose that |x,| - WW, |z,| 1V a good index to estimate the feasibility of fully recovering the input using gradient attacks at the i-th layer. We denote this value rank analysis index (RA-i). Particularly, |x W, - |z, |. > 0 indicates it is not possible to perform a complete reconstruction of the input, and the larger this index is, the poorer the quality of reconstruction will be. If the constraints in a particular problem are linearly independent, |x| W.. |z [ O implies the ability to fully recover the input. The quality of reconstruction of data is well estimated by the maximal RA-i of all layers, as shown in Figure In practice, the layers close the data usually have smaller RA-i due to fewer virtual constraints.

---

Published as a conference paper at ICLR 2021
Image
Image
Image
Image
Image
Architecture
conv1 4x4@
conv1 4x4@03
conv1 4x4
conv1 3x3
conv1 5x5
3364x1 fc
2523x1 fc
2523x500 ic
conv2 3x3@4
conv2 4x4@2
500x1
3136x1 fc
2500x1
[ 3556
[W] 2667
W| = 1.26x10
[W] 3388
[W] 3056
conv1:
convi:
conv1:
conv1:
conv1: Kg| 1W11-12,11 12,1 <
Rank Analysis
Kg|- [W] 1
KJ]
[W.I 1z
XJ| [W]1 1
| -IWIWWI--- 12
conv2:
conv2:
|_]| -W.J
-
P/1- [W] IM
DLG Reconstruction
Figure 2: Estimating the privacy leakage of network through rank analysis. The critical layer for reconstruction has been red colored. First three columns show that even though bigger network has much more parameters denoted by [W), which means the data, but if the layer close to data is rank-deficient, we are nor able to fully recover the data. Despite that in the objective function of DL.G, distance between all gradients will be reduced the same time, redundant constraints in subsequent layer certainly cannot compensate the lack of constraints previous layer. The fourth column shows that if rank-deficiency happens the in- termediate layer, redundant weight constraints in previous layer, i.e. virtual constraints, is able to compensate the deficiency at the intermediate layer. a layer is rank-deficient after taking virtual constraints into account, fully recovery is again not possible shown in the fifth column. However, as the rank analysis index of last column smaller than the one the second and third column, reconstruction at the fifth column has a better quality. This figure demonstrates that rank analysis can correctly estimate the feasibility of performing DLG, for statistic result refer to Appendix A
collect more gradients to reconstruct
On top of that analyse the residual block in ResNet, which shows some interesting traits of the skip connection in terms of the rank-deficiency, for more details refer to Appendix D
valuable observation we obtain through the rank analysis is that the architecture rather than the number of parameters is critical to gradient attacks, as shown in Figure 2 This observation is obvious from simply specifying the DLG optimization problem(see Equation [[]. Furthermore, since the data vulnerability of network depends on the layer with maximal RA-1, we can design rank-defyciyncy into the architecture to improve the security of network (see Figure
RESULTS
Our novel approach R-GAP successfully extends the analytic gradient attack (Phong et al.) 2018) from attacking a FCN with bias terms to attacking FCNs and CNN With or without bias terms. To test its performance, we use CNN6 network as shown in Figure 3 which is full-rank considering gradient constraints and weight constraints. Additionally, we report results using a CNN6-d network, which is rank-deficient without consideration of virtual constraints, in order to fairly compare the performance of DLG and R-GAP. CNN6-d has a CNN6 backbone and just decreases the output channel of the second convolutional layer 20. The activation function LeakyReLU except the last layer, which is Sigmoid. We have randomly initialized the network, as DLG is prone to fail if the network is at late stage of training (Geiping al.) 2020). Furthermore, can be analytically recovered by R-GAP, we always provide DLG the ground-truth label and let recover the image only. Therefore the experiment actually compares R-GAP with iDLG (Zhao al, 2020). The experimental results show that, due to an analytic one-shot process, au-timee of R-GAP orders of magnitude shorter than DLG. Moreover, R-GAP can recover the data more accurately,
the label
via equivalence between convolution and multiplication with (block) cireulant matrix.

---

Published as a conference paper at ICLR 2021
while optimization based methods like DLG recover the data with artifacts, shown in Figure The statistical results in Table also show that the reconstruction of R-GAP has a much lower MSE than DLG on the CNN6 network. However, as R-GAP only considers gradient constraints and weight constraints
the current implementation, it does not work well on the CNN6-d network. Nonetheless, we find that it is easy assess the quality of reconstruction of gradient attack without knowing the original image. As the better reconstruction has less salt-and-pepper type noise. We measure this by the difference of the image and its smoothed version (achieved by a simple 3x3 averaging) and select the output with the smaller norm. This hybrid approach which we name H- GAP combines the strengths of R- R-GAP and DLG, and obtains the best results.
Architecture
Origin
Image
conv1 4x4g312.
Our approach
conv 3x330336,
conva 3x3gr36
convé 3x3/338
convs 3x3@664
120
3200x1 to
DLG
Figure 3: Performance of our approach and DLG over CNN6 architecture. The diagram on the left demonstrates the network architecture on which we perform attack. The activation functions are LeakyReLU, except the last one which is Sigmoid.
C
CNN6-d*
CNN6
CN 0,0090 1 9.3 x 10"4
R-GAP
0.010 1 0.0017
1.4 1 0.073
1.9 10
x
10-5
DLG
0.050 0.0014
0.053 + 0.0016
4.2
559
10
0.0012 + 1.8 10
H-GAP
0.0069 + 0.0012
0.053 + 0.0016
1.4 10
2.3
10
0.0012 + 1.8 10-4
CIFARIO *cINNIST
Table 1: Comparison of the performance of R-GAP, DLG and H-GAP. MSE has been used to mea- sure the quality of the reconstruction.
Moreover, we compare R-GAP with DLG LeNet which has been benchmarked in DLG et al. 2019). the statistical results are shown in Table 2 Both DLG and R-GAP perform well on LeNet. Empirically, if the MSE is around or below 1 10 the difference of the reconstruction will be visually undetectable. However, we surprisingly find that by replacing the Sigmoid function with the Leaky ReLU, the reconstruction of DLG becomes much poorer. The condition number of matrix A (from Algorithm[]] D changes significantly in this case. Since the Sigmoid function leads to a higher condition number at each convolutional layer, reconstruction error in the subsequent layer could be amplified in the previous layer, therefore DLG is forced to converge to better result. In contrast, R-GAP has an accumulated error and naturally performs much better on LeNet*. Additionally, we find R-GAP could be a good initialization tool for DLG. As shown in the last column of Table 2 by initializing DLG with the reconstruction of R-GAP, and running 8% of the previous iterations, achieve visually indistinguishable result. However, for LeNet*, we find that DLG reduces the reconstruction quality obtained by R-GAP, which further shows the instability of DLG.
Our rank analysis is useful offline tool to understand the risk inherent in certain network architec- tures. More precisely, we can use the rank analysis to find out the critical layer for the success of
Condition number conv22
Lonv
cuny3
DLG
R-GAP
R-CA- DLG
LeNet
1.8 x 1
6.1 x 10
32.4
3.7 x 10-5
1.1 10-4
1.1 x 10-6
+22.9
40.3
+2.9
18.6 10
10-8
=1.1 -8
LeNer
1.2 10a
1.3 x 10a
14.2
5.2
1.5 x 10
4.8 x 10
119.7
1.22.5
10.05
1.29 x 10
12.5 x 10
19.1 x 10-5
LoNer ideetiical LeNet uses Leaky RcLL aclivation function instead Sigmoodd
Table 2: Comparison of R-GAP and DLG on LeNet benchmarked in DLG et al.
2019
8

---

Published as a conference paper at ICLR 2021
gradient attacks and take precision measurements to improve the network's defendability. We report results on the ResNet-18, where the third residual block is critical since by cutting its skip connec- tion the RA-i increases substantially. To perform the experiments, use the approach proposed by| Geiping et al. (2020), which extends DL.G to incorporate image priors and performs better on deep networks. As shown in Figure 4 by cutting the skip connection of the third residual block, reconstructions become significantly poorer and more unstable. As a control test, cutting the skip connection of non-critical residual block does not increase defendability noticeably, Note that two variants have the same or even slightly better performance on the classification task compared with the backbone. In previous works (Zhu et al.) 2019: Wei et al. 2020), trade-ofi between accuracy and defendability of adding noise to gradients has been discussed. We show that using the rank analysis we are able to increase the defendability network with no cost in accuracy.
Image
Origin
conv 3x30F16
residual Block 3x3G266
ResNet18
residual Block 3x3
Variant 1
residual
3x3,932,0 /2
Variant
residual Black X
RA-i
Accuracy val.
MSE of reconstructions
1x3
R8sNet18
-1.0 10"
89.36%
0.12 + 0.0070
avgpool 4x4
Variant
-7.8 x 10
89.46%
0.32 0.021
Variant 2
-10 10
89.75%
0.15 + 0.0073
328X10
Figure 4: Left: Architectures of the ResNet18 with base width 16 and two variants. Variant cuts the skip connection of the third residual block. Variant cuts the skip connection of the eighth residual block. Upper right: Reconstruction examples of three networks. Lower right: Accuracy and reconstruction error of three networks. Training 200 epochs on CIFAR10 and saving the model with the best performance on the validation set, three networks achieve a close accuracy. Two variants perform even slightly better. In terms of gradient attacks, MSE of reconstructions from ResNetl 8 and Variant are similar, since Variant cut the skip connection of a non-critical layer and the RA-i does not change. Whereas, by cuting the skip connection of a critical layer, according to the rank analysis, increases RA-i substantially. MSE of the reconstructions from Variant I increases by nearly a factor of three with higher variance.
6 DISCUSSION AND CONCLUSIONS
R-GAP makes the first step towards a general analytic gradient attack and provides a framework to answer questions about the functioning of optimization-based attacks. It also opens new ques- tions, such as how to analytically reconstruct a minibatch of images, especially considering non- uniqueness due to permutation of the image indices. Nonetheless, we believe that by studying these questions, we can gain deeper insights into gradient attacks and privacy secure federated learning.
In this paper, we propose a novel approach R-GAP, which has achieved an analytic gradient attack for CNNs for the first time. Through analysing the recursive reconstruction process, we propose a novel rank analysis to estimate the feasibility of performing gradient based privacy attacks given network architecture. Our rank analysis can be applied to the analysis of both closed-form and optimization- attacks such as DLG. Using our rank analysis, we are able to determine network modifications that maximally improve the network's security, empirically without sacrificing its accuracy. Furthermore, we have analyzed the existence of twin data using R-GAP, which can explain at least in part why DLG is sensitive to initialization and what type of initialization is optimal. In summary, our work proposes a novel type of gradient attack, a risk estimation tool and advances the understanding of optimization-basee gradient attacks.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGEMENTS
This research received funding from the Flemish Government (Al Research Program).
REFERENCES
Peter L Bartlett, Michael Jordan, and Jon D McAuliffe. Convexity, classification, and risk bounds.
Journal of the American Statistical Association, 101(473):138-155 2006.
Emiliano De Cristofaro. An overview of privacy in machine learning. arXiv:2005.08679 2020.
Lixin Fan, Kam Woh Ng, Ce Ju, Tianyu Zhang, Chang Liu, Chee Seng Chan, and Qiang Yang. Rethinking privacy preserving deep learning: How evaluate and thwart privacy attacks. In Qiang Yang, Lixin Fan, and Han Yu (eds.), Federated Learning: Privacy and Incentive, pp. 32- 50. Springer, 2020.
Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradients: How easy is it to break privacy in federated learning? In Hugo Larochelle, Mare' Aurelio Ranzato, Balcan, and Hsuan- Tienn Lin (eds.), Advances in Neural Information Processing Systems 33, 2020.
Raia Hadsell,
Gene H. Golub and Charles F. Van Loan. Matrix Computations. Johns Hopkins University Press, 1996.
Zecheng He, Tianwei Zhang, and Ruby B. Lee. Model inversion attacks against collaborative in- ference. In Proceedings of the 35th Annual Computer Security Applications Conference, ACSAC '19, pp. 148-162, 2019.
Arthur Jochems, Timo M. Deist, Johan van Soest, Michael Eble, Paul Bulens, Philippe Coucke, Wim Dries, Philippe Lambin, and Andre Dekker. Distributed learning: Developing a predictive model based data from multiple hospitals without data leaving the hospital a real life proof of concept. Radiotherapy and Oncology, 121(3):499 - 467, 2016.
Arthur Jochems, Timo Deist, Issam El Naqa, Mare Kessler, Chuck Mayo, Jackson Reeves, Shruti Jolly, Martha Matuszak, Randall Ten Haken, Johan Soest, Cary Oberije. Corinne Faivre-Fime Gareth Price, Dirk Ruysscher, Philippe Lambin, and André Dekker. Developing and validating survival prediction model for nsele patients through distributed learning across three countries. International Journal of Radiation
gagolooyyBBooggge Physics, 99, 04 2017.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, 2015.
Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter Richtarik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. In NIPS Workshop Private Multi-Party Machine Learning, 2016.
Dong C. Liu and Jorge Nocedal. On the limited memory BFGS method for large scale optimization.
Math. Program., 45(1-3):503-522 August 1989.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-eficcee
learning of deep networks from decentralized data. In Aarti Singh and Jerry Zhu (eds.), Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pp. 1273-1282, 2017.
L. T. Phong, Y. Aono, T. Hayashi, L. Wang, and S. Moriai. Privacy-preserving deep learning via additively homomorphic encryption. IEEE Transactions on Information Forensics and Security, 13(5):1333- 2018
Maria Rigaki and Sebastian Garcia. A survey of privacy attacks in machine learning. CoRR, abs/2007.076466 2020.
Z. Wang. M. Song, Z. Zhang, Y. Song, Q. Wang, and H. Qi. Beyond inferring class representatives: User-level privacy leakage from federated learning. In IEEE INFOCOM 2019 IEEE Conference Computer Communications, pp. 2512-2520, 2019.
10

---

Published as a conference paper at ICLR 2021
Wenqi Wei, Ling Liu, Margaret Loper, Ka-Ho Chow, Mehmet Emre Gursoy, Stacey Truex, and Yanzhao Wu. A framework for evaluating client privacy leakages in federated learning. Liqun Chen. Ninghui Li, Kaitai Liang, and Steve Schneider (eds.), Computer Security ESORICS, pp- 545-566. Springer, 2020.
Ziqi Yang, Jiyi Zhang, Be-Chien Chang, and Zhenkai Liang. Neural network inversion in adver- sarial setting via background knowledge alignment. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pp. 225-240, 2019.
Yuheng Zhang, Ruoxi Jia, Hengzhi Pei, Wenxiao Wang, Bo Li, and Dawn Song. The secret revealer: Generative -ndee--inversion attacks against deep neural networks. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 250-258 2020.
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. iDLG: Improved deep leakage from gradients. arXiv:2001.024. 2020.
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. In H. Wallach, Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 14774-14784, 2019.
A QUANTITATIVE RESULTS OF RANK ANALYSIS
quantitative analysis of the predictive performance of the rank analysis index for the mean squared error of reconstruction is shown in Table 3
RA-i
405
316
MSE
9
0.056 1 0.0035 0.063 1 0.004
4
0.013
22.2 10-9
1:2.0 10
#7.2 10-4
Table 3: Mean square error of the reconstruction over test set of CIFARIO. The corresponding network architecture has been shown in Figure 2 in the same order. Rank analysis index (RA-i) clearly predicts the reconstruction error. We can also regard RA-i the security level of network. negative value indicates that the gradients of the network are able to fully expose the data, i.e. insecure, while positive value indicates that completely recover the data from gradients is possible. On top of that, higher RA-i indicate higher reconstruction error, therefore the network is more secure. According our experiment, the order of magnitude of MSE is equal 10 10-4, we could barely visually distinguish the recovered and real data, as shown in the fourth column of Figure / Note that, as the network gets deeper. DLG will become vulnerable, R-GAP will also be effected by numerical error. Besides that, DLG is sensitive to the initialization of dummy data, while R-GAP also needs to confirm the μ if not unique. Therefore, RA-i provides a reasonable upper bound of the privacy risk rather than quality prediction of one reconstruction.
less than
B TWIN DATA
As we know at always allow to uniquely recover ut. It is relatively straightforward to show that for mono- tonic convex losses (Bartlett al. 2006), ou l is invertible for μ 0, T. S 0 for p 2 0, de and +cc 8p μ 0. Due to the non-uniqueness of f w.r.t 8 uu, have:
at Tu 4 is mon-ooottoiic as shown in Figure which means knowing ay u does not
dt
ae al
3 x
s.t.
#
(17)
where x the real data.
Taking the common setting that activation functions are ReLU LeakyReLU, we can derive from Eq. that:
de
W;
W;; i= I,...,d
(18)
OW.
aW
11

---

Published as a conference paper at ICLR 2021
if there is W, is equal to W, whereas the corresponding x is not can find data point that differs from the true data but leads to the same gradients. We name such data twin data, denoted by x. As know the gradients and μ of the twin data x, by just giving them to R-GAP, we are able to easily find out the twin data. As shown in Figure 5 twin data is actually proportional to the real data and smaller than it, which can also be straightforwardly derived from Equation to Equation 8 Since the twin data and the real data trigger the same gradients, by decreasing the distance of gradients
since μr F jú,
Equation [ DLG suppose converge either of these data. As shown in Figure 5 we initialize DLG with a data close to the twin data x, DLG converges to the twin data. In the work of Wei et (2020). the authors argue that using an image from the same
0.51
64-
-0.14
0.14
P
-1.13
-0.33
-032
-2300
Step
Figure 5: Twin data. The left figure demonstrates a twin data X, which will trigger exactly the same gradients the real data does. Therefore, from the perspective of DLG, these two data global minimum for the objective function. The right figure shows that by adding noise to shift the twin data little and using
initialization, DLG will converge the twin data rather than real data.
class as the real data would be the optimal initialization and empirically prove that. We want to point that twin data is one important factor why DLG is sensitive to the initialization and prone to fail with random initialization of dummy data particularly after some training steps of the network. Since DLG converges either to the twin data or the real data depends on the distance between these two data and the initialization, an image of the same class is usually close to the real data, therefore, DLG works better with that. While, with respect to μ or the prediction the network, a random initialization is close to the twin data, so DLG converges to the twin data. However, the twin data has extremely small value, so any noise that comes up with optimization process stands out in the last result as shown in Figure 5
worth noting that the twin data can be fully reconstructed only RA-i < 0. In other words, complete reconstruction is feasible and the twin data exits, R-GAP and DLG can recover either the twin data or real data depend on the initialization. But both of them lead to privacy leakage.
C VIRTUAL CONSTRAINTS
In this section we investigate the virtual constraints as proposed in the rank analysis. To the begin- ning, let derive the explicit virtual constraints from the i layer the reconstruction of the i layer by assuming the activation function is an identity function. The weight constraints of the layer can be expressed as:
Wx,-1 Z;
Split W, into two parts coherently, i.e.:
W
+
x;
z
(19)
12

---

Published as a conference paper at ICLR 2021
Assume the upper part of the weights W is already full rank, therefore:
2 I,
(20)
- W W 1+2
(21)
2 I_
(22)
- Iz
(23)
Substituting Equation 21 into Equation 23 rearranging:
we can derive the following constraints over z after
WW_ W - I. )z 0
(24)
Since the activation function is the identity function, i.e. z = x,, the virtual constraints that the i-th layer has inherited from the weight constraints of 1 layer are:
Vx; V= W_ W_
(25)
Virtual constraints as external constraints are able to compensate the local rank-deficiency of an intermediate layer. For other strictly monotonic activation function like Leaky ReLU, Sigmoid, Tanh, the virtual constraints over X; can be expressed as:
(x,=(xx)=-0 =0
(26)
This is not a linear equation system w.r.t. X; therefore it is hard to be incorporated in R-GAP. In terms of ReLU the virtual constraints could become further more complicated which will reduce its efficacy. Nevertheless, the reconstruction of the i-th layer must take the virtual constraints into account. Otherwise, it will trigger non-negligible reconstruction error later on. From this perspec- tive, we can see that iterative algorithms like optimization-base attacks can inherently utilize such virtual constraints, which is a strength of O-GAP.
We would like to point out that theoretically the gradient constraints also have the same effect the weight constraints in the virtual constraints but in a more sophisticated way. Empirical results show that the gradient constraints of previous layers do not have evident impact on the subsequent layer in the O-GAP, so we have not taken it into account. The number of virtual constraints at i-th layer can therefore be approximated by Σ n=1 max |
xxl. 0) - max[[xx))
|
Wxl 0).
D RANK ANALYSIS OF THE SKIP CONNECTION
the skip connection skips one layer, for simplicity assuming the activation function is the identity function, then the layer can be expressed
W x; W W+I
(27)
where is the output of this layer, the weight matrix W is clear and the number of weight con- straints is equal to ffl While the expression of gradients are the same as without skip connection, since:
VW VW
(28)
Therefore the number of gradient constraints is equal to |W] In other words, without consideration of the virtual constraints, if [ |W| [x|] this layer is locally rank-deficient, otherwise it is full rank. This is the same as removing the skip connection.
If the skip connection skips tity function, then the residual block can be expressed as:
layers, for simplicity assuming the activation function is iden-
W1x1; f W2x +
(29)
Whereas, the residual block has its equivalent fully connected format, i.e.:
W
w
W2
W2 I]
(30)
Wixi
x Wixi
(31)
xi
W/
(32)
13

---

Published as a conference paper at ICLR 2021
From the perspective of a recursive reconstruction, is clear, so after the reconstruction of Xg. the in- put of this block X1 can be directly calculated by subtracting W2x2 from f as shown Equation 29 Back to the Equation 31 that means only x needs to be recovered. Similar to the analysis for one layer, in terms of the reconstruction of xzz the number weight constraints is |/l and the number of gradient constraints is W2]. On top of that the upper part and lower part of X related, which actually represents the virtual constraints from the first layer. Taking these into account, there are [W2l + [f] + |2| constraints for the reconstruction of X2. However, X is also augmented compared with X2 and the number of entries is X1 [x2]. To conclude, if [f W2l < [x1] the residual block locally rank-deficient, otherwise is full rank. Seemingly, the constraints of the last layer have been used to reconstruct the input of the residual block due to the skip connection This is in- teresting trait, because the skip connection is able to make the rank-deficient layers like bottlenecks again full rank, as shown in Figure 6 It is worth noticing that the bottlenecks have been commonly used for residual blocks. Further, downsampling residual blocks also have this characteristic rank condition, the gradient constraints in the last layer are much more than the first layer due to the number channels.
Network
w/ skip connection
w/o skip connection
5x5@4
1x1@1
4x4@4
5x5@4
1x1@2
1x1 44
4x4@5
5x5@4 4
1x1@ 6
1x1@4 4
4x4@5
Figure 6: Comparison of optimization-basae gradient attacks over architectures with or without the skip connection. The width of blue bars represents the number of features at each layer. The first row shows that there is impact the reconstruction if the skip connection skips one layer. The second row shows if the skip connection skips a bottleneck block, which is rank-deficient, the resulting network can still be full rank and enable full recovery of the data. The third row shows the reconstructions of two full-rank architectures. Since the skip connection aids in the optimization process, the quality of its reconstruction is marginally better.
E IMPROVING DEFENDABILITY OF RESNET101 101
We also apply the rank analysis to ResNet101 and try to improve its defendability. However, we find that this network is redundant. It is not possible to decrease the RA-i by cutting single skip connection as was done in Figure 4 Nevertheless, we devise two variants, the first of which cuts the skip connection of the third residual block and generates layer that locally rank-deficient
Through formulating the residual block with its equivalent sequential structure, this conclusion readily generalizes residual blocks with three layers.
14

---

Published as a conference paper at ICLR 2021
and requires a large number of virtual constraints. Additionally, we devise second variant, which cuts the skip connection of the first residual block and reduces the redundancy of two layers. The accuracy and reconstruction error of these networks can be found in Table 4
RA-i
Accuracy on val.
MSE of reconstructions
10
-1.4 x 10"
91.04%
0.96 + 0.091
Variant
- 1.4 x 10"
90.36%
1.8 + 0.14
Variant 2
1.4 x 10
90.16%
1.3 1 0.14
Table 4: Training 200 epochs on CIFARIO and saving the model with the best performance on the validation set, ResNer101 with base width 16 and its two variants achieve similar accuracy on the classification task. The two modified variants which are designed to introduce rank deficiency per- form almost as well as the original, but better protect the training data. We conduct a gradient attack with the statc-of-the of the two rank- ann-ceficient variants is significantly higher, which indicates that for deep networks, we can also improve the defendability by decreasing local redundancy or even making layers locally rank-deficient.
approach proposed by Geiping et al. (2020). MSE of the reconstructions
F R-GAP IN THE BATCH SETTING RETURNS A LINEAR COMBINATION OF TRAINING IMAGES
can be verified straightforwardly that R-GAP the batch setting will return linear combination of the training data. This is due to the fact that in the batch setting the gradients are simply accu- mulated. The weighting coefficients of the data in this linear mixture are dependent on the various values of for the different training data (see Figure II. Figures 7 and g illustrate the results vs. batch DLG (Zhu et al. 2019) on examples from MNIST.
Origin
R-GAP
DLG
4
2
7
9
7
4
9
9
9
5
4
/
4
4
1
Figure 7: Reconstruction over FCN3 network with batch-size equal to 2. For FCN network, R- GAP is able to reconstruct sort of a linear combination of the input images. DLG will also works perfectly such architecture.
G ADDING NOISE TO THE GRADIENTS
The effect on reconstruction of adding noise the gradients is illustrated in Figure 9
15

---

Published as a conference paper at ICLR 2021
Origin
R-GAP
DLG
7
2
1
4
7
4
2
O
1
1
4
9
9
1
5
9
6
9
0
1
0
9
4
6
1
5
7
9
3
4
7
9
3
9
Figure 8: Reconstruction over a FCN3 network with batch-size equal to Sometimes DLG will converge to image similar to the reconstructed by the R-GAP.
Image
Image
Image
Image
(00 0.0.)
4x4 conv1, 4
4x4 convl, (2x4)
4x4 conv1, (4x4)
4x4 6x)x
3364x1 fc
2x3364))1 fc
(4x3364)x1 fc
(16x3364)x1 fc
A0,0 0.005
N/0, 0.001)
Figure 9: terms of least square as what we have used for R-GAP, overall increasing the width of the network will involve more constraints and hence enhance the denoising ability of the gradient attack. For O-GAP this also means a more stable optimization process and less noise in the recon- structed image, which has been empirically proven by Geiping al. (2020). Increasing the width of every layer will definitely decrease the RA-i, so the quality of reconstruction has been improved. Whereas, increasing the width of some layers may not change RA-i of network, since the RA-i of a network is equal to the largest RA-i among all the layers, i,c, the reconstruction will not get better. However, it is widely believed that more parameter means less secure.
16

---

Published as a conference paper at ICLR 2021
H DERIVING GRADIENTS
=i/a-1(x)
14 = yWada-1
Wd-1 0d-2 (W (x))
(33)
xxx)
8 = log(1 + te
(34)
de
-M
de 1 ca
d1s
(35)
1 60
de 0n.
df y) d( d(wafa-1(x))
(36)
de v) (d(wa) (o11))--1(x) + wad(fa-1(x))
de-
(37)
0p'
0e y)) de yf ofd-i(x) dwa + (w] (g dfa-1(x)
dl
(38)
0p DE de vfIl1
(39)
Owa
0p
dl dl Owd Ol de Owd Ol
06
dwd + (wd 0p
y)) (d 3 df)-
(40)
dwd + ((w) T( 0l
y) ) df)-
(41)
0p
08
de
dwd + ((w) 0p'
y)) 2 1(1) (d(W + Wa-rd(fa-2(x))
(42)
Owd
10
30
Th. !!
t--p Sd2
(43)
OW
1-1
0e
de Owd
dwa + OW d-1
dWa-1 WT ((w]
1)) 2 d'a1)) dfa-2(2)
(44)
17


Reviews:
[{"review_id": "C2-I6FaiyEc", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors proposed a theoretical explanation of the gradient attack on privacy. To be specific, a closed-form approach, namely recursive gradient attack on privacy has been proposed to explain how the gradients can be used to recover the original data. Moreover, the authors also presented a rank analysis method that is used to estimate the risk of being gradient attacked. Overall, this paper is easy to follow and well-written. I have a few concerns as follows:\n1. In Eqn.10, the authors assume the activation function is ReLU or LeakyReLU. In that case, the recursive form will be held. I guess whether the limitation for this method would be the activation function has to be ReLU or LeakyReLU? For instance, sigmoid and tanh activation functions are also widely used. Whether the proposed method is able to address those? If not, what would the reconstruction errors be.\n\n2. I am a little bit confused by the equations (19) and (20). When the activation functions are non-linear, how the authors define V? Also, how does V affect the layer rank? Maybe the conclusion below equation (20) is not very straightforward to me. \n\n3. As for the networks that used in this paper, I wonder when residual connections are used, how the rank deficiency problem would be?\n\n4. The follow-up question is when the network is very deep, like DenseNet and ResNet, whether the conclusions of this paper will hold? \n\n5. The symbols in Algorithm 1 should be consistent to the context. More importantly, I would suggest the authors highlight the correspondences between the equation and the algorithm diagram.\n\n6. Practical usage is one of my concern. In practice, researchers or engineers may use very deep models for practical problems. If the authors could demonstrate a more practical model, that would make this submission very strong. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "9DzFIJE_ERl", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the problem of gradient attack in deep learning models. In particular,  this paper tries to form a system of linear equations to find a training data point when the gradient of the deep learning model with respect to that data point is available. The algorithm for finding the data point is called R-GAP.\n\nStrengths: \n1. The idea of the paper is simple and interesting. The main idea is that for a deep learning model with $d$ layers, we can form $d$ systems of linear equations that can be solved recursively. Solving the last system of linear equations gives us the reconstructed data point. \n2. Moreover, because R-GAP is using systems of linear equations, it is very easy to know/analyze the feasibility of the R-GAP algorithm.\n3. In contrast to (Phong et al. (2018)), the proposed method works for CNNs as well. \n\nWeaknesses: \n1. The contribution of the paper seems limited. This paper extends the method of (Phong et al. (2018)). More precisely, (Phong et al. (2018)) forms a system of equations only with respect to the first layer. The current paper does the same thing for $d$ layers.\n\n2. This paper compares R-GAP with the DLG algorithm. However, there is an improved version of the DLG algorithm called iDLG (Zhao et al. (2020)). Therefore, more numerical examples are required to compare R-GAP with iDLG. \n3. This paper situates itself in the Federated Learning (FL) literature. However, in FL problems, each node reports the gradient with respect to the whole local training data points (not a single data point). Therefore, it is not realistic to assume that the central node or an adversary has access to the gradient with respect to one data point. I believe batch DLG (Zhu et al., 2019) is a better attack method in an FL setting. \n\nUpdate: I would like to increase the score to 7. The authors have improved the paper and addressed my concerns.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "7zj1CqFpDEp", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new gradient attack method named R-GAP. R-GAP decomposites the DNN gradient attack problem into subproblems for each layer, and recursively solves each of them. The subproblem of each layer is formulated as a least-square reconstruction problem.\n\nThe authors further point out the rank of network weight matrix is (non-surprisingly) correlated with the difficulty of input recovery. Based on this finding, they design a metric based on the weight matrix rank to estimate the feasibility of fully recovering data.\nExperimental results on MNIST and CIFAR10 show that the proposed method R-GAP is comparable or superior to the classic DLG method. The authors also claimed the proposed method to be much faster than DLG baseline.\n\nStrengths:\n1. Gradient attacks raise data privacy concerns in many applications such as federated learning, making it an important problem.\n2. As an analytical method to solve the input reversion problem, R-GAP should have its intrinsic advantage over previous optimization-based gradient attack (O-GAP) methods such as DLG. For example, in my assumption (and also claimed by the authors), R-GAP can be much faster than O-GAP.\n3. R-GAP has much better performance than DLG on full-rank CNN6 networks, as shown both visually and numerically in Figure 3 and Table 1. This shows that if the attacked model satisfies the full-rank condition, R-GAP can be both faster and more effective than DLG. \n\nWeakness:\n1. Insufficient experiments.\nMy largest concern is over the lack of necessary experiments to show the advantage of R-GAP. \ni. Why only showing results on a self-designed CNN6 network? In order to fairly compare with DLG, and also to show the general effectiveness of the proposed method, the authors should also consider comparing with DLG on some standard network, such as the LeNet benchmarked in many previous gradient attack works [1,2].\nThis is very important also because we need to see whether the popular deep models such as LeNet, VGG, ResNet, etc. satisfy the full rank condition required by the proposed method. If not, the proposed R-GAP will have limited application scenarios. \nii. Why not compare with more recent gradient attack methods such as iDLG [2], which has been shown to also outperform the original DLG [1]?\niii. The authors claimed the proposed method is much faster than DLG. Although I agree this is intuitively true, I think it necessary to report the numbers in the paper. For example, how much time/FLOPs does it take to attack a single image for each method?\n\n2. Additional tricks used without detailed description in the Method section. \nIn Table 1, the authors show that R-GAP is largely outperformed by DLG on the rank-deficient network CNN6-d. However, according to the authors' vague descriptions, simply adding a smoothing operation can largely improve R-GAP performance. (I assume H-GAP = R-GAP + image smoothing?) Is the image smoothing the main technique making the proposed method effective?\nThis is really confusing since neither H-GAP nor image smoothing is mentioned in the method/related work sections. I suggest the authors to provide more descriptions about the H-GAP method and also provide explanations why it largely outperforms R-GAP.\n\nI'm willing to increase my score if these concerns are properly tackled during the rebuttal period.\n\nOther comments:\n1.  The artifacts of DLG reconstruction images are mainly located on the corner of the images (see Figure 2), while the artifacts of DLG are evenly distributed on the whole images (see Figure 3). Is this a general trend? If yes, any explanations or intuitions behind this?\n2. The proposed RA-i is only using matrix rank to predict the hardness of input recovery. In my view, it might be better to consider using matrix condition number as the metric. This is because the sub-problem at each layer is basically a least-square regression problem, and two least-square regression problems can have different difficulties when the matrix have identical ranks but different condition numbers. In other words, condition number contains more information than rank, and thus might be more useful. (Please point out if I'm wrong here.)\n\nReference\n\n[1] Deep leakage from gradients.\n\n[2] iDLG: Improved Deep Leakage from Gradients. \n\nUpdate: The authors have addressed my concerns and now I vote for acceptance.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The major criticism of this paper after the initial reviews was a lack of experimental results on deeper and more modern architectures that include skip connections.  The authors added results to the paper to address these issues.
Decision: Accept (Poster)