Jonas Böhler

Daniel Bernau

Florian Kerschbaum
email: florian.kerschbaum@uwaterloo.ca

Privacy-Preserving Outlier Detection for Data Streams

In cyber-physical systems sensors data should be anonymized at the source. Local data perturbation with differential privacy guarantees can be used, but the resulting utility is often (too) low. In this paper we contribute an algorithm that combines local, differentially private data perturbation of sensor streams with highly accurate outlier detection. We evaluate our algorithm on synthetic data. In our experiments we obtain an accuracy of 80% with a differential privacy value of = 0.1 for well separated outliers.

Introduction

In cyber-physical systems, e.g. smart metering, connected cars or the Internet of Things, sensors stream data to a sink, e.g. a database in the cloud, which is commonly controlled by a different entity. The subjects observed by the sensors have a vested interest in preserving their privacy towards the other entity. A technical means to preserve privacy is to anonymize the data (at the source). However, the data itself may be personally identifiable information as was, e.g., shown for smart meter readings [START_REF] Jawurek | Plug-in privacy for smart metering billing[END_REF]. Local data perturbation with differential privacy guarantees [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF] can be used to protect against such exploitation and can be applied by the sensor. However, the resulting utility in this noninteractive model is often much lower than in the interactive, trusted curator model of differential privacy. So far, successful, differentially private outlier detection was only achieved in the interactive model [START_REF] Feldman | Private coresets[END_REF][START_REF] Nissim | Smooth sensitivity and sampling in private data analysis[END_REF][START_REF] Nissim | Locating a small cluster privately[END_REF].

Our algorithm contributed in this paper shows that local data perturbation of sensor streams combined with highly accurate outlier detection is feasible. We achieve this by using a relaxed version of differential privacy and a privacy-preserving correction method. The relaxation is to adapt the sensitivity to the set of data excluding the outliers [START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF]. We assume a scenario where outliers are subject to subsequent investigation which requires precise data, e.g. a broken power line or water pipe. Our privacy-preserving correction method uses distribution of trust between a correction server and an analyst server (the database). The correction server never learns the real measurements, but only the random noise added by the data perturbation (with indices of data values). The analyst server never learns the random noise, but only indices of data values whose outlier status -false positives and false negatives -the correction server has adjusted 3 .

The result provides an improved outlier detection and preserves differential privacy towards the data analyst, since data perturbation is applied at the source (independent of the algorithm). Furthermore, the correction server never learns enough information to reconstruct any of the data.

Our non-interactive data perturbation is applied once for all subsequent analyses and does not require a privacy budget distributed over a series of queries which is critical in many applications [START_REF] Erlingsson | Rappor: Randomized aggregatable privacypreserving ordinal response[END_REF][START_REF] Roth | New Algorithms for Preserving Differential Privacy[END_REF]. We evaluate our algorithm on synthetic data. In our experiments we detect 80% of outliers in a subset of 10% of all points with a differential privacy value of = 0.1 on data sets with well separated outliers. Our error correction method has an average runtime of less than 40 milliseconds on 100,000 data points.

Related Work

We perform outlier detection on sensor data perturbed with relaxed differential privacy at the source and correct the detection errors due to perturbation. We are not aware of any related work on this specific problem, however, there has been extensive work in related areas: releasing differentially private topographical information, relaxations of differential privacy and separation of outliers and non-outliers.

In the area of releasing topological proximities under differential privacy a foundation for privately deriving cluster centers is provided in [START_REF] Blum | Practical privacy: the sulq framework[END_REF][START_REF] Mcsherry | Privacy integrated queries: an extensible platform for privacy-preserving data analysis[END_REF][START_REF] Roy | Airavat: Security and privacy for mapreduce[END_REF]. Their approaches have two drawbacks due to the use of the interactive model: The complex determination of for an assumed number of iterations until convergence and the limitation to aggregated cluster centers. An approach towards non-interactive differential privacy in clustering through a hybrid approach of non-interactive and interactive computations is formulated in [START_REF] Su | Differentially private k-means clustering[END_REF]. A foundation for increasing differential privacy utility by sensitivity optimizations is introduced in [START_REF] Nissim | Smooth sensitivity and sampling in private data analysis[END_REF]. Furthermore, the authors formulate a differentially private approach to release near optimal k-means cluster centers with their sample-andaggregate framework. In [START_REF] Nissim | Locating a small cluster privately[END_REF] the sample-and-aggregate approach is extended to detect the minimal ball B enclosing approximately 90% of the points; everything outside B is presumed to be an outlier. Their approach is formulated in the interactive model and requires to apply the calculated ball B to the original data for outlier identification. The work in [START_REF] Feldman | Private coresets[END_REF] is similar in the desire to produce a sanitized data set representation allowing an unlimited series of adaptive queries. Their non-interactive approach for producing private coresets (a weighted subset of points capturing geometric properties of its superset) suitable for k-means and k-median queries is proven theoretically efficient, but does not allow to identify individual outliers. Chances for great accuracy improvements in differentially private analysis are identified in [START_REF] Nissim | Locating a small cluster privately[END_REF] if outliers were identified and removed before analysis.

