Rafiq Sekkal

Clement Strauss

François Pasteau

Marie Babel

Olivier Deforges

Fast pseudo-semantic segmentation for joint region-based hierarchical and multiresolution representation

Keywords: Image segmentation, spatial scalability, hierarchical segmentation, RAG

In this paper, we present a new scalable segmentation algorithm called JHMS (Joint Hierarchical and Multiresolution Segmentation) that is characterized by region-based hierarchy and resolution scalability. Most of the proposed algorithms either apply a multiresolution segmentation or a hierarchical segmentation. The proposed approach combines both multiresolution and hierarchical segmentation processes. Indeed, the image is considered as a set of images at different levels of resolution, where at each level a hierarchical segmentation is performed. Multiresolution implies that a segmentation of a given level is reused in further segmentation processes operated at next levels so that to insure contour consistency between different resolutions. Each level of resolution provides a Region Adjacency Graph (RAG) that describes the neighborhood relationships between regions within a given level of the multiresolution representation. Region label consistency is preserved thanks to a dedicated projection algorithm based on inter-level relationships. Moreover, a preprocess based on a quadtree partitioning reduces the amount of input data thus leading to a lower overall complexity of the segmentation framework. Experiments show that we obtain effective results when compared to the state of the art together with a lower complexity.

INTRODUCTION

Image segmentation is a fundamental process in many image, video and computer vision applications. Image segmentation is used to partition an image into separate regions, according to a dedicated homogeneous criterion (texture, colors, gradient...) so that to reach a given level of granularity (regions, objects). [START_REF] Lucchese | Color image segmentation: A State-of-the-Art survey[END_REF] Segmentation techniques generally suffer from high computational complexity as they typically process full resolution images. In this article, we propose to use a simplified version of the image so that to achieve faster segmentation solution. To this aim, a quadtree-based partitioning process is applied, leading to a non uniform subsampled image representation. Moreover, our segmentation performs both multiresolution and hierarchy scalability, as shown on figure 1. Multiresolution representation consists of representing a given image as a set of images at different levels of resolution. In this image representation, the segmentation process is typically based on Top-down approaches. In the literature, multiresolution segmentations rely on regular pyramids. [START_REF] Kropatsch | Multiresolution image segmentations in graph pyramids[END_REF][START_REF] Vantaram | An adaptive and progressive approach for efficient gradient-based multiresolution color image segmentation[END_REF][START_REF] Stojmenovic | Colour and texture based pyramidal image segmentation[END_REF] The relationships and properties between pixels from different levels of representation are thus preserved. As for region-based hierarchical representations they rely on a bottom-up approach: seeds are first created then the number of regions is progressively reduced. Hierarchical segmentations are classically represented by irregular pyramids. [START_REF] Kropatsch | Vision pyramids that do not grow too high[END_REF][START_REF] Mignotte | Mds-based multiresolution nonlinear dimensionality reduction model for color image segmentation[END_REF] Semantic or pseudo-semantic region extraction takes advantage of multiresolution representation in terms of region definition at the expense of the computational complexity. Then an effective tradeoff should be found so that to obtain both content compliant representation and a fast segmentation solution.

This paper is organized as follow: section 2 describes quadtree partitioning which is the key data structure and the regular image pyramid construction driven by the quadtree. Section 3 presents the global JHMS framework including the description of the multiresolution RAG on which inter and intra level region links rely. In section 4, experiments on Berkeley benchmark and obtained results are discussed.

RESOLUTION SCALABLE REPRESENTATION

In this section, we describe the preprocess steps involved in JHMS technique, i.e. the structure of the quadtree and the multiresolution pyramid.

The quadtree represents the key acceleration mechanism of our algorithm. The goal of the quadtree is to partition the image in order to reduce the processing space while preserving the semantic content of the image.

The quadtree corresponds to a block-based partition that depends on local cues of the image. With a top-down approach, each node that does not respect a given homogeneity criterion is decomposed into four sub-blocks. Figure 2 shows different decomposition steps of the quadtree. A block based image is then built following the quadtree partitioning where each block of the image corresponds to the local block mean value.

The resolution scalable representation is obtained by building a multiresolution pyramid that uses the block based image at different levels of resolution. At each level, the image is then composed of blocks of different sizes according to the quadtree partition. Let Res l be the block image at the l th resolution level of the pyramid.

JHMS FRAMEWORK

In this section, we introduce the general JHMS framework. First we present the general principles of the segmentation technique. Secondly, we focus on the multiresolution Region Adjacency Graph (RAG) process.

Finally hierarchy is considered.

General principles

The JHMS technique relies on an iterative process of the pyramid until reaching the desired level of resolution lmin. As described in figure 3, an initialization process from the low resolution image is first required.

Let RAG l be the Region Adjacency Graph at resolution level l, with l ∈ {lmax, . . . , lmin}. Regions of the initial RAG lmax correspond to the blocks of the lowest resolution image. Then, a hierarchical segmentation modifies the RAG lmax by including hierarchical description.

Iteratively, for each level l of the pyramid, the current RAG l is obtained by projecting the RAG l+1 onto the RAG l resolution. RAG l is then updated by taking into account both the projected RAG l+1 and changes within neighborhood relationships. Finally, a hierarchical segmentation is performed onto the current RAG l .

Pyramidal representation Pyramidal representation

RAG Initialization

Resolution

Multiresolution RAG

Figure 4 depicts the different steps of the multiresolution RAG algorithm. To project RAG l+1 onto RAG l across resolution, the algorithm projects the regions labels by using the quadtree partition. Indeed it is used as a reference to decide which blocks are kept unchanged and which ones are split. Thus regions composed of at least one unchanged block are considered as fixed regions, and are directly projected in the current level. Labels of fixed regions are maintained for the next segmentation step. Inheriting labels ensures the label consistency of the segmentation. Unchanged blocks correspond to leaves of the quadtree. Thus if an unchanged block is detected at l th level, it means that 2 l+1 pixels in the full resolution will be discarded from the computation. Consequently, the computation is reduced thanks to quadtree partitioning.

