Christophe Nicolle
email: cnicolle@u-bourgogne.fr

Christophe Cruz
email: christophe.cruz@u-bourgogne.fr

Semantic Building Information Model and Multimedia for Facility Management

Keywords: Interoperability, 3D collaborative platform, Industry foundation classes (IFC), Building information modeling (BIM), Semantic web

whether they are published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

For twenty years, the construction sector makes a profound challenge. This is due to several causes such as: evolution of standards, evolution of methodologies and pressure on controlling costs and delays. The building lifecycle management requires the development of a specific environment solving at the same time the problems of syntactic and semantic heterogeneity [START_REF] Keith | Facilities Management, Innovation and Performance[END_REF][START_REF] Barrett | Facilities Management, Towards Best Practice[END_REF]. Moreover, the environment should also allow the required extensibility and the flexibility in order to guarantee the coherent evolution of the collaborative processes developed in this field. The information in an AEC project is generated during all the building lifecycle. It is essential to structure the information in a relevant way for a better management. The activities in an AEC project generate a huge variety of data and information. Consequently, the management and the communication of these data by various participants are complex. The process of information sharing requires a framework in which computer programs can exchange data automatically regardless of the software and data location. Moreover, in this field, the use of tools for 3D visualization of the buildings is crucial. Towards this goal the IAI proposed a standard called IFC that specifies object representations for AEC projects [5]. Industry foundation classes (IFCs) include object specifications, or classes, and provide a structure for data sharing among applications.

From a collaborative point of view the IFCs form the basis of a building description. This basis is enriched during the building's lifecycle with elements related to facilities management: financial data, maintenance rules, evacuation procedures and so on. The quantity of information becomes exponential and then a relevant organization of these elements becomes very complex. Today, "Building Information Modeling (BIM)" is promising to be the facilitator of integration, interoperability and collaboration in the future of building industry. The term BIM has been recently pointed to demarcate the next generation of Information Technologies (IT) and Computer-Aided Design (CAD) for buildings.

The remainder of this paper is structured in 3 parts. The first part presents a brief description of the concept of BIM. The second part presents the principles of our approach using semantic graphs to describe the objects of the building. The third part presents the industrial platform derived from our work and examples to illustrate our point.

Building Information Modeling

The term BIM marks the transition from conventional CAD applications for construction and recent developments in computer science. It is the process of generating, storing, managing, exchanging and sharing building information in an interoperable and reusable way. A BIM system is a tool that enables users to integrate and reuse the information of a building and the domain knowledge throughout the lifecycle of a building [START_REF] Lee | Specifying parametric building object behavior (BOB) for a building information modeling system[END_REF]. A BIM system is a central system that manages various types of information, such as enterprise resource planning, resource analysis packages, technical reports, meeting reports, etc. However, the main feature of a BIM is the 3D modeling system with data management, data sharing and data exchange during the lifecycle of the building. As a matter of fact, a building is composed of geometrical elements which are the basis of a building's design. Furthermore, parametric modeling provides powerful mechanisms that can automate the generation of the building information. Especially those mechanisms, in conjunction with the behavior of building object and an object-based system, facilitate the maintenance and the validity of the building's designs. Several definitions of BIM can be found in the specialized literature. The NBIMS [START_REF]NBIMS: National Building Information Modeling Stan-dard Part-1: Overview, Principles and Methodologies[END_REF] divides BIM categories in three axes which are Product, Collaborative Process and Facility. The Product is an intelligent digital representation of the building. The Collaborative Process covers business drivers, automated process capabilities and open information standards used for information sustainability and fidelity. The Facility concerns the well understood information exchanges, workflows, and procedures which are used by the different teams as a repeatable, verifiable and sustainable information-based environment throughout the building's lifecycle. According to [START_REF]NBIMS: National BIM Standard Purpose[END_REF], a BIM is a computable representation of all the physical and functional characteristics of a building and it is related to the project information, which is intended to be a repository of information for the building owner/operator to use and maintain throughout the lifecycle of the building. According to Autodesk [START_REF]Autodesk White Paper: Building Information Modelling[END_REF], BIMs have three main features: They create and operate on digital databases for collaboration. They manage change through those databases so that a change to any part of the database is coordinated in all other parts. They capture and preserve information for reuse by adding industry-specific applications.

By analyzing the BIM definition we index a set of features common to BIM systems [START_REF] Tolman | Product modelling standards for the building and construction industry: past, present and future[END_REF][START_REF]NIST CIS2 Web Site, Web Site[END_REF][START_REF] Eastman | Deployment of an AEC industry sector product modelo[END_REF][START_REF] Zamanian | A software industry perspective on AEC information models for distributed collaboration[END_REF][START_REF]SABLE Web Site, Web Site[END_REF][START_REF] Cruz | Active3D: Vector of Collaboration, Between Sharing and Data Exchange, INFOCOMP[END_REF][START_REF] Vanlande | IFC and Buildings Lifecycle Management[END_REF]. [START_REF] Klyne | Resource description Framework (RDF): Concepts and Abstract Syntax[END_REF] The main feature of BIM is the ability to store, share and exchange data. Many methods are used to realize those processes like files or databases. Concerning data exchange, BIMs are developed with the aim to keep open non-proprietary data format exchange. (2) Data managed in BIM processes concerns building geometries which are most of the time 3D data. 3D data is more helpful for designers for the visualization of complex construction conditions than 2D while it communicates at the same time design intentions. AEC industry visualizes the design using stereoscopic projection tools to create an immersive experience [START_REF] Campbell | Building Information Modeling: The Web3D Application for AEC[END_REF]. Spatial relationships between building elements are managed in a hierarchical manner. (3) BIMS are data rich and comprehensive as they cover all physical and functional characteristics of a building. BIMs are also rich semantically as they store a high amount of semantic information about building elements. Moreover, the data model is fully object oriented to facilitate data management and process definition. (4) Some of the BIMs are extensible to cover unimplemented information domains. For instance, the development of IFC 2.X went though a major change in order to extend progressively the range and the capability of IFCs by using modules. (5) BIMs play a central role in the building lifecycle. In order to ease data exchange, a data format has to be widely used. By definition, BIMs enable interoperability among diverse applications using a shared universal information standard. [START_REF] Guha | Contexts for the semantic web[END_REF] The lifecycle of the project in AEC is composed of several phases which have to be validated by the corresponding AEC engineering designer. BIMs cover several lifecycle phases. The state of these phases is processed by BIMs in order to sequence and schedule the process. BIMs support 4D analysis, where activities from the project schedule can be simulated and studied to optimize the sequence of construction.

Our research aims at solving the problem linked to the constant IFC evolution (4). The definition of a complete framework that allows to manage knowledge around the building process requires an extensible and generic formalism to represent both specific data describing building information and connected information defined by the user during the building's lifecycle. It requires also tools to handle and query the corresponding modeled data, and it requires also tools to manage the data evolution during the building's lifecycle. Moreover, the contextual management of data that needs to correspond with the user's view and constraints has to be taken into account. It requires also an adaptive graphical 2D/3D representation, dynamically connected with data from buildings according to the BIM features. Finally, the most important point is the fact that the framework has to take into account the constant evolution of specific data describing building information and the corresponding connected information defined by the user during the building's lifecycle. We have developed a method that combines IFC and the various requirements related to facility management.

Overview of Our Approach

In our study context the requirement of the model extensibility and the model evolution generates others difficulties, such as mapping data between two models. Handling information during the building lifecycle requires a contextual and temporal representation of knowledge. It is important to trace each data evolution at a time and to know how to present data according to the user context [START_REF] Guha | Contexts for the semantic web[END_REF][START_REF] Guha | Contexts: A Formalization and Some Applications[END_REF]. To deal with these requirements, we derived Names Graph [START_REF] Carroll | Named Graph. Provenance and Trust[END_REF] in order to complete our framework. Based on the context we developed a system description and operators in an architecture called CDMF that allows dealing with the traceability of the data schema evolution. This innovative approach allows knowing, at any time of the project, the current version of the data schema that defines the facility data.

