Lifo - Laboratoire d'Informatique Fondamentale d'orléans INSA Centre Val de Loire Université d'Orléans Université d'Orléans

Lifo > Les rapports de recherche du LIFO en 2011

 English Version



Contact

LIFO - Bâtiment IIIA
Rue Léonard de Vinci
B.P. 6759
F-45067 ORLEANS Cedex 2

Email: contact.lifo
Tel: +33 (0)2 38 41 70 11
Fax: +33 (0)2 38 41 71 37



Accéder aux Rapports de l'année : 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017

Les rapports de recherche du LIFO en 2011


RR-2011-01 On (K_q,k) stable graphs with small k.
Jean-Luc FOUQUET, Henri THUILLIER, Jean-Marie VAHERPE, Pawel WOJDA.
Date : 2011-01-28
Résumé Télécharger

RR-2011-02 Coherence and Performance for Interactive Scientific Visualization Applications
Sébastien Limet, Sophie Robert, Ahmed Turki
Date : 2011-03-08
Résumé Télécharger

RR-2011-03 Solving Q-SAT in bounded space and time by geometrical computation (extended version).
Denys Duchier, Jérôme Durand-Lose, Maxime Senot.
Date : 2011-03-24
Résumé Télécharger

RR-2011-04 Characterizing Conclusive Approximations by Logical Formulae
Y. Boichut, T.-B.-H. Dao, V. Murat
Date : 2011-03-18
Résumé Télécharger

RR-2011-05 Parallel Programming with Orléans Skeleton Library
Noman Javed, Frédéric Loulergue
Date : 2011-04-12
Résumé Télécharger

RR-2011-06 A Formal Programming Model of Orléans Skeleton Library
Noman Javed, Frédéric Loulergue
Date : 2011-04-12
Résumé Télécharger

RR-2011-07 Weak Inclusion for XML Types (full version)
Joshua Amavi, Jacques Chabin, Mirian Halfeld Ferrari, Pierre Réty
Date : 2011-04-26
Résumé Télécharger

RR-2011-08 A Security-Aware Scheduler for Virtual Machines on IaaS Clouds
Zaina Afoulki, Zaina Afoulki, Jonathan Rouzaud-Cornabas
Date : 2011-05-13
Résumé Télécharger

RR-2011-09 A Trust Aware Distributed and Collaborative Scheduler for Virtual Machines in Cloud
Jonathan Rouzaud-Cornabas
Date : 2011-05-13
Résumé Télécharger

RR-2011-10 2nd International Workshop on New Worlds of Computation (NWC 2011)
Jérôme Durand-Lose (chair), Maxime Senot, Mathieu Chapelle
Date : 2011-06-09
Résumé Télécharger

RR-2011-14 From Manual Cyber Attacks Forensic to Automatic Characterization of Attackers’ Profiles
J. Briffaut, P. Clemente, J.-F. Lalande, J. Rouzaud-Cornabas
Date : 2011-07-21
Résumé Télécharger

RR-2011-15 ANR AGAPE - Implémentation d'algorithmes exacts pour le problème du stable maximum
Vincent Levorato
Date : 2011-07-25
Résumé Télécharger

RR-2011-16 ANR AGAPE - Implémentation du problème de couverture minimum et applications d'algorithmes exacts paramétrés aux graphes aléatoires
Vincent Levorato
Date : 2011-07-25
Résumé Télécharger

RR-2011-17 On minimum (K_q,k) stable graphs
Jean-Luc FOUQUET, Henri THUILLIER, Jean-Marie VAHERPE, Pawel WOJDA
Date : 2011-12-06
Résumé Télécharger


Résumés des rapports de recherche


RR-2011-01 On (K_q,k) stable graphs with small k.
Jean-Luc FOUQUET, Henri THUILLIER, Jean-Marie VAHERPE, Pawel WOJDA.
Résumé : A graph G is (K_q,k) (vertex) stable if it contains a copy of K_q after deleting any subset of k vertices. We show that for q > 5 and k < q/2 +2 the only (K_q,k) stable graph with minimum size is isomorphic to K_{q+k}.
Mot(s) Clé(s) : Stable graph.

