Regression Model Fitting under Differential Privacy and Model Inversion Attack

1 Introduction

Privacy-preserving data mining is an important research area. In many applications, sensitive datasets such as financial transactions, medical records, or genetic information about individuals are often only disclosed to authorized users, yet models learned from them are made public. The released models may be exploited by an adversary to breach privacy of both participant individuals in the datasets and regular nonparticipant individuals.

Differential privacy [Dwork et al., 2006] has been developed and shown as an effective mechanism to protect privacy of participant individuals. Simply speaking, differential privacy is a paradigm of post-processing the models such that the inclusion or exclusion of a single individual from the dataset makes no statistical difference to the results found. In other words, differential privacy aims to achieve the goal, i.e., the risk to one's privacy should not substantially increase as a result of participating in a database when models built

Xintao Wu

University of Arkansas Fayetteville, AR, USA xintaowu@uark.edu

from the database are released to public. On the contrary, the models (or even the perturbed models which preserve differential privacy of participants) may be exploited to breach attribute privacy of regular individuals who are not necessarily in the dataset. In [Fredrikson et al., 2014], the authors developed a model inversion attack where an adversary uses the released model to make predictions of sensitive attributes (used as input to the model) of a target individual when some background information about the target individual is available. Fredrikson et al. showed that differential privacy mechanisms prevent model inversion attacks only when the privacy budget is very small. However, for privacy budgets effective at preventing attacks, the model utility in terms of performing simulated clinical trials is significantly lost.

Hence it is imperative to develop mechanisms to achieve differential privacy protection for participants and prevent attribute privacy disclosure from model inversion attacks while retaining the utility of the released models. In this paper, we focus on regression models which have been widely applied in many applications. Regression studies often involve continuous data (e.g., blood lipid levels or heights) in addition to categorical attributes (e.g., gender, race and disease). Various regression models including linear regression, logistic regression, and lasso models have been developed. There are generally two approaches to derive differential privacy preserving regression models. The first approach is to directly perturb the output coefficients of the regression models. However, this approach requires an explicit sensitivity analysis of the regression models, which is often infeasible. The second approach is to add noise to the objective function used to derive regression models [Chaudhuri and Monteleoni, 2008]. Recently the authors [Zhang et al., 2012] developed the functional mechanism which adds noise to the coefficients of polynomial representation of the objective function, and showed that deriving a bound on the amount of noise needed for the functional mechanism involves a fairly simple calculation on the object function.

Differential privacy preserving regression models [Chaudhuri and Monteleoni, 2008; Zhang et al., 2012] guarantee protection against attempts to infer whether a subject was included in the training set used to derive a model. It is not effective to protect attribute privacy, which is the target of the model inversion attacks. This is because the mechanism perturbs coefficients equally no matter whether they correspond to sensitive or non-sensitive attributes. However, model inversion attacks seek to exploit correlations between the target sensitive attributes, known non-sensitive attributes and the model output. In this paper, we aim to develop a new approach to learn differential privacy preserving regression models which effectively prevent model inversion attacks and retain the model utility. Our approach leverages the functional mechanism but effectively balances the privacy budget for sensitive and non-sensitive attributes in learning the differential privacy preserving regression models.

1.1 ProblemFormalization

Let D be a data set that contains n tuples t1, t2, ..., tn regarding d explanatory attributes X1,X2, · · · ,Xd and one response attribute Y . The explanatory attributes can be divided into two groups: non-sensitive attributes and sensitive attributes. For simplicity, we consider there is only one sensitive attribute Xs and all remaining ones are non-sensitive. Our analysis can be straightforwardly extended to multiple sensitive attributes. For each explanatory attribute Xi, without loss of generality, we assume its domain Xi in the range of [-1, 1]. Similarly, we denote Y as the domain of the response attribute Y , which could be [-1, 1] for linear regression or {0, 1} for logistic regression. We denote each tuple ti as (xi, yi) where xi = (xi1, xi2, ..., xid). Throughout this paper, we use bold lower-case variables, e.g., xi, to represent vectors; upper-case alphabets, e.g., Xi, to denote an attribute; calligraphic upper-case alphabets, e.g., Xi, to denote the domain of attribute Xi. xT refers the transpose of vector x. Table 1 summarizes the notations used in this paper.