Several relaxations for differential privacy have been suggested. Either by adapting the sensitivity [START_REF] Nissim | Smooth sensitivity and sampling in private data analysis[END_REF], additional privacy loss [START_REF] Dwork | Our data, ourselves: Privacy via distributed noise generation[END_REF], by distinguishing between groups with different privacy guarantees [START_REF] Kearns | Privacy for the protected (only)[END_REF][START_REF] Lui | Outlier privacy[END_REF], or by relaxing the adversary [START_REF] Rastogi | Relationship privacy: output perturbation for queries with joins[END_REF][START_REF] Tramèr | Differential privacy with bounded priors: Reconciling utility and privacy in genome-wide association studies[END_REF]. In [START_REF] Dwork | Our data, ourselves: Privacy via distributed noise generation[END_REF] ( ,δ)differential privacy is presented where the privacy loss does not exceed with probability at most 1 -δ where δ is negligible. For our scenario in which outliers should be treated as a separate group, δ would become very large. Instead, we argue for a noise distribution with different guarantees for outliers and non-outliers. By relaxing the assumed adversary knowledge about the data the work [START_REF] Tramèr | Differential privacy with bounded priors: Reconciling utility and privacy in genome-wide association studies[END_REF] shows that utility gains in Genome-Wide Association Studies are achievable. This relaxation is not discriminating between different groups found in the data set as in our case. Additionally, we avoid relaxing the adversary and instead decrease the privacy guarantee for outliers.

The discussion on separation of outliers and non-outliers has been addressed in [START_REF] Kearns | Privacy for the protected (only)[END_REF] by questioning the equal right for privacy for all (i.e. citizens vs. terrorists). Their work is close to ours in enforcing privacy guarantees to differentiate between a protected and a target subpopulation. However, in [START_REF] Kearns | Privacy for the protected (only)[END_REF] the original data is maintained and query answers are perturbed interactively with a trusted curator. We avoid giving access to original data and enforce perturbation at the source. It is concluded in [START_REF] Machanavajjhala | Privacy: Theory meets practice on the map[END_REF] that sparse domains incorporate a high risk of producing outliers in the perturbed data and thus argue for the need of outlier identification and removal in the unperturbed data set. In contrast, we preserve outliers and enable the detection of outliers in the perturbed data. Tailored differential privacy is defined in [START_REF] Lui | Outlier privacy[END_REF] and aims to provide stronger -differential privacy guarantees to outliers. We decided to evaluate the opposite by granting them less protection since we see outliers as faulty systems or sensors one needs to detect.

Preliminaries

We model a database (or data set) D as a collection of records from D n , i. The protection for an individual in the database is measured by the privacy level . While a small offers higher protection for individuals involved in the computation of a statistical function f , a larger offers higher accuracy on f . In case an individual is involved in a series of n statistical functions perturbed by a corresponding mechanism M i , where each function is requiring i , her protection is defined as = n i=1 i by the basic sequential composition theorem of Dwork et al. [START_REF] Dwork | Our data, ourselves: Privacy via distributed noise generation[END_REF][START_REF] Mcsherry | Privacy integrated queries: an extensible platform for privacy-preserving data analysis[END_REF]. A data owner can limit the privacy loss by specifying a maximum for called privacy budget [START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF]. Depending on the mutual agreement the exhaustion of the privacy budget can require the original data to be destroyed as mentioned in [START_REF] Roth | New Algorithms for Preserving Differential Privacy[END_REF] since the privacy guarantee no longer holds.