RR-2011-02 Coherence and Performance for Interactive Scientific Visualization Applications
Sébastien Limet, Sophie Robert, Ahmed Turki
Résumé : This paper addresses the use of component-based development to build interactive scientific visualization applications. Our overall approach is to make this programming technique more accessible to non-computer-scientists. Therefore, we present a method to, out of constraints given by the user, automatically build and coordinate the dataflow of a real-time interactive scientific visualization application. This type of applications must run as fast as possible while preserving the accuracy of their results. These two aspects are often conflicting, for example when it comes to allowing message dropping or not. Our approach aims at automatically finding the best balance between these two requirements when building the application. An overview of a prototype implementation based on the FlowVR high-performance middleware is also given.
Mot(s) Clé(s) : Composition, Coherence, Coordination, Synchronization

RR-2011-03 Solving Q-SAT in bounded space and time by geometrical computation (extended version).
Denys Duchier, Jérôme Durand-Lose, Maxime Senot.
Résumé : Abstract geometrical computation can solve PSPACE-complete problems efficiently: any quantified boolean formula, instance of Q-SAT, the problem of satisfiability of quantified boolean formula, can be decided in bounded space and time with simple geometrical constructions involving only drawing parallel lines on an Euclidean space-time. Complexity as the maximal length of a sequence of consecutive segments is quadratic. We use the continuity of the real line to cover all the possible boolean valuations by a recursive tree structure relying on a fractal pattern: an exponential number of cases are explored simultaneously by a massive parallelism.
Mot(s) Clé(s) : Abstract geometrical computation; Signal machine; Q-SAT; Fractal computation; Massive parallelism; Unconventional computation.

RR-2011-04 Characterizing Conclusive Approximations by Logical Formulae
Y. Boichut, T.-B.-H. Dao, V. Murat
Résumé : Tree Regular Model Checking is the name of a family of techniques for analyzing infinite-state systems in which states are represented by trees and sets of states by tree automata. We are interested in showing that a set of states Bad can not be reached from the set of initial states. Since the set of reachable is in general not computable, we focus on a computation of an over-approximation of the set of reachable states. A main obstacle is to be able to compute an over-approximation precise enough that does not intersect Bad i.e. a conclusive approximation. This notion of precision is often defined by a very technical parameter of techniques implementing this over-approximation approach. In this paper, we propose a new characterization of conclusive approximations by logical formulae generated from a new kind of automata called symbolic tree automata. Solving a such formula leads automatically to a conclusive approximation without extra-technical parameter.
Mot(s) Clé(s) :

RR-2011-05 Parallel Programming with Orléans Skeleton Library
Noman Javed, Frédéric Loulergue
Résumé : La bibliothèque Orléans Skeleton Library (OSL) de squelettes algorithmiques pour la programmation parallèle en C++, repose pour les communications sur MPI. OSL offre un modèle structuré de programmation parallèle, à la fois par ses squelettes et le modèle de parallélisme quasi-synchrone sous-jacent (BSP). Les applications en OSL sont développées en utilisant différentes combinaisons et compositions de squelettes. Cet article illustre l'expressivité d'OSL par deux applications: une simulation de diffusion de la chaleur en deux dimensions, et une simulation du problème des N-corps. Des expérimentations sur diverses machines parallèles sont réalisées avec ces applications.
Mot(s) Clé(s) : Programmation parallèle, Squelettes algorithmiques, Parallélisme quasi-synchrone, Applications

RR-2011-06 A Formal Programming Model of Orléans Skeleton Library
Noman Javed, Frédéric Loulergue
Résumé : Orléans Skeleton Library (OSL} est une bibliothèque de squelettes algorithmiques pour le langage C++, reposant pour les communications sur une bibliothèque MPI. OSL permet une approche structurée de la programmation parallèle. Les squelettes en OSL sont basés sur le modèle de parallélisme quasi-synchrone BSP. Dans ce rapport nous présentons une sémantique formelle pour OSL: un modèle de programmation et ses propertiés, modélisés dans l'assistant de preuves Coq.
Mot(s) Clé(s) : Programmation parallèle, Squelettes algorithmiques, Sémantique formelle, Assistant de preuves