Region relationships between two successive levels are shown in figure 4. Two kinds of region relationships are obtained: regions created in RAG l with blocks from the same region in the RAG l+1 (Figure 4

Hierarchical segmentation

An Extension to hierarchical representation at each level of multiresolution can be designed to overcome the natural resulting over-segmentation by selecting the segmentation granularity. This global solution called Joint Hierarchical and Multiresolution Segmentation (JHMS) provides a highly scalable region representation.

EXPERIMENTS AND RESULTS

Region merging criteria

The proposed algorithm combines two criteria. The first criterion is the difference between the mean values of two adjacent regions. The second criterion computes the gradient between blocks along the shared contour between two regions. For our experiments, we used the Locally Adaptive Resolution structure to build the quadtree and the hierarchical segmentation function. [START_REF] Déforges | Color LAR codec: a color image representation and compression scheme based on local resolution adjustment and self-extracting region representation[END_REF] Although a learning step is recommended to find the optimal set of parameters, they have been empirically tuned relying on experiments when trying to get effective results.

Visual results

In Figure 5, resulting segmented images are shown. Regions are here presented in false color. From the left to the right, original image is first presented, then the corresponding oversampled image of labels at different resolution levels (i.e. 3, 2, 1). As can be observed, results at this resolution are satisfactory in terms of representation. In addition, the consistency of region labels is well preserved across resolutions, so that object tracking can be envisaged throughout the multiresolution. Furthermore, color gradated regions such as the sky of the first image are well detected as a single region thanks to the local gradient feature.

Objective quality of segmentation

In order to compare the proposed algorithm with the literature, obtained segmentation maps are tested against the Berkeley benchmark 8 . This benchmark is usually used for comparing contour detector algorithms. Contour maps are thus compared with contour maps designed by human beings which are then considered as ground truth. In our experiment the BSDS300 dataset is used.

The proposed algorithm is strictly based on local gradient and mean merging criteria. To provide a fair comparison, only color-based contour detectors, from the Berkeley benchmark, that share the same features have been compared. The algorithm results have been then compared with ground truth images. As shown in table 1, JHMS obtained F=0.60 score. As for it, GPB 9 (Global Probability of Boundary) combines the use of local information derived from brightness, color, and texture signals to produce a contour detector. It provides the best performance on the benchmark with F=0.70. CG 10 (Color Gradient), algorithm based on same features as the JHMS provides a score of F=0.57. JHMS provides a pseudo semantic segmentation and is not able to reach object level granularity by itself. Typically, the difference of score with GPB is due to the fact that additional texture information are used in the GPB segmentation. Texture improves the segmentation results, however, extracting texture features makes the algorithm more computationally complex.

Algorithms

Ground Truth GPB CG JHMS Scores Average 0.79 0.70 0.57 0.59 In figure 6, different contour maps are presented from GPB, CG and JHMS techniques. Most of contours in JHMS are similar to those found in the ground truth images. Neither global information nor texture features are used in JHMS. In consequence, any strong brightness or color variations within a single object lead to oversegmentation, thus penalizing the score of our algorithm. For example, to segment the tiger in the last row of figure 6, hand segmented images consider the whole tiger as a single region and one consistent contour. With the proposed algorithm, the tiger is detected as multiple adjacent regions corresponding to the stripes of the skin.

Multiresolution and quadtree partitioning influence on complexity and objective scores

In order to exhibit the influence of the quadtree partitioning and the influence of the multiresolution scalability on the computational complexity and objective scores, segmentations in different configurations have been performed on the BSDS300 dataset images. Results are here obtained using an Intel Core i7 @2.67GHz with a single thread. The average time of segmenting the 100 images of the dataset and mean scores of Berkeley benchmark have been measured.

First the influence of the quadtree partitioning is evaluated without multiresolution. Segmentations are directly performed on the full resolution image, either on pixel based images or on block based images following the quadtree partitioning. Table 2 shows that the quadtree partitioning enables a 5.5 times speed up compared to the pixel based images. In addition the objective score with quadtree partitioning is better. This can be explained by the fact that the quadtree helps by guiding the segmentation algorithm in the image by providing a first pseudo semantic description.

Secondly the multiresolution segmentations are compared with an increasing number of resolution levels. Table 2 depicts the results of our experiments with segmentations performed without multiresolution, and with up to 4 levels of embedded resolution levels. Objective scores remain almost identical when increasing the number of resolution levels and remain close to the performances of the segmentations without multiresolution. However, using multiresolution, scalability strongly impacts the complexity. Complexity comes from both the RAG projection from one resolution level to the next and the segmentation itself at one level of resolution. With more levels of resolution the segmentation at each resolution level is simplified, therefore, more levels tend to reduce the overall complexity. As for the RAG projection mechanism, its complexity is proportional to the number of blocks. From the half resolution up to the full resolution, the RAG projection handles much more small blocks than during other previous projection steps. Therefore, the last RAG projection onto the full resolution level explains for the most part the complexity of the method. Future plans are to optimize the RAG projection and reduce the overall complexity.

CONCLUSION

We present in this paper a fast segmentation method characterized by both multiresolution and hierarchical scalability. At each level, we apply a region merging approach. In the meantime, we construct a hierarchical RAG. Through the successive levels of resolution, the label consistency is insured by the dedicated RAG projection mechanism. As our approach relies on a quadtree structure, thus simplifying the image, our approach exhibits a low computational complexity. Results obtained by the proposed algorithm are effective when considering the limited amount of information used as input. Regions remain coherent with the original image content. Contours are well detected, leading to an efficient pseudo-semantic representation. Future works will be performed to improve the objective results, in order to find the optimal set of parameters.

In particular, a statistical study has to be performed on the learning set of the Berkeley dataset.

Figure 1 .

 1 Figure 1. Multiresolution and hierarchical segmentation representations

Figure 2 .

 2 Figure 2. Quadtree construction on the first frame of hall in cif (352x288) resolution using 5 levels of multiresolution. a) The original image, b) c) d) e) f) quadtree representations

Figure 3 .

 3 Figure 3. JHMS general scheme

Figure 4 .

 4 Figure 4. Inter-level regions relationships. Four regions in Res l , in a) regions are composed with blocks of the same region parent. However in b) there is one region composed from blocks belonging to the two regions parents

Figure 5 .

 5 Figure 5. Scalable segmentation results

Figure 6 .

 6 Figure 6. Image Boundaries, from the left: ground truth, Global Probability of Boundary GPB, Color Gradient (CG) and our algorithm JHMS

Table 1 .

 1 Quantitative scores on Berkeley database BSDS30

Table 2 .

 2 Multiresolution and quadtree partitioning influence on complexity and objective scores

	Multiresolution	none	none	2 levels 3 levels 4 levels
	Quadtree partitioning	no	yes	yes	yes	yes
	BSDS300 scores	0.58	0.60	0.575	0.577	0.578
	Execution time (s)	1.100 0.200	1.429	1.355	1.300


Romaric Ludinard

Loïc Le Hennaff

Eric Totel

RRABIDS, un système de détection d'intrusion pour les applications Ruby on Rails

RRABIDS (Ruby on Rails Anomaly Based Intrusion Detection System) est un système de détection d'intrusion au niveau applicatif pour des applications Web écrites avec le framework Ruby on Rails. Le but de cet IDS est de fournir un outil de détection des attaques contre les données dans le cadre d'applications Web. Cet IDS comportemental se fonde sur l'apprentissage d'invariants dynamiques pendant une phase d'observation du comportement normal de l'application pour définir son profil de référence. Dans une deuxième phase, ce profil est utilisé pour vérifier à l'exécution que le comportement normal de l'application est respecté, en instrumentant automatiquement l'application Web. Les premiers résultats sont encourageants et montrent que des classes d'attaques classiques contre les données (telles que des injections SQL, ou des modifications de paramètres de requêtes) sont détectées par les mécanismes mis en place.

Introduction