Our approach considers all requirements at large (temporal management, adaptive view, 2D/3D representation) in order to propose a global solution with a framework based on Semantic Web technologies. To meet these requirements, we have built a complete framework, called CDMF, derived from Semantic Web formalism: RDF, Named Graph, OWL and SWRL. These formalisms constitute the base of our approach. We have extracted from each of them the more adapted features to our problematic. RDF formalism allows data modeling and can be used by operators provided by OWL/SWRL. Finally, Named Graph gives a contextual layer to this unit. To obtain a complete formalism, well adapted to facilities management, we have defined a framework called CDMF which will be presented in the following section.

The CDMF Architecture

The CDMF architecture proposes to use semantic operators in order to manage data in the context of a facility management environment. The objective of CDMF is to join together the semantics of OWL and SWRL in only one formalism. For that DMF defines a whole system of logical operators allowing the description of classes, properties, constraints and of rules. The principal interest of CDMF is to offer a framework facilitating the description of contextual data. This framework offers a single structure that permit us to define a set of data, all types of contexts and the actions that can be realized on these data. CDMF aims at meeting the various needs evoked; moreover, it achieves for the complete system, due to its structure and its operators, a reduction in volume of the data that represents an information system in a collaborative environment, as well as restricted treatments due to the unicity of information. Thus, we used the formalisms of the semantic Web to create an environment meeting in a single way our various needs.

The operators of DMF allow the modeling of knowledge on 3 levels (Table 1): the model level, where DMF makes it possible to define the concepts of modeling (class, property, etc). The diagram level, where DMF allows defining the description of knowledge. The instance level, which makes it possible to define the objects of the real-world according to the structure of the diagram defined in the higher level of abstraction. For each level a set of triplets forms RDF graphs. The architecture of CDMF is based on the structure of modeling RDF. This structure RDF makes it possible to represent knowledge with graphs. These graphs are modeled using a set of triplets. A triplet is composed of a subject, a predicate, and an object. The architecture of CDMF is composed of two layers: "DMF" and "C". The "DMF" layer is composed of the model construction operators and the "C" layer is composed of the context manager operator and the handling graph operator.

The CDMF architecture is made of the space system stack, the API and the engine. This environment allows the creation of specific applications that permit to deal with facility management requirements. The Space System is used to configure the system and to allow data access. It is based on an RDF document. This space system contains a set of graphs called SystemGraph. From this point, the CDMF engine checks the declared graphs and responds to queries executed from the API. The API CDMF is a set of methods used to handle the data system. This API proposes to access data with two main classes called SystemSetGraph and SystemGraph. The first one allows to access the system graph which composes the space system. The second one is made of methods that permit to modify system data. For instance, the method SystemGraph.create() provides the list of Class elements and Property elements which can be created. The CDMF engine is the kernel of the architecture. This engine uses a space system to configure and to know the set of systems to use. The engine contains processes which manage methods of the API CDMF. The engine selects the system graphs in the space system, and creates data, deletes data, etc.

DMF: A Reduced Set of Modeling Operators

This section presents the DMF stack. This stack is made of operators which allow to model information (from simple and monovalued attributes to complex 3D objects) into semantic graphs. This section enables us to show that the formalism that we have defined has a restricted set of operators. We show that these operators can be combined to meet all the needs for semantic modeling defined in the statements. For each operator we give its equivalent in SWRL or OWL.

• dmf:Class defines a class. The equivalent operator in OWL is owl:Class.

• dmf:Property carries out the definition of a property of a Class.

• dmf:Equal defines the equality between two variables. This operator makes it possible to test if two resources are equivalent. • "dmf:Var" makes it possible to define variables used in the logical formulas. Its equivalent is defined in SWRL by the operator "swrl:Variable". • "dmf:Pred1" makes it possible to define unary predicates. Its equivalent is defined in SWRL by "swrl:ClassAtom". • "dmf:Pred2" makes it possible to define binary predicates. The equivalent operators in SWRL are "swrl:IndividualPropertyAtom" and "swrl:DatavaluedPropertyAtom". A binary predicate is a property with a subject and an object. To make the correspondence with RDF, the terms of subject and object are used in order to define the first and last element of a triplet RDF.

Fig. 1. Hierarchy of CDMF operators and properties using Protégé

• "dmf:Equiv" makes it possible to define that two classes are equivalent. The set of the elements of the type A is equivalent to the set of the elements of the type B. The equivalent operator in OWL is "owl:equivalentClass".

• etc .

Context and Mapping Operators

This section presents the operators defined in the stack C of our architecture. These operators are used to handle graphs and to define contexts. With these operators, new graphs can be generated by combination of existing graphs. These operators are commonly used to update the data model definition when a norm in architecture is upgraded. For example, the IFC norm has been updated six times since 2000. The elements defined in this part use the space of name cdmf. For each type of graph we present its definition by using DMF operators, as well as an example of use with the result of the operation carried out on the graphs.

Union Operator. The result of the addition of G1 and G2 is the union of the set of the triplets of G1 and the set of the triplets of G2. Table 2 gives its definition in DMF (Table 2).

Table 2. DMF definition of the union operator

Class(AddGraph) Property(args) args(?x,?y) → AddGraph(?X) ∧ rdf:Bag(?y) args(?x,?y) ∧ rdf:li(?y,?Z) → CdmfGraph(?Z)

The operator of a union of graphs is defined by the class cdmf:AddGraph. It has a property cdmf:args. This property is a list of RDF elements (rdf:Bag) whose elements are graphs. The definition of these elements allows the union of two or several graphs. Table 3 shows an example of a union of graphs as well as the result of the operation.

Table 3. Script defining the union of two graphs G1 and G2

:Ga1 rdf:cdmf type:AddGraph :Ga1 cdmf:args :li1 :li1 rdf:Li :G1 :li1 rdf:Li :G2 :G1{

:b1 rdf:type :Building :e1 rdf:type :Floor} :G2{ G1:b1 G1:contain :e1}

G1 defines two objects b1 and e1 of the Building type and Floor. G2 defines a relation contain between b1 and e1. The resources b1 and e1 in G1 and G2 are the same resources because their URI is identical. Indeed b1 and e1 are defined in G1, their URI is the concatenation of the URI of G1 with b1. In G2, we define the namespace G1 with the URI of G1, therefore G1:b1 and G1:e1 in G2 is the same URI as:b1 and:e1 in G1. The result of the calculation of this combination is presented in Table 4.

Table 4. Script resulting from the union of G1 and G2

:Ga1 { :b1 rdf:type :Building :e1 rdf:type :Floor :b1 contain :e1}

Intersection Operators. The intersection operator can be defined in different manners and can imply a different result according to the type of intersection carried out. The intersection operator is defined by two elements cdmf:InterGraph and cdmf:CompInterGraph. The first element defines a "traditional" intersection. The second element makes it possible to specify on which elements of a triplet the intersection is carried out.

Traditional Intersection. The result of the intersection between G1 and G2 is the set of the identical triplets in G1 and G2 (Table 5). This operator has two properties cdmf:arg1 and cdmf:arg2. These two properties are CdmfGraph types representing the two graphs on which the intersection must be computed. Table 6 defines an intersection between the two graphs G1 and G2. The result of this intersection is the empty set, because the set of triplets is disjoint.

Table 6. Script defining the union of two graphs G1 and G2

:G1{ :b1 rdf:type :Building :e1 rdf:type :Floor} :G2{G1:b1 :contain G1:e1} :Gi1 rdf:cdmf type:InterGraph :Gi1 cdmf:arg1 :G1 :Gi1 cdmf:arg2 :G2

Composed Intersection. The composed intersection makes it possible to determine which part of the triplet is concerned in the calculation of the intersection. In the case of the "traditional" intersection, one carries out the intersection on the set of triplets of each graph (Table 7). Here we can compose the intersection with the various parts of a triplet (subject, object). Below you will find possible combinations of intersections.