RR-2011-07 Weak Inclusion for XML Types (full version)
Joshua Amavi, Jacques Chabin, Mirian Halfeld Ferrari, Pierre Réty
Résumé : Considering that the unranked tree languages L(G) and L(G) are those defined by given non-recursive XML types G and G, this paper proposes a simple and intuitive method to verify whether L(G) is “approximatively” included in L(G ). Our approximative criterion consists in weakening the father-children relationships. Experimental results are discussed, showing the efficiency of our method in many situations.
Mot(s) Clé(s) : XML, weak inclusion, tree languages

RR-2011-08 A Security-Aware Scheduler for Virtual Machines on IaaS Clouds
Zaina Afoulki, Zaina Afoulki, Jonathan Rouzaud-Cornabas
Résumé : With the number of services using virtualization and clouds growing faster and faster, it is common to mutualize thousands of virtual machines (vms) within one distributed system. Consequently, the virtualized services, softwares, hardwares and infrastructures share the same physical resources. This has given rise to important challenges regarding the security of vms and the importance of enforcing non-interference between those vms. Indeed, cross-vm attacks are an important and real world threat. The problem is even worse in the case of adversary users hosted on the same hardware and therefore the isolation facility within clouds needs to be strong. Furthermore, each user has different adversaries and the placement and scheduling processes need to take these adversaries into account. First, we show that the current isolation facility within clouds i.e. virtualization is weak and can be easily attacked. To avoid such vulnerabilities, we propose a security-aware scheduler that implements security policies expressing isolation requirements. The policies are expressed by the cloud users themselves by giving them the possibility to choose their own adversaries. Then, we show how we enforce these policies within our vm placement and migration algorithms. Finally, we present virtual networks with a better granularity for the clouds based on lists of trusted users. We conclude by presenting both physical and simulated experimental results showing the efficiency of our approach and the inability of other solutions to enforce such policies.
Mot(s) Clé(s) : IaaS, Security, Virtualization, Scheduling

RR-2011-09 A Trust Aware Distributed and Collaborative Scheduler for Virtual Machines in Cloud
Jonathan Rouzaud-Cornabas
Résumé : With the number of services using virtualization and clouds growing faster and faster, it is common to mutualize thousands of virtual machines within one distributed system. Consequently, the virtualized services, softwares, hardwares and infrastructures share the same physical resources, thus the performance of one depends of the resources usage of others. Furthermore, each user and his vms have different objectives in term of quality of trust and protection. Thus, the placement and reconfiguration processes need to take them into account. Finally, a new trend is to use clouds to build hpc systems but the deployment of such architecture is not straightforward. We propose a solution for vm placement and reconfiguration based on the observation of the resources quota and the dynamic usage that leads to better balancing of resources. Moreover, our solution also takes into account user’s objectives that express Quality of Trust and Protection and ease the deployment of hpc architectures on top of clouds. Furthermore, as it is not possible to have a single scheduler for the whole cloud and to avoid a single point of failure, our scheduler uses distributed and collaborative scheduling agents. Finally, we present a scenario simulating a geographical distributed clouds and multiple vm usage. This article is an extended version of [22]. It includes larger scale evaluations and the scheduler supports user’s objectives in addition of the resource-centric algorithms.
Mot(s) Clé(s) : IaaS, Virtualization, Scheduling, Distributed, Trust, HPC, Security

RR-2011-10 2nd International Workshop on New Worlds of Computation (NWC 2011)
Jérôme Durand-Lose (chair), Maxime Senot, Mathieu Chapelle
Résumé : The second edition of the international workshop "New Worlds of Computation", held on May the 23th and 24th, 2011, dealt with non-classical models of computation going beyond the usual Church-Turing computing. It included several important subjects such as quantum computing, analog and hybrid systems, membrane and DNA computing, abstract geometrical computation, spacial computing,... The following booklet contains all the abstracts of the talks given during this workshop.
Mot(s) Clé(s) : theoretical models of computation; unconventional computing; non-classical approaches; local proceedings

