Stefan Haar
email: stefan.haar@inria.fr

Salim Perchy
email: yamil-salim.perchy@inria.fr

Frank Valencia
email: frank.valencia@polytechnique.fr

D-SPACES: Implementing Declarative Semantics for Spatially Structured Information

Keywords: semantic interpretation, social networks, epistemic logic, utterance

We introduce in this paper D-SPACES, an implementation of constraint systems with space and extrusion operators. Constraint systems are algebraic models that allow for a semantic language-like representation of information in systems where the concept of space is a primary structural feature. We give this information mainly an epistemic interpretation and consider various agents as entities acting upon it. D-SPACES is coded as a c++11 library providing implementations for constraint systems, space functions and extrusion functions. The interfaces to access each implementation are minimal and thoroughly documented. D-SPACES also provides propertychecking methods as well as an implementation of a specific type of constraint systems (a boolean algebra). This last implementation serves as an entry point for quick access and proof of concept when using these models. Furthermore, we offer an illustrative example in the form of a small social network where users post their beliefs and utter their opinions.

I. INTRODUCTION

Systems where information is created and manipulated across a spatial structure are now commonplace. Applications like social networks, forums, or any other that organizes its information in a defined hierarchy are among these systems. The nature of this information can be reviews, opinions, news, etc., whereas the information belongs to a certain entity, e.g. users, agents, applications. This relation of ownership and its alteration can be conceptualized as space and extrusion respectively [1], [START_REF] Perchy | Opinions and beliefs as constraint system operators[END_REF]. We aim to achieve a clear understanding of the concept of space and extrusion that will enable us to study the meaning of information in these systems.

In this work we focus in epistemic systems where we have agents believing information [3] and uttering opinions and lies [START_REF] Van Ditmarsch | On the logic of lying[END_REF]. In order to attain a semantical meaning of these epistemic behaviors we use declarative models, specifically constraint systems; algebraic structures that operate on elements called constraints [5] (the information). Constraints can be viewed as assertions representing partial information (e.g. t < 50 would stand for a certain temperature being lower than 50 degrees), this makes constraint systems ideal to model and operate over scattered data.

The characterization of space as the operator [•] over constraints was developed in [1]. This made possible assertions like [c] i "information c belongs to agent i's space" or [[c] j ] i "c holds in a space associated to agent j inside agent i's space". Alternatively, we can epistemically interpret these assertions as "agent i believes c" and "agent i believes agent j believes c" respectively. Movement of information across spaces was introduced by means of the constraint operator ↑ called extrusion [START_REF] Guzman | Belief, knowledge, lies and other utterances in an algebra for space and extrusion[END_REF]. One can now conceive statements like [↑ i [c] j ] i "agent i extrudes the information c to agent j" or epistemically as "agent i extrudes that agent j believes c".

The purpose of this article is to present D-SPACES, an implementation of constraint systems with space and extrusion operators. Our intention is to use it to provide a semantic language for describing systems where information is structured in a hierarchy of spaces. D-SPACES was conceived as a c++11 library, using the boost graph library1 (BGL). It is thoroughly documented using HeaderDoc2 and can be directly used in the OS X (XCode) and Linux (GCC+Make) environments 3 . Usage on Windows depends upon compilation of BGL, nonetheless the implementation is sufficiently cross-platform.

The paper is divided in four sections. Section I provides an introduction with basic details of the tool. Section II defines the constraints systems and describes D-SPACES; it explains the general design, the class interfaces, and Moreover, we provide some remarks on the complexity issues of the implementation of some constraint system operations. In Section III we present powerset boolean algebras as a specific instantiation of our model and we use it to give semantics to a belief language describing a small social networks based on tags. Finally, Section IV offers some concluding remarks and future endeavors regarding D-SPACES.

II. IMPLEMENTING SPACE AND EXTRUSION IN CONSTRAINT SYSTEMS

We begin by describing the class hierarchy of D-SPACES (Fig. 1). There are three modules implementing each constraint system, they are named cs, scs and scs-e. A fourth module, named ba, implements powerset boolean algebras using the functionality of all the others.

Each module parametrizes the cs elements (the information) using a template T. The type used must be comparable in the standard way (i.e. operator<) as there is reliance on the automatic sorting of the container std::set. Currently, there are instantiations of types int, char, std::string and containers std::vector and std::set of these same types. We continue with the description of the cs module.

Flat Constraint Systems:

We first formalize the concept of constraint system. A basic background in domain theory is presupposed [START_REF] Davey | Introduction to lattices and order[END_REF], [START_REF] Abramsky | Domain theory[END_REF]. Definition II.2 (cs). A constraint system [5] is a complete lattice, that is, a lattice where the meet and join operations are defined for every subset of Con.

Intuitively, a cs is an information structure where its elements are the set Con (called constraints). A cs has a bottom element true (denoted as the global meet ⊥ in lattice literature) and a top element false (denoted as ). Furthermore, the reverse ordering relation is interpreted in cs as entailment (i.e. d c means d entails c). Notice this interpretation suggests the greater an element is on the ordering relation , the more information the element denotes. In the example of Fig. 2, true is the element 0 and false is the element 5, needlessly to say, false entails all the elements of the cs.

We can also define a binary implication operator c → d = {e | c e d}. This definition is adapted from Complete Heyting Algebras [START_REF] Vickers | Topology via logic[END_REF] and it additionally allows us to encode the pseudo-complement of a constraint as ∼ c = c → false. Pseudo-complements do not necessarily comply with the law of the excluded middle and the above definition only works as an implication if the cs is distributed, that is if for every a, b, c ∈ Con we have that:

a (b c) = (a b) (a c) (1)
Interface and usage: Table I describes part of the interface to the cs module. The input elements in glb and lub (the respective implementations of the meet and join operators) may be empty vectors, in this situation they produce the bottom and top elements respectively. Similarly, Properties of cs: As mentioned above, one optional and important property of constraint systems is that of distributivity. This property is necessary for modus ponens to hold, that is, (c → d) c d must be true for every c, d ∈ Con [START_REF] Haar | An algebraic view of space/belief and extrusion/utterance for concurrency/epistemic logic[END_REF]. In D-SPACES distributivity can be checked with the boolean method CS.is_distributive().

The D-SPACES snippet in Fig. 3 creates a constraint system with the underlying lattice of Fig. 2. Additionally, it calculates 1 2, {2, 3, 4}, 2 → 3 and checks if the cs is distributive.

Spatial Constraint Systems with Extrusion:

We continue with the scs and scs-e modules. For this we begin by defining the remaining two constraint systems. We refer to S.1 as emptiness, intuitively signifying that empty spaces amounts to no information at all. S.2 is referred to as -distribution, meaning that spaces distribute over the joining of information. A derived property of S.2 is monotonicity of spaces; for all i = 1 . . . n, S.

3 if c d then [c] i [d] i for all c, d ∈ Con.
The intuition behind S.3 is that the structure of the information (w.r.t. ) is preserved inside spaces. We now define extrusion in spatial constraint systems.

Definition II.4 (scse). An n-agent spatial constraint system with extrusion is a scs equipped with n self-maps ↑ 1 , . . . , ↑ n (called extrusion functions) over its set of elements. Additionally, for each map ↑ i : Con → Con: E.1 [↑ i c] i = c for all c ∈ Con.

E.1 means that the i-th extrusion function is the right inverse of the i-th space function. One might also require that the extrusion function satisfy duals of S.1 and S.2: E.2 ↑ i (true) = true, and

E.3 ↑ i (c d) = ↑ i c ↑ i d for all c, d ∈ Con.
It is not unreasonable to suppose that the extrusion function might be a semantical interpretation of an operation that satisfies emptiness and -distribution.

Interface and usage: Table II exposes part of the interfaces to the scs and the scs-e modules. The interfaces are similar in that both offer methods to retrieve, set and modify the space/extrusion functions. However, with module scs-e it is possible to evolve a scs into a scse according to a choice function that automatically maps the extrusion functions. There are four choice functions implemented ; i. infima, ii. suprema, iii. manual and iv. random.

The choice function manual expects the user to set the extrusion function using e_map after the creation of the scse. The choice function random maps each constraint c ∈ Con to a random element of its space function pre-image (i.e. [c] -1 i ). Choice functions infima and suprema map each constraint to the greatest lower bound and least upper bound appropriately of its space function pre-image. Mathematically speaking, for each c ∈ Con we have

↑ i c = [c] -1 i and ↑ i c = [c] -1 i
when using the infima and sumprema choice functions respectively. Choice functions random and manual do not necessarily satisfy E.1 while infima and sumprema do, moreover the choice function infima satisfies E.2 and E.3 [START_REF] Haar | An algebraic view of space/belief and extrusion/utterance for concurrency/epistemic logic[END_REF].

Properties of scs and scs-e: Several properties of the space/extrusion functions might be desired or needed for correct functioning (e.g. E.1 as mentioned above). Both modules offer property checking via the methods s_properties and e_properties. One can verify standard properties like surjectivity (this implies the existence of an inverse function), -distributivity (i.e. S.2, E.3) and inversion (i.e. E.1) among others.

The snippet in Fig. 4 creates a scs out of the cs created in Fig. 3 and maps some of its elements. Next, it creates a scs-e with this scs. Here, the parameter EC_SUPREMA

A. Complexity

