E Bas

A Menafoglio

T Okhulkova

Polynomial Chaos Expansion for an Efficient Uncertainty and Sensitivity Analysis of Complex Numerical Models

In this work we address the problem of performing uncertainty and sensitivity analysis of complex physical systems where classical Monte-Carlo methods are too expensive to be applied due to the high computational complexity. We consider the Polynomial Chaos Expansion (PCE) as an efficient way of computing a response surface for a model of gas injection into an incompressible porous media aiming at assessing the sensitivity indices and the main distributional features of the maximal spread of the gas cloud. The necessity of an uncertainty study for such a model arises in case of CO2 storage risk assessment and is here performed by jointly using a numerical scheme to solve the system of partial differential equation (PDE) governing the model and the PCE method to efficiently simulate the physical system response by a meta-model. The performances of the PCE method and a standard MC approach are compared through an extended simulation study showing that the computational gain of the PCE approach is remarkable without significant loss in the precision of the estimates.

INTRODUCTION

The uncertainty quantification for a complex numerical model is an important goal for which significant challenges are yet to be achieved. In general, the uncertainty might be associated to several elements of the system such as input data measurements, parameter values, model structure, model solution algorithms and even human behavior. Therefore, the uncertainty assessment under a given cost might not be straightforward.

Most of the research efforts have been focused so far on the development of efficient algorithms to be used in different applications, assuming ideal input data measurements with precisely defined computational domains: to this end, for instance, Monte-Carlo approaches can be employed. However, the simulation of a large-scale system turns in computationally very heavy operations: thus the need of making the convergence to the solution faster naturally arises. The classical Monte-Carlo approach is used in such cases as the last resort. Another option is the perturbation method where all the stochastic quantities are expanded around the mean via Taylor series, nevertheless, it is limited to small perturbations and does not provide information on high-order statistics of the response. The expansion of the inverse of the stochastic operator in a Neumann series can be considered, but it is again limited to small fluctuations [START_REF] Shinozuka | Response variability of stochastic finite element systems[END_REF].

A more effective approach pioneered by [START_REF] Ghanem | Stochastic finite elements: a spectral approach[END_REF] in the context of finite element method is the Polynomial Chaos Expansion, which is a method based on a spectral representation of uncertainty. This idea comes from the theory about polynomial chaos by [START_REF] Wiener | The Homogeneous Chaos[END_REF][START_REF] Wiener | Nonlinear Problems in Random Theory[END_REF], which was firstly applied in the study of turbulence in the 1960s [START_REF] Meecham | Wiener-Hermite Expansion in Model Turbulence at Large Reynolds Numbers[END_REF][START_REF] Siegel | Wiener-Hermite Expansion in Model Turbulence in the Late Decay Stage[END_REF][START_REF] Meecham | Use of the Wiener-Hermite expansion for nearly normal turbulence[END_REF]. Nevertheless, its convergence rate was judged slow [START_REF] Orszag | Dynamical Properties of Truncated Wiener-Hermite Expansions[END_REF][START_REF] Crow | Relationship between a Wiener-Hermite expansion and an energy cascade[END_REF][START_REF] Chorin | Gaussian fields and random flow[END_REF]): hence, it did not receive much attention until the work of [START_REF] Ghanem | Stochastic finite elements: a spectral approach[END_REF]. A rich state of art with many applications can be found in [START_REF] Sudret | Stochastic finite elements and reliability: a state-of-the-art report[END_REF], Xiu and Karniadakis 2002, Xiu et al. 2002).

However, the availability of solid theoretical basis as well as efficient numerical codes (OpenTURNS 2012) for performing uncertainty analysis has recently contribute in making possible the sensitivity analysis of very complex systems [START_REF] Blatman | Efficient computation of global sensitivity indices using sparse polynomial chaos expansions[END_REF][START_REF] Sudret | Global sensitivity analysis using polynomial chaos expansions[END_REF][START_REF] Formaggia | Global sensitivity analysis through polynomial chaos expansion of a basinscale geochemical compaction model[END_REF][START_REF] Oladyshkin | An integrative approach to robust design and probabilistic risk assessment for CO 2 storage in geological formations[END_REF].

The main purpose of this work is to show how Polynomial Chaos Expansion (PCE) can be used for uncertainty and sensitivity analysis. In particular, we study as a specific application a model of gas injection into porous media, presented in Section 2. The theoretical basis of PCE is briefly introduced in Section 3. The validity of this approach is proved by simulation in Section 4: here, we first perform the sensitivity analysis on our model, then we compare the results of the analytical solution from available simplified model and the results of the Monte Carlo simulation.

INJECTION OF GAS INTO POROUS MEDIA

The predictive numerical model engaged in this study represents a two-phase flow of immiscible compressible fluids through incompressible porous medium. This model is developed in INERIS in order to estimate the intensity of physical processes in underground compartments in case of CO2 storage in a saline aquifer. The injected gas displaces water (initially in place) and simultaneous flow of the two fluids takes place in the porous medium. The model accounts for gravity, capillarity and fluid compressibility effects, and is formulated in terms of CO2 and water pressures. Empirical laws by [START_REF] Van Genuchten | A closed-form equation for predicting the hydraulic conductivity of unsaturated soils[END_REF] are used to close the system with the relations between capillary pressure, relative permeability and saturation.

The corresponding system of differential equations is solved within the software COMSOL (2012) in 2Daxisymmetric mode. The source (injection well) is concentric to the symmetry axis.

The upper and lower bounds of the reservoir are considered impermeable, therefore a "zero flux" boundary condition is used. On the bound along the injection well the debit of the gas phase is fixed, on the other side the boundary condition fluid pressures are fixed. The main configuration and the variable of interest are shown in Figure 1.

In Figure 1, p w and p nw [P a] are water and gas pressures respectively, C p [P a -1 ] the coupling term, θ w and θ nw the water and gas volume fractions, k rw and k rnw [-] the water and gas relative permeabilities; Q nw [m/s] represents the gas injection rate, K int [m 2 ] the intrinsic permeability, p w0 and p nw0 [P a] the initial water and gas pressures, ρ w and ρ nw [kg/m 3 ] the fluid densities, µ w and µ nw [P a • s] the fluid viscosities and, finally, χ w and χ nw [P a] are the fluid compressibilities.

The numerical solution of the system at time t = 10 years is finally shown in Figure 2. The uncertainty analysis as well as the sensitivity analysis which will be described in Section 4 are referred to this solution.

POLYNOMIAL CHAOS EXPANSION FOR SENSITIVITY ANALYSIS

Polynomial Chaos Expansion

Let y be the scalar output of a model that depends on the n-dimensional random vector x = (x 1 , ..., x n ) collecting n random parameters x i , valued in Ω i ⊆ R, i = 1, ..., n:

y = f (x), x ∈ Ω ⊆ R n , (1)
where Ω denotes the cartesian product

Ω 1 × • • • × Ω n .
Suppose x 1 , ..., x n to be statistically independent and the response y to be a second-order integrable variable: the PCE of y [START_REF] Maître | Spectral methods for uncertainty quantification[END_REF][START_REF] Ghanem | Stochastic finite elements: a spectral approach[END_REF], Xiu and Karniadakis 2002) is the spectral decomposition of f over a set of polynomials Ψ i (x), which are orthogonal with respect to the probability measure on Γ (i.e. the law of x), namely [START_REF] Sudret | Global sensitivity analysis using polynomial chaos expansions[END_REF]:

y = ∞ k=0 β k Ψ k (x).
(2)