RR-2011-14 From Manual Cyber Attacks Forensic to Automatic Characterization of Attackers’ Profiles
J. Briffaut, P. Clemente, J.-F. Lalande, J. Rouzaud-Cornabas
Résumé : This chapter studies the activities of cyber attackers on a large scale honeypot run- ning for more than 2 years. A honeypot is a set of online computers that welcome attackers and let them perform their attacks. The chapter presents how to classify complex distributed sessions of attacks. The first part of this chapter analyzes the illegal activities performed by attackers using the data collected during two years of attacks: logged sessions, intrusion detection system alerts, mandatory access control system alerts. The study of these illegal activities allows to understand the global motivations of the cyber attackers, their technical skills and the geographical location of the attackers and their targets. The second part of this chapter presents generic methods to rebuild the illegal ac- tivities appearing on several attacked hosts. By correlating information collected by multiple sources (loggers, monitors, detectors) both watching at the network and the operations occurring on each system, we provide precise and high level characterization of attacks. The proposed method follows an incremental approach that characterizes attacks from basic ones to highly complex malicious activities, including largely distributed attacks (migrating/hopping attacks, distributed denials of service). This work reveals the global goals of attackers that take control of mul- tiple hosts to launch massive attacks on big universities, industries, or governmental organisations. Experimental results of these forensic and high level characteriza- tion methods are presented using the collected data of our large-scale honeypot.
Mot(s) Clé(s) :

RR-2011-15 ANR AGAPE - Implémentation d'algorithmes exacts pour le problème du stable maximum
Vincent Levorato
Résumé : Les travaux que j'ai effectués jusqu'à présent concernent l'implémentation d'algorithmes exacts connus sur le problème de la recherche d'un ensemble stable maximum dans les graphes, ainsi que l'étude et l'utilisation de la librairie MASCOPT et JUNG pour l'implémentation des algorithmes. >>>> Ce rapport détaille les algorithmes, explique l'implémentation de ceux-ci, et quels choix ont été retenus pour la représentation des structures de données. Il y sera également abordé des comparaisons d'implémentation avec d'autres librairies et/ou langage de programmation (C++ notamment), ainsi que des tests de performance. Les algorithmes sont détaillés pour faire apparaître certaines opérations non visibles dans les algorithmes de base (facteur polynomial) pour ainsi avoir une vision claire de la version implémentée. Une étude des résultats est également proposée en dernière partie.
Mot(s) Clé(s) : graphe, algorithmes exacts, stable, implémentation

RR-2011-16 ANR AGAPE - Implémentation du problème de couverture minimum et applications d'algorithmes exacts paramétrés aux graphes aléatoires
Vincent Levorato
Résumé : Ce document est axé autour de deux parties principales: l'implémentation d'algorithmes pour le problème du Minimum Vertex Cover et l'exposé de résultats concernant le comportement d'algorithmes Minimum Vertex Cover et Maximum Independent Set sur des graphes aléatoires et/ou réguliers particuliers.
Mot(s) Clé(s) : graphe, algorithmes exacts, algorithmes paramétrés, couverture, implémentation, génération graphes aléatoires

RR-2011-17 On minimum (K_q,k) stable graphs
Jean-Luc FOUQUET, Henri THUILLIER, Jean-Marie VAHERPE, Pawel WOJDA
Résumé : A graph G is (K_q,k) vertex stable (with q > 2) if it contains a copy of K_q after deleting any subset of k vertices. We are interested by the (K_q,kappa(q)) vertex stable graphs of minimum size where kappa(q) is the maximum value for which for every nonnegative integer k < kappa(q) the only (K_q,k) vertex stable graph with minimum size is K_{q+k}.
Mot(s) Clé(s) : Stable graph