#  ††thanks: Identify applicable funding agency here. If none, delete this.

Meisam Mohammady1, Han Wang 2, Lingyu Wang 3, Mengyuan Zhang 4 Yosr Jarraya 5,
Suryadipta Majumdar 3, Makan Pourzandi 5, Mourad Debbabi 3, Yuan Hong 6
<EMAIL_ADDRESS>{yosr.jarraya<EMAIL_ADDRESS>1
Data61, CSIRO, Cyber Security CRC
2 Illinois Institute of Technology, 3 Concordia University
4 Hong Kong Polytechnic University, 5 Ericsson Security Research, Ericsson
Canada, 6 University of Connecticut
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>{wang,
suryadipta.majumdar<EMAIL_ADDRESS>
#  DPOAD: Differentially Private Outsourcing of Anomaly Detection through
Iterative Sensitivity Learning

Meisam Mohammady1, Han Wang 2, Lingyu Wang 3, Mengyuan Zhang 4 Yosr Jarraya 5,
Suryadipta Majumdar 3, Makan Pourzandi 5, Mourad Debbabi 3, Yuan Hong 6
<EMAIL_ADDRESS>{yosr.jarraya<EMAIL_ADDRESS>1
Data61, CSIRO, Cyber Security CRC
2 Illinois Institute of Technology, 3 Concordia University
4 Hong Kong Polytechnic University, 5 Ericsson Security Research, Ericsson
Canada, 6 University of Connecticut
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>{wang,
suryadipta.majumdar<EMAIL_ADDRESS>
###### Abstract

Outsourcing anomaly detection to third-parties can allow data owners to
overcome resource constraints (e.g., in lightweight IoT devices), facilitate
collaborative analysis (e.g., under distributed or multi-party scenarios), and
benefit from lower costs and specialized expertise (e.g., of Managed Security
Service Providers). Despite such benefits, a data owner may feel reluctant to
outsource anomaly detection without sufficient privacy protection. To that
end, most existing privacy solutions would face a novel challenge, i.e.,
preserving privacy usually requires the difference between data entries to be
eliminated or reduced, whereas anomaly detection critically depends on that
difference. Such a conflict is recently resolved under a local analysis
setting with trusted analysts (where no outsourcing is involved) through
moving the focus of differential privacy (DP) guarantee from “all” to only
“benign” entries. In this paper, we observe that such an approach is not
directly applicable to the outsourcing setting, because data owners do not
know which entries are “benign” prior to outsourcing, and hence cannot
selectively apply DP on data entries. Therefore, we propose a novel
_iterative_ solution for the data owner to gradually “disentangle” the
anomalous entries from the benign ones such that the third-party analyst can
produce accurate anomaly results with sufficient DP guarantee. We design and
implement our Differentially Private Outsourcing of Anomaly Detection (DPOAD)
framework, and demonstrate its benefits over baseline Laplace and PainFree
mechanisms through experiments with real data from different application
domains.

###### Index Terms:

component, formatting, style, styling, insert

##  I Introduction

The recent worldwide surge in the adoption of cloud/edge computing
necessitated by the lockdown and remote working would likely sustain even
post-pandemic due to the apparent benefits of outsourcing computing tasks to
clouds, such as the pervasive access, increased flexibility and efficiency,
and reduced costs 111For example, Microsoft said it had seen “two years of
digital transformation in two months” as its customers started adopting cloud
solutions, and Gartner projected that the worldwide spending on public cloud
services would grow by 18.4% in 2021 to a total of $304.9 billion.. In such a
context, there is also an increasing need for outsourcing security analyses,
such as anomaly detection, to third parties hosted in clouds, e.g., Managed
Security Service Providers (MSSPs) [1]. Outsourcing security analyses to
clouds offers several benefits. First, it can allow light-weight distributed
systems (especially in IoT) to overcome their resource constraints (e.g.,
limited computational power, storage, or battery of lightweight smart
devices). Second, it can enable collaborative analysis that involves multi-
party data sharing (e.g., detection of a common malware infection across
different smart homes). Third, it can bring various benefits of hiring an
MSSP, such as cost effectiveness, updated technologies, and better trained and
specialized experts with knowledge about a diverse range of clients and
security vulnerabilities.

However, most data owners would be reluctant to outsource their security
analyses without sufficient privacy protection due to the sensitive nature of
such analyses [2]. In particular, outsourcing anomaly detection raises an
interesting and unique challenge to existing privacy solutions. On one hand,
most outsourcing and collaborative approaches (e.g., [3]) do not allow
outsourcing anomaly detection, and may sacrifice privacy guarantee for
accuracy . On the other hand, existing privacy measures, such as differential
privacy (DP) (which has been widely recognized as the state-of-the-art privacy
notion [4, 5]), often require the differences between data objects to be
eliminated or reduced (e.g., DP aims to generate indistinguishable outputs),
whereas anomaly detection critically relies on such differences to identify
outliers. In particular, Hafiz et al. [6, 7]) show that relatively strong
privacy guarantees render the analysis results useless (one false positive in
each three detected anomalies).

Such a “conflict” between anomaly detection and privacy is recently resolved
under a _local analysis setting_ where no outsourcing is involved and the
analyst is trusted to know the distribution of data. The key idea behind those
solutions, namely the “anomaly-restricted” strategy, is to only preserve the
privacy for benign records (instead of all records, as in a normal application
of DP). Unfortunately, such a strategy is no longer applicable when it comes
to the _outsourced analysis setting_ where the (third-party) analyst is not
trusted to know the data distribution, whereas the data owner does not know
which entries are “benign”, and hence cannot selectively apply DP on data
entries prior to outsourcing. In particular, Figure 1 compares the system
models of the _local analysis setting_ , as addressed in existing works [6, 8,
9, 7, 10] (top), and the _outsourced analysis setting_ studied in this work.

  * •

In the first model (_local analysis setting_), the data owner (who is also the
analyst) is a trusted data center (e.g., a Bank) who both applies DP to the
data and performs anomaly detection. On the other hand, the external user is
untrusted (for seeing the original data), and can only access DP-protected
detection results. Under such a model, we can see that the trusted data center
can easily apply the anomaly-restricted solutions [6, 7] by selectively
applying DP on only the benign records, as it has access to the original data.

  * •

The second model (_outsourced analysis setting_) is similar to the first
model, except that the data owner and analyst are now decoupled due to
outsourcing, e.g., the data owner is a lightweight IoT device who is trusted
but incapable of performing anomaly detection by itself, whereas the analyst
is an untrusted (for seeing the original data) cloud service provider to whom
the detection has been outsourced. Under such a model, we can see that the
data owner can no longer apply the anomaly-restricted solutions [6, 7], as it
does not know which records are benign before sending the data to the analyst.
On the other hand, the data owner cannot send the data without privacy
protection (due to untrusted analyst), or simply apply DP on all records
(which could render the records indistinguishable to anomaly detection).

Therefore, the outsourced analysis setting creates a unique challenge to
privacy protection. Specifically, we need to resolve the cyclic dependencies
between the following research questions:  (i) How can the analyst provide the
data owner with enough information, e.g., an approximate likelihood of
outlierness, to facilitate the anomaly-restricted DP solutions [6, 7].  (ii)
How can the data owner provide an (honest but untrusted) analyst with a DP-
protected version of its data that can lead to sufficiently accurate anomaly
detection.

Figure 1: System models of existing works [6, 8, 9, 7, 10] (top), and of DPOAD
(down)

Main Idea. To address the aforementioned challenges, our main idea is an
iterative approach for the data owner and analyst to gradually “disentangle”
the anomaly entries from the benign ones. Intuitively, by representing the DP
sensitivity as “water level” to hide people’s heights, Figure 2 depicts the
two major phases of our approach, i.e., the _learning_ phase (top), and the
_prediction_ phase (bottom). First, in the _learning_ phase, the data owner
starts by sending to the analyst IID data excerpts protected under regular DP
guarantees. Note an analyst who knows the shape of the pool and the DP
guarantee of the top portion of the figure “can” infer a good guess of the
distribution of the heights yet “cannot” accurately conduct anomaly detection.

Analyst then using all the DP data excerpts, computes a sufficiently accurate
estimation of the distribution of the underlying dataset (to be used for
effectively disentangling anomalous records from the benign ones) and sends it
to the data owner. Second, in the _prediction_ phase (bottom of Figure 2), the
data owner, using the approximated learnt PDF, disentangles the most likely
benign records from the suspicious ones, and focuses the DP mechanism
attention on them. To this end the accuracy of anomaly detection will be
significantly boosted through “entangling” the privacy of data records with
the learnt PDF.

Figure 2: The main idea of DPOAD which comprises learning and prediction
phases. The water height denotes the sensitivity of DP mechanism to hide
people’s height. The learnt PDF is used to disentangle (likely) benign records
from (likely) anomalous ones.

Contributions. We design our Differentially Private Outsourcing of Anomaly
Detection (_DPOAD_) framework for this iterative approach in Section III and
theoretically analyze its privacy guarantee in Section IV. Our analysis shows
that this mechanism satisfies a popular version of DP called the Random
Differential Privacy [11] which is widely used in protecting datasets with
unbounded/unknown sensitivities (similar to anomaly included datasets). In
particular, we show that with DPOAD preserves $\epsilon$-DP of benign
(anomalous) records with a probability close to (equivalently far from) one.
Furthermore, we formally benchmark DPOAD with the Laplace and Pain-Free
mechanisms on different anomaly detection applications such as network,
parking monitoring, IoT and credit card anomaly (fraudulent) detection.
Finally, we experimentally evaluate the accuracy improvements in anomaly
detection under DPOAD in comparison to the baselines Laplace mechanism and the
Pain-Free mechanism [12]. In summary, our main contributions are as follows:

  * •

As per our knowledge, DPOAD is the first approach that addresses the
_outsourced_ version of the long-standing conflict between differential
privacy and anomaly detection. This is especially relevant today as
outsourcing computing tasks to clouds has seen a global surge lately. To that
end, DPOAD introduces a novel iterative approach that allows the data owner
and analyst to collectively find an optimal differential privacy setting under
which the accuracy of anomaly detection can be maximized while guaranteeing
privacy.

  * •

DPOAD tackles various technical challenges pertaining to privacy-preserving
anomaly detection in the outsourced setting, including (a) learning data
distribution from orthodox DP excerpts of the dataset (which are not directly
suitable for anomaly detection), (b) guaranteeing an iterative version of DP,
called RDP [13], by sampling the sensitivity, first uniformly from the domain
of the data (the learning phase), and then from the learnt distribution (the
prediction phase), (c) further boosting the accuracy through refining the
estimated distribution of the data over time using the computed anomaly
scores, and leveraging this distribution into the sensitivity sampler.

  * •

Our experimental results demonstrate that DPOAD significantly improves the
accuracy of anomaly detection compared to the Laplace mechanism and the Pain-
Free solution [12]). The improvement rate varies between [0-100]% for the
parking dataset, [100-500]% for the credit card clients dataset, and
[300-600]% for network and building monitoring dataset.

The rest of the paper is organized as follows. Section II provides necessary
background, and Section III defines the DPOAD framework. Section IV analyzes
privacy, utility and efficiency advantage of DPOAD. Section V details the
experiments. Section VI reviews the related work, and Section VII concludes
the paper.

##  II Background

We review some notion and notations, as well as some required background on
differential privacy for the theoretical foundations of the DPOAD framework.

###  II-A Notions and Notations

Data [7]. We consider a database as a multiset of elements from a set
$\mathcal{X}$, which is the set of possible values of records. In a database,
we assume each record is associated with a distinct individual. We represent a
database $\mathcal{D}$ as a histogram in
$\mathcal{H}=\\{y\in\mathbb{N}^{\mathcal{X}}:||y||_{1}<\infty\\}$, where
$\mathcal{D}$ is the set of all possible database,
$\mathbb{N}=\\{0,1,2,\cdots\\}$, and $C_{j}$ is the number of records in
$\mathcal{D}$ that are identical to $j$. In particular, at each iteration $i$,
the data owner releases an excerpt of her/his dataset $D_{i}$ collected
between time $t_{i-1}$ and $t_{i}$; converts it to histogram $H_{i}$ consist
of a fixed set of bins $B_{1},B_{2},\cdots,B_{m}$ (also a subset of
$\mathcal{H}$), and their corresponding counts reported in a time-window
$C_{j\leq m,t_{i-1}\leq t\leq t_{i}}$. The bins’ edges (boundaries) are
defined by the MSSP in a way that maximizes the detection accuracy
(independent from the privacy mechanism), and the counts are collected in a
specified time-window and are aggregated in a matrix whose elements are time
series counts $C_{j\leq m,t_{i-1}\leq t\leq t_{i}}$. This count matrix is also
denoted by $C_{i}$ to save notations.

Distance Metrics [14]. For two probability distributions $p$ and $q$ over
$[N]=\\{1,\cdots,N\\}$, for some $N\in\mathbb{Z}_{+}$. (1) the Kolmogorov
distance between $p$ and $q$ is defined as
$d_{K}(p,q)\overset{\operatorname{def}}{=}\max_{j\in[N]}|\sum_{i=1}^{j}p(i)-\sum_{i=1}^{j}q(i)|$,
and (2) the total variation distance between $p$ and $q$ is defined as
$d_{TV}(q,p)=0.5\cdot\left\lVert q-p\right\rVert_{1}$ which is sometimes
called statistical distance. Note that $d_{K}(p,q)\leq d_{TV}(q,p)$.

Agnostic Learning [14]. Let $\mathcal{C}$ be a family of distributions over a
domain $\Omega$. Given sample access to an unknown distribution $p$ over
$\Omega$ and $0<\alpha,\beta<1$, the goal of an ($\alpha,\beta$)-agnostic
learning algorithm for $\mathcal{C}$ is to compute a hypothesis distribution
$h$ such that with probability at least $1-\beta$, it holds $d_{TV}(h,p)\leq
C\cdot opt_{\mathcal{C}}(p)+\alpha$; where
$opt_{\mathcal{C}}(p):=\inf_{q\in\mathcal{C}}d_{TV}(q,p)$ and $C\geq 1$ is a
universal constant.

###  II-B Differential Privacy

We follow the standard definition of $\epsilon$-differential privacy [15, 16].
Let $\mathsf{D}$ be a dataset of interest, and $d$, $d^{\prime}$ be two
adjacent subsets of $\mathsf{D}$ where $d^{\prime}$ can be obtained from $d$
by simply adding or subtracting the data of one individual. A randomization
mechanism $\mathcal{M}:\mathsf{D}\times\Omega\to\mathsf{R}$ is
$\epsilon$-differentially private if for all $S\subset\mathsf{R}$,

$\displaystyle\mathbb{P}(\mathcal{M}(d)\in S)\leq
e^{\epsilon}\mathbb{P}(\mathcal{M}(d^{\prime})\in S)\;\;$ (1)

If the inequality fails, then a leakage ($\epsilon$ breach) takes place. We
recall below a basic mechanism that can be used to answer queries in an
$\epsilon$-differentially private way.

While strong $\epsilon$-DP is ideal, utility may demand compromise. Precedent
exists for weaker privacy, with the definition of ($\epsilon,\delta$)-DP where
with small probability $\delta$, $\epsilon$-DP is allowed to fail. Another
relaxed notion is ($\epsilon,\gamma$)-Random Differential Privacy (RDP) [11],
where on all but a small $\gamma$-proportion of unlikely database pairs,
strong $\epsilon$-DP holds.

######  Definition II.1.

Randomized mechanism $\mathcal{M}_{q}:\mathsf{D}\times\Omega\to\mathbb{R}$
preserves ($\epsilon,\gamma$)-random differential privacy, at privacy level
$\epsilon>0$ and confidence $\gamma\in(0,1)$, if $\mathbb{P}[\forall
S\subset\mathsf{R},\mathbb{P}(\mathcal{M}(d)\in S)\leq
e^{\epsilon}\cdot\mathbb{P}(\mathcal{M}(d)\in S)]\geq 1-\gamma$, with the
inner probabilities over the mechanism’s randomization, and the outer
probability over neighbouring $d,d^{\prime}\in\mathsf{D}$ drawn from some
$P^{n+1}$.

###  II-C Laplace Mechanism

The Laplace mechanism modifies a numerical query result by adding zero-mean
noise (denoted as $Lap(b)$) subjecting to a Laplace distribution with mean
zero and scale parameter $b$. It has density
$p(x;b)=\frac{1}{2b}exp(-\frac{|x|}{b})$ and variance $2b^{2}$. The following
sensitivity concept plays an important role in the design of differentially
private mechanisms [5].

######  Definition II.2 (Global Sensitivity).

The sensitivity of a query $q:\mathsf{D}\to\mathsf{R}$ is defined as $\Delta
q=\max_{d,d^{\prime}:\text{Adj}(d,d^{\prime})}|q(d)-q(d^{\prime})|$ [15, 16].

######  Theorem II.1.

Let $q:\mathsf{D}\to\mathbb{R}$ be a query , $\epsilon>0$. Then the mechanism
$\mathcal{M}_{q}:\mathsf{D}\times\Omega\to\mathbb{R}$ defined by
$\mathcal{M}_{q}(d)=q(d)+w$, with $w\sim Lap(b)$, where $b\geq\frac{\Delta
q}{\epsilon}$, is $\epsilon$-differentially private [5].

###  II-D Pain-Free Algorithm [12]

Rubinstein et al. (the Pain-Free solution) developed an RDP mechanism using a
_sensitivity sampler_ , which approximates the global sensitivity with high
probability.

######  Definition II.3 (Approximate Sensitivity).

Consider sampling parameters size $1\ll m\in\mathbb{N}$ and order statistic
index $k\leq m\in\mathbb{N}$, the (k,m)-approximate sensitivity of a query
$q:\mathsf{D}\to\mathsf{R}$ is given by uniformly sampling $m$ sensitivity
candidates, sorts them, and picks the $k^{th}$ one to calibrate the Laplace
mechanism.

As shown in the following theorem, combined with generic mechanisms like
Laplace, such a sampler enables systematizing of privatization.

######  Theorem II.2 (Proof in [12])).

Consider any database $\mathsf{D}$ of $n$ records, privacy parameters
$\epsilon>0$, $\gamma\in(0,1)$, Kolmogorov approximation confidence
$0<\rho<\min\\{\gamma,1/2\\}$, and the known distribution $P$ on $\mathsf{D}$.
The Pain-Free algorithm defined as Laplace mechanism calibrated with
(k,m)-approximate sensitivity preserves ($\epsilon,\gamma$)-random
differential privacy, where
$m=\left\lceil\cfrac{\log(1/\rho)}{2(\gamma-\rho)^{2}}\right\rceil$,
$k=\left\lceil
m\big{(}1-\gamma+\rho+\sqrt{\cfrac{\log(1/\rho)}{2m}}\right\rceil$, and
$\rho=exp(W_{-1}(-\frac{\gamma}{2\sqrt{e}})+0.5)$.

The derived specific expressions involve branches of the Lambert-W function,
which is the inverse relation of the function $f(z)=z\cdot exp(z)$. Moreover,
a number of natural choices for sampling distribution $P$ could be made. In
particular, the Pain-Free algorithm and its privacy guarantee are derived by
assuming a uniform distribution defined over the domain of the dataset
$\mathsf{D}$. However, the accuracy of the solution can be significantly
boosted where a simulation process capable of approximating the actual $P$
exists, e.g., the anomaly scores computed by an MSSP can be leveraged.

##  III The DPOAD Framework

In this section, we introduce the main building blocks for our DPOAD
framework, provide a high level overview of our DPOAD framework and describe
its main steps.

###  III-A The Building Blocks

DPOAD relies on the following three modules; namely, the _DP Distribution
Learning_ , the _Monotonic Disentanglement_ and the _Count Reconstruction_
which are described below.

####  III-A1 DP Distribution Learning

One important building block of DPOAD is the distribution learning module.
This algorithm measures the closeness between distributions in total variation
distance ($d_{TV}$), and the goal is to construct a hypothesis $h$ from the
actual distribution $p$ such that (with high probability) the total variation
distance $d_{TV}(h,p)$ between $h$ and $p$ is at most $\alpha$, where
$\alpha>0$ is called the approximation confidence. Since the accuracy of the
sensitivity learning is directly linked to the soundness of the sensitivity
estimation (which is crucial for providing a sufficient degree of protection),
we consider two-phase operations for DPOAD, namely (1) the learning phase
($t<T$) over which a sufficiently large number of samples are provided to MSSP
(using the Pain-Free algorithm) to approximate the underlying distribution for
a desired confidence, and (2) the prediction phase ($t\geq T$) during which
the distribution learning can be considered as sufficiently “accurate”, and
therefore, the learnt distribution with its approximation confidence can be
successfully leveraged to the Pain-Free algorithm. The accuracy guarantee of
the learnt discrete distribution from a sufficient number of DP data samples
(sample complexity of
$\mathcal{O}(|\mathcal{D}|\log(1/\beta)/(\epsilon\alpha))$) is quite high as
proved in Theorem IV.1, and therefore, as shown in Section V, the value of $T$
is reasonably low (few iterations of communication). Figure 3 illustrates this
theoretical results for data samples collected from a smart home environment
in [17]. These phases are further described in the framework.

Figure 3: The average Kolmogorov error between the learnt distribution from DP
samples and the actual data distribution, for an excerpt of the smart home
dataset [17]. Figure 4: The density plot of the distribution of (a) the
example data, and (b) its anomaly scores. Figure (c) shows that mapping data
samples to their anomaly scores enables monotonic disentanglement

####  III-A2 Monotonic Disentanglement

This building block is required during the prediction phase to enable
effective anomaly detection with RDP. As shown in Figure 2, both small and
large sensitivity values (the height of the water) entail weak anomaly
detection results, specifically, the former introduces a large false positive
and the latter introduces a large false negative. This issue is inherent to
the notion of differential privacy with a constant or uniformly sampled
sensitivity value which essentially makes the mechanism ineffective for many
classification-based analyses including anomaly detection (see Section IV-D).
Therefore, an effective mechanism must provide some sort of quantified
disentanglement between benign and anomalous records (desired class of
detection from the rest of the dataset) when imposing any notion of
differential privacy. Fortunately, DPOAD can easily address this by leveraging
the granular probability distribution of the data using the anomaly scores,
meaning that the sensitivity to be sampled from a rather objective-oriented
(anomaly detectable) probability distribution.

Beside disentangling, another issue lies in the fact that anomalous records
can potentially take any value as shown in Figure 2 and Figure 4. Therefore,
sampling the sensitivity value, even merely from the benign records, may
contribute to very large values. Therefore, effective disentanglement ideally
maps the anomalous records to larger values so that tuning DP mechanism w.r.t.
benign values could preserve both privacy of the benigns and accuracy of the
anomaly detection. Figure 2 metaphorically shows such a desirable monotonic
(larger anomaly score$\rightarrow$ less protection) disentanglement property
that our DPOAD framework must prevail. Finally, Figure 4 shows that a perfect
monotonic and disentangled version of the original data could be generated
through mapping the data records to their assigned anomaly scores. This
finding is very intuitive because anomaly scores are essentially designed to
monotonically disentangle the outlier records from the benign ones in a given
dataset. We note that the fixed sensitivity bar shown in Figure 4(c) will look
like the shape of water if we “map back” the monotonic and disentangled
version of the data to its original format.

####  III-A3 Count Reconstruction

Clearly, the aforementioned mapping is crucial for DP to maintain the
functionality of anomaly detection, and has to be applied all the time (both
phases). However, since anomaly detection operates over counts, a count
reconstruction function must be applied prior to sending the data over. The
count reconstruction function is the reverse function of the monotonic
disentangler which generates pseudo-counts $\tilde{C_{i}}$ for the MSSP to
compute the new set of anomaly scores.

Figure 5: The high level overview of the DPOAD framework

###  III-B The Framework

As shown in Figure 5, DPOAD includes the following steps.

####  III-B1 DP Outsourcing at the Data Owner Side

Step 1:

At iteration $i$, the data owner releases an excerpt of her/his dataset
collected between time $t_{i-1}\leq t\leq t_{i}$; denoted by $D_{i\leq t}$;
for anomaly detection analysis, it specifies the desired degree of
differential privacy (DP) guarantee ($\epsilon$).

Step 2:

The data excerpt $D_{i}$ is converted into a histogram $H_{i}$ with a fixed
set of bins $B_{1},B_{2},\cdots,B_{k}$. The bins’ edges (boundaries) are
defined by the MSSP in a way that maximizes the detection accuracy
(independent from the privacy mechanism).

Step 3:

Next, the corresponding count matrix $C_{i}=\\{C_{\\{j\leq k,t_{i-1}\leq t\leq
t_{i}\\}}\\\ \in\mathcal{C}\\}$ consisting of time series counts of each bin
will undergo the RDP mechanism. 222Note that the privacy parameter $\gamma$ is
the same as the confidence probability of anomaly detection. Our analysis and
experiments show that running DPOAD with $\gamma\approx 0.2$ both converges
and preserves $\epsilon$-DP of benign records. This mechanism in the learning
phase, prior to learning iteration threshold $T$ (detailed in Section III-A1),
is the Pain-Free algorithm which exerts a Laplace mechanism with a sensitivity
value uniformly sampled from the domain of $\mathcal{C}$, and in the
prediction phase consists of the monotonic disentangler (described in Section
III-A2), Laplace mechanism and the count reconstruction function. In
particular, the disentangler transforms the counts to their anomaly scores
using the latest set of anomaly scores. The sensitivity of Laplace mechanism
is provably computed using the sensitivity learner (Step 6).

Step 4:

The privatized counts $\tilde{C}_{i}$ is outsourced to the MSSP to compute the
new set of anomaly scores.

####  III-B2 Sensitivity Update at the MSSP Side

Step 5:

The MSSP executes a score-based anomaly detection function, e.g., the
Kolmogorov–Smirnov test (KS test), over all the received pseudo-counts, and
generates the anomaly scores $S_{i}$ corresponding to data of iteration $i$.

Step 6:

The set of computed anomaly scores is analyzed using the sensitivity learner
module to update the sensitivity value for the next iteration. The operations
in this module includes (1) constructing the probability distribution of each
histogram bin’s counts ($P(\mathcal{C}))$) according to all previously
aggregated data and their anomaly scores (the higher score of an observation
is, the lower its probability mass function will become), (2) sampling $m$
sensitivities from the constructed distribution, sorting them and reporting
the $k^{th}$ one as $\Delta q_{i}$ where $m$ and $k$ are given in the Pain-
Free algorithm II.2, and (3) monotonic disetanglement mapping function to
generate an anomaly score version of the sensitivity $\Delta q^{\prime}_{i}$.

Step 7:

The anomaly detection report for iteration $i$ is sent back to the data owner.

1

Input : Dataset $D$, Privacy budgets $\epsilon$, Number of samples ($n$)
transmitted so far using Pain-Free, Learnt distribution $P$, Domain
$\mathcal{C}$, Histogram function $\mathcal{H}$, number of histogram bins $k$

2

Output : Set of identified Anomalies $S_{i}$

3

4Function(Private Cloud)

5 $G\leftarrow P(\mathcal{C})$

6 $m\leftarrow I\gg m$ in Theorem IV.2

7 $\rho^{*}\leftarrow\cfrac{p}{(m+q)^{r}}$

8 $k\leftarrow\left\lceil
m\big{(}1-\gamma+\rho^{*}+\sqrt{-\cfrac{\log(1-\sqrt{1-\rho^{*}}))}{2m}}\right\rceil$

9

10$Sens\leftarrow\\{\Delta q_{j\leq m}\sim G\\}$

11 $Sens\leftarrow sort(Sens)$

12 $\Delta q_{i}\leftarrow Sens(k)$

13

14$\tilde{H}_{i}=\\{B_{\\{j\leq k\\}},C_{\\{j\leq
k\\}}\\}\leftarrow\mathcal{H}(D_{i},k)$

15

16$\tilde{S}_{i}\leftarrow P(C_{\\{j\leq k\\}})$

17

18$\tilde{S}_{i}\leftarrow\tilde{S}_{i}+Lap(\frac{\Delta
q_{i}}{\epsilon_{i}})$

19

20$\mathcal{R}\leftarrow normalize(P^{-1}(\cdot))$

21 Function(MSSP)

22 $\tilde{C}_{i}\leftarrow\mathcal{R}(\tilde{S}_{i})$

23

24$S_{i}=\mathcal{A}(\tilde{H}_{1,2,\cdots,i})$: Analyzing all previously
received datasets to optimally identify anomalous records

25

26Update $P$

return $S_{i},P$

Algorithm 1 Prediction Phase Algorithm in DPOAD

Since DPOAD during learning phase merely focuses on distribution learning
using the Pain-Free algorithm, we summarize the above steps of DPOAD over the
prediction phase in Algorithm 1. Next, we analyze the privacy and utility of
DPOAD.

##  IV Analysis

In this section, we analyze privacy, utility and efficiency advantages of
DPOAD.

###  IV-A Privacy Analysis

Our analysis adapts the well-known findings in private distribution estimation
[14], which are reviewed as below. Sepecifically, let $\mathcal{C}_{N}$ be the
family of all distributions over $[N]$, the following holds:

######  Theorem IV.1.

There is a computationally efficient $\epsilon$-differentially private
$(\alpha,\beta)$-learning algorithm for $\mathcal{C}_{N}$ that uses
$n=\mathcal{O}((N+\log(1/\beta))/\alpha^{2}+N\log(1/\beta)/(\epsilon\alpha))$
samples.

Sketch Proof of Theorem IV.1. Diakonikolas et al. [14], by properties of the
Laplace distribution combining with the VC inequality [18] and the Dvoretzky-
Kiefer-Wolfowitz (DKW) inequality [19], showed that at least
$\mathcal{O}(N+\log(1/\beta)/\alpha^{2}+N\log(1/\beta)/(\epsilon\alpha^{2}))$
number of $\epsilon$-DP data samples is required to accurately
(($\alpha,\beta$)-learning) estimate the non-private discrete probability
distribution of the dataset.

####  IV-A1 Privacy Guarantee of DPOAD

We now present the required conditions for DPOAD to satisfy a desired level of
($\epsilon,\gamma$)-RDP.

######  Theorem IV.2.

The DPOAD framework satisfies ($\epsilon,\gamma$)-RDP if for the sensitivity
sampling parameters size $m$ , $k$ we have

$m=\begin{cases}\left\lceil\frac{\log(1/\rho)}{2(\gamma-\rho)^{2}}\right\rceil,&\text{Learning}\\\
\left\lceil\frac{-2\log(1-\sqrt{1-\rho})}{(T-\sqrt{T^{2}-4})^{2}}\right\rceil&\text{Prediction,}\end{cases}$
$k=\begin{cases}\left\lceil
m\Big{(}1-\gamma+\rho+\sqrt{\frac{\log(1/\rho)}{2m}}\Big{)}\right\rceil,&\text{Learning}\\\
\left\lceil
m\Big{(}1-\gamma+\rho+\sqrt{-\frac{\log(1-\sqrt{1-\rho}))}{2m}}\Big{)}\right\rceil,&\text{Prediction}\end{cases}$

where $T=2+\frac{n\cdot\epsilon_{i}}{2N\cdot c}$, and $c$ is the distribution
learning constant parameter for Laplace mechanism. Moreover, the $\rho^{*}$
values which minimize $k$ for a fixed $m$ in each state are

$\rho^{*}=\begin{cases}exp(W_{-1}(-\frac{\gamma}{2\sqrt{e}})+0.5),&\text{Learning}\\\
\frac{p}{(m+q)^{r}},&\text{Prediction.}\end{cases}$

where $p\approx 1.426$, $q\approx 0.8389$ and $r\approx 0.4589$.

###### Proof.

In the learning state, the ($\epsilon,\gamma$)-differentially private Pain-
Free algorithm is applied and the results in the Theorem are borrowed from
[12], so it remains to prove the privacy guarantee of the prediction phase. In
the prediction phase ($t\geq T$), let $\mathbb{P}_{\mathcal{C}}$ be the latent
distribution for the count values of a given histogram bin $B_{j}\leq k$. In
line with the sensitivity analysis given in [12], for the i.i.d. samples of
sensitivity $\Delta q_{1},\cdots,\Delta q_{m}$ drawn from $\mathcal{C}$,
denote the corresponding fixed unknown CDF, and corresponding random empirical
CDF, by

$\displaystyle\Phi(x)=\mathbb{P}_{\mathcal{C}}(\Delta q\leq x)$
$\displaystyle\Phi_{m}(x)=\frac{1}{m}\sum^{m}_{i=1}\mathds{1}(\Delta q_{i}\leq
x).$

However, DPOAD’s samples are drawn from DP estimated distribution
$\hat{\mathbb{P}}_{\mathcal{C}}$ learnt over a dataset $S$ of $n$ noisy
samples received by time $t$. Let $\hat{\Delta}q_{\\{i\leq m\\}}$ be the
ascending sorted sample sensitivities from $\hat{\mathbb{P}}_{\mathcal{C}}$,
and
$\hat{\Phi}_{m}(x)=\frac{1}{m}\sum^{m}_{i=1}\mathds{1}(\hat{\Delta}q_{i}\leq
x)$ be its corresponding random empirical CDF. Moreover, let
$\hat{\rho}\in(0,1)$ be the DKW probability error parameter, provided that

$1-\gamma+\rho+\hat{\rho}\leq 1\Leftrightarrow\rho^{\prime}\leq\gamma-\rho,$
(2)

then for the random sensitivity $\hat{\Delta}=\hat{\Delta}q_{k}$, where
$k=\lceil m(1-\gamma+\rho+\hat{\rho})\rceil$, we have
$\hat{\Phi}_{m}(\hat{\Delta})\geq 1-\gamma+\rho+\hat{\rho}$. Suppose
$\tilde{C}_{t}$ is the released set of DP counts generated by randomizing by
the current set of $C_{t}\in\mathbb{P}_{\mathcal{C}}$ in accordance with the
sample sensitivity $\hat{\Delta}$. Define the events

$\displaystyle
A_{\hat{\Delta}}=\\{\forall\mathsf{R}\subset\mathbb{R}^{n},\hat{\mathbb{P}}(\tilde{C}_{t}\in\mathsf{R})\leq
e^{\epsilon}\cdot\hat{\mathbb{P}}(\tilde{C^{\prime}}_{t}\in\mathsf{R})\\}$
$\displaystyle
B_{\rho^{\prime}}=\\{\sup\limits_{\hat{\Delta}}(\hat{\Phi}_{m}(\hat{\Delta})-\Phi(\hat{\Delta}))\leq\rho^{\prime}\\}$

The first is the event that DP holds for a specific DB pair, when the
mechanism is run with (possibly random) sensitivity parameter $\hat{\Delta}$;
the second records the empirical CDF uniformly one-sided approximating the CDF
to level $\rho^{\prime}$. Moreover, by definition of differential privacy, we
have

$\forall\Delta>0,\ \ \ \
\mathbb{P}_{\\{C_{t},C^{\prime}_{t}\in\mathbb{P}_{\mathcal{C}}\\}}(A_{\Delta})\geq\Phi(\Delta).$
(3)

Putting inequalities (2) and (3) together yields that

$\displaystyle\mathbb{P}_{\\{C_{t},C^{\prime}_{t},\hat{\Delta}q_{1},\cdots,\hat{\Delta}q_{m}\\}}(A_{\hat{\Delta}})=$
$\displaystyle\mathbb{E}(\mathds{1}[A_{\hat{\Delta}}]|B_{\rho^{\prime}})\mathbb{P}(B_{\rho^{\prime}})+\mathbb{E}(\mathds{1}[A_{\hat{\Delta}}]|\bar{B}_{\rho^{\prime}})\mathbb{P}(\bar{B}_{\rho^{\prime}})$
$\displaystyle\geq\mathbb{E}(\hat{\Phi}(\hat{\Delta})|B_{\rho^{\prime}})\mathbb{P}(B_{\rho^{\prime}})$
$\displaystyle\geq\mathbb{E}(\hat{\Phi}_{m}(\hat{\Delta})-\rho^{\prime}|B_{\rho^{\prime}})\mathbb{P}(B_{\rho^{\prime}})$

######  Lemma IV.3.

For all $\rho^{\prime}>0$, $\mathbb{P}(B_{\rho^{\prime}})$ in the DPOAD
methodology is tightly lower-bounded by
$\left[1-exp\left(-m\left(Q-\sqrt{Q^{2}-4}\right)^{2}/2\right)\right]^{2}$,
where $Q=2+\frac{n\cdot\epsilon}{2N\cdot m\cdot c}$ and $c$ is the hidden
constant term in
$\mathcal{O}(N+\log(1/\beta)/\alpha^{2}+N\log(1/\beta)/(\epsilon\alpha^{2}))$.

###### Proof.

Using triangle inequality, we have

$\displaystyle\mathbb{P}(B_{\rho^{\prime}})=\mathbb{P}\left(\\{\sup\limits_{\hat{\Delta}}(\hat{\Phi}_{m}(\hat{\Delta})-\Phi(\hat{\Delta}))\leq\rho^{\prime}\\}\right)$
$\displaystyle=\mathbb{P}\left(\\{\sup\limits_{\hat{\Delta}}\left(\hat{\Phi}_{m}(\hat{\Delta})-\hat{\Phi}(\hat{\Delta})+\hat{\Phi}(\hat{\Delta})-\Phi(\hat{\Delta})\right)\leq\rho^{\prime}\\}\right)$
$\displaystyle\geq\mathbb{P}\left(\\{\sup\limits_{\hat{\Delta}}(\hat{\Phi}_{m}(\hat{\Delta})-\hat{\Phi}(\hat{\Delta}))\\}\leq\rho^{\prime}-\\{\sup\limits_{\hat{\Delta}}(\hat{\Phi}(\hat{\Delta})-\Phi(\hat{\Delta}))\\}\right)$

The necessary condition for the last expression, denoted by $E$, to be a non-
zero probability is that we have
$\rho^{\prime}>\sup\limits_{\hat{\Delta}}\\{\hat{\Phi}(\hat{\Delta})-\Phi(\hat{\Delta})\\}$.
To tightly calculate $E$, our idea is to assume that we have
$\sup\limits_{\hat{\Delta}}\\{\hat{\Phi}(\hat{\Delta})-\Phi(\hat{\Delta})\\}\leq
x.\rho^{\prime}$ (event A) for a real-value $x<1$. We can then write
$E\geq\mathbb{P}(A)\cdot P(B|A)$, where $B|A$ is the event that
$\sup\limits_{\hat{\Delta}}\\{\hat{\Phi}_{m}(\hat{\Delta})-\hat{\Phi}(\hat{\Delta})\\}\leq(1-x).\rho^{\prime}$.
Moreover, from Theorem IV.1, we can easily show that for a set of $n$
$\epsilon$-DP data samples, we have

$\displaystyle\mathbb{P}(A)\geq 1-exp\left(\frac{N\epsilon
c-n\epsilon((1-x).\rho^{\prime})^{2}}{c\epsilon+Nc(1-x).\rho^{\prime}}\right)$
(4)

Moreover, using DKW inequality we have that for all
$\rho^{\prime}\geq\sqrt{\log{2}/(2m)}$,

$\displaystyle\mathbb{P}(B|A)=\mathbb{P}\left(\sup\limits_{\hat{\Delta}}\\{\hat{\Phi}_{m}(\hat{\Delta})-\hat{\Phi}(\hat{\Delta})\\}\leq(1-x)\cdot\rho^{\prime}\right)$
(5) $\displaystyle\geq 1-exp\left(-2m(1-x\rho^{\prime})^{2}\right)$

Using the inequality of arithmetic and geometric means, the multiplication of
the two probability lower-bounds 4 and 5 together is maximized when the two
terms 4 and 5 are equal. Solving this equality is equivalent to solving the
equality between the two exponent powers, which by some algebraic manipulation
and ignoring negligible terms returns
$x=\frac{Q-\sqrt{Q^{2}-4}}{2\rho^{\prime}}$ where
$Q=2+\frac{n\cdot\epsilon}{2N\cdot m\cdot c}$. Consequently, the maximum
lower-bound of $\mathbb{P}(B_{\rho^{\prime}})$ is

$\left[1-exp\left(-m\left(Q-\sqrt{Q^{2}-4}\right)^{2}/2\right)\right]^{2}$ (6)

∎

However, $Q$ has functionality of $m$. To get rid of this functionality, we
can introduce the following weaker lower-bound for
$\mathbb{P}(B_{\rho^{\prime}})$

$\left[1-exp\left(-m\left(T-\sqrt{T^{2}-4}\right)^{2}/2\right)\right]^{2}$ (7)

where $T=2+\frac{n\cdot\epsilon}{2N\cdot c}$. Therefore,

$\displaystyle\mathbb{P}_{\\{C_{t},C^{\prime}_{t},\hat{\Delta}q_{1},\cdots,\hat{\Delta}q_{m}\\}}(A_{\hat{\Delta}})$
$\displaystyle\geq\mathbb{E}(\hat{\Phi}_{m}(\hat{\Delta})-\rho^{\prime}|B_{\rho^{\prime}})$
$\displaystyle\geq(1-\gamma-\rho+\rho^{\prime}-\rho^{\prime})\left[1-exp\left(-m\left(T-\sqrt{T^{2}-4}\right)^{2}/2\right)\right]^{2}$
$\displaystyle\geq(1-\gamma-\rho)(1-\rho)\geq(1-\gamma+\rho-\rho)=1-\gamma$

The last inequality follows from $\rho<\gamma$; the penultimate inequality
follows from
$m\geq\left\lceil\frac{-2\log(1-\sqrt{1-\rho})}{(T-\sqrt{T^{2}-4})^{2}}\right\rceil$.
Therefore,

$m=\begin{cases}\left\lceil\frac{\log(1/\rho)}{2(\gamma-\rho)^{2}}\right\rceil,&\text{learning~{}\cite[cite]{[\@@bibref{}{pmlr-v70-rubinstein17a}{}{}]}}\\\
\left\lceil\frac{-2\log(1-\sqrt{1-\rho})}{(T-\sqrt{T^{2}-4})^{2}}\right\rceil&\text{Prediction}\end{cases}$

Finding the expression for $k$, we note that since both $0<x<1$ then

$\displaystyle\left[1-e^{\\{-2m\rho^{\prime
2}\\}}\right]^{2}\geq\left[1-exp\left(-m(T-\sqrt{T^{2}-4})^{2}/2\right)\right]^{2}$
$\displaystyle\geq 1-\rho$

By some straightforward algebraic manipulation, we have
$\rho^{\prime}\geq\sqrt{-\frac{\log(1-\sqrt{1-\rho}))}{2m}}$, and hence,