The PCE was first introduced for Gaussian input parameters involving Hermite polynomials (e.g., [START_REF] Wiener | The Homogeneous Chaos[END_REF]). In the presence of non-Gaussian distributed variables, two strategies can be adopted in order to preserve the optimal exponential convergence rate: a) transform the input parameters to obtain Gaussian random entries b) consider other families of polynomials (Xiu andKarniadakis 2002, Soize and[START_REF] Soize | Physical systems with random uncertainties: Chaos representations with arbitrary probability measure[END_REF]. In this work, for every input parameter x i , i = 1, ..., n, a log-normal distribution ρ Γ i (x i ) is considered. In this case, the simplest way to reach the exponential rate of convergence is to use the Hermite basis, by transforming each input parameter x i into a standard normal random variable ξ i :

ξ i = Φ -1 (F x i (x i )), (3)
where Φ and F denotes the cumulative density function (CDF) of a standard Gaussian variable and of the variable x i respectively. Given the vector of transformed (independent) input parameters ξ = (ξ 1 , ..., ξ n ), the PCE can be computed as:

y = f (ξ) = ∞ k=0 β k Ψ k (ξ). (4)
For computation, expansion (4) needs to be truncated, obtaining finally an approximation of the response as: The P coefficients β k , k = 0, ..., P -1 appearing in (5) are assumed deterministic and fully characterize the randomness of the response y. In applications, these coefficients are unknown and thus need to be properly estimated. A number of methods are presented in the literature [START_REF] Sudret | Global sensitivity analysis using polynomial chaos expansions[END_REF][START_REF] Crestaux | Polynomial chaos expansion for sensitivity analysis[END_REF]; among them, in this work, the regression method is used. It consists in estimating β k by least-squares on the basis of an experimental design {y j , j = 1, ..., N }. The experimental design is built by collecting N exact solutions y j , j = 1, ..., N , which are derived solving the complete mathematical model for N realizations x j , j = 1, ..., N , of the random input x. The least-squares estimate of β = (β k ) ∈ R P is found by solving the minimization problem:

y ≈ P -1 k=0 β k Ψ k (ξ), (5)
β = argmin β 0 ,...,β P -1 ∈R 1 N N j=1 y j - P -1 k=0 β k Ψ k (ξ j ) 2 , (6) being ξ j = (Φ -1 (F x i (x i ))). If the design matrix Ψ = (Ψ j (ξ i )) ∈ R N,P is of full rank, problem (6) admits the unique solution β: β = (Ψ T Ψ) -1 Ψ T y, (7)
where y = (y 1 , ..., y N ). Techniques for an efficient computation of coefficients estimates ( 7) has been presented in the literature (e.g., [START_REF] Sudret | Global sensitivity analysis using polynomial chaos expansions[END_REF]) and are exploited in the simulations here presented.

The utility of PCE for the uncertainty analysis of the response is two-fold:

• Response mean and variance can be directly obtained from (5) as:

E[y] = β 0 ; Var(y) ≈ P -1 k=0 β 2 k ψ k 2 .
Analogously, the sensitivity Sobol' indices can be computed directly from coefficients β k , k = 0, ..., P -1 (see Subsection 3.2)

• The approximation (5) can be used as metamodel for Monte-Carlo simulations (i.e., the response is simulated through the approximate model instead of solving the PDE system). This allows to perform a much more efficient assessment of the CDF as the approximated model is easier to simulate compared to the full model (1).

Sensitivity Analysis through Sobol Indices

Sobol' indices [START_REF] Sobol | Sensitivity estimates for nonlinear mathematical models[END_REF]) will be used in Section 4 to perform the sensitivity analysis on the response. The total variance of the response can be decomposed into the effect of each random parameters x j and the joint effects of all the subsets x i 1 , ..., x is of the input parameters x 1 , ..., x n . As stated in [START_REF] Sobol | Sensitivity estimates for nonlinear mathematical models[END_REF][START_REF] Sudret | Global sensitivity analysis using polynomial chaos expansions[END_REF][START_REF] Formaggia | Global sensitivity analysis through polynomial chaos expansion of a basinscale geochemical compaction model[END_REF], this variance decomposition follows from the Sobol' decomposition of the function f (ξ) which appears in (4):

f (ξ) = f 0 + N i=1 f i (ξ i ) + N i,j=1 f i,j (ξ i , ξ j )+ (8) + • • • + f 1,2,...,n (ξ 1 , ξ 2 , . . . , ξ n ),
where

f 0 = Γ f (ξ)ρ Γ (ξ)dξ, f i (s) (ξ i (s) ) = Γ -i (s) f (ξ)ρ Γ -i (s) (ξ -i (s) )dξ -i (s) - I⊆i (s) f I denoting with i (s) the multi-index {i 1 , . . . , i s }, with ξ i (s) the collection {ξ i 1 , ..., ξ is }, with ρ Γ = n i=1 ρ Γ i the multivariate gaussian density of ξ, Γ -I = × i∈{1,...,N }\I Γ i and ρ Γ -I = i∈{1,...,N }\I ρ Γ i .
Notice that in the considered case Γ i = R, i = 1, . . . , n, but what follows remains valid for any measurable Γ i ⊆ R. In particular, decomposition ( 8) is unique whenever f is integrable over Γ and each term f i (s) in ( 8) is orthogonal with respect to the others.

To define the Sobol' indices, call V f , V f the variance of f , f respectively. The Sobol' index relative to the mixed effect ξ i (s) (or to x i (s) ) is defined as:

S i (s) = 1 V f Γ i (s) f 2 i (s) (ξ i (s) )ρ Γ i (s) dξ i (s) , (9)
where

Γ i (s) = Γ i 1 × • • • × Γ is . Hence, S i (s)
represents the proportion of the total variance explained by ξ i (s) (or x i (s) ) and thus the Sobol' indices sum to 1.

Concerning the total effect of a parameter ξ i (x i ) (or of x i ) on the total variability, it can be computed directly from Sobol' indices as:

S T i = i (s) :i∈i (s) S i (s) . (10)
The computational effort needed to compute the sensitivity indices ( 9) and (10) consists mainly in the cost of calculating (numerically) 2 n -1 integrals. To this end, Monte-Carlo quadrature schemes can be used but, due to its low rate of convergence, the computational cost might become unaffordable. However, this problem can be faced and solved by introducing the PCE of the response y, since Sobol' indices can be directly computed from coefficients β k , k = 0, ..., P -1. Indeed, expansion (5) can be reordered so that it is equivalent to (8):

f (ξ) = i (s) ⊆{1,...,n} k∈K i (s) β k Ψ k (ξ), (11)
where

K = {0, . . . , P -1}, K i (s) = {k ∈ K| Ψ k (ξ) = Ψ k (ξ = ξ i (s) )} (Crestaux et al. 2009).
From the equivalence between ( 4) and ( 11) the bijective relation existing between Sobol indices and coefficients β k , k = 1, ..., n can be derived. Indeed, the PC-based Sobol' indices can be obtained as:

S i (s) = k∈K i (s) β 2 k Ψ k , Ψ k P -1 k=0 β 2 k Ψ k , Ψ k
, being i (s) ⊆ {1, . . . , n}, while the total indices can be computed from (10).

SIMULATION AND RESULTS

After a preliminary study on the analytical model, the following four input parameters of the model have been considered: the maximal relative gas permeability kr max [-], the reservoir thickness H[m], the reservoir total porosity φ [-] and the irreducible water saturation (or maximal gas saturation Snw max [-]). These four parameters form the random vector x appearing in (1): x = (kr max , H, φ, Snw max ). In this study the log-normal probability density function is attributed to each parameter.

The response variable which is of interest for the sensitivity analysis is the natural logarithm of the maximal spread of the gas cloud, ln(r max ). Once a set of input parameters x 0 = (kr 0 max , H 0 , φ 0 , Snw 0 max ) is fixed, the corresponding ln(r 0 max ) can be calculated by numerically solving the system of partial differential equation governing the model (Figure 1). The solution includes the saturation 2D profile for any time step: ln(r 0 max ) is calculated as the maximum horizontal extension of the 0.99 saturation contour. The numerical solution of the system for a given set of parameters requires 5.67 minutes on a personal computer (4 CPU Xeon E31245 3.30GHz, RAM 16GB).

The experimental design In order to determine the least-square estimate of vector β as in ( 6), an experimental design {ln(r j max ), j = 1, ..., N } of size N = 100 has been considered. The number of replications N has been tuned by balancing the computational cost and the precision in least square estimate: the higher N is, the higher either the precision in estimating β or the computational cost are. In particular, the computational cost spent for generating an experimental design of size N on a personal computer with the technical characteristic specified before is about 5.67 • N minutes (O(N )), which corresponds to 9 hours and 27 minutes in the considered scenario.

In order to justify the choice of N , a preliminary study has been performed on the analytical model corresponding to the simplified physical problem presented in [START_REF] Nordbotten | Similarity solutions for fluid injection into confined aquifers[END_REF], for which the exact expression of the response distribution can be computed. In Figure 3 the empirical CDF of the output samples on which the meta-model is built (solid green line) is compared to the exact CDF calculated (c) N = 1000 analytically (dashed blue line), for N = 50, 100, 1000 (subfigures (a), (b) and (c) respectively). Even the meta-model built out of 50 samples reproduces the response variability quite closely; for N = 100 the approximation is very accurate without showing significant gains with respect to N = 1000. Therefore, a reasonable value for the parameter N is N = 100: this choice seems to balance the most the precision in the CDF estimate and the corresponding computational cost.

Supported by these results, the PCE on the gas injection model -detailed in Section 2-has been performed on the basis of an experimental design of size N = 100 (Figure 4). In Figure 4 the N = 100 realizations of the (log-transformed) response r max are represented against the parameters kr max , H, φ and Snw max , superimposing the corresponding least squares lines. The slope of the regression line is positive in the case of parameters kr max , while it is negative for H, φ and Snw max . This result can be expected from the point of view of the physical model: the higher the relative permeability of the gas is, the further it can penetrate, that is why the first correlation is positive. Concerning the other three parameters, the correlation is negative. Indeed, the increase of the reservoir height is not favorable for the horizontal spread. Increasing the porosity and maximal gas saturation leads to a bigger fraction of gas staying in place after the front passage, which means that for the same injected volume the maximal horizontal extension would be smaller.

PCE expansion and sensitivity analysis

The coefficients to be included in PCE has been selected following the sparse PCE approach proposed in (Blatman and Sudret 2010, [START_REF] Blatman | Adaptive sparse polynomial chaos expansions for uncertainty propagation and sensitivity analysis[END_REF]. Having fixed the maximum degree p of Hermite polynomials to p = 4, the 15 coefficients β 0 , β 1 , β 2 , β 3 , β 4 , β 5 , β 7 , β 9 , β 15 , β 18 , β 20 , β 38 , β 40 , β 48 , β 58 , proved to be significant for the expansion. Only the first 5 coefficients are reported in Table 1, since the other coefficients proved unstable when replicating the simulations. Noticed that coefficients β 1 , β 2 , β 3 , β 4 reflects the behav- These estimates are coherent with a standard Monte Carlo simulation: indeed, 1000 Monte Carlo simulation provides an estimate of 7.2197 for the mean (error: 0.05%), and of 0.0863 for the standard deviation (error: 0.9%)).

In order to assess the uncertainty propagation through the system, Sobol' indices have been computed by using ( 11) and ( 10); the results are reported in Table 2. According to Sobol' total indices (Table 2, second column), the parameters which seem to influence the most the response variability are the reservoir total porosity Φ and the maximal gas saturation Snw max , whose variability explains about 31.0% and 29.8%, respectively, of the output variability. The remaining variability is explained in decreasingly order of importance by maximal relative gas permeability kr max (20.2%) and reservoir thickness H (18.2%). Very similar conclusions can be drawn by considering the Sobol' indices reported in the first column of Table 2, meaning that the influence of the input parameters on the output is mainly due to single effects, while mixed effects play a minor role.

To access the uncertainty in the estimated statistics, the simulation has been replicated with the same settings starting from different seeds. The results are 3. It can be noticed that the response mean and standard deviation seem precisely estimated. Instead, the parameters affected by the most significant variability are the Sobol' indices relative to the reservoir thickness H and to the maximal gas saturation Snw max -either the indices relative to the single effects or the total indices-. Notice also that the coefficients β k selected by the sparse PCE approach varied by replicating the simulation, with only the first five coefficients steadily selected. However, both the variability in the PCE estimates and in the selected coefficient do not seem to significantly affect the conclusions previously drawn about the uncertainty propagation through the system.

Assessing the response distribution function Although Sobol' indices provide an important tool for sensitivity analysis, in this study the whole CDF is of interest. Generally, CDF can be estimated in three ways: (a) analytical calculation (b) standard MC simulation (c) meta-model MC simulation -i.e., generation of an experimental design of size N by a standard MC-simulation on the complete model, computation of the β coefficients in approximation ( 5) and finally MC simulation on the meta-model exploiting the same approximation-. The main drawback of method (a) is that an analytic form of response CDF is rarely available; on the other hand the computational cost of a standard MC simulation on a complex model as the one considered here increases fast with the number of samples required (more than 94 hours for 1000 samples). Notice in particular that a preliminary MC simulation is needed when using method (c), but a fair size of the experimental design is typically much smaller than the number of simulations required to assess the complete CDF with method (b).

To evaluate the performance of methods (b) and (c) when the analytical form of the CDF is available, the simplified gas-injection model has been again considered. In Figure 5 the following CDFs are compared: 1) exact CDF -method (a), dashed blue line-; 2) empirical CDF obtained by 1000 standard MC-simulations -method (b), green line-; 3) empirical CDF obtained by 10000 PCE-based meta-model simulations having an experimental design of size 100 -method (c), red line-. The parameters of the latter simulation have been chosen according to the feasibility of an analogous simulation on the complete gas injection model: indeed, the computational cost of the MC-simulation on the complete model soon becomes unaffordable as the sample size increases and the simulation of 1000 samples already requires more than 94 hours 1 .