The data mining task is to release a regression model from D to predict the attribute value of Y given the corresponding attribute value of X1, ...,Xd. That is to say, we are to release a regression function ρ parameterized with a real number vector ω = (ω1, ..., ωd). The model takes xi as input and output the corresponding prediction for yi as ˆ yi = ρ(xi, ω). Most regression analytical methods often iteratively optimize some objective functions with various constraints. A cost function f is often chosen to measure the difference between the original and predicted values based on specific ω. The optimal model parameter ω∗ is defined as the one that minimizes the cost function.

In our paper, we consider two commonly used regression models, linear regression and logistic regression.

Definition 1. (Linear Regression) Assume without loss of generality that Y has a domain of [-1, 1]. A linear regression on D returns a prediction function ˆ yi = ρ(xi, ω∗ ) = xTi ω∗ , where ω∗ is a d-dimensional real vector that minimizes the following cost function.

Definition 2. (Logistic Regression) Assume Y has a domain of {0, 1}. A logistic regression on D returns a prediction function which returns ˆ yi = 1 with the probability P (ˆ yi = 1|xi, ω∗ ) = exp(xTi ω∗ )/(1 + exp(xTi ω∗ )), where ω∗ is a d-dimensional real vector that minimizes the following cost function.

Releasing the regression model under differential privacy requires noise injection to the model parameter ω∗ . Adding noise to ω∗ involves the derivation of the sensitivity of ω∗ , which is rather challenging. In this paper, we apply the functional mechanism proposed in [Zhang et al., 2012], which perturbs the objective function of the regression model. However, the release model parameter ω∗ or its perturbed one ¯ω could be exploited by the adversary to predict the value of sensitive input attributes xαs for a target individual α when some background information about the target individual is available. Formally, the adversary has access to the regression model with parameters ω∗ , the domain value and marginal probability of each attribute, accuracy metrics of the model like the confusion matrix, in addition to some background knowledge of the target individual including the value of a subset of non-sensitive input attributes and the value of output attribute of the model yα.

Our research problem is how to derive the perturbed regression model parameter ¯ω such that we achieve differential privacy protection for participants and prevent attribute privacy disclosure frommodel inversion attacks on regular individuals while retaining the utility of the regression model.

2 Background

2.1 Differential Privacy

We revisit the formal definition and the classic mechanism of differential privacy. In prior work on differential privacy, a database is treated as a collection of rows, with each row corresponding to the data of a different individual. Differential privacy ensures that the inclusion or exclusion of one individual's record makes no statistical difference on the output.

Definition 3. (Differential Privacy[Dwork et al., 2006]) A randomized function A gives ϵ-differential privacy if for all data sets D and D′ differing at most one row, and all S ⊆ Range(A)

The privacy parameter ϵ controls the amount by which the distributions induced by two neighboring data sets may differ (smaller values enforce a stronger privacy guarantee).

A general method for computing an approximation to any function f while preserving ϵ-differential privacy is given in [Dwork et al., 2006]. It computes the sum of the true answer and random noise generated from a Laplace distribution. The magnitude of the noise distribution is determined by the sensitivity of the computation and the privacy parameter specified by the data owner. The sensitivity of a computation bounds the possible change in the computation output over any two neighboring data sets (differing at most one record).

Definition 4. (Global Sensitivity[Dwork et al., 2006]) The global sensitivity of a function f : Dn → Rd

Theorem 1. (Laplace Mechanism[Dwork et al., 2006]) An algorithm A takes as input a data set D, and some ϵ > 0, a query Q with computing function f : Dn → Rd , and outputs

where the Yi are drawn i.i.d from Lap(GSf(D)/ϵ). The Algorithm satisfies ϵ-differential privacy.

