Tristan Allard
email: tristan.allard@irisa.fr

Davide Frey
email: davide.frey@inria.fr

George Giakkoupis
email: george.giakkoupis@inria.fr

Julien Lepiller
email: julien.lepiller@irisa.fr

Lightweight Privacy-Preserving Averaging for the Internet of Things

The number of connected devices is growing continuously, and so is their presence into our everyday lives. From GPS-enabled fitness trackers, to smart fridges that tell us what we need to buy at the grocery store, connected devices-things-have the potential to collect and make available significant amounts of information. On the one hand, this information may provide useful services to users, and constitute a statistical gold mine. On the other, its availability poses serious privacy threats for users. In this paper we propose a novel protocol that makes it possible to aggregate personal information collected by smart devices in the form of an average, while preventing attackers from learning the details of the non-aggregated data. 1

Introduction

The Internet of Things has become a reality. Personal connected devices allow people to keep track of their weight, their fitness progress, or the distance they walk. Medical devices can inform doctors in real time about the health parameters of the patient wearing them. Smart environmental monitors make it possi-ble to aggregate data into detailed maps to monitor pollution, weather, or other parameters. Home appliances like refrigerators connect to the Internet to tell people what to buy at the grocery store, while smart meters collect information from one's home electricity usage to compute area statistics and optimize distribution. It is easy to foresee that more and more devices will become available in the near future and that more and more of them will access and make available personal data.

These data constitute a gold mine not only for their direct recipients-doctors, users, electrical companies-but also for researchers, companies, or even end users interested in global statistical information. Electrical companies already use data about electric consumption to manage their smart-grid infrastructures. Public health agency could use data from health sensors to identify areas of a city that have a higher risk for a given disease. Supermarkets may use the data from smart fridges to adapt their stocks to the demands of their customers. However, the state-of-the art equates the implementation of these use cases with clear threats to the privacy of users.

Today's typical IoT applications collect the data of huge numbers of users into a single data store, possibly on the cloud or on a private data center, and process it, for example to compute relevant statistics. But this gives the application provider unconditioned access to the data of all users.

A promising solution to the privacy issues associated with the analysis of large-scale privacy-sensitive information consists instead in decentralizing the processing itself. Keeping data where it is generated prevents service providers from accessing sensitive user information. However, decentralizing computation, whether on the edge or through completely peer-topeer protocols, does not automatically eliminate all privacy risks. Even if sensors themselves aggregate data in a peer-to-peer fashion, they may still leak sensitive information to potentially malicious neighboring devices.

To address privacy in decentralized data processing, some authors have proposed the use of homomorphic encryption techniques [START_REF] Allard | Chiaroscuro: Transparency and privacy for massive personal time-series clustering[END_REF][START_REF] Danner | Fully distributed privacy preserving mini-batch gradient descent learning[END_REF]. But like in the case of centralized solutions, the high cost associated with encryption and decryption operations makes them ill-suited to environments consisting of low-power devices like most IoT nodes.

In this paper, we address the limitations of existing techniques by proposing a novel lightweight protocol for decentralized averaging. The protocol exploits randomness and decomposition into shares as techniques to obfuscate the value associated with each node, and lightweight encryption techniques to withstand eavesdropping attacks. Although a thorough evaluation is out of the scope of this paper, we briefly analyze the protocol's resistance to colluding nodes and to eavesdropping attacks.

Background and Requirements

We focus on the problem of computing the average of a set of values in a decentralized manner while maintaining the individual values private. To this end, we take inspiration from existing decentralized averaging protocols, and in particular from the gossip-based aggregation solution in [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF].

In the epidemic protocol in [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF], each participating node maintains and iteratively refines a local approximation of the desired aggregate (the average). Initially, each node sets the value of its local approxima-tion to its own value. Then it updates it as a result of gossip exchanges. In particular, each node, u, periodically contacts a random other node, v. The two nodes, u and v, exchange and update their values so that they both correspond to the average of the two values before the exchange.

This simple protocol causes the local estimates of all nodes to converge to the average of all the initial values. [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF] further analyzes the speed of convergence and shows that it does not depend on the number of nodes but only on the variance of the initial distribution of values. This makes the protocol particularly suited to very large scale networks, and the very simple computation performed at every gossip exchange makes the protocol an excellent candidate for monitoring devices with limited computing power.

Unfortunately, this decentralized averaging protocol requires each node to exchange its initial value with another node at the beginning of the protocol. This makes the protocol unable to operate on privacy-sensitive information. To address this limitation, we propose a protocol that is at the same time: (i) lightweight, and (ii) resistant to honest-butcurious adversaries.

Lightweight Operation

Large-scale systems consisting of communicating "things" require lightweight protocols that can operate on devices with limited memory, computation, and communication capabilities and rules out solutions based on expensive encryption techniques. For example, Chiaroscuro [START_REF] Allard | Chiaroscuro: Transparency and privacy for massive personal time-series clustering[END_REF] includes an privacypreserving variant of [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF]. But we experimentally verified that its encryption and decryption operations can take as long as 200s on a RaspberryPI, an already fairly powerful device.

Attack Resilience

We aim to design a protocol that can enable a set of cooperating users to compute the average of their initial values, while limiting the information that can be deduced by attackers. We consider two types of attackers: a node attacker, and an edge-attacker, which we describe in the following.

Node Attacker

The node attacker models the case in which one or more users attempt to learn the initial values of a target user while participating in the protocol. We consider an honest-but-curious node attacker that controls a set of c nodes. Each of the controlled nodes, faithfully follows the protocol, but it forwards all the information it receives to the attacker which attempts to learn the initial value of a target node. Equivalently, we can view this attack as being played by a set of colluding users that follow the protocol, and exchange information to learn the initial value of the target user.

Edge/Eavesdropping Attacker The edge, or eavesdropping, attacker models instead the case in which a network service provider, or other external entity can observe all communication links between the users connected to its network. Again, we assume the attacker to be honest but curious, meaning that it cannot modify the data being exchanged. However, it will try to use all the information it observes to infer the initial value of a target node.

Private Lightweight Averaging through Random Shares

To address this problem, we start by observing that the protocol in [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF] operates by having nodes exchange successive approximations of the average of all the nodes values. While towards the end of the protocol's execution, all values tend to be similar to each other, at the beginning they are very different, and at the first round, each node exchanges its own original value, the value that we wish to protect. More precisely, after k rounds of execution, we can intuitively observe that the value held and shared by a node will be the result of the average of O(2 k ) values. Based on this observation, it appears therefore clear that the protocol in [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF] leaks most of the information about a node in the first few rounds of its execution, while it leaks almost none in later rounds. While some existing protocols protect this information by means of homomorphic encryption techniques [START_REF] Allard | Chiaroscuro: Transparency and privacy for massive personal time-series clustering[END_REF], we adopt a more lightweight solution. We obfuscate the initial value of a node by decomposing it into a set of s shares, that is s values whose average corresponds to the initial value of the node. After creating the shares, each node creates a new virtual node for each of these shares and participates in the same protocol as in [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF] with each of its virtual nodes. Specifically, in each round, a node u selects the value of one of its virtual nodes u i and sends it to another node v; upon receiving the message, v also randomly selects one of its virtual nodes v j and sends the corresponding value back to u. Both u and v then update the values of their corresponding shares so that they are both equal to

V(ui)+V(vj ) 2
, where V(x) denotes the value of virtual node x.

Creating Random Shares This simple idea, which takes inspiration from well-known secretsharing techniques [START_REF] Shamir | How to share a secret[END_REF], effectively protects the initial value of the target node from curious nodes (node attacker from Section 2.2) provided that the value of each virtual node lies sufficiently far from the node's real initial value.

To achieve this, each node builds its random shares by adding a random value to its original value. The choice of this value clearly determines the effectiveness of the obfuscation solution. For example, a value drawn from a bounded interval would make high and low values easy to guess. We therefore opt for a distribution over an infinite domain: a Gaussian with a mean of µ = 0 and a variance of σ 2 . We explore possible values for σ in Section 4.

Protection from the Edge Attacker As suggested above, the use of virtual nodes with perturbed initial values serves as a protection from a node attacker that controls one or more curious network nodes. However, it offers absolutely no protection against an edge attacker, that is one that can observe all the messages exchanged by a node, or by a set of nodes. Such an attacker can simply monitor the messages sent and received by a node and average the corresponding values. By monitoring the exchanges, the attacker can thus easily compute the initial value of any node.

To counteract this kind of attack, we therefore aug- ment our protocol with public-key encryption. To this end, we rely on the underlying peer-sampling protocol to disseminate the public key of nodes along the lines of [START_REF] Boutet | Freerec: An anonymous and distributed personalization architecture[END_REF], and use them to encrypt the messages sent during the first phases of the protocol. As we show in Section 4, a few encrypted rounds suffice to protect the privacy of users thanks to the convergence properties of the averaging protocol. Additionally, nodes send encrypted bait messages-empty messages-to random nodes to mask the set of nodes they are communicating with. Nodes receiving such messages reply with their own encrypted bait messages.