The empirical CDFs obtained with the two methods are pretty similar to the exact CDF, but more accurate and smooth results are obtained for PCE-based simulations, being based in fact on a rich meta-model MC sample. Figure 6 represents the statistical moments of the response. Notice that the meta-model reproduces exactly the even statistical moments even when it is build on a small size of the experimental design. Theoretically being zero, the odd statistical moments seem to be better approximated for metamodels based on a larger size of the experimental design. Observe that the time consumption required for computing the meta-model estimate is essentially due to the computation of the experimental design. Therefore the very low additional cost required for the PCE step turns in a much more accurate CDF estimate.

Supported by these results, methods (b) and (c) have been applied on the full numerical model of gasinjection detailed in Section 2. The response empirical CDF computed by 1000 standard Monte Carlo simulations (blue dotted line) and with a PCE-based meta-model simulation (red line) are presented in the left panel of Figure 4, superimposed to the results of the replicated simulations (grey lines). It has to be noticed that the results are fairly stable among the replicates, as the lines seems perfectly superimposed. This supports the conclusion previously drawn about the stability of the results with respect to the variability in the selected coefficients and their estimates. Moreover, all the empirical CDF are very close to the MC results obtained from the full model.

In order to appreciate the most the existing differences among the obtained estimates, the right panel of Figure 4 reports the kernel density PDF estimates computed as before from the MC sample, the metamodel sample and the replicates. Replicates have been built either with the same parameters (darker lines), or by fixing the maximum degree of Hermite polynomials to p = 5. Although some differences are now appreciable, all the meta-model curves appear very similar each other and very close to the MC estimates. The main difference is present in the right tail of the distribution, where a slight underestimation occurs. However, the meta-model PDF estimates provides a very good approximation of the MC PDF estimates obtained in less than 10 hours against the 94 hours required by the full MC-simulation.

Finally, Figure 8 shows the statistical moments of the resulting response distributions. All the replicates 1 4 CPU Xeon E31245 3.30GHz, RAM 16GB seem to provide similar results, that are close to the MC estimate. No significant gains are reached if increasing the maximum degree of the Hermite polynomials. The first two moments of the distribution, in particular the mean, are very precisely estimated, as already noticed when analyzed Table 3. Increasing uncertainty is observed when increasing the order of the estimated moments. As in the simplified model, the uncertainty in the estimates is higher for even order moments, while odd moments are more accurately estimated.

CONCLUSION

In this work, the Polynomial Chaos Expansion method as an efficient technique for performing uncertainty and sensitivity analysis of complex numerical models has been investigated. In particular, the potentiality of this approach has been explored in terms of computational efficiency when dealing with a model of gas injection into porous media. The regularity of the response for this particular physical model is favorable for the use of the described method.

The crucial points encountered while performing PCE on a real system have been underlined. For instance, one need to pay close attention when making the choice of the size of the experimental design used for estimating the expansion coefficients and the basis functions form. The minimal size is dictated by the number of coefficients in the decomposition, further validation of the meta-model quality can only be done by experience in every particular case. Here, the size of the experimental design has been fixed by exploiting the information coming from the application of the same technique to a simplified model, but other considerations -e.g., in terms of variance of the estimate-can be made.

A great deal of attention has been focused on the computational gain of the PCE approach, which is very significant for the considered application: while obtaining the response PDF by 1000 standard Monte Carlo simulation takes more than 94 hours, with a PCE approach the computational cost is reduced to less than 10 hours.

