Computer arithmetic approximates real numbers (as used in mathematics) by finite-size representations. Floating point representation, where any number is represented by a sign, a mantissa and an exponent is a widespread choice [2]. The most common actual implementation is referred to as IEEE-754 [1]. The floating point representation introduces inevitable errors due to rounding. To mitigate the problem of having different results for a single application, vendors have come up with a standard that specifies many aspects of the representation.

Despite the IEEE-754 standard, we have observed that applications often produce different results when executed on different machines or when compiled by different compilers [3].

The purpose of this internship is to identify the source of the divergence between different runs of the same application, and to locate it in order to report it to the programmer. In practice, several executables of the same application will be instrumented by the Pin dynamic binary instrumentation tool [4] and run on an Intel x86 machine to collect relevant floating-point computations.

• d'analyser les méthodes existantes et les problèmes rencontrés dans la fouille de données séquentielle avec intervalles temporels,
• de proposer un algorithme pour la fouille de séquences avec intervalles temporels n'utilisant pas de motifs,
• d'analyser les propriétés des algorithmes proposés,
• de développer et tester les algorithmes sur des données simulées et réelles (données médicales et de consommation électrique).

Power consumption has become a key characteristics of computing systems. Maximizing performance for a given power budget, or minimizing power for a given power target are important goals in many industrial contexts. Power consumption, however, cannot easily be measured from the computer itself.

On the other hand, current processors let users observe many events related to the behavior of the micro-architecture. Hardware performance counters [1] monitor various events, such as the number of executed instructions, cycles, cache misses, mispredicted branch instructions, etc. [2] Performance counters have attracted considerable attention due to their ability to collect information at no (or negligible) cost.

The goals of this internship are:

1. to study to what extent the power consumption of a computer can be correlated to micro-architectural events (similar to [5], but simpler and more automated), and to identify a few events that can be used to safely predict the power,
2. to develop a tool that can display the estimated power consumption in real-time, and
3. to use the tool to study the impact of parallelism (hyperthreading, multicore) on the power consumed by various applications.

Various kinds of computers will be considered: smart phone, laptop, desktop (x86, PowerPC, Sparc), and node of a cloud.

Performance readings will be taken in real-time using a TCP-IP power distribution unit [4] available in our laboratory, and hardware counters are made available by a dedicated Linux system call.

The protein 3D structure is the spatial conformations in which the protein sequence folds. The biological function of a protein depends on its 3D structure and its knowledge is highly important in medicine (for example, in drug design) and biotechnology (for example, in the design of novel enzymes). Many of available structures are available in the Protein Data Bank as sets of the atoms coordinates, determined by costly techniques such as X-ray crystallography. Prediction of the structure of proteins is one of the most important goals pursued by bioinformatics and theoretical chemistry. The set of atoms coordinates contain the raw information but is not the more adequate for automatic prediction or characterizations based on the structures of proteins. In the team we have been able to get good or promising results by using alternative representations, such as protein contact maps, for the comparison of structures and their automatic classification [1] and pattern discovery and grammatical inference [2]. Protein contact maps represent structures of proteins by a binary relation between the residues which are close enough. We propose here to continue this line of research and to work on the definition of new representations of the protein structure based on the contact maps, to offer the right level of abstraction (without loss of important information) to develop new algorithms handling protein structures with a better quality and efficiency.

1. Maximum Contact Map Overlap Revisited, Rumen Andonov, Noël Malod-Dognin, Nicola Yanev, Journal of Computational Biology 18, 1 (2011) 1-15
2. Towards pattern discovery and grammatical inference in protein folds, François Coste, Fabio Cunial, techn. rapport, Symbiose, 2010.
3. Reconstruction of 3D Structures From Protein Contact Maps, Vassura M, Margara L, Di Lena P, Medri F, Fariselli P, Casadio R (2008). IEEE/ACM Transactions on Computational Biology and Bioinformatics 5 (3): 357–367
4. Predicting helix-helix interactions from residue contacts in membrane proteins, Lo A, Chiu YY, Rødland EA, Lyu PC, Sung TY, Hsu WL. (2009). Bioinformatics 25 (8): 996–1003

Learning a compact hierarchical structure of a sequence is motivated by several applications: to compress the sequence, to measure its amount of information or to better understand it. In his thesis [1], Matthias Gallé worked successfully on the smallest grammar problem (i.e. searching for the smallest context free grammar that generates only one sequence) and introduced variants of this problem to cope with the specificities of DNA sequences. In particular, to cope with mutations arising frequently in DNA, he proposed to extend grammars with "don't cares" (grammars based on "motifs", see for instance [3]). The grammars in that case represent more than one sequence, forgetting uninteresting regions (for structure discovery or lossy compression) or relying on the emission of an extra amount of information to fill the gaps (structure discovery in the minimum description/message length [2] perspectives or lossless compression). This new setting opens new perspectives for both structure discovery and compression. The subject is to propose and implement new algorithms and heuristics in this framework to find efficiently more compact hierarchical structures, with a special interest to their application on real DNA sequences.

1. Searching for Compact Hierarchical Structures in DNA by means of the Smallest Grammar Problem, PhD thesis, Univ. Rennes 1, 2011 http://tel.archives-ouvertes.fr/tel-00595494/fr/
2. See references cited in http://en.wikipedia.org/wiki/Minimum_description_length
3. MADMX: A Strategy for Maximal Dense Motif Extraction, Roberto Grossi, Andrea Pietracaprina, Nadia Pisanti, Geppino Pucci, Eli Upfal and Fabio Vandin. Journal of Computational Biology. April 2011.
   

The last on-chip cache level on multicore processors is often shared between all the cores. Recently, shared caches have received a lot of attention from researchers in computer architecture. However, there is no clear agreement among researchers as to what is the best method for studying shared caches. One difficulty is to define a good performance metric for multiprogrammed workloads, i.e., workloads consisting of independent tasks. Several possible metrics have been proposed [1][2], each highlighting one particular performance aspect, e.g., throughput or fairness. This multi-dimensional aspect of performance makes it more difficult to draw conclusions. Another difficulty comes from the methods used by computer architects to draw conclusions, which are mostly based on simulations. An implicit assumption is that the benchmarks used in simulations are representative. Given a fixed number of benchmarks, the number of possible multiprogrammed workloads increases quasi-exponentially with the number of cores. Because simulations are time consuming, researchers generally work on a small set of workloads, which they define more or less arbitrarily. Yet, even if the benchmarks themselves are representative, it is not clear how many workloads must be considered to make a representative set.

The work proposed consists in comparing the cache replacement policies that have been proposed in the recent Cache Replacement Championship [3]. More precisely, the goal is to understand to what extent the qualitative conclusions depend on the performance metric and on the set of workloads.

[1] S. Eyerman, L. Eeckhout, "System-level performance metrics for multi-program workloads", IEEE Micro, Vol. 28, No. 3, 2008.

[2] H. Vandierendonck, A. Seznec, "Fairness metrics for multi-threaded processors", Computer Architecture Letters, January 2011.

[3] Cache Replacement Championship, 1st JILP Workshop on Computer Architecture Competitions (JWAC-1), 2010. http://www.jilp.org/jwac-1/

Contexte

Objectif

• Conception des IHM
  1. A. Blouin , O. Beaudoux - Improving modularity and usability of interactive systems with Malai, Proceedings of the 2nd ACM SIGCHI Symposium on Engineering Interactive Computing Systems (EICS 2010), ACM, 2010.
     
  2. G. E. Krasner and S. T. Pope. A description of the model-view-controller user interface paradigm in smalltalk80 system. Journal of Object Oriented Programming, 1 :26–49, 1988.
• Mécanismes de “data-binding” :
  1. Eclipse Foundation. JFace data binding. http ://wiki.eclipse.org/index.php/JFace_Data_Binding.
  2. R. Field. JavaFX language reference (chapter 7 - Data binding). http ://openjfx.java.sun.com/ current-build/doc/reference/ch07s01.html.
  3. C. Kazoun and J. Lott. Programming Flex 2. O’Reilly, 2007.