Analysis

Node Attacker We start by considering a simple attack in which a coalition of c colluding nodes, attempts to obtain all the shares from a given target node thereby learning its initial value. 2 In this preliminary analysis, we assume that nodes run a byzantine resilient peer-sampling protocol (e.g. [START_REF] Bortnikov | Brahms: Byzantine resilient random membership sampling[END_REF]) that prevents nodes from communicating with the same node too often, and that the samples provided by such a protocol are independent of each other. Finally, we assume that nodes exchange the values of their shares in a round-robin fashion: they first do a first exchange for all their shares, then a second exchange for all their shares and so on. The most straightforward way for this attack to succeed consists in the target node's doing the first exchange for each of its shares with one of the colluding nodes. If the network comprises n nodes, of which c controlled by the attacker, then a node will exchange a given share with an attacker with a relatively small probability, c n . However, the attacker may learn about the value of a node's share indirectly if it has information about the nodes that have previously communicated with the target. Precisely modeling the probability that an attacker may perform this kind of inference would be quite complicated. But we may easily compute an upper bound if we observe that if the target node communicates the initial value of a share to another node which is also communicating the initial value of its share, then the attacker will never be able to learn the exact value of either of these, but only their average. Conversely if the target node communicates the initial value of a share to a node that has already communicated its share value to someone else, then there is a possibility that the attacker may exploit this information. To model this probability, consider a node A that is exchanging its ith share with node B. Let P (i, j) be the probability that B has already exchanged j values since the beginning of the protocol. If we consider i to be the average number of exchanges since the start of the protocol, then we can model P (i, j) as a Poisson distribution with parameter i:

P (i, j) = i j e -i j! .
The probability that, after i communication steps, a specific node has already exchanged all its original values P Xall corresponds to the probability of having exchanged at least s values, that is:

P Xall (i) = 1 - s-1 j=0 P (i, j).
The probability, P learn , that the attacker will learn about all the s shares of a specific node can therefore be bounded from above as follows:

P learn ≤ s i=1 c n + n -c n • P Xall (i) .
From this, we can bound the probability P any of an attacker's learning all the shares of at least one node.

P any ≤ (n -c) • P learn .

Figure 1 depicts this probability and evaluates the number of shares required to manage different percentages of attackers (corruption) with increasing network sizes (n varying from 100 to 100, 000). For example, the left plot shows that 10 shares provide enough if the attacker controls 10% of the nodes, while 30 are required to withstand an attacker controlling half of the network.

Edge Attacker

The edge attacker has no way to acquire the initial values of a node's share since nodes encrypt the first rounds of exchanges. However, it can easily monitor all the data exchanged by nodes as soon as non-encrypted rounds begin. By monitoring the non-encrypted rounds, the attacker can easily estimate the average of a node's current share values. The information this provides will depend on the number of encrypted rounds as well as on the variance of the noise added when creating the shares. To evaluate this trade-off we ran an experiment with a network of n = 1, 000 nodes. One high-valued node starts with an initial value of 10, 000 while all the other low-valued nodes start with an initial value of 0. Initially each node creates its shares by adding a normally distributed noise N (val, σ). Then the protocol runs for k encrypted rounds after which we measure the average of the shares of the node that started with a value of 10, 000, and that of a node that started with a value of 0. We repeat the experiment 10, 000 times to obtain a distribution of values for both high-and low-valued nodes. Figure 2 compares the resulting distributions for several configurations. Results show that privacy can be enhanced by increasing either k or σ. Yet we expect that increasing σ may make the protocol more vulnerable to churn in the first rounds.

The use of gossip to aggregate information lies on well established results [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF]. But only recently have researchers started to explore how to tweak these well known aggregation protocols in order to preserve privacy. One of the authors of this paper proposed a decentralized system for k-means computation which provides a differentially private average [START_REF] Allard | Chiaroscuro: Transparency and privacy for massive personal time-series clustering[END_REF]. Yet, the protocol relies on expensive homomorphic encryption primitives that make it unsuitable for IoT scenarios.

Another recent contribution [START_REF] Hegedus | Distributed differentially private stochastic gradient descent: An empirical study[END_REF] uses gossip to achieve differentially private stochastic gradient descent. The use of noise to achieve differential privacy may appear similar to what we do in this paper, but contrary to [START_REF] Hegedus | Distributed differentially private stochastic gradient descent: An empirical study[END_REF], we seek to eliminate noise to obtain as precise an average as possible, rather than a differentially private one. Some related work [START_REF] Danner | Fully distributed privacy preserving mini-batch gradient descent learning[END_REF] proposes the use of shares for gradient descent learning. However, unlike our protocol, their solution still relies on expensive homomorphic encryption.

Finally, [START_REF] Benkaouz | A distributed protocol for privacy preserving aggregation with nonpermanent participants[END_REF] proposes DiPA, a protocol that also relies on shares but with a more structured topology. This requires special mechanisms to deal with node failures which are not required in the case of gossip. Moreover DiPA does not take into account the presence of an edge attacker.

Conclusions

We presented a novel protocol for privacy-preserving averaging. The protocol is resilient to colluding nodes as well as to eavesdropping attacks, without relying on expensive homomorphic encryption operations. Our preliminary results encourage us to perform a more thorough evaluation of security and scalability properties, while addressing open questions like the impact of stronger attackers.

Figure 1 :

 1 Figure 1: Success probability for the node attacker.

(a) k = 1 ,

 1 σ = 10, 000 (b) k = 3, σ = 10, 000 (c) k = 1, σ = 30, 000

Figure 2 :

 2 Figure 2: Distributions seen by edge attacker: impact of the number of encrypted rounds, k, and of the noise's standard deviation, σ, with s = 5 shares.

Albeit appearing last in alphabetical order, Julien Lepiller was the main contributor to the work in this paper.

A more sophisticated attack could consist in acquiring only a subset of the shares thereby obtaining an approximation of the actual value. We leave the analysis of such a variant to future work.

Acknowledgments.

This work was partially funded by the Region of Brittany, France, 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).


Ondřej Kuželka
email: kuzelkao@cardiff.ac.uk

Yuyi Wang
email: yuyi.wang@tik.ee.ethz.ch

Jan Ramon
email: jan.ramon@inria.fr

Bounds for Learning from Evolutionary-Related Data in the Realizable Case

This paper deals with the generalization ability of classifiers trained from non-iid evolutionary-related data in which all training and testing examples correspond to leaves of a phylogenetic tree. For the realizable case, we prove PAC-type upper and lower bounds based on symmetries and matchings in such trees.

Introduction

Modeling evolutionary aspects of species correctly is crucial for many biological problems. An important challenge is that usually only the genomes and phenotypes of today's individuals can be observed, while their ancestry and the characteristics of their ancestors are uncertain. In a number of cases, e.g. for haploid species, it is a reasonable approximation to assume that evolution follows a tree, i.e. that every individual only has one parent. Such trees representing individuals and their ancestors are called phylogenetic trees. There is a large body of work studying techniques for deriving phylogenetic trees from the genomes of the leaves [START_REF] Lemey | The phylogenetic handbook: a practical approach to phylogenetic analysis and hypothesis testing[END_REF][START_REF] Mossel | Learning nonsingular phylogenies and hidden Markov models[END_REF]. Similar techniques are also used in other fields, e.g. in stemmatology to reconstruct the ancestry of historic documents.

While reconstructing phylogenetic trees has been thoroughly studied, there has been much less attention to learning theory exploiting the phylogenetic tree information. In particular, consider a set of individuals for which we know the genomes and ancestry, and assume that we know for a subset of these individuals a target value (phenotype) which depends on the genome (features). The individuals are not independent as they inherit properties from common parents, and hence we can't assume they are distributed identically and independently (iid), which makes most classic generalization bounds inapplicable. Can we construct a new generalization error bound which not only depends on the number of training examples, but also on the relationship through the phylogenetic tree with the testing examples on which we want to make a prediction? An adequate answer to this question would be of significant value in a lot of bio-medical experimental research. Example 1. Let us consider the following hypothetical scenario. A lab O (origin) cultivates a strain of bacteria in petri dishes and then distributes samples to labs A, B, C and D. Labs A, B, C and D then search for hypotheses about gene mutations for some phenotype (e.g. resistance to antibiotics). Now, something strange happens: the hypotheses from labs A, B and C usually work well on each others data but the hypotheses from lab D do not work on data from A, B, C and vice versa. After reconstructing the phylogenetic tree of the bacteria from all four labs, it may turn out that the bacteria which lab D received is actually an almost isolated subpopulation for which generalizing to the rest of the population is difficult (as we show rigorously in this paper). A machine learning practitioner may try to explain this phenomenon by pointing out that the training and testing data is not iid. But the data is not iid for A, B and C either, even though they are mixed, so such an explanation would not be sufficient.

