Emmanuelle Anceaume
email: emmanuelle.anceaume@irisa.fr

Yann Busnel
email: yann.busnel@ensai.fr

Nicolò Rivetti
email: nicolo.rivetti@univ-nantes.fr

Bruno Sericola
email: bruno.sericola@inria.fr

Identifying Global Icebergs in Distributed Streams Research report

Keywords: stream model, randomised approximation algorithm, generalised coupon collector problem, oblivious adversary, performance analysis

We consider the problem of identifying global iceberg attacks in massive and physically distributed streams. A global iceberg is a distributed denial of service attack, where some elements globally recur many times across the distributed streams, but locally, they do not appear as a deny of service. A natural solution to defend against global iceberg attacks is to rely on multiple routers that locally scan their network traffic, and regularly provide monitoring information to a server in charge of collecting and aggregating all the monitored information. Any relevant solution to this problem must minimise the communication between the routers and the coordinator, and the space required by each node to analyse its stream. We propose a distributed algorithm that tracks global icebergs on the fly with guaranteed error bounds, limited memory and processing requirements. We present a thorough analysis of our algorithm performance. In particular we derive an optimal upper bound on the number of bits communicated between the multiple routers and the coordinator in presence of an oblivious adversary. Finally, we present the main results of the experiments we have run on a cluster of single-board computers. Those experiments confirm the efficiency and accuracy of our algorithm to track global icebergs hidden in very large input data streams exhibiting different shapes.

I. INTRODUCTION

A Denial of Service (DoS) attack tries to take down an Internet resource by flooding this resource with more requests than it is capable of handling. A Distributed Denial of Service (DDoS) attack is a DoS attack triggered by many machines that have been infected by a malicious software, causing immediately the total shutdown of targeted web resources (e.g., e-commerce websites). A common approach to detect and to mitigate DDoS attacks is to monitor network traffic through routers and to look for highly frequent signatures that might suggest ongoing attacks. However, a recent strategy followed by the attackers is to hide their massive flows of requests by finely distributed them in a multitude of routes, so that locally, the malicious sub-flows do not appear as frequent, while globally they represent a significant percentage Θ of the network traffic [START_REF] Manjhi | Finding (recently) frequent items in distributed data streams[END_REF]. The term "global iceberg" has been introduced to describe such an attack as only a very small part of the latter can be observed from each single router [START_REF] Zhao | Global iceberg detection over distributed streams[END_REF]. A natural solution to track and detect global icebergs is to rely on multiple routers that locally scan their network traffic, and regularly provide monitoring information to a server in charge of collecting and aggregating all the monitored information. To be applicable, two issues must be solved. Firstly, routers must be capable of monitoring a very large number of flows to discover the presence of potential global icebergs and this must be done on the fly to have some chance to detect icebergs soon enough. Secondly, the frequency of the communications between routers and the server must be low enough to prevent the server from being overloaded by iterative exchanges with all the routers; however reducing the frequency of these exchanges must not jeopardise the detection latency of global icebergs and must not introduce false negatives (that is, the non-detection of global icebergs).

To address both points, one needs to design appropriate schemes for summarising the input streams [START_REF] Muthukrishnan | Data Streams: Algorithms and Applications[END_REF], namely algorithms capable of efficiently and accurately maintaining some function f over the prefix of a huge -potentially unboundedsequence of data items. By efficient, we mean that such algorithms must compute function f by scanning only once each data item of the input stream and by storing only a very small amount of information with respect to the number of data items received so far. By accurate, we expect that, despite their remarkable space-efficiency, such algorithms approximate function f with a guaranteed approximation error. Finally, to cope with adversarial strategies, such algorithms must be insensitive to the order in which data items are received.

The solution we propose to efficiently and accurately detect and identify global icebergs while preserving the server from being overloaded by all the monitored information, consists in relying on sketches and in locally organising items according to their estimated frequency. Only the most recent and high enough flows, i.e., those that locally represent at least a fraction Θ of the local stream, are tracked and sent to the server (called coordinator in the following), while the others are thrown away. This is achieved by locally splitting the interval [Θ, 1] into sub-intervals in a geometric way, and by maintaining a small number of buffers, Γ 1 , . . . , Γ , such that each Γ k will contain data items whose probability of occurrence matches the k-th interval. Each time one of these buffers is full, its content is sent to the coordinator. The coordinator polls all the other nodes to determine if global icebergs are indeed present. We show that our solution (ε, δ)approximates the detection of global icebergs, for any ε ∈ [0, 1] and δ ≤ 1/2 in a space efficient way. Moreover, we provide an optimal upper bound on the number of bits exchanged by our distributed algorithm. Finally, we have implemented our solution on a testbed of single-board computers fed with different shapes of streams (both synthetic and real traces). Numerical results clearly confirm that for any value of Θ, all the global icebergs are detected (i.e., no false negatives). They also show that the communication overhead due to our protocol (i.e., the number of bits communicated between the nodes and the coordinator to detect global icebergs) is very small (less than 1.2% of the global number of bits received by the routers). Finally, these experiments show that less than 3% of the global stream need to be read to detect all the global icebergs.

The outline of this paper is the following. Section II presents related works. Section III formally states the problem and describes the model we rely on to derive bounds of our algorithms. Section IV presents and analyses an omniscient and full-space algorithm that solves the global iceberg problem, while Section V presents a knowledge-free and space-efficient algorithm and analyses its quality. Finally, numerical results obtained from extended experiments conducted on single-board computers are studied in Section VI. Section VII concludes.

II. RELATED WORK

The detection of heavy hitters or global icebergs originating from multiple streams has first been studied by Manjhi et al. [START_REF] Manjhi | Finding (recently) frequent items in distributed data streams[END_REF].

In their paper, the authors propose a solution for detecting recent global icebergs by relying on a multi-level structure where each node must guarantee a degree of precision that depends on its level in the hierarchical structure. This structure helps to minimise the communication between nodes and the central coordinator. On the other hand, and in contrast to our work, they make the assumption that global icebergs are locally detectable at each node. In [START_REF] Zhao | Global iceberg detection over distributed streams[END_REF], the authors do not assume any more that nodes can locally detect global iceberg, however they suppose that there exists a gap between non iceberg frequencies and iceberg ones. That is, items that appear at least T times from the inception of the stream are global icebergs, while there are no items whose frequency belongs to an interval (λT, T ), with 0 < λ < 1. Based on this assumption, the authors can accurately detect the presence of global icebergs. Note that, in contrast to our work, they do not identify the global icebergs items, they only inform the coordinator that some global icebergs exist. In addition, in our work, we also (ε, δ)-approximate the size of each global iceberg. In [START_REF] Zhao | Finding global icebergs over distributed data sets[END_REF], the authors propose a solution that identifies items whose aggregated frequency over the distributed streams exceeds some given threshold, irrespective of the size of the input streams. Thus, their motivation is to detect global icebergs only during a fixed time interval (note that the same definition has been adopted by [START_REF] Zhao | Global iceberg detection over distributed streams[END_REF]). Their approach combines sampling and sketching through Bloom filters [START_REF] Bloom | Space/time trade-offs in hash coding with allowable errors[END_REF][START_REF] Cormode | An improved data stream summary: the count-min sketch and its applications[END_REF][START_REF] Demaine | Frequent estimation of Internet packet streams with limited space[END_REF][START_REF] Karp | A simple algorithm for finding frequent elements in streams and bags[END_REF][START_REF] Manku | Approximate frequency conuts over data streams[END_REF] to respectively sample and count items. Similarly to our solution, their strategy is robust to any adversarial items splitting, however we address a much more challenging model. The authors in [START_REF] Zhao | Finding global icebergs over distributed data sets[END_REF] suppose that each node locally knows prior to executing its algorithm the exact frequency of all the items it will receive. This model is commonly called the "distributed bag model". Finally, Yi and Zhang in [START_REF] Yi | Optimal tracking of distributed heavy hitters and quantiles[END_REF] propose a solution in the spirit of the ones proposed in functional monitoring to minimise the communication cost between the nodes and the coordinator. However this is achieved by requiring that each node maintains at any time the exact frequency of each received item in its stream, which is definitively a very strong assumption.