De nos jours, les serveurs informatiques forment les piliers des infrastructures de nos systèmes d'information. En tant que tels, ils sont aussi en première ligne vis-à-vis d'attaques visant à corrompre le système d'information. Aussi est-il nécessaire de mettre en place des outils visant à détecter ces attaques. Les systèmes de détection d'intrusion (ou IDS) sont utilisés dans ce but. Il s'agit de systèmes destinés à détecter des attaques ou des violations de la politique de sécurité à l'égard d'un système d'information. Ainsi cette entité informatique va observer le système et comparer les résultats de son observation par rapport à une base de connaissance afin d'établir un diagnostic. On distingue classiquement deux types d'IDS. La différence fondamentale se situe dans la base de connaissance utilisée. Ainsi lorsque celle-ci constitue une connaissance d'attaques connues permettant d'amener l'entité observée dans un état illégal, on parle d'IDS par scénario. L'IDS observe alors l'activité du système et la compare aux attaques déjà connues et déclenche une alerte le cas échéant (c'est par exemple la méthode utilisée par l'IDS Snort qui repose sur une base de signatures des paquets réseau). Le deuxième type d'approche est dit "comportemental". La connaissance préalable du comportement normal de l'application constitue la base de référence. Ainsi toute déviation sensible vis-à-vis du comportement attendu indique une intrusion potentielle. L'avantage de cette dernière approche réside dans sa capacité à détecter de nouvelles attaques sans pour autant devoir mettre à jour une base de signatures. Néanmoins, pour que la détection soit pertinente il faut être capable de se doter d'un profil de référence suffisamment complet et exact du comportement normal de l'application. C'est une approche de ce type que nous développons dans cet article. Concernant les attaques contre les applications, la majorité des études menées considèrent qu'une attaque sur l'application entraîne une modification de son flot de contrôle (c'est-à-dire l'ordre dans lequel les actions sont réalisées). Ainsi, dans le cadre des applications web, l'observation de l'enchaînement des actions effectuées (l'enchaînement des pages par exemple) par l'application surveillée permet de détecter si le comportement observé dévie du comportement de référence. Cependant toutes les attaques n'altèrent pas nécessairement le flot de contrôle. Par exemple, dans le cas d'une injection SQL, l'enchaînement des actions réalisées par l'application est tout à fait légal. Cependant l'exécution de l'injection SQL peut permettre à l'attaquant d'interagir de manière incorrecte avec la base de données pour extraire de l'information confidentielle (violation de la confidentialité de certaines données) ou corrompre des données (violation de l'intégrité de l'application ou de ses données). Cela peut par exemple mener à l'obtention de privilèges supérieurs à ceux que l'utilisateur devrait avoir ou lui permettre d'effectuer des actions nécessitant des privilèges qu'il n'a normalement pas. Ceci illustre le fait que les attaques contre les données ne modifiant pas forcément le flot de contrôle de l'application ne doivent pas être ignorées : ces travaux portent ainsi sur la détection d'attaques contre les données. Dans cet article, nous étudierons dans un premier temps la manière de caractériser le comportement normal de l'application dans le contexte des attaques contre les données, ensuite nous définirons les données critiques dans ce contexte, nécessaires à cette caractérisation. Dans une troisième partie, nous présenterons une implémentation de notre IDS comportemental dans le cadre d'applications web écrites avec le framework Ruby on Rails. Enfin, en dernière partie nous présenterons les résultats que nous avons d'ores et déjà obtenus avec notre outil.

Des contraintes invariantes de l'application

Pour fixer les idées, considérons une petite application web de type CMS. La majorité de ces applications utilisent une base de données contenant l'ensemble des billets ayant été rédigés par les administrateurs. Ce sous-ensemble d'utilisateurs dispose de privilèges pour modifier la base de données. Considérons encore que cette petite application jouet est vulnérable à diverses attaques, en particulier vis-à-vis d'injections SQL. Le code utilisé dans l'application Ruby est donné dans le Listing 1.1. Au lieu de fournir en entrée un identifiant correct, l'attaquant fournit une chaîne de caractères totalement différente des identifiants des utilisateurs ( "'OR '1'='1"), et réussit une injection SQL, qui le mène à s'authentifier, sans pour autant avoir à fournir un couple identifiant/mot de passe correct. Dans l'application concernée, le résultat de la requête SQL en comportement normal donne comme utilisateur l'utilisateur ayant pour identifiant login. Alors que dans le cas de l'injection SQL, l'identifiant du premier utilisateur retourné est forcément différent du login introduit. Ceci montre deux choses : en comportement normal, il existe un invariant qui est vérifié : user.login == params[ :user][ :login] (le résultat de la requête à la base comporte une valeur égale aux entrées de la requête), alors que dans le cas de l'attaque, ce même invariant n'est pas vérifié. Nous avons illustré ici notre approche pour le type d'attaque le plus commun qui existe pour les applications web, mais l'approche s'applique pour toutes les attaques qui visent à violer l'intégrité des données utilisées par l'application (comme la modification de paramètres de requêtes, la modification de données portées par des cookies, etc.). Ces attaques, à un moment ou à un autre, modifient la valeur d'une variable, la rendant inconsistante par rapport à l'état normal attendu du programme. Le problème qui se pose est d'être capable de générer des invariants de manière automatique et sur des données pertinentes. C'est ce problème que nous abordons dans la section suivante.

Modèle de détection fondé sur les invariants

Nous proposons dans cette section de décrire l'approche que nous souhaitons utiliser pour la détection d'intrusion comportementale. Pour ce faire, nous allons construire un modèle de référence fondé sur les invariants issus du programme que l'on souhaite sécuriser. Notre détection se concentrera uniquement sur les attaques contre les données du programme. Comme nous l'avons vu précédemment, ces attaques exploitent du code valide de façon illégale de manière à produire des sorties incorrectes, en violant l'intégrité du programme.

Données sensibles aux attaques

Le modèle de référence basé sur les invariants du programme repose sur la génération d'invariants caractérisant l'exécution normale du programme au travers des valeurs des variables du programme à différents instants de l'exécution. Cependant, il est bien évident que toutes les données de l'application ne sont pas pertinentes pour la construction de cet ensemble de référence. Comme l'ont remarqué Sarrouy et al. [START_REF] Sarrouy | Application data consistency checking for anomaly based intrusion detection[END_REF] dans le cadre général d'applications quelconques, il semble tout d'abord nécessaire de prendre en compte les données influençant les appels systèmes et leurs arguments. En effet, si une variable n'influence pas les appels systèmes ou leurs arguments, elle n'a que peu d'intérêt vis-à-vis de l'attaquant et donc par conséquent vis-à-vis de la détection d'intrusion. D'autre part, il faut aussi prendre en compte les données fournies par l'utilisateur ainsi que celles influencées par ces entrées. En effet, celles-ci constituent le seul moyen pour l'utilisateur d'interagir avec l'application et donc a fortiori d'attaquer l'application.

t (v0, t0) (v1, t1) (v2, t1) (v3, t2) (v4, t2) (v5, t3) (v6, t4) (v7, t5) (v8, t5) (v9, t6) (v10, t7) (v11, t7)
Entrée utilisateur Paramètre appel système Donnée appartenant à l'ensemble critique Donnée n'appartenant pas à l'ensemble critique dépend de

Figure 1. Ensemble des variables sensibles d'un programme

Au final, l'ensemble des données critiques pour le programme est donc situé dans l'union de l'ensemble des données influençant les appels système et leurs arguments et de l'ensemble des données influencées par les entrées utilisateurs. Afin de réduire au maximum le nombre de données pour lesquelles on cherche à calculer des invariants, notre approche s'intéresse uniquement aux données influencées par les utilisateurs (voir la Figure 1). Cette approche en soit n'est pas nouvelle (elle est par exemple utilisée dans [START_REF] Cavallaro | Anomalous taint detection[END_REF]) et consiste à marquer les données (data tainting) pour savoir si elles sont ou non dépendantes des entrées utilisateurs.

Génération automatique de contraintes

Daikon [START_REF] Ernst | The daikon system for dynamic detection of likely invariants[END_REF]

Collecte des données sensibles à l'exécution Ruby on

Rails permet de créer des plugins pour une application. C'est par ce moyen que nous allons pouvoir créer nos traces d'exécution en interceptant l'exécution de l'interprétation du programme à chaque ligne. Lors de l'initialisation de l'application, Ruby on Rails lit automatiquement les fichiers init.rb des éventuels plugins en vue de leur intégration au sein de l'application. Un plugin RoR n'est autre qu'un fragment de code placé à l'endroit adéquat dans l'arborescence de l'application, il ne modifie donc pas le code de l'application, ainsi toute la réalisation que nous avons menée est indépendante de celle-ci. Nous allons voir plus en détail les deux plugins que nous avons réalisés, pour notre système de détection d'intrusion. Pour collecter les données, il est nécessaire d'intercepter le code Ruby qui s'exécute. Une fois encore, Ruby nous fournit toutes les fonctionnalités dont on a besoin. En effet au travers de son module Kernel, Ruby offre la fonction set trace func. Celle ci, lorsqu'elle est appelée avec un paramètre différent de nil permet de suspendre l'exécution courante (exécution d'instruction, appel de méthode, initialisation d'objet, ...) afin d'exécuter le code qu'on lui passe en paramètre avant de reprendre l'interprétation du code au point où elle avait été suspendue. Ainsi, grâce à cette méthode, on peut exécuter à chaque instant, un parcours en profondeur sur les objets en mémoire, de manière a obtenir tous les objets marqués comme tainted et ainsi générer un fichier de traces contenant les couples (nomdevariable, valeurdevariable). Il faut noter que dans une utilisation classique d'un front-end de Daikon, il n'y a pas, sauf cas particulier de relations entre les variables dans Listing 1.3. Exemple de trace fournie à Daikon v a r i a b l e 17 1 @ p a r a m s [ " u s e r " ] [ " name " ] var-k i n d v a r i a b l e dec-t y p e S t r i n g rep-t y p e j a v a . l a n g . S t r i n g e n c l o s i n g -v a r 17 1 @ p a r a m s [ " u s e r " ] c o m p a r a b i l i t y 0 v a r i a b l e 19 2 @ s e s s i o n [ " u s e r " ] . @ a t t r i b u t e s [ " name " ] var-k i n d v a r i a b l e dec-t y p e S t r i n g rep-t y p e j a v a . l a n g . S t r i n g e n c l o s i n g -v a r 19 2 @ s e s s i o n [ u s e r ] . @ a t t r i b u t e s c o m p a r a b i l i t y 0 . . . 17 1 @ p a r a m s [ " u s e r " ] [ " name " ] " e v e t t e " 1 19 2 @ s e s s i o n [ " u s e r " ] @ a t t r i b u t e s [ " name " ] " e v e t t e " 1 Listing 1.4. Exemple d'invariant généré par Daikon 17 1 @ p a r a m s [ " u s e r " ] [ " l o g i n " ] == 19 2 @ s e s s i o n [ : u s e r ] [ " l o g i n " ] le temps. C'est-à-dire qu'on ne peut pas avoir d'invariants tels que 'la variable v1 a l'instant t0 est égale à la variable v2 à l'instant t1". Or dans notre approche, puisqu'on intercepte l'exécution du programme ligne à ligne, on introduit implicitement la notion d'évolution du temps dans les traces qu'on génère (l'avancement d'une ligne à une autre correspondant à l'incrémentation du temps), en nommant les variables qui sont tracées en fonction de la ligne d'exécution. Ainsi, si on se réfère au Listing 1.3, la variable @ session[:user].@attributes[:name] a été tracée à la ligne 10 du fichier source. Le numéro 1 indique le nombre de fois où cette ligne a été atteinte pendant l'exécution du programme (ainsi, la gestion des boucles est prise en compte par notre approche). Ceci signifie que Daikon pourra nous fournir des invariants plus pertinents que ceux qu'il produit en utilisant les front-ends associés aux langages pour lesquels il est normalement conçu.

Invariants Générés

Une fois que l'on a collecté suffisamment de traces, il suffit de les fournir en entrée de Daikon, et celui-ci va fournir en retour un ensemble d'invariants de l'application. Les types d'invariants que nous avons décidés de chercher sont les suivants : -la valeur d'une variable (qui peut être une référence sur un objet) est constante ; ceci permet par exemple de vérifier que la session utilisée est constante pour un même utilisateur ; -la donnée est dans un ensemble fini d'éléments ; ceci peut servir à vérifier que des options en paramètres font bien partie de leur ensemble de définition attendu ; -relation d'ordre entre variables comparables (inférieur, supérieur) ; pour des variables de même type, ceci permet de s'assurer de la validité de certaines variables par rapport à d'autres ; -relation d'égalité entre deux variables ; l'exemple de l'injection SQL développé dans cet article peut être détecté par ce genre d'invariants.

Il faut noter que la pertinence des invariants générés dépend étroitement de l'exhaustivité de la phase d'apprentissage. Nous avons expérimenté cette approche sur une application de e-commerce développée par Kereval 4 en Ruby on Rails dans le cadre du projet ANR DALI 5 , et pour laquelle nous avons réalisé cet apprentissage. Cette phase consiste à automatiser le parcours de l'application web de manière à être le plus exhaustif possible dans son fonctionnement normal. Ceci s'apparente à effectuer un test fonctionnel de l'application, et nous avons donc utilisé un outil de tests d'applications web nommé Selenium 6 . Ceci nous a permis d'automatiser la collecte de traces d'exécution sur l'application. La mise en place de l'IDS nécessite de tisser les invariants dans le code de l'application afin de vérifier à l'exécution si le comportement normal de l'application, appris pendant la phase d'apprentissage, est bien respecté (Figure 2)).