The noise level of M in differential privacy is dependent on the sensitivity of f . For an overview of different notions of sensitivity with respect to the l 1 -metric see Table 1. The global sensitivity GS f of a function f : D n → R k determines the worstcase change that the omission or inclusion of a single individual's data can have on f . For example, if f is a counting query the removal of an individual can only change the result by 1. GS f has to cover all neighboring databases, whereas local sensitivity LS f (D) covers one fixed database instance D ∈ D n and all its neighbors. In certain

Global [4] GS f = max D 1 ,D 2 : d H (D 1 ,D 2 )=1; D 1 ,D 2 ∈D n f (D1) -f (D2) 1 Local LS f (D1) = max D 2 : d H (D 1 ,D 2 )=1; D 2 ∈D n f (D1) -f (D2) 1 Smooth [17] SS f,β (D1) = max D 2 ∈D n LS f (D2)e -βd H (D 1 ,D 2 )
cases databases with low local sensitivity can have neighbors with high local sensitivity, thereby allowing an attacker to distinguish them by the sensitivity-dependent noise magnitude alone. In contrast, smooth sensitivity SS f (D) compares a fixed database instance D with all other database instances but with respect to the distance between them and a privacy parameter β. 4 Using the notation from Table 1, the parameters that differ in the various notions are: allowed distance between neighboring databases D 1 , D 2 (1 for GS f and LS f , unrestricted for SS f ) and choice of databases D 1 (a single fixed database instance for LS f and SS f , unrestricted for GS f ). In Sect. 4 we introduce a new notion of sensitivity, relaxed sensitivity, where the choice of databases is generalized to allow the selection of a subgroup of all possible databases. Two models for computation of a mechanism M have been suggested by [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF]. In the interactive model a data analyst receives noisy answers to functions evaluated on unperturbed data D as long as the privacy budget is not exhausted. In contrast, the original data D can be discarded in the non-interactive model by producing a sanitized version D = M(D, f ) of D and results are calculated with D . While [START_REF] Nissim | Smooth sensitivity and sampling in private data analysis[END_REF] assumes that the majority of mechanisms utilize the interactive model the findings of [START_REF] Blum | A learning theory approach to noninteractive database privacy[END_REF] suggest that D is inefficient but potentially useful for many classes of queries if computational constraints are ignored. However, the non-interactive model also has its benefits: First, there is no need for a curator who requires access to the sensitive D, analyzes and permits queries and adjusts the privacy budget. Second, storage constrained sensors do not need to retain D and instead release a locally sanitized D . Third, the data owner is not left with the administrative decision on how to handle exhausted privacy budgets (e.g. destroy D or refresh budget periodically as discussed in [START_REF] Mcsherry | Privacy integrated queries: an extensible platform for privacy-preserving data analysis[END_REF][START_REF] Roy | Airavat: Security and privacy for mapreduce[END_REF]).

Relaxed Differential Privacy

Differential privacy is a strong privacy guarantee due to its two worst-case assumptions: the adversary is assumed to have complete knowledge about the data set except for a single record and all possible data sets are covered by the guarantee. To relax differential privacy one has to relax these assumptions. The first assumption was relaxed in [START_REF] Rastogi | Relationship privacy: output perturbation for queries with joins[END_REF] by using a weaker but more realistic adversary and bounding the adversary's prior and posterior belief. In [START_REF] Nissim | Smooth sensitivity and sampling in private data analysis[END_REF] the second assumption is relaxed by their notion of smooth sensitivity. We focused on the latter approach due to the fact that we are concerned with the discovery of outliers: We do not need the guarantee to hold for all records equally.

Relaxed Sensitivity

Our following new notion of relaxed sensitivity allows for different privacy guarantees for groups N (non-outliers), O (outliers) within a single dataset

D n = N ∪ O. Definition 2 (Relaxed sensitivity). Let D n = N ∪ O then the relaxed sensitivity of a function f : D n → R k is RS N ,D n f = max D1,D2∈N D 2 : d H (D 1 ,D 2 )=1 f (D 1 ) -f (D 2 ) 1 .
In the following we abuse notation slightly and say that in the case that D consists of multiple, independent columns the sensitivity and perturbation are calculated per column and not the entire database at once. While local sensitivity only holds for one fixed database instance the relaxed sensitivity covers all databases from the subset N . Let LS X f , GS X f denote local and global sensitivity respectively over a database set X. Theorem 1. Relaxed sensitivity compares to local and global sensitivity as follows:

LS N f (D) ≤ RS N ,D n f = GS N f ≤ GS D n f where D ∈ N ⊆ D n .
The proof is omitted due to space constraints. We will omit the dataset in the sensitivity notation in the following when it is not explicitly needed. The privacy guarantee is enforced by noise whose magnitude is controlled by privacy parameter and the sensitivity. We adapt the popular Laplace mechanism [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF] to allow its invocation with different sensitivity notions.

Definition 3 (Laplace mechanism). Given any function f : D n → R k , the Laplace mechanism is defined as

M L (x, f (•), GS f / ) = f (x) + (Y 1 , . . . , Y k )
where Y i are independent and identically distributed random variables drawn from the Laplace distribution Laplace (GS f / ).

To relax differential privacy, we will adapt the scaling parameter to RS f / , thus sampling noise from Laplace (RS f / ). We view a database as consisting of multiple columns and the perturbation is performed per column: The Laplace mechanism receives a column, i.e. a vector, as input and outputs a perturbed vector. The proof is omitted due to space limitations.

Approximation of Relaxed Sensitivity

We do not want to restrict the queries an analyst can perform in the non-interactive model. Therefore, we choose to evaluate the identity function f id (x) = x for sensitivity determination. The sensitivity for f id can be unbounded depending on the input domain.

In the following we assume elements in N to be bounded real numbers. With f id as our function and bounded N , we can express the relaxed sensitivity as RS fid = max(N )min(N ), i.e. the gap between possible databases, that we seek to close. We see sensors measurements as point coordinates and use the terms interchangeably.

With historical data and domain knowledge the approximation can be tailored more precisely to individual data sets. With knowledge about what measurements can be considered physically possible one can approximate a bound for N . We approximate RS fid in the following with q-th percentiles ρ q , q ∈ [0, 100] of D. We denote with p o the percentage of outliers in the data set -alternatively, it can be seen as a bound on N . We set q max = 100 -p o /2, q min = 100 -q max , and approximate RS fid with

RS fid = ρ qmax (D) -ρ qmin (D). (1)
For this approximation we assume the following characteristics regarding our datasets:

1. We define outliers as points on an outer layer surrounding non-outliers, 2. the percentage of outliers or a bound for N can be approximated, 3. the data set contains only one cluster.

Assumption 1 is also used in depth-based outlier detection algorithms. Regarding assumption 2, one can learn the outlier percentage or bounds via historical data and the range of plausible (i.e. non-faulty, physically possible) measurements. If multiple clusters exists the data can be split in cluster groups thus fulfilling assumption 3. The split is either performed by the data owner or a third party in a privacy-preserving manner (see Sect. 2 for clustering approaches consuming a portion of ). RS f implicitly defines N , which is an estimation of N . An estimation RS f > RS f leads to N ⊂ N , i.e. more elements than necessary are protected which does not decrease privacy for elements from N . However, RS f < RS f implicitly defines N ⊂ N , i.e. elements in N \N could suffer a privacy loss since they receive less noise than needed. We want to stress that even for an inaccurate approximation, the non-outliers are still protected and receive a privacy level of = • RS fid / RS fid ≥ (see Theorem 2). Furthermore, we correct errors introduced by the perturbation (or estimation RS f > RS f ). For this we classify and detect the errors based on their change in distance to the center after and before perturbation as described in the following sections.

Outliers and False Negative Types

Let f outlier be an outlier detection function f outlier : T → {1, . . . , |T |} which returns the indices (i.e. row numbers) of T which are outliers. We will refer to outliers detected in the unperturbed data set as outliers or O = f outlier (T ). When referring to the perturbed version of T , denoted as T , we will use presumed outliers or O = f outlier (T ). We define outliers as points on an outer layer surrounding a (denser) core similar to [START_REF] Nissim | Locating a small cluster privately[END_REF]. Our goal is to find a small subset containing on the perturbed data without having access to the original data. We perturb the data set with the adapted Laplace mechanism using approximated relaxed sensitivity per column. For well-separated outliers and nonoutliers and with our relaxed sensitivity notion O and O can be equal. However, this is not necessarily the case and therefore we present a correction algorithm in Sect. 6 to find the false negatives i.e. missing outliers from O that are not in O . The presumed outliers in O can be separated in two sets: false positives, i.e. presumed outliers in O that are not in O and true positives, i.e. outliers in O that are also in T .