III. MODEL OF THE SYSTEM AND ADDRESSED PROBLEM

A. The distributed functional monitoring model

We present the computational model used to analyse our algorithms. This model follows the distributed functional monitoring model proposed by Cormode et al. [START_REF] Cormode | Algorithms for distributed functional monitoring[END_REF], which combines features of the data streaming model and communication complexity. Specifically, we consider a set S of nodes such that each node receives a continuous stream (or sequence) of items drawn from a large universe N . Items arrive quickly, in any order and may recur an arbitrary and unknown number of times in each stream. This allows us to model, for instance, the reception of high speed TCP/IP streams with different throughputs at each router. If TCP DDoS attacks are tracked, then the relevant items are the packet's destination IP addresses. Instead, if worms detection is investigated, then the relevant items are the packet's source IP addresses [START_REF] Estand | New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice[END_REF]. In the following we denote the different items by integers 1, . . . , n, with n = |N |. We denote by σ s the stream received by node s, s ∈ S, and by m s the size of the sequence of items prefix received from σ s so far. For any two nodes s and s in S, m s can be different from m s . Any input stream σ s implicitly defines an empirical probability distribution on the set of items it contains; the probability p j,s of occurrence of item j in σ s is approximated by f j,s /m s , where f j,s represents the number of times item j has occurred in σ s since the inception of σ s . Due to memory constraints, nodes can locally store only a small amount of information with respect to the size of their input stream and perform simple operations on them to keep pace with the data stream. Thus streams need to be processed sequentially and online, that is, any item of the stream that has not been locally stored for any further processing cannot be read again.

Nodes communicate solely with a dedicated node, called coordinator. Communications are initiated by nodes upon receipt of an item or a sequence of them in their input stream. This in turn triggers additional communications from the coordinator to some of the S nodes, where S = |S|. The goal of the coordinator is to continuously determine whether a given function applied on the union of received streams approximately exceeds some given threshold Θ ∈ (0, 1]. This is formalised in the next section.

The key property of the model is to maintain this knowledge by minimising both the space used by the S nodes and the number of bits exchanged between these nodes and the coordinator.

B. The global iceberg detection problem

The global iceberg detection problem has first been formalised by Estan and Varghese [START_REF] Estand | New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice[END_REF], and then adapted to different contexts [START_REF] Manjhi | Finding (recently) frequent items in distributed data streams[END_REF][START_REF] Zhao | Global iceberg detection over distributed streams[END_REF][START_REF] Zhao | Finding global icebergs over distributed data sets[END_REF]. In this paper, we extend this problem to the general distributed functional monitoring model [START_REF] Cormode | Algorithms for distributed functional monitoring[END_REF]. Informally, the global iceberg detection problem lies, for the coordinator, in quickly identifying any item j whose aggregated number of occurrences over the union of the distributed streams approximately exceeds some given fraction of the total size of all the streams since their inception. Such an item j is called a global iceberg. Specifically, we denote by σ the union of the S data streams σ s since the inception of σ s . We have σ = σ 1 ∪ . . . ∪ σ S . Let m be the number of items in σ. We have m = s∈S m s . Finally, let f j be the total number of occurrences of item j in σ.

Definition 1 (The global iceberg detection problem). For any given threshold Θ ∈ (0, 1], approximation parameter ε ∈ [0, 1], and probability of failure δ ≤ 1/2, the global iceberg detection problem consists for the coordinator C

• in outputting item j if f j ≥ Θm, and • in never outputting item j if f j < (1 -ε)Θm. This must be achieved by minimising both the space used by the S nodes and the number of bits exchanged between these nodes and the coordinator.

C. Adversary

We assume the presence of an oblivious adversary that tries to prevent the detection of global icebergs by judiciously distributing them in the S data streams so that none of the S monitoring nodes can locally detect an ongoing attack. By oblivious we mean that the adversary can adaptively insert any number of items to increase or decrease the number of global icebergs according to the current states of both the coordinator C, the S nodes and threshold Θ. Notice that the adversary may also strategise to make the coordinator a potential DDoS target by maximising the number of interactions between the S nodes and the coordinator. This is achieved by adversarially ordering items in the streams, and/or by injecting well chosen items. On the other hand, both the S nodes and the coordinator follow the prescribed protocols, that is, they are correct. We finally suppose that any algorithm run by any correct node is public knowledge to avoid some kind of security by obscurity. However we classically assume that the adversary has not access to the local random coins used in the proposed probabilistic algorithms.

IV. AN OMNISCIENT ALGORITHM TO TRACK GLOBAL

ICEBERGS

Prior to presenting our space-efficient and knowledge-free solution to the global iceberg problem, we first describe our algorithm by ideally assuming that each time a data item j is received in the input stream σ s , item j is tagged with the exact probability p j,s with which it will appear in σ s . Note however that the algorithm does not know ahead of time the items that will appear in σ s . Furthermore we suppose that each node s locally keeps track of items frequency count, i.e., the number of times each item j has been received so far at node s.

A. Principles of the solution

The pseudo-code of the algorithms run by each of the S nodes and by the coordinator are respectively provided in Algorithms 1 and 2. These algorithms work as follows. Each node s ∈ S reads on the fly and sequentially its input stream σ s . For each received item j, node s increments its frequency count F [j], and maintains the current size m s of its input stream, which is the number of items received so far in σ s . If p j,s ≥ Θ then j is a potential candidate for being a global iceberg and thus s keeps track of item j if not already done (see lines 9-27 of Algorithm 1). This is achieved by maintaining buffers Γ 1 , . . . , Γ , where = log 2 S + 1. 1 The interval [Θ, 1] is split into sub-intervals in a geometric way. Each buffer Γ k , whose size is denoted by c k , only contains items j whose probability p j,s matches the k-th interval. That is, buffer Γ k , with 1 ≤ k ≤ -1, contains items j whose probability p j,s verifies Θ+(1-Θ)/2 k < p j,s ≤ Θ+(1-Θ)/2 k-1 , and Γ contains items j whose probability p j,s satisfies Θ ≤ p j,s ≤ Θ + (1 -Θ)/2 -1 . The size c k of each of buffer Γ k , with 1 ≤ k ≤ , is set to n k × r , where n k is the maximum number of items that could fit the k-th buffer, and

0 < r ≤ 1. Since Γ k , for 1 ≤ k ≤ -1, contains items whose probability p j,s verifies Θ + (1 -Θ)/2 k < p j,s ≤ Θ + (1 -Θ)/2 k-1 , we set n k to 1/(Θ + (1 -Θ)/2 k ) and n = 1/Θ . Note that for r = 1, that is for all k, c k = n k , if
some buffer say Γ h is filled with c h items then it means that all the items j in the stream are uniformly distributed with p j,s = Θ + (1 -Θ)/2 h (and p j,s = Θ for h = ), and thus none of the other buffers can receive any single item. Thus in practice r is set to a value less than or equal to 1/2. When some buffer Γ k is full (i.e, Γ k contains c k items), node s sends all the items of Γ k , together with their frequency counts and the stream size m s to the coordinator (see lines 20-25 of Algorithm 1), and empties Γ k . Upon receipt of such a buffer, the coordinator queries the other S -1 nodes to get the frequency of each of the items sent by node s, if any (see lines 7-10 of Algorithm 2).