$k=\begin{cases}\left\lceil
m\big{(}1-\gamma+\rho+\sqrt{\frac{\log(1/\rho)}{2m}}\right\rceil,&\text{learning~{}\cite[cite]{[\@@bibref{}{pmlr-v70-rubinstein17a}{}{}]}}\\\
\left\lceil
m\big{(}1-\gamma+\rho+\sqrt{-\frac{\log(1-\sqrt{1-\rho}))}{2m}}\right\rceil,&\text{Prediction}\end{cases}$

Finally, to find the optimal $\rho^{*}$ which minimizes $k$ for a fixed $m$ in
the prediction phase, the following is the best computed fit function.

$\rho^{*}\approx\begin{cases}exp(W_{-1}(-\frac{\gamma}{2\sqrt{e}})+0.5),&\text{Learning~{}\cite[cite]{[\@@bibref{}{pmlr-v70-rubinstein17a}{}{}]}}\\\
\frac{1.426}{(m+0.8389)^{0.4589}},&\text{Prediction.}\end{cases}$

∎

###  IV-B On the Relationship Between RDP and DP

######  Theorem IV.4.

A Laplace mechanism which calibrates (k,m)-approximate sensitivity
$\hat{\Delta}=\hat{\Delta}q_{k}$, where $k=\lceil
m(1-\gamma+\rho+\hat{\rho})\rceil$, preserves $\epsilon$-DP for all benign
records with probability 1.

###### Proof.

We have $\hat{\Phi}_{m}(\hat{\Delta})\geq 1-\gamma+\rho+\hat{\rho}$.
Therefore, for all records where $\gamma\leq\rho+\hat{\rho})$, we have
$\hat{\Phi}_{m}(\hat{\Delta})=1$ and $k=m$. Such records are those who have
been frequently observed (non-anomalous) and as a result their estimation
error are smaller than $\gamma$. ∎