However, the robustness of the procedure with respect to the size of the experimental design would be worth being further investigated. Indeed, by repeating the simulations with a different size of the experimental design, the coefficients estimate might significantly vary, with possible effects on the Sobol' indices and on the consequent sensitivity analysis. Although this does not seem to be the case, in order to avoid this problem, a direct control on the estimates variance should be considered, in particular if no 'a priori' information is available on the response distribution.

A further development regarding the considered physical model, which might be of industrial and physical importance, is to consider a space-time varying response, such as the water and gas pressure, while analyzing the propagation of the uncertainty from the input parameters to the space-time random field described by the response. In such a complex setting, the use of PCE could make the computational cost of performing uncertainty and sensitivity analysis affordable, which is a very important goal to be reached for this kind of complex numerical systems.

ACKNOWLEDGMENT

The authors would like to thank the organizers of ISRI seminar. Without their effort for bringing researchers from different disciplines together, this work would not have been possible. The event is organized under the companion of Supélec, École Centrale and Politecnico di Milano. The authors also thank MSS-Mat laboratory for providing the numerical resources and technical support. The work of E. Bas ¸tug has been supported by Alcatel Lucent Chair on Flexible Radio and the ERC Starting Grant 305123 MORE (Advanced Mathematical Tools for Complex Network Engineering).

Figure 1 :

 1 Figure1: Specification of the problem: the vertical section of the domain and the system of differential equations entered in Comsol Multiphysics.

Figure 2 :

 2 Figure 2: Numerical solution of the system for t = 10 years. The color mapping shows the water saturation level. -2350 -2380 -2410 -2440 -2470 1.00 0.75 0.50 0.25 0.00 0 300 600 900 1200 depth (meter) horizontal distance from the injection well (meter)

Figure 3 :

 3 Figure3: Comparison of the meta-model CDF (red line) with the exact CDF (dashed blue line) and with the empirical CDF of the samples used for the meta-model construction (green line). The figures correspond to the analytical solution with varying number of the samples for PCE decomposition, from left to right: 50 samples (first panel), 100 samples (second panel), 1000 samples (third panel).

  Figure 4. Afterward, the estimates of the first two moments of the response probability density function (PDF) have been derived by using (5), obtaining: E[ln(r max )] ≈ 7.2157 sd[ln(r max )] ≈ 0.0871.

Figure 4 :

 4 Figure 4: Experimental design. From left to right: plot of r max against kr max (first panel), H (second panel), φ (third panel) and Snw max (fourth panel).

  Figure 5: Comparison of the meta-model CDF obtained with an experimental design of size N = 100 (red line) with the exact CDF (dashed blue line) and with the empirical CDF obtained with 1000 standard MC-simulations (green line)

Figure 7 :

 7 Figure 7: Response CDF (left panel) and kernel density estimated PDF (right panel) for: 1000 standard Monte Carlo simulation (dotted blue line), meta-model simulation through PCE (solid red line), replicated meta-model simulation (dark grey lines).

Figure

  Figure 8: Comparison of the statistical moments for: 1000 standard Monte Carlo simulation (dotted blue line), meta-model simulation through PCE (solid red line), replicated meta-model simulations when the maximum degree of the Hermite polynomials is p = 4 (light grey lines) and p = 5 (solid grey lines).

Table 1 :

 1 Estimates of the decomposition coefficients

	Parameter Estimate
	β 0	7.2157
	β 1	0.0387
	β 2	-0.0370
	β 3	-0.0485
	β 4	-0.0475
	ior previously noticed by inspecting

Table 2 :

 2 Sobol' indices

	Parameter Sobol' index Sobol' total index
	kr max	0.2019	0.2098
	H	0.1823	0.1884
	Φ	0.3102	0.3177
	Snw max	0.2977	0.2990

Table 3 :

 3 Mean, standard deviation and coefficient of variation relative to the estimated indices.

		Mean	Sd	C.V.
	E[ln(r max )] 7.2151 0.0020 2.8e-4
	sd[ln(r max )] 0.0861 8.5e-4 0.0099
	S krmax	0.2026 0.0087 0.0431
	S H	0.1640 0.0179 0.1091
	S Φ	0.3119 0.0104 0.0335
	S Snwmax	0.3149 0.0214 0.0681
	S T krmax S T H S T Φ S T Snwmax	0.2079 0.0082 0.0395 0.1701 0.0236 0.1384 0.3159 0.0100 0.0318 0.3168 0.0192 0.0608
	reported in Table


The Role of Signal Processing in meeting Cyber-Security and Privacy Challenges Lalitha Sankar, Wade Trappe, Kannan Ramachandran, H. Vincent Poor, and Mérouane Debbah

I. INTRODUCTION: INFORMATION LEAKAGE EVERYWHERE

We are in an era where computing and communication technologies are an integral part of our lives.

Our environment is becoming increasingly more cyberphysical, with sensors and actuators exchanging information through a variety of networks. We access information from the cloud, share information with each other on social networks, and synthesize new information all while we are on-the-go. Storage technologies have also evolved significantly, with data density and access speeds projected to continue to increase dramatically over the next decade. The confluence of these technologies is leading to huge volumes of data flowing across our networks, to and from computers where they will be analyzed, and deposited into vast databases for later retrieval. The huge quantities of data poses new societal risks that are just now starting to manifest. Users post information on social networks unaware of the privacy risks they face; companies submit information to the cloud for processing to reduce their own computing costs yet unaware that potentially sensitive information might be leaked; sensor networks and global positioning systems monitor the state of our roads and vehicles yet reveal where we are driving to/from and even why.

Although some of these systems might be protected using conventional cryptographic protocols, many of them cannot and many of the risks exist outside the realm of protection offered by a cipher suite.

For example, once information has been decrypted and placed into a database in plaintext it loses the confidentiality provided by the secure socket that connected the originating client to the database. Now, not only does the owner of that database know the exact value of that data, but it can examine the entirety of data it holds in order to glean information beyond the scope of the information provided.

To protect data from unforeseen security and privacy breaches, we should revisit information security and privacy from a fundamental point of view and search for techniques that complement traditional cryptographic services. Although conventional cryptographic protocols and services can and must be a part of the solution to ensuring data security and privacy, such techniques do not reflect the full spectrum of techniques available to protecting information. In particular, information is associated with a particular [START_REF] Dalenius | Finding a needle in a haystack -or identifying anonymous census records[END_REF] DRAFT context and has value to its users, and these notions of context and utility serve as the basis for formulating signal and information processing techniques that can enhance or complement traditional security/privacy services.

Whether one considers traditional network and computer security mechanisms, or complementary techniques for data protection that employ signal and information-theoretic mechanisms, there are several common classes of security threats that one expects to encounter. For example, in network communications an eavesdropper might listen on communications to gain access to restricted information, or the adversary might manipulate specific data fields to falsify data or instructions. Similarly, in cloud storage applications the adversary might be the storage service itself and attempt to glean unintended information from its repositories that was meant to remain private, or a user might inject false information into the database repository in hopes of harming the utility of the database to others as illustrated in Figure 1. At a highlevel there are several major goals that can help address in order to better protect information. Three of these objectives, which correspond to the traditional "C-I-A" security framework, are described below, where we have outlined how signal processing techniques can have a direct impact.

• Confidentiality: Confidentiality is a guarantee that only those entities intended to access information January 15, 2013 DRAFT or data should be able to access that information. In communications, this might involve a guarantee that the information exchanged in a protocol is only able decipherable by legitimate entities. In database applications, where the data from many users might be stored together, confidentiality involves encrypting the data and managing the keys needed to access and decrypt the data.

• Integrity: Integrity is a guarantee that a system or data is consistent with its purpose or how it is expected to be shared. For example, in communications, integrity might involve algorithms (e.g., cryptographic checksums) that ensure that data or messages have not been altered, or provide assurance that the data came from its claimed origin. In network and computer systems, integrity corresponds to ensuring that the system is operating correctly and that anomalous events can be rapidly detected and defended against. Similarly, in database and data-driven applications, it is desirable to ensure that stored or actuated upon data is correct and consistent with physical reality.

• Availability: The goal of availability is to ensure that system resources, such as stored data or services, are accessible to entities when legitimate service requests are made. In the context of communications and network services, this might correspond to ensuring protecting against denial of service attacks, while in computer systems this involves guaranteeing that if an entity has privileges for specific set of objects/services then that access should not be obstructed.