Vérification des invariants à l'exécution

Les invariants que nous obtenons portent sur des relations (identifiées précédemment) sur la valeur d'une ou plusieurs variables dans le temps. Afin de vérifier les invariants à l'exécution, il faut (1) être capable de retrouver ces valeurs et (2) insérer dans le code final de l'application la vérification de l'invariant. Ceci nous mène à tisser dans le code final deux types d'instructions : la sauvegarde de valeurs de variables afin qu'elles soient accessibles lorsqu'on en aura besoin, et la vérification de l'invariant lui-même à la ligne adéquate. On observe sur le Listing 1.6 le résultat de ces deux étapes : on observe la sauvegarde de variables en utilisant la méthode store du module ID-SAsserts, et l'invariant (égalité entre deux variables) est vérifié grâce à la méthode assertEqualVar. Dans cet exemple, on détecte une injection SQL similaire à celle qui a été présentée Section 2, et une alerte est levée (Listing 1.7) en cas d'injection.

Dans la pratique, les relations entre variables peuvent porter entre deux exécutions successives de requêtes à l'application, de sorte qu'on ne retient dans le temps qu'une fenêtre de variables de deux exécutions. La sauvegarde des variables est réalisée sur le serveur entre ces deux exécutions, et les invariants portant sur des variables entre deux exécutions successives peuvent être vérifiés.

Résultats

Comme dit précédemment, nous avons expérimenté notre approche sur une application de e-commerce développée dans le cadre du projet ANR DALI 7 . Sur cette application, nous avons pu générer plus de 10000 invariants qui ont été tissés dans son code. Afin de tester si les mécanismes de détection détectent réellement des attaques, nous avons réalisé quatre types d'attaques contre les données : -les injections SQL que nous avons réalisées mènent à la levée d'une alerte ; -nous avons altéré les paramètres de requêtes vers l'application, et ces modifications ont été détectées ; -nous avons modifié, grâce à un plugin Firefox, des cookies contenant des données de l'application, et ces modifications ont été détectées ; -nous avons réalisé des attaques de type cross-site scripting. Ces attaques, bien qu'elles concernent des données de l'application, ne sont en fait pas utilisées par l'application serveur, mais par le navigateur client, et n'ont donc pas d'impact sur le fonctionnement de l'application côté serveur. Par conséquent, ces attaques n'ont pas été détectées. Ces premiers résultats sont encourageants et seront, nous l'espérons, confirmés par une phase d'évaluation intensive de l'IDS applicatif qui sera menée dans le cadre du projet ANR DALI.

Conclusion

Ces travaux montrent qu'il est possible de générer automatiquement dans une application des mécanismes de détection d'erreurs qui permettent la détection d'attaques contre les données de l'application. De plus, ces mécanismes qui ont été expérimentés initialement sur des binaires, s'avèrent efficaces sur des applications aussi différentes que des 7. http ://dali.kereval.com applications web. Par contre, afin de pouvoir générer des invariants pertinents, il faut être capable de générer des traces des valeurs des variables utilisées par l'application pendant son exécution. Afin de pouvoir avoir un niveau d'introspection suffisant pour effectuer ces observations, nos expérimentations nous ont porté vers un langage et un environnement de développement fort apprécié : Ruby on Rails. L'application développée dans le cadre du projet afin de tester la faisabilité de l'approche nous a montré que les attaques classiques trouvées dans les applications web sont correctement détectées par notre IDS, à l'exception des attaques par cross-site scripting qui sont des attaques contre le client, et non contre le serveur. Enfin, les outils permettant de réaliser cet IDS dans le cadre d'applications Ruby on Rails seront prochainement disponibles en libre accès sur le web.

Listing 1 . 1 .

 11 Requête SQL pour l'authentification u s e r=U s e r . a u t h e n t i c a t e ( params [ : u s e r ] [ : l o g i n ] , params [ : u s e r ] [ : p a s s w o r d ] )

Figure 2 .

 2 Figure 2. Les différentes étapes de la réalisation

  4. http ://www.kereval.com 5. http ://dali.kereval.com 6. http ://seleniumhq.org/ Listing 1.5. Code Ruby initial d e f l o g i n i f r e q u e s t . p o s t ? # w h o l e u s e r i s s t o r e d i n t h e s e s s i o n i f s e s s i o n [ : u s e r ] = U s e r . a u t h e n t i c a t e ( params [ : u s e r ] [ : l o g i n ] , params [ : u s e r ] [ : p a s s w o r d ] ) f l a s h [ : n o t i c e ] = ' You have been s u c c e s s f u l l y l o g g e d i n . ' i f s e s s i o n [ : u s e r ] . admin r e d i r e c t t o : c o n t r o l l e r => ' / admin /home ' , : a c t i o n => ' i n d e x ' e l s e r e d i r e c t t o : c o n t r o l l e r => ' / u s e r /home ' , : a c t i o n => ' i n d e x ' end e l s e f l a s h . now [ : e r r o r ] = ' L o g i n f a i l e d ' end end end Listing 1.6. Code Ruby instrumenté d e f l o g i n i f r e q u e s t . p o s t ? i f i s D e f i n e d ? ( ' @ params [ " u s e r " ] [ " l o g i n " ] ' ) #AutoGenerated I D S A s s e r t s . s t o r e ( ' 1 7 1 @ p a r a m s [ " u s e r " ] [ " l o g i n " ] ' , @ params [ " u s e r " ] [ " l o g i n " ] ) end # w h o l e u s e r i s s t o r e d i n t h e s e s s i o n i f s e s s i o n [ : u s e r ] = U s e r . a u t h e n t i c a t e ( params [ : u s e r ] [ : l o g i n ] , params [ : u s e r ] [ : p a s s w o r d ] ) i f i s D e f i n e d ? ( ' @ s e s s i o n [ : u s e r ] [ " l o g i n " ] ' )#AutoGenerated I D S A s s e r t s . s t o r e ( ' 1 9 2 @ s e s s i o n [ : u s e r ] [ " l o g i n " ] ' , @ s e s s i o n [ : u s e r ] [ " l o g i n " ] ) a s s e r t E q u a l V a r ( ' 1 7 1 @ p a r a m s [ " u s e r " ] [ " l o g i n " ] ' , ' 1 9 2 @ s e s s i o n [ : u s e r ] [ " l o g i n " ] ' ) end f l a s h [ : n o t i c e ] = ' You have been s u c c e s s f u l l y l o g g e d i n . ' i f s e s s i o n [ : u s e r ] . admin r e d i r e c t t o : c o n t r o l l e r => ' / admin /home ' , : a c t i o n => ' i n d e x ' e l s e r e d i r e c t t o : c o n t r o l l e r => ' / u s e r /home ' , : a c t i o n => ' i n d e x ' end e l s e f l a s h . now [ : e r r o r ] = ' L o g i n f a i l e d ' end end end