We now turn our attention to the details of time complexity (see Table III for a complete chart). Implementation of lattices operators, and by extension those of constraint systems, might yield considerable time complexities due to the potentially large number of elements in the cs. We discuss the most critical cases here, those of methods leq, glb, lub and imp. Recall that posets were implemented using a BGL graph.

leq:

The result of c d can be given in constant time provided this is calculated in advanced. We achieve this by performing a transitive closure on the poset relation whenever an element is added (i.e. method add_element). This transitive closure is performed using the BGL method boost::transitive_closure. glb and lub: We take advantage of the fact that posets in cs are always in transitive closure to lower the complexity of calculating meets and joins. The meet and join of a set of elements S are defined as glb(S) = max(S l ) and lub(S) = min(S u ) respectively, where S l (lower bounds of S) is defined as the set {e | ∀ s∈S e s} and S u (upper bounds of S) as the set {e | ∀ s∈S e s} [START_REF] Davey | Introduction to lattices and order[END_REF]. Moreover, S l and S u can be calculated in consant time with BGL methods boost::inv_adjacent_vertices and boost::adjacent_vertices. Calculating max(S l ) and min(S u ) then boils down to finding a minimum value as the next proposition shows. Corollary II.1 follows from Proposition II.1. Moreover, some elements need not be tested when calculating S. A particular common case is the negation (i.e. d = false), the elements of the set (c u \{false}) l are never in S. The next proposition proves this. Suppose not, then a ∈ S , meaning that ∃a ∈ c u \{false} and a a . Furthermore c a < false and a a . We can show that c a a and by transitivity we deduce that c a < false. Furthermore a ∈ S (by supposition), meaning that c a false, a contradiction.

III. SEMANTICAL DESCRIPTION OF SOCIAL NETWORK BEHAVIORS

Boolean Algebras: Adopting D-SPACES for constructing proof of concepts using constraint systems with extrusion is feasible. To achieve of this, the module ba is offered as an implementation of powerset boolean algebras (ba). In this module, a constraint system is built automatically from a powerset lattice which in turn is constructed from a set of elements called atoms. The atoms represent the indivisible bits that make up the information in the constraint system, moreover, a powerset lattice is complete and distributive by construction [START_REF] Davey | Introduction to lattices and order[END_REF].