###  IV-C Utility Analysis

Motivated by the analysis presented by Asif et al. [7], to formally analyze
the utility pay-off of DPOAD, we employ the following abstraction of the
process in privacy preserving anomaly detection algorithms. Suppose the
anomaly identification algorithm is a binary functions
$f:D\rightarrow\\{0,1\\}$, and let $\mathcal{M}$ be the DP mechanism that is
supposed to compute $f$. Now let $x$, $y$ be two databases that differ in one
record and that $f(x)=0$ and $f(y)=1$. Asif et al. [7] have shown that the
differential privacy constraints create a trade-off, i.e., one of the two
following expressions always holds.

$\displaystyle\mathbb{P}(\mathcal{M}(x)\neq f(x))\geq 1/(1+e^{\epsilon})\ \
\text{or}$ $\displaystyle\mathbb{P}(\mathcal{M}(y)\neq f(y))\geq
1/(1+e^{\epsilon}).$

which means that with an intensity depending on the value of $\epsilon$ (the
higher the privacy requirements are, i.e. for smaller $\epsilon$ the stricter
this trade-off is), any DP anomaly identification solution always entails high
rate of either false positive or false negative. As a result, this trade-off
leads to a very low precision rate for DP anomaly detection algorithms [7]. In
the following theorem, we show that by virtue of clever sensitivity adjustment
and monotonic disentanglement, DPOAD can vastly improve on this trade-off.