Listing 1 . 7 .

 17 Exemple d'alerte<A l e r t > <To> <Request>h t t p : / / l o c a l h o s t : 3 0 0 0 / l o g i n </Request> <C o n t r o l l e r >u s e r s </ C o n t r o l l e r > <A c t i o n>l o g i n </A c t i o n> <I n v a r i a n t > <D e s c r i p t i o n > 17 1 @ p a r a m s [ " u s e r " ] [ " l o g i n " ] == 19 2 @ s e s s i o n [ : u s e r ] [ " l o g i n " ] </ D e s c r i p t i o n > <L i n e >19</L i n e> <Value1 >' o r '1 '= '1 </ Value1> <Value2>s e c r e t </Value2> <Datetime>Tue Jun 15 1 7 : 5 4 : 4 5 +0200 2010</ Datetime> </ I n v a r i a n t > </To> </ A l e r t >

  est un outil issu du test logiciel et développé par Michael Ernst pour la détection dynamique d'invariants. À partir de traces d'exécutions constituées de couples (variable, valeur), Daikon est capable d'inférer des contraintes invariantes portant sur les données du programme qui a généré ces traces. En particulier, Daikon peut exhiber des invariants sur une variable (constante, domaine de valeur, référence constante,...), ou sur un ensemble de valeurs (relation d'ordre entre deux variables, combinaison linéaire de variables, etc...). D'autre part, Daikon est capable d'appréhender certaines conditions temporelles, à savoir le lien entre les valeurs d'une même variable en entrée et en sortie d'une fonction, ou alors sur des conditions structurelles des données : il peut ainsi générer des invariants portant sur des objets ou sur des classes. La découverte dynamique d'invariants se déroule en deux temps. Tout d'abord, Daikon possède un front-end qui instrumente le programme de manière à obtenir des informations sur ses variables internes, et la structure de celui-ci, de manière à générer un fichier de traces structuré que Daikon saura exploiter. L'instrumenteur est totalement dépendant du langage source puisqu'il doit être capable de s'interfacer avec le programme de manière à récupérer le maximum d'information (structure et valeurs) sur les données qui nous intéressent. Une fois ces traces collectées, on peut les fournir à Daikon lui-même. Son moteur d'inférence est alors utilisé pour extraire des invariants des traces d'exécution et est totalement indépendant de l'instrumenteur. Ce moteur est configuré par une description du type d'invariants qui doivent être recherchés dans les traces.Identification des variables critiques Comme nous l'avonsdit précédemment, la création de notre modèle de référence débute par l'identification des variables critiques de l'application. Le langage Ruby offre de manière native une fonctionnalité permettant d'identifier les variables du programme dont la valeur est influencée par les entrées utilisateur. En effet, tout objet Ruby contient un flag tainted positionné automatiquement dès que la valeur de l'objet dépend d'une entrée utilisateur. La valeur du flag est obtenue au moyen de la méthode tainted ? Listing 1.2. Lecture de l'entrée standard et propagation du flag tainted True présente dans chaque objet. D'autre part, la propriété tainted se propage par transitivité. Ainsi, si une variable x est marquée tainted et si on initialise une autre variable y à partir d'un calcul faisant intervenir la valeur de x, celle-ci sera marquée tainted aussi, comme on peut le voir dans le listing 1.2. Cependant, le flag tainted ne se propage pas par inclusion structurelle. En effet, si un objet contient un champ tainted, Ruby ne marque pas l'objet en question comme tainted. Il est donc nécessaire de parcourir en profondeur l'ensemble des objets présents en mémoire qui nous intéressent,

	x=g e t s
	x . t a i n t e d ? -> True
	y=" t o t o "
	y . t a i n t e d ? -> F a l s e
	y=x
	y . t a i n t e d ? ->
	1. http ://rubyonrails.org/
	2. http ://twitter.com/
	3. https ://github.com/

4 Mise en oeuvre avec Ruby on Rails

Nous allons détailler dans cette section les principales technologies et techniques mises en oeuvre dans le cadre de notre implémentation d'un système de détection d'intrusion comportemental reposant sur des invariants.

4.1 Ruby et Ruby on Rails

Présentation de Ruby on Rails Ruby on rails 1 (ou RoR) est un framework web libre permettant le développement rapide d'applications web. Il est connu pour certains sites qui n'ont pas hésité à l'adopter, tels que Twitter 2 ou GitHub 3 . Ruby on Rails offre de nombreuses facilités pour implémenter notre approche. à savoir les variables locales, d'instance et les variables de classes afin d'extraire ceux qui permettent d'atteindre un champ tainted et ainsi les marquer eux aussi comme tainted. Cette opération est rendue possible grâce aux grandes capacités d'introspection offertes par Ruby.


Casenave Fabien

Ghattassi Mohamed

Joubaud Rémi

A MULTISCALE PROBLEM IN THERMAL SCIENCE

Nous considérons un problème multi-échelle d'aérothermie en aviation civile. Nous souhaitons déterminer le champ de température dans un avion en conditions de vol, avec présence d'une climatisation. Des composants électroniques ventilés sont présents dans la soute, et constituent une source de chaleur, introduisant une deuxième échelle dans notre problème. Dans un premier temps, nous présentons trois niveaux de modélisation pour le phénomène d'aérothermie, que nous appliquerons aux deux sous-problèmes : l'avion et le composant électronique. Ensuite, nous appliquons la méthode des bases réduites au problème du composant électronique, en considérant des simplifications de modélisation amenant à la résolution numérique d'une EDP elliptique linéaire coercive non-symmétrique.

Introduction

In the civil aircraft industry, one of the main stakes is fuel efficiency. The use of composite materials, to replace aluminium alloys, enables the manufacturers to lighten the plane while keeping the required mechanical properties. However, these materials present lower thermal conductivity, leading to new air conditionning problems. The goal of the present work is to develop fast tools to compute the temperature in an aircraft cabin in flying conditions, with presence of heat sources : mainly the electronic components. A closer look will be taken at two problems :

• the passenger confort in which case the ouput of interest is the temperature in the cabin ; • the equipment failure in which case the output of interest is the maximum of the temperature in the electronic components.

After presenting three levels of modelling for the physical phenomena, we present numerical simulations of the model providing the best trade-off between physical realism and computationnal accuracy. Then, a reduced basis approach will be developped for the electronic component problem to further speed up the computations.

Physical modelling

In both cabin and equipment problems, the flow as well as the temperature have to be computed. We first introduce three models of increasing complexity to solve this physical problem. The standard continuum model for natural convection phenomenon is the compressible Navier-Stokes system (CNS). This model present both theoretical and numerical difficulties in the sense that the equations of conservation are strongly coupled and nonlinear. We choose to consider a hierarchy of simplifications of (CNS).

A hierarchy of models