Finally, by combining all these pieces of information, the coordinator checks whether any of these items is a global iceberg or not (see lines 11-14 of Algorithm 2). Note that in contrast to [START_REF] Zhao | Global iceberg detection over distributed streams[END_REF], the coordinator is capable of identifying which are the global icebergs that is an important feature when tracking DDoS attacks. Finally, since the distribution of the items in σ s is unknown, one cannot guarantee that c k distinct items with a probability that matches Γ k exist in the stream σ s . Actually, even no item can appear in the stream with those probabilities. Thus to guarantee that all the potential icebergs in Γ k are at some point sent to the coordinator, a timer τ k is set upon receipt of the first item in Γ k , and is incremented each time node s reads an item from the input stream σ s . Timeout of τ k is set to H 1/Θ /Θ, where H n is the n-th harmonic number defined by H 0 = 0 and

H n = 1 + 1/2 + • • • + 1/n. Lemma 1

shows the derivation of that

Algorithm 1: Omniscient and full-space algorithm run at any node s ∈ S Input: An arbitrary input stream σs; Θ: threshold qualifying an item as a global iceberg; r: proportion size parameter of the buffers; timeout. Each time the coordinator detects a global iceberg j, it informs all the S nodes that j is a global iceberg (this amounts to returning Freq in Line 16 of Algorithm 2 to both the application and the S nodes). Nodes locally enqueue j (in FIFO order) in a specific buffer, denoted by Λ s , whose size is equal to r/Θ . Hence, when a node s locally detects that some item j is a potential global iceberg, then s does not inform the coordinator if j belongs to Λ s . Note that as the oldest detected global icebergs are progressively dequeued, Λ s contains at any time the last r/Θ global icebergs. The rationale of this feedback is to prevent nodes from repeatedly informing the coordinator of the presence of a global iceberg already detected by the coordinator.

1 foreach k ∈ {1, -1} do 2 Γ k ← ∅; n k ← 1/(Θ + (1 -Θ)/2 k ) ; c k ← rn k ; τ k ← (not-active, 0); 3 end 4 Γ ← ∅; n ← 1/Θ ; c ← rn ; τ ← (not-active, 0) ; 5 ms ← 0; Freq ← ∅; Λs ← ∅; 6 for j ∈ σs do 7 ms ← ms + 1; 8 F [j] ← F [j] + 1; 9 if p j,s ≥ Θ then 10 if p j,s ≤ Θ + (1 -Θ)/2 -1 then 11 k ← ; 12 else 13 k ← min{h ∈ {1, -1} | Θ + (1 -Θ)/2 h < p j,s }; 14 end 15 if j ∈ Γ k then 16 if Γ k = ∅ then 17 τ k ← (active, 0); 18 end 19 Γ k ← Γ k ∪ {j}; 20 if |Γ k | = c k then 21 for each {j} ∈ Γ k do 22 Freq ← Freq ∪{(j, F [j])}; 23 send message ("identify", ms, Freq) to C; 24 Γ k ← ∅; Freq ← ∅; τ k ← (not-active, 0); 25 end 26 end 27 end 28 foreach active timer τ k , k ∈ {1, } do 29 τ k ← (active, τ k + 1); 30 if τ k > H 1/Θ /Θ and Γ k = ∅ then 31 for each {j} ∈ Γ k do 32 Freq ← Freq ∪{(j, F [j])};
F req ← (j, F [j]); 41 if ∃k ∈ {1, }, j ∈ Γ k then 42 Γ k ← Γ k \ {j};
m ← m + m ; 9 for each (k, f k ) ∈ F do 10 Update F: f k ← f k + f k with (k, f k ) ∈ Freq; 11 for each (k, f k ) ∈ F do 12 if f k < Θm then 13 F ← F \ {(k, f k )};

B. Analysis of the omniscient algorithm

In this section we provide an upper bound of the number of bits communicated between the S nodes and the coordinator (see Theorem 2), and show that the omniscient algorithm solves the global iceberg problem (see Theorem 3).

1) Adversarial Strategies: We investigate whether malicious nodes can prevent the global iceberg problem from being solved. This amounts to showing that for any given threshold Θ ∈ (0, 1], and approximation parameter ε ∈ (0, 1], the adversary cannot compel the coordinator to return any items j such that f j < (1ε)Θm and cannot prevent the coordinator from returning all items j such that f j ≥ Θm by finely distributing the occurrences of item j among the S streams. Theorem 3 shows that Algorithms 1 and 2 exactly guarantee such properties.

Maximising the communication between the S nodes and the coordinator requires for the adversary to manipulate the S input streams so that the time needed to locally fill the buffers is minimised, and thus the frequency at which nodes communicate with the coordinator is maximised. Theorem 2 shows that this is achieved if, for all s ∈ S, all the global icebergs appear with the same probability in σ s .

2) Communication complexity of the omniscient algorithm: Communication between the S nodes and coordinator C is triggered each time a buffer becomes full or upon timeout. To analyse the communication cost, we study a generalisation of the coupon collector problem. Indeed, we have to determine the number of items, in expectation, that must be received at any node s ∈ S to locally fill buffer Γ k , 1 ≤ k ≤ . a) Preliminary results: In the general formulation of this problem, we have a set of n coupons with p i being the probability that coupon i is drawn and

p 1 + • • • + p n = 1.
The problem amounts to determine the distribution of the number T n of coupons that need to be drawn from set {1, 2, . . . , n} with replacement, till obtaining the full collection of the n different coupons. In our case, we consider a generalisation of this formulation, where we need to determine the distribution of the number T c,n of coupons that must be drawn, with replacement, to collect c ≤ n different coupons from the set {1, . . . , n}. The expected value of T c,n has been considered in [START_REF] Flajolet | Birthday paradox, coupon collectors, caching algorithms and self-organizing search[END_REF]. In addition we suppose that p = (p 1 , . . . , p n ) is not necessarily a probability distribution, that is

p 1 + • • • + p n ≤ 1 and we define p 0 = 1 -(p 1 + • • • + p n ).
This models the presence of a null coupon 0 that is drawn with probability p 0 but that is not allowed to belong to the collection of c items, 1 ≤ c ≤ n, among {1, . . . , n}. In the following, we denote by S i,n all the sets of items of {1, . . . , n} whose size is exactly equal to i, that is S i,n = {J ⊆ {1, . . . , n} | |J| = i}. Note that we have S 0,n = {∅}. For every J ∈ S i,n , we define P J = j∈J p j , with P ∅ = 0. Finally, since the distribution of T c,n depends on the vector p = (p 1 , . . . , p n ), we will use the notation T c,n (p) instead of T c,n , meaning by the way that the dimension of vector p is n. We have from [START_REF] Anceaume | Optimization results for a generalized coupon collector problem[END_REF] that for every n ≥ 1, c = 1, . . . , n and h ≥ 1

P{T c,n (p) > h} = c-1 i=0 (-1) c-1-i n -i -1 n -c J∈Si,n (p 0 + P J ) h , (1)
and that the expectation of T c,n (p) is given for every n ≥ 1 and c = 1, . . . , n by