-The intersection on the subject in the two graphs. The result of the intersection between G1 and G2 is the set of the triplets whose subjects are identical in G1 and G2. -The intersection on the object in the two graphs. The result of the intersection between G1 and G2 is the set of the triplets whose objects are identical in G1 and G2. -The intersection on the subject of the triplets of a graph with the object of the triplets of the other graph. The result of the intersection between G1 and G2 is the set of the triplets whose subjects of the graph G1 are identical to the objects of the graph G2. -The intersection on the subject or the object. There is a last combination which is actually the addition of two intersections. The result of the intersection on the subject of G1 and the subject or the object of G2 is equivalent to the sum of the intersections on the subject of G1 and G2, and on the subject of G1 and the object of G2. The intersection operator cdmf:CompInterGraph has two properties cdmf:arg1 and cdmf:arg2 which are the two graphs on which the intersection is carried out. It has two additional properties cdmf:on1 and cdmf:on2 respectively defining the two parts of the triplets used to carry out the calculation of an intersection. Table 8 defines a composed intersection between the graphs G1 and G2 previously defined (e.g. Table 3). Table 8. Script defining the composed intersection of two graphs, G1 (on subject part) and G2 (on object part) :Gci2 rdf:cdmf type:CompInterGraph :Gci2 cdmf:arg1:G2 :Gci2 cdmf:on1 'Object' :Gci2 cdmf:arg2:G1 :Gci2 cdmf:on2 'Subject' :Gic2 { :e1 rdf:type :Floor :b1 :contain :e1}

Difference Operator. The difference between two graphs is indicated by the element cdmf:RemoveGraph. The result of the difference between G1 and G2 is the suppression of the set of the triplets of G2 in G1 (Table 9). The class cdmf:RemoveGraph has two properties cdmf:src and cdmf:rem. The second property constitutes the set of the triplets to be withdrawn from the graph indicated by the first argument.

Table 10. Script defining the difference between two graphs, G1 and G2.

:Gr1 rdf:cdmf type:RemoveGraph :Gr1 cdmf:src :G1 :Gr1 cdmf:rem :G2 :G1{ :b1 rdf:type :Building :e1 rdf:type :Floor :b1 :contain :e1} :G2{ :b1 rdf:type :Building} :Gr1{:e1 rdf:type :Floor :b1 :contain :e1}

In this operation, only the identical triplets are a removed graph source.

Mapping Operator. The last type of operation on the graphs is the operation of mapping described by the element cdmf:MapGraph. A graph of mapping is a transformation of a graph into another graph using mapping rules; The mapping operator has two properties cdmf:src and cdmf:map indicating the source graph and the target graph. The result of the operation of mapping is the set of the triplets which is defined by the rules of Gmap. A rule in Gmap is described by an operator of implication. All the triplets of Gsrc are transformed into triplets defined by the rules (Table 12 & 13).

Table 12. Script defining the mapping of graph Gsrc using the rules defined in a graph :Gsrc{ :b1 rdf:type :Building :e1 rdf:type :Floor :b1 :contain :e1} :Gmap{Gsrc:Building(?x) → Gx:Building(?x) Gsrc:Floor(?x)→ Gx:BuildingStorey(?x) Gsrc:contain(?x,?y)→ Gx:relContains(?x)} :Gmap1 rdf:cdmf type:MapGraph :Gmap1 cdmf:src :Gsrc :Gmap1 cdmf:map :Gmap

In this part we have studied five operators which allow to carry out various combinations of graphs. These five operators are the union, the difference, the intersection (traditional and composed) and the mapping. They constitute the first part of the C stack. The second part of the C operators is the definition of a particular graph SystemGraph. This element associates various types of information with a graph. This element is used to represent contexts. Table 13. Script presenting the result of the mapping of the graph G1 previously defined (Table 3) :Gmap1{ Gsrc:b1 rdf:type Gmap:Building Gsrc:e1 rdf:type Gmap:BuildingStorey Gsrc:b1 Gx:relContains Gsrc:e1}

Context Modeling, th

The element cdmf:Syste the contexts with the help with the graphs presented a the set of problems met in f graph, on which a graph da use and actions that can be SystemGraph evokes protégé description of the S For instance, the definiti the composition of a buildi the associated graph and all graph. This data model is d fact, the SystemGraph d reading, writing or deletin authorized on the associated is a list of RDF resources with its properties: cdmf: name space cdmf is used to emGraph uses the mechanism of Named Graphs to def of the properties. The SystemGraph element associa above all useful information which is needed to respond facility management. This element defines the nature of ata model is based. The element also defines the contex realized on this graph. the data model on which the associated graph is built SystemGraph is depicted in figure 2. ion of building X is based on a data model that descri ing. The data model allows to check the data coherence lows to indicate which kind of data can be generated in defined with the help of operators introduced in DMF defines actions that can be undertaken on the graph such ng. This can be done according to the actions which d graph. The description of the context in SystemGra . This section presents the definition of SystemGra model, cdmf:of, cdmf:Action, cdmf:graph. T o present these elements. SystemGraph can be a data model in a certain version or SystemGraph can represent data on a certain date and in a certain language, for a certain user. It can also define the nature of the graph and the conditions that have to be fulfilled in order to be able to access a graph system.

Description of

The property cdmf:Action determines the actions authorized on the graph. It defines the actions of writing, suppression and modification. If no action is associated to the system, this implies that only the visualization of information is possible.

The element cdmf:Action determines which actions are possible, on which part of the data and starting from which model.

An action has one or two properties. If it has only one property add then the addition is allowed. If it has only one property remove then the system allows the deletion of data. If it has the two properties, we can add and remove data in the graph system. An element cdmf:Add defines which information we can add (cdmf:model) and where it has to be added (cdmf:addIn).

The Element cdmf:Remove indicates the suppressible data which have to be removed. If it does not have this property, all the data of the graph of the system can be deleted. The property cdmf:From binds an element of the cdmf:From type. According to the origin of the suppression (cdmf:graph), this element defines the action to be realized: either an addition in a cdmf:RemoveGraph, or a suppression in the graph cdmf:graph.

The property cdmf:graph contains the associated graph representing the data. The associated graph is a cdmf:graph type. SystemGraph has an attribute of the cdmf:graph type. Thus, SystemGraph can refer to all the types of graphs presented in CDMF.

Active3D Facility Server

This section presents the Active3D Facility Server, a web collaborative platform dedicated to the facility management, taking into account all aspects of the building's lifecycle. Due to the lack of space, we will illustrate only our proposal with two examples of use. The first example concerns the initialization of a space system when a facility manager needs to configure the platform. This extension is realized by defining a specific model. This model will be used in the building definition process. The second point illustrates the use of context to display specific information to users.

Configuration of a SpaceSystem

In facility management, various versions of the building can be managed and presented to different actors in many countries. The representation of a building mixes textual and graphic representations. The first step in facility management consists in creating the data model. A building description will be generated starting from this model. The new data model is created from a new applicative environment. An initial space system is created. The graphical representation is given in Fig. 2. specific user. Thus, during the identification protocol, when a user tries to connect himself to the platform, a specific graph is built and a view of a building is built according to its context. Figures 4 and5 show two different views of the building according to the Architect view and the Structure Engineering view respectively.

Conclusions

