# Detecting Anomalous LAN Activities under Differential Privacy∗††thanks: ∗The
definitive Version of Record was published in Security and Communication
Networks, vol. 2022, Apr. 2022. https://doi.org/10.1155/2022/1403200

Norrathep Rattanavipanon  College of Computing, Prince of Songkla University,
Phuket, 83120, Thailand
{norrathep.r<EMAIL_ADDRESS>Donlapark Ponnoprat  Data Science
Research Center, Department of Statistics, Faculty of Science,
Chiang Mai University, Chiang Mai, 50200, Thailand
<EMAIL_ADDRESS>Hideya Ochiai  Graduate School of Information Science
and Technology, The University of Tokyo, Tokyo, 113-8656, Japan
<EMAIL_ADDRESS>Kuljaree Tantayakul  College of Computing,
Prince of Songkla University, Phuket, 83120, Thailand
{norrathep.r<EMAIL_ADDRESS>
Touchai Angchuan  Faculty of Engineering, Prince of Songkla University,
Songkhla, 90110, Thailand
{touch<EMAIL_ADDRESS>Sinchai Kamolphiwong  Faculty of Engineering,
Prince of Songkla University, Songkhla, 90110, Thailand
{touch<EMAIL_ADDRESS>
###### Abstract

Anomaly detection has emerged as a popular technique for detecting malicious
activities in local area networks (LANs). Various aspects of LAN anomaly
detection have been widely studied. Nonetheless, the privacy concern about
individual users or their relationship in LAN has not been thoroughly explored
in the prior work. In some realistic cases, the anomaly detection analysis
needs to be carried out by an external party, located outside the LAN. Thus,
it is important for the LAN admin to release LAN data to this party in a
private way in order to protect privacy of LAN users; at the same time, the
released data must also preserve the utility of being able to detect
anomalies. This paper investigates the possibility of privately releasing ARP
data that can later be used to identify anomalies in LAN. We present four
approaches, namely naïve, histogram-based, naïve-$\delta$ and histogram-
based-$\delta$, and show that they satisfy different levels of differential
privacy – a rigorous and provable notion for quantifying privacy loss in a
system. Our real-world experimental results confirm practical feasibility of
our approaches. With a proper privacy budget, all of our approaches preserve
more than 75% utility of detecting anomalies in the released data.

##  I Introduction

Security of local area networks (LANs) has been getting more attention in the
last few decades. Traditional LAN defense mechanisms based on a firewall are
no longer effective in preventing malware infection since malware can simply
circumvent the firewall or infect the network through other means [1, 2]. A
prominent example is the recent emergence of ransomware that can infect LAN
devices via phishing attacks; these attacks remain effective even if the LAN’s
firewall is active and configured correctly [3, 4]. In addition, with the rise
of the Internet-of-things (IoT), the so-called “smart” devices have become
widely popular and, at the same time, are also extremely vulnerable to malware
attacks [5]. These devices may be infected from the outside world and
introduce malware to the LAN.

To overcome this challenge, several anomaly detection techniques have been
proposed to detect malicious activities in LAN. Among those, techniques based
on the Address Resolution Protocol (ARP) are shown to be promising in
detecting anomalous activities in LAN without requiring a change to existing
devices [6, 7], making it suitable to the current IoT networks.

Despite this success, there still remains a severe privacy concern to LAN
users, which has not been thoroughly explored in the previous work. Often
times, the anomaly detection must be performed by an entity outside LAN [8, 9,
10] or third-party software [11, 12]. Thus, it is equally important to ensure
privacy of the data exposed to this external and potentially malicious entity.
For instance, a LAN admin in an enterprise may choose to outsource an anomaly
detection analysis to an external widely-popular service, e.g., Microsoft’s
Anomaly Detector [11], or the admin simply wants to release some features of
network data for transparency or academic purposes. In either case, it would
require the LAN admin to output network data (which is an input to the anomaly
detection algorithm) to an untrusted party. Doing so may lead to having such
party learn privacy-sensitive information about the LAN users. For example, it
may directly disclose personally identifiable information (PII), e.g., IP/MAC
addresses, which can be used to uncover the identity of LAN users. It may also
cause an indirect information leakage by revealing information about access
patterns (e.g., the time of the day that a specific user is online) or
relationship between users [13].

While it is possible to simply erase all users’ sensitive information from the
output data, this kind of technique does not provide strong and provable
privacy guarantees. A motivated adversary may still be able to deanonymize
users through other means, e.g., performing a side-channel analysis [14] or
correlating the remaining network traces with the physical world data [15].
Therefore, there is a need for a technique with _rigorous_ privacy guarantees,
while preserving the utility of detecting anomalies in the LAN environment.

Contributions: To this end, the goal of this paper is to investigate the
possibility of privately publishing ARP data that can later be used to
identify anomalies in LAN. Our work presents the following contributions:

  * •

Privacy Notions for ARP Publication. We identify four concrete privacy notions
in the context of ARP-data publication. Each notion is defined over a
different type of information that needs to be privacy-protected as well as
the probability that this protection holds. Specifically, they are derived
from the widely-known _differential privacy_ [16] notion, which allows us to
mathematically prove whether a specific algorithm adheres to any of these
notions. We argue that this is a necessary and essential step towards
designing, implementing and deploying any privacy-preserving approach into the
real world. Without it, it is doubtful whether any meaningful guarantee can be
obtained from our approaches.

  * •

Releasing ARP for Anomaly Detection with Various Degrees of Privacy. We
present four approaches capable of privately releasing ARP data that still
preserves the utility of detecting LAN anomalies. Our approach provides a wide
range of privacy-preserving degrees, making them suitable to different
scenarios:

    * –

The first approach requires small additive perturbations to the input ARP data
in exchange for privacy protection of user relationship.

    * –

The second approach perturbs the input data by a relatively higher amount but
it can attain a stronger privacy protection guarantee for each individual LAN
device/user.

    * –

The third and fourth are variants of the first two approaches that require
even smaller data perturbations; however, they sacrifice some small
probability that the privacy guarantee will not hold, making them an
appropriate option for scenarios where data utility needs to be maximized.

  * •

Practicality via Real-world Deployment. We demonstrate practicality of our
approaches by implementing and deploying them as part of a large-scale real-
world project, called ASEAN-Wide Cyber-Security Research Testbed Project
111https://www.nict.go.jp/en/asean_ivo/ASEAN_IVO_2020_Project03.html. Overall,
the aim of this project is three-fold: (1) to capture network data from
multiple LANs across the ASEAN region, (2) to determine malware behaviors
based on the captured data and (3) to make the captured data sharable in the
public domain. Our work fits perfectly in this project as it fulfills the
third goal by providing a privacy-preserving mechanism for releasing captured
ARP data.

  * •

Evaluation on Real-world Dataset. We evaluate our approaches on a real-world
ARP dataset captured from 3 LANs over 30 weeks. The experimental result shows
feasibility of our approaches as they introduce only low error values ($<10$
in the root-mean-square error) to the original data. In addition, we assess
utility of the released data by testing it on the existing LAN anomaly
detector [6]. The result is promising as our approaches can achieve $75\%$
anomaly detection rate.

Organization: The rest of the paper is organized as follows: Section II
overviews existing work related to LAN anomaly detection and differential
privacy. The background in Address Resolution Protocol and differential
privacy are discussed in Section III. Section IV describes the system and
adversarial models targeted in this work. Section V presents privacy notions
in the context of releasing ARP data. Section VI and Section VII present four
approaches and prove that they satisfy privacy notions defined in the previous
section. Experiments are carried out and reported in Section VIII. Several
issues are discussed in Section IX. Finally, the paper concludes in Section X.

##  II Related Work

Differential privacy in anomaly detection. To the best of our knowledge, there
has been no prior work that proposes a release mechanism for ARP data with
differential privacy guarantees while retaining the utility of anomaly
detection in the LAN setting. The closest related work can be found in [17],
where the authors employ PINQ differential privacy framework [18] to detect
network-wide traffic anomalies. The main difference between our work and the
work in [17] lies in the type and magnitude of the released data as well as
the privacy guarantee. The work in [17] aims to privately release _link-level
traffic volumes of ISP_ whose overall value tends to be much larger than noise
introduced by any differentially-private release mechanism. On the other hand,
our work operates on more restricted input (ARP-degree) which generally
contains a much smaller value, making it more noise-sensitive than ISP’s
traffic volume. Reducing this sensitivity poses a main challenge addressed in
this work. Further, the work in [17] provides _no_ privacy protection
guarantee for individual network users. Achieving this guarantee is non-
trivial, as discussed in Section VI-B.

Besides the work in [17], several existing work focuses on providing anomaly
detection with differential privacy guarantees in non-networked settings,
e.g., web browsing [19], social network [20], health care [21], or syndrome
surveillance [22]. Due to the difference in the target setting, the
aforementioned techniques are not directly applicable to our work.

LAN anomaly detection. There are a number of existing research that aims to
detect anomalies in LAN _without_ providing privacy protection. Zhang et al.
[23] present an approach based on honeypot to detect malicious LAN activities.
Yeo et al. [24] propose a framework to monitor a network traffic and detect
anomalies in the Wireless LAN (WLAN) environment via the IEEE 802.11 MAC
protocol. Nonetheless, this approach is specific to wireless LAN and thus
cannot be directly applied to the wired LAN setting. Our approaches are based
on ARP requests, making them suitable for both wired and wireless LAN
environments.

Several prior work focuses on detecting LAN anomalies based on ARP-related
data. Whyte et al. [25] propose an anomaly detection approach that
distinguishes anomalous activities through statistical analyses of ARP
traffic. Yasami et al. [7] propose to model normal ARP traffic behaviors using
Hidden Markov Model. Farahmand et al. [26] detect LAN anomalies based on four
features: traffic rate, burstiness, dark space and sequential scan. Matsufuji
et al. [6] present an anomaly detection algorithm based on the degree of
destination of ARP requests.

##  III Background

###  III-A Address Resolution Protocol (ARP)

In a nutshell, ARP is a request-response protocol that provides a mapping
between dynamic IP addresses and permanent link-layer addresses (also known as
MAC addresses), allowing one computer to discover a MAC address of another
from its IP address. This protocol is essential in a LAN environment since it
enables communication between any two computers within the same sub-network as
follows:

In LAN, when one computer needs to connect with another, it uses ARP to
broadcast a request asking for the MAC address associated with the IP address
of the destination computer. Therefore, an ARP request contains the
requester’s IP and MAC addresses as well as the destination’s IP address. Upon
receiving the ARP request, every computer checks whether the received IP
address matches with one of its network interfaces. If it does, it unicasts an
ARP response back to the requester along with its IP and MAC addresses. At the
end of this process, the requester successfully retrieves the destination’s
MAC address and can use this information to construct Ethernet frames for
transmitting subsequent data to the target computer.

Similar to other network protocols, ARP involves using sensitive data that has
previously been shown to be directly (e.g., IP address) or indirectly (e.g.,
traffic volume [15]) linkable to the identity of network users. Hence, this
privacy concern must be taken into account when designing an approach for
releasing ARP data.

###  III-B Differential Privacy (DP)

Consider a setting in which there are $n$ users who send individual data to a
trusted curator. The curator then applies an algorithm $\mathcal{M}$ and
outputs these results to an untrusted party. In a strong notion of privacy,
the data of an individual must be kept private from strong adversaries – even
ones who get a hand on the data of the other users.

The _differential privacy_ (DP) is a viewpoint of this notion given in a
seminal paper by Dwork, McSherry, Nissim, and Smith [16]. First, we say that
two databases $X$ and $X^{\prime}$ are _neighboring_ if they differ by exactly
one database entry. The differential privacy is then satisfied if changing $X$
to $X^{\prime}$ does not change the probability of observing an output of
$\mathcal{M}$ by very much. With differential privacy, presence of a single
entry will not affect the published output by much. Therefore, outputs from a
differentially-private algorithm cannot be used to infer about any single
entry from the input dataset.

######  Definition 1 (Differential Privacy).

An algorithm $\mathcal{M}:\mathcal{X}\to\mathcal{Y}$ satisfies
$(\varepsilon,\delta)$-_differential privacy_ ($(\varepsilon,\delta)$-DP) if,
for every pair of neighboring datasets $X$ and $X^{\prime}$ and every subset
$S\in\mathcal{Y}$,

$\mathbb{P}\left(\mathcal{M}(X)\in S\right)\leq
e^{\varepsilon}\mathbb{P}\left(\mathcal{M}(X^{\prime})\in S\right)+\delta,$

where $\varepsilon$ is referred as a privacy budget. We will refer to
$(\varepsilon,0)$-DP as $\varepsilon$-DP. Intuitively, smaller values of
$\varepsilon$ and $\delta$ lead to a stronger privacy guarantee. Conversely,
higher values of $\varepsilon$ and $\delta$ imply a weaker guarantee with
possibly better utility/accuracy of the released data.

A related notion of differential privacy is the concentrated differential
privacy, which aims to control the moments of the _privacy loss variable_ :
$f(Y)=\mathbb{P}(\mathcal{M}(X)=Y)/\mathbb{P}(\mathcal{M}(X^{\prime})=Y)$,
where $Y$ is distributed as $\mathcal{M}(X)$.

######  Definition 2 (Rényi Divergence).

Let $P$ and $P^{\prime}$ be probability densities. The Rényi divergence of
order $\lambda\in(1,\infty)$ between $P$ and $P^{\prime}$ is defined as:

$\displaystyle\operatorname{D}_{\lambda}(P\|P^{\prime})$
$\displaystyle=\frac{1}{\lambda-1}\log\int
P(y)^{\lambda}P^{\prime}(y)^{1-\lambda}\ dy$
$\displaystyle=\frac{1}{\lambda-1}\log\mathbb{E}_{y\sim
P}\left[\frac{P(y)^{\lambda-1}}{P^{\prime}(y)^{\lambda-1}}\right].$

######  Definition 3 (Concentrated Differential Privacy [27]).

An algorithm $\mathcal{M}:\mathcal{X}\to\mathcal{Y}$ satisfies $\rho$-_zero-
concentrated differential privacy_ ($\rho$-zCDP) if, for every pair of
neighboring datasets $X$ and $X^{\prime}$ and every $\lambda\in(1,\infty)$,

$\operatorname{D}_{\lambda}(\mathcal{M}(X)\|\mathcal{M}(X^{\prime}))\leq\lambda\rho.$

One useful property of the differential privacy is that it is preserved under
post-processing.

######  Proposition 1 (Post-processing [28]).

For any $(\varepsilon,\delta)$-DP ($\rho$-zCDP) algorithm
$\mathcal{M}:\mathcal{X}\to\mathcal{Y}$ and arbitrary random function
$f:\mathcal{Y}\to\mathcal{Z}$, the algorithm $f\circ\mathcal{M}$ is also
$(\varepsilon,\delta)$-DP ($\rho$-zCDP).

There may be some certain situations in which we want to apply multiple DP
algorithms, e.g., releasing continual or time-series data. In this case, the
resulting algorithm is also differentially private. However, every new DP
algorithm comes with a cost of privacy loss, as stated in the following
proposition.

######  Proposition 2 (Composition [28]).

For any $(\varepsilon,\delta)$-DP ($\rho$-zCDP) algorithms
$\mathcal{A}_{i}:\mathcal{X}\to\mathcal{Y}_{i}$ for $i\in[k]$, the algorithm
$\mathcal{A}_{[k]}:\mathcal{X}\to\prod_{i=1}^{k}\mathcal{Y}_{k}$ defined by
$\mathcal{A}_{[k]}(X)=(\mathcal{A}_{1}(X),\ldots,\mathcal{A}_{k}(X))$ is
$(k\varepsilon,k\delta)$-DP ($k\rho$-zCDP).

To introduce one of the most ubiquitous $\varepsilon$-DP algorithms, we start
with the $\ell_{1}$-_sensitivity_ of a randomized algorithm
$\mathcal{M}:\mathcal{X}\to\mathbb{R}^{k}$, which is the maximum $\ell_{1}$
change in the output as a result of modifying a single datum. We denote this
sensitivity as $\Delta^{\mathcal{M}}$, and formally define it as:

$\Delta^{\mathcal{M}}=\max_{\text{neighbor
}X,X^{\prime}}\|\mathcal{M}(X)-\mathcal{M}(X^{\prime})\|_{1}.$

######  Theorem 1 (Laplace mechanism [28]).

Let $\mathcal{M}:\mathcal{X}\to\mathbb{R}^{k}$ be an algorithm with
sensitivity $\Delta^{\mathcal{M}}$ and $Y_{i}$ be a noise generated by
sampling from a Laplace distribution at scale
$=\Delta^{\mathcal{M}}/\varepsilon$, i.e.,
$Y_{i}\sim\text{Laplace}(\Delta^{\mathcal{M}}/\varepsilon)$, then the
randomized algorithm $\mathcal{A}$ defined by

$\mathcal{A}(X)=\mathcal{M}(X)+(Y_{1},\ldots,Y_{k})$

is $\varepsilon$-DP.

In addition to the Laplace mechanism, the Gaussian mechanism is also commonly
used to provide $\rho$-zCDP:

######  Theorem 2 (Gaussian mechanism [27]).

Let $\mathcal{M}:\mathcal{X}\to\mathbb{R}^{k}$ be an algorithm with
sensitivity $\Delta^{\mathcal{M}}$ and $Y_{i}$ be a noise generated by
sampling from a Gaussian distribution at scale
$\Delta^{\mathcal{M}}/\sqrt{2\rho}$, i.e., $Y_{i}\sim
N(0,(\Delta^{\mathcal{M}})^{2}/2\rho)$, then the randomized algorithm
$\mathcal{A}$ defined by

$\mathcal{A}(X)=\mathcal{M}(X)+(Y_{1},\ldots,Y_{k})$

is $\rho$-zCDP.

In view of Proposition 2, a composition of $N$ Laplace mechanisms at scale
$N\Delta^{\mathcal{M}}/\varepsilon=O(N)$ is $\varepsilon$-DP, while that of
$N$ Gaussian mechanisms at scale
$\Delta^{\mathcal{M}}\sqrt{N/2\rho}=O(\sqrt{N})$ is $\rho$-zCDP. We see that,
for successive use of a DP mechanism, the Gaussian mechanism gives
comparatively smaller noise than the Laplace mechanism. The following lemma
shows how the two definitions of differential privacy are related.

######  Lemma 1 ([27]).

Any $\rho$-zCDP algorithm is also an $(\varepsilon,\delta)$-DP algorithm for
any given $\delta>0$ and

$\varepsilon=\rho+2\sqrt{\rho\log(1/\delta)}.$ (1)

Conversely, for any given $\varepsilon$ and $\delta>0$, any $\rho$-zCDP
algorithm where

$\rho=\left(\sqrt{\log(1/\delta)+\varepsilon}-\sqrt{\log(1/\delta)}\right)^{2},$
(2)

is also an $(\varepsilon,\delta)$-DP algorithm.

Figure 1: System model considered in this work

##  IV System and Adversarial Models

Figure 1 illustrates the system model considered in this work. We consider a
system in which an entity, called Admin, possesses a LAN consisting of $n$
User-s (i.e., computing devices). In addition, Admin introduces a monitoring
device to this LAN in order to observe ARP requests of all User-s. We denote
$V_{jk}$ to be aggregate ARP requests originated from User $k$, measured and
accumulated at the $j^{th}$ interval. In this work, we assume the time
interval to be in a unit of “a week”, since this time scale allows us to use
data collected from a long period of time without losing too much privacy
budget from the composition (Proposition 2). $V_{j}$ is denoted the result
after appending all ARP requests of all User-s generated in week $j$, i.e.
$V_{j}=\\{V_{j1},V_{j2},...,V_{jn}\\}$.

As shown in Figure 1, our system starts by having the monitoring node
(periodically) send aggregate ARP requests – $V=\\{V_{1},...,V_{t}\\}$ – to
Admin, corresponding to step ❶ in Figure 1. Admin is interested in learning
whether the LAN _as a whole_ has had any anomalous activities for the last $t$
weeks in a private way. Thus, in step ❷, he proceeds to apply a certain
algorithm $Algo$ with the goal of hiding sensitive information from the input
$V$ and then releases the output $D$ to an external entity Analyst in step ❸.
In step ❹, Analyst in turn performs an anomaly detection analysis on $D$ and
returns the result $O$ back to Admin. $O$ contains $O_{i}$ that allows Admin
to identify whether the LAN contains an anomaly at week $i$. We summarize
notation used throughout the paper in Table I

TABLE I: Notation

Differential Privacy (DP) Notation $\varepsilon$ Privacy budget $\delta$
Probability of failing DP guarantees $\Delta^{\mathcal{M}}$ Sensitivity of
algorithm $\mathcal{M}$ $\operatorname{Laplace}(b)$ Laplace distribution with
mean $0$ and scale $b$ $N(\mu,\sigma^{2})$ Normal distribution with mean $\mu$
and standard deviation $\sigma$ System Notation $n$ Number of LAN User-s $t$
Number of data collection intervals $V_{jk}$ User $k$’s ARP requests aggregate
at interval $j$ $V_{j}=\\{V_{j1},...,V_{jn}\\}$ Aggregate ARP requests of all
LAN User-s at interval $j$ $V=\\{V_{1},...,V_{t}\\}$ Aggregate ARP requests of
all LAN User-s from interval $1$ to $t$ $D=\\{D_{1},...,D_{t}\\}$ Output after
applying privacy-preserving algorithm $O=\\{O_{1},...,O_{t}\\}$ Anomaly
detection output

Adversarial Model: Analyst is assumed to be honest-but-curious, i.e, he always
honestly applies an anomaly detection algorithm on any given input data and
returns the correct output to Admin. However, during the process, he may
attempt to learn sensitive information about User-s or their relationship, and
use it for his own benefits.

Goal & Scope: In this work, we focus on addressing privacy concerns in the
aforementioned system, where data from LAN is exposed to an external party.
Hence, we do not consider other LAN settings capable of handling and
processing this data locally, e.g., LANs in a large corporate with its own
internal anomaly detection tool.

The goal of this work is to design approaches that can be appropriately used
as the algorithm $Algo$ in step ❷ of Figure 1. In other words, our approaches
must allow the process of releasing ARP data with some levels of provable
privacy guarantees. Besides privacy, utility of the privatized/released data
for anomaly detection is also important. We must ensure that the privatized
value does not change by a significant amount, compared to the non-privatized
counterpart; otherwise, it will not be useful in detecting anomalies.

##  V DP Notions for ARP-request data

Figure 2: Illustration of a LAN with 3 User-s and 4 ARP requests (represented
by arrows).

In this section, we describe 4 variants of differential privacy notions
related to our system model. The summary of DP notions discussed throughout
this Section is shown in Table II.

TABLE II: Summary of DP notions for ARP-request Data

Notion | Definition # | Protected Info. | Protection Prob.
---|---|---|---
($\varepsilon,\delta$)-edge-DP | 4 | ARP requests | 1-$\delta$
$\varepsilon$-edge-DP | 5 | ARP requests | 1
($\varepsilon,\delta$)-node-DP | 6 |  User-s | 1-$\delta$
$\varepsilon$-node-DP | 7 |  User-s | 1

To understand privacy (i.e., what _concrete_ information needs to be private
and hidden from Analyst) in our target scenario, we first describe the
characteristic of ARP-request data. Figure 2 illustrates an example of a LAN
that consists of 3 User-s producing 4 ARP requests over a specific time
interval. We define the (ARP-request) “degree” of User $k$ as the number of
User-s that receives ARP requests from User $k$. In this example, the degrees
of User $1$, $2$ and $3$ are 2, 2 and 0, respectively.

Using this model, we can view $V_{j}$ – aggregate ARP-request data at week $j$
– as a directed graph, where User can be represented by a node; whereas an
arrow (or a directed edge) from node $s$ to node $r$ indicates ARP request(s)
generated by User $s$ and sent to User $r$ in the same time interval. The
degree of User $k$ is then equivalent to the number of directed edges
originating from User $k$.

As a directed graph, $V_{j}$ can not directly represent a database entry,
required by Definition 1. Thus, the aforementioned notion of differential
privacy does not accurately capture the privacy guarantee in our scenario.
Fortunately, there was prior work focusing on expressing differential privacy
of a graph database. Specifically, the work in [29] presents notions of
differential privacy between graphs by first defining two types of neighboring
graphs: two graphs are _edge-neighboring_ if they differ by a single edge.
Likewise, they are _node-neighboring_ if they differ by a single node.

We now proceed to present two notions of privacy in edge-neighboring graphs:

######  Definition 4 (($\varepsilon,\delta$)-edge-DP).

Let $\mathcal{G}$ be the set of graphs between User-s. An algorithm
$\mathcal{M}:\mathcal{G}\to\mathcal{Y}$ satisfies ($\varepsilon,\delta$)-edge-
differential privacy or ($\varepsilon,\delta$)-edge-DP if, for every pair of
edge-neighboring graphs $G$ and $G^{\prime}$ and every subset
$S\subseteq\mathcal{Y}$,

$\mathbb{P}\left(\mathcal{M}(G)\in S\right)\leq
e^{\varepsilon}\mathbb{P}\left(\mathcal{M}(G^{\prime})\in S\right)+\delta.$

######  Definition 5 ($\varepsilon$-edge-DP).

An algorithm satisfies $\varepsilon$-edge-differential privacy
($\varepsilon$-edge-DP) if and only if it satisfies ($\varepsilon,0$)-edge-DP.

Since an edge in our system refers to ARP requests between a pair of User-s,
Definition 4 and 5 provide privacy protection for these ARP requests. This
means that an algorithm satisfying $\varepsilon$-edge-
DP/($\varepsilon,\delta$)-edge-DP is guaranteed to reveal no information about
all ARP requests exchanged between any pair of User-s, _resulting in hiding
the ARP relationship of all User-s_. This, for example, could hide the source
of infection in LAN as it is common for malware to utilize ARP as the first
step to discover and infect other LAN User-s.

Nonetheless, the guarantee provided by these definitions is not strong enough
to protect privacy of individual User-s. To achieve this stronger guarantee,
we adopt the following notions:

######  Definition 6 (($\varepsilon,\delta$)-node-DP).

Let $\mathcal{G}$ be the set of graphs between User-s. An algorithm
$\mathcal{M}:\mathcal{G}\to\mathcal{Y}$ satisfies ($\varepsilon,\delta$)-node-
differential privacy or ($\varepsilon,\delta$)-node-DP if, for every pair of
node-neighboring graphs $G$ and $G^{\prime}$ and every subset
$S\subseteq\mathcal{Y}$,

$\mathbb{P}\left(\mathcal{M}(G)\in S\right)\leq
e^{\varepsilon}\mathbb{P}\left(\mathcal{M}(G^{\prime})\in S\right)+\delta.$

######  Definition 7 ($\varepsilon$-node-DP).

An algorithm satisfies $\varepsilon$-node-differential privacy
($\varepsilon$-node-DP) if and only if it satisfies ($\varepsilon,0$)-node-DP.

Indeed, by removing a node we also have to remove all of its edges. One then
has that $\varepsilon$-node-DP is stronger than $\varepsilon$-edge-DP. In our
scenario, an algorithm satisfying $\varepsilon$-node-
DP/($\varepsilon,\delta$)-node-DP prevents information leakage about presence
or absence of any individual User.

Remark: recall $\delta$ represents an upper bound of the probability that an
algorithm fails to satisfy the $\varepsilon$-DP notion. As an example, an
algorithm satisfying $(\varepsilon,\delta)$-node-DP has at most $\delta$
probability that will leak some information about an individual node in a
graph. To make $(\varepsilon,\delta)$-edge/node-DP notions meaningful in
practice, one must minimize this failure probability by ensuring that $\delta$
is negligible in terms of number of data points ($\\#p$) considered in the DP
notion [28]. One way to achieve this is to set $\delta$ to:

$\delta=\delta^{\prime}/\\#p$ for some small $\delta^{\prime}$

In $(\varepsilon,\delta)$-node-DP notion, $\\#p$ is the number of nodes;
whereas, in $(\varepsilon,\delta)$-edge-DP, $\\#p$ corresponds to the number
of possible directed edges $\approx(\\#nodes)^{2}$. Thus, it is easy to see
that $\delta$ in $(\varepsilon,\delta)$-edge-DP must be set smaller than that
in $(\varepsilon,\delta)$-node-DP in order to attain the negligible
probability.

##  VI Releasing ARP-request Data with $\varepsilon$-edge/node-DP

In this section, we present two approaches, called _naïve_ and _histogram-
based_ ; the former guarantees $\varepsilon$-edge-DP while the latter is
proven to satisfy the $\varepsilon$-node-DP notion. Later in Section VII, we
describe variants of these approaches that satisfy the more relaxed
$(\varepsilon,\delta)$-edge/node-DP notions.

###  VI-A Naïve Approach

Input: $V=\\{V_{1},V_{2},...,V_{t}\\}$, $t$, $\varepsilon$

Output: $D=\\{D_{1},D_{2},...,D_{t}\\}$

1

2for  _$j=1$ to $t$_ do

3 $D_{j}\leftarrow\textsc{Sum}(\textsc{Degree}(V_{j}))$

4 $D_{j}\leftarrow D_{j}+\text{Laplace}(t/\varepsilon)$

5 if  _$D_{j} >0$_ then $D_{j}\leftarrow\text{int}(D_{j})$

6 else $D_{j}\leftarrow 0$

7

8 end for

Algorithm 1 Naïve Approach

The naïve approach is described in Algorithm 1. In the rest of this section,
we discuss non-trivial details of this approach and show that it indeed
satisfies $\varepsilon$-edge DP.

######  Theorem 3.

The naïve approach as described in Algorithm 1 is $\varepsilon$-edge-DP.

###### Proof.

Let $V_{j}\in\mathcal{G}$ be the directed graph of ARP requests in week $j$.
Let $\mathcal{M}$ be the algorithm that computes the weekly total degrees and
$D_{j}=\mathcal{M}(V_{j})$ (Line 2 of Algorithm 1), which also corresponds to
the total number of edges in $V_{j}$. To preserve $\varepsilon$-edge-DP of
each User’s ARP requests, one can simply use the Laplace mechanism. To do so,
we need to find an upper bound of the sensitivity $\Delta^{\mathcal{M}}$. Let
$V^{\prime}_{j}$ be an edge-neighboring graph of $V_{j}$ in week $j$ and
$D^{\prime}_{j}=\mathcal{M}(V^{\prime}_{j})$ . Then,
$\Delta^{\mathcal{M}}=|D_{j}-D^{\prime}_{j}|\leq 1$ and we have the following
Laplace mechanism $\mathcal{A^{\prime}}$ (Line 2-3) guarantee the
$\varepsilon/t$-node DP:

$\mathcal{A^{\prime}}(V_{j})=\mathcal{M}(V_{j})+Y_{j},$

where $Y_{j}\sim\text{Laplace}(t/\varepsilon)$ (Line 3).

Algorithm 1 can then be represented as:

$\mathcal{A}(V)=\mathcal{P}(\mathcal{A^{\prime}}(V_{1}),\ldots,\mathcal{A^{\prime}}(V_{t}))$

where $\mathcal{P}$ is a post-processing function (Line 4-5) that: (i)
precludes a negative output by thresholding it to 0, and (ii) rounds a non-
negative privatized value into the closest integer in order to prevent the
floating point attack [30].

By Proposition 1 and 2, we can conclude that this algorithm is
$t\varepsilon/t$-edge-DP or $\varepsilon$-edge-DP.

∎

To prevent excessive information loss, one needs the Laplace noise to be
smaller than $D_{j}$, i.e., $t/\varepsilon<\mathbb{E}[D_{j}]$ or
$\varepsilon>t/\mathbb{E}[D_{j}]$. This can be achieved in realistic settings,
e.g., $\varepsilon=2$ in our experiment (Section VIII) where $t=30$ and the
lower quartile of $D_{j}$ is $20$.

On the other hand, a similar analysis for the $\varepsilon$-node-DP results in
much bigger Laplace noises; consider two node-neighboring directed graphs
$V_{j},V^{\prime}_{j}$ of $n$ User-s. The degrees $D_{j},D^{\prime}_{j}$
defined as above satisfy $|D_{j}-D^{\prime}_{j}|\leq n$, which cannot be
improved further. Thus, in order to employ the Laplace mechanism, the noises
have to be sampled from $\text{Laplace}(tn/\varepsilon)$. In contrast to the
edge-DP regime, the scale of the noise comes with a factor of $n$. As a
result, for a large number of User-s, it is no longer feasible to preserve
both privacy and utility at the same time.

###  VI-B Histogram-based Approach

As seen in the previous subsection, the naïve approach can not be used to
satisfy $\varepsilon$-node-DP in practice due to its high sensitivity, leading
to too strong additive noises which in turn significantly lower utility of the
released data. Instead, we propose a second approach utilizing a histogram
that helps reduce the $\varepsilon$-node-DP sensitivity to a reasonable
amount.

Our histogram-based approach is shown in Algorithm 2. The rationale behind
this approach is to transform the degree data in such a way that its
sensitivity is minimized when any User is removed from $V_{j}$. Naturally, a
histogram is a good fit for this approach since it provides a way to partition
data into disjoint groups/bins, where each bin in this case represents a range
of degrees. Thus, this approach first computes the degrees of each User in a
specific week and uses this degree data to construct a histogram, as shown in
Line 2 of Algorithm 2. This histogram data minimizes the $\varepsilon$-node-DP
sensitivity because removing a User from the histogram data affects only one
bin, i.e., the one this User belongs, and it only decreases its bin count by
one; _other histogram bins are unaffected by this change._ We then can apply
the Laplace mechanism on each bin (Line 3), threshold and round the resulting
value to the closest integer (Line 5-6) and finally return this noisy
histogram as an output.

We now formally show that the histogram-based approach satisfies
$\varepsilon$-node-DP.

######  Theorem 4.

The histogram-based approach as described in Algorithm 2 is
$\varepsilon$-node-DP.

###### Proof.

Let $V_{j}$ and $V^{\prime}_{j}$ be node-neighboring directed graph at time
$j$, i.e., $V^{\prime}_{j}$ can be obtained from $V_{j}$ by adding or removing
a single node. Let $\mathcal{M}:\mathcal{G}\to\mathbb{R}^{k}$ be the algorithm
that computes the histogram of the degrees, i.e., the entries of
$\mathcal{M}(V_{j})$ and $\mathcal{M}(V^{\prime}_{j})$ are the count of nodes
by their degrees. Then $\mathcal{M}(V_{j})$ and $\mathcal{M}(V^{\prime}_{j})$
differ by one in the entry corresponding to the degree of User $j$, who only
exists in either $V_{j}$ or $V^{\prime}_{j}$. Therefore,
$\Delta^{\mathcal{M}}=|\mathcal{M}(V)-\mathcal{M}(V^{\prime}_{j})|\leq 1$.

Observe that Line 2-7 of Algorithm 2 can be written as a randomized algorithm
$\mathcal{A^{\prime}}:\mathcal{G}\to\mathbb{R}^{k}$ defined by

$\mathcal{A^{\prime}}(V_{j})=\mathcal{P}(\mathcal{M}(V_{j})+(Y_{1},\dots,Y_{k}))$

where $Y_{i}\sim\text{Laplace}(t/\varepsilon)$ and $\mathcal{P}$ corresponds
to the _threshold-then-round_ function computed on all bin counts (Line 5-6).
It follows from Theorem 1 and Proposition 1 that $\mathcal{A^{\prime}}$ is
$\varepsilon/t$-node-DP.

Then, we can define Algorithm 2 as a randomized algorithm $\mathcal{A}$ as
follows:

$\mathcal{A}(V)=(\mathcal{A^{\prime}}(V_{1}),\ldots,\mathcal{A^{\prime}}(V_{t}))$

By Proposition 2, we have that the histogram-based approach (described in
Algorithm 2) is $t\varepsilon/t$-node-DP or $\varepsilon$-node-DP.

∎

Input: $V=\\{V_{1},V_{2},...,V_{t}\\}$, $t$, $\varepsilon$

Output: $D=\\{D_{1},D_{2},...,D_{t}\\}$

1

2for  _$j=1$ to $t$_ do

3 $D_{j}\leftarrow\textsc{Histogram}(\textsc{Degree}(V_{j}))$

4 foreach  _$bin\in D_{j}$_ do

5 $bin.count\leftarrow bin.count+\text{Laplace}(t/\varepsilon)$

6 if  _$bin.count >0$_ then $bin.count\leftarrow\text{int}(bin.count)$

7 else $bin.count\leftarrow 0$

8

9 end foreach

10

11 end for

Algorithm 2 Histogram-based Approach

##  VII Releasing ARP-request Data with $(\varepsilon,\delta)$-edge/node-DP

The approaches in the previous section require adding a noise proportional to
$t$, which may not scale well in practice when $t$ is large. We explore an
alternative by instead adopting the Gaussian Mechanism in order to reduce
additive noise from $O(t)$ to $O(\sqrt{t})$. We call these variants, _naïve-
$\delta$_ and _histogram-based- $\delta$_, which guarantee
($\varepsilon,\delta$)-edge-DP and ($\varepsilon,\delta$)-node-DP
respectively.

###  VII-A Naïve-$\delta$ Approach

In conjunction with the naïve approach (Algorithm 1) which gives a strong
privacy guarantee by adding considerably large amount of noises, we develop
here another approach that adds less noises, but provides a weaker
$(\varepsilon,\delta)$-edge DP guarantee. The algorithm is described in
Algorithm 3. Similar to Algorithm 1, we round the noisy outputs to the nearest
integers to protect the data from floating point attacks. In the rest of this
section, we discuss non-trivial details of this approach and show that it
indeed satisfies $(\varepsilon,\delta)$-edge DP.

######  Theorem 5.

The naïve-$\delta$ approach as described in Algorithm 3 is
$(\varepsilon,\delta)$-edge-DP.

###### Proof.

Let $V_{j}\in\mathcal{G}$ be the directed graph of ARP requests in week $j$.
Let $\mathcal{M}$ be the algorithm that computes the weekly total degrees and
$D_{j}=\mathcal{M}(V_{j})$ (Line 3 of Algorithm 3). As in the proof of Theorem
3, the edge-sensitivity $\Delta^{\mathcal{M}}$ satisfies
$\Delta^{\mathcal{M}}\leq 1$. Observe that Line 3-6 of Algorithm 3 can be
written as a randomized algorithm
$\mathcal{A}^{\prime}:\mathcal{G}\to\mathbb{R}^{k}$ defined by

$\mathcal{A}^{\prime}(V_{j})=\mathcal{P}(\mathcal{M}(V_{j})+(Y_{1},\dots,Y_{k}))$

where $Y_{i}\sim N(0,t/2\rho)$ and $\mathcal{P}$ corresponds to the
_threshold-then-round_ function computed on all bin counts (Line 5-6). It
follows from Theorem 2 and Proposition 1 that $\mathcal{A}^{\prime}$ is
$\rho/t$-zCDP.

Then, we can define Algorithm 3 as a randomized algorithm $\mathcal{A}$ as
follows:

$\mathcal{A}(V)=(\mathcal{A}^{\prime}(V_{1}),\ldots,\mathcal{A}^{\prime}(V_{t}))$

By Proposition 2, we have that the Algorithm 3 is $t\rho/t$-zCDP or
$\rho$-zCDP. Using Lemma 1 and recalling the definition of $\rho$ in Line 1 of
Algorithm 3, we conclude that this algorithm is also
$(\varepsilon,\delta)$-edge-DP.

∎

Input: $V=\\{V_{1},V_{2},...,V_{t}\\}$, $t$, $\varepsilon$, $\delta$

Output: $D=\\{D_{1},D_{2},...,D_{t}\\}$

1

2$\rho\leftarrow\left(\sqrt{\log{(1/\delta)}+\varepsilon}-\sqrt{\log{(1/\delta)}}\right)^{2}$

3 for  _$j=1$ to $t$_ do

4 $D_{j}\leftarrow\textsc{Sum}(\textsc{Degree}(V_{j}))$

5 $D_{j}\leftarrow D_{j}+N(0,t/2\rho)$

6 if  _$D_{j} >0$_ then $D_{j}\leftarrow\text{int}(D_{j})$

7 else $D_{j}\leftarrow 0$

8

9 end for

Algorithm 3 Naïve-$\delta$ Approach

###  VII-B Histogram-based-$\delta$ Approach

We aim to construct an $(\varepsilon,\delta)$-node-DP with less noises
compared to the $\varepsilon$-node-DP algorithm in Section VI-B. We still rely
on a histogram-based approach as it has small sensitivity upon adding/removing
a node. Our histogram-based-$\delta$ approach is described in Algorithm 4.

######  Theorem 6.

The histogram-based-$\delta$ approach as described in Algorithm 4 is
$(\varepsilon,\delta)$-node-DP.

###### Proof.

Let $V_{j}$ and $V^{\prime}_{j}$ be node-neighboring directed graph at time
$j$, i.e., $V^{\prime}_{j}$ can be obtained from $V_{j}$ by adding or removing
a single node. Let $\mathcal{M}:\mathcal{G}\to\mathbb{R}^{k}$ be the algorithm
that computes the histogram of the degrees, i.e., the entries of
$\mathcal{M}(V_{j})$ and $\mathcal{M}(V^{\prime}_{j})$ are the count of nodes
by their degrees. As in the proof of Theorem 4, the node-sensitivity
$\Delta^{\mathcal{M}}$ satisfies $\Delta^{\mathcal{M}}\leq 1$

Looking at Algorithm 4, we observe that Line 3-7 can be written as a
randomized algorithm $\mathcal{A}^{\prime}:\mathcal{G}\to\mathbb{R}^{k}$
defined by

$\mathcal{A}^{\prime}(V_{j})=\mathcal{P}(\mathcal{M}(V_{j})+(Y_{1},\dots,Y_{k}))$

where $Y_{i}\sim N(0,t/2\rho)$ and $\mathcal{P}$ corresponds to the
_threshold-then-round_ function computed on all bin counts (Line 6-7). It
follows from Theorem 2 and Proposition 1 that $\mathcal{A}^{\prime}$ is
$\rho/t$-node-DP.

Then, we can define Algorithm 4 as a randomized algorithm $\mathcal{A}$ as
follows:

$\mathcal{A}(V)=(\mathcal{A}^{\prime}(V_{1}),\ldots,\mathcal{A}^{\prime}(V_{t}))$

By Proposition 2, we have that the histogram-based approach (described as in
Algorithm 4) is $t\rho/t$-zCDP or $\rho$-zCDP. From the definition of $\rho$
in Line 1 of Algorithm 4), we conclude using Lemma 1 that this algorithm is
also $(\varepsilon,\delta)$-node-DP. ∎

Input: $V=\\{V_{1},V_{2},...,V_{t}\\}$, $t$, $\varepsilon$, $\delta$

Output: $D=\\{D_{1},D_{2},...,D_{t}\\}$

1

2$\rho\leftarrow\left(\sqrt{\log{(1/\delta)}+\varepsilon}-\sqrt{\log{(1/\delta)}}\right)^{2}$

3 for  _$j=1$ to $t$_ do

4 $D_{j}\leftarrow\textsc{Histogram}(\textsc{Degree}(V_{j}))$

5 foreach  _$bin\in D_{j}$_ do

6 $bin.count\leftarrow bin.count+N(0,t/2\rho)$

7 if  _$bin.count >0$_ then $bin.count\leftarrow\text{int}(bin.count)$

8 else $bin.count\leftarrow 0$

9

10 end foreach

11

12 end for

Algorithm 4 Histogram-based-$\delta$ Approach

##  VIII Evaluation

In this section, we evaluate our approaches by deploying them as part of a
large-scale research project and reporting their utility from a real-world
dataset extracted from such project.

###  VIII-A Real-world Deployment

Background. ASEAN-Wide Cyber-Security Research Testbed Project is a large-
scale research project with collaboration between multiple universities
primarily located in Southeast Asia including Prince of Songkla University,
Thailand (PSU), Universitas Brawijaya, Indonesia (UB), University of Computer
Studies Yangon, Myanmar (UCSY), Institute of Technology of Cambodia, Cambodia
(ITC), University of Information Technology, Myanmar (UIT), and The University
of Tokyo, Japan (UT). The ultimate goal of this project is to create a real-
world public testbed of malware behaviors captured in ASEAN countries.

Figure 3: Monitoring device (raspberry-Pi 3B) deployed to a LAN

Independent of our work, the first phase of this project involves capturing,
collecting and analyzing LAN data in Southeast Asian countries. To achieve
this task, a small monitoring device, implemented atop of a raspberry-Pi 3B in
Figure 3, is introduced and placed into several LANs across the ASEAN region.
This monitoring device observes and captures the network traffic flowing
within a LAN and periodically outputs the captured data to our server, in
which such data is analyzed and a model of ASEAN malware is eventually
created.

Deployment. Our work plays an important role in the second phase of this
research project. It allows us to privately share aggregate ARP data collected
from the previous phase with other project members as well as to the public
domain. Our approaches enable a release mechanism of ARP-request data that
still retains the utility of LAN anomaly detection. To assess utility, we
evaluated our approaches on a subset of data captured and extracted from this
research project.

The extracted dataset contains all ARP-request data observed and collected
from 3 real-world LANs over a 30-week period. These LANs are located in: (1)
The University of Tokyo, Japan (thus, its dataset is labeled as JPN), (2)
Prince of Songkla University – Phuket Campus, Thailand (HKT) and (3) Prince of
Songkla University – Hatyai Campus, Thailand (HDY). Details about these
monitored LANs can be found in Table III.

TABLE III: Details of monitored LANs

Label | Location of LAN | Collection Period |  # User-s ($n$)
---|---|---|---
University | City | Country | Start Date | End Date | # Weeks ($t$)
JPN | UT | Tokyo | Japan | Aug 9, 2019 | Mar 6, 2020 | 30 | 95
HKT | PSU | Phuket | Thailand | Nov 6, 2020 | June 4, 2021 | 30 | 63
HDY | PSU | Hat Yai | Thailand | Oct 21, 2020 | May 19, 2021 | 30 | 206

Parameter Selection. As we collected ARP requests over a 30-week period,
$t=30$. The naïve approach involves no other parameters. Meanwhile, the
histogram-based approach consists of an additional set of parameters: the
number of bins and the width of each bin. Intuitively, a larger number of bins
leads to smaller bin counts. In such case, the noise injected by our approach
would become too large, severely decreasing utility of the released data. To
avoid this problem, we select the number of histogram bins to be relatively
small – 3. Specifically, we choose the first two bins to correspond to the
number of User-s whose degrees are 1 and 2, respectively; the third bin
contains the number of User-s with degree $\geq 3$.

Finally, the approaches in Section VII consist of another parameter $\delta$.
Recall from the remark in Section V that $\delta$ must be negligible with
respect to the number of data points ($\\#p$). In other words:

$\delta=\delta^{\prime}/\\#p$ for some small $\delta^{\prime}$

In our target system, $\\#p$ corresponds to $n$ and $n^{2}$ for the node-DP
and edge-DP notions, respectively; See Table III for the number of User-s
($n$) in each monitored LAN. Unless stated otherwise, we use
$\delta^{\prime}=0.01$ for all experiments. Nonetheless, the impact of
different $\delta^{\prime}$ values on the utility is also assessed in the next
subsection.

###  VIII-B Utility Assessment: RMSE

RMSE. In the context of differential privacy, one common utility metric is
defined as an error between the released privatized values $z^{*}$ and the
non-privatized aggregates $z$. We adopt a similar approach and select the
root-mean-square error (RMSE) as our first evaluation metric:

$RMSE=\sqrt{\frac{1}{n}\sum_{i=1}^{n}\left(z^{*}[i]-z[i]\right)^{2}}$

where $z[i]$ and $z^{*}[i]$ represent the $i^{th}$ data point in $z$ and
$z^{*}$, respectively. For the naïve approach and its variant, $z[i]$
corresponds to the sum of all User’s ARP degrees observed in week $i$, while
$z^{*}[i]$ refers to the privatized output on the same ARP data. On the other
hand, $z[i]$ represents a histogram bin in the histogram-based and histogram-
based-$\delta$ approaches.

Impact of $\varepsilon$. Recall that $\varepsilon$ refers to a privacy budget
in the DP notion and a lower value of $\varepsilon$ implies stronger privacy,
while possibly sacrificing utility.

Figure 7 shows the impact of $\varepsilon$ on the utility of the proposed
approaches. Unsurprisingly, we achieve lower errors and thus better utility
from a higher $\varepsilon$. For all 3 monitored LANs, $\varepsilon=5$ seems
to be a pragmatic choice in order to maintain a low error ($<10$) for all
approaches.

Next, we show how much utility can be improved by using the approaches in
Section VII instead of their counterparts in Section VI. The result,
illustrated in Figure 7, suggests that both naïve-$\delta$ and histogram-
based-$\delta$ approaches enjoy higher utility (i.e., a utility gain) when
$\varepsilon\leq 4$. However, as the $\varepsilon$ gets larger, this utility
gain becomes smaller; in fact, the naïve-$\delta$ approach incurs a utility
loss when $\varepsilon\geq 8$ for all monitored LANs. This result suggests
using the approaches in Section VII only when one needs stronger privacy,
i.e., small $\varepsilon$.

Figure 7 also indicates the histogram-based-$\delta$ approach significantly
outperforms the naïve-$\delta$ approach in terms of the utility gain. For
$\varepsilon\leq 4$, the histogram-based-$\delta$ approach provides $\geq
28\%$ utility gain, while a smaller amount of utility gain ($\leq 20\%$) can
be realized in the naïve-$\delta$ approach. This is expected because the
histogram-based-$\delta$ approach introduces a smaller value of $\delta$ (see
the remark in Section V), making the additive noise smaller and thus resulting
in the higher utility gain.

In addition, $n$ also has a direct impact to $\delta$ and hence to the overall
utility. As seen in Figure 7, among all monitored LANs, HDY has the highest
number of User-s and therefore suffers the lowest utility gain.

Impact of $\delta^{\prime}$. We now assess the impact of $\delta^{\prime}$ on
the utility of our approaches. Figure 7 shows RMSE of the naïve-$\delta$ and
histgoram-based-$\delta$ approaches for different values of $\delta^{\prime}$.
As expected, increasing $\delta^{\prime}$ results in a decrease in RMSE and
thus improves the utility of our approaches. This decrease is logarithmic as a
function of $\delta^{\prime}$.

The utility gain of the naïve-$\delta$ and histgoram-based-$\delta$ approaches
with respect to their original counterparts is illustrated in Figure 7. Our
approaches benefit from the higher utility gain when $\delta^{\prime}$ is
larger. For most $\delta^{\prime}$ values, the histogram-based-$\delta$
approach provides a positive utility gain over the histogram-based approach.
Meanwhile, a utility gain can be achieved from the naïve-$\delta$ approach
when $\delta^{\prime}\geq 10^{-3}$.

This experimental result suggests that both naïve-$\delta$ and histogram-
based-$\delta$ approaches still provide a utility advantage over their
original counterparts even for $\delta^{\prime}$ smaller than $10^{-2}$ (up to
$10^{-3}$ for the naïve-$\delta$ approach and $10^{-6}$ for the histogram-
based-$\delta$ approach). In practice, one may choose to opt for smaller
$\delta^{\prime}$ if a stronger privacy guarantee is needed.

(a) JPN

(b) HKT

(c) HDY

Figure 4: RMSE with different $\varepsilon$ values

(d) JPN

(e) HKT

(f) HDY

Figure 5: Utility gain (in $\%$) with respect to their
$\varepsilon$-edge/node-DP counterparts

(a) JPN

(b) HKT

(c) HDY

Figure 6: RMSE with different $\delta^{\prime}$ values where
$\delta=\delta^{\prime}/(\\#p)$ and $\varepsilon$ is fixed to 1

(a) JPN

(b) HKT

(c) HDY

Figure 7: Utility gain (in $\%$) with respect to their
$\varepsilon$-edge/node-DP counterparts

###  VIII-C Utility Assessment: Anomaly Detection Accuracy

Anomaly detection algorithm. In addition to low errors, it is also essential
that outputs produced by our approaches can still be useful in identifying
anomalous activities in LAN. Hence, we further evaluate utility of our
approaches by assessing them via a LAN anomaly detector. In this experiment,
we consider our approaches to preserve the utility of anomaly detection if the
anomaly detector classifies the privatized data the same way as the original
(non-privatized) data.

For the anomaly detector, we choose an approach based on exponentially
weighted moving average and variance [31] proposed by Matsufuji et.al. [6]
since it is tailored specifically for detecting LAN anomalies based on ARP
data, which is also the focus in this work. All parameter values are selected
based on the recommendation from [6].

It is worth noting that the anomaly detector in [6] only supports input of
type univariate time series. However, the histogram-based approach and its
variant produce a multivariate time series output (i.e., a time series of
histograms), and hence cannot be used directly as input to the anomaly
detector. To address this issue, we perform a simple transformation that
converts two consecutive histograms into a single variable using the $L_{1}$
distance function; the result of this transformation is then given as input to
the anomaly detector. More formally, the transformation is defined as:

$z^{*}[i]=\|hist[i]-hist[i+1]\|_{1}\text{ for }i\in\\{1,...,t-1\\}$

(a) JPN

(b) HKT

(c) HDY

Figure 8: $TPR$ result for different $\varepsilon$ in all 3 monitored LANs

(d) JPN

(e) HKT

(f) HDY

Figure 9: $F_{1}$ result for different $\varepsilon$ in all 3 monitored LANs

Metrics. In this experiment, we evaluate utility of our approaches using two
metrics: true positive rate ($TPR$) and $F_{1}$ score. In particular, we
consider $z^{*}[i]$, a noisy data point produced by our approach, to be a true
positive ($TP$) if the anomaly detector classifies both $z^{*}[i]$ and $z[i]$
as an anomaly, where $z[i]$ represents the original non-privatized
counterpart. $z^{*}[i]$ is a false positive ($FP$) if the anomaly detector
finds an anomaly in $z^{*}[i]$ but not in $z[i]$. A true negative ($TN$) and a
false negative ($FN$) are also defined similarly.

Based on these definitions, $TPR$ and $F_{1}$ metrics can be formulated as:

$TPR=\frac{TP}{TP+FN}$ $F_{1}=\frac{TP}{TP+.5(FP+FN)}$

A high value of $TPR$ implies that a high percentage of anomalies detected in
the original data is also captured as an anomaly in the privatized data. On
the other hand, a high value of $F_{1}$ implies relatively small values of
$FP$ and $FN$ compared to $TP$.

Results. Figure 9 and 9 show the utility of our approaches evaluated using
$TPR$ and $F_{1}$ metrics, respectively. First, we can see that $\varepsilon$
does not affect utility of the naïve and naïve-$\delta$ approaches as both
approaches still provide almost perfect utility scores in all monitored LANs.

On the other hand, the histogram-based and histogram-based-$\delta$ approaches
yield low utility for small $\varepsilon$. The utility scores then become
higher as $\varepsilon$ increases. For HKT, both approaches achieve a
reasonable score of $>.75$ with $\varepsilon=5$. Meanwhile, $\varepsilon$ must
be set to $6$ in order to achieve the same utility score in HDY. JPN requires
the highest $\varepsilon$ ($=12$) in order for the histogram-based-$\delta$
approach to perform $75\%~{}TPR$.

Lastly, the results also confirm that the histogram-based-$\delta$ approach
significantly outperforms the naïve-$\delta$ approach in terms of utility.
Thus, we recommend to deploy the histogram-based-$\delta$ approach over the
histogram-based approach when one needs to publish ARP-request data with user
privacy protection (i.e., corresponding to the node-DP notion); whereas, if
edge-DP is sufficient, the naïve approach is a more reasonable choice over the
naïve-$\delta$ approach as the former provides a stronger privacy guarantee
while both approaches achieve the similar utility performance.

Comparison with RMSE. In most cases, the utility results from $TPR$ and
$F_{1}$ metrics are consistent with the previous results measured using RMSE
in Section VIII-B. That is, a higher $\varepsilon$ leads to higher utility
with lower RMSE and higher $TPR$ and $F_{1}$. On the other hand, an extremely
low value of $\varepsilon$ (e.g., $\varepsilon=1$) renders the output data
useless as it can no longer be used to reveal anomalies due to its low
$TPR$/$F_{1}$. There is, however, one exception: the naïve and naïve-$\delta$
approaches surprisingly can still attain high $TPR$ and $F_{1}$ utility
despite low $\varepsilon$. This indicates that such approaches are more robust
to additive noises than other approaches.

##  IX Discussion

ARP Fields. Our approaches take as input ARP-degree data, which in turn makes
use of only 5 fields in ARP packets: SHA, SPA, THA, TPA, and OPER. In this
work, we choose to discard the rest of the ARP fields (i.e., Hardware
Type/Length (HTYPE/HLEN) and Protocol Type/Length (PTYPE/PLEN)) from our
analysis. This is because, in practice, these discarded fields usually have
fixed values that contain neither sensitive information nor anything
meaningful to our approaches. For instance, since ARP is only applicable to
IPv4, the PLEN field is always set to the value of 4 indicating the size of an
IPv4 address; or HTYPE usually contains the value of 1 representing the
ubiquitous Ethernet hardware type. As these fields are generally constant for
all ARP packets, their absence does not affect privacy or utility to our
approaches.

DP Mechanisms. In this work, we focus on releasing ARP-degrees in
differentially private manners. Publishing degrees has sensitivity of $1$
(removing a user’s ARP request alters the total ARP-degrees by $1$), which is
small compared to the number of ARP requests sent by all users. Thus we choose
the noise perturbation methods, namely the Laplace and the Gaussian mechanism,
to privatize the ARP-degrees. Another well-known differential privacy
mechanism is the randomized response, whose standard deviation is
$O\left(\frac{\sqrt{N}}{\varepsilon}\right)$ [32], which is worse than the
standard deviation of the Laplace and Gaussian mechanism, which is
$O\left(\frac{1}{\varepsilon}\right)$. There are also differential privacy
mechanisms based on data synthesis [33]. However, as anomaly detection
algorithms look for “spiking” behaviors at a particular time interval, these
data synthetic approaches, which try to replicate the distribution of the data
as a whole, will not be able to retain the spikes as well as the perturbation
mechanisms.

Time Interval. In our evaluation, we consider the time interval for ARP-data
collection to be in a unit of a week. Albeit a bit long, this design choice is
necessary as it allows us to incorporate all data (which spans for 30 weeks)
into our analysis with higher utility rate and without losing too much privacy
budget.

To illustrate this point, we conduct a new experiment on the JPN network where
we aggregate and process ARP data on a shorter period, i.e., every day instead
of every week. Compared to the original experiment, we have observed a drastic
decrease in the utility rate for all our approaches. As an example, for the
naïve approach with $\varepsilon=4$, the RMSE has increased by a factor of $6$
(from 10 to 60), while the $TPR$ and $F_{1}$ score have reduced substantially
from $1.0$ to $\approx 0.6$.

Utility Metrics. We evaluate our approaches using two utility metrics: RMSE
and Anomaly Detection Accuracy. We select the former because it is one of the
most common metrics for measuring utility from a DP mechanism [34].
Intuitively, it tells us “how far apart the privatized data is from the
original data”. Since an anomalous activity appears as an unusual value in the
data, a privacy-preserving mechanism with small RMSE would not perturb _that
value_ by much, allowing such activity to be detected from the privatized
data. Besides RMSE, there are other similar metrics with the same purpose,
e.g., Mean Absolute Error. Even though we do not include them in this work, we
expect the results from such metrics to be in line with our current results.

Nonetheless, the RMSE does not directly indicate the “true” utility in this
work since our end goal is to detect LAN anomalies, not minimize error rates.
To this end, we choose to include Anomaly Detection Accuracy as our second
metric. This metric realistically gives us an idea of how effective our
approaches are when performing on a real-world LAN anomaly detector [6].

Finally, we do not consider other utility metrics that target different types
of data publication. For example, $L_{p}$-Error [35] and Hausdorff Distance
[36] are geared towards measuring utility in location privacy protection.
Also, information-theoretic metrics [37] require the input to be generated
from a probability distribution, which is not the case in this work.

##  X Conclusion

This paper presents four approaches to privately releasing ARP-request data
that can later be used for identifying anomalies in LAN. We prove that the
naïve approach satisfies edge-differential privacy, and thus provides privacy
protection on the user-relationship level. On the other hand, the histogram-
based approach can provide node-differential privacy, thus leaking no
information about a presence of each individual user. We also propose two
alternatives, named naïve-$\delta$ and histogram-based-$\delta$, which require
even smaller additive noises than their original counterparts in exchange for
a small probability that the privacy guarantee will not hold. Feasibility of
our approaches is demonstrated via real-world experiments in which we show
that, with a reasonable privacy budget value, our approaches yield low errors
($<10$ in RMSE) and also preserve more than 75% utility of detecting LAN
anomalies.

## References

  * IFP [2018] IFP, “6 hacks sure to defeat your firewall (and how to prevent them),” https://www.insightsforprofessionals.com/it/security/hacks-sure-to-defeat-your-firewall, 2018\.
  * Yan et al. [2008] W. Yan, Z. Zhang, and N. Ansari, “Revealing packed malware,” _IEEE Security & Privacy_, vol. 6, no. 5, pp. 65–69, 2008.
  * Chapple [2021] M. Chapple, “The threat of ransomware still looms large over healthcare,” https://healthtechmagazine.net/article/2021/06/threat-ransomware-still-looms-large-over-healthcare, 2021\.
  * Kern [2016] C. Kern, “95filtering,” https://www.varinsights.com/doc/of-ransomware-bypass-firewalls-email-filtering-0001, 2016\.
  * Valeo Networks [2021] Valeo Networks, “How is the internet of things (iot) being impacted by malware?” https://www.valeonetworks.com/how-is-the-internet-of-things-iot-being-impacted-by-malware/, 2021\.
  * Matsufuji et al. [2019] K. Matsufuji, S. Kobayashi, H. Esaki, and H. Ochiai, “Arp request trend fitting for detecting malicious activity in lan,” in _International Conference on Ubiquitous Information Management and Communication (ICUIMC)_ , 2019\.
  * Yasami et al. [2007] Y. Yasami, M. Farahmand, and V. Zargari, “An arp-based anomaly detection algorithm using hidden markov model in enterprise networks,” in _International Conference on Systems and Networks Communications (ICSNC)_. IEEE, 2007.
  * Ren et al. [2019] H. Ren, B. Xu, Y. Wang, C. Yi, C. Huang, X. Kou, T. Xing, M. Yang, J. Tong, and Q. Zhang, “Time-series anomaly detection service at microsoft,” in _ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2019.
  * Mobilio et al. [2019] M. Mobilio, M. Orrù, O. Riganelli, A. Tundo, and L. Mariani, “Anomaly detection as-a-service,” in _IEEE International Symposium on Software Reliability Engineering Workshops (ISSREW)_ , 2019.
  * Yao et al. [2017] D. Yao, X. Shu, L. Cheng, and S. J. Stolfo, “Anomaly detection as a service: challenges, advances, and opportunities,” _Synthesis Lectures on Information Security, Privacy, and Trust_ , vol. 9, no. 3, pp. 1–173, 2017.
  * Microsoft Azure [2020] Microsoft Azure, “Anomaly detector,” https://azure.microsoft.com/en-us/services/cognitive-services/anomaly-detector/, 2020\.
  * TIBCO Software [2021] TIBCO Software, “Anomaly detection — tibco software,” https://www.tibco.com/solutions/anomaly-detection, 2021.
  * Hu et al. [2016] J. Hu, C. Lin, and X. Li, “Relationship privacy leakage in network traffics,” in _2016 25th International Conference on Computer Communication and Networks (ICCCN)_. IEEE, 2016, pp. 1–9.
  * Srivatsa and Hicks [2012] M. Srivatsa and M. Hicks, “Deanonymizing mobility traces: Using social network as a side-channel,” in _ACM Conference on Computer and Communications Security_ , 2012.
  * Takbiri et al. [2018] N. Takbiri, A. Houmansadr, D. L. Goeckel, and H. Pishro-Nik, “Privacy against statistical matching: Inter-user correlation,” in _IEEE International Symposium on Information Theory (ISIT)_ , 2018.
  * Dwork et al. [2006] C. Dwork, F. Mcsherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in _Theory of Cryptography Conference (TCC)_ , 2006.
  * McSherry and Mahajan [2010] F. McSherry and R. Mahajan, “Differentially-private network trace analysis,” _ACM SIGCOMM Computer Communication Review_ , vol. 40, no. 4, pp. 123–134, 2010.
  * McSherry [2009] F. D. McSherry, “Privacy integrated queries: an extensible platform for privacy-preserving data analysis,” in _International Conference on Management of data_ , 2009.
  * Fan et al. [2014] L. Fan, L. Bonomi, L. Xiong, and V. Sunderam, “Monitoring web browsing behavior with differential privacy,” in _International Conference on World Wide Web (WWW)_ , 2014.
  * Wang et al. [2016] Q. Wang, Y. Zhang, X. Lu, Z. Wang, Z. Qin, and K. Ren, “Real-time and spatio-temporal crowd-sourced social network data publishing with differential privacy,” _IEEE Transactions on Dependable and Secure Computing_ , vol. 15, no. 4, pp. 591–606, 2016.
  * Dankar and El Emam [2013] F. K. Dankar and K. El Emam, “Practicing differential privacy in health care: A review.” _Trans. Data Priv._ , vol. 6, no. 1, pp. 35–67, 2013.
  * Fan and Xiong [2013] L. Fan and L. Xiong, “Differentially private anomaly detection with a case study on epidemic outbreak detection,” in _International Conference on Data Mining Workshops (ICDMW)_ , 2013.
  * Zhang et al. [2019] Z. Zhang, H. Esaki, and H. Ochiai, “Unveiling malicious activities in lan with honeypot,” in _International Conference on Information Technology (InCIT)_ , 2019.
  * Yeo et al. [2004] J. Yeo, M. Youssef, and A. Agrawala, “A framework for wireless lan monitoring and its applications,” in _Proceedings of the 3rd ACM workshop on Wireless security_ , 2004.
  * Whyte et al. [2005] D. Whyte, P. van Oorschot, and E. Kranakis, “Arp-based detection of scanning worms within an enterprise network,” in _Proceedings of the Annual Computer Security Applications Conference (ACSAC)_ , 2005.
  * Farahmand et al. [2006] M. Farahmand, A. Azarfar, A. Jafari, and V. Zargari, “A multivariate adaptive method for detecting arp anomaly in local area networks,” in _International Conference on Systems and Networks Communications (ICSNC)_ , 2006.
  * Bun and Steinke [2016] M. Bun and T. Steinke, “Concentrated differential privacy: Simplifications, extensions, and lower bounds,” in _Theory of Cryptography Conference (TCC)_ , 2016.
  * Dwork and Roth [2014] C. Dwork and A. Roth, “The algorithmic foundations of differential privacy,” _Foundations and Trends® in Theoretical Computer Science_ , vol. 9, no. 3–4, pp. 211–407, 2014.
  * Hay et al. [2009] M. Hay, C. Li, G. Miklau, and D. D. Jensen, “Accurate estimation of the degree distribution of private networks,” in _ICDM 2009, The Ninth IEEE International Conference on Data Mining, Miami, Florida, USA, 6-9 December 2009_ , W. Wang, H. Kargupta, S. Ranka, P. S. Yu, and X. Wu, Eds. IEEE Computer Society, 2009, pp. 169–178. [Online]. Available: https://doi.org/10.1109/ICDM.2009.11
  * Mironov [2012] I. Mironov, “On significance of the least significant bits for differential privacy,” in _ACM Conference on Computer and Communications Security_ , 2012\.
  * Montgomery and Mastrangelo [1991] D. C. Montgomery and C. M. Mastrangelo, “Some statistical process control methods for autocorrelated data,” _Journal of Quality Technology_ , vol. 23, no. 3, pp. 179–193, Jul. 1991. [Online]. Available: https://doi.org/10.1080/00224065.1991.11979321
  * Beimel et al. [2008] A. Beimel, K. Nissim, and E. Omri, “Distributed private data analysis: Simultaneously solving how and what,” in _Advances in Cryptology - CRYPTO 2008, 28th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2008. Proceedings_ , ser. Lecture Notes in Computer Science, D. A. Wagner, Ed., vol. 5157. Springer, 2008, pp. 451–468.
  * Tao et al. [2021] Y. Tao, R. McKenna, M. Hay, A. Machanavajjhala, and G. Miklau, “Benchmarking differentially private synthetic data generation algorithms,” _arXiv preprint arXiv:2112.09238_ , 2021.
  * Yang et al. [2017] X. Yang, T. Wang, X. Ren, and W. Yu, “Survey on improving data utility in differentially private sequential data publishing,” _IEEE Transactions on Big Data_ , 2017.
  * Xiao and Xiong [2015] Y. Xiao and L. Xiong, “Protecting locations with differential privacy under temporal correlations,” in _Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security_ , 2015, pp. 1298–1309.
  * Hua et al. [2015] J. Hua, Y. Gao, and S. Zhong, “Differentially private publication of general time-serial trajectory data,” in _2015 IEEE Conference on Computer Communications (INFOCOM)_. IEEE, 2015, pp. 549–557.
  * Lopuhaä-Zwakenberg et al. [2019] M. Lopuhaä-Zwakenberg, B. Škorić, and N. Li, “Information-theoretic metrics for local differential privacy protocols,” _arXiv preprint arXiv:1910.07826_ , 2019.