2.2 Model Inversion

Model inversion attack [Fredrikson et al., 2014] leverages the released regression model y = ρ(x, ω∗ ) trained from a dataset D which contains a sensitive attribute Xs. An adversary then exploits the released model to predict the sensitive input attribute value of the target individual based on some of the target individual's background (values of some nonsensitive input attributes, e.g. demographic information, for the model) and the observed response attribute value.

The model inversion attack algorithm works as follows. The adversary has access to the regression model ρ with parameter ω∗ trained over a dataset D drawn i.i.d from an unknown prior distribution p. Recall that D has input domain X1 × · · · × Xd and output domain Y. The target individual is represented by tα = (xα, yα). The adversary is assumed to know values of some (or all) input attributes of the target individual except the sensitive one, i.e., S ⊆ X\Xs, and the output value yα. The sensitive attribute value the adversary wants to learn is referred to as xαs. Note that the target individual tα is not necessarily in D. In addition to the released model ρ(x, ω∗ ), the adversary also has access to marginal p1, ..., pd, py of the joint prior p, the input domain and the output domain, the information π about the model prediction performance where π(y, y′ ) = Pr(yi = y|ρ(xi, ω∗ ) = y′ ). The algorithm makes prediction by estimating the probability of a potential target attribute value given the available information of the target individual and the model.

• Find the feasible set ˆ X ⊆ X, i.e., for ∀x ∈ ˆ X , x matches xα on each known attribute in S.
• if ˆ X = 0, return null; otherwise, return ˆxαs = z that maximizes ∑ x∈ ˆ X :xs=z π(yα, ρ(xα, ω)) ∏1≤j≤d pj (xj ).

In step 1, the algorithm filters the domain space using the known attribute values of the target individual. In step 2, the algorithm calculates weight to each candidate row in the domain space based on known priors and how well the model's output on that row coincides with the target individual's model output value. It then returns the value of the target sensitive attribute with the largest weight computed by marginalizing the other attributes. The model inversion algorithm is optimal as it minimizes the expected misclassification rate on the maximum-entropy prior given the model and marginals. It was demonstrated in [Fredrikson et al., 2014] that the value of the sensitive attribute is predicted with significantly better accuracy than guessing based on marginal distributions. It was also concluded that differential privacy mechanisms can prevent model inversion attacks only when privacy budget is very small, but in those cases, the private model usually does not simultaneously retain desirable efficacy. In clinical trials, such lack of efficacy may put patients in increased risk of health problems.

3 Our Approach

We propose a new approach to provide regression models under differential privacy and against model inversion attacks. Our approach aims to improve privacy specifically for sensitive attributes while retaining the efficacy of the released regression model by balancing the privacy budget for sensitive and non-sensitive attributes. Our approach leverages the functional mechanism proposed in [Zhang et al., 2012] but perturbs the polynomial coefficients of the objective function with different magnitudes of noise.

3.1 Functional MechanismRevisited

Functional mechanism achieves ϵ-differential privacy by perturbing the objective function fD(ω) and then releasing the model parameter ¯ω that minimizes the perturbed objective function ¯ fD(ω) instead of the original one. Because fD(ω) is a complicated function of ω, the functional mechanism exploits the polynomial representation of fD(ω).

The model parameter ω is a vector that contains d values ω1, ω2, ..., ωd. Let φ(ω) denote a product of ω1, ω2, ..., ωd, namely, φ(ω) = ωc1 1 · ωc2 2 ...ωcd d for some c1, c2, ..., cd ∈ N. Let Φj(j ∈ N) denote the set of all products of ω1, ω2, ..., ωd with degree j, i.e.,

By the Stone-Weierstrass Theorem, any continuous and differentiable f(ti, ω) can always be written as a polynomial of ω1, ω2, ..., ωd, i.e., for some J ∈ [0,∞], we have

where λφti ∈ R denotes the coefficient of φ(ω) in the polynomial. Similarly, fD(ω) can also be expressed as a polynomial of ω1, ..., ωd.