Confidentiality as a security goal is particularly tricky to categorize since it can involve issues such as preventing an eavesdropper from learning specific information, ensuring that various contexts surrounding data is preserved, and that the combination of several distinct pieces of data, when put together, do not allow an adversary to infer other information that was not meant to be inferred. For the sake of clarity, in this paper we shall specifically call out two different flavors of confidentiality: secrecy, which is concerned with ensuring that specific information cannot be received/deciphered by well-defined and untrusted adversaries external to the system (e.g. eavesdroppers), and privacy which involves ensuring that unintended information is not revealed (via inference and correlations) when intended data is shared with legitimate users.

In this article, we shall examine signal and information processing techniques that can be used to protect information. We begin in Section II by identifying several information-theoretic (IT) themes that have emerged across many emerging cyber-security and privacy problems. After identifying these basic themes, we then explore in detail how signal processing techniques that are motivated by IT principles can be applied to address emerging privacy problems.

January 15, 2013 DRAFT

II. AN INFORMATION-PROCESSING PERSPECTIVE OF SECURITY

Security and privacy, at a high-level, involves making certain that an adversary does not know the correct value or meaning behind information being shared and that the adversary cannot alter or affect the data or a system in a manner that is not allowed by legitimate parties.

Let us generically label an original piece of data as X, which may correspond to a communications signal or to N different fields in a database or to an N -dimensional data vector measured by a cyberphysical sensor system. The confidentiality objective, whether secrecy or privacy, involves applying a transformation on X to create a new information Y vector from which it is difficult for an adversary to answer questions about X or even infer X itself. For example, in conventional cryptography, Y corresponds to ciphertext that is the result of an encryption algorithm being applied to X. In general, some form of advantage should exist between the legitimate parties (Alice and Bob) over the adversary (Eve).

For conventional cryptography, this advantage takes the form of Alice and Bob sharing an encryption key unknown to Eve. In many settings, it is possible to find other sources of advantage that Alice and Bob share over Eve. For example, there has been recent work in the physical layer security community, where the properties of the (wireless) communications is exploited for secrecy. This area of research is well-grounded in IT principles [START_REF] Wyner | The wire-tap channel[END_REF], [START_REF] Csiszar | Broadcast channels with confidential[END_REF], and the body of work suggests an intuitive strategy for achieving secret communications: one should develop methods that ensure that the Alice-Bob channel effectively has higher quality than the Alice-Eve channel.

However, since many of these methods are analogous to mechanisms employed in privacy, we briefly give our own interpretation of signal and information processing strategies that may be used to enhance confidentiality. Later, in Section III, we commence with exploring such methods in more detail in terms of privacy where the goal is to ensure that unintended information is not revealed to legitimate users.

• Perturbing Data: A natural approach to protecting the true data value is to introduce a perturbation to the data by adding random noise. Such an approach has been applied, for example, in the database privacy community [START_REF] Aggarwal | On the design and quantification of privacy preserving data mining algorithms[END_REF], where one attempts to design a noise distribution so as to obscure the original data distribution while preserving certain aggregate metrics (e.g. data average). Another area where perturbation is applied is in secret communications, where legitimate parties design interference signals so as to best disrupt an eavesdropper's ability to listen on communications [START_REF] Liang | Secure communication over fading channels[END_REF]. In both cases, confidentiality becomes a problem in signal design and signal processing techniques can be applied.

• Altering Data Precision: Data has utility that is directly related to its precision. In many situations, it is possible to exploit the different valuations that legitimate users have in the data. For example, January 15, 2013 DRAFT a legitimate user might only need coarse-grained information, while an adversary might only derive value and infer on fine-grained information. In such scenarios, it is possible to quantize the data to a level coarser than originally measured [START_REF] Gruteser | Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking[END_REF]. Such techniques arise in problems like location privacy,

where coarse-grained position information is released to a location-service.

• Data Aggregation: Another approach is to amass a collection of information and, rather than report all of the data, merely report an aggregation of that data. For example, a location-based service might choose to reveal that a group of users is at a specific location (e.g. a specific office) or that an individual is at a vague location (e.g. a shopping mall as opposed to a specific store), but would not reveal that a specific individual is at a specific location [START_REF] Gruteser | Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking[END_REF]. Similar techniques have been employed

in Web services, such as in [START_REF] Reiter | Crowds: anonymity for web transactions[END_REF], where users are gathered into geographically diverse groups to make it difficult to identify who is initiating a Web request. In all of these cases, techniques from signal and information fusion can be used to formulate the tradeoff between privacy and data utility.

Moving beyond confidentiality, integrity also involves examining X to decide whether X corresponds to a valid situation. For example, we might want to decide whether temperature data from a thermistor used in a smart home is correct. It is clearly unreasonable to accept a temperature reading of 10000 Kelvin.

Similarly, in network anomaly detection, X might correspond to traffic statistics measured over a period of time and we might wish to infer whether X corresponds to an acceptable operational condition for the network, or whether X flags anomalous activities [START_REF] Liu | ALDO: An Anomaly Detection Framework for Dynamic Spectrum Access Networks[END_REF]. As a final example, we might have data being inserted by a malicious entity into a database or into cloud storage that will be accessed by a wide array of users. In such situations, it is often desirable for the database service to sanitize the database of false or outlier data. In any of these cases, a general signal or information processing approach to assuring the integrity of information or a system involves formulating the integrity problem using a statistical hypothesis testing framework. Specifically, hypothesis checking involves determining whether X falls inside or outside of a region of validity Ω. If the data falls in the valid region, the null hypothesis H 0 is verified and thus the data/system integrity is validated. On the other hand, unreliable data is classified as H 1 , and the system integrity is deemed suspect or compromised.

III. PROTECTING PRIVATE INFORMATION

While security mechanisms address the problem of external hackers and eavesdroppers, guaranteeing the privacy of individuals and organizations whose data is being transferred across networks and stored in distributed repositories requires different tools to protect contextual information from being gleaned by potential insider inference.

January 15, 2013 DRAFT

There are many application scenarios where the issue of privacy arises and unfortunately the traditional approach to developing privacy solutions for these applications involves application-specific solutions that are often heuristic and generally disconnected from a formal theoretical foundation that quantifies the privacy benefits. These different applications, whether they correspond to smart grids or medical records, can all benefit from a unifying framework that allows a privacy engineer to build solutions where the privacy benefits can be explored with well-understood utility tradeoffs, first introduced and developed in .

In this section, we begin by outlining a unified approach to understanding privacy and application utility.

This model is based on IT principles introduced and developed in [START_REF] Sankar | A theory of privacy and utility in databases[END_REF]. Following the model presentation,

in Section IV we illustrate how this model can be used to motivate the application of signal processing techniques to reliably support information privacy.

A. A Unifying Analytical Model

Our privacy model involves datasets (e.g. databases or communication packets/signals) with K attributes per entry/occurrence. For the remainder of this discussion, we shall simplify our discussion to refer to these datasets as databases. Our proposed model focuses on large databases with K attributes per entry.

Let X k , for all k ∈ K = {1, 2, , . . . , K}, and Z be finite sets. Let X k ∈ X k be a random variable denoting the k th attribute, k = 1, 2, . . . , K, and let X K ≡ (X 1 , X 2 , . . . , X K ). A database d with n rows is a sequence of n independent observations from a source having a probability distribution

p XK (x K ) = p X1X2...XK (x 1 , x 2 , . . . , x K ) (1)
which is assumed to be known to both the designers and users of the database. Our simplifying assumption of row independence holds generally in large databases as correlation typically arises across attributes and can be ignored across entries given the size of the database. We write X n K = (X n 1 , X n 2 , . . . , X n K ) to denote the n independent and identically distributed (i.i.d.) observations of X K .

The joint distribution in (1) models the fact that the attributes corresponding to an individual entry are correlated in general and consequently can reveal information about one another.

Public and private attributes:

We consider a general model in which some attributes need to be kept private while the source can reveal a function of some or all of the attributes. We write K r and K h to denote sets of private (subscript h for hidden) and public (subscript r for revealed) attributes, respectively, such that K r ∪ K h = K ≡ {1, 2, . . . , K}. We further denote the corresponding collections of public and private attributes by X Kr ≡ {X k } k∈Kr and X Kh ≡ {X k } k∈Kh , respectively.

Our notation allows for an attribute to be both public and private; this is to account for the fact that a database may need to reveal a function of an attribute while keeping the attribute itself private. In [START_REF] Dalenius | Finding a needle in a haystack -or identifying anonymous census records[END_REF] DRAFT general, a database can choose to keep public (or private) one or more attributes (K > 1). Irrespective of the number of private attributes, a non-zero utility results only when the database reveals an appropriate function of some or all of its attributes.