Consider a bounded domain Ω ⊂ R 2 representing the cabin or the electronic components. The domain Ω is splitted in two parts : Ω = Ω solid ∪ Ω air , where Ω solid stands for solid structures in the cabin or in the electric component. Thus, the velocity field is considered as non-zero on Ω \ Ω solid and extended by 0 on Ω solid . As a first simplification, we will consider the Boussinesq equations, neglecting density variations except in the body force so that the fluid is divergence free. The coupling between the velocity and temperature fields appears in the body force terms in the equations of the fluid and the advective term in the heat equation. This model expresses conservation of momentum and mass of the fluid coupled to the heat equation. The unsteady equations of conservatio ns reads, for a time t S > 0, for all t ∈ [0, t S ] :

             ρ 0 ∂u ∂t + u • ∇u = ρ 0 1 - T -T 0 T 0 g -∇p + η∆u in Ω air , div (u) = 0 in Ω air , ρ 0 c p (x) ∂T ∂t + u • ∇T = div (κ(x)∇T ) + Q(x) in Ω, (1)
Here, u denote the velocity field, p the pressure and T the temperature. T 0 is a reference temperature (300 Kelvin), ρ 0 is the air density at temperature T 0 , g the gravity constant, η the air dynamic viscosity. Then, c p and κ are space dependant discontinuous functions and represent the heat capacity and the heat conductivity of the considered medium (e.g air, aircraft structure). Eventually, Q is a space dependant function representing a source term in the heat problem. In the following, the function κ, c p , Q have the form

κ(x) = i κ i 1 Ωi , c p (x) = i c i p 1 Ωi , Q(x) = i Q i 1 Ωi (2)
where indices i refer to the air and different solid parts depending on the considered problem (aircraft structure, electronic component part,...).

If we assume that the variations of temperature do not modify the velocity field, we can decouple the fluid and heat problems. Moreoever, we consider the fluid at steady state thereby neglecting any feedback of the temperature on the convection of the air. The conservation equations writes for a time t S > 0, for all t ∈ [0, t S ] :

         ρ 0 u NS • ∇u NS = ρ 0 g -∇p + η∆u NS in Ω air , div (u NS ) = 0 in Ω air , ρ 0 c p (x) ∂T ∂t + u NS • ∇T = div (κ(x)∇T ) + Q(x) in Ω. (3)
The last level of modelling consists, as in the previous case, in taking a stationnary regime and in decoupling the fluid and heat problems for the same reasons. The next simplification is to consider a basic model for the fluid equation, namely a potential flow. All the phenomena induced by the viscosity are not captured by this type of model (recirculation zones, boundary layers).

The conservation equations writes :

-∆ψ = 0 in Ω air , ρ 0 c p (x) (∂ t T + u pot • ∇T ) = div (κ(x)∇T ) + Q(x) in Ω, (4)
Here, u pot = ∇ψ is the velocity field associated with the potential ψ. All the three models are supplemented with initial and boundary conditions. A nice consequence for the numerical calculations is that for the two last systems (3) and ( 4), a single evaluation of the velocity field is required.

Geometry and boundary conditions

Now, we describe the different boundary conditions that we consider in the numerical experiments. Assume that the boundary of Ω is partitionned as follow :

∂Ω = Γ in ∪ Γ out ∪ Γ wall .
The portions Γ in/out represent parts of the domain where there are exchange of air (fans and evacuations) and Γ wall are solid adiabatic walls. We enforce non-penetration and no-slip boundary conditions for the fluid flow on the walls :

u = 0 on Γ wall ,
(5) and an inflow of air is imposed on Γ in through a dirichlet boundary condition :

u • n = u in on Γ in , η (∇u • n) • τ = 0 on Γ in , ( 6
)
where u in is a scalar function that we will specify for the numerical calculations and τ a tangent vector to Γ in .

In the case of systems (1) and (3), we enforce natural boundary condition, requiring :

η (∇u • n) = pn on Γ out . ( 7
)
In the case of system (4), in order to have a well posed problem, we impose exact conservation of mass enforcing :

u pot • n = 0 on Γ out , (8)
so that the Poisson problem for the potential flow has to be solved with non-homogeneous Neumann boundary conditions. With this setting, the potential is determined up to an additive constant. For the numerical experiments we fix Ωair ψ = 0. This condition ensure the well-posedness of the problem.

For the temperature field, we assume Dirichlet boundary conditions in the inflow part. Since we assume that the wall are adiabatic, the boundary conditions for the temperature reads :

T = T in on Γ in , ∇T • n = 0 on Γ out ∪ Γ wall .
(9)

Time and space discretization

We now describe the numerical implementation used to solve the previous systems of conservation equations. We describe the numerical algorithm used to solve unsteady Navier-Stokes equations and the heat equation. We use those algorithms in an iterative process to solve the Boussinesq equations. We start by describing the Navier-Stokes solver. The discretization is based on finite elements in space and implicit Euler scheme in time. Let δt be the time step, taken to be constant for simplicity. We denote by t n = nδt the n-th discrete time. We introduce V h (Ω air ) 2 and M h (Ω air ) the finite elements spaces for velocity and pressure. We define the fluid problem at time t n+1 for a temperature T by : given

u n ∈ V h (Ω air ) 2 , we seek (u n+1 , p n+1 ) ∈ V h (Ω air ) 2 × M h (Ω air ) such that for all (v, q) ∈ V h (Ω air ) 2 × M h (Ω air ), Fluid(n + 1, T ) :=                  1 δt Ωair ρ 0 u n+1 • v dx + Ωair ρ 0 u n+1 ∇u n+1 • v dx + η Ωair ∇u n+1 : ∇v dx - Ωair p n+1 div (v) dx = 1 δt Ωair ρ 0 u n • v dx + Ωair ρ 0 1 - T -T 0 T 0 g • v dx, Ωair qdiv (u n+1 ) dx = 0. ( 10
)
Let us denote ũ the extension by zero of u on Ω. We search the temperature in the same finite element space than the velocity components. We define the heat problem at time t n+1 for a fluid velocity ũ by : given

T n ∈ M h (Ω), we seek T n+1 ∈ M h (Ω) such that for all Θ ∈ M h (Ω) : Heat(n + 1, ũ) :=        1 δt Ω ρ 0 c p (x)T n+1 Θ dx + Ω ρ 0 c p (x) ũ • ∇T n+1 Θ dx+ Ω k(x)∇T n+1 • ∇Θ dx = Ω Q(x)Θ dx + 1 δt Ω ρ 0 c p (x)T n Θ dx. ( 11
)
The variational formulation for steady Navier-Stokes equations and equation can be straightforwardly obtained from (10) and (11). Note that the time scheme for the system (10) is nonlinear and we resort to a Newton-Raphson algorithm to solve this nonlinear problem at each time step. In the case of the potential flow, one can resort to a variational formulation of the Poisson equation with Neumann boundary conditions in conjunction with a Lagrange multiplier to ensure that Ωair ψ = 0. For instance, we take the inf-sup stable pair of discrete finite elements spaces V h (Ω air ) 2 × M h (Ω air ) = (P 2 )

2 × P 1 for the fluid equations and M h (Ω) = P 1 for the heat equation. Let us depict the iterative process allowing to solve the Boussinesq system : Initialize with u 0 ∈ V h (Ω air ) 2 and T 0 ∈ M h (Ω) ; For all n ≥ 0, (i) solve Fluid(n + 1, T n ) to get u n+1 ; (ii) solve Heat(n + 1, u n+1 ) to get T n+1 ; All calculations are performed using the finite element solver FreeFEM++ (see [START_REF] Pironneau | freeFEM++[END_REF]). As a matter of illustration, the computationnal code was tested on a simple configuration : consider a square box, with initial state uniform temperature and fluid at rest. A source term Q for the heat problem is localized in the lower part of the box. As we can see in Figure 1, the temperature dependent density in the gravitational term lightens hot air and Figure 1. Temperature field at times t=0, 0.5, 1 and 4 s weighs down cold air. This enable a nonzero velocity field to arise, and a convective dissipation of the heat.

Numerical results

The plane

Consider a bidimensional cross section of a plane (see Figure 2). The upper part, the cabin, presents an inflow of cool air coming from an air conditionning system. Air is leaving the plane through a hole in the lower part, the bay, which contains the electronic components that create heat by Joule effect. A simplified geometry is considered : the goal here is to develop a methodology, not to carry out an accurate industrial simulation. We Figure 2. Geometry of the plane test case consider that the heat produced by the components is completely brought to the bay. Therefore, we can take a constant effective surfacic source term Q in the heat problem. The velocity on Γ in,EC is imposed by the fans of the components. This methodology has been applied for the three different models considered previously.