######  Theorem IV.5.

Precision of the DPOAD algorithm is at least

$\displaystyle\frac{2+e^{-\epsilon((m/k)+1)}-e^{-\epsilon}-2e^{-\epsilon
m/k}}{2+e^{-\epsilon((m/k)+1)}-e^{-\epsilon m/k}-2e^{-\epsilon}}$ (8)

times better than anomaly detection using Laplace mechanism.

###### Proof.

From [7] (Claim 1 and Figure 1), we have $\mathbb{P}(\mathcal{M}(x)\neq
f(x))\propto e^{\epsilon}(\mathbb{P}(\mathcal{M}(y)\neq f(y)))$. On ther hand,
from Theorem IV.2, we can tune DPOAD such that $k$ minimizes w.r.t a fixed
$m$. Since DPOAD applies monotonic disentanglement on the data values, the
quantile level $k/m$ can be seen as an indication of the probability of
$\mathbb{P}(\mathcal{M}(y)\neq f(y))$. As a result, we have

$\displaystyle\mathbb{P}(\mathcal{M}(x)\neq f(x))\propto
e^{\epsilon}(\mathbb{P}(\mathcal{M}(y)\neq f(y))),\ \ \ \ \ \ \ \ \ \ \
\text{Laplace}$ $\displaystyle\mathbb{P}(\mathcal{M}(x)\neq f(x))\propto
e^{\epsilon m/k}(\mathbb{P}(\mathcal{M}(y)\neq f(y))),\ \ \ \ \ \
\text{DPOAD}$