E[T c,n (p)] = c-1 i=0 (-1) c-1-i n -i -1 n -c J∈Si,n 1 1 -(p 0 + P J ) , (2)
and that for every p = (p 1 , ..., p n ) with p 0 = 1 -

n i=1 p i and 0 < Θ ≤ p i for i = 1, . . . , n, E[T c,n (v)] ≤ E[T c,n (p)] ≤ E[T c,n (q)],
where vector v = ((1 -p 0 )/n, . . . , (1 -p 0 )/n), and vector q = (Θ, . . . , Θ, 1 -p 0 -(n -1)Θ). Note that the second inequality is true only for distribution p such that p i ≥ Θ. Vector v represents a scenario where all the coupons {1, . . . , n} are drawn uniformly, while vector q represents a scenario where they all occur with probability Θ except a single one that occurs with high probability 1 -p 0 -(n -1)Θ. Intuitively, vector v is the one that minimises the time to get a collection of c ≤ n coupons, while vector q is the one that maximises it when p i ≥ Θ > 0, for i = 1, . . . , n.

We now prove that E[T c,n (q)] ≤ H 1/Θ /Θ. Lemma 1. For every n ≥ 1, c = 1, . . . , n, and 0 < Θ ≤ p i for i = 1, . . . , n, we have

E[T c,n (q)] ≤ H 1/Θ /Θ.
Proof: The set S i,n can be partitioned into subsets S i,n and S i,n as follows: S i,n = {J ⊆ {1, . . . , n} | |J| = i and n ∈ J} and S i,n = {J ⊆ {1, . . . , n} | |J| = i and n / ∈ J}. Note that we have

S i,n = S i,n-1 , |S i,n | = n-1 i-1 and |S i,n | = n-1 i . We thus get, for p = q, J∈S i,n 1 1 -p0 -PJ = J∈S i,n 1 1 -p0 -PJ + J∈S i,n 1 1 -p0 -PJ = J∈S i,n 1 (n -i)Θ + J∈S i,n 1 1 -p0 -iΘ = n -1 i -1 1 (n -i)Θ + n -1 i 1 1 -p0 -iΘ
where the first term is 0 when i = 0. This leads from Relation [START_REF] Anceaume | New results on a generalized coupon collector problem using markov chains[END_REF] to E[T c,n (q)] = A + B, where

A = 1 nΘ c-1 i=0 (-1) c-1-i n -i -1 n -c n -1 i -1 n n -i and B = c-1 i=0 (-1) c-1-i n -i -1 n -c n -1 i 1 1 -p 0 -iΘ .

It is easily checked that

A = 1 nΘ (E[T c,n (u)] -1) ,
where vector u = (u 1 , . . . , u n ) is the uniform distribution defined by u i = 1/n. Note that it is equal to vector v when p 0 = 0.

From [START_REF] Flajolet | Birthday paradox, coupon collectors, caching algorithms and self-organizing search[END_REF], we have

E[T c,n (u)] = n(H n -H n-c ). (3)
For the second term we use the equality

n -i -1 n -c n -1 i = n -1 c -1 c -1 i .
We then get

B = n -1 c -1 c-1 i=0 (-1) c-1-i c -1 i 1 1 -p 0 -iΘ .
The change of variable i := c -1 -i gives

B = 1 1 -p 0 -(c -1)Θ n -1 c -1 c-1 i=0 (-1) i c -1 i 1 1 + βi , where β = Θ/(1-p 0 -(c-1)Θ). Note that since Θ ≤ (1-p 0 )/n we have 1 -p 0 -(c -1)Θ ≥ Θ.
The last sum in B is well-known and we have

B = 1 1 -p 0 -(c -1)Θ n -1 c -1 c -1 + 1/β c -1 ,
where the second fraction is equal to

= (n -1)! (n -c)! 1 (c -1 + 1/β)(c -2 + 1/β) • • • (1 + 1/β) = n -1 c -1 + 1/β n -2 c -2 + 1/β • • • n -c + 1 1 + 1/β . Now since Θ ≤ (1 -p 0 )/n, we have (1 -p 0 )/Θ ≥ n which leads to c + 1 β = 1 -p 0 Θ + 1 ≥ n + 1.
We thus get

n -1 c -1 c -1 + 1/β c -1 ≤ n -1 n • • • n -c + 1 n -c + 2 = n -c + 1 n .
Moreover, we have

1 1 -p 0 -(c -1)Θ = 1 Θ 1 (1 -p 0 )/Θ -(c -1) ≤ 1 Θ 1 n -c + 1 .
We then obtain B ≤ 1/(Θn) which gives

E[T c,n (q)] ≤ 1 Θ (H n -H n-c ) ≤ H c Θ . (4)
Given that c ≤ 1/Θ , Relation (4) concludes the proof.

By the way, we get from Relation (3),

E[T c,n (u)] ≤ E[T c,n (q)] ≤ 1 nΘ E[T c,n (u)].
b) Calculation of the communication cost to track global icebergs: We first derive the number of items that need to be received in each stream σ s , s ∈ S, to fill buffer Γ k , 1 ≤ k ≤ . This is done by applying the general formulation of the coupon collector to each buffer Γ k , k = 1, . . . , .

For each k = 1, . . . , -1, we denote by J k the set of all the items j in σ s whose probability of occurrence p j,s verifies

Θ + (1 -Θ)/2 k < p j,s ≤ Θ + (1 -Θ)/2 k-1 . We set j k = |J k |,
and we have j k ≤ n k (recall from Section IV-A, that n k represents the maximal number of items whose probability of occurrence is equal to the lower bound of the range, that is n k = 1/(Θ + (1 -Θ)/2 k ) ). For k = , we denote by J the set of all the items j in σ s whose probability of occurrence p j,s verifies Θ < p j,s ≤ Θ + (1 -Θ)/2 -1 . We set j = |J |, and we have j ≤ n with n = 1/Θ . Hence, S i,j k = {J ⊆ J k | |J| = i}, and for every J ∈ S i,j k , P J = j∈J p j,s .

Based on this, for each node s ∈ S, the expected number of items that need to be received from σ s to fill buffer Γ k is given by E[T c k ,j k (p)], with vector p = (p j,s

) j∈J k . From Relation (2), we have E[T c k ,j k (p)] = c k -1 i=0 (-1) c k -1-i j k -i -1 j k -c k J∈Si,j k 1 1 -(p 0 + P J )
,

where p 0 = 1 -P J k . We now determine the timer settings. The instant at which each timer τ k , 1 ≤ k ≤ , should fire must be short enough to bound the global iceberg detection latency, but sufficiently large to prevent the content of a buffer from being sent too often, that is well before it contains potential global icebergs. Our idea is to set the timer for a value that allows a buffer to be full, in expectation, whatever the frequency at which items recur the input stream. To simplify notation, we define τ (Θ) = H 1/Θ /Θ, and thus in accordance with Lemma 1, we set for every k = 1, . . . , , τ k = τ.

2mS(log m + log n) k=1 c k τ -1 i=0 P{T c k ,n k (v) > i} bits. (5)
Proof: From Algorithms 1 and 2, node s ∈ S triggers a transmission with the coordinator each time one of its buffers is full or upon timeout. Thus, assuming that s maintains a single buffer Γ k , then for m s large, the expected number of times node s sends the content of Γ k to the coordinator, denoted C k,s , verifies