We derive probabilistic bounds shedding light on phenomena such as the one described in the above example. We model the task of learning from evolutionary-related data using complete binary trees and develop techniques to bound test-set errors of classifiers trained from such trees in the realizable case, i.e. when there is a hypothesis achieving zero training error. We provide both lower bounds and upper bounds. This is important because without the lower bounds, we would not have any means to check to what extent the upper bounds make sense in situations when they are much more pessimistic compared to learning from iid data (e.g. in situations where the training and testing data come from almost separated subpopulations).

Allowing ourselves to speculate a bit, the theoretical results presented in this paper may also be relevant to problems of organism immunization. For instance, it seems to be typically the case that people vaccinated against one strain of flu may be immune also against similar strains but not necessarily to the more distant ones [START_REF] Carrat | [END_REF]. If we think of immunization as learning of immune system to cope with germs, the analysis described in this paper may be very relevant.

Preliminaries

A tree is a simple, undirected, connected, acyclic graph. When a special node is designated to turn a tree into a rooted tree, it is called the root. In such a tree, each of the nodes that is one edge further away from the root than a given node is called its child (parent can be defined correspondingly).

The depth of a rooted tree is the distance from the root to the farthest leaf node. If every node in a tree has at most two children, this tree is a binary tree. Every non-root node with degree 1 is a leaf of the tree. An ordered rooted binary tree is a binary tree in which children of non-leaf nodes are distinguished, called left and right child, respectively. If T is a tree, we denote by L(T ) its left subtree and by R(T ) its right subtree. Similarly, L(T, v) and R(T, v) denote the left and right subtree of the subtree of T rooted in v. Unless stated otherwise, when speaking of trees, we assume that they are complete, ordered and binary, and their leaves are indexed by increasing integers (from left-most to right-most). Leaves of trees may also be labeled (not to be confused with indexing of leaves which is given by ordering of the nodes in a given tree).

As long as we keep working only with complete ordered binary trees, we can represent labelings of leaves of any tree T by a sequence z = (z 1 , z 2 , . . . , z m ) with m = 2 d where d is depth of the tree, z 1 is the label of the left-most leaf, z 2 is the label of the second left-most leaf and so on. For instance, the labeling of the tree from Figure 1 is z = (A, B, B, A). Here, A and B are just labels whose meaning is not important at this point. Sequences z = (z 1 , z 2 , . . . , z m ) and z = (z 1 , z 2 , . . . , z m ) of labels of leaves of a complete binary tree are said to be isomorphic if there exists an automorphism π of the (unordered version of) the tree such that the label of any leaf in z is the same as the label of the image under π of that leaf in z . Informally, z and z are isomorphic if there exists a complete binary tree whose m leaves are labeled by z, and z is the leaf labeling sequence obtained by flipping the order of some subtrees in it (i.e. by swapping some left and right subtrees). For instance, the sequence z = (A, B, B, A) from Figure 1 is isomorphic to z = (B, A, B, A) but not to z = (B, B, A, A). Aut(z 1 , z 2 , . . . , z m ) is the set of all sequences (z 1 , z 2 , . . . , z m ) that are isomorphic to (z 1 , z 2 , . . . , z m ). For instance, Aut(B,B,A,A) = {(B,B,A,A),(A,A,B,B)} We can further define an order on the sequences in Aut(z 1 , z 2 , . . . , z m ), e.g. the lexicographical order. The smallest sequence in an Aut(z 1 , z 2 , . . . , z m ) is then called the canonical representative of sequences in this set.

Evolutionary Tree Model

The evolutionary tree model considered in this paper is given by a class X of possible instances (e.g. genomes of individuals), a complete binary tree T , a conditional probability function p(x|x ) : X × X → [0, 1] and a probability function p 0 (x) : X → [0, 1]. The joint probability of the individuals in the tree is given as P

[X 1 = x 1 ∧ • • • ∧ X k = x k ] = = p 0 (x 1 ) • (k-1)/2 i=1 p(x 2i |x i ) • p(x 2i+1 |x i )
where k is the number of vertices in T , X 1 corresponds to the root, X 2i and X 2i+1 are children of X i (i.e. the probability factorizes according to a Bayesian network with structure corresponding to the tree with edges directed from root).

Intuitively, the model describes the following generative process. First, the common ancestor x 1 is sampled according to the probability distribution p 0 (.). Then two children x 2 and x 3 of this common ancestor are sampled according to the conditional probability distribution p(.|x 1 ). In the next step, the children of these nodes are again sampled according to p(.|x 2 ) and p(.|x 3 ) and so on. Since we will mostly be working only with leaves of the trees, we will denote by P * (S) the marginal probability of the instances in the leaves of the given tree, i.e.

P * (S) = P [X m = x 1 ∧ • • • ∧ X 2m-1 = x m ]
where S = (x 1 , . . . , x m ) ∈ X m is called a sample (notice that samples only involve leaves of the tree). It holds that if S = (x 1 , . . . , x m ) ∈ X m and S = (x 1 , . . . , x m ) ∈ X m , satisfy S ∈ Aut(S) then P * (S) = P * (S ), i.e. the distribution is invariant with respect to symmetries which correspond to reorderings of a given ordered tree.

Learning in the evolutionary tree model. We assume that we are given an evolutionary tree model. The positions of training and testing examples in the tree are specified by dataset configurations. A dataset configuration is a sequence A = (a 1 , a 2 , . . . , a m ) where a i ∈ {train, test}. The leaves of the tree T with an index i such that a i = train are called train-set leaves and the remaining leaves are called test-set leaves.

Example 2. For instance, the dataset configuration (train, train, train, train, test, test, test, test) corresponds to training and testing examples forming two completely separated populations. Regarding Example 1 from Introduction, this could happen if lab O put half of the original sample of bacteria to one petri dish and the other half to another petri dish, continued cultivating the bacteria in the two dishes separately and then provided samples from one dish to one lab and samples from the other dish to the other lab. On the other hand, the dataset configuration (train, test, test, train, train, train, test, test) Let H be some class of functions from X to {0, 1}. The goal of learning is to find a hypothesis h ∈ H which can do well in predicting labels of testing examples. In the realizable learning case, we also want the hypothesis h to correctly classify all training examples (such a hypothesis is called consistent hypothesis). A learning algorithm L may be seen as a function mapping training examples S T r ∈ (X × {0, 1}) * to hypotheses h ∈ H such that for all training examples

(x i , l i ) ∈ S T r it holds l i = h(x i ). If h is a hypothesis then err(S, h) = xi∈S 1(h(x i ) = l i ) is the error of the hypoth- esis h on S.
By error upper bounds in this model, we will understand inequalities of the form

P [err(S T e , L(S T r )) ≥ k] ≤ f A (k)
where S T r = S T r (S, A), S T e = S T e (S, A) and S is jointly sampled from the given evolutionary tree model. Put simply in words, we are interested in bounding the probability that a hypothesis produced by a learning algorithm L which returns a hypothesis h ∈ H consistent with the sample will disagree with the unknown concept c ∈ H, which determines labels of training and testing examples, on k or more testing examples from the joint sample.

Upper Bounds

In this section we derive upper bounds on test-set error. The next theorem gives a bound on the probability that a fixed (train, train, train, train, test, test, test, test). Using Theorem 1, we obtain the same bound1 2 for the probability of 1, 2, 3, and 4 errors on test-set examples. For instance, for 3 errors e maximizing the fraction in Theorem 1 is e = (0, 0, 0, 0, 1, 1, 1, 0) and we can check that the size of the set in the numerator is 4 and |Aut(e)| = 8 which gives the bound 1 2 . Intuitively, this dataset configuration is not very good for learning because, revisiting the evolutionary motivation, we have two subpopulations which evolved independently of each other but we have only training examples from one of the populations. It is not surprising that we In this case the bounds are 1 2 , 1 4 , 1 8 , and 1 16 for the probability of 1, 2, 3, and 4 errors, respectively.

The bound in Theorem 1 has two disadvantages for practical use. First, it is not expressed in terms of a very intuitive or an easy-to-compute graph parameter, and second, it does not have exponential form which is needed for obtaining analytic bounds on the expected error as done in Section 6. Therefore, next, we connect the bound from Theorem 1 with matchings in trees. A matching in an ordered tree T with dataset configuration A is a set of pairs of indices of leaves M = {(i 1 , j 1 ), (i 2 , j 2 ), . . . , (i n , j n )} such that: (i) for every (i, j) ∈ M , i is index of a train-set leaf and j is index of a test-set leaf, and (ii) the shortest paths connecting (i, j), (i , j ) ∈ M are disjoint if (i, j) = (i , j ). Theorem 2. Let T be a tree, let A be its dataset-configuration and let B(A, k) be the upper bound from Theorem 1. Let M be a matching of a subset of train and test leaves (M is supposed to be a set of pairs of indexes). Then B(A, k) ≤ 2 -k+|T e(A)|-|M | . Thus, matchings in trees give us simpler, albeit looser, upper bounds than the bounds from Theorem 1. Example 5. Let us have a tree with dataset configuration A = (test, test, train, test, train, test, train, train) displayed in Figure 2. Then Theorem 2 gives us the upper bound 2 1-k on probability of getting at least k errors on test-set examples and 0 errors on train-set examples for a fixed hypothesis h.