Denoting by $0\leq p,q\leq 1$, respectively, the true negative and the true
positive (complements of the above) probabilities, we have

$Precision:\frac{q}{1-p+q}\leq\begin{cases}\frac{1-e^{-\epsilon}(1-p)}{1-p+1-(e^{-\epsilon}(1-p))}&\text{Laplace}\\\
\frac{1-e^{-\epsilon m/k}(1-p)}{1-p+1-(e^{-\epsilon
m/k}(1-p))}&\text{DPOAD}\end{cases}$

It is easy to verify that for all choices of $p$, the DPOAD precision is
placed higher because $m/k\geq 1$ and the expression is strictly increasing
w.r.t. $m/k$. Hence, let $x=1-p$ and denote by $\mathsf{R}$ the precision
ratio between the later and the former, we can easily show that this ratio
w.r.t. $x$ is strictly increasing.

$\displaystyle\mathsf{R}\geq\frac{2+e^{-\epsilon((m/k)+1)}-e^{-\epsilon}-2e^{-\epsilon
m/k}}{2+e^{-\epsilon((m/k)+1)}-e^{-\epsilon m/k}-2e^{-\epsilon}}$

∎

where the expression on the left is “the worst case” improvement achieved at
$x=1$. This bound is extremely loose lower-bound since we have assumed a
“linear relation” between $k/m$ and strictness of the FP/FN tradeoff, while
DPOAD uses a more granular PDF for more accurate TP predictions as shown in
our experiments.

###  IV-D Discussion

Finally, we discuss some important aspects of DPOAD which are derived from our
results in Sections IV and V.

Tuning $n$ in the Learning Phase. What number of samples is sufficient to stop
the learning phase and switch to the prediction phase? Parameter $n$, as shown
in Theorem IV.2, affects parameters $k$ and $m$, which ultimately impact the
quality of anomaly detection. In particular, if in the learning phase the
underlying distribution is not learnt accurately due to a small number of
samples ($n\downarrow\rightarrow T\downarrow\rightarrow m\downarrow$), we have
$k\approx m$ which results in inaccurate anomaly detection (refer to Utility
Analysis IV-C). Therefore, it is important to ensure that a sufficient number
$n$ of samples is aggregated by the MSSP to certifiably benefit from accurate
anomaly detection. Figure 6 (b) depicts a picture of the utility pay-off of
DPOAD for various privacy parameters if a sufficiently large number of samples
is used for learning the distribution of the dataset.

Tuning the Sensitivity Quantile Levels $k/m$. Figure 6 (a) depicts the
sensitivity quantile levels $k/m$ in both the learning and the prediction
phases for different RDP parameter $\gamma$. This figure clearly shows this
important parameter in the learning phase (Pain-Free) is negligibly better
than in the prediction phase. This is expected since in the prediction phase,
sensitivity sampling is conducted according to a learnt distribution over
noisy observations which obviously entails less confidence and consequently,
prevails a more conservative quantile value. Nonetheless, our experiments show
that it is good enough for DPOAD to operate significantly better than the
Pain-Free thanks to its monotonic disentangling function.

Figure 6: The (a) sensitivity quantile level $k/m$ in the Prediction and the
Learning (Pain-Free) phases, and (b) precision pay-off (%) in DPOAD for
different $\epsilon$ and $\gamma$ parameters.

DPOAD in Other Statistical Inferences.

Besides application of DPOAD in many use cases including IoT, fraud detection
and resource/budget allocations (see the experiments), it can be used to
compute various interesting data analysis functions in the outsourcing
setting. In particular, DPOAD can be deployed to enable a specific type of
analysis through iteratively constructing a monotonic disentangled version of
the dataset according to what algorithm demands. For instance, in the heavy
hitter (HH) computation, DPOAD can be applied with minor modifications.
Specifically, MSSP at each iteration computes the distribution of the dataset
and sends the heavy hitter scores back to the data owner. The monotonic
disentangler can be tuned using these scores to preserve the privacy of all
non-HH entries while enabling accurate HH identification. Other potential
algorithms include SQL queries, clustering and optimal distribution learning.

DPOAD and Non-Interactive DP. Instead of histogram, we can apply DPOAD to the
DP raw data publishing algorithms, namely non-interactive solutions.
Unfortunately, the state-of-the-art is still struggling to find accurate and
scalable non-interactive solutions and most of existing approaches usually
result in significant utility loss [20]. DPOAD can be applied to boost utility
for practical non-interactive solutions.

Efficiency Analysis. Table I summarizes the computational and communication
complexity for the main action items of DPOAD.

TABLE I: Complexities of DPOAD’s main functions

Function Computation Communication Distribution Learning $O(n\log{N})$
$\mathcal{O}((N+\log(1/\beta))/\alpha^{2}$ $+N\log(1/\beta)/(\epsilon\alpha))$
Monotonic Disentanglement $O(nlog^{n})$ — Pain-Free Algorithm $O(nlog^{n})$ —
Anomaly Detection (KS) $O(n^{2})$ —

##  V Experimental Evaluations

In this section, we experimentally evaluate the performance of DPOAD using a
diverse collection of well-known datasets, including the parking Birmingham
dataset [21], individual household electric power consumption dataset [22],
credit card clients dataset [23] and KDDCup99 dataset [24].

More specifically, the parking dataset consists of the occupancy rates of 31
parking lots in Birmingham for 2 months in 2016. The individual household
electric power consumption dataset contains around 2 million power consumption
measurements in 47 months from 2006 to 2010 in France. The credit card clients
dataset consists of customers default payments in Taiwan in 2005. The KDDCup99
dataset consists of “good” and “bad” network connections simulated in a
military network environment. The anomaly detection in our experiments is
based on the histogram combination of all the attributes in every dataset.
Table II summarizes the characteristics of the datasets.

TABLE II: Characteristics of the experimental datasets

Databset Size # of Attributes Parking Birmingham [21] 35,718 4 Electric
consumption [22] 2,075,259 9 Credit card clients [23] 30,000 23 KDDCup99 [24]
494,021 42

###  V-A Experimental Setting

We perform all the experiments and comparisons on both privacy parameters
($\epsilon$ and $\gamma$) and anomaly detection parameters (the Threshold T
and the sensitivity $\Delta q$). DPOAD is benchmarked with the Laplace
mechanism and the recent Pain-Free mechanism for differential privacy.333[6,
8, 9, 7, 10] can only disclose analysis results, i.e., detected anomalies
(rather than data). Thus, they are incomparable with DPOAD. We apply the
original anomaly detection algorithm on all the datasets to obtain the
baseline results in all the experiments for evaluating the accuracy of DPOAD
and benchmarks.

(a) Parking

(b) Electric Consumption

(c) Credit Card

(d) KDDCup99

Figure 7: Time Performance Comparison of Local Setting and DPOAD
(Outsourcing).

Definition of Anomalies. In all the experiments, the MSSP runs anomaly
detection based on Kolmogorov-Smirnov (KS) test [25]. It is widely used in
anomaly detection [26, 27] as a reliable score-based anomaly detection.
Specifically, it defines and compares the distribution of the training and
testing sets. The randomly sampled training data can be transformed to a
uniform distribution. Then, we apply the same transformation as defined in
training data to test if the testing data points fall in the same uniform
distribution on the $p$-dimensional hybercube. Any data point falls outside of
the distribution would be considered as anomalies in this case. In general,
the KS test evaluates the null hypotheses that the class labels predicted by a
classifier are no better than random [28].

Privacy Parameters. In the first set of our experiments, we examine the
accuracy of DPOAD on varying privacy parameters $\epsilon$ and $\gamma$, using
two well-known accuracy metrics: precision and recall. In this group of
experiments, we set the anomaly detection threshold as 0.9 and the number of
analysis iterations as 5, respectively.

In the initialization, we first sample the sensitivity $\Delta q$ from the
uniform distribution defined over all possible values of a dataset. In the
next iteration, we then update the underlying distribution using the anomaly
scores computed by an MSSP and sample the new sensitivity with updated
distribution.

Anomaly Detection Parameters. In the second set of our experiments, we
investigate how DPOAD behaves under different detection thresholds T and
iterations from an MSSP. The threshold is the parameter that shows the
abnormal rate in a dataset, which would affect the utility. Since the sample
sensitivity $\Delta q$ in each iteration from the MSSP should be updated, the
corresponding noise would then be different in each iteration. We run all
experiments in the second set by fixing the privacy budget ($\epsilon=1$ and
$\gamma=0.05$) and tuning anomaly detection parameters.

Platform. The experiments on the cloud (outsourced computation in DPOAD) were
performed on the NSF Chameleon Cluster with Intel(R) Xeon(R)Gold 6126 2.60GHz
CPUs and 192G RAM. The experiments under local setting were performed on an HP
PC with Intel Core i7-7700 CPU 3.60GHz and 32G RAM.

###  V-B Computation Advantage

The first group of experiments are conducted to evaluate the runtime of the
algorithms by comparing the local anomaly detection and DPOAD (local noise
injection and outsourced computation). We run all the algorithms on different
percents of the overall data (the same four datasets). Figure 7 shows that the
local computation can be significantly reduced if outsourcing the data to the
cloud. Since the anomaly detection in the cloud is completed by multiple
computing nodes with parallel computation, the runtime by the cloud is also
significantly reduced compared to performing local anomaly detection.

(a) Precision vs $\epsilon$

(b) Recall vs $\epsilon$

(c) Precision vs $\epsilon$

(d) Recall vs $\epsilon$

(e) Precision vs $\epsilon$

(f) Recall vs $\epsilon$

(g) Precision vs $\epsilon$ (h) Recall vs $\epsilon$

Figure 8: Precision and Recall vs $\epsilon$ on the parking dataset (a,b),
electric consumption dataset (c,d), credit card clients dataset (e,f) and
KDDCup99 dataset (g,h).

###  V-C Privacy Parameters

We study the effectiveness of DPOAD by varying the privacy parameters, i.e.,
$\epsilon$ and $\gamma$ in all experiments is fixed to $0.1$ which regards to
the accuracy of the PDF estimator in the learning phase. The precision and
recall values shown in the figures are calculated based on the baseline
results (the results are obtained without any injected noise). In the studied
accuracy metrics, recall shows the sensitivity of the approaches, while
precision demonstrates the ratio of correctly identified anomalies.