Revealed attributes and side information: The public attributes X Kr are in general sanitized/distorted prior to being revealed in order to reduce possible inferences about the private attributes. We denote the resulting revealed attributes as XKr ≡ { Xk } k∈Kr . In addition to the revealed information, a database user can have access to correlated side information from other information sources. We model the side information as an n-length sequence Z n = (Z 1 , Z 2 , . . . , Z n ), Z i ∈ Z for all i, which is correlated with the database entries via a joint distribution p XKZ (x K ,z).

Reconstructed database: The final reconstructed database at the user will be either a database of revealed public attributes (when no s.i. is available) or a database generated from a combination of the revealed public attributes and the side information (when s.i. is available).

B. The Privacy and Utility Principle

Even though utility and privacy measures tend to be specific to the application, there is a fundamental principle that unifies all these measures in the abstract domain. The aim of a privacy-preserving database is to provide some measure of utility to the user while at the same time guaranteeing a measure of privacy for the entries in the database.

A user perceives the utility of a perturbed database to be high as long as the response is similar to the response of the unperturbed database; thus, the utility is highest of an unperturbed database and goes to zero when the perturbed database is completely unrelated to the original database. Accordingly, our utility metric is an appropriately chosen average 'distance' function between the original and the perturbed databases. Privacy, on the other hand, is maximized when the perturbed response is completely independent of the data. Our privacy metric measures the difficulty of extracting any private information from the response, i.e., the amount of uncertainty or equivocation about the private attributes given the response [START_REF] Yamamoto | A source coding problem for sources with additional outputs to keep secret from the receiver or wiretappers[END_REF], [START_REF] Sankar | A theory of privacy and utility in databases[END_REF]. This basic principle and the resulting mappings from the application to the analysis (abstract) domain are summarized in Table I.

C. A Privacy-Utility Tradeoff Model

Since database sanitization is traditionally the process of distorting the data to achieve some measure of privacy, it is a problem of mapping a database to a different one subject to specific utility and privacy requirements. Mapping: Our notation below relies on this abstraction [START_REF] Sankar | A theory of privacy and utility in databases[END_REF]. Let X k , k ∈ K, and Z, be as above and let Xj be additional finite sets for all j ∈ K r . Recall that a database d with n rows is an instantiation of X n K . Thus, we will henceforth refer to a real database d as an input database and to the corresponding sanitized database (SDB) d s as an output database. When the user has access to side information, the reconstructed database d ′ at the user will in general be different from the output database.

Our coding scheme consists of an encoder F E which is a mapping from the set of all input databases (i.e., all databases d allowable by the underlying distribution) to a set of indices J ≡ {1, 2, . . . , M } and an associated table of output databases (each of which is a d s and has a one-to-one mapping to J ) given by

F E : (X n 1 × . . . × X n k ) k∈Kenc → J ≡ {SDB k } M k=1 (2)
where K r ⊆ K enc ⊆ K and M is the number of output (sanitized) databases created from the set of all input databases. To allow for the case where an attribute can be both public and private, we allow the encoding F E in (2) to include both public and private attributes. A user with a view of the SDB (i.e., an index j ∈ J ) and with access to side information Z n , whose entries Z i , i = 1, 2, . . . , n, take values in the alphabet Z, reconstructs the database d ′ via the mapping

F D : J × Z n → k∈Kr X n k . (3)
The encoding and decoding are assumed known at both parties.

Utility: Relying on a distance based utility principle, we model the utility u via the requirement that the average distortion of the public variables is upper bounded, for each ǫ > 0 and all sufficiently large n, as

u ≡ E 1 n n i=1 ρ X Kr,i , XKr,i ≤ D + ǫ, (4)
where ρ (•, •) denotes a distortion function, E is the expectation over the joint distribution of (X Kr , XKr ), and the subscript i denotes the i th entry of the database. Examples of distortion functions include the January 15, 2013 DRAFT Euclidean distance for Gaussian distributions, the Hamming distance for binary input and output databases, and the Kullback-Leibler (K-L) divergence.

Privacy: We quantify the equivocation e of all the private variables using entropy as

e ≡ 1 n H X n Kh |J, Z n ≥ E -ǫ. (5)
Analogous to [START_REF] Gruteser | Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking[END_REF], for continuous sources, we can quantify the privacy leakage l using mutual information as

l ≡ 1 n I X n Kh ; J, Z n ≤ L + ǫ. (6)
The mappings in ( 2) and ( 3) ensure that d is mapped to d ′ such that the constraints in ( 4) and ( 5) are met. The formalism in ( 1)-( 6) is analogous to lossy compression in that a source database is mapped to one of M quantized databases that are designed a priori. For a chosen encoding, a database realization is mapped to the appropriate quantized database. It suffices to communicate the index J of the resulting quantized database as formalized in (2) to the user. This index, in conjunction with side information, if any, enables a reconstruction at the user as in [START_REF] Aggarwal | On the design and quantification of privacy preserving data mining algorithms[END_REF]. Note that the mappings in ( 2) and ( 3), i.e., lossy compression with privacy guarantees, ensure that for any D > 0, the user can only reconstruct the database d ′ = Xn Kr , formally a function f (J, Z n ), and not d = X n K itself. The utility and privacy metrics in (4) and ( 5) capture the statistical nature of the problem, i.e., the fact that for large enough n the entries of the database statistically mirror the distribution (1). Thus, both metrics represent averages across all database instantiations d, and hence, (assuming stationarity and large n) over the sample space of X K thereby quantifying the average distortion (utility) and equivocation (privacy) achievable per entry.

D. Equivalence of Utility-Privacy and Rate-Distortion-Equivocation

Mapping utility to distortion and privacy to information uncertainty via entropy (or leakage via mutual information) leads to the following definition of the utility-privacy (U-P) tradeoff region.

Definition 1: The U-P tradeoff region T is the set of all U-P tuples (D, E) for which there exists a coding scheme (F E , F D ) given by ( 2) and (3), respectively, with parameters (n, M, u, e) satisfying ( 4) and ( 5).

While T in Definition 1 can be determined for specific database examples, one has to, in general, resort to numerical techniques to solve the optimization problem. To obtain closed form solutions that define the set of all tradeoff points and identify the optimal encoding schemes, we exploit the rich set of techniques from rate distortion theory with and without equivocation constraints. To this end, we study a January 15, 2013 DRAFT more general problem of rate-distortion-equivocation (RDE) by introducing an additional rate constraint M ≤ 2 n(R+ǫ) which bounds the number of quantized SDBs in [START_REF] Csiszar | Broadcast channels with confidential[END_REF]. Besides enabling the use of known rate-distortion techniques, the rate constraint also has an operational significance. For a desired level of accuracy (utility) D, the rate R is the precision required on average (over X K ) to achieve it. We now define the achievable RDE region as follows.

Definition 2: The RDE region R RDE is the set of all tuples (R, D, E) for which there exists a coding scheme given by ( 2) and (3) with parameters (n, M, u, e) satisfying the constraints in ( 4), ( 5), and on the rate. In this region, R D-E , the set of all feasible distortion-equivocation tuples (D, E) is defined as

R D-E ≡ {(D, E) : (R, D, E) ∈ R RDE , R ≥ 0} . (7)
The RDE problem includes a constraint on the precision of the public variables in addition to the equivocation constraint on the private data in the U-P problem. Thus, in the RDE problem, for a desired utility D, one obtains the set of all rate-equivocation tradeoff points (R, E) , and therefore, over all distortion choices, the resulting region contains the set of all (D, E) pairs. From Definitions 1 and 2, we thus have the following Proposition. -dimensional database space n ---Database instatiation ---Quantized/Revealed database nD Fig. 3. Space of all database realizations and the quantized databases.

E. Understanding the Formalism

The formalism here aims to determine the optimal sanitization, i.e., a mapping which guarantees the maximal privacy for the private (hidden) attributes and a desired level of utility for the public attributes, among the set of all possible mappings that transform the public attributes of a database. We use the terms encoding and decoding to denote this mapping at the data publisher end and the user end respectively.

A database instance is an n-realization of a random source (the source is a vector when the number of attributes K > 1) and can be viewed as a point in an n-dimensional space (see Fig. 3). The set of all possible databases (n-length source sequences) that can be generated using the source statistics (probability distribution) lie in this space.