We can use the result from Theorem 2 together with the shattering lemma (see Lemma 2.1 in [Natarajan, 1991]) and union bound to obtain the upper bound (m + 1) d • 2 -k+|T e(A)|-|M | for learning from a hypothesis class with VC dimension d [Vapnik, 1995]. We will use this bound for computing bounds for expected error in Section 6.

Lower Bounds

In this section, we derive a lower bound 1 corresponding to the upper bound from Theorem 1.

Theorem 3. Let A be a dataset configuration and let k ≤ |Te(A)|. Then there exists an evolutionary tree model, a hypothesis h and a concept c such that

P [err(S T r (S, A), h) = 0 ∧ err(S T e (S, A), h) ≥ k] ≥ 1 |Aut(A)| 2 .
Example 6. Let us have a dataset configuration corresponding to train and test set coming from two completely separated populations, i.e. A = (train, train, . . . , train, test, test, . . . , test). Then the upper bound obtained using Theorem 1 is 1 2 for all k and the lower bound obtained using Theorem 3 is

1 2 2 = 1 4
, also for all k. So, in this case the ratio of the upper bound and the lower bound is constant. On the other hand, when we consider the case in which train and test set are perfectly mixed, such as in the case of the dataset configuration A = (train, test, train, test, train, test, train, test), then one may check that the ratio of the upper bound and the lower bound grows with k.

We should note here that the lower bound presented in this section is not the tightest possible. In general, one could get tighter lower bounds for a fixed dataset configuration by viewing the tree as a Bayesian network and directly optimizing the conditional probability functions p(.|.) and p 0 (.). However, first, this would lead to intractable optimization problems and, second, it would not give any insight into the problem. The lower bounds provided in this section are useful especially in the cases when |Aut(A)|, where A is a dataset configuration, is small, such as in cases when training and testing examples come from (almost) separated populations.

Bounds on Expected Error

In this section we describe a method for obtaining upper bounds on expected error. In order to compute expected error bounds, we will utilize the following theorem which considers only the special case of dataset configurations with only one test-set leaf. The bounds from the previous theorem lead to a general and straightforward method for obtaining bounds on expected errors. For every test-set leaf, we can find the largest complete binary tree embedded in the original tree T with the dataset configuration A which still contains that test-set leaf and no other test-set leaves. By summing up the bounds, using linearity of expected value, for all test-set leaves in the tree, we obtain an upper bound on the expected error when learning a consistent hypothesis from a class H with VC dimension d. Example 7. Let A be a dataset configuration of size 1024 and let A consist of interleaved blocks of 4 train-set leaves and 4 test-set leaves and let H have VC dimension d = 2. Then for every test-set leaf, we can find an embedded complete binary tree consisting of 128 leaves, in which every other leaf is a train-set leaf. Therefore we can bound the expected number of errors in this tree by E S [err(S T e (S, A), L(S T r (S, A)))]

≤ 512 • 4 + 2 • 2 • log 2 129 128 ≈ 128.2
which corresponds to error rate of approximately 25%.

Related Work

In this section, we discuss related works on learning theory for learning settings violating the iid assumption. An example is learning from examples which are not independent but only exchangeable. Many classical results on iid learning can be generalized to this setting [Catoni, 2004;Pestov, 2010;Shalizi and Kontorovitch, 2013]. Although superficially similar to our work because both rely on symmetries, there are important differences between the two settings. Most notably, the structure of symmetries is more complicated in our setting because the bounds in our work must somehow reflect the dependence on symmetries of the dataset configurations.

There are also works on inductive learning from various models of dependent training examples. In [START_REF] Brabanter | [END_REF], the correlations between training errors are explicitly specified. In [START_REF] Usunier | [END_REF], a setting was studied in which binary classifiers are trained with data which may be dependent but deterministically generated from a sample of independent examples. In time series analysis, training examples are usually assumed to satisfy some mixing conditions, e.g. α-mixing or β-mixing [START_REF] Guo | [END_REF][START_REF] Ralaivola | [END_REF], which is then used to obtain generalization guarantees. In [START_REF] Wang | [END_REF], dependency structure of examples is assumed to be known and represented by hypergraphs. In all these cases, while training examples are assumed to be dependent, the test-set examples are assumed to be sampled independently from them. In contrast, in our work the train-set and test-set examples are both assumed to be sampled from the evolutionary process and, thus, not independently.

The case when training and testing examples are not mutually independent of each other, like in the present paper, has also received attention in learning theory. In [START_REF] Aldous | David Aldous and Umesh Vazirani. A Markovian extension of Valiant's learning model[END_REF], a model was introduced in which training and testing examples are sampled from a random walk (Markov chain). Our work may be regarded as related to these works in that the evolutionary tree model is related to branching random walks. However, one difference is that we assume that the examples come only from leaves of the tree (which is sensible from the biological motivation because living individuals correspond to the leaves) whereas in the random walk model the examples are assumed to come from all stages of the walk. Another difference which stems from this is that there is no notion of dataset configurations in the random walk model. Several results from [Kontorovich, 2012] would be relevant for our work as well, but only if we put additional assumptions on the evolutionary process beyond those used in this paper.

The work presented in this paper is also related to transductive learning [Gammerman et al., 1998;[START_REF] El-Yaniv | Ran El-Yaniv and Pechyony Dmitry. Transductive rademacher complexity and its applications[END_REF] in that the number of test-set examples is finite and known in advance (whereas in inductive learning, the number of test-set examples is assumed to be infinite as there we are mostly interested in bounding the probability that a hypothesis with high expected error is learned). However, unlike in transductive learning we do not assume that the test-set examples are known by the time of learning.

Conclusions

In this paper we studied generalization bounds for learning from examples which are sampled from an evolutionary model. We provided PAC-type upper bounds based on combinatorial arguments and also upper bounds on expected errors. To complement the upper bounds we also provided a lower bound for the number of errors of a consistent hypothesis. For some dataset configurations corresponding to training and testing examples from populations which are not very mixed with each other, the lower bounds and upper bounds are relatively tight and pessimistic, confirming the intuition that guaranteeing good generalization performance should not be possible in general for such situations -without some additional assumptions on the evolutionary process. For the cases when the training and testing examples come from similar populations, the upper bounds have exponentially decaying tails which also leads to reasonable bounds for expected errors. To our best knowledge, this is the first work providing a theoretical analysis of learning where training and testing examples are evolutionary related. Extending our analysis to the agnostic case is an interesting future direction.

the matching and an error configuration e ∈ ConsAut(e) we can actually 'decode' the original configuration as well as the vector B from which the next two required properties follow: ϕ(e ) ∩ ϕ(e ) = ∅ for any e = e and |ϕ(e )| ≥ 2 k-|T e(A)|+|M | -1. The decoding can be done as follows. We iterate j from 1 to |M |. For any pair (tr j , te j ) we check if e trj = 1 or e tej = 1. If so, we know that (tr j , te j ) ∈ M . If e trj = 1, we set b j = 1 and swap (e s , e s+1 . . . , e s+r ) and (e s+r+1 , e s+r+2 . . . , e s+2r ) in e where (s, s + 1 . . . , s + r) and (s + r + 1, s + r + 2 . . . , s + 2r) are the indices of the leaves of the left and right subtree of the tree rooted in the root of the pair (tr j , te j ). Otherwise we set b j = 0 and do not change e at all. It can be shown using induction on the length of B that this procedure correctly reconstructs both B and the original e.

Since is the fraction of these configurations with no errors on training examples). Since the second factor is fixed for any given error configuration, we can maximize the first factor independently of it for the fixed error configuration e, i.e. we can find the set X , functions p 0 (.), p(.|.) and a hypothesis h and concept c maximizing the probability of sampling an error configuration isomorphic to e.