Given a set of atoms A, a powerset ba is a specific case of a scse where Con = P(A), = ∪ (or ∩ if the lattice Space and extrusion functions are defined programmatically using c++11 lambda functions. Because the powerset ba is also a scse, the module also exposes all the functionality of the constraint systems discussed up until this point. The code example in Fig. 5 creates a twoagent powerset boolean algebra and automatically maps the extrusion functions as the infima choice of user-given space functions.

A. A Tagged Social Network

We proceed to illustrate an application of constraint systems with extrusion as semantics for epistemic behaviors in social networks. We define a social network of comments that are tagged according to their content, the tags used are the following: h: Personal. p: Political. r: Religious. n: News. s: Sports.

We create a powerset boolean algebra to represent the social network, its set of atoms being the above tags. Additionally, there are three users in the social network represented as the three agents of the constraint system: ba<char> ReseauSocial( { 'h', 'p', 'r', 'n', 's' }, 3 ); Users in this social network are allowed to have their own set of beliefs inside their spaces (e.g. walls) and make opinions about the existing information (e.g. posts). We intend to use a boolean algebra to calculate the semantic meaning of scenarios where these opinions and beliefs exist together. For this we express the epistemic behaviors using the logical language of belief and utterance BU n [START_REF] Haar | An algebraic view of space/belief and extrusion/utterance for concurrency/epistemic logic[END_REF]:

F := t | F ∧ F | ¬F | B i (F ) | U i (F )
where i = 1 . . . n. In BU n , a comment F can be a tag t, a conjunction of comments, a negation of a comment, a user belief (i.e. B i (F ) stands for "user i believes F ") and a user utterance (i.e. U i (F ) stands for "user i utters F ").

We assign to each user a profile that dictates how he believes and utters comments. User 1 is a political person and at the same time discreet of his personal life, user 2 has a very religious character while being apolitical and finally user 3 is an objetive individual. We emulate their belief profiles by applying the next lambda function as the space function of the social network: Notice how user 1 inserts in every news a political aspect, while user 2 give to his personal comments a religious interpretation. User 3 is objective and interprets the comment unchanged. We also create a lambda function to code the uttering profiles: In this case user 1 inserts a political angle in every news but removes any personal detail from a comment. User 2 removes the political aspect in the comment and user 3 remains objective. To interpret statements of epistemic behavior in the social network we inductively give semantics to the language of belief and utterance using constraint systems with extrusion. We define a function • : F → Con that maps a statement from BU n to a constraint of

auto belief_func = [] (int
auto utterance_func = [] (int
ReseauSocial. t = {t} F ∧ F = F F ¬F = ∼ F B i (F ) = [ F ] i U i (F ) = ↑ i F
A tag is semantically interpreted as a set containing the tag, the conjunction of comments is interpreted as their join, the negation as the pseudo-complement and the belief and utterance actions as the space and extrusion operators respectively. We now present some epistemic scenarios where we use the boolean algebra representing the social network to calculate their semantical meaning. As a first case, we want to model the belief of user 2 of a news comment that user 1 believes true and utters to him:

B 2 (B 1 (news U 1 (news)))
We encode this scenario in the social network as follows: The semantical result of the above statement is {'n', 'p'} indicating that the subjective (possible wrong) political interpretation of the news from user 1 was also picked up by user 2. Next, we model an scenario where user 1 is a friend of user 2 and he comments on their mutual personal activities (a sport activity denoted here by personal). For this, user 1 verifies if the activity is common to them, and utters such activity as interpreted by user 2:

B 1 (personal) → U 1 (B 2 (personal sports)) B 1 (personal)
The scenario is encoded as follows: The result here, {'h', 'r', 's'}, shows that the semantical interpretation mixes religious and sport tags in the same scenario. Such configurations could be considered potentially problematic and politically incorrect for a moderator of the social network. For the last scenario we want to model user 3 as an active liar where he intentionally utters to the other users news he regards as untrue. User 2 however already believes the news to be untrue:

B 3 (¬news ¬news → U 3 (B 1 (news) B 2 (news)))
B 2 (¬news) The semantical result is {'h', 'n', 'p', 'r', 's'} which is the top element of the constraint system. This can be interpreted as false due to the inconsistency generated in the beliefs of agent 2 after the news is uttered to him by agent 3.

IV. CONCLUSIONS AND FUTURE WORK

We presented D-SPACES, an implementation of constraint systems with space and extrusion operators for semantically describing information structured in spaces. We covered the different definitions of constraint systems as well as an implication operator to increase expressivity. Additionally, we documented the different methods in the implementation to verify conditions in the constraint systems that might be desired for certain properties to hold. To implement the ordering relation of a constraint system we used the BGL's implementation of graphs. This, together with some mathematical results, allowed us to work on the complexity of the cs operators.

As a way to code proof of concepts on scse we introduced a module to create powerset boolean algebras (a specific case of scse) with space and extrusion functions specified as lambda functions. Furthermore, we illustrated the use of scse with a semantical interpretation of an epistemic language of belief and utterance. Here, we created a small social network as a powerset ba and discussed the resulting semantical interpretations of different epistemic behaviors described in the aforementioned language.

As future endeavors we plan to implement more significant cases of scse and support more data types. This will allow for more description languages to be interpreted easier and quicker. We would also like to see support for removing elements, as this, together with the add_element method, would allow to interactively manipulate a scse and give meaning to a constantly changing structure of information. Finally, we envisage that results from an interpretation of a language can be coupled with other tools to perform verification and/or detection of desired/undesired features.

Figure 1 .

 1 Figure 1. General class diagram

Definition II. 1 (Figure 2

 12 Figure 2. A Poset

Figure 3 .

 3 Figure 3. Snippet using the cs module

Definition II. 3

 3 (scs). An n-agent spatial constraint system (scs) is a cs equipped with n self-maps [•] 1 , . . . , [•] n (called space functions) over its set of elements. Additionally, for each map [•] i : Con → Con we have: S.1 [true] i = true and S.2 [c d] i = [c] i [d] i for all c, d ∈ Con.

Figure 4 .

 4 Figure 4. Snippet using the scs and scse modules

Proposition II. 1 .

 1 max(S l ) = arg min si∈S l |s i u | Proof: Suppose not, then s k = max(S l ), s j = arg min si∈S l |s i u | and s j < s k because the maximal element is unique ( is antisymmetric by Definition II.1). Furthermore, s k u ⊂ s j u because is transitive. Consequently |s k u | < |s j u |, a contradiction. Corollary II.1. min(S u ) = arg min si∈S u |s i l | imp: Recall that c → d = S where S = {e | c e d}, we lower the complexity by characterizing S. When c d we have that S = Con, thereby c → d = Con = true. When c d is not the case, it is easy to show that d u ⊆ S, whereby d u = d, therefore we can safely omit all elements of d u from S, except d (due to associativity of ).

Proposition II. 2 .

 2 S ∩ S = ∅ where S = {e | c e false} and S = (c u \{false}) l . Proof: If c = false then S = ∅, thus the proposition is trivially true. If c = true we prove that if a ∈ S then a ∈ S.

  (or ∪ if inverted), true = ∅ (or A if inverted) and false = A (or ∅ if inverted). Additionally, a boolean algebra is equipped with a complementation operation (i.e. c ) that we calculate by using the pseudocomplement 4 defined in Section II.

	ba<char> BA( {'c', 'a', 'b'}, 2, true );
	// space function
	auto s = [] (int i, set<char> e, set<char> atoms) {
	switch( i ) {
		case 1: // s_1(c) = c
		return e;
		case 2: // s_2(c) = A \ {c}
		return set_difference( atoms.begin(),
	→	atoms.end(), e.begin(), e.end() );
	}
	};
	BA.map_s( s, EC_INFIMA ); // e_n(c) = glb(s_n_inv(c))
	BA.m_scse.is_distributibe(); // All powerset lattices
	→	are distributive
			Figure 5. Snippet using the ba module
	is inverted),	= ∩
				Table III
			WORST-CASE COMPLEXITY OF METHODS, n MEANS # OF ELEMENTS IN THE CS
			Method	Complexity Method	Complexity
			add_element	O(n 3 )	s, e	O(1)
			leq	O(1)	s_inv, e_inv	O(n)
			glb, lub	O(n 2 )	s_map, e_map	O(1)
			imp	O(n 3 )	s_property	O(n 2 )
			is_distributive O(n 3 )	e_property	O(n 2 )

http://www.boost.org/doc/libs/release/libs/graph/

http://developer.apple.com/opensource/tools/headerdoc.html

http://www.lix.polytechnique.fr/ ∼ perchy/d-spaces/

In powerset lattices, the complement and the pseudo-complement are equivalent.

ACKNOWLEDGMENT This work has been partially supported by the Colciencias project 125171250031 CLASSIC, and Labex DigiCosme (project ANR-11-LABEX-0045-DIGICOSME) operated by ANR as part of the program "Investissement d'Avenir" Idex Paris-Saclay (ANR-11-IDEX-0003-02).


Maxime Dupraz

Roberta Poloni

Kitti Ratter

David Rodney

Maurizio De Santis

Bruno Gilles

Guillaume Beutier

Marc Verdier

Wetting layer of copper on the tantalum (001) surface

Keywords: numbers: 68.35.bd, 68.35.Md, 61.05.C-

come   L'archive ouverte pluridisciplinaire

INTRODUCTION

Copper is nowadays a widely used interconnected metal in integrated circuits devices. However, the rapid diusion of copper through silicon and its poor adhesion to silicon oxide led to the investigation of reliable diusion barriers to isolate the copper interconnects from the silicon chips. Among the diusion barrier metals, tantalum is one of the most interesting candidates and the past two decades have seen an increasing interest for the study of the CuTa system 14 . On top of its technological interest, the CuTa system is also a prime example of a strongly heterogeneous lm-substrate system with almost zero mutual solubility 5 , dierent crystal structure [face-centered cubic (fcc) Cu vs. body-centered cubic (bcc) Ta], and very dierent lattice parameters. An atomic scale understanding of the growth mode, structure and thermodynamic stability of Cu thin lms on Ta substrates is thus of both fundamental and technological interest.

The Cu/Ta interface is a good example of a bi-metallic system with a Stranski-Krastanov (SK) growth mode 6 and can be described as a growth of three-dimensional (3D) islands on top of a thin wetting layer. The structure and morphology of the Cu/Ta interface is however dicult to predict and the study of the stability and wetting behavior of thin Cu lms deposited on a Ta substrate has been the subject of several experimental investigations and controversial observations over the past few years. All studies agree that Cu thin lms are metastable on Ta and tend to dewet into 3D structures, leaving a thin wetting layer: this general behavior has been observed on polycrystalline bcc Ta 7 and on single-crystal surfaces of the bcc 8 and β structures 9 .

Most studies deal with the (110) surface of bcc tantalum, which is the dense plane of the stable structure. It has been established that ultrathin Cu lms form a stable pseudomorphic (PM) layer when deposited on top of a Ta (110) substrate for a coverage up to 1.22 monolayers (ML) 10 . Additional Cu layers are unstable and dewet in the solid state at temperatures and with kinetics depending strongly on contamination 7,9 and on the lm thickness 8 . On a clean Ta surface in a Ultra High Vacuum (UHV) environment a Cu monolayer is stable up to 1000 K, temperature at which diusion into the polycrystalline bulk occurs 7 . It was shown experimentally 9 and with ab initio calculations 11 that when Cu lms dewet from Ta(110) substrates, they leave a single stable monolayer on top of which 3D Cu islands form. The crystallographic orientation of the dewetted copper on Ta(110) follows the Nishiyama-Wassermann relationship: Ta(110) [110]//Cu(111) [112] 8 .

The growth mode and wetting behavior of Cu thin lms on Ta(001) are not well documented. The main experimental UHV investigation, performed by Venugopal et al., reported the dewetting of Cu thin lms deposited on Ta(001) 8 . They observed, by X-ray diraction, both the (111) and (001) out-of-plane orientations of the Cu islands and found, based on the morphologies observed by Scanning Electron Microscopy (SEM), that the latter is largely predominant. On the other hand, Francis et al. observed a strong (111) texture for copper thin lms sputtered on Ta(001) 12 . We also reported the dewetting of highly strained Cu islands with Cu(001)[110]//Ta(001)[100] orientation relationship 13 . Venugopal et al. evidenced a remaining wetting layer between the dewetted islands, with a thickness estimated to less than 5 Å, corresponding to 1 or 2 ML 8 .

There is, to our knowledge, no experimental determination of its structure to date, but several numerical works have addressed the question. A rst study employing molecular dynamics (MD) predicted that the Cu(111)/Ta(001) interface is more stable than Cu(001)/Ta(001) and Cu(110)/Ta(001) interfaces 14 . More relevant to the dewetting of a single Cu thin lm, Lazic et al. performed MD calculations of the deposition of Cu on a Ta(001) surface, and found a fcc structure with (111) texture from the third Cu ML, on top of a PM ML and a complex intermediate ML 15 . Only Hashibon et al. 16 developed cross potentials for CuTa from ab initio calculations, to describe the dewettting of Cu on the Ta(110) surface. There is thus so far no numerical work predicting the Cu(001)[110]//Ta(001)[100] orientation relationship evidenced by Venugopal et al. and Beutier et al. 8,13 . We note that in the works mentioned above, ab initio calculations using the density functional theory (DFT) were not directly employed to assess the stability of various interfaces, but used indirectly to build interatomic potentials for MD simulations.

In this study, we used Surface X-Ray Diraction (SXRD) and DFT calculations to address the presence and structure of a wetting layer of Cu on the Ta(001) surface. We measured SXRD in situ while depositing and dewetting a thin Cu layer on a Ta(001) surface. The measurements show unambiguously the presence of two PM Cu layers. The interplanar spacing between the Cu layers and the uppermost Ta layers is also determined. DFT calculations in the local density approximation were used to calculate the excess interface energy of a variety of congurations with dierent numbers of Cu ML and dierent structures. A very good agreement is found between both approaches.

I. SURFACE X-RAY DIFFRACTION

SXRD is a powerful probe of the structure of crystalline surfaces 17 . Sharp interfaces give rise to Crystal Truncation Rods (CTR) in reciprocal space 18 that are particularly useful to evidence PM wetting layers 19 . Indeed, the scattering amplitude from PM layers is enhanced by interference with the scattering amplitude from the substrate in the vicinity of the in-plane Bragg reections of the latter, allowing a quantitative determination of the number of atomic layers and their interplanar spacing.

The experiment was carried out at beamline BM32 of the European Synchrotron Radiation Facility (ESRF), on the SUV end station 20 . The latter consists of an UHV chamber fully equipped for sample preparation, mounted on a Z-axis diractometer 21 . Further degrees of freedom are available to align the sample. While the deposition of copper by molecular beam epitaxy (MBE) and the dewetting could be performed in situ, the preparation of the Ta(001) surface requires ash annealing at temperatures above 2000 K, which cannot be done with the set-up of the beamline. The surface preparation was thus performed in the UHV chamber of the SIMaP laboratory and then transferred to the beamline chamber.

A high purity (more than 99.9999%) Ta crystal, cut and polished to less than 0.1 • along the (001) plane, was purchased from MaTecK GmbH. The surface was prepared by repeated cycles of Argon sputtering and ash annealing above 2000 K to remove oxygen and carbon contamination 22 . The atomic atness of the surface was monitored by Low-Energy Electron Diraction (LEED), and the minimum level of oxygen or carbon contamination was checked by X-ray Photoelectron Spectrometry (XPS). A protective 5 nm copper layer was then de- posited to cover the Ta surface during the transfer from the laboratory chamber to the UHV beamline chamber, where it was removed by evaporation above 1300K. The transfer was done mostly in primary vacuum, with a short exposure (a few seconds) to air. We were thus able to obtain a clean Ta bare substrate surface (FIG. 1).

Four data sets (thereafter called A, B, C, and D) were collected during two experimental sessions. The conditions of preparation of the Ta surface, and the Cu deposition and dewetting diered for the four data sets. The relevant parameters are summarized in Table I. The same substrate was used for the (A,B,C) data set according to the procedure detailed above. For data set D, the substrate from experiment C was reused and thus did not undergo a high temperature ash annealing preparation. The remaining copper was evaporated in situ until a clean surface was obtained (3 minutes at 1370 K). A characteristic signature of Oxygen can be seen in the Auger spectrum of the bare Ta substrate, at 510 eV. It corresponds to about a third of an atomic layer. These are adsorbed Oxygen atoms, responsible for a surface reconstruction 23 , that desorb during the dewetting (green line in FIG. 1).

Starting from the bare substrate at room temperature, a few (exact numbers depending on data sets) ML of copper were deposited in situ at low rate (∼5 min/ML). For the data set A only, the Cu thin lm was then sputtered by argon for 20 minutes. The dewetting was then performed in situ at high temperature (1020 1070 K), using the furnace of the sample stage. The temperature was monitored with a pyrometer and the base pressure into the chamber was carefully checked to avoid copper evaporation from the surface. The dewetting was monitored by the rocking curve of the Cu 111 reections: the beginning of dewetting into islands yield a sharp increase of the peak intensity and a decrease of the rocking curve width. After dewetting, the Auger spectra show an increase of the ratio between low energy electron and high energy electrons (FIG. 1). This can be explained by the presence of a thin wetting layer between the islands. The Cu(920 eV)/Cu(60 eV) intensity ratio does not increase despite the dewetting at high temperature, which suggests that diusion of copper into the substrate can be excluded 7 . At this stage, the Oxygen signature has disappeared, due to the desorption of the adatoms upon heating 23 . No other contamination is evidenced yet. The Auger spectra were remeasured after the CTRs measurements, evidencing oxygen and carbon contaminations of more or less importance depending on the data set (FIG. 1). The level of contamination is summarized in Table II. Because of the slow contamination, the delay between the dewetting and the CTR measurements could be an important parameter. This issue can be addressed by comparing the four data sets.

The X-ray source is a bending magnet and the monochromator is a Si(111) double crystal, with the second crystal bent to give sagittal focusing on the sample. The vertical focusing is provided by a mirror, resulting in a spot size of about 0.4×0.3 mm 2 . The measurements were performed at photon energy of 22 keV. The detector was a Maxipix camera 24 . In order to reduce the Thermal Diuse Scattering from the bulk, the penetration of Xrays into the sample has to be kept as small as possible. This can be achieved by using a low glancing angle α of the incoming X-ray beam. In this experiment alpha was set to 0.6 • , a value about three times the critical angle of total external reection (0.194 • for Ta at 22 keV).

The atomic structure of the surface can be determined from the structure factors measured along the CTRs, extracted from the integrated intensities measured by scanning across the CTRs with the angle ω 20,25 over a range of ±5 • . This relatively large range ensures an accurate measurement of the background level. The CTRs are thereafter indexed in the reciprocal lattice units (r.l.u.) of bcc tantalum, with a (001) surface. The 10L and 11L CTRs (0<L<3) were measured for each data set. All measurements were averaged over two equivalent CTRs, based on the overall tetragonal symmetry of the surface. The agreement factor ∆ (average-normalized variance) between equivalent CTRs is reported in Tab. II. The error bars shown in the gures below are calculated as a mix of the variance between equivalent reections and of the statistical error 26 . For all data sets, clear interferences can be seen on the CTRs, revealing the presence of epitaxial layers (FIG. 2). A straitforward conclusion is the absence of amorphisation of copper, such as observed by Kwon et al at the interface with β-tantalum upon annealing 27 . Consistently with our result, they do not see such amorphisation but an atomically sharp interface with bcc tantalum, of which the crystallographic orientation is not given.

Auger spectroscopy revealed a strong carbon contamination in the data set A after the CTR measurements. This is clearly seen on both CTRs from this data set, which show less contrasted features than the other three data sets and a shift of the minimum of the 11L CTR (FIG. 2). The impact of carbon contamination seems to be lower on the 10L CTR, which was measured shortly after dewetting, while the 11L was measured three hours later. Such contamination could decrease the coherent fraction of the wetting layer. The other three data sets show very similar CTRs. The eect of oxygen contamination is dicult to evaluate, because the contamination level is similar for the four data sets.

After the last SXRD measurement, the surface of the sample has been imaged by optical and atomic force microscopy and conrm the dewetting of the excess copper into 3D islands similar to those observed in 8,13 . Their density is very low, in agreement with the small quantity of copper deposited for this data set (estimated to 3 ML, among which only one dewetted), with an average 30 µm distance between islands.

II. DENSITY FUNCTIONAL THEORY CALCULATIONS

From the measured CTRs, the precise determination of the structure of the interface is in principle obtained by the tting of the experimental data. DFT calculations were performed to gain further insight in the experimental results. The agreement between the interfaces predicted from the experimental data and the DFT calculations is quantied and discussed in details.

Total energy calculations were performed using the local-density approximation to the exchange and correlation and norm conserving Martins-Troullier pseudo potentials 28 as implemented in the PWSCF code 29 . The wave function and charge density cutos were taken as 90 Ry and 360 Ry, respectively. Atomic relaxation was performed until atomic forces were less than 0.03 eV/Å. The bulk structures of bcc Ta and fcc Cu were fully optimized using a 12x12x12 Monkhorst-Pack grid 30 for the integration of the irreducible Brillouin zone leading to a Cu = 3.554 Å and a T a = 3.235 Å. These values are about 2% smaller than the experimental values (3.615 Å and 3.301 Å respectively at room temperature), consistent with the local density approximation. Importantly, the ratio of calculated lattice parameters is (a Cu -a T a )/a T a = 9.9%, in good agreement with the experimental value (9.5%). The slab calculations of a few PM Cu layers described in the following section employed a 12x12x1 Monkhorst-Pack grid.

In order to determine the stability and structure of a Cu thin lm on Ta(001), interfaces containing 1 to 6 PM layers were modeled using a periodic slab conguration (FIG. 3). It consists of a stack of 14 Ta (001) planes covered by 1 to 6 bcc Cu layers on both sides, leading to two equivalent Cu/Ta interfaces. Each layer was modeled using only one atom per unit cell by taking advantage of the in-plane periodic boundary conditions. A thick vacuum region of about 15 Å was added along z between the two Cu lms in order to ensure a negligible interaction between the two free surfaces. The structural relaxation was computed by relaxing the z coordinate of all atoms of the supercell.

The thermodynamical stability of Cu thin lms was evaluated by computing the excess interface energy as the energy dierence between the fully relaxed conguration for each model and the conguration with the same number of atoms in their bulk environments. It can thus be written as:

γ = E supercell -(E T a bulk + E Cu bulk ) 2A (1)
where E supercell is the total energy of the slab calculation and A is the surface area (considered twice for the two Cu/Ta interfaces). The excess interface energy described in Eq. 1 is the sum of the lm/substrate interface energy, γ i , and the free surface energy of the thin lm, γ f , i.e. γ = γ i + γ f . The elastic strain energy contribution (estimated to 1/2M ϵ 2 h, with M the biaxial in plane elastic modulus, ϵ the strain and h the thickness) which is im- plicitly contained in Eq. 1 increases with the number of layers of the lm and quickly dominates the trend.

In order to evaluate the stability and growth mode of a lm on a substrate, the energy dierence δ between the free surface and the interface congurations needs to be considered. This is given by 31,32 :

δ = γ i + γ f -γ s = γ -γ s (2)
where γ s is the free surface energy of the substrate. For δ < 0 the lm/substrate interface is thermodynamically stable and a complete coverage of the substrate by the thin lm is expected. When this condition is satised, a layer-by-layer growth, known as the Frank-vander-Merwe mode is observed 33,34 . Starting from δ = 0, the Stranski-Krastanov growth is obtained, which corresponds to a 3D growth on top of the thin lm. The excess interface energies calculated up to 6 Cu PM layers are reported in Tab. III. The computed free surface energy, γ f , of Ta( 001) is 3.18 J/m 2 which is larger than the experimental value of 2.5 J/m 235 , but close to other theoretical values of 3.10 J/m 236 and 3.14 J/m 237 . This results in δ < 0 for up to 5 PM layers. As mentioned above, the increase in γ found for increasing number of layers, reects the increase in strain energy.

The conguration with 2 PM layers on top of the substrate has the lowest energy and is therefore the most stable conguration for a thin lm of Cu on Ta(001) while 1, 3, 4 and 5 Cu PM layers are metastable. The calculations indicate that a Frank-van-der-Merwe growth mode is expected up to 5 PM layers above which a Stranski-Krastanov mode is expected. This result is consistent with experimental data which reported the presence of 1 or 2 wetting layers 8 . For all the PM congurations, the high in-plane tensile strain induces a compensative high out-of-plane compressive strain among the Cu layers. The conguration with 2 PM layers is studied in more details in the next section.

As a comparison, we computed the wetting behavior of Cu on Ta(110) and found that 1 PM layer is the most stable conguration thermodynamically, while 2 PM layers are metastable. The computed free surface energy of Ta( 110) is 2.98 J/m 2 while the excess interface energy is 2.34 J/m 2 and 2.74 J/m 2 , respectively. This result contradicts the ndings of Ref. 11 , where none of the PM congurations were predicted to be stable on the Ta(110) surface, but is consistent with experimental observations 7,10 .

We also considered the case of Cu fcc layers on top of the Ta substrate or on top of the PM Cu layers. These congurations, requiring a signicantly larger cell and larger computing time, did not converge to acceptable structures. For instance, the conguration with a single Cu fcc layer on top of the Ta substrate tends to form a PM layer. Other cases involving PM Cu layers result in an out-of-plane modulation due to the periodic boundary conditions. It is therefore impossible to extract the excess interface energy of these congurations. We note that bcc copper is not uncommon at interfaces 38,39 . The interplanar distances in the DFT conguration with two PM layers are shown in FIG. 4. The high in-plane mist strain results in reduced interplanar distances along the (001) direction by 11% for the TaCu interface and by 36% for the CuCu bilayer, with respect to the interlayer spacing in bulk Ta (a T a /2). Such a huge tetragonal distortion has been observed in thick lms in the case of the Bain transformation 40 . Here it is not a relevant parameter of stability since we deal with only two atomic layers, each of them being at an interface. It is more relevant to consider the CuCu nearest-neighbor distance in the Cu bilayer. With an interplanar distance of d 1,2 = 1.042 Å, the latter is:

d Cu-Cu = √ 2 ( a T a 2 ) 2 + d 2 1,2 ≈ 2.513 Å (3)
By comparison, the nearest-neighbor distance in fcc copper (a Cu / √ 2) is also 2.513 Å. (The real experimental value is 2.556 Å at room temperature.) We see that, in absence of a third layer, the body-centered tetragonal pseudomorphic stacking allows the copper atoms to keep an interatomic distance similar to that in the bulk fcc value, thus minimizing the elastic energy. A third PM layer would cause a large frustration either of the rst-neighbor distance or of the second-nearest-neighbor distance, hence the increase of energy above 2 PM layers.

The interplanar distance at the interface is of 1.436 Å, resulting in a CuTa interatomic distance:

d Cu-T a = √ 2 ( a T a 2 ) 2 + d 2 0,1 ≈ 2.701 Å (4)
The tantalum atoms are also aected by the presence of neighboring Cu atoms, and a strong relaxation of the rst three tantalum interlayer distances at the interface is observed. The rst two are compressed by 3.9% and 2.5% for d -1,0 and d -2,-1 respectively, while the third one is increased by 2.3%. The strain below the rst three planes nearly vanishes: the spacing between Ta -4 , and Ta -5 , Ta -5 and Ta -6 , and Ta -6 and Ta -7 is indeed close to the bulk nominal value of Ta (respective variations of -0.3%, -0.45% and 0.24%).

III. COMPARISON BETWEEN DFT CALCULATIONS AND SXRD DATA

According to the DFT calculations, the thermodynamically most stable conguration is 2 PM copper layers on top of the Ta(001) surface. The agreement between DFT calculations and SXRD measurements was checked by computing the structure factors using the DFT congurations and comparing them with the experimental structure factors. These calculations were performed in the kinematical approximation of X-ray diraction using the software ROD 41 according to:

F tot (HKL) ∝ |F b (HKL) + F s (HKL)| (5)
where HKL are the Miller indices. The bulk structure factor F b (HKL) is calculated for a perfect semiinnite crystal of tantalum, and the surface structure factor F s (HKL) is calculated using all the atoms of the model, including the tantalum atoms belonging to the seven layers just below the copper layers:

F s (HKL) = ∑ j f j e 2iπ(Hxj +Kyj +Lzj ) e - B j (H 2 +K 2 +L 2 ) 4a 2 T a
(6) where f j is the atomic scattering factor of atom j, (xyz) j its position in fractional coordinates and B j its isotropic Debye-Waller parameter. The scale factor in Equation 5 includes a roughness factor calculated within the β model 42 .

FIG. 5 presents several comparisons between CTRs measured from the cleanest Ta surfaces (data sets A and D), and the simulated CTRs for 1, 2 and 3 PM Cu layers. For both the 11L and 10L CTRs, the best agreement is found for 2 PM layers. We note that the structure factors are systematically overestimated at high L values. Despite this discrepancy, the 2 PM model reproduces well all the features of the experimental data, unlike the other models. To clarify the importance of the Ta relaxation, the structure factors of four dierent systems were calculated and compared to the experimental data. In the rst case, the relaxation of the Cu atoms was taken into account whereas the atomic positions for Ta were equal to their nominal bulk values. In the second, third and fourth cases, the relaxation of Cu was taken in account and the relaxation of the Ta atoms was restricted respectively to 2, 3 and 7 Ta planes. As shown in FIG. 6, for up to 3 Ta planes, the number of Ta planes taken into account for relaxation has a very strong inuence on the calculated structure factors. In all cases and independently of the number of relaxed Ta planes, the positions of the minima of amplitude are reproduced accurately for both CTR. However, the agreement between the calculated structure factors and the experimental data is rather poor for less than 3 relaxed Ta plane. For the 10L CTR, the four congurations reproduce the dip of intensity around L = 2.1 r.l.u., however the bump which is observed in the 2.2 < L < 2.6 r.l.u. region is reproduced accurately only when at least 3 Ta planes are relaxed. Similar conclusions can be drawn for the 11L CTR where the congurations with 0 and 2 relaxed Ta planes fail to reproduce the curve inection in the 1 < L < 1.5 r.l.u. and 2.3 < L < 2.7 r.l.u. regions. The dip of amplitude for L = 0.7 r.l.u. is also strongly overestimated when the number of relaxed Ta planes is less than three. These remarks allow to set an upper limit for the resolution obtained on the lattice relaxation: the relaxation of the third Ta layer, of 0.03 Å, is clearly seen. The simulated CTR for 3 and 7 relaxed Ta planes exhibit a remarkable similarity. This suggests that most of the relaxation occurs within the upper three Ta planes and is consistent with the small value of displacements found for the Ta planes further away from the interface. The good agreement with the experimental data obtained by relaxing the atomic layers is a strong evidence supporting the absence of nonpseudomorphic layers (fcc) on top of the pseudomorphic layers, because additional layers, even though invisible on the CTRs originating from the Ta reciprocal lattice points, would modify the interplanar spacing.

Finally, the DFT structure of the fully relaxed interface with 2 PM layers was employed as the starting model to t the experimental data, by relaxing the following parameters: the interplanar spacings, the Debye-Waller factors, and the β value of the roughness factor 42 . ROD also allows to release the surface fraction of the coherent layer. Attempts to do so lead to values very close to 1 (full coverage) without signicant improvements of the ts, and the results presented here were performed without releasing this parameter. Indeed, the total amount of deposited copper exceeded 2 PM and there is no reason to think that the surface coverage is not full. The 8 experimental data sets (2 CTRs for each of the 4 samples) were tted independently. FIG. 7 shows a comparison between two experimental curves and the calculations before and after tting. The interlayer spacings resulting from the ts are given in Tab. IV, averaged by CTR over the 4 samples, and shown in FIG. 8. Alternative starting guesses were tried, such as using a T a /2 for the TaTa interlayer distances, and the ts converged to the same values well within the error bars. Remarkably, the nal t parameters are very close to the DFT predictions. In particular, the SXRD data conrm the relaxation of the three upper atomic layers of tantalum. For each CTR, the dispersion of the values of the interlayer spacings is very small, suggesting the small inuence of the surface contamination. There is actually more dispersion between the values provided by the two CTRs. This systematic error is also observed on the roughness parameter β, which is found of the order of 1% for the 10L CTR and of the order of 10% for the 11L CTR. In addition to the interlayer spacings, the isotropic Debye-Waller factors of the 4 upper layers (the 2 Cu layers and 2 Ta layers) are relaxed for the ts. The ts yield isotropic displacement parameters of 3.8, 4.7, 5.3, 11. perimental data at large L. We infer that they point to a large static disorder. The surface contamination and its increase with time have probably a major role in determining such high values.

CONCLUSIONS

This study of the Cu/Ta(001) interface, combining SXRD measurements and DFT calculations in excellent mutual agreement, demonstrates the presence of two pseudomorphic layers of copper wetting on the Ta(001) surface after dewetting of excess copper. This result is robust for a small contamination of the surface by carbon and oxygen. The measurements performed with the lowest contamination were used to t the surface structure and to determine the interplanar distances. The two copper PM layers are in body-centered tetragonal stacking and have interplanar spacing of d 1,2 = 1.05 ű 0.05 Å, which allows to maintain the same nearest-neighbor distance as in the bulk (fcc). This conguration, which min- imizes the elastic energy in the Cu Cu bonds, is possible only in the absence of a third layer of copper. This feature is possibly one reason that explain the anomalously fast diusion of Cu atoms during solid-state dewetting on Ta(001). Indeed, the dewetting occurs not directly on the Ta(001) surface, but on top of two PM layers.

  FIG.1. Auger spectra at various stages of the experiment (here: data set D).

  FIG. 2. 10L and 11L CTRs for four dierent data sets with dierent states of surface contamination. Error bars have been omitted to facilitate the visualization.

FIG. 3 .

 3 FIG. 3. Slab conguration to model the relaxation of a varying number of PM Cu layers.

  FIG. 5. 10L (a) and 11L (b) structure factors obtained using DFT congurations with a varying number of PM Cu layers, compared with experimental data.

  FIG. 6. Inuence of the number of relaxed Ta planes in the DFT calculations on the calculated 10L and 11L structure factors.

  FIG. 7. 10L and 11L CTRs structure factors, before and after tting.

TABLE I .

 I Sample preparation parameters for the four data sets.Oxygen contamination Carbon contaminationData set before CTR after CTR before CTR after CTR Age at start of 11L CTR ∆(11L) Age at start of 10L CTR ∆(10L)

	A	very low	medium	no	strong	3.5 h	0.073	0.5 h	0.116
	B	low	medium	no	low	2 h	0.103	3.5 h	0.099
	C	low	medium	no	low	0.5 h	0.089	3.5 h	0.079
	D	low	medium	no	medium	0.5 h	0.078	3.5 h	0.083

TABLE II .

 II Contamination of the surface before and after the CTR measurements. The age of the sample is counted from the end of the dewetting.

TABLE III .

 III Calculated excess interface energy γ as a function of the number N of PM Cu layers on the Ta(001) surface.

	N	0	1	2	3	4	5	6
	γ (J/m 2 ) 3.18 2.50 2.19 2.63 2.78 3.13 3.32

  The numerical values for 7 relaxed planes are given in TableIV. The last tantalum plane is at index 0; indexes 1 and 2 correspond to copper planes. dNN is the value of d1,2 that conserves the nearest-neighbor distance of the bulk copper.

		1.05
		1
		0.95
		0.9
	/2)
	Ta (a	0.85	7 Ta layers relaxed 2 Ta layers relaxed
	n,n-1	0.8	d NN
	d
		0.75
		0.7
		0.65
		0.6
		-5	-4	-3	-2	-1	0	1	2
					Plane index
	FIG. 4. Interplanar spacing versus plane index for 2 and 7
	relaxed Ta planes, normalized to the value in bulk tantalum
	(aT a/2).

TABLE IV .

 IV Interlayer spacings: DFT values and rened t parameters. Error bars for the CTR ts corresponds to the largest deviation to the mean in the 4 data sets (or in the 4×2 data sets for the average value).

	Interlayer spacing [/(aT a/2)] DFT value	10L		11L	SXRD average
	d-6,-5 (TaTa)	1.000	1.000	*	1.000 *	1.000	*
	d-5,-4 (TaTa)	0.995	0.995	*	0.995 *	0.995	*
	d-4,-3 (TaTa)	0.997	0.997	*	0.997 *	0.997	*
	d-3,-2 (TaTa)	1.023	1.020±0.001 1.020±0.001 1.020±0.001
	d-2,-1 (TaTa)	0.985	0.985±0.002 0.983±0.001 0.984±0.003
	d-1,0 (TaTa)	0.962	0.964±0.002 0.963±0.009 0.964±0.009
	d0,1 (CuTa)	0.888	0.903±0.006 0.85±0.03	0.88±0.05
	d1,2 (CuCu)	0.644	0.62±0.03	0.65±0.01	0.64±0.03

* value not relaxed for the ts.

  Interlayer spacing resulting from the 8 experimental curves. dNN is the value of d1,2 that conserves the nearestneighbor distance of the bulk copper. The values are given in unit of the interlayer spacing in the bulk tantalum.

		1.05
		1
		0.95	DFT
	d Ta /2) (a n,n-1	0.9 0.85 0.8	A_10L B_10L C_10L D_10L A_11L B_11L C_11L
		0.75	D_11L
		0.7	d NN
		0.65
		0.6
		-5	-4	-3	-2	-1	0	1	2
					Plane index
	FIG. 8.

ACKNOWLEDGMENTS

Beamtime is acknowledged at the French CRG BM32 beamline of the ESRF. Calculations were performed using computer resources from GENCI under the CINES grant C2016097211. This work was supported by the French ANR project MECANIX (ANR-11-BS10-0014).

K. Holloway, P. M. Fryer, C. Cabral Jr, J. Harper, P. Bai- ley, and K. Kelleher, Journal of Applied Physics 71, 5433 (1992).


C Ray

A Napoli

METHODOLOGY FOR REAL-TIME DETECTION OF AIS FALSIFICATION

Keywords: AIS Falsification, data mining, signal processing

The Automatic Identification System is an electronic system enabling vessels to send localization messages. Those messages are used for several uses such as fleet control, traffic control or boarding prevention. Sent messages contain errors, falsifications and undergo spoofing due to the unsecured channel of transmission, and that weakens the whole system and the safety of navigation. Beyond known errors, recent works have shown that falsification of AIS messages is easy, and therefore could mask or favor illegal actions, lead to disturbance of monitoring systems and new maritime risks. This paper presents the DEAIS project which proposes a methodological approach for modelling, analyzing and detecting such maritime events.

INTRODUCTION

The Automatic Identification System is an electronic system enabling vessels to send localization messages. Those messages are used for several uses such as fleet control, traffic control or boarding prevention. Sent messages contain errors (unintentional), falsifications (intentional) and undergo spoofing (intentional) due to the unsecured channel of transmission, and that weakens the whole system and the safety of navigation.

This work reports on the design and first results of a methodology for the detection of AIS falsification. The objectives are the determination of the false messages in real-time and the improvement of both the effectiveness of the system as a security system and the maritime situational awareness.

As a first step, a risk analysis study of the Automatic Identification System has been done via EBIOS method. It led to the identification of circa 350 threat scenarios. A typology of anomalies has been also proposed, alongside with a methodology for anomaly detection.

Intentional broadcast of false AIS information can be understood at both the physical and logical levels. The first approach focuses on signals transmitted by transponders while the second considers information exchanged where fraud and attacks can be identified by message-based data mining methodology to identify abnormal messages (and parameters). In our approach we are considering a combination of both analyses within a single information system.

Method for the integrity assessment of messages and the discovery of anomalous data is particularly based on spatial information, which is the cornerstone of AIS messages but not only as AIS also broadcast many contextual and control information along 27 messages. Integrity assessment is done within one lone message, between messages sent by the same vessel, and between messages sent by several vessels and include MMSI-based cross verification in order to link information received by different stations.

We also studied physical characteristics of the signal which are intended to be integrated in the mining process. We currently considered five parameters. The first parameter is the power of the received signal and the four others are time-dependent and are relative to the shape of the signal. While these parameters cannot fully qualify ship's identity and presence, the regularity of these parameters can conversely help to identify inconsistent values.

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 In: The proceedings of OCEANS[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 nonsecured 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 (Harati-Mokhtari et al., 2007), 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 (The Maritime Executive, 2012), 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 (Katsilieris et al., 2013) are types of falsification. According to (Harati-Mokhtari et al., 2007), about 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).

The whole AIS data transmission system is displayed in Figure 1, where ( 1) is GPS data transmission, ( 2) is AIS-SAT transmission, ( 3) and ( 4) display VHF marine transmission, (5) shows digital transmission and ( 6) depicts human supervision. All the chain of AIS data transmission can be affected by one of these three problems.

Figure 1 AIS data transmission

As mentioned, problems with the AIS can be understood at the physical and logical levels. DEAIS project considered these two levels for the identification of falsifications. Next sections summarise our risk analysis (section 3) and the methodology proposed for signal analysis (section 4) and message integrity assessment (section 5).

AIS EBIOS RISKS ANALYSIS

The EBIOS method (ANSSI, 2010) has been created by the ANSSI (French National Agency for the Security of Information Systems) and is used in both the public and private sectors. It is an approach of risk evaluation which clarifies the entities of the system, their vulnerabilities, the inventoried threats, and contributes in the assessment of the right level of security (compliant with ISO norms 27001, 27005 and 31000).

We conducted an EBIOS analysis of the AIS in which we compiled all known information about the system in order to obtain a complete understanding of it. The application of the EBIOS method on the AIS led to the construction of several tables that enable us to consider several risk levels and the importance to put in place security measures on certain areas which have been found out as particularly vulnerable according to threat scenarios and possible threat sources. These tables describe:

-

The essential goods (e.g. dynamic AIS data) -

The The study led to the identification of more than 350 threat scenarios. Such a study influences the choice of detection algorithms to elaborate first. In particular, it has motivated the study of the AIS signal.

SIGNATURE IDENTIFICATION THROUGH MAGNITUDE AND TEMPORAL CHARACTERIZATION

At the physical level, falsification can be identified by signal analysis. For instance, destination masking or disappearances which are also a kind of falsification, as ships turn off their AIS transponder in order to hide some of their activities can be studied by exploiting radar information (Katsilieris et al., 2013). Another approach considers radiolocation of signals to confirm the existence of a real ship and its approximate localization [START_REF] Papi | Radiolocation and tracking of automatic identification system signals for maritime situational awareness[END_REF].

In order to identify a ship's signature or possible falsifications, pertinent features extracted from each frame of the input AIS signals have been studied [START_REF] Salmon | Design principles of a stream-based framework for mobility analysis[END_REF]. An experimental campaign of reception of frame AIS was conducted in the bay of Brest. Sixteen recordings of five minutes each were collected corresponding to 10 000 usable AIS frames. Each sample is also 5 minutes with a center frequency of 162 MHz and a bandwidth of 100 kHz. It allows recording simultaneously both frequencies of the AIS.

Five features were measured for every AIS frame (Figure 2). The top graph represents the temporal evolution of the frequency modulation of the AIS signal and the down graph represents its power. The first feature is level of the received power, which will allow estimating the broadcast power knowing the distance. The four others temporal parameters are relative to the shape of the signal and are: rise time (Fig. 2-2), fall time (Fig. 234), and times before (Fig. 2-1) and after demodulation (Fig. 23).

Decoded frames, power of the received signal, and temporal characteristics of the associated signals were then gathered into a geographical database (cf. section 6) to realize a reference database of ships' id and allow statistical studies.

Figure 2 Analysis of a received AIS frame

The study of these different parameters highlights particular values which will allow us to relate with ships' identity signature. For example, Figure 3 proposes a representation of time before modulation in the form of box-plot. The X-Axis corresponds to the MMSI number of ships, the time before modulation being on the Y-Axis. For each ship, the values of "time before modulation" are in a given interval, values that seem different from a ship in the other one.

Figure 3 Box plot "Time before modulation" distribution for 'class A' AIS systems

While temporal characterization cannot fully qualify ship's identity, the regularity of these parameters can conversely help to identify inconsistent values. In addition, the study showed that repeaters exhibit specific patterns easily recognizable.

The perspective concerns the improvement of this methodology with the definition of additional signal parameters and the integration of data mining techniques combining signal features with static and dynamic information provided by AIS messages as described in the following section.

AIS MESSAGES INTEGRITY ASSESSMENT

At the logical level, fraud and attacks can be identified by message-based data mining methodology to identify abnormal messages and navigational behaviours (Iphar et al., 2015). For instance a ship navigating with a MMSI number which is not the real one, allocated and internationally recognized, can be identified by a correlation with official ships' registry and confirmed by a real-time monitoring of AIS identities at the worldwide level.

Considering the data within the fields of the 27 AIS messages, four ways to discriminate the inner integrity of those data can be distinguished. The first way consists of the control of the integrity of each field of each message taken individually. The second way is at the scale of one single message, and assesses the integrity, in this very message, of all the fields with respect to one another. As there are 27 types of messages, message of the same type have the same fields and it is thus possible to compare them and assess their integrity, this makes the third way. Eventually, the fourth way is the comparison and integrity assessment of the fields of different messages. Indeed, although pieces of information can come from different messages, it is possible to assess their integrity as some fields are either the same or linked or comparable (i.e. MMSI-based cross verification in order to link information received by different stations). Those four ways are referred as first-order, second-order, third-order and fourth-order assessments, respectively.

Depending on the type of messages assessed and the order of assessment, the number of item to check is fixed. We established a list of 669 items for the 27 messages, and an ad-hoc nomenclature has been established so that each item can have a clear unique identifier.

An integrity coefficient is assessed by order, i.e. a coefficient is computed for first-order items, another one for second-order, and so on, depending on the type of assessment wanted. Then a global coefficient can be computed, by weighting the order-based coefficients and other results from other methods as desired.

The perspective concerns the implementation of the methodology together with first detection algorithms. Amongst current developments, we are considering black hole detection in AIS transmission in order to identify possible masking. The following section introduces the architecture designed for the detection of AIS falsification.

ARCHITECTURE FOR DATA PROCESSING

A synoptic diagram of the proposed architecture can be found in the Figure 4. The signal can be received from various sources, the parser provides messages 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. Two implementations are currently developed in parallel; one based on a relational database (postgres/postgis) and a second one based on Flink (Salmon et al., 2015) to cope with larger volume of data.

The data processing box number two corresponds to a signal processing for the determination of aforementioned characteristics. These data are stored in the database with the associated NMEA message and decoded AIS frame.

The data processing box number one is in charge of onthe-fly analysis of first-order and second-order data assessment, in order to have as output coefficients to store in the database. Similarly, the data processing box number three is in charge of the analysis of third-order and fourthorder data assessment, in order to have as output coefficients to be stored in the database. This part of the study, unless the previous, needs to request historical data. The data processing box number four will be in charge of integrity assessments between AIS data and external and aggregated data, (e.g. cartographic information, weather conditions, black hole computations). Of course, the types of processing will vary according to the type of external information available, and it is not possible to have a strictly defined process in this part. A list of assessment items can be created for each new database when its specifications are known (i.e. its fields, their precision, their source and reliability), and two similar databases (i.e. on the same subject) are likely to have two different lists of assessment items as their specifications will differ. Updating of the external databases will, in certain cases, be necessary, as to ensure information is not outdated and data quality assessment is reliable.

CONCLUSION

This article proposes a method for analysing AIS data using integrity of information as a key factor, with database storage of information and an assessment done on the message itself, on the message with respect to other messages, on the message with respect to external databases and on the signal itself with its physical characteristics. Such an assessment is the consequence of the defects of this system, transmitting erroneous and possibly falsified data. This method is meant to be implemented and to provide integrity-based confidence coefficient on data that will be useful for the determination of erroneous and falsified data, leading to a risk assessment and alert triggering in a decision-support system and in the end provide an additional tool for the enhancement of maritime security.

Figure 4

 4 Figure 4 Proposed architecture In the database itself, each new entry will lead to the creation of a new item (i.e. a new line), with as attributes shall have: a unique identifier, the time of reception, the raw frame, all message field values and the various coefficient obtained through assessments (the four orders and the signal parameters).The data processing box number four will be in charge of integrity assessments between AIS data and external and aggregated data, (e.g. cartographic information, weather conditions, black hole computations). Of course, the types of processing will vary according to the type of external information available, and it is not possible to have a strictly defined process in this part. A list of assessment items can be created for each new database when its specifications are known (i.e. its fields, their precision, their source and reliability), and two similar databases (i.e. on the same subject) are likely to have two different lists of assessment items as their specifications will differ. Updating of the external databases will, in certain cases, be necessary, as to ensure information is not outdated and data quality assessment is reliable.

ACKNOWLEDGEMENT

This research is supported by The French National Research Agency (ANR) and co-funded by DGA under reference ANR-14-CE28-0028 and labelled by French clusters Pôle Mer Bretagne Atlantique and Pôle Mer Méditerranée.


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

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

Clément Iphar Mines

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

A method for integrity assessment of information in a worldwide maritime localization system

Keywords: Automatic Identification System, data falsification, integrity assessment, anomaly detection

published or not. The documents may come

A method for integrity assessment of information in a worldwide maritime localization system

Introduction

As a major place of human activities such as transportation of goods, fishing, cruising and sailing, the ocean has an important impact on the worldwide economy, and a central place in some particular domains such as energy transportation and goods transportation where 90% of worldwide traffic is done by sea. This ever increasing traffic leads to navigation difficulties and risks in coastal and crowded areas where numerous ships exhibit different movement objectives which can be conflicting.

The international traffic is globally dense, but some regions (such as Northern Europe or South-Eastern Asia) and some locations (such as straits or canals) have a particularly dense traffic. For instance Malacca strait has 50 000 vessels per year, the Panama canal 14 000, the Bab-el-Mandeb strait 10 000 and the Suez canal 20 000.

The comprehension of vessels intentions and of maritime situation comes through the analysis of ships localizations, with a long or a short time span of data. On the one hand, short-term studies concentrate on instantaneous behaviours while on the other hand long-term studies concentrate on the trajectories and the identification of specific behaviours.

Currently, one of the most widely deployed systems is the Automatic Identification System (AIS) that helps in completing the radar picture and providing information beyond the radar horizon. Section II presents the systems and the vulnerability problems it undergoes and examples of AIS falsification and section III presents the proposed methodology for the analysis of AIS messages and the detection of falsifications.

2

The Automatic Identification System

A system for maritime safety

The Automatic Identification System (AIS) was put in place by the International Maritime Organization, in the Safety Of Life At Sea (SOLAS) convention, in its 2002 version [START_REF]International convention for the safety of life at sea[END_REF]. All the vessels from the signatory states are not concerned with this system. Indeed, the SOLAS convention, in its fifth chapter, nineteenth rule, paragraph 2.4, 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].

At first, messages were transmitted (radio-transmission in the Very High Frequency bandwidth) from vessel to vessel and from vessel to coastal station within the radio horizon range (circa 40 nautical miles), then with the development of satellite technology, messages are also received by satellites and their position and trajectory can be displayed in dedicated websites. The understanding of the worldwide traffic then switched from local to global.

There are 27 different kinds of messages depending on the type of transmission, but the most used ones are the numbers 1, 3 and 5 [START_REF] Tunaley | Utility of Various AIS Messages for Maritime Awareness[END_REF], used by transponders of vessels for which the use of AIS system is compulsory, for spatiotemporal position reports, respectively scheduled, special and static.

In a standard position report of those transponders, the geographical information in the messages is sent every 2 to 12 seconds when the vessel moves, depending on the speed of the vessel: the higher the speed, the closer the messages. When the ship is anchored, the messages are sent only every three minutes [START_REF] Tunaley | Utility of Various AIS Messages for Maritime Awareness[END_REF]. The number of messages is important: in a mean day, 400 000 messages are sent from more than 22 000 vessels [START_REF]Space station keeps watch on world's sea traffic[END_REF], and in the sole waters of the European Union, circa 200 million messages are sent every year. The main data given in the message are the number of the message, the unique identification number of the user, the navigational status, the turning rate, the speed, the longitude, the latitude, the course, the true heading, the time and the destination.

The spatial components within the messages

As AIS messages are primarily localization messages, the spatial components of it are of foremost importance. In a classical position report message, the purely spatial fields are the latitude and the longitude, while the spatial-linked fields are the rate of turn, the speed over ground, the course over ground and the true heading.

The total number of bits allocated in the message number 1 for latitude and longitude is important (27 and 28, respectively), thus the elementary unit of the measure is the one ten thousandth of minute of arc (1/10 000 arcmin). The longitudes are given in a scale going from -180 to 180 deg, positive values going towards east and the latitudes are given in a scale going from -90 to 90 deg, positive values going towards north. For all longitudes and for the latitude close to the equator, this basic unit is worth circa 20cm on the surface of the Earth, this value progressively deceasing as latitudes grow. As the GNSS computation is mainly done when the vessel is moving, the accuracy of this computation shall be at least of the order of magnitude of the meter, thus the size of the basic unit shall not be the limiting element of the study.

In the message number 5, the destination of the vessel has a dedicated textual field of 20 6-bits ASCII characters. This voyage-based spatial information has nevertheless the drawback to be filled widely inappropriately.

Some other fields such as the user ID or the time stamp are not spatial data but will be useful in our study. The user ID will be used to be able to define trajectories by tracking one single user over time and the time stamp will be used to reconstruct the trajectory and shift spatial data into spatiotemporal data.

A vulnerable system

As stated before, the AIS system transmits through VHF radio band, however the transmission is free and the channels of transmission are not secured, which brings problems of both quality of information (as the messages are freely sent) and genuineness of reception (as anyone can cover genuine messages by falsified ones). Three major cases of bad data quality can be highlighted: the errors (unintentional broadcast of false information), the falsifications (intentional broadcast of false information) and the spoofing (intentional coverage of a genuine message) [START_REF] Ray | DeAIS project: Detection of AIS Spoofing and Resulting Risks[END_REF]. Moreover, the system transmits a high quantity of messages, which brings spatial big data issues in their study.

Indeed, some data contained in AIS messages are fulfilled manually during the system initialization (first use), they can be done by underestimating the importance of a proper fulfilment of the fields or by ignorance of the way the system works, and each human-filled field is subject to errors [START_REF] Harati-Mokhtari | Automatic Identification System (AIS): a human factors approach[END_REF], such as the destination field.

Intentional falsification of the AIS signal is done by the crews on board the ships in order to modify or stop the message they send, in the very particular purpose of misleading the outside world. The fact to falsify one's whereabouts is a kind of falsification allowing the user, displaying false GNSS coordinates, to be somewhere else and to hide its activity. Spoofing of AIS data consists of an action made by an external actor in order to mislead the crew of the ship and the outside world on the behaviour of the proper ship.

Exemplification of falsification

In the maritime domain, identity theft [START_REF] Windward | AIS data on the high seas: an analysis of the magnitude and implications of growing data manipulation at sea[END_REF] corresponds to the fact to navigate with a Maritime Mobile Service Identity (MMSI) number which is not the real one, allocated and internationally recognized, but with the one of another vessel that actually exists somewhere else. As the MMSI number changes, there is no way to assess a priori whether the vessel one is looking at is the right one. As stated in [START_REF]Iran, Tanzania and falsifying AIS signals to trade with Syria[END_REF], Iran used to falsify the MMSI number of some ships in order to trade with Syria, then under embargo. The Iranian ship Millionnaire took the identity of the Syrian ship Lady Rasha. At some time, there were two declared Lady Rasha, one in the Mediterranean Sea and one in the Indian Ocean.

Destination masking is also sometimes a falsification [START_REF] Windward | AIS data on the high seas: an analysis of the magnitude and implications of growing data manipulation at sea[END_REF]. As sometimes it can be considered as an error, some other cases are about a voluntary deficiency of information, done in order to sidestep the overview of the global ships flows. Disappearances are also a kind of falsification, as ships turn off their AIS transponder in order to hide their activities, such as fishing in an unauthorized area, or trade illegal goods [START_REF] Katsilieris | Detection of malicious AIS position spoofing by exploiting radar information[END_REF] with other ships or on coasts.

One of the trickery is a false closest point of approach alert [START_REF] Balduzzi | A security evaluation of AIS automated identification system[END_REF]. An alert is triggered and the vessel is forced to changed its heading and perhaps be guided to hazardous places in order to avoid a hypothetical boarding by a ghost vessel. Moreover, [START_REF] Balduzzi | A security evaluation of AIS automated identification system[END_REF] implemented a spoofing program imitating a fake ship which is following a spatiotemporal path which made it spelling a word in the Mediterranean Sea. It was then possible to see it displayed on the website marinetraffic.com.

An example of spoofing is given in [START_REF] Balduzzi | A security evaluation of AIS automated identification system[END_REF], with a pirate who emits a false signal with a higher power than the genuine one, covering it. In other vessels the system is then misled as it receives a message different than the transmitted one. This can force the pilot or the autopilot to manoeuver in order to bring the vessel away from a non-existing hazard, and possibly leading it to others actually existing hazards.

Detection and analysis of errors and falsifications

The uses of the AIS are numerous, albeit initially designed for safety and security purposes such as the prevention of boarding, the AIS can be used for investigation in case of accident, analysis of global traffic and traffic in specific hazardous areas, control of fishing fleets, cargo fleets or aid to navigation. The diversity of those uses makes necessary the fact for the users to use real data. Moreover, the confidence of the users in the system highly depends on the truthfulness of the messages, and the more unswayed is the user, the less confident will be the system.

Besides the falsification detection, which is the purpose of the next part, one of the purposes of the analysis of AIS messages is to model and detect behaviours by the establishment of behavioural patterns and the comparison between actual data and those patterns. This moving object assessment with the techniques of data mining shall be done with reliable data, cleaned up of all erroneous, falsified or spoofed messages.

Integrity assessment for AIS messages

Amongst the data quality dimensions, integrity has a leading position for the determination of the reliability of sets of data. The assessment of data quality can also be done under the dimensions of accuracy, precision, reliability, currentness, completeness and consistency [START_REF] Iphar | Data quality assessment for maritime situation awareness[END_REF], but for the overall understanding and assessment of the coherence of data, integrity covers them all, the coherence we use being defined by [START_REF] Hartmann | A probabilistic theory of the coherence of an information set[END_REF], as: "when we gather information from less than fully reliable sources, then the more coherent the story that materializes is, the more confident we may be, ceteris paribus".

Such an assessment of integrity can be done within one lone message, between messages sent by the same vessel (according to their MMSI number), between messages sent by several vessels. An exemplification of the integrity assessment is, for a lone message: "Is the speed consistent with the declared type of vessel?" or "Are the declared GNSS coordinates compatible with the existence of a navigable area?"; for several messages: "Are the declared GNSS coordinates compatible with the time stamps, the speed and the heading?" or "Is the trajectory consistent with the declared destination?"; and for several messages sent by several vessels doing the same trip: "Is the trajectory of one vessel coherent with the mean trajectory of all vessels?" or "Is the speed of one vessel consistent with the mean speed of all vessels?". The last two questions can be applied to each field, and the study can go further and ask: "If not, why?". In this case, the use of external information such as external databases (weather for instance) is necessary to the understanding of behaviours that are anomalous-looking, in order to determine whether they are anomalous or not.

Anomaly detection in AIS-derived information

Anomaly detection is used in the field of data analysis, with the three elementary steps that are: (1) the identification of the "normality" characteristics by computation and determination of data classical signatures (for instance trajectory clusters in the AIS messages case), (2) the determination of metrics for the computation of the distance of the studied behaviour from the standard behaviour and (3) the determination of threshold criteria for the distance to the standard behaviour, allowing the normality, the abnormality, the magnitude of normality and the magnitude of abnormality for a datum.

The determination of a normal behavioural pattern can be done using diverse methods such as statistical methods, neural networks or machine leaning [START_REF] Martineau | Maritime Anomaly Detection: Domain Introduction and Review of Selected Literature[END_REF], that will depend on the nature of the data to study: the created patterns can be a sequence of events, a cluster or a statistical distribution. Statistical methods are fitted with the data in which extreme values are anomalous (the speed for instance), and do not work in the cases where the anomalies are evenly distributed. Neural networks are fitted for the discovery of hidden patterns with complex boundaries but their black box behaviour and their need of a learning phase. The principle of machine learning is to automatically learn complex structures and take data-based decisions. Amongst those methods are the genetic algorithms, Bayesian networks or the clustering.

The distance determination will depend on the type of data and distances such as Euclidian distance in dimension 1 (in the case of speed), Euclidian distance in dimension 2 (in case of localization coordinates with small distance), orthodromic distance (in case of long distance localization coordinates), mean, Hausdorff or Fréchet distances (in the cases of computation of distance between trajectories), or edition distance (in the case of distance with textual data, for the field "destination" for instance). The choice of the right distance for each field is of major importance in the anomaly detection process.

The third step in this anomaly detection is the thresholding for outlier determination in different cases, among which those aforesaid. This will be the purpose of future work.

Conclusion

This paper introduces issues on AIS, the system itself and its vulnerabilities that lead to multiples errors in the messages, falsification and spoofing of them. The spatial characteristics of the messages such as the GNSS coordinates are an important part of falsification, thus the development of an ad hoc methodology is necessary, based on messages integrity assessments and anomaly detection, to discover the falsified messages with the purpose of analysing the data between the raw information stream and the use for diverse purposes by the users.

Figure 1 :

 1 Figure 1: The maritime traffic in Europe (AIS data)

Figure 2 :

 2 Figure 2: Example of a case of compliant report in the Brest harbour, France

Acknowledgments

The research presented in this paper is supported by The French National Research Agency (ANR) and co-funded by DGA under reference ANR-14-CE28-0028, in the frame of the DéAIS project, labelled by French clusters Pôle Mer Bretagne Atlantique and Pôle Mer Méditerranée.