C k,s ≤ m s E[min(T c k ,j k (p), τ ] = m s τ -1 i=0 P{T c k ,j k (p) > i}
,

where P{T c k ,j k (p) > h} = c k -1 i=0 (-1) c k -1-i j k -i -1 j k -c k J∈Si,j k (p 0 + P J ) h .
It has been observed (Theorem 3 in [START_REF] Anceaume | Optimization results for a generalized coupon collector problem[END_REF]) that for vectors p = (p j,s ) j∈J k and with p 0 = 1 -P J k and 0 < Θ ≤ p j,s ,

P{T c k ,j k (v) > h} ≤ P{T c k ,j k (p) > h}.
Thus, we have

C k,s ≤ m s τ -1 i=0 P{T c k ,j k (p) > i} ≤ m s τ -1 i=0 P{T c k ,n k (v) > i} .
Finally, we need to determine the number of bits sent each time buffer Γ k is full or upon timeout. From Algorithm 1, the sending of message "identify" requires log m s + c k (log n + log m s ) bits to be transmitted to the coordinator (where log m s represents the number of bits needed to code item frequencies, and log n the one needed to code item identifiers). By Algorithm 2, this triggers a round trip communication between the coordinator and the remaining S -1 nodes to collect the frequencies of all potential icebergs of Γ k (Line 44 of Algorithm 1 and Line 6 of Algorithm 2). This generates respectively S -1 messages of c k log n bits from the coordinator and a message of log m s + c k (log m s + log n) bits from each node s = s in S, where m s is the size of σ s . As the sum of all the local streams is equal to m, the number of bits sent because Γ k is full is less than 2Sc k (log m + log n). Thus, the fact that C k,s must be computed for all the buffers at every node s ∈ S, allows us to complete the proof of the lemma. Note that when Θ → 0, which is the case in the global iceberg problem, we have τ → ∞, and the denominator in Relation ( 5)

tends to n k (H n k -H n k -c k )[2].
3) Correctness of the omniscient algorithm: We now prove that the omniscient algorithm solves the global iceberg problem. Theorem 3. (Correctness) The omniscient algorithm (see Algorithms 1 and 2) deterministically and exactly solves the global iceberg problem (i.e, δ = 0 and ε = 0 ). Proof: The proof consists in showing that the algorithm does not output any items j such that f j < Θm (i.e., no false positive) and returns all items j such that f j ≥ Θm (i.e., no false negative).

Let us first focus on false positives. Suppose by contradiction that the coordinator returns at time t some item j such that f j < Θm. Then, by Algorithm 2, this means that the coordinator has received from some node s ∈ S a message "identify" for which j ∈ Freq. By Algorithm 1, this can only happens if node s has identified j as a potential global iceberg, that is, p j,s ≥ Θ (see Line 9 of Algorithm 1). Now, upon receipt of Freq, the coordinator collects from the other S -1 nodes the frequency of each item i ∈ Freq, and in particular j frequency, as well as the current size of their input stream (see Lines 7-10 of Algorithm 2). By Lines 12 and 13, the coordinator removes from Freq all the items whose frequency is less than Θm, and in particular item j. Thus the coordinator cannot return j at time t.

A false negative means that the coordinator does not return a true global iceberg. Suppose that there exists j such that f j ≥ Θm and j is not returned. Thus there exists at least one stream σ s such that p j,s ≥ Θ. By Lines 10-19 of Algorithm 1, j is inserted in the buffer Γ k that matches its occurrence probability p j,s (if not already present). By Lines 23 and 33, j is sent to the coordinator after at most H 1/Θ /Θ reading. By applying an argument similar to the above case, we get a contradiction with the assumption of the case.

To summarize, Theorem 3 has shown that the omniscient algorithm accurately tracks global icebergs, even if they are hidden in distributed streams. In addition, we have provided with Theorem 2 an upper bound on the communication cost between the S nodes and the coordinator. This bound is reached when each buffer is fed with items that all occur with the same probability.

V. KNOWLEDGE-FREE ALGORITHM TO TRACK GLOBAL

ICEBERGS

The algorithm we have proposed in Section IV relies on the assumption that upon receipt of item j at node s ∈ S, its probability of occurrence p j,s in the full stream σ s is known and that node s has no memory space restriction. Clearly both assumptions are unrealistic, in particular in presence of an adversary that may modify on the fly the occurrence probability of any items in the streams to affect the global iceberg detection algorithm.

A. Principles of the knowledge-free algorithm

We now propose an algorithm, called hereafter knowledgefree algorithm, that solves the global iceberg problem without making any assumption on the probability of occurrence of items in σ s , with s ∈ S. Instead, this algorithm builds an estimation of this knowledge from a compact synopsis of σ s computed on the fly and with a little space (with respect to the size of the input stream and the size of the domain from which items are drawn). This compact synopsis, called in the following Count-Min Sketch F , is built from the algorithm proposed by Cormode and Muthukrishnan [START_REF] Cormode | An improved data stream summary: the count-min sketch and its applications[END_REF]. In the following this algorithm is called the CM algorithm. For self-containment reasons, prior to presenting our algorithm, we recall some definitions and describe the main features of the CM algorithm.

1) Preliminaries: a) (ε, δ)-approximation: A randomised algorithm A is said to be an (ε, δ)-approximation of a function φ on a stream σ if for any sequence of items in σ, A outputs φ such that P{| φφ |≥ εφ} ≤ δ, where 0 < ε, δ < 1 are given as parameters of the algorithm.

b) 2-universal Hash Functions: A collection H of hash functions h : {1, . . . , n} → {0, . . . , n } is said to be 2universal if for every two different items i, j ∈ {1, . . . , n}, P h∈H {h(i) = h(j)} ≤ 1/n . Note that this is the probability of collision obtained if the hash function assigned truly random values to any i ∈ {1, . . . , n}. Carter and Wegman [START_REF] Carter | Universal classes of hash functions[END_REF] provide an efficient method to build large families of hash functions approximating the 2-universal property.

c) The Count-Min (CM) sketch algorithm [START_REF] Cormode | An improved data stream summary: the count-min sketch and its applications[END_REF]: The Count-Min Sketch algorithm approximates the frequencies of each item present in a stream. This approximation is done on the fly (items are read only once) and requires sub-linear memory space in the size of the input stream and in the size of the domain of the items. Briefly, the CM algorithm maintains a two-dimensional array F of s 1 × s 2 counters with s 1 = log(1/δ) and s 2 = e/ε , and by using 2-universal hash functions h 1 , . . . , h s1 (where e = exp(1)).

Parameters ε and δ, with 0 < ε, δ < 1, represent respectively the accuracy of the approximation, and the probability with which the accuracy holds. Both ε and δ are imposed by the user. Each time an item j is read from the input stream, this causes one counter per line to be incremented, i.e., F [u][h u (j)] is incremented for all u ∈ {1, . . . , s 1 }. Thus at any time, the sum of the counters of any given line is equal to the number of items m read from the input stream. When a query is issued to get an estimate fj of the number of times item j has occurred since the inception of the stream, the returned value corresponds to the minimum among the s 1 values of F [u][h u (j)], 1 ≤ u ≤ s 1 . Algorithm 3 presents the pseudo-code of the Count-Min Sketch algorithm. The error of the estimator in answering a query for fj is within a factor of ε(mf j ). The space required by this algorithm is proportional to log(1/δ)/ε, and the update time per element is sub-linear in the size of the sketch [START_REF] Cormode | An improved data stream summary: the count-min sketch and its applications[END_REF]. Specifically, after reading m items from the stream, we have