In this paper we have presented a Semantic Web approach for facility management. This approach allows facility managers to support the building's lifecycle management from the design to the destruction of the building in a collaborative context. Several actors provide and handle building information. This approach is based on a semantic model called CDMF and the IFC 2x3 standard which defines the 3D geometries of the objects of building. CDMF improves data management during the lifecycle of a building. Our proposition, based on graph combinations and the contextual element SystemGraph, addresses the problem of model evolution, of data mapping, of the management of temporal data, and of the adaptation of data according to the use and the user. Our framework facilitates data maintenance (data migration, model evolution) during the building lifecycle and reduces the volume of data. A collaborative Internet platform was developed to support the building's lifecycle. This platform is mainly used to federate all the actions realized on a building during its lifecycle, to merge all information related to these actions in an adaptive hypermedia graph, to extract some trade views of the building by combining information collected during the lifecycle from heterogeneous sources and to handle all these views through a dynamic and adaptive 3D interface. Currently, the Active3D platform supports more than 70 million square meters of building where more than 400 actors from all civil engineering domains collaborate at each step of the building's lifecycle. Semantic management of these millions of object requires some optimizations to reduce the data extraction time from semantic graphs. To meet these new challenges, we are working on a new semantic engine using based technique on the Model Checking. The objective will be the rapid extraction and verification of relevant semantic graphs in different contexts of use.

Fig. 2 .

 2 Fig. 2. D

  SystemGraph into Protégé odel defines the model on which a SystemGra ociated model will be used to define the objects and enerated in the SystemGraph graph. Subsequently, i coherency by comparing it to the model. SystemGra s also a SystemGraph. CDMF defines a cl raph to represent a specific SystemGraph. This type definitions of classes, properties and rules defined cdmf:of defines the subject of the SystemGraph element. This property defines the context. It associates a set of RDF resources which resume what is described by the SystemGraph. For instance, SystemGraph can be the description of a data model in the building field.

Following

  this step, the the possibility to create dat creation of SystemGrap the graph of data. For the SystemModelGraphs" SystemGraph whose cha SystemModelGraph rep resources contains only one For the associated graph contain the definition of the we have based our mod approximately 600 classes model in the application. application (creation of clas Fig. 3 presents a snapsho Building Model by an op operator dmf:Property properties, rules, etc. In thi Building, Floor and Sp

Fig. 3 .Fig. 4 .

 34 Fig. 3. An example of a 3D v DMF operators

Fig. 5 .

 5 Fig. 5. Structural view of a building. This view is required for structure engineers. The corresponding graph provides all elements needed to make structure calculations.

Table 1 .

 1 The 3 levels of the modeling data of DMF

	Model		Schema		Instance
	dmf:Class type dmf:Class	:Building type dmf:Class	:b1 type :Building
	dmf:Property	type	:Storey type dmf:Class	:e1 type :Floor
	rdf:Property		:contains	type	:e2 type :Floor
			dmf:Property		:b1 :contain :s1
					:b1 :contain :s2

Table 5 .

 5 DMF definition of the traditional intersection operator (cdmf:InterGraph operators)

	Class(InterGraph)
	Property(arg1)
	Property(arg2)
	arg1(?x,?y) → CdmfGraph(?y)
	arg2(?x,?y) → CdmfGraph(?y)

Table 7 .

 7 DMF definition of the composed intersection operator (cdmf:CompInterGraph operators)

	Class(CompInterGraph)
	Property(arg1)
	Property(arg2)
	Property(on1)
	Property(on2)
	arg1(?x,?y) → CdmfGraph(?y)
	arg2(?x,?y) → CdmfGraph(?y)
	on1(?x,?y) → Equal(?y,'Subject') ∧ Equal(?y,'Object')
	on2(?x,?y) → Equal(?y,'Subject') ∧ Equal(?y,'Object')

Table 9 .

 9 DMF definition of the difference operator

	Class(RemoveGraph)
	Property(cdmf:src)
	Property(cdmf:rem)
	cdmf:src(?x,?y)→	RemoveGraph(?x)	∧
	CdmfGraph(?y)
	cdmf:rem(?x,?y)→	RemoveGraph(?x)	∧
	CdmfGraph(?y)

Table 11 .

 11 DMF definition of the mapping operator

	Class(MapGraph)
	Property(src)
	Property(map)
	src(?x,?y)→ ΜapGraph(?x)∧ CdmfGraph(?y)
	map(?x,?y)→ ΜapGraph(?x)∧ CdmfGraph(?y)


Alexandre Lung-Yut-Fong

Céline Lévy-Leduc

Olivier Cappé

Distributed detection/localization of change-points in high-dimensional network traffic data *

We propose a novel approach for distributed statistical detection of change-points in highvolume network traffic. We consider more specifically the task of detecting and identifying the targets of Distributed Denial of Service (DDoS) attacks. The proposed algorithm, called DTopRank, performs distributed network anomaly detection by aggregating the partial information gathered in a set of network monitors. In order to address massive data while limiting the communication overhead within the network, the approach combines record filtering at the monitor level and a nonparametric rank test for doubly censored time series at the central decision site. The performance of the DTopRank algorithm is illustrated both on synthetic data as well as from a traffic trace provided by a major Internet service provider.

Introduction

Detecting malevolent behaviors has become a prevalent concern for the security of network infrastructures, as exemplified by the, now common, attacks against major web services providers. In this contribution, we consider more specifically the case of DDoS (Distributed Denial of Service) type of attacks where many different sources transmit data over the network to a few targets so as to flood resources and, eventually, cause disruptions in service.

Several methods for dealing with DDoS attacks have been proposed. They can be arranged into two categories: signature-based approaches and statistical methods. The former operate by comparing the observed patterns of network traffic with known attack templates. Obviously, this methodology only applies for detecting anomalies that have already been encountered and characterized. The second type of approaches relies on the statistical analysis of network patterns and can thus potentially detect any type of network anomalies. The basic statistical modelling for this task is to assume that network anomalies lead to abrupt changes in some network characteristics. Hence, most statistical methods for detection of network anomalies are cast in the framework of statistical change-point detection, which is a familiar topic in statistics, see, e.g., [START_REF] Basseville | Detection of Abrupt Changes: Theory and Applications[END_REF]; [START_REF] Brodsky | Nonparametric Methods in Change-Point Problems[END_REF]; [START_REF] Csörgő | Limit theorems in change-point analysis[END_REF], and references therein.

Two different approaches to change-point detection are usually distinguished: the detection can be retrospective and hence with a fixed delay (batch approach) or online, with a minimal average delay (sequential approach). In the field of network security, a widely used changepoint detection technique is the cumulated sum (CUSUM) algorithm described in [START_REF] Basseville | Detection of Abrupt Changes: Theory and Applications[END_REF] which is a sequential approach. It has, for instance, been used by [START_REF] Wang | Detecting syn flooding attacks[END_REF] and by [START_REF] Siris | Application of anomaly detection algorithms for detecting syn flooding attacks[END_REF] for detecting DoS attacks of the TCP (Transmission Control Protocol) SYN flooding type. This attack consists in exploiting the TCP three-way handshake mechanism and its limitation in maintaining half-open connections. More precisely, when a server receives a SYN packet, it returns a SYN/ACK packet to the client. Until the SYN/ACK packet is acknowledged by the client, the connection remains half-opened for a period of at most the TCP connection timeout. A backlog queue is built up in the system memory of the server to maintain all half-open connections, this leading to a saturation of the server. In [START_REF] Siris | Application of anomaly detection algorithms for detecting syn flooding attacks[END_REF], the authors use the CUSUM algorithm to detect a change-point in the time series corresponding to the aggregation of the SYN packets received by all the requested destination IP addresses. With such an approach, it is only possible to set off an alarm when a massive change occurs in the aggregated series; it is moreover impossible to identify the attacked IP addresses.

Given the nature of a TCP/SYN flooding attack, the attacked IP addresses may be identified by applying multiple change-point detection tests, considering each of the time series formed by counting the number of TCP/SYN packets received by individual IP addresses. This idea is used in [START_REF] Tartakovsky | Detection of intrusion in information systems by sequential change-point methods[END_REF] where a multichannel detection procedure, which is a refined version of the previously described algorithm, is proposed: it makes it possible to detect changes which occur in a channel and which could be obscured by the normal traffic in the other channels if global statistics were used.