• Unsteady Boussinesq : See Figures 3 and4.

As expected in such physical situation, the Boussinesq solution does not reach a steady state. The convection effects induced by temperature gradients are the dominant effects, therefore the Boussinesq coupling could not be simplified. Cool air is coming from the upper part and the air in the lower part is being heated up, and the hydrostatic equilibrium is not reached at the end of the simulation.

• Steady decoupled NS/heat : See Figure 5.

The velocity field has been computed once for all, and is assumed not to depend on the temperature. The air viscosity produces recirculation zones. Without Boussinesq effect, the cooling down is only ensured by diffusion and convection from the precomputed velocity field. These two effects are too low, and the temperature reaches very high values.

• Unsteady decoupled potential/heat : See Figure 6. The precomputed flow is very simple, viscosity is neglected. Recirculation zones are not obtained and therefore the cooling of the components (away from the air conditioning main stream) is even worse. Diffusion and convection are way too low, and the temperature diverges. For this situation, only the unsteady Boussinesq can capture all the physical phenomena, and is therefore the model to be considered. In the two other models, the convection brought by the Boussinesq term is not captured, and the components are not cooled down enough. Note that there do not seem to be any steady state to reach for this problem. We simulated up to 40 min, and the velocity and temperature fields appear to reach a periodic in time behavior.

In the present section, we simply modelled the presence of electronic components by a constant surfacic heat source term. We will now develop a model to simulate the velocity and the temperature inside the electronic component.

The electronic component

Consider a 2D section of an electronic component (see Figure 7). The green area represent the support board for the red-colored integrated circuits. The blue zone is filled with air, pushed from the bottom part by a fan, and leaving the box through the top part. The red components will heat up by Joule effect while functioning. Periodic boundary conditions are enforced at Γ per . In this case, the steady decoupled incompressible Navier-Stokes / heat model gives the same result as the long time Boussinesq (see Figure 8). Actually, the Péclet number is large (≈ 10 4 ), indicating that convective effects are dominant. Moreover, the flux is strongly guided inside a channel, which is different from the previous case where air was blowed inside a large volume at rest. Forced convection domines convection induced by local thermal fluxes. The unsteady decoupled potential / heat is not satisfactory : the absence of boundary layer does not allow the air close to the integrated circuits to heat up. In this case, contrary to the previous one, the convection is overestimated in the heating area.

As a conclusion, a decoupling of the fluid and the heat problems is possible. For instance, in order to determine the conductivities and heat capacities of the elements of the electronic component that minimize the temperature, a reduced basis approach can be carried out to drastically reduce the computation time in such a many queries context.

A reduced basis approach for the electronic component problem

Review of the method

The reduced basis (RB) method aims at reducing the computation time in a precise context : running many times the same calculation with a small change of a set of parameters. The idea is somehow close to modal A wide variety of problems can be tackled by this method (see [START_REF] Boyaval | Mathematical modelling and numerical simulation in materials science[END_REF], [START_REF] Boyaval | A reduced basis approach for variational problems with stochastic parameters : Application to heat conduction with variable robin coefficient[END_REF]). We will present it in the context of the present study : the steady decoupled incompressible Navier-Stokes / heat model (3) applied to the electronic component. The reduced basis method has been applied to a heat conduction problem by Sen (see [START_REF] Sen | Reduced-basis approximation and a posteriori error estimation for many-parameter heat conduction problems[END_REF]), and recently to the unsteady Boussinesq equations by Knezevic, Nguyen and Patera (see [START_REF] Knezevic | Reduced Basis Approximation and A Posteriori Error Estimation for the Parametrized Unsteady Boussinesq Equations[END_REF]).

Consider that the fluid equations have been solved once for all, the RB method will be applied to the set of equations :

ρ 0 c p u NS • ∇T -div (κ(x)∇T ) = Q(x), ( 12
)
where u NS is the result of the preliminary incompressible Navier-Stokes computation, and Q(x) = q1 x∈Ω IC (Ω IC stands for integrated circuits and is defined in Figure 7). u NS is extended by 0 in the integrated circuits and in the board.

Equation ( 12) can be rewritten as

A µ T µ = f (13)
with µ a set of n parameters (for instance c p IC , κ board , etc...) in a n-dimensional subspace D of R n . Intervals of variation for the parameters are specified in section 3.3.3. Here, A µ is the linear operator of the problem, f the source term and T µ represents the temperature, solution of equation ( 12) with the parameters set µ.

Let us first check that the RB approach is reasonable in the present case, by selecting by hand a finite set of parameter values, computing the corresponding solutions T i , selecting a problem-related scalar product -(T, Θ) = Ω ∇T • ∇Θ, and checking the variation of the eigenvalues of the matrix M ij = (T i , T j ). This is close to finding principal components of the energy operator (like modal basis). On Figure 9, we see that the eigenvalues of the gramian matrix M of the problem lose 8 orders of magnitude with a reduced basis of size 81 chosen randomly, and the decreasing is exponential. This indicates that the solutions, for µ ∈ D, can be efficiently represented by a linear combination of a small number of functions.

We are interested in the variational formulation of equation ( 13) :

Find T µ ∈ M h such that ∀Θ ∈ M h a µ (T µ , Θ) = l(Θ) (14)
where M h is a finite dimensional subspace of X := H 1 per,0 (Ω) = {T ∈ H 1 (Ω) |T Γin = 0, T periodic at Γ per }, (we can make the Dirichlet condition homogeneous, considering a lifting of T in ). We use the Lagrange's P 1 finite elements for this heat equation (see section 2.3). Since we have mixed boundary condition with a homogeneous Dirichlet condition, ||.|| H 1 0 (Ω) is a norm on H 1 per,0 (Ω) . The considered output is

s µ = l(T µ ) = (f, T µ ) H 1 0 (Ω) = q Ω IC
T µ , a quantity proportional to the mean temperature in the integrated circuits. This specific output allows efficient mathematical analysis.

The RB consists in two steps :

• A computationaly healy offline stage : construct a low dimensional basis, which is a good basis for the high dimensional problem (12) for every parameter µ in D, • Fast online stages : solve light low dimensional problems. The challenge of this approach is to guaranty that the approximate solution of equation ( 12) is a good one. This is possible thanks to the efficient computation of an a posteriori error estimate for our specific quantity of interest.

Goal-oriented a posteriori error estimate : certified RB

Consider T FE µ the solution of ( 14) and T RB µ the current RB approximation of (14) (the proper construction of T RB µ is explained in section 3.3). These quantities verify a µ T FE µ , Θ = l(Θ), ∀Θ ∈ M h and a µ T RB µ , Θ = l(Θ), ∀Θ ∈ M RB , where M RB is the space spanned by the current reduced basis, and has much lower dimension than M h . The quantity of interest is s FE µ , which is computed using the expensive finite element solution, is approximated by s RB µ , which is computed using reduced basis approximation. We need an accurate and fastly computable a posteriori error estimate ∆ µ for the approximation error between the RB and the FE solution : |s RB µ -s FE µ |. By "fast", we mean that the evaluation of ∆ µ should not require the computation of the FE solution.

The bilinear form a µ in Equation ( 14) is coercive and non symmetric : given u NS ∈ V 2 h (Ω air ) we seek T ∈ M h such that for all Θ ∈ M h :

a µ (T, Θ) = Ω ρ 0 c p (u NS • ∇Θ) T + k∇Θ • ∇T + 1 2 Ω ρ 0 c p div (u NS )T Θ.
where the last integral is the Temam term The non-symmetry is induced by the convective terme u NS • ∇T . Recall that the precomputed velocity field u NS is incompressible and cancels on ∂Ω :