∀j ∈ N , P fj -f j ≥ ε (m -f j ) ≤ δ. (6)
2) The Knowledge-free Algorithm: The knowledge-free algorithm we propose combines the algorithm run by the coordinator (see Algorithm 2) and the algorithm presented in Algorithm 4. This algorithm, local to each node s ∈ S consists in the execution of two parallel tasks: Task 1 and Task 2 . Task 1 maintains an estimation of the frequency of occurrence of each received item in σ s and Task 2 is a simple adaptation of the omniscient algorithm presented in Algorithm 1. The adaptation consists in substituting Algorithm 3: Estimating the Frequency of Items in a Stream (Count-Min Sketch algorithm) [START_REF] Cormode | An improved data stream summary: the count-min sketch and its applications[END_REF] Input: An input stream σ; real values δ and ε; Output: The estimate fj for the frequency of any item j read from the input stream execute Algorithm 1 such that lines 9-13 are modified as below: the estimation fj,s of item j frequency in σ s for the exact frequency F [j] and in replacing the probability of occurrence p j,s in the full stream with fj,s /m s , where m s is the number of items received in the stream σ s so far. The CM algorithm strongly relies on 2-universal hash functions, to guarantee an δ)-approximation of item frequencies. If all the S nodes use the same set of hash functions in H, one may argue that the adversary could launch a dictionary attack to easily tamper with these estimations. In our solution, each of the S nodes locally and independently chooses at random its hash functions from H. We show in Section V-B that this does not prevent the coordinator from (ε, δ)-approximating the detection of global icebergs.

1 s 1 ← log(1/δ) ; 2 s 2 ← e/ε ; 3 F [s 1 ][s 2 ] ← 0; 4 Choose s 1 2-universal hash functions h 1 , . . . , hs 1 : N → {1, . . . , s 2 }; 5 for j ∈ σ do 6 for v = 1 to s 1 do 7 F [v][hv(j)] ← F [v][hv(j)] + 1;
if fj,s /ms ≥ Θ then if fj,s /ms ≤ Θ + (1 -Θ)/2 -1 then k ← ; else k ← min{h ∈ {1, -1} | Θ + (1 -Θ)/2 h <

B. Analysis of the knowledge-free algorithm

The following lemma shows that the knowledge-free algorithm is an (ε, δ)-approximation of the omniscient one, for any ε ∈ (0, 1) and probability of failure δ ≤ 1/2. This is achieved by sharpening the bounds obtained in [START_REF] Cormode | An improved data stream summary: the count-min sketch and its applications[END_REF] and by relying on Theorem 3. Specifically, Lemma 4 shows that for all items whose probability of occurrence is greater than or equal to Θ, then the randomised Count-Min Sketch algorithm is an (ε, δ)approximation of the item frequency computation. Lemma 4. For a stream σ, for any ε ∈ (0, 1) and probability of failure δ ≤ 1/2, Algorithm 3 run with s 1 = log(1/δ) and

s 2 = 2(1 -Θ)/εΘ guarantees that ∀j ∈ σ,    P fj -f j ≥ εf j ≤ δ if p j ≥ Θ P fj -f j ≥ ε (m -f j ) ≤ δ otherwise.
Proof: From [START_REF] Cormode | An improved data stream summary: the count-min sketch and its applications[END_REF] we have, for any ε ∈ (0, 1) and δ ≤ 1/2,

∀j ∈ σ, P fj -f j ≥ ε (m -f j ) ≤ δ. (7)
By Theorem 3, we can only focus on items j for which the probability of occurrence satisfies p j ≥ Θ. Let X j be the random variable representing the error made by the Count Min sketch algorithm [START_REF] Cormode | An improved data stream summary: the count-min sketch and its applications[END_REF] between the estimate fj and the real frequency f j . As p j ≥ Θ, then f j ≥ Θm. Note that as this lemma applies to any context where p j ≥ Θ, Θ ∈ (0, 1), we consider a single stream and denote by m its size. We then get m -

f j ≤ f j /Θ -f j = f j (1 -Θ)/Θ, leading to P fj -f j ≥ εf j ≤ P fj -f j ≥ εΘ m -f j 1 -Θ .
Moreover, every counter F [u][h u (j)] is equal to the sum of the exact frequencies of all data items that collide with j, that is, that share the same hashed value as the one of item j (i.e., all i ∈ N such that h u (i) = h u (j)). We first analyze the excess of a given counter

F [u][h u (j)] with u ∈ {1, . . . , s 1 }. Let X (u) j
denote the random variable that measures this specific excess. We have

X j = min u∈{1,...,s1} X (u) j , with X (u) j = i∈N \{j} f i 1 {hu(i)=hu(j)} . (8)
By the 2-universality property of each hash function from the chosen family, we have P{h u (i) = h u (j)} ≤ 1/s 2 . Thus, by linearity of the expectation, we get

E[X (u) j ] = i∈N \{j} E f i 1 {hu(i)=hu(j)} ≤ m -f j s 2 .
Since for every item j in the stream, f j ≥ Θm and X (u) j ≥ 0 for any u ∈ {1, . . . , s 2 }, we can apply Markov's inequality. Moreover, as s 2 ≥ 2(1 -Θ)/εΘ, we get

P X (u) j ≥ εf j ≤ P X (u) j ≥ εΘ m -f j 1 -Θ ≤ E[X (u) j ](1 -Θ) εΘ(m -f j ) ≤ 1 -Θ s 2 εΘ ≤ 1 2 . (9)
Relation ( 9) holds for any u ∈ {1, . . . , s 1 }. Algorithm 3 uses s 1 such estimators, mutually independent. By Relation [START_REF] The | DDoS Attack[END_REF], we are able to estimate the excess of fj as the minimum of X (u) j over all u ∈ {1, . . . , s 1 }. Then, we obtain

P fj -f j ≥ εf j = P min u∈{1,...,s1} X (u) j ≥ εf j = P X (1) j ≥ εf j , . . . , X (s1) j ≥ εf j = s1 u=1 P X (u) j ≥ εf j ≤ 1 2 s1 ≤ δ.
This concludes the proof.

Theorem 5. The knowledge-free algorithm presented in Algorithms 2 and 4 uses O((log n + log m) log(1/δ)(1/Θ -1)/ε + (log S log n)/Θ) bits of space on each node to (ε, δ)approximate tracking of global icebergs in arbitrarily distributed input streams.

Proof: By Lemma 4 applied to any stream σ s of length m s , with s ∈ S, Algorithm 3 returns an (ε, δ)-approximation of f j,s for all j ∈ σ s . Thus, using ((1/εΘ) log(1/δ)(log n + log m s )) bits of space, Algorithm 4 (ε, δ)-approximates the tracking of potential global icebergs at each node s. We now demonstrate that the coordinator correctly (ε, δ)-approximates the frequency of each item that has been locally detected as potential global icebergs at any node s. We have,

P s∈S fj,s -f j ≥ ε(m -f j ) = P s∈S fj,s -f j,s ≥ ε(m -f j ) = P s∈S min u∈{1,...,s1} X (u) j,s ≥ ε(m -f j ) ,
where X (u) j,s denote the random variable that measures, given u ∈ {1, . . . , s 1 }, the excess of a counter F [u][h s u (j)] on a specific node s. We clearly have min u∈{1,...,s1} s∈S X (u) j,s ≥ s∈S min u∈{1,...,s1} X (u) j,s . Then, by the mutual independence of the s 1 estimators, and since E[X (u) j,s ] ≤ ms-fj,s s2

[5], we have Then, given that locally the s 1 estimators are mutually independent, we have

P s∈S fj,s -f j ≥ ε(m -f j ) ≤ P min u∈{1,...,s1} s∈S X (u) j,s < ε(m -f j ) ≤ s1 u=1 P s∈S X (u) j,s < ε(m -f j ) As E[X (u) j,s ] ≤ ms-fj,s s2
(see proof of Lemma 4), we obtain

P s∈S fj,s -f j ≥ ε(m -f j ) ≤ s1 u=1 E s∈S X (u) j,s ε(m -f j ) = s1 u=1 s∈S E X (u) j,s ε(m -f j ) = s1 u=1 s∈S (m s -f j,s ) s 2 ε(m -f j ) = s1 u=1 m -f j s 2 ε(m -f j ) ≤ 1 2 s1 ≤ δ.
Similarly, by applying the same argument as above and the one of Lemma 4, we get that P s∈S fj,s -f j ≥ εf j ≤ δ if f j ≥ Θm in the global stream σ. Hence, Algorithms 2 and 4 (ε, δ)-approximate the omniscient approach presented in Section IV-A. By Theorem 3, the omniscient strategy implements a global iceberg detection, robust to any biased distributed input streams, which completes the second part of the proof. Finally, by Lemma 4, on each node, O((log n+log m s ) log(1/δ)(1/Θ-1)/ε) bits of space are required to (ε, δ)-approximate item frequencies. Moreover, the space required to locally track potential icebergs is the sum of the size used by each buffer Γ k , that is k=1 c k log n bits. By construction c k ≤ 1/Θ. Thus, an upper bound of the total space used is equal to O((log S log n)/Θ).

VI. EXPERIMENTAL EVALUATION

This section describes the main results obtained from the experiments run with the knowledge-free algorithm. All these experiments have been achieved on a testbed of S = 20 single-board computers (Raspberry Pi Model B) and two servers connected through a Gigabit Ethernet network. Single-board computers are small computers with limited memory and storage capacities (100 Mbps, 250MB RAM and 700MHz CPU). Each Raspberry Pi hosts a node, one of the two servers hosts the coordinator, while the other one generates all the S streams. Objective of these experimentations is a proof of concept. Actually, real routers (as for example, Cisco or Juniper type M or T, 10 Gbps throughput, from 768MB to 4GB of memory, Pentium CPU 1GHz) would definitively handle the code run by the small Raspberries. Experiments have been conducted on different types of streams and for different parameters settings. The single-board computers have been fed with both real-world datasets and with synthetic traces. This allows to capture phenomenons that may be difficult to obtain from real-world traces, and thus allows to check the robustness of our algorithm. Each run has been executed a hundred times, and we provide the mean over the repeated runs, after removing the 1-st and 10-th deciles to avoid outliers.

The following metrics are evaluated: (i) recall and precision of our solution, (ii) frequency estimation of global icebergs, (iii) communication cost induced by our solution to detect global icebergs and, (iv) detection latency of global icebergs.

a) Simulation results with synthetic traces: Synthetic streams have been generated using Zipfian distributions with α ∈ {0.5; 1.0; 2.0; 3.0}, denoted respectively by Zipf-0.5, Zipf-1, Zipf-2, and Zipf-3. Each stream is made of m s = 100, 000 items (i.e., the global stream is made of m = 2, 000, 000 items) picking them from an universe N whose size is equal to 10, 000. Each node receives around 4, 000 items per second. Several values of Θ have been considered, namely, Θ ∈ [0.005; 0.1], with logarithmic steps, as well as different values of r, i.e., r ∈ [0.005; 1.0]. For clarity reasons we show only the results of the experiments with the two extremum values of r, i.e, r = 0.005 (each buffer Γ k contains a single item, which amounts for the nodes to directly send each potential global iceberg to the coordinator), and r = 1 (all the buffer Γ k have their maximal size n k , see Section 4). In the following both cases will respectively be referred to as no buffer and with buffers.