When analyzing wide-area-network traffic, however, it is not possible anymore to consider individually all the possible target addresses for computational reasons. For instance, the data used for the evaluation of the proposed method (see Section 3) contain several thousands of distinct IP addresses in each one-minute time slot. In order to detect anomalies in such massive data within a reasonable time span, it is impossible to analyze the time series of all the IP addresses receiving TCP/SYN packets. That is why dimension reduction techniques have to be used. Three main approaches have been proposed. The first one uses Principal Component Analysis (PCA) techniques, see [START_REF] Lakhina | Diagnosing network-wide traffic anomalies[END_REF]. The second one uses random aggregation (or sketches), see [START_REF] Krishnamurthy | Sketch-based change detection: methods, evaluation, and applications[END_REF] and the third one is based on record filtering, see [START_REF] Lévy-Leduc | Detection and localization of change-points in high-dimensional network traffic data[END_REF]. Localization of the anomalies is possible with the second and third approaches but not with the first one. By localization, we mean finding the attacked IP addresses.

In the approaches mentioned above, all the data are sent to a central analysis site, called the collector in the sequel, in which a decision is made concerning the presence of an anomaly. These methods are called centralized approaches. A limitation of these methods is that they are not adapted to large networks with massive data since, in this case, the communication overhead within the network becomes significant. The approach that we propose in this paper consists in processing the data within the network (in local monitors) in order to send to the collector only the most relevant data. These methods are called, in the sequel, decentralized or distributed approaches. In [START_REF] Huang | In-network pca and anomaly detection[END_REF], a method to decentralize the approach of [START_REF] Lakhina | Diagnosing network-wide traffic anomalies[END_REF] is considered but, as previously explained, with such a method localizing the network anomaly is impossible.

The main contribution of this paper is an efficient way of decentralizing the TopRank algorithm introduced in Lévy- [START_REF] Lévy-Leduc | Detection and localization of change-points in high-dimensional network traffic data[END_REF]. The proposed algorithm, termed DTopRank (for Distributed TopRank), uses the TopRank algorithm locally in each monitor and only sends the most relevant data to the collector. The data sent by the different local monitors are then aggregated in a specific way that necessitates the development of a novel nonparametric rank test for doubly censored data that generalizes the proposal of [START_REF] Gombay | A nonparametric test for change in randomly censored data[END_REF]. The DTopRank algorithms makes it possible to achieve a performance that is on a par with the fully centralized TopRank algorithm while minimizing the data that needs to be send from the monitors to the collector.

The paper is organized as follows. In Section 2, we describe the DTopRank method and determine the limit in distribution of the proposed test statistic under the null hypothesis that there is no network anomaly. The performance of the proposed algorithm (implemented in C language) is then assessed both using a real traffic trace provided by a major Internet Service Provider (Section 3) as well as on synthetic data (Section 4). In both cases, DTopRank is compared both to the centralized TopRank algorithm and to a simpler baseline decentralized algorithm based on the use of the Bonferroni correction.

Description of the methods

The raw data that is analyzed consists of flow-level summaries of the communications on the network. These include, for each data flow, the source and destination IP addresses, the start and end time of the communication as well as the number of exchanged packets. All of this information is contained in the standard Netflow format.

Depending on the type of anomaly to be detected, one needs to consider specific aspects of the network traffic. In the case of the TCP/SYN flooding, the quantity of interest is the number of TCP/SYN packets received by each destination IP address per unit of time. We denote by (N i (t)) t≥1 the discrete time series formed by counting the number of TCP/SYN packets received by the destination IP address i in the t-th sub-interval of size ∆ seconds, where ∆ is the sampling period.

The centralized TopRank algorithm analyzes these global packets counts. In our case however, we consider a monitoring system with a set of local monitors M 1 , . . . , M K , which collect and analyze the locally observed time series. As as consequence of decentralized processing, the packets sent to a given destination IP address are not observed at all monitors, although some overlap may exist, depending on the routing matrix and the location of the monitors. We thus denote by N k i (t) the number of TCP/SYN packets transiting to the destination IP address i in the sub-interval indexed by t, as observed by the k-th monitor. In the proposed batch approach, detection is performed from the data observed during an observation window of duration P × ∆ seconds. The goal is to detect change-points in the aggregated time series (N i (t)) t≥1 using only the local time series N k i (t)

t≥1
for each k ∈ {1, . . . , K} and a quantity of data transmitted to the collector that is as small as possible.

The DTopRank method

The DTopRank algorithm operates at two distinct levels: the local processing step within the local monitors M 1 , . . . , M K and the aggregation and global change-point detection step within the collector.

Local processing

The local processing of DTopRank consists of the four steps described below, which are applied in each of the K monitors. The first three steps are similar to the TopRank algorithm applied to the local series of counts N k i (t)

1≤t≤P

. The second and third steps are however modified by introducing a lower censoring value for each analyzed series so as to make possible global aggregation at the collector level. In this section, the superscript k, corresponding to the monitor index, is dropped to alleviate the notations.

Record filtering:

For each time index t ∈ {1, . . . , P}, the indices of the M largest counts N i (t) are recorded and labeled as i 1 (t), . . . , i M (t) to ensure that

N i 1 (t) (t) ≥ N i 2 (t) (t) ≥ • • • ≥ N i M (t) (t).
In the sequel, T M (t) denotes the set {i 1 (t), . . . , i M (t)}. We stress that, in order to perform the following steps, we only need to store the variables {N i (t), i ∈ T M (t), t = 1, . . . , P}.

Creation of censored time series:

For each index i selected in the previous step (i ∈ P t=1 T M (t)), the censored time series is built. This time series is censored since i does not necessarily belong to the set T M (t) for all indices t in the observation window, in which case, its value N i (t) is not available and is censored using the upper bound N i M (t) (t) = min i∈T M (t) N i (t). More formally, the censored time series (X i (t), δ i (t)) 1≤t≤P are defined, for each t ∈ {1, ..., P}, by

(X i (t), δ i (t)) = (N i (t), 1), if i ∈ T M (t) ( min j∈T M (t) N j (t), 0), otherwise.
The value of δ i (t) indicates whether the corresponding value X i (t) has been censored or not. Observe that, by definition,

δ i (t) = 1 implies that X i (t) = N i (t) and δ i (t) = 0 implies that X i (t) ≥ N i (t).
We also define the upper and lower bounds of

X i (t) by X i (t) = X i (t) and X i (t) = X i (t)δ i (t), respectively.
In order to process a fixed number S of time series instead of all those in P t=1 T M (t) (at most M × P), we only build the time series corresponding to the index i in the list i 1 (1), . . . , i 1 (P), i 2 (1), . . . , i 2 (P), i 3 (1), . . . where the indices i k (t) are defined in the previous step.

Change-point detection test:

In Lévy-Leduc and Roueff ( 2009), the nonparametric test proposed by [START_REF] Gombay | A nonparametric test for change in randomly censored data[END_REF] is used for detecting change-points in censored data. Here, this test is extended in order to detect change-points in doubly censored time series so that the same procedure can be applied both in the local monitors and within the collector. This test, described hereafter, is applied to each time series created in the previous stage and the corresponding p-value is computed, a small value suggesting a potential anomaly.

Let us now further describe the statistical test that we perform. This procedure aims at testing from the observations previously built (X i (t), X i (t)) 1≤t≤P if a change occurred in this time series for a given i. More precisely, if we drop the subscript i for convenience in the description of the test, the tested hypotheses are:

(H 0 ): "(X(t), X(t)) 1≤t≤P are independent and identically distributed. " (H 1 ): "There exists some r such that (X(1), X(1)), . . . , (X(r), X(r)) and (X(r + 1), X(r + 1)), . . . , (X(P), X(P)) have a different distribution. "

To define the proposed test statistic, define, for each s, t in {1, . . . , P},

h(s, t) = 1(X(s) > X(t)) -1(X(s) < X(t)) ,
where 1(E) = 1 in the event E and 0 in its complementary set, and