We distinguish between two different types of false negatives visualized in Fig. 1. Non-outliers lie in the core layer, outliers in the outlier layer and the empty border layer separates the two. The layers for the unperturbed data differ from the perturbed layers which are omitted in Fig. 1. The two types of false negatives can occur as follows: First, a non-outlier can become a cover point after perturbation, i.e. "cover" a real outlier to produce a false negative as shown in Fig. 1b. Second, an outlier can also become a false negative on its own when it lands in a non-outlier region after perturbation, e.g. a dense core as in Fig. 1c, where it will not be detected in the perturbed data.

Relaxed Differentially Private Outlier Detection & Correction

Given the data T , a relaxed differentially private version of T , we want to find the outliers corresponding to the unperturbed T . We use the semi-honest model introduced in [START_REF] Goldreich | Foundations of Cryptography: Volume 2, Basic Applications[END_REF] where corrupted protocol participants do not deviate from the protocol but gather everything created during the run of the protocol. (e.g. message transcripts, temporary memory). Furthermore, we assume that only one participant can be corrupted; an alternative assumption is that participants do not share their knowledge. The assumption that parties do not share their knowledge is similar to the interactive model of differential privacy, i.e. different analysts do not collaborate by combining their privacy budgets.

In the following we view data sets as consisting of two columns, one column per measured attribute. Let T , T be the unperturbed resp. perturbed data set. For the perturbation each column receives independently drawn noise from the Laplace mechanism with approximated relaxed sensitivity. We use sets of indices corresponding to rows in T and T . This is convenient since an index identifies the same point before and after perturbation. Let I be the set of indices from T (and thereby also T ). We denote with T [i] the row at index i ∈ I and with T [, j] the selection of column j. Recall that we denote with O the set of all indices corresponding to rows with outliers in T detected by f outlier , i.e. O = f outlier (T ), and with O the set of all presumed outlier indices from T . As before, false negatives are missing outliers from O that are not found in O , false positives are presumed outliers in O that are not in O, and true positives are outliers in O that are also in O . We denote the Euclidean distance of two points c, x as d(c, x) = d c (x) where c is the center of T , determined by averaging each column.

Definition 4 (Distance Difference d diff ). The distance difference between a point in T and T at index i and the center c after and before perturbation respectively is

d diff [i] = d c (T [i]) -d c (T [i]).
We denote with w O the width of the outlier layer (visualized in Fig. 1) in the unperturbed data T . We denote with FN Lj a set of indices for different layers j ∈ {1, 2, 3} of presumed false negatives. These are spatial layers based on the false negative types of Fig. 1 used in the correction phase.

Correction Algorithm

Our goal is to detect presumed outliers on relaxed differentially private data T , find the undetected false negatives and remove additionally detected false positives. The algorithm presented in Fig. 2 operates as follows: Each sensor S has as input the data set T , the privacy parameter and approximated relaxed sensitivities RS fid,j for each data column j. The correction server CS has as input the outlier layer width w O . The values for RS fid,j and w O are determined with historical data, i.e. knowledge about past outliers, and bounds for the non-outliers, e.g. normal, non-faulty measurement values for sensors. S scales the data in line 1a and generates the perturbed data set T via perturbation of each column j with the adapted Laplace mechanism parameterized with RS fid,j / . Then it sends T to the analyst A and the distance differences d diff to the correction server CS. In line 3 the server CS filters O in two sets FP and T P for presumed false positives and true positives respectively. The filtering is based on comparison of d diff against a threshold -the distance difference with the biggest change between sorted distance differences. We use the fact that false positives, i.e. non-outliers that were detected as outliers in the perturbed set, have a higher distance difference, i.e. receive more noise, than true positives when non-outliers and outliers are well-separated. We do not want to remove true positives (actual outliers) under any circumstances. Thus, we err on the side of removing not enough false positives if the separation between outliers and non-outliers is low. In line 4 we reduce the set of indices to check for potential false negatives. Without the reduction true negatives can land in FN Lj , since they have the same distance difference (d diff ) but not the same core distance (d c ) as false negative candidates. The server CS detects false negatives in line 5, i.e. outliers not contained in O , in three spatial layers FN L1 , FN L2 , and FN L3 , where the first corresponds to the false negative type from Fig. 1c and the latter to 1b. The use of two layers FN L2 and FN L3 for one false negative type is due to the row reduction and a simplification for FN L2 explained in the following. (c) Sends (id, dT P , dT P + wO) to A.