The probability of failure δ and the error ε of the knowledgefree algorithm have been respectively set to δ = 0.1 and ε = 0.1. Using our proven bounds (see Lemma 4), this leads for each node to a memory usage of up to 7.5% of the one that would require a naive algorithm that would maintain a counter for each received item to determine which of them are potential icebergs or not. Actually, we show that using as little as 1.43% of the space of the naive algorithm is sufficient (see Table I). This is achieved by reducing the number of columns s 2 in the Count-Min sketch from s 2 = 2(1 -Θ)/(0.1Θ) (see Lemma 4) to s 2 = e/Θ . 3 Notice that in all the subsequent plots, the points are linked together by lines although they should appear as points. This has been only done to improve the readability of the plots.

b) Precision and recall: Figure 2 shows the precision and recall of our solution. By precision, we mean the number of global icebergs detected by our solution divided by the total number of detected items. By recall, we mean the number of global icebergs detected by our solution divided by the total number of generated global icebergs. The main result is that recall is always equal to 1 whatever the input streams features. This is a very important property of our solution as it shows that all the global icebergs are perfectly detected (there are no false negatives), even if global icebergs are well hidden in all the distributed streams (i.e., Θ = 3 For simplicity reason, we present memory usage with classical 32-bit coding. This is an overestimation of the requirement as only log n and/or log m are sufficient. 0.005). Now, this figure shows that precision is also very high when input streams follow Zipfian distributions with α ≥ 1 while for α = 0.5 it decreases. This is easily explained by the fact that with slightly skewed distributions (case with α ≤ 0.5), there are very few frequent items (one or two), and the gap between those frequent items and the most frequent sparse items (the ones with a relative frequency close but less than Θ) is very small (see Table II). Thus even a small over-approximation of Count-Min can wrongly tag them as frequent items. Tagging two items as frequent items when there is a single one makes a precision equal to 0.5. Notice that both the precision and the recall are independent from the size of the local buffers Γ k .

Figure 3 shows more details on the precision of our solution by showing the number of global icebergs that should be detected (referred to as generated) and the number of items that have been effectively detected as global icebergs by our knowledgefree algorithm (referred to as detected) as a function of Θ. By construction of the Count-Min sketch algorithm, item frequencies are over-estimated, thus the difference between the number of detected and effectively generated global icebergs corresponds to the number of false positives of our solution with the ε error. Note that the number of false positives may slightly increase with the size of the system due to the over-approximation of the sketch algorithm at each node. However, the absence of false negatives is guaranteed. For Θ = 0.005, Figure 3 shows the results presented in Figure 2. When Θ increases, the precision of our solution drastically augments whatever the form of the input distributions. c) Frequency estimation of global icebergs: Figure 4 compares the total number of occurrences of all the global icebergs as estimated by the knowledge-free algorithm with the total number of occurrences effectively generated. The overestimation of frequent items (i.e., those whose relative frequency exceeds Θ) is negligible as expected by Lemma 4. 5 and6 respectively show the ratio between the number of bits and messages exchanged by the knowledge-free algorithm and the number of bits and messages received in the input streams as a function of Θ. The primary remark is the negligible communication overhead induced by the algorithm to accurately detect global icebergs: strictly less than 8.5% of the size of all the distributed streams is exchanged by the nodes and the coordinator (Figure 5) even for slightly skewed distributions, which by Theorem 2, provide the upper communication bound. Notice the impact of buffers Γ k on the communication overhead for these slightly skewed distributions, for small values of Θ. Note that in terms of messages, the ratio is even better (less than 1, 12% of the content of all the streams in Figure 6), which is due to the fact that messages exchanged between the different parties carry a set of items, while an item is equal to a message in the input streams. All these results are very impressive compared to [START_REF] Zhao | Global iceberg detection over distributed streams[END_REF], which for highly skewed input distributions, get a ratio to raw data equal to 75% (see Sect. 7.B [START_REF] Zhao | Global iceberg detection over distributed streams[END_REF]).