For example, the polynomial expression of the linear regression is as follows.

We can see that fD(ω) only involves monomials in Φ0 = {1}, Φ1 = {ω1, ω2, ..., ωd}, and Φ2 = {ωiωj|i, j ∈ [1, d]}. Each φ(ω) has its own coefficient, e.g., for ωj , its polynomial coefficient λφti = -2yixij.

fD(ω) is perturbed by injecting Laplace noise into its polynomial coefficients λφ, and then the model parameter ¯ω is derived to minimize the perturbed function ¯ fD(ω). Each polynomial coefficient λφ is perturbed by adding Laplace noise Lap( ∆ϵ ), where ∆ = 2maxt ∑Jj=1 ∑φ∈Φj ||λφt||1, according to the following Lemma 1.

Lemma 1. [Zhang et al., 2012] Let D and D′ be any two neighboring datasets. Let fD(ω) and fD′ (ω) be the objective functions of regression analysis on D and D′ , respectively, and denote their polynomial representations as follows:

Then, we have the following inequality

where ti, t′i or t is an arbitrary tuple.

When the polynomial form of an objective function (e.g., logistic regression objective function) contains terms with unbounded degrees, [Zhang et al., 2012] developed an approximation polynomial form based on Taylor expansion. The perturbation method based on the functional mechanism [Zhang et al., 2012] also removes the requirements, i.e., the convexity of the objective function, from the original function perturbation approach [Chaudhuri and Monteleoni, 2008].

3.2 Improved Perturbation of Objective Function

To better optimize the balancing between privacy and the regression model' efficacy, we propose a new algorithm based on the functional mechanism to improve privacy specifically for sensitive attributes. To improve the privacy on Xs, we aim to weaken the correlation between Xs and the model output Y

by perturbing the corresponding ωs more intensely. In other words, we need to add noise with larger magnitude to the coefficients of the monomials involving ωs and add noise with smaller magnitude to the other coefficients. As a result, we expect to retain the utility of the released regression model while achieving differential privacy for participants and preventing model inversion attacks.

In general, a database can contain more than one sensitive attribute. We allocate privacy budget ϵn for non-sensitive attributes and ϵs for sensitive ones. We introduce a ratio parameter, γ such that ϵs = γϵn and 0 < γ ≤ 1. The smaller the γ, the more noise added to the sensitive attributes.

Algorithm 1 Functional Mechanism with Different Perturbation of Coefficients

Input: Database D, objective function fD(ω), privacy threshold ϵ, privacy budget ratio γ

Output: ¯ω

• 1: Set Φn = {},Φs = {};
• 2: for each 1 ≤ j ≤ J do
• 3: for each φ ∈ Φj do
• 4: if φ does not contain ωs for any sensitive attribute then
• 5: Add φ into Φn;
• 6: else
• 7: Add φ into Φs;
• 8: end if
• 9: end for
• 10: end for

15: for each 1 ≤ j ≤ J do

16:

for each φ ∈ Φj do

19:

else

20:

21:

end if

22:

end for

• 23: end for

• 25: Compute ¯ω = argminω ¯ fD(ω);
• 26: return ¯ω;

Specifically, we split all φs into two subsets Φn and Φs based on whether they involve any sensitive attribute, as shown in Lines 1-10 of Algorithm 1. Secondly, we determine the privacy budget according to the given ϵ and the privacy budget ratio γ. In Line 11, we set ∆ based on the maximum value of all the coefficients λφt of φ(ω) in the polynomial. Accordingly, In Lines 12-13, β1 and β2 can be considered as the fraction of contributions to ∆ from coefficients corresponding to elements in Φn and that in Φs. We will derive formula of ∆, β1 and β2 for linear regression and logistic regression and show they do not disclose any private information about dataset D in Results 1 and 2, respectively. Thirdly, we add noise to polynomial coefficients of φ ∈ Φn with ϵn and to those of φ ∈ Φs with ϵs, to derive the differentially private objective function ¯ fD(ω). Finally, we calculate and output the optimized ¯ω according to ¯ fD(ω). Next we show our algorithm achieves ϵ-differential privacy.