January 15, 2013 DRAFT Our choice of utility metric is a measure of average 'closeness' between the original and revealed database public attributes via a distortion requirement D. Thus the output of sanitization will be another database (another point in the same n-dimensional space) within a ball of 'distance' nD. We seek to determine a set of M = 2 nR output databases that 'cover' the space, i.e., given any input database instance there exists at least one sanitized database within bounded 'distance' nD as shown in Fig. 3. Note that the sanitized database may be in a subspace of the entire space because only the public attributes are sanitized and the utility requirement is only in this subspace.

Such a distortion-constrained encoding is referred to in the signal processing literature as vector quantization because the compression is of an n-dimensional space and can be achieved in practice using clustering algorithms. In addition to a distortion (utility) constraint, our privacy constraint also requires that the "leakage" (i.e. the loss of uncertainty) about the private attributes via correlation from the sanitized database is bounded. The set of M source-sanitized database pairs is chosen to satisfy both distortion and leakage constraints.

IV. PRIVACY CASE STUDIES

We now turn our attention to exploring case studies where signal and information processing techniques, motivated by the framework we outline in Section III, can be applied to improve privacy. Our exploration of case studies will examine three broad categories of database privacy: (i) statistical data privacy which involves guaranteeing privacy of any individual in a database that is used for statistical information processing (utility); (ii) competitive privacy which involves information sharing for a common system good (utility) between competing agents that are physically interconnected; and (iii) consumer privacy related to guaranteeing privacy when monitoring users using smart devices (utility).

A. Statistical Data Privacy

The problem of privacy for databases was first exposed by census statisticians who were required to publish statistics related to census functions but without revealing any particulars of individuals in the census databases [START_REF] Dalenius | Finding a needle in a haystack -or identifying anonymous census records[END_REF]. Several early attempts were made to publish census data using ad hoc techniques such as sub-sampling. However, the first widely reported attempt at a formal definition of privacy was by Sweeney [START_REF] Sweeney | k-anonymity: A model for protecting privacy[END_REF]. The concept of k-anonymity proposed by Sweeney captures the intuitive notion of privacy that every individual entry should be indistinguishable from (k -1) other entries for some large value of k.

January 15, 2013 DRAFT

The approaches considered in the literature have centered on the correct application of sanitization that ensure that a user interacts only with a modified database that is derived from the original (e.g.: [START_REF] Dalenius | Finding a needle in a haystack -or identifying anonymous census records[END_REF], [START_REF] Sweeney | k-anonymity: A model for protecting privacy[END_REF], [START_REF] Aggarwal | On the design and quantification of privacy preserving data mining algorithms[END_REF]). Most of the these sanitization approaches, with the exception of differential privacy-based ones, are application-specific and often focus on additive noise approaches. More recently, privacy approaches for statistical databases has been driven by the differential privacy definition [START_REF] Dwork | Differential privacy[END_REF] in which the authors take the view that the privacy of an individual in a database is related to the ability of an adversary to detect whether that individual's data is in that database or not. In this special issue, the reader will find an article ***To Be Filled in After Review Cycle Completes*** discussing signal processing techniques for DP.

DP is a strictly stronger concept than the IT definition of privacy used here. However, the IT model has a strong statistical basis and is suited to many application domains where strict anonymity is not the requirement. For example, in many wellness databases the presence of the record of an individual is not a secret but that individual's disease status is. The vector quantization based sanitization approach presented here applies to both numerical and categorical data whereas DP, while being a very popular model for privacy, appears limited to numerical data.

More generally, a rigorous model for privacy-utility tradeoffs with a method to achieve all the optimal points has remained open and is the subject of this survey. The use of information theoretic and signal processing tools for privacy and related problems is relatively sparse and and is beginning to draw the attention of signal processing researchers. [START_REF] Yamamoto | A source coding problem for sources with additional outputs to keep secret from the receiver or wiretappers[END_REF] analyzed a simple two variable model using rate distortion theory with equivocation constraints, which is the prime motivation for the general framework introduced here.

We now illustrate how our framework can be applied to a simple numerical database example. Consider a K = 2 database where both attributes X and Y are jointly Gaussian with zero means and variances σ 2 X and σ 2 Y , respectively, and with correlation coefficient ρ = E [XY ] / (σ X σ Y ). This model applies for numeric data (e.g., clinical data), such as height and weight measures, which are roughly assumed to be normally distributed. We assume that for every entry only one of the two attributes, say X, is revealed while the other, say Y , is hidden such that Y -X -X forms a Markov chain. The RDE region for this case can be obtained directly from Yamamoto's results [START_REF] Yamamoto | A source coding problem for sources with additional outputs to keep secret from the receiver or wiretappers[END_REF] with appropriate substitution for a jointly Gaussian source. Furthermore, due to the Markov relationship between of X, Y, and X, the minimization of I(X; X) is strictly over p(x|x), and thus, simplifies to the familiar rate-distortion problem for a Gaussian source X which in turn is achieved by choosing the reverse channel from X to X as an additive white Gaussian noise channel with variance D (average distortion). The resulting minimal rate [START_REF] Dalenius | Finding a needle in a haystack -or identifying anonymous census records[END_REF] DRAFT in a number of distributed computing applications.

Privacy and confidentiality concerns are frequently driven by economics [START_REF] Varshney | On cross-enterprise collaboration[END_REF]; for the distributed state estimation problem described above, [START_REF] Belmega | Pricing mechanisms for cooperative state estimation[END_REF] explores the cost of privacy using game-theoretic principles and shows that strictly non-zero prices are required to incentive cooperation when agents choose to optimize a linear combination of their leakage and distortion functions. For the same setup, [START_REF] Belmega | Repeated games for privacy-aware distributed state estimation in the smart grid[END_REF] highlights the power of a repeated games model to build trust and enable collaborate over multiple interactions. Signal processing algorithms that allow interaction and games is the first step towards enabling secure distributed platforms.

C. Consumer Privacy

We now examine consumer privacy, which deals with problems arising as organizations monitor their clients or users. Within this broad class of client privacy, there exist different types of information that can be collected. One such category consists of physical measurements; this includes quantities like water, energy, or bandwidth usage. For instance, when people use electricity, power companies track clients' usage patterns in order to determine pricing; on the other hand, detailed information about power usage can reveal a lot about an individual's daily habits. The client would ideally like to preserve some level of privacy while still being able to benefit from the power company's service. It thus makes sense to ask how much information really needs to be leaked without affecting service quality. We illustrate this category with an example of privacy for smart meters and highlight the signal processing challenges.

Another category consists of more categorical measurements, such as the types of products a person buys, or the nature of Internet queries. In this context, we will discuss an example of how signal processing techniques can be used to achieve privacy in an image classification application.

1) Smart Meter Privacy: While the fine-grained monitoring afforded by smart meters enable better load balancing and reliability analysis in the electric grid, data from smart meters may be mined to infer personal information in ways that are unknown to us presently. A number of solutions have been proposed such as using batteries to mask usage patterns [START_REF] Kalogridis | Privacy for smart meters: Towards undetectable appliance load signatures[END_REF], [START_REF] Varodayan | Smart meter privacy using a rechargeable battery: minimizing the rate of information leakage[END_REF], anonymizing user data, adding noise and aggregating neighborhood data [START_REF] Rastogi | Differentially private aggregation of distributed time-series with transformation and encryption[END_REF]. Focusing on the tradeoff problem, [START_REF] Sankar | Smart meter privacy: A theoretical framework[END_REF] proposes a rigorous approach grounded in the framework presented in the earlier Section to quantify the tradeoff between utility and privacy and reveal signal processing methods of achieving privacy.

The motivation is to decouple the revealed meter data as much as possible from the personal actions of a consumer. This insight is based on the observation that irregular (intermittent) activity such as kettles or lights turned on manually are much more revealing of personal actions than regular (continuous) activity January 15, 2013 DRAFT such as refrigerators or lights on timers. In [START_REF] Sankar | Smart meter privacy: A theoretical framework[END_REF], the time-series data from the smart meters is modeled as a noisy linear mixture of colored Gaussian processes 1 , each process generated by an underlying appliance. Appliances are modeled as belonging to two broad classes, one which is continuously on (e.g., air conditioners, heaters) in time (and thus, have narrow spectral signatures) and the other which come on intermittently (e.g., toasters, kettles, washers, etc.) and are bursty in time (and thus, have broad spectral signatures). The privacy-utility tradeoffs on the total load are shown to be achievable using an interference-aware reverse waterfilling solution which: (i) exploits the presence of high-power but less private appliance spectra as implicit distortion noise, and (ii) filters out frequency components with lower power relative to a distortion threshold.