Let X = {-1, 0, 1, 2, . . . , |A|-1}. Let h(x) = 0 for every x ∈ X and let c(x) = 1 for x = -1 and c(x) = 0 otherwise. We prove using induction on depth d of the tree T that for any error configuration e there are functions p 0 (.) and p(.|.) such that: p 0 (x 0 ) = 1 for some x ∈ X , p(x 0 |.) = 0 and p(x|y) is non-zero only for x's from a set X d ⊆ X of cardinality at most 2 d-1 + 1, and e ∈Aut(e) P E (e ) ≥ 1 |Aut(e)| . (Base case, d = 1). In this case the tree consists of just the root (which is at the same time also either a train-set leaf or a test-set leaf). If e = (1) (i.e. e is the configuration ('error')) then we set p 0 (-1) = 1 and p 0 (x) = 0 for x ∈ X \ {-1}. Otherwise, if e = (0), we set p 0 (0) = 1 and p 0 (x) = 0 for x ∈ X \ {0}. Therefore we have e ∈Aut(e) P E (e ) = 1 ≥ 1 |Aut(e)| so the base case holds.

(Inductive step, depth of the tree T is d = n). We consider two cases according to symmetry of e. (i) If L(e) and R(e) are isomorphic then we can select the same p 0 (.), p (.|.) and X maximizing the probability P E (L(e)) for both the left and right subtree of the tree T . Let x 0 be the only element from X for which p 0 (x 0 ) = 1. Let us set p 0 (x 0 ) = 1 for an arbitrary x 0 ∈ X \ X . Let us set p(x 0 |x 0 ) = 1 and p(x|y) = p (x|y) for all x, y ∈ X and p 0 (x) = 0 for the rest of x ∈ X \ {x 0 }. By the induction hypothesis: P E (e) = P E (L(e)) • P E (R(e)) ≥ (where the last equality follows from Lemma 5). (ii) If L(e) and R(e) are not isomorphic, let p L 0 (.), p L (.|.), p R 0 (.), p R (.|.), X L , X R maximize P L E (L(e)) and P R E (R(e)), respectively. We can assume w.l.o.g. that there is no x ∈ X \ {-1, 0} for which both p L (x|.) = 0 and p R (x|.) = 0. Let x L 0 and x R 0 be the only elements for which p L 0 (x L 0 ) = 1 and p R 0 (x R 0 ) = 1, respectively. Let us set p 0 (x 0 ) = 1 for an arbitrary x 0 ∈ X \ (X L ∪ X R ) and p 0 (x) = 0 for the rest of x ∈ X \ {x 0 }. Let us set p(x L 0 |x 0 ) = 0.5, p(x R 0 |x 0 ) = 0.5 and p(x|y) = p L (x|y) for all x, y ∈ X L , and p(x|y) = p R (x|y) for all x, y ∈ X R . By the induction hypothesis, we get Proof of Theorem 4. We can 'pretend' that the dataset configuration is (test, train, test, train, . . . , test, train) by ignoring (|A| -1)/2 train-set leaves (this never decreases the probability of selecting a 'bad' hypothesis from H which produces an error on the test-set leaf). Then we can use the bound on expected error from Lemma 7. It follows from the symmetry of the problem that we can obtain the bound on expected error from the statement of this theorem.

Figure 1 :

 1 Figure 1: A tree with dataset configuration (A, B, B, A).

  corresponds to training and testing examples being more mixed. The set of indices of train-set leaves is denoted by Tr(A) and the set of indices of test-set leaves is denoted by Te(A). If S is a joint sample of leaves of a given tree then S T r (S, A) = (S) Tr(A) and S T e (S, A) = (S) Te(A) are the samples of training and testing examples, respectively. In a sample, we not only get feature-vectors x (e.g. genomes), but also the corresponding labels l ∈ {0, 1} given by an unknown concept. Example 3. If we substitute A := train, B := test in the tree in Figure 1 then its dataset configuration is (train, test, test, train). It holds Tr(A) = (1, 4), Te(A) = (2, 3). If S = (w, x, y, z) then S T r (S, A) = (w, z) and S T e (S, A) = (x, y) are the training and testing samples, respectively.

  hypothesis h consistent with training examples will result in k or more errors on the test-set examples. Theorem 1. Let us have an evolutionary tree model from which samples S are sampled. Let A = (a 1 , a 2 , . . . , a m ) be a dataset configuration, h be a fixed hypothesis and c be an unknown concept. Then the probability P [err(S T r (S, A), h) = 0 ∧ err(S T e (S, A), h) ≥ k] is bounded by max e=(e1,...,em)∈C k |{e ∈ Aut(e) s.t. i∈T r(A) e i = 0}| |Aut(e)| where C k denotes the set of all sequences e ∈ {0, 1} m with i e i ≥ k. Not surprisingly, error bounds depend on given dataset configurations. The next example shows a dataset configuration for which one cannot really guarantee good generalization. Example 4. Let us have a complete binary tree with dataset configuration

  Theorem 4. Let A = (test, train, train, . . . , train, train) be a dataset configuration and H be a hypothesis class with VC dimension d. Let us suppose that the learning algorithm L selects a hypothesis from H which is consistent with training examples. Then for the test-set error we have the inequality E S [err(S T e (S, A), L(S T r (S, A)))] ≤ 4 + 2d log (|A| + 1) |A|

  |ϕ(e) ∪ {e}| ≥ 2 k-|T e(A)|+|M | , ϕ(e) ⊆ Aut(e) \ ConsAut(e) for any e ∈ C k and ϕ(e ) ∩ ϕ(e ) = ∅ for any e = e , we can conclude that max e ∈C k e(A)|+|M | . We state the next simple lemma without proof. Lemma 5. For an error (or dataset) configuration e, if L(e) is isomorphic to R(e) then |Aut(e)| = |Aut(L(e))| • |Aut(R(e))|, else |Aut(e)| = 2 • |Aut(L(e))| • |Aut(R(e))|. Theorem 3 will follow directly from the next lemma. Lemma 6. If A is a dataset configuration then there exists an evolutionary model, a hypothesis h and a concept c such that P [err(S T r (S, A), h) = 0 ∧ err(S T e (S, A), h) ≥ k] For any fixed error configuration e, we have P [err(S T r (S, A), h) = 0 ∧ err(S T e (S, A), h) ≥ k] ≥ e ∈Aut(e) P E (e ) • |ConsAut(e)| |Aut(e)| (because the factor e ∈Aut(e) P E (e ) is the probability of obtaining an error configuration isomorphic to e and the other factor |ConsAut(e)| |Aut(e)|

P

  E (e) ≥ 2 • p(x L 0 |x 0 ) • p(x R 0 |x 0 ) • P L E (L(e)) • P R E (R(e)) last equality follows from Lemma 5) which finishes the proof. Lemma 7. Let A = (test, train, test, train, . . . , test, train) be a dataset configuration and H, d and L be as in Theorem 4. Then for the expected test-set error we have the inequality E S [err(S T e (S, A), L(S T r (S, A)))] ≤ 2 + d log 2 (|A| + 1). Proof. We have E S [err(S T e (S, A), L(S T r (S, A)))] = = ∞ i=1 P [err(S T e (S, A), L(S T r (S, A))) ≥ i] 1) d • 2 -i ≤u + 1 + (|A| + 1) d • 2 -uNow setting u := log 2 (|A| + 1) d (since the above inequalities hold for any real number u ≥ 0), we get E S [err(S T e (S, A), L(S T r (S, A)))] ≤ 2 + d log 2 (|A| + 1).

  Figure2: A tree with dataset configuration(test, test, train, test, train, test, train, train). A matching of cardinality 3 is depicted by the thick edges where different colors correspond to different matched pairs of train-set and test-set leaves.cannot give very good guarantees for generalization when learning only from one of the sub-populations. A dataset configuration, better suited for learning and leading to much better bounds is(train, test, train, test, train, test, train, test).

	?	?	T	?	T	?	T	T

In Appendix we actually prove a lemma with a stronger lower bound than the one in Theorem 3 but less interpretable from which Theorem 3 follows.

Acknowledgments

This work has been supported by ERC Starting Grant 240186 MiGraNT: Mining Graphs and Networks, a Theory-based approach.

A Proofs of Theorems

We will need a little additional notation.

Let S = (x 1 , . . . , x m ) be a joint sample of leaves of the given tree. Let c ∈ H be an unknown concept according to which training and testing examples are labeled, and h ∈ H be a hypothesis. Then we let e(S) = (1(c(x 1 ) = h(x 1 )), . . . , 1(c(x m ) = h(x m ))) denote a sequence which contains ones in the places of examples for which h and c disagree. We call e(y) error configuration of y.

which is the set of all error configurations isomorphic to e with errors only on the test-set leaves. Let ISO be the set of representatives for classes of isomorphic error configurations (i.e. for for every e ∈ {0, 1} m there is e ∈ ISO such that e ∈ Aut(e )). We are interested in bounding the probability of the event E T e ≥ k ∧ E T r = 0 for which we have

which is what we needed to show.

Proof of Theorem 2. First, we define an auxiliary concept called root of pair. Let (tr, te) ∈ M and let tr = v 1 , v 2 , . . . , v r+1 , . . . , v 2r+1 = te be the unique path connecting tr and te then v r+1 is called root of the pair (tr, te).