Y s = U s ∑ P t=1 U 2 t , with U s = P ∑ t=1 h(s, t) . ( 1
)
The test statistic is then given by

W P = max 1≤t≤P | t ∑ s=1 Y s | .
The following theorem, which is proved in appendix, provides, under mild assumptions, the limiting distribution of W P , as P tends to infinity, under the null hypothesis and thus provides a way of computing the p-values of the test.

Theorem 1 Let (X, X) be a R 2 -valued random vector such that

P(F(X -) + G(X) = 1) < 1 , ( 2
)
where F is the c.d.f. of X, G the c.d.f. of X and F(x -) denotes the left limit of F at point x. Let (X(t), X(t)) 1≤t≤P be i.i.d. random vectors having the same distribution as (X, X), then, as P tends to infinity,

sup 0≤u≤1 | ⌊Pu⌋ ∑ s=1 Y s | d -→ B ⋆ := sup 0≤u≤1 |B(u)| , ( 3
)
where {B(u) , 0 ≤ u ≤ 1} denotes the Brownian Bridge and d -→ refers to convergence in distribution.

Theorem 1 of this paper thus extends Theorem 1 of [START_REF] Gombay | A nonparametric test for change in randomly censored data[END_REF], where only one-sided censoring was considered and continuity of the random variables was assumed.

Remark 1 Theorem 1 provides a way of controlling the asymptotic false-alarm rate, for large enough observation sizes. The only requirement is (2), which is a minimal condition. In particular, if the random variables X and X both have a continuous c.d.f., (2) holds whenever P(X = X) > 0, that is, when the probability of not being censored is positive. Indeed,

P(F(X) + G(X) = 1) = P({F(X) + G(X) = 1} ∩ {X = X}) + P({F(X) + G(X) = 1} ∩ {X = X}) = P({2F(X) = 1} ∩ {X = X}) + P({F(X) + G(X) = 1} ∩ {X = X}).
Observe that the first probability is smaller than P(2F(X) = 1). Using that F is continuous, F(X) has a uniform distribution on [0, 1] and thus P(2F(X) = 1) = 0. Thus, P(F(X) + G(X) = 1) ≤ P(X = X) = 1 -P(X = X). In practice, the p-values deduced from Theorem 1 are reliable whenever the observation size P is large enough and some non-censored values have indeed been observed. [START_REF] Park | Long-range dependence in a changing internet traffic mix[END_REF] and references therein. However, the assumption here applies to single Origin-Destination flows which, most often, do not exhibit strong autocorrelations; see [START_REF] Susitaival | Characteristics of origin-destination pair traffic in funet[END_REF] for further discussion of this issue.

Remark 2 The i.i.d. assumption in Theorem 1 may seem surprising in light of the ubiquity of long-range dependence phenomenons in aggregated network traffic measurements; see for instance

Remark 3 In practice, the computation of the quantities (∑ t s=1 Y s ) 1≤t≤P can be done in O(P) operations only using the alternate form of U s in term of the empirical cumulative distribution functions of X(t) and X(t) (see Eq. ( 7) in appendix).

Based on (3), we take for the change-point detection test the following p-value: Pval(W P ), where for all positive b (see, for instance, Billingsley, 1968, p. 85),

Pval(b) = P(B ⋆ > b) = 2 ∞ ∑ j=1 (-1) j-1 e -2j 2 b 2 .

Selection of the data to be transmitted to the collector:

We select in each monitor M k the d censored time series having the smallest p-values and send them to the collector. Thus, the collector receives at most d × K censored time series, instead of ∑ K k=1 D k , where D k is the number of destination IP addresses seen by the kth monitor, if a centralized approach was used.

Aggregation and change-point detection test in the collector

Within the collector, the lower and upper bounds of the aggregated time series (Z i (t), Z i (t)) 1≤t≤P associated to the IP address i are then built as follows:

Z i (t) = ∑ k∈K X (k) i (t) and Z i (t) = ∑ k∈K X (k) i (t) , (4)
where (X (k) i (t), t = 1, . . . , P) and (X (k) i (t), t = 1, . . . , P) are the time series associated to the IP address i computed by the monitor M k , and K is the set of monitors which have transmitted series pertaining to the IP address i. Then, the test described in step 3 of the local processing is applied to the time series (Z i (t), t = 1, . . . , P) and (Z i (t), t = 1, . . . , P). An IP address i is thus claimed to be attacked at a given false alarm rate α ∈ (0, 1), if Pval(W P ) < α, and the change-point time is estimated with r = arg max 1≤t≤P | ∑ t s=1 Y s |. As noted in Remark 1 above, Theorem 1 may be safely applied to the aggregated time series (Z i (t), Z i (t)) as long as they are not fully censored. By definition, the aggregated series is more censored than the individual series (X

(k) i (t), X (k) i (t)
) detected at monitor level. On the other hand, for a given address i, only the series that are among the d series having the smallest p-values at the monitor level are aggregated at the collector level. Hence, the collector usually aggregates strictly less than K series and only aggregates potentially significant series. In the experimental conditions described in Sections 3 and 4 below (d ranging from one to five, P = 60 and M = 10), the average number of uncensored values in the aggregated series is 18.7 (out of 60) and the average rate of completely censored time series is equal to 0.62%. The parameter that has the largest influence on these values is the depth M of the record filtering buffer: increasing M reduces censoring (for M = 20, the proportion of uncensored data in the aggregated series raises up to 31.2 out of 60 and the average rate of completely censored time series is equal to 0.017%), on the other hand, the required memory and computation time for the record filtering step are both increasing with M. Hence, M = 10 represents a good tradeoff -see also Section 4 for further discussion.

The BTopRank method

In the sequel, the DTopRank algorithm is compared with a simpler approach using, instead of the aggregation step, a simple Bonferroni correction of the p-values determined in each monitor. More precisely, in BTopRank an IP address is claimed to be attacked at the level α ∈ (0, 1) within the collector if at least one local monitor has computed a p-value smaller than α/K, namely if K(inf 1≤k≤K Pval k ) < α, Pval k being the p-value computed in the monitor k.

Application to real data

This section summarizes the results obtained by the DTopRank and BTopRank algorithms applied to an actual Internet traffic trace provided by a major Internet service provider.

Description of the data

We consider the data used in Section 4 of [START_REF] Lévy-Leduc | Detection and localization of change-points in high-dimensional network traffic data[END_REF], which corresponds to a recording of 118 minutes of ADSL (Asymmetric Digital Subscriber Line) and Peer-to-Peer (P2P) traffic to which some TCP/SYN flooding type attacks have been added. As this data set does not contain full routing information, it has been artificially distributed over a set of virtual monitors as follows: the data is shared among K = 15 monitors by assigning each source destination pair (source IP address, destination IP address) to a randomly chosen monitor; a single monitor thus records all the flows between two particular IP addresses. The experiments reported below are based on 50 independent replication of this process. Finally, the existing anomalies have been down-sampled (by randomly dropping packets involved in the attacks) to 12.5 and 25 packets/s, respectively, to explore more difficult detection scenarios.

Figure 1-(a) displays the total number of TCP/SYN packets received during each second by the different requested IP addresses. The number of TCP/SYN packets received by the four attacked destination IP addresses are displayed in (d) (12.5 packets/s case). As we can see from this figure, the first attack occurs at around 2000 seconds, the second at around 4000 seconds, the third at around 6000 seconds and the last one at around 6500 seconds. These attacks produce The attacked IP addresses (bottom part of Figure 1) are completely hidden in the global TCP/SYN traffic (top part of Figure 1) and thus very difficult to detect. Note also that 1006000 destination IP addresses are present in this data set, with an average of 15000 destination IP addresses in each of the 118 one-minute observation windows. Hence, real time processing of the data would not be possible, even at the monitor level, without a dimension reduction step such as record filtering.

Performance of the methods