####  V-C1 Accuracy vs Privacy Budget $\epsilon$

For each dataset, as described in Table II, we evaluate the accuracy for
anomaly detection based on two metrics by varying $\epsilon$ ($\gamma$ is
fixed as 0.3 in this set of experiments). Laplace mechanism has been used as
the baseline in all the studies. Overall, the value of metrics increases when
the privacy budget increases. Specifically, we have the following observation:

  * •

In Figure 8, the DPOAD-based anomaly detection is significantly more accurate
than Laplace and Pain-Free with the same privacy budget for all the datasets.
The precision and recall results are much higher than the benchmarks. This is
because the noise injected to anomalies by DPOAD is much smaller, and thus
more anomalies can be accurately identified.

  * •

Similar to the two other solutions, the accuracy of DPOAD-based anomaly
detection increases as the privacy protection becomes weaker (larger
$\epsilon$), and the accuracy also relies on the characteristics of the
datasets. For example, compared to other datasets the records in both credit
card clients are more homogeneous, which lead to slightly smaller recall
values in Figure 8(f). It is worth noting that the recall values can be simply
improved by applying better anomaly detection algorithms w.r.t. such type of
datasets.

Summary. DPOAD achieves much better precision and recall results than two
benchmarks on all the datasets. In both strong and weak privacy cases, DPOAD
identifies anomalies more accurately.

(a) Precision vs Threshold

(b) Recall vs Threshold

(c) Precision vs Threshold

(d) Recall vs Threshold

(e) Precision vs Threshold

(f) Recall vs Threshold

(g) Precision vs Threshold

(h) Recall vs Threshold

Figure 9: Precision and Recall vs Detection Threshold (T) on the parking
dataset (a,b), electric consumption dataset (c,d), credit card clients dataset
(e,f) and KDDCup99 dataset (g,h).

###  V-D Anomaly Detection Parameters

This group of experiments is conducted to provide insights about the anomaly
detection parameters in the six datasets for DPOAD and two benchmarks. In
particular, Figure 9 depicts the impact of the chosen threshold on anomaly
detection, while Table III shows the impact of the number of analysis
iterations.

####  V-D1 Accuracy vs Detection Threshold

Unlike the anomaly detection, i.e., the ground truth for comparison is fixed,
the threshold in this set of experiments also impacts the baseline solution.
Thus, the recall and precision in all the experiments grow when the threshold
increases. This confirms that DPOAD can apply minor noise in the explicit
anomalies, i.e., threshold $\geq$ 0.95, while only applying privacy to normal
data. Specifically, with a smaller pool of highly anomalous items (higher
threshold), DPOAD has a even better precision and recall on all the datasets.
On the contrary, the accuracy of Laplace cannot increase much as the threshold
increases.

TABLE III: Precision and Recall vs Analysis Iterations.

Parking Dataset | Electric Consumption Dataset
---|---
|  | Iteration | 1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---|---|---
Precision | Laplace | 0.00 | 0.05 | 0.13 | 0.18 | 0.24 | 0.25
Painfree | 0.03 | 0.04 | 0.23 | 0.28 | 0.38 | 0.41
DPOAD | 0.20 | 0.43 | 0.68 | 0.80 | 0.82 | 0.84
Recall | Laplace | 0.00 | 0.00 | 0.01 | 0.07 | 0.08 | 0.11
Painfree | 0.00 | 0.11 | 0.13 | 0.19 | 0.23 | 0.27
DPOAD | 0.10 | 0.26 | 0.33 | 0.45 | 0.56 | 0.63
|  | Iteration | 1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---|---|---
Precision | Laplace | 0.00 | 0.05 | 0.08 | 0.17 | 0.19 | 0.20
Painfree | 0.11 | 0.25 | 0.30 | 0.48 | 0.52 | 0.58
DPOAD | 0.27 | 0.37 | 0.47 | 0.63 | 0.77 | 0.83
Recall | Laplace | 0.00 | 0.01 | 0.01 | 0.01 | 0.03 | 0.03
Painfree | 0.01 | 0.02 | 0.13 | 0.23 | 0.35 | 0.41
DPOAD | 0.25 | 0.42 | 0.50 | 0.55 | 0.58 | 0.67

Credit Card Clients Dataset | KDDCup99 Dataset
---|---
|  | Iteration | 1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---|---|---
Precision | Laplace | 0.20 | 0.22 | 0.24 | 0.25 | 0.28 | 0.32
Painfree | 0.23 | 0.34 | 0.36 | 0.37 | 0.40 | 0.41
DPOAD | 0.38 | 0.44 | 0.50 | 0.62 | 0.74 | 0.81
Recall | Laplace | 0.00 | 0.00 | 0.02 | 0.04 | 0.05 | 0.05
Painfree | 0.01 | 0.02 | 0.06 | 0.08 | 0.08 | 0.10
DPOAD | 0.21 | 0.29 | 0.33 | 0.40 | 0.57 | 0.60
|  | Iteration | 1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---|---|---
Precision | Laplace | 0.00 | 0.08 | 0.15 | 0.22 | 0.27 | 0.37
Painfree | 0.33 | 0.39 | 0.43 | 0.47 | 0.56 | 0.64
DPOAD | 0.42 | 0.52 | 0.60 | 0.71 | 0.75 | 0.81
Recall | Laplace | 0.00 | 0.01 | 0.02 | 0.05 | 0.10 | 0.11
Painfree | 0.04 | 0.05 | 0.06 | 0.06 | 0.10 | 0.17
DPOAD | 0.36 | 0.37 | 0.43 | 0.49 | 0.55 | 0.67

####  V-D2 Accuracy vs Analysis Iteration

In this set of experiments, we study the effectiveness of the analysis
iterations on each dataset. Recall that the data owner releases the dataset
collected between time $t_{i-1}\leq t\leq t_{i}$ in each iteration $i$. To
simulate that, we then add $1000$ new records into the dataset in each
iteration. To establish a comparison with Laplace and Pain-Free mechanisms, we
implemented those two mechanisms in an interactive manner between the MSSP and
data owner. However, DPOAD would sample the sensitivity in each iteration
according to the MSSP-updated PDF, while Laplace and Pain-Free utilize the
global sensitivity and uniformly sampled sensitivity, respectively.

As shown in Table III, for all mechanisms, we first observe that both
precision and recall increase with more analysis iterations by the MSSP.
However, as the number of iterations increases, the precision and recall of
Laplace and Pain-free mechanisms only have minor improvement compared to
DPOAD. Thus, we also observe that the DPOAD can achieve a much better accuracy
on all the datasets (e.g., $\sim$500% better recall results than Laplace and
Pain-Free on the credit card clients dataset).

The main reason is that DPOAD benefits from the MSSP-updated PDF to select the
sensitivity in each iteration, the sensitivity should be smaller as the
iteration number increases. On the contrary, since the sensitivity in Laplace
and Pain-Free has to be very large in each iteration, the accuracy of these
two benchmarks cannot be high.

Summary. The above experiments have validated the effectiveness of DPOAD to
improve the precision and recall in anomaly detection while ensuring
$(\epsilon,\gamma)$-differential privacy. A better accuracy could also be
achieved by performing the analysis with more iterations, e.g., 6 analysis
iterations in our experiments could achieve as high as 0.84 precision and 0.67
recall by DPOAD (the results can be even better if we relax the privacy
protection). All the experiments on different datasets have validated the
practicality of DPOAD.

##  VI Related Work

Most existing works recognized the paradox between anomaly detection and
differential privacy (DP) due to the indistinguishability property. Okada et
al. [9] first highlights such a conflict. To solve this paradox, a DP
relaxation is inevitable, particularly for existence-dependent queries, to
ensure a certain level of detection accuracy. Thus, all DP-based works have
defined their own relaxed DP notion, which generally make them applicable to
limited cases (e.g., Anomaly-restricted privacy [6], and sensitive privacy
[7]). In contrast, we define our relaxed DP with the Random Differential
Privacy (RDP) [13] to protect specific percent of data with $\epsilon$-DP.

Furthermore, most of the existing works do not consider outsourcing the
anomaly detection task as they mainly rely on the fact that the anomaly
detection is locally performed on the data and only the analysis result is
provided with DP. Instead, DPOAD performs anomaly detection on the outsourced
data (generated by the DP algorithm), which is more practical since the
clients do not need to perform expensive analysis.

Okada et al. [9] introduce a mechanism based on the smooth upper bound of the
local sensitivity (a relaxed DP) and use it in a limited setting. The approach
does not report the detected outliers but cover two types of DP queries:
outlier counting and top-h subspaces with a large number of outliers.
Similarly, several other approaches (e.g., [6, 10, 29, 8]) propose to
relax/generalize DP and design anomaly detection methods with DP. Most of such
approaches are data-dependent and can only be performed under a specific
setting. For instance, Bittner et al. [6] defines the anomaly-restricted DP
and proposes a group-based search algorithm for this relaxed notion. However,
their approach relies on input datasets that have a single outlier, which is
different from our approach. Asif et al. [10, 29] considers DP in the
collaborative outlier detection where data is either vertically or
horizontally distributed among multiple parties. However, such approach works
only for datasets with certain characteristics (i.e., categorical data) and
its extension to numeric data using discretization can limit the types of
detectable outliers with reduced data usability. In contrast to them, we
consider a more general and practical model including any number of anomalies.

Moreover, Asif et al. [7] generalizes DP and defines sensitive privacy, which
determines sensitive records after quantifying the database. Böhler et al. [8]
assumes that the data owner already knows the outliers and excludes them from
the dataset before adapting the sensitivity to the remaining data. It also
relies on the trust between the analyst and a new entity called the correction
server whose role is to increase the accuracy of the outlier detection.

##  VII Conclusion

We propose a novel solution called DPOAD to address the problem of privacy-
preserving outsourcing of anomaly detection by decreasing the privacy of the
anomalies through communication between the data owners and the data analysts.
We show that DPOAD can significantly improve the accuracy of the analysis for
the data with abnormal behaviour while preserving the privacy of the data with
normal behavior. The system receives the input from the data owners and the
data analysts. Each data owner, to build a reliable estimation of the
sensitivity, releases sufficient number of DP version of their dataset (non
suitable for anomaly detection) to analysts. The analyst provides owners with
distribution of their data which can be used to estimate an updated
sensitivity value using the calculated anomaly scores for records. The
framework can be used in settings with one or more data owners. We formally
benchmark DPOAD under DP-Histogram publishing and showcase the performance
improvements.