The solution in [START_REF] Sankar | Smart meter privacy: A theoretical framework[END_REF] exploits the fact that the time-series measurements can be transformed to the spectral domain in which minimizing the information leakage of the intermiittent appliances leads to the problem of optimally allocating the distortion (mean-squared error between the actual and revealed meter data) for each spectral frequency subject to a joint distortion constraint over all frequencies. This joint distortion constraint in turn determines a threshold waterlevel (PSD) below which all spectral energy is suppressed (and hence, the name reverse water-filling).

The power of the solution is illustrated in the following example. A continuous (denoted c) and an intermittent appliance (denoted i) load measurements are modeled as (time-limited) Gauss-Markov processes whose auto-correlation fucntions P (l) ρ -|k| (l) , l = i, c, are characterized by variance P (l) , correlation coefficient ρ (l) , and memory m (l) for the l th appliance type. These parameters allow modeling the fact that the continuously used appliances have a longer memory and a larger correlation coefficient relative to the intermittently used appliances; furthermore, the bursty usage pattern of the intermittent appliances is incorporated by choosing P i > P c .

For P i = 12, P c = 8, ρ i = 0.4, ρ c = 0.8, m i = 40, and m c = 120, in Fig. 4, the power spectral densities (PSDs) for the intermittent, continuous (with noise), and both (with noise) for the parameters is shown. Also shown is the waterlevel λ and the distortion spectrum ∆ (f ). From both figures, we see that the distortion spectrum is zero when the PSD of the noisy continuous process dominates either that of the intermittent process or the waterlevel λ leading to zero and minimal leakage, respectively, for the two cases. The waterlevel λ determines the distortion spectrum otherwise.

2) Image Classification Privacy: A commonly-cited application for client privacy is biometric identification [START_REF] Lai | Privacy-Security Tradeoffs in Biometric Security Systems -Part I: Single-Use Case[END_REF]. The FBI recently unveiled plans to spend one billion dollars on a tracking system that 1 Colored processes are those in which the signals generated at each time instance are correlated with those generated previously. relies on face recognition to scan surveillance video for wanted persons; meanwhile, civil rights groups are raising objections about privacy violations [START_REF] Reardon | FBI launches $1 billion face recognition project[END_REF]. To relieve this tension, privacy-preserving algorithms could prevent normal citizens from being tracked by the government, while simultaneously allowing police agencies to find criminals. This problem reduces to one of privacy-preserving image classification.

Many existing algorithms dealing with private media classification rely on cryptographic primitives that permit basic computation in the encrypted domain (e.g., [START_REF] Erkin | Privacy-preserving face recognition[END_REF]). An example of a system that instead uses signal processing techniques to reduce the necessary communication and computational load is the private face recognition system in [START_REF] Fanti | Private media search on public databases[END_REF]. In this system, the client inputs a face image, and with the help of a server storing a database of faces, the client learns the subject's name. Meanwhile, the server learns nothing about the client's query.

The basic insight in [START_REF] Fanti | Private media search on public databases[END_REF] is that a practical privacy-preserving search algorithm should be designed with privacy primitives in mind. Therefore, the system alters a Euclidean-distance nearest-neighbor search into a Hamming distance comparison, which is more compatible with distortion-intolerant privacy primitives. This problem redefinition occurs via a feature vector transformation that involves projection onto random hyperplanes [START_REF] Yeo | Rate-efficient visual correspondences using random projections[END_REF]. Yeo et al. showed that the Hamming distance between two transformed vectors is directly related to the Euclidean distance between the original real-valued vectors. The new binary features couple nicely with a primitive called private information retrieval to enable privacy-preserving searches at communication and computation costs sublinear in database size. This example is useful because it illustrates that signal processing techniques-in this case, the feature January 15, 2013 DRAFT transformation-can significantly reduce the resource consumption of privacy-aware systems. However, the face recognition system in [START_REF] Fanti | Private media search on public databases[END_REF] combines signal processing with privacy primitives to achieve IT client privacy. An even more signal-processing-flavored option would be a system that eschews privacy primitives altogether, and instead relies on the privacy properties of transformed feature vectors. Of course, to make such a system useful, it is critical to understand the privacy properties of various feature transformations at a theoretical level.

V. CONCLUDING REMARKS

We have explored a set of non-cryptographic mechanisms for security and privacy, and provided a unifying framework for studying and formulating the tradeoff between privacy and data utility. We note that traditional security mechanisms must play a role in securing our communications and information.

However, there are many situations on the horizon where a set of new tools can complement and enhance traditional security mechanisms. Domain-specific approaches that are founded on well-developed information-theoretical and signal processing principles represent an untapped resource for developing such new security tools. We explored several case studies where the methods described in this survey article can be used to drive the design of signal and information processing techniques that can thwart threats that cannot be dealt with using only conventional cryptographic mechanisms.

Fig. 1 .

 1 Fig. 1. Illustration of several classes of cyber-security and privacy threats in networks and distributed data systems.

Proposition 3 (

 3 Fig. 2. (a) Rate Distortion Equivocation Region; (b) Utility-Privacy Tradeoff Region.

629 Distortion D = 4 Fig. 4 .

 62944 Fig.4. A graphical illustration of the spectral filtering approach to suppress those appliance signatures that if revealed can lead to privacy violations.

R(D) and leakage L(D) achieved (in bits per entry) are, for D ∈ 0, σ 2 X , R(D) = 1 2 log σ 2 X /D and L(D) = 1 2 log( 1 -ρ 2 XY + ρ 2 XY D σ 2 X -1 ), respectively. As expected, L(D) is maximal for D = 0 (X revealed perfectly) in which case only the data independent of X in Y can be guaranteed perfect privacy, and minimal for D = σ 2 X when nothing is revealed (R = 0). The largest U-P tradeoff region is thus the region enclosed by L(D).

It is worth noting that the reconstructed database is also Gaussian distributed. Thus, if one wishes to preserve the most uncertainty about (some or all of) the original input database from the output, it suffices to add Gaussian noise. The power of the framework are two-fold: (i) one can find the privacy-optimal sanitization for the Gaussian case; and (ii) practical applications such as medical analytics that assume Gaussian-distributed data can still work on sanitized data, albeit with modified parameter values.

B. Competitive Privacy

The problem of sharing information across autonomous entities in such a way that no information apart from the answer to the query is revealed was identified by Agrawal et al [START_REF] Agrawal | Data security and protection: Information sharing across private databases[END_REF] (see also [START_REF] Wong | Competitive privacy: Secure analysis on integrated sequence data[END_REF] where the term competitive privacy is introduced). More recently, in [START_REF] Sankar | Competitive privacy in the smart grid: An information-theoretic approach[END_REF], the notion of competitive privacy was generalized to a variety of domains involving complex distributed networks (e.g., financial, water distribution, transport and congestion control, etc.).

The evolution of distributed sensing, control, and actuation systems to monitor complex networks (e.g., the power grid) had led to the problem of interactive distributed processing, often between competing entities, that manage subnetworks of a large connected network. The common benefit of network reliability drives the need for interaction while economics, competition, and consumer policies lead to privacy (confidentiality) constraints. In [START_REF] Sankar | Competitive privacy in the smart grid: An information-theoretic approach[END_REF] the formalism presented here is applied to the problem of distributed state estimation (estimation of complex voltages across the grid) enabled via data interactions amongst many agents. The formalism captures the tradeoff at each agent between the rate (precision) of data exchanges, the fidelity of its estimate (distortion), and the leakage of its private information (typically state information, say X, in an agent's subnetwork) when every agent shares a (compressed) function of its measurements (say Y which is a function of some or all X) with others.

For a Gaussian measurement model (i.e., measurement Y at each agent is a noisy linear combination of Gaussian states X at the different agents), [START_REF] Sankar | Competitive privacy in the smart grid: An information-theoretic approach[END_REF] shows that while private information leakages are inevitable in an interactive model, it is possible to share data minimally to achieve both the desired global estimation reliability at each agent and minial information leakage. More broadly, the resulting RDE tradeoff framework demonstrates that privacy-and confidentiality-aware interactions are possible