4. Analyst A creates I2 = {i ∈ I\O | dc(T [i]) ≥ dT P }, I3 = {i ∈ I\O | dc(T [i]) ≥ dT P + wO},
and sends (id, I2, I3) to CS. 5. Correction Server CS creates false negatives layer sets

FN L1 = {i ∈ I\O | ddiff[i] < 0}, FN L2 = {i ∈ I2 | 0 ≤ ddiff[i] ≤ dT P }, FN L3 = {i ∈ I3 | dT P ≤ ddiff[i] ≤ dT P + wO}.
Output: CS outputs (id, T P, FN L1, FN L2, FN L3) to DO. The inequalities are based on the unperturbed position of outliers in respect to nonoutliers (i.e. on an outer, less dense layer) and the distance difference after perturbation. The reasoning for FN L1 is that non-outliers, who are by definition closer to the center c, are distanced further away from c after perturbation due to the noise magnitude. Whereas outliers, who are already further away, can reduce their distance to the center as seen in Fig. 1c. Hence, we look for indices i fulfilling d diff [i] < 0. The idea behind FN L2 is a simplification that all outliers lie on the same "orbit" around the center (same center distance). In this case the minimal distance difference d diff to become a true positive is the minimal d diff one can find from the set of presumed true positives T P, i.e. d T P = min t∈T P (d diff [t]). Only unperturbed outliers with a d diff greater than d T P could be detected as an outlier after perturbation. Hence, the remaining undetected have d diff larger than 0 (otherwise they land in FN L1 ) but smaller than d T P . However, not all outliers do lie on the same orbit. Therefore, we collect in FN L3 indices with distance difference greater than d T P . We also know that no undetected outlier's distance difference can be greater than the distance difference of false positives in FP, i.e. d F P = min

f ∈F P (d diff [f ]
). More precise is the outlier layer width w O (line 4).

Privacy of the Correction Algorithm

The server CS knows the distance difference for points at a given index i, i.e. d diff [i], but CS does not know which perturbed point is identified by i since this knowledge remains at the analyst A. The only information CS sends to A is d T P , w O , i.e. information regarding outliers which we like to detect. Even if A had access to all outlier information, including the noise used to perturb them, it would not lessen the protection of nonoutliers. In exchange A sends CS I L2 , I L3 , i.e. sets of indices j of perturbed points with d c (T [j]) ≥ d T P and d c (T [j]) ≥ d T P + w O respectively. However, CS does not know which points correspond to these indices. If A and CS were to collaborate (i.e. not semi-honest) they could only narrow down the possible origin of a perturbed point. The information collaborating servers could learn can be reduced by using frequency-hiding order-preserving encryption as presented in [START_REF] Kerschbaum | Frequency-hiding order-preserving encryption[END_REF] for the distance differences. Secure computation is not practical for our scenario (e.g. computation constrained IoT sensors) due to the bidirectional communication -although the communication complexity can be seen as almost independent of the network performance as shown in [START_REF] Kerschbaum | On the practical importance of communication complexity for secure multi-party computation protocols[END_REF].

Outlier Detection Evaluation

We compared detected outliers on the original data with presumed outliers found on the perturbed data. Our algorithm was implemented in R 3.3.1 and run on a Apple MacBook Pro (Intel Core i7-4870HQ CPU, 16GB main memory). We selected DBSCAN [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF] to realize f outlier and used the fpc package implementation. DBSCAN utilizes density and proximity of points, thus matching our spatial definition of the outlier topology where the outliers lie on an outer layer surrounding a denser core. DBSCAN is parameterized via eps for neighborhood reachability (point proximity and connections) and minP ts (threshold density within the reachable neighborhood). We used the same DBSCAN parameters for the unperturbed and perturbed data. Our error correction logic only requires between 30 and 40 milliseconds for 100,000 points. Four synthetic datasets were created to examine the impact of varying separation between outliers and non-outliers with the following characteristics: 100,000 points in R 2 where each dimension is sampled independently from a normal distribution with standard deviation 3 and mean 0. Outlier percentage in the unperturbed data is 10%. After sampling the distances between outliers and non-outliers were increased to ≈ 50, 120, 220, 400; we denote these data sets with Separation 50, etc. These separation distances were chosen based on decreasing probabilities that Laplace distributed noise preserves the outlier topology.