## References

  * [1] Deepali Deshpande.  Managed security services: An emerging solution to security.  In Proceedings of the 2nd Annual Conference on Information Security Curriculum Development, InfoSecCD ’05, page 107–111, New York, NY, USA, 2005. Association for Computing Machinery.
  * [2] Margaret Davino.  Assessing privacy risk in outsourcing.  ”A” Journal of AHIMA 75, 3:42–46, 2004.
  * [3] Thien Duc Nguyen, Samuel Marchal, Markus Miettinen, Hossein Fereidooni, N Asokan, and Ahmad-Reza Sadeghi.  Dïot: A federated self-learning anomaly detection system for iot.  In ICDCS, pages 756–767, 2019.
  * [4] Cynthia Dwork.  Differential privacy: A survey of results.  In Theory and Applications of Models of Computation, pages 1–19, 2008.
  * [5] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, pages 265–284, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
  * [6] Daniel M. Bittner, Anand D. Sarwate, and Rebecca N. Wright.  Using noisy binary search for differentially private anomaly detection.  In Cyber Security Cryptography and Machine Learning, pages 20–37, 2018.
  * [7] Hafiz Salman Asif, Periklis A. Papakonstantinou, and Jaideep Vaidya.  How to accurately and privately identify anomalies.  In Proceedings of the Computer and Communications Security, pages 719–736, 2019.
  * [8] Jonas Böhler, Daniel Bernau, and Florian Kerschbaum.  Privacy-preserving outlier detection for data streams.  In IFIP Annual Conference on Data and Applications Security and Privacy, pages 225–238. Springer, 2017.
  * [9] Rina Okada, Kazuto Fukuchi, and Jun Sakuma.  Differentially private analysis of outliers.  In Machine Learning and Knowledge Discovery in Databases, volume 9285, pages 458–473, 2015.
  * [10] Hafiz Salman Asif, Tanay Talukdar, Jaideep Vaidya, Basit Shafiq, and Nabil R. Adam.  Collaborative differentially private outlier detection for categorical data.  In CIC, pages 92–101, 2016.
  * [11] Robert Hall, Larry Wasserman, and Alessandro Rinaldo.  Random differential privacy.  Journal of Privacy and Confidentiality, 4(2), Mar. 2013.
  * [12] Benjamin I. P. Rubinstein and Francesco Aldà.  Pain-free random differential privacy with sensitivity sampling.  IMCL, pages 2950–2959, 2017.
  * [13] Robert Hall, Larry Wasserman, and Alessandro Rinaldo.  Random differential privacy.  Journal of Privacy and Confidentiality, 4(2), 2013.
  * [14] Ilias Diakonikolas, Moritz Hardt, and Ludwig Schmidt.  In Advances in Neural Information Processing Systems, volume 28, pages 2566–2574, 2015.
  * [15] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil P. Vadhan.  On the complexity of differentially private data release: efficient algorithms and hardness results.  In STOC, pages 381–390, 2009.
  * [16] Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith.  Smooth sensitivity and sampling in private data analysis.  In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 75–84, 2007.
  * [17] Simon Birnbach, Simon Eberz, and Ivan Martinovic.  Peeves: Physical event verification in smart homes.  In Proceedings of the Conference on Computer and Communications Security, page 1455–1467, 2019.
  * [18] Luc Devroye and Gábor Lugosi.  Combinatorial methods in density estimation.  Springer Science & Business Media, 2012.
  * [19] A. Dvoretzky, J. Kiefer, and J. Wolfowitz.  Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator.  The Annals of Mathematical Statistics, 27(3):642–669, 1956.
  * [20] Rui Chen, Noman Mohammed, Benjamin CM Fung, Bipin C Desai, and Li Xiong.  Publishing set-valued data via differential privacy.  Proceedings of the VLDB Endowment, 4(11):1087–1098, 2011.
  * [21] Daniel H. Stolfi, Enrique Alba, and Xin Yao.  Predicting car park occupancy rates in smart cities.  In Smart Cities - Second International Conference, Smart-CT 2017, Málaga, Spain, June 14-16, 2017, Proceedings, volume 10268, pages 107–117, 2017.
  * [22] Individual household electric power consumption data set, 2020.  https://archive.ics.uci.edu/ml/datasets/Individual+household+electric+power+consumption.
  * [23] I-Cheng Yeh and Che-hui Lien.  The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients.  Expert Syst. Appl., 36(2):2473–2480, 2009.
  * [24] Kdd cup 1999 data, 2020.  http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html.
  * [25] Michael Kim.  Anomaly detection, 2020.  https://www.mathworks.com/matlabcentral/fileexchange/39593-anomaly-detection.
  * [26] Nour Moustafa and Jill Slay.  The evaluation of network anomaly detection systems: Statistical analysis of the unsw-nb15 data set and the comparison with the kdd99 data set.  Information Security Journal: A Global Perspective, 25(1-3):18–31, 2016.
  * [27] Ana Justel, Daniel Peña, and Rubén Zamar.  A multivariate kolmogorov-smirnov test of goodness of fit.  Statistics & Probability Letters, 35(3):251–259, 1997.
  * [28] Andrew P. Bradley.  Roc curve equivalence using the kolmogorov–smirnov test.  Pattern Recognition Letters, 34(5):470–475, 2013.
  * [29] Hafiz Salman Asif, Tanay Talukdar, Jaideep Vaidya, Basit Shafiq, and Nabil R. Adam.  Differentially private outlier detection in a collaborative environment.  Int. J. Cooperative Inf. Syst., 27(3):1850005:1–1850005:36, 2018\.


ISIS light curves. For 29 sources, the ISIS light curves had fewer systematic
errors. The remaining 7 light curves were ambiguous, in that both the
TESSreduce and ISIS light curves were of comparable quality, but showed
differing shapes and amplitudes for the SN signal. In these cases, we use the
difference imagining light curves for consistency, although we also mark these
sources in Table 1. Figure 15 shows examples of light curves from TESSreduce
and ISIS. However, a full comparison between the two pipelines is beyond the
scope of this contribution.

##  Appendix B Fitting Procedure and Model Comparison

We sampled the posterior distributions of the model parameters and estimated
the Bayesian evidence of each model using dynesty. dynesty uses Dynamic Nested
Sampling to explore the posterior parameter distributions, identifying
contours of constant likelihood by sampling from nested shells of the
posterior distributions with monotonically increasing likelihood. Along the
way, Dynamic Nested Sampling estimates the Bayesian evidence by numerically
integrating the posterior distribution. Regions of very high likelihood may
correspond to a very narrow region of parameter space and so contribute little
to the Bayesian evidence, while regions of lower likelihood that encompass a
large portion of the prior parameter space can dominate the Bayesian evidence.
Model comparisons based on the Bayesian evidence use these volumes to penalize
additional parameters, which is the main difference from model comparison
tests based on maximum likelihood ratios or varieties of Bayesian information
criteria. Besides estimating the Bayesian evidence, Dynamic Nested Sampling
carefully explores the parameter space defined by the prior parameter
distributions, identifying the global maximum of the likelihood function and
any important modes of the posterior distributions. Figure 16 shows the
posterior parameter distributions for each SN.

We used uniform priors for the model parameters except for the normalization
$C$ and the companion separation $a$. For $C$, we used a uniform prior in
$\log C$ because this is a scaling parameter, while for $a$ our
logarithmically spaced grid corresponds to a uniform prior on $\log a$. Table
6 gives the ranges of these prior parameter distributions. We used a Gaussian
likelihood function for the Dynamic Nested Sampling. We fit the light curves
at the original cadence (either 30 minutes or 10 minutes), and we fit from the
start of the TESS light curve up to $t_{\rm peak}+0.5$ days, where $t_{\rm
peak}$ is given in Table 1 (see §2.1).

For our model comparison tests, we define the Bayes factor $K$ as the ratio of
the Bayesian evidence $Z$ for the model with companion signatures to that of
the model with no companion signatures

$\displaystyle
K=\frac{Z_{1}}{Z_{2}}=\frac{\int\mathcal{L}(\theta_{1})\pi(\theta_{1})\,d\theta_{1}}{\int\mathcal{L}(\theta_{2})\pi(\theta_{2})\,d\theta_{2}}$
(B1)

where $\mathcal{L}$ is the likelihood, $\pi$ is the prior distribution,
$\theta_{1}$ is the vector of model parameters with a companion signature and
$\theta_{2}$ is the vector of model parameters without a companion signature.
The $\pi(\theta)$ are normalized probability distributions, so large prior
volumes tend to decrease the product of $\mathcal{L}(\theta)\pi(\theta)$. This
definition of the Bayes factor $K$ therefore penalizes models with larger
prior volumes, due to either a large number of parameters or broad priors.

We also compared the Bayesian Information Criteria (BIC) of the two models

$\displaystyle{\rm BIC}=k\ln N-\ln\mathcal{L}$ (B2)

where $k$ is the number of parameters, $N$ is the number of data points in the
fit, and $\mathcal{L}$ is the likelihood. The BIC explicitly penalizes models
with additional parameters, which may be an advantage over the Bayes factor if
the change in prior volume introduced by extra parameters is relatively small.
If the penalty for additional parameters is relatively small, then modest
improvements in the likelihood will appear significant, which might be the
case for companion interaction models with small amplitudes that cannot, by
definition, substantially change the fit. The BIC test is therefore a useful
check on how strongly the data prefer a companion interaction model,
especially for very low amplitude signals.

Figure 16: Example of the posterior parameter distributions for SN2021zny. The
vertical lines in the 1D histograms mark the medians and 95% credible regions
of the distributions. There are correlations between the time of first light
$t_{0}$, power law index $\beta_{1}$, and normalization C, which we discuss in
§4. The complete figure set is available in the online journal article. Table
6: Ranges of Parameter Priors.

Parameter | Symbol | Range
---|---|---
Time of first light | $t_{0}$ | Time range of first sector
Normalization at 1 day | $C$ | 0.008 – 1.0
Early-time rising index | $\beta_{1}$ | 0 – 4.0
Late-time curving index | $\beta_{2}$ |  $-$0.1 – 0
Residual baseline flux | $f_{0}$ |  $-$0.2 – 0.2
Companion Separation | $a$ | (0.02 – 4)$\times 10^{13}$ cm
Calibration offset | $c$ |  $-$1.0 – 1.0

Note. — Uniform priors were assumed for all prior distributions except for the
normalization $C$ and companion separation $a$. The normalization prior was
uniform in $\log C$, and restricted at the low end to capture our highest
dynamic range light curves (just over 5 magnitudes). Companion separations
were drawn from a grid of 20 models evenly spaced in the logarithm of the
separation, which corresponds to a uniform prior on $\log a$. Fluxes are in
units relative to peak.

Figure 17: Analysis of residual systematic errors after fitting a curved power
law model. As an example, the left panel shows the root-mean-square (RMS)
scatter of the residuals on 30 or 10 minute time scales and on 8 hour time
scales. For Gaussian noise, the ratio of the RMS scatter on 30 or 10 minute
time scales and 8 hour time scales should be $\sqrt{16}$ or $\sqrt{48}$,
respectively. These ratios are shown with the solid lines. The middle panel
shows the RMS scatter scaled to the observed 30 or 10 minutes scatter for
supernova light curve residuals after binning to 2, 4, 8, 16, 24, 32, 64 and
128 hours (the solid lines connect points for individual supernovae—only 50
random supernovae are shown for clarity). The thick line shows the expected
trend for Gaussian scaling. We calculate the ratio of the Gaussian expectation
to the observed RMS scatter at each time scale, and take the maximum across
timescales for an individual supernova as a metric for the quality of the
light curve. The right panel shows the distributions of the scaled RMS scatter
at each timescale (the distributions do not show how individual supernova
light curve residuals vary across time scales). The tails of the distribution
below the expectation for Gaussian noise are due to sampling error, as there
are less than 20, 10, and 5 points after binning to 32, 64, and 128 hours.

##  Appendix C Subsamples

There are four subsamples of TESS SNe light curves. The first subsample
consists of cases where TESS did not observe the peak flux, and so we cannot
estimate the value of $t_{\rm rise}$. The second subsample consists of cases
where fits for the time of first light $t_{0}$ place it in data gaps,
introducing uncertainty into the early time light curve shapes. We refer to
this subset as the ”No First Light” subsample. The last two subsets are the
”High Quality” subsample and the ”High Dynamic Range” subsample, which we
discuss in detail here. SNe from each subsamples are marked in Tables 1, 3,
and 4.

###  C.1 Residual Noise Properties and High Quality Subsample