• Opérations actives :
  1. O. Beaudoux , A. Blouin , O. Barais , J.M. Jézéquel - Specifying and implementing UI Data Bindings with Active Operations, EICS’11 : Proceedings of the 3rd ACM SIGCHI symposium on Engineering Interactive Computing Systems, 2011.
  2. O. Beaudoux, A. Blouin, O. Barais, and J. M. Jezequel. Active operations on collections. In MoDELS ’10 : Proceedings of the 13th ACM/IEEE International Conference on on Model Driven Engineering Languages and Systems (LNCS 6394), pages 91–105. Springer, 2010.
  3. O. Beaudoux and A. Blouin. Linking data and presentations : from mapping to active transformations. In DocEng ’10 : Proceedings of the 2010 ACM symposium on Document engineering, pages 107–110. ACM, 2010.
• Contraintes :
  1. J. B. Warmer and A. G. Kleppe. The object constraint language : getting your models ready for MDA. Addison-Wesley.
  2. Cabot, J., Teniente, E. : Incremental evaluation of OCL constraints. In : CAiSE 2006, LNCS 4001. (2006) 81–95
  3. ObeoDesigner : http ://www.obeodesigner.com/
  4. Timothy Heron Programming with Dependency. MSc thesis, Department of Computer Science, University of Warwick, UK (September 2002).

Afin de détecter des intrusions, deux grandes techniques existent : l’approche par scénario et l’approche comportementale. Dans l’approche par scénario, on décrit les attaques connues contre le système et on stocke ces descriptions dans une base de connaissance (ou base de signatures). A l’exécution, on cherche à détecter si certaine de ces attaques sont en train d’être perpétrées. Malheureusement, une telle approche ne permet pas détecter des attaques inconnues qui, par définition, ne sont pas présentes dans la base de signatures. La deuxième approche consiste au contraire à modéliser le comportement normal de l’application : à l’exécution on cherchera à détecter toute déviation du comportement de l’application par rapport à ce profil de référence. On en déduit que ces déviations sont dues à des intrusions. Parmi les approches comportementales, l’approche dite « par la spécification » a été utilisée pour des applications centralisées ou distribuées. Ce type d’approche utilise comme comportement de référence une description de la spécification de l’application. Toute la difficulté de ce genre d’approche consiste à obtenir une description utilisable et suffisamment précise. Une spécification identifie plus ou moins finement soit des séquences d’actions autorisées (caractérisation des enchainements d’instructions, d’appels systèmes), soit des séquences d’états atteignables (caractérisation des prédicats/invariants qui doivent être satisfait par les valeurs des données manipulées).

Plusieurs travaux ont déjà été menés afin de détecter des attaques contre des applications. Dans [1], Uppuluri et al. montrent qu’il est possible de construire un modèle fondé sur la définition d’un langage décrivant les actions des processus (accès à des fichiers, lecture de fichiers ou de sockets, …) de manière fine (occurrence d’événement, séquence d’événements, …). La détection proposée dans ces travaux est essentiellement locale au nœud du réseau considéré. Dans [2], Ko et al. centralisent les actions (appels systèmes) réalisées sur chaque nœud en les ordonnant dans le temps afin de vérifier des propriétés temporelles globales sur le système distribué. D’autres travaux ont utilisé l’approche de détection par spécification dans le cadre de systèmes distribués, par exemple pour modéliser des protocoles [3, 4]. Les travaux sur le thème de la détection d’erreurs dans les systèmes distribués (outils de monitoring) ont également pour objectif de spécifier (et de détecter) des prédicats décrivant un comportement normal ou anormal d’une application [5].

Dans le cadre de ce stage, nous souhaitons modéliser des comportements normaux d’applications distribuées en utilisant les concepts suivants: nous raisonnerons à la fois en terme d’actions (échanges de messages, interactions avec le système, manipulation de l’état) et en terme d’états (locaux aux processus et globaux). Lorsque l’application s’exécute sur des processus distants, seule l’existence d’un référentiel de temps commun permet de dater de façon cohérente tous les événements et d’appréhender ainsi le comportement global de l’application. Dans le cas d’un système asynchrone, la notion de temps ne peut pas être utilisée. La notion de dépendance causale apparaît alors comme une alternative: d’une part, les actions (et les états locaux) de chaque processus sont totalement ordonnés ; d’autre part, le fait que la réception d’un message ne peut se faire avant l’émission de celui-ci permet de définir une relation d’ordre partiel entre les événements lorsque ceux-ci se produisent sur des sites distants.

Ces notions et ces approches seront utilisées pour définir un langage de modélisation du comportement attendu de l’application (cohérence des états des processus, enchaînement des actions). Ce langage pourra notamment prendre en compte la notion de temps lorsque cela est possible et permettre de gérer la granularité des observations (actions atomiques ou points d’observation dans l’application). Une application répartie réelle (très simple) sera identifiée. Elle devra permettre d’illustrer les différentes possibilités offertes par le langage de spécification et de démontrer que la spécification est suffisante pour détecter des déviations par rapport aux comportements attendus (attaques réelles).