Without loss of generality, we assume that A is such that for any pair of train-set and test-set leaves (tr, te) ∈ M , if v r is the root of the pair (tr, te), l is the index of the leftmost leaf of L(T, v r ) (which is the left subtree of the subtree of T rooted in v r ) and r is the index of the left-most leaf of R(T, v r ) then either tr = l, te = r or tr = r, te = l. It is not difficult to see that for any dataset-configuration A there is an isomorphic dataset-configuration satisfying this property.

Let e ∈ C k be an error configuration. We will construct a mapping ϕ : ConsAut(e) → 2 Aut(e)\ConsAut(e) such that for any two different e , e it will hold ϕ(e ) ∩ ϕ(e ) = ∅ and |ϕ(e

First, we order the pairs of the matching M = ((tr 1 , te 1 ), (tr 2 , te 2 ), . . . , (tr |M | , te |M | )) as follows: if the unique path connecting te i and the root of the tree intersects the path connecting tr j and te j then j ≤ i. Now, let e = (e 1 , . . . , e m ) ∈ ConsAut(e) ∩ C k be an error configuration with exactly k errors and let Err e = {i ∈ N |c i = 1} be the set of indexes of the errors in the error configuration e. Let M = ((tr 1 , te 1 ), . . . , (tr k , te k )) be a subsequence of M consisting of those pairs (tr i , te i ) ∈ M where te i ∈ Err e . Note that k ≥ k-|T e(A)|+|M |. Next, let B = {0, 1} k \(0, 0, . . . , 0). For every b = (b 1 , . . . , b k ) ∈ B we construct a new error configuration isomorphic to e as follows. We iterate j down from k to 1. If b j is 0, we do not do anything. If b j is 1 then we find the root v r of the pair (tr j , te j ), we take e[L(T, v r )] = (e s , e s+1 . . . , e s+r ) and e[R(T, v r )] = (e s+r+1 , e s+r+2 . . . , e s+2r ) and swap them in e. where (s, s + 1 . . . , s + r) and (s + r + 1, s + r + 2 . . . , s + 2r) are the indices of the leaves of the left and right subtree rooted in the children of v r . Now we need to show that the sets of error configurations produced by the above procedure have the desired properties. First, it is obvious that any error configuration produced in this way must be contained in Aut(e). Next, notice that there will always be at least one e i = 1 with i ∈ T r T (A) (at least the one produced by the last swap) which implies that no error configuration e produced in this way can be in ConsAut(e). So ϕ maps elements from ConsAut(e) to subsets of Aut(e) \ ConsAut(e) as required. Now, given


Clément Iphar
email: clement.iphar@mines-paristech.fr

Aldo Napoli
email: aldo.napoli@mines-paristech.fr

Cyril Ray
email: cyril.ray@ecole-navale.fr

On the interest of data mining for an integrity assessment of AIS messages

Keywords: Automatic Identification System, data falsification, integrity assessment

Put in place by the International Maritime

Organization, the Automatic Identification System is a worldwide maritime electronic system that sends radio broadcasted messages at a high rate between the stations, either on board the vessels or on shores. However, some misuses of the system such as identity theft, localization spoofing or disappearances have been demonstrated. The high rate of transmission implies a considerable amount of data to process in order to point out those irregularities. This paper proposes a method based on data mining and clustering methods combined to an integrity assessment of AIS messages for anomaly detection, with a proposition of software architecture for a data processing done both on-the-fly and with archived data. The computation of confidence coefficients and the use of data mining techniques will lead to behaviour characterization with the purpose of enhance the maritime situational awareness.

I. INTRODUCTION

The maritime traffic is globally dense, and as the traffic increases some regions are facing a particularly high density of traffic, particularly in Europe, South-Eastern Asia or specific locations such as canals or straits. For instance, Malacca strait and the Suez canal have respectively a yearly traffic of circa 50,000 and 20,000 vessels. Moreover, this traffic sometimes takes place in quite hazardous places such as Malacca strait [START_REF] Afrida | Malacca Strait rampant with pirates[END_REF] or the Suez canal [START_REF]Armed Conflict Location and Events Dataset, "Real-time Analysis of African Political Violence[END_REF].

For the enhancement of the security and safety of navigation some systems have been put in place. Amongst those systems (radar, Long Range Identification and Tracking for instance), the Automatic Identification System uses electronic devices to send and receive messages to or from other vessels or some coastal stations within its radio horizon range. However, this system is not fully reliable and some errors and data falsification have been demonstrated. Spatial data analysis [START_REF] Le Blanc | A multiple discriminant analysis of vessels accidents[END_REF], [START_REF] Marven | Exploratory Spatial Data Analysis to Support Maritime Search and Rescue Planning[END_REF] and data mining techniques [START_REF] Torun | Using spatial data mining techniques to reveal vulnerability of people and places due to oil transportation and accidents: a case study of istanbul strait[END_REF] were used in some studies about maritime accidents, but without covering the fields of data falsification discovery. On the one hand, behavioural analysis of moving objects is treated by [START_REF] Roy | Anomaly detection in the maritime domain[END_REF] and [START_REF] Roy | Exploitation of Maritime Domain Ontologies for Anomaly Detection and Threat Analysis[END_REF] and on the other hand, data mining techniques [START_REF] Chen | Clustering moving objects in spatial networks[END_REF] for trajectories analysis are displayed in [START_REF] Giannotto | Trajectory pattern mining[END_REF] and [START_REF] Idiri | Méthodologie d'extraction de connaissances spatio-temporelles par fouille de données pour l'analyse de comportements à risques : application à la surveillance maritime[END_REF]. An overview of the clustering methods [START_REF] Jain | Data Clustering: A Review[END_REF] presents the possibilities associated with the use of such methods in our case of study. The use of data mining for the enhancement of maritime situational awareness has been presented in [START_REF] Fernandez Arguedas | Spatio-temporal Data Mining for Maritime Situational Awareness[END_REF], for the depiction of the current navigation state and forecasted positioning data.

In our study which is focused on falsification discovery, a methodology involving clustering and data mining methods for integrity assessment is proposed, that would lead to the determination of confidence coefficient for the message and the sender, and given the high amount of data available through this system, clustering methods for anomaly detection and behavioural characterization are proposed.

In this article, section II presents the Automatic Identification System, the volumetry of data and its weaknesses, then section III presents the structure and characteristics of data, section IV the proposed method for data processing, then section V presents the proposed architecture of the software.

II. AIS FALSIFICATIONS

A. The principles of the system

The AIS was put in place in 2000 by the International Maritime Organization and its characteristics and deployment schedule are defined in the Safety of Live at Sea convention [START_REF]International convention for the safety of life at sea[END_REF]. This convention, initiated two years after the sinking of the RMS Titanic in 1912, aims at defining the minimal requirements to which every vessel belonging to a signatory country should comply with. The convention deals with a large scope of subjects which range from the construction of vessels to the way radio-communications shall be done.

One of the themes of the convention is the safety and security of maritime navigation, and it is in this scope that the system was created, as it provides a real-time spatiotemporal positioning of a vessel to every vessels and shore station located in its radio range of action. Not all the vessels from the signatory countries are concerned with the AIS regulation, as the convention states that "All ships of 300 gross tonnage and upwards engaged on international voyages and cargo ships of 500 gross tonnage and upwards not engaged on international voyages and passenger ships irrespective of size shall be fitted with an automatic identification system" [START_REF]International convention for the safety of life at sea[END_REF].

The system uses transponders to send messages through Very High Frequency marine bandwidth on two worldwide dedicated frequencies: 161.975MHz and 162.025MHz. The transponder is linked with a Global Navigation Satellite System (GNSS) which computed its location as well as external sensors (electronic compass for instance) in order to fill in several data fields within the messages. The AIS can also transmit to satellite the messages (AIS-SAT), that makes possible to keep a track of a vessel even beyond the radio horizon. One kind of message (number 27) is shorter than all other messages and is especially dedicated to satellite reception.

The system, albeit being mainly initially designed for security purposes, the AIS has alternative uses such as the prevention of boarding (alarm triggering when a small closest point of approach is computed), investigation in case of accident, control of fishing fleets, cargo fleets, global traffic, traffic in specific hazardous areas, maritime safety (for a state), aid to navigation or search and rescue operations. Indeed, some examples of the use of AIS for alternative purposes can be found in studies in several subjects such as accident investigation [START_REF] Wang | A spatial-temporal forensic analysis for inland-water ship collision using AIS data[END_REF], the detection of near miss collision between vessels [START_REF] Zhang | A method for detecting possible near miss ship collisions from AIS data[END_REF], the behaviour understanding in a waterway through traffic monitoring [START_REF] Xiao | Comparison study on AIS data of ship traffic behavior[END_REF] or the mapping of the fishing effort using AIS data [START_REF] Natale | Mapping Fishing Effort through AIS Data[END_REF].

B. Data Volumetry

All equipped vessels must transmit localization messages at a given rate, which ranges from 2 seconds to 12 seconds according to the speed of the vessel, the higher the speed, the higher the rate of transmission. Localization messages are sent every 3 minutes when the vessel is at anchor. As stated before, all messages are not localization messages, however they account for circa 90% of the total message number. This high rate of transmission implies a high number of messages, for instance, in the waters of the European Union, there are circa 10,000 unique vessels per day and about 100,000,000 messages per year, and as stated by [START_REF]Space station keeps watch on world's sea traffic[END_REF], at the global level, "on a good day, approximately 400,000 ship position reports are received from more than 22,000 different ship identification numbers (Maritime Mobile Service Identity, or MMSI). In a summary made in Oct. 2011, the total number of position reports received exceeded 110 million messages from more than 82,000 different MMSI numbers". The total amount of data that can then be accumulated through the reception and storage of AIS data tends the treatment of those pieces of information towards big data issues.

C. A system with weaknesses

Three major cases of bad data quality can be distinguished: the errors (when false data in non-deliberately broadcasted), the falsifications (when false data is deliberately broadcasted) and the spoofing (when data is created or modified and broadcasted by an outsider) [START_REF] Ray | DeAIS project: Detection of AIS Spoofing and Resulting Risks[END_REF]. Data contained in AIS messages can be erroneous, falsified or spoofed for several reasons: there is no strong verification of the transmission, the transmission is done using a non-secured channel, some pieces of information might not be well known by the crew or the crew may want to hide some data from other people's knowledge. Those operations modify and handicap the understanding of the maritime traffic.

The errors, by nature unintentional, can be caused by transponder deficiency, a wrong input of manual data, an input of manual data of poor quality, erroneous pieces of information that come from external sensors, and can have an impact on the name of the vessel, its physical characteristics, the position or the destination for instance. Those pieces of information can then be false, incomplete, impossible according to the norm or impossible according to the physics (for instance, a latitude field value shall be inferior to 90°). According to [START_REF] Harati-Mokhtari | Automatic Identification System (AIS): Data Reliability and Human Error Implications[END_REF], circa 50% of the messages contain erroneous data.

A falsification is the fact to voluntarily degrade a message by the modification of a genuine value by a false value, or by stopping the broadcast of messages, made in order to mislead the outer world. Identity theft [START_REF]Iran, Tanzania and falsifying AIS signals to trade with Syria[END_REF], the disappearances [START_REF] Windward | AIS data on the high seas: an analysis of the magnitude and implications of growing data manipulation at sea[END_REF], the broadcast of false GNSS coordinates or the statement of a wrong activity [START_REF] Katsilieris | Detection of malicious AIS position spoofing by exploiting radar information[END_REF] are types of falsification. According to [START_REF] Harati-Mokhtari | Automatic Identification System (AIS): Data Reliability and Human Error Implications[END_REF], circa 1% of the vessels broadcast falsified data.

The spoofing of messages is done by an external actor by the creation ex nihilo of false messages and their broadcast on the AIS frequencies [START_REF] Balduzzi | A security evaluation of AIS automated identification system[END_REF]. Those spoofing activities are done in order to mislead both the outer world and the crews at sea, by the creation of ghost vessels, of false closest point of approach trigger, a false emergency message or even a false cape (in the case of a spoofed vessel).

III. DATA

A. Data structure

Due to the variety of communications, there are 27 different kinds of messages. Position report messages, information messages and check messages are the three main groups of messages [START_REF] Tunaley | Utility of Various AIS Messages for Maritime Awareness[END_REF]. All 27 kinds of messages are standardized by the International Telecommunications Union [START_REF]Technical characteristics for an automatic identification system using time division multiple access in the VHF maritime mobile frequency band". ITU[END_REF] and have its particular outline with data fields, each one being allocated a certain number of bits. The information within each field can take several forms: boolean, text, number representing a physical quantity, number representing a choice in a given list. The content of the messages do vary largely from one message to another: in a position report message the data fields are the speed, the position and the cape, amongst others, while an aid to navigation message will display the type of beacon, its name or the location of a hazard. Each message has then different data fields, accordingly with its type, each data field having a given location in the message and a given number of bits allocated. The meaning of the values of the data fields within the messages are also defined in an unambiguous way in the technical specifications [START_REF]Technical characteristics for an automatic identification system using time division multiple access in the VHF maritime mobile frequency band". ITU[END_REF].

B. The unique identification of data fields

In order to get an all-encompassing assessment of the integrity of AIS messages, all the available information from all available messages shall be taken into consideration. However, as a lot of messages display localization information, there is a quite high redundancy of some data fields. This profusion of barely identical fields in different messages leads to the need of an ad-hoc field nomenclature so that one field in a given message cannot be confused with another one in another message. The nomenclature we propose matches each field of each message to a unique three-character string of type "XXY", where the XX part stands for the number of the message from 01 to 27 and the Y part stands for a letter ranging from A to S (at most, as no message has more than 19 fields), the position of which in the alphabetical order indicating the position of the field in the given message. So in this nomenclature, the field "02F" corresponds to the sixth field (as F is the sixth letter in the alphabetical order) of the message number 2, i.e. the "Speed Over Ground" field.

C. The diverse data types within the messages

The data within the messages can take several forms, and the message number 5 is a good witness of the diversity of data types. The following table displays the layout of the message number 5, with the unique nomenclature identifier, the parameter in the field and the datum type. Discrimination can be made between six types of data: numeric representing a physical quantity, numeric representing an identifier, numeric representing a choice in a given list, date, textual and binary, as shown in Figure 1.

For the numeric values, the physical quantity data type is a piece of information that has a sense in the physical world (such as latitude, longitude, speed or for message 5 the maximum present static draught). In general, as the physical quantities are continuous quantities, a given precision is associated with it, for instance here 0.1m for the 05L field. The identifier data type is a piece of information linked with a field number standing for a unique identification number, such as MMSI number of IMO number. The choice in a given list data type stands for the pieces of information of which the meaning has to be deduced from a given list of values are stated in the technical specifications [START_REF]Technical characteristics for an automatic identification system using time division multiple access in the VHF maritime mobile frequency band". ITU[END_REF]. For instance, the 05I field stands for the type of electronic position fixing device, that can range from 0 to 15. If the value is 1 then "GPS" is used, if it is 2 then "GLONASS" is used, and so on until the last possible value.

For the non-numeric values, a textual data type stands for the pieces of information in which the bits are converted by groups of 6 into ASCII characters, used in the case of "Name" or "Destination" fields. Date data type is a rare data type in AIS messages standing for a date representation and binary data type is related data types where a statement is declared as true or false. Alternatively, it can be used to state if the value of the physical quantity representing the field is superior or inferior to a given threshold, or a choice in a list of exactly two choices.

IV. METHOD FOR DATA PROCESSING

A. Selection of cases suitable for study

In the data comparison field, a set of messages must be selected in order to compare data within a scope where comparison makes sense. Four different relevant ways for data processing have been discriminated by our study: MMSIbased, station-based, location-based and route-based, with the hypothesis that the messages received from the same MMSI, by the same station, from the same route or location will tend to look alike.

The MMSI-based study takes only into consideration the messages from a single emitting station, that can be a vessel, an aircraft, a coastal station or even a buoy as all those devices have an assigned MMSI number. The station-based study concentrates on the messages received by a single station onshore, and albeit there is a theoretical coverage of circa 40 nautical miles, it is possible that some messages from a way longer position are received because of the favourable transmission conditions or that some messages sent from a shorter location are not received because of masks. The location-based study takes into consideration the messages sent from a given spatial extent, for instance a circle around a point of interest, a fishing area or a particularly hazardous zone. The route-based study selects only the messages that are sent by the vessels which follow a given route, for instance sailing between two given ports or going through a given corridor (a Traffic Separation Scheme for instance).

B. Integrity assessment

As it was stated in [START_REF] Iphar | Detection of false AIS messages for the improvement of maritime situational awareness[END_REF], integrity is the most important of all data quality dimensions when it comes to the veracity assessment of AIS messages. The method we propose is based on the integrity of AIS data at several levels. The first level consists in the assessment of each single data field, taken apart from the others, which consists of checking whether the field value is consistent with the possible field values given by the technical specifications [START_REF]Technical characteristics for an automatic identification system using time division multiple access in the VHF maritime mobile frequency band". ITU[END_REF]. The second level consists of assessing the integrity of data within a single message, thus apart from all other messages, and check if there is any discording data between the fields. The third level is an assessment between messages of the same type (for field value evolution for instance) and the fourth level is an assessment between the fields values of different kind of messages.

In our method, the first and second levels are within a message and can be done on-the-fly whereas the third and fourth levels are between messages, and require database queries. We established a list of more than six hundred items, with each item corresponding to a single data integrity check. Besides, a nomenclature for unique identification of assessment items has been performed. Figure 2 presents a sample of those items.

Figure 2: Integrity assessment items

According to the message we have or to the situation we want to assess, a subset of those items is selected and the data integrity assessment takes place with the selected items and the selected messages. A confidence coefficient is then computed taking into consideration a weight factor (how important is the item in the assessment) and an assessment factor (how integer are the pieces of information assessed in this particular item).

The experimental validation of this method is being done in ongoing work and uses data we have been collecting using antennas located in Brest harbour. The use of some additional data will be used in future works.

C. Clustering methods for behaviour charecterization

As the subset of items that can be used for an assessment depends on the type of assessment, it is then possible to compute several kinds of coefficients according to the purpose of the assessment. Some items are more useful to highlight disappearances whereas some other items are more likely to highlight identity fraud.

Once all different kind of assessment selected, and each kind being allocated a subset of items, a vector of coefficients can then be computed, and each vector compared then to archived data for pattern matching.

In addition, for the fields in the messages, a measure of the rareness of the fields can lead to the use of statistical methods. For a given set of values, typically the subset of messages extracted by one of the methods proposed in section IV.A, a statistical study on how do pieces of information tend to appear more than other. Of course, such an assessment is tightly linked to the type of data, as data can be of very diverse types, as shown in section III.C.

A strict and simple statistical distribution can be used in the case of binary and numeric representing a choice in a given list cases, whilst a buffer is used for numeric data representing a physical value and date (which means if we concentrate on value x and take a buffer y, all values between x-y and x+y will be taken into consideration). A textual distance such as Levensthein distance or a translation table can help in the case of textual fields, particularly for the destination field case, as the names are often written in various languages and sometimes with spelling mistakes. This process leads to a clustering of data under groups that represent the same port, and a statistical method can then be used in order to assess the frequency of each group.

In addition, similarity and dissimilarity measures are able to compare vectors of data extracted from AIS messages. Clustering methods with data of quite high dimensionality (in general about 15 data fields, where each data field worth one dimension) can then be applied. Moreover, conditional probabilities can be extracted from the set of messages, by using subsets of messages where a certain number of conditions are gathered (for instance, where a combination of field values occurs). This will be the purpose of future works.

V. SOFTWARE ARCHITECTURE

A. Integration of external data

If AIS was an isolated system, the sole study of its data would be enough for an integrity assessment. However, the AIS is set on vessels and of course vessels have diverse physical characteristics, and themselves evolve in diverse environments with particular features. And as the environment evolves, it is possible to enhance the understanding of the behaviour of vessels with external sources of information. Indeed, on the one hand, data can look anomalous on the basis of the sole AIS data and turned out as normal with the study of external data, and on the other hand data can look normal with the sole AIS data and turned out as anomalous with the assistance of external data. Moreover, some cases of possible falsifications such as disappearances must be investigated as the fact to receive or not to receive a message is more complex than the presence or absence of the given vessel within the line of sight. Anomaly detection in such case [START_REF] Mazzarella | AIS Reception Characterisation for AIS on/off Anomaly Detection[END_REF] requires extra processing. Indeed, on the one a vessel can sail beyond the line of sight and yet the messages sent from it are received, on the other hand a vessel can sail within the line of sight distance and yet the messages sent by it are not received for several reasons including masks, message collision or system failure.

An approach on multiple frames is enabled by the diversity of possible databases, and we selected three main families of databases: environmental, vessel-based and navigation-based. However, there is no exhaustive list of possible integrable databases as databases appear, evolve and go out of date through time. Their purpose is to bring expert data to enlighten specific situations.

Environmental data would embrace all kind of databases with a relation with the environment in which the vessel evolves. Meteorological databases with information such as pressure, temperature, wind force, rainfalls and wave height can be used for behaviour understanding. Tidal information and bathymetric maps can also be useful for the understanding of coastal navigation.

Vessel-oriented databases would gather insurance databases or the different fleet registers available, from the freely online available European Union Fishing Fleet Register to charged Lloyd's Register.

Navigation-oriented databases would embrace all kind of information linked to navigation and vessels' routes. Some other sensors (radar for instance) can be included, as well as regular origin and destination ports for each vessel.

B. The proposed architecture

A synoptic diagram of the proposed architecture can be found in the Figure 3 below. Various sources can provide the signal, the parser gives message parameters, the data processing of the signal provides some signal parameters and two different steps of data processing. All this architecture is built around the database in order to fill it and use it for knowledge discovery. It is very important in our study that the parser we chose and modify at our convenience does not discard any message, as we want to process every single frame going through the reception system.

The data processing box number two corresponds to a signal processing for the computation of four characteristics figures of a transponder [START_REF] Alincourt | Methodology for AIS Signature Identification through Magnitude and Temporal Characterization[END_REF], which are the rise time (power from 10% to 90%), the time before modulation (from 50% of power to first bit of the training sequence of the message), the fall time (power from 90% to 10%) and the time after modulation (from the last bit of the message to 50% of power). Some patterns are recognizable and it is then possible to distinguish the diverse emitter transponders with those characteristics. Although it is not possible to determine the identity of the vessel of origin only with those characteristics, it is however possible to determine whether or not two or more messages are sent by the same vessel.

The data processing box number one is in charge of on-thefly analysis of the first and second levels of data assessment, in order to have as output computed coefficients to store in the database. Similarly, the data processing box number three is in charge of the analysis of the third and fourth levels of data assessment, in order to have as output computed coefficients to be stored in the database. This second part of the study, unlike the first, needs some requests to the database to be done.

In the database itself, each new entry will lead to the creation of a new item with a unique identifier, the time of reception, the raw frame, all the message field values and the various computed coefficient obtained through assessments (the four orders and the signal parameters) as attributes.

The data processing box number four is in charge of integrity assessments between AIS data and external data, i.e. with data coming from the external providers. Of course, the types of processing will vary accordingly with the type of external information available, and no strict process is proposed. A list of assessment items, similar to the ones describes in section IV.B for inner information integrity assessment can be created for each new database when its specifications are known (such as its fields, their source, their precision and reliability). Some updates to the external databases will, in some cases, be necessary, as to ensure to have data that are not outdated to lead to a reliable data quality assessment. This implies the fact that databases must have a time stamp, some information on the provider and all kind of metadata that could be useful for the processing of data.

C. Use case

In the scope of the discovery of anomalous data, it is important that the selected use cases are in relationship with the weaknesses of the system as discussed in section II.C. Taking into consideration this analysis, we selected in a first draft five scenarios for which peculiar messages types can and will be used. Those scenarios are identity theft (messages 5, 24 and spatiotemporal messages), use of a fictitious identity (message 5, 24 and spatiotemporal messages), frequency hopping (message 22), disappearances (spatiotemporal messages) and GNSS spoofing (spatiotemporal messages and messages for which an answer is expected, for instance the pair 10/11). The messages that are considered as spatiotemporal are the ones in which the latitude and longitude are given, i.e. messages number 1, 2, 3, 9, 18, 19 and 27.

As for the use case of disappearances, theoretical coverage of terrestrial receivers have been computed, the practical coverage have been extracted from received data and an official vessel fleet register have been downloaded for the first external information implementations.

D. Implementation details

This article focuses on methodology and does not provide implementation details, which are ongoing research. The AIS parser, already in operation, is in Java language and is adapted from AISMESSAGE parser available online. Also in operation is the signal data processing. In addition, the database architecture has been built. It is based on a relational database using a PostgreSQL / PostGIS architecture, with one table for each kind of message, tables for the storage of analysis results and additional tables receiving data such as, for instance, weather, fleet registers or signal information. The analysis process will make use of this database in continuous mode using Python language programs for the extraction of information linked to the processes presented in this paper.

VI. CONCLUSION

This article proposes a methodology for anomaly assessment and falsification discovery in AIS messages, using data mining techniques and an integrity-based assessment, enhanced by external databases. The purpose is to assign to each message and to each single user of the system a confidence coefficient, leading to behavioural characterization of trajectories that are spatial, temporal and semantic. An architecture for the implementation of this method is proposed, that will be able to lead to an integrity-based assessment, itself leading to an alert triggering system in decision-support cases, for the eventual enhancement of the maritime safety.

Figure 1 :

 1 Figure 1: The data fields of message 5 Dark blue: num. repr. an identifier ; Red: num. repr. a physical quantity ; Green: num. repr. a choice in a given list ; violet: textual ; Orange: date ; Sky Blue: binary

Figure 3 :

 3 Figure 3: Proposed Architecture

ACKNOWLEDGMENT

Research presented in this paper is supported by The French National Research Agency (ANR) and co-funded by DGA (French Armaments Procurement Agency) under reference ANR-14-CE28-0028. The project is also labelled by French clusters Pôle Mer Bretagne Atlantique and Pôle Mer Méditerranée.