Theorem 2. Algorithm 1 satisfies ϵ-differential privacy.

Proof. Assume D and D′ are two neighbouring datasets. Without loss of generality, D and D′ differ in the last row tn and t′n . ∆ is calculated as Line 11 of Algorithm 1, and ¯ f(ω) is the output of Line 24. Φs (Φn) denotes the set of φ that does (does not) contain sensitive attribute ωs. The maximum difference of the objective function on D and D′ is then the maximum difference of coefficients introduced by tn and t′n . Adding Laplace noise to coefficients would produce the differentially private objective function. Specifically, we can add different magnitudes of noise to coefficients corresponding to φ ∈ Φn and those corresponding to φ ∈ Φs. γ is pre-determined as the ratio of such difference of noise magnitude. Formally, we have

Similarly, we have the formula for Pr( ¯ f (ω|D′ )).

Our algorithm needs to derive ∆, β1 and β2 to add noise with different magnitudes to the polynomial coefficients of sensitive attributes and non-sensitive attributes. Result 1 shows their derived formulas for linear regression and Result 2 shows for logistic regression. We can see they only involve the number of attributes d and the number of sensitive attributes k. As a result, they do not disclose any private information of the dataset D, which guarantees the rigorous ϵ-differential privacy. Due to space limitations, we only give the proof for linear regression in Result 1 and skip the proof for logistic regression in Result 2.

Result 1. For linear regression defined in Definition 1, assume there are k sensitive attributes among the total d input attributes. We have in Algorithm 1, ∆ = 2(d2 + 2d); β1 = d-k d and β2 = kd .

Proof. According to Equation 9, we have

where x(j) denotes the jth entry in vector x, which satisfies |x(j)| ≤ 1. Similarly, for the coefficients related to k sensitive attributes, we have

Result 2. For logistic regression defined in Definition 2, assume there are k sensitive attributes among the total d input attributes. Algorithm 1 can be applied with the approximate objective function ∑ni=1 1 8 (xTi ω)2 + ∑ni=1 ( 1 2 -yi)xTi ω based on Taylor expansion. We have ∆ = d2 4 + 3d and β1 = d-k d , β2 = kd .

4 Evaluation

In our experiments, we mainly focus on the problem of releasing the logistic regression model under differential privacy against model inversion attacks. We use the Adult dataset [Lichman, 2013] to evaluate the performance of Algorithm 1 and apply five-fold cross validation for all the accuracy calculation. The Adult dataset contains census information of 30,175 individuals with 14 attributes such as age, workclass, education, marital-status, hours-per-week and so on. The regression task is to predict whether the income of an individual is greater than 50K. Among the 13 input attributes, we pick marital status as the sensitive attribute which the model inversion attack would target.

Figure 1 shows how both the accuracy of the released model and the accuracy of the model inversion attack are affected by different ϵ values varying from 0.01 to 10. In this experiment, we do not differentiate the privacy budget for sensitive attribute and non-sensitive attribute. We can see from Figure 1(a) that the prediction accuracy of the regression model increases as ϵ increases and from Figure 1(b) that the accuracy of the model inversion attack on marital status also increases as as ϵ increases. This is not surprising because the larger ϵ is, the less noise introduced in the released model. Hence, the model has high utility but also incurs high risk under model inversion attacks. We can see even with small ϵ values such as 0.01, the model inversion attack still outperform random guessing based on the marginal probability (0.57 vs. 0.53) although the model utility is significantly lost.

In the second experiment, we set the privacy threshold ϵ = 1 and change the privacy budget ratio γ from {1, 0.5, 0.25, 0.1, 0.05, 0.025, 0.01}. Table 2 shows the corresponding ϵs and ϵn values under each γ. Note that these values can be easily derived from Result 2.