With accuracy we denote the percentage of all false negatives and true positives, i.e. all outliers, found with our approach. Furthermore, subset size is the size of the output of algorithm in Fig. 2, i.e. {T P, FN L1 , FN L2 , FN L3 }. Accuracy and subset (a) Accuracy. size for ∈ {0.1, 0.5, 1} is shown in Fig. 3a and Fig. 3b respectively. The results for = 0.1 indicate that our correction algorithm achieves meaningful accuracy of ≈ 75% for separation ≥ 220. However, = 0.1 is a strong privacy guarantee and ∈ {0.5, 1} still offers meaningful protection. For = 0.5 the found outlier percentage increases to 95-100% for all data sets. With a privacy guarantee of = 1 our correction algorithm is not always needed since the separation between outliers and non-outliers is preserved even after perturbation. The subset size is always below 20% as is evident from Fig. 3b.

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •
• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •

Conclusion

We implemented and evaluated an algorithm for detection of individual outliers on data perturbed in the local, non-interactive model of differential privacy, which is especially useful for IoT scenarios. We introduced a new notion of sensitivity, relaxed sensitivity, to provide different differential privacy guarantees for outliers in comparison to nonoutliers. Furthermore, we presented a correction algorithm to detect false negatives and false positives. In our experiments we detect 80% of outliers in a subset of 10% of all points with a differential privacy value of = 0.1 for data with well separated outliers.

  e. D ∈ D n , where each entry D i of D represents one participant's information. The Hamming distance d H (•, •) between two databases x, y ∈ D n is d H (x, y) = |{i : x i = y i }|, i.e. the number of entries in which they differ. Databases x, y are called neighbors or neighboring if d H (x, y) = 1. Definition 1 (Differential Privacy). A perturbation mechanism M provides -differential privacy if for all neighboring databases D 1 and D 2 , and all S ⊆ Range(M), Pr[M(D 1 ) ∈ S] ≤ exp( ) • Pr[M(D 2 ) ∈ S].

Theorem 2 .

 2 Let D n = N ∪ O and f be a function f : D n → R k . The Laplace mechanism M L (x, f, RS f / ) preserves -differential privacy for x ∈ D n and preserves -differential privacy for x ∈ N , where = • GS f /RS f ≥ .

  Outlier undetected due to perturbation of other points.(c) Outlier undetected due to its perturbation.

Fig. 1 .

 1 Fig. 1. Types of false negatives after perturbation. Layers correspond to unperturbed data points.

1 .

 1 Each sensor S id (a) Scales each column T [, j]: subtraction of mean and division of standard deviation. (b) Perturbs each column to T [, j] = ML(T [, j], fid, RS f id ,j / ) and sends its id and perturbed data, i.e. (id, T ), to analyst A. (c) Calculates the data center c by averaging every dimension, calculates the distance differences ddiff = dc(T ) -dc(T ) and sends (id, ddiff) to correction server CS. 2. Analyst A performs standard outlier detection on T to get the list O of presumed outliers indices and sends (id, O ) to CS. 3. Correction Server CS (a) Calculates the threshold index t for the biggest change between ascending ddiff values of presumed outliers: t = arg max j k ∈J ddiff[j k+1 ] -ddiff[j k ] where J = {j1, j2, . . . } are the indices from O sorted according to ascending ddiff values. (For convenience we define j k+1 = j k for k + 1 > |J|.) (b) Separates indices via t into false positives FP = {i ∈ O | ddiff[i] > ddiff[t]} and true positives T P = O \FP and calculates dT P = min i∈T P ddiff[i].

Fig. 2 .

 2 Fig. 2. Algorithm for correction of outlier detection.

  Subset size as percentage of all points.

Fig. 3 .

 3 Fig. 3. Accuracy and subset size for synthetic data sets; mean of 5 runs with ∈ {0.1, 0.5, 1}.

Table 1 .

 1 Comparison of different sensitivity notions

The analyst server learns also parameters about the data set which are however computable from the output of the algorithm.

SS f needs to be a smooth upper bound S as defined in[START_REF] Nissim | Smooth sensitivity and sampling in private data analysis[END_REF], i.e. ∀D ∈ D n : S(D) ≥ LS f (D) and ∀D1, D2 ∈ D n , dH (D1, D2) = 1 : S(D1) ≤ e β • S(D2). These requirements can be fulfilled by S(D) = GS f with β = 0. SS f , however, is the smallest function to satisfy these requirements with β > 0.

Acknowledgments. This work has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 700294 (C3ISP) and 653497 (PANORAMIX).