Wei-Bo Chu et al.: Protecting User Privacy in a Multi-Path Information-Centric Network 587
contents provide a basis for analyzing the privacy of
multi-path ICN with random-caches. For more details
we suggest readers refer to [7].
2.1 Cache Snooping Attack
Cache snooping is a technique that uses timing in-
formation to infer the presence of interested content in
a network. B asically, this attack requires an adversary
to send interests/probes to the network , and then based
on the delays of fetching it, he/she decides whether the
interested content is cached by the network. For exam-
ple, after comparing the delay of fetching the interested
content from the network with the one of fetching con-
tent object from a first-hop ro uter’s cache, the adver-
sary can immediately determine that the content has
been recently requested by his/her neighbors if the two
delays are very close. Note that the delays of fetching
content from a first-hop router’s cache can be obtained
via a well-controlled process. More specifically, the ad-
versary can first disa ble the local cache of his/her own
device, a nd then continuously sends interests to the net-
work for a content with a size compa rable to the inter-
ested one. He/she then observes a series of content de-
lays. The delays of fetching content from the first-hop
routers’ cache can be well estimated by the minimum
of these delays. Some examples and scenario s of this
attack can be found in [8-12].
The attack has been shown very effective. Ac-
cording to the study in [7], the probability of de-
termining the presence of interested content from a
shared consumer-facing router’s cache can be higher
than 99.9%, and the attack still works under compli-
cated network topologies. As a result, cache snooping
is generally c onsidered as a major threat to users’ pri-
vacy in ICN.
2.2 A Formal Framework for Privacy
Evaluation
The propos e d framework for privacy evaluation
comprises of three different components, namely, sys-
tem model, adversary model, and privacy model. Let
us elabor ate these models.
System Model. In the framework, each router R
maintains an internal state for each content object C,
i.e., R records the number of times that C has been
forwarded by it. Denote S as the state and S (C) the
number of times that C has been forwarded.
Meanwhile, a cache management algorithm CM
controls R’s response to interests. For security con-
cerns, CM can hide cache hits but it cannot hide cache
misses. In par ticular, when the requested co ntent is in
cache, CM can hide cache hits simply by not using the
cache and forwarding the interest to content source, or
by introducing ar tificial delays be fore returning the con-
tent. Mathematically, this process can be modeled as
a probabilistic algor ithm Q
S
: NM → {0,1}, where NM
denotes the content name space. Q
S
(C) outputs 1 if the
required content C is cached in the router with state S
and a cache hit is generated, and it outputs 0 if a cache
miss occurs. After forwarding the content C, CM in-
crements S (C) by 1, a nd it keeps S (C
′
) unchanged for
all other co ntent C
′
6= C.
Adversary Model. Given the above setting, an ad-
versary A is able to launch cache snooping attacks by
interacting with R. To be specific, the adversary learns
the information about the content forwarded by R by
querying Q
S
(C), and based on the observed outputs, A
then determines whether the interested content C is in
R.
Privacy Model. The conce pt of (ε, δ)-probabilistic
indistinguishability is used to define and evaluate cache
privacy. The definition is given in [7]. We present it
here for completeness.
Definition 1 ((ε, δ)-Probabilistic Indistinguisha-
bility). Two distributions D
1
and D
2
are (ε, δ)-
probabilistic indistinguishable, if we can divide the out-
put space Ω = Range(D
1
) ∪ Range(D
2
) into Ω
1
=
Range(D
1
) ∩ Range(D
2
) and Ω
2
= Ω\Ω
1
such that
• for all O ∈ Ω
1
, e
−ε
6
Pr(D
1
=O)
Pr(D
2
=O)
6 e
ε
,
• Pr(D
1
∈ Ω
2
) + Pr(D
2
∈ Ω
2
) 6 δ.
From the above definition, we can see that ε de-
scribes the probabilistic differences of the output of D
1
and D
2
in their intersection, and δ measures the size
of their difference set. As a result, the larger ε and δ,
the more the differences of the two distributions. In
other words, if both ε and δ are very small, then the
two distributions are considered to be identical.
In the framework, (ε, δ)-probabilistic indistin-
guishability is used to evaluate cache privacy. The idea
is to treat the responses of a cache under probes as a
random process. T hus two output sequences can be
obtained when an adversary sends queries to the cache
with and without the interested content (see Fig.1).
The distributions of the two output sequences can b e
calculated, and then their difference can be evaluated
by the (ε, δ )-probabilistic indistinguishability. Intui-
tively, if ε a nd δ a re b oth very small, then it is regarded
that cache privacy is well protected.