a µ (T, T ) = Ω ρ 0 c p (u NS • ∇T ) T + Ω k∇T • ∇T + 1 2 Ω ρ 0 c p div (u NS )T 2 = - 1 2 Ω ρ 0 c p div (u NS )T 2 + Ω k∇T • ∇T + 1 2 Ω ρ 0 c p div (u NS )T 2 . (15) Therefore, a µ (T, T ) = Ω κ µ ∇T • ∇T ≥ min (κ µ ) ||T || 2 H 1 0 (Ω)
; the Temam term ensures coercivity for this bilinear form defined on M 2 h (T ∈ P 1 , therefore T 2 / ∈ P 1 and Ω div (u NS )T 2 = 0). This lower bound is quite pessimistic, especially when κ µ varies a lot in the computational domain. For simplicity, we take this one in the present work. Methods exist to determine sharper constant for the discrete problem, based on solving eigenvalue problems (see [START_REF] Boyaval | Mathematical modelling and numerical simulation in materials science[END_REF] remark 16 p.114 for symmetric problems, see [START_REF] Bao | A successive constraint linear optimization method for lower bounds of parametric coercivity and inf-sup stability constants[END_REF] for a presentation of the successive constraint method is of complexity O(n 2 d 2 ), which corresponds to a fast computation compared to the FE problem. The faster the estimator is computed, the larger D trial we can explore in the greedy algorithm for a given computation time.

Numerical results

The greedy algorithm has been carried out to compute 10 basis functions, with a parameter set of 20, 000 points. The finite elements problem has 9012 degrees of freedom. We took as parameters : κ IC , κ board , κ air the integrated circuit, board and air heat conductivity and c p air the air thermal capacity, varying in the following intervals (international system of units) : κ IC κ board κ air c p air min 0.5 0.06 0.028 1080 max 5 0.6 0.032 1120

We first check that the growth of the basis reduces projection errors (see Figure 11) : 12). The error estimate and the error are not strictly decreasing. Maybe this is due to the fact that the RB is certified for a scalar quantity different from the projection error represented in Figure 11. Recall also that we did not compute a satisfying lower bound for the coercivity constant of the bilinear form a µ . The error estimate for a random parameter is not strictly decreasing with the size of the basis, but globally tends to zero. Remark that an error of 8 × 10 -5 correspond to a mean temperature error of 1 K

Figure 3 .Figure 4 .

 34 Figure 3. Temperature field in the Boussinesq model, with the cluster at the right of the bay, at times 0, 100, 200,... 1700

Figure 5 .

 5 Figure 5. Plane test case in the decoupled NS/heat model. Velocity and temperature fields.

Figure 6 .

 6 Figure 6. Plane test case in the decoupled potential/heat model. Velocity and temperature fields.

Figure 7 .Figure 8 .

 78 Figure 7. Distorted geometry of the electronic component test case (the height of the component is actually 16 times larger than its width)

Figure 9 .

 9 Figure 9. Eigenvalues of the gramian matrix M

  of the projection error Evolution of the projection error during the greedy algorithm

Figure 11 . 1 0

 111 Figure 11. Evolution of T FE μ -T RB μ H 1 0 for μ ∈ D taken randomly with the size of the reduced basis Consider now the evolution of the maximum error estimate ∆ µ for µ ∈ D trial and the corresponding value of the error s RB, * RB µ

Figure 13 .

 13 Figure 13. Temperature maps for the electronic component case. Left : RB online call u RB , center : FE calculation u FE , right : difference u FEu RB

Université Paris Est, CERMICS, Ecole des Ponts ParisTech, 6 & 8 Av. Pascal, 77455 Marne-la-Vallée, France

EADS France, Bâtiment Campus Engineering -Service IW/SE/MA, BP 90112 -31703 BLAGNAC Cedex

Institut Élie Cartan, Université Henri Poincaré Nancy 1, F-54506 Vandoeuvre-lès-Nancy Cedex

ANDRA, DRD/EAP, Parc de la croix blanche, 1,7 rue Jean Monnet, 92298 Châtenay-Malabry Cedex, France c EDP Sciences, SMAI 2012

Acknowledgments

This work was financially supported by EADS IW. The authors wish to thank the CEMRACS'11 organizers and Sébastien Boyaval, Albert Cohen, Alexandre Ern, Benoit Fabrèges and Tony Lelièvre for fruitful discussions.

used in nonsymmetric problems).

We introduce the adjoint problem of (14) :

We have to construct a reduced basis for this problem as well : define Ψ * RB µ the current RB approximation of (16) (verifying a µ v, Ψ * RB µ = -l(v), ∀v ∈ M * RB , the space spanned by the current reduced basis of ( 16)).

Consider the residual for the direct and the adjoint problems : for all w, v ∈ M h ,

Make use of the version of Riesz-Fréchet representation theorem applied to continuous bilinear forms : there exists a unique application

). This specific output has been chosen to ensure the posteriori estimate given in the proposition 3.1.

Note that the FE corresponding quantity is l T

where α LB,µ is a computable lower bound for the coercivity constant α µ of a µ (., .) (recall that a bound for the continuous case is α LB,µ = min (κ µ )).

Proof. Using elements of proof from Boyaval's PhD thesis (propositions 18 and 23) :

Using (16),

Using Cauchy-Schwarz inequality, we can write :

Then by coercivity, (16), (17) and the Cauchy-Schwarz inequality :

Pluging this in (19), we get the inequality (3.1). ♦ Remarque 3.2. Note that the error estimate ∆ µ does not require the evaluation of the FE solutions, enabling fast computation.

The inexpensive a posteriori error estimate (3.1) is useful to check rapidly if an online call approximates well the FE reference and to construct iteratively the reduced basis using a greedy algorithm (see section 3.3).

Computation aspects and construction of the basis with a greedy algorithm

Offline stage : precomputation and greedy algorithm

The certified RB method consists in iteratively construct a basis with solutions of the considered problem, computed at particular values of the parameters µ.

Ideally, we would like to choose a tolerance ǫ for the error |s RB, * RB µ -s F E µ | and make use of the error estimate ∆ µ to construct a low dimensional basis where the error is guaranteed to be smaller than ǫ for all µ in the parameter space D. Unfortunately, such a result does not exist. One can refer to recent work by Binev, Cohen, Dahmen, DeVore, Petrova and Wojtaszczyk [START_REF] Binev | Convergence rates for greedy algorithms in reduced basis methods[END_REF] for theoretical results on greedy algorithms convergence performances. In the present setting, we have an affine dependance of the operator on the parameters (thanks to equations (2)) :

In the same fashion, the residuals are written : for all w, v ∈ M h ,

where the a i do not depend on µ.

). Take g 0 and g * 0 , solutions of (g 0 , v)

In practice, we only need to compute G i w and G * i v for given vectors w, v ∈ M h . This is done by solving variational problems. Consider for instance

The other quantities defined above are computed in the same way. This will speed up the online stage since lots of quantities will be precalculated during the offline stage, letting to the online stage simple low dimension algrebra operations (see section 3.3.2). Take a finite set D trial ⊂ D. The greedy algorithm reads as follow :

.. n] ;

Remark : since the problem is not symmetric, we also have to store

Note that we did not explain how to chose the finite set D trial . In our case, we simply discretized each direction of D with a constant step : see Figure 10. The efficient evaluation of ∆ µ is explained in the next section 3.3.2.

Online stage

Consider that a basis (b) i of size d has been constructed (and a basis (b * ) i for the adjoint problem) , and that we want to efficiently compute the temperature using the RB for a given parameter.

An online call consists in solving the following Galerkin problem : In practice, when the size of the reduced basis increases, the matrix A µ may be close to singular. One can improve this by orthonormalizing the basis using modified or simple Gram-Schmidt (see [START_REF] Boyaval | Mathematical modelling and numerical simulation in materials science[END_REF], p.109).

Then, an online call should also contain an evaluation of the a posteriori error estimate ∆ µ , and if it is larger than ǫ, one can compute the FE solution and enrich the basis with this fonction. This way, the error estimate is guaranteed, but we may need to compute the expensive solution sometimes.

We also use precomputed quantities to get an evaluation of ∆ µ in a complexity independant of the FE problem size.

where all the scalar products involved have been precomputed and stored during the offline stage. Therefore

over the integrated circuits. Once the basis constructed, we tried an online call taking a random parameter in D (see Figure 13) :

• A posteriori error estimate : 7.24 × 10 -6

Conclusion

We developped different models for solving the velocity and the temperature of the air under different conditions. The full Boussinesq model yields satisfactory results in the cases we considered, whereas decoupled incompressible Navier-Stokes / heat was satisfactory for the electronic component case (forced convection in a pipe).

We then tested a certified RB method for the heat problem with non homogeneous convection. Our code makes use of an a posteriori error estimate to build a basis iteratively using a greedy algorithm. The affine parametric assumption allows to precompute many terms, and online calls are reduced to add and inverse low