[1] Prem Uppuluri and R. Sekar, Experiences with Specification-Based Intrusion Detection, Proceedings of the Fourth International Symposium on the Recent Advances in Intrusion Detection (RAID'2001), 2001, W. Lee and L. Mé and A. Wespi, 2212, LNCS, pp. 172-189, Davis, pp 172-189, 2001.

[2] Calvin Ko, Manfred Ruschitzka and Karl Levitt, Execution Monitoring of Security-Critical Programs in Distributed Systems : A Specification-based Approach, Proceedings of the 1997 IEEE Symposium on Security and Privacy, 1997, pp. 175-187, Oakland, CA, May, 1997.

[3] R. Sekar and Ajay Gupta and James Frullo and Tushar Shanbhag and Abhishek Tiwari and Henglin Yang and Sheng Zhou, Specification-based anomaly detection: a new approach for detecting network intrusions, Proceedings of the 9th ACM conference on Computer and communications security, pp. 265-274, Washington, DC, November, 2002.

[4] Chinyang Henry Tseng and Tao Song and Poornima Balasubramanyam and Calvin Ko and Karl Levitt, A Specification-based Intrusion Detection Model for OLSR, Proceedings of 8th International Symposium on Recent Advances in Intrusion Detection (RAID '2005), september, 2005.

[5] V. K. Garg, Principles of Distributed Systems, Kluwer Academic Publishers, ISBN: 0-7923-9668-5, 1996.

Modèles et algorithmes pour la détection de variants génomiques dans les données de séquençage nouvelle génération

Une question fondamentale en biologie est de détecter et interpréter les variations entre les génomes d'individus d'une même espèce. Ces variations peuvent être des mutations ponctuelles d'un seul nucléotide (SNP), ou bien peuvent impliquer des segments d'ADN plus longs qui peuvent être dupliqués, supprimés, inversés ou déplacés le long du génome. Ces variants sont appelés des variants de structure et leur importance dans la diversité génétique entre individus n'a été révélée que récemment.

L'analyse de la diversité génomique entre individus a connu un essor sans précédent ces dernières années avec l'arrivée des NGS (Next Generation Sequencing). Ces nouvelles technologies permettent de séquencer l'ADN avec un débit beaucoup plus important et un coût beaucoup moindre. Cependant, elles génèrent de très grandes quantités de données d'un nouveau type qui requièrent des méthodes informatiques poussées.

L'équipe Symbiose est à la pointe dans ce domaine et a développé une nouvelle approche permettant d'extraire des variants de type SNPs de ces données. Elle est basée sur l'exploration du graphe de DeBruijn, une structure de données communément utilisée dans ce domaine, le principe étant que les variants génomiques génèrent des motifs spécifiques dans ce graphe.

L'objectif du stage est d'étendre la méthode KisSNP, dédiée aux SNPs, pour détecter d'autres types de variants comme les variants de structure, qui sont plus complexes et plus rarement étudiés.

Le travail consistera dans un premier temps à formaliser les modèles générés dans le graphe de DeBruijn par chaque type de variant génomique. Leurs propriétés topologiques et combinatoires seront analysées pour caractériser chaque variant. D'autres structures de données alternatives au graphe de DeBruijn (ou dérivant de) pourront être proposées afin de gérer des informations biologiques supplémentaires. Dans un deuxième temps, de nouveaux algorithmes seront proposés pour détecter efficacement ces variants.

• Next-generation gap. J D McPherson. Nat Methods, 2009, 6:S2-S5
• Assembly algorithms for next-generation sequencing data. J R Miller, S Koren & G Sutton. Genomics, 2010, 95:315-327
• Computational methods for discovering structural variation with next-generation sequencing. P Medvedev, M Stanciu & M Brudno. Nat Methods, 2009, 6:S13-S20
• Identifying SNPs without a reference genome by comparing raw reads. P Peterlongo, N Schnel, N Pisanti, MF Sagot & V Lacroix. In proceedings of String Processing and Information Retrieval, 2010

Contexte général

Ingénierie dirigée par les modèles

L'augmentation rapide et constante du volume, de la complexité et de l'hétérogénéité des systèmes informatiques pose les problèmes de la maîtrise des coûts et des délais de développement, de la garantie de qualité, et de la capacité pour un produit existant à être réutilisé dans différents contextes.

Afin de pallier ces problèmes, un certain nombre de pratiques ont été proposées, étudiées et partiellement adoptées par l'industrie du logiciel. Parmi elles, l'ingénierie dirigée par les modèles (IDM, ou MDE pour Model Driven Engineering) est un paradigme d'ingénierie dans lequel les modèles constituent les constructions primitives d'un logiciel et se retrouvent au coecontemplatifs (i.e. des documents de référence) : ils sont productifs. Ils sont ainsi la source d'artefacts produits automatiquement (e.g. code, tests, documentation).

Parmi les approches MDE notoires figurent le MDA (Model Driven Architecture), le MIC (Model Integrated Computing), et les Software Factories.

Métamodèles et langages dédiés

La production, et en particulier l'édition, d'un modèle est rendue possible par des outils de modélisation généralement dédiés à un langage particulier. Ces langages de modélisation peuvent être généralistes ou spécifiques à un domaine. Leur très grande diversité pose les problèmes de l'interopérabilité et de la réutilisation des outils.

La plupart des solutions à ces problèmes ont pour origine l'expression uniforme des modèles de ces langages appelés métamodèles, dans un même métalangage dont l'outillage peut être réutilisé (e.g. édition, sérialisation, transformations). Ecore, dialecte d'UML pour les modèles statiques, est un exemple notoire de métalangage.

Transformation de modèle

Une approche du développement logiciel dirigé par les modèles cible les problèmes de construction et d'évolution en s'appuyant sur la notion fondamentale de transformation. De nombreuses solutions pour la transformation de modèles existent, parmi lesquelles figurent ATL, SmartQVT, ou Kermeta.

Problématique

Réutilisation d'outils

La réutilisation de composants logiciels permet de réduire considérablement le coût du développement des outils dédiés à un langage spécifique. Un environnement de méta-modélisation comme EMF basé sur Ecore permet par exemple de produire des éditeurs spécifiques ou des explorateurs d'instances. Cependant, il reste souvent des composants spécifiques à définir. Dans de nombreux cas, ces éléments spécifiques sont déjà disponibles mais ils sont conçus pour des variantes du métamodèle sur lequel le concepteur travaille.

Langage de transformation spécifique

Nous nous intéressons plus particulièrement aux composants qui s'appuient sur des transformations de modèle. Une transformation de modèle s'applique à domaine correspondant à un certain métamodèle source. Les données traitées par la transformation sont donc des instances conformes au métamodèle source.

Afin de réutiliser une transformation, une méthode assez naturelle consiste à injecter les données dont on dispose dans le domaine d'application de la transformation. Du point de vue de l'IDM, cette injection est également une transformation de modèles qu'il serait possible d'exprimer en ATL ou SmartQVT. Cependant, puisque le concepteur juge pertinent d'appliquer une transformation existante aux instances de son métamodèle, nous pouvons raisonnablement supposer que des liens sémantiques forts existent entre le métamodèle du concepteur et le domaine de définition de cette transformation. Nous avons donc défini un langage de transformation spécifique appelé Modif pour cibler ce type de problème.

Modif est inspiré de certaines fonctions de stockage persistant (CRUD) à partir d'un métamodèle source pour produire un métamodèle cible. Ces fonctions sont notamment update (i.e. rename et change) et deletion. Il est ensuite possible depuis Modif de générer le métamodèle cible, ainsi que le composant de migration de données correspondant.

Problème posé

Les fondements sémantiques de Modif restent à définir formellement. Dans ce but, un domaine sémantique approprié doit être mis en évidence. Il doit en particulier couvrir les concepts fondamentaux des métamodèles, ainsi que les opérations primitives de refactoring de modèles.

Ce travail permettra de coupler Modif à des outils d'analyse formelle afin notamment de prouver que certaines propriétés des données initiales sont préservées une fois ces données transformées.

Ce travail permettra également de simplifier l'analyse et le traitement des spécifications Modif. En effet, certaines des nombreuses opérations proposées par le langage pourront très certainement être exprimées par la composition des opérations primitives qui auront été identifiées.

Enfin, l'outillage actuel de Modif devra être mis à jour en conséquence.

Organisation et objectifs du stage

Le stage se déroulera en trois phases. L'étude bibliographique sur l'IDM, les transformations de modèles, l'outillage IDM, la migration de données et les sémantiques de métamodèles constituera la première phase.

La deuxième phase consistera à mettre au point le domaine sémantique de Modif, ainsi que les fonctions de valuation du langage vers ce domaine sémantique.

Enfin, la dernière phase consistera à mettre à jour l'outillage existant.

Frama-C [1] est un framework permettant de réaliser l’analyse statique de codes écrits en langage C qui est activement développé par le CEA. Ce framework offre un ensemble de briques permettant de conduire différentes analyses classiques de code source. Frama-C est complètement écrit en objective CAML et repose lui-même sur le projet CIL dont le but est de transformer un code écrit en langage C vers un langage intermédiaire sémantiquement équivalent, mais utilisant seulement un sous-ensemble restreint du langage C. Par ailleurs, Frama-C peut être étendu par un système de plugins. Dans le cadre de sa thèse Jonathan Demay a réalisé un plugin pour Frama-C nommé SIDAN [2, 3, 4] qui permet la génération automatique d’invariants et leur incorporation dans un programme C. Ces invariants permettent de détecter des erreurs à l’exécution du programme, dont la survenue peut être attribuée à une attaque. Cependant dans son état actuel , il a été montré que la couverture de détection des erreurs de SIDAN reste relativement faible. Faute de temps, certaines améliorations du plugin identifiées par Jonathan Demay mais n’ont pas pu être implémentées durant la durée de sa thèse.

Le stage consistera donc à améliorer le plugin SIDAN suivant trois directions clairement identifiées :

1. Pour l’instant le plugin SIDAN ne considère que les variables simples de type entières. On cherchera à améliorer SIDAN en intégrant dans l’analyse des entiers contenus dans des structures de données arborescentes ou des tableaux d’entier ;

2. Les invariants générés actuellement ne portent que sur des relations entre variables à l’intérieur d’une même fonction. Or Frama-C réalise une analyse interprocédurale, ce qui permettrait d’établir des relations entre variables appartenant à des fonctions différentes. On cherchera à ajouter cette fonctionnalité à l’intérieur de SIDAN.

3. Si le temps le permet, on cherchera aussi à améliorer le plugin réalisant l’analyse de valeur au sein de Frama-C (plugin utilisé par Frama-C afin de calculer ses invariants) de manière à augmenter la vitesse d’analyse et la consommation mémoire. Pour cela on essaiera de modifier le plugin d’analyse de valeurs afin qu’il puisse conduire une analyse de valeur procédure par procédure (plutôt qu’une analyse globale).

Les compétences suivantes seraient un plus pour ce stage : la connaissance d’algorithmes d’analyse statique, une bonne connaissance des langages C et Objective CAML.

• Réaliser un travail bibliographique sur les travaux existants visant à définir les attributs de qualités logicielles [ISO09], les choix de conception d’architecture et leur justification [K04, BB08, WB10] ;
• Identifier les concepts des styles architecturaux et de leurs propriétés non fonctionnelles à rattacher aux design rationals ;<:li>
• Proposer un formalisme pour spécifier des design rationals génériques pour 3 styles ou pattern classiques [TMD09] ;
• Proposer une analyse pour vérifier la cohérence, la contradiction ou les conflits entre les design rationals d’une architecture conforme aux 3 styles classiques;
• Etudier et proposer une extension de l’analyse précédente à des styles d’architecture hybrides ;
• Rédiger un rapport de stage en français ou en anglais, potentiellement co-publier un article scientifique en anglais.

• [BB08] Burge J. E.and Brown D. C.. Software engineering using rationale. J. Syst. Softw., 81(3):395–413, 2008.
• [K04] Kruchten, P. An Ontology of Architectural Design Decisions. In Proceedings of the 2nd Groningen Workshop on Software Variability Management, 2004.
• [ISO09] ISO/IEC. ISO/IEC 25010. Systems and software engineering - Systems and software Quality Requirements and Evaluation (SQuaRE). System and software quality models. ISO/IEC-JTC1/SC7/WG6,2009.
• [TMD09] Taylor R. N., Medvidovic N., and Dashofy E. M., Software Architecture: Foundations, Theory, and Practice. Wiley, January 2009.
• [WB10] Wang W. and Burge J.. Using Rationale to Support Pattern-Based Architectural Design. In Proceedings of the Workshop on Sharing and Reusing Architectural Knowledge. 2010.

• Réaliser une étude bibliographique sur les travaux de contrôle de flux d'information existants [SM03] en approfondissant ceux qui prennent en compte les déclassifications [SS07] et des politiques de sécurité plus expressives [NBG11].
• Proposer une spécification formelle de la politique de flux d’information permettant de mixer différentes types de déclassifications pour étendre l'expressivité de la politique.
• Proposer l'intégration de contre-mesures dans la politique de sécurité pour rendre négligeables voire supprimer les fuites d’information induites par les déclassifications.
• Rédiger un rapport de stage (problématique, état de l’art, approches, solu­tions, etc.).

• [DMLT09] T. Demongeot, J. Mallet and Y. Le Traon. Runtime Verification of Declassification for Imperative Programs: Formal Foundations. In International Conference on Risks and Security of Internet and Systems (CRiSIS 2009), 2009.
• [Gol06] D. Gollmann. Computer Security. John Wiley & Sons, 2nd Edition, 2006.
• [LGBJS06] G. Le Guernic, A. Banerjee, T. Jensen, and D. Schmidt. Automata-based confidentiality monitoring. In Proceedings of the Annual Asian Computing Science Conference, 2006.
• [SM03] A. Sabelfeld and A. Myers. Language-based information-flow security. IEEE J. on selected areas in communications 21, 1, 5—19, 2003.
• [SS07] A. Sabelfeld and D. Sands. Declassification : Dimensions and principles. Journal of Computer Security, 2007.
• [NBG11] A. Nanevski, A. Banerjee and D. Garg.Verification of Information Flow and Access Control Policies via Dependent Types. IEEE Symposium on Security and Privacy , 2011.

La faiblesse des débits montants sur les connexions ADSL reste une limite pour de nombreuses applications en ligne (Picasa, Youtube, Photoweb, RapidShare…). En effet, l’augmentation de la qualité des contenus (vidéos, photos), rend leur envoi vers des sites webs contraignant : l’envoi d’un album de 300 photos ou d’une longue vidéo peut prendre 3-4h. Durant toute la durée de l’envoi, l’utilisateur ne peut ni mettre en veille son terminal, ni le déconnecter, ce qui devient d’autant plus critique que de plus en plus de terminaux sont soit des smartphones, soit des portables, tous alimentés par batteries. Afin d’offrir un service plus commode à l’utilisateur, il serait intéressant d’exploiter les passerelles d’accès (box de FAI qui sont généralement allumées 24h/24h) pour y déporter les tâches longues afin d’autoriser la mise en veille et la déconnexion du terminal.

Nous souhaitons étudier une solution permettant de déporter dynamiquement certaines tâches (exécution de code Javascript, uploads, …) du navigateur vers un composant logiciel sur la passerelle d’accès afin d’autoriser la mise en veille du terminal faisant tourner le navigateur. Afin d’offrir une compatibilité avec les systèmes existants et un déploiement aisé, nous considérerons que seule la passerelle d’accès et éventuellement la partie cliente (navigateur) peuvent être modifiées. Par ailleurs, pour l’utilisateur, l’utilisation du système doit rester quasi inchangée : le déport des tâches doit être transparent.

Cloud computing is increasingly gaining popularity as it enables users to provision computing resources on-demand while paying for their use [1,2]. This paradigm relies on the use of virtualization technologies to provide users with private environments that can be customized by need. Users can elastically scale these environments by adding more resources when needed. "Private cloud" systems attempt to bring these advantages to private infrastructures. However, current resource provisioning models applied by these cloud systems do not provide users with enough feedback about the resource availability of the physical infrastructure. As the infrastructure capacity is limited, users require this feedback to know how many resources they are allowed to use, while the infrastructure needs to differentiate between the importance of their requests.

One approach that we see as an attractive alternative to current models is to provision VMs to users through a proportional-share auction [3]. In this model we allocate to each VM an amount of resource (i.e., CPU) proportional to the amount that the user is willing to pay and inversely proportional to the total resource price [4]. To validate this model, we have implemented a proof-of-concept scheduler on top of the OpenNebula [5] Virtual Infrastructure Manager. This scheduler uses a simple heuristic to allocate resources for each requested VM by using the proportional-share rule described above.

The main goal of this internship is to analyze the existing proportional-share allocation mechanism and extend it to handle multiple resource types beyond CPU. In the first stage, the intern will study the state of the art on VM placement algorithms in datacenters [6,7]. Afterwards, the intern will analyze the existing algorithm in terms of the resource share that VMs actually receive. Following that and based on the related work, the intern will propose an improved algorithm that maximizes the resource allocation for multiple resource types (i.e., memory and network) and takes into account the cost of VM migration. Finally, the intern will implement and integrate the algorithm in the existing scheduler.

[1] AmazonEC2. http://aws.amazon.com/ec2/

[2] http://aws.amazon.com/ec2/spot-instances/

[3] T. Sandholm and K. Lai. Dynamic proportional share scheduling in Hadoop. In 15th Workshop on Job Scheduling Strategies for Parallel Processing, 2010.

[4] S. Costache, N. Parlavantzas, C. Morin and S. Kortas, An economic approach for Application QoS Management in Clouds, Europar 2011, Parallel Processing Workshops, 2011

[5] B. Sotomayor, R. Montero, I. Llorente, and I. Foster. An Open Source Solution for Virtual Infrastructure Management in Private and Hybrid Clouds. IEEE Internet Computing, 13(5):14–22, 2009.

[6] F. Hermenier, X. Lorca, and J.M. Menaud. Entropy: a consolidation manager for clusters. In Proceedings of the 2009 ACM SIGPLAN/SIGOPS international conference on Virtual Execution Environments, 2009.

Cloud computing is increasingly gaining popularity as it enables users to provision computing resources on-demand while paying for their use [1]. This paradigm relies on the use of virtualization technologies to provide users with private environments that can be customized by need. Users can elastically scale these environments by adding more resources when needed. "Private cloud" systems attempt to bring these advantages to private infrastructures. However, current resource provisioning models applied by these cloud systems do not provide users with enough feedback about the resource availability of the physical infrastructure. As the infrastructure capacity is limited, users require this feedback to know how many resources they are allowed to use, while the infrastructure needs to differentiate between the importance of their requests.

To address this problem, we propose to provision virtual machines (VMs) to users through a proportional-share auction [2]. This model allocates to each VM an amount of resource (i.e., CPU) proportional to the amount that the user is willing to pay and inversely proportional to the total resource price [3]. To validate this model, we have implemented a proof-of-concept scheduler on top of the OpenNebula [4] Virtual Infrastructure Manager. When using this model, a key challenge is how to react to changes in market prices to meet application performance requirements (e.g., deadlines).

[1] AmazonEC2. http://aws.amazon.com/ec2/

[2] S. Costache, N. Parlavantzas, C. Morin and S. Kortas, An economic approach for Application QoS Management in Clouds, Europar 2011, Parallel Processing Workshops, 2011

[3] T. Sandholm and K. Lai. Dynamic proportional share scheduling in Hadoop. In 15th Workshop on Job Scheduling Strategies for Parallel Processing, 2010

[4] B. Sotomayor, R. Montero, I. Llorente, and I. Foster. An Open Source Solution for Virtual Infrastructure Management in Private and Hybrid Clouds. IEEE Internet Computing, 13(5):14–22, 2009.

• guided interaction for multidimensional and aggregation queries,
and its impact on the user interface of Sewelis
• integration with OLAP visualization tools
• nested aggregation queries, such as "the average, per month,
of the sum of the sales per shop"

• guided interaction for defining dimensions as a function of several attributes through a formula (like in spreadsheets): e.g., the weighted average mark per student
• guided interaction for defining a relation as a function of other relations: e.g., the age of people from their birthdate
• the integration with semantic data of domain-specific functions and aggregations, e.g., for handling temporal and spatial values

• enregistrement pendant le stage: emails, fichiers, log machine (ex., acces fichiers), log web (ex., acces pages), photos, evenements avec personnes presentes, contacts
• collecte d'usages et recherches types (extensionel et intensionel)
• acquisition et modelisation des donnees
• modules logiques et contextuels pour proprietes et relations
• validation modelisation viz. usages
• experimentation avec Sewelis

• d'analyser les méthodes existantes et les problèmes rencontrés dans la fouille de grands graphes et dans la fouille de données de avec intervalles temporels,
• de proposer un algorithme pour la fouille de grand graphe avec contraintes numériques,
• d'analyser les propriétés des algorithmes proposés,
• de développer et tester les algorithmes sur des données simulées et réelles (données de la Zone Atelier Armorique).

Une des approche utilisée dans le domaine de la détection d'intrusions consiste à contrôler dynamiquement les flux d'information qui résultent de l'exécution des programmes sur le système surveillé. Les travaux successifs réalisés au sein de l'équipe CIDre ont conduit à la proposition de différentes approches pour réaliser ce contrôle. Ces approches ont elles-mêmes donné lieu au développement de différents prototypes.

Ainsi, Blare [8, 7, 3], une version modifiée du noyau Linux, permet le suivi dynamique, au niveau OS, des flux d'information. Cette approche permet facilement de suivre l'ensemble des flux d'information d'un système tout en limitant le surcoût à l'exécution. Toutefois, il s'agit d'une approche "gros grain" qui ne permet pas de suivre finement les flux d'information générés par un programme donné (le comportement de chaque application est fortement sur-approximé).

Cette limitation nous a conduit à proposer une deuxième approche où le contrôle dynamique des flux d'information est réalisé au niveau de la machine virtuelle Java (JVM) [2, 4, 3]. Cette deuxième approche permet certes un suivi plus précis (au niveau de chaque variable du programme) des flux d'information mais elle présente les limitations suivantes :

• l'approche purement dynamique du contrôle ne permet pas de suivre correctement les flux d'information indirects résultant des branchements conditionnels;
• la précision du suivi se fait au détriment d'une dégradation importante des performances à l'exécution des programmes surveillés.

• une analyse statique du bytecode de chaque méthode du programme surveillé est réalisée hors-ligne ou lors du chargement;
• le contrôle des flux d'information à proprement parler est réalisé dynamiquement en s'appuyant sur les résultats de l'analyse statique.

Dans cette approche, la pré-analyse statique permet d'une part de prendre en compte les flux indirects et d'autre part de limiter les opérations réalisées dynamiquement pour le suivi et le contrôle des flux d'information, ce qui permet donc de limiter le surcoût à l'exécution.

Lors de son stage de Master 2 réalisé en 2011 dans l'équipe CIDre, Mounir Assaf a proposé une telle approche. Plus précisément, il a proposé une analyse statique qui permet de déterminer, en différents points d'une méthode Java, des dépendances entres variables. L'ensemble de ces dépendances constitue le "profil" d'une application Java qui est stocké dans le bytecode de l'application sous la forme d'annotations Java. Mounir Assaf a également modifié une JVM afin qu'elle puisse réaliser un contrôle purement dynamique des flux d'information ou un contrôle hybride en s'appuyant sur les profils calculés au préalable. Ce prototype, H-JBlare, permet donc de comparer les deux approches.

Les résultats obtenus sont encourageants et montrent l'intérêt d'une telle approche, notamment en ce qui concerne la diminution du surcoût à l'exécution. Toutefois, l'analyse statique mise en œuvre dans H-JBlare reste rudimentaire et aucune preuve de correction du contrôle de flux n'a été établie. L'objectif du stage proposé pour l'année 2011/2012 consiste à poursuivre ces travaux en améliorant l'analyse statique.

Par ailleurs, l'équipe CELTIQUE s'intéresse à la certification des programmes, afin d'assurer notamment la sécurité. Elle a proposé différentes approches d'analyse statique pour différents langages et propriétés. Elle s'est notamment intéressé à l'analyse statique de bytecode Java et elle a développé Sawja [5], une bibliothèque OCaml permettant d'implémenter des analyses statiques de bytecode Java. Contrairement aux autres outils existants, il a été prouvé, pour cette bibliothèque, que la transformation vers un langage intermédiaire, sur lequel porte l'analyse, préserve la sémantique originale de la méthode analysée. L'utilisation de cette bibliothèque permettrait donc à terme d'initier la preuve de la correction du contrôle des flux d'information dans H-JBlare.

Le stage consistera dans un premier temps à porter l'analyse statique mise en oeuvre dans H-JBlare en utilisant Sawja. Dans un second temps, il s'agira d'améliorer cette analyse statique afin de limiter le nombre de points de contrôle et ainsi diminuer la dégradation des performances à l'exécution. L'étudiant devra implémenter et valider expérimentalement l'approche proposée : mesure de l'impact sur les performances, vérification d'une politique sur des cas simples puis sur des applications réalistes (Eclipse, Jetty, Tomcat, etc.).

Le stage sera principalement réalisé à Supélec au sein de l'équipe CIDre. Ponctuellement, l'étudiant pourra être amené à travailler dans les locaux de l'INRIA au sein de l'équipe CELTIQUE.

A major research topic in the context of HPC simulations running on Post-Petascale supercomputers is to explore how to efficiently record and visualize data during the simulation without impacting the performance of the corresponding computation generating that data, that is to say by improving I/O efficiency without introducing any additional jitter. Conventional practice of storing data on disk, moving it off-site, reading it into a workflow, and analyzing it to produce scientific solutions becomes increasingly harder to the use due to large data volumes generated at fast rates compared to limited backend speeds. Scalable approaches to deal with these I/O limitations are thus of utmost importance.

In this context, the KerData joint team of INRIA Rennes - Bretagne Atlantique and ENS Cachan - Bretagne started to explore ways to remove the limitations mentioned above through a collaborative work in the framework of the Joint INRIA-UIUC Lab for Petascale Computing (Urbana-Champaign, USA). Our preliminary investigations on the I/O behavior of a sample application (the CM1 atmospheric model) showed the inefficiency of current I/O approaches, which either consists in writing large amounts of small files periodically, or writing a set of shared files using collective I/O. These approaches produce burst of I/O in the parallel file system, leading to poor performance and extreme variability compared to what could be expected from the underlying hardware. We then proposed a new approach called Damaris (Dedicated Adaptable Middleware for Application Resources Inline Steering), which leverages one dedicated core in each multicore SMP node to perform I/O and data post-processing asynchronously. By keeping data longer in main memory, Damaris is able to make an efficient use of the underlying file system by avoiding synchronization and contention as much as possible.

Le stage se déroulera dans le contexte des applications accédant intensivement des données (recherche textuelle dans des documents, simulation scientifique) [1]. Les accès disques et les transferts de données constituent des goulots d'étranglement qui deviennent critiques pour l'exploitation efficace des plateformes de calcul à large échelle. En effet, la croissance des capacités disque et réseau en terme de vitesse est moindre que celle des moyens de calcul tandis que la quantité de données à traiter croit exponentiellement.

Pour répondre à ces besoins de traitement, la plateforme MapReduce a été proposée par Google. L'architecture a ensuite été reprise dans le projet libre Hadoop [2]. Les applications s'appuyant sur MapReduce se décomposent en un ensemble de tâches accédant chacune à des données. Les résultats sont ensuite regroupés par une opération de réduction. Considérer des applications MapReduce fournit un cadre restreint qui permet de délimiter un problème plus spécifique tout en étant général en terme d'applications.

L'architecture MapReduce repose sur un système de fichiers optimisé (GFS pour l'implémentation de Google et HDFS [3] pour Hadoop). Les tâches sont placées au plus près des données afin de limiter les temps de communication. Cependant, les algorithmes utilisés sont peu élaborés et ne prennent pas en compte les caractéristiques de la plateforme matérielle.

L'équipe KerData développe un outil, BlobSeer [4], gérant efficacement des données. Il se base sur plusieurs principes tels que la segmentation et le versionnage des données, une gestion distribuée des métadonnées, etc. Malgré des performances avantageuses par rapport à HDFS, sa stratégie de placement se limite à distribuer les données de façon uniforme et à les répliquer dans une logique de fiabilité.

Il existe donc une opportunité pour gérer plus finement les données et accélérer les temps de traitement. Il semble par exemple intuitif de regrouper les données qui sont peu accédées sur quelques machines pour laisser davantage de bande-passante à celles fréquemment utilisées. De plus, adapter le taux de réplication des données en fonction de leur usage et des capacités de la plateforme soulève un problème algorithmique non-trivial. Le placement des données dans les infrastructures de calcul fait d'ailleurs l'objet d'études récentes [5,6].

L'objectif du stage sera de mettre au point une solution plaçant efficacement les utilisées par une application MapReduce. Plusieurs étapes sont envisagées : modélisation et formulation mathématique du problème ; conception d'algorithmes de placement de données ; implémentation de ces stratégies au sein de BlobSeer ; validation expérimentale par le biais d'applications MapReduce.

[1] "Data-Intensive Technologies for Cloud Computing," A.M. Middleton. Handbook of Cloud Computing. Springer, 2010.

[2] "The hadoop distributed file system: Architecture and design", D. Borthakur, Hadoop Project Website, 2007.

[3] "HDFS architecture", D. Borthakur, Hadoop 0.19 Documentation, 2008.

[4] "Blobseer: Next generation data management for large scale infrastructures", Bogdan Nicolae, Gabriel Antoniu, Luc Bougé, Diana Moise, Alexandra Carpen-Amarie, Journal of Parallel and Distributed Computing 71:2, 2011.

[5] "A data placement strategy in scientific cloud workflows", D. Yuan, Y. Yang, X. Liu, J. Chen, Future Generation Computer Systems, 2010.

Managing data at a large scale has become a critical requirement in a wide spectrum of research domains. BlobSeer [1] is a service developed by the KerData team at INRIA Rennes - Bretagne Atlantique with this goal, able to share massive data at very large scale under high concurrency. A first step towards BlobSeer’s performance improvement and resource-usage optimization consisted in enabling its autonomic behavior based on introspection [2].

However, self-adaptation incurs a high degree of complexity in the configuration and tuning of the system, with possible repercussions on its availability and reliability. We therefore plan to complement this approach by a comprehensive performance model of BlobSeer. Its role is to capture how the system’s components interact for different operations (read / write) and to identify the relevant parameters to adjust, costs incurred or the maximum workload thresholds.

[1] Bogdan Nicolae, Gabriel Antoniu, Luc Bouge, Diana Moise, and Alexandra Carpen-Amarie. 2011. BlobSeer: Next-generation data management for large scale infrastructures. J. Parallel Distrib. Comput. 71, 2 (February 2011), 169-184.

L'analyse statique de programme par interprétation abstraite [1] est une méthodologie pour prouver automatiquement des propriétés de sûreté et de sécurité des programmes. Il s'agit d'une méthode formelle qui établit une théorème de correction vis-à-vis de la sémantique des programmes. Cette méthodologie est utilisée avec succès pour construire des modèles abstraits de programmes sources.

L'analyse de code binaire comporte des difficultés supplémentaires [2]. Les buts de ce stage sont d'identifier les défis supplémentaires pour l'analyse de malware et de proposer une analyse statique pour du code binaire qui soit adaptée aux caractéristiques spécifiques des malware. Pour la partie pratique de ce stage, on étendra la plateforme BAP [3] qui est une bibliothèque OCaml pour l'analyse de code binaire.

JavaScript est un des langages de script les plus utilisés pour étendre les fonctionnalités de pages web. On le rencontre par exemple dans de nombreux outils Google (tels Google Maps ou Gmail). Bien qu’il possède une spécification standardisée, sa sémantique n’est pas donnée de manière formelle.

L’objectif de ce stage est de définir une sémantique formelle de JavaScript dans l’assistant de preuves Coq en se basant sur un travail définissant sa sémantique opérationnelle [1]. Ce développement pourra être utilisé pour extraire un interpréter certifié de JavaScript, ainsi que pour prouver plusieurs résultats comme la correction de la traduction de JavaScript en λJ [2]. Plusieurs extensions seront ensuite possibles, comme l’addition d’un système de types [3] ou la formalisation des API donnant accès au navigateur et au HTML DOM.

Il est recommandé d’avoir suivi le cours “Analyse de programmes pour la sécurité logicielle”.

Les systèmes distribués sont souvent modélisés par des calculs de processus. Pour étudier des systèmes échangeant des programmes, on utilise des calculs de processus d’ordre supérieur: ce sont des calculs de processus qui peuvent échanger des processus.

HOCore [1] est un calcul de processus d’ordre supérieur minimal, semblable à un lambda-calcul concurrent, possédant l’étrange propriété d’être Turing puissant (donc la terminaison est indécidable) mais dont la notion d’équivalence naturelle est décidable.

L’objectif de ce stage est de prouver ce résultat dans l’assistant de preuve Coq, en se basant sur des premiers résultats et des techniques développées dans le cadre du projet ANR PiCoq. Cette modélisation présente de nombreuses opportunités de développement: encodage de machines de Minsky, preuves impliquant différentes formes de bisimulations, ou encodage du problème de correspondance de Post.

In recent years, Infrastructure as a Service (IaaS) cloud computing has emerged as a viable alternative to the acquisition and management of physical resources. With IaaS, user rent a theoretically unlimited number of virtual machines that they can use to build huge virtual environments. Such virtual environments are increasingly appealing as a non-expensive solution for running High Performance Computing (HPC) applications that are traditionally built for supercomputing infrastructures, which often are out of reach to many users due to high acquisition and operational costs.

In this context, an assumption about complete reliability is highly unrealistic: at such large scale, hardware component failure is the norm rather than the exception. Traditionally this problem has been addressed using checkpoint-restart [1]: capture the application state at regular intervals and restart from such states in case of failures, thus greatly reducing the amount of lost computation. However, with increasing scale the failure rate increases as well, which leads to the need for frequent checkpoints. While there are efficient approaches to checkpoint the application state of HPC applications running in IaaS clouds (such as BlobCR[2]: BlobSeer[3]-based Checkpoint-Restart), performance degradation with increasing checkpointing frequency is inevitable.

[1] E. N. M. Elnozahy, L. Alvisi, Y.-M. Wang, and D. B. Johnson. A survey of rollback-recovery protocols in message-passing systems. ACM Comput. Surv., 34:375–408, September 2002.

[2] B. Nicolae and F. Cappello, "BlobCR: Efficient Checkpoint-Restart for HPC Applications on IaaS Clouds using Virtual Disk Image Snapshots," in Proc. SC '11: 24th International Conference for High Performance Computing, Networking, Storage and Analysis, Seattle, USA, 2011.

Les langages contrôlés sont des langages artificiels utilisant un sous-ensemble du vocabulaire, des formes morphologiques, des constructions grammaticales et des interprétations sémantiques d'une langue naturelle (dans notre cas : le français). En quelque sorte ils constituent le pont entre les langages formels et les langues naturelles. De ce fait, ils remplissent la fonction de communication du médium texte tout en étant rigoureux et analysables par la machine sans ambiguïté.

En particulier, ils peuvent être utilisés pour faciliter l'alimentation de bases de connaissances, dans le cadre d'une interface homme-machine au moment de la saisie du texte.

Le Service Hydrographique et Océanographique de la Marine (SHOM) publie depuis plusieurs années les Instructions Nautiques, un recueil de renseignements généraux, nautiques et réglementaires, destinés aux navigateurs. Ces informations complètent les cartes marines. Elles sont obligatoires à bord des navires de commerce et de pêche.

L'Organisation Hydrographique Internationale (OHI) a publié des normes spécifiant l'échange de données liées à la navigation et notamment un modèle universel de données hydrographiques (norme S-100, janvier 2010).

Le but de ce stage est d'élaborer un langage contrôlé qui couvre les besoins des Instructions Nautiques et qui permette l'alimentation de bases de connaissances conformes à la norme S-100.

Dans le contexte d'une thèse CIFRE, deux applications seront envisagées : (a) une interface homme-machine qui analyse en temps réel le texte saisi par l'opérateur des Instructions Nautiques et qui valide son appartenance au langage contrôlé ; (b) un outil semi-automatique de traduction des documents existants dans le langage contrôlé.

Ce stage se concentrera sur la faisabilité d'un langage contrôlé qui satisfasse les deux contraintes : adéquation avec le contenu traditionnel des Instructions Nautiques et avec la norme S-100. Un prototype de langage sera élaboré, accompagné des algorithmes d'extraction de connaissances et d'alimentation d'une base de connaissance conforme à la norme S-100.

Ce stage est proposé en collaboration avec le SHOM.

Rolf Schwitter: Controlled Natural Languages for Knowledge Representation http://web.science.mq.edu.au/~rolfs/papers/coling10-schwitter.pdf

Wyner et al. On Controlled Natural Languages: Properties and Prospects. CNL 2009 Workshop, LNAI 5972, p. 281--289, 2010 http://omega2.enstb.org/html/yannis/17.pdf

SHOM Instructions Nautiques http://www.shom.fr/fr_page/fr_shom/Fiche_produits/fiche_ins.naut.pdf http://www.shom.fr/fr_page/fr_prod_ouvrage/inaut.htm

Normes de l'OHI http://www.iho.int/iho_pubs/IHO_Download.htm#S-100

L’extension de jeux d’instructions constitue une approche efficace pour l’accélération des performances de processeurs embarqués. L’accélération consiste alors à déporter les parties critiques de l’application sur du matériel spécialisé. Ceci est réalisé, d’une part en ajoutant des unités fonctionnelles spécialisées fortement couplées au chemin de données du processeur, et d’autre part en étendant le jeu d’instructions du processeur pour permettre l’exécution de ces parties critiques sur ces unités fonctionnelles. Le concepteur réalise, encore souvent, cette tâche complexe et critique de sélection de ces nouvelles instructions à la main.

Quelques méthodes automatiques traitant de l’extension de jeux d’instructions de processeurs existent [1], elles ont montré des résultats intéressants mais elles sont souvent limitées dans la façon dont elle traite les instructions d’accès à la mémoire. La bande passante entre le chemin de données du processeur et l’extension étant limitée, il en résulte une pénalité importante induite par les mouvements de données, limitant ainsi l’accélération.

[1] Carlo Galuzzi, Koen Bertels, The Instruction-Set Extension Problem: A Survey, ACM Transactions on Reconfigurable Technology and Systems, 2010.

[2] Partha Biswas, Nikil D. Dutt,Laura Pozzi, Paolo Ienne, Introduction of Architecturally Visible Storage in Instruction Set Extensions, IEEE Trans. on CAD of Integrated Circuits and Systems, 2007.

La découverte de motifs sonores est une tâche émergente qui consiste à trouver dans un signal sonore des portions de signal répétés avec une certaine variabilité, sans aucune connaissance a priori sur les motifs potentiellement présents. Suivant l'application visée, les motifs recherchés peuvent être peu variable d'une instance à l'autre (chansons répétés à la radio, publicités, etc.) [1,2] ou, au contraire, présenter une forte variabilité (cas des mots et locutions répétés dans les données de parole) [3,4].

Une approche naïve de la découverte de motifs nécessite de comparer tous les segments possibles entre eux, ce qui est inconcevable. Les techniques proposées pour résoudre ce problème font appel à des stratégies de restriction du nombre de comparaison et s'appuient, tant pour des motifs faiblement variables que pour les motifs hautement variables, sur des techniques de comparaison de motifs (pattern matching), coûteuse en temps de calcul, limitant ainsi le passage à l'échelle des technologies de découverte de motifs [2]. En parallèle, les techniques d'indexation sonore permettent de retrouver de manière extrèmement efficace (en terme de temps de calcul) les plus proches voisins d'une portion de signal requête [5]. Ces techniques d'indexation restent cependant peu étudiés dans le cadre de la découverte de motifs dans des données sonores.

L'objectif du stage est d'étudier l'apport des techniques d'indexation pour la découverte de motifs sonores afin de permettre un passage à l'échelle. On s'intéressera pour cela à différents aspects de la question : comparaison de techniques d'indexation, graphes de plus proches voisins approximatifs, indexing based fast match, fingerprinting, etc. On étudiera l'apport des techniques d'indexation dans deux cas d'étude : la découverte de chansons et publicités dans les flux radios (faible variabilité) et la découverte de mots dans des documents oraux (forte variabilité), en s'efforcant de montrer le potentiel et les limites des différentes techniques d'indexation dans ces deux cadres.

[1] Cormac Herley. ARGOS: Automatically extracting Repeating Objects from multimedia Streams. IEEE Trans. on Multimedia, 8(1), 2006.

[2] Armando Muscariello, Guillaume Gravier and Frédéric Bimbot. An efficient method for the unsupervised discovery of signalling motifs in large audio streams. Proc. Content Based Multmedia Indexing, 2011.

[3] Alex Park and James Glass. Unsupervised Word Acquisition from Speech using Pattern Discovery. Proc. Intl. Conf. on Acoustics, Speech and Signal Processing, 2006.

[4] Armando Muscariello, Guillaume Gravier, Frédéric Bimbot. Audio keyword extraction by unsupervised word discovery. Proc. Conf. of the Intl. Speech Communication Association (Interspeech), 2009.

• G. Wachsmuth, “Metamodel adaptation and model co-adaptation,” in Proceedings of the 21st European Conference on Object-Oriented Programming (ECOOP’07), ser. Lecture Notes in Computer Science, E. Ernst, Ed., vol. 4609. Springer-Verlag, jul 2007, pp. 600–624.
• S. Markovic and T. Baar, “Refactoring OCL annotated UML class diagrams,” Software and System Modeling, vol. 7, no. 1, pp. 25–47, 2008.
• M. Herrmannsdoerfer, S. Benz, and E. Juergens, “Automatability of coupled evolution of metamodels and models in practice,” in MoDELS ’08: Proceedings of the 11th international conference on Model Driven Engineering Languages and Systems. Berlin, Heidelberg: Springer- Verlag, 2008, pp. 645–659.
• M. Giese and D. Larsson, “Simplifying Transformations of OCL Constraints,” in MoDELS, 2005, pp. 309–323.

Context

Real time systems do not only have to provide correct results, but also have to provide them under quantified time constraints, typically deadlines. Two dinstinct trends exist for scheduling task sets on unicore systems: non preemptive and preemptive scheduling. Under preemptive scheduling, for instance Earliest Deadline First (EDF) scheduling, a task may be preempted at any point in time when a higher priority task arrives (for EDF, a task with a deadline earlier than those of the task under execution). Preemptions obviously result in preemption delays. Cache related preemption delays (CRPD) are the most important ones, and are caused by the preempted tasks that modify the cache; the preempted task then suffers an indirect delay after the preemption to reload the cache with useful information. Several techniques exist to estimate upper bounds of cache-related preemption delays [1,2]. In comparison, non preemptive scheduling policies, by definition, does not suffer from any preemption delay.

Although preemptive EDF was demonstrated as optimal (always able to meet deadlines if a feasible schedule exists), optimality is guaranted only when practical factors such as preemption delays are ignored. In contrast, non preemptive scheduling, although not optimal, do not suffer from preemption delays. In between, limited preemptive scheduling [3,4,5] aim at conjugate both word's benefits, by limiting preemption points (and then preemption delays).

Internship

The objective of the internship is propose and evaluate a new limited preemptive scheduling policy having the following properties :

• ability to compute cache-related preemption delays (CRPDs) and have CRPDs as low as possible
• ability to demonstrate that all tasks in the system meet their deadlines

In contrast to existing work, the proposed scheduling policy will account for the practical factors that are CRPDs, and will use real CRPD values to determine the system feasibility. The proposed limited preemptive scheduling policy will be compared to fully preemptive, non preemptive scheduling, and possibly other hybrid scheduling schemes, in terms of feasibility. A first step will be to examine the floating non-preemptive region scheduling policy described in [6].

The internship will be co-supervised by Isabelle Puaut (IRISA Rennes) and Stefan M. Petters (ISEP, Porto). There will be regular contacts between IRISA and ISEP during the internship duration; part of the internship may be spent in Porto.

[1] C.-G. Lee, J. Hahn, Y.-M. Seo, S. L. Min, R. Ha, S. Hong, C. Y. Park, M. Lee, and C. S. Kim, “Analysis of cache-related preemption delay in fixed-priority preemptive scheduling,” IEEE Transactions on Computers, vol. 47, no. 6, 1998.

[2] S. Altmeyer, R. I. Davis, and C. Maiza, “Pre-emption cost aware response time analysis for fixed priority pre-emptive systems,” in 32nd RTSS, nov 2011.

[3] M. Bertogna and S. Baruah, “Limited preemption EDF scheduling of sporadic task systems,” IEEE Transactions on Industrial Informatics, vol. 6, no. 4, nov. 2010.

[4] G. Yao, G. Buttazzo, and M. Bertogna, “Feasibility analysis under fixed priority scheduling with limited preemptions,” Journal Real-Time Systems, vol. 47, no. 3, 2011.

[5] M. Bertogna, O. Xhani, M. Marinoni, F. Esposito, and G. Buttazzo, “Optimal selection of preemption points to minimize preemption overhead,” in 23th RTSS, Jun 2011.

[6] J. Marinho, V. Nelis, I. Puaut, S. M. Petters "Preemption Delay Analysis for Floating Non-Preemptive Region Scheduling" - under submission to DATE 2012

Context

Multicore processors have now become mainstream for both general-purpose and embedded computing. Many applications running on multicore platforms, for instance multimedia applications, feature (soft or hard) real-time requirements. Many scheduling policies and associated schedulability analysis methods have been devised for both uniprocessors and multiprocessors. Schedulability analysis methods take as inputs a description of the system (tasks arrival law, e.g. tasks periods, tasks worst-case execution times - WCET [3]) and determine if tasks deadlines will be met or not.

Regarding multiprocessors, scheduling techniques can be divided in two categories: global scheduling (e.g. global Earliest Deadline First) allow task migrations between cores, while partitioned scheduling assign tasks to cores statically and do not allow migrations. Global scheduling was shown to result in higher core utilization than partitioning.

Most schedulability analysis methods for multicores assume that tasks WCETs are constant, regardless of the tasks execution context, for instance tasks running on the other cores. This is not however not true in practice [2,4]. On multicores with shared caches, a task WCET depends in the cache usage of the tasks running on the other cores. When cache partitioning is used, a task WCET depends on the size of the cache partition assigned to the core.

Internship

The objective of this internship is to integrate the practical aspects stemming from shared caches in the definition of multicore scheduling algorithms. As a first step, a multicore architecture with a shared cache partitioned among the cores [1], and partitioned non-preemptive scheduling, will be assumed.

The problem will then be to define heuristics or exact methods for joint task placement and assignment of partition sizes, most efficient than the early work described in [5]. The next step will be to compare such an approach with global scheduling approaches with a dynamically shared cache.

[1] Bach D. Bui, Marco Caccamo, Lui Sha, Joseph Martinez, Impact of Cache Partitioning on Multi-Tasking Real Time Embedded Systems, RTCSA 2008.

[2] Calandrino, J.M.; Anderson, J.H., Cache-Aware Real-Time Scheduling on Multicore Platforms: Heuristics and a Case Study, ECRTS 2008

[3] Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David B. Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Tulika Mitra, Frank Mueller, Isabelle Puaut, Peter P. Puschner, Jan Staschulat, Per Stenstrom: The worst-case execution-time problem - overview of methods and survey of tools. ACM Trans. Embedded Comput. Syst. 7(3): (2008)

[4] Damien Hardy, Thomas Piquet and Isabelle Puaut, Using Bypass to Tighten WCET Estimates for Multi-Core Processors with Shared Instruction Caches, IEEE Real-Time System Symposium (RTSS), dec 2009.

[5] Marco Paolieri, Eduardo Quiñones, Francisco J. Cazorla, Robert I. Davis, Mateo Valero:
IA3: An Interference Aware Allocation Algorithm for Multicore Hard Real-Time Systems. 280-290, RTAS 2011, Chicago, USA.

Context

In order to execute efficiently upcoming applications on a large spectrum of hardware platforms, the computer science community has to invent a new form of application portability that will replace the traditional binary compatibility. Processor virtualization can be used to address this portability issue [1]. Applications are no longer directly compiled in the final native code, but in a target independent bytecode format. The final native code generation is delayed till the executing target is known. It can even occur at run-time through just-in-time compilation (JIT).

Many applications running on multicore platforms, for instance multimedia applications, feature (soft or hard) real-time requirements. For such applications, predicting as precisely as possible worst-case execution time (WCET) of pieces of software is required to demonstrate that the applications meets is time constraints, in all situations including the worst case. Many WCET estimation methods have been defined [2], and operate through static code analysis, measurements or a combination of both. A static WCET analysis tool should be able to work at a high-level to determine the structure of a program's task. But it should also work at a low-level, using timing information about the real hardware that the task will execute on, with all its specific features. By combining those two kinds of analysis, the tool should give an upper bound on the time required to execute a given task on a given hardware platform.

Internship

Our overall objective is to investigate how to reconcile the benefits of virtualization and just-in-time compilation, with the real-time guarantees. A preliminary study towards this ambitious goal has been conducted last year, through the proposal of a predictable binary code cache [3]: the benefits of the proposal are to decrease the number of times a function has to be compiled at run-time, and at the same time allowing to determine how many compilations / re-compilations at worst will occur.

The goal of the internship is to go one step forward the use of JIT compilers in real-time systems, though a deeper study of the worst-case execution time of the JIT compiler itself. Due to the inherent difficulty of applying static WCET estimation methods on complex codes such as the code of a compiler, measurement based methods will be used. The internship will be decomposed in two main steps :

1. investigation, through automatic instrumentation of a compiler, of the reasons behind undeterministic compilation times: optimization phases, code generation, memory management, underlying hardware, etc.
2. for the most undeterministic features, proposal of more deterministic features (e.g. real-time memory allocation, time predictable optimization algorithms, etc)

Experiments will be conducted in a compiler platform such as LLVM, Mono or Gcc (yet to be decided).

[1] Marco Cornero, Roberto Costa, Ricardo Fernández Pascual, Andrea C. Ornstein, and Erven Rohou. An experimental environment validating the suitability of CLI as an effective deployment format for embedded systems. In Proceedings of the 2008 International Conference on High Performance and Embedded Architectures and Compilers (HiPEAC'08), pages 130-144, Goteborg, Sweden, January 2008. Lecture Notes in Computer Science 4917.

[2] Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David B. Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Tulika Mitra, Frank Mueller, Isabelle Puaut, Peter P. Puschner, Jan Staschulat, Per Stenström: The worst-case execution-time problem - overview of methods and survey of tools. ACM Trans. Embedded Comput. Syst. 7(3): (2008)

1. la première appelé "active learning", consiste à faire annoter à un humain un premier jeu de donnée tiré aléatoirement puis de s'en servir pour entrainer un système automatique (algorithme d'apprentissage automatique). Le système est ensuite utilisé pour annoter le reste des données disponibles. Le système fourni une mesure de confiance sur son annotation et les données annotés avec le minimum de confiance sont sélectionnées pour être annotées manuellement: ce sont les données sur lesquelles le système se juge inefficace et qui a priori seront les plus utiles. Cette méthode [2] permet de réduire fortement le nombre de données à étiqueter manuellement tout en maintenant un système d'une efficacité équivalente.
2. la seconde, consiste, lorsque l'on possède déjà des données annotées sur une tâche similaire, à utiliser un système automatique appris sur ces données pour pré-annoter les nouvelles données et ensuite les faire corriger par des humains [3,5] ce qui est en général moins couteux que d'annoter à partir de zéro.

1. du point de vue des performances des méthodes statistiques (retrait de la phase d'apprentissage des exemples détectés comme mal annotés)
2. du point de vue du coût en supervision humaine lors de la phase d'annotation si l'on ne demande à corriger que les exemples détectés comme erronés