Figure 2 shows the accuracy trend of the model prediction task and the model inversion attack. We can see that the prediction accuracy of the released model generally stays stable. However, the accuracy of the model inversion attack shows a clear decreasing trend as γ goes small. For example, when γ is 0.01 or 0.025 , the model inversion attack would fail to beat random guessing based on the marginal probability; while the prediction accuracy of regression model can still stay higher than 75%. This result shows that our approach can significantly decrease the attribute privacy disclosure risk due to the model inversion attack while retaining the utility of the released regression model.

5 RelatedWork

Differential privacy research has been significantly studied from the theoretical perspective, e.g., [Chaudhuri and Monteleoni, 2008; Hay et al., 2010; Kifer and Machanavajjhala, 2011; Lee and Clifton, 2012; Ying et al., 2013]. There are also studies on the applicability of enforcing differential privacy in real world applications, e.g., collaborative recommendation [McSherry and Mironov, 2009], logistic regression [Chaudhuri and Monteleoni, 2008; Zhang et al., 2012], publishing contingency tables [Xiao et al., 2010; Barak et al., 2007] or data cubes [Ding et al., 2011], privacy preserving integrated queries [McSherry, 2009], synthetic graph generation [Wang and Wu, 2013; Mir and Wright, 2009; Sala et al., 2011], computing graph properties such as degree distributions [Hay et al., 2009] and clustering coefficient [Rastogi et al., 2009; Wang et al., 2012], and spectral graph analysis [Wang et al., 2013] in social network analysis. The mechanisms of achieving differential privacy mainly include the classic approach of adding Laplace noise [Dwork et al., 2006], the exponential mechanism based on the smooth sensitivity [McSherry and Mironov, 2009], and the functional perturbation approach [Chaudhuri and Monteleoni, 2008; Zhang et al., 2012]. Privacy preserving models based on differential privacy guarantee protection against attempts to infer whether a subject was included in the training set used to derive models. However, they are not designed to protect attribute privacy of a target individual when model inversion attacks are launched. In this paper, we have studied how to effectively prevent model inversion attacks while retaining model efficacy.

There are several studies that showed differential privacy still could leak various type of private information. In [Kifer and Machanavajjhala, 2011], the authors showed that when rows in a database are correlated, or when previous exact statistics for a dataset have been released, differential privacy cannot achieve the ultimate privacy goal - nearly all evidence of an individual's participation should be removed. The authors in [Cormode, 2011] showed that if one is allowed to pose certain queries relating sensitive attributes to quasiidentifiers, it is possible to build a differentially-private Naive Bayes classifier that accurately predicts the sensitive attribute. The authors [Dankar and El Emam, 2012] examined the various tradeoffs between interactive and non-interactive mechanisms and the limitation of utility guarantees in differential privacy. Another notable work [Lee and Clifton, 2012] studied the relationship of ϵ to the relative nature of differential privacy.

6 Conclusion and FutureWork

Recent work [Fredrikson et al., 2014] showed that the existing differential privacy mechanisms cannot prevent model inversion attacks while retaining desirable model efficacy. In this paper, we have developed an effective approach which simultaneously protects differential privacy of participants and prevents sensitive attribute disclosure of regular individuals from model inversion attacks while retaining the efficacy of released regression models. Leveraging the functional mechanism [Zhang et al., 2012], our approach rewrites the objective function in its polynomial representation and adds more (less) noise to the polynomial coefficients with (w/o) sensitive attributes. Our approach can effectively weaken the correlation between the sensitive attributes with the output to prevent model inversion attacks whereas retaining the utility of the released model by decreasing the perturbation effect on nonsensitive attributes. As a result, we still achieve ϵ-differential privacy for participants. In our future work, we will evaluate our research on real world applications such as clinical study which involves genetic privacy. We plan to theoretically analyze applicability of model inversion attacks under different background knowledge. We will explore other perturbation strategies to decrease utility loss under differential privacy and potential model inversion attacks.

Acknowledgments

The authors would like to thank anonymous reviewers for their valuable comments and suggestions. This work was supported in part by U.S. National Institute of Health (1R01GM103309).