We inspected the residuals of each SN fit to investigate the quality of the
fits. We found that the residuals are often correlated in time, typically on
time scales of 8 hours or shorter. Correlated residuals suggest the presence
of residual systematic errors in some of our light curves. The correlated
noise is not stationary in time and appears at a variety of amplitudes and on
different time scales—the shapes and amplitudes depend primarily on the
variable scattered light signals from the Earth and Moon that are specific to
each TESS observing sector.

Correlated noise can introduce ambiguity into the shape of the early time
light curves derived from our fits. To quantify the impact of correlated noise
on our results, we calculated the RMS scatter of the residuals for the
original cadence at 30 minutes or 10 minutes and after binning to 2, 4, 8, 16,
32, 64, and 128 hours (we include 24 hours because we are specifically worried
about scattered light signals from the Earth). In the limit of random Gaussian
noise, the RMS scatter of the residuals should decrease by a factor of
$\sqrt{N}$, where $N$ is the number of FFIs taken within a given time
interval. If correlated noise is present, the RMS scatter of the residuals
binned to 8 hours will decrease more slowly than for the Gaussian limit,
indicating the presence of residual systematic errors.

As an example, the left panel of Figure 17 shows the 8 hour residual RMS
scatter as a function of the original 30 or 10 minute residual RMS scatter,
with the theoretical ratios for Gaussian noise are shown with the solid lines.
The RMS scatter spans a wide range of values, but a subset of SN cluster near
the theoretical Gaussian limits. The middle panel shows a generalization of
this investigation to multiple timescales, by scaling the observed RMS scatter
at a given timescale to that observed at 30 or 10 minutes. Averaging over
longer and longer timescales reduces the random component of the noise, until
systematic errors start to limit the observed scatter. The right panel shows
the distributions of the scaled RMS scatter, to give an sense of the
population as a whole relative to the Gaussian limit. Note that on timescales
of 32 hours (1.3 days), there are less than 20 points in the light curves and
the estimate of the RMS scatter becomes noisy due to sampling error. Sampling
error likely explains why the RMS scatter of some light curves increase on
longer timescales, or decreases to be well below the Gaussian limit.

We define a ”noise metric” for each light curve as follows: First, we
calculate the RMS scatter of the light curve residuals at each timescale, and
then divide the observed RMS scatter by the RMS scatter at the native 30 or 10
minute samples. This ratio RMSt/RMS${}_{\rm native}={\rm rms}_{t}$ gives the
rate at which random noise is averaging out of the light curves on longer and
longer timescales. We compare this observed scatter rmst,observed to the
Gaussian expectation rms${}_{t,{\rm Gauss}}=N^{-1/2}$, where $N$ is the number
of FFIs in a given time bin. We then divide the Gaussian scaled scatter
rmst,Gauss by the observed scaled scatter rmst,observed, and the noise metric
is the minimum across timescales min(rms${}_{t,{\rm Gauss}}/$rmst,observed) =
rms${}_{\rm Gauss}/$rmsobserved. The metric rms${}_{\rm Gauss}/$rmsobserved
captures the largest departure of the SN light curve from Gaussian noise, and
should be sensitive to systematic errors appearing on different timescales.
This metric also has an intuitive scaling from 0 to 1, where values near zero
indicate very little improvement from binning (systematic errors dominate over
random noise), while 1 indicates perfect Gaussian noise scaling (random noise
only).

We then define a ”High Quality” subsample as the SNe with noise metrics in the
top quartile. This threshold is at rms${}_{\rm Gauss}/$rms${}_{\rm
observed}\geq 0.49$, i.e., within a factor of about 2 of the Gaussian
expectation. There are 77 SNe in this subsample, which are the least affected
by correlated noise. The ”High Quality” SN sample is marked by a flag in Table
1 and Table 4, and rms${}_{\rm Gauss}/$rmsobserved for each light curve is
given in Table 1. We give more details and show the distributions of the noise
properties in Appendix C.1.

The correlated noise in the rest of the supernova sample is caused by residual
systematic errors from complicated backgrounds that were not removed by the
$\sigma$-clipping or corrected by the background model procedure, or by blends
with background stars for which we could not isolate the variable star signal.
However, the SN signal is clearly present in these light curves and so some
information about the early rise of these SNe is still available. We show
results based on both the full sample of SN light curves and results from the
”High Quality” sample alone. The results based on the full sample are
consistent with results from the ”High Quality” sample.

Figure 18: Correlations of power law index $\beta_{1}$ and rise time $t_{\rm
rise}$ with peak magnitude $T_{\rm peak}$, dynamic range $\Delta T$, and
redshift. We only show the 74 SNe in the ”High Dynamic Range” sample, and we
only show values of $t_{\rm rise}$ for the 46 SNe that TESS observed the peak
(see §2.1 and Appendix C). The color bar gives the noise amplitude relative to
peak, showing that light curves with large noise amplitudes tend to have lower
values of $\beta_{1}$ and $t_{\rm rise}$. This correlation is a measurement
bias found by Miller et al. (2020b), which we discuss in Appendix C.2.  Figure
19: Simulations used to quantify the observational bias discussed in Appendix
C.2. The left panels show simulated light curves with different levels of
noise. The input model is shown in the top panel, and has a time of first
light $t_{0}=0.0$, power law index $\beta_{1}=2.0$, power law index
$\beta_{2}=-0.015$, and rise time $t_{\rm rise}=17.25$ days. The light curve
is sampled at 30 minute cadence and scaled so that the peak flux is unity.
Different levels of noise are added in the lower panels, logarithmically
spaced between 1% and 100% of the peak flux. The maximum likelihood models
from dynesty are shown with red lines, and the recovered value of $t_{0}$ is
shown with the vertical dashed red lines. The right panel shows the recovered
values of power law index $\beta_{1}$ as a function of the recovered time of
first light $t_{0}$, with the true values of the input model shown by dashed
black lines. The color coding gives the logarithm of the noise amplitudes from
the left panel. There is a bias in the recovered parameters for light curves
with the noise amplitude $\gtrsim$ 10% of peak.

###  C.2 Observational Biases and High Dynamic Range Subsample

Miller et al. (2020b) found an observational bias such that the rising power
law index and rise time are correlated with redshift. This bias is easy to
understand as a result of signal-to-noise ratio: the lower the signal-to-noise
ratio, the later the SN will be detected during its initial rise. A later
detection results in a later value of $t_{0}$ and a bias in $t_{\rm rise}$ to
smaller values. Furthermore, $t_{0}$ is correlated with the fitted power law
index $\beta_{1}$, and so a later value of $t_{0}$ biases fits for $\beta_{1}$
to smaller values.

Figure 18 shows the same biases in power law index $\beta_{1}$ and rise time
$t_{\rm rise}$ for our fits to the TESS SN light curves. Brighter SNe at peak
tend to have higher values of $\beta_{1}$ and smaller values of $t_{\rm
rise}$. Brighter SNe also tend to have larger values of $\Delta T$ and smaller
redshifts, so $\beta_{1}$ is correlated with these observables as well. We
also checked for relationships between $\beta_{2}$ and the observed properties
(peak magnitude $T_{\rm peak}$, dynamic range $\Delta T_{\rm peak}$, and
redshift), but did not find any significant correlations.

The color bar in Figure 18 shows the 30 minute RMS scatter (calculated from
the first 2 days of each light curve) in units relative to peak flux, which
quantifies the signal-to-noise ratio of the light curve. This noise amplitude
relative to peak is independent of the SN limiting magnitude $T_{\rm lim}$,
peak magnitude $T_{\rm peak}$, and redshift, but is closely related to the
dynamic range $\Delta T$. SN with large noise amplitudes relative to peak have
smaller power law index fits in each panel of Figure 18.

Figure 19 quantifies the biases in the time of first light $t_{0}$ and power
law index $\beta_{1}$ by showing simulated light curves with different levels
of noise relative to peak and the results of fits to these simulations. The
input model is a curved power law, with $t_{0}=0$, $\beta_{1}=2.0$, and
$\beta_{2}=-0.015$. The resulting rise time for this model is 17.25 days. The
light curve is sampled at 30 minute cadence and renormalized so that the peak
flux equals unity. We then add Gaussian noise of different amplitudes relative
to peak, logarithmically spaced between 1% and 100%, as indicated in the left
hand panels of Figure 19. Finally, we run dynesty on the simulated light
curves and report the median values of the posterior distributions for $t_{0}$
and $\beta_{1}$. The right hand panel shows the recovered value of $\beta_{1}$
as a function of the recovered value of $t_{0}$, where the input model had
$\beta_{1}=2.0$ and $t_{0}=0$. Sources with noise amplitudes $\gtrsim$ 10% of
peak have inferred values of $t_{0}$ and $\beta_{1}$ significantly biased from
the true value.

We therefore restrict our sample to SNe with noise amplitudes $\leq$ 10% of
peak flux on 30 minute time scales, which we refer to as the ”High Dynamic
Range” subsample. If TESS did not observe the peak of the light curve, we
estimate the relative noise amplitude by assuming an absolute magnitude peak
of $T_{\rm peak}=-19.5$, calculating the apparent magnitude based on the
luminosity distance, and re-normalizing the observed noise floor to the new
peak flux. In total, 74 SNe have a noise floor $<$ 10% of peak, 56 of which
have observations at the time of first light, 46 of which have observations of
the peak (and so valid estimates of $t_{\rm rise}$), and 10 of which are in
the ”High Quality” sample (§C.1). These SNe are flagged in Table 4.

The noise amplitude relative to peak is inversely related to the dynamic range
$\Delta T$, because $\Delta T$ gives the ratio of the peak flux to the
detection limit and the detection limit is based on the observed noise in the
early light curve. The 30 minute RMS scatter relative to peak is roughly
related to our definition of $\Delta T$ by ${\rm RMS}_{\rm
30min}=10^{-0.4\Delta T}\sqrt{16}/3$, where the factor of $\sqrt{16}$ converts
from an 8 hour time scale to 30 minutes and the factor of 1/3 converts from a
3$\sigma$ limit to a 1$\sigma$ characteristic amplitude. For the requirement
of 10% noise relative to peak, unbiased SN parameters can be obtained from
TESS light curves with $\Delta T>2.8$ mag.

##  Appendix D Candidates

In this section, we show the light curves discussed in §4.2. This includes the
light curves that strongly prefer Kasen (2010) models but are false positives
due to red noise and/or data gaps (SN2018fpm, SN2020ftl, and SN2022exc, Figure
20), the light curves within a factor of 3 of Gaussian statistics that show a
slight preference for adding a Kasen (2010) model in addition to a curved
power law model (SN2020abqu, SN2021ahmz, and SN2022ajw, Figure 21), the light
curves approaching Gaussian statistics that disfavor Kasen (2010) models
(SN2020tld and SN2022eyw, Figure 22), and the light curve that disfavors the
Kasen (2010) models but is affected by correlated red noise (SN2021abko,
Figure 23).

---
Figure 20: SN light curves with very large Bayes factors or BIC values that
strongly prefer companion interactions, but are false positives due to red
noise and/or data gaps. The panels are formatted and marked in the same way as
Figure 3.
---
Figure 21: SN light curves approaching Gaussian statistics that prefer
companion signatures in addition to a curved power law model. Note that the
evidence for the companion interaction vanishes when using the BIC for all
three SN. For SN2022ajw, the Bayes factor is just below our fiducial
threshold. The panels are formatted and marked in the same way as Figure 3.
---
Figure 22: SN light curves approaching Gaussian statistics that disfavor
companion signatures. The panels are formatted and marked in the same way as
Figure 3. SN2022eyw has excess noise from scattered light before the time of
first light, but the early rise of the SN itself is reliable.
---
Figure 23: Light curve for SN2021abko that disfavor companion signatures but
is affected by residual systematic errors. The panels are formatted and marked
in the same way as Figure 3.