In what follows, the DTopRank algorithm is used with the same parameters as those adopted in Lévy-Leduc and Roueff (2009) for the TopRank algorithm, with one-minute windows divided in P = 60 subintervals of ∆ = 1 s, with M = 10 and S = 60. The parameter d was set to d = 1, due to the limited number of attacks expected in each one minute window. In setting P and ∆ the main concern is the overall observation duration ∆ × P which should be sufficient to allow for meaningful statistical decisions while ensuring an acceptable detection delay and that the extracted series can still be considered as stationary in the absence of change. Note that the computational cost of the procedure also scales proportionally to P. The influence of the other parameters (d, M and S) is discussed at the end of Section 4.2.

Figure 2 and 3 show the benefits of the aggregation stage within the collector of the DTopRank algorithm with respect to the use of the simple Bonferroni correction in the BTopRank algorithm. Figures 2-(a),(b) and (c) display the time series (X(t), t = 1, . . . , P) and (X(t), t = 1, . . . , P) associated to an attacked IP address in three different monitors as well as the corresponding p-values. Figure 2-(d) displays the aggregated time series (Z(t), t = 1, . . . , P) and (Z(t), t = 1, . . . , P), as defined in (4), as well as the associated p-value. Note that the aggregated time series corresponds to the aggregation of 11 time series created by 11 different monitors where the attacked IP address has been detected. The p-value of the aggregated time series is much smaller than the ones determined at the local monitors, which enables the detection of an attack which would be difficult to detect within the local monitors. The DTopRank provides smaller p-values than the Bonferroni approach for IP addresses that were really attacked and p-values of the same order as inf 1≤k≤K Pval k for the other IP addresses.

10 -12 10 -11 10 -10 10 -9 10 -8 10 -7 10 -6 10 -5 10 -4 10 -3 10 -2 10 -1 PvalDTop 10 -10 The DTopRank and BTopRank algorithms are further compared in Figure 4 which displays the ROC curves obtained using these two methods with 50 Monte-Carlo replications in two different cases. The bottom plot deals with attacks having an intensity of 12.5 SYN/s. In the other situation, the attacks are the same except that their intensity is 25 SYN/s. For comparison purpose, the ROC curve associated to the non distributed TopRank algorithm is also displayed in both situations. Figure 4 shows that for the 25 SYN/s-attacks, the three methods give similar results. However, in the most difficult case of the 12.5 SYN/s-attacks, the DTopRank algorithm outperforms the BTopRank algorithm.

Thus, DTopRank performs very similarly to the centralized algorithm, especially in the range of interest where the false alarm rate is about 1e-4 (recall that there are about 15000 different IP addresses in each one minute window). The quantity of data exchanged within the network is however much reduced as the centralized algorithm needs to obtain information about, on average, 34000 flows per minute whereas the DTopRank algorithm only need to transmit the d upper and lower censored time series from the monitors to the collector. For d = 1 and K = 15, this amounts to 1800 scalars that need to be transmitted the collector, versus 34000 × 5 (start and end time stamps, source and destination IP, number of SYN packets for each flow) for the centralized algorithm, resulting in a reduction of almost two orders of magnitude of the data that needs to be transmitted over the network.

Application to synthetic data

In this section, we provide results obtained on simulated data with two specific goals in mind. First, the the traffic trace used in Section 3 contains generated attacks but is not fully labeled. Hence, it could be the case that non-labeled anomalies are already present in the background ADSL and P2P traffic contributing to a slight overestimation of false alarms (see [START_REF] Lévy-Leduc | Detection and localization of change-points in high-dimensional network traffic data[END_REF]. Second, the random decentralization approach used in Section 3 does not necessarily correspond to a realistic network topology. In this section, we thus consider synthetic high-dimensional data corresponding to an idealized minute of traffic containing a single anomaly, as measured by 15 monitors randomly positioned on a plausible network topology.

Description of the data

A network topology is generated in which synthesized traffic between hosts located in the nodes of that network is injected. We first generate an Erdős-Rényi random graph [START_REF] Erdős | On random graphs[END_REF]) with 15 nodes and a probability of edge creation of 0.15. The generated graph is displayed in Figure 5. It is similar in terms of number of nodes or nodes degrees to the Abilene network, which has been widely considered in the context of network anomaly detection, see [START_REF] Lakhina | Diagnosing network-wide traffic anomalies[END_REF] and [START_REF] Huang | In-network pca and anomaly detection[END_REF]. This graph has been generated once and is used for all replications of the Monte-Carlo simulations that will follow. For each Monte-Carlo replication, a node of the graph is randomly assigned to each of the D = 1000 IP addresses and K = 15 monitors are also randomly positioned on 15 of the 24 edges of the graph, see Figure 5.

Figure 5: Generated graph: nodes are displayed with circled numbers and monitors with colored boxes.

Using the shortest path [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF] algorithm, the routes between each node of the network are computed, that is the lists of edges of the graph that form the path between the nodes. These routes are used to determine which monitors will see the traffic between two hosts. Note that in our procedure, we have deliberately not considered network links capacity, that would otherwise imply some more sophisticated dynamic routing algorithms, which is beyond the scope of this contribution.

The traffic injected in this network is generated as follows. For a given Source-Destination IP address pair (i, j), we follow Lévy-Leduc and Roueff (2009) and model the SYN packet traffic using a Poisson point process with a given intensity θ i,j , expressed as the number of SYN packets received by j per sub-interval of the observation window. In Network applications, different Source-Destinations pairs exchange a very different amount of traffic. Hence we shall use different intensities for each pair of hosts. To take into account this diversity, we propose using the realizations of a Pareto distribution for the parameters of the different intensities so that a lot of machines receive a small number of SYN packets while a few receive a lot. Note that [START_REF] Nucci | The problem of synthetically generating IP traffic matrices: initial recommendations[END_REF] similarly use a heavy-tailed distribution to generate network traffic.

We first randomly generate a sequence (µ k ) 1≤k≤N of intensities with the Pareto distribution having the following density: γα/(1 + γx) 1+α , when x > 0, with α = 2.5 and γ = 0.72, which roughly corresponds to what we observed in the (centralized) real traffic traces used in Section 4. The parameters µ k are assumed to be sorted as follows:

µ 1 ≥ • • • ≥ µ N .
Here, (X i,j (t)) 1≤t≤P correspond to the number of SYN packets sent by i and received by j in each of the P sub-intervals of the observation window, where i, j are in {1, . . . , D}. Among these N time series, N a of them correspond to the traffic received by the attacked destination IP address j 0 , which is assigned to a fixed location, in node 7, at the "edge" of the network (see Figure 5). This traffic, which is sent by source IP addresses i belonging to a randomly chosen subset I a of {1, . . . , D}, is generated as follows:

∀i ∈ I a , (X i,j 0 (t)) 1≤t≤τ iid ∼ Poisson(θ i,j 0 ) , and ∀i ∈ I a , (X i,j 0 (t))

τ<t≤P iid ∼ Poisson(ηθ i,j 0 ) ,
where η is a positive number which modulates the change intensity, τ is the change-point instant and (θ i,j 0 ) i∈I a are chosen in (µ k ) 40N a ≤k≤41N a . (θ i,j 0 ) i∈I a are thus chosen around 0.6 (0.4-quantile of the Pareto distribution with parameters α and γ, whose mean is about 0.93). Hence, the attack to be detected consists of a multiplicative increase in intensity of N a attacker sources, whose intensity is otherwise in the bulk of the distribution of the intensity (close to the 0.4quantile). The remaining background traffic is generated as:

∀i ∈ {1, . . . , D}, j = j 0 , (X i,j (t))

1≤t≤P iid ∼ Poisson(θ i,j ) ,
where (θ i,j ) i∈{1,...,D},j =j 0 are chosen randomly in the remaining values of