e) Detection latency: Figure 7 shows the latency of our solution to detect global icebergs. This latency is computed as the time needed to detect all the global icebergs divided by the time needed to receive all the streams. The important and very remarkable feature of our solution is that less than 3% of the global stream need to be received to detect all the global icebergs (when the streams are randomly ordered). The second remark is the impact of buffers Γ k on the detection latency: locally keeping items in Γ k prior to sending them to the coordinator increases the detection latency by a factor 4 while it decreases the communication overhead by a factor 2 (see Zipf-1 with Θ = 0.005 in Figures 7 and6). There must exist some optimal value of r that should minimise the detection latency and communication overhead. Fig. 6. Ratio between the number of messages exchanged by the knowledge-free algorithm and the number of items received in the 20 input streams as a function of Θ.

their frequency in the distributed streams. We have also shown that simply maintaining the last detected global icebergs at the nodes drastically reduces the communication between the nodes and the coordinator. We will see that our algorithm enjoys the same features in presence of real datasets. f) Real trace results: We have fed our distributed algorithm with a real world dataset tracked during a DDoS attack; it has been retrieved from the CAIDA repository [START_REF] The | Anonymized Internet Traces[END_REF][START_REF] The | DDoS Attack[END_REF]. The total raw data size over the 20 nodes is m = 2×10 8 (with 32 bytes for flow size. There are in total n = 825, 695 unique destination address in this dataset (items in these experiments are destination addresses). This represents a 15-minute trace of traffic, monitored on OC192 Internet backbone links. Note that this dataset is definitely larger than the synthetic ones, drastically increasing the number of collisions in the Count Min sketch. This dataset has been split into 20 streams, each one sent to a different node of our testbed. The main results drawn from the analysis of these streams are summarised in Table III.

The DDoS target is the unique global iceberg, with a probability of occurrence equals to 0.15 (Θ = 0.1), as any other items occur with a probability lower than 5 × 10 -3 . As illustrated in Table III, the DDoS target is correctly detected (no false positives or negatives). The communication ratio is at most equal to 3.6 × 10 -4 (note that the ratio is computed as the size of the information exchanged between the parties divided by the size of the destination addresses contained in the full messages). These good results are mainly due to the large gap between probabilities of occurrence of the unique global iceberg and the other items, which occurs in classical DDoS attack.

VII. CONCLUSION

We have presented a distributed algorithm that deterministically detects all global icebergs either finely hidden or massively present in massive and physically distributed data streams. Moreover, we also (ε, δ)-approximate the size of each global iceberg. We have derived a thorough performance analysis by deriving bounds on the algorithm and performing real experiments on a cluster of single-board computers. These experiments have illustrated the enjoyable properties of our solution in terms of precision, recall, communication overhead and detection latency.

As future work, we plan to extend our solution to fit the requirements of long-lasting applications, including sensor-based monitoring ones. In this context, global icebergs do not necessarily reflect attacks but rather significative short-lived events. Extending our solution to the windowing data stream model should fit the specificities of such applications.

n 2 = 3 , c 2 = 2 n 3 = 6 , c 3 = 3 n 4 = 10 , c 4 = 5 n 5 =n 1 = 1 , c 1 = 1 Fig. 1 .

 232363410551111 Fig. 1. Data structure on node s ∈ S, with Θ = 0.04, r = 0.5 and S = 20.

33

  send message ("identify", ms, Freq) to C; 34 Γ k ← ∅; Freq ← ∅; τ k ← (not-active, 0); message ("freq ?", Freq) from the coordinator do 39 for each j ∈ F req do 40

  "freq", ms, Freq) to C; 45 upon receipt message ("Global Iceberg", F ) from the coordinator do 46 enqueue F in Λs;

Algorithm 2 : 2 m

 22 Algorithm run at the coordinator Input: Θ: threshold qualifying an item as a global iceberg; Output: The set F of global icebergs; 1 upon receipt message ("identify", m , Freq) from s do ← m ;F ← Freq; 3 for each (k, f k ) ∈ Freq do 4 (k, f k ) ← (k, null) ; 5 for each s = s ∈ S do 6 send message ("freq ?", Freq) to s ; 7 for each received message ("freq", m , Freq) from s , s = s do 8

  "Global Iceberg", F ) to each s ∈ S; 18 end

2

 2

Theorem 2 .

 2 (Upper bound on the communication cost) The omniscient algorithm (see Algorithms 1 and 2) exchanges in average no more than

10 Algorithm 4 :

 104 Upon query of Estimate(f j ): return fj = min 1≤v≤s 1 F [v][hv(j)]; Knowledge-free algorithm run at any node s ∈ S Input: An arbitrary input stream σs; real values δ and ε; Θ: threshold qualifying an item as a global iceberg; r: proportion size parameter of the buffers ; Initialisation of the data structure F of Algorithm 3 with s 1 ← log(1/δ) and s 2 ← 2(1 -Θ)/εΘ ; for j ∈ σs do Task T 1 : F ← Algorithm presented in Figure 3 fed with j; end Task T 2 :

Fig. 2 . 3 Fig. 3 .

 233 Fig. 2. Precision and recall as a function of the input distributions for Θ = 0.005 -with buffers.

Fig. 7 .

 7 Fig. 7. Ratio between the time needed by the knowledge-free algorithm to detect all the iceberg items and the time needed to receive all the 20 input streams as a function of Θ.

  Communication cost induced to detect global icebergs: Figures

	TABLE II
	FREQUENCY GAPS.

d)

  The study of this optimum represents a challenging open question. Main lessons learned from these experiments. We have shown the remarkable capability of the knowledge-free algorithm to accurately detect global icebergs in a space-efficient way whatever Fig.5. Ratio between the number of bits exchanged by the knowledge-free algorithm and the number of bits (of the items) received in the 20 input streams as a function of Θ.

	Communication Ratio (bits)	0.02 0.04 0.06 0.08 0.1		no buffer Zipf-0.5 no buffer Zipf-1 no buffer Zipf-2 no buffer Zipf-3	with buffer Zipf-0.5 with buffer Zipf-1 with buffer Zipf-2 with buffer Zipf-3
			0 0.005	0.01	Θ	0.05	0.1
	(messages)	0.015 0.02		no buffer Zipf-0.5 no buffer Zipf-1 no buffer Zipf-2 no buffer Zipf-3	with buffer Zipf-0.5 with buffer Zipf-1 with buffer Zipf-2 with buffer Zipf-3
	Communication Ratio	0.005 0.01
			0 0.005	0.01	Θ	0.05	0.1

  Communication Ratio (bits) without buffer 3.6 × 10 -4 Communication Ratio (bits) with buffers 3.2 × 10 -4

	Stream Size (m)	2 × 10 8
	Distinct Items (n)	825, 695
	Global Icebergs	1
	Detected Global Icebergs	1
	False Positives	0
	False Negatives	0
	Global Iceberg Frequency	3.2 × 10 6
	Estimated Global Iceberg Frequency	3.4 × 10 6

  TABLE III REAL-WORLD TRACE RESULTS -Θ = 0.1

For the sake of clarity, we will use the notation log to denote the logarithm in base

for the rest of this paper, unless otherwise specified.

For the sake of clarity, unless otherwise specified, we will use the notation τ to denote τ (Θ) if there is no ambiguity.

This work was partially funded by the French ANR project SocioPlug (ANR-13-INFR-0003), and by the DeSceNt project granted by the Labex CominLabs excellence laboratory (ANR-10-LABX-07-01).