µ k : (µ k ) k / ∈[40N a ;41N a ] .
In the experiments below, N = 10100, N a = 100, P = 60, τ = 30 and we consider different values for the parameter η (1.2, 1.5) in order to modulate the detection difficulty. Results presented in Figures 6 to 7 correspond to the case where d = 1 and the influence of d on the performance is discussed in the final paragraph of Section 4.2. With these settings, the DDoS-type attacks against j 0 are generated by a large number N a of source hosts coming from all routing nodes in in the network. Hence, these attacks can be locally (within a monitor) very difficult to distinguish from the background traffic, as can be seen in Figure 6: It displays for each monitor, when η = 1.5, an example of the time series formed by the number of packets received by the first ("×") and 10th ("•") most solicited destination IP address at each sub-interval as well as the time series of the attacked address j 0 ("⊲"). The monitors that have not detected any traffic directed to j 0 were omitted. In (d), (e) and (i), j 0 is detected by the monitor, but the number of packets is never high enough to be selected by the record filtering step and to appear in {T M (t), t = 1, . . . , 60}. Hence in these monitors, no change detection test is performed for j 0 . In the other six figures, all steps of the TopRank algorithm are carried out since the number of packets sent to j 0 is high enough. A special case is shown in (a), which displays the time series in the monitor located on the edge between nodes 10 and 7, see Figure 5, which is the link where all the traffic directed to the attacked IP address j 0 appears.

Performance of the methods

The two methods described in Section 2 are compared by computing their false alarm and detection rates when tested on 1000 Monte-Carlo replications of the synthetic data described in Section 4.1. The left plot of Figure 7 displays the corresponding ROC curves for different values of η (1.2 and 1.5); the solid and dashed lines show the results of the DTopRank and BTopRank algorithms, respectively.

For larger values of η (1.5), both methods perform very well, with a few missed attacks for a low false alarm rate. DTopRank yields slightly better results than the other method. For η = 1.2 for which attacks are more difficult to detect, the detection performance is naturally lower for both algorithms; the toll is however heavier on BTopRank than on DTopRank.

We observed that the detection performance was improved for Monte Carlo runs in which a monitor is assigned to the 7-10 edge of Figure 5. Indeed in this case, at least a monitor has access to all the traffic sent to the attacked IP address sitting at node j 0 = 7. The right plot of Figure 7 corresponds to the case where this configuration is avoided in the Monte Carlo simulation, which gives some idea of the significance of the phenomenon. For a given monitor topology, the detection performance is thus better for target addresses located at the edge of the network, behind a monitor. In the opposite case however, the detection performance is still appreciable due to the aggregation, at the collector level, of the information sent by the monitors.

We now consider the influence of the parameter d on the performance of DTopRank. The proposed algorithm has been shown to reveal attacks which are not locally detectable. Indeed, the statistical performance of the DTopRank algorithm is close to that achieved by the fully centralized detector but with a greatly reduced communication overhead. An additional interesting feature of the proposed aggregation and detection mechanism is the fact that it operates similarly at the monitor and collector level. Hence, the test could also be applied hierarchically, with tree structured monitors, so as to produce decisions corresponding to groups of monitors of different granularity in the network.

A Appendix

A.1 Proof of Theorem 1

The following proof is based on (Billingsley, 1968, Theorem 24.2), which asserts that if ξ 1 , . . . , ξ n are exchangeable random variables (each permutation of the set of variables has the same joint distribution) and satisfy, as n → ∞,

n ∑ i=1 ξ i p -→ 0, n ∑ i=1 ξ 2 i p -→ 1, max 1≤i≤n |ξ i | p -→ 0 , (5)
then {∑ ⌊nt⌋ i=1 ξ i , 0 ≤ t ≤ 1} d -→ {B(t) , 0 ≤ t ≤ 1}, as n → ∞, where B is a Brownian bridge. We apply this theorem to the random variables Y 1 , . . . , Y P , defined in (1), which are exchangeable since (X(i), X(i)) 1≤i≤P are i.i.d random vectors. Let us now check the three conditions in (5). By the anti-symmetry of the kernel h, To check the third condition, denote by F P (resp. G P ) the empirical c.d.f. of X(1), . . . , X(P) (resp. X(1), . . . , X(P)): 1(X(i) > X(j)) -1(X(i) < X(j))

= F P (X(i) -) -{1 -G P (X(i))} = F P (X(i) -) -G P (X(i)) , (7)

Figure 1 :

 1 Figure 1: Number of TCP/SYN packets globally exchanged (top) and received by the 4 attacked IP addresses (bottom) in the original data (a,d) and within two particular monitors (b, c, e, f). Note that the scale of the bottom figures is divided by 20 with respect to the top ones.

Figure 2 :

 2 Figure 2: (a), (b), (c): times series (X(k) i (t), t = 1, . . . , 60) and (X (k) i (t), t = 1, . . . , 60) displayed with ('x') and ('o') respectively, for 3 different values of k, (d): (Z i (t), t = 1, . . . , 60) and (Z i (t), t = 1, . . . , 60) displayed with ('x') and ('o') respectively.

Figure 3

 3 Figure 3 displays on the x and y-axes the quantities Pval DTop and Pval BTop , respectively. For a given IP address, Pval DTop corresponds to the p-value computed with the DTopRank and Pval BTop is obtained by applying the Bonferroni correction to the p-values transmitted by the monitors.The DTopRank provides smaller p-values than the Bonferroni approach for IP addresses that were really attacked and p-values of the same order as inf 1≤k≤K Pval k for the other IP addresses.

Figure 3 :

 3 Figure 3: (Pval DTop , Pval BTop ) displayed with ('.') except for the ground-truth attacked IP addresses which are displayed with ('•').

Figure 4 :

 4 Figure 4: ROC curves for the DTopRank, BTopRank and TopRank algorithms for attacks having intensities of 25 SYN/s (top) and 12.5 SYN/s (bottom).

Figure 6 :

 6 Figure6: Time series formed in 9 monitors by the number of packets received by the first ("×") and 10th ("•") most solicited destination IP address at each sub-interval, as well as the time series of the attacked address j 0 ("⊲").

Figure 7 :

 7 Figure7: Left: ROC curves for DTopRank (solid lines) and BTopRank (dashed lines), for η = 1.2 ("•"), 1.5 (" "). Right: similar simulation when forbidding the 10-7 edge from the monitors.

  j) = 0 , which gives the first condition of the theorem. The second one follows from the definition of Y i :

F

appears to provide the best tradeoff, even in cases where the actual number of attacks to be detected per window is larger than 5. This behavior can be explained by the observation that the traffic directed towards a particular attacked IP address is not always visible by all local monitors. We have also investigated how the parameters M and S (see Section 2.1.1) affect the performance of the DTopRank algorithm. Figure 9 shows the impact of M while keeping S constant to the value of 60; both the number of attacks per observation window and the parameter d were set to 5. Similar experiments, whose results are not reported here, have also shown that changing S to values of 30 or 120 does not affect at all the ROC curves. From Figure 9, one can observe that larger values of M consistently yield improved results, which is related to a lower censorship. Recall however that both the computational cost and the memory footprint within each monitor are proportional to M. Hence, the choice of M results from a tradeoff between performance and memory or CPU-consumption. The absence of influence of S may be explained by the fact that only d values are sent to the central collector by the monitor. It suffices that S be much larger than d and of the order of P so as to record all the "heavy hitters" that correspond to the largest N i (t), for all t ∈ {1, . . . , P}.

Conclusion

In this paper, we proposed a distributed method for detecting and localizing DDoS attacks in Internet traffic. With this approach, a local processing based on a record filtering technique fol-where G P (•) = 1 -G P (•). Then, using the Glivenko-Cantelli Theorem (van der Vaart, 1998, Theorem 19.1), we get, as P tends to infinity, that

.

By the law of large numbers and our assumption in (2), we obtain, as P tends to infinity, that

Using ( 7), P -1 |U i | ≤ 2, i = 1, . . . , P, and thus

, i = 1, . . . , P .

By (8), Y i satisfies the third condition of (5), which completes the proof.